基于改進(jìn)遺傳算法的圖像分割

高 欣， 卓東風(fēng)， 劉國(guó)洋

（太原科技大學(xué) 電子信息工程學(xué)院，山西 太原 030024）

0 引言

在對(duì)圖像的研究中，圖像分割[1]是由圖像處理到圖像分析的重要步驟。圖像分割是根據(jù)圖像的灰度、顏色、幾何特性等，把圖像分成各具特色的區(qū)域，將圖像中感興趣的部分分割出來(lái)，圖像分割的好壞直接影響到圖像分析的結(jié)果，因此具有很重要的意義。圖像分割的常用方法有閾值分割法，邊緣檢測(cè)法和區(qū)域分割法等，其中閾值分割法是最基本，應(yīng)用最廣泛的分割方法。許多學(xué)者已經(jīng)提出了很多閾值分割的方法，其中OTSU提出的最大類(lèi)間方差準(zhǔn)則[2-3]來(lái)選取閾值的方法被認(rèn)為是閾值分割的經(jīng)典方法。由于多數(shù)圖像不是簡(jiǎn)單的單峰，對(duì)于那些灰度直方圖的灰度級(jí)分布谷底不明顯的復(fù)雜圖像，單一的使用 OTSU準(zhǔn)則并不能從圖像中穩(wěn)定可靠的將目標(biāo)分割出來(lái)，很難達(dá)到滿(mǎn)意的效果。很多人用遺傳算法和 OTSU法結(jié)合來(lái)解決上述問(wèn)題，但是傳統(tǒng)的遺傳算法容易出現(xiàn)早熟收斂現(xiàn)象。為此本文對(duì)基本遺傳算法進(jìn)行改進(jìn)，提出一種改進(jìn)的遺傳算法與 OTSU法則結(jié)合的優(yōu)化算法。本文根據(jù)指數(shù)變換法的特點(diǎn)提出了一種基于指數(shù)變換的非線性的動(dòng)態(tài)適應(yīng)度函數(shù)[4]，使得對(duì)種群中個(gè)體的評(píng)價(jià)更為合理，從而保證算法的收斂性，避免早熟，提高全局搜索能力。

1 相關(guān)算法

1.1 OTSU分割方法

1979 年，N.OTSU提出最大類(lèi)間方差法（稱(chēng)為OTSU法），是一種性能良好的自動(dòng)閾值選擇方法，直接計(jì)算出閾值，不需要對(duì)直方圖做預(yù)處理，計(jì)算簡(jiǎn)單，穩(wěn)定有效，優(yōu)于其他閾值化算法，受到廣泛關(guān)注。它的基本思想是以某一灰度值為閾值將圖像中的像素分成兩類(lèi)，計(jì)算它們的方差。差值越大，目標(biāo)和背景之間的差異越大，差值最大時(shí)所得的灰度值為最佳閾值[5]。

設(shè)要待分圖像的像素為N，灰度級(jí)為L(zhǎng)個(gè)（0,1,2,…,L-1），灰度值i的像素值為ni，那么各灰度值的概率設(shè)閾值k將圖像分成兩類(lèi)c0和c1（目標(biāo)和背景），則c0類(lèi)和c1類(lèi)的灰度值分別是（0,1,…,k）和（k+1,k+2,…,L-1）。c0類(lèi)和c1類(lèi)產(chǎn)生的概率分別為：

c0類(lèi)和c1類(lèi)平均灰度值分別為：

整體灰度平均值為：

其中閾值為k時(shí)灰度的平均值為：

兩類(lèi)方差公式為：

變化0到L-1之間的k值，使得d(k)最大，此時(shí)k的取值為則k*為最佳分割閾值。因此，要計(jì)算出maxd(k)，必須對(duì)0到L-1之間所有的灰度值進(jìn)行方差計(jì)算，計(jì)算量非常大，所以尋找一種有效快速的計(jì)算方法非常重要。

1.2 遺傳算法

遺傳算法[6-8]（GA，Genetic Algorithm）是模擬生物進(jìn)化自然選擇和遺傳機(jī)制的一種尋優(yōu)算法。模擬了生物進(jìn)化機(jī)制，自然選擇和遺傳進(jìn)化中發(fā)生的繁殖、交配和突變現(xiàn)象。遺傳算法在求解之前，首先要進(jìn)行編碼，將問(wèn)題空間的可行解表示成遺傳空間的串結(jié)構(gòu)數(shù)據(jù)，生成一個(gè)可能潛在解集的初始種群，按照優(yōu)勝劣汰，適者生存的原則，逐步演化產(chǎn)生出一群新的更適應(yīng)環(huán)境的個(gè)體，使群體進(jìn)化到搜索空間中越來(lái)越好的區(qū)域。在每一代，根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度選擇個(gè)體，進(jìn)行交叉組合和變異，一代又一代不斷繁殖、進(jìn)化，最后收斂到一群最適應(yīng)環(huán)境的個(gè)體并解碼，作為問(wèn)題的最優(yōu)解或近似最優(yōu)解。

1.3 改進(jìn)遺傳算法

