Efficient K-nearest neighbor search algorithm for three-dimensional (3D) lidar point cloud in unmanned driving

Patent metadata

Field	Value
Publication number	US-11430200-B2
Application number	US-202117593852-A
Country	US
Kind code	B2
Filing date	Jun 9, 2021
Priority date	Jul 22, 2020
Publication date	Aug 30, 2022
Grant date	Aug 30, 2022

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.

First claim

What is claimed is:

1. An optimal method providing 3D geometric information on an autonomous vehicle's surroundings implemented by a computer having a processor and a memory, wherein a computer instruction is stored on the memory, wherein the computer instruction, when being executed, implements the following steps comprising:
step 1 : calculating an axis-aligned bounding box (AABB) of a disordered point cloud data set;
step 2 : segmenting the AABB obtained in step 1 into S 3D spaces based on an expected radius R set by a user, wherein each 3D space is defined as a voxel, an edge length of each voxel is R re , and R re >R;
step 3 : traversing each piece of point cloud data in the disordered point cloud data set in step 1 , and calculating a specific voxel to which each piece of point cloud data belongs and a quantity of pieces of point cloud data comprised in each voxel;
step 4 : further segmenting a corresponding voxel into a plurality of sub-voxels based on the quantity of pieces of point cloud data comprised in each voxel; assuming that an i th voxel comprises N i pieces of point cloud data, wherein i=1, 2, . . . , I; segmenting the i th voxel into J sub-voxels when N i >T, and ensuring that N j <A, wherein T is a preset threshold,

N
_

J

=

∑

j
=
1

J

⁢

N
j

J

,

N j represents a quantity of pieces of point cloud data comprised in a j th sub-voxel, and A is a parameter adjusted by the user or dynamically adjusted by a scene;
step 5 : segmenting the disordered point cloud data set into a series of voxels and sub-voxels by using step 1 to step 4 , wherein a double segmentation voxel structure (DSVS) data structure is constructed by the series of voxels and sub-voxels;
step 6 : obtaining a search set constructed by search points, and sorting the disordered point cloud data set and the search set based on the DSVS data structure and the configuration information, wherein physical addresses of search points located in an identical voxel or sub-voxel in the search set are neighboring and continuous, the search points are continuously transmitted into a field programmable gate array (FPGA), and a plurality of pieces of data in an identical voxel or sub-voxel on the FPGA are read simultaneously to optimize data transmission and data access on the FPGA; and
step 7 : searching for a search point based on the DSVS data structure by using the K-nearest neighbor search algorithm to obtain K pieces of nearest neighboring point cloud data of the current search point within the expected radius R, wherein step 7 comprises the following steps:
step 701 : calculating a voxel to which the search point belongs, and defining the voxel as a current voxel;
step 702 : calculating distances between the search point and neighboring voxels and/or sub-voxels of the current voxel, wherein a search domain is constructed by the neighboring voxels and/or sub-voxels within a distance range and the current voxel; and
step 703 : traversing pieces of point cloud data in the search domain, and calculating K pieces of nearest neighboring point cloud data of the search point in the pieces of point cloud data to improve search efficiency or energy consumption efficiency of the computer while providing real-time 3D geometric information on an autonomous vehicle's surroundings.

2. The method according to claim 1 , wherein in step 2 , a memory constraint is further considered when the 3D space is segmented, and the memory constraint is as follows:
when a quantity of voxels obtained based on the expected radius R is greater than a maximum quantity M allowed by a memory, the edge length R re of each voxel is greater than the expected radius R when the AABB is segmented, wherein the quantity of voxels obtained though segmentation is not greater than M;
when the quantity of voxels obtained based on the expected radius R is not greater than the maximum quantity M allowed by the memory, the edge length R re of each voxel is equal to the expected radius R when the AABB is segmented.

3. The method according to claim 1 , wherein in step 5 , the DSVS data structure further comprises configuration information, and the configuration information comprises a total quantity of voxels, voxels segmented into sub-voxels, a quantity of corresponding sub-voxels, pieces of point cloud data comprised in each voxel and sub-voxel, and the edge length R re of each voxel.

4. The method according to claim 1 , wherein in step 703 , in a traversal search process, the K pieces of nearest neighboring point cloud data are searched in parallel in forms of an intra-function pipeline and an inter-function data flow by using the FPGA.

5. The method according to claim 1 , wherein a point cloud map matching process is performed by executing either steps 1 to 5 or steps 6 and 7 ;
wherein when a 3D point cloud map already constructed of the autonomous vehicle's surroundings is the disordered point cloud data set in step 1 , the DSVS data structure of the 3D point cloud map is constructed by using step 1 to step 5 ; and
wherein when point cloud data obtained in real time of the autonomous vehicle's surroundings is the search point in step 6 and step 7 , the K pieces of nearest neighboring point cloud data of the point cloud data obtained in real time are found in the 3D point cloud map by using step 6 and step 7 , to realize point cloud map matching.

Assignees

• Univ Shanghai Technology

Inventors

• Sun Hao
• Ha Yajun

Classifications

• G06F18/24147

  Distances to closest patterns, e.g. nearest neighbour classification · CPC title

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title

• G06V10/23 Primary

  based on positionally close patterns or neighbourhood relationships · CPC title

• G06V20/56 Primary

  exterior to a vehicle by using sensors mounted on the vehicle · CPC title

• G06T2207/10028

  Range image; Depth image; 3D point clouds · CPC title