刘 政，熊 昊，肖森林，王 越

(重庆理工大学 计算机科学与工程学院，重庆 400054)

基于PCA和分段RHT的PCB板圆Mark点定位

刘 政，熊 昊，肖森林，王 越

(重庆理工大学 计算机科学与工程学院，重庆 400054)

圆Mark点定位是自动光学检测的重要环节，针对多场景的印刷电路板圆Mark定位问题提出了基于主成分分析和分段随机霍夫变换圆检测的方法。该方法在canny边缘检测的基础上，运用主成分分析去掉不相关的线段及曲线，结合随机霍夫变换检测得到类圆的相关参数，最终利用最小二乘拟合得到定位圆。实验结果表明:该方法能很好地提取单孔或多孔的mark圆，并能给出准确的定位参数，为进一步的PCB缺陷检测提供了保障。

定位；自动光学检测；主成分分析；随机霍夫变换；最小二乘拟合

随着电子行业的兴起，各种先进的技术被首先应用在电子领域，而电子产业的基石之一印刷电路板(printed circuit board，PCB)的发展时刻影响着工业的发展。自动光学检测(automatic optic inspection，AOI)是目前大部分印刷电路板生产、质检所经历的缺陷检测环节，它能克服人工检测中重复性和不可靠性的缺点，提高生产质量和效率。AOI检测算法中的参考法是最常见的方法，通过将待匹配板与参考模板图像配准，以便进行后续的缺陷检测，其中PCB定位孔中常见的圆形孔即Mark点的定位是技术的关键，直接影响到整个系统的检测准确性。

文献[1]提出了一种结合随机RHT和空间数据坐标变换理论的PCB配准方法，提高了寻找配准目标和完成配准的效率。文献[2]提出了基于相位一致性和标准霍夫变换(standard hough transform，SHT)的PCB定位方法，将检测得到的参数上传给上位机控制机来实现配准定位，但这种方法很依赖前期圆心的检测精度，对偏转角的计算影响较大。文献[3]采用快速Hough变换来检测PCB圆形孔，并以最小二乘法拟合得到圆参数，这种方法适于内容较单一的PCB图像，且快速Hough变换不能保证较好的精确度。文献[4]针对获取到的非完美圆定位孔，采用otsu阈值分割Mark区域与背景，圆参数获取调用Opencv的cvFindContours函数实现，但实验结果表明:otsu阈值分割引入了大量的噪点，鲁棒性较差。文献[5]选择利用形态学操作来消除二值化后PCB图像的无关区域，再用最小二乘直接拟合得到圆参数，由于形态学操作的局限性，无法排除的干扰区域将加大最小二乘的拟合运算量，且影响最终的定位精度。

本文提出了基于PCA和分段RHT的PCB圆Mark定位方法，采用抗噪性较好的canny算子检测二值图像边缘来保证后续工作的进行，引入PCA全局分析关键区域并排除无关区域，提高了容错率，也减轻了后期检测和拟合圆的工作负荷。

1 传统的圆Mark检测方法

常见的圆Mark的检测方法包括模板匹配和霍夫(Hough)变换，由二者各自衍生的一系列方法都有其独特的适用性，目前仍活跃在各个算法工程师的视线里。

1.1 模版匹配

模版匹配[6]是基于灰度值的图像匹配算法，由于图像内容的所有信息都包含在图像灰度值中，因此可以把图像的灰度信息通过相似性度量联系起来，工作就转化为找寻使相似性度量值最大的模型参数。

通常采用的模版匹配是灰度归一化[7]匹配，相似性度量定义如下：

(1)

其中：T为模版T(m,n)；Si,j为子图Si,j(m,n)。匹配示意图见图1。

先用自适应阈值二值化模版T和子图S，再将子图S覆盖在模版T上，通过在T上规律地平移S并计算像素灰度相关性，直到搜索到相关值最大的点，即为最佳点。这种方法适用于局部的PCB图像，较高精密度的图像会带来相当大的计算量，且检测效果依赖于模版和子图的清晰度和一致性。

