基于Delaunay三角剖分的PCB檢孔機多重孔位校正方法

蔡 宇 王 靜

（廣東正業(yè)科技股份有限公司，廣東 東莞 523808）

1 前言

1.1 背景介紹

PCB檢孔機就是一種高度智能化的PCB鉆孔自動檢測設(shè)備[1]，用來對PCB制作過程中鉆孔檢測，快速地檢測出孔的數(shù)量，并且對出現(xiàn)孔大、孔小、孔多、孔少、孔內(nèi)異物以及孔的重心偏移這幾種錯誤類型進行判定。

在PCB光電檢孔機檢測過程中，標(biāo)準(zhǔn)檔與測試檔對應(yīng)孔位的配準(zhǔn)作為關(guān)鍵步驟，顯得尤為重要，其配準(zhǔn)效果直接影響判定結(jié)果。由于目前PCB板整體制作工藝的提升，孔徑越來越小、孔間距越來越近[2]。對PCB檢孔機測試過程的孔位配準(zhǔn)技術(shù)也提出了更高的要求, 因此本文提出了一次粗配準(zhǔn)加兩次細(xì)配準(zhǔn)的多重孔位校正技術(shù)，可以快速可靠地實現(xiàn)測試檔數(shù)據(jù)與標(biāo)準(zhǔn)檔數(shù)據(jù)的的匹配，大大降低孔位配準(zhǔn)錯誤的概率。

1.2 相關(guān)概念

1.2.1 三角剖分[3]

假設(shè)V是二維實數(shù)域上的有限點集，邊e是由點集中的點作為端點構(gòu)成的封閉線段， E為e的集合。那么該點集V的一個三角剖分T=（V,E）是一個平面圖G，該平面圖滿足條件：

（1）除了端點，平面圖中的邊不包含點集中的任何點；

（2）沒有相交邊；

（3）平面圖中所有的面都是三角面，且所有三角面的合集是散點集V的凸包。

1.2.2 Delaunay三角剖分

在定義Delaunay三角剖分之前，需要給出Delaunay邊的定義:假設(shè)E中的一條邊e（其端點為a、b），若e滿足條件：存在一個圓經(jīng)過a、b兩點，圓內(nèi)不含點集中任何其他的點，這一特性又稱空圓特性，則稱之為Delaunay邊[4]。

利用Delaunay邊，Delaunay三角剖分定義為：如果點集的一個三角剖分T只包含Delaunay邊，那么該三角剖分稱為Delaunay三角剖分。它具有如下特征：

（1）空圓特性；

（2）最大化最小角特性。

2 由粗到細(xì)的孔位校正算法思想

為了實現(xiàn)標(biāo)準(zhǔn)檔與測試檔的孔徑信息比對，必須在空間坐標(biāo)上實現(xiàn)配準(zhǔn)，故快速而準(zhǔn)確地實現(xiàn)大規(guī)模散亂點云數(shù)據(jù)的配準(zhǔn)是PCB檢孔機孔徑檢測的關(guān)鍵環(huán)節(jié)。

理論上，測試檔數(shù)據(jù)與標(biāo)準(zhǔn)檔數(shù)據(jù)是一一對應(yīng)的，但是實際中由于同一塊PCB板不同位置加工的精度不同[5]（如PCB的邊緣以及不需要插入電子元件的孔的位置，其加工精度比需要插入電子元件的鉆孔精度要差）、掃描過程中平臺振動導(dǎo)致的橫向誤差、以及運動過程中速度不一致和不同位置摩擦系數(shù)不一致導(dǎo)致的縱向誤差、板子翹曲導(dǎo)致的局部形變等，都會造成實際得到的測試檔孔位會偏離標(biāo)準(zhǔn)位置, 并且這種偏差是無法避免的。考慮到目前PCB板整體制作工藝的提升，孔徑越來越小、孔間距越來越近。對PCB檢孔機測試過程的孔位配準(zhǔn)技術(shù)也提出了更高的要求，因此本文提出了一次粗配準(zhǔn)和兩次細(xì)配準(zhǔn)的多重孔位校正技術(shù)，可以快速可靠地實現(xiàn)測試檔數(shù)據(jù)與標(biāo)準(zhǔn)檔數(shù)據(jù)的的一一匹配。

多重孔位校正方法分為三個步驟。 如圖1所示，第一步是利用PCB板四個角點處的定位孔圓心信息對標(biāo)準(zhǔn)檔和測試檔孔位進行仿射配準(zhǔn)，得到初始的空間對應(yīng)關(guān)系，該步驟稱之為粗校正。第二步將測試檔中“較大”孔徑的孔提取出來作為Delaunay三角剖分點集[6]，并計算其與標(biāo)準(zhǔn)檔對應(yīng)孔之間的位移偏差。 第三步計算測試檔中“較小”孔徑的孔落在了三角剖分中的位置，然后利用其對應(yīng)的三角形三個頂點信息對其進行校正。 上述兩個步驟稱之為細(xì)校正。

