Two matches are enough

One shutter, two views establishes that the fundamental matrix of a real image and its reflection is skew-symmetric. This essay is about what that is worth, and the answer has two halves that are usually confused: how many marks are needed, and how well the answer is determined when there are more marks than that.

The two halves pull in opposite directions, and a claim that mentions only the first is the kind of claim this collection is written to distrust.

The count #

A fundamental matrix is a three-by-three, defined up to a scale, whose determinant must vanish. Nine entries, less one for the scale, less one for the rank condition: seven free numbers. Each correspondence contributes one linear equation, so eight of them determine it — which is where the eight-point algorithm gets its name and why eight points and the basis they are read in spends its length on how those eight equations are conditioned.

A skew-symmetric three-by-three is a different object. Its diagonal is zero and its off-diagonal entries come in pairs with opposite signs, so it is a three-vector wearing a matrix; up to scale that is two numbers. And the rank condition is free: every skew matrix of odd size is singular, because its determinant equals the determinant of its own negative transpose and therefore equals minus itself.

The construction #

Write the epipolar constraint with the skew matrix in its vector form and it collapses to something a ruler can do:

$$\mathbf{x}'^{\mathsf{T}}[\mathbf{a}]_{\times}\mathbf{x} = \mathbf{a}\cdot(\mathbf{x}\times\mathbf{x}') = 0$$

The cross product of two homogeneous image points is the line through them. So each correspondence says that the unknown three-vector is perpendicular to one known three-vector — that the epipole lies on the line joining a mark to its reflection. Two such lines meet at a point, and the point is the answer.

Nothing here is a numerical method. There is no least-squares problem, no normalisation, no singular value to throw away, and no design matrix whose conditioning has to be reported — which is exactly the apparatus eight points and the basis they are read in has to set up for the general case. There is a straightedge and there are two marks.

What one match leaves #

The refusal is the part that makes the claim a measurement. One correspondence gives one linear equation in three unknowns defined up to scale, which is one equation short. What it determines is a line of candidate epipoles, and every point on that line is a fundamental matrix consistent with everything that has been seen.

Both halves of that matter. The true epipole is on the line, which says the constraint is right; it is not anywhere in particular along the line, which says one correspondence is not an answer. A routine that reported the least-squares solution of a single equation would return the point of the line nearest the origin — a perfectly definite number, arrived at from an assumption about coordinates that nobody made. Here it lands five thousand three hundred and fifty-eight pixels from the truth — off the page entirely — and the honest report is that the system is underdetermined rather than that it has that answer.

What the constraint is worth when the marks are wrong #

The count above says two marks suffice. It does not say two marks are a good idea, and the distinction is where most of the value is.

Marks on a real print are read to some precision. Four tenths of a pixel is careful work. With sixteen correspondences available, there are two things to do with them: fit a skew matrix, which is two unknowns from sixteen equations, or fit a general one with the eight-point algorithm, which is seven unknowns from sixteen equations. Both are given every mark. This is not two matches against eight; it is the same evidence read with the constraint and without it, which is the only comparison that says anything about the constraint.

The ratio holding across the range is the informative part. If the constraint merely helped at low noise it would be a statement about the linearisation; a constant factor across three decades says the two estimators have the same error law and differ by a fixed amount of leverage, which is what a reduction in the number of unknowns buys.

Using only two of the sixteen is much worse than either — two hundred and thirty-three pixels of error against nine tenths of one. That is the correct answer to “two marks are enough”: enough to determine, not enough to determine well, and the two words are doing different work.

Where the extra equations go #

There is a way of reading the comparison that makes it sound like nothing. Sixteen equations, seven unknowns, nine degrees of freedom left over; sixteen equations, two unknowns, fourteen left over. Both are overdetermined, both are least squares, and it would be easy to say that the second simply has more redundancy and stop there.

What that account misses is where the errors go. In an overdetermined fit the marking error is projected onto the space the model cannot represent, and what survives is the part that lies along the model’s own directions. A seven-parameter model has seven such directions and a two-parameter model has two, so five directions’ worth of noise that the general fit absorbs into its answer is, for the constrained fit, simply residual — visible, discarded, and not part of the estimate.

