一种基于空时域相关性的HEVC帧间预测模式快速决策算法

李　强，覃杨微

(重庆邮电大学 信号与信息处理重庆市重点实验室，重庆 400065)



一种基于空时域相关性的HEVC帧间预测模式快速决策算法

李强，覃杨微

(重庆邮电大学 信号与信息处理重庆市重点实验室，重庆 400065)

摘要：为了减小高性能视频编码(high efficiency video coding，HEVC)的复杂度，提出一种基于四叉树结构类型分析的帧间预测模式快速决策改进算法。一方面，统计并分析空时域相邻编码单元(coding unit，CU)和CU深度之间的相关性，确定其深度遍历区间，跳过一些冗余CU的分割，从而减少CU深度划分的复杂度；另一方面，通过分析遍历区间内CU的运动特征和预测单元(prediction unit，PU)模式特性，确定不同运动特征所对应的PU模式，减少所需遍历候选PU模式的数量和所需要进行的率失真代价计算的数量。与HM14.0相比，采用该算法的HEVC编码器在输出比特率增加很小的情况下，平均编码时间降低了46.9%，而编码后的视频质量基本不变。

关键词：高效率视频编码；深度划分；模式决策；率失真代价

0引言

随着通信系统和网络技术的发展，通信终端处理能力的提高，人们互相传递和下载的视频内容日益丰富多样。高清/超高清视频、3D电视、视频流媒体等这些海量数据的存储和传输对数据压缩编码技术提出了更高的要求。虽然采用H.264/AVC[1]标准的视频编码器具有出色的压缩性能，但已经不能满足新型视频应用的需求。ITU-T和ISO/OSI联合成立的视频编码联合协作组JCT-VC[2-3]于2013年1月发布新一代高效率视频编码(high efficiency video coding，HEVC)[4]标准，通过采用灵活的四叉树编码结构，更多的编码模式和新颖的滤波技术，提高了视频编码效率。与H.264/AVC高档次[1]相比，在保证相同视频质量的前提下，HEVC可降低50%的编码输出比特率，但是，编码复杂度大幅度增加。

帧间预测编码是HEVC的关键技术之一，利用相邻图像间的相关性，采取运动估计和运动补偿预测的编码方法消除了视频信息中的时间冗余。在帧间预测模式决策过程中，HEVC参考模型(HEVC model，HM)采用了拉格朗日率失真优化方法为每个编码树单元(coding tree unit，CTU)确定除量化参数外的编码参数，主要包括编码单元(coding unit，CU)划分模式、预测单元(prediction unit, PU)模式和变换单元(transform unit，TU)模式判决的预测参数等。由于一个CTU包含了大量的编码参数，而采取分级遍历的方式来确定不同层的编码参数导致了非常高的计算复杂度。文献[5]根据CU的运动特征进行自适应调整深度范围。文献[6]根据空域相关性自适应地决定当前CU深度的最大值和最小值。显然，这种仅根据空域的相关性的方法降低的复杂度是有限的，且其预测深度值的准确度也不高。文献[7]采用空时域联合预测的方式，利用相邻CU深度值加权预测出当前CU的深度值，确定CU的深度遍历区间。该方法虽然很大程度上减少了遍历范围，但未考虑到视频内容及其序列的差异性，其固定权重值导致预测深度值在其给定的遍历区间存在相当大的改善空间。

本文针对CU深度判断提出了一种改进的快速决策算法，提高了帧间预测模式决策速度。利用相邻CU空时域相关性和CU深度之间的相关性，减少CU深度划分的复杂度。通过分析参考帧中对应位置CU的PU模式特性和相邻CU的PU模式的复杂参数对PU模式进行快速决策，减少不必要的PU候选模式的遍历，从而降低PU模式选择的复杂度。实验结果表明，采用本文的改进算法可使得在平均编码比特率增加很少的情况下，平均编码时间大幅度减少，视频质量基本不受影响。

1HEVC快速帧间模式决策算法

1.1HEVC中的CU和PU特性

HEVC中的一帧视频分为多个片，一个片由多个CU组成。处于第1层的CU尺寸为64×64，它可以分为4个32×32的CU块，递归划分CU直到当前CU的尺寸为8×8。图1表示了CU的四叉树结构[8]划分过程。每个CU都是根据相应的四叉树结构来决定是否划分。在HEVC的参考软件HM的14.0版本HM14.0[9]中，为了得到最佳的CU深度层，需遍历深度0—3的CU，比较得出率失真代价值最小的CU即为所选取的最佳CU。

图1　CU划分Fig.1　CU splitting

图2　PU模式Fig.2　PU mode

