运动估计中经典的块匹配算法比较

牛晓桐 孙 亮 牛 犇

合肥工业大学仪器科学与光电工程学院 安徽合肥 230009

【文章摘要】

运动估计算法的精度是决定超分辨率图像重建质量的一个很重要的因素，所谓运动估计就是对图像序列中前后两帧图像的同一像素点之间的运动进行估计。本论文采用平均峰值信噪比PSNR 和平均搜索点数为评判标准，在基本思想、算法描述、算法性能等方面对块匹配算法中四步搜索法、十字搜索法、双十字搜索算法进行分析比较，实验证明双十字搜索法具有复杂度小、准确度高的优点。

【关键词】

运动估计; 块匹配; 四步搜索; 十字搜索; 双十字搜索

1 块匹配算法简介

块匹配算法就是对两帧图像的同一个位置的运动通过分块比较得到其估计矢量。算法思想如下：每一帧图像都被分割为若干个大小为M × N 的块，通过中心定位找到参考帧上像素点(x, y)的所在的图像块，通过某种匹配准则估计得到待匹配帧上最佳匹配图像块。则这两个图像块之间的位移即为(x, y)点的位移。块匹配法的差异主要体现在匹配准则、搜索算法和块大小等方面。常用的块匹配准则有最小绝对差和函数、最小均方误差、最小平均绝对值差等。本文采用的是：

2 经典块匹配算法

2.1 四步搜索法FSS

（1）基本思想

四步搜索算法相对于三步搜索法, 搜索窗口由9×9 变成5×5 的9 个搜索点，FSS 搜索的上一步的最佳匹配位置决定了下一步的搜索范围并且将搜索窗口的中心移向最小块距离MBD 点处, 搜索步长在前三步不改变, 在最后一步改变步长,获得最后的最佳匹配位置, 而且后两步搜索窗口的宽度由MBD 点的位置来决定。（2）算法步骤

step1 ：在7×7 的搜索区域内，FSS搜索首先建一个5×5 的搜索窗口并计算如图1 所示9 个点的匹配误差。如果最小匹配误差点MBD 点出现在搜索窗口的中心，转到第四步，否则转到第二步。step2 ：新的搜索窗口的中心定位在第一步中的MBD 点，新建5×5 的窗口。最小匹配误差点出现在四角，如图2 所示，需要新增加5 个点计算匹配误差，找到匹配误差最小的点。最小误差点出现在为四边，如图3 所示，需要增加3 个黑色点计算其匹配误差。如果这些点的匹配误差都比中心点大，转到第四步，否则转到第三步。

step3 ：搜索方法和第二步相同，但终将会转到第四步。step4 ：搜索窗口缩小为3×3。最终结果由图4 所示的9 个点中的最小匹配误差点决定。

（3）性能分析

FSS 的最少搜索点数为9+8=17，最大搜索点数为9+5+5+8=27 个点，计算复杂度比TSS 低，对于方向上的误导性比TSS要小很多，具有较好的搜索效果。

2.2 十字搜索法RPS

（1）基本思想

为了进一步提高效率减少检查点数目，RPS 算法搜索利用四点十字方案。FSS 在第一步搜索时需要计算9 个点，而十字搜索只需要5 个。如果十字中心不是最小的SAD 点，十字搜索也只需要多计算

3 个点的SAD 值。

（2）算法步骤

Step1: RPS 搜索首先建立一个十字模板，计算十字模板的4 个十字端点的SAD值，通过其最近的块预测一个运动矢量，如图5 所示。

Step2: 上一步得到的最小SAD 点作为下一步搜索的新的十字中心，如图6 所示，比较新的十字模板的4 个端点和十字中心，得到新的最小SAD 点。Step3 ：重复第二步，直到十字模板的中心的SAD 值最小为止。__

（3）性能分析

十字搜索因为只计算十字模板的端点位置，有可能造成搜索方向的偏离，准确度较低，但是该搜索方法所需检测点的数目最少，计算复杂度比较低，从而搜索速度得到提高。

2.3 双十字搜索法DCS

（1）基本思想

双十字搜索算法是在十字搜素算法的基础上提出来的，采用了两个搜索模板，一个是4×4 的大十字模板，一个是2×2 的小十字模板，大十字搜索过程和十字搜索类似，不同的是在小十字精化时，为了得到最佳匹配点，它不仅检查小十字模板中心的四个端点，还增加了三个可能存在最小SAD 点的位置检测。

（2）算法步骤

Step1: 预测一个中心点位置作为初始搜索中心。

Step2 ：4×4 大十字搜索，以第一步得到的搜索中心建立一个4×4 大十字的大十字模板，把大十字模板的4 个端点位置的SAD 与中心点SAD 比较，如果最小SAD 出现在大十字中心则停止搜索，转到第四步，否则转到第三步，如图7 所示。Step3 ：重复第二步搜所，检查新的大十字模板的四个端点位置的SAD 值。Step4 ：2×2 小十字搜索，以上一步得到的最小SAD 点的位置作为新的2×2小十字模板的中心，如图8 所示的4 种情况下，多计算额外的3 个可能的最佳点，检查2×2 小十字模板其它三个端点的SAD 值，。最终结果由这六个点和当前十字中心里的最小SAD 点来决定。图8

（3）性能分析

双十字精化搜索与RPS 相比仍然具有快速搜索的优点，在计算量没有明显增加的情况下，还提高了搜索的准确度。

3 实验结果及分析

在matlab 7.0 上进行仿真实验，采用了YUV 格式的标准测试序列“foreman”和“highway”的前30 帧对于四步搜索算法、十字搜索算法以及双十字搜索算法进行了测试并与全搜索算法FS 进行比较。在测试过程中，采用SAD 为匹配准则，运动估计的块大小为16×16，搜索步长为7。我们主要测试了每块的平均搜索点数和平均峰值信噪比PSNR , 结果如下表所示：表1 表示foreman 各种块匹配算法情况下的每块的平均搜索点数points、相对全搜索算法的加速率ratio 以及平均峰值信噪比PSNR ：表2 分别表示highway 在各种块匹配算法情况下的每块的平均搜索点数points、相对全搜索算法的加速率ratio 以及平均峰值信噪比PSNR ：

4 结语

本文介绍了运动估计的原理以及一些经典的块匹配算法，通过3 个不同视频序列的仿真结果可以看出, DCS 算法在提高搜索速度的同时, 性能 PSNR 与其他算法相比变化几乎可以忽略不计, 这说明在达到相同搜索质量的前提下，DCS 算法很能在很大程度上使搜索速度得以提高。

【参考文献】

[1] 陈宫, 牛秦洲. 图像序列运动估计中经典块匹配算法研究[J]. 计算机应用与软件,2012,29(5):147-151.

[2] 刘海华, 雷奕, 谢长生. 双十字搜索算法的快速块匹配运动估计[J]. 计算机研究与发

展,2006,43(9):1666-1673.