基于时域相关性的快速HEVC帧间模式判决方法

刘 娟，钟国韵，王 蕾，刘梅锋，徐洪珍

（东华理工大学 软件学院，江西 抚州 344000）

基于时域相关性的快速HEVC帧间模式判决方法

刘 娟，钟国韵，王 蕾，刘梅锋，徐洪珍

（东华理工大学 软件学院，江西 抚州 344000）

高效率视频编码（HEVC）相比目前的国际视频编码标准H.264/AVC，在压缩率方面有了较大的提高，但也带来了巨大的编码计算复杂度。为了降低HEVC的编码计算复杂度，提出了一种快速HEVC帧间模式判决方法。统计并分析了相邻两帧之间对应块的编码单元（CU）和预测单元（PU）的时域相关性，在此相关性基础上，跳过了一些冗余CU分割层和PU预测模式，CU层最多只取两种PU预测模式，从而大大减少了所需要进行的率失真代价计算的数量。实验结果显示，与HM7.0相比，该方法在仅损失了0.21%～1.66%的压缩率和0.01～0.09 dB的峰值信噪比的前提下，降低了52.3%～63.5%的编码时间。

效率视频编码；编码单元；预测单元；模式判决

目前的国际视频编码标准H.264/AVC[1]是由两大国际标准化组织ITU-T和ISO/IEC的联合视频小组（JVT）开发的。该视频编码标准采用的最大的块尺寸为16×16，随着高清视频的发展，国内外学者发现该块尺寸已不能适应高清视频高效编码的需求[2]。为此，两大国际组织专门成立了视频编码联合协作组JCT-VC，以开发下一代国际视频编码（HEVC）标准[3-5]。该标准采用最大尺寸为64×64的编码单元，其目标为在保持视频质量不变的基础上，压缩率比H.264/AVC标准提高一倍。

相比H.264/AVC，HEVC最大的改进是采用了以下3种技术：编码单元（CU）、预测单元（PU）和变换单元（TU）。HEVC采用了4种CU尺寸和8种PU预测模式，在每种CU尺寸和PU模式下均对其进行率失真代价值的计算，因此，总体的计算复杂度是巨大的。若要将HEVC应用于实际的实时视频通信系统中，降低其计算复杂度是很必要的。针对H.264/AVC，近几年国内外的学者提出了一些快速模式判决的方法。如干宗良等[6]提出了一种基于先验预测的帧间编码模式选择快速算法。Li等[7]利用基本层和提高层之间的相关性跳过提高层的许多率失真代价的搜索数量来降低编码计算复杂度。C.Grecos等[8]提出了根据帧内/帧间预测和代价函数的单调性，减少了所需进行的帧间预测模式数量。A.Yu等[9]提出了包含跳过、宏块和子宏块等3层的分等级结构，每一层采用不同的运动估计的复杂度，从而降低了编码的计算复杂度。Ates等[10]提出一个联合率失真和计算复杂度的优化框架，仅对最佳的分块进行运动估计以降低编码计算复杂度。Kim等[11]根据前一帧对应块的编码模式和率失真代价分布模式，提出了自适应的快速模式判决方法。文献[12-13]中，通过在4×4块归一化运动向量场得到运动向量一致性，判决当前有可能出现的分块模式，从而跳过其他一些不太可能出现的模式。M.Knesebeck等[14]利用16×16块与其潜在最优的分块之间率失真的相关性，跳过其他分块的率失真代价计算。Zhao等[15]利用空、时域相邻分块之间的相关性，构建最优模式列表以节省其他模式的率失真代价的计算。文献[16]通过利用当前块与参考块之间相位相关性，从候选预测模式中仅挑选一种最佳预测模式进行预测。P.Lee等[17]利用模糊逻辑的方法，通过对前一帧对应块预测模式的分布情况进行分析，根据分析结果判决当前块对某种模式进行率失真代价计算的必要性，从而跳过了一些不必要的预测模式。

上述方法均取得了较好效果，但均根据H.264/AVC的宏块结构设计，并不适合HEVC。本文将分析相邻两帧间时域的相关性，根据该相关性，即相邻两帧之间CU及PU的相似度，跳过当前最大CU（LCU）中各种尺寸CU中的多个不太可能出现的PU模式，使得每个CU中最多只有两种PU模式的率失真代价需要计算，从而减少编码的计算复杂度。

1 HEVC帧间预测模式判决

1.1 HEVC中的CU分割方式

