一种HEVC帧内预测快速算法

张新晨,肖秀秀,赵 娅,黎 伟,江 昊,肖进胜

(1.华中师范大学物理科学与技术学院,武汉430079;2.武汉大学电子信息学院,武汉430072)

一种HEVC帧内预测快速算法

张新晨1,肖秀秀1,赵 娅1,黎 伟2,江 昊2,肖进胜2

(1.华中师范大学物理科学与技术学院,武汉430079;2.武汉大学电子信息学院,武汉430072)

HEVC作为新一代的视频编码标准,比现有H.264标准的压缩效率提高近一倍,但其存在复杂度较高的问题。为此,针对HEVC中帧内预测最耗时的模块,即编码单元块划分模块和帧内预测模式选择模块,提出一种适合HEVC帧内预测的快速算法。该算法将率失真(RD)代价作为阈值参数,利用候选模式集中预测模式被选中概率快速递减的规律,基于RD代价进行帧内预测块划分和帧内预测模式选择。实验结果表明,该算法在相同编码质量条件下可减少59%的HM10.0帧内预测模块复杂度,相应比特率的增加幅度小于1.34%。

视频编码;HEVC标准;帧内预测;块划分;模式选择

1 概述

2013年1月,JCT-VC新一代视频编码标准HEVC正式发布,作为现行标准H.264/AVC的替换标准,该标准应用支持视频分辨率从320×240像素至7 680×4 320像素,与H.264/AVC的高档次编码配置(High Profile)的编码性能相比,能提高近一倍的编码压缩效率[1-2]。

但HEVC在获得更高性能的同时,也无可避免地增加了计算复杂度,在帧内编码过程中,采用了四叉树递归编码单元结构以及采用枚举法遍历35种帧内预测模式找出最佳模式[3],其计算复杂度成倍的增加导致HEVC不能有效地应用于实时通信应用。因此,在保持HEVC视频主客观质量的前提下,有效地降低计算复杂度是普及HEVC视频编码标准和将其商业化应用的关键所在[4-5]。

本文基于率失真(Rate-distortion,RD)代价函数提出一种提前终止四叉树的帧内预测块划分方法,并利用图像相关性选取候选预测模式集进一步降低预测模式选择的计算复杂度。

2 HEVC帧内预测

HEVC参考模型(HM10.0)[6]采用树形结构和递归模式进行编码单元(Coding Unit,CU)块的划分,对于帧内预测模式来说,CU块的深度优先遍历递归从树根最大编码单元(Largest Coding Unit, LCU)(64×64)开始,依次出发搜索它的每个邻接点(4个32×32的子CU块),若邻接点未曾访问过,则以它为新的出发点继续进行深度优先遍历,一直递归至4×4大小的块,直至四叉树中所有节点均被访问为止,四叉树深度优先搜索结束[7-8]。

参考模型深度优先遍历四叉树的每个节点,计算出四叉树上每个节点的权重,即当前层次编码单元CU的率失真代价RDCost。如果当前编码单元CU所划分的4个子CU的RDCost之和大于当前编码单元CU自身的RDCost,则当前CU在编码的时候不需要做划分;否则,当前CU需要划分。另外,将当前编码单元CU的RDCost赋值为两者之间的小者。通过这个算法,计算出使整个 64×64的RDCost最小的划分路径,用于编码。在计算RDCost的过程中,主要采用以下3个步骤[9]获得每个CU单元的最佳帧内预测模式:

步骤1 对所有34种或17种角度的预测模式,使用基于HAD(Hadamard transform Absolute Difference)的代价函数计算代价,然后按代价值从小到大的顺序排列预测模式,选出前若干种代价最小的模式构成一组候选模式。候选模式集中的候选模式的数量如表1所示。

表1 角度帧内预测方向模式和候选模式数量

步骤2 从相邻编码单元中推导出最有可能模式(MPM),并将其加入候选模式集中,若候选集中已经有此模式,则不重复加入候选模式集中;否则,将MPM加入候选模式集的末尾。

步骤3 从这些候选模式中,使用基于 SSE (Sum of Square Error)的代价函数计算代价,选出有最小RDCost的模式作为最佳预测模式。

3 帧内预测的优化算法

帧内预测模式计算运算量巨大。帧内模式快速选择算法的研究作为提高编码效率的研究重点之一。通过上述HEVC中较为耗时模块的分析,降低帧内预测算法复杂度可以从以下2个方面进行研究:(1)采用提前终止的思想,预判块帧内编码块类型,节省块划分时间;(2)通过一些低复杂度的方法有效地将候选集中不太可能的模式过滤掉[7,10-12],从而减少计算的预测模式数量。

