摘  要： 針對常規(guī)二維最佳熵法計(jì)算復(fù)雜，運(yùn)行時(shí)間長，收斂性差等不足，提出基于改進(jìn)遺傳算法的二維最佳熵閾值分割方法。通過對選擇、交叉、變異等因子的優(yōu)化設(shè)計(jì)，使閾值搜索的魯棒性與收斂性有了很大改善，并對圖像的分割效果進(jìn)行評價(jià)。分析與仿真結(jié)果表明，改進(jìn)算法在大大減少閾值搜索時(shí)間的同時(shí)，保持了良好的分割性能。

　　關(guān)鍵詞： 二維最佳熵；遺傳算法；圖像分割；評價(jià)指標(biāo)

0 引言

　　自20世紀(jì)50年代以來，對圖像分割方法的研究不斷深入與發(fā)展，涌現(xiàn)出了許多新理論、新方法。但到目前為止，尚不存在一種通用的圖像分割方法。同時(shí)缺乏一種評價(jià)各種算法性能優(yōu)劣的判斷標(biāo)準(zhǔn)。在眾多圖像分割方法中，閾值法以其實(shí)現(xiàn)簡單、計(jì)算量小、性能穩(wěn)定成為圖像分割中最基本、應(yīng)用最廣泛的分割技術(shù)。但是，如何選取合適閾值以獲得理想的分割效果成為閾值分割的一大難點(diǎn)[1]。隨著智能算法的不斷發(fā)展，將智能方法用于閾值的優(yōu)化成為圖像分割研究的熱點(diǎn)[2-4]。在繁多的算法中往往存在著諸如算法的抗噪性能、運(yùn)算時(shí)間、全局優(yōu)化性等方面的不足。此外，各種算法的評價(jià)也缺乏完善、客觀的標(biāo)準(zhǔn)，如何評判圖像分割算法的性能成為圖像分割研究的又一大難題。

　　本文將遺傳算法用于圖像分割的最優(yōu)閾值選取中，針對傳統(tǒng)遺傳算法易陷入局部最優(yōu)、收斂性速度慢、抗噪能力差等不足提出了改進(jìn)方法，并通過全局一致性誤差函數(shù)、概率邊緣指數(shù)以及變化信息對其性能進(jìn)行評價(jià)分析。

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

　　閾值分割將灰度圖像轉(zhuǎn)換為二值圖像，不僅極大地壓縮了數(shù)據(jù)，而且大大簡化了后續(xù)的分析與處理步驟。自Pun根據(jù)Shannon熵的概念提出圖像熵的定義以來，基于熵的閾值分割方法一直頗受關(guān)注。

　　若一幅圖像的灰度空間為G={0，1，2，…，L-1}，其中，灰度值為i的像素個(gè)數(shù)為ni，則圖像的熵定義為：

　　其中，，fi表示灰度值i在圖像中出現(xiàn)的頻率，N為圖像的總的像素?cái)?shù)。

　　傳統(tǒng)遺傳算法易陷入局部最優(yōu)，且在噪聲背景下收斂速度較慢，甚至出現(xiàn)接近最優(yōu)的個(gè)體被淘汰，進(jìn)化過程不收斂。為此本文對傳統(tǒng)遺傳算法的選擇、交叉、變異因子進(jìn)行優(yōu)化設(shè)置，從而增強(qiáng)變異的多樣性，加快搜索的收斂性，以獲得全局最優(yōu)解。其基本思路如下：

　　（1）編碼

　　對于灰度值在0~255之間的圖像，一維最佳熵分割可采用8位二進(jìn)制代碼分割值，由于二維最佳熵分割待分割值是二維的，本文采用16位二進(jìn)制碼表示分割閾值，前8位表示分割值s，后8位表示分割值t。

　?。?）初始化種群

　　針對二維閾值分割，采用均勻分布在（0，0）~（255，255）之間隨機(jī)產(chǎn)生的n對個(gè)體，編碼為16位二進(jìn)制碼。

　?。?）適應(yīng)度函數(shù)

