基于提前终止编码单元划分的快速帧内预测算法

沈　健　杨　静

(上海海事大学　上海 201306)



基于提前终止编码单元划分的快速帧内预测算法

沈健杨静*

(上海海事大学上海 201306)

摘要为了降低高效视频编码HEVC(High Efficiency Video Coding)帧内预测过程的计算复杂度，提出一种提前终止编码单元(CU)划分的快速帧内预测算法。首先，针对HEVC编码结构，提出一种纹理复杂度测度的方法(即像素亮度方差值)。然后,分析不同纹理特性对帧内预测编码单元层次结构的影响，提出一种基于像素亮度方差值统计的提前终止编码单元的方法。对不同层次结构的编码单元进行像素亮度方差值统计，同时结合平均像素代价值统计，设置合理的阈值，自适应提前终止编码单元的划分，从而降低了帧内预测的编码复杂度。实验结果表明，在保证信噪比和比特率不变的情况下,该算法与HEVC参考软件HM10.0相比,编码时间平均节省32%。

关键词高效视频编码(HEVC)帧内预测编码单元纹理特性像素亮度方差值平均像素代价值

0引言

高效视频编码HEVC标准是目前最新的视频编码标准。由于采用了灵活递归的四叉树结构编码单元分割模式，用编码单元(CU)代替宏块(MB)，且采用了35种帧内预测模式，因此，与H.264/AVC标准相比，HEVC的码率可以减小一半。在HEVC标准中，对于不同尺寸的宏块所对应的预测模式的数量也是不同的，宏块尺寸的变化和预测模式数量的增加使HEVC的帧内预测更加准确，但同时也使编码复杂度显著增加。因此，减少帧内预测计算的复杂度是当前的一个研究热点。

针对H.264/AVC帧内预测高计算复杂度的问题， Yinbo Liu等人提出了基于空间域能量的快速帧内模式决策算法，通过计算16×16宏块的像素方差值和平均亮度值确定参数R，根据参数R判断16×16宏块的纹理特性，从而选择16×16,8×8,或者4×4的帧内预测模式。文献[2]中，Yunhui Shi利用像素方差值提出一种检测平滑区域纹理特性的快速帧内预测算法，根据平滑区域的纹理特性选择4×4或者16×16宏块的帧内预测模式，有效地减少了帧内预测计算的复杂度。在HEVC视频编码标准中，由于编码单元CU采用的是递归划分，且编码块的尺寸大小分别为64×64，32×32,16×16和8×8。因此，上述H.264/AVC标准中的帧内预测快速算法不能直接用于判断编码单元的纹理特性，提前终止编码单元的递归划分。

同样，针对HEVC帧内预测计算复杂度的问题，文献[3]中，Mingyuan Yang等人采用不同的方法分别提出了快速CU终止算法，快速PU(预测单元)决策算法，快速TU(变换单元)决策算法，该算法分别从编码单元，预测单元，变换单元三个方面对帧内预测过程进行优化，有效地减少了帧内预测计算的复杂度。文献[4]中，通过计算CTB的Sobel边缘密度的方法，Yet-Chuan Lin提出了一种提前终止CU递归划分的算法。胥加旺等人在文献[5]中，利用图像的纹理特性，分析不同深度下相邻编码块划分的相关性，提出提前终止编码块划分的一种帧内预测优化算法。文献[6]中，雷海军等人提出了一种快速HEVC编码单元决策算法,该算法统计当前编码单元和相邻编码单元的相关性，分析编码单元纹理复杂度，并设定合理的阈值，判断编码单元是否提前终止划分。文献[7]中，K.Saurty等人提出了通过定义并计算一个编码单元的平均像素代价值，减少CU的递归划分过程，该算法只通过平均像素代价值阈值判断CU是否进行递归划分，且只针对量化步长(QP)为32的CU划分过程有效。以上提出的HEVC帧内预测快速算法都是从不同的角度，通过判断编码单元的纹理特性，设置阈值，减少编码单元的递归划分,但这些算法都并未考虑通过分析编码单元像素亮度值的关系进行提前终止CU分割过程。

