基于改進仿射傳播聚類的圖像分割算法研究

趙淑娟，王江晴，孫陽光

(中南民族大學 計算機科學學院，湖北 武漢 430074)

基于改進仿射傳播聚類的圖像分割算法研究

趙淑娟，王江晴，孫陽光

(中南民族大學 計算機科學學院，湖北 武漢 430074)

仿射傳播聚類算法是一種比較新的基于質心的聚類算法，在圖像分割領域得到了廣泛應用。仿射傳播聚類算法最終聚類數目會受到偏向參數P(Preference)的影響，得到的聚類數目往往偏多，影響分割質量。鑒于此，提出一種改進的仿射傳播聚類的圖像分割算法，該算法將仿射傳播聚類算法與CURE層次聚類算法相結合，CURE算法能夠對仿射傳播聚類算法的分割結果進行優化。實驗驗證表明，改進后的算法圖像分割效果更好。

圖像分割；仿射傳播聚類；聚類數目；偏向參數；CURE算法

0 引言

在計算機高速發展的時代，人們越來越多地借助計算機獲取與處理自己所需的圖像信息。然而，在對圖像進行研究和處理時，人們不一定對所有的圖像信息感興趣，而有時只對圖像中某些特定的、具有獨特性質的部分感興趣，這就需要將這些區域從圖像中分割出來。圖像分割就是將圖像劃分為幾個不同的區域，在相同的區域內，圖像的特征相近；而在不同的區域，圖像特征差異性較大。圖像特征可以是圖像自身的特征，如像素的灰度、邊緣輪廓和紋理等[1]。圖像分割技術應用領域廣泛，已在生物醫學圖像分析、工業自動化、在線產品檢驗、生產程控、文件圖像處理、遙感圖像、保安監視及軍事等方面得到了廣泛應用。然而由于圖像自身的復雜性，其發展至今仍沒有一個通用的、絕對好的方法，因此對圖像分割方法的進一步研究具有十分重要的意義。聚類算法一經提出就憑借其在圖像分割上的良好效果，在圖像分割領域受到了廣泛關注。聚類分析是根據圖像在某些屬性上的相似性，將圖像劃分為不同類的過程。聚類算法能夠保證一幅圖像上同一類內的對象有較高的相似性，類間對象有較高的差異性，這就有利于人們特定地去分析自己感興趣的內容。根據聚類方法的不同，聚類算法可以分為多種，文獻[2]中將聚類算法大致分為層次算法、劃分算法、基于密度和網格的方法以及其它聚類算法。K-means聚類算法作為一種比較經典的圖像分割算法，在圖像分割中得到了很好的應用。然而，K-means聚類算法必須預先給定聚類數目，對初始聚類中心的選擇比較敏感，如果給定的數值不合適則容易陷入局部最優狀態。

仿射傳播聚類算法(Affinity Propagation Clustering, AP)是2007年由Frey等[3-4]在《Science》上提出的同屬于K-means算法的一種新的聚類算法，AP算法克服了K-means算法的缺點，不需要預先指定聚類中心，初始時將全部的數據點都作為候選聚類中心點，通過數據點之間的消息傳遞過程不停地循環迭代，最終獲得高質量的聚類中心[5]，避免了局部最優的狀態，同時 AP算法對數據點之間生成的相似度矩陣的對稱性沒有要求，多次獨立運行的結果都非常穩定。目前也有一些學者對AP算法進行了改進[6-9]，有的是與其它算法結合來縮短運行時間，有的是對自身結構作了改進，然而并沒有從根本上解決問題。AP聚類算法雖然運行結果比較穩定，但是在處理結構較松散的數據時產生的類數往往會偏多[10]，在處理具有復雜結構的數據集時，不能夠產生合理的聚類效果，因此會影響圖像分割質量。同時AP算法最終的聚類數目在很大程度上會受到偏向參數ρ的影響，這就使得AP算法對ρ值的選擇較為敏感[11-12]。CURE算法是一種凝聚型層次聚類算法，它是基于質心和代表點的策略，能夠有效地處理非球形數據，且該算法能夠很好地控制孤立點對聚類結果的影響[13-14]。因此，本文將AP聚類算法和CURE算法相結合，利用CURE算法的優點對AP聚類算法的結果進行優化，從而提高聚類質量。

1 相關算法

1.1 傳統AP聚類算法

AP聚類算法不需要事先指定聚類數目，而是在初始時把全部的數據點都作為候選聚類中心，通過計算數據點間的相似度矩陣S，確定偏向參數p(preference)，經過循環迭代過程，判斷決策矩陣E從而找到聚類中心。

