劉戀，常冬霞，鄧勇

（1．北京交通大學(xué)信息科學(xué)研究所，北京100044；2．北京交通大學(xué)計算機與信息技術(shù)學(xué)院，北京100044；3．北京交通大學(xué)北京現(xiàn)代信息科學(xué)與網(wǎng)絡(luò)技術(shù)北京市重點實驗室，北京100044；4．中國科學(xué)院軟件研究所，北京100190）

動態(tài)小生境人工魚群算法的圖像分割

劉戀1，2，3，常冬霞1，2，3，鄧勇4

（1．北京交通大學(xué)信息科學(xué)研究所，北京100044；2．北京交通大學(xué)計算機與信息技術(shù)學(xué)院，北京100044；3．北京交通大學(xué)北京現(xiàn)代信息科學(xué)與網(wǎng)絡(luò)技術(shù)北京市重點實驗室，北京100044；4．中國科學(xué)院軟件研究所，北京100190）

為了克服傳統(tǒng)基于聚類的圖像分割算法需要指定聚類數(shù)目以及依賴初始值等缺點，提出了一種基于動態(tài)小生境的人工魚群算法的圖象分割方法。該算法將圖像分割問題轉(zhuǎn)化為根據(jù)圖像像素特征對像素的自動聚類問題。采用更為簡單的個體描述方式，每條人工魚表示一個分割區(qū)域的一個可行解，并對進化過程中的人工魚進行動態(tài)的劃分小生境，每個小生境對應(yīng)了圖像分割問題中一個分割區(qū)域。通過對魚群行為的模擬及種群的動態(tài)劃分實現(xiàn)了對圖像分割問題的分割區(qū)域中心和區(qū)域數(shù)的同時進化，實現(xiàn)了一種新的聚類算法，并實現(xiàn)了對圖像的自動分割。實驗結(jié)果表明：該算法可以自動地估計分割的區(qū)域數(shù)，并獲得較好的分割性能。

人工魚群算法；圖像分割；聚類；動態(tài)小生境；進化計算

圖像分割作為計算機視覺和人工智能領(lǐng)域中一項意義重大而又艱巨的研究工作，眾多國內(nèi)外學(xué)者對此展開了深入廣泛的研究，提出了很多算法，現(xiàn)有算法大致可以分為：邊緣檢測算法、聚類算法和區(qū)域算法。其中，基于聚類算法的圖像分割算法是圖像分割領(lǐng)域中一類極其重要且應(yīng)用廣泛的算法。該類算法將圖像分割問題轉(zhuǎn)化為根據(jù)像素特征對像素進行分類的過程，使得在同一類中的像素盡可能的相似，而不同類中的像素則盡可能的不相似。

所謂聚類就是將具有相似性質(zhì)的事物區(qū)分并加以分類，而圖像分割問題恰好是將圖像的像素集進行分類的問題，因此，人們很自然地將聚類分析應(yīng)用于圖像分割。早在1979年，Coleman和Anderews就提出采用聚類算法進行圖像分割［1］，同時也有學(xué)者使用聚類算法進行預(yù)分，然后再基于高低精度距離重構(gòu)泡的方法對圖像進行分割［2］。K?均值作為一種簡單有效的聚類算法也在圖像分割中得到了廣泛的應(yīng)用。最初的基于K?均值的圖像分割算法只考慮特征向量，而忽略了像素間的空間位置關(guān)系，因此，會造成在空間位置上很接近的像素點在特征空間中卻相距很遠。為了有效地消除這種情況，又出現(xiàn)了對K?均值分割方法的改進研究，從而產(chǎn)生了一系列基于空間位置約束的K?均值圖像分割算法研究［3］，不僅考慮像素的視覺相似性，還考慮了像素的空間鄰域信息。基于K?均值的圖像分割算法雖然是一種簡單高效的算法，仍存在很多問題。首先需要預(yù)先知道聚類中心的數(shù)目，雖然大多情況下能夠得到很好的分割效果，但分割結(jié)果對初始值敏感，算法魯棒性不強。實際上，基于K?均值的聚類通常將聚類問題轉(zhuǎn)化為一個優(yōu)化問題，然后采用各種優(yōu)化算法求解。在實際應(yīng)用中，由于樣本數(shù)據(jù)分布的多樣性，目標函數(shù)往往比較復(fù)雜，采用傳統(tǒng)的優(yōu)化算法很難獲得問題的最優(yōu)解。因此，近似最優(yōu)算法以及尋找局部最優(yōu)解的聚類算法成為人們研究的熱點。人工魚群算法作為一類智能優(yōu)化算法［4?5］，其主要特點是群體搜索策略以及群體之間的信息交換，對目標函數(shù)的性態(tài)沒有苛刻要求，具備全局尋優(yōu)的能力，求解不依賴于梯度信息，因而特別適用于大規(guī)模復(fù)雜問題的求解，在實際中具有廣泛的應(yīng)用前景［6?7］。因此，本文提出了一種基于人工魚群的圖像自動分割算法。

