用于 ICP 的近似 KD-Tree搜索加速器设计及 FPGA 实现

为了加速迭代最近点(iterative closest point, ICP)算法中 k 近邻 (k-nearest neighbor, KNN) 搜索过程，文章根据近似 K 维树 (K-dimensional tree, KD-Tree) 数据结构，基于现场可编程门阵列 (field programmable gate array, FPGA) 提出一种高性能的 KNN 搜索加速器；分析近似 KD-Tree 数据结构的可行性，结果表明该数据结构能够满足 ICP 算法精度要求，并提高计算的并行度和性能；为了解决近似 KD-Tree 建树过程耗费时间长的问题，设计基于分治归并排序的具有反馈数据通路的树构建计算模块，该模块可在 8.95 ms 内计算出 256 个空间的树节点并完成树构建；为了优化点云暴力搜索过程，设计一种高吞吐率的点云搜索模块，可以在 0.49 ms 内完成近 30 000 个点的最近点搜索。研究结果表明，与相关的设计相比，该文提出的硬件加速方法可以有效降低 KNN 搜索时间复杂度，提高算法性能。

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.