Efficient K-nearest neighbor search algorithm for three-dimensional (3D) lidar point cloud in unmanned driving
US11430200B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 9, 2021 |
| Grant date | Aug 30, 2022 |
| Priority date | — |
| Expiry date | Jun 9, 2041 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T2207/10028
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.