目前已有學(xué)者提出了基于人工魚群的分割算法，文獻［8］提出了一種基于人工魚群的二維Otsu閾值分割，成功地將魚群算法應(yīng)用到了灰度圖像的分割。該算法通過模擬魚群的聚群、追尾、捕食等行為來找到實物濃度最大的個體，從而找到最好的分割閾值。文獻［9］則對含噪聲圖像使用小波變換來進行小波域抑噪預(yù)處理后，使用魚群算法來尋找最優(yōu)閾值進行閾值分割，也取得了比較好的分割效果。文獻［10］則采用人工魚群算法對K?均值聚類進行初始化，從而克服K?均值聚類對初始化的依賴。但是，目前魚群算法的應(yīng)用都是針對灰度圖像分割的應(yīng)用。本文提出了利用魚群算法這種群體智能算法針對彩色圖像的特征空間進行聚類，同時在聚類過程引入動態(tài)小生境的概念，通過小生境內(nèi)部個體之間以及不同小生境之間的自組織，自動確定聚類類別數(shù)目，并對初始值不敏感。實驗結(jié)果表明所提算法能夠很好地根據(jù)彩色圖像的特征空間對圖像進行自動分割。

1 人工魚群算法

人工魚群算法是20世紀初提出來的一種智能群體尋優(yōu)算法［4］。該方法通過模仿魚類行為方式，模仿魚群的聚群、追尾、捕食等行為來進行尋優(yōu)，其具體步驟如圖1所示。魚群中個體根據(jù)視野范圍內(nèi)的個體食物濃度選擇合適的行為以最大步長范圍內(nèi)的距離進行活動。

圖1 人工魚群基本操作步驟Fig．1 The basic operation of the artificial fish swarm

人工魚群算法初始種群給定后，每個人工魚就是一個初始聚類中心，在搜索空間中以visual為視野范圍觀察周圍個體的適應(yīng)度和擁擠情況，并根據(jù)情況來選擇聚群和追尾行為。若找到一個比當前適應(yīng)度大的行為方向，則以小于最大步長step的長度向此方向進行游動，當都不滿足2種行為的條件移動的時候，則選擇捕食行為。算法中所使用的聚群、追尾、捕食等行為具體操作如下：

1）聚群行為：設(shè)人工魚當前狀態(tài)為（zi，J），個體在特征空間中以visual為視野范圍，設(shè)在其視野范圍內(nèi)有nf個個體，這些個體的中心位置為（zc，Jc）。若Jc／nf＞δ×Ji（δ表示擁擠度數(shù)），則說明其視野范圍內(nèi)個體中食物濃度較高并且還不太擁擠，則該個體向該個體伙伴中心位置方向，即（zc，Jc）方向以小于最大步長step前進一步。

