利用遗传算法实现模板匹配的瓷砖分选

郑力新,姚强,周凯汀,林福泳

(华侨大学信息科学与工程学院,福建泉州362021)

利用遗传算法实现模板匹配的瓷砖分选

郑力新,姚强,周凯汀,林福泳

(华侨大学信息科学与工程学院,福建泉州362021)

提出瓷砖图像模板匹配的匹配程度公式,分析匹配度与公式值的关系.将匹配程度公式作为最优保留个体遗传算法的目标函数,设立遗传算法的3个变量,即x轴起始位置、y轴起始位置和放大倍数对图像的模板进行匹配优化.实验结果表明,遗传算法的匹配结果基本稳定,能满足工业实时性的要求,模板的大小同匹配时间成反比,同效果成正比.

模板匹配;瓷砖;遗传算法;分选;适应度函数;精度

在瓷砖的生产过程中,区分瓷砖的主要依据是它们的花纹,因此可以根据纹理的不同,采用模板匹配的方法完成机器代替人力的工作.在图像识别中,模板匹配是常用的方法.模板匹配是将图像中某种特征或目标作为模板,在被识别的图像上滑动,并作运算,确定被识别图像上的特征或目标的位置,识别出待测的事物与标本相同或相似的方法[1].遗传算法[2-3](Genetic A lgo rithm,GA)是模仿自然界生物进化机制发展起来的随机高效全局搜索和优化方法,其本质是一种高效、并行、全局的搜索方法.直接的模板匹配速度太慢,不能满足生产实时性的要求,而采用遗传算法来完成模板匹配,能够快速搜索到最佳匹配效果,大大提高搜索效率,能够满足实际生产的需求.本文将遗传算法与模板匹配相结合,提出瓷砖图像模板匹配的匹配程度公式并应用于瓷砖的分选.

1 模板匹配

模板匹配的基本原理:设一个3 px×3 px的图像模板W(i,j),其像素w(i,j)的位置如图1所示.该模板叠放在被检测的图像F上平移,图像F通常称作子图像Fm,n(i,j),其像素f(i,j)的位置如图1所示.

若模板W(i,j)与子图像Fm,n(i,j)完全一致,两者之差为零,即表示两者匹配的程度很好.匹配程度或相似程度可表示为

图1 像素位置Fig.1 Pixel position

2 改进的保留最佳适应个体的遗传算法

标准遗传算法存在早期收敛慢、早熟现象,以及后期在最优解附近振荡的缺陷,而这些缺点是可以通过提高交叉概率和变异概率来改善的.但是,交叉概率和变异概率的提高又会带来新的问题,如变异概率大的话,遗传算法就退化成随机搜索了,已经求得的最大值被替换掉了,即出现振荡现象[4].

保留最佳适应个体的遗传算法的基本流程,如图2所示.在每一代中求出最佳个体,如果下一代的最佳个体的适应度值比上一代的最佳个体适应度值高,则继续进行算法;否则,用上一代的最佳个体替代下一代中的一个个体.这样就保证了算法始终在朝着适应度值不断增加的方向进行.

图2 保留最佳适应个体的遗传算法流程Fig.2 Flow chart of genetic algo rithm for best keeping chromosome

Shubert函数是个多峰值函数,在区间[-10,10]有760个局部最小值,而其中的18个是全局最小值-186.73.标准遗传算法的计算速度慢,而且很容易进入局部最小值点.用改进的保留最佳值的遗传算法的方法,可以很快搜索到最小值,并且不会陷入局部最小值点.具体算法有如下5个步骤.

(1)采用二进制编码.要求精度为0.000 1,因为[10-(-10)]/0.000 1=200 000,217<200 000< 218.所以,每个变量要用长度为18的二进制串来表示,两个变量要36位二进制串.

(2)初始化种群.取初始种群的大小为40,即随机生成长度为36的二进制串,每个二进制串的每一位随机地取0和1.

(3)求每个个体的适应度和种群中的最佳适应个体.将f(x)取为适应度函数.例如,对于个体p= (010110100010100100100101011101010101),其适应度值为fit(x)=f(x)=-128.54.如果这一步的循环代数(n)满足要求或最佳适应个体满足精度要求,则结束循环,退出程序.当其不满足结束循环的条件且这一代的代数大于1时,如果这一代的最佳个体的适应度值大于上一代最佳个体的适应度值,则继续往下执行;否则,用上一代的最佳个体取代这一代中的一个个体.

(4)进行交叉操作.交叉概率Pc=0.25.

(5)进行变异操作.变异概率Pm=0.01,并转向步骤(3).

经过50代迭代后,其目标函数值和种群目标函数均值(zav)与最优解(zop)的变化,如图3所示.从图3可以看出,经过迭代后,目标函数值基本趋于一致,达到要求的最小值.在第22代时基本趋于稳定,说明该方法是快速、高效的.此时,x1=-1.434 2,x2=-0.800 3,min f(x1,x2)=-186.730 9.

用改进后的遗传算法求Shubert函数,有

