Structure from Motion (SfM)

Structure from Motion

Structure from Motion (SfM) jointly recovers a 3D point cloud (structure) and the poses of the cameras that observed it (motion) from an unordered collection of $n\ge 2$ images with overlapping views. It is the general multi-view extension of two-view reconstruction, and produces a sparse reconstruction (one 3D point per matched feature).

Given images $I_1,\dots ,I_n$ with known intrinsics $K$, SfM estimates:

• Camera extrinsics $(R_i,T_i)\in SE(3)$ for each view $i$,
• A set of 3D points $\{X_j\}\subset {\mathbb{R}}^3$ visible across multiple views.

The standard incremental SfM pipeline proceeds as:

1. Feature detection and description (SIFT / ORB) across all images.
2. Pairwise feature matching with RANSAC filtering of the epipolar constraint to reject outliers.
3. Initial pair selection: pick two images with many matches and a wide baseline. Recover their relative pose from the essential matrix, then triangulate matched points to seed the point cloud.
4. Incremental registration: for each new image, find 2D-3D correspondences with existing points, then solve Perspective-n-Point (PnP) to recover its pose.
5. Triangulate new points visible in the registered image but not yet reconstructed.
6. Bundle adjustment (global nonlinear refinement) to jointly optimize all poses and 3D points by minimizing reprojection error:
   $E={\sum }_{i,j}{v}_{ij}\Vert x_{ij}-\pi (K[R_i|T_i]X_j){\Vert }^2,$
   where $v_{ij}=1$ if point $j$ is visible in camera $i$ and $\pi (\cdot )$ is the pinhole projection.

Reconstruction is recovered up to a global similarity transform (rotation, translation, and scale) unless metric priors (e.g., known baseline or calibration object) anchor the absolute scale.

Intuition

Two-view geometry gives the relative pose of one camera with respect to another — but it says nothing about a third view. SfM solves the problem of stitching many pairwise views into a single globally consistent reconstruction, much like how a panorama stitches overlapping images into a common frame.

The central idea is incremental anchoring: start with two views whose geometry is well-constrained (wide baseline, many matches), triangulate a seed point cloud, and then add each new image by finding 2D features that correspond to existing 3D points. Once a new image has enough 2D-3D correspondences, its pose is recovered by solving a minimal geometric problem (PnP), and the growing point cloud both supports and is extended by each new view.

The pipeline is a sequence of locally linear problems (SVD-based initial pair, PnP, DLT triangulation) interleaved with global nonlinear refinement (bundle adjustment) that corrects the drift accumulated by greedy incremental registration.

Properties

Pipeline Structure

(Feature-based front end) SfM begins with detector-descriptor features (SIFT, ORB, SuperPoint) matched pairwise across images.

The front end produces tentative correspondences. Descriptor ambiguity, repeating texture, and moving objects introduce outliers, so RANSAC is applied to each pair using the epipolar constraint as the geometric model: a correspondence $(x,x^{\prime })$ is an inlier iff $(x^{\prime }{)}^{T}Fx\approx 0$.

(Initial pair selection) The two seed images are chosen to maximize reconstructability: many inlier matches, but a sufficiently wide baseline.

A narrow-baseline pair has poorly conditioned triangulation (rays nearly parallel), while a very wide baseline has few matches. A common heuristic: pick the pair with the most inliers subject to a minimum median triangulation angle (e.g., 3°).

(Incremental registration) Each new image is registered by solving Perspective-n-Point for its pose, then triangulating new points.

Once a partial reconstruction exists, each new image $I_k$ is aligned by looking up 2D features in $I_k$ whose descriptors match 3D points already in the cloud. This gives 2D-3D pairs $(x,X)$, and the camera pose $[R_k|T_k]$ that projects each $X$ to its observed $x$ is recovered via PnP (see below).

Perspective-n-Point

(P3P — minimal solver) Three 2D-3D correspondences give a closed-form solution with up to four geometric candidates.

