摘  要： 自適應(yīng)遺傳算法是一種有效的尋優(yōu)算法，本文首先對自適應(yīng)遺傳算法進(jìn)行改進(jìn)，提出分段自適應(yīng)遺傳算法，達(dá)到了防止早熟，加快尋優(yōu)速度的目的。閾值分割是一種經(jīng)典的圖像分割算法，本文將利用改進(jìn)的自適應(yīng)遺傳算法（分段自適應(yīng)遺傳算法）對圖像分割。本文算法以最大類間方差比作為適應(yīng)度函數(shù)，通過最佳閾值進(jìn)行尋優(yōu)，以信息熵和最大方差比作為評價標(biāo)準(zhǔn)對圖像分割進(jìn)行比較，實驗證明基于分段自適應(yīng)遺傳算法的圖像閾值分割算法能夠達(dá)到較好的分割效果。

　　關(guān)鍵詞： 圖像分割；分段自適應(yīng)遺傳算法；最大方差比；信息熵

0 引言

　　在對圖像進(jìn)行研究和分析時，人們往往只對某些部分區(qū)域感興趣（稱作目標(biāo)或前景），其余的部分則被稱作背景。為了識別、分析的需要，有必要將目標(biāo)和背景分離出來。圖像分割[1，2]就是將一幅數(shù)字圖像細(xì)分為若干個小的子區(qū)域的過程，是進(jìn)行圖像處理和圖像分析并進(jìn)而進(jìn)行圖像理解的關(guān)鍵步驟，圖像分割的好壞，對后面的分析和理解具有很大的影響。因此，好的分割方法非常重要。利用閾值分割對圖像進(jìn)行分割，關(guān)鍵是找到恰當(dāng)?shù)拈撝祵⑶熬昂捅尘皡^(qū)分開來，在眾多的閾值分割中，如何準(zhǔn)確快速地確定最優(yōu)閾值是基于閾值分割的關(guān)鍵問題。而遺傳算法是一類借鑒生物界的進(jìn)化規(guī)律演化而來的隨機(jī)全局化搜索算法，是一種具有魯棒性、并行性和自適應(yīng)性的優(yōu)化算法。本文將改進(jìn)的自適應(yīng)遺傳算法應(yīng)用到圖像分割中，提出了一種基于改進(jìn)遺傳算法的最大類間方差比的圖像閾值分割算法，新算法不僅能夠?qū)D像進(jìn)行準(zhǔn)確的分割，而且能夠以較少的計算代價得到最優(yōu)閾值。

1 遺傳算法

　　遺傳算法（Genetic Algorithm）[3]是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展而來的高度并行的搜索算法。遺傳算法包括三個基本的操作：選擇、交叉和變異。遺傳算法的交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性，Pc的大小決定種群的更新和搜索速度的快慢。Pc越大，產(chǎn)生新個體的速度就會越快，然而，Pc過大會使具有適應(yīng)度高的個體被很快破壞；如果Pc過小，搜索過程就會變得緩慢。變異概率Pm是保持種群多樣性，防止早熟的一種手段。Pm過小則不容易產(chǎn)生新的個體，過大則會使遺傳算法變?yōu)榧兇獾碾S機(jī)搜索。基于以上問題，Srinvivas等人提出了一種自適應(yīng)遺傳算法（Adaptive GA，AGA），Pc和Pm能夠隨適應(yīng)度的改變而自適應(yīng)地做出改變。如圖1、圖2所示。

　　在傳統(tǒng)的自適應(yīng)算法中，Pc和Pm按下列公式進(jìn)行自適應(yīng)調(diào)整：

　　式中，fmax為最大的適應(yīng)度值；favg為平均適應(yīng)度；f ′為要交叉的兩個個體中較大的適應(yīng)度值；f 為要變異個體的適應(yīng)度值。

　　但是這種方法在進(jìn)化初期種群中較優(yōu)個體幾乎不會發(fā)生變化，而得到的優(yōu)良個體不一定是全局最優(yōu)解，可能產(chǎn)生局部最優(yōu)解[4]。任子武等人在此基礎(chǔ)上提出了一種改進(jìn)的自適應(yīng)遺傳算法（IAGA）[5]。本文提出的改進(jìn)的自適應(yīng)遺傳算法是交叉概率和變異概率隨著進(jìn)化代數(shù)和適應(yīng)度函數(shù)的變化而改變，不會在進(jìn)化的初期陷入局部最優(yōu)。首先將進(jìn)化分為3個階段，每個階段的交叉概率、變異概率的上限和下限隨著進(jìn)化代數(shù)的增減而逐漸減小，這種分階段的方法能夠使算法實現(xiàn)首先對圖像進(jìn)行廣泛粗略搜索，再進(jìn)行細(xì)致搜索。這樣可以更快更好地尋找到最優(yōu)解，并且不會出現(xiàn)早熟現(xiàn)象。

　　改進(jìn)的自適應(yīng)遺傳算法（稱為分段自適應(yīng)遺傳算法）分為三個進(jìn)化階段。M為最大遺傳代數(shù)，Pc為交叉概率，Pm為變異概率，f為適應(yīng)度值。第一階段為1~0.4M代，這時Pc1=0.9 Pc2=0.7 Pm1=0.08 Pm2=0.05；第二階段為第0.4M~0.8M代，Pc1=0.7 Pc2=0.5 Pm1=0.06 Pm2=   0.03；第三階段為第0.8M到第M代，Pc1=0.5 Pc2=0.3 Pm1=0.03 Pm2=0.01。

