八叉树结构下动态点云的无损几何编码方法

王哲诚, 万帅,2, 魏磊, 杨付正

(1. 西北工业大学电子信息学院, 710129, 西安; 2. 皇家墨尔本理工大学工程学院, VIC3001, 澳大利亚墨尔本; 3. 西安电子科技大学通信工程学院, 710071, 西安)

由于点云在增强现实和虚拟现实的应用迅速发展,人们对压缩三维点云数据的研究兴趣日益强烈[1]。三维点云是一种由数十万甚至更多不规则的点组成的数据格式。除了点的几何位置信息外,它还包括一些附加属性信息来表示三维物体,比如颜色和反射率[2]。与由规则的二维网格中像素表示的图像和视频相比,由三维空间中不规则点组成的点云更加难以被压缩。作为属性信息压缩的前提,几何信息的压缩也更具挑战性。此外,很多应用更是要求对动态点云的几何信息进行压缩。面对这一挑战,人们提出了很多动态点云的几何信息压缩方法[3-4]。

目前,点云的几何信息压缩通常是基于八叉树结构进行的[5]。八叉树结构能够比较容易地表示三维空间中点的几何位置,而且便于探索点云内部的空间相关性。早期,人们采用相邻帧的八叉树节点信息进行帧间编码,比如基于相邻帧对当前八叉树节点信息进行重排序来构建有效的上下文[6],或者基于当前八叉树节点与相邻帧内八叉树节点之间的距离构建上下文[7]。在八叉树结构下,当前八叉树节点的父节点信息也可以用作上下文。最后,再通过基于上下文的算数编码或者LZW编码实现点云的无损压缩[8]。

2020年,文献 [9]提出了一种基于八叉树结构的动态点云无损几何编码方法P(Full)。它采用当前帧中当前八叉树节点的父节点信息作为帧内参考节点,或者采用上一帧中的节点信息作为帧间参考节点。该方法计算当前节点与各参考节点的最小汉明距离,选择汉明距离最小的参考节点作为上下文,通过基于上下文的算数编码进行无损压缩。相较于点云在八叉树结构下且不进行任何压缩的数据大小,该方法带来了约55%的无损几何编码增益。然而,该方法并没有同时使用帧内和帧间的几何信息作为上下文,而是用基于最小汉明距离的方法选择其一,未能综合利用空间和时间相关性。此外,国际标准化组织运动图像专家组(Moving Picture Expert Group, MPEG)开发了基于几何的点云压缩(geometry-based point cloud compression, G-PCC)[10]。G-PCC以通用点云编解码器为目标,力求涵盖静态和动态物体场景下的稀疏和密集点云的压缩。G-PCC标准于2023年3月正式发布[11],现阶段只涉及帧内编解码。G-PCC主要采用八叉树结构进行几何编码,应用当前八叉树节点的父节点、相邻节点和相邻子节点的几何信息进行上下文建模,进而采用基于上下文自适应的二进制算术编码(context-based adaptive binary arithmetic coding, CABAC)[12-17]实现点云无损几何编码。因为缺少对帧间时间相关性的利用,G-PCC在编码动态点云时压缩性能并不突出。

与上述文献在八叉树结构下实现动态点云无损几何编码不同,文献 [18-20]首先利用二元分解将点云沿x、y、z中的某方向平等划分为两部分,再根据轮廓投影将每一部分点云转换为二值轮廓图像,提出了基于轮廓图像中当前像素邻居像素的帧内上下文[18]、基于参考轮廓图像中同位置像素及其邻居像素的帧内上下文[18]以及基于上一帧点云同位置轮廓图像中同位置像素及其邻居像素的帧间上下文[19]。为提高不同上下文条件下概率估计的精度,文献 [20]根据条件熵大小优先挑选高效率的上下文进行CABAC。随着点云二元分解的进行,轮廓图像被逐一编码。实验结果表明,文献 [20]的S4D-CSPrune方法比文献 [9]的P(Full) 方法提高了大概27%的无损几何编码增益。然而,该方法仅使用了同层级像素,并没有使用已编解码的父层级像素构建上下文,未能有效利用点云的空间相关性。此外,还有大量的研究首先将三维动态点云投射到二维平面上,生成一个二维视频。再利用现有的视频编解码器进行压缩。该类方法掩盖了部分点云真实的三维分布特性,对于动态点云的无损压缩性能并不突出。此类方法通常用于有损压缩[21-23]。

