HEVC帧内预测编码的快速CU决策算法

吴良堤， 冯桂

(华侨大学 信息科学与工程学院， 福建 厦门 361021)

HEVC帧内预测编码的快速CU决策算法

吴良堤， 冯桂

(华侨大学 信息科学与工程学院， 福建 厦门 361021)

提出一种快速编码单元(CU)修剪方法和CU深度范围决策方法.在快速CU修剪方法中，根据贝叶斯决策准则,基于残差信息Hadamard变换绝对值之和(SATD)提前结束CU的修剪；在CU深度范围决策方法中，根据当前CU深度与空间邻近CU深度的相似性决策当前CU深度级范围.通过在HM10.1的实验证明：文中方法相比于HM10.1的标准代码，能降低35.9%的编码时间，且BDBR的增加仅为1.039%. 关键词： 高效视频编码; 帧内编码; 编码单元; 残差信息; Hadamard变换

2013年，JCT-VC制定了高效视频编码(HEVC)，它采用混合编码结构[1].HEVC引入了新的编码工具，使其具有更高的压缩能力，同时也导致了编码复杂度的提高.为了提高HEVC的实时性，研究者们提出了3类快速帧内编码算法：快速CU尺寸决策算法、快速模式决策算法和RQT优化算法.在快速CU尺寸决策算法上，Shen等[2]将CU分割公式化，提出基于贝叶斯准则的快速CU决策；Shen等[3]根据邻近CU提出一个预测当前CU深度的公式，跳过某些CU深度级搜索；Kim等[4]设定一个基于RD代价的阈值来提前终止当前CU的分割；Xu等[5]利用灰度级自相关函数来决策当前CU的深度范围，同时利用固定的残差信息Hadamard变换绝对值之和(SATD)作为阈值来提前终止CU修剪过程.在快速模式决策算法方面，Ting等[6]采用了变换域的边缘检测法，减化RMD模式个数；Fang等[7]通过计算特定角度的方向能量减少进行RMD过程的预测模式；Yan等[8]通过对RMD后的模式进行分组合并，减少RDO侯选模式个数.在RQT优化算法中，Teng等[9]利用合并分割决策过程代替原来的深度优先模式决策过程；Zhang等[10]根据不同尺寸CU的最大帧间RQT深度在编码性能上不相同，提出一种帧间模式的自适应RQT选择.上述算法在测试中都取得了一定的效果.Cho等[11]提出以RMD后的代价和RDO后的代价为阈值，利用贝叶斯准则自适应地对CU进行快速修剪和分割.基于此，本文以SATD为阈值，利用贝叶斯准则来自适应地提前终止CU修剪过程.

(a) CU的分割 (b) 四叉树结构 图1 CU的分割及对应的四叉树结构Fig.1 Partitioning CU and corresponding quadtree structure

1 HEVC帧内预测编码概述

HEVC编码中引入3种单元：编码单元(CU)、预测单元(PU)和变换单元(TU).相对于H.264固定大小的宏块，HEVC提供的CU尺寸从64×64到8×8，对应深度(Depth)级分别从0到3.CU的分割及对应的四叉树结构，如图1所示.在HEVC测试模型(HM)中，帧内预测编码主要由CU分割和CU修剪完成.CU分割过程如下：首先，CU从Depth=0开始进行预测编码，获得率失真代价(RD Cost)；然后，将CU分割成4个等大的子CU，此时Depth=1，并对当前CU进行预测编码得其RD Cost；以此类推，直至CU深度为3时，结束分割.

CU修剪过程如下：从Depth=3的CU开始，比较4个8×8子CU的RD Cost之和是否小于其父CU的RD Cost，若小于，则选择子CU；否则，选择父CU；以此类推，直至Depth=0.32×32 CU的分割与修剪示意图，如图2所示.图2中：灰色阴影为修剪过程;其他为分割过程.

HEVC帧内预测提供了35种预测模式，如图3所示.帧内模式决策过程:首先,进行粗选择(RMD),即对35种预测模式进行低复杂度的RD Cost计算，选出其中代价最小的N个，作为率失真优化(RDO)的初始候选模式集;然后，判断MPMs是否包含在初始候选模式集中，若不包含则将相应模式添加到RDO初始候选模式集中，反之，则不添加;其次,对N到N+2个侯选模式用式(1)计算RD Cost，选出其中RD Cost最小的作为最佳预测模式;最后，利用RQT来得到最佳TU尺寸，即

(1)

