分级自适应的HEVC帧内预测模式快速选择算法

金智鹏，代绍庆，曾 涛

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

分级自适应的HEVC帧内预测模式快速选择算法

金智鹏1，2，代绍庆1，曾 涛2

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

针对HEVC帧内预测编码计算复杂度高的问题，提出了一种基于分组自适应的帧内预测模式快速选择算法。该算法抽选12个候选模式进行预测方向初步判断，然后根据初步判断结果再精选预测模式；并根据粗选的HCost代价排除部分可能性较低的候选模式，以达到减少候选模式数量，降低计算复杂度的目的。在HEVC参考软件HM12.0上的测试表明，该算法在BD-PSNR平均损失0.041 dB的情况下，平均可降低36.521%的编码时间，显著提高了编码速度。实验结果显示，该算法的适应性强，对不同尺寸、不同纹理和运动特点的测试序列均有明显效果，具有良好的实际应用价值。

视频编码；H.265/HEVC；帧内预测；模式判决；快速算法；提前排除

新一代高效视频编码标准(High Efficiency Video Coding,HEVC)于2010年4月在JCT-VC第一次会议上被提出来，并在之后逐步得到完善。相对于之前的H.264，HEVC在预测编码方面有了长足的发展，提高了1倍的编码效率。HEVC主要面向下一代4K分辨率高清电视、3D视频、移动视频、流媒体视频等最新应用[1]。

HEVC采用了灵活的基于大尺寸四叉树的分割结构和编码结构[2]，包括编码单元(Coding Unit，CU)、预测单元(Prediction Unit，PU)以及变换单元(Transform Unit，TU)。为满足高清视频中更为细致的纹理预测需要，HEVC最高支持35种帧内预测模式，其中方向预测增加到33种，提高了预测精度。此外，在DC均值模式的基础上增加了Planar平滑预测模式，提高了对渐变式平滑纹理区的预测精度。但是，HEVC的高性能编码是以极高的计算复杂度为代价的，而高计算复杂度却是其面向实际应用的技术难题。因此，如何降低编解码的计算复杂度，成为了HEVC当前的研究热点。

1 HEVC帧内预测快速模式选择算法分析

1.1 HEVC帧内预测模式判断过程

为了提高预测精度，自参考软件HM7.0之后，每个尺寸的PU都有35种帧内预测模式；HEVC帧内预测模式快速判断的流程可分为以下3个阶段。

阶段一，采用Hadamard变换对所有35种模式进行RMD(Rough Mode Decision)模式粗选择[3]。根据HCost选取代价最小的N个预测模式作为候选模式，加入粗选子集。针对4×4和8×8的PU尺寸，N=8；针对其他的PU尺寸，N=3。HCost定义为

HCostmode=HSATDmode+λ·bitsmode

(1)

式中：HSATD表示残差信号哈达玛变换系数绝对和，它在一定程度上反映了残差比特率，其定义如式(2)所示；mode为35种帧内预测模式之一；λ为拉格朗日乘子；bits为该模式下的编码比特数。

(2)

式中：T(D)=HDH是指Hadamard变换；H是Hadamard变换矩阵；D指残差信号矩阵Diff(i,j)。

Diff(i,j)=Orig(i,j)-Pred(i,j)

(3)

式中：Orig(i,j)是指原始图像块中的像素值；Pred(i,j)是指预测值。

阶段二，检测当前编码块的最有可能模式MPM(Most Probable Mode)是否包含在粗选子集中。若不在，则将其加入粗选子集。换言之，无论RMD阶段的模式粗选结果如何，都加入当前预测块的左侧块和上方块的最优模式作为候选模式，使其具有自适应性[4]。MPM技术提高了RMD粗选模式子集的准确度，有效地降低了计算复杂度。

阶段三，对粗选子集中的预测模式进行RDO(Rate Distortion Optimization)率失真代价计算，RDCost代价最小的模式即为最优预测模式。然后通过最优预测模式预测当前PU，并对预测残差进行变换、量化和熵编码。RDCost定义为

(4)

相较于进行35 次RDCost计算，通过RMD算法进行帧内预测模式粗选节省了大量的编码时间；但即便如此，亮度帧内预测进行RDCost计算的过程仍然占用了50%～60%的帧内预测编码时间[5]。因此，提高RMD粗选的准确性，减少需要进行RDCost计算的候选模式数量，是降低帧内预测编码计算复杂度的关键。

1.2 HEVC帧内预测快速算法分析

在保持HEVC 编码性能的前提下，很多学者开始研究降低算法的计算复杂度，以便实际应用和推广。其中针对帧内预测部分有两个研究热点，分别是块划分算法的优化和预测模式的快速判决。

