王 鈦,許 斌,李林國(guó),亓 晉

(1.南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 2100032.南京郵電大學(xué)，江蘇 南京 210003)

基于離散灰狼算法的多級(jí)閾值圖像分割

王 鈦1,許 斌2,李林國(guó)2,亓 晉2

(1.南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 2100032.南京郵電大學(xué)，江蘇 南京 210003)

閾值分割方法的關(guān)鍵在于閾值選取。閾值決定了圖像分割結(jié)果的好與壞，隨著閾值數(shù)量的增加，圖像分割的計(jì)算過程越來越復(fù)雜。為了選取適當(dāng)?shù)拈撝颠M(jìn)行圖像分割，文中提出了離散灰狼算法(Discrete Grey Wolf Optimizer,DGWO)，即經(jīng)過離散化處理的灰狼算法，并用該算法求解以Kapur分割函數(shù)為目標(biāo)函數(shù)的全局優(yōu)化問題。DGWO算法具有很好的全局收斂性與計(jì)算魯棒性，能夠避免陷入局部最優(yōu)，尤其適合高維、多峰的復(fù)雜函數(shù)問題的求解，并且可以很好地融合到圖像分割過程當(dāng)中。大量的理論分析和仿真實(shí)驗(yàn)的結(jié)果表明，與遺傳算法(GA)、粒子群算法(PSO)的圖像分割結(jié)果相比，在選取多張分割圖像、多個(gè)分割閾值的情況下，該算法具有更好的分割效果，更高的分割效率，優(yōu)化得到的閾值范圍更加穩(wěn)定，分割質(zhì)量更高。

圖像分割；優(yōu)化算法；離散灰狼算法；Kapur熵

1 概 述

圖像是人類接收、處理和傳遞信息的一種重要途徑。由于圖像信息有著直觀、易懂、形象以及信息量龐大的優(yōu)點(diǎn)，它也是人們生活與生產(chǎn)過程中最不可或缺和最高效的信息獲取與交流的方式之一。圖像分割是目前為止幫助人們獲取有用信息最有效的方法。圖像分割是指將要處理的目標(biāo)圖像劃分成若干個(gè)特定的具有獨(dú)特性質(zhì)的區(qū)域并且提取出有用的或者感興趣的目標(biāo)的技術(shù)與過程。

圖像分割技術(shù)的研究已經(jīng)涉及眾多領(lǐng)域，它的深入研究和最終解決，能夠極大地推動(dòng)眾多學(xué)科的發(fā)展與成熟。近年來，國(guó)內(nèi)外都對(duì)其進(jìn)行了大量的研究，新的分割技術(shù)和方法層出不窮。但是，依然沒有具有普遍適用性的分割理論。圖像分割算法有很多種，經(jīng)典算法有基于閾值的分割算法、基于邊緣的分割算法、基于區(qū)域的分割算法以及與其他特定理論結(jié)合的圖像分割算法。而閾值分割法是圖像分割中最常用的方法，通過選取適當(dāng)?shù)姆指铋撝?，把圖像中的目標(biāo)與非目標(biāo)分割開，為后續(xù)工作提供依據(jù)。

Seyedali等[1]模仿自然界中灰狼的領(lǐng)導(dǎo)等級(jí)制度和狩獵行為在2014年提出了一種新型算法——離散灰狼算法(DGWO)。根據(jù)灰狼群的等級(jí)制度將狼群分成α,β,δ,ω四個(gè)等級(jí)。其中，α是領(lǐng)導(dǎo)狼(首領(lǐng))，等級(jí)依次降低，ω等級(jí)最低。此外，狩獵行為有三個(gè)主要步驟：搜尋、包圍和攻擊。與其他經(jīng)典的智能算法如PSO、ABC、GA等相比，DGWO算法有較好的優(yōu)化效果和收斂性，擁有強(qiáng)大的探索和開發(fā)能力，能夠有效避免陷入局部最優(yōu)，而且在解決未知空間和具有挑戰(zhàn)的問題中也有良好效果，對(duì)于約束問題和非約束問題同樣具有高度績(jī)效，尤其適用于解決實(shí)際問題。Nipotepat等[2]提出了一種改進(jìn)的灰狼算法(IGWO)，應(yīng)用了參數(shù)選擇策略使搜索能力加強(qiáng)，采用雜交策略增加了代理的多樣性。

