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

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

(重慶郵電大學 計算智能重慶市重點實驗室,重慶 400065)

0 概述

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

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

本文提出一種基于DPC的圖像分割算法。針對傳統DPC中的參數截斷距離靠經驗取值的情況,引入信息論中信息熵的概念,求得其自適應的截斷距離,得到改進后的密度峰值聚類(EDPC),并在EDPC的基礎上對彩色圖像進行分割。該算法將彩色圖像的每個像素點的顏色特征空間作為聚類算法的輸入數據,最后基于決策圖確定聚類數和聚類中心,實現對圖像的準確分割。

1 相關理論

1.1 密度峰值聚類算法

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

DPC算法中的局部密度和相對距離這2個特征分別用參數ρi和δi來刻畫,一般選擇ρi和δi值較大的點作為聚類中心,實現聚類。

樣本點xi的局部密度ρi數學公式定義如下:

(1)

樣本點xi的相對距離δi的數學公式定義如下:

(2)

DPC算法原理簡單,效率較高,所需參數較少,僅需要局部密度和相對距離2個參數,從式(1)和式(2)可以看出,算法的一個關鍵參數為截斷距離,而參數截斷距離dc的選取是基于若干數據集的經驗值[20]。截斷距離dc一般默認為dij升序排列后前2%處的取值,dc的選取在一定程度上影響著聚類的效果,其值過大過小都會使得聚類效果變差。極端情況下,當dc小于dmin時,每個樣本點都是一類;當dc大于dmax時,整個數據集是一類。因此,DPC選取的dc在真實的數據集中分類效果可能不理想。

1.2 信息熵理論

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

對于隨機變量X,香農定義的信息熵公式如下:

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

(3)

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

2 基于改進DPC的圖像分割算法

2.1 改進的密度峰值聚類

針對DPC算法中截斷距離dc靠經驗取值這一情況,本文提出了一種基于信息熵的截斷距離自適應的密度峰值聚類算法EDPC。在EDPC中首先通過信息熵得到自適應的截斷距離,然后計算各個參數,畫出決策圖,根據決策圖來選擇聚類中心,進行聚類分析。

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

(4)

其中,dc∈(0,+∞)為自適應截斷距離。

(5)

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

(6)

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

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

圖1 真實數據集算法聚類結果

圖2 EDPC與DPC在不同數據集上的聚類效果對比

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

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

圖3 不同算法精度對比

圖4 不同算法F值對比

表1 EDPC在不同數據集上的聚類結果

2.2 算法流程

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

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

(7)

將得到的距離矩陣應用到EDPC中進行圖像分割,算法實施過程如圖5所示。

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

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

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

2)將RGB圖像轉換為Lab圖像。

3)計算每個點與其他點的距離dij。

4)計算信息熵H的極小值,確定自適應截斷距離dc。

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

7)將剩余的像素樣本點根據EDPC算法進行聚類處理。

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

3 實驗與結果分析

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

圖6 不同算法的分割結果

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

圖7 不同算法的聚類細節比較

圖8 不同算法對真實圖片的分割細節結果比較

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

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

表2 不同算法的平均分割時間和PRI指標

Table 2 Average segmentation time and PRI index of different algorithms

指標FCMK-meansIGSOIS-FDCEDPCPRI0.6750.6940.6830.7230.721分割時間/s6.1925.5317.39012.76414.658

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

4 結束語

針對傳統DPC算法依靠經驗選取截斷距離的情況,本文提出基于信息熵的密度峰值聚類算法。通過計算信息熵的極小值獲得自適應的截斷距離,在此基礎上對輸入圖像進行聚類并分割。在Berkeley數據集中進行對比實驗,結果表明,與FCM、K-means和IGSO等算法相比,本文算法受噪聲影響小,分割效果較好,其PRI指標為0.721,達到了預期效果。但本文算法未對圖像進行預處理,導致分割時間較長,后續將對此進行改進,減少計算數據量,從而提高算法分割速度。