# 八點算法

## 共面性約束

${\displaystyle y'^{\mathrm {T} }\mathbf {E} y=0}$

## 基本算法

${\displaystyle (\mathbf {y} ')^{\mathrm {T} }\,\mathbf {E} \,\mathbf {y} =0}$

### 制定齊次線性方程

${\displaystyle \mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}}$${\displaystyle \mathbf {y} '={\begin{pmatrix}y'_{1}\\y'_{2}\\1\end{pmatrix}}}$同埋${\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}}}$

${\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}$
${\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\,}$

${\displaystyle \mathbf {e} \cdot {\tilde {\mathbf {y} }}=0}$

${\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}}}$同埋${\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}}}$

${\displaystyle \mathbf {e} \cdot {\tilde {\mathbf {y} }}_{k}=0}$

${\displaystyle \mathbf {e} ^{\mathrm {T} }\,\mathbf {Y} =\mathbf {0} }$

### 求解方程

${\displaystyle \|\mathbf {e} ^{\mathrm {T} }\,\mathbf {Y} \|}$

### 強制執行內部約束

${\displaystyle \|\mathbf {E} '-\mathbf {E} _{\rm {est}}\|}$

${\displaystyle \mathbf {E} _{\rm {est}}=\mathbf {U} \,\mathbf {S} \,\mathbf {V} ^{\mathrm {T} }}$

${\displaystyle \mathbf {S} '={\begin{pmatrix}s_{1}&0&0\\0&s_{2}&0\\0&0&0\end{pmatrix}},}$

${\displaystyle \mathbf {E} '=\mathbf {U} \,\mathbf {S} '\,\mathbf {V} ^{\mathrm {T} }}$

## 歸一化算法

${\displaystyle (\mathbf {y} ')^{\mathrm {T} }\,\mathbf {F} \,\mathbf {y} =0}$

${\displaystyle \mathbf {f} ^{\mathrm {T} }\,\mathbf {Y} =\mathbf {0} }$

### 原因

Hartley 喺 1997 年嘅文章中解決唨呢個估計問題。佢對個問題嘅分析表明，個問題係由於均勻圖像坐標喺個空間${\displaystyle \mathbb {R} ^{3}}$中嘅分佈唔好。二維圖像坐標嘅典型均勻表示${\displaystyle (y_{1},y_{2})\,}$

${\displaystyle \mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}}$

### 解決方案

• 新坐標系嘅原點應該以圖像點嘅質心（重心）為中心（有佢嘅原點）。呢個係透過捉原始來源翻譯成新來源來實現嘅。
• 平移後，坐標着統一縮放，令到從原點到一粒點嘅平均距離等於${\displaystyle {\sqrt {2}}}$ .

${\displaystyle \mathbf {\bar {y}} =\mathbf {T} \,\mathbf {y} }$
${\displaystyle \mathbf {\bar {y}} '=\mathbf {T} '\,\mathbf {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}} }$

${\displaystyle \mathbf {F} =(\mathbf {T} ')^{\mathrm {T} }\,\mathbf {\bar {F}} \,\mathbf {T} }$

## 取少過八粒點

Kaveh Fathian 等提出唨五、六、七點算法，係透過直接計算旋轉四元數嚟規避唔去計算個本質矩陣${\displaystyle \mathbf {E} }$[1] [2]

## 考

1. Fathian, Kaveh (2018). "QuEst: A Quaternion-Based Approach for Camera Motion Estimation From Minimal Feature Points". IEEE Robotics and Automation Letters. arXiv:1704.02672. doi:10.1109/LRA.2018.2792142.
2. Fathian, Kaveh (2018). "Camera relative pose estimation for visual servoing using quaternions". Robotics and Autonomous Systems. doi:10.1016/j.robot.2018.05.014.

## 讀埋

• 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.
• 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.