一种H.264模式决策算法的快速实现
2009-08-11
作者:高 参,陆铁军
摘 要:MPEG4 AVC/ITU-T H.264视频编码标准因其优异的编码效率和性能而被广泛采用,但其模式决策问题导致运动估计器运算复杂度非常大。本文提出一种快速模式决策算法的实现方法。仿真结果证明,本方法在编码质量降低较小的情况下,能够减少80%以上的编码时间。
关键词:H.264 快速模式决策 编码器复杂度
1 现有的快速决策算法
ITU-T和ISO/IEC组成的联合视频专家组(JVT)于2003年3月公布了H.264/MPEG-4 AVC标准(以下简称H.264)。与MPEG-4 ASP标准相比,在编码质量相同的情况下,编码率可以减少50%。这一优异性能的取得很大程度上得益于H.264所采用的多模式、多参考帧的运动估计编码算法和多模式帧内预测编码算法。但是,其采用的基于最佳码率和失真折衷(Rate-Distortion Optimization,RDO)的模式决策算法,使编码算法的复杂度提高了3倍,编码时间也大大增加。而且,H.264用于模式决策的时间占整个编码时间的80%~90%。所以,如何有效加快模式决策过程的实现速度,成为当前研究的热点。
针对运动估计模式的快速决策算法已有如下几种:(1)通过3×3的Sobel计算得到当前宏块的边缘矢量图(Edge Map),然后利用每点边缘矢量的幅度值之和的统计特性去判断宏块的空间一致性,并根据一致性越强所采用的运动估计块越大的原则,减少进行复杂的码率和失真折衷值(Rate-Distortion Cost,RDC)计算的候选模式数量。但是,由于Sobel计算涉及每个象素点,因此它本身的计算量也很大。(2)利用模式间的相关性把7种模式分组,计算有代表性的16×16、8×8、4×4三种模式的RDC值,通过分析结果选择出最佳的模式组,然后只对组内的候选模式进行RDC计算。这种算法没有考虑编码图像自身的特性,能够删除的候选模式不多。(3)只进行基于8×8子块的运动估计,通过分析得到的4个运动矢量间的相似性进行估计块(即模式)的合并,合并后得到的模式即为最佳模式。此外,也有学者针对帧内编码模式的选择,提出了多种快速算法。
本文提出一种适合在移动终端设备等计算能力有限的应用场合下进行H.264实时编码的快速模式决策算法的实现方法。该方法具有计算复杂度低和逻辑简单的特点。实验证明,在图像质量和压缩效率降低很少的情况下,该方法使编码速度提高了80%以上。
2 H.264的模式决策算法
H.264采用8种帧间编码模式,包括7种采用不同大小和形状的运动估计块对宏块进行运动估计的编码模式和SKIP模式。H.264帧间预测模式如图1所示,其决策算法是:首先,对宏块分别计算16×16、16×8、8×16和SKIP 4种模式下的RDC值;然后,对宏块中的每一个8×8子块分别计算8×8、8×4、4×8和4×4 4种子模式下的RDC值,得到具有最小值的最佳子模式,再将子块的最小RDC值相加得到宏块在模式下的RDC值;最后,在宏块层次上比较各模式RDC值,选取值最小的模式作为宏块最佳编码模式。
在帧内编码方面,H.264采用基于4×4子块和基于16×16宏块的2种预测模式,其中4×4模式有9个预测方向,宏块模式有4个预测方向。在最新的参考软件JM9.3中加入了基于8×8子块的预测模式。每一种预测模式都是利用相邻已编码块的样点值去预测当前块的样点值。H.264要分别计算宏块在基于4×4、16×16和8×8 3种模式下的各个预测方向的RDC值,并选择值最小的模式作为最佳帧内预测模式。如果当前编码宏块属于帧间预测帧(P帧),该最小值还要与最佳帧间编码模式的RDC值进行比较来确定最佳模式。
H.264协议采用Lagrange代价函数计算每种模式下宏块的RDC值,其定义如下:
式(1)中,JMODE表示相应模式的RDC值,λMODE是Lagrange因子,其值与量化系数有关。R(s,c,MODE)指的是该模式所需的编码比特数。SSD(s,c,MODE)指的是原始宏块和重建宏块之间的平方差之和,其定义如下:
式(2)中,S(x,y)表示原始宏块,C(x,y)表示重建宏块。
通过上面的分析可以看到,H.264在进行宏块模式决策时,运动估计、量化、反量化和DCT变换等操作被多次反复调用,这样的计算强度对于实时性要求较高的视频通信应用及处理能力相对较弱的手持设备而言是很难被接受的。
3 模式决策算法的快速实现
3.1 提出方法的动机
H.264协议帧间模式决策的基本原则是:对只含有背景成分、全局运动成分或很少量局部运动成分的宏块采用大估计块模式进行编码;对于含有丰富运动成分的宏块采用小估计块模式进行编码。由此可以得出:随着7种运动估计块自大向小被调用,宏块的RDC值呈现出近似的单调变化趋势。所以,通过对这种趋势的分析,很可能在不调用所有模式的情况下得到最佳编码模式。
使用H.264参考软件JM9.3对9个QCIF和CIF格式的图像序列进行编码实验,编码模式的分配情况如表1所示。从表中可以得到很多关于图像统计特性的信息:(1)SKIP模式被使用的概率相当高,特别是那些类似于视频通信应用的图像序列,如Claire、News等序列。这表明对这些图像进行编码时如果能够尽早确定是否采用SKIP模式,将使模式决策过程所需的时间大大减少。(2)P帧中的宏块使用帧内预测编码模式(表中INTRA列)的概率很低,所以对P帧中的宏块不采用帧内模式对编码质量不会产生大的影响。(3)对于8×8的子块采用8×4、4×8、4×4 3种子模式的概率较低,特别是在那些类似于视频通信应用的序列中,这3种子模式被使用的概率只有1%左右,而含有许多运动成分的图像序列使用这3种子模式的概率大约是2%~10%。由于算法主要针对小尺寸视频图像在移动终端设备中的应用,为了大幅度降低算法复杂度可以去掉这3种子模式。
3.2 帧间模式决策算法的快速实现
通过分析,本文提出一种快速模式决策算法的实现方法。具体步骤如下。
第1步:计算编码宏块SKIP模式的RDC值JSKIP并与阈值TSKIP比较,若小于阈值则表示SKIP模式为最佳模式,模式决策过程结束;否则,到第2步。其中阈值TSKIP的确定方法是根据经验确定一个比较小的初值,在编码过程中利用所有用SKIP模式编码的已编码宏块的RDC值的均值动态改变它。
第2步:计算16×16模式的RDC值J16×16和16×8模式的代价函数值J16×8,若J16×8-J16×16≥T16,则表示随着运动估计块的变小,宏块RDC值增大的趋势已经明显,所以设16×16模式为最佳模式,模式决策过程结束;否则,到第3步。其中阈值T16的确定方法与第1步中TSKIP的确定方法类似。
第3步:计算8×16模式的RDC值J8×16,若J8×16-J16×16≥T16,则根据与第2步相同的原因,设16×16模式为最佳模式,模式决策过程结束;若J16×8-J16×16≥T16且J8×16-J16×16≥T8,也可认为随着运动估计块的变小,宏块RDC值有增大趋势,所以设16×16模式为最佳模式,模式决策过程结束;若J8×16
第4步:计算8×8模式的RDC值J
8×8,并与上面得到的各种模式的值进行比较,得到最佳模式。
3.3 帧内模式决策算法的快速实现
关于帧内预测模式决策算法的快速实现,本文提出的方法的核心思想是利用反映图像空间特性的原始图像和预测图像在变换域中的绝对差值之和(SATD)与J
MODE值之间的相关性,减少需要RDC计算的候选模式的数量。SATD定义如下:
式中I(x,y)表示原始图像值,P(x,y)表示预测图像值,T{}表示Hadamard变换,b
k表示取值范围,即块的大小。
方法的具体步骤是:(1)计算每个4×4子块基于4×4预测模式的可能预测方向上的SATD值。(2)选择具有最小SATD值的3个模式进行RDC值的计算,如果由相邻的已编码块得出的最可能模式没有被包含其中,则还要计算这种模式的RDC值。(3)选出具有最小RDC值的模式为4×4子块的最佳模式。对基于8×8块的预测模式的选择采用同样的办法。
4 仿真结果
根据本文提出的方法,修改软件JM9.3的相应部分,并对8个格式为CIF和QCIF的图像序列进行了编码仿真。具体的仿真环境:编码帧数为100,参考帧数为5,序列形式为IPPP,固定的量化系数(28、38),CAVLC熵编码。此外,采用JM软件默认的运动估计算法,搜索范围为16。本方法的仿真结果如表2所示。表中ΔPSNR-Y表示本方法与原算法编码图像亮度信号之间的PSNR差值,ΔBitrate表示比特的增加比率,Speed Up表示编码时间的减少比率。仿真结果表明,本方法虽然使得图像质量有所下降,但明显减少了编码时间。
5 结束语
本文提出的H.264模式决策算法的快速实现方法,有效利用了图像序列和编码模式的统计特性和空间特性。因此,本方法能够在编码质量下降不多的情况下,大幅度地降低编码时间和算法复杂度,使H.264协议更适于移动终端设备的视频通信应用。下一步的工作重点是改进运动估计的搜索算法,拟采用自适应路径搜索算法(Adaptive Root Pattern Search,ARPS),以及整个决策算法的硬件实现和仿真。
参考文献
1 Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification.ITU-T Rec.H.264 | ISO/IEC 14496-10 AVC,2003
2 Wiegand T,Sullivan G J,Bjontegaard G et al.Overview of H.264 Video Coding Standartd.IEEE Trans on Circuits and Systems for Video Technology,2003;13(7)
3 Wu D,Wu S,Lim K P et al.Block Inter Mode Decision for Fast Encoding of H.264.In:IEEE Int′l Conference on Speech Acoustics and Signal Processing,2004
4 Yin P,Tourapis H Y,Tourapis A M et al.Fast Mode Decision and Motion Estimation for H.264.In:IEEE Int′l Conference on Image Processing,2003
5 Tu Y,Yang J,Shen Y et al.Fast Variable-size Block Motion Estimation Using Merging Procedure with an Adaptive Threshold.In:IEEE Int′l Conference on Multimedia & Expo,Baltimore,Maryland,2003
6 Kim C S,Shih H H,Kuo C J.Feature Based Intra-prediction Mode Decision for H.264.In:IEEE International Conference on Image Processing,2004