基于改進(jìn)樹(shù)種算法的模糊聚類圖像分割*

肖石林宣士斌溫金玉

(廣西民族大學(xué) 信息科學(xué)與工程學(xué)院，廣西 南寧 530006)

0 引言

隨著科學(xué)技術(shù)的飛速發(fā)展，越來(lái)越龐大的信息數(shù)據(jù)量需要處理.其中圖像在信息數(shù)據(jù)處理過(guò)程中有著最直觀，信息量寬廣的特點(diǎn)，圖像信息在人類日常生活中接觸極多.但是面對(duì)龐大的圖像信息源，可能只有某一塊區(qū)域是人類所需要的，這就要求人類利用相關(guān)的圖像處理算法將一些區(qū)域分割開(kāi)來(lái)以便后續(xù)圖像研究.將一幅完整的圖像劃分為多個(gè)有意義的目標(biāo)區(qū)域的這類方法便被稱作為圖像分割.[1]一些常見(jiàn)的圖像分割算法有如下幾種：(1)閾值化分割[2]是圖像分割算法中較早出現(xiàn)的算法，在閾值分割算法中，難點(diǎn)和關(guān)鍵是閾值的選擇.閾值化分割算法的各種變形算法都是基于閾值的選取衍變而來(lái).其中直方圖方法、最大類間方差法、最大熵方法等在閾值化圖像分割中廣泛應(yīng)用.(2)基于區(qū)域的方法[3]假如在一個(gè)相鄰區(qū)域的像素在計(jì)算機(jī)視覺(jué)上有一些比較相似的特征，比如有灰度特征、紋理特征等.這種方法它主要是利用了圖像空間信息，那么所分割的圖像也是連續(xù)不間斷的，并且它不受圖像中分支數(shù)的約束，其中區(qū)域增長(zhǎng)，區(qū)域分割和區(qū)域合并算法在區(qū)域分割圖像方法中經(jīng)常被使用到.(3)在圖像分割領(lǐng)域中，聚類的分割算法主要分為硬聚類和軟聚類.軟聚類是模糊C-均值聚類算法(FCM)，[4]它在圖像分割領(lǐng)域的研究一直都是熱門，本文所要用的方法便是通過(guò)不停迭代隸屬度矩陣和簇中心以得到目標(biāo)函數(shù)最小值的模糊C-均值聚類(FCM)算法.

除此之外，最近幾年元啟發(fā)式算法[5]發(fā)展迅速，在國(guó)際學(xué)術(shù)界掀起了一種新的研究熱潮，引起了許多學(xué)者的高度關(guān)注.與一些傳統(tǒng)的優(yōu)化算法相互比較，元啟發(fā)式算法在解決復(fù)雜可以更直觀、更有效地解決復(fù)雜的實(shí)際問(wèn)題.它們的過(guò)程通常是先創(chuàng)建一組隨機(jī)解，然后使用設(shè)定的更新規(guī)則來(lái)優(yōu)化這組解，最后獲得最優(yōu)解.元啟發(fā)式算法是基于社會(huì)行為[6]和自然現(xiàn)象[7]產(chǎn)生的.比如，遺傳算法(GA)[8]是一種基于達(dá)爾文生物進(jìn)化理論的算法，最關(guān)鍵的搜索最優(yōu)解的過(guò)程是模擬生物進(jìn)化的過(guò)程.粒子群優(yōu)化(PSO)[9]是基于對(duì)鳥的社會(huì)行為和個(gè)體行為的研究，它要求候選解圍繞當(dāng)前個(gè)體的最優(yōu)位置和當(dāng)前種群的最佳位置進(jìn)行移動(dòng).重力搜索算法(GSA)[10]是一種基于萬(wàn)有引力定律和牛頓第二定律的所衍變出的種群優(yōu)化算法，它依賴于個(gè)體之間的引力相互作用去尋找最優(yōu)解.灰狼優(yōu)化算法(GWO)[11]是一種基于對(duì)灰狼捕食行為和等級(jí)制度的算法，優(yōu)化的目的是通過(guò)灰狼尋找獵物、包圍獵物、捕食獵物和攻擊獵物的過(guò)程來(lái)實(shí)現(xiàn)的.2015年，Mustafa Servet Kiran等人提出了一種新的叫作樹(shù)種優(yōu)化(TSA)[12]的元啟發(fā)式算法.在眾多的元啟發(fā)式算法中，樹(shù)種算法尋優(yōu)能力較GA、PSO等一些經(jīng)典傳統(tǒng)優(yōu)化算法更強(qiáng)，從而受到了學(xué)術(shù)界的廣泛關(guān)注.它是通過(guò)模擬自然界中樹(shù)木的繁殖方式來(lái)實(shí)現(xiàn)最優(yōu)函數(shù)值的尋找.首先在解空間內(nèi)隨機(jī)生產(chǎn)一批樹(shù)木，即一批解，然后在這一批樹(shù)木中挑出生產(chǎn)種子能力最強(qiáng)的一批解.這一批可行解便會(huì)接著隨機(jī)地產(chǎn)生新生種子，這些種子的生成方式有兩種：一種迭代方式側(cè)重全局搜索，另一種則是局部搜索，搜索趨勢(shì)常數(shù)ST決定著他們的迭代生成方式.最后，這些新產(chǎn)生的種子進(jìn)行再次尋優(yōu)迭代，直到產(chǎn)生一個(gè)最優(yōu)秀的解.

