use dijkstra algorithm to segment images

8 次查看（过去 30 天）
André
André 2024-12-18
编辑： André 2024-12-21
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.
  2 个评论
Walter Roberson
Walter Roberson 2024-12-18
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é
André 2024-12-18
编辑：André 2024-12-18
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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

André
André 2024-12-21
编辑：André 2024-12-21
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

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Dijkstra algorithm 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by