文中運(yùn)用DGWO來確定最優(yōu)閾值，進(jìn)而達(dá)到成功分割圖像的目的。該算法應(yīng)用到圖像分割上能夠迅速選取合適的閾值使得分割效果更好，提高了分割效率和分割精度，從而有利于后續(xù)工作的高效進(jìn)行。實(shí)驗(yàn)結(jié)果表明了DGWO的優(yōu)越性能。

2 相關(guān)工作

圖像分割發(fā)展至今，已經(jīng)有很多學(xué)者研究出了多種多樣的實(shí)現(xiàn)方法，而由于圖像的種類繁多，圖像數(shù)據(jù)通常還有著許多不確定性，所以迄今為止也還不存在某一種通用的圖像分割算法可以準(zhǔn)確地依照人們的理解來分割任一幅圖像。一些算法能直接分割一般圖像，而有一些卻只能分割一些特定的圖像。到目前為止，已經(jīng)有很多經(jīng)典優(yōu)化算法被運(yùn)用到圖像分割中，主要用于解決閾值的選擇問題，并且也獲得了較為理想的效果。遺傳算法(GA)[3]就被多次應(yīng)用到分割工作中。李康順等[4]提出一種改進(jìn)遺傳算法(IGA)的圖像分割方法。該方法能夠根據(jù)個(gè)體適應(yīng)度大小和種群分散程度自適應(yīng)調(diào)整遺傳控制參數(shù)，保持了種群的多樣性，也提高了收斂速度。受到群體行為啟發(fā)的進(jìn)化算法如粒子群算法(PSO)[5]和人工蜂群算法(ABC)[6]，也是廣泛采用到圖像分割問題中的經(jīng)典優(yōu)化算法。這兩種算法是將Kapur熵函數(shù)作為適應(yīng)度函數(shù)尋找最優(yōu)的閾值進(jìn)行分割的。張小峰[7]將模糊聚類算法(FCA)應(yīng)用到醫(yī)學(xué)圖像分割中。該算法是一種典型的“軟分割”方法,它允許像素以相異的隸屬度同時(shí)隸屬于相異的組織與器官，能夠有效解決醫(yī)學(xué)圖像中的部分容積效應(yīng)現(xiàn)象問題，能夠從原始圖像中盡可能多地保留信息，因此可以獲得較好的分割效果。Diego等[8]將EMO算法和HSA算法[9]用于多級(jí)閾值轉(zhuǎn)換優(yōu)化分割問題中。當(dāng)然還有許多優(yōu)化算法也被研究者們應(yīng)用到這類問題當(dāng)中，并且也取得了較為滿意的效果，如DE、CS、FA、HBM、BF等[10-13]。

文中采用DGWO進(jìn)行圖像分割，解決閾值選擇的問題，把Kapur熵函數(shù)作為適應(yīng)度函數(shù)進(jìn)行優(yōu)化，使得分割效果更好，效率更高，閾值的范圍較穩(wěn)定。

3 問題描述

3.1 熵標(biāo)準(zhǔn)法圖像分割

熵標(biāo)準(zhǔn)法是Kapur提出的非參數(shù)閾值尋優(yōu)方法[14]。它是一種依據(jù)灰度直方圖概率分布的基于熵閾值轉(zhuǎn)換法的有效分割技術(shù)。當(dāng)分離類的最佳閾值被正確分配時(shí)，熵是最大的。圖像的熵測(cè)量類之間的緊湊性和分離性。該方法的目的就是尋找最優(yōu)閾值產(chǎn)生最大熵。

從灰度圖像或一個(gè)RGB(紅色、綠色、藍(lán)色)圖像各分量中取亮度水平L，亮度值的概率分布計(jì)算如下：

(1)

