RANSAC:在有離群值時擬合模型
選讀・IP 12・特徵擷取 的補充資料(第 9/10 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。
導覽:本頁與本系列: 導覽:本頁與本系列
想像你要在一堆點之間畫一條直線,但其中有些點錯得離譜。把所有點一視同仁地平均,直線會被壞點拉偏。RANSAC(random sample consensus,隨機取樣一致)[21] 的做法正好相反:先用一小撮隨機取出的點猜一條線,數一數其他點有多少同意這個猜測,最後留下支持者最多的那一個。
假設模型需要 個點才能唯一決定(直線的 )。重複以下步驟 次:
- 隨機抽出 個點,並用它們擬合模型。
- 計算每個點的殘差(residual,即到模型的距離)。殘差不超過門檻 的點稱為內點(inlier),所有內點構成「共識集合」(consensus set)。
- 若這個共識集合是目前最大的,就記下來。
最後,用最佳共識集合中的所有點重新擬合一次模型,因為只靠 個點得到的擬合含有較多雜訊。離群值(outlier)彼此很少一致,所以含有離群值的樣本通常得不到什麼支持。那要試幾次才夠?一組隨機樣本不含離群值的機率是 ,因此 組樣本全都被汙染的機率是 。要求這個機率不超過 ,得到
其中 是我們希望至少抽到一組不含離群值樣本的機率(例如 0.99), 是資料中內點所占的比例, 是樣本大小, 是試驗次數。當 、、 時,公式得到 10.3,也就是 11 次。若 , 時得到 18.9, 時得到 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 有其限制。模型必須能由很小的樣本決定,因為 一變大, 就迅速變小。內點比例很低時它會變得吃力(、 時,公式要求 4602.9 次試驗)。門檻 必須配合雜訊程度調整:太小會排除好點,太大會收進壞點。它是隨機演算法,只提供機率性的保證,而非確定的保證。
在本章的配對程式中,資料是 SIFT 配對,模型是相似轉換(similarity transformation)。相似轉換有四個參數,所以兩組對應點就足以決定它;程式碼設定 min_samples=3、最多 500 次試驗、門檻 2 像素。在那次執行中,484 個配對有 483 個是內點, 接近 1,只需要少數幾次試驗。真實的照片配對 低得多,試驗次數的預算就變得重要。
參考文獻
- R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 12. publisher page
- M.-K. Hu, “Visual pattern recognition by moment invariants,” IRE Transactions on Information Theory, vol. 8, no. 2, pp. 179–187, 1962. doi
- 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
- C. Harris and M. Stephens, “A combined corner and edge detector,” in Proc. Alvey Vision Conference, pp. 23.1–23.6, 1988. doi
- 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
- D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, 2004. doi
- 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
- 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
- D. Zhang and G. Lu, “Review of shape representation and description techniques,” Pattern Recognition, vol. 37, no. 1, pp. 1–19, 2004. doi
- 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
- 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
- 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
- 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
- D. DeTone, T. Malisiewicz, and A. Rabinovich, “SuperPoint: Self-supervised interest point detection and description,” arXiv:1712.07629, 2017. arXiv
- P.-E. Sarlin, D. DeTone, T. Malisiewicz, and A. Rabinovich, “SuperGlue: Learning feature matching with graph neural networks,” arXiv:1911.11763, 2019. arXiv
- M. J. Tyszkiewicz, P. Fua, and E. Trulls, “DISK: Learning local features with policy gradient,” arXiv:2006.13566, 2020. arXiv
- J. Sun, Z. Shen, Y. Wang, H. Bao, and X. Zhou, “LoFTR: Detector-free local feature matching with Transformers,” arXiv:2104.00680, 2021. arXiv
- P. Lindenberger, P.-E. Sarlin, and M. Pollefeys, “LightGlue: Local feature matching at light speed,” arXiv:2306.13643, 2023. arXiv
- M. Oquab, T. Darcet, T. Moutakanni, et al., “DINOv2: Learning robust visual features without supervision,” arXiv:2304.07193, 2023. arXiv
- 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
- 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
- scikit-image contributors, “skimage.measure.ransac,” scikit-image 0.26 documentation (API reference). docs