基于块匹配的视频图像运动估计技术研究_.pdf

《基于块匹配的视频图像运动估计技术研究_.pdf》由会员分享，可在线阅读，更多相关《基于块匹配的视频图像运动估计技术研究_.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、162.4 经典的块匹配算法2.4.1 全搜索法（Full Search Method,FS）全搜索法（Full Search Method,FS）也称为穷尽搜索法，是对（M2dx）（N2dy）搜索范围内所有可能的候选位置计算MAD(i,j)值，从中找出最小MAD，其对应偏移量即为所求运动矢量。此算法虽计算量大，但最简单、可靠，找到的必为全局最优点。FS 算法描述如下：从原点出发，按顺时针螺旋方向由近及远，在逐个像素处计算MAD值，直到遍历搜索范围内听有的点，然后在计算的所有点的MAD 中找到最小值，该点所在位置即对应最佳运动矢量。FS 算法是最简单、最原始的块匹配算法，由于可靠，且能够得到全

2、局最优的结果，通常是其它算法性能比较的标准，但它的计算量的确很大，这就限制了在需要实时压缩场合的应用，所以有必要进一步研究其它的快速算法。2.4.2 三步搜索算法（Three Step Search，TSS）此搜索算法如图2-2 所示，每一步搜索9 个位置点，对每一个位置计算MSE（最小均方误差）来确定最小失真方向（DMD），在最小失真方向上搜索区域减少一半进行第二步的搜索匹配，然后继续沿最小失真方向将搜索区域又减少一半第一步第二步第三步图 2-2 三步法（TSS）搜索步骤17来进行第三步的搜索匹配，由于第二步和第三步的9 个搜索点中均有一个点是在上一步中已经计算过MSE 值，所以第二步与第三

3、步均只要计算8 个点而已，所以 TSS 算法的计算次数是98825 次，同直接匹配需要169 次比较，计算量大大减少。2.4.3 新三步搜索算法26（New Three Step Search,NTSS）大部分近似的快速BMA 算法（如 TSS、2D-LOG 等）假设 BDM 随搜索窗口内当前检查点与最优BDM 点之间的距离的增大而单调增加（当BDM 为 MSE 或MAD 时），然而这个假设并非总是正确，原因是：孔径问题；分块时引起的运动物体和背景的不连续分割；周期性纹理形状的图像内容；光线改变。以上原因有时会导致搜索过程陷入局部最优点而找不到真正的最优点。这正是TSS等传统快速BMA 的主要

4、缺点。不过，尽管 BDM 的单峰假设在全局上并不总是成立，但是它在全局最优点的一个小邻域内还是成立的。因此利用运动矢量的中心偏移特性的新三步法（NTSS）、四步法（FSS）、二步法（2SS）等可以比TSS、2D-LOG 等得到更好的结果。Renxiang Li 等于 1994 年提出了新三步搜索算法。NTSS 是对 TSS 的一个改进，对运动量比较小的视频序列如可视电话序列有比较好的性能。对于绝大多数的视频序列，运动矢量的分布都是在中心位置上的概率最大，随着与中心位置的距离的增大，概率会急剧地下降，这也就是前面所说的运动矢量的中心偏移特性。运动量比较小的视频序列的这一特性会更加明显。图2-3

5、显示了这种中心偏移特性。图 2-3 Saleman 运动矢量18为了利用运动矢量的中心偏移特性，NTSS 在第一步除了搜索TSS 第一步的9 个点外，还搜索了中心点周围的8 个点，如图2-4 所示。图中显示出了W7时的两个搜索路径。中间位置的路径显示了搜索小运动的情形。在这种情形下，第一步的最小BDM 点是中心点周围的8 个相邻点之一，这时只要再搜索一下该第一步第二步第三步图 2-4 新三步法（NTSS）示意图点周围的3 个点（若该点为8 个相邻点中的4 个边点之一，如图2-4 所示）或者5 个点（若该点为8 个相邻点中的4 个角点之一），即可结束本次搜索，这样的话，图中的情形只需2 步，共搜

