基于參數(shù)化變形模板的圓形引腳元件視覺定位

王祖進(jìn)，黃筱調(diào)，顧萍萍

?

基于參數(shù)化變形模板的圓形引腳元件視覺定位

王祖進(jìn)1，黃筱調(diào)1，顧萍萍2

(1. 南京工業(yè)大學(xué)機(jī)械與動力工程學(xué)院，江蘇南京，210009；2. 南京康尼機(jī)電股份有限公司，江蘇南京，210038)

通過分析圓形引腳元件的圖像特征，提出一種基于參數(shù)化變形模板的貼片元件偏轉(zhuǎn)角度與偏移量檢測方法。根據(jù)元件引腳的排列形式構(gòu)建變形模板，采用5個(gè)參數(shù)表征變形模板的平移、偏轉(zhuǎn)和縮放。結(jié)合圖像的梯度、灰度以及幾何特征定義變形模板的能量函數(shù)，采用遺傳算法對能量函數(shù)進(jìn)行優(yōu)化搜索，找到變形模板和目標(biāo)圖像的最佳匹配位置。研究結(jié)果表明：該方法具有很好的準(zhǔn)確性和穩(wěn)定性，對偏移量的檢測誤差小于0.25個(gè)像素，對偏轉(zhuǎn)角度的檢測誤差小于0.07°，滿足貼片機(jī)對視覺系統(tǒng)定位算法的精度要求。

視覺定位；變形模板；貼片機(jī)；亞像素；遺傳算法

隨著貼片元件的微型化以及引腳間距的密集化，芯片貼裝領(lǐng)域?qū)N片機(jī)視覺系統(tǒng)的精度提出了更高的要求，因此，必須建立精度更高的視覺定位算法。貼片機(jī)視覺系統(tǒng)定位算法主要包括貼片元件定位算法和印刷電路板(PCB)定位算法2個(gè)部分，其中貼片元件定位是對貼片元件中心相對于吸嘴中心的偏移量和貼片元件在拾取過程中的偏轉(zhuǎn)角度進(jìn)行檢測；PCB板定位是通過對母板上的定位標(biāo)志進(jìn)行檢測，進(jìn)而得到PCB板坐標(biāo)系與機(jī)器坐標(biāo)系之間的轉(zhuǎn)換關(guān)系。眾多學(xué)者對貼片機(jī)視覺系統(tǒng)的相關(guān)算法[1?2]進(jìn)行了研究，但對偏移量和偏轉(zhuǎn)角度的檢測基本都是分開進(jìn)行的，很少將兩者結(jié)合起來考慮，研究對象多為片式元件和矩形引腳元件，對圓形引腳元件定位的研究較少，且大多以檢測元件的幾何特征為目標(biāo)，處理對象為各個(gè)像素點(diǎn)，定位的精度只能達(dá)到像素級。為此，本文作者提出一種基于參數(shù)化變形模板[3?6]的圓形引腳元件視覺定位算法。該方法基于球柵陣列(BGA)元件的引腳排列形式構(gòu)建變形模板，利用模板的邊緣特征、模板所包含的像素點(diǎn)特征以及模板的幾何特征定義能量函數(shù)，運(yùn)用遺傳算法對能量函數(shù)進(jìn)行優(yōu)化搜索。實(shí)驗(yàn)證明，該算法具有很好的穩(wěn)定性和準(zhǔn)確性，能夠同時(shí)檢測圓形引腳元件的偏移量和偏轉(zhuǎn)角度，且檢測精度都達(dá)到了亞像素級別。

1 圖像預(yù)處理

首先采用自動閾值法對原灰度圖像進(jìn)行二值化，以簡化后續(xù)的計(jì)算。然后采用2×2的結(jié)構(gòu)元對圖像進(jìn)行二值形態(tài)學(xué)開運(yùn)算，以剔除引腳邊緣上的毛刺點(diǎn)，即8連通鄰域內(nèi)只有1個(gè)亮點(diǎn)的邊緣點(diǎn)。預(yù)處理后的元件圖像如圖1所示。

(a) 原灰度圖像；(b) 預(yù)處理后圖像

2 參數(shù)化變形模板

