Structure from motion

A moving camera sees the same scene from many places. Structure from motion recovers both the camera trajectory and the 3-D scene from nothing but the images — a chicken-and-egg problem, since knowing the poses makes the structure easy and knowing the structure makes the poses easy. This page works through how the deadlock is broken: the epipolar constraint that relates two views without knowing anything, triangulation and its brutal dependence on parallax, and the scale that monocular vision can never recover.

Symbols used on this page are defined in the Nomenclature → camera & multi-view geometry.

The refinement step that ends every SfM pipeline is on the bundle adjustment page; pose-from-known-structure is on the PnP page.

1 · The pipeline

Steps 1–3 are the front end and are about correspondence; steps 4–5 are the back end and are about geometry and optimisation. The division matters because the failure modes are completely different: front-end failures are wrong matches, back-end failures are degenerate geometry and drift.

2 · Two-view geometry

2.1 The epipolar constraint

Two cameras observing the same point, plus the two optical centres, are coplanar — the point, the two rays and the baseline all lie in one epipolar plane. Writing that coplanarity as a triple product in the first camera's frame, with the second camera at $(\mathbf R, \mathbf t)$:

$$ \hat{\mathbf u}_2^\top \left(\mathbf t \times \mathbf R\,\hat{\mathbf u}_1\right) = 0 \qquad\Longleftrightarrow\qquad \hat{\mathbf u}_2^\top\,\mathbf E\,\hat{\mathbf u}_1 = 0, \qquad \mathbf E = [\mathbf t]_\times \mathbf R . $$

In pixel coordinates, with calibration folded in, the same statement is $\tilde{\mathbf x}_2^\top \mathbf F \tilde{\mathbf x}_1 = 0$ with $\mathbf F = \mathbf K_2^{-\top}\mathbf E\,\mathbf K_1^{-1}$. This is remarkable: it constrains correspondences without knowing the scene or the motion, which is what makes bootstrapping possible at all. Its practical use is as a one-dimensional search constraint and as an outlier test — a match violating it is wrong.

2.2 Estimating E and F

The 5-point algorithm is strongly preferred for calibrated cameras, and the reason is the RANSAC trial count from RANSAC §3: at $w = 0.5$, $s = 5$ needs 146 trials while $s = 8$ needs 1177. It also avoids a real trap — the 8-point algorithm becomes degenerate for planar scenes, which are extremely common (building facades, floors, tabletops), while the 5-point algorithm handles them.

2.3 Decomposing E

Given $\mathbf E$, the relative pose follows from its SVD $\mathbf E = \mathbf U\boldsymbol\Sigma \mathbf V^\top$. There are four combinations:

$$ \mathbf R \in \left\{\mathbf U\mathbf W\mathbf V^\top,\; \mathbf U\mathbf W^\top\mathbf V^\top\right\}, \qquad \mathbf t \in \left\{+\mathbf u_3,\; -\mathbf u_3\right\}, \qquad \mathbf W = \begin{bmatrix}0&-1&0\\1&0&0\\0&0&1\end{bmatrix}. $$

The four correspond to two rotations times two translation signs — geometrically, the "twisted pair" and a baseline reversal. Only one places the observed points in front of both cameras, so the disambiguation is the cheirality test: triangulate a point with each candidate and keep the one giving positive depth in both views. With noise, test several points and take a majority vote.

3 · Triangulation

3.1 The linear method

With two known camera matrices $\mathbf P_1, \mathbf P_2$ and matched points, each observation gives two linear constraints on the homogeneous 3-D point. Using the cross-product form $\tilde{\mathbf x} \times \mathbf P\tilde{\mathbf X} = \mathbf 0$ and stacking:

$$ \mathbf A\,\tilde{\mathbf X} = \mathbf 0, \qquad \mathbf A = \begin{bmatrix} u_1\,\mathbf p_1^{3\top} - \mathbf p_1^{1\top} \\ v_1\,\mathbf p_1^{3\top} - \mathbf p_1^{2\top} \\ u_2\,\mathbf p_2^{3\top} - \mathbf p_2^{1\top} \\ v_2\,\mathbf p_2^{3\top} - \mathbf p_2^{2\top} \end{bmatrix} \in \mathbb{R}^{4\times4}, $$

solved as the right singular vector of the smallest singular value. This is the DLT triangulation: fast, trivially extended to $n$ views, and statistically wrong — it minimises an algebraic residual, not reprojection error, and the homogeneous scaling weights the views unevenly. Use it to initialise, then refine by minimising

$$ \min_{\mathbf X} \sum_{i} \left\| \mathbf x_i - \pi\!\left(\mathbf P_i \mathbf X\right)\right\|^2 , $$