3.1 基于率失真代价的帧内预测块划分快速算法

对于当前CU块的最佳RD代价,需要搜寻在每一个深度CU的每一个可能的模式。但是可以发现,如果当前CU的深度是逼近最优的,停止分裂当前CU只会导致一个微不足道的损失[13],但是速度却会有一个巨大的提升[14]。

图1是RaceHorses序列在标准HM代码下的CU分割结果。在第一个64×64的LCU块中,当第一个32×32的块计算出的代价逼近最优模式时,可以停止继续分割CU,大幅提高编码速率;在第4个32×32的块计算出的代价很大时,可以直接确定该块需要继续分割成4个16×16的子块,无需在该32×32的块中做量化等工作。要确定提前终止的条件,本文使用率失真代价RDCost。

图1 RaceHorses序列的CU分割结果

通过设定一个阈值,当RDCost小于该阈值时,说明预测效果很好,可以满足编码需要,则不需要进一步的判断以及下一层的递归划分;否则,需要做进一步的判断和下一层的递归划分。下面将详细介绍阈值的选定流程。

其中,E表示错误率;T是阈值。

因此,满足dE/dT=0以及d2E/dT2＞0的阈值应该是最佳的阈值,也可以视为2条曲线的交点。

因而,对于每个2N×2N单元,如果ΔC2N大于离线训练的阈值,则被认为是应该被分割成N×N的块。否则,2N×2N预测单元大小对编码这种2N× 2N单元来说是合适的。按照这一办法,在训练集中的每个序列和量化参数(Quantization Parameter, QP),只需要一次编码迭代就能得到一整套阈值,复杂度降低的同时,能得到接近图1的最佳结果。

本文选择5种不同分辨率的测试序列进行阈值训练,如表2所示。对于每一个序列,QP值分别为22,27,32和37。在获得所有序列的阈值组合后,计算5个序列的平均阈值,最终采用的阈值如图2所示,有4条曲线对应于4种单元尺寸在不同QP下的阈值。

表2 测试序列

图2 算法训练后采用的阈值

以RaceHorses序列为例,在使用上述算法流程改进后的HM代码下,该视频序列的CU分割结果如图3所示。

图3 RaceHorses序列的CU分割结果

3.2 帧内预测模式快速选择

本文提出的帧内预测模式选择快速算法具体步骤如下:

(1)从所有角度模式中,使用基于HAD代价的代价函数,并按代价值从小到大,选出若干个模式构成一组候选模式。

(2)从相邻编码单元中推导出最有可能模式MPM,判断该MPM是否是候选模式集中代价最小的模式,如果是,直接选为最佳预测模式,否则,将其加入候选模式集中,并跳至第(3)步。

(3)从这些候选模式中,选出最小RD代价的模式作为最佳预测模式。

4 实验结果及分析

本文算法在HM10.0上实现,配置文件选用配置encoder_intra_main.cfg,测试过程中I帧的周期设置为1,所有编码帧均为帧内编码。

表3的实验结果表明,本文算法在帧内预测编码平均节省58.97%的编码时间,在PSNR几乎没有下降的同时编码码率增加了1.34%,这个性能损失值是可以接受的。在不同的分辨率或者序列特征下,可以实现降低几乎相同的复杂度,表明本文所提出的算法在实时HEVC编码应用的潜力较大。

表3 块划分和模式选择结合快速算法的性能比较

5 结束语

本文在分析HEVC中帧内预测算法和现有快速算法的基础上,提出一种提前终止四叉树的递归处理方法,提前终止的判断参数选用率失真代价,再利用图像的相关性,对HEVC帧内预测候选模式集中根据概率快速递减的规律,减少了候选模式数目。最后,针对HEVC帧内编码在HM10.0参考模型中实现了快速处理算法,降低了原算法的计算复杂度和帧内编码时间。实验结果表明,与参考模型中的算法相比,本文算法在不降低编码质量的情况下进行帧内编码时缩减了59%的编码时间,考虑到编码过程中其他模块的耗时,帧内预测处理的速度实际上有了成倍的提高。因此,本文提出的针对HEVC帧内预测的快速算法具有较高的实用和研究参考价值。

[1] Bross B,Hhi F.High Efficiency Video Coding(HEVC) Text Specification Draft 10[C]//Proc.of the ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11 12th Meeting.Geneva,Switzerland:[s.n.],2013:14-23.

[2] 刘梅峰,陆 玲.新一代视频编码标准HEVC变换方法的研究[J].电视技术,2012,36(1):1-5.

