高效 FPGA 实现

针对 3D 的 K-最近邻搜索算法

智能车辆中的 LIDAR 定位与映射

Hao Sun^ID, Xinzhe Liu^ID, Qi Deng, Weixiong Jiang, 研究生会员, IEEE,

Shaobo Luo, and Yajun Ha^ID, 高级会员, IEEE

摘要—K-最近邻搜索（KNN）已被广泛应用于基于 3D 激光点云的智能车辆定位与地图构建。考虑到智能车辆对定位的实时性要求和严格的电池约束，开发高能效 KNN 实现是一大挑战。不幸的是，以往的 KNN 实现要么无法高效构建搜索数据结构，要么无法在大规模且分布不均的点云中高效搜索。为解决此问题，我们提出一种新的框架来优化 FPGA 上的 KNN 实现。首先，我们提出一种基于空间细分方法的创新数据结构，即使在大规模点云中也能高效构建。其次，基于该数据结构，我们提出一种能够在不均匀分布的点云中高效搜索的 KNN 搜索算法。我们已在 FPGA 和 GPU 上实现了该新框架。能效结果表明，我们提出的方法平均比 FPGA 和 GPU 平台上最先进的 KNN 实现高 2.1 倍和 6.2 倍。

关键词—K-最近邻搜索，FPGA，3D LIDAR 定位与映射，智能车辆，KNN

I. 引言

虽然广泛使用，KNN 在尤其 use-

在智能车辆中用于匹配当前 LIDAR 帧

(光探测与测距) 点云与大规模

LIDAR 点云地图，其点数为

超过 50000，且点分布在宽阔空间

超过 100 × 100 × 5m³。KNN 是多样化的关键步骤 vari-

ous SLAM（同步定位与地图构建）算法 algo-

算法 ¹ 因为匹配两点云非常重要

稿件于2020年4月1日收到；2020年6月11日修订；2020年6月28日接受。发表日期为2020年8月3日；当前版本日期为2020年9月3日。本工作得到上海市科学技术委员会资金支持，资助号19511131200。该简报由副编辑J. M. de la Rosa推荐。(通讯作者：Yajun Ha.)

Hao Sun、Xinzhe Liu、Qi Deng 和 Weixiong Jiang 均隶属于上海科技大学信息科学与技术学院，上海 201210，中国；亦隶属于中国科学院上海微系统与信息技术研究所，上海 200050，中国；亦隶属于中国科学院大学电子、电气与通信工程学院，北京 100049，中国。

Shaobo Luo 隶属于法国巴黎东部大学，巴黎 93162，法国 (e-mail: mailto:[email protected]).

Yajun Ha 隶属于上海科技大学信息科学与技术学院，上海 201210，中国 (e-mail: mailto:[email protected]).

本文中一个或多个图的彩色版本可在线查看，网址为 http://ieeexplore.ieee.org.

数字对象标识符 10.1109/TCSII.2020.3013758

以纠正任何定位错误。与图像点云不同，

激光雷达点云通常在

车辆广阔的周围区域。物体分类的

激光点云的分类一直具有挑战性，且尚未得到充分研究-

研究。结果是，当匹配两个激光点云时，我们

必须高度依赖KNN算法，该算法在激光点云地图中找到

最近的K个邻居作为配对

点。虽然KNN使用简单的操作在

庞大的点云地图中搜索，但它占用了约80%的

匹配过程的 ²。考虑到实时定位的

定位及智能车的严格电池约束-

辆，开发高能效的

KNN实现以尽可能低的能耗

能量在满足时限约束下计算KNN结果。

已有多项工作尝试实现-

化KNN效率。首先，研究人员尝试使用GPU或

FPGA ³ 用于加速 KNN，但仅能通过暴力等价-

潜在搜索方法。它们只能实现有限的能耗

效率提升。其次，研究人员提出一种树

结构称为KD-tree ⁴，用于在一

短时间。然而，它需要大量时间来构建KD-

树用于大型点云地图，才开始搜索。

因为构建数据结构在每次智能

车辆更新地图时，KD-tree 的长时间构建

阻止其在实际应用中使用，在点云地图

通常很大。参考⁵提出了一个并行构-

造KD-tree在GPU上的并行。它满足速度需求，但

但代价是不可接受的功耗。第三，研究人员提出

GBDS（基于网格的数据结构）⁶。与KD-tree不同，

GBDS可以快速构建大规模点云地图。它分-

段将数据空间划分为网格，使用用户定义的数量并

仅在附近网格中搜索KNN，而不是在整个数据空间

的整个数据空间。然而，GBDS只在

