基于改進差分進化算法的多閾值圖像分割①

楊兆龍, 劉秉瀚

(福州大學 數學與計算機科學學院, 福州 350108)

基于改進差分進化算法的多閾值圖像分割①

楊兆龍, 劉秉瀚

(福州大學 數學與計算機科學學院, 福州 350108)

閾值法是一種簡單有效的圖像分割技術. 但是閾值法也有著明顯的缺點, 即閾值求解的計算量隨閾值的增加而指數級增長. 為克服多閾值圖像分割計算量大、運算時間長的缺點, 引入改進的差分進化算法, 提出新的變異策略, 采用自適應的縮放因子和交叉系數,并新增擾動策略. 改進的算法將多閾值分割模型視為優化問題,將最大類間方差法作為目標函數, 實現多閾值分割. 實驗結果表明, 和其它算法相比, 該算法不僅可以取得正確的分割結果, 而且分割速度更快.

圖像分割; 多閾值; 差分進化算法; 最大類間方差; 灰度圖像

圖像分割目的是將一幅圖像劃分成若干個具有某種均勻一致性的區域, 把人們“感興趣的目標物”從復雜的場景中提取出來. 閾值分割法是一種傳統的圖像分割方法, 因其實現簡單、性能較穩定而成為圖像分割中最基本和應用最廣泛的分割方法. 其中閾值的選取是圖像閾值分割方法的關鍵技術. 常見的計算閾值的方法有最大類間方差法(Otsu算法)[1]、最大熵法[2,3]和最小誤差法[4]等. 上述計算閾值方法基本是在滿足一定準則下通過解析式求得閾值. 比如Otsu算法利用圖像灰度的一維概率直方圖, 以最大可分性為準則,自適應地選取分割閾值, 實現圖像分割, 具有算法簡單易實現的優點. 但是包括Otsu算法在內的通過解析式求解閾值的算法, 當擴展到多閾值圖像分割時, 搜索空間大、計算復雜度高、計算量大和耗時長的缺點便呈現出來.

圖像多閾值分割可以被視為一個優化問題, 因此很多學者將智能優化算法應用于閾值求解. 比如: 基于遺傳算法[5]、基于改進量子粒子群優化算法[6]、基于螢火蟲算法[7]、基于反向螢火蟲算法[8]、基于改進魚群算法[9]和回溯搜索優化算法[10]等等. 這些基于智能優化的分割算法的優化函數常采用Otsu方法或熵函數,設計一些獨特的計算技巧來提高算法的性能, 運用智能優化達到求解所要分割圖像的優化函數的目的.

差分進化算法(Differential Evolution DE)[11]是1997年由Storn和Price提出的一種基于種群迭代的隨機搜索算法, 該算法從原始種群開始, 先通過交叉、變異、選擇幾種遺傳操作來衍生出新的種群, 然后通過逐步迭代, 不斷進化實現全局最優解的搜索, 因此也是一種并行隨機搜索算法. 差分進化算法具有原理簡單、控制參數少、魯棒性強、收斂速度快等優點. 因而引起了眾多學者的關注, 提出了很多基于差分進化算法的改進及應用[12-17]. 其中文獻[17]將改進的差分進化算法應用與圖像的多閾值分割中, 實驗取得了較好的結果.

文獻[17]提出基于Beta分布的縮放因子和交叉系數, 兩個參數在區間[0,1]范圍內有更高的頻率取到兩端極值. 這樣算法在大部分迭代過程中兩個參數可以在區間[0,1]上取到不同的極值, 產生全新的個體, 加強算法搜索過程, 改進原算法中縮放因子和交叉系數保持不變的缺陷. 然而差分進化算法的搜索性能取決于全局探索和局部開發能力的平衡, 而這在很大程度上依賴于算法的控制參數選取, 包括變異策略、縮放因子和交叉概率等[18]. 文獻[17]雖然可以取得正確的圖像分割閾值, 但耗時較大, 不適用于對圖像分割實時性要求高的場合. 因此本文提出改進的DE算法, 采用多種群并行的變異策略, 以提高收斂速度和維持種群多樣性. 同時, 再采用自適應的縮放因子和交叉概率以平衡局部搜索和全局搜索. 將本文的改進差分進化算法用于圖像分割中閾值的選擇, 以最大類間方差作為目標函數進行優化, 并與文獻[17]中提出改進的差分進化算法作比較, 實驗結果表明本文的算法不僅可以取得正確的分割結果, 而且分割速度更快, 適應于實時性要求高的圖像多閾值分割場合.

