馮 哲, 陳云鳳, 周 宇, 云 挺, 鄧玉和

(1.南京林業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院, 江蘇 南京 210037)(2.南京林業(yè)大學(xué) 材料科學(xué)與工程學(xué)院,江蘇 南京 210037)

基于改進(jìn)的NCSPSO-AFSA對SVM參數(shù)的優(yōu)化及其應(yīng)用

馮 哲1, 陳云鳳1, 周 宇1, 云 挺1, 鄧玉和2

(1.南京林業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院, 江蘇 南京 210037)(2.南京林業(yè)大學(xué) 材料科學(xué)與工程學(xué)院,江蘇 南京 210037)

為了找到支持向量機(jī)(SVM)最佳的分類參數(shù),用以構(gòu)建適合紋理圖像分割的SVM分類器,文中是將基于小生境和交叉選擇算子的粒子群算法(NCSPSO)引入變異算子和族外競爭機(jī)制加以改進(jìn)后與人工魚群算法(AFSA)混合,提出了一種改進(jìn)的NCSPSO-AFSA混合算法優(yōu)化支持向量機(jī)參數(shù),并分別與AFSA算法,粒子群算法(PSO),NCSPSO算法在圖像分割準(zhǔn)確率、參數(shù)尋優(yōu)時(shí)間、圖像分割時(shí)間等方面進(jìn)行對比和分析,實(shí)驗(yàn)表明文中算法能夠更好地獲得適用于紋理圖像分割的SVM參數(shù),在縮短圖像分割時(shí)間的同時(shí)提高了圖像分割準(zhǔn)確率,相比較其他算法,文中算法穩(wěn)健性更好.將此方法應(yīng)用于電鏡及超聲紋理圖像分割中能較好地提取出目標(biāo)區(qū)域,圖像邊緣部分的分類也很清晰.

NCSPSO算法; 人工魚群算法; 支持向量機(jī); 圖像分割

圖像分割是圖像處理與計(jì)算機(jī)視覺領(lǐng)域中最為基礎(chǔ)和重要的問題之一,圖像分割的效果將直接影響到后續(xù)分析、識別和解釋等處理.而紋理是圖像的重要特征,普遍存在于各類圖像當(dāng)中,由于紋理圖像自身的復(fù)雜性,使得紋理圖像的分割顯得尤為困難.

支持向量機(jī)[1](support vector machine, SVM)是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法,能較好地解決小樣本、非線性等實(shí)際問題.實(shí)踐表明,SVM的性能與核函數(shù)的參數(shù)及懲罰系數(shù)C有很大關(guān)系.文中在基于小生境和交叉選擇算子的粒子群算法中加入變異算子和族外競爭機(jī)制,再將其與人工魚群算法混合,提出了改進(jìn)的NCSPSO-AFSA混合算法.該算法有利于提高紋理圖像分割的速度和精度.

1 SVM分類器

對于給定的線性可分?jǐn)?shù)據(jù)集{xi,yi},i=1,…,l,yi∈{-1,+1},xi∈Rn,滿足

yi[w·xi+b]-1≥0;i=1,…,l

(1)

利用Lagrange乘子法并滿足KKT(Karush-kuhn-Tucher)條件,最后可得到解上述問題的最優(yōu)分類函數(shù)為:

f(x)=sgn{w*·x+b*}=

(2)

式中：α*,b*為確定最優(yōu)劃分超平面的參數(shù),(xi·x)為兩個(gè)向量的點(diǎn)積.

對于線性不可分情況,通過在約束條件中引入松弛變量,在目標(biāo)函數(shù)中加入懲罰函數(shù)來解決這一問題.這時(shí)廣義最優(yōu)分類面問題可以進(jìn)一步演化為求取下列函數(shù)的極小值:

(3)

式中:C為懲罰系數(shù),用于控制錯(cuò)分樣本懲罰的程度.

支持向量機(jī)引入核函數(shù),避免了高維空間的向量內(nèi)積而造成大量運(yùn)算.徑向基核函數(shù)是目前應(yīng)用最廣泛的核函數(shù),文中采用的就是這一核函數(shù),形式如下:

