{"id":398,"date":"2011-12-06T07:00:11","date_gmt":"2011-12-06T12:00:11","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=398"},"modified":"2019-10-29T17:02:03","modified_gmt":"2019-10-29T21:02:03","slug":"exploring-shortest-paths-part-4","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2011\/12\/06\/exploring-shortest-paths-part-4\/","title":{"rendered":"Exploring shortest paths – part 4"},"content":{"rendered":"
\r\n

In my previous posts on Exploring shortest paths<\/i> (November 1<\/a>, November 26<\/a>, and December 3), I have noted several times that there isn't a unique shortest path (in general) between one object and another in a binary\r\n image. To illustrate, here's a recap of the 'quasi-euclidean' example from last time.\r\n <\/p>

bw = logical([ ...<\/span>\r\n    0 0 0 0 0 0 0\r\n    0 1 0 0 0 0 0\r\n    0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0\r\n    0 0 0 0 0 1 0\r\n    0 0 0 0 0 0 0  ]);\r\nL = bwlabel(bw);\r\nbw1 = (L == 1);\r\nbw2 = (L == 2);\r\n\r\nD1 = bwdist(bw1, 'quasi-euclidean'<\/span>);\r\nD2 = bwdist(bw2, 'quasi-euclidean'<\/span>);\r\nD = D1 + D2;\r\nD = round(D * 32) \/ 32;\r\n\r\npaths = imregionalmin(D);\r\nP = false(size(bw));\r\nP = imoverlay(P, paths, [.5 .5 .5]);\r\nP = imoverlay(P, bw, [1 1 1]);\r\nimshow(P, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
The gray pixels shown above all<\/b> belong to one or more of the shortest paths between the two objects. So how do we pick one path?\r\n   <\/p>\r\n   
The first idea I had was to thin the paths \"blob\" using the 'thin' option of bwmorph<\/tt>.\r\n   <\/p>
paths_thinned_once = bwmorph(paths, 'thin'<\/span>);\r\nP = false(size(bw));\r\nP = imoverlay(P, paths, [.5 .5 .5]);\r\nP = imoverlay(P, paths_thinned_once, [1 1 0]);\r\nP = imoverlay(P, bw, [1 1 1]);\r\nimshow(P, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
That seems promising. What if we keep thinning until convergence? You do that by passing inf<\/tt> as the repetition value to bwmorph<\/tt>.\r\n   <\/p>
paths_thinned_many = bwmorph(paths, 'thin'<\/span>, inf);\r\nP = false(size(bw));\r\nP = imoverlay(P, paths, [.5 .5 .5]);\r\nP = imoverlay(P, paths_thinned_many, [1 1 0]);\r\nP = imoverlay(P, bw, [1 1 1]);\r\nimshow(P, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
That looks great.<\/p>\r\n   
Let's try the whole sequence with a longer path.<\/p>
url = 'https:\/\/blogs.mathworks.com\/images\/steve\/2011\/two-letters-cropped.png'<\/span>;\r\nbw = imread(url);\r\nimshow(bw, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
L = bwlabel(bw);\r\nbw1 = (L == 1);\r\nbw2 = (L == 2);\r\n\r\nD1 = bwdist(bw1, 'quasi-euclidean'<\/span>);\r\nD2 = bwdist(bw2, 'quasi-euclidean'<\/span>);\r\nD = D1 + D2;\r\nD = round(D * 32) \/ 32;\r\n\r\npaths = imregionalmin(D);\r\n\r\npaths_thinned_many = bwmorph(paths, 'thin'<\/span>, inf);\r\nP = false(size(bw));\r\nP = imoverlay(P, paths, [.5 .5 .5]);\r\nP = imoverlay(P, paths_thinned_many, [1 1 0]);\r\nP = imoverlay(P, bw, [1 1 1]);\r\nimshow(P, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
As before, the pixels belonging to any shortest path are shown in gray. The pixels in yellow belong to one particular path.<\/p>\r\n   
Next time I'll explain how to find shortest paths subject to constraints.<\/p>\r\n
All the posts in this series<\/h4>\r\n