DOI: 10.11817/j.issn.1672-7207.2015.09.016

基于参数化变形模板的圆形引脚元件视觉定位

王祖进¹，黄筱调¹，顾萍萍²

(1. 南京工业大学 机械与动力工程学院，江苏 南京，210009；

2. 南京康尼机电股份有限公司，江苏 南京，210038)

摘要：通过分析圆形引脚元件的图像特征，提出一种基于参数化变形模板的贴片元件偏转角度与偏移量检测方法。根据元件引脚的排列形式构建变形模板，采用5个参数表征变形模板的平移、偏转和缩放。结合图像的梯度、灰度以及几何特征定义变形模板的能量函数，采用遗传算法对能量函数进行优化搜索，找到变形模板和目标图像的最佳匹配位置。研究结果表明：该方法具有很好的准确性和稳定性，对偏移量的检测误差小于0.25个像素，对偏转角度的检测误差小于0.07°，满足贴片机对视觉系统定位算法的精度要求。

关键词：视觉定位；变形模板；贴片机；亚像素；遗传算法

中图分类号：TP391.4             文献标志码：A         文章编号：1672-7207(2015)09-3274-05

Visual positioning for round pin chips based on parametric deformable template

WANG Zujin¹, HUANG Xiaodiao¹, GU Pingping²

(1. College of Mechanical and Power Engineering, Nanjing University of Technology, Nanjing 210009, China;

2. Nanjing Kangni Mechanical & Electrical Co. Ltd., Nanjing 210038, China)

Abstract: 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.

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

随着贴片元件的微型化以及引脚间距的密集化，芯片贴装领域对贴片机视觉系统的精度提出了更高的要求，因此，必须建立精度更高的视觉定位算法。贴片机视觉系统定位算法主要包括贴片元件定位算法和印刷电路板(PCB)定位算法2个部分，其中贴片元件定位是对贴片元件中心相对于吸嘴中心的偏移量和贴片元件在拾取过程中的偏转角度进行检测；PCB板定位是通过对母板上的定位标志进行检测，进而得到PCB板坐标系与机器坐标系之间的转换关系。众多学者对贴片机视觉系统的相关算法^[1-2]进行了研究，但对偏移量和偏转角度的检测基本都是分开进行的，很少将两者结合起来考虑，研究对象多为片式元件和矩形引脚元件，对圆形引脚元件定位的研究较少，且大多以检测元件的几何特征为目标，处理对象为各个像素点，定位的精度只能达到像素级。为此，本文作者提出一种基于参数化变形模板^[3-6]的圆形引脚元件视觉定位算法。该方法基于球栅阵列(BGA)元件的引脚排列形式构建变形模板，利用模板的边缘特征、模板所包含的像素点特征以及模板的几何特征定义能量函数，运用遗传算法对能量函数进行优化搜索。实验证明，该算法具有很好的稳定性和准确性，能够同时检测圆形引脚元件的偏移量和偏转角度，且检测精度都达到了亚像素级别。

1  图像预处理

首先采用自动阈值法对原灰度图像进行二值化，以简化后续的计算。然后采用2×2的结构元对图像进行二值形态学开运算，以剔除引脚边缘上的毛刺点，即8连通邻域内只有1个亮点的边缘点。预处理后的元件图像如图1所示。

图1  图像预处理

Fig. 1  Image preprocessing

2  参数化变形模板

圆形引脚元件的引脚几何排列较规则，有着明确的先验知识。所以，本文用1组参数定义变形模板，这组参数包含了元件引脚的位置、大小和形状等先验知识。

以图1中的圆形引脚元件图像为例，设计了图2所示的参数化变形模板。图2中：以图像的(0, 0)点   作为坐标原点；θ为元件的偏转角度；d为引脚间距；(x，y)为左上角第1个引脚的圆心坐标。

图2  参数化变形模板模型

Fig. 2  Model of a parametric deformable template

模板中每个引脚的圆心坐标可表示为

        (1)

式中：i和j为引脚所在位置；0＜i≤m；0＜j≤n；m和n为模板的行列数。模板中每个引脚的边缘坐标可表示为

              (2)

式中：r为元件引脚半径；φ∈[0, 2π]。

由上述分析可知：该变形模板可以用参数向量I=(x, y, d, r, θ)来描述。其中：x和y为模板的平移；d和r为模板的缩放；θ为模板的偏转。

