模板匹配MATLAB实现及算法优化一、引言现代社会已进入信息时代，随着计算机技术、通信技术和数学的发展，图像信息处理能力和水平也不断提高，相应的也得到和更多关注、研究和更加广泛的应用。

图像匹配是图像处理的一项关键技术，可广泛用于目标识别与跟踪、立体视觉、变化检测、车场车牌识别、人脸识别、机器人导航、测绘、等领域，已成为一门新兴的分支学科。

由于拍摄时间、拍摄角度、自然环境的变化、多种传感器的使用和传感器本身的缺陷，使拍摄的图像不仅受噪声的影响，而且存在严重的灰度失真和几何畸变。

在这种条件下，如何有效地进行图像匹配一直是人们研究的热点和难点。

要研究模板匹配，首先必须明确模板匹配的定义：模板匹配是指通过一定的匹配算法在两幅或多幅图像之间识别同名点，如二维图像匹配中通过比较目标区和搜索区中相同大小的窗口的相关系数，取搜索区中相关系数最大所对应的窗口中心点作为同名点。

其实质是在基元相似性的条件下，运用匹配准则的最佳搜索问题。

简单的讲就是，要判读一幅大图像中是否存在某种已知的图案，则以一幅与该图案有着相同尺寸和方向的小图像为模板，通过一定的算法可以在图中找到目标，确定其坐标位置。

那么如何实现模板与原图像的匹配呢？下面将结合一个具体例子说明模板匹配的实现过程。

二、问题描述及解决方法1.问题描述现有模板如下图：原图如下图：问题：如何在原图中找到模板所处的位置，并把该位置标记出来。

2.解决方法首先必须建立判断模板与原图相应位置相似程度的准则。

对于彩色图像，是基于图像的特征匹配；而灰度图像，则是基于相关函数。

本实验的处理对象主要是灰度图片。

相关函数又分成两类：（1） 差值测度。

计算公式如下：max |(,)(,)|f x y g x y ε=-|(,)(,)|Df x yg x y dxdy ε=-⎰⎰22[(,)(,)]Df x yg x y dxdy ε=-⎰⎰（2） 相关测度。

计算公式如下：1222(,)(,)(,)[(,)(,)]D D D f x y g x y dxdy p x y f x y dxdy g x y dxdy =⋅⎰⎰⎰⎰⎰⎰显然，上式中的p(x,y)取值范围是0到1。

越接近于0，表示两图像相差越大；越接近于1，表示两图像越相似。

有了描述相似程度的数学模型，接下来就可以用MATLAB 编程实现模板匹配，从而解决上述问题了。

三、 MATLAB 实现要实现这个程序，必须有三个重要组成部分：1. 模板循环功能：实现模板扫过原图的每一个像素点。

语句：for i=1:M-mfor j=1:N-nendend描述：以模板左上角第一个点为标志点，使其依次从左到右、从上到下扫过原图每一个像素点。

2. 相似性判断功能：在每一次循环时，计算模板与覆盖的原图区域的相似程度，并判断两图像是否相似。

语句：temp=imcrop(im,[j,i,n-1,m-1]);r=corr2(temp,T);%È¡µÃÏà¹ØϵÊýif r>0.95%¹æ¶¨ÖµÎª0.95end描述：（1）imcrop是MATLAB自带库函数，实现的是图像裁剪的功能，这里使用此函数，可以得到原图上被模板覆盖区域，与模板同尺寸的矩阵。

（2）corr2也是MATLAB自带库函数，是用来计算两个矩阵的相关测度的。

（3）0.95是置信阈值，当相关测度大于0.95时，就认为模板匹配成功。

3.标识原图上匹配成功的区域功能：用框圈出或高亮显示原图上与模板匹配成功的区域位置。

语句：plot(j:j+n,i,'w');plot(j:j+n,i+m,'w');plot(j,i:i+m,'w');plot(j+n,i:i+m,'w');描述：此语句实现用方框圈出匹配成功区域。

实验结果如图：四、算法优化模板匹配在实际应用中经常用于制导导引头、传感器等，这类设备计算能力、内存有限，且要求在较短时间内得到处理结果。

因此，以减少处理计算量、加快处理速度为目的的算法优化必不可少。

我个人将优化的方式分为三种：循环次数优化，具体有粗精匹配相结合、乱序匹配等；相似性计算优化，这是我们此次实验的着眼点，将做具体介绍；以及以上两种思路的结合优化。

通过上文列举的相似性计算准则可知，不同数学模型的计算量明显不同，而多种相似性计算公式的存在也为算法优化提供了可能。

1.差值测度优化思路：相比相关测度计算，差值测度只计算减法，所以在计算量上将大大降低。