That is why the ratio is a constant rather than something that changes with the noise level. It is a fact about dimensions rather than about magnitudes, and it is the same accounting what more measurement buys sets out for a length recovered from a photograph: the return on extra evidence depends on how many directions the model has to spend it in.

There is a second consequence, and it is the one that matters on a difficult photograph. A general fit needs eight correspondences before it can produce anything at all, so a mirror reflecting only five identifiable marks yields nothing. The constrained fit produces an answer from two and improves steadily thereafter — which is not a marginal difference when the mirror is small, at an angle, or half occluded, and small mirrors at angles are what real rooms contain.

The two-mark penalty is conditioning, not count #

The comparison above puts two marks at 233 pixels of error against sixteen at nine tenths of one — a factor of 259 — and it is worth splitting that number, because only a small part of it is about having fewer marks.

Averaging accounts for a factor of about $\sqrt{8}$, or 2.8: sixteen equations against two, with the error of a least-squares fit falling as the root of the count. Everything else — a factor of ninety — is conditioning, and conditioning is a property of which two marks rather than of how many.

The geometry says why. Two joining lines meeting at an angle $\varphi$ locate their crossing to $\delta/\sin\varphi$, where $\delta$ is how well each line is placed, so the epipole’s error is the mark’s error divided by the sine of the angle the two marks subtend at the epipole. Marks close together on the reflected lens subtend almost nothing there and their lines are nearly parallel; marks on opposite sides subtend the whole spread available. The condition numbers the section below reports — $3.1 \times 10^{3}$ for an adjacent pair against $1.1 \times 10^{2}$ for the widest — are that ratio of sines, and they predict a factor of twenty-eight in the error on noisy marks.

Two consequences, and the second reverses the usual advice about minimal solvers.

A well-chosen pair is close to as good as the whole set. Removing the factor of ninety leaves the factor of 2.8, so two marks taken from opposite sides of the reflected lens should land within about three times the sixteen-mark fit rather than within 259. The evidence a mirror pair contains is concentrated in the spread of its marks, not in their number.

And “more marks” and “better marks” buy different things here. More marks buy a square root; choosing the two extremes buys a factor that grows with how many there are to choose from, since the widest available pair spreads further as the set grows. For a set of $N$ marks around a lens the best pair’s advantage over a typical one grows roughly as $N$, which outruns $\sqrt{N}$ — so on a photograph with a handful of identifiable marks the first thing to do is not to find more of them but to use the two that are furthest apart.

That is an unusually cheap piece of advice, and it is the practical form of everything else in this essay. The constraint reduces seven unknowns to two; the geometry then says that the two are located by an intersection; and an intersection is a construction whose quality a reader can judge by eye, which nothing else in two-view geometry offers.

A minimal solver, and why minimal solvers exist #

A two-point solver for a mirror pair is a minimal solver in the sense the recovery field uses the word: the smallest set of measurements from which the unknown can be computed at all. Seven marks, three answers is the collection’s other one, and the contrast between them is instructive.

The seven-point solver is minimal for a general pair and returns up to three answers, because dropping to seven equations leaves a one-parameter family and the rank condition then cuts it with a cubic. The two-point solver here returns exactly one, because the rank condition was never a constraint that had to be imposed — it came free with the skewness. A minimal solver that returns one answer is a great deal easier to use than one that returns three and then has to choose.

That is the practical use. Real correspondences contain wrong ones, a wrong match is not a small error shows what a single one does to a fit, and the standard defence is to draw small random subsets, solve each, and keep the answer most of the data agrees with. The cost of that search grows steeply with the size of the subset. Two is the smallest subset any such search has ever had to draw on this site.

The scale that is not there #

One thing the constraint does not buy is worth naming, because it is the thing a reader might reasonably hope for. Two unknowns rather than seven is a statement about the epipolar geometry, not about the reconstruction, and the reconstruction is still a shape without a size.

The skew matrix names the epipole, and the epipole names the direction of the mirror’s normal in the camera’s own frame. It says nothing about how far away the mirror is. Doubling the distance to the glass doubles the baseline, doubles every recovered depth, and moves not one pixel of the photograph — which is the one thing a single view cannot give arriving in a new costume, and determined up to something is the thread the collection files it under.

