Design and FPGA implementation of approximate KD-Tree searching accelerator for ICP
To shorten the time that k-nearest neighbor(KNN)searching process in iterative closest point(ICP)algorithm takes,a high-performance KNN accelerator is designed,with approximate K-di-mensional tree(KD-Tree),on the field programmable gate array(FPGA).The feasibility of approxi-mate KD-Tree is analyzed with the result showing that this data structure can meet the precision re-quirements of ICP algorithm and boost its parallel degree as well as performance.To improve the time-consuming tree building phase of approximate KD-Tree,a tree building calculation module,which is based on merge sort and equipped with feedback data channels,is made to be able to deter-mine 256 space nodes and finish tree building in 8.95 ms.To better point cloud searching process,a point cloud searching module with high throughput rate is created so that it can execute the nearest search of almost 30 000 points in 0.49 ms.The research results show that,compared to other relevant designs,the hardware acceleration method in this paper can significantly lower the complexity of KNN searching time and upgrade the performance of ICP algorithm.