OpenCV库将近似的cv :: distanceTransform函数使用一种算法,该算法将图像从左上角传递到右下角并返回。该算法在Gunilla Borgefors的论文“数字图像中的距离变换”中进行了描述(Comput。Vision Graph。Image Process。34 3,第344–371页,1986) 。
该算法通过一些基本跳跃(水平,垂直,对角线和骑士移动)的组合来计算距离。每次跳跃都会产生费用。下表显示了不同跳转的成本。
+------+------+------+------+------+
| 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 |
+------+------+------+
从图像的左上方移动到右下方。在此过程中,位于蒙版边界内的单元格保持其值(如果已知且较小),或者从单元格中获取通过将蒙版值与单元格值(如果已知)相加得出的值在mask-0单元下方。之后,执行从右下到左上的第二遍(使用垂直和水平翻转的蒙版)。第二次通过后,将计算距离。
0
我正在寻找距离转换最快的可用算法。
根据该站点http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm的描述,该站点描述: “仅使用两个遍历(例如Rosenfeld和Pfaltz 1968)。”
到处搜寻,我发现: “ Rosenfeld,A和Pfaltz,J.L。1968年。数字图片上的距离函数。模式识别,1,33-61。”
但是我相信我们应该有一个比1968年更好,更快的算法吗?实际上,我找不到1968年的消息来源,因此非常感谢您的帮助。