改進(jìn)TLBO 優(yōu)化人工魚群算法實(shí)現(xiàn)FCM 圖像分割

賀風(fēng)婷，劉彥隆，劉鑫晶

（太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院，山西晉中 030600）

海量的圖片是計(jì)算機(jī)與外部世界溝通的橋梁，圖像分割作為圖像處理的第一步，也是最為重要的一步，是之后圖像處理的基礎(chǔ)，分割效果的好壞決定了后續(xù)步驟的質(zhì)量。圖像分割本質(zhì)上是將像素進(jìn)行分類，將具有相似特征的像素劃分到一類，具有差異性的像素則被劃分到不同類別[1]。FCM 算法是一種常用的聚類方法，由Dunn 首先提出，是對早期K 均值聚類算法的一種改進(jìn)，其由于簡單有效的特點(diǎn)得到了廣泛的使用[2]。

近幾年來，針對FCM 算法對初始聚類中心較為敏感的問題，許多群智能優(yōu)化算法被應(yīng)用于確定FCM 算法的聚類中心。其中，人工魚群算法（AFSA）具備優(yōu)秀的全局尋優(yōu)性能，同時(shí)對初始參數(shù)的要求較低，魯棒性較強(qiáng)[3]。研究學(xué)者針對人工魚群算法做出了很多改進(jìn)，文獻(xiàn)[4]將通信行為引入人工魚群算法中，并與FCM 算法進(jìn)行結(jié)合；文獻(xiàn)[5]利用最速下降法對公告板中適應(yīng)度最好的人工魚進(jìn)行更新，提高了算法的收斂速度；文獻(xiàn)[6]將反向?qū)W習(xí)機(jī)制引入到人工魚群算法中，避免了算法的早熟；文獻(xiàn)[7]利用體能變換模型確定算法搜索過程中的步長，使得算法的尋優(yōu)精度得以提高；文獻(xiàn)[8]為了防止算法陷入局部最優(yōu)，在人工魚的行為中加入了游動行為；文獻(xiàn)[9]將跳躍行為加入到工魚群算法中，以改善算法后期易陷入局部最優(yōu)解的缺陷。雖然國內(nèi)外學(xué)者針對標(biāo)準(zhǔn)AFSA 算法進(jìn)行了不同程度的改進(jìn)，并且用于各個(gè)領(lǐng)域的研究，但仍存在不足。

為了更好地改進(jìn)標(biāo)準(zhǔn)AFSA 算法存在的后期尋優(yōu)效果較差以及FCM 算法對初始聚類中心敏感導(dǎo)致的圖像分割速率和精度較低的問題，文中提出了基于改進(jìn)教學(xué)優(yōu)化的人工魚群算法（ITLBO-AFSA）實(shí)現(xiàn)FCM 圖像分割的方法。算法利用AFSA 較強(qiáng)的全局搜索能力，同時(shí)將改進(jìn)之后的教學(xué)優(yōu)化算法（TLBO）融入尋優(yōu)過程，充分利用人工魚群算法尋優(yōu)過程中每一次的最優(yōu)值，進(jìn)行正向引導(dǎo)。通過仿真實(shí)驗(yàn)數(shù)據(jù)證明，將優(yōu)化后的算法應(yīng)用于尋找FCM 算法的聚類中心，算法容易跳出局部極值，圖像分割的速度和精確度均有較明顯的提升。

1 優(yōu)化的人工魚群算法

1.1 基本的人工魚群算法

基本的人工魚群算法（AFSA）[10]是模仿魚類尋找食物過程中的各種行為特點(diǎn)而提出的一種動物體的智能全局優(yōu)化算法。用向量X={x1,x2,x3…xn}表示人工魚個(gè)體的狀態(tài)，每條人工魚代表了問題的一個(gè)解，食物濃度則代表了目標(biāo)函數(shù)的值，為Y=f(X)，算法通過不斷地進(jìn)行行為選擇來執(zhí)行魚群的基本行為，通過更新人工魚的位置來找到食物濃度最高的地方，尋得最優(yōu)解。魚群的基本行為有以下4 種：

1）聚群行為：人工魚根據(jù)所確定的視野范圍搜索此范圍內(nèi)的所有人工魚，令所有人工魚的數(shù)目為s，其中心位置表示為Xc，如果Yc＞Yi并且s/N＜δ，說明Xc處的食物濃度較高并且擁擠度較低，則人工魚按照下式向Xc前進(jìn)一步：