K(xi,xj)=exp(-γ‖xi-xj‖2),γ>0

(4)

式中:參數(shù)γ是核函數(shù)中的重要參數(shù),影響著SVM分類算法的復(fù)雜程度.

綜上所述,懲罰參數(shù)C和核函數(shù)參數(shù)γ是影響SVM分類器性能的關(guān)鍵參數(shù),所以文中以(C,γ)作為尋優(yōu)變量.

2 基于改進(jìn)的NCSPSO-AFSA優(yōu)化SVM的紋理圖像分割方法

2.1 現(xiàn)有NCSPSO算法

針對粒子群算法容易陷入局部最優(yōu),出現(xiàn)早熟現(xiàn)象,池元成等人[2]2010年結(jié)合小生境和交叉選擇算子提出了一種改進(jìn)粒子群優(yōu)化算法(NCSPSO).該算法通過對當(dāng)前代個(gè)體歷史最好位置的多樣化處理,增強(qiáng)了粒子搜索復(fù)雜未知空間的能力.

首先,根據(jù)小生境數(shù)[3-4]確定孤立點(diǎn).假設(shè)當(dāng)前代個(gè)體歷史最好位置的集合為CP={Pi=(pi1,pi2,…,piD) |i=1,2,…,N},計(jì)算該集合所有元素之間的距離

(5)

其中,i=1,2,…,N,j=1,2,…,N,且i≠j.相應(yīng)的共享函數(shù)值

(6)

其中,σshare為給定的小生境半徑.在此基礎(chǔ)上,計(jì)算每個(gè)元素的小生境數(shù)

(7)

其中,i=1,2,…,N,且i≠j.經(jīng)過比較,小生境數(shù)最小的元素就是當(dāng)前代個(gè)體歷史最好位置中的孤立點(diǎn)Q=(q1,q2,…,qD).

然后對所有個(gè)體歷史最好值劣于孤立點(diǎn)值的粒子使用交叉和選擇算子進(jìn)行更新.

2.2 人工魚群算法

人工魚群算法(artificial fish-swarm algorithm,AFSA) 是李曉磊等人[5]于2002年提出的一種基于模擬魚群行為的隨機(jī)搜索優(yōu)化算法.它是說在一片水域中,魚往往能自行或尾隨其它魚找到營養(yǎng)物質(zhì)多的地方,因而魚生存數(shù)目最多的地方一般就是本水域中營養(yǎng)物質(zhì)最多的地方.人工魚群算法就是根據(jù)仿生學(xué)特點(diǎn),通過構(gòu)造人工魚來模仿魚群的覓食、聚群及追尾行為,從而實(shí)現(xiàn)尋優(yōu)[6-7].人工魚在移動中有3個(gè)典型的行為:

1)覓食行為 魚在水中自由地游動,發(fā)現(xiàn)食物時(shí),會向著食物逐漸增多的方向迅速游去.

2)聚群行為 魚在游動過程中為了保證自身的生存和躲避危害會自然地聚集成群.魚聚群時(shí)所遵守的規(guī)則有3條:① 避免與伙伴過于擁擠;② 盡量與伙伴的平均方向一致;③ 盡量朝伙伴的中心移動.

3)追尾行為 當(dāng)發(fā)現(xiàn)食物時(shí),魚會尾隨其臨近的伙伴快速到達(dá)食物點(diǎn).

2.3 NCSPSO算法的改進(jìn)

2.3.1 引入變異算子

NCSPSO算法對當(dāng)前代個(gè)體歷史最好位置進(jìn)行了多樣化處理,但由于個(gè)體沒有變異機(jī)制,一旦陷入局部最優(yōu)時(shí)需要借助其他個(gè)體跳出局部最優(yōu)的環(huán)境.由于文中改進(jìn)的算法最終是應(yīng)用于SVM參數(shù)優(yōu)化,并應(yīng)用到兩類紋理圖像分割,因此適應(yīng)度值很重要.鑒于此,對變異算子做出了相應(yīng)的改進(jìn):

(8)

根據(jù)變異因子,文中對于適應(yīng)度值劣于孤立點(diǎn)適應(yīng)度值的個(gè)體采用如下的變異方式:

