一种基于遗传算法的影像匹配方法研究

维普资讯 http://www.cqvip.com 第２８卷第１期　２００８年１月　ＨＹＤＲＯＧＲ　Ａ咖海洋测绘　Ｖ０１．２８．Ｎｏ．１　Ｊａｎ．，２００８　Ｃ　ＳＵＲＶＥＹⅡ　Ｇ　ＡＮＤ　ＣＨＡＲＴⅡ　Ｇ　一种基于遗传算法的影像匹配方法研究　李　国　，巩丹超　，郭海涛　（１．解放军信息工程大学测绘学院，河南郑州４５００５２；２．６５０１５部队，辽宁大连１１６０２３）　摘要：影像匹配是计算机视觉及数字摄影测量的核心问题。基于遗传算法优良的全局寻优特点及影像匹配的　具体特点，将遗传算法引入到遥感影像的匹配定位中，针对基本遗传算法易提前收敛的特点，对基本遗传算法进行　了一定的自适应改进。实验结果表明这种方法可以产生一个快速而且可靠的匹配结果。　关键词：影像匹配；遗传算法；格雷码　中图分类号：ＴＰ３９１．４１　文献标识码：Ａ　文章编号：１６７１－３０４４（２００８）Ｏ１－００２２－０３　１　引　言　３．１　编码的实现　影像匹配的精度、速度和可靠性一直是人们　所关心的三大要素。在基于灰度的匹配算法中，　遗传算法是在遗传空间搜索最优解，而实验最　终目的却是在解空间寻找到最优解。影像匹配的目　标解就是同名像点在匹配图像上的行列坐标，在实　验中采用Ｇｒａｙ码对目标点的行坐标和列坐标进行　编码。　３．２适应度函数　随着具有摄影测量特色的最小二乘匹配理论和核　线相关理论的出现，人们把关注的焦点逐渐转移　到了匹配的可靠性及速度上。目前，在摄影测量　与计算机视觉界，大量的工作集中在基于有效搜　索方案的立体算法研究，而遗传算法是近些年来　在计算智能领域中，研究最为活跃、应用最为广泛　在基于灰度的影像匹配中，相关系数是应用最　广泛的匹配测度之一，相关系数在评价左右影像时　的相关性方面体现出了较高的优越性。由于相关系　的优化搜索算法。本文针对遗传算法优良的全局　数是标准化的协方差函数，即使当目标影像的灰度　与搜索影像的灰度之间存在线形畸变时，也能较好　的评价它们之间的相似程度　Ｊ，所以本文就以相关　寻优特点，将遗传算法引入到遥感影像的匹配定　位中。实验结果表明这种方法可以产生一个快速　而且可靠的匹配结果。　系数测度作为适应度函数。　３．３初始群体的产生　２遗传算法简介　遗传算法（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ，ＧＡ）是一类借　鉴生物界的进化规律（适者生存，优胜劣汰遗传机　制）演化而来的随机化搜索方法。遗传算法最早　由美国的Ｊ．Ｈ．Ｈｏｌｌａｎｄ教授提出，直到１９７５年　为了能用较少的群体和遗传代数尽可能快地找　到准最优解，本文所采用的初始群体的产生方法是　按一定的要求择优选择一定数量的初始种子。即首　先获取一定数量的种子，然后从这些种子中依其适　应度的优劣进行排序并挑选一定数量的初始群体。　步骤如下：　Ｈｏｌｌａｎｄ教授出版了第一本系统论述遗传算法和人　工自适应系统的专著《自然系统和人工系统的自　适应性》…。遗传算法将生物进化过程中适者生　存规则与染色体的随机性信息交换机制相结合，　（１）通过仿射变换确定匹配点的概略位置，并　以匹配点的概略位置为中心，建立搜索区域。　（２）以目标窗口大小将搜索区域分成若干子　区，分别在每一子区中选择其主对角线上的坐标点，　以保证初始种群均匀分布且遍布整个搜索区域，并　要求总点数不少于设定的初始群体大小。　同时从多个初始搜索点开始搜索，使用了多个搜　索点的搜索信息，与传统的优化算法相比具有更　好的全局寻优能力。　３遗传算法在影像匹配中的应用　（３）用适应度函数估计每个种子的适应度，依　收稿日期：２００７－０１－３１；修回日期：２００７－０９－０３　基金项目：解放军信息工程大学测绘学院第二届学员科技创新基金项目（Ｘ０６０８）。　作者简介：李国（１９８３－），男，吉林延边人，学员，主要从事数字摄影测量研究。　维普资讯 http://www.cqvip.com

