基于Canny算子的有效块匹配运动估计算法

谭 畅，季春玉，龚俊松，赵永党，魏景海

(东北林业大学理学院，哈尔滨150040)

从视频序列图像中提取有关物体运动的信息称为运动估计，其表达方式是运动矢量[1－3].常见的运动估计算法主要有块匹配法、像素递归法、全局运动估计算法等[4－5]，其中，块匹配法因其算法简单有效而得到广泛应用.块匹配运动估计就是按照匹配准则寻找当前块在参考帧中的匹配块.其算法分为2类，一类是完全搜索块匹配(FSBM)算法，它可以获得全局最优解，但是运算量大，不适合实时应用[6－7].一类是快速搜索块匹配算法CS、CDS、AMTS、GPS.利用相邻块之间的运动相关性，选择一个反映当前块运动趋势的预测点作为初始搜索点，以提高搜索速度和预测的准确性.评价运动估计最佳匹配的准则有很多种，常用的有平均绝对误差(mean absolute difference，MAD)、均方误差(mean square error，MSE)和归一化互相关系数(normalized cross correlation function，NCCF)等.

当前帧中特征块的选取对匹配的准确性有较大影响，特征块中包含图像的特征越多，越有利于提高配准的精度.另外考虑到图像在传输的过程中会受到噪声的污染，而噪声也会影响匹配的精度.基于以上两方面的考虑，本文首先利用Canny算子提取当前帧的轮廓，并用差分算子找出包含轮廓最多的小块，作为特征块.然后对参考帧进行2值化处理，并将处理后的参考帧在新的匹配准则下与特征块进行配准.与其他块匹配算法相比，本文算法在不增加计算复杂度的同时，还能有效地提高搜索精度.

1 Canny算子

Canny算子是一种常用的边缘检测算子，它可以有效地提高图像的边缘信息.这是由于其具有最为严格的边缘检测的3个标准，即好的信噪比、好的定位性能和单边响应准则(产生多个响应的概率低).

Canny算子的实现步骤如下.

1)用高斯滤波器对图像进行滤波，以减小噪声影响;

2)利用微分算子(如Roberts算子、Sobel算子)找到每个像素的梯度，并求出梯度的大小和方向;

3)对梯度进行非极大抑制，保留局部梯度最大的点，确定边缘，即若像素的灰度值与其梯度方向上前后两个像素的灰度值相比不是最大的，则认为不是边缘，并将该像素值置0;

4)边缘连接，设置高、低阈值.根据高低阈值判断出强、弱边缘点，在2值图像上标出强边缘点，并标出与强边缘点8连接的弱边缘点，得到边缘图像.利用形态学方法把2值化的边缘图像细化，得到源图像的边缘信息.

2 新算法的思路与步骤

影响配准结果的主要因素有噪声和亮度，在信噪比较低的情况下，如果在最佳匹配点噪声很大，利用以往的匹配准则(如MAD)，会使得MAD最小值不出现在最佳匹配点处，而出现在附近点，从而导致匹配结果不准确.

基于Canny算子对噪声有很好的抑制，本文的主要思路是利用Canny算子对参考帧进行2值化轮廓提取，并提出了一种新的匹配准则，降低了在配准过程中噪声对最佳匹配点选取的影响.

步骤如下:

Step1.在当前帧中选取特征块

首先用Canny算子提取图像的轮廓，这里使用的高斯滤波器为

并采用Sobel算子求平滑后图像的梯度，分别使用两个的卷积“掩模”来求得水平方向和和垂直方向的梯度.

得到当前帧的2值化图像后，利用差分算子计算出包含轮廓最多的小块，作为特征块;

Step2.对参考帧进行2值化处理

将参考帧中的像素值进行2值化处理，其中像素值大于等于2Q－1的置为1，小于2Q－1的置为0，Q为图像的位深;

Step3.搜索最佳匹配点

在参考帧的轮廓图像中搜索与当前特征块最为相似的匹配块，取当前块的中心作为参考帧的搜索起始点，取距起始点长度为64的8个点，按照下面的匹配准则计算这9个点的T值，找出T值最小的点，再以找出的点为中心，将步长减半，重复如上计算.依此过程，直至步长为1.

匹配准则如下:

其中:(k，l)为参考帧中待匹配点的坐标，f表示当前块的像素，g表示待匹配块的像素，M，N分别是特征块的行数和列数，Q为图像的位深.

该准则的优点在于，对于灰度值t大于2Q－1的像素点，若为正确的匹配点，T(k，l)=t－2Q+1，若为错误的匹配点，T'(k，l)=t，T'(k，l)≪T'(k，l).

3 实验结果

实验采用医学图像对基于特征的三步搜索块匹配法和本文的方法进行计算机模拟，其中，2种方法选取的特征块如图1、2所示.

图1 差分法选取的特征块

图2本文算法选取的特征块

图3 是在另一幅图像中选取的特征块，图4、5分别是在加入高斯噪声后利用两种方法所得到的匹配结果.

图5本方法在参考帧中搜索的匹配块

图1 、2表明，本文计算的特征块比差分法寻找的特征块包含的图像信息要多.图4、5显示，本文方法在加入高斯噪声的参考帧中可以准确找到最匹配特征块的小块，而基于MAD准则的三步搜索算法在横向上有偏差.因此，本文的方法在噪声较大的情况下，准确性高于基于MAD准则的三步搜索算法.

4 结语

本文提出了一种新的、有效的块匹配算法.先利用Canny算子提取当前帧的轮廓，并用差分算子找出包含轮廓最多的小块，即为特征块.然后对参考帧进行2值化处理，并将处理后的参考帧在新的匹配准则下与特征块进行配准.提取当前帧的轮廓再选取特征块，这使得选取的特征块包含的图像信息更多.而Canny算子的使用及对参考帧进行2值化处理降低了配准过程中噪声对最佳匹配点选取的影响.实验结果表明，在噪声较大的情况下，本文算法的准确性高于基于MAD准则的三步搜索算法.

[1]SEFERIDISV，GHANBARIM.General approach to block matching motion estimation[J].Optical Engineering，1993，32(7):1464－1474.

[2]VOS L D，STEGHEER M.Parameterizable VLSIarchitectures for the full－search block－matching algorithm[J].IEEE Trans on Circuits and Systems，1989，36(10):1309－1316.

[3]GHANBARIM.The Cross－Search Algorithm for Motion Estimation[J].IEEE Trans on Communications，1990，38(7):950－953.

[4]SRINIVASAN R，RAO K R.Predictive Coding Based on Efficient Motion Estimation[J].IEEE Trans on Communications，1985，COM－33:888－896.

[5]XU JB，PO L M，CHEUNG C K.Adaptive Motion Tracking Block Matching Algorithms for Video Coding[J].IEEE Trans on Circuits and System for Video Technology，1999，9(7):1025－1029.

[6]JOU JM，CHEN PY，SUN JM.The Gray Prediction Search Algorithm for Block Motion Estimation[J].IEEE Trans on Circuits and System for Video Technology，1999，9(6):843－848.

[7][美]冈萨雷斯.数字图像处理[M].北京:电子工业出版社，2003:152－153.