8点アルゴリズム

8点アルゴリズムは、コンピュータービジョンの分野で使用されるアルゴリズムで、対応する画像上の点のセットから、ステレオカメラペアに対応する基本行列または基礎行列を推定する。これは、1981 年にクリストファー・ロンゲ・ヒギンズによって基本行列の推定のために導入された。理論的には、このアルゴリズムは基礎行列にも使用できるが、実際上は1997年にリチャード・ハートレーによって記述され正規化された8点アルゴリズムがこのケースにより適している。

このアルゴリズムの名前は、対応する8つ（またはそれ以上）の画像上の点のセットから基本行列または基礎行列を推定するということに由来している。ただし、このアルゴリズムの変形は、8点未満の場合でも使用できる。

共平面性制約

エピポーラ幾何の例。投影点O _LおよびO _Rのそれぞれの中心を持つ 2 つのカメラは点Pを観測する。各画像平面へのＰの投影は、p_Ｌおよびp_Ｒで示される。点E_LとE_Rはエピポールである。

2台のカメラのエピポーラ幾何と空間内の点を代数方程式で表すことができる。点$P$がどこにあったとしても、ベクトル${\overline {O_{L}P}}$、${\overline {O_{R}P}}$、${\overline {O_{R}O_{L}}}$は同一平面上にあることがわかる。「左目」の画像内の点$P$の座標を$X_{L}$、「右目」の画像内の点$P$の座標を$X_{R}$、2画像間の回転と平行移動を$R,T$とする。2つの画像座標系でそれぞれ表された$P$の座標の間の関係は$X_{R}=R(X_{L}-T)$と表せる。記号$\wedge$をウェッジ積とすると、$T\wedge X_{L}$から生成されるベクトルは$T$と$X_{L}$の両方に直交するから、次の式が常に成り立つ。

$X_{L}^{T}T\wedge X_{L}-T^{T}T\wedge X_{L}=(X_{L}-T)^{T}T\wedge X_{L}=0$

$I=R^{T}R$であるから、次が得られる。

$(X_{L}-T)^{T}R^{T}RT\wedge X_{L}=0$ .

$(X_{L}-T)^{T}R^{T}$を$X_{R}^{T}$に置き換えることで、次が得られる。

$X_{R}^{T}RT\wedge X_{L}=X_{R}^{T}RSX_{L}=X_{R}^{T}EX_{L}=0$

$T\wedge$は行列とみなすことができる。ロンゲ・ヒギンズは記号$S$を用いてそれを示した。積$RT\wedge =RS$はしばしば基本行列と呼ばれ$E$で表される。

ベクトル${\overline {O_{L}p_{L}}},{\overline {O_{R}p_{R}}}$はベクトル${\overline {O_{L}P}},{\overline {O_{R}P}}$と平行であるから、これらのベクトルを置き換えても共平面性の制約は保持される。左右の画像平面へ$P$を投影した座標を$y,y'$とすると、共平面性制約は次のように記述できる。

$y'^{T}\mathbf {E} y=0$

基本的なアルゴリズム

ここでは、基本行列$\mathbf {E}$を推定する場合の基本的な8点アルゴリズムについて説明する。これは3つのステップで構成されている。まず、同次線形方程式を定式化する。ここで、解は$\mathbf {E}$に直接関連しており、正しい解がない可能性があることを考慮して方程式を解く。最後に、得られた行列の内部制約を利用する。1番目のステップはロンゲ・ヒギンズの論文で説明されているもので、2番目と3番目のステップは推定理論の標準的なアプローチである。

基本行列$\mathbf {E}$によって定義される制約は次のように表せる。

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

$\mathbf {y} ,\mathbf {y} '$は対応する画像上の点の正規化画像座標である。 アルゴリズムが解くべき問題は、対応する画像上の点の集合から基本行列$\mathbf {E}$を決定することである。実際には、画像点の画像座標はノイズの影響を受け、解も過剰決定される可能性がある。つまり、すべての点について上記の制約を正確に満たす$\mathbf {E}$を見つけることができない場合がある。この問題は、アルゴリズムの2番目のステップで対処される。

