基于改进遗传算法的图像匹配定位

傅超斌，南开来

(杭州电子科技大学 计算机学院，浙江 杭州 310018)

基于改进遗传算法的图像匹配定位

傅超斌，南开来

(杭州电子科技大学 计算机学院，浙江 杭州 310018)

为了提高彩色图形匹配效率，提出一种针对大图搜索匹配的改进遗传算法搜索策略。针对图像匹配问题的特点，以及根据遗传算法的优化策略，对其初始种群及交叉变异操作进行改进，从而加快图形匹配定位速度，提高其结果的可靠性。

遗传算法；优化策略；图像匹配定位

0 引言

遗传算法在边界搜索(Blind Search)、组合优化(Combine Optimization)、机器学习(Machine Learning)领域有不少的应用[1]。图像匹配是计算机视觉的一个关键技术，遗传算法搜索法是图像匹配中一种常用的搜索法，通过图像匹配可以快速确定待匹配大图像中是否有目标图像，若有则可同时确定其位置。

1 遗传算法的基本原理[2]

1.1 遗传算法概念

遗传算法(Genetic Algorithm，GA)是模拟生物进化过程的遗传选择和自然淘汰的计算模型，是由美国学者Holland于1975年首先提出[3]。其基本思想很简单：一个原始问题的参数被转换成一些基因编码，通常被表示为二进制染色体。初始的染色体个体都是随机生成的，然后根据一些标准来评判其个体的适应度。个体适应度的优劣决定了其染色体继续影响搜索的机会。适应度越优的个体也越有可能被选择作为创建下一代的一部分，通过不同个体间的随机信息交换，使得优秀个体不断被保留遗传，从而不断产生更优的染色体。后代继承了直系祖先的大部分基因信息，且整体优于祖先群体，进而使其种群不断往优发展。

1.2 理论基础

Holland提出的模式定理奠定了遗传算法的数学基础，其数学表达形式为：

(1)

积木块假设：由模式定理可看出，具有低阶、短定义矩以及平均适应度高于群体平均适应度的模式在子代中将以指数级增长。而通过短定义矩、低阶以及高平均适应度的模式，在遗传操作下接近全局最优解，即积木块假设。

1.3 基本遗传算法

基本的遗传算法根据问题选择编码方式，把参数集合域映射到位串空间；确定适应度函数；确定种群规模N、交叉概率Pc和变异概率Pm等算法参数。主要有以下几个步骤：(1)初始化随机生成的初始种群；(2)根据适应度函数，计算种群个体适应度；若已达最大迭代次数，则跳出结束遗传算法，否则继续执行；(3)执行轮盘赌选择操作；(4)根据交叉算子生成新的后代；(5)根据变异算子对新后代进行变异操作，然后重新执行步骤(2)。

图1 基本遗传算法流程图

算法流程图如图1所示。

2 算法应用[4-5]

2.1 匹配问题描述

假设搜索图为N×M像素的图像P和n×m像素的模板T，令Pij为以(i,j)为左顶点坐标的n×m像素的子图。图像匹配搜素即通过在待搜索图P中移动n×m像素的模板T寻找与T一致的子图Pij，可用类间方差来衡量其模板T和子图Pij之间的相似度判别函数：

(2)

采用归一化衡量相似度判别函数：

(3)

其中0≤Z(i,j)≤1，Z(i,j)越大表示其子图Pij与模板T的相似程度越高，当Z(i,j)=1时，Pij与T完全匹配。

2.2 优化改进策略

遗传算法的主要操作就是选择、交叉、变异，因此这三个步骤是主要优化的方向；同时，对于具体的问题，初始化种群的选择也是一个关键。

(1)优化初始种群：对于无先验知识的搜索匹配问题，基本遗传算法是采取完全随机生成初始种群，此方法得到的种群随机性太强，所拥有的最优信息少。本文针对模板目标快速定位的问题，采用离散间隔中心点法来提高搜索定位效率，即将初始点按照n×m像素的模板T大小作为最小间隔尺度生成种群个体，以增加可行域覆盖率。

(2)优化选择操作：对于大图搜索单一目标来说，在保持快速收敛的同时需要保证种群的多样性，因此在选择过程中，高于一定适应度阈值Th的个体可以直接选择保留加入交叉变异后代，低于一定适应度阈值Tl的个体直接淘汰。为了确保种群多样性，保持高于适应度阈值Th的较优个体不大于1/3种群规模，如果大于这个上限，将部分个体重置为随机生成的新个体。

