Evidence grid-based methods for 3D map matching
- 1 May 2009
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2009 IEEE International Conference on Robotics and Automation
- p. 1637-1642
- https://doi.org/10.1109/robot.2009.5152688
Abstract
Registering multiple sets of 3D range data is a crucial capability for robots. The standard method for matching two sets of range data is to convert the ranges to a point cloud representation, and then use on of the many variants of iterative closest point (ICP). We present a set of alternative methods for matching 3D range scans based on a different data representation: evidence grid maps. Evidence grids are robust to noise and variations in point density, can incorporate an indefinite number of ranges, and explicitly encode empty as well as occupied space. While 3D evidence grids can be huge when naively implemented, we use an optimized octree data structure to efficiently store sparse volumetric maps. To register a series of range scans, we build an evidence grid map for each scan, and then register them together using a several different methods. The first two methods are based on a 3D extension of the classic 2D Lucas-Kanade template matching method, and differ only in whether we match a single large region, or multiple small regions that are selected heuristically. Our third method involves extracting surfaces from the evidence grids, and then running ICP to register the surfaces. We demonstrate our methods and compare them to ICP using two datasets collected by two different subterranean robots.Keywords
This publication has 22 references indexed in Scilit:
- Automatic 3D Underground Mine MappingPublished by Springer Science and Business Media LLC ,2006
- 6D SLAM with approximate data associationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Approximate K-D tree search for efficient ICPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Geometrically stable sampling for the ICP algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- A system for volumetric robotic mapping of abandoned minesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Map building with mobile robots in populated environmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Autonomous underground navigation of an LHD using a combined ICP-EKF approachPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Systems and Experiment Paper: Construction of Panoramic Image Mosaics with Global and Local AlignmentInternational Journal of Computer Vision, 2000
- Spatial learning for navigation in dynamic environmentsIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996
- Algorithm for computer control of a digital plotterIBM Systems Journal, 1965