2）追尾行為：設(shè)人工魚當前狀態(tài)為（zi，Ji），在其搜索空間內(nèi)尋找一個適應(yīng)值最大的個體（zj，Jj），并在其視野范圍內(nèi)尋找同伴的個數(shù)nf，若滿足Jj／nf＞δ×Ji，說明最大個體附近食物濃度較高，且不擁擠，則沿著此最大個體方向移動。

3）捕食行為：此行為為追尾和聚群行為的缺省行為，設(shè)人工魚當前狀態(tài)為（zi，Ji），在個體搜索范圍內(nèi)即半徑為visual范圍內(nèi)向任意方向（zj，Jj）嘗試移動，若該位置具有比當前位置較高的食物濃度，則向此方向隨機大小移動一步，否則繼續(xù)嘗試。若達到設(shè)定的最大嘗試次數(shù)還未找到一個比當前位置適應(yīng)值更高的方向則執(zhí)行隨機行為。

4）隨機行為：隨機行為是在以上3種行為均不滿足時執(zhí)行的缺省行為，就是在其視野范圍內(nèi)隨機方向移動一步。

2 基于動態(tài)小生境的人工魚群算法

本節(jié)提出了一種基于動態(tài)小生境人工魚群算法（DNAF），該算法將彩色圖像的顏色空間作為特征空間，使用魚群算法實現(xiàn)了圖像的自動分割，其具體步驟如圖2所示。為了克服傳統(tǒng)聚類算法中需要指定聚類中心的數(shù)目的問題，DNAF算法使用了動態(tài)小生境技術(shù)，在每一代的進化后都根據(jù)魚群的在特征空間的分布情況，將魚群自動分為相應(yīng)數(shù)目的小生境，然后繼續(xù)下一代的進化。該算法中所獲得的魚群的小生境個數(shù)即為圖像分割問題的類別數(shù)。

圖2 DNAF算法流程圖Fig．2 Flowchart of DNAF algorithm

2．1 魚群初始化

在算法中，本文采用實數(shù)編碼方式對分割中心進行編碼，一個人工魚描述一個類別中心，即每個人工魚為長度N＋1的實數(shù)序列（zj，jj） ：

式中：N為圖像特征空間的維數(shù)，zj為人工魚在特征空間的位置，Jj為人工魚的食物濃度，即目標函數(shù)值。種群規(guī)模為P的初始魚群是隨機生成的，本文隨機選取P個不同的像素點作為初始魚群。

2．2 食物濃度函數(shù)

本節(jié)引入一種新的聚類算法的目標函數(shù)，通過該目標函數(shù)，可以將傳統(tǒng)的基于聚類算法的圖像分割轉(zhuǎn)化為多峰函數(shù)求極值問題，目標函數(shù)峰值的個數(shù)即為分割問題的區(qū)域數(shù)，峰值所對應(yīng)的變量值即為分割問題的區(qū)域中心。

令X＝｛x1，x2，…，xn｝為N維圖像特征集，K為類別數(shù)，即圖像中的區(qū)域數(shù)，則分割目標就是尋找一系列ci使得目標函數(shù)Js（z）值最大，且：

式中：Z＝（Z1，Z2，…，Zk），β為標準化參數(shù)：

文獻［11］指出了目標函數(shù)中的γ決定目標函數(shù)峰的位置和個數(shù)。本文采用文獻［11］提出的CCA算法估計γ。在獲得γ的估計值之后，函數(shù)Js（zj）則轉(zhuǎn)變?yōu)橐粋€多峰函數(shù)，且其峰的個數(shù)與特征集X＝｛x1，x2，…，xn｝中的類別數(shù)相同。因此，通過此目標函數(shù)即可將圖像分割問題轉(zhuǎn)化為一個多峰函數(shù)求解問題，通過估計函數(shù)Js（zj）的峰的個數(shù)和峰值來求解分割問題的區(qū)域數(shù)和區(qū)域中心，Js（zj）局部極值的個數(shù)即為所求分割的區(qū)域數(shù)，局部最優(yōu)值即為區(qū)域中心。

2．3 自適應(yīng)動態(tài)小生境

