The Five-Point Algorithm & Minimal Relative-Pose Solvers

Motivation

A 3×3 matrix has nine entries. F has seven degrees of freedom, which is exactly why the eight-point algorithm has to hand it eight correspondences: eight linear equations are barely enough to leave a one-dimensional null space. But a calibrated pair is not estimating F — it is estimating the essential matrix E, and E carries one structural fact that F does not: its two nonzero singular values must be equal. That single fact spends two more degrees of freedom, dropping E from seven DOF to five. Five DOF means five correspondences should suffice, and indeed five-point solvers do exactly that.

Why care about a sample being minimal? Because the sample is the unit of work inside RANSAC. Robust estimation repeatedly draws a random subset of correspondences, fits a model to just that subset, and then counts how many of the other correspondences agree with it. If a subset contains even one outlier, the model it produces is worthless — so the whole method hinges on drawing an all-inlier subset, and the probability of that collapses as the subset grows. For a correspondence set with inlier ratio w, the expected number of samples needed to hit an all-inlier set is

where s is the sample size and p the desired confidence. The exponent is the whole story: shrinking s from 8 to 5 shrinks the cost exponentially. At w = 0.5 and p = 0.99, an eight-point sample needs on the order of a thousand iterations while a five-point sample needs roughly one hundred and fifty — an eightfold saving, for free, the moment the cameras are calibrated.

The constraints

Recall from the epipolar page that the essential matrix is built from the relative pose — rotation R and translation direction t — as E = [t]× R, and that a calibrated correspondence obeys x̃₂ᵀ E x̃₁ = 0. Three separate facts constrain what E can be.

(i) It is homogeneous — 9 → 8. The constraint x̃₂ᵀEx̃₁ = 0 is unchanged if every entry of E is scaled by the same nonzero number, so E and λE are the same essential matrix. Fixing that gauge — for example by requiring a unit Frobenius norm — spends one of the nine numbers. Eight remain.

(ii) It has rank 2 — 8 → 7. [t]× is skew-symmetric, so [t]× t = t × t = 0: it always has t in its null space and therefore has rank 2, not 3. Multiplying by the invertible rotation R leaves the rank at 2, so E = [t]×R is rank-2 as well: det(E) = 0, always. That is one genuine nonlinear constraint.

(iii) Its two nonzero singular values are equal — 7 → 5. This is the Demazure constraint, and it is exactly the imprint of calibration. Because any essential matrix is a scalar multiple of some [t]×R, its singular-value decomposition can always be written

so the middle singular value equals the largest one, and the smallest is zero. "The two singular values are equal" is two additional constraints (equality is one equation, but here one finds two independent conditions fall out of the E EᵀE structure), which is why the degree count goes 7 → 5. Concretely, the entire class of essential matrices is characterized by the cubic matrix equation

together with det(E) = 0. The trace equation is what forces equal nonzero singular values: writing E = U diag(σ₁,σ₂,σ₃)Vᵀ, it becomes a diagonal condition whose only solutions are σ₁ = σ₂ with σ₃ = 0 (up to an overall scale).

The contrast with F. The fundamental matrix F = K₂⁻ᵀ E K₁⁻¹ has seven degrees of freedom: nine entries, minus one for scale, minus one for det(F) = 0. It has no equal-singular-value constraint, because multiplying E by the arbitrary intrinsics K scrambles the singular values. That single missing constraint is the entire difference between needing eight correspondences and needing five — and, as the demo below shows, it is also the difference between a model that survives a planar scene and one that does not.

How the minimal solver works

Five correspondences give five scalar equations x̃₂ᵀ E x̃₁ = 0 in the nine entries of E. Each is linear in those entries — exactly the same flattened outer-product row the eight-point algorithm uses — so stacking them gives a 5 × 9 matrix A with a null space of dimension at least 4. Taking the SVD of A, the four right-singular vectors belonging to the four smallest singular values give a basis E₁, E₂, E₃, E₄ of that null space, and every solution must be a linear combination

where the coefficient of E₄ has been fixed to 1 (one gauge choice). Substituting that combination into the ten cubic constraints from Step 1 — the determinant condition det(E) = 0 plus the nine entries of 2 E EᵀE − trace(E Eᵀ)E = 0 — produces a system of ten polynomials of degree three in the three unknowns (x, y, z).

That polynomial system is the heart of the algorithm. Nistér's key step is that it can be reduced, by elimination, to a single tenth-degree polynomial in one variable (here z): the solver builds a 10 × 10 action (multiplication) matrix in the quotient ring of the constraint ideal and finds z as the eigenvalues of a companion matrix — modern implementations solve the same polynomial with Jenner–Sturm sequences or a companion-matrix eigenvalue routine. A degree-10 polynomial has up to ten real roots, and each root is back-substituted to recover x and y, yielding up to ten candidate essential matrices. The solver then keeps the geometrically valid ones: a candidate is accepted only if the posed translation puts the correspondences in front of both cameras (cheirality/positive depth), and in a RANSAC loop by the number of inliers it explains.

Two practical notes. First, five-point solvers return multiple roots by design — do not expect a single answer — and they are almost always the sample generator inside RANSAC rather than a stand-alone estimator. Second, the uncalibrated analogue is the seven-point algorithm: seven correspondences give a 7 × 9 matrix whose null space is two-dimensional, so F = F₀ + λF₁ and the rank-2 condition det(F₀ + λF₁) = 0 becomes a cubic in λ, with one to three real candidates. It is the same "minimal sample = polynomial system" story, one constraint weaker.

Interactive

Both panes show the same second image and the same clean corresponding points. The left pane fits the uncalibrated fundamental matrix by the Hartley-normalized eight-point method, rank-2 projected, using a minimal sample of eight correspondences. The right pane fits the calibrated essential matrix from a minimal sample of five correspondences, using the numerical minimal solver described above, and draws its epipolar lines through F = K₂⁻ᵀEK₁⁻¹. Drag scene planarity toward 1: the eight-point constraint matrix becomes ill-conditioned (its σmin/σmid climbs toward 1, the signature of a degenerate null space) while the five-point E residual and equal-singular-value readout stay put. Resample the noise to watch the difference become instability. This is the same separation story as the epipolar page’s DOF-peeling step, now with the calibrated constraint doing the stabilizing.

Two readouts deserve a word of explanation. The five-point ‖E − Etrue‖ is not tiny, and that is expected: a minimal solver is fit to exactly five noisy points, so it is a high-variance estimate. In practice one uses it only as the sample inside RANSAC and then refines E nonlinearly over all its inliers — which is precisely the payoff step the solver performs here when it picks the root that explains every correspondence best. The epipolar residual, not the raw matrix error, is what tells you the lines are right. And the eight-point σmin/σmid is measured over all correspondences, not the eight the fit consumed: a minimal sample always has an exact one-dimensional null space, so only the full matrix reveals the planar degeneracy building underneath.

Recap