基本行列 (コンピュータビジョン)

基本行列（きほんぎょうれつ、英 : essential matrix） $\mathbf {E}$ はコンピュータビジョンの分野で用いられる $3\times 3$ 行列であり、カメラがピンホールカメラモデルを満たすことを仮定したステレオ画像ペア間の対応する2点の関係を表す。

概要

より具体的には、 $\mathbf {y}$ と $\mathbf {y} '$ をそれぞれ画像1と2の同次正規化画像座標とし、 $\mathbf {y}$ と $\mathbf {y} '$ がシーン内の同じ3次元点に対応する場合、以下の式が成り立つ。

(\mathbf {y} ')^{\top }\,\mathbf {E} \,\mathbf {y} =0

基本行列を定義する上記の関係は、1981年にH.クリストファー・ロンゲ・ヒギンズによって発表され、この概念がコンピュータービジョンコミュニティに紹介された。リチャード・ハートレーとアンドリュー・ジサーマンの著書では、類似の行列がもっと以前から写真測量法に登場していたと報告されている。ロンゲ・ヒギンズの論文には、対応する正規化画像座標の組から $\mathbf {E}$ 推定するためのアルゴリズムと、 $\mathbf {E}$ が既知である場合に2台のカメラの相対的な位置と向きを決定するためのアルゴリズムが含まれている。そして最終的に、基本行列を用いて画像上の点の3次元座標を決定する方法を示している。

利用

基本行列は、基礎行列 $\mathbf {F}$ の前身とみなせる。いずれの行列も画像上の点ペア間の制約を確立できるが、基本行列は正規化を行うためにカメラの内部パラメータ（行列 $\mathbf {K}$ と $\mathbf {K} '$ ）を知る必要があるため、キャリブレーションされたカメラ間の関係にのみ使用できる。カメラがキャリブレーション済みである場合には、基本行列はカメラ間の相対的な位置と方向、および対応する画像上の点の3次元位置の両方を決定するために利用できる。基本行列は、基礎行列と次の関係がある。

\mathbf {E} =({\mathbf {K} '})^{\top }\;\mathbf {F} \;\mathbf {K} .

導出と定義

ここではロンゲ・ヒギンズによる論文に従って導出を行う。

正規化済みの2つのカメラが、それぞれの画像平面に3次元世界を投影しているとする。点Pの3次元座標を各カメラの座標系に対して $(x_{1},x_{2},x_{3})$ と $(x'_{1},x'_{2},x'_{3})$ とする。カメラは正規化済みであるからピンホールカメラモデルが適用でき、対応する画像座標は

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

と

{\begin{pmatrix}y'_{1}\\y'_{2}\end{pmatrix}}={\frac {1}{x'_{3}}}{\begin{pmatrix}x'_{1}\\x'_{2}\end{pmatrix}}

と表せる。

2つの画像座標の同次表現は、次の式で与えられる。

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

と

{\begin{pmatrix}y'_{1}\\y'_{2}\\1\end{pmatrix}}={\frac {1}{x'_{3}}}{\begin{pmatrix}x'_{1}\\x'_{2}\\x'_{3}\end{pmatrix}}

これは、

\mathbf {y} ={\frac {1}{x_{3}}}\,{\tilde {\mathbf {x} }}

と

\mathbf {y} '={\frac {1}{x'_{3}}}\,{\tilde {\mathbf {x} }}'

のようにコンパクトに書くこともできる。ここで $\mathbf {y}$ と $\mathbf {y} '$ は、二次元画像座標の同次表現であり、 ${\tilde {\mathbf {x} }}$ と ${\tilde {\mathbf {x} }}'$ は適切な3次元座標だが、2つは異なる座標系である

正規化されたカメラのもう1つの結果は、各座標系を平行移動と回転によって関連付けられることである。これは、3次元座標の組が次のように式で関係付けられることを意味する。

{\tilde {\mathbf {x} }}'=\mathbf {R} \,({\tilde {\mathbf {x} }}-\mathbf {t} )

ここで $\mathbf {R}$ は $3\times 3$ 回転行列、 $\mathbf {t}$ は3次元平行移動ベクトルである。

基本行列は次のように定義される。

\mathbf {E} =\mathbf {R} \,[\mathbf {t} ]_{\times }

ここで $[\mathbf {t} ]_{\times }$ は $\mathbf {t}$ の外積の行列表現である。注: ここで、変換 $[\mathbf {R} ^{T}|\mathbf {t} ]$ は2番目のビューの点を1番目のビューに変換する。

$\mathbf {E}$ の定義では、正規化された画像座標の方向のみに関心がある^[1]（参照 : 三重積）。そのため画像座標を基本方程式（英 : essential equation）に代入する際、平行移動成分は必要がない。この $\mathbf {E}$ の定義が対応する2つの画像座標間の制約を表すことを確認するには、次のように $\mathbf {E}$ の左右から2つの異なる座標系の点Pの3次元座標かければ良い。

{\tilde {\mathbf {x} }}'^{T}\,\mathbf {E} \,{\tilde {\mathbf {x} }}\,{\stackrel {(1)}{=}}\,{\tilde {\mathbf {x} }}^{T}\,\mathbf {R} ^{T}\,\mathbf {R} \,[\mathbf {t} ]_{\times }\,{\tilde {\mathbf {x} }}\,{\stackrel {(2)}{=}}\,{\tilde {\mathbf {x} }}^{T}\,[\mathbf {t} ]_{\times }\,{\tilde {\mathbf {x} }}\,{\stackrel {(3)}{=}}\,0

上で述べた ${\tilde {\mathbf {x} }}'$ と ${\tilde {\mathbf {x} }}$ 間の関係と、 $\mathbf {R}$ と $\mathbf {t}$ を用いた $\mathbf {E}$ の定義を代入。
$\mathbf {R}$ は回転行列であるから、 $\mathbf {R} ^{T}\,\mathbf {R} =\mathbf {I}$ 。
外積の行列表現の性質。

最後に、いずれのカメラからも見えていることから $x_{3}$ , $x'_{3}$ > 0 であると想定できる。これは次の式を与える。

0=({\tilde {\mathbf {x} }}')^{T}\,\mathbf {E} \,{\tilde {\mathbf {x} }}={\frac {1}{x'_{3}}}({\tilde {\mathbf {x} }}')^{T}\,\mathbf {E} \,{\frac {1}{x_{3}}}{\tilde {\mathbf {x} }}=(\mathbf {y} ')^{T}\,\mathbf {E} \,\mathbf {y}

これは、基本行列が対応する画像上の点間で定義する制約である。

性質

すべての $3\times 3$ 行列が、何かしらのステレオカメラにとっての基本行列になるわけではない。（基本行列は1つの回転行列と1つの交代行列（いずれも $3\times 3$ 行列）の行列積として定義されていることに注意。）。交代行列は等しい2つの特異値と0であるもう1つの特異値を持つ。回転行列の乗算は特異値を変えない。これは、基本行列もまた等しい2つの特異値と0であるもう1つの特異値をもつことを意味する。この性質は、しばしば基本行列の内部制約（英 : internal constraints）と呼ばれる。

基本行列 $\mathbf {E}$ にゼロ以外のスカラーを掛けても、その結果は $\mathbf {E}$ と全く同じ制約を与える基本行列となる。これは $\mathbf {E}$ を射影空間の元とみなせることを意味する。すなわち、一方が他方のゼロ以外のスカラー倍である場合、2つの行列は等価とみなされる。これは、例えば $\mathbf {E}$ が画像データから推定される場合の適切な考え方である。一方、 $\mathbf {E}$ を次のように定義することも考えられる。

\mathbf {E} =[\mathbf {\widetilde {t}} ]_{\times }\,\mathbf {R}

ここで、 $\mathbf {\widetilde {t}} =-\mathbf {R} \mathbf {t}$ であり、このとき $\mathbf {E}$ はwell-definedな「スケーリング」を持つ。どちらの考え方がより適切かは、その利用場面によって異なる。

制約は、次のようにも表せる。

\det \mathbf {E} =0

また、

2\mathbf {E} \mathbf {E} ^{T}\mathbf {E} -\operatorname {tr} (\mathbf {E} \mathbf {E} ^{T})\mathbf {E} =0.

ここで、最後の式は行列制約で、各行列要素に1つずつ、9つの制約とみなせる。これらの制約は、5組の対応する点のペアから基本行列を決定するためによく用いられる。

基本行列には、射影要素として表示されるかどうかに応じて、5つまたは6つの自由度がある。回転行列 $\mathbf {R}$ と平行移動ベクトル $\mathbf {t}$ にはそれぞれ 3 つの自由度があり、合計で6つである。一方で基本行列を射影要素とみなす場合は、スカラー倍に関連する1つの自由度を差し引く必要があり、計5つの自由度となる。

推定

対応する画像上の点のセットが与えられると、セット内のすべての点について定義されるエピポーラ制約を満たす基本行列を推定できる。ただし、（実際の状況ではよくあることだが）画像点がノイズの影響を受ける場合、すべての制約を正確に満たす基本行列を見つけることはできない。

各制約に関連する誤差がどのように測定されるかに応じて、対応する画像上の点の特定のセットの制約を最適に満たす基本行列を決定または推定できる。最も簡単なアプローチは、一般に8点アルゴリズムとして知られる最小二乗問題を設定することである。

回転と平行移動の抽出

上記の推定方法などによりステレオカメラペアの基本行列が分かっている場合、この情報を用いて2つのカメラ座標系間の回転行列 $\mathbf {R}$ と平行移動 $\mathbf {t}$ (スケーリングを含む)も決定できる。これらの導出において $\mathbf {E}$ はwell-definedに決定されたスケーリングを持つというよりは射影要素であるとみなされる。

1つの解を見つける

$\mathbf {R}$ と $\mathbf {t}$ を決定する次の方法は、 $\mathbf {E}$ の特異値分解に基づく（ハートレーとジサーマンの本を参照）。 ^[2]特異値分解を用いずに $\mathbf {R}$ と $\mathbf {t}$ を決定することもできる（ロンゲ・ヒギンズの論文等）。

$\mathbf {E}$ に対して特異値分解を実行すると次が得られる。

\mathbf {E} =\mathbf {U} \,\mathbf {\Sigma } \,\mathbf {V} ^{T}

ここで $\mathbf {U}$ と $\mathbf {V}$ は $3\times 3$ の直行行列で、 $\mathbf {\Sigma }$ は次のような $3\times 3$ の対角行列である。

\mathbf {\Sigma } ={\begin{pmatrix}s&0&0\\0&s&0\\0&0&0\end{pmatrix}}

$\mathbf {\Sigma }$ の対角要素は $\mathbf {E}$ の特異値であり、基本行列の内部制約に従い等しい2つの値と1つのゼロ値で構成される必要がある。また、次を定義する。

\mathbf {W} ={\begin{pmatrix}0&-1&0\\1&0&0\\0&0&1\end{pmatrix}}

と

\mathbf {W} ^{-1}=\mathbf {W} ^{T}={\begin{pmatrix}0&1&0\\-1&0&0\\0&0&1\end{pmatrix}}

そして、次のアンザッツを設定する。

[\mathbf {t} ]_{\times }=\mathbf {U} \,\mathbf {W} \,\mathbf {\Sigma } \,\mathbf {U} ^{T}

\mathbf {R} =\mathbf {U} \,\mathbf {W} ^{-1}\,\mathbf {V} ^{T}

実際のカメラ画像などのデータを扱う場合、 $\mathbf {\Sigma }$ は制約を完全には満たさない可能性があるため、代わりに次を用いると役立つ場合がある。

[\mathbf {t} ]_{\times }=\mathbf {U} \,\mathbf {Z} \,\mathbf {U} ^{T}

と

\mathbf {Z} ={\begin{pmatrix}0&1&0\\-1&0&0\\0&0&0\end{pmatrix}}

証明

第一に、 $\mathbf {R}$ と $[\mathbf {t} ]_{\times }$ を表現している式は、以下より、基本行列の定義式を満たす。

[\mathbf {t} ]_{\times }\,\mathbf {R} =\mathbf {U} \,\mathbf {W} \,\mathbf {\Sigma } \,\mathbf {U} ^{T}\mathbf {U} \,\mathbf {W} ^{-1}\,\mathbf {V} ^{T}\,=\mathbf {U} \,\mathbf {\Sigma } \,\mathbf {V} ^{T}=\mathbf {E}

第二に、この $[\mathbf {t} ]_{\times }$ がある $\mathbf {t}$ の外積の行列表現であることを示さなければならない。まず、

\mathbf {W} \,\mathbf {\Sigma } ={\begin{pmatrix}0&-s&0\\s&0&0\\0&0&0\end{pmatrix}}

であるから、 $\mathbf {W} \,\mathbf {\Sigma }$ は交代行列、すなわち $(\mathbf {W} \,\mathbf {\Sigma } )^{T}=-\mathbf {W} \,\mathbf {\Sigma }$ である。これは次のように $[\mathbf {t} ]_{\times }$ についても同様に当てはまる。

([\mathbf {t} ]_{\times })^{T}=\mathbf {U} \,(\mathbf {W} \,\mathbf {\Sigma } )^{T}\,\mathbf {U} ^{T}=-\mathbf {U} \,\mathbf {W} \,\mathbf {\Sigma } \,\mathbf {U} ^{T}=-[\mathbf {t} ]_{\times }

外積の行列表現の一般的な性質によれば、 $[\mathbf {t} ]_{\times }$ はただ1つのベクトル $\mathbf {t}$ の外積演算子でなければならない。

第三に、 $\mathbf {R}$ が回転行列であることも示す必要がある。 $\mathbf {R}$ は3つの直交行列の積である。従って $\mathbf {R}$ もまた直交し、 $\det(\mathbf {R} )=\pm 1$ である。回転行列であるためには、 $\det(\mathbf {R} )=1$ でなければならないが、ここでは $\mathbf {E}$ は射影要素とみなされているため、必要であれば $\mathbf {E}$ の符号を反転することで実現できる。

すべての解を見つける

ここまでで、 $\mathbf {E}$ が与えられた場合に $\mathbf {R}$ と $\mathbf {t}$ の1つの可能な解を求める手段が確立されている。しかし、これは唯一の可能な解ではなく、実用の観点からは有効な解でない可能性さえある。まず、 $\mathbf {E}$ のスケーリングが定義されていないため、 $\mathbf {t}$ のスケーリングも定義されていない。次の式が成り立つため、これは $\mathbf {E}$ の零空間にある必要がある。

\mathbf {E} \,\mathbf {t} =\mathbf {R} \,[\mathbf {t} ]_{\times }\,\mathbf {t} =\mathbf {0}

しかしこの後の解の分析のためには $\mathbf {t}$ の厳密なスケーリングは、その「符号」、つまりどの方向を指しているかほど重要ではない。 ${\hat {\mathbf {t} }}$ を $\mathbf {E}$ の零空間で正規化されたベクトルとする。このとき ${\hat {\mathbf {t} }}$ と $-{\hat {\mathbf {t} }}$ の両方が $\mathbf {E}$ に対して有効な平行移動ベクトルになる。上で述べた $\mathbf {R}$ と $\mathbf {t}$ の導出では、 $\mathbf {W}$ を $\mathbf {W} ^{-1}$ に変更することもできる。この変更は、平行移動ベクトルに対しては符号の変更のみを起こす。これについては可能性として既に説明した。一方で回転に対しては、少なくとも一般的なケースでは、これは異なる変換を生成する。

要約すると、与えられた $\mathbf {E}$ には、 $\mathbf {t}$ に対して可能な2つの正反対な方向があり、この基本行列に準じた2つの異なる回転がある。これにより、2つのカメラ座標系間の回転と平行移動に対して計4つの解のクラスが得られる。その上、選択された平行移動方向の未知のスケーリング $s>0$ も存在する。

ただし、4つの解のクラスのうち、実際に実現できるのは1つだけである。対応する画像座標のペアが与えられたとき、3つの解のクラスは常に2つのカメラのうち少なくとも1つの後方に3次元点を生成してしまいカメラから見ることができない。4つのクラスのうちの1つだけが、常に両方のカメラの前方に3次元点を生成する。これが正しい解であるはずである。ただしそれでも、平行移動成分に関する未定の正のスケーリングがある。

上記の $\mathbf {R}$ と $\mathbf {t}$ の決定は $\mathbf {E}$ が基本行列の内部制約を満たすことを前提としている。これが当てはまらない場合、典型的には例えば $\mathbf {E}$ が実際の（ノイズの多い）画像データから推定されている場合には、内部制約をほぼ満たしていると想定する必要がある。ベクトル ${\hat {\mathbf {t} }}$ は、最小の特異値に対応する $\mathbf {E}$ の右特異ベクトルとして選択される。

対応する画像上の点からの3次元点

対応する正規化された画像座標 $(y_{1},y_{2})$ と $(y'_{1},y'_{2})$ が与えられた場合、基本行列が既知であり対応する回転および平行移動が決定されていれば、 $(x_{1},x_{2},x_{3})$ を計算する多くの方法が存在する。

ツール

MATLABでの基本行列推定(Manolis Lourakis)。

外部リンク

RI Hartley による基本行列の研究

参考文献

^ Photogrammetric Computer Vision: Statistics, Geometry, Orientation and Reconstruction (1st ed.)
^ Hartley, Richard; Andrew Zisserman (2004). Multiple view geometry in computer vision (2nd ed.). Cambridge, UK. ISBN 978-0-511-18711-7. OCLC 171123855

David Nistér (June 2004). “An efficient solution to the five-point relative pose problem”. IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (6): 756–777. doi:10.1109/TPAMI.2004.17. PMID 18579936.
H. Stewénius and C. Engels and D. Nistér (June 2006). “Recent Developments on Direct Relative Orientation”. ISPRS Journal of Photogrammetry and Remote Sensing 60 (4): 284–294. Bibcode: 2006JPRS...60..284S. doi:10.1016/j.isprsjprs.2006.03.005.
H. Christopher Longuet-Higgins (September 1981). “A computer algorithm for reconstructing a scene from two projections”. Nature 293 (5828): 133–135. Bibcode: 1981Natur.293..133L. doi:10.1038/293133a0.
Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. ISBN 978-0-521-54051-3
Yi Ma; Stefano Soatto; Jana Košecká; S. Shankar Sastry (2004). An Invitation to 3-D Vision. Springer. ISBN 978-0-387-00893-6
Gang Xu and Zhengyou Zhang (1996). Epipolar geometry in Stereo, Motion and Object Recognition. Kluwer Academic Publishers. ISBN 978-0-7923-4199-4
Förstner, Wolfgang and Wrobel, Bernhard P. (2016). Photogrammetric Computer Vision: Statistics, Geometry, Orientation and Reconstruction (1st ed.). Springer Publishing Company, Incorporated. ISBN 3319115499

[1] Photogrammetric Computer Vision: Statistics, Geometry, Orientation and Reconstruction (1st ed.)

[2] Hartley, Richard; Andrew Zisserman (2004). Multiple view geometry in computer vision (2nd ed.). Cambridge, UK. ISBN 978-0-511-18711-7. OCLC 171123855

[1]

[2]