Structure from Motion

Definition

Given $m$ images of $n$ fixed 3D points with $u_{ij}=P_i{X}_j$, Structure from Motion jointly estimates the camera matrices $P_i$ (motion) and the 3D points $X_j$ (structure). Only the 2D observations $u_{ij}$ are known.

flowchart LR
  A["Images"] -- "data association" --> B["Scene graph"] -- "SfM" --> C["Sparse model"] -- "MVS" --> D["Dense model"]

Typically the motion is estimated first (two-view geometry with the essential matrix), then the structure by triangulation, refined with bundle adjustment.

Paradigm	Idea	Efficiency / Robustness / Accuracy	Examples
Incremental	start with two views, add one view per step (PnP, triangulate, BA)	− / ++ / +	COLMAP, OpenSfM
Global	all poses at once: rotation + translation averaging, then BA	+ / + / +	GLOMAP, OpenMVG, Theia
Hierarchical	cluster the scene graph, reconstruct clusters, merge	++ / − / −

Trap

SfM is scale ambiguous: $u\simeq ({\alpha }^{-1}P)(\alpha X)$. The absolute size of the scene can’t be recovered from images alone.

Appears in

• Lecture 3, The SfM Problem
• Lecture 3, Incremental SfM
• Lecture 3, Global SfM
• Lecture 3, Challenges
• Lecture 1, course overview
• Lecture 8, 3DGS: SfM points initialize the Gaussians
• Lecture 9, Classical vs. learned: COLMAP problems, spectrum of methods

Related concepts

• Point Map
• Epipolar Geometry
• Triangulation
• Bundle Adjustment
• RANSAC
• Point Cloud