3.3 Structure from motion (SfM)

Structure from Motion (SfM) is a game-changing technique in digital art history. It creates 3D models of artifacts and sites using regular photos. This method lets us digitally preserve cultural heritage without fancy equipment, making it accessible to more researchers and institutions.

SfM works by analyzing multiple 2D images to reconstruct 3D scenes. It detects features across photos, estimates camera positions, and builds point clouds. This process enables detailed 3D modeling of objects and spaces, revolutionizing how we document and study cultural heritage.

Principles of structure from motion

• Structure from motion (SfM) is a photogrammetric technique that reconstructs 3D scenes from a series of overlapping 2D images
• SfM algorithms rely on the principles of computer vision and multiple view geometry to estimate camera positions and 3D point coordinates
• In the context of digital art history and cultural heritage, SfM enables the creation of detailed 3D models of artifacts, monuments, and sites without the need for specialized hardware

Reconstructing 3D scenes from 2D images

Top images from around the web for Reconstructing 3D scenes from 2D images

• 

  Internet Archaeol. 36. Baxter. Jarlshof Lost and Found. Structure from motion photogrammetry View original

  Is this image relevant?

• 

  computer vision - 3d point reconstruction from depth map (with camera parameters) - Stack Overflow View original

  Is this image relevant?

• 

  Frontiers | Evaluation of 3D Markerless Motion Capture Accuracy Using OpenPose With Multiple ... View original

  Is this image relevant?

• 

  Internet Archaeol. 36. Baxter. Jarlshof Lost and Found. Structure from motion photogrammetry View original

  Is this image relevant?

• 

  computer vision - 3d point reconstruction from depth map (with camera parameters) - Stack Overflow View original

  Is this image relevant?

1 of 3

Top images from around the web for Reconstructing 3D scenes from 2D images

• 

  Internet Archaeol. 36. Baxter. Jarlshof Lost and Found. Structure from motion photogrammetry View original

  Is this image relevant?

• 

  computer vision - 3d point reconstruction from depth map (with camera parameters) - Stack Overflow View original

  Is this image relevant?

• 

  Frontiers | Evaluation of 3D Markerless Motion Capture Accuracy Using OpenPose With Multiple ... View original

  Is this image relevant?

• 

  Internet Archaeol. 36. Baxter. Jarlshof Lost and Found. Structure from motion photogrammetry View original

  Is this image relevant?

• 

  computer vision - 3d point reconstruction from depth map (with camera parameters) - Stack Overflow View original

  Is this image relevant?

1 of 3

• SfM reconstructs 3D scenes by analyzing the parallax and motion parallax between corresponding features in multiple 2D images
• By identifying and matching features across images taken from different viewpoints, SfM algorithms can triangulate the 3D positions of those features
• The resulting 3D point cloud represents the structure of the scene, while the estimated camera positions and orientations provide the motion information

Key assumptions and constraints

• SfM assumes that the scene is static and that the images are taken from different viewpoints with sufficient overlap
• The scene must have sufficient texture and features to allow for reliable feature detection and matching across images
• SfM performs best when the images are captured under consistent lighting conditions and with minimal lens distortion
• The accuracy of the reconstructed 3D model depends on factors such as image resolution, number of images, and the geometric configuration of the camera positions

SfM pipeline and workflow

• The SfM pipeline consists of several stages that process the input images and gradually build up the 3D reconstruction
• Understanding the workflow is crucial for effectively applying SfM techniques to digitize and analyze cultural heritage objects and sites
• The main stages of the SfM pipeline include image acquisition, feature detection and matching, camera pose estimation, and point cloud generation

Image acquisition and preprocessing

• Acquiring high-quality images is the first step in the SfM pipeline
• Images should be captured from multiple viewpoints with sufficient overlap (typically 60-80%) to ensure reliable feature matching
• Preprocessing steps may include image resizing, noise reduction, and color correction to improve the quality and consistency of the input data

Feature detection and matching

• Feature detection algorithms (SIFT, SURF, ORB) identify distinctive keypoints in each image that are invariant to scale, rotation, and illumination changes
• Feature descriptors are computed for each keypoint, encoding the local image information around the keypoint
• Feature matching techniques (brute-force, ANN, RANSAC) establish correspondences between keypoints across different images based on the similarity of their descriptors

Camera pose estimation

• Camera pose estimation determines the position and orientation of each camera in the 3D space
• The estimation process typically involves solving the structure and motion problem using epipolar geometry and bundle adjustment
• Pairwise relative camera poses are computed using the fundamental matrix or essential matrix, which encode the geometric relationship between two views

