基于宏块预判的快速帧内预测模式选择算法①

王 林, 贠境孺

(西安理工大学 自动化与信息工程学院,西安 710048)

H.264/AVC[1]是国际电信联盟ITU-T的视频编码专家组VCEG和国际标准化组织ISO/IEC的运动图像专家组MPEG联合制定的新一代视频编码标准. 为了提高编码效率,H.264采用了许多新的编码技术,其中帧内预测编码是消除空间冗余的关键技术. 帧内预测编码中引入率失真优化(Rate Distortion Optimization,RDO)[1]技术求最优预测模式,有效地降低了空间冗余,但为了得到一个最优帧内预测模式需要计算592种[2]组合模式的代价函数,大幅度增加了编码时间和计算复杂度. 因此,研究一种快速帧内预测模式选择算法替代原有复杂算法成为研究的重点方向. 针对帧内预测模式选择算法计算复杂度降低问题,国内外学者主要进行了两方面的研究：一是通过简化代价函数; 二是通过减少候选模式数量. Pan等人[3]最早用Sobel算子对当前待编码块每个点进行边缘矢量强度计算,根据边缘方向直方图的特点,确定候选模式,降低了的编码时间,但该算法需要对当前块中所有像素点的边缘方向矢量进行计算,计算复杂度仍然很高. Manuel等人[4]为了减少梯度计算数量使用Roberts算子代替Pan算法中的Sobel算子,编码时间比Pan算法平均减少了22.32%,但Roberts算子对斜向边缘提取效果较差,容易忽略少量边缘信息. Tsai等人[5]运用像素梯度检测预测方向的边缘强度提出了一个模式过滤算法,取得编码性能和计算复杂度之间的平衡. Joohyeok Kim等人[6]提出了一种基于绝对误差和(SATD)的快速帧内预测模式选择算法,实验结果表明在码率和峰值信噪比允许范围内减少了大约70%编码时间. Wang等人[7]计算帧内预测模式中四个主要预测方向(水平、垂直、45°和135°)的梯度强度,然后选择最小的梯度强度及邻近的预测模式,获得最佳预测模式. 杨军等人[8]提出了一种基于MAD值的自适应阈值快速帧内预测算法,先对宏块周围像素使用绝对误差(MAD)进行预判,虽然该算法编码效率不是很高,但与其它帧内预测模式选择快速算法结合使用可以取得较好效果. 宋云等人[9]提出一种基于方向梯度的帧内预测模式选择算法,使用参考像素与当前块之间的方向梯度检测出预测方向与边缘强度,优先筛选部分方向梯度较大的预测模式,实验结果减少了50%的编码时间,码率上升1.477%. 王欣欣等人[10]针对Pan算法中存在的缺陷加以改进,并与中心8×8块边界信息判定算法相结合,最大编码时间减少最大超过40%,但中心8×8块边界信息采用的像素过多,存在计算误差. Kau等人[11,12]针对Sobel算子存在像素使用多问题,提出一种新的边缘检测算子三点梯度算子,边缘检测率比Sobel算子高很多. Bhimani等人[13,14]针对预测应用程序视频运行需要高性能并行计算提出了FIM方法,采用两种模型马尔科夫模型和机器学习模型来提高迭代计算时间和多级的数据处理,为大规模视频处理减少更多的运行时间.

虽然上述研究对帧内预测模式选择计算复杂度降低具有一定贡献,但是研究的焦点一直围绕如何提高某一宏块的编码效率,只是对当前编码块内进行方向与边缘强度进行预测模式的筛选,通过改进算法筛选出最有可能的几个预测模式,再进行率失真优化计算,得到最佳预测模式,没有充分考虑到H.264帧内预测中Intra_4×4、Intra_16×16宏块类型与QP量化参数之间的关系. 本文为了提高预判准确度提出了一种基于宏块预判的快速帧内预测模式选择组合算法,先根据MAD值[8]与QP结合定义阈值判断宏块的类型,然后采用三点梯度算子[11]使用较少的像素求梯度矢量,进而得到边缘方向,最后通过边缘方向与预测模式方向的关系对宏块进行预测,筛选出最佳的预测模式.

