8点アルゴリズム は、コンピュータービジョン の分野で使用されるアルゴリズムで、対応する画像上の点のセットから、ステレオカメラペアに対応する基本行列 または基礎行列 を推定する。これは、1981 年にクリストファー・ロンゲ・ヒギンズ によって基本行列の推定のために導入された。理論的には、このアルゴリズムは基礎行列にも使用できるが、実際上は1997年にリチャード・ハートレー によって記述され正規化された8点アルゴリズムがこのケースにより適している。
このアルゴリズムの名前は、対応する8つ（またはそれ以上）の画像上の点のセットから基本行列または基礎行列を推定するということに由来している。ただし、このアルゴリズムの変形は、8点未満の場合でも使用できる。
エピポーラ幾何の例。 投影点O L およびO R のそれぞれの中心を持つ 2 つのカメラは点P を観測する。各画像平面へのＰ の投影は、p Ｌ およびp Ｒ で示される。点E L とE R はエピポールである。2台のカメラのエピポーラ幾何 と空間内の点を代数方程式で表すことができる。点
P
{\displaystyle P}
O
L
P
¯
{\displaystyle {\overline {O_{L}P}}}
O
R
P
¯
{\displaystyle {\overline {O_{R}P}}}
O
R
O
L
¯
{\displaystyle {\overline {O_{R}O_{L}}}}
P
{\displaystyle P}
X
L
{\displaystyle X_{L}}
P
{\displaystyle P}
X
R
{\displaystyle X_{R}}
R
,
T
{\displaystyle R,T}
P
{\displaystyle P}
X
R
=
R
(
X
L
−
T
)
{\displaystyle X_{R}=R(X_{L}-T)}
∧
{\displaystyle \wedge }
ウェッジ積 とすると、
T
∧
X
L
{\displaystyle T\wedge X_{L}}
T
{\displaystyle T}
X
L
{\displaystyle X_{L}}
X
L
T
T
∧
X
L
−
T
T
T
∧
X
L
=
(
X
L
−
T
)
T
T
∧
X
L
=
0
{\displaystyle 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
{\displaystyle I=R^{T}R}
(
X
L
−
T
)
T
R
T
R
T
∧
X
L
=
0
{\displaystyle (X_{L}-T)^{T}R^{T}RT\wedge X_{L}=0}
(
X
L
−
T
)
T
R
T
{\displaystyle (X_{L}-T)^{T}R^{T}}
X
R
T
{\displaystyle X_{R}^{T}}
X
R
T
R
T
∧
X
L
=
X
R
T
R
S
X
L
=
X
R
T
E
X
L
=
0
{\displaystyle X_{R}^{T}RT\wedge X_{L}=X_{R}^{T}RSX_{L}=X_{R}^{T}EX_{L}=0}
T
∧
{\displaystyle T\wedge }
S
{\displaystyle S}
R
T
∧
=
R
S
{\displaystyle RT\wedge =RS}
基本行列 と呼ばれ
E
{\displaystyle E}
ベクトル
O
L
p
L
¯
,
O
R
p
R
¯
{\displaystyle {\overline {O_{L}p_{L}}},{\overline {O_{R}p_{R}}}}
O
L
P
¯
,
O
R
P
¯
{\displaystyle {\overline {O_{L}P}},{\overline {O_{R}P}}}
P
{\displaystyle P}
y
,
y
′
{\displaystyle y,y'}
y
′
T
E
y
=
0
{\displaystyle y'^{T}\mathbf {E} y=0}
ここでは、基本行列
E
{\displaystyle \mathbf {E} }
同次線形方程式 を定式化する。ここで、解は
E
{\displaystyle \mathbf {E} }
基本行列
E
{\displaystyle \mathbf {E} }
(
y
′
)
T
E
y
=
0
{\displaystyle (\mathbf {y} ')^{T}\,\mathbf {E} \,\mathbf {y} =0}
y
,
y
′
{\displaystyle \mathbf {y} ,\mathbf {y} '}
E
{\displaystyle \mathbf {E} }
E
{\displaystyle \mathbf {E} }
次のように、
y
=
(
y
1
y
2
1
)
{\displaystyle \mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}}
y
′
=
(
y
1
′
y
2
′
1
)
{\displaystyle \mathbf {y} '={\begin{pmatrix}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}}}
と書くと、制約は次のように書き換えることもできる。
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
{\displaystyle 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\,}
あるいは
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} }
y
~
{\displaystyle {\tilde {\mathbf {y} }}}
3
×
3
{\displaystyle 3\times 3}
y
′
y
T
{\displaystyle \mathbf {y} '\,\mathbf {y} ^{T}}
対応する画像上の点の各ペアは、ベクトル
y
~
{\displaystyle {\tilde {\mathbf {y} }}}
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} }
同次線形方程式 の解であることを意味する。
この方程式を解くための標準的なアプローチは、
e
{\displaystyle \mathbf {e} }
Y
{\displaystyle \mathbf {Y} }
右特異ベクトル として求める方法である。
Y
{\displaystyle \mathbf {Y} }
y
~
k
{\displaystyle {\tilde {\mathbf {y} }}_{k}}
e
{\displaystyle \mathbf {e} }
E
{\displaystyle \mathbf {E} }
Y
{\displaystyle \mathbf {Y} }
最小二乗 問題として記述することである。すなわち、
‖
e
‖
=
1
{\displaystyle \|\mathbf {e} \|=1}
e
{\displaystyle \mathbf {e} }
‖
e
T
Y
‖
{\displaystyle \|\mathbf {e} ^{T}\,\mathbf {Y} \|}
解は
Y
{\displaystyle \mathbf {Y} }
最小 特異値に対応する左特異ベクトルとして
e
{\displaystyle \mathbf {e} }
e
{\displaystyle \mathbf {e} }
3
×
3
{\displaystyle 3\times 3}
E
e
s
t
{\displaystyle \mathbf {E} _{\rm {est}}}
ノイズの多い画像座標を扱っている場合は、結果の行列が基本行列の内部制約（その特異値のうち2つは互いに等しく非ゼロであり、もう1つはゼロでなければならない）を満たさない可能性もある。利用場面によって、内部制約からの偏差が小さい場合も大きい場合も、問題になる場合と問題にならない場合がある。推定された行列が内部制約を満たすことが重要な場合、これは以下を最小化するランク2の行列
E
′
{\displaystyle \mathbf {E} '}
‖
E
′
−
E
e
s
t
‖
{\displaystyle \|\mathbf {E} '-\mathbf {E} _{\rm {est}}\|}
ここで
E
e
s
t
{\displaystyle \mathbf {E} _{\rm {est}}}
フロベニウス行列ノルム が使用される。この問題を解くために、まず次のように
E
e
s
t
{\displaystyle \mathbf {E} _{\rm {est}}}
特異値分解 する。
E
e
s
t
=
U
S
V
T
{\displaystyle \mathbf {E} _{\rm {est}}=\mathbf {U} \,\mathbf {S} \,\mathbf {V} ^{T}}
ここで
U
,
V
{\displaystyle \mathbf {U} ,\mathbf {V} }
S
{\displaystyle \mathbf {S} }
E
e
s
t
{\displaystyle \mathbf {E} _{\rm {est}}}
S
{\displaystyle \mathbf {S} }
S
′
=
(
s
1
0
0
0
s
2
0
0
0
0
)
,
{\displaystyle \mathbf {S} '={\begin{pmatrix}s_{1}&0&0\\0&s_{2}&0\\0&0&0\end{pmatrix}},}
ここで
s
1
,
s
2
{\displaystyle s_{1},s_{2}}
S
{\displaystyle \mathbf {S} }
E
′
{\displaystyle \mathbf {E} '}
E
′
=
U
S
′
V
T
{\displaystyle \mathbf {E} '=\mathbf {U} \,\mathbf {S} '\,\mathbf {V} ^{T}}
行列
E
′
{\displaystyle \mathbf {E} '}
基本的な8点アルゴリズムは、原理的に基礎行列
F
{\displaystyle \mathbf {F} }
F
{\displaystyle \mathbf {F} }
(
y
′
)
T
F
y
=
0
{\displaystyle (\mathbf {y} ')^{T}\,\mathbf {F} \,\mathbf {y} =0}
ここで
y
,
y
′
{\displaystyle \mathbf {y} ,\mathbf {y} '}
Y
{\displaystyle \mathbf {Y} }
f
T
Y
=
0
{\displaystyle \mathbf {f} ^{T}\,\mathbf {Y} =\mathbf {0} }
ここで
f
{\displaystyle \mathbf {f} }
F
{\displaystyle \mathbf {F} }
F
{\displaystyle \mathbf {F} }
エピポーラ制約 を決定するのに役立たない場合がある。
問題は、結果として得られる
Y
{\displaystyle \mathbf {Y} }
悪条件 （英 : ill-conditioned ）となることである。理論上、
Y
{\displaystyle \mathbf {Y} }
Y
{\displaystyle \mathbf {Y} }
well-defined な特異値が存在しない可能性がある。その結果、同次連立一次方程式の解は、実用に耐えうるほどの正確さが得られない可能性がある。
ハートレーは、1997年の記事でこの推定問題に対処した。彼の問題の分析は、問題がその空間
R
3
{\displaystyle \mathbb {R} ^{3}}
(
y
1
,
y
2
)
{\displaystyle (y_{1},y_{2})\,}
y
=
(
y
1
y
2
1
)
{\displaystyle \mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}}
ここで
y
1
,
y
2
{\displaystyle y_{1},y_{2}\,}
y
{\displaystyle \mathbf {y} }
Y
{\displaystyle \mathbf {Y} }
(
700
,
700
)
±
(
100
,
100
)
{\displaystyle (700,700)\pm (100,100)\,}
y
{\displaystyle \mathbf {y} }
Y
{\displaystyle \mathbf {Y} }
この問題の解決策としてハートレーは次の原則に従って2画像のそれぞれの座標系を独立して新しい座標系に変換することを提案した。
新しい座標系の原点は、画像の図心（重心）を中心とする（原点を持つ）必要がある。これは、元の原点を新しい原点に平行移動することで実現できる。
平行移動後、原点から点までの距離の平均が
2
{\displaystyle {\sqrt {2}}}
この原則により通常2つの画像のそれぞれに対して個別に座標変換が行われる。その結果、新しい同次画像座標
y
¯
,
y
¯
′
{\displaystyle \mathbf {\bar {y}} ,\mathbf {\bar {y}} '}
y
¯
=
T
y
{\displaystyle \mathbf {\bar {y}} =\mathbf {T} \,\mathbf {y} }
y
¯
′
=
T
′
y
′
{\displaystyle \mathbf {\bar {y}} '=\mathbf {T} '\,\mathbf {y} '}
ここで
T
,
T
′
{\displaystyle \mathbf {T} ,\mathbf {T} '}
基礎行列に基づくエピポーラ制約は、次のように書き換えられる。
0
=
(
y
¯
′
)
T
(
(
T
′
)
T
)
−
1
F
T
−
1
y
¯
=
(
y
¯
′
)
T
F
¯
y
¯
{\displaystyle 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}} }
ここで
F
¯
=
(
(
T
′
)
T
)
−
1
F
T
−
1
{\displaystyle \mathbf {\bar {F}} =((\mathbf {T} ')^{T})^{-1}\,\mathbf {F} \,\mathbf {T} ^{-1}}
y
¯
,
y
¯
′
{\displaystyle \mathbf {\bar {y}} ,\mathbf {\bar {y}} '}
F
¯
{\displaystyle \mathbf {\bar {F}} }
正規化変換の目的は、一般に正規化された画像座標から構築された行列
Y
¯
{\displaystyle \mathbf {\bar {Y}} }
Y
{\displaystyle \mathbf {Y} }
条件数 を持つようにすることである。これは、解
f
¯
{\displaystyle \mathbf {\bar {f}} }
Y
¯
f
¯
{\displaystyle \mathbf {\bar {Y}} \,\mathbf {\bar {f}} }
Y
{\displaystyle \mathbf {Y} }
f
{\displaystyle \mathbf {f} }
f
¯
{\displaystyle \mathbf {\bar {f}} }
F
¯
{\displaystyle \mathbf {\bar {F}} }
非正規化を行い
F
{\displaystyle \mathbf {F} }
を得ることができる。
F
=
(
T
′
)
T
F
¯
T
{\displaystyle \mathbf {F} =(\mathbf {T} ')^{T}\,\mathbf {\bar {F}} \,\mathbf {T} }
一般に、基礎行列のこの推定値は、正規化されていない座標からの推定値よりも優れている。
各点ペアは
E
{\displaystyle \mathbf {E} }
E
{\displaystyle \mathbf {E} }
E
{\displaystyle \mathbf {E} }
カヴェ・ファシアンらは、回転クォータニオン を直接計算することにより、基本行列の計算を回避する5、6、および7点のアルゴリズムを提案した。 [ 1] [ 2]
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 
