一种模板匹配的改进算法

张天飞，龙海燕，丁 娇，张 磊

（安徽信息工程学院，安徽 芜湖 241000）

1 引言

模板匹配理论是按照相关策略，根据已知模块在搜索图像中寻找逼近模块匹配的过程，是一种简单有效、使用广泛的图像处理方法[1-3].模板匹配主要通过模板按照一定的准则在待匹配图像中寻找出相似性最大的对象，使用的准则有很多，例如平方差、相关、相关系数、归一化平方差、归一化相关、归一化相关系数等.为了使运算过程既简单又快速，本文使用归一化平方差作为模板匹配的相似性度量.

2 模板匹配原理

本文模板匹配采用将模板在待匹配图中按照从左到右、从上到下的原则扫描待匹配图，在扫描过程中用归一化平方差准则计算两者的匹配度，以确定是否有最适合的对象.模板和待匹配图像可以直接进行归一化平方差运算，但是这样可能会使得一些不必要的特征如灰度信息等让运算结果出现偏差甚至是出现错误匹配.而边缘检测既能减少待匹配图像的部分干扰信息，又能保留图像中物体的形状信息，所以在做归一化平方差之前，我们需要对模板和待匹配图做一定的边缘检测.

图1 待匹配图

图2 模板

3 归一化平方差

为使计算的数据在一定的范围内变化以及使计算值能够快速收敛到想要的结果，本文使用归一化平方差作为模板匹配的准则，下面首先简单介绍一下归一化平方差.平方差能够描述两个像素点p1、p2的相似性，如果像素点p1、p2完全相同，那么平方差值为0；如果像素点p1、p2差别越大，平方差值就越大.对于二维图像，如果两个图像块的平方差的和越小，那么表示这两个图像块越接近；当结果为零时，可以认为两图像块完全相同.本文采用的归一化平方差如式（1）所示：

通过该式能够看出，归一化平方差值越小，表示待匹配的图像与模板越相近.

4 边缘检测

使用模板匹配时，我们可以不对模板和待匹配图像进行处理而直接进行匹配，这样在一些情况下可以正确匹配，而在其他一些情况下会由于光照等条件的影响使得目标不能正确匹配，其鲁棒性不好.所以我们常常需要对模板和待匹配图像做进一步的处理.由于边缘是位置的标志，对灰度的变化不敏感，因此，边缘可以作为图像匹配的一个重要特征.在实时图像处理中，使用Sobel算子对图像进行边缘检测是常用的算法之一[4-5].Sobel算子是一种一阶差分的边缘检测算子，其计算简单，能够提供目标相对准确的边缘信息，在实际计算中我们使用5x5的模板与图像做卷积运算，就可得到边缘检测图像.5x5的Sobel算子x、y方向的模板如下表所示.

表1 Sobel x方向模板

表2 Sobel y方向模板

将模板x方向的Sobel运算结果与待匹配图像x方向的Sobel运算结果运用归一化平方差的方法，得到结果Gx(i,j)，其中|Gx(i,j)|中的值越小的点，其相似性就越大，同理将模板y方向的Sobel运算结果与待匹配图像y方向的Sobel运用归一化平方差方法，得到结果为Gy(i,j)，其中|Gy(i,j)|中的值越小的点，其相似性同样越大.我们既要考虑x方向的边缘，也要考虑y方向的边缘，所以最终匹配结果值用式（2）表示：

只要找到G(i,j)中的最小值，即MIN(G(i,j))，就是待匹配图中与模板最匹配的目标位置.此方法一定程度上可以减少模板与待匹配图像中的噪声、灰度变换的影响，寻找的位置相对准确.能够适用一些情况，但是当图像中含有高频信息的噪声时，则可能导致匹配的失败.为了解决此问题，我们需要对模板和待匹配图像做进一步优化.

5 优化模板和待匹配图像

由于待匹配图中可能含有高频噪声，经过Sobel算子进行边缘检测后并不能将其去除掉，所以需要进一步的处理.本文提出对经过Sobel算子边缘检测后的图像进一步作阈值化处理，如式（3）（4）所示：

其中，Gx(i,j)、Gy(i,j)分别为 x、y方向 Sobel算子，Th为所用阈值.

将经过Sobel算子边缘检测后的待匹配图像按照式（3）（4）进行处理得到 Gx'、Gy'，然后将 Gx'、Gy'分别代入归一化平方差公式（即式（1））进行匹配，综合考虑 x、y方向的边缘检测将 Gx'、Gy'代入式（2）得到G'，然后寻找G’中的最小值处的位置，就是与模板最相近的目标.本方法可以有效地抑制噪声中的高频部分，使得匹配的稳定性及可靠性增强.

6 实验分析

本文设计的实验是在连续的图像序列中进行匹配，图像大小为640x480，实验软件环境是在win7系统、VS2013平台，实验的硬件环境是Intel(R)Core(TM)2 Duo CPU T6570，内存 2G.在不同环境中测试物体跟踪效果得到实验数据.

实验一：在室内分别用经过Sobel算子边缘检测处理后的图像与本文对其改进的优化算法实现对水杯的跟踪，实验分别在图像序列的第10帧，第50帧，第120帧，第121帧进行截图，从图中可以看出Sobel边缘检测处理的图像进行匹配时，在第121帧时出现误匹配而本文的改进方法可以进行正确跟踪.

图3 10帧匹配结果

图4 30帧匹配结果

图5 120帧匹配结果

图6 121帧匹配结果

实验二：在室内分别用经过Sobel边缘检测处理后的图像与本文对其的优化算法实现对化妆品盒子的跟踪，实验分别在图像序列的第180帧，第210帧，第330帧，第343帧进行截图，从图中可以看出Sobel边缘检测处理的图像进行匹配时，在第343帧时出现误匹配而本文的改进方法可以进行正确跟踪.

图7 180帧匹配结果

图8 210帧匹配结果

图9 330帧匹配结果

图10 343帧匹配结果

7 结论

本文提出的阈值化Sobel边缘检测后的模板与待匹配图像的方法，能够有效地实现对物体的正确匹配，并且具有一定的鲁棒性，能够较好地实现实时跟踪.