ステップ 1:同次線形方程式の定式化

次のように、

$\mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}$ と $\mathbf {y} '={\begin{pmatrix}y'_{1}\\y'_{2}\\1\end{pmatrix}}$ と $\mathbf {E} ={\begin{pmatrix}e_{11}&e_{12}&e_{13}\\e_{21}&e_{22}&e_{23}\\e_{31}&e_{32}&e_{33}\end{pmatrix}}$

と書くと、制約は次のように書き換えることもできる。

$y'_{1}y_{1}e_{11}+y'_{1}y_{2}e_{12}+y'_{1}e_{13}+y'_{2}y_{1}e_{21}+y'_{2}y_{2}e_{22}+y'_{2}e_{23}+y_{1}e_{31}+y_{2}e_{32}+e_{33}=0\,$

あるいは

$\mathbf {e} \cdot {\tilde {\mathbf {y} }}=0$

ここで、それぞれ以下を表している。

${\tilde {\mathbf {y} }}={\begin{pmatrix}y'_{1}y_{1}\\y'_{1}y_{2}\\y'_{1}\\y'_{2}y_{1}\\y'_{2}y_{2}\\y'_{2}\\y_{1}\\y_{2}\\1\end{pmatrix}}$ と $\mathbf {e} ={\begin{pmatrix}e_{11}\\e_{12}\\e_{13}\\e_{21}\\e_{22}\\e_{23}\\e_{31}\\e_{32}\\e_{33}\end{pmatrix}}$

つまり、これら2つのベクトルは直交している必要がある、ということである。$\mathbf {e}$は基本行列を9次元ベクトルの形式で表したものであり、同様に${\tilde {\mathbf {y} }}$も$3\times 3$行列$\mathbf {y} '\,\mathbf {y} ^{T}$を9次元ベクトルの形式で表したものになっている。

対応する画像上の点の各ペアは、ベクトル${\tilde {\mathbf {y} }}$を生成する。3次元点$\mathbf {P} _{k}$の集合が与えられたとき、これらをベクトル${\tilde {\mathbf {y} }}_{k}$の集合とみなすと、これらの全てがベクトル$\mathbf {e}$に対して次の式を満たさなければならない。

$\mathbf {e} \cdot {\tilde {\mathbf {y} }}_{k}=0$

十分な数（少なくとも8つ）の線形独立なベクトル${\tilde {\mathbf {y} }}_{k}$が与えられると、簡単な方法で$\mathbf {e}$を決定することができる。行列$\mathbf {Y}$の列としてすべてのベクトル${\tilde {\mathbf {y} }}_{k}$を集めると、次のようになる必要がある。

$\mathbf {e} ^{T}\,\mathbf {Y} =\mathbf {0}$

これは$\mathbf {e}$が同次線形方程式の解であることを意味する。

ステップ 2: 方程式を解く

この方程式を解くための標準的なアプローチは、 $\mathbf {e}$をゼロに等しい特異値に対応する$\mathbf {Y}$の右特異ベクトルとして求める方法である。$\mathbf {Y}$を構成するために少なくとも8つの線形独立ベクトル${\tilde {\mathbf {y} }}_{k}$が使用される場合、この特異ベクトルは（スカラー乗算を無視すれば）一意であり、$\mathbf {e}$と$\mathbf {E}$を決定できる。

$\mathbf {Y}$を構成するために8より多くの対応点が使用される場合、ゼロに等しい特異値を持たない可能性がある。このケースは、画像座標がさまざまな種類のノイズの影響を受ける場合に実際に発生する。この状況に対処するための一般的なアプローチは、これを最小二乗問題として記述することである。すなわち、$\|\mathbf {e} \|=1$のもとで以下を最小にする$\mathbf {e}$を求める。

$\|\mathbf {e} ^{T}\,\mathbf {Y} \|$

解は$\mathbf {Y}$の最小特異値に対応する左特異ベクトルとして$\mathbf {e}$を選択することで得られる。この$\mathbf {e}$を$3\times 3$行列に並べ替えると、このステップの結果（ここでは$\mathbf {E} _{\rm {est}}$と呼ぶ）が得られる。

