运用 FPGA 实现 3D-LiDAR 中的 NN 搜索：聚焦缓存架构

摘要

3D 激光雷达（3-D LiDAR）传感器对于自动驾驶汽车的定位、感知和地图构建等功能至关重要。然而，它们对计算处理的显著需求仍然是一个重要的缺点。尽管高端 GPU 和 CPU 可以解决上述问题，但其高昂成本和大功耗阻碍了 3D LiDAR 在车辆中的商业应用。本文提出了一种基于现场可编程门阵列（FPGA）的新型最近邻（NN）搜索方法，旨在实现 3D LiDAR 的卓越效率和精确度。该方法旨在提供实时 LiDAR 数据处理方案，在 GPU 和 CPU 平台上均能获得优异结果。该方法包括三个部分：LiDAR 数据预处理、硬件加速 NN 搜索，以及高效的点云数据缓存架构。上述 LiDAR 处理方法已成功在所提 FPGA 平台上实现。实验结果表明，我们定制的测试板能够将 NN 搜索加速到超过 CPU 的能力。最后，我们提出的系统实现了仅 2.8W 的功耗的实时功能。其精度水平可与软件等价物甚至最新的 LiDAR 数据处理技术媲美。

作者

刘越泽 北京理工大学机械工程学院，北京，中国

田一红 北京理工大学先进技术研究院，北京，中国

杨宏伟 北京理工大学先进技术研究院，北京，中国

贾耀汉 北京理工大学机械工程学院，北京，中国

卜占浩 北京理工大学机械工程学院，北京，中国

陈雪梅 北京理工大学先进技术研究院，北京，中国

出版信息

期刊: 2024 IEEE 信号、信息与数据处理国际会议 (ICSIDP) 年份: 2024 页码: 1-6 DOI: 10.1109/ICSIDP62679.2024.10868383 文章编号: 10868383

指标

总下载量: 49

资助

• 中国国家自然科学基金

关键词

IEEE 关键词: Laser radar, Three-dimensional displays, Accuracy, Computer architecture, Data processing, Search problems, Real-time systems, Software, Sensors, Field programmable gate arrays

索引术语: Cache Architecture, Power Consumption, Point Cloud, Real-time Performance, Autonomous Vehicles, Ranging, Caching, Point Cloud Data, Lidar Data, Computation Time, Computational Efficiency, Parallelization, Resource Consumption, Computational Capabilities, Data Frame, Digital Signal Processing, Random Access Memory, Buffer Size, Clock Cycles, ARM Processor, Data Cache, Hardware Architecture, Vertical Angle, Computation Latency

作者关键词: LiDAR, FPGA, Nearest Neighbour, Cache Architecture

未定义

SECTION I. 引言

移动机器人平台，包括机器人和无人驾驶汽车，需要利用标准的激光雷达点云数据，以便在此前未涉足的环境中高效运行 ¹–​²。 同时，定位算法通过从点云数据中提取的地标位置估计构建环境的空间表征，并同时预测机器人姿态和位置 ³。 重要的是，所有空间划分均以所选世界参考系统表示，通常源自机器人的初始坐标。 机器人精确确定姿态和位置的构造中一个重要方面，即对于高速应用（如无人驾驶汽车）至关重要的需求 ⁴。 SLAM ⁵, ⁶ 算法的计算速度至关重要，主要因为在两帧点云数据之间快速执行点到点最小搜索以确定机器人位置所需的巨大计算需求 ⁷, ⁸。

技术僵局仍然存在于平衡计算资源与处理速度，同时确保移动机器人能获得节能、精确的算法结果。 自动化程度往往受所使用的主要基于微处理器的硬件架构功耗的限制 ⁹。 为了解决这一问题，熟练的嵌入式系统设计至关重要，它能提供强大的计算能力并结合低功耗。 现代可重构设备，包括FPGA，包含可配置切片、可重构架构以及适用于浮点应用的嵌入式数字信号处理器（DSP） ¹⁰。 高强度计算算法可以在FPGA上以浮点精度并行处理，优于传统的高级精简指令集计算机（ARM）和GPU平台 ¹¹。 FPGA的特定内存管理和可重构性提供了更高的计算效率 ¹²。 在相同的计算成本水平下，FPGA相比GPU也消耗更少的功率 ¹³, ¹⁴。