HEVC中，一幅图片可以分为多个片，而一个片可以由多个最大编码单元（LCU）组成。LCU的尺寸最大可以设置为64×64，它的概念类似于H.264/AVC中的宏块的概念。LCU尺寸为64×64，该尺寸CU处于第一层，它可分为4个相同尺寸的32×32的CU分块。同样，1个32×32尺寸的CU分块可以分为4个相同尺寸的16×16的CU分块，直到8×8尺寸的CU分块。

1.2 HEVC中PU预测模式

伴随着CU，HEVC同时也介绍了预测单元（PU），该单元与预测过程相关。PU只用在树梢节点CU中，因此，PU尺寸由CU决定，PU可等于或小于CU的尺寸。但它的形状并不一定为正方形，该形状的设计能使它的边界更加接近实际视频图像中对象的边界。图1显示了HEVC中定义的8种PU预测模式。

图1 HEVC中定义的8种PU模式

2 基于时域相关性的快速帧间模式判决

从上一节可以看出，HEVC对每种CU尺寸和PU预测模式下的率失真代价值均进行了计算。因此，这样的遍历带来了巨大的计算量。为了降低HEVC的帧间预测模式判决的计算复杂度，国内外学者纷纷向HEVC标准制定大会提交了提案，目前的HEVC编码标准中，在模式判决过程中加入了SKIP模式，跳过一些子树上的率失真代价计算[18]；也提出了当编码宏块标准cbf为0时（此时CU的量化后AC系数均为0）跳过除PART_2N×2N外的其他模式的机制[19-20]。这些算法均已经加入到了HEVC最新的参考软件HM7.0中。然而，若要将HEVC应用于实际的实时通信系统，其编码计算复杂度必须进一步降低。

受文献[17]针对H.264/AVC的算法的启发，本文利用相邻帧之间CU分割方式及PU预测模式的时域相关性，跳过一些当前块的CU分割方式和PU预测模式，从而降低HEVC的编码计算复杂度。

2.1 时域相关性及PU模式统计分析

为了分析相邻帧之间时域相关性及各种PU模式之间的关系，首先统计相邻两帧之间的CU分割方式及PU预测模式的相似程度和每种尺寸CU中的各种PU模式的分布情况。

2.1.1 相邻帧之间时域相关性统计分析

为了统计相邻两帧的对应位置块之间CU分割方式及PU预测模式的相似度，分别定义了两个概率：PCU和PPU，PPU代表相邻两帧对应块之间CU相同的概率，而PPU代表相同的CU下PU模式相同的概率，具体定义为

式中：Asc是相邻两帧对应块相同CU的面积；Atc是总的CU的面积；Asp是相邻两帧对应块相同的CU中，有着相同PU模式的块的面积；Atp是总的PU的面积。

为了统计实际视频中相邻两帧之间的CU及PU的相似度，采用了6个不同分辨率和运动特性的视频序列，在HEVC参考软件HM7.0中进行了统计，结果如表1所示。

从表1中的统计结果可以看出，相邻两帧之间的CU分割方式和PU预测模式有着高度的相似性，因此，本文拟利用该相关性跳过当前块的部分冗余的CU分割方式和PU预测模式是合理的。

表1 相邻两帧之间的CU及PU的相似概率

2.1.2 PU模式分布情况

为了统计各种尺寸下CU的PU预测模式分布情况，对6个视频序列进行了统计，发现其中的PART_2N×2N具有最高的出现概率，并且远高于其他模式出现的概率。表2列出了各种视频下各种尺寸该模式最优的概率。从表2可以看出，在各层CU的遍历中，其中PU预测模式PART_2N×2N最大，则率失真代价值可能最小，因此，本文将该模式设为最佳的PU预测模式。

表2 各种尺寸下PU模式PART_2N×2N的概率

2.2 快速HEVC帧间模式的分析及其判决方法的提出

由第1节可知，对于当前的LCU，编码器将对其各种尺寸的CU均要进行遍历，而每一块CU在前一帧对应位置已编码的CU尺寸只有一种，于是，当前CU分块与前一帧对应CU尺寸大小之间关系存在3种情况：当前CU尺寸大于、等于和小于前一帧对应块CU的尺寸，因此，必须在3种情况下分别讨论分析当前CU的帧间模式判决方法。

2.2.1 当前CU尺寸小于对应CU尺寸

当前CU尺寸小于对应CU尺寸时，如图2所示，此时当前CU尺寸为对应块的1/2（指的是边长），块E可能对应的位置为A、B、C或者D。

