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

作     者：Sun, Hao Liu, Xinzhe Deng, Qi Jiang, Weixiong Luo, Shaobo Ha, Yajun 

作者机构：ShanghaiTech Univ Sch Informat Sci & Technol Shanghai 201210 Peoples R China Chinese Acad Sci Shanghai Inst Microsyst & Informat Technol Shanghai 200050 Peoples R China Univ Chinese Acad Sci Sch Elect Elect & Commun Engn Beijing 100049 Peoples R China Univ Paris Est F-93162 Paris France 

出 版 物：《IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS》 (IEEE Trans. Circuits Syst. Express Briefs)

年 卷 期：2020年第67卷第9期

页      面：1644-1648页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 

基　　金：Shanghai Science and Technology Commission 

主　　题：Three-dimensional displays Field programmable gate arrays Data structures Laser radar Buildings Graphics processing units Indexes K-nearest-neighbor search FPGA 3D LIDAR localization and mapping smart vehicles KNN 

摘      要：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.