3 算法流程

為了描述方便，文中引入如下標(biāo)記，假設(shè)表示標(biāo)準(zhǔn)檔所有孔中心坐標(biāo)集合，表示測試檔中所有孔中心坐標(biāo)集合，A、B、C、D為標(biāo)準(zhǔn)檔的四個定位孔圓心，A’、B’、C’、D’為測試檔的四個定位孔圓心，D1表示最小孔徑，D2表示最小孔邊距，E表示系統(tǒng)整體的最大誤差。

3.1 全局粗校正

考慮到PCB定位孔一般位于四個角處、孔徑較大、特征明顯且比較容易和普通鉆孔區(qū)分開來，以下內(nèi)容假定定位孔信息是已知的。

如圖2所示，根據(jù)標(biāo)準(zhǔn)檔S和測試檔T的定位孔之間的對應(yīng)關(guān)系，可以利用最小二乘擬合出其仿射變換矩陣M1。 令T1=M1T， 那么T1便是通過定位孔信息校正后的測試檔中心集合。

3.2 全局細(xì)校正

在實際應(yīng)用中發(fā)現(xiàn)，如果最小孔間距D1，最小孔徑D2和系統(tǒng)最大誤差E滿足如下條件：

圖1 PCB信息配準(zhǔn)定位流程圖

圖2 標(biāo)準(zhǔn)檔與測試檔之間對應(yīng)的定位孔

那么就會出現(xiàn)誤匹配。考慮到目前PCB制造向小孔徑、高密度的方向發(fā)展，在系統(tǒng)誤差無法避免的情況下，誤匹配現(xiàn)象發(fā)生的概率會越來越大。反之，如果D2足夠大，比如D2>2×E，那么理論上，對于任意孔間距，都不會發(fā)現(xiàn)誤匹配現(xiàn)象。

文中的數(shù)據(jù)的全局細(xì)校正方法基于上述事實，首先從標(biāo)準(zhǔn)檔S中提取子集S_large，并滿足如下條件：

對于任意s∈S_large，其孔徑大于2×E。

S_large 中元素分布比較均勻。

S_large 中元素個數(shù)適中。

由于S_large中的元素滿足條件（1），故S_large中的元素可以直接計算出其在T1中的對應(yīng)點。 已知對應(yīng)點后，可以計算出S_large=（s1,s2.......）和T1_large=（t1,t2.....）之間的偏移量集合， 記為Offset=（o1,o2......）滿足下式：

又由于S_large是從標(biāo)準(zhǔn)檔S中提取的，且由于PCB板鉆孔工藝可能出現(xiàn)的瑕疵，S_large中的每個元素在測試檔T中不一定都存在對應(yīng)元素。這時候標(biāo)準(zhǔn)檔與測試檔的子集對應(yīng)的Delaunay三角剖分不一致。避免該問題最簡單的方法是對S_large進行初始篩選， 將在T不存在對應(yīng)元素的點剔除掉，這樣就保證了Delaunay三角剖分的一致性。

下面以篩選后的S_large作為Delaunay三角剖分集合，對其集合中元素進行Delaunay三角剖分，如圖3所示：（a）為初始的S_large集合，（b）其Delaunay三角剖分圖DT。以該三角剖分作為基準(zhǔn)，下面進行細(xì)校正步驟2。

圖3

3.3 局部細(xì)校正

假定集合S_small=S_large， 即S_small是S_large對應(yīng)的補集，由S_large的定義可知，S_small中的元素s一般是孔徑比較小的，且落在Delaunay三角剖分圖DT的某一三角片內(nèi)。 這樣，可以利用DT中三角片三個頂點的信息來校正s。

圖4 s落在DT中某一三角片內(nèi)、外兩種情形

對于任意∈S_small，其校正步驟如下：

（1）計算s落在DT內(nèi)三角片的三個頂點坐標(biāo)。

（2）假定落在△ABC內(nèi)，其中A、B、C∈S_large。那么：

計算s與A、B、C之間的距離，記為lA、lB、lC。

由3.2節(jié)，已經(jīng)計算出S_large中元素的空間偏移量，故A、B、C三點的偏移量OA、OB、OC可以作為已知量。

計算s的加權(quán)偏移：

（3）如果s落在DT中所有三角片外部，如圖4所示，那么只需要考慮距離其最近的兩個點。偏移量計算方式和（2）相同。

