基于运动特征的HEVC帧间模式快速判决算法

金智鹏，代绍庆，王利华

(1.嘉兴职业技术学院　信息技术分院，浙江 嘉兴 314036；2.浙江(嘉兴)微软技术研究中心，浙江 嘉兴 314000)



基于运动特征的HEVC帧间模式快速判决算法

金智鹏1，代绍庆1，王利华2

(1.嘉兴职业技术学院信息技术分院，浙江 嘉兴 314036；2.浙江(嘉兴)微软技术研究中心，浙江 嘉兴 314000)

摘要:为降低HEVC帧间预测编码过程的计算复杂度，提出了一种新的基于运动特征的编码单元(CodingUnits，CU)及预测单元(PredictionUnits，PU)快速判决算法。首先，通过二阶帧差法检测运动剧烈程度，并分析运动特征对CU及PU时域相关性的影响。然后，利用前帧相同位置CU及PU的最优模式预测当前CU的深度范围，并根据运动剧烈程度优化预测范围。最后，根据预测范围跳过和终止部分不必要的CU深度和PU模式，从而加快帧间编码速度。在HM12.0平台上的实验测试表明，该算法在BDPSNR仅降低0.068dB、BDBR只增加1.530%的情况下，提高了48.389%的编码速度。

关键词:HEVC；帧间预测；编码单元(CU)；预测单元(PU)；前帧相同位置；CU深度范围

新一代高性能视频编码国际标准(HighEfficiencyVideoCoding，HEVC)主要面向高清晰度、高帧率、高压缩率的应用需求[1]。相比H.264，HEVC采用了四叉树结构的编码单元(CodingUnits，CU)、预测单元(PredictionUnits，PU)和变换单元(TransformUnits，TU)等众多新技术[2]，将压缩效率提高了一倍。

HEVC将每帧图像按最大编码单元(LargestCodingUnits，LCU)进行划分，每个LCU又可分为一个或多个不同深度(depth)的CU，包括64×64(depth=0)、32×32(depth=1)、16×16(depth=2)、8×8(depth=3)等4种CU模式。每一深度的CU又可按2N×2N、2N×N、N×2N、N×N、2N×nU、2N×nD、nL×2N、nR×2N等8种PU模式进行预测编码[3]。在编码过程中，HEVC采用遍历方式比较上述各种CU及其PU模式的率失真代价，并根据率失真代价确定LCU的最优四叉树结构以及各深度CU的最优PU预测模式，这使得编码器的计算量非常巨大。

为了降低编码复杂度，HEVC采纳了早期编码单元设置(EarlyCodingUnit，ECU)[4]、快速合并模式(FastDecisionforMerge，FDM)[5]、编码标志快速终止(CodedBlockFlag，CBF)[6]、自适应CU深度遍历(AdaptiveCUDepthRange，ACUDR)[7]等一些快速编码算法，以减少编码时间。

为进一步提高HEVC的编码速度，Kim等人[8]通过分析运动矢量差和CBF，提前检测当前PU是否满足Skip模式，并终止后续PU预测模式的遍历计算。Lee等人[9]等利用时域相关性来预测当前CU的深度范围，跳过部分可能性较低的CU模式。Shen等人[10]利用时空相关性以及CU层间相关性来预测当前CU的深度范围，并通过检查运动矢量和率失真代价，提前终止PU模式的计算，以降低编码复杂度。

近来，蒋等人[11]提出了一种基于贝叶斯决策的CU快速判决算法，通过相邻LCU的四叉树结构来预测当前LCU的深度范围，并依据率失真代价和阈值的比较进行CU提前终止判决。晏等人[12]提出了一种CU分级判决快速算法，采用自适应权值量化分析时空相邻CU之间的相关性，并预测当前CU的深度范围，跳过和提前终止不必要的深度计算。

上述快速算法在很大程度上减少了CU遍历范围，但若能结合CU运动特征分类进行CU深度预测，可进一步提高编码速度。本研究将基于CU的运动特征，分类进行CU及PU模式的快速判决，加快HEVC帧间编码速度。

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

1.1CU运动特征检测

在帧间编码过程中，背景和纹理平滑区往往采用大尺寸CU进行编码，以降低编码码率；运动剧烈区域往往采用小尺寸CU进行编码，以提高编码质量。因此，预判CU的运动特征是提高编码速度的关键。

帧间差分法是比较常用且有效的运动对象检测法[13]，即利用前后两帧相同位置处像素的亮度绝对差来衡量运动变化程度。本文采用LCU中4个32×32子CU的二阶亮度绝对差来检测运动对象并衡量其运动幅度。32×32子CU的一阶帧差(FirstDifferenceofCU，FD)计算如下

