Visual navigation of an autonomous underwater vehicle based on the global search of image correspondences
Kamaev A.N., Karmanov D.A.


Computing Center FEB RAS, Khabarovsk, Russia


A task of autonomous underwater vehicle (AUV) navigation is considered in the paper. The images obtained from an onboard stereo camera are used to build point clouds attached to a particular AUV position. Quantized SIFT descriptors of points are stored in a metric tree to organize an effective search procedure using a best bin first approach. Correspondences for a new point cloud are searched in a compact group of point clouds that have the largest number of similar descriptors stored in the tree. The new point cloud can be positioned relative to the other clouds without any prior information about the AUV position and uncertainty of this position. This approach increases the reliability of the AUV navigation system and makes it insensitive to data losses, textureless seafloor regions and long passes without trajectory intersections. Several algorithms are described in the paper: an algorithm of point clouds computation, an algorithm for establishing point clouds correspondence, and an algorithm of building groups of potentially linked point clouds to speedup the global search of correspondences. The general navigation algorithm consisting of three parallel subroutines: image adding, search tree updating, and global optimization is also presented. The proposed navigation system is tested on real and synthetic data. Tests on real data showed that the trajectory can be built even for an image sequence with 60% data losses with successive images that have either small or zero overlap. Tests on synthetic data showed that the constructed trajectory is close to the true one even for long missions. The average speed of image processing by the proposed navigation system is about 3 frames per second with  a middle-price desktop CPU.

navigation, AUV, SLAM, feature points, dead reckoning, image matching.

Kamaev AN, Karmanov DA. Visual navigation of an autonomous underwater vehicle based on the global search of image correspondences. Computer Optics 2018; 42(3): 457-467. DOI: 10.18287/2412-6179-2018-42-3-457-467.


  1. Bobkov VA, Mel'man SV, Tolstonogov AJu, Shherbatjuk AF. On some algorithms for visual navigation of the autonomous underwater vehicle using stereo images [In Russian]. Underwater Investigations and Robotics 2016; 2(22): 19-24.
  2. Eustice RM, Pizarro O, Singh H. Visually augmented navigation for autonomous underwater vehicles. IEEE Journal of Oceanic Engeneering 2008; 33(2): 103-122. DOI: 10.1109/JOE.2008.923547.
  3. Salvi J, Petillot Y, Battle E. Visual SLAM for 3D large-scale seabed acqui-sition employing underwater vehicles. 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems 2008: 1011-1016. DOI: 10.1109/IROS.2008.4650627.
  4. Aulinas J, Petillot Y, Llado X, Salvi J, Garcia R. Vision-based underwater SLAM for the SPA-RUS AUV. Proceedings of the 10th International Conference on Computer and IT Applications in the Maritime Industries 2011: 171-180.
  5. Johnson-Roberson M, Pizarro O, Williams SB, Mahon I. Generation and visualization of large-scale three-dimensional reconstructions from underwater robotic surveys. Journal of Field Robotics 2010; 27(1): 21-51. DOI: 10.1002/rob.20324.
  6. Eustice RM, Singh H, Leonard JJ, Walter MR. Visually mapping the RMS titanic: Conservative covariance estimates for SLAM information filters. The International Journal of Robotics Research 2006; 25(12): 1223-1242. DOI: 10.1177/0278364906072512.
  7. Kim A, Eustice RM. Real-time visual SLAM for autonomous underwater HULL inspection using visual saliency. IEEE Transaction on Robotics 2013; 29(3): 719-733. DOI: 10.1109/TRO.2012.2235699.
  8. Carraso PLN, Bonin-Font F, Codina GO. Stereo Graph-SLAM for autonomous underwater vehicles. In Book: Menegatti E, Michael N, Berns K, Yamaguchi H, eds. Intelligent Autonomous Systems 13: Proceedings of the 13th International Conference IAS-13. Heidelberg, New York, Dordrecht, London: Springer; 2014: 351-360. DOI: 10.1007/978-3-319-08338-4_26.
  9. Kamaev AN. Relative features based orientation of low contrast images obtained from AUV [In Russian]. Scientists notes PNU 2011; 2(2): 32-42.
  10. Lowe DG. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 2004; 60(2): 91-110. DOI: 10.1023/B:VISI.0000029664.99615.94.
  11. Hartley R, Zisserman A. Multiple view geometry in computer vision. 2nd ed. Cambridge: Cambridge University Press; 2004. DOI: 10.1023/B:VISI.0000029664.99615.94.
  12. Jegou H, Douze M, Schmid C. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence 2011; 33(1): 117-128. DOI: 10.1109/TPAMI.2010.57.
  13. Fischler MA, Bolles RC. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM 1981; 24(6): 381-395. DOI: 10.1145/358669.358692.
  14. Kabsch W. A solution for the best rotation to relate two sets of vectors. Acta Crystallographica Section A 1976; 32(5): 922-923. DOI: 10.1107/S0567739476001873.
  15. Liu T, Moore AW, Gray A, Yang K. An investigation of practical approximate nearest neighbor algorithms. Proceedings of the 17th International Conference on Neural Information Processing Systems 2004: 825-832.
  16. Beis J, Lowe DG. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97) 1997: 1000-1006. DOI: 10.1109/CVPR.1997.609451.
  17. Kamaev AN. Computation of positions of sea floor images obtained from AUV [In Russian]. Underwater Investigations and Robotics 2013; 2(16): 38-47.
  18. Grisetti G, Kümmerle R, Stachniss C, Burgard W. A Tutorial on graph-based SLAM. IEEE Intelligent Transportation Systems Magazine 2010; 2(4): 31-43. DOI: 10.1109/MITS.2010.939925.
  19. Kamaev AN, Sukhenko VA, Karmanov DA. Constructing and visualizing three-dimensional sea bottom models to test AUV machine vision systems. Program Comput Soft 2017; 43(3): 184-195. DOI: 10.1134/S0361768817030070.
  20. Kamaev AN, Smagin SI, Sukhenko VA, Karmanov DA. Synthetic data for AUV technical vision systems testing. CEUR Workshop Proceedings 2017; 1839: 126-140.

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20