完整搜尋頁面 →

RANSAC:在有離群值時擬合模型

選讀・IP 12・特徵擷取 的補充資料(第 9/10 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。

導覽:本頁與本系列: 導覽:本頁與本系列

想像你要在一堆點之間畫一條直線,但其中有些點錯得離譜。把所有點一視同仁地平均,直線會被壞點拉偏。RANSAC(random sample consensus,隨機取樣一致)[21] 的做法正好相反:先用一小撮隨機取出的點猜一條線,數一數其他點有多少同意這個猜測,最後留下支持者最多的那一個。

假設模型需要 ss 個點才能唯一決定(直線的 s=2s = 2)。重複以下步驟 NN 次:

  1. 隨機抽出 ss 個點,並用它們擬合模型。
  2. 計算每個點的殘差(residual,即到模型的距離)。殘差不超過門檻 tt 的點稱為內點(inlier),所有內點構成「共識集合」(consensus set)。
  3. 若這個共識集合是目前最大的,就記下來。

最後,用最佳共識集合中的所有點重新擬合一次模型,因為只靠 ss 個點得到的擬合含有較多雜訊。離群值(outlier)彼此很少一致,所以含有離群值的樣本通常得不到什麼支持。那要試幾次才夠?一組隨機樣本不含離群值的機率是 wsw^s,因此 NN 組樣本全都被汙染的機率是 (1−ws)N(1 - w^s)^N。要求這個機率不超過 1−p1 - p,得到

N≥log⁡(1−p)log⁡(1−ws),N \ge \frac{\log(1 - p)}{\log\left(1 - w^{s}\right)},

其中 pp 是我們希望至少抽到一組不含離群值樣本的機率(例如 0.99),ww 是資料中內點所占的比例,ss 是樣本大小,NN 是試驗次數。當 p=0.99p = 0.99、s=2s = 2、w=0.6w = 0.6 時,公式得到 10.3,也就是 11 次。若 s=3s = 3,w=0.6w = 0.6 時得到 18.9,w=0.3w = 0.3 時得到 168.2。

程式碼 · Python · 20 行
import numpy as np
from skimage.measure import LineModelND, ransac

rng = np.random.default_rng(0)
x = rng.uniform(0, 10, 100)
y = 2 * x + 1 + rng.normal(0, 0.3, 100)          # 100 points near y = 2x + 1
y[:40] = rng.uniform(-10, 30, 40)                # replace 40 of them by gross outliers
pts = np.column_stack([x, y])

slope, intercept = np.polyfit(x, y, 1)           # ordinary least squares
print("least squares : slope %.2f, intercept %.2f" % (slope, intercept))

model, inliers = ransac(pts, LineModelND, min_samples=2,
                        residual_threshold=1.0, max_trials=100, rng=0)
x_in, y_in = pts[inliers].T
slope, intercept = np.polyfit(x_in, y_in, 1)     # refit on all inliers
print("RANSAC        : slope %.2f, intercept %.2f, %d inliers" % (slope, intercept, inliers.sum()))

w, s, p = 0.6, 2, 0.99
print("trials needed : %.1f" % (np.log(1 - p) / np.log(1 - w**s)))

真實的直線斜率為 2、截距為 1。最小平方法被 40 個離群值拉偏,得到斜率 1.52、截距 2.74。RANSAC 則從 65 個內點得到斜率 2.00、截距 1.05:這 65 個點包含 60 個真正的點,加上 5 個剛好落在直線 1.0 範圍內的離群值。最後一行印出由公式算出的試驗次數(10.3),遠低於允許的 100 次。ransac 及其參數 min_samples、residual_threshold、max_trials 的說明見 [22]。

RANSAC 有其限制。模型必須能由很小的樣本決定,因為 ss 一變大,wsw^s 就迅速變小。內點比例很低時它會變得吃力(w=0.1w = 0.1、s=3s = 3 時,公式要求 4602.9 次試驗)。門檻 tt 必須配合雜訊程度調整:太小會排除好點,太大會收進壞點。它是隨機演算法,只提供機率性的保證,而非確定的保證。

在本章的配對程式中,資料是 SIFT 配對,模型是相似轉換(similarity transformation)。相似轉換有四個參數,所以兩組對應點就足以決定它;程式碼設定 min_samples=3、最多 500 次試驗、門檻 2 像素。在那次執行中,484 個配對有 483 個是內點,ww 接近 1,只需要少數幾次試驗。真實的照片配對 ww 低得多,試驗次數的預算就變得重要。

參考文獻

  1. R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 12. publisher page
  2. M.-K. Hu, “Visual pattern recognition by moment invariants,” IRE Transactions on Information Theory, vol. 8, no. 2, pp. 179–187, 1962. doi
  3. R. M. Haralick, K. Shanmugam, and I. Dinstein, “Textural features for image classification,” IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-3, no. 6, pp. 610–621, 1973. doi
  4. C. Harris and M. Stephens, “A combined corner and edge detector,” in Proc. Alvey Vision Conference, pp. 23.1–23.6, 1988. doi
  5. J. Matas, O. Chum, M. Urban, and T. Pajdla, “Robust wide-baseline stereo from maximally stable extremal regions,” Image and Vision Computing, vol. 22, no. 10, pp. 761–767, 2004. doi
  6. D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, 2004. doi
  7. H. Bay, A. Ess, T. Tuytelaars, and L. Van Gool, “Speeded-up robust features (SURF),” Computer Vision and Image Understanding, vol. 110, no. 3, pp. 346–359, 2008. doi
  8. E. Rublee, V. Rabaud, K. Konolige, and G. Bradski, “ORB: An efficient alternative to SIFT or SURF,” in Proc. IEEE International Conference on Computer Vision (ICCV), pp. 2564–2571, 2011. doi
  9. D. Zhang and G. Lu, “Review of shape representation and description techniques,” Pattern Recognition, vol. 37, no. 1, pp. 1–19, 2004. doi
  10. T. Tuytelaars and K. Mikolajczyk, “Local invariant feature detectors: A survey,” Foundations and Trends in Computer Graphics and Vision, vol. 3, no. 3, pp. 177–280, 2008. doi
  11. L. Liu, J. Chen, P. Fieguth, G. Zhao, R. Chellappa, and M. Pietikäinen, “From BoW to CNN: Two decades of texture representation for texture classification,” International Journal of Computer Vision, vol. 127, pp. 74–109, 2019. arXiv
  12. J. Ma, X. Jiang, A. Fan, J. Jiang, and J. Yan, “Image matching from handcrafted to deep features: A survey,” International Journal of Computer Vision, vol. 129, pp. 23–79, 2021. doi
  13. Y. Jin, D. Mishkin, A. Mishchuk, J. Matas, P. Fua, K. M. Yi, and E. Trulls, “Image matching across wide baselines: From paper to practice,” International Journal of Computer Vision, 2021. doi · arXiv
  14. D. DeTone, T. Malisiewicz, and A. Rabinovich, “SuperPoint: Self-supervised interest point detection and description,” arXiv:1712.07629, 2017. arXiv
  15. P.-E. Sarlin, D. DeTone, T. Malisiewicz, and A. Rabinovich, “SuperGlue: Learning feature matching with graph neural networks,” arXiv:1911.11763, 2019. arXiv
  16. M. J. Tyszkiewicz, P. Fua, and E. Trulls, “DISK: Learning local features with policy gradient,” arXiv:2006.13566, 2020. arXiv
  17. J. Sun, Z. Shen, Y. Wang, H. Bao, and X. Zhou, “LoFTR: Detector-free local feature matching with Transformers,” arXiv:2104.00680, 2021. arXiv
  18. P. Lindenberger, P.-E. Sarlin, and M. Pollefeys, “LightGlue: Local feature matching at light speed,” arXiv:2306.13643, 2023. arXiv
  19. M. Oquab, T. Darcet, T. Moutakanni, et al., “DINOv2: Learning robust visual features without supervision,” arXiv:2304.07193, 2023. arXiv
  20. J. Edstedt, Q. Sun, G. Bökman, M. Wadenbäck, and M. Felsberg, “RoMa: Robust dense feature matching,” in Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2024. arXiv
  21. M. A. Fischler and R. C. Bolles, “Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography,” Communications of the ACM, vol. 24, no. 6, pp. 381–395, 1981. doi
  22. scikit-image contributors, “skimage.measure.ransac,” scikit-image 0.26 documentation (API reference). docs