ステップ 3: 内部制約の適用

ノイズの多い画像座標を扱っている場合は、結果の行列が基本行列の内部制約（その特異値のうち2つは互いに等しく非ゼロであり、もう1つはゼロでなければならない）を満たさない可能性もある。利用場面によって、内部制約からの偏差が小さい場合も大きい場合も、問題になる場合と問題にならない場合がある。推定された行列が内部制約を満たすことが重要な場合、これは以下を最小化するランク2の行列$\mathbf {E} '$を見つけることによって達成できる。

$\|\mathbf {E} '-\mathbf {E} _{\rm {est}}\|$

ここで$\mathbf {E} _{\rm {est}}$はステップ2で得られた行列で、フロベニウス行列ノルムが使用される。この問題を解くために、まず次のように$\mathbf {E} _{\rm {est}}$を特異値分解する。

$\mathbf {E} _{\rm {est}}=\mathbf {U} \,\mathbf {S} \,\mathbf {V} ^{T}$

ここで$\mathbf {U} ,\mathbf {V}$は直交行列であり、 $\mathbf {S}$は$\mathbf {E} _{\rm {est}}$の特異値を含む対角行列である。理想的には$\mathbf {S}$の対角要素の1つはゼロであるが、少なくとも互いに等しいことが期待されている他の2つと比較して小さい必要がある。いずれにせよ、次を設定する。

$\mathbf {S} '={\begin{pmatrix}s_{1}&0&0\\0&s_{2}&0\\0&0&0\end{pmatrix}},$

ここで$s_{1},s_{2}$はそれぞれ$\mathbf {S}$の最大および2番目に大きい特異値である。 結局、$\mathbf {E} '$は次のように与えられる。

$\mathbf {E} '=\mathbf {U} \,\mathbf {S} '\,\mathbf {V} ^{T}$

行列$\mathbf {E} '$がこのアルゴリズムによって得られた基本行列の推定結果である。

正規化されたアルゴリズム

基本的な8点アルゴリズムは、原理的に基礎行列$\mathbf {F}$の推定にも使用できる。定義される$\mathbf {F}$の制約は次のようになる。

$(\mathbf {y} ')^{T}\,\mathbf {F} \,\mathbf {y} =0$

ここで$\mathbf {y} ,\mathbf {y} '$対応した画像座標の同次表現である（正規化していなくともよい）。これは、以下のように基本行列と同様の方法で行列$\mathbf {Y}$を形成し、方程式を解くことができることを意味する。

$\mathbf {f} ^{T}\,\mathbf {Y} =\mathbf {0}$

ここで$\mathbf {f}$は$\mathbf {F}$のベクトル表現である。上記の手順に従うことで、8つの対応点の集合から$\mathbf {F}$を決定することができる。ただし実際には結果として得られる基本行列はエピポーラ制約を決定するのに役立たない場合がある。

問題点

問題は、結果として得られる$\mathbf {Y}$がしばしば悪条件（英 : ill-conditioned）となることである。理論上、$\mathbf {Y}$はゼロに等しい特異値を1つ持つ必要があり、残りは非ゼロである。ただし実際には、非ゼロの特異値の一部は、大きな特異値に比べて小さくなる可能性がある。 $\mathbf {Y}$を構成するために8よりも多い対応点が使用され、座標がほぼ正確である場合、ほぼゼロとして識別できるwell-definedな特異値が存在しない可能性がある。その結果、同次連立一次方程式の解は、実用に耐えうるほどの正確さが得られない可能性がある。

原因

ハートレーは、1997年の記事でこの推定問題に対処した。彼の問題の分析は、問題がその空間$\mathbb {R} ^{3}$内の同次画像座標の分布の悪さによって引き起こされることを示している。二次元画像座標$(y_{1},y_{2})\,$の典型的な同次表現は次のようになる。

$\mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}$

