Find closest 8-connected chessboard distance between multiple pairs of points: shortest m-path

1 回表示 (過去 30 日間)
I am working on binary images. I have two sets of points: PNodes and FNodes. I want to find the closest PNode to each of the FNodes (shortest m-path); closest in terms of 8-connected chessboard distance.
In the example below, suppose PNodes (donated by *) are: (6,1), (6,5) and (5,8). (indexing starts from 0, first element is row number). FNodes (denoted by #) are: (0,1), (0,9), (1,6), (2,5) and (4,3).
In =
[0, 1#, 0, 0, 0, 0, 0, 0, 0, 1#, 0;
1, 0, 0, 0, 0, 0, 1#, 0, 1, 0, 0;
0, 1, 0, 0, 0, 1#, 0, 0, 1, 0, 0;
0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0;
0, 1, 1, 1#, 0, 1, 0, 0, 1, 0, 0;
0, 1, 0, 0, 0, 1, 0, 0, 1*, 0, 0;
0, 1*, 0, 0, 0, 1*, 0, 0, 1, 0, 0;
0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0;
0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]
Distance Matrix =
[0, 6#, 0, 0, 0, 0, 0, 0, 0, 5#, 0;
5, 0, 0, 0, 0, 0, 5#, 0, 4, 0, 0;
0, 4, 0, 0, 0, 4#, 0, 0, 3, 0, 0;
0, 0, 3, 0, 0, 0, 3, 0, 0, 2, 0;
0, 2, 2, 3#, 0, 2, 0, 0, 1, 0, 0;
0, 1, 0, 0, 0, 1, 0, 0, **, 0, 0;
0, **, 0, 0, 0, **, 0, 0, 1, 0, 0;
0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0;
0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]
I want to find out the distance of closest path from each FNode to reach closest PNode. Something like this: FNode at (0,1) is closest to PNode at (6,1). FNode at (4,3) is closest to PNode at (6,1). All distances are in terms of 8-connected chessboard distance.
Ultimate requirement from this entire process: I just want to make sure all PNodes have atleast 1 FNode which lie within a given distance range (along the path of 1s);
Suppose PNode (PN_1) has a FNode (FN_1) which lies within the required distance range, I also make sure that PN_1 is closest to FN_1, and not any other PNode.
For a better understanding, I have attached an image below; FNodes are rectangular and PNodes are circular.
I don't care about other elements in the matrix, apart from those of PNodes and FNodes, as depicted.

回答 (1 件)

Image Analyst
Image Analyst 2018 年 1 月 19 日
See Steve's 5-part blog series on shortest path distances in images: http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/ It goes into a lot of detail that should help you if you make an effort to follow along.

Community Treasure Hunt

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

Start Hunting!

Translated by