郭涛算法在模板匹配中的应用.doc

郭涛算法在模板匹配中的应用摘要：目前图像模板匹配算法一般都有计算量非常大的缺点,在实际运用中存在一定问题,根据这一问题提出了将演化算法应用到图像模板相关匹配中。模板匹配实际是寻找最优解的问题,将模板和子图像的互相关函数作为目标函数,基于演化的郭涛算法实现了模板匹配的最优解。最后根据实验说明了该算法较传统的遍历式模板匹配算法具有计算量大大减少的优越性。关键词：郭涛算法; 模板匹配; 张成子空间图1模板匹配原理用平方误差之和来衡量原图中的子图和模板之间的差别。假设模板的大小为x*y(宽*高);图像的大小为m n。模板中的某点坐标为(x ,y),该点的灰度为t(x,y);与之重合的图像中的点坐标为(i+x,j+y),该点的灰度为s(i+x ,j+y),在这里记做si,j( x,y)。则一次匹配的误差平方之和为d(i,j)=xx=1yy=1si,j(x,y)-t(x,y)2将该式展开:d(i,j)=xx=1yy=1si,j(x,y)2-2xx=1yy=1si,j(x,y)t(x,y)+xx=1yy=1t(x,y)2(1)上式中，右边第一项称为原图像中与模板对应区域的能量,它与子图的位置有关,但是随子图位置变化而缓慢变化。第二项称为模板与原图中子图的互相关，它随子图位置(i,j)的变化而变化，当模板t(x,y)和原图中子图区域相匹配时取得最大值。式中第三项称为模板的能量,它与图像像素位置(i,j)无关。只用一次计算即可。t与si,j匹配时这一项的取值最大, 因此用这一项便可以进行图像匹配,可以用下列相关函数作相似性度量。但假设ds项为常数会产生误差,严重时无法完成匹配,因此将ds考虑在内,用下面的相关函数做相似性度量:归一化为r(i,j)=xx=1yy=1si,j(x,y)*t(x,y)xx=1yy=1si,j(x,y)2xx=1yy=1t(x,y)2(2) 根据式（2）,对于任何一个r(i,j)都可算得一根据上式,对于任何一个r(i,j)都可算得一个值,当( i, j) 变化时,r(i,j)值的最大值便指出了与t 匹配得最佳位置, 取得匹配图像。可以看到模板匹配的运算量是惊人的。一次匹配都要做x*y次减法，x*y次平方, x*y-1 次加法,整个图像要匹配(m-x+1)*(n-y+1)次。用归一化互相关求匹配的计算量大的惊人,因为模板要在(m-j+1)*(n-k+1)个参考点上做相关计算,除最佳匹配点外,其余做的都是无效运算。2郭涛算法简介郭涛算法简单，计算效率高。它采用了演化计算中的群体搜索策略，保证了搜索空间的全局性，有利于搜索问题的解，可以有效地求解函数优化问题。其最主要的特点是采用了如下多父体杂交算子：以m个父体（向量）x=(x1,x2,xm) ，所张成的子空间v=x|x=x，作为搜索空间，其中是m维向量，满足条件mi=1ai=1,-0.5ai1.5(3)该杂交算子采用随机空间中的随机搜索（多父体重组）策略,特别是子空间中随机搜索的非凸性：x=x，mi=1ai=1,-0.5ai1.5，使算法搜索的子空间可覆盖多父体的凸组合空间，保证了随机搜索的遍历性，即解空间中不存在算法搜索不到的“死角”。其次，郭涛算法采用了“最劣个体淘汰策略”，每次把群体中适应性最差的个体淘汰出局，淘汰压力最小，即保证了群体的多样性，也保证了群体最后集体落入最深谷。求解极小化问题的郭涛算法如下所示，其中p是种群，t是演化代数，f为适应度函数，是误差。algorithm gt：begin初始化p=x1,x2,xn，xid ；t=0；xbest=min1inf(xi)xworst=max1inf(xi)while abs(f(xbest)-f(xworst)从p中随机选择m个点x1，x2，xm形成子空间v;从v中随机选取一个点x；if f(x)f(xworst) then xworst=x；t=t+1；xbest=min1inf(xi)xworst=max1inf(xi)输出t，p；end3郭涛算法在模板匹配的处理实现在具体实现中,我们采取以下几个步骤执行：首先、要根据具体匹配的图像类型选取匹配准则，从而计算出模板图像与子图像的相似度函数。郭涛算法采用了演化计算中的群体搜索策略,保证了搜索空间的全局性。该算法采用了劣汰策略,每次只把群体中适应性最差(目标函数值最大)的个体淘汰出局,淘汰压力最小,既保证了群体的多样性,也保证了适应性最好(目标函数值最小)的个体可保存下来。这种群体爬山策略,保证了整个群体最后集体达到最深的谷底。当最优解不惟一时,算法可能1次同时找到多个最优解。其次、初始化(initialize)是随机地从解空间d中选取n个点(个体)形成初始群体p，n的选取,可根据问题的维数n与f(x)场景的复杂性而定,当n较大且场景复杂时,n可取大些,反之,则取小些。一般取20n150，m的选取,根据经验取m =7、8、9或10较合适。再次、张成子空间的随机性很重要，这样做的目的是保证了解的多样性，以免漏掉最优解，陷入局部最优。同时在选取x时也是随机的，所以构造的这个人为随机函数也有讲究。最后、我们根据具体的精度要求设置停机条件，以及我们对最优解的解码。在这里我们用的是十进制数编码，通过演化出来的最优解。就可以找到与模板匹配的子图的左上角的坐标（x,y）。图2郭涛算法进行匹配搜索最优解的流程4结束语用matlab 编程实现了上述的算法和验证,图2用郭涛算法进行匹配搜索最优解的流程。以lena 图像为例，实验中取群体取值为50，迭代次数为2000，传统的穷举模板匹配搜索算法所用的时间是惊人的，在实际应用中有一定困难。文中采用郭涛算法实现模板匹配,该算法思想简单，算法效率高，能够在短时间内找到全局最优解。 通过实验可以看出,采用郭涛算法的模板匹配可以大大减少时间。进一步的研究应该集中在如何确定匹配准则，以提高该算法的匹配速度和精度。并且郭涛算法还可用于特征匹配最优解的搜索。参考文献：1郭涛，康立山，李艳.一种求解不等式约束下函数优化问题的新算法j.武汉大学学报(自然科学版)，1999（5b）.2郭涛.演化计算与优化d.武汉:武汉大学软件工程国家重点实验室，1999.3陈国良,王煦法,庄镇泉,等.遗传算法及其应用m.北京:人民邮电出版社,1996.4段玉倩,贺家李.遗传算法及其改进j.电力系统及其自动化学报,1998( 1) .5董建明,邹奉元,胡觉亮,等.基于自适应遗传互相关算法的模板匹配j.浙江理工大学学报,2006(1).6顾