東苗

(上海行健職業(yè)學(xué)院 信息技術(shù)與機(jī)電工程系， 上海 200070)

0 引言

自動(dòng)光學(xué)檢測(cè)(Automated Optical Inspection，AOI)是基于光學(xué)原理獲取被測(cè)對(duì)象的照明圖像并數(shù)字化，采用計(jì)算機(jī)進(jìn)行圖像分析，用于對(duì)焊接生產(chǎn)中遇到的常見缺陷進(jìn)行檢測(cè)和處理[1]。近年來，AOI已廣泛應(yīng)用在印刷電路板(Printed Circuit Board，PCB)組裝質(zhì)量檢測(cè)中。在圖像采集時(shí)，受到CCD視野、測(cè)量精度的要求等因素的影響，需要將整張PCB劃分成多個(gè)檢測(cè)窗，通過移動(dòng)CCD或PCB的方式進(jìn)行多次數(shù)據(jù)采集來完成取像工作。在傳統(tǒng)的檢測(cè)方法中多采用順序取像法，依次取像后再進(jìn)行拼接得到全局圖像。其優(yōu)點(diǎn)是CCD移動(dòng)控制簡(jiǎn)單，但是取像次數(shù)較多、圖像拼接難度大、測(cè)量精度較低[2]。因此必須對(duì)檢測(cè)窗的位置和移動(dòng)路徑進(jìn)行合理規(guī)劃[3]，以確保圖像采集的效率。選取檢測(cè)窗位置時(shí)需要以待檢測(cè)對(duì)象在PCB上的二維坐標(biāo)信息為屬性，以CCD視場(chǎng)(Field of View, FOV)大小作為約束條件，對(duì)待檢測(cè)目標(biāo)進(jìn)行區(qū)域聚類劃分。結(jié)果中聚類的個(gè)數(shù)即檢測(cè)窗的個(gè)數(shù)，聚類的大小與FOV的尺寸差異即檢測(cè)窗位置的容差。將檢測(cè)窗位置容差與CCD移動(dòng)次序進(jìn)行組合求解確定檢測(cè)窗位置及拍攝序列。

蟻群算法(Ant Colony Optimization, ACO)是一種群體智能優(yōu)化算法，在20世紀(jì)90年代由Dorigo M最早提出并將其應(yīng)用于解決經(jīng)典的路徑規(guī)劃旅行商問題(TSP)。蟻群算法具有強(qiáng)烈的正反饋和分布并行能力，但是由于初期信息素匱乏導(dǎo)致在搜索初期具有很強(qiáng)的盲目性，搜索速度變慢，容易陷入局部最優(yōu)解。粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)通過每個(gè)粒子在解空間內(nèi)追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)值，具有較強(qiáng)的并行搜索能力和較快的全局搜索速度，但存在計(jì)算后期容易陷入局部最優(yōu)，收斂速度慢的缺點(diǎn)。

本文算法混合的思路是在前期利用粒子群算法快速的全局收斂性能進(jìn)行初步搜索，在一定次數(shù)的迭代后找到問題的次優(yōu)解，然后用求得的次優(yōu)解初始化蟻群算法的信息素矩陣，提高收斂速度，改善蟻群算法初期搜索的盲目性和易陷入局部最優(yōu)的問題，從而找到問題的全局最優(yōu)解。

1 檢測(cè)窗的劃分

劃分檢測(cè)窗時(shí)需要滿足以下條件：以最少的檢測(cè)窗來覆蓋所有的檢測(cè)目標(biāo)，而且窗口的大小必須小于或等于FOV的大小；為提高檢測(cè)精度，每個(gè)檢測(cè)目標(biāo)只能唯一地被包含在一個(gè)檢測(cè)窗中。為了解決本問題，在約束條件下對(duì)待檢測(cè)目標(biāo)進(jìn)行聚類，聚類結(jié)果中類別的個(gè)數(shù)即檢測(cè)窗個(gè)數(shù)。

1.1 檢測(cè)窗劃分的數(shù)學(xué)模型