1.2 RHT圆检测

RHT算法运用了不在同一直线上的3点可以确定1个圆的原理，通过在图像上随机采集几个点来分析得到圆参数。定义类圆的一般公式为：

(2)

约束条件：

ac-b2>0

(3)

随机选取的3个点，设为x1,x2,x3。这3个点处的切线的交叉点设为s12和s23，线段x1x2和x2x3的中点分别为t12和t23，则类圆的中心(x0,y0)即是线段s12t12和s23t23的交点，最终类圆的方程为：

(4)

可以通过代入选取的3点来得到a，b，c的值。

具体的RHT算法流程[8]如下：

1) 设定图像边界点集A及参数空间单元集B并初始化B，循环次数k=0。

2) 在点集A中随机选取3个点并由此计算候选圆参数C。若有解，转步骤3)；否则转步骤6)。

3)在B中找到一个满足‖B-B1‖≤del的值B1，del是容许的误差值。若有，转步骤5)；否则转步骤4)。

4) 将C插入B并赋值等于1，转步骤6)。

5) 将B1的值加1，若小于阈值N，则转步骤6)，否则转步骤8)。

6)k=k+1。若k>kmax，则进行下一步；否则转步骤2)。

7)B1是候选圆参数。若对应圆点数MB1>Mmin，则转步骤8)；否则为虚假圆并去除，转步骤2)。

8) 判断检测到有B1的圆是否达规定数目。若是，则算法结束；否则将MB1去除并转步骤2)。

算法的实验效果见图2。

相较模版匹配，Hough变换及其改进算法应用场景更多，有较高的可靠性，在有噪声、发生变形，甚至部分区域丢失的状态下仍能取得较为理想的结果，且与其他的算法更容易搭配，有利于进一步的改进和应用，因此在圆形物体的检测方面较为有利。但由于在有复杂线条场景下，随机采样引入较多的无效单元，既耗时又耗存储空间，因此本文先采用主成分分析简化图像，再分段采用随机Hough圆算法达到省时、高效的目的。

图2 RHT效果图Fig.2 Effect graphs based on RHT

2 本文检测方法

本文定位算法的关键在于利用主成分分析提取感兴趣的数据，再利用分段进行的RHT确认可拟合成圆的重要参数。

2.1 主成分分析

主成分分析(PCA)[9]是一种统计方法，对原始数据进行分析，通过线性变换将高维空间中的样本数据投影到低维空间中，把原先的n个特征用数目更少的m个特征取代，新特征是旧特征的线性组合，这些线性组合最大化样本方差，尽量使新的m个特征互不相关。在图像处理方面，由于过多的变量会妨碍查找规律的建立，PCA常被用于对样本空间的降维、去除噪声和冗余、找出最主要的数据联系并以简单的结构显现出来。通过对数据进行统计分析得到协方差矩阵，进而得到其特征值和特征向量，即数据的主成分，再对线段依次进行主成分分析，获得其协方差矩阵的特征值，并对其进行分析来保留类圆曲线段。

假设线段点集内像素点的个数为N，任一像素点的坐标为(x,y)，则：

(5)

(6)

(7)

协方差矩阵S的特征根可以表述为：

(8)

(9)

由主成分分析的基本原理可以知道，线段主方向的个数以及各主方向的主要分布情况可分别用特征值的个数和大小来获取，因此可得出判断线段方向的规则：

1) 当λ1或λ2=0时，各线段只有一个朝向，此时线段为直线。

2) 当λ1>λ2>0时，各线段主要在2个不均匀的朝向分布，此时线段为非圆曲线段。

3) 当λ1=λ2时，各线段主要在2个相同的朝向分布，此时各线段组成了一个完整的圆。

