基于區(qū)域生長(zhǎng)和蟻群聚類的圖像分割

摘要：提出了一種基于區(qū)域生長(zhǎng)和蟻群聚類的圖像分割方法——BRGAC。該方法首先用區(qū)域生長(zhǎng)法對(duì)圖像作

初始分割，然后利用蟻群算法搜索最優(yōu)解的能力，在區(qū)域之間進(jìn)行聚類合并，獲得最終的分割結(jié)果。BRGAC算法不但克服了區(qū)域生長(zhǎng)得不到有意義區(qū)域的不足，而且還大大提高了蟻群聚類算法的搜索時(shí)間，并利用初始分割后的空間信息和灰度信息定義了一種新的引導(dǎo)函數(shù)，可更準(zhǔn)確有效引導(dǎo)蟻群聚類。實(shí)驗(yàn)結(jié)果表明，該方法可以準(zhǔn)確地分割出目標(biāo)，是一種有效的圖像分割方法。

關(guān)鍵詞：區(qū)域生長(zhǎng)；群體智能；蟻群聚類；引導(dǎo)函數(shù)

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)05-1579-03

0引言

圖像分割是自動(dòng)目標(biāo)識(shí)別的關(guān)鍵和首要步驟，其目的是將目標(biāo)和背景分離，為計(jì)算機(jī)視覺(jué)的后續(xù)處理提供依據(jù)。

區(qū)域生長(zhǎng)是一種具有代表性的傳統(tǒng)圖像分割技術(shù)，該方法能夠提供封閉的區(qū)域，且計(jì)算簡(jiǎn)單。但它需要人工交互以獲得種子點(diǎn)，且區(qū)域生長(zhǎng)方式對(duì)噪聲敏感，導(dǎo)致抽取出的區(qū)域有空洞或者在局部體效應(yīng)的情況下將分開(kāi)的區(qū)域連接起來(lái)，產(chǎn)生了錯(cuò)誤的分割結(jié)果。在此基礎(chǔ)上研究者們提出了各種各樣的擴(kuò)展算法。Pohle等人將待分割區(qū)域像素值看做一個(gè)正態(tài)發(fā)布，先用原始區(qū)域生長(zhǎng)算法估算出分布參數(shù)，再將該參數(shù)應(yīng)用到第二次生長(zhǎng)過(guò)程中，從而獲得更好的結(jié)果[1]。文獻(xiàn)[2]將圖像的紋理信息和灰度信息融合在區(qū)域生長(zhǎng)的標(biāo)準(zhǔn)中；文獻(xiàn)[3]將模糊理論和優(yōu)化算法應(yīng)用到區(qū)域生長(zhǎng)算法中。

蟻群算法是一種具有離散性、并行性、魯棒性和模糊聚類能力的進(jìn)化方法。它是1992年意大利學(xué)者M(jìn).Dorigo等人受螞蟻覓食過(guò)程中路徑選擇行為的啟發(fā)而提出的帶有正反饋性等特點(diǎn)的一種隨機(jī)啟發(fā)式搜索方法。它已成功應(yīng)用于組合優(yōu)化問(wèn)題，如旅行商問(wèn)題、車間任務(wù)調(diào)度、圖著色、管線敷設(shè)等[4~6]。蟻群算法的離散性和并行性特點(diǎn)對(duì)于離散的數(shù)字圖像非常適用。而基本蟻群算法在進(jìn)行大規(guī)模優(yōu)化時(shí)，其收斂時(shí)間過(guò)長(zhǎng)，這是應(yīng)用該算法的一個(gè)瓶頸。

本文提出了一種基于區(qū)域生長(zhǎng)和蟻群聚類的圖像分割方法。首先選取目標(biāo)中最亮點(diǎn)(灰度最大點(diǎn))作為種子點(diǎn)，然后按照一定規(guī)則進(jìn)行區(qū)域生長(zhǎng)，再利用蟻群聚類得到有意義的區(qū)域。本文的方法避免了單獨(dú)使用區(qū)域生長(zhǎng)時(shí)的典型分割錯(cuò)誤，同時(shí)蟻群算法不再基于單個(gè)像素作為螞蟻去尋優(yōu)，而是將區(qū)域作為螞蟻尋優(yōu)，節(jié)省了計(jì)算成本，聚類快速高效。實(shí)驗(yàn)結(jié)果表明，BRGAC算法能夠快速準(zhǔn)確的分割圖像。

