一种基于删除量化矩阵中0元素的点云属性压缩方法

摘要

本发明公布了一种基于删除量化矩阵中0元素的点云属性压缩方法，针对点云属性压缩过程中的量化矩阵，在编码端采用最优的遍历顺序使0元素在生成的数据流中集中分布在末端，将这些0删除后进行熵编码，降低数据流的数据量，减小编码后生成的码流，在解码端结合点云几何信息复原被删除的0元素，保证本方法不引入额外的误差；包括：编码端优化对量化矩阵的遍历顺序；删除数据流末端的0元素；解码端参考几何信息复原量化矩阵；点云属性压缩编码过程和解码过程。本发明在点云属性压缩的编码端对量化矩阵采用7种遍历顺序，使0元素在数据流中的分布更集中在末端；删除数据流末端的0元素，去除冗余信息，减小需要进行熵编码的数据量；在解码端结合点云几何信息补齐被删除的0元素，按照遍历顺序复原量化矩阵，在不引入新误差的前提下提高压缩性能。

说明书

技术领域

本发明属于点云数据处理技术领域，涉及点云数据压缩方法，尤其涉及一种基于删除量化矩阵中0元素的点云属性压缩方法。

背景技术

三维点云是现实世界数字化的重要表现形式。随着三维扫描设备(激光、雷达等)的快速发展，点云的精度、分辨率更高。高精度点云广泛应用于城市数字化地图的构建，在如智慧城市、无人驾驶、文物保护等众多热门研究中起技术支撑作用。点云是三维扫描设备对物体表面采样所获取的，一帧点云的点数一般是百万级别，其中每个点包含几何信息和颜色、纹理等属性信息，数据量十分庞大。三维点云庞大的数据量给数据存储、传输等带来巨大挑战，所以点云压缩十分必要。

点云压缩主要分为几何压缩和属性压缩，现有的点云属性压缩框架主要包括以下几种：

一、基于八叉树分解和DCT的方法：该方法先用八叉树对点云进行空间分解得到编码块，然后对树进行深度优先遍历，将遍历的结点颜色值按照蛇形的顺序写入二维的JPEG表，再利用现有的JPEG编码器对获得的点云颜色表进行编码，其中JPEG编码器使用的是DCT。该方法利用现有的编码器，计算复杂度低，但并未充分利用点与点之间的空间相关性，在压缩性能上有待提高；

二、基于八叉树分解和图变换的方法：该方法先用八叉树对点云进行空间分解，划分到特定层次得到变换块；在每个变换块内形成图，将沿着任意坐标轴的距离不超过1的两点用一条边连接起来，边的权重与欧氏距离成反比；再对图中结点的属性信息进行图变换。该方法的压缩性能佳；但运算复杂度较高，其构图方式可能会带来子图问题，影响图变换的效率，仍有改善的空间；

三、基于KD树分解和图变换的方法：该方法先用KD树对点云进行空间分解，划分到一定深度得到变换块，其中每个变换块内所包含的点数大致相同：在变换块内，每两点用一条边连接起来，边的权重与欧氏距离有关，设定的边欧式距离阈值决定图的稀疏度；然后再对图内点的属性信息进行图变换。该方法彻底解决了子图问题，同时在压缩性能方面较前两种方法都有较大的提升，但运算复杂度较高，性能仍待改善。

发明内容

为了进一步提升上述技术的性能，在考虑计算复杂度的条件下，本发明在点云属性压缩的编码端对量化矩阵采用7种遍历顺序，使0元素在数据流中的分布更集中在末端；删除数据流末端的0元素，减小需要进行熵编码的数据量；在解码端结合点云几何信息补齐被删除的0元素，按照遍历顺序复原量化矩阵，在不引入新误差的前提下提高压缩性能。

本发明提供的技术方案是：

