一種基于密度峰值聚類的圖像分割算法

趙 軍,朱 荽,楊雯璟,許彥輝,龐 宇

(重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400065)

0 概述

圖像分割是計(jì)算機(jī)視覺和圖像處理中的基礎(chǔ)部分,其目的在于按照顏色、灰度、紋理等將圖像劃分成多個(gè)不相交的區(qū)塊,從中提取研究者感興趣的區(qū)域[1]。在計(jì)算機(jī)視覺領(lǐng)域,對(duì)于灰度圖像的研究比對(duì)彩色圖像的研究更為成熟。但隨著人工智能的發(fā)展,對(duì)彩色圖像研究方法的需求量在不斷增加,針對(duì)彩色圖像的研究得到了研究者高度重視。

研究者提出許多彩色圖像的分割方法,這些方法可分為基于閾值的分割[2-4]、基于聚類的分割[5]、基于邊緣或輪廓檢測(cè)的分割[6-7]和基于區(qū)域提取的分割[8]四大類。相較于其他方法,由于聚類是一種無監(jiān)督的分類算法,不必事先知道分類準(zhǔn)則,因此研究者將各類聚類方法應(yīng)用于圖像分割領(lǐng)域,形成諸多基于聚類的圖像分割方法,如模糊C均值(Fuzzy C-Means,FCM)聚類[9-11]、K-means聚類[12-13]、譜聚類[14]、Mean-Shift聚類[15-16]、簡(jiǎn)單線性迭代聚類(Simple Linear Iterative Clustering,SLIC)[17-18]等。其中,有些方法如K-means和FCM在給定聚類數(shù)的前提下,能夠生成一種分割算法,但算法分割的性能對(duì)聚類中心和聚類數(shù)敏感,并且多數(shù)算法需要人工確定參數(shù)。而密度峰值聚類(Density Peak Clustering,DPC)適用于處理任何形狀的數(shù)據(jù)集,無需提前設(shè)置簇的數(shù)量,所需參數(shù)少,算法原理簡(jiǎn)單容易理解,其復(fù)雜度也比一般的聚類算法如FCM和K-means低,但是DPC的可靠性依賴于截?cái)嗑嚯x的取值和人工確定的聚類中心。

本文提出一種基于DPC的圖像分割算法。針對(duì)傳統(tǒng)DPC中的參數(shù)截?cái)嗑嚯x靠經(jīng)驗(yàn)取值的情況,引入信息論中信息熵的概念,求得其自適應(yīng)的截?cái)嗑嚯x,得到改進(jìn)后的密度峰值聚類(EDPC),并在EDPC的基礎(chǔ)上對(duì)彩色圖像進(jìn)行分割。該算法將彩色圖像的每個(gè)像素點(diǎn)的顏色特征空間作為聚類算法的輸入數(shù)據(jù),最后基于決策圖確定聚類數(shù)和聚類中心,實(shí)現(xiàn)對(duì)圖像的準(zhǔn)確分割。

1 相關(guān)理論

1.1 密度峰值聚類算法

文獻(xiàn)[19]提出的DPC算法是一種新型的選取聚類中心的方法,其選取的聚類中心有本身的局部密度大和與其他局部密度大的樣本點(diǎn)相對(duì)距離較遠(yuǎn)2個(gè)主要特征。基于上述聚類中心的特征,DPC算法計(jì)算樣本點(diǎn)的局部密度和相對(duì)距離,建立決策圖,根據(jù)決策圖選取聚類中心,再對(duì)非聚類中心的樣本點(diǎn)進(jìn)行歸類合并,從而實(shí)現(xiàn)聚類[19]。

DPC算法中的局部密度和相對(duì)距離這2個(gè)特征分別用參數(shù)ρi和δi來刻畫,一般選擇ρi和δi值較大的點(diǎn)作為聚類中心,實(shí)現(xiàn)聚類。

樣本點(diǎn)xi的局部密度ρi數(shù)學(xué)公式定義如下:

(1)

樣本點(diǎn)xi的相對(duì)距離δi的數(shù)學(xué)公式定義如下:

(2)

