A KNN Accelerator Based on Approximate K-D Tree for ICP

In this paper, we propose a software/hardware co-accelerator architecture based on approximate k-d tree for accelerating k-nearest neighbor (KNN) search. Firstly, aiming at the time-consuming operation of sorting large amount of data in the tree building part, we propose an efficient-lightweight parallel pipelined merge sorting acceleration circuit. Secondly, in order to accelerate the exhaustive search of points in a subspace to the greatest extent, we propose a high-speed fully parallel searching acceleration circuit, which can calculate the Euclidean distance of all points in a subspace in parallel. The experimental results show that when the point cloud scale is 32k, our accelerator can complete a 1-NN search in only 2.3ms, and can ensure the accuracy of ICP point cloud registration.