1蟻群聚類算法

蟻群聚類算法模擬真實(shí)螞蟻的協(xié)作過(guò)程， 由許多螞蟻共同完成， 每只螞蟻在候選解的空間中獨(dú)立地搜索解， 并在所尋得的解上留下一定的信息量，信息量越大的解被選擇的可能性也越大。蟻群聚類方法正是受此影響而來(lái)。蟻群聚類突出的特征是:可使數(shù)據(jù)更容易可視化，聚類的數(shù)量可從數(shù)據(jù)中自動(dòng)產(chǎn)生；蟻群聚類算法不僅能有效地處理有較好的抗噪聲數(shù)據(jù)能力， 而且更容易發(fā)現(xiàn)數(shù)據(jù)的本質(zhì)信息；其能實(shí)現(xiàn)完全分布式控制， 并具有自組織性、可擴(kuò)展性、健壯性等特征， 而且采用蟻群模型進(jìn)行聚類更加接近實(shí)際的聚類問(wèn)題[7]。因此筆者提出用蟻群聚類算法來(lái)解決區(qū)域生長(zhǎng)后得不到有意義區(qū)域的不足。

2基于區(qū)域生長(zhǎng)與蟻群聚類的圖像分割

本文算法流程如圖1所示。

2．1圖像的預(yù)處理

由于考慮的前提是從灰度值最高的像素點(diǎn)開(kāi)始生長(zhǎng)，去除圖像中的噪聲很重要。考慮到需要去除的只是一些灰度值不正常(偏高或者偏低) 的噪聲點(diǎn)，采用四鄰域的中值濾波，結(jié)果顯示對(duì)不正常的像素點(diǎn)有很好的效果。實(shí)驗(yàn)中同時(shí)發(fā)現(xiàn)，如果中值濾波的窗口取大了，會(huì)過(guò)度地模糊圖像中的目標(biāo)邊緣，在進(jìn)行增長(zhǎng)判斷時(shí)，容易引起像素點(diǎn)的誤生長(zhǎng)。

2．2區(qū)域生長(zhǎng)

用區(qū)域生長(zhǎng)方法對(duì)圖像進(jìn)行初始劃分。該方法利用圖像區(qū)域或像素之間的連續(xù)性與鄰接性來(lái)進(jìn)行處理。根據(jù)事前定義的規(guī)則將像素或子區(qū)域聚合成更大的區(qū)域[10]。它的基本思路是從一個(gè)或多個(gè)種子點(diǎn)出發(fā)，不斷地加入滿足相似性規(guī)則的鄰居點(diǎn)來(lái)生長(zhǎng)出圖像區(qū)域。本文的區(qū)域生長(zhǎng)過(guò)程如下：

a)種子點(diǎn)的選擇上，每次選擇具有灰度值最大的像素點(diǎn)作為種子點(diǎn)進(jìn)行區(qū)域生長(zhǎng)。

b)在空間上采用八鄰域連通方案對(duì)鄰接的相似像素進(jìn)行搜索。

c)在相似性準(zhǔn)則的選取上，定義如下的公式用于選擇鄰近的像素：

|Iseed-I|＜λ|Imax-Imin|（5）

其中：I表示像素的灰度值；Iseed表示種子點(diǎn)的灰度值；Imax與Imin分別表示圖像中的最大灰度值與最小灰度值；λ是可調(diào)節(jié)的參數(shù)，用來(lái)控制像素之間的相似度門限，將滿足此公式的鄰接像素加入到種子區(qū)域。

d)生長(zhǎng)的過(guò)程中當(dāng)沒(méi)有像素滿足加入某個(gè)種子區(qū)域的條件時(shí)，區(qū)域生長(zhǎng)中止。

