基于近鄰傳播和區(qū)域融合的彩色圖像分割算法

王 磊

（商洛學(xué)院 現(xiàn)代教育技術(shù)中心，陜西商洛 726000）

2007年Frey&Dueck在Science提出了一種新的聚類算法：近鄰傳播聚類（Affinity Propagation，簡稱AP），其主要優(yōu)勢體現(xiàn)在無須事先確定聚類數(shù)（與k-means不同），而是根據(jù)數(shù)據(jù)自身的特性自動聚類到合適的數(shù)目。AP算法已經(jīng)被實驗證明效果要優(yōu)于K均值算法[1]。例如，對數(shù)千個手寫的郵政編碼的圖片，AP算法只花很短的時間就可以聚類到少量代表各種筆跡類型的手寫圖片，而K-means算法要達到同樣精度要耗費500萬年[2]。該算法已在醫(yī)學(xué)圖像處理[3]、路線搜索和選址[4]、基因外顯子發(fā)現(xiàn)、圖像搜索[5]等方面得到了應(yīng)用。但是傳統(tǒng)AP算法在實際應(yīng)用中仍然存在一些問題，如：該算法的空間復(fù)雜度和時間復(fù)雜度嚴(yán)重受制于樣本個數(shù)，因此導(dǎo)致傳統(tǒng)AP算法無法處理大規(guī)模數(shù)據(jù)，特別是大規(guī)模圖像分割問題[6]。由此，本文提出了一種基于近鄰傳播聚類的彩色圖像分割算法。包括三部分：圖像預(yù)處理過程，將RGB顏色空間彩色圖像變換到CIE L*u*v*顏色空間彩色圖像，目的是采用更符合人類視覺感受顏色空間，并進一步解除R、G、B三分量的相關(guān)性；基于給定數(shù)目的近鄰傳播聚類（APGNC）的圖像分割，目的是獲得整幅圖像的分割結(jié)果；圖像后處理過程，利用區(qū)域合并方法修正圖像的分割結(jié)果，目的是保證最終分割目標(biāo)的整體性，去除目標(biāo)區(qū)域內(nèi)的錯分或者誤分的部分。

1 彩色圖像預(yù)處理過程

目前表達彩色的顏色空間已經(jīng)有很多種不同的形式（即：顏色空間）：RGB、HSL、HSV、CIE L*u*v*以及CIE L*a*b*?，F(xiàn)在應(yīng)用最為廣泛的顏色空間是RGB，這種顏色空間雖然簡單不需要轉(zhuǎn)換，但R、G、B三分量之間有很高的相關(guān)性，這對于圖像分割是不利的。CIE L*u*v*顏色空間是根據(jù)人眼視覺系統(tǒng)構(gòu)造的，L*分量表示亮度，u*v*共同表示某種顏色，它可以表示所有人眼可以看見的顏色，同時也包括一些物理世界不能再現(xiàn)的顏色。另外，它對應(yīng)的飽和度線和色調(diào)線近似于線性變換，可以很好地改善了視覺非正規(guī)的問題。因此，在圖像分割前需要將以RGB形式描述的彩色圖像轉(zhuǎn)換為CIE L*u*v*顏色系統(tǒng)中的彩色圖像，進而進行分析和處理。轉(zhuǎn)換過程如公式(1)-(3)所示。

RGB顏色空間先轉(zhuǎn)換到XYZ顏色空間

CIE L*u*v*的計算公式[7]

其中

Y0為XYZ空間中白色對應(yīng)的顏色分量，Y0、u0、v0為 CIE L*u*v*中白色對應(yīng)的三個顏色分量[8]。

2 基于A P的圖像分割

在利用AP算法進行圖像分割時，想要降低算法的時間復(fù)雜度和空間復(fù)雜度通常有兩種方法：一種是采用稀疏相似性傳播聚類[9]；另一種是將圖像劃分成互不重疊的子圖，并將子圖作為數(shù)據(jù)點進行聚類[10]。這兩種方法雖然都能夠一定程度上降低算法的空間和時間復(fù)雜度，但是算法本身復(fù)雜度較高、不易實現(xiàn)[6]，且不能從根本上加快聚類的速度。