DPC算法原理簡(jiǎn)單,效率較高,所需參數(shù)較少,僅需要局部密度和相對(duì)距離2個(gè)參數(shù),從式(1)和式(2)可以看出,算法的一個(gè)關(guān)鍵參數(shù)為截?cái)嗑嚯x,而參數(shù)截?cái)嗑嚯xdc的選取是基于若干數(shù)據(jù)集的經(jīng)驗(yàn)值[20]。截?cái)嗑嚯xdc一般默認(rèn)為dij升序排列后前2%處的取值,dc的選取在一定程度上影響著聚類的效果,其值過大過小都會(huì)使得聚類效果變差。極端情況下,當(dāng)dc小于dmin時(shí),每個(gè)樣本點(diǎn)都是一類;當(dāng)dc大于dmax時(shí),整個(gè)數(shù)據(jù)集是一類。因此,DPC選取的dc在真實(shí)的數(shù)據(jù)集中分類效果可能不理想。

1.2 信息熵理論

信息論中的信息熵是一種系統(tǒng)有序化程度的度量方法。在一個(gè)系統(tǒng)中,某個(gè)屬性取值提供的信息量越多,系統(tǒng)越穩(wěn)定,信息熵越小;反之,該屬性提供的信息量越少,系統(tǒng)越混亂,信息熵越大[21]。因此,信息熵在聚類分析領(lǐng)域得到了廣泛的應(yīng)用。

對(duì)于隨機(jī)變量X,香農(nóng)定義的信息熵公式如下:

H(X)=-∑p(xi)lb(p(xi)),i=1,2,…,n

(3)

其中,p(xi)表示為事件xi發(fā)生的概率,且∑p(xi)=1。一般信息熵的單位為bit。

2 基于改進(jìn)DPC的圖像分割算法

2.1 改進(jìn)的密度峰值聚類

針對(duì)DPC算法中截?cái)嗑嚯xdc靠經(jīng)驗(yàn)取值這一情況,本文提出了一種基于信息熵的截?cái)嗑嚯x自適應(yīng)的密度峰值聚類算法EDPC。在EDPC中首先通過信息熵得到自適應(yīng)的截?cái)嗑嚯x,然后計(jì)算各個(gè)參數(shù),畫出決策圖,根據(jù)決策圖來選擇聚類中心,進(jìn)行聚類分析。

在DPC算法中,局部密度ρi定義采用離散的密度函數(shù),導(dǎo)致樣本點(diǎn)具有相同局部密度的可能性較大,不利于后續(xù)研究,因此,本文采用連續(xù)高斯核密度函數(shù)來刻畫局部密度,其相應(yīng)的定義如下:

(4)

其中,dc∈(0,+∞)為自適應(yīng)截?cái)嗑嚯x。

(5)

信息熵作為一種不確定性的度量,被廣泛應(yīng)用于聚類分析中用以判斷聚類效果的好壞程度。EDPC將信息熵理論應(yīng)用到傳統(tǒng)的DPC中,用信息熵來判斷數(shù)據(jù)集聚類效果,如果數(shù)據(jù)集的信息熵較大,則數(shù)據(jù)集的聚類效果較差,數(shù)據(jù)較混亂;反之,數(shù)據(jù)集的聚類效果較好,數(shù)據(jù)相對(duì)較穩(wěn)定。因此,數(shù)據(jù)集的信息熵可表示為:

(6)

在EDPC中,假設(shè)每個(gè)樣本點(diǎn)的局部密度概率相等,則數(shù)據(jù)分布的不確度最大,此時(shí)有最大的熵。由式(6)可知,對(duì)于具有n個(gè)樣本點(diǎn)的數(shù)據(jù)集有0≤H≤lb(n)。對(duì)于該算法的高斯核函數(shù),由分析可知,當(dāng)dc趨近0時(shí),H趨近最大值lb(n);隨dc的增大,H首先減小,在某處達(dá)到最小值,然后逐漸增大,當(dāng)dc趨近+∞時(shí),H再一次趨近lb(n)。獲得效果最好的聚類效果等價(jià)于尋找使得H最小的dc值。因此,本文結(jié)合H在(0,+∞)上的變化情況對(duì)式(6)中的類信息熵函數(shù)H進(jìn)行求導(dǎo)得到H′,令H′=0來求取極值點(diǎn)處的所有dc值并代入H中,選取使其最小的dc作為自適應(yīng)的截?cái)嗑嚯x進(jìn)行聚類分析。