1)文献[6]提出了一种基于梯度的 HEVC 帧内预测模式快速选择算法。该算法继承了H.264中基于边缘检测的快速算法[7]，利用PU内的纹理梯度信息进行预测模式的快速选择。实验结果显示，该算法能够降低约20%的编码复杂度。

2)由于色度帧内预测只有5种模式，因此文献[8]提出先进行色度的帧内预测编码，然后参考色度预测结果再进行亮度预测模式的筛选，以达到降低亮度帧内预测复杂度的目的。实验结果显示，在BD-PSNR(Bjontegaard delta PSNR)损失为0.05 dB的情况下，该算法能够降低约30%的编码复杂度。

3)文献[9]提出了一种自适应的候选模式快速选择算法。对于大尺寸的PU块，如果最小HCost代价为DC或Planar模式，则只对DC和Planar模式进行RDCost计算。对于小尺寸的PU块，检查HCost代价最小的2个模式是否相邻，将较佳候选模式数动态地减少为2～5个。在BD-BR(Bjontegaard delta bit rate)增加1%的情况下，该算法能够降低约20%的编码复杂度。

4)文献[10]充分利用视频序列的时域相关性，提出利用相邻帧CU划分信息提前判定当前编码块的最优CU尺寸；并在PU层考察粗选模式的HCost代价，如果代价偏离过大，则将其排除出候选模式子集。该算法的PSNR平均损失为0.06 dB，码率增加0.09%，编码时间节省了约49%。

5)文献[11]分析了图像平滑特性与编码块尺寸大小的关系，提出一种依据纹理平滑性判断的快速帧内编码算法。算法首先对64×64的块进行正常编码，将其编码率失真信息与阈值比较，判断是否需要将其分割为4个更小的32×32编码块。在BD-BR增加约0.44%的情况下，编码时间减少了24.8%。

6)文献[12]提出了一种候选模式分组计算的帧内模式快速选择算法。算法通过将35种预测模式分为3组进行计算，总共利用其中17种模式就能完成RMD阶段的模式粗选。该算法可以降低约50%的编码时间，但算法易陷入局部最优，平均码率损失达到了5.23%。

虽然以上几种快速算法的性能损失极小，但编码时间节省的幅度并不大。尤其对于4×4和8×8尺寸的PU块，RMD粗选得到的候选模式数量较多，还需深入研究。

2 基于分级自适应的HEVC帧内预测模式快速选择算法

2.1 算法设计依据

RMD模式粗选是帧内预测的关键步骤，图1展示了RMD粗选模式和MPM模式最终成为当前PU最优预测模式的概率统计。本文的数据是在HEVC的参考软件HM12.0上(encoder_intra_main配置)进行50帧全I帧编码统计的结果，实验对象为Class A～E共5个类别的20个标准测试序列。通过图1的实验数据分析，RMD粗选后代价最小的模式Mode_HCost 0最终成为当前PU最优预测模式的平均概率达到了71.5%；而且，从Mode_HCost 0～Mode_HCost 7，随着候选模式在RMD粗选中排名的降低，呈现出概率快速衰减的趋势，如图1所示。

根据实验统计数据，MPM模式最终成为当前PU最优预测模式的平均概率达到了76.2%，并且这个比率是所有候选模式中最高的。因此，有必要将MPM模式始终作为候选模式之一参与RDO阶段的判决。

图1 各RMD粗选模式成为最优模式的概率分布图

2.2 分级自适应的帧内预测模式快速选择算法

本文提出的快速算法的核心思路为：首先查找最佳预测方向可能所在的大方向区间，然后对大方向区间内的模式进行精细搜索，以求得更精确的预测模式；并依据HCost代价提前排除部分可能性较小的候选模式。算法的具体描述如下。

步骤1，采用如图2所示的12个一级候选模式进行RMD粗选计算，初步确定最优预测方向所在的大方向区间。一级候选模式中的Planar模式主要考虑纹理平滑区域的决策，其余11个方向预测模式采用角度均匀间隔的方式抽选。

图2 用于RMD粗选的12个一级候选模式

步骤2，经步骤1计算后，检测代价最小的2个较佳预测模式中是否存在Planar模式。如果存在Planar模式，则转入步骤3；否则转入步骤4。

步骤3，增加3个二级候选模式进行RMD粗选计算，即DC模式、较佳预测方向的左右2个相邻预测模式，计算出较为准确的候选模式范围。转入步骤5。

步骤4，增加4个二级候选模式进行RMD粗选计算，即2个较佳预测方向的左右2个相邻预测模式，计算出较为准确的预测方向区间。

