基于雙自適應遺傳算法的Otsu圖像分割研究?

廖延娜 李夢君

1 引言

圖像分割［1］是圖像處理與計算機視覺［2］的基本問題之一，是進行圖像分析、特征提取和目標識別的基礎，圖像分割的好處直接影響到后續圖像的處理。近年來，圖像分割一直是人們研究關注的熱點和重點，圖像分割的方法很多，大體可分為三類：閾值分割法［3］、邊緣檢測法［4］和區域法［5］等。類間最大方差法［6］作為傳統的閾值分割技術被大多數人所熟知，它具有計算簡單、分割效果較優等優點，但由于Otsu法計算量大、效率不高、分割效果不可靠等缺點，有學者將遺傳算法［7］與類間最大方差法相結合，借鑒遺傳算法并行性、搜索能力強等優點，進行圖像閾值［8］尋優。

文獻［9］利用傳統的遺傳算法與Otsu法相結合的方法大大提高了圖像分割的效率，但標準遺傳算法存在易早熟、易陷入局部最優的缺點，本文對相關算法進行改進，提出一種基于雙自適應遺傳算法的Otsu閾值分割算法。

2 改進的雙自適應遺傳算法

標準遺傳算法［10］采用固定的遺傳算子，如固定的交叉率和變異率，使其在進化尋優過程中仍然存在一定的局限性。Srinvivas等提出了自適應遺傳算法［11］，以動態的、隨種群進化過程有規律變化的參數函數取代以往固定的交叉率和變異率，在保持種群多樣性的同時保證了遺傳算法的收斂性［12］。交叉率和變異率的參數函數分別為

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

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

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

圖1 logistic曲線圖

從logistic曲線得到啟發，設計了一種交叉率隨進化代數變化的自適應交叉率函數：

式中，Pcmax為最大交叉率，t為進化代數，T為最大進化代數，Pcmax和t為常數。

自適應交叉率隨相應的進化代數變化的曲線示意圖如圖2所示。

圖2 交叉率與進化代數關系曲線圖

種群進化過程中，通過AGA的交叉率函數產生的交叉率PcAGA可能大可能小，不一定適應種群進化過程中的交叉率變化規律，將 PcAGA代入改進的自適應交叉率函數中，可以有效避免在進化初期小交叉和末期大交叉的可能，避免了局部最優，同時也改善了全局收斂性和穩定性。

本文將改進的自適應交叉率函數改進的同時，融合AGA，既考慮了交叉率與個體適應度的關系，也考慮了交叉率與進化代數的關系，即形成了雙自適應交叉算法，該算法由以下兩步來完成：

1）基于個體適應度 f的交叉率算法。計算每代種群中所有個體的適應度值，并通過對比適應度值之間的關系來進行交叉率計算，其中自適應交叉概率由式（1）計算而來，計算求得的交叉率為PcAGA。

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

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

3 改進的Otsu圖像分割算法

3.1 最大類間方差法

類間最大方差法是一種自適應閾值選取［13］的圖像分割方法。其基本原理是以某一灰度值作為閾值t進行圖像分割，大于t的設置為目標類，小于t的設置為背景類，則圖像中的像素分成了兩類。計算它們的方差，當取得某一t使得兩類的類間方差最大時，由此閾值t對圖像進行分割［14］。兩類的類間方差定義為

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

3.2 基于目標背景可變的Otsu圖像分割算法

傳統的Otsu法僅考慮類間像素之間的差異，而忽略類本身像素之間的特性，造成分割效果不滿意。先引入了類內離散度［15］的概念，在實現類間方差最大的基礎上，同時也實現類內的一致性。

定義類內離散度為每個像素到該類中心μi的類內均方差，設目標類和背景類的類內均方差分別為和，即

那么目標類和背景類的類內方差之和為

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

由式（10）所得，當 H(t)取得最大值時所對應的t即是所求得的最佳閾值。

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

本文在式（9）的基礎上進行改進，分別在目標類和背景類的類內方差前設置一個常系數，改進后可得

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

