基于高斯金字塔與新粒子群的印刷電路板裝配模板匹配算法

閆 河，李曉玲，謝 敏，趙其峰，劉倫宇

(1.重慶理工大學 計算機科學與工程學院，重慶 400054；2.重慶理工大學 兩江人工智能學院，重慶 401135)

0 引言

隨著電子技術的進步，印刷電路板裝配(Printed Circuit Board Assembly, PCBA)趨于微型化、密集化，導致元器件的裝配定位、尺寸測量和分割等工作非常困難，其中元器件目標區(qū)域檢測是定位、測量和分割的首要問題。目標區(qū)域檢測的準確性直接影響后續(xù)定位、測量和分割精度；準確性低容易出現(xiàn)錯檢、漏檢情況，導致定位、測量和分割結果偏差較大。提高目標定位、測量和分割精度及計算實時性，是PCBA產(chǎn)線非常重要的任務。

機器視覺檢測系統(tǒng)通常采用模板匹配方法檢測目標區(qū)。模板匹配方法是在源圖像中找到與模板圖像相關性最大的位置，因此可以根據(jù)相關性建立一個全局優(yōu)化問題，采用優(yōu)化技術找到最優(yōu)匹配位置。近年來，有許多學者將粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法應用于模板匹配領域[1-2]。TAVARES等[3]采用PSO算法搜尋最佳匹配位置，利用PSO算法概率搜索特性減少匹配次數(shù)，降低相關性計算量，從而縮短匹配時間；MAOGUO等[4]考慮到PSO算法參數(shù)少、收斂速度較快，將其用于高階圖匹配。然而，經(jīng)典PSO算法容易過早收斂而陷入局部解[5-6]，匹配準確性不高。因此有學者對影響粒子群優(yōu)化的參數(shù)、位置和速度進行改進。SHI等[7]提出線性調整權重的PSO算法，平衡了算法搜索能力；姜建國等[8]采用自適應學習因子在不同搜索階段自動調整合適的學習因子，使粒子能更好地學習靠近最優(yōu)解；馮浩等[9]通過引入活力因子提出一種名為自適應變異粒子群優(yōu)化算法(Adaptive Mutation Particle Swarm Optimization, AMPSO)算法的改進PSO算法，其能有效激發(fā)失活粒子跳出局部最優(yōu)解，從而提升算法的全局尋優(yōu)能力；楊延西等[10]引入混沌映射，提出混沌粒子群優(yōu)化(Chaos Particle Swarm Optimization, CPSO)算法，增加了粒子群的多樣性，使算法全局尋優(yōu)能力得到進一步提升。

雖然改進的PSO算法性能都有提升，但是匹配的準確性和實時性仍然較低?？紤]到圖像高斯金字塔變換(Gaussian Pyramid Transformation, GPT)匹配算法[11]采用遍歷匹配方法保證了匹配的準確性，但是耗時較長，PSO算法準確性較低，但運算時間較短，而實際應用中對PCBA目標區(qū)域檢測的準確性和實時性都有較高要求，可以結合兩種算法進行互補。因此，本文提出一種GPT與新PSO算法結合的PCBA模板匹配算法，該算法結合GPT與新PSO算法，利用圖像GPT匹配算法的遍歷匹配方法提高匹配準確性，利用新PSO算法改變搜索策略進一步縮短匹配時間。實驗表明，本文算法能較好地滿足PCBA視覺檢測的要求。

1 標準粒子群優(yōu)化算法

PSO算法是群體智能優(yōu)化算法中的一種，是通過模擬鳥群捕食的信息傳遞行為提出的優(yōu)化算法[12]，該算法具有群體智能的局部和全局搜索能力且參數(shù)較少。

假設在一個K維空間中，粒子數(shù)為m，根據(jù)式(1)和式(2)初始化粒子群的位置和移動速度：

Xi=LX×rand；

(1)

Vi=LV×rand。

(2)

式中：LX和LV分別為粒子群的位置和移動速度的邊界值；rand為均勻分布的隨機數(shù)。

進行到t次迭代時，第i個粒子在空間中的位置表示為Xi(t)=(xi1,xi2,…,xiK)，飛行速度表示為Vi(t)=(vi1,vi2,…,viK),適應度值表示為Pi(t)=(pi1,pi2,…,piK)，其中i=1,2,3,…,m。根據(jù)適應度值選擇粒子個體中的最大值作為最優(yōu)解Pbest(t)，將群體中搜索到的最優(yōu)解記為gbest(t)，根據(jù)如下速度和位置動態(tài)調整公式對粒子進行更新：

Vi(t+1)=ωVi+c1r1(Pbest(t)-Xi(t))

