use dijkstra algorithm to segment images

I would like to use graph cut to segment hundreds of large images using Dijkstra's algorithm, in a fully automated fashion,and using custom weights, so the MATLAB function grabcut is not suitable. Using the Image Segmenter App is also not an option. Segmentation must be fully automated, and I already know how to specify the endpoints.

What I am struggling is in constructing the adjacency array in an efficient manner and the best way to efficienlty fill the sparse matrix.

Does anyone know an efficient implementation of this algorithm? Everything I have seen online is for small images, does not involve sparse matrices, and so does not seem efficient at all. I have also seen FEX implementations of Dijkstra's algorithm, but I am not sure if they work with sparse matrices or large arrays.

[Walter Roberson]

It is not clear to me exactly what is sparse? Are the images themselves somehow sparse?

I am having difficulty figuring out how Dijkstra's algorithm fits into the situation. It sounds as if bwdistgeodesic would be more suitable.

[André]

I believe this is the original paper using the algorithm: https://pmc.ncbi.nlm.nih.gov/articles/PMC3408910/

So, instead of weights representing minimum distance, they use weights representing maximum gradients between objects, where larger gradients are encoded by smalle weights.

Because typical images have at least 1000x1000 pixels, this would require insanely large adjacency matrices (in this case 1000^2 x 1000^2), but because pixel conectivity is usually 4 or 8, the matrix is also extremely sparse.

Anyway, I can use other algorithms than Dijkstra, the important here is efficiently building the adjacency matrix.

Answer 1

[André]

Seems I ended up solving the problem after a lot of effort and research. I found two fantastic packages that allowed me to solve the problem. I share everything with the MATLAB comunity, so you can use it in the future. This is the most efficient method I found:

Requires the following very efficient function to create sparse adjancency matrix:

https://github.com/shaibagon/GCMex/blob/master/sparse_adj_matrix.m

And requires also this FEX containing a very efficient implementation of the Dijkstra algorithm:

https://www.mathworks.com/matlabcentral/fileexchange/24134-gaimc-graph-algorithms-in-matlab-code?s_tid=srchtitle

Took 2 seconds to process the image.

Please let me know if you know of a more efficient implementation.

img = imread('I.jpg');
imshow(img);

fPrewittHorizontal = fspecial("prewitt");
imgGrad = mat2gray(imfilter(img, fPrewittHorizontal, 'replicate'));

% Padding
% hGradPad = padarray(hGrad, [1,1]);

imgGradPad = padarray(imgGrad, [0,1], 1); % pad with maximum value, so that weight is minimum

wmin = 10e-5;
r = 1;

tic
% Create adjacency matrix
dims = size(imgGradPad);
N = numel(imgGradPad);
[ii, jj] = sparse_adj_matrix(dims, r, 2);

% Remove pixels neighbours with themselves (diagonal elements)
valid = ii~=jj;
ii = ii(valid);
jj = jj(valid);

% Compute weights
vv = 2 - (imgGradPad(ii) + imgGradPad(jj)) + wmin;

% Create adjacency matrix
Adj = sparse(ii, jj, vv, N, N);

% Apply Dijkstra algorithm to find shortest path
source = 1;
[d, pred] = dijkstra(Adj, source);
destiny = N;

u = destiny;
shortestpath = [];
while (u ~= source) 
    shortestpath = [u, shortestpath]; 
    u = pred(u); 
end

BW = false(dims);
BW(shortestpath) = true;

t = toc
imshow(imoverlay(img, BW(:,2:end-1))); % dont forget to remove padding from the mask