基于HEVC帧内预测的复杂度控制

李林格，张 恋，王 洁，周 巧，张 昊

(中南大学 信息科学与工程学院，湖南 长沙 410083)



基于HEVC帧内预测的复杂度控制

李林格，张 恋，王 洁，周 巧，张 昊

(中南大学 信息科学与工程学院，湖南 长沙 410083)

帧内预测在视频编码中是非常重要的模块。在视频实时编码与传输过程中，场景切换会经常出现。此时，一般会采用全I帧编码。研究发现，即使是全I帧编码，也往往会非常耗时。基于编码单元深度范围和帧内预测中候选预测方向个数研究了HEVC编码器的复杂度控制问题。针对不同的目标编码复杂度，算法自适应地选择不同的方法来优化编码过程。实验结果表明，该算法在保证视频质量的前提下实现了对不同复杂度目标的控制。

视频编码；HEVC；帧内预测；复杂度控制

1 HEVC视频标准编码

随着视频技术的发展，特别是高清(HD)、超高清(UHD)、3D和多视点(multi-view)视频技术的兴起，各种视频信息已普及和深入到人们生产和生活的各个方面。基于互联网的网络视频实时通信己经成为当前通信领域的热点，并在视频会议、视频监控、远程教育、视频点播等方面得到广泛的应用，视频压缩技术受到巨大的挑战。视频应用的多样化和高清化趋势对视频压缩性能提出了更高的要求。为此，2010年4月VCEG和MPEG再次组建视频编码联合组(Joint Collaborative Team On Video Coding，JCT-VC)，联手制定新一代视频编码标准——HEVC(High Efficiency Video Coding)[1]。相比以往的视频编码标准，HEVC沿用了传统视频编码标准的混合视频编码基本框架，并在各个编码模块上进行了改进和革新。其核心模块包括：预测、变换和量化、熵编码、环内滤波等。与先前的H.264/AVC标准相比，在相同应用条件和视频质量的前提下HEVC的编码效率要提高一倍。随着HEVC的发展，基于HEVC的应用级编码器也随之出现，目前可以直接使用的有两个：x265，DivX265。类似于以往的国际标准，HEVC采用混合编码框架，如图1所示[2]，主要包括变换、量化、熵编码、帧内预测、帧间预测以及环路滤波等模块[3]。

图1 HEVC视频标准编码框

2 复杂度控制研究现状

目前HEVC快速帧内模式选择算法，一般都只考虑在尽量少损失客观质量的情况下对模式进行选择。一般的论文中，都只考虑3%以内的质量损失(采用BDBR或者BD-PSNR的指标)。在某些场合，仅仅采用这些保守的模式选择算法，是达不到实际应用需求的。由于HEVC的复杂程度很大，有时候需要通过相对比较大的质量损失，以达到实时性[4]，在这方面，复杂度控制算法可以作为参考。针对H.264，已经有很多复杂度控制方面的研究[5-7]。然而，由于HEVC与H.264的编码结构大不相同，因此其复杂度控制算法也需要重新设计。比如，在文献[8]中，G.Correa通过同位区域中的纹理关系对编码单元的深度进行调整。如果纹理关系相近，那么当前编码CU也将采用这个深度。并且通过总的时间关系，对需要做算法的帧数进行提前计算，从而控制编码的复杂度。

文献[9]中，A.Ukhanova通过率失真和复杂度的关系来选择量化和深度参数，使用预测和博弈论作为基础，对于某一些帧的最大CU深度进行限制，从而控制编码复杂度。

文献[10]中，M.Grellert提出了负载管理的方案。该方案的基本思路就是估算每一帧的复杂度预算，动态地控制每一帧的复杂度。比如通过限制最大CU深度的预测和运动搜索范围等，并通过反馈的环路控制最大限度地减少RD损失。

文献[11]中，J.Leng对相邻和同位的编码深度进行分析，通过阈值来避免一些无必要的编码深度。控制需要进行优化的最大CU数量来调整编码的复杂度。

文献[12]中，X.Shen利用了贝叶斯的方法来对深度进行选择。这个算法是基于离线的机器学习方法，使用贝叶斯决策的规则，对编码单元是否需要划分进行判断。

