遗传算法对图像模板匹配的优化

刘德华 呼家龙

（马鞍山职业技术学院，安徽 马鞍山 243000）

遗传算法对图像模板匹配的优化

刘德华 呼家龙

（马鞍山职业技术学院，安徽 马鞍山 243000）

本文分析了常见标志物的特征模板匹配过程，并通过遗传算法对十字丝匹配进行优化，在给定参数下，绘制了平均适应度和最大适应度曲线。通过固定代数和不固定代数情况下的实验，分析匹配结果值，得出遗传算法对模板匹配有极强的全局寻优能力，能够大大减少匹配计算量。

图像处理；模板匹配；遗传算法

图像模板匹配在图像处理的研究中是一个很重要的研究方向，在机器识别的过程中，常需要把不同传感器在不同时间，不同成像条件下对同一景物获取的两幅或是多幅图像在空间上对准，或是根据己知的模式到另一幅图找到相应的模式，这就需要用到图像匹配。图像匹配就是将模板与待检测的图像进行比较匹配，并给出一个描述匹配程度的计算结果。如果算法的运算结果显示图像中的某一部分与模板相同或是相似性大于设定的阈值，则认为匹配成功[1][2]。

1 常见标志物模板匹配方法

1.1 标志物选择

研究特定目标运动时，常在目标的某些位置贴上特定的识别标志，其中最简单的标志是圆标志和十字丝标志，如图1所示。然后根据目标的已知特征，建立相应的数学模型，最后用模式识别方法对目标特征进行提取和匹配。这种方法称为模式识别匹配跟踪法。其主要优点是：可靠性较高，受背景环境干扰小，计算量小等[3]。

图1 标志物

1.2 圆标志的识别定位法

以下是一种对圆标志识别定位算法的主要步骤：

1.2.1 对图像进行预处理，如滤除噪声，线性增强；

1.2.2 对圆标志进行二值化或提取边缘，得到图像中可能目标的特征，如区域的面积S和周长L；

1.2.3 根据得到的目标特征对目标进行模式识别，并用亚像素方法定位。

1.3 十字丝标志的识别与定位

对十字丝标志进行识别与定位通常可采用如下步骤：

1.3.1 对图像进行预处理，如滤除噪声，线性增强；

1.3.2 对图像进行分割，得到二值目标，然后用Hough变换检测十字丝两交叉直线的方位，可以对二值目标进行滤波和细化运算来减少运算量；

1.3.3 以两条直线的交点为十字丝的粗略搜索区域中心点，选取一个搜索区域，然后根据十字丝的角度和线宽度制作理想的相关模板，在目标搜索区域进行亚象素相关运算对目标进行亚像素定位。

1.4 十子线的灰度投影法匹配规则

根据图像特征(十字线)，对模板图像分别进行在 x、y 方向的灰度投影。 图 2（a）、2（b）分别是投影曲线的斜率图，此图的特征非常明显。对投影图像进行数值处理，求出投影曲线斜率最大值及其所在位置，构成特征向量CT[TxV，TxP，TyV，TyP]。其中：CTxP和CTxP为模板图像在x向投影的最大值及其所在位置；CTyP和CTyP为模板图像在y向投影的最大值及其所在位置；然后对原图像中左上角坐标为（i，j），大小为模板T的子图像Sij进行相同的运算，求出其特征向量CS[SxV，SxP，SyV，SyP]。其中 SxV 和 SxP 为子图像在x向投影的最大值及其所在位置；SyV和SyP为子图像在y向投影的最大值及其所在位置。定义匹配距离为：

距离最小且小于阈值者即为匹配点。运算中，首先进行x向的距离运算，若结果小于阈值，再进行y向的距离运算；否则，认为此处为非匹配点，搜索下一个子图像。这样，就加快了搜索速度。因匹配过程是根据图像的特征进行的，而不是简单的像素灰度差值判断，故适应于一定的噪声、缩放、旋转和变形图像。

图2 （a）模版图像垂直投影梯度

图2 （b）模版图像水平投影梯度

2 遗传算法优化

在灰度投影法匹配过程中，如果采用逐点匹配，计算量很大。遗传算法是非常出色的优化算法。

遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法操作使用适者生存原则，在潜在的解决方案种群中逐次产生一个近似最优的方案。在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到新个体比原个体更能适应环境，就像自然界中的改造一样[4]。

2.1 遗传算法特点

遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，与传统的优化算法相比，它有以下特点：

2.1.1 传统的优化算法往往利用决策变量的实际值本身来进行优化计算，但是遗传算法并不是直接利用决策变量的值，而是以决策变量的编码作为研究对象。

2.1.2 传统的算法不仅需要目标函数值，而且往往需要目标函数值的导数等其它一些辅助信息才能确定搜索方向。而遗传算法直接以目标函数值作为搜索信息，具有通用性。

2.1.3传统的优化方法往往是从解空间中的一个初始点开始最优解的迭代搜索过程。

