Feature Correspondence Filtering using RANSAC

1. Background Knowledge

RANSAC (Random Sample Consensus) is a robust estimation algorithm for fitting models to data contaminated by outliers, widely used in computer vision for tasks like homography estimation from feature correspondences (e.g., SIFT, ORB). In feature matching between images, inliers satisfy the geometric model (e.g., homography $H$ mapping points $\mathbf{x}_i \leftrightarrow$\mathbf{x}$_i'$ via $\mathbf{x}_i' \approx H$\mathbf{x}$_i$), while outliers (ratio $R_{outlier}$) do not due to mismatches.

Key prerequisites:

• Homography: 8 DOF matrix ($3 \times 3$) estimated from minimal subset $M=4$ point correspondences (homogeneous coordinates).
• Inlier ratio $\varepsilon = 1 - R_{outlier}$: Fraction of good matches.
• Success probability $p$: Confidence that at least one iteration yields a clean subset.

The core probability models assume independent random sampling from a pool with $\varepsilon$ inliers.

2. Algorithm Approach

Standard RANSAC for this problem:

1. Repeat $K$ iterations:

• Sample $M$ correspondences randomly.
• Fit model (e.g., solve for $H$ via DLT - Direct Linear Transform).
• Count inliers (points within distance threshold $t$ of model).

2. Select model with maximum inliers; refit on all inliers.

Theoretical sampling: Computes minimum $K$ iterations needed for probability $p$ of selecting one clean subset (all $M$ inliers), avoiding exhaustive search.

Variants (from literature): PROSAC (quality-guided sampling), USAC (preemptive scoring), but basic probabilistic RANSAC suffices here.

3. Step-by-Step Strategy

Inputs: $M$ (e.g., 4), $R_{outlier} \in [0,1)$, $p \in (0,1]$.

1. Compute inlier ratio: $\varepsilon = 1 - R_{outlier}$.
2. Clean subset probability: $P_{clean} = \varepsilon^M$ (binomial: all $M$ samples are inliers).
3. Iterations formula (1 - probability of all $K$ failures):

$$K = \frac{\log(1 - p)}{\log(1 - P_{clean})}$$

• Derivation: $P($\text{at least one success}$) = 1 - (1 - P_{clean})^K = p$.

4. Ceil to integer: $K = \lceil K \rceil$ (ensure $\geq$ required iterations).
5. Edge cases:

• If $\varepsilon = 1$, $P_{clean}=1$, $K=1$.
• If $\varepsilon^M \approx 0$, $K \to \infty$ (handle via max iterations or log bounds).
• Use math.ceil, math.log in code.

Python snippet:

import math

def ransac_iterations(M: int, R_outlier: float, p: float) -> int:
 epsilon = 1.0 - R_outlier
 if epsilon == 0:
 return float('inf') # or large number
 P_clean = epsilon ** M
 if P_clean == 0:
 return float('inf')
 K = math.log(1 - p) / math.log(1 - P_clean)
 return math.ceil(K)

4. Common Pitfalls

• Floating-point precision: $\log(1 - P_{clean})$ near 0 when $P_{clean} \approx 1$; use math.log1p(-P_clean) for accuracy.
• Division by zero: When $P_{clean} = 1$ ($\varepsilon=1$), denominator=0; return $K=1$.
• Negative log arg: Ensure $1-p > 0$, $1 - P_{clean} > 0$; validate inputs.
• Non-integer ceiling: Always ceil (e.g., 10.1 → 11) to guarantee probability.
• Assuming total correspondences $N$: Formula ignores $N$ (valid for large $N$); for small $N$, use hypergeometric but overkill here.
• Outlier ratio misinterpretation: $R_{outlier}$ is fraction, not count.

5. Time & Space Complexity

• Time: $O(1)$ per call (constant-time log/power operations). Full RANSAC: $O(K \cdot N \cdot M)$ where $N$ is total correspondences (model fit + inlier test per iteration).
• Space: $O(1)$ (scalar computations only).

This formulation ensures $p$-confidence in finding a clean sample, enabling robust model estimation even with 50-90% outliers typical in feature matching.