图2 当前CU尺寸小于对应CU尺寸时的相互关系

当对应CU分块的PU模式为PART_nL×2N时，如图3a所示，则当前CU分块的PU模式应为PART_N×2N；若对应CU分块的PU模式为PART_2N×nU时，如图3b所示，则当前CU分块的PU模式应为PART_2N×N。

图3 当前CU尺寸小于对应CU尺寸时，PU模式的对应关系

因此，当前CU分块尺寸小于对应CU分块尺寸时，总的算法设计如下：

1）当前CU分块尺寸为对应块尺寸的1/2时，设区域A和E左上角的坐标分别为（x，y）和（s，t），则区域B、C和D的坐标分别为（x+l，y）、（x，y+l）和（x+l，x+l），其中l为当前CU分块的边长。定义一个当前CU分块尺寸为对应块尺寸的1/2时，两者关系的总集合Ω1为

式中：Mw指的是对应块的PU预测模式；w表示模式的序号；n表示对应CU分块PU模式数量（如64×64尺寸为3，而32×32和16×16尺寸为7）。式（3）中①部分指的是块E分别对应块A、B、C和D的所有情况的集合，②部分指的是对应CU可能出现的所有PU预测模式的集合。设CO为对应CU分块位置和PU模式的其中一种情况，CO∈Ω1。定义8种条件的集合为

式中：“⋂”和“⋃”分别表示交集和并集；PUco表示对应CU分块的PU模式。此时最佳PU模式为

式中：Mb表示当前CU分块最佳PU模式（除PART_2N×2N外）。

2）当前CU尺寸为对应CU尺寸的1/4时，CU分块E只遍历PART_2N×2N模式。

3）当前CU尺寸小于对应CU尺寸的1/4时，CU分块E被跳过。

2.2.2 当前CU尺寸等于对应CU尺寸

当前CU分块尺寸等于对应CU块尺寸时，根据表1的统计结果，当前CU分块的PU模式直接采用对应CU分块的PU模式。

2.2.3 当前CU尺寸大于对应CU尺寸

当前CU尺寸大于对应CU尺寸时，CU分块可能的PU模式包括PART_2N×2N，PART_2N×N，PART_N×2N，PART_nL×2N，PART_nR×2N，PART_2N×nU和PART_2N× nD等，除模式PART_2N×2N外，其他模式则必须通过对应块中各个CU分块的尺寸和PU预测模式进行判决。经过大量的实验统计，本文用以下的方法进行归类：将6种模式（除PART_2N×2N外）分为垂直和水平2种，按照对应块中具体的CU和PU分布情况，判决当前CU分块的PU模式应为垂直或水平模式中的哪一种。

将对应块中垂直和水平模式CU所占的面积Av和Ah分别定义如下

式中：p和q分别为对应块中垂直和水平PU模式的CU数量；Mi和Ni分别为第i个垂直和水平PU模式的CU分块的边长。

为了进一步判决当前CU分块的PU模式，本文采用集合的方式来定义对应块中CU的分块尺寸及其PU模式分布情况

式中：CPAu，v，w指的A块区域中所有的CU分块尺寸和PU预测模式；u指的是A块继续四叉树划分的深度，当u为0时，指的是A块不进行四叉树划分；v指的是四叉树划分后其中的CU块序号；w指的是PU模式的序号。CPBu，v，w，CPCu，v，w和CPDu，v，w的意义同CPAu，v，w。因此，ΩA，ΩB，ΩC和ΩD分别指的是块A，B，C和D中CU分块方式和PU预测模式的所有可能组合的集合。同理，可以定义整个对应块所有的CU分块和PU预测模式的集合为

式中：u∈（1，m）是由于对应块中CU尺寸小于当前CU分块，将进行四叉树划分，因此u是从1开始的。

对于A块，设Aʹ为当A块未进行四叉树划分并PU模式为PART_2N×2N时的集合，因此

于是，A块中除了Aʹ其他的情况为Aʺ，Aʺ可以由以下公式得到

同理可以分别得到B、C和D块的Bʺ、Cʺ和Dʺ

根据式（8）～式（17），设定7种条件，分别为

对6种视频进行上述7种条件下出现6种PU预测模式的概率统计，由于各种视频及CU尺寸下总体趋势类似，为了简明清晰，本文只给出各种视频及CU尺寸下各种条件下平均的PU模式分布情况，如图4所示。从图4可以看出，条件Con1～Con6下分别出现的模式1～6的概率最大，而Con7条件下则不能判决哪种模式概率最大。图5显示了条件Con1～Con7下各种出现概率最大的PU预测模式（除模式PART_2N×2N外）。

