金保華，岳 艷，周 兵

(鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院，河南鄭州450002)

基于改進(jìn)遺傳算法的otsu圖像分割算法

金保華，岳 艷，周 兵

(鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院，河南鄭州450002)

在圖像分割過程中，傳統(tǒng)的遺傳算法存在收斂速度慢、易陷入局部最優(yōu)解等缺陷.因此，提出了一種基于改進(jìn)遺傳算法的otsu圖像分割算法，該算法在原有分割算法基礎(chǔ)上對(duì)交叉率和變異率進(jìn)行改進(jìn)，使用otsu作為適應(yīng)度函數(shù)，并采用選擇、交叉、變異等操作尋找最佳分割閾值.仿真實(shí)驗(yàn)表明，該算法可以有效提高圖像的分割精度和計(jì)算速度，證明了該算法具有良好的尋優(yōu)能力.

遺傳算法；閾值；圖像分割；otsu函數(shù)

圖像分割是圖像處理和計(jì)算機(jī)視覺中基本而關(guān)鍵的技術(shù)之一.其目的是將目標(biāo)和背景分離，為后續(xù)的圖像分類，識(shí)別和檢索提供依據(jù)，在實(shí)際生產(chǎn)中有著廣泛的應(yīng)用.

遺傳算法[1－4]有廣泛的應(yīng)用，目前已被應(yīng)用到閾值圖像分割上.王丹、周錦程等[5]提出一種改進(jìn)遺傳算法在圖像分割中的應(yīng)用，該方法利用二維最大熵在二維空間灰度空間上搜索參數(shù)，該方法計(jì)算量較大，參數(shù)選取比較困難.Chen Y等[6]提出圖像分割的一個(gè)簡(jiǎn)化PCNN的新參數(shù)自定設(shè)置方法，Zhou D[7]提出一種簡(jiǎn)化的脈沖耦合神經(jīng)網(wǎng)絡(luò)的粗到細(xì)的迭代分割策略，Acharya A[8]利用近似邊緣推理的分?jǐn)?shù)階學(xué)習(xí)模型參數(shù)來進(jìn)行圖像的分割，Niu S等[9]提出一種魯棒噪聲區(qū)域的輪廓模型的局部相似性因子用于圖像分割，Takeda H等[10]基于場(chǎng)景前景和背景的貝葉斯風(fēng)險(xiǎn)估計(jì)的圖像分割，謝昕，王建賓等[11]提出一種粒子群和otsu相結(jié)合的絮體圖像分割算法，可實(shí)現(xiàn)對(duì)絮體區(qū)域的快速提取，單粒子群算法實(shí)施過程中，參數(shù)設(shè)置主要依靠實(shí)驗(yàn)者的經(jīng)驗(yàn)去設(shè)置，缺乏準(zhǔn)確性.閾值分割[12－15]由于其簡(jiǎn)單有效，而被大家所常用.閾值圖像分割算法的關(guān)鍵部分就是如何快速有效地選取最優(yōu)閾值[16－17].但是，由于傳統(tǒng)的遺傳算法存在收斂速度慢，易早熟等缺點(diǎn)，對(duì)圖像分割最優(yōu)閾值的選擇帶來了很大問題.

針對(duì)上述問題，本文在傳統(tǒng)遺傳算法基礎(chǔ)上，做了算法的改良，并將改良后的算法應(yīng)用到otsu圖像分割中，該方法通過對(duì)交叉算子和變異算子進(jìn)行優(yōu)化和改進(jìn)，使得改進(jìn)后的遺傳算法避免陷入局部最優(yōu)解中，通過函數(shù)驗(yàn)證，該方法具有一定的實(shí)用性，然后將這種改進(jìn)后的算法用于最優(yōu)閾值尋找上，事實(shí)證明，改進(jìn)后的算法，有很好的尋優(yōu)性能，精確度高，圖像分割的效果也得到了改進(jìn)，該算法具有一定的有效性.

1 otsu閾值分割

而otsu是上個(gè)世紀(jì)被提出的一種自適應(yīng)閾值分割算法.它是利用圖像的灰度值，把圖像分為兩個(gè)方面，通過計(jì)算確定兩者之間的類間方差.而兩者之間的最大值，也就是所要求得圖像分割的閾值.

有L個(gè)灰度級(jí)，灰度級(jí)為i的像素總數(shù)為mi，則總的像素?cái)?shù)目灰度值為i的像素出現(xiàn)的概率:

大間類方差的基本思想是:用灰度值K作為圖像分割閾值，把圖像分割成類A1和A2.灰度級(jí)從0到K的像素為A1類，灰度級(jí)從K＋1到L－1的像素為A2類.A1和A2兩類出現(xiàn)的概率分別為:

A1和A2兩類像素的灰度均值分別為

