基于Fourier变换的模板匹配算法

论文总字数：7200字

目 录

1 引言…………………………………………………………………………2

2 基于互相关的模板匹配……………………………………………………3

3 基于Fourier变换的模板匹配……………………………………………3

3.1 卷积定理…………………………………………………………………………3

3.2 利用FFT实现模板匹配…………………………………………………………4

4 实验结果……………………………………………………………………5

4.1 实验一……………………………………………………………………………5

4.2 实验二……………………………………………………………………………7

4.3 实验三……………………………………………………………………………10

5 结论与思考…………………………………………………………………11

参考文献………………………………………………………………………12

基于Fourier变换的模板匹配

李成溪

摘要：本文研究基于Fourier变换的模板匹配问题。基于互相关的模板匹配通过最大化模板与图像之间的互相关来实现。本文根据卷积定理介绍了一种模板匹配算法，通过Fourier变换，将两个函数在时域中的卷积转化为在频域中的乘积，通过频域中的乘法运算来计算时域中的相关，从而实现模板匹配。实验结果表明，当图片的大小符合要求时，算法可以快速准确地识别模板的位置，并且当存在噪声时有一定的鲁棒性。

关键词：模板匹配；互相关；傅里叶变换；快速傅里叶变换；

引言

图像识别在生活、军事、航空航天等各个领域的作用越来越重要。例如，在我们的日常生活中风靡的美颜相机，就可以自动分辨出人的五官和皮肤，从而。针对各个部位进行不同的美化；在道路监控系统中，智能摄像头可以将超速的车辆牌照并直接从照片中“认出”车辆的车牌号等；在军事中，有一种导弹制导方式要不断对目标进行拍照，随后根据图像中目标的偏移来修正弹道等等。。。这些都要求机器能在图像中找到目标图像。而模板匹配就是在图像中寻找目标的主要方法之一。

近几十年来，模板匹配始终是人们研究的热点，最早是在70年代美国从事飞行器辅助导航系统等军事应用研究中提出来的。经历了10多年的发展，到80年代以后，其应用逐步从原来单纯的军事应用扩大到其它领域。作为图像信号处理中经常用到的技术，模板匹配已经应用到了很多工业生产应用中的检测和监控上了。

在现阶段，国内外对于模板匹配的研究主要是以提高匹配的精度和速度为主，同时对匹配方法的通用性及鲁棒性也有一定要求。主要分为基于图像灰度的匹配方法和基于图像特征的匹配方法。

基于灰度相关的图像匹配方法，主要处理不存在旋转的匹配对象，且已经提出了各种各样针对灰度匹配的方法，其中，有三个比较经典的算法，MAD算法 、SSDA贯相似性算法以及NCC归一化相关算法。

由于模板和目标之间存在的不仅仅是灰度的差异问题，缩放和旋转也经常是模板对比中存在的差异数据的来源，基于几何的匹配算法因而诞生。此类算法多种多样，与数学数量的变换息息相关，如傅里叶变换，直方图统计，K-L变换，图像距等等。

提高运算速度仍旧是研究者们研究的难点和重点，相对地，精确度方面已经有了保证，而提高实时性，是目前主要面临的问题。

本文第二部分介绍基于互相关的模板匹配，第三部分介绍基于Fourier变换的模板匹配，第四部分为实验结果，最后第五部分为结论以及思考。

1. 基于互相关的模板匹配

设模板为一个离散的函数Txy，其中x，y∈W，而图像为Ixy，模板匹配可以看成是确定最佳的位置使如下的目标函数最小化

将上式展开得

最后一项与模板位置（ij）有关，因此上式的最优化问题可以化为最小化下式

