浅谈一种线性预测搜索方向的运动估计算法

摘要：为了减小快速运动估计算法的搜索速度和提高运动补偿的准确性，本文提出了一种线性预测搜索方向的快速运动估计算法。该算法在正方形模板块失真匹配的基础上，确定中心点到最小误差点为搜索方向，在此方向上不断延伸一个点进行块失真匹配，直至下一个点的块失真大于当前点的块失真。以当前点作为最小误差点，重复以上操作，直至找到最优点结束搜索。实验表明本算法在保证图像质量的情况下搜索速度比DS搜索算法提高1.5倍左右。

关键词：块匹配算法；运动估计；DS算法

中图分类号：TP312文献标识码：A文章编号：1009-3044(2007)03-10821-01

1 引言

在视频编码中，视频序列相邻帧中存在着很大的时间冗余，而运动估计和补偿技术可以有效地去除时间冗余，大幅度提高视频编码的效率。运动估计的综合性能直接决定视频图像编码方案的计算复杂度和编码效率。如何提高运动估计的效率，使运动估计算法的搜索过程更健壮、更快速、更高效一直是视频编码研究领域的一个热点。

运动估计算法多种多样，其中块匹配运动估计因其算法简单、便于VLSI实现等优点己被广泛应用。在块匹配运动估计算法中，全搜索（FS）算法精度最高，但是因为它要对搜索区域内的每个点进行检测，所以运算量太大，软硬件实现困难。后来人们相继提出了许多快速搜索算法，如三步法（TSS），四步法（FSS），二维对数法（TDL），基于块的梯度下降法（BBGDS），交叉法（CS），菱形法（DS）和MVFAST算法，它们通过不同的搜索模板和搜索策略，减少了搜索点数，在速度上比FS提高了许多，但性能比不上FS。

本文在对各种快速算法以及运动矢量的空间分布特性进行分析的基础上，设计了一种新的搜索算法――搜索方向自选择延伸的快速搜索算法。实验结果表明，此算法在相同条件下搜索点数大大少于DS算法，压缩比和峰值信噪比与FS算法几乎相差无几。

2 DS算法

菱形搜索（Diamond Search, DS）算法，最早由Shan Zhu和Kai-kuang Ma两人提出，后又经过多次改进，已成为目前快速块匹配算法中性能最优异的算法之一。1999年10月，菱形法被MPEG-4国际标准采纳并收入验证模型。

DS算法采用了两种搜索模板，分别是有9个检测点的大模板（Large Diamond Search Pattern, LDSP）和有5个检测点的小模板（Small Diamond Search Pattern, SDSP），如图1和图2所示。搜索时先用大模板计算，当最小块误差（Minimum Block Distortion, MBD）点出现在中心点处时，将大模板LDSP换成小模板SDSP，再进行匹配计算，这时5个点中的MBD点即为最优匹配点。

图1 小模板SDSP图2 大模板LDSP

DS算法的特点在于它分析了视频图像中运动矢量的基本规律，选用了大小两种形状的搜索模板LDSP和SDSP。先用LDSP搜索，可以进行粗定位，使搜索过程不会陷入局部最小；再用SDSP来精确定位，使搜索不至于有大的起伏，所以它的性能优于其它算法。但是，DS算法只是一种搜索策略的折中处理，对于大运动序列，DS算法在搜索最佳点所在区域时，广度搜索和梯度下降搜索同时进行，即同等的对待搜索区域的各部分，造成较大的搜索冗余，影响了算法的搜索速度；对于小运动序列中几乎保持静止的图像部分，DS算法也要经历由LDSP到SDSP的变化过程，要对13个搜索点进行搜索。由此可见，DS算法也需要改进。

3 搜索方向自选择延伸的快速搜索算法

3.1算法描述

