一种新的H.264运动估计快速搜索算法

高颖敏,李玖玲

摘 要:综合分析各种运动估计搜索算法及算法的基本原理,在充分利用相邻像素块之间相关性的基础上,提出一种新的快速搜索算法,意在保持图像质量不变的情况下,降低运算复杂度,提高搜索效率。实验结果显示,该算法的运动估计时间是FS算法的25%~30%,UMHexagonS的50%~60%,可见不失为实时性较好的算法。

关键词:H.264;运动估计;快速搜索算法;UMHexagonS

中图分类号:TN91981文献标识码:A

文章编号:1004-373X(2009)19-125-03

A New Fast Searching Algorithm of Motion Estimation for H.264/AVC

GAO Yingmin,LI Jiuling

(School of Information Engineering,Zhengzhou University,Zhengzhou,450001,China)

Abstract:In this paper,a new fast searching algorithm is proposed on the basis of comprehensive analysis of variety of searching motion estimation algorithm and it′s basic principles.It makes full use of the correlation between the adjacent pixel block.The purpose is to reduce complexity and improve the efficiency of search with maintaining the same image quality.Experimental results show that the time consuming of this algorithm is 25%-30% of FS and 50%-60% of UMHexagons.

Keywords:H.264;motion estimation;fast searching algorithm;UMHexagonS

0 引 言

H.264是由ISO/IEC与ITU-T联合制定的新一代视频压缩编码标准[1],与以往标准相比,H.264在性能上有了很大提高。在相同重构图像质量下,H.264的预测精度达到1/4像素,与H.263和MPEG-4标准相比,能节约50%的码率。但其运算复杂度是H.263标准的4~5倍,其中先进的运动估计算法扮演着不可忽视的角色。无论在硬件实现,还是在软件编程的过程中,运动估计和补偿均占很重要的地位,而作为运动估计主要部分的搜索算法更为人门所重视。为了降低算法复杂度,提高算法实时性,人们研究出了多种快速算法,在很大程度上提高了算法的性效能。本文将介绍几种重要的搜索算法,结合这些算法[2-6],同时对H.264中快速搜索原理进行分析,给出了新的快速搜索算法。

1 H.264运动估计算法的特点

H.264标准中运动估计特点主要体现在三个方面:

(1) 高精度估计。采用1/4像素运动估计,运动补偿精度比H.263提高2倍,甚至4倍。由于其运动矢量的位移以1/4像素为基本单位,使得帧间剩余误差更小,传输码率更低,即压缩比更高;

(2) 多宏块划分模式。在H.264的预测模式中,一个宏块(MB)可划分成7种不同模式的尺寸,这种多模式的灵活、细微的宏块划分,更切合图像中实际运动物体的形状;

(3) 多参考帧。采用多个参考帧的运动估计,即在编码器的缓存中存有多个刚刚编码好的参考帧,并指出哪个帧被用于预测,这样就可获得比只用上一个刚编码好的帧作为预测帧更好的编码效果。

精确的运动估计可以大幅降低数据码率,但同时也导致了算法的复杂度增加,其复杂性主要集中在以下几个方面:

(1) 多尺寸帧间像块模式搜索。多尺寸像块划分模式使得帧间预测时像块的匹配更准确,从而提高PSNR和降低码率。但帧间像块模式的快速选择十分重要,增加了算法复杂性。

(2) 高精度运动搜索。运动矢量精度提高到1/4像素,增加了算法复杂性。

(3) 多参考帧预测。H.264在帧间预测时可以支持5个参考帧,通过多个参考帧进行运动搜索,可以获得更好的预测效果,研究表明其可节省14%的码率,但也增加了复杂性。

2 基于H.264的快速搜索算法分析

2.1 三步搜索法(Three Step Search,TSS)和新三步搜索法(NewTSS,NTSS)

三步搜索法[2]是由T.Koga等人提出的在搜索范围中限制搜索点的一种搜索算法。对于H.264全搜索法(FS)要完成搜索15×15=225个点的计算量,采用TSS搜索法计算25个搜索点即可完成。三步搜索法的数据读取比较规则,也易于硬件实现,所以被许多标准推荐使用。但由于算法第一步过于粗糙,在搜索范围较大(或更大)时,初始步长相对于块的运动矢量估计来说太大了,跳出了可能性比较大的区域,会导致搜索方向的不确定性,因此很容易陷入局部最优。于是Renxiang Li等人提出了新三步搜索法NTSS[3],其核心思想是采用具有中心偏置的搜索点模式,并应用中止门限判断来减少搜索次数。对于缓慢变化的序列NTSS,其平均信噪比明显高于TSS算法,而对于变化相对较快,特别是运动平均的序列NTSS,其优势就不明显了。如果把新三步法中心的小正方形分别换成十字形、菱形、六边形等,会在不同性能方面有所提高。

