回溯搜索優化算法輔助的多閾值圖像分割

尹雨山，王李進,2，尹義龍,3，王冰清，趙文婷，徐云龍

（ 1. 山東大學 計算機科學與技術學院，山東 濟南 250101； 2.福建農林大學 計算機與信息學院，福建 福州 350002； 3.山東財經大學 計算機科學與技術學院，山東 濟南 250014）

?

回溯搜索優化算法輔助的多閾值圖像分割

尹雨山1，王李進1,2，尹義龍1,3，王冰清1，趙文婷1，徐云龍1

（ 1. 山東大學 計算機科學與技術學院，山東 濟南 250101； 2.福建農林大學 計算機與信息學院，福建 福州 350002； 3.山東財經大學 計算機科學與技術學院，山東 濟南 250014）

閾值法是一種簡單且有效的圖像分割技術。然而閾值求解的計算量隨閾值的增加而呈指數級別增長，這給多閾值圖像分割帶來巨大挑戰。為了克服計算量過大問題，視多閾值分割模型為優化問題，分別將Otsu法和Kapur法作為目標函數，采用回溯搜索優化算法求解目標函數，實現多閾值圖像分割。將提出的多閾值分割算法應用于自然圖像分割，并與其他算法比較，實驗結果說明基于回溯搜索優化算法的多閾值圖像分割技術是可行的，而且具有較好的分割效果。

閾值法；回溯搜索優化算法；圖像分割；Otsu；Kapur；PSNR

圖像分割就是指把圖像分成各具特性的區域并提取感興趣目標的過程，是圖像處理到圖像分析的關鍵步驟[1]，也是計算機視覺的一個基本問題[2]。圖像分割多年來一直得到人們的高度重視，至今已提出了各種各樣的分割算法，如基于閾值的分割方法[3-7]、基于邊緣檢測的分割方法[8-9]、基于區域的分割方法[10-12]、基于圖論的分割方法[13-14]、基于能量泛函的分割方法[15-16]以及基于機器學習的分割方法[17-20]等。

基于閾值的分割方法是各類分割算法中簡單且廣泛采用的方法，其基本思想是用一個或者多個閾值將待分割的圖像的灰度級分為多個部分，灰度值在同一類中的像素屬于同一個目標[2]。因此，閾值的選取非常關鍵，并決定分割的結果。常見的計算閾值的方法主要有最大類間方差法（Otsu算法）[3]、最大熵法[4-5]以及最小誤差法[7]等。上述計算閾值方法基本是在滿足一定準則下通過解析式求得閾值，例如Otsu算法以目標和背景的類間方差最大或類內方差最小為準則選取閾值。然而，通過解析式求解閾值的計算量和計算復雜度會隨著閾值的增加而呈指數增長。因此，一些學者將基于準則函數的閾值求解問題視為以準則函數為目標函數的優化問題，于是出現了一些基于遺傳算法[21]、粒子群優化算法[22]以及差分算法[23]等的多閾值方法。得益于經典進化算法能有效求解多閾值問題，一些新穎的仿生算法用于該類問題，并呈現出較好的分割效果[24-27]。

回溯搜索優化算法（backtracking search optimization algorithm, BSA）是一種新興的仿生算法，其具有簡單的結構，并能有效且快速求解各類函數優化問題[28]。然而，關于BSA算法的應用研究報道較少，特別是在圖像處理及應用領域。因此，借鑒于仿生算法求解多閾值問題的有效性，本文將BSA算法應用于圖像分割，提出基于BSA算法的多閾值圖像分割。提出的方法將Otsu算法和最大熵法的準則函數視為目標函數，并采用BSA算法分別獲取多閾值，實現圖像分割。實驗說明提出的方法具有更好的性能。

1 閾值法

1.1 最大類間方差法（Otsu法）

最大類間方差法給予判別分析最小二乘法的原理，其根據圖像的灰度特性，將圖像分為不同類別，各類之間方差要求最大。假設存在m級灰度的圖像P，閾值q將圖像的灰度值范圍[0,1,…,m-1]分為背景與目標2部分。又設pi表示灰度值為i出現的概率，則目標部分和背景的概率分別表示為

（1）

（2）

設λ、λ1、λ2分別表示圖像、目標和背景的灰度值均值，則可表示為

（3）

（4）

