Pose by agreement II: images alone

Lesson 4 aligned two scans by making their points coincide, which needs a sensor that measures 3-D directly. A phone measures only pixels, and a pixel is a ray, so what must agree is not points but rays: the two rays of one scene point have to meet. This lesson turns that sentence into one equation per match (the epipolar constraint, empty in a plane, so the lesson leaves Flatland for true 3-D), solves it in closed form from eight matches, survives wrong matches with RANSAC, and refines every camera and every point together by bundle adjustment, the explain–compare–update loop that the rest of the track reuses. It delivers camera poses and a sparse cloud of points, in a frame and at a scale the pixels never fixed.

The thesis, here

A camera pose is right when the rays of every matched pair of pixels meet. One match gives one equation, eight matches a closed-form first answer, and the pixel error of the picture that answer predicts drives a loop (explain, compare, update) that polishes all cameras and points together. The pixels can never fix seven numbers: a frame and a scale.

Linear position

Forced by: Aligning scans has a closed-form answer when the matches are known, and a two-step loop when they are not: match each point to its nearest neighbour, solve, repeat. The loop converges to the nearest consistent answer if it starts close enough. All of it needs a sensor that measures 3D directly. A phone measures only pixels, so there is no scan to align. How can poses be recovered from images alone, and what plays the role of "the scans should coincide"?
New idea: what must agree is the rays: a pose is right when the two rays of every match meet, and the size of the failure is a reprojection error in pixels. Minimising that error over all poses and points, with steps taken in the tangent space of lesson 3, is bundle adjustment: explain (project), compare (residual), update (tangent-space step).
Forces next: Images alone give camera poses and a sparse set of 3D points, up to one global scale, by adjusting both until the points reproject onto the pixels. That is the first model we fitted by comparing its prediction with the data. Now test it on the job it is for: predict a photograph from a camera we did not use. Points show through one another and nothing exists between them. What must a model of geometry provide to answer "what does this ray hit?", and how is it built from noisy depth?

The plan

Seven moves. (1) What can agree when there are no 3-D points, and why the answer needs true 3-D. (2) One equation per match, solved in closed form. (3) The pose out of the solution: four candidates, one chosen by depth, and a scale that is gone. (4) Wrong matches, RANSAC and how many tries it needs. (5) Refining all cameras and points together: explain, compare, update. (6) The directions the data cannot see: the gauge. (7) The exam, and what the result cannot say.

1 · What can agree when there are only pixels

Lesson 4 made two scans agree by moving one until its points sat on the other's. Here the data are photographs. By lesson 1 a pixel is a ray, so a match, a pair of pixels (one per image) that show the same scene point, is a pair of rays, and nothing yet says where along them the point is. Three things could be asked to agree:

Ask that…	What it needs	What goes wrong
the matched pixels coincide	nothing	they do not: in the widget the two pixels of a match differ by 40 px on average, by amounts that depend on the unknown depth Z (parallax f·b/Z, lesson 1)
the 3-D points coincide (lesson 4)	the points	there are none: triangulating them needs the poses we are looking for
the two rays meet	the pose only	nothing: each ray is a whole line, so the unknown depths never enter the condition, only the pose does

Only the third involves the unknown pose and none of the unknown depths. Its price is that the lesson works in true 3-D instead of Flatland. Count. A scene point has two unknowns in a plane and three in space. A match measures four numbers in space (two pixels, two coordinates each) but only two in a plane (one coordinate per image). In the plane every match leaves 2 − 2 = 0 constraints on the pose: two lines in a plane cross (unless parallel), so every pose explains every match. In space a match leaves 4 − 3 = 1: two lines in space generally miss each other, and these meet only if the pose is right. One constraint per match is all the pixels offer, and it is enough.

2 · One equation per match

