激光点云线性KNN算法FPGA实现及加速

doi:10.3969/j.issn.0255-8297.2023.05.009

Abstract

Abstract: 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.

Key words: 3D laser point cloud matching, K-nearest neighbors (KNN) algorithm, fieldprogrammable gate array (FPGA) acceleration, parallel computing

CLC Number:

CHEN Xiaoyu, YANG Mengxue, LI Changdui, ZHAO Pengcheng. Implementation and Acceleration of Linear KNN Algorithm for Laser Point Cloud Based on FPGA[J]. Journal of Applied Sciences, 2023, 41(5): 831-839.

References

[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)

Implementation and Acceleration of Linear KNN Algorithm for Laser Point Cloud Based on FPGA

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	SONG Hai-feng, CHEN Guang-sheng, JING Wei-peng, YANG Wei-wei. Restricted Boltzmann Machine Algorithm for Image Classifcation and Its Parallel Implementation Based on (2D)² PCA [J]. Journal of Applied Sciences, 2018, 36(3): 495-503.
[2]	ZHANG Shu-fen, DONG Yan-yan, Chen Xue-bin. HKM Clustering Algorithm Design and Research Based on Hadoop Platform [J]. Journal of Applied Sciences, 2018, 36(3): 524-534.