Full search page →

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

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 ss points to be determined exactly (s=2s = 2 for a line). Repeat the following for NN trials:

  1. Draw ss points at random and fit the model to them.
  2. Compute every point’s residual (its distance to the model). A point is an inlier if its residual is at most the threshold tt; the inliers form the consensus set.
  3. 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 ss 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 wsw^s, so the chance that all NN samples are contaminated is (1−ws)N(1 - w^s)^N. Asking this to be at most 1−p1 - p gives

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

where pp is the probability we want of drawing at least one outlier-free sample (for example 0.99), ww the fraction of inliers among the data, ss the sample size and NN the number of trials. For p=0.99p = 0.99, s=2s = 2 and w=0.6w = 0.6 the formula gives 10.3, so 11 trials. With s=3s = 3 it gives 18.9 at w=0.6w = 0.6 and 168.2 at w=0.3w = 0.3.

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 wsw^s shrinks quickly as ss grows. It degrades when the inlier ratio is low (at w=0.1w = 0.1 and s=3s = 3 the formula asks for 4602.9 trials). The threshold tt 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 ww is close to 1 and a few trials suffice. On real photo pairs ww is much lower and the trial budget matters.

References

  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