1、現(xiàn)代檢測技術(shù)論文題目：基于遺傳算法的PCB板元件檢測 學(xué) 院:信息科學(xué)與工程學(xué)院專 業(yè):控制科學(xué)與工程班 級:研141班學(xué) 號:201404703028學(xué)生姓名:牛洪芳日 期:二一四年十二月基于遺傳算法的PCB板元件檢測摘 要：隨著PCB板制造工藝的發(fā)展，電路板上焊接的各種器件越來越多，發(fā)生焊接錯誤的概率也越來越高。如果在檢驗過程中不能將這些問題找出來，勢必在PCB板調(diào)試和應(yīng)用過程中留下安全隱患。本文針對目前檢測方法中的一些不足，提出了一種新的檢測方法，即通過圖像模板匹配法逐個檢測PCB板上元器件，詳細描述了PCB板元器件檢測的基本原理，并使用基于FPAG硬件平臺的代間差分遺傳算法對圖像搜索匹

2、配過程進行優(yōu)化，顯著降低了系統(tǒng)的成本以及設(shè)計復(fù)雜度，同時也為遺傳算法的實對應(yīng)用開辟了新的思路和方法。關(guān)鍵詞：PCB板元件；遺傳算法；FPGAThe Application of Genetic Algorithm in Detecting Printed Circuit Board ComponentsAbstract: With the development of the manufacture technology of the PCB, there are more and more apparatus that need to be sealed on the electronic

3、board, which leads to higher possibility of sealing error. If these problems cannot be found out, there will necessarily be hidden security trouble in the process of the debugging and application of the PCB. In this paper a new method of testing is proposed to be against the disadvantages of the pre

4、sent testing methods, which is to test components on the PCB one by one based on the image template matching method. The fundamental theory of the PCB components testing is described in detail, and an optimization is made to the image template matching process using the IDGA based on the FPGA platfo

5、rm, which greatly reduces the cost of the system and the complexity of the system design, at the same time a new way and method of the real time application of GA is brought out. Key Words: PCB components; genetic algorithm; FPGA引言印刷電路板的生產(chǎn)需要經(jīng)過多道工序，在焊接元器件這道工序由于焊接元器件種類多、數(shù)量大，是最易發(fā)生疏漏的地方。尤其當需要在板上焊接較多元器件時

6、，更易發(fā)生漏焊和焊接錯誤。如果在檢驗過程中不能將這些問題找出來，勢必在PCB板調(diào)試和使用過程中留下安全隱患。目前通常使用兩種方法來檢測PCB板上元件安裝質(zhì)量。一種方法是采用人工檢測的方法，顯然這種方法速度慢、效率低，無法滿足較大規(guī)模生產(chǎn)的需求，同時也無法保證檢測質(zhì)量。另一種方法就是采用計算機視覺檢測技術(shù)1來實現(xiàn)PCB板元件的自動檢測。本文提出了一種新的檢測方法，即通過圖像模板匹配法2對PCB板上每個元件進行逐個檢測。1. PCB板元件檢測的基本原理PCB板的生產(chǎn)需要經(jīng)過多道工序，在焊接元器件這道工序，由于焊接元器件種類多、數(shù)量大，容易發(fā)生漏焊和焊接錯誤。依靠傳統(tǒng)的人工檢驗方法容易發(fā)生疏漏，檢驗

7、速度也無法滿足大規(guī)模生產(chǎn)的需要。所以一般采用圖像模板匹配的方法來實現(xiàn)PCB板元件的自動檢測。其基本原理是將該器件表面圖像作為圖像模板，檢測需要焊接該器件的區(qū)域是否存在與圖像模板相類似的圖像，從而來判斷該區(qū)域元器件焊接是否正確。該算法無需對圖像進行分割和特征提取處理，而只在原始圖像數(shù)據(jù)上進行運算，從而保留了圖像的全部信息。圖像模板匹配方法通常采用全局搜索法，即將模板與搜索圖作逐點匹配運算，這種搜索匹配模塊的計算量是非常大的，為了減少計算量，本文使用簡單遺傳算法對其進行優(yōu)化，加快其檢測速度。以檢測電阻為例，檢測的目的是檢查PCB板上應(yīng)焊接某一阻值電阻的區(qū)域是否焊接了其他阻值的電阻或者發(fā)生漏焊。例如