1 相关理论与算法

1.1 H.264帧内预测编码

H.264帧内预测编码利用相邻像素的相关性,通过当前宏块的上边和左边相邻的像素进行预测,对实际值和预测值的差值进行变换、量化、熵编码,以消除空间冗余达到压缩目的[1,3]. 编码以宏块单位,分为亮度块预测和色度块预测两部分. 亮度块预测包括9种4×4预测模式(4×4预测模式)和4种16×16块的预测模式(16×16预测模式),色度块预测包含4种8×8预测模式. 图1(a)中的a～p的值可用相邻块的A～M来预测,其中,a～p表示当前需要预测的像素,A～M表示已编码并进行重建的像素. 图1(b)是Intra_4×4预测模式及方向示意图,包括8种方向的预测模式和DC模式.对于亮度16×16块和色度8×8块仅支持垂直、水平、直流和平面模式. 图2的4个子图分别表示Intra_16×16四种预测模式.

图1 4×4亮度预测

1.2 帧内预测模式选择

H.264JM8.6[15]模型中对帧内预测模式选择运用全搜索 (Full Search,FS)算法[1]. 采用率失真优化(Rate Distortion Optimization,RDO)策略进行最优化编码模式选择,通过遍历所有可能的编码模式,最后选择最小率失真代价模式作为最佳帧内预测模式.

图2 16×16亮度预测

其中SSD表示原始块与重建块的均方差值(Sum of Squared Differences,SSD);lmode=0.85×2(QP-12)/3表示拉格朗日算子(QP为量化参数);R表示熵编码后的比特率. H.264在基本档次下,以色度模式为外循环,依次扫描亮度的所有模式,每一个宏块需要进行M8×(M4×16+M16)=592次RDO计算才能得到最优的预测模式,其中M8、M4、M16分别代表8×8块、4×4块和16×16块的预测模式个数,可见获得最优的帧内预测模式的计算量非常大[2].

2 帧内预测模式选择组合算法

2.1 基于MAD值与QP结合的宏块预判算法

H.264帧内预测标准中指出,Intra_16×16模式适用于平坦区域图像编码,Intra_4×4模式适用于有大量细节的图像编码[1]. 如果能提前判断出宏块编码类型,就可以对预测宏块只进行一种方式的搜索. 经过对6个不同30帧视频序列在全搜素算法编码下的测试,得到6个视频序列采用不同编码类型的汇总. 表1是6个视频序列两种类型中DC模式所占比例; 表2是帧内预测宏块类型数量统计,可以看出Intra_4×4编码类型平均占82.7%,Intra_16×16编码类型平均占17.3%,所以提前判断宏块类型很有必要. 本算法主要是选取何种图像特征来表示宏块类型. 目前表征图像宏块平坦程度方法主要有计算交流系数AC与直流系数DC的比值[16]、图像的信息熵[16]、二维直方图[17]、相邻像素差值[2]、MAD值[8]. 交流系数与直流系数的比值和信息熵在某些情况下不能准确表示图像的平滑程度[16]; 直方图统计图像中各个像素灰度值出现的次数和频率,计算比较复杂; 由于基于相邻像素差值只考虑水平和垂直像素的差值存在一定误差; 而MAD值计算只涉及到简单的加法、绝对值和移位操作,计算复杂度上相对较小.

如果MAD值偏小,则图像细节平坦; 如果MAD值偏大,则图像细节丰富. 使用码流分析工具H264Visa对全搜索算法编码得到的码流进行模式分析,图3表示原始视频第一帧,图4表示运用JM8.6模型编码后宏块类型选择(小方格表示采用Intra_4×4,大方格表示采用Intra_16×16),可以看出不同宏块使用的是不同的编码方式,小方格区域图像细节丰富,大方格区域图像细节较为平坦.

图3 原始视频序列第一帧

图4 编码后宏块类型选择

