基于Mean Shift的芯片X光圖像層次分割算法*

宋淑娟，吳靜靜，安　偉，秦　煜，張　洪，周德強(qiáng)（江南大學(xué)機(jī)械工程學(xué)院，江蘇無錫214122）

基于Mean Shift的芯片X光圖像層次分割算法*

宋淑娟，吳靜靜，安偉，秦煜，張洪，周德強(qiáng)
（江南大學(xué)機(jī)械工程學(xué)院，江蘇無錫214122）

針對芯片X光圖像多目標(biāo)、背景復(fù)雜、灰度分布不均勻的特點，提出一種基于Mean Shift的層次分割算法。運(yùn)用旋轉(zhuǎn)縮放不變的模板匹配定位算法定位芯片并確定其興趣區(qū)域（ROI），從而實現(xiàn)外層分割。再運(yùn)用Mean Shift算法對芯片模板圖像和芯片ROI圖像進(jìn)行統(tǒng)計聚類分析，分別計算原圖像金線模式類的灰度平均值，以芯片模板圖像的金線模式類的平均灰度為基準(zhǔn)，對芯片ROI的聚類圖像采用優(yōu)化閾值進(jìn)行自適應(yīng)閾值分割，從而實現(xiàn)內(nèi)層分割。實驗結(jié)果表明：與傳統(tǒng)的均值偏移分割算法相比，該方法的多目標(biāo)分割準(zhǔn)確，可靠性高。

Mean Shift；層次分割；興趣區(qū)域；自適應(yīng)閾值

0　引言

芯片X光圖像分割是將芯片目標(biāo)對象從圖像中分割出來，是后期進(jìn)行缺陷識別、定位等問題的前提［1］。但由于芯片X光圖像背景復(fù)雜、灰度分布不均勻且包括多目標(biāo)對象，對其進(jìn)行有效的分割一直是難點問題。目前對X光圖像的分割算法主要是聚類分割算法［2］。該算法依據(jù)像素的灰度特征和空間特征將像素分成若干類，從而實現(xiàn)分割。常用的是模糊C均值聚類，但其存在一定的局限性。該算法要求先確定目標(biāo)對象的分類數(shù)目以及聚類的初始中心，妨礙了目標(biāo)對象分類的自動實現(xiàn)，分類數(shù)目不同，分類結(jié)果也不同，初始的聚類中心不同，聚類結(jié)果往往也不同，聚類結(jié)果缺乏必要的可靠性。

針對以上問題，本文提出一種基于Mean Shift的芯片X光圖像層次分割算法，運(yùn)用旋轉(zhuǎn)縮放不變的模板匹配定位算法定位芯片并確定其興趣區(qū)域（regions of interests，ROI）從而實現(xiàn)外層分割；再運(yùn)用Mean Shift算法對芯片模板圖像和芯片ROI圖像進(jìn)行統(tǒng)計聚類分析，分別計算金線模式類的原圖像的所有像素的灰度平均值，以芯片模板圖像的聚類結(jié)果為基準(zhǔn)，對芯片ROI的聚類圖像采用優(yōu)化閾值進(jìn)行自適應(yīng)閾值分割，從而實現(xiàn)內(nèi)層分割。該算法通過內(nèi)外層分割，能夠有效地分割出目標(biāo)對象，提高分割的精度和可靠性。

1　芯片X光圖像特性

實際工業(yè)生產(chǎn)中，X光實時成像檢測系統(tǒng)所測的圖像如圖1所示，圖1（a）是單芯片的X光圖像，圖1（b）是焊盤上多芯片的X光圖像。對于芯片X光圖像而言，其特征主要表現(xiàn)在三方面：

1）芯片X光圖像背景復(fù)雜：芯片主要由金線、金球、PAD和槽四部分組成。在芯片X光圖像中，金線、金球和PAD為要分割的目標(biāo)，槽成為圖像背景。

