Eight points and the basis they are read in

The fundamental matrix has appeared twice now as something that exists. This essay is about getting one out of a list of marks, which is a linear algebra problem with an unusually clear moral.

The moral is that the coordinates the marks are written in are part of the method, not a neutral container for it. Two people can implement the identical algorithm, feed it the identical correspondences, and get answers an order of magnitude apart, because one of them centred the numbers first.

The system #

Each correspondence gives one equation. Writing the mark in the left picture as $(x, y)$ and its match as $(u, v)$, and $F$’s nine entries as $f_1 \ldots f_9$, the constraint $\mathbf{x}'^{\top} F \mathbf{x} = 0$ expands to

$$ux\,f_1 + uy\,f_2 + u\,f_3 + vx\,f_4 + vy\,f_5 + v\,f_6 + x\,f_7 + y\,f_8 + f_9 = 0.$$

That is one row of a matrix with nine columns, and $n$ correspondences give an $n \times 9$ system whose right-hand side is zero. Homogeneous systems have the trivial solution, so the answer wanted is the non-trivial one — the direction in which the system does least, which is the right singular vector of the smallest singular value.

Eight correspondences make the system $8 \times 9$, which has a null space by counting alone, and that is where the name comes from.

Two mechanical things then have to happen, and both are the kind of step that gets left out of a summary.

The solution has to be reshaped into a matrix and forced to rank two, because a nine-parameter fit does not know it is answering a seven-parameter question, and the un-forced matrix has no epipole at all.

And the whole thing has to be done in sensible coordinates, which is the rest of this essay.

Why pixels are a bad basis #

Look at the row above and read the magnitudes rather than the symbols.

On a 690 × 400 picture, $x$ and $u$ run to around 690. So $ux$ runs to around 470,000. Meanwhile the last entry of every row is 1.

A matrix whose columns differ in typical magnitude by a factor of half a million is badly conditioned in a specific and damaging sense: the directions in its column space are not comparable, so a least-squares fit — which minimises a sum of squares over all of them equally — is effectively weighting the $ux$ column half a million times more heavily than the constant column. The answer it returns is dominated by the large columns, and the small ones are fitted with whatever is left.

The repair, due to Hartley, is one line of preprocessing. Translate the marks so their centroid is at the origin, and scale them so their mean distance from the origin is $\sqrt{2}$. Do it separately for each picture, record the two transforms, solve, and push the result back into pixel coordinates at the end.

After that the coordinates are of order 1, the products are of order 1, the constant column is of order 1, and the columns are comparable.

What it is actually worth #

Here the essay departs from the textbook, because the textbook states a factor and the measurement does not support one.

At a quarter-pixel reading, the two bases give answers 1.1 times apart. That is nothing. Forty-four well-spread correspondences with a quarter-pixel of error is a comfortable problem, and both bases have accuracy to spare.

At four pixels, they are 29.9 times apart.

The shape of that is the finding. Normalisation is not a fixed improvement applied to a fixed method; it is insurance whose value is zero when nothing goes wrong and large when something does. The condition numbers say why: the raw system’s determined directions span a factor of 2.5 × 10⁵ regardless of how carefully the marks were read, and the normalised system’s span 102 regardless. What changes across the figure is how much error is being fed in, and a badly conditioned system amplifies it while a well conditioned one does not.

The measurement that inverted #

The first version of this figure quoted a single factor at one operating point, and the factor came out at 0.53 — the raw fit better than the normalised one.

Nothing was wrong with either fit. The configuration was a 2.6 m separation, forty-four points spread across the whole frame, marks read to a whole pixel: a comfortable problem in both bases, where the residual difference between them is arithmetic noise and either can win.

It is worth dwelling on how nearly that shipped. The claim being made was the standard one, the number produced was in the right ballpark, and the direction was the only thing wrong. A caption reading “raw is 0.5× worse” would have been visibly broken; a caption reading “normalisation is worth 1.9×” — which is what the same measurement gives with the ratio the other way up — would have looked entirely reasonable and would have been backwards.

What caught it was that the assertion demanded better than a factor of two and the assertion failed. The assertion was written expecting the textbook result, so it fired on a case the textbook does not cover, and the honest repair was not to relax it but to find out what was true across a range.

That is the third time this site has replaced a single measured number with a curve after the single number turned out to depend on where it was taken. The height recovery’s conditioning was computed in a variable nobody perturbed; the uncorrected lens error was a function of radial span rather than of position, and passed through zero at an object height of about 3.2 m; and now this. In all three the mistake has the same shape, which is quoting a derivative at one point and reading it as a property.

The condition number that had to be redefined #

A smaller repair, and a satisfying one, because it turns an uninformative number into an informative one.

The natural thing to report about a design matrix is $\sigma_1 / \sigma_n$ — the largest singular value over the smallest. For this system that quantity is infinite, in both bases, for every input.

The reason is that $\sigma_n$ is the null direction. On exact correspondences it is zero to rounding, because a null direction is exactly what the system is being asked for. So the textbook condition number reports the same thing — infinity, or something around 10⁻¹⁶ in the denominator — whether the system is beautifully posed or hopeless.

What distinguishes them is how hard the other eight directions are pinned, and that is $\sigma_1 / \sigma_{n-1}$. The first draft printed the textbook ratio, produced Infinity for both bases, and made the two look identical at exactly the moment they differ by more than three orders of magnitude.

The corrected quantity is what the figure reports: 102 normalised, 2.5 × 10⁵ raw. Those are numbers about the part of the system that determines the answer.

And a number in the spectrum that is a distance #

Having looked closely at the spectrum for a numerical reason, there is something in it worth looking at for a geometric one.