综合而言,上述方法都没有充分地利用点云帧内的空间相关性和帧间的时间相关性。本文针对动态点云几何信息的无损熵编码,旨在构建更高效的上下文模型,同时改进不同上下文条件下的概率估计,从而提高CABAC的编码效率。

1 八叉树结构下的无损几何编码方法

1.1 编码器设计

八叉树结构被广泛应用于表达各种类型的三维点云数据。一个点云被格式化为2D×2D×2D的立方体包围盒,定义为一个D位深度的点云。图1是一个八叉树分解示意。在八叉树的第一层,包围盒被划分为8个尺寸为2D-1×2D-1×2D-1的小立方体。立方体也被称为八叉树节点。当点占据一个八叉树节点时,这个节点再被细分为8个子节点。对于空的八叉树节点,则不再进行划分。通过递归地分割八叉树节点,就可以生成一个八叉树结构。

图1 八叉树分解示意图

为了表示每一个八叉树节点的占用状态,每次划分产生的节点按照莫顿扫描顺序从第0个到第7个进行索引。占据比特表示一个八叉树节点的占用状态,其定义为

(1)

基于八叉树结构的点云压缩即对所有八叉树节点的占据比特进行编码。由于占据比特是二值化符号,所以非常适合使用二进制算术编码器进行压缩编码。

本文提出了一种八叉树结构下动态点云的无损几何编码方法(octree structured dynamic point cloud lossless geometry coding method, octree-DPCLGC),编码器如图2所示。为提高编码效率,本文首先采用当前八叉树节点在帧内的邻居节点和父节点进行上下文建模。同时,将已编解码的上一帧点云作为参考帧,并将参考帧中与当前八叉树节点同位置的节点作为参考节点。然后,用参考节点及其父节点构建上下文。本文提出了一种不同上下文条件下的二级概率估计方法。最后,采用二进制算数编码(binary arithmetic coding, BAC)进行熵编码。

图2 octree-DPCLGC方法的编码器框图

1.2 点云帧内上下文建模

为充分利用点云帧内的空间相关性,本文分别根据当前八叉树节点的邻居节点和邻居父节点进行上下文建模。

与八叉树节点分解出子节点的莫顿扫描顺序一致,本文所提的编解码方法也采用莫顿顺序。因此,编解码当前八叉树节点时,在当前八叉树层级中只有相对于该节点坐标轴负方向分布的节点是绝对编解码过的。当然,采用全部的已编解码节点构建上下文对复杂度来讲是不现实的。为了确保选取的节点与当前节点有较强的空间相关性,本文在每个分布方向上仅选取2个最近的节点参与上下文建模。图3展示了当前节点c0选取的14个邻居节点,根据占据比特可以构建出214=16 384种上下文。上下文索引R可以表示为

(a)r0～r5,与当前节点c0面相邻方向分布的邻居节点

(2)

式中:rj代表第j个邻居节点的占据比特。

此外,本文也利用当前八叉树节点的邻居父节点进一步构建上下文。不同于当前八叉树层级,在父节点层级中所有父节点都是已编解码过的。因此,为上下文建模选取父节点不再仅限于相对于当前节点坐标轴负方向分布的父节点。不过同样考虑到复杂度的问题,不能采用所有父节点构建上下文。为了确保选取的父节点与当前节点有较强的空间相关性,本文采用与选取邻居节点同样的规则,即每个分布方向上仅选取2个最近的父节点参与上下文建模。图4展示了当前节点c0选取的14个邻居父节点,可以构建214=16 384种上下文,其索引S为

(a)s0～s5,与当前节点c0面相邻方向分布的邻居父节点

(3)

式中:sk代表第k个邻居父节点的占据比特。

1.3 点云帧间上下文建模

与二维视频相似,三维动态点云的相邻帧之间存在时间相关性。不同的是,这种相关性不仅表现在点的颜色(点云属性信息)上,也表现在点的位置(点云几何信息)上。针对动态点云的几何信息,图5 展示了动态点云Redandblack第1 450序号帧与第1 451序号帧之间的点位置差异部分。图中,第1 450帧点位置差异用蓝色点表示,第1 451帧点位置差异用黄色点表示。

(a)第1 450帧

