基于改進密度峰值聚類算法的圖像分割

張力丹，王軍鋒

(西安理工大學(xué) 理學(xué)院，陜西 西安 710054)

0 引 言

聚類作為一種無監(jiān)督的分類方法，能夠用于無標簽的數(shù)據(jù)對象的劃分[1]。作為數(shù)據(jù)處理的技術(shù)，聚類分析已經(jīng)廣泛應(yīng)用于多個領(lǐng)域，例如計算機科學(xué)、數(shù)學(xué)、經(jīng)濟學(xué)等。聚類可分為劃分聚類、層次聚類、基于密度的聚類和基于網(wǎng)格的聚類等。K-means作為最為經(jīng)典且具代表性的劃分聚類，需在給定簇類個數(shù)的前提下，經(jīng)過反復(fù)迭代獲取最優(yōu)分組，但是該方法很難用于非球形聚類數(shù)據(jù)的無監(jiān)督劃分[2]。FCM聚類算法作為軟聚類法的代表之一，需要構(gòu)造各數(shù)據(jù)點歸屬于某一簇類的隸屬度函數(shù)，而同一數(shù)據(jù)點可同時歸屬至不同的簇類中[3]。DBSCAN算法在限制Eps鄰域及最小核心點MinPts下，通過建立了密度可達及直接密度可達一套機制將數(shù)據(jù)進行歸類，但很難發(fā)現(xiàn)密度變化差異明顯的簇類[4]。

2014年Alex Rodriguez發(fā)表于《Science》上的密度峰值聚類(DPC)算法[5]，其核心思想在于對簇類中心的刻畫。該算法認為簇類中心同時具有兩個特點：一是具有較大的密度，即簇類中心被密度較小的數(shù)據(jù)點包圍；二是與其他局部密度更高的點的距離較大。該文將對DPC算法中的敏感參數(shù)截斷距離dc進行自適應(yīng)選取，并將改進的DPC算法應(yīng)用于圖像分割。

1 密度峰值聚類算法

DPC算法在含n個數(shù)據(jù)點的數(shù)據(jù)集中定義了各點i(i=1,2,…,n)的局部密度ρi和局部距離δi。局部密度ρi的計算公式如下：

(1)

(2)

式中，dij為各數(shù)據(jù)點間的相似度；dc為截斷距離，本質(zhì)為簇類中心的鄰域半徑。上述公式表明，各數(shù)據(jù)點的局部密度為dc鄰域內(nèi)所含數(shù)據(jù)點個數(shù)[6]。截斷距離dc的選取基于各數(shù)據(jù)點的相似度，取值為升序排列的第c個數(shù)據(jù)點間的相似度dij，c的計算公式為：

c=?N×P+0.5」

(3)

式中，N為數(shù)據(jù)點間相似度總數(shù)；P為截斷距離dc的取值閾值。因此，截斷距離dc仍需依賴人為選取的閾值P。各數(shù)據(jù)點的局部距離δi刻畫了各數(shù)據(jù)點與密度更高點之間的距離，具體計算公式如下：

(4)

上式表明，對于局部密度最大的數(shù)據(jù)點，其局部距離為該點與其他數(shù)據(jù)點間相似度的最大值[7]；其余數(shù)據(jù)點的局部距離則為該點與其他數(shù)據(jù)點間相似度的最小值。計算簇類中心的選擇閾值γi：

γi=f(δi,ρi)

(5)

上式表明，閾值γi為關(guān)于局部密度ρi和局部距離δi的函數(shù)。文獻[4]將前K個降序排列的γi所對應(yīng)的數(shù)據(jù)點作為簇類中心。

2 自適應(yīng)截斷距離dc的DPC算法

DPC算法在計算局部密度ρi時采用基于ε近鄰的方式，將數(shù)據(jù)點xi的dc鄰域內(nèi)包含的數(shù)據(jù)點個數(shù)作為該點局部密度。dc的選取依賴于人為確定的閾值P，P按經(jīng)驗取值為1%～2%。DPC算法核心在于計算各數(shù)據(jù)點的局部密度ρi和局部距離δi，并將局部密度ρi和局部距離δi的局部極值點作為局部峰值點，也就是簇類中心。其中局部距離δi的計算依賴于局部密度ρi，而局部密度ρi的計算又依賴于截斷距離dc，因此dc的選取對密度峰值聚類結(jié)果的影響尤為重要[8-10]。

