基于蟻群算法和C－means 算法的圖像分割方法

吳小菁，陳星娥

(福建江夏學(xué)院，福建福州 350108)

圖像分割是對(duì)圖像進(jìn)行處理以及計(jì)算機(jī)視覺領(lǐng)域的最基礎(chǔ)工作，具有很多種分割辦法。而第一代編碼技術(shù)主要依據(jù)波形編碼，利用像素來表示圖像;第二代編碼主要針對(duì)圖像內(nèi)容進(jìn)行編碼，其信源模型利用對(duì)圖像的劃分，讓它們變成很多不一樣的對(duì)象，隨后對(duì)每個(gè)對(duì)象進(jìn)行編碼，通過一個(gè)統(tǒng)一程序，發(fā)送運(yùn)動(dòng)的軌跡和紋理。此外，可以參照人們視覺的愛好對(duì)象進(jìn)行分配比特?cái)?shù)。和波形的編碼壓縮法比較，這種方式具有更高的效率，也為查詢對(duì)象的內(nèi)容夯實(shí)了基礎(chǔ)。

1 蟻群算法基本原理

螞蟻會(huì)在行走的路線上釋放信息素以實(shí)現(xiàn)和其他螞蟻的間接交流，啟發(fā)了蟻群算法的誕生，該算法有信息素?fù)]發(fā)、正反饋兩種機(jī)制［1］。從蟻穴到食物源會(huì)存在多條路徑，但絕大多數(shù)螞蟻都能選擇出最短的路徑，就是利用了正反饋機(jī)制，因?yàn)閱挝粫r(shí)間內(nèi)最短路徑上通過的螞蟻數(shù)量較多，信息素含量也就會(huì)隨之增多，吸引越來越多的螞蟻，最終實(shí)現(xiàn)螞蟻都經(jīng)過最短路徑尋找食物源或返回蟻穴;信息素?fù)]發(fā)則可避免路徑上信息素含量的大幅增加。蟻群算法中的螞蟻與現(xiàn)實(shí)中的螞蟻存在區(qū)別:蟻群算法中的螞蟻并不是完全依照信息素強(qiáng)度進(jìn)行路徑選擇，它們具有記憶區(qū)，而且還處在離散時(shí)間狀態(tài)中。如圖1 可進(jìn)行抽象說明:(a)表明蟻群螞蟻沿著A－E 路徑行走;(b)說明當(dāng)出現(xiàn)障礙物時(shí)，螞蟻們會(huì)分成兩條路徑行走;(c)顯示絕大部分螞蟻都會(huì)選擇較短路徑行走，較短路徑上聚集了更多的信息素，吸引越來越多的螞蟻選擇。

如圖1 所示，設(shè)定A 點(diǎn)為蟻穴，E 點(diǎn)是食物源，HC 是障礙物。螞蟻行走要繞開障礙物，有兩種選擇，經(jīng)過H或經(jīng)過C 到達(dá)食物源，路徑距離為:BH=HD=1，BC=CD=0.5。假設(shè)t=1 的時(shí)候，有30 只螞蟻從蟻穴出發(fā)去往食物源，路徑上沒有信息素，螞蟻分開繞行，BH 和BC 均有15 只螞蟻選擇，由于信息素會(huì)伴隨時(shí)間的流逝而逐漸揮發(fā)，如果螞蟻群的運(yùn)動(dòng)速度一樣，路徑信息素的留余會(huì)和路徑長(zhǎng)度成反比，而螞蟻算法和路徑的概率與信息濃度成正比，所以BH、DH 路徑上螞蟻留下的信息素?fù)]發(fā)量是BC、DC 路徑上的2 倍。t=2 時(shí)，30 只螞蟻返回蟻穴，就會(huì)選取信息量濃度較多的DC 和BC 路徑，也就是說有20 只螞蟻會(huì)選擇DCB 路徑，而同時(shí)有15 只DHB 路徑［2－3］。照此推理，經(jīng)較長(zhǎng)時(shí)間運(yùn)動(dòng)后，選擇DCB 路徑的螞蟻會(huì)越來越多，最終都選擇DCB 路徑。

