Chapter 4: Multi-View Geometry

A typical SfM pipeline follows these steps: (1) feature detection (SIFT, SuperPoint) finds distinctive points in each image, (2) feature matching finds correspondences between image pairs, (3) geometric verification uses RANSAC with the fundamental/essential matrix to reject incorrect matches, (4) an initial pair is selected and reconstructed using the essential matrix, (5) new cameras are added one at a time via PnP (perspective-n-point), (6) new 3D points are triangulated from the added camera, (7) bundle adjustment refines all parameters, (8) steps 5-7 repeat until all cameras are registered.

The first two images bootstrapping the reconstruction must be chosen carefully. The ideal initial pair has: (1) sufficient parallax (wide baseline) for accurate triangulation, (2) many feature matches for a robust essential matrix estimate, (3) no degenerate configuration (not a pure rotation, which makes the essential matrix estimation ambiguous). In practice, pairs are scored by the number of inliers after RANSAC and the triangulation angle distribution. Pairs where the median triangulation angle is less than 2 degrees should be avoided.

After the initial pair, new cameras are added one at a time. For each candidate camera, the algorithm: (1) finds 2D-3D correspondences between the new image's features and existing 3D points, (2) estimates the camera pose using PnP + RANSAC, (3) triangulates new 3D points from the newly registered camera and its neighbors, (4) runs local or global bundle adjustment. The order of camera addition matters: cameras with more 2D-3D correspondences are registered first (they have more constraints, leading to more accurate poses). After every few cameras, global BA is run to prevent drift.

SIFT (Scale-Invariant Feature Transform) finds keypoints at extrema of a difference-of-Gaussians scale space, assigns each a dominant gradient orientation, and describes the surrounding patch with a 128-dimensional histogram of gradient orientations over a 4 by 4 grid of cells. That makes it invariant to scale and rotation and tolerant to moderate viewpoint and lighting change, and it has been the default for SfM since 2004. Matching takes each descriptor's nearest neighbour, then applies Lowe's ratio test: keep the match only if the nearest distance is below 0.8 times the second-nearest. Repeated textures still defeat it.

SuperPoint (2018) is a self-supervised network that detects keypoints and computes 256-dimensional descriptors in one forward pass. It is first trained on synthetic shapes with known corners, then adapted to real images by homographic adaptation, which warps each image many times and aggregates the detections. On HPatches its detector was the most repeatable under illumination changes and competitive under viewpoint changes, and the full network runs at about 70 FPS on 480 by 640 images. SuperGlue (2020) replaces nearest-neighbour matching with a graph neural network that attends across both images' keypoints and their positions, then solves an optimal-transport assignment. LightGlue (2023) is a faster successor.

LoFTR (2021) takes a fundamentally different approach: instead of detecting keypoints first, it directly produces dense semi-matches between two images using a transformer architecture. It first extracts coarse features using a CNN backbone, then uses self- and cross-attention to find correspondences at 1/8 resolution, and finally refines matches to sub-pixel accuracy. LoFTR excels in textureless regions and repetitive patterns where keypoint detectors fail, because it uses global image context to disambiguate matches. The trade-off is higher computational cost (100-200ms per pair on GPU).

Bundle adjustment minimizes: $\sum_{(i,j)} \|x_{ij} - \pi(R_j, t_j, K_j, X_i)\|^2$, where $x_{ij}$ is the observed pixel location of 3D point $i$ in camera $j$, and $\pi$ is the projection function. This is a nonlinear least squares problem solved with the Levenberg-Marquardt (LM) algorithm. The number of parameters is $6 \times n_{\text{cameras}}$ (rotation + translation per camera) $+ 3 \times n_{\text{points}}$ (xyz per point), which can be millions for large reconstructions. The key insight is that the Jacobian matrix is very sparse: each observation involves only one camera and one point.

The normal equations $J^T J \, \delta x = -J^T r$ in BA have a special block structure: the camera-camera block is dense among cameras sharing points, the point-point block is diagonal (each point is independent of other points), and the camera-point blocks are sparse. The Schur complement trick eliminates point parameters, reducing the system from $(6C + 3P)$ to $(6C)$ unknowns. For 50 cameras and 10,000 points, this reduces a 30,300 x 30,300 system to a 300 x 300 system---a 10,000x reduction. Libraries like Ceres Solver (Google) and g2o exploit this structure for efficient optimization.

