一种改进的HEVC编码单元划分方法

谢晓燕，王 欢，石鹏飞

(西安邮电大学 计算机学院,陕西 西安 710061)



·信息科学·

一种改进的HEVC编码单元划分方法

谢晓燕，王 欢，石鹏飞

(西安邮电大学 计算机学院,陕西 西安 710061)

针对高效率视频编码(HEVC)帧内预测中的率失真优化(RDO)算法计算复杂度高的问题，该文提出了一种基于统计学的率失真优化的改进方法。通过对不同量化参数的率失真代价概率分布图产生的阈值进行统计，得到最大编码单元(LCU)划分过程中不同深度的阈值方程，并利用该阈值提前终止编码单元的划分从而达到降低计算复杂度的目的。实验表明该文所提出的改进方法与HEVC的测试模型HM10.0相比，在保证视频质量和码率基本不变的前提下(码率仅增加了0.5%，Y-PSNR只降低了0.019dB)，减少了26.7%的编码时间，提高了编码效率。

HEVC；帧内预测；编码单元划分；率失真优化

近年来，数字视频已经成为许多电子应用媒体的主要形式[1]，高清晰率、高帧率、高压缩率的发展趋势愈加明显，而已颁布的视频标准H.264/AVC在这些方面呈现出一定的局限性[2]。因此在2010年1月，ITU-T VCEG(video coding experts group)视频编码专家组和ISO/IEC MPEG(moving picture experts group)运动图像专家组成立了JCT-VC(joint collaborative team on video coding)联合小组，制定了新一代高效率视频编码标准：HEVC(high efficiency video coding)[3]，其核心目的是在H.264/AVC的基础上，将压缩效率提高一倍[4]。HEVC的设计继续沿用了经典的基于块的混合编码方式，在编码结构上，HEVC放弃了H.264/AVC中宏块的概念，采用了具有四叉树结构的编码单元(CU)以及预测单元(PU)和变换单元(TU)。这使得HEVC的编码性能和效率得到显著的提高，但同时也增加了编码的复杂度。

HEVC的测试模型(HEVC Test Model)HM[5]是由JCT-VC编写的一个标准代码库，可以对不同的测试场景进行仿真编码。HM采用了递归的方式对最大编码单元(Largest CU, LCU)进行四叉树结构的划分[6]。在一个LCU块中，递归遍历所有深度的CU，根据拉格朗日率失真优化的策略选择最佳的CU尺寸，实现LCU与相关PU块的划分[7]。虽然这种全部遍历搜索的算法可以得到最优的编码参数，但是它仅根据图像的像素点信息进行LCU划分，并且大大的增加了计算复杂度[8]。近年来，在相关领域众多学者开展了大量优化研究来降低计算复杂度。文献[9]提出了自适应CU深度遍历的算法，利用空域相关性来预测当前编码块的深度值，而大部分的编码块还是要遍历3个CU以上的深度，所以该方法节省的时间相当有限。文献[10]采用时域空域相结合的预测方式，通过相邻编码块深度值加权方式来预测当前编码块的深度值。虽然这种方法在很大程度上减少了遍历范围，但没有考虑到不同视频序列之间的差异性，用固定权重求得的预测深度与预先设定的遍历区间仍存在一定的改善空间。文献[11]利用CU四叉树编码的特点，缩短了参考像素和预测像素间的距离，提高了帧内预测的精度，针对纹理丰富的图像，这种方法明显提高了编码效率，但对于一般的图像没有普适性。文献[12]提出了一种基于CU深度的快速算法，主要通过前一帧同一位置编码块(co-located CTU)和当前编码块的时间相关性来预测当前LCU的深度，使得编码时间平均减少了21.3%。但Lee的方法仅从时域考虑了co-located CTU的深度值对当前编码块的影响，可能会造成误判的偏差。文献[13]从帧内预测的角度出发，提出对CU自下而上的修剪进行预先判断来提前终止LCU的划分过程，但没有考虑到在有限的深度遍历区间上提前终止LCU划分。

目前，大部分的研究仅停留在用时域和空域的相关性来预测当前编码块的深度，关于对率失真代价的优化研究并未深入开展。本文通过对不同深度间的率失真代价进行相关统计研究，提出一种基于统计学的率失真优化的改进方法。该方法与HEVC的测试模型HM10.0相比，使得优化后的结果在基本不改变图像的质量与输出码率的情况下，编码时间平均减少了26.7%。

