Keypoint design and evaluation for place recognition in 2D lidar maps

We address the place recognition problem, which we define as the problem of establishing whether an observed location has been previously seen, and if so, determining the transformation aligning the current observations to an existing map. In the contexts of robot navigation and mapping, place recognition amounts to globally localizing a robot or map segment without being given any prior estimate. An efficient method of solving this problem involves first selecting a set of keypoints in the scene which store an encoding of their local region, and then utilizing a sublinear-time search into a database of keypoints previously generated from the global map to identify places with common features. We present an algorithm to embed arbitrary keypoint descriptors in a reduced-dimension metric space, in order to frame the problem as an efficient nearest neighbor search. Given that there are a multitude of possibilities for keypoint design, we propose a general methodology for comparing keypoint location selection heuristics and descriptor models that describe the region around the keypoint. With respect to selecting keypoint locations, we introduce a metric that encodes how likely it is that the keypoint will be found in the presence of noise and occlusions during mapping passes. Metrics for keypoint descriptors are used to assess the distinguishability between the distributions of matches and non-matches and the probability the correct match will be found in an approximate kk-nearest neighbors search. Verification of the test outcomes is done by comparing the various keypoint designs on a kilometers-scale place recognition problem. We apply our design evaluation methodology to three keypoint selection heuristics and six keypoint descriptor models. A full place recognition system is presented, including a series of match verification algorithms which effectively filter out false positives. Results from city-scale and long-term mapping problems illustrate our approach for both offline and online SLAM, map merging, and global localization and demonstrate that our algorithm is able to produce accurate maps over trajectories of hundreds of kilometers.