Fast and energy-efficient K-nearest neighbor (KNN) search accelerator for large-scale point cloud
US12292888B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 18, 2024 |
| Grant date | May 6, 2025 |
| Priority date | — |
| Expiry date | Dec 18, 2044 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/24542
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A fast and energy-efficient K-nearest neighbors search accelerator for a large-scale point cloud is provided. A nearest sub-voxel-selection (NSVS) framework that performs search based on a double-segmentation-voxel-structure (DSVS) search structure is constructed, and a K-nearest neighbors search algorithm for a large-scale point cloud map is implemented on a field programmable gate array (FPGA). The K-nearest neighbors search accelerator is configured for constructing the DSVS search structure, and searching for K-nearest neighbors based on the DSVS search structure. An experimental result on a KITTI dataset shows that the K-nearest neighbors search accelerator has a search speed 9.1 times faster than a state-of-the-art FPGA implementation. In addition, the K-nearest neighbors search accelerator also achieves an optimal energy efficiency, and the optimal energy efficiency is 11.5 times and 13.5 times higher than state-of-the-art FPGA and GPU implementations respectively.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.