[3] Lainema J,Ugur K.Angular Intra Prediction in High Efficiency Video Coding(HEVC)[C]//Proc.of the 13th IEEE International Workshop on Multimedia Signal Processing.Hangzhou,China:[s.n.]:2011:1-5.

[4] Saygili G,Gurler C G,Tekalp A M.Evaluation of Asymmetric Stereo Video Coding and Rate Scaling for Adaptive 3D Video Streaming[J].IEEE Transactions on Broadcasting,2011,57(2):593-601.

[5] Bossen F,Drugeon V.Video Coding Using a Simplified Block Structure and Advanced Coding Techniques[J]. IEEE Transactions on Circuits and Systems for Video Technology,2010,20(12):1667-1675.

[6] Bross B,McCann K.JCT-VC AHG Report:HEVC Draft and Test Model Editing[C]//Proc.of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11 12th Meeting. Geneva,Switzerland:[s.n.],2013:1085-1090.

[7] Sun Heming,Zhou Dajiang,Goto S.A Low-complexity HEVC Intra Prediction Algorithm Based on Level and Mode Filtering[C]//Proc.of 2012 IEEE International Conferenceon Multimedia and Expo.Melbourne, Australia:IEEE Press,2012:1085-1090.

[8] Saxena A,Fernandes F C.On Secondary Transforms for Intra Prediction Residual[C]//Proc.of IEEE International Conference on Acoustics,Speech and Signal Processing.Kyoto,Japan:IEEE Press,2012:1201-1204.

[9] Bross B,Han W,Ohm J,et al.WD5:High Efficiency Video Coding(HEVC)Text Specification Draft 9[C]// Proc.of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/ WG11 11th Meeting.Shanghai,China:2012.

[10] Yeo Chuohuo,Tan Yihhan.Mode-Dependent Transforms for Coding Directional Intra Prediction Residuals[J]. IEEE Transactions on Circuits and Systems for Video Technology,2012,22(4):545-554.

[11] Huang Yihsin,Ou Taosheng,Chen H H.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.

[12] 成益龙,滕国伟,石旭利,等.一种快速HEVC帧内预测算法[J].电视技术,2012,36(21):4-7.

[13] Lim K,Kim S.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.

[14] Yeo C,Tan Y H.Low-complexity Mode-dependent KLT for Block-based Intra Coding[C]//Proc.of the 18th IEEE International Conference on Image Processing. Brussels,Belgium:IEEE Press,2011:3685-3688.

编辑 金胡考

A Fast Intra-frame Prediction Algorithm for HEVC

ZHANG Xin-chen1,XIAO Xiu-xiu1,ZHAO Ya1,LI Wei2,JIANG Hao2,XIAO Jin-sheng2
(1.College of Physics Science and Technology,Central China Normal University,Wuhan 430079,China;
2.School of Electronic and Information,Wuhan University,Wuhan 430072,China)

As a new generation video coding standard,HEVC has more compression efficiency than the existing video coding H.264 standard,but it has higher complexity.Aiming at this problem,after brief analysis of the intra prediction algorithm,a fast algorithm based on Rate-distortion(RD)cost of intra prediction block dividing and the intra-frame prediction mode selection fast algorithm is proposed to reduce the HEVC intra-frame prediction complexity.This algorithm takes full use of the advantages of rate distortion cost and the probability of the prediction mode is selected in the candidate pattern quick descending law.Experimental results show that complexity reduction from HM10.0 is over 59% and stable for various sequences,which makes the proposed algorithm suitable for real-time applications.The corresponding bit rate increase is lower than 1.34%.

video coding;HEVC standard;intra-frame prediction;block partitioning;mode decision

1000-3428(2014)10-0017-03

A

TP18

10.3969/j.issn.1000-3428.2014.10.004

国家自然科学基金资助项目(61371126);教育部-中国移动科研基金资助项目(MCM20122041)。

张新晨(1977-),男,副教授、博士,主研方向:视频编码,多媒体通信;肖秀秀,硕士研究生;赵 娅,本科生;黎 伟,硕士研究生;江 昊,教授、博士;肖进胜,副教授、博士。

2013-09-03

2013-11-12E-mail:zxc9501@163.com

中文引用格式:张新晨,肖秀秀,赵 娅,等.一种HEVC帧内预测快速算法[J].计算机工程,2014,40(10):17-19,24.

英文引用格式:Zhang Xinchen,Xiao Xiuxiu,Zhao Ya,et al.A Fast Intra-frame Prediction Algorithm for HEVC[J]. Computer Engineering,2014,40(10):17-19,24.