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

Design and FPGA implementation of approximate KD-Tree searching accelerator for ICP

作　　者：郑凯磊 陈强 肖昊 ZHENG Kailei;CHEN Qiang;XIAO Hao(School of Microelectronics,Hefei University of Technology,Hefei 230601,China)

机构地区：[1]合肥工业大学微电子学院,安徽合肥230601

出　　处：《合肥工业大学学报（自然科学版）》2024年第12期1648-1654,共7页Journal of Hefei University of Technology：Natural Science

基　　金：国家自然科学基金资助项目(61974039)。

摘　　要：为了加速迭代最近点(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内完成近30000个点的最近点搜索。研究结果表明,与相关的设计相比,该文提出的硬件加速方法可以有效降低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 30000 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.

关 键 词：K维树(KD-Tree) 迭代最近点(ICP)算法 三维重建 硬件加速 现场可编程门阵列(FPGA) 

分 类 号：TN791[电子电信—电路与系统] TN402