　　根據(jù)最佳熵閾值分割原理，選擇背景和目標(biāo)的熵測度函數(shù)作為適應(yīng)度函數(shù)，即：

　　則（t1*，t2*）即為所要求的最佳閾值。

　?。?）選擇

　　采用賭輪選擇和精英策略相結(jié)合的方法，首先將種群中各個(gè)體的適應(yīng)度除以種群總的適應(yīng)度，得到個(gè)體的相對適應(yīng)度。相對適應(yīng)度大的基因被遺傳到下一代，而相對適應(yīng)度較小的基因則逐步被淘汰。而后利用精英策略將適應(yīng)度最大的個(gè)體以一定比例直接復(fù)制到下一代。該方案不僅保證了最優(yōu)個(gè)體絕對復(fù)制到下一代，而且還體現(xiàn)了適應(yīng)度越高的個(gè)體繁衍后代的幾率越大的進(jìn)化思想。

　?。?）交叉

　　由于二維閾值法的前8位和后8位分別代表不同的閾值，因此采用雙點(diǎn)交叉法。若交叉概率選取過高，則個(gè)體更新較快，可達(dá)到更大的解空間，但對已有的較優(yōu)模式的破壞性也越大。反之，交叉概率過低，搜索范圍的減小，導(dǎo)致最優(yōu)解的搜索變得遲鈍。為了保證交叉后的新個(gè)體向著最優(yōu)解的方向進(jìn)化，采用如下規(guī)則：

　　若f（t1，t2）（X′）>f（t1，t2）（X）

　　則X′=（x0，…，xm，ym+1，…，y7，x8，…，xn，yn+1，…，y15）

　　否則X′=X

　　若f（t1，t2）（Y′）>f（t1，t2）（Y）

　　則Y′=（y0，…，ym，xm+1，…，x7，y8，…，yn，xn+1，…，x15）

　　否則Y′=Y

　　其中，X=（x0，…，x7，x8，…，x15）與Y=（y0，…，y7，y8，…，y15）為兩個(gè)交叉的父個(gè)體，X′與Y′為新子代個(gè)體。交叉點(diǎn)的位置前8位為m，后8位為n，且0<m<7，0<n<7。

　?。?）變異

　　本文采用這樣一種自適應(yīng)的變異策略：若當(dāng)前變異個(gè)體的適應(yīng)度比群體的適應(yīng)度平均值大，則使其以較小的概率變異，因?yàn)樗碇^優(yōu)的個(gè)體，反之則以較大變異概率繁殖下一代，以保持種群的多樣性。變異概率bm表示為：

　　其中，fmax表示當(dāng)前種群中適應(yīng)度函數(shù)的最大值，f是適應(yīng)度的平均值，f為當(dāng)前產(chǎn)生變異個(gè)體的適應(yīng)度值。

　?。?）算法終止判斷

　　選擇當(dāng)前群體的平均適應(yīng)度與上一代的平均適應(yīng)度值之比R0作為算法的終止條件，當(dāng)算法達(dá)到最大迭代次數(shù)或者終止條件時(shí)停止，輸出此時(shí)的最佳閾值。

　　2 分割評價(jià)指標(biāo)

　　對幾種圖像分割方法的性能評價(jià)，除了采用一些常用的指標(biāo)（如閾值、迭代次數(shù)、時(shí)間等）外，還引入全局一致性誤差、概率邊緣指數(shù)、變化信息對分割后的圖像進(jìn)行比較。

　　2.1 全局一致性誤差

　　全局一致性誤差（Global Consistency Error，GCE）是定義在局部細(xì)分誤差基礎(chǔ)上的，局部細(xì)分誤差定義為：

　　其中，<R>表示集合R中元素的個(gè)數(shù)，符號“\”表示差集。原始圖像中的像元為pi，參考分割結(jié)果中pi∈Sk，實(shí)際分割結(jié)果。則全局一致性誤差可以用下式表示：

　　GCE取值范圍為[0，1]，其值越小，說明全局一致性誤差越小。

　　2.2 概率邊緣指數(shù)