整個(gè)圖像的灰度均值為:fg＝PA1c1＋PA2c2.則類A1和A2的類間方差:σ2(k)＝PA1(c1－fg)2＋PA2(c2－fg)2.由PA1＋PA2＝1可進(jìn)一步得:當(dāng)K的值從0到L－1變化，使得σ2(k)取得最大的K值即為最大閾值.

由otsu的基本原理可知:otsu算法通過遍歷所有灰度值，然后計(jì)算出每個(gè)灰度值的類間方差，找出其中的最大值，作為最佳閾值，當(dāng)處理圖像數(shù)量較大時(shí)，計(jì)算量比較大，效率不高.其次，當(dāng)圖像中有噪聲時(shí)，otsu算法容易使圖像分割出錯(cuò).

2 改進(jìn)的遺傳算法

在傳統(tǒng)的遺傳算法中，通常把交叉率和變異率大小設(shè)置為定值，如果選取不當(dāng)，則容易陷入局部最優(yōu)解.有人提出了一個(gè)新的交叉率，變異率的方法，公式如下所示:

其中:gmax:種群的最大適應(yīng)度，g′:交叉?zhèn)€體中的適應(yīng)度大的個(gè)體，gavg:種群的平均適應(yīng)度，g:變異個(gè)體的適應(yīng)度.

從上述公式看出，適應(yīng)度和gmax幾乎相等的情況下，交叉率和變異率就會(huì)越來越低；當(dāng)兩者相同時(shí)，交叉概率和變異概率得值變?yōu)榱?這樣就導(dǎo)致了在種群剛開始進(jìn)化時(shí)，適應(yīng)度高的個(gè)體幾乎不會(huì)發(fā)生變化，使算法陷入局部最優(yōu)解.

上述算法存在的情況，本文做出了新的改進(jìn)，提出了一個(gè)新的優(yōu)化方法:

其中:gavg:平均適應(yīng)度值，gi:個(gè)體i的適應(yīng)度值，gmax:最大適應(yīng)度值；pc1為最大交叉率，pm1為最小變異率.

對(duì)于公式可以看出，無論什么情況，都避免了交叉率和變異率為0的情況.這樣既保留了優(yōu)秀的個(gè)體，又避免進(jìn)入局部最優(yōu)解.

3 改進(jìn)后的遺傳算法的驗(yàn)證

為了證明優(yōu)化后算法的有效性，采用數(shù)學(xué)函數(shù)對(duì)算法測(cè)試，所選函數(shù):

分別對(duì)傳統(tǒng)遺傳算法和改進(jìn)后的算法對(duì)函數(shù)進(jìn)行最優(yōu)值求解，設(shè)初始種群為50，代數(shù)為80，對(duì)運(yùn)行的結(jié)果如表1所示.

表1 測(cè)試函數(shù)的優(yōu)化結(jié)果Tab.1 Test function optimization results

從圖1可以看出，改進(jìn)后的算法與傳統(tǒng)的遺傳算法相比較，有了很大的進(jìn)步，尋優(yōu)能力更強(qiáng)，具有一定的應(yīng)用性，可以把改進(jìn)后的算法應(yīng)用到圖像分割中.

圖1 算法在測(cè)試函數(shù)下各代的適應(yīng)度值Fig.1 Various generation algorithms under the test function of fitness value

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

改良后的遺傳算法應(yīng)用到圖像分割中，根據(jù)otsu算法尋找圖像的最佳閾值.首先對(duì)種群進(jìn)行二進(jìn)制編碼，然后生成初始種群，把otsu函數(shù)作為算法的適應(yīng)度函數(shù)，然后對(duì)種群進(jìn)行選擇，交叉和變異之后，找到最終的最佳分割閾值.

改進(jìn)遺傳算法應(yīng)用到otsu算法中的具體步驟:

1)編碼和種群初始化.級(jí)在0～255之間的圖像，使用8位二進(jìn)制代碼作為分割值.初始種群不應(yīng)過大也不應(yīng)過小，初始化種群太大，會(huì)因此導(dǎo)致算法運(yùn)行時(shí)間長(zhǎng)，初始化種群選擇過小，直接影響種群的多樣性.

2)適應(yīng)度函數(shù).根據(jù)otsu閾值圖像分割原理，本文采用公式(1)來對(duì)種群中每個(gè)個(gè)體適應(yīng)度進(jìn)行計(jì)算，結(jié)果采用升序排列，以便后續(xù)處理.

3)選擇.采用輪轉(zhuǎn)選擇對(duì)種群進(jìn)行選擇，計(jì)算個(gè)體的適應(yīng)度，然后利用輪盤賭法進(jìn)行計(jì)算所占比例，最后確定其是否被選擇.個(gè)體被選中的概率為