設任意兩個數據點xi和xk，它們之間的相似度s(i,k)是通過計算它們的負的歐氏距離來得到，最終得到的相似度矩陣S是一個N×N的矩陣，s(i.k)的計算公式如下：

(1)

式(1)中，當i=k時，s(i,k)本應該是零，但為了確保每個點成為聚類中心的可能性相同，這里全部設置為偏向參數ρ的值。

AP算法在消息傳遞過程中涉及兩個重要參數：吸引度矩陣R和歸屬度矩陣A。吸引度矩陣R：吸引度r(i，k)是由點xi發送到候選聚類中心點xk的消息，表示點x可以成為點xi的類中心點的程度。歸屬度矩陣A：歸屬度a(i,k)是由候選聚類中心點xk發送到點xi的消息，表示點xi是否選擇點xk作為其類中心點的程度。

r(i，k)與a(i,k)的大小直接決定著xk能否成為聚類中心，值越大，xk成為聚類中心的可能性越大。它們之間的消息傳遞過程如圖1所示。

圖1 消息傳遞過程

根據文獻[3]用相似度矩陣S來計算吸引度矩陣R和歸屬度矩陣A：

(2)

(3)

(4)

(5)

AP算法還引入了兩個重要的信息參數：阻尼振蕩因子lam和偏向參數p(preference)。在每一次的更新迭代過程中，R和A的值利用lam來進行迭代更新，更新過程如下：

(6)

(7)

其中，當迭代過程中獲得的聚類個數不停地發生震蕩而無法收斂時，適當增大lam的值可消除震蕩，使算法更快收斂。通常情況下，lam設置在0.85左右可以直接避免震蕩。對于偏向參數p，在很大程度上影響最終的聚類數目，通常會把p值設置成相似度矩陣的中值，但即使設置成相似度矩陣的中值也并非就能夠獲得最好的聚類效果，因此很難直接知道p取何值時能夠獲得最好的聚類效果。

AP算法不停地更新吸引度矩陣R和歸屬度矩陣A的值，當超過預先設置的最大迭代次數maxits或聚類中心連續convits次穩定不變時，算法將停止迭代。通過終止時r(i,k)+a(i,k)的值來確定最終的聚類結果。數據點k確定為i的類中心點，k的值為：

k=argkmax(r(i,k)+a(i,k))

(8)

對式(2)兩邊同時加上a(i,k)得：

(9)

1.2 AP算法步驟

對于由N個數據點組成的數據集T，AP算法的運算步驟可以用圖2所示的流程圖來表示。

AP聚類算法雖然多次獨立運行的結果比較穩定，但其仍然存在兩個缺點：①AP算法對偏向參數P的選擇較敏感，P值偏小獲得的聚類個數偏少，P值越大獲得的聚類個數越多。如果逐個去試就會增加算法的復雜度，因此P值的選擇不容忽視；②AP算法在處理較松散的數據時容易產生較多的聚類數，影響聚類效果，即在消息傳遞過程中有可能多個數據點成為聚類中心的優先級相同，從而導致聚類數目偏多，影響圖像分割質量。

1.3 CURE算法

CURE算法是針對大多數數據集而提出的一種基于質心的聚結型層次聚類算法。CURE算法最開始是將每個數據點都看成一個類(即每個類中只有這個數據點本身)，然后計算各個數據點間的相似性，將最相似的兩個數據點進行合并。CURE聚類算法可以適用任意形狀的簇，通過收縮因子來控制孤立點的影響。因此在遇到較松散的數據集時CURE算法能夠更好地處理孤立點，而且能夠識別非球形和大小并改變較大的類。

設任意一個數據集W，CURE算法最初聚類時每個數據點都是一類，通過計算兩兩之間的距離，然后融合距離最近的兩個類，直到達到預先設定的聚類個數。對于任意一個類u，u.mean和u.rep分別表示類u的聚類中心點和屬于類u的數據點，類與類之間的距離是采用歐式距離，兩個聚類u、v之間的距離計算公式定義為：

圖2 AP算法運算步驟流程

dist(u,v)=min(dist(u.rep,v.rep))

(10)

當確定距離最小的兩個類后，將這兩個類融合，融合后形成新的聚類中心點，計算公式為：

(11)

其中|u|為類u的數據點個數。

2 改進的AP聚類算法

