Matching Image Sequences using Mathematical Programming: Visual Localization Applications

Abstract

This paper proposes a new visual localization algorithm that utilizes the visual route map to localize the agent. The sequence of the current and past images is matched to the map, i.e. the reference image sequence, to produce the best match of the current image. The image sequence matching is achieved by measuring the similarity between the two image sequences using the dynamic time warping (DTW) algorithm. The DTW algorithm employs Dynamic Programming (DP) to calculate the distance (the cost function) between the two image sequences. Consequently, the output of the alignment process is an optimal match of each image in the current image sequence to an image in the reference one. Our proposed DTW matching algorithm is suitable to be used with a wide variety of engineered features, they are SIFT, HOG, LDP in particular. The proposed DTW algorithm is compared to other recognition algorithms like Support Vector Machine (SVM) and Binary- appearance Loop-closure (ABLE) algorithm. The datasets used in the experiments are challenging and benchmarks, they are commonly used in the literature of the visual localization. These datasets are the” Garden point”, “St. Lucia”, and “Nordland”. The experimental observations have proven that the proposed technique can significantly improve the performance of all the used descriptors, i.e, SIFT, HOG, and LDB as compared to its individual performance. In addition, it was able to the SVM and ABLE localization algorithm.

Keywords

• Dynamic programming,Dynamic time warping,Visual localization

References

1. [1] Michael J Milford and Gordon F Wyeth. Seqslam: Visual route-based navigation for sunny summer days and stormy winter nights. In Robotics and Automation (ICRA), 2012 IEEE International Conference on, pages 1643–1649. IEEE, 2012.
2. [2] AH Hafez, Nakul Agarwal, and CV Jawahar. Connecting visual experiences using max-flow network with application to visual localization. arXiv preprint arXiv:1808.00208, 2018.
3. [3] A H Abdul Hafez, Manpreet Arora, K Madhava Krishna, and CV Jawahar. Learning multiple experiences useful visual features for active maps localization in crowded environments. Advanced Robotics, 30(1):50–67, 2016.
4. [4] A H Abdul Hafez, Shivudu Bhuvanagiri, K Madhava Krishna, and CV Jawahar. On-line convex optimization based solution for mapping in vslam. In 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 4072–4077. IEEE, 2008.
5. [5] Arren Glover, William Maddern, Michael Warren, Stephanie Reid, Michael Milford, and Gordon Wyeth. Openfabmap: An open source toolbox for appearance-based loop closure detection. In ICRA,, pages 4730–4735. IEEE, 2012.
6. [6] Tayyab Naseer, Wolfram Burgard, and Cyrill Stachniss. Robust visual localization across seasons. IEEE Transactions on Robotics, 34(2):289–302, 2018.
7. [7] Roberto Arroyo, Pablo F Alcantarilla, Luis M Bergasa, J Javier Yebes, and Sergio G´amez. Bidirectional loop closure detection on panoramas for visual navigation. In Intelligent Vehicles Symposium Proceedings, 2014 IEEE, pages 1378–1383. IEEE, 2014.
8. [8] Emilio Garcia-Fidalgo and Alberto Ortiz. Methods for Appearance based Loop Closure Detection: Applications to Topological Mapping and Image Mosaicking, volume 122. Springer, 2018.

