3D-HEVC帧间编码的低复杂度算法

马 然，史楠迪，李攀攀，沈礼权

(上海大学 通信与信息工程学院 新型显示技术及应用集成教育部重点实验室，上海 200072)

3D-HEVC帧间编码的低复杂度算法

马 然，史楠迪，李攀攀，沈礼权

(上海大学 通信与信息工程学院 新型显示技术及应用集成教育部重点实验室，上海 200072)

3D-HEVC将HEVC先进的编码工具充分应用到3D视频，随之带来的主要问题是编码的高复杂度。针对3D-HEVC的帧间编码提出了两点改进以降低其编码复杂度。首先，根据相邻帧相关性自适应确定编码单元的划分深度，然后通过判断编码单元的运动活跃度来限定预测单元的类型选择。提出的算法经仿真实验证明，在保持码率、PSNR基本不变的情况下，其编码时间平均可减少30%。

3D-HEVC；帧间编码；低复杂度；预测单元；划分深度

随着立体视频成为当下社会的研究热点，多视点视频加深度编码(Multi-View Video Plus Depth Coding，MVD)已成为描述立体视频场景最为有效的视频格式，并被MPEG所采纳。为了有效地消除多视点视频的空间、时间冗余和视点间冗余，可以在采用分层B帧(Hierarchical B Pictures)编码预测结构的3D-HEVC编码平台HTM上实现MVD的编码[1]。基于HEVC的MVD编码技术引入了视差估计预测技术，在编码效率提高的同时显著增加了编码计算复杂度。因此在多视点高清视频进入实际应用系统之前，研究高压缩效率和低复杂度的3D-HEVC编码技术是必要的。

为了提高HEVC的编码速度，国内外学者已经提出了一些HEVC快速算法。其中，对帧间编码的快速算法主要包括基于SKIP模式提前终止编码单元(Coding Unit，CU)划分的算法、自适应设置率失真代价(RDCost)阈值算法以及预测模式快速选择算法等。基于SKIP模式提前终止CU划分算法是在对当前CU进行深度划分时，如果预测单元(Prediction Unit，PU)为SKIP模式，就提前终止CU划分[2]。此类算法对于平坦或运动缓慢序列效果较好，平均可以提高50%的编码速度，而对于纹理复杂或运动剧烈序列效果较差，平均仅能提高16%的编码速度。自适应设置RDCost阈值算法[3]是对每个划分深度的CU设置不同的阈值，如果在当前划分深度下，最佳预测模式对应的RDCost小于设置的阈值，则提前终止CU划分。此类算法对于各种类型序列都能平均提高40%左右的编码的速度，但是BD-rate却上升2%左右，对编码效率影响较大。Shen提出的预测模式选择的优化算法[4]是在遍历划分模式中，如果当前模式使得RDCost小于参考CU的RDCost加权和则提前终止预测模式选择。此类算法对于不同序列均可以提高50%的编码速度，而且在不同序列上编码效率略有差异。

在双目视频编码中，文献[5]分析纹理视频在时间域和视点间的相关性，提出了一种深度宏块的编码跳过算法。针对跳过编码的宏块，算法通过相邻视点间的深度图预测设计了一个可以重建该宏块的模型。试验结果证明该算法不仅能够提高虚拟视点的绘制质量，并且可以降低整体的编码复杂度。但是它设计的模型依赖于双目视频格式，在多视点视频格式中没有较好的表现。文献[6]首先利用多视点间的几何信息和相应的深度信息来获取编码视点的位置；然后将已获取位置且已编码的视点的编码类型和运动信息用来限制当前编码帧的类型选择，这种算法可以有效降低运动估计的计算复杂度。然而，它所提出的时空相关性的思想只限于视点级的应用，没有推广到帧级和编码单元级。此外，这些文献中的MVD编码算法都不是基于HTM编码平台的。换言之，上述的MVD编码算法并不适用于HTM编码平台，同时也未充分发挥HEVC的先进编码技术。文献[7]提出了3D-HEVC下的独立视点纹理快速帧间预测算法，该算法分析了视点间相关性，并以此设计了一种划分深度快速抉择和Merge模式选择机制，其算法的实现与Shen的快速深度遍历选择有相似之处。

