基于雙自適應(yīng)遺傳算法的Otsu圖像分割研究?

廖延娜 李夢(mèng)君

1 引言

圖像分割［1］是圖像處理與計(jì)算機(jī)視覺(jué)［2］的基本問(wèn)題之一，是進(jìn)行圖像分析、特征提取和目標(biāo)識(shí)別的基礎(chǔ)，圖像分割的好處直接影響到后續(xù)圖像的處理。近年來(lái)，圖像分割一直是人們研究關(guān)注的熱點(diǎn)和重點(diǎn)，圖像分割的方法很多，大體可分為三類(lèi)：閾值分割法［3］、邊緣檢測(cè)法［4］和區(qū)域法［5］等。類(lèi)間最大方差法［6］作為傳統(tǒng)的閾值分割技術(shù)被大多數(shù)人所熟知，它具有計(jì)算簡(jiǎn)單、分割效果較優(yōu)等優(yōu)點(diǎn)，但由于Otsu法計(jì)算量大、效率不高、分割效果不可靠等缺點(diǎn)，有學(xué)者將遺傳算法［7］與類(lèi)間最大方差法相結(jié)合，借鑒遺傳算法并行性、搜索能力強(qiáng)等優(yōu)點(diǎn)，進(jìn)行圖像閾值［8］尋優(yōu)。

文獻(xiàn)［9］利用傳統(tǒng)的遺傳算法與Otsu法相結(jié)合的方法大大提高了圖像分割的效率，但標(biāo)準(zhǔn)遺傳算法存在易早熟、易陷入局部最優(yōu)的缺點(diǎn)，本文對(duì)相關(guān)算法進(jìn)行改進(jìn)，提出一種基于雙自適應(yīng)遺傳算法的Otsu閾值分割算法。

2 改進(jìn)的雙自適應(yīng)遺傳算法

標(biāo)準(zhǔn)遺傳算法［10］采用固定的遺傳算子，如固定的交叉率和變異率，使其在進(jìn)化尋優(yōu)過(guò)程中仍然存在一定的局限性。Srinvivas等提出了自適應(yīng)遺傳算法［11］，以動(dòng)態(tài)的、隨種群進(jìn)化過(guò)程有規(guī)律變化的參數(shù)函數(shù)取代以往固定的交叉率和變異率，在保持種群多樣性的同時(shí)保證了遺傳算法的收斂性［12］。交叉率和變異率的參數(shù)函數(shù)分別為

式中，k1、k2、k3和 k4為0～1之間的常數(shù)，fmax為種群中最大適應(yīng)度值，favg為種群中平均適應(yīng)度值，f′為待交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值，f為待變異個(gè)體的適應(yīng)度值。

式（1）～（2）均僅依據(jù)個(gè)體的適應(yīng)度大小而忽略種群的進(jìn)化過(guò)程的判斷，不能完全把握種群的進(jìn)化趨勢(shì)，容易使種群陷入局部最優(yōu)?？紤]到我們希望交叉率在進(jìn)化初期不要減小得太慢，這樣可以增大種群的進(jìn)化效率；交叉率在進(jìn)化末期不要減小得太快，這樣不容易錯(cuò)過(guò)最優(yōu)解。由于交叉率的設(shè)計(jì)通常要求其值域在［0，1］之間，考慮logistic曲線(xiàn)：

y的值域恰好在［0，1］之間，而且其曲線(xiàn)圖恰好成遞減的趨勢(shì)，如圖1所示。

圖1 logistic曲線(xiàn)圖

從logistic曲線(xiàn)得到啟發(fā)，設(shè)計(jì)了一種交叉率隨進(jìn)化代數(shù)變化的自適應(yīng)交叉率函數(shù)：

式中，Pcmax為最大交叉率，t為進(jìn)化代數(shù)，T為最大進(jìn)化代數(shù)，Pcmax和t為常數(shù)。

自適應(yīng)交叉率隨相應(yīng)的進(jìn)化代數(shù)變化的曲線(xiàn)示意圖如圖2所示。

圖2 交叉率與進(jìn)化代數(shù)關(guān)系曲線(xiàn)圖

種群進(jìn)化過(guò)程中，通過(guò)AGA的交叉率函數(shù)產(chǎn)生的交叉率PcAGA可能大可能小，不一定適應(yīng)種群進(jìn)化過(guò)程中的交叉率變化規(guī)律，將 PcAGA代入改進(jìn)的自適應(yīng)交叉率函數(shù)中，可以有效避免在進(jìn)化初期小交叉和末期大交叉的可能，避免了局部最優(yōu)，同時(shí)也改善了全局收斂性和穩(wěn)定性。

