王建璽，張國(guó)平

（平頂山學(xué)院軟件學(xué)院，平頂山467000）

一種新的大規(guī)模圖像數(shù)據(jù)集分割方法*

王建璽，張國(guó)平

（平頂山學(xué)院軟件學(xué)院，平頂山467000）

圖像分割是圖像識(shí)別過程中的一個(gè)重要步驟，在計(jì)算機(jī)視覺研究中占有非常重要的地位，圖像分割的好壞直接影響圖像識(shí)別的效果。為提高大規(guī)模圖像數(shù)據(jù)集的分割效果，實(shí)現(xiàn)自動(dòng)、快速、高質(zhì)量分割，首先采用均值漂移算法對(duì)大規(guī)模圖像進(jìn)行預(yù)分割以降低圖像規(guī)模，然后根據(jù)圖像的顏色特征使用層次聚類算法對(duì)分割后的小區(qū)域進(jìn)行聚類處理，以實(shí)現(xiàn)快速分割圖像。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效減少圖像分割時(shí)的運(yùn)算時(shí)間和空間復(fù)雜度，提高圖像分割效率，獲取良好的圖像分割效果，為后續(xù)圖像分析、理解和識(shí)別打下基礎(chǔ)。

均值漂移算法；層次聚類算法；大規(guī)模圖像數(shù)據(jù)集；圖像平滑；預(yù)分割；圖像識(shí)別

1 引 言

圖像分割是圖像識(shí)別過程中的一個(gè)重要環(huán)節(jié)，在計(jì)算機(jī)視覺研究中占有非常重要的地位。圖像分割的好壞對(duì)后續(xù)圖像分析、理解和識(shí)別至關(guān)重要［1］。目前，電子成像技術(shù)不斷提高，電子設(shè)備拍攝的圖像像素量增長(zhǎng)很快，使用聚類算法處理大像素圖像能夠獲得較好的分割效果，但單獨(dú)使用聚類算法對(duì)圖像進(jìn)行分割需要的時(shí)間太長(zhǎng)，且較高的時(shí)間復(fù)雜度和空間復(fù)雜度要求使分割實(shí)現(xiàn)起來(lái)極其困難，在某些情況下幾乎是無(wú)法實(shí)現(xiàn)的。目前，一般使用復(fù)雜度比較低的聚類算法進(jìn)行預(yù)處理，隨后再使用較高復(fù)雜度的聚類算法進(jìn)行二次聚類處理。例如分水嶺算法與譜聚類算法相結(jié)合［2］，輪廓波變換與改進(jìn)模糊C均值聚類相結(jié)合［3］，均值漂移算法與歸一化算法相結(jié)合［4］，標(biāo)記分水嶺和區(qū)域合并算法相結(jié)合［5］，EHMM－HMT與MSWHMT相結(jié)合［6］，邊緣流引導(dǎo)的各向異性擴(kuò)散算法與歸一化算法相結(jié)合［7］等。在這類圖像分割方法中，都是采用復(fù)雜度低的算法先把原始圖像劃分成較多的小區(qū)域，然后以這些小區(qū)域?yàn)闃颖?，選取這些小區(qū)域的某方面的特征進(jìn)行二次聚類處理，最后實(shí)現(xiàn)大規(guī)模圖像數(shù)據(jù)集的分割。通過這種預(yù)處理方式有效減少了二次處理的圖像集的數(shù)據(jù)量，實(shí)現(xiàn)了整體算法復(fù)雜度的降低和處理速度的提高。為此，研究中提出了一種新的圖像分割方法，首先對(duì)大規(guī)模圖像數(shù)據(jù)集采用均值漂移算法進(jìn)行預(yù)分割，再使用層次聚類算法對(duì)預(yù)分割的圖像結(jié)果進(jìn)行二次聚類處理，二者結(jié)合起來(lái)能快速有效的對(duì)大規(guī)模圖像集進(jìn)行分割，且分割效果比較好。

2 預(yù)分割

采用均值漂移算法進(jìn)行圖像分割其實(shí)是圖像平滑的擴(kuò)展，因彩色圖像數(shù)據(jù)量較大，故以彩色圖像為例，來(lái)介紹圖像平滑的過程。彩色圖像任一點(diǎn)用一個(gè)五維的向量來(lái)表示，表達(dá)式為x＝（xs，xr），這里xs表示彩色圖像二維地址空間坐標(biāo)，xr表示彩色圖像的三維特征向量。其核函數(shù)公式為：

