唐 堂，徐光辉，刘铭哲
（中国人民解放军陆军工程大学，江苏 南京 210001）
0 引言
点云是三维空间中一组离散坐标点的集合，其中每个点除包含自身所在空间位置的三维坐标信息外，通常还包含颜色、激光反射强度等属性信息。点云数据的获取方式可分为直接和间接两种[1]，直接方式通常采用距离传感器如激光雷达、深度相机等，通过主动发射电磁波并接收回波，获取相应反射点的坐标，从而获得场景内物体的几何信息，结合图像采集设备可以获取对应的颜色等属性信息；间接方式则是通过计算或者采样从其他形式的数据中获取点云，比如双目相机结合运动信息进行三维重建等。其中激光雷达因为具有采集迅速、点云密集、精确度高的特点[2]，成为目前最常用的点云采集设备。
点云数据信息量丰富，三维场景表现能力出色，在场景建模、虚拟现实、环境测绘、自动驾驶等领域应用广泛，前景广阔。但是，作为一种高维度的信息，密集的点云不可避免地存在着数据量庞大的问题。以Velodyne HDL-64S2 型激光雷达为例，当其以10Hz 的频率采集数据时，连续运行一小时将产生超过100GB 的数据[3]。虽然快速发展的通信及存储技术在一定程度上缓解了点云数据量庞大带来的挑战，但是在一些分布式、低成本、实时性要求高的场景下，庞大的数据量仍然是制约点云应用和发展的瓶颈。因此，研究如何压缩点云数据，对其在更多场景下的应用具有重要意义。
点云压缩算法跟点云获取方式及其对应场景密切相关。针对激光雷达点云，运动图像专家组（Moving Pictures Experts Group，MPEG）最先公布的点云压缩方案L-PCC[4]中使用的是基于八叉树的几何编码。通过八叉树将目标区域迭代划分为精细立方体，以树的形式遍历访问目标立方体所在空间，从而实现空间编码。而在之后公布的G-PCC 方案中[5]，引入了一种一维遍历的预测几何编码方法，其基本思想是利用点云中点与点基于几何距离的领域关系，构建一种预测树，树中每个节点的位置信息都可以从其父节点或其祖父节点推断出来，编码预测节点和其相关联的实际点的残差，从而降低点云几何信息的冗余。Tu 等人结合激光雷达旋转扫描获取点云的特点，将激光雷达原始数据转化为距离图，对距离图序列使用JPEG 进行压缩，从而间接实现了点云的压缩。此外，结合场景语义信息来进行点云数据压缩也取得了不错的效果[6]。不同于以上算法，Feng 等人[7]利用了单帧点云中含有大量近似平面以及相邻点云帧中存在大量重复场景的特点，通过平面拟合的方式实现了点云数据的实时压缩，该方法在算法复杂度、压缩率、场景应用精度上的综合表现更为优异。
本文在Feng 等人的基础上提出了使用预测残差处理未拟合点距离的方案，解决了其在复杂场景平面信息少或是平面拟合精度要求高导致的非拟合点过多，占据大量编码空间的问题，能够在同等误差精度条件下，取得比原算法更好的压缩效果。
1 编解码框架介绍
本文设计的基于平面拟合及残差预测的编解码框架如图1 所示，它由编码端和解码端两部分构成。编码端首先将三维点云降维转换为二维距离图，转换方法是根据点云中点的坐标位置，计算其相对于原点的旋转角、俯仰角以及直线距离，根据激光雷达角度分辨率对旋转角和俯仰角进行量化，量化值分别作为二维距离图中像素位置的列索引和行索引，直线距离则作为该像素的像素值，如此点云中的每个点便可以投射到二维距离图中的某个像素上。降维转换可以将无序的点云转换为有序的二维图，同时可以最大限度地保留点云中点的相关性，为后续的平面拟合及残差预测奠定基础。此过程中生成的二维占位图与距离图具有同等尺寸，像素值用单个比特1 或0 编码，指示距离图对应的像素上是否存在点云投射点，用于解码过程。在二维图的基础上，以固定数量的像素拼接的像素块为单位，进行平面拟合，由可以拟合的像素提取得到相应的平面参数，不能拟合的像素则进行预测编码，得到相应的预测值、残差值和孤立值。拟合的过程中产生相关的索引值用来区分可拟合像素块、可预测像素块及孤立像素块。最后对平面参数、索引、预测、残差、孤立值及占位图进行熵编码，产生可以保存或传输的二进制码流。解码端解码提取相应数据，根据相关参数及索引对空白距离图进行像素值填充，最后进行升维转换，恢复得到原始点云数据。编解码过程中数据形式转换如图2 所示。
图1 平面拟合及残差预测编解码框架
图2 编解码过程数据形式转换
2 平面拟合及残差预测
2.1 平面拟合
平面拟合的基本思想是使用空间平面去拟合空间中孤立的点，当空间中某一区域的点共面时，就可以用该拟合平面去间接表示所有位于该平面上的点，从而实现减少保存的数据量的目的。常用的车载激光雷达采集数据示例如图3 所示：位于移动载具上的激光雷达发出短脉冲激光束，当激光束照射到目标物体上时，会被部分反射回来，激光雷达接收到反射回来的激光脉冲信号，并测量信号的时间差以计算距离。利用多次测量可以获取目标物体在三维空间中的坐标。实际场景中存在大量共面的点，比如平整的墙壁、汽车部分表面以及平坦的路面，即使有些宏观上看起来并不规则的物体，也可以用一系列微小的平面去近似拼接表示。基于这一特征，激光雷达采集到的点云中实际存在大量共面的点，因此可以使用平面拟合来降低点云的信息 冗余。
图3 激光雷达采集数据示例及点云局部放大
使用空间平面去拟合空间中共面的点，其实就是根据给定的点确定一组平面参数，使得所有目标点距离该平面的距离都在允许的误差范围内。为此，可以使用最小二乘法得到相应的平面参数。其基本思想是通过最小化误差的平方和来寻找数据的最佳匹配函数。假设有n个待拟合的三维坐标点(xi,yi,zi)，i=1,2,3,…,n。当平面不过原点时，平面方程可以表示为：
对于平面拟合来说，误差最小就是将待拟合的点带入式（1）后，等式右边取值尽可能接近0，因此可以得到以下目标函数：
为使式（2）最小，需要对a,b,c分别求偏导数，使得：
具体编码是在降维转换后形成的二维距离图的基础上进行的。将二维距离图按照固定个数的像素点进行分块，因为降维操作的过程保留了相邻位置点的领域关系，因此同一块内的像素点所对应的点云中点的分布也具有领域关系。对块内的像素点使用上述方法进行平面拟合，得到一个拟合平面，之后判断该块内的所有像素点到拟合平面的欧式距离是否小于某一设定阈值。当所有点的误差都在阈值范围内时，即认为该像素块可以被平面拟合，平面的参数随即确定，通过保存该拟合平面的参数来替代保存该像素块内的像素点，因为只需要保存3 个参数，而像素块内的像素点的数量是超过3 的，所以能够实现减少数据量的目的。当像素块内存在点到拟合平面的距离超过阈值时，则说明无法拟合出满足要求的平面，认为该像素块内的像素不在同一平面内，需要进行残差预测或者独立编码。
在解码端，当解码的像素块被平面拟合编码时，根据激光雷达采集点云的原理，只需要知道激光的入射角度、拟合平面参数以及该位置是否存在投射点，即可恢复出该点的空间坐标位置。激光的入射角度已经被编码在二维距离图的横纵坐标索引里，对应的像素点是否被点云投射可以根据二维占位图获取。
2.2 残差预测
平面拟合主要利用的是点云中存在共面的点这一特点，通过平面来替代该面上的一个个孤立的点，从而降低信息冗余。当场景比较简洁、规整时，比如城市道路、桥梁隧道环境下，激光雷达采集到的点云存在大量共面的点，平面拟合压缩效果显著。但是当场景信息复杂时，比如灌木林立的郊区道路环境，点云中不共面的点较多，需要被单独编码，压缩性能降低。图4 展示了激光雷达采集数据的两种不同场景：场景1 是隧道环境，存在较多平面目标物；场景2是郊区道路环境，虽然存在平整的路面，但是道路两边有茂密的树木，几乎无法用平面进行拟合。
图4 激光雷达采集数据场景
对两种场景下采集的激光雷达数据使用相同的参数进行平面拟合压缩处理，表1 统计了两种场景点云压缩相关数据。
表1 两种场景平面拟合压缩数据统计
从表1 可以看出，在相同压缩参数下，不同场景采集到的点云中，不能被平面拟合的点数存在较大差异，并且非拟合点的占比对压缩效果有较大影响。因此，如果能够对非拟合点进行一定的处理，而不是直接保存其距离值，将会提升点云压缩的效果。
对于降维转换后的二维距离图来说，像素点上的距离值实际上是激光雷达到场景地物反射点的距离，同一场景地物的多个反射点到激光雷达的距离应该是相近的，而二维距离图保存了空间中反射点之间的领域关系，因此二维距离图上相近区域的几个像素值即使不能被平面拟合，也应该存在一定的近似关系。对场景2 采集到的激光雷达点云进行降维转换后，对其中不能被平面拟合的像素块进行抽样，共抽样5 次，每次抽取连续的10 个非拟合像素块，统计抽取的像素块内所含的像素值分布情况，如图5 所示。
图5 非平面点连续区域像素值分布统计
从图5 可以看出，非拟合点虽然不能被平面拟合，但是像素值的分布较为集中。残差预测编码正是利用此特点，对非拟合点进行处理，从而减少信息冗余。
残差预测同样是以像素块为单位，对每个像素块内的像素值进行操作。在降维转换、平面拟合编码的基础上，针对不能被平面拟合的像素块，首先判断该像素块内的像素值是否可以被预测编码，即像素值分布是否集中在一个预先设定的较小阈值范围内，如果像素值分布满足条件，则以其中最小的值作为该像素块所有像素的预测值，块内其余像素值与该预测值相减作为残差值保留；如果像素值分布不满足条件，即该块内的像素值差异过大，则无法进行预测编码，需要将其作为孤立像素块，单独进行编码。之后对下一个不能拟合像素块进行预测编码的判断，该像素块的判断需要参考前一个像素块的编码情况，如果前一个像素块是可以被预测编码的，则首先判断当前像素块是否也在前一个像素块预测编码的范围内，如果是，则利用前一个像素块的预测值进行残差预测编码，如果不在前一个像素块的预测范围内，则判断当前像素块是否能够被独立预测编码，如果可以，则重新确定预测值并在此基础上计算残差，如果不行，则作为孤立像素块单独编码。经过预测编码后，所有非平面编码的像素值均可由孤立值、预测值和残差值所确定。
判断是否可以预测编码的阈值对预测编码效果有着显著影响，当阈值设置较大时，可被预测编码的像素块数量就会增多，预测范围广，编码效果好，但是受到编码残差比特数的影响，量化误差会增大，最终会增加点云的信息损失。因此在实际使用中，预测判别阈值通常根据压缩需求和点云失真情况来确定。
为了直观地看到残差预测的处理效果，选取4种不同场景采集到的单帧点云数据，分别使用平面拟合和平面拟合加残差预测进行压缩，统计两种压缩方法中的非拟合点数据量，结果如表2 所示。
表2 残差预测处理前后非拟合点数据量统计
从表2 可以看出，经过残差预测处理后，非拟合点的数据量显著减少，残差预测能够在原平面拟合算法的基础上带来压缩性能的提升。
3 压缩性能分析
3.1 实验环境和评价指标
实验在Windows 10 系统上完成，电脑配置是Intel Core i5-11300H @ 3.10 GHz，16 GB 运行内存。实验采用KITTI 数据集，该数据集包含数百个行驶场景的录制视频序列、激光雷达数据和图像数据，被广泛用于自动驾驶和计算机视觉领域。其中的激光雷达数据主要是通过搭载的Velodyne HDL-64E 传感器采集，该传感器拥有64 个激光发射器和接收器，每秒钟可以生成高达100万个测量点，配合旋转支架，可以在水平平面上捕捉高密度的3D 点云信息。
使用编码每个点所用的比特数（bpp）表示点云压缩程度，其计算公式为：
式中：Size(P)表示点云的数据量，单位为bit；N(P)表示点云中点的总数。例如：原始点云编码每个点的坐标需要使用96 bit 数据，则原始点云的bpp就是96，压缩后的点云bpp则是以压缩包的数据量除以原始点云中点的个数得到，因此bpp越小表示压缩后的数据量越小，压缩程度越大。
因为是有损压缩，所以还需要评估压缩后信息的损失情况。本文使用两种方法对信息损失进行量化评估。第一种方法是对称最近邻均方根误差，该指标是直接比较解压重建后的点云与原始点云的位置差异，通过计算所有点的位置偏移均值来量化压缩导致的点云几何失真[8]。具体的计算方法为：对于原始点云P中的每一个点p，通过最近邻算法在解压重建的点云Q中找到其对应的点q，P相对于Q的误差为：
除了比较原始点云和重建点云之间的几何误差，本文还从点云应用的角度对信息损失进行评估。位姿估计是点云的一种常见应用，它是指从传感器数据中估计物体或相机相对于参考坐标系的位置和方向信息，在计算机视觉、机器人及自动驾驶等领域使用广泛。本文使用激光雷达里程计建图（Lidar Odometry and Mapping，LOAM）算法[9]，基于同一段序列，对经过不同程度压缩解压后的点云进行位姿估计，通过比较位姿估计的误差来衡量压缩算法对点云应用造成的影响。
3.2 实验结果与分析
本次实验与基于平面拟合、八叉树[10]及JPEG[3]的点云压缩方法进行对比。针对直接信息损失比较，使用KITTI 数据集中不同场景共10 帧激光雷达点云作为压缩处理对象。图6 是本文算法与其他3 种算法在不同压缩程度下，几何信息损失的情况。从图中可以看出，随着压缩程度加大，4 种算法都表现出了信息损失增加的情况；在同等误差条件下，本文提出算法的bpp最小，表明压缩性能最好。
图6 不同点云压缩方法失真情况比较
针对位姿估计应用评价，使用KITTI 数据集中一段30 秒内连续采集的激光雷达点云序列作为压缩处理对象。采用不同的压缩算法对该序列进行不同程度的压缩解压后，使用a-loam 算法进行位姿估计，结果如图7 所示。从图中可以看出，在同等位姿估计误差情况下，本文提出的算法能将该段序列点云数据量压缩至最小。
图7 不同压缩算法位姿估计精度比较
4 结语
本文针对激光雷达点云压缩，在平面拟合算法的基础上，对非平面拟合点进行残差预测处理，有效改善了高拟合精度和复杂场景下平面拟合压缩性能下降的情况。从直接信息损失和应用精度两个方面比较了不同压缩率情况下，压缩导致的点云失真情况。结果表明，本文算法较八叉树压缩和基于JPEG 的压缩有较大提升，优于之前的基于平面拟合的压缩算法。