6、索17320 个点；若为角点，则也是2 步，这时的搜索点数是17522 个。右上的路径是大运动的情形，第一步的最小BDM 点是外部的8 个搜索点之一，第二步以后的方法与TSS 完全相同。因此总共也是3步，但总搜索点数目多了8 个，为 178833 个。另外，在 NTSS 中如果第一步的最小BDM 点恰好是中心点，则立即停止搜索，搜索得出的运动矢量结果为（0，0）。2.4.4 四步搜索算法27（Four Step Search，FSS）Lar Man Po 等于 1996 年提出了四步搜索算法（FSS）。该算法也利用了运动矢量的中心偏移特性，方法是采用比TSS 小的初始步长，取为W4。由于采用了

7、较小的初始步长，W7 时 FSS需要 4 步才能达到搜索窗口的边缘。与 NTSS 一样，当运动较小时，FSS 也会很快结束搜索过程，只需要2 到 3步即可。图2-5 显示了大运动量时FSS的两个搜索路径，二者都需要4 步。左下方的路径需要搜索953825 个点。正好与三步法（TSS）相同；右上方的路径则需要955827 个点，比三步法（TSS）略多。不过W7 时 27 个搜索点是 FSS的最坏情况。-6 -4 -2 0 2 4 6-6 -4 -2 0 2 4 619第一步第二步第三步第四步图 2-5 四步法（FSS）示意图 1 图 2-6 显示了运动较小时FSS 的两个搜索路径，分别只需要2

8、步和 3 步，而且 W 为任何值时都是如此。左边的路径需要9817 个搜索点，右边的需要93820 个搜索点。图 2-6 四步搜索算法（FSS）示意图 2 从图 2-5 和图 2-6 中可以看出，当最小BDM 点不在某次搜索的中心位置时，则下一步需要3 个或 5 个搜索点（最后一步除外）；如果已达到搜索窗口的边缘，则进行最后一步。如果最小BDM 点在中心位置，则步长减半，增加8 个点；如果此时 W1 则进行最后一步。2.4.5 基于块的梯度下降搜索算法28（Block-Based Gradient Descent Search,BBGDS）基于块的梯度下降搜索法是1996 年由 Lurng-K

9、uo Li和 Ephraim Feig 提出的。-6 -4 -2 0 2 4 6-6 -4 -2 0 2 4 620该算法采用了一个非常偏向于中心位置的搜索模式步长为1 的 9 点搜索，如图 2-7 所示。它不限制搜索的步数，当某一步的最小BDM 点位于中心位置或该步已到达搜索窗口的边缘时，则停止搜索。与FSS 的某些搜索步骤一样，BBGDS的每个后续搜索步骤都是增加3 个或 5 个搜索点。这个算法非常适合于小运动量的场合。图2-7 显示了 BBGDS 的两个小运动情况下的搜索路径。Step 1：使用 33 搜索窗对 9 个点进行搜索；Step 2：若 BDM 点在搜索窗中心，则算法结束；否则

10、以上一步BDM 点为中心，重复 Step 1。在每一步搜索过程中，BBGDS 算法使用了中心匹配块而不是匹配块，降低了陷入局部最优的可能性。利用梯度下降的方向来指导搜索方向，对该方向进行重点搜索，从而减少和避免了不必要的搜索，大大降低了算法的复杂度。第一步第二步第三步图 2-7 BBGDS 算法示意图2.4.6 二维对数搜索算法29（Two-Dimensional Logarithmic，TDL）为了减少块匹配算法的计算，人们提出了许多块匹配快速算法。J.R.Jain 和A.K.Jain 早在 1981 年就提出了二维对数搜索算法。它开创了快速算法的先例，分多个阶段搜索，逐次减小搜索范围直到不