然而不同的數(shù)據(jù)內(nèi)部稀疏程度不一致，若僅靠經(jīng)驗值選取截斷距離dc勢必導(dǎo)致錯誤歸類。閾值P過大會導(dǎo)致截斷距離dc取值過大，容易將本不屬于同一簇類的像素點合并；閾值P過小又會導(dǎo)致截斷距離dc取值過小，容易將本屬于同一簇類的像素點分成多個簇類，因此基于閾值P的截斷距離dc并不可靠且影響了局部密度ρi的全局可靠性[11]。

2.1 基于最小化信息熵的截斷距離dc

DPC算法中定義的局部密度ρi依賴于截斷距離dc以及數(shù)據(jù)點間的相似度dij。實際中，數(shù)據(jù)集在不同維度上的分量通常不在一個數(shù)量級上[12-13]，為此該文重新定義數(shù)據(jù)點間的相似度dij。計算數(shù)據(jù)集X的第d維分量的極差A(yù)d：

Ad=max(Id)-min(Id)

(6)

將數(shù)據(jù)點xi和xj間的相似度dij定義為：

(7)

式中，D為數(shù)據(jù)維數(shù)。計算當(dāng)前數(shù)據(jù)點xi的dc鄰域內(nèi)相似度均值μdc_i：

(8)

式中，p和q為當(dāng)前數(shù)據(jù)點xi的dc鄰域內(nèi)所含數(shù)據(jù)點；N_i為該點dc鄰域內(nèi)所含數(shù)據(jù)點的個數(shù)。設(shè)數(shù)據(jù)集含有n個數(shù)據(jù)點，引入高斯核將當(dāng)前數(shù)據(jù)點的局部密度ρi定義為：

(9)

改進的局部密度增加了數(shù)據(jù)點xi的dc鄰域內(nèi)所含數(shù)據(jù)點的影響權(quán)值，使得同一簇類當(dāng)中的數(shù)據(jù)點相似程度更緊密。各數(shù)據(jù)點的概率密度定義為：

(10)

對于一個包含n個隨機變量x1,x2,…,xn的系統(tǒng)，其信息熵為：

(11)

則基于公式(10)得到的數(shù)據(jù)集信息熵為：

(12)

由上式可知，改進方法后的信息熵中唯一變量為截斷距離dc。隨機事件發(fā)生的概率越大提供的信息越少，信息熵體現(xiàn)出事件的不確定性。因此作為一種量化指標，信息熵越小對應(yīng)的系統(tǒng)越穩(wěn)定[14-15]。

該文將使得信息熵最小的dc值作為截斷距離dc的最優(yōu)取值，具體如下：

dc=arg minH(X)

(13)

2.2 基于改進DPC算法在圖像分割上的應(yīng)用

在DPC算法中，若局部密度ρi和局部距離δi越大，則對應(yīng)的數(shù)據(jù)點xi越有可能成為簇類中心。DPC算法通過公式(5)將降序排列的前K個γi所對應(yīng)的數(shù)據(jù)點作為簇類中心，這種選取方式本質(zhì)上仍需人為選擇。為了自適應(yīng)地選擇圖像的簇類中心，定義簇類中心點選取的閾值γmin為：

γmin=E(ρ)×E(δ)

(14)

式中，E(ρ)和E(δ)分別為數(shù)據(jù)點的局部密度均值和局部距離均值。若當(dāng)前數(shù)據(jù)點為簇類中心，則該數(shù)據(jù)點的局部密度ρi和局部距離δi應(yīng)遠大于其余數(shù)據(jù)點。將符合公式(14)的數(shù)據(jù)點作為初始的簇類中心。

計算各數(shù)據(jù)點的ρi和δi的乘積，并記作γi：

γi=ρi×δi

(15)

在確定閾值之后，對初始判斷的簇類中心進行深度篩選，最終確定的簇類中心集合C為：

C={ci|γi>γmin,δi>dc,ci∈X}

(16)

上式表明，dc作為一個特殊的鄰域半徑，應(yīng)當(dāng)小于簇類中心之間的距離。因此，選擇γi大于閾值γmin且δi大于dc的對應(yīng)點作為簇類中心。

