基于时空预测的H.264快速帧内预测模式选择算法

徐平，佘青山，金朝阳，徐伟栋

（杭州电子科技大学 自动化学院，浙江 杭州 310018）

1 引言

在H.264标准中，为了获得高质量和高压缩比，采用率失真优化RDO (rate distortion optimization)模型[1,2]进行帧内预测模式选择。但同时，帧内预测模式选择算法的高计算复杂度是制约H.264实际应用的主要因素之一。

针对帧内预测模式选择的改进策略研究，成为近年来国内外的研究热点。现有的帧内预测模式选择改进算法，大体可分为2类：1) 简化RDO代价函数[3]，寻找可以替代RDO，且基本不影响编码质量的简化RDO代价函数；2) 通过概率预测或者阈值判断减少候选模式数[4～16]，预测各模式被选择为最佳模式的概率，减少小概率模式的编码；通过实验统计等方法获得阈值，在编码过程中一旦满足阈值条件，提前终止后续的模式选择过程，减少候选模式数。

上述的第 2类方法是目前业界的主要研究趋势。Pan等人基于边缘方向直方图预测最佳帧内模式，仅在几个大概率模式中进行选择，显著减少候选模式数，提高编码速度[4,5]。Wang等人提出基于边缘强度的帧内预测算法，将4×4亮度块的9个帧内预测模式中垂直、水平、45°、135°和DC模式作为主模式，分情况确定候选模式[6]。Wei等人采用基于NHT(non-normalized Haar transform)，提取边缘的方向信息，排除冗余的模式[7]。Tsai等人采用梯度强度滤波算子，以确定宏块的方向性，减少候选模式数量[8]。蒋刚毅等人计算4×4亮度参考块的方差，对于方差较小的亮度块，仅采用几种概率高的预测模式[9]。贾克斌等人提出了一种基于自相关性的帧内预测算法，该算法在进行帧内预测之前先进行宏块预判，从2种预测模式中选择一种，从而减少算法的复杂度[10]。苏睿等人利用变换域的信息得到图像纹理方向，仅在的几个高概率模式中进行模式选择，降低运算量[11]。陆璐等人对块的细节程度和纹理方向进行分析，根据细节程度和纹理方向对模式进行筛选，从而提高模式搜索速度[12]。黄凯等人在Sobel模式判决算法的基础上，提出一种面向VLSI的模式优化算法[13]。腾国伟等人利用色度块和亮度块以及4×4亮度块和16×16亮度块模式选择之间的相关性，提出一种基于 RDO的快速模式选择算法[14]。文献[15]通过大量实验观察得出以下结论：多参考帧运动估计中的最佳匹配块的帧内模式是当前块时域的最佳帧内预测模式。基于此结论，采用与最佳匹配块重叠像素最多已编码块的帧内模式作为当前块的最佳帧内预测模式。文献[16]提出了基于时空相关性的快速模式选择算法。该算法应用于 AVS-M 平台，其模式预测是基于以下假设：图像块时域间的距离越近，时域相关性越高，预测模式相关性越强。由于该算法不是基于文献[15]的观察结果，算法的时域预测准确性有待进一步提高。

Pan等人[4,5]提出的基于边缘方向直方图的快速帧内预测模式选择算法（以下简称Pan算法）是第2类方法中具有代表性的一种算法，可在保持较好的编码图像质量的同时较大地提升编码速度。但是，该算法仅利用了块内部纹理信息进行候选模式的概率预测，没有充分利用编码过程中存在的时域和空域相关性，因此，编码效率还有待提高。本文在Pan算法的基础上，充分考虑编码过程中的时域和空域相关性，提出了基于时空预测的H.264快速帧内预测模式选择算法，进一步精简候选模式数，从而进一步提高帧内预测模式选择的速度。

2 Pan算法的空域改进

在Pan算法中，分3种块类型(16×16亮度块、4×4亮度块和8×8色度块)分别建立各自的边缘方向帧内预测模式概率直方图，减少候选模式数。Pan算法通过在初始化过程中引入高计算复杂度的Sobel算子运算获得内部块的纹理方向概率直方图，确定候选模式数。Pan算法仅利用了块内部的纹理信息，而未充分利用空域已编码邻块的信息。本文通过引入已编码邻块信息，利用已编码邻块帧内模式构建当前编码块的空域最佳模式概率直方图，确定空域候选模式。

3 Pan算法的时域改进