2）多目標(biāo)：芯片X光圖像中包括多個目標(biāo)芯片，各目標(biāo)芯片發(fā)生了角度的旋轉(zhuǎn)和一定比例的縮放。

3）灰度分布不均勻：X光穿過芯片時，光子將與芯片發(fā)生多種相互作用，如電子對效應(yīng)、光電效應(yīng)和康普頓效應(yīng)等，這些相互作用產(chǎn)生的散射射線會造成X光能量衰減，從而導(dǎo)致X光圖像灰度分布不均勻。

芯片X光圖像的背景復(fù)雜、多目標(biāo)和灰度分布不均勻的特點造成目標(biāo)對象的分割困難，所以，需采用自適應(yīng)層次分割方法對芯片圖像進(jìn)行處理，以解決背景信息干擾，多目標(biāo)分割困難和灰度分布不均勻的問題，以保證目標(biāo)對象分割的準(zhǔn)確性。

圖1　芯片X光圖像Fig 1　X-ray image of chips

2　基于Mean Shift的層次分割算法

基于Mean Shift的層次分割算法系統(tǒng)框圖如圖2所示。在芯片X光圖像中挑選一幅符合標(biāo)準(zhǔn)的無缺陷的圖像，并以此作為圖像模板。以此圖像模板作為芯片定位模板，在待檢測的X光圖像上實施模板匹配算法，獲取每個芯片的ROI位置和旋轉(zhuǎn)角度，從而實現(xiàn)外層分割。內(nèi)層分割主要是運(yùn)用均值偏移算法和閾值分割算法，以模板圖像的聚類分割結(jié)果設(shè)計自適應(yīng)閾值，從而實現(xiàn)芯片ROI中各子目標(biāo)的準(zhǔn)確聚類與分割。層次分割算法遵循目標(biāo)粗定位、精確定位及自適應(yīng)更新閾值的原則，降低了復(fù)雜背景對分割對象的干擾，提高了多目標(biāo)分割精度和可靠性，進(jìn)而為后續(xù)的缺陷檢測提供可靠保障。

2.1外層分割

外層分割采用旋轉(zhuǎn)縮放不變的模板匹配定位算法定位芯片并確定ROI。該方法主要原理是基于灰度值匹配的方法。根據(jù)待測圖像與定位模板的灰度值進(jìn)行匹配，通過計算待測圖像與定位模板之間的相似度來實現(xiàn)［3］?；叶戎灯ヅ涫茄卮郎y圖像中的所有點移動模板，在每個位置計算兩者的相似度，求得兩者相似度最高點的算法。相似度用函數(shù)t（m，n）表示，即

圖2　算法系統(tǒng)框圖Fig 2　System block diagram of algorithm

式中s（u，v）為模板T中各點的灰度值，f（m+u，n+v）為圖像當(dāng)前位置的匹配區(qū)域中點的灰度值。基于旋轉(zhuǎn)縮放不變的模板匹配算法是在基于灰度值匹配方法的基礎(chǔ)上，創(chuàng)建多個方向的模板并且創(chuàng)建多個與模板大小成一定的比例的模板。利用這些定位模板與待測圖像進(jìn)行匹配，找出相似度最高點，從而實現(xiàn)目標(biāo)的定位。

2.2內(nèi)層分割

對于外層分割獲得的芯片ROI圖像的像素xi，采用擴(kuò)展形式的均值偏移算法，x點的均值偏移向量Mh（x）可定義為

式中G為核函數(shù)，w為權(quán)重。均值偏移向量的方向和核函數(shù)的概率密度梯度方向是一致的，Comaniciu已經(jīng)證明Mean Shift算法在滿足一定條件下，一定可以收斂到最近的一個概率密度函數(shù)的穩(wěn)態(tài)點［4］。因此，沿著均值偏移向量的方向不斷移動核函數(shù)的中心位置直至收斂，即找到了鄰近的模式點的位置。對芯片ROI圖像的各像素點運(yùn)用均值偏移算法進(jìn)行不斷的偏移直至收斂就得到了各自的模式，實現(xiàn)了對ROI圖像的像素點特征空間的聚類，從而獲得初步的分割圖像。

