自適應煙花算法下多維模糊C均值彩色圖像分割

王 龍 梅英杰 王 霄 楊 靖

(貴州大學電氣工程學院 貴州 貴陽 550025)

0 引 言

隨著科學技術的發展，人們對彩色圖像分割越來越重視，聚類方法也廣泛地運用于圖像分割。常見的聚類分割方法有Mean Shift算法、K-means算法、Fuzzy C-mean算法等[1]。Bezdek基于模糊集提出模糊C均值理論[2]，模糊C均值(FCM)算法是目前應用最為廣泛的算法之一，它可以保留比硬聚類更多的圖像信息，但是它不考慮空間信息，因而對噪聲和其他成像比較敏感。

為了解決這些問題，Zhang等[3]提出了一種結合局部空間和灰度信息約束的自適應模糊局部信息C均值聚類方法，利用新的模糊局部相似度測度，自動實現對噪聲不敏感和邊緣模糊偽影減少之間的平衡，以保持圖像細節。Zhao等[4]提出基于泰森多邊形法(VT)和隱馬爾可夫隨機場(HMRF)的模糊C均值(FCM)算法紋理圖像分割，該算法結合了魯棒區域HMRF和基于FCM的聚類分割的優點。Jing等[5]提出了一種基于模糊聚類和空間金字塔的圖像分割算法，該算法具有較好的精度和時間復雜度。Fan等[6]利用神經動態優化的兩相模糊聚類算法，并將其應用于極化合成孔徑雷達遙感圖像的分割，該聚類算法具有一定的有效性和優越性。

盡管現有基于模糊聚類改進的方法的圖像分割技術有較好的效果，但也存在一些不足之處，圖像分割不僅要保持圖像細節的處理，又要保證圖像分割的精度。本文利用多維相似性，克服歐氏距離依靠時間而忽視趨勢特征的缺陷，在聚類過程中引入煙花算法，防止陷入局部最優，使算法達到全局最優。實驗表明，本文方法可以有效地對圖像分割，且保持圖像的細節，分割精度高。

1 相關工作

為了解決傳統的FCM圖像分割對圖像的影響，結合動態時間彎曲的思想，解決歐氏距離的不足，運用煙花算法尋找最優解，達到圖像分割的效果。

本文算法流程如圖1所示。

圖1 自適應模糊C均值算法流程

1.1 模糊C均值算法(FCM)

模糊C均值算法目標函數[7-8]如下:

(1)

式中：m是模糊隸屬度的加權指數；xi是第i個像素的灰度值；vk是k個簇的原型值；uki是模糊程度；Gki是模糊因子。

式(1)模糊因子Gki表示為：

(2)

式中：dij表示像素xi與xj之間的歐氏距離。

利用拉格朗日乘子法得出隸屬度劃分矩陣和聚類中心如下：

(3)

(4)

1.2 動態時間彎曲(DTW)

動態時間彎曲(DTW)是應用于時間序列數據分類和聚類算法中的一種流行并有效的距離度量方法[9]。假設x={xi∈R,i=1,2,…,n},y={yj∈R,j=1,2,…,n}那么，矩陣D(i,j)對應xi和yj，構造矩陣元素D(i,j)的一條彎曲路徑P=(P1,P2,…,Pk)，再最小化彎曲代價下DTW距離：

(5)

DDTW(x,y)=DTW(x′,y′)

(6)

DDDTW(x,y)=(1-a)DTW(x,y)+aDDTW(x,y)

(7)

式中：DDTW是DTW的時間序列x、y的導數；α是特征權重，α∈[0,1]；DDDTW表示改進的動態時間彎曲。

1.3 煙花算法(FWA)

Tan等[11]根據煙花爆炸產生的火花提出了煙花算法(FWA)。該算法對局部和全局優化有很強的平衡能力。在煙花算法中，煙花的爆炸半徑和煙花的爆炸火花數目是由對煙花適應度評估得到的，其中對煙花xi、爆炸半徑Ai和爆炸火花數目Si的計算如下：

(8)

(9)

雖然煙花算法的局部優化和全局優化能力很強，但是算法仍然會有計算、選擇策略不足。余冬華等[12]提出峰值火花及探索火花概念,增強了尋找最優解的能力,降低了對初值的敏感性,并提升了搜索效率。徐一等[13]提出了一種基于學習的煙花算法(LFWA)，通過學習利用煙花的歷史爆炸信息,自適應地估計后代煙花的爆炸幅度,解決爆炸幅度難以設定的問題。Li等[14]提出自適應煙花算法(AFWA)，通過煙花的爆炸半徑的確定依據當前種群適應度值最優的個體和一個特定個體之間的距離計算。

2 自適應煙花算法優化改進的FCM算法

通過動態時間彎曲改進相似性距離，將其改進成多維相似FCM算法，在自適應煙花算法尋優下，達到理想的圖像分割效果。

2.1 改進的相似性距離

傳統的FCM聚類，采用歐氏距離表示相似度量：

(10)

由于歐氏距離是在數據上直觀地體現，受主觀的影響比較大，不能很好地表現真實的相似度量。由式(7)的思想，采用改進的DTW序列點匹配的相似度結合歐氏距離，構造出多維相似性距離如下：

(11)

式中：α、ε是特征權重，且α=1-ε,α∈[0,1]。由實驗驗證本文α取0.3，ε取0.7。

