TY - GEN
T1 - Fast voxel maps with counting bloom filters
AU - Ryde, Julian
AU - Corso, Jason J.
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84872326358&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84872326358&partnerID=8YFLogxK
U2 - 10.1109/IROS.2012.6385984
DO - 10.1109/IROS.2012.6385984
M3 - Conference contribution
AN - SCOPUS:84872326358
SN - 9781467317375
T3 - IEEE International Conference on Intelligent Robots and Systems
SP - 4413
EP - 4418
BT - 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2012
T2 - 25th IEEE/RSJ International Conference on Robotics and Intelligent Systems, IROS 2012
Y2 - 7 October 2012 through 12 October 2012
ER -