Sparse point cloud generation

• Once the camera poses are estimated, a sparse point cloud is generated by triangulating the 3D positions of the matched features
• The sparse point cloud provides an initial representation of the scene structure, albeit with a limited number of 3D points
• The sparse reconstruction serves as a foundation for further refinement and densification steps

Dense point cloud reconstruction

• Dense reconstruction methods (multi-view stereo) aim to generate a more detailed and complete point cloud by estimating depth information for each pixel in the images
• Depth maps are computed for each view by analyzing the photometric consistency and geometric constraints between neighboring views
• The depth maps are then fused and filtered to create a dense point cloud that captures the fine details of the scene

Camera models in SfM

• Camera models describe the mathematical relationship between 3D points in the scene and their 2D projections on the image plane
• Accurate camera modeling is essential for precise 3D reconstruction and for handling various types of cameras and lenses used in cultural heritage documentation
• The most commonly used camera model in SfM is the pinhole camera model, which assumes a simple perspective projection

Pinhole camera model

• The pinhole camera model is a basic perspective projection model that describes the mapping between 3D points and their 2D image coordinates
• In this model, light rays pass through a small aperture (the pinhole) and project an inverted image of the scene onto the image plane
• The pinhole camera model is characterized by intrinsic parameters (focal length, principal point) and extrinsic parameters (camera position and orientation)

Intrinsic vs extrinsic parameters

• Intrinsic parameters describe the internal characteristics of the camera, such as the focal length and the principal point (the intersection of the optical axis with the image plane)
• Extrinsic parameters define the camera's position and orientation in the 3D world coordinate system
• SfM algorithms estimate both intrinsic and extrinsic parameters during the camera pose estimation stage to accurately model the image formation process

Lens distortion correction

• Real camera lenses often introduce geometric distortions (radial and tangential) that deviate from the ideal pinhole model
• Lens distortion can cause straight lines to appear curved in the images, affecting the accuracy of feature matching and 3D reconstruction
• SfM pipelines typically include a lens distortion correction step that estimates the distortion parameters and undistorts the images to improve the quality of the reconstruction

Feature detection and description

• Feature detection and description are fundamental steps in the SfM pipeline that enable the identification and matching of corresponding points across images
• Robust and distinctive features are essential for accurate camera pose estimation and 3D reconstruction
• Several feature detection and description algorithms have been developed, each with its own strengths and trade-offs

Scale-invariant feature transform (SIFT)

• SIFT is a widely used feature detection and description algorithm that is robust to scale, rotation, and illumination changes
• SIFT detects keypoints at multiple scales using a difference-of-Gaussian (DoG) function and assigns orientations based on local image gradients
• The SIFT descriptor is a 128-dimensional vector that encodes the local image information around each keypoint, making it highly distinctive and suitable for matching

Speeded up robust features (SURF)

• SURF is a faster alternative to SIFT that achieves comparable performance by using integral images and approximations of the DoG function
• SURF detects keypoints using the determinant of the Hessian matrix and assigns orientations based on Haar wavelet responses
• The SURF descriptor is a 64-dimensional vector that captures the distribution of intensity content within the neighborhood of each keypoint

Oriented FAST and rotated BRIEF (ORB)

• ORB is a binary feature descriptor that combines the FAST keypoint detector and the rotated BRIEF descriptor
• FAST (Features from Accelerated Segment Test) is a computationally efficient keypoint detector that identifies corners based on intensity comparisons in a circular neighborhood
• The rotated BRIEF descriptor is a binary string that encodes the intensity comparisons between pairs of pixels, making it fast to compute and match

Feature matching strategies

• Feature matching establishes correspondences between keypoints detected in different images based on the similarity of their descriptors
• Accurate feature matching is crucial for estimating camera poses and reconstructing the 3D scene
• Various matching strategies have been developed to handle the challenges of outliers, ambiguities, and computational efficiency

Brute-force matching

• Brute-force matching exhaustively compares each feature descriptor from one image against all feature descriptors from another image
• The Euclidean distance between descriptor vectors is commonly used as a similarity measure, with smaller distances indicating better matches
• While brute-force matching guarantees finding the best matches, it can be computationally expensive for large datasets

Approximate nearest neighbors (ANN)

• ANN techniques aim to accelerate the feature matching process by efficiently searching for approximate nearest neighbors in high-dimensional descriptor space
• Algorithms like k-d trees and locality-sensitive hashing (LSH) partition the descriptor space and enable fast retrieval of similar descriptors
• ANN methods trade off some matching accuracy for improved computational efficiency, making them suitable for large-scale SfM applications

