吳 曉

（莆田學(xué)院 電子信息工程學(xué)系，福建 莆田 351100）

目前，在國(guó)際與國(guó)內(nèi)LED芯片檢測(cè)領(lǐng)域，視覺伺服定位技術(shù)是熱點(diǎn)又是難點(diǎn).盡管國(guó)外已研制出成型的LED芯片檢測(cè)機(jī)、固晶機(jī)等設(shè)備，但其檢測(cè)定位精度、定位速度都很難滿足LED高速發(fā)展的要求.由于LED晶圓上LED芯片不但尺寸小，而且數(shù)量多達(dá)1.5萬(wàn)多只，因此找到一種定位既準(zhǔn)又快的方法成為L(zhǎng)ED發(fā)展的關(guān)鍵之一.本文在分析各種傳統(tǒng)半導(dǎo)體芯片定位系統(tǒng)的基礎(chǔ)上提出了一種基于遺傳算法的LED芯片快速定位方法.

1 遺傳算法

遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，是一種群體性操作的框架算法，采用了概率轉(zhuǎn)移原則，它不依賴于問題具體的領(lǐng)域，與傳統(tǒng)的方法相比，不需很多先驗(yàn)知識(shí)、收斂速度快、魯棒性強(qiáng)，成為全局優(yōu)化問題的有力工具之一[1].

如圖1所示為簡(jiǎn)單遺傳算法的流程圖.選擇、交叉和變異是遺傳算法的3個(gè)主要操作算子，構(gòu)成了遺傳操作，是遺傳算法區(qū)別其他算法的主要特點(diǎn).

（1）將問題及解的空間構(gòu)成編碼和解碼空間，確定種群規(guī)模和適應(yīng)度函數(shù)[2].

圖1 遺傳算法基本流程圖

（2）對(duì)種群設(shè)定初值，即基因初始化.

（3）計(jì)算種群的各個(gè)體的適應(yīng)度值，判斷其值是否滿足終止條件，如滿足則輸出最優(yōu)個(gè)體并解碼，得到問題的解.否則選擇有較大適應(yīng)值的個(gè)體進(jìn)行交叉、變異，以便產(chǎn)生更適應(yīng)環(huán)境的個(gè)體.

（4）返回（3）直至滿足終止條件.這樣一代代不斷進(jìn)化，最終將收斂到一個(gè)最適應(yīng)環(huán)境的個(gè)體上，即問題的最優(yōu)解.

遺傳算法的核心內(nèi)容是：個(gè)體的編碼解碼、初始種群的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)和控制參數(shù)設(shè)定[3].

2 模板匹配的圖像定位方法

模板匹配的基本思想以已知的某種目標(biāo)的模型形成一個(gè)灰度矩陣，用該矩陣在圖像的搜索范圍內(nèi)分別移動(dòng)計(jì)算其與圖像上相應(yīng)區(qū)域的相似度，以相似度最大的位置為待識(shí)別目標(biāo)的位置[4].基于圖像灰度的匹配方法不需對(duì)圖像做特征提取，而是直接利用全部可用的圖像灰度信息，因此，能提高估計(jì)的精度和魯棒性[5].

模板匹配算法主要有以下四種：

（1）兩幅圖像灰度的平方差之和[6]；

（2）序貫相似度檢測(cè)（SSDA）[7]；

（3）互相關(guān)[8]；

（4）歸一化互相關(guān)[9]；

其中，模板圖像T（a，b）的大小為m×n，（a，b）表示坐標(biāo)位置，T（a，b）表示（a，b）處的灰度值；輸入圖像F（i，j）的大小是M×N（M>m，N>n）.在這里選用序貫相似檢測(cè)算法，即SSDA.

SSDA是一種快速圖像匹配算法，以隨機(jī)不重復(fù)的順序選取像元對(duì)（a，b），它使用公式（1）作為相似性度量.

