A wrong match is not a small error

Every measurement in this field so far has assumed that the correspondences are correct. Marks may be read imprecisely — that assumption has been relaxed repeatedly, and the consequences measured — but they have always been marks of the same world point.

A mismatch is a different kind of input. It is not a mark read to a pixel instead of to a hundredth; it is a pair of positions that were never images of one thing. And a fit has no way to represent that.

Where a mismatch comes from #

It is worth a paragraph on what actually produces one, because the corruption in the figure is applied by hand and that can make the failure look artificial.

The commonest source is repetition. Two pictures of a building with forty identical windows offer, for each window in one picture, forty plausible partners in the other. The epipolar constraint removes most of them, and does not remove the ones that lie along the same line — which, for a row of windows photographed from roughly the same height, is precisely the ones that are confusable. The geometry and the ambiguity are aligned.

The second commonest is occlusion. A corner visible to one camera may be hidden from the other, so the correct partner does not exist, and a matcher asked to produce one produces the best of the wrong answers rather than declining.

The third is a surface seen at very different angles by the two cameras, where the same physical patch genuinely looks different and the best-matching patch is not the corresponding one.

None of those is noise. All three produce a confident, specific, wrong pair, and the arithmetic below is about what a fit does with one.

The measurement #

Forty-four correspondences, one of them moved.

Before the corruption the fit is exact to 2.3 × 10⁻¹³ px, which is arithmetic. After moving one mark by thirty pixels, every other correspondence — all forty-three of them, none of which was touched — is wrong by half a pixel on average and by 1.7 px at worst.

Half a pixel does not sound like much. Against a fit that was exact to a part in ten trillion, it is an increase of twelve orders of magnitude, and it is distributed across points that were, individually, measured perfectly.

Why the damage spreads #

The mechanism is the one thing about least squares that everybody knows and that is easy not to apply.

Each correspondence contributes one row to a linear system, and the solution minimises the sum of squares of the residuals over all rows. A row that is inconsistent with the others cannot be satisfied and cannot be ignored: the minimiser trades a little error on every good row against a lot of error on the bad one, because the objective is a sum and the trade reduces it.

So the bad row is not rejected. It is shared out.

The fundamental matrix’s independence from the scene makes this precise. All forty-four rows are measurements of one object with seven degrees of freedom. A mismatched pair is not an awkwardly placed measurement of that object; it is a measurement of a different object, spliced into the list. The fit has no representation for “one of these is about something else”, so it returns the matrix that best compromises between the two objects — which is a matrix describing neither.

What the residual does and does not say #

The obvious defence is to look at the residuals after fitting and reject whatever is large.

It works here. The largest residual does fall on the correspondence that was moved, and a practitioner following that recipe would find it.

The figure’s caption says it is not obliged to, and that qualification is doing real work. The reason is that the fit has already been distorted by the outlier, so the residuals are measured against a wrong geometry. A correspondence that is perfectly correct but sits where the distortion is largest can acquire a residual comparable to the culprit’s, and with a larger corruption, a smaller point count, or a less favourable spread, the ordering flips.

This is the well-known failure of least squares in the presence of outliers, and it has a name in the literature — the breakdown point of the estimator is zero, meaning a single bad observation can move the answer arbitrarily far. What is worth measuring rather than citing is the shape of the damage: not that the answer moves, but that it moves everywhere, so that no local inspection finds the cause.

There is a second-order effect worth naming too. Rejecting the largest residual and refitting is a reasonable procedure and it can reject the wrong point. Having done so, the refit is cleaner — one row removed always reduces the residual — and the fit now excludes a good measurement and retains a bad one. Nothing in the numbers reports that, because every diagnostic improved.

Where the damage lands, and where it does not #

The figure draws the residual at every one of the forty-four correspondences rather than summarising them, and the arrangement of the bars carries an argument the summary would lose.

If the damage were local — if a bad correspondence spoiled the geometry near itself and left the rest alone — the bars would show a peak around the corrupted index and a flat floor elsewhere. They do not. The residual is raised across the whole set, with structure that has nothing to do with which point was moved.

