基于改进梯度算子的快速视频编码算法

蓝 敏

(长沙民政职业技术学院,湖南 长沙 410004)

基于改进梯度算子的快速视频编码算法

蓝 敏

(长沙民政职业技术学院,湖南 长沙 410004)

针对H.264的高复杂性，提出基于改进梯度算子的快速帧内帧间模式选择算法。借助运算量极小的改进梯度算子得出块的梯度方向，以此来指导帧内模式的选择和帧间模式的划分。这种算法使得模式选择跳出了全遍历，只锁定在部分模式中，从而大大减少了时间复杂度，而且码流不会明显增加，视频质量也较佳。

视频编码；帧间预测；帧内预测；模式选择；基于纹理

随着H.264/MPEG-4 part 10被联合视频组（Joint Video Team(JVT)，formed by ITU-T VCEG and ISO/IEC MPEG）作为新一代编解码标准发布，视频编解码效率得到了很大的提高，但是复杂度也提高了不少[1][2]。特别是率失真优化（The rate distortion optimization(RDO)）技术的应用，使得编码质量提高并且码率也得到了下降，但是它却是以遍历帧内帧间模式为代价的：帧内预测中亮度有9种模式，色度有4种；帧间预测中每个宏块可以分割成7种宏块模式和4种子宏块模式。采用各种方式编码后编码效果和码率差别较大，因此，每个宏块的模式选择是编码过程中非常关键和耗时的步骤。

众多快速算法应用而生。快速帧内预测模式选择算法[3]，利用Sobel算子生成边缘方向直方图，找到相关性最强的方向模式，并使用其进行预测编码，可大大减少不相关的模式计算，从而减小时间复杂度，但是要进行三角函数运算和直方图统计，比较耗时。Jia-Ching Wang等人提出了一个简单的边缘检测算法[4]，用五个空间域滤波器处理每个下采样后的宏块，通过比较滤波后的值来判断宏块纹理的走向。它被MPEG-7做为特征描述符采纳，达到了更好的对比效果。An-Chao Tsai提出了一个更简便的算子[5]，他并不考虑所有的像素，仅用一部分像素得出每个方向的梯度值，用以检测块的边缘方向。

在帧间算法里，Inchoon Choi采用SKIP模式提前中止策略，这样可以省掉后面很多模式的判决；针对在帧间编码时还要遍历intra4×4、intra16×16这两种帧内预测模式的情况，他通过比较宏块时间和空间相关性大小的方法来有选择地进行帧内模式预测[6]。但他仅限于优先SKIP模式和排除不必要的帧内预测模式，除此之外的帧间模式未给予考虑。Andy C.Yu[7]提出利用当前块的DCT系数计算该块的能量，从而得到块的纹理复杂度，进行快速划分模式的选择。该技术的一个不足之处是依靠AC系数总能量来判断宏块细节高低，这样必须对宏块进行额外的DCT变换，而DCT变换计算量较大。

针对这些弊端，本文提出了基于改进梯度算法的帧内帧间算法。首先用改进梯度算子快速得出块的梯度方向，之后以梯度方向为依据求出最佳帧内预测模式。再利用梯度方向按照从大块到小块的顺序去划分帧间模式，即先计算skip模式和inter16×16模式，再有选择地计算较小模式，从而快速锁定最佳帧间模式。

1.改进梯度算子

在文献[5]中，图象梯度如图所示，每个方向取出四个标黑了的像素的梯度。（见图1-1）

梯度算子是：G(x)=-1/2*P(x-1)+1/2*P(x+1)

G(x)代表像素x的梯度强度，当它接近或者等于0时，意味它有个方向。

图1-1 基于梯度算子的四个方向

梯度算子在四个方向都能得到很好的效果，但是仔细研究发现，它实际上只取了部分像素计算其梯度，并不够精确。对它的一种改造如下[8]：

预测4×4块的纹理方向：

图1-2 下采样4×4亮度块

以平均值为依据计算出纹理的走向 (挑出以下最小值的就是这个4×4块的纹理走向)。

可以看出，式1-1反映了四个方向上像素块的紧密程度， （x＝0、45、90、或 135）越小，纹理的走向越接近这个方向。

2.基于改进梯度算子的快速帧内算法

由上一节可以得到每个4×4块的梯度方向，而帧内预测模式和梯度方向有极大的相关性。9种帧内预测模式中，除了DC模式是没有方向的，其余8种代表了8个不同方向。于是选取梯度方向及其相邻的两个方向的模式，再加上DC模式，总共只要计算4种模式，这比起JM要遍历9种模式，节省了50%以上的计算复杂度。

同理，可以求出16×16块的模式方向，只不过下采样时，涉及的像素点更多。采样块还是以上图1-1为例，但a～p不是16个像素，而是16个4×4小块的平均值。由于16×16宏块只有4个方向的模式选择，所以只要计算梯度方向的模式和DC模式，同样也能节约不少的计算复杂度。

3.基于改进梯度算子的快速帧间算法

