基于全局K-means算法的超像素分割方法

吉長東, 李相澤, 敖國政(. 遼寧工程技術大學 測繪與地理科學學院, 遼寧 阜新 505;. 東北大學 計算機科學與工程學院, 遼寧 沈陽 089;. 遼寧工業(yè)大學 電子與信息工程學院, 遼寧 錦州 00)

?

基于全局K-means算法的超像素分割方法

吉長東1, 李相澤2, 敖國政3
(1. 遼寧工程技術大學 測繪與地理科學學院, 遼寧 阜新 125105;2. 東北大學 計算機科學與工程學院, 遼寧 沈陽 110819;3. 遼寧工業(yè)大學 電子與信息工程學院, 遼寧 錦州 121001)

為了提高超像素分割的性能,提出了一種基于全局K-means算法的超像素分割方法。該算法利用全局K-means算法計算超像素聚類,優(yōu)化了超像素的分割質量,并根據聚類后的超像素結果從圖像中分割出目標.實驗數據來自于國際公認的PASCAL VOC 2007數據集.實驗結果表明,與Wang算法和ISLIC算法相比,提出的分割算法的PRI、CR、VOI及運行時間4個指標分別平均提高9.38%、17.13%、21.67%、10.50%,可以實現更佳的圖像分割效果.

圖像分割; 超像素; 全局K-means算法; 聚類

圖像分割是圖像處理中的重要部分,良好的分割算法能夠對目標提取和識別提供巨大幫助.為了提高分割算法的性能,加州大學的X.Ren和J.Malik提出了一種符合人類視覺感知的自然圖像分割算法,即超像素(Superpixel)[1].近幾年,在計算機視覺方面,超像素已經受到了廣泛的重視[2-3].與普通的像素相比,超像素有4個優(yōu)勢:①計算復雜度低;②符合人眼特點;③圖像信息描述效率高;④圖像信息保存完整.雖然超像素具有許多良好的屬性,但是這些屬性的發(fā)揮都是基于高質量的超像素.所以,如何分割出超像素就成為關鍵問題.目前,對于超像素分割已經提出了許多有效的改進算法.Liu等人[4]提出了基于熵率的ERS(entropy rate superpixel segmentation)算法,該算法通過構造新的目標函數,直接控制生成的超像素數量,獲得的超像素邊緣貼合度較好;Zhang等人[5]提出了基于偽布爾函數(pseudo-boolean function)的超像素分割算法,其基本思想是將圖像從垂直和水平兩個方向用半重疊的圖像帶(strip)覆蓋,使任意像素只屬于其中一個圖像帶;Bergh 等人[6]提出了SEEDS算法,該算法從一個規(guī)則圖像網格出發(fā),漸進地修正超像素邊緣的像素點,最終獲得分割結果;Wang等人[7]提出了結構敏感的超像素分割算法,該算法利用測地線距離代替歐氏距離度量像素間相似性,用于衡量圖像局部結構密度.該算法能夠根據圖像結構密度自適應地調整超像素分布疏密程度,同時保持了較高的計算效率.

本文基于全局K-means算法來分割超像素,該算法是傳統(tǒng)K-means算法的一種有效改進.通過實驗證明,該算法獲得的超像素能夠有效地對靜態(tài)圖像中的目標進行提取.

1 K-means算法

K-means算法是一種聚類算法,不同的學者在不同的領域分別獨立提出了這種聚類思想[8].雖然K-means算法提出至今已經有半個世紀,但依然是應用最廣泛的聚類算法之一.

1.1K-means算法特點

K-means算法能對大型數據集進行高效分類,其計算復雜性為O(tKmn).其中,t為迭代次數,K為聚類數,m為特征屬性數,n為待分類的對象數,通常m

但K-means算法存在著如下四個主要缺點:①分群結果與初始點的選取有關,分群的結果不穩(wěn)定甚至錯誤;②對于球形群的聚類效果會很好,但卻無法適用于任意形狀的群;③對離群與噪聲目標較為敏感;④只適用于數值型數據,對于分類型數據則難以進行處理.