圖2 改進(jìn)遺傳算法流程圖Fig.2 Improved genetic algorithm flow chart

其中A:種群大小，fi:種群中個(gè)體第i個(gè)的適應(yīng)度值.

選擇算法通過把個(gè)體中優(yōu)良個(gè)體從原來種群中選擇出來，這樣有利選擇出個(gè)體中適應(yīng)度更高的個(gè)體，以便新的種群比原來的種群適應(yīng)度更高.進(jìn)行選擇時(shí)，應(yīng)用了達(dá)爾文適者生存的原則.

4)交叉.將選擇操作后的新種群個(gè)體進(jìn)行兩兩交叉，將一部分基因段交叉調(diào)換，從而將父代優(yōu)秀的基因得意保留下來，并進(jìn)入到下一代，按照式(2)進(jìn)行交叉概率操作.

5)變異.機(jī)選擇個(gè)體，將變異算子作用于這個(gè)個(gè)體，模仿生物界中變異現(xiàn)象，得到新個(gè)體，經(jīng)過變異，不僅能使種群數(shù)量和種類更加豐富，也能保證有更多的優(yōu)良個(gè)體出現(xiàn)，并依照式(3)變異概率操作.

6)算法終止判斷.進(jìn)行選擇，交叉，變異等操作，判斷最大代數(shù)是否達(dá)到最優(yōu)值，若滿足最大遺傳代數(shù)，則遺傳終止，得出最優(yōu)解.

5 實(shí)驗(yàn)與分析

為了證明本文所提出的遺傳算法的otsu圖像分割算法的是否可行，本文用lena和horse測(cè)試圖為例，對(duì)otsu分割算法，遺傳算法圖像分割和本文算法的分割結(jié)果分別測(cè)試，實(shí)驗(yàn)所有結(jié)果均基于Matlab實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為Intel core i7，4G內(nèi)存，Windows 7操作系統(tǒng).選擇初始種群規(guī)模M為30，最大進(jìn)化代數(shù)為170，結(jié)果如圖3、4所示.

由圖4中可以看出，三種分割方法都能很好的對(duì)原圖像進(jìn)行分割，分割后的圖像較完整的保留了原始圖像信息.其中可以發(fā)現(xiàn)otsu算法的圖像分割結(jié)果最差，精度不夠準(zhǔn)確分割出來的效果圖較差，許多細(xì)節(jié)都沒有表現(xiàn)出來，對(duì)比otsu和遺傳算法圖像分割，本文所用分割方法不僅能夠完整的完成對(duì)圖像的分割，而且目標(biāo)與背景分割比較清楚，分割出來的圖像更為清晰，能夠非常好的把背景和目標(biāo)分離，是以上幾種算法中效果最好的.以lena測(cè)試圖為例，帽子上的裝飾物和臉部的輪廓細(xì)節(jié)保留的比較好，都非常好的展現(xiàn)了出來，保留了原來圖像數(shù)據(jù)的更多的原本屬性.

圖3 lena.jpg圖像分割結(jié)果Fig.3 lena.jpg image segmentation results

圖4 horse.jpg圖像分割結(jié)果Fig.4 horse.jpg image segmentation results

從表2可以得出，otsu算法平均最優(yōu)閾值約為127，遺傳算法平均最優(yōu)閾值約為128，本文改進(jìn)算法平均最佳閾值約為133.從上述可以看出本文所用方法獲得的平均最優(yōu)閾值最大，在這三種分割算法中，本文所用算法的分割精度最高，分割的效果較前兩種算法有了很大的提高.

表2 Lena和apple測(cè)試最佳閾值圖Tab.2 Lena and apple Test the best threshold figure

對(duì)于本文提出圖像分割算法.通過實(shí)驗(yàn)結(jié)果分析，可以看出，改進(jìn)后的算法相比較改進(jìn)前的兩種算法，有更良好的尋優(yōu)性能，在提高精確度的情況下細(xì)節(jié)又很好的得到了體現(xiàn)，并且改算法的穩(wěn)定性也得到了一定程度的加強(qiáng)，精確度高，圖像分割的效果也得到了改進(jìn).

6 結(jié)束語

論文針對(duì)經(jīng)典的遺傳算法在進(jìn)行圖像分割過程中易陷入局部最優(yōu)解的問題，提出了一種改進(jìn)遺傳算法的otsu圖像分割算法，利用對(duì)交叉率和變異率的不斷改進(jìn)方式，為圖像分割提供了一種參考，通過對(duì)該算法進(jìn)行數(shù)學(xué)函數(shù)仿真實(shí)驗(yàn)驗(yàn)證，改進(jìn)后的遺傳算法尋優(yōu)能力更強(qiáng)，最后將該遺傳算法應(yīng)用到otsu圖像分割上，解決了陷入局部最優(yōu)解的問題，表明了改進(jìn)后的遺傳算法具有一定的優(yōu)越性，具有良好的參考價(jià)值.

