PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Structure from Motion

Onur Ozyesil, Vladislav Voroninski, Ronen Basri, Amit Singer

arXiv:1701.08493v2cs.CV

TL;DR

SfM asks how to recover stationary-scene 3D structure from image measurements while estimating camera motion. This survey synthesizes methods for motion and structure estimation, alongside feature matching, SLAM, ambiguities, and camera models. It highlights robust location-estimation methods and practical pipeline constraints, including non-convex refinement and outlier-heavy correspondences.

  • Problem

    SfM must recover 3D structure and camera motion from images despite non-convex reprojection optimization, ambiguous matches, and challenging camera-location distributions.

  • Method

    The survey organizes early factorization methods, camera-location estimation, structure recovery, SLAM, feature extraction and matching, scene ambiguities, alternative camera models, and practical datasets and software.

  • Results

    The survey reports robust convex and related methods for camera-location estimation, including globally convergent LUD optimization and exact-recovery results under stated measurement conditions.

  • Takeaways & Limitations

    SfM reconstruction relies on coordinated feature correspondence, camera-orientation and location estimation, triangulation, and subsequent refinement of camera pose and 3D structure.

  • Takeaways & Limitations

    RANSAC can be effective offline but is combinatorial and only tractable to run to completion there, forcing tradeoffs in real-time settings.

Abstract

from arXiv · show

The structure from motion (SfM) problem in computer vision is the problem of recovering the three-dimensional ($3$D) structure of a stationary scene from a set of projective measurements, represented as a collection of two-dimensional ($2$D) images, via estimation of motion of the cameras corresponding to these images. In essence, SfM involves the three main stages of (1) extraction of features in images (e.g., points of interest, lines, etc.) and matching these features between images, (2) camera motion estimation (e.g., using relative pairwise camera positions estimated from the extracted features), and (3) recovery of the $3$D structure using the estimated motion and features (e.g., by minimizing the so-called reprojection error). This survey mainly focuses on relatively recent developments in the literature pertaining to stages (2) and (3). More specifically, after touching upon the early factorization-based techniques for motion and structure estimation, we provide a detailed account of some of the recent camera location estimation methods in the literature, followed by discussion of notable techniques for $3$D structure recovery. We also cover the basics of the simultaneous localization and mapping (SLAM) problem, which can be viewed as a specific case of the SfM problem. Further, our survey includes a review of the fundamentals of feature extraction and matching (i.e., stage (1) above), various recent methods for handling ambiguities in $3$D scenes, SfM techniques involving relatively uncommon camera models and image features, and popular sources of data and SfM software.

1 Introduction

SfM recovers stationary-scene 3D structure from multiple images by estimating camera parameters and scene geometry. This survey emphasizes recent methods for camera motion and structure estimation, while also covering the broader SfM pipeline and related topics.

  • Motivation: Recovering a stationary scene’s 3D structure from many images is a fundamental computer-vision goal addressed by multiview SfM.The survey situates SfM within a large body of computer-vision research.
  • Core formulation: Modern SfM commonly uses bundle adjustment to jointly estimate 3D scene points and camera calibration parameters by minimizing total reprojection error.The cost compares image measurements with their predictive camera-and-structure model.
  • Core formulation: Because bundle adjustment is non-convex and often reaches undesirable local minima, reliable initialization of camera motion, calibration, and structure is critical.Initialization should be as close as possible to the true solution.
  • Practical pipelines: A sequential SfM pipeline demonstrated accurate reconstruction from hundreds or thousands of unordered photographs, beginning with keypoint detection and SIFT matching.RANSAC is then applied to the candidate matches.
  • Scope: The survey reviews early factorization methods, camera-location estimation, 3D structure recovery, SLAM, feature matching, scene ambiguities, camera models, datasets, and software.It focuses primarily on relatively recent SfM techniques and refers elsewhere for additional earlier work.

2 Early Works

Early SfM work established pairwise epipolar estimation and factorization-based recovery under orthographic and perspective camera models. These methods exploit low-rank measurement structure, with later extensions addressing projective depths and occlusions.

  • Pairwise perspective SfM: The eight-point algorithm introduced a linear pairwise SfM method that estimates relative camera motion and 3D scene points from point correspondences.It is based on the epipolar constraint between two cameras.
  • Pairwise perspective SfM: With a fixed scale, eight linearly independent epipolar constraints determine an essential matrix for a camera pair.Rotation and scene points are then recovered algebraically, with signs selected so points lie in front of the cameras.
  • Orthographic factorization: Under an orthographic camera model, centered image measurements form a rank-3 matrix whose best noisy approximation is obtained by SVD.The factorization separates camera orientations from 3D point coordinates and can be extended to occlusions.
  • Pairwise perspective SfM: Only five corresponding 3D points suffice to estimate an essential matrix, but doing so requires solving a nonlinear system.The eight-point formulation instead uses eight linearly independent epipolar constraints.
  • Perspective factorization: Perspective factorization extends this idea using a rank-4 measurement matrix, but requires estimating otherwise inaccessible projective depths first.Pairwise camera equations estimate depths up to global scale before SVD factorization.

