完整分析 2D Projective Transformation（一）

本文為 Multiple View Geometry 第四章 Estimation - 2D Projective Transformation 的筆記。

從 Direct Linear Transformation (DLT) 談起

假設 2D 圖片上的兩個點 \(\mathbf{x_i} = (x_i, y_i, w_i)\) 與 \(\mathbf{x_i'} = (x_i', y_i', w_i')\)，則想要解的 homography 矩陣關係式為 \(\mathbf{x_i'} = H \mathbf{x_i}\)，經由外積整理之後可以得到以下關係式： \[ \begin{bmatrix} \mathbf{0}^T & -w_i' \mathbf{x_i}^T & y_i' \mathbf{x_i}^T\\ w_i' \mathbf{x_i}^T & \mathbf{0}^T & -x_i' \mathbf{x_i}^T\\ -y_i' \mathbf{x_i}^T & x_i' \mathbf{x_i}^T & \mathbf{0}^T \end{bmatrix}_{3 \times 9} \begin{bmatrix} \mathbf{h}^1\\ \mathbf{h}^2\\ \mathbf{h}^3 \end{bmatrix}_{9 \times 1} = \mathbf{0}_{3 \times 1} \]第三個 row 為第一與第二個 row 的 linear combination，所以真正能用的只有前兩個 row。由於 homography 矩陣為 up-to-scale，也就是說自由度為 8，因此只要四個點就能解出來此 homography 矩陣。

Over-determined solution

在有更多點的情況下搭配 SVD 解中對應最小的 singular value 的向量即為解 \(\mathbf{h}\)。細節可以參考前文：線性系統的最小平方解。

Inhomogeneous solution

在前文：利用 Homography 矩陣描述兩張圖片的變換關係之中，我們提到可以假設 \(h_9\) 為 1，但在某些情況下萬一真正的 \(h_9\) 很靠近 0 時會使得結果不穩定，因此實務上不推薦這種解法。

Degenerate 以及點與線的等價解

在有三個點共線的情況下為 degenerate 的情形，無法求出唯一解。另外在二維空間中點與線是等價的表示概念，因此使用四個線的變換關係也能求出 homography 矩陣。另外用一個點與三個線或三個點與一個線都能求出 homography 矩陣，但是兩個點與兩條線卻不行。

考慮以上兩條線與兩個點的例子，其與五條線中有四條線在同一個點交會，或五個點中有四個點共線等價，因此為 degenerate 的情形。

不同的 cost function

Algebraic distance

用上述的 DLT 演算法最佳化的是 algebraic distance：\[d_{alg}(\mathbf{x}_i', H\mathbf{x}_i)^2=\left \| \epsilon _i \right \|^2=\left \| A_i\mathbf{h} \right \|^2\]這個 cost function 的問題是其不帶有幾何或統計上的意義，但實務上來講搭配適當的 normalization 時使用 algebraic distance 仍然可以得到不錯的結果；另外一種常用的方法是利用 algebraic distance 當 cost function 求出初始值，再用其他的 non-linear optimization 方法更優化結果。

Transfer error

首先假設在第一張圖片中的點我們有辦法取得沒有誤差的點 \(\bar{\mathbf{x}}\)(例如在 calibration 過程中有辦法取得精準的 feature point)，我們可以計算以下 transfer error：\[\sum_i d(\mathbf{x}_i', H\mathbf{\bar{x}}_i)^2\]在一般實務上我們可以計算 symmetric transfer error：\[\sum_i d(\mathbf{x}_i,H^{-1}\mathbf{x}_i')^2+d(\mathbf{x}_i',H\mathbf{x}_i)^2\]

Reprojection error

另一種想法是計算 reprojection error，也就是找到一個 homography 矩陣使得 \(\mathbf{\hat{x}}_i\) 與 \(\mathbf{\hat{x}}'_i\) 與觀察到的點 \(\mathbf{x}_i\)、 \(\mathbf{x}'_i\) 的距離最小，也就是：\[\sum_i d(\mathbf{x}_i, \hat{\mathbf{x}}_i)^2 + d(\mathbf{x}_i', \hat{\mathbf{x}}_i')^2\ subject\ to\ \mathbf{\hat{x}}_i'= H\mathbf{\mathbf{\hat{x}}}_i\]下圖（Marc Pollefeys 的投影片）解釋了 symmetric transfer error 與 reprojection error 的關係：

Sampson error

在實務上計算 reprojection error 相當麻煩，必須利用非線性最佳化來求解，而 Sampson error 即為 reprojection error 的 first-order 線性近似。關於 Sampson error 的細節請參考前文：解釋 Sampson Distance。

Cost function 與 Maximum Likelihood Estimation 的關係

現在假設觀測到的點 \(\mathbf{x}_i\) 是由 \((\bar{\mathbf{x}}_i,\sigma)\) 產生的高斯分布，則 homography 矩陣對應到兩張圖的 error probability density function 為：\[Pr(\{\mathbf{x}_i, \mathbf{x}_i'\}|H,\{\bar{\mathbf{x}}_i\})=\prod_i(\frac{1}{2 \pi \sigma^2})exp(-\frac{d(\mathbf{x}_i, \bar{\mathbf{x}}_i)^2+d(\mathbf{x}_i',H\mathbf{\bar{x}}_i')^2}{2 \sigma^2})\]而上式的 MLE 解即為 reprojection error。