人工魚群初始化后或者每一次迭代之后，根據(jù)人工魚群在特征空間中的分布情況將每一個個體分配到相應(yīng)的小生境中，具體的算法描述如下。

1）計算每個個體的食物濃度；

2）找到最大個體，以此個體為中心初始小生境半徑范圍內(nèi)的所有個體劃分到以此個體為中心的小生境內(nèi)；

則人工魚群的食物濃度為

3）在沒有被劃分的個體中尋找適應(yīng)度最大的個體，進行操作2），直至所有個體都被劃分到各自所在的小生境內(nèi)。

偽代碼如表1所示。

通過表1給出動態(tài)小生境算法即可將第t代人工魚群Popt劃分為一系列的小種群。將確定的一系列的候選小生境的集合分為2類，一類是種群中個體數(shù)目大于1的小生境稱為真正的小生境，記為另一類則是只有一個個體的小生境，將這些單個體小生境合并為一個小生境這樣，Popt即被劃分為v（t）個真正的小種群和一個復(fù)合小種群S?t，即

2．4 魚群迭代尋優(yōu)

給定一個迭代次數(shù)，每一個個體按照基本的魚群算法進行迭代尋優(yōu)，在每一次迭代結(jié)束后重復(fù)2．3中的動態(tài)小生境的劃分，真正的小生境的代表個體即為分割問題的區(qū)域中心。隨著迭代次數(shù)的增加，最后得到的小生境個數(shù)就是圖像分割的區(qū)域總數(shù)，小生境中代表個體即為分割區(qū)域的中心。

3 實驗結(jié)果與分析

為了驗證本文所提DNAF算法的分割性能，在本節(jié)中將小生境遺傳算法SCGA［12］、K?均值、模糊C?均值［13］和DNAF應(yīng)用于彩色圖像的分割，實驗證明本文的算法可以有效的對圖像進行分割。

實驗中采用如圖3所示的3幅圖像（源自Berkeley圖像數(shù)據(jù)庫）。由于K?均值和模糊C?均值算法需要預(yù)先知道劃分的類別數(shù)，在實驗中將其設(shè)為圖像中的真實類別數(shù)。為了直觀的比較3種算法的性能，進行了多次試驗結(jié)果進行平均（通過投票確定最終的分割區(qū)域數(shù)，并僅對正確分割的結(jié)果進行平均），在圖4～6中給出4種算法的最終分割結(jié)果。由圖可見，本文所提DNAF算法可以有效地對圖像進行分割，并且可以自動地確定分割的類別數(shù)，算法自動獲得的分割區(qū)域數(shù)如表2所示。由于本文提出的算法主要是通過魚群的游動實現(xiàn)的，在每一代的進化時每一個個體都要進行一次行為的判斷，并且每一個個體都需要根據(jù)周圍特征點分布進行計算得到食物濃度，因此本算法時間復(fù)雜度為O（nm），其中為n初始化魚群個體數(shù)目，m為圖像像素點的個數(shù)。

圖3 實驗使用的原始圖像Fig．3 The original image used in the experiment

圖4 4種算法對教堂圖像的分割結(jié)果Fig．4 The segmentation results for the church obtained by four algorithms

圖5 4種算法對飛機圖像的分割結(jié)果Fig．5 The segmentation results for the plane obtained by four algorithms

圖6 4種算法對海星圖像的分割結(jié)果Fig．6 The segmentation results for the starfish ob?tained by four algorithms

表2 DNAF算法所得圖像的分割區(qū)域數(shù)Table 2 The cluster number obtained by DNAF

為了進一步驗證算法的有效性，采用文獻［14］中的F（I）、F′（I）和Q（I）對算法性能進行比較，其值越小則意味著對圖像的分割結(jié)果越好。表3中給出了對實驗中所采用的4幅圖像分割結(jié)果的F（I）、F′（I）和Q（I）。由表3可見，DNAF算法的性能優(yōu)于其他2種算法，對圖像的分割結(jié)果獲得了較小的F（I）、F′（I）和Q（I）。