本文在標(biāo)準(zhǔn)樹(shù)種算法(TSA)的基礎(chǔ)上提出改進(jìn)樹(shù)種優(yōu)化算法(ITSA)，將判斷參數(shù)ST由固定值轉(zhuǎn)變成隨迭代次數(shù)逐漸增大的變量，并將步長(zhǎng)因子構(gòu)造非線性遞減函數(shù)，用以提高本文中TSA算法收斂的精度和速度，經(jīng)過(guò)這樣的調(diào)整后，使得TSA算法迭代初期側(cè)重點(diǎn)是全局搜索而在算法后期側(cè)重點(diǎn)是局部搜索，來(lái)解決模糊聚類中對(duì)初始聚類中心的求解過(guò)程中計(jì)算復(fù)雜，易陷于局部最優(yōu)等問(wèn)題.本文的后續(xù)部分是按如下方式進(jìn)行的，第2部分介紹樹(shù)種算法及改進(jìn)樹(shù)種算法并對(duì)其進(jìn)行算法測(cè)試.第3部分給出實(shí)驗(yàn)結(jié)果和數(shù)據(jù)分析.最后，第4部分進(jìn)行論文總結(jié).

1 樹(shù)種算法

1.1 標(biāo)準(zhǔn)樹(shù)種算法

樹(shù)種算法模擬自然界中樹(shù)木生成種子的衍變特點(diǎn)，從而被提出來(lái)成為一種新興元啟發(fā)式搜索算法，經(jīng)過(guò)初步的研究結(jié)果表明，該算法的尋優(yōu)能力優(yōu)異，有希望超過(guò)當(dāng)前諸如PSO(粒子群算法)、[13]ABC(人工蜂群算法)、[14]FA(螢火蟲算法)[15]等群體智能算法，該算法模擬大樹(shù)的繁殖方式來(lái)實(shí)現(xiàn)最優(yōu)值的尋找.首先在解空間內(nèi)隨機(jī)生產(chǎn)一批樹(shù)木，即一批解，然后在這一批樹(shù)木中挑出生產(chǎn)種子能力最強(qiáng)的一批樹(shù)木.這一批可行解便會(huì)接著隨機(jī)地產(chǎn)生新生種子，這些種子的生成方式有兩種：一種迭代方式側(cè)重全局搜索，另一種則是局部搜索，搜索趨勢(shì)常數(shù)ST決定著他們的迭代生成方式.最后，這些新產(chǎn)生的種子進(jìn)行再次尋優(yōu)迭代，直到產(chǎn)生一個(gè)最優(yōu)秀的解.

