论文导读：运动估计是视频处理系统的一个重要的组成部分。下面是综合运用多个提升搜索速度的途径得到兼有各类快速算法优点的混合快速算法。
关键词：运动估计，快速搜索算法，混合快速算法
运动估计是视频处理系统的一个重要的组成部分，它是降低视频信号时间冗余的最基本和最重要的方法之一，运动矢量的准确性直接影响整个编码系统的，并对最终视频系统的质量和实时性有很大关系。因此需要综合考虑运动估计准确度和计算复杂度的关系，得到它们之间的折中点也成为了视频压缩编码领域的一个研究热点课题。
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)附近很小范围内。因此对于搜索起点的预测一般从中心位置开始。
1/2 1 2 下一页 尾页 |
