李昌興， 黃艷虎， 支曉斌， 謝笑娟

(1.西安郵電大學(xué) 理學(xué)院，陜西 西安 710121；2.西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

?

基于加速k均值的譜聚類圖像分割算法改進(jìn)*

李昌興1， 黃艷虎2， 支曉斌1， 謝笑娟1

(1.西安郵電大學(xué) 理學(xué)院，陜西 西安 710121；2.西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

對(duì)譜聚類圖像分割算法進(jìn)行改進(jìn)，即引入加速 均值算法替換原算法中的k均值算法，得出加速譜聚類的圖像分割算法。將改進(jìn)算法應(yīng)用于微軟劍橋研究院Grab cut數(shù)據(jù)集中的5幅實(shí)驗(yàn)圖像，結(jié)果顯示：在平均區(qū)域一致性評(píng)價(jià)不降低的前提下，改進(jìn)算法完成分割所花費(fèi)的平均時(shí)間比改進(jìn)前可縮短58 %。

圖像分割； 譜聚類； 加速k均值； 加速譜聚類

0　引　言

圖像分割是計(jì)算機(jī)視覺領(lǐng)域的重要組成部分[1]。譜聚類算法[2]在圖像分割和特征提取方面應(yīng)用廣泛[3]。

譜聚類算法能在任意形狀的樣本空間上聚類，且收斂于全局最優(yōu)解[4]，將譜聚類算法應(yīng)用于圖像分割，通常能取得很好的分割效果[5]，但同時(shí)它也有著自身的缺陷—計(jì)算相似性矩陣高度復(fù)雜，問題的求解會(huì)變得異常費(fèi)時(shí)[6]。文獻(xiàn)[7]中提出基于路徑的相似性度量，但對(duì)邊界點(diǎn)過于敏感，分割耗時(shí)不理想；文獻(xiàn)[8]提出基于密度敏感的相似性度量，但當(dāng)位于高密度區(qū)的兩個(gè)樣本數(shù)據(jù)點(diǎn)穿過的路徑較長(zhǎng)時(shí)，效果尚不明顯，并且最終采用k均值聚類簡(jiǎn)化后的向量空間，造成聚類耗時(shí)過長(zhǎng)。本文對(duì)譜聚類圖像分割算法進(jìn)行了改進(jìn)，即引入加速 均值替換原有算法中的k均值算法，得出加速譜聚類的圖像分割算法。

1　譜聚類算法與 均值算法

1.1譜聚類算法

給定n個(gè)數(shù)據(jù)點(diǎn)x1,x2,…,xn，譜聚類算法構(gòu)建了一個(gè)相似性矩陣，它反映了xi與xj之間的關(guān)系。然后，它使用相似性信息，將x1,x2,…,xn聚類成k個(gè)簇[9]。譜聚類有很多種解釋，最常用的就是基于圖切的理論。它要求將譜聚類轉(zhuǎn)化為求出數(shù)據(jù)集的Laplacian矩陣，然后再求該矩陣的特征向量，進(jìn)而對(duì)特征向量進(jìn)行聚類[10]。其算法流程如下：

1)計(jì)算數(shù)據(jù)間的相似性矩陣W=(wij),其中,wij=exp(‖xi-xj‖22σ2),(i,j=1,2,…，n)。

3)計(jì)算Laplacian矩陣L，一般取L=D-1/2WD-1/2。

4)計(jì)算矩陣L的前k個(gè)特征值所對(duì)應(yīng)的特征向量v1,v2,…,vk。

5)將v1,v2,…,vk按列組成矩陣V∈Rn×k。

6)對(duì)于i=1,2,…,n,令yi∈Rk是對(duì)應(yīng)于V的第i行所構(gòu)成向量。

7)將點(diǎn)yi(i=1,2,…,n)用k均值算法聚類成簇C1,C2,…,Ck。