每一个CU可以继续划分成如图2所示的PU。PU模式包括：跳过模式(skip mode)、合并模式(merge mode)、帧间模式(inter mode)和帧内模式(intra mode)。其中inter mode中的interN×N只有当前CU深度值为最小深度时才可用。而intra mode中的intraN×N也只有当前CU深度值为最小深度时才可用。HEVC使用公式(1)计算率失真代价。

(1)

(1)式中，Bmode表示在每个决策下，实际需要耗费的比特率。SSE是当前块和匹配块的平均差值，ωchroma是色度分量的权重因子，λ是拉格朗日乘子。其中下标luma表示的是亮度分量，chroma表示的是色度分量，mode表示的是当前所选模式。

选择较大的CU块意味着可用较少的比特去表示所选择的运动矢量和预测模式类型。但是在复杂或运动变化剧烈的区域，当前块和匹配块之间的残差会产生较大的能量。选择较小的CU块，虽会产生较小的SSE，但增加了表示运动矢量的比特数。对于背景静止或平稳的区域，较大的块能较好地表示其运动特征，且不会带来较大的比特。对于含有不同目标的背景或较复杂运动区域，选择较小的块可以较细致地表示出运动特征，且不会带来较大的残差。如果利用CU的运动特征去预测那些可能被选为较大块来进行编码的块，就可以跳过一些较小块的率失真代价的计算，这样来降低编码复杂度。

由文献[10]可知，当前CU0最佳预测模式和其相邻CU有很大的相关性，因此，可定义一个如(2)式所示的预测候选块集合。

O={CU1,CU2,CU3,CU4,CU5,CU6,CU7,CU8}

(2)

在图3中，CU1，CU2，CU3和CU4是与CU0空域相邻的候选预测编码单元；CU5和CU6是在参考帧中与CU0位置相同的编码单元，即时域相邻的编码单元；CU7和CU8是CU0的父类(上级)编码单元。

图3　预测和当前CU

经统计相邻帧CU的相关性[11]发现，参考帧相同位置的CU，即Co-located CU与当前CU的深度差值为3的概率很小。如果当前CU的深度为X，而Co-located CU的深度达到了X+3，则可跳过当前深度X的计算，直接跳到下一深度X+1，减小CU深度划分的复杂度。

1.2CU深度快速决策

本文充分利用空域、时域以及父类CU的相关性来提高CU深度决策的速度，其算法流程如图4所示。

由于视频序列存在空时域相关性，当前CU的最佳深度与相邻CU的深度接近，有些甚至相等。基于这个特点，可将HEVC的CU深度划分为如表1所示的5个深度类别。根据图3中所示的相邻块，采用(3)式和(4)式计算得到深度预测值Depthp。

(3)

(4)

图4　CU深度快速决策算法流程图Fig.4　Flow chart of a fast CU depth decision algorithm

(3)—(4)式中：i是图3中候选CU的下标值；N为所有候选CU的数量，其值为8；depthi表示相邻的CU的深度值；αi表示的是权重，其值根据表2中的相关性值ρi来确定。由表2和表3可知，当前CU和相邻CU的相关性越低，αi值越小；反之，αi值越大。同时，αi必须满足(4)式。这里需要指出的是，只有当相邻的CU全部可用时，才能使用(3)式来确定当前深度范围，否则深度为[0,3]。

表1　CU的候选深度层

表2　当前CU和相邻CU之间的相关性

表3　CU权重值

计算出Depthp值后，根据以下步骤，将CU深度划分为5个类型。

①当Depthp的值为0时，相邻CU深度均为0，且选择SKIP作为其最佳的预测模式，表明当前CU处于静止区域，将该区域划分为M0。

②当Depthp的值在区间(0,0.3]时，大多数相邻CU选择最佳深度为0，表明当前CU处于平稳区域，将该区域划分为M1。

③当Depthp的值在区间(0.3,1.3]时，大多数相邻CU选择最佳深度为1，表明当前CU处于比较平稳区域，将该区域划分为M2。

④当Depthp的值在区间(1.3,2.5]内时，大多数相邻CU选择最佳深度为2，表明当前CU处于较复杂区域，将该区域划分为M3。

⑤当Depthp的值大于2.5时，大多数相邻CU选择最佳深度为3，表明当前CU处于复杂区域，将该区域划分为M4。

对于M0区域的CU，其最佳深度为0，不再进入下一深度的遍历；对于M1—M3区域内的CU，如果Co-located CU与当前CU所要遍历的深度的差值大于2，则选择跳过当前深度，直接进入到下一深度的遍历。

1.3PU模式快速决策

