Abstract: 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-dimensional tree (KD-Tree), on the field programmable gate array (FPGA). The feasibility of approximate KD-Tree is analyzed with the result showing that this data structure can meet the precision requirements 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 determine 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.
Keywords: K-dimensional tree (KD-Tree); iterative closest point (ICP) algorithm; three-dimensional reconstruction; hardware acceleration; field programmable gate array (FPGA)
合肥工业大学学报自科版