VAN-ICP: GPU-Accelerated Approximate Nearest Neighbor Search for ICP Registration via Voxel Dilation

The Iterative Closest Points (ICP) algorithm and its variants have been widely applied for 3D point cloud registration which estimates the rigid transformation. As the most computationally intensive step in ICP, nearest neighbor search (NNS) takes up most of the execution time, hindering the practical applications of ICP registration. To overcome the bottleneck, we propose a novel approximate nearest neighbor search (ANNS) acceleration scheme, named Voxel dilAtioN (VAN), which can efficiently convert the global search to local (O(n)). Extensive experiments demonstrate that our VAN can drastically boost the NNS processing while keeping a high accuracy. Specifically, our GPU-based VAN-ICP achieves 2.7x, 7.6x, and 13.4x speedup on three datasets compared with the CPU-based ICP implementation of Point Cloud Library (PCL). Source codes are available at https://github.com/mfxox/VAN-ICP.