惠鵬飛，苗鳳娟，陶佰睿，王成琳

（齊齊哈爾大學(xué)通信與電子工程學(xué)院，黑龍江齊齊哈爾 161006）

基于K－均值聚類和分水嶺算法的PCB彩色圖像分割

惠鵬飛，苗鳳娟，陶佰睿，王成琳

（齊齊哈爾大學(xué)通信與電子工程學(xué)院，黑龍江齊齊哈爾 161006）

針對(duì)光學(xué)檢測(cè)印刷電路板（PCB）時(shí)需要進(jìn)行圖像分割的問(wèn)題，提出一種結(jié)合K－均值聚類算法的分水嶺算法，用于PCB彩色圖像分割，即首先將PCB彩色圖像聚類，分成不同的顏色區(qū)域，按照不同區(qū)域進(jìn)行分水嶺分割，最后，將分割線透明的加在原始圖像上，完成分割。實(shí)驗(yàn)表明，本文提出的算法可以分割PCB彩色圖像，并且分割效果好。

PCB;分水嶺算法;彩色圖像分割;聚類

印刷電路板（Printed Circuit Board，PCB）是電子零件彼此連接溝通的支撐物，它質(zhì)量的好壞直接影響電子產(chǎn)品的正常工作，所以對(duì)PCB的檢測(cè)是必要的。近年來(lái)，利用光學(xué)手段獲取PCB表面圖像，并通過(guò)圖像處理的方法進(jìn)行檢驗(yàn)、分析和判斷的光學(xué)檢測(cè)PCB技術(shù)已成為研究的熱點(diǎn)［1－4］。圖像分割則是進(jìn)行光學(xué)檢測(cè)的首要步驟，其成功與否直接影響到后續(xù)的檢測(cè)識(shí)別工作?，F(xiàn)有的PCB圖像分割算法有:文獻(xiàn)［5］提出一種將PCB圖像分割轉(zhuǎn)化為閾值最優(yōu)問(wèn)題，進(jìn)而利用改進(jìn)遺傳算法求解圖像最優(yōu)問(wèn)題的算法;文獻(xiàn)［6］提出了基于改進(jìn)分水嶺的PCB圖像分割算法;文獻(xiàn)［7］對(duì)PCB圖像利用模糊集和Otsu理論進(jìn)行分割。上述算法雖能成功地對(duì)PCB圖像進(jìn)行分割，但都只針對(duì)灰度圖像，丟失了原始圖像的色彩信息，PCB彩色圖像的分割算法卻未見提及。于是本文提出一種結(jié)合K－均值聚類算法的分水嶺算法，用于PCB彩色圖像分割。

1 K－均值聚類算法

聚類是對(duì)數(shù)據(jù)空間中數(shù)據(jù)對(duì)象進(jìn)行分類，位于同一類中的數(shù)據(jù)對(duì)象之間的相似度較大，而位于不同類之間的數(shù)據(jù)對(duì)象差異度較大。聚類是一種無(wú)監(jiān)督學(xué)習(xí)，能自動(dòng)對(duì)數(shù)據(jù)集進(jìn)行劃分。常見的聚類算法有:K－means，DBSCAN，CURE等算法。K－means即K－均值聚類，該算法確定的K個(gè)劃分到達(dá)平方誤差最小，當(dāng)聚類是密集的，且類與類之間區(qū)別明顯時(shí)，效果較好。并且對(duì)于處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效的，計(jì)算的復(fù)雜度為O（NKt），其中N是數(shù)據(jù)對(duì)象的數(shù)目，t是迭代的次數(shù)，具體步驟如下:

第一步，選K個(gè)初始聚類中心，z1（1），z2（1），…，zK（1），其中括號(hào)內(nèi)的序號(hào)為尋找聚類中心的迭代運(yùn)算的次序號(hào)。聚類中心的向量值可任意設(shè)定，例如可選開始的K個(gè)模式樣本的向量值作為初始聚類中心。

第二步，逐個(gè)將需分類的模式樣本{x}按最小距離準(zhǔn)則分配給K個(gè)聚類中心中的某一個(gè)zj（1）。假設(shè)i=j時(shí)，則zi（k）=zj（k），其中k為迭代運(yùn)算的次序號(hào)，第一次迭代k=1，Sj表示第j個(gè)聚類，其聚類中心為zj。

第三步，計(jì)算各個(gè)聚類中心的新的向量值z(mì)j（k+1），j=1，2，…，K，求各聚類域中所包含樣本的均值向量:其中Nj為第j個(gè)聚類域Sj中所包含的樣本個(gè)數(shù)。以均值向量作為新的聚類中心，可使如下聚類準(zhǔn)則函數(shù)最小:在這一步中要分別計(jì)算K個(gè)聚類中的樣本均值向量，所以稱之為K－均值算法。

