用于快速块运动估计的多方向钻石搜索算法*

阴法明

(南京信息职业技术学院，南京 210013)

由于视频序列的相邻帧间具有很高的时间相关性，视频编码系统可以通过降低时间冗余度而获得高压缩率。帧间编码利用前面的帧(或参考帧)预测当前帧，降低连续帧间的时间冗余度。运动估计是帧间编码的核心技术。相比于其他运动估计算法，块匹配技术因为其简单性与易于实现性，而被广泛应用于许多视频编码标准中，如MPEG2、H.26x。在块匹配技术中，每帧都被划分成块，每块都对应一个运动矢量。运动预测通过搜索为当前帧的每个块产生一个运动矢量，它指向参考帧中的最佳匹配块。该最佳匹配块作为当前块的预测值。

全搜索(Full Search，FS)块匹配算法是最简单的，并且性能最好。其缺点是计算复杂度大。它搜索参考帧搜索范围内的所有点，从而产生最佳匹配点。如果搜索窗在水平与垂直方向上的最大运动分量为±W，每块需要搜索的点数为(2W+1)2。为了降低计算复杂度，快速搜索算法成为人们研究的重点。现在，典型的快速算法有3 步搜索(TSS)［1］、新3 步搜索(NTSS)［2］、4 步搜索(FSS)［3］、基于块的梯度下降搜索(BBGDS)［4］、钻石搜索(DS)［5］、1 次1 步搜索法(One-at-a-time Search，OTS)［6］等。

TSS 由3 步组成，每步包含均匀空间分布的9个点。并且每步之后，点之间的距离都会变小，前1步的最佳备选点作为当前的中心点。TSS 第1 步采用大搜索模板，使得其在搜索小运动量块时显得低效。这与现实视频序列的运动矢量的中心偏置特性相矛盾［2］。NTSS 通过在TSS 第1 步的中心点周围添加8个点，解决了这一问题。同时NTSS 允许在第1、第2 步后提前中止搜索，所以其搜索速度比TSS 要快，并且具有较好的搜索质量。但对于拥有大量较大运动矢量的序列，NTSS 的计算量要比TSS的大。FSS 搜索质量与NTSS 相仿，并优于TSS。

本文第1 部分，讲解视频编码中块匹配运动估计算法的基本原理。DS、OTS 两种快速搜索算法将在第2 部分中进行介绍。第3 部分提出多方向钻石搜索(MDDS)算法。第4 部分进行试验。最后，第五部分对实验结果进行分析。

1 基于块的运动估计基本原理

块匹配运动估计就是将图像划分成许多互不重叠的子块，并假定子块内的所有象素具有运动一致性，且只作平移运动，然后对当前帧图像的每一子块(也即宏块)，在参考帧的一定范围内按照一定的匹配准则进行匹配，搜索与当前子块最相似的块，即最佳匹配块，由最佳匹配块与当前子块的相对位置的偏移量，即为当前子块的运动矢量，如图1所示。

图1 基于块的运动估计基本原理

为了判定最佳匹配块，首先定义块误差准则(Block Distortion Measure，BDM)。本文选择绝对误差和(Sum of Absolute Difference，SAD)作为BDM。其定义如下:

其中，－W≤mx，my≤+W。每个N×N 块的左上角在当前帧ft中的坐标为(p，q)，它通过运动矢量(mx，my)在重建帧ft－Δt中得到同样大小块的预测值。

2 基础算法简介

2.1 钻石搜索算法

DS 算法使用两种搜索模板:大钻石搜索模板(Large Diamond Search Pattern，LDSP)与小钻石搜索模板(Small Diamond Search Pattern，SDSP)，如图2所示。

图2 大钻石搜索模板(LDSP)与小钻石搜索模板(SDSP)

大钻石搜索模板由9个点组成，小钻石搜索模板则为5个。该算法步骤如下:

第1 步:将LDSP 放在搜索窗口的中心，计算模板上每个点的SAD。如果最小SAD点在LDSP 的中心(c，c)，则跳至第3 步。否则进入第2 步。