11、能再小而结束。其搜索步骤如图2-8 所示。它通过连续减少搜索区域来寻找最小失真方向（DMD）。每一步搜索由区域中心位置和与中心相联的4 个边缘点组成，形状就是一个十字形，连续搜索直到寻找的区域成为33 矩形区域为止。最后一步计算33 矩形区域 9 个位置点，MSE 最小值就是要寻找的DMD。在这种算法中，MES 的搜索点数是w2log72+，同直接寻找所需搜索点数2w 相比较，计算量大大减少。-6 -4 -2 0 2 4 6-6 -4 -2 0 2 4 621图 2-8 二维对数搜索算法（TDL）示意图算法的具体步骤是：Step 1：从原点开始，选取一定的步长，在以十字形分布的五个点处进行最小

12、块误差 MAD 值的计算并比较；Step 2：若 MBD 点在边缘四个点处，则以该点为中心点，保持步长不变，重新搜索十字形分布的五个点；若MBD 点位于中心点，则保持中心点位置不变，将十字点群的步长减半，并在五个点处计算；Step 3：在中心及周围8 个点处找出MBD 点，若步长为1，该点所在位置即对应最佳匹配点，算法结束；否则重复Step 2。具体的一个搜索例子请参考图2-8。图中点（0，-4）、（+4，-4）、（+6，-4）是每个搜索阶段的最小块误差点。最终运动矢量为（+5，-4），每个点上的数字表明了每个阶段搜索时计算的候选块的位置。TDL 算法搜索时，最大搜索点数为w2log72+，若

13、发现新的十字形点群的中心点位于搜索区的边缘，则步长也减半，后来有人提出应该在搜索的每个阶段都将步长减半。所有这些改动都是为了使算法搜索范围很快变小，提高收敛速度。TDL 算法的前提是假设搜索区内只有一个谷点，如果搜索区内存在多个谷点时，该方法找到的可能是局部最小点。不能保证找到全局最优点也正是大部分快速搜索算法的通病。-8 -6 -4 -2 0 2 4 6 8-8 -6 -4 -2 0 2 4 6 8111112223344445566666666222.4.7 菱形搜索算法30（Diamond Search，DS）DS 算法即菱形算法，也称钻石算法，最早由 Shan Zhu 和 Kai-Ku

14、ang Ma 两人提出，后又经过多次改进，已成为目前快速块匹配算法中性能最优异的算法之一，该算法同时也被MPEG-4 VM 标准接受。搜索模板的形状和大小不但影响整个算法的运行速度，而且也影响它的性能。块匹配的误差实际上是在搜索范围内建立了误差表面函数，全局最小点即对应着最佳运动矢量。由于这个误差表面通常并不是单调的，所以搜索窗口太小，就容易陷入局部最优，例如BBGDS 算法，其搜索窗口仅为33；而搜索窗口太大，又容易产生错误的搜索路径，象TSS 算法的第一步。另外，统计数据表明，视频图像进行运动估计时，最优点通常在零矢量周围(以搜索窗口中心为圆心，两像素为半径的圆内)，如图 2-9 所示。基

15、于这两点实事，DS 算法采用了两种搜索模板，分别是只有5 个检测点的小模板 SDSM(Small Diamond Search Mask)和 9 个检测点的大模板LDSM(Large Diamond Search Mask)，如图 2-10 和图 2-11 所示。搜索时先用大模板计算，当最小块误差MBD 点出现在中心点处时，将大模板LDSM 换为 SDSM，再进行匹配计算，这时5 个点中的 MBD 即为最优匹配点。图 2-9 最优点分布规律图 2-10 小模板 SDSM 图 2-11 大模板 LDSM DS 算法的具体步骤是：Step 1：用 LDSM 在搜索区域中心及周围八个点处进行匹配计算