+c2r2(gbest(t)-Xi(t))；

(3)

Xi(t+1)=Xi(t)+Vi(t+1)；

(4)

Pbest(t)=max{Pi(j)|1≤j≤t}；

(5)

gbest(t)=max{Pbest(j)|1≤j≤t}。

(6)

式中：ω為慣性權重；t和T分別為第t次迭代和最大迭代次數(shù)；c1為個體學習因子，c2為群體學習因子，一般取值為2；r1和r2均為屬于[0,1]范圍內互不干擾的隨機數(shù)。

2 高斯金字塔變換與新粒子群優(yōu)化算法結合的匹配算法

2.1 新粒子群優(yōu)化算法

雖然PSO算法參數(shù)少、簡單易用，但是容易陷入局部最優(yōu)，且粒子尋優(yōu)能力與參數(shù)變化密切相關[13]。因此，本文對標準參數(shù)變化提出以下改進，從而提出一種新PSO算法。

2.1.1 慣性權重

慣性權重是粒子移動的重要影響因子之一。對于PSO算法，慣性權重較大時全局尋優(yōu)能力強，慣性權重較小時局部尋優(yōu)能力強。SHI等[7]對慣性權重采用線性遞減的方式調整，雖然有效提高了算法性能，但是算法迭代前期慣性權重值遞減速度較快，容易使算法陷入局部最優(yōu)。針對該問題，采用黃洋等[14]提出的倒Sigmod函數(shù)衰減方式進行調整，使慣性權值在前期和后期緩慢變化。具體公式為

(7)

式中：ωmax和ωmin為慣性權重的最大值和最小值；a和b表示非線性調整系數(shù)，a=3.4，b=0.07；t為迭代次數(shù)。這種變換方法可以讓慣性權值在算法迭代前期和后期能用較長時間取得較大值和較小值來平衡全局和局部搜索能力，但是粒子群依賴個體競爭與群體協(xié)作尋優(yōu)，僅調整慣性權值不能更好地發(fā)揮搜索性能。

2.1.2 自適應學習因子

學習因子c1，c2的變化分別影響個體和群體粒子向最優(yōu)解靠近。迭代前期較大概率依賴粒子個體的移動經(jīng)驗進行全局搜索，迭代后期主要依賴群體的移動經(jīng)驗進行局部搜索。傳統(tǒng)PSO算法采用固定的學習因子，無法在不同階段更好地引導個體和群體向最優(yōu)解靠近。因此根據(jù)PSO算法的特性，PSO算法在迭代前期學習因子c1取較大值、c2取較小值能增強全局搜索能力，后期c1取較小值、c2取較大值能增強局部搜索能力。為了在不同階段更好地發(fā)揮全局和局部搜索能力，采用自適應的學習因子，關系如下：

(8)

(9)

2.1.3 隨機動量因子

雖然對參數(shù)影響因子進行動態(tài)調整能有效提高尋優(yōu)能力，但是無法完全避免過早收斂陷入局部解。方差能夠表現(xiàn)數(shù)據(jù)離散程度的特性，判別粒子是否收斂陷入局部解，如式(10)所示；為了使粒子擴大搜索范圍并跳出局部解，引入隨機動量因子λ進行擾動，如式(11)所示。

(10)

Xi(t)=λLX。

(11)

2.2 高斯金字塔變換與新粒子群優(yōu)化結合算法

圖像匹配通常采用由粗到精的方式來保證匹配的準確性，將圖像GPT匹配算法由粗到精的分層匹配思想和新PSO算法結合可以進一步提高匹配效果。在不同圖像層采用由粗到精的匹配方式能夠彌補新PSO算法準確性不高的問題，而新PSO算法可以替代圖像GPT的遍歷式匹配，進一步加快計算速度，兩種算法相輔相成，可以達到較好的效果。本文算法首先對待匹配圖像和模板子圖進行高斯金字塔變換，在變換后的待匹配圖像頂層子圖中采用新PSO算法搜索粗匹配區(qū)域，在后續(xù)層的鄰域范圍內進行逐像素精匹配，其中GPT通過圖像與高斯函數(shù)多次卷積后獲得圖像的低通濾波，然后進行二次下采樣產(chǎn)生不同尺寸的圖像塔，詳細構造過程參見文獻[15]。本文算法具體步驟如下：

步驟1設置金字塔層數(shù)為L，分別對待匹配圖像和模板圖像進行高斯金字塔變換。

步驟2在待匹配圖像變換后的L層子圖中采用新PSO算法搜索粗匹配區(qū)域，新PSO算法搜索的詳細過程如下：

(1)初始化PSO算法參數(shù)，即種群個數(shù)m、空間維度K、迭代次數(shù)T。

