三角測量（コンピュータービジョン）

コンピュータビジョンにおいて、三角測量とは、2 枚以上の画像への投影に基づいて 3D 空間内の点を決定するプロセスを指します。この問題を解決するには、関係するカメラの 3D から 2D へのカメラ投影関数のパラメータを知る必要があります。最も単純なケースでは、カメラ マトリックスによって表されます。三角測量は、再構成または交差とも呼ばれることがあります。

三角測量の問題は、原理的には簡単です。画像内の各点は 3D 空間の線に対応するため、3D の線上のすべての点は画像内の点に投影されます。2 枚以上の画像で対応する点のペアが見つかった場合、それらは共通の 3D 点xの投影である必要があります。画像点によって生成される線のセットは、x (3D 点) で交差する必要があり、 x (3D 点) の座標の代数式は、以下に示すようにさまざまな方法で計算できます。

しかし、実際には、画像点の座標を任意の精度で測定することはできません。代わりに、レンズの歪みによる幾何学的ノイズや関心点の検出エラーなど、さまざまな種類のノイズが、測定された画像座標の不正確さにつながります。その結果、対応する画像点によって生成された線は、3D 空間で常に交差するわけではありません。問題は、測定された画像点に最適に適合する 3D ポイントを見つけることです。文献には、最適性を定義する方法と最適な 3D ポイントを見つける方法について複数の提案があります。それらは異なる最適性の基準に基づいているため、ノイズが関係する場合、 さまざまな方法で 3D ポイントxの異なる推定値が生成されます。

以下では、ピンホールカメラによって生成された2つのビューから対応する画像点に対して三角測量が行われると仮定します。

左の画像は、ピンホール モデルの一対のステレオ カメラのエピポーラ幾何学を示しています。3D 空間の点x (3D 点) は、カメラの焦点 、および を通る線 (緑) に沿ってそれぞれの画像平面に投影され、2 つの対応する画像点 および が生成されます。およびが与えられ、2 台のカメラの幾何学が分かっている場合、2 つの投影線 (緑の線) を決定することができ、それらは点x (3D 点)で交差する必要があります。基本的な線形代数を使用すると、その交差点は簡単な方法で決定できます。 ${\displaystyle \mathbf {O} _{1}}$${\displaystyle \mathbf {O} _{2}}$${\displaystyle \mathbf {y} _{1}}$${\displaystyle \mathbf {y} _{2}}$${\displaystyle \mathbf {y} _{1}}$${\displaystyle \mathbf {y} _{2}}$

右の画像は実際のケースを示しています。画像の位置はポイントであり、正確に測定することはできません。その理由は、次のような要因の組み合わせです。 ${\displaystyle \mathbf {y} _{1}}$${\displaystyle \mathbf {y} _{2}}$

• 幾何学的歪み、たとえばレンズ歪みは、カメラの 3D から 2D へのマッピングがピンホール カメラ モデルから外れていることを意味します。これらのエラーはある程度補正できますが、幾何学的エラーが残ります。
• x (3D ポイント)からの単一の光線は、点像分布関数に従ってカメラのレンズ システム内で分散されます。画像内の分散強度関数の測定から対応する画像ポイントを復元すると、エラーが発生します。
• デジタル カメラでは、画像の強度関数は個別のセンサー要素でのみ測定されます。実際の強度関数を復元するには、個別の強度関数の不正確な補間を使用する必要があります。
• 三角測量に使用される画像ポイントy ₁ ^'およびy ₂ 'は、コーナーや一般的な関心ポイントなど、さまざまなタイプの特徴抽出器を使用して検出されることがよくあります。近傍操作に基づくあらゆる種類の特徴抽出には、固有の位置特定エラーがあります。

その結果、測定された画像点は、およびではなく、およびになります。ただし、それらの投影線（青）は、3D 空間で交差したり、 xに近づいたりする必要はありません。実際、これらの線が交差するのは、およびが基本行列によって定義されたエピポーラ制約を満たす場合のみです。および の測定ノイズを考えると、エピポーラ制約が満たされず、投影線が交差しない可能性が高くなります。 ${\displaystyle \mathbf {y} '_{1}}$${\displaystyle \mathbf {y} '_{2}}$${\displaystyle \mathbf {y} _{1}}$${\displaystyle \mathbf {y} _{2}}$${\displaystyle \mathbf {y} '_{1}}$${\displaystyle \mathbf {y} '_{2}}$${\displaystyle \mathbf {y} '_{1}}$${\displaystyle \mathbf {y} '_{2}}$

