Seven marks, three answers

A fundamental matrix has nine entries, is defined up to scale, and must be singular. That is nine minus one minus one: seven degrees of freedom, so seven correspondences ought to be enough.

Eight points and the basis they are read in uses eight because eight makes the problem linear, and a point is a line over there is where the constraint each mark imposes was established. Seven does not, and what happens when the count is dropped to the minimum is the subject here — because the answer is not one matrix and it is not a family. It is three.

Where the cubic comes from #

Seven correspondences give seven linear conditions on nine entries, so the nullspace has dimension two: every candidate is F = αF₁ + (1−α)F₂ for two basis matrices and one free number.

The singularity requirement has not been used yet. Imposing it means det(αF₁ + (1−α)F₂) = 0, and a determinant of a three-by-three whose entries are linear in α is a cubic in α. A cubic with real coefficients has one real root or three.

So the minimal problem has one solution or three, and which it has is a property of the seven marks rather than of the algorithm.

Three answers, all exact #

On the arrangement here it has three real roots, and each of them is a matrix that satisfies every one of the seven marks to 8.9 × 10⁻⁹ pixels.

That number is the point. These are not three near-solutions clustered around a true one, and they are not a numerically ill-conditioned single answer split by rounding. They are three distinct matrices — over 0.05 apart after normalisation, with different epipoles — each of which explains the evidence to the last bit of the arithmetic.

The eighth mark chooses #

Add one correspondence that was not used in the fit and the three separate immediately: 0.00 pixels for one of them, 16.2 and 17.9 for the other two.

That is an order of magnitude and a half of separation from a single extra measurement, and it is why the seven-point algorithm is used in practice rather than avoided. Inside a robust estimator, seven marks is a cheaper hypothesis than eight and generating three hypotheses per sample rather than one is an advantage: more of the hypothesis space is covered per random draw, and the scoring step against all the other marks resolves them for free.

Why this ambiguity is not the plane’s #

The two failures in this round’s row look similar and are opposites, and the difference is exactly what one more mark does.

A plane leaves a two-parameter continuum of fundamental matrices, and every one of them predicts every mark on the plane. Adding marks buys nothing, because the extra marks are on the plane too and every candidate explains them. A flat scene fixes no second eye is that case.

Seven marks leave a finite set of three, and the three disagree about points not among the seven. One more mark almost anywhere separates them. The ambiguity is real, exact, and cheap to remove.

So the useful distinction is not between “one answer” and “more than one”. It is between an ambiguity whose alternatives disagree about something measurable and one whose alternatives agree about everything the arrangement can measure — which is what an ambiguity is not an uncertainty is written to make precise.

What the three answers look like #

Their epipoles are in different parts of the picture and their epipolar bundles run at different angles, so the three are visibly different geometries rather than three versions of one.

What they have in common is the seven marks, and it is worth being precise about how strong that is. Seven marks in two pictures is fourteen numbers. Each of the three matrices reproduces all fourteen relationships exactly. If those seven were the only marks that existed, no amount of care, no better solver and no better camera would distinguish them.

That is the shape of every genuine ambiguity in this collection: two views give shape and no size is one continuous parameter that no pair of pictures reaches, and this is three discrete alternatives that no seven marks reach.

How the cubic is actually solved #

A note on method, because the obvious approach is worse than it looks.

Expanding det(αF₁ + (1−α)F₂) symbolically gives four coefficients and a page of algebra with plenty of places to make a sign error. Sampling the determinant at four values of α and solving the resulting four-by-four Vandermonde system is exact for a cubic, is four determinant evaluations and one small solve, and cannot be got wrong in a way that passes a test.

The roots then come from the trigonometric form of the cubic rather than from an iteration. That matters here: an iterative root-finder started near one root returns that root, and the whole content of this essay is that there may be three. A closed form returns all of them or says there is one, and the discriminant says which case it is.

When there is one root and when there are three #

The count is a property of the arrangement, and finding an arrangement with three took a search: consecutive subsets of seven were tried until one gave a discriminant of the right sign.

