基于兰氏距离的H.264/AVC帧内快速算法*

霍利岭，张有会，王志巍，杨会云，赵 金

（河北师范大学 数学与信息科学学院，河北 石家庄 050016）

1 引言

基于空域的帧内预测是H.264/AVC[1]的重要组成部分。H.264/AVC采用全搜索算法进行帧内预测，使帧内预测具有很高的计算复杂度。因此，人们提出了很多快速算法。F.Pan等提出基于边缘方向直方图的帧内模式快速选择算法[2]；Kim等通过计算4×4块的SAD和SATD值，根据两者直方图的混合特征减少候选模式的个数[3]；Jong-ho Kim等利用帧间信息来进行帧内模式的快速选择[4]。国内也有大量文献进行了相关研究[5-7]。笔者利用宏块内部相邻像素值的差异判定宏块的类型，进行Intra_4×4和 Intra_16×16的快速选择。 对于 Intra_4×4模式，根据4×4块的纹理方向排除不必要的候选模式。

2 H.264/AVC的帧内预测算法

H.264/AVC的帧内预测充分利用图像的空间相关性，用当前块的左边和上边像素值进行预测（如图1所示）。编码时，只对宏块实际值和预测值的差值进行编码，从而减少编码的码率。H.264/AVC标准算法有3类帧内预测方式：4×4 亮度块预测（Intra_4×4）、16×16 亮度块预测（Intra_16×16）、8×8 色度块预测（Intra_chroma）。其中，Intra_4×4 有 9种预测模式，包括8种方向性预测和1种均值预测（如图2所示）。Intra_16×16有4种预测模式 （如图3所示）。Intra_chroma预测方式与Intra_16×16相似，有4种预测模式[1]。

图1 宏块预测

图2 Intra_4×4预测方向

图3 Intra_16×16帧内预测模式

JVT提供的参考模型中，色度块的预测方式较为简单，亮度块的预测方式较为复杂。因此这里只讨论亮度块预测方式的快速算法。

3 H.264/AVC帧内快速选择算法

3.1 宏块类型的判定

宏块可以分为平坦宏块和非平坦宏块。Intra_16×16模式适用于平坦宏块，而Intra_4×4模式适用于非平坦宏块。如果可以提前判断出宏块的类型，就可以提前从Intra_4×4和Intra_16×16中选择一种模式，排除不必要的模式。

通过分析可知，平坦宏块内部相邻像素间的灰度值变化不大，即宏块在水平和垂直方向相邻像素值的差异较小。因此，可以利用宏块在水平和垂直方向的相邻像素值差异来判定宏块的平坦性。

设Ghor，Gver分别表示水平和垂直方向相邻像素值的差异，表示如下

其中，f（x，y）为在（x，y）处的像素值。

令G=Ghor+Gver，既考虑了宏块在水平方向的像素值的差异，又考虑了在垂直方向像素值的差异，因此G的大小可以在一定程度上反映宏块的平坦性。

如图4所示，宏块1、宏块2、宏块3为Foreman序列第0帧中的3个平坦程度不同的宏块。相应的差异值如表1所示。

图4 Foreman序列的第0帧

表1 不同宏块的相应差异值

由表1可知，G的值越小宏块越平坦。因此，可以设定阈值T，如果G＜T，则表明当前宏块比较平坦，只进行Intra_16×16帧内预测；否则表明当前宏块纹理复杂，只进行Intra_4×4帧内预测。

3.2 基于兰氏距离的Intra_4×4模式快速选择算法

兰氏距离（也称Canberra距离）是由Lance和Williams最早提出的[8]，它是聚类分析中一种度量距离的常用方法。X1和X2的兰氏距离计算公式如下

式中：d（X1，X2）越小表示 X1和 X2的接近程度越大，d（X1，X2）越大表示X1和X2接近程度越小。

本文以兰氏距离为度量，提取4×4块的纹理方向，主要思想如下： 计算 4×4 块在 0°，45°，90°和 135°这 4 个主要方向的兰氏距离和，然后比较大小，找出最小值。由于兰氏距离和越小，表示该方向上的像素值变化越小，因此兰氏距离和的最小值对应的方向即为当前4×4块的纹理方向。

为了得到更准确的纹理方向，获取当前4×4子块的像素值以及上边一行和左边一列的像素值，组成1个5×5的图像块 X。计算 X 在 0°，45°，90°和 135°这 4 个方向的兰氏距离 Dθ（θ=0°，45°，90°，135°），每行相邻像素间的兰氏距离之和D0的公式如下

式中：f（x，y）为 X 在（x，y）处像素值。 同理可定义 D90为

D45的计算方法如图5所示，图中的箭头方向为差分方向。D135的计算公式与D45类似。