此外,K-means算法在目標分群的應用上也具有一定的局限性.通常,目標會用很多個屬性特征來描述,而對于目標分群而言,有些屬性很重要,但有些屬性特征甚至不會影響到目標對象的聚類[8].有很多傳統(tǒng)的基于距離的聚類方法應用到目標的復雜多維屬性特征上獲得的效果很不理想.主要原因是傳統(tǒng)K-means類的算法所采用的度量準則是單純的歐氏距離的度量方法,也就是計算每個樣本數據到每個聚類中心的歐氏距離,最后將數據劃入距離最近的類中.由于該方法沒有區(qū)分每個屬性對于聚類的重要程度,在進行多維復雜數據聚類時,傳統(tǒng)K-means算法的效果很不理想.

1.2K-means算法流程

K-means算法應用于目標分群的主要流程:

輸入:群的數目k;包含n個目標實體的數據庫.

輸出:k個群.

步驟如下:

(1) 初始化,隨機指定k個聚類中心(c1,c2,…,ck);

(2) 分配xi,對每一個樣本xi,找到離它最近的聚類中心cv,并將其分配到cw所標明的類;

(3) 修正cw,將每一個cw移動到其標明的類的中心;

(5) 判斷D是否收斂,如果D值收斂,則return(c1,c2,…,ck)并終止本算法;否則,返回步驟(2).

2 基于全局K-means的超像素分割

與普通像素點相比,利用超像素描述圖像信息能夠獲得更高的效率.因為超像素劃分之后,會以此為單位對圖像的各項特征進行統(tǒng)計,這樣可以高效描述圖像信息,由此對后續(xù)的圖像處理都有很大幫助.超像素的形成是根據相似特征得到的,屬于聚類問題,所以本文使用全局K-means算法來獲取超像素.

2.1 全局K-means算法

K-means算法在進行超像素分割的過程中,主要的問題就是由于其聚類結果嚴重依賴于初始聚類中心的選取,最終聚類結果非常不穩(wěn)定,從而對每次得到的超像素影響很大.為了解決對初始位置敏感這一瓶頸問題,A.Likas等人提出了一種確定性的全局優(yōu)化算法即GlobalK-means(GKM)算法,該方法初始點的選取不依賴于任何初始參數值,在其局部搜索上使用K-means算法[9-10].與大部分全局聚類算法不同的是,GKM算法采用一種增量的方式,即每循環(huán)一次只增加一個新的聚類中心而不是隨機地選取所有初始聚類中心.由此可見,該算法對于超像素分割非常適用.

GKM算法的基本框架如下:

輸入:聚類數K,數據Xij,1≤i≤N,1≤j≤D;

輸出:最終聚類中心(z1,…,zk),聚類錯誤F.

步驟如下:

(1) 初始化k=1,z1=mean(X);

(2) 利用K-means算法求出第k+1類的初始最優(yōu)類中心;

(3) 利用K-means算法優(yōu)化得到的前k+1類聚類中心(z1,…,zk,zk+1);

(4) 如果k+1>K,算法結束,否則返回步驟(2),并且k=k+1.

GKM算法首先解決僅聚為一類(k=1)的問題,此時最優(yōu)的聚類中心位于所有數據的質心位置,即z1=mean(X).當本文已經求出了k(k>1)類問題的結果之后,就通過以下方式求解k+1類聚類問題:(z1,…,zk)表示已經求出的k類問題的最優(yōu)解,設置初始位置為(z1,…,zk,xi)(i=1,2,…,N)執(zhí)行N次K-means算法得出的最優(yōu)結果所對應的聚類中心就是k+1類聚類問題的初始最優(yōu)解.然后執(zhí)行K-means算法優(yōu)化初始解(z1,…,zk,zk+1)直到結果不再改善為止[11-12].

GKM算法通過一個確定有效的全局搜索來最小化聚類錯誤函數,故其性能因為不受聚類中心初始位置的影響而非常穩(wěn)定.GKM算法較K-means算法是相當具有優(yōu)勢的.

