最快可用的距离变换算法

Question

我在寻找最快的距离转换算法。

根据这个站点http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm，它描述了：“使用聪明的算法，只需两次（例如Rosenfeld和Pfaltz 1968）就可以更有效地计算距离变换。”

四处搜寻，我发现：“罗森菲尔德，A和普法茨，J L.1968。数字图像上的距离函数。模式识别，1，33-61.“

但我相信我们应该有一个比1968年更好更快的算法？事实上，我找不到1968年的消息来源，所以我非常感谢你的帮助。

Answer 1

在计算距离函数方面有很多新的工作。

• Fast marching algorithms that originally came from Tsitsiklis (not Sethian like Wikipedia says).有大量的实现可用于此。
• Fast sweeping algorithms from Zhao
• O(n) (approximate) fast marching by Yatziv

顺便说一句，你真的想用这些来代替罗森菲尔德的工作，特别是当你想在有障碍物的情况下计算距离的时候。

Answer 2

本文回顾了已知的精确距离变换算法：

“二维欧氏距离变换算法：比较研究”
http://liu.diva-portal.org/smash/get/diva2:23335/FULLTEXT01

最快的精确距离转换来自Meijster：

“计算线性时间中距离变换的通用算法。”
http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

该算法的设计特别适合于并行计算。

这是在我的开源库中实现的，它试图模仿Photoshop的“图层样式”：

https://github.com/vinniefalco/LayerEffects

Answer 3

OpenCV库使用近似的cv::distanceTransform函数，该算法将图像从左上角到右下角再向后传递。本文描述了Gunilla Borgefors（Comput）的“数字图像中的距离变换”算法。视觉图表。图像处理。34 3，第344-3711986页）。

该算法通过一些基本跳跃（水平、垂直、对角线和骑士移动）的组合计算距离。每次跳跃都会产生成本。下表显示了不同跳跃的成本。

+------+------+------+------+------+
| 2.8  |2.1969|   2  |2.1969|  2.8 |
+------+------+------+------+------+
|2.1969|  1.4 |   1  |  1.4 |2.1969|
+------+------+------+------+------+
|   2  |   1  |   0  |   1  |   2  |
+------+------+------+------+------+
|2.1969|  1.4 |   1  |  1.4 |2.1969|
+------+------+------+------+------+
| 2.8  |2.1969|   2  |2.1969|  2.8 |
+------+------+------+------+------+

从一个像素到另一个像素的距离是必要的跳跃成本之和。下图显示了从0单元格到其他单元格的距离。箭头是指向某些单元格的方向。彩色数字反映了精确的（欧几里德）距离。

算法的工作原理如下：跟踪掩码

+------+------+------+
|   0  |   1  |   2  |
+------+------+------+
|   1  |  1.4 |2.1969|
+------+------+------+
|   2  |2.1969|  2.8 |
+------+------+------+

从图像的左上角移动到右下角。在此过程中，位于掩码边界内的单元格要么保留其值（如果已知且较小），要么通过将掩码值与掩码0单元格下的单元格值（如果已知）相加来获得计算值。 之后，执行从右下到左上的第二次传递（使用垂直和水平翻转的遮罩）。第二次通过后，计算距离。