D0，D45，D90，D135中的最小值对应的方向为当前4×4子块的纹理方向。将与此纹理方向对应的预测模式（mode）加入到预测范围。考虑到预测模式的相关性以及DC模式的特殊性，将与mode相邻的2个模式mode1，mode2和DC模式也加入预测范围，使Intra_4×4的预测模式由9个减少为4个，从而加快编码速度。

图5 D45的差分方向

4 帧内模式快速选择算法描述

算法首先计算宏块相邻像素值的差异G，结合给定的阈值T判定宏块的类型，进行Intra_4×4和Intra_16×16模式的快速选择。其中，T的取值对编码的性能影响很大，实验结果表明，T取值为600时获得的编码效果最好。而对于Intra_4×4模式，采用基于兰氏距离的Intra_4×4模式快速选择算法。

具体实现步骤如下：

1）获取宏块的亮度数据，并设定阈值T。

2）计算当前宏块内部相邻像素值的差异G。

3）若 G＜T，转到 4），只进行 Intra_16×16 模式选择，否则，转到5），只进行Intra_4×4模式选择。

4）采用H.264/AVC标准算法进行Intra_16×16模式选择，宏块预测结束。

5）采用基于兰氏距离的Intra_4×4快速选择算法，具体过程如下：（1）获得当前4×4块的数据以及其上边行和左边列的数据，组成一个5×5图像块X；（2）计算X在 0°，45°，90°，135°这 4 个方向的兰氏距离 D0，D45，D90，D135；（3）选取 D0，D45，D90，D135中的最小值对应的模式mode以及与其相邻的2个模式mode1，mode2和DC模式加入到预测范围，则Intra_4×4的预测范围为（mode，mode1，mode2，DC）；（4）计算预测范围内4个模式的RD_Cost值，选取具有最小RD_Cost值的模式作为Intra_4×4的最佳模式；（5）重复（1）～（4）直到预测完宏块内所有 4×4 子块，宏块预测结束。

6）循环1）～5），直到预测完所有宏块，算法结束。

5 实验结果及分析

为了验证算法的性能，在H.264参考模型JM13.2上对快速算法进行了仿真实验。编码配置为：帧率30 f/s（帧/秒）； 全I帧序列； 编码帧数为100帧；QP=28；RDO开；CAVLC 开。 硬件配置为：AMD Athlon 64 X2 3600＋；主频 2.0 GHz；内存 1.0 Gbyte。

表2列出了新算法与全搜索算法针对10个QCIF标准视频序列的的结果比较。

表2 新快速算法与全搜索算法对比结果

表2中，Rt表示编码时间变化的百分比，ΔPSNR表示峰值信噪比的变化，Rbit表示比特率变化幅度的百分比，由表2可知，本文算法与全搜索算法相比，各指标变化的平均值为：速度提高51.53%；PSNR降低0.06 dB；码率提高1.98%。

图6给出了Foreman序列的RD曲线。由图可知，本文算法的RD曲线与JM13.2全搜索算法的RD曲线基本重合。这表明本文算法在编码时间明显降低的同时，图像质量和码率的变化很小，从而验证了本文算法的有效性。

图6 Foreman序列的RD曲线

6 结论

本文首先利用宏块相邻像素值的差异结合预先给定的阈值判定宏块的类型，进行Intra_16×16和Intra_4×4快速选择。对于Intra_4×4模式，利用兰氏距离提取图像的纹理方向，根据得到的纹理方向排除可能性小的模式，进而进行Intra_4×4模式的快速选择。实验结果表明，本文算法在PSNR和码率变化很小的情况下，极大地提高了编码速度。

[1]ISO/IEC 14496-10，Information technology coding of audio visual objects，Part 10[S].2004.

[2]PAN F，LIN X，RAHARDJA S，et al.A directional field based fast intra mode decision algorithm for H.264 video coding[EB/OL].[2009-09-10].http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1394420.

[3]KIM C，SHIH H H，KUO C J.Feature-based intra prediction mode decision for H.264[C]//Proc.2004 IEEE International Conference on Image Processing（ICIP）.[S.l.]：IEEE Press， 2004：769-772.

[4]KIM Jong-ho，KIM Byung-gyu.Fast block mode decision algorithm in H.264/AVC video coding[J].Journal of Visual Communication and Image Representation，2008，19（3）：175-183.

[5]刘代如，宋昊，李晓辉，等.H.264中一种快速帧内预测判决算法[J].电视技术，2007，31（4）：10-11.

[6]王日霞，朱伟兴，陈先勇.H.264基于宏块自适应的快速模式选择算法[J].电视技术，2009，33（2）：14-17.

[7]王海勇，孙雁飞，吴启宗.H.264编码中帧内预测算法研究[J].电视技术，2009，33（8）：11－12.

[8]朱玉全，杨鹤标，孙蕾.数据挖掘技术[M].南京:东南大学出版社，2006.