楊兆龍, 劉秉瀚

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 福州 350108)

基于改進(jìn)差分進(jìn)化算法的多閾值圖像分割①

楊兆龍, 劉秉瀚

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 福州 350108)

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

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

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

圖像多閾值分割可以被視為一個(gè)優(yōu)化問(wèn)題, 因此很多學(xué)者將智能優(yōu)化算法應(yīng)用于閾值求解. 比如: 基于遺傳算法[5]、基于改進(jìn)量子粒子群優(yōu)化算法[6]、基于螢火蟲(chóng)算法[7]、基于反向螢火蟲(chóng)算法[8]、基于改進(jìn)魚(yú)群算法[9]和回溯搜索優(yōu)化算法[10]等等. 這些基于智能優(yōu)化的分割算法的優(yōu)化函數(shù)常采用Otsu方法或熵函數(shù),設(shè)計(jì)一些獨(dú)特的計(jì)算技巧來(lái)提高算法的性能, 運(yùn)用智能優(yōu)化達(dá)到求解所要分割圖像的優(yōu)化函數(shù)的目的.

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

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

1 差分進(jìn)化算法

1.1 經(jīng)典的差分進(jìn)化算法

差分進(jìn)化算法[11]是一種基于群體智能的優(yōu)化算法,算法利用群體中個(gè)體之間的差異信息引導(dǎo)算法進(jìn)行搜索, 通過(guò)變異、交叉、選擇三步操作實(shí)現(xiàn)種群的進(jìn)化和優(yōu)化搜索.

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

初始種群隨機(jī)產(chǎn)生:

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

2) 變異操作. DE通過(guò)差分策略實(shí)現(xiàn)個(gè)體變異, 這也是DE差異進(jìn)化思想的體現(xiàn), 其根據(jù)當(dāng)前個(gè)體, 在種群中隨機(jī)選擇幾個(gè)向量進(jìn)行差分操作并產(chǎn)生一個(gè)差分向量, 最常見(jiàn)的差分變異策略有以下五種:

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

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

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

4) 選擇操作. DE采用貪婪算法來(lái)選擇進(jìn)入下一代種群的個(gè)體, 經(jīng)過(guò)變異和交叉操作后生成的試驗(yàn)個(gè)體ug,i與xg,i進(jìn)行競(jìng)爭(zhēng). 只有當(dāng)?shù)膗g,i適應(yīng)度較xg,i更優(yōu)時(shí)才被選作子代; 否則xg,i直接作為子代. 選擇操作方程為:

1.2 改進(jìn)的差分進(jìn)化算法

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

具體的改進(jìn)措施見(jiàn)下:

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

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

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

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

其中,CRmax為最大的交叉系數(shù),CRmin為最小的交叉系數(shù).

3) 新增擾動(dòng)策略. 對(duì)交叉后產(chǎn)生的新種群, 按照適應(yīng)值大小重新排序, 對(duì)適應(yīng)值最低的兩個(gè)個(gè)體采取拋棄策略, 從種群中剔除, 種群同時(shí)重新隨進(jìn)生成新的兩個(gè)個(gè)體進(jìn)入下一次迭代中.

1.3 改進(jìn)算法的流程

① 初始化種群, 即隨機(jī)產(chǎn)生2*N個(gè)個(gè)體.

② 依據(jù)每個(gè)個(gè)體的適應(yīng)度大小, 將種群按中值分為兩個(gè)子種群, 每個(gè)種群大小為N.

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

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

⑤ 選擇. 交叉產(chǎn)生的個(gè)體和初始個(gè)體中選擇保留較優(yōu)的個(gè)體進(jìn)入下一步.

⑥ 判斷是否滿足算法終止條件. 若滿足, 算法結(jié)束, 否則進(jìn)入步驟⑦.

⑦ 兩個(gè)子群在步驟⑤產(chǎn)生的個(gè)體集中在一起再次依據(jù)其適應(yīng)度大小排序, 拋棄適應(yīng)度最小的2個(gè)個(gè)體, 隨機(jī)生成新的2個(gè)個(gè)體. 返回步驟②, 算法進(jìn)入下一次迭代中.

2 實(shí)驗(yàn)結(jié)果與分析

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

圖1 原始圖像

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

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

2.1 圖像分割結(jié)果比較

每種算法針對(duì)不同的圖像分別運(yùn)行10次, 取10次運(yùn)行結(jié)果的平均值作為圖像最終分割的結(jié)果.

圖2 文獻(xiàn)[17]BDE算法圖像的雙閾值分割

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

圖4 文獻(xiàn)[17]BDE算法圖像的三閾值分割

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

圖6 文獻(xiàn)[17]BDE算法圖像的四閾值分割

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

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

表1 圖像的雙閾值及運(yùn)行時(shí)間

表2 圖像的三閾值及運(yùn)行時(shí)間

表3 圖像的四閾值及運(yùn)行時(shí)間

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

3 結(jié)語(yǔ)

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

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 楊震倫.閔華清.羅榮華.基于改進(jìn)量子粒子群優(yōu)化的多閾值圖像分割算法.華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,(5).

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

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

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

10 尹雨山.王李進(jìn).尹義龍.王冰清.趙文婷.徐云龍.回溯搜索優(yōu)化算法輔助的多閾值圖像分割.智能系統(tǒng)學(xué)報(bào),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 邱曉紅,江陽(yáng),李渤.分形變異因子修正的差分進(jìn)化算法.模式識(shí)別與人工智能,2015,(2):132–138.

13 康忠健,訾淑偉.基于差分進(jìn)化算法的油田區(qū)域配電網(wǎng)無(wú)功優(yōu)化技術(shù)的研究.電工技術(shù)學(xué)報(bào),2014,28(6):226–231.

14 董麗麗,黃賁,介軍.云計(jì)算中基于差分進(jìn)化算法的任務(wù)調(diào)度研究.計(jì)算機(jī)工程與應(yīng)用,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 高岳林,劉軍民.差分進(jìn)化算法的參數(shù)研究.黑龍江大學(xué)自然科學(xué)學(xué)報(bào),2009,26(1):81–85.

19 姜立強(qiáng),郭錚,劉光斌.儀表、自動(dòng)化與先進(jìn)集成技術(shù)大會(huì), 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

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

2016-03-30;收到修改稿時(shí)間:2016-06-21

10.15888/j.cnki.csa.005537