用于圖像分割的雙變異遺傳算法*

周 陽， 李曉春

(中南大學 物理與電子學院，湖南 長沙 410000)

用于圖像分割的雙變異遺傳算法*

周 陽， 李曉春

(中南大學 物理與電子學院，湖南 長沙 410000)

針對遺傳算法(GA)收斂結(jié)果不穩(wěn)定、易陷入局部最優(yōu)解等問題，提出了一種基于全局的改進雙變異遺傳算法(DMGA)，并應用于圖像的灰度閾值分割；分析了仿真初始參數(shù)對于圖像分割結(jié)果的影響。實驗結(jié)果表明：圖像分割精度高，效果好，結(jié)果可靠,相對于傳統(tǒng)GA，DMGA具有更好的全局和局部搜索能力，收斂結(jié)果穩(wěn)定。

雙變異遺傳算法； 圖像分割； 灰度閾值

0 引 言

遺傳算法(genetic algorithm,GA)模擬自然進化過程，從問題解的串集開始搜索最優(yōu)解，相比于其它(如粒子群優(yōu)化算法[1])單個初始值迭代求最優(yōu)解的算法，它覆蓋面大[2]，具有更佳的全局搜索能力。而且，GA具有自組織、自適應和自學習的優(yōu)點，僅需適應度函數(shù)值來評估個體，因而廣泛應用于圖像分割[3]、復雜函數(shù)系統(tǒng)優(yōu)化[4]、系統(tǒng)識別[5]、神經(jīng)網(wǎng)絡設計[6]等眾多領域[7,8]。Zhou Wei等人[9]將GA運用于虛擬企業(yè)的合作伙伴的選擇和優(yōu)化；Teoh Yeong Yeap等人[10]將GA運用于低通濾波器的設計；Guo Pengfei等人[11]將GA用于離散變量的優(yōu)化。

本文采用一種特別的雙變異方法，使得種群個體的多樣性以及父代優(yōu)良基因的遺傳得到了較好的處理，有利于全局搜索最優(yōu)解，并且可以適當?shù)亟档碗s交概率pc和變異概率pm值，提高種群的收斂性，較好地解決了收斂速度和全局搜索之間的平衡問題。

1 雙變異遺傳算法

雙變異遺傳算法(double-mutation genetic algorithm,DMGA)與傳統(tǒng)GA的最大區(qū)別在于變異操作的處理。傳統(tǒng)GA只采取一次變異，變異率一般由種群大小、染色體長度等因素所決定，取值通常很小；變異操作一般是從群體中某個個體染色體中隨機挑選一個或多個基因座，并對選取的基因座進行變異。雙變異在原有變異操作基礎上，人為加上一次變異選擇操作，變異概率可以人為給定，不受種群大小、染色體長度等因素的影響，如果得到更好后代，則取代原先最優(yōu)個體，如果沒有得到更好后代，則保留原先最優(yōu)個體。雙變異操作可以極大地豐富群體中個體的多樣性，保留父代的優(yōu)良基因，縮短尋找最優(yōu)解的迭代次數(shù)。

1.1 雙變異操作

圖1為傳統(tǒng)的變異操作示意圖。

圖1 傳統(tǒng)單變異示意圖

染色體長度V=8，每一條染色體均有8個基因座，圖1中的一個正方形和一個圓形分別表示具體的某一個基因座。圖中本代初始種群中圓形組合P1和正方形組合P2分別代表兩個不同的父代種群，通過一次變異后得到子代種群P3和P4。其中 P3為優(yōu)良種群，得以繼承，P4成為淘汰種群，它們之間進行選擇，就得到本代最優(yōu)個體P5。

圖2為文獻[14]所述的一般雙變異操作示意圖。

5.仰口線蟲病。剖檢可見病牛尸體極度消瘦、水腫，皮下漿液性浸潤，血凝不全，腸黏膜發(fā)炎，出血，內(nèi)容物呈褐色或血紅色。

圖2 一般雙變異示意圖[16]

在第一次變異得到的子代種群P3(優(yōu)良品種)、P4(淘汰種群)的基礎上，將淘汰種群P4再次變異后進行優(yōu)選，得到種群P5。P6為傳統(tǒng)遺傳算法(選擇1)的最優(yōu)個體。P5,P6經(jīng)過再次選擇(選擇2)，得到文獻[14]的最優(yōu)個體P7。