[1] DE S，BHATTACHARYYA S，DUTTA P.Automatic magnetic resonance image segmentation by fuzzy intercluster hostility index based genetic algorithm:An application[J].Applied Soft Computing，2016，47:669－683.

[2] ?AM E，LüY M，MAMUR H.PID Parameter Optimization of Blade Pitch Controller in Wind Turbines by a New Intelligent Genetic Algorithm[J]. IET Renewable Power Generation，2016.

[3] 袁方潔，張佳萍.基于多階段遺傳算法的人力資源管理[J].云南民族大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，25(3):275－279.

[4] 朱煥，馬文靜，盛永生，等.多尺度各向異性小波收縮圖像分割算法在玉米病斑特征提取時(shí)的應(yīng)用[J].黑龍江八一農(nóng)墾大學(xué)學(xué)報(bào)，2016，28 (2):136－140.

[5] 王丹，周錦程.一種改進(jìn)的遺傳算法在圖像分割中的應(yīng)用[J].科技視界，2016，13:108－109，117.

[6] CHEN Y，PARK S K，MA Y，et al.A New Automatic Parameter Setting Method of a Simplified PCNN for Image Segmentation[J].IEEE Transactions on Neural Networks，2011，22(6):880－92.

[7] ZHOU D，GAO C，GUO Y.A coarse－to－fine strategy for iterative segmentation using simplified pulse－coupled neural network[J].Soft Computing，2014，18(3):557－570.

[8] ACHARYA A，MUKHERJEE U，F(xiàn)OWLKES C.On Image segmentation using Fractional Gradients－Learning Model Parameters using Approximate Marginal Inference[J].arXiv preprint arXiv:1605.02240，2016.

[9] NIU S，CHEN Q，DE Sisternes L，et al.Robust noise region－based active contour model via local similarity factor for image segmentation[J].Pattern Recognition，2017，61:104－119.

[10] TAKEDA H，GHARAVI－ALKHANSARI M.Image segmentation using bayes risk estimation of scene foreground and background:U.S.Patent 9，437，008[P].2016－9－6.

[11] 謝昕，王建賓，胡鋒平.一種基于PSO與OSTU的改進(jìn)絮體分割算法[J].傳感器與微系統(tǒng)，2015，34(1):131－134.

[12] ZHANG M X，ZHAO C Y，SHANG Z W，et al.An algorithm based on rough－set theory for color image segmentation[C]//Wavelet Analysis and Pattern Recognition，International Conference on，IEEE，2010:28－32.

[13] CHANG D，ZHAO Y，LIU L，et al.A dynamic niching clustering algorithm based on individual－connectedness and its application to color image segmentation[J].Pattern Recognition，2016，60:334－347.

[14] 劉桂紅，趙亮，孫勁光，等.一種改進(jìn)粒子群優(yōu)化算法的Otsu圖像閾值分割方法[J].計(jì)算機(jī)科學(xué)，2016，43(3):309－312.

[15] 袁小翠，吳祿慎，陳華偉.基于Otsu方法的鋼軌圖像分割[J].光學(xué)精密工程，2016(7):1772－1781.

[16] JIANG Y，YEH W C，HAO Z，et al.A cooperative honey bee mating algorithm and its application in multi－threshold image segmentation[J].Information Sciences，2016，369:171－183.

[17] HORNG M H.Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation[J].Expert Systems with Applications，2011，38(11):13785－13791.

責(zé)任編輯:高 山

The otsu Image Segmentation Algorithm Based on Improved Genetic Algorithm

JIN Baohua，YUE Yan，ZHOU Bing
(School of Computer and Communication Engineering，Zhengzhou University of Light Industry，Zhengzhou 450002，China)

In the process of image segmentation，the traditional genetic algorithm has such defects as slow convergence speed and easily falling into local optimal solution.Therefore，this paper proposes an otsu image segmentation algorithm based on improved genetic algorithm.The proposed algorithm，on the basis of the original segmentation algorithm，improves the crossover rate and mutation rate by using otsu as fitness function and using the selection，crossover and mutation operations to search for the best segmentation threshold.The simulation results show that the proposed algorithm can effectively improve the image segmentation accuracy and calculation speed and it has good optimization ability.

genetic algorithm；threshold value；image segmentation；otsu function

TS210.1

A

1008－8423(2017)01－0007－04

10.13501/j.cnki.42－1569/n.2017.03.002

2016－10－18.

國(guó)家自然科學(xué)基金項(xiàng)目(61402422).

金保華(1966－)，男，博士，教授，主要從事人工智能，計(jì)算機(jī)輔助決策系統(tǒng)的研究.