16、。若MBD点位于中心点，则进行Step 3；否则进行Step 2。Step 2：以上一次找到的MBD 点作为中心点，用新的 LDSM 来计算，若 MBD点位于中心点，则进行Step 3；否则重复Step 2。Step 3：以上一次找到的MBD 点作为中心点，将LDSM 换为 SDSM，在五个点处计算，找出MBD 点，该点所在位置即对应最佳运动矢量。如图 2-12 所示，就是一个用DS 算法搜索到运动矢量(-5，-2)的例子，。搜索共有 5 步，MBD 点分别为(-2，0),(-3，-1),(-4，-2)，使用了四次LDSM 和一次SDSM，总共搜索了24 个点。23第一步第二步第三步第四步第五

17、步图 2-12 菱形（Diamond Search）算法示意图DS 算法的特点在于它分析了视频图像中运动矢量的基本规律，选用了大小两种形状的搜索模板LDSM 和 SDSM。先用 LDSM 搜索，由于步长大，搜索范围广，可以进行粗定位，使搜索过程不会陷于局部最小；当粗定位结束后，可以认为最优点就在LDSM 周围 8 个点所围的菱形区域中，这时再用 SDSM 来准确定位，使搜索不至于有大的起伏，所以它的性能优于其它算法。另外，DS 搜索时各步骤之间有很强的相关性，模板移动时只需在几个新的检测点处进行匹配计算，所以也提高了搜索速度。2.4.8 交叉搜索算法31（Cross Search Algori

18、thm，CSA）1990年，Ghanbari 提出了交叉搜索算法,它也是在 TDL 和 TSS 基础上为进一步减少计算量而发展起来的快速算法。CSA 是从原点开始，以“”字形分布的五个点构成每次搜索的点群，以TDL 的搜索方法检测MBD 点，仅在最后一步采用“十”字形点群。CSA 算法以“”字形搜索模式、初始步长为W2 开始搜索，每一步搜索5 个点，步长也是每一步减半。图2-13 显示了 CSA 的两个搜索路径。当步长减到1 时：如果该步骤的最小BDM 点位于中心、左上角或右上角位置，则以该点为中心再进行一次步长为1 的搜索，但搜索模式为“十”字形（如图2-13 所示左下方的路径）；否则，以该