一种基于删除量化矩阵中0元素的点云属性压缩方法，针对点云属性压缩过程中的量化矩阵，在编码端采用最优的遍历顺序使0元素在生成的数据流中集中分布在末端，并将这些0删除后进行熵编码，降低数据流的数据量，减小编码后生成的码流；在解码端结合点云几何信息复原被删除的0元素，保证本方法不引入额外的误差。包括如下步骤：

1)点云属性压缩的编码过程

待压缩的点云数据首先会根据几何信息进行KD树划分，KD树划分的最后一层所得到的块即为点云的编码块，每一个编码块内的属性信息经过帧内预测、残差变换、量化之后会得到一个量化矩阵。

2)编码端优化对量化矩阵的遍历顺序：

对于每一个量化矩阵，采用7种不同的遍历顺序，将二维的矩阵转化为一维的数据流，比较0元素在数据流末端连续出现的个数，选择0元素在末端连续出现个数最多的数据流为最优数据流，同时记录对应的遍历模式。

3)删除数据流末尾的0元素：

得到了最优数据流之后，将数据流末端所有连续出现的0都删除，得到裁剪后的数据流，对所有编码块进行相同操作之后，统一进行熵编码，得到点云属性压缩的码流。

4)解码端参考几何信息复原量化矩阵：

在解码对码流进行熵解码得到裁剪后的数据流，结合点云的几何信息，求出被删除的0元素的个数并补齐得到原始的数据流，依照遍历顺序将一维的数据流复原为二维的量化矩阵。

5)点云属性压缩的解码过程：

按顺序对复原出的量化矩阵进行反量化、逆变换、预测补偿，解码出点云的属性信息。

上述步骤1)中点KD树划分方法为二元划分方法；设待处理的点云共有N个点，KD树设定的划分深度为d，经过对点云d次划分后，得到2^d个编码块，每个块内点的个数接近，有n个或n+1个，n的计算方法如式1。对所有的编码块按照广度优先遍历的顺序进行编号该编号将作为编码块后期处理的顺序。

上述步骤1)中得到的量化矩阵大小与编码块中点的个数有关，即n×3或(n+1)×3。

上述步骤2)中对于每一个量化矩阵，采用7种不同的遍历顺序，分别为：YUV逐行扫描、YUV逐列扫描、YVU逐列扫描、UYV逐列扫描、UVY逐列扫描、VYU逐列扫描、VUY逐列扫描。扫描后n×3的二维矩阵被转化为长度为3n的一维数据流，选择0元素在末端连续出现个数最多的数据流为最优数据流，同时记录对应的遍历模式m_i。

上述步骤3)中选出的最优数据流长度为3n，假设数据流末端连续出现的0元素个数为l_i，则裁剪后的数据流长度为3n-l_i。

上述步骤4)中熵解码得到裁剪后的数据流，长度为l_c，需要知道被删除的0元素的个数来恢复原始的数据流。在解码端对点云的几何信息进行与编码端相同的KD树划分，得到2^d个编码块，每个块内有n个(或n+1个)点，再对所有的编码块按照广度优先的遍历顺序进行编号，得到的结果与编码端一一对应，则根据式2可以求出被删除的0元素的个数l₀。补齐0元素之后的数据流长度为3n，根据保存的遍历模式m_i将数据流转化为n×3的量化矩阵。

l₀＝3_n-l_c>

上述步骤5)中具体细节如下：

(5-1)经过步骤4)得到了量化矩阵，对量化矩阵进行反量化、逆变换、预测补偿，解码出点云的属性信息；

(5-2)基于删除量化矩阵中0元素的点云属性压缩方法的码流主要由压缩头信息和编码块信息两大部分组成。头信息主要包括量化步长、预测模式信息、量化矩阵的遍历模式信息等；编码块信息以编码块为单位，按照编码块的顺序排列，每个块内主要包括编码块的颜色残差信息。