圓形引腳元件的引腳幾何排列較規(guī)則，有著明確的先驗(yàn)知識。所以，本文用1組參數(shù)定義變形模板，這組參數(shù)包含了元件引腳的位置、大小和形狀等先驗(yàn)知識。

以圖1中的圓形引腳元件圖像為例，設(shè)計(jì)了圖2所示的參數(shù)化變形模板。圖2中：以圖像的(0, 0)點(diǎn) 作為坐標(biāo)原點(diǎn)；為元件的偏轉(zhuǎn)角度；為引腳間距；(，)為左上角第1個(gè)引腳的圓心坐標(biāo)。

圖2 參數(shù)化變形模板模型

模板中每個(gè)引腳的圓心坐標(biāo)可表示為

式中：和為引腳所在位置；0＜≤；0＜≤；和為模板的行列數(shù)。模板中每個(gè)引腳的邊緣坐標(biāo)可表示為

式中：為元件引腳半徑；∈[0, 2π]。

由上述分析可知：該變形模板可以用參數(shù)向量=(,,,,)來描述。其中：和為模板的平移；和為模板的縮放；為模板的偏轉(zhuǎn)。

設(shè)，，和這4點(diǎn)的坐標(biāo)分別為(1,1)，(2,2)，(3,3)和(,)，點(diǎn)為左上角第1個(gè)引腳的圓心坐標(biāo)，點(diǎn)繞圖像中心旋轉(zhuǎn)角后得到點(diǎn)，點(diǎn)偏移(Δ, Δ)后得到點(diǎn)，點(diǎn)為圖像的中心點(diǎn)。圖3所示為幾何變換坐標(biāo)圖。令=，則由圖3可得：

則最終的偏移量為

3 變形模板能量函數(shù)

能量函數(shù)是變形模板最重要的特征，表征了圖像和變形模板之間的匹配程度，動態(tài)調(diào)整描述參數(shù)使得能量函數(shù)取得最大值或最小值以實(shí)現(xiàn)最佳的位置匹配。能量函數(shù)由內(nèi)部能量函數(shù)和外部能量函數(shù)組成，內(nèi)部能量考慮變形模板和實(shí)際輪廓之間的偏差，外部能量考慮一些具體的圖像特征。分析圓形引腳元件圖像的特征，以圖像的梯度約束能量和灰度約束能量作為外部能量，以幾何形狀約束能量作為內(nèi)部能量。

圖像的梯度約束能量定義為模板邊緣輪廓上圖像梯度的負(fù)平均值，即

式中：為模板的邊緣輪廓線；為模板邊緣輪廓線的長度；(,)為模板邊緣輪廓線上點(diǎn)(,)梯度。

對于數(shù)字圖像，為了簡化計(jì)算用羅伯特絕對值來近似表示梯度函數(shù)，即

(7)

梯度約束能量表征模板邊緣輪廓線和目標(biāo)圖像的邊緣之間距離的遠(yuǎn)近，當(dāng)模板輪廓線接近目標(biāo)圖像的邊緣時(shí)，此項(xiàng)約束能量達(dá)到最小。

圖像的灰度約束能量定義為模板內(nèi)部的圖像灰度的負(fù)平均值，即

式中：為模板的封閉區(qū)域；為模板的面積；(,)為模板封閉區(qū)域內(nèi)點(diǎn)(,)的灰度。

灰度約束能量表征模板對目標(biāo)圖像的包含程度，當(dāng)模板與目標(biāo)圖像匹配時(shí)，該約束能量達(dá)到最小。

幾何形狀約束能量定義為模板的形狀及大小的約束綜合加權(quán)即

式中，0和0為模板的初始參數(shù)；1和2為各項(xiàng)的權(quán)值。

幾何形狀約束能量可以約束模板的形狀，避免模板的形狀和目標(biāo)圖像的形狀偏離過大。

模板的總能量為

(10)

式中：gradient，grey和geometry為3個(gè)能量項(xiàng)的權(quán)值。

4 搜索空間限定