Random sample consensus (RANSAC)

• RANSAC is a robust estimation technique used to filter out outlier matches and estimate the fundamental matrix or essential matrix between image pairs
• RANSAC iteratively samples a minimal set of feature matches, estimates the model parameters (e.g., fundamental matrix), and evaluates the support from the remaining matches
• The model with the highest consensus (inlier count) is selected as the best estimate, effectively rejecting outlier matches that do not conform to the geometric constraints

Bundle adjustment optimization

• Bundle adjustment is a key optimization step in the SfM pipeline that refines the estimated camera poses and 3D point positions to minimize the reprojection error
• The reprojection error measures the difference between the observed image coordinates of a 3D point and its projected coordinates based on the estimated camera parameters
• By minimizing the reprojection error across all images and points, bundle adjustment produces a globally consistent and accurate 3D reconstruction

Minimizing reprojection error

• The goal of bundle adjustment is to find the optimal camera parameters and 3D point positions that minimize the sum of squared reprojection errors
• The reprojection error for a 3D point is defined as the Euclidean distance between its observed image coordinates and the coordinates obtained by projecting the point using the estimated camera parameters
• Minimizing the reprojection error involves solving a non-linear least-squares problem, typically using iterative optimization techniques like Levenberg-Marquardt

Sparse vs dense bundle adjustment

• Sparse bundle adjustment optimizes only the camera parameters and a sparse set of 3D points, typically the ones corresponding to the matched features
• Dense bundle adjustment, also known as multi-view stereo (MVS), additionally optimizes the positions of a dense set of 3D points, aiming to recover the full scene geometry
• Sparse bundle adjustment is computationally more efficient and provides a good initial estimate, while dense bundle adjustment produces a more detailed and complete reconstruction

Levenberg-Marquardt algorithm

• The Levenberg-Marquardt (LM) algorithm is a widely used optimization technique for solving non-linear least-squares problems, including bundle adjustment
• LM combines the Gauss-Newton method and gradient descent, adaptively adjusting the step size based on the improvement in the objective function
• The algorithm iteratively updates the parameter estimates by solving a linear system of equations and evaluating the reduction in the reprojection error
• LM is known for its robustness and fast convergence, making it well-suited for bundle adjustment in SfM pipelines

Multi-view stereo (MVS) reconstruction

• Multi-view stereo (MVS) is a dense 3D reconstruction technique that builds upon the output of the SfM pipeline to generate a detailed and complete 3D model of the scene
• MVS algorithms aim to estimate depth information for each pixel in the input images by analyzing the photometric and geometric consistency across multiple views
• The resulting dense point cloud captures the fine-grained geometry of the scene, enabling the creation of high-resolution 3D models for cultural heritage applications

Depth map estimation

• Depth map estimation is a key step in MVS reconstruction that computes a depth value for each pixel in the input images
• Various approaches exist for depth map estimation, including patch-based methods, plane-sweeping algorithms, and variational optimization techniques
• Patch-based methods (PatchMatch) estimate depth by finding the best-matching patches across neighboring views, while plane-sweeping algorithms (COLMAP) test multiple depth hypotheses and select the most photoconsistent one

Point cloud fusion and filtering

• Once depth maps are estimated for each view, they need to be fused into a single consistent point cloud representation
• Depth map fusion techniques (Poisson surface reconstruction, volumetric merging) aggregate the depth information from multiple views and generate a unified 3D point cloud
• Filtering steps (statistical outlier removal, noise reduction) are applied to remove erroneous or noisy points and improve the quality of the reconstructed point cloud

Mesh generation and texturing

• The dense point cloud obtained from MVS reconstruction can be further processed to generate a polygonal mesh representation of the scene
• Meshing algorithms (Marching Cubes, Delaunay triangulation) create a triangular mesh that approximates the surface of the point cloud
• Texture mapping techniques (UV mapping, color projection) assign color information from the input images to the mesh vertices, resulting in a photorealistic and visually appealing 3D model

SfM applications in cultural heritage

• Structure from motion (SfM) has found extensive applications in the field of cultural heritage, revolutionizing the way we document, analyze, and disseminate information about artifacts, monuments, and sites
• SfM provides a cost-effective and non-invasive means of creating detailed 3D models of cultural heritage objects, enabling their digital preservation and accessibility
• The generated 3D models serve various purposes, including research, conservation, restoration, and public engagement

Digitizing artifacts and monuments

