一种快速HEVC编码单元决策算法

雷海军，杨忠旺，陈 骁，袁梅冷

一种快速HEVC编码单元决策算法

雷海军1，杨忠旺1，陈 骁2，袁梅冷3

(1. 深圳大学计算机与软件学院，广东 深圳 518060；2. 创维集团深圳研究院，广东 深圳 518060； 3. 深圳职业技术学院，广东 深圳 518060)

分析高效视频编码标准(HEVC)的编码单元算法，针对当前视频编码标准计算复杂度大的问题，基于相邻编码单元相关性和纹理特性，提出一种快速HEVC编码单元决策算法。该算法统计当前编码单元和相邻编码单元的相关性，分析编码单元的纹理复杂度，并设定合理的阈值，决定检测是否提前终止，以此快速找到最优编码单元。仿真结果表明，该算法与HEVC参考软件HM8.0相比，在码率增加忽略不计的情况下，编码时间平均缩短了37.4%，最高可达48.2%。

高效视频编码；编码单元；计算复杂度；提前终止；纹理特征；码率

1 概述

随着数字技术的快速发展以及互联网的广泛应用，图像和视频压缩技术已经渗透到人们的日常生活中，而且近几年对高清和超高清的需求服务越来越大。虽然H.264/AVC在高清视频处理方面仍不能得到具体应用，但随着大量的新技术不断涌现，编码性能不断提高，在H.264基础上进一步提升高清视频的压缩效率已成为可能。为此，国际电信联盟(ITU-T)与ISO/IEC移动图像专家(MPEG)成立了视频编码联合小组(JCT-VC)，通过研究并制定下一代视频编码标准——高效视频编码(High Efficient Video Coding, HEVC)，旨在H.264/AVC的高级档次基础上，使压缩效率提高1倍[1-2]。

HEVC同样采用预测加变换的混合编码结构，然而HEVC采用更加灵活的编码块结构：编码单元(CU)，预测单元(PU)和转换单元(TU)，其中，CU作为编码的基本单元，类似于H.264的宏块；PU作为预测的基本单元，是在CU基础上进一步分割得到；TU作为变换的基本单元，更能适合不同图像的内容[3-4]。由于编码单元决定最初块的大小，对后面的预测单元、变换单元的一步划分都有很大影响，文献[5]指出不同的编码单元的性能大不相同，相对于编码大小为16×16，设置编码单元大小为64×64可以减少12%的比特率。因此，编码单元在降低编码复杂度方面起着很重要的作用。

本文通过分析HEVC中相邻编码单元编码模式的相关性和编码单元的纹理，提出一种快速的编码单元模式选择算法，以降低编码复杂度。

2 参考模型中的编码单元决策算法

HEVC标准采用大小可变的编码单元，范围从最小编码单元8×8到最大编码单元64×64，按照四叉树块结构，可以递归地把最大编码单元(LCU)分割成4块以得到合适的编码单元大小。

图1显示了HEVC中编码单元在各深度的划分。64×64是深度为0的最大的编码单元(LCU)；8×8是深度为3的最小的编码单元(SCU)。是否进行分割由分割标志决定，当分割标志为1时，LCU被分割成4个子编码单元，否则LCU不进行划分；当递归分割到四叉树的叶结点或者达到制定要求时，终止继续分割。这样如果为找到一个最优的编码单元大小而计算所有的编码单元，重复计算85个编码单元的率失真消耗[6]，并且比对其大小，将花费大量的编码时间。

图1 HEVC编码单元结构

现阶段HEVC参考模型已经采纳了SKIP模式提前终止[7]、基于CBF的提前终止算法[8]和编码单元提前终止算法[6]，这几种方案都在一定程度上降低编码复杂度。SKIP模式主要采用式(1)提前终止编码单元分割：

虽然SKIP模式可以降低约50%的编码时间，但由于图像的质量也随之降低很大，默认不可用。文献[9]提出了 一种基于编码单元部分检测的快速选择算法，编码复杂度降低10%，文献[10]通过贝叶斯统计设置阈值决策编码单元的大小等。

HEVC测试模型8.0采用如图2所示流程决定当前编码单元是否分割。首先初始化率失真值，编码当前的编码单元，记录当前编码的结果和消耗；然后查看现在编码单元所处的深度是否达到最大的允许深度，如果达到最大深度，则终止继续分割；递归处理分割的各个子编码单元，计算得到率失真消耗；最后比较没有分割时的编码单元的消耗和分割后的率失真消耗，如果前者大于后者，则进行分割；否则不进行分割终止。

