摘要：运动估计是根据视频序列中时间上相关的信息估计场景或目标的二维运动向量场的过程，块运动估计是目前使用最广泛的运动估计方法。本文设计了一种基于空间预测的块运动估计的快速算法，通过空间预测得到运动向量的初始估计。若当前块和相邻块的运动相关，则用相邻块的运动向量预测估计当前块的运动向量，再以该预测值为中心，比较小菱形上的搜索点；否则，用CDS算法从搜索窗口的原点开始搜索运动向量。实验结果表明，本文设计的算法兼顾了搜索速率和精度，其性能优于现有的SEA、N3SS、DS、HEXBS、CDS、CDHS算法。
    关键词：运动估计、运动向量、块匹配算、法空间预测
    1、引言
    运动估计是根据视频序列中时间上相关的信息估计场景或目标的二维运动向量场的过程，主要分为两类：基于参数模型的运动估计和非参数的运动估计。若场景的运动由摄像机的平移、旋转、倾斜或缩放运动引起，则采用基于参数模型的运动估计，如基于光流的方法。基于参数模型的运动估计的主要缺点是只能应用于全局刚性运动。当场景中存在独立的运动物体时，则采用非参数的运动估计，如基于块的方法、像素递归方法和最大后验概率估计方法。因为块运动估计的简单性和有效性，它已经成为目前使用最广泛的运动估计方法。
    块运动估计的基本思想是将当前帧划分为图像块，对于当前帧中的每一个图像块，在参考帧的搜索窗口内搜索最佳匹配块，参考帧中的最佳匹配块相对于当前帧图像块的位移称之为当前帧图像块的运动向量。通常采用平均绝对值差（MAD, mean absolute difference）准则衡量最佳匹配块。设当前帧中块的大小为 ，左上角的坐标为 ，运动向量为u和v、i和g分别为当前帧和参考帧在像素 处的灰度值。MAD的定义为
    到目前为止，研究工作者们提出了很多块运动估计的快速算法（也称快速块匹配算法），和全搜索相比，它们在搜索速率上有很大的提高，然而在搜索的准确度上仅有微小的下降。现有的快速块匹配算法大致可分为如下四类：
    A. 采用固定搜索模式集的快速块匹配算法
    这类算法是基于全局误差场单调分布的假设：随着搜索位置移向全局极小点，匹配误差值单调递减。误差曲面的特性直接影响块匹配算法的性能。对于搜索窗口内有且仅有一个全局极小点的单峰误差曲面（如图1(a)所示），经过搜索少量的像素就可

(a) 误差曲面仅有一个局部极小点

(b) 误差曲面有多个局部极小点
图1  两个块的MAD误差曲面

    以到达全局极小点。但对于有多个局部极小点的误差曲面（如图1(b)所示），不一定收敛到全局极小点，搜索很容易陷入某个局部极小点。这类算法使用固定搜索模式集搜索运动向量，且每个块的运动向量的搜索彼此独立。众所周知的搜索算法有二维对数搜索（2DLOG, 2-D logarithmic search）[1]、三步搜索（3SS, three step search）[2]、叉形搜索（CS, cross search）[3]、新三步搜索（N3SS, new three step search）[4]、四步搜索（4SS, four step search）[5]、梯度下降搜索（BBGDS, gradient descent search）[6]、菱形搜索（DS, diamond search）[7][8]、六边形搜索（HEXBS, hexagon-based search）[9]、十字形菱形搜索（CDS, cross-diamond search）[10]、有效三步搜索（E3SS, efficient three step search）[11]和十字形菱形六边形搜索（CDHS, cross-diamond-hexagonal search）[12]。其中，DS算法被MPEG-4VM采纳。
    B. 基于块间相关的快速块匹配算法
    这类方法利用和当前块在空间上和（或）时间上相关的邻近块的运动向量预测当前块的运动向量。通过计算这些邻近块运动向量的统计特征（如均值、中间值，加权平均值等）[13][14]或者根据某准则选择其中一个邻近块的运动向量（如选择使当前块匹配误差最小的运动向量）[15]作为当前块运动向量的预测值。获得预测值后，以预测向量为中心执行缩小的全搜索算法。
    C. 分级快速块匹配算法
    在分级方法[16][17]中，不同级图像的分辨率不同，块的大小不变。通过对图像下采样，降低图像的分辨率，级越低，图像的分辨率越低。这类方法用低一级所得运动向量作为高一级运动估计的初值，通过由粗到细的过程，得到原图像的每个块的运动向量。
    D. 减少计算匹配误差像素数的快速块匹配算法
    这类方法通过减少参与块匹配误差计算的像素数来加速运动估计。一种方法是在每一个块中分别沿水平和垂直方向按2：1的比率下采样，这样，计算量将降低为原来的1/4。这类方法可以和其他类的块运动匹配算法结合达到更高的搜索速率。
    2  基于空间预测的快速块匹配算法
    2.1  算法原理
 如前所述， A类算法的搜索很容易陷入某个局部极小点。但是，局域内误差场单调分布的假设是成立的。如果运动向量的初始估计在全局极小点的邻域内，再用A类算法搜索，那么经过搜索少量的像素就可以到达全局极小点。对于一个图像序列，运动目标往往覆盖许多图像块，空间上相邻块的运动是高度相关的。为此，本文设计了一种基于空间预测的快速块匹配算法，首先通过空间预测得到运动向量的初始估计，期望得到的运动向量初值在误差曲面全局极小点的邻域内。