9. [9] AH Abdul Hafez, Manpreet Singh, K Madhava Krishna, and CV Jawahar. Visual localization in highly crowded urban environments. In 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2778–2783. IEEE, 2013.
10. [10] Abdul Hafez Abdul Hafez, Manpreet Arora, K Madhava Krishna, and CV Jawahar. Learning multiple experiences useful visual features for active maps localization in crowded environments. Advanced Robotics, 30(1):50–67, 2016.
11. [11] Liz Murphy, Steven Martin, and Peter Corke. Creating and using probabilistic costmaps from vehicle experience. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 4689–4694. IEEE, 2012.
12. [12] Winston Churchill and Paul Newman. Experience-based navigation for long-term localisation. The International Journal of Robotics Research, 32(14):1645–1661, 2013.
13. [13] Marcin Dymczyk, Simon Lynen, Titus Cieslewski, Michael Bosse, Roland Siegwart, and Paul Furgale. The gist of maps-summarizing experience for lifelong localization. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 2767–2773. IEEE, 2015.
14. [14] Mathieu Labb´e and Franc¸ois Michaud. Memory management for realtime appearance-based loop closure detection. In 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1271–1276. IEEE, 2011.
15. [15] Mathieu Labbe and Francois Michaud. Appearance-based loop closure detection for online large-scale and long-term operation. IEEE Transactions on Robotics, 29(3):734–745, 2013.
16. [16] Mark Cummins and Paul Newman. Fab-map: Probabilistic localization and mapping in the space of appearance. The International Journal of Robotics Research, 27(6):647–665, 2008.
17. [17] Grant Schindler, Matthew Brown, and Richard Szeliski. City-scale location recognition. In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–7. Citeseer, 2007.
18. [18] M. Dymczyk, S. Lynen, T. Cieslewski, M. Bosse, R. Siegwart, and P. Furgale. The gist of maps - summarizing experience for lifelong localization. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 2767–2773, 2015.
19. [19] Fan Zeng, Adam Jacobson, David Smith, Nigel Boswell, Thierry Peynot, and Michael Milford. Enhancing underground visual place recognition with shannon entropy saliency. 2017.
20. [20] Abbas M Ali and Tarik A Rashid. Place recognition using kernel visual keyword descriptors. In 2015 SAI Intelligent Systems Conference (IntelliSys), pages 921–926. IEEE, 2015.
21. [21] Yongliang Qiao, Cindy Cappelle, and Yassine Ruichek. Place recognition based visual localization using lbp feature and svm. In Mexican International Conference on Artificial Intelligence, pages 393–404. Springer, 2015.
22. [22] Richard Bellman. Some applications of the theory of dynamic programming—a review. Journal of the Operations Research Society of America, 2(3):275–288, 1954.
23. [23] Cory Myers, Lawrence Rabiner, and Aaron Rosenberg. Performance tradeoffs in dynamic time warping algorithms for isolated word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing, 28(6):623–635, 1980.
24. [24] Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE transactions on acoustics, speech, and signal processing, 26(1):43–49, 1978.
25. [25] Alon Efrat, Quanfu Fan, and Suresh Venkatasubramanian. Curve matching, time warping, and light fields: New algorithms for computing similarity between curves. Journal of Mathematical Imaging and Vision, 27(3):203–216, 2007.
26. [26] Charles C. Tappert, Ching Y. Suen, and Toru Wakahara. The state of the art in online handwriting recognition. IEEE Transactions on pattern analysis and machine intelligence, 12(8):787–808, 1990.
27. [27] Ana Kuzmanic and Vlasta Zanchi. Hand shape classification using dtw and lcss as similarity measures for vision-based gesture recognition system. In EUROCON 2007-The International Conference on” Computer as a Tool”, pages 264–269. IEEE, 2007.
28. [28] Vit Niennattrakul and Chotirat Ann Ratanamahatana. On clustering multimedia time series data using k-means and dynamic time warping. In 2007 International Conference on Multimedia and Ubiquitous Engineering (MUE’07), pages 733–738. IEEE, 2007.
29. [29] Jie Gu and Xiaomin Jin. A simple approximation for dynamic time warping search in large time series database. In International Conference on Intelligent Data Engineering and Automated Learning, pages 841– 848. Springer, 2006.
30. [30] Meinard M¨uller. Dtw-based motion comparison and retrieval. Information Retrieval for Music and Motion, pages 211–226, 2007.
31. [31] Zhang Zhang, Kaiqi Huang, Tieniu Tan, et al. Comparison of similarity measures for trajectory clustering in outdoor surveillance scenes. In ICPR (3), pages 1135–1138. Citeseer, 2006.
32. [32] J´erˆome Vial, Hicham Noc¸airi, Patrick Sassiat, Sreedhar Mallipatu, Guillaume Cognon, Didier Thi´ebaut, B´eatrice Teillet, and Douglas N Rutledge. Combination of dynamic time warping and multivariate analysis for the comparison of comprehensive two-dimensional gas chromatograms: application to plant extracts. Journal of Chromatography A, 1216(14):2866–2872, 2009.
33. [33] Meinard M¨uller, Henning Mattes, and Frank Kurth. An efficient multiscale approach to audio synchronization. In ISMIR, volume 546, pages 192–197. Citeseer, 2006.
34. [34] Rohit J Kate. Using dynamic time warping distances as features for improved time series classification. Data Mining and Knowledge Discovery, 30(2):283–312, 2016.
35. [35] Franc¸ois Petitjean, Germain Forestier, Geoffrey I Webb, Ann E Nicholson, Yanping Chen, and Eamonn Keogh. Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm. Knowledge and Information Systems, 47(1):1–26, 2016.
36. [36] Arren Glover,Will Maddern, Michael Milford, and GordonWyeth. FABMAP + RatSLAM: Appearance-based SLAM for Multiple Times of Day. In ICRA, Anchorage, USA, 2010.
37. [37] Daniel Olid, Jos´e M. F´acil, and Javier Civera. Single-view place recognition under seasonal changes. In PPNIV Workshop at IROS 2018, 2018.