algorithm - 距离图的高效计算

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 倍的加速。

考虑最坏的情况

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