由以上规则可知，理想圆的线段点集也可由λ1=λ2来表示，但受到各种因素比如类圆的存在或者图像光照引起的噪声等的影响，一般无法确定边缘像素的确切位置，因此在实际应用中采用λ1≥λ2表示。

2.2 分段RHT

Hough变换是目前广泛采用的圆形物检测方法。如前所述，随机采样引入了大量的无效点，为达到省时、高效的目的，将分段检测的思想应用到本文当中。基本原理是：通过PCA和圆拟合处理可保留二值图像中部分没有公共点的曲线段，由于一个圆上的点一定是在同一条曲线上，因此对每条曲线段分别进行随机Hough变换，可以大大减少冗余数据的引入和干扰，从而减少时间消耗。

RHT的基本算法[10]描述如下：设P为经过PCA和圆拟合后被保留的图像边缘点集，对每个连通的有效曲线段进行序号标记，按照标记顺序依次进行随机Hough变换；从曲线段Si点集中随机选取3个点，确定一个候选圆参数s，再由此计算曲线段上的其他点落在该候选圆上的点数Ms，如果大于圆所必需的最小点数Mmin，则认为该候选圆为可信赖的真实圆，并从P中删除该圆上的点，再继续进行下一个圆的检测，直到检测出点集P中所有可能的圆。

2.3 本文算法流程

本文基于PCA和分段RHT的印刷电路板圆Mark点定位的主要算法流程如下：

1) 首先载入原始彩色PCB板图像，进行灰度二值化后采用canny算子提取图像边缘。

2) 去掉交叉点和小线段，并标记剩下的线段，找出大于所设阈值的线段。

3) 运用PCA分析降维去噪，并保留类圆的曲线段。

4) 采用分段RHT分析得到圆的个数及相关参数。

5) 结合以上得到的圆参数，通过最小二乘拟合得到所要的圆Mark。

3 实验分析

实验平台为64位Win7，软件环境为Matlab2015b。为验证本文算法的可行性，先进行了局部PCB板的模版匹配检测、RHT圆检测和本文算法的对比实验。实验的图像尺寸为186×163，是含多个焊孔的局部PCB板图。模版匹配子图为手动截取，并依照检测圆数量制作多个子图以提高其检测效果。实验结果见图3。

模版匹配方法匹配到的圆用蓝色方框标出。RHT检测到的圆参数输出在Matlab命令行窗口。本文算法检测到的圆用红色标出。从实验结果可以直观看出：相较于直接采用RHT检测，本文算法在识别圆之前利用PCA去除了大量的干扰非圆曲线段，提高了后续检测的容错率。实验中图像的左上角设定为原点，X轴为水平向右，Y轴垂直向下，输出的圆检测结果如表1所示。

图3 对比实验Fig.3 Comparative experiment graphs表1 圆识别个数实验结果Table 1 Experimental results of circle recognition

方法识别个数误差/%模版匹配528.8RHT442.8本文算法70

模版匹配考虑到每个圆的不同制作了7个子图来提高多圆匹配的成功率，但受到获取的模版和子图的效果的限制，并没有匹配到全部圆孔。RHT受到二值图像右边无关线条区域的干扰，输出的圆心数量超过了已确定的圆孔数量，且部分要识别的圆孔并没有输出来，误差较大。具体的圆心坐标输出结果如表2所示。

由表2可以得出：RHT的最大误差有5个像素，识别精度不高，且鲁棒性较差，易收到干扰；模版匹配的最大误差有3个像素，较RHT精度高些，但识别太依赖于模版与子图一致性；本文算法全部识别了所有的圆孔，且误差在2个像素以内，保持了较高的识别精度。

为进一步验证算法的有效性，以下进行以PCB整板为基础的单孔及多孔的圆Mark定位实验。相较于局部PCB板，整板含有更多的无关线段和曲线，可以体现出PCA的作用。但由于PCB整板含有较多的焊孔圆，而本文侧重于对圆Mark的定位，因此设定在一定面积阈值以下的检测圆被屏蔽，以显示所要定位的圆。