由于芯片X光圖像灰度分布不均勻，在通過Mean Shift算法獲得初步分割圖像后，采用全局閾值法［5］無法提取出每個芯片的目標(biāo)對象。而常用的自適應(yīng)閾值分割算法，如Sauvola算法、Niblack算法、Kaneko和Chow算法等［6，7］，在分割芯片時，適應(yīng)性不足，也無法解決目標(biāo)對象提取問題。據(jù)此，提出了一種自適應(yīng)閾值分割算法。運(yùn)用Mean Shift算法對芯片模板圖像和芯片ROI圖像進(jìn)行統(tǒng)計聚類分析，分別計算金線模式類的所有像素的灰度平均值，以模板圖像的聚類結(jié)果為基準(zhǔn)，對ROI的聚類圖像采用優(yōu)化閾值進(jìn)行自適應(yīng)閾值分割從而得到目標(biāo)對象。

基于Mean Shift的層次分割算法主要包括對模板的操作和對芯片ROI的操作。其中對模板操作的算法步驟如下：

1）輸入模板匹配定位時模板圖像矩陣M；

2）統(tǒng)計圖像矩陣的直方圖和像素值Mdata，統(tǒng)計Mean Shift聚類樣本數(shù)（0≤Mdata≤255，圖像的灰度值區(qū)間）；

3）運(yùn)用Mean Shift均值偏移算法，可將輸入的數(shù)據(jù)集Mdata聚為m類，輸出聚類的m個中心點，并得到聚類后的圖像N；

4）從m個聚類中心中，根據(jù)灰度值確定并標(biāo)記金線類的聚類中心CL，其灰度值用V（CL）表示；

5）查找被聚為CL類的圖像矩陣M的所有像素，并計算其灰度平均值μM；

6）對聚類得到的圖像N采用閾值δb=V（CL）進(jìn)行分割，并將圖像N中的像素點灰度值小于等于此閾值的目標(biāo)像素賦值“1”，其他為“0”，從而產(chǎn)生分割的芯片模板圖像邏輯矩陣，輸出基準(zhǔn)閾值δb和灰度平均值μM；

7）對芯片ROI圖像矩陣U實施以上步驟（1）～（5），得到聚類后的圖像V和灰度平均值μR，之后實施步驟（8）；

8）對圖像V采用優(yōu)化閾值δ進(jìn)行分割，并將圖像V中的像素點灰度值小于等于此閾值的目標(biāo)像素賦值“1”，其他為“0”，從而產(chǎn)生分割的芯片目標(biāo)邏輯矩陣并輸出該矩陣。其中，優(yōu)化閾值等于基準(zhǔn)閾值加上微調(diào)量

式中δb為基準(zhǔn)閾值，Δ為微調(diào)量。μM和μR分別為模板圖像和芯片ROI圖像的金線模式類的原圖像的所有像素的灰度平均值。

3　實驗結(jié)果與分析

圖3是實際采集的芯片X光圖像。圖4、圖5分別是采用本文算法對圖4的外層分割結(jié)果和內(nèi)層分割結(jié)果。圖6是采用Mean Shift算法對圖3聚類分割的結(jié)果。

從圖4和圖5可以看出，本文算法具有很強(qiáng)的適應(yīng)性，對于旋轉(zhuǎn)角度大、背景復(fù)雜以及灰度分布不均勻的圖像的分割都有較好的結(jié)果。對比圖5、圖6可知標(biāo)準(zhǔn)Mean Shift算法的處理結(jié)果中存在過分割的現(xiàn)象從而導(dǎo)致目標(biāo)對象的提取失敗。與標(biāo)準(zhǔn)Mean Shift算法的分割相比，本文算法從層次分割來改善分割結(jié)果。通過外層分割得到芯片ROI，有效濾除了大量背景信息，降低了復(fù)雜背景對分割對象的干擾；通過內(nèi)層的自適應(yīng)閾值分割可以解決灰度分布不均勻問題，提高分割的精度，從而提高整個缺陷檢測的精度。

