分析 2D Projective Transformation 與 RANSAC 演算法的細節

本文接續前文：完整分析 2D Projective Transformation 介紹估計 homography 矩陣時要注意的細節，以及如何與 RANSAC 演算法連結在一起。

Data normalization

由於 DLT 演算法在不同的輸入 scale 時會得到不同的結果，在實務上必須加上 isotropic scaling 的步驟：

1. 平移輸入點使其 centroid 在原點
2. Normalize 平移後的輸入點，使得平均至原點的距離為 \(\sqrt{2}\)
3. 若有兩張圖的話要分別進行 normalization
4. 做完 DLT 後再轉換回原本的 scale

非線性最佳化問題要考慮的細節

一般來說非線性最佳化雖然有機會得到更精準的答案，但其有一些限制：需要較長時間、需要好的初始值、有可能卡在 local minimum，以及不容易找到一個 stopping criterion。在設計一套非線性最佳化問題的解時我們另外還得考慮以下細節：

1. Cost function：像是在前文中討論過各種 cost function 的差異。
2. Parametrization：通常不建議使用 minimal parametrization，但也有時候用過多的 parameters 會導致無法順利滿足原始問題的條件。
   
3. Function specification：考慮 cost function 與 parameters 的對應關係。
   
4. Initialization：必須從好的起始點開始，像是先用 DLT 解出起始點再用非線性最佳化找出最好的 homography 矩陣。
   
5. Iteration：使用哪一種最佳化的演算法，請參考前面一系列介紹各種演算法的文章。

RANSAC (Random sample consensus)

RANSAC 為常見估計參數並且能處理 outlier 的演算法，可以參考維基百科。關於 RANSAC 需要考慮以下幾個問題：

如何訂出 distance threshold ？

假設 error 為標準差為 \(\sigma\) 的常態分布，若以 squared error 來看的話，squared error distance 會形成卡方分布（請參考維基百科）。一般來說為了界定 inlier 與 outlier，我們會取 p-value 為 0.05 的情形，並且使用卡方分布表來決定 distance threshold 為幾倍的 \(\sigma\)。比如說當估計一條直線時，其 codimension（可以想成 error 的自由度）為 1，因此會去查自由度為 1，p-value 為 0.05 時的卡方分布表得到 3.84，因此 distance threshold 即為 3.84 \(\sigma\)。而當計算 homography 矩陣時，其 codimension 為 2，而 trifocal tensor 的情況下其 codimension 為 3。

需要多少樣本數？需要重複跑多少次？

假設一個 dataset 包含 s 個樣本，每個樣本是 inlier 的機率為 \(w\)，而我們希望在跑 \(N\) 次後可以有 p 以上的成功機率，則我們可以寫出以下關係式： \[ 1-p=(1-w^s)^N \\ N = \frac{log(1-p)}{log(1-w^s)} \]通常我們會設定 p 為 0.99，因此若對於 dataset 有一些初步的了解即可套用此式子來決定需要跑多少次。

動態調整樣本數的演算法

當無法估計 inlier 的機率時，實務上可以用此演算法來決定要跑多少次：

• 設 N 的初始值為無限大，sample_count 的初始值為 0
• While N > sample_count：
• 選 sample_count 個樣本，計算 inlier 比例
• 利用當前的 inlier 機率來更新 N
• sample_count += 1
  
• 終止
  

舉個例子，當有一組 dataset 的 inlier 數目為 156，inlier 機率為 56% 時，用以上的演算法跑 43 次即會終止。