Structure from motion
Structure from motion (SfM) is a range imaging technique; it refers to the process of estimating three-dimensional structures from two-dimensional image sequences which may be coupled with local motion signals. It is studied in the fields of computer vision and visual perception. In biological vision, SfM refers to the phenomenon by which humans (and other living creatures) can recover 3D structure from the projected 2D (retinal) motion field of a moving object or scene.
Obtaining 3D information from 2D images
Humans perceive a lot of information about the three-dimensional structure in their environment by moving through it. When the observer moves and the objects around the observer move, information is obtained from images sensed over time.
Finding structure from motion presents a similar problem to finding structure from stereo vision. In both instances, the correspondence between images and the reconstruction of 3D object needs to be found.
To find correspondence between images, features such as corner points (edges with gradients in multiple directions) are tracked from one image to the next. One of the most widely used feature detectors is the SIFT (Scale-invariant feature transform). It uses the maxima from a Difference-of-Gaussians (DOG) pyramid as features. The first step in SIFT is finding a dominant gradient direction. To make it rotation-invariant, the descriptor is rotated to fit this orientation. Another common feature detector is the SURF (Speeded Up Robust Features). In SURF, the DOG is replaced with a Hessian matrix-based blob detector. Also, instead of evaluating the gradient histograms, SURF computes for the sums of gradient components and the sums of their absolute values. The features detected from all the images will then be matched. One of the matching algorithms that track features from one image to another is the Lukas-Kanade tracker.
Sometimes some of the matched features are incorrectly matched. This is why the matches should also be filtered. RANSAC (Random Sample Consensus) is the algorithm that is usually used to remove the outlier correspondences. In the paper of Fischler and Bolles, RANSAC is used to solve the Location Determination Problem (LDP), where the objective is to determine the points in space that project onto an image into a set of landmarks with known locations.
The feature trajectories over time are then used to reconstruct their 3D positions and the camera's motion. An alternative is given by so-called direct approaches, where geometric information (3D structure and camera motion) is directly estimated from the images, without intermediate abstraction to features or corners.
There are several approaches to structure from motion. In incremental SFM, camera poses are solved for and added one by one to the collection. In global SFM, the poses of all cameras are solved for at the same time. A somewhat intermediate approach is out-of-core SFM, where several partial reconstructions are computed that are then integrated into a global solution.
SfM for Cultural Heritage structure analysis
Cultural heritage is present everywhere. Its structural control, documentation and conservation is one of humanities main duties (UNESCO). Under this point of view, SfM is used in order to properly estimate situations as well as planning and maintenance efforts and costs, control and restoration. Because serious constraints often exist connected to the accessibility of the site and impossibility to install invasive surveying pillars that did not permit the use of traditional surveying routines (like total stations), SfM provides a non-invasive approach for the structure, without the direct interaction between the structure and any operator. The use is accurate as only qualitative considerations are needed. It is fast enough to respond to the monument’s immediate management needs. The first operational phase is an accurate preparation of the photogrammetric surveying where is established the relation between best distance from the object, focal length, the ground sampling distance (GSD) and the sensor’s resolution. With this information the programmed photographic acquisitions must be made using vertical overlapping of at least 60% (figure 02).
- Simultaneous localization and mapping
- Kinetic depth effect
- Match moving
- Motion field
- Motion parallax
- Epipolar geometry
- Tomasi–Kanade factorization
- Richard Hartley & Andrew Zisserman (2003). Multiple View Geometry in Computer Vision. Cambridge University Press. ISBN 0-521-54051-8.
- Olivier Faugeras and Quang-Tuan Luong and Theodore Papadopoulo (2001). The Geometry of Multiple Images. MIT Press. ISBN 0-262-06220-8.
- Yi Ma; S. Shankar Sastry; Jana Kosecka; Stefano Soatto; Jana Kosecka (November 2003). An Invitation to 3-D Vision: From Images to Geometric Models. Interdisciplinary Applied Mathematics Series, #26. Springer-Verlag New York, LLC. ISBN 0-387-00893-4.
- Linda G. Shapiro; George C. Stockman (2001). Computer Vision. Prentice Hall. ISBN 0-13-030796-3.
- D. G. Lowe (2004). "Distinctive image features from scale-invariant keypoints". International Journal of Computer Vision 60: 91–110. doi:10.1023/b:visi.0000029664.99615.94.
- H. Bay; T. Tuytelaars & L. Van Gool (2006). "Surf: Speeded up robust features". 9th European Conference on Computer Vision.
- K. Häming & G. Peters (2010). "The structure-from-motion reconstruction pipeline – a survey with focus on short image sequences". Kybernetika.
- B. D. Lucas & T. Kanade. "An iterative image registration technique with an application to stereo vision". IJCAI81.
- M. A. Fischler & R. C. Bolles (1981). "Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography". Commun. ACM 24: 381–395. doi:10.1145/358669.358692.
- F. Dellaert; S. Seitz; C. Thorpe & S. Thrun (2000). "Structure from Motion without Correspondence" (PDF). IEEE Computer Society Conference on Computer Vision and Pattern Recognition.
- Engel, Jakob; Schöps, Thomas; Cremers, Daniel (2014). "European Conference on Computer Vision (ECCV) 2014" (PDF).
- Guidi. G.; Beraldin, J.A.; Atzeni, C. High accuracy 3D modelling of cultural heritage: The digitizing of Donatello. IEEE Trans. Image Process. 2004, 13, 370-380
- Kraus, K., 2007. Photogrammetry: Geometry from Image and Laser Scans. Walter de Gruyter, 459 pp. ISBN 978-3-11-019007-6
Structure from Motion software toolboxes
Open source solutions
- Bundler - Structure from Motion for Unordered Photo Collections by Noah Snavely
- openMVG An Open Multiple View Geometry library + Structure from Motion demonstrators
- Libmv - A Structure from Motion library
- Theia: A Fast and scalable structure-from-motion library released under the BSD license
- COLMAP: General-purpose Structure-from-Motion pipeline with a graphical and command-line interface, licensed under the GPL.
- MicMac, a SFM open-source code released by the Institut national de l'information géographique et forestière
- LSD-SLAM: Large-Scale Direct Monocular SLAM in real-time, by Jakob Engel
- MVE - The Multi-View Environment by Simon Fuhrmann, TU Darmstadt.
- ceres-solver for general non-linear least squares. Has features for bundle adjustment. Previously used by Google internally for google maps. Released to the public in 2012.
- SBA for generic bundle adjustment by Manolis Lourakis.
- NuxSFM NuxSFM 2.0 pacman X86_64 build scripts.
- Structure from Motion toolbox for Matlab by Vincent Rabaud
- Matlab Functions for Multiple View Geometry by Andrew Zissermann
- Structure and Motion Toolkit by Phil Torr
- Matlab Code for Non-Rigid Structure from Motion by Lorenzo Torresani
- Python Photogrammetry Toolbox GUI - an open-source SFM GUI (Easy SfM and dense point cloud estimation launcher) by Pierre Moulon and Arc-Team
- Smart3DCapture, a complete photogrammetry solution by Acute3D.
- 3DF Samantha - Command line structure from Motion pipeline for Windows, by 3Dflow srl. Free for non-commercial purposes.
- Automatic Camera Tracking System (ACTS), a structure-from-motion with dense depth recovery system for Microsoft Windows, by Vision Group of State Key Lab of CAD&CG, Zhejiang University.
- Large-Scale Automatic Camera Tracking System (LS-ACTS), a large-scale structure-from-motion system for Microsoft Windows, by Vision Group of State Key Lab of CAD&CG, Zhejiang University.
- VisualSFM: A Visual Structure from Motion System, by Changchang Wu
- SFMToolkit a complete photogrammetry solution based on open-source software
- MountainsMap SEM software for Scanning Electron Microscopes. 3D is obtained by tilting the specimen + photogrammetry.
- Voodoo Camera Tracker, non-commercial tool for the integration of virtual and real scenes.
Original site, archived: Laboratorium für Informationstechnologie, University of Hannover
- MetaIO Toolbox SfM for augmented reality on mobile devices.
- TacitView by 2d3 Sensing
- Catena Python Abstract Workflow Framework with SfM components.
- CMPMVS Multi-View Reconstruction Software