K 维（K-d）树是常用的近邻计算方法，因其高效且占用资源低而闻名。然而，由于点云数据量大且分布稀疏，内存占用高是不可避免的。此外，其内在的动态性要求对 K 维（K-d）树进行持续重构 ¹⁵, ¹⁶。这些因素导致在 FPGA 上部署 NN 搜索算法时资源消耗高且效率低。暴力搜索最近邻（BFNN）方法能够在仅需存储基本数据且占用空间极小的情况下求得最优解。然而，该方法需要逐点比较目标与所有候选点以实现 100% 的精度。尽管精确，但该过程计算量大，往往导致计算延迟。本研究旨在缓解这些限制。结合上述算法的优缺点，我们提出基于 FPGA 的缓存架构聚焦 NN 搜索算法。该设计在 FPGA 上实现，利用该过程的高度并行性，为后端应用提供支持。

我们提出一种高效 FPGA 实现的 NN 搜索算法，采用能耗低的数据缓存处理架构，以缓解计算不平衡和延迟。该方法包括一种改进的 BFNN 算法，利用最近邻阈值（NNT）来提升 NN 搜索精度。一种利用 NNT 的机制可减少在不成功匹配中多次迭代导致的时间重复 ¹⁷, ¹⁸。

SECTION II. 设计优化

在本节中，我们详细说明了搜索 NN 值的过程。该过程包括在 FPGA 内开发计算框架、处理原始 LiDAR 数据 ¹⁹、加速 NN 搜索以及配置匹配算法以解决 NN 问题。我们的解释主要聚焦于在学术背景下增强理解。

A. LiDAR 数据预处理

Robosenes LiDAR 传感器的软件驱动已被修改并嵌入到片上处理系统中，编程逻辑充当定制硬件加速器。主数据流输出协议 (MSOP) 和设备信息输出协议 (DIFOP) 为 LiDAR 数据提供结构。DIFOP 包含垂直角度校准 (λch)、水平角度校准 (µch) 以及安装误差参数 (γx, γy)。在误差补偿后数据的精度取决于这些参数，并且这些参数是针对每个 LiDAR 传感器确定的。因此，它们仅需在系统启动时计算一次，然后存储在片上块随机存取存储器 (BRAM) 中。这种方法显著提升了计算效率。LiDAR 数据转换公式如下：

\begin{equation*}\begin{array}{l} X = r \cdot \cos {\omega _{ch}} \cdot \cos \left( {{\alpha _\theta } + {\lambda _{ch}} - {\mu _{ch}}} \right) + {\gamma _x} \cdot \cos {\omega _{ch}} \\ Y = - r \cdot \cos {\omega _{ch}} \cdot \sin \left( {{\alpha _\theta } + {\lambda _{ch}} - {\mu _{ch}}} \right) + {\gamma _x} \cdot \sin {\omega _{ch}} \\ Z = r \cdot \sin {\omega _{ch}} + {\gamma _z} \cdot \sin {\omega _{ch}} \end{array} \end{equation*}

在此背景下，r 表示测量距离，ω 表示 LiDAR 的垂直角度，α 表示 LiDAR 单元的水平旋转角度。坐标的笛卡尔投影记作 X, Y, Z。

为利用 FPGA 硬件固有的并行计算能力并优化存储使用，原始方程被重新表述如下：

\begin{equation*}\begin{array}{l} X = r \cdot \cos {\omega _{ch}} \cdot \left( {\left( {\cos {\alpha _\theta }\cos {\lambda _{ch}} - \sin {\alpha _\theta }\sin {\lambda _{ch}}} \right)\cos {\mu _{ch}} - } \right. \\ \left. {\left( {\sin {\alpha _\theta }\cos {\lambda _{ch}} + \cos {\alpha _\theta }\sin {\lambda _{ch}}} \right)\sin {\mu _{ch}}} \right) + {\gamma _x} \cdot \cos {\omega _{ch}} \\ Y = - r \cdot \cos {\omega _{ch}} \cdot \left( {\left( {\sin {\alpha _\theta }\cos {\lambda _{ch}} + \cos {\alpha _\theta }\sin {\lambda _{ch}}} \right)\cos {\mu _{ch}}} \right. \\ \left. { - \left( {\cos {\alpha _\theta }\cos {\lambda _{ch}} - \sin {\alpha _\theta }\sin {\lambda _{ch}}} \right)\sin {\mu _{ch}}} \right) + {\gamma _x} \cdot \sin {\omega _{ch}} \\ Z = r \cdot \sin {\omega _{ch}} + {\gamma _z} \cdot \sin {\omega _{ch}} \end{array} \end{equation*}