The structure it does have is geometric. Points whose epipolar lines run at similar angles are affected similarly, and the largest residuals cluster where the recovered pencil has swung furthest from the true one. That is a pattern in the picture, not in the list, and the list’s ordering makes it look like noise.

The consequence for practice is a small but real one: sorting residuals and looking at the top of the list is a procedure that discards the spatial information. A residual map — the same numbers drawn at the positions of the marks — shows a coherent pattern when the geometry is wrong and an incoherent one when a single mark is misread, and the two cases call for different responses.

An outlier and a badly conditioned pair are not the same failure #

It is easy to lump this essay’s failure together with the short-baseline failure, because both produce a confident wrong answer with clean-looking diagnostics. They are different, and separating them matters because the responses differ.

A short baseline is a failure of information. The pictures do not contain what is being asked of them, every correspondence is correct, and no estimator recovers what is not there. The response is to change the configuration — step further sideways, read the marks better, or accept a weaker answer.

An outlier is a failure of assumption. The pictures contain plenty of information; the estimator has been told something false about one measurement. The response is to detect and remove, and the configuration is fine.

The two also leave different traces. A short baseline shows up in the second-smallest singular value of the design matrix, which is small because the geometry is nearly degenerate. An outlier leaves that singular value perfectly healthy — forty-four rows still pin eight directions firmly — and shows up instead in the spread of per-point residuals. So the two diagnostics are independent, and a pair can suffer from either, both, or neither.

Confusing them produces the worst response of each: adding correspondences to fight an outlier, or hunting for outliers in a pair that simply has no baseline.

Why this site does not solve it #

The standard answer is robust estimation: fit to random minimal subsets, count how many correspondences agree with each candidate, keep the candidate with the most support, and refit to those. RANSAC and its many relatives.

It works well, it is what every practical system does, and it is not this site’s subject. ../CLAIM_REGISTRY.md records the boundary: RANSAC and its relatives belong to the algorithms site as algorithms, and are licensed here for exactly the one thing this field needs them to say — that a wrong correspondence is not a small error, so the estimator has to be able to reject rather than to accommodate.

The distinction is not territorial fussiness. A robust estimator is a piece of procedure whose behaviour is analysed in terms of sampling, breakdown points and probability of success. The claim this essay makes is a piece of geometry: the fundamental matrix is a single object measured by every correspondence, so an inconsistent measurement contaminates the whole estimate rather than a region of it. The second explains why the first is necessary, and it survives whatever the first is replaced by.

There is also a practical reason to state the geometry separately. A robust estimator can only reject what it can detect, and what it detects is disagreement with a candidate model. A mismatch that happens to lie on the correct epipolar line agrees with the model perfectly and is invisible to any amount of resampling. Those are not rare: the constraint leaves one degree of freedom, so any repeating structure — railings, brickwork, a row of identical windows — produces wrong candidates spaced along exactly the direction that is free.

So the honest sequence is that the geometry says a mismatch is catastrophic, robust estimation removes the mismatches that disagree with the geometry, and the ones that agree with it survive both.

The corruption that was too polite #

A note on how the figure’s numbers were arrived at, because the first version asserted the wrong thing.

The assertion originally demanded that the median residual after corruption exceed one pixel, and it measured 0.54. The assertion was not describing anything: forty-four well-spread correspondences divide one bad row into forty-four small ones, and half a pixel is what that division gives.

Rewriting the assertion to demand a larger corruption would have been arranging for the number to be impressive. What the measurement actually supports is a comparison rather than a magnitude — the typical point moved from 2.3 × 10⁻¹³ px to 0.54 px, which is a factor of over 10¹², and that ratio is the claim. The corrected assertion is on the ratio, plus a count: more than half of the untouched correspondences moved by over 0.05 px, which says the damage is general rather than concentrated near the corruption.