图2 LCU分割方法流程

3 快速决策算法

3.1 相关性测试及阈值设定

本文根据当前编码单元和相邻编码单元的空间相关性合理设置阈值参数，在图像质量变化不大的情况下，降低了编码复杂度。由于SKIP/MERGE模式提前终止算法已经能很大程度上降低编码复杂度，只要能降低对图像质量的损耗就可以达到一个很不错的效果。而且如果当前的编码单元的最佳模式为SKIP，那么式(1)中的权值参数能更高。所以本文分别测试相邻编码单元和父母编码单元(如果当前编码单元的深度为1，则父母编码单元为0)与当前编码单元的相关性。图3显示了当前编码单元的测试依赖关系。其中，0表示父母编码单元；1表示当前的编码单元；2表示当前编码单元的左侧相邻编码单元；3表示当前编码单元的上侧相邻编码单元。

图3 测试编码单元相关性模型

为进一步验证相邻的CU的相关性概率，设定测试条件如下：

测试条件1当前编码单元为SKIP/MERGE模式时，相邻的编码单元为SKIP/MERGE模式的概率。

测试条件2父母编码单元为SKIP/MERGE时，当前编码单元为SKIP/MERGE的概率。

由表1可以看出，使用测试条件1时的概率最大达到90%，平均相关性概率为73.4%；使用测试条件2时最大概率为接近90%，平均相关性概率达到75.8%。根据测试项及结果很明显可以得到当前编码单元不仅与相邻的编码单元有很大的相关性，而且和上一层编码单元也有很大的相关性。

表1 相关性概率 %

通过编码单元的相关性调整式(1)中的权值系数，首先调整权值系数为0.8，然后如果相邻的编码单元为SKIP/ MERGE模式时，更改权值系数为1；如果更高一层或父母编码单元为SKIP/MERGE时，同样调整编码系数为1.5。

3.2 编码单元纹理特征分析

HEVC支持最大编码达到64×64，如果编码单元比较平缓或者具有方向(垂直方向水平方向等)，则当前编码单元比较适合大尺寸编码单元预测。这样可以通过式(2)当前编码单元的纹理复杂度，然后设定不同大小编码单元的阈值，从而快速地决策当前的编码单元是否进行分割，从而减少编码时间[11]，如果当前的编码单元的大小为64×64，然后计算相应的纹理复杂度，若小于设定的阈值，当前的编码单元不进行分割，否则把当前编码单元分割成更好的编码单元，然后再比较分割后的大小，并且判断此时是否满足对应此大小的阈值。

其中，表示当前编码单元的纹理复杂度；为当前编码像素数；(,)为(,)所制定的像素值。

3.3 整体算法流程

经过上述过程分析以及HM8.0，采用图4所述的算法流程。首先从最小深度，也就是最大编码单元LCU开始，选取预测模式，然后进行SKIP/MERGE模式的提前终止检测，如果满足条件，则直接终止；如果不满足条件则检测当前编码单元的纹理复杂度，如果小于设定的阈值则编码单元相对平坦不进行划分，否则按照标准中的判断方式进行检测，这样既可以保证准确度，又可以减少编码单元分割所需时间。算法具体流程如图4所示。

图4 本文算法流程

4 实验仿真结果

本文实验仿真采用HEVC参考模型HM8.0，测试条件与测试序列采用提案JCTVC-E700[12]。电脑配置如下：CPU为Intel Pentium E5800 3.2 GHz，内存为2 GB。

表2显示了本文算法与HM8.0之间编码性能的比较结果。其中，(%)表示码率的变化，采用文献[13]中公式计算；Δ(%)表示时间的变化，根据下式计算：

表2 编码性能比较 %

可以看出，本文算法与HM8.0相比，PSNR减少幅度较小，平均减少0.9 dB，码率稍有增长，平均增加1.2%，但是编码时间最大可节省48.2%，平均节省37.4%，而且在较平缓序列中节省时间相对更大。通过合理设定阈值能在很少增加或者不增加比特率的情况下，大幅提高编码效率，降低编码时间。

5 结束语

本文分析HEVC编码在单元空间上的相关性，研究编码单元的纹理特性，通过减少编码单元预测模式，提出一种快速的编码单元决策方法。与HEVC参考模型相比，本文算法平均可减少37.4%编码时间，而且对不同的序列有明显的效果，能很好地提高编码效率、降低编码复杂度。下一步主要将结合编码单元和预测单元，进一步加快编码单元决策，减少帧内模式预测数量，降低预测单元模式选择复杂度，提高整个编码端的效率。

