八點算法 （英文 ：Eight-point algorithm 電腦視覺 演算法 ，攞來從一組對應嘅圖像點估計啲戥一副立體相機孖有拏褦嘅本質矩陣 （essential matrix）或者基礎矩陣 （fundamental matrix）嘅。個演算法係由Christopher Longuet-Higgins 喺1981年針對本質矩陣嘅情況引入嘅。理論上講，個演算法亦都喺基礎矩陣使得到，但實際上，Richard Hartley喺1997年描述嘅歸一化八點算法 啱種情況多啲。
個演算法名來源係從一組八粒（或者再多啲）對應嘅圖像點來估計本質矩陣或者基礎矩陣。之不過，演算法嘅變體可以採少過八粒點。
共面性約束
編輯
基本算法
編輯
呢度描述有基本嘅八點算法，攞來估計本質矩陣
E
{\displaystyle \mathbf {E} }
齊次線性方程 ，其中個方程解戥
E
{\displaystyle \mathbf {E} }
估計理論 中嘅標準方法。
本質矩陣
E
{\displaystyle \mathbf {E} }
(
y
′
)
T
E
y
=
0
{\displaystyle (\mathbf {y} ')^{\mathrm {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
2
′
,
1
)
(
e
11
e
12
e
13
e
21
e
22
e
23
e
31
e
32
e
33
)
(
y
1
y
2
1
)
=
0
{\displaystyle (y'_{1},y'_{2},1){\begin{pmatrix}e_{11}&e_{12}&e_{13}\\e_{21}&e_{22}&e_{23}\\e_{31}&e_{32}&e_{33}\end{pmatrix}}{\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}=0}
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}}}
即係，
e
{\displaystyle \mathbf {e} }
y
~
{\displaystyle {\tilde {\mathbf {y} }}}
3
×
3
{\displaystyle 3\times 3}
y
′
y
T
{\displaystyle \mathbf {y} '\,\mathbf {y} ^{\mathrm {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}
畀定足夠多（至少八粒）線性無關嘅向量
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} ^{\mathrm {T} }\,\mathbf {Y} =\mathbf {0} }
個意思即係
e
{\displaystyle \mathbf {e} }
齊次線性方程嘅解 。
求解方程
編輯
解呢條方程嘅標準方法意思即係
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} ^{\mathrm {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}}}
強制執行內部約束
編輯
處理噪音圖像坐標嘅另一個後果係個結果矩陣可能唔滿足本質矩陣嘅內部約束，個約束即係佢啲奇異值當中有兩個係相等且非零、另一個為零。睇在唔同應用方面，戥內部約束偏差細啲或者大啲，成唔成問題都有可能。如果個估計得出嘅矩陣要滿足內部約束係好緊要，可以透過搵到rank 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}}}
Frobenius 矩陣範數 。呢個問題嘅解係幫
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} ^{\mathrm {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} ^{\mathrm {T} }}
矩陣
E
′
{\displaystyle \mathbf {E} '}
歸一化算法
編輯
基本嘅八點算法原則上亦都可以攞來估計返本質矩陣
F
{\displaystyle \mathbf {F} }
F
{\displaystyle \mathbf {F} }
(
y
′
)
T
F
y
=
0
{\displaystyle (\mathbf {y} ')^{\mathrm {T} }\,\mathbf {F} \,\mathbf {y} =0}
其中
y
,
y
′
{\displaystyle \mathbf {y} ,\mathbf {y} '}
Y
{\displaystyle \mathbf {Y} }
f
T
Y
=
0
{\displaystyle \mathbf {f} ^{\mathrm {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} }
Hartley 喺 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} }
解決方案
編輯
作為呢個問題嘅解決方案，Hartley 提出應該根據以下原則，捉兩幅圖像中每幅圖像嘅坐標系獨立噉變換成新嘅坐標系。
新坐標系嘅原點應該以圖像點嘅質心（重心）為中心（有佢嘅原點）。呢個係透過捉原始來源翻譯成新來源來實現嘅。
平移後，坐標着統一縮放，令到從原點到一粒點嘅平均距離等於
2
{\displaystyle {\sqrt {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}} ')^{\mathrm {T} }\,((\mathbf {T} ')^{\mathrm {T} })^{-1}\,\mathbf {F} \,\mathbf {T} ^{-1}\,\mathbf {\bar {y}} =(\mathbf {\bar {y}} ')^{\mathrm {T} }\,\mathbf {\bar {F}} \,\mathbf {\bar {y}} }
其中
F
¯
=
(
(
T
′
)
T
)
−
1
F
T
−
1
{\displaystyle \mathbf {\bar {F}} =((\mathbf {T} ')^{\mathrm {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 {f} }
Y
{\displaystyle \mathbf {Y} }
f
¯
{\displaystyle \mathbf {\bar {f}} }
Y
¯
f
¯
{\displaystyle \mathbf {\bar {Y}} \,\mathbf {\bar {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} ')^{\mathrm {T} }\,\mathbf {\bar {F}} \,\mathbf {T} }
一般來講，本質矩陣嘅呢種估計好過非標準化坐標嘅估計。
取少過八粒點
編輯
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 . H. Christopher Longuet-Higgins (September 1981). "A computer algorithm for reconstructing a scene from two projections". Nature . 293 (5828): 133–135. doi :10.1038/293133a0 . 
