针对三维激光点云线性K最近邻（K-nearest neighbor,KNN）搜索耗时长的问题，提出了一种利用多处理器片上系统（multi-processor system on chip,MPSoC）现场可编程门阵列（field-programmable gate array，FPGA）实现三维激光点云KNN快速搜索的方法。首先给出了三维激光点云KNN算法的MPSoC FPGA实现框架；然后详细阐述了每个模块的设计思路及实现过程；最后利用MZU15A开发板和天眸16线旋转机械激光雷达搭建了测试平台，完成了三维激光点云KNN算法MPSoC FPGA加速的测试验证。实验结果表明：基于MPSoC FPGA实现的三维激光点云KNN算法能在保证邻近点搜索精度的情况下，减少邻近点搜索耗时。
To address the time-consuming problem of 3D laser point cloud for linear K-nearest neighbor (KNN) search, a fast KNN search method based on multi-processor system on chip (MPSoC) field-programmable gate array (FPGA) is proposed. Firstly, the implementation framework of 3D laser point cloud KNN algorithm based on MPSoC FPGA is given. Then, the design ideas and implementation process of each module are elaborated. Finally, the proposed method is validated through tests and verification on platform built based on MZU15A development board and TM-LIDAR-16. Results demonstrate that the 3D laser point cloud KNN algorithm based on MPSoC FPGA can reduce time consumption while ensuring the accuracy of neighboring point search.
[1] Pinkham R, Zeng S, Zhang Z. QuickNN:memory and performance optimization of K-D tree based nearest neighbor search for 3D point clouds[C]//2020 IEEE International Symposium on High Performance Computer Architecture, 2020:180-192.
[2] Zeng S. An object-tracking algorithm for 3D range data using motion and surface estimation[J]. IEEE Transactions on Intelligent Transportatin Systems, 2013, 14(3):1109-1118.
[3] 谭骏祥. 地面LiDAR散乱点云配准关键技术研究[D]. 成都:成都理工大学, 2014.
[4] 王敬轩. 基于GPU加速的图像颜色编辑研究与实现[D]. 杭州:浙江大学, 2016.
[5] Kosuge A, Yamamoto K, Akamine Y, et al. An SoC-FPGA-based iterative-closest-point accelerator enabling faster picking robots[J]. IEEE Transactions on Industrial Electronics, 2021, 68(4):3567-3576.
[6] Park J, Zhou Q Y, Koltun V. Colored point cloud registration revisited[J]. IEEE International Conference on Computer Vision, 2017:143-152.
[7] Kosuge A, Oshima T. An object-pose estimation acceleration technique for picking robot applications by using graph-reusing KNN search[C]//IEEE Graph-Computing (GC 2019), 2019:68-74.
[8] Kosuge A, Yamamoto K. 4.8x faster FPGA-based iterative closest point accelerator for object pose estimation of picking robot applications[J]. IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines, 2019:331-331.
[9] 彭军. 基于新型异构计算平台的数据挖掘算法研究与实现[D]. 成都:电子科技大学, 2015.
[10] Liang S S, Liu Y, Wang C, et al. Design and evaluation of a parallel K-nearest neighbor algorithm on CUDA-enabled GPU[C]//IEEE 2nd Symposium on Web Society, 2010:53-60.
[11] 毋雪雁, 王水花, 张煜东. K最近邻算法理论与应用综述[J]. 计算机工程与应用, 2017, 53(21):1-7. Wu X Y, Wang S H, Zhang Y D. Survey on theory and application of K-nearest-neighbors algorithm[J]. Computer Engineering and Applications, 2017, 53(21):1-7. (in Chinese)
[12] 刘诚诚, 姜瑛. 基于紧密度的模糊加权KNN数据分类方法[J]. 应用科学学报, 2018, 36(4):679-688. Liu C C, Jiang Y. Data classification method of fuzzy weighted K-nearest neighbor based on affinity[J]. Journal of Applied Sciences, 2018, 36(4):679-688. (in Chinese)
[13] 张卓. KNN算法的改进研究及在外卖软件中的应用[D]. 大连:大连交通大学, 2020.
[14] 王振力, 滕藤, 王群, 等. 遥感影像K-最近邻图目标分类改进算法的研究[J]. 地理空间信息, 2021, 19(2):33-35. Wang Z L, Teng T, Wang Q, et al. Research on improved algorithm of K-nearest neighbor map target classification in remote sensing images[J]. Geospatial Information, 2021, 19(2):33-35. (in Chinese)
[15] 蔡孟翔. 基于SVM的改进加权KNN算法对不均衡数据的分类与应用[D]. 合肥:安徽大学, 2020.
[16] 周艳茹. 基于高斯核的KNN算法及其应用[D]. 兰州:兰州大学, 2021.
[17] 代凯, 申棋仁, 吴官朴, 等. 基于激光雷达的SLAM和融合定位方法综述[J]. 汽车文摘, 2021(2):1-8. Dai K, Shen Q R, Wu G P, et al. A review of LiDAR based SLAM and multi-sensor fusion for localization[J]. Automotive Digest, 2021(2):1-8. (in Chinese)
