混沌與對立學習正余弦算法及多閾值圖像分割

楊 淼

(1.武漢科技大學 信息科學與工程學院，湖北 武漢 430080；2.常州工程職業(yè)技術(shù)學院 智能制造學院，江蘇 常州 213164)

0 引 言

圖像分割的目標是根據(jù)位置、紋理或灰度級將圖像劃分為特定區(qū)域[1]，常用方法分為閾值法、區(qū)域法和邊緣法[2-4]。閾值分割法具有較強魯棒性和準確性，是圖像分割的主流方法。閾值法又可以分為單閾值和多閾值。單閾值以獨立閾值分割圖像為前景和背景，多閾值則根據(jù)亮度信息將圖像分割為若干類別。多閾值法中，Kapur熵和大津Otsu法是目前的主流方法。Kapur熵以最大化分割類別直方圖熵為目標尋找最優(yōu)閾值，而Ostu法則通過最大化類間方差尋找最優(yōu)閾值。問題在于：隨著分割閾值量的增加，分割算法時間復雜度呈現(xiàn)指數(shù)遞增，搜索空間擴展太快。

群智能算法較強的全局尋優(yōu)能力，被學者們利用于圖像分割領(lǐng)域。如文獻[5]采用PSO算法在多閾值圖像分割中，文獻[6]利用WOA對圖像分割的多閾值進行尋優(yōu)，文獻[7]引入GWO設計熵最大化的多閾值圖像分割算法，具有較好的全局搜索能力和收斂性能，圖像分割質(zhì)量更高。文獻[8]引入智能ABC算法對灰度圖像分割閾值進行尋優(yōu)，表現(xiàn)良好的搜索能力。其它群智能算法[9-11]在求解多閾值圖像分割問題上也展現(xiàn)出良好的分割性能。

正弦余弦算法SCA是一種新型群智能優(yōu)化算法[12]，利用正弦余弦函數(shù)的振蕩波動進行全局尋優(yōu)。因其參數(shù)少、結(jié)構(gòu)簡單且易于實現(xiàn)的優(yōu)點，尋優(yōu)性能優(yōu)于遺傳算法、粒子群算法和花授粉等算法。然而，處理復雜高維問題時，SCA算法依然存在尋優(yōu)精度低、易得到局部最優(yōu)的不足。本文將設計一種改進的正余弦算法并將其應用于多閾值圖像分割問題求解問題上，并利用改進正余弦算法對分割閾值尋優(yōu)，有效提升了圖像分割精度和分割效率。

1 正弦余弦算法SCA

SCA算法是一種隨機優(yōu)化算法，利用數(shù)學中正弦余弦函數(shù)的振蕩特性尋找最優(yōu)解，波形向外擴展即為全局搜索，趨近最優(yōu)解的波動即為局部開發(fā)。假設種群粒子數(shù)量為N，位置維度為d，第t次迭代時粒子i的位置表示為xi(t)=(xi1,xi2,…,xid)。 通過計算粒子的適應度，比較種群中粒子所處位置的優(yōu)劣。令當前種群中最優(yōu)粒子為pg(t)=(pg1,pg2,…,pgd)， 粒子i的位置更新方式為

(1)

其中，j=1,2,…,d， 表示位置維度，d>0，r2∈[0,2π]，r3∈[-2,2]，r4∈[0,1]， 3個參數(shù)均為隨機量。r1為振幅轉(zhuǎn)換因子，定義為

(2)

其中，Tmax為最大迭代數(shù)，a為常量，一般取值2。根據(jù)SCA算法的位置更新式(1)可知，算法的主要參數(shù)為r1、r2、r3、r4。振幅轉(zhuǎn)換因子r1用于決定粒子迭代的位置區(qū)域，平衡算法的全局搜索和局部開發(fā)過程；r2用于決定粒子的移動方向，表明當前解是靠近目標解，或是遠離目標解；r3用于決定目標位置的隨機權(quán)重， |r3|<1 代表需要增強目標解對當前解的指導影響， |r3|>1 則代表需要削弱目標解對當前解的牽引；r4用于決定正弦函數(shù)sine()和余弦函數(shù)cosine()的隨機切換概率。

