Structure from Motion (SfM)

SfM begins by performing a sparse 3D reconstruction. It detects distinctive keypoints (like SIFT or ORB features) in each image and matches them across views. Using epipolar geometry and triangulation, it estimates the 3D coordinates of these matched features and the camera poses for each image. The result is a sparse point cloud representing the scene's salient structure, not a dense surface. This sparsity makes the initial optimization computationally tractable.

SfM pipelines are primarily categorized by their optimization strategy:

• Incremental SfM: Starts with a two-view reconstruction and adds images one by one, performing bundle adjustment after each addition. It is robust but can accumulate drift and is computationally heavy for large sets.
• Global SfM: Attempts to estimate all camera rotations and translations simultaneously using a global rotation averaging step, followed by translation averaging and a final bundle adjustment. It is faster and avoids sequential drift but can be less robust to outliers. Most popular open-source tools, like COLMAP, use an incremental approach for its superior stability.

Bundle adjustment is the non-linear optimization backbone of SfM. It jointly refines the 3D coordinates of all scene points, the camera poses, and often the intrinsic camera parameters (like focal length). The optimization minimizes the total reprojection error—the sum of squared distances between observed 2D keypoints and the re-projected 3D points. This process is crucial for achieving a globally consistent and accurate reconstruction, correcting errors accumulated during initial estimation.

Feature matching inevitably produces incorrect correspondences (outliers). SfM relies on robust estimation algorithms, primarily RANSAC (Random Sample Consensus), to filter these out. For each step (e.g., estimating the fundamental matrix between two views), RANSAC randomly samples minimal point sets, computes a model, and finds consensus. The model with the largest set of inliers is selected. This process is repeated for essential matrix estimation, triangulation, and pose estimation, making the pipeline resilient to noisy data.

A defining characteristic of classic SfM is that it operates on unordered image collections with unknown camera poses, as opposed to video sequences. The images can be from different times, cameras, and viewpoints. The algorithm must first establish connectivity by finding which images share a common field of view (image matching), often accelerated with vocabulary trees. This flexibility makes it ideal for applications like cultural heritage digitization and Google Street View reconstruction from internet photos.

SfM is typically the first stage in a full 3D modeling pipeline. Its output—a sparse point cloud and calibrated camera poses—provides the essential geometric foundation for subsequent dense reconstruction techniques like Multi-View Stereo (MVS). MVS uses the known camera parameters from SfM to perform dense matching, generating a dense point cloud, mesh, or volumetric representation (like a TSDF). SfM does not produce watertight models or surface textures; it solves for the camera motion and sparse geometry.

Multi-View Stereo (MVS) is the dense reconstruction stage that follows SfM. While SfM produces a sparse 3D point cloud and camera poses, MVS generates a dense 3D representation, such as a dense point cloud, mesh, or depth map, for every pixel in the input images.

• Input: Calibrated images and camera poses from SfM.
• Output: Dense geometry (e.g., millions of points or a complete surface mesh).
• Key Distinction: SfM solves for correspondences and geometry simultaneously; MVS assumes known camera geometry and solves for dense depth per pixel.

Bundle adjustment is the non-linear optimization backbone of SfM. It jointly refines the 3D coordinates of scene points, camera positions, orientations, and intrinsic parameters (like focal length) to minimize the total reprojection error—the difference between observed 2D image features and the re-projected 3D points.

• Function: The 'bundle' refers to the collection of light rays (features) connecting camera centers to 3D points.
• Algorithm: Typically uses the Levenberg-Marquardt algorithm due to its efficiency with sparse matrices.
• Critical Role: This optimization is what gives SfM its high accuracy, making it the gold standard for offline 3D reconstruction from unordered photos.

Visual SLAM (Simultaneous Localization and Mapping) is SfM's real-time counterpart for moving agents (e.g., robots, AR headsets). While both estimate 3D structure and camera pose, their objectives differ fundamentally.

• SfM: Offline, global, batch processing of unordered images. Prioritizes accuracy and completeness.
• vSLAM: Online, sequential processing of a video stream. Prioritizes speed and robustness for immediate localization.
• Key Techniques: vSLAM systems heavily rely on tracking (frame-to-frame pose estimation) and often use keyframes and local bundle adjustment, whereas SfM performs global optimization over all data.

Photogrammetry is the overarching science and technology of obtaining reliable measurements from photographs. SfM is a core computational technique within the modern digital photogrammetry pipeline.

• Broader Scope: Photogrammetry includes planning the image capture (flight paths, camera settings), ground control, and the generation of orthomosaics and digital elevation models (DEMs).
• SfM's Role: Automates the historically manual process of aerial triangulation, which establishes the geometric relationship between photos.
• Application Context: The term 'photogrammetry' is dominant in geospatial, surveying, and cultural heritage fields, while 'SfM' is more common in computer vision and robotics research.

Inverse rendering is a more ambitious problem that subsumes SfM. The goal is to infer not just 3D geometry and camera pose, but also the underlying scene properties that explain the images: materials (BRDF), textures, and lighting.

• SfM as a Subset: Classical SfM primarily recovers geometry and pose, often assuming Lambertian (matte) surfaces.
• Advanced Modeling: Inverse rendering uses differentiable rendering to optimize for complex, non-Lambertian materials and illumination, enabling the creation of photorealistic, relightable 3D assets.
• Modern Approach: Techniques like Neural Radiance Fields (NeRF) can be seen as a form of inverse rendering that uses a neural network to implicitly model geometry and view-dependent appearance.

Feature matching and RANSAC are the fundamental low-level operations that make SfM robust to outliers and practical for unordered image collections.

• Feature Matching: Establishes correspondences between distinctive keypoints (e.g., SIFT, ORB) across multiple images. This creates the 'tracks' of 2D observations that link to a single 3D point.
• RANSAC (Random Sample Consensus): A robust estimation algorithm used at multiple stages. For example, to compute the fundamental matrix or essential matrix between an image pair, RANSAC finds the geometric model that best fits the inlier correspondences while rejecting mismatches (outliers).
• Pipeline Role: These techniques are used in the initial image pair matching and incremental reconstruction steps of a typical SfM pipeline.