現(xiàn)有實驗已經(jīng)證明在普通PC下（matlab環(huán)境），AP算法中樣本個數(shù)一般被限制在3000以內(nèi)[11]，顯然這在實際應(yīng)用中有很大弊端；而本文通過選取適當(dāng)?shù)牟蓸勇?，可以大大擴展AP算法在圖像分割中的應(yīng)用。

本文對經(jīng)過預(yù)處理的彩色圖像，進行初始近鄰傳播聚類。包括三個步驟：首先，對彩色圖像進行數(shù)據(jù)采樣（包括自動均勻采樣和手工標(biāo)定采樣）；然后，對采樣數(shù)據(jù)進行給定聚類數(shù)目的近鄰傳播聚類（APGNC），獲得相應(yīng)的聚類中心；最后，根據(jù)最大相似度規(guī)則，計算其余未采樣數(shù)據(jù)點的類標(biāo)簽。

2.1 對彩色圖像進行數(shù)據(jù)采樣

2.1.1 自動均勻采樣

利用均勻采樣方法對整幅圖像進行數(shù)據(jù)采樣，設(shè)置采樣率rate，其范圍為[0,1]，具體做法是每間隔1/rate個點采樣一次。顯然，采樣率越高，采樣數(shù)據(jù)就越少，圖像分割的時間就越短，聚類效果也就越差；反之亦然。因此，綜合考慮算法的效果和效率，通過改變采樣率rate，把采樣數(shù)據(jù)控制在300-2000為宜，以保證聚類過程的高效。

2.1.2 手工標(biāo)定采樣

由于在自動均勻采樣中當(dāng)rate較小時，采樣數(shù)據(jù)之間的間隔（即1/rate）就很大，這樣對于一些小目標(biāo)就存在采樣不充分或者直接跳過的情況，因此本文設(shè)定當(dāng)rate小于某個值（默認(rèn)為1%）時，應(yīng)當(dāng)結(jié)合人工標(biāo)定，添加一些感興趣的區(qū)域或小目標(biāo)點。

2.2 給定聚類數(shù)目的APGNC算法

傳統(tǒng)AP算法不能像K-means那樣在聚類前預(yù)知最終聚類數(shù)目，即AP算法不能得到指定聚類數(shù)目的結(jié)果。但是從文獻[12]的思想出發(fā)，可以通過基于二分法的判斷，實現(xiàn)上述目標(biāo)。

算法： APGNC（Affinity Propagation with Given Number of Cluster）

步驟：

1)初始化AP：人工指定最終聚類數(shù)目為DK，偏向參數(shù)P為median（S），上界P_high=0,下界P_low=2*P。

2)運行一次經(jīng)典AP算法：得到聚類數(shù)K。

3)進行判斷：若K＜DK，說明聚類數(shù)目少，應(yīng)增大P值：P_low=P，得到新的偏向參數(shù)P=1/2*(P_low+P_high)，轉(zhuǎn)入 2）；若 K＞DK，說明聚類數(shù)目多，應(yīng)減小P值：P_high=P和P_low=2*P_low，得到新的偏向參數(shù)P=1/2*(P_low+P_high)，轉(zhuǎn)入2）；若K=DK，說明達到給定的聚類數(shù)目，轉(zhuǎn)入 4）。

4)輸出聚類結(jié)果，算法結(jié)束。

2.3 判斷未采樣數(shù)據(jù)的類標(biāo)簽

采樣數(shù)據(jù)經(jīng)過APGNC聚類后獲得了相應(yīng)的類歸屬，而其余的未采樣數(shù)據(jù)仍然沒有類歸屬。因此，要將采樣數(shù)據(jù)聚類的結(jié)果擴展到其他未采樣數(shù)據(jù)，具體做法如下：