2 融入混沌與對立學習機制的改進正弦余弦算法COLSCA

2.1 振幅轉(zhuǎn)換因子非線性調(diào)整

SCA算法中，振幅轉(zhuǎn)換因子r1的作用是平衡算法的全局搜索和局部開發(fā)過程。r1>1時，粒子處于目標位置和當前位置之外，算法傾向于全局搜索；r1<1時，粒子介于目標位置與當前解之間，算法則傾向于局部開發(fā)。而式(2)表明，r1在區(qū)間[0,a]內(nèi)將隨著迭代次數(shù)的增加而呈線性遞減趨勢，使得在迭代初期，r1取值較大，搜索步長更長，算法具有更強的全局搜索能力，但參數(shù)遞減太快，全局搜索不充分，易得到局部最優(yōu)；而在迭代后期，r1取值較小，遞減速度慢，算法無法快速收斂。為了均衡算法的全局搜索與局部開發(fā)能力，改進算法COLSCA采用基于對數(shù)函數(shù)的非線性調(diào)整策略，將振幅轉(zhuǎn)換因子r1的更新方式定義為

(3)

其中，astart、aend分別代表參數(shù)a的初值和終值，astart>aend≥0，e為自然數(shù)常量，ζ為調(diào)節(jié)系數(shù)。根據(jù)式(3)，r1將呈非線性遞減，前期迭代次數(shù)更多，可以提升全局搜索能力，后期迭代會加速遞減，加快算法收斂，進而有效提升SCA算法的尋優(yōu)精度和收斂速度。

2.2 混沌搜索機制

由式(1)可知，粒子位置的更新主要由精英個體(當前種群中最優(yōu)粒子為pg)引導，為了提升種群的多樣性，引入混沌搜索對種群的精英粒子進行混沌變異。令prob表示種群的精英粒子占比，0

eaj(t)=min(ex1j(t),ex2j(t),…,exmj(t))

(4)

ebj(t)=max(ex1j(t),ex2j(t),…,exmj(t))

(5)

利用式(6)將精英粒子exi(t) 映射到區(qū)間[0,1]，得到混沌變量Ci(t)=(Ci1(t),Ci2(t),…,Cij(t))， 有

(6)

利用式(7)對Cij(t)進行混沌迭代，有

Cij(k+1)=μCij(k)(1-Cij(k))

(7)

式中：k為混沌迭代數(shù)，μ為常量。

當混沌迭代次數(shù)到達最大值kmax時，可以得到種群中精英粒子i對應的混沌變量，表示為Ci(kmax)。 然后，可結(jié)合混沌變量將該精英粒子映射至區(qū)間 [eaj(t),ebj(t)]， 得到相應的混沌粒子XCi(t)， 具體映射公式為

XCi(t)=Ci(kmax)(ebj(t)-eaj(t))+eaj(t)

(8)

根據(jù)原始精英粒子exi(t)和混沌粒子XCi(t)，可得變異粒子候選解為

xi(t)′=λ·exi(t)+(1-λ)·XCi(t)

(9)

λ=(Tmax-t)/Tmax

(10)

其中，λ為收縮因子?？梢姡藢㈦S迭代次數(shù)遞減。

在侯選變異粒子與原始精英粒子間采用貪婪策略，選擇適應度函數(shù)值f(·)更優(yōu)的個體取代原始精英粒子，即

(11)

式中：f(·)表示適應度函數(shù)，也對應于實驗分析中的基準函數(shù)(目標函數(shù))。

根據(jù)式(9)、式(10)可知，收縮因子λ隨著迭代增加而減小，此時，精英粒子exi(t)對變異粒子侯選解xi(t)′的影響將逐步降低，即代表精英粒子的邊界會逐步縮小至目標解區(qū)域，侯選解xi(t)′越側(cè)重于混沌粒子XCi(t)，由于該粒子的隨機性、遍歷性更好，故此時局部開發(fā)能力變得更強。

2.3 對立學習機制