假定PCB上共有m個(gè)待檢測(cè)目標(biāo)，規(guī)劃后共有n個(gè)檢測(cè)窗。

所有待檢測(cè)目標(biāo)的集合,如式(1)。

O={oi|1≤i≤m}

(1)

規(guī)劃后檢測(cè)窗的集合，如式(2)。

A={aj|1≤j≤n}

(2)

目標(biāo)函數(shù)如式(3)。

Min(n)

(3)

聚類的約束條件為式(4)。

(4)

式中，Pij表示檢測(cè)窗j是否包含檢測(cè)目標(biāo)i；Qji表示檢測(cè)目標(biāo)j是否被檢測(cè)窗i訪問過；Wi和Hi分別表示檢測(cè)窗i的長度和寬度；WFOV和HFOV分別表示FOV的長度和寬度[4]。

1.2 ISODATA算法

迭代自組織數(shù)據(jù)(Iterative Self-Organizing Data，ISODATA)算法在K-均值算法的基礎(chǔ)上，根據(jù)設(shè)定的分類條件不斷地對(duì)聚類進(jìn)行合并和分割，移動(dòng)聚類的中心來自我調(diào)整，直至相鄰兩次迭代的聚類中心不再變化為止[4]。在本問題中應(yīng)用改進(jìn)的ISODATA算法，基本步驟如下。

步驟1 初始化，從左上角開始將PCB板用FOV大小的網(wǎng)格覆蓋，每一個(gè)網(wǎng)格作為一個(gè)初始聚類；

步驟2 刪除不包含任何檢測(cè)目標(biāo)的無效網(wǎng)格；

步驟3 對(duì)每個(gè)聚類，重新修正它的中心坐標(biāo)，使其包含更多的待檢測(cè)目標(biāo)；

步驟4 對(duì)每個(gè)聚類，縮小它的幾何尺寸，使之達(dá)到最??；

步驟5 在網(wǎng)格大小必須小于或等于FOV尺寸的前提下，將相鄰的幾個(gè)網(wǎng)格合并以組成新的網(wǎng)格；

步驟6 如果存在檢測(cè)目標(biāo)不屬于任何網(wǎng)格，則新增網(wǎng)格來包含它們；

步驟7 重復(fù)步驟3—步驟6直到?jīng)]有可以合并的網(wǎng)格，也沒有遺漏的檢測(cè)目標(biāo)。

改進(jìn)的ISODATA聚類算法流程圖如圖1所示。

圖1 改進(jìn)的ISODATA聚類算法流程圖

2 CCD移動(dòng)路徑規(guī)劃

完成檢測(cè)窗的劃分之后，CCD應(yīng)當(dāng)找到一條盡可能最短的移動(dòng)路徑以提高檢測(cè)效率，此過程與經(jīng)典的旅行商問題(Traveling Salesman Problem,TSP)相類似，其不同之處在于：由前一步的ISODATA算法流程可知，聚類結(jié)果的范圍均小于或等于FOV的尺寸，所以檢測(cè)窗中心點(diǎn)的位置存在容差R。因此在進(jìn)行路徑規(guī)劃時(shí)不僅要考慮CCD移動(dòng)的次序，還需要在每個(gè)檢測(cè)窗中心可移動(dòng)的范圍內(nèi)調(diào)整中心位置，以減少總的路徑長度[5]。

2.1 CCD移動(dòng)路徑規(guī)劃的數(shù)學(xué)模型

以下針對(duì)該問題建立數(shù)學(xué)模型，本問題的目標(biāo)函數(shù)如式(5)。

(5)

式中，n表示檢測(cè)窗的個(gè)數(shù)，Tcam表示CCD拍攝一張圖像的時(shí)間(常數(shù))；dij表示相機(jī)從第ai個(gè)檢測(cè)窗中心(拍攝點(diǎn))移動(dòng)到第aj個(gè)檢測(cè)窗中心的時(shí)間；zij表示移動(dòng)路徑中ai和aj是否相鄰,如式(6)。

(6)