為了提高優(yōu)化搜索的速度，需要對搜索空間進(jìn)行縮小，將搜索空間限定在一定的范圍內(nèi)。本文通過對引腳連通區(qū)域進(jìn)行標(biāo)記[7?8]來估算各優(yōu)化參數(shù)的取值范圍。采用形態(tài)學(xué)膨脹運(yùn)算對每個(gè)引腳的連通區(qū)域進(jìn)行標(biāo)記。由于每個(gè)引腳的連通區(qū)域之間的間隙寬度至少為1個(gè)像素，所以采用3×3的結(jié)構(gòu)元，以確保每次膨脹都不會產(chǎn)生位于其他連通區(qū)域內(nèi)的點(diǎn)，然后把膨脹后的圖像和原始圖像相交，就能把膨脹限制在連通區(qū)域的內(nèi)部。具體步驟如下。

1) 隨機(jī)選取原始圖像中某個(gè)連通區(qū)域內(nèi)的1個(gè)亮點(diǎn)0。

2) 采用3×3的結(jié)構(gòu)元0對0進(jìn)行膨脹運(yùn)算，膨脹后的結(jié)果與原始圖像相交得到1，重復(fù)進(jìn)行膨脹運(yùn)算與相交運(yùn)算，直到B+1== B，1個(gè)連通區(qū)域標(biāo)記完成。為該連通區(qū)域分配1個(gè)唯一的編號，并將輸出圖像中該連通區(qū)域內(nèi)的所有像素點(diǎn)賦值為該區(qū)域的編號，從原始圖像中刪除已標(biāo)記的連通區(qū)域。

3) 重復(fù)上述步驟，直到原始圖像中再無亮點(diǎn)為止，至此所有的連通區(qū)域標(biāo)記完畢。

計(jì)算每個(gè)連通區(qū)域的中心點(diǎn)。設(shè)，和3個(gè)點(diǎn)為圓形引腳元件1個(gè)角上的引腳的圓心，坐標(biāo)分別為(,)，(1,1)和(2,2)，點(diǎn)為圖像的(0, 0)點(diǎn)，則由圖2可得：

2點(diǎn)間距離的計(jì)算公式為

則可得

的取值范圍為0°~15°，則由正余弦曲線可得

即4個(gè)角上的引腳圓心坐標(biāo)到圖像上對應(yīng)的4個(gè)角點(diǎn)的距離最短。由此可以定位左上角第1個(gè)引腳的圓心和右上角第1個(gè)引腳的圓心。

以點(diǎn)坐標(biāo)作為(,)的估計(jì)值(0,0)，以和這2點(diǎn)構(gòu)成的直線的傾角作為的估計(jì)值0，以和這2點(diǎn)間的距離的1/12作為的估計(jì)值0，以2個(gè)連通區(qū)域半徑的均值作為的估計(jì)值0，則5個(gè)參數(shù)的搜索范圍為

5 優(yōu)化算法

本文采用遺傳算法對參數(shù)化變形模板的能量函數(shù)進(jìn)行計(jì)算機(jī)優(yōu)化。遺傳算法[9?10]是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，具有很強(qiáng)的全局搜索能力，能夠處理復(fù)雜的優(yōu)化問題，能以很大的概率找到全局最優(yōu)解。算法的流程如下。

1) 采用二進(jìn)制方式對模板參數(shù)進(jìn)行編碼，，，和分別以3位字符表示，以7位字符表示，種群個(gè)體的長度為各變量的位數(shù)之和，即19。

2) 生成個(gè)初始種群，初始種群的取值范圍限定在上面估計(jì)的5個(gè)參數(shù)的搜索范圍內(nèi)。

3) 計(jì)算每個(gè)個(gè)體的能量函數(shù)值和適應(yīng)度。為了避免出現(xiàn)負(fù)能量函數(shù)值和防止過早收斂，本文采用Baker設(shè)計(jì)的適應(yīng)度計(jì)算公式，即按照個(gè)體的能量函數(shù)值由大到小進(jìn)行排序，能量函數(shù)值越小的個(gè)體，排序越靠后，適應(yīng)度也就越高。則適應(yīng)度的計(jì)算如下：

式中：x為個(gè)體的排序位置；為選擇壓差。

