八點算法

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

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

共面性約束 

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

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

本質矩陣定義到嘅約束係

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

制定齊次線性方程 
透過

同同埋

約束亦都可以改寫成：

或者

其中有

同埋

即係， 以 9 維向量嘅形式表示本質矩陣，呢枚向量必須戥向量正交，可以睇作係表示向量嘅矩陣 .

每副對應嘅圖像點產生一枚向量 .一組 3D 點對應於一組向量，而且對於向量必須都滿足：

畀定足夠多線性無關嘅向量可以直接噉確定得到。擸齊所有向量作為矩陣嘅一列，噉實有：

個意思即係係個齊次線性方程嘅解。

求解方程 
解呢條方程嘅標準方法意思即係係嘅左奇異向量對應於一個零奇異值。假設至少有八粒線性無關向量着攞來構建，噉呢個奇異向量係唯一嘅，因此， 同埋都可以確定。

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

前提保證 .解決辦法係揀作為對應於最細奇異值嘅左奇異向量。呢個重新排過，整成一個矩陣，即畀出呢步嘅結果，記成 .

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

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

其中係正交矩陣，係包含奇異值嘅對角矩陣。喺理想情況下，對角線元素之一應該係零，或者者至少細過其他兩個應該相等嘅對角元素。喺任何情況下，設置

其中分別係最大同第二大奇異值。

最後， 係由下式畀出

矩陣係演算法提供嘅、本質矩陣嘅估計結果。

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

其中係對應圖像坐標嘅齊次表示。個意思即係可以構成一個矩陣，攞求本質矩陣類似嘅方式求解方程

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

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

原因 
Hartley 喺 1997 年嘅文章中解決唨呢個估計問題。佢對個問題嘅分析表明，個問題係由於均勻圖像坐標喺個空間中嘅分佈唔好。二維圖像坐標嘅典型均勻表示係

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

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

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

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

其中係轉換從舊到新變成標準化過嘅圖像坐標嘅。呢種歸一化衹取決於喺單幅圖像中使用到嘅圖像點，並且通常唔同於由歸一化過嘅相機產生嘅歸一化圖像坐標。

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

其中 。個意思即係可以使用歸一化過嘅同質圖像坐標嚟估計變換後嘅本質矩陣，使用到上述嘅基本八點算法。

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

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

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

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

本質矩陣
 基礎矩陣
 三焦張量

考

讀埋 

電腦視覺
演算法