對立學習可以在通過同步考慮當前解及其對立解的適應度的情況下，通過貪婪選擇改善候選解的質(zhì)量，提升種群多樣性。為了提高SCA算法的尋優(yōu)精度，進一步引入對立學習機制改進SCA算法中粒子位置的更新方式，使SCA算法的原始更新方法及對立學習機制交替執(zhí)行，在確保種群多樣性的同時，改善算法的尋優(yōu)精度和收斂速度。

令迭代t時粒子i的位置為xi(t)=(xi1,xi2,…,xid)，lj、uj分別表示j維位置上的下邊界和上邊界，則粒子i的對立位置為

xij(t)′=lj+uj-xij(t)

(12)

若對立解xi(t)′的適應度優(yōu)于原始解xi(t)， 即f(xi(t)′)≥f(xi(t))， 則可以對立解替換原始解；否則，依然保留原始解在種群中。則采用對立學習機制后，種群的生成思想是：通過對立學習生成種群的N個對立解，改進算法COLSCA將在2N個種群粒子中利用貪婪選擇策略選擇N個粒子至下一代種群，確保較強的全局搜索能力的同時，豐富種群多樣性。

以下是COLSCA算法的詳細執(zhí)行過程：

步驟1 參數(shù)初始化，包括：種群規(guī)模N、最大迭代數(shù)Tmax、參數(shù)a的初值astart和終值aend、調(diào)節(jié)系數(shù)ζ、精英粒子概率prob、混沌系數(shù)μ；

步驟2 種群初始化，在搜索空間內(nèi)隨機生成N個粒子組成初始種群，表示為NP；

步驟3 利用對立學習機制求解種群NP的對立種群NP′，計算合并種群NP∪NP′中的粒子適應度并按降序排列，選擇適應度排序前列的N個粒子構(gòu)成初始種群，表示為NP″；并記錄當前種群生成的最優(yōu)粒子x*(t)；

步驟4 若迭代次數(shù)t為奇數(shù)，種群NP″根據(jù)標準SCA算法執(zhí)行位置更新形成新種群(按適應度降序排列)，且根據(jù)式(3)更新振幅轉(zhuǎn)換因子r1；若迭代次數(shù)t為偶數(shù)，根據(jù)對立學習機制生成種群NP″的對立解，然后將原始種群NP″和對立種群合并(按適應度降序排列)，選擇適應度前N的粒子形成新種群；

步驟5 對步驟4中新生成的種群按精英概率prob選擇精英粒子，根據(jù)混沌搜索機制對精英個體變異；

步驟6 迭代是否達到Tmax，若滿足，返回步驟4；否則，輸出種群最優(yōu)個體(最優(yōu)解)。

COLSCA算法的時間復雜度。令種群規(guī)模為N，粒子維度為d，最大迭代次數(shù)為Tmax，COLSCA算法執(zhí)行主要由初始化、對立學習和混沌搜索3個部分組成。種群初始化和對立學習過程的時間復雜度均為O(N×d×Tmax)， 混沌搜索需要區(qū)分奇數(shù)迭代和偶數(shù)迭代兩種情形，并按概率對精英粒子進行變異，因此，該過程的最差時間復雜度也為O(N×d×Tmax)。 綜上結(jié)果，COLSCA算法的最差時間復雜度為O(N×d×Tmax)， 這與標準SCA算法的時間復雜度是相同的，說明改進算法COLSCA在提高尋優(yōu)精度和收斂速度的同時，并未降低算法的運行效率。

3 利用改進正弦余弦算法COLSCA求解Kapur熵多閾值圖像分割

3.1 Kapur熵最大化的多閾值圖像分割模型

令圖像I具有L個灰度級，分割閾值TH={th1,th2,…,thnt} 可將圖像I分割為K個類別，表示為C1,C2,…,CK， 其中，nt=1,2,…,K-1，th1

(13)

令z為給定像素的灰度級，則0

Phz=hz/CP

(14)

(15)

每個閾值對應的圖像Kapur熵值為

(16)

(17)

…

(18)

每個類別的累積分布函數(shù)定義為

(19)

3.2 圖像分割算法設計

