在智能车辆中 3D LIDAR 定位与映射的 K-Nearest-Neighbor 搜索算法的高效 FPGA 实现

摘要

K-Nearest-Neighbor search (KNN) 已被广泛用于基于 3D 激光点云的智能车辆定位与映射。考虑到定位的实时需求和智能车辆的严格电池约束，开发高能效的 KNN 实现是一大挑战。过去的 KNN 实现要么无法高效构建搜索数据结构，要么无法在大规模且分布不均匀的点云中高效搜索。为了解决这个问题，我们提出了一个新的框架来优化 FPGA 上的 KNN 实现。首先，我们提出了一种具有空间细分方法的新型数据结构，即使在大规模点云中也能高效构建。其次，基于我们的数据结构，我们提出了一种能够在分布不均匀的点云中高效搜索的 KNN 搜索算法。我们已在 FPGA 和 GPU 上实现了这一新框架。能效结果表明，我们提出的方法平均比现有最先进的 FPGA 平台 KNN 实现高 2.1 倍，比 GPU 平台高 6.2 倍。

作者

Hao Sun 上海技术大学信息科学与技术学院，上海，中国；中国科学院上海微系统与信息技术研究所，上海，中国；中国科学院大学电子、电气与通信工程学院，北京，中国 ORCID: 0000-0003-4518-2533

Xinzhe Liu 上海技术大学信息科学与技术学院，上海，中国；中国科学院上海微系统与信息技术研究所，上海，中国；中国科学院大学电子、电气与通信工程学院，北京，中国 ORCID: 0000-0002-7557-4960

Qi Deng 上海技术大学信息科学与技术学院，上海，中国；中国科学院上海微系统与信息技术研究所，上海，中国；中国科学院大学电子、电气与通信工程学院，北京，中国

Weixiong Jiang 上海技术大学信息科学与技术学院，上海，中国；中国科学院上海微系统与信息技术研究所，上海，中国；中国科学院大学电子、电气与通信工程学院，北京，中国 ORCID: 0000-0002-6014-6453

Shaobo Luo 巴黎-埃斯特大学，法国巴黎

Yajun Ha 信息科学与技术学院，上海科技大学，上海，中国 ORCID: 0000-0003-4244-5916

发表信息

期刊: IEEE Transactions on Circuits and Systems II: Express Briefs 年份: 2020 卷号: 67 期号: 9 页码: 1644-1648 DOI: 10.1109/TCSII.2020.3013758 文章编号: 9154442 ISSN: 印刷版 ISSN: 1549-7747, 电子版 ISSN: 1558-3791

统计数据

论文引用数: 25 总下载量: 1788

资金来源

• 上海市科技委员会资金（资助号：19511131200）

关键词

IEEE 关键词: 三维显示，现场可编程门阵列，数据结构，激光雷达，建筑，图形处理单元，索引

索引词条: 搜索算法, K最近邻, 光检测与测距, 高效实现, 智能车辆, 数据结构, 能源效率, 点云, 基数, 点值, 包围盒, 树结构, 数据空间, 边长, 哈希函数, 临近区域, 测试平台, 平方欧几里得距离, 查询集, 查询点, 相邻体素, 同时定位与地图构建, 搜索区域, 最小包围盒

作者关键词: K最近邻搜索, FPGA, 3D LIDAR定位与地图构建, 智能车辆, KNN

未定义

第一节. 引言

虽然广泛使用，KNN 在智能汽车中尤其有用，用于将当前的 LIDAR（Light Detection and Ranging）点云帧与一个包含超过 50000 个点且点分布在 100 \times 100 \times 5 m^{3} 宽广空间的大型 LIDAR 点云地图匹配。KNN 是多种 SLAM（Simultaneous Localization and Mapping）算法中的关键步骤 ¹，因为匹配两点云对于纠正任何定位误差至关重要。与图像点云不同，LIDAR 点云通常在车辆周围广阔区域内分布不均匀。激光点云的对象分类一直具有挑战性且尚未得到充分研究。因此，在匹配两组激光点云时，我们必须严重依赖 KNN 算法，该算法在激光点云地图中寻找最近的 K 个邻居作为配对点。尽管 KNN 使用简单的操作在大规模点云地图中搜索，但它占匹配过程的约 80% ²。考虑到定位的实时要求和智能汽车的严苛电池约束，开发能够在时间约束下尽可能少耗电量计算 KNN 结果的高能效 KNN 实现是一项巨大挑战。

已有多项研究致力于高效实现 KNN。 首先，研究者尝试使用 GPU 或 FPGA ³ 来加速 KNN，但仅采用暴力等价搜索方法。 他们只能实现有限的能效提升。 其次，研究者提出一种称为 KD-tree ⁴ 的树结构，以在短时间内高效搜索 KNN。 然而，在能够开始搜索之前，需要大量时间来构建大规模点云地图的 KD-tree。 由于智能车辆在更新地图时必须构建该数据结构，KD-tree 的构建时间过长阻碍了其在实际应用中的使用，而点云地图往往很大。 参考文献 ⁵ 提出在 GPU 上并行构建 KD-tree。 它满足速度要求，但耗电不可接受。 第三，研究者提出 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 搜索问题定义如下：给定空间 M 中的一组点 S 和一个查询点 q \in M，寻找在 S 中到 q 最近的 K 个点。对于智能车辆中的 LIDAR SLAM 应用，S 由周围点云地图中的点组成，称为参考集。通常，参考集庞大且在广阔区域内分布不均。查询 q 由一帧 LIDAR 数据中的特征点构成。M 是三维向量空间，采用平方欧氏距离测量。