本文延续了Shen的算法思路，将其扩展到多视点加深度的编码框架中，并加以改进。在分析基于多尺寸CU的编码复杂度的基础上，从CU的深度划分和PU类型选择这两个方面降低编码的计算耗时。

本文的结构安排如下：第1节分析HEVC中帧间编码的复杂度及影响编码复杂度的2个重要指标：划分深度和帧间PU类型选择。在此基础上，第2节提出了2个改进——基于相邻帧相关性的自适应深度预测和基于运动活跃度的PU类型选择，进而实现旨在降低编码复杂度的基于HTM的MVD编码算法。第3节的实验验证了本文提出的2个改进算法以及整体算法在保证PSNR基本不变的情况下，使得编码复杂度得到一定程度的下降。第4节简要总结本文的研究。

1 HEVC中的帧间复杂度分析

有文献表明，HEVC在引入先进的编码技术后，帧间编码耗费时间占据总体编码时间的的60%以上[8]。因此，研究低复杂度的HEVC帧间编码算法势在必行。

1.1 HEVC的划分深度和帧间PU类型

HEVC编码器从最大编码单元(Largest Coding Unit， LCU)开始划分成若干个CU，直至划分到最小编码单元(Smallest Coding Unit， SCU)为止。其对应的尺寸从64×64～8×8，划分深度是[0，3]。CU作为编码的基本单位，其功能类似于H.264中的宏块，不同在于CU的最大尺寸不受限制。根据编码的需要，CU可以递归地分割为4个相同尺寸的子CU。每个CU或子CU又可分成若干个PU[9]。

在HEVC编码过程中，所有与预测相关的操作 (例如帧内预测和帧间预测) 均是以PU为单位进行；PU作为预测编码的基本单元，它可以分割成8种类型(见图1)，以适应规则的或不规则的编码区域特性。

图1 PU的8种类型

1.2 HEVC帧间编码过程分析

HEVC特殊的编码块结构决定了其帧间编码过程与H.264完全不同。HEVC帧间编码以四叉树的形式对编码单元进行递归编码。每层深度的CU，都会对所有的PU类型进行率失真代价的计算，并判断深度划分是否合适。在HTM-9.0中，1个LCU的完整帧间编码过程主要由以下2个主要步骤组成[10]：

1)对于当前的LCU，所有CU(编码深度从0～3)都遍历所有帧间和帧内预测模式，得到其对应的最优PU类型和率失真代价。

2)求得4个编码深度为3的CU的率失真代价之和，并与编码深度为2的CU的率失真代价相比，取率失真代价小对应的PU类型；接着，再将4个编码深度为2的CU的率失真代价之和与编码深度为1的CU的率失真代价相比，取率失真代价小对应的PU类型。以此类推，直到确定编码深度为0的CU的PU类型。

文献[4]指出，当编码的划分深度为3时，LCU进行的率失真代价计算约为800次。所以可以从划分深度和PU类型两方面入手研究，对帧间预测进行优化。

1.3 3D-HEVC的实验数据分析

除了从HEVC的编码结构和编码过程可以看到划分深度和PU类型的选择对帧间编码的复杂度影响很大外，HTM原算法的实验数据也可证明该影响的严重性。这里，在HTM9.0上对MVD序列进行实验(QP分别取25、30，每个视点编码17帧)，统计了不同MVD序列CU最佳划分深度的相关数据，见图2和图3。

图2 CU实际划分及最佳深度分布

图3 时间复杂度测试结果

图2a是Street序列第5帧的CU实际划分情况。显然，在纹理复杂区域和运动的边缘区域，由于需要更精确的编码，CU划分深度较大。图2b是Balloons和Street两个MVD测试序列中纹理、深度视频的CU划分深度比例及平均划分深度比例。平均划分深度是编码17帧纹理与深度的平均值。从图2b可以看出，随着CU划分深度的增加，对应划分深度的CU所占比例呈负指数曲线的降低。遗憾的是，在实际的编码器中，在编码时始终按照[0，3]线性递进的定义划分深度值来进行计算、划分子块等工作，没有自适应地跳过一些不必要的PU类型和深度，增加了编码复杂度。