否則執(zhí)行覓食行為。

2）追尾行為：人工魚根據(jù)所確定的視野范圍，搜索此范圍內(nèi)食物濃度最高的位置Xh，鄰域內(nèi)所有人工魚的數(shù)目為s，如果探測到s/N＜δ，則人工魚按照下式向Xh前進(jìn)一步：

否則執(zhí)行覓食行為。

3）覓食行為：人工魚根據(jù)確定的視野范圍隨機(jī)搜索一個(gè)位置Xj，如果Yj＞Yi，則說明Xj處的食物濃度比當(dāng)前位置Xi處的更高，則人工魚按照下式向Xj前進(jìn)一步：

否則執(zhí)行隨機(jī)行為。

4）隨機(jī)行為：如果人工魚在覓食行為進(jìn)行了try_number次之后，在視野范圍內(nèi)還是沒有發(fā)現(xiàn)食物濃度更高的位置，則按照下式隨機(jī)移動一步，以免解陷入局部最優(yōu)：

5）公告板：用來記錄人工魚群的最優(yōu)解，包括食物濃度及位置，它是一個(gè)根據(jù)人工魚行為動態(tài)變化的值。

1.2 AFSA的改進(jìn)

1.2.1 自適應(yīng)確定視野和步長的值

在基本的AFSA 中，visual和step的值均為固定的值。如果初始化的visual值過大，那么在人工魚群算法的前期可以提高收斂速度，但是在后期，逐漸逼近最優(yōu)解，這時(shí)過大的visual值會導(dǎo)致算法錯過最優(yōu)解，得到的僅僅是局部最優(yōu)解，反之，如果初始化的visual值過小，則收斂速度過慢，效率下降。如果步長較大，則在算法初期，人工魚的聚集速度很快，但是在后期，較大的步長將會使人工魚很難精確地到達(dá)極值點(diǎn)，從而產(chǎn)生振蕩現(xiàn)象，而此時(shí)較小的步長會獲得更加精確的極值。如果采用隨機(jī)值，則將會增加計(jì)算的時(shí)間。所以文中采用自適應(yīng)視野和步長的策略[11]，具體的視野和步長取決于人工魚當(dāng)前的位置和距最優(yōu)人工魚位置的距離，方法如下：

每進(jìn)行一次迭代之前，每條人工魚都要計(jì)算自身Xi與公告板中保存的最優(yōu)個(gè)體Xm的距離，并將這個(gè)距離值作為其視野，而步長通過聯(lián)合系數(shù)a(0＜a≤1)和視野聯(lián)系起來，即

因此，視野和步長不再是一個(gè)固定不變的值，而是會隨著最優(yōu)個(gè)體的改變而不斷地進(jìn)行更新，從而避免盲目尋找。隨著算法的進(jìn)行，選擇合適的視野和步長值，從而改善算法的整體性能。

1.2.2 引入改進(jìn)的教學(xué)優(yōu)化算法

雖然AFSA 算法超初收斂速度快，效果較好，但是當(dāng)算法進(jìn)行到后期時(shí)，如果繼續(xù)在全局范圍內(nèi)盲目搜索，將會導(dǎo)致時(shí)間的浪費(fèi)，而如果充分利用公告板中所保存的歷史解[12]，對其余人工魚個(gè)體的尋優(yōu)過程進(jìn)行正向指引，則會加快尋優(yōu)速度。

基本的教學(xué)優(yōu)化算法[13]主要包括教師教學(xué)和學(xué)生交流兩個(gè)階段，整個(gè)人工魚群是一個(gè)“班級”，公告板上記錄的個(gè)體是班級中的“教師”，為當(dāng)前最優(yōu)個(gè)體，每個(gè)人工魚除自身以外的個(gè)體都看作是“學(xué)生”。具體實(shí)現(xiàn)如下：

1）自適應(yīng)教學(xué)因子的教學(xué)過程

教師通過不斷地向?qū)W生傳授知識，提高學(xué)生的整體水平。經(jīng)過教學(xué)過程產(chǎn)生的解為：

在基本的教學(xué)算法中，教學(xué)因子TF隨機(jī)取值為1 或2，這就導(dǎo)致了學(xué)生學(xué)習(xí)過程中要么不向老師汲取知識，要么汲取全部知識，所以令