在真實(shí)數(shù)據(jù)集上驗(yàn)證EDPC算法的有效性,實(shí)驗(yàn)結(jié)果如圖1所示。進(jìn)一步地,在不同數(shù)據(jù)集中對(duì)比EDPC與DPC的聚類效果,結(jié)果如圖2所示。在圖2(a)中,采用DPC的聚類結(jié)果明顯地把一類數(shù)據(jù)劃分為了兩類,產(chǎn)生了數(shù)據(jù)誤分,而EDPC聚類效果較之更合理,分類更準(zhǔn)確;在圖2(b)中,DPC聚類邊界交叉度高,而且產(chǎn)生了部分?jǐn)?shù)據(jù)的誤分,而EDPC結(jié)果較好;在圖2(c)中,DPC聚類結(jié)果產(chǎn)生了數(shù)據(jù)遺失,EDPC保留了完整的數(shù)據(jù)數(shù)目;在圖2(d)中,DPC產(chǎn)生的聚類邊界相互交叉,聚類邊界不明顯,而EDPC產(chǎn)生的聚類邊界較之更清晰。從DPC與EDPC的對(duì)比實(shí)驗(yàn)可以看出,EDPC較DPC聚類效果更好,EDPC可以很好的彌補(bǔ)DPC截?cái)嗑嚯x靠經(jīng)驗(yàn)取值而導(dǎo)致的在部分?jǐn)?shù)據(jù)集上聚類不準(zhǔn)確以及聚類邊界交叉的不足。實(shí)驗(yàn)證明了將信息熵引入到DPC中較好地提升了算法的性能。

圖1 真實(shí)數(shù)據(jù)集算法聚類結(jié)果

圖2 EDPC與DPC在不同數(shù)據(jù)集上的聚類效果對(duì)比

Fig.2 Comparison of clustering effect between EDPC and DPC on different datasets

圖3和圖4給出EDPC、DPC、FCM 和DBSACN 4種算法在不同據(jù)集上的精度值和F值,精度值和F值的取值范圍均為[0,1],其值越大表示聚類效果越好。從圖3和圖4可以看出,在所有數(shù)據(jù)集上,EDPC算法的性能均優(yōu)于對(duì)比算法。在常見數(shù)據(jù)集上EDPC算法的聚類結(jié)果以及相應(yīng)的dc如表1所示。

圖3 不同算法精度對(duì)比

圖4 不同算法F值對(duì)比

表1 EDPC在不同數(shù)據(jù)集上的聚類結(jié)果

2.2 算法流程

基于DPC算法選取聚類中心的特點(diǎn),本文提出一種基于EDPC的圖像分割算法。該算法首先將輸入圖像的每一個(gè)像素點(diǎn)視為一個(gè)樣本點(diǎn),將其顏色空間的CIE Lab值作為樣本的特征數(shù)據(jù),然后通過計(jì)算信息熵求得自適應(yīng)截?cái)嗑嚯xdc,從而計(jì)算樣本點(diǎn)的局部密度ρi以及相對(duì)距離δi,建立相應(yīng)的決策圖,最后在決策圖中,將ρi和δi都很大的樣本點(diǎn)選取聚類中心,確定聚類中心總數(shù),歸類非聚類中心點(diǎn),剔除噪聲點(diǎn)從而完成圖像分割。

對(duì)于圖像的像素點(diǎn),本文修改了DPC算法中的公式。設(shè)分割圖像中有2個(gè)像素點(diǎn)i、j,Lab值分別用(Li,ai,bi)、(Lj,aj,bj)表示,本算法采用歐氏距離作為度量距離,則像素點(diǎn)i、j的歐式距離dij如下所示:

(7)

將得到的距離矩陣應(yīng)用到EDPC中進(jìn)行圖像分割,算法實(shí)施過程如圖5所示。

圖5 基于EDPC的圖像分割流程

基于EDPC的圖像分割算法的具體步驟如下:

1)輸入待分割的彩色圖像,讀取原始圖像數(shù)據(jù)。

2)將RGB圖像轉(zhuǎn)換為Lab圖像。

3)計(jì)算每個(gè)點(diǎn)與其他點(diǎn)的距離dij。

4)計(jì)算信息熵H的極小值,確定自適應(yīng)截?cái)嗑嚯xdc。

6)建立決策圖,選取聚類中心。

7)將剩余的像素樣本點(diǎn)根據(jù)EDPC算法進(jìn)行聚類處理。

