八點算法

**八點算法**（）係一種雙視角電腦視覺演算法，攞來從一組對應嘅圖像點估計啲戥一副立體相機孖有拏褦嘅本質矩陣（essential matrix）或者基礎矩陣（fundamental matrix）嘅。個演算法係由Christopher Longuet-Higgins喺1981年針對本質矩陣嘅情況引入嘅。理論上講，個演算法亦都喺基礎矩陣使得到，但實際上，Richard Hartley喺1997年描述嘅歸一化八點算法啱種情況多啲。

個演算法名來源係從一組八粒（或者再多啲）對應嘅圖像點來估計本質矩陣或者基礎矩陣。之不過，演算法嘅變體可以採少過八粒點。

## 共面性約束

兩台相機同空間裏頭一點嘅對極幾何可以攞代數方程來表示（睇右圖）。簡單嚟講，兩粒相機點連成嘅線\overline{O_L O_R}係「**基線**」（），\overline{O_L P}, \overline{O_R P}喺第幅（對手幅）圖像上嘅投影線係啲「**對極線**」（）注意，無論點P喺空間裏頭邊啲埞，向量\overline{O_L P}, \overline{O_R P}同 \overline{O_R O_L}都屬於同一幅平面（即「**對極平面**」，）。參睇對極幾何相關內容，如果令y, y'係P投影到左右圖像平面上嘅坐標，噉共面性約束可以寫得成

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


## 基本算法
呢度描述有基本嘅八點算法，攞來估計本質矩陣 \mathbf{E} 嘅情況，係由三個步驟組成。首先，寫出齊次線性方程，其中個方程解戥 \mathbf{E} 有拏褦，求解方程同時考慮到可能冇精確解，最後得到矩陣嘅內部約束（internal constraints）。 Longuet-Higgins 嘅論文裏便描述到第一步，第二步同第三步係估計理論中嘅標準方法。

本質矩陣 \mathbf{E} 定義到嘅約束係

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

約束到啲相應圖像點，喺條式裏便係攞歸一化圖像坐標迾 \mathbf{y}, \mathbf{y}' 表示嘅。呢個演算法解決嘅問題係確定 \mathbf{E} 畀一組圖像匹配嘅點。喺實踐中，像點嘅圖像坐標受噪音嘅影響，個解亦都可能係超定（over-determined）嘅，意思係可能冇辦法搵到 \mathbf{E}  係喺所有點完全滿足上述約束嘅。呢個問題喺演算法嘅第二步裏頭得到解決。

### 制定[[線性方程組|齊次線性方程]]
透過

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

或者

:  \mathbf{e} \cdot \tilde{\mathbf{y}} = 0 

其中有

:  \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} 同埋 \mathbf{e} = \begin{pmatrix} e_{11} \\ e_{12} \\ e_{13} \\ e_{21} \\ e_{22} \\ e_{23} \\ e_{31} \\ e_{32} \\ e_{33} \end{pmatrix} 

即係，  \mathbf{e} 以 9 維向量嘅形式表示本質矩陣，呢枚向量必須戥向量 \tilde{\mathbf{y}} 正交，可以睇作係表示向量嘅 3 \times 3 矩陣 \mathbf{y}' \, \mathbf{y}^{\mathrm 
 T}  .

每副對應嘅圖像點產生一枚向量 \tilde{\mathbf{y}}  .一組 3D 點 \mathbf{P}_k 對應於一組向量 \tilde{\mathbf{y}}_{k} ，而且對於向量 \mathbf{e} 必須都滿足：

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

畀定足夠多（至少八粒）線性無關嘅向量 \tilde{\mathbf{y}}_{k} 可以直接噉確定得到 \mathbf{e} 。擸齊所有向量 \tilde{\mathbf{y}}_{k} 作為矩陣 \mathbf{Y} 嘅一列，噉實有：

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

個意思即係 \mathbf{e} 係個齊次線性方程嘅解。

### 求解方程
解呢條方程嘅標準方法意思即係 \mathbf{e} 係 \mathbf{Y} 嘅左奇異向量對應於一個零奇異值。假設至少有八粒線性無關向量 \tilde{\mathbf{y}}_{k} 着攞來構建 \mathbf{Y} ，噉呢個奇異向量係唯一嘅（唔考慮標量乘法），因此，  \mathbf{e} 同埋 \mathbf{E} 都可以確定。

使用8個以上對應點來構建 \mathbf{Y} 嘅情況下，有可能做到冇任何等於零嘅奇異值。實際操作係會發生呢種情況，指喺圖像坐標受到各種類型嘅噪音影響嗰陣。處理呢種情況嘅常用方法係捉佢描述成總體最細二乘問題；搵返 \mathbf{e} 係最細化條式嘅：

:  \| \mathbf{e}^{\mathrm T} \, \mathbf{Y} \| 

前提保證 \| \mathbf{e} \| = 1  .解決辦法係揀 \mathbf{e} 作為對應於 \mathbf{Y} 最細奇異值嘅左奇異向量。呢個 \mathbf{e} 重新排過，整成一個 3 \times 3 矩陣，即畀出呢步嘅結果，記成 \mathbf{E}_{\rm est}  .

### 強制執行內部約束
處理噪音圖像坐標嘅另一個後果係個結果矩陣可能唔滿足本質矩陣嘅內部約束，個約束即係佢啲奇異值當中有兩個係相等且非零、另一個為零。睇在唔同應用方面，戥內部約束偏差細啲或者大啲，成唔成問題都有可能。如果個估計得出嘅矩陣要滿足內部約束係好緊要，可以透過搵到rank 2  \mathbf{E}' 矩陣嚟最細化下式來完成：

:  \| \mathbf{E}' - \mathbf{E}_{\rm est} \| 