4) 通過選擇、交叉、變異等操作產(chǎn)生新的個(gè)體。采用隨機(jī)遍歷抽樣法對個(gè)體進(jìn)行選擇，交叉算子采用單點(diǎn)交叉，變異算子采用單點(diǎn)基本位變異。

5) 重復(fù)步驟3)和4)，若相鄰兩代能量函數(shù)值的均值之差小于1個(gè)很小的值或者進(jìn)化代數(shù)達(dá)到設(shè)定的閾值，則算法終止。適應(yīng)度最高的個(gè)體即為最終的匹配結(jié)果。某次匹配的結(jié)果如圖4所示。

圖4 圓形引腳元件匹配結(jié)果

6 實(shí)驗(yàn)結(jié)果及分析

采用如圖1所示的P?LFBGA144?1111?0.80型BGA芯片作為研究對象對定位算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。初始種群規(guī)模=100，交叉概率為0.9，變異概率為0.05，代溝為1，最大進(jìn)化代數(shù)為100，0=24，0=6，=0.005，=2。經(jīng)過多次實(shí)驗(yàn)總結(jié)，得到5個(gè)權(quán)值的取值為1=2=0.5，gradient=0.4和grey=geometry=0.3。對具有不同偏移量和偏轉(zhuǎn)角度的元件進(jìn)行檢測，檢測的結(jié)果如表1所示。表1中：ΔX和ΔY為偏移量理論值；θ為偏轉(zhuǎn)角度的理論值；ΔX和ΔY為偏移量實(shí)際檢測值；θ為偏轉(zhuǎn)角度的實(shí)際檢測值1和2為偏移量檢測誤差；3為偏轉(zhuǎn)角度的檢測誤差。

對1幅元件圖像重復(fù)實(shí)驗(yàn)10次，實(shí)際偏移量為 [2 2]，偏轉(zhuǎn)角度為5°，將實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)分析，檢測結(jié)果如表2所示。表2中，min為誤差的最小值，max為誤差的最大值，mean為誤差的平均值，std為誤差的方差。

由表1可得：本文定位算法對偏移量的檢測誤差小于0.25個(gè)像素，對偏轉(zhuǎn)角度的檢測誤差小于0.07°，達(dá)到了亞像素精度。由表2可以看出：本文所采用的優(yōu)化方法具有很好的穩(wěn)定性。由于實(shí)驗(yàn)中的偏移量和偏轉(zhuǎn)角度是通過相關(guān)的算法實(shí)現(xiàn)的，與實(shí)際情況存在一定的偏差，所以最終得到的誤差比實(shí)際情況下的誤差小，但滿足貼片機(jī)對偏移量誤差小于0.5個(gè)像素和偏轉(zhuǎn)角度誤差小于0.1°的精度要求。

表1 檢測結(jié)果

表2 重復(fù)檢測結(jié)果

7 結(jié)論

1) 本文提出的基于參數(shù)化變形模板的圓形引腳元件定位算法具有很好的準(zhǔn)確性和穩(wěn)定性，算法以元件的圓形引腳來構(gòu)建變形模板，在優(yōu)化搜索的過程中，兼顧了所有的圓形引腳。此外，通過采用效果更好的圖像預(yù)處理方法可以進(jìn)一步提高定位的精度。

2) 基于參數(shù)化變形模板的定位算法的關(guān)鍵在于能量函數(shù)的定義和優(yōu)化算法參數(shù)的選擇，本文定義的能量函數(shù)能夠很好地表征模板和目標(biāo)圖像的匹配程度，遺傳算法的各個(gè)參數(shù)是通過多次實(shí)驗(yàn)得到的，如何自適應(yīng)地選擇優(yōu)化算法的參數(shù)和提高優(yōu)化的速度還需進(jìn)一步研究。

[1] 解楊敏，劉強(qiáng). 高精度自動貼片機(jī)視覺系統(tǒng)定位算法研究[J]. 光學(xué)技術(shù)，2008, 34(3): 449?454. XIE Yangmin, LIU Qiang. Research on locating algorithm of vision alignment system in automatic high precision chip mounter[J]. Optical Technique, 2008, 34(3): 449?454.