Pan算法仅利用当前块的内部信息来预测最佳帧内模式，以提高帧内预测模式选择的速度，没有考虑视频序列的时域相关性。此外，在初始化阶段的Sobel算子求概率过程，复杂度较大，较大地增加了编码开销。

视频图像不仅在空域上具有较高的相关性，而且在时域上也有很高的相关性。由于H.264中是先进行多参考帧运动估计，然后进行帧内模式选择确定最终编码模式，因此在进行帧内模式选择之前已获得最佳匹配块。本文利用最佳匹配块构建当前编码块的时域最佳模式概率直方图，预测当前块的最佳帧内模式，并避免复杂的 Sobel算子运算。

4 算法实现

基于时空预测的快速帧内预测模式选择算法利用了帧间运动估计最佳匹配块的信息，为了尽量减少帧间编码的差错扩散，算法对 I帧采用全搜索方法，从而得到 I帧的最佳帧内模式，并保存下来。

基于时空预测的快速帧内预测模式选择算法的流程如图1所示，详细步骤描述如下。

1) 初始化

当一个块编码完毕，保存其最佳帧内模式。每一帧编码结束后，保存该帧的所有不同大小块（每个块包括1个16×16亮度块、16个4×4亮度块和2个8×8色度块）的最佳帧内模式，保存的帧数等于参考帧的总数。

图1 基于时空预测的快速帧内模式选择算法流程

2) 基于空域的模式预测

通过相邻已编码块预测当前块的帧内模式。图2给出了空域模式预测的当前块E及其相邻已编码块A、B、C和D的示意图，由式（1）可求得当前块E的空域最佳模式概率直方图：

其中，M[0]、M[1]、M[2]和M[3]分别为相邻已编码块A、B、C和D的最佳帧内模式；a[0]、a[1]、a[2]和a[3]分别表示A、B、C、D与当前块E的相关程度(值为0到1之间)，h(M[i])表示帧内模式M[i]为当前块最佳预测模式的概率。考虑到A和B与E直接相邻，相关程度较大，而C和D与E是对角相邻，其相关程度相对较小，假定有如下关系：a[2]+a[3]＞a[1]=a[0]＞a[2]=a[3]。实验中，a[0]、a[1]、a[2]和a[3]分别设为1、1、0.7和0.7。

图2 基于空域的模式预测

利用式（1），可以分别得到4×4亮度块、16×16亮度块和8×8色度块的空域最佳帧内模式概率直方图。图3给出了当4×4亮度块的相邻已编码块A、B、C和D的帧内编码模式分别是模式5、模式2、模式3和模式3时，即M[0]、M[1]、M[2]和M[3]的值分别为5、2、3和3，当前块E的空域最佳帧内模式概率直方图。可以看出，模式3的概率最大，模式2和模式5的概率次之，而其余模式的概率很小。将概率直方图中幅值最大者作为空域最佳帧内预测模式，记为P[0]。

图3给出仅存在一个最佳空域帧内预测模式的情况。当A、B、C和D的编码模式均不相同时，A和B的编码模式同为最大概率模式，此时将A和B的模式均作为最佳空域帧内预测模式，分别记为P[0]和 P[1]。

图3 4×4亮度块的空域最佳帧内模式概率直方图

3) 基于时域的模式预测

通过最佳匹配块从时域预测最佳帧内模式。如图4所示，经过多参考帧运动估计得到当前块E的最佳匹配块为R。根据最佳匹配块R在参考帧中与已编码块重叠的位置，可分为R1、R2、R3和R4 4个子块。利用各子块所属已编码块的最佳帧内模式和各子块的像素面积可求得时域最佳模式概率直方图。

图4 最优匹配块帧内模式预测

帧内模式网格的构造过程如下：每一帧编码结束后，按照每个块的空间位置存储每个块的最佳帧内模式，构成帧内模式网格。网格的大小等于块的个数。针对3种不同类型的块(4×4亮度块、16×16亮度块和8×8色度块)，采用3个大小不同的网格来存储不同类型块的最佳帧内模式。

记 1R、 2R、 3R和 4R所包括的像素个数分别为 N[0]、N[1]、N[2]和 N[3]。M[0]、M[1]、M[2]和M[3]分别保存 R1、R2、R3和 R4所属已编码块的最佳帧内模式，块内总的像素数为

由式（2）可以得到时域最佳帧内模式概率直方图。