COLSCA算法以式(13)Kapur熵作為適應度函數(shù)，迭代對最優(yōu)分割閾值進行尋優(yōu)，具體思想是：利用COLSCA算法在給定圖像的灰度空間內(nèi)尋優(yōu)，根據(jù)式(13)定義的Kapur熵函數(shù)評估COLSCA算法中粒子的適應度優(yōu)劣，通過粒子的迭代尋優(yōu)，尋找使得Kapur熵值達到最大的分割閾值TH*，并以TH*做圖像分割。以下是算法具體步驟：

步驟1 讀取待分割圖像I，生成圖像灰度直方圖；

步驟2 算法參數(shù)初始化；

步驟3 生成初始種群。粒子位置矢量代表圖像的灰度值組合，將矢量中的分量約定為遞增序列，分量范圍為灰度組范圍，即[0,255]，表示圖像分割閾值；

步驟4 以Kapur熵函數(shù)作為適應度函數(shù)，執(zhí)行COLSCA算法的尋優(yōu)過程；

步驟5 判斷算法迭代是否達到Tmax，若未達到，返回步驟4；否則，輸出種群最優(yōu)粒子，即代表分割的最優(yōu)閾值TH*；

步驟6 以步驟5生成的最優(yōu)閾值TH*做圖像分割，并評估分割圖像質(zhì)量。

4 實驗分析

4.1 實驗環(huán)境和參數(shù)配置

實驗分兩組進行。第一組：驗證COLSCA算法的尋優(yōu)性能，利用表1所示的基準函數(shù)進行測試，4個基準函數(shù)即為需要尋優(yōu)最優(yōu)解的目標函數(shù)，搜索空間為尋優(yōu)時粒子的尋優(yōu)范圍，fmin為函數(shù)理論可達的最優(yōu)值。f1(x)、f2(x) 是單峰函數(shù)，f3(x)、f4(x) 是多峰函數(shù)，單峰函數(shù)在整個搜索區(qū)間內(nèi)只有一個極值點，利于探測算法求解精度；而多峰函數(shù)在整個搜索區(qū)間內(nèi)呈現(xiàn)多個谷底，有多個極值點，利于探測算法是否能夠跳離局部最優(yōu)解，而繼續(xù)搜索其它區(qū)域。第二組：為了驗證COLSCA算法優(yōu)化Kapur熵最大化多閾值圖像分割求解問題上的性能，利用圖1中的6幅伯克利圖庫中的經(jīng)典圖像Lena、Butterfly、Hunter、Cameraman、Mandrill和Jet作為測試對象，并分別進行雙閾值、三閾值、四閾值和五閾值圖像分割實驗。算法參數(shù)中，最大迭代數(shù)Tmax=500，振幅調(diào)節(jié)系數(shù)ζ=2，a的初值astart=2，終值aend=0，種群精英粒子占比prob=20%，混沌系數(shù)μ=4，種群規(guī)模N=30。實驗在Matlab R2015b平臺下進行，操作系統(tǒng)為Win10 OS，CPU主頻率為2.8 GHz，內(nèi)存容量為8 GB。選擇灰狼優(yōu)化算法GWO的多閾值圖像分割算法[7]、改進正余弦算法ISCA的多閾值圖像分割算法[13]及融入混沌與對立學習機制的改進正余弦算法COLSCA優(yōu)化的多閾值圖像分割算法進行性能對比。

表1 基準函數(shù)

圖1 測試圖像

4.2 圖像分割的評估指標

利用峰值信噪比PSNR、結(jié)構(gòu)相似度SSIM和特征相似度FSIM這3個指標評估分割圖像性能

(20)

(21)

其中，R、I分別表示大小為M×N的原始圖像和分割圖像。對于分割圖像，PSNR值越大，分割圖像質(zhì)量越好

(22)

其中，ρR、δR分別表示原始圖像的像素均值和方差，ρI、δI分別表示分割圖像的像素均值和方差，δRI表示原始圖像與分割圖像間的協(xié)方差，R1、R2為常量，實驗中設置R1=R2=6.5025。對于分割圖像，SSIM值越大，分割性能越好

(23)

其中

SL(x)=SPC(x)SG(x)

(24)

(25)

(26)

PCm(x)=max{PC1(x),PC2(x)}

(27)

