Structure from motion recovers two unknowns at once from a pile of photographs: where each camera was, and where the world is. Neither can be computed without the other, which is why the pipeline is incremental and why one bad image can poison a reconstruction.
The pipeline, in order
- Feature detection. Find repeatable interest points in every image and describe each with a vector that survives changes in scale, rotation and moderate viewpoint change. SIFT, published by David Lowe in 2004, is still the default in reconstruction software because its descriptors match reliably across wide baselines, which is what this task needs and what cheaper detectors give up.
- Matching. For every image pair, find descriptor correspondences. This is the quadratic step and the one that decides the runtime.
- Geometric verification. Fit a two-view geometric model to each candidate match set with RANSAC and keep only the matches consistent with it. Pairs that survive form the view graph.
- Initialisation. Pick a well-conditioned pair — wide baseline, many verified matches — and reconstruct it: relative pose, then triangulated points.
- Incremental growth. Register the next image by solving perspective-n-point against already-triangulated points, triangulate new points it sees, and repeat.
- Bundle adjustment. Jointly refine all poses and all points, repeatedly, as the reconstruction grows.
COLMAP, described by Johannes Schönberger and Jan-Michael Frahm at CVPR 2016, is the reference implementation of this exact ordering, and its paper is largely about the details that make step 5 not collapse — which image to add next, when to re-triangulate, and how often to run the expensive step 6. Structure-from-Motion Revisited sets out the incremental pipeline and its failure cases.
Matching, and why most matches are wrong
A descriptor match is a nearest-neighbour lookup in a high-dimensional space and it always returns something. On a facade of identical windows, the nearest descriptor is frequently the wrong window. The standard first filter is Lowe’s ratio test: accept a match only if the best distance is meaningfully smaller than the second best — a typical threshold is 0.8 — which discards matches whose feature is ambiguous rather than merely distant.
Even after the ratio test, a large fraction of surviving matches are incorrect. This is why geometric verification is not optional. RANSAC, published by Martin Fischler and Robert Bolles in 1981, samples a minimal set of matches, fits the two-view model, counts how many other matches agree within a pixel threshold, and keeps the best-supported hypothesis. The number of iterations needed follows directly from the inlier ratio:
N = log(1 - p) / log(1 - w^s)
p = probability of drawing at least one all-inlier sample
w = inlier fraction
s = sample size (5 for the essential matrix, 3 for a plane)
with p = 0.99, s = 5:
w = 0.5 -> N = log(0.01) / log(1 - 0.03125) = 145 iterations
w = 0.3 -> N = log(0.01) / log(1 - 0.00243) = 1893 iterations
w = 0.2 -> N = log(0.01) / log(1 - 0.00032) = 14388 iterations
The cost explodes as the inlier fraction falls, which is why the ratio test in front of RANSAC earns its place: it does not have to be a good filter, only good enough to move w from 0.2 to 0.5.
Two-view geometry
Given a point in image A, its match in image B is constrained to a line — the epipolar line — determined entirely by the relative pose of the two cameras. The fundamental matrix encodes that constraint for uncalibrated cameras; the essential matrix does so when the intrinsics (focal length and principal point) are known, which is the normal case when EXIF data is available.
The essential matrix has five degrees of freedom — three for rotation, two for translation direction — and the translation length is not among them. This is the origin of the scale ambiguity that follows the whole reconstruction: the recovered model is correct up to an unknown global scale factor, because a scene twice as large viewed from twice as far produces identical images. Fixing it requires an external measurement: a ground control point, a known object length, a GPS track, or a calibrated stereo rig.
Worked: triangulating one point
Take the simplest case — two cameras with the same intrinsics, aligned and separated horizontally by a baseline B. A world point projects to different horizontal positions in the two images, and the difference is the disparity d in pixels. Depth follows from similar triangles:
Z = f * B / d
f = 800 px (focal length in pixel units)
B = 0.12 m (baseline)
d = 25 px (disparity)
Z = 800 * 0.12 / 25 = 96 / 25 = 3.84 m
now the error. differentiating Z with respect to d:
dZ/dd = -f*B / d^2 = -(Z^2) / (f*B)
a 1 px disparity error at this depth:
dZ = Z^2 / (f*B) = 3.84^2 / 96 = 14.75 / 96 = 0.154 m
the same 1 px error at 10 m:
dZ = 10^2 / 96 = 1.04 m
the same 1 px error at 20 m:
dZ = 20^2 / 96 = 4.17 m
Depth error grows with the square of depth and shrinks linearly with the baseline. That single relation explains most practical advice about photogrammetry: take pictures from further apart than feels necessary, use a longer focal length if you cannot, and do not expect useful geometry on the far background of a scene you photographed from one side of a room. In the general case the cameras are not aligned and the point is found by intersecting two rays that, because of noise, do not actually meet — the usual solution is the direct linear transform, or the midpoint of the shortest segment joining them.
Bundle adjustment
Every triangulated point was computed from poses that were themselves estimated, so errors compound as the reconstruction grows. Bundle adjustment fixes this by optimising everything at once: it minimises total reprojection error — the sum over all observations of the squared pixel distance between where a point was detected and where the current estimate says it should project — over all camera poses, all intrinsics, and all 3D points simultaneously.
The problem has hundreds of thousands of variables and is solved with Levenberg-Marquardt. It is tractable only because the Jacobian is extremely sparse: a given 3D point is seen by a handful of cameras, so almost every camera-point pair contributes nothing. Exploiting that structure — the Schur complement trick, which eliminates the point variables first — is what makes large reconstructions possible at all, and it is why bundle adjustment is a well-defined engineering artefact rather than a generic optimiser call.
The four ways it fails
- Pure rotation. A camera panning on a tripod has no baseline, so nothing can be triangulated — the two views are related by a homography and the depth is unobservable. Reconstruction software detects this and refuses the pair. If your capture was a panorama, no amount of images will produce structure.
- Repeated structure. Identical windows, tiles or fence posts produce matches that are geometrically consistent and semantically wrong, so RANSAC endorses them. The symptom is a reconstruction that folds a building onto itself. More images do not help; different viewpoints that break the symmetry do.
- Textureless and specular surfaces. A white wall or a glass facade has no repeatable features, so it produces no points. The gap in the cloud is not noise to be filtered — it is an absence of measurement, and any later meshing step will invent geometry there. This is one of the main reasons a dense reconstruction is checked against a density gate before meshing.
- Drift on long sequences. A corridor photographed in one direction accumulates small pose errors that bend the reconstruction. Revisiting the start and letting the matcher connect the two ends turns the error into a closed loop that bundle adjustment can distribute — the same idea as loop closure in SLAM, which is essentially this pipeline run online with a motion prior.
Top comments (0)