That is worth reporting as a search rather than presenting as a construction, because it says something about how common the case is. Most sevens on this scene give one root. Some give three. Nothing about a set of seven marks looks different in advance, and the discriminant is the only thing that says which case is in hand.

A practical consequence: an implementation that assumes one root will silently take whichever the solver returns first, and will be wrong on some fraction of its samples. Inside a robust estimator that fraction is absorbed — a wrong hypothesis simply scores badly — but in a pipeline that trusts a single minimal solve it is a source of failure with no symptom, which is the shape where the adjustment stops measures at the other end of the same pipeline.

What the three do to a reconstruction #

Choosing the wrong root does not produce a slightly wrong scene. It produces a scene that reprojects perfectly onto the seven marks and is otherwise unrelated to the one in front of the camera.

That is the same property the plane’s family has, and it is worth stating twice because it is counterintuitive. A wrong fundamental matrix is not a noisy fundamental matrix. Triangulating against it gives points that satisfy their own epipolar constraint by construction — the constraint the wrong matrix imposes — so every consistency check that reads the seven marks passes.

The checks that fail are the ones that read something else: the eighth mark, the visibility of the reconstructed points, the agreement with a third view. All three are cheap, and a pipeline that runs none of them will report a confident wrong answer with no complaint anywhere. That is the failure mode this collection keeps meeting under different names — a wrong match is not a small error is the same shape at the level of a single correspondence.

The count of solutions, across the field’s minimal problems #

Three is not a special number and it is worth putting beside its neighbours, because a reader meeting minimal solvers for the first time will meet several counts.

Seven points and an uncalibrated pair: three solutions, from a cubic. Five points and a calibrated pair: ten solutions, from a tenth-degree polynomial. Three points and a known scene: four solutions, of which visibility usually removes two. Six points and a general camera: three again.

Every one of them is the same phenomenon — the minimum evidence for a problem determines it only up to a finite set — and every one is resolved the same way, by scoring the candidates against evidence that was withheld. Four cameras fit and one can see is this collection’s other instance, where the finite set is four poses and the withheld evidence is which of them puts the scene in front of both cameras.

Why the minimum is worth using #

Robust estimation is the reason, and the arithmetic is short.

A sample of n marks is uncontaminated with probability (1−ε)ⁿ if a fraction ε are wrong. At thirty per cent contamination, seven marks are clean 8.2 per cent of the time and eight marks 5.8 per cent — so seven needs about seventy per cent as many random samples to find a clean one. Add that each clean sample of seven yields up to three hypotheses rather than one and the advantage compounds.

The cost is the cubic, the possibility of three roots, and the need to score every root rather than the first. All three are cheap, and none of them is optional: an implementation that skips the scoring throws away most of the advantage it went to the trouble of getting.

The sample count is exponential in the sample size #

The arithmetic above compares seven marks with eight and finds seventy per cent. Carrying it one step further turns a comparison into a law, and the law is what explains why minimal solvers are pursued so hard.

To be confident to probability $p$ of drawing at least one clean sample of $n$ marks from data with a contaminated fraction $\varepsilon$, the number of random samples needed is

$$N = \frac{\log(1-p)}{\log\!\left(1 - (1-\varepsilon)^{n}\right)} \;\approx\; -\log(1-p)\,(1-\varepsilon)^{-n}$$

whenever the clean probability is small. $N$ is exponential in $n$, with base $1/(1-\varepsilon)$ — so every mark removed from the minimal sample divides the work by a constant factor, and the factor is worse the dirtier the data.

At thirty per cent contamination and ninety-nine per cent confidence: eight marks need 78 samples, seven need 54, and the calibrated five-point solver needs 25. The ratios are $1/0.7$ per mark dropped, which is 1.43 for the first and 2.04 for the pair. At fifty per cent contamination the same counts are 1,178, 588 and 145 — a factor of two per mark, and a solver that uses three fewer marks does eight times less searching.

Against that, the hypothesis counts run the other way: one root for eight marks, three for seven, ten for five. Each hypothesis has to be scored against every other mark, so the scoring work per sample grows with the count. But it grows linearly while the sample count falls exponentially, and a linear cost against an exponential saving has only one outcome once the contamination is appreciable.