The general lesson is one this phase learned three times. An absolute threshold on a residual is a claim about a configuration; a ratio against a clean baseline is a claim about a mechanism. The first has to be re-tuned whenever anything changes and quietly stops meaning anything; the second does not.

The same mechanism, three fields back #

This is not the first time on this site that one bad input has been shown to contaminate a whole fit, and the earlier cases are worth recalling because together they make a pattern rather than an anecdote.

The conic fitted to a projected circle is a least-squares fit to sampled points, and the reason its design matrix is centred and scaled before solving is that without it the condition number runs into the millions and the fitted centre wanders by more than the offset being measured. That is the same arithmetic as this essay’s outlier — a fit distributing an inconsistency across all its parameters — with conditioning rather than a mismatch as the source.

The plumb-line lens fit found something sharper. Fitting one distortion coefficient to data generated by a two-term lens returned a coefficient 22% wrong with a residual of 0.68 px. The model was inadequate rather than the data corrupt, and the fit responded the same way: absorb the discrepancy into the parameters and report a small residual.

And the gauge directions in the many-view field are the extreme case of the same fact about least squares. There the objective is exactly flat in seven directions, so the fit will happily return any point along them, and the residual reports nothing at all about which one.

The common thread is that a residual measures agreement between a model and its own fit, not between a model and the truth, and every one of these cases is a place where those two come apart. It is the reason this site’s habit is to check a recovery against something it was not given, rather than against how well it explains what it was given.

How large a corruption has to be #

Thirty pixels is a substantial displacement — on a 690-pixel frame it is about four per cent of the width — and it was chosen to be visible rather than to be typical.

The interesting regime is smaller. A mismatch of a few pixels is what a matcher produces on repetitive texture, and it is small enough to be mistaken for a badly-read mark. The distinction between the two is not the size but the origin: a badly-read mark is a measurement of the right object with noise on it, and its errors average out across many marks. A mismatch is a measurement of the wrong object, and its error does not average out — adding more good correspondences dilutes it but never cancels it, because it is a bias rather than a fluctuation.

That distinction has a testable consequence. Add correspondences to a set containing pure reading noise and the fit improves as the square root of the count. Add correspondences to a set containing one mismatch and the fit improves toward a wrong answer, converging to the geometry that best compromises between forty-four good rows and one bad one. More data helps in the first case and helps in the second only up to a floor set by the corruption.

What is left when the marks are trusted #

It is worth closing by naming what this essay does not undermine, since it has been mostly about a hazard.

Every other measurement in this field was made with exact correspondences, and each of them is a statement about geometry that does not depend on matching. The epipole lands on the projection of the other eye to a billionth of a pixel. The shape comes back to fourteen digits with the size undetermined. The range past which nothing can be bounded is fB/δ regardless of how the marks were obtained.

Those are properties of two pictures of one scene. Supplying correspondences exactly is what makes them measurable rather than confounded with the performance of a matcher, and the test that they are geometry rather than matching is that every one of them survives with no image data at all — only coordinates.

What this essay adds is the boundary condition. The geometry is exact and it is exact about the correspondences it is given. Feed it a list containing something that is not a correspondence and it will return a matrix, a pose, a point cloud and a small reprojection error, and every one of them will be wrong, in a way that no single point’s residual reliably names.

That boundary is also where this field hands over. Detecting which of a list of candidate matches are real, on actual image data, against repetition and occlusion and changing illumination, is the whole of a subject that this site does not take. What it leaves behind for that subject is the reason the work is necessary: not that mismatches introduce noise, which would be tolerable, but that a single one relocates the entire estimate, and that the estimate’s own diagnostics improve while it does.

The next field raises the number of pictures, and it changes this calculation in a way worth anticipating. With many views a point is observed several times, so a correspondence can be checked against more than one geometry, and an observation inconsistent with the rest becomes visible in a way it cannot be with two. That is a genuine gain — and it arrives alongside a loss, because more pictures also mean more parameters, and the seven that no picture determines are waiting there regardless of how clean the correspondences are.