距离变换最快的可用算法
image-processing
5
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年的消息来源,因此非常感谢您的帮助。

参考资料:
Stack Overflow
收藏
评论
共 5 个回答
高赞 时间 活跃

我已经实现了Vinnie的答案中引用的Meijster的O(N)方法。 “用于计算线性时间中距离变换的通用算法。” http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

令人高兴的是,它可以非常有效地并行化,独立地计算每条像素线(这是一种可分离的方法)。运行在12个CPU内核上,几秒钟内即可计算出1000 ^ 3体积图像的距离字段。

Felzenszwalb和Huttenlocher于2012年提出的“采样函数的距离变换”解决方案(引用bw1024的答案)基于完全相同的想法。有趣的是,他们没有引用Meijster在12年前所做的工作。

收藏
评论

在计算距离函数方面有大量新工作。

顺便说一句,您真的想用这些来代替Rosenfeld的工作,特别是当您要在存在障碍物的情况下计算距离时。

收藏
评论

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单元下方。之后,执行从右下到左上的第二遍(使用垂直和水平翻转的蒙版)。第二次通过后,将计算距离。

收藏
评论

Felzenszwalb和Huttenlocher在其论文“采样函数的距离变换”中提供一种精确的精确算法,并且O(N)在此处可用。他们利用了以下事实:欧几里德距离变换的平方是一个抛物线,可以在每个维度上独立地对其进行评估。

源代码也可用

收藏
评论

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

“二维欧氏距离变换算法:比较调查”
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

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号