which for two views has a known closed-form optimal solution (Hartley & Sturm's polynomial method) and for many views is a tiny 3-parameter Gauss-Newton.

3.2 Parallax controls everything

The conditioning of triangulation is governed by the parallax angle $\alpha$ subtended at the 3-D point by the two camera centres. For small $\alpha$, with bearing noise $\sigma_\theta$ and baseline $B$:

$$ \sigma_Z \;\approx\; \frac{Z^2}{B}\,\sigma_\theta \;=\; \frac{Z\,\sigma_\theta}{\alpha} \quad\text{(small angle, } \alpha \approx B/Z ) . $$

This is the same $Z^2$ law as stereo — unsurprisingly, since stereo is triangulation with a fixed baseline. The consequences:

• Depth error grows quadratically with distance and falls only linearly with baseline.
• The uncertainty is strongly anisotropic — a long thin ellipsoid aligned with the line of sight. Treating a triangulated point as having isotropic uncertainty is a significant modelling error.
• At low parallax the depth distribution is skewed and heavy-tailed; the mean depth is not $1/\overline{(1/Z)}$ and may not usefully exist.

3.3 The sim

The simulation linearises the two-bearing measurement and plots the exact position covariance. Things to try:

• Set the baseline small or the depth large. The ellipse stretches along the line of sight — the elongation readout climbs into the tens or hundreds. That is depth becoming unobservable while lateral position stays well determined.
• Watch the rule-of-thumb line: $\sigma_Z \approx Z^2\sigma_\theta/B$ tracks the exact value closely at small parallax and departs as parallax approaches 90°, where the ellipse becomes round.
• Push the parallax below about 1.5° and the warning fires — this is the pure-rotation failure of monocular SfM.

4 · Degeneracies

SfM has more ways to be ill-posed than most estimation problems, and the dangerous thing is that most of them still return an answer.

5 · Growing a reconstruction

5.1 Choosing the initial pair

The seed pair disproportionately determines whether the whole reconstruction succeeds, because every later camera is registered against structure that this pair created. Good criteria: many verified inlier matches, wide parallax distribution, and a low homography-inlier ratio — because a high one means the scene is planar or the motion is pure rotation, both of which make a terrible seed. Choosing the pair with the most matches is the naive approach and often picks two nearly identical frames, which is the worst possible choice.

5.2 Incremental vs global

A middle path is common and effective: hierarchical SfM builds small clusters independently, solves each, then merges — getting much of the incremental robustness at closer to global cost.

5.3 Scale and drift

Two distinct problems get conflated. Scale ambiguity is the single unknown global factor; it is benign and fixed by one external measurement — a known object size, a GNSS baseline, wheel odometry, or a stereo pair. Scale drift is worse: in an incremental pipeline each new triangulation inherits scale from existing structure, and small errors compound, so the scale factor changes slowly along the trajectory. A long monocular corridor run comes back with the far end reconstructed at a different scale from the near end — which a rigid-body loop closure cannot fix. The remedies are to close loops in a similarity group (7-DoF $Sim(3)$ rather than 6-DoF $SE(3)$), or to remove the freedom entirely with a metric sensor. The pose-graph page develops the $Sim(3)$ formulation.

6 · The front end

6.1 Features

The learned matchers matter more than they might appear, precisely because of the trial-count formula: they raise the inlier ratio $w$, and RANSAC cost depends on $w$ exponentially. Improving the front end is usually the cheapest way to make the back end fast and reliable.

6.2 Match filtering

The standard cascade, each stage cheap and each removing a different error class:

• Lowe's ratio test. Accept a match only if the best descriptor distance is clearly better than the second best, typically $d_1/d_2 \lt 0.7$ to $0.8$. This is the single most effective filter, because a repeated pattern produces two near-equal candidates and the ratio test rejects the pair outright rather than guessing.
• Mutual / cross-check. Keep only pairs that are each other's best match.
• Geometric verification. RANSAC on $\mathbf E$ or $\mathbf F$; also produces the relative pose as a by-product.
• Track consistency. A feature track that visits the same image twice, or that is inconsistent across a triplet of views, indicates a bad merge.

7 · Practical checklist

• Normalise coordinates (Hartley) before any linear estimation.
• Use the 5-point algorithm when calibrated — fewer RANSAC trials and no planar degeneracy.
• Always run the cheirality check to pick among the four decompositions of $\mathbf E$.
• Test for pure rotation and for planarity by fitting a homography in parallel, and branch on the result rather than triangulating blindly.
• Gate triangulation on parallax, and store points in inverse depth when parallax is marginal.
• Carry anisotropic point covariances into PnP and BA; a triangulated point is an elongated ellipsoid, not a sphere.
• Choose the seed pair on parallax, not on match count.
• Bundle-adjust regularly, not just at the end — drift compounds and a late BA may not recover.
• Close loops in $Sim(3)$ for monocular pipelines, to absorb scale drift.
• Fix scale with one external measurement and state clearly in the interface that the raw reconstruction is scale-free.

8 · Further reading

• Hartley & Zisserman, Multiple View Geometry in Computer Vision, 2nd ed. Chapters 9–12 for two-view geometry and triangulation. The canonical reference.
• Szeliski, Computer Vision: Algorithms and Applications, 2nd ed., chapter 11. Freely available and the best modern overview of the whole pipeline.
• Nistér (2004), "An Efficient Solution to the Five-Point Relative Pose Problem," IEEE TPAMI 26(6).
• Hartley (1997), "In Defense of the Eight-Point Algorithm," IEEE TPAMI 19(6). The paper that established why normalisation is essential.
• Hartley & Sturm (1997), "Triangulation," CVIU 68. The optimal two-view method and a careful comparison of the alternatives.
• Civera, Davison & Montiel (2008), "Inverse Depth Parametrization for Monocular SLAM," IEEE T-RO 24(5). Why inverse depth is the right parameterisation.
• Schönberger & Frahm (2016), "Structure-from-Motion Revisited," CVPR. The COLMAP paper — the most useful single reference on making incremental SfM actually robust.
• Snavely, Seitz & Szeliski (2006), "Photo Tourism: Exploring Photo Collections in 3D," SIGGRAPH. The work that showed unordered internet photos could be reconstructed.
• Mur-Artal & Tardós (2017), "ORB-SLAM2," IEEE T-RO. Real-time SfM with loop closing and the $Sim(3)$ treatment of scale drift.
• Sarlin et al. (2020), "SuperGlue: Learning Feature Matching with Graph Neural Networks," CVPR.

Related pages: Bundle adjustment · PnP · Stereo · RANSAC · GraphSLAM & pose graphs