本文將改進(jìn)的自適應(yīng)交叉率函數(shù)改進(jìn)的同時(shí)，融合AGA，既考慮了交叉率與個(gè)體適應(yīng)度的關(guān)系，也考慮了交叉率與進(jìn)化代數(shù)的關(guān)系，即形成了雙自適應(yīng)交叉算法，該算法由以下兩步來(lái)完成：

1）基于個(gè)體適應(yīng)度 f的交叉率算法。計(jì)算每代種群中所有個(gè)體的適應(yīng)度值，并通過(guò)對(duì)比適應(yīng)度值之間的關(guān)系來(lái)進(jìn)行交叉率計(jì)算，其中自適應(yīng)交叉概率由式（1）計(jì)算而來(lái)，計(jì)算求得的交叉率為PcAGA。

2）基于進(jìn)化代數(shù)T的交叉率算法。進(jìn)化代數(shù)不同，每代的交叉率也不同，且隨著種群的不斷進(jìn)化，交叉率不斷減少。以AGA算法求得的交叉率PcAGA為依據(jù)，將PcAGA代入到式（4）中，求取最終的交叉率。

本文采用的雙自適應(yīng)交叉算法，即依據(jù)不同的參考角度對(duì)交叉率參數(shù)進(jìn)行選取的解決思路，正是充分借鑒其自適應(yīng)的思想，克服了原AGA的缺陷，改善了遺傳算法的全局收斂性和穩(wěn)定性，避免算法陷入局部最優(yōu)。

3 改進(jìn)的Otsu圖像分割算法

3.1 最大類(lèi)間方差法

類(lèi)間最大方差法是一種自適應(yīng)閾值選?。?3］的圖像分割方法。其基本原理是以某一灰度值作為閾值t進(jìn)行圖像分割，大于t的設(shè)置為目標(biāo)類(lèi)，小于t的設(shè)置為背景類(lèi)，則圖像中的像素分成了兩類(lèi)。計(jì)算它們的方差，當(dāng)取得某一t使得兩類(lèi)的類(lèi)間方差最大時(shí)，由此閾值t對(duì)圖像進(jìn)行分割［14］。兩類(lèi)的類(lèi)間方差定義為

Otsu法求得的閾值使分割出的目標(biāo)類(lèi)和背景類(lèi)的方差越大，即使兩類(lèi)之間的距離盡可能的大，那么兩類(lèi)就分割的越明顯。式（5）可改寫(xiě)為

3.2 基于目標(biāo)背景可變的Otsu圖像分割算法

傳統(tǒng)的Otsu法僅考慮類(lèi)間像素之間的差異，而忽略類(lèi)本身像素之間的特性，造成分割效果不滿(mǎn)意。先引入了類(lèi)內(nèi)離散度［15］的概念，在實(shí)現(xiàn)類(lèi)間方差最大的基礎(chǔ)上，同時(shí)也實(shí)現(xiàn)類(lèi)內(nèi)的一致性。

定義類(lèi)內(nèi)離散度為每個(gè)像素到該類(lèi)中心μi的類(lèi)內(nèi)均方差，設(shè)目標(biāo)類(lèi)和背景類(lèi)的類(lèi)內(nèi)均方差分別為和，即

那么目標(biāo)類(lèi)和背景類(lèi)的類(lèi)內(nèi)方差之和為

定義分類(lèi)判別函數(shù)H(t)為類(lèi)間方差和類(lèi)內(nèi)方差的比值，即代入式（6）和式（9），得

由式（10）所得，當(dāng) H(t)取得最大值時(shí)所對(duì)應(yīng)的t即是所求得的最佳閾值。

但大多數(shù)文章對(duì)Otsu法的改進(jìn)在考慮類(lèi)內(nèi)最小方差時(shí)，忽視了目標(biāo)類(lèi)和背景類(lèi)類(lèi)內(nèi)方差之間的關(guān)系。本文提出一種基于目標(biāo)背景可變的閾值分割算法。該算法設(shè)計(jì)了一種新的閾值判別函數(shù)，在原有Otsu法引入總的類(lèi)內(nèi)離散度的考量外，還著重考慮了各類(lèi)的類(lèi)內(nèi)方差之間的影響，保證了圖像分割的效果較好。

