c++ - 一致する線分-堅牢で高速な方法

Question

単一の画像データから抽出された2D線分があり、他のソースから抽出された3D線分と一致させたいです。そのために、最初に、共直線性方程式を使用して3D線分を画像空間に投影したいと思います（私は外部標定パラメーターを知っています）。両方の線分が同じ座標系にあるので、その線に最も一致する線分を見つけたいと思います。

後で3D線分を更新するために、対応する線分と一致する高速で堅牢なアルゴリズムを探しています。

誰かがこれについて考えを持っているならば、いくつかの提案をしてください。前もって感謝します。

Answer 1

あなたは線分の交差点に似た問題を見ています。したがって、当然のことながら、そのソリューションもおそらく同様です。

簡単なアプローチは、各2Dセグメントを各3Dセグメントと比較することです。最適な一致は、実際と比較したときに予測された長さと位置に最も近いものです。実際は2Dセグメントです。これはO（AB）のようなもので、Aは2Dセグメントの数、Bは3Dセグメントの数です。

2Dセグ​​メントを辞書式順序で並べ替えることで、メソッドをいくらか高速化できます。次に、この質問で尋ねたのと同じ種類のアルゴリズムを使用して、x値が一方または両方の期待されるx値の特定の量内にあるすべての線分を取得します。線分終点*。最悪の場合でも、O（AB）に遭遇する可能性がありますが、平均時間はO（B log A）に近いはずです。しかし、あなたが言ったことに基づいてこの方法を使用できるかどうかは明確ではないので、この段落はより概要と見なされるべきです。

O（B log A）またはO（A log B）よりも高速であるため、これは十分に調査された問題である必要があります。

• 2Dエンドポイントを辞書式順序で並べ替えると、おそらく1つのエンドポイントで回避できます。