この観察は、三角測量で解決される問題につながります。カメラのジオメトリと与えられたxの最適な推定値はどの 3D ポイント x est でしょうか?_答えは、多くの場合、 x _estに依存する誤差尺度を定義し、この誤差を最小化することで見つかります。次のセクションでは、文献で紹介されている x _estを計算するさまざまな方法について簡単に説明します。${\displaystyle \mathbf {y} '_{1}}$${\displaystyle \mathbf {y} '_{2}}$

すべての三角測量法は、かつの場合、つまりエピポーラ制約が満たされる場合（特異点を除く、下記参照）、 x _est = xを生成します。制約が満たされない場合に何が起こるかは、方法によって異なります。 ${\displaystyle \mathbf {y} _{1}=\mathbf {y} '_{1}}$${\displaystyle \mathbf {y} _{2}=\mathbf {y} '_{2}}$

三角測量法は次のような 関数で記述できる。${\displaystyle \tau \,}$

${\displaystyle \mathbf {x} \sim \tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})}$

ここで、 は検出された画像ポイントの同次座標であり、はカメラ行列です。 x (3D ポイント) は、結果として得られる 3D ポイントの同次表現です。の符号は、同次ベクトルが関係するため、非ゼロのスカラーによる乗算まで xに等しいベクトルを生成するためにのみ必要であることを意味します。${\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2}}$${\displaystyle \mathbf {C} _{1},\mathbf {C} _{2}}$${\displaystyle \sim \,}$${\displaystyle \tau \,}$

特定の方法、つまり特定の機能を見る前に、その方法に関連する一般的な概念について説明する必要があります。特定の問題に対してどの三角測量法を選択するかは、ある程度これらの特性に依存します。 ${\displaystyle \tau \,}$

いくつかの方法では、 x (3D 点) が 3D 空間の特定のサブセット ( の組み合わせに対応) 内にある場合、 x の推定値を正しく計算できません。このサブセット内の点は、三角測量法の特異点になります。失敗の理由は、解くべき方程式系の一部が不完全決定であるか、 x _estの射影表現が特異点のゼロ ベクトルになることです。 ${\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2}}$

アプリケーションによっては、三角測量が 3D ポイントを表すのに使用される座標系から独立していることが望ましい場合があります。つまり、三角測量の問題をある座標系で定式化し、別の座標系に変換すると、結果として得られる推定値x _{est も}同じように変換される必要があります。この特性は一般に不変性と呼ばれます。すべての三角測量法が不変性を保証するわけではありません。少なくとも一般的なタイプの座標変換では不変性は保証されません。

3D座標の同次表現の場合、最も一般的な変換は射影変換であり、行列で表される。同次座標が次のように変換されると、 ${\displaystyle 4\times 4}$${\displaystyle \mathbf {T} }$

${\displaystyle \mathbf {\bar {x}} \sim \mathbf {T} \,\mathbf {x} }$

カメラ行列は( C _k ) のように変換する必要がある。

${\displaystyle \mathbf {\bar {C}} _​​{k}\sim \mathbf {C} _{k}\,\mathbf {T} ^{-1}}$

同じ同次画像座標（y _k） を生成する

${\displaystyle \mathbf {y} _{k}\sim \mathbf {\bar {C}} _​​{k}\,\mathbf {\bar {x}} =\mathbf {C} _{k}\, \mathbf {x} }$

三角関数が不変であれば、次の関係が成立するはずである。 ${\displaystyle \tau}$${\displaystyle \mathbf {T} }$

${\displaystyle \mathbf {\bar {x}} _{\rm {est}}\sim \mathbf {T} \,\mathbf {x} _{\rm {est}}}$

そこから

${\displaystyle \tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})\sim \mathbf {T} ^{-1}\,\tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1}\,\mathbf {T} ^{-1},\mathbf {C} _{2}\,\mathbf {T} ^{-1}),}$   全ての${\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2}}$

各三角測量法について、この最後の関係が有効かどうかを判断できます。有効である場合、この関係は、たとえば剛体変換やアフィン変換などの射影変換のサブセットに対してのみ満たされる可能性があります。

関数は、実際には比較的複雑になる可能性がある計算の抽象的な表現にすぎません。方法によっては、閉じた形式の連続関数である が得られますが、他の方法では、たとえばSVDや多項式の根を求めるなどの一連の計算ステップに分解する必要があります。また、別の種類の方法では、いくつかのパラメータの反復推定に依存する が得られます。つまり、計算時間と関連する操作の複雑さは、方法によって異なる可能性があります。 ${\displaystyle \tau}$${\displaystyle \tau}$${\displaystyle \tau}$