4 結(jié)束語

本文提出了一種基于DNAF算法的圖像分割算法，該算法通過對魚群的不斷進化，可以同時獲得分割問題的區(qū)域數(shù)和區(qū)域中心。由于該算法并不需要預(yù)先對分割區(qū)域數(shù)進行設(shè)定，因此，在實際中將具有更廣泛的應(yīng)用前景。DNAF分割算法采用一種更為簡便的個體描述方式，即每個個體即代表一個區(qū)域中心，通過動態(tài)地對魚群劃分為幾個小生境而獲得分割的區(qū)域數(shù)。通過實驗仿真可見，所提DNAF算法可以有效地實現(xiàn)對圖像的自動分割。

［1］COLEMAN G B，ANDREWS H C．Image segmentation by clustering［J］．Proceedings of the IEEE，1979，67（5）：773?785．

［2］陽春華，楊盡英，牟學(xué)民，等．基于聚類預(yù)分割和高低精度距離重構(gòu)的彩色浮選泡沫圖像分割［J］．電子與信息學(xué)報，2008，30（6）：1286?1290．YANG Chunhua，YANG Jinying，MOU Xuemin，et al．A segmentation method based on clustering pre?segmentation and high?low scale distance reconstruction for colour froth image［J］．Journal of Electronics＆Information Technology，2008，30（6）：1286?1290．

［3］ZHANG Jingdong，JIANG Wuhan，WANG Ruichun，et al．Brain MR image segmentation with spatial constrained K?mean algorithm and dual?tree complex wavelet transform［J］．Journal of Medical Systems，2014，38（9）：93．

［4］李曉磊．一種新型的智能優(yōu)化方法——人工魚群算法［D］．杭州：浙江大學(xué)，2003：10?15．LI Xiaolei．A new intelligent optimization method?artificial fish school algorithm［D］．Hangzhou，China：Zhejiang Uni?versity，2003：10?15．

［5］HUANG Zhenhuang，CHEN Yidong．An improved artificial fish swarm algorithm based on hybrid behavior selection［J］．International Journal of Control and Automation，2013，6（5）：103?116．

［6］EI?SAID S A．Image quantization using improved artificial fish swarm algorithm［J］．Soft Computing，2014，24（8）：221?232．

［7］LIU Qing，ODAKA T，KUROIWA J，et al．Application of an artificial fish swarm algorithm in symbolic regression［J］．IEICE Transactions on Information and Systems，2013，96?D（4）：872?885．

［8］潘喆，吳一全．二維Otsu圖像分割的人工魚群算法［J］．光學(xué)學(xué)報，2009，29（8）：2115?2121．PAN Zhe，WU Yiquan．The two?dimensional Otsu threshol?ding based on fish?swarm algorithm［J］．Acta Optica Sinica，2009，29（8）：2115?2121．

［9］范玉軍，王冬冬，孫明明．改進的人工魚群算法［J］．重慶師范大學(xué)學(xué)報：自然科學(xué)版，2007，24（3）：23?26．FAN Yujun，WANG Dongdong，SUN Mingming．Improved artificial fish?school algorithm［J］．Journal of Chongqing Normal University：Natural Science Edition，2007，24（3）：23?26．

［10］楚曉麗．K?means聚類算法和人工魚群算法應(yīng)用于圖像分割技術(shù)［J］．計算機系統(tǒng)應(yīng)用，2013，22（4）：92?94．CHU Xiaoli．K?means clustering algorithm and artificial fish swarm algorithm applied in image segmentation tech?nology［J］．Computer Systems and Applications，2013，22（4）：92?96．

［11］YANG M S，WU K L．A similarity?based robust clustering method［J］．IEEE Transactions on Pattern Analysis Ma?chine Intelligence，2004，26（4）：434?448．

［12］LI Jianping，MARTON E B，PARKS GY T，et al．A spe?cies conserving genetic algorithm for multimodal function optimization［J］．Evolutionary Computation，2002，10（3）：207?234．

