李 陽 歸偉夏

(廣西大學計算機與電子信息學院 廣西 南寧 530004)

一種基于改進小生境遺傳算法的圖像分割方法

李 陽 歸偉夏

(廣西大學計算機與電子信息學院 廣西 南寧 530004)

利用經(jīng)典的Otsu算法和基本遺傳算法相結(jié)合進行圖像分割存在有算法效率低、容易提前形成偽解的問題，對于上述問題，提出一種基于改進小生境遺傳算法的圖像分割算法(IVNGAMS)。算法全局優(yōu)化了二維Otsu圖像分割函數(shù)，可以按照個體適應度大小自動控制遺傳參數(shù)。并通過引入模擬退火算法，進一步提升算法的局部搜索能力。實驗結(jié)果表明，改進的圖像分割方法能更好提升算法的全局搜索能力，能夠更加穩(wěn)定快速的收斂到最佳的分割閾值，并且得到了更好的圖像分割效果。

遺傳算法 小生境 圖像分割 閾值

0 引 言

圖像分割就是在被分割成若干個特定并有獨特性質(zhì)的區(qū)域的圖像中，尋得所需求的區(qū)域[1]。在計算機圖像處理領(lǐng)域的研究的課題中，圖像分割理論十分重要。1979年Otsu提出了一種最大類間方差法(Otsu算法)，該算法通過閾值將原始圖像劃分為目標圖像和背景圖像，比較兩類圖像的類間方差值，來選取最優(yōu)閾值[2]。但是Otsu圖像分割法較適用于單極值出現(xiàn)的情況。

目前研究學者發(fā)現(xiàn)要想獲得更好的圖像處理效果，需要將各種分割算法相互融合。近年來的研究成果[3-6]大都是結(jié)合型算法。其中在分割效率和效果方面，基于遺傳算法的圖像分割應用優(yōu)勢很大。將閾值法和遺傳算法進行整合，并且把其它優(yōu)化算法嵌入其中來提升算法運行的收斂速度和穩(wěn)定性[7]。但是，由于使用基本遺傳算法還存在易早熟，收斂性差等缺點，使得尋找圖像分割最優(yōu)閾值十分困難。

因此，如何解決早熟和提高算法的收斂速度成為了尋找圖像分割最優(yōu)閾值的關(guān)鍵性問題[8-11]。本文針對經(jīng)典的Otsu算法或是基本遺傳算法結(jié)合Otsu算法進行圖像分割存在有算法效率低、收斂不到最佳閾值的問題提出一種新的圖像分割方法(IVNGAMS)，將改進的小生境遺傳算法與二維Otsu算法相結(jié)合并引入模擬退火的思想，使之能夠隨著適應度值和群體分散程度自動調(diào)整。從而來提高閾值求取效率和圖像清晰度，以此達到滿意的圖像分割結(jié)果。

1 二維Otsu圖像分割法

由于經(jīng)典的Otsu圖像分割法存在目標圖像與整幅圖像的面積比不確定問題，導致圖像切割的閾值求取不簡單。所以本文采用二維Otsu圖像分割法。

假定圖像中像素的鄰域灰度均值在0～(K-1)級之間。設(shè)p(m,n)表示圖像中坐標(m,n)的像素灰度值，點(m,n)的鄰域灰度均值為：

(1)

其中像素點p(m, n)的鄰域?qū)挾扔肗來代表，設(shè)N=5。

用Cij表示向量(i，j)發(fā)生的頻數(shù)，那么向量(i，j)發(fā)生的頻率Pij為：

(2)

設(shè)二維矢量(U,V)為圖像閾值，用圖1來描述圖像的二維直方圖。圖中目標圖像用區(qū)域1表示，背景圖像用區(qū)域2表示；邊緣和噪聲用3和4表示。

圖1 圖像的二維直方圖

設(shè)定背景圖像用A0表示，目標圖像用A1表示，這兩種圖像有不同的概率分布。設(shè)其閾值為(U,V)，那么兩類圖像所顯現(xiàn)的概率分布是：

(3)

(4)

在這里背景圖像顯現(xiàn)的概率用W0來代表，目標圖像顯現(xiàn)的概率用W1來代表。求得背景圖像和目標圖像對應均值的矢量為：

μ0= (μ0i,μ0j)T=

(5)

μ1= (μ1i,μ1j)T=

(6)

