HEVC帧间快速运动估计及计算复杂度分析

陈 红，齐 华

(西安工业大学 电子信息工程学院，西安 710021)



HEVC帧间快速运动估计及计算复杂度分析

陈 红，齐 华

(西安工业大学 电子信息工程学院，西安 710021)

为了降低高性能视频编码标准中帧间运动估计的高计算复杂度，提出了一种基于运动矢量相似性的运动估计快速终止算法.该算法利用视频序列中同一个对象的运动矢量相似性，对当前编码单元的分割方式进行了选取，提前终止了部分可能性较低的复杂分割模式的运动估计.结合运动相似区域的编码单元，在分解后的下一递归深度中对小块预测单元划分的运动估计进行了裁减.实验结果表明：所提方法与高性能视频编码标准参考代码中的标准算法相比，在低延时编码配置下，编码时间和峰值信噪比分别降低了41.79%和0.052 dB.随机访问编码配置下，编码时间和峰值信噪比分别降低了41.98%和0.041 dB.运动估计的计算量减小，计算复杂度降低.

高性能视频编码标准；运动估计；运动差异; 计算复杂度

高效视频编码(High Efficiency Video Coding， HEVC)于2013年被正式确定为最新一代的国际视频压缩编码标准，主要面对高清、超高清视频应用[1].HEVC编码沿用了H.26X编码采用的基于块的混合编码框架，在此基础上对很多编码技术做了突破性的改进[2].主要包括编码单元(Coding Unit，CU)中运动融合、递归式四叉树块划分结构、高精度运动补偿及自适应环路滤波等.在相同的编码质量条件下，HEVC编码对视频数据的压缩能力是H.264/AVC编码的2倍[3]，但同时也导致编码复杂，不利于HEVC编码应用于实时视频，因此在不降低编码性能的前提下降低编码复杂度是HEVC编码能否得到广泛应用的关键.

运动估计作为视频编码的核心技术，占用了 50%以上的编码时间，寻找快速高效的运动估计算法一直是视频编码领域研究的一个热点问题.文献[4]利用光流法计算金字塔运动发散(Pyramid Movement Divergence，PMD)的特征值决定CU单元的分割情况，在一定程度上降低了复杂度.文献[5]利用 Bayes 决策规则判定当前 CU 单元是否进行划分.文献[6]提出了一种小块预测单元(Predicting Unit，PU)划分快速算法，检查Cbf标志位以及当前PU单元的率失真(Rate Destortion，RD)代价，若这两个值符合一定条件，则提前终止下一个PU单元的预测.文献[7]采用预测残差的特征计算预测块和原始块的平均平方误差，实现了部分 CU 单元划分的提前终止.文献[8]基于视频内容相关性和时域、空域相邻 CU 单元预测模式，结合RD 代价信息对当前 CU 单元的预测模式进行了预测，对部分冗余的预测模式进行裁剪.文献[9-10] 通过前后帧的变化情况来判断运动剧烈程度，以快速判定编码模式，取得了较高的编码效率.由以上可见，根据当前CU单元自身的特征如RD代价、运动信息，提前终止CU单元或者PU单元的进一步划分，是一种切实有效的方法.

基于此，文中利用运动矢量相似性，提出了一种HEVC编码帧间运动估计快速终止算法，根据当前CU单元的运动矢量差异性，合理选取当前CU单元的分割方式，减少运动估计的计算量.通过对当前CU单元的运动矢量绝对偏差的平均值进行计算，确定出当前CU单元的运动差异性，若运动差异小于给定阈值，则当前CU单元位于运动相似区，在下一递归深度的CU单元中非块大小为2N×2N(N为2的幂次方，无量纲)分割模式的运动估计被裁减，提前终止运动估计，降低HEVC编码复杂度.

1 HEVC编码中帧间复杂度分析

1.1 HEVC编码中CU单元划分方式

