Feature matching and robust estimation

Features and descriptors become useful when they are matched: the same physical point found in two images, or in an image and a stored model. Matches let a robot compute how the camera moved, where a known object sits, how two images align, or how far away a point is. But matching is error-prone. Repeated textures such as shelving, tiles and brickwork produce many similar descriptors, and moving people, reflections and occlusions add matches that obey no consistent geometry. Even a good matcher typically returns 20 % to 50 % wrong matches in a cluttered robot scene, and a single wrong match can wreck an ordinary least-squares fit. This lesson covers how to produce candidate matches and how to estimate geometry robustly in spite of the outliers among them, with RANSAC as the central tool.

Producing candidate matches

The simplest matcher is brute force: for each descriptor in image A, compute its distance to every descriptor in image B and take the nearest. With n features in each image this costs \( n^2 \) distance computations, about a million for 1000 features, which is fine for binary descriptors on a modern CPU but slow for 128-dimensional SIFT vectors at video rates. Approximate nearest-neighbor methods such as k-d trees and the FLANN library find near-best matches much faster with little loss.

Nearest neighbor alone accepts too many bad matches, because every feature has some nearest neighbor even if its true partner is not in the other image. Two filters remove most of them.

• The ratio test (Lowe, 2004): compare the distance to the nearest neighbor \( d_1 \) with the distance to the second nearest \( d_2 \), and accept the match only if \( d_1/d_2 < \tau \), with τ typically 0.7 to 0.8. A genuine match is usually much closer than any alternative; an ambiguous feature on a repeated pattern has two near-equal candidates and is rejected.
• Mutual consistency (cross-checking): accept a match from A to B only if B's best match back is the same feature in A.

After these filters the surviving matches are mostly correct, but not all, and the remaining errors are exactly the ones that look plausible. Geometry has to do the rest.

Geometric models that matches must obey

Correct matches between two images are not independent: they all obey one geometric relationship determined by the scene and the camera motion. Which relationship depends on the situation.