设A，B，C和D这4点的坐标分别为(x₁, y₁)，(x₂, y₂)，(x₃, y₃)和(a, b)，A点为左上角第1个引脚的圆心坐标，A点绕图像中心旋转θ角后得到B点，B点偏移(Δx, Δy)后得到C点，D点为图像的中心点。图3所示为几何变换坐标图。令L=，则由图3可得：

               (3)

          (4)

则最终的偏移量为

      (5)

图3  几何变换坐标图

Fig. 3  Coordinate diagram of geometric transformation

3  变形模板能量函数

能量函数是变形模板最重要的特征，表征了图像和变形模板之间的匹配程度，动态调整描述参数使得能量函数取得最大值或最小值以实现最佳的位置匹配。能量函数由内部能量函数和外部能量函数组成，内部能量考虑变形模板和实际轮廓之间的偏差，外部能量考虑一些具体的图像特征。分析圆形引脚元件图像的特征，以图像的梯度约束能量和灰度约束能量作为外部能量，以几何形状约束能量作为内部能量。

图像I的梯度约束能量定义为模板边缘轮廓上图像梯度的负平均值，即

            (6)

式中：L为模板的边缘轮廓线；l为模板边缘轮廓线的长度；G(x, y)为模板边缘轮廓线上点(x, y)梯度。

对于数字图像，为了简化计算用罗伯特绝对值来近似表示梯度函数，即

            (7)

梯度约束能量表征模板边缘轮廓线和目标图像的边缘之间距离的远近，当模板轮廓线接近目标图像的边缘时，此项约束能量达到最小。

图像I的灰度约束能量定义为模板内部的图像灰度的负平均值，即

                 (8)

式中：S为模板的封闭区域；s为模板的面积；g(x, y)为模板封闭区域内点(x, y)的灰度。

灰度约束能量表征模板对目标图像的包含程度，当模板与目标图像匹配时，该约束能量达到最小。

几何形状约束能量定义为模板的形状及大小的约束综合加权即

      (9)

式中，D₀和 R₀为模板的初始参数；w₁和w₂为各项的权值。

几何形状约束能量可以约束模板的形状，避免模板的形状和目标图像的形状偏离过大。

模板的总能量为

           (10)

式中：w_gradient，w_grey和w_geometry为3个能量项的权值。

4  搜索空间限定

为了提高优化搜索的速度，需要对搜索空间进行缩小，将搜索空间限定在一定的范围内。本文通过对引脚连通区域进行标记^[7-8]来估算各优化参数的取值范围。采用形态学膨胀运算对每个引脚的连通区域进行标记。由于每个引脚的连通区域之间的间隙宽度至少为1个像素，所以采用3×3的结构元，以确保每次膨胀都不会产生位于其他连通区域内的点，然后把膨胀后的图像和原始图像相交，就能把膨胀限制在连通区域的内部。具体步骤如下。

1) 随机选取原始图像中某个连通区域内的1个亮点B₀。

2) 采用3×3的结构元S₀对B₀进行膨胀运算，膨胀后的结果与原始图像相交得到B₁，重复进行膨胀运算与相交运算，直到B_i+1== B_i，1个连通区域标记完成。为该连通区域分配1个唯一的编号，并将输出图像中该连通区域内的所有像素点赋值为该区域的编号，从原始图像中删除已标记的连通区域。

3) 重复上述步骤，直到原始图像中再无亮点为止，至此所有的连通区域标记完毕。

计算每个连通区域的中心点。设A，B和C 3个点为圆形引脚元件1个角上的引脚的圆心，坐标分别为(x, y)，(x₁, y₁)和(x₂, y₂)，O点为图像的(0, 0)点，则由图2可得：

               (11)

             (12)

             (13)

2点间距离的计算公式为

           (14)

则可得

        (15)

θ的取值范围为0°~15°，则由正余弦曲线可得

                    (16)

即4个角上的引脚圆心坐标到图像上对应的4个角点的距离最短。由此可以定位左上角第1个引脚的圆心A和右上角第1个引脚的圆心D。

以A点坐标作为(x, y)的估计值(x₀, y₀)，以A和B这2点构成的直线的倾角作为θ的估计值θ₀，以A和D这2点间的距离的1/12作为d的估计值d₀，以2个连通区域半径的均值作为r的估计值r₀，则5个参数的搜索范围为

                    (17)