第2 步:如果上一步的最小SAD点在LDSP 的顶点，如(c－2，c)、(c+2，c)、(c，c－2)或(c，c+2)，则将进行顶点搜索。如果上一步的最小SAD点在LDSP 的边上，如(c－1，c+1)、(c－1，c－1)、(c+1，c+1)或(c+1，c－1)，则进行面搜索。

顶点搜索:以上一步的最小SAD点为新的LDSP 的中心，更新中心点(c，c)，并计算新增五个点的SAD。例如最小SAD点在(c，c+2)，新的LDSP位置如图3(a)所示。

面搜索:以上一步的最小SAD点为新的LDSP的中心，更新中心点(c，c)，并计算新增三个点的SAD。例如最小点在(c+1，c+1)，新的LDSP 位置如图3(b)所示。

图3

如果模板覆盖的点超出搜索窗的边界则忽略。当新的最小SAD点出现在(c，c)，跳至第3 步。否则，循环执行第2 步。

第3 步:在点(c，c)使用SDSP，计算最后一个大钻石搜索模板内部四个点的SAD。类似，如果备选点超出搜索窗边界，则忽略。最小的SAD点对应的运动矢量作为预测块的最终运动矢量。当前块的搜索过程完成，可以进行下一块的搜索。

2.2 一次一步搜索算法

基于块的运动估计算法OTS 是由R.Srinivasan和K.R.Rao 在1985年首次提出［6］，在水平和垂直方向上先后应用OTS 搜索策略。一个OTS 搜索路径的例子如图3所示。首先，搜索窗中心及其水平方向上相邻的两个点先被搜索，即(0，0)、(－1，0)、(1，0)三个点。如果最小SAD点是搜索窗中心的左边点(－1，0)，则OTS 向搜索窗左边执行;如果最小SAD点搜索窗中心的右边点(1，0)，则OTS 向搜索窗右边执行。当最小SAD点出现在水平方向3点的中间时，OTS停止执行。该点被看作搜索窗中心水平方向上的最小SAD点，假设为(s，0)。垂直方向的OTS 于此类似，首先搜索(s，1)、(s，－1)两点。比较垂直方向上相邻3点的SAD，如果最小SAD点为(s，1)，OTS 则沿着(s，1)向上执行;如果最小SAD点为(s，－1)，OTS 则沿(s，－1)向下执行。垂直方向上OTS 终止条件与水平方向上的相同。此时得到的最小SAD点对应的MV 便是当前块的最终预测MV。简而言之，OTS 算法在误差平面上进行两次一维的梯度下降搜索。虽然与其他搜索算法相比，只需要搜索很少的点，但搜索的质量很低。因为一维梯度下降搜索算法不能有效搜索到全局最佳匹配点的位置。

如图4所示，一个用OTS 算法搜索的路径例子，最终得到的最佳匹配点为⑦。

图4 OTS 算法实例

3 多方向钻石搜索算法

DS 算法只考虑块误差梯度下降最大的方向，从而降低了得到最佳匹配点为全局最优的概率，本文提出了多方向钻石搜索法。该方法为了考虑到SAD 可能下降的每个方向，在钻石搜索法的第1 步之后，对LDSP 外围8个点中小于中心点SAD 的方向上执行OTS。

MDDS 算法中，LDSP 对应的8个方向如图5所示。

图5 LDSP 对应的八个方向

MDDS 算法的运行步骤如下:

开始 以搜索窗的中心为起点，开始使用模板LDSP。先计算LDSP 中心点的SAD，并用中心点信息初始化临时最佳匹配点的位置与SAD。

第1 步 计算LDSP 其它8个点的SAD。如果有点的SAD 小于中心点的SAD，则在该方向上执行OTS。将OTS 后的最小BMD 与临时最佳匹配点的SAD 比较，如果小，则更新临时最佳匹配点的位置信息与SAD值。如果中心点为最小SAD点，则跳至第3 步。否则进行第2 步。