2.1.4 传统的算法使用是确定的搜索方法，遗传算法属于一种自适应概率搜索技术。

2.1.5 全局最优性，鲁棒性，兼容性。

2.2 遗传算法基本过程

图3是遗传算法的基本过程[7]。

图3 遗传算法的基本过程

不同的编码方案、选择策略和遗传算子相结合构成了不同的遗传算法，但不同遗传算法在计算中的迭代过程大体相同，都包含了编码、选择、交叉、变异和解码等五个阶段[5][6]。

2.3 遗传算法优化流程[7]

2.3.1 对模板图像 进行 方向的灰度投影，生成特征向量 ；

2.3.2 对待匹配空间 生成初始种群，即初始化待匹配点；

2.3.3 根据待匹配点确定待匹配子图像 ，求出其特征向量 CS[SxV，SxP，SyV，SyP]，及与 TS 的匹配距离D[SM，TS]，从而求出群体的适应度；

2.3.4 对该群体进行最优保存的选择操作；

2.3.5 进行交叉和变异操作；

2.3.6 计算群体的适应度；

2.3.7 若符合匹配条件就结束，求出匹配点；否则，返回3)继续进行。

3 匹配计算量分析

在主频1.7G、1G内存的酷睿双核主机上，用Matlab编写测量软件，进行实验。待匹配图像为CCD采集到的现场实验图像，大小为640×480，模板图像为从中取出的76×76的包含十字线定位特征的图像。

传统自相关匹配中由归一化相关函数知：对M×N的模板图像，计算1次相关函数需要的计算量约为 3×M×N×4（4 次减法+1 次乘法）；而对相同大小的子图像进行1次灰度投影所需要的计算量约为2×M×N加法。可见，采用灰度投影大大降低了运算量。

GA能够大幅度减少图像匹配中模板匹配的次数。对图像进行逐点匹配法匹配次数=（640-76+1）×（480-76+1）=228825。 而 GA 相关匹配的匹配次数=~ （进化代数）×（种群数）=（80）×（40）=3200，两者计算效率比为228825/3200>71倍，可见计算效率有了明显提高。

4 实验结果分析

用GA对取自自身的模板进行匹配，初始种群为40，最大代数为80，交叉概率为0.6，变异概率为0.001。在某次匹配过程中其平均适应度如图4（a）所示，最大适应度曲线如图 4（b）所示。 图中，GA的最大值适应度值逐渐变大，种群平均值适应值有一个比较平缓的增长后，出现抖动现象，表明种群的多样性得到了保持。如果种群快速收敛，则可能造成早熟现象，造成最大适应度解在最优解附近抖动。

图5 匹配结果

表1 遗传算法匹配结果

图5为程序运行时匹配图像，其中矩形框为匹配的结果，目视情况下，匹配正确。矩形框的左边十字丝标记是为了试验误匹配情况，图5中没有出现误匹配。

为了研究遗传算法全局寻优能力和早熟现象，在一副图像上截取模板，然后与此图像在固定代数和不固定代数情况下分别进行匹配，结果数据如表1。上表结果表明，遗传算法的全局寻优能力较强，极大的减少了匹配过程中的计算量，通常能在80代内寻找到最优值，但是同时也能看到，由于早熟而出现的抖动现象。这对定位标志物非常不利，有必要在粗定位后进行精确定位。

[1]叶声华,王仲,杨学友.视觉检测技术及应用[J].中国工程科学.1999(1):49～52.

[2]王红梅,张科.图像匹配研究进展[J].计算机工程与应用.2004 Vol.40 No.19 ：42～44

[3]杨光,田地.基于投影特征的快速图像匹配方法[J].吉林大学学报(工学版).2010(5)：1340～1344

[4]席裕庚,柴天佑.遗传算法综述[J].控制理论与应用.1996(6):697～708

[5]张晓缋,方浩.遗传算法的编码机制研究[J].信息与控制.1997(2):55～60

[6]郑力新.利用遗传算法实现模板匹配的瓷砖分选[J].华侨大学学报(自然科学版).2010(6):632～635

[7]ZHANG Lei,HU Jia-long,QIAN Ya-ping.Research of Online Weighing System of Molten-iron Based on Image Processing.SPIE Vol.6623:66231F

OPTIMIZATION OF IMAGE TEMPLATE MATCHING BASED ON GENETIC ALGORITHM

LIU De-hua HU Jia-long
(Maanshan Technical College,Maanshan Anhui243000)

This paper analyzes feature template matching process of the common markers,and optimizes the cross-wire matching by genetic algorithm,draws the average fitness and maximum fitness curve under the given parameters.Through experiments under a fixed and not fixed algebraic,analysis of the value of matching results,genetic algorithms have a strong global optimization to match the template and can greatly reduce the amount of matching calculation.

image Processing； template matching；genetic Algorithm

A

1672－2868（2011）03－0057－04

2010-12-16

刘德华（1966-），男，安徽霍邱人。硕士，研究方向：图形图像处理

责任编辑：宏 彬