[1] OurazadMTP, DoutreC,AzimiM, et al.HEVC:The New Gold Standard for Video Compression[J].IEEE Consumer Electronics,2012, 1(3):36-46.

[2] 蔡晓霞, 崔岩松, 邓中亮, 等. 下一代视频编码标准关键技术[J]. 电视技术, 2012, 36(2): 80-84.

[3] BossenF, BrossB, SuhringK,et al. HEVC Complexity and Implementation Analysis[J]. IEEE Transactionson Circuits and Systems for Video Technology, 2012,22(12):1685-1696.

[4] SullivanGJ, OhmJR, HanWJ, et al. Overview of the High Efficiency Video Coding(HEVC) Standard[J]. IEEE Transac- tions on Circuits and Systems for Video Technology, 2012,22(12): 1649-1668.

[5] Kim M K J.Report on Large Block Structure Testing[C]//Proc.of JCT-VC’10. Guangzhou, China: [s. n.], 2010: 1-4.

[6] ChoiK, JangES. Fast Coding Unit Decision Method Based on Coding Tree Pruning for High Efficiency Video Coding[J]. Optical Engineering, 2012, 51(3).

[7] Han WJ, Min J, Lee T, et al. Improved Video Compression Efficiency Through Flexible Unit Representation and Corres- ponding Extension of Coding Tools[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2010, 20(12):1709-1720.

[8] GweonRH,LeeYL, LimJ. Early Termination of CU Encoding to Reduce HEVC Complexity[C]//Proc. of JCT-VC’11. Torino, Italy: [s. n.], 2011: 1-5.

[9] TanHuili, LiuFengjiao, TanYH, et al. On Fast Coding Tree Block and Mode Decision for HEVC[C]//Proc. of Conference on Acoustics, Speech and Signal Processing. Kyoto,Japan: [s. n.], 2012:825-828.

[10] ShenXiaolin, YuLu,ChenJie. Fast Coding Unit Size Selection for HEVC Based on Bayesian Decision Rule[C]//Proc. of 2012 Picture Coding Symposium. Krakow, Poland: IEEE Press, 2012: 453-456.

[11] TianGuifen, GotoS. Content Adaptive Prediction Unit Size Decision Algorithm for HEVC Intra Coding[C]//Proc. of 2012 Picture Coding Symposium. Krakow,Poland: IEEE Press, 2012: 405-408.

[12] BossenF. Common Test Conditions and Software Reference Configurations[C]//Proc. of JCT-VC’11.Geneva,Switzerland: [s. n.], 2011: 1-22.

[13] Senzaki K, Chono H, Aoki J, et al. BD-PSNR/Rate Compu- tation Tool for Five Data Points[C]//Proc. of JCT-VC’10. Geneva, Switzerland: [s. n.], 2010: 1-11.

编辑 金胡考

A Fast Coding Unit Decision Algorithm for HEVC

LEI Hai-jun1, YANG Zhong-wang1, CHEN Xiao2, YUAN Mei-leng3

(1. College of Computer and Software, Shenzhen University, Shenzhen 518060, China; 2. Shenzhen Research Institute of Skyworth Group,Shenzhen 518060, China; 3. Shenzhen Polytechnic, Shenzhen 518060, China)

This paper analyzes coding unit algorithm of High Efficient Video Coding(HEVC) standard. Aiming at its high computational complexity, this paper proposes a fast coding unit decision algorithm for HEVC based on the coding unit correlation and texture of coding unit. This algorithm counts the correlation of current coding unit and adjacent coding unit, calculates texture complexity of encoding units, sets a reasonable threshold, and detects early termination, to quickly find the optimal coding unit. Simulation results show that, compared with the HEVC conference software HM8.0, the proposed algorithm can reduce about 37.4% encoding time and up to 48.2%, while it suffers from negligible on bit-rates performance.

High Efficient Video Coding(HEVC); coding unit; computational complexity; early termination; texture characteristic; bit rate

1000-3428(2014)03-0270-04

A

TP37

国家自然科学基金资助项目(60972037)；广东省部产学研基金资助项目(2012B091100495, 2009B090300267)；深圳市基础研究基金资助项目(JCYJ20120613113419607)。

雷海军(1968－)，男，副教授，主研方向：图像/视频处理，模式识别；杨忠旺，硕士研究生；陈 骁，工程师、硕士；袁梅冷，副教授、硕士。

2013-01-23

2013-03-18 E-mail：15969714254@163.com

10.3969/j.issn.1000-3428.2014.03.057