That is the whole argument for minimal solvers, and it is worth having as an arithmetic rather than as a preference, because it also says when the argument stops applying. At five per cent contamination the base is $1/0.95 = 1.05$, so a mark dropped saves five per cent of the sampling and the five-point solver’s ten hypotheses cost ten times the scoring. On clean data the elaborate minimal solver is a bad trade, and the plain eight-point fit over all the marks is better than any of them — which is the arrangement most of this collection’s figures are in, and the reason they use it.

The exponent also explains a practical rule that otherwise looks like superstition: it is worth spending real effort to lower $\varepsilon$ before spending any on the solver. Halving the contamination from 50% to 25% takes the five-point count from 145 samples to 17, a factor of eight, which is more than the entire gap between the eight-point solver and the five-point one at the higher rate. A better matcher is worth more than a better minimal solver, and the arithmetic says by how much.

Where the seven-point solver is genuinely the right tool #

Two arrangements, and both are common.

A pair of photographs with a lot of wrong matches in them. The arithmetic above is the whole argument: fewer marks per sample means more clean samples, and three hypotheses per sample means more coverage. Every practical two-view pipeline runs the seven-point solver inside a robust estimator for this reason.

And a pair with barely eight matches at all. A textureless scene, a night photograph, a pair taken through a doorway: sometimes there are seven good correspondences and the eighth is a guess. Using seven and scoring the three roots against the doubtful eighth is a better use of it than putting it into the fit, because a bad mark in a fit contaminates the answer and a bad mark in a score only weakens the separation.

The one place it is the wrong tool is the one this round is about. If the seven marks are coplanar, the design matrix loses another rank, the nullspace has three dimensions instead of two, and the cubic construction has nothing to stand on. A flat scene fixes no second eye is where that is measured, and it is one more reason a planar check belongs upstream of any minimal solver rather than downstream of it.

Why seven and not six #

The degree-of-freedom count says seven, and it is worth checking that the count is the right one rather than a coincidence of three numbers subtracting to seven.

A fundamental matrix is a rank-two three-by-three up to scale. The rank-two three-by-threes form a seven-dimensional variety inside the eight-dimensional projective space of all three-by-threes — one dimension lost to the determinant vanishing — and each correspondence imposes one linear condition. Seven conditions cut a seven-dimensional variety in a finite set, and the number of points in that set is the variety’s degree, which is three.

So the three is not an accident of the algebra either. It is the degree of the determinantal variety, and the cubic is that degree showing up in coordinates. The same reasoning gives ten for the five-point calibrated problem, where the variety is the essential matrices and its degree is ten.

That is a satisfying place to leave the count, because it says the number of answers is a property of the problem rather than of the method. No cleverer solver returns fewer.

What the two basis matrices are #

The nullspace’s two directions are not meaningful individually, and it is worth saying so because a reader implementing this will want to interpret them.

They come out of the singular value decomposition as the two right singular vectors with the smallest singular values, and any two independent combinations of them span the same pencil. Neither is a fundamental matrix — neither is singular, in general — so drawing the epipolar geometry of F₁ alone is drawing something that is not an epipolar geometry at all.

What is meaningful is the pencil: the one-parameter line through the nullspace, and the three points on it where the determinant vanishes. That is why the cubic is solved rather than the basis inspected, and why the figure plots the determinant against the mix rather than showing the two matrices.

The same caution applies to the flat scene’s three-dimensional nullspace one essay over. Its basis vectors are equally arbitrary; what is meaningful there is the whole two-parameter family after the rank-two projection, and the three members drawn are three points chosen from it to be visibly different rather than three canonical answers.

The short version #

Seven correspondences leave a two-parameter nullspace, and the singularity requirement turns it into a cubic in one parameter. The cubic has one real root or three, which is a property of the marks; here it has three, and all three satisfy every one of the seven to 8.9 × 10⁻⁹ pixels.

The eighth mark separates them by 16 pixels against 0.00. That is what makes this ambiguity different in kind from a plane’s: the alternatives disagree about something a measurement can reach, so one more measurement removes them. A plane’s alternatives agree about everything the plane contains, and nothing removes them.