在樹(shù)種算法開(kāi)始搜索時(shí)，利用式子(1)來(lái)隨機(jī)初始化樹(shù)木的位置，為優(yōu)化問(wèn)題產(chǎn)生可行解：

式中L j，min是搜索空間的下界，H j，max是搜索空間的上界，r i，j是在每一維空間和位置上的一個(gè)隨機(jī)數(shù)，r i，j∈ (0，1).

并不是所有的樹(shù)產(chǎn)生種子的能力都是一樣的，根據(jù)測(cè)試表明，10%樹(shù)的種群數(shù)量產(chǎn)生的種子數(shù)量最低，25%樹(shù)的種群數(shù)產(chǎn)生的種子數(shù)量最高.所以生成了樹(shù)木之后，我們要對(duì)種群進(jìn)行優(yōu)化，利用式(2)選出最好位置的樹(shù)木：

式中N是樹(shù)木的種群數(shù)量.

在搜索解空間中生成了最好位置的樹(shù)木后，這一批樹(shù)木便會(huì)接著隨機(jī)地產(chǎn)生新生種子，這些種子的生成方式有兩種：一種迭代方式側(cè)重全局搜索，另一種則是局部搜索，搜索趨勢(shì)常數(shù)ST決定著他們的迭代生成方式：

其中S i，j是第i棵樹(shù)上產(chǎn)生的第i顆種子的第j個(gè)元素，T i，j是第i棵樹(shù)上的第j個(gè)元素，B j是當(dāng)前位置最好的樹(shù)上的第j個(gè)元素，T r，j是可行解中隨機(jī)生成的第r棵樹(shù)上的第j個(gè)元素，αi，j是進(jìn)行迭代的步長(zhǎng)因子，是一個(gè)隨機(jī)數(shù)，αi，j∈ (-1，1).

1.2 改進(jìn)樹(shù)種算法

在標(biāo)準(zhǔn)的樹(shù)種算法中，搜索趨勢(shì)常數(shù)ST通常為固定值，但是這個(gè)參數(shù)ST在樹(shù)種算法中又是一個(gè)很重要的參數(shù)，在算法迭代的過(guò)程中，如果ST一直較小，雖然它會(huì)加速算法的收斂，并且會(huì)有利于其全局優(yōu)化，但它可能無(wú)法獲得更高精度的最優(yōu)解.反之，如果ST一直較大，算法又會(huì)一直進(jìn)行局部尋優(yōu)，導(dǎo)致算法的時(shí)間復(fù)雜度明顯提高.步長(zhǎng)因子αi，j其大小和方向都是高度隨機(jī)的，這有益于進(jìn)行全局尋優(yōu)，很快就可以接近全局最優(yōu)解，但隨著TSA算法在進(jìn)行了多次迭代運(yùn)算后，后期的局部尋優(yōu)過(guò)程會(huì)因步長(zhǎng)因子跳躍性太強(qiáng)而得不到較精確的局部最優(yōu)解，從而導(dǎo)致后期收斂速率變慢.

通過(guò)對(duì)布谷鳥算法[16-17]和粒子群算法[18]以及其他智能算法的研究，本文針對(duì)樹(shù)種算法中搜索趨勢(shì)常數(shù)ST構(gòu)造了非線性遞增函數(shù)，以及對(duì)步長(zhǎng)因子αi，j構(gòu)造了非線性遞減函數(shù)：

其中，STmax和STmin為搜索趨勢(shì)常數(shù)ST的最大值和最小值，αmax和αmin為步長(zhǎng)因子αi，j的最大值和最小值，i和T分別表示當(dāng)前迭代次數(shù)和最大迭代次數(shù)，采用上面兩式，可以提高算法的收斂速度和精度，隨著算法的動(dòng)態(tài)變化而調(diào)整步長(zhǎng)因子和搜索趨勢(shì)常數(shù)，改進(jìn)后的樹(shù)種算法(ITSA算法)迭代初期更傾向于全局尋優(yōu)，而迭代后期利用全局最優(yōu)解進(jìn)行局部尋優(yōu).

ITSA算法的主要步驟如下：