本文将多种快速块匹配算法进行了总结比较，六边形的搜索速率高于菱形，但搜索精度过低。对于静止或近似静止块较多的视频序列，提前终止搜索技术不仅可以提高搜索速率，而且可以提高搜索的准确率。为了兼顾搜索速率和精度，当当前块和相邻块的运动不相关时，则用CDS算法（搜索过程见文献[10]）从搜索窗口的原点开始搜索运动向量。
    本文算法的搜索过程如下：从左到右，从上到下依次扫描当前帧中的每个图像块。左上角的块是扫描到的第一个块，没有可作预测的相邻块，故用全搜索算法比较搜索窗口内所有位置的块匹配误差，最小块匹配误差（MBD, minimum block distortion）点相对于原点的位移即为要求的运动向量。对于第一行、第一列和最后一列的块，没有足够的相邻块用来预测当前块的运动向量，且这些块的运动向量的准确性又直接影响其他块搜索的准确性，故用修改的SEA算法（见2.2节）。对于其他块，本文选择当前块左边、上边、右上方相邻块的运动向量和 作为空间预测集中的元素，并分别计算它们指向的块和当前块之间的块匹配误差。忽略左上方相邻块的原因是它和左边、上边的相邻块高度相关，它能被这两个块或其中的一个所代替。若运动向量为 对应的块匹配误差最小，表明当前块和相邻块的运动不相似（例如场景中存在独立的运动物体），则用CDS算法从原点开始搜索运动向量；否则，从相邻块的运动向量中选择使当前块的匹配误差最小的作为当前块运动向量的预测估计，再以该预测值为中心，比较小菱形（见图2）上5个点的块匹配误差，若周围的4个点之一是MBD点，则以该MBD点为中心形成新的小菱形，如此继续，直到小菱形的中心是MBD点或搜索点到达搜索窗口边界，每次仅需再计算3个或2个点的块匹配误差。实验表明，用小菱形代替3×3的方形（见图3），搜索点数明显减少，而搜索精度的降低却是可以忽略的。

    2.2 修改的SEA算法
    SEA算法[18]是一种快速全搜索算法，SEA算法和全搜索算法得到的运动估计结果相同，它能够搜索到全局极小点，但它的计算量有较大程度地减小
    2.2.1 SEA算法原理
    SEA算法通过一个有上下界约束的不等式限制了搜索空间。设块的大小是 ，允许搜索的最大步长是 ， 和 分别表示当前帧和参考帧中像素 处的灰度值，MAD准则用于计算块匹配误差，得到不等式（2）如下：
 （2）