在CU深度范围内，对当前CU所需遍历的候选PU模式进行优化，减少遍历候选PU模式的数量，降低PU模式决策的复杂度。由于当前CU与Co-located CU具有很大的相似性[12]，若当前所要遍历的CU深度和Co-located CU的深度相等，则可根据Co-located CU的PU模式来决定当前CU的PU模式的候选遍历。本文PU模式快速决策算法流程如图5所示。

图5　PU模式快速决策算法流程图Fig.5　Flow chart of a fast PU mode decision algorithm

①当Co-located CU的PU模式为SIZE_2N×2N时，说明对应块的纹理比较平稳或其所处的区域中的运动对象都有着相似的运动方向。因此，对当前CU的PU模式为SIZE_2N×2N，SKIP，SIZE_2N×N和SIZE_N×2N进行检测。

②当Co-located CU的PU模式为SIZE_nL×2N或SIZE_nR×2N，说明对应块的纹理较复杂，分为左右两部分的概率大。因此，对当前CU的PU模式为SIZE_nL×2N，SIZE_nR×2N和SIZE_N×2N进行检测。

③当Co-located CU的PU模式为SIZE_2N×nU或SIZE_2N×nD，说明对应块的纹理较复杂，且分为上下两部分的概率大，因此，对当前CU的PU模式为SIZE_2N×nU，SIZE_2N×nD和SIZE_2N×N进行检测。

④当Co-located CU的PU模式为SIZE_N×2N，说明对应块的纹理运动比较平缓，分为左右两部分的概率较大，因此，对当前CU的PU模式为SIZE_2N×2N，SIZE_N×2N，SIZE_nL×2N，SIZE_nR×2N和SIZE_2N×N进行检测。

⑤当Co-located CU的PU模式为SIZE_2N×N，说明对应块的纹理运动比较平缓，且分为上下两部分的概率较大，因此，对当前CU的PU模式为SIZE_2N×2N，SIZE_N×2N，SIZE_2N×nU，SIZE_2N×nD和SIZE_2N×N进行检测。

⑥当Co-located CU的PU模式为SIZE_N×N，说明对应块的纹理相对复杂，因此，对当前CU的PU模式为SIZE_N×N，SIZE_2N×nU，SIZE_2N×nD，SIZE_nL×2N和SIZE_nR×2N进行检测。

如果当前CU的深度和Co-located CU的深度不相等且差值不大于2时，可以根据相邻CU的PU模式来预测当前CU的PU模式。根据相邻CU的PU模式复杂度的不同，将HEVC中的PU模式划分4个不同复杂度的类型，模式的权重值如表4。模式复杂度参数MC根据(2)式中Ο的候选CU的特性得到。

(5)

(5)式中：i表示图3中候选CU的下标值；N表示所有候选CU的数量，其值为8；ωi是模式权重值。当Ο中的候选CUi是可用时，ki为1，否则ki为0。

本文将CU划分为简单、一般和复杂3种运动类型。这些运动类型所包含的PU模式分别用(6)式所示的Ω，Ψ和Ζ集合表示。其中，非对称inter候选包括SIZE_2N×nU，SIZE_2N×nD，SIZE_nL×2N和SIZE_nR×2N4种PU模式。利用(5)式计算得到MC的值后，再根据(7)式，将当前CU划分为3种运动模式的其中一类，然后再遍历该类中的候选PU模式。

Ω={SKIP,Merge,inter_2N×2N,intra_2N×2N}

Ψ={SKIP,inter,intra,merge}

Z={SKIP,Merge,非对称inter,inter_N×N,

intra_N×N}

(6)

(7)

如果当前CU的深度和参考帧对应位置的CU的深度差值为3，则可跳过当前CU的PU模式遍历，直接进入下一深度的CU的判断。

1.4帧间预测模式快速决策

基于以上分析，本文帧间预测模式快速决策算法流程如下。

①利用(3)式和(4)式得到Depthp，根据Depthp值和表1可得到当前CU的深度范围Mi。

②在Mi区间内，计算当前CU的深度与参考帧中Co-located CU的深度差值Diff。若Diff为3时，则跳过当前CU的所有PU模式遍历；若Diff为0时，根据参考帧中Co-located CU的PU模式来对当前CU的候选PU模式进行删选，而当前CU只需要遍历删选后的候选PU模式；若Diff为1或者2时，首先利用(5)式得到模式复杂度参数(MC)，根据MC的值，将候选PU模式划分为相应的运动类型集合。当前CU遍历相应的运动类型集合中的候选PU模式。

③进入下一深度的CU并重新进行上述操作，直到当前CU的深度大于3为止。

2实验结果

2.1测试指标

