距离图的高效计算

Question

我有一张充满黑白像素的二维图像。现在，对于每个白色像素，我想知道（到）最近的黑色像素（距离），对于每个黑色像素，我想知道（到）最近的白色像素（距离）。

一个朴素的算法是：

for(var y = 0; y < height; y++)
{
    for(var x = 0; x < width; x++)
    {
        var min = float.MaxValue;
        var me = image[x,y];

        for(var sy = 0; sy < height; sy++)
        {
            for(var sx = 0; sx < width; sx++)
            {
                var target = image[sx,sx];

                if(target != me)
                {
                    // target is the opposite color
                    var distance = Distance(x, y, sx, sy);
                    if(distance < min)
                    {
                        min = distance;
                    }
                }       
            }
        }

        distanecImage[x,y] = min;
    }
}

我认为这是二次复杂度。有什么办法可以加快速度吗？我有一个想法，如果你知道所有邻居的最近目标像素，你就可以计算你自己的最近距离，而不必遍历整个图像。但是我在使用该想法生成算法或如何调用这样的算法时遇到了问题。

我仅限于 DirectX9 级别的硬件，但如果需要，我可以使用 GPU 来加快速度。它们的最大尺寸约为 256x256。

Answer 1

术语：你有4 for个循环：两个外循环扫描点和两个内循环寻找最近点。

显着加速内部循环

您正在逐行扫描图像，查看每个点。

您应该在知道找到要查找的内容后立即从最近的停止点到最远的停止点以螺旋方式扫描点：

您的点是 X，您按 1,2,3... 的顺序扫描点，如图所示。（请注意，在 20 处找到一个像素并不意味着您可以停下来 - 您可以在 22 处找到一个更近的像素）。

（使用 Gimp 创建 - 我应该改用什么？！）

使用旧结果进行额外加速

如果为每个已处理的点保留找到的最近点，则可以通过为每个下一个点仅扫描图像的一部分来实现额外的加速。

您需要仔细考虑您需要查找的位置，但通常情况下，您可以获得 4 倍的加速。

考虑最坏的情况

最糟糕的情况是白色图像的一角有一个黑点。在这种情况下，我的改进不会给你带来任何好处。

距离图的高效计算

Efficient computation of distance map

algorithm

2d

dynamic-programming

显着加速内部循环

使用旧结果进行额外加速

考虑最坏的情况