语句：temp=imcrop(im,[j,i,n-1,m-1]);a=temp-T;b=abs(a);e=max(a);if e<50;end结果：未优化运行时间：T=3.9746s采用差值测度优化后运行时间：T=1.7524s2.TMP优化思路：TMP法首先认为原图与模板具有相同的直流分量，那么只要检测除直流分量能量外的能量水平，就可以判断相似性。

语句：Nimage=im(i:i+r2-1,j:j+c2-1);Nimage=Nimage-mean(mean(Nimage));corr=sum(sum(Nimage.*image22));M(i,j)=corr/sqrt(sum(sum(Nimage.^2)));结果：采用TMP优化算法后运行时间：T=1.5853s3.TMC优化思路：TMC法原理与TMP法相同，只是在计算时省略了归一化过程。

语句：Nimage=im(i:i+r2-1,j:j+c2-1);Nimage=Nimage-mean(mean(Nimage));corr=sum(sum(Nimage.*image22));corrMat(i,j)=corr;结果：采用TMC优化算法后运行时间：T=1.140s4.边缘检测优化思路：以上所有算法的处理对象都是模板及原图包含的所有信息，但是区别一个物体最直观的方式是区分他的轮廓，所以如果先提取原图与模板轮廓，然后再进行匹配计算，则在保证精度的基础上可以大大减少信息处理量。

语句：tedge = edge(tt);wedge = edge(ww);out = filter2(tedge,wedge);o = max(max(out));output = (1/o)*out;结果：采用边缘检测优化算法后运行时间：T=0.0964s结论：以上4种优化算法相比原未优化算法，在处理相同模板匹配问题的前提下，都显著提升了运行速度。

这几种算法中，边缘检测优化算法更具优势。