• SfM allows for the rapid and accurate digitization of cultural heritage artifacts and monuments, creating high-resolution 3D models that capture their geometry, texture, and appearance
• Digitized models provide a permanent digital record of the objects, enabling their study and analysis without the need for physical access
• SfM-based digitization is particularly valuable for fragile or inaccessible artifacts, as it minimizes the risk of damage during the documentation process

Virtual museums and exhibitions

• SfM-generated 3D models can be used to create immersive virtual experiences, allowing users to explore and interact with cultural heritage objects in a digital environment
• Virtual museums and exhibitions provide global access to cultural heritage, reaching a wider audience and engaging the public in new ways
• Interactive 3D models can be integrated into educational platforms, enabling students and researchers to examine artifacts in detail and gain insights into their historical and cultural context

Preservation and conservation

• SfM plays a crucial role in the preservation and conservation of cultural heritage by providing detailed documentation of the current state of objects and sites
• 3D models serve as a baseline for monitoring changes and deterioration over time, aiding in the development of conservation strategies
• In the event of damage or loss, SfM-generated models can guide the restoration process by providing accurate reference data for reconstruction and repair

Challenges and limitations of SfM

• While SfM has proven to be a powerful technique for 3D reconstruction in cultural heritage, it also faces certain challenges and limitations that need to be considered
• Understanding these challenges is essential for effectively applying SfM and developing strategies to mitigate their impact on the quality and accuracy of the reconstructed models
• Researchers and practitioners in the field of digital art history and cultural heritage should be aware of these limitations and adapt their approaches accordingly

Dealing with textureless regions

• SfM relies on the presence of distinctive features in the input images to establish correspondences and estimate camera poses
• Textureless regions, such as smooth surfaces or areas with repetitive patterns, pose a challenge for feature detection and matching algorithms
• Lack of reliable features in these regions can lead to gaps or inaccuracies in the reconstructed 3D model
• Strategies to address this issue include using additional cues (e.g., silhouettes, edges) or incorporating active illumination techniques (e.g., structured light) to enhance surface texture

Handling large-scale scenes

• SfM algorithms can struggle with large-scale scenes that span vast areas or contain a high number of images
• As the number of images and the size of the scene increase, the computational complexity of feature matching, camera pose estimation, and bundle adjustment grows exponentially
• Large-scale scenes may also exhibit significant variations in lighting, viewpoint, and scale, further complicating the reconstruction process
• Hierarchical and divide-and-conquer approaches (e.g., incremental SfM, parallel processing) can help in managing the complexity and scalability of large-scale reconstructions

Accuracy vs computational efficiency

• SfM pipelines often face a trade-off between reconstruction accuracy and computational efficiency
• Achieving highly accurate 3D models requires dense feature matching, rigorous bundle adjustment, and multi-view stereo techniques, which can be computationally intensive and time-consuming
• On the other hand, faster and more efficient SfM methods may sacrifice some level of accuracy and detail in the reconstructed models
• The choice between accuracy and efficiency depends on the specific requirements of the cultural heritage application, available computational resources, and the desired level of detail in the final 3D model

Comparison of SfM software

• Various software solutions, both open-source and commercial, are available for performing SfM-based 3D reconstruction in cultural heritage projects
• Each software package offers different features, workflows, and performance characteristics, making it important to consider the specific needs and constraints of the project when selecting a tool
• Comparing and evaluating different SfM software options can help in making informed decisions and optimizing the reconstruction process for digital art history and cultural heritage applications

Open-source vs commercial solutions

• Open-source SfM software (e.g., OpenMVG, COLMAP, AliceVision) provides freely available and customizable tools for 3D reconstruction
• These solutions often offer flexibility, transparency, and the ability to modify and extend the underlying algorithms to suit specific project requirements
• Commercial SfM software (e.g., Agisoft Metashape, Reality Capture) typically provides user-friendly interfaces, streamlined workflows, and advanced features for professional-grade reconstructions
• Commercial solutions often come with technical support, documentation, and regular updates, but may have higher costs and less flexibility compared to open-source alternatives

Agisoft Metashape vs Reality Capture

• Agisoft Metashape (formerly PhotoScan) is a popular commercial SfM software known for its ease of use, robust performance, and high-quality reconstructions
• Metashape offers a comprehensive workflow, from image alignment and dense point cloud generation to mesh modeling and texture mapping
• Reality Capture is another commercial SfM solution that focuses on speed and efficiency, utilizing advanced algorithms and GPU acceleration to process large datasets quickly
• Reality Capture provides