{"id":395,"date":"2011-11-01T13:57:03","date_gmt":"2011-11-01T17:57:03","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2011\/11\/01\/exploring-shortest-paths-part-1\/"},"modified":"2019-10-29T16:58:48","modified_gmt":"2019-10-29T20:58:48","slug":"exploring-shortest-paths-part-1","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2011\/11\/01\/exploring-shortest-paths-part-1\/","title":{"rendered":"Exploring shortest paths – part 1"},"content":{"rendered":"
\r\n

Blog reader Bogdan<\/a> asked this question last week:\r\n <\/p>\r\n

I am trying to find the length and location of the shortest path between objects. It seems like some application of bwdist\r\n should be able to do this. Any advice? Example:<\/i><\/p>

1 0 1\r\n0 1 0\r\n0 0 0\r\n0 1 0\r\n1 0 1<\/pre>
Should yield<\/i><\/p>
0 0 0\r\n0 0 0\r\n0 p 0\r\n0 0 0\r\n0 0 0<\/pre>
With p = path length = 1<\/i><\/p>\r\n   
I agree, some application of bwdist<\/tt> should do it. Actually, there are several other useful functions that can be applied to this task, including imregionalmin<\/tt> and bwdistgeodesic<\/tt>, a new function that just shipped in R2011b.\r\n   <\/p>\r\n   
I've been tinkering with this problem off and on for a few days, and I think it might take a few posts to explore some of\r\n      the interesting ideas and issues posed by this problem. Today I'll start with the basics of using bwdist<\/tt> and imregionalmin<\/tt> to identify a set of shortest paths from one object to another.\r\n   <\/p>\r\n   
Let's use this simple test image to start our exploration.<\/p>
bw = [ ...<\/span>\r\n    0 0 0 0 0 0 0 0 0 0 0 0\r\n    0 1 1 0 0 0 0 0 0 0 0 0\r\n    0 1 1 0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0 0 0 1 1 0\r\n    0 0 0 0 0 0 0 0 0 1 1 0\r\n    0 0 0 0 0 0 0 0 0 0 0 0   ]<\/pre>
\r\nbw =\r\n\r\n     0     0     0     0     0     0     0     0     0     0     0     0\r\n     0     1     1     0     0     0     0     0     0     0     0     0\r\n     0     1     1     0     0     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0     0     0     1     1     0\r\n     0     0     0     0     0     0     0     0     0     1     1     0\r\n     0     0     0     0     0     0     0     0     0     0     0     0\r\n\r\n<\/pre>
We want to find the shortest path (or paths!) from the upper left block of foreground pixels to the lower right block. The\r\n      key algorithmic idea is this:\r\n   <\/p>\r\n   
\r\n      
    \r\n         
  1. Compute the distance transform for just the upper left block of foreground pixels.<\/li>\r\n         
  2. Compute the distance transform for just the lower right block of foreground pixels.<\/li>\r\n         
  3. Add the two distance transforms together.<\/li>\r\n         
  4. The pixels in the regional minimum of the result lie along one or more of the shortest paths from one block to the other.<\/li>\r\n      <\/ol>\r\n   <\/div>\r\n   
    (For reference, see P. Soille, Morphological Image Analysis: Principles and Applications, 2nd edition, Springer, 2003, section\r\n      7.3.4, \"Application to minimal path detection,\" pp. 233-234.)\r\n   <\/p>\r\n   
    But we can't use the normal Euclidean distance transform because it doesn't correspond to a path traversal from one pixel\r\n      center to another. Rather, we have to use one of the distance transform approximations supported by bwdist<\/tt>: 'chessboard'<\/tt>, 'cityblock'<\/tt>, and 'quasi-euclidean'<\/tt>.\r\n   <\/p>\r\n   
    Here's how to do it using 'quasi-euclidean'<\/tt>.\r\n   <\/p>
    bw1 = [ ...<\/span>\r\n    0 0 0 0 0 0 0 0 0 0 0 0\r\n    0 1 1 0 0 0 0 0 0 0 0 0\r\n    0 1 1 0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0 0 0 0 0 0   ];\r\n\r\nbw2 = [ ...<\/span>\r\n    0 0 0 0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0 0 0 1 1 0\r\n    0 0 0 0 0 0 0 0 0 1 1 0\r\n    0 0 0 0 0 0 0 0 0 0 0 0   ];\r\n\r\nD1 = bwdist(bw1, 'quasi-euclidean'<\/span>);\r\nD2 = bwdist(bw2, 'quasi-euclidean'<\/span>);\r\n\r\nD_sum = D1 + D2;\r\nD_sum(3:5, 3:10)<\/pre>
    \r\nans =\r\n\r\n    7.8284    7.8284    7.8284    7.8284    7.8284    7.8284    8.4142    9.0000\r\n    8.4142    7.8284    7.8284    7.8284    7.8284    7.8284    7.8284    8.4142\r\n    9.0000    8.4142    7.8284    7.8284    7.8284    7.8284    7.8284    7.8284\r\n\r\n<\/pre>
    You can see that the smallest value of D_sum<\/tt> is about 7.8284, and there's a set of pixels in-between the two objects that all have that value. The function imregionalmin<\/tt> identifies them all:\r\n   <\/p>
    path_pixels = imregionalmin(D_sum)<\/pre>
    \r\npath_pixels =\r\n\r\n     0     0     0     0     0     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0     0     0     0     0     0\r\n     0     0     1     1     1     1     1     1     0     0     0     0\r\n     0     0     0     1     1     1     1     1     1     0     0     0\r\n     0     0     0     0     1     1     1     1     1     1     0     0\r\n     0     0     0     0     0     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0     0     0     0     0     0\r\n\r\n<\/pre>
    In the quasi-euclidean approximation to the distance transform, the distance from a pixel to one of its horizontal or vertical\r\n      neighbors is 1, and the distance from a pixel to one of its diagonal neighbors is sqrt(2). The result above says that the\r\n      shortest such path between the two objects is 7.8284. Furthermore, it says that there is more than one shortest path.\r\n   <\/p>\r\n   
    I plan to explore this topic more fully this month. When using the quasi-euclidean distance transform, for example, there\r\n      are floating-point round-off issues that have to be dealt with when you try to apply the technique above to larger images.\r\n      Another issue is the effect of using different path-based distance transform approximations, such as 'cityblock'<\/tt> or 'chessboard'<\/tt>. Yet another issue is how to identify specific paths from the family of paths identified by imregionalmin<\/tt>. Along the way I'll experiment with different ways to visualize the results.\r\n   <\/p>\r\n   
    Finally, I'll explore how to use a new function, bwdistgeodesic<\/tt>, to find shortest paths when there are constraints on where the paths can go.\r\n   <\/p>\r\n\r\n
    All the posts in this series<\/h4>\r\n