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

　　關鍵詞： 圖像分割；分段自適應遺傳算法；最大方差比；信息熵

0 引言

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

1 遺傳算法

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

　　在傳統的自適應算法中，Pc和Pm按下列公式進行自適應調整：

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

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

　　改進的自適應遺傳算法（稱為分段自適應遺傳算法）分為三個進化階段。M為最大遺傳代數，Pc為交叉概率，Pm為變異概率，f為適應度值。第一階段為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。

　　改進的自適應遺傳算法中，Pc和Pm按下列公式分段調整：

2 最大方差比準則[6]

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

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

　　最大方差比為：

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

3 改進算法在圖像分割中的應用

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

　　算法步驟：

　　（1）圖像預處理：對圖像進行雙線性插值處理。

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

　　（3）確定自適應函數，把方差比作為適應度函數，計算個體的適應度值，并對種群進行解碼。

　　（4）開始進行迭代，首先判斷進化的代數，選擇恰當的交叉概率和變異概率。

　　（5）進行遺傳操作：選擇，交叉，變異。

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

　　（7）對圖像進行閾值分割，并求出對應的類間方差、類內方差、方差比以及分割后的信息熵。

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

4 結論

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

參考文獻

　　[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] 王小平，曹立明.遺傳算法：理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.

　　[5] 任子武，傘冶.自適應遺傳算法的改進及在系統辨別中的應用研究[J].系統仿真學報，2006，18（1）：42-66.

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