第2 步 以上一步得到的临时最佳匹配点为中心，重复执行第1 步。

第3 步 使用SDSP，搜索LDSP 内部剩余的4个点，得到的最小SAD点作为最佳匹配点。

一个用MDDS 算法搜索的路径如图6所示。其中虚线表示检测过的SAD 可能下降的方向，实线表示所选择的SAD 下降的方向，即每一步得到的最小SAD点。

图6 MDDS 算法实例

4 测试结果

本文选取的测试模型为JM，版本为15.1，测试序列为CIF4:2:0 格式，其中Football、Ice 具有高度空间细节与大量运动;Soccer 具有中度空间细节和中量运动;Silent、Coastguard 具有中度空间细节和少量运动;Flower 具有低度空间细节和少量运动。W 取16，序列长度为100 帧，帧率为30 帧/秒，采用5个参考帧。序列编码方式为IPPP…，即第1 帧为I 编码，剩余99帧采用P 编码。I 帧的QP(量化参数)设为36，P 帧的QP为38。帧间编码只采用16×16 的宏块。熵编码方法为基于上下文的二进制算术编码。相互比较的搜索算法有:FS、NTSS、FSS、BBGDS、DS 与本文提出的MDDS。性能比较的参数为PSNR 与平均搜索点数(Average Number of Searched Points，ANSP)。实验结果如表1所示。

表1 MDDS 算法与FS、NTSS、FSS、BBGDS、DS 算法测试结果 单位:dB

5 小结

从表1 可以看出，FS 能够取的最好的搜索质量，但其计算复杂度太大。快速搜索算法在提高搜索速度的同时，很小程度的降低了搜索质量。总体来说，前四个快速搜索算法中，BBGDS 搜索速度最快，但质量也是最差的;FSS 算法搜索速度比较慢，对于帧间图像含有少量运动的序列性能最好;NTSS 搜索速度最慢，但搜索质量最佳，尤其是帧间图像具有大量运动和丰富空间细节的序列，对于帧间图像具有少量运动的序列性能一般。DS 算法搜索速度仅次于BBGDS 算法，但性能不如FSS 算法与NTSS 算法。

表2 MDDS 算法与DS 性能比较 单位:dB

如表2所示，本文提出的MDDS 搜索速度略低于DS，每个16×16 宏块平均多出0.48～1.86个搜索点，性能有很大提升，PSNR 最多提高了0.07 dB。序列帧间图像的运动量越大，空间细节信息越丰富，性能相对提高的越多。对于帧间图像含有中量与大量运动的序列，其性能略次于NTSS 算法;对于帧间图像含有少量运动的序列，性能持平或好于NTSS 算法。因此，该算法在搜索速度与性能上都具有一定的竞争优势。

［1］Koga T，Iinnma K，Hirano A，et al.Motion-Compensated Interframe Coding for Video Conferencing［C］//Nut.Telecommun.Con，pp.G5.3.145.G5(3).145－153.1981.

［2］Li R，Zeng B，Liou M L.A New Three-Step Search Algorithm for Block Motion Estimation［J］.IEEE Trans.Circuits Syst.Video Technol.，1994，4:438－442.

［3］Po L M，Ma W C.A Novel Four-Step Search Algorithm for Fast Block Motion Estimation［J］.IEEE Trans.Circuits Syst.Video Technol.，1996，6:313－317.

［4］Liu L K，Feig E.A Block-Based Gradient Descent Search Algorithm for Block Motion Estimation in Video Coding［J］.IEEE Trans.on Circuits and Systems for Video Technology，1996，6:419－422.

［5］Tham J Y，Ranganath S，Ranganath M，et al.A Novel Unrestricted Center-Biased Diamond Search Algorithm for Block Motion Estimation［J］.IEEE Trans.on Circuits and Systems for Video Technology，1998，8:369－377.

［6］Srinivasan R，Rao K R.Predictive Coding Based on Efficient Motion Estimation［J］.IEEE Trans.Commun.，1985，COM－33:888－896.