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

王 鈦,許 斌,李林國,亓 晉

(1.南京郵電大學 自動化學院，江蘇 南京 2100032.南京郵電大學，江蘇 南京 210003)

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

王 鈦1,許 斌2,李林國2,亓 晉2

(1.南京郵電大學 自動化學院，江蘇 南京 2100032.南京郵電大學，江蘇 南京 210003)

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

圖像分割；優化算法；離散灰狼算法；Kapur熵

1 概 述

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

圖像分割技術的研究已經涉及眾多領域，它的深入研究和最終解決，能夠極大地推動眾多學科的發展與成熟。近年來，國內外都對其進行了大量的研究，新的分割技術和方法層出不窮。但是，依然沒有具有普遍適用性的分割理論。圖像分割算法有很多種，經典算法有基于閾值的分割算法、基于邊緣的分割算法、基于區域的分割算法以及與其他特定理論結合的圖像分割算法。而閾值分割法是圖像分割中最常用的方法，通過選取適當的分割閾值，把圖像中的目標與非目標分割開，為后續工作提供依據。

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

文中運用DGWO來確定最優閾值，進而達到成功分割圖像的目的。該算法應用到圖像分割上能夠迅速選取合適的閾值使得分割效果更好，提高了分割效率和分割精度，從而有利于后續工作的高效進行。實驗結果表明了DGWO的優越性能。

2 相關工作

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

文中采用DGWO進行圖像分割，解決閾值選擇的問題，把Kapur熵函數作為適應度函數進行優化，使得分割效果更好，效率更高，閾值的范圍較穩定。

3 問題描述

3.1 熵標準法圖像分割

熵標準法是Kapur提出的非參數閾值尋優方法[14]。它是一種依據灰度直方圖概率分布的基于熵閾值轉換法的有效分割技術。當分離類的最佳閾值被正確分配時，熵是最大的。圖像的熵測量類之間的緊湊性和分離性。該方法的目的就是尋找最優閾值產生最大熵。

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

(1)

對于多個類(多級)的定義如下：

?

(2)

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

?

(3)

基于Kapur熵的多個閾值方法，有必要用閾值的相似數將圖像分成k類。因此，目標函數為：

(4)

每個熵分別與其對應的閾值進行計算，公式如下：

?

(5)

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

(6)

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

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

(7)

3.2 DGWO數學模型

3.2.1 社會等級

灰狼算法依據社會等級，把認為最適當的解作為α，第二、第三適當解作為β、δ，其余的候選解假設為ω。DGWO算法的狩獵(優化)是在α、β、δ的指導下進行的，即ω跟隨它們。

3.2.2 包 圍

捕獵過程中的包圍是依據下列公式進行的：

(8)

(9)

(10)

(11)

3.2.3 捕 獵

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

(12)

(14)

3.2.4 攻 擊

3.2.5 算法過程

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

初始化e、A和C

計算每個搜索代理的適應度值

While(t<最大迭代次數)

for所有的搜索代理

依據式(14)更新當前搜索代理的位置

endfor

更新e、A和C

計算所有搜索代理的適應度值

更新Xα,Xβ,Xδ

t=t+1

endwhile

returnXα

4 基于DGWO的圖像分割

DGWO算法應用于圖像分割主要是對Kapur熵函數進行優化，以期取得最優閾值來分割圖像。因此，把Kapur熵函數作為算法的適應度函數。

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

Step2：獲得圖像的直方圖。灰度圖像的為hgr，RGB圖像的為hR,hG,hB。

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

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

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

Step6：把Kapur熵函數作為適應度函數，計算出每個搜索代理的適應度值。

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

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

Step10：把擁有最優目標函數值的狼的位置作為最優分割閾值。

Step11：輸出最優分割閾值、分割前后的圖像。

5 實 驗

5.1 參數設置

文中將會用8張標準圖像對DGWO算法進行測試。這些圖像都是采用灰色圖像以及同樣的格式(JPGE)。

為了對算法進行分析，把DGWO與GA和PSO進行對比。為了避免結果的隨機性，采用適當的統計度量來比較這些算法的效能。因此，所有算法對每張圖執行35次，依據文獻[8]測試閾值th=2,3,4,5。每個實驗的停止準則都為150次迭代，NP=50。為了驗證穩定性，在每次測試結束時根據式(15)計算標準差(STD)。

(15)

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

(16)

(17)

5.2 結 果

把Kapur熵函數作為目標函數來分析DGWO的性能。表1給出了DGWO對整組基準圖像的實驗結果。列出PSNR、STD、閾值個數k、最優閾值Thresholds和目標函數均值MEAN。

5.3 比 較

比較DGWO與GA和PSO的分割結果，如表2所示。所有方法都要對每張圖像運行35次；每張圖像都分別計算PSNR、STD和目標函數的平均值，而且目標函數都為Kapur熵函數。

表1 DGWO對整組基準圖像的實驗結果

續表1

表2 DGWO、GA和PSO的圖像分割結果對比

續表2

6 結束語

文中提出一種基于DGWO的多級閾值圖像分割方法。將DGWO算法應用到多閾值圖像分割領域，從而實現圖像的多閾值分割。實驗結果表明，基于DGWO的圖像分割方法不僅能夠獲得更好的圖像分割質量，而且在運行時間和收斂性方面相較GA和PSO方法具有明顯優勢。

[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].計算機應用研究,2009,26(11):4364-4367.

[5] 孫越泓.基于粒子群優化算法的圖像分割研究[D].南京:南京理工大學,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] 張小峰.基于模糊聚類算法的醫學圖像分割技術研究[D].濟南:山東大學,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

時間：2016-06-22

國家自然科學基金資助項目(61401225);南京郵電大學引進人才科研啟動基金(NY213047,NY214102，NY213050,NY214098)

王 鈦(1986-)，男，碩士研究生，研究方向為智能系統應用;許 斌，博士，講師，研究方向為智能計算、云制造服務組合。

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