Accelerating Nearest Neighbor Search in 3D Point Cloud Registration on GPUs

The Iterative Closest Points (ICP) algorithm is the most widely used method for estimating rigid transformation in 3D point cloud registration. However, the ICP relies on repeatedly performing computationally intensive nearest neighbor searches (NNS) within 3D space. This dependency becomes a significant bottleneck when processing large datasets, thereby hindering the practical deployment of point cloud technologies in real-world applications. To address this issue, we propose two approximate nearest neighbor search (ANNS) acceleration strategies for efficient improvement of the processing speed of the NNS. Our strategies first voxelize target cloud points and then fill voxels in the 3D coordinate space around the source point cloud in two different ways, which can convert the global nearest neighbor search to a local search. Both the proposed methods are suited to be parallelized on GPUs with a low computational load. Extensive experiments show that our methods significantly accelerate NNS processing while maintaining high accuracy, outperforming most of the currently known approaches.