图5给出了4×4亮度块E的最佳匹配块R的子块R1、R2、R3和R4所属已编码4×4亮度块的最佳帧内模式分别是2、2、4和5时的最佳帧内模式概率直方图。可以看出，模式5的概率最大，模式2的概率次之，接着是模式 4，其余模式的概率很小。取概率直方图中幅值最大者作为时域最佳帧内预测模式，记为C[0]。当出现k个相同的概率最大模式时，将这 k个时域最佳帧内预测模式记为C[k-1]。

图5 4×4亮度块的时域最佳帧内模式概率直方图

针对C[k-1]中是否包括DC模式，进行以下讨论。

a) 对于4×4亮度块，分以下2种情况：

第1种情况，C[k-1]中包括DC模式，此时认为DC模式概率很大，舍弃其他模式，最终只保留DC模式；

第2种情况，C[k-1]中不包括DC模式，将DC模式增加为候选模式。

b) 对于16×16亮度块和8×8色度块，分以下2种情况：

第1种情况，当C[k-1]中存在DC模式时，此时认为DC模式概率很大，舍弃其他模式，最终只保留DC模式；

第2种情况，当C[k-1]中不存在DC模式时，增加DC模式作为候选模式。

4) 得到最终的候选模式

合并上述空域和时域最佳帧内预测模式的结果，得到最终候选模式。

5) 经过以上步骤，候选模式数显著减少，对最终候选模式采用RDO算法求得最佳模式。

5 算法复杂度分析

表1给出了JM98、Pan算法（记为Pan）、基于空域预测的快速帧内预测模式选择算法（记为New1）和基于时空预测的快速帧内预测模式选择算法（记为 New2）的复杂度比较，采用最终候选模式数和是否采用Sobel算子衡量算法复杂度。其中，基于空域预测的快速帧内预测模式选择算法在初始化过程中与Pan算法一样也采用了Sobel算子确定初始的帧内模式，带来了较大的编码代价。基于时空预测的快速帧内预测模式选择算法在 4×4亮度块的基于空域和时域的预测部分时各取得一种模式的概率较高，再加上可能的DC模式，最终的候选模式一般为1或2或3种。

表1 各算法复杂度比较

6 实验结果

实验采用的硬件环境：AMD Athlon(tm) 64 Processor 3200+ 2.0GHz ；512MB内存；操作系统：Windows XP Professional Sevice Pack 2；软件实现平台：JM98校验模型。实验采用5个标准测试序列，包括3个QCIF序列(News、Foreman和Silent)和2个CIF序列(Mobile和Container)。实验参数设置如下。

1) 采用 RDO；

2) 采用CABAC；

3) 采用hardama变换；

4) 帧率，QCIF：10Hz；CIF：30Hz；

5) QP 取值：28、32、36、40；

6) 编码帧数：100；

7) GOP类型：IPPP格式；

8) 运动估计搜索半径，QCIF：16像素；CIF：32像素；

9) 参考帧数：5；

10) 运动估计精度：1/4像素。

采用编码时间、比特率和平均信噪比的减少百分数来衡量算法的优化性能。其中编码时间减少百分数采用式（3）计算。

比特率减少百分数采用式（4）计算。

平均信噪比（PSNR）减少百分数采用式（5）计算。

表2给出了Pan、New1和New2 3种算法CPU总耗时减少百分数比较，基于时空预测的快速算法与其他 3种算法相比，平均编码耗时分别降低35.81%、13.10%和9.98%，编码时间显著减少。表3给出3种算法输出码率减少百分数的比较，基于时空预测的快速算法与其他3种算法输出码率相差不大。表4给出3种算法亮度分量的平均PSNR减少百分数的比较，4种算法的平均PSNR值基本一致。图6给出这5个标准测试序列的率失真比较，这4种算法的率失真曲线基本是重合的，这说明基于时空预测的快速帧内预测模式选择算法与其他3种算法相比，具有基本相同的率失真性能。

表2 编码时间的比较

表3 输出码率的比较

表4 输出PSNR的比较

图6 算法的率失真曲线

7 结束语

通过以上实验和分析，可以得出以下结论，与JM98全搜索算法、Pan快速算法和基于空域的预测算法相比较，基于时空预测的快速帧内预测模式选择算法在保持较好的编码图像质量的同时，平均编码总耗时分别降低35.81%、13.10%和9.98%，显著提高编码速度，从而显著提升H.264的编码性能。

[1] ORTEGA A, RAMCHANDRAN K. Rate-distortion methods for image and video compression[J]. IEEE Signal Processing Magazine,1998, 15∶ 23-50.

