蛙跳結(jié)合模糊C-均值的圖像分割算法

顧英杰， 賈振紅， 覃錫忠， 楊 杰， 龐韶寧

（①新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046；②上海交通大學(xué) 圖像處理與模式識(shí)別研究所, 上海 200240；③新西蘭奧克蘭理工大學(xué) 知識(shí)工程與開(kāi)發(fā)研究所，新西蘭 奧克蘭1020）

0 引言

現(xiàn)代人類(lèi)接收的信息中，有80%來(lái)自視覺(jué)，或者說(shuō)為圖像信息，但是大多數(shù)人并不是對(duì)整幅圖像感興趣，而是對(duì)圖像中的一部分感興趣，所以圖像分割技術(shù)已經(jīng)成為了研究熱點(diǎn)。現(xiàn)在，人們常用的圖像分割方法有K均值聚類(lèi)、模糊C均值聚類(lèi)(FCM)、ISODATA等[1-3]。其中 FCM是比較常用的方法，但是FCM算法是一種局部搜索優(yōu)化算法，如果初始值選擇不當(dāng)，它就會(huì)收斂到局部極小點(diǎn)上，這對(duì)聚類(lèi)效果會(huì)產(chǎn)生較大的影響[4-5]。為了克服這種缺陷，近期有文獻(xiàn)提出用FPSO與FCM結(jié)合的方法對(duì)圖像進(jìn)行分割[6-7]，其分割效果優(yōu)于遺傳算法和OTSU算法。為了進(jìn)一步提高圖像分割的效果和效率，文中首次將混合蛙跳算法與模糊C-均值算法相結(jié)合。實(shí)驗(yàn)表明，該方法具有搜索全局最優(yōu)解的能力，可以有效地克服FCM對(duì)于初始值選擇的敏感性，分割效果好。

1 混合蛙跳算法的模型概述

1.1 基本概念

隨機(jī)生成F只青蛙組成初始群體，第i只青蛙表示問(wèn)題的解為Xi=(xi1,xi2,…,xis)，其中s表示變量的個(gè)數(shù)即解空間的維數(shù)。在生成初始群體之后，根據(jù)式（1）計(jì)算青蛙個(gè)體的適應(yīng)度f(wàn)(xi)：

將種群內(nèi)青蛙個(gè)體按適應(yīng)度降序排列，然后將整個(gè)青蛙群體分成m個(gè)子群,每個(gè)子群包含n只青蛙,滿足關(guān)系F=m×n。其中第1只青蛙分入第1子群，第2只青蛙分入第2子群，第m只青蛙分入第m子群，第m+1只青蛙分入第1子群，第m+2只青蛙分入第2子群，以此類(lèi)推，直到全部青蛙分完畢。

1.2 局部搜索

青蛙種群中各族群執(zhí)行局部搜索策略的目的是在不同的搜索方向上搜索局部最優(yōu)，搜索迭代一定次數(shù)后使得族群中局部最優(yōu)個(gè)體逐步趨向于全局最優(yōu)個(gè)體。首先將青蛙種群劃分成多個(gè)族群，對(duì)每個(gè)族群進(jìn)行局部搜索，但是為了避免青蛙個(gè)體過(guò)早陷入局部最優(yōu)，同時(shí)加快收斂速度，在每個(gè)族群中按照特定的原則選擇一定數(shù)目的青蛙構(gòu)成該族群的子族群。

對(duì)于青蛙群體，具有全局最好適應(yīng)度的解表示為Ug；對(duì)于每一個(gè)子族群，具有最好適應(yīng)度的解表示為UB，最差適應(yīng)度的解表示為 UW。首先對(duì)每個(gè)子族群進(jìn)行局部搜索，即對(duì)子族群中最差適應(yīng)度的青蛙個(gè)體進(jìn)行更新操作，更新策略為：

其中，s表示青蛙個(gè)體的調(diào)整矢量，smax表示青蛙個(gè)體允許改變的最大步長(zhǎng)。

1.3 全局信息交換

全局信息交換有助于收集各族群搜索的局部信息，通過(guò)模因在全局中的傳遞，獲得新的搜索全局最優(yōu)解。當(dāng)所有族群經(jīng)過(guò)一定次數(shù)的局部搜索后，將各族群中青蛙個(gè)體混合在一起，按適應(yīng)度f(wàn)(xi)降序排列后，重新劃分族群，這樣使得青蛙個(gè)體間的模因信息得到充分的傳遞，然后繼續(xù)進(jìn)行局部搜索，如此反復(fù)直到滿足收斂條件算法為止。

2 蛙跳結(jié)合模糊C-均值的圖像分割算法

基于混合蛙跳與模糊C-均值結(jié)合的圖像分割算法步驟：

①初始化算法參數(shù)，其中包括：運(yùn)行次數(shù)，變異概率，青蛙族群數(shù)，每族青蛙個(gè)數(shù)，每個(gè)青蛙種群的子種群青蛙個(gè)數(shù)，允許最大步長(zhǎng)，以及青蛙個(gè)體；

②計(jì)算初始化聚類(lèi)中心的適應(yīng)度值，對(duì)適應(yīng)度進(jìn)行排序；

③生成種群和子種群，對(duì)適應(yīng)度差的個(gè)體進(jìn)行更新；

④若分類(lèi)數(shù)為 3，且第一類(lèi)聚類(lèi)中心與第二類(lèi)聚類(lèi)中心之差小于第二類(lèi)局類(lèi)中心與第三類(lèi)聚類(lèi)中心之差時(shí)，則對(duì)第一類(lèi)的聚類(lèi)中心進(jìn)行變異。變異目的是為了找到更優(yōu)的解；