维普资讯 http://www.cqvip.com 海表１　洋测绘　第２８卷　控制参数　初始种群个数　５０　最大值终止代数　２０　最大遗传代数　ｌ０ｏ　交叉概率　０．９５　变异概率初值　０，０ｌ　表２　匹配时间及适应度　ｌ　匹配时间（ｓ）　０，５３ｌ　２　０．４６９　３　０．７９７　４　０．５１６　５　０．８２８　６　０．６５６　７　１．６７ｌ　８　０．９２２　９　０．６５７　平均值　０，７８３　适应度　０．７３０９９　０．６３３　５３　０．９００　６４　０，５４９　３９　０．４７９６９　０．７６０４４　０．５９２７７　０．６５２０４　０．５９２　５０　０．６５４　６７　４．２实验结果分析　生学技术。近几年来，人们一直在探讨应当如何更　进一步利用遗传算法的全局选优的特性，在各自的　领域内进行更充分的应用。本文对基于遗传算法的　影像匹配技术进行了初步的研究，实验结果表明基　于遗传算法的匹配定位不仅可以满足定位精度要　１号点实验初期与实验后期的数据相比，初期　群体适应度的平均值偏高，最差个体适应度偏高，主　要原因是初始群体的选取是择优选取，使得初期的　群体适应度的平均值、最差个体适应度偏高。本文　对变异概率实行了一定的自适应策略，后期变异概　率相对较大，产生新个体的机会较大，最佳个体的适　应度发生较大的波动。　求，而且具有较高的匹配速率。下一步的工作，是对　交叉概率、变异概率采取一定的自适应策略，防止遗　传算法提前收敛，提高匹配速率，更快更好的寻找到　全局最优点。　实验中匹配窗口为３１×３１个像素，搜索窗口为　２５６×２５６个像素。匹配可靠性方面，１０个点中有９　个点匹配正确，１个匹配不正确；匹配时间方面，匹　配正确的９个点中最大时间是１．６７１　ｓ，其余均小于　１　ｓ，平均匹配时间为０．７８３ｓ。在匹配窗口和搜索窗　口大小相同的情况下相关系数法影像匹配的平均匹　配时间则为４．３２６３ｓ，实验结果表明这种方法可以　产生一个快速而且可靠的匹配结果。该算法具有较　高的匹配速率及一定的匹配可靠性，可以满足数量　级较大的卫星影像的使用。　５结论及展望　参考文献：　［１］周明，孙树栋．遗传算法原理及应用［Ｍ］，北京：国　防工业出版社，ｌ９９９．　［２］张祖勋，张剑清．数字摄影测量学［Ｍ］．武汉：武汉测　绘科技大学出版社，１９９７．　［３］熊兴华．改进遗传算法及其在影像匹配中的应用［Ｊ］．　测绘科学与工程，２００４，２４（２）：２２～２４．　［４］　郭海涛．基于卫星遥感影像的单片测图与修测技术研　究［Ｄ］．郑州：解放军信息工程大学测绘学院，２００２．　遗传算法是一门非常年轻且正在蓬勃发展的仿　Ｓｔｕｄｙ　ｏｎ　ｔｈｅ　Ｍｅｔｈｏｄ　ｏｆ　Ｉｍａｇｅ　Ｍａｔｃｈｉｎｇ　Ｂａｓｅｄ　ｏｎ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ　ＬＩ　Ｇｕｏ　，ＧＯＮＧ　Ｄａｎ—ｃｈａｏ　，ＧＵＯ　Ｈａｉ—ｔａｏ　（１．Ｉｎｓｉｔｔｕｔｅ　ｏｆ　Ｓｕｒｖｅｙｉｎｇ　ａｎｄ　Ｍａｐｐｉｎｇ，Ｉｎｆｏｒｍａｉｔｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ，Ｈｅｎａｎ，４５００５２；　２．６５０１５　Ｔｒｏｏｐｓ，Ｄａｌｉｎ，ａＬｉａｏｎｉｎｇ，１１６０２３）　Ａｂｓｔｒａｃｔ：Ｉｍａｇｅ　ｍａｔｃｈｉｎｇ　ｉｓ　ａ　ｋｅｒｎｅｌ　ｐｒｏｂｌｅｍ　ｉｎ　ｃｏｍｐｕｔｅｒ　ｖｉｓｉｏｎ　ａｎｄ　ｄｉｇｉｔａｌ　ｐｈｏｔｏｇｒａｍｍｅｔｒｙ．Ｂａｓｅｉｎｇ　ｏｎ　ｔｈｅ　ｅｘｃｅｌｌｅｎｔ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｏｆ　ｓｅｅｋｉｎｇ　ｆｏｒ　ｇｌｏｂａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｎｄ　ｓｐｅｃｉｆｉｃ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｏｆ　ｉｍａｇｅ　ｍａｔｃｈｉｎｇ，　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｉｎｔｒｏｄｕｃｅｄ　ｉｎ　ｔｈｅ　ｍａｔｃｈｉｎｇ　ａｎｄ　ｌｏｃａｔｉｏｎ　ｏｆ　ｓｅｎｓｏｒ　ｉｍａｇｅｓ．Ｔｈｅ　ｓｉｍｐｌｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ｔｅｎｄ　ｔｏ　ｇｅｔ　ｉｎｔｏ　ｐｒｅｍａｔｕｒｅ　ｃｏｎｖｅｒｇｅｎｃｅ，ＳＯ　ａｎ　ａｄａｐｔｉｖｅ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｒｅａｌｉｚｅｄ　ｉｎ　ｉｍａｇｅ　ｍａｔｃｈｉｎｇ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｍｅｔｈｏｄ　ｄｉｓｃｕｓｓｅｄ　Ｃａｎ　ｐｒｏｄｕｃｅ　ａ　ｆａｓｔ　ａｎｄ　ｒｅｌｉａｂｌｅ　ｍａｔｃｈｉｎｇ　ｒｅｓｕｌｔ．　Ｋｅｙ　ｗｏｒｄｓ：ｉｍａｇｅ　ｍａｔｃｈｉｎｇ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ；Ｇｒａｙ　ｃｏｄｅｓ