[2] WIEGAND T, GIROD B. Lagrange multiplier selection in hybrid video coder control[A]. IEEE International Conference on Image Processing[C]. 2001. 542-545.

[3] KIM H, ALTUNBASAK Y. Low-complexity macroblock mode selection for H.264/AVC encoders[A]. Proceedings of the 2004 Interna-tional Conference on Image Processing[C]. 2004. 765-768.

[4] PAN F, LIN X, RAHARDJA S, et al. Fast Mode Decision for Intra Prediction[R]. JVT 7th Meeting Pattaya, Thailand IEEE JVT-G013,2003.

[5] PAN F, LIN X, RAHARDJA S, et al. Fast mode decision algorithm for intraprediction in H.264/AVC video[J]. Coding Circuits and Systems For Video Technology, IEEE Transactions, 2005, 15(7)∶ 813-822.

[6] WANG J, WANG J, CHEN J, et al. A novel fast algorithm for intra mode decision in H.264/AVC encoders[A]. Proceedings of the IEEE International Symposium[C]. 2006. 3498-3501.

[7] WEI Z Y, LI H L, KING N N. An efficient intra mode selection algorithm for H.264 based on fast edge classification[A]. ISCAS 2007[C].2007. 3630-3633.

[8] TSAI A C, PAUL A, WANG J C, et al. Efficient intra prediction in H.264 based on intensity gradient approach[A]. IEEE International Symposium[C]. 2007. 3952-3955.

[9] 蒋刚毅, 李世平, 叶锡恩等. 基于块参考像素特征的快速帧内预测模式选择新算法[J]. 电子与信息学报, 2006, 28(10).1874-1878.JIANG G Y, LI S P, YE X E, et al. A novel fast mode selection algorithm for intra prediction based on characteristics of block’s reference pixels[J]. Journal of Electronics & Information Technology, 2006,28(10)∶ 1874-1878.

[10] 贾克斌, 谢晶, 方晟. 一种基于自相关法的H.264/AVC高效帧内预测算法[J]. 电子学报, 2006, 34(1).152-154.JIA K B, XIE J, FANG S. An efficient intra-frame prediction algorithm based on autocorrelation for H.264/AVC[J]. Acta Electronica Sinica,2006, 34(1)∶152-154.

[11] 苏睿, 刘贵忠, 张彤宇等. 利用变换域信息快速实现H.264 帧内预测编码的新算法[J], 电子与信息学报, 2007, 29(1)∶161-165.SU R, LIU G Z, ZHANG T Y, et al. Fast mode decision algorithm for intraprediction in H.264/AVC with integer transform[J]. Journal of Electronics & Information Technology, 2007, 29(1)∶161-165.

[12] 陆璐, 周维. 适用于 H.264 的快速模式选择算法[J]. 通信学报,2006, 27(7)∶117-121.LU L, ZHOU W. Efficient inter mode selection algorithm for H.264[J].Journal on Communications, 2006, 27(7)∶117-121.

[13] 黄凯, 秦兴, 严晓浪等. 一种 H.264 帧内预测模式判决算法及VLSI 实现体系[J]. 电子学报, 2007, 35(2)∶207-211.HUANG K, QIN X, YAN X L, et al. A H.264 intra prediction mode decision algorithm and VLSI implementation[J]. Acta Electronica Sinica, 2007, 35(2)∶207-211.

[14] 腾国伟, 王国中, 张兆扬等. 一种基于自适应阈值的H.264/AVC帧内预测模式快速选择算法[J]. 自动化学报, 2006, 32(4)∶526-533.TENG G W, WANG G Z, ZHANG Z Y, et al. A fast intra-prediction mode selection algorithm of H.264/AVC based on adaptive thresholds[J]. Acta Automatica Sinica, 2006, 32(4)∶526-533.

[15] HWANG M C, CHO J K, KIM J S, et al. Fast Intra Prediction Mode Selection Scheme Using Temporal Correlation in H.264[R]. IEEE Region 10 TENCON 2005, 2005. 1-5.

[16] 戴声奎, 喻莉, 朱光喜等. 基于视频时空相关性的帧内预测模式抉择[J]. 通信学报, 2005, 26(11)∶ 43-48.DAI S K, YU L, ZHU G X, et al. Intra-prediction mode decision based on video temporal and spatial correlation[J]. Journal on Communications, 2005, 26(11)∶43-48.