8.3 Structure from motion

Structure from Motion (SfM) is a powerful technique that reconstructs 3D scenes from 2D image sequences. It combines computer vision and photogrammetry to estimate camera poses and 3D structure simultaneously, with applications in robotics, augmented reality, and cultural heritage preservation.

SfM relies on feature detection, matching, and camera modeling to recover 3D geometry from overlapping images. It extends traditional photogrammetry by automating camera pose estimation and incorporating advanced computer vision algorithms, enabling reconstruction from uncalibrated and unordered image sets.

Fundamentals of structure from motion

• Structure from Motion (SfM) reconstructs 3D scenes from 2D image sequences captured by moving cameras
• SfM combines computer vision techniques with photogrammetry principles to estimate camera poses and 3D structure simultaneously
• Applications span across various fields including robotics, augmented reality, and cultural heritage preservation

Concept and applications

Top images from around the web for Concept and applications

• 

  A novel no-sensors 3D model reconstruction from monocular video frames for a dynamic environment ... View original

  Is this image relevant?

• 

  Reconstruction of Historical Buildings using Structure from Motion (SfM) Applications. An ... View original

  Is this image relevant?

• 

  Frontiers | Automatic 3D Reconstruction From Unstructured Videos Combining Video Summarization ... View original

  Is this image relevant?

• 

  A novel no-sensors 3D model reconstruction from monocular video frames for a dynamic environment ... View original

  Is this image relevant?

• 

  Reconstruction of Historical Buildings using Structure from Motion (SfM) Applications. An ... View original

  Is this image relevant?

1 of 3

Top images from around the web for Concept and applications

• 

  A novel no-sensors 3D model reconstruction from monocular video frames for a dynamic environment ... View original

  Is this image relevant?

• 

  Reconstruction of Historical Buildings using Structure from Motion (SfM) Applications. An ... View original

  Is this image relevant?

• 

  Frontiers | Automatic 3D Reconstruction From Unstructured Videos Combining Video Summarization ... View original

  Is this image relevant?

• 

  A novel no-sensors 3D model reconstruction from monocular video frames for a dynamic environment ... View original

  Is this image relevant?

• 

  Reconstruction of Historical Buildings using Structure from Motion (SfM) Applications. An ... View original

  Is this image relevant?

1 of 3

• Recovers 3D geometry and camera motion from multiple overlapping images
• Utilized in aerial mapping for creating detailed terrain models
• Enables virtual tourism through 3D reconstruction of historical sites
• Assists in movie production for camera tracking and special effects integration

Key assumptions and constraints

• Assumes static scenes with no moving objects between images
• Requires sufficient overlap between consecutive images (typically 60-80%)
• Depends on the presence of distinct visual features for accurate matching
• Works best with well-textured surfaces and avoids reflective or transparent objects

Relation to photogrammetry

• Extends traditional photogrammetry by automating camera pose estimation
• Incorporates computer vision algorithms for feature detection and matching
• Enables reconstruction from uncalibrated and unordered image sets
• Utilizes bundle adjustment for simultaneous optimization of structure and motion

Feature detection and matching

• Feature detection and matching form the foundation of SfM by identifying corresponding points across images
• These techniques enable the establishment of geometric relationships between different views of a scene
• Robust feature detection and matching algorithms contribute to the accuracy and reliability of 3D reconstruction

Interest point detection

• Locates distinctive points in images that can be reliably identified across multiple views
• Harris corner detector identifies points with significant intensity changes in multiple directions
• FAST (Features from Accelerated Segment Test) algorithm quickly detects corners by examining pixel intensities in a circular pattern
• Blob detectors like SIFT (Scale-Invariant Feature Transform) locate regions with consistent properties across different scales

Feature descriptors

• Encodes local image information around interest points for robust matching
• SIFT descriptor computes gradient histograms in a 4x4 grid around the keypoint
• SURF (Speeded Up Robust Features) uses Haar wavelet responses for faster computation
• Binary descriptors like BRIEF (Binary Robust Independent Elementary Features) use simple intensity comparisons for efficient matching

Matching algorithms

• Brute-force matching compares all descriptors between images but can be computationally expensive
• FLANN (Fast Library for Approximate Nearest Neighbors) uses efficient data structures for faster approximate matching
• Ratio test filters out ambiguous matches by comparing the distances of the two closest neighbors
• RANSAC (Random Sample Consensus) removes outliers by fitting geometric models to randomly sampled subsets of matches

Camera models and calibration

• Camera models mathematically describe how 3D world points project onto 2D image planes
• Calibration determines the intrinsic and extrinsic parameters of cameras used in SfM
• Accurate camera models and calibration improve the precision of 3D reconstruction and camera pose estimation

Pinhole camera model

