基于RANSAC算法的2D Metrology在BGA质量检测中的应用研究

周亚歌，宁爱林

(邵阳学院 机械与能源工程系，湖南 邵阳，422000)



基于RANSAC算法的2D Metrology在BGA质量检测中的应用研究

周亚歌，宁爱林

(邵阳学院 机械与能源工程系，湖南 邵阳，422000)

针对BGA质量检测中芯片图像的识别定位问题，提出了一种基于RANSAC算法的2D Metrology芯片定位方法。首先进行2D Metrology建模，其次添加对象到2D Metrology模型，然后设置2D Metrology模型参数，应用2D Metrology，最后得到2D Metrology模型的对象定位边结果。该方法基于RANSAC算法，能精确识别模型对象中的边缘轮廓特征，简单易行、定位精度高、鲁棒性好、抗干扰能力强。文中通过实验，与常用的基于最小二乘法的芯片定位方法进行对比，验证了该方法的有效性。

BGA检测；2D Metrology ；芯片定位；RANSAC算法

BGA封装技术以其独特的优势:I/O端数量多、贴装失效率低、散热性能好、电路性能稳定、高密度高性能等，使得它在电子行业得到广泛的应用。但由于封装的不可见性，使其检测技术成为工业生产中的难题[1-2]。在实际生产中的BGA质量检测，通常以Tray盘装载待测芯片，利用光学成像原理，基于参考图像来检查锡球平面度、球偏、球径、缺球、球高、正印内容等是否符合要求。

基于参考图像来检测待测芯片的缺陷，需将待测芯片的图像进行变换，使图像中物体的位姿与参考图像中物体的位姿相同[3]。对待测芯片进行定位，拟合边缘直线，找到待测芯片四个角点的精确位置坐标，即可计算出待测芯片四个角点与模板芯片四个角点位置坐标的映射矩阵，为以后映射变换做准备。所找四个角点位置的准确性，直接影响计算出的映射矩阵的准确性，对BGA质量检测结果的影响特别大，故在BGA质量检测中需要采用定位精度高、鲁棒性好、抗干扰能力强的芯片定位方法[4-6]。

目前常用的芯片定位方法大多是基于最小二乘法的直线拟合算法，拟合直线的速度特别快，但是对于远离边缘的离群值鲁棒性不好，很难排除离群数据对拟合结果的影响，故拟合的效果不是特别理想[7-8]。针对这个问题，本文提出了一种基于RANSAC算法的2D Metrology芯片定位方法，定位精度高、鲁棒性好、抗干扰能力强。

1 RANSAC算法

被广泛应用于计算机视觉领域的RANSAC算法，它能从包含大量离群数据的数据集中估计出高精度的模型参数，当离群数据超过一半时仍可得到鲁棒的拟合结果，抗干扰性特别强[9-10]。

1.1 RANSAC算法的基本思想

“RANdom SAmple Consensus(随机抽样一致)”是 RANSAC的英文全拼。它的基本思想可以描述如下：

