论文导读：运动估计是视频处理系统的一个重要的组成部分。下面是综合运用多个提升搜索速度的途径得到兼有各类快速算法优点的混合快速算法。

　　关键词：运动估计，快速搜索算法，混合快速算法

　　运动估计是视频处理系统的一个重要的组成部分，它是降低视频信号时间冗余的最基本和最重要的方法之一，运动矢量的准确性直接影响整个编码系统的，并对最终视频系统的质量和实时性有很大关系。因此需要综合考虑运动估计准确度和计算复杂度的关系，得到它们之间的折中点也成为了视频压缩编码领域的一个研究热点课题。

　　1 运动估计原理

　　运动估计的基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并假设宏块内所有的像素的位移量都相同，然后对于当前帧中的每一块在前一帧或后一帧的某一给定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块。由匹配块与当前块的相对位置计算出运动位移，所得的运动位移即为当前块的运动矢量（Motion Vector）。利用搜索到的运动矢量在参考帧上进行运动补偿，补偿残差经过DCT变化、量化、行程编码后与运动矢量共同经熵编码，然后以比特流形式传出去。快匹配法是现在最基本的运动估计法。

　　2 典型估计算法及优缺点

　　下面介绍一下常见的典型的快匹配算法。

　　全搜索算法FS（Full Search）[1] 是按一定的顺序计算出搜索窗口（以当前宏块位置（0,0）为中心的±S个像素的搜索范围）内每一个点的求和绝对误差值SAD（Sum of Absolute Difference），找出SAD最小的点所在的位置的算法。

　　FS 算法简单、可靠，搜索效果好，且能够得到全局最优的结果，通常是其他算法性能比较的标准，但它计算量相当大，也是最耗时，这就限制了在需要实时压缩场合的应用，所以有必要进一步研究改进算法。

　　三步搜索法TSS（Three Step Search）[2] 总共进行三步搜索，它基本上保持了FS的性能，逐步减小搜索步长。每次搜索都是以上一步的搜索结果为中心，搜索步长为上一步步长的一半，搜索精度为1个像素。

　　TSS算法是一种由粗到精的搜索算法，快速而且高效，其计算量只有FS的10%左右，是块匹配运动估计的一种典型的快速算法，但这种搜索不能保证整体最小点，只能求得局部的SAD 最小点。较适合对小运动的估计性能。

　　二维对数搜索法TDLS（Two-Dimension Logarithmic Search）是第一个利用象限划分搜索区域的快速匹配算法。算法的中心思想是，由每一步搜索的结果，确定下一步的搜索所在的象限范围，并动态地变化搜索的步长，最终找到相应的最佳匹配位置。

　　TDLS的性能比TSS略差一点，但速度快了许多。由于该算法的前提是假设搜索区内只有一个谷点，搜索过程中可能进入其中一个非最佳匹配的谷点而误认为其是最佳匹配点，就停止搜索，陷入局部最小点。

　　共轭方向搜索法CDS （Conjugate Directiona1 Search）[3]，它是先在一个方向（设为X轴方向）进行搜索，固定Y轴方向对横向的所有点进行逐一匹配，按SAD最小的原则得到一个点；然后保持X不变，在Y轴方向搜索所有点，得到最佳匹配点。

　　这种算法简单，实现容易。但由于只对两个方向进行了搜索得到的匹配点可能与真正的最佳匹配点有差距，其性能略低于TSS，运算时间也略长于TSS。

　　四步搜索法FSS （Four Step Search） 是对新三步搜索法NTSS（New Three Step Search）的改进，算法的中心思想是，每一步的搜索范围由上一步的最佳匹配位置决定，前三步的搜索是定步长搜索，最后一步改变步长，得到最后的最佳匹配位置。

　　这种算法依赖最佳匹配像素点的唯一性及其周围的单调性，计算复杂度低，可以明显减少匹配的计算量，性能比TSS算法更好，与NTSS算法相似。

　　菱形搜索算法DS（Diamond Search）采用的大菱形搜索模板LDSP和小菱形搜索模板SDSP。在进行搜索时，先用大菱形模板进行搜索，如果最佳匹配点不是大菱形的中心点，则以当前最佳匹配点为中心继续进行大菱形模板搜索，直至最佳匹配点为当前大菱形的中心点为止，转为小菱形搜索。

　　DS是一个优秀的算法，是依据一般物体在水平方向和垂直方向上运动的概率比较大的特性设计模板，能在较大的范围内能维持较快的搜索速度和较高的搜索精度。但对于实际运动矢量较大（全局最小值偏离搜索区中心）而块匹配误差平面在近中心区域存在局部最小值的块，该算法不能求出正确的运动矢量，而且偏离正确运动矢量的位移较大。

　　3 改进方法

　　前面介绍了各种典型算法，这些算法都有各自的优缺点，但如果我们能取长补短，再结合视频图象本身的一些特性，就能有新的，较实用的算法的出现。

　　3.1 图象特性

　　图象的基于中心倾向分布特性指一般物体在水平和垂直方向上运动的概率比较大。在各向同性分布搜索法中，可以在搜索开始时，对水平和垂直方向上进行菱形的粗搜索。对于典型的匹配模型根据中心倾向特性加强在水平和垂直方向的搜索后形成偏水平十字模型，偏垂直十字模型，偏向钻石模型等。