遺傳算法在搜索選擇中以適應(yīng)度函數(shù)為依據(jù)，利用種群中每個(gè)個(gè)體的適應(yīng)度值來(lái)進(jìn)行搜索，即用個(gè)體的適應(yīng)度值對(duì)解的質(zhì)量進(jìn)行評(píng)價(jià)，適應(yīng)度越高，解的質(zhì)量越好，該個(gè)體被選擇的幾率越大，因此選擇合適的評(píng)價(jià)函數(shù)至關(guān)重要。一般基于遺傳算法的OTSU分割方法用公式7直接作為適應(yīng)度函數(shù)。但在實(shí)際中，遺傳進(jìn)化初期，往往會(huì)產(chǎn)生一些超常個(gè)體，他們的適應(yīng)度值遠(yuǎn)高于其他個(gè)體適應(yīng)度值，這些超常個(gè)體因?yàn)楦?jìng)爭(zhēng)力太強(qiáng)而控制了選擇過(guò)程，導(dǎo)致早熟收斂現(xiàn)象，影響算法的全局優(yōu)化；在進(jìn)化過(guò)程中，會(huì)出現(xiàn)群體的平均適應(yīng)度已接近最佳個(gè)體適應(yīng)度，減弱個(gè)體間的競(jìng)爭(zhēng)力，使優(yōu)化過(guò)程無(wú)法趨于最優(yōu)解。對(duì)于這2種情況，前者需要降低個(gè)體的適應(yīng)度值，后者需要放大適應(yīng)度值，以保證群體的多樣性。所以本文提出基于指數(shù)變換的非線性的動(dòng)態(tài)適應(yīng)度函數(shù)，將公式7進(jìn)行改進(jìn)之后作為遺傳算法的評(píng)價(jià)函數(shù)。改進(jìn)后的新適應(yīng)度函數(shù)為：

式（8）中，d*(k)是得到的新的適應(yīng)度函數(shù)，a是一個(gè)隨進(jìn)化代數(shù)增加而逐漸增加的動(dòng)態(tài)變化的正數(shù)，t是當(dāng)前的進(jìn)化代數(shù)，T是最大遺傳代數(shù)，davg是當(dāng)前種群的平均值。

基于改進(jìn)遺傳算法的OTSU分割算法

算法步驟如下：

①編碼：由于圖像灰度值在0～255，對(duì)應(yīng)一個(gè)8位二進(jìn)制數(shù)，將染色體編成8位二進(jìn)制碼。

②生成初始種群：產(chǎn)生規(guī)模為100的初始種群，設(shè)置最大進(jìn)化代數(shù)為50，交叉概率Pc=0.6，變異概率Pm=0.02。

③適應(yīng)度評(píng)估檢測(cè)：以式（8）為適應(yīng)度函數(shù)。

④選擇：從當(dāng)前種群中選擇優(yōu)良的（適應(yīng)度高的）個(gè)體，復(fù)制到下一代新種群中，舍棄適應(yīng)度低的個(gè)體。

⑤交叉：對(duì)染色體中的某些相同的基因位按交叉概率Pc進(jìn)行交換，產(chǎn)生新的種群。

⑥變異：變異就是對(duì)種群某個(gè)個(gè)體中的某些位進(jìn)行異位，其異位的多少由變異概率Pm來(lái)決定從而形成新一代群體。

⑦終止條件：當(dāng)算法執(zhí)行到最大迭代次數(shù)或群體中的最高適應(yīng)度值變化不大時(shí)，算法停止運(yùn)行，對(duì)具有最高適應(yīng)度值的個(gè)體進(jìn)行解碼，即可求得最佳分割閾值k。

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

為了驗(yàn)證上述方法的有效性和準(zhǔn)確性，分別用基于遺傳算法的OTSU圖像分割算法和基于改進(jìn)遺傳算法的OTSU圖像分割算法在matlab環(huán)境下對(duì)灰度級(jí)為256圖像進(jìn)行分割實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明（如圖1所示），采用遺傳算法的OTSU圖像分割算法分割的圖像清晰，改進(jìn)的算法較之經(jīng)典遺傳算法在時(shí)間方面雖略有增加，但表現(xiàn)出了更好的全局搜索能力，突出感興趣的區(qū)域，獲得的分割效果更佳。

圖1 OTSU圖像

3 結(jié)語(yǔ)

本文針對(duì)標(biāo)準(zhǔn)遺傳算法易于早熟陷入局部最優(yōu)的不足，提出了一種改進(jìn)的基于遺傳算法的OTSU分割方法，用動(dòng)態(tài)的適應(yīng)度函數(shù)評(píng)價(jià)選擇個(gè)體，保證了算法初期種群的多樣性，提高了后期較優(yōu)個(gè)體的適應(yīng)度，有效地克服了早收斂。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法較之傳統(tǒng)的遺傳算法，獲得的分割效果更好。

[1]章毓晉.圖像處理和分析[M].清華大學(xué)出版社，1999(03):179-180.

[2]劉建莊，栗文青.灰度圖像的二維Otsu自動(dòng)閾值分割法.[J]自動(dòng)化學(xué)報(bào)，1993，19(01):101-105.

[3]肖超云，朱偉興.基于Otsu準(zhǔn)則及圖像熵的閾值分割算法[J].計(jì)算機(jī)工程，2007，33(07)：188-189，209

[4]張思才，張方曉. 一種遺傳算法適應(yīng)度函數(shù)的改進(jìn)方法[J].計(jì)算機(jī)應(yīng)用與軟件，2006，23(02):108-110.

[5]譚志存.遺傳聚類(lèi)算法及其在圖像分割中的應(yīng)用[D].重慶：西南大學(xué)，2009.

[6]李樂(lè),陳鴻昶.一種改進(jìn)的遺傳算法在聚類(lèi)分析中的應(yīng)用[J].通信技術(shù)，2009,42(03):263-265.

[7]薛嵐燕，程麗. 基于最大方差法和改進(jìn)遺傳算法的圖像分割[J].計(jì)算機(jī)應(yīng)用與軟件，2008,2(25)：221-222，247.

[8]楊淑瑩.模式識(shí)別與智能計(jì)算——matlab技術(shù)實(shí)現(xiàn)[M].北京：電子工業(yè)出版社，2008.