RANSAC Line Fitting

mediumFREERANSACFittingCV: Model Fitting and Optimization

Implement RANSAC for robust line fitting to 2D points with outliers. This task involves using the RANSAC algorithm to estimate the parameters of a line that best fits a set of 2D points, some of which may be outliers.

The RANSAC algorithm is a robust estimation technique used to fit models to data with outliers. It works by randomly selecting a minimum number of samples, fitting a model to these samples, and then counting the number of inliers, which are points that are within a certain threshold of the model. The process is repeated for a specified number of iterations, and the model with the most inliers is kept as the best fit. In the case of line fitting, the line can be represented by the equation $ax + by + c = 0$ , where $a^2 + b^2 = 1$ . The distance from a point $(x_0, y_0)$ to the line is given by $d = |ax_0 + by_0 + c|$ .

Here are the steps to follow:

Randomly select a minimum number of samples (2 points for a line)
Fit a line to these samples
Count the number of inliers (points within a threshold of the line)
Repeat for a specified number of iterations

d = |ax_0 + by_0 + c|

This technique is widely used in computer vision applications, such as image processing and feature detection.

Example

Input

points = [[0,0], [1,1], [2,2], [3,3], [10,0]]  # Last is outlier
threshold = 0.1
n_iterations = 100

Output

{'line': [0.7071, -0.7071, -0.0], 'inliers': 4}

Reasoning

Inputs: five 2D points, an inlier threshold of 0.1 (a perpendicular distance), and 100 trials, each taking the line through a random pair of points as a candidate.
A good pair: any two of [0,0], [1,1], [2,2], [3,3] give the line $x - y = 0$ . Its normal $(1, -1)$ has length $\sqrt{2}$ , so scaling to unit length gives $a = 0.7071$ , $b = -0.7071$ , $c = 0$ .
Scoring it: the four diagonal points have $d = 0$ . For [10,0], $d = |0.7071 \cdot 10 - 0.7071 \cdot 0| \approx 7.07$ , far above 0.1. Score: 4 inliers.
A bad pair: [0,0] with [10,0] gives the line $y = 0$ , which passes through only those 2 points. Score: 2. Since 6 of the 10 possible pairs are good, 100 trials almost surely find the best line.
Output: line is rounded to 4 decimal places and inliers is 4. Notice that $(a, b, c)$ and $(-a, -b, -c)$ are the same line, so $(-0.7071, 0.7071, 0)$ is equally correct; -0.0 is a rounded negative zero.

Constraints

points: List of [x, y] coordinates
threshold: Max distance to be considered inlier
n_iterations: Number of RANSAC iterations
Return: Dict with 'line' [a,b,c] and 'inliers' count

Learn this in

Model Fitting and OptimizationCV Study Plan NumPy & Data WranglingFoundations

More from CV: Model Fitting and Optimization

RANSAC Homography Estimationmedium RANSAC Line Fithard Line from Two Pointseasy Count Inlierseasy Weighted Least Squareshard

Concept primer

Background Knowledge

RANSAC (Random Sample Consensus) is a robust parameter estimation method designed to fit a model (here, a 2D line) when many data points are outliers. Instead of trying to fit all points at once (like least squares), RANSAC repeatedly samples small subsets, fits a candidate model, and then tests how many points agree with that model within a tolerance. The model with the largest consensus set (inliers) is chosen.

For line fitting in 2D, we use the implicit line form $ax + by + c = 0$ , normalized so that $a^2 + b^2 = 1$ . This makes the perpendicular distance from a point $(x_0, y_0)$ to the line simply $d = |ax_0 + by_0 + c|$ . With this distance metric and a threshold $\tau$ , we can decide whether each point is an inlier (distance ≤ $\tau$ ) or an outlier (distance > $\tau$ ).

Algorithm/Approach

General RANSAC pattern for line fitting:

Randomly sample the minimal set of points needed to define the model (2 points for a line).
Compute the candidate line parameters from those samples.
For that candidate line, count inliers: points whose distance to the line is below a chosen threshold.
Keep track of the best model: the one with the most inliers (and optionally best error on those inliers).
After a fixed number of iterations (or until a probabilistic stopping condition), refit the line using all inliers of the best model (e.g., with least squares).

This works because even with many outliers, random minimal samples will occasionally pick only inliers, yielding a good model that many points agree with.

Step-by-Step Strategy
Preliminaries

Input: list of 2D points $(x_i, y_i)$ .
Hyperparameters:
num_iterations (N): how many random trials.
distance_threshold ( $\tau$ ): max allowed distance to count as inlier.
Optional: min_inliers to accept a model.

Helper: fit a line from 2 points

Given two distinct points $(x_1,y_1)$ , $(x_2,y_2)$ :
Direction vector: $(dx, dy) = (x_2 - x_1, y_2 - y_1)$ .
Normal vector to line: $(a, b) = (dy, -dx)$ .
Normalize: $n = \sqrt{a^2 + b^2}$ , then $a \leftarrow a/n$ , $b \leftarrow b/n$ .
Compute $c$ so that the line goes through a point, e.g.:
$c = -(a x_1 + b y_1)$ .
Now $a^2 + b^2 = 1$ .

Helper: distance from point to line

For point $(x, y)$ and line $ax + by + c = 0$ :
$d = |ax + by + c|$ .

Main RANSAC loop

best_inlier_count = 0
best_model = None

for _ in range(num_iterations):
# 1. Random minimal sample
i, j = random distinct indices
line = fit_line(points[i], points[j]) # returns (a, b, c)

# 2. Count inliers
inliers = []
for p in points:
if distance(line, p) <= distance_threshold:
inliers.append(p)

# 3. Update best model
if len(inliers) > best_inlier_count:
best_inlier_count = len(inliers)
best_inliers = inliers
best_model = line

Optional refinement

Once you have best_inliers, refit a line using all these inliers with a more accurate method (e.g., least squares line fit) instead of just the two-point formula.
Return final line parameters $a, b, c$ .

Common Pitfalls

Not normalizing $a, b$ : then distance formula is wrong; ensure $a^2 + b^2 = 1$ .
Degenerate samples: two randomly chosen points may coincide or be extremely close; skip those.
Bad distance threshold:
Too small → almost no inliers; RANSAC fails.
Too large → outliers counted as inliers; model not robust.
Too few iterations: you might never pick an all-inlier minimal sample; increase num_iterations when outlier ratio is high.
Numerical stability: when points are very large or nearly vertical/horizontal, using the parametric slope form can be unstable; the implicit $ax + by + c = 0$ form is more robust.

Time & Space Complexity

Let $N$ = number of points, $K$ = number of iterations.
Each iteration:
Fitting a line from 2 points: $O(1)$ .
Scanning all points to count inliers: $O(N)$ .
Time complexity: $O(KN)$ .
Space complexity:
Storing points: $O(N)$ .
Temporary inlier lists per iteration can be reused; overall extra space: $O(N)$ in the worst case (if all points are inliers).

solution.py

Python 3.13

Test results