HEVC编码中编码树单元(Coding Tree Unit，CTU)为最大编码单元，根据涵盖图像区域复杂度，通过递归，各个CTU单元划分成较小的编码单元，最多可以划分4层，这样的划分模式称为四叉树划分[11]，如图1所示.图1中split-flag为划分标志位；CU-Size为编码单元大小；CU-Depth为编码单元深度；N0、N1、N2、N3为划分后编码子单元大小；CU0、CU1、CU2、CU3分别为不同深度的编码单元.

图1 CU单元的四叉树结构

若CU单元深度为0 层时，CU单元的大小与CTU单元相同，为64×64；当深度为1 层时，一个CTU单元可划分为4个CU1单元，每个CU1单元大小为32×32，以此类推，每个CU2单元大小为16×16，CU3单元大小为8×8，在CU单元的四叉树结构中，深度最大为3 层.CU单元可继续被划分为PU单元，每个PU单元预测信息相同,包括运动矢量、预测模式及参考帧等[12].图2为帧内预测和帧间预测情况下PU单元划分方式.图2中N、U、D、L、R、n为PU单元的划分尺寸参数.每个CU单元，按划分方式的不同，可含有1个、2个或者4个PU单元，对于帧间类型，CU单元共有8种划分方法[13].使用变换单元(Transform Unit，TU)进行残差变换，TU单元可有4×4、8×8、16×16或32×32等划分模式.

图2 PU单元划分模式

1.2 帧间编码复杂度分析

HEVC编码使用全深度搜索方法以获取最优块划分方式，每个CU单元分别进行2种帧内划分和8种帧间划分，判定最佳划分的条件是计算该划分下的总RD代价.以误差平方和(Sum of Square Error,SSE)作为帧间运动估计中最佳划分的RD代价为

JSSE=(SSEL+ωchroma×SSEC)+λSSE×Bits

(1)

式中：JSSE为误差平方和；SSEL和SSEC分别为亮度和色度分量的误差平方和；λSSE为拉格朗日乘子；ωchroma为色度分量加权因子；Bits为编码后的码流大小.

假定编码中不考虑 Skip 模式 CU 单元不分解的情形，从最大编码单元(Largest Coding Unit,LCU)分解为最小尺寸的CU单元所需计算的RD代价次数为3 068次.

对于每一次计算RD代价，均需进行变换、量化、反变换、反量化及熵编码等过程，在一幅分辨率为1 920×1 080 pixel的视频图像中包含超过500个块大小为64×64的LCU.由此可见，HEVC编码的帧间预测因CU单元、PU单元的引入使得编码器的复杂度过高.

2 HEVC编码帧间运动估计快速终止算法

2.1 CU单元的运动差异程度衡量

同一运动对象区域中CU单元的运动矢量分布相似，这是由于视频序列中同一对象具有相似的运动矢量.为此，对于这些区域进行运动估计时不需要分割成较小的PU单元，这是由于运动矢量通过大块PU单元运动估计即可得到，且较为准确.对运动变化剧烈区域内的CU单元，分割成较小块的PU单元将有助于搜索到正确运动矢量.若不划分运动特征相似区域的CU单元，运动估计就能提前终止，因此减少了较小尺寸CU单元的运动估计次数.

通过分析当前运动矢量差异程度可以衡量当前编码块是否处于运动相似区域，测试模型HM中运动矢量以4×4块大小为单位进行存储.某个视频区具有N个4×4块，运动矢量在水平和垂直方向的差异程度分别为

(2)

(3)

式中：Hx,Hy分别为运动矢量在水平和垂直方向的差异程度；vx(i)和vy(i)分别为4×4块在水平和垂直方向的运动矢量.当Hx和Hy小于某阈值时，则判定当前N个4×4块的视频区域属于运动相似区域，且Hx和Hy的值越小，说明该区域的运动特征越相似.通过计算空域相邻CU单元和当前CU单元的运动差异程度，可以判定当前CU单元是否要划分为更小块的CU单元进行运动估计.

2.2 运动估计快速终止准确度统计分析