其中，Ω表示全部圖像空間域，SL(x) 表示圖像相似性，SPC(x) 表示圖像的特征相似性，SG(x) 表示圖像的梯度相似性，T1、T2為常量，實驗中設置T1=0.85，T2=160，G1(x)、G2(x) 分別表示參考圖像和被測試圖像的梯度幅值，PC1(x)、PC2(x) 表示參考圖像和被測試圖像的相位一致性。對于分割圖像，F(xiàn)SIM值越大，性能越好。

4.3 實驗結(jié)果分析

第一組實驗結(jié)果的分析。

表2統(tǒng)計了在30次實驗中GWO算法、標準SCA算法、ISCA算法以及本文的COLSCA算法在4種基準函數(shù)上尋優(yōu)得到的函數(shù)均值、標準方差、最小值和最大值?；鶞屎瘮?shù)中f1(x)、f2(x)是單峰函數(shù)，f3(x)、f4(x)是多峰函數(shù)。前者由于整個搜索區(qū)間內(nèi)只有一個極值點，所以可以測試算法收斂速度和求解精度；而后者在整個搜索區(qū)間內(nèi)呈現(xiàn)多個谷底，有多個極值點(局部最優(yōu)解)，所以更加利于測試算法跳離局部最優(yōu)解的能力。均值和標準方差可以同步觀察算法的尋優(yōu)精度和穩(wěn)定性。結(jié)果表明，COLSCA算法在兩類基準函數(shù)測試中的尋優(yōu)精度和穩(wěn)定性都是最好的，如在單峰Schwefel1.2函數(shù)中可以比對比算法提升平均約5個數(shù)量級，在多峰Rastigin函數(shù)中可以平均提升約8個數(shù)量級，這說明COLSCA算法引入的混沌搜索與對立學習機制對標準SCA算法中的搜索與開發(fā)的均衡、提升收斂速度和尋優(yōu)精度的改進是有效可行的。

表2 算法在基準函數(shù)上得到的統(tǒng)計結(jié)果對比

圖2是算法的尋優(yōu)收斂曲線。可見，本文的COLSCA算法可以在所有基準函數(shù)上最快收斂在最優(yōu)精度上，具有最快的收斂速度。與此同時，無論是針對單峰函數(shù)或是多峰函數(shù)，算法都能穩(wěn)定取得最佳性能。同時，對于多峰函數(shù)來說，由于存在多個波峰點，極其考察算法的拓展能力。圖中結(jié)果表明，COLSCA算法可以脫離局部最優(yōu)點。

圖2 收斂曲線

第二組實驗結(jié)果的分析。

圖3～圖8是COLSCA算法優(yōu)化Kapur熵的多閾值圖像分割結(jié)果，圖中分別展示了雙閾值、三閾值、四閾值和五閾值圖像分割結(jié)果。依據(jù)分割結(jié)果可知，分割閾值數(shù)越大，越能顯示原圖像目標對象和區(qū)域邊緣，這表明分割圖像中的灰度信息更加豐富。

圖3 COLSCA算法對Lena圖像進行雙閾值、三閾值、四閾值和五閾值的圖像分割效果

圖4 COLSCA算法對Butterfly圖像進行雙閾值、三閾值、四閾值和五閾值的圖像分割效果

表3是不同算法在求解Lena圖像、Butterfly圖像、Hunter圖像分割時得到的最優(yōu)分割閾值。明顯地，若分割閾值數(shù)較少，算法所選取的分割閾值區(qū)別不大，基本保持一致。但隨著分割閾值數(shù)的增加，算法求解的分割閾值顯現(xiàn)出不同。然而， COLSCA算法是否能夠求解更優(yōu)的閾值此時還無法判斷，因此，繼續(xù)引用峰值信噪比PSNR、結(jié)構(gòu)相似度SSIM和特征相似度FSIM這3個定理指標對算法的分割效果做一步對比分析。

圖5 COLSCA算法對Hunter圖像進行雙閾值、三閾值、四閾值和五閾值的圖像分割效果

圖6 COLSCA算法對Cameraman圖像進行雙閾值、三閾值、四閾值和五閾值的圖像分割效果