图4 各种CU尺寸、条件下PU模式分布

图5 条件Con1～Con7下出现概率最大的PU模式

根据图4和图5的结果，当前CU尺寸大于对应块中CU尺寸时，本文具体算法设计如下：

1）当前块尺寸为64×64时，最佳PU模式为

2）当前块尺寸为32×32或16×16时，设此时对应块中CU分块模式和PU预测模式为Ωco，则最佳PU模式为

3 实验结果及分析

由于目前未有对HEVC最新参考软件HM7.0中对应模式判决进行改进的算法报导，因此，本文将所提出的算法与HM7.0进行比较。采用了6种视频序列：Basket⁃ball-Drill，Partyscreen，Fourpeople，Johnny，Kimono1和BQ⁃Terrace。测试其中的前100帧，图像组结构（GoP）设为“IPPP”，最大分块深度（MPD）设为4，即CU尺寸为64× 64，32×32，16×16和8×8等4种，运动估计采用快速搜索方法，搜索范围设为64，时能量化、变换跳过（SKIP）方法，内部比特深度设为10 bit，使能其他所有的编码工具：样值自适应补偿（SAO）、自适应环路滤波（ALF）、基于亮度的色度帧内模式（LMC）、非正方形变换（NSQT）和非对称运动分块（AMP）等。QP值取22，27，32和37。为了比较本文算法和HM7.0算法之间的性能，本文采用了以下3种指标

式中：Bitratepro和Bitrateref分别表示本文算法和HM7.0的比特率；ΔBitrate表示本文算法相比HM7.0增加比特率的百分比；PSNRpro和PSNRref分别表示本文算法和HM7.0的峰值信噪比（PSNR），该性能指标代表了视频的客观质量；ΔPSNR表示本文算法相比HM7.0提高的视频质量；Timepro和Timeref分别表示本文算法和HM7.0的总体编码时间；ΔTime表示本文算法相比HM7.0增加编码时间的百分比。表3显示了本文算法相比HM7.0各方面性能的比较结果。从表中可以看出，相比HM7.0，本文算法在损失了0.21%～1.66%的压缩率和0.01～0.09 dB的视频质量的前提下，节省了52.3%～63.5%的编码时间。

4 结论

本文首先统计分析了相邻两帧之间CU分块方式和PU预测模式的相似性和各种CU尺寸下的PU模式分布情况，接着将当前块与对应块之间尺寸大小关系分为大于、等于和小于3种情况讨论，每种情况下，分别根据对应块中CU分块的PU预测方式情况，利用集合的方法分析并统计了当前块最有可能出现最小率失真代价值的PU预测模式，并根据统计结果设计了各种情况下帧间模式方法。实验结果显示，与HM7.0相比，本文提出的方法在比特率和视频质量损失很小的情况下，节省了52.3%～63.5%的编码时间。

表3 本文算法与HM7.0在比特率、视频质量和编码时间方面的比较

[1]WIEGAND T，SULLIVAN G，BJONTEGAARD G，et al.Overview of the H.264/AVC video coding standard[J].IEEE Trans.Circuits Syst.Video Technol.，2003，13（7）：560-576.

[2] LEE K，ALSHINA E，MIN J.Technical considerations for ad hoc group on new challenges in video coding standardization[EB/OL]. [2013-08-02].http://www.doc88.com/p-485729021575.htm l.

[3]UGUR K，ANDERSSON K，FULDSETH A，et al.High performance，low complexity video coding and the emerging HEVC standard[J]. IEEE Trans.Circuits Syst.Video Technol.，2010，20（12）：1688-1697.

[4]刘梅锋，陆玲.新一代视频编码标准HEVC变换方法的研究[J].电视技术，2012，36（1）：1-5.

[5]李元，何小海，钟国韵，等.基于时域相关性的HEVC快速帧内预测算法[J].电视技术，2012，36（9）：1-4.

[6] 干宗良，齐丽娜，朱秀昌.H.264中基于先验预测的帧间编码模式选择算法研究[J].电子与信息学报，2006，28（10）：1883-1887.

[7] LIH，LI Z，WEN C.Fastmode decision algorithm for inter-frame coding in fully scalable video coding[J].IEEE Trans.Circuits Syst.，Video Technol.，2006，16（7）：889-895.

[8] GRECOS C，YANG M.Fast mode prediction for the baseline and main pro f les in the H.264 video coding standard[J].IEEE Trans. Multimedia，2006，8（6）：1125-1134.

