Introduction

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.

Try It

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.

<!-- RANSAC demo: canvas + controls -->
<div class="controls">
  <button id="btnRun" type="button">Run RANSAC</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
  <label class="toggle"><input type="checkbox" id="chkTrials"> Show all 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>Inlier
  <span class="dot outlier"></span>Outlier
  <span class="line-blue"></span>RANSAC fit
  <span class="line-gray"></span>Least squares
</div>

/* styles for the RANSAC demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// RANSAC line-fitting demo — vanilla JS, no imports
const W = 560, H = 320;
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const status = document.getElementById('status');
const chkTrials = document.getElementById('chkTrials');

// True hidden line: y = SLOPE * x + INTERCEPT (pixel coords)
const SLOPE = 0.35, INTERCEPT = 60;
const N_INLIER = 30, N_OUTLIER = 30;
const INLIER_NOISE = 18; // pixel noise on inliers
const THRESHOLD = 20;    // pixel distance threshold for inlier classification
const ITERATIONS = 50;

let pts = [], bestLine = null, lsLine = null, trialLines = [];

function randInt(a, b) { return Math.floor(Math.random() * (b - a + 1)) + a; }

// Generate inlier points near the true line plus random outliers.
function generatePoints() {
  pts = [];
  for (let i = 0; i < N_INLIER; i++) {
    const x = randInt(30, W - 30);
    const y = SLOPE * x + INTERCEPT + (Math.random() - 0.5) * 2 * INLIER_NOISE;
    pts.push({ x, y, inlier: true });
  }
  for (let i = 0; i < N_OUTLIER; i++) {
    pts.push({ x: randInt(20, W - 20), y: randInt(20, H - 20), inlier: false });
  }
}

// Fit a line through two points: y = m*x + b
function lineThroughTwo(p1, p2) {
  const m = (p2.y - p1.y) / (p2.x - p1.x + 1e-9);
  const b = p1.y - m * p1.x;
  return { m, b };
}

// Perpendicular distance from point p to line.
function distToLine(p, line) {
  // formula: |m*x - y + b| / sqrt(m^2 + 1)
  return Math.abs(line.m * p.x - p.y + line.b) / Math.sqrt(line.m * line.m + 1);
}

// Count how many points are within THRESHOLD of the line.
function countInliers(line) {
  return pts.filter(p => distToLine(p, line) < THRESHOLD).length;
}

// Ordinary least squares for comparison (not robust).
function leastSquares() {
  const n = pts.length;
  let sx = 0, sy = 0, sxy = 0, sx2 = 0;
  for (const p of pts) { sx += p.x; sy += p.y; sxy += p.x * p.y; sx2 += p.x * p.x; }
  const m = (n * sxy - sx * sy) / (n * sx2 - sx * sx + 1e-9);
  const b = (sy - m * sx) / n;
  return { m, b };
}

// Main RANSAC loop: sample two points, count inliers, keep best.
function runRANSAC() {
  bestLine = null; trialLines = [];
  let bestScore = -1;
  for (let iter = 0; iter < ITERATIONS; iter++) {
    const i1 = randInt(0, pts.length - 1);
    let i2 = randInt(0, pts.length - 1);
    while (i2 === i1) i2 = randInt(0, pts.length - 1);
    const line = lineThroughTwo(pts[i1], pts[i2]);
    const score = countInliers(line);
    trialLines.push({ line, score });
    if (score > bestScore) { bestScore = score; bestLine = line; }
  }
  lsLine = leastSquares();
  return bestScore;
}

// Draw an infinite line across the canvas.
function drawLine(line, color, dash = []) {
  const x0 = 0, x1 = W;
  const y0 = line.m * x0 + line.b;
  const y1 = line.m * x1 + line.b;
  ctx.save();
  ctx.strokeStyle = color;
  ctx.lineWidth = 2.5;
  ctx.setLineDash(dash);
  ctx.beginPath(); ctx.moveTo(x0, y0); ctx.lineTo(x1, y1); ctx.stroke();
  ctx.restore();
}

function drawScene() {
  ctx.clearRect(0, 0, W, H);
  if (chkTrials.checked && trialLines.length) {
    // Show faint candidate lines from each iteration.
    for (const t of trialLines) {
      const alpha = 0.06 + 0.1 * (t.score / pts.length);
      drawLine(t.line, `rgba(100,160,220,${alpha.toFixed(2)})`);
    }
  }
  if (lsLine) drawLine(lsLine, 'rgba(150,150,150,0.85)', [6, 4]);
  if (bestLine) drawLine(bestLine, '#1d6fa8');
  for (const p of pts) {
    const isInlierOfBest = bestLine && distToLine(p, bestLine) < THRESHOLD;
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fillStyle = isInlierOfBest ? '#1d6fa8' : '#e63946';
    ctx.fill();
  }
}

function init() {
  bestLine = null; lsLine = null; trialLines = [];
  generatePoints();
  status.textContent = '';
  drawScene();
}

document.getElementById('btnRun').addEventListener('click', () => {
  const score = runRANSAC();
  const pct = Math.round(100 * score / pts.length);
  status.textContent = i18nFmt('Done! Best consensus: %score% / %total% points (%pct% %).', { score, total: pts.length, pct });
  drawScene();
});
document.getElementById('btnReset').addEventListener('click', init);
chkTrials.addEventListener('change', drawScene);

init();
Result
Console

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.

The Real Complexity

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

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

k=log⁡(1−p)log⁡(1−wm)k = \frac{\log(1-p)}{\log(1-w^{m})}

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

k=log⁡0.01log⁡(1−0.25)≈16 iterationsk = \frac{\log 0.01}{\log(1 - 0.25)} \approx 16 \text{ iterations}

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

The catch: kk grows exponentially in the minimal sample size mm. For models that need many points (homographies need 4, fundamental matrices need 7) and low inlier ratios, kk 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/ransac/Content licensed under CC BY-NC 4.0.