步驟1 設(shè)置種群數(shù)N，搜索趨勢(shì)常數(shù)的最大值STmax和最小值STmin，步長(zhǎng)因子的最大值αmax和最小值αmin，問(wèn)題維數(shù)D，用式子(1)生成一些隨機(jī)樹(shù)，為優(yōu)化問(wèn)題挑選適應(yīng)度函數(shù)，再利用式子(2)在這些隨機(jī)樹(shù)中選擇最優(yōu)解.

步驟2 利用位置較優(yōu)的樹(shù)木生成種子完成迭代過(guò)程，此過(guò)程中利用式子(3)和式子(4)對(duì)這些位置較優(yōu)的樹(shù)進(jìn)行選擇迭代，若rand＞STi，則用式子(3)進(jìn)行全局尋優(yōu)，若rand＜STi，則用式子(4)進(jìn)行局部尋優(yōu).

步驟3 選出最優(yōu)解，并保留上一代最佳樹(shù)木位置，若生成的種子比上一代樹(shù)木位置更優(yōu)，則用新生成樹(shù)木的位置替代當(dāng)前位置.

步驟4 迭代過(guò)程中迭代次數(shù)少于最大迭代次數(shù)，則返回步驟2，否則迭代結(jié)束，輸出全局最優(yōu)目標(biāo)函數(shù)值.

1.3 性能比較

為了評(píng)價(jià)ITSA的有效性，我們從文獻(xiàn)[19-22]中選取了幾個(gè)測(cè)試函數(shù)，設(shè)置其維數(shù)等于50，因?yàn)楦呔S測(cè)試函數(shù)可以反映出算法的優(yōu)越性.

表1 測(cè)試函數(shù)Tab.1 Test function

本文選取了主流算法中的5種算法來(lái)和ITSA作比較，它們分別是ABC，[14]GSA，[10]PSO，[9]GWO，[11]TSA.[12]各算法的參數(shù)設(shè)置如下：

實(shí)驗(yàn)的每一步都是在 Windows 7 Intel Core i5，4G RAM環(huán)境下Matlab平臺(tái)上進(jìn)行的.為了突出比較的公平性，每種算法分別在測(cè)試函數(shù)中獨(dú)立運(yùn)行30次，并在最好值、最差值、平均值和標(biāo)準(zhǔn)差4個(gè)方面進(jìn)行比較.最好值、最差值、平均值和標(biāo)準(zhǔn)差的表示分別用Best、Worst、Mean和Std來(lái)替代.排名的順序是以Std為標(biāo)準(zhǔn).

從表2來(lái)看，針對(duì)單峰測(cè)試函數(shù)Sphere本文提出的ITSA算法實(shí)驗(yàn)結(jié)果遠(yuǎn)優(yōu)于其他算法測(cè)試結(jié)果，但是從函數(shù)Resonbrock來(lái)說(shuō)和灰狼算法測(cè)試結(jié)果相差不大.針對(duì)多峰測(cè)試函數(shù)Griewan來(lái)說(shuō)，實(shí)驗(yàn)結(jié)果排名第二，僅次于灰狼算法.但在其他兩個(gè)多峰測(cè)試函數(shù)上來(lái)看，本文提出的ITSA算法的實(shí)驗(yàn)結(jié)果都是最優(yōu)的.

表2 測(cè)試函數(shù)結(jié)果比較Tab.2 Comparison of test function results

2 改進(jìn)樹(shù)種算法與模糊聚類圖像分割(ITSA_FCM)

2.1 FCM算法介紹

模糊C-均值聚類(FCM)算法是通過(guò)不停迭代隸屬度矩陣和簇中心以得到目標(biāo)函數(shù)最小值的過(guò)程，在進(jìn)行圖像分割的時(shí)候它是根據(jù)像素以及聚類中心的加權(quán)相似性對(duì)目標(biāo)函數(shù)不斷的進(jìn)行迭代優(yōu)化以便尋找最優(yōu)解.設(shè)有n個(gè)數(shù)據(jù)樣本為X={x1，x2，…，x n}，c(2≤c≤n)是要將數(shù)據(jù)樣本分成的類別的數(shù)目，A={A1，A2，…，A C}表示相應(yīng)的c個(gè)類別，U是相似度矩陣，各類別的聚類中心為{v1，v2，…，v c}.根據(jù)以上定義，F(xiàn)CM的目標(biāo)函數(shù)為：

