2022年5月21日 星期六

分析 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 次即會終止。

沒有留言:

張貼留言