FOG: 快速八叉树生成器用于 LiDAR 点云
摘要
随着各行业对环境逼真沉浸式 3-D 表现需求不断增长，寻找高效的数据表示方式变得至关重要。将 3-D 空间划分为结构化数据格式的常用方法是使用八叉树，主要得益于其在处理稀疏和密集 3-D 数据时的高效性。该方法在涉及汽车光学雷达（LiDAR）传感器的应用中尤为有用，LiDAR 在自动驾驶系统中被广泛使用，能够实时捕获详细的空间信息。本文提出了快速八叉树生成器（FOG）算法，一种利用硬件加速从 3-D LiDAR 点云生成八叉树的创新方法。与 PCL 的八叉树实现相比，FOG 的性能提升可达 88.8%，实现了在嵌入式平台上为高端传感器实时生成八叉树。
作者
Ricardo Roriz ALGORITMI 研究中心/ LASI，米尼奥大学，吉马良斯，葡萄牙 ORCID: 0000-0002-8543-550X
Diogo Costa ALGORITMI 研究中心/ LASI，米尼奥大学，吉马良斯，葡萄牙
Mongkol Ekpanyapong 工程与技术学院，亚洲理工学院，巴吞他尼，泰国
Tiago Gomes ALGORITMI 研究中心/ LASI，米尼奥大学，吉马良斯，葡萄牙 ORCID: 0000-0002-4071-9015
出版信息
期刊: IEEE Sensors Letters 年份: 2025 卷: 9 期: 1 页码: 1-4 数字对象唯一标识: 10.1109/LSENS.2024.3520800 文章编号: 10816469 ISSN: Electronic ISSN: 2475-1472
指标
论文引用: 1 总下载量: 170
关键词
IEEE 关键词: 八叉树, 三维显示, 点云压缩, 传感器, 图像重建, 激光雷达, 代码, 实时系统, PSNR, 可编程门阵列
索引词： Point Cloud, Light Detection And Ranging, 3D Space, Hardware Accelerators, Processing Speed, Real-time Performance, Bounding Box, Root Node, Design Considerations, Level Of Resolution, Peak Signal-to-noise Ratio, Leaf Node, Child Nodes, Obstacle Avoidance, Hardware Resources, Depth-first, Peak Signal-to-noise Ratio Values, Higher Peak Signal-to-noise Ratio, Occupational Codes, Point Cloud Reconstruction, Original Point Cloud
作者关键词： Sensor applications, 3-D light detection and ranging (LiDAR), field-programmable gate array (FPGA), octree
未定义
第 I 节 介绍
随着对逼真3-D环境日益增长的需求，跨行业对高级表示的需求激增，包括汽车制造业。光学测距（LiDAR）传感器正成为现代车辆的关键组成部分，以辅助自动驾驶任务，因为它们能够以高速生成丰富的3-D数据。然而，处理这些大量信息相当具有挑战性，因为大多数车载计算平台由硬件受限的嵌入式系统组成，而传感器每年都在进一步进步。
三维数据表示的最有效方法之一是使用八叉树 1。如图1所示，八叉树的层次结构将三维空间划分为逐渐变小的区域，优化空间数据的组织、存储、检索和处理。这使得八叉树在驾驶相关任务 2 中尤为有价值，例如实时障碍物检测、动态环境映射和规划。除此之外，其固有的下采样结构有助于管理大型激光雷达数据集，降低整体数据存储和计算需求。
Fig. 1. Octree 在 3-D 空间中的可视化.
点云库（PCL）3，是机器人技术和计算机视觉中广泛使用的库，根据其目标应用提供不同的八叉树实现。某些实现支持复杂的数据结构以提供快速搜索功能，而其他实现则针对数据存储，采用基于熵的压缩技术来压缩输出比特流。然而，在实时应用中使用八叉树仍可能面临一些限制。尽管效率和快速访问数据得到保证，但创建和更新数据结构所需的复杂性和时间可能成为瓶颈，尤其是在资源受限的设备上部署时。
本信介绍了快速八叉树生成器（FOG）算法，这是一种硬件加速的八叉树生成方法，通过多树架构实现最终占用比特流的并行生成。为进一步提升性能，FOG 预定义了八叉树的作用边界，并通过使用定点算术简化其计算。所做评估显示，与 PCL 的八叉树实现相比，执行性能提升近 89%，从而使高端传感器在嵌入式平台 Xilinx Zynq UltraScale+ 上实现实时八叉树生成成为可能。
第二节：FOG：快速八叉树生成器
FOG 是一种针对资源受限嵌入式系统优化的八叉树实现。其主要目标是在硬件中生成内存高效的八叉树和节点占用码比特流，以实现 LiDAR 数据的实时处理。FOG 设计侧重于显著影响八叉树生成的关键方面，如其边界框（BB）、内部结构以及比特流的生成方式。
A. 设计考虑
BB: BB 是定义 3-D 数据极限的体积。它设定了所有轴上的最小和最大坐标，确定了构建八叉树的 3-D 空间。大多数八叉树实现会在预处理阶段选择 BB 4，分析点云以确定最大和最小边界，而其他方法使用动态 BB，在向八叉树插入新点时扩展 5。FOG 使用预定义 BB 构建八叉树，这往往会留下少量点在指定感兴趣区域（ROI）之外。这些远处的点通常被视为噪声，因为它们不包含关于周围环境的有用信息。尽管如此，该方法在创建八叉树时显著优化了资源和计算。
八叉树结构: 三维空间中的空间区域由八叉树内部的节点表示。树结构由这些节点之间的互连以及它们存储的信息定义。由于激光雷达数据的稀疏性，八叉树结构通常使用内存指针 6 连接节点。这使得树只在存在数据的地方扩展，避免对空区域进行不必要的细分，并最终优化内存使用。八叉树中最小的细分称为叶子，它们由停止条件决定。在某些实现中，例如 OctSqueeze 7，叶节点由节点能够容纳的最大点数决定。对于包含点数超过阈值的节点，结构会进一步细分，直到满足条件。因此，该结构在密集区域实现更细的细分，在稀疏区域实现更粗的分辨率。相反，OcTr 8 使用固定深度方法，在任何分支中从根到叶节点建立固定数量的细分。这一策略也被 FOG 采用，简化了遍历算法，使其更快、更易实现。八叉树还可以在叶节点中包含额外信息，例如指向点云点的内存指针 9。尽管这可以保留原始点云精度，后者在分割应用中可能是必需的，但它显著增加了生成的八叉树的内存占用。FOG 不会在叶节点上存储任何额外信息。相反，它通过计算其体素的质心生成原始点的粗略近似。
Bitstream generation: 将八叉树结构编码成位流通常涉及遍历树以检索每个节点的占用码。最常见的策略之一是深度优先搜索（DFS），它在回溯到下一分支之前完全遍历一个分支。DFS 的顺序特性确保最终的位流包含独立生成的分支位流，以可预测的顺序连接。这使得 DFS 特别适合并行化处理，例如在 FOG 中部署的硬件。
B. 实现
多叉树架构: FOG实现采用多叉树架构，将空间数据划分为八个较小的八叉树，每个八叉树管理BB的一个八分支。此方法实现并行处理，多点可以同时处理并插入到八叉树中。所有点插入完毕后，所有八叉树的占用序列被连接形成最终的比特流结构，每个八叉树可视为更大父八叉树的一个分支。
八叉树实例: 每个八叉树分配专用内存来存储其节点，节点按顺序组织并按索引标识。一个节点的结构仅包含其八个子节点的信息。为支持回溯操作，每个父节点 ID 存储在内存栈中，使整个八叉树结构更紧凑、更高效。层级计数器补充此过程，通过监控八叉树的深度来判断节点是叶子还是中间节点。为进一步降低内存使用，叶子节点不作为独立节点存储，因为这需要表示八个空子节点。相反，它们仅在其父节点中表示。该策略见图 2，图 2 描述了最大深度为 3 的八叉树的数据结构。根节点（节点 #1），八叉树深度 0，包含三个子节点，即节点 #2、#12 和 #24。随后，节点 #2 是节点 #3、#12、#26、#70 和 #90 的父节点。由于节点 #26 的第二个子节点是叶子节点（深度 3）——标记为 “1”——它不需要进一步的内存资源来存储空节点。
图 2. 由 FOG 管理的八叉树的内存数据结构.
将点插入结构并创建占用代码也是每棵树的任务。点插入到最近一次插入的节点，利用连续点的空间接近性优化遍历速度。算法评估每个节点的 BB，判断点是否位于其中，若在则下移到子节点，若在外则上移到父节点。插入过程在点因位于根的 BB 外而被丢弃，或成功加入叶子节点时完成。一旦所有点都插入完毕，使用 DFS 遍历八叉树生成占用代码比特流。
第三节：评估
FOG 被实现并使用 ALFA 框架进行测试，ALFA 是一套工具，旨在支持开发者在具备硬件加速支持的嵌入式系统上创建和评估基于 LiDAR 的算法。评估环境包括 Xilinx 的 ZCU104 Evaluation Kit 平台，该平台配备了基于四核 Arm Cortex‑A53 处理器的 Zynq UltraScale+ MPSoC、具有 504K 逻辑单元和 1728 DSP 切片的可编程逻辑器件（FPGA）以及 2GB DDR4 内存。
FOG 首先在软件中实现（sFOG），以验证其设计。随后，八叉树生成和占用码提取在 FPGA 上实现为硬件（hFOG）。评估使用来自四台 Velodyne LiDAR 传感器（VLP‑16、HDL‑32、HDL‑64、VLS‑128）的数据，这些数据在不同环境下采集，如崎岖地形、城市和高速公路。对于每个数据集，使用三种不同的八叉树分辨率评估该方法：低（10 cm）、中（5 cm）和高（2.5 cm）。这些数值对应于八叉树达到最大深度时创建的体素大小，直接影响重建点云的分辨率，如图 3 所示。
图 3。不同分辨率水平下，八叉树退化对 Velodyne VLS‑128 帧的可视化表示。(a) 原始点云。(b) 来自高分辨率（2.5 cm）八叉树的重建点云。(c) 来自中分辨率（5 cm）八叉树的重建点云。(d) 来自低分辨率（10 cm）八叉树的重建点云。
评估将 FOG 与 PCL 中的 octreepointcloudcompression 库进行比较，该库的实现提供了与 FOG 类似的结构和功能特性。配置参数汇总在表 1 中，其中 octreeResolution 取值为 10 cm、5 cm 和 2.5 cm。FOG 则由三个参数定义：numberOfNodes，设为 250 000，这是在 hFOG 中分配必要硬件资源以支持八叉树创建所需的；BBCoordinates，定义了 BB 的边界（坐标）；以及 maxDepth。由于硬件限制，为满足所选平台中所有数据集，定义了两组 BBCoordinates。
第一组，Full BB，是一个立方体形状的 BB，尺寸为 200 m，中心位于传感器上。 对于这个 BB，maxDepth 在 11、12 和 13 之间变化，分别对应 10、5 和 2.5 cm 的分辨率。 full BB 被应用于 VLP-16 和 HDL-32 数据集的所有分辨率级别，以及 HDL-64 数据集的低分辨率和中分辨率。 第二个 BBCoordinates 配置定义了一个非立方体 BB，具有 100 m 长度、12 m 宽度的特定 ROI。 当硬件资源有限且需要实时处理时，这种方法通常用于高分辨率传感器，例如 VLS-128。 ROI 包括点云的重要区域，例如传感器移动方向的环境 10。 由于 BB 的尺寸被减小，可以通过将 maxDepth 设置为 8、9 和 10，分别实现 10、5 和 2.5 cm 的八叉树分辨率。 ROI BB 被应用于 HDL-64 数据集的高分辨率级别，以及 VLS-128 数据集的所有分辨率级别。
表 1
A. 性能评估与硬件资源
执行性能: 对于每个不同的数据集/传感器，在不同分辨率级别下的点云帧处理时间已在表 2 中进行总结，其中 \bar{x} 表示计算得到的平均值，\sigma 表示完整数据集的标准差。 总体而言，hFOG 在所有数据集和分辨率下始终优于 PCL 和 sFOG。 hFOG 在中等分辨率下处理 VLP-16 帧耗时 13.7 毫秒，比 PCL（111 毫秒）提升 87.6%，比 sFOG（116 毫秒）提升 88.2%。 对于 HDL-64 的中等分辨率配置，hFOG 处理一帧点云耗时 39.4 毫秒，比 PCL 快 88.8%；而对于 VLS-128，hFOG 处理一帧耗时 47.2 毫秒，比 PCL 提升 68.5%。
表 2
重建点云尺寸与峰值信噪比（PSNR）: 重建点云尺寸表明可以恢复原始数据的多少信息，而 PSNR 则量化原始点云与重建点云之间的相似度。更高的 PSNR 表示更好的质量，即重建图像更接近原始图像，而较低的 PSNR 则表示重建图像失真更大。通常，30–50 dB 的 PSNR 范围表示高质量的点云重建。表 3 总结了获得的结果，显示 PCL 与 sFOG 在几乎所有数据集中表现相似。在中等分辨率水平下，PCL 能恢复近 64.8% 的原始 VLP-16 数据集，峰值信噪比（PSNR）为 70.9 dB，而 sFOG 恢复原始点云的 64.8%，PSNR 为 70.8 dB。对于同一数据集，hFOG 恢复 60.5% 的点云，PSNR 为 57.7 dB。其他数据集中也观察到类似趋势，hFOG 一直重建较小比例的点云，但仍实现良好的 PSNR 值。
表 3
硬件资源: 为加速 FOG 部署硬件加速器会消耗 FPGA 的硬件资源。在所选平台上，FOG 使用了可用 230,400 个 LUT 的 37.31%，460,800 个触发器的 2.53%，312 个 BRAM 块的 87.18%，完全占用所有 96 个 URAM 块，1720 个 DSP 单元的 5.58%，以及 201,600 个 MUX 的 54.95%。
B. 讨论
表 2 和表 3 中的结果表明，在相似条件下，sFOG 与 PCL 在 PSNR 与点云大小方面可以提供相似的性能表现，sFOG 稍快，但仍无法实现实时性能。然而，hFOG 能够在所有数据集上实现实时性能，但代价是略微的 PSNR 降低，主要是由于硬件设计的考量，例如采用固定点运算而非 PCL 与 sFOG 所使用的浮点运算。这在 HDL-64 和 VLS-128 数据集中尤为明显，主要是因为它们点云的密度较高。然而，在需要实时任务时，例如障碍物检测与碰撞规避，FOG 可以成为 PCL 的良好替代方案。另一方面，当点云需要更接近原始数据时，例如用于高清地图或细粒度物体分类，PCL 具有优势，因为它能提供略高的 PSNR 值。在 FOG 中，八叉树的分辨率由设置 BB（边界框）和最大深度决定。当使用非立方体 BB 时，叶子体素会变为非立方体，这意味着各轴之间存在不同的分辨率，而 PCL 则保持统一的分辨率。最后，hFOG 的性能受到硬件资源限制的显著影响，节点固定数量是最突出的一项限制。在处理高分辨率或高密度数据集时，所需节点数可能因特定帧或帧区域而异。由于 hFOG 的预定义 BB 无法按帧动态调整，必须事先仔细定义合适的 BB，以在使用资源、处理速度与八叉树覆盖区域之间取得平衡。
SECTION IV. 结论
本信函提出了 FOG：一种针对嵌入式实时点云处理优化的八叉树生成方法。软件版本的性能与 PCL 的实现相当，而硬件加速的 FOG 在速度上相较软件方案表现出显著提升。然而，对处理速度的优化导致在密集或高分辨率场景下略微降低了 PSNR。未来工作将侧重于提升八叉树结构的内存效率，使得在同一硬件平台上实现更多节点成为可能。此外，FOG 还可以进一步扩展，在获取占用码后集成压缩步骤，类似于 PCL 的 OctreePointCloudCompression 库，从而减少存储点云数据所需的内存大小。