纹理的HEVC编码块尺寸决策算法

张聪聪，李子印，应凌楷，郭笙听

(中国计量学院 光学与电子科技学院，浙江 杭州 310018)



纹理的HEVC编码块尺寸决策算法

张聪聪，李子印，应凌楷，郭笙听

(中国计量学院 光学与电子科技学院，浙江 杭州 310018)

【摘要】针对高效视频编码(HEVC)帧内编码算法计算复杂度高的问题，提出了一种基于纹理的HEVC编码块尺寸快速决策算法.首先，提出了编码块四个方向的纹理复杂度衡量指标，再通过训练视频序列选取在不同量化参数(QP)下的最佳阈值，最后根据阈值判断当前编码块的纹理复杂度，纹理复杂度高的编码块跳过率失真(RD)代价的计算，纹理复杂度低的编码块将会终止划分.实验结果表明，在全帧内模式配置下，与HM10.0相比较，该算法的编码时间可缩短45.3%，同时BD-Bitrate(Bjontegaard Delta Bitrate)增加了1.27%，BD-PSNR(Bjontegaard Delta Peak Signal-to-noise Rate)减少了0.058 dB；与GEC-LEC算法相比，编码时间可节省3%，BD-Bitrate增加了0.5%，BD-PSNR减少了0.023 dB.

【关键词】高效视频编码；纹理复杂度；编码块尺寸

随着人们对高清和超高清视频需求的不断增加，H.264编码技术在编码效率上已经不能满足需求.另外，手机和电脑产生的海量视频流量及视频的实时传输，对当今的网络提出了巨大的要求和挑战[1].

视频编码技术是一种对视频信息去除信息冗余，从而进行有效压缩、存储和网络传输的技术.为了提高编码效率，ITU-T和ISO/IEC 联合制定了新一代高效视频编码(HEVC)标准.与H.264/AVC相比，HEVC支持更大的编码深度和更大的编码块，以及更多的帧内预测模式.HEVC支持的最大编码块的大小为64×64，定义其深度为0，最小编码块的大小为8×8，定义其深度为3，其余大小为32×32、16×16的编码块，其深度分别为1和2；而H.264支持的最大编码块为16×16的宏块[2].HEVC的帧内预测模式增加到了35个模式[3]，而H.264只有8个帧内预测模式.由于HEVC有更大的编码深度和更多的帧内预测模式，以及基于四叉树递归编码方式，从而保证了HEVC帧内编码的高效性.HEVC采取基于四叉树递归划分方式来决定编码块的最终大小[4]，这种编码块递归划分的方式，需要递归计算所有深度编码块的代价，因此，HEVC的帧内编码时间长于H.264的帧内编码时间.在保持HEVC编码效率基本不变的前提下，缩短编码时间，提出HEVC帧内编码块尺寸的快速决策算法是相当必要的.

现有的HEVC帧内编码块尺寸的快速决策算法大体上分可为三类：1)裁剪帧内预测模式的算法；2)编码块递归划分提前终止或跳过的算法；3)裁剪帧内预测模式算法和编码块提前终止或跳过算法相结合的算法.Tian等人[5]首先把64×64大小的编码块下采样成16×16的块，通过计算16×16块内部的变化情况来决定编码块的最终大小，与HM4.0相比，编码时间平均可节省28.8%；Nishikori等人[6]提出了基于方差的编码块递归划分提前终止的快速算法，与HM8.0相比，其编码时间平均可节省55%，BD-Bitrate平均增加了0.64%，但是只测试了六个视频序列；Khan等人[7]基于香农公式，提出了一种PUMA的编码块尺寸快速决策算法，与HM7.2相比，其编码时间平均可节省43.7%，BD-Bitrate平均增加了1.27%，但是只测试了七个视频序列；Kim等人[8]统计了所有编码深度的率失真代价，提出了一种编码块递归划分提前终止的快速算法，与HM5.2rc1相比，其编码时间平均可节省24%，BD-Bitrate平均增加了0.83%；Zhang等人[9]提出了一种基于Hadmard代价的编码块递归划分提前终止的快速算法，与HM7.0相比，其编码时间平均可节省32%，BD-Bitrate平均增加了1.1%；Shen等人[10-11]提出了ADRD和ET-SCUME的快速分块算法，与HM2.0相比，其编码时间平均可节省42%，BD-Bitrate平均增加了1.49%；Min等人[12]提出了基于GEC-LEC的编码块递归划分提前终止和跳过的快速算法，与HM10.0相比，其平均编码时间可节省43.2%，BD-Bitrate平均增加了0.74%；Lim等[13]提出了一种基于相邻编码块编码深度和RMD代价的编码块尺寸快速决策算法，与HM14.0相比，其ΔBitrate增加了1.18%，平均编码时间缩短了44.05%.