1 HEVC的CU划分编码过程

HEVC创新的采用了具有四叉树结构的编码单元CU来提高帧内编码精度，如图1所示。在HM编码器中，每一帧图像都从LCU的划分编码开始，LCU作为CU划分的根节点，其初始尺寸是64×64，深度Depth=0。通过对LCU进行预测编码，可以得到其率失真代价RD-Cost(rate distortion cost)。接着对LCU进行分割，得到4个子CU，每个子CU的大小为32×32，深度Depth=1，对这4个子CU再分别进行预测编码，得到各自的RD-Cost；如此递归的划分下去，直到子CU的大小为8×8，划分深度Depth=3时结束。

图1 CU的划分及对应的四叉树结构Fig.1 CU split and the quard-tree structure

HEVC采用拉格朗日率失真优化的策略决定LCU最终四叉树结构的划分形式。这样在不影响视频质量的前提下得到最小的输出码率。率失真是指编码的码率与图像失真度之间的相互关系,率失真代价函数J(CUd)定义如下

J(CUd)=SSE(s,c,m|QP)+

λ·R(s,c,m|QP)，

(1)

式中d是深度值,QP是量化参数,λ是拉格朗日乘子,R(·)是利用模式m进行编码的比特数,SSE(·)是原始亮度块与重建块之间的差值平方和,如式2所示

(2)

其中,BlockA(i,j)为当前编码块s的像素值,BlockB(i,j)为重建块c的像素值。

接着对已完成划分的LCU进行自下向上修剪,如图2所示。从Depth=3开始,如果4个8×8子CU的 RD-Cost之和小于其对应的16×16的父CU的 RD-Cost,则保留这个8×8的CU分割,否则继续往上修剪。以此类推,直至回溯到Depth=0。

图2 LCU的分割与修剪Fig.2 LCU splitting and prunning

采用 64×64的LCU四叉树划分方式比H.264采用的16×16宏块划分减少了12%的码率[14];然而,在HM模型中要想确定一个LCU的最终划分方式,则需要完成四叉树的全遍历,并进行40+41+42+43=85次CU尺寸选择的RD-Cost计算,且每个CU还需要进行各种PU预测和帧内模式选择的RD-Cost计算。这使得计算复杂度非常高,大大增加了编码时间。

2 基于统计学的率失真优化方法

针对前节中的分析,提出一种基于统计学的率失真优化改进方法,通过对不同QP下的RD-Cost概率分布图产生的阈值进行统计,得到LCU划分过程中不同深度的阈值方程,利用该阈值来提前终止CU的划分从而达到降低计算复杂度的目的。

通过在HM10.0上对视频序列进行测试,对不同深度的CU在分割和不分割的情况下进行穷举搜索,得到了RD-Cost概率分布图。从图3可以观察到:不进行分割的CU率失真代价值偏小;而进行分割的CU率失真代价值比较高并且分布比较均匀。由此说明,一个CU若不能分割成子CU,它肯定比已划分的CU拥有更小的RD-Cost值。因此,可以通过判断RD-Cost是否低于某一阈值,来提前终止不必要的CU划分。文献[13]说明此阈值VQP正好是两条曲线的交点所对应的率失真代价值,如图3的测试序列在CU划分深度Depth等于1时,其阈值VQP在35 000左右。图3测试条件:视频序列BQTerrace-1 920×1 080, QP=37,帧率60帧/s。

图3 Depth=1时CU分割与不分割RD-Cost概率分布图Fig.3 CU split and non-split RD-Cost probability distribution when Depth=1

因为不同的QP产生相应的RD-Cost概率分布,阈值一定随着QP的变化而变化。基于上述的分析,对HM10.0代码库中自带的18个通用视频标准序列设定不同的QP,按公式3进行统计,得到不同划分深度下的的阈值。

QP=0～51)

(3)

表1 不同深度的阈值表Tab.1 Threshold of different depth

为了能更直观的描述QP与ThDepth=i之间的关系,将表1绘制成图4所示的折线图,横坐标是量化参数QP,纵坐标是RD-Cost值,绘出的3条曲线分别是Depth等于0,1,2时的阈值。