以上校正環(huán)節(jié)可以概述為以下三點：

（1）利用定位孔信息對原始孔中心集合進行全局的仿射變換；

（2）對于大孔徑的孔，一般不會出現(xiàn)誤匹配現(xiàn)象，故可直接利用仿射矩陣對其進行校正處理；

（3）對于小孔徑的孔，利用大孔徑集合構(gòu)成的Delaunay三角剖分進行局部校正。

4 試驗與結(jié)果分析

4.1 不同大小的S_large劃分方式試驗結(jié)果

考慮到Delaunay三角剖分算法的時間復(fù)雜度較高，檢孔機的實時性要求也很高。所以S_large的選取非常重要，既要考慮到后期校正的精度，也要顧慮到時間開銷。文中選擇孔數(shù)46754的PCB鉆孔板，設(shè)置不同大小的S_large，其Delaunay三角剖分及校正時間開銷如表1所示。

從表1中可見，S_large的數(shù)目控制在5000以內(nèi)時，基本上可以滿足實時性要求。實際操作中，可以只在第一次檢測時進行Delaunay三角剖分計算，之后的檢測可以直接利用其剖分作為初始剖分網(wǎng)格。需要注意的是，初始剖分網(wǎng)格和實際檢測中的網(wǎng)格不一定完全一致，還需要對網(wǎng)格點進行篩減，幸運的是，Delaunay三角網(wǎng)格的局部調(diào)整是很容易處理的。采用這種方式處理的話，表1中的Delaunay剖分耗時可以忽略不計。經(jīng)驗證，文中校正算法增加的時間可以控制在100 ms以內(nèi)。

4.2 校正結(jié)果與不校正結(jié)果比較

為了測試文中提出的方法，選擇三種不同孔數(shù)，不同孔徑的PCB做對比試驗。 其中板A孔數(shù)為33523，板B孔數(shù)為148381，板C孔數(shù)為6427。對比試驗結(jié)果如圖5所示。其中（a）、（c）、（e）是未校正時所有孔的位移偏差絕對值，（b）、（d）、（f）是校正之后的所有孔的位移偏差絕對值。從圖對比結(jié)果可以看出，利用文中的校正技術(shù)處理之后，孔位偏差明顯優(yōu)于未校正的情況。

5 結(jié)論

基于Delaunay三角剖分的PCB檢孔機多重孔位校正技術(shù)，可以快速準(zhǔn)確地實現(xiàn)多孔數(shù)、高密度、小孔間距的PCB板的孔位配準(zhǔn)，保證了圖像的配準(zhǔn)精度。實驗結(jié)果表明：文中提出的算法能夠完全滿足檢測要求的精度和實時檢測的快速性要求。

表1 Delaunay三角剖分及校正時間開銷

圖5 測試結(jié)果對比圖

目前，上述算法和理論研究均成功地應(yīng)用于ASIDA品牌的PCB光電檢孔機JK-3200，達(dá)到PCB 孔徑檢測的技術(shù)指標(biāo)，目前已經(jīng)推向了市場，用戶反應(yīng)良好。

項目來源：2012年廣東省數(shù)控一代機械產(chǎn)品創(chuàng)新應(yīng)用示范工程專項資金入庫項目專題“關(guān)鍵技術(shù)攻關(guān)與行業(yè)數(shù)控裝備類”重大項目《名稱：面向數(shù)控一代的印刷電路板及其精密聯(lián)裝關(guān)鍵設(shè)備研發(fā)與產(chǎn)業(yè)化》；立項批文：粵科高字（2012）150號。

[1]陳志云.印制電路板檢測系統(tǒng)的研究與應(yīng)用[D].重慶:重慶大學(xué), 2006.

[2]姚曉棟,張永宏,吳琦等. 基于圖像識別的印制電路板精密檢測實驗研究[J]. 測控技術(shù), 2006,25(6):75-77.

[3]申利民. Delaunay三角剖分算法優(yōu)化的實現(xiàn)[J]. 計算機與數(shù)字工程, 2009:34-36.

[4]李小麗,陳花竹等. 基于格網(wǎng)劃分的Delaunay三角剖分算法研究[J]. 計算機與數(shù)字工程, 2011:57-59.

[5]秦超華. 印制電路板設(shè)計與工藝的技術(shù)探討[J]. 西安航空技術(shù)高等?？茖W(xué)校學(xué)報, 2004,2(5):35-38.

[6]余杰,呂品等. Delaunay三角網(wǎng)構(gòu)建方法比較研[J].中國圖像圖形學(xué)報, 2010:1158 -1165.