對(duì)于檢測(cè)窗集合：A={ai|1≤i≤n}中的任意ai，其取像位置容差Ri的范圍為式(7)。

(7)

2.2 粒子群與蟻群混合算法

粒子群與蟻群混合算法步驟如圖2所示。

圖2 粒子群與蟻群混合算法流程圖

步驟1 算法開始，初始化種群中各粒子的位置和速度；

假設(shè)一個(gè)由N個(gè)粒子組成的粒子群分布在一個(gè)D維空間中，粒子i(i=1,2,…,N)在空間中的位置表示為：Xi=(x1,x2,…,xD)，粒子i的速度定義為粒子在D維空間中每次迭代走過的距離，表示為：Vi=(v1,v2,…,vD)。

步驟2 代入粒子位置和速度，評(píng)價(jià)每個(gè)粒子的適應(yīng)度；

在路徑規(guī)劃問題中，移動(dòng)距離最短是首要考慮的目標(biāo)，因此將路徑總長度作為粒子的適應(yīng)度函數(shù)。

步驟3 更新個(gè)體極值和群體極值；

在每一次迭代中，粒子i在時(shí)間(t+1)速度和位置更新為式(8)、式(9)。

vid(t+1)=ωvid(t)+c1r1[Pid-xid(t)]+

c2r2[Pgd-xid(t)]

(8)

xid(t+1)=xid(t)+vid(t),d=1,2,…,D

(9)

式中,vid(t)為粒子i第d維的當(dāng)前速度；xid(t)為粒子i第d維的當(dāng)前位置；Pid為個(gè)體極值；Pgd為全局極值；c1、c2為加速常數(shù)；r1、r2為0～1之間均勻分布的隨機(jī)數(shù)；ω為慣性權(quán)重。

步驟4 如果滿足約束條件(達(dá)到最大迭代次數(shù))進(jìn)入步驟5，否則返回步驟2；

步驟5 初始化蟻群參數(shù)，使用粒子群算法得到的次優(yōu)解對(duì)蟻群算法的信息素矩陣分布進(jìn)行初始化[6],如式(10)。

τs=c+τp

(10)

式中，c為一個(gè)信息素常數(shù)；τp為由粒子群算法得到的初始信息素增量。將粒子群算法得到的次優(yōu)解區(qū)域范圍作為主要信息素分布區(qū)域，并將每一點(diǎn)的最佳適應(yīng)度值作為蟻群算法的初始信息素增量,如式(11)。

τp=Pgd(j)

(11)

步驟6 將螞蟻隨機(jī)置于任一節(jié)點(diǎn)上，計(jì)算螞蟻轉(zhuǎn)移概率，并選擇下一步路徑；

當(dāng)螞蟻在t時(shí)刻完成檢測(cè)窗ai的拍攝后，選擇aj作為下一個(gè)拍攝窗口的概率，如式(12)。

(12)

式中，ηij為由ai轉(zhuǎn)移到aj的啟發(fā)信息，即兩檢測(cè)窗的距離對(duì)螞蟻選擇的影響；τij(t)為t時(shí)刻，從ai到aj的路徑上的信息素濃度；α分別為啟發(fā)信息ηij對(duì)路徑選擇概率的影響參數(shù)；β為信息素τij對(duì)路徑選擇概率的影響參數(shù)；allowedk為螞蟻k下一步允許到達(dá)的檢測(cè)窗集合，在此集合中包含螞蟻k尚未到達(dá)的所有檢測(cè)窗的集合，保證所有檢測(cè)窗均經(jīng)歷且只經(jīng)歷一次。

步驟7 逐次逼近調(diào)整檢測(cè)窗位置；

每只螞蟻完成一次循環(huán)后，考慮本次路徑中各個(gè)檢測(cè)窗的可移動(dòng)范圍。如圖3所示，若選擇移動(dòng)路徑A-B-C，則移動(dòng)檢測(cè)窗B的中心位置，使A-B-C的路徑最短，然后根據(jù)B-C-D來移動(dòng)檢測(cè)窗C的中心位置，使B-C-D的路徑最短……重復(fù)直到經(jīng)過所有檢測(cè)窗。這樣計(jì)算得到本次路徑的最短距離，并用于計(jì)算更新各分支路徑的信息素[3]，如圖3所示。