综上所述，在控制编码效率基本不变的条件下，HEVC编码块尺寸快速决策算法的计算复杂度还需进一步提升以适应实时编码的需求.本文提出了基于方向性纹理的HEVC编码块尺寸快速决策算法，定义了编码块水平、垂直、45°和135°这四个方向纹理复杂度的衡量指标，通过大量视频序列的训练选取最优阈值，并对提案[14]中所提到的所有的视频序列(除Nebuta和SteamLocomotive两个视频序列外)进行了测试.

1基于方向性纹理的HEVC编码块尺寸快速决策算法

1.1纹理复杂度函数的提出

文献[10]指出，纹理丰富的编码块通常有更大的编码深度，平坦的区域有较小的编码深度.图1为QP=32时，全帧内模式配置下,原始HM10.0对BasketballDrive的最终划分结果，可以看出其对纹理复杂的视频区域会以更小的编码块进行编码，对纹理简单的视频区域会以更大的编码块进行编码.

图1　当QP=32时，原始HM10.0对BasketballDrive的最终划分结果Figure 1　Final CU partition given by HM-10.0 under all-intra-main test configuration with QP= 32 when applied to encode the first frame from the sequence BasketballDrive

在H.264中，文献[15-16]提出了一种衡量编码块纹理复杂度的指标如下式：

(1)

(2)

1.2提出的HEVC编码块尺寸快速决策算法

GEC-LEC算法同时运用了Global算子和Local算子来决定编码块的最终大小，Global算子描述了编码块全局的变化情况，Local算子描述了编码块局部的复杂程度，将两者进行结合，可以准确地描述编码块的纹理信息，但有较高的计算复杂度.本文将Global算子和Local算子相融合，提出了计算复杂度更低的基于编码块四个方向复杂度的衡量指标如式(3～6)所示，并将其只用于当前编码块来决定当前编码块的最终大小.

(4)

其中

(5)

其中

(6)

(7)

(8)

图2　本文提出的算法流程图Figure 2　Flowchart of the proposed algorithm

图2为本文提出的编码块尺寸快速决策算法的流程图.本文算法首先通过计算当前编码块的水平、垂直、45°和135°这四个方向的纹理复杂度，根据纹理复杂度可以对当前编码块做如下判定：

(9)

其中，ThrDepth为深度为Depth(取值为0，1，2，3)的编码块所选取的阈值，complexity为当前编码块的纹理复杂度.如果当前编码块纹理复杂度被判定为High，则其被认为是一个纹理复杂的编码块，被判定为复杂纹理的编码块将会以更大的编码深度进行编码，跳过当前编码深度的率失真代价的计算，从而可以减少编码的计算复杂度；如果当前编码块纹理复杂度被判定为Low，则当前编码块被认为是一个纹理简单的编码块，被判定为简单纹理的编码块将会以当前深度进行编码，大于当前深度编码块的递归计算将会被终止，从而减少了编码的计算复杂度.否则，通过计算率失真代价来决定当前编码块的最终划分.

1.3阈值选择分析

本文提出的算法性能很大程度上依赖于阈值的选取，选取最优化的阈值是发挥本文算法优势相当关键的一步.如果阈值太小或者太大，编码块最终划分结果与HM10.0相比，错误命中率都会偏高.文献[8]指出，错误命中率与BD-Bitrate几乎成线性关系，错误命中率越小，BD-Bitrate就会越小.