Real-world data contains outliers: incorrectly triangulated points or wrong feature matches that survived RANSAC. Standard least squares is sensitive to outliers because the squared error grows quadratically. Robust loss functions (also called robust kernels or M-estimators) down-weight large residuals: Huber loss transitions from quadratic to linear at a threshold, Cauchy loss uses a logarithmic function, and Tukey's biweight completely ignores residuals beyond a threshold. Ceres Solver supports these as loss functions applied to each residual in BA.

COLMAP's SfM pipeline has five main stages: (1) Feature extraction using SIFT (GPU-accelerated), producing typically 5000-10000 keypoints per image. (2) Feature matching using exhaustive, sequential, or vocabulary tree strategies, with geometric verification via RANSAC. (3) Incremental reconstruction: selects the best initial pair, then iteratively registers cameras, triangulates points, and runs bundle adjustment. (4) Retriangulation: attempts to triangulate additional points after BA improves poses. (5) Final global BA with all cameras and points. COLMAP automatically handles multiple disconnected components and merges them if possible.

After sparse SfM, COLMAP's multi-view stereo (MVS) module computes dense depth maps for every image. It uses PatchMatch stereo: for each pixel, it samples random depth/normal hypotheses, evaluates photometric consistency across neighboring views, and propagates good hypotheses to neighbors. The depth maps are then fused into a single dense point cloud by checking multi-view consistency and removing outliers. The final output can contain millions to tens of millions of colored 3D points. For mesh reconstruction, Poisson surface reconstruction or Delaunay triangulation is applied to the dense point cloud.

To use COLMAP effectively: (1) capture images with 60-80% overlap between consecutive views, (2) avoid texture-free surfaces (white walls) and moving objects (people, cars), (3) maintain consistent exposure (or use EXIF data for varying focal lengths), (4) for large datasets, use sequential or vocabulary tree matching instead of exhaustive, (5) inspect the reconstruction in COLMAP's GUI to identify unregistered cameras (add more images of those areas), (6) export results in various formats (PLY, NVM, bundler) for downstream processing. COLMAP runs on both CPU and GPU, with GPU providing 5-10x speedup for feature extraction and matching.

Incremental SfM (used by COLMAP, VisualSFM, Bundler) adds cameras one at a time and runs bundle adjustment frequently. Strengths: robust to outliers (each camera is verified against the existing reconstruction), handles arbitrary camera configurations, and naturally produces a consistent reconstruction. Weaknesses: (1) sensitive to the initial pair choice, (2) prone to drift (errors accumulate as cameras are added sequentially), (3) computationally expensive due to repeated global BA, (4) order-dependent (different camera orderings can produce different results). For large datasets (10,000+ images), the repeated BA becomes the bottleneck.

Global SfM (used by OpenMVG, Theia) first estimates all relative rotations from pairwise matches, then computes global rotations simultaneously (rotation averaging), then estimates translations (translation averaging), and finally triangulates and runs BA. Strengths: (1) no drift because all cameras are solved simultaneously, (2) faster for large datasets (no repeated BA), (3) order-independent. Weaknesses: (1) more sensitive to outlier relative poses, (2) translation averaging is less robust than rotation averaging, (3) may fail on loosely connected scene graphs. Global methods are theoretically cleaner but practically require very robust outlier rejection.

Modern systems mix both paradigms. Hierarchical SfM partitions the view graph into clusters, reconstructs each one, often incrementally, then merges clusters by aligning their shared cameras and points. Global pipelines have also become more robust: GLOMAP replaces separate translation averaging with a joint global positioning step over cameras and points, and matches COLMAP's accuracy while running far faster. Learning-based methods such as DUSt3R and MASt3R regress dense 3D point maps directly from image pairs with transformers, which helps with little texture or overlap. They currently need GPUs, memory grows with the number of views, and accuracy on out-of-domain scenes is less proven.