計算未采樣數(shù)據(jù)與各聚類中心點之間的相似度，然后按照最大相似度原則，為它們賦予相應(yīng)的類標(biāo)簽Cx：

其中，Ci表示經(jīng)APGNC聚類得到的第i個聚類中心，i=1,2，…，DK。

3 圖像分割的后處理

由于只在彩色圖像的顏色特征上聚類，沒有考慮像素點的空間信息，因此彩色圖像經(jīng)過AP算法初始分割后，較容易產(chǎn)生了面積較小的獨立區(qū)域或孤立點。區(qū)域合并就是將兩個在空間上相鄰，且在顏色上最相近的區(qū)域合并為一個區(qū)域，用以消除圖像分割中瑣碎的區(qū)域和噪聲點的干擾，讓分割圖像更趨于整體，使分割結(jié)果更符合人類的視覺效果。

本文主要利用區(qū)域鄰接圖（RAG），并采用區(qū)域的面積和顏色特征來進行區(qū)域合并的[13]。這樣做主要有兩個目的：首先通過區(qū)域面積準(zhǔn)則，篩選小而孤立的區(qū)域或孤立點，作為區(qū)域合并的對象區(qū)域；接著計算對象區(qū)域和與它相鄰近的各區(qū)域之間的顏色距離，顏色最接近的區(qū)域作為將要進行合并的目標(biāo)區(qū)域。最后，通過修改對象區(qū)域中數(shù)據(jù)的類標(biāo)簽，完成區(qū)域合并。

區(qū)域合并的具體算法步驟：

1)初始化。n 為初始分割區(qū)域數(shù)，R={r1，r2，…，rn}，且R'=φ。R為合并前的區(qū)域集合，R'為合并后的區(qū)域集合。rm是第m個區(qū)域,m=1,2,…,n。

2)如果ri的面積小于T，那么ri就是對象區(qū)域，R=R-ri,i=1,2,…,n.

3)rj=argmin(Dis(ri，rj)|1≤j≤n，rj∈R)，那么 rj就是對象區(qū)域。其中：

|ri|，|rj|分別代表第i和第j區(qū)域中包含的像素個數(shù)（面積）代表兩個區(qū)域的顏色均值，在本文即為L,u,v三分量的區(qū)域均值表示三維歐氏距離[14]；

4)將ri的類標(biāo)簽修改為rj的類標(biāo)簽,and r'=ri∪rj，R=R-rj，R'=R'+r'；

5)重復(fù)2)-4)，直到R為空。

4 實驗結(jié)果及分析

4.1 實驗數(shù)據(jù)

從Berkeley圖像庫中選取三副實驗圖像（圖1）。對于每幅實驗圖像，APGNC算法中相似度取負(fù)的歐氏距離，偏向參數(shù)P初始為median（S），指定的目標(biāo)聚類數(shù)目DK設(shè)置為表1中圖片相應(yīng)的分割數(shù)目，阻尼系數(shù)設(shè)置為0.7，自動采樣率rate設(shè)置為2‰，區(qū)域合并的面積閾值T取200。（硬件環(huán)境：CPU：Intel Core(TM)2，1.86GHz With 1G memory），實驗軟件：MATLAB 7.8.0(R2009a)。

圖1 實驗用圖（鳥、飛機、教堂）

4.2 實驗結(jié)果

為了驗證本文所提方法的高效性和準(zhǔn)確性，特意選擇了基于K-means的RGB彩色圖像分割算法作對比驗證實驗，其聚類數(shù)目設(shè)置見表1。

表1 圖像信息

在圖2中，基于K均值的彩色圖像分割中存在大量孤立點和小區(qū)域，嚴(yán)重影響了分割結(jié)果的精度。很顯然，與K均值的分割結(jié)果相比，本文方法減少了分割結(jié)果中的孤立小區(qū)域，提高了分割的精度，使結(jié)果更加趨于整體一致性，更加符合人類整體視覺感觀的特點；另外，可以通過調(diào)整自動采樣率rate的值，使該算法用于更大尺寸圖像的分割處理，這是傳統(tǒng)AP算法所不具備的。