①从样本集P中随机抽取包含n个样本的P的子集S初始化模型M(n——初始化最小抽样集模型参数所需的最小样本数，集合P的样本数#(P)>n)；

②余集SC=PS中与模型M的误差不超过某一设定容忍阈值t的样本集和子集S构成S*。S*构成S的一致集(S*被认为是内点集)；

③若#(S*)≥N，认为得到正确的模型参数，并利用集S*(inliers)重新计算新的模型M*；重新随机抽取新的S，重复以上过程；

④通过一定次数的迭代，找到最大一致集判断内外点，算法结束，若未找到一致集则算法失败；

1.2 RANSAC算法参数的确定

根据RANSAC算法的基本思想，可知抽样过程中所需确定的参数为：

t——判定数据能否适应模型的容忍阀值

d——判定模型是否适用于数据集的数据数目，表征正确模型的一致集的大小

k——迭代次数

参数t和d可由具体的问题和数据集通过实验确定。参数k从理论结果来推断，设在迭代过程中从数据集内随机选取出的点均为局内点的概率即置信概率为p，每次从数据集中选取一个局内点的概率为w，如下式所示：

w=局内点的数目/数据集内所有数据的总数目

若需要选定n个点估计模型，则 n个点均为局内点的概率为wn，至少有一个点为局内点的概率为1-wn，(1-wn)k表示选择到n个点均为局外点的概率，它和1-p相同。因此，

1-p=(1-wn)k

我们对上式的两边取对数，得出

由此推导出的k值被看作是选取不重复点的上限(因为这个结果是假设n个点都是独立选择的)。为了得到更可信的参数，在k上加上标准偏差或它的乘积。k的标准偏差定义为：

在RANSAC算法计算过程中，要保证抽出的样本在一定的置信概率P条件下一定有一组没有外点的抽样数据，必须选取的抽样集数量非常大。特别当原始数据数量庞大，外点较多时，初始数据的优劣直接决定着RANSAC算法的效率。此时如果先对样本的初始数据进行预检验，剔除一部分外点，优化初始数据，可大大减少迭代次数、提升效率[11]。

2 2DMetrology

2DMetrology，是德国MVtec公司开发的机器视觉方面的专业软件Halcon中的一个算法包，包括add_metrology_object_line_measure、add_metrology_object_circle_measure、add_metrology_object_rectangle2_measure等算子,能够精确找到图像中由圆、椭圆、矩形和直线组成的物体的边缘轮廓。

2.1 2D Metrology基本原理

2DMetrology是使用一个计量模型检测边缘，采用合理的数据模型: 第一，通过调整矩形区域的尺寸，可剔除一部分外点，提高内点在抽样数据中所占的比例；第二，通过调整矩形测量区域的分布函数，合理减少参与RANSAC算法的样本数据的总量，提高随机抽取n个内点组成正确模型的概率(尤其当原始数据数量庞大、边缘点密集的情况下)；第三，通过高斯滤波求导，提取出矩形测量区域内长轴方向上尽可能靠近实际边缘的边缘点，优化数据参数。2D Metrology实质上是一方面合理减少参与RANSAC算法的样本数据的总量，一方面对矩形区域内长轴方向上的边缘点进行预检验，使用优化后的数据参与RANSAC算法的运算，在保证精度的同时，大大减少了RANSAC算法的迭代次数、提升了效率。

2.2 2D Metrology芯片定位方法步骤

(1)创建2D Metrology模型的数据结构：创建一个计量模型，将测量对象(芯片的边缘轮廓)的位置、方向和几何形状的大概值，作为初始参数存储在模型中。

(2)创建矩形测量区域: 建立一系列长轴垂直排列于近似边界的矩形测量区域，尽量使矩形测量区域的中心位于近似边界上。本文中的待测芯片，每条边大概有600个边缘点，通过实验发现，在每条边上建立20个矩形测量区域就可以保证拟合边缘的精度。

(3)设置2D Metrology参数：

num_measures为测量区域期望的对象个数，measure_select为该参数指定的边缘的端点的选择，min_scor为计量对象有效的分数。

(4)应用2D Metrology，建立2D Metrology对象的轮廓：

通过高斯滤波求导，沿矩形测量区域长轴方向逐个找到每一个矩形测量区域内位于长轴上的像素突变点，作为RANSAC算法拟合直线的边缘点，通过RANSAC算法拟合直线。

(5)得到待测芯片边缘轮廓，如图1所示。

图1 芯片边缘轮廓拟合结果(图中红色的实线是找到的边缘轮廓线，绿色╳是找到的边缘点，蓝色矩形区域是测量区域)

3 实验结果与分析

为了验证本文提出的2D Metrology芯片定位方法的有效性，我们从速度和准确性两方面与我们常用的基于最小二乘法的芯片定位方法对比。

(1)我们随机选取30张同一种类BGA芯片的图像，在相同的实验条件下，采用两种不同的芯片定位方法找到芯片四个角点位置坐标，得出定位每张芯片的平均时间为：T最小二乘法=10.771ms，T2D Metrology=12.587ms，可见2D Metrology芯片定位方法的速度还是非常快的，仅仅比最小二乘法慢了1.816ms,能够满足实际生产中对实时性的需求。

(2)我们先利用两种不同的方法找到同一待测芯片四个角点的坐标，计算出待测芯片四个角点和模板芯片四个角点坐标的映射矩阵，再通过模板文件将模板芯片上焊球的坐标映射到待测芯片上，结果如图2所示。

图2 焊球参考坐标位置(图中╳是找到的芯片四个角点的位置，+是映射到芯片上焊球的参考坐标位置)

从图2(a)中可以明显看出，使用最小二乘法芯片定位方法找到的芯片左下角的角点明显不够准确，导致芯片左下角焊球参考坐标位置的整体偏移。

我们通过blob分析提取这张芯片上的焊球轮廓，得到每一个焊球的实际位置坐标，计算实际位置与参考位置的偏差，得出图 3所示的偏差曲线。

图3 焊球实际位置与参考位置的偏差曲线

从图3中很明显的可以看出基于RANSAC算法2D Metrology芯片定位方法得到的焊球参考位置与实际位置的偏差集中在3个像素之内，偏差小，且较稳定。而基于最小二乘法的芯片定位方法得到的焊球参考位置和实际位置的偏差却在15个像素内，甚至超出15个像素，之所以有这么大的偏差，是因为基于最小二乘法芯片定位方法所找到的芯片四个角点位置不够准确，由此计算出的待测芯片与模板芯片的映射矩阵不够准确。可见基于最小二乘法的芯片定位的准确性远远不如基于RANSAC算法2D Metrology芯片定位方法。

4 结束语

本文提出了一种基于RANSAC算法的2D Metrology芯片定位方法，详细的阐述了2D Metrology的基本原理和使用方法，并通过实验，与常用的基于最小二乘法的芯片定位方法进行对比。实验结果表明，该方法的速度与常用的基于最小二乘法的芯片定位方法的速度相差无几，但定位精度特别高、鲁棒性特别好。尤其对于那种质量不太好、干扰比较大的图像，2D Metrology芯片定位方法的优越性更加的突出。

[1]何志刚,梁堃,周庆波,等.基于X射线成像的BGA焊接质量检测技术[J].电子工艺技术，2016，37(01)：32-34，39.

[2]夏石川.BGA内部缺陷检测技术研究[D].太原：中北大学，2014.

[3]Yen H N,Tsai D M.A fast full-field 3D measurement system for BGA coplanarity inspection[J].International Journal of Advanced Manufacturing Technology.2004，24(01):132-139.

[4]刘学平,陈艺昌,才常龙,等.基于机器视觉的BGA芯片检测对中技术[J].计算机工程，2013，39(08):281-284.

[5]周卫星,秦笛,白洁,等.基于增强现实技术的BGA芯片辅助定位[J].电子测量技术，2010，(09):56-59.

[6]方晓胜,胡跃明,高红霞.BGA芯片的高速高精度视觉检测与定位算法[J].电子工艺技术，2006，27(05):262-264.

[7]覃经文.基于机器视觉的BGA微焊球高度测量方法与系统研究[D].长沙：中南大学，2012.

[8]闫蓓,王斌,李媛.基于最小二乘法的椭圆拟合改进算法[J].北京航空航天大学学报，2008，34(03):295-298.

[9]宋卫艳.RANSAC算法及其在遥感图像处理中的应用[D].北京：华北电力大学，2011.

[10]陈艺虾,孙权森,徐焕宇,等.SURF算法和RANSAC算法相结合的遥感图像匹配方法[J].计算机科学与探索，2012，6(09):822-828.

[11]袁清坷,张振亚,毕庆.改进RANSAC算法在直线拟合中的应用[J].组合机床与自动化加工技术，2015，(01):123-125.

[12]黄梅.基于改进RANSAC法的图像拼接技术[J].海南大学学报(自然科学版),2011，29(02):172-177.

[13]夏链,贾伟妙,崔鹏,等.基于机器视觉的BGA芯片缺陷检测及其MATLAB实现[J].合肥工业大学学报(自然科学版)，2009，32(11):1652-1655.

[14]马少鹏,金观昌,李江城.BGA焊点共面度的特殊结构光投影测量技术[J].清华大学学报，2002，42(11):1488-1491.

[15]陈亮,胡跃明,戚其丰.BGA芯片视觉检测定位算法[J].电子工艺技术，2008，29(06)：311-313，327.

Application research on 2D Metrology in BGA quality testing based on RANSAC algorithm

ZHOU Yage,NING Ailin

(Department of Mechanical and Energy Engineering，Shaoyang University，Shaoyang 422000，China)

For BGA chip positioning problem in quality detection,this paper proposes a 2D Metrology chip positioning method based on RANSAC algorithm.First carries on the 2D Metrology modeling,the second object is added to the 2D Metrology model,and then set 2D Metrology model parameters,using 2D Metrology,finally get the 2D Metrology model object positioning results.Based on RANSAC algorithm,this method can accurately identify the model of object boundary characteristics,simple,high precision,good robustness and strong anti-jamming capability.The experiment show that the proposed method is more effective than the chip positioning method based on least square method.

BGA detection;2D Metrology;chip positioning;RANSAC algorithm

1672-7010(2016)03-0108-05

2016-05-16

邵阳学院研究生科研创新项目(CX2014SY033)

周亚歌(1986-)，女，河南叶县人，邵阳学院2013级硕士研究生，从事机器视觉检测研究

宁爱林(1956-)，男，博士，教授，从事材料加工工程研究，E-mail：zmm1958@163.com

TP751;TP391

A