Place recognition using keypoint voting in large 3D lidar datasets

In developing autonomous solutions for mapping and localization, one problem that often needs to be dealt with is determining when an area is revisited despite having poor or no prior information on the relative alignment error. There are well-formulated approaches for recognizing such matches using the rich information in camera data; however, it is a much more challenging problem using lidar sensors alone. Most existing approaches employ a pairwise place comparison of place descriptors and thus finding matches requires linear time per place. We instead propose the use of a keypoint voting approach to achieve sub-linear matching times. A constant number of nearest neighbor votes per keypoint are queried from a database of local descriptors and aggregated to determine likely place matches. It becomes critical to analyze the distributions of vote scores such that a suitable threshold for matching scores can be determined a priori, so that the system is not overwhelmed by false positives nor starved for true matches. We have empirically determined that the vote scores follow a log-normal distribution, and we are able to fit a parametric model of its hyper-parameters based on the number of neighbors, the number of keypoints in a place, and the total number of keypoints in the database. We demonstrate the performance of our system in a variety of large scale 3D lidar datasets using data collected from a continually scanning handheld lidar sensor, and also on two publicly available lidar datasets.