我已经实现了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年前所做的工作。

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

• 快速行进算法最初来自Tsitsiklis（不像Wikipedia所说的Sethian）。大量的实现可用于此。
• 赵的快速清扫算法
• O（n）（近似）由Yatziv快速行进

顺便说一句，您真的想用这些来代替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