［13］BEZDEK J C，CHRISTIAN J．Fuzzy mathematics in pat?tern classification［D］．New York City：Cornell University，1973，142?147．

［14］BORSOTTI M，CAMPADELLI P，SCHETTINI R．Quanti?tative evaluation of color image segmentation results［J］．Pattern Recognition Letters，1998，19（8）：741?747．

An image segmentation method based on dynamic niche artificial fish?swarm algorithm

LIU lian1，2，3，CHANG Dongxia1，2，3，DENG Yong4
（1．Institute of Information Science，Beijing Jiaotong University，Beijing 100044，China；2．School of Computer and Information Tech?nology，Beijing Jiaotong University，Beijing 100044，China；3．Beijing Key Laboratory of Advanced Information Science and Network Technology，Beijing Jiaotong University，Beijing 100044，China；4．Institute of Software，Chinese Academy of Sciences，Beijing 100190，China）

In order to overcome the defects in the traditional clustering?based image segmentation algorithm，e．g．，it needs to specify the number of clusters，it is sensitive to initial value，and so on，an image segmentation method based on dynamic niche artificial fish?swarm algorithm（DNAF）is presented in this paper．In the new algorithm，the image segmentation problem is transformed into an automatic pixel clustering process based on the pixel features of the image．A simpler representation is adopted，each artificial fish represents a single feasible solution of one seg?mented area．Moreover，the dynamic identification of the fish niches is performed at each generation to automatical?ly evolve the optimal number of regions．Each fish niche corresponds to one segmentation region in the image seg?mentation problem．Therefore，the proposed DNAF algorithm implements simultaneous evolution in the center of the segmentation region and the optimal number of regions through simulation on the behaviors of fish swarm and the dynamic division of population．It thereby achieves a new clustering algorithm and automatic segmentation of an im?age．Experiment results demonstrate that the DNAF algorithm is able to automatically estimate the number of the segmented regions，and an excellent segmentation performance can be attained．

artificial fish?swarm algorithm；image segmentation；clustering algorithm；dynamic niche；evolutionary com?putation

劉戀，男，1990年生，碩士研究生，主要研究方向為智能優(yōu)化算法和圖像分割。

常冬霞，女，1977年生，博士，副教授，主要研究方向為進化計算、非監(jiān)督分類算法、圖像分割以及圖像分類等。主持國家自然科學(xué)基金項目1項，中央高?；究蒲袠I(yè)務(wù)費1項。發(fā)表學(xué)術(shù)論文10余篇，其中SCI收錄4篇，EI收錄2篇。

鄧勇，男，1974年生，博士，副研究員，主要研究方向為智能信息處理、數(shù)據(jù)庫系統(tǒng)技術(shù)及應(yīng)用等。主持和參與國家863項目1項，北京市自然科學(xué)基金項目1項。發(fā)表學(xué)術(shù)論文20余篇，其中EI收錄10余篇。

TN391．41；TP391．41

A

1673?4785（2015）05?0669?06

10．11992／tis．201501001

http：／／www．cnki．net／kcms／detail／23．1538．TP．20150827．1716．016．html

劉戀，常冬霞，鄧勇．動態(tài)小生境人工魚群算法的圖像分割［J］．智能系統(tǒng)學(xué)報，2015，10（5）：669?674．

英文引用格式：LIU Lian，CHANG Dongxia，DENG Yong．An image segmentation method based on dynamic niche artificial fish?swarm algorithm［J］．CAAI Transactions on Intelligent Systems，2015，10（5）：669?674．

2015?01?01．

日期：2015?08?27．

國家自然科學(xué)基金資助項目（61100141）；中央高?；究蒲袠I(yè)務(wù)費資助項目（2013JBM021）；中央高?；究蒲袠I(yè)務(wù)費專項基金資助項目（2012RC044）．

鄧勇．E?mail：dengyong＠iscas．a(chǎn)c．cn．