基于蟻群算法的醫學圖像分割研究

摘 要：通過對螞蟻信息激素釋放、路徑轉移的重新定義，并將圖像空間的模糊連接關系引入螞蟻的覓食過程中，進而轉換為螞蟻搜尋食物的準則，實現了醫學影像圖像的分割，并進一步分析了算法實現中相關影響因素參數選擇的問題。

關鍵詞：醫學圖像分割； 蟻群算法； 模糊連接

中圖分類號：TN911.72；TP391 文獻標志碼：A

文章編號：10013695(2008)09285303

Study on medicalimage segmentation based on ant colony algorithm

KANG Xiaodong1，2， HE Pilian1， LIU Yujie1，3， LI Zhisheng1

（1. School of Computer Science Technology， Tianjin University， Tianjin 300072， China; 2. Dept. of Medical Image， Tianjin Medical University， Tianjin 300070， China; 3. School of Computer Science Technology， Civil Aviation University of China， Tianjin 300300， China）

Abstract:This paper made a redescription to the ant pheromone releasing and route of ant. A fuzzy connectedness of image was introduced to the process of ant’s seeking for food， therefore， transferred to the ruler of art’s seeking for food. Thus， the medicalimage segmentation was realized. The related factors for the preferences were analyzed further while the algorithm was used.

Key words：medicalimage segmentation; ant colony algorithm(ACA); fuzzy connectedness

圖像分割是圖像處理、模式識別和計算機視覺等領域的經典研究領域，但因醫學影像圖像對比度較低，且組織特征具有可變性、不同組織或組織與病灶間邊界模糊、微細結構（血管、神經）分布復雜等，目前尚無通用的方法對任意醫學圖像都能取得較好的分割效果。故人們致力于將新概念、新方法應用于醫學圖像分割領域。

1 蟻群算法

由意大利Marco Dorigo等人于1991年首次提出的蟻群算法（ACA），是繼神經網絡、遺傳算法和免疫算法之后的又一類啟發式搜索算法。

1.1 螞蟻及其群體覓食策略

觀察和研究表明：螞蟻有能力在無任何可見提示下找出蟻穴與食物源間的最短距離，且能隨環境變化而變化地搜索新路徑，產生新選擇。螞蟻行為的實質是簡單個體的自組織行為體現出來的群體行為，每只螞蟻的行為均對環境產生影響，環境的變化進而對螞蟻影響并波及其他螞蟻。螞蟻間通過相互通信協作完成一系列復雜的任務。

螞蟻間的相互通信借助于其所特有的分泌物，即信息激素（pheromone）實現。在一定范圍內，螞蟻能夠察覺到信息激素，并憑借其指導自己的行為，路徑通過的螞蟻多，則留下的信息激素多，后續的螞蟻選擇該路徑的概率也高，進而更增加信息激素的強度^[1]。

上述螞蟻間為達到搜索事物目的而通過物質信息的交流來選擇路徑過程即為螞蟻的自催化行為（autocatalytic behavior），是一類正反饋機制。

1.2 螞蟻系統

以求解平面上n個城市的旅行商問題（traveling salesman problem，TSP）而提出的螞蟻系統（ant system，AS）是最早的模擬蟻群行為的蟻群算法。該算法基于如下假設：

a）螞蟻間通過環境通信。每只螞蟻僅依據其周圍局部環境產生相應反應，且也僅對其周圍局部環境產生影響。螞蟻間通過信息激素間接通信，并趨于選擇信息激素濃度高的方向。

b）螞蟻對環境的反應由其內部模式決定。螞蟻屬反應型適應主體。

c）雖然在個體上，每只螞蟻僅根據環境作出獨立選擇，但在群體上，單只螞蟻的行為是隨機的，且蟻群通過自組織形成高度有序的群體行為。

在人工螞蟻系統中，人工蟻是一類反應型主體，它由感知器、效應器和內部執行系統組成。感知器收集環境信息；效應器改變環境；內部執行系統是一組條件和動作規則，負責連接主體感知與效應器。

蟻群算法通過候選組織群體的進化過程來尋求最優解，其過程包括適應和協作兩個階段。在適應段，各候選解根據積累的信息調整自身結構；在協作段，各候選解間通過信息交流，產生性能更好的解。螞蟻使用一種結構上的貪婪啟發式搜索可行解，根據問題約束列出一個解，作為經過問題狀態的最小代價。每只螞蟻均能夠找出一個解，但可能是較差的解。蟻群中的個體可同時建立多個不同的解，而找出高質量的解則是群體中所有個體間全局性的協作結果。

令：m為蟻群中螞蟻數，bi（t）為t時刻位于城市i的螞蟻數且m=∑ni=1bi(t)，dij為城市i與j間距離，ηij為城市i至j間的能見度或期望度，τij為t時刻城市ij間信息激素殘留量，Pkij為螞蟻k的轉移概率。

若初始時刻各條路徑上的信息激素量相同，即τij（0）=C（常數），則對螞蟻k（k=1，2，…，m），其t時刻由位置i轉移至位置j的概率為

Pkij（t）=[ταij(t)ηβij(t)]/