由于區(qū)域3和4的出現(xiàn)概率可略之不計，則W0+W1≈1，用μw代表總體平均值為：

μw= (μwi,μwj)T=

(7)

設(shè)定一個關(guān)于目標類和背景類的離散測度矩陣：

W0[(μ0-uw)(μ0-uw)T]+

W1[(μ1-uw)(μ1-uw)T]

(8)

則目標圖像與背景圖像中的距離測度函數(shù)表示為：

trσB(U,V) =W0[(μ0i-μwi)2+(μ0j-μwj)2]+

W1[(μ1i-μwi)2+(μ1j-μwj)2]=

(W0(U,V)μwi-μi(U,V))2+

(9)

其中trσB(U,V)只和W0(U,V)、μi(U,V)、μj(U,V)有關(guān)。

當分割算法的閾值(U0,V0)取在trαB(U,V)為最大時，即：

trσB(U0,V0)=max{trσB(U,V)} 0≤U,V<1

(10)

使用Otsu法進行圖像分割計算復雜繁瑣，對任意(U,V)，測度函數(shù)中的變量W0(U,V)、μi(U,V)、μj(U,V)都要進行累積求和，而且要對全部的U和V進行遍歷的，算法復雜度約為O(K3)。因此為了提升計算效率，本文將改進小生境遺傳算法與之結(jié)合。

2 小生境遺傳算法

20世紀60年代， 美國密歇爾大學的JohnHolland對自然進化的特征產(chǎn)生了極大興趣， 在對生物模擬技術(shù)進行研究時受到啟發(fā)， 從而促使了遺傳算法的產(chǎn)生[12]。 這之后由Bagley第一次將“遺傳算法”規(guī)范化，并在其博士論文中將該詞語正式提出[13]。它具有隱含并行性，在遺傳算法中引入小生境的概念有助于優(yōu)化算法能夠快速的找出全部的最優(yōu)解。

在多模態(tài)遺傳算法的研究中，小生境技術(shù)是指把每代群體里的具有特征的實體分成很多類，之后在這些類中分別篩選得到很多實體，它們都具有較高的適應度值，并且把這些實體結(jié)合為新的群體。然后于不同群體間進行遺傳操作，衍生出新的個體種群，并且使用某種小生境技術(shù)進行選擇[14]。這樣不但保持了種群的多樣性，而且具備很高的收斂效率和尋找全局最優(yōu)解的能力，對于求多個局部最優(yōu)解的復雜問題特別合適。

小生境遺傳算法有三種選擇機制：預選擇機制、排擠機制和共享機制。小生境遺傳算法的算法步驟如下：

Step1 初始化種群。求取種群中的S個個體的適應度Fs(s=1,2,…,S)。