CU单元进行各PU单元分割模式的运动估计后，若当前CU单元的最佳预测模式是2N×2N，则所有4×4块的运动矢量是一致的，若最佳预测模式是小块PU单元的运动估计，每个PU单元的运动矢量可能不同，则以4×4块为单位存储的运动矢量呈现一定的差异性.根据式(2)～(3)，当前CU单元进行运动估计后的运动矢量在水平和垂直方向的差异分别为

(4)

(5)

其中N为当前CU单元的4×4块的个数.当前CU单元进行运动估计后的运动矢量在水平和垂直方向的总差异为

vart=varx+vary

(6)

vart的值越大则当前CU单元的各个部分的运动差异越大，进行小块PU单元划分的可能性越高.因此当vart足够小，小于一定阈值varth时，当前

CU单元位于运动相似区域，各个部分的运动矢量的相似度很高，进行小块PU单元划分的可能性小，varth设为 0.2.

为了准确分析此阈值下裁减小块PU单元划分的运动估计，通过编码实验分析vart的分布.编码配置采用随机访问编码，CU单元在不同vart下的最佳预测模式为2N×2N和非2N×2N，vart值分布情况见表1.表1～4中序列为不同分辨率的测试视频序列.

表1 vart值分布情况统计表

从表1可以看出vart

通过统计小块PU单元运动估计判定正确的CU单元个数占总CU单元个数的比例，得到裁减小块PU单元运动估计后的准确率，准确率统计结果见表2.

由表2可以看出，文中所提的运动估计快速终止方法的准确率非常高，平均达到了 98.72%，说明只有少部分需要非2N×2N模式运动估计的CU单元被判定为只进行2N×2N模式运动估计，这部分CU单元对整体效果的影响非常小，由此证明了算法的可靠性.

表2 运动估计快速终止准确率统计

Tab.2 Accuracy statistics of motion estimation quick ending

分辨率/pixel序列准确率/%416×240BlowingBubbles97.22416×240BasketballPass98.89416×240BQSquare99.19832×480BQMall98.71832×480BasketballDrill97.62832×480PartyScene98.591280×720Vidyo399.791280×720Vidyo499.78平均98.72

2.3 算法流程

算法实现步骤如下：①当前递归深度Dc为 0 时，进行2N×2N和非2N×2N模式运动估计；如果递归深度不为0，当上一递归深度Dc-1下的标志位DeepME为True 时,才进行非2N×2N模式运动估计，否则跳过非2N×2N模式运动估计；②如果当前递归深度小于最大递归深度，根据式(4)、(5)和(6)计算当前CU单元所有4×4块运动矢量的运动差异vart；③如果vart

3 实验结果与分析

为测试所提方法性能，测试了分辨率为2 560×1 600 pixel、1 920×1 080 pixel、1 280×720 pixel、832×480 pixel和416×240 pixel的视频序列共15个.采用HEVC编码标准的官方测试模型HM(版本为HM9.0)作为测试平台.实验配置：编码树单元CTU大小为64×64，最大深度为3，运动搜索模式为快速搜索算法(Enhanced Predictive Zonal Search，EPZS)，搜索区域的窗口是[-64,64]，将用于编码中运动搜索加速项(Fast Encoder Decision，FEN)设置为使能.采用低延时(Low Delay,LD )和随机访问(Random Access,RA)编码结构，实验中采用量化参数(Quantum Parameter,QP)为22、27、32和37，通过所有帧的信噪比变化量ΔPSNR和码率变化率ΔBR分析了算法的率失真性能.通过对算法编码时间变化率ΔT的统计，衡量了计算复杂度的变化，ΔPSNR为负值表示峰值信噪比(Peak Signal to Noise Ratio,PSNR)有所下降，ΔBR为正值表示码率有所上升，ΔT为负值表示算法编码时间的减少.

计算公式分别为

(7)

(8)

(9)

表3 本文算法的率失真和性能

从表3可知，在LD、RA编码配置下，本文算法的编码时间较编码器HM9.0分别减少41.79%和41.98%，ΔBR总体平均值分别增加1.73%和1.12%，ΔPSNR总体平均值分别降低0.052dB和0.041dB.这一结果说明，本算法在保证良好的率失真性能的同时，大幅减少了编码时间.其中对某些视频序列如Vidyo1序列和Vidyo3序列，在不同配置下，编码时间减少最高能够达到58.21%和57.98%.分析vart值分布情况统计表可知，对于分辨率较高的720p高清格式视频，vart