[∑s∈Sταis(t)ηβis(t)] 若j∈S

0否則（1）

其中：S={0，1，…，n-1}為螞蟻k下一步允許選擇的城市；α和β反映了螞蟻運動中積累的信息及啟發式因子對其選擇路徑過程中的作用。

由式（1）知，轉移概率Pkij（t）與ταij、ηβij成正比。

螞蟻經n時刻完成一次循環，同時其先前殘留的信息激素也將逐漸消失。令Δτkij（t，t+1）為螞蟻k于（t，t+1）時刻留在路徑（i，j）上的信息激素量，（1-ρ）為信息激素量的衰減系數，則有調整

τij(t+1)=ρτij(t)+Δτij(t，t+1)

Δτij(t，t+1)=∑mk=1Δτkij(t，t+1)(2)

其中：Δτkij（t，t+1）=Q 螞蟻k在(t，t+1)間經過(i，j)0否則；Q是螞蟻完成一次搜索循環后在單位長度上釋放的信息激素總量，為常量。

算法不同，Δτij、Δτkij和Pkij（t）的表達形式也不同，并可依據其將螞蟻系統具體劃分為蟻周系統（antcycle）模型、蟻量系統（antquantity）模型和蟻密系統（antdensity）模型三類^[1，2]。

13 改進的蟻群算法

單個螞蟻的狀態包括位置信息r和運動方向信息θ。螞蟻在不同像素間的轉移概率為

W（σ）=（1+σ/（1+δσ））β（3）

式（3）是一個雙參數的信息激素加權函數。像素r的信息激素強度為σ（r），β用來控制螞蟻沿信息激素梯度方向運動的可能性，1/δ為螞蟻對信息激素的敏感度。

考慮到螞蟻的運動慣性，即其向前運動的概率較大，增加一項加權系數W（Δθ）后，則t時刻，螞蟻從像素k至i的轉移概率為

Pik=(W(σi)w(Δi))/∑j/kW(σj)w(Δj)

（4）

其中：j/k為像素k的相鄰像素；Δi為（t-1）時刻像素i相對于k的方向與螞蟻先前運動方向的差別。當螞蟻被放置于圖像中某位置后，其會通過概率Pik的計算來選擇自己的移動方向，并釋放一定的信息激素。信息激素釋放量為

T=η+pΔh（5）

其中：η為恒定的釋放量；p為常量；當在像素k和i周圍取相同窗口時，Δh為窗口間像素的相似度。

Δh由三項組成，分別為兩窗口間像素平均灰度強度相似度、像素灰度均勻相似度和像素灰度直方圖相似度，即

Δh=a｜m1-m2｜/（max ｜m1-m2｜）+

b｜σ21-σ22｜/（max ｜σ21-σ22｜）+c S/Smax （6）

其中：（a+b+c）=1；mi為窗口像素的平均灰度強度；σ2i為窗口像素灰度強度的方差；S為窗口像素灰度直方圖的差別^[3]。

2 基于蟻群算法的醫學圖像分割

2.1 圖像模糊關系的描述

對任意幅灰度數字圖像I，均存在一個等價的圖像模糊場M：M={（x，μ（x））｜x∈I}，μ（x）∈（0，1）。其模糊關系則是模糊數字空間（Zn，α）上圖像場C中的一個子集μk（c，d）：μk（c，d）=max[min（μ（c0，c1），μ（c1，c2），…，μ（cn-1，cn））]。這里，c0，c1，…，cn是任意（c，d）∈C間的路徑。考慮到灰度數字圖像的二值關系，則Oθ（o）應是一個由如下隸屬度函數定義的模糊子集

μOθ(c)=η(f(c)) 若c∈Oθ(o)0否則（7）

其中：對于任意o∈C，定義Oθ（o）為Kθ對象的一個包含O的等價類。

進一步，通過對于特定圖像場上模糊kθ對象的模糊子集的計算，即可得到一個反映像素連通特性的圖像。不妨以如下兩個函數來描述圖像空間中的灰度及空間信息的隸屬度^[4]

μξ(c，d)=μω(c，d)/（1+k2｜f(d1)-f(d2)｜）(8)

