基于边缘检测的帧内预测快速算法

王玉松，赵 明

（清华大学 电子工程系，北京 100084）

1 引言

H.264/AVC[1]引入了帧内预测算法以提高帧内编码效率，但算法复杂度较高，使得帧内编码速度变慢，影响了H.264/AVC的实际应用。因此，研究更简单快速的算法以便广泛应用，即在编码质量影响不大，保持原有编码结构和码率的情况下，降低算法复杂度，提高编码速度，就成了编码研究的热点[2]。

在众多快速帧内编码的研究中，如在文献[3]中，F.Pan等利用了边缘map来获得边缘的强度和方向，大大减少了预测模式个数，此算法已经在JM6中实现。在文献[4-5]中将4×4块化为2×2块，进行各个方向的滤波，选择其中最大的作为边缘方向的预测，减小了模式预测个数，提高了预测速度。

通过对图像边缘特性的统计分析发现，在边缘方向上的像素具有相近的灰度，它们之间具有很强的连续的相关度，而不在边缘方向的像素很少具有这一特性。所以笔者充分利用了这一特性，计算相应模式方向的相关度，然后选择其中较小的几个模式作为候选的预测模式，从而减小了预测模式的数量。由于本算法与其他快速算法独立，在与其他算法结合使用时，将会进一步提高编码速度。

2 快速算法的分析

根据H.264/AVC相关标准可知，在H.264/AVC帧内编码模式选择时，全搜索算法总共需要进行的RDO计算复杂度为：N=4×（9×16＋4）=592，N 为搜索次数。 在 4×4 帧内编码预测模式中，共有9种方向的预测。目前采用的快速算法很多，笔者仅选取其中具有代表性的2种作分析。

2.1 F.Pan等的快速算法[3]

在文献[3]中，通过梯度Sobel算子计算来获得宏块边缘信息的map，这个map包含了边缘方向和边缘强度，通过这个map来计算它的每个方向的边缘强度。两个方向的计算，具体见文献[3]。

选取其中值最大的3种方向模式，再加DC直流模式共4个模式作为候选模式。

文献[3]算法的模式复杂度为：Nmax=3×（4×16＋2）=198；Nmin=2×（4×16＋2）=132。复杂度降低了 66.6%～77.7%。文献[3]算法在计算中采用了3×3的矩阵，只能用3×3的块，但是为与下面的算法比较，即都以16个3×3即12×12大小的块作比较，所以该算法的计算复杂度如表1所示。

很明显该算法在速度上确实有大幅提升，但是码率比FS有了一定的增长，PSNR也有些提高。所以码率和PSNR损失较高是本算法的一个弱点。而在算法的开销上，由于它包含的乘法、除法、函数运算，使它在FPGA等实现时开销很大，这确实是应用中的弱点。

表1 文献[3]算法的运算量统计

2.2 Jhing-Fa Wang等的快速算法[4]

在文献[4]中，首先将宏块化为一个2×2的新块，然后对其中4个新像素块进行预测方向的滤波，每个方向的滤波选用不同的滤波算子，具体计算见文献[4]。

选择其中值较大的作为边缘预测的候选模式，这里每种模式代表相应的4种预测模式。Snd为除其他4种模式外的一种模式，如果是此模式，则选择所有9种模式计算，文献[4]算法的复杂度为：Nmax∶2×（9×16＋2）=292；Nmin∶2×（4×16＋2）=132。 复杂度降低了 49.3%～77.7%。

文献[4]算法运用了滤波。为了与其他算法比较，使用了9个4×4的块即12×12大小的块，所以文献[4]算法的计算复杂度如表2所示。

表2 文献[4]算法的运算量统计

在PSNR上文献[4]算法比文献[3]算法提高了近10倍，码率也下降了1%左右，所以文献[4]算法的优势是PSNR提高比较明显，不过码率还是偏高。同样在算法开销上，它也包含了大量的乘法和除法，这使得FPGA等实现的复杂度不小，这也是该算法的弱点。

3 基于宏块边缘方向的快速算法

为了达到全面准确地了解宏块的边缘特性，减少误判等造成的PSNR损失和码率上升，充分利用了边缘处相邻像素相关的特性。笔者对每种模式方向的相关度，采用相邻像素间相关度的MAD之和来评判这种模式的总体相关度，由于相关性越大，那么它们的差值MAD就小，反之MAD值就大。所以最后选择其中值较小的几个模式作为候选的预测模式，从而减小了模式预测的数量。

3.1 4×4块的快速预测

对于一个4×4块的预测，首先将它按照各个模式方向，计算相应方向的相关度，如图1所示。

