基于分段自適應(yīng)遺傳算法的圖像閾值分割

杜雯超 ，陳其松 ，周 瑩

（1.貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025；2.貴州財經(jīng)大學(xué) 計算機信息學(xué)院，貴州 貴陽 550003）

0 引言

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

1 遺傳算法

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

圖1 自適應(yīng)的交叉概率（k=k1=k2）

圖2 自適應(yīng)的變異概率（k′=k3=k4）

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

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

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

改進的自適應(yīng)遺傳算法 （稱為分段自適應(yīng)遺傳算法）分為三個進化階段。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。

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

2 最大方差比準則[6]

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

最大方差比為：

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

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

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

算法步驟：

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

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

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

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

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

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

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

圖3 兩種算法的圖像分割結(jié)果對比

表1 處理結(jié)果統(tǒng)計

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

4 結(jié)論

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

[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)遺傳算法的改進及在系統(tǒng)辨別中的應(yīng)用研究[J].系統(tǒng)仿真學(xué)報，2006，18（1）：42-66.

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