ここで$y_{1},y_{2}\,$はいずれも一般的なデジタルカメラでは、0から1000～2000の範囲にある。これは、$\mathbf {y}$の最初の2つの座標が3番目の座標よりもはるかに広い範囲にわたって変化することを意味する。さらに、$\mathbf {Y}$を構築するために使用される画像上の点が画像の比較的小さな領域、例えば$(700,700)\pm (100,100)\,$にある場合、ベクトル$\mathbf {y}$はすべての点に対してだいたい同じような方向を指す。結果として、$\mathbf {Y}$には1つの大きな特異値があり、残りは小さい値になってしまう。

解決策

この問題の解決策としてハートレーは次の原則に従って2画像のそれぞれの座標系を独立して新しい座標系に変換することを提案した。

• 新しい座標系の原点は、画像の図心（重心）を中心とする（原点を持つ）必要がある。これは、元の原点を新しい原点に平行移動することで実現できる。
• 平行移動後、原点から点までの距離の平均が${\sqrt {2}}$に等しくなるように、座標を均一にスケーリングする。

この原則により通常2つの画像のそれぞれに対して個別に座標変換が行われる。その結果、新しい同次画像座標$\mathbf {\bar {y}} ,\mathbf {\bar {y}} '$は次の式で与えられる。

$\mathbf {\bar {y}} =\mathbf {T} \,\mathbf {y}$

$\mathbf {\bar {y}} '=\mathbf {T} '\,\mathbf {y} '$

ここで$\mathbf {T} ,\mathbf {T} '$は、元の画像座標から新しい正規化された画像座標への変換（平行移動とスケーリング）である。この正規化は、単一の画像で使用される画像点のみに依存するもので、一般に正規化されたカメラによって生成される正規化画像座標とは異なるものである。

基礎行列に基づくエピポーラ制約は、次のように書き換えられる。

$0=(\mathbf {\bar {y}} ')^{T}\,((\mathbf {T} ')^{T})^{-1}\,\mathbf {F} \,\mathbf {T} ^{-1}\,\mathbf {\bar {y}} =(\mathbf {\bar {y}} ')^{T}\,\mathbf {\bar {F}} \,\mathbf {\bar {y}}$

ここで$\mathbf {\bar {F}} =((\mathbf {T} ')^{T})^{-1}\,\mathbf {F} \,\mathbf {T} ^{-1}$である。これは、正規化された同次画像座標$\mathbf {\bar {y}} ,\mathbf {\bar {y}} '$を使用して、上記の基本的な8点アルゴリズムを使用して変換された基本行列$\mathbf {\bar {F}}$を推定できることを意味する。

正規化変換の目的は、一般に正規化された画像座標から構築された行列$\mathbf {\bar {Y}}$が、$\mathbf {Y}$よりも優れた条件数を持つようにすることである。これは、解$\mathbf {\bar {f}}$が同次方程式$\mathbf {\bar {Y}} \,\mathbf {\bar {f}}$の解として、$\mathbf {Y}$に対する$\mathbf {f}$に比べてより well-defined であることを意味する。$\mathbf {\bar {f}}$が決定し$\mathbf {\bar {F}}$が再形成されると次の式に従って非正規化を行い$\mathbf {F}$を得ることができる。

$\mathbf {F} =(\mathbf {T} ')^{T}\,\mathbf {\bar {F}} \,\mathbf {T}$

一般に、基礎行列のこの推定値は、正規化されていない座標からの推定値よりも優れている。

8未満の点を用いる場合

各点ペアは$\mathbf {E}$の要素に対して1つの拘束方程式に与える。$\mathbf {E}$には5つの自由度があるため、$\mathbf {E}$の決定には5つの点ペアだけで十分なはずである。これは理論的な観点からは可能だが、実際に実装するのは簡単ではなく、さまざまな非線形方程式を解く必要がある。

カヴェ・ファシアンらは、回転クォータニオンを直接計算することにより、基本行列の計算を回避する5、6、および7点のアルゴリズムを提案した。

関連項目

• 基本行列
  • 基本行列#回転と平行移動の抽出
• 基礎行列
• 三焦点テンソル

参考文献

• Richard I. Hartley (June 1997). “In Defense of the Eight-Point Algorithm”. IEEE Transactions on Pattern Recognition and Machine Intelligence 19 (6): 580–593. doi:10.1109/34.601246. 

• Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. ISBN 978-0-521-54051-3 

• 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.