李瑞芳

(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,陜西 西安　710126)

?

基于改進(jìn)布谷鳥搜索算法的圖像分割

李瑞芳

(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,陜西 西安710126)

摘要針對布谷鳥搜索算法在應(yīng)用其進(jìn)行圖像分割時計算量大、易陷入局部極小值解、收斂速度慢的問題。文中采用一種基于改進(jìn)布谷鳥搜索算法的多閾值圖像分割算法。該算法以O(shè)stu算法設(shè)計自適應(yīng)度函數(shù),將布谷鳥搜索算法和K均值算法融合,增加種群的多樣性,且能自適應(yīng)地確定閾值個數(shù)及其范圍,并找到待分割圖像的最優(yōu)閾值。實驗結(jié)果表明,與K均值算法和布谷鳥搜索算法相比,該算法找到的閾值質(zhì)量更佳,圖像分割結(jié)果更好。

關(guān)鍵詞圖像分割;閾值分割;K均值

圖像分割的核心思想是通過采取一定的技術(shù)手段提取目標(biāo)區(qū)域,是圖像分析之前的必要準(zhǔn)備。分割圖像的方法有多種,其中最經(jīng)典的當(dāng)屬大津算法,即Ostu法[1]及其各種改進(jìn)方法[3-4]?；诰垲惙治龅膱D像分割方法也是較為常見的圖像分割方法,K均值算法便是其中一種。利用K均值算法做圖像分割實質(zhì)上就是以反復(fù)迭代的方法對圖像像素點進(jìn)行劃分分類,求得一個較好的像素分組。K均值算法因其算法簡單、收斂速度較快等優(yōu)勢,在圖像處理領(lǐng)域得到了廣泛應(yīng)用[5-6]。

近年來,隨著生物啟發(fā)式算法的迅速發(fā)展,研究者們也順勢將這些啟發(fā)式算法成功應(yīng)用于圖像處理領(lǐng)域,如布谷鳥搜索算法(CS)[2]便可應(yīng)用于圖像分割。文獻(xiàn)[2]表明在多峰值優(yōu)化問題中,CS算法要比PS0算法、GA算法的穩(wěn)定性和遺傳性要好,且CS算法結(jié)構(gòu)簡單、參數(shù)少。但CS算法也存在收斂速度慢、搜索精度低、易陷入局部極小值點等不足。Walton等人建議使用隨代數(shù)遞減的步長因子來加速算法的收斂速度[7],Valian等人提出自適應(yīng)步長和自適應(yīng)發(fā)現(xiàn)概率的自適應(yīng)CS算法[8]。此外,還有諸多學(xué)者對CS算法進(jìn)行研究[9-11],但CS算法所固有的缺點仍未得到較好地克服。為充分利用K均值算法和CS算優(yōu)勢的同時克服其不足之處,本文提出一種修正的CS算法(MCS)。

1算法的原理

由于本文所提出的算法是基于閾值的圖像分割,故選Ostu法,即類間方差(1)作為適應(yīng)度函數(shù)

(1)

1.1確定閾值個數(shù)和范圍

首先利用自適應(yīng)K均值算法[12]確定某個鳥巢

xI=(x1,x2,…,xM)

(2)

其中,m表示每個鳥巢中鳥蛋的數(shù)量,即優(yōu)化問題中解空間的維數(shù)。在灰度圖像中,灰度值[0,L-1]便是鳥巢位置,故m=1。

然后根據(jù)Xi的取值確定閾值范圍

Ub=Xi+[diff(Xi),0],Ub(n)=L-1

(3)

Lb=Xi-[diff(Xi),0],Lb(1)=0

(4)

其中,diff(Xi)=[x2-x1,…,xn-xn-1]。

最后初始化鳥巢

X=(X1,X2,…,Xn)=Lb+rand×(Ub-Lb)

(5)

其中,rand∈[0,1]。

1.2修正的CS算法(MCS)

由于CS算法屬于啟發(fā)式算法,故其固有的后期收斂速度慢、易陷入局部極小的缺點仍然存在。鑒于此,本文提出一種修正的CS算法(MCS),即在CS算法中引入k均值聚類算。MCS算法的基本思想:經(jīng)過改進(jìn)后的鳥巢位置X(t+1)不會直接進(jìn)入下一次迭代,而是對其做k均值聚類,產(chǎn)生一個較好的鳥巢位置,并與當(dāng)前最佳的鳥巢位置作比較并保留質(zhì)量較好的鳥巢位置,然后再進(jìn)入下一次迭代,繼續(xù)利用CS算法計算。如此便使得種群多樣性增加,走出了易陷入局部最優(yōu)解的困境取得全局最優(yōu)解,且收斂速度和搜索精度在一定程度上也有所提高。修正布谷鳥搜索算法,即MCS:

