上海科技大学知识管理系统

An efficient K-nearest neighbor search algorithm for three-dimensional (3D) lidar point cloud in unmanned driving and a use of the foregoing K-nearest neighbor search algorithm in a point cloud map matching process in the unmanned driving are provided. A novel data structure for fast K-nearest neighbor search is used, such that each voxel or sub-voxel includes a proper quantity of points to reduce redundant search. The novel K-nearest neighbor search algorithm is based on a double segmentation voxel structure (DSVS) and a field programmable gate array (FPGA). By means of the novel K-nearest neighbor search algorithm, nearest neighbors are searched for only in a neighboring expected area near a search point, thereby reducing search of redundant points. In addition, an optimized data transmission and access policy is used, which makes the algorithm more fit the characteristic of the FPGA.

提供了一种用于无人驾驶中的三维LiDAR点云的高效k近邻搜索算法，以及前述k近邻搜索算法在无人驾驶中的点云地图匹配过程中的用途。 使用用于快速k近邻搜索的新数据结构，使得每个体素或子体素包括适当数量的点以减少冗余搜索。 本发明基于双分割体素结构(DSVS)和现场可编程门阵列(FPGA)。 本发明仅在搜索点附近的相邻期望区域内搜索最近邻，减少了冗余点的搜索。 另外，采用优化的数据传输和访问策略，使算法更符合FPGA的特点。