譜聚類算法有著它自身的缺陷。當(dāng)將譜聚類算法用于圖像分割時(shí)，一般是以圖像的像素作為輸入數(shù)據(jù)，而一幅圖像像素通常在百萬以上，這時(shí)，相似性矩陣的計(jì)算，存儲(chǔ)以及特征值求解都面臨著巨大的困難[11]，導(dǎo)致計(jì)算時(shí)間過長(zhǎng)。目前通用算法最后一步都是以k均值算法對(duì)拉普拉斯矩陣進(jìn)行聚類，如能將k均值算法替換成比k均值更快的加速k均值算法，那么可對(duì)譜聚類算法的收斂速度起到一定的增幅作用。

1.2k均值算法

k均值算法在模式識(shí)別中被叫做Lloyd算法[12]，其算法的兩個(gè)主要步驟：

1)對(duì)n個(gè)數(shù)據(jù)點(diǎn)X={x1,x2,…,xn}任意選擇k個(gè)對(duì)象作為初始聚類中心c1,c2,…,ck， 計(jì)算每對(duì)x和c之間的距離，分配x到其最接近的聚類中心。

2)重新計(jì)算每個(gè)聚類的均值作為新的聚類中心。

k均值算法雖然是迄今為止使用最廣泛的一種聚類算法，但當(dāng)它處理巨量數(shù)據(jù)時(shí)，由于要計(jì)算多中心點(diǎn)之間的距離且需要許多次迭代來達(dá)到收斂，k均值算法非常緩慢。文獻(xiàn)[13]提出了一種利用三角不等式來加速經(jīng)典k均值算法。

2　加速譜聚類算法

2.1加速k均值算法

在k均值中大多數(shù)的距離計(jì)算在算法中是多余的。如果一個(gè)點(diǎn)遠(yuǎn)離一個(gè)中心，就沒必要為了知道這個(gè)數(shù)據(jù)點(diǎn)不屬于這個(gè)中心而計(jì)算它們之間的距離。相反，如果一個(gè)點(diǎn)比任何其他點(diǎn)更接近一個(gè)中心，也就沒有必要為了知道這個(gè)數(shù)據(jù)點(diǎn)應(yīng)該被分配到這個(gè)中心而計(jì)算它們之間精確的距離。令x是任何數(shù)據(jù)點(diǎn)，c是當(dāng)前為x分配的簇中心，并設(shè)c′是任何其他中心。

如果知道d(x,c)的上限為u(x)，且

則

則不必計(jì)算d(x,c′)。

又設(shè)c′為某個(gè)簇的中心，該簇中包含數(shù)據(jù)點(diǎn)x，c″為前一次迭代過程中的中心點(diǎn)。如果

d(x,c″)≥l(x,c″)

則

d(x,c′)≥max{0,d(x,c″)-d(c′,c″)}

≥max{0,l(x,c″)-d(c′,c″)}

=l(x,c′)

如果d(x,c)的上限u(x)與d(x,c′)的下限l(x,c′)存在，并且

u(x)≤l(x,c′)

則

d(x,c)≤u(x)≤l(x,c′)≤d(x,c′)

加速k均值法可以描述如下：

初始化：選擇初始中心。對(duì)于每個(gè)數(shù)據(jù)點(diǎn)x和中心c，設(shè)定下限

l(x,c)=0

分配每個(gè)x到其最近的初始中心

c(x)=argmincd(x,c)

每當(dāng)d(x,c)被計(jì)算時(shí)，令

l(x,c)=d(x,c)

上限

u(x)=mincd(x,c)

下面，重復(fù)直到算法收斂。

2)確定所有滿足u(x)≤s(c(x))的x點(diǎn)。

3)對(duì)于所有剩余的點(diǎn)x和中心c必滿足

c≠c(x)

u(x)>l(x,c),

三個(gè)條件。

1)如果r(x)為真，則計(jì)算d(x,c(x))和令