从图4可以清晰的看到阈值随着QP增大而增大,Depth=0的曲线增长幅度最大,Depth=2的曲线增长幅度相对较小。其中的每条曲线都可以拟合为关于QP的指数函数,方程如下

ThDepth=0=1182e121·QP，

ThDepth=1=177.243e0.146·QP，

(4)

ThDepth=1=177.243e0.146·QP，

(5)

ThDepth=2=20.443e0.186·QP。

(6)

根据以上的实验分析,可以通过阈值来提早结束LCU的划分,改进后块划分的算法流程如下:

步骤1 计算Depth=0时LCU的RD-Cost值，记为RC0。

步骤2 判断RC0是否小于Depth=0时的阈值ThDepth=0；若RC0< ThDepth=0，则终止当前LCU划分，并对当前块进行预测编码，然后结束本次LCU划分编码；否则，直接跳过第0层编码，执行步骤3，进入第1层编码。

步骤3 进行一次四叉树划分，得到Depth=1时的4个子CU，并计算其RD-Cost值之和，记为RC1。

步骤4 判断RC1是否小于Depth=1时的阈值ThDepth=1；若RC1< ThDepth=1，则终止当前LCU划分，并对第1层CU进行选择和预测编码，然后结束本次LCU划分编码；否则，直接跳过第1层编码，执行步骤5，进入第2层编码。

步骤5 进行一次四叉树划分，得到Depth=2时的4个子CU，并计算其RD-Cost值之和，记为RC2。

步骤6 判断RC2是否小于Depth=2时的阈值ThDepth=2；若RC2< ThDepth=2，则终止当前LCU划分，并对第2层CU进行选择和预测编码，然后结束本次LCU划分编码；否则，直接跳过第2层编码，执行步骤7，进入第3层编码。

步骤7 进行一次四叉树划分，得到Depth=3时的4个子CU，进行块选择和预测编码，然后结束本次LCU划分编码。

3 仿真与验证

为了验证文中所提方法的有效性,将改进的方法集成到HEVC的测试环境HM10.0上,在全I帧的结构下,采用18个通用视频标准序列进行实验,量化参数QP取值点分别为:22，27，32，37,每个序列测试10帧。这里主要从所提方法带来的速度增益以及付出的相应代价——峰值信噪比与编码码率来考虑方法的性能,具体包括Δtime,Δbitrate和ΔY-PSNR[15]。

1)Δtime指本文所提出的方法与HM的编码时间之差的百分比,编码器计算复杂度的度量采用编码器平均执行时间的减少量Δtime表示,定义如下

Δtime=

(7)

2)Δbitrate指本文所提出的方法与HM的编码码率之差的百分比,定义如下

Δbitrate=

(8)

其中,bitrateproposed(QPi)表示文中方法的编码码率,bitrateHM(QPi)表示HM编码器得到的编码码率;编码码率越小说明视频图像的压缩效率越好。

3)ΔY-PSNR指本文所提出的方法与HM的峰值信噪比的百分比,定义如下

Y-PSNRpro(QPi)×100%。

(9)

其中，Y-PSNRpro(QPi)表示文中方法的亮度峰值信噪比，Y-PSNRHM(QPi)表示HM编码器得到的亮度峰值信噪比。PSNR表示视频图像的质量，PSNR越高，表明图像的质量越好。

由于本文的方法是通过跳过部分编码模式来达到减少计算复杂度的目的，所以从原理上讲选择出来的最终编码模式有可能不是最优的，必然会导致编码性能的降低，即峰值信噪比的下降或者输出码率增大。但是，所提出的方法在降低编码时间的同时只有极小的峰值信噪比PSNR下降和很小的码率bitrate增加。表2的数据可以看出本文所提出的方法与HM10.0相比，编码时间平均减少了26.7%,而bitrate仅增加了0.5%，Y-PSNR只降低了0.019dB，可见对视频图像质量的影响非常小，可以忽略不计。因此，本文的方法在保证视频质量和码率几乎不变的前提下，有效地降低了编码时间，提高了编码效率。

表2 节省的编码时间与编码质量的对比Tab.2 Differences of encoding time and coding efficiency

4 结 语