如圖2所示，SSDA在進(jìn)行上述求和時(shí)不需要計(jì)算所有像素，只要其和超過給定的閾值，則說(shuō)明當(dāng)前位置為非匹配位置，停止本次計(jì)算，否則進(jìn)行下一位置的運(yùn)算，直至找到匹配點(diǎn)為止[10-11].

盡管SSDA匹配速度較快，但隨模板像素?cái)?shù)的增長(zhǎng)，時(shí)間呈平方增長(zhǎng).采用遺傳算法的SSDA是提高效率的辦法之一.

圖2 模板匹配識(shí)別流程圖

3 基于遺傳算法的圖像匹配

由于LED芯片定位系統(tǒng)要求檢測(cè)速度要快，所以我們采用基于遺傳算法的序貫相似度檢測(cè)（SSDA），這樣既可保證精度，又提高了快速性.

3.1 遺傳算法的SSDA

圖3為遺傳算法SSDA LED芯片定位流程圖，采用選擇、交叉和變異三種遺傳算子及SSDA算法的主要運(yùn)算過程，采用實(shí)數(shù)編碼方法P（X，Y），速度快，精度高.

在這里特別采用無(wú)回放式余數(shù)隨機(jī)選擇，選擇誤差較小，可確保適應(yīng)度比平均適應(yīng)度大的個(gè)體進(jìn)化到下一代群體中.

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)表明個(gè)體或解的優(yōu)劣性.適應(yīng)度越高，個(gè)體越接近最優(yōu)解[10].針對(duì)序貫相似度檢測(cè)SSDA模板匹配來(lái)說(shuō)，模板T（a，b）上的所有灰度值與圖像子圖上所有對(duì)應(yīng)像素的灰度值之差越小，也就認(rèn)為是越匹配，也就是求極小值如公式（1）所示.由于適應(yīng)度是求解極大值，所以定義適應(yīng)度函數(shù)E（i，j）

其中模板大小為m、n，取自圖像的一個(gè)LED芯片，F(xiàn)（i，j）為待求坐標(biāo)值的圖像大小為M、N，圖像子圖為F（a+i，b+j）大小為m、n，適應(yīng)度函數(shù)E（i，j）的范圍是0～255.

4 實(shí)驗(yàn)結(jié)果比較

采用雙核2.6 G，4 G內(nèi)存的計(jì)算機(jī)，用VC++實(shí)現(xiàn)了遺傳算法SSDA匹配，流程如圖3所示.為了測(cè)試遺傳算法SSDA匹配的速度、精度等實(shí)驗(yàn)參數(shù)，待匹配的圖像為1280×1024的LED芯片灰度圖，模板也來(lái)自于這個(gè)灰度圖一部分，模板T（a，b）選用一個(gè)完整的LED芯片圖像，大小為133×101 pixels.設(shè)置總代數(shù)為150，種群大小為60，交叉率：0.75，變異率：0.008，適應(yīng)度函數(shù)為公式（2），終止運(yùn)算灰度 值為大于 150，而 SS?DA 的 D（i，j）大于50，則說(shuō)明當(dāng)前位置為非匹配位置，停止本次計(jì)算.

圖3 遺傳算法模板匹配LED芯片定位流程圖

4.1 模板學(xué)習(xí)模塊

模板學(xué)習(xí)模塊主要完成以下過程（如圖4所示），（1）確定作為模板的標(biāo)準(zhǔn)芯片；（2）設(shè)定模板區(qū)域RIO；（3）設(shè)定訓(xùn)練模板及其相關(guān)參數(shù).

在圖像中，設(shè)定模板時(shí)，首先通過拖拉ROI框，框選出一塊LED芯片作為標(biāo)準(zhǔn)芯片，找到芯片的邊界，得到芯片的學(xué)習(xí)坐標(biāo)等參數(shù)，進(jìn)行學(xué)習(xí)并保存為模板.

圖4 模板學(xué)習(xí)界面