(9)

1)固定取值的變異算子,以FG1=0.2,FG2=0.9為例.

2)傳統(tǒng)的動態(tài)變異算子:FG=FG1+rand(0,1)·(FG2-FG1).

3)改進(jìn)變異算子,取值方式如式(8).以4種變異算子的取值為例,將荻草圖像和超聲圖像作為分割對象,進(jìn)行分割測試.

采用兩類紋理圖像作為分割對象,其中荻草細(xì)胞圖來自國家科學(xué)自然基金項(xiàng)目(30871973),超聲圖像是醫(yī)院實(shí)際所用超聲圖像[8].圖像紋理特征的提取方法參考文獻(xiàn)[9],采用結(jié)合灰度共生矩陣Curvelet變換的特征提取方法.

表1列舉了不同的變異算子FG的取值對荻草圖像和超聲圖像的分割效果.其中:圖像分割時(shí)間為獲得C和γ后建立的分類模型對兩類紋理圖像進(jìn)行分割所用時(shí)間.從表1可以看出引入變異算子,尤其是經(jīng)過文中改進(jìn)的變異算子的取值方式使得兩類圖像的分割準(zhǔn)確率均略高于其他方式,所用的圖像分割時(shí)間也少.

表1 選擇不同變異算子時(shí)的訓(xùn)練結(jié)果Table 1 Training results with different mutation operator

2.3.2 引入族外競爭機(jī)制

NCSPSO算法的選擇操作是在同一個(gè)種群中不同的小生境之間形成的競爭,就是意義上的內(nèi)部競爭.為了增加個(gè)體之間的競爭壓力,將個(gè)體的直接的競爭擴(kuò)大到不同種群之間,將進(jìn)化種群中的最優(yōu)解的個(gè)體與隨機(jī)組成的種群的最優(yōu)解形成競爭.族內(nèi)競爭使個(gè)體易于局部最優(yōu),而族外競爭使目標(biāo)函數(shù)值向全局最優(yōu)解快速收斂.

將初始種群稱作主群,根據(jù)隔離機(jī)制的小生境的基本思想,將主群任意分為若干子群,每個(gè)子群是由主群的一部分和其他子群的全局最優(yōu)值構(gòu)成的.而在整個(gè)算法的迭代過程中,主群的進(jìn)化更新與子群的進(jìn)化更新相互獨(dú)立.

2.4 改進(jìn)NCSPSO-AFSA優(yōu)化的SVM分類模型

1) 樣本數(shù)據(jù)初始化

樣本數(shù)據(jù)大小為100×136,并進(jìn)行[0,1]區(qū)間歸一化.

2) 人工魚群算法設(shè)置

Step1:設(shè)定魚群的參數(shù),包括魚群規(guī)模m,最大迭代次數(shù)gen,最大嘗試次數(shù)trynum,最大移動步長step,擁擠度因子δ等;

Step2:計(jì)算初始適應(yīng)度值,把最優(yōu)值放入公告板中;

Step3:計(jì)算出追尾行為、群聚行為的值,選擇最優(yōu)的行為作為魚的前進(jìn)方向,同時(shí)與公告板中的值進(jìn)行比較,如果優(yōu)于公告板上的值則更新公告板;

Step4:判斷是否達(dá)到最大迭代次數(shù),若已經(jīng)達(dá)到則終止尋優(yōu),輸出公告板上的最優(yōu)值;否則,返回到Step2,繼續(xù)運(yùn)行.

3) 改進(jìn)的NCSPSO算法設(shè)置

Step1:初始化進(jìn)化主種群,包括最大種群數(shù)、最大迭代次數(shù)、個(gè)體的位置和速度、計(jì)算主種群初始的適應(yīng)度值.

Step2:根據(jù)隔離機(jī)制的小生境的基本思想,將主種群分為了子群1和子群2,子群1的一部分是從主群中任意選出,另外一部分是由子群2的全局最優(yōu)值構(gòu)成.子群2同樣由此構(gòu)成.

Step3:更新進(jìn)化種群