2.2 超像素分割

在利用GKM算法進行超像素分割時,需要的參數是目標超像素個數S.GKM生成超像素過程如下:

(1) 首先,如果原始圖像為RGB空間,需要先將其轉化為CIELab顏色空間.轉換過程為先將RGB轉換到CIEXYZ顏色空間,如式(1)所示,然后再轉換到CIELab顏色空間,如式(2)～式(4)所示.

(1)

(2)

(3)

(4)

(2) 均勻初始化聚類中心點并利用GKM算法對圖像中的像素點進行聚類.

圖1展示了GKM算法生成超像素的效果,圖1a為S=1 000時的分割結果;圖1b為S=2 000時的分割結果;圖1c為S=3 000時的分割結果.

圖1 利用GKM算法生成超像素Fig.1 Superpixel generation based on GKM algorithm(a)—S=1 000; (b)—S=2 000; (c)—S=3 000.

參數S過大會產生分割現象,過小有可能分割比較粗糙,所以適中的參數S對于分割效果非常重要.

3 仿真結果及分析

本文實驗的硬件環(huán)境:CPU為Intel Core I7 4770kB,內存8 GB.程序的運行環(huán)境是Windows 7操作系統(tǒng)下的MATLAB R2013a.對于實驗的數據集,本文實驗使用國際公認的數據集VOC 2007.該數據集包括9 963張圖片,共分成20個目標類.

實驗部分首先將本文算法與Wang算法和ISLIC算法比較.圖2分別展示了這3種算法的分割結果,各個算法選取的都是最優(yōu)閾值,本文算法的S=2 000,而Wang算法和ISLIC算法的S=3 000.分割過程中最重要的是保證感興趣區(qū)域(ROI)與實際分割區(qū)域之間的一致性.如圖2所示,Wang算法由于更加關注算法效率,分割效果略有下降.ISLIC算法是對SLIC算法的改進,超像素的貼合度更高,分割效果比較好.

表1所示為三種算法的分割結果數據對比.利用PRI(probabilistic rand index)、VOI(variation of information)以及CR(covering rate)三個指標對分割結果進行評價.PRI值和CR值在區(qū)間[0,1]內,值越大說明分割結果越好;VOI值在區(qū)間[0,+∞)內,值越小說明分割結果越好.表中的1st代表圖2中的第一列圖片,2nd代表第二列圖片,3rd代表第三列圖片.

表1 分割結果對比Table 1 Comparison of segmentation results

表2展示了算法的執(zhí)行效率對比.通過表2可以看出,Wang算法運行時間略低于本文算法,但是與平均值的對比可以體現出算法在運行速度上具有一定優(yōu)勢.所以總體而言,本文的算法在各項性能上都有一定提高.

表2 運行時間對比Table 2 Comparison of running time

4 結 語

本文分析了傳統(tǒng)K-means算法的局限性,并針對這些不足引入全局K-means算法提出了改進的超像素分割算法.為了驗證基于全局K-means算法的超像素分割方法的有效性,本文選取了Wang算法和ISLIC算法等相關算法作為實驗參照.通過仿真實驗驗證,本文提出的改進算法獲得了良好的分割效果.

[ 1 ] 田丹,吳靜飛,范立南. 水平集理論在磁共振腦圖像分割中的模型研究[J]. 沈陽大學學報(自然科學版), 2013,25(4):298-302. (TIAN D,WU J F,FAN L N. Survey on model of level set in MR brain image segmentation[J]. Journal of Shenyang University(Natural Science), 2013,25(4):298-302.)

[ 2 ] WANG S,LU H,YANG F,et al. Superpixel tracking[C]∥International Conference on Computer Vision. IEEE Computer Society, 2011:1323-1330.

[ 3 ] CHANG J,WEI D,FISHER J W. A video representation using temporal superpixels[C]∥IEEE Conference on Computer Vision & Pattern Recognition. IEEE, 2013:2051-2058.