1 差分進化算法

1.1 經典的差分進化算法

差分進化算法[11]是一種基于群體智能的優化算法,算法利用群體中個體之間的差異信息引導算法進行搜索, 通過變異、交叉、選擇三步操作實現種群的進化和優化搜索.

DE算法流程如下: 1) 初始化種群.

初始種群隨機產生:

其中,x0,i表示種群中第0代的第i個個體,x0,j,i表示第0代第i個個體的第j個分量.和分別表示第j個分量取值范圍的上界和下界.NP表示種群大小,rand(0,1)表示在(0,1)區間均勻分布的隨機數.

2) 變異操作. DE通過差分策略實現個體變異, 這也是DE差異進化思想的體現, 其根據當前個體, 在種群中隨機選擇幾個向量進行差分操作并產生一個差分向量, 最常見的差分變異策略有以下五種:

其中xg,i代表種群第g代的第i個個體.i1,i2,i3,i4,i5分別表示從當前種群中隨機選擇的5個不同的個體.xg,best當前第g代及之前的最優個體,F為縮放因子.

3) 交叉操作. 對第g代個體及xg,i其變異的中間體vg,i進行個體間的交叉操作:

其中,CR為交叉概率,j是正整數且1≤j≤D,D是種群個體最大維數,jrand為1到D的隨機整數.

4) 選擇操作. DE采用貪婪算法來選擇進入下一代種群的個體, 經過變異和交叉操作后生成的試驗個體ug,i與xg,i進行競爭. 只有當的ug,i適應度較xg,i更優時才被選作子代; 否則xg,i直接作為子代. 選擇操作方程為:

1.2 改進的差分進化算法

為了提高差分進化算法收斂速度和維持種群多樣性并克服差分進化算法易早熟、易陷入局部最優的缺點. 本文對縮放因子、變異策略的選擇、交叉概率的設置作了改進, 采用多種群并行的變異策略, 自適應選擇縮放因子和交叉概率以平衡局部搜索和全局搜索,同時增加了擾動策略, 拋棄適應度低的種群個體.

具體的改進措施見下:

1) 變異策略的選擇. 以最大類間方差函數作為適應度函數, 以適應度值排序, 按中值將種群分為兩類. ①適應度小的一類選擇全局最優變異策略進行變異(式(9)), 加速收斂. ②適應度大的一類迭代前期偏向選擇隨機變異策略, 迭代后期偏向選擇全局最優變異策略(式(10)). 這樣前期保持了種群的多樣性, 避免局部最優, 后期既加速收斂速度, 也有利于局部精細搜索, 尋找更佳的圖像分割閾值組合.

其中,G表示當前的迭代次數,Gmax表示總的迭代次數.F為縮放因子, F較大時能產生較大的擾動, 從而有利于保持種群的多樣性, 在圖像閾值搜索中更全面, 避免收斂到局部最優值.F較小, 擾動較小, 縮放因子能起到局部精細化搜索的作用. 且文獻[19]通過對差分進化算法縮放因子的不同取值策略研究得出開口向上拋物線策略略優于指數策略, 指數策略優于慣性(線性)策略, 而慣性策略優于開口向下策略. 故本文縮放因子采用開口向上拋物線策略, 具體見下式:

Fmin為最小的縮放因子,Fmax為最大的縮放因子.

2) 交叉概率CR的選擇. 較大的CR可以增大交叉概率, 加速收斂, 較小的CR有利于保留最優個體,增強算法魯棒性. 因此本文采用下式調整CR:

其中,CRmax為最大的交叉系數,CRmin為最小的交叉系數.

3) 新增擾動策略. 對交叉后產生的新種群, 按照適應值大小重新排序, 對適應值最低的兩個個體采取拋棄策略, 從種群中剔除, 種群同時重新隨進生成新的兩個個體進入下一次迭代中.

1.3 改進算法的流程