Write the pose as the motion from camera 1 to camera 2: a point at x₁ in camera 1's frame is at x₂ = R x₁ + t in camera 2's. Use normalised pixels p = ((u − c_x)/f, (v − c_y)/f, 1), the direction of the pixel's ray with z-component 1. A scene point at depth Z₁ in camera 1 is x₁ = Z₁ p₁, so in camera 2 it satisfies Z₂ p₂ = Z₁ R p₁ + t. Cross with t to remove the last term, then dot with p₂ to remove the left side: 0 = Z₁ p₂·(t × R p₁). Since Z₁ > 0,

p₂^T E p₁ = 0, E = [t]_× R, [t]_× v = t × v

Both depths are gone. E is the essential matrix (Longuet-Higgins, 1981). Geometrically E p₁ is a line in image 2, the picture of camera 1's ray, and the match's second pixel must lie on it: the one constraint of §1. How many numbers is E? The rotation has 3, the translation 3, and scaling t changes nothing, so 5. As a matrix it has 9 entries, 8 up to scale, but E E^T = [t]_×[t]_×^T = |t|² I − t t^T has eigenvalues |t|², |t|², 0: its singular values are two equal numbers and a zero, which costs three of the 8 (one for the zero, two for the equal pair): 8 − 3 = 5. Five matches suffice in principle (Nistér's five-point solver, 2004, returns up to ten candidates). Eight make the problem linear: p₂^T E p₁ is a dot product of the nine entries of E with (p₂ ⊗ p₁), so stack one such row per match into a matrix A and take the unit vector minimising |A e|, the eigenvector of A^TA with the smallest eigenvalue. Noise makes the result a general 3×3 matrix, so project it: with its singular values (a, b, c), keep U diag(μ, μ, 0) V^T with μ = (a + b)/2, the nearest essential matrix.

Normalised pixels keep every entry of A of order 1, the kind of normalisation that Hartley (1997) showed brings the eight-point method close to the best iterative ones. How good is the answer? Mean of 100 noise draws, 80 matches, the widget's cameras 0 and 2 (28° apart):

pixel noise σ	0	0.5 px	1 px
rotation error	0°	0.27°	0.54°
baseline-direction error	0°	0.50°	1.02°
epipolar error of this E (RMS, pixels)	0	1.16	2.33

The error is proportional to σ, and exact data give an exact answer. But look at the last row. At σ = 0.5 the true pose leaves each match 0.50 px from its epipolar line, which is the noise itself; the eight-point pose, a quarter of a degree from the truth, leaves 1.16 px (a quarter of a degree is 2.5 px of image motion at f = 520 px). It is a very good start and not the best answer: it minimises an algebraic quantity, |A e|², not the pixel error. §5 fixes that.

3 · From E back to a pose, and the scale that is gone

Write E = U diag(1, 1, 0) V^T, with t scaled to unit length and U, V rotations (the zero singular value lets us flip the sign of a last column). Since t^TE = t^T[t]_×R = 0, the translation is the left null vector, the third column u₃ of U, up to sign. With W a quarter turn about z, [u₃]_× = U W diag(1,1,0) U^T and W commutes with diag(1,1,0), so R = U W^T V^T with t = u₃ reproduces E, and so does R = U W V^T with t = −u₃ (W² is a half turn). The equation cannot tell E from −E, which gives the other two signs. That makes four candidates: two rotations that differ by a half turn about the baseline, each with either sign of t. Only one places the scene in front of both cameras. Triangulate every match with each candidate (lesson 2; the rays miss each other, so take the point that fits both best) and count the points with positive depth in both: this is cheirality. On the widget's 80 matches the four counts are 80, 0, 0 and 0.

The translation came out a unit vector, and it had to. Scale the scene by s and the baseline by s: both depths become sZ₁ and sZ₂, p₁ and p₂ do not change, and no pixel moves (scaling the widget's scene by 3.7 moves none by 10⁻⁹ px). This is lesson 1's crate and wall painting the same pixels, once more. The frame in which we choose to write the world adds 3 rotations and 3 translations to the one scale: 3 + 3 + 1 = 7 numbers that no set of photographs can fix, the similarity gauge (Triggs, McLauchlan, Hartley and Fitzgibbon, 2000). A metric scale needs something that is not a picture: a known baseline, an inertial sensor, a range sensor, an object of known size.

4 · Wrong matches, and how many tries RANSAC needs

Matches come from comparing the appearance of patches, and some are wrong. A wrong match disagrees with the E that the right matches share, but the linear solution minimises a sum of squares, and a wrong match has a big residual to square. In the widget's data, 4 wrong matches out of 80 (5%) take the eight-point rotation error from 0.28° to 28°; with 20 wrong (25%) the rotation is 31° off and the baseline direction 112°.

Let the matches vote. Eight right matches determine an E up to their noise, and then the other right matches lie near the epipolar lines it predicts while wrong ones do not. Measure "near" by the distance, in pixels, that a match must move for its two rays to meet, to first order: d = |p₂^TE p₁| / ‖∇‖, the equation's value over the length of its gradient with respect to the four pixel coordinates (the Sampson distance). Call a match agreeing when d < 4 px. RANSAC draws 8 matches at random, fits E, counts the agreeing matches, repeats, keeps the hypothesis with the most agreement and refits on its agreeing set.

How many draws? Let a fraction w of the matches be right and the draws independent. One draw of s matches is clean with probability w^s, all N draws contain a wrong match with probability (1 − w^s)^N, and demanding that this be at most 1 − P, for a chosen confidence P, gives

N = log(1 − P) / log(1 − w^s)

right fraction w	sample size s	w^s	N for P = 0.99 (rounded up)	simulated success in N draws
0.75	8	0.100	44	0.991
0.5	8	0.0039	1177	0.985
0.5	5	0.031	146	0.989
0.3	8	0.000066	70188	not run

The simulation draws 8 or 5 of 500 matches without replacement, at least 6000 times per row, and counts how often at least one draw is clean. The count grows exponentially with the sample size, so a minimal solver is worth having: the five-point solver, intended as a RANSAC hypothesis generator, needs 146 draws where the eight-point needs 1177 at w = 0.5. Sampling without replacement from a short list is slightly worse than the formula: with 80 matches the same 1177 draws succeed 0.96 of the time. The loop does not know w; it estimates it from the largest agreeing set so far and stops when its trials reach N(ŵ). On the widget's data with 25% wrong it keeps the 60 right matches, rejects all 20 wrong ones and recovers the pose to 0.4°; over 100 noise draws it lands within 2° of the truth 97 times, against none for the plain eight-point.

5 · Refine everything together: explain, compare, update

The eight-point answer minimises an algebraic quantity from two images. Ask instead for what has a physical meaning, and use every image: choose all camera poses T_i and all points X_j so that the picture they predict is the picture we took. Explain: project every point into every camera, û_ij = π(T_i X_j) with π(x, y, z) = (c_x + f x/z, c_y + f y/z). Compare: the residual r_ij = û_ij − u_ij, and the disagreement L = ½ Σ ‖r_ij‖² in pixels². Update: move poses and points to lower it. This is bundle adjustment, "jointly optimal structure and viewing parameter estimates" in the words of Triggs et al. (2000), and it is the template of the fits in lessons 8 to 10: a model explains the data, a residual compares them, a step in the model's natural coordinates updates it. Lesson 4's match–solve–repeat was a relative of it.

The update. Linearise, r(θ + δ) ≈ r + Jδ, where θ stacks all the unknowns and J holds the derivatives of every residual with respect to every unknown. The Gauss–Newton step minimises |r + Jδ|², which gives J^TJ δ = −J^Tr. Levenberg–Marquardt damps it, (J^TJ + λ diag(J^TJ)) δ = −J^Tr: small λ is Gauss–Newton, which is very fast near a solution with small residuals; large λ is a short downhill step. Accept a step only if the error fell and divide λ by 3; otherwise multiply it by 4 and retry. The unknowns are not a flat vector: a camera lives on SE(3), and lesson 3's rule applies, so its step is a twist ξ = (ρ, ω) applied through the exponential, T ← exp(ξ) T (lesson 3 multiplied on the right; on the left, ξ acts on camera-frame coordinates, which keeps the derivatives below short), while a point takes a plain 3-vector.

The derivatives have a closed form. For a point at x_c = (x, y, z) in a camera, J_π = ∂π/∂x_c = (f/z) [[1, 0, −x/z], [0, 1, −y/z]]. A twist moves x_c by ρ + ω × x_c and a shift δX moves it by R δX, so ∂r/∂ρ = J_π, ∂r/∂ω = −J_π[x_c]_× and ∂r/∂X = J_πR. Each residual touches one camera and one point, so J^TJ is mostly zeros; Triggs et al. eliminate the point blocks with a Schur complement and COLMAP (Schönberger and Frahm, 2016) does too. Our problem, 5 cameras and 20 points, is small enough to solve whole: 90 unknowns, 200 residuals.

6 · What the data cannot see: the gauge

Move the whole scene by X → sQX + c (rotate by Q, scale by s, shift by c) and move the cameras with it. Every pixel stays where it was, so every residual and the error are unchanged. The error therefore has a 7-dimensional valley floor: J maps those 7 directions to zero, J^TJ has 7 zero eigenvalues, and the Gauss–Newton equation has no unique solution, since any multiple of a null vector can be added to δ. The damping of LM hides this: it makes the matrix invertible, and along those directions the step is then set by the damping, not by the data. The cure is to pin 7 numbers, camera 0's pose (6) and one component of camera 1's translation (the scale); delete those columns and the matrix is positive definite. The answer then lives in the frame those choices define, so comparing it with the truth needs lesson 4's SVD alignment with a scale added (Umeyama, 1991). Pinning leaves k free unknowns, and k unknowns fitted to m noisy residuals swallow k of the m directions of the noise, so the RMS to expect at the optimum is σ√((m − k)/m), the amber line in the widget. The widget also draws the eigenvalues.

Two views, then five: eight-point, RANSAC, bundle adjustment

Seen from above (x right, z up): grey is the truth, colour the estimate, aligned as in §6. Two views: thin lines are the epipolar lines E p₁ of every fifth match; a green dot should sit on its line, red dots are wrong matches. Five views: the 20 points start off the truth by the start-error factor; dots are observed pixels, rings the predictions, red segments the residuals; below them, RMS per iteration and the smallest eigenvalues of JᵀJ; the third panel (violet) is a sixth camera the fit never saw.

pixel noise σ 0.50 px stage wrong matches 0 % start error ×1.5 gauge

rotation error

—

baseline-direction error

—

epipolar RMS, this pose

—

epipolar RMS, true pose

—

matches that agree

—

trials · formula N

—

in front, 4 candidates

—

Show the core JS

BA.trials = function (w, s, p) { var q = Math.pow(w, s); return q >= 1 ? 1 : Math.ceil(Math.log(1 - p) / Math.log(1 - q)); };
...
var r = [sc.cx + f * x * iz - obs[i][j][0], sc.cy + f * y * iz - obs[i][j][1]];
var Jp = [[f * iz, 0, -f * x * iz * iz], [0, f * iz, -f * y * iz * iz]], ci = 6 * i, pj = 6 * m + 3 * j;
var q = Jp[row], jc = [q[0], q[1], q[2], y * q[2] - z * q[1], z * q[0] - x * q[2], x * q[1] - y * q[0]];
...
var Hd = Float64Array.from(S); for (k = 0; k < m; k++) Hd[k * m + k] += lam * (S[k * m + k] + 1e-12);
var d = G3._solveSPD(Hd, rhs, m);
var st2 = BA.retract(st, d, free, L.n), c2 = BA.cost(sc, st2, obs);
if (c2 < L.cost) return { st: st2, cost: c2, lam: Math.max(lam / 3, 1e-12), ok: true };
lam *= 4;
...
for (i = 0; i < m; i++) out.cams[i] = se3.compose(se3.exp([full[6 * i], full[6 * i + 1], full[6 * i + 2], full[6 * i + 3], full[6 * i + 4], full[6 * i + 5]]), st.cams[i]);

What to try. The page opens on two views, eight-point on all 80 matches, σ = 0.5 px, none wrong: the rotation is off by 0.28° and the baseline direction by 0.51°, the four candidates have 80, 0, 0, 0 points in front, and the matches lie 1.08 px (RMS) from the epipolar lines of this E against 0.51 px from those of the true one (§2). Set σ to 0 and both errors vanish; at 1.5 px they are 3.1 times larger. Drag the wrong matches to 25%: the rotation error jumps to 31° and the baseline direction is 112° off. Switch to RANSAC: back to 0.38°, with 60 of 80 matches agreeing (all the right ones) after 145 trials. The formula asks 44 for the fraction it finally found, but the loop learns that fraction only as its best agreeing set grows. Now take five views, bundle adjustment, start error ×1.5: the reprojection RMS starts at 18.9 px, is 1.24 after one LM step and 0.42 after two, and after twelve sits at 0.39 px, on the floor σ√(117/200) = 0.38 px (m = 200 residuals, k = 83 free unknowns); camera 2 against camera 0 is then off by 0.19° and 0.20°. Over 100 noise draws bundle adjustment averages 0.18° and 0.26°, the eight-point on two of the same images 0.70° and 1.26°. Set σ to 0: the RMS falls below 10⁻¹² px, under 10⁻¹⁰ after 8 steps. Start error 0 begins at the truth, at 0.53 px for this noise draw, and the RMS goes down to 0.39 px: the fit explains part of the noise. Leave the gauge free: 7 zero eigenvalues appear (the next is 1.6e2) and camera 0 wanders 0.06 m; fixed, the smallest is 3.6 and camera 0 stays. The held-out panel shows 20 predicted points 0.51 px (RMS) from the truth, out of 307,200 pixels.

Road not taken · filter instead of batch, features instead of pixels

Keep only the newest camera and a covariance, and fold each image in as it arrives (an extended Kalman filter). It is cheap and suits a moving robot, but each old residual is linearised once, at the estimate of its moment, and never revisited, so a linearisation error is frozen into the answer; batch bundle adjustment re-linearises every residual at every iteration. SLAM is this loop run online (lesson 14). The other road, comparing pixel intensities instead of matched feature positions, keeps the loop and changes the residual; it needs a depth for every pixel, and lessons 8 and 9 take it.

7 · What the points cannot answer

Give the result the exam of lesson 1. A held-out camera, between cameras 3 and 4, was never in the fit. Express the reconstruction in the world's frame by the closed-form alignment of §6, which needs a fitted size (the cloud came out ×1.05 in this run: the scale was ours to choose), project the 20 points into the new camera and compare them with where they really land. After the fit they are 0.51 px away (RMS), against 17.6 px at the start: for the points, an excellent prediction. But a photograph has 307,200 pixels, and 20 points speak for 20 of them: 0.0065%, or 0.16% with a 5 × 5 patch each. For every other pixel the model has no answer, because nothing in a cloud says what lies between its points or which point hides which.

What this lesson did not do

It did not say where a good start comes from for many images. Real pipelines run incrementally (RANSAC verification, initialisation, registration, triangulation, bundle adjustment, outlier filtering, as in COLMAP); the widget starts from the truth moved by a controlled amount. It did not find the matches, and it assumed known intrinsics and no lens distortion. It did not treat the cases where the equation says nothing: a plane (the nine-column system then has a null space of dimension 3, not 1) and a pure turn (t = 0, so E = 0; lesson 1). It did not fix the scale, which needs a cue from outside the images. Lessons 8 to 10 keep this loop and replace the projection by a renderer.

Common mistakes / failure modes

"two views give the translation"

They give its direction. Scale the scene and the baseline together and no pixel moves, so the length is gone (§3).

"a few wrong matches only add a little noise"

Least squares squares them: 4 wrong matches of 80 take the rotation error from 0.28° to 28° (§4).

"the best pose has the smallest error"

The fit goes below the noise because it absorbs some of it: 0.53 px at the truth, 0.39 after the fit. It minimises disagreement with the data, not distance to the truth (§6).

"a singular J^TJ means a bug"

Seven zero eigenvalues are the gauge: a frame and a scale the pixels cannot see. Pin seven numbers (§6).

Checkpoint exercise

Try it

A rig has 4 cameras and 15 points seen in every image, with pixel noise σ = 1 px. (a) How many unknowns and residuals does bundle adjustment have, how many unknowns are free once the gauge is fixed, and what RMS should a converged fit show? (b) A matcher returns 60% right matches. How many RANSAC trials for P = 0.95 with an 8-match sample, and with a 5-match sample? Answer: (a) 6·4 + 3·15 = 69 unknowns and 2·4·15 = 120 residuals; the 7 gauge numbers leave k = 62 free, so m − k = 58 and the RMS is 1·√(58/120) = 0.70 px. (b) 0.6⁸ = 0.0168, so N = log 0.05 / log(1 − 0.0168) = 177; with 5 matches 0.6⁵ = 0.078 and N = 38.

Where this points next

Images alone have given camera poses and a sparse cloud, in a frame and at a scale the pictures never fixed. On the exam the cloud is accurate where it speaks: in a camera it never saw, its 20 points land 0.51 px from where they belong. But it speaks at 20 of 307,200 pixels, 0.0065% of the photograph, and a point has no extent, no opacity and no front or back. What must a model of geometry provide to answer "what does this ray hit?", and how is it built from noisy depth?

Takeaway

With no range sensor, what must agree is the rays: a pose is right when the two rays of every match meet. In a plane that is no condition at all, so the lesson works in 3-D, where each match leaves one constraint, p₂^TE p₁ = 0 with E = [t]_×R. Eight matches solve it linearly, four candidates come out and cheirality picks one, but the baseline length is gone: pixels fix a pose only up to seven numbers, a frame and a scale (the gauge). Wrong matches wreck the linear solution, and RANSAC repairs it with N = log(1−P)/log(1−w^s) random tries. Bundle adjustment polishes all cameras and points by the loop explain (project), compare (reprojection residual), update (damped Gauss–Newton, cameras moved by twists); its normal matrix has seven zero eigenvalues until the gauge is pinned. The result predicts 20 pixels of a new photograph very well and says nothing about the rest.

Interview prompts

Why does recovering pose from images need true 3-D, and what does one match constrain? (§1 — a match gives 4 numbers for a point with 3 unknowns, so 1 constraint; in a plane 2 for 2, so none.)
Derive the epipolar constraint and count the degrees of freedom of E. (§2 — Z₂p₂ = Z₁Rp₁ + t, cross with t, dot with p₂; 3 + 3 − 1 = 5.)
Why does one E give four poses, and how is the right one chosen? (§3 — the sign of E and the half-turn ambiguity; cheirality keeps the points in front of both cameras.)
Why is the translation known only up to scale, and what else is lost? (§3 — scaling scene and baseline together moves no pixel; with the world frame, 3 + 3 + 1 = 7 numbers.)
Derive the number of RANSAC trials. What does a 5-point solver change? (§4 — (1 − w^s)^N ≤ 1 − P; exponential in s: 146 against 1177 at w = 0.5.)
What are the unknowns, residual and update of bundle adjustment, and why is the camera step a twist? (§5 — poses and points; reprojection error; damped Gauss–Newton with T ← exp(ξ)T on SE(3).)
Why does J^TJ have seven zero eigenvalues, and what do you do about it? (§6 — the gauge leaves every residual unchanged; pin camera 0 and one translation component.)
Does a 0.4 px reprojection error mean the model predicts a new photograph? (§7 — it predicts 20 pixels of 307,200; nothing is said between the points.)

Companion reads: Computer Vision · 05 Multi-view, depth and SLAM (the survey of this topic), Computer Vision · 04 Cameras and projection geometry (the pinhole model) and Computer Graphics · 02 Transforms and spaces (rotations).