应用于电子稳像的改进块匹配算法

杨 莉 邵克勇 刘远红 白丽丽 张会珍

(东北石油大学电气信息工程学院，黑龙江 大庆 163318)

电子稳像是一种利用图像处理手段实现视频去抖的技术。经典电子稳像过程主要包含3部分：运动估计、运动分离和运动补偿。其中，运动估计用来检测视频帧之间的全局运动矢量。作为稳像过程的第一步，其计算的准确性和速度对后续处理有重要影响。块匹配(BMA)是电子稳像中常用的运动估计算法,其基本思想是将参考帧图像分成一定大小的图像块，在当前帧中找到各块的最佳匹配位置，以一定准则去除错误匹配，计算得到帧间全局运动矢量。

准确并快速定位最佳匹配位置是块匹配搜索算法的研究目的。在已有的搜索算法中，基于平均绝对值误差(MAD)和平均方差(MSE)的全局搜索算法(FS)被认为是块匹配中最准确的算法[1]。但其缺点是计算量大，难以实时处理。常用的改进算法多是采用减少搜索点的数量来提高速度。比较典型的有三步法(NTSS)[2]、四步法(4SS)[3]及菱形搜索法(Diamond)[4]等。在此基础上后继学者又进行了很多改进，如文献[5,6]中所提出的算法。这些快速搜索算法的主体思想，都是利用图像运动矢量的中心偏置特性，即越接近最佳匹配位置，匹配误差越小。在图像小偏移的情况下，初始搜索位置大多在中心偏置区域内，所得运动估计具有很好的准确性和快速性。然而，在实际稳像应用中，图像帧的偏移经常超出最小偏置作用区域，造成初始搜索方向不确定，很容易陷入局部最优，产生错误运动估计。为处理偏移较大的情况，可以扩大窗口搜索范围，采用全局搜索方式找到最小匹配误差的位置，但计算复杂度会大幅增加。针对这一缺陷，笔者提出了一种检测大偏移运动的扩展搜索算法，综合了全局搜索的准确性和中心偏置快速性。

1 准备工作①

1.1 块的选取

图像偏移过大时，边缘区域不能在两帧中重复出现，因此尽量避免将块选择在靠近边缘区域的位置上，故将每帧图像的四周预留10%的边界补偿区域。

块匹配基于块内各像素点做相同运动的原则。块选得太大，内部像素运动的不一致性增大，且计算量增加；块选得太小，匹配特征不显著，易受噪声干扰。笔者针对640×360大小的视频帧，在区域内均匀选择大小为16×16的块，并使块间间距与块的大小相同。

位于图像平坦区域或直线边缘处的块，所在区域纹理相近，块的移动不能引起匹配误差的显著变化，难以精确定位，应用梯度阈值剔除这类块。

1.2 降采样全局搜索算法(DSFS)

在引出中心扩展搜索法之前，先介绍一种降采样全局搜索算法。采用最小绝对误差(SAD)作为搜索的匹配准则。

图1a是全局搜索算法的示意图，颜色越浅表示匹配误差越小。计算搜索窗口内每一个点的SAD值，找到最小值(图中颜色最浅的s)处为最佳匹配位置。图1b是降采样全局搜索算法示意图，在搜索窗口内隔行隔列取点计算SAD值，在最小值处与相邻的8个点比较，找到最佳匹配点位置。

a. 全局搜索算法 b. 降采样全局搜索算法

与全局搜索算法相比，降采样全局搜索算法减少了计算点数，由于其间隔只有一个像素，中心偏置特性在最佳匹配位置附近很显著，其精确度与全局搜索相当。降采样全局搜索法虽然减少了计算点数，依然无法克服全局搜索的缺陷，即窗口大小固定。对于无偏移的两幅图像，仍要遍历完整个窗口寻找到最小偏差位置。这样使得每个块匹配的计算量只与预设搜索窗口大小有关，无论图像实际偏移如何，计算开销不变。显然，这种搜索方式在大多数情况下将进行很多不必要的计算。

2 中心扩展搜索算法(CEXS)

