P4-T3 — Correspondences and Outliers

Learning objectives

After this lesson, you should be able to:

• Define a correspondence, an inlier and an outlier, and the inlier ratio.
• Explain the sources of wrong correspondences.
• Show with a worked example why least squares is not robust to outliers.
• Use precision, recall and residual statistics to describe and diagnose a set of matches.

The idea: noise is small, mistakes are large

A correspondence pairs an observation in one image (or scan) with an observation in another and asserts that they are the same physical point. An inlier is a correspondence that is right (up to measurement noise); an outlier is one that is wrong. The inlier ratio w is the fraction of inliers.

The errors of inliers and outliers are different in kind. An inlier’s position error is random, small and has a known size (a fraction of a pixel). An outlier’s error is whatever the mistake produced: pairing a window on the left of a building with a window on the right gives an error of hundreds of pixels. There is no distribution to average away.

An outlier is not a large noise sample. It is a different kind of error, and an estimator that treats it as noise is broken by one example.

Where wrong correspondences come from

The mathematics: least squares, breakdown and statistics

Least squares and its weak point

Fit a model with parameters θ to correspondences (p_i, q_i) by minimising the sum of squared residuals r_i(θ), the distance between q_i and the model’s prediction for p_i:

The influence of a residual on the estimate grows with its size, because the gradient of r² is 2r. One point whose residual is 100 times larger than the others pulls as hard as 100 of them. Formally, the breakdown point of least squares is 0%: a single arbitrarily bad point can move the estimate arbitrarily far. The median has a breakdown point of 50%.

Robust alternatives

• Consensus methods (RANSAC): find the model that most correspondences agree with, then use only those (Lesson P4-T4).
• Robust loss functions (Huber, Cauchy, Tukey): replace r² by a function that grows more slowly (linearly or not at all) for large r, so a bad point has bounded influence. Used inside the optimisation of bundle adjustment and SLAM.
• Gating: reject correspondences whose residual under a predicted model is too large (for example more than 3 standard deviations).

Measuring a set of matches

These need ground truth, which is available in a benchmark with a known transform (as in the labs) and not in operation. In operation you use proxies: the fraction of matches consistent with the best model (RANSAC’s inlier count), the spread of the residuals, and whether the estimate agrees with another source (odometry, IMU).

Residuals as a diagnostic

After fitting a model, the residuals of the inliers follow the measurement noise: roughly Gaussian with the standard deviation σ of the feature locations (often 0.3 to 1 pixel). A histogram of residuals therefore has a narrow peak of inliers and a long flat tail of outliers; the gap between them suggests the inlier threshold, typically 2 to 3 σ.

A worked example: how far do two outliers move a line?

Ten points lie near the line y = 0.5 x + 1 with noise of ±0.3, and two outliers are added: (3.5, 9.0) and (8.5, 0.5). The figure shows the data.

least squares on the ten good points: slope 0.494, intercept 1.053 least squares on all twelve points: slope 0.213, intercept 2.744

With the good points only, the fit recovers the true line (0.5, 1.0) to within the noise. With two outliers out of twelve (17%), the slope is 0.21 instead of 0.50 and the intercept 2.74 instead of 1.00. At x = 10 the true line is at 6.0 and the contaminated fit is at 4.87, an error of 1.13, about 4 times the noise level. Two wrong points among twelve have destroyed the estimate.

The same thing for image matching

In Lab P4-L3, 40 matches relate two views by a rotation and a shift. About 50% are wrong. A least-squares fit to all matches gives a transform whose average position error is several pixels, against about half a pixel for a fit to the inliers alone. The gain from separating inliers from outliers is not a few percent; it is the difference between a usable and an unusable result.

How many matches survive?

Suppose a matcher keeps 40 matches with inlier ratio w = 0.6. There are 24 inliers and 16 outliers. A sample of two matches for a similarity transform is entirely correct with probability w² = 0.36. If the matcher is improved so that w = 0.8, the probability becomes 0.64: improving the inlier ratio from 0.6 to 0.8 makes a random sample 1.8 times more likely to be clean, and lowers the number of RANSAC tries needed by the same factor. This is why a ratio test and a cross-check in front of RANSAC pay off.

Diagnosing from residuals

Suppose a model fits 25 of 40 matches with residuals below 1.5 pixels (a narrow peak around 0.5) and the other 15 have residuals between 6 and 50 pixels. The gap between 1.5 and 6 is a natural threshold (2 to 3 pixels). If instead the residuals were spread evenly from 0 to 20 pixels with no gap, either the model is wrong (a rotation modelled as a shift, say) or there are almost no correct matches, and moving the threshold will not help.

Engineering implications and limitations

Assume outliers exist and design for them. Any pipeline that estimates something from correspondences with ordinary least squares is a bug waiting for the first repeated texture. Use RANSAC, a robust loss or both.

Clean first, then fit. Cheap filters (ratio test, cross-check, motion-based gating) remove most wrong matches before the estimator sees them. Each factor that raises the inlier ratio lowers the cost of the robust step.

Keep the match statistics. Log the number of matches, the inlier count after RANSAC, the residual histogram and the estimated model with its confidence. A drop in the inlier ratio is an early warning of a problem (blur, darkness, repeated scene) well before the pose goes wrong.

Do not discard what the outliers tell you. A coherent group of “outliers” can be a second motion: a moving person or car. Segmenting the matches into several consistent groups (multi-model fitting) gives the dynamic objects too.

Check the minimum number of inliers. A model fitted to 6 inliers is unreliable even if all six are correct. Require both an absolute number and a minimum spread over the image before accepting a pose.

Use ground truth in testing. Build a test set with known transforms or simulated outliers (as in the labs) and measure precision and recall of the whole matching pipeline whenever it changes.

Common misconceptions

Engineering takeaways

1. A correspondence pairs two observations of one physical point; inliers are right up to small noise, outliers are wrong by an arbitrary amount; w is the inlier ratio.
2. Least squares has a 0% breakdown point: two outliers among twelve points can tilt a line completely.
3. Robust options are consensus (RANSAC), robust loss functions (Huber, Cauchy) and gating by residual.
4. Precision, recall and inlier ratio describe a set of matches when ground truth exists; in operation use inlier counts, residual histograms and cross-sensor checks.
5. Raise the inlier ratio first with ratio test, cross-check and motion gating; then use a robust estimator; log the statistics.

References and further reading

Standard references; the line-fit numbers were computed for this lesson.

• Fischler, M. A. and Bolles, R. C. (1981). Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM 24(6).
• Huber, P. J. and Ronchetti, E. M. (2009). Robust Statistics, 2nd ed. Wiley: breakdown point and M-estimators.
• Hartley, R. and Zisserman, A. (2004). Multiple View Geometry in Computer Vision, 2nd ed. Cambridge University Press: robust estimation and outlier handling.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: RANSAC, the standard way to fit a model when a large share of the data is wrong.

Related content

Nothing below is required to finish this lesson.

• Before
  P4-T2: Feature Descriptors and Matching

  Build a patch descriptor and match by distance with a ratio test.

• Lab
  P4-L2: Match Features Between Images

  Describe patches, match them and measure precision against ground truth.