其中，Xinew為經(jīng)過教學(xué)過程后人工魚Xi的新位置，rand 為[0,1]的隨機(jī)數(shù)，Xm為公告板上的最優(yōu)人工魚個(gè)體位置，i為當(dāng)前的迭代次數(shù)。從式（7）可看出，隨著迭代次數(shù)的增加，TF的值從2 逐漸減小，直到最后減為0，這符合前期學(xué)生與教師之間水平差距較大，學(xué)習(xí)能力較強(qiáng)，后期掌握的知識逐漸增多，學(xué)習(xí)能力減弱的客觀事實(shí)。經(jīng)過教學(xué)過程后，如果Yinew＜Yi，則將人工魚位置更新為Xinew，否則不更新。

2）基于差分進(jìn)化的交流過程

在人工魚群算法的前期，學(xué)生之間可以相互交流，此時(shí)充分利用人工魚個(gè)體的多樣性，可以進(jìn)一步提升尋優(yōu)結(jié)果的全局性。在基本的教學(xué)算法中，交流過程只與兩個(gè)學(xué)生有關(guān)，在改進(jìn)后的交流過程中，學(xué)生之間不僅可以內(nèi)部交流，同時(shí)也可以和教師進(jìn)行交流，經(jīng)過此過程所得到的解為：

其中，Xinew為經(jīng)過交流過程后人工魚Xi的新位置，Xm為公告板上的最優(yōu)人工魚個(gè)體位置，Xa、Xb為當(dāng)前迭代次數(shù)中不同于Xi的兩個(gè)互異的學(xué)生。經(jīng)過交流過程后，如果Yinew＜Yi，則將人工魚位置更新為Xinew，否則不更新。

2 混合優(yōu)化算法用于FCM圖像分割

2.1 基本的FCM算法

假設(shè)一個(gè)數(shù)據(jù)集中有n個(gè)元素，用X={x1,x2,x3…xn}表示，如果把這些元素分為c類，則會有c個(gè)聚類中心[14]，每個(gè)類對應(yīng)的類中心為Vi(1＜i≤c)，數(shù)據(jù)集中的每個(gè)樣本xi屬于每一類別j的隸屬度為uij，F(xiàn)CM 的目標(biāo)函數(shù)定義如下：

利用拉格朗日乘數(shù)法得到以下兩個(gè)方程：

可以發(fā)現(xiàn)，uij和Vi屬于相互包含、相互影響的關(guān)系，F(xiàn)CM 算法就是不斷地對隸屬度uij和聚類中心Vi進(jìn)行調(diào)整，迭代之后使目標(biāo)函數(shù)的值最小，最終求解最優(yōu)值的過程。

FCM 算法的具體步驟如下：

1）初始化模糊指數(shù)m、聚類個(gè)數(shù)c、最大迭代次數(shù)T、迭代停止閾值ε等參數(shù)以及隸屬度矩陣U；

2）根據(jù)式（10）計(jì)算聚類中心Vi；

3）根據(jù)式（11）更新隸屬度uij；

4）重復(fù)步驟2）、3），直到達(dá)到最大迭代次數(shù)或者收斂閾值ε。

2.2 文中算法具體步驟

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

圖1 文中算法流程圖

步驟1 初始化參數(shù)：初始化人工魚群數(shù)目N、覓食行為的試探次數(shù)try_number、最大迭代次數(shù)max_inter、擁擠度因子δ、最大停滯次數(shù)Tm等各項(xiàng)參數(shù)；

步驟2 更新公告板：在該算法中，人工魚個(gè)體的適應(yīng)度值即為FCM 聚類算法的目標(biāo)函數(shù)，根據(jù)式（9）計(jì)算每個(gè)人工魚個(gè)體的適應(yīng)度值，在公告板上保存最優(yōu)個(gè)體的信息；

步驟3 計(jì)算視野和步長：計(jì)算每條人工魚與公告板中記錄的人工魚個(gè)體的距離，將其作為visual值，并根據(jù)式（1）計(jì)算出相應(yīng)的step值；

步驟4 更新人工魚個(gè)體的位置：按照式（1）～（4）執(zhí)行人工魚群的4 種基本行為，更新人工魚個(gè)體的位置，得到更新后的人工魚；