式(1)中：SSE表示原始图像块与预测图像块差的平方和；λmode为拉格朗日乘子；Rmode为编码预测模式信息所需的比特数.

图2 32×32 CU的分割与修剪 图3 帧内预测模式及方向 Fig.2 32×32 CU splitting and CU pruning process Fig.3 Intra prediction modes and directions

2 快速帧内CU尺寸决策算法

帧内预测编码复杂度增大的原因主要有两方面：CU分割与修剪的复杂化和模式决策的复杂化.为了降低帧内编码的复杂度，根据当前LCU与空间邻近LCU深度的相似性，缩小LCU分割的深度范围，同时提出了基于贝叶斯准则利用SATD提前结束CU修剪过程.

图4 当前LCU的空间邻近LCUFig.4 Spatial neighbor LCU of current LCU

2.1 空间邻近LCU决策当前LCU深度范围

2.1.1 观察与分析 在帧内预测中，LCU分割深度级与图像纹理有很大的关系.进一步分析可知：当前LCU的分割深度级与空间邻近(左边、上边、左上、右上)LCU的分割深度级具有极大的相似性.当前LCU与空间邻近LCU 的空间位置关系,如图4所示.

为了量化空间邻近LCU与当前LCU深度的相似度，定义相似度计算公式为

(2)

式(2)中：cur(i)为当前第i个LCU的深度；nei_X(i)为与当前第i个LCU邻近(X=L表示左邻近，以此类推)的LCU的深度；N为统计的当前LCU的总个数；SL，SU，SLU，SRU分别为与当前LCU左邻近、上邻近、左上邻近和右上邻近LCU的相似度.当前LCU的深度与邻近LCU的深度相等时，cur(i)=nei_X(i)为1；否则为0.因此，SX的取值为[0，1].

经过上述定义后，取各分辨率的序列，计算当前LCU与各邻近LCU的相似度.每个序列在不同的量化参数下编码，量化参数选择为22，27，32，37.其中：PeopelOnStreet，Cactus，BasketballDrill，BasketballPass属于纹理复杂、运动较剧烈的序列；Traffic，BQMall，BQSquare属于纹理较均质、平坦，运动变化较小的序列；FourPeople，AristenAndSara属于背景较简单、前景较复杂的序列.得到当前LCU与邻近LCU相似度SL，SU，SLU，SRU分别为0.795，0.794，0.788，0.763.由此可知:当前LCU与左邻近LCU、上邻近LCU、左上邻近LCU、右上邻近LCU的相似度呈递减趋势.因此，可以利用空间邻近LCU的深度级跳过当前LCU不太可能的深度级搜索.

2.1.2 算法内容 记当前LCU空间邻近4个LCU的深度分别为：LDepth(左边)、UDepth(上边)、LUDepth(左上)、RUDepth(右上).

将LDepth，UDepth，LUDepth，RUDepth的异同分两大类：LDepth，UDepth，LUDepth，RUDepth有任意两个深度相等；LDepth，UDepth，LUDepth，RUDepth的深度级各不相等.

对于第一大类，又可分成两小类：LDepth≠UDepth和LDepth=UDepth.当LDepth=UDepth时，当前LCU有极高的可能性选择与其相同的深度级作为当前LCU的最佳分割深度级.为了减少这种情况引起的编码性能的损失，增加一个额外的深度级进行搜索.此额外深度级e_Depth定义为

(3)

当LDepth≠UDepth时，可通过判断空间邻近LCU各深度级的个数决策当前LCU的深度级搜索.若空间邻近LCU中深度0和深度1的个数之和多于深度2和深度3的个数之和，则将当前LCU搜索深度级最大值设为2；反之，则将当前LCU搜索深度级最小值设为1.

表1 空间邻近LCU预测当前LCU深度范围命中率Tab.1 Hit-ratio of spatial neighbor LCU to predicted depth of current LCU

对于第二大类，当LDepth,UDepth,LUDepth只要有一个的深度为3，此时当前LCU选择深度级0为最佳分割的概率非常小.因此,将当前LCU的深度级最小值设为1；反之，将当前LCU的深度级最大值设为2.

为了证明上述算法中利用空间邻近LCU深度预测当前LCU深度搜索范围的合理性，取与上述一致的测试序列，统计其命中率.统计结果如表1所示.通过表1分析可知：利用空间邻近LCU跳过当前LCU不必要的深度级搜索，平均命中率达到了94.1%，足以说明所提出的利用空间邻近LCU决策当前LCU的深度范围能精确、有效地排除不必要的深度级搜索.

