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