在實(shí)現(xiàn)上，程序遞歸地調(diào)用該算法直到所有的像素都被劃分區(qū)域。當(dāng)區(qū)域生長(zhǎng)完成時(shí)，輸出的是一系列空間上連續(xù)的種子區(qū)域。本文在區(qū)域生長(zhǎng)完后將一些過(guò)于瑣碎的區(qū)域(總像素少于10)簡(jiǎn)單地并入到與其鄰接的相似度最接近的一個(gè)區(qū)域中，因?yàn)檫@些區(qū)域的數(shù)量比較多，這樣做可以避免復(fù)雜的計(jì)算量；同時(shí)也不影響圖像中的主要信息，而且可以使蟻群聚類的問(wèn)題求解規(guī)模減小。

2．3改進(jìn)的蟻群聚類算法

通過(guò)第1章蟻群聚類算法描述可以看出螞蟻行走是隨機(jī)和盲目的。將圖像每個(gè)像素看做一只螞蟻，假設(shè)圖像大小為m×n，在循環(huán)搜索過(guò)程中，每個(gè)像素要和其余m×n-1個(gè)像素進(jìn)行距離和路徑選擇概率的計(jì)算，而且系統(tǒng)必須經(jīng)過(guò)多次循環(huán)才能完成聚類過(guò)程，導(dǎo)致搜索時(shí)間長(zhǎng)，整體計(jì)算量大。

針對(duì)這一問(wèn)題，BRGAC算法根據(jù)區(qū)域生長(zhǎng)后的圖像作為蟻群聚類算法的輸入，將每個(gè)區(qū)域看做螞蟻，這樣可以降低計(jì)算量和加快聚類進(jìn)程。

引導(dǎo)函數(shù)是由要解決的問(wèn)題本身提供的先驗(yàn)信息，代表數(shù)據(jù)(螞蟻)i選擇聚類中心cj的期望程度，也稱為數(shù)據(jù)i與聚類中心j之間路徑(i， j)的能見(jiàn)度(visibility)。從式(3)中可見(jiàn)，引導(dǎo)函數(shù)在路徑的選擇中，尤其是在算法處于初始階段時(shí)，起著決定性的作用。

本文用區(qū)域生長(zhǎng)后的灰度信息和空間信息來(lái)改變基本蟻群聚類算法中的引導(dǎo)函數(shù)，即區(qū)域與聚類中心的相似度，以減少螞蟻行走的盲目性，可更加準(zhǔn)確有效地引導(dǎo)蟻群聚類。改進(jìn)的引導(dǎo)函數(shù)的設(shè)置如下所述。

其中：r為聚類半徑。聚類半徑越大，引導(dǎo)函數(shù)值越大，選擇該聚類中心的概率隨之增大；區(qū)域與聚類中心之間的距離越大，引導(dǎo)函數(shù)值越小，選擇該聚類中心的概率就越小；區(qū)域與聚類中心之間的平均灰度差越大，引導(dǎo)函數(shù)值越小，選擇聚類中心的概率也就越小。這里不僅考慮到圖像的空間特性，而且將其灰度特性也融入聚類的過(guò)程中，使得整個(gè)算法速度和精確性都有改善。

2．4BRGAC具體算法步驟

設(shè)圖像大小為Ｍ×Ｎ。

a)對(duì)圖像進(jìn)行中值濾波。

b)在沒(méi)有被標(biāo)記的像素中選擇灰度最大點(diǎn)為種子點(diǎn)。

c)根據(jù)式（5）的定義規(guī)則，取λ=0.3，進(jìn)行區(qū)域生長(zhǎng)。不斷地加入鄰近的像素并對(duì)它們進(jìn)行標(biāo)記。

d)如果還有未被標(biāo)記的像素，轉(zhuǎn)到b)；否則輸出被劃分的區(qū)域。

圖2、3中的（a）為原始圖像；（b）為區(qū)域生長(zhǎng)算法后得到的分割圖像；（c）為基本蟻群聚類算法得到的分割圖像；（d）使用本文算法得到的結(jié)果圖。

