RANSAC

Imagine you are trying to draw the best straight line through a scatter of points — but someone has secretly replaced half of them with random noise. Every classical method (least squares, linear regression) will be dragged sideways by those imposters. Yet the true line is still there, hidden inside the crowd.

RANSAC — Random Sample Consensus, introduced by Martin Fischler and Robert Bolles in 1981 — solves this with a beautifully simple loop: pick the smallest random subset of points needed to define a model, measure how many other points agree with it (the inliers), and remember the best consensus you have seen. Repeat many times, and with high probability you will have sampled a clean subset at least once.

The insight is almost philosophical: instead of trying to be robust to every bad point at once, bet that a small random draw will be clean, then verify globally. The algorithm does not even try to identify which points are noise — it just counts votes.

The canvas below has a hidden line with 50 % of the points replaced by random outliers (shown in red after the fit). Click Run RANSAC to watch the algorithm sample random pairs, count inliers, and converge on the true model.

<!-- {{c_html_desc}} -->
<div class="controls">
  <button id="btnRun" type="button">{{btn_run}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  <label class="toggle"><input type="checkbox" id="chkTrials"> {{lbl_trials}}</label>
</div>
<canvas id="cv" width="560" height="320"></canvas>
<div id="status" class="status"></div>
<div class="legend">
  <span class="dot inlier"></span>{{leg_inlier}}
  <span class="dot outlier"></span>{{leg_outlier}}
  <span class="line-blue"></span>{{leg_ransac}}
  <span class="line-gray"></span>{{leg_ls}}
</div>

/* {{c_css_desc}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui; padding: .42rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.toggle { font-size: .88rem; display: flex; align-items: center; gap: .3rem; cursor: pointer; user-select: none; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; display: block; max-width: 100%; background: #f8fafb; }
.status { font-size: .92rem; font-weight: 600; min-height: 1.4em; margin: .4rem 0; color: #0a7d33; }
.legend { display: flex; align-items: center; gap: .7rem; flex-wrap: wrap; font-size: .82rem; color: #555; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.dot.inlier { background: #1d6fa8; }
.dot.outlier { background: #e63946; }
.line-blue { display: inline-block; width: 24px; height: 3px; background: #1d6fa8; border-radius: 2px; }
.line-gray  { display: inline-block; width: 24px; height: 3px; background: #aaa; border-radius: 2px; border-top: 2px dashed #888; background: none; }

// Code not found

Notice that least-squares (the gray dashed line) is pulled badly off course by the outliers, while RANSAC (the blue line) recovers the true fit. Toggle Show all trials to see each sampled candidate line before the best one is selected.

RANSAC is not a single algorithm but a meta-algorithm: the inner step (fit a minimal sample, count inliers) runs in $O(n)$ per iteration. The key question is how many iterations $k$ you need.

If a fraction $w$ of the data are genuine inliers and you draw a minimal sample of size $m$ (two points for a line), then the probability that one sample is entirely clean is $w^{m}$. To guarantee that at least one of $k$ samples is clean with probability $p$ you need:

$$k = \frac{\log(1-p)}{\log(1-w^{m})}$$

For $w = 0.5$ (50 % inliers), $m = 2$ (line), and $p = 0.99$:

$$k = \frac{\log 0.01}{\log(1 - 0.25)} \approx 16 \text{ iterations}$$

Sixteen iterations — not thousands. The total cost is $O(k \cdot n)$, and $k$ grows only logarithmically with the desired confidence $p$.

The catch: $k$ grows exponentially in the minimal sample size $m$. For models that need many points (homographies need 4, fundamental matrices need 7) and low inlier ratios, $k$ can explode. Variants like PROSAC (prioritized sampling) and LO-RANSAC (local optimization) attack this, but the core trade-off remains: more complex models or dirtier data cost exponentially more samples.

Wherever sensors meet the real world, some fraction of observations will be wrong. RANSAC's robustness makes it a cornerstone of modern computer vision and beyond:

• Panorama stitching: matching keypoints between two photos produces many false matches. RANSAC fits a homography using only the true correspondences, enabling seamless panoramas in every phone camera app.
• 3D reconstruction (Structure from Motion): estimating camera poses from images requires fitting the fundamental or essential matrix — a task overwhelmed by mismatched feature points without RANSAC.
• Autonomous driving and LiDAR: fitting ground planes, detecting lane lines, and registering point clouds all rely on RANSAC-style loops to ignore sensor noise and reflections.
• Medical imaging: aligning organ surfaces or MRI slices uses robust fitting to ignore misregistered patches.
• Astronomy: fitting orbits to telescope observations, where a fraction of readings are corrupted by atmospheric distortion.

RANSAC pairs naturally with feature detectors like SIFT and optimization methods like gradient descent. Its simplicity makes it easy to combine with almost any model class.

RANSAC turns a seemingly hopeless task — finding structure inside heavily corrupted data — into a probabilistic near-certainty through sheer repetition. Pick a tiny random sample, count who agrees, keep the best score, repeat. With enough trials the true model emerges, even when most of the data is lying.

The deeper lesson is about consensus over correctness: you never need to know which points are bad. You only need to ask, over and over, whether a randomly chosen few happen to agree — and trust that the majority will eventually speak loudly enough to be heard above the noise.