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

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

?

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

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

1? 適用于圖像分割的改進(jìn)遺傳算法

1.1 算法的基本原理

1.1.1 編? 碼

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

1.1.2 初始化種群

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

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

1.1.3 設(shè)計(jì)適應(yīng)度函數(shù)

　　設(shè)計(jì)一個(gè)好的適應(yīng)度函數(shù),對(duì)一個(gè)進(jìn)化算法是否成功起決定性作用,尤其對(duì)圖像閾值分割的遺傳算法。因?yàn)榈侥壳盀橹?并沒(méi)有一個(gè)適合所有圖像的統(tǒng)一模式的閾值分割。所以其適應(yīng)度函數(shù)的設(shè)計(jì)并無(wú)嚴(yán)格限制,有很多種構(gòu)造適應(yīng)度函數(shù)方法。不同的構(gòu)造方法,達(dá)到的效果也不同。在實(shí)驗(yàn)中,采用如下的適應(yīng)度函數(shù)構(gòu)造方法。

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

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

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

1.1.4 交? 叉

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

1.1.5 變? 異

　　在實(shí)驗(yàn)的基礎(chǔ)上,采用了整數(shù)編碼變異,同時(shí)考慮到圖像數(shù)據(jù)相鄰象素相關(guān)性強(qiáng)的特點(diǎn),定義如下變異操作:

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

1.1.6 引入新個(gè)體

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

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

1.2 算法步驟

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

2? 應(yīng)用實(shí)例

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

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

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

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

2.2 實(shí)驗(yàn)結(jié)果

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

?

3? 結(jié)? 論

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

?

參考文獻(xiàn)

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

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

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

4? 鄭宏,潘勵(lì).基于遺傳算法的圖像閾值的自動(dòng)選取.中國(guó)圖像學(xué)報(bào),1999;4(4)

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