從實(shí)驗(yàn)圖像分割結(jié)果和表1的算法運(yùn)行時(shí)間比較中可以看到，采用區(qū)域生長(zhǎng)算法分割速度較快，可幾乎得不到有意義的區(qū)域。基本蟻群聚類算法分割結(jié)果比區(qū)域生長(zhǎng)算法較精確，整體上可分割出了圖像各個(gè)區(qū)域的形態(tài)，但分割效果不是完全理想，且計(jì)算時(shí)間比較長(zhǎng)。本文的方法與前兩種方法相比，分割結(jié)果更具有意義，目標(biāo)圖像的各個(gè)部分都正確地表示出。且BRGAC算法所用的時(shí)間要少于其他兩種算法。從實(shí)驗(yàn)圖的對(duì)比中還可表明，使用本文定義的引導(dǎo)函數(shù)， BRGAC算法分割的精度也大有改善。

4結(jié)束語(yǔ)

圖像分割是計(jì)算機(jī)視覺(jué)和圖像分析的重要環(huán)節(jié)。本文在對(duì)區(qū)域生長(zhǎng)算法和蟻群聚類算法模型分析的基礎(chǔ)上，指出了兩種算法的不足，提出了一種將區(qū)域生長(zhǎng)算法與智能蟻群聚類算法相結(jié)合的混合分割方法。BRGAC算法保留了兩種算法的優(yōu)點(diǎn)，有效地提高了分割速度和區(qū)域完整性。實(shí)驗(yàn)結(jié)果表明該方法能夠取得好的分割效果。

標(biāo)準(zhǔn)區(qū)域生長(zhǎng)算法依賴于用戶的交互輸入，需要不斷地根據(jù)結(jié)果調(diào)整閾值參數(shù)，過(guò)小的閾值導(dǎo)致生長(zhǎng)不完全，過(guò)大的閾值則可能導(dǎo)致過(guò)生長(zhǎng)。本文算法則是預(yù)先給一閾值參數(shù)進(jìn)行區(qū)域生長(zhǎng)，隨后用蟻群聚類算法作后續(xù)的分割處理。雖然取得較好的結(jié)果，但自適應(yīng)程度不高，這將是筆者下一步研究中要解決的問(wèn)題。

參考文獻(xiàn)：

［1］POHLE R，TOENNIES K D.Segmentation of medical images using adaptive regiongrowing[C]//Proc of SPIE.America:SPIE Press，2001:1337－1346.

[2]于水，馬范援.一種基于數(shù)據(jù)融合的醫(yī)學(xué)圖像分割方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2001，13（12）：1073－1076.

[3] 尤建潔，周則明，王平安.基于模擬退火的簡(jiǎn)化Snake 弱邊界醫(yī)學(xué)圖像分割[J].中國(guó)圖象圖形學(xué)報(bào)，2004，9（1）：11－17.

[4]DORIGO M，MANIEZZO V，COLOMI A.Ant system:optimization by a colony of cooperative learning approach to the traveling agents[J].IEEE Trans on Systems， Man， and Cybernetics，1996，26(1): 29-41.

[5] DORIGO M，GAMBARDELLA L M．Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Trans on Evolutionary Computation，1997，1(1) ：53-66．

[6] WU B，ZHENG Y，LIU S H，et al.CSIM:a document clustering algorithm based on swarm intelligence[C]//Proc of Congress on Evolutionary Computation.Hawaii:IEEE Press，2002:477-482.

[7]楊新斌，孫京誥，黃道．一種進(jìn)化聚類學(xué)習(xí)新方法[J].計(jì)算機(jī)工程與應(yīng)用， 2003，39(15) ：60-62．

[8] CHU S C，RODDICK J F，PAN J S.Ant colony system with communication strategies[J].Information Science，2004，167(1-4): 63-76.

[9] DORIGOM.Guest editorial:special section on ant colony optimization[J].IEEE Trans on Evolutionary Computation，2002，6(4):317-319.

[10]WEICKERT J.Applications of nonlinear diffusion in image processing and computer vision[J].Acta Mathematica Universitatis Come-nianae，2001，70(1):33-50.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”