　　图象的运动相关性指在实际中的视频图像大部分块是静止或准静止的，运动矢量的分布以（0,0）为中心向外发散，越往外概率越小，即运动矢量主要集中在搜索中心（0,0）附近很小范围内。因此对于搜索起点的预测一般从中心位置开始。

　　连续排除算法SEA（Successive elimination algorithm）[7]的基本思想是应用三角不等式，用块的和范数差值SND（sumnorm difference）先进行判断，排除 SAD 不可能最小的搜索位置，避免计算运算复杂度很高的块匹配误差，不断更新目前最佳匹配位置，连续不断地排除不可能的位置，加快搜索速度。它在不损失任何性能的基础上，有效加快搜索速度， 16×16 宏块运动估计中 SEA 算法实际计算了大约 6%～10%的块的 SAD 值，约可提高速度10 倍左右。

　　早停止技术，主要思想可归纳为“找到足够好的匹配，而并非一定要最好的匹配”。一般的做法是预先设定一个闽值。当匹配误差小于这个闽值时，立即停止搜索过程。由于不需要完成整个搜索，因此可以达到加速的目的。

　　3.2 混合快速算法

　　下面是综合运用多个提升搜索速度的途径得到兼有各类快速算法优点的混合快速算法。

　　在十字模型中如果考虑到图象的中心倾向特性形成双十字搜索算法[5]。该算法在搜索的初始阶段使用小十字搜索模型SCSP和大十字搜索模型LCSP对小运动矢量进行搜索；而在后继的搜索步骤中，充分考虑大运动矢量概率分布的方向性，对大运动矢量进行搜索，从而加快了运动矢量的搜索速度。该算法不仅保持与其他快速块匹配运动估计算法相当的搜索质量，而且可提高大约40%的搜索速度。

　　将连续排除算法SEA和菱形搜索法结合起来形成连续消除菱形运动估计算法SEDS[6]，再结合准确的运动矢量初始位置选择、提前终止判断、有效的菱形搜索模式等方法，从而大幅度降低运动估计运算量，同时保持编码性能，块匹配误差计算量为快速全搜索算法的 0.2%~1%。或者也可将SEA和六边形和小菱形搜索法结合在一起形成连续排除六边形算法[7]将SEA和全搜索法结合在一起形成连续排除全搜索法。SEA和各类算法结合都有提高速度，减少时间的作用。与SEA有类似作用的还有亚像素估计法，子抽样法等。

　　基于运动矢量的统计分布特性的双起点大小正方形算法DBSS （Double Big Small Square），算法的其中一个策略是采用预测点和当前分块所在位置两点作为搜索起点，使得在出现相关性预测误差大时，仍能把握运动的方向；另外就是采用大小正方形的搜索模式，模板如图1所示，内部是一个小的正方形，外部是一个大的正方形。

　　DBSS算法主要步骤：

　　（1）当MBD（Minimun Block Distortion）出现在大的正方形四个顶点，表明物体运动幅度很大，则仍选用原有的搜索模式；

　　（2）当MBD出现在小的正方形的四个顶点，表明物体运动幅度很小，则以MBD的正方形顶点为中心，采用小钻石搜索方式进行搜索。

　　（3）当MBD出现在大小正方形的中心，说明图像没有运动，结束搜索。

　　从BSS的搜索方式中我们可以看出BSS算法不必一定经历从较大搜索步长到小搜索步长的变换，而是根据物体运动情况来确定搜索步长。从直观上可看出，大小正方形分别用来粗细定位，这本质上体现了一种并行处理的思想。

　　图1 DBSS算法的搜索模板

　　Fig 1 The search pattern of DBSS algorithm

　　实验结果表明，采用DBSS算法的峰值信噪比十分接近FS算法，而优于DS算法； DBSS算法的比特率略高于FS算法，但明显低于DS算法； DS算法的编码时间大概是FS全搜索的1 /25，而DBSS算法大概是采用FS全搜索的1/30，也就是说DBSS算法大大提高了编码速度，比DS算法更有效节约了运算时间。也就是说，DBSS算法取得了运算复杂度和搜索精度之间的折中，在保证视频性能相对高的前提下，大大降低了运算复杂度，提高了编码速度。

　　4 结论

　　混合快速算法结合了各类典型算法的优点，在速度与准确度两方面做出折中，使能够满足视频传输的需要，近年来已被多个视频压缩标准采纳。

　　参考文献

　　[1]A.M.Tekalp,"DigitalVideo Processing",Englewood Clifs:Printice Hall,1995.

　　[2]王建。H.264 中运动估计的研究与实现。[硕士毕业论文],江苏：南京邮电学院，2005.

　　[3]刘根林。H.264 实时视频编码技术研究及其 DSP 实现。[硕士毕业论文],上海：上海交通大学，2004.

　　[4] Li W, Salari E.Successive Elimination Algorithm for Motion Estimation[J]. IEEE Trans. on ImageProcessing, 1995, 4（1）：105-107.

　　[5]刘海华，雷 奕，谢长生。双十字搜索算法的快速块匹配运动估计。计算机研究与发展，43（9）：1666~1673,2006.

　　[6]杨铭。H.264 视频编码快速算法与算术编码检错研究。[硕士毕业论文],北京：清华大学，2004.

　　[7]黄 帅，宋国新。基于连续消除的六边形自适应搜索算法。计 算 机 工 程，2006 年 11 月，Vol.32 No.21.