張力丹，王軍鋒

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

0 引 言

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

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

1 密度峰值聚類算法

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

(1)

(2)

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

c=?N×P+0.5」

(3)

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

(4)

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

γi=f(δi,ρi)

(5)

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

2 自適應(yīng)截?cái)嗑嚯xdc的DPC算法

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

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

2.1 基于最小化信息熵的截?cái)嗑嚯xdc

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

Ad=max(Id)-min(Id)

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

(11)

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

(12)

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

該文將使得信息熵最小的dc值作為截?cái)嗑嚯xdc的最優(yōu)取值，具體如下：

dc=arg minH(X)

(13)

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

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

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

(14)

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

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

γi=ρi×δi

(15)

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

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

(16)

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

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

算法1：基于改進(jìn)算法的圖像分割。

輸入：圖像I

將圖像進(jìn)行分塊處理，共計(jì)M×N個(gè)塊.

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

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

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

利用公式(7)計(jì)算像素點(diǎn)間的相似度dij；

利用公式(13)計(jì)算截?cái)嗑嚯xdc；

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

遍歷歸類剩余像素點(diǎn)；

將屬于同一類的像素點(diǎn)進(jìn)行合并；

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

End

End

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

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

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

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 圖像分割評(píng)價(jià)指標(biāo)

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

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

(17)

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

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

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

(18)

3.2.3 欠分割誤差(USE)

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

(19)

(20)

(21)

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

3.3 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 各指標(biāo)比較

4 結(jié)束語

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