計算 structure：三維世界裡點的位置

本文為 Multiple View Geometry 第十二章 Structure Computation 的筆記，介紹了幾種在給定二維圖片上的對應點及相機矩陣 P 時，如何重建出此點在三維世界中的位置。

線性 triangulation

在實際的狀況中，二維世界裡的點 x 與 x' 兩者 back-projection 的光會因為 noise 而無法相交，也就是無法滿足 epipolar constraint \(\mathbf{x}'^T F \mathbf{x}=0\)。我們想要找的 triangulation 方法必須滿足相機類型的不變性，也就是 affine 或 projective transformation invariance，也就是說當 triangulation 方法 \(\tau\) 必須滿足對於變換 H 的條件： \[ \mathbf{X}=\tau(\mathbf{x}, \mathbf{x}', P, P') \\ \tau(\mathbf{x}, \mathbf{x}', P, P') = H^{-1}\tau(\mathbf{x}, \mathbf{x}', PH^{-1}, P'H^{-1}) \]一個很直觀的想法是在這兩條不相交的光上面找到與他們垂直的線段並取此線段的中點當成結果 \(\mathbf{X}\)，但這個解法並不滿足 transformation invariance 的條件。

線性 triangulation 的方法是用兩個式子：\(\mathbf{x}=P\mathbf{X}\) 與 \(\mathbf{x'}=P'\mathbf{X}\)，將他們移項以後寫成 \(A\mathbf{X}=\mathbf{0}\) 的形式。這個式子會與計算 homography 矩陣非常類似，請參考前文。第一種解法為 homogeneous method，也就是 DLT，利用 SVD 最小的 singular value 對應的特徵向量當成解。第二種方法為 inhomogeneous method，將解 \(\mathbf{X}\) 寫成 (X, Y, Z, 1) 的形式，但如前文所說這種方法當 X 很靠近 point at infinity 時會導致數值計算上的不穩定性。最後值得一提的是儘管這兩種方法都不是 projective invariant，只是 affine invariant，但實務上仍然可以得到可接受的解。

考慮 geometric cost function

考慮 geometric error 的方法我們在前文已經大致介紹過了。這種方法在假設 error 是高斯分布時的 Maximum Likelihood Estimates。而 Sampson Error 是此 geometric cost function 的 first order approximation。

最佳的解

書中的 12.5 節介紹了一種 close form 的最佳解。其大意是將 x 與 x' 經由轉換後分別會在 (0, 0, 1)，而兩個 epipole 分別在 (1, 0, f) 與 (1, 0, f') 之上。在此轉換後的座標設定之下，fundamental 矩陣的形式為： \[ F=\begin{bmatrix} ff'd & -f'c & -f'd\\ -fb & a & b\\ -fd & c & d \end{bmatrix} \]想要優化的 cost function 為點到 epipolar line 的距離平方：\(d(\mathbf{x}, \mathbf{l}(t))^2+d(\mathbf{x}', \mathbf{l}'(t))^2\)，這個 cost function 會是個 t 六維的多項式，因此在有實根的情況下會有三個最小值，其中最小的 t 即可解出直線上的點的位置，然後就可以找到 \(\hat{\mathbf{x}}\) 與 \(\hat{\mathbf{x}}'\) 滿足 \(\hat{\mathbf{x}}'^TF\hat{\mathbf{x}}=0\) 對應的 \(\hat{\mathbf{X}}\)。與迭代法相比這個最佳解可以找到 global minimum，而不是在不好的初始值之下得到 local minimum。