均匀分布的数据集上表现良好，但在3D LIDAR

点云地图时。处理大规模和不均匀的

点云时，GBDS有些网格为空，其他网格则

密集，这对KNN搜索效率低。进一步，

GBDS需要在扩展-

环中找到足够的候选邻居，浪费时间在异常值上。第四，研究人员

提出了一种在FPGA ⁷ 上的高效大规模ANN搜索。

他们提出了一种高度并行的k选择方法来加速-

速搜索过程，并展示FPGA性能

优于CPU和GPU在高维度、大规模

数据集，但其能耗效率应进一步提升。

为解决这些问题，我们提出了一种使用 HLS（高层次综合）工具实现高效 FPGA 的 KNN 方法。我们的方法包括一种名为 DSVS（双分割体素结构）的新型数据结构，以及基于 DSVS 的新搜索算法。借助 DSVS 数据结构，我们对点云进行有限次数的分割，以生成三维立方体空间（体素）和具有适当点数的子体素。利用搜索算法，我们仅在相邻体素和子体素中搜索最近邻，从而避免在扩展搜索圈内的冗余搜索 ⁸。

本简报的贡献如下：

1. 一种用于快速 KNN 搜索的新型数据结构（DSVS）：确保每个体素或子体素中点的可扩展数量，从而减少冗余搜索。与 GBDS ⁹ 不同，该新结构在每个子空间返回平衡数量的点。与树结构 ¹⁰ 不同，我们仅对数据空间进行有限次数的分割，构建数据结构所需时间极少。

2. 一种基于 DSVS 和 FPGA 的新 KNN 搜索方法，具有以下特性。 (1) 在有限数量的邻近体素和子体素内，在定义良好的范围内搜索 KNN。 (2) 优化的数据传输和访问策略。仅将靠近定义良好范围的点传输，以最小化数据传输流量。一个体素内的点按顺序存储在块 RAM 中，以实现并行访问。

本简报的其余部分组织如下。第二节概述了 DSVS 框架。第三节介绍了新颖的 DSVS 数据结构。第四节介绍了基于 DSVS 的新 KNN 搜索算法。第五节展示了实验结果和分析。第六节给出结论与未来工作。

II. DSVS 框架概述

在本节中，我们首先在 LIDAR SLAM 应用中定义 KNN 搜索问题，然后介绍我们用于高效 KNN 实现的 DSVS 框架。

正式地，KNN 搜索问题定义如下：给定一组点 S 位于空间 M 中，以及查询点 q \in M ，找到 S 中距离 q 最近的 K 个点。对于智能车辆中的 LIDAR SLAM 应用， S 由周围点云地图中的点组成，称为参考集。通常，参考集庞大且分布不均，覆盖广阔区域。查询 q 由一帧 LIDAR 数据中的特征点构成。 M 是三维向量空间，使用平方欧氏距离进行测量。

我们定义一个预定的搜索范围 R_{in} ，在此范围内我们保证可以搜索到所有邻居，同时对范围外的点不作过多关注。 R_{in} 表示用户的需求，构建过程与搜索过程都与之相关。首先，我们对点云进行分段，获得边长等于 R_{in} 的一组体素。如果某个体素中的点数超过阈值，我们将该体素划分为若干子体素。我们将其记作

图 1. DSVS 框架概览。

阈值为 T_{voxel} 。在搜索过程中，我们仅在相邻体素和子体素内的预定范围 R_{in} 内搜索 KNN，以避免在扩展搜索圆 ¹¹ 中进行冗余搜索。

我们在一种将功能强大的 PS（处理系统）和 PL（用户可编程逻辑）集成到同一 FPGA 上的异构系统中实现了 DSVS 框架。如图 1 所示，DSVS 方法包括两个部分：构建 DSVS 数据结构以及基于 DSVS 的 KNN 搜索。通过 HLS 性能分析工具，我们发现对参考集和查询集进行排序不是计算密集型任务，因此我们选择在 PS 侧执行。我们使用 Xilinx Vivado HLS 工具为 FPGA 生成 RTL（寄存器传输级）代码。所有接口都实现了直接内存访问，并且数组被打包以获得最高效的数据传输。

搜索 KNN 主要涉及三个模块：

• 数据集缓冲区：缓存围绕查询点的参考集合中的点。

• 搜索候选邻居：在相邻体素和子体素内的 R_{in} 中搜索候选邻居。

• 硬件并行 K 选取：并行从候选邻居中选择 K 个最近邻。

III. DSVS 数据结构

本节介绍 DSVS 数据结构及其构建方法。