公式（1）中，C是歸一化常量；p、d表示的是空間維度（其中p＝3，d＝2）；hs表示該核函數(shù)的半徑，指空域的核大??；hr表示特征空間半徑，表示值域的核大小。這里假設(shè)參數(shù)M為劃分區(qū)域像素?cái)?shù)目最小值，xi表示d維原始輸入圖像中的數(shù)據(jù)點(diǎn)，zi表示經(jīng)均值漂移預(yù)處理后的點(diǎn)，基于均值漂移算法的圖像平滑步驟如下：

步驟1：初始化，令j＝1且yi，1＝xi，從需要處理圖像的第一個(gè)像素點(diǎn)開始進(jìn)行計(jì)算，并把偏移過程核函數(shù)的中心位置記錄下來(lái)，直至整幅圖像處理完畢；

步驟2：根據(jù)均值漂移算法計(jì)算出的yi，j＋1值，一直到此次迭代滿足收斂條件結(jié)束，并記錄下該收斂值yi，c；

在使用均值算法進(jìn)行圖像分割時(shí)，根據(jù)圖像平滑的結(jié)果，把在同一密度極大值點(diǎn)收斂的全部像素作為同一類，對(duì)該類中的所用像素點(diǎn)賦予相同的標(biāo)號(hào)，如果得到某個(gè)類的點(diǎn)數(shù)量小于最小值M，把該類去除。具體分割過程如下：

步驟1：在圖像平滑處理過程中，根據(jù)記錄下來(lái)的五維向量的收斂點(diǎn)，把收斂于同一個(gè)點(diǎn)的像素劃歸同一個(gè)類中；

步驟2：根據(jù)hs和hr參數(shù)的值，把空間域中距離小于hs及特征空間中距離小于hr的全部點(diǎn)zi劃分到同一類中，如果最終劃分為m類，則用｛Cn｝n＝1，…，m表示；

步驟3：標(biāo)記圖像，Li＝｛n｜zi∈Cn｝，并把區(qū)域像素少于M的區(qū)域合并到與它相鄰的小區(qū)域中。

預(yù)分割后存在過分割現(xiàn)象，圖像被分割成很多比較小的區(qū)域，目標(biāo)物體被分割的較細(xì)致，物體的邊界信息都得到了很好的保留。在圖像分割中，hr、hs這兩個(gè)參數(shù)的選擇直接影響分割結(jié)果，在具體操作過程中要根據(jù)解析度要求給出具體的值。

3 二次聚類分割

3．1 圖像特征選擇

研究中采用層次聚類算法對(duì)圖像進(jìn)行二次聚類處理。因?yàn)椴噬珗D像中的顏色是最主要特征，所以把圖像的顏色信息作為特征空間，其中任一點(diǎn)的顏色可以用三維向量Xi表示，Xi＝（x1i，x2i，x3i），不同像素點(diǎn)之間的顏色差異公式為：

經(jīng)過預(yù)分割后，圖像被劃分成y個(gè)區(qū)域，任一區(qū)域用Ri（i＝1，2，…，m）表示，則任一區(qū)域的顏色向量可以用表示，這里表示第y個(gè)區(qū)域全部像素的各顏色分量的均值。為得到最佳的分割效果，選用Luv顏色模型，該模型具有線性映射特性，L表示像素點(diǎn)的亮度，u、v表示像素點(diǎn)的色度坐標(biāo)，故被分割的區(qū)域間顏色差異可用如下公式表示：

3．2 圖像分割過程

在使用層次聚類算法進(jìn)行二次聚類處理時(shí)，把預(yù)分割后的每個(gè)區(qū)域當(dāng)作一個(gè)簇，其均值用XRi表示，用計(jì)算出的每個(gè)簇之間的差異度構(gòu)成區(qū)域的鄰近度矩陣。并采用ward算法實(shí)現(xiàn)對(duì)簇的合并，因?yàn)樵撍惴ê喜⒌男Ч绕渌麑哟尉垲愃惴ê?。它采用全局目?biāo)函數(shù)實(shí)現(xiàn)層次聚類，首先計(jì)算鄰近度矩陣中所有鄰近簇的誤差平方和（SSE），然后合并平方和的增量最小的兩個(gè)鄰近簇，合并后更新鄰近度矩陣，共經(jīng)過n－k次鄰近簇合并，最終產(chǎn)生k個(gè)簇。假設(shè)合并后的簇C*的質(zhì)心用u*表示，而ni、ui、nj、uj分別表示簇Ci，Cj的大小與均值。則簇Ci，Cj的鄰近度更新計(jì)算公式為：

