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

基本行列（きほんぎょうれつ、英 : "essential matrix"）formula_1はコンピュータビジョンの分野で用いられる formula_2 行列であり、カメラがピンホールカメラモデルを満たすことを仮定したステレオ画像ペア間の対応する2点の関係を表す。
概要.
より具体的には、 formula_3とformula_4をそれぞれ画像1と2の同次"正規化"画像座標とし、formula_3とformula_4がシーン内の同じ3次元点に対応する場合、以下の式が成り立つ。
基本行列を定義する上記の関係は、1981年にH.クリストファー・ロンゲ・ヒギンズによって発表され、この概念がコンピュータービジョンコミュニティに紹介された。 リチャード・ハートレーとアンドリュー・ジサーマンの著書では、類似の行列がもっと以前から写真測量法に登場していたと報告されている。 ロンゲ・ヒギンズの論文には、対応する正規化画像座標の組からformula_1推定するためのアルゴリズムと、formula_1が既知である場合に2台のカメラの相対的な位置と向きを決定するためのアルゴリズムが含まれている。そして最終的に、基本行列を用いて画像上の点の3次元座標を決定する方法を示している。
利用.
基本行列は、基礎行列formula_10の前身とみなせる。いずれの行列も画像上の点ペア間の制約を確立できるが、基本行列は正規化を行うためにカメラの内部パラメータ（行列formula_11とformula_12）を知る必要があるため、キャリブレーションされたカメラ間の関係にのみ使用できる。カメラがキャリブレーション済みである場合には、基本行列はカメラ間の相対的な位置と方向、および対応する画像上の点の3次元位置の両方を決定するために利用できる。基本行列は、基礎行列と次の関係がある。
導出と定義.
ここではロンゲ・ヒギンズによる論文に従って導出を行う。
正規化済みの2つのカメラが、それぞれの画像平面に3次元世界を投影しているとする。点Pの3次元座標を各カメラの座標系に対してformula_14とformula_15とする。カメラは正規化済みであるからピンホールカメラモデルが適用でき、対応する画像座標は
と表せる。
2つの画像座標の同次表現は、次の式で与えられる。
これは、
のようにコンパクトに書くこともできる。ここでformula_22とformula_4は、二次元画像座標の同次表現であり、formula_24とformula_25は適切な3次元座標だが、2つは異なる座標系である
正規化されたカメラのもう1つの結果は、各座標系を平行移動と回転によって関連付けられることである。これは、3次元座標の組が次のように式で関係付けられることを意味する。
ここでformula_27は formula_2 回転行列、formula_29は3次元平行移動ベクトルである。
基本行列は次のように定義される。
ここでformula_30はformula_29の外積の行列表現である。注: ここで、変換formula_32は2番目のビューの点を1番目のビューに変換する。
formula_33の定義では、正規化された画像座標の方向のみに関心がある（参照 : 三重積）。そのため画像座標を基本方程式（英 : "essential equation"）に代入する際、平行移動成分は必要がない。このformula_33の定義が対応する2つの画像座標間の制約を表すことを確認するには、次のようにformula_1の左右から2つの異なる座標系の点Pの3次元座標かければ良い。
最後に、いずれのカメラからも見えていることからformula_44, formula_45 > 0 であると想定できる。これは次の式を与える。
これは、基本行列が対応する画像上の点間で定義する制約である。
性質.
すべての formula_2 行列が、何かしらのステレオカメラにとっての基本行列になるわけではない。（基本行列は1つの回転行列と1つの交代行列（いずれも formula_2 行列）の行列積として定義されていることに注意。）。交代行列は等しい2つの特異値と0であるもう1つの特異値を持つ。回転行列の乗算は特異値を変えない。これは、基本行列もまた等しい2つの特異値と0であるもう1つの特異値をもつことを意味する。この性質は、しばしば基本行列の"内部制約（英" : "internal constraints）"と呼ばれる。
基本行列formula_1にゼロ以外のスカラーを掛けても、その結果はformula_1と全く同じ制約を与える基本行列となる。これはformula_1を射影空間の元とみなせることを意味する。すなわち、一方が他方のゼロ以外のスカラー倍である場合、2つの行列は等価とみなされる。これは、例えばformula_1が画像データから推定される場合の適切な考え方である。一方、formula_1を次のように定義することも考えられる。
ここで、formula_55であり、このときformula_1はwell-definedな「スケーリング」を持つ。どちらの考え方がより適切かは、その利用場面によって異なる。
制約は、次のようにも表せる。
また、
ここで、最後の式は行列制約で、各行列要素に1つずつ、9つの制約とみなせる。これらの制約は、5組の対応する点のペアから基本行列を決定するためによく用いられる。
基本行列には、射影要素として表示されるかどうかに応じて、5つまたは6つの自由度がある。回転行列formula_27と平行移動ベクトルformula_29にはそれぞれ 3 つの自由度があり、合計で6つである。一方で基本行列を射影要素とみなす場合は、スカラー倍に関連する1つの自由度を差し引く必要があり、計5つの自由度となる。
推定.
対応する画像上の点のセットが与えられると、セット内のすべての点について定義されるエピポーラ制約を満たす基本行列を推定できる。ただし、（実際の状況ではよくあることだが）画像点がノイズの影響を受ける場合、すべての制約を正確に満たす基本行列を見つけることはできない。
各制約に関連する誤差がどのように測定されるかに応じて、対応する画像上の点の特定のセットの制約を最適に満たす基本行列を決定または推定できる。最も簡単なアプローチは、一般に8点アルゴリズムとして知られる最小二乗問題を設定することである。
回転と平行移動の抽出.
上記の推定方法などによりステレオカメラペアの基本行列が分かっている場合、この情報を用いて2つのカメラ座標系間の回転行列formula_27と平行移動formula_29(スケーリングを含む)も決定できる。これらの導出においてformula_1はwell-definedに決定されたスケーリングを持つというよりは射影要素であるとみなされる。
1つの解を見つける.
formula_27とformula_29を決定する次の方法は、formula_1の特異値分解に基づく（ハートレーとジサーマンの本を参照）。 特異値分解を用いずにformula_27とformula_29を決定することもできる（ロンゲ・ヒギンズの論文等）。
formula_1に対して特異値分解を実行すると次が得られる。
ここでformula_71とformula_72はformula_2の直行行列で、formula_74は次のようなformula_2の対角行列である。
formula_74の対角要素はformula_1の特異値であり、基本行列の内部制約に従い等しい2つの値と1つのゼロ値で構成される必要がある。また、次を定義する。
そして、次のアンザッツを設定する。
実際のカメラ画像などのデータを扱う場合、formula_74は制約を完全には満たさない可能性があるため、代わりに次を用いると役立つ場合がある。
証明.
第一に、formula_27とformula_30を表現している式は、以下より、基本行列の定義式を満たす。
第二に、このformula_30があるformula_29の外積の行列表現であることを示さなければならない。まず、
であるから、formula_92は交代行列、すなわち formula_93 である。これは次のようにformula_30についても同様に当てはまる。
外積の行列表現の一般的な性質によれば、formula_30はただ1つのベクトルformula_29の外積演算子でなければならない。
第三に、formula_27が回転行列であることも示す必要がある。formula_27は3つの直交行列の積である。従ってformula_100もまた直交し、formula_101である。回転行列であるためには、formula_102でなければならないが、ここではformula_1は射影要素とみなされているため、必要であればformula_1の符号を反転することで実現できる。
すべての解を見つける.
ここまでで、formula_1が与えられた場合にformula_27とformula_29の1つの可能な解を求める手段が確立されている。しかし、これは唯一の可能な解ではなく、実用の観点からは有効な解でない可能性さえある。まず、formula_1のスケーリングが定義されていないため、formula_29のスケーリングも定義されていない。次の式が成り立つため、これはformula_1の零空間にある必要がある。
しかしこの後の解の分析のためにはformula_29の厳密なスケーリングは、その「符号」、つまりどの方向を指しているかほど重要ではない。formula_113をformula_1の零空間で正規化されたベクトルとする。このときformula_113とformula_116の両方がformula_1に対して有効な平行移動ベクトルになる。上で述べたformula_27とformula_29の導出では、formula_120をformula_121に変更することもできる。この変更は、平行移動ベクトルに対しては符号の変更のみを起こす。これについては可能性として既に説明した。一方で回転に対しては、少なくとも一般的なケースでは、これは異なる変換を生成する。
要約すると、与えられたformula_1には、formula_29に対して可能な2つの正反対な方向があり、この基本行列に準じた2つの異なる回転がある。これにより、2つのカメラ座標系間の回転と平行移動に対して計4つの解のクラスが得られる。その上、選択された平行移動方向の未知のスケーリング formula_124 も存在する。
ただし、4つの解のクラスのうち、実際に実現できるのは1つだけである。対応する画像座標のペアが与えられたとき、3つの解のクラスは常に2つのカメラのうち少なくとも1つの後方に3次元点を生成してしまいカメラから見ることができない。4つのクラスのうちの1つだけが、常に両方のカメラの前方に3次元点を生成する。これが正しい解であるはずである。ただしそれでも、平行移動成分に関する未定の正のスケーリングがある。
上記のformula_27とformula_29の決定はformula_1が基本行列の内部制約を満たすことを前提としている。これが当てはまらない場合、典型的には例えばformula_1が実際の（ノイズの多い）画像データから推定されている場合には、内部制約をほぼ満たしていると想定する必要がある。ベクトルformula_113は、最小の特異値に対応するformula_1の右特異ベクトルとして選択される。
対応する画像上の点からの3次元点.
対応する正規化された画像座標formula_131とformula_132が与えられた場合、基本行列が既知であり対応する回転および平行移動が決定されていれば、formula_133を計算する多くの方法が存在する。