首先，我们需要通过遍历参考集合中的所有点来寻找一个包围盒。每个轴（x、y、z）的最小和最大范围被计算为点云的 AABB（轴对齐包围盒），记为

\begin{aligned} \text{highbound} &= \{x_{max}, y_{max}, z_{max}\} \\ \text{lowerbound} &= \{x_{min}, y_{min}, z_{min}\} \end{aligned} \qquad (1)

接下来，我们将 theABB 划分为一组体素。理想情况下，每个体素的边长应等于 R_{in} 。然而，由于体素的内存资源有限，边长可能被放大以避免溢出。最终得到的边长记为 R_{re} ，其中 R_{re} \ge R_{in} 。每个轴上的体素数量记为 VS = \{VS_x, VS_y, VS_z\} ，计算方式为

VS = \left( \frac{\text{highbound} - \text{lowerbound}}{R_{re}} \right) \qquad (2)

图 2. 构建 DSVS 数据结构的示例。(a) 32 个点的原始点云。(b) 第一次分割结果。(c) DSVS 结果。(d) 第一次分割的信息。第一行表示哈希表。第二行表示每个体素中的点数。(e) 第二次分割的信息。第一行表示每个体素中的子体素数量。第二行表示子哈希表，第三行表示每个子体素中的点数。

为了快速确定哪个体素包含特定点，我们为每个体素分配一个索引。给定点 p = \{x, y, z\} , 我们假设该点被分配到以 vp = \{vp_x, vp_y, vp_z\} 为索引的体素。 vp 可以通过

vp \leftarrow voxel(p) = \lfloor \frac{p - lowerbound}{R_{re}} \rfloor \quad (3)

为简化体素的索引，定义了一个单射哈希函数为：

hash(p) = vp_x * VS_y * VS_z + vp_y * VS_z + vp_z \quad (4)

按之前的程序，我们可以快速计算包含特定点的体素索引。当单个体素中的点数超过阈值 T_{voxel} , 我们会进一步将其分割成一组子体素，每个子体素最多包含 K 个点，原因如下: (1) 第二次分割可以消除大量冗余搜索，因为仅需寻找 K 个最近邻。 (2) 第二次分割使得即使在不均匀点云中也能高效搜索，因为体素被限制为不够密集。与 GBDS ¹² 相比，这是一大优势。

图 2 给出了构建 DSVS 的详细示例。 首先，我们将点云划分为 4 \times 4 个体素。 假设 T_{voxel} = 4 , K = 1 , 然后我们再次将这两个体素（哈希表中的 6 和 7）划分为 2 \times 2 个子体素。 结果，每个体素或子体素都包含相当数量的点。

在两级分割后，两个属性 hash 和 sub_hash 被添加到点 p,

p = \{x, y, z, hash, sub_hash\} \quad (5)

其中 x, y, z 表示点 p 的位置。 hash 表示体素索引，sub_hash 表示 hash 体素中的子体素索引。 如果以 hash 为索引的体素未进一步细分，sub_hash 将被赋予非子体素标记。

因为我们拥有所有点的 hash 和 sub_hash 值，所以我们以一种方式对它们进行排序，使得来自同一体素和子体素的点在物理上连续地按顺序排列。

Fig. 3. Comparison of candidate neighbors. 红点表示查询点，红圆圈代表半径为 R_{in} 的理想搜索区域。 (a) 仅在体素层面搜索时，在 {6, 7, 10, 11, 14, 15} 体素（蓝色）中有 15 个候选邻居（黄色）。 (b) 在子体素层面搜索时，在 {10, 11, 14, 15} 体素和 {6 - 3, 7 - 2} 子体素（蓝色）中各有 7 个候选邻居（黄色）。

内存。已排序的点大大有利于硬件实现。 首先，当在单个体素或子体素中遍历点时，我们可以获得更高的 DDR 到 PL 侧的传输速度。 其次，已排序的点意味着我们可以使用参考集合的循环分区，以并行方式访问更多点。

IV. KNN 搜索算法

本节中，我们介绍基于 DSVS 的 KNN 搜索过程。该过程分为三步： (1) 计算查询点的 hash 和 sub_hash 值； (2) 以查询点的 R_{in} 为中心，选择相邻的体素和子体素作为搜索区域； (3) 遍历搜索区域内的点，计算它们与查询点的平方欧氏距离，并选取 KNN。

对于给定的查询点，hash 值可以由 Eq.(4) 计算得到。在 hash 级别，我们通过模拟半径等于 R_{in} 的球来寻找附近的区域。所有与球相交或在球内的体素被标记为候选搜索体素。随后我们遍历这些候选体素，以去除超出范围的子体素 R_{in}。