综上所述，已经提出的方法一般针对编码单元的深度进行调控，或者对模式数量进行调控，没有把这两者结合起来分析考虑。并且以前的工作都是针对帧间预测进行的复杂度控制，而在帧内预测方面还没有相关工作。本文将针对帧内预测的复杂度控制进行研究。

3 帧内预测复杂度分析

帧内预测主要用于去除图像的空间相关性。通过编码后的重构块信息来预测当前像素块以去除空间冗余信息，提高图像的压缩效率。帧间预测模块主要用于去除图像时间相关性。HEVC采用了编码单元、预测单元、变换单元代替H.264宏块的概念[13]。由于最大编码单元比宏块要大很多，而且编码单元和变换单元都可以采用树形分块，预测单元采用了更多的分割模式，因此，HEVC复杂度比H.264要高很多。另外，对帧内预测，HEVC的预测方向要比H.264多好几倍[14-15]，如图2所示。

图2 LCU递归划分过程

虽然一般来说帧间预测的复杂度高于帧内预测，但是在实际视频编码中，帧间预测经常会采用Merge甚至Skip模式[16]，可以大大节省计算量。而HEVC帧内编码可选择编码单元大小和预测方向都比较多，因此计算复杂度高，在实时性要求较高的场合(比如视频聊天、直播)可能会引起卡帧现象[17-18]。本文主要对帧内模式进行分析，找出最优的编码单元大小和预测方向组合，为具体应用提供参考。

3.1 编码单元深度的复杂度分析

在HEVC中，视频编码时采用树型结构编码单元(CodingUnit，CU)，对于亮度像素CU，其尺寸可以从64×64一直递归划分至8×8，CU的递归划分过程如图3所示。较大块的CU可以被划分成较小的CU，例如对于depth=n的CU，若划分标志位(splitflag)为1，则继续划分为depth=n+1的4个小CU，每个较小CU的尺寸是上一深度CU的1/2。

图3 CU中不同深度所占的复杂度

从图3中可以得到，编码单元CU的深度一共可分为0，1，2，3，分别对应编码单元的大小为64×64，32×32，16×16，8×8。在递归划分的过程中需要进行大量的RDO计算，LCU的递归划分过程也占到了编码时间的90%，因此通过提前终止CU的划分，减少CU深度大小能够有效减少视频编码复杂度，达到缩短视频编码时间的目的[19]。

HEVC帧内预测复杂度可以通过不同的编码参数对其进行评估，比如说编码的总时间。在本文中，在不需要考虑操作系统的其他性能时，可以通过软件分析器来获得编码时间，统计3个1 280×720分辨率的视频测试序列(Four People，Johnny和Kristen and Sara)的每个CU深度的编码时间。其中每个序列的帧数均为150帧，因此总的编码时间基本上也都很相似。

图3显示了每一个CU深度层的平均编码时间比。CDN代表不同深度的时间比，N从0到3。从图中可以看出，深度越大，计算所占的时间比重越大。因此，对复杂度的控制可以转化为对深度进行优化，从而大大减少编码时间。

3.2 帧内预测中候选预测方向个数复杂度分析

帧内预测是视频编码过程中的一个重要组成部分，它充分利用图像的空间相关性，来提高压缩效率。然而帧内预测具有极高的算法复杂度，实时性要求高的场合使用起来效果往往不是很好，特别是在出现场景切换时，编码器会进行大量的帧内预测。因此在实际应用中需要加快帧内预测过程，使得编码过程更加流畅，减少卡帧现象。

对于不同尺度大小PU，最佳的候选预测方向个数也不同，大小为16×16，32×32，64×64的PU只有3个预测方向，大小为4×4和8×8的PU有8个预测方向。因此在保证图像损失很小的情况下，可以减少候选预测方向个数来减少编码时间。本文对不同大小的PU的候选预测方向个数进行调整，通过实验定义了4种不同的候选预测方向个数组合CP1，CP2，CP3，CP4，如表1所示。

表1 不同PU大小对应不同的候选预测方向组合