在圖3中，對比本文方法、k-means與人工分割結(jié)果，不難發(fā)現(xiàn)本文方法的分割結(jié)果是比較符合理想的人工分割結(jié)果，這是與事實相一致的；特別是由于采用了區(qū)域合并策略，對AP初始分割進行了一定的修正，消除了背景區(qū)域中的孤立區(qū)域的影響，使最終的分割結(jié)果更傾向于整體一致。

表2對本文方法與K-means方法在運行時間（s）上進行了對比，結(jié)果表明,本文方法擁有較快的執(zhí)行時間，并能夠達到較滿意的分割效果。

圖2 聚類結(jié)果

表2 對比試驗

5 結(jié)論

本文針對近鄰傳播聚類在圖像分割方面存在的問題，提出了利用數(shù)據(jù)采樣和區(qū)域合并的基于近鄰傳播聚類的彩色圖像分割方法。經(jīng)仿真試驗證明，本文所提的圖像分割方法進一步改善了圖像分割質(zhì)量，具有較滿意的分割結(jié)果和較快的處理速度，更符合人類的整體視覺感觀。但該方法仍然存在不足之處，即只利用了圖像中的顏色信息，而忽視了紋理等有用的空間信息。因此，如何將這些豐富的空間信息整合應(yīng)用到該圖像分割算法中還需要進一步探討。

圖3 分割結(jié)果

[1]FreyBJ,DueckD.Clustering bypassingmessages between data points[J].Sincence,2007,315(5814):972-976.

[2]Kelly K.Affinity propagation slashes computing times[OL/DB].available:http://www.news.utoronto.ca/bin6/070215-2952.asp,October 25,2007.

[3]Li G,Guo L,Liu T M.Grouping of brain MR images via affinity propagation[C].IEEE International Symposium on Circuits and Systems,Taipei,Taiwan,2009:2425-2428.

[4]唐東明,朱清新,楊 凡，等.基于仿射傳播聚類的大規(guī)模選址布局問題求解[J].計算機應(yīng)用研究,2010,27(3):841-844.

[5]萬 潔.基于affinity propagation聚類方法的圖像檢索技術(shù)在數(shù)字圖書館中的應(yīng)用[J].計算機與現(xiàn)代化,2008(8):116-119.

[6]張仁彥,趙洪亮.基于相似性傳播聚類的灰度圖像分割[J].海軍工程大學(xué)學(xué)報,2009,21(3):33-37.

[7]Cheng H D,Jiang X H,Sun Y,et al.Color image segmentation: advanees and prospects. Pattern Recognition[J].December,2001,34(l2):225-2281.

[8]SHARMA C,TRUSSELL H.Digital color image[J].IEEE Transaction on Image Processing,1997,6(7):901-932.

[9]Xiao J X,Wang J D,Tan P,et al.Joint affinity propagation for multiple view segmentation[C].Proceedings of 2007 IEEE 11th internationa conference on computer vision. piscataway,NJ0885521331,United States:Institute of Electrical and Electronics Engineers Inc,2007:1-7.

[10]FREY B J,DUECK D.Mixture modeling by affinity propagation [J].Neural Information Processing Systems,2006,18:379-386.

[11]谷瑞軍,汪加才.面向大規(guī)模數(shù)據(jù)集的近鄰傳播聚類[J].計算機工程,2010,36(23):22-24.

[12]王 磊,汪西莉.一種結(jié)合半監(jiān)督的改進自適應(yīng)親和傳播聚類[J].計算機應(yīng)用研究，2010:27(12):4436-4442.

[13]CHENG H D,JIANG X H,WANG J.Color image segmentation based on homogram thresholding and region merging[J].Pattern Recognition,2002,35(2):373-393.

[14]ERLANDSSON F,LINNMAN C,EKHOLM S,et al.A detailed analysis of cyclin a accumulation at the G1/S border in normaland transformed cells[J].Experimental Cell Research,2000,259:86-95.