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

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

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

?

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

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

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

對譜聚類圖像分割算法進行改進，即引入加速 均值算法替換原算法中的k均值算法，得出加速譜聚類的圖像分割算法。將改進算法應用于微軟劍橋研究院Grab cut數據集中的5幅實驗圖像，結果顯示：在平均區域一致性評價不降低的前提下，改進算法完成分割所花費的平均時間比改進前可縮短58 %。

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

0　引　言

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

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

1　譜聚類算法與 均值算法

1.1譜聚類算法

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

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

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

4)計算矩陣L的前k個特征值所對應的特征向量v1,v2,…,vk。

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

6)對于i=1,2,…,n,令yi∈Rk是對應于V的第i行所構成向量。

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

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

1.2k均值算法

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

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

2)重新計算每個聚類的均值作為新的聚類中心。

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

2　加速譜聚類算法

2.1加速k均值算法

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

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

則

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

又設c′為某個簇的中心，該簇中包含數據點x，c″為前一次迭代過程中的中心點。如果

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均值法可以描述如下：

初始化：選擇初始中心。對于每個數據點x和中心c，設定下限

l(x,c)=0

分配每個x到其最近的初始中心

c(x)=argmincd(x,c)

每當d(x,c)被計算時，令

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

上限

u(x)=mincd(x,c)

下面，重復直到算法收斂。

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

3)對于所有剩余的點x和中心c必滿足

c≠c(x)

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

三個條件。

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

r(x)=false;

否則

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

2)如果

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

或者

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

d(x,c)

令

c(x)=c

4)對于每個中心c，讓m(c)為被分配到c點的平均值。

5)對于每個點的x和中心c，分配

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

6)對于每個點x，分配

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

r(x)=true。

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

2.2加速譜聚類算法

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

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

2)計算L的前k個特征值所對應的特征向量v1,v2,…,vk，并將它們按列組成矩陣V。

3)對V的n個行向量執行加速k均值，聚類成簇C1,C2,…,Ck。

3　實驗結果

計算機配置為酷睿2代處理器，2.2 GHz主頻，4 GB內存以及320 GB硬盤。算法實現基于Win7操作系統，仿真軟件由Matlab2010b。

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

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

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

圖3　對樹圖像用不同算法分割的效果

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

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

可以看出，加速譜聚類算法對圖像的分割效果與原譜聚類相當。客觀地，用區域一致性[15]對兩種算法進行評價如表1，數據顯示，5幅圖像的區域一致性平均提高了0.004 %，新算法完全可以勝任圖像分割的要求。

表1　算法的區域一致性評價

表2給出了兩種算法的運行時間。

表2　算法運行時間表

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

4　結束語

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

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

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

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

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

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

[6]葛芳,王年,郭秀麗.一種改進的譜聚類算法及其在基因表達譜分析中的應用[J].安徽大學學報,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].電子學報,2007,35(8):1577-1581.

[9]趙鳳,范九倫,支曉斌,等.灰度和空間特性的譜聚類圖像分割[J].西安郵電學院學報，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] 董安國,薛方.基于隨機譜聚類的圖像分割算法[J].數學的實踐與認識,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計算機視覺編程[M].北京:人民郵電出版社,2014:216-218.

[15] 李學俊,劉祥俊,趙禮良.基于梯度熵的Otsu圖像分割算法[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

陜西省自然科學基金資助項目(2014JM8307)； 陜西省教育廳科學研究計劃資助項目(14JK1661)

TP 391

A

1000—9787(2016)09—0137—04

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