19、点为中心再进行一次步长为1 的“”字形搜索（如图2-13 所示右上方的路径）。W7 时，CSA 需要搜索 544417 个点，共4 步。对于任意W，CSA 需进行)1(log12+W步，搜索)1(log452+W个点。CSA 算法的具体步骤是：Step l：从原点开始，选取最大搜索长度的一半为步长，在以“”字形分布-8 -6 -4 -2 0 2 4 6 8-8 -6 -4 -2 0 2 4 6 824第一步第二步第三步第四步图 2-13 交叉搜索算法（CSA）示意图的五个点处进行块匹配计算并比较。Step 2：以上一步的MBD 点为中心，将步长减半，继续做“”字形的5 点搜索。若步长大于1，则

20、重复 Step 2；若步长为1，则进行 Step 3。Step 3：最后一步根据MBD 点的位置，分别做“十”字形和“”字形搜索：若上一步MBD 点处于中心点、左上角或右上角，做“十”字形搜索；若上一步MBD 点处于左下角或右下角，做“”字形搜索。由当前MBD 点得到最佳运动矢量，算法结束。CSA 的最大搜索点数为)1(log452+W，搜索速度很快，但是运动补偿的效果不算太好，在搜索区域的边界上有四分之一的点CSA 没有考虑，因此它不适用于较复杂的运动。2.4.9 共轭方向搜索算法（A Conjugate Direction Search，CDS）早在 1985 年，R.Srinirasan

21、 和 K.Rao 提出了共轭方向搜索算法。搜索示意图如图 2-14 所示。图 2-14 共轭方向搜索算法（CDS）示意图-6 -4 -2 0 2 4 6 -6 -4 -2 0 2 4 6 i-1j-3 j-1 j j+1 j+3 j+5i-5i-3i+1i1111122222333123为水平方向上的极小值点为垂直方向上的极小值点为搜索域中最小值点25共轭方向搜索算法是一种寻找最小失真方向的有效方法。第一步是沿着水平方向的轴上搜索，计算最小均方误差函数（MSE），找出最小失真方向（DMD）。第二步是以沿着水平方向找到的最小失真方向为起点，朝垂直方向搜索，找到垂直方向上的极小值点。第三步是把水平

22、方向的极小值点和垂直方向的极小值点相连，沿着连线搜索，找到连线上的极小值点。显然，连线上的极小值点就是矩形区域内的最小值点即为全程搜索DMD。2.4.10 正交搜索算法32（Orthogonal Search Algorithm,OSA）Puri 等于 1987 年提出了 OSA 算法，也是最早提出利用运动矢量的相关性进行中心搜索点预测的算法。OSA 的初始步长是W2，每一步都包含水平与竖直搜索两个小步骤，两个小步骤的步长相同。图2-15 显示了 OSA 的两个不同的搜索路径。从水平搜索开始，首先搜索水平方向上的三个点，最小BMD 点作为下一步竖直搜索的中心点，竖直方向上也是搜索三个点，与TS

23、S 相同，第二步以后每一步的步长也是上一步步长的一半。如果步长减少到1 时，则该步为最后一步。不过 OSA 的最后一步仍然与前面的步骤相同，不像TDL 最后一步与TSS 相同。图 2-15 中 W7，需搜索32222213 个点，总共也是3 步。通常情况下，OSA 需进行)1(log2+W步，搜索)1(log412+W个点。可见。OSA 搜索的点数大约是TSS 的一半。第一步第二步第三步图 2-15 正交搜索算法（OSA）示意图OSA 算法每一步可以看成是由水平和垂直两个阶段组成，直到步长变为1 时视为算法结束。由于每次计算的匹配点数太少，不能顾及各个方向，虽然速度较快，但得到局部最优的可能性

24、进一步扩大。-6 -4 -2 0 2 4 6262.4.11 分层块匹配算法33（HBMA）Bierling 于 1988 年提出了HBMA 算法。其基本思想是在图像的多分辨率表示的每一层分别进行运动估计，从最底分辨率层开始，逐层进行，最底层以外的其它层进行运动估计时都要利用上一层的估计结果，如图2-16 所示。低分辨率层估计出来的运动矢量将被用来作为下一步估计时的初始值，即高分辨率层的运动估计是对上一低分辨率层估计结果的进一步细化。由于已经有了粗精度的初始估计，高分辨率层在进行运动估计时就可以采用更小的搜索窗口。每一层都可以采用各种BMA 方法如 FS、TSS 等。低分辨率层可以通过对高分辨

25、率层进行亚抽样得到，也可以采用均值塔形算法或其它算法得到。均值塔形算法的低分辨率层的每一像素对应上一高分辨率层的四个像素，且像素值为四个像素值的均值。HBMA 可用于分层视频编码以提供性能可伸缩性。第一步第二步第三步图 2-16 分层块匹配算法（HBMA）示意图2.4.12 简易搜索算法（SES）简易搜索算法又称为象限法，它是在 TSS 的基础上进一步减少调用函数的次数。TSS 中，有完整的八个搜索方向，每个方向都有一个相反的方向。据单律性误差平面的假定，块匹配误差沿远离全局最小误差处的方向单调增加。这意味着：最小值不可能同时在两个相反的方向上产生。也就是说，实际上每一步最多需要搜索八个方向的

26、一半，因此，计算复杂度可大大减少。但另一方面，为了确定搜索方向，也需要附加一定计算。SES 算法的原理是：我们可以先任选两个正交的方向，然后将搜索区域限制低高-6 -4 -2 0 2 4 6分辨率层分辨率层27在某一个仅含三个搜索方向的象限中；另外，同TSS 一样，SES算法也使用第二步和第三步来确定所需的步骤数目和步长。SES 的创新在于它将每一步分为两段来完成：第一段用来选择进行搜索的象限；第二段用来在所选象限中寻找最小误差所处位置。在第一段中，我们计算A（0，0），B（P，0），C（0，-P）三个点（如图2-17所示）的误差函数（选定MAD）值。然后，根据下述四条准则选择象限：如果 MA

27、D（A）MAD（B）且 MAD（A）MAD（C），选择第 IV 象限；如果 MAD（A）MAD（B）且 MAD（A）MAD（C），选择第 I 象限；如果 MAD（A）MAD（B）且 MAD（A）MAD（C），选择第 II 象限；如果 MAD（A）MAD（B）且 MAD（A）MAD（C），选择第 III 象限；图 2-17 SES 算法第一段示意图在第二段中，根据每个选定的象限，如图2-18 所示，其中a、b、c、d 分别对应 I、II、III、IV 象限，进一步计算相应的某些位置（如黑点所示）的MAD 并作比较。其它与TSS 相同。SES在 TSS 的基础上将处理速度提高了近一倍。图 2-18

28、 SES 算法第二段示意图综上所述，通过总结概括以上经典的块匹配搜索算法，我们不难发现，基于块匹配的运动估计算法的性能取决于以下三个因素：搜索策略；匹配准则；搜索范围参数。其复杂度亦由上述三个因素决定。显然，通过选择适当的搜索策略、减少匹配准则的复杂性或缩短搜索距离可以降低块匹配算法的复杂性。这就决定了基于块匹配的运动估计算法研究必须解决以下几个难题：1、搜索起点的选择由于参考帧所对应的原点往往不是最优匹配点所在的位置，所以为了缩小目标的搜索范围，缩短搜索起点与最优匹配点之间的距离，许多算法都采用了某种方法预测目标在下一时刻可能出现的位置，并以其作为搜索范围的原点。ABCIIIIIIIVABC

29、ABCABCABC第一次第二次282、匹配准则为了测量当前帧中的匹配块与参考帧中候选块的相似度，定义了三个匹配准则：平均平方误差（Mean Square Error,MSE），平均绝对误差（Mean Absolute Difference,MAD）和 归 一 化 互 相 关 函 数（Normalized Cross Correlation Function,NCCF）。因为不需要乘法运算，平均绝对误差（MAD）是最常用的匹配准则。但这些匹配准则通常要求块内所有像素都参与计算，研究者们从抽样定理得到启发，运用在搜素区内只选取部分搜索点进行运动估计的思路，从块内选取一定数量的像素来计算MSE 或

30、MAD 也达到了相同的效果，这样做最直接的好处是减小了计算量，提高搜索速度。3、块匹配算法（BMA）全搜索法是最直接的块匹配算法，它通过对搜索窗中所有测试点的检查来获得最优匹配点的运动矢量。全搜索算法虽然可以获得最精确的运动矢量，但由于计算复杂性高，所以并不实用。为了降低全搜索算法的计算复杂度，研究者们提出了很多减少搜索窗尺寸或测试点数目的块匹配算法。最常用的三步搜索算法（TSS）、新三步算法（NTSS）、四步搜索算法（FSS）、钻石搜索算法（DS）等等。它们将计算复杂度降低，利用合适的硬件可以实时实现的。因此这些算法己成为发展新算法的基准。2.5 本章小结本章首先介绍了运动估计的二维运动模型、块匹配运动估计搜索算法的工作原理以及块匹配搜索算法的评价方法，在此基础上，详细研究了运动估计的12种经典的快速块匹配搜索算法，重点分析和研究了这些快速块匹配法的的理论模型、搜索策略与搜索步骤，与当前相关文献相比，更加精细和系统规范地绘制了这些经典快速算法的搜索流程示意图，并分析和总结了各自的适用范围和优缺点。