考虑到 LiDAR 在预设频率和周期下的恒定旋转，偏转角 α 在每一次迭代中保持稳定。类似地，发射的垂直角度 ω 虽受具体 LiDAR 系统影响，但同样保持固定状态。正如前述方程所示，余弦和正弦的系数可在系统初始化时确定并预存，以供后续使用。实时处理可使用输入 r，充分利用 FPGA 的并行计算能力。值得注意的是，所提出的优化框架能够在仅三时钟周期内高效执行该方程。这种卓越的效率凸显了其对 NN 搜索的重要性。

在FPGA上实现坐标转换是通过²⁰的定点算术完成的，在每个乘法步骤中使用组合逻辑计算，而时序逻辑留给加法。这利用了FPGA固有的并行处理能力，使单点云数据的坐标转换能够在极快的时间内完成 - 仅仅三个时钟周期，或 15 ns 在 200MHz. 这体现了相较于CPU更高一个数量级的计算能力，展示了一种高效优化的策略。

将LiDAR数据转换为笛卡尔坐标系以获取点云数据后，必须对单帧点云执行姿态变换，以有效识别最近的 NN 点。为实现高效的数据对应，我们采用旋转矩阵 R 和平移向量 t 作为参数。方程如下：

\begin{equation*}R\left[ {\begin{array}{l} {{X_i}} \\ {{Y_i}} \\ {{Z_i}} \end{array}} \right] + \left[ {\begin{array}{l} {{t_x}} \\ {{t_y}} \\ {{t_z}} \end{array}} \right] = \left[ {\begin{array}{l} {{X_o}} \\ {{Y_o}} \\ {{Z_o}} \end{array}} \right]\end{equation*}

在该方程中，Xi, Yi, Zi 表示已补偿 LiDAR 安装误差后的数据，而 Xo, Yo, Zo 表示已完成姿态调整的数据。

B. 数据缓存架构

LiDAR 激光发射原理如图 1 所示。系统每 0.4 度水平旋转一次，并同时通过以太网接口将垂直发射激光的回波距离发送至接收端。由于我们的系统直接处理原始雷达数据，完全可以按激光数据输出格式直接处理并存储原始数据。以 0 度的数据为每帧的起始数据，确保每帧数据的起始点为同一方向的激光回波。此外，数据按顺序存储，因此在搜索最近邻阈值 (NNT) 时不需要排序，NN 值即可快速定位。整体存储架构如图 2 所示。

Fig. 1: 3D-LiDAR 示意图.

原始 LiDAR 数据在预处理后被存储在双倍速率同步动态随机存取存储器（DDR SDRAM）中。通过写通道切换和存储管理架构，数据被分配到预先规划的地址区域，并被标记为“Data Mark”。后算法处理确定其是否充当基本数据“Base Mark”，并在数据存储的地址区域上执行整体标记“All Mark”。鉴于系统处于动态状态，当新数据伴随姿态变化到来时，随后算法会生成 R, t，对新数据执行姿态变换。这确保了可以在点云数据上执行 NN 搜索。BASE 数据和新数据在输入到并行矩阵进行计算和 NN 值检索前会被转置。当一帧数据完成算法计算后，将评估其是否具备“Base”数据的资格；若不合格，则清除数据和 ’mark’ 以释放存储空间。

为实现并行计算矩阵的高效运行，系统直接从缓存读取数据，执行旋转计算，并将结果输入到先进先出（FIFO）预存储中。此过程实现了低延迟、直接输入到并行计算阵列，提升了计算效率。然而，在 FPGA 内部署时，我们必须定义 NNT 值，NNT 代表数据计算操作的截止点，并触发新数据的输入以进行进一步计算。然而，定义 NNT 值并不保证结果一定是绝对 NN 值。因此，基于 Lidar 输入模式和激光旋转模式，系统按数组存储数据。通过搜索并计算后续 50 次，可确保定位到更小的 NN 点，如图 3 所示。首先，系统找到符合 NNT 的红点，但并非最小的。随后所有绿色点都满足 NNT，而只有黄色点对应绝对 NN。此外，我们的方法采用轮询方式读取 ’base’ 数据和 ’data’，寻找与现有 NN 值接近的合适数据。因此，该方法可为后续算法提供更高精度的 NN 值，减少系统计算和迭代时间。

C. 硬件加速NN搜索

