利用遺傳算法實(shí)現(xiàn)模板匹配的瓷磚分選

鄭力新,姚強(qiáng),周凱汀,林福泳

(華僑大學(xué)信息科學(xué)與工程學(xué)院,福建泉州362021)

利用遺傳算法實(shí)現(xiàn)模板匹配的瓷磚分選

鄭力新,姚強(qiáng),周凱汀,林福泳

(華僑大學(xué)信息科學(xué)與工程學(xué)院,福建泉州362021)

提出瓷磚圖像模板匹配的匹配程度公式,分析匹配度與公式值的關(guān)系.將匹配程度公式作為最優(yōu)保留個(gè)體遺傳算法的目標(biāo)函數(shù),設(shè)立遺傳算法的3個(gè)變量,即x軸起始位置、y軸起始位置和放大倍數(shù)對(duì)圖像的模板進(jìn)行匹配優(yōu)化.實(shí)驗(yàn)結(jié)果表明,遺傳算法的匹配結(jié)果基本穩(wěn)定,能滿足工業(yè)實(shí)時(shí)性的要求,模板的大小同匹配時(shí)間成反比,同效果成正比.

模板匹配;瓷磚;遺傳算法;分選;適應(yīng)度函數(shù);精度

在瓷磚的生產(chǎn)過(guò)程中,區(qū)分瓷磚的主要依據(jù)是它們的花紋,因此可以根據(jù)紋理的不同,采用模板匹配的方法完成機(jī)器代替人力的工作.在圖像識(shí)別中,模板匹配是常用的方法.模板匹配是將圖像中某種特征或目標(biāo)作為模板,在被識(shí)別的圖像上滑動(dòng),并作運(yùn)算,確定被識(shí)別圖像上的特征或目標(biāo)的位置,識(shí)別出待測(cè)的事物與標(biāo)本相同或相似的方法[1].遺傳算法[2-3](Genetic A lgo rithm,GA)是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來(lái)的隨機(jī)高效全局搜索和優(yōu)化方法,其本質(zhì)是一種高效、并行、全局的搜索方法.直接的模板匹配速度太慢,不能滿足生產(chǎn)實(shí)時(shí)性的要求,而采用遺傳算法來(lái)完成模板匹配,能夠快速搜索到最佳匹配效果,大大提高搜索效率,能夠滿足實(shí)際生產(chǎn)的需求.本文將遺傳算法與模板匹配相結(jié)合,提出瓷磚圖像模板匹配的匹配程度公式并應(yīng)用于瓷磚的分選.

1 模板匹配

模板匹配的基本原理:設(shè)一個(gè)3 px×3 px的圖像模板W(i,j),其像素w(i,j)的位置如圖1所示.該模板疊放在被檢測(cè)的圖像F上平移,圖像F通常稱作子圖像Fm,n(i,j),其像素f(i,j)的位置如圖1所示.

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

圖1 像素位置Fig.1 Pixel position

2 改進(jìn)的保留最佳適應(yīng)個(gè)體的遺傳算法

標(biāo)準(zhǔn)遺傳算法存在早期收斂慢、早熟現(xiàn)象,以及后期在最優(yōu)解附近振蕩的缺陷,而這些缺點(diǎn)是可以通過(guò)提高交叉概率和變異概率來(lái)改善的.但是,交叉概率和變異概率的提高又會(huì)帶來(lái)新的問(wèn)題,如變異概率大的話,遺傳算法就退化成隨機(jī)搜索了,已經(jīng)求得的最大值被替換掉了,即出現(xiàn)振蕩現(xiàn)象[4].

保留最佳適應(yīng)個(gè)體的遺傳算法的基本流程,如圖2所示.在每一代中求出最佳個(gè)體,如果下一代的最佳個(gè)體的適應(yīng)度值比上一代的最佳個(gè)體適應(yīng)度值高,則繼續(xù)進(jìn)行算法;否則,用上一代的最佳個(gè)體替代下一代中的一個(gè)個(gè)體.這樣就保證了算法始終在朝著適應(yīng)度值不斷增加的方向進(jìn)行.

圖2 保留最佳適應(yīng)個(gè)體的遺傳算法流程Fig.2 Flow chart of genetic algo rithm for best keeping chromosome

