(レーザー スキャナーからの) 3D ハイトマップが与えられた場合、どうすればサドル ポイントを見つけることができますか?
つまり、次のようなものが与えられます。
曲率が一方向で正で、他の方向で負であるすべてのポイントを探しています。
(これらの方向は、X 軸と Y 軸に揃える必要はありません。X 方向の曲率が Y 方向の曲率と反対の符号を持っているかどうかを確認する方法は知っていますが、すべてのケースを網羅しているわけではありません。さらに悪いことに、 、X の解像度は Y の解像度とは異なります)
理想的には、ある程度のノイズを許容し、「重要な」サドル ポイントのみをマークできるアルゴリズムを探しています。
私は計算トポロジー クラスの同様の問題を調査しており、以下に概説する方法である程度の成功を収めています。
まず、2 つの入力ポイントで高さを評価し、任意の入力に対して < または > (等しくない) を返す比較関数が必要です。これを行う 1 つの方法は、ポイントが同じ高さである場合、位置ベースまたはランダム インデックスを使用してより大きなポイントを見つけることです。これは、高さに極小の摂動を加えていると考えることができます。
ここで、各点について、周囲のすべての隣接点の高さを比較します (2D 長方形グリッドには 8 つの隣接点があります)。ポイントの下のリンクは、高さがポイントよりも小さいすべての隣接ポイントのセットになります。
隣接するすべての値が下のリンクにある場合は、極大値に達しています。下のリンクにポイントがない場合は、ローカル ミニマムにいます。それ以外の場合、下のリンクが 1 つの接続されたセットである場合は、斜面上の通常のポイントにいます。しかし、下のリンクが接続されていない 2 つのセットである場合は、サドルにいます。
2D では、チェックしているポイントの周りに循環順序で 8 つの隣接ポイントのリストを作成できます。比較関数に応じて、各近傍に +/-1 の値を割り当てます。次に、そのリストをステップ実行し (2 つの端点を比較することを忘れないでください)、符号が変化する回数を数えて、下のリンクの連結要素の数を決定します。
どのサドルが「重要」かを判断することは、より難しい分析です。ガイダンスについては、http : //www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Gyulassy08.pdf を参照してください。
-マイケル
(実体験というより数学での推測です)
最小二乗法などを使用して、各候補点の周りの小さなパッチで二次曲線を曲面に当てはめます。パッチの大きさはノイズを制御する 1 つの方法であり、候補ポイントからの距離に応じてポイントを重み付けすることでゲインを得ることができます。行列表記では、二次を x'Ax + b'x + c として表すことができます。ここで、A は対称です。
二次方程式は、x = (A^-1)b/2 で勾配がゼロになります。これがパッチ内にない場合は、破棄します。
A が +ve と -ve の両方の固有値を持つ場合、x に鞍点があります。A は 2x2 しかなく、最大で 2 つの固有値を持つため、固有値がゼロの場合は無視でき、前の段階で反転できませんでした。