基于最大熵和遺傳算法的圖像分割方法研究?

余榮泉 段先華

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

圖像分割是圖像處理和計(jì)算機(jī)視覺領(lǐng)域的一個(gè)重要分支，是后續(xù)的分類、跟蹤、識(shí)別等處理的基礎(chǔ)，具有重要的研究意義。圖像分割是把圖像分成若干個(gè)特定的、具有獨(dú)特性質(zhì)的區(qū)域，然后從中找出感興趣目標(biāo)的技術(shù)和過程。在所有的圖像分割方法中，閾值法因快速、簡(jiǎn)單而得到了廣泛的應(yīng)用。閾值分割的方法有很多，例如:直方圖閾值分割［1］、最大類間方差法［2］、基于最大熵的閾值分割［3］等。其中，基于最大熵的閾值分割算法利用圖像的空間信息和灰度分布信息來定義圖像的信息熵，不需要先驗(yàn)知識(shí)，根據(jù)假設(shè)的不同或視角的不同提出熵函數(shù)準(zhǔn)則，通過優(yōu)化得到最佳閾值。該方法的缺陷是在確定閾值尤其是多閾值的時(shí)候，計(jì)算量比較大，算法復(fù)雜度高。

隨著科學(xué)技術(shù)的不斷發(fā)展，一些新理論、新方法逐漸運(yùn)用到圖像分割領(lǐng)域中，如人工神經(jīng)網(wǎng)絡(luò)［4］、深度學(xué)習(xí)［5］、模式識(shí)別［6］、模糊數(shù)學(xué)［7］、蟻群算法［8］、機(jī)器學(xué)習(xí)［9］和遺傳算法［10］等。通過閱讀文獻(xiàn)，閾值法與這其中的某些方法結(jié)合使用，可以得到較好的分割效果，無論是在算法復(fù)雜度還是圖像分割精確度上都有了較大的提升。

本文利用遺傳算法具有的并行性、魯棒性和自適應(yīng)性的優(yōu)點(diǎn)結(jié)合最大熵算法，對(duì)幾幅經(jīng)典的圖像進(jìn)行分割。仿真結(jié)果表明，改進(jìn)的算法與傳統(tǒng)的圖像分割算法相比，分割效率高，分割速度有所提高，圖像分割更加精確。

2 傳統(tǒng)最大熵閾值分割

2.1 一維最大熵閾值分割

在信息論中，熵是事件出現(xiàn)概率不確定性的量度，在圖像中它是圖像統(tǒng)計(jì)特性的一種表現(xiàn)形式，反映了圖像包含信息量的大小。將信息論中熵的概念應(yīng)用于圖像分割［11］，把圖像中目標(biāo)與背景視為兩個(gè)獨(dú)立的信源，通過分析圖像灰度直方圖的熵，找到最佳分割閾值。設(shè)圖像的灰度范圍是{0,1,…,L-1} ，圖像的分割閾值為 τ ，Pi為灰度i 出現(xiàn)的概率，i ?{0 ,1,…,L-1} 。假設(shè)圖像中像素灰度在{0 ,1,…,τ} 范圍內(nèi)的構(gòu)成目標(biāo)區(qū)域( T )，像素灰度在{τ +1,τ+2,…,L-1} 范圍內(nèi)的構(gòu)成背景區(qū)域( B )，那么它們的概率分布為

其中

對(duì)于數(shù)字圖像，定義與目標(biāo)區(qū)域和背景區(qū)域概率分布相關(guān)的熵為

其中

準(zhǔn)則函數(shù)定義為

使準(zhǔn)則函數(shù)φ( τ )取最大值的灰度級(jí)τ 即是所求出的最優(yōu)閾值τ*，即

2.2 二維最大熵閾值分割

二維最大熵法［12］是在一維最大熵法的基礎(chǔ)上進(jìn)行改進(jìn)，利用圖像中各像素的灰度值分布，結(jié)合像素點(diǎn)之間的空間分布，建立二維直方圖，計(jì)算最大熵值，并以此作為最佳閾值進(jìn)行圖像分割。和一維最大熵法相比，二維最大熵法不僅考慮了像素間的空間關(guān)系，還考慮了像素的灰度分布關(guān)系，具有更好的抗噪性能。

二維最大熵閾值分割法綜合運(yùn)用圖像像素點(diǎn)灰度和區(qū)域灰度特征表示圖像信息，具體方法如下。