尽管H.264中编码模式很多,但通过对不同复杂度视频序列的仿真,发现7种编码模式所占比例并不均衡，skip模式和inter16×16模式占据了很大的比重。这是因为在自然视频序列中存在着一些空域上均匀或者时域上平稳的区域,如图像的背景区域等。在这种类型的区域中,通常以比较大的块尺寸进行编码比如inter16×16或者skip模式。本文首先考虑这两种模式，并计算它们的率失真代价值。

接着，开始考虑其他模式，按照大块到小块的顺序对当前块计算率失真值，符合终止条件时，即可不做之后的遍历。根据仿真实验可知，只要小块模式的率失真值比大块的大，遍历即可终止；否则，继续搜索计算更小的模式。比inter16×16小的有inter16×8和inter8×16，比 inter8×8 小的也有 inter8×4、inter4×8 和inter4×4，到底应该采用哪一种呢？这个时候，用梯度方向来决定小块模式的选择。

小块模式划分的准则是：

1.分的原则：梯度方向是水平的块，小块模式采用水平划分；梯度方向是垂直的块，小块模式采用垂直划分。如：16×16的4个8×8小块中，只要有3个及3个以上的块是水平的，那么16×16块就分为两个16×8小块；只要有3个及3个以上是垂直的，那么16×16块就分为两个8×16小块。也就是说在计算完skip模式和inter16×16模式的率失真值后，我们只要计算inter16×8或inter8×16模式二者之一就可以了。

2.合的原则：相邻小块的梯度方向如果相同，那么这两个小块就可以合并。如：8×8小块中有4个4×4的小块，它们的梯度方向如果相同，就可以合并为8×4小块或者4×8小块。

有了这两个准则，在计算完skip和inter16×16模式后，可以清楚地知道接下来该采用哪种较小的模式。如果这种较小模式的代价值比之前的更小，那么再考虑选择更小的模式；如果这种较小模式的代价值比之前的更大，那么遍历终止。

4.实验结果及对比

实验在JM12上进行。表1是JM编码器参数配置，表2是实验数据。

表2

5.结束语

在JM12平台中，帧内模式选择和帧间模式选择是分开进行的。如果要用帧内模式进行编码（如I帧），那么不必考虑帧间模式，我们可用改进梯度算子方便地得到帧内编码模式；如果要用帧间模式进行编码(如P帧)，JM12平台仍然会去计算帧内模式intra4×4、intra16×16(如在实时视频的场景发生变化时，后一帧是无法利用前一帧进行编码的，此时最好是采取帧内模式编码)。既然帧间模式选择也要用到帧内模式，那么改进梯度算子就有了很大的通用性。

[1]ITU-T Recommendation H.264.Advanced Video Coding for Generic Audiovisual Services,H.264 Standard,2005.

[2]Wiegand,T.,Sullivan,G.J.,Bjontegaard,G.,Luthra,A.Overview of the H.264/AVC video coding standard.IEEE Trans.Circuits Syst.Video Technol.,vol.13,no.7,Jul.2003.560-576.

[3]Feng Pan,Xiao Lin,Rahardja,S.,Lim,K.P.,Li,Z.G.,Dajun Wu,Si Wu.Fast mode decision algorithm for intraprediction in H.264/AVC videocoding.IEEE Trans.Circuits Syst.Video Technol.,vol.15,no.7,Jul.2005.813-822.

[4]Jia-Ching Wang,Jhing-Fa Wang,Jar-Ferr Yang,Jang-Ting Chen.A fast mode decision algorithm and its VLSI design for H.264/AVC intra prediction.IEEE Trans.Circuits and Syst.Video Technol.,vol.17,no.10,Oct.2007.1414-1422

[5]An-Chao Tsai,Anand Paul,Jia-Ching Wang,Jhing-Fa Wang.Intensity Gradient Technique for Efficient Intra-Prediction in H.264/AVC.IEEE Trans.Circuits Syst.Video Technol.,vol.18,no.5,May 2008.694-698.

[6]Choi,I.,Lee,J.,Jeon,B.Fast Coding Mode Selection with Rate-Distortion Optimization for MPEG-4 Part-10 AVC/H.264.IEEE Trans.Circuits Syst.Video Technol.,vol.16,no.12,Dec.2006.1557-1561.

[7]Yu,A.C.Efficient Block-size Selection Algorithm for Inter-frame Coding in H.264/MPEG-4 AVC Acoustics IEEE International Conference on Acoustics,Speech and Signal Processing,vol.3,no.17-21,May 2004.169-172.

[8]Tsai,A.C.,J.F.Wang,J.F.Yang&W.G.Lin.Effective Subblockbased and Pixel-based Fast Direction Detections for H.264 Intra Prediction[J].IEEE Trans.Circuits Syst.Video Technol.,2008,18(7):975-982.

[9]毕厚杰.新一代视频压缩编码标准-H.264/AVC[M].北京:人民邮电出版社，2003.

[10]余兆明，查日勇，黄磊，周海娇.图象编码标准H.264技术[M].人民邮电出版社,2005.

TP301

A

1671-5136（2011） 01-0120-03

2010-12-13

蓝敏(1982-)，男，湖南长沙人，长沙民政职业技术学院软件学院助教、硕士。研究方向：计算机图形图像。