测试在定义的4种不同的候选预测方向个数组合下，记录对应的视频编码过程中的时间减少(ΔTime/%)和峰值性噪比的减少(ΔY-PSNR/dB)，变化趋势如图4所示。其中参与测试的视频序列有BasketballPass，BQSquare，BasketballDrill，BQMall和FourPeople，编码帧数为150帧。由图4分析可得，随着候选预测方向的减少，编码时间会随之减少，CP1组合有将近10%的时间减少，Y-PSNR的损失在0.01 dB以内，而CP4组合有将近20%的时间减少，但是图像质量损失较大，已经超过了0.1 dB。

图4 不同候选模式组合与编码时间和Y-PSNR的关系

综合分析这4种组合的ΔTime和ΔY-PSNR可得：本文选择CP1组合作为候选预测方向的最佳组合，此时时间下降明显，同时视频质量没有损失太多。此时，对复杂度的控制可以解释为：先设定一个需要减少的目标时间，把候选预测方向的个数组合设定为CP1来达到复杂度控制的目的。

4 算法描述

为了更好地适应视频播放时出现场景切换的情况，并加快帧内预测编码时间来减少复杂度，本文提出了两种解决方案：

1)对帧内预测中编码单元CU深度大小范围进行调整，节省编码时间；

2)对帧内预测中的最佳候选模式数量进行调整。根据不同的情况，结合以上两种方案，对编码复杂度进行联合控制。

在整个视频序列中，分为需要做优化算法的编码帧Scn和不需要做优化正常编码的普通帧Su。如图5所示，通常第一帧是不需要做优化的普通帧，然而接下来的帧需要对其进行时间上的预测和控制，如果需要对其进行复杂度控制，则加入优化算法，否则依然不需要进行优化。

图5 视频编码帧结构

为了控制编码复杂度，在CU深度方面对当前编码帧的每一个64×64的CU块进行统计，对其中的深度大小进行范围统计，得到当前CU的深度范围区间[MinDepth，MaxDepth]和深度范围大小NumDepth，可以用来限制下一帧的同位CU的编码深度的选择。当需要进行优化算法的编码帧Scn进行编码时，可以使用前一帧的深度信息去限制当前编码块的最大和最小深度，这样就不需要做所有的RDO计算，从而节省了编码时间。由于视频存在时间相关性，前一帧与当前编码帧存在一定的相似性，所以同位的CU区域也会拥有一个相似的深度范围，在不影响编码效率的情况下，可以对当前同位的CU使用前一帧的编码深度范围。

而在候选预测方向个数方面，通过前文分析可以得到，在使用CP1的候选预测组合时，时间减少了近10%，而图片的质量损失可以忽略不计。在本文中，主要考虑时间复杂度，定义视频的编码总时间复杂度为Tt，目标时间复杂度为Td，已编码帧的时间复杂度为Tp。对当前帧进行编码时，若已编码的平均时间复杂度TYave比未编码的平均时间复杂度TNave大，则加入优化算法；若已编码的平均复杂度TYave比未编码的平均时间复杂度TNave小，则不加入优化算法，正常编码。TYave和TNave的计算公式如式(1)和式(2)所示

(1)

(2)

式中：n代表已经编码的帧数；N代表总编码帧数。

总体的算法流程框图如图6所示。

图6 算法结构流程图

具体的复杂度控制度算法如下：

1)第一帧正常编码，记录每个CU块中的深度范围[MinDepth，MaxDepth]和深度的范围大小NumDepth。

2)通过式(1)和(2)得到TYave与TNave，如果TYave大于等于TNave的1.1倍，转向步骤3)；若小于TNave的1.1倍并且大于等于TNave，则转向步骤4)，其他情况转向步骤5)。同时记录当前帧的编码深度信息。

3)当TYave大于等于TNave的1.1倍，表示当前需要减少的编码时间较多，则直接利用深度优化算法。如果前一帧同位CU的NumDepth大于0时，则表示前一帧同位CU中有不同的深度，那么当前编码CU只需要遍历[MinDepth，MaxDepth]。否则，表示前一帧同位CU深度都一样，那么当前编码CU需要编码[0，MaxDepth]。同时记录下当前帧的序号，如果连续超过4帧图像使用深度优化算法，为了保证视频图像的质量，则从第5帧开始，对每个当前编码块的同位CU的MaxDepth减1。

