8点アルゴリズム
この方程式を解くための標準的なアプローチは、 e {\displaystyle \mathbf {e} } をゼロに等しい特異値に対応する Y {\displaystyle \mathbf {Y} } の右特異ベクトルとして求める方法である。 Y {\displaystyle \mathbf {Y} } を構成するために少なくとも8つの線形独立ベクトル y ~ k {\displaystyle {\tilde {\mathbf {y} }}_{k}} が使用される場合、この特異ベクトルは(スカラー乗算を無視すれば)一意であり、 e {\displaystyle \mathbf {e} } と E {\displaystyle \mathbf {E} } を決定できる。
Y {\displaystyle \mathbf {Y} } を構成するために8より多くの対応点が使用される場合、ゼロに等しい特異値を持たない可能性がある。このケースは、画像座標がさまざまな種類のノイズの影響を受ける場合に実際に発生する。
各点ペアは E {\displaystyle \mathbf {E} } の要素に対して1つの拘束方程式に与える。 E {\displaystyle \mathbf {E} } には5つの自由度があるため、 E {\displaystyle \mathbf {E} } の決定には5つの点ペアだけで十分なはずである。これは理論的な観点からは可能だが、実際に実装するのは簡単ではなく、さまざまな非線形方程式を解く必要がある。
カヴェ・ファシアンらは、回転クォータニオンを直接計算することにより、基本行列の計算を回避する5、6、および7点のアルゴリズムを提案した。
対応する画像上の点の各ペアは、ベクトル y ~ {\displaystyle {\tilde {\mathbf {y} }}} を生成する。3次元点 P k {\displaystyle \mathbf {P} _{k}} の集合が与えられたとき、これらをベクトル y ~ k {\displaystyle {\tilde {\mathbf {y} }}_{k}} の集合とみなすと、これらの全てがベクトル e {\displaystyle \mathbf {e} } に対して次の式を満たさなければならない。
e ⋅ y ~ k = 0 {\displaystyle \mathbf {e} \cdot {\tilde {\mathbf {y} }}_{k}=0}
十分な数(少なくとも8つ)の線形独立なベクトル y ~ k {\displaystyle {\tilde {\mathbf {y} }}_{k}} が与えられると、簡単な方法で e {\displaystyle \mathbf {e} } を決定することができる。行列 Y {\displaystyle \mathbf {Y} } の列としてすべてのベクトル y ~ k {\displaystyle {\tilde {\mathbf {y} }}_{k}} を集めると、次のようになる必要がある。
e T Y = 0 {\displaystyle \mathbf {e} ^{T}\,\mathbf {Y} =\mathbf {0} }
これは e {\displaystyle \mathbf {e} } が同次線形方程式の解であることを意味する。
8点アルゴリズムは、コンピュータービジョンの分野で使用されるアルゴリズムで、対応する画像上の点のセットから、ステレオカメラペアに対応する基本行列または基礎行列を推定する。これは、1981 年にクリストファー・ロンゲ・ヒギンズによって基本行列の推定のために導入された。理論的には、このアルゴリズムは基礎行列にも使用できるが、実際上は1997年にリチャード・ハートレーによって記述され正規化された8点アルゴリズムがこのケースにより適している。
このアルゴリズムの名前は、対応する8つ(またはそれ以上)の画像上の点のセットから基本行列または基礎行列を推定するということに由来している。ただし、このアルゴリズムの変形は、8点未満の場合でも使用できる。
e ⋅ y ~ = 0 {\displaystyle \mathbf {e} \cdot {\tilde {\mathbf {y} }}=0}
ここで、それぞれ以下を表している。
y ~ = ( 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 ) {\displaystyle {\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}}} と e = ( e 11 e 12 e 13 e 21 e 22 e 23 e 31 e 32 e 33 ) {\displaystyle \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つのベクトルは直交している必要がある、ということである。 e {\displaystyle \mathbf {e} } は基本行列を9次元ベクトルの形式で表したものであり、同様に y ~ {\displaystyle {\tilde {\mathbf {y} }}} も 3 × 3 {\displaystyle 3\times 3} 行列 y ′ y T {\displaystyle \mathbf {y} '\,\mathbf {y} ^{T}} を9次元ベクトルの形式で表したものになっている。