本文利用像素亮度值对帧内预测编码单元划分过程进行优化，提出了基于提前终止编码单元划分的快速帧内预测算法。首先，该算法通过统计不同视频序列CU深度分布特性，分析不同序列的纹理复杂度。然后，计算并分析64×64的LCU像素亮度方差值和深度为1时CU的平均像素代价值，提出基于纹理复杂度测度方法和基于APC提前终止编码单元划分的快速帧内预测算法。最后，通过设置合理的阈值，减少CU递归划分，在率失真性能没有明显下降情况下，减少编码时间，降低复杂度。

1HEVC帧内预测编码单元快速算法

1.1编码单元纹理特性分析

在HEVC标准中,由于纹理复杂的区域采用较小的编码块，纹理平缓的区域采用较大的编码块,因此,本文首先分析LCU的纹理复杂性,分别统测试序列 BasketballPass,Kimono,BQTerrace50个LCU的深度(0到3),统计结果如表1所示。

表1　LCU的划分深度

分析表1中的数据可以看出纹理特性相对平缓的视频序列Kimono和BQTerrace更多的分为深度为0的64×64块和深度为1的32×32块，而纹理复杂的视频序列BasketballPass则更多地分为深度为2的16×16块和深度为3的8×8的块。因此，基于不同纹理复杂度的视频序列与其对应的划分块深度关系的分析，本文提出一种判断纹理复杂度测度的方法，用来减少编码单元递归划分。

1.2提出基于纹理复杂度测度方法

对于64×64的LCU块，为了判断其纹理复杂性，本文提出的帧内预测算法首先将64×64块分割为16个16×16的块B0到B15，再将每个16×16的块进一步分割为更小的16个4×4的子块A0到A15，且每个4×4的子块分别包含16个像素P0到P15。一个LCU块的具体划分过程如图1所示。

图1　LCU划分示意图

如图1所示划分好LCU后，首先，计算每个16×16子块中256个像素的总和Sum1到Sum16，如式(1)所示：

(1)

然后，计算16个16×16块亮度像素平均值Var1到Var16，如式(2)所示：

(2)

得到每个16×16块的亮度像素平均值后，计算一个LCU的亮度像素平均值，如式(3)所示：

(3)

最后，计算LCU的像素亮度方差值，如式(4)所示：

(4)

分别统计测试序列BasketballPass,Kimono,BQTerracece50个LCU的像素亮度方差值，统计结果如表2所示。

表2　LCU像素亮度方差值

分析表2中的数据可以看出纹理特性复杂的视频序列BasketballPass的LCU像素亮度方差值较大，而纹理特性平滑的视频序列Kimono,BQTerrace的LCU像素亮度方差值相对较小。因此，本文所提出的基于计算LCU像素亮度方差值的方法可以判断不同序列的纹理复杂度。例如，对于16×16的块，可以通过判断LCU的像素亮度方差值是否超过阀值减少编码单元递归划分，而在LCU中，如果所有16×16块的深度均小于3，则可以提前终止递归划分。

1.3基于APC编码单元快速算法

在32×32的大小块是否进行递归划分的层次上，对100个LCU的像素亮度方差值进行统计，其中，包含深度为1的块的个数可能为1、2、3或者4，统计出现深度为1的块的LCU像素亮度方差值，结果如表3所示。

表3　32×32块的像素亮度方差值

对于纹理特性平滑的视频序列，从表3中可以看出，出现所有深度都为1的块的个数较多，且LCU像素亮度方差值差别不大。因此，用LCU的像素亮度方差值可以提前终止深度为1的CU递归划分。

然而，对于纹理特性复杂的视频序列，由表3中可以看出，几乎很少出现所有32×32块的深度都为1的情况，所以无法用像素亮度方差值判断深度为1的编码单元是否提前终止划分。原因是在32×32块的划分层次上，纹理特性复杂的序列基本上都要进行递归划分，所以出现所有深度都为1的个数很少。