本文在式（9）的基礎(chǔ)上進(jìn)行改進(jìn)，分別在目標(biāo)類(lèi)和背景類(lèi)的類(lèi)內(nèi)方差前設(shè)置一個(gè)常系數(shù)，改進(jìn)后可得

其中，k1+k2=1。將改進(jìn)后的總類(lèi)內(nèi)方差替換式（10）中的 σ2i，得到改進(jìn)后的閾值判別函數(shù)H′(t)

由式（12）所得，當(dāng) H′(t)取得最大值時(shí)所對(duì)應(yīng)的t即是所求得的最佳閾值。

當(dāng)k1=k2時(shí)，此時(shí)該式與式（10）相同。

當(dāng) k1＞k2時(shí)，在滿(mǎn)足 σ2i最小的情況下，隨著k1的增加，越小，此時(shí)目標(biāo)類(lèi)的離散度越小，則該類(lèi)中像素的一致性越高，那么此時(shí)得到偏向需要提取目標(biāo)類(lèi)中的重要信息的分割圖像。

當(dāng) k1＜k2時(shí)，在滿(mǎn)足最小的情況下，隨著k2的增加，越小，此時(shí)背景類(lèi)的離散度越小，則該類(lèi)中像素的一致性越高，那么此時(shí)得到偏向需要提取背景類(lèi)中的重要信息的分割圖像。

4 基于雙自適應(yīng)遺傳算法的改進(jìn)Otsu圖像閾值分割

Otsu法求閾值的過(guò)程其實(shí)就是尋找式（12）最優(yōu)解的過(guò)程，所以完全可以使用改進(jìn)遺傳算法來(lái)完成這一工作。

基于雙自適應(yīng)遺傳算法的改進(jìn)Otsu閾值分割算法的具體步驟如下：

Step1確定GA的控制參數(shù)；包括種群規(guī)模、交叉率Pc、變異率Pm及進(jìn)化代數(shù)等。

Step2編碼和解碼；讀入一幅彩色圖像，將其轉(zhuǎn)換為256個(gè)灰度級(jí)灰度圖像，將灰度級(jí)進(jìn)行8位二進(jìn)制編碼。算法結(jié)束后，進(jìn)行解碼操作，將8位二進(jìn)制數(shù)字串轉(zhuǎn)換為一個(gè)十進(jìn)制數(shù)，該十進(jìn)制數(shù)即為閾值T。

Step3初始化種群；本文設(shè)置初始種群為40個(gè)，并采用隨機(jī)的方式生成40個(gè)染色體作為初始種群 pop1n～pop40n。

Step4適應(yīng)度函數(shù)的設(shè)計(jì)；采用式（12）作為適應(yīng)度函數(shù)，即本文改進(jìn)的Otsu算法指導(dǎo)遺傳算法。

Step5選擇操作；本文采用輪盤(pán)賭選擇法作為選擇算子，生成種群～。

Step6交叉操作；采用本文提出的雙自適應(yīng)交叉新算法進(jìn)行單點(diǎn)交叉操作，即基于進(jìn)化代數(shù)的交叉率函數(shù)和基于個(gè)體適應(yīng)度的交叉率函數(shù)相結(jié)合的新算法進(jìn)行單點(diǎn)交叉，生成種群 pop″1n～pop，其中k1為0.25，k2為0.85。新算法共分為兩個(gè)部分。

第一部分采用自適應(yīng)遺傳算法。通過(guò)比較個(gè)體適應(yīng)度值 f與當(dāng)前種群中最大適應(yīng)度Pcmax之間的關(guān)系來(lái)計(jì)算交叉率PcAGA；

第二部分采用本文提出的自適應(yīng)交叉新算法。通過(guò)交叉率Pc隨進(jìn)化代數(shù)T之間的關(guān)系，計(jì)算交叉率Pc。

Step7變異操作；采用基因位取反的方式進(jìn)行變異，生成種群 po～po。 Pm為0.1。

Step8返回step4直至算法的終止條件：當(dāng)種群進(jìn)化到最大代數(shù)時(shí)，結(jié)束遺傳操作，此時(shí)輸出最優(yōu)解，即最佳閾值T。