2.2 菱形搜索算法(Diamond Seacrh,DS)和六边形搜索(HEXBS)算法

Zhu和Ma在2000年提出了菱形搜索法[4],与过去提出的正方形搜索模式不同,DS算法第一次提出搜索应该是各向同性的,即应该选用圆形搜索模式。表现在离散化后的平面上,就变成了菱形的搜索模式。DS算法无论在性能,还是质量上都优于TSS算法。但对于运动大的序列,菱形法在搜索最佳点所在区域时,广度搜索和梯度下降同时进行,即同等地对待搜索区域的各部分,造成较大的搜索冗余,影响了算法的搜索速度。另外,对于保持静止的图像序列,即零运动矢量的情况,菱形法仍要对13个搜索点进行搜索,这是有待改进之处。

六边形搜索(HEXBS)算法[5]是将DS的LDSP改成六边形模式,SDSP仍然保留。实践证明,现实世界的视频块运动矢量有超过80%的概率落在以中心点为圆心,2为半径的圆内。由于大六边形模式相对于其他模式来说,更接近于以2为半径的圆,所以搜索效率更高。

2.3 非对称十字型多层次六边形格点搜索算法(UMHexagonS)

UMHexagonS算法[6]采用多种运动矢量预测及六边形搜索模式,能降低90%的整像素运动搜索复杂度,而PSNR的下降小于0.05 dB,是到目前为止效果最高的快速运动估计算法。UMHexagonS首先确定搜索起始点,在起始搜索矢量的集合中搜索一个对应费用函数值最小的候选运动矢量作为起始搜索点,然后判断是否提前截止。该算法搜索过程如图1所示。

图1 UMHexagonS的搜索过程

UMHS算法比DS算法可以取得更好的预测效果,但是UMHS算法因为步骤多,所以在搜索过程中增加了大量的搜索点,运算时间消耗较多。

3 新的快速搜索算法

本文将对文献[7]中的小菱形分层搜索算法做出改进,将其第四步的底层搜索换成UMHexagonS,具体步骤与其相同,下面给出详细介绍。

由于实际中绝大部分视频图像的运动都很小,如可视电话、视频会议中的视频图像序列运动矢量通常都高度集中在零矢量及其附近,这称为中心偏移性。对运动矢量为零的块在这里称其为静止块,运动矢量很小的块(运动矢量在以(0,0)为中心的5×5的区域内)称其为准静止块,其他的块称为运动块,那么有超过80%的块可被看作静止或准静止块。由此,可设一个阈值T0,当零矢量位置的块匹配的SAD值小于T0时,认为当前块为静止块,则停止搜索(一步停止法);再设一个阈值T1,当零矢量位置的块匹配SAD值大于T0而小于T1时,认为当前块为准静止块。在进行准静止块搜索时,由于运动矢量比较小,这里采用小菱形搜索模式。

在对运动块进行搜索时,一般分为粗略搜索和精确搜索两步,如DS搜索时先用菱形模式进行粗略搜索,然后再用小菱形模式进行精确定位;HEXBS搜索时先用大六边形模式进行粗略搜索,然后再用小六边形模式进行精确定位。另一种搜索方法就是运用多分辨塔方式进行搜索,将图像金字塔应用到运动估计是一项新技术,它充分利用了运动矢量场在空间和时间两个方向的相关性,在低分辨率的顶层中求出粗略的运动矢量,然后以此为基础,指导下一层的运动估计,逐渐缩小运动搜索范围。多分辨塔算法的分层不宜太多,在实际应用中一般取2~3层。对于本文的整像素运动估计算法,取2层多分辨塔,采用均值滤波采样算法,将原图像帧帧的像素值作为塔的底层,记为S0(x,y,k),(x,y)为平面点坐标,k为帧序号,顶层塔记为S1(x,y,k),则顶层的采样公式为:

S1(x,y,k)=14∑1m=0∑1n=0S0(2x+m,2y+n,k)(1)

这样第k帧就由两层塔分别构成底层{S0(x,y,k),0≤x≤N0-1,0≤y≤M0-1}和顶层{S1(x,y,k),0≤x≤(N0/2)-1,0≤y≤(M0/2)-1},如图2所示。在进行运动搜索的时候,先在顶层进行搜索,结果传递给下层再进行搜索,每一层的搜索方式都采用小菱形搜索模式。由于底层4个点只能抽样为顶的一个点,即底层16×l6的宏块相当于顶层8×8的块,所以在进行运动搜索时,顶层搜索块应相当于底层块的1/4大小,如在顶层进行8×8的块搜索,而在底层进行16×16的宏块搜索,也即是说,中层搜索一个点计算量仅相当于底层一个点计算量的1/4。

