基于PCA和分段RHT的PCB板圓Mark點定位

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

(重慶理工大學 計算機科學與工程學院，重慶 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