Step9分割圖像；使用T將灰度值劃分為兩類(lèi)，將灰度值小于T的像素點(diǎn)都賦值為0，而將灰度值大于T或等于的像素點(diǎn)都賦值為1，這樣就將原來(lái)的灰度圖像變?yōu)槎祱D像，從而達(dá)到將原圖像中目標(biāo)和背景進(jìn)行分割的目的。

5 仿真結(jié)果及分析

為驗(yàn)證上述方法的有效性和準(zhǔn)確性，本文利用Matlab編程語(yǔ)言實(shí)現(xiàn)自編程序的Otsu算法、基于遺傳算法的Otsu法及本論文所提出的新算法，對(duì)數(shù)字圖像Lena（256*256）、twelve圖像（350*350）及教室內(nèi)監(jiān)控圖像（800*450）分別進(jìn)行分割，對(duì)比分析實(shí)驗(yàn)的結(jié)果。

圖4 lena圖分割效果對(duì)比圖

圖5 twelve圖像分割效果對(duì)比圖

圖6 教室監(jiān)控圖像分割效果對(duì)比圖

表1 Otsu法、基本遺傳算法與本文算法與運(yùn)算時(shí)間與閾值比較

從圖4、5和6的三個(gè)實(shí)驗(yàn)對(duì)象的分割結(jié)果對(duì)比來(lái)看，顯然本文算法分割效果在很多細(xì)節(jié)的處理上比Otsu法及遺傳算法的分割圖像效果較好。lena圖像中帽子毛穗特征更細(xì)膩，教室監(jiān)控圖像中人物與背景等分離更明顯。尤其是twelve圖像中，三種算法對(duì)其分割的效果明顯差別最大。本文算法統(tǒng)籌考慮了類(lèi)內(nèi)和類(lèi)間之間的關(guān)系，不僅使兩類(lèi)之間距離越大，同時(shí)也保證了類(lèi)內(nèi)的內(nèi)聚性，滿(mǎn)足分割要求，因此本文算法更適合圖像的分割，尤其是對(duì)復(fù)雜圖像的分割。

經(jīng)典Otsu法、基于遺傳算法的Otsu法及本文算法的運(yùn)算時(shí)間與閾值比較如表1所示。其中，運(yùn)算時(shí)間及閾值均取10次運(yùn)算的平均值。

從表中可以看出對(duì)于lena、twelve及教室監(jiān)控圖像三幅圖像，利用遺傳算法進(jìn)行分割所用的時(shí)間均明顯減少，可見(jiàn)遺傳算法與Otsu相結(jié)合可以大大提高算法的運(yùn)算速率。而基于遺傳算法的Otsu圖像分割與本文算法時(shí)間相差不大。

本文算法與Otsu算法相比，對(duì)于lena圖像，本文算法進(jìn)行分割所用時(shí)間僅為0.267s，而利用Otsu法進(jìn)行分割用時(shí)為0.528s；對(duì)于twelve圖像，本文算法進(jìn)行分割所用時(shí)間為0.282s，而利用Otsu法進(jìn)行分割用時(shí)則為0.541s；對(duì)于教室監(jiān)控圖像這種較大較復(fù)雜的圖像效果尤其明顯，本文算法進(jìn)行分割所用時(shí)間為0.785s，而利用Otsu法進(jìn)行分割用時(shí)則為4.214s。

6 結(jié)語(yǔ)

本文在研究類(lèi)間最大方差的基礎(chǔ)上，對(duì)類(lèi)間最大方差法進(jìn)行了改進(jìn)，并利用遺傳算法具有的快速尋優(yōu)特點(diǎn)，將自適應(yīng)遺傳算法進(jìn)行改進(jìn)，融合交叉率與進(jìn)化代數(shù)之間的關(guān)系，提出雙自適應(yīng)遺傳算法。在改進(jìn)算法的具體實(shí)現(xiàn)中，引入雙自適應(yīng)策略，改善了算法的全局收斂性及穩(wěn)定性。實(shí)驗(yàn)結(jié)果表明：本文提出的基于雙自適應(yīng)遺傳算法的改進(jìn)Otsu閾值分割方法，與傳統(tǒng)的Otsu法及遺傳算法相比，改善了圖像分割效果，減少了圖像分割時(shí)間，尤其在處理較大圖像或者細(xì)節(jié)較多的圖像時(shí)，該算法顯示出優(yōu)越性，具有一定的實(shí)用價(jià)值。

