article

FAB-MAP: Probabilistic Localization and Mapping in the Space of Appearance

Authors:

Paul NewmanAuthors Info & Claims

International Journal of Robotics Research, Volume 27, Issue 6

Pages 647 - 665

https://doi.org/10.1177/0278364908090961

Published: 01 June 2008 Publication History

Abstract

This paper describes a probabilistic approach to the problem of recognizing places based on their appearance. The system we present is not limited to localization, but can determine that a new observation comes from a previously unseen place, and so augment its map. Effectively this is a SLAM system in the space of appearance. Our probabilistic approach allows us to explicitly account for perceptual aliasing in the environment—identical but indistinctive observations receive a low probability of having come from the same place. We achieve this by learning a generative model of place appearance. By partitioning the learning problem into two parts, new place models can be learned online from only a single observation of a place. The algorithm complexity is linear in the number of places in the map, and is particularly suitable for online loop closure detection in mobile robotics.

References

[1]

Bach, F.R. and Jordan, M.I. (2002). Thin junction trees. Advances in Neural Information Processing Systems.

[2]

Bay, H., Tuytelaars, T. and Van Gool, L. (2006). SURF: Speeded Up Robust Features. Proceedings of the 9th European Conference on Computer Vision, Graz, Austria, Vol. 13, pp. 404-417.

[3]

Bishop, Y.M., Fienberg, S.E. and Holland, P.W. (1977). Discrete Multivariate Analysis: Theory and Practice . Cambridge, MA, MIT Press.

[4]

Bowling, M., Wilkinson, D. and Ghodsi, A. (2006). Subjective mapping. Twenty-First National Conference on Artificial Intelligence. Boston, MA, AAAI Press.

[5]

Bowling, M., Wilkinson, D., Ghodsi, A. and Milstein, A. (2005). Subjective localization with action respecting embedding. Proceedings of the International Symposium of Robotics Research.

[6]

Chen, C. and Wang, H. (2006). Appearance-based topological Bayesian inference for loop-closing detection in a cross-country environment. International Journal of Robotics Research, 25(10): 953-983.

Digital Library

[7]

Chow, C. and Liu, C. (1968). Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, 14(3): 462-467.

Digital Library

[8]

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2001). Introduction to Algorithms, 2nd edn. Cambridge, MA, MIT Press .

[9]

Cummins, M. and Newman, P. (2007). Probabilistic appearance based navigation and loop closing. Proceedings IEEE International Conference on Robotics and Automation (ICRA'07), Rome.

[10]

Dementiev, R., Sanders, P., Schultes, D. and Sibeyn, J. (2004). Engineering an external memory minimum spanning tree algorithm. Proceedings 3rd International Conference on Theoretical Computer Science.

[11]

Ferreira, F., Santos, V. and Dias, J. (2006). Integration of multiple sensors using binary features in a Bernoulli mixture model. Proceedings IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems, pp. 104-109.

[12]

Filliat, D. (2007). A visual bag of words method for interactive qualitative localization and mapping. Proceedings IEEE International Conference on Robotics and Automation, 3921- 3926.

[13]

Frome, A., Huber, D., Kolluri, R., Bulow, T. and Malik, J. (2004). Recognizing objects in range data using regional point descriptors. Proceedings of the European Conference on Computer Vision . Berlin, Springer.

[14]

Goedemé, T. (2006). Visual navigation. Ph.D. Thesis, Katholieke Universiteit Leuven.

[15]

Gumbel, E.J. (1958). Statistics of Extremes. New York, Columbia University Press.

[16]

Gutmann, J. and Konolige, K. (1999). Incremental mapping of large cyclic environments . Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA). Monterey, CA, pp. 318-325. http://citeseer.ist.psu.edu/gutmann00incremental.html .

[17]

Ho, K. and Newman, P. (2005a). Combining visual and spatial appearance for loop closure detection. Proceedings of the European Conference on Mobile Robotics .

[18]

Ho, K. and Newman, P. (2005b). Multiple map intersection detection using visual appearance. Proceedings of the International Conference on Computational Intelligence, Robotics and Autonomous Systems, Singapore.

[19]

Ho, K.L. and Newman, P. (2007). Detecting loop closure with scene sequences. International Journal of Computer Vision, 74(3): 261-286.

Digital Library

[20]

Johnson, A. (1997). Spin-Images: a representation for 3-D surface matching. Ph.D. thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.

[21]

Jordan, M.I., Ghahramani, Z., Jaakkola, T.S. and Saul, L.K. (1999). An introduction to variational methods for graphical models. Machine Learning, 37(2): 183-233.

Digital Library

[22]

Kröse, B.J.A., Vlassis, N.A., Bunschoten, R. and Motomura, Y. (2001). A probabilistic model for appearance-based robot localization. Image and Vision Computing, 19(6): 381- 391.

[23]