(3)优化交叉操作：根据全图搜索的单目标稀疏性特点，将低于适应度阈值Tl的个体由1/5较优个体中某两条交叉生成，从而使其能够快速收敛，交叉段数为2段，交叉点位随机生成，增加交叉的可能性。

选择交叉方式示意图如图2所示。

图2 选择交叉操作示意图

(4)优化变异操作：根据全图搜索的规律，可知当适应度大于一定值时，很可能此个体已经在标准图附近，因此调整其变异区间，将其左顶点坐标(x,y)变异范围控制在x1-n≤x≤x1+n和y1-m≤y≤y1+m，其中(x1,y1)为当前个体左顶点坐标，从而提高变异的可靠性。当种群整体优于Th的比例大于2/3时，将其部分进行随机化变异，从而确保种群的多样性。

2.3 问题建模

首先，将N×M像素按照二进制编码分别将坐标(x,y)编码长度定为：lx=log2N+1和ly=log2M+1。其次，适应度函数使用归一化的类间方差Z(x,y)作为个体适应度评判标准，将模板图与实际个体图像素点的ARGB值作为计算类间方差的参数，从而实现对彩色图的匹配定位。最后，确定迭代次数Dt、交叉概率Pc和变异概率Pm。

3 实验示例及结果

本文实验采用的是仿真足球机器人界面的足球图形以及队员图形，示例使用黄底棕色三角形、粉底绿色倒三角形、灰底蓝色球分别表示A球队队员、B球队队员以及足球，以此来模拟标识一个足球机器人界面。用不同的颜色作为区别，后期采集到的图像根据此标准图片来进行分析快速定位，即图片快速匹配定位。

3.1 实验示例

图3所示是一个实验demo，测试软件界面可选择遗传算法的一些基本参数：迭代次数、交叉率、变异率、种群规模；根据下拉框的选择来确定需要寻找匹配的图片类型，其中当匹配定位到一张图片时，将其图片标记并显示GA搜索耗时，以及定位到的位置坐标点。示例中的输入坐标点代表的是待匹配定位图实际位置，找到的最优坐标代表的是实际匹配定位到的位置。

3.2 实验结果

在同样GA参数，迭代次数为500，交叉率0.8，变异率0.05，种群规模100代的情况下，得到的基本遗传算法和改进遗传算法的结果比较如表1。

图3 实验示例

算法实验次数单个平均匹配时间/s正确匹配次数匹配精度/%基本遗传算法505.12836.0改进遗传算法500.3624692.0

从实验结果可以看到，改进的遗传算法匹配定位效率明显要高于基本遗传算法。

4 结论

本文通过改进的遗传算法实现了快速图片匹配定位，根据遗传算法的特点，优化了初始种群选择策略、交叉策略以及变异策略，在快速收敛的同时保证了种群的多样性。实验示例结果表明，这些策略的改进有效地提高了其搜索效率，改善了其搜索的可靠性。

[1] ROOKER T. Review of genetic algorithms in search, optimization, and machine learning[J].AI Magazine, 1991, 12(1):102-103.

[2] 金希东.遗传算法及其应用[D].成都：西南交通大学,1996.

[3] HOLLAND J H.Adaptation in natural and artificial systems[D]. MIT Press, 1992.

[4] 朱红, 赵亦工. 基于遗传算法的快速图像相关匹配[J]. 红外与毫米波学报, 1999,2(2):145-150.

[5] 严国荣, 赵亦工. 基于改进的遗传算法的快速图像相关匹配技术[J]. 电讯技术, 2002, 42(5):96-99.

Image matching and location based on improved genetic algorithm

Fu Chaobin, Nan Kailai

(College of Computer, Hangzhou Dianzi University, Hangzhou 310018, China)

In order to improve the efficiency of color image matching, an improved genetic algorithm search strategy is proposed. According to the characteristics of the image matching problem, and according to the optimization strategy of genetic algorithm, the initial population and crossover and mutation operation are improved, thus to speed up the matching positioning speed and improve the reliability of the results.

genetic algorithm; optimization strategy; image matching and localization

TP391

A

10.19358/j.issn.1674- 7720.2017.23.013

傅超斌，南开来.基于改进遗传算法的图像匹配定位[J].微型机与应用，2017,36(23)：44-45,49.

2017-05-02)

傅超斌(1993-)，通信作者，男，硕士研究生，主要研究方向：LD-VHDL的并行编译。E-mail：610519112@qq.com。

南开来(1992-)，男，硕士研究生，主要研究方向：基于可编程逻辑阵列的图像处理。