Efficient FPGA Implementation of K-Nearest-Neighbor Search Algorithm for 3D LIDAR Localization and Mapping in Smart Vehicles

doi:10.1109/TCSII.2020.3013758

	Efficient FPGA Implementation of K-Nearest-Neighbor Search Algorithm for 3D LIDAR Localization and Mapping in Smart Vehicles
	Hao Sun1,2,3 ; Xinzhe Liu1,2,3 ; Qi Deng1,2,3 ; Weixiong Jiang1,2,3 ; Shaobo Luo 4; Yajun Ha1
	2020
发表期刊	IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II: EXPRESS BRIEFS (IF:4.0[JCR-2023],3.7[5-Year])
ISSN	1558-3791
卷号	67 期号:9 页码:1644-1648
发表状态	已发表
DOI	10.1109/TCSII.2020.3013758
摘要	K-Nearest-Neighbor search (KNN) has been extensively used in the localization and mapping based on 3D laser point clouds in smart vehicles. Considering the real-time requirement of localization and stringent battery constraint in smart vehicles, it is a great challenge to develop highly energy-efficient KNN implementations. Unfortunately, previous KNN implementations either cannot efficiently build search data structures or cannot search efficiently in massive and unevenly distributed point clouds. To solve the issue, we propose a new framework to optimize the implementation of KNN on FPGAs. First, we propose a novel data structure with a spatial subdivision method, which can be built efficiently even for massive point clouds. Second, based on our data structure, we propose a KNN search algorithm which is able to search in unevenly distributed point clouds efficiently. We have implemented the new framework on both FPGA and GPU. Energy efficiency results show that our proposed method is on average 2.1 times and 6.2 times higher than the state-of-the-art implementations of KNN on FPGA and GPU platform, respectively.
URL	查看原文
收录类别	SCI ; SCIE ; EI ; CPCI
来源库	IEEE
引用统计	正在获取...
文献类型	期刊论文
条目标识符	https://kms.shanghaitech.edu.cn/handle/2MSLDSTB/123586
专题	信息科学与技术学院_硕士生信息科学与技术学院_PI研究组_哈亚军组信息科学与技术学院_博士生
作者单位	1.School of Information Science and Technology, ShanghaiTech University, Shanghai, China 2.Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai, China 3.School of Electronic, Electrical and Communication Engineering, University of Chinese Academy of Sciences, Beijing, China 4.Universite Paris-Est, Paris, France
第一作者单位	信息科学与技术学院
第一作者的第一单位	信息科学与技术学院
推荐引用方式 GB/T 7714	Hao Sun,Xinzhe Liu,Qi Deng,et al. Efficient FPGA Implementation of K-Nearest-Neighbor Search Algorithm for 3D LIDAR Localization and Mapping in Smart Vehicles[J]. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II: EXPRESS BRIEFS,2020,67(9):1644-1648.
APA	Hao Sun,Xinzhe Liu,Qi Deng,Weixiong Jiang,Shaobo Luo,&Yajun Ha.(2020).Efficient FPGA Implementation of K-Nearest-Neighbor Search Algorithm for 3D LIDAR Localization and Mapping in Smart Vehicles.IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II: EXPRESS BRIEFS,67(9),1644-1648.
MLA	Hao Sun,et al."Efficient FPGA Implementation of K-Nearest-Neighbor Search Algorithm for 3D LIDAR Localization and Mapping in Smart Vehicles".IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II: EXPRESS BRIEFS 67.9(2020):1644-1648.