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

In this post in the Exploring shortest paths<\/i> series, I make things a little more complicated (and interesting) by adding constraints to the shortest path problem. Last\r\n time, I showed this example of finding the shortest paths between the \"T\" and the sideways \"s\" in this image:\r\n <\/p>

url = 'https:\/\/blogs.mathworks.com\/images\/steve\/2011\/two-letters-cropped.png'<\/span>;\r\nbw = imread(url);<\/pre>
And this was the result:<\/p>\r\n   
 <\/p>\r\n   
What if we complicate the problem by adding other objects to the image and looking for the shortest path that avoids these\r\n      other objects?\r\n   <\/p>\r\n   
For example, what if we want to find a shortest path between the \"T\" and the sideways \"s\" without going through any of other\r\n      letters between them in the image below?\r\n   <\/p>
url = 'https:\/\/blogs.mathworks.com\/images\/steve\/2011\/text-cropped.png'<\/span>;\r\ntext = imread(url);\r\nimshow(text, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
We can do this by using bwdistgeodesic<\/tt> instead of bwdist<\/tt> in our algorithm. bwdistgeodesic<\/tt> is a new function in the R2011b release of the Image Processing Toolbox. In addition to taking a binary image input that\r\n      bwdist<\/tt> takes, it takes another argument that specifies which pixels the paths are allowed to traverse.\r\n   <\/p>\r\n   
Let's use our text image to make a mask of allowed path pixels.<\/p>
mask = ~text | bw;\r\nimshow(mask, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
Next, we make our two binary object images as before.<\/p>
L = bwlabel(bw);\r\nbw1 = (L == 1);\r\nbw2 = (L == 2);<\/pre>
Next, instead of using bwdist<\/tt>, we use bwdistgeodesic<\/tt>.\r\n   <\/p>
D1 = bwdistgeodesic(mask, bw1, 'quasi-euclidean'<\/span>);\r\nD2 = bwdistgeodesic(mask, bw2, 'quasi-euclidean'<\/span>);\r\n\r\nD = D1 + D2;\r\nD = round(D * 8) \/ 8;\r\n\r\nD(isnan(D)) = inf;\r\npaths = imregionalmin(D);\r\n\r\npaths_thinned_many = bwmorph(paths, 'thin'<\/span>, inf);\r\nP = false(size(bw));\r\nP = imoverlay(P, ~mask, [1 0 0]);\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> 
In the image above, the white characters are the starting and ending points for the path. The path is not allowed to pass\r\n      through the red characters. The gray pixels are all the pixels on any shortest path, and the yellow pixels lie along one particular\r\n      shortest path.\r\n   <\/p>\r\n   
Let's have a little fun by using this technique to solve a maze. Here's a test maze (created by The Maze Generator<\/a>).\r\n   <\/p>
url = 'https:\/\/blogs.mathworks.com\/images\/steve\/2011\/maze-51x51.png'<\/span>;\r\nI = imread(url);\r\nimshow(I)<\/pre> 
Make an image of walls by thresholding the maze image. Dilate the walls (make them a little thicker) in order to keep the\r\n      solution path a little bit away from them.\r\n   <\/p>
walls = imdilate(I < 128, ones(7,7));\r\nimshow(walls)<\/pre> 
The function bwgeodesic<\/tt> will take seed locations (as column and row coordinates) in addition to binary images. Below I specify the seed locations\r\n      as the two entry points into the maze.\r\n   <\/p>
D1 = bwdistgeodesic(~walls, 1, 497, 'quasi-euclidean'<\/span>);\r\nD2 = bwdistgeodesic(~walls, 533, 517, 'quasi-euclidean'<\/span>);<\/pre>
The rest of the procedure is the same as above.<\/p>
D = D1 + D2;\r\nD = round(D * 8) \/ 8;\r\n\r\nD(isnan(D)) = inf;\r\npaths = imregionalmin(D);\r\n\r\nsolution_path = bwmorph(paths, 'thin'<\/span>, inf);\r\nthick_solution_path = imdilate(solution_path, ones(3,3));\r\nP = imoverlay(I, thick_solution_path, [1 0 0]);\r\nimshow(P, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
(If you're interested in other maze-solving techniques using image processing, take a look at the File Exchange contribution\r\n      maze_solution<\/a> by Image Analyst<\/a>.)\r\n   <\/p>\r\n   
In a comment on part 1 of this series<\/a>, Sepideh asked this question:\r\n   <\/p>\r\n   
\"I have a binary image which contains one pixel width skeleton of an image. I have got the skeleton using the bwmorph function.\r\n      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\r\n      ‘quasi-euclidean’ distance between two nonzero elements which are on the skeleton? The path should be on the skeleton itself\r\n      too.\"\r\n   <\/p>\r\n   
The techniques described above can be applied to this path-along-a-skeleton problem. Let's try an example.<\/p>
bw = imread('circles.png'<\/span>);\r\nimshow(bw, 'InitialMagnification'<\/span>, 200)<\/pre> 
skel = bwmorph(bw, 'skel'<\/span>, Inf);\r\nimshow(skel, 'InitialMagnification'<\/span>, 200)<\/pre> 
Let's find the skeleton-constrained path distance between these two points.<\/p>
r1 = 38;\r\nc1 = 53;\r\n\r\nr2 = 208;\r\nc2 = 147;\r\n\r\nhold on<\/span>\r\nplot(c1, r1, 'g*'<\/span>, 'MarkerSize'<\/span>, 15)\r\nplot(c2, r2, 'g*'<\/span>, 'MarkerSize'<\/span>, 15)\r\nhold off<\/span><\/pre> 
D1 = bwdistgeodesic(skel, c1, r1, 'quasi-euclidean'<\/span>);\r\nD2 = bwdistgeodesic(skel, c2, r2, 'quasi-euclidean'<\/span>);\r\n\r\nD = D1 + D2;\r\nD = round(D * 8) \/ 8;\r\n\r\nD(isnan(D)) = inf;\r\nskeleton_path = imregionalmin(D);\r\nP = imoverlay(skel, imdilate(skeleton_path, ones(3,3)), [1 0 0]);\r\nimshow(P, 'InitialMagnification'<\/span>, 200)\r\nhold on<\/span>\r\nplot(c1, r1, 'g*'<\/span>, 'MarkerSize'<\/span>, 15)\r\nplot(c2, r2, 'g*'<\/span>, 'MarkerSize'<\/span>, 15)\r\nhold off<\/span><\/pre> 
Finally, the skeleton path length is given by the value of D<\/tt> at any point along the path.\r\n   <\/p>
path_length = D(skeleton_path);\r\npath_length = path_length(1)<\/pre>
\r\npath_length =\r\n\r\n  239.2500\r\n\r\n<\/pre>\r\n
All the posts in this series<\/h4>\r\n