Fast voxel maps with counting bloom filters

Julian Ryde, Jason J. Corso

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

In order to achieve good and timely volumetric mapping for mobile robots, we improve the speed and accuracy of multi-resolution voxel map building from 3D data. Mobile robot capabilities, such as SLAM and path planning, often involve algorithms that query a map many times and this lookup is often the bottleneck limiting the execution speed. As such, fast spatial proximity queries has been the topic of much active research. Various data structures have been researched including octrees, k-d trees, approximate nearest neighbours and even dense 3D arrays. We tackle this problem by extending previous work that stores the map as a hash table containing occupied voxels at multiple resolutions. We apply Bloom filters to the problem of spatial querying and voxel maps for the example application of SLAM. Their efficacy is demonstrated building 3D maps with both simulated and real 3D point cloud data. Looking up whether a voxel is occupied is three times faster than the hash table and within 10% of the speed of querying a dense 3D array, potentially the upper limit to query speed. Map generation was done with scan to map alignment on simulated depth images, for which the true pose is available. The calculated poses exhibited sub-voxel error of 0.02m and 0.3 degrees for a typical indoor scene with a map resolution of 0.04m.

Original languageEnglish
Title of host publication2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2012
Pages4413-4418
Number of pages6
DOIs
StatePublished - 2012
Event25th IEEE/RSJ International Conference on Robotics and Intelligent Systems, IROS 2012 - Vilamoura, Algarve, Portugal
Duration: 7 Oct 201212 Oct 2012

Publication series

NameIEEE International Conference on Intelligent Robots and Systems
ISSN (Print)2153-0858
ISSN (Electronic)2153-0866

Conference

Conference25th IEEE/RSJ International Conference on Robotics and Intelligent Systems, IROS 2012
Country/TerritoryPortugal
CityVilamoura, Algarve
Period7/10/1212/10/12

Fingerprint

Dive into the research topics of 'Fast voxel maps with counting bloom filters'. Together they form a unique fingerprint.

Cite this