(1)

式中：FD(cur)表示当前32×32子CU的一阶帧差；fcur(x,y)表示当前32×32子CU的亮度像素值；gcol(x,y)表示前一帧相同位置处32×32子CU的亮度像素值。

但是由于摄像机抖动、镜头运动、光照等影响，一阶帧差的运动对象检测效果并不理想。鉴于由摄像机抖动所产生的帧间差是持续的、大小相近的，因此本文通过计算二阶帧差，滤除由摄像机抖动等因素所带来的扰动和噪声。32×32子CU的二阶帧差(Second Order Difference of CU，SOD)的定义如下

(2)

式中：SOD(cur)表示当前32×32子CU的二阶帧差；FD(col)表示前一帧相同位置处子CU的一阶帧差。

基于上述分析，本文根据二阶帧差SOD来衡量CU的运动特征，并将当前CU分为3种类型：背景平滑区、运动平缓区和运动剧烈区。具体分类如下

(3)

根据编码经验，设置T1=128，T2=3×T1，能取得较佳的编码效果。

1.2运动特征对CU及PU时域相关性的影响

为了掌握相邻两帧之间CU及PU最优模式的相关性概率，分析CU运动特征对CU及PU模式划分的影响，本文采用ClassA～E的15个不同分辨率和运动特性的视频序列进行编码统计。测试平台为HEVC参考软件HM12.0[14]，统计结果如图1和表1所示。

表1中，PCU表示相邻两帧相同位置CU其模式相同的概率，即CU模式相同的面积/图像总面积；PPU表示相同位置PU模式相同的概率。据表1的数据统计可知，运动剧烈区，其相邻两帧之间的PCU平均仅为50.4%；说明其时域相关性较弱，前帧相同位置的最优CU模式不具有参考意义。而对于背景平滑区，其相邻两帧之间的CU及PU模式有着高度的相似性，其PCU平均为82.6%，其PPU平均达89.2%，分别比运动剧烈区高出32.2%和27.7%。因此，对于背景平滑区，可以使用前帧相同位置的最优CU及PU模式来预测当前CU及PU的模式范围；其预测准确性高，且对不同类型的序列都比较稳定。

表1相邻两帧之间CU及PU最优模式的相关性概率 %

从图1可见，各种PU预测模式中，2N×2N模式的使用概率高达84.6%，远高于其他预测模式的使用率。结合表1的统计数据，若当前CU被判为背景平滑区，则当前CU的PU模式更有可能为前帧对应位置的最优PU模式和2N×2N模式；因此，根据一定的判断条件跳过其他冗余PU模式是合理的。

1.3CU划分模式快速判决

步骤1)第1个P帧图像，根据LCU的一阶帧差结果进行运动区和背景区的判断。如果当前LCU的一阶帧差FD>1 920，则判为运动区；否则判为背景区。对运动区遍历计算深度depth=1～3的CU模式，并根据率失真代价选择最优的CU四叉树结构；对背景区，则直接确定depth=0为最佳CU模式。

步骤2)后续P帧图像，先进行二阶帧差计算，判断当前CU的运动特征，并根据CU特征选取相应的编码策略。如果当前LCU中某个32×32子CU的二阶帧差SOD>T2，则判定当前LCU处于运动区，转入步骤3)；否则，判定当前LCU处于背景区，转入步骤4)。

步骤3)运动区。如果当前32×32子CU的二阶帧差SOD>T2，属于运动剧烈区，则设置当前CU的深度遍历范围为depth=1～3。非运动剧烈区，首先获取前帧相同位置处CU的最小深度MinDepth和最大深度MaxDepth，作为当前CU划分的预测范围。然后进一步优化，如果当前32×32子CU的二阶帧差SOD>T1，属于运动平缓区，则修正CU预测范围MinDepth--、MaxDepth++。转入步骤5)。

步骤4)背景区。首先获取前帧相同位置处CU的最小深度MinDepth和最大深度MaxDepth，作为当前CU的预测范围。进一步优化，如果当前32×32子CU的二阶帧差SOD>T1，属于运动平缓区，则MaxDepth++；如果当前32×32子CU的二阶帧差SOD≤T1，属于背景平滑区，则MinDepth--。

步骤5)跳过和终止不必要的CU深度，进行编码计算。根据对当前CU的预测范围，跳过深度depth

步骤6)对LCU中的每个子CU，递归进行步骤2)～5)的判决过程。

1.4 PU预测模式快速判决算法

步骤1)第1个P帧图像，采用PU预测模式全遍历计算，根据率失真代价选择最优的PU预测模式。