PMD算法利用光流法计算金字塔运动发散的特征值决定CU的分割情况，在一定程度上降低了复杂度，但其未考虑运动矢量间的相关性，导致其编码RD性能并不十分理想，光流法基于图像序列实现对光流场的精确、快速及鲁棒性估计.然而，由于图像序列目标的特性、场景中照明、光源的变化、运动的速度以及噪声的影响等多种因素均影响光流法的有效性，因此降低了帧间快速运动估计准确性.金字塔运动发散特征值的计算存在3个假设：亮度恒定，即图像场景中目标的像素在帧间运动时外观上保持不变；时间连续或者运动是“小运动”，即图像的运动随时间的变化比较缓慢；空间一致，即一个场景中同一表面上邻近的点具有相似的运动.然而，对于多数30Hz的摄像机，大而连贯的运动是普遍存在的情况，因此光流在实际中的跟踪效果并不是很好.这就需要增大窗口来捕获大的运动，而大窗口往往违背运动连贯的假设，导致编码率失真性能下降，难以实现对更快和更长的运动的跟踪.而本文算法能充分利用视频序列中同一个对象的运动矢量相似性来改善编码RD性能.为此将本文算法与PMD算法进行了横向比较，表4列出了PMD算法在LD和RA编码配置下的率失真和性能.

表4 PMD算法的率失真和性能

结合表4和表3可以看出，本文算法在LD、RA编码配置下，较PMD算法ΔBR分别降低了0.56%和1.15%，ΔPSNR分别提高了0.027dB和0.036dB，提高了编码的RD性能，同时编码时间分别节约了1.19%和3.51%.

图3 不同算法在LD、RA编码配置下的RD曲线图

4 结 论

为降低HEVC编码中CU单元递归划分的计算复杂度，文中基于运动矢量相似性，提出了一种快速帧间预测算法.

1) 该算法利用视频序列中同一个对象的运动矢量相似性，通过选取当前CU单元的划分方式，实现了部分可能性较低的复杂划分方式下运动估计的提前终止.通过分析当前运动矢量差异程度和判定运动相似区域内的当前编码块，实现了运动相似区域内编码块的运动估计裁剪.

2) 实验结果表明，本文算法与HM9.0 算法相比，在LD、RA编码配置下，编码时间分别减少了41.79%和41.98%，码率分别增加了1.73%和1.12%，峰值信噪比分别降低了0.052dB和0.041dB.表明本文算法在保证良好的率失真性能的前提下，减少了编码时间，降低了编码复杂度.