5  优化算法

本文采用遗传算法对参数化变形模板的能量函数进行计算机优化。遗传算法^[9-10]是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法，具有很强的全局搜索能力，能够处理复杂的优化问题，能以很大的概率找到全局最优解。算法的流程如下。

1) 采用二进制方式对模板参数进行编码，x，y，d和r分别以3位字符表示，θ以7位字符表示，种群个体的长度为各变量的位数之和，即19。

2) 生成N个初始种群，初始种群的取值范围限定在上面估计的5个参数的搜索范围内。

3) 计算每个个体的能量函数值和适应度。为了避免出现负能量函数值和防止过早收敛，本文采用Baker设计的适应度计算公式，即按照个体的能量函数值由大到小进行排序，能量函数值越小的个体，排序越靠后，适应度也就越高。则适应度的计算如下：

          (18)

式中：x_i为个体i的排序位置；p为选择压差。

4) 通过选择、交叉、变异等操作产生新的个体。采用随机遍历抽样法对个体进行选择，交叉算子采用单点交叉，变异算子采用单点基本位变异。

5) 重复步骤3)和4)，若相邻两代能量函数值的均值之差小于1个很小的值δ或者进化代数达到设定的阈值，则算法终止。适应度最高的个体即为最终的匹配结果。某次匹配的结果如图4所示。

图4  圆形引脚元件匹配结果

Fig. 4  Matching result of a round pin chip

6  实验结果及分析

采用如图1所示的P-LFBGA144-1111-0.80型BGA芯片作为研究对象对定位算法进行实验验证。初始种群规模N=100，交叉概率为0.9，变异概率为0.05，代沟为1，最大进化代数为100，D₀=24，R₀=6，δ=0.005， p=2。经过多次实验总结，得到5个权值的取值为w₁=w₂=0.5，w_gradient=0.4和w_grey=w_geometry=0.3。对具有不同偏移量和偏转角度的元件进行检测，检测的结果如表1所示。表1中：ΔX_t和ΔY_t为偏移量理论值；θ_t为偏转角度的理论值；ΔX_e和ΔY_e为偏移量实际检测值；θ_e为偏转角度的实际检测值；e₁和e₂为偏移量检测误差；e₃为偏转角度的检测误差。

对1幅元件图像重复实验10次，实际偏移量为  [2 2]，偏转角度为5°，将实验结果进行统计分析，检测结果如表2所示。表2中，M_min为误差的最小值，M_max为误差的最大值，M_mean为误差的平均值，M_std为误差的方差。

由表1可得：本文定位算法对偏移量的检测误差小于0.25个像素，对偏转角度的检测误差小于0.07°，达到了亚像素精度。由表2可以看出：本文所采用的优化方法具有很好的稳定性。由于实验中的偏移量和偏转角度是通过相关的算法实现的，与实际情况存在一定的偏差，所以最终得到的误差比实际情况下的误差小，但满足贴片机对偏移量误差小于0.5个像素和偏转角度误差小于0.1°的精度要求。

表1  检测结果

Table 1  Detection results

表2  重复检测结果

Table 2  Sensitivity analysis results

7  结论

1) 本文提出的基于参数化变形模板的圆形引脚元件定位算法具有很好的准确性和稳定性，算法以元件的圆形引脚来构建变形模板，在优化搜索的过程中，兼顾了所有的圆形引脚。此外，通过采用效果更好的图像预处理方法可以进一步提高定位的精度。

2) 基于参数化变形模板的定位算法的关键在于能量函数的定义和优化算法参数的选择，本文定义的能量函数能够很好地表征模板和目标图像的匹配程度，遗传算法的各个参数是通过多次实验得到的，如何自适应地选择优化算法的参数和提高优化的速度还需进一步研究。

参考文献：

[1] 解杨敏，刘强. 高精度自动贴片机视觉系统定位算法研究[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.

(编辑  罗金花)

收稿日期：2014-11-21；修回日期：2015-01-28

基金项目(Foundation item)：国家自然科学基金资助项目(51175242)；江苏省科技成果转化专项基金资金项目(BA2012031)；江苏省普通高校研究生科研创新计划项目(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)

通信作者：黄筱调，教授，博士生导师，从事数控理论与技术、机电一体化技术、先进制造技术等研究；E-mail: ngdwzj@126.com