步骤2)后续P帧图像，依据二阶帧差计算结果，分运动区、平缓区、背景区等3种情况设置PU模式候选范围。

步骤3)运动区，采用所有PU预测模式全遍历计算。

步骤4)平缓区，采用2N×2N、2N×N、N×2N、和前帧对应位置的最优PU模式组成候选集。

步骤5)背景区，采用2N×2N、前帧对应位置的最优PU模式组成候选集。

步骤6)根据PU模式候选集，计算最优PU模式。如果在2N×2N模式下，残差经量化后的所有系数为0，且运动矢量差值也为0，则认定2N×2N模式为当前CU的最优PU模式，提前终止PU模式候选集的计算。

本文算法CU及PU模式判决过程如图2所示。

2实验结果及数据分析

为测试与分析快速算法的性能，在HM12.0软件平台上按通用测试条件[15]进行测试分析。编码器采用低复杂度配置、低延时编码方案，具体测试参数为：

IPPP，MaxPartitionDepth=4，MotionSearchRange=64；采用快速合并模式判决算法(FastDecisionforMerge，FDM)、快速运动估计搜索算法(EnhancedPredictiveZonalSearch，EPZS)和运动搜索加速算法(FastEncoderDecision，FEN)；编码QP设置为22、27、32和37。

算法性能采用BDBR和BDPSNR[16]指标进行评价，分别表示同样PSNR下码率的损失和相同码率下PSNR的损失情况。采用平均节省时间(AverageSavingTime，AST)表示编码复杂度，其定义如下

(4)

式中：AST表示本文算法相比HM12.0节省的编码时间；Timeproposed和TimeHM12.0分别表示本文算法和HM12.0的总体编码时间。

由表2可见，与HM12.0编码器相比，本文算法的BDBR平均增加1.530%，BDPSNR平均损失0.068dB，编码时间AST平均节省48.389%。这一结果说明，本文提出的HEVC帧间模式快速判决算法具有良好的率失真性能，能大幅降低编码时间。特别是对于背景静止、运动复杂度较低的序列，本文算法可以跳过大量不必要的CU深度和PU模式计算，加速效果尤为显著。

表2本文快速算法测试结果与HM12.0的比较

图3和图4分别为HM12.0和本文快速算法对“BasketballPass”(416×240)序列进行编码的最优CU划分示意图。根据图3和图4的对比可见，仅有5处地方CU划分结构不同，且CU划分深度差都仅为1(如图4中圆圈标识的区域)。这说明本文快速算法的CU划分准确性较高。

为进一步评估本文快速算法的性能，笔者将文献[11]中编码单元裁剪与快速选择算法、文献[12]中时空相关的CU分级判决算法和本文基于运动特征的快速算法进行比较。从表3各种快速算法的率失真和编码时间对比数据可知，与文献[11]提出的算法相比，本文算法的BDBR降低0.65%，编码时间能多节省6%；与文献[12]提出的算法相比，本文算法的编码时间能节省3%，BDPSNR提高0.02dB，BDBR降低0.98%。因此，本文快速算法的综合性能要优于这两种快速算法。其主要原因是本文算法通过二阶帧差法提取运动对象，提高了对不同运动特征的CU及PU的预测针对性和准确性，特别是有效减少了背景平滑区的CU及PU遍历范围。

3小结

根据运动特征对CU及PU时域相关性的影响分析，本文提出了一种新的基于运动特征的CU及PU模式快速判决算法。该算法首先采用二阶帧差法提取运动对象并判定运动剧烈程度，然后根据运动特征采用不同的编码策略。对运动剧烈区，仍以大范围遍历计算为主；对背景平滑区，则主要以前帧相同位置CU及PU的最优模式来预测当前CU的深度范围，从而有效减少了CU及PU的遍历范围。实验结果显示，本文算法提高了48.389%的编码速度，能促进HEVC面向高清视频监控、视频会议以及低复杂度实时编码等领域的应用。

参考文献：

[1]沈燕飞，李锦涛，朱珍民，等. 高效视频编码[J]. 计算机学报，2013，36(11)：2340-2355.

[2]CORREAG，ASSUNCAOP，AGOSTINIL，etal.Performanceandcomputationalcomplexityassessmentofhigh-efficiencyvideodecoders[J].IEEEtransactionsoncircuitsandsystemsforvideotechnology，2012，22(12)：1899-1909.

[3]刘昱，胡晓爽，段继忠. 新一代视频编码技术HEVC算法分析及比较[J]. 电视技术，2012，36(20)：45-49.

[4]CHOIK，PARKSH，JANGES.CodingtreepruningbasedCUearlytermination[C]//Proc.JCT-VC6thMeeting.Torino：JCT-VC， 2011：14-22.