Given three points $X_1,X_2,X_3$ seen at normalized image directions ${\hat{x}}_i=K^{-1}{x}_i$, the distances $d_i=\Vert X_i-C\Vert$ from the camera center $C$ satisfy three law-of-cosines equations in the known angles $\cos {\theta }_{ij}={\hat{x}}_i\cdot {\hat{x}}_j$ and known 3D distances $\Vert X_i-X_j\Vert$. The resulting polynomial system has up to four real roots; a fourth correspondence disambiguates.

(PnP with $n>3$) More correspondences give an overdetermined system solved by least squares, often refined nonlinearly.

With $n\ge 4$ points, a direct linear transform (DLT) estimates $[R|T]$ linearly by solving $A\text{vec}([R|T])=0$, then projects the result onto $SE(3)$ (e.g., via SVD of the rotation block). EPnP is a faster $O(n)$ variant. The DLT solution is typically refined by minimizing reprojection error with Levenberg-Marquardt.

(RANSAC wrapping) PnP runs inside RANSAC because 2D-3D matches still contain outliers.

Repeated minimal fits (P3P samples of three correspondences) followed by inlier counting reject descriptor-based mismatches and erroneous triangulations.

Triangulation and Bundle Adjustment

(Linear triangulation) Given two or more cameras $P_i=K[R_i|T_i]$ observing the same 3D point, its homogeneous coordinates are recovered by stacking the cross-product constraints $x_i\times (P_{i}X)=0$ into $AX=0$.

Each view contributes two linearly independent rows (the third is dependent). The solution $X$ is the right singular vector of $A$ corresponding to the smallest singular value. Because noise makes rays non-intersecting, this gives a least-squares midpoint rather than a true intersection.

(Reprojection error) The gold-standard cost for jointly refining structure and motion is the sum of squared pixel distances between observed and reprojected features.

$E={\sum }_{i,j}{v}_{ij}\Vert x_{ij}-\pi (P_i{X}_j){\Vert }^2$, where $v_{ij}$ is the visibility indicator. This is the negative log-likelihood under i.i.d. Gaussian pixel noise and is the right objective for Gauss-Newton / Levenberg-Marquardt descent.

(Bundle adjustment) Joint nonlinear least squares over all camera poses $\{(R_i,T_i)\}$ and all 3D points $\{X_j\}$ minimizes reprojection error across the entire reconstruction.

The Jacobian has a characteristic sparse block structure (each residual depends on only one camera and one point) that the Schur complement exploits to solve the normal equations in $O(\text{views}\cdot \text{points})$ rather than cubically. Bundle adjustment runs periodically during incremental registration and once at the end.

Reconstruction Ambiguities

(Similarity gauge) Without metric priors, the reconstruction is determined only up to a 7-DoF similarity: overall rotation, translation, and scale.

The reprojection error is invariant under $X_j\to sR{X}_j+T$ and $(R_i,T_i)\to (R_i{R}^T,T_i-s{R}_i{R}^{T}T/s)$. Fixing the world frame (e.g., world = first camera, unit baseline) removes this gauge freedom and is required for numerical stability.

(Degenerate configurations) Pure rotation, planar scenes, and collinear points all produce degenerate SfM problems.

Under pure camera rotation there is no parallax, triangulation fails, and only a homography relates the views. For a planar scene, the essential matrix is not uniquely determined from matches — the correct model is again a homography. These cases must be detected and handled with alternative estimators.

Practical Considerations

(Drift accumulation) Purely incremental registration accumulates error, especially along long sequences.

The solution is periodic bundle adjustment and, for video or loop-closing sequences, explicit loop-closure detection (a new image that matches an old part of the reconstruction), which provides a large-baseline correction.

(Modern implementations) COLMAP, OpenMVG, and Meshroom package the full pipeline with robust heuristics for pair selection, keyframing, and BA scheduling.

These systems operate on unordered internet photo collections and handle reconstructions with $10^4$–$10^5$ images and $10^7$ points.

See Also

• 5.3. Epipolar Geometry — the two-view geometry that seeds SfM
• 5.2. Stereo Geometry — rectified stereo with a known baseline
• Multi-View Stereo — the dense reconstruction that follows SfM
• 4.4.1. RANSAC — robust estimation inside every stage of the pipeline