且滿足λ=w1λ1+w2λ2和w1+w2=1。

類間方差可表示為

d（q）=w1（λ1-λ）2+w2（λ2-λ）2

（5）

根據類間最大化準則，當方差取得最大值時,便得到最佳閾值q。

假設圖像P存在a個閾值（q1,q2,…,qa），式（5）容易擴展多閾值類間方差，可表示為

d（q1,…,qa）=w1（λ1-λ）2+…+wa（λa-λ）2

（6）

根據類間最大化準則，可通過計算式（7）獲得最佳閾值：

（q1,q2,…,qa）=argmax（d（q1,q2,…,qa））

1.2 最大熵法（Kapur法）

20世紀80年代以來，Shannon信息熵的概念被應用于圖像閾值化處理中，其思想是利用圖像的灰度分布密度函數定義圖像的信息熵，并根據優化準則求得閾值。文獻[4]通過使后驗的上限最大化準則確定閾值，而文獻[5]假定目標和背景服從2個不同的概率分布，使得信息熵最大化求得最佳閾值。

假設存在m級灰度的圖像P，閾值q將圖像的灰度值范圍[0,1,…,m-1]分為背景與目標2部分。又設pi表示灰度值為i出現的概率，則目標和背景表示為式（1）和式（2），而它們的信息熵則可表示為

（8）

（9）

Kapur方法[5]是在圖像P的總信息熵最大時，獲得最佳閾值，即

q=argmax（H1+H2）

（10）

同樣，式（10）很容易擴展為多閾值最大熵，可表示為

（q1,q2,…,qa）=argmax（H1+H2+…+Ha）

（11）

式中：a表示閾值數目。

2 回溯搜索優化算法

BSA算法是一種新興的隨機優化搜索技術，其結構簡單，并且能夠有效求解各類優化問題。另外，BSA算法也是基于種群的搜索技術，并且使用一個外部文檔維護其歷史種群信息以引導種群進化。

當BSA算法用于求解優化問題時，首先在解搜索空間[xj,min,xj,max] （j=1,2,…,D）內，通過均勻采樣初始化候選解X和歷史種群Xold：

xi,j,0=xi,j,min+r（xi,j,max-xi,j,min）i=1,2,…,NP

（12）

式中：r∈[0,1]是隨機數，NP是種群大小。

與其他進化算法類似，BSA算法使用3個基本的遺傳操作：變異、交叉和選擇。

BSA算法采用隨機變異策略為每個個體生成中間候選個體Vm。該策略能夠有效利用歷史種群的信息引導算法進化，具體公式為

Vm=X+F（Xold-X）

（13）

式中：F縮放系數用以控制搜索方向矩陣。其次，BSA算法在變異個體Vm和當前種群X的基礎上采用非均勻且較復雜的交叉策略生成候選解T。該策略通過隨機方式生成一個映射矩陣map（NP×D），并根據該矩陣將Vm和X中的信息映射成T。根據文獻[28]，交叉策略可概括如算法1所示。

算法1交叉策略

輸入變異個體Vm、種群X、種群規模NP、問題維數D、以及混合率mixrate。

輸出候選解T

1）初始化矩陣map（1:NP,1:D）=1；

2）均勻產生2個[0,1]之間的隨機數a和b；

3）ifa>b，轉入4），否則轉入5）；

4）進行如下操作后轉入第6步：

fori=1 to NP

隨機生成系列u=permuting（1:D）；

均勻生成1個[0,1]的隨機數c；

處理map（i,1:u（1：mixrate×c×D））=0;

end for

5）進行如下操作：

fori=1 to NP

均勻生成1個[0,D]的隨機整數d；

處理map（i, d）=0;

end for

6）T=Vm;

7）進行如下操作：

fori=1 to NP

forj=1 to D

if map（i, j）=1 thenT（i, j）= P（i, j）;

end for

end for

另外，BSA算法采用2種選擇操作。第一種選擇操作用于更新歷史種群的信息，其完全隨機下接收當前種群信息，可概括為

if a>bXold=X | a,b ～U（0,1）

（14）

第2種選擇操作則根據當前種群X和候選種群T

的適應值，貪婪選擇適應值較好的個體進入下一代。

3 應用BSA求解多閾值