为了降低HEVC的计算复杂度， 本文提出了一种基于统计学的率失真优化方法，通过大量实验统计获得不同深度下的阈值，利用该阈值提前结束LCU的划分。实验结果证明本文的方法在保证视频质量和码率几乎不变的前提下，节省了26.7%的编码时间，提高了编码效率，为将来多视点、高效率视频编码的研究及应用打下基础。

[1] SHEN Li-quan, ZHANG Zhao-yang, AN Ping. Fast CU size decision and mode decision algorithm for HEVC intra coding[J].IEEE Transactions on Consumer Electronics,2013, 59(1):207-213.

[2] KIM J,CHOE Y,KIM Y G. Fast coding unit size decision algorithm for intra coding in HEVC[C]∥2013 IEEE International Conference Consumer Electronics(ICCE)，Piscataway:IEEE,2013:637-638.

[3] LAINEMA J, BOSSEN F, HAN W J,et al. Intra coding of the HEVC standard[J].IEEE Transactions on Circuits and Systems for video technology,2012, 22(12):1792-1801.

[4] 田小平,田永召. 面向交互应用的HEVC编码性能分析[J].西安邮电大学学报,2014,19(3):6-10.

[5] 严顺卿.HEVC帧内预测快速模式选择算法研究[D].上海：上海交通大学，2012.

[6] SULLIVAN G.J,OHM J,WOO-JIN Han,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-16 68.

[7] JIANG Gang-yi, YANG Xiao-xiang, PENG Zong-ju, et al. Fast CU depth range selection and early CU pruning for HEVC[J].Optics and Precision Engineering,2014,22(5): 1322-1330.

[8] WEI Jiang ,MA Han-jie, CHEN Yao-wu.Gradient based fast mode decision algorithm for intra prediction in HEVC[C]∥2012 2nd International Conference on CECNet,Piscataway:IEEE,2012:1836-1840.

[9] LI X, AN J C, GUO X, et al.Adaptive CU depth range[C]∥5th JCT-VC Meeting, Geneva:[s.n.], 2011.

[10] SHEN L Q, LIU Z, ZHANG X P, et al.An effective CU size decision method for HEVC encoders[J].IEEE Transactions on Multimedia, 2013, 15(2):465-470.

[11] CAO Xiao-ran , LAI Chang-cai , WANG Yun-fei, et al. Short distance intra coding scheme for HEVC[C]∥Proceedings of Picture Coding Symposium.[s.l.]: IEEE Press, 2012: 501-504.

[12] LEE H S, KIM K Y,KIM T R,et al.Fast encoding algorithm based on depth of coding-unit for high efficiency video coding[J].Optical Engineering,2012,51(6):1-11.

[13] CHO S,KIM M. Fast CU splitting and pruning for suboptimal CU partitioning in HEVC intra coding[J].IEEE Transactions on Circuits and Systems for Video Technology,2013,23(9):1555-1564.

[14] BAI Cai-xia, YUAN Chun. Fast coding tree unit decision for HEVC intra coding[C]∥2013 IEEE ICCE China Workshop,Piscataway:IEEE,2013:28-31.

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

(编 辑曹大刚)

An improved division method of HEVC coding units

XIE Xiao-yan, WANG Huan, SHI Peng-fei

(School of Computer, Xi′an University of Posts and Telecommunications, Xi′an 710061， China)

To further reduce the high computational complexity in High Efficiency Video Coding ( HEVC) intra prediction, an improved method of rate distortion optimization (RDO) based on statistics was proposed in this paper. Based on statistical analysis of the rate distortion cost under different quantization parameter probabilities distribution, threshold equations of different depths in the process of Large Code Unit (LCU) division were given, which were used to end the division of code unit, and then reduce the computational complexity. The experimental results show that, compared with HEVC HM10.0 testing models, the proposed algorithm can save an average 26.7% of encoding time with negligible loss of coding efficiency (only 0.5% bitrate increasing, and 0.0019 dB Y-PSNR(Y-Peak Signal-to-Noise Ratio) loss), promoting the coding efficiency.

HEVC, intra prediction; code unit division; rate distortion optimization

2014-03-11

国家自然科学基金面上项目(61272120);陕西省自然科学基础研究计划基金资助项目(2013JC2-32)

谢晓燕，女，陕西西安人，西安邮电大学副教授，从事视频编解码算法研究。

TN919.81

：ADOI：10.16152/j.cnki.xdxbzr.2015-03-009