根据运动矢量分布的中心偏移性，本文在搜索起始时，使用一个正方形模板，用于精确搜索；在做一次正方形模板搜索的后，对其MBD点方向上的点做进一步搜索，水平和垂直方向上的步长为1像素，对角线的步长为21/2像素；在对实际视频序列的运动特征的进行观察后可知：运动矢量（Motion Vector, MV）在水平和垂直方向的分布占运动方向分布概率的绝大多数。因而对于水平方向上搜索到的最佳点，仅对它上下的两个点再次进行搜索；对于垂直方向上搜索到的最佳点，仅对它左右的两个点再次进行搜索；对于对角线方向上搜索到的最佳点，仅对它和前一个点所在的小正方形的另外两个点进行搜索。图3给出了本文算法的搜索策略图。

(a)沿水平方向上的搜索策略 (b) 沿对角线方向上的搜索策略

图3 搜索方向自选择延伸算法的搜索策略图

3.2 算法的步骤

算法的具体步骤如下：(1)以搜索区原点作为正方形模板的中心点；(2)在模板的9个点处分别计算出对应的绝对差和（Sum of Absolute Difference, SAD），找出MBD点。若MBD点位于中心，则执行Step5；(3)计算MBD点所在方向上的下一个点（水平和垂直方向上是步长为1像素的点，对角线方向上是步长为21/2像素的点）的SAD。若此点的SAD小于MBD点的SAD，则将此点作为MBD点，继续执行Step3；若此点的SAD大于MBD点的SAD，则计算MBD点的上下两个点（水平方向）或是左右两个点（垂直方向）或是小正方形的另两个点（对角线方向）的SAD；(4)若这两个点的SAD都大于MBD点的SAD，则执行Step5，否则将SAD最小的点作为MBD点，继续执行Step3；(5)以该MBD点为最佳匹配点，得到运动矢量。

3.3 算法性能分析

这里通过一个具体例子来说明本文算法相对于DS算法在速度上的优越性。

(a) DS算法搜索路径 (b) 本文算法搜索路

图4显示了用DS算法和本文算法搜索到运动矢量[7,-2]的例子。图4(a)显示了DS算法的搜索路径，总共搜索了28个点；图4(b)是用本文算法搜索到同样点的路径，共搜索了20个点，本算法比DS算法少用了8个搜索点，这说明本文算法比DS算法的计算复杂度低。

4 实验结果和结论

为了验证本文算法的性能，在相同的条件下对FS、DS和本文算法在H.264/AVC参考模型T2641.0上进行了计算机仿真试验。本文试验采用了三个具有不同运动的视频序列各3帧，其中News序列的运动较小，Foreman序列的运动适中，而Mobile序列的运动则较为剧烈；量化参数（ ）选择24、48、34和40。编码时搜索范围为16像素，参考帧数为1。本文比较了搜索点数、编码压缩比和重建图像的峰值信噪比（PRSN），其中搜索点数是指搜索一个宏块运动矢量所需要的平均搜索点数。从表中可以看出，与DS算法相比本文方法明显地减少了计算量，同时又在不同程度上提高了编码质量，即编码质量接近于FS算法。尤其是对小运动News和大运动序列Mobile本文算法在速度上更快，在准确性上更高。由此可以看出本文算法在搜索准确性和速度上优于DS算法，是一种更高效的快速估计算法。

参考文献：

[1]丁贵广,郭宝龙.基于线性搜索的快速运动估计算法[J].西安交通大学学报,2004年2月,第38卷第2期.

[2]杨天武,彭强,诸昌岭.一种可伸缩的预测性快速运动向量搜索算法[J].西南交通大学学报.2005年2月,第40卷第1期.

[3]王晓燕,郑建宏.用于快速块匹配运动估计自适应十字模式搜索[J].电子与信息学报. 2005年1月,第27卷第1期.

[4]ISO/IEC JT C1/SC29/WG11 N3675,2000-10.Coding of moving pictures and audio[S].

[5]ISO/IEC JT C1/SC29/WG11 MPEG2000/m5865,2000-05.fast block matching motion estimation using advanced predictive diamond zonal search(APDZS)[S].

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。