Jump to content

Structure from motion

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Jarble (talk | contribs) at 03:55, 10 October 2018 (added Category:Motion in computer vision using HotCat). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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. 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.

Principle

Digital surface model of motorway interchange construction site
Real photo x SfM with texture color x SfM with simple shader. Made with Python Photogrammetry Toolbox GUI and rendered in Blender with Cycles.
Bezmiechowa airfield 3D digital surface model extracted from data collected during 30min flight of Pteryx UAV

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.[1]

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 scale-invariant feature transform (SIFT). 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.[2] Another common feature detector is the SURF (speeded-up robust features).[3] 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.[4] 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.[5]

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.[6]

The feature trajectories over time are then used to reconstruct their 3D positions and the camera's motion.[7] 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.[8]

There are several approaches to structure from motion. In incremental SFM[9], camera poses are solved for and added one by one to the collection. In global SFM [10][11], 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.

Applications

Geosciences

Structure from Motion photogrammetry with multi-view stereo provides hyperscale landform models using images acquired from a range of digital cameras and optionally a network of ground control points. The technique is not limited in temporal frequency and can provide point cloud data comparable in density and accuracy to those generated by terrestrial and airborne laser scanning at a fraction of the cost.[12][13][14]. Structure from motion is also useful in remote or rugged environments where terrestrial laser scanning is limited by equipment portability and airborne laser scanning is limited by terrain roughness causing loss of data and image foreshortening.The technique has been applied in many settings such as rivers[15], badlands[16], sandy coastlines[17][18], fault zones[19], and coral reef settings[20]. A full range of digital cameras can be utilized, including digital SLR's, compact digital cameras and even smart phones. Generally though, higher accuracy data will be achieved with more expensive cameras, which include lenses of higher optical quality. The technique therefore offers exciting opportunities to characterize surface topography in unprecedented detail and, with multi-temporal data, to detect elevation, position and volumetric changes that are symptomatic of earth surface processes. Structure from Motion can be placed in the context of other digital surveying methods.

Cultural heritage

Cultural heritage is present everywhere. Its structural control, documentation and conservation is one of humanity's 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.[21] 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).[22]

See also

Further reading

  • Jonathan L. Carrivick, Mark W. Smith, Duncan J. Quincey (2016). Structure from Motion in the Geosciences. Wiley-Blackwell. 208 pages. ISBN 978-1-118-89584-9
  • Richard Hartley; Andrew Zisserman (2003). Multiple View Geometry in Computer Vision. Cambridge University Press. ISBN 0-521-54051-8. {{cite book}}: Unknown parameter |lastauthoramp= ignored (|name-list-style= suggested) (help)
  • 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.