步驟1初始化MCS算法的鳥巢。運(yùn)用上述方法初始化鳥巢x=(x1,x2,…,xn),xI=(x1,x2,…,xM)其中,n表示鳥巢數(shù)量,M表示每個鳥巢中鳥蛋數(shù)量,即優(yōu)化問題中解空間的維數(shù);

步驟2根據(jù)適應(yīng)度函數(shù)計算初始化的鳥巢質(zhì)量;

步驟3各鳥巢主人使用Levy飛行機(jī)制更新自己的鳥巢位置。根據(jù)適應(yīng)度函數(shù)計算更新后的鳥巢質(zhì)量,并與更新前的鳥巢質(zhì)量作比較,利用貪婪算法保留質(zhì)量較好的鳥巢位置。鳥巢位置的更新公式為

(6)

其中,t表示迭代次數(shù);α～N(0,1)表示步長控制;⊕表示點乘運(yùn)算符;S表示Levy搜索路徑,即步長

(7)

步驟4按發(fā)現(xiàn)概率Pa丟棄質(zhì)量較差的鳥巢,并用隨機(jī)游動機(jī)制產(chǎn)生新的鳥巢來代替丟棄的鳥巢

(8)

步驟5對改進(jìn)后的鳥巢做k均值聚類,產(chǎn)生一個較好的鳥巢位置;

步驟6將步驟5中所得求鳥巢質(zhì)量與當(dāng)前質(zhì)量最佳的鳥巢位置作比較,保留質(zhì)量較好的鳥巢位置,并根據(jù)式(3)和式(4)更新鳥巢位置范圍,最后根據(jù)式(5)更新鳥巢;

步驟7當(dāng)達(dá)到最大迭代次數(shù)就終止迭代計算,輸出質(zhì)量最好的鳥巢,否則返回步驟2～步驟5。

2算法的流程

MCS算法如下:輸入:圖像u,發(fā)現(xiàn)概率Pa,迭代次數(shù)t,鳥巢數(shù)目n。輸出:分割圖像u1。

步驟1利用自適應(yīng)快速k均值算法[12]求得初始閾值,確定分割閾值個數(shù)num及其范圍Ub,Lb;

步驟2計算各個灰度水平的像素點數(shù)目、概率及期望;

步驟3隨機(jī)初始化各個鳥巢的位置,并計算適應(yīng)度;

步驟4將發(fā)現(xiàn)概率Pa與Pa∈[0,1]比較,根據(jù)比較結(jié)果更新鳥巢位置;

步驟5計算更新后各個鳥巢的適應(yīng)度,并與未更新前相對應(yīng)的鳥巢的適應(yīng)度做比較若結(jié)果較好,則用更新后的適應(yīng)度替換更新前的適應(yīng)度,并替換對應(yīng)的鳥巢位置;

步驟6對比步驟5中所得的最新鳥巢位置的適應(yīng)度,確定當(dāng)前最優(yōu)的鳥巢位置,即適應(yīng)度最大;

步驟7利用k均值算法,對更新后的鳥巢進(jìn)行聚類劃分,求得一個質(zhì)量較好的鳥巢,并與當(dāng)前最優(yōu)的鳥巢比較,保留較好的鳥巢及其適應(yīng)度,并計算新的閾值范圍Ub,Lb;

步驟8判斷是否達(dá)到最大迭代次數(shù),若達(dá)到最大迭代次數(shù)是則停止,否則返回步驟2;

步驟9利用所求得的最佳鳥巢,計算分割圖像u1,并輸出。

3算法的實驗結(jié)果與分析

為驗證本文所提圖像分割算法的有效性,本文做了大量的實驗仿真,并選擇Peppers(256×256)、Livers(256×256)、Zebra(250×167)進(jìn)行說明。新算法與k-means算法、CS算法的有效性用最大類間方差進(jìn)行比較。對k-means模型和MC算法,嚴(yán)格按照其應(yīng)用于圖像分割的方法進(jìn)行實驗。設(shè)置發(fā)現(xiàn)概率Pa=0.25,鳥巢數(shù)目n=25,迭代次數(shù)t=500。

觀察圖1,發(fā)現(xiàn)圖1(D)的對比度高于圖1(b)和圖1(c),所以分割效果較佳。

圖1　Livers的分割結(jié)果

