基于改進樹種算法的模糊聚類圖像分割*

肖石林宣士斌溫金玉

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

0 引言

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

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

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

1 樹種算法

1.1 標準樹種算法

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

在樹種算法開始搜索時，利用式子(1)來隨機初始化樹木的位置，為優化問題產生可行解：

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

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

式中N是樹木的種群數量.

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

其中S i，j是第i棵樹上產生的第i顆種子的第j個元素，T i，j是第i棵樹上的第j個元素，B j是當前位置最好的樹上的第j個元素，T r，j是可行解中隨機生成的第r棵樹上的第j個元素，αi，j是進行迭代的步長因子，是一個隨機數，αi，j∈ (-1，1).

1.2 改進樹種算法

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

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

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

ITSA算法的主要步驟如下：

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

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

步驟3 選出最優解，并保留上一代最佳樹木位置，若生成的種子比上一代樹木位置更優，則用新生成樹木的位置替代當前位置.

步驟4 迭代過程中迭代次數少于最大迭代次數，則返回步驟2，否則迭代結束，輸出全局最優目標函數值.

1.3 性能比較

為了評價ITSA的有效性，我們從文獻[19-22]中選取了幾個測試函數，設置其維數等于50，因為高維測試函數可以反映出算法的優越性.

表1 測試函數Tab.1 Test function

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

實驗的每一步都是在 Windows 7 Intel Core i5，4G RAM環境下Matlab平臺上進行的.為了突出比較的公平性，每種算法分別在測試函數中獨立運行30次，并在最好值、最差值、平均值和標準差4個方面進行比較.最好值、最差值、平均值和標準差的表示分別用Best、Worst、Mean和Std來替代.排名的順序是以Std為標準.

從表2來看，針對單峰測試函數Sphere本文提出的ITSA算法實驗結果遠優于其他算法測試結果，但是從函數Resonbrock來說和灰狼算法測試結果相差不大.針對多峰測試函數Griewan來說，實驗結果排名第二，僅次于灰狼算法.但在其他兩個多峰測試函數上來看，本文提出的ITSA算法的實驗結果都是最優的.

表2 測試函數結果比較Tab.2 Comparison of test function results

2 改進樹種算法與模糊聚類圖像分割(ITSA_FCM)

2.1 FCM算法介紹

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

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

其中，u ij表示第i個樣本點屬于第j類的隸屬度，u ij∈ [0，1].

FCM算法的主要步驟如下：

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

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

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

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

2.2 改進樹種模糊聚類算法

改進的樹種優化算法能有效優化FCM容易陷入局部最優值的問題，還能克服原始樹種算法迭代尋優隨機性等問題.將改進的樹種優化算法和FCM相結合用于圖像分割不僅可以有效提高算法效率，加快最優解求解的同時，還能取得不錯的圖像分割效果.

評價每顆種子的生成價值，定義適應度函數：

其中，n為常數;J(U，A)為區域圖像中每個像素點的目標函數值之和，它的值越小，代表聚類效果越優異.因此，要想聚類效果好，則適應度函數f的值越大.種子的位置就是由每次迭代產生的聚類中心位置來更新，最終迭代結果的最優解就是最優樹種位置，也是最后的聚類中心.

改進樹種算法的模糊聚類圖像分割流程如下：

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

步驟2 對c個聚類中心進行隨機初始化，即初始化最原始樹木的位置，隨機生成一批樹.

步驟3 通過式(10)計算原始樹木適應度函數值，從而選出較優位置的樹木.

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

步驟5 將計算得到的新樹木適應度函數值與上代比較，若較好則更新樹木位置，否則不變.

步驟6 判斷算法迭代次數是否大于算法終止閾值，若到達算法終止閾值，則輸出最優樹木位置，否則返回步驟4繼續進行算法迭代.

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

3 實驗結果和分析

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

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

圖1 原始圖像Fig.1 Original image

圖2 Lena分割結果Fig.2 Split results of Lena

圖3 Cameraman分割結果Fig.3 Split results of Cameraman

圖4 Orangutan分割結果Fig.4 Split results of Orangutan

表3 計算效率比較Tab.3 Computational efficiency comparison

4 結語

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