其中，u, v表示运动向量的两个分量-w≤u v≤ w表示当前块的所有像素灰度值之和u，v表示运动向量 对应的参考帧中匹配块的所有像素灰度值之和。 为初始值，表示初始预测估计的运动向量对应的MAD。
    SEA算法仅需计算参考帧中搜索窗口内满足不等式（2）的搜索位置的块匹配误差，显然，满足不等式（2）的搜索点数比搜索窗口内总的搜索点数少，因此，算法较大程度地降低了计算量。根据不等式（2），SEA算法的效率依赖于参考帧中匹配块的像素灰度值和的快速计算以及初始的运动估计。
从不等式（2）中可以看到，若界的范围大，或搜索窗口内搜索点对应的块内像素灰度值之和彼此相近，都会增加搜索位置的个数。场景改变大或初始估计不准确会导致不等式（2）界的范围较大，而图像平滑部分的搜索点对应的块内像素灰度值之和彼此相近。
    2.2.1 参考帧中匹配块像素灰度值和的快速计算
    如果当判断搜索窗口内的搜索点是否满足不等式（2）时，再累加该搜索点对应的块内像素灰度值，那么计算量相当大。因此，必须提前计算参考帧中的每个搜索点对应的块内像素灰度值之和。这一节讨论参考帧中匹配块内像素灰度值和的快速计算。设图像的大小是H*W，在像素（i，j）处的灰度值用f（i，j）表示。如图4所示，将参考帧划分为H-N+1条窄带，每一条窄带包含N行像素。

图4 匹配块内像素灰度值和的快速计算示意图

    第一步：计算第一条窄带每一列像素灰度值之和，记为。第二条窄带每一列像素灰度值之和记为，显然,
… , 。同理计算得到其余窄带每一列的像素灰度值之和。C矩阵的大小为(H-N+1)*W。
    第二步：第一条窄带第一个块的像素灰度值之和记为SN11，则。沿水平方向向右平移1个像素，得到第二个块的像素灰度值之和，记为SN11，则，依此类推，可以得到 。同理计算得到其余窄带的每一个块的像素灰度值之和。 矩阵的大小为 (H-N+1)*(W-N+1)。
    本文设计的算法仅需对当前帧中第一行、第一列和最后一列各块对应的搜索窗口内的每一个匹配块的像素灰度值求和，因此只需计算如图5所示的阴影部分的 和 的值，而不用计算整个C和SN矩阵的值。

图5C和SN矩阵中的阴影区域

    2.2.1 初始MV的估计
    根据不等式（2），初值MAD越小，搜索空间越小。用相邻块的运动向量近似估计当前块的运动向量，当前帧第一行各块的预测集的元素选择左边相邻块的运动向量和（0，0），第一列各块的预测集的元素选择上边相邻块的运动向量和，最后一列各块的预测集的元素选择左边、上边相邻块的运动向量和 。预测集中使当前块匹配误差最小的运动向量即为初始的运动估计，从而得到要求的初值 。
初值 在搜索过程中并不是恒不变的，如果搜索位置 对应的小于，那么用代替不等式（2）中的值，这样进一步减少了搜索位置。
    2 性能评价
    评价块运动估计的快速算法通常有4个准则：①平均每个像素的误差平方和（MSE）；②每个块的平均搜索点数（Search Points）；③采用快速算法搜索得到的运动向量和全搜索算法搜索得到的最优运动向量相等的块个数占总数的比例（Avg. Prob）；④采用快速算法搜索得到的运动向量和全搜索算法搜索得到的最优运动向量之间的平均距离（Avg. Dist）。
    根据上述的4个准则，本文在Mobile、Tennis、Garden和Surfside等测试序列上将SEA、N3SS、DS、HEXBS、CDS、CDHS算法和本文设计的算法做比较。块的大小选择 ，用MAD准则计算块匹配误差，搜索窗口为原始图像块起始位置的 像素范围内。Mobile序列中，整个场景向右移动，场景中存在多个目标，墙上的日历向上平移，玩具火车向左近似作平移运动，火车推动前面的小球作旋转运动。Tennis序列中，球拍托球，使球上下运动，背景是静止的。Garden序列中，整个场景向右运动，运动程度较大。Surfside序列中，背景是汹涌澎湃的大海，前景中的三个人都向前缓慢移动，运动相似。表1比较了在上述的Mobile、Tennis、Garden和Surfside 4个序列上各种块匹配算法的4个评价指标。
    从表中可以看出，SEA算法的性能最优，但每个块的平均搜索点数过高。若当前帧中图像块的运动向量之间有较高的相关性，例如Garden和Surfside序列，则本文的算法可以同时显著地加速搜索速率和提高搜索精度。而在Tennis序列中，静止的背景中存在多个目标，一部分图像块运动向量之间的相关性较差，为此，本文的算法比较了更多的搜索点，虽然每个块的平均搜索点数略有增加，但是搜索误差相对较小。Mobile序列中也存在多个目标，但整个场景的运动是全局性的，因此本文的算法既提高了搜索的速率，又提高了搜索的准确率。
   3 、结论
    基于块的方法是最常用的运动估计方法，本文设计了一种基于空间预测的块运动估计的快速算法，将该算法与SEA、N3SS、DS、HEXBS、CDS、CDHS算法进行了比较，得到了令人满意的结果。

    参 考 文 献