4.2 芯片搜索模塊

芯片搜索模塊的主要功能和步驟為：（1）在待測(cè)的目標(biāo)圖像中，首先選定LED芯片搜索范圍即感興趣區(qū)域RIO；（2）在RIO內(nèi)，利用模板匹配搜索到所有LED芯片位置，記錄LED芯片的中心坐標(biāo)參數(shù)，并判斷芯片是否有缺陷；（3）把LED芯片位置坐標(biāo)數(shù)據(jù)送到分類數(shù)據(jù)庫(kù)并適時(shí)送給滑臺(tái)控制系統(tǒng).如圖5所示.

為了對(duì)比分析，分別用該模板圖像和待匹配圖像進(jìn)行傳統(tǒng)的SSDA匹配和基于遺傳算法的SSAD匹配.如表1所示，經(jīng)對(duì)運(yùn)行結(jié)果進(jìn)行統(tǒng)計(jì)，和傳統(tǒng)方法相比，遺傳算法在運(yùn)行時(shí)間上占有明顯優(yōu)勢(shì)，LED芯片定位效率提高了223%，精度也有所提高.

圖5 檢測(cè)結(jié)果

表1 傳統(tǒng)方法與基于遺傳算法的模板匹配效

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

由于LED發(fā)光管使用方便、節(jié)能且價(jià)格低，所以它廣泛應(yīng)用在生產(chǎn)生活中.LED生產(chǎn)設(shè)備中的關(guān)鍵部件之一是定位系統(tǒng)，首先對(duì)LED芯片定位系統(tǒng)的視覺定位系統(tǒng)進(jìn)行分析研究，確定運(yùn)用基于遺傳算法模板匹配對(duì)LED芯片圖像進(jìn)行識(shí)別和定位.然后理論分析了定位方法、步驟和關(guān)鍵技術(shù).實(shí)驗(yàn)測(cè)試和精度分析表明，基于遺傳算法模板匹配的效率是傳統(tǒng)方法的223倍，定位精度也有所提高.

[1]Srinivasa K,Venugopal K,Patnaik L.A self-adaptive migration model genetic algorithm for data mining applications[J].Information Sciences,2007,177（20）:4295-4313.

[2]巨永鋒，藺廣逢，蔡占華.基于遺傳算法的圖像識(shí)別技術(shù)[J].長(zhǎng)安大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，24（6）：98-101.

[3]虞松，趙國(guó)群，王廣春，等.LED晶粒自動(dòng)點(diǎn)測(cè)臺(tái)系統(tǒng)研究[D].西安：西安工業(yè)大學(xué)，2004，34（2）：6-9.

[4]王波，宋長(zhǎng)新，程敬之.自動(dòng)特征識(shí)別的新方法[J].西安交通大學(xué)學(xué)報(bào)，2002，36（8）：806－809.

[5]宋長(zhǎng)新，馬克，王波.特征的自動(dòng)識(shí)別規(guī)則與提取[J].計(jì)算機(jī)工程，2002，28（11）：72-75.

[6]劉建立，左保齊.基于遺傳算法的織物印花圖案的分割[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（15）：3966-3967

[7]侯格賢，吳成柯.一種利用遺傳算法的快速匹配算法[J].西安電子科技大學(xué)學(xué)報(bào)，1998，25（4）：450-452.

[8]湯曉燕.基于機(jī)器視覺的芯片成型分離視覺檢測(cè)系統(tǒng)的研究[J].軟件導(dǎo)刊，2009，27（4）：30-33.

[9]吉根林.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用與軟件，2004，21（2）：69-73.

[10]吳曉.LED芯片視覺伺服二次定位系統(tǒng)：中國(guó)，ZL201220208320.2[P/OL].2012.http://www.zlzrw.com/html/zlgq/16330.html.

[11]鄭軍，諸靜.基于自適應(yīng)的遺傳算法的圖像匹配[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2003，37（6）：689-692.