應用BSA算法求解多閾值問題，其實質是將多閾值準則作為目標函數，采用BSA算法搜索最優閾值，具體步驟如算法2所示。

算法2基于BSA算法的多閾值圖像分割

輸入種群規模NP、問題維數D（閾值數目）、混合率mixrate、最大迭代次數MaxIteration。

輸出最佳閾值q

1）采用式（12）初始化種群X和歷史種群Xold；

2）初始化迭代計數器iter=1；

3）if iter>MaxIteration，轉入11）;

4）執行第1種選擇操作，即執行式（14）更新歷史種群；

5）執行變異操作，即執行式（13）；

6）執行交叉操作獲得T，即執行算法1；

7）采用式（7）或者式（11）評價T；

8）根據X和T的適應值，采用第2種選擇操作獲得下一代種群X。

9）獲得當前最優閾值q；

10）iter=iter+1，轉入3）；

11）輸出最優閾值q。

4 實驗與結果

為了分析BSA算法的多閾值圖像分割性能，本文采用文獻[25]中的Camera、Lena、Pepper以及Baboon等4幅圖像作為待分割圖像見圖1，其中，每幅圖像的大小為256×256。

另外，圖像峰值信噪比（peak signal to nose ratio, PSNR）作為性能指標，其中PSNR公式[24]如下：

（15）

式中：

（16）

式中：圖像I大小為M×N，J為閾值化后的圖像。

在實驗中，各算法針對每幅圖像獨立運行30次。每次獨立運行中，最大迭代數MaxIteration為160，種群大小NP為20。

4.1 Otsu方法的實驗結果

表1給出了與基于傳統優化算法的多閾值Otsu（MOT）[29]比較的實驗結果。MOT中的適應值是將MOT中的閾值帶入式（7）求得。表2列出與基于細菌算法（bacterial foraging algorithm, BFA）的Otsu多閾值[25]和帶慣性權重PSO算法[30]的Otsu多閾值的實驗結果。其中，PSO算法的最大和最小慣性權重分別為0.9和0.4；BFA算的參數見文獻[25]。另外，圖2給出各算法求解的PSNR隨Otsu閾值數的變化趨勢。

表1 MOT和BSA算法的Otsu多閾值目標函數適應值和PSNRTable 1 Multi-threshold Otsu fitness and PSNR obtained by MOT and BSA

圖2 PSNR隨Otsu閾值變化的趨

從表1可知，采用BSA算法求解的閾值使得適應值都優于MOT的所得適應值；另外借助于PSNR，BSA算法也優于MOT。上述結果說明了BSA算法以Otsu的最大類間準則為目標函數求解多閾值是可行的，而且獲得較好的性能。

從表2可以看出，與BFA算法比較，BSA算法求解的多閾值在目標函數適應值以及PSNR上都明顯較優。另外，與PSO算法比較，在各測試圖像的2和3個閾值上，BSA算法求解的多閾值與PSO算法求解的多閾值是相同的，然而在4和5個閾值上，PSO算法獲得稍微較好的目標函數適應值，但是BSA算法卻獲得較好的PSNR?？傮w而言，BSA算法的多閾值與帶慣性權重PSO算法的多閾值性能是相同的。圖2同樣說明了隨閾值數的增加，BSA算法求解的PSNR趨勢總體上是最好的。

表2 BFA算法、PSO算法和BSA算法求解的Otsu多閾值目標函數適應值和PSNRTable 2 Multi-threshold Otsu fitness and PSNR obtained by BFA, PSO and BSA

表3 BFA算法、PSO算法和BSA算法求解的Kapur多閾值目標函數適應值和PSNRTable 3 Multi-threshold Kapur fitness and PSNR obtained by BFA, PSO and BSA

4.2 Kapur方法的實驗結果

表3給出了不同仿生算法求解Kapur多閾值的比較結果，其中參數與4.1節相同。

從表3可以看出，BSA算法求解的目標函數適應值上完全優于BFA算法求解的目標函數適應值，而且借助于PSNR性能，BSA算法也優于BFA算法。另外與PSO算法比較，BSA算法求解的目標函數適應值基本上相似，但借助于PSNR，BSA算法的多閾值法總體上優于PSO算法的多閾值法。

圖3給出各仿生算法求解的PSNR隨Kapur閾值數的變化趨勢。從圖3可以看出，在多數的圖像上，BSA求解的PSNR隨Kapur閾值數的變化趨勢優于其他2種算法。