4)当TYave小于TNave的1.1倍并且大于等于TNave，表示当前需要减少的编码时间较少，为了保证视频图像质量，则不使用深度优化，直接调整模式候选个数，将候选模式预测组合切换到CP1。

5)当TYave小于TNave时，表示前面已编码帧数的平均时间已经小于目标时间下的剩余编码平均时间，如果标记为优化帧Scn，那么编码总时间会达不到目标时间，所以直接标记为Su即可。

6)重复到步骤2)，直到编码结束为止。

5 实验分析

为了验证本文算法的有效性，本文在HEVC参考软件HM-15.0上进行仿真实验。实验平台的硬件配置为Iter(R)-Core(TM)i7-4790CPU，主频为3.60GHz，内存为8Gbyte，操作系统为64位Windows7，开发工具为VS2013。实验中，配置文件是“encoder_intra_main.cfg”。全I帧，原始的深度范围是0～3(即[0，1，2，3])，其他参数均采用HM默认配置。

设定不同的目标复杂度，记为TC(%)={90，80，70，60}，在不同的目标复杂度的情况下，使用本文提出的复杂度控制算法。使用比特率的变化幅度百分比ΔBR、峰值性噪比(PSNR)的差值ΔPSNR和编码时间减少TS来衡量编码性能，TS计算方法如下[16]

(3)

实验结果如表2所示，其中在不同的目标时间复杂度下，对表中19组不同的视频测试序列使用不同量化参数QP进行测试，计算了QP分别为22，27，32，37时的ΔBR，ΔPSNR和TS的平均值。根据表2数据，分析3个视频序列(BasketballPass，PartyScene，FourPeople)的目标复杂度和实际复杂度的对比图如图7所示，可以明显得出实际测得的复杂度和目标复杂度相差不多。从所有视频序列的平均情况来看，目标时间复杂度TS从90%到60%，ΔPSNR平均值从0.01 dB到0.08 dB，其中效果最差的是序列BQSquare，在目标时间复杂度是60%的时候，PSNR下降了0.31 dB，总体上来说图像的质量损失不大，可以忽略不计。ΔBR平均值从0.02到2.32，其中效果最差的是序列BQSquare和BasketballDrill。除此之外，总体上比特率的变化不大。图8给出了序列Johnny在不同QP下达到不同的目标复杂度时的PSNR和比特率，可以看出视频图像的质量损失可以忽略不计。

为了能更好地看到每一帧时间复杂度的变化，图9统计了目标复杂度为70%时，编码100帧的时间折线图。从图中可以看到，实际每一帧的编码时间在平均每一帧的编码时间线的上下波动。更加明显地体现了复杂度控制的作用性。综上所述：本文提出的算法基本能达到目标的时间，从而对编码过程进行复杂度的控制，同时编码性能基本不变，保证了视频图像的质量。

表2 实验结果

图7 序列的目标复杂度与实际复杂度

图8 序列Johnny性能分析

6 结论

本文研究了基于HEVC帧内预测的复杂度控制方法。提出了改变CU深度范围和减少RDO候选模式个数的方法来联合控制编码复杂度。算法针对不同复杂度目标来自适应地选择不同的复杂度方法。当目标复杂度调整幅度比较大的时候采取CU深度范围调整，而目标复杂度调整幅度较小的时候将选取减少RDO候选模式个数的方法。实验结果表明，以上算法的效果比较明显，能够把复杂度控制做给定目标附近。

图9 在目标复杂度为70%时，序列BasketballDrive每一帧所花费的时间

[1] SULLIVAN G J，OHM J，HAN W J，et al. Overview of the high efficiency video coding (HEVC) standard[J]. IEEE transactions on circuits and systems for video technology，2012，22(12)：1649-1668.

[2]朱秀昌，李欣，陈杰.新一代视频编码标准——HEVC.[J].南京邮电大学学报，2013，33(3)：2-3.

[3] POUAZAD M T，DOUTRE C，AZIMI M. HEVC：the new gold standard for video compression how does heve compare with H.264/AVC[J]. IEEE consumer electronis magazine，2012，1(3)：36-46.

[4]余越，周健，王贻良，等.一种场景切换检测及自适应码率控制方法[J].通信学报，1999(5)：50-55.