8、在規(guī)定的坐標上應(yīng)焊接5l歐姆電阻，那么就需檢測該區(qū)域是否焊接了該阻值的電阻，有沒有發(fā)生焊接了其他阻值電阻的情況，或者發(fā)生漏焊的情況。如圖1所示，以該阻值電阻的數(shù)字圖像“510”作為圖像模板T，取應(yīng)焊接該電阻區(qū)域的圖像作為搜索圖I。圖1 模版T和搜索圖I圖像匹配算法利用相關(guān)函數(shù)來計算兩幅圖像的相關(guān)系數(shù)值。設(shè)搜索圖I的像素為PQ，模板T的像素為MN，在搜索圖I上取像素為MN的子圖Sx,y，(x, y)為這塊子圖左上角像素點在搜索圖I中的坐標。模板T和子圖Sx,y的相似程度用D(x, y)表示， (1)其中Sx,y(m, n)和T(m, n)分別為子圖Sx,y和模板T中坐標(m, n)對應(yīng)的圖像像素

9、值。展開(1)式， (2)(2)式右邊的第l項是子圖Sx,y的能量，與(x, y)有關(guān)：第3項是模板T的能量，在模板確定時為一個常數(shù)，第2項是子圖Sx,y與模板T的互相關(guān)，模板T與子圖Sx,y匹配時這一項的取值最大。由此可以使用歸一化相關(guān)函數(shù)作為模板和子圖的相似性度量； (3)計算搜索圖I中每個子圖Sx,y與模板T的相關(guān)函數(shù)R(x, y)的值，即從左上角第一個子圖開始，從左往右、從上往下每次移動一個像素，計算得到整個圖像的一個相關(guān)曲面，如圖2所示：圖2 圖像的相關(guān)曲面圖從圖2中不難發(fā)現(xiàn)，相關(guān)函數(shù)R(x, y)的值大于0.6，且在多個區(qū)域內(nèi)具有大于0.8的較高峰值，使得整個分布呈多極值分布，這樣

10、的分布采用遺傳算法進行優(yōu)化容易出現(xiàn)局部收斂的情況，增加誤檢測的概率，因此本文將歸一化相關(guān)函數(shù)R(x, y)做如下改進； (4)(4)式表示子圖Sx,y中所有像素值的平均值，表示模板T中所有像素值的平均值。2. 簡單遺傳算法(SGA)的實現(xiàn)如果采用全局搜索匹配子圖的方法， 需要計算ent(P-M)(Q-N)0.5)個子圖與模板的匹配程度，用歸一化相關(guān)函數(shù)求圖像匹配的計算量非常大，顯然需要花費大量的搜索時間。而其中除匹配子圖外，其余計算都是無效計算，因此可利用遺傳算法快速尋優(yōu)、魯棒性強的特點進行優(yōu)化，加快檢測速度。 簡單遺傳算法，即首先對欲求解問題進行編碼，基于這種編碼方式，隨機產(chǎn)生一組染色體作為

11、進化起點的第一代群體，并且計算每個個體的適應(yīng)度值。接著從這些個體中通過一定的選擇策略選擇個體作為父本，使用雜交算子和變異算子對父本進行交叉和變異，這樣通過選擇和繁殖就產(chǎn)生了下一代種群。反復(fù)上述選擇和繁殖過程，直到找到達到適應(yīng)度閾值的染色體，即目標最優(yōu)解。由于一般情況下，實數(shù)編碼比二進制編碼直觀、方便，同時更能有效克服采用二進制編碼帶來的例如漢明懸崖3等一系列問題，所以本文中編碼方案選擇實數(shù)編碼。選擇策略中應(yīng)用最為廣泛的是輪盤賭選擇策略，但是采用輪盤賭選擇策略需計算群體中每個個體的相對適應(yīng)度值，當種群規(guī)模較大時，這種計算會帶來不小的計算量，所以本文中采用錦標賽選擇策略。錦標賽選擇策略如圖3所示，