⑤如果當(dāng)前的迭代次數(shù)達(dá)到預(yù)先設(shè)定的最大次數(shù)，則停止迭代，找到最優(yōu)解，否則返回到步驟③。

3 實(shí)驗(yàn)結(jié)果與討論

采用混合蛙跳與模糊 C-均值結(jié)合的圖像分割算法的參數(shù)設(shè)定：類(lèi)別數(shù)取3，變異概率為0.05，青蛙種群數(shù)為10，每一個(gè)青蛙種群的青蛙個(gè)數(shù)為10，每個(gè)青蛙種群的子種群青蛙個(gè)數(shù)為8，允許最大步長(zhǎng)為4。

將所提算法與FCM結(jié)合FPSO的算法進(jìn)行比較，在初始條件相同的情況下分別采用兩種方法對(duì)圖像進(jìn)行分割實(shí)驗(yàn)。

為了獲取一個(gè)定量的實(shí)驗(yàn)結(jié)果比較，筆者引入有效性評(píng)價(jià)函數(shù)，在聚類(lèi)方法中，它們經(jīng)常用來(lái)評(píng)價(jià)聚類(lèi)效果的好壞。其中最具代表性的是分割系數(shù) Vpc和分割熵 Vpe[8],它們分別定義如下：

當(dāng)兩個(gè)有效性評(píng)價(jià)函數(shù)達(dá)到最優(yōu)值，即Vpc達(dá)到最大值，Vpe達(dá)到最小值時(shí)，模糊聚類(lèi)分割的效果最好。

以下是幾幅航拍圖的分割效果。

圖1 航拍原圖

圖2 基于FPSO和FCM結(jié)合算法的分割

圖3 所提算法的 圖像分割圖像

可以看出，在相同初始條件下，所提出的算法可以更加有效地分割背景與目標(biāo)，取得了更好的分割結(jié)果。

表1匯總了兩種分割方法所對(duì)應(yīng)的分割系數(shù)Vpc和分割熵Vpe的值。

從表1中可以看出所提算法與FCM結(jié)合FPSO算法相比提高了聚類(lèi)的精度，并且縮短了分割所用時(shí)間，在圖像聚類(lèi)分割方面有更好的表現(xiàn)能力。

表1 兩種算法的分割結(jié)果

作為一種全新的生物進(jìn)化算法，混合蛙跳結(jié)合了基于基因進(jìn)化的模因演算法（MA）和基于群體行為的粒子群算法（PSO）兩者的優(yōu)點(diǎn)，具有概念簡(jiǎn)單，參數(shù)少（比 PSO更少的算法參數(shù)），易于實(shí)現(xiàn)的特點(diǎn)。從實(shí)驗(yàn)數(shù)據(jù)來(lái)看，分割系數(shù)Vpc值大于FCM結(jié)合FPSO算法的值，分割熵Vpe的值小于FCM結(jié)合FPSO算法的值，因此提高了圖像分割的精度。綜上所述，所提方法對(duì)圖像進(jìn)行分割不但能得到較好的圖像分割效果而且提高了圖像分割效率。

4 結(jié)語(yǔ)

所提出的圖像分割算法是將混合蛙跳算法引入到 FCM聚類(lèi)算法中。實(shí)驗(yàn)表明，該算法能有效解決傳統(tǒng)FCM對(duì)于初始化比較敏感以及容易陷入局部極小的問(wèn)題，具有較強(qiáng)的全局搜索能力，并且在圖像分割的效果方面優(yōu)于FCM結(jié)合其他算法。

[1]WANG Xiang-yang, WANG Chun-hua. An Adaptive FCM Image Segmentation Algorithm Based on the Feature Divergence[J].Image and Graphic, 2008, 13(05): 906-910.

[2]BEZDEK J C, EHRLICH R, FULL W. The Fuzzy C-means Clustering Algorithm[J]. Computers and Geosciences, 1994, 10(2):191-203.

[3]ADEL H, BERTRAND Z. FCM with Spatial and Multi-resolution Constraints for Image Segmentation[J].Lecture Notes in Computer Science,2005,3656(10): 17-23.

[4]INGUNN BERGET, BJM-HELGE MEVIKC, TORMOD NAS. New Modifications and Applications of Fuzzy C-means Methodology[J].Computational Statistics＆Data Analysis, 2008,52: 2403-2418.

[5]DU Gen-yuan, MIAO Fang. A Modified Fuzzy C-means Algorithm in Remote Sensing Image Segmentation[C]//IEEE. 2009 IEEE International Conference on Environmental Science and Information Application Technology. [s.l.]:IEEE, 2009:447-450.

[6]JING Zang, Image Segmentation Using Possibilistic C Means Based on Particle Swarm Optimization[C]// IEEE. IEEE Global Congress on intelligent Systems. [s.l.]:IEEE,2009: 119-123.

[7]張蕾, 呂振肅. 基于改進(jìn)的自適應(yīng)克隆選擇粒子群優(yōu)化算法的多用戶檢測(cè)[J]. 通信技術(shù), 2007, 40(12):190-192.

[8]CHUANG K S, TZENG H L, CHEN S W, et al. Fuzzy C-means Clustering with Spatial Information for Image Segmentation[J].Comp.Med.Imag.Graph, 2006,30: 9-15.