3 Camera Location Estimation

Camera location estimation uses pairwise motion measurements to recover camera positions, but noise, sparsity, outliers, and insufficient geometric constraints create instability and ambiguity. Recent methods address these issues through convex relaxations, robust estimators, rigidity analysis, outlier detection, and distributed or synchronized pipelines.

  • Pairwise point matches yield relative rotations and translations, whose translational components provide pairwise directions for estimating camera locations.For the pinhole model, essential-matrix estimates can be factorized into relative rotational and translational parts.
  • Least squares methods are efficient but can degrade substantially on large, sparse, unordered, and noisy datasets, often producing tightly clustered spurious locations.The survey identifies underconstrained instances, including disconnected measurement graphs and collinearity of directions at one node, as additional sources of non-uniqueness.
  • Semidefinite relaxation produces camera-location estimates from the leading eigenvector of its solution and has empirical tightness and stability under relatively high noise.The associated stability result bounds location-estimate distortion by the noise level under fairly general noise assumptions.
  • Parallel rigidity characterizes well-posed location recovery from pairwise directions, showing that measurement-graph connectivity alone is insufficient for camera locations.Camera orientation estimation requires connectivity, whereas location recovery additionally depends on geometric rigidity.
  • 3.2 Other Methods: Alternative approaches include 1DSfM outlier detection, distributed consensus-based joint motion estimation, and group synchronization pipelines that fuse intermediate estimates into final locations.The distributed framework uses a quadratic location estimator and relaxed repulsion constraints to preserve efficiency without the clustering tendency reported for basic least squares methods.
  • 3.1 Robust Convex Methods: Robust convex methods improve outlier handling: LUD is globally convergent and empirically exhibits exact recovery with sufficiently many exact directions, while ShapeFit has rigorous recovery guarantees under corrupted observations.ShapeFit guarantees exact recovery with high probability in specified random-graph, Gaussian-location settings and under broader deterministic assumptions.

4 Structure Estimation

Structure estimation in SfM refines camera, structure, and calibration parameters through bundle adjustment, but large unordered image collections make the underlying computations increasingly difficult. Recent methods address this challenge with sparse or iterative optimization, image-subset selection, and parallel processing.

  • Bundle adjustment: Bundle adjustment jointly refines 3D structure, camera motion, and possibly intrinsic calibration by minimizing total reprojection error.It requires an initial estimate of camera and structure parameters before refinement.
  • Large-scale optimization: Unordered community photo collections have denser connectivity graphs than structured image sets, increasing the cost of sparse factorization and Schur-complement methods.The reduced camera matrix S becomes harder to construct and store as sparsity decreases.
  • Large-scale optimization: Preconditioned conjugate gradients within an inexact Newton or Levenberg–Marquardt framework improve bundle-adjustment efficiency by avoiding exact large sparse linear solves.The method uses preconditioners to improve conditioning and reports accuracy and significant time and memory improvements over classical Schur-complement factorization.
  • Scalable reconstruction: Large-scale systems reduce computation through skeletal camera subsets, approximate dominating sets, or parallelization across SfM stages.City-scale processing combines distributed image matching, skeletal-set reconstruction, sequential initialization, and bundle adjustment selected for problem size.
  • Alternative structure formulations: After camera rotations are estimated, SfM can be reformulated as bipartite recovery of camera locations and 3D points from camera-to-point directions.Convex ShapeFit methods provide a route to simultaneous location and structure estimation with potential implications for real-time robotics.

5 Simultaneous Localization and Mapping (SLAM)

