RANSAC Line Fitting

1. 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$).

2. 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.

3. Step-by-Step Strategy

4. 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.

2. 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$.

3. Helper: distance from point to line

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

4. 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

5. 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$.

4. 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.

5. 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).