[5]TAN Y H，LEE W S，THAM J Y， et al. Complexity scalable H.264/AVC encoding[J]. IEEE transactions on circuits & systems for video technology， 2010， 20(9)：1271-1275.

[6]SU L， LU Y， WU F， et al. Complexity-constrained H.264 video encoding[J]. IEEE transactions on circuits & systems for video technology， 2009， 19(4)：477-490.

[7]MA S， GAO W， LU Y. Rate-distortion analysis for H.264/AVC video coding and its application to rate control[J]. IEEE transactions on circuits & systems for video technology， 2005， 15(12)：1533-1544.

[8]CORREA G，ASSUNCAO P，AGOSTINI L，et al. Complexity control of high efficiency video encoders for power-constrained devices[J]. IEEE transations on consum. electron.，2011，57(4)： 1866-1874.

[9]UKHANOVA A，MILANI S，FORCHHAMMER S. Game-theoretic ratedistortion-complexity optimization for HEVC[C]//Proc. IEEE 20th Int. Conf. Image Processing.[S.l.]：IEEE，2013：1995-1999.

[10] GRELLERT M. An adaptive workload management scheme for HEVC encoding[C]//Proc. IEEE 20th Int. Conf. Image Process.， Sep. 2013， pp. 1850-1854.

[11]LENG J, SUN L, IKENAGA T, et al. Content based hierarchical fast coding unit decision algorithm for HEVC[C]//Proc. Int. Conf. Multimedia Signal Processing. [S.l.]：IEEE，2011：56-59.

[12]SHEN X，YU L，CHEN J. Fast coding unit size selection for HEVC based on Bayesian decision rule[C]//Proc. Picture Coding Symp.[S.l.]：IEEE，2012：453-456.

[13]LAINEMA J， BOSSEN F， HAN W， et al. Intra coding of the HEVC standard[J]. IEEE transctions on circuits and systems for video technology，2012，22(12)：1792-1801.

[14]KIM I， MIN J， HAN W，et al. Block partitioning structure in the HEVC standard[J]. IEEE transctions on circuits and systems for video technology，2012，22(12)：1697-1706.

[15] OJALA T，PIETIKAINEN M，MAENPAA T. Multiresolution gray scale and rotation invariant texture classification with local binary patterns[J]. IEEE transactions on pattern analysis and machine intelligence，2002，24(7)：971-987.

[16]FENG P. Fast mode decision for intra prediction[S]. 2003.

[17]杨任尔，郑紫薇，金炜.基于图像特征的隐写术载体图像的旋转[J].光电子·激光，2014，25(4)：764-768.

[18] WANG Z，BOVIK A C，SHEIKH H R，et al. Image quality assessment：from error visibility to structural similarity[J]. IEEE transactions on image processing， 2004，13(4)：600-612.

[19]XU D W，WANG R D，WANG J C. Prediction mode modulated data-hiding algorithm for H.264/AVC[J]. Journal of real-time image processing，2012，7(4)：205-214.

责任编辑：时 雯

Complexity control of HEVC intra prediction

LI Linge，ZHANG Lian，WANG Jie，ZHOU Qiao，ZHANG Hao

(SchoolofInformationScienceandEngineering,CentralSouthUniversity，Changsha410083，China)

Intra prediction is a very important module in video coding. In real-time video coding and transmission， scene changes frequently occur and all-I frames are usually adopted. Researches have showed that it also takes lots of time even using the all-I frames coding. In this paper， the coding unit depth range and the number of candidate prediction in intra prediction are used to control the coding complexity. According to different target coding complexity， different algorithm is adaptively used to optimize the coding process. The experiment results show that the algorithm in this paper achieves the different target complexity control on the condition of ensuring the quality of the video.

video coding； HEVC； intra prediction； complexity control

李林格，张恋，王洁，等.基于HEVC帧内预测的复杂度控制[J].电视技术，2016，40(11)：18-24. LI L G，ZHANG L，WANG J，et al.Complexity control of HEVC intra prediction[J].Video engineering，2016,40(11)：18-24.

TN911

A

10.16280/j.videoe.2016.11.004

2016-03-30