［1］譚優(yōu)，王澤勇.圖像閾值分割算法實(shí)用技術(shù)研究與比較［J］.微計(jì)算機(jī)信息，2007，23（24）：298-299，233.

TANYou，Wang Zeyong.Study on applied technology arithmetic of image threshold segmentation［J］.Microcomputer Information，2007，23（24）：298-299，233.

［2］S.Sharma，D.Shah.A Practical Animal Detection and Collision Avoidance System Using Computer Vision Technique［J］.IEEEAccess ，2016：1-1.

［3］劉紫燕，吳俊熊，毛攀，等.基于遺傳模擬退火算法的

Otsu圖像分割研究［J］.電視技術(shù)，2016，40（8）：15-18.LIUZhiyan，WUJunxiong，MAOPan，et al.Image segmentation on genetic simulated annealing algorithm［J］.Video engineering，2016，40（8）：15－18.

［4］師文，朱學(xué)芳，朱光.基于形態(tài)學(xué)的MRI圖像自適應(yīng)邊緣檢測(cè)算法［J］.儀器儀表學(xué)報(bào)，2013，34（2）：408-414.

SHI Wen，ZHU Xuefang，ZHU Guang.A daptive edge detection algorithm of MRI image based on morphology［J］.Chinese Journal of Scientific Instrument，2013，34（2）：408-414.

［5］Qin A K，Claus DA.Multivariate Image Segmentation Using Semantic Region Growing With Adaptive Edge Penalty Image Processing［J］.IEEETransactions on 2010，19（8）：2167-2169.

［6］OTSU N.A threshold selection method from gray level histograms［J］.IEEE Trans on SMC，1979，9（1）：62-69.

［7］WANG F J，LI J L，LIU SW，et al.An improved adaptive genetic algorithm for image segmentation and vision alignment used in microelectronic bonding［J］.IEEE transactions on mechatronics，2014，19（3）：916-923.

［8］TAO W B，JIN H.Image thresholding using graph cuts［J］.IEEE Transactions on Systems，Man，and Cybernetics，2008，38（5）：1181-1194.

［9］劉秋生，楚來(lái)國(guó)，楊繼昌.基于遺傳優(yōu)化的閾值選取方法［J］.信號(hào)處理，2002，18（4）：374-377.

LIU Qiusheng，CHU Laiguo，YANG Jichang.Seleotion of lmage Threshold on the Basis of Genetie Algorithms［J］.Signal Processing，2002，18（4）：374-377.

［10］Zhang L，Chang H，Xu R.Equal-width partitioning roulette wheel selection in genetic algorithm［C］//Technologies and Applications of Artificial Intelligence（TAAI），2012 Conference on IEEE，2012：62-67.

［11］鄺航宇，金晶，蘇勇.自適應(yīng)遺傳算法交叉變異算子的改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42（12）：93-96，99.

KUANG Hangyu，JIN Jing，SU Yong.Improving Crossover and Mutation for Adaptive Genetic Algorithm［J］.Computer Enginerring and Applications，2006，42（12）：93-96，99.

［12］何春華，胡迎春.基于改進(jìn)遺傳算法的自動(dòng)閾值圖像分割方法［J］.計(jì)算機(jī)仿真，2011（2）：312-315.

HE Chunhua，HU Yingchun.Automatic Threshold Image Segmentation Approach Baced on Improved Genetic Algorithm［J］.Computer Simulation，2011（2）：312-315.

［13］Haralick RM，Shapiro LG，Image Segmentation techniques［J］.CVGIP，1985，29（37）：100-132.

［14］王爽，黃友銳，李冬.基于蟻群算法的改進(jìn)Otsu理論的圖像多閾值分割［J］.微計(jì)算機(jī)應(yīng)用，2008，29（4）：25-28.

WANG Shuang，HUANG Yourui，LI Dong.Multilevel Thresholging Methods for Image Segmentation with Improved Otsu Based on Ant Colony Algorithm［J］.Microcomputer Applications，2008，29（4）：25-28.

［15］周云燕，楊坤濤，黃鷹.基于最小類(lèi)內(nèi)離散度的改進(jìn)Otsu分割方法的研究［J］.華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，35（2）：101-103.

ZHOU Yunyan，YANG Kuntao，HUANG Ying.Improved Otsu Thresholding Based on Minimum Inner-cluster Variance［J］.J.Huazhong Univ.of Sci.&Tech.（Nature Science Edition），2007，35（2）：101-103.