H.264运动估计算法的优化

摘 要 :通过对H.264中运动估计的分析,选择合适的快速搜索算法来对H.264算法进行化简,对菱形快速搜索算法、分像素的运动估计算法进行了改进,减少了H.264巨大的计算量.

关 键 词 : H.264/C视频压缩编码运动估计搜索算法分像素预测

H.264图像编码标准是ITU-T的视频编码专家组(VCEG)和ISO的活动图像专家组(MPEG)共同制定的新一代国际编码标准.它具有多个闪光点,如统一的VLC符号编码,高精度、多模式的位移估计,基于4×4块的整数变换,以及分层的编码语法等[1].这些使H.264具有很高的编码效率,可适应高图像质量和低速率应用的要求.

H.264在编码效率方面的成功是以增加复杂度为代价的,复杂的运算成为了制约其发展的因素.如何简化H.264的计算是当今视频编码的热点问题.为此本文提出对H.264的运动估计算法进行优化,改进算法中的不足以达到减少运算的效果.

1.整像素运动估计算法优化

在视频压缩编码领域,为了减少计算复杂度并保证图像质量,通常采用简化全搜索算法运动估计的方法,因为其占用整个编码器大约80%的计算量.

为了减少搜索次数,研究人员提出了多种快速搜索方法,主要有对数搜索法(LOGS)、三步搜索法(TSS)、新三步搜索法(NTSS)、新六边形搜索法(HEXBS)、预测搜索法等.除了矩形窗搜索模式外,还出现了菱形模式、六边形模式、十字形模式以及这些模式相结合的混合模式等[2-3].4T搜索算法是一种新的搜索算法,它能很好地捕捉剧烈的运动或变换的边缘部分,但是,对于平缓区,却不可避免的带来了图像信噪比的下降.

在各种算法中,菱形搜索算法(DS)的综合性比较优越.它采用两种搜索模板:9搜索点的大模板LDSP和5搜索点的小模板SDSP.搜索时先设定固定的阈值,再用LDSP计算.当最小宏块误差点出现在中心点处时,将LDSP换为SDSP进行计算.这时5点中的最小宏块误差点若在中心处,此点即为最优匹配点.否则,将最小宏块误差点作为新的中心点用LDSP重复搜索.实际应用中绝大部分视频图像存在中心偏移性,即运动矢量高度集中在零矢量及其附近.对运动矢量为零的宏块称为静止块,其它的块称为运动块.在视频图像中有超过80%的块可看作静止块,这种情况下如果同等对待搜索区域的各部分,势必造成较大的搜索冗余,影响搜索速度.针对这些不足,可对块的类型加以分类,分离出静止块和小运动块,采用小模板SDSP进行搜索,而剩余的少许大运动块则采用4T搜索方式.分类后,先对原搜索方法阈值相对固定的情况进行改进,通过设置不同的阈值来处理不同的情况,并结合起点预测和组合模板搜索策略,实现一种快速运动估计算法.

改进后的DS算法流程如图1所示,首先利用相邻宏块的运动矢量来预测当前宏块的搜索起点,并根据图像的运动类型和内容,自动选择下一步适用的搜索方式,这样使中心偏移更集中,提高了搜索速度.对于小运动块和静止块使用SDSP模板只需要搜索5个点就可以结束.而对大运动块进行搜索时,则改用4T算法.

搜索具体步骤:

Stepl:用中值法求出当前运动矢量的预测值作为搜索起始值,以预测点为初始搜索点,以该点为原点建立搜索区域.