图1 4×4块模式预测相关度计算示意图

各个方向的MAD的计算如下：

1）水平（M1）

2）垂直（M0）

3）对角下（M3）

4）对角上（M4）

根据预测方向的对称性，充分利用已计算的方向值，其他几个方向可以通过其相邻方向组合计算出来，而不需要按先前的方法计算。例如，水平上（M8）：MAD22.5=（MAD0＋MAD45）/2。 其他模式方向 67.5°，112.5°，157.5°计算类似。上面公式中的差值为相邻像素间的MAD值，由于边缘处像素相近，它们的相关性大，这样其差值就小。同样如果像素不在边缘处，它们的相关性就小，结果是它们的差值就大。选择其中MAD值最小的3种模式，再加1个总是被选择的DC直流模式，共4个模式作为候选的预测模式。

3.2 16×16亮度块和8×8色度块的预测

对16×16的亮度块，将一个16×16块化为16个4×4的a块，再将每个块下面4×4像素子块b的16个像素的总和作为a块的像素值

a块其他像素值计算类似。

对8×8的色度块，也是先化为4个4×4的a块，再将每个块用其中2×2子块的4个像素值的总和作为a块的像素值。

16×16的亮度块和8×8的色度块的a块的相关度计算类似4×4的亮度块，然后都选用其中值最小的方向模式和常选DC直流模式共2种模式，作为候选的预测模式。

3.3 算法的复杂度分析

在预测模式选择上， 本算法复杂度为：2×（4×16＋2）=132，复杂度降低了77.7%。算法在模式的预测上，总是使用最少的模式，模式的复杂度减少到最大为77.7%，而其他算法都有不同程度降低。

为了与其他算法比较，用了9个4×4的块即12×12大小的块，所以本算法的计算复杂度如表3所示。

表3 改进算法的运算量统计

与其他算法相比，可以发现本算法没有使用复杂度高的乘法和函数，所以计算的复杂度比其他算法低。本算法由于复杂度较低，规律性强，所以能够在FPGA等上很好地实现并行计算。

4 实验结果及分析

在JM10的代码基础上进行实验，使用了JM10的相关测试模型。其编码特性分别在QP为28，32，36，40下获得，其中的 ΔPSNR，Δt，ΔRbit为相应算法与 JM10.0 中基于RDO的FS算法比较所得的差值。具体见表4～5和及图2～3。

图2 News序列的RD曲线

图3 Mobile序列的RD曲线

从测试中可以发现，改进后的算法比文献[3]与文献[4]的快速算法在速度上都有6%～10%的提高，比文献[3]算法码率下降了1.5%，PSNR提高了5倍，比文献[4]算法的码率也有一定降低。与FS相比，PSNR基本保持不变，CIF序列的速度平均提高了65.98%，码率平均只提高了2%；对于QCIF序列，速度平均提高67.07%，其码率平均也只提高了2%。可以看出，本算法与其他快速算法相比，速度、码率、PSNR都有了不同程度的改善，效果是明显的。

5 小结

笔者提出了一种H.264/AVC帧内编码的快速算法，它利用宏块边缘处像素具有很强的相关度特性，通过计算在各个预测方向的相关度值，选择其中最小的几个值作为候选的预测模式，降低了模式预测的复杂度。实验结果证明，本算法比H.264/AVC算法有了66%左右的提高，而PSNR基本保持不变，与其他算法[2-3]相比都有不同程度的性能提高。由于本算法计算复杂度比较低，能够很好地适用于VLSI的实现。

表4 采用QCIF序列3种算法的性能比较

表5 采用CIF序列3种算法的性能比较

[1]Joint Video Team of ISO/IEC MPEG&ITUT VCEG.ITU-T Recommendation and Final Draft International Standard of Joint Video Specification （ITU-T Rec.H.264 ISO/IEC 14496-10 AVC）[S].2003.

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

[3]PAN F，LIN X，RAHARDJA S，et al.Fast mode decision algorithm for intra prediction in H.264/AVC video coding[J].IEEE Trans.Circuits and Syst.Video Technol.，2005，15（7）：813-822.

[4]WANG J F，WANG J C，CHEN J T，et al.A novel fast algorithm for intra mode decision in H.264/AVC Encoders[C]//Proc.2006 IEEE Int.Symp.Circuit Syst.Island of Kos，Greece：IEEE Press，2006：3498-3501.

[5]TSAI A，WANG J，LIN W，et al.A simple and robust direction detection algorithm for fast H.264 intra prediction[C]//Proc.2007 IEEE International Conference on Multimedia and Expo.[S.l.]：IEEE Press，2007：1587-1590.