本文首先从ClassB-F中共选出7个视频序列作为训练样本，计算了当QP=22，27，32，37时，7个视频序列的平均错误命中率与阈值之间的关系曲线如图3.平均错误命中率越低，则表明本文算法的编码块划分结果与HM10.0的更为接近，进一步说明平均错误命中率最低时的阈值可以更精确的区分编码块的复杂程度，从而可以提早对编码块的大小进行跳过或终止的决策.

当QP=22，27，32，37时，本文选取7个视频序列(Cactus,BasketballDrive,PartyScene,RaceHorses,BQSquare,FourPeople和SlideShow)的平均错误命中率最小时的阈值作为最优阈值.当QP=22，27，32，37时, 本文最终选取的阈值ThrDepth如下式：

(10)

其中Depth为编码块的深度，取值为0，1，2，3.

图3　平均错误命中率与阈值之间的关系曲线　Figure 3　Relationship between the average wrong hit rate and threshold

2测试结果及比较

本文算法是在HM10.0平台上进行了算法改进的，算法的测试条件参考了提案[14]，测试的视频序列包含了提案[14]中提到的Class A-F这六个序列.算法测试时，我们测试了视频序列第一帧所用的编码时间，对第一帧编码10次求取该帧平均所用的编码时间，节省的编码时间ΔTS用下式去衡量：

(11)

本文算法的编码效率是用BD-Bitrate和BD-PSNR来衡量的，它们的计算参考了提案[17].本文算法是在AI-Main配置下，在Intel Core i3-2120CPU @3.30GHz 5.0GB RAM Windows 7操作系统，VS2010的实验环境中进行测试的，测试结果详见表1.测试结果表明，与HM10.0相比，本文提出的算法可以减少45.3%的编码时间，同时BD-Bitrate增加1.27%.本文算法也与GEC-LEC算法[12]进行了比较，编码时间可节省3%，BD-Bitrate增加了0.5%，BD-PSNR减少了0.023 dB.由于本文中用来衡量纹理复杂度算子的计算复杂度更低，而且只需要计算当前编码块的纹理复杂度.因此，本文提出的算法在保持编码效率几乎不变的情况下，在编码时间的节省上具有一定的优势.

表1　在全帧内模式配置下，本文算法与HM10.0的算法性能比较

3结论

本文基于编码块四个方向的纹理复杂度提出了一种编码块尺寸快速决策算法.该算法计算了当前编码块四个方向的纹理复杂度，通过训练选取最优阈值，根据阈值决定当前编码块的最终大小.在QP=22，27，32，37时，本文选取所有训练视频序列的平均错误命中率最低时所对应的阈值作为最优阈值.实验结果表明，与HM10.0相比较，本文提出的算法可以减少45.3%编码时间，同时BD-Bitrate增加了1.27%，BD-PSNR减少了0.058 dB；与GEC-LEC算法相比，编码时间可节省3%，BD-Bitrate增加了0.5%，BD-PSNR减少了0.023 dB.因此，本文提出的算法在保持编码效率几乎不变的情况下，在编码时间的节省上具有一定的优势.

【参考文献】