步骤5，初步确定RMD预测模式筛选结果，得到粗选模式子集。针对16×16，32×32和64×64的PU尺寸，N=3。针对4×4和8×8的PU尺寸，N=2+二级候选模式数量。

步骤6，提前排除法(Early Rule Out，ERO)。考察粗选模式子集中各个预测模式的代价大小，若其代价HCostmode>α×HCostmin，则将其排除出粗选模式子集。根据编码经验α=1.2。如果代价差异大，说明当前PU块的纹理方向性明显，再结合图1的概率分布，可以排除一部分可能性较小的候选模式。

步骤7，检测最有可能模式MPM是否包含在粗选子集中。若未包含，则将其加入到粗选子集。最后，对粗选子集中的预测模式计算率失真代价RDCost，代价最小的模式即为最终的最优预测模式。

2.3 算法计算量的理论分析

在RMD阶段，本算法一级候选模式含有12个模式，二级候选模式含有3～4个模式，这样总共需要进行HCost计算的模式有15～16个，还不及全体35个预测模式数量的一半，节约了一半的计算量。

在RDO阶段，经过步骤6的ERO提前排除法，能提前排除部分可能性较小的候选模式。经过ERO提前排除后，对16×16以上尺寸的PU块，本算法的候选模式将动态地减少为1～3个；对8×8以下尺寸的PU块，候选模式将动态地减少为1～6个，有效地减少了复杂的RDCost计算次数。

3 实验结果与分析

PC机实验平台为： CPU Intel(R)Xeon(R) W3503 双核，主频2.4 GHz，内存2 Gbyte×2，操作系统为Windows7 SP1，编译软件为Microsoft Visual Studio 2008。实验测试模型为HM12.0(encoder_intra_main配置)，具体实验参数设置为：IntraPeriod=1(即全I帧编码)，编码前50帧，帧频30 f/s(帧/秒)，MaxCUWidth=64，MaxCUHeight=64，MaxPatitionDepth=4，CABAC为熵编码。

为了更客观更全面地对算法性能进行比较，本文选择了HEVC Class A～E等5种不同尺寸的标准YUV测试序列进行实验测试。测试序列中Class A是分辨率为2 560×1 600的超清序列，Class B和Class E是分辨率为1 920×1 080和1 280×720的高清和标清序列，Class C和Class D分别为832×480及416×240的WVGA和WQVGA小尺寸序列。

表1和表2反映了本文提出的快速算法与HM12.0中帧内预测算法的编码性能对比情况。ΔPSNR=PSNRproaposed-PSNRref，表示本文算法和HM12.0中帧内预测算法PSNR的差值；ΔRate表示两者码率差值的百分比

(5)

式中：Rateref和Rateproposed分别指HM12.0帧内预测算法和本文算法的编码码率。ΔTime表示两者编码时间差值的百分比，参考式(5)进行计算。

依据表1的实验数据，本文基于分级自适应的帧内预测模式快速选择算法具有良好的编码性能，码率平均增加0.164%，亮度PSNR平均降低0.032dB；这个损失对编码RD性能的影响微乎其微，人眼基本察觉不到画面质量的损失。同时，对不同尺寸、不同纹理和运动特点的测试序列，本文算法都获得了大致相同的效果，显示出良好的适应性，更贴近实际应用。

表1 本文算法和HM12.0算法的实验测试比较

表2 相对于HM12.0本文算法的实验测试结果

BD-PSNR表示在相同码率下，本文算法和HM12.0算法的亮度PSNR的差值，具体可参考文献[13]的计算方法。从表2的BD-PSNR实验数据可以看出，在相同的码率下，本文快速算法的平均PSNR损失只有0.041 dB，编码时间平均能缩短36.521%；而文献[8]的BD-PSNR损失达到了0.05 dB，而编码时间只缩短了30%，可见本文算法具有更好的编码性能。

表3是本文快速算法与其他几种快速算法的性能比较。根据表3的数据，本文快速算法的PSNR、码率和编码时间等指标都要明显优于文献[9]和[12]的算法。与文献[10]的算法相比，编码性能指标互有优劣。主要是文献[10]的算法包括快速CU划分算法，节省了更多的计算量。

图3和图4给出了Class A People on Street和Class B Kimono1序列的编码率失真曲线。可以看出，本文算法与HM12.0算法的RD曲线几乎重合，表明两者的编码性能差异极小。

表3 本文算法与其他快速算法的性能比较

图3 Class A People on Street序列的RD曲线对比图

图4 Class B Kimono1序列的RD曲线对比图

4 结论

