Paper: Occupancy Grid Matching

Paper: J.L. Blanco, J. Gonzalez-Jimenez, J.A. Fernandez-Madrigal, “A Robust, Multi-Hypothesis Approach to Matching Occupancy Grid Maps”, Robotica, 2013 (DOI, draft PDF).

Abstract:This article presents a new approach to matching occupancy grid maps by means of finding correspondences between a set of sparse features detected in the maps. The problem is stated here as a special instance of generic image registration. To cope with the uncertainty and ambiguity that arise from matching grid maps, we introduce a modified RANSAC algorithm which searches for a dynamic number of internally consistent subsets of feature pairings from which to compute hypotheses about the translation and rotation between the maps. By providing a (possibly multi-modal) probability distribution of the relative pose of the maps, our method can be seamlessly integrated into large-scale mapping frameworks for mobile robots. This article provides a benchmarking of different detectors and descriptors, along extensive experimental results that illustrate the robustness of the algorithm with a 97% success ratio in loop-closure detection for ~1700 matchings between local maps obtained from four publicly available datasets.


1. Source code and datasets

  • The method described in the article uses and at the same time is a part of the MRPT library mrpt-slam. See mrpt::slam::CGridMapAligner. The modified RANSAC method described in the paper corresponds to options.methodSelection = amModifiedRANSAC.
  • The implementation of feature detectors and descriptors can be found in the MRPT C++ class: mrpt::vision::CFeatureExtraction
  • The evaluation of the 2D optimal rigid-transformation’s covariance is implemented in the function mrpt::scanmatching::leastSquareErrorRigidTransformation()
  • The datasets, the results of the experiments and scripts to reproduce them are available for downloaded here: feature_benchmark.tar.gz

2. The maps used for the characterization

Below are displayed the pairs of submaps used in the training for optimal values of Td, Tδ, as described in the article.
Click on the images to see them in full resolution.