圖1 螞蟻覓食抽象圖

2 基于蟻群算法和C－means 算法的圖像分割算法

采用蟻群算法進(jìn)行圖像分割的主要指導(dǎo)思想是:由于圖像分割是一種把圖像中全部的像素記作不同類別的過程，在應(yīng)用蟻群算法求解時(shí)，螞蟻會(huì)對(duì)圖像中的全部像素進(jìn)行分類標(biāo)記，記下每個(gè)像素中相對(duì)應(yīng)的類別就組成了解決圖像分割問題的一個(gè)解。如果把一幅圖像分為C 類，在此基礎(chǔ)上，把每個(gè)像素依據(jù)一定的規(guī)則劃分到C 類中的某一類。那么對(duì)于一張M×M 面積的影像來說，共有CM－M種劃法，一般情況下，根據(jù)固定的劃分判斷標(biāo)準(zhǔn)選取一種最佳劃分方法從而達(dá)到分割圖像的目標(biāo)，如果像素的空間較大，相應(yīng)的劃分?jǐn)?shù)量也會(huì)較大;如果把這一個(gè)聚類過程直接在像素集合方面進(jìn)行的話，分割過程中的計(jì)算量也是驚人的［4－5］。從本質(zhì)來講，聚類算法是利用像素的灰度信息，以圖像中存在的灰度級(jí)別作為分析的對(duì)象，能夠減少搜索的劃分組合數(shù)，縮短計(jì)算時(shí)間。采用蟻群算法解決聚類問題的流程如下:

2.1 解析問題，確定問題的編碼

首先把256 色的灰度圖像按照一定的要求分成C 類，可以看作是螞蟻要經(jīng)過256 個(gè)灰度級(jí)找尋食物，通過每一個(gè)灰度級(jí)都要對(duì)其進(jìn)行類別劃分，隨后前進(jìn)一步，而每一步的選擇都要?jiǎng)澐诸悇e數(shù)進(jìn)行確定。對(duì)于第二類問題一共有2256種方法［6］。所以，這個(gè)問題的編碼長(zhǎng)度是256 位，每一位解元素的數(shù)值表示對(duì)應(yīng)灰度級(jí)被劃分到相應(yīng)的類別標(biāo)記。

2.2 確定相對(duì)應(yīng)的適應(yīng)函數(shù)

如果x=(x1，y1)表示一個(gè)像素的坐標(biāo)，而g(x)表示像素的灰度數(shù)值，則C－means 算法就要最小化。而C－means 的值越小，表明聚類的效果越好;值越大，適應(yīng)度的函數(shù)數(shù)值越大，說明計(jì)算所得的解的質(zhì)量越好。

2.3 優(yōu)化途徑

2.3.1 構(gòu)建解串

假若選用N 只螞蟻來尋求問題的解，那么對(duì)于256 色的灰度影像，所得解的長(zhǎng)度就等于256。為了建立一個(gè)解，螞蟻會(huì)采用信息軌跡以及啟發(fā)信息對(duì)每個(gè)灰度級(jí)進(jìn)行標(biāo)記。在算法的初步階段，信息素矩陣就會(huì)被初始化成一個(gè)很小的數(shù)值。每一個(gè)灰度級(jí)具有相應(yīng)的信息素濃度，一共有C 種。對(duì)于這種問題，信息素的矩陣大小一共有256 ×C，并且隨著迭代的進(jìn)行而不斷地進(jìn)化。把灰度級(jí)和待標(biāo)記類的灰度中心距離當(dāng)作啟發(fā)信息，假如灰度級(jí)和某一個(gè)種類的灰度中心相距較近，則說明該類的可能性很大［7］。因此螞蟻第一次漫游對(duì)灰度級(jí)進(jìn)行劃分時(shí)，起初的類中心都是隨機(jī)選取的，隨后的迭代中類中心是通過最優(yōu)解求得的。