對(duì)于多個(gè)類(多級(jí))的定義如下：

?

(2)

其中，ω0(th),ω1(th),…,ωk-1(th)分別是C1,C2,…,Ck的概率分布，由式(3)計(jì)算：

?

(3)

基于Kapur熵的多個(gè)閾值方法，有必要用閾值的相似數(shù)將圖像分成k類。因此，目標(biāo)函數(shù)為：

(4)

每個(gè)熵分別與其對(duì)應(yīng)的閾值進(jìn)行計(jì)算，公式如下：

?

(5)

最后，需要使用式(6)將像素分隔在各自的類中。閾值轉(zhuǎn)換是一個(gè)把圖像的像素依據(jù)灰度級(jí)(L)分成集或類的過程。這種分類必須選擇一個(gè)閾值(th)或者遵循下面多級(jí)閾值轉(zhuǎn)換公式準(zhǔn)則：

(6)

其中，p為灰度圖像Ig中m×n個(gè)像素點(diǎn)中的一個(gè)，它代表著在L灰度級(jí)中的等級(jí)，L={0,1,…,L-1}；Ci為像素點(diǎn)p所屬的類；{th1,th2,…,thk}為不同的閾值。

多級(jí)或多閾值轉(zhuǎn)換的問題都是選擇正確識(shí)別類的閾值th。Kapur熵法是眾所周知的用來確定這些閾值的方法。該方法提出的目標(biāo)函數(shù)必須是最大化的，以便找到最佳閾值。文中使用式(7)來獲得k維最優(yōu)閾值和最大化Kapur’s目標(biāo)函數(shù)。

(7)

3.2 DGWO數(shù)學(xué)模型

3.2.1 社會(huì)等級(jí)

灰狼算法依據(jù)社會(huì)等級(jí)，把認(rèn)為最適當(dāng)?shù)慕庾鳛棣?，第二、第三適當(dāng)解作為β、δ，其余的候選解假設(shè)為ω。DGWO算法的狩獵(優(yōu)化)是在α、β、δ的指導(dǎo)下進(jìn)行的，即ω跟隨它們。

3.2.2 包 圍

捕獵過程中的包圍是依據(jù)下列公式進(jìn)行的：

(8)

(9)

(10)

(11)

3.2.3 捕 獵

捕獵行為通常是在α的領(lǐng)導(dǎo)下，β、δ不定時(shí)參加。在抽象空間中很難確定最優(yōu)解的位置。為了精確模擬灰狼的捕獵行為，把獵物的潛在位置信息知識(shí)交給α、β、δ。因此，保存目前為止獲得前三個(gè)最優(yōu)解，并迫使其他的搜索代理(含ω)根據(jù)最好搜索代理的位置來更新自己的位置。公式如下：

(12)

(14)

3.2.4 攻 擊

3.2.5 算法過程

初始化灰狼群的位置Xi(i=1,2,…,m)

初始化e、A和C

計(jì)算每個(gè)搜索代理的適應(yīng)度值

While(t<最大迭代次數(shù))

for所有的搜索代理

依據(jù)式(14)更新當(dāng)前搜索代理的位置

endfor

更新e、A和C

計(jì)算所有搜索代理的適應(yīng)度值

更新Xα,Xβ,Xδ

t=t+1

endwhile

returnXα

4 基于DGWO的圖像分割

DGWO算法應(yīng)用于圖像分割主要是對(duì)Kapur熵函數(shù)進(jìn)行優(yōu)化，以期取得最優(yōu)閾值來分割圖像。因此，把Kapur熵函數(shù)作為算法的適應(yīng)度函數(shù)。

Step1：讀取圖像J進(jìn)行判斷，如果是RGB圖像就分離成JR,JG,JB三個(gè)通道；如果是灰度圖像就存儲(chǔ)到Jgr。a=1,2,3是RGB圖像，a=1是灰度圖像。

Step2：獲得圖像的直方圖?；叶葓D像的為hgr，RGB圖像的為hR,hG,hB。

Step3：根據(jù)式(3)計(jì)算出各灰度值的概率分布和直方圖。

