Structure from Motion (SfM) is the process of estimating the 3-D structure of a scene from a set of 2-D images. To be more clear on definition: Structure from motion (SfM) is a photogrammetric range imaging technique for estimating three-dimensional structures from two-dimensional image sequences that may be coupled with local motion signals. It is studied in the fields of computer vision and visual perception. As in the case of volumetric streaming, we should understand the 3D world from 2D camera outputs.
Humans perceive a great deal of information about the three-dimensional structure in their environment by moving around it. When the observer moves, objects around them move different amounts depending on their distance from the observer. This is known as motion parallax, as seen in the above figure. A funny fact is that way when you are on a road trip, you see astronomical objects such as the Sun and the Moon that look like they are following you along the road. This depth information can be used to generate an accurate 3D representation of the world around them. 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 objects needs to be found.
There are few important steps which need to be followed for 3D reconstruction from multiple views of 2D images, in which a sequence of images is shot on the target object or scene in different orientations or projections. It is suggested to set a specific angle for each orientation. Then, suitable and matching algorithms designated for chosen approach are applied on the acquired 2D images to extract, match up, and estimate correspondence feature points that will form a bulk of coordinate points. The bulk of feature points obtained compose a 3D point cloud that contains information on 3D geometries and spatial location; however, the area of the surface and detail appearance is unknown but only shows approximate shape of the object. This problem is solved by creating 3D meshes, which is composed of connecting triangles from 3D point clouds. The Delaunay triangulation helps to construct surface in 3D space (C. Yang et al 2013).
The reconstructing 3D shape from 2D image is an ill-posed problem. A sufficient number of 2D images must be obtained, suitable algorithms need to be constructed and specified for this reconstruction process which digital camera and turntable setup for the data acquisition.
In Structure from Motion (SfM), the camera parameters (intrinsic and extrinsic) need to be estimated jointly with the 3D structure while in Multi-View Stereo (MVS), the camera parameters are assumed to be known. Furthermore, while MVS approaches create a dense 3D model of the object or scene of interest, SfM approaches typically recover a sparse 3D point cloud of the scene. Solving for the camera parameters and 3D geometry of the scene is equivalent to solving the correspondence problem based on a photo-consistency function that measures the agreement between different viewpoints. Typically, 3D reconstruction pipelines consist of an SfM method to estimate a coarse 3D reconstruction while recovering the camera parameters followed by an MVS method to obtain a finer reconstruction, as illustrated in the below figure of COLMAP (Johannes Lutz Sch¨onberger et al 2016)
Classical SfM pipelines as in the case of given below references (631, 630, 136, 482, 2, 729, 218, 650) first extract and match sparse features. Usually, an initial transformation between pairs of cameras (essential matrix) is estimated with RANSAC. Given the initial camera transformations, a geometric verification stage evaluates photometric consistency between re-projected sparse features and excludes outliers. Starting from an initial two-view reconstruction, an incremental reconstruction is performed based on best view selection, triangulation, and bundle adjustment. Due to this incremental approach, SfM pipelines are usually not very efficient and need to be applied offline. Simultaneous Localization and Mapping (SLAM) methods which will be discussed in further posts also address the problem of joint camera estimation and 3D scene reconstruction. However, SLAM techniques focus primarily on accurate pose estimation and real-time performance, typically sacrificing geometric accuracy for these goals.
The web provides large amounts of publicly available imagery from cities taken by tourists that can be used to reconstruct popular buildings or even entire cities. This task requires a different approach than the ones mentioned earlier because of the large amount of images and the unknown geometric properties of the cameras the images have been taken with. Agarwal et al. 2009 address this problem by considering Flickr images of Rome. They use SIFT feature matching in combination with an efficient image retrieval approach to reduce the number of comparisons. Afterwards, a fast bundle adjustment method on minimal subsets of images captures the geometry of a scene. Finally, they optimise the whole pipeline in parallel, which allows them to reconstruct cities from 150K images in less than a day using 500 computing nodes. Frahm et al. (2010) present a highly efficient system for city-scale reconstruction from millions of images on a single computer by leveraging the high parallelization capabilities of graphics hardware. Recently, Sch¨onberger et al (2019) proposed a structure-from-motion pipeline with better completeness and accuracy while better reducing drift in comparison to previous methods.They further propose a more robust best view selection and triangulation method, producing more complete structures. Finally, a novel iterative Bundle Adjustment, re-triangulation, and outlier filtering step lead to significantly more complete and accurate 3D models.
For further reading, you may want to take a look at following references:
- Johannes Lutz Schoenberger and Jan-Michael Frahm. “Structure-fromMotion Revisited”. In: Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR). 2016.
- Noah Snavely, Steven M. Seitz, and Richard Szeliski. “Modeling the World from Internet Photo Collections”. In: International Journal of Computer Vision (IJCV) 80.2 (2008), pp. 189–210.
- Jan-Michael Frahm, Pierre Fite-Georgel, David Gallup, Tim Johnson, Rahul Raguram, Changchang Wu, Yi-Hung Jen, Enrique Dunn, Brian Clipp, Svetlana Lazebnik, and Marc Pollefeys. “Building Rome on a Cloudless Day”. In: Proc. of the European Conf. on Computer Vision (ECCV). 2010.