設(shè)原始圖像 f( x,y )是灰度級(jí)為 L ，大小為M×N 的灰度圖像，以原始圖像中各像素及其四鄰域的四個(gè)像素為一個(gè)區(qū)域，計(jì)算出區(qū)域的灰度均值圖像。采用點(diǎn)灰度—區(qū)域灰度均值對(duì)，這樣的數(shù)據(jù)對(duì)共有L×L 對(duì)。令Pij=nij(M×N)。根據(jù)香農(nóng)熵的定義，二維離散熵定義為其中，nij表示當(dāng)前點(diǎn)灰度值為i，其四鄰域平均灰度為 j 的像素點(diǎn)對(duì)的個(gè)數(shù)，Pij是該事件發(fā)生的概率。 Pij就是該圖像關(guān)于點(diǎn)灰度—區(qū)域灰度均值的二維直方圖。如圖1 所示，閾值( )s,t 將圖像分為目標(biāo)區(qū)A 和背景區(qū)B，遠(yuǎn)離對(duì)角線的為邊界區(qū)C和噪聲區(qū)D。所以二維熵包含了目標(biāo)區(qū)A 和背景區(qū)B 的最大信息量，同時(shí)也能夠保留細(xì)節(jié)部分。在區(qū)A 和區(qū)B 上運(yùn)用點(diǎn)灰度—區(qū)域灰度均值二維最大熵法確定最大閾值，使得目標(biāo)區(qū)和背景區(qū)的信息量達(dá)到最大。

圖1 圖像二維平面直方圖

假設(shè)待分割的圖像目標(biāo)區(qū)域和背景區(qū)域都具有不同的概率分布，目標(biāo)區(qū)A 和背景區(qū)B 的概率分布分別為

目標(biāo)區(qū)A 和背景區(qū)B 的二維熵函數(shù)分別為

其中

由于邊界區(qū)C 和噪聲區(qū)D 發(fā)生的概率微小，幾乎可以忽略不計(jì)，假設(shè)它們的Pij=0，由此得:

其中

則

圖像熵的判別函數(shù)定義為

最佳閾值向量( )s,t 應(yīng)該滿足如下條件:

3 基于最大熵和遺傳算法的圖像分割

遺傳算法［13］是一種模仿生物在自然環(huán)境中遺傳和進(jìn)化，通過“優(yōu)勝劣汰”的方式，不斷遺傳變異，產(chǎn)生最佳適應(yīng)個(gè)體的方法。二維最大熵在本質(zhì)上是對(duì)圖像在二維灰度空間上搜索參數(shù)，使得目標(biāo)函數(shù)取得最大值的優(yōu)化問題，該算法計(jì)算量較大、耗時(shí)多。因此，將遺傳算法運(yùn)用于最大熵的圖像閾值分割［14～15］中，可以降低算法的復(fù)雜度。

在本文中，根據(jù)圖像區(qū)域的灰度直方圖信息，對(duì)遺傳算法的種群進(jìn)行初始化，將最大熵值函數(shù)作為遺傳算法的適應(yīng)度函數(shù)或目標(biāo)函數(shù)，對(duì)群體中的個(gè)體施加遺傳操作（選擇、交叉、變異），實(shí)現(xiàn)群體內(nèi)個(gè)體結(jié)構(gòu)重組，使得群體中的個(gè)體不斷得以優(yōu)化，最終獲得最大熵值圖像的最優(yōu)分割閾值。將遺傳算法應(yīng)用于圖像分割，算法流程如圖2 所示，算法步驟如下:

Step1:隨機(jī)產(chǎn)生初始種群。本文設(shè)置其初始代數(shù)Gen為0；

Step2:編碼。編碼是遺傳算法的基礎(chǔ)，編碼的好壞直接影響后續(xù)遺傳算法的選擇、交叉和變異的運(yùn)算。編碼［16］的方式有很多，由于圖像的灰度級(jí)在［0，255］范圍內(nèi)，所以，本文采用16 位二進(jìn)制編碼的方式對(duì)染色體進(jìn)行編碼，每個(gè)染色體都代表一個(gè)分割閾值；

Step3:設(shè)定種群規(guī)模。種群規(guī)模的設(shè)置應(yīng)該合理，規(guī)模過大，會(huì)導(dǎo)致每一代適應(yīng)度值的計(jì)算量增加；規(guī)模過小，會(huì)導(dǎo)致未成熟收斂的現(xiàn)象。實(shí)驗(yàn)中，設(shè)置種群規(guī)模為20，最大繁殖代數(shù)為100；

Step4:解碼。將二進(jìn)制染色體組解碼為［0，255］范圍內(nèi)的值，文中采用二維熵函數(shù)作為適應(yīng)度函數(shù)，對(duì)每個(gè)個(gè)體通過φ( s,t )=MAX{φ( s,t )}計(jì)算其適應(yīng)度值；

Step5:選擇。選擇的目的是從群體中選出優(yōu)良的個(gè)體，讓這些個(gè)體作為父代為下一代的繁殖做好準(zhǔn)備。文中采用了輪盤賭的方式，首先計(jì)算群體中所有個(gè)體的適應(yīng)度總和，然后計(jì)算每個(gè)個(gè)體的相對(duì)適應(yīng)度大小，最后用輪盤賭的操作確定每個(gè)個(gè)體的選中次數(shù)；