2.2 多維模糊C均值算法

針對傳統的模糊C均值算法，引入多維相似性距離，改進FCM算法。假設xi是第i個像素的區域，yj是第j個像素的區域，p={p1,p2,…,pi}為i區域的像素點的集合，可視為一個種群。根據式(11)，可得到多維相似距離：

(12)

由式(12)和式(1)，可得到新的目標函數：

(13)

uki滿足如下關系：

(14)

對式(13)引入拉格朗日乘子法有：

(15)

(16)

(17)

式(16)和式(17)分別表示隸屬度的更新公式和聚類中心的更新公式。

2.3 算法流程

自適應煙花算法(AFWA)是通過種群最優個體與一個特定個體之間的距離確定煙花爆炸半徑，并根據搜索結果進行自適應調節。設v={v1,v2,…,vi},vi為第i代種群，個體x={x1,x2,…,xi},xi為第i個像素區域。隨機選取C個樣本作為初始聚類中心，初始化第一代種群v1，計算劃分矩陣uki,將其分配到臨近的簇類中。更新聚類中心vi，從而獲得新的種群vi以及新的相似距離D。其中：UB、LB是P區域搜索空間的上下界；A*為最優煙花半徑。

自適應煙花多維FCM算法過程如算法1所示。

算法1自適應煙花多維FCM算法

在搜索空間中隨機選取m個煙花

評估A*←UB-LB

初始化:聚類中心r,種群v

重復

(1) 根據式(16)和式(17)計算uki和vi

(2) 生成種群v0

(3) 根據式(13)計算適應值

(4) 根據式(8)和式(9)計算Ai和Si

(5) 產生爆炸性煙花Si

(6) 生成高斯煙花

(7) 計算A*

(8) 選取最優煙花

(9) 在其余個體隨機選擇N-1煙花與最優煙花形成下一代種群直到滿足終止條件(Jm-Jm-1≤η)

輸出聚類中心

3 實驗結果分析

本文選用 NDFCM算法[15]、AFCM算法[16]、HFCM算法[17]、CKGSA-FC算法[18]與本文算法進行對比，從主觀評價和客觀評價對算法的效果進行評估。

主觀評價主要是通過人眼的視覺、主觀的感受加以評價，其評價比較片面。客觀的評價采用DICE系數[19-20]、PRI系數和BDE誤差[21-22]來評估圖像分割后的效果。DICE越接近1，表明圖像分割的效果越好。PRI值越大越好，取值范圍為[0,1]。BDE值越小越好，取值范圍為[0,∞]。本文實驗采用Windows7 64位操作系統，Intel(R)Core(TM)i5-3230 2.60 GHz，4 GB內存。本文算法所涉及的參數選取為：m=2,C=3,α=0.3,ε=0.7。

3.1 主觀評價

本文選取圖2為原始圖，圖3-圖7分別為本文算法、NDFCM算法、AFCM算法、HFCM算法以及CKGSA-FC算法的展示分割效果。由分割效果對比來看，NDFCM算法整體分割的直觀效果還不錯，圖4(a)把老虎部分區域劃分到了其他區域，造成了分割效果不好；圖4(b)和圖4(d)對目標分割效果不錯，但對細節的保持有些不夠，對分割目標的輪廓較粗糙。AFCM算法對細節處理不夠好，圖5(b)把目標區域劃分到其他區域，造成圖像的過度分割。HFCM算法分割效果比較粗糙，對細節把握也不好，如圖6(e)效果比較模糊；圖6(c)沒有達到分割效果，分割目標沒有突出。CKGSA-FC算法對分割整體效果不錯，細節的保持把握也可以。圖7(b)出現過度分割，造成幾個區域效果不理想；圖7(c)對細節保持較好，但會影響其他分割區域。

與其他幾種算法比較，本文算法對細節保持較好，也沒有出現過度分割，造成幾個分割區域混亂的情況；從圖3可以看出，分割的圖像整體效果比其他幾種算法分割效果好，各個分割區域一目了然，沒有出現區域重疊情況。

圖2 原始圖 圖3 本文算法 圖4 NDFCM分割 圖5 AFCM分割 圖6 HFCM分割 圖7 CKGSA-FC算法

3.2 客觀評價

表1中，雖然本文算法在圖3(a)的分割圖DICE數據指標并非是最優的，但是在幾個圖號指標比較上，綜合指標性能最好。表2、表3中本文算法指標均優于其他算法，分割效果比較良好，較其他算法分割后的圖像細節保持完整，體現了本文算法的穩定性。且本文算法更適合人眼視覺，能更直觀地體現分割效果。由總體指標性能的結果顯示，本文算法優于其他算法。

表1 圖像DICE指標對比結果

表2 圖像PRI指標結果對比

表3 圖像BDE指標對比結果

4 結 語

本文結合自適應煙花算法和改進的多維模糊C均值算法，利用多維相似距離克服歐氏距離的缺點，自適應煙花算法確定聚類中心、聚類個數，解決模糊C忽視空間鄰域信息的問題。根據實驗可知，本文算法對圖像的分割既保留了細節，也提高了分割精度，證明算法在彩色圖像分割應用上的優越性。但引入尋優算法，增加了算法的復雜性，分割耗時較長，算法還可以進一步地優化改進。