在八叉树结构下,这些点位置的差异势必导致当前帧和参考帧生成不同的八叉树。并且,随着八叉树层级的增加,两个八叉树的差异将会扩大。因此,参考帧的八叉树结构不再按照占据节点继续分解、空节点停止分解的规则来生成,而是在当前帧进行八叉树分解的同时,将参考帧按照同样的树结构进行分解,从而准确地找到参考帧中与当前节点同位置的节点,并作为参考节点。图6展示了基于当前帧的参考帧八叉树分解。然而,上述方法会导致参考帧的八叉树结构中存在空的八叉树节点继续分解的情况,如图6(b)所示。

(a)当前帧

为确保准确地利用点云帧间的时间相关性,空节点分解出的空子节点与占据节点分解生成的空子节点需要被区分出来。因此,参考节点的占据比特n及其父节点的占据比特nparent都需要参与上下文建模。值得注意的是,当nparent=0时,n也一定为0。因此,参考节点及其父节点仅构建3种上下文,其索引可以表示为

U=n+nparent

(4)

1.4 二级概率估计

在基于上下文的熵编码中,上下文信息越多,熵就越小或者保持不变。前提条件为:必须在编解码开始前得到其符号概率。然而,当前被应用于点云压缩的CABAC并不满足这一条件。为避免预先计算概率带来的复杂度和延迟,CABAC是在编解码过程中实时估计并更新概率的。

与传统二维视频编解码方法中CABAC所采用的概率估计类似[12-16],本文也基于指数移动平均[24]进行概率估计。给定一个占据比特序列bt,其中t∈{1,…,N}。占据比特bt+1=1的概率pt+1为

(5)

式中:α∈ [0,1]是一个决定概率更新速度的参数。式(5)还可以通过迭代的形式描述

pt+1=pt(1-α)+btα

(6)

式中:pt是上一时刻的估计概率。为了避免使用小数,简化概率估计的实现复杂度,参数α的取值被限定为α=2-β,且β∈N+。因此,式(5)可改写为

qt+1=qt-(qt>>β)+bt((2w-1)>>β)

(7)

式中:qt是pt的w比特整数表现形式;>>是右移运算符。本文采用16比特整数来表示概率,即w=16。这比二维视频编码标准高效率视频编码(high efficiency video coding, HEVC)的7 比特多,但比通用视频编码(versatile video coding, VVC)中双概率估计总共采用的24 比特少[16]。此外,本文根据实验经验设定β=6。

然而,由本文提出的帧内上下文R、S和帧间上下文U组成的上下文数量(16 384×16 384×3=805 306 368)非常庞大。这就意味着,超过8亿个概率qt+1需要被维护和更新,共占用1.5 GB的内存。这空前提升了硬件实现的复杂度。此外,这些上下文中必然包含了大量的罕见上下文。因为缺少输入比特bt,这些罕见上下文相应的概率就不会被很好地估计和更新。使用不准确的概率将会导致编解码器的性能欠佳。综合而言,直接基于8亿多种上下文进行概率估计的方法不可行。

本文提出了一种二级概率估计的方法,如图7所示。帧内上下文R、S的数量是造成上一段所述问题的根本原因。因此,首先分别基于R、S进行概率估计,得出qt+1(R)和qt+1(S)。将概率划分为2θ个大小相等的概率区间,作为优化后的2θ种上下文。上下文索引可以通过右移运算得出

图7 本文提出的二级概率估计方法

R′=qt+1(R)>>(16-θ)

(8)

S′=qt+1(S)>>(16-θ)

(9)

然后,基于优化后的帧内上下文R′、S′和帧间上下文U构建新的二级上下文V。通过调整θ,可以将二级上下文V的数量控制在合理范围内。根据实验经验,本文设定θ=5。因此,二级上下文V的数量为25×25×3=3 072。最后,基于二级上下文V进行概率估计。

2 实验与分析

2.1 实验方法

为评估本文方法octree-DPCLGC的编码性能,使用C++在个人计算机上完成了软件实现,并与下列点云无损几何编码方法进行了比较:基于八叉树结构的方法P(Full)[9]、国际标准G-PCC[11]、基于二值图像的方法S4D-CSPrune[20]。为直接与P(Full)和S4D-CSPrune在各自文献中的实验结果对比,分别选取了微软体素化人物上半身(Microsoft voxelized upper bodies, MVUB)[25]和8i 体素化人物全身(8i voxelized full bodies, 8iVFB)[26]两类点云数据集的第2帧到第101帧作为测试集。这两类点云数据集被广泛应用于评估动态点云压缩方法的性能[6-9, 18-20]。表1给出了两类点云数据集中每个点云序列的名称、每占据体素比特数(Ibpov)。图8和图9展示了每个点云序列的单帧内容。