[1] J. R. Jain, A. K. Jain. Displacement Measurement and Its Application in Interframe Image Coding [J]. IEEE Transactions on Communications, 1981, 29(12): 1799～1808
[2] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, T. Ishiguro. Motion Compensated Interframe Coding for Video Conferencing [A]. In: Proceedings IEEE National Telecommunication Conference. 1981: G5.3.1～G5.3.5
[3] M. Ghanbari. The Cross-Search Algorithm for Motion Estimation [J]. IEEE Transactions on Communications, 1990, 38(7): 950～953
[4] R. Li, B. Zeng, M. L. Liou. A New Three-Step Search Algorithm for Block Motion Estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1994, 4(8): 438～442
[5] L. M. Po, W. C. Ma. A Novel Four-Step Search Algorithm for Fast Block Motion Estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(6): 313～317
[6] L. K. Liu, E. Feig. A Block-based Gradient Descent Search Algorithm for Block Motion Estimation in Video Coding [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(8): 419～423
[7] J. Y. Tham, S. Ranganath, M. Ranganath, A. A. Kassim, A Novel Unrestricted Center-biased Diamond Search Algorithm for Block Motion Estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1998, 8(8): 369～377
[8] S. Zhu, K. K. Ma. A New Diamond Search Algorithm for Fast Block-matching Motion Estimation [J]. IEEE Transactions on Image Processing, 2000, 9(2): 287～290
[9] C. Zhu, X. Lin, L. P. Chau. Hexagon-based Search Pattern for Fast Block Motion Estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2002, 12(5): 349～355
[10] C. H. Cheung, L. M. Po. A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2002, 12(12): 1168～1177
[11] X. Jing, L.P. Chau. An Efficient Three-Step Search Algorithm for Block Motion Estimation [J]. IEEE Transactions on Multimedia, 2004, 6(6): 435～438
[12] C. H. Cheung, L. M. Po. Novel Cross-Diamond-Hexagonal Search Algorithms for Fast Block Motion Estimation [J]. IEEE Transactions on Multimedia, 2005, 7(2): 16～22
[13] L. J. Luo, C. Zou, X. Q. Gao, A New Prediction Search Algorithm for Block Motion Estimation in Video Coding [J]. IEEE Transactions on Consumer Electronics, 1997, 43(2): 56～61
[14] J. B. Xu, L. M. Po, C. K. Cheng. Adaptive Motion Tracking Block-matching Algorithms for Video Coding [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1999, 97(10): 1025～1029
[15] C. H. Hsieh, P. C. Lu, J. S. Shyn, E. H. Lu. Motion Estimation Algorithm Using Inter-block Correlation [J]. Electronic Letters, 1990, 26(3): 276～277
[16] K. M. Uz, M. Vetterli, D. LeGall. Interpolative Multiresolution Coding of Advanced Television with Compatible Subchannels [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1991, 1(3): 86～99
[17] Y. Q. Zhang, S. Zafar. Motion-compensated Wavelet Transform Coding for Color Video Compression [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1992, 2(9): 285～296
[18] W. Li, E. Salari. Successive Elimination Algorithm for Motion Estimation [J]. IEEE Transactions on Image Processing, 1995, 4(1): 105～107