不同圖像分割方法的最大類間方差和最佳閾值如表1～表3所示。從表中可知,相對于K-Means算法、CS算法,本文提出的圖像分割算法(MCS)的最大類間方差值有明顯增大。且CS算法和本文算法在相同的迭代你次數(shù)下,MCS算法的最大類間方差大于CS算法的類間方差,這說明MCS算法的收斂速度要比CS的收斂速度快。同時,MCS算法閾值個數(shù)及其初始值的確定是自適應(yīng)的,而CS算法、K-Means算法閾值個數(shù)及其初始值的確定是需不斷調(diào)整。所以,從時間成本來看,MCS算法也優(yōu)于CS算法和K-Means算法。為對比這3種算法的分割效果,文中將CS算法和K-Means算法的閾值個數(shù)取為MCS算法所求得的閾值個數(shù)。

表1　對Peppers不同分割方法的閾值和最大類間方差

表2　對Livers不同分割方法的閾值和最大類間方差

表3　對Zebra不同分割方法的閾值和最大類間方差

4結(jié)束語

布谷鳥算法(CS)是受自然界中布谷鳥繁衍后代的特性激發(fā),融入Levy飛行機(jī)制,從而形成了一種求解最優(yōu)問題的方法。本文將布谷鳥算法和K均值算法融合,用于增強(qiáng)種群的多樣性,以提高CS算法的搜索能力,走出了易陷入局部最優(yōu)解的困境,且收斂速度在一定程度上也有所提高。此外,本文算法對閾值個數(shù)及其初始值的確定是自適應(yīng)的,無需經(jīng)過額外的調(diào)整。

參考文獻(xiàn)

[1]Ostu N A.Threshold selection method from gray level histograms[J].IEEE Transactions on System,Man,and Cybernetics,1979,9(1):62-66.

[2]Yang Xingshe,Deb S.Cuckoo search via levy flights[C].Coimbatore,India:Proceeding of World Congress on Nature & Biologically Inspired Computing,2009.

[3]胡斌,宮寧生.一種改進(jìn)的Otsu閾值分割算法[J].微電子學(xué)與計算機(jī),2009,26(12):153-155.

[4]Liu Jianzhuang,Li Wenqing.Automatic thresholding using the otsu algorithm based on the two-dimensional gray image[J].Acta Automatica Sinica,1993,19(1):101-105.

[5]Pei Zhenkui,Hua Xia.The clustering algorithm based on particle swarm optimization algorithm[C].Hunan:International Conference on Intelligent Computation Technology and Automation,2008.

[6]Liu Jingming,Han Lichuan.Cluster analysis based on particle swarm optimization algorithm[J].Systems Engineering-Theory & Practice,2005(6):54-58.

[7]Walton S,Hassan O,Morgan K,et al.Modified cuckoo search:A new gradient free optimisation algorithm[J].Chaos Solitons & Fractals,2011,44(9):710-718.

[8]Valian E,Mohanna S,Tavakoli S.Improved cuckoo search algorithm for feedforward neural network training[J].International Journal of Artificial Intelligence & Applications,2011,2(3):36-43.

[9]Tawfik A S,Badr A A,Abdel-Rahman I F.One rank cuckoo search[J].International Journal of Computer Applications,2013,64(6):30-37.

[10]Long Wen,Chen Le.Hybrid cuckoo search algorithm for solving constrained chemical engineering optimization problems[J].Journal of Computer Applications,2014,34(2):523-527.

[11]Yang Xinshe,Suash Deb.Multiobjective cuckoo search for design optimization[J].Computers & Operations Research,2013,40(6):1616-1624.

[12]李玉鑑.自適應(yīng)K-均值聚類算法[J].計算機(jī)研究與發(fā)展,2007(z2):100-104.

An Image Segmentation Algorithm Based on Modified Cuckoo Search

LI Ruifang

(School of Mathematics and Statistics,Xidian University,Xi’an 710126,China)

AbstractThe cuckoo search algorithm (CS) is a bionic algorithm,but its application to image segmentation suffers from such drawbacks as large amount of calculation,appearing local minimum and slow convergence.In order to solve these problems,we propose a multi-threshold image segmentation algorithm based on modified cuckoo search algorithm.This algorithm employs the Otsu method as the fitness function,combines the cuckoo search algorithm with the K-means algorithm for better diversity of population,and adaptively determines the number and range of the thresholds to find the optimal thresholds of the image to be segmented.Experimental results show that the MCS algorithm outperforms the K-means and the cuckoo search (CS) in terms of segmentation thresholds and segmentation effect.

Keywordsimage segmentation;threshold segmentation;K-means

doi:10.16180/j.cnki.issn1007-7820.2016.05.028

收稿日期:2015-10-17

作者簡介:李瑞芳(1990—),女,碩士研究生。研究方向:多尺度分析理論及其在圖像處理中的應(yīng)用。

中圖分類號TP391.41

文獻(xiàn)標(biāo)識碼A

文章編號1007-7820(2016)05-105-03