Step2 按照個體適應值降序排序每個個體，并且記住前T個個體(T

Step3 對排序后的個體進行選擇、交叉、和變異運算。

Step4 小生境運算：合并Step3得到的A個個體與Step2得到的B個個體，生成一個新的種群，它包含A+B個個體。針對其中的每兩個個體Xs和Xt，求取它們之間的相似度Dst。當Dst

Step5 按照A+B個個體的新的適應值降序排序每個個體，記住前B個個體。

Step6 結(jié)束條件：若滿足結(jié)條件，就輸出最優(yōu)解。否則，就將Step5中得到的前A個個體構(gòu)成子代新的種群，之后跳到Step6。

本文對基本的小生境遺傳算法做了四處改進。

第一，改進SRINVIVAS[15]研究的基本自適應遺傳算法中計算交叉、變異概率的公式，確保種群中適應度值最高的個體的交叉、變異概率不為零。修改后的交叉、變異概率的計算公式如式(11)和式(12)所示：

(11)

(12)

其中：fmax為種群中最大的適應度值；favg為每代種群的平均適應度值；f′為等待交叉的兩個個體中較大的適應度值；f為變異個體的適應度值；Pc1為交叉概率的最大值；Pm1為變異概率的最大值。

第二，原算法用海明距離來衡量兩個個體的遠近程度是不妥的。因為即使兩個個體之間的海明距離很小，它們之間實際距離也可能很大。因此本文選用歐氏距離。從而提高了個體相似度的準確性。

第三，原算法通常采用(1+1)淘汰來進行小生境運算。然而(μ+λ)選擇策略可有效地保持群體的多樣性。這樣新的種群中就含有了更多的高適應值的個體。通過仿真實驗可以看出，用(μ+λ)競爭選擇機制可以達到較高的收斂效率，很大程度上提高了種群多樣性。在考慮計算效率后，本文選用 (2+2)的競爭機制。

第四，將模擬退火算法與原算法相結(jié)合，深入提升算法的局部搜索能力和收斂速度。

3 模擬退火算法

模擬退火算法起源于固體退火原理，隨著溫度的遞減，遍歷搜索空間搜尋最優(yōu)解。

該算法能夠解決遺傳算法的局部搜索能力差的問題。

模擬退火的基本思想：

(1) 初始化參數(shù)：初始溫度T0，初始解S，每個T0值的迭代次數(shù)L，降溫系數(shù)K；

(2) 對i=1,2,…,L循環(huán)(3)至(6)操作；

(3) 得出新解S＇；

(4) 計算增量△t＇=C(S＇)-C(S)作為評價函數(shù)；

(5) 若△t＇<0則采用S＇為新的當前解，否則通過概率exp(-△t＇/T0)將S＇看作新解；

(6) 若達到終止的條件，就把當前解輸出為最優(yōu)解；

(7)T0逐漸減少(T0=T0×K)，T0>0，然后轉(zhuǎn)第(2)步。

4 改進的圖像分割算法

Otsu算法求閾值其實就是尋求式(9)的最優(yōu)解。因此將改進的小生境遺傳算法和Otsu算法相結(jié)合，并嵌入模擬退火操作得到改進的圖像分割方法(IVNGAMS)。該方法可以在一定程度上提高算法的局部搜索能力，使算法更快的尋求到最優(yōu)解，從而得到更好的圖像分割效果。

IVNGAMS的算法步驟如下：

Step1 初始化參數(shù)。設(shè)定MAXGEN′為最大進化代數(shù)，NIND為種群規(guī)模，Pc為交叉概率， Pm為變異概率，q為降溫系數(shù)，T1為退火初始溫度，gen′為當前所處進化代數(shù)，Tend為退火終止溫度。

Step2 編碼和解碼。采取二進制編碼策略，設(shè)置(0,255)為圖像的灰度值范圍。對于二維Otsu算法，由于目標閾值為二維矢量，所以算法將(U,V) 用16位的二進制串來代表，由這個二進制串的前后兩部分分別來代表U和V。并分別解碼為在灰度值范圍的數(shù)。

Step3 初始化種群。由于本章節(jié)是討論函數(shù)優(yōu)化問題，算例是各個目標函數(shù)，所以直接把各個目標函數(shù)表達式作為適應度函數(shù)，若某函數(shù)為最小值問題，則另f(x)=-f(x)，調(diào)整為最大值問題。本文隨機生成NIND個個體的初始種群Chrom，適應度函數(shù)用式(9)表示，得到各個個體的適應度值φs，s=1,2, …,NIND。

Step4 按照φs排序每個個體，存儲前Q個個體(Q

Step5 設(shè)置gen′=0，gen′Tend為循環(huán)條件。

Step6 選擇運算。對種群Chrom進行輪盤賭選擇，得到新種群SelCh。

Step7 交叉運算。使用雙點交叉的方法，在16位二進制串的前面8位與后面8位分別設(shè)置兩個交叉點，按照式(11)自適應調(diào)節(jié)交叉概率，設(shè)Pc1=0.8。

Step8 變異運算。采用高斯變異算子，按照式(12)自適應調(diào)節(jié)變異概率，設(shè)Pm1=0.01。

Step9 對小生境的進行排擠計算。合并Step8獲取的P個個體和Step4獲取的Q個個體，獲得一個包含P+Q個個體的新種群。選擇兩個個體Xs和Xt按公式(13)計算每兩個個體Xs和Xt之間的相似度：

(13)

其中，s,t=1,2, …,P+Q。若Dst

Step11 終止條件。當gen′Tend，那么gen′= gen′+1，Ts+1=qTs，回轉(zhuǎn)到子種群，轉(zhuǎn)至Step6；否則轉(zhuǎn)至Step12。

Step12 利用返回的最優(yōu)閾值對圖像進行分割。

Step13 算法結(jié)束。

IVNGAMS算法流程如圖2所示。

圖2 IVNGAMS的算法流程圖

5 改進算法的時間復雜度分析

從上一節(jié)的算法步驟中可以看出本算法主要由選擇操作、交叉操作、變異操作、排擠操作、模擬退火操作和圖像分割操作組成。其中在最壞的情況下選擇操作的時間復雜度為O(N2)，交叉操作和變異操作的時間復雜度為O(N×MAXGEN′×NIND)，排擠操作的時間復雜度為O(N×MAXGEN′×NIND)，模擬退火操作的時間復雜度為O(MAXGEN′)，圖像分割操作的時間復雜度由二維Otsu算法決定即為O(K4)，所以本算法的時間復雜度為O(N2+ N×MAXGEN′×NIND+ K4)。其中MAXGEN′表示最大進化代數(shù)，NIND表示種群大小，N表示目標函數(shù)的維數(shù)，K表示圖像中像素的鄰域灰度均值的級數(shù)。

6 仿真實驗

6.1 實驗環(huán)境和參數(shù)設(shè)置

為驗證本文算法的性能，本文選取了文獻[16-17]所介紹的兩個灰度級圖像，針對圖像分別選擇Otsu圖像分割算法、Otsu結(jié)合SGA與本文算法做五次比較分割處理實驗。該項實驗的實驗環(huán)境為Microsoftwindows7.0和matlab2014a。實驗中，設(shè)置參數(shù)為：種群規(guī)模NIND=15，遺傳代數(shù)最大值MAXGEN=10，原始溫度T0=100，降溫系數(shù)q=0.8，懲罰函數(shù)Penalty=10-30，小生境半徑M=0.15。

6.2 實驗結(jié)果與分析

實驗1Lena測試圖像分割。針對Lena測試圖像分別選擇Otsu圖像分割法、Otsu結(jié)合SGA與IVNGAMS做分割比較。圖3體現(xiàn)了原圖像及分割結(jié)果，如下所示，實驗數(shù)據(jù)如表1所示。

圖3 Lena測試圖像及分割效果

實驗次數(shù)Otsu法Otsu結(jié)合SGAIVNGAMS閾值時間/s閾值時間/s閾值時間/s11172.97881351.53191351.384421172.88421321.53721341.391431172.94521271.53281351.311941172.88891291.53921351.384551172.95771251.54221331.3084平均1172.93096129.61.53666134.41.35612

從圖3可以看出，標準遺傳算法在分割的結(jié)果上要比Otsu算法略更優(yōu)，分割圖像的背景陰影部分也相對減少了，說明IVNGAMS和標準遺傳算法在分割結(jié)果上相近。表1顯示，將SGA與Otsu算法結(jié)合進行圖像分割相比Otsu算法很大程度上提升了獲取最優(yōu)閾值的效率，閾值在9個像素之間波動。然而IVNGAMS不但在閾值獲取效率上比遺傳算法略有提升，而且閾值范圍在2個像素之間。相比于標準遺傳算法，本文算法在進化同等代數(shù)后可以確保種群的多樣性并且提高了收斂效率，更加穩(wěn)定。

實驗2 Car測試圖像分割。針對Car測試圖像分別選擇Otsu圖像分割法、Otsu結(jié)合SGA與IVNGAMS做分割比較。圖4體現(xiàn)了原圖像及分割結(jié)果，如下所示，實驗數(shù)據(jù)如表2所示。

圖4 Car測試圖像及分割效果

實驗次數(shù)Otsu法Otsu結(jié)合SGAIVNGAMS閾值時間/s閾值時間/s閾值時間/s1891.05811070.75411070.54462891.06561080.74021080.53973891.06051100.74821080.53794881.06951060.75051070.54265891.05611050.74641080.5369平均891.06196107.20.74788107.60.54034

從圖4可以看出，標準遺傳算法在分割的結(jié)果上要比Otsu算法略優(yōu)，分割圖像中的車牌號也相對清晰了，說明IVNGAMS和SGA在分割結(jié)果上相近。表2顯示，將SGA與Otsu算法結(jié)合進行圖像分割相比Otsu算法很大程度上地提升了獲取最優(yōu)閾值的效率，閾值在5個像素之間波動。然而IVNGAMS不但在閾值獲取效率上比遺傳算法略有提升，而且閾值范圍在2個像素之間。相比于標準遺傳算法，IVNGAMS在進化同等代數(shù)后可以確保種群的多樣性并且提高了收斂效率，更加穩(wěn)定。

7 結(jié) 語

本文利用改進的小生境遺傳算法全局優(yōu)化了二維圖像分割函數(shù)，并通過結(jié)合模擬退火算法提出一種IVNGAMS算法，算法確保了種群多樣性并提升了收斂效率并更加穩(wěn)定。仿真實驗的實驗結(jié)果表明，IVNGAMS的閾值運算效率比Otsu圖像分割法提高了很多，比標準遺傳算法也略有提高。閾值范圍穩(wěn)定在2個像素之間，可以迅捷精確地對圖像進行分割處理，實用性較高。在圖像分割方法的研究方面，還可以與其他智能優(yōu)化算法相結(jié)合來提升分割效率，而且針對彩色圖像分割的研究也是圖像分割研究重點，之后可以進行深入研究。

[1] 章毓晉.圖像工程(上冊)——圖像處理[M].2版.北京:清華大學出版社,2006.

[2] 張自嘉,岳邦珊,潘琦,等.基于蟻群和自適應濾波的模糊聚類圖像分割[J].電子技術(shù)應用,2015,41(4):144-147.

[3] 李銀松.基于遺傳算法的圖像分割方法[D].北京:北京交通大學,2014.

[4] 黃倩.基于粒子群優(yōu)化聚類的SAR圖像分割方法研究[D].西安:西安電子科技大學,2014.

[5] 王雪.基于遺傳算法的醫(yī)學圖像分割技術(shù)的研究[D].長春:長春理工大學,2013.

[6] 劉辰龍.基于遺傳算法的水聲圖像技術(shù)研究[D].哈爾濱:哈爾濱工程大學,2013.

[7] 李賢陽,黃嬋.一種結(jié)合改進Otsu法和改進遺傳算法的圖像分割方法[J].實驗室研究與探索,2012,31(12):57-61,112.

[8] 王小平,曹立明.遺傳算法——理論、應用與軟件實現(xiàn)[M].西安:西安交通大學出版社,2002.

[9] 李婷.云模型在圖像分割領(lǐng)域的應用研究[D].太原:太原理工大學,2015.

[10] 謝佩軍.一種基于膜計算的遺傳算法圖像分割方法[J].工業(yè)控制計算機,2015,28(4):92-94.

[11]AntoniolG,CeccarelliM.Microarrayimagegriddingwithstochasticsearchbasedapproaches[J].ImageandVisionComputing,2007,25(2):155-163.

[12]LinS,KernighanBW.AnEffectiveHeuristicAlgorithmfortheTraveling-Salesmanproblem[J].OperationsResearch,1973,21(2):498-516.

[13] 韓瑞鋒.遺傳算法原理與應用實例[M].北京:兵器工業(yè)出版社,2010.

[14]CavicchioDJ.AdaptiveSearchUsingSimulatedEvolution[D].AnnArbor,MI,USA:UniversityofMichigan,1970.

[15] 玄光男,程潤偉.遺傳算法與工程設(shè)計[M].北京:科學出版社,2000.

[16] 李輝.基于改進遺傳算法的圖像分割[D].長春:東北師范大學,2004.

[17] 于霞霞,何朗,黃樟燦.基于模擬退火并行算法的二維熵多閾值分割[J].武漢理工大學學報,2015,37(1):116-120.

AN IMAGE SEGMENTATION METHOD BASED ON IMPROVED NICHE GENETIC ALGORITHM

Li Yang Gui Weixia

(SchoolofComputer,ElectronicsandInformation,GuangxiUniversity,Nanning530004,Guangxi,China)

The classical Otsu algorithm and the basic genetic algorithm combined with image segmentation have the problem of low efficiency and easy to form pseudo solution in advance. For this problem, an image segmentation algorithm based on improved niche genetic algorithm (IVNGAMS) is proposed. The algorithm optimizes the two-dimensional Otsu image segmentation function globally, and automatically adjusts the genetic parameters according to the individual fitness. And the simulated annealing algorithm is introduced to further improve the local search ability. The experimental results show that the improved image segmentation method can improve the global search ability, and can converge to the optimal segmentation threshold more stably and quickly, and obtain better image segmentation effect.

Genetic algorithm Niche Image segmentation Threshold

2016-01-22。國家自然科學基金項目(61363002)；廣西教育廳科研基金項目(LX2014002)。李陽，碩士生，主研領(lǐng)域：智能計算。歸偉夏，副教授。

TP301.6

A

10.3969/j.issn.1000-386x.2017.04.034