References

  1. ^ Linda G. Shapiro; George C. Stockman (2001). Computer Vision. Prentice Hall. ISBN 0-13-030796-3.
  2. ^ 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.
  3. ^ H. Bay; T. Tuytelaars; L. Van Gool (2006). "Surf: Speeded up robust features". 9th European Conference on Computer Vision. {{cite journal}}: Unknown parameter |last-author-amp= ignored (|name-list-style= suggested) (help)
  4. ^ K. Häming; G. Peters (2010). "The structure-from-motion reconstruction pipeline – a survey with focus on short image sequences". Kybernetika. {{cite journal}}: Unknown parameter |lastauthoramp= ignored (|name-list-style= suggested) (help)
  5. ^ B. D. Lucas; T. Kanade. "An iterative image registration technique with an application to stereo vision". IJCAI81. {{cite journal}}: Unknown parameter |lastauthoramp= ignored (|name-list-style= suggested) (help)
  6. ^ 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. {{cite journal}}: Unknown parameter |lastauthoramp= ignored (|name-list-style= suggested) (help)
  7. ^ 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. {{cite journal}}: Unknown parameter |last-author-amp= ignored (|name-list-style= suggested) (help)
  8. ^ Engel, Jakob; Schöps, Thomas; Cremers, Daniel (2014). "European Conference on Computer Vision (ECCV) 2014" (PDF). {{cite journal}}: |contribution= ignored (help); Cite journal requires |journal= (help)
  9. ^ J.L. Schönberger; J.M. Frahm (2016). "Structure-from-Motion Revisited" (PDF). IEEE Computer Society Conference on Computer Vision and Pattern Recognition. {{cite journal}}: Unknown parameter |last-author-amp= ignored (|name-list-style= suggested) (help)
  10. ^ C. Tomasi; T. Kanade (1992). "Shape and motion from image streams under orthography: a factorization method". International Journal of Computer Vision. {{cite journal}}: Unknown parameter |last-author-amp= ignored (|name-list-style= suggested) (help)
  11. ^ V.M. Govindu (2001). "Combining two-view constraints for motion estimation". IEEE Computer Society Conference on Computer Vision and Pattern Recognition. {{cite journal}}: Unknown parameter |last-author-amp= ignored (|name-list-style= suggested) (help)
  12. ^ Westoby, M. J.; Brasington, J.; Glasser, N. F.; Hambrey, M. J.; Reynolds, J. M. (2012-12-15). "'Structure-from-Motion' photogrammetry: A low-cost, effective tool for geoscience applications". Geomorphology. 179: 300–314. doi:10.1016/j.geomorph.2012.08.021.
  13. ^ James, M. R.; Robson, S. (2012-09-01). "Straightforward reconstruction of 3D surfaces and topography with a camera: Accuracy and geoscience application". Journal of Geophysical Research: Earth Surface. 117 (F3): F03017. doi:10.1029/2011jf002289. ISSN 2156-2202.
  14. ^ Fonstad, Mark A.; Dietrich, James T.; Courville, Brittany C.; Jensen, Jennifer L.; Carbonneau, Patrice E. (2013-03-30). "Topographic structure from motion: a new development in photogrammetric measurement". Earth Surface Processes and Landforms. 38 (4): 421–430. doi:10.1002/esp.3366. ISSN 1096-9837.
  15. ^ Javernick, L.; Brasington, J.; Caruso, B. "Modeling the topography of shallow braided rivers using Structure-from-Motion photogrammetry". Geomorphology. 213: 166–182. doi:10.1016/j.geomorph.2014.01.006.
  16. ^ Smith, Mark William; Vericat, Damià (2015-09-30). "From experimental plots to experimental landscapes: topography, erosion and deposition in sub-humid badlands from Structure-from-Motion photogrammetry". Earth Surface Processes and Landforms. 40 (12): 1656–1671. doi:10.1002/esp.3747. ISSN 1096-9837.
  17. ^ Goldstein, Evan B; Oliver, Amber R; deVries, Elsemarie; Moore, Laura J; Jass, Theo (2015-10-22). "Ground control point requirements for structure-from-motion derived topography in low-slope coastal environments". PeerJ PrePrints. doi:10.7287/peerj.preprints.1444v1. ISSN 2167-9843.{{cite journal}}: CS1 maint: unflagged free DOI (link)
  18. ^ Mancini, Francesco; Dubbini, Marco; Gattelli, Mario; Stecchi, Francesco; Fabbri, Stefano; Gabbianelli, Giovanni (2013-12-09). "Using Unmanned Aerial Vehicles (UAV) for High-Resolution Reconstruction of Topography: The Structure from Motion Approach on Coastal Environments". Remote Sensing. 5 (12): 6880–6898. doi:10.3390/rs5126880.{{cite journal}}: CS1 maint: unflagged free DOI (link)
  19. ^ Johnson, Kendra; Nissen, Edwin; Saripalli, Srikanth; Arrowsmith, J. Ramón; McGarey, Patrick; Scharer, Katherine; Williams, Patrick; Blisniuk, Kimberly (2014-10-01). "Rapid mapping of ultrafine fault zone topography with structure from motion". Geosphere. 10 (5): 969–986. doi:10.1130/GES01017.1.
  20. ^ Bryson, Mitch; Duce, Stephanie; Harris, Dan; Webster, Jody M.; Thompson, Alisha; Vila-Concejo, Ana; Williams, Stefan B. "Geomorphic changes of a coral shingle cay measured using Kite Aerial Photography". Geomorphology. 270: 1–8. doi:10.1016/j.geomorph.2016.06.018.
  21. ^ 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
  22. ^ 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

  • Trying all the free Photogrammetry-Tools[1]

C++

Matlab

Python

Closed source software

  1. ^ pfalkingham (2016-09-14). "Trying all the free Photogrammetry!". Dr Peter L. Falkingham. Retrieved 2017-05-16.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Structure_from_motion&oldid=863333739"