2.3.2 小范圍搜索

采用點(diǎn)式變異進(jìn)行局部搜索。先從生成服從均勻布列的［0，1］之間的隨機(jī)數(shù)，序列的長(zhǎng)度就等于解的長(zhǎng)度，代表對(duì)應(yīng)解中某位能否發(fā)生變異的概率。假若某一個(gè)隨機(jī)的數(shù)值比設(shè)定的概率閾值小，那么對(duì)應(yīng)解中該位的標(biāo)記就要發(fā)生變異。如果灰度級(jí)L 被選中進(jìn)行變異，那么產(chǎn)生均勻分布的［1，c］間的隨機(jī)整數(shù)就會(huì)代替原來的類別號(hào)。隨后計(jì)算新解的適應(yīng)度，假如比原來的適應(yīng)度優(yōu)良，就能夠取代變異前的解串。

2.3.3 更新信息素，確定控制參數(shù)

在完成迭代以后，要從螞蟻群中選取質(zhì)量最好的20%的螞蟻更新信息素。采用最優(yōu)解的保留方法，在循環(huán)過程中建立一個(gè)全局最優(yōu)解，把它作為全局的變量保存起來。假如迭代過程中得到的最優(yōu)解比全局的最優(yōu)解好，就可以用它代替全局的最優(yōu)解;如果相反，則保持最優(yōu)解不變［8］。每一個(gè)類別中的類中心都要根據(jù)最優(yōu)解來解答。蟻群算法的控制參數(shù)主要有蟻群規(guī)模、局部搜索比例、搜索概率、循環(huán)次數(shù)等，選擇最大的運(yùn)行次數(shù)作為終止的條件，把適應(yīng)度最大的劃分當(dāng)作聚類的結(jié)果。

3 結(jié)語

基于蟻群算法和C－means 算法的圖像分割方法能夠比一般的C－means 算法獲得更好的聚類結(jié)果主要原因在于，蟻群算法在搜尋最優(yōu)解的過程中采用的是群體尋優(yōu)的方法，經(jīng)過無數(shù)次的迭代操作以后，消除了初始類中心選擇不佳的影響，經(jīng)過在較優(yōu)解元素的基礎(chǔ)上釋放出更多的信息素，使得群體合作搜索的方法讓解的質(zhì)量整體向更好的方向轉(zhuǎn)化，最后生成了很好的解。總之，蟻群算法和C－means 算法相結(jié)合的圖像分割方法，使分割結(jié)果有了較大程度的改善，使得聚類的精度更高，具有很大的應(yīng)用前景。

［1］湯可宗，江新姿，高尚.蟻群模糊聚類的圖像分割［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008(7):1770－1771.

［2］葉志偉，常勝，高山.基于蟻群算法的最佳熵圖像分割閾值方法［J］.湖北民族學(xué)院學(xué)報(bào):自然科學(xué)版，2007(3):304－307.

［3］盧玨.基于自適應(yīng)蟻群算法的圖像分割［J］.ITS 通訊，2005(4):886－889.

［4］何小娜，逄煥利.基于二維直方圖和改進(jìn)蟻群聚類的圖像分割［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010(3):128－131.

［5］趙娜，王希常，劉江.自適應(yīng)蟻群算法優(yōu)化紅外圖像分割［J］.計(jì)算機(jī)應(yīng)用研究，2009(11):4375－4377.

［6］葉志偉.一種基于蟻群算法和C－Means 算法的圖像分割方法［J］.激光與紅外，2007(13):106－107.

［7］白楊，孫躍，王君，等.基于動(dòng)態(tài)自適應(yīng)蟻群算法的MRI 圖像分割［J］.計(jì)算機(jī)科學(xué)，2008(2):226－229.

［8］王爽，黃友銳，李冬.基于蟻群算法的改進(jìn)Otsu 理論的圖像多閾值分割［J］.微計(jì)算機(jī)應(yīng)用，2008(4):25－28.