最终的搜索区域由（不能被二次细分的）体素和范围为 R_{in} 的子体素组成。如图 3 所示，搜索区域数量从 6 减少到 4.5，候选邻居数量因二次细分从 15 减少到 7。

最终，我们在搜索区域内遍历候选邻居以 K-selection ¹³ 方式选取 KNN。

然而，要在硬件上实现该搜索过程，仍存在若干挑战。

1. 周边体素及子体素的动态数量

2. 体素或子体素中点的动态数量

3. 从外部内存访问点会限制性能。与此同时，PL 侧有限的块 RAM 数量不足以支持大规模参考集。

针对这三个挑战，我们已经制定了以下解决方案。

首先，由于体素最大数量的限制，我们以 R_{re} 为侧长，其中 R_{re} \ge R_{in} 。因此，我们可以限制在 3 \times 3 \times 3 体素中的搜索区域，如图 4 所示。每个查询点的 KNN 搜索过程。

围绕一个查询点，应该包含所需的搜索-

半径为 R_{in} 的球。 此外，来自建筑

DSVS 处理过程，我们知道体素中点的数量

不进行二次分割的体素被限制为 T_{voxel} 。因此，

相邻体素的数量小于 27，且

单个体素中的点数小于 T_{voxel} 。

其次，对于单个子-

体素，我们也可以将其设为 T_{voxel}，原因有两个。

(1) 如果单个子体素中的点数超过 T_{voxel}，

这意味着子体素异常稠密。我们可以忽略

那些多余的点，对结果影响很小。(2)

同样的最大值意味着体素可以被视为

特殊子体素，减少了逻辑复杂度

并有利于硬件实现。对数据集进行分析后

数据集，单个体素中的子体素数可以固定

以保证单个子体素中的点数小于

T_{voxel}。一般而言，固定数可以根据

参考集的分布和分配的内存

体素、子体素。因此，子体素的数量在

单个体素小于固定大小，且点数

在单个子体素中小于 T_{voxel} 。

第三，对于数据集传输和访问挑战，我们

开发了一种基于 DSVS 的新策略。我们注意到

在 DSVS 数据结构中，点按 hash 和

sub_hash。同一体素和子体素中的点将会

放置在内存中。我们还注意到我们可以 cal-

计算查询点的hash以同样方式排序。

此外，我们知道仅需要围绕的点

查询点在搜索 KNN 时需要。基于以下

前面三个特征，我们已经设计了一个定制的数据集

缓冲区。（1）它支持高速数据率流式接口在

将参考集合从外部内存传输到 PL 侧。

（2）它使用循环分区的块 RAM，因此

点在一个体素或子体素中可以同时访问 simultane-

ously. (3) 它持续使用查询点更新。我们

确保围绕当前查询点的点是

始终在数据集缓冲区中。

KNN 搜索过程的概览如图 4 所示。

在 func_1 中，对于每个查询点，我们获取其附近区域

由相邻体素和子体素在范围内组成

R_{in} . 相邻体素在管道中处理，且

子体素在一个体素中并行处理。在 func_2，

我们选择附近区域中的点并将其标记为

候选邻居。点在一个体素或子体素

并行处理。在 func_3，我们将 can-

候选邻居拥有大量点划分为几个

较小的点组。在 func_4，我们并行选择 KNN

从那些划分的候选邻居中。四个函数

旨在平衡以实现高性能的

数据流操作。函数间的数据通道是

实现为流类型以实现任务级流水线。

V. 实验结果与分析

A. 实验设置

数据集和测试平台：我们选择 KITTI ¹⁴ (Visual Odometry/SLAM Evaluation 2012 点云) 作为数据集，并将 LOAM (Lidar Odometry and Mapping) 算法 ¹⁵ 作为测试平台，因为 LOAM 在所选的 KITTI 数据集上取得了最佳结果。在 LOAM 算法中，KNN 用于匹配一帧 LIDAR 数据中的特征点（查询集）与周围点云地图（参考集），以校正车辆姿态。在我们的实验中，首先在 KITTI 点云数据集上运行 LOAM 算法。随后，在调用 KNN 之前，我们将参考集和查询集输出为 PCD 文件。然后，我们使用这两个 PCD 文件测试我们的 KNN，并与最先进的 KNN 实现进行比较。KNN 搜索时间应小于 80 ms，以满足 LOAM 的 1 Hz 频率约束，因为 KNN 搜索过程最多可迭代 10 次以获得最佳匹配结果。应注意的是，数据结构只需构建一次，因为地图在整个匹配过程中保持不变。我们不比较构建时间，因为在典型情况下，GBDS 和 DSVS 的构建时间均少于 20 ms，足够小。