圖7 COLSCA算法對Mandrill圖像進行雙閾值、三閾值、四閾值和五閾值的圖像分割效果

圖8 COLSCA算法對Jet圖像進行雙閾值、三閾值、四閾值和五閾值的圖像分割效果

表4、表5、表6和表7分別是算法進行多閾值圖像分割時得到的PSNR、SSIM、FSIM及算法計算時間表現(xiàn)。綜合結(jié)果可以看出，在分割閾值選取越多時，圖像失真更少、圖像一致性保留更加完整，圖像分割越準確，所以PSNR、SSIM、FSIM這3個指標均會遞增。對比之下，本文的COLSCA算法可以進行閾值分割得到的PSNR、SSIM、FSIM這3個指標值是最高的，說明在COLSCA算法中采用的非線性對數(shù)振幅參數(shù)調(diào)整機制、混沌搜索精英個體變機制以及對立學習機制對改進SCA算法的尋優(yōu)精度是有效可行的。此外，由于分割閾值量較少，算法的分割閾值選取相差并不大，所以此時3個指標上相差也不大。但隨著分割閾值量的增加，算法差距逐步體現(xiàn)，說明在多閾值情形下，COLSCA算法所得到的閾值更加能夠準確做出圖像分割。

表3 分割閾值

表4 PSNR

表7表明，增加分割閾值量，會增加算法的計算時間，這是由于算法在尋優(yōu)空間上的維度增加所導致的。此外，當閾值量較少時，COLSCA算法的計算時間會略高于其它算法，但并不明顯。分割閾值量增加后，COLSCA算法的計算效率穩(wěn)步提升，說明COLSCA算法在尋優(yōu)精度和收斂速度上的改進可以提升圖像分割效率。

為了驗證COLSCA算法在標準SCA算法上所做改進工作的有效性，本節(jié)比較分別利用COLSCA算法和標準SCA算法進行Kapur熵多閾值圖像分割后的PSNR值在顯著性水平為5%的情況下，進行Wilcoxon秩和檢驗的結(jié)果。

建立假設條件為：H0：定義COLSCA算法和標準SCA算法進行圖像分割后得到的PSNR值沒有明顯差異；H1：定義COLSCA算法和標準SCA算法進行圖像分割后得到的PSNR值存在顯著差異。

表5 SSIM

表8為Wilcoxon秩和檢驗結(jié)果?？梢?，P值均小于5%，表明結(jié)果拒絕H0，接受H1，COLSCA算法相對SCA算法得到的PSNR值具有顯著性差異，不具偶然性，說明COLSCA算法所做改進是有效的。

圖9、圖10和圖11是算法在Lena圖像、Butterfly圖像、Hunter圖像上進行四閾值分割時得到的適應度。COLSCA算法具有更快的收斂速度，基本在30次迭代之后即可得到最優(yōu)適應度，這說明此時的Kapur熵值更大，對應其分割閾值更加精確，也進一步驗證將本文設計的融合混沌搜索與對立學習機制的改進正余弦算法COLSCA應用于圖像分割問題的可行性。

表6 FSIM

表7 算法計算時間

表8 Wilcoxon秩和檢驗值

圖9 Lena圖像適應度收斂曲線

圖10 Butterfly圖像適應度收斂曲線

圖11 Hunter圖像適應度收斂曲線

5 結(jié)束語

本文提出了一種融入混沌與對立學習機制的改進正余弦算法COLSCA，并利用該算法對Kapur熵最大化的多閾值圖像分割問題進行了求解。利用伯克利圖像對COLSCA算法的閾值尋優(yōu)準確性和尋優(yōu)效率進行了實驗分析，驗證該算法可以有效提升圖像分割精度和分割效率，說明COLSCA算法所做的工作在提升算法的全局搜索與局部開發(fā)間的均衡、避免局部最優(yōu)解方面具有良好的效果，可以增強算法的尋優(yōu)精度和收斂速度。今后的研究工作將進一步將圖像分割實驗擴展至其它領(lǐng)域，如醫(yī)學圖像中的MRI圖像、紅外圖像等，進一步驗證算法的尋優(yōu)能力。