由于DPC算法需要計算數(shù)據(jù)點之間的距離，以此來判斷數(shù)據(jù)點之間的相似程度，因此對于一般圖像而言，將像素點作為輸入數(shù)據(jù)進行密度峰值聚類會耗時很久。為解決DPC聚類在處理較大數(shù)據(jù)集用時較久這一問題，采用并行分塊處理圖像數(shù)據(jù)的方式。將一般圖像劃分成M×N個塊，對每一塊依次使用改進的密度峰值聚類進行分割，將每一塊的像素點作為輸入數(shù)據(jù)，得到每一塊的聚類中心(共計k'個)。在此基礎(chǔ)之上，使用提出的改進的密度峰值聚類，重新對M×N個塊中的k'個聚類中心進行二次聚類，此次聚類的輸入數(shù)據(jù)為k'個聚類中心，輸出數(shù)據(jù)為最終的k個聚類中心。經(jīng)過兩次聚類之后得到最終需要的聚類中心，最后對所有數(shù)據(jù)按照相似度進行歸類，得到最終的分割結(jié)果?；诟倪MDPC算法的圖像分割流程如下所示。

算法1：基于改進算法的圖像分割。

輸入：圖像I

將圖像進行分塊處理，共計M×N個塊.

Whilei≤最大迭代次數(shù)M×N

Run 第一次調(diào)用改進的DPC算法：

提取像素點特征：X,Y,R,G,B,LBP(分別為位置特征X、Y，顏色特征R、G、B，LBP紋理特征)；

利用公式(7)計算像素點間的相似度dij；

利用公式(13)計算截斷距離dc；

使用公式(9)和公式(4)分別計算局部密度ρi、計算局部距離δi；使用公式(14)計算簇類中心選擇閾值γmin；并使用公式(16)選取簇類中心；

遍歷歸類剩余像素點；

將屬于同一類的像素點進行合并；

輸出當(dāng)前塊的聚類結(jié)果；

End

End

二次調(diào)用改進的DPC算法，將第一次聚類中屬于同一類的區(qū)域進行合并；

輸出最終分割結(jié)果.

3 實驗結(jié)果與分析

3.1 實驗環(huán)境

對多個彩色數(shù)字圖像數(shù)據(jù)集使用文中算法進行分割，并將文中算法與K-means、FCM、DPC算法和文獻[5]中的算法進行對比，驗證改進算法具有較高的分割精度，實驗硬件為i5-6500 CPU @ 3.20 GHz,RAM 4.00 GB,64位操作系統(tǒng)，實驗軟件為Matlab R2016b。

3.2 圖像分割評價指標

3.2.1 概率蘭德指數(shù)(PRI)

設(shè)圖像共包含N個像素點，Sg為GroundTruth，使用不同算法得到的分割結(jié)果記為Stest。當(dāng)Sg的第i個像素與Stest中第j個像素具有相同標簽時，將該事件記作Aij，該事件發(fā)生的概率為pij。PRI指標取值范圍為[0,1]，數(shù)值越大算法分割精度越高。PRI指標具體計算方式為：

(17)

3.2.2 變換信息量指數(shù)(VOI)

計算分割結(jié)果Stest和GroundTruth圖像Sg信息熵之和，并減去二者的聯(lián)合信息熵，將計算結(jié)果作為VOI指標值。該指數(shù)代表相對變化的信息量，VOI越小實驗精度越高，且越接近GroundTruth。VOI指數(shù)具體計算方式為：

VOI(Sg,Stest)=H(Sg)+H(Stest)-2H(Sg,Stest)

(18)

3.2.3 欠分割誤差(USE)

所謂的“欠分割”是指前景目標錯誤地劃分到背景中，反之“過分割”提取到的前景中包含本屬于背景中的某些區(qū)域。USE指標能夠衡量圖像中的分割精度，對于包含N個像素點的數(shù)字圖像，其在不同算法下得到的分割結(jié)果Stest與Sg分別由nb和nbst個不相交的區(qū)域構(gòu)成：

(19)

(20)

(21)

式中，B為分割結(jié)果圖像與GroundTruth圖像中包含共同像素點個數(shù)的最小值。據(jù)公式(21)可知，USE越小實驗精度就越高。

3.3 結(jié)果分析

3.3.1 二維數(shù)據(jù)聚類效果

(1)二維數(shù)據(jù)集。

選用6個不同數(shù)據(jù)集進行實驗分析，表1給出了數(shù)據(jù)集的樣本數(shù)和真實類別數(shù)。圖1為原始數(shù)據(jù)分布。

表1 不同數(shù)據(jù)集信息

圖1 原始數(shù)據(jù)集分布

(2)二維數(shù)據(jù)聚類效果。

為驗證改進算法的有效性，分別使用DPC算法和改進算法進行實驗，對比結(jié)果如圖2所示。圖2第一列為DPC算法結(jié)果，第二列為改進的DPC算法結(jié)果。其中將DPC算法中的截斷距離閾值P均設(shè)置為0.01，簇類個數(shù)與真實數(shù)據(jù)保持一致。改進算法的截斷距離dc均可自適應(yīng)取得，簇類個數(shù)與真實數(shù)據(jù)保持一致。觀察可得除了第四組數(shù)據(jù)集Jain以外，改進算法的聚類結(jié)果與原始分布更加吻合。

為了進一步驗證文中算法的可靠性，選用精確度(ACC)、F測度(FM)和蘭德系數(shù)(RI)三個有效性指標對算法結(jié)果進行量化分析，三個指標值越大，聚類效果越好。表2給出了6個數(shù)據(jù)集在DPC算法和文中改進算法下的指標值，綜合比較可知改進算法有效性指標值更佳。

表2 不同數(shù)據(jù)的有效性指標

圖2 原始數(shù)據(jù)集分布

3.3.2 數(shù)字圖像分割效果

為驗證文中算法能夠較好地應(yīng)用于圖像分割，使用改進算法對數(shù)字圖像數(shù)據(jù)集進行分割。將文中算法與K-means、FCM、DPC和文獻[5]中的算法進行對比，驗證改進算法具有較高的分割精度，對比算法的分割結(jié)果如圖3所示。K-means、FCM、DPC和文獻[5]中的算法需要確定簇類個數(shù)，且運行時間會隨著類簇個數(shù)的增加而增加，而文中算法平均耗時為8秒，無論分割的簇類數(shù)有多大，運行時間基本不會發(fā)生改變，且文中算法的分割結(jié)果同GroundTruth更貼近，更能夠清晰地分割圖像邊緣輪廓，將感興趣的目標同背景分離。

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

由圖3可知，上述算法均能對數(shù)字圖像進行分割。但在細節(jié)方面，K-means和FCM算法會出現(xiàn)過分割的現(xiàn)象，即冗余區(qū)域過多，導(dǎo)致本應(yīng)屬于同一區(qū)域的像素點被冗余的分割線條劃分開，DPC算法和文獻[5]中的算法錯誤分割較多。四種對比算法下的分割結(jié)果，均會導(dǎo)致顏色變化并不突兀的地方出現(xiàn)了過多冗余線條。而改進算法的分割得到圖像輪廓與GroundTruth更加貼近，每個獨立目標中的小區(qū)域很少，提取的輪廓界限也更加清晰可見。

作為較為經(jīng)典的聚類算法，K-means比原始的DPC算法在圖像分割上具有更明顯的分割精度，然而無論是K-means、FCM、DPC還是文獻[5]中的算法，均無法合理地選取簇類個數(shù)，這也是傳統(tǒng)的聚類方法面臨的統(tǒng)一難題。通過橫向?qū)Ρ劝l(fā)現(xiàn)，改進算法具有較強的穩(wěn)定性，從三個評價指標來看，改進算法均具有較強的優(yōu)越性，無需確定任何參數(shù)，便可自適應(yīng)地進行較為理想的圖像分割。計算圖3中的3幅圖像PRI、VOI和USE三個指標平均值，指標數(shù)據(jù)如表3所示。

表3 各指標比較

4 結(jié)束語

針對DPC算法對參數(shù)敏感的問題，對截斷距離dc進行自適應(yīng)選取，并將改進的算法應(yīng)用于圖像分割。為解決DPC算法難以處理較大圖像的問題，提出了分塊并行的解決思路，并根據(jù)圖像各區(qū)域內(nèi)聚程度提出自適應(yīng)獲取數(shù)字圖像簇類個數(shù)的方法。實驗表明，該算法不但對二維數(shù)據(jù)有較好的聚類效果，而且能夠適用于圖像分割。