相對于傳統(tǒng)遺傳算法(圖1)，文獻[14]的一般雙變異操作中，本代最佳個體的選擇范圍多了淘汰種群P4的再次變異優(yōu)選結(jié)果P5。本文的雙變異操作算法如圖3。

圖3 本文雙變異操作示意圖

圖3中，在一次變異后得到的子代種群P3、P4基礎上，對優(yōu)良品種P3、淘汰種群P4分別再次變異，得到種群P5、P6。P7仍為傳統(tǒng)遺傳算法(選擇1)的最優(yōu)個體。P5、P6、P7經(jīng)過再次選擇(選擇2)，得到本文算法的最優(yōu)個體P8。

圖3的雙變異操作可看成是一次“配種”過程。一次“配種”是否成功，取決于再次變異后得到的個體P5、P6是否優(yōu)于本代中的最佳個體P7。如果優(yōu)于，則“配種”成功；反之，“配種”失敗。“配種”成功將為種群創(chuàng)造出更優(yōu)良的父代基因，迫使種群向更加優(yōu)良的方向發(fā)展，經(jīng)過多代繁殖之后，種群進化到全局最優(yōu)種群的機率與速度將大大提高。

因此，圖3在圖2的基礎上，增加了優(yōu)良品種P3的再次變異，并將其優(yōu)選結(jié)果P5列入后續(xù)選擇過程。本文相對文獻[14]的一般DMGA，不僅擴大了種群選擇范圍，而且增加了優(yōu)良品種在這個范圍中的比重，從而擴大了全局搜索能力，加快了收斂到最優(yōu)解的速度。

1.2 DMGA用于圖像分割

將改進的遺傳算法用于圖像分割需要解決兩個問題：一是選擇怎樣的分割方式；二是如何構(gòu)造適應度函數(shù)來衡量每條染色體(基因串)對環(huán)境的適應能力。本文選擇的分割方式是運用最為廣泛的圖像灰度閾值分割；適應度函數(shù)為最大類間方差法公式。

本文構(gòu)造的DMGA用于圖像分割的流程圖如圖4所示。

圖4 DMGA用于圖像分割流程圖

2 仿真實驗

為了驗證本文算法對圖像分割的有效性和準確性，選取三副圖像分別在Matlab 7.0下進行分割對比實驗，表1為兩種算法的初始參數(shù)如下：初始種群數(shù)Q=6,染色體長度L=8,遺傳代數(shù)G=150,雜交概率pc= 0.05,變異概率pm=0.01。

2.1 分割精度對比

圖5(a1)，圖6(a1)，圖7(a1)都為選取的原始圖像；圖5(a2)，(b2)，(c2)為對應的傳統(tǒng)算法的圖像分割效果圖；圖5(a3)，(b3)，(c3)為本文改進算法的圖像分割效果圖。

圖5 兩種分割方法效果的對比

從圖5(a2)，(c2)中可以看出，分割后的圖像將背景物體過多地分割到了目標物體。圖5(a2)中圖像則過多地把目標物體當成背景物體給分割掉了。本文改進算法的結(jié)果圖5(a3)，(b3)，(c3)，則對分割實現(xiàn)了較好的均衡，背景物體基本分割完全，目標物體圖像清晰，輪廓分明，沒有出現(xiàn)將背景物體錯分為目標物體或?qū)⒛繕宋矬w錯當成背景物體的現(xiàn)象。

2.2 可靠性對比

表1、表2、表3為相同參數(shù)(表1)條件下，分別對圖5(a1)，(b1)，(c1)采用傳統(tǒng)GA和改進DMGA依次進行8次仿真得到的閾值結(jié)果圖。

由表1、表2、表3可以看出:在Q=6，L=8，G=150，p=0.05，pm= 0.01情況下。傳統(tǒng)GA得到的閾值跳動較大，表1為38～110，表2為55～188，表3為63～146，很不穩(wěn)定。而本文改進的GA得到的閾值上下跳動不超過1，變動較少，基本趨于平衡；再結(jié)合圖5的效果可知，采用DMGA仿真得到的閾值分割精度也非常準確。可見，采用本文改進的DMGA幾乎全部可以分割到最佳閾值，是一種比較可靠的分割方法。

表1 對圖5(a1)采用兩種算法得到的閾值對比

算法12345678GA 94107 38755381110 60DMGA8383848583858485

