基于改進(jìn)遺傳算法的最佳熵閾值圖像分割法

王學(xué)忠，徐麗萍，吳海燕

安徽三聯(lián)學(xué)院電子電氣工程學(xué)院，合肥，230601

圖像分割是利用計(jì)算機(jī)對圖像進(jìn)行分析的第一步，也是圖像處理的關(guān)鍵技術(shù)，是將一幅圖像分解成若干具有性質(zhì)特殊、互不重疊區(qū)域的過程，圖像分割也是計(jì)算機(jī)圖像處理與機(jī)器視覺處理的最基本的研究方向和領(lǐng)域，其核心的部分就是把圖像內(nèi)容和背景內(nèi)容盡可能分割開。隨著計(jì)算機(jī)技術(shù)、數(shù)字信號處理技術(shù)以及高速DSP芯片的不斷發(fā)展，出現(xiàn)了最大類間方差法、最佳直方圖熵法等多種圖像分割技術(shù)。其中，閾值分割法的計(jì)算方法簡明、實(shí)用性強(qiáng)，是圖像分割最常用的方法，該分割方法的關(guān)鍵是確定最佳閾值。最佳閾值又有多種分割法，李賢陽和金保華等采用最大類間方差法（Otsc）進(jìn)行圖像分割，閾值計(jì)算比較穩(wěn)定，但需要計(jì)算每個像素點(diǎn)對應(yīng)的方差值，因此存在計(jì)算數(shù)據(jù)多、時(shí)間長、效率低等缺點(diǎn)［1-2］；最佳熵閾值法（簡稱KSW法）是由Kapur等提出［3］，該算法也存在計(jì)算過程復(fù)雜、計(jì)算量較大等不足；汪筱紅等將遺傳算法與最佳熵閾值分割方法相融合（Simple Genetic Algorithms KSW，SGAKSW）［4-5］進(jìn)行圖像分割，縮短了運(yùn)算時(shí)間，具有速度快、效率高等優(yōu)點(diǎn)，但存在收斂性差、閾值尋找不是最優(yōu)，最大熵的結(jié)果不穩(wěn)定，導(dǎo)致圖像分割過當(dāng)或不足等現(xiàn)象。

本文提出了改進(jìn)型遺傳閾值算法（Improve Genetic Algorithms KSW，IGA-KSW），通過精英策略和賭輪盤相結(jié)合選擇法、交叉概率與變異概率隨著進(jìn)化代數(shù)而變化的遺傳算法來計(jì)算出圖像熵的閾值，從而達(dá)到閾值最佳，獲得比較清晰、準(zhǔn)確、穩(wěn)定的圖像。

1 KSW最佳熵閾值分割法

美國著名的數(shù)學(xué)家、信息論創(chuàng)始人香農(nóng)先生最早于1948年提出了“信息熵”的概念，后來，人們把“信息熵”的概念用到了圖像分割當(dāng)中。根據(jù)香農(nóng)的“信息熵”理論，一個灰度值是｛0，1，2，3，…，l-1｝的直方圖圖像，其熵的值可以用下面的公式計(jì)算出來。即：

式中，Pi是圖像中第i個像素的灰度值在整幅圖像中出現(xiàn)的概率，t為分割閾值。t將圖像劃分成兩大區(qū)域，其中一個區(qū)域是有目標(biāo)像素所構(gòu)成的圖像（稱為目標(biāo)圖像），另一區(qū)域是有背景像素所構(gòu)成的圖像（稱為背景圖像）則：

當(dāng)閾值t將圖像劃分成兩大區(qū)域后，分別用Ⅰ和Ⅱ來表示兩個區(qū)域的圖像（即背景和目標(biāo)圖像），則Ⅰ和Ⅱ的概率分別為：

因此，目標(biāo)圖像熵 HⅠ（t）、背景圖像 HⅡ（t）分別為：