圖3 PSNR隨Kapur閾值變化的趨勢

5 結束語

本文將BSA算法應用于圖像分割，提出BSA算法求解的多閾值圖像分割。提出方法將Otsu方法和Kapur方法的求多閾值準則函數作為目標函數，應用BSA算法求解，并實現圖像分割。仿真結果說明BSA算法求解的多閾值圖像分割是可行的，與其他的BFA算法和PSO算法求解的多閾值分割方法比較，本文提出的方法具有較好的性能。下一步工作將提出方法應用于更多的圖像測試，包括遙感圖像以及醫學影像等。

[1]章毓晉. 圖像工程 [M]. 北京:清華大學出版社, 2002:179-186.

[2]劉國英, 馬國銳, 王雷光, 等. 基于Markov隨機場的小波域圖像建模及分割—Matlab環境[M]. 北京:科學出版社, 2010: 6-15.

[3]OTSU N. A threshold selection method from gray-level histograms[J]. Automatica, 1975, 11： 23-27.

[4]PUN T. A new method for grey-level picture thresholding using the entropy of the histogram[J]. Signal Processing, 1980, 2（3）: 223-237.

[5]KAPUR J N, SAHOO P K, WONG A K C. 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.

[6]REDDI S S, RUDIN S F, KESHAVAN H R. An optimal multiple threshold scheme for image segmentation[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1984, 14（4）: 661-665.

[7]KITTLER J, ILLINGWORTH J. Minimum error thresholding[J]. Pattern Recognition, 1986, 19（1）: 41-47.

[8]CANNY J. A computational approach to edge detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, PAMI-8（6）: 679-698.

[9]ZIOU D, TABBONE S. Edge detection techniques: an overview[J]. International Journal of Pattern Recognition and Image Analysis, 1998, 8（4）: 537-559.

[10]CHEN P C, PAVLIDIS T. Segmentation by texture using a co-occurrence matrix and a split-and-merge algorithm[J]. Computer Graphics Image Processing, 1979, 10（2）: 172-182.

[11]CHEN S Y, LIN W C, CHEN C T. Split-and-merge image segmentation based on localized feature analysis and statistical tests[J]. CVGIP: Graphical Models and Image Processing, 1991, 53（5）: 457-475.

[12]CHANG Y L, LI X. Adaptive image region-growing[J]. IEEE Transactions on Image Processing, 1994, 3（6）: 868-872.

[13]BOYKOV Y, JOLLY MP. Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images[C]//Proceedings of the Eighth International Conference on Computer Vision. Piscataway, NJ: IEEE, 2001:105-112.

[14]GRADY L. Random walks for image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28（11）: 1768-1783.

[15]KASS M, WITKIN A, TERZOPOULOS D. Snakes: active contour models[J]. International Journal of Computer Vision, 1988, 1（4）: 321-331.

[16]OSHER S, SETHIAN J A. Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations[J]. Journal of Computational Physics, 1988, 79（1）: 12-49.

[17]ROUT S, SRIVASTAVA M J. Multimodal image segmentation using a modified Hopfield neural network[J]. Pattern Recognition, 1998, 31（6）: 743-750.

[18]林開顏, 徐立鴻, 吳軍輝. 快速模糊C均值聚類彩色圖像分割方法[J]. 中國圖像圖像學報, 2004, 9（2）: 159-163. LIN Kaiyan, XU Lihong, WU Junhui. A fast fuzzy C-M eans cluster ing for color image segmentation[J]. Journal of Image and Graphics, 2014, 9（2）:159-163.

[19]CAO G B, WANG S L, WEI B Z, et al. A hybrid CNN-RF method for electron microscopy images segmentation[J]. Journal of Biomimetics Biomaterials and Tissue Engineering, 2013, 18（2）: 1-6.

[20]WANG S L, CAO G B, WEI B Z, et al. Hierarchical level features based trainable segmentation for electron microscopy images[J]. Biomedical Engineering Online, 2013, 12（1）: 59-72.

[21]TANG K Z, YUAN X J, SUN T K, et al. An improved scheme for minimum cross entropy threshold selection based on genetic algorithm[J]. Knowledge-Based Systems, 2011, 24（8）: 1131-1138.

[22]YIN P Y. Multilevel minimum cross entropy threshold selection based on particle swarm optimization[J]. Applied Mathematics and Computation, 2007, 182（2）: 503-513.

[23]ALI M, AHN C W, PANT M. Multi-level image thresholding by synergetic differential evolution[J]. Applied Soft Computing, 2014, 17: 1-11.

[24]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: 16-30.

[25]SATHYA P D, KAYALVIZHI R. Optimal multilevel thresholding using bacterial foraging algorithm[J]. Expert System with Application, 2011, 38（12）: 15549-15564.

[26]HORNG M H, LIOU R J. Multilevel minimum cross entropy threshold selection based on the firefly algorithm[J]. Expert System with Application, 2011,38（12）: 14805-14811.

[27]MA M, LIANG J H, GUO M, et al. SAR image segmentation based on artificial bee colony algorithm[J]. Applied Soft Computing, 2011, 11（8）: 5205-5214.

[28]CIVICIOGLU P. Backtracking search optimization algorithm

for numerical optimization problems[J]. Applied Mathematics and Computation, 2013, 219: 8121-8144.

[29]MATHWORKS. Multilevel image thresholds using Otsu′s method[EB/OL]. [2014-08-22]. http://www.mathworks.cn /cn/help/images/ref/multithresh.html.

[30]SHI Y H, EBERHART R C. A modified particle swarm optimizer[C]//Proceedings of the 1998 IEEE World Congress on Computational Intelligence. Piscataway, NJ, 1998: 69-73.

尹雨山，男，1990年生，碩士研究生，主要研究方向為智能信息處理及其應用。

王李進，男，1977年生，副教授，主要研究方向為計算智能及其應用。

尹義龍，男，1972年生，教授，博士生導師，主要研究方向為機器學習、數據挖掘、圖像處理。中國人工智能學會機器學習專委會副秘書長、中國計算機學會多值邏輯與模糊邏輯專委常委、人工智能與模式識別專委會委員。主持國家自然科學基金重點項目等科研項目10余項。獲國家發明專利授權6項。獲2014年度山東省科技進步二等獎1項，2011年入選教育部新世紀優秀人才支持計劃。

Backtracking search optimization algorithm assisted multilevel threshold for image segmentation

YIN Yushan1， WANG Lijin1,2， YIN Yilong1,3， WANG Binqing1， ZHAO Wenting1， XU Yunlong1

（1. School of Computer Science and Technology, Shandong University, Jinan 250101, China; 2. College of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou 350001, China; 3. School of Computer Science and Technology, Shandong University of Finance and Economics, Jinan 250014, China）

The threshold method is a simple and effective image segmentation technique. However, the amount of calculation for solving threshold appears to be exponential amplification with the increase of threshold. This results in a huge challenge for multi-threshold image segmentation. This paper utilizes Otsu and Kapur methods as the target function in order to deal with image segmentation.In this paper, image segmentation is considered as an optimization problem whose objective function is formulated according to Otsu and Kapur methods, respectively. The backtracking search optimization algorithm is used to solve these two objective functions and to realize multi-threshold image segmentation. The proposed approach is applied to nature image segmentation and compared to other algorithms. The results showed that the multi-threshold image segmentation technique on the basis of backtracking search optimization algorithm is feasible and the segmentation effect is satisfactory

threshold method; backtracking search optimization algorithm; image segmentation; Otsu; Kapur; PSNR

2014-10-08.

日期：2015-01-13.

國家自然科學基金-廣東聯合基金重點資助項目（U1201258）；山東省自然科學杰出青年基金資助項目（JQ201316）.

王李進.E-mail：lijinwang@fafu.edu.cn.

10.3969/j.issn.1673-4785.201410008

http://www.cnki.net/kcms/doi/10.3969/j.issn.1673-4785.201410008.html

TP183

A

1673-4785（2015）01-0068-07

尹雨山，王李進，尹義龍，等. 回溯搜索優化算法輔助的多閾值圖像分割[J]. 智能系統學報， 2014, 10（1）: 68-74.

英文引用格式：YIN Yushan， WANG Lijin， YIN Yilong， et al. Backtracking search optimization algorithm assisted multilevel threshold for image segmentation[J]. CAAI Transactions on Intelligent Systems, 2014, 10（1）: 68-74.