Shubert函數(shù)是個(gè)多峰值函數(shù),在區(qū)間[-10,10]有760個(gè)局部最小值,而其中的18個(gè)是全局最小值-186.73.標(biāo)準(zhǔn)遺傳算法的計(jì)算速度慢,而且很容易進(jìn)入局部最小值點(diǎn).用改進(jìn)的保留最佳值的遺傳算法的方法,可以很快搜索到最小值,并且不會(huì)陷入局部最小值點(diǎn).具體算法有如下5個(gè)步驟.

(1)采用二進(jìn)制編碼.要求精度為0.000 1,因?yàn)閇10-(-10)]/0.000 1=200 000,217<200 000< 218.所以,每個(gè)變量要用長(zhǎng)度為18的二進(jìn)制串來(lái)表示,兩個(gè)變量要36位二進(jìn)制串.

(2)初始化種群.取初始種群的大小為40,即隨機(jī)生成長(zhǎng)度為36的二進(jìn)制串,每個(gè)二進(jìn)制串的每一位隨機(jī)地取0和1.

(3)求每個(gè)個(gè)體的適應(yīng)度和種群中的最佳適應(yīng)個(gè)體.將f(x)取為適應(yīng)度函數(shù).例如,對(duì)于個(gè)體p= (010110100010100100100101011101010101),其適應(yīng)度值為fit(x)=f(x)=-128.54.如果這一步的循環(huán)代數(shù)(n)滿足要求或最佳適應(yīng)個(gè)體滿足精度要求,則結(jié)束循環(huán),退出程序.當(dāng)其不滿足結(jié)束循環(huán)的條件且這一代的代數(shù)大于1時(shí),如果這一代的最佳個(gè)體的適應(yīng)度值大于上一代最佳個(gè)體的適應(yīng)度值,則繼續(xù)往下執(zhí)行;否則,用上一代的最佳個(gè)體取代這一代中的一個(gè)個(gè)體.

(4)進(jìn)行交叉操作.交叉概率Pc=0.25.

(5)進(jìn)行變異操作.變異概率Pm=0.01,并轉(zhuǎn)向步驟(3).

經(jīng)過(guò)50代迭代后,其目標(biāo)函數(shù)值和種群目標(biāo)函數(shù)均值(zav)與最優(yōu)解(zop)的變化,如圖3所示.從圖3可以看出,經(jīng)過(guò)迭代后,目標(biāo)函數(shù)值基本趨于一致,達(dá)到要求的最小值.在第22代時(shí)基本趨于穩(wěn)定,說(shuō)明該方法是快速、高效的.此時(shí),x1=-1.434 2,x2=-0.800 3,min f(x1,x2)=-186.730 9.

用改進(jìn)后的遺傳算法求Shubert函數(shù),有

圖3 迭代50次后的目標(biāo)函數(shù)值Fig.3 Value of target function after 50 generation

采用保留最佳適應(yīng)個(gè)體的遺傳算法進(jìn)行求解,優(yōu)化最大值為1,進(jìn)化代數(shù)為22,時(shí)間小于0.5 s;而采用簡(jiǎn)單遺傳算法進(jìn)行求解,優(yōu)化最大值為1,進(jìn)化代數(shù)(n)為150,時(shí)間為3 s.由此可知,保留最佳適應(yīng)個(gè)體的遺傳算法在收斂速度上優(yōu)于簡(jiǎn)單遺傳算法,而且得到相同的結(jié)果使用更少的代數(shù)和時(shí)間,并能保證解的最優(yōu)化.

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

3 實(shí)驗(yàn)結(jié)果

實(shí)際過(guò)程中,把每種瓷磚的特征部分提取出來(lái)作為模板,如圖4所示.提取的模板一定要能體現(xiàn)瓷磚之間的顯著差別.將其與生產(chǎn)過(guò)程中拍攝到的圖片(圖5)作模板匹配,如果滿足相似性要求,即可確定為同一類.

