本文為 Multiple View Geometry 第十一章 Computation of the Fundamental Matrix F 的筆記，介紹了計算 fundamental 矩陣的細節以及如何利用已知的 fundamental 矩陣來做 image rectification。
相關的前文可參考：
從 8-point algorithm 開始
利用式子 \(\mathbf{x}'^TF\mathbf{x}=0\) 可以得到一組解 F 的等式，而若將所有的式子重整後寫成 \(\mathbf{A}_{n \times 9}f=0\) 的代數式時至少要八個點，因此稱為 8-point 演算法。
8-point 演算法雖然簡單快速，但其忽略了一些 fundamental 矩陣的性質：
- Fundamental 矩陣的 rank 為二，left 與 right nullspace 分別為兩個 epipole。一個方便的解法是在解 SVD 時計算 \(F'=U\texttt{diag}(r,s,0)V^T\)，而 F' 必定為 singular，並且其 Frobenius norm 會最接近 F。
- 前文已經提過 fundamental 矩陣的自由度為七，因此其實只要七組對應點理論上即能求出解，但是若用上述的方法 A 矩陣將會是 \(7 \times 9\)，因此將會有兩組解 \(F_1\) 與 \(F_2\)。最後還是得利用行列式為零的限制帶入消去，而此時將會有三組可能的解。
- 一般來說 8-point algorithm 需要 normalized coordinates，但由於 F 的每一項並不是一樣重要，因此若要得到更正確的解必須考慮 F 的 covariance 矩陣，而上述的 SVD 解又無法找出此 covariance 矩陣的線性解，因此書中 11.3.1 節提到了一種迭代法來解 fundamental 矩陣。
- 到目前為止討論的方法都是為了最佳化 algebraic error，並沒有直觀的幾何意義。
考慮幾何距離的方法
一般來說考慮幾何距離的方法都是非線性的，更多細節可以參考前文的 Levenberg–Marquardt Method。書中建議的方法稱為 Gold Standard method，目的是最佳化 reprojection error：\(\sum_i d(\mathbf{x}_i, \hat{\mathbf{x}}_i)^2 + d(\mathbf{x}_i', \hat{\mathbf{x}}'_i)^2\)，其假設為 error 是高斯分布的 MLE。非線性的解通常需要好的初始值，而此初始值可由 8-point algorithm 的結果得到。
接下來要討論的是如何在非線性的方法實現 rank 為二的限制：
- Over-parametrization：利用 12 個參數組成 F： \(F=[\mathbf{t}]_{\times}M\)，由矩陣 \([\mathbf{t}]_{\times}\) 保證 F 的 rank 為二。
- Epipolar-parametrization：設計 F 並利用第三個 column 為第一與第二的線性相加，總共需要 8 個參數。
- Both epipoles as parameters：上面的方法的物理意義為使用一個 epipole，而也可以使用兩個 epipole 的限制來描述 F。
一個完整解出 fundamental 矩陣的演算法
這一段將綜合前面的內容，總結出一個自動解出 fundamental 矩陣的演算法。
- 找出對應的特徵點
- RANSAC 找出一組線性解，書中建議使用七個點的方法，因為其可以直接產生 rank 2 矩陣，並且跟八點法相比需要的樣本數只需一半。
- 利用非線性解來優化結果
- Guided matching：利用算出來的 fundamental 矩陣重新找出對應的特徵點
其中步驟 3 與 4 可重複進行直到結果收斂。
特殊情況與 degeneracies
- 若已知兩個視角只純移動的關係，則只要兩組對應點即可估計出 fundamental 矩陣。
- 若相機的 intrinsics 已知，將會變成計算 essential 矩陣。而除了行列式為零以外還多了 singular values 相同的限制，將有助於算出更理想的解。
- 儘管 epipolar geometry 描述了兩個點的關係，但兩個視角中的兩個線並無法產生 epipolar constraint。
- 當用七點法時，可能會有三組解，此為一個 degenerate 的情形。原因為需要九個參數來描述一個二維的 quadric，但當只有七個等式時將會有三種可能。在實務的 RANSAC 演算法中我們會選出 inlier 最多的那一組解。
- 若只有旋轉無平移，或是對應點都在同一個平面上，分別會形成 degenerate motion 與 degenerate structure 的情形。
Image Rectification
在前文 Triangulation 及 Rectification 已經提過了一種 rectification 的方法，而其假設是 intrinsics 矩陣已知。書中 11.12 節提到的方法是直接從 fundamental 矩陣來計算 rectification 的 homography 矩陣：
- 找出一個 homography 矩陣 H 使得 \(H\mathbf{e}\) 會在 point-at-infinity 上： \[ G=\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ -1/f & 0 & 1 \end{bmatrix} \\ G\mathbf{e} = [f, 0, 0]^T \\ H = GRT \]其假設特徵點 x 周圍只有平移與旋轉；T 為將 x 移至原點的位移，R 為 將 epipole \(\mathbf{e}\) 旋轉至 x 軸上使得旋轉後座標為 \([f, 0, 1]^T\)。
- 可以用線性的方法算出另一個對應的 homography 矩陣，細節請參考資料 [1]。
- Resample 兩張圖即完成 rectification 了。
- 參考資料 [2] 提出了另一種 rectification 的方法，並包含與此方法的比較。
沒有留言:
張貼留言