Step4：初始化DGWO的種群數(shù)NP和參數(shù)e、A、C和最大迭代次數(shù)Max_iter。

Step5：初始化灰狼種群位置Xi(i=1,2,…,NP)。

Step6：把Kapur熵函數(shù)作為適應(yīng)度函數(shù)，計(jì)算出每個(gè)搜索代理的適應(yīng)度值。

Step7：根據(jù)適應(yīng)度值的大小，把最好搜索代理的位置賦給α狼，把第二好搜索代理的位置賦給β狼，把第三好搜索代理的位置賦給δ狼。

Step9：循環(huán)指針q增加1；如果q≥Max_iter或者滿足算法停止條件，完成迭代過程，跳至第十步；否則跳至第六步。

Step10：把擁有最優(yōu)目標(biāo)函數(shù)值的狼的位置作為最優(yōu)分割閾值。

Step11：輸出最優(yōu)分割閾值、分割前后的圖像。

5 實(shí) 驗(yàn)

5.1 參數(shù)設(shè)置

文中將會(huì)用8張標(biāo)準(zhǔn)圖像對(duì)DGWO算法進(jìn)行測(cè)試。這些圖像都是采用灰色圖像以及同樣的格式(JPGE)。

為了對(duì)算法進(jìn)行分析，把DGWO與GA和PSO進(jìn)行對(duì)比。為了避免結(jié)果的隨機(jī)性，采用適當(dāng)?shù)慕y(tǒng)計(jì)度量來比較這些算法的效能。因此，所有算法對(duì)每張圖執(zhí)行35次，依據(jù)文獻(xiàn)[8]測(cè)試閾值th=2,3,4,5。每個(gè)實(shí)驗(yàn)的停止準(zhǔn)則都為150次迭代，NP=50。為了驗(yàn)證穩(wěn)定性，在每次測(cè)試結(jié)束時(shí)根據(jù)式(15)計(jì)算標(biāo)準(zhǔn)差(STD)。

(15)

另外，峰值信噪比(PSNR)依據(jù)每個(gè)像素的均方差(MSE)來比較圖像(圖像分割)與基準(zhǔn)圖像(原圖像)的相似性。

(16)

(17)

5.2 結(jié) 果

把Kapur熵函數(shù)作為目標(biāo)函數(shù)來分析DGWO的性能。表1給出了DGWO對(duì)整組基準(zhǔn)圖像的實(shí)驗(yàn)結(jié)果。列出PSNR、STD、閾值個(gè)數(shù)k、最優(yōu)閾值Thresholds和目標(biāo)函數(shù)均值MEAN。

5.3 比 較

比較DGWO與GA和PSO的分割結(jié)果，如表2所示。所有方法都要對(duì)每張圖像運(yùn)行35次；每張圖像都分別計(jì)算PSNR、STD和目標(biāo)函數(shù)的平均值，而且目標(biāo)函數(shù)都為Kapur熵函數(shù)。

表1 DGWO對(duì)整組基準(zhǔn)圖像的實(shí)驗(yàn)結(jié)果

續(xù)表1

表2 DGWO、GA和PSO的圖像分割結(jié)果對(duì)比

續(xù)表2

6 結(jié)束語

文中提出一種基于DGWO的多級(jí)閾值圖像分割方法。將DGWO算法應(yīng)用到多閾值圖像分割領(lǐng)域，從而實(shí)現(xiàn)圖像的多閾值分割。實(shí)驗(yàn)結(jié)果表明，基于DGWO的圖像分割方法不僅能夠獲得更好的圖像分割質(zhì)量，而且在運(yùn)行時(shí)間和收斂性方面相較GA和PSO方法具有明顯優(yōu)勢(shì)。

[1] Mirjalili S,Mirjalili S M,Lewis A.Grey wolf optimizer[J].Advances in Engineering Software,2014,69:46-61.

[2] Muangkote N,Sunat K,Chiewchanwattana S.An improved grey wolf optimizer for training q-Gaussian radial basis functional-link nets[C]//Proc of computer science and engineering conference.[s.l.]:[s.n.],2014:209-214.

