王 磊

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

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

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

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

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

CIE L*u*v*的計(jì)算公式[7]

其中

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

2 基于A P的圖像分割

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

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

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

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

2.1.1 自動(dòng)均勻采樣

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

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

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

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

傳統(tǒng)AP算法不能像K-means那樣在聚類前預(yù)知最終聚類數(shù)目，即AP算法不能得到指定聚類數(shù)目的結(jié)果。但是從文獻(xiàn)[12]的思想出發(fā)，可以通過(guò)基于二分法的判斷，實(shí)現(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)運(yùn)行一次經(jīng)典AP算法：得到聚類數(shù)K。

3)進(jìn)行判斷：若K＜DK，說(shuō)明聚類數(shù)目少，應(yīng)增大P值：P_low=P，得到新的偏向參數(shù)P=1/2*(P_low+P_high)，轉(zhuǎn)入 2）；若 K＞DK，說(shuō)明聚類數(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，說(shuō)明達(dá)到給定的聚類數(shù)目，轉(zhuǎn)入 4）。

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

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

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

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

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

3 圖像分割的后處理

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

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

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

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

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

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

|ri|，|rj|分別代表第i和第j區(qū)域中包含的像素個(gè)數(shù)（面積）代表兩個(gè)區(qū)域的顏色均值，在本文即為L(zhǎng),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 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

圖1 實(shí)驗(yàn)用圖（鳥(niǎo)、飛機(jī)、教堂）

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

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

表1 圖像信息

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

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

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

圖2 聚類結(jié)果

表2 對(duì)比試驗(yàn)

5 結(jié)論

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

圖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ī)模選址布局問(wèn)題求解[J].計(jì)算機(jī)應(yīng)用研究,2010,27(3):841-844.

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

[6]張仁彥,趙洪亮.基于相似性傳播聚類的灰度圖像分割[J].海軍工程大學(xué)學(xué)報(bào),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].計(jì)算機(jī)工程,2010,36(23):22-24.

[12]王 磊,汪西莉.一種結(jié)合半監(jiān)督的改進(jìn)自適應(yīng)親和傳播聚類[J].計(jì)算機(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.