表2 對圖5(b1)采用兩種算法得到的閾值對比

算法12345678GA 10762133955513018891DMGA111112 112112 112 112112113

表3 對圖5(c1)采用兩種算法得到的閾值對比

算法12345678GA 146 8791106 160 8463140 DMGA9393949393939294

2.3 搜索能力對比

圖6為表2中第二次仿真得到的單變異與雙變異最佳閾值進化曲線圖。

圖6 最佳閾值進化曲線的對比

由圖6(a)可以看出，閾值的進化比較單一，搜索遲鈍，易于早熟收斂，陷入局部最優(yōu)，搜索到的最優(yōu)解可靠性能差。對比圖6(b)曲線波動明顯加快，搜索反應迅速，無論前期后期曲線都有波動，很好地限制了傳統(tǒng)GA易于早熟收斂、后期搜索遲鈍等缺點。因此，搜索能力更強。

2.4 參數(shù)設置問題

為了驗證參數(shù)對算法的影響， 本文從初始種群、遺傳代數(shù)、雜交概率、變異概率四個方面分別對算法進行研究。以初始種群數(shù)Q=2，遺傳代數(shù)G=10,雜交概率pc=0.01，變異概率pm=0.01為初始參數(shù)。

表4為初始種群數(shù)Q=2,6,10,12，G=10，pc=0.01，pm=0.01時；分別對圖5(a1)進行10次GA與10次DMGA求閾值后得到的平均值與方差。

表4 初始種群數(shù)不同得到的閾值對比

Q2平均值方差 6平均值方差 10平均值方差 12平均值方差GA 124182081575872488535DMGA 87 2285 483 283 2

表5為初始種群數(shù)Q=2，G=20,50,100,150，pc=0.01，pm=0.01時；分別對圖5(a1)進行10次GA與10次DMGA求閾值后得到的平均值與方差。

表5 遺傳代數(shù)不同得到的閾值對比

G20平均值方差 50平均值方差 100平均值方差 150平均值方差GA 8337881253721873782913293DMGA83 4 85 985 484 3

表6為初始種群數(shù)Q=2，G=10，pc=0.02,0.06,0.1,0.14，pm=0.01時；分別對圖5(a1)進行10次GA與10次DMGA求閾值后得到的平均值與方差。

表6 雜交概率不同得到的閾值對比

pc0．02平均值方差 0．06平均值方差 0．1平均值方差 0．14平均值方差GA 100387711128611053106994194DMGA 83 71 86 8 84 386 8

表7為初始種群數(shù)Q=2，G=10，pc=0.01，pm=0.02,0.06,0.1,0.14時；分別對圖5(a1)進行10次GA與10次DMGA求閾值后得到的平均值與方差。

表7 變異概率不同得到的閾值對比

pm0．02平均值方差 0．06平均值方差 0．1平均值方差 0．14平均值方差GA1443742838228916488120DMGA 87 1884 984 484 2

由表4、表7可以看出：隨著初始種群或變異概率的增多，GA與本文算法得到的閾值的平均值越來越靠近最佳閾值，方差越來越小，可見閾值的波動的幅度越來越小，可靠性增加。由表5、表6可以看出：兩種算法的平均值與方差變化不大。

對于灰度圖像識別來說，灰度值的選擇范圍在0～255之間，本算法中染色體位數(shù)取8位是足以滿足灰度取值范圍要求的。從圖像分割的模擬結(jié)果看，無論初始種群數(shù)、遺傳代數(shù)、雜交、變異概率如何變化，本文算法得到的閾值的平均值均與最佳閾值非常接近，并且方差較小，穩(wěn)定性高，是一種比較可靠的圖像灰度閾值分割方法。

3 結(jié) 論

模擬結(jié)果表明:與傳統(tǒng)的GA相比，本文的改進DMGA，具有更好的全局和局部搜索能力，收斂結(jié)果穩(wěn)定；在圖像分割的具體應用上，圖像分割[16,17]精度高，分割效果好，結(jié)果可靠，是一種實用的高效的圖像灰度閾值分割方法。

[1] Rokbani N,Momasso A L,Alimi A M.AS-PSO,ant supervised by PSO meta-heuristic with application to TSP[C]∥Proceedings Engineering & Technology,2013:148-152.