第四步，若zi（k+1）≠zj（k），j=1，2，…，K，則返回第二步，將模式樣本逐個(gè)重新分類，重復(fù)迭代運(yùn)算;若zi（k+1）=zj（k），j=1，2，…，K，則算法收斂，計(jì)算結(jié)束。

2 本文算法

本文提出的結(jié)合K－均值聚類的分水嶺算法，目的是對(duì)已經(jīng)聚類的顏色目標(biāo)進(jìn)行分割，從而完成PCB彩色圖像的分割。

2.1 分水嶺算法

分水嶺分割方法，是一種基于拓?fù)淅碚摰臄?shù)學(xué)形態(tài)學(xué)的分割方法，其基本思想是把圖像看作是測(cè)地學(xué)上的拓?fù)涞孛?，圖像中每一點(diǎn)像素的灰度值表示該點(diǎn)的海拔高度，每一個(gè)局部極小值及其影響區(qū)域稱為集水盆，而集水盆的邊界則形成分水嶺。分水嶺的概念和形成可以通過(guò)模擬浸入過(guò)程來(lái)說(shuō)明。在每一個(gè)局部極小值表面，刺穿一個(gè)小孔，然后把整個(gè)模型慢慢浸入水中，隨著浸入的加深，每一個(gè)局部極小值的影響域慢慢向外擴(kuò)展，在兩個(gè)集水盆匯合處構(gòu)筑大壩，即形成分水嶺。對(duì)于分水嶺變換（Watershed by Immersion），令f:D是一幅灰度圖像，它的最大和最小灰度值為h_max和h_min。定義一個(gè)從h_min到h_max的水位h不斷遞增的遞歸過(guò)程。在這個(gè)過(guò)程中每個(gè)與不同的局部最小相關(guān)的匯水盆地都不斷擴(kuò)展，定義X（h）記作在水位h時(shí)候匯水盆地的集合的并。在h+1層，一個(gè)連通分量T（h+1）或者是一個(gè)新的局部最小，或者是一個(gè)已經(jīng)存在的X（h）中的一個(gè)盆地的擴(kuò)展。對(duì)于后者，按鄰接關(guān)系計(jì)算高度為h+1的每一個(gè)點(diǎn)與各匯水盆地的距離。如果1個(gè)點(diǎn)與2個(gè)以上的盆地等距離，則它不屬于任何盆地，否則它屬于與它距離最近的盆地。這樣從而產(chǎn)生新的X（h+1）。把在高度h出現(xiàn)的局部最小記作MIN（h）。把Y（h+1，X（h））記作高度為h+1同時(shí)屬于X（h）的點(diǎn)的集合。

分水嶺變換Watershed（f）就是X（h_max）的補(bǔ)集。

2.2 結(jié)合K－均值聚類的分水嶺算法

2.2.1 顏色空間選擇

選擇合適的顏色空間是成功進(jìn)行彩色圖像分割的首要環(huán)節(jié)，計(jì)算機(jī)處理分析系統(tǒng)接收到的PCB彩色圖像是在RGB顏色空間中表示的。由于彩色顯示器采用紅、綠和藍(lán)來(lái)生成目標(biāo)顏色，所以RGB顏色空間是計(jì)算機(jī)圖形學(xué)最通常的選擇，這樣可以簡(jiǎn)化系統(tǒng)的構(gòu)架與設(shè)計(jì)。RGB顏色空間用三維的笛卡爾坐標(biāo)系統(tǒng)來(lái)表示，如圖1所示。

圖1 RGB顏色空間圖

其中，每個(gè)頂點(diǎn)的三色疊加值如表1所示。

表1 RGB顏色表

可見RGB顏色空間的色彩是比較豐富的，同時(shí)還是顯示器硬件系統(tǒng)的默認(rèn)顏色空間，做圖像處理時(shí)的速度比其他顏色空間快，所以本文選擇RGB顏色空間。

2.2.2 圖像分割算法

將PCB彩色圖像在RGB顏色空間中分別提取R、G、B三個(gè)灰度圖像。將每幅灰度圖像的像素值考慮成一組二維數(shù)學(xué)矩陣，在其中隨機(jī)選取2個(gè)像素值x（i，j）和y（i，j）作為初始聚類中心，根據(jù)下列公式對(duì)剩余的像素值進(jìn)行聚類

其中，當(dāng)z（i，j）取到x（i，j）或y（i，j）時(shí)，上述公式中D為0，當(dāng)z（i，j）為異于x（i，j）和y（i，j）的像素值時(shí)，設(shè)置D0為0.05，驗(yàn)證下列公式