8)完成最終的圖像分割,輸出圖像。

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

將本文算法與FCM、K-means、IGSO[22]以及IS-FDC[23]算法進(jìn)行對(duì)比實(shí)驗(yàn),驗(yàn)證其正確性以及有效性。實(shí)驗(yàn)的圖片來源于Berkeley圖像分割數(shù)據(jù)集[24],開發(fā)工具為MATLAB R2016b,不同算法的聚類分割結(jié)果如圖6所示。從圖6可以看出,FCM和K-means的圖像分割效果較差,分割結(jié)果容易受噪聲影響,單一的目標(biāo)和背景容易產(chǎn)生誤分,而且生成的像素塊模糊程度較高,而本文算法EDPC和IS-FDC以及IGSO受噪聲影響小,分割效果更好,目標(biāo)區(qū)域和背景區(qū)域比較清晰。從實(shí)驗(yàn)結(jié)果還可以看出,本文算法針對(duì)單一目標(biāo)和背景差距較大的圖片分割效果更好。

圖6 不同算法的分割結(jié)果

不同算法具體的聚類細(xì)節(jié)如圖7所示。可以看出,在FCM和K-means分割時(shí)細(xì)節(jié)保留不夠完整,窗戶邊緣的窗戶框信息遺失,圖像分割不完整,聚類邊界交叉較多;而采用算法EDPC、IGSO和IS-FDC時(shí),建筑物上的窗戶幾乎完整地保留了窗戶框,細(xì)節(jié)保留更多,聚類邊界清晰,圖像分割效果更好。圖8在圖7基礎(chǔ)上展示了不同算法分割后真實(shí)圖片對(duì)比。可以看出,本文算法和IS-FDC較其他算法分割出來的目標(biāo)建筑更完整,遺失的細(xì)節(jié)較少。

圖7 不同算法的聚類細(xì)節(jié)比較

圖8 不同算法對(duì)真實(shí)圖片的分割細(xì)節(jié)結(jié)果比較

Fig.8 Comparison of real image segmentation details of different algorithms

為了進(jìn)一步證明EDPC算法在分割圖像方面的有效性和準(zhǔn)確性,本文在Berkeley數(shù)據(jù)集中隨機(jī)抽取50張圖片,計(jì)算每種算法的平均分割時(shí)間和平均PRI(Probabilistic Rand Index)指標(biāo),結(jié)果如表2所示。其中,PRI為算法分割結(jié)果的準(zhǔn)確程度,其取值范圍為[0,1],其值越大算法分割效果越好。

表2 不同算法的平均分割時(shí)間和PRI指標(biāo)

Table 2 Average segmentation time and PRI index of different algorithms

指標(biāo)FCMK-meansIGSOIS-FDCEDPCPRI0.6750.6940.6830.7230.721分割時(shí)間/s6.1925.5317.39012.76414.658

從表2可以看出,本文算法在Berkeley數(shù)據(jù)集上相對(duì)于FCM、K-means和IGSO分割效果更好。將EDPC應(yīng)用到圖像分割上,對(duì)于像素為n的圖像,樣本點(diǎn)之間距離的計(jì)算時(shí)間復(fù)雜度為O(n2),雖然算法時(shí)間消耗和內(nèi)存消耗較大,但仍然在可承受范圍內(nèi)。

4 結(jié)束語

針對(duì)傳統(tǒng)DPC算法依靠經(jīng)驗(yàn)選取截?cái)嗑嚯x的情況,本文提出基于信息熵的密度峰值聚類算法。通過計(jì)算信息熵的極小值獲得自適應(yīng)的截?cái)嗑嚯x,在此基礎(chǔ)上對(duì)輸入圖像進(jìn)行聚類并分割。在Berkeley數(shù)據(jù)集中進(jìn)行對(duì)比實(shí)驗(yàn),結(jié)果表明,與FCM、K-means和IGSO等算法相比,本文算法受噪聲影響小,分割效果較好,其PRI指標(biāo)為0.721,達(dá)到了預(yù)期效果。但本文算法未對(duì)圖像進(jìn)行預(yù)處理,導(dǎo)致分割時(shí)間較長,后續(xù)將對(duì)此進(jìn)行改進(jìn),減少計(jì)算數(shù)據(jù)量,從而提高算法分割速度。