[1]HANGJ,OHMJR,HANWJ,etal.OverviewoftheHighEfficiencyVideoCoding(HEVC)Standard[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology，2012,22(12):1649.

[2]ZHANGY，WONGSK，WANGX,etal.MachineLearning-basedCodingUnitDepthDecisionsforFlexibleComplexityAllocationinHighEfficiencyVideoCoding[J].IEEETransactionsonImageProcessingaPublicationoftheIEEESignalProcessingSociety,2015,24(7):2225.

[3]LAINEMAJ，BOSSENF，HANWJ，etal.IntraCodingoftheHEVCStandard[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology,2012,22(12):1792.

[4]XIONGJ,LIHL,WUQB,etal.AFastHEVCInterCUSelectionMethodBasedonPyramidMotionDivergence[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology,2014,16(2):559.

[5]KIMJ,KIMM.AnalysisoftheJND-suppressionEffectinQuantizationPerspectiveforHEVC-basedPerceptualVideoCoding[J].Hingorani,2015,4(1):22.

[6]SULLIVANGJ,WIEGANDT.Rate-distortionOptimizationforVideoCompression[J].IEEESignalProcessMagazine,1998,15(6):74.

[7]CMFU,ALSHINAE,ALSHINA，etal.SampleAdaptiveOffsetintheHEVCStandard[J].IEEETransactionsonCircuits&SystemsforVideoTechnology,2012,22(12):1755.

[8]SHENLQ,LIUZ,ZHANGXP,etal.AnEffectiveCUSizeDecisionMethodforHEVCEncoders[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology,2013,15(2):465.

[9]VANLP，PRAETERJD，WALLENDAELGV,etal.EfficientBitRateTranscodingforHighEfficiencyVideoCoding[J].IEEETransactionsonMultimedia,2015,18(3):1.

[10]WIEGANDT，OHMJR，SULLIVANGJ,etal.SpecialSectionontheJointCallforProposalsonHighEfficiencyVideoCoding(HEVC)Standardization[J].IEEETransactionsonCircuits&SystemsforVideoTechnology,2010,20(12):1661.

[11]ZHOUCT,TIANX,CHENYW.FastCodingUnitSizeDecisionforHEVC[J].JournalofZhejiangUniversity(EngineeringScience),2014,48(8):1452.

[12]FANGSQ,YUM,XUSY,etal.ANovelFastInterCodingAlgorithmforHEVC[J].JournalofOptoelectronicsLaser,2015,26(5):932.

[13]LIW,WANGRD,WANGJJ,etal.AFastIntraCodingAlgorithmwithLowComplexityforHEVC[J].JournalofOptoelectronicsLaser,2015,26(3):597.

(责任编辑、校对 张 超)

简 讯

《西安工业大学学报》中英文摘要的写作要点

论文摘要为读者阅览起引导作用,又为文献汇编、计算机储存、检索做好准备,成为科技情报的重要来源.科技论文的中英文摘要在写作时应注意的要点包括：

中文摘要：① 尽量简短、开门见山.不写课题研究的背景信息和在第一句话中重复题目或题目的一部分；② 包含正文的要点.重点内容,试验研究的方法、设备、材料等均不能漏掉，且要得出结论；③ 只列出最关键的数据，且摘要应具有独立性；④ 不要标榜自己的研究结果；⑤ 文中不出现图、表的数据；⑥ 内容应在正文中出现，不表述个人观点和未来计划，只要纯粹的文章概述；⑦ 句子应尽量简短，只叙述新信息和发现，删除和减少研究细节；⑧ 缩写词应附有全称；⑨语句简洁，专业词汇准确.

英文摘要：不出现以下情况：① 一对一翻译.避免出现中国式英语，专业词汇要用专业词语翻译；② 主谓不一致；③ 时态不一致.

(张立新)

Estimation Algorithm of Fast Inter-Frame Motion for HEVC and Analysis of the Calculation Complexity

CHENHong,QIHua

(School of Electronic Information Engineering,Xi’an Technological University,Xi’an 710021,China)

In view of highly complicated calculation problems of inter-frame motion estimation of high efficiency video coding (HEVC),a fast termination algorithm of motion estimation on motion homogeneity was proposed.The motion homogeneity of the same object in video sequence was adopted to make a reasonable selection for the division method of current coding unit (CU) and end, in advance, motion estimation of partial and less posible complex division mode.For CU in the similar motion regions,after decomposition of next recursive depth,small prediction unit (PU) splitting motion estimation was cut.The results show:Compared with the original HEVC encoding algorithm,the proposed algorithm reduces en-coding time by 41.79% and 41.98% ,peak signal-to-noise ratio(PSNR) loss by 0.052 dB and 0.041 dB in the low-delay and random-access cases.The amount of calculation of motion estimation and the calculation complexity were reduced.

high efficiency video coding;motion estimation;motion difference;calculation complexity

10.16185/j.jxatu.edu.cn.2016.10.014

2016-03-29

陕西省教育厅科研计划项目(12JK0503);陕西省科技厅科学技术发展计划项目(2014K05-19)

陈 红(1980—),女,西安工业大学讲师,主要研究方向为图像处理算法、无线传感器网络及信息论与编码.E-mail:chenhong8008@126.com.

TN919.81

A

1673-9965(2016)10-0848-08