在激光雷达（LIDAR）应用中，只有在特定范围内的邻居才具有意义。如果KNN结果与查询点相距较远，则该查询点将被视为离群点。我们定义一个预设的搜索范围 R_{in}，在该范围内我们确保所有邻居都能被搜索，而对范围外的点关注较少。R_{in} 表示用户的需求，构建过程和搜索过程都与之相关。首先，我们对点云进行分割，得到一组体素，其边长等于 R_{in}。如果一个体素内的点数超过阈值，我们将该体素细分为若干子体素。我们将阈值记为 T_{voxel}。在搜索过程中，我们仅在相邻体素和子体素内的预设范围 R_{in} 内搜索KNN，以避免在不断扩大的搜索圆中进行冗余搜索 ¹¹。

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

图 1. DSVS 框架概览.

主要有三个与搜索KNN相关的模块：

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

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

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

第III节。DSVS 数据结构

本节中，我们介绍DSVS数据结构以及如何构建它。

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

\begin{align*} highbound=&\{x_{max},y_{max},z_{max}\} \\ lowerbound=&\{x_{min},y_{min},z_{min}\}\tag{1}\end{align*}

接下来，我们将 AABB 分割成一组体素。理想情况下，每个体素的边长应等于 {R}_{in}。然而，由于体素的内存资源有限，边长可能会被放大以避免溢出。实际获得的边长记为 {R}_{re}，其中 {R}_{re} \ge {R}_{in}。每个轴上的体素数量记为 {VS = \{ {VS}_{x},{VS}_{y},{VS}_{z} \} }，计算公式为

\begin{equation*} VS = \left({{\frac{highbound - lowerbound }{ {R_{re}}}} }\right)\tag{2}\end{equation*}

为了快速确定某个点所在的体素，我们为每个体素分配一个索引。给定一个点 p=\{x,y,z\}，我们假设该点被分配到一个索引为 {vp}= \{{vp}_{x}, {vp}_{y}, {vp}_{z}\} 的体素中。vp 可以通过以下方式计算得出

\begin{equation*} vp \leftarrow voxel(p) = floor\left({{\frac{p - lowerbound }{ {R_{re}}}} }\right)\tag{3}\end{equation*}

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

\begin{equation*} hash(p) = {vp}_{x} * {VS}_{y} * {VS}_{z} + {vp}_{y} * {VS}_{z} + {vp}_{z}\tag{4}\end{equation*}

按照上述过程，我们可以快速计算包含特定点的体素索引。当某个体素内的点数超过阈值 T_{voxel} 时，我们进一步将其分割成一组子体素，每个子体素最多包含 K 个点，原因如下： (1) 第二次分割可以消除大量冗余搜索，因为只需要找到最多 K 个最近邻。 (2) 第二次分割即使在不均匀点云中也能实现高效搜索，因为体素不会变得过于稠密。与 GBDS ¹² 相比，这具有显著优势。

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

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

经过两级分割后，给点 p 添加了两个属性 hash 和 sub\_{}hash，

\begin{equation*} p = \{x,y,z,hash,sub\_{}hash \}\tag{5}\end{equation*}

x,y,z 代表点 p 的位置。hash 代表体素索引，sub\_{}hash 代表在 hash 体素内的子体素索引。如果由 hash 指定的体素尚未进一步细分，sub\_{}hash 将被赋予非子体素标志。由于我们拥有所有点的 hash 与 sub\_{}hash 值，我们按一种方式对它们进行排序，使得同一体素及子体素中的点按顺序连续存放在物理连续内存中。排序后的点极大地有利于硬件实现。首先，当在同一体素或子体素内遍历点时，可以获得更高的 DDR 到 PL 侧的数据传输速度。其次，已排序的点意味着我们可以使用参考集合的循环分区来并行访问更多点。

第四节. KNN 搜索算法

本节中，我们介绍基于 DSVS 的 KNN 搜索过程。其步骤包括： (1) 计算查询点的 hash 与 sub\_{}hash 值； (2) 以查询点为中心在 R_{in} 范围内选择相邻体素和子体素作为搜索区域； (3) 遍历搜索区域内的点，计算其与查询点的平方欧氏距离，并选择 KNN。

对于给定的查询点，其 hash 值可按式（4）计算。在 hash 级别上，我们通过模拟半径为 R_{in} 的球来寻找附近的区域。所有与该球相交或位于球内的体素都被标记为候选搜索体素。随后，我们遍历这些候选体素，剔除距离 R_{in} 之外的子体素。