因此，在对32×32的大小块是否进行递归划分的层次上，无法用LCU像素亮度方差值提前终止判断，所以，本文引入CU的平均像素代价值(APC)[7]对深度为1的CU逐个进行判断，如式(5)所示。

(5)

1.4提出的快速算法整体流程

对1.1节、1.2节以及1.3节提出的算法进行了整合，总的算法流程描述如下：

Step1depth=0时，如果像素亮度方差值小于阈值(S2

Step2depth=1时，如果平均像素代价值小于阈值(APC

Step3depth=2时，分析深度为1的32×32的块，统计其16个8×8的子块中CU的深度，如果含有深度为3的CU个数较少，则深度为2时16×16的块不进行递归划分，结合表1中CU深度分布特性和表2中的像素亮度方差值的关系确定深度为2时16×16的块是否递归划分的LCU像素亮度方差值阈值S12。如果LCU像素亮度方差值小于阈值(S2

2实验结果仿真

在HEVC参考软件HM10.0 上，对本文提出的基于提前终止编码单元划分的快速帧内预测算法进行仿真测试，使用的测试平台为：CPU为Intel(R)Core(TM)i3-3240 ,内存为4.00 GB。采用配置为encoder_intra_main的全I帧编码，编码帧数为100 frame，四个量化参数分别为22、27、32、37。算法性能的评价指标采用ΔBitrate, ΔPSNR和ΔT, ΔBitrate, ΔPSNR和ΔT的计算公式如式(6)-式(8)所示。

(6)

ΔP=PSNR本文算法-PSNRHM10.0

(7)

(8)

实验中采用5个纹理特性不同的通用测试序列进行测试,其中,Kimono,ParkScene,BQTerrace的测试序列纹理特性相对平滑，而测试序列RaceHorses,BasketballPass的纹理特性比较复杂。经过大量的实验测试，本文算法结果采用的阈值S02=5，APC0=12，S12=100，文献[7]中算法采用的阈值APC=25，所得的测试结果如表4、表5所示。

表4　本文算法实验结果

表5　文献[7]算法实验结果

续表5

表4是本文算法与HM10.0算法的实验数据比较，表5是文献[7]算法与HM10.0算法的实验数据比较。分析可知，本文算法在比特率增加约0.6%，PSNR值降低约0.05 dB的情况下，平均编码时间降低了约32%，且编码时间最多可以减少74.5%。而文献[7]中算法与本文算法相比较，虽然平均编码时间减少更多，但比特率显著增加，PSNR下降也更加明显。同时，对比表4和表5的实验结果，可以看出，在量化步长为22时，对于所有的测试序列，文献[7]中的算法比特率都显著增加，PSNR下降明显，且BasketballPass的测试序列，比特率增加甚至超过20%；而本文算法比特率几乎没有增加，PSNR下降很少。且对于不同量化步长的测试条件，相比于文献[7]中的算法，本文算法实验结果的差异性较小。

因此，本文提出的算法相比于文献[7]中的算法，虽然编码时间有一定的增加，但比特率增加明显减少，PSNR下降更少，且更适用于不同量化步长(QP)的情况。相比于HM10.0原始算法，本文算法在相同码率下，保持了较好的编码图像质量，尤其对于纹理特性较为平滑的视频(Kimono), 而对于纹理特性复杂的视频(BasketballPass),本文算法仍有较好的效果，具有较好的普适性。

3结语

本文首先简单介绍了最新的视频编码标准HEVC的帧内预测编码技术，然后，分析了不同视频序列的纹理特性,计算LCU的像素亮度方差值和深度为1的CU的平均像素代价值，进而提出基于纹理复杂度测度的方法和基于APC提前终止编码单元的帧内预测快速算法，通过合理设置LCU像素亮度方差阈值和深度为1时CU平均像素代价值阈值，减少CU的递归划分，降低了帧内预测计算的复杂度。最后，分别与HM10.0标准算法和文献[7]中的算法进行比较，本文提出的基于编码单元快速帧内预测算法在保持视频信噪比和码率稳定的前提下，有效地节省了帧内编码时间，同时，本文算法更适用于不同的量化步长。

（2）边坡系数为1∶1的表层无覆土无植草边坡60min内的土壤流失质量1.31kg，15～20，20～25，25～30mm植生混凝土组的底部土壤流失量分别为0.0792，0.1089，0.1584kg；植生混凝土对底部土壤的反滤拦截率达86.92%。

参考文献

[1] Liu Y,Liu X,Shen Z,et al.Fast Intra Mode Decision Algorithm Based on Spatial-Domain Energy for H.264/AVC[C]//Trust,Security and Privacy in Computing and Communications (TrustCom),2013 12th IEEE International Conference on.IEEE,2013:1357-1361.

[2] Shi Y,Cai H,Yin B.A fast and efficient intra mode decision algorithm for H.264/AVC[C]//Wireless Communications,Networking and Mobile Computing,2009.WiCom’09.5th International Conference on.IEEE,2009:1-4.

[3] Yang M,Grecos C.Fast intra encoding decisions for high efficiency video coding standard[J].Journal of Real-Time Image Processing,1-10.

[4] Lin Y C,Lai J C.Edge Density Early Termination Algorithm for HEVC Coding Tree Block[C]//Computer,Consumer and Control (IS3C),2014 International Symposium on.IEEE,2014:39-42.

[5] 胥加旺.基于HEVC帧内预测算法的优化[D].南京理工大学,2014.

[6] 雷海军,杨忠旺,陈骁,等.一种快速HEVC编码单元决策算法[J].计算机工程,2014,40(3):270-273.

[7] Saurty K,Catherine P C,Soyjaudah K M S.Early CU size determination in HEVC intra prediction using Average Pixel Cost[C]//Digital Information and Communication Technology and it's Applications (DICTAP),2014 Fourth International Conference on.IEEE,2014:247-252.

[8] Sullivan G J,Ohm J,Han W J,et al.Overview of the high efficiency video coding (HEVC) standard[J].Circuits and Systems for Video Technology,IEEE Transactions on,2012,22(12):1649-1668.

[9] Hao Zhang,Zhan Ma.Fast Intra Mode Decision for High Efficiency Video Coding (HEVC)[J].IEEE Transactions on Circuits and Systems for Video Technology,2013,24(4):660-668.

[10] 陈王焕.新一代高效视频编码帧内预测快速算法研究[D].中山大学,2012.

[11] 陶阳.面向高性能视频压缩的关键技术研究[D].国防科学技术大学,2007.

FAST INTRA PREDICTION ALGORITHM BASED ON EARLY TERMINATION OF CODING UNIT

Shen JianYang Jing*

(ShanghaiMaritimeUniversity,Shanghai201306,China)

AbstractThis paper presents a fast intra prediction algorithm which is based on early termination of coding unit (CU) partition in order to reduce the computational complexity of intra prediction process in HEVC. First, aiming at HEVC coding structure we put forward a texture complexity measurement method (i.e. the pixel luminance variance value). Then we analysed the influences of different texture features on CU hierarchical structure of intra prediction, and gave a new method for early termination of CU based on pixel luminance variance value statistics. By counting the luminance variance value of coding units with different hierarchical structure and in combination with counting the average pixel cost value, we set the reasonable threshold to adaptively terminate the CU partition early, so that reduced the coding complexity of intra prediction. Experimental results showed that comparing with the reference software HM10.0 of HEVC, the algorithm reduced the encoding time by 32% in average with negligible changes in PSNR and bit rate.

KeywordsHigh efficient video coding (HEVC)Intra predictionCoding unit (CU)Texture featurePixel luminance variance valueAverage pixel cost value

收稿日期：2015-01-09。国家自然科学基金项目(61402278)；上海市国际科技合作基金项目(12510708400)。黄志勇，工程师，主研领域：图像处理。陈一民，教授。 2014-12-16。国家自然科学基金项目(61404083)。沈健，硕士生，主研领域：图像通信与视频压缩编码。杨静，副教授。

中图分类号TP3

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.042