RANSAC: fitting a model despite outliers
Optional · supplementary note 9 of 10 for IP 12 · Feature Extraction. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.
Navigate: this page and this track: Navigate: this page and this track
On this page
- The Moore boundary-following procedure
- Slope chain codes
- Minimum-perimeter polygons in more detail
- The medial axis transform
- Computing shape numbers of a given order
- Moments of a 1-D boundary function
- Euler’s formula for polygonal networks
- Keypoint localization
- RANSAC: fitting a model despite outliers
- Learned features in more detail
Image Processing
Suppose you draw a straight line through a scatter of points, but some of the points are wrong by a mile. Averaging over everything drags the line toward the bad points. RANSAC (random sample consensus) [21] does the opposite: it guesses a line from a tiny random sample, counts how many of the other points agree with the guess, and keeps the guess with the most supporters.
Let the model need points to be determined exactly ( for a line). Repeat the following for trials:
- Draw points at random and fit the model to them.
- Compute every point’s residual (its distance to the model). A point is an inlier if its residual is at most the threshold ; the inliers form the consensus set.
- If this consensus set is the largest so far, remember it.
At the end, refit the model on all points of the best consensus set, because a fit from points alone is noisy. Outliers rarely agree with one another, so a sample that contains one usually gathers little support. How many trials are enough? A random sample is free of outliers with probability , so the chance that all samples are contaminated is . Asking this to be at most gives
where is the probability we want of drawing at least one outlier-free sample (for example 0.99), the fraction of inliers among the data, the sample size and the number of trials. For , and the formula gives 10.3, so 11 trials. With it gives 18.9 at and 168.2 at .
Code · Python · 20 lines
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)))The true line has slope 2 and intercept 1. Least squares, pulled by the 40 outliers, returns slope 1.52 and intercept 2.74. RANSAC returns slope 2.00 and intercept 1.05 from 65 inliers: the 60 genuine points plus 5 outliers that happened to fall within 1.0 of the line. The last line prints the trial count from the formula (10.3), well below the 100 allowed. ransac and its parameters min_samples, residual_threshold and max_trials are documented in [22].
RANSAC has limits. It needs a model that a small sample determines, because shrinks quickly as grows. It degrades when the inlier ratio is low (at and the formula asks for 4602.9 trials). The threshold must be tuned to the noise level: too small rejects good points, too large admits bad ones. It is randomized and offers a probabilistic guarantee only, not a certain one.
In this chapter’s matching script the data are SIFT matches and the model is a similarity transformation. A similarity has four parameters, so two correspondences already determine it; the snippet asks for min_samples=3, allows 500 trials and uses a 2-pixel threshold. In that run 483 of 484 matches are inliers, so is close to 1 and a few trials suffice. On real photo pairs is much lower and the trial budget matters.
References
- 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