　　概率邊緣指數(shù)（Probabilistic Rand Index，PRI）是一個(gè)檢驗(yàn)實(shí)際分割結(jié)果與參考結(jié)果之間的屬性共生的一致性的參數(shù)。對于任一像元對（xi，xj），設(shè)其在原圖像S的標(biāo)記為（li，lj），在分割圖像中的標(biāo)記為（l′i，l′j），PRI的計(jì)算公式如式（9）所示，其值越大則分割結(jié)果與參考值之間的屬性共生一致性也就越好，PRI的取值范圍在[0，1]內(nèi)。

　　其中，N為總的像元數(shù)目，I表示一個(gè)判別函數(shù)。

　　2.3 變化信息

　　變化信息（Variation of Information，VI）是利用參考分割圖像的熵、實(shí)際分割結(jié)果的熵以及參考分割圖像與實(shí)際分割結(jié)果的聯(lián)合熵這3個(gè)參數(shù)來衡量實(shí)際分割結(jié)果相對參考分割圖像的信息變化。變化信息越小，說明實(shí)際分割結(jié)果相對參考分割圖像信息變化越少，實(shí)際分割結(jié)果越接近參考分割圖像。

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

　　選擇一幅255×255的米?；叶葓D像作為仿真對象。選擇種群規(guī)模為20，最大迭代次數(shù)為200，精英策略將適應(yīng)度最大個(gè)體以10%直接復(fù)制到下一代，終止條件R0取[1.0，1.000 5]，交叉率取0.7。分別采用一維最大熵法、二維最大熵法與本文方法在不同的條件下進(jìn)行仿真比較分析。

　　圖1為未經(jīng)處理的原始圖像，對噪聲圖像的分割效果如圖2所示，表1為對應(yīng)的分割性能指標(biāo)。可以看出，一維最佳熵法對低信噪比圖像的分割效果明顯下降。而二維最佳熵法能夠有效降低干擾的影響，但噪聲的影響使得窮舉法與傳統(tǒng)遺傳算法的搜索時(shí)間變得更長。從全局一致性誤差、概率邊緣指數(shù)以及變化信息中可以看出，改進(jìn)的遺傳算法在大大減少搜索時(shí)間的同時(shí)，保持了良好的分割效果。

　　為了進(jìn)一步分析噪聲對各種算法的影響，仿真分析不同信噪比下性能指標(biāo)的變化情況，如圖3所示?？梢钥闯?，隨著噪聲強(qiáng)度的增加，圖像分割性能指標(biāo)不斷惡化；相同SNR下，改進(jìn)算法的性能要優(yōu)于常規(guī)遺傳算法。

4 結(jié)論

　　本文首先介紹一維、二維最佳閾值分割方法的原理；而后針對二維最佳熵法的閾值搜索空間大、算法的運(yùn)行時(shí)間長、收斂性差等不足，提出了基于改進(jìn)遺傳算法的最佳熵閾值分割算法。通過對選擇、交叉、變異等因子的優(yōu)化設(shè)計(jì)，使新算法的收斂性以及分割效果有了明顯改進(jìn)。最后通過圖像分割評價(jià)指標(biāo)驗(yàn)證了改進(jìn)算法在噪聲圖像分割中的高效性。

參考文獻(xiàn)

　　[1] OTSU N. A threshold selection method from gray level histograms[J]. IEEE Transactions on Systems， Man and Cybernetics， 1979， SMC-9（1）：62-66.

　　[2] 湯可宗，柳炳祥，徐洪焱，等.一種基于遺傳算法的最小交叉熵閾值選擇方法[J].控制與決策，2013，28（12）：1805-1810.

　　[3] CHANDER A， CHATTERJEE A， SIARRY P. A new social and momentum component adaptive PSO algorithm for image segmentation[J]. Expert Systems with Applications， 2011，38（5）：4998-5004.

　　[4] 湯官寶.基于量子粒子群的改進(jìn)模糊聚類圖像分割算法[J].微型機(jī)與應(yīng)用，2014，33（15）：40-42.