博客读者Bogdan上周问这个问题：

我正在尝试找到对象之间最短路径的长度和位置。BWDIST的某些应用似乎应该能够做到这一点。有建议吗？例子：

1010100000 1 0 1 0 1

应该屈服

0 0 0 0 0 0 0 p 0 0 0 0 0 0 0 0

p =路径长度= 1

我同意，一些应用BWDISTshould do it. Actually, there are several other useful functions that can be applied to this task, includingImrigionalminandbwdistgeodesic，刚刚在R2011b中发货的新功能。

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 the interesting ideas and issues posed by this problem. Today I'll start with the basics of usingBWDISTandImrigionalmin确定一组从一个对象到另一个对象的最短路径。

Let's use this simple test image to start our exploration.

bw = [...0000000000 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ]

bw = 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0

我们希望从前景像素的左上块到右下块找到最短的路径（或路径！）。关键算法的想法是：

（有关参考，请参见P. Soille，形态图像分析：原理和应用，第二版，Springer，2003年，第7.3.4节，“应用于最小路径检测的应用”，第233-234页。）。

但是我们不能使用普通的欧几里得距离变换，因为它与从一个像素中心到另一个像素中心的路径遍历相对应。相反，我们必须使用支持的距离变换近似之一金宝appBWDIST：'棋盘'，，，，'城市街区'，，，，and'quasi-euclidean'。

这是使用的方法'quasi-euclidean'。

bw1 = [...0000000000 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]; bw2 = [...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];d1 = bwdist（bw1，'quasi-euclidean'）；d2 = bwdist（bw2，'quasi-euclidean'）；d_sum= D1 + D2; D_sum(3:5, 3:10)

ans = 7.8284 7.8284 7.8284 7.8284 7.8284 7.8284 8。41429.0000 8.4142 7.8284 7.8284 7.8284 7.8284 7.8284 7.8284 8.4142 9.0000 8.4142 7.8284 7.8284 7.8284 7.8284 7.8284 7.8284

您可以看到最小的价值d_sum约为7.8284，两个对象之间都有一个具有该值的对象。功能Imrigionalminidentifies them all:

path_pixels = imregionalmin(D_sum)

path_pixels = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

In the quasi-euclidean approximation to the distance transform, the distance from a pixel to one of its horizontal or vertical neighbors is 1, and the distance from a pixel to one of its diagonal neighbors is sqrt(2). The result above says that the shortest such path between the two objects is 7.8284. Furthermore, it says that there is more than one shortest path.

我计划本月更全面地探索这个主题。例如，当使用Quasi-Euclidean距离变换时，当您尝试将上述技术应用于较大图像时，必须处理一些浮点圆形问题。另一个问题是使用不同的基于路径的距离变换近似，例如'城市街区'or'棋盘'。Yet another issue is how to identify specific paths from the family of paths identified byImrigionalmin。一路走来，我将采用不同的方式来可视化结果。

Finally, I'll explore how to use a new function,bwdistgeodesic，在路径可以走到哪里时找到最短路径。

All the posts in this series

• the basic idea of finding shortest paths by adding two distance transforms together (part 1）
• the nonuniqueness of the shortest paths (part 2）
• 处理浮点圆形效果（part 3）
• 使用thinning to pick out a single path (part 4）
• 使用bwdistgeodesic找到受约束约束的最短路径（part 5）

Get the MATLAB code

以MATLAB®7.13出版