我正在寻找最快的距离变换算法。
根据图像处理学习资源 - HIPR 2（超媒体图像处理参考） - 形态 - 距离变换：
使用巧妙的算法，只需两遍（例如 Rosenfeld 和 Pfaltz 1968），就可以更有效地计算距离变换。
环顾四周，我发现：“Rosenfeld, A 和 Pfaltz, J L. 1968。数码照片上的距离函数。模式识别，1, 33-61。”
但我相信我们应该已经有了比 1968 年更好更快的算法？事实上，我找不到 1968 年的源代码，因此非常感谢任何帮助。
最快的距离变换算法
信息处理
图像处理
算法
距离度量
2021-12-22 23:46:47
3个回答
Pedro F. Felzenszwalb 和 Daniel P. Huttenlocher 发布了他们的距离变换实现。您不能将它用于体积图像，但也许您可以扩展它以支持 3d 数据。我只将它用作黑匣子。
本文讨论了所有现代精确距离变换：
“2D 欧几里得距离变换：比较调查”，ACM 计算调查，第 40 卷，第 1 期，2008 年 2 月 http://www.lems.brown.edu/~rfabbri/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf
该论文引用了 Meijster 等人的技术。人。作为最快的通用，精确变换。此处详细介绍了此技术：
“线性时间计算距离变换的通用算法”，A. Meijster、JBTM Roerdink 和 WH Hesselink。 http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf
在我的开源效果库中使用了 Meijster 算法： https ://github.com/vinniefalco/LayerEffects
我希望这可以帮助别人。
根据Felzenszwald & Huttenlocher 的论文，这里是一维欧几里得距离变换的 C# 代码：
private static void DistanceTransform(double[] dataInput, ref double[] dataOutput)
{
int n = dataInput.Length;
int k = 0;
int[] v = new int[n];
double[] z = new double[n + 1];
v[0] = 0;
z[0] = Double.NegativeInfinity;
z[1] = Double.PositiveInfinity;
double s;
for (int q = 1; q < n; q++)
{
while (true)
{
s = (((dataInput[q] + q * q) - (dataInput[v[k]] + v[k] * v[k])) / (2.0 * q - 2.0 * v[k]));
if (s <= z[k])
{
k--;
}
else
{
break;
}
}
k++;
v[k] = q;
z[k] = s;
z[k + 1] = Double.PositiveInfinity;
}
k = 0;
for (int q = 0; q < n; q++)
{
while (z[k + 1] < q)
{
k++;
}
dataOutput[q] = ((q - v[k]) * (q - v[k]) + dataInput[v[k]]);
}
}
这可以很容易地用于二进制和灰度图像，方法是首先将其应用于图像列然后是行（反之亦然，当然）。
转换确实非常快。
以下是源图像和输出图像：
黑色像素的值为 0，白色像素的值较大（必须大于图像中可能的最大平方距离，但不是无穷大），以便变换返回与黑色像素的距离，而忽略白色像素。
要获得真正的欧几里德距离变换，只需从输出图像中取每个像素的平方根。