假设进入中心偏置区域内时，梯度向量的方向基本一致，指向最佳匹配中心。基于降采样全局搜索法(DSFS)原理，以起始点为中心，向外逐层扩展，搜索到进入中心偏置区域内的点，再在中心偏置区域内准确定位最佳匹配位置。具体步骤如下：

a. 以起始点P0为圆心，找到半径r1的圆环C1上的最小SAD值SAD(P1)，P1为最小SAD值所在位置，并记圆心到P1的向量为LV1=P1-P0。

b. 令r2=r1+Δr，得到半径r2的圆环C2上最小SAD值SAD(P2)和位置P2，并得到向量LV2=P2-P1。

c. 用相同的计算方式得到在半径为rk=r1+(k-1)Δr的圆周Ck上最小SAD值SAD(Pk)和位置Pk，并得到向量LVk=Pk-Pk-1。

e. 若不满足步骤d中的条件，则继续执行步骤c，直到半径扩大到搜索窗口的边界为止。

图2 中心扩展搜索算法原理示意图

实际中，为了计算方便，用方形环代替圆环，可以得到很好的近似。

3 实验结果与分析

实验在Matlab 2012a仿真平台上进行，处理器主频为2.1GHz，内存2G，操作系统Windows7。对一段分辨率为640×360大小的抖动视频，应用笔者所提算法进行稳像。先通过实验比较算法处理两帧图像的效果，再给出处理整段视频序列的结果。分别就帧间小偏移和大偏移两种情况，采用全局搜索算法、菱形搜索算法、降采样全局搜索算法和中心扩展搜索算法获得帧间(水平、垂直、旋转)偏移参数，得到校正前后两帧的峰值信噪比(PSNR)，同时记录每种算法的运行时间。

图3为实验小偏移时选用的两帧图像，表1列出4种算法处理后的PSNR值和运行时间。

a. 参考帧 b. 当前帧

搜索算法PSNRdB时间消耗s全局搜索法32.687 48.557 7菱形搜索法32.687 40.064 2降采样全局搜索法32.687 42.196 9中心扩展搜索法32.687 40.795 5

图4为视频中大偏移的相邻两帧图像，表2是4种算法处理后的结果对比。

由实验结果可以看出，帧间小偏移时4种算法的峰值信噪比相同，均能准确得到全局运动向量，其中菱形搜索法耗时最少；大偏移情况下，菱形搜索法的峰值信噪比明显小于其他3种算法，原因是其计算参数出现错误，其他3种算法均可靠，且中心扩展搜索法耗时最少。

a. 参考帧 b. 当前帧

搜索算法PSNRdB时间消耗s全局搜索法22.769 16.427 9菱形搜索法17.229 10.082 3降采样全局搜索法22.767 51.656 2中心扩展搜索法23.060 00.865 9

图5a为视频前100帧相邻帧间的峰值信噪比对比图，全局搜索法(FS)、降采样全局搜索法(DSFS)和中心扩展搜索算法(CEXS)的PSNR值基本相同，菱形搜索法(DS)出现很大波动，在偏移较大的情况先得出错误的全局运动矢量。图5b中显示了4种算法的时间消耗，其中全局搜索、降采样全局搜索算法的计算量主要与搜索窗口的大小有关，故其时间消耗对不同图像帧不发生显著变化，菱形搜索在较小范围内会找到最优解，总体计算量小，时间消耗显示在图中也很平缓。中心扩展搜索算法波动比较明显，其计算量随帧间偏移情况的不同而变化。

a. PSNR值对比 b. 计算时间对比

4 结束语

针对电子稳像中传统块匹配算法的缺陷，提出了一种中心扩展搜索算法，利用半全局搜索结合最小中心偏置特性，避免搜索陷入局部最优，同时降低了计算复杂度，能在一定程度上根据视频帧的偏移大小调整搜索步数，减少计算量。实验表明：新算法在具有全局搜索算法准确性的同时还提高了计算速度。然而提出的稳像算法尚需进一步完善，在图中可以看出，菱形搜索算法能准确定位的地方，新算法的时间消耗比其要高，需要继续改进。