8点アルゴリズム

8点アルゴリズムは、コンピュータービジョンの分野で使用されるアルゴリズムで、対応する画像上の点のセットから、ステレオカメラペアに対応する基本行列または基礎行列を推定する。これは、1981 年にクリストファー・ロンゲ・ヒギンズによって基本行列の推定のために導入された。理論的には、このアルゴリズムは基礎行列にも使用できるが、実際上は1997年にリチャード・ハートレーによって記述され正規化された8点アルゴリズムがこのケースにより適している。
このアルゴリズムの名前は、対応する8つ（またはそれ以上）の画像上の点のセットから基本行列または基礎行列を推定するということに由来している。ただし、このアルゴリズムの変形は、8点未満の場合でも使用できる。
共平面性制約.
2台のカメラのエピポーラ幾何と空間内の点を代数方程式で表すことができる。点formula_1がどこにあったとしても、ベクトルformula_2、formula_3、formula_4は同一平面上にあることがわかる。「左目」の画像内の点formula_1の座標をformula_6、「右目」の画像内の点formula_1の座標をformula_8、2画像間の回転と平行移動をformula_9とする。2つの画像座標系でそれぞれ表されたformula_1の座標の間の関係はformula_11と表せる。記号formula_12をウェッジ積とすると、formula_13から生成されるベクトルはformula_14とformula_6の両方に直交するから、次の式が常に成り立つ。
formula_17であるから、次が得られる。
formula_19をformula_20に置き換えることで、次が得られる。
formula_22は行列とみなすことができる。ロンゲ・ヒギンズは記号formula_23を用いてそれを示した。積formula_24はしばしば基本行列と呼ばれformula_25で表される。
ベクトルformula_26はベクトルformula_27と平行であるから、これらのベクトルを置き換えても共平面性の制約は保持される。左右の画像平面へformula_1を投影した座標をformula_29とすると、共平面性制約は次のように記述できる。
基本的なアルゴリズム.
ここでは、基本行列formula_31を推定する場合の基本的な8点アルゴリズムについて説明する。これは3つのステップで構成されている。まず、同次線形方程式を定式化する。ここで、解はformula_31に直接関連しており、正しい解がない可能性があることを考慮して方程式を解く。最後に、得られた行列の内部制約を利用する。1番目のステップはロンゲ・ヒギンズの論文で説明されているもので、2番目と3番目のステップは推定理論の標準的なアプローチである。
基本行列formula_31によって定義される制約は次のように表せる。
formula_35は対応する画像上の点の正規化画像座標である。 アルゴリズムが解くべき問題は、対応する画像上の点の集合から基本行列formula_31を決定することである。実際には、画像点の画像座標はノイズの影響を受け、解も過剰決定される可能性がある。つまり、すべての点について上記の制約を正確に満たすformula_31を見つけることができない場合がある。この問題は、アルゴリズムの2番目のステップで対処される。
ステップ 1:同次線形方程式の定式化.
次のように、
と書くと、制約は次のように書き換えることもできる。
あるいは
ここで、それぞれ以下を表している。
つまり、これら2つのベクトルは直交している必要がある、ということである。formula_45は基本行列を9次元ベクトルの形式で表したものであり、同様にformula_46もformula_47行列formula_48を9次元ベクトルの形式で表したものになっている。
対応する画像上の点の各ペアは、ベクトルformula_46を生成する。3次元点formula_50の集合が与えられたとき、これらをベクトルformula_51の集合とみなすと、これらの全てがベクトルformula_45に対して次の式を満たさなければならない。
十分な数（少なくとも8つ）の線形独立なベクトルformula_51が与えられると、簡単な方法でformula_45を決定することができる。行列formula_56の列としてすべてのベクトルformula_51を集めると、次のようになる必要がある。
これはformula_45が同次線形方程式の解であることを意味する。
ステップ 2: 方程式を解く.
この方程式を解くための標準的なアプローチは、 formula_45をゼロに等しい特異値に対応するformula_56の右特異ベクトルとして求める方法である。formula_56を構成するために少なくとも8つの線形独立ベクトルformula_51が使用される場合、この特異ベクトルは（スカラー乗算を無視すれば）一意であり、formula_45とformula_31を決定できる。
formula_56を構成するために8より多くの対応点が使用される場合、ゼロに等しい特異値を持たない可能性がある。このケースは、画像座標がさまざまな種類のノイズの影響を受ける場合に実際に発生する。この状況に対処するための一般的なアプローチは、これを最小二乗問題として記述することである。すなわち、formula_67のもとで以下を最小にするformula_45を求める。
解はformula_56の"最小"特異値に対応する左特異ベクトルとしてformula_45を選択することで得られる。このformula_45をformula_47行列に並べ替えると、このステップの結果（ここではformula_74と呼ぶ）が得られる。
ステップ 3: 内部制約の適用.
ノイズの多い画像座標を扱っている場合は、結果の行列が基本行列の内部制約（その特異値のうち2つは互いに等しく非ゼロであり、もう1つはゼロでなければならない）を満たさない可能性もある。利用場面によって、内部制約からの偏差が小さい場合も大きい場合も、問題になる場合と問題にならない場合がある。推定された行列が内部制約を満たすことが重要な場合、これは以下を最小化するランク2の行列formula_75を見つけることによって達成できる。
ここでformula_74はステップ2で得られた行列で、フロベニウス行列ノルムが使用される。この問題を解くために、まず次のようにformula_74を特異値分解する。
ここでformula_80は直交行列であり、 formula_81はformula_74の特異値を含む対角行列である。理想的にはformula_81の対角要素の1つはゼロであるが、少なくとも互いに等しいことが期待されている他の2つと比較して小さい必要がある。いずれにせよ、次を設定する。
ここでformula_85はそれぞれformula_81の最大および2番目に大きい特異値である。 結局、formula_75は次のように与えられる。
行列formula_75がこのアルゴリズムによって得られた基本行列の推定結果である。
正規化されたアルゴリズム.
基本的な8点アルゴリズムは、原理的に基礎行列formula_90の推定にも使用できる。定義されるformula_90の制約は次のようになる。
ここでformula_35対応した画像座標の同次表現である（正規化していなくともよい）。これは、以下のように基本行列と同様の方法で行列formula_56を形成し、方程式を解くことができることを意味する。
ここでformula_96はformula_90のベクトル表現である。上記の手順に従うことで、8つの対応点の集合からformula_90を決定することができる。ただし実際には結果として得られる基本行列はエピポーラ制約を決定するのに役立たない場合がある。
問題点.
問題は、結果として得られるformula_56がしばしば悪条件（英 : "ill-conditioned"）となることである。理論上、formula_56はゼロに等しい特異値を1つ持つ必要があり、残りは非ゼロである。ただし実際には、非ゼロの特異値の一部は、大きな特異値に比べて小さくなる可能性がある。 formula_56を構成するために8よりも多い対応点が使用され、座標がほぼ正確である場合、ほぼゼロとして識別できるwell-definedな特異値が存在しない可能性がある。その結果、同次連立一次方程式の解は、実用に耐えうるほどの正確さが得られない可能性がある。
原因.
ハートレーは、1997年の記事でこの推定問題に対処した。彼の問題の分析は、問題がその空間formula_102内の同次画像座標の分布の悪さによって引き起こされることを示している。二次元画像座標formula_103の典型的な同次表現は次のようになる。
ここでformula_105はいずれも一般的なデジタルカメラでは、0から1000～2000の範囲にある。これは、formula_106の最初の2つの座標が3番目の座標よりもはるかに広い範囲にわたって変化することを意味する。さらに、formula_56を構築するために使用される画像上の点が画像の比較的小さな領域、例えばformula_108にある場合、ベクトルformula_106はすべての点に対してだいたい同じような方向を指す。結果として、formula_56には1つの大きな特異値があり、残りは小さい値になってしまう。
解決策.
この問題の解決策としてハートレーは次の原則に従って2画像のそれぞれの座標系を独立して新しい座標系に変換することを提案した。
この原則により通常2つの画像のそれぞれに対して個別に座標変換が行われる。その結果、新しい同次画像座標formula_112は次の式で与えられる。
ここでformula_115は、元の画像座標から新しい正規化された画像座標への変換（平行移動とスケーリング）である。この正規化は、単一の画像で使用される画像点のみに依存するもので、一般に正規化されたカメラによって生成される正規化画像座標とは異なるものである。
基礎行列に基づくエピポーラ制約は、次のように書き換えられる。
ここでformula_117である。これは、正規化された同次画像座標formula_112を使用して、上記の基本的な8点アルゴリズムを使用して変換された基本行列formula_119を推定できることを意味する。
正規化変換の目的は、一般に正規化された画像座標から構築された行列formula_120が、formula_56よりも優れた条件数を持つようにすることである。これは、解formula_122が同次方程式formula_123の解として、formula_56に対するformula_96に比べてより well-defined であることを意味する。formula_122が決定しformula_119が再形成されると次の式に従って"非正規化を行いformula_90"を得ることができる。
一般に、基礎行列のこの推定値は、正規化されていない座標からの推定値よりも優れている。
8未満の点を用いる場合.
各点ペアはformula_31の要素に対して1つの拘束方程式に与える。formula_31には5つの自由度があるため、formula_31の決定には5つの点ペアだけで十分なはずである。これは理論的な観点からは可能だが、実際に実装するのは簡単ではなく、さまざまな非線形方程式を解く必要がある。
カヴェ・ファシアンらは、回転クォータニオンを直接計算することにより、基本行列の計算を回避する5、6、および7点のアルゴリズムを提案した。