通過(guò)對(duì)式(1)引入拉格朗日乘子，更新隸屬度矩陣和聚類中心：

其中，u ij表示第i個(gè)樣本點(diǎn)屬于第j類的隸屬度，u ij∈ [0，1].

FCM算法的主要步驟如下：

步驟1 確定初始的聚類類別數(shù)c和模糊指數(shù)b，定義條件終止參數(shù)ε，以及初始化隸屬度矩陣U.

步驟2 通過(guò)式(2)和式(3)更新每次迭代后的隸屬度矩陣U和聚類中心A的值.

步驟3 如果‖U(t)-U(t-1)‖＜ε，則此算法結(jié)束，如果沒(méi)有大于條件終止參數(shù)所定義的值，則返回步驟2，繼續(xù)完成迭代過(guò)程.

FCM算法在圖像分割領(lǐng)域雖廣泛應(yīng)用但還存在一些問(wèn)題，它很難選取算法初始迭代中心，而且在迭代后期容易陷入局部最優(yōu)解.

2.2 改進(jìn)樹(shù)種模糊聚類算法

改進(jìn)的樹(shù)種優(yōu)化算法能有效優(yōu)化FCM容易陷入局部最優(yōu)值的問(wèn)題，還能克服原始樹(shù)種算法迭代尋優(yōu)隨機(jī)性等問(wèn)題.將改進(jìn)的樹(shù)種優(yōu)化算法和FCM相結(jié)合用于圖像分割不僅可以有效提高算法效率，加快最優(yōu)解求解的同時(shí)，還能取得不錯(cuò)的圖像分割效果.

評(píng)價(jià)每顆種子的生成價(jià)值，定義適應(yīng)度函數(shù)：

其中，n為常數(shù);J(U，A)為區(qū)域圖像中每個(gè)像素點(diǎn)的目標(biāo)函數(shù)值之和，它的值越小，代表聚類效果越優(yōu)異.因此，要想聚類效果好，則適應(yīng)度函數(shù)f的值越大.種子的位置就是由每次迭代產(chǎn)生的聚類中心位置來(lái)更新，最終迭代結(jié)果的最優(yōu)解就是最優(yōu)樹(shù)種位置，也是最后的聚類中心.

改進(jìn)樹(shù)種算法的模糊聚類圖像分割流程如下：

步驟1 參數(shù)初始化.包括樹(shù)木種群規(guī)模定義為N，搜索維度定義為D，搜索趨勢(shì)常數(shù)ST設(shè)置最小值STmin和最大值STmax.算法的最大迭代次數(shù)定義為T，聚類中心類別數(shù)目定義為c，模糊指數(shù)定義為b等.

步驟2 對(duì)c個(gè)聚類中心進(jìn)行隨機(jī)初始化，即初始化最原始樹(shù)木的位置，隨機(jī)生成一批樹(shù).

步驟3 通過(guò)式(10)計(jì)算原始樹(shù)木適應(yīng)度函數(shù)值，從而選出較優(yōu)位置的樹(shù)木.

步驟4 根據(jù)式(3)或式(4)用種子更新上一代的樹(shù)木位置，得到新樹(shù)木的適應(yīng)度函數(shù)值.

步驟5 將計(jì)算得到的新樹(shù)木適應(yīng)度函數(shù)值與上代比較，若較好則更新樹(shù)木位置，否則不變.

步驟6 判斷算法迭代次數(shù)是否大于算法終止閾值，若到達(dá)算法終止閾值，則輸出最優(yōu)樹(shù)木位置，否則返回步驟4繼續(xù)進(jìn)行算法迭代.

步驟7 得到最優(yōu)樹(shù)種位置，即最終聚類中心后，根據(jù)式(8)和式(9)分別計(jì)算隸屬度矩陣和聚類中心，輸出分割結(jié)果.

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