則兩個(gè)簇的誤差平方和為：

故簇Ci，Cj的距離為：

在對(duì)圖像進(jìn)行全部分割后，在圖像中還會(huì)存在一些孤立的沒有被合并的區(qū)域，這些孤立的區(qū)域可以采用四鄰加權(quán)法進(jìn)行處理，處理后的圖像得到一定的平滑，其中一些細(xì)小的噪聲點(diǎn)可以去除。

下面對(duì)結(jié)合均值漂移和層次聚類算法實(shí)現(xiàn)圖像分割的過程進(jìn)行描述。首先是預(yù)分割，采用均值漂移算法對(duì)輸入的彩色圖像進(jìn)行分割，產(chǎn)生較多的小區(qū)域；接著根據(jù)預(yù)分割的結(jié)果，計(jì)算所劃分區(qū)域像素點(diǎn)的顏色均值，將每個(gè)區(qū)域的顏色均值作為層次聚類算法需要輸入的一個(gè)數(shù)據(jù)點(diǎn)；然后根據(jù)層次聚類算法，將每個(gè)區(qū)域的均值數(shù)據(jù)當(dāng)作一個(gè)簇，構(gòu)成圖像的鄰近度矩陣；根據(jù)距離函數(shù)計(jì)算相鄰簇的誤差平方和，選擇誤差平方和增量最小的相鄰兩個(gè)簇合并，并更新鄰近度矩陣，重復(fù)這一步n－k次，直到滿足設(shè)定的分割類別數(shù)k；最后應(yīng)用加權(quán)算子進(jìn)行分割后處理，去除圖像中的孤立噪點(diǎn)。

4 實(shí)驗(yàn)結(jié)果與分析

在MATLAB2013b環(huán)境下進(jìn)行實(shí)驗(yàn)。預(yù)分割時(shí)均值漂移算法的參數(shù)設(shè)置為hs＝9，hr＝8，，M＝60，hs表示空域帶寬，hr表示值域帶寬，M表示區(qū)域像素的下限值。圖像均從Berkeley的標(biāo)準(zhǔn)彩色圖像庫(kù)BSDS500中進(jìn)行選擇［8］。在使用均值漂移算法分割之后，圖像被劃分成很多小區(qū)域，但是分割的區(qū)域數(shù)已經(jīng)遠(yuǎn)遠(yuǎn)小于原始圖像的像素?cái)?shù)目，但分割的區(qū)域仍較多，再應(yīng)用層次聚類算法進(jìn)行二次聚類處理，把需要合并的區(qū)域合并之后，分割效果就比較好了。運(yùn)用研究中提出的算法進(jìn)行圖像分割時(shí)，考慮到原始圖像的整體情況，分割后的孤立點(diǎn)很少，分割的邊緣很平滑，得到的分割效果較好，圖1是實(shí)驗(yàn)分割效果圖。

圖1 分割結(jié)果Fig．1 Segmentation results

通過實(shí)驗(yàn)可知，圖像分割所花費(fèi)的時(shí)間主要在預(yù)分割階段，花費(fèi)時(shí)間在0．6s左右，而聚類合并階段速度較快，花費(fèi)時(shí)間不到0．1s。對(duì)150×200像素的圖像來(lái)說(shuō)，圖像的像素點(diǎn)數(shù)為30000，如果直接采用層次聚類算法進(jìn)行分割，產(chǎn)生的鄰近度矩陣為30000×30000，對(duì)該矩陣的運(yùn)算需要特別大的內(nèi)存空間，一般的機(jī)器是無(wú)法運(yùn)行的。研究中采用的這種方法，用分割得到的小區(qū)域代替圖像像素點(diǎn)，一般情況下分割的區(qū)域不超過300，可見對(duì)不超過300的數(shù)據(jù)組成的矩陣進(jìn)行處理能夠有效降低層次聚類算法輸入的數(shù)據(jù)規(guī)模，使二次聚類合并的運(yùn)算時(shí)間和空間復(fù)雜度得到有效降低，實(shí)驗(yàn)數(shù)據(jù)證明提出的方法在進(jìn)行大規(guī)模數(shù)據(jù)集處理時(shí)是可行的。

5 結(jié)束語(yǔ)

研究中把均值漂移和層次聚類算法結(jié)合起來(lái)對(duì)大規(guī)模圖像數(shù)據(jù)集進(jìn)行分割，既達(dá)到了預(yù)期的分割效果，又提高了分割速度，且分割效果較好，是一種大規(guī)模圖像數(shù)據(jù)集分割的有效方法。