五、主要程序1.未优化原程序clcclearclose alltic;im=imread('D:\1120120260 ÕÔ´«\t-m\letters.jpg');%¶ÁÈ¡Ô-ͼÏñT=imread('D:\1120120260 ÕÔ´«\t-m\K.jpg');%¶ÁÈ¡Æ¥ÅäͼÏñimshow(im);im=rgb2gray(im);%½«Ô-ͼ»Ò¶È»¯T=rgb2gray(T);%½«Æ¥Åäͼ»Ò¶È»¯im=double(im);T=double(T);[m,n]=size(T);%»ñÈ¡Æ¥ÅäͼÏóµÄ´óС³ß[M,N]=size(im);%»ñÈ¡Ô-ͼÏóµÄ´óС³ß´çhold onfor i=1:M-mfor j=1:N-ntemp=imcrop(im,[j,i,n-1,m-1]);r=corr2(temp,T);%È¡µÃÏà¹ØϵÊýif r>0.95%¹æ¶¨ÖµÎª0.95%ÏÂÃæÓÃplotº¯ÊýÔÚÔ-ͼµÄ×ø±êϵÉÏ»-³öÆ¥ÅäÇøÓòplot(j:j+n,i,'w');plot(j:j+n,i+m,'w');plot(j,i:i+m,'w');plot(j+n,i:i+m,'w');endendendtime=toc;2.差值测度优化clcclearclose alltic;im=imread('D:\1120120260 ÕÔ´«\t-m\letters.jpg');%¶ÁÈ¡Ô-ͼÏñT=imread('D:\1120120260 ÕÔ´«\t-m\K.jpg');%¶ÁÈ¡Æ¥ÅäͼÏñimshow(im);im=rgb2gray(im);%½«Ô-ͼ»Ò¶È»¯T=rgb2gray(T);%½«Æ¥Åäͼ»Ò¶È»¯im=double(im);T=double(T);[m,n]=size(T);%»ñÈ¡Æ¥ÅäͼÏóµÄ´óС³ß[M,N]=size(im);%»ñÈ¡Ô-ͼÏóµÄ´óС³ß´çhold onfor i=1:M-mfor j=1:N-ntemp=imcrop(im,[j,i,n-1,m-1]);a=temp-T;b=abs(a);e=max(a);if e<50; %ÈÏΪ×î´óÎó²îСÓÚ50¼´Æ¥Åä³É¹¦%ÏÂÃæÓÃplotº¯ÊýÔÚÔ-ͼµÄ×ø±êϵÉÏ»-³öÆ¥ÅäÇøÓòplot(j:j+n,i,'w');plot(j:j+n,i+m,'w');plot(j,i:i+m,'w');plot(j+n,i:i+m,'w');endendendtime=toc;3. TMP优化clcclearclose alltic;im=imread('D:\1120120260 ÕÔ´«\t-m\letters.jpg');%¶ÁÈ¡Ô-ͼÏñT=imread('D:\1120120260 ÕÔ´«\t-m\K.jpg');%¶ÁÈ¡Æ¥ÅäͼÏñim=rgb2gray(im);%½«Ô-ͼ»Ò¶È»¯T=rgb2gray(T);%½«Æ¥Åäͼ»Ò¶È»¯im=double(im);T=double(T);[r1,c1]=size(im);[r2,c2]=size(T);image22=T-mean(mean(T));%»ùÓÚÄÜÁ¿·¨µÄÏà¹ØÐÔ¼ì²âM=[];for i=1:(r1-r2+1)for j=1:(c1-c2+1)Nimage=im(i:i+r2-1,j:j+c2-1);Nimage=Nimage-mean(mean(Nimage)); %ÓëÄ£°åÖغϲ¿·ÖÔ-ͼÏñµÄ¾ùÖµ²îcorr=sum(sum(Nimage.*image22));M(i,j)=corr/sqrt(sum(sum(Nimage.^2)));endend% plot box on the target imageresult=plotbox(im,T,M);imshow(uint8(result));title('Matching Result using tmp');% figure,% subplot(2,2,1),imshow(uint8(T));title('Template');% subplot(2,2,2),imshow(uint8(im));title('Target');% subplot(2,2,3),imshow(uint8(result));title('Matching Result using tmp');time=toc;4.TMC优化clcclearclose alltic;im=imread('D:\1120120260 ÕÔ´«\t-m\letters.jpg');%¶ÁÈ¡Ô-ͼÏñT=imread('D:\1120120260 ÕÔ´«\t-m\K.jpg');%¶ÁÈ¡Æ¥ÅäͼÏñim=rgb2gray(im);%½«Ô-ͼ»Ò¶È»¯T=rgb2gray(T);%½«Æ¥Åäͼ»Ò¶È»¯im=double(im);T=double(T);[r1,c1]=size(im);[r2,c2]=size(T);% Ä£°åµÄ¾ùÖµ²îimage22=T-mean(mean(T));corrMat=[];%»ùÓÚ¾ùÖµ²îµÄÏà¹ØÐÔ¼ìÑéfor i=1:(r1-r2+1)for j=1:(c1-c2+1)Nimage=im(i:i+r2-1,j:j+c2-1);Nimage=Nimage-mean(mean(Nimage)); % ÓëÄ£°åÖغϲ¿·ÖµÄͼÏñ¾ùÖµ²î corr=sum(sum(Nimage.*image22));corrMat(i,j)=corr;endend% plot box on the target imageresult=plotbox(im,T,corrMat);imshow(uint8(result));title('Matching Result using tmc');% figure,% subplot(2,2,1),imshow(uint8(T));title('Template');% subplot(2,2,2),imshow(uint8(im));title('Target');% subplot(2,2,3),imshow(uint8(result));title('Matching Result using tmc');time=toc;5.边缘检测优化clcclearclose alltic;%¶ÁÈëͼÏñSw = imread('D:\1120120260 ÕÔ´«\t-m\letters.jpg');w = im2double(w);sizw = size(w);% figure% imshow(w)% title('Input Image')%¶ÁÈëÄ£°åTt = imread('D:\1120120260 ÕÔ´«\t-m\K.jpg');t = im2double(t);sizt = size(t);% figure% imshow(t)% title('Target Image')ww = rgb2gray(w);tt = rgb2gray(t);%ÓÅ»¯-ÓñßÔµ½øÐÐÏà¹Ø¼ì²âtedge = edge(tt);wedge = edge(ww);%²ÉÓþí»ýÅжÏÏà¹ØÐÔ£¬ÈôÏàͬ£¬¾í»ý×î´óout = filter2(tedge,wedge);o = max(max(out));output = (1/o)*out;%ÕÒµ½Ä£°åλÖ㬲¢¸ßÁÁÏÔʾģ°åÇøÓòpixel = find(output == 1);pcolumn = fix(pixel / sizw(1));prow = mod(pixel,sizw(1));rdis = fix(sizt(1)/2);cdis = fix(sizt(2)/2);cmin = pcolumn - cdis;cmax = pcolumn + cdis;rmin = prow - rdis;rmax = prow + rdis;c = [cmin cmin cmax cmax];r = [rmin rmax rmax rmin];m = roipoly(ww,c,r);m = im2double(m);% figure,imshow(m);m = 0.5 * (m + 1);mask(:,:,1) = m;mask(:,:,2) = m;mask(:,:,3) = m;final = mask .* w;figureimshow(final)title('Result Image')time=toc;6.plotbox子程序function result=plotbox(im,T,M);[r1,c1]=size(im);[r2,c2]=size(T);[r,c]=max(M);[r3,c3]=max(max(M));i=c(c3);j=c3;result=im;for x=i:i+r2-1for y=jresult(x,y)=255;endendfor x=i:i+r2-1for y=j+c2-1result(x,y)=255;endendfor x=ifor y=j:j+c2-1result(x,y)=255;endendfor x=i+r2-1for y=j:j+c2-1result(x,y)=255;endend。