表2 圆定位坐标实验结果Table 2 Experimental results of circle location

首先进行含单圆形孔的PCB板定位实验，图片尺寸为281×339，实验各个流程的效果见图4。

图4(b)的灰度二值化操作将原图像因光照等因素造成的噪声归为灰度值为1的白点或区域，使其可被算法处理。图4(c)调用canny算子来检测图像边缘，由文献[11]可以看出canny有滤波增强和抑制噪声的作用，检测到的圆孔有较好的边缘完整性。图4(d)为去小线段和PCA综合处理的结果，可以明显看出噪点和非圆线段被去掉了，为后续RHT的检测减少了运算量，提高了精度。图4(e)为对图2(d)做SHT检测圆后，利用最小二乘拟合出圆Mark并标出。定位结果与标准测量结果完全一致，证明本文算法对单圆检测是有效的。

之后进行了多圆PCB mark点的定位实验，图片尺寸为599×384，实验结果见图5。

给出的实验效果图同样按照单圆检测的流程来进行，定位孔的增加带来了周围更多的干扰，结果仍然影响定位的准确性，最终圆心坐标与标准一致。以上实验结果可以看出：本文算法在PCB圆Mark的定位上有较好的鲁棒性和准确性，可以完成多种复杂的PCB板圆Mark定位任务，能为后续AOI匹配检测奠定良好的基石。

图4 单定位孔实验Fig.4 Experiment on single locating hole

图5 多定位孔实验Fig.5 Experiment on multiple locating hole

4 结束语

本文针对多场景的PCB圆Mark提出了基于主成分分析和分段随机霍夫变换圆检测的方法。该方法采用抗噪性较好的canny算子进行边缘检测，在此基础上，运用主成分分析去掉不相关的线段及曲线，为后续检测工作减少了计算量并提高了精度，再结合随机霍夫变换检测得到类圆的相关参数，最终利用最小二乘拟合得到定位圆。实验结果表明，该方法能很好地提取单孔或多孔的Mark圆，并能给出准确的定位参数。

本文算法在有较好成像效果的图像中识别和定位结果较好，可运用于PCB图像的缺陷检测和定位，结合预处理和匹配之后PCB缺陷检测的完整优化研究是之后的主要研究方向。

[1] 张静,叶玉堂,谢煜.印刷电路板表观检测中光电图像的快速配准方法[J].光电工程,2013(6):51-57.

ZHANG Jing,YE Yutang,XIE Yu.Method for Fast Registration of Photoelectric Image of Appearance Detection in Printed Circuit Board[J].Opto-Electronic Engineering,2013(6):51-57.

[2] 陈戈珩,李华杰,房晓伟.基于相位一致性和Hough圆的贴片机视觉定位系统的研究[J].科学技术与工程,2015(27):59-63.

CHEN Geheng,LI Huajie,FANG Xiaowei.Research of the Vision Positioning System of Surface Mounting Machine Based on Phase Congruence and Hough Circle Transform[J]. Science Technology and Engineering,2015(27):59-63.

[3] 潘忆江,黄际彦,吴波,等.PCB中圆形图像的自动光学检测研究[J].现代电子技术,2014(8):69-71.

PAN Yijiang,HUANG Jiyan,WU Bo,et al.Automatic optical inspection for the circular images in printed circuit board[J].Modern Electronic Technology,2014(8):69-71.

[4] 熊光洁,马树元,刘瑞祯.PCB检测中圆Mark的快速精确定位[J].计算机工程,2012(11):211-213,216.

XIONG Guangjie,MA Shuyuan,LIU Ruizhen.Fast Precise Positioning of Circular Mark in PCB Inspection[J].Computer Engineering,2012(11):211-213,216.