［1］ 許新征，丁世飛，史忠植，等．圖像分割的新理論新方法［J］．電子學(xué)報(bào)，2010，38（2A）：6－82．XU Xin－zheng，DING Shi－fei，SHI Zhong－zhi，et al．New Theories and Methods of Image Segmentation［J］．Acta Electronica Sinica，2010，38（2A）：6－82．

［2］ 馬秀麗，焦李成．基于分水嶺－譜聚類的SAR圖像分割［J］．紅外與毫米波學(xué)報(bào)，2008，27（6）：452－456．MA Xiu－Li，JIAO Li－Cheng．SAR IMAGE SEGMENTATION BASED ON WATERSHED AND SPECTRAL CLUSTERING［J］．Journal of Infrared and Millimeter Waves，2008，27（6）：452－456．

［3］ 劉剛，梁曉庚，張京國(guó)．基于輪廓波變換和改進(jìn)模糊c均值聚類的紅外圖像分割［J］．系統(tǒng)工程與電子技術(shù)，2011，33（2）：443－448．LIU Gang，LIANG Xiao－geng，ZHANG Jing－guo．Contourlet transform and improved fuzzy c－means clustering based infrared image segmentation［J］．Systems Engineering and Electronics，2011，33（2）：443－448．

［4］ Wenbing Tao，Hai Jin，Yimin Zhang．Color Image Segmentation Based on Mean Shift and Normalized Cuts［J］．IEEE Transactions on Systems，Man，and Cybernetics－Part B：Cybernetics，2007，37（5）：1382－1389．

［5］ 余旺盛，侯志強(qiáng)，宋建軍．基于標(biāo)記分水嶺和區(qū)域合并的彩色圖像分割［J］．電子學(xué)報(bào)，2011，39（5）：1007－1012．YU Wang－sheng，HOU Zhi－qiang，SONG Jian－jun．Color Image Segmentation Based on Marked－Watershed and Region－Merger［J］．Acta Electronica Sinica，2011，39（5）：1007－1012．

［6］ 陳蓉偉，劉芳，郝紅俠．基于EHMM－HMT和MSW HMT的多尺度紋理圖像分割［J］．軟件學(xué)報(bào)，2010，21（9）：2206－2223．CHEN Rong－Wei，LIU Fang，HAO Hong－Xia．Multi－Scale Texture Image Segmentation Based on EHMMHMT and MSWHMT Models［J］．Journal of Software，2010，21（9）：2206－2223．

［7］ 徐麗燕，張潔玉，孫權(quán)森，等．結(jié)合EFD與NCut的彩色圖像分割方法［J］．模式識(shí)別與人工智能，2010，23（5）：671－677．XU Li－Yan，ZHANG Jie－Yu，SUN Quan－Sen，et al．Color Image Segmentation Approach by Combining EFD and NCut［J］．Pattern Recognition and Aitificial Intelligence，2010，23（5）：671－677．

［8］ Arbeláez Pablo，Maire Michael，F(xiàn)owlkes Charless，et al．Contour detection and hierarchical image segmentation［J］．IEEE Trans Pattern Anal Mach Intell，2010，33（5）：898－916．

A New Segmentation Method of Large Scale Image Datasets

Wang Jianxi，Zhang Guoping
（Software Institute，Pingdingshan University，Pingdingshan 467000，China）

：Image segmentation，as an key part in the process of image recognition，performs the important effect on the research of computer vision because the image segmentation will affect the result of image recognition．To improve the segmentation effect of large scale image datasets and realize segmentation in automatic，high speed and high quality，this paper first uses the mean shift algorithm for large scale image datasets segmentation to reduce the image size，then，according to the color of the images features，uses hierarchical clustering algorithm to perform clustering processing for the small area after segmentation in order to quickly achieve segmentation of images．The test results show that this method can effectively reduce the operation time and space complexity，improve the efficiency of image segmentation，obtain good image segmentation effect，and lay the foundation for analysis，understanding and recognition of the image．

Mean Shift Algorithm；Hierarchical Clustering Algorithm；Large Scale Image Datasets；Image Smooth；Pre－segmentation；Image Recognition

10．3969／j．issn．1002－2279．2015．04．016

TP391．4

A

1002－2279（2015）04－0061－03

河南省科技廳科技發(fā)展計(jì)劃項(xiàng)目（134300510037）

王建璽（1981－），女，河南社旗人，碩士研究生，講師，主研方向：模式識(shí)別、圖像處理等。

2014－12－26