MAD值是指宏块中每个像素值相对均值的离差绝对值的平均值,预测点像素与宏块中所有像素的平均值的绝对值.

其中,p(x,y)是坐标为(x,y)处的像素值,Mean是此宏块所有像素的平均值

表1 6个30帧视频序列DC预测模式比例(单位：%)

表2 帧内预测宏块类型数量统计

为解决宏块预判不够精确通过设置动态阈值T1、T2决定宏块采用Intra_4×4亮度块类型,还是采用Intra_16×16亮度块类型,不在阈值范围内的宏块使用全搜索算法. 从表2可以看出QP值对宏块类型有很大的影响. QP越小,编码宏块使用Intra_4×4类型越多.为了使预判更准确,动态阈值的设定与QP有关,随QP值得变化而变化. 通过大量仿真实验,得出QP下的动态阈值如式(4).

表3是QP=28时对预判宏块的准确度统计,可以看出6个视频序列在Intra_4×4、Intra_16×16的宏块选择中基本误差很小,最高的误判是Foreman视频序列在Intra_16×16宏块类型选择时达到10.6%,序列的宏块类型误判符合误差范围,以上可以说明预判算法与QP值的结合是必要的. 表4是基于MAD值的宏块预判算法与JM8.6全搜索算法的性能比较,可以看出码率(Bit Rate)和峰值信噪比(PSNR)的变化都比较小,但是编码时间平均下降了11.23%.

2.2 Pan算法

Pan算法[3]的基本思想是在H.264帧内预测编码中,沿局部边缘方向的像素具有相似的亮度值,并且大部分的预测模式都是基于方向性的模式,即得到某一方向对应的预测模式,证明该块的方向具有该模式对应的方向. Pan利用Sobel算子提取边缘方向信息,利用每个像素的边缘方向直方图来得到当前编码块方向的统计特性. 对于Intra_4×4亮度块的8种方向性的预测模式,用二分法将预测方向图划分成8个帧内预测模式选择区间,确定每个像素的边缘方向矢量所处的预测区间,根据预测区间判断预测模式.

表3 QP = 28时误判宏块统计(单位：%)

表4 基于MAD值的宏块预判算法与全搜索算法的性能比较

2.2.1 建立边缘方向图

Pan算法[2,3]中利用Sobel算子获得边缘方向信息,Sobel算子是常用的边缘检测算子,有两个分别反映垂直方向变化程度和反映水平方向变化程度的卷积核.原始视频帧序列分别与Sobel算子的两个卷积核卷积后,得到第i行第j列像素pi,j相应的边缘矢量：

dxi,j和dyi,j分别表示垂直和水平的变化强度,定义如下：

边缘矢量强度为：

边缘矢量的方向：

2.2.2 建立预测模式直方图

3 改进的Pan算法

Pan算法[3]利用边缘方向直方图筛选出可能性较小的候选模式,大大减少计算量,但在Pan算法中使用的Sobel算子使用周围像素较多以及在任何情况下都将DC模式作为候选模式之一,从表1可以看出DC模式在不同编码类型中作为候选模式的比例不同. 针对以上缺陷提出以下改进方法.

3.1 减少周围像素计算

Pan算法利用Sobel算子求边缘矢量,使用3×3卷积模板时使用周围像素至少6个,计算量较大. 采用三点梯度算子[11],只使用4个相邻像素中的3个像素得到预测像素的梯度矢量和边缘方向. 图5是像素x周围的3个像素,也就是边缘检测时使用的像素. 三点梯度算子示意图如图6所示,其中待求像素为x和周围像素a,b,c,虚线部分表示边缘方向,实线表示梯度矢量.

图5 边缘检测时使用像素

图6 三点梯度算子示意图

三点梯度算子：定义图像帧f的梯度

对角像素差：

梯度矢量：

3.2 DC模式选择

Pan算法在任何情况下都计算DC模式的率失真代价值,为了降低计算复杂度,设定DC模式的选择依据,判断是否采用DC模式[12].