[5] 郭亚娟,秦襄培,章秀华.基于最小二乘拟合的PCB板焊点定位[J].计算机与数字工程,2014(11):2181-2184.GUO Yajuan,QIN Xiangpei,ZHANG Xiuhua.Locating of PCB Solder Joint Baesd On Least Squares Fitting[J].Computer and Digital Engineering,2014(11):2181-2184.[6] 谢光伟,仲兆准,钟胜奎,等.基于机器视觉的PCB板上圆Mark点定位方法的研究[J].电脑知识与技术,2013(32):7340-7344.

XIE Guangwei,ZHONG Zhaozhun,ZHONG Shengkui,et al.Research on Position Method of Circular Mark in PCB Based on Machine Vision[J].Computer Knowledge and Technology,2013(32):7340-7344.

[7] BARNEA D I,SILVERMAN H F.A class of algorithms for fast digital image registration[J].IEEE Transactions on Computers,1972,C-21(2):179-186.

[8] 吴全玉,周署,俞洋,等.Hough算法在印刷电路板焊孔缺陷检测中的应用[J].工业仪表与自动化装置,2015(6):56-59，62.

WU Quanyu,ZHOU Shu,YU Yang,et al.Application of Hough algorithm in the detection of PCB welding hole defects[J].Industrial Instrumentation& Automation,2015(6):56-59,62.

[9] JUNG S,SEN A,MARRON J S.Boundary behavior in high dimension,low sample size asymptotics of PCA[J].Journal of Multivariate Analysis,2012(4):192-203.

[10]徐培智,徐贵力,黄鑫.基于随机Hough变换的人头检测[J].计算机工程,2012,38(1):199-200.

XU Peizhi,XU Guili,HUANG Xin.Head Detection Based on Randomized Hough Transform[J].ComputerEngineering,2012,38(1):199-200.

[11]石永禄,梅领亮.基于PCB定位圆孔边缘检测技术研究[J].印制电路信息,2012(11):53-57.

SHI Yonglu,MEI Lingliang.Edge detection technologies research based on PCB locating hole[J].Printed Circuit Information,2012(11):53-57.

(责任编辑 杨黎丽)

Positioning of Circular Mark in PCB Based on PCA and Segment RHT

LIU Zheng，XIONG Hao，XIAO Sen-lin，WANG Yue

(College of Computer Science and Engineering,Chongqing University of Technology, Chongqing 400054, China)

Positioning of circle mark is an important part of the automatic optic inspection(AOI for short). A circle detection method based on principal component analysis (PCA for short) and segment randomized hough transform (RHT for short) is proposed, aiming at circular mark positioning of PCB in multi-scene. The method is based on Canny edge detection, use PCA to remove irrelevant line and curve, and combine with RHT to receive parameters of the Quasi-circular; and then get the position circular by least square fitting. The experimental results show that this method can extract the single hole or porous mark circle well and give accurate positioning parameters. Besides, it can provide guarantee for further defect detection.

positioning；automatic optic inspection；principal component analysis；randomized Hough transform；least square fitting

2016-09-21

国家自然科学基金资助项目(61502064)

刘政(1969—)，男，副教授，硕士生导师，主要从事水利水电软硬件设备的研究与设计，E-mail:liuzhewng@cqut.edu.cn；熊昊(1991—)，男，硕士研究生，主要从事图像处理方面的研究。

刘政，熊昊，肖森林，等.基于PCA和分段RHT的PCB板圆Mark点定位[J].重庆理工大学学报(自然科学)，2017(1):93-99.

format：LIU Zheng，XIONG Hao，XIAO Sen-lin，et al.Positioning of Circular Mark in PCB Based on PCA and Segment RHT[J].Journal of Chongqing University of Technology(Natural Science)，2017(1):93-99.

10.3969/j.issn.1674-8425(z).2017.01.015

TP391.41

A

1674-8425(2017)01-0093-07