Automatically and efficiently inferring the hierarchical structure of visual maps

M. Chli, A.J. Davison

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

In Simultaneous Localisation and Mapping (SLAM), it is well known that probabilistic filtering approaches which aim to estimate the robot and map state sequentially suffer from poor computational scaling to large map sizes. Various authors have demonstrated that this problem can be mitigated by approximations which treat estimates of features in different parts of a map as conditionally independent, allowing them to be processed separately. When it comes to the choice of how to divide a large map into such ‘submaps’, straightforward heuristics may be sufficient in maps built using sensors such as laser range-finders with limited range, where a regular grid of submap boundaries performs well. With visual sensing, however, the ideal division of submaps is less clear, since a camera has potentially unlimited range and will often observe spatially distant parts of a scene simultaneously. In this paper we present an efficient and generic method for automatically determining a suitable submap division for SLAM maps, and apply this to visual maps built with a single agile camera. We use the mutual information between predicted measurements of features as an absolute measure of correlation, and cluster highly correlated features into groups. Via tree factorisation, we are able to determine not just a single level submap division but a powerful fully hierarchical correlation and clustering structure. Our analysis and experiments reveal particularly interesting structure in visual maps and give pointers to more efficient approximate visual SLAM algorithms.
Original languageEnglish
Title of host publicationRobotics and Automation, 2009. ICRA '09. IEEE International Conference on
Number of pages8
Publication statusPublished - 2009

Keywords / Materials (for Non-textual outputs)

  • Algorithm design and analysis
  • Cameras
  • Clustering algorithms
  • Filtering
  • Layout
  • Mutual information
  • Optimization methods
  • Robotics and automation
  • Simultaneous localization and mapping
  • State estimation


Dive into the research topics of 'Automatically and efficiently inferring the hierarchical structure of visual maps'. Together they form a unique fingerprint.

Cite this