图3 迭代50次后的目标函数值Fig.3 Value of target function after 50 generation

采用保留最佳适应个体的遗传算法进行求解,优化最大值为1,进化代数为22,时间小于0.5 s;而采用简单遗传算法进行求解,优化最大值为1,进化代数(n)为150,时间为3 s.由此可知,保留最佳适应个体的遗传算法在收敛速度上优于简单遗传算法,而且得到相同的结果使用更少的代数和时间,并能保证解的最优化.

图4 瓷砖的特征部分提取模板Fig.4 Temp late draw n from charateristic part of the ceramic brick

3 实验结果

实际过程中,把每种瓷砖的特征部分提取出来作为模板,如图4所示.提取的模板一定要能体现瓷砖之间的显著差别.将其与生产过程中拍摄到的图片(图5)作模板匹配,如果满足相似性要求,即可确定为同一类.

在瓷砖分选中,应用遗传算法实现模板匹配需要用到3个变量:横坐标起始位置x,纵坐标起始位置y和放大倍数t.如果在匹配之前没有进行图像的矫正,也就是旋转,还需要一个变量——旋转角度.根据图像的大小,x最大的取值不超过1 000,所以采用二进制编码方式10位即可;对于y的取值也是如此,而模板和图片的大小差别在0.7～2.0之间.如果取放大系数的步长为0.1,则放大倍数需要4位,所以一个个体的长度为24位就能满足要求.

算法的具体实现和要求有如下6点.(1)编码方案.采用二进制编码.(2)初始化种群.取初始种群为40,即有40个长度为24的二进制串组成初始种群.(3)适应度函数.因为是以匹配程度为标准进行瓷砖分选的,所以以模板匹配的相似度作为适应度函数.(4)选择操作.依据各个个体的适应度,按照改进的保留最佳适应个体的算法,选用随机遍历抽样法[5],并且规定最大遗传代数为200代.(5)交叉操作.采用单点交叉,交叉概率Pc=0.20.(6)变异操作.取变异概率Pm=0.01.

图5 生产过程中拍摄到的图片Fig.5 Photo taken in the p roduction p rocess

根据以上要求,进行模板匹配,结果如图6所示.从图6可看出,对于同一类,最后的匹配率达到95%以上.在模板提取过程中,由于存在噪声干扰、图片个体的特殊性等因素,理论上最佳匹配效果只有96%.所以,误差是在范围之内的.对于不同的瓷砖,最终的匹配结果不到50%,说明可依匹配度的大小来进行区分.在40～50代的时候,匹配结果基本稳定,用M atlab实现需要的时间为10 s左右,而用DSP实现需要2 s左右,能满足生产实时性的要求.

图6 模板匹配实验结果Fig.6 Experimental result of temp late matching

4 结束语

模板的选取对实验结果会有一定的影响.如果模板取得较大,匹配效果好,但是需要的时间长;如果模板取得较小,会缩短匹配所需时间,但是效果稍差.因此,既要保证匹配效果好,又要缩短匹配时间,就必需选取图像的特征部分,使其能成为图像之间的明显区分.

[1] 熊光华,夏庆观.基于模板匹配的零件检测的应用[J].中国制造业信息化,2006,35(15):68-70.

[2] 雷英杰,张善文.Matlab遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005.

[3] 郑力新,周凯汀.基于遗传算法的双闭环系统模糊优化设计[J].华侨大学学报:自然科学版,2000,21(1):16-20.

[4] LOU IS SJ,FANG Zhao.Domain know ledge for genetic algorithms[R].Nevada:Nevada University,1989.

[5] KANG Li-shan,KANG Zhuo,L I Yan,et al.A synchronous parallelization of Guo’s algorithm fo r function op timization[C]∥Proc 2000 Congress on Evolutionary Computation.Piscataway:IEEE Press,2000:876-881.

Tile Separation Based on Tem plate Matching Realized by Genetic Algorithm

ZHENG Li-xin,YAO Qiang, ZHOU Kai-ting,L IN Fu-yong
(College of Information Science and Engineering,Huaqiao University,Quanzhou 362021,China)

This paper put forwards the formula of ceramic brick image temp latematching degree and pointsout the relationship between matching degree and the formula.Using the function of matching degree as the target function of elitist genetic algorithm,we set the three variablesof the genetic algo rithm,that is,original position of x axis,o riginal position of y axis and amp lifier to op timally matching the image to its temp late.The experiment results show that genetic matching result is always stable and suitable for real time industrial usage.The greater the size of temp late image,the less matching time and the better matching effect.

templatematching;ceramic brick;genetic algorithm;sorting;fitness function;p recision

TP 391.41;TQ 174.76

A

(责任编辑:陈志贤 英文审校:吴逢铁)

1000-5013(2010)06-0632-04

2009-03-23

郑力新(1967-),男,教授,主要从事工业自动化技术和人工智能的研究.E-mail:zlxzkt@yahoo.com.cn.

教育部科学技术研究重点项目(207145);福建省高等学校新世纪优秀人才支持项目(07FJRC01)