Abstract
In this work we present a novel system for autonomous mobile robot navigation. With only an omnidirectional camera as sensor, this system is able to build automatically and robustly accurate topologically organised environment maps of a complex, natural environment. It can localise itself using such a map at each moment, including both at startup (kidnapped robot) or using knowledge of former localisations. The topological nature of the map is similar to the intuitive maps humans use, is memory-efficient and enables fast and simple path planning towards a specified goal. We developed a real-time visual servoing technique to steer the system along the computed path.
A key technology making this all possible is the novel fast wide baseline feature matching, which yields an efficient description of the scene, with a focus on man-made environments.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aliaga, D. 2001. Accurate catadioptric calibration for real-time pose estimation in room-size environments. In Proc. IEEE Int. Conf. Computer Vision (ICCV), Vancouver, pp. 127–134.
Arya, S., Mount, D., Netanyahu, N., Silverman, R., and Wu, A. 1998. An optimal algorithm for approximate nearest neighbor searching. Journal of the ACM, 45:891–923.
Basri, R., Rivlin, E., and Shimshoni, I. 1998. Visual homing: Surfing on the epipoles. In IEEE International Conference on Computer Vision ICCV’98, Bombay, pp. 863–869.
Beevers, K. and Huang, W. 2005. Loop Closing in Topological Maps. ICRA.
Bischof, H., Wildenauer, H., and Leonardis, A. 2001. Illumination insensitive eigenspaces. In Proc. ICCV01, IEEE Computer Society, pp. 233–238.
Cartwright, B. and Collett, T. 1987. Landmark maps for Honeybees. Biol. Cybernetics, 57:85–93.
Chen, C. and Wang, H. 2005. Appearance-based topological Bayesian inference for loop-closing detection in cross-country environment. IROS, Edmonton, pp. 322–327.
Davison, A. 2003. Real-time simultaneous localisation and mapping with a single camera. Intl. Conf. on Computer Vision, Nice.
Dempster, A.P. 1967. Upper and lower probabilities induced by a multivalued mapping. The Annals of Statistics, (28):325–339.
Demeester, E., Nuttin, M., Vanhooydonck, D., and Van Brussel, H. 2003. Fine motion planning for shared wheelchair control: Requirements and preliminary experiments. International Conference on Advanced Robotics, Coimbra, pp. 1278–1283.
Dijkstra, E.W. 1959. A note on two problems in connection with graphs. Numerische Mathematik, 1:269–271.
Fischler, M. and Bolles, R. 1981. Random sample consensus: A paradigm for model fitting with applications to image analysis. Comm. of the ACM, 24:381–395.
Franz, M., Schölkopf, B., Mallot, H., and Bülthoff, H. 1998. Where did I take that snapshot? Scene-based homing by image matching. Biological Cybernetics, 79:191–202.
Geyer, C. and Daniilidis, K. 2003. Mirrors in motion: Epipolar geometry and motion estimation. Proc. ICCV, Nice, p. 766.
Goedemé, T., Tuytelaars, T., and Van Gool, L. 2004. Fast wide baseline matching with constrained camera position. Computer Vision and Pattern Recognition. Washington, DC, pp. 24–29.
Goedemé, T., Tuytelaars, T., Vanacker, G., Nuttin, M., and Van Gool, L. 2005. Feature based omnidirectional sparse visual path following. IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2005, Edmonton.
Haralick, R., Lee, C., Ottenberg, K., and Nölle, M. 1994. Review and analysis of solutions of the three point perspective pose estimation problem. International Journal of Computer Vision, 13(3):331–356.
Hartley, R. 1992. Estimation of relative camera positions for uncalibrated cameras. In 2nd European Conference on Computer Vision, Springer-Verlag, LNCS 588, pp. 579–587.
Jain, A. 1989. Fundamentals of Digital Image Processing. Prentice Hall.
Jogan, M. and Leonardis, A. 1999. Panoramic eigenimages for spatial localisation, In Proceedings 8th International Conference on Computer Analysis of Images and Patterns(1689), F. Solina, and A. Leonardis, (Eds.), Ljubljana, pp. 558–567.
Jogan, M. and Leonardis, A. 2000. Robust localization using panoramic view-based recogniton, In Proceedings 15th International Conference on Pattern Recognition ICPR’00, Barcelona, Spain, pp. 136–139.
Koenig, S. and Simmons, R. 1996. Unsupervised Learning of Probabilistic Models for Robot Navigation, ICRA.
Košecká, J. and Yang, X. 2004. Global localization and relative pose estimation based on scale-invariant features. ICPR, (4):319–322.
Kröse, B., Porta, J., van Breemen, A., Crucq, K., Nuttin, M., and Demeester, E. 2003. Lino, the User-Interface Robot, First European Symposium on Ambient Intelligence (EUSAI 2003), Veldhoven, The Netherlands, pp. 264–274.
Ledwich, L. and Williams, S. 2004. Reduced SIFT features for image retrieval and indoor localisation. Australasian Conf. on Robotics and Automation ACRA, Canberra.
Loeffler, C., Ligtenberg, A., and Moschytz, G. 1989. Practical Fast 1-D DCT Algoritmh with 11 Multiplications, ICASSP, pp. 988–991.
Lowe, D. 1999. Object recognition from local scale-invariant features. In International Conference on Computer Vision, pp. 1150–1157.
Matas, J., Chum, O., Urban, M., and Pajdla, T. 2002. Robust wide baseline stereo from maximally stable extremal regions. British Machine Vision Conference, Cardiff, Wales, pp. 384–396.
Mariottini, G., Alunno, E., Piazzi, J., and Prattichizzo, D. 2005. Epipole-Based Visual Servoing with Central Catadioptric Camera. IEEE ICRA05, Barcelona.
Mikolajczyk, K. and Schmid, C. 2002. An affine invariant interest point detector. ECCV, 1:128–142.
Millnert, O., Goedemé, T., Tuytelaars, T., Van Gool, L., Huntemann, A., and Nuttin, M. 2006. Range determination for mobile robots using one omnidirectional camera. In International Conference on Informatics in Control, Automation and Robotics, ICINCO 2006, Setubal.
Mindru, F., Moons, T., and Van Gool, L. 1999. Recognizing color patters irrespective of viewpoint and illumination. Computer Vision and Pattern Recognition, 1:368–373.
Nistér, D., Naroditsky, O., and Bergen, J. 2004. Visual Odometry, Conference on Computer Vision and Pattern Recognition. Washington, DC.
Nuttin, M., Demeester, E., Vanhooydonck, D., and Van Brussel, H. 2001. Shared autonomy for wheelchair control: Attempts to assess the user’s autonomy. Autonome Mobile Systeme, pp. 127–133.
Nuttin, M., Vanhooydonck, D., Demeester, E., Van Brussel, H., Buijsse, K., Desimpelaere, L., Ramon, P., and Verschelden, T. 2003. A Robotic Assistant for Ambient Intelligent Meeting Rooms, First European Symposium on Ambient Intelligence (EUSAI 2003), Veldhoven, The Netherlands, pp. 304–317.
Okuma, T., Sakaue, K., Takemura, H., and Yokoya, N. 2000. Real-time camera parameter estimation from images for a Mixed Reality system. In Proc. ICPR, Barcelona, Spain.
Pérer-Fontán, F., Sanmartin, B., Steingaß, A., Lehner, A., Kubista, E., Martin, M.J., and Arbesser-Rastburg, B. 2004. Measurements and modelling of the satellite-to-indoor channel for Galileo. European Navigation Conference GNSS, Rotterdam.
Pollefeys, M., Van Gool, L., Vergauwen, M., Verbiest, F., Cornelis, K., Tops, J., and Koch, R. 2004. Visual modeling with a hand-held camera. International Journal of Computer Vision, 59(3):207–232.
Ranganathan, A., Menegatti, E., and Dellaert, F. 2005. Bayesian inference in the space of topological maps. IEEE Transactions on Robotics
Rekimoto, J. and Ayatsuka, Y. 2000. CyberCode: Designing augmented reality environments with visual tags. Designing Augmented Reality Environments (DARE 2000).
Schmid, C., Mohr, R., and Bauckhage, C. 1997. Local grey-value invariants for image retrieval. International Journal on Pattern Analysis an Machine Intelligence, 19(5):872–877.
Se, S., Lowe, D., and Little, J. 2001. Local and global localization for mobile robots using visual landmarks. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS ’01), Hawaii, USA.
Shafer, G. 1976. A Mathematical Theory of Evidence. Princeton University Press.
Shatkay, H. and Kaelbling, L.P. 1997. Learning topological maps with weak local odometric information. IJCAI, (2):920–929.
Shi, J. and Tomasi, C. 1994. Good features to track. Computer Vision and Pattern Recognition, Seattle, pp. 593–600.
Stricker, D., Daehne, P., Seibert, F., Christou, I.T., Almeida, L., Carlucci, R., and Ioannidis, N.I. 2001. Design and development issues for archeoguide: An augmented reality based cultural heritage on-site guide. In International Conference on Augmented, Virtual Environments and Three-Dimensional Imaging, Mykonos.
Svoboda, T., Pajdla, T., and Hlaváč V. 1998. Motion estimation using panoramic cameras. In Conf. on Intelligent Vehicles, Stuttgart, pp. 335–340.
Svoboda, T. 2000. Central Panoramic Cameras, Design, Geometry, Egomotion, PhD Thesis, Czech Technical University.
Tapus, A. and Siegwart, R. 2005. Incremental Robot Mapping with Fingerprints of Places, IROS, Edmonton.
Tuytelaars, T., Van Gool, L., D’haene, L., and Koch, R. 1999. Matching of affinely invariant regions for visual servoing. International Conferemce on Robotics and Automation, pp. 1601–1606.
Tuytelaars, T. and Van Gool, L. 2000. Wide baseline stereo based on local, affinely invariant regions. British Machine Vision Conference, Bristol, UK, pp. 412–422.
Ulrich, I. and Nourbakhsh, I. 2000. Appearance-based place recognition for topological localisation. In IEEE International Conference on Robotics and Automatisation, San Francisco, pp. 1023–1029.
van Veen, H., Distler, H.K., Braun, S.J., and Bülthoff, H.H. 1998. Navigating through a virtual city: Using virtual reality technology to study human action and perception. Future Generation Computer Systems, 14:231–242.
Vale, A. and Isabel Ribeiro, M. 2003. Environment Mapping as a Topological Representation. ICAR, Coimbra, Portugal.
Zivkovic, Z., Bakker, B., and Kröse, B. 2005. Hierarchical Map Building Using Visual Landmarks and Geometric Constraints, IROS, Edmonton, pp. 7–12.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Goedemé, T., Nuttin, M., Tuytelaars, T. et al. Omnidirectional Vision Based Topological Navigation. Int J Comput Vision 74, 219–236 (2007). https://doi.org/10.1007/s11263-006-0025-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-006-0025-9