图2 两层多分辨塔

算法具体步骤如下:

第一步:计算(0,0)位置的SAD值,判断SAD值是否小于T0,如果小于,则判定当前块为静止块,停止搜索,输出MV为(0,0),否则进行下一步;

第二步:判断SAD值是否小于T1,如果小于,则判定当前块为准静止块,跳到第四步,否则进行第三步;

第三步:进行分层搜索的顶层搜索。首先确定搜索起始位置,如图3所示。选取V1,V2,V3,再加上V4=(0,0)为候选起始运动矢量,其中V1为当前块左边块的运动矢量,V2为当前块上方块的运动矢量,V3为当前块右上方块的运动矢量,V4为(0,0)矢量。计算这四个位置的SAD值,选取最优点为运动搜索的起始点,然后以起始点为中心,进行小菱形搜索,结束后转下一步;

第四步:进行底层搜索,如果是由第二步跳转来的,则以(0,0)为中心进行UMHexagonS搜素;如果由第三步转来的,则以顶层所得的运动矢量乘以2为初始运动矢量进行小菱形搜索,结束后输出MV。

图3 候选起始运动矢量

4 实验结果

以JVT的JM86为测试平台,对图像格式为QCIF的三种典型的标准图像序列“Akiyo”(运动缓慢)、“Foreman”(中等运动)、“Carphone”(运动剧烈)的前100帧进行测试,实验室选用3个参考帧,帧速为30 f/s,搜索范围为16,编码序列为IPPP格式,量化系数为28,采用Hadamard变换和CABAC熵编码,试验测试结果如表1所示。从表中可以看出,改进算法的SPNR与FS算法相比略有下降,但改进算法的运动估计时间是FS算法的25%~30%,UMHexagonS的50%~60%,可见实时性得到明显提高。

表1 搜索算法的性能比较

算法Akiyo序列Foreman序列Carphone序列

YPSNR

/dBUPSNR

/dBVPSNR

/dBtME /sYPSNR

/dBUPSNR

/dBVPSNR

/dBtME /sYPSNR

/dBUPSNR

/dBVPSNR

/dBtME /s

FS37.3739.5440.6245736.0239.1340.7247036.1237.2040.63468

UMHexagonS37.3539.5240.5920535.8938.6740.5223435.6935.8940.03221

改进算法36.3639.5340.7212136.0139.0240.6913535.9436.9240.52118

5 结 语

运动估计是视频编码器中计算量最大的一个模块,由于能够有效地减少帧间相关性,被广泛用于各种视频编码标准中。本文对快速运动估计算法原理进行了分析,并详细介绍了几种目前比较重要的整像素搜索算法,在此基础上结合H.264标准要求,提出了用于H.264标准的快速算法改进思路和改进算法。本文创新点:充分利用相邻块之间的相关性,结合不同视频序列的特点设计了混合式分层搜索算法。

参考文献

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

[2]Babu D V,An P S R,Karthikeyan C.Performance Analysis of Block Matching Algorithms for Highly Scalable Video Compre-ssion[J].IEEE,2006:179-182.

[3]Shan Zhu,Kai Kuang Ma.A New Diamond Search Algorithm for Fast Block Matching Motion Estimation[J].IEEE Trans.on Image Processing,2000,9(2):287-290.

[4]Ce Zhu,Xiao Lin,Lap Pui Chau.Hexagon-based Search Pattern for Fast Block Motion Estimation[J].IEEE Trans.on Circuits and Systems for Video Technology,2002,12(5):349-355.

[5]周巍,史浩山,周欣.基于H.264的快速运动估计算法[J].计算机工程与设计,2007,28(2):379-381,385.

[6]Li Renxiang,Zeng Bing,Liu Ming L.A New Three-step Search Algorithm for Block Motion Estimation[J].IEEE Trans.on Circuit and Systems for Video Technology,1994,4(4):438-442.

[7]乔轩.H.26X系列的算法研究[D].杭州:浙江大学,2005.

[8]张淑芳,李华,刘晓青,等.基于H.264的复杂度-失真最有的运动估计算法[J].计算机工程,2007,33(9):228-230,234.

[9]陈传东,陈新.H.264中二进制算术编码的硬件实现[J].现代电子技术,2007,30(22):48-50.