(2)根據(jù)式(1)和式(2)初始化粒子群的位置和移動速度，將NCC系數(shù)[16]作為適應度值Pi，然后根據(jù)式(5)和式(6)找出個體和群體的初始最優(yōu)值。

(3)根據(jù)式(3)～式(11)更新粒子的移動速度、位置、個體最優(yōu)值和群體最優(yōu)值。

(4)若t=T，則算法運行結束，將群體最優(yōu)值反變換傳入L-1層;否則執(zhí)行(3)。

步驟3設置鄰域大小為n×n，在鄰域范圍內將相同層的模板子圖與待匹配子圖逐像素匹配，找到最佳匹配位置。

步驟4若L=0，則算法結束，輸出匹配區(qū)域；否則執(zhí)行步驟3。

3 實驗結果及分析

為了驗證本文算法(對比試驗中簡稱Our Proposed)的有效性，將上述方法與PSO算法[7]、AMPSO算法[9]、CPSO算法[10]、GPT算法[11]進行比較。實驗環(huán)境為：Intel(R)Core(TM)i5=8300H CPU、8 G內存、Windows 10操作系統(tǒng)、MATLAB R2018a。

3.1 運行時間比較

圖1所示為測試圖像，其中：圖1a為待匹配圖像，尺寸為484×800；圖1b為模板圖像，尺寸為95×95。保持圖1b左上角坐標不變，按照10個像素遞增另取4種大小分別為105×105，115×115，125×125，135×135的模板圖像，在每種尺寸下分別進行20次實驗來比較5種算法的平均運行時間。本文算法參數(shù)設置為粒子數(shù)m=80、最大迭代次數(shù)T=80，L=4，K=2，n=5，實驗結果如表1所示。

表1 運行時間比較 s

由表1可見，相同尺寸下，本文算法的運行時間明顯低于其他算法。隨著尺寸的增大，PSO和AMPSO算法時間的增幅在0.17 s～0.28 s內，CPSO算法時間的增幅在0.37 s～0.55 s內，GPT算法時間的增幅在0.1 s～0.38 s內，本文算法時間的增幅在0 s～0.01 s內，驗證了本文算法的實時性。

3.2 匹配準確性比較

匹配準確性通常采用模板圖像和待匹配圖像的重疊率[17]衡量。分別采用3.1節(jié)的5種算法在測試圖像的5種尺寸下進行50次試驗，比較匹配的準確性。實驗結果如圖2、圖3和表2所示。

表2 準確性比較

由圖2可見，本文算法的準確性明顯高于其他4種算法。表2所示為不同算法的準確性比較，可見在無噪聲干擾下，AMPSO算法和CPSO算法的匹配率比傳統(tǒng)PSO算法提升了28.8%和19.2%，本文算法比AMPSO算法、CPSO算法、GPT算法提升了22.8%，32.4%，1.6%，驗證了本文算法在保證實時性的情況下，比其他算法的匹配準確性更高。

3.3 魯棒性比較

為了驗證本文算法在保證匹配準確性和實時性的情況下還具有魯棒性，在3.1節(jié)5種測試圖像中加入方差為0.01～0.1的高斯白噪聲，分別對5種算法在不同尺寸下進行30次實驗，比較每種尺寸加入10級噪聲后的平均匹配率，實驗結果如圖4所示。對比實驗結果可知，在添加不同程度的高斯白噪聲下，本文算法的平均匹配準確率為99.58%，明顯高于其他4種算法，表明該方法同時具有魯棒性。

4 結束語

為提高PCBA中目標區(qū)域檢測的準確性和實時性，提出GPT與新PSO算法結合的PCBA模板匹配算法，不僅可以提高PCBA檢測的準確性，還能加快運行速度、保證實時性，同時具有較好的魯棒性。本文提出一種新的PSO算法，該算法采用倒Sigmod函數(shù)調整粒子群慣性權值，分別構建個體和群體的自適應學習因子模型，同時提出粒子是否陷入局部解的自適應判據(jù)并對粒子采用隨機動量因子進行調整，然后與高斯金字塔相結合，在不同層采用由粗到精的匹配方式，不但提高了匹配準確性和實時性，而且具有較好的魯棒性。實驗表明，本文算法在計算速度、匹配準確性或魯棒性的任一方面，均比經(jīng)典PSO算法、相關改進算法和圖像金字塔算法有顯著提升，驗證了本文算法應用在PCBA目標區(qū)域檢測中的有效性?？紤]到多目標區(qū)域檢測的情況，后續(xù)將對本文算法進行進一步改善，以提升算法性能和適用性，使算法能更好應用于PCBA目標區(qū)域檢測。