摘? 要: 提出一種應用于圖像分割的改進遺傳算法,算法中引入了優(yōu)生算子、改進的變異算子和新個體,避免了局部早熟,提高了收斂速度和全局收斂能力。

　　關鍵詞: 圖像分割? 遺傳算法? 優(yōu)生算子? 新個體

?

　　圖像處理在工業(yè)自動化、在線產(chǎn)品檢驗、生產(chǎn)過程控制、遙感、生物醫(yī)學圖像分析和保安監(jiān)視等方面得到了廣泛的應用。在各種圖像應用中,對圖像目標的提取、測量等都離不開圖像分割。分割的準確性直接影響后續(xù)任務的有效性,因此圖像分割具有十分重要的意義。

　　遺傳算法具有全局搜索能力,是一種迭代式的優(yōu)化算法,在分割圖像時常用來幫助確定最佳分割閾值。將模糊C-均值算法與遺傳算法結合用于圖像分割可得到比較好的結果。本文提出一種適合于圖像分割的遺傳算法,并在初始化種群、變異操作和引進新個體方面提出了新的觀點和方法。實驗結果證明效果顯著。

1? 適用于圖像分割的改進遺傳算法

1.1 算法的基本原理

1.1.1 編? 碼

　　基于坐標位置的閾值分割法(閾值曲面方法)具有抗噪聲能力強的特點,對一些用單閾值分割法不易分割的圖像(如目標和背景的灰度有梯度變化的圖像)有較好的效果。實驗中,選用閾值曲面方法來進行遺傳編碼。將染色體編碼成以各象素的分割閾值為元素的二維矩陣,也就是將基因座排成二維數(shù)組,每個基因座對應圖像的一個象素,基因座上的等位基因是該對應象素的分割閾值,這樣每個染色體代表一個閾值曲面。由于閾值是[0,255]內(nèi)的整數(shù),所以算法采用整數(shù)編碼。這樣所有染色體構成包括256M*N個閾值曲面的解空間。

1.1.2 初始化種群

　　為了加快收斂速度,可以在種群初始化階段進行改進,引入優(yōu)生操作算子,即先用傳統(tǒng)閾值分割方法產(chǎn)生一個閾值作為種子閾值T0,用該種子閾值T0產(chǎn)生一個等閾值平面。再對閾值平面疊加隨機擾動,得到閾值曲面:

　　如此重復,直至完成K個帶有隨機擾動閾值曲面的初始化個體。random(x,y)為一隨機函數(shù),可產(chǎn)生一個隨機數(shù)r(x

1.1.3 設計適應度函數(shù)

　　設計一個好的適應度函數(shù),對一個進化算法是否成功起決定性作用,尤其對圖像閾值分割的遺傳算法。因為到目前為止,并沒有一個適合所有圖像的統(tǒng)一模式的閾值分割。所以其適應度函數(shù)的設計并無嚴格限制,有很多種構造適應度函數(shù)方法。不同的構造方法,達到的效果也不同。在實驗中,采用如下的適應度函數(shù)構造方法。

利用一種Hopfield網(wǎng)絡的能量函數(shù):

　　其中,R(x,y)是拉普拉斯操作數(shù)運算的結果。E1可以看作是拉普拉斯表達式的能量形式,已證明對閾值曲面應滿足R(x,y)=0,即E₁=0。E₂、E₃和E₄都是一致性度量。E₂越小表示相鄰象素的分割閾值應該越接近;E₃越小表示原始圖梯度和閾值曲面梯度的拓撲結構越相近;E₄越小表示原始圖灰度曲面和閾值曲面的拓撲結構越相近;E₃和E₄的引入有助于消除偽目標。當網(wǎng)絡收斂接近最優(yōu)解時上述能量函數(shù)均趨向于最小值。但由于遺傳算法按最大適應度準則搜索,所以實際應用中要先對各項能量函數(shù)分量歸一化并取反,即定義適應度函數(shù)F(Fitness):

　　上式中C1～C4是歸一化因子,依次取值為:

1.1.4 交? 叉

　　考慮到圖像處理的特殊性,選用窗口交叉方法進行操作,也就是把2個染色體基因中的多段同時進行交叉。

1.1.5 變? 異

　　在實驗的基礎上,采用了整數(shù)編碼變異,同時考慮到圖像數(shù)據(jù)相鄰象素相關性強的特點,定義如下變異操作:

　　上式中,g_mn表示需進行變異操作的基因,m、n分別為該基因在染色體二維矩陣(M×N)中的行、列位置。t為系數(shù),可根據(jù)需要設為不同值。上式表示,當基因g_mn需要變異操作時,構造以g_mn為中心,以2t為邊長的矩形,用該矩形內(nèi)所有基因的平均值替換g_mn的值。值得注意的是,由(1)式的結構可知,處于染色體邊緣的基因不能進行變異操作,但由于欲分割的目標一般處于圖像中央,所以略去這些基因?qū)Ψ指罱Y果影響不大。