圖像總熵H（t）就是兩大區(qū)域圖像Ⅰ和Ⅱ的熵HⅠ（t）和 HⅡ（t）的和，即

最佳閾值t的值，就是當(dāng)t取得某一數(shù)值使總熵H（t）取得最大值，即：

2 基于遺傳算法最佳熵閾值分割法

遺傳算法（Genetic Algorithms，GA）就是模擬生物優(yōu)勝劣汰的進(jìn)化過程來達(dá)到搜索最優(yōu)解的目的。隨著遺傳算法在應(yīng)用領(lǐng)域的不斷擴(kuò)展，出現(xiàn)了基于機(jī)器學(xué)習(xí)的遺傳算法以及遺傳算法向模糊推理、神經(jīng)網(wǎng)絡(luò)、人工生命、圖像處理及自動控制等眾多領(lǐng)域的滲透，開拓了智能計(jì)算領(lǐng)域的新局面。

2.1 SGA-KSW基本遺傳算法的最佳熵閾值分割法

該方法就是借助于計(jì)算機(jī)及工程計(jì)算軟件Matlab，將 遺 傳 算 法 （Simple Genetic Algorithms，SGA）與KSW融合，通過多輪的循環(huán)搜索，最終找到圖像的最佳閾值。算法過程如圖1所示。

圖1 SGA-KSW算法框圖

算法步驟：

（1）編碼和產(chǎn)生初始種群。采用二進(jìn)制的方法對灰度圖像的閾值進(jìn)行編碼。初始種群要求適中，一般取20～100之間，本文采用初始種群為20。

（2）計(jì)算適應(yīng)度函數(shù)。即利用該函數(shù)求出每個個體對環(huán)境的適應(yīng)能力，通過計(jì)算結(jié)果把優(yōu)良的個體保留下來，適應(yīng)度差的個體被淘汰掉。本文算法中采用的適應(yīng)度計(jì)算公式為公式（8）。

（3）選擇。采用輪盤賭法，公式如下：

其中，pi為個體i被選中的概率，fi為個體i的適應(yīng)度，∑fi為群體的累加適應(yīng)度。

（4）交叉。將上代父體中相鄰兩個體的部分基因結(jié)構(gòu)按照預(yù)先設(shè)定的概率PC進(jìn)行交換組合產(chǎn)生新的個體的過程，PC一般取值0.4～0.9之間。

（5）變異。變異就是個體中的部分基因在遺傳過程中發(fā)生了突變，即基因由0變1或由1變0。Pm取值一般為0.001～0.04。

（6）終止。反復(fù)執(zhí)行（2）-（5）步驟，直到循環(huán)超過最大循環(huán)次數(shù)或前后平均最佳閾值差小于某個值時(shí)終止循環(huán)搜索。

2.2 IGA-KSW改進(jìn)遺傳算法最佳熵閾值分割法

第一，改進(jìn)基本遺傳算法中的步驟（3）選擇算子。傳統(tǒng)的遺傳算法是個體適應(yīng)度（即個體的熵值占群體熵累加值的概率）越大，個體被選中的概率也就越大，所有的個體都需要不斷地計(jì)算適應(yīng)度值，從而增加了算法的運(yùn)算量、降低了算法的效率，同時(shí)易破壞好的基因個體，對優(yōu)秀的個體繼承也不利；因此，本文中采用10%的精英策略和90%輪盤賭法相結(jié)合的選擇算法，具體的做法是：把上代中10%的優(yōu)秀個體（即圖像熵值比較大的，對應(yīng)個體被選概率前10%的圖像閾值）保留下來，不參與后面的輪賭選擇算法，只有余下90%的個體參與輪賭選擇算法，這樣既保護(hù)了好的基因個體不被破壞，也提高了搜索效率。

max_adapt_value1＝max（adapt_value1）；

s1（1）＝round（mean（X1（find（adapt_value1＝＝max_adapt_value1））））；

r＝rand（1，population-1）；