針對AP聚類算法存在的一些缺點，以及CURE算法能夠處理任意形狀數據集的優點，本文是將兩種聚類算法進行結合形成一種新的算法，即C-AP算法，以克服AP算法的不足，經驗證C-AP算法的圖像分割效果明顯優于AP算法的聚類結果。

2.1 算法原理

C-AP算法進行聚類分為3個過程：首先運用AP算法對數據集進行預分割，會獲得n個聚類中心；其次對于獲得的這n個聚類中心進行去異常值處理，獲得n個質量較好的聚類中心；最后階段是將這個質量較好的聚類中心作為CURE算法的輸入數據，經過CURE算法聚類后將獲得最終的聚類中心，也是質量最高的聚類中心Cbest，再將其余的數據點分配到所屬的類。C-AP算法為了得到更好的聚類效果，偏向參數p的值不能設置得太小，這樣才能保證在進行CURE聚類的階段輸入數據點個數不會太少。若值設置得太大，一些噪聲點就會被分割出來，這就必須進行去噪聲處理。C-AP算法引入了去噪聲率α，若centeri為中心的簇中樣本點個數ni<α

由于CURE算法需要初始設定聚類數目，為了能夠得到最好的聚類個數，本文加入了聚類有效性指標Silhouette指標，能夠通過Silhouette指標值來判斷出最優的聚類個 數[15]。設一個有N個樣本的數據集被劃分為k個類Ci(i=1,2,l,k)，其中，ni表示Ci類中的樣本點個數。t為類別Ci中的樣本點，則設a(t)表示為Ci中t與其類內其它樣本的平均距離(此處為歐氏距離)，d(t,Ci)表示t到另一類別中所有樣本平均聚類，得到bt=min{d(t,Ci},j=1,23,…,k,且j≠i，得到樣本t的Silhouette指標為：

(12)

一個聚類中所有樣本點的平均值能夠反映該類的緊密性和可分性，那么整個數據集內所有樣本的Sil平均值就可以反映整個聚類結果的質量，平均Silhouette指標越大表明聚類質量越好，其最大值對應的類數即為最優聚類個數。本文是通過比較不同的分割類數得到不同的Silhouette指標值，選擇Silhouette指標值較大的類數輸出。

2.2 C-AP算法進行圖像分割步驟

Step1：輸入待分割圖像，提取圖像的灰度值作為數據點輸入。

Step2：初始化聚類算法參數：計算數據點間的相似度矩陣S，偏向參數P，去噪聲率α。

Step3：應用AP算法對圖像進行預分割，會得到M個聚類中心點{center1，center2，…，centerm}。

Step4：對m個聚類中心進行去噪聲點處理。即基于該聚類中心的簇中樣本個數是否小于α×N，若小于a×N的值，則將該聚類中心刪除；反之將該聚類中心進行下一步聚類，這樣就得到n個質量較好的聚類中心{goodcenter1，goodcenter2，…，goodcentern}。

Step5：對獲得的這n個聚類中心進行CURE算法聚類，通過比較不同類數對應不同的Silhouette指標值選出最好的聚類個數，對剩余的數據點進行類標簽分配。

Step6：根據聚類結果輸出分割后的圖像。

3 實驗結果及分析

本文的實驗運行環境是在MATLAB 7.10.0(R2010a)版本上運行。圖像均來源于Berkeley的標準灰度圖像分割數據庫BSDS300中的圖像。本文是對AP算法和C-AP算法的聚類性能進行比較，實驗中AP算法初始時偏向參數P設置為相似度矩陣的中值，算法最大迭代次數設置為1 000，迭代過程聚類結果連續不發生改變的次數設置為100，阻尼系數lam設置為0.9，去噪聲率α取值為0.02。本文選取了其中的3幅圖像進行分割，分割效果如圖3所示。

圖3 AP算法和C-AP算法分割結果

從圖2可以看出，本文的C-AP算法分割效果要優于傳統的AP算法分割效果。其中傳統AP算法將第一幅圖像分割成了6類，本文算法是分割成了3類，傳統AP算法分割數目多于本文算法，天空背景區域出現了錯分割現象，本文算法分割后的圖像更加干凈，相對準確。第二幅圖像，傳統AP算法對草地分割得比較粗糙，本文C-AP算法則比較細膩，將背景和山羊明顯的區分開來。第三幅圖像中，本文C-AP算法對背景光暈處的分割效果明顯優于傳統AP算法的分割效果。直觀上看，實驗結果驗證了本文改進后的算法在分割效果上更加精確，但有時通過肉眼觀察會存在主觀性，缺乏定量分析，因此本文引入了區域間對比度來客觀評價算法的性能。圖像分割就是將圖像分割成若干類，類與類之間的差異越大表明分割效果越好，因此選擇區域間對比度能很好地反應分割的好壞。區域間對比度(GC)用于衡量分割后圖像各區域之間的差異度，GC值越大表明分割效果越好[16]。設一幅圖像被分割成fi和fj個區域，i和j分別表示圖像中的任意兩個區域，fi和fj分別表示第i個區域和第j個區域的平均灰度，則GC可表示為：

(13)

傳統AP算法和本文算法的區間對比度如表1所示。

表1 兩種算法GC值對比

從表1中的數據可以看出，改進后的仿射傳播聚類算法(C-AP算法)與傳統的AP聚類算法相比，3幅圖像的區域間對比度都得到了提高，說明改進后的算法分割效果更好。

4 結語

本文針對傳統的仿射傳播聚類算法在圖像分割上存在的不足，對傳統的仿射傳播聚類算法作了改進，通過與CURE層次聚類算法結合使得算法克服了對偏向參數選擇的敏感性，對于一些孤立點的處理更加健壯，經驗證改進后的算法在圖像分割效果和性能上都得到了一定的提高。由于本文算法是在傳統放射傳播聚類算法分割之后再利用CURE算法作進一步分割，在運行時間上會略長，因此如何進一步縮短運行時間是下一步研究的重點。

[1] 章毓晉.圖像分割[M].北京：科學出版社,2001.

[2] 孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學報,2008,19(1):48-61.

[3] FREY B J,DUECK D.Clustering by passing messages between data points[J].Science,2007,315(5814):972-976.

[4] MéZARD M.Where are the exemplars[J].Science,2007,315(5814):949-951.

[5] SHANG FAN-HUA,JIAO L C,SHI JIA-RONG,et al.Fast affinity propagation clustering:a multil- evel approach[J].Pattern Recognition,2012,45(1).

[6] 肖宇,于劍.基于近鄰傳播算法的半監督聚類[J].軟件學報,2008,19(11):2803-2813.

[7] 許曉麗,盧志茂,張格森,等.改進近鄰傳播聚類的彩色圖像分割[J].計算機輔助設計與圖形學學報,2012,24(4):514-519.

[8] 董俊,王鎖萍,熊范綸.可變相似性度量的近鄰傳播聚類[J].電子與信息學報,2010,32(3):509-514.

[9] 劉曉楠,尹美娟,李明濤,等.面向大規模數據的分層近鄰傳播聚類算法[J].計算機科學,2014,41(3):185-188.

[10] 王開軍,李健,張軍英,等.半監督的仿射傳播聚類[J].計算機工程,2007,33(23):197-199.

[11] KAREN K.Affinity program slashes computing times [EB/OL].http://www.news. utoronto. ca/bin6/ 070215-2952.Asp,2007-10-25.

[12] BODENHOFER U,KOTHMEIER A,HOCHREITER S.APcluster:an R package for affinity propagation clustering[J].Bioinformatics,2011,27(17):2463-2464.

[13] GUHA S,RASTOGI R,SHIM K.CURE:an efficient clustering algorithm for large databases[J].ACM SIGMOD Record,ACM,1998,27(2):73-84.

[14] 沈潔,趙雷,楊季文,等.一種基于劃分的層次聚類算法[J].計算機工程與應用,2007,43(31):175-177.

[15] DUDOIT S,FRIDLYAND J.A prediction-based resampling method for estimating the number of clusters in a dataset[EB/OL].http://www.edlab.cs.umass.edu/cs69 1k/conlon/readings/Dudoit Fridlyand2002GB.pdf,2002.

[16] LEVINC M D,NAZIF A M.Dynamic measurement of computer generated image segmentations[J].IEEE Trans.PAMI-7,1985,7(2):155-164.

(責任編輯：孫 娟)

國家自然科學基金項目(60975021)；中南民族大學中央高校基本科研業務費專項資金項目(CZZ15003)

趙淑娟(1990-)，女，山東菏澤人，中南民族大學計算機科學學院碩士研究生，研究方向為圖像處理、人工智能；王江晴(1964-)，女，湖北武漢人，博士，中南民族大學計算機科學學院教授，研究方向為人工智能、數字圖像處理；孫陽光(1978-)，男，湖北武漢人，博士，中南民族大學計算機科學學院副教授，研究方向為數字圖像處理。

10.11907/rjdk.162273

TP312

A

1672-7800(2017)003-0018-04