在HM14.0中，对本文的改进算法进行了实现，以标准测试序列为编码对象，测试改进算法的性能。标准测试序列参数如表5所示。评估算法的性能指标采用峰值信噪比(peak signal to noise ratio，PSNR)、编码输出比特率和复杂度来衡量。编码输出比特率和复杂度分别使用BDBR(Bjntegaard delta bit rate)(%)和DT(delta time)(%)值来衡量，其中BDBR(%)是平均编码效率差[12]；DT(%)是指以百分比变化的编码时间，正值和负值分别表示与HM14.0中原始算法相比，时间的增加和减少。算法性能测试结果主要包含BDBR和DT变量。率失真曲线图中横轴表示bitrate(kbit/s)，纵轴表示亮度分量的PSNR(dB)值。

以泰克公司的图像质量分析仪PQA600A服务器为测试平台。

表5　测试序列参数

2.2CU深度和PU模式快速决策算法性能测试

表6和图6分别表示CU深度快速决策算法的性能测试结果和率失真曲线图。与HM14.0相比，本文算法在编码输出比特率平均增加0.33%的情况下，平均编码时间减少了18.0%，而率失真代价(rate distortion cost，RD)曲线基本重合。测试数据表明，本文算法能有效地减少CU深度划分的复杂度。根据减少时间的幅度来看，对于低活性序列，如“Traffic”，“BQTerrac”和“SlideEditing”减少的时间普遍高于如“PeopleOnStreet”和“RaceHorses”高活性序列，而其编码效率的损失可忽略不计。实验结果表明，对于低活性序列，可以跳过较多的CU深度，大幅度地降低了编码复杂度。

表6　CU深度决策快速算法性能测试结果

图6　Kimono1序列的率失真曲线图Fig.6　RD curves of “Kimono1” sequence

PU模式快速决策算法的性能测试数据如表7和图7所示。与HM.14.0相比，本文算法在编码输出比特率平均增加1.1%的情况下，平均编码时间减少了39.7%，而RD曲线基本重合。测试数据说明，本文的PU模式快速决策算法大幅度减少了遍历候选PU模式的数量，降低了PU模式决策的复杂度。从测试的数据结果来看，不同的活性序列时间的减少是不同的，如“SlideEditing”减少了52.8%，而“RaceHorses (416×240)”仅减少了31.5%。由于低活性序列的运动特征相对简单，则其需要遍历的PU模式是趋于简单类型的，其所要遍历的候选PU模式较少，减少的时间也较多。

表7　PU模式决策快速算法性能测试结果

2.3帧间预测模式快速决策算法性能测试

帧间预测模式主要包括CU划分、PU模式判断和PU预测参数的计算，而本文主要就CU划分和PU模式判断做了改进。把CU深度和PU模式快速决策算法应用在帧间预测模式决策算法中，得到如表8和图8所示的实验结果。与HM.14.0相比，本文算法在编码输出比特率平均增加1.72%的情况下，平均编码时间减少了46.9%，而RD曲线基本重合。对于慢运动低活性序列，例如“Traffic”,“BQTerrace”和“SlideEditing”，本文算法能减少50%以上编码时间，其中“SlideEditing”序列的编码时间减小了60.8%。而对于快运动高活性序列，例如“RaceHorses”和“PeopleOnStreet”，本文算法也能减少35%以上的编码时间。由于低活性序列运动特征相对简单，则其最终选择的CU深度和PU模式类型都是低深度和简单的模式类型，因而，可以跳过的CU深度和PU候选模型类型也较多，则降低的复杂度也较高。反之，对于高活性序列来说，其降低的复杂度相对较低。测试结果说明，本文帧间预测模式快速决策算法在HEVC编码输出比特率增加很少的情况下，能大幅度地减少编码时间，且视频编码的质量基本不变。

图7　BQTerrace序列的率失真曲线图Fig.7　RD curves of “BQTerrace” sequence

3结论

本文提出的一种帧间预测模式快速决策改进算法充分利用了相邻CU空时域和CU深度之间的相关性，减少了CU深度划分的复杂度；通过分析CU的运动特征和PU模式特性，减少所需遍历候选PU模式的数量。性能测试结果表明，与HM14.0相比，本文提出的算法在编码比特率增加不多，视频质量损失很小的情况下，有效地降低了HEVC编码器的复杂度。

参考文献：

[1]毕厚杰. 新一代视频压缩编码标准——h164/AVC[M].2版.北京:人民邮电出版社,2009：1-3，132-147.

BI Houjie, A new generation of video compression coding standard——h164/AVC[M]. 2nd ed. Beijing: The People’s Posts and Telecommunications Press, 2009：1-3，132-147.