为提高计算效率，系统预加载所需的基准数据和实时输入点云数据，并将这些数据集并行化以进行计算，如图 4 所示。 在任何给定的时钟周期内，计算可执行的次数等于数组大小的 i∗k，其中 i 表示查询基准缓冲区的大小，k 表示数据缓冲区的大小。 基准数据以实时方式更新。 在完成单个点云 NN 计算后，系统继续使用之前存储在 FIFO 中的点云数据进行计算。 由于系统仅需搜索 NN 值，在最坏情况下，单个数据点的计算次数与“基准”数量相关；假设“基准”数量为 n，单帧点云数据量为 p，计算频率为 Fre，则最大计算次数为 t = \frac{{(p*n)}}{{(i*k)}}*(1/Fre). 考虑到 16 行 LIDAR 的点云数据量为 14,400，n = 14400 且有 5 个“基准”，频率 Fre = 200MHz，查询基准缓冲区大小 i = 20，数据缓冲区大小 k = 10，“基准”数量 nmax = 5，最长计算时间为 t = 25ms。 由于 LIDAR 的输出频率为 10Hz，单帧输入更新时间为 100ms，该方法可充分满足后续算法的实时要求。 在实践中，借助基于存储序列的搜索方法，计算时间可以进一步减少。

第三节. 实施与实验结果

在本研究领域，我们使用 Verilog 创建了 NN 搜索算法，并在 Xilinx Vitis 2022.1 上实现了它。该过程包括综合和布局布线协议的执行。我们选择了一个定制的开发平台——如图 5 所示——作为目标设备，以评估在资源受限场景中经济可行 FPGA 的可行性。该定制开发板的硬件由 Xilinx XC7K325T-FFG900 组成——其功能与 Kinect-7 相似。该板能够执行 326080 个逻辑单元操作、840 个 DSP48 切片操作，并配备 2GB DDR3 DRAM。

图 2：基于 DDR 缓存的并行数据处理架构图.

图 3：NN 搜索缓存架构图.

图 4：并行搜索阵列计算流程图.

A. NN 策略分析

表 I 展示了所提出的 HA-BFNN 算法在 200MHz 频率和 20∗ 10 并行阵列尺寸下，在硬件平台上的资源利用情况。

表 I:

计算方法在第 II-C 节中描述，即 t = n∗p/i∗k∗(1*/Fre*). 然而，在实际应用中，NNT 的设置可以大幅加速获取 NN 值的速度。后续章节将展示每一次迭代计算所消耗的时间，并根据这些数据平衡资源利用和速度。

图 5：自定义平台.

图 6：计算次数统计

B. 执行时间分解与比较

表 II 显示了 K-d 树、BFNN 以及我们的方法在 i9-14900K 处理器和 FPGA 上的执行时间分解。

表 II:

我们方法性能提升的根源在于算法的内存管理模型和并行化策略，基于第二节所述的硬件架构。表II证实了这一显著影响：基于我们的NN搜索算法相较于暴力NN搜索，在CPU上实现了900倍的提升。然而，当所需算法迭代次数超过第5百分位数时，K‑d树表现更为突出。相比之下，面向FPGA的NN搜索算法在K‑d树算法（需要先在CPU上构建）之上取得了更优的进展。当所需算法迭代次数接近第10百分位数时，它升至与K‑d树相竞争的水平，但若迭代次数少于第5百分位数，数据收敛是可行的，进一步迭代无法为整体指标带来显著精度提升。因此，基于FPGA的NN搜索算法提升了系统效率。

C. 功耗

我们使用功率计评估了整块定制板的功耗。运行NN系统时，功耗读数在2.5到2.8瓦特之间变化。值得强调的是，上述数据已包含板上其他辅助外设的功耗。这意味着NN核心单独的功率需求低于所给的2.5至2.8瓦特范围。

第四节. 结论

本研究提出了一种采用3-D激光雷达技术的新型高性能NN搜索方法。值得注意的是，该方法可以在FPGA上实现实时执行，从而取得了可喜的性能表现。我们提出的NN搜索算法显著加速了NN搜索，性能提升可达900倍，相比BFNN方法。除此之外，我们的方法在与K-d树方法相比时，在五次迭代内展示了更高的精度和更快的速度，这得益于BFNN的逐点搜索策略。值得强调的是，我们基于FPGA的NN搜索展示了与软件实现相当的性能，甚至在仅使用LiDAR作为传感器时，超过了一些最先进的LiDAR NN处理方法。

参考文献

附加参考文献

2. Y. Guo, H. Wang, Q. Hu, H. Liu, L. Liu, and M. Bennamoun, “3D 点云深度学习综述,” IEEE transactions on pattern analysis and machine intelligence, vol. 43, no. 12, pp. 4338–4364, 2020.