　　改進(jìn)的自適應(yīng)遺傳算法中，Pc和Pm按下列公式分段調(diào)整：

2 最大方差比準(zhǔn)則[6]

　　對于灰度級S=（1，2，3，...，L）的圖像，T為分割閾值，把圖像分割為S1=（1，2，3，…，T），S2=（T+1，T+2，…，L）。則類內(nèi)方差分別為：

　　N為像素總個數(shù)，S1，S2的方差，w1，w2是S1，S2的發(fā)生概率，S1，S2的平均灰度值，T是圖像的平均灰度值。

　　最大方差比為：

　　說明不同類像素之間的灰度相差越大，同類像素之間的灰度值相差越小。所以，?濁越大，說明分割效果越佳。

3 改進(jìn)算法在圖像分割中的應(yīng)用

　　自適應(yīng)遺傳算法作為一種模擬生物在自然環(huán)境中遺傳和進(jìn)化過程的自適應(yīng)全局搜索算法，其魯棒性、適應(yīng)性及全局優(yōu)化性等明顯優(yōu)于傳統(tǒng)遺傳算法。分段的自適應(yīng)遺傳算法具有更高的適應(yīng)性，同時可以減小進(jìn)化的代數(shù)，在初始階段保證了種群的多樣性，進(jìn)化的最后階段可以很好地保持最優(yōu)解的完整性。本文基于分段自適應(yīng)遺傳算法的圖像分割，采用了方差比作為適應(yīng)度函數(shù)，并與經(jīng)典的Ostu圖像分割方法進(jìn)行比較。兩種算法分割結(jié)果如圖3所示。

　　算法步驟：

　　（1）圖像預(yù)處理：對圖像進(jìn)行雙線性插值處理。

　　（2）初始化：在改進(jìn)的遺傳算法中，令種群規(guī)模為15，進(jìn)化代數(shù)為50，染色體長度為8，初始化種群（采用二進(jìn)制編碼），讀入預(yù)處理的圖像。

　　（3）確定自適應(yīng)函數(shù)，把方差比作為適應(yīng)度函數(shù)，計算個體的適應(yīng)度值，并對種群進(jìn)行解碼。

　　（4）開始進(jìn)行迭代，首先判斷進(jìn)化的代數(shù)，選擇恰當(dāng)?shù)慕徊娓怕屎妥儺惛怕省?/p>

　　（5）進(jìn)行遺傳操作：選擇，交叉，變異。

　　（6）停止準(zhǔn)則：判斷最大適應(yīng)度值在連續(xù)三代中的變化是否小于0.005或者是否執(zhí)行到最大代數(shù)，若否，繼續(xù)循環(huán)（4）；若是則找出最佳的方差比?濁以及對應(yīng)的灰度級?茲。

　　（7）對圖像進(jìn)行閾值分割，并求出對應(yīng)的類間方差、類內(nèi)方差、方差比以及分割后的信息熵。

　　由分割圖像和結(jié)果統(tǒng)計表（表1）得出，本文算法在分割圖像和參數(shù)比較方面優(yōu)于Otsu方法，從直觀感受，本文算法所分割圖像簡潔而又不失細(xì)膩，從數(shù)據(jù)方面本文算法分割圖像的信息熵是0.987 3，Otsu方法分割后圖像的信息熵是0.978 6。由信息熵定義判定，信息熵越大圖像分割效果越好。本文算法分割后圖像最大方差略大于由Otsu方法分割后圖像，說明不同類像素之間的灰度相差大，同類像素之間的灰度值相差小。從這兩方面比較本文算法的分割效果更好一些。

4 結(jié)論

　　傳統(tǒng)自適應(yīng)遺傳算法容易出現(xiàn)早熟或是局部最優(yōu)解，本文提出的分段自適應(yīng)遺傳算法遵循先廣搜索，再細(xì)搜索的策略，在進(jìn)化的初期能增加種群的多樣性，而在后期較小的交叉、變異概率下很好地保證了最優(yōu)解的結(jié)構(gòu)不被破壞。自適應(yīng)能力強，具有較好的性能。用分段自適應(yīng)遺傳算法結(jié)合最大方差比尋求最佳閾值進(jìn)行圖像分割，分割后的圖像清晰簡潔，算法效率比較高。

參考文獻(xiàn)

　　[1] BYUNGKI C， KAWANO H， SUETAKE N， et al. Minimum-Spanning-Tree-like based image segmentation[C]. 2008. ICNC′08 Fourth International Conference on Natural Computation（Volume：6）， Jinan， 2008，152-156.

　　[2] Zhang Jian， Chen Xiaowei. Non-subsampled contourlets and gray level co-occurrence matrix based images segmentation[C]. 2011 International Conference on Uncertainty Reasoning and Knowledge Engineering （URKE）， Bali： 2011：168-170.

　　[3] Chang Chengyuan， Chen Dengrui. Active noise cancellation without secondary path identification by using an adaptive genetic algorithm[J]. IEEE Transactions on Instrumentation and Measurement， 2010，59（9）：2315-2327.

　　[4] 王小平，曹立明.遺傳算法：理論、應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.

　　[5] 任子武，傘冶.自適應(yīng)遺傳算法的改進(jìn)及在系統(tǒng)辨別中的應(yīng)用研究[J].系統(tǒng)仿真學(xué)報，2006，18（1）：42-66.

　　[6] 辛國江，模擬人類視覺機(jī)理的圖像處理方法[D].長沙：中南大學(xué)，2013.