① 初始化種群, 即隨機產生2*N個個體.

② 依據每個個體的適應度大小, 將種群按中值分為兩個子種群, 每個種群大小為N.

③ 適應度較高的子種群采用式(10)的變異策略,另一適應度較低的種群采用式(9)變異策略.

④ 在步驟③的基礎上兩個子群的個體分別進行交叉操作, 交叉概率CR依據式(12)選取.

⑤ 選擇. 交叉產生的個體和初始個體中選擇保留較優的個體進入下一步.

⑥ 判斷是否滿足算法終止條件. 若滿足, 算法結束, 否則進入步驟⑦.

⑦ 兩個子群在步驟⑤產生的個體集中在一起再次依據其適應度大小排序, 拋棄適應度最小的2個個體, 隨機生成新的2個個體. 返回步驟②, 算法進入下一次迭代中.

2 實驗結果與分析

為了驗證本文算法對圖像多閾值分割的有效性和運行速度上的優越性, 文章選取了Lenna圖、Camera圖和Baboon圖(圖1)作為實驗對象進行圖像多閾值分割, 并與文獻[17]中BDE算法作比較. 實驗是在3.30GHz CPU、4G內存的PC機和MATLAB 2012a 環境中進行.

圖1 原始圖像

依文獻[17]所述, BDE算法參數設置如下: 縮放因子F和交叉系數CR按Beta分布自適應選取, 初始種群個體數80, 最大迭代次數40.

文獻[20]對DE算法的參數展開了詳細的數值分析, 指出了DE算法性能對參數敏感的問題, 這些參數不僅與具體問題相關, 而且它們之間也相互影響. 該文獻通過大量實驗推薦F初始值為0.6, 交叉系數取值介于0.3～0.9之間. 因此, 本文參數設置如下:Fmin=CRmin=0.3,Fmax=CRmax=0.9. 這樣依據式(11),縮放因子F的取值在0.6附近由增遞減. 依據式(12),交叉系數CR介于0.3～0.9. 同時經過多次實驗初始種群個體數設置為20, 最大迭代次數20.

2.1 圖像分割結果比較

每種算法針對不同的圖像分別運行10次, 取10次運行結果的平均值作為圖像最終分割的結果.

圖2 文獻[17]BDE算法圖像的雙閾值分割

圖3 本文算法圖像的雙閾值分割

圖4 文獻[17]BDE算法圖像的三閾值分割

圖5 本文算法圖像的三閾值分割

圖6 文獻[17]BDE算法圖像的四閾值分割

圖7 本文算法圖像的四閾值分割

以雙閾值、三閾值和四閾值分割為例, 從圖2、圖3、圖4、圖5、圖6和圖7的分割效果看, 不同的算法分割效果幾乎一樣, 并無明顯的不同. 從時間性能比較, 見表1、表2和表3.

表1 圖像的雙閾值及運行時間

表2 圖像的三閾值及運行時間

表3 圖像的四閾值及運行時間

由表1、表2和表3可知, 所有的分割算法都能取得相似的分割結果, 分割的閾值相近. 但不同的算法分割時間卻相差較大. 文獻[17]和本文算法對比可知,本文算法的耗時要遠遠少于文獻[17]的算法. 而且文獻[17]在雙閾值圖像分割和三閾值圖像分割的運行時間對比, 三閾值的圖像分割要比雙閾值圖像分割的耗時明顯多一些. 但本文算法中雙閾值、三閾值和四閾值圖像分割時間對比可知, 本文算法隨著閾值的增加,耗時幾乎不變, 這說明本文算法更穩定.

3 結語

本文提出的基于改進的差分進化算法能夠充分利用差分進化的特點, 較好的解決了圖像多閾值選取過程中計算量大、耗時長的缺點, 提高了圖像分割速度,有利于圖像的后續處理, 適應于實時性要求高的場合.但本文只考慮了無噪聲灰度圖像的分割, 因此, 對于彩色圖像和含噪聲圖像的分割是作者今后的研究方向.

1 Otsu N. A Threshold selection method from gray level histogram. IEEE Trans. on System Manand Cybernetics, 1979, 9(1): 62–66.

2 Pun T. A new method for grey-level picture thresholding using the entropy of the histogram. Signal Processing, 1980, 2(3): 223–237.