[5]LAROCHEG，POIRIERT，ONNOP.Encoderspeed-upforthemotionvectorpredictorcostestimation[C]//Proc.JCT-VC8thmeeting.SanJose，CA，USA：JCT-VC，2012：121-128.

[6]GWEONRH，LEEYL，LIMJ.EarlyterminationofCUencodingtoreduceHEVCcomplexity[C]//Proc.JCT-VC6thmeeting.Torino：JCT-VC，2011：1-5.

[7]LIX，ANJC，GUOX，etal.AdaptiveCUdepthrange[C]//Proc.JCT-VC5thMeeting.Geneva：JCT-VC，2011.

[8]KIMJ，YANGJ，WONK，etal.EarlydeterminationofmodedecisionforHEVC[C]//Proc.PictureCodingSymposium(PCS).Kraków，Poland：PCS2012：449-452.

[9]LEEHS，KIMKY，KIMTR，etal.Fastencodingalgorithmbasedondepthofcoding-unitforhighefficiencyvideocoding[J].Opticalengineering，2012，51(6)：56-61.

[10]SHENLiquan，LIUZhi，ZHANGXinpeng，etal.AneffectiveCUsizedecisionmethodforHEVCencoders[J].IEEEtransactionsonmultimedia，2013，15(2)：465-470.

[11]蒋刚毅，杨小祥，彭宗举，等. 高效视频编码的快速编码单元深度遍历选择和早期编码单元裁剪[J]. 光学精密工程，2014，22(5)：1322-1330.

[12]晏轲，滕国伟，胡锦雯，等. 一种基于时空相关性的编码单元深度快速分级判决算法[J]. 光电子·激光，2014，25(1)：156-162.

[13]姚春莲，郭克友. 一种利用帧差信息的实时运动对象检测算法[J]. 计算机工程与应用，2011，47(8S)：390-393.

[14]JCT-VC．HEVCReferenceSoftwareHM-12.0 [EB/OL][2014-09-01].https//hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/tags/HM-12.0.

[15]BOSSENF.JCTVC-L1100,Commontestconditionsandsoftwarereferenceconfigurations[S].2013.

[16]PATEUXS，JUNGJ.Anexceladd-inforcomputingbjontegaardmetricanditsevolution[S].2007.

金智鹏(1982— )，硕士，副教授，主要研究方向为低复杂度视频编码与传输、图像质量评价等；

代绍庆(1972— )，硕士，副教授，主要研究图像压缩、图像处理与模式识别；

王利华(1977— )，高级工程师，主要研究网络视频测试与传输技术。

责任编辑：时雯

FastintermodedecisionalgorithmforHEVCbasedonmotionfeatures

JINZhipeng1，DAIShaoqing1，WANGLihua2

(1.Information Technology Branch Institute，Jiaxing Vocational Technical College，Zhejiang Jiaxing 314036，China；2. Zhejiang(Jiaxing) Microsoft's Technology Research Center，Zhejiang Jiaxing 314000，China)

Keywords:HEVC；interprediction；codingunits(CU)；predictionunits(PU)；co-locatedposition；CUdepthrange

Abstract:ToreducethecomplexityofHEVCinterpredictioncoding，anovelfastCU(CodingUnits)andPU(PredictionUnits)modedecisionalgorithmbasedonmotionfeaturesisproposed.Firstly，todetectmovementintensitythroughsecondorderdifferencemethod，andtoanalyzetheimpactofmotionfeaturestoCUandPUtemporalcorrelation.Secondly，topredictthecurrentCUdepthrangeandPUmodeusingthebestCUandPUmodeoftheco-locatedpositioninthepreviousframe.Then，tooptimizethepredictedrangeaccordingtothemotionfeatures.Finally，inordertospeeduptheinterpredictioncoding，toskipandterminationofsomeunnecessaryCUandPUmodeaccordingtothepredictedrange.ExperimentalresultsonHM12.0showthattheproposedalgorithmcanreduceencodingtimefor48.389%，whileBDPSNRlossisonly0.068dBandBRBRincrementis1.530%．

中图分类号：TN919.8

文献标志码:A

DOI：10.16280/j.videoe.2016.01.003

基金项目：浙江省教育厅科研计划项目(Y201431212)；嘉兴市科技计划项目(2014AY11003)

作者简介：

收稿日期：2014-9-12

文献引用格式：金智鹏,代绍庆,王利华.基于运动特征的HEVC帧间模式快速判决算法[J].电视技术,2016，40(1)：13-18.

JINZP，DAISQ，WANGLH.FastintermodedecisionalgorithmforHEVCbasedonmotionfeatures[J].Videoengineering,2016,40(1)：13-18.