尹雨山，王李進(jìn),2，尹義龍,3，王冰清，趙文婷，徐云龍

（ 1. 山東大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250101； 2.福建農(nóng)林大學(xué) 計(jì)算機(jī)與信息學(xué)院，福建 福州 350002； 3.山東財(cái)經(jīng)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250014）

?

回溯搜索優(yōu)化算法輔助的多閾值圖像分割

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

（ 1. 山東大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250101； 2.福建農(nóng)林大學(xué) 計(jì)算機(jī)與信息學(xué)院，福建 福州 350002； 3.山東財(cái)經(jīng)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250014）

閾值法是一種簡(jiǎn)單且有效的圖像分割技術(shù)。然而閾值求解的計(jì)算量隨閾值的增加而呈指數(shù)級(jí)別增長(zhǎng)，這給多閾值圖像分割帶來(lái)巨大挑戰(zhàn)。為了克服計(jì)算量過(guò)大問(wèn)題，視多閾值分割模型為優(yōu)化問(wèn)題，分別將Otsu法和Kapur法作為目標(biāo)函數(shù)，采用回溯搜索優(yōu)化算法求解目標(biāo)函數(shù)，實(shí)現(xiàn)多閾值圖像分割。將提出的多閾值分割算法應(yīng)用于自然圖像分割，并與其他算法比較，實(shí)驗(yàn)結(jié)果說(shuō)明基于回溯搜索優(yōu)化算法的多閾值圖像分割技術(shù)是可行的，而且具有較好的分割效果。

閾值法；回溯搜索優(yōu)化算法；圖像分割；Otsu；Kapur；PSNR

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

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

回溯搜索優(yōu)化算法（backtracking search optimization algorithm, BSA）是一種新興的仿生算法，其具有簡(jiǎn)單的結(jié)構(gòu)，并能有效且快速求解各類函數(shù)優(yōu)化問(wèn)題[28]。然而，關(guān)于BSA算法的應(yīng)用研究報(bào)道較少，特別是在圖像處理及應(yīng)用領(lǐng)域。因此，借鑒于仿生算法求解多閾值問(wèn)題的有效性，本文將BSA算法應(yīng)用于圖像分割，提出基于BSA算法的多閾值圖像分割。提出的方法將Otsu算法和最大熵法的準(zhǔn)則函數(shù)視為目標(biāo)函數(shù)，并采用BSA算法分別獲取多閾值，實(shí)現(xiàn)圖像分割。實(shí)驗(yàn)說(shuō)明提出的方法具有更好的性能。

1 閾值法

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

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

（1）

（2）

設(shè)λ、λ1、λ2分別表示圖像、目標(biāo)和背景的灰度值均值，則可表示為

（3）

（4）

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

類間方差可表示為

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

（5）

根據(jù)類間最大化準(zhǔn)則，當(dāng)方差取得最大值時(shí),便得到最佳閾值q。

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

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

（6）

根據(jù)類間最大化準(zhǔn)則，可通過(guò)計(jì)算式（7）獲得最佳閾值：

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

1.2 最大熵法（Kapur法）

20世紀(jì)80年代以來(lái)，Shannon信息熵的概念被應(yīng)用于圖像閾值化處理中，其思想是利用圖像的灰度分布密度函數(shù)定義圖像的信息熵，并根據(jù)優(yōu)化準(zhǔn)則求得閾值。文獻(xiàn)[4]通過(guò)使后驗(yàn)的上限最大化準(zhǔn)則確定閾值，而文獻(xiàn)[5]假定目標(biāo)和背景服從2個(gè)不同的概率分布，使得信息熵最大化求得最佳閾值。

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

（8）

（9）

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

q=argmax（H1+H2）

（10）

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

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

（11）

式中：a表示閾值數(shù)目。

2 回溯搜索優(yōu)化算法

BSA算法是一種新興的隨機(jī)優(yōu)化搜索技術(shù)，其結(jié)構(gòu)簡(jiǎn)單，并且能夠有效求解各類優(yōu)化問(wèn)題。另外，BSA算法也是基于種群的搜索技術(shù)，并且使用一個(gè)外部文檔維護(hù)其歷史種群信息以引導(dǎo)種群進(jìn)化。

當(dāng)BSA算法用于求解優(yōu)化問(wèn)題時(shí)，首先在解搜索空間[xj,min,xj,max] （j=1,2,…,D）內(nèi)，通過(guò)均勻采樣初始化候選解X和歷史種群Xold：

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

（12）

式中：r∈[0,1]是隨機(jī)數(shù)，NP是種群大小。

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

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

Vm=X+F（Xold-X）

（13）

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

算法1交叉策略

輸入變異個(gè)體Vm、種群X、種群規(guī)模NP、問(wèn)題維數(shù)D、以及混合率mixrate。

輸出候選解T

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

2）均勻產(chǎn)生2個(gè)[0,1]之間的隨機(jī)數(shù)a和b；

3）ifa>b，轉(zhuǎn)入4），否則轉(zhuǎn)入5）；

4）進(jìn)行如下操作后轉(zhuǎn)入第6步：

fori=1 to NP

隨機(jī)生成系列u=permuting（1:D）；

均勻生成1個(gè)[0,1]的隨機(jī)數(shù)c；

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

end for

5）進(jìn)行如下操作：

fori=1 to NP

均勻生成1個(gè)[0,D]的隨機(jī)整數(shù)d；

處理map（i, d）=0;

end for

6）T=Vm;