r(x)=false;

否則

d(x,c(x))=u(x)

2)如果

d(x,c(x))>l(x,c)

或者

則計(jì)算d(x,c)，如果

d(x,c)

令

c(x)=c

4)對(duì)于每個(gè)中心c，讓m(c)為被分配到c點(diǎn)的平均值。

5)對(duì)于每個(gè)點(diǎn)的x和中心c，分配

l(x,c)=max{l(x,c)-d(c,m(c)),0}。

6)對(duì)于每個(gè)點(diǎn)x，分配

u(x)=u(x)+d(m(c(x)),c(x)),

r(x)=true。

7)用m(c)替換每個(gè)中心c。

2.2加速譜聚類算法

對(duì)譜聚類圖像分割算法進(jìn)行如下改進(jìn)，即引入加速k均值替換原有算法中的k均值算法，得出加速譜聚類的圖像分割算法。其算法步驟如下：

1)依次計(jì)算相似性矩陣W、度矩陣D以及拉普拉斯矩陣L。

2)計(jì)算L的前k個(gè)特征值所對(duì)應(yīng)的特征向量v1,v2,…,vk，并將它們按列組成矩陣V。

3)對(duì)V的n個(gè)行向量執(zhí)行加速k均值，聚類成簇C1,C2,…,Ck。

3　實(shí)驗(yàn)結(jié)果

計(jì)算機(jī)配置為酷睿2代處理器，2.2 GHz主頻，4 GB內(nèi)存以及320 GB硬盤。算法實(shí)現(xiàn)基于Win7操作系統(tǒng)，仿真軟件由Matlab2010b。

圖1～圖5給出了兩種譜聚類的分割效果，其中(a)選自微軟劍橋研究院Grab Cut數(shù)據(jù)集[14]中的5幅作為原始圖像。各圖中(b)列為原譜聚類處理后的效果，(c)列為快速譜聚類算法處理后的效果。

圖1　對(duì)蔬菜圖像用不同算法分割的效果

圖2　對(duì)大兵圖像用不同算法分割的效果

圖3　對(duì)樹圖像用不同算法分割的效果

圖4　對(duì)工人圖像用不同算法分割的效果

圖5　對(duì)蘑菇圖像用不同算法分割的效果

可以看出，加速譜聚類算法對(duì)圖像的分割效果與原譜聚類相當(dāng)。客觀地，用區(qū)域一致性[15]對(duì)兩種算法進(jìn)行評(píng)價(jià)如表1，數(shù)據(jù)顯示，5幅圖像的區(qū)域一致性平均提高了0.004 %，新算法完全可以勝任圖像分割的要求。

表1　算法的區(qū)域一致性評(píng)價(jià)

表2給出了兩種算法的運(yùn)行時(shí)間。

表2　算法運(yùn)行時(shí)間表

表2是兩種算法分別對(duì)每幅圖像運(yùn)行20次，記錄兩種算法對(duì)上述5幅圖像的平均分割時(shí)間。從表2可以看出，加速譜聚類算法能夠有效地減少圖像分割所用的時(shí)間，其中，最差的蘑菇圖像，用了原譜聚類運(yùn)行時(shí)間的54 %，而樹木圖像，更是只用了原譜聚類運(yùn)行時(shí)間的36 %。通過計(jì)算，五幅圖像平均花費(fèi)時(shí)間縮短了58 %。

4　結(jié)束語

本文通過引入加速k均值替換原有算法中的k均值算法，對(duì)原譜聚類算法進(jìn)行了改進(jìn)，得出加速譜聚類的圖像分割算法。新算法應(yīng)用于實(shí)驗(yàn)圖像，取得了非常好的效果，在分割效果保持基本不變的情況下，分割所用耗時(shí)縮短 58 %。因此改進(jìn)后的快速譜取類算法具有高效的分割特性。

