吳 曉

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

目前，在國際與國內LED芯片檢測領域，視覺伺服定位技術是熱點又是難點.盡管國外已研制出成型的LED芯片檢測機、固晶機等設備，但其檢測定位精度、定位速度都很難滿足LED高速發展的要求.由于LED晶圓上LED芯片不但尺寸小，而且數量多達1.5萬多只，因此找到一種定位既準又快的方法成為LED發展的關鍵之一.本文在分析各種傳統半導體芯片定位系統的基礎上提出了一種基于遺傳算法的LED芯片快速定位方法.

1 遺傳算法

遺傳算法提供了一種求解復雜系統優化問題的通用框架，是一種群體性操作的框架算法，采用了概率轉移原則，它不依賴于問題具體的領域，與傳統的方法相比，不需很多先驗知識、收斂速度快、魯棒性強，成為全局優化問題的有力工具之一[1].

如圖1所示為簡單遺傳算法的流程圖.選擇、交叉和變異是遺傳算法的3個主要操作算子，構成了遺傳操作，是遺傳算法區別其他算法的主要特點.

（1）將問題及解的空間構成編碼和解碼空間，確定種群規模和適應度函數[2].

圖1 遺傳算法基本流程圖

（2）對種群設定初值，即基因初始化.

（3）計算種群的各個體的適應度值，判斷其值是否滿足終止條件，如滿足則輸出最優個體并解碼，得到問題的解.否則選擇有較大適應值的個體進行交叉、變異，以便產生更適應環境的個體.

（4）返回（3）直至滿足終止條件.這樣一代代不斷進化，最終將收斂到一個最適應環境的個體上，即問題的最優解.

遺傳算法的核心內容是：個體的編碼解碼、初始種群的設定、適應度函數的設計、遺傳操作設計和控制參數設定[3].

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

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

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

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

（2）序貫相似度檢測（SSDA）[7]；

（3）互相關[8]；

（4）歸一化互相關[9]；

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

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

如圖2所示，SSDA在進行上述求和時不需要計算所有像素，只要其和超過給定的閾值，則說明當前位置為非匹配位置，停止本次計算，否則進行下一位置的運算，直至找到匹配點為止[10-11].

盡管SSDA匹配速度較快，但隨模板像素數的增長，時間呈平方增長.采用遺傳算法的SSDA是提高效率的辦法之一.

圖2 模板匹配識別流程圖

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

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

3.1 遺傳算法的SSDA

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

在這里特別采用無回放式余數隨機選擇，選擇誤差較小，可確保適應度比平均適應度大的個體進化到下一代群體中.

3.2 適應度函數

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

其中模板大小為m、n，取自圖像的一個LED芯片，F（i，j）為待求坐標值的圖像大小為M、N，圖像子圖為F（a+i，b+j）大小為m、n，適應度函數E（i，j）的范圍是0～255.

4 實驗結果比較

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

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

4.1 模板學習模塊

模板學習模塊主要完成以下過程（如圖4所示），（1）確定作為模板的標準芯片；（2）設定模板區域RIO；（3）設定訓練模板及其相關參數.

在圖像中，設定模板時，首先通過拖拉ROI框，框選出一塊LED芯片作為標準芯片，找到芯片的邊界，得到芯片的學習坐標等參數，進行學習并保存為模板.

圖4 模板學習界面

4.2 芯片搜索模塊

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

為了對比分析，分別用該模板圖像和待匹配圖像進行傳統的SSDA匹配和基于遺傳算法的SSAD匹配.如表1所示，經對運行結果進行統計，和傳統方法相比，遺傳算法在運行時間上占有明顯優勢，LED芯片定位效率提高了223%，精度也有所提高.

圖5 檢測結果

表1 傳統方法與基于遺傳算法的模板匹配效

5 結束語

由于LED發光管使用方便、節能且價格低，所以它廣泛應用在生產生活中.LED生產設備中的關鍵部件之一是定位系統，首先對LED芯片定位系統的視覺定位系統進行分析研究，確定運用基于遺傳算法模板匹配對LED芯片圖像進行識別和定位.然后理論分析了定位方法、步驟和關鍵技術.實驗測試和精度分析表明，基于遺傳算法模板匹配的效率是傳統方法的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]巨永鋒，藺廣逢，蔡占華.基于遺傳算法的圖像識別技術[J].長安大學學報：自然科學版，2004，24（6）：98-101.

[3]虞松，趙國群，王廣春，等.LED晶粒自動點測臺系統研究[D].西安：西安工業大學，2004，34（2）：6-9.

[4]王波，宋長新，程敬之.自動特征識別的新方法[J].西安交通大學學報，2002，36（8）：806－809.

[5]宋長新，馬克，王波.特征的自動識別規則與提取[J].計算機工程，2002，28（11）：72-75.

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

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

[8]湯曉燕.基于機器視覺的芯片成型分離視覺檢測系統的研究[J].軟件導刊，2009，27（4）：30-33.

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

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

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