So the ledger for a mirror pair reads: two numbers from the picture, fixing the direction the second eye lies in; one number from outside it, fixing how far along that direction the eye sits; and after that everything is metric. The number from outside is a distance a tape measure reads, which is the friendliest closure in the collection.

What a reader can check #

The reason to care about a straightedge construction in an age of solvers is not nostalgia. It is that almost nothing in two-view geometry can be checked by eye.

An epipolar line drawn across a photograph is a claim about a matrix somebody fitted, and a reader looking at it has no independent access to whether the fit was any good. The concurrence of the joining lines is different: it is on the print, a ruler reaches it, and it fails visibly. A photograph whose joining lines do not meet at a point is a photograph whose mirror is not flat, or whose correspondences are not correspondences.

The conditioning, since two equations is where conditioning starts #

Two equations in three unknowns is the minimum, and a minimum is where the conditioning of a system stops being academic. The two joining lines meet well if they cross at a decent angle and badly if they are nearly parallel — which is the same statement as two rays that do not meet makes about triangulation, one dimension down.

Two joining lines are nearly parallel when the two marks lie in nearly the same direction from the epipole. So the instruction for choosing two marks out of sixteen is: choose them on opposite sides of the reflected lens. The design matrix’s condition number in the arrangement drawn above is 3.1 × 10³ for an adjacent pair and 1.1 × 10² for the widest available one — a factor of twenty-eight, which is a large return on a choice that costs nothing. Measured on that arrangement, the adjacent pair puts the epipole 1.8 × 10⁻¹² pixels from the truth and the separated one 3.7 × 10⁻¹³.

Two constraints, and only one of them is free #

It is worth being precise about which of the two savings is the interesting one, because they have different characters.

The scale saving — nine entries down to eight — is trivial and applies to every homogeneous quantity in the subject. The rank saving is not. In the general case the vanishing determinant is a cubic condition, so it cannot be imposed inside a linear fit; the eight-point algorithm solves the linear problem, gets a matrix with three nonzero singular values, and repairs it afterwards by setting the smallest to zero. That repair is a projection onto the nearest matrix of rank two, and “nearest” is being measured in a norm nobody chose for a reason.

Skewness makes the repair unnecessary. Every three-by-three skew matrix already has rank two — its determinant is minus its own determinant, so it is zero, and the rank cannot be one unless the vector is zero. So the constrained fit produces a valid fundamental matrix directly, and there is no step in it whose justification is “the smallest singular value was small”.

This is a recurring shape in the collection. A constraint that arrives as part of the parameterisation is worth much more than the same constraint imposed afterwards, because the second kind admits a step where an answer is nudged toward validity by an amount nobody stated. Four cameras fit, and one of them can see is the same lesson from the pose side: a family of algebraically valid answers, cut down by a condition that could have been in the model from the start.

What is measured here #

Two well-separated marks put the epipole 3.7 × 10⁻¹³ pixels from where the full computation puts it, at a design condition number of 110; two adjacent marks manage 1.8 × 10⁻¹² at a condition number of 3,100. One mark puts it five thousand three hundred pixels away and reports the system as underdetermined rather than reporting that number as an answer, and the true epipole lies on that single line to 10⁻¹² pixels.

Given all sixteen marks read to four tenths of a pixel, the skew fit lands 0.90 pixels from the truth and the eight-point fit 4.35, a factor of 4.8; using only two of the sixteen lands 233 pixels away. And the ratio between the two full fits is constant to within a few per cent across marking errors from a tenth of a pixel to three.

The short version #

The skewness of a mirror pair’s fundamental matrix reduces it from seven unknowns to two, and two correspondences therefore determine it — by a construction with a straightedge rather than by a solver, which is a rare thing in this part of the subject.

One correspondence determines a line of candidates and the true answer is on it. Sixteen correspondences read with the constraint give an answer about five times better than the same sixteen read without it. And two marks, though enough, are not the way to use sixteen: minimal is a statement about what determines the answer, not about what determines it well.