Step6:交叉。交叉也可以稱為重組，按照較大的概率（概率太低影響收斂速度）從群體中選擇兩個(gè)個(gè)體，交換兩個(gè)個(gè)體的某個(gè)或者某些位，產(chǎn)生不同于母體的子體。文中采用了單點(diǎn)交叉，交叉概率設(shè)置為0.6；

Step7:變異。變異是以較小的概率對(duì)個(gè)體編碼串上的某個(gè)或某些值進(jìn)行改變，從而產(chǎn)生新個(gè)體。采用基本的變異運(yùn)算，將染色體編碼串中的某個(gè)或某些基因座上的基因值用它的等位基因來替換，形成新個(gè)體。實(shí)驗(yàn)中設(shè)置變異概率為0.03；

Step8:判斷終止準(zhǔn)則。預(yù)先設(shè)定最大代數(shù)為20，當(dāng)算法執(zhí)行到最大代數(shù)或經(jīng)過20 代進(jìn)化，群體中的最高適應(yīng)度值仍未發(fā)生變化時(shí)，算法中止，具有最高適應(yīng)度值的個(gè)體即為分割閾值。若沒有執(zhí)行到最大代數(shù)，則重復(fù)Step4至Step7；

Step9:分割圖像。將得到的最高適應(yīng)度值作為分割閾值進(jìn)行圖像分割。

圖2 圖像閾值分割的遺傳算法流程圖

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

本文所有的仿真實(shí)驗(yàn)都是在Intel Core i3-380M、4GB 內(nèi)存，Matlab R2014a 軟件環(huán)境下完成的。為了驗(yàn)證本文提出的基于最大熵和遺傳算法的圖像分割算法的有效性，對(duì)幾幅經(jīng)典的圖像進(jìn)行了仿真。在仿真過程中，首先將圖像轉(zhuǎn)換成灰度級(jí)在［0，255］范圍內(nèi)的灰度圖像，然后繪制直方圖，最后用傳統(tǒng)的最大熵閾值分割法和本文的分割算法對(duì)圖像進(jìn)行了分割。

分別對(duì)比圖3、4、5 中的實(shí)驗(yàn)結(jié)果我們可以發(fā)現(xiàn):

圖3 Girl圖像分割

在分割效果上，與傳統(tǒng)最大熵分割結(jié)果相比，本文算法的分割效果更加逼真和精確，更富有層次感，特別是對(duì)于一些細(xì)節(jié)的分割效果。例如，圖3中的圖（d），女孩的頭發(fā)、眉毛、眼睛、嘴以及人物的輪廓，對(duì)這些細(xì)節(jié)的分割效果要優(yōu)于圖（c），人物也更加逼真；圖4 中的圖（d），左側(cè)的樹葉、草叢、房屋屋頂瓦片、樹影以及附近的那輛小轎車這些細(xì)節(jié)用本文算法都很好地分割了出來，而圖（c）則沒有體現(xiàn)；圖5 中的圖（d），左側(cè)兩個(gè)蘋果（特別是最左側(cè)的蘋果）以及蘋果上面的斑塊在本文算法的分割結(jié)果中都較好地體現(xiàn)出來了，分割結(jié)果也更有立體感，視覺效果明顯優(yōu)于圖（c）。

圖4 風(fēng)景圖像分割

圖5 水果圖像分割

在分割時(shí)間上，本文算法對(duì)圖像分割所用的時(shí)間要比傳統(tǒng)的最大熵圖像分割算法少。本文算法和傳統(tǒng)最大熵閾值分割算法對(duì)每幅圖像分割耗費(fèi)的時(shí)間如表1所示。

表1 兩種算法運(yùn)行時(shí)間對(duì)比

5 結(jié)語

針對(duì)傳統(tǒng)的最大熵閾值分割存在的算法復(fù)雜度高、計(jì)算多閾值時(shí)運(yùn)算時(shí)間長(zhǎng)、對(duì)目標(biāo)細(xì)節(jié)分割模糊以及分割結(jié)果不精確的問題，本文將最大熵閾值分割和遺傳算法相結(jié)合，利用遺傳算法具有的并行性、魯棒性和自適應(yīng)性的優(yōu)點(diǎn)來快速準(zhǔn)確地確定灰度圖像直方圖熵的最佳分割閾值，實(shí)現(xiàn)圖像分割。實(shí)驗(yàn)結(jié)果表明，本文算法能夠縮短尋找閾值的時(shí)間，對(duì)圖像的細(xì)節(jié)分割效果要優(yōu)于傳統(tǒng)算法，具有較好的理論意義和實(shí)踐意義。