• Represents the simplest mathematical model of a camera
• Projects 3D points onto a 2D image plane through a single point (pinhole)
• Described by the equation: $\lambda \mathbf{x} = K[R|\mathbf{t}]\mathbf{X}$
• $\mathbf{x}$ represents the 2D image point, $\mathbf{X}$ the 3D world point, $K$ the intrinsic matrix, and $[R|\mathbf{t}]$ the extrinsic matrix

Intrinsic vs extrinsic parameters

• Intrinsic parameters describe the internal characteristics of the camera
  • Focal length determines the field of view
  • Principal point represents the image center
  • Skew factor accounts for non-rectangular pixels (usually assumed to be zero)
• Extrinsic parameters define the camera's position and orientation in the world
  • Rotation matrix $R$ specifies the camera's orientation
  • Translation vector $\mathbf{t}$ indicates the camera's position

Camera calibration techniques

• Zhang's method uses a planar checkerboard pattern viewed from multiple angles
• Direct Linear Transformation (DLT) estimates camera parameters from known 3D-2D point correspondences
• Self-calibration techniques estimate camera parameters directly from image sequences without known 3D points
• Bundle adjustment refines calibration parameters along with 3D structure and camera poses

Epipolar geometry

• Epipolar geometry describes the geometric relationships between two views of a 3D scene
• Constrains the search for corresponding points between images to epipolar lines
• Plays a crucial role in stereo matching and motion estimation in SfM pipelines

Epipolar lines and points

• Epipolar line represents the projection of a ray from one camera center through a 3D point onto the other camera's image plane
• Epipole marks the intersection of the baseline (line connecting camera centers) with the image plane
• Corresponding points in two views must lie on their respective epipolar lines
• Epipolar constraint reduces the search for matches from 2D to 1D, improving efficiency and accuracy

Fundamental matrix

• Encapsulates the epipolar geometry between two uncalibrated views
• $\mathbf{x}'^T F \mathbf{x} = 0$ where $\mathbf{x}$ and $\mathbf{x}'$ are corresponding points in two views
• Rank-2 matrix with 7 degrees of freedom
• Estimated using the normalized 8-point algorithm or robust methods like RANSAC

Essential matrix

• Specialization of the fundamental matrix for calibrated cameras
• Related to the fundamental matrix by $E = K'^T F K$, where $K$ and $K'$ are the intrinsic matrices
• Encodes the relative rotation and translation between two camera poses
• Can be decomposed to recover the relative camera motion (up to a scale ambiguity)

Motion estimation

• Determines the relative positions and orientations of cameras in the SfM pipeline
• Enables the reconstruction of camera trajectories and scene structure
• Combines geometric constraints with optimization techniques for accurate estimation

Two-view geometry

• Estimates relative camera pose between two views using the essential matrix
• Decomposes the essential matrix into rotation and translation components
• Resolves the four-fold ambiguity in decomposition using cheirality constraint
• Triangulates 3D points to determine the correct solution and initialize the reconstruction

Multiple view geometry

• Extends two-view geometry to handle sequences of images or unordered image sets
• Incremental SfM adds new views one by one to an initial two-view reconstruction
• Global SfM methods simultaneously optimize all camera poses and 3D points
• Utilizes track generation to link feature matches across multiple images

Bundle adjustment

• Refines camera parameters, 3D point positions, and optionally intrinsic parameters
• Minimizes the reprojection error between observed and predicted image points
• Formulated as a non-linear least squares problem: $\min_{\mathbf{P}, \mathbf{X}} \sum_{i,j} d(\mathbf{x}_{ij}, \mathbf{P}_i \mathbf{X}_j)^2$
• Employs sparse optimization techniques (Levenberg-Marquardt algorithm) for efficiency

3D reconstruction

• Generates a 3D representation of the scene from estimated camera poses and image correspondences
• Produces sparse, semi-dense, or dense reconstructions depending on the approach
• Forms the basis for various applications including 3D modeling, virtual reality, and scene understanding

Triangulation methods

• Linear triangulation solves a system of equations using the Direct Linear Transform (DLT)
• Midpoint method estimates 3D points as the midpoint of the closest approach of two rays
• Optimal triangulation minimizes geometric error under epipolar constraints
• Robust triangulation techniques handle outliers and improve accuracy in the presence of noise

Point cloud generation

• Creates a sparse 3D point cloud from triangulated feature correspondences
• Filters points based on reprojection error and triangulation angle to ensure quality
• Estimates surface normals using local neighborhood information
• Applies outlier removal techniques to clean up the point cloud (statistical outlier removal, radius outlier removal)

Mesh reconstruction

