structure from motion

Structure from motion takes an unordered pile of photographs of a scene — say a few hundred tourist snapshots of a cathedral, taken at different times by different cameras — and reconstructs two things at once: where each camera was and how it was oriented (the motion), and a sparse cloud of 3D points marking distinctive scene features (the structure). The name captures the duality: as the camera moves, the way features slide across the images encodes both the camera's path and the points' positions, and SfM untangles the two from each other.

The pipeline begins with features. A detector like SIFT (or a learned descriptor) finds repeatable keypoints in each image and describes their local appearance so the same world point can be recognized across photos despite changes in scale, rotation, viewpoint, and lighting. These tentative matches are then geometrically verified: for each image pair, robust estimation (RANSAC fitting a fundamental or essential matrix) keeps only matches consistent with a single rigid two-view geometry, discarding the many spurious ones. The surviving matches are chained into tracks — a track is one physical 3D point seen across several images.

Reconstruction then proceeds either incrementally or globally. Incremental SfM, embodied by the widely used COLMAP, starts from a well-chosen image pair, triangulates initial points, and then repeatedly adds one more camera by solving its pose from already-reconstructed points (the Perspective-n-Point problem), triangulates new points, and periodically runs bundle adjustment to keep errors from accumulating. Global SfM instead estimates all camera rotations and then translations together in one shot, which is faster and avoids drift but is more sensitive to bad matches. Either way the engine of accuracy is bundle adjustment, the joint nonlinear refinement of all cameras and points.

The honest limitation is scale: from images alone the entire reconstruction is determined only up to an unknown similarity transform — you recover the shape and the relative camera trajectory perfectly, but not the absolute size, position, or orientation in the real world. To fix the scale you add external information: a known distance in the scene, GPS tags, or sensor fusion with an IMU. SfM produces a sparse model; turning it into dense geometry is the job of multi-view stereo, which uses the camera poses SfM provides.