[3] Pal S K,Bhandari D,Kundu M K.Genetic algorithms for optimal image enhancement[J].Pattern Recognition Letters,1994,15(3):261-271.

[4] 李康順,李茂民,張文生.一種基于改進(jìn)遺傳算法的圖像分割方法[J].計(jì)算機(jī)應(yīng)用研究,2009,26(11):4364-4367.

[5] 孫越泓.基于粒子群優(yōu)化算法的圖像分割研究[D].南京:南京理工大學(xué),2010.

[6] Karaboga D,Gorkemli B.A quick artificial bee colony -qABC- algorithm for optimization problems[C]//Proc of international symposium on innovations in intelligent systems and applications.[s.l.]:[s.n.],2012:1-5.

[7] 張小峰.基于模糊聚類算法的醫(yī)學(xué)圖像分割技術(shù)研究[D].濟(jì)南:山東大學(xué),2014.

[8] Oliva D,Cuevas E,Pajares G,et al.A multilevel thresholding algorithm using electromagnetism optimization[J].Neurocomputing,2014,139:357-381.

[9] Oliva D,Cuevas E,Pajares G,et al.Multilevel thresholding segmentation based on harmony search optimization[J].Journal of Applied Mathematics,2013,2013:575414.

[10] Sathya P,Kayalvizhi R.Optimal multilevel thresholding using bacterial foraging algorithm[J].Expert Systems with Applications,2011,38(12):15549-15564.

[11] Sarkar S,Patra G R,Das S.A differential evolution based approach for multilevel image segmentation using minimum cross entropy thresholding[M]//Swarm,evolutionary,and memetic computing.Berlin:Springer,2011:51-58.

[12] Horng M H, Liou R J. Multilevel minimum cross entropy threshold selection based on the firefly algorithm[J].Expert Systems with Applications,2011,38(12):14805-14811.

[13] Agrawal S,Panda R,Bhuyan S,et al.Tsallis entropy based optimal multilevel thresholding using cuckoo search algorithm[J].Swarm and Evolutionary Computation,2013,11(1):16-30.

[14] Kapur J N,Sahoo P K,Wong A K.A new method for gray-level picture thresholding using the entropy of the histogram[J].Computer Vision,Graphics,and Image Processing,1985,29(3):273-285.

A Multi-threshold Image Segmentation Algorithm Based on Discrete Grey Wolf Optimization

WANG Tai1，XU Bin2，LI Lin-guo2，QI Jin2

(1.College of Automation,Nanjing University of Posts and Telecommunications,Nanjing 210003,China; 2.Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

The key of threshold segmentation is to select the thresholds which can determine the result of segmentation.With the increasing amounts of thresholds,the computation complexity gets higher.In this paper,a Discrete Grey Wolf Optimization (DGWO) is proposed to select the appropriate thresholds for image segmentation and apply it to the global optimization problem of objective function of Kapur segmentation function.The DGWO can be well blended into image segmentation.It specially suits for solving complex function with high-dimension and multi-peak for its excellent performance in global convergence,robustness and ability to avoid trapping into local optimization.Extensive theoretical analysis and the results of simulation have shown that DGWO has better effectiveness,efficiency,stability of the range of thresholds and quality in multi-images and multi-thresholds segmentation compared with GA and PSO.

image segmentation;optimization algorithm;Discrete Grey Wolf algorithm (DGWO);Kapur entropy

2015-10-23

2016-01-27

時(shí)間：2016-06-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(61401225);南京郵電大學(xué)引進(jìn)人才科研啟動(dòng)基金(NY213047,NY214102，NY213050,NY214098)

王 鈦(1986-)，男，碩士研究生，研究方向?yàn)橹悄芟到y(tǒng)應(yīng)用;許 斌，博士，講師，研究方向?yàn)橹悄苡?jì)算、云制造服務(wù)組合。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0844.022.html

TP301.6

A

1673-629X(2016)07-0030-06

10.3969/j.issn.1673-629X.2016.07.007