2つの画像点とにはそれぞれ対応する投影線（上の右の画像では青）があり、ここではおよびで示され、カメラ行列 が与えられれば決定できます。を（3D線） Lとx（3D点） の間の距離関数とし、を と の間のユークリッド距離とします。中点法では、を最小化する 点x _{estを見つけます。}${\displaystyle \mathbf {y} '_{1}}$${\displaystyle \mathbf {y} '_{2}}$${\displaystyle \mathbf {L} '_{1}}$${\displaystyle \mathbf {L} '_{2}}$${\displaystyle \mathbf {C} _{1},\mathbf {C} _{2}}$${\displaystyle d\,}$${\displaystyle d(\mathbf {L} ,\mathbf {x} )}$${\displaystyle \mathbf {L} }$${\displaystyle \mathbf {x} }$

${\displaystyle d(\mathbf {L} '_{1},\mathbf {x} )^{2}+d(\mathbf {L} '_{2},\mathbf {x} )^{2} }$

x _{est は}、2 つの投影線を結ぶ最短の線分のちょうど中央に位置すること がわかります。

ここで解決すべき問題は、与えられた対応する正規化された画像座標とを計算する方法です。必須行列がわかっていて、対応する回転変換と平行移動変換が決定されている場合、このアルゴリズム（Longuet-Higgins の論文で説明）が解決策を提供します。 ${\displaystyle (x_{1},x_{2},x_{3})}$${\displaystyle (y_{1},y_{2})}$${\displaystyle (y'_{1},y'_{2})}$

回転行列のk行目を次のように表すとします。 ${\displaystyle \mathbf {r} _{k}}$${\displaystyle \mathbf {R} }$

${\displaystyle \mathbf {R} ={\begin{pmatrix}-\mathbf {r} _{1}-\\-\mathbf {r} _{2}-\\-\mathbf {r} _{3}-\end{pmatrix}}}$

2つの座標系における3D座標間の上記の関係と、先に説明した3D点と2D点間のマッピングを組み合わせると、次のようになります。

${\displaystyle y'_{1}={\frac {x'_{1}}{x'_{3}}}={\frac {\mathbf {r} _{1}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}{\mathbf {r} _{3}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}}={\frac {\mathbf {r} _{1}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}{\mathbf {r} _{3}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}}$

または

${\displaystyle x_{3}={\frac {(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {y} }}}$

が決定したら、他の2つの座標は次のように計算できる。 ${\displaystyle x_{3}}$

${\displaystyle {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=x_{3}{\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}}$

上記の導出は一意ではない。 の式から始めて、 の式を次のよう に導出することもできる。${\displaystyle y'_{2}}$${\displaystyle x_{3}}$

${\displaystyle x_{3}={\frac {(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {y} }}}$

理想的なケースでは、カメラが完全なピンホールカメラに従って 3D ポイントをマッピングし、結果として得られる 2D ポイントがノイズなしで検出できる場合、 の 2 つの式は等しくなります。ただし、実際には等しくないため、たとえば何らかの平均に関して の 2 つの推定値を組み合わせると有利になる場合があります。 ${\displaystyle x_{3}}$${\displaystyle x_{3}}$

上記の計算には、他のタイプの拡張も可能です。プライム付き画像座標の式から始めて、プライムなしシステムで 3D 座標を導き出しました。プライムなし画像座標から始めてプライム付き 3D 座標を取得し、最終的にプライムなし 3D 座標に変換することも可能です。この場合も、理想的なケースでは結果は上記の式と同じになるはずですが、実際には異なる可能性があります。

最後に、基本的なマトリックスが対応する画像座標から決定される場合（3D ポイントがこのように決定される場合が多い）には、変換ベクトルは未知の正のスケーリングまでしか分からないという事実について述べます。その結果、再構成された 3D ポイントも正のスケーリングに関しては未決定となります。 ${\displaystyle \mathbf {t} }$

• 複数の画像からの3D再構築
• バンドル調整
• 線と線の交差

• リチャード・ハートリー、アンドリュー・ジッサーマン (2003)。『コンピュータビジョンにおけるマルチビュージオメトリ』ケンブリッジ大学出版局。ISBN 978-0-521-54051-3。

• Matlab での 2 ビューおよびマルチビューの三角測量