Step2:以原点为小菱形模板的中心,在SDSP上5个点分别进行匹配计算,寻找SAD值最小的点,同时设立两个门限T0, T1(T0

(1)若最优点不在原点处且匹配误差小于门限值T1时,认为运动很小,进行Step3,

(2)若最优点位于原点并且匹配误差小于门限值TO时,认为静止,搜索中止,进行Step5,

(3)若最优点为其他情况时,认为运动很大,进行Step4.

Step3:以上一次的最优点作为中心点,继续使用菱形模板SDSP,在5个点分别计算SAD值,找出最小值的点,然后:

(1)若最优点位于中心,进行Step5,

(2)若最优点位于周围4个点处,重复Step3,

(3)若模板的点超出搜索范围,该点视为无效.

Step4:采用4T算法.

Step5:将该中心点作为最佳匹配点,得到运动矢量.

通过初始搜索点的预测使第一次搜索就能得到最佳匹配点的可能性大大增加,因此对静止或小运动块只需检测5个点即可获得运动矢量.而对大运动块的搜索点数明显比原DS少,提高了搜索速度.

2.分像素运动估计算法优化

分像素的运动搜索通常为:搜索最佳整像素点周围的8个1/2像素点,获得最佳半像素位置,如果还要进行1/4像素的搜索,则再搜索最佳1/2像素点周围的8个1/4像素点,获得最佳1/4点像素位置,即在上一级像素精度的最佳位置点对其内插后的相邻8点逐个进行块匹配运算,求出最小SAD值,得到最佳运动估计矢量.

分像素运动矢量与整像素运动矢量及整像素次优点有关,所以可利用整像素运动矢量和整像素次优点来预测分像素的大致方向,大大减少了计算量.检测设整像素运动预测的最优像素点是C点,C点周围有8个整像素点,计算这8个整像素点的SAD值,最小的那个点就是整像素次优点.在进行 1/4像素运动预测之前,需要整像素运动预测中求出整像素次优点的位置.当对最优整像素点C周围的8个整像素点进行搜索时,只需要记次优点位置即可,不需要专门进行计算.但是,根据实验表明[4],很多时候并没有必要进行1/2或1/4像素搜索,一般来说,1/2像素搜索比1/4像素重要.因此,设定两个门限值来判断是否进行1/2或1/4像素搜索.

1/4像素快速搜索算法分为三步:设定门限值,T1等于0,T2等于H×W(高×宽),第一步对SAD的值进行判断,如果SAD的值大于T1,继续第二步,否则不计算,第二步是根据整像素运动矢量方向和整像素次优点的位置确定1/2像素搜索方向,再求出1/2像素搜索的最优点和次优点位置,并判断块的SAD值,若大于T2,进行第三步,否则停止搜索,第三步是在第一步的1/2像素的最优点和次优点的基础上确定需要搜索的1/4像素位置,找出最优点.

如果必须进行 1/4像素搜索,首先要求出1/2像素搜索的最优1/2像素点和次优1/2像素点.根据计算出的3个1/2像素位置的SAD值再加上最优整像素点C的SAD值,从中求出最小的SAD值,对应的点即为最优1/2像素点.求次优1/2像素点要分两种情况考虑:一是最优1/2像素点是C点,那么次优1/2像素点就从上述的4个SAD值中求出,另一种情况是如果最优1/2像素点不是C点,那么考虑最优1/2像素点所对应的整像素点的SAD值.

如图2所示,检测设 1/2像素运动预测快速搜索算法所求出的最优1/2像素点为A,次优1/2像素点为B.图中“1、2、3、4、5、6、7、8”表示最优1/2像素点A周围的8个1/4像素点.从最优1/2像素点A和次优1/2像素点B的位置看,可以分为两种模式:一种是A和B处于同一水平线或垂直线上,这种模式所确定的1/4像素搜索点为A和B之间的3个1/4像素点,如图2(a)所示的3、5、8点,另一种是A和B处于对角位置,这一种模式所确定的1/4像素搜索点为A和B之间的3个1/4像素点,如图2(b)所示的2、3、5点.计算这个3个1/4像素点的F(p)值,并和最优1/2像素点A的F(A)值作比较,从中求出最优的1/4像素点,由这个点所确定的1/4像素运动矢量就是最优的1/4像素运动矢量.从以上可知1/4像素运动预测的快速搜索算法只需要搜索6-8个像素点,相对于1/4像素全搜索算法的16个像素点,效率可提高50%-62.5%.

3.结语

结合H.264视频编的视频图像的中心偏移特性对DS搜索算法进行了改进,改进后的综合搜索算法在降低编码时间和保证图像质量两个方面达到了较佳的平衡.对H.264的分数像素运动估计算法也进行了优化,降低了H.264在计算上的复杂度,提高了编解码的质量和速度,可适应实时视频通信、电视广播、视频流媒体和移动网络等各种业务的需求.