在瓷磚分選中,應(yīng)用遺傳算法實(shí)現(xiàn)模板匹配需要用到3個(gè)變量:橫坐標(biāo)起始位置x,縱坐標(biāo)起始位置y和放大倍數(shù)t.如果在匹配之前沒(méi)有進(jìn)行圖像的矯正,也就是旋轉(zhuǎn),還需要一個(gè)變量——旋轉(zhuǎn)角度.根據(jù)圖像的大小,x最大的取值不超過(guò)1 000,所以采用二進(jìn)制編碼方式10位即可;對(duì)于y的取值也是如此,而模板和圖片的大小差別在0.7～2.0之間.如果取放大系數(shù)的步長(zhǎng)為0.1,則放大倍數(shù)需要4位,所以一個(gè)個(gè)體的長(zhǎng)度為24位就能滿足要求.

算法的具體實(shí)現(xiàn)和要求有如下6點(diǎn).(1)編碼方案.采用二進(jìn)制編碼.(2)初始化種群.取初始種群為40,即有40個(gè)長(zhǎng)度為24的二進(jìn)制串組成初始種群.(3)適應(yīng)度函數(shù).因?yàn)槭且云ヅ涑潭葹闃?biāo)準(zhǔn)進(jìn)行瓷磚分選的,所以以模板匹配的相似度作為適應(yīng)度函數(shù).(4)選擇操作.依據(jù)各個(gè)個(gè)體的適應(yīng)度,按照改進(jìn)的保留最佳適應(yīng)個(gè)體的算法,選用隨機(jī)遍歷抽樣法[5],并且規(guī)定最大遺傳代數(shù)為200代.(5)交叉操作.采用單點(diǎn)交叉,交叉概率Pc=0.20.(6)變異操作.取變異概率Pm=0.01.

圖5 生產(chǎn)過(guò)程中拍攝到的圖片F(xiàn)ig.5 Photo taken in the p roduction p rocess

根據(jù)以上要求,進(jìn)行模板匹配,結(jié)果如圖6所示.從圖6可看出,對(duì)于同一類,最后的匹配率達(dá)到95%以上.在模板提取過(guò)程中,由于存在噪聲干擾、圖片個(gè)體的特殊性等因素,理論上最佳匹配效果只有96%.所以,誤差是在范圍之內(nèi)的.對(duì)于不同的瓷磚,最終的匹配結(jié)果不到50%,說(shuō)明可依匹配度的大小來(lái)進(jìn)行區(qū)分.在40～50代的時(shí)候,匹配結(jié)果基本穩(wěn)定,用M atlab實(shí)現(xiàn)需要的時(shí)間為10 s左右,而用DSP實(shí)現(xiàn)需要2 s左右,能滿足生產(chǎn)實(shí)時(shí)性的要求.

圖6 模板匹配實(shí)驗(yàn)結(jié)果Fig.6 Experimental result of temp late matching

4 結(jié)束語(yǔ)

模板的選取對(duì)實(shí)驗(yàn)結(jié)果會(huì)有一定的影響.如果模板取得較大,匹配效果好,但是需要的時(shí)間長(zhǎng);如果模板取得較小,會(huì)縮短匹配所需時(shí)間,但是效果稍差.因此,既要保證匹配效果好,又要縮短匹配時(shí)間,就必需選取圖像的特征部分,使其能成為圖像之間的明顯區(qū)分.

[1] 熊光華,夏慶觀.基于模板匹配的零件檢測(cè)的應(yīng)用[J].中國(guó)制造業(yè)信息化,2006,35(15):68-70.

[2] 雷英杰,張善文.Matlab遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2005.

[3] 鄭力新,周凱汀.基于遺傳算法的雙閉環(huán)系統(tǒng)模糊優(yōu)化設(shè)計(jì)[J].華僑大學(xué)學(xué)報(bào):自然科學(xué)版,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

(責(zé)任編輯:陳志賢 英文審校:吳逢鐵)

1000-5013(2010)06-0632-04

2009-03-23

鄭力新(1967-),男,教授,主要從事工業(yè)自動(dòng)化技術(shù)和人工智能的研究.E-mail:zlxzkt@yahoo.com.cn.

教育部科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(207145);福建省高等學(xué)校新世紀(jì)優(yōu)秀人才支持項(xiàng)目(07FJRC01)