[ 4 ] LIU M Y,TUZEL O,RAMALINGAM S,et al. Entropy rate superpixel segmentation[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern recognition. Washington DC,USA: IEEE, 2011:2097-2104.

[ 5 ] ZHANG Y,HARTLEY R,MASHFORD J,et al. Superpixels via pseudo-Boolean optimization [C]∥Proceedings of IEEE International Conference on Computer Vision. Washington DC, USA: IEEE, 2011:1387-1394.

[ 6 ] BERGH M V D,BOIX X,ROIG G,et al. SEEDS: Superpixels extracted via energy-driven sampling[M]∥Computer Vision-ECCV 2012. Berlin Heidelberg: Springer, 2012:13-26.

[ 7 ] WANG P,ZENG G,GAN R,et al. Structure-sensitive superpixels via geodesic distance[J]. International Journal of Computer Vision, 2013,103(1):1-21.

[ 8 ] 惠轉妮. 基于GlobalK-means的多維數據聚類算法研究及其GPU加速[D]. 西安:西安電子科技大學, 2012. (HUI Z N. Research on multidimensional data clustering algorithm based on globalK-means and its GPU acceleration[D]. Xi’an: Xidian University, 2012.)

[ 9 ] 岳溫川,王衛(wèi)衛(wèi),李小平. 基于加權稀疏子空間聚類多特征融合圖像分割[J]. 系統(tǒng)工程與電子技術, 2016,38(9):2184-2191. (YUE W C,WANG W W,LI X P. Multi-feature fusion image segmentation based on weighted-sparse subspace clustering[J]. Systems Engineering and Electronics, 2016,38(9):2184-2191.)

[10] 陳愷,陳芳,戴敏,等. 基于螢火蟲算法的二維熵多閾值快速圖像分割[J]. 光學精密工程, 2014,22(2):517-523. (CHEN K,CHEN F,DAI M,et al.Fast image segmentation with multilevel threshold of two-dimensional entropy based on firefly algorithm[J]. Optics and Precision Engineering, 2014,22(2):517-523.)

[11] 周晨航,田力威,趙宏偉. 基于改進螢火蟲算法的二維Otsu圖像分割法[J]. 沈陽大學學報(自然科學版), 2016,28(1):45-50. (ZHOU C H,TIAN L W,ZHAO H W. Image thresholding segmentation with 2-D otsu based on improved firefly algorithm[J]. Journal of Shenyang University(Natural Science), 2016,28(1):45-50.)

[12] 許志遠,王庸凱,孫康,等. 基于CLAHE的DSP實時去霧系統(tǒng)[J]. 沈陽大學學報(自然科學版), 2014,26(4):296-300. (XU Z Y,WANG Y K,SUN K,et al.DSP real-time fog removal system based on CLAHE[J]. Journal of Shenyang University(Natural Science), 2014,26(4):296-300.)

【責任編輯: 李 艷】

Superpixel Segmentation Method Based on GlobalK-means

JiChangdong1,LiXiangze2,AoGuozheng3

(1. School of Geomatics, Liaoning Technical University, Fuxin 125105, China; 2. School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China; 3. School of Electronics & Information Engineering, Liaoning University of Technology, Jinzhou 121001, China)

In order to improve the performance of the superpixel segmentation, a superpixel segmentation method based on globalK-means algorithm is proposed. The algorithm uses the globalK-means algorithm to compute the superpixel clustering, optimizes the segmentation quality of the superpixel, and divides the target from the image according to the superpixel result after clustering. The experimental data came from the international recognized PASCAL VOC 2007 data sets. The experimental results show that compared with the Wang algorithm and ISLIC algorithm, the proposed segmentation algorithm has an average increase of 9.38%, 17.13%, 21.67% and 10.50% respectively in PRI, CR, VOI and run time, and has better performance.

image segmentation; superpixel; globalK-means; cluster

2016-01-30

國家科技重大專項資助項目(2013ZX04007031); 國家科技重大專項資助項目(2012ZX01029001-002).

吉長東(1970-),男,遼寧錦州人,遼寧工程技術大學教授.

2095-5456(2017)03-0212-05

TP 391.4

A