1.1.6 引入新個體

　　為了保持種群多樣性,避免局部早熟,考慮引入一個特殊操作數(shù)。考慮到圖像數(shù)據(jù)的特殊性,把該操作數(shù)定義為:當父代染色體經(jīng)過交叉和變異后生成子代種群C₁,以C₁中各染色體的基因的平均值為基因值,生成一個新個體(X_new),然后用該個體替換C₁中的最差個體從而生成新的子代種群。X_new定義如下:

　　值得注意的是,由于圖像數(shù)據(jù)的基因值是二維矩陣,因此基因值的平均值是指各矩陣同一位置元素的平均值。

1.2 算法步驟

　　(1)確定控制參數(shù),包括種群規(guī)模、變異率、交叉率和世代數(shù)。(2)初始化種群。先用迭代法生成種子閾值T0,然后生成閾值平面,再通過隨機加擾完成種群初始化。(3)用適應度函數(shù)評價父代染色體并排序,保留最優(yōu)染色體。(4)選擇、交叉和變異,生成子代種群C1。(5)引入新個體,生成新的子代種群。(6)判斷是否滿足收斂條件,若滿足則輸出結果,并退出;否則,轉(zhuǎn)入步驟(3)。

2? 應用實例

2.1 參數(shù)設定及程序?qū)崿F(xiàn)

　　實驗中,采用256級灰度圖像,圖像尺寸為128×128(單位為象素)。種群規(guī)模為100,平均疊代次數(shù)為822,交叉率為0.2,變異率為0.01。所有程序都是用VC++6.0在Win98環(huán)境下編譯完成。部分程序?qū)崿F(xiàn)方法如下。

　　(1)設計一個新類Class GASegment。所有的遺傳操作都被分別設計成函數(shù)模塊,以成員函數(shù)的形式封裝在類GASegment中。(2)染色體設計成結構體Struct genotype。結構體genotype中定義了染色體基因值、變異率和交叉率等變量。(3)種群初始化在構造函數(shù)GASegment(LONG temp)中實現(xiàn)。(4)定義一個全局API函數(shù)。

　　BOOL WINAPI GaSegmentMain(LPSTR lpDIBBits,LONG lWidth,LONG lHeight);調(diào)用該API函數(shù)實現(xiàn)一次遺傳分割操作。

2.2 實驗結果

　　疊代法分割與遺傳分割的實驗測試結果如圖1所示。可以看出,改進的遺傳分割算法的分割效果明顯優(yōu)于傳統(tǒng)疊代法。

?

3? 結? 論

　　本文提出的遺傳分割算法充分考慮了圖像數(shù)據(jù)本身的特殊性,從提高全局搜索能力和收斂速度出發(fā),加入了三個新的操作策略。算法在初始化種群階段引入了優(yōu)生算子,而且改進的變異操作使遺傳算法的收斂速度大大提高。在形成新種群階段引入新個體避免了局部早熟,提高了全局收斂能力。以基于坐標的閾值分割方法為基礎進行二維實數(shù)編碼,采用窗口交叉方法,利用Hopfield網(wǎng)絡的能量函數(shù)形式來構造適應度函數(shù)。實驗結果表明,改進遺傳分割算法的分割效果明顯優(yōu)于傳統(tǒng)分割算法。

?

參考文獻

1? Nikhil R P,Sanker K P.A Review on Image Segmentation Techniques.Pattern Recognition,1993;26(9)

2? 章毓晉.圖像分割.北京:科學出版社,2001

3? 王愛民,沉蘭蓀.圖像分割研究綜述.測控技術,2000;19(5)

4? 鄭宏,潘勵.基于遺傳算法的圖像閾值的自動選取.中國圖像學報,1999;4(4)

5? 王培珍,杜培明,陳維男.一種多閾值圖像自動分割的混合遺傳算法.中國圖像圖形學報,2000;5(1)