設(shè)置閾值T，對(duì)T進(jìn)行取值，滿足上述公式則完成三幅灰度圖像的聚類。對(duì)每幅聚類后的灰度圖像進(jìn)行分水嶺分割，即對(duì)已經(jīng)聚類好的灰度圖像，利用公式（1）尋找相同高度的像素值，對(duì)分水嶺變換后的三幅灰度圖像進(jìn)行單通道圖像整合，合成RGB空間的彩色圖像，即完成PCB彩色圖像的分割。算法流程如圖2所示。

3 實(shí)驗(yàn)與分析

利用本文提出的算法，在MATLAB 7.1環(huán)境下，對(duì)用CCD攝像機(jī)獲取的PCB彩色圖像進(jìn)行仿真，如圖3所示，可以看到，本文提出的算法可以很好地分割PCB彩色圖像，分割清晰，PCB的結(jié)構(gòu)保持完整，同時(shí)由于所采取的方法均為無(wú)監(jiān)督算法，所以整體程序所消耗的時(shí)間較短，僅為7.254 s，說(shuō)明了本文算法的高效性。

圖2 算法流程圖

4 結(jié)論

本文成功地分割了PCB彩色圖像，提出了結(jié)合聚類算法的分水嶺算法，通過(guò)實(shí)驗(yàn)仿真可以看到，所提出的算法可以清晰地分割PCB彩色圖像，為之后的PCB檢測(cè)工作奠定了基礎(chǔ)。

圖3 實(shí)驗(yàn)仿真圖

:

［1］杜顏顏，楊帆，王曉穎.一種彩色PCB圖像的邊緣檢測(cè)算法研究［J］.電視技術(shù)，2011，35（13）:112－115.

［2］李剛，韓建國(guó).PCB圖像檢測(cè)中閾值化分割的研究［J］.北京化工大學(xué)學(xué)報(bào)，2002，29（4）:72－74.

［3］趙曉霞，王明泉，李高亮.一種基于偏微分方程的PCB圖像增強(qiáng)方法［J］.電視技術(shù)，2011，36（3）:33－35.

［4］孫曉霞，熊紅云.PCB檢測(cè)系統(tǒng)中的圖像預(yù)處理［J］.中國(guó)科技信息，2007，30（22）:116－117.

［5］曾成，趙錫鈞，徐欣，等.PCB檢測(cè)中圖像分割技術(shù)研究［J］.傳感器與微系統(tǒng)，2011，30（2）:26－28.

［6］曾歆懿，章云，季秀霞，等.基于分水嶺變換的PCB圖像分割［J］.質(zhì)量工程卷，2007，20（1）:22－26.

［7］張鵬程，劉若鈞，張記龍，等.基于模糊集和Otsu理論的PCB圖像分割算法［J］.中北大學(xué)學(xué)報(bào):自然科學(xué)版，2009，30（4）:386－389.

苗鳳娟（1982— ），博士，主研傳感器;

陶佰睿（1972— ），博士，主研傳感器;

王成琳（1986— ），碩士生，主研圖像處理。

PCB Color Image Segmentation Based on K－means Cluster and Watershed Algorithm

HUI Pengfei，MIAO Fengjuan，TAO Bairui，WANG Chenglin

（Communication and Electronic Engineering Institute，Qiqihar University，Heilongjiang Qiqihaer 161006，China）

According to the problem of optical detection printed circuit board（PCB）need image segmentation，a kind of combination clustering algorithm and watershed algorithm in PCB color image segmentation algorithm is put forward.Firstly，the PCB color image is clustered to divide into different color area，then the different area is segmented by watershed segmentation algorithm.At last，the cut－off rule transparent is added to the original image，the segmentation is completed.Experiments show that the proposed algorithm can split PCB color image，and segmentation effect is good.

PCB;watershed algorithm;color image segmentation;clustering

TN911.73;TP391.41

A

【本文獻(xiàn)信息】惠鵬飛，苗鳳娟，陶佰睿，等.基于K－均值聚類和分水嶺算法的PCB彩色圖像分割［J］.電視技術(shù)，2013，37（13）.

國(guó)家自然科學(xué)基金項(xiàng)目（61204127）;齊齊哈爾市科技局工業(yè)攻關(guān)項(xiàng)目（GYGG－201109）;齊齊哈爾大學(xué)青年教師科研啟動(dòng)支持計(jì)劃項(xiàng)目（2010k－M03）;黑龍江省青年基金項(xiàng)目（QC2011C092）

惠鵬飛（1980— ），碩士，主研信息檢測(cè)，電磁場(chǎng)與微波技術(shù);

責(zé)任編輯:魏雨博

2012－10－31