图3是实验测试得到的不同划分深度的 CU 在 帧间编码中的编码时间比。其中，图3a图为Street序列测试结果，图3b为Balloon序列测试结果。横坐标0、1、2、3分别代表各划分深度。从图3可以看到，各划分深度CU对应的编码时间所占比大体相差不多。但与图2b相对照，很明显，划分深度越小的CU所消耗的编码时间越小；反之亦然。

不同编码图像的最佳CU划分与其图像内容有很大的相关性。在HEVC中，对运动缓慢的、平坦的编码区域往往采用大尺寸块进行编码，以节省运动信息和预测模式的编码比特传输；对运动剧烈的、复杂的图像往往采用小尺寸块进行编码，以提高视频质量。针对此特点，可根据当前CU和参考CU的时空相关性，对LCU进行分类。诸如8×8和16×16小尺寸块的CU的遍历过程在整个划分过程中消耗着巨大的计算资源，对编码性能的提升却是很有限的贡献。

在HEVC编码模型中，CU的划分深度一般固定在[0，3]之间。然而，根据以上分析，在平坦的区域，CU划分深度一般在较小范围变化；而在运动剧烈区或纹理复杂区则划分深度一般较大。并且由上文所述的深度复杂度分布来看，一味地将所有深度遍历之后再决定最佳划分深度，浪费了很多的编码时间。所以，应根据当前编码块的运动特性自适应的调整深度选取范围。因此，基于不同编码序列的图像内容，实现自适应的最佳块划分预测的快速算法，可以有效减少块划分中不必要的编码判决计算过程，降低块划分过程中的编码复杂度。

2 低复杂度帧间编码算法

根据上节的实验验证和分析，本文充分挖掘HEVC的编码特性和MVD的编码预测结构，提出了一种旨在降低帧间编码复杂度的快速算法。此算法关键方面在于：1)利用参考帧与当前帧的相关性，预测当前CU的划分深度，跳过预测范围外的深度判断。2)利用定义的运动特征函数对CU进行判定，并根据判定跳过一些不必要的PU类型。

2.1 基于相邻帧相关性的自适应深度划分

同一视点中的CU之间存在时间、空间相关性，当前CU的最佳划分深度与参考CU的划分深度相似或者相同。因此，可以利用时空相关性的特性把当前CU的深度限制在一定的范围内，从而跳过一些不必要的计算。

除了时空相关性以外，多视点中的CU之间还存在视点间相关性，因此本文选用的参考CU不仅包含了当前帧空间相邻的CU，而且还包括了相同视点内前一帧或相邻视点同一时刻帧的相同位置的CU及其相邻CU。图4给出了参考CU的示意图，其中参考帧既可以是相同视点内前一帧，也可以是相邻视点同一时刻帧，依据编码标准的参考帧设置策略，选取参考帧列表中首选位置的参考帧。

图4 参考CU的示意图

在每个参考CU中，其内部各子CU的最佳划分深度值一般是不同的，因此首先根据式(1)求得各子CU的平均划分深度作为该参考CU的深度

(1)

式中：Depthref(i)为第i个参考CU的划分深度值；M为这个参考CU中4×4块的个数；Depth(k)代表第k个4×4块的深度值。

设定Depthcur表示当前CU的最佳划分深度，可根据式(2)由N个参考CU的深度值加权获得

(2)

据实验统计，这里N取7，即图4所示全部7个参考CU。ε(i)为不同参考CU对当前CU的影响权重，且∑ε(i)=1。文献[11]指出参考帧上相同位置的参考块CU与当前CU存在很强的相似性，经大量实验验证以及深度预测准确率的反馈，本文将参考帧相同位置上的CU的ε(i)设置为0.4，其他参考CU均为0.1。

具体算法实现步骤如下：

1)在Z字形扫描过程中，根据式(1)计算每一个参考CU的深度值Depthref。

