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

基本行列（きほんぎょうれつ、英 : essential matrix） E {\displaystyle \mathbf {E} } はコンピュータビジョンの分野で用いられる 3 × 3 {\displaystyle 3\times 3} 行列であり、カメラがピンホールカメラモデルを満たすことを仮定したステレオ画像ペア間の対応する2点の関係を表す。 より具体的には、 y {\displaystyle \mathbf {y} } と y ′ {\displaystyle \mathbf {y} '} をそれぞれ画像1と2の同次正規化画像座標とし、 y {\displaystyle \mathbf {y} } と y ′ {\displaystyle \mathbf {y} '} がシーン内の同じ3次元点に対応する場合、以下の式が成り立つ。 ( y ′ ) ⊤ E y = 0 {\displaystyle (\mathbf {y} ')^{\top }\,\mathbf {E} \,\mathbf {y} =0} 基本行列を定義する上記の関係は、1981年にH.クリストファー・ロンゲ・ヒギンズによって発表され、この概念がコンピュータービジョンコミュニティに紹介された。 リチャード・ハートレーとアンドリュー・ジサーマンの著書では、類似の行列がもっと以前から写真測量法に登場していたと報告されている。 ロンゲ・ヒギンズの論文には、対応する正規化画像座標の組から E {\displaystyle \mathbf {E} } 推定するためのアルゴリズムと、 E {\displaystyle \mathbf {E} } が既知である場合に2台のカメラの相対的な位置と向きを決定するためのアルゴリズムが含まれている。そして最終的に、基本行列を用いて画像上の点の3次元座標を決定する方法を示している。 基本行列は、基礎行列 F {\displaystyle \mathbf {F} } の前身とみなせる。いずれの行列も画像上の点ペア間の制約を確立できるが、基本行列は正規化を行うためにカメラの内部パラメータ（行列 K {\displaystyle \mathbf {K} } と K ′ {\displaystyle \mathbf {K} '} ）を知る必要があるため、キャリブレーションされたカメラ間の関係にのみ使用できる。カメラがキャリブレーション済みである場合には、基本行列はカメラ間の相対的な位置と方向、および対応する画像上の点の3次元位置の両方を決定するために利用できる。基本行列は、基礎行列と次の関係がある。 E = ( K ′ ) ⊤ F K . {\displaystyle \mathbf {E} =({\mathbf {K} '})^{\top }\;\mathbf {F} \;\mathbf {K} .} ここではロンゲ・ヒギンズによる論文に従って導出を行う。 正規化済みの2つのカメラが、それぞれの画像平面に3次元世界を投影しているとする。点Pの3次元座標を各カメラの座標系に対して ( x 1 , x 2 , x 3 ) {\displaystyle (x_{1},x_{2},x_{3})} と ( x 1 ′ , x 2 ′ , x 3 ′ ) {\displaystyle (x'_{1},x'_{2},x'_{3})} とする。カメラは正規化済みであるからピンホールカメラモデルが適用でき、対応する画像座標は ( y 1 y 2 ) = 1 x 3 ( x 1 x 2 ) {\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\frac {1}{x_{3}}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}  と  ( y 1 ′ y 2 ′ ) = 1 x 3 ′ ( x 1 ′ x 2 ′ ) {\displaystyle {\begin{pmatrix}y'_{1}\\y'_{2}\end{pmatrix}}={\frac {1}{x'_{3}}}{\begin{pmatrix}x'_{1}\\x'_{2}\end{pmatrix}}} と表せる。 2つの画像座標の同次表現は、次の式で与えられる。 ( y 1 y 2 1 ) = 1 x 3 ( x 1 x 2 x 3 ) {\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}={\frac {1}{x_{3}}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}}  と  ( y 1 ′ y 2 ′ 1 ) = 1 x 3 ′ ( x 1 ′ x 2 ′ x 3 ′ ) {\displaystyle {\begin{pmatrix}y'_{1}\\y'_{2}\\1\end{pmatrix}}={\frac {1}{x'_{3}}}{\begin{pmatrix}x'_{1}\\x'_{2}\\x'_{3}\end{pmatrix}}} これは、 y = 1 x 3 x ~ {\displaystyle \mathbf {y} ={\frac {1}{x_{3}}}\,{\tilde {\mathbf {x} }}}  と  y ′ = 1 x 3 ′ x ~ ′ {\displaystyle \mathbf {y} '={\frac {1}{x'_{3}}}\,{\tilde {\mathbf {x} }}'} のようにコンパクトに書くこともできる。ここで y {\displaystyle \mathbf {y} } と y ′ {\displaystyle \mathbf {y} '} は、二次元画像座標の同次表現であり、 x ~ {\displaystyle {\tilde {\mathbf {x} }}} と x ~ ′ {\displaystyle {\tilde {\mathbf {x} }}'} は適切な3次元座標だが、2つは異なる座標系である 正規化されたカメラのもう1つの結果は、各座標系を平行移動と回転によって関連付けられることである。これは、3次元座標の組が次のように式で関係付けられることを意味する。 x ~ ′ = R ( x ~ − t ) {\displaystyle {\tilde {\mathbf {x} }}'=\mathbf {R} \,({\tilde {\mathbf {x} }}-\mathbf {t} )} ここで R {\displaystyle \mathbf {R} } は 3 × 3 {\displaystyle 3\times 3} 回転行列、 t {\displaystyle \mathbf {t} } は3次元平行移動ベクトルである。 基本行列は次のように定義される。 ここで [ t ] × {\displaystyle [\mathbf {t} ]_{\times }} は t {\displaystyle \mathbf {t} } の外積の行列表現である。注: ここで、変換 [ R T | t ] {\displaystyle [\mathbf {R} ^{T}|\mathbf {t} ]} は2番目のビューの点を1番目のビューに変換する。 E {\displaystyle \mathbf {E} } の定義では、正規化された画像座標の方向のみに関心がある（参照 : 三重積）。そのため画像座標を基本方程式（英 : essential equation）に代入する際、平行移動成分は必要がない。この E {\displaystyle \mathbf {E} } の定義が対応する2つの画像座標間の制約を表すことを確認するには、次のように E {\displaystyle \mathbf {E} } の左右から2つの異なる座標系の点Pの3次元座標かければ良い。 x ~ ′ T E x ~ = ( 1 ) x ~ T R T R [ t ] × x ~ = ( 2 ) x ~ T [ t ] × x ~ = ( 3 ) 0 {\displaystyle {\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} 上で述べた x ~ ′ {\displaystyle {\tilde {\mathbf {x} }}'} と x ~ {\displaystyle {\tilde {\mathbf {x} }}} 間の関係と、 R {\displaystyle \mathbf {R} } と t {\displaystyle \mathbf {t} } を用いた E {\displaystyle \mathbf {E} } の定義を代入。 R {\displaystyle \mathbf {R} } は回転行列であるから、 R T R = I {\displaystyle \mathbf {R} ^{T}\,\mathbf {R} =\mathbf {I} } 。 外積の行列表現の性質。 最後に、いずれのカメラからも見えていることから x 3 {\displaystyle x_{3}} , x 3 ′ {\displaystyle x'_{3}} > 0 であると想定できる。これは次の式を与える。 0 = ( x ~ ′ ) T E x ~ = 1 x 3 ′ ( x ~ ′ ) T E 1 x 3 x ~ = ( y ′ ) T E y {\displaystyle 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 × 3 {\displaystyle 3\times 3} 行列が、何かしらのステレオカメラにとっての基本行列になるわけではない。（基本行列は1つの回転行列と1つの交代行列（いずれも 3 × 3 {\displaystyle 3\times 3} 行列）の行列積として定義されていることに注意。）。交代行列は等しい2つの特異値と0であるもう1つの特異値を持つ。回転行列の乗算は特異値を変えない。これは、基本行列もまた等しい2つの特異値と0であるもう1つの特異値をもつことを意味する。この性質は、しばしば基本行列の内部制約（英 : internal constraints）と呼ばれる。 基本行列 E {\displaystyle \mathbf {E} } にゼロ以外のスカラーを掛けても、その結果は E {\displaystyle \mathbf {E} } と全く同じ制約を与える基本行列となる。これは E {\displaystyle \mathbf {E} } を射影空間の元とみなせることを意味する。すなわち、一方が他方のゼロ以外のスカラー倍である場合、2つの行列は等価とみなされる。これは、例えば E {\displaystyle \mathbf {E} } が画像データから推定される場合の適切な考え方である。一方、 E {\displaystyle \mathbf {E} } を次のように定義することも考えられる。 E = [ t ~ ] × R {\displaystyle \mathbf {E} =[\mathbf {\widetilde {t}} ]_{\times }\,\mathbf {R} } ここで、 t ~ = − R t {\displaystyle \mathbf {\widetilde {t}} =-\mathbf {R} \mathbf {t} } であり、このとき E {\displaystyle \mathbf {E} } はwell-definedな「スケーリング」を持つ。どちらの考え方がより適切かは、その利用場面によって異なる。 制約は、次のようにも表せる。 det E = 0 {\displaystyle \det \mathbf {E} =0} また、 2 E E T E − tr ⁡ ( E E T ) E = 0. {\displaystyle 2\mathbf {E} \mathbf {E} ^{T}\mathbf {E} -\operatorname {tr} (\mathbf {E} \mathbf {E} ^{T})\mathbf {E} =0.} ここで、最後の式は行列制約で、各行列要素に1つずつ、9つの制約とみなせる。これらの制約は、5組の対応する点のペアから基本行列を決定するためによく用いられる。 基本行列には、射影要素として表示されるかどうかに応じて、5つまたは6つの自由度がある。回転行列 R {\displaystyle \mathbf {R} } と平行移動ベクトル t {\displaystyle \mathbf {t} } にはそれぞれ 3 つの自由度があり、合計で6つである。一方で基本行列を射影要素とみなす場合は、スカラー倍に関連する1つの自由度を差し引く必要があり、計5つの自由度となる。 対応する画像上の点のセットが与えられると、セット内のすべての点について定義されるエピポーラ制約を満たす基本行列を推定できる。ただし、（実際の状況ではよくあることだが）画像点がノイズの影響を受ける場合、すべての制約を正確に満たす基本行列を見つけることはできない。 各制約に関連する誤差がどのように測定されるかに応じて、対応する画像上の点の特定のセットの制約を最適に満たす基本行列を決定または推定できる。最も簡単なアプローチは、一般に8点アルゴリズムとして知られる最小二乗問題を設定することである。 上記の推定方法などによりステレオカメラペアの基本行列が分かっている場合、この情報を用いて2つのカメラ座標系間の回転行列 R {\displaystyle \mathbf {R} } と平行移動 t {\displaystyle \mathbf {t} } (スケーリングを含む)も決定できる。これらの導出において E {\displaystyle \mathbf {E} } はwell-definedに決定されたスケーリングを持つというよりは射影要素であるとみなされる。 R {\displaystyle \mathbf {R} } と t {\displaystyle \mathbf {t} } を決定する次の方法は、 E {\displaystyle \mathbf {E} } の特異値分解に基づく（ハートレーとジサーマンの本を参照）。 特異値分解を用いずに R {\displaystyle \mathbf {R} } と t {\displaystyle \mathbf {t} } を決定することもできる（ロンゲ・ヒギンズの論文等）。 E {\displaystyle \mathbf {E} } に対して特異値分解を実行すると次が得られる。 E = U Σ V T {\displaystyle \mathbf {E} =\mathbf {U} \,\mathbf {\Sigma } \,\mathbf {V} ^{T}} ここで U {\displaystyle \mathbf {U} } と V {\displaystyle \mathbf {V} } は 3 × 3 {\displaystyle 3\times 3} の直行行列で、 Σ {\displaystyle \mathbf {\Sigma } } は次のような 3 × 3 {\displaystyle 3\times 3} の対角行列である。 Σ = ( s 0 0 0 s 0 0 0 0 ) {\displaystyle \mathbf {\Sigma } ={\begin{pmatrix}s&0&0\\0&s&0\\0&0&0\end{pmatrix}}} Σ {\displaystyle \mathbf {\Sigma } } の対角要素は E {\displaystyle \mathbf {E} } の特異値であり、基本行列の内部制約に従い等しい2つの値と1つのゼロ値で構成される必要がある。また、次を定義する。 W = ( 0 − 1 0 1 0 0 0 0 1 ) {\displaystyle \mathbf {W} ={\begin{pmatrix}0&-1&0\\1&0&0\\0&0&1\end{pmatrix}}}  と  W − 1 = W T = ( 0 1 0 − 1 0 0 0 0 1 ) {\displaystyle \mathbf {W} ^{-1}=\mathbf {W} ^{T}={\begin{pmatrix}0&1&0\\-1&0&0\\0&0&1\end{pmatrix}}} そして、次のアンザッツを設定する。 [ t ] × = U W Σ U T {\displaystyle [\mathbf {t} ]_{\times }=\mathbf {U} \,\mathbf {W} \,\mathbf {\Sigma } \,\mathbf {U} ^{T}} R = U W − 1 V T {\displaystyle \mathbf {R} =\mathbf {U} \,\mathbf {W} ^{-1}\,\mathbf {V} ^{T}} 実際のカメラ画像などのデータを扱う場合、 Σ {\displaystyle \mathbf {\Sigma } } は制約を完全には満たさない可能性があるため、代わりに次を用いると役立つ場合がある。 [ t ] × = U Z U T {\displaystyle [\mathbf {t} ]_{\times }=\mathbf {U} \,\mathbf {Z} \,\mathbf {U} ^{T}}  と  Z = ( 0 1 0 − 1 0 0 0 0 0 ) {\displaystyle \mathbf {Z} ={\begin{pmatrix}0&1&0\\-1&0&0\\0&0&0\end{pmatrix}}} 第一に、 R {\displaystyle \mathbf {R} } と [ t ] × {\displaystyle [\mathbf {t} ]_{\times }} を表現している式は、以下より、基本行列の定義式を満たす。 [ t ] × R = U W Σ U T U W − 1 V T = U Σ V T = E {\displaystyle [\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} } 第二に、この [ t ] × {\displaystyle [\mathbf {t} ]_{\times }} がある t {\displaystyle \mathbf {t} } の外積の行列表現であることを示さなければならない。まず、 W Σ = ( 0 − s 0 s 0 0 0 0 0 ) {\displaystyle \mathbf {W} \,\mathbf {\Sigma } ={\begin{pmatrix}0&-s&0\\s&0&0\\0&0&0\end{pmatrix}}} であるから、 W Σ {\displaystyle \mathbf {W} \,\mathbf {\Sigma } } は交代行列、すなわち ( W Σ ) T = − W Σ {\displaystyle (\mathbf {W} \,\mathbf {\Sigma } )^{T}=-\mathbf {W} \,\mathbf {\Sigma } } である。これは次のように [ t ] × {\displaystyle [\mathbf {t} ]_{\times }} についても同様に当てはまる。 ( [ t ] × ) T = U ( W Σ ) T U T = − U W Σ U T = − [ t ] × {\displaystyle ([\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 }} 外積の行列表現の一般的な性質によれば、 [ t ] × {\displaystyle [\mathbf {t} ]_{\times }} はただ1つのベクトル t {\displaystyle \mathbf {t} } の外積演算子でなければならない。 第三に、 R {\displaystyle \mathbf {R} } が回転行列であることも示す必要がある。 R {\displaystyle \mathbf {R} } は3つの直交行列の積である。従って R {\displaystyle \mathbf {R} } もまた直交し、 det ( R ) = ± 1 {\displaystyle \det(\mathbf {R} )=\pm 1} である。回転行列であるためには、 det ( R ) = 1 {\displaystyle \det(\mathbf {R} )=1} でなければならないが、ここでは E {\displaystyle \mathbf {E} } は射影要素とみなされているため、必要であれば E {\displaystyle \mathbf {E} } の符号を反転することで実現できる。 ここまでで、 E {\displaystyle \mathbf {E} } が与えられた場合に R {\displaystyle \mathbf {R} } と t {\displaystyle \mathbf {t} } の1つの可能な解を求める手段が確立されている。しかし、これは唯一の可能な解ではなく、実用の観点からは有効な解でない可能性さえある。まず、 E {\displaystyle \mathbf {E} } のスケーリングが定義されていないため、 t {\displaystyle \mathbf {t} } のスケーリングも定義されていない。次の式が成り立つため、これは E {\displaystyle \mathbf {E} } の零空間にある必要がある。 E t = R [ t ] × t = 0 {\displaystyle \mathbf {E} \,\mathbf {t} =\mathbf {R} \,[\mathbf {t} ]_{\times }\,\mathbf {t} =\mathbf {0} } しかしこの後の解の分析のためには t {\displaystyle \mathbf {t} } の厳密なスケーリングは、その「符号」、つまりどの方向を指しているかほど重要ではない。 t