总第２８９期 ２０１３年第１１期 计算机与数字工程 Ｃｏｍｐｕｔｅｒ＆Ｄｉｇｉｔａｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏ１．４１ Ｎ Ｄ．１１ １８２３
基于遗传算法的图像匹配算法研究 李红梅 （广东白云学院计算机系广州 ５１０４５０） 摘要图像匹配算法的研究是模式识别学科研究的一个分支，针对图像匹配速度问题，论文提出一种改进的遗传算法的快速图像匹 配算法。该算法首先确定问题的参数空间，通过对参数空间编码和种群初始化得到待匹配的多个初始位置，然后利用模板图和当前搜素子 图的直方图信息，分别构建参考序列和比较序列，以两序列间的灰色关联度为适应度函数 通过改进的遗传算子实现遗传操作，对遗传个体 进行迭代寻优，找出图像中的最佳匹配点。实验结果表明，基于该算法的图像匹配具有运算量小、匹配精确等优点，实时性得到了明显的提 高。 关键词遗传算法；图像匹配；适应度函数；多父体杂交 中图分类号ＴＰ３０１．６ ＤＯＩ：１０．３９６９￣．ｉｓｓｎ１６７２－９７２２．２０１３．１１．０３４ Ｉｍａｇｅ Ｍａｔｃｈｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ＬＩ Ｈｏｎｇｍｅｉ （Ｃｏｍｐｕｔｅｒ Ｄｅｐａｒｔｍｅｎｔ，Ｇｕａｎｇｄｏｎｇ Ｂａｉｙｕｎ Ｃｏｌｌｅｇｅ，Ｇｕａｎｇｚｈｏｕ ５１０４５０） Ａｂｓｔｒａｃｔ Ｔｈｅ ｓｔｕｄｙ ｏｆ ｉｍａｇｅ ｒｅｇｉｓｔｒａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｂｒａｎｃｈｅｓ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ．Ａｉｍ ａｔ ｔｈｅ ｐｒｏｂｌｅｍｓ ｏｎ ｉｍａｇｅ ｍａｔｃｈｉｎｇ ｆｏｒ ｓｌｏｗ ｓｐｅｅｄ，ａｎ ｉｍａｇｅ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ａ ｎｅｗ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ．Ｉｎ ｔｈｅ ｍｅｔｈｏｄ，ｍａｔｃｈｉｎｇ ｐａｒａｍｅ— ｔｅｒ ｓｐａｃｅ ｉｓ ｄｅｔｅｒｍｉｎｅｄ ａｎｄ ｓｅｖｅｒａｌ ｐｏｓｉｔｉｏｎｓ ａｒｅ ａｃｑｕｌｒｅｄ ｂｙ ｔｈｅ ｉｎｉｔｉａｌｉｚａｔｉｏｎ ｏｆ ｔｈｅ ｃｈｒｏｍｏｓｏｍｅｓ ｆｉｒｓｔ．Ｓｅｃｏｎｄｌｙ，ａ ｒｅｆｅｒｅｎｔｉａｌ ｓｅｑｕｅｎｃｅ ａｎｄ ａ ｃｏｍｐａｒａｔｉｖｅ ｓｅｑｕｅｎｃｅ ａｒｅ ｓｅｐａｒａｔｅｌｙ ｃｏｎｓｔｒｕｃｔｅｄ ｂｙ ｔｈｅ ｈｉｓｔｏｇｒａｍ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｔｈｅ ｔｅｍｐｌａｔｅ ｉｍａｇｅ ａｎｄ ｔｈｅ ｃｕｒｒｅｎｔ ｓｅａｒｃｈｉｎｇ ｓｕｂｉｍａｇｅ． Ａｎｄ ｔｈｅｎ，ｔａｋｉｎｇ ｔｈｅ ｇｒｅｙ ｒｅｌａｔｉｏｎａｌ ｄｅｇｒｅｅ ｂｅｔｗｅｅｎ ｔｈｅ ｔＷＯ ｓｅｑｕｅｎｃｅｓ ａｓ ｔｈｅ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ，ｍｏｓｔ ｏｆ ｔｈｅ ｃｈｒｏｍｏｓｏｍｅｓ ｃｏｎｃｕｒｒｅｎｔｌｙ ａｐ— ｐｒｏａｃｈ ｔｏ ｔｈｅ ｍａｔｃｈｉｎｇ ｐｏｓｉｔｉｏｎ ｔｈｒｏｕｇ ｔｈｅ ｎｅｗ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａ１ ｒｅｓｕｌｔｓ ｉｎｉｃａｔｅ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｎｏｔ ｏｎｌｙ ｏｂｔａｉｎｓ ｐｒｅｃｉｓｅ ｐｏｓｉｔｉｏｎｓ，ｂｕｔ ａｌｓｅ ｏｂｖｉｏｕｓｌｙ ｉｎｃｒｅａｓｅｓ ｔｈｅ ｍａｔｃｈｉｎｇ ｓｐｅｅｄ． Ｋａｙ Ｗｏｒｄｓ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ｉｍａｇｅ ｍａｔｃｈｉｎｇ，ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ，ｍｕｌｔｉ—ｐａｒｅｎｔ ｃｒｏｓｓｏｖｅｒ ＣｌａｓｓＮｕｎｑ￣ｙ ＴＰ３０１．６ １ 引言 图像匹配是图像处理中一个重要的课题，在计算机视 觉、运动目标跟踪与识别、序列图像压缩中运动补偿、医学 图像处理等领域有广阔的应用前景。在对图像的理解中， 匹配技术起着重要的作用。对于图像匹配算法目前主要可 以分为两大类：基于图像全局灰度值的匹配算法和基于图 像局部特征的匹配算法。 图像匹配＿】］是指在待匹配的大图像中判断是否存在模 板图像，以及确定模板图像在待匹配图像中的位置。根据 匹配原理，基于图像全局灰度值匹配算法［４］以图像间灰度 信息的相关性作为匹配判决准则，该类方法实现简单，但速 度较慢；基于图像局部特征的匹配算法的总体思路是首先 对图像的特征进行定义和提取，并以之作为相似性判决准 则，优点是匹配精度高，但只适用于具有典型特征且易于提 取的图像。 遗传算法的思想＿２］是从代表问题可能潜在解集的一个 种群开始的，而一个种群则由经过基因编码的一定数目的 个体组成。每个个体实际上是染色体带有特征的实体。染
收稿日期：２０１３年５月４日，修回日期：２０１３年６月２９日 作者简介：李红梅，女，硕士研究生，讲师，研究方向：演化计算。 色体作为遗传物质的主要载体，即多个基因的集合，其内部 表现是某种基因组合，它决定了个体的性状的外部表现。 因此，在一开始需要实现从表现型到基因型的映像即编码 工作。初代种群产生之后，按照适者生存和优胜劣汰的原 理，逐代演化产生出越来越好的近似解。在每一代，根据问 题中个体的适应度大小挑选个体，并借助于自然遗传学的 遗传算子进行组合交叉和变异，产生出代表新的解集的种 群。这个过程将导致种群像自然进化一样的后生代种群比 前代更加适应于环境，末代种群中的最优个体经过解码，可 以作为问题近似最优解。遗传算法不同于传统的搜索和优 化方法，其主要的特点在于：自组织、自适应和自学习性。 应用遗传算法求解问题时，在编码方案、适应度函数及遗传 算子确定后，算法将利用进化过程中获得的信息自行组织 搜索。 本文针对图像匹配速度问题，将图像全局灰度值和遗 传算法结合，提出一种基于遗传算法的快速图像匹配算法， 增强了算法的快速性和全局收敛性能。该算法首先确定问 题的参数空间，通过对参数空间编码和种群初始化得到待 匹配的多个初始位置，
然后利用模板图和当前搜素子图的 ２０１３年第１１期 计算机与数字工程 １８２５ ４结语 本文以提高图像匹配算法的速度为目的，提出了基于 改进的遗传算法的快速图像匹配方，初步实验结果显示该 方法在实时性方面具有较好的性能，该方法将模板图像与 待匹配图像中子图的直方图信息之间的关联度作为遗传算 法的适应度函数，大大节省了运算时间，同时，提出一种改 进的遗传算法，利用遗传算法并行匹配 多个搜索位置， 实时性得到了进一步的提高。 参考文献 ［１］章毓晋．图像理解与计算机视觉［Ｍ］．北京：清华大学出版社， ２０００：１０—１５． ＺＨＡＮＧ Ｙｕｊｉｎ．Ｉｍａｇｅ ｕｎｄｅｒｓｔａｎｄｉｎｇ ａｎｄ ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ Ｉ－Ｍ］．Ｂｅｉｊｉｎｇ：Ｔｓｉｎｇｈｕａ Ｕｎｉｖｅｒｓｉｔｙ ｐｒｅｓｓ，２０００：１０—１５． ［２］李敏强．遗传算法的基本理论与应用［Ｍ］．北京：科学出版社， ２００２：２０—２５． ＬＩ Ｍｉｎｑｉａｔ￣．Ｂａｓｉｃ ｔｈｅｏｒｙ ａｎｄ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｓｃｉｅｎｃｅ Ｐｒｅｓｓ，２００２：２０—２５． ［３］马苗，田红朋，张艳宁．灰色理论在图像工程中的应用研究进展 ［Ｊ］．中国图像图形学报，２００７，１２（１１）：１９４３—１９５１． ＭＡ Ｍｉａｏ，ＴＩＡＮ Ｈｏｎｇｐｅｎｇ，ＺＨＡＮＧ Ｙａｎｎｉｎｇ．Ｒｅｓｅａｒｃｈ ｐｒｏｇｒｅｓｓ ｏｎ Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ｇｒｅｙ Ｔｈｅｏｒｙ ｉｎ ｉｍａｇｅ ｅｎｇｉｎｅｅｒｉｎｇ ［Ｊ］．Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ ｉｍａｇｅ ａｎｄ ｇｒａｐｈｉｃｓ，２００７，１２（１１）： １９４３—１９５１． ［４］李强，张钹．一种基于图像灰度的快速匹配算法［Ｊ］．软件学报， ２００６，１７（２）：２１６—２２２． ＬＩ Ｑｉａｎｇ，ＺＨＡＮＧ １３ｏ．Ａ ｆａｓｔ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｉｍａｇｅ ｇｒａｙ ｖａｌｕｅ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ ｓｏｆｔｗａｒｅ，２００６，１７（２）：２１６— ２２２． ［５］云庆夏，黄光球，王战权．遗传算法和遗传规划［Ｍ］．北京：冶金 工业出版社，１９９７：３Ｏ一４０． ＹＵＮ Ｑｉｎｇｘｉａ，ＨＵＡＮＧ Ｇｕａｎｇｑｉｕ，ＷＡＮＧ Ｚｈａｎｑｕａ￣Ｏｅｎｅｔ— ｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｇｅｎｅｔｉｃ ｐｒｏｇｒａｍｍｉｎｇ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｍｅｔａｌｌｕｒ— ｇｉｃａｌ Ｉｎｄｕｓｔｒｙ Ｐｒｅｓｓ，１９９７：３Ｏ一４０． ［６］赵艳林，韦树英，梅占馨．灰色欧几里德关联度［Ｊ］．广西大学学 报（自然科学版），１９９８（３）：１０—１３． ＺＨＡ０ Ｙａｎｌｉｎ，ＷＥＩ Ｓｈｕｙｉｎｇ，ＭＥＩ ＺｈａｎｘｉｒＬ Ｇｒｅｙ Ｅｕｃｌｉｄ ｒｅｌａ— ｔｉｏｎａｌ ｄｅｇｒｅｅ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｇｕａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ（ＮＡＴＵＲＡＬ ＳＣＩＥＮＣＥ ＥＤＩＴＩＯＮ），１９９８（３）：１０－１３． ［７］李红梅．基于约束强度的演化算法［Ｊ］．计算机工程与设计， ２００９，４（２８）：６２４３—６２４６． ＬＩ Ｈｏｎｇｍｅｉ．Ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｃｏｎｓｔｒａｉｎｅｄ ｓｉｎｇｌｅ－ｏｂ— ｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ｄｅｓｉｇｎ， ２００９，４（２８）：６２４３—６２４６． ［８］阮沈勇，王永利，桑群芳．ＭＡＴＬＡＢ程序设计［Ｍ］．北京：电子 工业出版社，２００２：２０—６０． ＲＵＡＮ Ｓｈｅｎｙｏｎｇ，ＷＡＮＧ Ｙｏｎｇｌｉ，ＳＡＮＧ Ｑｕｎｆａｎｇ．ＭＡＴ— ＬＡＢ ｐｒｏｇｒａｍ ｄｅｓｉｇｎ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｐｕｂｌｉｓｈｉｎｇ Ｈｏｕｓｅ ｏｆ ｅｌｅｃ— ｔｒｏｎｉｃｓ ｉｎｄｕｓｔｒｙ，２００２：２０—６０． ［９］郑军，诸静．基于自适用遗传算法的图像匹配［Ｊ］．浙江大学学 报（工学版），２００３，３７（６）：６８９—６９２． ＺＨＥＮＧ Ｊｕｎ，ＺＨＵ Ｊｉｎｇ．Ｉｍａｇｅ ｍａｔｃｈｉｎｇ ｂａｓｅｄ ｏｎ ａｄａｐｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｚｈ￣ｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ（Ｅｎｇｉ— ｎｅｅｒｉｎｇ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｅｄｉｔｉｏｎ），２００３，３７（６）：６８９—６９２． ［１Ｏ］周明，孙树栋．遗传算法原理及应用［Ｍ］．长沙：国防工业出版 社，１９９９：３０—４５． ＺＨＯＵ Ｍｉｎｇ，ＳＵＮ Ｓｈｕｄｏｎｇ．Ｔｈｅ ｐｒｉｎｃｉｐｌｅ ａｎｄ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ［Ｍ］．Ｃｈａｎｇｓｈａ：Ｎａｔｉｏｎａｌ Ｄｅｆｅｎｅｅ Ｉｎｄｕｓｔｒｙ Ｐｒｅｓｓ，１９９９：３０—４５．
（上接第１８１６页） ［５］陈胜勇，刘盛．基于ＯｐｅｎＣＶ的计算机视觉技术实现［Ｍ］．北 京：科学出版社，２００８：３６４－３８９． ＣＨＥＮ Ｓｈｅｎｇｙｏｎｇ，ＬＩＵ Ｓｈｅｎｇ．Ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ ｔｅｃｈｎｏｌｏｇｙ ｂａｓｅｄ ｏｎ ｔｈｅ ＯｐｅｎＣＶ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｓｃｉｅｎｃｅ Ｐｒｅｓｓ，２００８：３６４— ３８９． ［６］Ｙｕｒｉ Ｍ Ｂａｙａｋｏｖｓｋｉ Ｐｈ．ｎ Ｇｒａｐｈｉｃｓ ａｎｄ Ｍｅｄｉａ Ｌａｂ［ＥＢ／ ＯＬ］．ｈｔｔｐ：／／ｒｅｓｅａｒｃｈ．ｇｒａｐｈｉｃｏｎ．ｒｕ／ｃａｌｉｂｒａｔｉｏｎ／２．ｈｔｍｌ，２００９一 Ｏ９． ［７３ Ｚｈａｎｇ ｚ Ｙ．Ａ Ｆｌｅｘｉｂｌｅ Ｎｅｗ Ｔｅｃｈｎｉｑｕｅ ｆｏｒ Ｃａｍｅｒａ Ｃａｌｉｂｒａｔｉｏｎ ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎ— ｔｅｌｌｉｇｅｎｃｅ，２０００，２２（１１）：１３３０—１３３４． ［８］毛剑飞，邹细勇．改进的平面模板两步法标定摄像机［Ｊ］．中国 图象图形学报，２００４，９（７）：８４６—８５３． ＭＡＯ Ｊｉａｎｆｅｉ，ＺＯＵ Ｘｉｙｏｎｇ．Ｉｍｐｒｏｖｅｄ ｔｗｏ－ｓｔｅｐ ｃａｌｉｂｒａｔｉｏｎ ｃａｍｅｒａ ｐｌａｎｅ ｔｅｍｐｌａｔｅ［Ｊ］．Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｉｍａｇｅ ａｎｄ Ｇｒａｐｈｉｃｓ，２００４，９（７）：８４６—８５３． ［９１ Ｄａｐｅｎｇ Ｇａｏ，Ｆｕｌｉａｎｇ Ｙｉｎ．Ｃｏｍｐｕｔｉｎｇ ａ ｃｏｍｐｌｅｔｅ ｃａｍｅｒａ ｌｅｎｓ ｄｉｓｔｏｒｔｉｏｎ ｍｏｄｅｌ ｂｙ ｐｌａｎａｒ ｈｏｍｏｇｒａｐｈｙ［Ｊ］．Ｏｐｔｉｃｓ＆Ｌａｓｅｒ Ｔｅｃｈｎｏｌｏｇｙ，２０１３（４９）：９５—１０７． ［１ｏ］尹文生，罗瑜林．基于ＯｐｅｎＣＶ的摄像机标定［Ｊ］．计算机工程 与设计，２００７（２８）：１９７—１９９． ＹＩＮ Ｗｅｎｓｈｅｎｇ，ＬＵＯ Ｙｕｌｉｎ．Ｃａｍｅｒａ ｃａｌｉｂｒａｔｉｏｎ ｂａｓｅｄ ｏｎ ＯｐｅｎＣＶ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｄｅｓｉｇｎ，２００７（２８）： １９７—１９９． Ｉｎ］Ａｌｅｘａｎｄｅｒ Ｖｅｌｉｚｈｅｖ．ＧＭＬ ｃａｍｅｒａ ｃａｌｉｂｒａｔｅ ｔｏｏｌｂｏｘ Ｉ ＥＢ｝ ＯＬ］．ｈｔｔｐ：／／ｇｒａｐｈｉｃｓ．ｃｓ．ｍｓｕ．ｒｕ／２０１１，１２． ［１２］Ｊｅａｎ－Ｙｖｅｓ Ｂｏｕｇｕｅｔ．Ｃａｍｅｒａ ｃａｌｉｂｒａｔｉｏｎ ｔｏｏｌｂｏｘ ｆｏｒ ｍａｔｌａｂ ［ＥＢ／ＯＬ］．ｈｔｔｐ ？ｆ Ｈ ．ｖｉｓｉｏｎ．ｃａｈｅｃｈ．ｅｄｕ／．２０１１，１２．
