canvas - 画像のポイントからエッジまでの最短距離

Question

これはおそらく他の場所で対処されていますが、何も見つかりません。精度よりも速度を重視して、画像上の任意の点と最も近い透明なピクセルの間の最短距離を見つけようとしています。

現在私が行っているのは、0.1ラジアンごとに1行の各ピクセルをチェックし、透明なピクセルに達したときに停止し、最短を追跡することです。ただし、これは特に高速でも正確でもありません。もっと良い方法はありますか？たぶん、人々がこの種のものに使用するアルゴリズム？

私はこれをjavascript/canvasで行っています。

Answer 1

1つのアプローチは、すべてのピクセルから最も近い透明ピクセルまでの距離を計算することです（距離変換）。これは、元の画像の2つのパスで実行できます。距離変換が計算されると、最も近い透明なピクセルが一定時間O（1）で見つかります。このアプローチは、透明な領域が時間の経過とともにゆっくりと変化する場合に優れています。

透明な領域が急速に変化している場合は、おそらくもっとうまくいくことができます。

Answer 2

最も高速で正確なアルゴリズムは、ポイントの周りを単純に円で囲むことです。隣接するすべてのピクセルをチェックしてから、次のレイヤーをチェックします。これは基本的に幅優先探索であり、O（n）時間で実行されます。ここで、nはピクセル数です。今あなたがしていることは、より速い確率論的アプローチです。

アルゴリズムをあなたのアルゴリズムよりも速くするために私が考えることができる唯一の方法は、円のサイズ、たとえば直径3ピクセルを選び、その円のピクセルの75％（最適なパーセンテージは精度に対する要望によって異なります）をチェックすることです。 。透明なピクセルが見つからない場合は、円のサイズを2倍にします。画像の外観によっては、これは非常に不正確な場合がありますが、精度よりも速度が優先されます。

そうでなければ、透明なピクセルがその周りのピクセルに基づいている場所に関するデータを収集できない限り、アルゴリズムの改善は実際には見られません。そうすれば、検索を少し賢くすることができます。そうでなければ、ピクセルをテストすることによって学ぶのは、唯一のピクセルが透明である（または透明でない）ということだけです。

xピクセルより大きい透明な領域のみを探していて、直径がxピクセルの領域を正確に見つけたい場合は、円のサイズを調整してx-1ずつ大きくし、精度を向上させることができます。最も近いピクセルが見つかるまで、原点に向かって透明なピクセルをたどることができます。