步驟5 交流過程：根據(jù)式（8），每條人工魚分別執(zhí)行交流過程得到Xinew，如果Yinew＜Yi，則更新人工魚的位置為Xinew，否則不更新，再與公告板中的狀態(tài)進(jìn)行比較，如果Yinew＜Ym，則更新公告板，否則不更新；

步驟6 檢查公告板：如果公告板沒有更新，則T=T+1，判斷是否T=Tm，如果成立，則轉(zhuǎn)到步驟8，否則轉(zhuǎn)到步驟7，如果公告板更新，則T=0；

步驟7 教學(xué)過程：利用公告板中記錄的最優(yōu)人工魚對每條人工魚個(gè)體執(zhí)行教學(xué)過程，得到Xinew，如果Yinew＜Ym，則更新公告板，否則不更新；

步驟8 判斷是否結(jié)束迭代：如果當(dāng)前迭代次數(shù)i＜max_inter，則迭代次數(shù)i=i+1，轉(zhuǎn)到步驟3，否則轉(zhuǎn)到步驟9；

步驟9 輸出尋優(yōu)結(jié)果，即為聚類中心；

步驟10 根據(jù)尋優(yōu)結(jié)果進(jìn)行FCM 圖像分割。

3 仿真實(shí)驗(yàn)與結(jié)果

為了驗(yàn)證提出算法的有效性，文中選取了MatlabR2015b 中的5 張典型圖片（rice、circuit、tire、cameraman 和mri），將改進(jìn)后的算法用于圖像分割，進(jìn)行了5 次實(shí)驗(yàn)，并將文中算法與傳統(tǒng)FCM 算法和人工魚優(yōu)化FCM 算法（AFSA_FCM）進(jìn)行圖像分割的分割效果進(jìn)行對比，5 次實(shí)驗(yàn)的結(jié)果分別如圖2～6所示。

圖2 rice圖像運(yùn)行結(jié)果

文中的實(shí)驗(yàn)環(huán)境為2.2G CPU，4GB RAM，Windows10.0 操作系統(tǒng)。實(shí)驗(yàn)所使用的工具是MatlabR2015b。實(shí)驗(yàn)中的相關(guān)參數(shù)設(shè)置如下：人工魚數(shù)目N=20，覓食行為的試探次數(shù)try_number=3，最大迭代次數(shù)max_inter=100，最大停滯次數(shù)Tm=10，擁擠度因子σ=0.618，視野和步長的相關(guān)系數(shù)a=0.5，迭代停止閾值ε=10-3。

圖3 circuit圖像運(yùn)行結(jié)果

圖4 tire圖像運(yùn)行結(jié)果

圖5 cameraman圖像運(yùn)行結(jié)果

圖6 mri圖像運(yùn)行結(jié)果

首先，從分割效果圖上來看，針對實(shí)驗(yàn)1，文中算法的分割過程減少了無關(guān)信息的干擾，得到了較為清晰的分割結(jié)果；針對實(shí)驗(yàn)2，文中算法分割出了較為清晰的線路紋路；針對實(shí)驗(yàn)3，文中算法將輪胎邊緣的線條保留得較為完整細(xì)致，更接近原始圖像；針對實(shí)驗(yàn)4，文中算法將cameraman 圖像中人物的衣服、臉部、手部分割得較為清楚，更加注重細(xì)節(jié)的體現(xiàn)；針對實(shí)驗(yàn)5，文中算法分割的核磁共振圖像保留了較多的細(xì)節(jié)信息，分割線條更加清晰，具有一定的現(xiàn)實(shí)意義。

其次，為了驗(yàn)證文中算法的收斂速度優(yōu)于其他兩種算法，將3 種算法的迭代次數(shù)和運(yùn)行時(shí)間進(jìn)行對比，結(jié)果如表1 所示。從表1 數(shù)據(jù)可以看出，與標(biāo)準(zhǔn)的FCM 算法進(jìn)行比較，文中算法的迭代次數(shù)明顯減少，原因就在于提出的算法利用改進(jìn)的人工魚群算法，同時(shí)在算法后期提高了魚群的收斂速度，對FCM算法進(jìn)行優(yōu)化，提高了整體的運(yùn)行速度，平均運(yùn)行時(shí)間下降了50%～55%，與AFSA_FCM 算法相比，運(yùn)行時(shí)間也下降了15%～30%，圖像分割的速率大幅提升。