• Converts point clouds into continuous surface representations
• Poisson surface reconstruction creates watertight meshes by solving a Poisson equation
• Delaunay triangulation generates meshes by connecting nearby points
• Marching cubes algorithm extracts isosurfaces from volumetric data for mesh creation

Dense reconstruction techniques

• Aims to reconstruct detailed 3D models with high point density
• Utilizes pixel-wise or patch-wise matching to generate dense correspondences
• Produces more complete and visually appealing 3D models compared to sparse reconstruction

Multi-view stereo

• Extends stereo matching principles to multiple views
• Plane-sweeping algorithms search for correspondences along epipolar lines in multiple images
• Patch-based multi-view stereo (PMVS) grows dense reconstructions from initial sparse points
• Depth map fusion techniques combine per-view depth maps into a consistent 3D model

Patch-based methods

• Represents surfaces using oriented patches
• Initializes patches at sparse feature points and expands to nearby pixels
• Optimizes patch parameters (position, normal, color) to maximize photo-consistency across views
• Filters patches based on visibility constraints and geometric consistency

Volumetric methods

• Discretizes the 3D space into a regular grid or octree structure
• Space carving removes voxels that are inconsistent with input images
• Volumetric graph cuts formulate reconstruction as an energy minimization problem
• Signed distance functions represent surfaces implicitly and enable smooth surface extraction

Optimization and refinement

• Improves the quality and accuracy of SfM reconstructions through various optimization techniques
• Addresses issues such as drift, loop closure, and outlier rejection
• Refines both camera poses and 3D structure to achieve globally consistent reconstructions

RANSAC for outlier rejection

• Robust estimation technique for fitting models in the presence of outliers
• Iteratively samples minimal subsets of data to estimate model parameters
• Evaluates the model against all data points to determine inlier set
• Selects the model with the largest inlier set as the best fit
• Applied in various stages of SfM (feature matching, fundamental matrix estimation, pose estimation)

Iterative closest point (ICP)

• Aligns 3D point clouds or meshes by iteratively estimating the transformation between them
• Consists of four main steps: point selection, correspondence matching, weighting, and minimization
• Variants include point-to-point ICP, point-to-plane ICP, and generalized ICP
• Used for refining alignments between partial reconstructions or for loop closure

Loop closure detection

• Identifies when a camera revisits a previously observed part of the scene
• Visual place recognition techniques compare current views with past observations
• Bag-of-Words models represent images as histograms of visual words for efficient matching
• Graph-based optimization redistributes accumulated error across the camera trajectory

Challenges and limitations

• SfM faces various challenges that can affect the quality and completeness of reconstructions
• Understanding these limitations helps in designing robust SfM systems and interpreting results
• Ongoing research addresses these challenges to expand the applicability of SfM techniques

Scale ambiguity

• SfM reconstructions are typically up to an unknown scale factor
• Arises from the projective nature of images and the inability to determine absolute distances
• Can be resolved by incorporating known distances or using additional sensors (GPS, IMU)
• Affects applications requiring metric reconstructions (autonomous navigation, precise measurements)

Degenerate configurations

• Certain camera motions or scene structures lead to ambiguities in reconstruction
• Pure rotational motion prevents the estimation of translation between views
• Planar scenes can result in multiple valid interpretations of camera motion
• Homographies can be used to detect and handle some degenerate cases

Handling moving objects

• SfM assumes a static scene, but real-world scenes often contain moving objects
• Dynamic objects can introduce errors in feature matching and motion estimation
• Segmentation techniques can identify and exclude moving regions from reconstruction
• Multi-body SfM approaches attempt to reconstruct both static and dynamic parts of the scene

Advanced topics

• Explores cutting-edge research and applications that extend the capabilities of traditional SfM
• Addresses practical challenges in deploying SfM systems in real-world scenarios
• Integrates SfM with other sensing modalities and computational techniques for enhanced performance

Large-scale reconstruction

• Tackles the challenge of reconstructing expansive environments (cities, landscapes)
• Employs hierarchical approaches to divide large problems into manageable subproblems
• Utilizes distributed computing and out-of-core algorithms to handle massive datasets
• Incorporates geo-referencing to align reconstructions with global coordinate systems

Real-time SfM

• Aims to perform 3D reconstruction and camera tracking in real-time
• Parallel tracking and mapping (PTAM) separates tracking and mapping into parallel threads
• ORB-SLAM combines efficient feature extraction with pose graph optimization for real-time performance
• Utilizes keyframe selection strategies to maintain computational efficiency

Integration with other sensors

• Fuses SfM with data from additional sensors to improve robustness and accuracy
• Inertial measurement units (IMUs) provide motion estimates to assist in tracking and scale estimation
• GPS integration helps in geo-referencing and resolving scale ambiguity
• Lidar sensors can provide accurate depth information to complement image-based reconstruction