[1]關(guān)昕,周積林．基于改進(jìn)譜聚類的圖像分割算法[J]．計(jì)算機(jī)工程與應(yīng)用,2014,50(21):184-188．

[2]章毓晉.圖像工程[M].3版.北京:清華大學(xué)出版社,2013:5-6.

[3]陳姿羽,黃靖,李偉鵬.一種改進(jìn)的自適應(yīng)譜聚類圖像分割算法[J].南方醫(yī)科大學(xué)學(xué)報(bào),2012, 32(5):655-658.

[4]高琰,谷士文,唐琎,等.機(jī)器學(xué)習(xí)中譜聚類方法的研究[J].計(jì)算機(jī)科學(xué),2007,34(2):201-203.

[5]賈建華,焦李成.空間一致性約束譜聚類算法用于圖像分割[J].紅外與毫米波學(xué)報(bào),2010,29(1):69-74.

[6]葛芳,王年,郭秀麗.一種改進(jìn)的譜聚類算法及其在基因表達(dá)譜分析中的應(yīng)用[J].安徽大學(xué)學(xué)報(bào),2012,36(5):67-72.

[7]Chang H,Yeung D Y.Robust path-based spectral clustering[J].Pattern Recognition,2008,41(1):191-203.

[8]王玲,薄列峰,焦李成.密度敏感的譜聚類[J].電子學(xué)報(bào),2007,35(8):1577-1581.

[9]趙鳳,范九倫,支曉斌,等.灰度和空間特性的譜聚類圖像分割[J].西安郵電學(xué)院學(xué)報(bào)，2012，17(1):52-57.

[10] Bühler T,Hein M.Spectral clustering based on the graph p-Laplacian[C]∥Proceedings of the 26th Annual International Confe-rence on Machine Learning,New York:ACM,2009:81-88.

[11] 董安國(guó),薛方.基于隨機(jī)譜聚類的圖像分割算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2013,43(23):169-174.

[12] Hamerly G.Makingk-means even faster[C]∥SIAM International Conference on Data Mining,Ohio:SDM,2010:130-140.

[13] Elkan C.Using the triangle inequality to acceleratek-means[C]∥Proceedings of the 20th International Conference on Machine Learning(ICML),WA,2003:147-153.

[14] 索利姆.Python計(jì)算機(jī)視覺編程[M].北京:人民郵電出版社,2014:216-218.

[15] 李學(xué)俊,劉祥俊,趙禮良.基于梯度熵的Otsu圖像分割算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2015,36(3):705-709.

黃艷虎，通訊作者，E—mail:869489894@qq.com。

Improvements of accelerationk-means based spectral clustering algorithm for image segmentation*

LI Chang-xing1, HUANG Yan-hu2, ZHI Xiao-bin1, XIE Xiao-juan1

(1.School of Science,Xi’an University of Posts and Telecommunications,Xi’an 710121,China;2.School of Communication and Information Engineering,Xi’an University of Posts and Telecommunication,Xi’an 710121,China)

A spectral clustering algorithm for image segmentation is achieved by improving spectral clustering algorithm for image segmentation,that is,introduce accelerationk-means algorithm to replace the originalk-means algorithm.The improved algorithm is applied in five experimental images from the Grab Cut dataset of Microsoft Research at Cambridge,results show that time consuming of image segmentation by the improved algorithm can be shortened by 58 % in the premise of average area of conformance assessment without reducing.

image segmentation; spectral clustering; accelerationk-means; acceleration spectral clustering

10.13873/J.1000—9787(2016)09—0137—04

2015—10—27

陜西省自然科學(xué)基金資助項(xiàng)目(2014JM8307)； 陜西省教育廳科學(xué)研究計(jì)劃資助項(xiàng)目(14JK1661)

TP 391

A

1000—9787(2016)09—0137—04

李昌興(1962-),男，陜西戶縣人，教授，從事數(shù)字圖像處理研究。