摘  要： 提出了一种基于H.264/AVC的快速运动算法。根据运动矢量的时空相关性建立一个预测运动矢量集合，再采用小交叉（SCSA）模板和大六边形（LHSP）搜索进行搜索。在搜索过程中采用提前终止技术，进一步减少计算量。实验结果和分析表明，该算法能够显著提高运动估计的搜索速度，节省了大量运动估计时间，而图像质量和比特率只有少量变化。 

    关键词: H.264/AVC； 运动矢量； 提前终止； 运动估计

    H．264/AVC 视频编码标准是ISO／IEC MPEG联合ITU-T VCEG成立的联合视频组JVT(Joint Video Team)制定的视频编码新标准。该标准在2003年正式成为国际标准，同时它也成为了MPEG-4的第10部分，称为AVC(Advanced Video Coding)。H.264标准的运动估计采用了可变长宏块和多参考帧等新的编码模式，使运动估计的精度更高，同时也使编码更加复杂且计算量更大。 

    在H.264编码中，运动估计和运动补偿占用了70％以上的编码时间。因此在进行H.264优化时，先要考虑的问题就是在保证视频质量不显著下降的情况下，采用高效快速的运动估计算法，尽量提高运动估计的搜索速度，减少编码的复杂度。 

1 运动矢量预测及阀值确定 

    实际中绝大部分视频图像的运动都很小。统计学的结论表明，在视频会议、视频电话中的视频图像序列，运动矢量通常都高度集中在零矢量及其附近，称为中心偏移性，即大部分运动矢量为零矢量或运动很小的矢量。对运动矢量为零的块在这里称其为静止块；运动矢量很小的块（以搜索窗口中心为圆心，两像素为半径的圆内）称其为准静止块；而其他的块称为运动块。如果有超过80%运动矢量很小的块可被看作静止或准静止块。 

    因此，可设一个阀值T，当运动矢量的值小于T时，认为当前块为静止块或者准静止块，可用小交叉型搜索法直接进行精确定位，找出最优点；当运动矢量的值大于T时，认为是运动块，可用大六边形搜索算法找出最优点。 

    由于一个运动物体会覆盖多个分块，所以空间域相邻块的运动矢量具有很强的相关性。同时由于运动物体运动具有连续性，运动矢量在时间域也存在一定的相关性，因此可以用邻近参考帧的运动矢量来预测。运动矢量空间域的预测方式有运动矢量中值预测（Median Prediction）、空间域的上层块模式运动矢量（Uplayer Prediction）两种^[2]。运动矢量在时间域的预测方式有前帧对应块运动矢量预测和时间域的邻近参考帧运动矢量预测两种。 

    为了便于寻找匹配块的运动矢量，减少计算复杂度，本文采用运动矢量中值预测方式。根据与当前块E相邻的左边块A，上边块B和右上边块C的运动矢量，取其中值作为当前块的预测运动矢量。把预测运动矢量作为运动估计的初始搜索位置。 

　　图1和图2中，设E为当前要编码的块，E的运动矢量为MVp。如果运动矢量的值MVp≤T，则认为与E块相邻的各块(子块)间运动的相关性较高，表明该区域的变化比较平缓。如果运动矢量的值MVp>T，则认为与E块相邻的各块间运动的相关性较低，表明该区域变化比较剧烈。 

    通过对foreman、football、bridge、highway等序列的多次测试，可取阀值T=2作为衡量当前块是静止块、准静止块还是运动块的判断及搜索算法选择的依据。 