• A homography H (3 × 3, 8 degrees of freedom) relates two views of a plane, such as a floor, a wall, a shelf front, a printed marker or a table top, or two views from a camera that only rotated. Points map as \( \lambda \tilde{\mathbf{u}}' = H \tilde{\mathbf{u}} \).
• The fundamental matrix F (3 × 3, 7 degrees of freedom) relates two views of a general 3-D scene by \( \tilde{\mathbf{u}}'^{\mathsf{T}} F \tilde{\mathbf{u}} = 0 \); with calibrated cameras it becomes the essential matrix E. Lesson 6 develops this epipolar geometry.
• A rigid transform relates a 3-D model to 3-D measurements, and the perspective-n-point problem relates known 3-D points to their 2-D images (lesson 11).

Each model can be estimated from a small minimal set of matches: four point pairs for a homography, eight (or seven, or five for the calibrated essential matrix) for epipolar geometry, three for a rigid 3-D transform. That minimal set size is what makes RANSAC work.

RANSAC

Random sample consensus, introduced by Fischler and Bolles in 1981 for exactly this kind of problem, inverts the usual approach to fitting. Instead of fitting all the data and hoping outliers average out, it fits many tiny subsets and keeps the model that most of the data agree with.

1. Randomly choose a minimal set of s matches (s = 4 for a homography).

2. Fit the model to those s matches exactly.

3. Count the inliers: matches whose error under this model is below a threshold, such as a reprojection distance of 2 pixels.

4. Repeat for N iterations and keep the model with the most inliers.

5. Refit the model to all its inliers by least squares, which averages out noise.

The method succeeds as soon as one sample happens to contain only inliers. If a fraction w of matches are inliers, a random sample of s is all-inlier with probability \( w^s \), so the probability that N samples all fail is \( (1 - w^s)^N \). Setting that equal to \( 1 - p \), for a desired success probability p, gives the number of iterations:

Because the inlier ratio is usually unknown in advance, implementations adapt N as they go: they start with a pessimistic guess and recompute N from the best inlier ratio found so far, stopping early when a good model appears. The inlier threshold should match the expected measurement noise, typically two to three times the standard deviation of keypoint location error.

import numpy as np
rng = np.random.default_rng(3)

def fit_h(a, b):
    """Homography from >= 4 point pairs by DLT (a, b are N x 2)."""
    rows = []
    for (x, y), (u, v) in zip(a, b):
        rows.append([x, y, 1, 0, 0, 0, -u * x, -u * y, -u])
        rows.append([0, 0, 0, x, y, 1, -v * x, -v * y, -v])
    H = np.linalg.svd(np.array(rows))[2][-1].reshape(3, 3)
    return H / H[2, 2]

def apply_h(H, a):
    p = np.hstack([a, np.ones((len(a), 1))]) @ H.T
    return p[:, :2] / p[:, 2:]

H_true = np.array([[1.10, 0.05, 30.0], [-0.03, 0.95, 12.0], [2e-4, 1e-4, 1.0]])
n_in, n_out = 120, 80
a = rng.uniform(0, 640, (n_in + n_out, 2))
b = apply_h(H_true, a) + rng.normal(0, 0.7, a.shape)        # 0.7 px noise
b[n_in:] = rng.uniform(0, 640, (n_out, 2))                  # 40 % outliers

# plain least squares on everything
H_ls = fit_h(a, b)

# RANSAC
best = np.zeros(len(a), bool)
for it in range(500):
    idx = rng.choice(len(a), 4, replace=False)
    H = fit_h(a[idx], b[idx])
    err = np.linalg.norm(apply_h(H, a) - b, axis=1)
    inl = err < 2.0
    if inl.sum() > best.sum():
        best = inl
H_r = fit_h(a[best], b[best])

test = rng.uniform(0, 640, (200, 2))
for name, H in [("least squares", H_ls), ("RANSAC", H_r)]:
    e = np.linalg.norm(apply_h(H, test) - apply_h(H_true, test), axis=1)
    print("%-13s mean error on fresh points: %7.2f px" % (name, e.mean()))
print("RANSAC inliers: %d of %d (true inliers %d)" % (best.sum(), len(a), n_in))

least squares mean error on fresh points: 4428.19 px
RANSAC        mean error on fresh points:    0.32 px
RANSAC inliers: 119 of 200 (true inliers 120)

Homographies in robot practice

Planes are everywhere in built environments, and homographies exploit them. A robot can map a floor-facing camera's image onto a top-down 'bird's-eye' view by computing the homography between the image and the ground plane from four known floor points, a standard trick for mobile robots and lane detection. Image stitching for inspection or mapping aligns overlapping views of a flat surface or views from a camera that rotates about its center. And a homography between a known planar object, such as a printed label or the face of a box, and its image can be decomposed into the camera's rotation and translation relative to that plane, given the intrinsics.

Beyond basic RANSAC

Many refinements exist. PROSAC samples the best-ranked matches first, often finding a good model in a handful of iterations. MLESAC and MSAC score models by the total error of inliers rather than just counting them, which separates models with similar inlier counts. Local optimization (LO-RANSAC) refits each promising model to its inliers before counting again. MAGSAC avoids choosing a single threshold by marginalizing over a range. For very high outlier rates, graduated non-convexity and robust cost functions such as the Huber and Cauchy losses, used inside least-squares solvers, down-weight large errors smoothly instead of discarding them. Libraries such as OpenCV expose these as flags (for example the USAC methods in findHomography), so choosing one is usually a matter of configuration.

Robust estimation is also a safety matter. A robot that acts on a pose computed from a bad set of matches can drive into an obstacle or crush a part. Production systems therefore check the result: a minimum number of inliers, a maximum reprojection error, a plausible motion compared with wheel odometry, and a covariance estimate from the final least-squares fit. If the checks fail, the right action is to report low confidence and fall back, not to act on the answer.