一種新的大規模圖像數據集分割方法*

王建璽，張國平

（平頂山學院軟件學院，平頂山467000）

一種新的大規模圖像數據集分割方法*

王建璽，張國平

（平頂山學院軟件學院，平頂山467000）

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

均值漂移算法；層次聚類算法；大規模圖像數據集；圖像平滑；預分割；圖像識別

1 引 言

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

2 預分割

采用均值漂移算法進行圖像分割其實是圖像平滑的擴展，因彩色圖像數據量較大，故以彩色圖像為例，來介紹圖像平滑的過程。彩色圖像任一點用一個五維的向量來表示，表達式為x＝（xs，xr），這里xs表示彩色圖像二維地址空間坐標，xr表示彩色圖像的三維特征向量。其核函數公式為：

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

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

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

在使用均值算法進行圖像分割時，根據圖像平滑的結果，把在同一密度極大值點收斂的全部像素作為同一類，對該類中的所用像素點賦予相同的標號，如果得到某個類的點數量小于最小值M，把該類去除。具體分割過程如下：

步驟1：在圖像平滑處理過程中，根據記錄下來的五維向量的收斂點，把收斂于同一個點的像素劃歸同一個類中；

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

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

預分割后存在過分割現象，圖像被分割成很多比較小的區域，目標物體被分割的較細致，物體的邊界信息都得到了很好的保留。在圖像分割中，hr、hs這兩個參數的選擇直接影響分割結果，在具體操作過程中要根據解析度要求給出具體的值。

3 二次聚類分割

3．1 圖像特征選擇

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

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

3．2 圖像分割過程

在使用層次聚類算法進行二次聚類處理時，把預分割后的每個區域當作一個簇，其均值用XRi表示，用計算出的每個簇之間的差異度構成區域的鄰近度矩陣。并采用ward算法實現對簇的合并，因為該算法合并的效果比其他層次聚類算法好。它采用全局目標函數實現層次聚類，首先計算鄰近度矩陣中所有鄰近簇的誤差平方和（SSE），然后合并平方和的增量最小的兩個鄰近簇，合并后更新鄰近度矩陣，共經過n－k次鄰近簇合并，最終產生k個簇。假設合并后的簇C*的質心用u*表示，而ni、ui、nj、uj分別表示簇Ci，Cj的大小與均值。則簇Ci，Cj的鄰近度更新計算公式為：

則兩個簇的誤差平方和為：

故簇Ci，Cj的距離為：

在對圖像進行全部分割后，在圖像中還會存在一些孤立的沒有被合并的區域，這些孤立的區域可以采用四鄰加權法進行處理，處理后的圖像得到一定的平滑，其中一些細小的噪聲點可以去除。

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

4 實驗結果與分析

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

圖1 分割結果Fig．1 Segmentation results

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

5 結束語

研究中把均值漂移和層次聚類算法結合起來對大規模圖像數據集進行分割，既達到了預期的分割效果，又提高了分割速度，且分割效果較好，是一種大規模圖像數據集分割的有效方法。

［1］ 許新征，丁世飛，史忠植，等．圖像分割的新理論新方法［J］．電子學報，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］．紅外與毫米波學報，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］ 劉剛，梁曉庚，張京國．基于輪廓波變換和改進模糊c均值聚類的紅外圖像分割［J］．系統工程與電子技術，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］ 余旺盛，侯志強，宋建軍．基于標記分水嶺和區域合并的彩色圖像分割［J］．電子學報，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］．軟件學報，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］ 徐麗燕，張潔玉，孫權森，等．結合EFD與NCut的彩色圖像分割方法［J］．模式識別與人工智能，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，Fowlkes 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

河南省科技廳科技發展計劃項目（134300510037）

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

2014－12－26