距离变换的最快可用算法 [英] Fastest available algorithm for distance transform

问题描述

我正在寻找最快的距离变换算法.

I am looking for the fastest available algorithm for distance transform.

根据本网站 http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm，它描述了:使用巧妙的算法只需两次传递即可更有效地计算距离变换(例如 Rosenfeld 和 Pfaltz 1968)."

According to this site http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm, it describes: "The distance transform can be calculated much more efficiently using clever algorithms in only two passes (e.g. Rosenfeld and Pfaltz 1968)."

四处搜索，我发现:Rosenfeld, A 和 Pfaltz, J L. 1968.数字图片上的距离函数.模式识别，1, 33-61."

但我相信我们应该已经拥有比 1968 年更好更快的算法了吧?事实上，我找不到 1968 年的来源，因此非常感谢任何帮助.

But I believe we should have a better and faster algorithm than the one in 1968 already? In fact, I could not find the source from 1968, so any help is highly appreciated.

推荐答案

有大量关于计算距离函数的新工作.

There's tons of newer work on computing distance functions.

• 最初来自 Tsitsiklis(不是像维基百科所说的 Sethian)的快速行进算法. 有大量的实现可用于此.
• 赵的快速扫描算法
• Yatziv 的 O(n)(近似)快速行军莉>

• Fast marching algorithms that originally came from Tsitsiklis (not Sethian like Wikipedia says). Tons of implementations are available for this.
• Fast sweeping algorithms from Zhao
• O(n) (approximate) fast marching by Yatziv

顺便说一句，您真的希望使用这些来代替 Rosenfeld 的工作，特别是当您想在存在障碍的情况下计算距离时.

By the way, you'd really want to use these instead of the work by Rosenfeld, specifically when you want to compute distances in the presence of obstacles.

这篇关于距离变换的最快可用算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！