①比較子群1和子群2的全局最優(yōu)值是否優(yōu)于主群的最優(yōu)解,如果優(yōu)于主群的最優(yōu)解,使用子群1和子群2的最優(yōu)解替換主群中的任意一行,進(jìn)行族外競爭.

②根據(jù)公式(5～7)確定主群中的孤立點(diǎn).

③對適應(yīng)度值劣于孤立點(diǎn)適應(yīng)度值的個(gè)體進(jìn)行交叉操作.

④根據(jù)公式(8～9)對適應(yīng)度值劣于孤立點(diǎn)適應(yīng)度值的個(gè)體進(jìn)行變異操作.

⑤對上面兩步產(chǎn)生的新個(gè)體進(jìn)行選擇競爭操作.

Step4:使用標(biāo)準(zhǔn)粒子群算法更新子群1和子群2的個(gè)體[10],與主種群的進(jìn)化相互獨(dú)立.

Step5:判斷是否達(dá)到最大迭代次數(shù),若已經(jīng)達(dá)到則終止尋優(yōu),輸出主群全局最優(yōu)解;否則,返回到Step2,繼續(xù)運(yùn)行.

4) 比較兩種算法所取得的C和γ的值,取最佳組合(C,γ).

3 實(shí)驗(yàn)結(jié)果與分析

3.1 SVM參數(shù)的選取

根據(jù)SVM理論,核函數(shù)的不同影響分類器的性能的好壞,所以核函數(shù)及相關(guān)參數(shù)選擇的好壞直接影響到SVM的性能.對于選定的核函數(shù)來說,選擇合適的懲罰系數(shù)C和γ是非常關(guān)鍵的.下面將運(yùn)用PSO算法、NCSPSO算法、AFSA算法和文中的算法分別選擇較為合適的參數(shù)，如表2.

表2 4種方法的參數(shù)值對比Table 2 Parameters of four methods

3.2 訓(xùn)練樣本的選取

文中實(shí)驗(yàn)軟件平臺為MATLAB R2011a,運(yùn)行環(huán)境為雙CPU PC機(jī),CPU是主頻為3.2G的Intel Pentium 4多線程處理器,內(nèi)存為2G,硬盤大小為250G,操作系統(tǒng)是Windows XP Professional SP3.

表3,4是以荻草圖像和超聲圖像做的對比試驗(yàn),在種群規(guī)模大小相同,迭代次數(shù)相同的情況下,隨機(jī)選取不同大小的訓(xùn)練樣本,使用改進(jìn)的NCSPSO-AFSA混合算法所取得的尋優(yōu)時(shí)間和分割準(zhǔn)確率.其中樣本1大小為100×136的矩陣,樣本2大小為200×136的矩陣,樣本3大小為300×136的矩陣,樣本4大小為400×136的矩陣,樣本5大小為500×136的矩陣.

表3 樣本大小不同情況下兩類圖像尋優(yōu)時(shí)間比較Table 3 Optimization time of texture image withdifferent sample size s

表4 樣本大小不同情況下兩類圖像分割準(zhǔn)確率比較Table 4 Segmentation accuracy of texture image withdifferent sample size %

從表3，4可以看出,不論是荻草圖像還是超聲圖像,隨著訓(xùn)練樣本的逐漸增大,整個(gè)算法的尋優(yōu)時(shí)間成倍的增長,但是平均分割準(zhǔn)確率不僅沒有明顯的增長,還略有下降的趨勢.超聲圖像樣本1的平均尋優(yōu)時(shí)間只有樣本5的1/15,甚至更少,平均分割準(zhǔn)確率卻比樣本5高出7%,甚至更多.這說明了樣本大小的選取對于整個(gè)算法性能的穩(wěn)定有很大的影響,樣本1大小更加適合改進(jìn)的NCSPSO-AFSA混合算法,通過樣本1找到的C和γ建立的分類模型更好.

3.3 圖像分割效果

為了對比,將改進(jìn)的NCSPSO-AFSA混合算法與PSO,NCSPSO,AFSA算法優(yōu)化SVM建立的分類模型對荻草圖像a1)和一組超聲圖像a2)～a8)做了分割實(shí)驗(yàn).圖中a1)～a8)為原圖,b1)～b8)、c1)～c8)、d1)～d8)分別為PSO算法、NCSPSO算法和AFSA算法優(yōu)化SVM后的分割效果圖,e1)～e8) 為改進(jìn)的NCSPSO-AFSA混合算法的分割效果圖.

