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

王 龍 梅英杰 王 霄 楊 靖

(貴州大學(xué)電氣工程學(xué)院 貴州 貴陽(yáng) 550025)

0 引 言

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

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

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

1 相關(guān)工作

為了解決傳統(tǒng)的FCM圖像分割對(duì)圖像的影響，結(jié)合動(dòng)態(tài)時(shí)間彎曲的思想，解決歐氏距離的不足，運(yùn)用煙花算法尋找最優(yōu)解，達(dá)到圖像分割的效果。

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

圖1 自適應(yīng)模糊C均值算法流程

1.1 模糊C均值算法(FCM)

模糊C均值算法目標(biāo)函數(shù)[7-8]如下:

(1)

式中：m是模糊隸屬度的加權(quán)指數(shù)；xi是第i個(gè)像素的灰度值；vk是k個(gè)簇的原型值；uki是模糊程度；Gki是模糊因子。

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

(2)

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

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

(3)

(4)

1.2 動(dòng)態(tài)時(shí)間彎曲(DTW)

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

(5)

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

(6)

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

(7)

式中：DDTW是DTW的時(shí)間序列x、y的導(dǎo)數(shù)；α是特征權(quán)重，α∈[0,1]；DDDTW表示改進(jìn)的動(dòng)態(tài)時(shí)間彎曲。

1.3 煙花算法(FWA)

Tan等[11]根據(jù)煙花爆炸產(chǎn)生的火花提出了煙花算法(FWA)。該算法對(duì)局部和全局優(yōu)化有很強(qiáng)的平衡能力。在煙花算法中，煙花的爆炸半徑和煙花的爆炸火花數(shù)目是由對(duì)煙花適應(yīng)度評(píng)估得到的，其中對(duì)煙花xi、爆炸半徑Ai和爆炸火花數(shù)目Si的計(jì)算如下：

(8)

(9)

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

2 自適應(yīng)煙花算法優(yōu)化改進(jìn)的FCM算法

通過(guò)動(dòng)態(tài)時(shí)間彎曲改進(jìn)相似性距離，將其改進(jìn)成多維相似FCM算法，在自適應(yīng)煙花算法尋優(yōu)下，達(dá)到理想的圖像分割效果。

2.1 改進(jìn)的相似性距離

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

(10)

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

(11)

式中：α、ε是特征權(quán)重，且α=1-ε,α∈[0,1]。由實(shí)驗(yàn)驗(yàn)證本文α取0.3，ε取0.7。

2.2 多維模糊C均值算法

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

(12)

由式(12)和式(1)，可得到新的目標(biāo)函數(shù)：

(13)

uki滿足如下關(guān)系：

(14)

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

(15)

(16)

(17)

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

2.3 算法流程

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

自適應(yīng)煙花多維FCM算法過(guò)程如算法1所示。

算法1自適應(yīng)煙花多維FCM算法

在搜索空間中隨機(jī)選取m個(gè)煙花

評(píng)估A*←UB-LB

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

重復(fù)

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

(2) 生成種群v0

(3) 根據(jù)式(13)計(jì)算適應(yīng)值

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

(5) 產(chǎn)生爆炸性煙花Si

(6) 生成高斯煙花

(7) 計(jì)算A*

(8) 選取最優(yōu)煙花

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

輸出聚類中心

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

本文選用 NDFCM算法[15]、AFCM算法[16]、HFCM算法[17]、CKGSA-FC算法[18]與本文算法進(jìn)行對(duì)比，從主觀評(píng)價(jià)和客觀評(píng)價(jià)對(duì)算法的效果進(jìn)行評(píng)估。

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

3.1 主觀評(píng)價(jià)

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

與其他幾種算法比較，本文算法對(duì)細(xì)節(jié)保持較好，也沒(méi)有出現(xiàn)過(guò)度分割，造成幾個(gè)分割區(qū)域混亂的情況；從圖3可以看出，分割的圖像整體效果比其他幾種算法分割效果好，各個(gè)分割區(qū)域一目了然，沒(méi)有出現(xiàn)區(qū)域重疊情況。

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

3.2 客觀評(píng)價(jià)

表1中，雖然本文算法在圖3(a)的分割圖DICE數(shù)據(jù)指標(biāo)并非是最優(yōu)的，但是在幾個(gè)圖號(hào)指標(biāo)比較上，綜合指標(biāo)性能最好。表2、表3中本文算法指標(biāo)均優(yōu)于其他算法，分割效果比較良好，較其他算法分割后的圖像細(xì)節(jié)保持完整，體現(xiàn)了本文算法的穩(wěn)定性。且本文算法更適合人眼視覺(jué)，能更直觀地體現(xiàn)分割效果。由總體指標(biāo)性能的結(jié)果顯示，本文算法優(yōu)于其他算法。

表1 圖像DICE指標(biāo)對(duì)比結(jié)果

表2 圖像PRI指標(biāo)結(jié)果對(duì)比

表3 圖像BDE指標(biāo)對(duì)比結(jié)果

4 結(jié) 語(yǔ)

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