在分析参考集和查询集的大小后

在 LOAM 与 KITTI 数据集中的 KNN 中，我们已评估

两种最具代表性的实现中存在不同的 KNN 实现

情况 I 将参考集大小设为 200000（平均

参考集的平均大小)，K 为 5，查询集大小

从 1000 到 20000。情况 II 将查询集大小设为 10000

(查询集的平均大小)，K 为 5，参考集

大小从 20000 到 400000。

此外，我们随机生成了一个参考集，包含

300,000 个点，并且查询集包含 10,000 个点，作为情况 III，

用于在一般 KNN 搜索中评估我们提出的方法

场景。

实验平台： 所有在 CPU 上报告的结果是在 Intel(R) i5-6300U 2.4GHz CPU 上测得的。 所有在 GPU 上报告的结果是基于 Nvidia GeForce GTX 1080 Ti 显卡测得的。 所有在 FPGA 上报告的结果是使用 Xilinx SDSOC 2018.2 设计，并在 Xilinx UltraScale+MPSoC ZCU102 FPGA 板上以 200MHz 运行测得的。 CPU 的功耗是通过功率计测得的。 FPGA 的功耗是通过嵌入式传感器 INA226 ¹⁶ 测得的。 GPU 的功耗是通过 NVIDIA 管理库的 API 测得的。

B. 结果与分析

为了将我们的方法与最先进的方法进行比较，

我们已收集来自五种不同KNN实现的结果，

实现。第一个是GBDS的基线实现

在CPU上，称为GBDS_CPU。第二个是一个实现

在GPU上实现GBDS ¹⁷，遵循伪代码，

图4。每个查询点的KNN搜索过程。

图5。不同实现在不同查询集大小下的KNN搜索时间。

图6。不同实现在不同参考集大小下的KNN搜索时间。

称为GBDS GPU。第三个是使用¹⁸中的优化策略在FPGA上实现的GBDS，称为GBDS_FPGA。第四个和第五个是我们提出的方法DSVS，在GPU和FPGA上实现，分别称为DSVS GPU、DSVS FPGA。

在图5和图6中，我们分别比较了案例I和案例II的KNN搜索时间。结果显示DSVS_FPGA的性能与GBDS_GPU相当。DSVS_GPU表现最佳，其速度大约是GBDS_GPU和DSVS_FPGA的5到10倍。然而，在考虑能效时，基于FPGA的实现优于GPU。案例I的平均功率和能效在表I中给出。结果表明DSVS_FPGA在能效上表现最佳，其能效是GBDS_FPGA ¹⁹、DSVS_GPU和GBDS_GPU ²⁰的2.1倍、2.8倍和17.4倍。

DSVS_FPGA与GBDS_FPGA之间的能效提升主要来自两个方面：(1) 由于DSVS，我们只需在相邻体素中搜索KNN，而不必在扩展圆中搜索。(2) 如图3所示，DSVS中候选邻居更少。DSVS_FPGA与DSVS_GPU之间的能效提升主要是因为DSVS_FPGA的搜索过程采用高并行度的数据流实现。

为了验证DSVS的适应性并与先前的基于FPGA的KNN实现 ²¹ 进行比较，我们在案例III上测试GBDS_FPGA和DSVS_FPGA，并记录一次查询时间，即总执行时间除以查询次数。表II中的结果显示DSVS_FPGA的EER为

表I

能效比较

表II

基于FPGA实现的比较

分别为149.86倍的²²和1.15倍的GBDS_FPGA ²³。DSVS_FPGA 与 GBDS_FPGA 之间的加速比因 DSVS 在处理均匀分布的点云时几乎退化为 GBDS 而降低。除此之外，DSVS_FPGA 在构建子体素和在子体素中搜索时使用的资源比 GBDS_FPGA 更多。

VI. 结论

在本简报中，我们展示了针对智能汽车中大规模 3D LIDAR 点云的高能效 FPGA 实现 KNN。我们提出了一个 DSVS 框架，以加速 KNN 搜索过程。DSVS 将点云仅分割有限次数，以避免在单个体素中出现过密点。我们已在 FPGA 和 GPU 上高效实现了 DSVS 框架。能效结果表明，我们提出的方法平均比 FPGA 上最先进的 KNN 实现高 2.1 倍，比 GPU 上的高 6.2 倍。未来工作中，我们将研究进一步提升搜索过程的方法，并探索如何平衡体素与子体素的数量。

参考文献