[1]SULLIVAN G J, OHM J R, HAN W J, et al. Overview of the high efficiency video coding standard[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(12): 1649-1668.

[2]DE JESUS OCHOA DOMINGUEZ H, VERGARA VILLEGAS O O, CRUZ SANCHEZ V G, et al. The h.264 video coding standard[J]. IEEE Potentials,2014,33(2):32-38.

[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]KIM I K, MIN J, LEE T, et al . Block partitioning structure in the hevc standard[J]. IEEE Transactions on Circuits and Systems for Video Technology,2012,22(12):1697-1706.

[5]TIAN Guifen, GOTO S. Content adaptive prediction unit size decision algorithm for hevc intra coding[C]//29th Picture Coding Symposium (PCS). Krakow: IEEE,2012:405-408.

[6]NISHIKORI T, NAKAMURA T, YOSHITOME T, et al. A fast cu decision using image variance in hevc intra coding[C]//IEEE Symposium on Industrial Electronics and Applications (ISIEA). Kuching: IEEE,2013:52-56.

[7]KHAN M U K, SHAFIQUE M, HENKEL J. An adaptive complexity reduction scheme with fast prediction unit decision for hevc intra encoding[C]//20th IEEE International Conference on Image Processing (ICIP). Melbourne: IEEE, 2013: 1578-1582.

[8]KIM J H,CHOE Y, KIM Y G. Fast coding unit size decision algorithm for intra coding in hevc[C]//IEEE International Conference on Consumer Electronics. Vegas: IEEE, 2013: 637-638.

[9]ZHANG Hao, MA Zhan. Early termination schemes for fast intra mode decision in high efficiency video coding[C]//IEEE International Symposium on Circuits and Systems. Beijing: IEEE,2013:45-48.

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

[11]SHEN Liquan, LIU Zhi, ZHANG Xinpeng, et al. An effective cu size decision method for hevc encoders[J]. IEEE Transactions on Multimedia, 2013, 15(2): 465-470.

[12]MIN B, CHEUNG R C C. A fast cu size decision algorithm for the hevc intra encoder[J]. IEEE Transactions on Circuits and Systems for Video Technology,2015,25(5):892-896.

[13]LIM K, LEE J, KIM S, et al. Fast pu skip and split termination algorithm for hevc intra prediction[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2015, 25(8): 1335-1346.

[14]BOSSEN F. Common test conditions and software reference configurations[C]//Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11 12th Meeting. Geneva: ITU, 2013: 1-4.

[15]LIM K, KIM K, LEE J, et al. Fast block size and mode decision algorithm for intra prediction in h.264/avc[J]. IEEE Transactions on Consumer Electronics, 2012, 58(2): 654-660.

[16]HUANG Y H, OU T S, CHEN H H, et al. Fast decision of block size, prediction mode, and intra block for h.264 intra prediction[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2010, 20(8): 1122-1132.

[17]PATEUX S, JUNG J. An excel add-in for computing bjontegaard metric and its volution[C]//ITU-Telecommunications Standardization Sector STUDY GROUP 16 Question 6 Video Coding Experts Group (VCEG) 31st Meeting. Marrakech: ITU, 2007: 1-5.

Fast coding unit size decision algorithms based on texture complexity for high efficiency video coding

ZHANG Congcong, LI Ziyin, YING Lingkai，GUO Shengting

(College of Optical and Electronic Technology, China Jiliang University, Hangzhou 310018, China)

Abstract:To reduce the computational complexity of the high efficiency video coding (HEVC) intra coding algorithm, a fast coding unit size decision algorithm based on four directional texture complexity for the HEVC was proposed. We proposed the four directional texture complexity metrics and selected the best thresholds in different quantization parameters (QP) by training video sequences and portioned the current coding unit according to the best thresholds. Experimental results showed that the encoding time reduced by 45.3% on average, with 1.27% BD-Bitrate increasing and 0.058 dB BD-PSNR decreasing under the all-intra-main test configuration compared with the reference software HM10.0. The encoding time reduced by 3% on average, with 0.5% BD-Bitrate increasing and 0.023 dB BD-PSNR decreasing under the all-intra-main test configuration compared with the GEC-LEC algorithm.

Key words:high efficiency video coding；texture complexity；coding unit size

【文章编号】1004-1540(2015)01-0086-05

DOI:10.3969/j.issn.1004-1540.2016.01.016

【收稿日期】2015-09-23《中国计量学院学报》网址：http://zgjl.cbpt.cnki.net

【作者简介】张聪聪(1990- )，男，甘肃省庆阳人，硕士研究生，主要研究方向为高效视频编码技术.E-mail:zccyman@163.com

【中图分类号】TN919.18

【文献标志码】A

通信联系人：李子印，男，副教授.E-mail:liziyin@cjlu.edu.cn