圖3　芯片X光圖像Fig 3　X-ray image of chips

圖4　外層分割結(jié)果Fig 4　Results of outer layer segmentation

圖5　內(nèi)層分割結(jié)果Fig 5　Results of inner layer segmentation

圖6　Mean Shift算法聚類結(jié)果Fig 6　Clustering results by Mean Shift algorithm

4　結(jié)論

針對芯片X光圖像多目標(biāo)、背景復(fù)雜、灰度分布不均勻的特點，本文提出一種基于Mean Shift的層次分割算法。實驗對本文算法的分割結(jié)果和Mean Shift分割算法的分割結(jié)果進(jìn)行了比較。實驗結(jié)果表明：本文算法的分割結(jié)果比較準(zhǔn)確，誤分率低，完整的芯片目標(biāo)對象完全分離于復(fù)雜背景。

［1］楊娜，陳益強(qiáng)，劉祎斌.復(fù)雜背景下多目標(biāo)圖像分割方法研究［J］.北京交通大學(xué)學(xué)報，2014，38（3）：118-122.

［2］苗彬，侯燕.基于改進(jìn)模糊均值聚類算法的醫(yī)學(xué)圖像分割［J］.激光雜志，2015，36（1）：140-143.

［3］Carsten Steger，Markus Ulrich，楊少榮.機(jī)器視覺算法與應(yīng)用［M］.吳迪靖，譯.北京：清華大學(xué)出版社，2008：302-317.

［4］Comaniciu D，Meer P.Mean shift analysis and applications［C］∥IEEE the Seventh International Conference on Computer Vision，1999：1197-1203.

［5］林倩倩，歐聰杰.二維 Tsallis熵在圖像閾值分割中的應(yīng)用［J］.傳感器與微系統(tǒng)，2014，33（7）：150-153.

［6］Dong W M，Zhou N，Paul J C.Perspective-aware texture analysis and synthesis［J］.The Visual Computer，2008，24（9）：515-523.

［7］郭佳，劉曉玉，吳冰.一種光照不均勻圖像的二值化方法［J］.計算機(jī)應(yīng)用與軟件，2014，31（3）：183-186.

Mean Shift-based hierarchical segmentation algorithm of X-ray image of chips*

SONG Shu-juan，WU Jing-jing，AN Wei，QIN Yu，ZHANG Hong，ZHOU De-qiang
（School of Mechanical Engineering，Jiangnan University，Wuxi 214122，China）

To overcome segmentation difficulties induced by multiple targets of interests，redundant background and inhomogeneous gray levels of the X-ray image，a hierarchical segmentation algorithm based on Mean Shift is proposed.The algorithm is achieved through two layer segmentation.The outer layer segmentation is to locate the positions and determine their regions of interests（ROI）for all single chips in the X-ray by the matching algorithm with the template of scale invariance and rotation invariance.The inner layer segmentation is to extract subobjects，i.e.，gold lines，balls and PAD of each chip by clustering and analyzing the ROI image and template image using the Mean Shift algorithm.Then calculates mean gray values of gold lines-pattern regions for ROI and template images respectively.Finally，according to the mean gray values of sub-patterns in the template，design an optimized threshold and segment the ROI image by the adaptive threshold segmentation algorithm.The experimental results show that the proposed segmentation algorithm achieves more accurate and reliable results compared with traditional algorithms.

Mean Shift；hierarchical segmentation；region of interest（ROI）；adaptive threshold

TP391

A

1000—9787（2016）06—0128—04

10.13873/J.1000—9787（2016）06—0128—04

2015—10—15

國家自然科學(xué)基金資助項目（61305016）；江南大學(xué)自主科研計劃青年基金資助項目（JUSRP1059）

宋淑娟（1990-），女，河南焦作人，碩士，主要研究方向為圖像處理與機(jī)器視覺。