最终的搜索区域由不可二次细分的体素以及范围为 R_{in} 的子体素构成。正如图 3 所示，搜索区域数量从 6 降至 4.5，候选邻居数量从 15 降至 7，这归因于二次细分。

图 3. 候选邻居比较。红点表示查询点，红圆圈表示半径为 R_{in} 的理想搜索区域。(a) 仅在体素层面搜索时，{6, 7, 10, 11, 14, 15} 体素（蓝色）中有 15 个候选邻居（黄色）；(b) 在子体素层面搜索时，{10, 11, 14, 15} 体素（蓝色）以及 {6 – 3, 7 – 2} 子体素（蓝色）中有 7 个候选邻居（黄色）。

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

然而，为在硬件上实现搜索过程，仍面临若干挑战。

1. 邻域体素和子体素的动态数量

2. 单个体素或子体素中的点数动态变化

3. 从外部内存访问点会限制性能。同时，PL 侧的块 RAM 数量有限，无法满足大规模参考集的需求。

针对上述三大挑战，我们提出了以下解决方案。

首先，由于体素最大数量的限制，我们用 R_{re} 来实现边长，其中 R_{re} \ge R_{in}。因此，我们可以限制查询点周围 3 \times 3 \times 3 个体素内的搜索区域，该区域应包含半径为 R_{in} 的搜索球。此外，在 DSVS 的构建过程中，我们知道未进行二次分割的体素中的点数受限于 T_{voxel}。因此，邻近体素的数量小于 27，单个体素中的点数小于 T_{voxel}。

其次，针对单个子体素的最大点数，我们也可以将其设定为 T_{voxel}，原因有两个。 (1) 如果一个子体素中的点数超过 T_{voxel}，说明该子体素异常稠密。我们可以忽略那些冗余点，对结果影响极小。 (2) 采用相同的最大值意味着该体素可以被视为特殊子体素，从而降低逻辑复杂度并有利于硬件实现。通过对数据集进行剖析，单个体素中的子体素数可以固定下来，以保证单个子体素中的点数小于 T_{voxel}。一般而言，固定数量可根据参考集的分布及为体素、子体素分配的内存进行调整。因此，单个体素中的子体素数小于固定大小，单个子体素中的点数小于 T_{voxel}。

第三，针对数据集传输和访问挑战，我们基于 DSVS 开发了一种新策略。我们注意到，在 DSVS 数据结构中，点按 hash 和 sub\_{}hash 排序。相同体素和子体素中的点会按顺序放置在内存中。我们还注意到，可以计算查询点的 hash，以同样的方式对它们进行排序。此外，我们知道在搜索 KNN 时，只需要查询点周围的点。基于前述三点特征，我们设计了一个定制的数据集缓冲区。(1) 它支持在将参考集从外部内存传输到 PL 侧时的高速流式接口。 (2) 它使用循环划分的块 RAM，因此同一体素或子体素中的点可同时访问。 (3) 它会持续更新查询点。我们确保当前查询点周围的点始终位于数据集缓冲区中。

图 4 给出了 KNN 搜索过程的概览。在 func_1 中，对每个查询点，我们获取其附近区域，该区域由 R_{in} 范围内的相邻体素和子体素组成。相邻体素采用流水线处理，单个体素内的子体素并行处理。func_2 中，我们挑选附近区域内的点并将其标记为候选邻居。单个体素或子体素内的点并行处理。func_3 中，我们将点数众多的候选邻居划分为若干较小的点组。func_4 中，我们从这些划分后的候选邻居中并行选择 KNN。四个功能被设计为平衡，以实现高性能的数据流操作。函数间的数据通道实现为流类型，以实现任务级流水线。

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

第五节. 实验结果与分析

A. 实验设置

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

在使用 KITTI 数据集对 LOAM 中 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 设计，并使用运行于 200MHz 的 Xilinx UltraScale+MPSoC ZCU102 FPGA 板进行测量。CPU 的功耗由功率计测量。FPGA 的功耗由嵌入式传感器 INA226 ¹⁶ 测量。GPU 的功耗由 NVIDIA Management Library 的 API 测量。

B. 结果与分析

为了将我们的方法与最先进的方法进行比较，我们收集了五种不同KNN实现的结果。第一种是基于CPU的GBDS基线实现，称为GBDS_CPU。第二种是在GPU上实现GBDS，遵循伪代码，称为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倍。

表 I

图5. 不同实现与不同查询集大小的KNN搜索时间.

图6. 不同实现与不同参考集大小的KNN搜索时间.

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

为了验证DSVS的适应性并与先前的基于FPGA的KNN实现 ²¹ 进行比较，我们在案例III上测试了GBDS_FPGA和DSVS_FPGA，并记录了一次查询时间，即总执行时间除以查询次数。表II中的结果表明，DSVS_FPGA的EER是 ²² 的149.86倍，GBDS_FPGA ²³ 的1.15倍。DSVS_FPGA与GBDS_FPGA之间的加速比降低，因为在处理均匀分布的点云时，DSVS几乎退化为GBDS。除此之外，DSVS_FPGA在构建子体素和在子体素中搜索时所需资源比GBDS_FPGA更多。

表 II

第六节 结论

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

参考文献

其他参考文献