2)利用式(2)计算当前CU最佳深度预测值Depthcur。

3)如果Depthcur在[0，0.7]之间，则表示当前CU所处区域一般为平坦区，限定深度区间为[0，1]；如果当前预测值在(0.7，2.8]之间，则表示当前CU处于一般运动区或一般纹理区，深度划分处于中间值，故限定区间为[1，3]；预测值大于2.8，表示当前CU处于复杂纹理区，故限定区间为[2，3]。

本文在HTM9.0平台上测试了4个序列Balloons，Street，Newspaper，Kendo。分别取不同量化步长进行实验，共编码17帧。表1是Depthcur按照步骤3)划分深度区间的正确率统计，可以看到其平均正确率在90%左右。

表1 深度范围预测正确率统计

2.2 基于运动活跃度的PU类型选择

文献[12]的研究成果表明在编码帧中大尺寸CU适合缓慢变化的平坦区域，而小尺寸CU适合包含快速运动物体的区域。由此可见当前CU的最佳PU类型与运动程度有密切关系，所以以当前CU的运动程度预测PU类型选择范围，减少模式遍历的计算过程，降低编码复杂度。

本文以运动活跃度[13]作为衡量当前CU的最佳PU类型和它的运动程度关系的判定标准。并推广至纹理与深度的联合编码框架中。运动活跃度是对编码单元内运动强弱的描述。本文在度量MVD中当前CU的运动程度时，考虑了多个与当前CU相关的参考块的情况。

接着，将来自这些参考CU的运动矢量以不同权重计算作为当前CU的运动矢量长度。与文献[13]不同的是，由于本文选取与当前CU相邻的上方、左方、左上的3个参考CU和参考帧中对应位置相同的参考CU(图4中灰色框对应的参考CU)的运动情况对当前CU进行准确的预测，所以本文重新定义了运动活跃度L

L=0.3×l(MV1)+0.3×l(MV2)+

0.3×l(MV3)+0.1×(MV4)

(3)

式中：MVi为运动矢量；l(MVi)是运动矢量的模，由式(4)求得；而l(MVi)前的系数为经验值，经过实验验证得出选取上述系数时，预测效果较好。

(4)

式中：xi和yi是MVi的水平和垂直方向的值，i=1，2，3，4。

本文选择上述相同的4个测试序列，分别取25、30、35、40不同量化步长，对纹理视频进行测试，运动活跃度L与PU类型分布之间的关系参见表2。

表2 PU类型分布与运动活跃度关系表 %

由表2可以看出，L在[0，1) 和[1，2)两个区间中，PU类型是“SKIP，Inter_2N×2N”的比例分别高达94%和89.02%；L在 [2，3)中PU的主要类型是“Inter_N×2N，2N×N”，在[3，∞)中则主要是“其他帧间或帧内类型”的 PU。因此，在帧间编码进行到PU类型选择时，可以预先将PU类型限制在小范围内，进而降低编码复杂度。当L确定后，如果只选表2中对应比例最大的PU类型，PU类型被限制在最小范围内，但也影响到了PU类型选择的精准性，因此，本文选择表2中比例大于9%的PU类型。至此，本文根据L与PU类型的关系将当前CU分为三种类型，参见表3。其中，[0，1)对应的CU运动简单，定义为类1；[1，2)对应的CU运动一般，定义为类2；[2， ∞)的时候则运动复杂，定义为类3。

表3 运动程度分类以及与其对应的类型

在得到CU的运动活跃度之后，根据表3选择与之对应的适用类型，无须遍历所有的模式，从而降低了编码复杂度。

因此，基于运动活跃度的PU类型选择算法的实现步骤如下：

1)判断当前CU是否属于关键帧。如果是关键帧，依照平台算法选取RDCost最小时的类型为最佳类型，继续处理下一个CU，否则执行2)。

2)根据式(3)求得当前CU的运动活跃度L，并判定当前CU的运动程度

3)根据表3选择对应的PU类型组，在这已缩小范围的PU类型组中，选择具有最小RDCost值的PU类型作为最佳PU类型。

2.3 整体算法