由式（12）所得，當 H′(t)取得最大值時所對應的t即是所求得的最佳閾值。

當k1=k2時，此時該式與式（10）相同。

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

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

4 基于雙自適應遺傳算法的改進Otsu圖像閾值分割

Otsu法求閾值的過程其實就是尋找式（12）最優解的過程，所以完全可以使用改進遺傳算法來完成這一工作。

基于雙自適應遺傳算法的改進Otsu閾值分割算法的具體步驟如下：

Step1確定GA的控制參數；包括種群規模、交叉率Pc、變異率Pm及進化代數等。

Step2編碼和解碼；讀入一幅彩色圖像，將其轉換為256個灰度級灰度圖像，將灰度級進行8位二進制編碼。算法結束后，進行解碼操作，將8位二進制數字串轉換為一個十進制數，該十進制數即為閾值T。

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

Step4適應度函數的設計；采用式（12）作為適應度函數，即本文改進的Otsu算法指導遺傳算法。

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

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

第一部分采用自適應遺傳算法。通過比較個體適應度值 f與當前種群中最大適應度Pcmax之間的關系來計算交叉率PcAGA；

第二部分采用本文提出的自適應交叉新算法。通過交叉率Pc隨進化代數T之間的關系，計算交叉率Pc。

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

Step8返回step4直至算法的終止條件：當種群進化到最大代數時，結束遺傳操作，此時輸出最優解，即最佳閾值T。

Step9分割圖像；使用T將灰度值劃分為兩類，將灰度值小于T的像素點都賦值為0，而將灰度值大于T或等于的像素點都賦值為1，這樣就將原來的灰度圖像變為二值圖像，從而達到將原圖像中目標和背景進行分割的目的。

5 仿真結果及分析

為驗證上述方法的有效性和準確性，本文利用Matlab編程語言實現自編程序的Otsu算法、基于遺傳算法的Otsu法及本論文所提出的新算法，對數字圖像Lena（256*256）、twelve圖像（350*350）及教室內監控圖像（800*450）分別進行分割，對比分析實驗的結果。

圖4 lena圖分割效果對比圖

圖5 twelve圖像分割效果對比圖

圖6 教室監控圖像分割效果對比圖

表1 Otsu法、基本遺傳算法與本文算法與運算時間與閾值比較

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

經典Otsu法、基于遺傳算法的Otsu法及本文算法的運算時間與閾值比較如表1所示。其中，運算時間及閾值均取10次運算的平均值。

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

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

6 結語

本文在研究類間最大方差的基礎上，對類間最大方差法進行了改進，并利用遺傳算法具有的快速尋優特點，將自適應遺傳算法進行改進，融合交叉率與進化代數之間的關系，提出雙自適應遺傳算法。在改進算法的具體實現中，引入雙自適應策略，改善了算法的全局收斂性及穩定性。實驗結果表明：本文提出的基于雙自適應遺傳算法的改進Otsu閾值分割方法，與傳統的Otsu法及遺傳算法相比，改善了圖像分割效果，減少了圖像分割時間，尤其在處理較大圖像或者細節較多的圖像時，該算法顯示出優越性，具有一定的實用價值。

［1］譚優，王澤勇.圖像閾值分割算法實用技術研究與比較［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］.電視技術，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］師文，朱學芳，朱光.基于形態學的MRI圖像自適應邊緣檢測算法［J］.儀器儀表學報，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］劉秋生，楚來國，楊繼昌.基于遺傳優化的閾值選取方法［J］.信號處理，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］鄺航宇，金晶，蘇勇.自適應遺傳算法交叉變異算子的改進［J］.計算機工程與應用，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］.計算機仿真，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］王爽，黃友銳，李冬.基于蟻群算法的改進Otsu理論的圖像多閾值分割［J］.微計算機應用，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］周云燕，楊坤濤，黃鷹.基于最小類內離散度的改進Otsu分割方法的研究［J］.華中科技大學學報（自然科學版），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.