DC模式的选择依据：

判断条件：

则将DC模式作为候选模式. 其中s24×4表示像素方差,即图1中12个像素A-L的平均值与待求像素的方差.θ4×4表示设定的阈值,Qstep表示量化步长,而量化参数是量化步长的编号,可以通过查表得到.

3.3 基于宏块预判快速帧内预测模式组合算法的具体描述

宏块预判算法与改进Pan算法的组合算法步骤如下：

1) 编码某I帧前,先获得视频序列的第一帧,利用公式(2)得到各个宏块的MAD值;

2) 设置不同QP值,获得多个视频序列中各个宏块的MAD值,通过仿真实验得到公式(4)阈值,根据阈值来判断新的编码视频序列宏块类型. 如果能判断出则不需要遍历两种编码类型,否则使用全搜索算法来计算;

3) 通过公式(14)(15)DC模式的判断依据,判断DC模式是否作为候选模式之一,如果满足条件DC模式可以作为候选模式;

4) 在1)、2)步预判算法的基础上,采用改进Pan算法中三点梯度算子计算待求宏块像素的梯度矢量,进而得到边缘方向,根据边缘方向得到预测模式,通过预测宏块中具有相同的预测模式的像素点的个数求和来确定预测模式直方图. 最后通过预测模式直方图得到更小范围的候选预测模式;

5) 在4)得到的候选预测模式与3)判断DC模式两者结合得到候选模式之后,再通过率失真优化 (RDO)来计算得编码块最优的预测模式.

4 实验结果

为了验证本文组合算法的有效性,将本文算法分别与JM8.6标准算法以及Pan算法,在编码时间、输出码率和峰值信噪比3个方面进行比较. 实验的硬件环境：CPU 2.6 GHz、内存4 GB、Windows7 64位操作系统; 软件环境：VC++ 6.0,JM8.6模型; 参数设置：基本档次(baseline)、全I帧编码、6个不同运动特性的QCIF格式视频测试序列(Bus,Claire,Foreman,Carphone,Suzie,News),在不同量化参数QP下对每个视频序列取前30帧进行编码.

(1) 评价指标

其中,峰值信噪比PSNR单位为dB,时间Time单位为s,码率Bit rate单位为kbit/s.

(2) 实验结果用3个部分表示

① 3种算法之间性能比较见表5、表6. 由表5和表6可见,组合算法比全搜索算法、Pan算法编码时间下降很多,平均降低分别是72.4%、28.6%; 以码率升高作为代价,比全搜索算法、Pan算法码率分别升高4.21%、1.8%.

② 图7、图8分别是Claire和News序列在3种算法下的性能对比图; 图7、图8的子图(a)是率失真对比图,(b)是编码时间对比图. 从图7(a)、(b)及图8(a)、(b) 可以看出Claire 、News视频序列分别在3种算法编码下得到的率失真对比,三者之间的误差较小,可以忽略影; 而编码时间的变化,组合算法明显优于其他单个算法,大幅度降低.

表5 组合算法与全搜索算法的性能比较

表6 组合算法与Pan算法的性能比较

③ 图9、图10分别是Claire和News视频序列在不同算法下解码的主观质量图; 图9、图10的子图(a)、(b)、(c)分别是JM8.6、Pan算法以及组合算法下的图. 从图9和图10可以看出3种算法下的视频帧主观质量相差很小. 综上编码时间可以衡量算法的复杂度,在码率稍高情况下,组合算法比单个算法有效,大幅度降低计算复杂度,减少编码时间.

图7 Claire视频序列在三种不同算法下的性能对比图

图8 New视频序列在三种不同算法下的性能对比图

图9 三种不同算法下Claire视频帧对比图

图10 三种不同算法下的News视频帧对比图

5 结语

本文针对帧内预测模式选择部分计算复杂度问题以及现有快速帧内预测模式选择算法中Pan算法中Sobel算子存在的缺点,找到一种更有效的快速帧内预测模式组合算法. 提出了考虑QP变化的MAD宏块预判算法与三点梯度算子相结合的帧内预测模式选择算法,避免了遍历所有模式. 通过实验可以得到：在视频帧主观质量基本不变,码率稍增高的情况下,可以大幅度降低计算复杂度,减少编码时间.