对于MVD这种特殊的视频编码结构而言，描述同一时刻、同一场景的纹理图与深度图存在着极大的轮廓相似性[11]和运动相似性，反映到两者的编码信息(如PU类型、RDCost、运动矢量等)具有相关性。因此，本文将第2.1节和第2.2节提出的算法直接用于深度图的帧间编码中。

本文提出的整体算法如图5所示。

图5 整体算法流程图

3 实验结果

为验证本文提出的算法的有效性，在参考软件HTM9.0上以“纹理加深度联合编码”为框架进行测试。表4给出了测试条件，硬件配置为i5-4570，4 Gbyte内存。其中测试序列为MVD标准序列：Street,Newspaper,Balloons,Kendo。量化步长从25变化到40，以测试算法在不同序列不同量化步长下的表现。

表4 测试条件

表5～表8给出了本文提出的算法时间复杂度的结果，其中“复杂度降低”列是指与HTM原算法相比，各算法的时间复杂度的降低比例。与原算法相比，第2.1节提出的自适应深度划分算法、第2.2节提出的PU类型选择算法以及整体算法无论是在高比特率(QP为25，30)还是在低比特率(QP为35，40)情况下，均能表现出较好的效果。并且整体算法可以降低平均30%的编码时间。

表5 QP=25时，快速算法测试结果

表6 QP=30时，快速算法测试结果

表7 QP=35时，快速算法测试结果

表8 QP=40时，快速算法测试结果

通过实验数据可发现，计算复杂度的降低幅度会随着QP的增大而增大。这是因为在高QP下大块划分和最佳PU类型为Inter 2N×2N的概率会增大，而本文算法的自适应深度划分算法跳过不必要深度的几率也随之增大；并且基于运动程度选择PU类型，在运动简单或一般区域将Inter_2N×2N设为必须遍历的PU类型。因此在高QP下，本文算法降低计算复杂度的效果更为明显。

本文除了与HTM9.0原算法进行比较之外，还选择了将Shen提出的算法[4]在HTM上扩展进行对比，其结果如表9所示。“BD-rate”列是与HTM原算法相比，在相同PSNR、QP分别取25,30,35,40的条件下所增加的平均比特率。由于快速算法跳过了一些划分深度和预测模式，可能存在预测编码中不能选取最佳预测类型而只能以次佳类型代之的情况，因此Shen的算法和本文的算法较之HTM原算法在比特率上稍有提高，但本文算法的比特率增加量较少。从“复杂度降低”列来看，与HTM原算法相比，Shen的算法和本文的算法的计算复杂度都有很大的降低，但Shen的算法效果更为明显。这实际上是在BD-rate和时间复杂度之间的矛盾所引起的。总体来看，本文算法对编码效率的影响较小，而编码复杂度亦可降低30%。

表9 两种方案的性能

图6给出了在Street,Newspaper,Balloons,Kendo 4个序列上3种方案的率失真性能比较曲线。可以看出，在不同序列下，本文算法均能表现出与软件平台相近的编码效果。

4 结论

在基于HTM的编码平台上，MVD结构通过对所有编码单元的类型遍历之后，才能获得最佳的类型及尺寸。这种技术同样也带来了非常高的计算复杂度，特别是帧间编码占用了较大的编码时间。为了降低计算复杂度并保证编码效率的稳定性，本文结合HEVC的编码特点，提出了一种有效的低复杂度编码算法，一方面根据帧间相关性预测当前CU的划分深度，另一方面利用运动分类方法对选择适当的划分类型，实

图6 本文提出的算法与HTM原算法的RD曲线对比图

验结果显示该算法适用于多视点视频加深度的编码平台。然而，必须指出的是，本文着重在对MVD中纹理视频编码的研究，并依据纹理和深度的相关性，将纹理视频的编码成果直接用于深度编码中，没有过多的考虑到深度序列的特性，在未来的研究中拟分析深度视频较为平滑的特点，有针对性地提出适用于深度序列的快速算法。

[1] NOOR N，KARIM H A，ARIF N A M，et al. Multiview plus depth video using high efficiency video coding method[C]//Proc. IEEE International Conference on Signal and Image Processing Applications(ICSIPA 2013). [S.l.]：IEEE Press，2013：209-213.

