shortestpath between two points on skeleton in binary image

Hi,

I have a binary image which contains one pixel width skeleton of an image. I have got the skeleton using the bwmorph function. As you may know basically in this binary image, I have ones on the skeleton and zeros anywhere else. how can I find the shortest ‘quasi-euclidean’ distance between two nonzero elements which are on the skeleton? The path should be on the skeleton itself too. I guess bwdist will be helpful for my problem, but I don't know how to apply it for this case.

I will really appreciate any help. Thanks,

Answer 1

[Ashish Uthama]

Maybe this blog post by Steve could give you some ideas. You could start out with an image with just the two points, go through the process in the blog and then add your skeleton as a mask at the end.

Or, you could just treat it as a graph and look to implement a basic Dijkstra's algorithm.

Answer 2

[George Abrahams]

Hi Sepideh. To expand upon @Ashish Uthama's answer, if you want to go down the shortestpath route which uses Dijkstra's algorithm, you can use my bwgraph function on File Exchange to construct the graph. See the example below.

By default, the edges of the graph will have weights (effectively, distances) which are Euclidean, so pixels sharing an edge have a distance of 1, and pixels sharing a corner will have a distance of . The total path distance will be the sum of these.

BW = imread( 'circles.png' );
BW = bwmorph( BW, 'skel', Inf ); % also consider bwskel.
% Construct the graph of connected non-zero pixels.
G = bwgraph( BW );
% Calculate the linear indices of the start and end pixels, which are 
% used to reference the respective node in G.
sz = size( BW );
source = sub2ind( sz, 25, 28 );
target = sub2ind( sz, 196, 192 );
% Find the shortest path between the 2 nodes.
P = shortestpath( G, source, target );
% Calculate the respective pixels for each node in the path.
[ Pi, Pj ] = ind2sub( sz, P );
% Plot the image and path.
figure
imshow( BW )
hold on
plot( Pj, Pi, 'r-', 'LineWidth', 4 )

Answer 3

[Catalytic]

You can use bwdistgeodesic.

[Image Analyst]

See Steve's blog series on it:Exploring shortest paths – bwdistgeodesic, as @Ashish Uthama already mentioned.