for i＝2：population

temp＝0；

for j＝1：population

temp＝temp+adapt_value1_new（j）；

if temp＞＝r（i-1）

s1（i）＝X1（j）；

break；

end

end

end

第二，改進(jìn)上述算法中的步驟（4）交叉算子。傳統(tǒng)的遺傳算法中，交叉概率PC一般都是取某一個固定值，一般取值0.4～0.9之間，這種固定的交叉概率不利于圖像閾值的最優(yōu)解搜索，容易陷入全局最優(yōu)、導(dǎo)致圖像分割不穩(wěn)定；本文把交叉概率由原先的一個固定值改為兩個不同的交叉概率值，基本思路是：在搜索的早期，為了獲得更多新的個體，避免圖像閾值陷入局部最優(yōu)而適當(dāng)提高交叉概率PC的值（譬如PC為0.8）；而在搜索的中后期，為了不破壞優(yōu)秀的個體，避免收斂太慢，提高搜索效率和圖像的穩(wěn)定性，適當(dāng)降低交叉概率PC的值（譬如PC為0.6），即：

PC其中K為搜索代數(shù)

這樣在搜索的初期能產(chǎn)生更多的新個體，避免早熟，在后期又可避免破壞優(yōu)良個體。

第三，改進(jìn)上述算法中的步驟（5）變異算子。

由固定的變異概率Pm改為變化的變異概率Pm，即：

通過上述的改進(jìn)、優(yōu)化變異算法后，避免早熟又可產(chǎn)生的新個體。

3 實(shí)驗(yàn)結(jié)果分析

本實(shí)驗(yàn)中，為了比較SGA-KSW和IGA-KSW兩種遺傳算法對同一圖像的分割效果，采用了初始種群均為20，循環(huán)終止的條件相同，即循環(huán)超過200代或前后平均最佳閾值差小于0.001時(shí)終止循環(huán)搜索。每種算法都分別進(jìn)行20次分割，結(jié)果如表1所示。實(shí)驗(yàn)采用的圖像是Lena，如圖2-7。圖2為Lena原始圖像；圖5為采用窮盡法所獲得的最佳閾值（142）圖像；圖3、圖4分別為基本遺傳算法所獲得最佳閾值圖像（其中最大閾值168，最小閾值80）；圖6、圖7分別為改進(jìn)遺傳算法所獲得最佳閾值圖像（其中最大閾值144，最小閾值114）。

表1 SGA-KSW算法與IGA-KSW算法的對比（20次分割）

從表1可知，兩種遺傳算法在搜尋的時(shí)間上僅 相差0.001 9秒，基本接近，但改進(jìn)后的算法獲得閾值更加穩(wěn)定，更接近最優(yōu)閾值，分割的圖像效果更好。

4 結(jié)論

本文在基本遺傳算法的最佳熵閾值分割法的基礎(chǔ)上提出了改進(jìn)型遺傳閾值算法，具體的方法是改進(jìn)基本遺傳算法中的選擇、交叉和變異的算子方法。其一，通過采用10%的精英策略和90%輪盤賭法相結(jié)合的選擇算法，把上代中10%的優(yōu)秀個體保留下來，不參與后面的輪賭選擇算法，只有余下90%的個體參與輪賭選擇算法；其二，把交叉概率由原先的一個固定值改為兩個不同的交叉概率值；其三，根據(jù)搜索的代數(shù)動態(tài)調(diào)整變異的概率。結(jié)果表明，該方法在閾值的尋優(yōu)方面要比SGA—KSW算法更好，所獲得的閾值更集中、閾值均方差進(jìn)一步縮小，平均最佳閾值得到較大改善，更接近實(shí)際最優(yōu)閾值。改進(jìn)后分割所得的圖像比較清晰、準(zhǔn)確、穩(wěn)定，明顯優(yōu)于傳統(tǒng)遺傳算法所獲得的圖像。