高效计算距离图

Question

我有一个2维图像充满黑色和白色像素。现在我想知道每个白色像素（距离）最近的黑色像素，以及我想知道的每个黑色像素（距离）最近的白色像素。

一个天真的算法是：

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

术语：您有 for环路：两个外环路扫描点和两个内环路寻找最近点。

大大加快行动的内环

您在扫描逐行图像行寻找每一个点。

而应该以螺旋从最近到最远尽快停止扫描的点，你知道你发现你在找什么：在

你的观点是X，你扫描点订单1,2,3 ...如图所示。 （请注意，在20找到像素并不意味着您可以停止 - 您可以在22找到更接近的像素）。

（用瘸子创建的 - 我应该怎么用，而不是？！）

使用旧效果为额外加快

如果你把找到的每个已处理点的最近点，就可以实现一个附加通过仅为每个下一个点扫描图像的一部分来加速。

你将需要仔细考虑，你需要寻找，但是，通常，你可以期望一个4倍的速度提升。

考虑最坏的情况下

你最坏的情况是，在一个角落里一个黑点的白色图像。 在这种情况下，我的改进将不会为您购买任何东西。