Lamon, P., Nourbakhsh, I., Jensen, B. and Siegwart, R. (2001). Deriving and matching image fingerprint sequences for mobile robot localization. Proceedings of the IEEE International Conference on Robotics and Automation, Seoul, Korea.

[24]

Levin, A. and Szeliski, R. (2004). Visual odometry and map correlation. Proceedings IEEE Conference on Computer Vision and Pattern Recognition, pp. 611-618.

[25]

Li, F. and Kosecka, J. (2006). Probabilistic location recognition using reduced feature set. IEEE International Conference on Robotics and Automation. Orlando, FL.

[26]

Lowe, D.G. (1999). Object recognition from local scale-invariant features. Proceedings of the 7th International Conference on Computer Vision, Kerkyra, pp. 1150-1157.

[27]

Meila, M. (1999). An accelerated Chow and Liu algorithm: Fitting tree distributions to high-dimensional sparse data. ICML '99: Proceedings of the Sixteenth International Conference on Machine Learning. San Francisco, CA, Morgan Kaufmann, pp. 249-257.

[28]

Meila2-Predoviciu, M. (1999). Learning with mixtures of trees. Ph.D. Thesis, Massachusetts Institute of Technology.

[29]

Mozos, O., Stachniss, C. and Burgard, W. (2005). Supervised learning of places from range data using AdaBoost. Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1730-1735.

[30]

Newman, P. and Ho, K. (2005). SLAM - loop closing with visually salient features . Proceedings of the IEEE International Conference on Robotics and Automation.

[31]

Newman, P.M., Cole, D.M. and Ho, K. (2006). Outdoor SLAM using visual appearance and laser ranging. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Orlando, FL.

[32]

Nister, D. and Stewenius, H. (2006). Scalable recognition with a vocabulary tree. Proceedings of the Conference on Computer Vision and Pattern Recognition, Vol. 2, pp. 2161- 2168.

Digital Library

[33]

Page, L., Brin, S., Motwani, R. and Winograd, T. (1998). The PageRank citation ranking: bringing order to the web. Technical Report, Stanford Digital Library Technologies.

[34]

Ramos, F.T., Upcroft, B., Kumar, S. and Durrant-Whyte, H.F. (2005). A Bayesian approach for place recognition. Proceedings of the IJCAI Workshop on Reasoning with Uncertainty in Robotics.

[35]

Ranganathan, A. and Dellaert, F. (2006). A Rao-Blackwellized particle filter for topological mapping. Proceedings of International Conference on Robotics and Automation, Orlando, FL. http://www.cc.gatech.edu/dellaert/pub/Ranganathan06icra.pdf.

[36]

Schindler, G., Brown, M., and Szeliski, R. (2007). City-scale location recognition. Proceedings IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-7.

[37]

Se, S., Lowe, D.G. and Little, J. (2005). Vision based global localisation and mapping for mobile robots. IEEE Transactions on Robotics, 21(3): 364-375.

Digital Library

[38]

Silpa-Anan, C. and Hartley, R. (2004). Localisation using an image-map. Proceedings of the Australian Conference on Robotics and Automation .

[39]

Silpa-Anan, C. and Hartley, R. (2005). Visual localization and loop-back detection with a high resolution omnidirectional camera. Proceedings of the Workshop on Omnidirectional Vision.

[40]

Sim, R. and Dudek, G. (1998). Mobile robot localization from learned landmarks . Proceedings of the IEEE International Conference on Intelligent Robots and Systems, p. 2.

[41]

Sivic, J. and Zisserman, A. (2003). Video Google: a text retrieval approach to object matching in videos. Proceedings of the International Conference on Computer Vision, Nice, France.

Digital Library

[42]

Squire, D., Müller, W., Müller, H. and Pun, T. (2000). Content-based query of image databases: inspirations from text retrieval. Pattern Recognition Letters, 21(13-14): 1193- 1198.

Digital Library

[43]

Srebro, N. (2001). Maximum likelihood bounded tree-width markov networks . Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence (UAI-01). San Francisco, CA, Morgan Kaufmann, pp. 504-551.

[44]

Torralba, A., Murphy, K.P., Freeman, W.T. and Rubin, M.A. (2003). Context-based vision system for place and object recognition. ICCV '03: Proceedings of the Ninth IEEE International Conference on Computer Vision. Washington, DC, IEEE Computer Society, p. 273

[45]

Ulrich, I. and Nourbakhsh, I. (2000). Appearance-based place recognition for topological localization. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Vol. 2, pp. 1023-1029.

[46]

Wang, J., Zha, H. and Cipolla, R. (2005). Vision-based global localization using a visual vocabulary. Proceedings of the IEEE International Conference on Robotics and Automation.

[47]

Wolf, J., Burgard, W. and Burkhardt, H. (2005). Robust vision-based localization by combining an image-retrieval system with Monte Carlo localization. IEEE Transactions on Robotics, 21(2): 208-216.

Digital Library

[48]