3 Kapur JN, Sahoop K, Wong AKC. A new method for gray-level picture thresholding using the entropy of the histogram. Computer Vision, Graphics and Image Processing, 1985, 29(3): 273–285.

4 Kittler J, Illingworth J. Minimum error thresholding. Pattern Recognition, 1986, 19(1): 41–47.

5 Tang KZ, Yuan XJ, Sun TK, et al. An improved scheme for minimum cross entropy threshold selection based on genetic algorithm. Knowledge-Based Systems, 2011, 24(8): 1131– 38.

6 楊震倫.閔華清.羅榮華.基于改進量子粒子群優化的多閾值圖像分割算法.華南理工大學學報(自然科學版),2015,(5).

7 陳愷,陳芳,戴敏,張志勝,史金飛.基于螢火蟲算法的二維熵多閾值快速圖像分割.光學精密工程,2014,(2).

8 陳愷,戴敏,張志勝,陳平,史金飛.基于反向螢火蟲算法的多閾值缺陷圖像分割.東南大學學報(英文版),2014,(4).

9 崔麗群,宋曉,李鴻緒,張明杰.基于改進魚群算法的多閾值圖像分割.計算機科學,2014,(8).

10 尹雨山.王李進.尹義龍.王冰清.趙文婷.徐云龍.回溯搜索優化算法輔助的多閾值圖像分割.智能系統學報,2015,(1).

11 Storn R, Price K．Differential evolutiona simple and efficient heuristic for global optimization over continuous spaces. Joumal of Global Optimization, 1997, 11(4): 341–359．

12 邱曉紅,江陽,李渤.分形變異因子修正的差分進化算法.模式識別與人工智能,2015,(2):132–138.

13 康忠健,訾淑偉.基于差分進化算法的油田區域配電網無功優化技術的研究.電工技術學報,2014,28(6):226–231.

14 董麗麗,黃賁,介軍.云計算中基于差分進化算法的任務調度研究.計算機工程與應用,2014,(5):90–95.

15 Chen N, Chen WN, Zhang J. Fast detection of human using differential evolution. Signal Processing, 2015, 110(2): 155–163

16 Niu Q, Li K, Irwin GW. Differential evolution combined with clonal selection for dynamic economic dispatch. Journal of Experimental & Theoretical Artificial Intelligence, 2015, 27(3): 325–350

17 Ayala HVH, dos Santos FM, Mariani VC, Coelho LdS. Image thresholding segmentation based on a novel beta differentialevolution approach. Expert Systems with Applications, 2015, (42): 2136–2142.

18 高岳林,劉軍民.差分進化算法的參數研究.黑龍江大學自然科學學報,2009,26(1):81–85.

19 姜立強,郭錚,劉光斌.儀表、自動化與先進集成技術大會, 2007.

20 Gamperle R, Muller S, Koumoutsakos P. A parameter study for differential evolution. Wseas Int Conf on Advances in Intelligent Systems, Fuzzy Systems, Evolutionary Computation. Interlaken, Switzerland. 2002. 293–298.

Multi-Threshold Image Segmentation Method Based on Improved Differential Evolution Algorithm

YANG Zhao-Long, LIU Bing-Han
(College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China)

The threshold method is a simple and effective image segmentation technique. However, the threshold method also has obvious disadvantage, the amount of calculation for solving threshold appears to be exponential amplification with the increase of threshold. In order to overcome the shortcomings of large computation load and long computation time for multi-threshold image segmentation, we introduce an improved differential evolution algorithm, which proposes a new mutation strategy, adopts self-adaption scaling factor and cross factor, and newly adds Perturbation strategy. In order to achieve multi-threshold segmentation, the improved algorithm considers multi-threshold segmentation as an optimization problem whose objective function is formulated according to Otsu. Experimental results show that compared with other algorithms, the improved algorithm not only can achieve an accurate image segmentation result, but also has a faster speed.

image segmentation; multi-threshold; differential evolution(DE); Otsu; gray image

福建省科技廳項目(2013J01186, JK2010056);福建省教育廳項目(JB10160)

2016-03-30;收到修改稿時間:2016-06-21

10.15888/j.cnki.csa.005537