(1）

更进一步，如果第一项接近于常量，剩余项将给出一个图像和模板之间相似性的度量，从而可以通过最大化模板与图像之间的互相关

(2)

进行模板匹配，也就是说模板的匹配可以通过最大化互相关得到。

1. 基于Fourier变换的模板匹配
   1. 卷积定理^´

卷积定理是利用Fourier 变换进行模板匹配的关键。两个函数f和g的卷积“*”以如下方式定义

而函数f的Fourier变化以如下方式定义

则卷积定理可叙述为

(f*g)^=f^(ω)·g^(ω)

也就是说时域的卷积相当于频域中的乘积。考虑到快速Fourier变换（FFT）算法，模板匹配可以在频域中进行快速实现，也就是通过频域的乘法运算来计算时域中的相关。

两个函数f和g的相关定义为

因此上面的（2）可写为IT。

• 1. 利用FFT实现模板匹配

注意到（2）式的匹配过程是相关而不是卷积，因此需要把相关转化为卷积，将（2）式的相关改写为

这里=x i，=y j，而卷积的定义为

因此，为了实现频域的模板匹配，把相关作如下变换

(3)

这里，此时相关与卷积是等效的，也就是说需要把模板进行水平和垂直的翻转。

根据卷积定理，卷积在频域中相当于乘法，因此（3）式的计算可通过下式来实现

I

这里F表示傅里叶变换，表示逆傅里叶变换(IFFT)，鉴于FFT的计算优势，这种方法计算速度更快。

有两种实现：第一种方法通过翻转模板计算出，然后计算它的Fourier变换，即。第二种方法，计算变换F(T)，然后计算其复共轭

*

这里[]*表示变换数据的复共轭，也就是说

1. 实验结果

在实验中，为了检测算法对噪声时的稳定性以及当原图像中有多个相似模板区域时算法的匹配结果我们分别选用了一组一般情况下的图片、一组有噪声的模板图片和一组重复型图片进行了多组实验来检测算法，分析该算法的优点和缺点。

图1 算法运行界面

• 1. 实验一

第一组实验，首先在一幅较为简单的场景（图2）中，寻找两辆汽车。从图5和图8中可以看到两次实验结果的峰值图，图中峰值很明显。然后在一副较为复杂的道路图（图9）中进行了相同的实验，实验结果同第一次实验相同，峰值很明显。

图2 实验图像1 图3 模板1

图4 模板1的实验结果 图5 模板1实验结果的互相关峰值图

图6 模板2

图7 模板2的实验结果 图8 模板2实验结果的互相关峰值图

图9 实验图像2 图10 模板3

图11 模板3的实验结果 图12 模板3实验结果的互相关峰值图

图13 模板4

图14 模板4的实验结果 图15 模板4实验结果的互相关峰值图

• 1. 实验二

第二个实验，分别在无噪声、有高斯噪声和有椒盐噪声的情况下，进行了三组匹配测试。

从图18、图220和图22可以看出在三种情况下，算法均能成功定位模板。图16为没有噪声的模板的实验结果的互相关峰制图，峰值最为明显。

在高斯噪声模板的实验结果互相关峰值图（图21）中，由于高斯噪声的概率密度函数服从高斯分布（即正态分布），噪声的分布相对均匀，对算法在对模板进行傅里叶变换以及与原图像进行互相关运算时的影响也较为均匀，因此虽然峰值可见，但是整体较为模糊、不明显，当噪声情况更为严重时可能出现匹配结果的不准确。

而相较于高斯噪声，椒盐噪声是由图像传感器，传输信道，解码处理等产生的黑白相间的亮暗点噪声，往往由图像切割引起。因此椒盐噪声的随机性较强，分布不均匀，对于算法在对模板整体进行变换和计算时的影响较小。从椒盐噪声的实验结果互相关峰值图中（图23）可以看出，虽然相较于无噪声模板的峰值，椒盐噪声模板的峰值也存在模糊，弱化的问题，但是比高斯噪声要清晰得多，更接近于没有噪声的情况。

从整体情况看来，算法在模板存在一些常见的噪声的情况下，有一定的识别准确性，体现出一定的鲁棒性。

剩余内容已隐藏，请支付后下载全文，论文总字数：7200字

相关图片展示：