Abstract
We consider the problem of merging together multiple appearance-based maps independently built by a team of robots jointly exploring an indoor environment. Due to the lack of accepted metrics to evaluate the quality of merged appearance-based maps, we propose to use algebraic connectivity for this purpose, and we discuss why this is an appropriate measure. Next, we introduce QuickConnect, an anytime algorithm aiming to maximize the given metric and we show how it can merge couple of maps, as well as multiple maps at the same time. The proposed algorithm has been implemented and tested on a fully functioning robotic system building appearance-based maps using a bag of words approach. QuickConnect outperforms alternative methods and features a convenient tradeoff between accuracy and speed.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
From now on we will refer to image-based maps in which no metric information is used as appearance-based maps.
Throughout the paper, vertex and image will be used interchangeably.
Kd-trees provide no speedup over exhaustive search for spaces with 10 or more dimensions for exact solutions, therefore striving for real time performance we decided for an approximate solution.
All code and dataset is freely available on our website.
It is known that \(2\delta (G)-n+2 \le \alpha (G)\), where \(n\) is the number of vertices (Fiedler 1973).
References
Angeli, A., Doncieux, S., Meyer, J.-A., & Filliat, D. (2008). Real-time visual loop-closure detection. In Proceedings of the IEEE international conference on robotics and automation (pp. 1842–1847).
Angeli, A., Doncieux, S., Meyer, J.-A., & Filliat, D. (2009). Visual topological slam and global localization. In Proceedings of the IEEE international conference on robotics and automation (pp. 4300–4305).
Angeli, A., Filliat, D., Doncieux, S., & Meyer, J.-A. (2008). Fast and incremental method for loop-closure detection using bags of visual words. IEEE Transactions on Robotics, 24(5), 1027–1037.
Aragüés, R., Cortés, J., & Sagüés, C. (2011). Distributed consensus algorithms for merging feature-based maps with limited communication. Robotics and Autonomous Systems, 59(3–4), 163–180.
Aragüés, R., Cortés, J., & Sagüés, C. (2012). Distributed consensus on robot networks for dynamically merging feature-based maps. IEEE Transactions on Robotics, 28(4), 840–854.
Birk, A., & Carpin, S. (2006). Merging occupancy grids from multiple robots. Proceedings of the IEEE, 94(7), 1384–1397.
Booij, O., Terwijn, B., Zivkovic, Z., & Krose, B. (2007). Navigation using an appearance based topological map. In Proceedings of the IEEE international conference on robotics and automation (pp. 3927–3932).
Carpin, S. (2008a). Fast and accurate map merging for multi-robot systems. Autonomous Robots, 25(3), 305–316.
Carpin, S. (2008b). Merging maps via Hough transform. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 1878–1883).
Cummins, M., & Newman, P. (2005). Highly scalable appearance-only slam fab-map 2.0. In Robotics science and systems.
Danesi, A., Fontanelli, D., & Bicchi, A. (2006). Visual servoing on image maps. In Proceedings of the IEEE international symposium on experimental, robotics (pp. 277–286).
Dedeoglu, G., & Sukhatme, G. S. (2000). Landmark-based matching algorithm for cooperative mapping by autonomous robots. In Distributed autonomous robotic systems (Vol. 4, pp. 251–260). Tokyo: Springer.
Erinc, G., & Carpin, S. (2009). Image-based mapping and navigation with heterogeneous robots. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 5807–5814).
Erinc, G., & Carpin, S. (2010). Evaluation criteria for appearance-based maps. In Proceedings of performance metrics for intelligent systems.
Erinc, G., & Carpin, S. (2012). Anytime merging of appearance based maps. In Proceedings of the IEEE international conference on robotics and automation (pp. 1656–1662).
Ferreira, F., Dias, J., & Santos, V. (2008). Merging topological maps for localisation in large environments. In Proceedings of the international conference on climbing and walking robots and the support technologies for mobile machines.
Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(98), 298–305.
Filliat, D. (2008). Interactive learning of visual topological navigation. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 248–254).
Fraundorfer, F., Engels, C., & Nister, D. (2007). Topological mapping, localization and navigation using image collections. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 3872–3877).
Hajjdiab, H., & Laganiere, R. (2004). Vision-based multi-robot simultaneous localization and mapping. In Proceedings of Canadian conference on computer and robot vision (pp. 155–162).
Hedau, V., Hoiem, D., & Forsyth, D. (2009). Recovering the spatial layout of cluttered rooms. In Proceedings of the IEEE international conference on computer vision (pp. 1849–1856).
Ho, K. L., & Newman, P. (2005). Multiple map intersection detection using visual appearance. In International conference on computational intelligence, robotics and autonomous systems.
Huang, W. H., & Beevers, K. R. (2005). Topological map merging. International Journal of Robotics Research, 24(8), 601–613.
Kang, H., Efros, A. A., Hebert, M., & Kanade, T. (2009). Image matching in large scale indoor environment. In IEEE computer society conference on computer vision and pattern recognition workshop on egocentric vision.
Kirkland, S. (2010). Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality. Discrete Mathematics, 310(4), 911–921.
Konolige, K., Fox, D., Limketkai, B., Ko, J., & Steward B. (2003). Map merging for distributed robot navigation. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 212–217).
Kosnar, K., Krajnik, T., & Preucil, L. (2008). Visual topological mapping. In Proceedings of European robotics symposium (Vol. 44, pp. 333–342).
Lee, H.-C., & Lee, B.-H. (2011). Improved feature map merging using virtual supporting lines for multi-robot systems. Advanced Robotics, 25(13–14), 1675–1696.
Lin, Z., Kim, S., & I. Kweon, S. (2005). Recognition-based indoor topological navigation using robust invariant features. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 2309–2314).
Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2), 91–110.
Luo, J., Pronobis, A., Caputo, B., & Jensfelt, P. (2006). The KTH-IDOL2 database. Technical report. KTH Royal Institute of Technology, CVAP/CAS.
Ma, Y., Soatto, S., Kosecka, J., & Sastry, S. S. (2003). An invitation to 3-D vision: From images to geometric models. Berlin: Springer.
Madhavan, R., Scrapper, C., & Kleiner, A. (2009). Special issue on “characterizing mobile robot localization and mapping”. Autonomous Robots, 27, 309–481.
Maohai, L., Bingrong, H., & Ronghua, L. (2006). Novel method for monocular vision based mobile robot localization. In Proceedings of international conference on computational intelligence and security (Vol. 2, pp. 949–954).
Mariottini, G. L., Oriolo, G., & Prattichizzo, D. (2007). Image-based visual servoing for nonholonomic mobile robots using epipolar geometry. IEEE Transactions on Robotics, 23(1), 87– 100.
Mosk-Aoyama, D. (2008). Maximum algebraic connectivity augmentation is np-hard. Operations Research Letters, 36(6), 677–679.
Muja, M., & Lowe, D. G. (2009). Fast approximate nearest neighbors with automatic algorithm configuration. In International conference on computer vision theory and applications (pp. 331–340).
Nicosevici, T., & Garca, R. (2009). On-line visual vocabularies for robot navigation and mapping. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 205–212).
Nister, D., & Stewenius, H. (2006). Scalable recognition with a vocabulary tree. In IEEE conference on computer vision and pattern recognition (pp. 2161–2168).
Özkucur, N., & Akin, H. L. (2010). Cooperative multi-robot map merging using fast-SLAM. In J. Baltes et al. (Eds.), Robocup 2009: Robot Soccer World Cup XIII (pp. 449–460). Berlin: Springer.
Philbin, J., & Zisserman, A. (2008). Object mining using a matching graph on very large image collections. In Proceedings of Indian conference on computer vision, graphics & image processing (pp. 738–745).
Pronobis, A., & Caputo, B. (2005). The KTH-INDECS database. Technical report. KTH Royal Institute of Technology, CVAP/CAS.
Quattoni, A., & Torralba, A. (2009). Recognizing indoor scenes. In IEEE conference on computer vision and pattern recognition (pp. 413–420).
Rybski, P. E., Roumeliotis, S. J., Gini, M., & Papanikolopoulos, N. (2008). Appearance-based mapping using minimalistic sensor models. Autonomous Robots, 24, 229–246.
Saeedi Gharahbolagh, S., Paull, L., Trentini, M., Seto, M., & Li, H. (2012a). Efficient map merging using a probabilistic generalized voronoi diagram. In Proceedings of the IEEE/RJS international conference on intelligent robots and systems (pp. 4419–4424).
Saeedi Gharahbolagh, S., Paull, L., Trentini, M., Seto, M., & Li, H. (2012b). Map merging using Hough peak matching. In Proceedings of the IEEE/RSJ international conference on intelliegent robots and systems (pp. 4683–4688).
Santos-Victor, J., Vassallo, R., & Schneebeli, H. (1999). Topological maps for visual navigation. In Proceedings of international conference on computer vision systems (pp. 21–36).
Se, S., Lowe, D., & Little, J. (2001a). Local and global localization for mobile robots using visual landmarks. In Proceedings of the IEEE international conference on intelligent robots and systems (Vol. 1, pp. 414–420).
Se, S., Lowe, D., & Little, J. (2001b). Vision-based mobile robot localization and mapping using scale-invariant features. In Proceedings of the IEEE international conference on robotics and automation (Vol. 2, pp. 2051–2058).
Se, S., Lowe, D., & Little, J. (2002). Mobile robot localization and mapping with uncertainty using scale-invariantvisual landmarks. International Journal of Robotics Research, 21(8), 735–758.
Sivic, J., & Zisserman, A. (2003). Video google: A text retrieval approach to object matching in videos. In Proceedings of the international conference on computer vision (Vol. 2, pp. 1470–1477).
Smith, T. F., & Waterman, M. S. (1981). Identification of common molecular subsequences. Journal of Molecular Biology, 147(1), 195–197.
Tran, T. T. H., & Marchand, E. (2007). Real-time keypoints matching: Application to visual servoing. In Proceedings of the IEEE international conference on robotics and automation (pp. 3787–3792).
Valgren, C., Lilienthal, A., & Duckett, T. (2006). Incremental topological mapping using omnidirectional vision. In Proceedings of the IEEE international conference on intelligent robots and systems (pp. 3441–3447).
Zhou, X. S., & Roumeliotis, S. I. (2006). Multi-robot SLAM with unknown initial correspondence: The robot rendezvous case. In Proceedings of the IEEE/RSJ international conference on intelliegent robots and systems (pp. 1785–1792).
Zivkovic, Z., Bakker, B., & Krose, B. (2005). Hierarchical map building using visual landmarks and geometric constraints. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 2480–2485).
Zivkovic, Z., Bakker, B., & Krose, B. (2006). Hierarchical map building and planning based on graph partitioning. In Proceedings of the IEEE international conference on robotics and automation (pp. 803–809).
Zivkovic, Z., Booij, O., & Krose, B. (2007). From images to rooms. Robotics and Autonomous Systems, 55(5), 411–418.
Zivkovic, Z., Booij, O., Krose, B., Topp, E. A., & Christensen, H. I. (2008). From sensors to human spatial concepts: An annotated data set. IEEE Transactions on Robotics, 24(2), 501–505.
Acknowledgments
A shorter version of this paper appeared at ICRA 2012 (Erinc and Carpin 2012).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Erinc, G., Carpin, S. Anytime merging of appearance-based maps. Auton Robot 36, 241–256 (2014). https://doi.org/10.1007/s10514-013-9352-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-013-9352-1