距離マップの効率的な計算

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ループ：2つの外側ループスキャンポイントと2つの内側ループが最も近いポイントを見つけます。

劇的にスピードアップインナーループ

あなたはすべての点で見て列によって画像の行をスキャンします。中

あなたのポイントはXで、あなたのスキャンポイント：あなたが知っているよう

あなたが代わりに遠いが、すぐに停止に近いから螺旋状にポイントをスキャンする必要がありますあなたが探しているものを見つけます描かれている1,2,3 ...の順番です。 （20にあるピクセルを見つけることは、停止することを意味するわけではありません。22に近いものを見つけることができます）。

（ギンプで作成した - 私が代わりに何を使うべき？！）まで

余分なスピードのため

使用古い結果は、各処理済みポイントが見つかり最も近い点を続ける場合は、追加を達成することができます次の各点について画像の一部を走査するだけで高速化することができる。

あなたは一般的に、あなたは4倍の高速化を期待することができ、あなたが見る必要がある場所を慎重に検討する必要がありますが、します。

最悪の場合

あなたの最悪の場合を考えてみては隅に単一の黒ドットと白のイメージです。 私の改善はあなたにこの場合は何も買わないでしょう。