圖1實(shí)驗(yàn)結(jié)果
Fig.1Segmentationresults

從分割效果圖1可以看出:文中方法對荻草細(xì)胞圖像和超聲圖像均達(dá)到了很好的分割效果.相比PSO算法、AFSA算法,改進(jìn)的NCSPSO-AFSA混合算法的紋理分割區(qū)域的邊緣輪廓更加完整、更加精確.而與NCSPSO算法相比,改進(jìn)的NCSPSO-AFSA混合算法穩(wěn)健性更好.

3.4 訓(xùn)練結(jié)果比對

在種群規(guī)模大小相同,尋優(yōu)迭代次數(shù)相同的情況下,對以上4種算法每次取得最優(yōu)解的時(shí)間,即收斂代數(shù)做了比較.從圖2中可以看出,改進(jìn)的NCSPSO-AFSA混合算法均在迭代3～5次之間就能獲取最優(yōu)解,而且適應(yīng)度值均高于95%.這表明改進(jìn)的NCSPSO-AFSA混合算法所找到的C和γ更加適合用于建立SVM紋理圖像分割模型.

圖24種方法的訓(xùn)練結(jié)果對比
Fig.2Comparativeresultsoffourmethods

4種方法的分割結(jié)果見表5,從表5可以看出:采用改進(jìn)的NCSPSO-AFSA混合算法尋找到的C和γ,建立SVM分類模型,不論是對兩類或多類的紋理圖像分割,都取得了很高的分割準(zhǔn)確率.對比AFSA算法,文中方法的尋優(yōu)時(shí)間較長于AFSA算法,但是分割準(zhǔn)確率比AFSA算法平均高出1%.對比NCSPSO算法,文中方法的分割準(zhǔn)確率平均提高了0.5%.對比PSO的方法,文中方法尋找最佳C和γ所用時(shí)間是其1/3,分割準(zhǔn)確率平均提高1%,圖像分割時(shí)間是其1/2.

表5 4種方法的分割結(jié)果對比Table 5 Segmentation results of four methods

4 結(jié)論

文中提出了基于改進(jìn)的NCSPSO-AFSA混合算法對SVM參數(shù)優(yōu)化,以荻草圖像和超聲圖像作為實(shí)例,分別采用PSO算法、NCSPSO算法、AFSA算法和文中的算法進(jìn)行比較分析,結(jié)果表明文中的算法所找到的參數(shù)C和γ對紋理圖像分割取得了很高的分割準(zhǔn)確率,同時(shí)縮短了圖像分割時(shí)間,在算法穩(wěn)健性上有一定的優(yōu)勢.應(yīng)用到電鏡及超聲紋理圖像的分割建模,取得了較好的效果.

References)

[1] Vapnik V, Levin E, Cun Y L. Measuring the VC-dimension of learning machines[J].NeuralComputation,1994, 6(5): 851-876.

[2] 池元成,方杰,魏鑫,等. 基于小生境和交叉選擇算子的改進(jìn)粒子群優(yōu)化算法[J]. 系 統(tǒng) 仿 真 學(xué)報(bào), 2010, 22(1):111-114. Chi Yuancheng, Fang Jie, Wei Xin,et al. Improved particle swarm optimization algorithm based on niche, crossover and selection operators[J].JournalofSystemSimulation,2010, 22(1):111-114.(in Chinese)

[3] 朱寧,馮志剛,王祁. 基于小生境遺傳算法的支持向量機(jī)分類器參數(shù)優(yōu)化[J]. 南京理工大學(xué)學(xué)報(bào):自然科學(xué)版, 2009, 33(1): 16-20. Zhu Ning, Feng Zhigang, Wang Qi. Parameter optimization of support vector machine for classification using niche genetic algorithm[J].JournalofNanjingUniversityofScienceandTechnology:NatureScience,2009, 33(1): 16-20. (in Chinese)

