8 点アルゴリズムは 、 コンピュータ ビジョン で使用されるアルゴリズムで、 対応する画像点のセットからステレオ カメラ ペアに関連する 必須行列 または 基本行列 を推定します。これは、必須行列の場合に Christopher Longuet-Higginsによって 1981 年に導入されました。理論上、このアルゴリズムは基本行列にも使用できますが、実際には、1997 年に Richard Hartley によって説明された正規化された 8 点アルゴリズムの方が このケースに適しています。
このアルゴリズムの名前は、8 個 (またはそれ以上) の対応する画像ポイントのセットから必須マトリックスまたは基本マトリックスを推定するという事実に由来しています。ただし、このアルゴリズムのバリエーションは、8 個未満のポイントにも使用できます。
共平面性制約 エピポーラ幾何学の例。 それぞれの中心が投影点 O L と O R である 2 台のカメラが点 P を 観測します。各画像平面への P の投影は p L と p R で示されます。点 E L と E R は エピポールです。 2 台のカメラと空間内の 1 点のエピポーラ幾何学 を代数方程式で 表すことができます。点 が空間内のどこにあっても、ベクトル 、 、 は 同じ平面に属することに注意してください。 左目の参照フレームでの 点の座標を 、 右目の参照フレームで の点の座標を 、 2 つの参照フレーム間の回転と移動をと呼びます。st は、2 つの参照フレームで の の座標間の関係です 。 から生成されたベクトルは と の 両方に直交する ため、次の方程式が常に成立します 。
ポ
{\displaystyle P}
お
ら
ポ
¯
{\displaystyle {\overline {O_{L}P}}}
お
R
ポ
¯
{\displaystyle {\overline {O_{R}P}}}
お
R
お
ら
¯
{\displaystyle {\overline {O_{R}O_{L}}}}
バツ
ら
{\displaystyle X_{L}}
ポ
{\displaystyle P}
バツ
R
{\displaystyle X_{R}}
ポ
{\displaystyle P}
R 、 T
{\displaystyle R,T}
バツ
R
= R （
バツ
ら
− T ）
{\displaystyle X_{R}=R(X_{L}-T)}
ポ
{\displaystyle P}
T ∧
バツ
ら
{\displaystyle T\wedge X_{L}}
T
{\displaystyle T}
バツ
ら
{\displaystyle X_{L}}
バツ
ら
T
T ∧
バツ
ら
−
T
T
T ∧
バツ
ら
= （
バツ
ら
− T
）
T
T ∧
バツ
ら
= 0
{\displaystyle X_{L}^{T}T\wedge X_{L}-T^{T}T\wedge X_{L}=(X_{L}-T)^{T}T\wedge X_{L}=0}
なぜなら 、私たちは
私 =
R
T
R
{\displaystyle I=R^{T}R}
（
バツ
ら
− T
）
T
R
T
R T ∧
バツ
ら
= 0
{\displaystyle (X_{L}-T)^{T}R^{T}RT\wedge X_{L}=0}
。 を に 置き換えると 、
（
バツ
ら
− T
）
T
R
T
{\displaystyle (X_{L}-T)^{T}R^{T}}
バツ
R
T
{\displaystyle X_{R}^{T}}
バツ
R
T
R T ∧
バツ
ら
=
バツ
R
T
R ス
バツ
ら
=
バツ
R
T
え
バツ
ら
= 0
{\displaystyle X_{R}^{T}RT\wedge X_{L}=X_{R}^{T}RSX_{L}=X_{R}^{T}EX_{L}=0}
は行列として考えることができること に注意してください。Longuet-Higgins は 、これを表すために記号 を使用しました。この積は、 しばしば 基本行列 と呼ばれ、 で表されます 。
T ∧
{\displaystyle T\wedge}
ス
{\displaystyle S}
R T ∧ = R ス
{\displaystyle RT\wedge =RS}
え
{\displaystyle E}
ベクトルは ベクトルに平行なので、これらのベクトルを代入すれば共平面性制約が成立する。 の投影座標を 左と右の画像平面と
呼ぶと、共平面性制約は次のように書ける。
お
ら
p
ら
¯
、
お
R
p
R
¯
{\displaystyle {\overline {O_{L}p_{L}}},{\overline {O_{R}p_{R}}}}
お
ら
ポ
¯
、
お
R
ポ
¯
{\displaystyle {\overline {O_{L}P}},{\overline {O_{R}P}}}
ええ 、
ええ ′
{\displaystyle y,y'}
ポ
{\displaystyle P}
ええ
′
T
え
ええ = 0
{\displaystyle y'^{T}\mathbf {E} y=0}
基本アルゴリズム ここでは、基本的な 8 点アルゴリズムについて、必須行列 を推定する場合について説明します 。このアルゴリズムは 3 つのステップで構成されます。まず、 同次線形方程式 を作成します。この方程式の解は に直接関連しており 、次に方程式が正確な解を持たない可能性があることを考慮して方程式を解きます。最後に、結果として得られる行列の内部制約を管理します。最初のステップは Longuet-Higgins の論文で説明されており、2 番目と 3 番目のステップは推定理論における標準的なアプローチです。
え
{\displaystyle \mathbf {E} }
え
{\displaystyle \mathbf {E} }
本質的な行列によって定義される制約 は
え
{\displaystyle \mathbf {E} }
（
ええ
′
）
T
え
ええ
= 0
{\displaystyle (\mathbf {y} ')^{T}\,\mathbf {E} \,\mathbf {y} =0}
正規化された画像座標で表された対応する画像点について 。アルゴリズムが解決する問題は 、一致する画像点のセットを決定することです。実際には、画像点の画像座標はノイズの影響を受け、解も過剰決定である可能性があります。つまり、 すべての点に対して上記の制約を正確に満たすものを見つけることができない可能性があります。この問題は、アルゴリズムの 2 番目のステップで対処されます。
ええ
、
ええ
′
{\displaystyle \mathbf {y} ,\mathbf {y} '}
え
{\displaystyle \mathbf {E} }
え
{\displaystyle \mathbf {E} }
と
ええ
=
（
ええ
1
ええ
2
1
）
{\displaystyle \mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}}
そして そして
ええ
′
=
（
ええ
1
′
ええ
2
′
1
）
{\displaystyle \mathbf {y} '={\begin{pmatrix}y'_{1}\\y'_{2}\\1\end{pmatrix}}}
え
=
（
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}}}
この制約は次のように書き直すこともできる。
ええ
1
′
ええ
1
e
11
+
ええ
1
′
ええ
2
e
12
+
ええ
1
′
e
13
+
ええ
2
′
ええ
1
e
21
+
ええ
2
′
ええ
2
e
22
+
ええ
2
′
e
23
+
ええ
1
e
31
+
ええ
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}}}
つまり、 9次元ベクトルの形で基本的な行列を表し、このベクトルは 行列 のベクトル表現として見ることができるベクトルと直交する必要があります 。
e
{\displaystyle \mathbf {e} }
y
~
{\displaystyle {\tilde {\mathbf {y} }}}
3
×
3
{\displaystyle 3\times 3}
y
′
y
T
{\displaystyle \mathbf {y} '\,\mathbf {y} ^{T}}
対応する画像点の各ペアはベクトルを生成する 。3D点の集合が与えられた場合、 これはベクトルの集合に対応し 、それらはすべて次の式を満たす必要がある。
y
~
{\displaystyle {\tilde {\mathbf {y} }}}
P
k
{\displaystyle \mathbf {P} _{k}}
y
~
k
{\displaystyle {\tilde {\mathbf {y} }}_{k}}
e
⋅
y
~
k
=
0
{\displaystyle \mathbf {e} \cdot {\tilde {\mathbf {y} }}_{k}=0}
ベクトル について 。十分な数（少なくとも8つ）の線形独立ベクトルが与えられれば、 簡単な方法で 決定することができます。すべてのベクトルを 行列の列として集める と、次のようになります。
e
{\displaystyle \mathbf {e} }
y
~
k
{\displaystyle {\tilde {\mathbf {y} }}_{k}}
e
{\displaystyle \mathbf {e} }
y
~
k
{\displaystyle {\tilde {\mathbf {y} }}_{k}}
Y
{\displaystyle \mathbf {Y} }
e
T
Y
=
0
{\displaystyle \mathbf {e} ^{T}\,\mathbf {Y} =\mathbf {0} }
これは、 が 同次線形方程式 の解であることを意味します 。
e
{\displaystyle \mathbf {e} }
ステップ2: 方程式を解く この方程式を解く標準的なアプローチでは、 は の 右特異ベクトル であり、これ は0 に等しい 特異値 に対応します 。少なくとも 8 つの線形独立ベクトルを 使用して構築すると 、この特異ベクトルは一意であり (スカラー乗算を無視)、したがって、 と を 決定できます。
e
{\displaystyle \mathbf {e} }
Y
{\displaystyle \mathbf {Y} }
y
~
k
{\displaystyle {\tilde {\mathbf {y} }}_{k}}
Y
{\displaystyle \mathbf {Y} }
e
{\displaystyle \mathbf {e} }
E
{\displaystyle \mathbf {E} }
8点以上の対応点が構築に使用されている場合、ゼロに等しい特異値を持たない可能性があり ます
。これは、画像座標がさまざまなタイプのノイズの影響を受ける場合に実際に発生します。この状況に対処する一般的な方法は、これを 最小二乗 問題として記述することです。
Y
{\displaystyle \mathbf {Y} }
e
{\displaystyle \mathbf {e} }
‖
e
T
Y
‖
{\displaystyle \|\mathbf {e} ^{T}\,\mathbf {Y} \|}
のとき、となります。この解法は、 の 最小の 特異値 に対応する左特異ベクトルとして を 選択することです 。これを行列 に戻して並べ替えると 、このステップの結果が得られ、ここでは と呼ばれます 。
‖
e
‖
=
1
{\displaystyle \|\mathbf {e} \|=1}
e
{\displaystyle \mathbf {e} }
Y
{\displaystyle \mathbf {Y} }
e
{\displaystyle \mathbf {e} }
3
×
3
{\displaystyle 3\times 3}
E
e
s
t
{\displaystyle \mathbf {E} _{\rm {est}}}
ステップ3: 内部制約の強制 ノイズの多い画像座標を扱うことによるもう1つの結果は、結果として得られる行列が基本行列の内部制約を満たさない可能性があることです。つまり、その特異値のうち2つが等しくゼロでなく、もう1つがゼロであるということです。アプリケーションによっては、内部制約からの偏差が小さいか大きいかが問題になる場合とそうでない場合があります。推定された行列が内部制約を満たすことが重要である場合、これは、次の式 を最小化するランク2の
行列を見つけることによって達成できます。
E
′
{\displaystyle \mathbf {E} '}
‖
E
′
−
E
e
s
t
‖
{\displaystyle \|\mathbf {E} '-\mathbf {E} _{\rm {est}}\|}
ここで、 は ステップ 2 の結果の行列であり、 フロベニウス行列ノルム が使用されます。 問題の解は、まず の 特異値分解 を計算することによって得られます 。
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}}
ここで、 は直交行列であり、 はの特異値を含む対角行列である 。理想的な場合、の対角要素の1つは ゼロであるか、少なくとも等しい他の2つと比較して小さいはずである。いずれの場合も、
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}},}
ここで、それぞれ 最大と2番目に大きい特異値です 。最後に、は次 のように与えられます
。
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} }
は の形状を変更したものです 。 上記の手順に従うと、 8 つの一致する点のセットから を決定することができます。ただし、実際には、結果として得られる基本行列は、エピポーラ制約を決定するのに役立たない場合があります。
f
{\displaystyle \mathbf {f} }
F
{\displaystyle \mathbf {F} }
F
{\displaystyle \mathbf {F} }
困難 問題は、結果として得られる が しばしば 条件が悪く なることです。理論上、 は 1 つの特異値がゼロで、残りは非ゼロになります。しかし、実際には、非ゼロの特異値の一部が、大きい特異値に比べて小さくなることがあります。 を構築するために 8 個を超える対応する点が使用され 、座標が近似的に正しいだけの場合、近似的にゼロであると識別できる明確に定義された特異値が存在しない可能性があります。その結果、同次線形方程式の解は、十分に正確でなく、役に立たない可能性があります。
Y
{\displaystyle \mathbf {Y} }
Y
{\displaystyle \mathbf {Y} }
Y
{\displaystyle \mathbf {Y} }
原因 ハートリーは1997年の論文でこの推定問題を取り上げました。彼の分析によると、この問題は同次画像座標の空間内での分布が不十分なために発生することが示されています 。2D画像座標の典型的な同次表現 は、
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}}}
ここで、最新のデジタル カメラでは、 両方とも0 から 1000–2000 の範囲にあります。つまり、 の最初の 2 つの座標は 、3 番目の座標よりもはるかに広い範囲で変化します。さらに、 の構築に使用される画像ポイントが 、たとえば などの画像の比較的狭い領域にある場合 、ベクトル はすべてのポイントに対してほぼ同じ方向を指します。その結果、 は 1 つの大きな特異値を持ち、残りは小さくなります。
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}} }
ここで、これは、正規化された同次画像座標を使用して、 上記の基本的な8点アルゴリズムを使用して
変換された基本行列を推定する ことが可能であることを意味します。
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}} }
f
{\displaystyle \mathbf {f} }
Y
{\displaystyle \mathbf {Y} }
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} }
一般に、この基本行列の推定値は、正規化されていない座標から推定した場合よりも優れています。
8ポイント未満を使用する 各点のペアは、 の要素に対する 1 つの制約方程式に貢献します 。 は 5 つの自由度を持つため、 を決定するには 5 つの点のペアのみで十分です 。 David Nister は、5 つのペアの点のセットから本質的な行列を推定する効率的なソリューションを提案しました。これは 5 点アルゴリズムとして知られています。 [1] Hartley らは後に、Nister のアルゴリズムに基づいて修正されたより安定した 5 点アルゴリズムを提案しました。 [2]
E
{\displaystyle \mathbf {E} }
E
{\displaystyle \mathbf {E} }
E
{\displaystyle \mathbf {E} }
参照
参考文献
^ Nister, David (2004). 「5 点相対姿勢問題に対する効率的な解決法」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 26 (6): 756–770. doi :10.1109/TPAMI.2004.17. PMID 18579936. S2CID 886598. ^ Li, Hongdong (2006). 「5 点モーション推定を簡単に」 第 18 回国際パターン認識会議 (ICPR'06) pp. 630–633. doi :10.1109/ICPR.2006.579. ISBN 0-7695-2521-0 . S2CID 7745676。
さらに読む Richard I. Hartley (1997 年 6 月)。「8 ポイント アルゴリズムの擁護」 IEEE Transactions on Pattern Analysis and Machine Intelligence。19 ( 6): 580–593。doi :10.1109/34.601246。S2CID 16919747 。 リチャード・ハートリー、アンドリュー・ジッサーマン (2003)。『 コンピュータ ビジョンにおけるマルチビュージオメトリ 』ケンブリッジ大学出版局。ISBN 978-0-521-54051-3 。 