SLAM estimates an agent’s location and the surrounding 3D environment, making it a robotics-specific case of SfM with shared ambiguities. Vision-based systems face outliers, geometric degeneracies, scale limitations, and computational constraints that motivate inertial sensing and efficient optimization.

  • 5 Simultaneous Localization and Mapping (SLAM): SLAM jointly estimates a depth map of the 3D environment and the position of a moving agent.It supports autonomous navigation for cars, drones, and consumer robots.
  • 5 Simultaneous Localization and Mapping (SLAM): SLAM is a robotics and augmented/virtual-reality specialization of SfM that retains many of SfM’s difficulties.
  • 5.1 Novel Approaches to and Limitations of Visual SLAM: The standard SfM and map-free SLAM pipeline establishes feature correspondences, estimates orientations, recovers camera locations and structure, then refines them jointly with bundle adjustment.Triangulation typically produces 3D structure after camera locations are recovered.
  • 5.1 Novel Approaches to and Limitations of Visual SLAM: Outliers arise from illumination changes, occlusions, specularities, repetitive structures, and independently moving objects, making correspondence estimation a central vision-based SfM challenge.RANSAC can reduce outlier rates in offline photo-tourism applications to still-high but acceptable levels of about 40 percent.
  • 5.3 Application-specific Difficulties: Straight-line motion, especially parallel to the optical axis, creates unrecoverable central depth and local minima associated with scene ambiguities.Semi-global methods address these issues but are too computationally intensive for real-time applications.
  • 5.4 Direct vs. Feature-based Methods: Monocular SLAM is scale-invariant but cannot infer absolute scale, so scale estimates drift over time when applications transition between differently scaled scenes.Stereo and LIDAR provide scale measurements but perform well only over limited scale ranges or with practical constraints.

6 Other Topics

The survey also covers feature processing, ambiguity handling, camera models, reconstruction software, and evaluation resources. These topics extend SfM beyond core motion and structure estimation toward practical image collections and diverse sensing setups.

  • 6 Other Topics: This section surveys feature extraction and matching, alternative measurements and camera models, image symmetries and ambiguities, and widely used SfM data and software.
  • 6.1 Feature Extraction and Matching: SIFT produces local features designed to be invariant to image scaling and rotation, with partial invariance to viewpoint and changes in illumination.Its pipeline detects scale-space extrema, assigns location, scale, and orientation, and computes local descriptors from image gradients.
  • 6.1 Feature Extraction and Matching: SIFT descriptors aggregate gradient orientations over 4×4 subregions into a normalized 128-dimensional vector.Normalization supports invariance to homogeneous illumination changes, while thresholding is used to improve robustness to nonlinear illumination changes.
  • 6.2 Symmetries and Ambiguities in Images: Ambiguous structures, including repeated or symmetric objects, can cause incorrect matches and major reconstruction errors such as phantom or superimposed structures.A graph-theoretic method specifically addresses disambiguation in large, unordered image datasets.
  • 6.3 Alternative Features and Camera Models: Omnidirectional and generic camera models broaden SfM to fish-eye, catadioptric, radial-distortion, non-central, pinhole, and stereo-rig cameras.Parametric models for para-catadioptric cameras and fish-eye lenses support calibration and reconstruction through angular-error minimization.
  • 6.4 Popular Software Packages and Data Sources: Multicore bundle adjustment reportedly preserves high accuracy while reducing memory use and improving runtime by up to ten times on CPU and thirty times on GPU.VisualSfM incorporates this solver into an incremental SfM package with a graphical interface and GPU SIFT integration.
  • 6.4 Popular Software Packages and Data Sources: PMVS reconstructs dense surfaces through matching, expansion, and filtering of patches, producing high-quality connected models when camera estimates and calibration are accurate.Dense reconstruction remains computationally expensive for large image sets, motivating distributed approaches scalable to tens of thousands of images.
  • 6.4 Popular Software Packages and Data Sources: Accessible datasets containing images, features, matches, calibration, and sometimes ground-truth motion enable comparative evaluation of SfM accuracy and efficiency.

7 Conclusion

The survey identifies unresolved efficiency, robustness, and theoretical-analysis challenges in SfM, while pointing to constrained applications as promising directions for progress.

  • Scope: The survey covers camera location estimation, structure and motion refinement, SLAM, feature matching, ambiguous scenes, and alternative features and camera models.It directs readers to other works for additional topics and methods.
  • Future challenges: Feature extraction and matching remain computationally intensive, with efficient methods potentially degrading accuracy.The survey calls for methods combining improved invariance with local and global image characteristics.
  • Future challenges: Existing ambiguous-scene methods trade computational efficiency against robustness to mismatched features and large ambiguous structures.Methods for small experimental sets handle higher mismatch proportions but are relatively inefficient, whereas methods for large image sets can fail on large ambiguities.
  • Future directions: Efficient SfM algorithms for tightly constrained instances, including fast depth estimation with known camera motion, are expected to attract increasing attention.The survey identifies predictable accuracy and provable robustness as important design goals for these techniques.
  • Future directions: The field would benefit from rigorous results on fundamental limits involving mismatched features, image noise, stability, and robustness.The survey notes that theoretical work exists but still identifies broader rigorous results as valuable.
Loading 1701.08493v2…