由上帧内预测编码概述可知，HEVC引入了RMD算法，其计算代价表示为

(4)

式(4)中：SATD为残差信息绝对Hadamard变换之和；λpred为拉格朗日乘子；Rpred为编码预测模式信息所需的比特数.SATD的定义为

(5)

式(5)中：N为残差信息块的大小；di,j为残差信息经Hadamard变换后位于(i,j)的值,其定义式为

(6)

式(6)中:S为原始图像块；C为重构图像块；H为Hadamard矩阵.

2.2.1 动机与统计 将当前CU不分割标记为w1，分割标记为w2，则由贝叶斯公式可得

(7)

式(7)中：P(SATD|wj)为在已知分割(或不分割)下SATD的条件概率；P(wj)为分割(或不分割)的先验概率，表示为

(8)

P(SATD)表示SATD的先验概率，表示为

2004年，为了开拓外部市场，李淑荣被公司选派为新组建的南方项目组组长，负责川东北地区测井解释及方法研究工作。尽管有着丰富的工作经验和骄人的工作业绩，但摆在李淑荣面前的，不仅是川东北油区井深、含气井段长、多含硫化氢等复杂的地质条件，还有和其他同行同台竞技、抢夺市场份额的激烈竞争。困难面前,李淑荣与她的团队选择迎难而上。

(9)

由式(7)可知：为了利用贝叶斯准则判断当前CU分割与否，需先统计相关的参量，如表2所示.

表2 各CU级下需获取的参数Tab.2 Needed parameters in each CU depth level

为使算法具备较好的适应性，文中相关参量都是在线周期性更新，更新周期为帧率.

如同文献[11]的JSATD服从高斯随机分布，文中也先假设SATD服从高斯分布.从这一假设出发，统计了SATD与P(SATD|w2)，SATD与P(SATD|w1)的关系.经过使用各种测试序列进行大量的实验，证明了SATD近似服从高斯分布.以BasketballDrill这一序列为例，其中,SATD以200为间隔，统计了QP=37,深度为2时的实际分布，并给出其拟合的高斯模型，如图5所示.

(a) P(SATD|w2) (b) P(SATD|w1)图5 BasketballDrill序列的RDcost实际分布及其拟合高斯模型Fig.5 BasketballDrill sequence actual distribution of RD cost and fit Gaussian distribution

2.2.2 阈值的计算 CU提前修剪的贝叶斯决策，如图6所示.由图6可知：αST表示在CU继续分割时被判断为不再分割的概率.在每一个CU的深度级上，当最小SATD小于预设阈值SATD_TH时，则执行提前修剪算法.由图6易得

图6 CU提前修剪的贝叶斯决策Fig.6 Bayes decision for early CU pruning

(10)

式(10)中:x=SATD.将式(10)变换为

(11)

(12)

式(12)中：z为服从标准正态分布变量积分的上界，可由查找标准正态分布表得到其值.即

(13)

大量实验证明，取αST=0.1时，在编码时间与码率损失之间可以达到较好的平衡.

3 结果与分析

文中提出的快速帧内CU尺寸决策算法在HM10.1上实现.实验配置参照文献[12]，使用QP=22，27，32，37，LCU尺寸为64×64，最大深度级为4.测试使用JCT-VC推荐的5个类别序列：ClassA，ClassB，ClassC，ClassD，ClassE.所用计算机处理器为AMD Athlon(tm)2×2 B28.使用BDBR，BDPSNR[13]来衡量编码性能，用平均节省时间(ATS)来衡量编码复杂度的降低,即

(14)

式(14)中：TimeHM10.1(QPi)，Timepro(QPi)分别为原始HM10.1与文中算法在不同QP下的编码时间.

文中算法与文献[3]，[4]比较的实验结果，如表3所示.文中算法与文献[5]ClassE测试序列的对比结果，如表4所示.

表3 文中算法与文献[3],[4]算法比较结果Tab.3 Performance comparison between proposed and literature [3]，[4]

表4 文中算法与文献[5]算法ClassE测试序列的比对Tab.4 Coding performance compared with ClassE in literature [5]

通过表3可知：文中算法平均能节省35.9%的编码时间，引起1.039%的BDBR增加.同时，从表3中可以发现：相较于文献[3]，文中算法以增加微量的BDBR为代价，平均多节省了14.5%的编码时间；与文献[4]相比较，文献[4]算法对ClassE的测试序列码率增加比较大，平均为3.339%；而文中算法对18个测试序列编码性能的损失都没那么严重，最大仅为1.654%；同时可以发现两者的平均率失真性能几乎相等，但文中算法编码时间减少的更多，平均多降低了3.4%.这说明文中算法与文献[4]相比，所有的测试序列都能在编码时间与码率之间达到更好的平衡.