表1 测试集详细信息

(a)Andrew

(a)LongDress

2.2 编码性能分析

点云无损几何编码的性能由压缩率ρ进行评估

(10)

式中:Ibpov,compressed表示点云被压缩后的每占据体素比特数;Ibpov,original表示原始点云的每占据体素比特数。从定义可见,压缩率越小说明压缩方法性能越好。

本文方法octree-DPCLGC相较于P(Full)、G-PCC和S4D-CSPrune方法的编码增益为

(11)

式中:Ibpov,octree-DPCLGC表示octree-DPCLGC方法压缩点云后的每占据体素比特数;Ibpov,compared表示对照组方法压缩点云后的每占据体素比特数。G为负数意味着octree-DPCLGC压缩后的点云数据更小,即取得了性能提升。反之,G为正数意味着性能降低。

不同动态点云无损几何编码方法的性能比较如表2所示。可以看出,octree-DPCLGC方法在MVUB和8iVFB数据集上分别表现出了较为平稳的编码性能,其压缩率为3%左右。其中,octree-DPCLGC方法在点云序列Soldier上的性能尤其突出,压缩率为2.3%,明显优于其他点云序列的压缩率。同时,观察到P(Full) 和S4D-CSPrune方法也存在同样的现象。根据对点云序列Soldier的内容分析可知,该动态点云中人物运动变化较小,有大量点云帧展现了人物站立不动的场景。与运动幅度大的点云序列相比,该点云序列拥有较强的时间相关性,从而提高了帧间上下文的效率。

表2 不同动态点云无损几何编码方法的性能比较

分析octree-DPCLGC方法的相对编码增益可知,octree-DPCLGC性能明显优于P(Full)和G-PCC,其原因主要在于本文提出的二级概率估计能够更高效地利用邻域和时域信息,显著提升了熵编码效率。与基于二值图像的方法S4D-CSPrune相比,octree-DPCLGC方法在MVUB和8iVFB数据集上的平均编码增益分别为-1.5%和-2.8%。具体地,octree-DPCLGC方法为9个点云序列中的6个带来了编码增益,最高的为点云序列LongDress的-6.8%。

2.3 时间复杂度分析

在一台配置了Intel Core i7-7500U CPU @ 2.70 GHz 和24 GB内存的个人计算机上测试了本文方法octree-DPCLGC的编解码时间。各点云序列从2～101 帧的平均每帧编解码时间和平均每帧占据体素数量如表3所示。分析可知,点云序列的平均每帧编解码时间与平均每帧占据体素数量呈线性正相关。需要说明的是,由于P(Full)[9]和S4D-CSPrune[20]仅是在Matlab上进行了仿真实验,所以本文无法与其进行精确的时间复杂度对比。

表3 octree-DPCLGC方法的编解码时间

3 结 论

本文面向动态点云的无损压缩,提出了一种八叉树结构下的几何信息编码方法。基于动态点云帧内的空间相关性,采用当前八叉树节点在各个方向上的有限个已编解码的邻居节点和父节点进行帧内上下文建模。针对动态点云帧间的时间相关性,将已编解码的上一帧作为参考帧,并将参考帧内同位置的八叉树节点作为参考节点。基于参考节点及其父节点构建帧间上下文。为解决上下文因数量过于庞大而导致的概率估计不准确和复杂度过高的问题,提出了一种二级概率估计的方法。该方法不仅有效地利用了帧内和帧间上下文,同时也将复杂度控制在可接受的程度。实验结果表明,与现有的八叉树结构下的动态点云无损几何编码方法相比,本文octree-DPCLGC方法带来了显著的编码增益。与近年来发表的基于二值图像的动态点云无损几何编码方法相比,octree-DPCLGC方法带来了大约-2.2%的编码增益。

本文在利用动态点云帧间时间相关性的方面还有所欠缺,下一步将进一步研究帧间上下文的建模。此外,引入点云帧间运动向量进一步去除时间冗余也是一个重点研究方向。