[2] CHOI K，PARK S H，JANG E S. Coding tree pruning based CU early termination[C]//Proc. Joint Collaborative Team on Video Coding.[S.l.]：JCT-VC，2011：14-22.

[3] CASSA M B，NACCARI M，PEREIRA F. Fast rate distortion optimization for the emerging HEVC standard[C]//Proc. Picture Coding Symposium (PCS). [S.l.]：IEEE Press，2012： 493-496.

[4] SHEN L，LIU Z，ZHANG X， et al. An effective CU size decision method for HEVC encoders[J]. IEEE Trans. Multimedia,2013，15(2)：465-470.

[5] LEE J Y，HO-CHEON W，DU-SIK P. A fast and efficient multi-view depth image coding method based on temporal and inter-view correlations of texture images[J]. IEEE Trans. Circuits and Systems for Video Technology，2011，21(12)：1859-1868.

[6] MICALLEF B W，DEBONO C J，FARRUGIA R A. Fast inter-mode decision in multi-view video plus depth coding[C]//Proc. Picture Coding Symposium (PCS). [S.l.]：IEEE Press，2012：113-116.

[7] ZHANG N，ZHAO D，CHEN Y W，et al. Fast encoder decision for texture coding in 3D-HEVC[J]. Signal Processing：Image Communication，2014， 29(9)： 951-961.

[8] 沈晓琳. HEVC低复杂度编码优化算法研究[D].杭州：浙江大学， 2013.

[9] SULLIVAN G J，OHM J，WOO-JIN H，et al. Overview of the high efficiency video coding (HEVC) standard[J]. IEEE Trans. Circuits and Systems for Video Technology，2012，22(12)：1649-1668.

[10] HEVC测试模型[EB/OL].[2014-12-06].https：//hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/tags/HM-9.0.

[11] SEO J，PARK D，WEY H C，et al. Motion information sharing mode for depth video coding[C]//Proc. 3DTV-Conference：The True Vision-Capture，Transmission and Display of 3D Video.[S.l.]：IEEE Press，2010：1-4.

[12] ZHANG Q，LI N，WU Q. Fast mode decision for 3D-HEVC depth intra-coding[J]. The Scientific World Journal，2014，50(14)：994-996.

[13] ZENG H，CAI C，MA K K. Fast mode decision for H. 264/AVC based on macroblock motion activity[J]. IEEE Trans. Circuits and Systems for Video Technology，2009，19(4)：491-499.

史楠迪(1990— )，硕士生，主研图像与视频信号处理；

沈礼权(1978— )，博士，副研究员，主要研究方向为图像与视频信号处理。

责任编辑：时 雯

Low Complexity Inter-frame Coding of Multi-view Plus Depth Video Coding

MA Ran，SHI Nandi，LI Panpan，SHEN Liquan

(SchoolofCommunicationandInformationEngineering，KeyLaboratoryofAdvancedDisplayandSystemApplicationoftheMinistryofEducation，ShanghaiUniversity，Shanghai200072，China)

3D-HEVC makes full use of HEVC’s advanced coding tools to 3D video， which causes high coding complexity. So， two improvements are proposed for inter-frame coding of 3D-HEVC， to reduce coding complexity in this paper. First， the bit-depth of coding unit is judged adaptively based on the correlation of adjacent frames. Then， the types of prediction unit are limited by estimating the motion activity of current coding unit. Experimental results show that the proposed algorithm can reduce about 30% of encoding time as compared to HTM， while it maintains the similar PSNR and bit-rate.

3D-HEVC；inter frame coding；low complexity；prediction unit；bit-depth

【本文献信息】马然，史楠迪，李攀攀，等.3D-HEVC帧间编码的低复杂度算法[J].电视技术,2015，39(13).

国家自然科学基金项目(61301112)

TN919.8

A

10.16280/j.videoe.2015.13.002

马 然(1974— )，女，博士，副教授，主要研究方向为图像与视频信号处理；

2015-01-15