The second-smallest singular value — $\sigma_8$, sitting just above the null direction — measures how far the system is from having a two-dimensional null space. And the configuration in which it has one is a familiar one: two eyes in the same place. A pure rotation makes the correspondences related by a homography, the epipolar constraint stops picking out a single matrix, and the null space grows.

So $\sigma_8$ is a measure of how far the two cameras are from being in the same place, computed from the marks.

Over three decades of baseline, from two millimetres to two metres, $\sigma_8$ is proportional to the separation: a log–log slope of 0.973 with every point within 0.055 of a decade of the fitted line.

The proportionality itself is not the interesting part. The interesting part is that a singular value of a matrix built entirely from image coordinates reports a distance in the world. Nothing in the computation was told where either camera was; the number came out of forty-four pairs of pixel positions.

That is this site’s oldest habit applied to a new quantity. The focal length recovered from three vanishing points is a fact about the camera read off the drawing. This is a fact about two cameras read off two drawings, and it is the one quantity a single view has no word for at all.

The proportionality is a proportionality, of course, not an equality — it is $\sigma_8$ in units set by the normalisation, not metres. Turning it into metres needs a length supplied from outside, and that is the ambiguity this field cannot escape. What the number does supply, without any external length, is a ratio: whether this pair of pictures has ten times the baseline of that pair, and whether the baseline is large enough for the reconstruction to mean anything.

Why the rank enforcement happens in the normalised frame #

The order of operations matters here in a way that is easy to get wrong, and the reason is worth setting out because it is the same reason the normalisation helps at all.

The recovered nine-vector is reshaped into a matrix and its smallest singular value is set to zero. That step is a projection: it finds the nearest rank-two matrix, in the sense of the Frobenius norm. And “nearest” is a statement about a metric, so it depends on the coordinates the matrix is written in.

In the normalised frame all nine entries of the matrix are of comparable size, so the Frobenius norm treats them comparably and the nearest rank-two matrix is the sensible one. In pixel coordinates the entries differ by many orders of magnitude, so the same projection is dominated by the largest entries and effectively ignores the smallest — which is the same failure as before, applied to a different step.

So the sequence is: normalise the marks, build the system, solve it, force rank two, and only then push the result back into pixel coordinates with the two recorded transforms. Forcing the rank after denormalising would undo a good part of what the normalisation bought, and would do it silently, because the resulting matrix is still rank two and still has an epipole and still draws convincing lines.

This is the sort of ordering that is impossible to debug from a picture. Both orders produce a figure. One of them is more wrong than the other by an amount that depends on the data, and the only way to know which is which is to have thought about what the projection is measuring.

What is being minimised, and what is not #

A last piece of honesty about the method, since the essay has been recommending it.

The eight-point algorithm minimises an algebraic quantity — the sum of squares of $\mathbf{x}'^{\top} F \mathbf{x}$ over the correspondences. That quantity is not a distance in the picture, and it is not the thing anyone actually wants small. What is wanted small is the distance from each mark to the line its partner predicts, which is what every figure in this field reports.

The two are related but not proportional. The algebraic residual for a given geometric error is larger for marks far from the epipole and smaller for marks near it, so the fit quietly weights points by their position in the frame. Estimators that minimise the geometric quantity directly — the Sampson approximation, or a full non-linear refinement — exist, and produce measurably better answers on noisy data.

They are also not what this field is about. The reason the linear method is used throughout is that its behaviour is completely transparent: it is one singular value decomposition of one matrix, its conditioning is visible in the spectrum, and when it goes wrong the spectrum says why. A non-linear refinement would produce better numbers and hide the mechanism, and the mechanism is the subject.

The point at which that stops being the right trade is the many-view field, where every camera and every point are adjusted together against a genuinely geometric error and the improvement over the linear chain is measured rather than assumed.

Eight points, and the SVD that refused them #

One implementation detail, recorded because the failure was absurd.

The routine that solves the homogeneous system originally asserted that the matrix passed to it was at least as tall as it was wide. That is the ordinary case — forty-four correspondences give a 44 × 9 system — and the assertion looked like reasonable hygiene.

It made the eight-point algorithm fail on eight points. Eight correspondences give an 8 × 9 system, which is the case the method is named after, and the assertion refused it.

The repair is that a wide matrix is padded with zero rows. That is exact for what the caller wants: $A^{\top}A$ is unchanged by appending zero rows, so the singular values and the right singular vectors are unchanged, and the null vector is the null vector. Only the left singular vectors gain a spurious zero, and no caller on a wide matrix reads them.

The lesson is not about padding. It is that a guard written for the common case had made the named case impossible, and nothing noticed until a figure was written that used exactly eight.

What a well-posed system needs #

Pulling the practical content together, since the essay has been mostly about a failure mode.

Spread the points across the frame. The normalisation fixes the scale of the coordinates and cannot fix a configuration where all forty-four marks sit in one corner. Points clustered in a small region determine the fit weakly no matter what basis it is written in.

Spread them in depth. Correspondences from a single plane in the world are a degenerate configuration for the fundamental matrix — they are related by a homography, which satisfies the epipolar constraint for a whole family of matrices. A wall photographed twice is exactly this case, and it is common.

Read them as precisely as possible, and know that precision is the thing being spent. The figure’s horizontal axis is reading precision because that is what changes across it. Everything else — the geometry, the algorithm, the number of points — is fixed, and the answer degrades anyway.

And do the normalisation, even though it will usually make no difference. That is the honest form of the recommendation. Most of the time both bases work. The reason to centre and scale is that when the data is poor, the raw basis fails at a rate the residual does not report, and the cost of avoiding it is four lines.

The matrix is now in hand. Turning it into two cameras takes one more step, one division by the calibration, and an assumption that has nothing to do with algebra.