(5-3)点云属性压缩的性能由码率和峰值信噪比PSNR(Peak Signal to NoiseRatio)来衡量，其中码率的单位是bpp(bits per point)，PSNR的单位是分贝dB；码率越小，PSNR越大，点云属性压缩性能越好。

与现有技术相比，本发明的有益效果是：

本发明提供一种基于删除量化矩阵中0元素的点云属性压缩方法，具有以下技术优势：

(一)针对点云属性压缩过程中的量化矩阵，在编码端采用最优的遍历顺序使0元素在生成的数据流中集中分布在末端，将这些0删除后进行熵编码，降低数据流的数据量，减小编码后生成的码流。

(二)在解码端结合点云几何信息补齐被删除的0元素，按照遍历顺序复原量化矩阵，在不引入新误差的前提下提高压缩性能。

附图说明

图1a是本发明提供方法的编码端的流程框图；

图1b是本发明提供方法的解码端的流程框图；

图2是编码端对量化矩阵采用的7种遍历顺序的示例图；

图3是点云属性信息压缩后的码流结构示例图；

图4a是测试Longdress-vox10-1300.ply本发明方法与现有传统方法的压缩性能对比图；

图4b是测试Queen-frame-0200.ply本发明方法与现有传统方法的压缩性能对比图；

图4c是测试Soldier-vox10-0690.ply本发明方法与现有传统方法的压缩性能对比图。

具体实施方式

下面结合附图，通过实施例进一步描述本发明，但不以任何方式限制本发明的范围。

本发明的一种基于删除量化矩阵中0元素的点云属性压缩方法，针对点云属性压缩过程中的量化矩阵，在编码端采用最优的遍历顺序使0元素在生成的数据流中集中分布在末端，将这些0删除后进行熵编码，降低数据流的数据量，减小编码后生成的码流，在解码端结合点云几何信息复原被删除的0元素，保证本方法不引入额外的误差。

图1a是本发明方法的编码端的流程框图。第一步在编码端输入待压缩点云数据的几何信息和属性信息；第二步根据点云的几何信息进行KD树划分，得到点的个数接近的编码块，并按顺序编号；第三步对应发明内容的步骤(1)，每个编码块内的属性信息经过帧内预测、变换、量化，得到对应的量化矩阵；第四步对应发明内容的步骤(2)，采用多种遍历顺序将量化矩阵转化为数据流，选择0元素在末端分布最集中的最优数据流；第五步对应发明内容的步骤(3)，删除上一步得到的数据流末端的0元素；第六步对所有编码块的数据流统一进行熵编码；最后得到点云属性信息的码流。

图1b是本发明方法的解码端的流程框图。第一步在解码端输入需要待处理的点云属性信息的码流；第二步对码流进行熵编码，得到所有编码块的数据流；第三步对应发明内容的步骤(4)，参照几何信息，按编码块的顺序补齐数据流末端的0元素并将其复原为量化矩阵；第四步对应发明内容的步骤(5)，对量化均值进行反量化、逆变换、预测补偿，得到每个块对应的属性信息；最后输出解码的点云属性信息。

图2是编码端对量化矩阵采用的7种遍历顺序的示例图，(a)到(g)分别表示对n×3的量化矩阵进行YUV逐行扫描、YUV逐列扫描、YVU逐列扫描、UYV逐列扫描、UVY逐列扫描、VYU逐列扫描、VUY逐列扫描，每个点对应量化矩阵中的每个元素，其中白色的点为遍历的起始点。

图3是点云属性信息压缩后的码流结构示例图。码流主要由头信息和各个编码块的编码块信息组成。头信息主要包括量化步长、预测模式、量化矩阵的遍历模式等信息；编码块信息以编码块为单位，按照编码块的遍历顺序排列，每个编码块信息内是该编码块的颜色残差。