在分析了HEVC帧内预测编码技术和最新的快速算法的基础上，提出了一种分级自适应的帧内预测模式快速选择算法。该算法采取分级计算、逐步精细的模式筛选方法；并根据粗选的HCost代价排除部分可能性较低的候选模式，以达到减少RDCost计算次数、降低计算复杂度的目的。实验结果显示，相比于HM12.0，本文算法在编码效率损失非常小的情况下，显著提高了编码速度；且算法的适应性强，对于不同类型的测试序列均有明显效果，具有良好的实际应用价值。

[1]吴敏，公衍超，杨楷芳.面向高效率视频编码标准的快速码率控制算法[J]．计算机应用，2013，33(5)：1251-1254.

[2]李轶夫，蒋毅飞，陈李维，刘宏伟.HEVC分像素插值与自适应环路滤波融合结构设计[J]．计算机辅助设计与图形学学报，2014，26(3)：493-501.

[3]PIAO Y，MIN J，CHEN J.Encoder improvement of unified intra prediction[EB/OL].[2014-03-21].http://phenix.int-evry.fr/jct/doc_end_user/documents/3_Guangzhou/wg11/JCTVC-C207-m18245-v2-JCTVC-C207.zip.

[4]ZHAO L，ZHANG L，ZHAO X.Further encoder improvement of intra mode decision [EB/OL].[2014-03-21].http://phenix.int-evry.fr/jct/doc_end_user/documents/4_Daegu/wg11/JCTVC-D283-v3.zip.

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

[6]JIANG W， MA H J，CHEN Y W.Gradient based fast mode decision algorithm for intra prediction in HEVC[C]//Proc.2nd International Conference on Consumer Electronics，Communications and Networks(CECNet 2012).[S.l.]：IEEE Press，2012：1836-1840.

[7]金智鹏，郁梅.用于移动终端的低复杂度快速模式选择算法[J]．计算机工程与应用，2014，50(5)：151-155.

[8]CHEN Wenjin，SU Jia，LI Bin.Reversed intra prediction based on chroma extraction in HEVC[C]//Proc.Intelligent Signal Processing and Communications Systems(ISPACS 2011).[S.l.]：IEEE Press，2011：1-5.

[9]ZHANG Mengmeng，ZHAO Chuan，XU Jizheng.An Adaptive fast intra mode decision in HEVC[C]//Proc.IEEE International Conference on Image Processing，2012.Orlando：IEEE Press，2012：221-224.

[10]成益龙，滕国伟，石旭利，等.一种快速 HEVC 帧内预测算法[J]．电视技术，2012，36(21)：4-7.

[11]蒋洁，郭宝龙，莫玮，等.利用平滑区域检测的HEVC帧内编码快速算法[J].西安电子科技大学学报：自然科学版，2013，40(3)：194-200.

[12]石飞宇，刘昱.一种HEVC快速帧内模式判断算法[J].电视技术，2013，37(11)：8-11.

[13]PATEUX S，JUNG J.An excel add-in for computing Bjontegaard metric and its evolution[S].2007.

金智鹏(1982— )，硕士，副教授，主研低复杂度视频编码技术；

代绍庆(1972— )，副教授，主要研究视频系统编码与质量评价；

曾 涛(1970— )，高级工程师，主要研究移动视频技术。

责任编辑：时 雯

Fast Intra Prediction Algorithm for HEVC Based on Classification-adaptively

JIN Zhipeng1，2，DAI Shaoqing1，ZENG Tao2

(1.InformationTechnologyBranchInstitute，JiaxingVocationalTechnicalCollege，ZhejiangJiaxing314036； 2.China(Jiaxing)Microsoft′sTechnologyResearchCenter，ZhejiangJiaxing314000)

In view of the high computational complexity of HEVC intra prediction， a new fast intra prediction mode decision algorithm based on classification-adaptively is proposed．Firstly， the algorithm dividing 12 candidate modes for the rough angular decision， then according to the results of preliminary judging， careful choice prediction mode. And according to theHCostprice excluding some modes of less likely， to speed up the intra prediction of HEVC.The experimental result tested in HM12.0 shows that， the proposed algorithm can reduce about 36.521% encoding time with drops of 0.041 dBBD-PSNR， improve the encoding speed significantly．And the algorithm has a strong adaptability and obvious effect for various test sequence with different size， different texture and motion characteristics， has good practical application value.

video coding；H.265/HEVC；intra prediction；mode decision；fast algorithm；early rule out

浙江省教育厅科研项目(Y201431212);嘉兴市科技计划项目(2013AY11028)

TN391.41

A

10.16280/j.videoe.2015.05.004

2014-04-28

【本文献信息】金智鹏，代绍庆，曾涛.分级自适应的HEVC帧内预测模式快速选择算法[J].电视技术,2015，39(5).