杜雯超 ，陳其松 ，周 瑩

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

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所示。

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

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

在傳統(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)方差分別為：

最大方差比為：

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

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)方差、方差比以及分割后的信息熵。

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

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

由分割圖像和結(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)能力強(qiáng)，具有較好的性能。用分段自適應(yīng)遺傳算法結(jié)合最大方差比尋求最佳閾值進(jì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.