图4a、b和c是测试Longdress-vox10-1300.ply、Queen-frame-0200.ply和Soldier-vox10-0690.ply的本发明方法与现有传统方法的压缩性能对比图。横轴是码率，单位是bpp(bits per point)，纵轴是亮度Y的峰值信噪比PSNR(Peak Signal to NoiseRatio)，单位是分贝db，码率越小，峰值信噪比越大，点云属性压缩性能越好；

以下针对MPEG点云压缩工作组中的官方点云数据集Longdress-vox10-1300.ply，Queen_frame_0200.ply，Soldier-vox10-0690.ply采用本发明方法进行点云属性压缩，以Longdress-vox10-1300.ply为例，如图1所示，具体实施步骤为：

(1)点云属性压缩的编码过程：

点云Longdress-vox10-1300.ply共有857966个点，KD树划分深度设为13，经过划分后共有8192个编码块，块内点的数量为104或105，以第1个编码块为例，有104个点，块内的属性信息经过帧内预测、残差变换、量化(量化步长为4)之后得到一个104×3的量化矩阵Q₁。

(2)编码端优化对量化矩阵的遍历顺序：

对得到的量化矩阵Q₁，采用7种不同的遍历顺序，比较发现YUV逐列扫描得到的数据流中0元素在末端连续出现个数最多，因此选择该模式将二维的量化矩阵转化为一维的数据流S₁，长度为312，同时记录第1个块对应的遍历模式m₁＝1。

(3)删除数据流末尾的0元素：

对得到的数据流S₁，删除其末端连续出现的266个0元素，得到新的数据流长度为46。8192个编码块都进行相同的操作之后，数据流分别写入各自的编码块信息，再将量化步长、遍历模式和预测模式等信息写入压缩头信息中，统一进行熵编码，输出的最终码流文件的结构如图3所示。

(4)解码端参考几何信息复原量化矩阵：

解码端输入码流文件进行熵解码，获取头信息和8192个块的编码块信息，以第1个块为例，得到裁剪后的数据流长度为46，需要知道被删除的0元素的个数来恢复原始的数据流。在解码端对点云的几何信息进行与编码端相同的KD树划分，得到8192个编码块，第1个块内有104个点，则可以求出被删除的0元素有266个。补齐0元素之后的数据流长度为312，根据头信息中第1个块的遍历模式m₁＝1，采用YUV逐列扫描的遍历顺序，将数据流转化为104×3的量化矩阵。，

(5)点云属性压缩的解码过程：

对复原的量化矩阵结合量化步长、预测模式等信息，依次进行反量化、逆变换、预测补偿，求出点云的属性信息。点云属性压缩的性能由码率和峰值信噪比PSNR(PeakSignal to Noise Ratio)来衡量，其中码率的单位是bpp(bits per point)，PSNR的单位是分贝dB。

为了验证本发明的一种基于删除量化矩阵中0元素的点云属性压缩方法的效果，我们使用上述3个数据集Longdress-vox10-1300.ply，Queen-frame-0200.ply，Soldier-vox10-0690.ply进行实验，在压缩性能上与现有的方法对比结果如图4所示。

从图4可以看出，在使用相同的基于帧内预测、图变换、量化、熵编码的点云属性压缩编码器情况下，引入本发明的删除量化矩阵中0元素的方法后，在测试的三类典型的点云数据上，产生了稳定且显著的性能增益。本方法在点云属性压缩的编码端对量化矩阵采用最优遍历顺序，使0元素集中分布在数据流末端并删除，减少冗余的信息；在解码端结合点云几何信息补齐被删除的0元素，按照遍历顺序复原量化矩阵，保证不引入新的误差。实验结果表明在各个码率点下，点云属性压缩的性能均得到改善，本发明产生的增益稳定，优点突出。

需要注意的是，公布实施例的目的在于帮助进一步理解本发明，但是本领域的技术人员可以理解：在不脱离本发明及所附权利要求的精神和范围内，各种替换和修改都是可能的。因此，本发明不应局限于实施例所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。