基于改進遺傳算法的最佳閾值分割方法及其性能評價

隋然，潘點飛（.全軍后勤信息中心，北京0084；.航天員科研訓練中心，北京00094）

基于改進遺傳算法的最佳閾值分割方法及其性能評價

隋然1，潘點飛2
（1.全軍后勤信息中心，北京100842；2.航天員科研訓練中心，北京100094）

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

二維最佳熵；遺傳算法；圖像分割；評價指標

0 引言

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

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

1 基于改進遺傳算法的最大熵閾值分割

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

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

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

（1）編碼

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

（2）初始化種群

針對二維閾值分割，采用均勻分布在（0，0）～（255，255）之間隨機產生的n對個體，編碼為16位二進制碼。

（3）適應度函數

根據最佳熵閾值分割原理，選擇背景和目標的熵測度函數作為適應度函數，即：

式中，

（4）選擇

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

（5）交叉

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

若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）為兩個交叉的父個體，X′與Y′為新子代個體。交叉點的位置前8位為m，后8位為n，且0＜m＜7，0＜n＜7。

（6）變異

本文采用這樣一種自適應的變異策略：若當前變異個體的適應度比群體的適應度平均值大，則使其以較小的概率變異，因為它代表著較優的個體，反之則以較大變異概率繁殖下一代，以保持種群的多樣性。變異概率bm表示為：

其中，fmax表示當前種群中適應度函數的最大值，f是適應度的平均值，f為當前產生變異個體的適應度值。

（7）算法終止判斷

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

2 分割評價指標

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

2.1 全局一致性誤差

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

其中，＜R＞表示集合R中元素的個數，符號“”表示差集。原始圖像中的像元為pi，參考分割結果中pi∈Sk，實際分割結果則全局一致性誤差可以用下式表示：

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

2.2 概率邊緣指數

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

其中，N為總的像元數目，I表示一個判別函數。

2.3 變化信息

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

3 實驗結果與分析

選擇一幅255×255的米粒灰度圖像作為仿真對象。選擇種群規模為20，最大迭代次數為200，精英策略將適應度最大個體以10%直接復制到下一代，終止條件R0取[1.0，1.000 5]，交叉率取0.7。分別采用一維最大熵法、二維最大熵法與本文方法在不同的條件下進行仿真比較分析。

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

圖1 米粒原圖

圖2 噪聲圖像閾值分割效果

表1 噪聲圖像的分割性能比較

為了進一步分析噪聲對各種算法的影響，仿真分析不同信噪比下性能指標的變化情況，如圖3所示。可以看出，隨著噪聲強度的增加，圖像分割性能指標不斷惡化；相同SNR下，改進算法的性能要優于常規遺傳算法。

圖3 分割性能隨噪聲變化曲線

4 結論

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

[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].微型機與應用，2014，33（15）：40-42.

Maximum entropy threshold segmentation method based on im proved genetic algorithm and its performance evaluation

Sui Ran1，Pan Dianfei2
（1.The army′s Logistics Information Center，Beijing 100842，China；2.Astronaut Research and Training Center，Beijing 100094，China）

Aiming at the problems of the classical algorithms for solving two-dimensional maximum entropy，such as heavy computational complexity，long running time and poor convergence reliability，a novel method based on improved genetic algorithm is proposed to solve the maximum entropy.The improved selection operator，crossover operator and mutation operator are used to search threshold，which have improved dramatically on the robustness and convergence reliability.Then the image segmentation effect is evaluated.The results show that the improved method greatly saves the search time of threshold，as well as maintains good image segment effect.

two-dimensional maximum entropy；genetic algorithm；image segmentation；evaluation index

TP391

A

1674-7720（2015）14-0045-03

2015-03-21）

隋然（1975-），男，博士，工程師，主要研究方向：圖像處理，模式識別。

潘點飛（1984-），男，博士，工程師，主要研究方向：陣列信號處理。