2 搜索策略描述 

    根据预测的运动矢量和相邻块间的运动相关性的不同(阀值T的不同)，采用两个不同的模板，分别为小交叉^[3]搜索模板SCSA(Small Cross Search Algorithm）和大六边形^[4]搜索模板LHSP(Large Hexagon Search Pattern),如图3所示。SCSA搜索模板以起始搜索点为中心，并由4个周围点组成，如果计算的最小值点为中心点，则停止搜索，中心点即为最终的运动矢量。如果最小值点在边缘上，则以该最小值点为中心，和其相邻的4个周围点进行下一次的搜索计算，直到最小值点为中心点。同时，由于H.264采用的是多种块划分的模式，可以根据块的不同形状和大小采用不同的步长。其搜索步骤如下： 

    (1) 设定当前块的预测运动矢量和起始搜索点，并判断相邻块间的相关性。 

    (2) 如果相邻块间的运动相关性较高，预测的运动矢量值较小或为零，则转入(5)；否则，进入(3)。 

    (3)利用LHSP模板进行搜索，计算7个点的SAD值，同时利用排除准则进行条件判断。如果最小值MBD为中心点，则转到(4)，否则重复(3)。 

    (4) 以中心点周围的上、下、左、右4个点组成1个小的菱形，计算5个点的SAD值，同时利用排除准则进行条件判断。SAD值最小的点即为最终的运动矢量。 

    (5)利用SCSA模板进行搜索，计算5个点的SAD值，重复点将不再计算，同时利用排除准则进行条件判断。如果最小值MBD为中心点，该点对应的运动矢量即为最终的运动矢量；如果最小值点为边缘点，重复(5)。 

    根据前面的分析方法和搜索步骤，可以得出此搜索算法的搜索框图，如图4所示。  

    改进后的算法大大减少了对于那些运动矢量为零的块的搜索冗余，同时对于运动比较缓慢的块直接进入小范围搜索。这样既提高了搜索效率，又不会使搜索结果只找到局部最优点。由于采用了中止判别技术，因此可大大降低搜索的复杂度，提高了搜索的效率，降低了搜索的成本。 

3 系统仿真与结果分析 

    利用本文提出的算法，使用JM86进行仿真实验^[5]，分别在搜索点数、峰值信噪比(YUV分量)、比特率等几个方面与FS、DS进行对比。仿真实验中采用大运动序列football。 

    由于在量化和反量化过程中，量化参数QP决定了量化器的编码压缩率及图像精度。如果QP比较大，则量化值FQ的动态范围较小，其相应的编码长度也较小，但反量化时损失较多的图像细节信息;如果QP比较小，则FQ的动态范围较大，相应的编码长度也较大，但图像细节信息损失较少。H.264中，量化步长Qstep共有52个值，在仿真实验中，取QP=5、QP=11(量化参数每增加6，则量化步长增加一倍)、QP=29进行同一序列取不同的QP值(为减少仿真实验的计算量，测试序列只取前90帧),其结果分别如表1、表2、表3所示。 

    通过分析可以得到，本文所提出的算法与FS及DS算法相比，PSNR值基本保持不变。可以得出如下结论: 

    (1)在搜索点数上大大优于FS算法，只有FS算法的1.33%，比DS算法也有很大的改进,是DS算法的75.75%。 

    (2)对视频图像的PSNR值影响甚微，而对搜索效率有很大的提高。 

    (3)对视频图像的压缩比相对DS算法差别很小，FS算法的压缩比最高。 

    (4)不同的QP值对搜索点数影响不大，但是对视频图像的数据率和PSNR值却影响很大，QP越大，PSNR越小，同时数据率也越小。 

    因此，本文使用优化的搜索算法，PSNR值基本不变，但大大减少了搜索时间，提高了搜索效率，这对于视频图像的实时传输是很有意义的。 

参考文献 

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

[2] KURCEREN R, KARCZEWICZ M. Synchronization predictive coding for video compression. The SP Frames Design for JVT/H.26L.Proc,ICIP.2002. 

[3] GHANBARI M. The cross-search algorithm for motion estimation [J]. IEEE TransCommunication.1990, 38(7):950-953. 

[4] ZHU S， MA K K.A new big hexagon search algorithm for fast block matching motion estimation [J].IEEE Trans-Image Processing，2000,9(2):287-290. 

[5] 丁贵广.Visual C++6.0数字图像编码.北京：机械工业出版社，2004.