由表4可知：虽然文中算法在编码时间降低上略有不足，但其对ClassE序列平均BDBR的增加为1.654%；而文献[5]对ClassE序列平均BDBR增加了4.765%，在Johnny测试序列中达到了7.565%这是比较难以接受的.通过这一点的对比，更能突显出文中算法对序列的自适应性.

4 结束语

提出了基于贝叶斯准则使用SATD提前终止CU修剪过程，同时利用空间邻近LCU与当前LCU深度级的相似性决策当前LCU深度范围的快速CU尺寸决策算法.该算法相比于原本的HM10.1，平均能节省35.9%的编码时间，而引起的平均码率增加只有1.039%.下一步的研究方向主要是在帧内模式决策上进行改进，从而获得更大的编码复杂度降低.

[1] SULLIVAN G J,HAN W J,WIEGAN D T.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] SHEN Xiaolin,YU Lu,CHEN Jie.Fast coding unit size selection for HEVC based on Bayesian decision rule[C]∥Picture Coding Symposium.Krakow：IEEE Press，2012:453-456.

[3] SHEN Liquan,ZHANG Zhaoyang,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.

[4] KIM J,CHOE Y,KIM Y G.Fast coding unit size decision algorithm for intra coding in HEVC[C]∥IEEE International Conference on Consumer Electronics.Las Vegas:IEEE Press,2013:637-638.

[5] XU Dongxu,LIN Qiwei,DONG Xiaohui.Fast intracoding unit size decision algorithm for high-efficiency video coding[J].Journal of Electronic Imaging,2014,23(1):013012.

[6] TING Y C,CHANG T S.Fast intra prediction algorithm with transform domain edge detection for HEVC[C]∥IEEE Asia Pacific Conference on Circuits and Systems.Kaohsiung:IEEE Press,2012:144-147.

[7] FANG Cemin,CHANG Yuanteng,CHUNG Wenhao.Fast intra mode decision for HEVC based on direction energy distribution[C]∥IEEE 17th International Symposium on Consumer Electronics.Hsinchu:IEEE Press,2013:61-62.

[8] YAN Shunqing,HONG Liang,HE Wei-feng,etal.Group-based fast mode decision algorithm for intra prediction in HEVC[C]∥Eighth International Conference on Signal Image Technology and Internet Based Systems.Naples:IEEE Press,2012:225-229.

[9] TEND S W,HANG H M,CHEN Y F.Fast mode decision algorithm for residual quadtree coding in HEVC[C]∥IEEE Visual Communications and Image Processing.Tainan:IEEE Press,2011:1-4.

[10] ZHANG Yongfei,ZHAO Mingfei.An adaptive RQT mode selection algorithm for HEVC[C]∥5th International Congress on Image and Signal Processing.Chongqing:IEEE Press,2012:173-177.

[11] 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.

[12] BOSSEN F.Common HM test conditions and software reference configuration[C]∥12th JCT-VC Meeting.Geneva:JCTVC-L1100,2013:1-3.

[13] BJONTEGAARD G.Calculation of average PSNR difference between RD-curves[C]∥13th VCEG-M33 Meeting.Austin:[s.n.],2001：290-294.

(责任编辑： 黄晓楠 英文审校： 吴逢铁)

Fast CU Decision Algorithm for HEVC Intra Prediction Coding

WU Liangdi， FENG Gui

(College of Information Science and Engineering, Huaqiao University, Xiamen 361021, China)

In this paper, a fast coding unit (CU) pruning and depth levels decision method is proposed. The early CU pruning method is performed according to a Bayes decision rule method based on the absolute sum of Hadamard transformed coefficients of the residual signal (SATD). Based on the depth information resemblance between spatio adjacent CUs and the current CU, some depths can be excluded. Experimental results show that the proposed algorithm achieves 35.9% encoder time saving on average compared to the original coding in HM10.1 with only 1.039% bit rate increment in coding performance.

high efficiency video coding; intra coding; coding unit; residual information; absolute sum of Hadamard transformed

10.11830/ISSN.1000-5013.201704021

2016-09-04

冯桂(1960-)，女，教授，博士，主要从事图像信息处理的研究.E-mail:fengg@hqu.edu.cn.

福建省自然科学基金资助项目(2014J01242, 2016J01306)

TN 919.81

A

1000-5013(2017)04-0556-06