1 毕厚杰,王健. 新一代视频压缩编码标准——H.264/AVC.2版. 北京：人民邮电出版社,2009.

2王慧,常建平. 改进的H.264快速帧内预测模式选择算法.计算机工程,2008,34(19)：228-229. [doi：10.3969/j.issn.1000-3428.2008.19.077]

3 Pan F,Lin X,Rahardja S,et al. Fast mode decision algorithm for intraprediction in H.264/AVC video coding. IEEE Transactions on Circuits and Systems for Video Technology,2005,15(7)：813-822. [doi：10.1109/TCSVT.2005.848356]

4 De-Frutos-López M,Orellana-Quirós D,Pujol-Alcolado JC,et al. An improved fast mode decision algorithm for intraprediction in H.264/AVC video coding. Signal Processing：Image Communication,2010,25(10)：709-716.[doi：10.1016/j.image.2010.10.005]

5 Tsai AC,Paul A,Wang JC,et al. Intensity gradient technique for efficient intra-prediction in H.264/AVC. IEEE Transactions on Circuits and Systems for Video Technology,2008,18(5)：694-698. [doi：10.1109/TCSVT.2008.919113]

6 Kim J,Jeong J. Fast intra mode decision algorithm using the sum of absolute transformed differences. Proceedings of 2011 International Conference on Digital Image Computing Techniques and Applications. Noosa,QLD,Australia. 2011.655-659.

7 Wang JC,Wang JF,Yang JF,et al. A fast mode decision algorithm and its VLSI design for H.264/AVC intraprediction. IEEE Transactions on Circuits and Systems for Video Technology,2007,17(10)：1414-1422. [doi：10.1109/TCSVT.2007.903786]

8 杨军,龚声蓉,刘纯平. 自适应阈值的宏块MAD快速帧内算法. 计算机工程与应用,2009,45(34)：189-191.

9 宋云,沈燕飞,龙际珍,等. 基于方向梯度的H.264帧内预测模式选择算法. 计算机学报,2013,36(8)：1757-1764.

10 王欣欣,陆中成,程欣欣. H.264/AVC标准中帧内预测宏块模式选择的优化. 计算机工程与应用,2011,47(16)：182-184. [doi：10.3778/j.issn.1002-8331.2011.16.055]

11 Kau LJ,Chen CS. A low complexity dual mode edge detector. Proceedings of 2011 Visual Communications and Image Processing (VCIP). Tainan,China. 2011. 1-4.

12 Kau LJ,Leng JW. A gradient intensity-adapted algorithm for the fast decision of H.264/AVC intra-prediction modes.Proceedings of 2013 IEEE Workshop on Signal Processing Systems (SiPS). Taipei City,Taiwan,China. 2013. 272-277.

13 Bhimani J,Mi NF,Leeser M,et al. FiM：Performance prediction for parallel computation in iterative data processing applications. Proceedings of the 2017 IEEE 10th International Conference on Cloud Computing (CLOUD).Honolulu,HI,USA. 2017. 359-366.

14 Bhimani J,Leeser M,Mi NF. Accelerating K-means clustering with parallel implementations and GPU computing. Proceedings of 2015 IEEE High Performance Extreme Computing Conference (HPEC). Waltham,MA,USA. 2015. 1-6.

15 刘佳,董金明. 一种新的H.264/AVC快速帧内预测模式选择判决算法. 电子与信息学报,2009,31(5)：1072-1076.

16 谢晶,贾克斌. 一种基于二维直方图的H.264/AVC快速帧内预测判决算法. 电子与信息学报,2005,27(7)：1053-1057.

17 Joint Video Team. H.264/AVC Reference Software JM8.6.http：//iphome.hhi.de/suehring/tml/download/old_jm/jm8.6.zi p. 2004-09.