其中 \mathbf{E}_{\rm est} 係步驟 2 嘅結果矩陣，並使用Frobenius 矩陣範數。呢個問題嘅解係幫 \mathbf{E}_{\rm est}  計個奇異值分解先：

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

其中 \mathbf{U}, \mathbf{V} 係正交矩陣， \mathbf{S} 係包含 \mathbf{E}_{\rm est} 奇異值嘅對角矩陣。喺理想情況下， \mathbf{S} 對角線元素之一應該係零，或者者至少細過其他兩個應該相等嘅對角元素。喺任何情況下，設置

:  \mathbf{S}' = \begin{pmatrix} s_1 & 0 & 0 \\ 0 & s_2 & 0 \\ 0 & 0 & 0 \end{pmatrix} ,

其中 s_1, s_2 分別係 \mathbf{S} 最大同第二大奇異值。

最後，  \mathbf{E}' 係由下式畀出

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

矩陣 \mathbf{E}' 係演算法提供嘅、本質矩陣嘅估計結果。

## 歸一化算法
基本嘅八點算法原則上亦都可以攞來估計返本質矩陣 \mathbf{F}  。定義 \mathbf{F} 嘅約束係

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

其中 \mathbf{y}, \mathbf{y}' 係對應圖像坐標嘅齊次表示（暫時唔需要歸一化）。個意思即係可以構成一個矩陣 \mathbf{Y} ，攞求本質矩陣類似嘅方式求解方程

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

其中 \mathbf{f} 係 \mathbf{F} 個重組。透過遵循上面概述到嘅程序，即從一組八粒嘅匹配點可以確定 \mathbf{F} 。之不過，喺實踐中，噉樣產生嘅本質矩陣可能冇辦法攞來確定個對極約束。

### 困難
問題係噉樣產生嘅 \mathbf{Y} 經常係病態嘅（ill-conditioned）。理論上，  \mathbf{Y} 應該有一個等於零嘅奇異值，其他啲值嘅都係非零嘅。之不過，喺實踐中，一啲非零奇異值相對於啲較大嘅奇異值會顯得好細。如果使用八粒以上嘅對應點來構造 \mathbf{Y}  ，喺啲坐標僅衹係近似正確嘅情況下，可能冇一個明確定義（well-defined）嘅奇異值、可以識別得近似為零。因此，啲齊次線性方程組嘅嗰個解可能冇咁準而唔用得。

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

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

兩個 y_{1}, y_{2} \, 對於現代數碼相機，範圍喺 0 到 1000-2000 之間。呢個意思即係前兩個坐標 \mathbf{y} 係喺相較於第三個坐標要大得多嘅範圍內變化。另外，如果啲攞來構造 \mathbf{Y} 嘅圖像點位於圖像嘅一個相對細啲嘅區域，例如喺 (700,700) \pm (100,100) \, , 係噉向量 \mathbf{y} 嘅所有點又都多多少少指向相同嘅方向。結果係 \mathbf{Y} 會有一個好大嘅奇異值，其他啲奇異值嘅好細。

### 解決方案
作為呢個問題嘅解決方案，Hartley 提出應該根據以下原則，捉兩幅圖像中每幅圖像嘅坐標系獨立噉變換成新嘅坐標系。

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

呢個原理通常會導致兩幅圖像嘅每一幅都有唔同嘅坐標變換。結果係新嘅均勻圖像坐標 \mathbf{\bar y}, \mathbf{\bar y}' 由下式畀出：

:  \mathbf{\bar y} = \mathbf{T} \, \mathbf{y} 
:  \mathbf{\bar y}' = \mathbf{T}' \, \mathbf{y}' 

其中 \mathbf{T}, \mathbf{T}' 係轉換（平移同縮放）從舊到新變成標準化過嘅圖像坐標嘅。呢種歸一化衹取決於喺單幅圖像中使用到嘅圖像點，並且通常唔同於由歸一化過嘅相機產生嘅歸一化圖像坐標。

基於本質矩陣嘅對極約束，而今可以重寫過，寫成：

:  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} 

其中 \mathbf{\bar F} = ((\mathbf{T}')^{\mathrm T})^{-1} \, \mathbf{F} \, \mathbf{T}^{-1}  。個意思即係可以使用歸一化過嘅同質（homogeneous）圖像坐標 \mathbf{\bar y}, \mathbf{\bar y}' 嚟估計變換後嘅本質矩陣 \mathbf{\bar F} ，使用到上述嘅基本八點算法。

歸一化變換嘅目標係矩陣 \mathbf{\bar Y}  ，由歸一化過嘅圖像坐標構造而成，一般來講有好啲嘅條件數（condition number），好過 \mathbf{Y} 。個意思即係相較於 \mathbf{f} 對於 \mathbf{Y} 嚟講，個解 \mathbf{\bar f} 更加明確噉有定義到作爲齊次方程 \mathbf{\bar Y} \, \mathbf{\bar f} 嘅解。等 \mathbf{\bar f} 得到確定又重整成 \mathbf{\bar F} 之後，後者可以着反歸一化（de-normalized）畀出 \mathbf{F} ，根據下式：

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

一般來講，本質矩陣嘅呢種估計好過非標準化坐標嘅估計。

## 取少過八粒點
每副點對都貢獻一個約束方程畀 \mathbf{E} 裏便個元素 。因爲 \mathbf{E} 有五個自由度，因此只需要有五副點對就足夠確定 \mathbf{E} 。雖然從理論嘅角度來睇噉樣係可能嘅，之不過個實際實現都唔簡單，並且依賴於求解各種非線性方程。

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

## 睇埋

* 本質矩陣
* 基礎矩陣
* 三焦張量（trifocal tensor）

## 考

## 讀埋

* 

* 

*