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

吳小菁，陳星娥

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

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

1 蟻群算法基本原理

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

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

圖1 螞蟻覓食抽象圖

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

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

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

首先把256 色的灰度圖像按照一定的要求分成C 類，可以看作是螞蟻要經過256 個灰度級找尋食物，通過每一個灰度級都要對其進行類別劃分，隨后前進一步，而每一步的選擇都要劃分類別數進行確定。對于第二類問題一共有2256種方法［6］。所以，這個問題的編碼長度是256 位，每一位解元素的數值表示對應灰度級被劃分到相應的類別標記。

2.2 確定相對應的適應函數

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

2.3 優化途徑

2.3.1 構建解串

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

2.3.2 小范圍搜索

采用點式變異進行局部搜索。先從生成服從均勻布列的［0，1］之間的隨機數，序列的長度就等于解的長度，代表對應解中某位能否發生變異的概率。假若某一個隨機的數值比設定的概率閾值小，那么對應解中該位的標記就要發生變異。如果灰度級L 被選中進行變異，那么產生均勻分布的［1，c］間的隨機整數就會代替原來的類別號。隨后計算新解的適應度，假如比原來的適應度優良，就能夠取代變異前的解串。

2.3.3 更新信息素，確定控制參數

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

3 結語

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

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

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

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

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

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

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

［7］白楊，孫躍，王君，等.基于動態自適應蟻群算法的MRI 圖像分割［J］.計算機科學，2008(2):226－229.

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