[4] 李雋穎,樓曉俊. 基于小生境遺傳算法的分類優(yōu)化方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(5): 1787-1790. Li Junying,Lou Xiaojun. Classifier optimization method using niche genetic algorithm[J].ApplicationResearchofComputers,2012, 29(5): 1787-1790. (in Chinese)

[5] 李曉磊,邵之江,錢積新. 一種基于動物自治體的尋優(yōu)模式:魚群算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2002, 22: 32-38. Li Xiaolei,Shao Zhijiang,Qian Jixin.An optimizing method based on autonomous animats: fish-swarmalgorithm[J].SystemsEngineering:Theory&Practice,2002, 22: 32-38. (in Chinese)

[6] 楊利紅. 基于AFSA的SVM參數(shù)優(yōu)化及其應(yīng)用[D]. 山西太原: 太原理工大學(xué), 2012.

[7] 施秋紅. 人工魚群算法的改進(jìn)及應(yīng)用研究[D]. 甘肅蘭州: 甘肅農(nóng)業(yè)大學(xué), 2010.

[8] 曹琳,云挺,舒華忠. 基于曲線波的超聲圖像分割[J]. 東南大學(xué)學(xué)報(bào):自然科學(xué)版, 2012, 42(3): 419-423. Cao Lin，Yun Ting，Shu Huazhong. Ultrasound image segmentation based on curvelet[J].JournalofSoutheastUniversity:NaturalScienceEdition,2012, 42(3): 419-423. (in Chinese)

[9] 王嫻,周宇,云挺,等. 基于Curvelet變換的荻草細(xì)胞圖像分割[J]. 計(jì)算機(jī)科學(xué), 2012, 39(11): 277-279. Wang Xian, Zhou Yu, Yun Ting,et al. Miscanthus Sacchariflorus Cells Image Segmentation Based on Curvelet Transformation[J].ComputerScience,2012, 39(11): 277-279.(in Chinese)

[10] 陳云鳳,云挺,周宇,等. 基于PSO優(yōu)化SVM的紋理圖像分割[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2014, 31(4): 214-218. Chen Yunfeng, Yun Ting, Zhou Yu, et al. Texture image segmentation based on pso optimising svm[J].ComputerApplicationsandSoftware,2014, 31(4): 214-218.(in Chinese)

(責(zé)任編輯：顧 琳)

ParameteroptimizationandapplicationofSVMbasedonimprovedNCSPSOandAFSA

Feng Zhe1, Chen Yunfeng1, Zhou Yu1, Yun Ting1, Deng Yuhe2

(1.College of Information Science and Technology, Nanjing Forestry University, Nanjing Jiangsu 210037, China)(2.College of Materials Science and Engineering, Nanjing Forestry University, Nanjing Jiangsu 210037, China)

To find the best parameters of SVM and construct the SVM Classifier which is suitable to be applied to texture image segmentation, the paper improves niche and cross-selection operator PSO where mutation mechanism and group competition mechanism are introduced and combined with artificial fish-swarm algorithm (AFSA). The parameter optimization algorithm for support vector machine (SVM) is proposed. Compared with AFSA, particle swarm optimization and NCSPSO algorithm in accuracy and time of image segmentation and parameter optimization time, it turns out that the proposed algorithm can effectively find the parameters of SVM, cut time and improve accuracy of image segmentation, at the same time, its stability is better than other algorithms. When applied to the electron microscope image and ultrasonic image segmentation, the method it can extract the target area and the image edges are classified quite clearly.

NCSPSO; AFSA; support vector machine; image segmentation

10.3969/j.issn.1673-4807.2014.04.018

2014-08-03

國家自然科學(xué)基金資助項(xiàng)目(31300472)；國家自然科學(xué)基金資助項(xiàng)目(30871973)；江蘇省自然科學(xué)基金資助項(xiàng)目(BK2012418)

馮 哲(1992—)，女，研究方向?yàn)槟Ｊ阶R別與圖像處理.E-mail:535716987@qq.com

周 宇(1972—)，女，副教授，研究方向?yàn)閳D像數(shù)理、數(shù)據(jù)融合.E-mail:zhouyu@shanghaitech.edu.cn

TN911.73

A

1673-4807(2014)04-0395-08