最快的距离变换算法

Question

最快的距离变换算法

Kar*_*arl 26 algorithm transform distance image-processing

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

根据这个网站http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm,它描述了:"距离变换可以使用聪明的算法在两次通过中更有效地计算(例如Rosenfeld和Pfaltz 1968)."

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

但我相信我们应该拥有比1968年更好更快的算法？事实上,我找不到1968年的来源,所以任何帮助都受到高度赞赏.

Answer 1

Vin*_*lco 14

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

"2D欧几里德距离变换算法:比较调查"
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 2

Chr*_*mer 12

OpenCV库为其近似的cv :: distanceTransform函数使用了一种算法,该算法将图像从左上角传递到右下角.该算法在Gunilla Borgefors的文章"数字图像中的距离变换" (Comput.Vision Graph.Image Process.34 3,pp 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 |
+------+------+------+------+------+

Run Code Online (Sandbox Code Playgroud)

从一个像素到另一个像素的距离是所需跳跃的成本之和.下图显示了从0细胞到每个其他细胞的距离.箭头显示了通向某些细胞的方式.彩色数字反映了确切的(欧几里德)距离.

在此输入图像描述

该算法的工作方式如下:掩码后面

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

Run Code Online (Sandbox Code Playgroud)

从图像的左上角移动到右下角.在此阶段,细胞躺在面具一直保持它们的值(如果它被称为小),或者他们得到由细胞求和掩模值和细胞值(如果已知)的计算值的边界内在mask-0-cell下面.之后,执行从右下到左上的第二次通过(具有垂直和水平翻转掩模).在第二次通过之后,计算距离.