[9] YU A，MARTIN G，PARK H.Fast inter-mode selection in the H.264/AVC standard using a hierarchical decision process[J].IEEE Trans.Circuits Syst.Video Technol.，2008，18（2）：186-195.

[10] ATES H，ALTUNBASAK Y.Rate-distortion and complexity opti⁃mized motion estimation for H.264/AVC video coding[J].IEEE Trans.Circuits Syst.Video Technol.，2008，18（2）：159-171.

[11] KIM S，HO Y.Fastmode decision algorithm for H.264 using statis⁃tics of rate-distortioncost[J].Electron.Lett.，2008，44（14）：849-850.

[12] LIU Z，SHEN L，ZHANG Z.An efficient intermode decision algo⁃rithm based on motion homogeneity for H.264/AVC[J].IEEE Trans. Circuits Syst.Video Technol.，2009，19（1）：128-132.

[13] SHEN L，LIU Z，ZHANG Z，et al.Fast inter mode decision using spatial property ofmotion field[J].IEEE Trans.Multimedia，2008，10（6）：1208-1214.

[14] KNESEBECK M，NASIOPOILOS P.An efficient early-termination mode decision algorithm for H.264[J].IEEE Trans.Consum.Elec⁃tron.，2009，55（3）：1501-1510.

[15] ZHAO T，WANG H，KWONG S，et al.Fastmode decision based on mode adaptation[J].IEEE Trans.Circuits Syst.Video Technol.，2010，20（5）：697-705.

[16] PAUL M，LIN W，LAU C，et al.Direct intermode selection for H.264 video coding using phase correlation[J].IEEE Trans.Image Process.，2011，20（2）：461-473.

[17]LEE P，KUO K，HUANG S，et al.Codingmode determination using fuzzy reasoning in H.264 motion estimation[J].IET Signal Process.，2011，5（2）：242-250.

[18] TAN H，LIU F.On fast coding tree block and mode decision for high-efficiency video coding（HEVC）[C]//Proc.IEEE International Conference on Acoustics，Speech and Signal Processing（ICASSP）. Kyoto：IEEE Press，2012：825-828.

[19]KIM J，YANG J，WON K，et al.Early determination ofmode deci⁃sion for hevc[C]//Proc.29th Picture Coding Symposium.Poland：IEEE Press，2012：449-452.

[20] GWEON R，LEE Y.Early termination of CU encoding to reduce HEVC complexity[J].IEICE Trans.Fundamentals of Electronics, Communications and Computer Sciences，2012（7）：1215-1218.

Fast Inter-mode Decision for HEVC Based on Tem porally Correlation

LIU Juan，ZHONG Guoyun，WANG Lei，LIU Meifeng，XU Hongzhen
（College of Software，East China Institute of Technology，Jiangxi Fuzhou 344000，China）

High efficiency video coding（HEVC）achieves higher compression ratio than the current international video coding standard H.264/AVC.However，it has brought about tremendous computational complexity than H.264/AVC.In order to reduce this complexity，a fast inter-mode decision for HEVC is proposed in this paper.The temporally correlation of coding unit（CU）and prediction unit（PU）between two adjacent frames is counted and analyzed.Based on this correlation，at most two PU prediction modes are selected for Rate Distortion（RD）cost calculation to skip the other modes，greatly reducing the number of the needed RD cost calculations.The experiment results show that the proposed algorithm reduces 52.3%～63.5%coding time with only 0.21%～1.66%compression ratio loss and 0.01～0.09 dB peak signal-to-noise ratiodegradation，compared to HM7.0.

high efficiency video coding（HEVC）；coding unit（CU）；prediction unit（PU）；mode decision

TN919.81

A

刘 娟（1989—），女，硕士生，研究方向为多媒体通信；

钟国韵（1979—），本文通讯作者，博士，讲师，研究方向为多媒体通信；

王 蕾（1979—），副教授，研究方向为图像与图形处理；

刘梅锋（1979—），讲师，研究方向为电路与系统、视频编码；

徐洪珍（1976—），博士，副教授，研究方向为软件理论。

�� 雯

2013-08-16

【本文献信息】刘娟，钟国韵，王蕾，等.基于时域相关性的快速HEVC帧间模式判决方法[J].电视技术，2014，38（13）.

国家自然科学基金项目（61262001）；江西省自然科学基金项目（20114BAB201043）；江西省科技支撑计划项目（20112BBE50048）