步驟8 更新信息素濃度；

當(dāng)經(jīng)過n個(gè)時(shí)刻，m只螞蟻均遍歷整條路徑后，更新各條路段上的信息素,如式(13)、式(14)。

τij(t+n)=ρ×τij(t)+Δτij

(13)

(14)

(15)

式中，Lk為螞蟻k完成本次遍歷的路徑長度；Q為常數(shù)。

步驟9 如果滿足約束條件(達(dá)到最大循環(huán)次數(shù))，程序結(jié)束，輸出最優(yōu)解；否則返回步驟6。

3 實(shí)驗(yàn)仿真結(jié)果與分析

為了驗(yàn)證本文算法的有效性，在給定參數(shù)下進(jìn)行仿真實(shí)驗(yàn)。相機(jī)FOV的尺寸為12 mm×10 mm，如果尺寸為226 mm×90 mm，則包含1 128個(gè)待測(cè)對(duì)象的PCB上進(jìn)行測(cè)試。獲取每個(gè)待檢測(cè)對(duì)象的坐標(biāo)信息后首先利用改進(jìn)的ISODATA聚類算法進(jìn)行檢測(cè)窗的劃分,如圖4、圖5所示。

圖4 待檢測(cè)PCB

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

得到檢測(cè)窗劃分結(jié)果之后分別采用標(biāo)準(zhǔn)蟻群算法以及本文算法對(duì)CCD的移動(dòng)路徑進(jìn)行規(guī)劃，分析算法性能的差別。在蟻群算法中，設(shè)定群體規(guī)模等于檢測(cè)窗個(gè)數(shù)、啟發(fā)信息因子α=1.0、信息素濃度因子β=5.0、軌跡持久性因子ρ=0.3、最大迭代次數(shù)iter=100；在粒子群與蟻群混合算法中，首先設(shè)定使用粒子群算法迭代50次得到次優(yōu)解后，根據(jù)式(10)、(11)初始化蟻群算法中的信息素分布，再使用蟻群算法進(jìn)行優(yōu)化。

蟻群算法在第78次迭代時(shí)收斂，最短路徑為14 127 mm，粒子群與蟻群混合算法在第31次迭代時(shí)收斂，最短路徑為12 673 mm；同時(shí)從迭代過程可以看出，由于混合算法的信息素矩陣分布由次優(yōu)解進(jìn)行初始化，改善了搜索初期的盲目性，因此混合算法的起點(diǎn)較高。

為進(jìn)一步驗(yàn)證粒子群與蟻群混合算法的算法性能，繼續(xù)在不同規(guī)格的PCB上進(jìn)行測(cè)試。

使用粒子群與蟻群混合算法可以得到最短的規(guī)劃路徑，而且混合算法得到最優(yōu)解所需的迭代次數(shù)最少，收斂速度最快,如圖6、圖7和表1所示。

表1 取像路徑優(yōu)化仿真實(shí)驗(yàn)結(jié)果

4 總結(jié)

本文采用改進(jìn)的ISODATA聚類算法進(jìn)行檢測(cè)窗劃分，然后采用粒子群與蟻群混合算法進(jìn)行取像路徑的優(yōu)化。在混合算法的第一階段采用粒子群算法，利用粒子群算法前期收斂的快遞性和全局性得到問題的次優(yōu)解，用次優(yōu)解初始化蟻群算法中的信息素分布，充分發(fā)揮蟻群算法的局部尋優(yōu)能力，考慮了檢測(cè)窗口的可移動(dòng)范圍從而縮短了路徑長度。使用不同規(guī)格的PCB進(jìn)行實(shí)驗(yàn)，混合算法在求解性能上均優(yōu)于標(biāo)準(zhǔn)蟻群算法，驗(yàn)證了本文算法的可行性和有效性。