[2] Aghaabbasloo M,Azarkaman M,Salehi M E.Biped robot joint trajectory generation using PSO evolutionary algorithm[C]∥The 5th RoboCup Iran Open International Symposium(RIOS) on Al & Robotics ,2013:1-6.

[3] Choong M Y,Liau C F,Mountstephens J,et al.Multistage image clustering and segmentation with normalised cuts[C]∥The 3rd International Conference on Intelligent Systems,Modelling and Simulation(ISMS),2012:362-367.

[4] Vellasco M B R,Cruz A V A,Pinho A G.Quantum-inspired evolutionary algorithms applied to neural modeling[C]∥IEEE World Conference on Computational Inteligence,Plenary and Invited Lectures,2010:125-150.

[5] Noshadi A,Shi J,Lee W S,et al.Genetic algorithm-based system identification of active magnetic bearing system:A frequency-domain approach[C]∥2014 IEEE International Conference on Control & Automation(ICCA),2014:1281-1286.

[6] Chagas S H,Martins J B,de Oliveira L L.An approach to localization scheme of wireless sensor networks based on artificial neural networks and genetic algorithms[C]∥2012 IEEE 10 th International Conference on New Circuits and Systems(NEWCAS),2012:1619-1622.

[7] Platel M D,Schliebs S,Kasabov N.A versatile quantum-inspired evolutionary algorithm[C]∥Congress on Evolutionary Computation,2007:423-430.

[8] Cam Z G,Cimen S,Yildirim T.Learing parameter optimization of multi-layer perceptron using artificial bee colony,genetic algorithm and particle swarm optimization[C]∥2015 IEEE the 13th International Symposium on Applied Machine Intelligence and Infomatics(SAMI),2015:329-332.

[9] Zhou Wei,Bu Yanping,Zhou Yeqing.Research on partner selection problem of virtual enterprise based on improved genetic algorithm[C]∥The 26th Chinese Control and Decision Conference,2014 CCDC,2014:1047-1052.

[10] Teoh Yeong Yeap,Neoh Siew Chin,Arau,Malaysia.A GA-based optimization for fourth-order sallen-Key low-pass filter[C]∥2012 the 4th Asia Symposium on Quality Electronic Design(ASQED),2012:164-167.

[11] Guo Pengfei,Wang Xuezhi,Han Yingshi.A hybrid genetic algorithm for structural optimization with discrete variables[C]∥2011 International Conference on Internet Computing & Information Services(ICICIS),2011:223-226.

[12] 劉荷花,崔 超,陳 晶,等.一種改進的遺傳算法求解旅行商問題[J].北京理工大學學報,2013,33(4):390-393.

[13] 劉曉明，溫福岳，曹云東，等.基于改進遺傳算法的SF6斷路器勻場設計[J].中國電機工程學報，2008,33(2):99-103.

[14] 方咸云,方千山,王永初.雙變異率自適應遺傳算法研究及其應用[J].南昌航空工業(yè)學院學報,2002,16(2):17-20.

[15] 曾 成,趙錫鈞,徐 欣，等.PCB檢測中圖像分割技術(shù)研究[J].傳感器與微系統(tǒng),2011,30(2):26-28.

[16] 劉小霞,徐貴力,嵇盛育，等.一種改進的艦船紅外圖像分割算法[J].傳感器與微系統(tǒng),2008,27(6):37-39.

[17] 陳天炎,曾思通,吳海彬,等.基于YCbCr顏色空間的火焰圖像分割方法[J].傳感器與微系統(tǒng),2011,30(10):62-64.

DMGA for image segmentation*

ZHOU Yang, LI Xiao-chun

(School of Physics and Electronic Engineering,Central South University,Changsha 410000,China)

Aiming at problem of unstable convergence result and easy to fall into locally optimal solution,present a global improved double-mutation genetic algorithm(DMGA),and apply to gray threshold image segmentation;analyze effect of simulation initial parameters on image segmentation result.Simulation results show that precision,effective and reliable of image segmentation is better,compared with the traditional GA,this algorithm has better global and local search capability,and convergence results are stable.

double-mutation genetic algorithm(DMGA)； image segmentation； gray threshold

10.13873/J.1000—9787(2017)02—0138—04

2016—03—11

國家自然科學基金資助項目(11264037)

TP 391.9

A

1000—9787(2017)02—0138—04

周 陽(1991-)，男，碩士研究生，主要研究方向為圖像處理、智能算法。