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

?

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

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

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

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

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

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

1 圖像預處理

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

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

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

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

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

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

模板中每個引腳的圓心坐標可表示為

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

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

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

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

則最終的偏移量為

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

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

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

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

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

(7)

梯度約束能量表征模板邊緣輪廓線和目標圖像的邊緣之間距離的遠近，當模板輪廓線接近目標圖像的邊緣時，此項約束能量達到最小。

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

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

灰度約束能量表征模板對目標圖像的包含程度，當模板與目標圖像匹配時，該約束能量達到最小。

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

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

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

模板的總能量為

(10)

式中：gradient，grey和geometry為3個能量項的權值。

4 搜索空間限定

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

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

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

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

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

2點間距離的計算公式為

則可得

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

即4個角上的引腳圓心坐標到圖像上對應的4個角點的距離最短。由此可以定位左上角第1個引腳的圓心和右上角第1個引腳的圓心。

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

5 優(yōu)化算法

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

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

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

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

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

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

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

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

6 實驗結(jié)果及分析

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

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

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

表1 檢測結(jié)果

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

7 結(jié)論

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

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

[1] 解楊敏，劉強. 高精度自動貼片機視覺系統(tǒng)定位算法研究[J]. 光學技術，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]. 華南理工大學學報(自然科學版)，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]. 儀器儀表學報, 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] 牛軼峰, 沈林成. 基于變形模板的多目標識別與定位[J]. 電子與信息學報，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

國家自然科學基金資助項目(51175242)；江蘇省科技成果轉(zhuǎn)化專項基金資金項目(BA2012031)；江蘇省普通高校研究生科研創(chuà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)，教授，博士生導師，從事數(shù)控理論與技術、機電一體化技術、先進制造技術等研究；E-mail: ngdwzj@126.com