[2] 張舞杰，李迪，葉峰. 基于視覺的貼片元件檢測算法[J]. 華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010, 38(1): 65?69. ZHANG Wujie, LI Di, YE Feng. Vision-based inspection algorithm for chip components[J].Journal of South China University of Technology (Natural Science Edition), 2010, 38(1): 65?69.

[3] 劉國傳, 陸琳, 汪琳. 食源性微生物檢測基因芯片圖象自動識別方法的初步研究[J]. 儀器儀表學(xué)報(bào), 2009, 30(3): 641?646. LIU Guochuan, LU Lin, WANG Lin. Preliminary study on microarray automatic spot identification method[J]. Chinese Journal of Scientific Instrument, 2009, 30(3): 641?646.

[4] Al-Mamun H A, Jahangir N, Islam M S, et al. Eye detection in facial image by genetic algorithm driven deformable template matching[J]. International Journal of Computer Science and Network Security, 2009, 9(8): 287?294.

[5] 牛軼峰, 沈林成. 基于變形模板的多目標(biāo)識別與定位[J]. 電子與信息學(xué)報(bào)，2006, 28(6): 1026?1030. NIU Yifeng, SHEN Lincheng. Multiple target recognition and location using deformable templates in downward looking image[J]. Journal of Electronics & Information Technology, 2006, 28(6): 1026?1030.

[6] LI Yali, WANG Shengjin, DING Xiaoqing. Eye/eyes tracking based on a unified deformable template and particle filtering[J]. Pattern Recognition Letters, 2010, 31(11): 1377?1387.

[7] He L, Chao Y, Suzuki K, et al. Fast connected-component labeling[J]. Pattern Recognition, 2009, 42(9): 1977?1987.Author Vitae

[8] Wu K, Otoo E, Suzuki K. Optimizing two-pass connected- component labeling algorithms[J]. Pattern Analysis and Applications, 2009, 12(2): 117?135.

[9] De Giovanni L, Pezzella F. An improved genetic algorithm for the distributed and flexible job-shop scheduling problem[J]. European Journal of Operational Research, 2010, 200(2): 395?408.

[10] LI Shijin, WU Hao, WAN Dingsheng, et al. An effective feature selection method for hyper spectral image classification based on genetic algorithm and support vector machine[J]. Knowledge- Based Systems, 2011, 24(1): 40?48.

(編輯 羅金花)

Visual positioning for round pin chips based on parametric deformable template

WANG Zujin1, HUANG Xiaodiao1, GU Pingping2

(1. College of Mechanical and Power Engineering, Nanjing University of Technology, Nanjing 210009, China;2. Nanjing Kangni Mechanical & Electrical Co. Ltd., Nanjing 210038, China)

A detection method of the deflection angle and the offset using the parametric deformable template was proposed based on the analysis of the image features of round pin chips. A deformable template was constructed according to the arrangement of pins. The offset, deflection and zoom of the deformable template were denoted with 5 parameters. Image gradient, gray and geometry features were combined to define an energy function, and genetic algorithm was used to optimize the energy function to find the best matching position between the deformable template and a target image. The results show that this method has good accuracy and stability, the detection errors of the offset are less than 0.25 pixels, and the detection errors of the deflection are less than 0.07°, which can meet the positioning accuracy of placement machine vision system.

visual positioning; deformable template; placement machine; sub-pixel; genetic algorithm

10.11817/j.issn.1672-7207.2015.09.016

TP391.4

A

1672?7207(2015)09?3274?05

2014?11?21；

2015?01?28

國家自然科學(xué)基金資助項(xiàng)目(51175242)；江蘇省科技成果轉(zhuǎn)化專項(xiàng)基金資金項(xiàng)目(BA2012031)；江蘇省普通高校研究生科研創(chuàng)新計(jì)劃項(xiàng)目(CXZZ13_0436) (Project(51175242) supported by the National Natural Science Foundation of China; Project(BA2012031) supported by the Science and Technology Foundation of Jiangsu Province; Project(CXZZ13_0436) supported by the College Graduate Research and Innovation Program of Jiangsu Province)

黃筱調(diào)，教授，博士生導(dǎo)師，從事數(shù)控理論與技術(shù)、機(jī)電一體化技術(shù)、先進(jìn)制造技術(shù)等研究；E-mail: ngdwzj@126.com