μω(c，d)=1/(1+k1

∑ni=1(ci-di)2） 若∑ni=1｜ci-di｜≤n0否則（9）

其中：k1、k2是常量；f（d）是像素灰度；i是像素坐標索引。

2.2 人工蟻食物參照物及搜索目標的確定

對醫學圖像分割可理解為模擬螞蟻行為的人工蟻覓食過程。此時，人工蟻是以灰度、梯度和鄰域為特征向量，圖像分割則是這些具有不同特征的人工蟻搜索食物源的過程。

1）定義人工蟻食物參照物 模擬螞蟻覓食過程所定義的人工蟻食物參照物即為醫學圖像分割過程中的參照物。

令t=0為初始時刻，選擇圖像像素為o，并取其周圍半徑為r的所有相鄰像素為Nr（o），則人工蟻i的參照物為

Nr（o）={e∈I ‖e-o‖

其中：I是所有待分割圖像像素。

2）確定人工蟻搜索目標。人工蟻搜索食物目標的過程等價于其在圖像中搜索與食物目標具有相似屬性像素的任務，因此，其必須有對相似像素比較的能力。當人工蟻位于像素c時，其隨后的行為將依據如下的比較步驟來確定^[5，6]

μk（o，c）=μφ(c，d)μψ(c，d)（11）

μφ(o，c)=min(mo，mc)/max(mo，mc)（12）

μψ(o，c)=1-｜D+(o，c)-D-(o，c)｜/∑e∈Nr(c)ω(‖o-c‖)（13）

D+(o，c)=∑{1-ωoc[δ+oc(e′)]ωoc(‖o-c‖)e∈Nr(o)，e′∈Nr(c)，e-o=e′-c}（14）

D-(o，c)=∑{1-ωoc[δ-oc(e′)]ωoc(‖o-c‖)e∈Nr(o)，e′∈Nr(c)，e-o=e′-c }（15）

δ+oc(e′，e)=f(e)-f(e′)， 若f(e)-f(e′)＞00，否則（17）

δ-oc(e′，e)=f(e′)-f(e)， 若f(e′)-f(e)＜00，否則（18）

式（11）~（18）中，μψ（o，c）是模糊連接的醫學圖像中基于均勻性的分量；mo和mc分別是Nr（o）和Nr（c）的灰度強度。Nr（o）與Nr（c）越相似，則μψ（o，c）越大；反之亦然。

當μk（o，c）超過一定閾值時，像素c就是人工蟻要搜索的目標。人工蟻i在t=τ時刻搜索到c后，其記憶中的食物參照物將調整為

Fi，t=τ=aNr（c）+bFi，t=τ-1（19）

23 人工蟻的轉移概率與信息激素釋放

每時刻，人工蟻都自像素k向像素j移動，鑒于人工蟻的移動將受環境影響，且該影響局限于以像素k為中心的窗口W的范圍內，應有轉移概率為

Pik=W(σi)(w(Δi)+bE(θi))/[∑j/kW(σj)(w(Δj)+bE(θj))]（20）

E(θ)=a （N(w，θ)/Nw）（21）

式（20）（21）中，Nw是窗口W內人工蟻數量；N（w，θ）是窗口W內沿θ方向移動的人工蟻數量；a、b是常數。如此定義顯然有利于彼此合作的人工蟻快速接近目標像素區域。

考慮到閾值Δ不同的人工蟻，即使μk（o，c）超過一定值時，也未必能夠搜索到目標，故須對Δ定義分布區間，以體現其變異性，實驗取Δ在0.72~0.88。如此，則人工蟻信息激素釋放量T就成為^[7]

T(c)=η 若μk(o，c)＜Δη+pΔ否則（22）

其中：η是恒量；p是常量。

3 算法流程與實驗結果

基于蟻群算法的醫學圖像分割步驟如下：

a）初始化人工蟻，為每只人工蟻分配初始位置、食物和移動方向等參數。

b）選擇最佳移動方向。

c）計算像素與目標食物的相似性，若相似則人工蟻更新記憶，并釋放信息激素；否則只釋放信息激素而不更新記憶。

d）若滿足對圖像分割要求，則輸出圖像；否則返回b）。

基于上述流程，以McConnell Brain Imaging Center的腦MRI數據予以仿真和評估，并取η=0.07，β=3.25，p=1.2，令人工蟻數量約為像素數的30%時的分割結果表明：該算法較模糊C均值算法（fuzzy Cmeans algorithm，FCM）的相似度高。

4 結束語

本文通過對螞蟻信息激素釋放、路徑轉移的重新定義，并將圖像空間的模糊連接關系引入螞蟻的覓食過程中，進而轉換為螞蟻搜尋食物的準則，實現了醫學影像圖像的分割。本研究還進一步表明：人工蟻的數目對分割結果有較大影響，雖數目少時迭代時間短但分割細節差；分割過程須進行人工監督，以避免多只人工蟻出現在同一像素位置的情形；過量的信息激素也將影響最終的分割結果。

參考文獻：

［1］BULLNHEIMER B， HARTL R F， STRAUSS C. Applying the ant system to the vehicle routing problem:advanced and trends in local search paradigms for optimization[M]. Boston: MetaHeuristics， 1988:109120.

[2]李士勇. 蟻群算法及其應用[M]. 哈爾濱: 哈爾濱工業大學出版社， 2004.

[3]CHIALVO D R， MILLONAS M M. How swarms build cognitive maps[C]//STEELS L. The biology and technology of intelligent autonomous agent.[S.l]: NATO ASI Series， 1995:439450.

[4]潘建江， 楊勛年， 汪國昭. 基于模糊連接度的圖像分割及算法[J]. 軟件學報， 2005，16(1):6776.

[5]羅述謙， 周果宏. 醫學圖像處理與分析[M]. 北京: 科學出版社， 2003.

[6]曹會志. 基于蟻群算法的醫學圖像分割[D]. 北京: 首都醫科大學， 2006.

[7]TERZOPOULOUS D. Artificial life for computer graphics[J].Communications for the ACM，1999，42(8):3242.