RANSAC Robust Line Fitting (2D)

Point Scatter

Outlier fraction 35%

Inlier scatter (noise σ) 0.08

RANSAC

Inlier distance threshold 0.18

Iterations / second 4

Live State

Iterations run

Best inliers

0 / 0

Inlier ratio w

Accuracy vs truth

—

Iterations needed for 99% confidence, k = ⌈ln(1−P) / ln(1−w²)⌉

—

How it works

RANSAC (RANdom SAmple Consensus) is the algorithm computer-vision pipelines use to fit a model when the data is contaminated with gross outliers — mismatched keypoints, reflections, moving objects — that a least-squares fit would be dragged off course by. Here the model is a 2D line (the CV analogue of fitting an epipolar line, a lane boundary, or a horizon from noisy feature points), the minimal case where only s = 2 points fix the model instead of 3:

repeat k times:
  1. sample s=2 points at random from all N
  2. fit the exact line through them:
       n = ⟂(p2−p1) / |p2−p1|,  d = −n·p1
  3. count inliers: points p where |n·p + d| < τ
  4. keep this model if its inlier count is the
     best seen so far
return the line with the largest consensus set

Because only 2 points are needed to define a line, a model built from two real on-line points is exact — no averaging with outliers. Across many random trials, models built from all-inlier pairs dominate because they alone explain a large, consistent fraction of the data. The number of trials needed to be reasonably sure of drawing at least one clean pair, with confidence P and true inlier ratio w, is:

k = ⌈ ln(1 − P) / ln(1 − w^s) ⌉,  s = 2 here

With the same inlier ratio, the 2D line case needs fewer trials than the 3D plane case (s=3) for the same confidence, because w² > w³ for 0<w<1 — a smaller minimal sample means a clean draw is easier to hit.

Outlier fraction — how much of the scatter is pure noise, unrelated to the line.
Inlier scatter σ — how far real on-line points wander off the true line (sensor/measurement noise).
Distance threshold τ — how close a point must be to a candidate line to count as an inlier; too tight rejects real points, too loose lets outliers in.
Run / Step — draws random pairs, fits, scores, and keeps the best model found so far; watch the blue line and the green inlier set converge onto the true line.

Real-world relevance: OpenCV's findHomography and findFundamentalMat, lane-line detection, horizon estimation, and 2D feature-match filtering all run this exact sample → fit → score → keep-best loop, just with a 2-point minimal model instead of a 3-point one.

Inlier (current best model) Outlier (current best model) Current random pair Best-fit line