[2]SULLIVAN G J, WIEGAND T. Video compression-from concepts to the H. 264/AVC standard[J]. Proceedings of the IEEE, 2005, 93(1): 18-31.

[3]BROSS B, HAN W J. High efficiency video coding text specification draft 10 [C]// Joint Collaborative Team of ISO/IEC MPEG & ITU-T VCEG). USA: San Jose, 2013: 9-12.

[4]SULLIVAN G J, OHM J, HAN W J. Overview of the high efficiency video coding (HEVC) standard[J]. Circuits and Systems for Video Technology, IEEE Transactions on, 2012, 22(12): 1649-1668.

[5]王晓锋.HEVC 帧间预测与 CU 划分快速算法[D].西安：西安电子科技大学，2014.

WANG Xiaofeng. A fast algorithm of inter prediction and CU partitioning in HEVC[D]. Xi’an:Xi’an Electronic and Engineering University, 2014.

[6]MU F, SONG L, YANG X, et al. Fast coding unit depth decision for HEVC[C]//Multimedia and Expo Workshops (ICMEW). USA: IEEE, 2014: 1-6.

[7]SHEN L Q, LIU Z, ZHANG X P, et al. An effective CU size decision method for HEVC encoders[J]. IEEE Transactions on Multimedia, 2013, 15(2):465-470.

[8]KARCZEWICZ M, CHEN P, JOSHI R L, et al. A hybrid video coder based on extended macroblock sizes, improved interpolation, and flexible motion representation[J]. Circuits and Systems for Video Technology, IEEE Transactions on, 2010, 20(12): 1698-1708.

[9]KIM I K, MCCANN K, SUGIMOTO K, et al. HM9: High Efficiency Video Coding (HEVC) Test Model 14 Encoder Description[C]//Proc. 16th JCT-VC Meeting, Switzerland: JCT-VC, 2014: 10-11.

[10] SHEN L, ZHANG Z, LIU Z. Adaptive inter-mode decision for HEVC jointly utilizing inter-level and spatiotemporal correlations[J]. Circuits and Systems for Video Technology, IEEE Transactions on, USA, 2014: 1709-1722.

[11] 李乐.针对 HEVC 视频编码标准的帧间快速算法研究[D]. 武汉：华中科技大学， 2013.

LI le. Research on fast inter prediction algorithm in HEVC coding standard[D]. Wuhan: Huazhong University, 2013.

[12] BJONTEGAARD G. Calculation of average PSNR difference between RD-curves[EB/OL].[2015-03-26]. http://libra.msra.cn/Publication/2391012/.

A fast inter prediction mode decision algorithm for HEVC based on spatio-temporal correlations

LI Qiang，QIN Yangwei

(Chongqing Key Laboratory of Signal and Information Processing, Chongqing University of Posts and Telecommunications,Chongqing 400065, P.R. China)

Abstract:In order to reduce the complexity of high efficiency video coding (HEVC), a fast inter prediction improved algorithm based on quad-tree analysis is proposed. On the one hand, we can reduce the complexity of the depth-splitting by utilizing the relationship between spatial-temporal information of CU and the depth of it. And we also can make some redundant CU skipped by ensuring the depth interval. On the other hand, it can make sure the different motion characteristics of the PU mode by analyzing the motion features of CU which is in depth interval and the property of PU mode. So it can reduce the number of ergodic candidates of PU mode and greatly reduce the number of the needed rate distortion cost calculations. Compared to HM14.0, the experiments show that the proposed algorithm of HEVC encoder is able to cut the average complexity of HM14.0 encoder by 46.9% at a small bit rate increase. Besides, the quality of encoded video almost remains unchanged.

Keywords：high efficiency video coding; depth splitting; mode decision; rate distortion cost

DOI：10.3979/j.issn.1673-825X.2016.01.002

收稿日期：2015-03-26

修订日期：2015-10-20通讯作者：覃杨微1076467981@qq.com

基金项目：国家自然科学基金(61102131)；重庆市教委科技项目(KJ1400425)

Foundation Items：The National Natural Science Foundation of China(61102131); The Science and Technology Research Project of Chongqing Municipal Education Commission of China(KJ1400425)

中图分类号：TN911.73

文献标志码：A

文章编号：1673-825X(2016)01-0009-08

作者简介：

李强(1968-)，男，湖南人，副教授，主要研究方向为音视频信号处理。E-mail：liqiang@cqupt.edu.cn。

覃杨微(1990-)，女，重庆人，硕士研究生，主要研究方向为视频编码。E-mail:1076467981@qq.com。

(编辑：张诚)