FOG-Zip：用于八叉树编码LiDAR数据的比特流压缩
摘要
光探测与测距（LiDAR）传感器在实现自主车辆的精准可靠环境感知方面发挥着关键作用。然而，处理它们产生的大量数据却带来了显著挑战。随着基于几何的点云压缩（G-PCC）等标准的出现，八叉树已被用作压缩3-D LiDAR数据的关键数据结构。尽管八叉树具有优势，但它们往往导致高内存占用和计算开销，特别是在处理高分辨率数据集时，限制了它们在具备实时需求的系统中的应用。本信件提出了FOG-zip：一种为资源受限的嵌入式系统设计的硬件加速八叉树压缩方法。实验结果表明，FOG-zip相较于相同未压缩的八叉树比特流，可实现高达27.8%的数据量减小，并能在传感器帧率限制内处理每一帧。
作者
Ricardo Roriz ALGORITMI 研究中心/LASI，葡萄牙米尼奥大学，Guimarães ORCID: 0000-0002-8543-550X
Jorge Cabral ALGORITMI 研究中心/LASI，葡萄牙米尼奥大学，Guimarães ORCID: 0000-0001-9954-9746
Sandro Pinto ALGORITMI 研究中心/LASI，葡萄牙米尼奥大学，Guimarães ORCID: 0000-0003-4580-7484
Tiago Gomes ALGORITMI 研究中心/LASI，葡萄牙米尼奥大学，Guimarães ORCID: 0000-0002-4071-9015
出版信息
期刊： IEEE Sensors Letters 年份： 2025 卷号： 9 期号： 8 页码： 1-4 DOI： 10.1109/LSENS.2025.3588338 文章编号： 11078905 ISSN： Electronic ISSN: 2475-1472
指标
总下载量： 41
关键词
IEEE 关键词: Octrees, Codes, Binary sequences, Symbols, Encoding, Three-dimensional displays, Laser radar, Point cloud compression, Field programmable gate arrays, Frequency conversion
Index Terms: 激光探测与测距, 点云, 光检测, 计算开销, 高计算开销, 三维空间, 峰值信噪比, 频率表, 码字, 二叉树, 点云数据, 硬件资源, 压缩方法, 峰值信噪比值, 压缩算法, 时间压缩, 动态树, 编码树, 无损压缩, 压缩层, 原始点云, 熵编码, 码分配, 点云重建, 频率分析, 查找表, 数据传输
Author Keywords: 传感器应用, 3-D 激光探测与测距 (LiDAR), 压缩, 可编程门阵列 (FPGA), 八叉树
未定义
SECTION I. 引言
自动驾驶正在重塑汽车行业，推动对能够提供准确高效环境感知的先进技术的需求。随着激光探测与测距（LiDAR）传感器成为生成高分辨率三维地图的基石 1，这些地图对于障碍物检测和路径规划等任务至关重要，如何高效管理这些数据的挑战日益重要。
一种有前景的方法是使用八叉树 2，这是一种将三维空间划分为更小立方体或区域的树状数据结构。这种结构简化了大型数据集的存储、访问和处理，同时还能有效地对点云进行下采样。对于需要存储或传输数据的应用，八叉树相对于原始点云提供了良好的压缩比（CRs）。通过对八叉树生成的比特流应用压缩技术，进一步提升这种减小。
基于几何的点云压缩（G-PCC）3标准使用八叉树作为核心数据结构，以高效编码空间信息，并对输出比特流应用算术编码，以实现更高的CRs. 同样，点云库（PCL）4，这是一款广泛使用的点云处理库，提供利用八叉树实现的压缩方法，以消除3-D data中的空间和时间冗余. 然而，尽管它们在以最小或无数据损失实现高CRs方面效率高，从激光雷达（LiDAR）传感器生成八叉树仍可能导致高内存占用和计算开销，尤其在处理大型数据集时.
由于大多数传感器的工作频率至少为10 Hz，必须确保点云采集、八叉树生成、压缩和数据传输在100 ms内完成，以匹配帧生成速率并避免帧丢失。本文提出了 FOG-zip，一种针对由快速八叉树生成器（FOG）5 八叉树实现生成的八叉树编码 LiDAR 数据专门定制的无损比特流压缩方法。FOG-zip 使用了一种专门改进并完全优化以实现高效部署在现场可编程门阵列（FPGA）上的哈夫曼编码算法。实验结果表明，FOG-zip 在 Velodyne HDL-64 上可实现 55.8 的压缩率（CR），同时保持帧压缩时间低至 38.3 ms，低于传感器帧率的 2.6 倍。
第 II 节：八叉树表示与比特流压缩
A. 八叉树表示
八叉树的生成6，如图1所示，涉及创建一个分层数据结构，该结构递归地将三维空间划分为八个更小的立方体区域，称为八分体。该过程持续进行，直至达到预设条件，例如最大深度或最小尺寸（分辨率）。得到的八分体，亦称体素（体积像素），代表八叉树中最小的区域。由于八叉树仅为占用或相关区域分配节点，因而在表示稀疏三维数据时尤其高效，减少了存储最终输出比特流所需的内存。比特流通常通过按特定顺序遍历树并使用算法（例如深度优先搜索）记录每个节点的占用码来创建。此遍历产生的序列化输出编码了所有点的空间分布。
图1. 八叉树的数据结构.
B. 比特流压缩
虽然比特流已经为原始三维空间提供了紧凑的表示，但进一步的技术仍可进一步降低其大小。例如，Kammerl 等人7提出了一种压缩方法，该方法使用排他或（XOR）运算计算连续八叉树帧之间的差异，然后进行整数算术范围编码。类似地，G-PCC 8采用基于上下文的熵编码技术，根据数据的当前上下文自适应地调整其预测。Schnabel 等人9引入了专为点采样几何设计的预测技术，利用局部表面近似实现高压缩率。最近，出现了基于学习的技术以提升压缩效率 10、11、12。例如，Huang 等人13开发了一种条件熵模型，学习八叉树结构并预测节点占用，从而生成优化的比特流。虽然减少八叉树的冗余可以提高压缩率，但其计算复杂度往往限制了其在实时应用或资源受限平台上的使用。
鉴于当前最先进解决方案的复杂性，可探讨传统压缩技术来压缩八叉树比特流。运行长度编码（RLE）通过将相同元素的序列替换为单个值及其计数来进行压缩，使其对包含长重复值序列的数据集非常有效。诸如 LZ77 和 LZ4 等算法将重复模式替换为对先前出现的引用。虽然 LZ77 旨在最大化压缩率，但 LZ4 优先考虑速度，使其非常适合实时应用。Huffman 编码 14 根据符号的频率为其分配可变长度编码。通过为频繁符号分配更短的编码，为低概率符号分配更长的编码，Huffman 编码生成无损但高度紧凑的比特流，针对数据特性进行优化。
第三节. FOG-Zip 算法
FOG-zip 是一种旨在高效压缩由 FOG 15 生成的比特流的压缩算法，这是一种优化 LiDAR 八叉树结构及其对应比特流创建的解决方案。FOG 采用多树架构以并行处理 3-D 空间的多个区域，利用 FPGA 技术实现低延迟性能。FOG-zip 为 FOG 算法增加了一个轻量级压缩层，旨在进一步降低二进制比特流的大小，同时保持算法的原始效率。
A. 基于软件的比特流压缩
为识别在八叉树生成的数据上表现最佳的压缩算法，使用FOG生成的八叉树比特流评估了RLE、LZ4、LZ77和哈夫曼编码。这些算法因其在比特流压缩中的广泛应用和简单性而被选为与FOG算法一起实现于FPGA的合适候选者。评估使用了来自不同Velodyne传感器、在不同环境下收集的LiDAR数据集：VLP-32数据集对应于稀疏的越野场景，而VLP-16和HDL-64数据集则代表了具有高度空间变异性的复杂城市场景。鉴于八叉树编码的有损特性，环境的空间同质性显著影响八叉树的复杂度，进而影响压缩比（CR）。更均匀的场景，例如VLP-32数据集，产生更简单的八叉树结构，具有更高的占据冗余，降低熵并提高CR。此外，八叉树参数（如最大深度）通过控制点云表示中保留的细节级别来影响CR。VLP-32数据集是在越野环境下收集的。压缩后尺寸（KB）和CR与原始点云数据尺寸进行测量并比较。如表1所示，哈夫曼编码始终实现了最小的压缩尺寸，并明显优于LZ4、LZ77和RLE，确立了其为FOG-zip的首选方法。
表 1
B. 基于硬件的压缩
压缩层采用基于霍夫曼编码算法的方案。如图 2 所示，该过程分为三个步骤：(1) 频率分析，(2) 码本创建与码分配，以及 (3) 编码。
图 2. FOG-zip 压缩算法的处理流程.
1) 频率分析: 在此步骤中，每个唯一符号在比特流中的频率被记录在频率表中。传统的基于霍夫曼的方法通过读取整个比特流来计算这些频率，这可能计算量大；或者使用基于先前数据分析的预设表。在 FOG-zip 中，八叉树比特流的频率分析以及 8 位符号频率表的创建与八叉树生成过程并行进行。
2) 码本创建与码分配: 在霍夫曼编码中，生成前缀自由码以确保没有码是另一码的前缀。通常，这些码是通过基于符号频率构造二叉树动态创建的。频率较高的符号位置更靠近根，导致码更短，而频率较低的符号则放置在树的更深层，导致码更长。然而，在硬件中部署动态二叉树可能既复杂又资源密集。为简化此过程并提升执行性能，FOG-zip 用一个包含预先设定前缀自由码的 Code Mapping Table 替代动态霍夫曼二叉树，并根据频率将码分配给每个符号。这种方法消除了动态树构造的需求，形成一个静态结构，高效编码八叉树比特流中的所有符号。
Code Mapping Table 被组织成多个层级，每个层级都有唯一的 Tier ID。 在每个层级内，FOG-zip 为对应符号分配固定数量的比特位。例如，在 Tier 0（处理前四个符号）中，生成的码由 Tier ID（0）加上两个额外比特位组成，以表示四个最常见的符号。 一旦 Frequency Table 与 Code Mapping Table 确定，Codebook 就会被创建，每个八位符号被分配唯一的码字。图 2 展示了 FOG-zip 算法的处理流程。在示例中，符号 “00000100” 在比特流中出现 1643 次，而符号 “11010110” 仅出现 50 次。使用 Code Mapping Table，符号 “00000100” 被映射为码字 “000”，而符号 “11010110” 被映射为码字 “10 000”。
3) 编码: 由于 Code Mapping Table 是静态的并且包含固定数量的符号（最多 256 个），编码后比特流的头部仅包含按频率排序的原始符号。利用这一点，原始比特流可以通过将编码数据中的每个码字替换为解码器中 Code Mapping Table 所对应的符号来恢复，从而确保符号与码的映射被准确地反转。
第四节. 评估
FOG-zip 在 Xilinx 的 ZCU104 Evaluation Kit 上实现并评估，该评估套件配备了 Zynq UltraScale+ MPSoC。该 MPSoC 包含四核 Arm Cortex‑A53 处理器、504K 逻辑单元的 FPGA、1728 个 DSP 切片以及 2 GB DDR4 内存。评估使用与表 1 所示预备结果相同的数据集，包括执行性能、压缩比 (CR)、峰值信噪比 (PSNR) 和 FPGA 资源占用。FOG-zip 与 FOG 生成的未压缩八叉树以及来自 PCL 的 OctreePointCloudCompression 库生成的压缩八叉树进行了比较，后者提供了与本工作一致的结构和功能特性。为保证一致性，所有方法均在同一平台上进行评估。PCL 使用的配置在表 2 中进行了总结，而 FOG 八叉树的 numberOfNodes 设为 250 000，BBCoordinates 定义为以传感器为中心、边长 200 m 的立方体包围盒以包含所有点，maxDepth 设为 12，对应 5 cm 的分辨率。这些参数的选择旨在在八叉树创建和原始点云重建方面产生相似结果，详见 16。
表 2
表 3
表 4
A. 性能评估与硬件资源
Compression Time: FOG-zip 在所有评估数据集上相较于 PCL 和 FOG 显著提升压缩时间。对于 VLP-16 数据集，FOG-zip 每帧处理时间为 12.6 毫秒，较 PCL 减少 88.7%，较 FOG 减少 7.9%。对于 VLP-32 数据集，压缩时间为 16.1 毫秒，相较 PCL 提升 85.7%，相较 FOG 提升 5.3%。同样，在 HDL-64 数据集上，FOG-zip 每帧处理时间为 38.3 毫秒，较 PCL 提升 89.1%，较 FOG 提升 3.0%。
CR and PSNR: FOG-zip 在 VLP-16、VLP-32 和 HDL-64 数据集上分别实现了 31.5、64.3 和 55.8 的压缩率（CR），相较于 PCL 分别降低了 15.8%、9.2% 和 7.6%。关于 PSNR，PSNR 用来量化原始点云与重建点云之间的相似度，FOG 与 FOG-zip 的 PSNR 相同，因为失真是在八叉树生成步骤中引入的。在 VLP-16 数据集上，它实现了 57.7 dB 的 PSNR，相比 PCL 降低了 18.6%。在 VLP-32 和 HDL-64 数据集上，PSNR 分别为 56.9 和 60.0 dB，对应的降幅分别为 21.3% 和 14.7%，其中 HDL-64 的质量损失最小。
Hardware Resources: FOG-zip 的压缩层会略微增加硬件资源的使用，尤其是在查找表（LUTs）、触发器（FFs）和多路复用器（MUXes）方面。FOG-zip 需要 114029 个 LUTs，利用率达到总可用资源的 49.49%，比 FOG 多 7.06%。同样，FFs 的利用率从 FOG 的 33 926（占可用资源的 7.36%）升至 FOG-zip 的 10.89%，增加了 3.53%。MUX 的利用率也呈现类似趋势，FOG-zip 需要 36.03% 的可用资源，相比 FOG 使用的 27.97% 增加了 8.06%。
B. 讨论
FOG-zip 的评估突出了其相较于 PCL 和 FOG 的优势与权衡。在压缩时间方面，FOG-zip 在所有数据集上均显著优于两者。这一改进主要来自 FOG-zip 与 FOG 的并行执行，避免了额外的处理开销。此外，FOG-zip 生成的编码比特流更小，从而降低了处理和传输所需时间。在 PSNR 方面，正如在 17 中讨论的那样，PCL 生成的八叉树保留了更多关于原始点云的细节信息。然而，FOG-zip 的 PSNR 值超过 55 dB，表明其为高质量的有损压缩，如图 3 所示。虽然无损方法通常超过 70 dB，FOG-zip 被归类为有损，原因不是其本质上无损的压缩层，而是 FOG 中有损八叉树生成过程。同样，在 CR 方面，FOG-zip 的数值显著高于 FOG，但略低于 PCL（当应用压缩时）。这是因为 FOG 的输出不是压缩比特流，而 PCL 使用更复杂的熵编码，从而降低了整体编码大小。FOG-zip 遵循霍夫曼编码的原则，然而；* 它通过使用确定性前缀无关的 Code Mapping Table，消除了构建临时霍夫曼树的必要。这可以实现更快的码分配，并确保一致的编码和解码过程。然而，这种方法可能导致压缩次优，因为它可能在编码比特流中添加不必要的额外位。与原始霍夫曼码符号相比，FOG 符号码在包含大量唯一或低频符号的数据集中也可能迅速增长。尽管如此，FOG-zip 可用于需要快速编码和解码的应用，并且由于其更简单的部署，可适配嵌入式平台。
图 3. 使用 FOG-zip 的 12 层深度八叉树对原始和解压后的点云进行比较。(a) 原始点云。(b) 重建点云.
第五节 结论
本信介绍了 FOG-zip，这是一种旨在将无损压缩集成到 LiDAR 数据的八叉树生成比特流中的算法，并在 FOG 框架内进行了测试。该算法采用了一种简化的基于霍夫曼编码的方法，依赖于静态前缀无歧义的 Code Mapping Table，而非创建动态霍夫曼树。这种更简单的方法针对 FPGA 实现进行了优化，降低了压缩时间并实现了可接受的编码比特流尺寸。评估结果突出了 FOG-Zip 的权衡与优势，证明其适用于实时应用。未来工作将聚焦于提升压缩层，包括探索额外层以提升整体压缩比 (CR)。此外，可在自动驾驶应用中评估 FOG-zip 的性能，例如物体检测，以确定其略低的 PSNR 是否会影响真实场景中的表现。