Zivkovic, Z., Bakker, B. and Kröse, B. (2005). Hierarchical map building using visual landmarks and geometric constraints. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 7-12.

Cited By

Yuan CLin JLiu ZWei HHong XZhang F(2024)BTC: A Binary and Triangle Combined Descriptor for 3-D Place RecognitionIEEE Transactions on Robotics10.1109/TRO.2024.335307640(1580-1599)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TRO.2024.3353076
Yin HXu XLu SChen XXiong RShen SStachniss CWang Y(2024)A Survey on Global LiDAR Localization: Challenges, Advances and Open ProblemsInternational Journal of Computer Vision10.1007/s11263-024-02019-5132:8(3139-3171)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s11263-024-02019-5
Khaliq AXu MHausler SMilford MGarg S(2024)VLAD-BuFF: Burst-Aware Fast Feature Aggregation for Visual Place RecognitionComputer Vision – ECCV 202410.1007/978-3-031-72784-9_25(447-466)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72784-9_25
Show More Cited By

Index Terms

FAB-MAP: Probabilistic Localization and Mapping in the Space of Appearance
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Sensors and actuators
2. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision problems
        Reconstruction
  2. Computer graphics
    1. Graphics systems and interfaces
      1. Perception

Recommendations

A pure vision-based topological SLAM system

In this paper, we present a feasible solution to the problem of autonomous navigation in initially unknown environments using a pure vision-based approach. The mobile robot performs range sensing with a unique omnidirectional stereovision system, ...
A Bayesian approach for place recognition

This paper presents a robust place recognition algorithm for mobile robots that can be used for planning and navigation tasks. The proposed framework combines nonlinear dimensionality reduction, nonlinear regression under noise, and Bayesian learning to ...
FAB-MAP: appearance-based place recognition and mapping using a learned visual vocabulary model
ICML'10: Proceedings of the 27th International Conference on International Conference on Machine Learning

We present an overview of FAB-MAP, an algorithm for place recognition and mapping developed for infrastructure-free mobile robot navigation in large environments. The system allows a robot to identify when it is revisiting a previously seen location, on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Robotics Research

International Journal of Robotics Research Volume 27, Issue 6

June 2008

108 pages

ISSN:0278-3649

Issue’s Table of Contents

Publisher

Sage Publications, Inc.

United States

Publication History

Published: 01 June 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

263
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yuan CLin JLiu ZWei HHong XZhang F(2024)BTC: A Binary and Triangle Combined Descriptor for 3-D Place RecognitionIEEE Transactions on Robotics10.1109/TRO.2024.335307640(1580-1599)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TRO.2024.3353076
Yin HXu XLu SChen XXiong RShen SStachniss CWang Y(2024)A Survey on Global LiDAR Localization: Challenges, Advances and Open ProblemsInternational Journal of Computer Vision10.1007/s11263-024-02019-5132:8(3139-3171)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s11263-024-02019-5
Khaliq AXu MHausler SMilford MGarg S(2024)VLAD-BuFF: Burst-Aware Fast Feature Aggregation for Visual Place RecognitionComputer Vision – ECCV 202410.1007/978-3-031-72784-9_25(447-466)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72784-9_25
Morlana JTardós JMontiel J(2024)Topological SLAM in Colonoscopies Leveraging Deep Features and Topological PriorsMedical Image Computing and Computer Assisted Intervention – MICCAI 202410.1007/978-3-031-72120-5_68(733-743)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-72120-5_68
Li KMa YWang XJi LGeng N(2023)Evaluation of Global Descriptor Methods for Appearance-Based Visual Place RecognitionJournal of Robotics10.1155/2023/91503572023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1155/2023/9150357
Dai YWu JWang D(2023)A Review of Common Techniques for Visual Simultaneous Localization and MappingJournal of Robotics10.1155/2023/88728222023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1155/2023/8872822
Li XZhu DLi H(2023)Loop Closure Detection Algorithm Combining Learning-Based Feature Description and Graph SearchProceedings of the 2023 7th International Conference on Electronic Information Technology and Computer Engineering10.1145/3650400.3650489(540-544)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1145/3650400.3650489
Yin PAbuduweili AZhao SXu LLiu CScherer S(2023)BioSLAM: A Bioinspired Lifelong Memory System for General Place RecognitionIEEE Transactions on Robotics10.1109/TRO.2023.330661539:6(4855-4874)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TRO.2023.3306615
Ge FZhang YWang LColeman SKerr D(2023)Double-Domain Adaptation Semantics for Retrieval-Based Long-Term Visual LocalizationIEEE Transactions on Multimedia10.1109/TMM.2023.334513826(6050-6064)Online publication date: 20-Dec-2023
https://dl.acm.org/doi/10.1109/TMM.2023.3345138
Zhang KLi ZMa J(2023)Loop Closure Detection With Bidirectional Manifold Representation ConsensusIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2022.322936424:4(3949-3962)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TITS.2022.3229364
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents