高效計算距離圖

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倍的速度提升。

考慮最壞的情況下

你最壞的情況是，在一個角落裏一個黑點的白色圖像。 在這種情況下，我的改進將不會爲您購買任何東西。