本文將ITSA_FCM算法和PSO_FCM[23]算法對(duì)圖像分割結(jié)果進(jìn)行比較分析.在參數(shù)設(shè)置方面，聚類類別數(shù)設(shè)置為8，最大迭代次數(shù)設(shè)為50，STmax=0.5，STmin=0.1.在ITSA_FCM中，搜索趨勢(shì)常數(shù)ST異常重要，它決定著迭代的進(jìn)行方式，是進(jìn)行全局尋優(yōu)還是局部尋優(yōu).在算法迭代前期，ST取較小值，容易進(jìn)行全局尋優(yōu)，隨著算法越來(lái)越接近全局最優(yōu)解，ST值也趨向最大值，方便進(jìn)行局部尋優(yōu).為驗(yàn)證算法的分割效果，本文在 Windows 7 Intel Core i5，4G RAM環(huán)境下Matlab平臺(tái)上采用三個(gè)公開(kāi)的標(biāo)準(zhǔn)測(cè)試圖像Lena、Cameraman、Orangutan，以式子(10)為實(shí)驗(yàn)的適應(yīng)度函數(shù).

根據(jù)本文方法進(jìn)行實(shí)驗(yàn)，待分割原始圖像如圖1(a)，(b)，(c)所示，圖(2)及圖(3)圖(4)中(a)，(b)，(c)，(d)分別表示使用 FCM、PSO_FCM、TSA_FCM、ITSA_FCM這3種分割算法所得到的分割結(jié)果.從分割結(jié)果上看，原始FCM方法均出現(xiàn)了一些過(guò)分割的現(xiàn)象，分割效果不如后三者理想，而PSO_FCM方法與TSA_FCM分割方法在效果上差異不大，都比原始FCM方法更優(yōu)且都比本文提出的ITSA_FCM效果差一點(diǎn).例如，圖(2)Lena用ITSA_FCM方法分割之后，頭發(fā)和面部細(xì)節(jié)更清晰，圖(4)Orangutan的眼部分割效果更好，輪廓更明顯.接下來(lái)比較分割效率，計(jì)算以上幾種算法的平均計(jì)算用時(shí)，分割效率結(jié)果見(jiàn)表3，從表3可以看出來(lái)，和FCM，PSO_FCM及TSA_FCM分割方法相比較，本文所提出的ITSA_FCM尋優(yōu)方法可以更快地找到初始聚類中心，完成圖像分割.

圖1 原始圖像Fig.1 Original image

圖2 Lena分割結(jié)果Fig.2 Split results of Lena

圖3 Cameraman分割結(jié)果Fig.3 Split results of Cameraman

圖4 Orangutan分割結(jié)果Fig.4 Split results of Orangutan

表3 計(jì)算效率比較Tab.3 Computational efficiency comparison

4 結(jié)語(yǔ)

本文在標(biāo)準(zhǔn)樹(shù)種算法(TSA)的基礎(chǔ)上提出改進(jìn)的樹(shù)種優(yōu)化算法(ITSA)，將判斷參數(shù)ST由固定值轉(zhuǎn)變成隨迭代次數(shù)逐漸增大的變量，并將步長(zhǎng)因子構(gòu)造一個(gè)非線性遞減函數(shù)，用以提高本文中TSA算法收斂的精度和速度，經(jīng)過(guò)如此調(diào)整后，使得TSA算法迭代初期側(cè)重點(diǎn)是全局搜索而在算法后期側(cè)重點(diǎn)是局部搜索.針對(duì)傳統(tǒng)的FCM容易陷入局部最優(yōu)值和其初始聚類中心計(jì)算復(fù)雜等這些缺點(diǎn)，將改進(jìn)的樹(shù)種優(yōu)化算法引入到FCM中.通過(guò)實(shí)驗(yàn)表明，ITSA_FCM算法不僅在圖像分割效果上優(yōu)于傳統(tǒng)FCM，在算法運(yùn)行時(shí)間上也明顯優(yōu)于傳統(tǒng)FCM.