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

用于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搜索时间复杂度,提高算法性能.
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.

K-dimensional tree(KD-Tree)iterative closest point(ICP)algorithmthree-dimensional reconstructionhardware accelerationfield programmable gate array(FPGA)

郑凯磊、陈强、肖昊

展开 >

合肥工业大学微电子学院,安徽 合肥 230601

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

2024

合肥工业大学学报(自然科学版)
合肥工业大学

合肥工业大学学报(自然科学版)

CSTPCD北大核心
影响因子:0.608
ISSN:1003-5060
年,卷(期):2024.47(12)