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

張力丹，王軍鋒

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

0 引 言

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

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

1 密度峰值聚類算法

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

(1)

(2)

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

c=?N×P+0.5」

(3)

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

(4)

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

γi=f(δi,ρi)

(5)

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

2 自適應截斷距離dc的DPC算法

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

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

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

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

Ad=max(Id)-min(Id)

(6)

將數據點xi和xj間的相似度dij定義為：

(7)

式中，D為數據維數。計算當前數據點xi的dc鄰域內相似度均值μdc_i：

(8)

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

(9)

改進的局部密度增加了數據點xi的dc鄰域內所含數據點的影響權值，使得同一簇類當中的數據點相似程度更緊密。各數據點的概率密度定義為：

(10)

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

(11)

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

(12)

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

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

dc=arg minH(X)

(13)

2.2 基于改進DPC算法在圖像分割上的應用

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

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

(14)

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

計算各數據點的ρi和δi的乘積，并記作γi：

γi=ρi×δi

(15)

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

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

(16)

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

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

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

輸入：圖像I

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

Whilei≤最大迭代次數M×N

Run 第一次調用改進的DPC算法：

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

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

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

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

遍歷歸類剩余像素點；

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

輸出當前塊的聚類結果；

End

End

二次調用改進的DPC算法，將第一次聚類中屬于同一類的區域進行合并；

輸出最終分割結果.

3 實驗結果與分析

3.1 實驗環境

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

3.2 圖像分割評價指標

3.2.1 概率蘭德指數(PRI)

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

(17)

3.2.2 變換信息量指數(VOI)

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

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

(18)

3.2.3 欠分割誤差(USE)

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

(19)

(20)

(21)

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

3.3 結果分析

3.3.1 二維數據聚類效果

(1)二維數據集。

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

表1 不同數據集信息

圖1 原始數據集分布

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

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

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

表2 不同數據的有效性指標

圖2 原始數據集分布

3.3.2 數字圖像分割效果

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

圖3 不同算法分割結果

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

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

表3 各指標比較

4 結束語

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