Efficient K-nearest neighbor (KNN) method for single-frame point cloud of lidar, and application thereof
An efficient K-nearest neighbor (KNN) method for a single-frame point cloud of a LiDAR and an application of the efficient KNN method for the single-frame point cloud of the LiDAR are provided, where the efficient KNN method for the single-frame point cloud of the LiDAR is accelerated by a field-programmable gate array (FPGA). In the efficient KNN method for the single-frame point cloud of the LiDAR, a data structure is established based on point cloud projection and a distance scale. The data structure ensures that adjacent points in space are organized in adjacent memories. A new data structure is efficiently constructed. An efficient nearest point search mode is provided.
1 . An efficient method of reconstructing an ordered point-cloud dataset for a single-frame point cloud of a LiDAR, executed by a KNN accelerator implemented on an FPGA comprising a projection module, a column-scanning scheduler, and an index-table memory, comprising the following steps:
step 1: obtaining unordered point cloud data by using the LiDAR, and projecting a point (x, y, z) onto a matrix based on horizontal and vertical resolution of the LiDAR, wherein a horizontal coordinate of the point (x, y, z) in the matrix is calculated according to h=arctan(y/x)/Δβ, a vertical coordinate of the point (x, y, z) in the matrix is calculated according to v=arctan(z/√{square root over (x 2 +y 2 )})/Δα, Δβ represents horizontal angular resolution of the LiDAR, and Δα represents vertical angular resolution of the LiDAR;
step 2: calculating a distance r from the point (x, y, z) to the LiDAR, and determining a corresponding distance dimension for the point (x, y, z) based on the distance r and a distance range corresponding to different predetermined distance dimensions;
step 3: dividing each column of the matrix obtained in step 1 into N p data blocks, where N p is a positive integer;
step 4: based on the distance dimension, calculated in step 2, corresponding to each point in each data block, obtaining a quantity of points on each distance dimension in each data block in the matrix, and recording the quantity in a statistical table;
step 5: obtaining an index position of a first point on each distance dimension in different data blocks based on the statistical table obtained in step 4, to obtain an index table stored in the index-table memory;
step 6: rearranging all points of the point-cloud based on the index table obtained in step 5 to obtain ordered point cloud data, such that adjacent points in space are organized in adjacent memories.
2 . The method according to claim 1 , further comprising:
step 7: for a target point p(x p , y p , z p ) in a same space, finding K adjacent points of the target point from the ordered point cloud data obtained in step 6, which comprises the following substeps:
step 701: determining positions v q and h q of the target point p(x p , y p , z p ) in the matrix according to
h
q
=
arctan
(
y
p
/
x
p
)
/
Δ
β
and
v
q
=
arctan
(
z
p
/
x
p
2
+
y
p
2
)
/
Δ
α
,
and determining a distance
r
q
=
x
p
2
+
y
p
2
+
z
p
2
;
step 702: narrowing a search region based on a target range, wherein a size of a narrowed matrix is [v q ±arcsin r in /r q )/Δα, h q ±arcsin(r in /r q )/Δβ], a range on the distance dimension is R q ±R in , r in represents the search region, R q represents a distance dimension of the target point p, and R in represents a distance dimension corresponding to r in ; and
step 703: obtaining candidate points of a narrowed region, and calculating and sorting Euclidean distances between all the candidate points and the target point using the KNN selection module to obtain K nearest points.
3 . The method of claim 1 , wherein the FPGA comprises FIFO interfaces to receive a reference set and a query set.