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

《郭涛算法在模板匹配中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、郭涛算法在模板匹配中的应用摘要：目前图像模板匹配算法一般都有计算量非常大的缺点,在实际运用中存在一定问题,根据这一问题提出了将演化算法应用到图像模板相关匹配中。模板匹配实际是寻找最优解的问题,将模板和子图像的互相关函数作为目标函数,基于演化的郭涛算法实现了模板匹配的最优解。最后根据实验说明了该算法较传统的遍历式模板匹配算法具有计算量大大减少的优越性。关键词：郭涛算法;模板匹配;张成子空间图1模板匹配原理用平方误差之和来衡量原图中的子图和模板之间的差别。假设模板的大小为x*y(宽*高);图像的大小为m@n。模板中的

2、某点坐标为(x,y),该点的灰度为t(x,y);与之重合的图像中的点坐标为(i+x,j+y),该点的灰度为s(i+x,j+y),在这里记做si,j(x,y)。则一次匹配的误差平方之和为d(i,j)=∑xx=1∑yy=1［si,j(x,y)-t(x,y)］2将该式展开:d(i,j)=∑xx=1∑yy=1［si,j(x,y)］2-2∑xx=1∑yy=1［si,j(x,y)×t(x,y)］+∑xx=1∑yy=1［t(x,y)］2(1)上式中，右边第一项称为原图像中与模板对应区域的能量,它与子图的位置有关,但是随子图位置

3、变化而缓慢变化。第二项称为模板与原图中子图的互相关，它随子图位置(i,j)的变化而变化，当模板t(x,y)和原图中子图区域相匹配时取得最大值。式中第三项称为模板的能量,它与图像像素位置(i,j)无关。只用一次计算即可。t与si,j匹配时这一项的取值最大,因此用这一项便可以进行图像匹配,可以用下列相关函数作相似性度量。但假设ds项为常数会产生误差,严重时无法完成匹配,因此将ds考虑在内,用下面的相关函数做相似性度量:归一化为r(i,j)=∑xx=1∑yy=1si,j(x,y)*t(x,y)∑xx=1∑yy=1［si

4、,j(x,y)］2∑xx=1∑yy=1［t(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)个参考点上做相关计算,除最佳匹配点外,其余做的都是无

5、效运算。2郭涛算法简介郭涛算法简单，计算效率高。它采用了演化计算中的群体搜索策略，保证了搜索空间的全局性，有利于搜索问题的解，可以有效地求解函数优化问题。其最主要的特点是采用了如下多父体杂交算子：以m个父体（向量）x=(x1,x2,…,xm)，所张成的子空间v={x

6、x=αx’}，作为搜索空间，其中α是m维向量，满足条件∑mi=1ai=1,-0.5≤ai≤1.5(3)该杂交算子采用随机空间中的随机搜索（多父体重组）策略,特别是子空间中随机搜索的非凸性：x=αx’，∑mi=1ai=1,-0.5≤ai≤1.5，使算法

7、搜索的子空间可覆盖多父体的凸组合空间，保证了随机搜索的遍历性，即解空间中不存在算法搜索不到的“死角”。其次，郭涛算法采用了“最劣个体淘汰策略”，每次把群体中适应性最差的个体淘汰出局，淘汰压力最小，即保证了群体的多样性，也保证了群体最后集体落入最深谷。求解极小化问题的郭涛算法如下所示，其中p是种群，t是演化代数，f为适应度函数，ε是误差。algorithmgt：begin初始化p={x1,x2,…,xn}，xi∈d；t=0；xbest=min1≤i≤nf(xi)xworst=max1≤i≤nf(xi)whileab

8、s(f(xbest)-f(xworst)){从p中随机选择m个点x’1，x’2，…，x’m形成子空间v;从v中随机选取一个点x’；iff(x′)

9、。该算法采用了劣汰策略,每次只把群体中适应性最差(目标函数值最大)的个体淘汰出局,淘汰压力最小,既保证了群体的多样性,也保证了适应性最好(目标函数值最小)的个体可保存下来。这种群体爬山策略,保证了整个群体最后集体达到最深的谷底。当最优解不惟一时,算法可能1次同时找到多个最优解。其次、初始化(initialize)是随机地从解空间d中选取n个点(个体)形成初始群体p，n的选