表1 3種算法迭代次數(shù)和運(yùn)行時(shí)間對比

最后，為了對文中算法的收斂精度進(jìn)行說明，選取了評價(jià)聚類分割效果常用的兩種指標(biāo)Vpc和Vpe以及對圖像分割效果進(jìn)行評價(jià)的評價(jià)準(zhǔn)則分類正確率SA，對3 種算法進(jìn)行了對比：

1）Bezdek 劃分系數(shù)Vpc[15]，定義為：

2）劃分熵Vpe[16]，定義為：

3）分類正確率SA定義為：

其中，正確率SA越高，說明分割效果越好。Vpc和Vpe反映了分割矩陣的模糊程度。一般來說，如果目標(biāo)圖像中的每個(gè)像素點(diǎn)屬于其中一類的隸屬度值越大，屬于其他類的隸屬度值越小，說明聚類算法的效果越好，則Vpc的值越大，而Vpe的值越小。

各個(gè)實(shí)驗(yàn)圖像的指標(biāo)如表2 所示。劃分系數(shù)Vpc的值越接近1，說明聚類的程度越強(qiáng)，劃分熵Vpe的值越接近于0，說明聚類的結(jié)構(gòu)越清晰。從表2 的數(shù)據(jù)可以看出，文中算法的Vpc值比標(biāo)準(zhǔn)FCM 算法分割圖像提升了7%左右，而Vpe值下降了57%左右，與AFSA_FCM 算法相比，Vpc值提升了3%左右，Vpe值下降了10%左右。同時(shí)，文中算法比標(biāo)準(zhǔn)FCM 算法的圖像分割正確率平均提升了10%，比AFSA_FCM 算法平均提升了7%。因此，綜合看來，文中算法相對于其他兩種算法，顯然聚類效果更優(yōu)。

表2 3種算法的聚類有效性指標(biāo)和正確率對比

為了進(jìn)一步體現(xiàn)文中算法的優(yōu)越性，再次從目標(biāo)函數(shù)值變化的方面對3 種算法的速度與精度進(jìn)行說明。圖7 為對cameraman 圖像進(jìn)行分割時(shí)目標(biāo)函數(shù)值隨迭代次數(shù)的變化曲線，從圖7 可看出，提出的算法在剛開始時(shí)就能得到一個(gè)比較小的目標(biāo)函數(shù)值，與標(biāo)準(zhǔn)FCM 算法和AFSA_FCM 算法相比，收斂速度更快，并且從最終結(jié)果來看，目標(biāo)函數(shù)值最小，避免算法陷入局部最優(yōu)值，聚類效果更好[17-19]。

圖7 對cameraman圖像進(jìn)行分割時(shí)目標(biāo)函數(shù)值隨迭代次數(shù)的變化曲線

綜上所述，提出的基于ITLBO-AFSA 算法實(shí)現(xiàn)FCM 圖像分割的方法，在保證分割效果提升的同時(shí)，能夠快速地對圖像進(jìn)行分割，滿足了圖像分割的實(shí)時(shí)性要求，尤其是對復(fù)雜圖像的分割，相比于其他兩種算法，更能體現(xiàn)出其優(yōu)勢。

4 結(jié)束語

文中提出了一種基于改進(jìn)教學(xué)算法優(yōu)化人工魚算法（ITLBO-AFSA）進(jìn)行FCM 圖像分割的方法，通過改進(jìn)AFSA 算法尋優(yōu)過程中后期搜索速度較慢的缺陷，得到更精確的最優(yōu)解，將其作為FCM 的聚類中心，改進(jìn)了FCM 算法對初始聚類中心較為敏感的不足，提高了FCM 算法分割圖像的準(zhǔn)確度和速率。同時(shí)，通過觀察Vpc、Vpe、正確率和運(yùn)行時(shí)間等數(shù)據(jù)，直觀地表明了文中算法的可行性，該方法已經(jīng)應(yīng)用于各類型的分割圖像，如簡單圖像（rice 圖）、人物圖像（cameraman 圖）、醫(yī)學(xué)圖像（mri 圖）、生活圖像（tire圖、circuit 圖），具有現(xiàn)實(shí)意義。但是，如何降低噪聲的影響，將是未來的一個(gè)研究方向。