7）進(jìn)行如下操作：

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種選擇操作。第一種選擇操作用于更新歷史種群的信息，其完全隨機(jī)下接收當(dāng)前種群信息，可概括為

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

（14）

第2種選擇操作則根據(jù)當(dāng)前種群X和候選種群T

的適應(yīng)值，貪婪選擇適應(yīng)值較好的個(gè)體進(jìn)入下一代。

3 應(yīng)用BSA求解多閾值

應(yīng)用BSA算法求解多閾值問(wèn)題，其實(shí)質(zhì)是將多閾值準(zhǔn)則作為目標(biāo)函數(shù)，采用BSA算法搜索最優(yōu)閾值，具體步驟如算法2所示。

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

輸入種群規(guī)模NP、問(wèn)題維數(shù)D（閾值數(shù)目）、混合率mixrate、最大迭代次數(shù)MaxIteration。

輸出最佳閾值q

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

2）初始化迭代計(jì)數(shù)器iter=1；

3）if iter>MaxIteration，轉(zhuǎn)入11）;

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

5）執(zhí)行變異操作，即執(zhí)行式（13）；

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

7）采用式（7）或者式（11）評(píng)價(jià)T；

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

9）獲得當(dāng)前最優(yōu)閾值q；

10）iter=iter+1，轉(zhuǎn)入3）；

11）輸出最優(yōu)閾值q。

4 實(shí)驗(yàn)與結(jié)果

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

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

（15）

式中：

（16）

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

在實(shí)驗(yàn)中，各算法針對(duì)每幅圖像獨(dú)立運(yùn)行30次。每次獨(dú)立運(yùn)行中，最大迭代數(shù)MaxIteration為160，種群大小NP為20。

4.1 Otsu方法的實(shí)驗(yàn)結(jié)果

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

表1 MOT和BSA算法的Otsu多閾值目標(biāo)函數(shù)適應(yīng)值和PSNRTable 1 Multi-threshold Otsu fitness and PSNR obtained by MOT and BSA

圖2 PSNR隨Otsu閾值變化的趨

從表1可知，采用BSA算法求解的閾值使得適應(yīng)值都優(yōu)于MOT的所得適應(yīng)值；另外借助于PSNR，BSA算法也優(yōu)于MOT。上述結(jié)果說(shuō)明了BSA算法以O(shè)tsu的最大類間準(zhǔn)則為目標(biāo)函數(shù)求解多閾值是可行的，而且獲得較好的性能。

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

表2 BFA算法、PSO算法和BSA算法求解的Otsu多閾值目標(biāo)函數(shù)適應(yīng)值和PSNRTable 2 Multi-threshold Otsu fitness and PSNR obtained by BFA, PSO and BSA

表3 BFA算法、PSO算法和BSA算法求解的Kapur多閾值目標(biāo)函數(shù)適應(yīng)值和PSNRTable 3 Multi-threshold Kapur fitness and PSNR obtained by BFA, PSO and BSA

4.2 Kapur方法的實(shí)驗(yàn)結(jié)果

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

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

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

圖3 PSNR隨Kapur閾值變化的趨勢(shì)

5 結(jié)束語(yǔ)

本文將BSA算法應(yīng)用于圖像分割，提出BSA算法求解的多閾值圖像分割。提出方法將Otsu方法和Kapur方法的求多閾值準(zhǔn)則函數(shù)作為目標(biāo)函數(shù)，應(yīng)用BSA算法求解，并實(shí)現(xiàn)圖像分割。仿真結(jié)果說(shuō)明BSA算法求解的多閾值圖像分割是可行的，與其他的BFA算法和PSO算法求解的多閾值分割方法比較，本文提出的方法具有較好的性能。下一步工作將提出方法應(yīng)用于更多的圖像測(cè)試，包括遙感圖像以及醫(yī)學(xué)影像等。

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

[2]劉國(guó)英, 馬國(guó)銳, 王雷光, 等. 基于Markov隨機(jī)場(chǎng)的小波域圖像建模及分割—Matlab環(huán)境[M]. 北京:科學(xué)出版社, 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]林開(kāi)顏, 徐立鴻, 吳軍輝. 快速模糊C均值聚類彩色圖像分割方法[J]. 中國(guó)圖像圖像學(xué)報(bào), 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年生，碩士研究生，主要研究方向?yàn)橹悄苄畔⑻幚砑捌鋺?yīng)用。

王李進(jìn)，男，1977年生，副教授，主要研究方向?yàn)橛?jì)算智能及其應(yīng)用。

尹義龍，男，1972年生，教授，博士生導(dǎo)師，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、圖像處理。中國(guó)人工智能學(xué)會(huì)機(jī)器學(xué)習(xí)專委會(huì)副秘書(shū)長(zhǎng)、中國(guó)計(jì)算機(jī)學(xué)會(huì)多值邏輯與模糊邏輯專委常委、人工智能與模式識(shí)別專委會(huì)委員。主持國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目等科研項(xiàng)目10余項(xiàng)。獲國(guó)家發(fā)明專利授權(quán)6項(xiàng)。獲2014年度山東省科技進(jìn)步二等獎(jiǎng)1項(xiàng)，2011年入選教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃。

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.

國(guó)家自然科學(xué)基金-廣東聯(lián)合基金重點(diǎn)資助項(xiàng)目（U1201258）；山東省自然科學(xué)杰出青年基金資助項(xiàng)目（JQ201316）.

王李進(jìn).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ìn)，尹義龍，等. 回溯搜索優(yōu)化算法輔助的多閾值圖像分割[J]. 智能系統(tǒng)學(xué)報(bào)， 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.