12、先從當代種群中，隨機選取2個個體作為一組，比較兩個個體的適應(yīng)度值，保留適應(yīng)度值高的個體，放入父代種群中。然后不斷的從當代種群中隨機選取一組個體，把適應(yīng)度值高的個體放入父代種群中。最后對父代種群應(yīng)用雜交算子，生成新一代種群(子代種群)。圖3 錦標賽選擇策略流程圖錦標賽選擇策略由于在選擇時與個體適應(yīng)度值的絕對大小不成直接比例，所以可以在一定程度上避免超級個體的影響，同時這種選擇策略使得適應(yīng)度值高的個體具有比較大的選擇概率，不至于在選擇過程中被淘汰。3. 簡單遺傳算法的應(yīng)用如圖1所示的搜索圖I的像素為PQ，模板像素為MN。要進行搜索的空間由搜索圖I中所有的子圖Sx,y全體構(gòu)成，子圖即對應(yīng)遺傳算法種群

13、中的個體。對于每個子圖Sx,y使用其左上角像素點的坐標(x, y)表示，顯然采用實數(shù)編碼比較直觀方便，更能克服采用二進制編碼帶來的倒如漢明懸崖等一系列問題。則遺傳算法種群中的個體用坐標的編碼可以表示為：r=(x, y)，其中x1, P-M，Y1，Q-N。為了防止近親繁殖，即在選擇產(chǎn)生的父代種群中同一個體或者相近個體太多，影響到產(chǎn)生的子代種群的多樣性，引入漢明距離d去判斷個體之間的差異。由于種群中個體的編碼為在圖像中像素的坐標點，所以兩個個體ri(x, y)和rj(x, y）之間的漢明距離定義為： (5)設(shè)定漢明距離d的閾值為3，相近個體規(guī)模數(shù)的閾值為2。將新選擇出來的個體ri與父代中已經(jīng)存在的

14、個體rj計算漢明距離di,j若父代中有一個個體rj與新選擇出來的個體ri計算出來的di,j小于3，則將相近個體規(guī)模數(shù)k加1。若k大于2，則說明新選擇出來的個體ri在父代中已經(jīng)存在一定的規(guī)模，直接淘汰，不放入父代種群中：若k小于2，則將該個體放入父代種群中。 適應(yīng)度函數(shù)采用(4)式改進歸一化相關(guān)函數(shù)，通過(4)式計算種群中每個個體的適應(yīng)度值。相關(guān)函數(shù)R(x, y)的值只有在圖像匹配區(qū)域附近具有較高的峰值，其余區(qū)域的峰值都低于于0.4。通過分析，本文假定其他阻值的搜索圖和模板具有相類似的適應(yīng)度值分布情況。因此可以將匹配相關(guān)度閾值設(shè)為0.85，只要種群中某個個體的適應(yīng)度值高于匹配相關(guān)度閾值，即可認為

15、找到該匹配圖像。4. 簡單遺傳算法的實驗結(jié)果簡單遺傳算法(SGA)采用的參數(shù)如下：種群數(shù)目為50，雜交概率為0.8，變異概率為0.01，匹配相關(guān)度閾值為0.85。本例采用粗定位后的圖像進行檢測，將待測元件定位于在一定的圖像內(nèi)，以保證其圖像的分辨率，以檢測如圖1所示的搜索圖I為例，搜索圖I的像素為384288，模板T的像素為130X70。由于子圖Sx,y完全包含于搜索圖中，所以子圖Sx,y左上角坐標額定取值范圍為：x1,384-130，Y1,288-70，即x1,254，Y1,218。首先隨機產(chǎn)生50個像素坐標，得到50個子圖，采用(4)式計算每個子圖與模板T的匹配相關(guān)度值，即為這50個像素坐標

16、的適應(yīng)度值。然后采用上述的錦標賽選擇策略、實數(shù)編碼雜交算子和均勻性變異算子，產(chǎn)生新一代種群，同樣含有50個像素坐標。接著繼續(xù)計算新的子圖和模板T的匹配相關(guān)度值，如此循環(huán)往復(fù)。若在某一代中有一個像素坐標的匹配相關(guān)度值高于0.85，即適應(yīng)度值高于0.85，認為檢測到匹配圖像，表示焊接正確。若在限定的最大進化代數(shù)中，未有一個像素坐標的適應(yīng)度值高于0.85，認為焊接錯誤。適應(yīng)度值評估函數(shù)會對簡單遺傳算法的收斂速度有明顯的影響，即對搜索匹配模板圖像的速度有明顯的影響。圖4、圖5表示采用簡單遺傳算法，使用不同適應(yīng)度值評估函數(shù)的檢測結(jié)果，圖4采用歸一化相關(guān)函數(shù)(3)式作為目標函數(shù)對搜索圖I進行10 000次

17、檢測的結(jié)果。圖5采用改進歸一化相關(guān)函數(shù)(4)式作為目標函數(shù)對搜索圖I進行10 000次檢測的結(jié)果。其中橫坐標表示檢測次數(shù)，縱坐標表示每次檢測所需的進化代數(shù)。進化代數(shù)達到設(shè)定的最大進化代數(shù)，表示在搜索圖I上未檢測到模板T，發(fā)生一次誤檢。圖4 歸一化相關(guān)函數(shù)作為目標函數(shù)的仿真結(jié)果圖5 改進歸一化相關(guān)函數(shù)作為目標函數(shù)的仿真結(jié)果對圖4和5進行統(tǒng)計，得到如表1所示的統(tǒng)計結(jié)果。表1中列出了最大進化代數(shù)分別設(shè)為100、80和60代時，10 000次檢測中發(fā)生誤檢的次數(shù)和概率。表1 簡單遺傳算法的統(tǒng)計結(jié)果目標函數(shù)每次檢測平均進化代數(shù)檢測10000次發(fā)生誤檢次數(shù)誤檢概率/%100代80代60代100代80代60

18、代歸一化相關(guān)函數(shù)30.1683651655160.651.655.16改進歸一化相關(guān)函數(shù)22.2685601353560.601.353.56從表中可以看出，使用了改進歸一化相關(guān)函數(shù)后，檢測的平均速度明顯加快，誤檢概率降低。5. 結(jié)論本文主要研究的是PCB板元器件安裝質(zhì)量檢測的問題。針對目前檢測過程中的一些不足，提出了一種新的檢測方法，即通過圖像模板匹配法逐個檢測PCB板上元器件，并采用遺傳算法對整個檢測過程進優(yōu)化。通過對遺傳算法各種編碼方案、選擇策略、交叉策略、變異策略、適應(yīng)度函數(shù)和遺傳算法終止法則的研究，本文采用實數(shù)編碼、錦標賽選擇策略、普通雜交算子和均勻性變異算子，具體實現(xiàn)了簡單遺傳算法

19、(SGA)，并采用簡單遺傳算法(SGA)對圖像搜索匹配過程進行優(yōu)化，驗證了簡單遺傳算法可以有效優(yōu)化圖像匹配搜索過程，加快檢測的速度。但同時發(fā)現(xiàn)簡單遺傳算法存在明顯的不足，即收斂速度慢，導(dǎo)致有比較高的誤檢概率。參考文獻1 魯昌華，徐勝海，劉春數(shù)字圖像處理技術(shù)在PCB板檢測中的應(yīng)用J儀器儀表學(xué)報，2001，22(4)：426-4282 Kenneth RCastlemanDigital Image ProcessingM1北京：清華大學(xué)出版社，20033 Michalewicz Z. Genetic algorithms + data structures = evolution programs M. Bedim: Springer-Veflag Berlin Heidelberg, 19964 張利，高永英，汪浩，吳國威PCB板檢測中的定位研究J中國圖像圖形學(xué)報，1999，4(8)：659-6615 JIN Cheng, WEI Chen, LI Chen