改進(jìn)烏鴉算法的二維Tsallis熵多閾值圖像分割算法

常君杰，李東興，鐘欣，杜文漢，王倩楠

(山東理工大學(xué) 機(jī)械工程學(xué)院，山東 淄博 255049)

圖像分割是指把圖像分成具有不同特性的各個(gè)區(qū)域，提取出所需目標(biāo)的過(guò)程[1]。閾值法因簡(jiǎn)單、高效，在圖像分割領(lǐng)域應(yīng)用廣泛[2]。近幾年，閾值分割方法大都與熵結(jié)合使用，Tsallis熵受非廣延統(tǒng)計(jì)物理的啟發(fā)，通過(guò)引入?yún)?shù)q來(lái)度量系統(tǒng)的不可擴(kuò)展性[3-4]。Sahoo等[5]提出了基于二維Tsallis熵的圖像閾值分割方法，充分利用了圖像的灰度分布、空間鄰域分布等信息，分割效果好，但存在速度慢、計(jì)算時(shí)間長(zhǎng)的缺點(diǎn)。

為加快閾值選取速度，人們將啟發(fā)式優(yōu)化算法與熵結(jié)合，用于圖像分割，取得了較好的效果[6]。文獻(xiàn)[7]將螢火蟲算法(firefly algorithm, FA)與二維熵結(jié)合對(duì)圖像進(jìn)行快速分割，減少了運(yùn)行時(shí)間，但需設(shè)置的參數(shù)多，適用性不強(qiáng)；文獻(xiàn)[8]利用自適應(yīng)布谷鳥算法和二維最大類間方差法進(jìn)行閾值分割，進(jìn)一步縮短運(yùn)行時(shí)間，卻易陷入局部最優(yōu)；文獻(xiàn)[9]將烏鴉搜索算法用于多閾值圖像分割，需設(shè)置的參數(shù)少，容易實(shí)現(xiàn)，可沿較優(yōu)路徑搜索，但傳統(tǒng)烏鴉算法位置更新策略為個(gè)體隨機(jī)搜索，存在盲目性，導(dǎo)致烏鴉算法收斂速度慢和易陷入局部最優(yōu)[10]。

針對(duì)烏鴉算法存在的問(wèn)題，本文提出改進(jìn)烏鴉算法優(yōu)化二維Tsallis熵多閾值圖像分割法，利用Levy飛行策略優(yōu)化烏鴉搜索算法，將改進(jìn)烏鴉搜索算法與二維Tsallis熵結(jié)合用于圖像分割，以提高二維Tsallis熵多閾值圖像分割效率和精度。

1 烏鴉搜索算法及其改進(jìn)

1.1 烏鴉搜索算法

烏鴉搜索算法(crow search algorithm, CSA)由Askarzadeh[11]提出，是一種基于烏鴉覓食過(guò)程的智能算法。烏鴉i為了獲取更多食物，會(huì)跟蹤其他烏鴉j并偷取食物，若烏鴉j發(fā)現(xiàn)被跟蹤，則會(huì)隨機(jī)飛行迷惑跟蹤者i，保護(hù)食物不被發(fā)現(xiàn)。烏鴉i的位置可表示為

xi,iter+1=

(1)

式中：ri、rj是0和1之間的隨機(jī)數(shù)；iter表示當(dāng)前迭代次數(shù)；mi,iter表示烏鴉i記憶中最優(yōu)的位置；xi,iter表示烏鴉i當(dāng)前位置；fli,iter表示飛行長(zhǎng)度；APj,iter是迭代時(shí)j的感知概率。

更新mi,iter的公式為

(2)

式中f(·)表示適應(yīng)度函數(shù)。

1.2 改進(jìn)的烏鴉搜索算法

CSA具有結(jié)構(gòu)簡(jiǎn)單、易于實(shí)現(xiàn)的優(yōu)點(diǎn)，已成功應(yīng)用于配電網(wǎng)導(dǎo)體選擇[12]、極限學(xué)習(xí)機(jī)參數(shù)優(yōu)化[13]等多個(gè)領(lǐng)域。但傳統(tǒng)烏鴉算法位置更新策略存在個(gè)體隨機(jī)搜索、具有一定盲目性的問(wèn)題，導(dǎo)致烏鴉算法收斂速度慢和易陷入局部最優(yōu)。

1.2.1 Levy飛行機(jī)制

Levy飛行是一種隨機(jī)步長(zhǎng)服從Levy分布的方法，具有隨機(jī)游走、隨機(jī)發(fā)現(xiàn)的特性[14]。利用Levy飛行優(yōu)化CSA，可以在擴(kuò)大算法的搜索范圍、保持局部搜索能力的同時(shí)，有效避免算法陷入局部最優(yōu)。其冪次形式為

levy(λ)～|s|-λ，1<λ<3。

(3)

本文采用Mantegna提出的Levy步長(zhǎng)公式[15]

(4)

(5)

式中δμ、δν定義為

(6)

其中Γ為標(biāo)準(zhǔn)Gamma函數(shù)。

1.2.2 自適應(yīng)Levy飛行策略優(yōu)化烏鴉搜索算法

利用自適應(yīng)Levy飛行策略對(duì)烏鴉的位置進(jìn)行更新,即

xi,iter+1=

(7)

式中：⊕表示點(diǎn)乘積；α(iter)為自適應(yīng)尺度系數(shù)，且

(8)

其中β是限制因子，通常為大于1的數(shù)。圖1為不同β時(shí)α(iter)的變化曲線。圖1表明，不同的β值均能使α(iter)滿足在前期保持一個(gè)相對(duì)較大的初值，并隨迭代進(jìn)行逐漸減小的條件，且隨β值增大，α(iter)后期衰減速率越快，效果越好；但β值的增大使算法計(jì)算量增加，影響算法的實(shí)時(shí)性。通過(guò)大量實(shí)驗(yàn)驗(yàn)證可知，β=3時(shí)可以使α(iter)有較快衰減速率的同時(shí)保證算法的實(shí)時(shí)性。

由計(jì)算所得的軸承靜載荷及動(dòng)載荷,選取軸承型號(hào)為22310C/W33,其額定動(dòng)載荷為175 kN,靜載荷為210 kN,滿足要求.

圖1 尺度系數(shù)變化圖

圖1顯示，α(iter)的變化是非線性的，在算法初期，迭代次數(shù)較少，α(iter)在較長(zhǎng)的時(shí)間內(nèi)保持較大的值，使得Levy飛行以較大步長(zhǎng)進(jìn)行搜索，全局搜索能力較強(qiáng)，便于找到近似的全局最優(yōu)解；算法運(yùn)行后期，解接近最優(yōu)解時(shí)，α(iter)的值急劇減小，自適應(yīng)縮小搜索步長(zhǎng)，利于在最優(yōu)解附近精細(xì)搜索，加速算法收斂。

傳統(tǒng)CSA中，當(dāng)rj

2 改進(jìn)CSA優(yōu)化Tsallis熵分割算法

2.1 二維多閾值Tsallis熵分割算法

假設(shè)I(x,y)為待處理圖像，用n個(gè)灰度級(jí)閾值(s1,t1)，…，(sn,tn)將I(x,y)的二維直方圖P(i,j)劃分為n+1個(gè)類{A1,A2,...,An+1}，如圖2所示。

圖2 二維多閾值直方圖

目標(biāo)區(qū)Ak中灰度級(jí)所對(duì)應(yīng)的概率為

(9)

2.2 改進(jìn)CSA優(yōu)化Tsallis熵分割算法

傳統(tǒng)二維Tsallis熵多閾值分割采用窮舉的搜索模式，設(shè)圖像的灰度級(jí)數(shù)為L(zhǎng)，閾值個(gè)數(shù)為n，則時(shí)間復(fù)雜度為O(L2n)，復(fù)雜度隨著閾值數(shù)的增加呈指數(shù)級(jí)增長(zhǎng)[17]。本文提出改進(jìn)CSA的二維Tsallis熵多閾值圖像分割方法，把分割閾值選擇的問(wèn)題轉(zhuǎn)變?yōu)楦倪M(jìn)CSA對(duì)二維Tsallis熵函數(shù)Sq((s1,t1),(s2,t2),...，(sn,tn))的尋優(yōu)問(wèn)題。設(shè)算法的種群規(guī)模為N，問(wèn)題維度為n，迭代次數(shù)為itermax，則算法的整體復(fù)雜度為O(itermax×N×n)，遠(yuǎn)遠(yuǎn)小于O(L2n)，因此改進(jìn)算法能在較短時(shí)間內(nèi)給出可行解或者近似最優(yōu)解。

改進(jìn)CSA的二維Tsallis熵多閾值圖像分割算法流程圖如圖3所示，具體步驟如下：

圖3 多閾值分割流程

步驟1：初始化基本參數(shù)，即種群數(shù)量N、最優(yōu)閾值向量的維數(shù)n(根據(jù)選取的閾值個(gè)數(shù)確定)、感知概率AP、飛行長(zhǎng)度f(wàn)l及最大迭代次數(shù)itermax；

步驟2：隨生成N只烏鴉的初始位置，算法初期由于烏鴉都沒(méi)有“記憶位置”，所以令mi=xi；

步驟3：利用式(7)對(duì)烏鴉位置x進(jìn)行更新，并計(jì)算新位置的適應(yīng)度；

步驟4：根據(jù)式(2)更新記憶位置m，若f(xi,iter+1)≥f(mi,iter)，則mi,iter=xi,iter+1，否則保持不變；

步驟5：判斷是否滿足條件，若未滿足最大迭代次數(shù)，回到步驟3，反之繼續(xù)進(jìn)行步驟6；

步驟6：輸出最優(yōu)閾值(s*,t*)，并以此分割圖像。

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

為驗(yàn)證改進(jìn)CSA在圖像分割效果和計(jì)算時(shí)間上的優(yōu)越性，本文將Lena和Peppers典型圖像作為實(shí)驗(yàn)對(duì)象進(jìn)行多閾值圖像分割。通過(guò)大量實(shí)驗(yàn)驗(yàn)證，本文選取參數(shù)種群規(guī)模N=20，最大迭代次數(shù)itermax=100,感知概率AP=0.4，飛行步長(zhǎng)fl=2。

3.1 多閾值圖像分割實(shí)驗(yàn)

用改進(jìn)CSA對(duì)Lena圖進(jìn)行二維Tsallis熵的分割，分割結(jié)果如圖4所示。從圖4中可以看出，采用單閾值分割圖像時(shí)，分割結(jié)果粗糙，背景中的細(xì)節(jié)被忽略，頭發(fā)細(xì)節(jié)處分割模糊；采用二閾值分割時(shí)，背景中被忽略的細(xì)節(jié)有所體現(xiàn)，但帽子處的分割效果不理想；采用三閾值分割時(shí)，分割效果較好，分割結(jié)果清晰，局部細(xì)節(jié)好。因此，本文算法能有效分割復(fù)雜圖像，且隨閾值的增加，分割效果越好，得到的有用信息越多。

(a) 原圖 (b) 單閾值

為進(jìn)一步驗(yàn)證改進(jìn)CSA的性能，將改進(jìn)CSA與文獻(xiàn)[7]中的FA和文獻(xiàn)[9]中的經(jīng)典CSA進(jìn)行二維Tsallis熵分割對(duì)比實(shí)驗(yàn)，對(duì)Peppers圖像進(jìn)行分割，以閾值n=3為例，分割結(jié)果如圖5所示。

(a) 原圖 (b) FA結(jié)果

從圖5中可以看出，F(xiàn)A分割后青椒上的細(xì)節(jié)嚴(yán)重丟失，傳統(tǒng)CSA分割后局部區(qū)域過(guò)亮和過(guò)暗，分割效果不理想；改進(jìn)CSA分割后圖像局部細(xì)節(jié)明顯好于其他2種算法，展現(xiàn)的信息更為清晰，分割效果更好。

3.2 分割性能對(duì)比

為定量分析3種算法的性能，采用峰值信噪比(peak signal to noise ratio, PSNR[18])與結(jié)構(gòu)相似性 (structural similarity index, SSIM[19])對(duì)分割后圖像的性能進(jìn)行比較?；叶葓D像x(i,j)及閾值分割后圖像y(i,j)的PSNR定義為

(10)

式中：

(11)

通常分割效果越好，PSNR值越大。

SSIM用來(lái)衡量?jī)煞鶊D像的相似度。原始圖像x與分割后的圖像y的結(jié)構(gòu)相似性可按照下式求出：

(12)

表1中數(shù)據(jù)顯示，當(dāng)閾值個(gè)數(shù)為1時(shí)，各算法均順利找到了最佳閾值，分割效果相近。但當(dāng)閾值個(gè)數(shù)為2、3時(shí)，本文算法的優(yōu)勢(shì)體現(xiàn)出來(lái)，分割結(jié)果更加準(zhǔn)確。以3閾值為例，本文算法分割Peppers圖像后的PSNR較FA與傳統(tǒng)CSA分別提高了12.68%、4.41%；SSIM分別提高了15.58%、12.73%。因此，相較對(duì)比算法，改進(jìn)后CSA在分割精度上具有明顯優(yōu)勢(shì)。

表1 閾值、PSNR及SSIM的對(duì)比

為了直觀反映3種算法的收斂過(guò)程，在itermax=100，n=3的情況下，繪制出Peppers圖的收斂曲線，如圖6所示。表2為不同算法在不同閾值條件下的分割結(jié)果。

圖6 Peppers收斂過(guò)程圖

從圖6中可以看出,FA和傳統(tǒng)CSA分別在第18次、第22次進(jìn)行局部精細(xì)求解，陷入局部最優(yōu)，雖最終均跳出了局部最優(yōu)，但迭代次數(shù)增加，收斂速度較慢。表2中數(shù)據(jù)顯示，對(duì)Peppers圖像進(jìn)行3閾值分割時(shí)，改進(jìn)算法在第35次迭代時(shí)已經(jīng)收斂到最優(yōu)值，明顯早于其他算法，且算法運(yùn)行時(shí)間最短，F(xiàn)A與傳統(tǒng)CSA所用時(shí)間分別是改進(jìn)算法的2.76倍、1.14倍。

表2 適應(yīng)度值、運(yùn)性時(shí)間以及迭代次數(shù)的對(duì)比

綜合圖6與表2中的數(shù)據(jù)可知：改進(jìn)后的CSA在運(yùn)行過(guò)程中未陷入局部最優(yōu)，迭代次數(shù)少、收斂速度快，且收斂后的目標(biāo)函數(shù)值遠(yuǎn)高于其他2種算法；改進(jìn)后的CSA能較好地引導(dǎo)個(gè)體趨于全局最優(yōu)解，相較其他2種算法在收斂速度以及分割精度上都有明顯改善。

4 結(jié)論

1)建立了一種自適應(yīng)Levy飛行搜索策略。利用Levy飛行隨機(jī)游走的特性幫助CSA跳出局部最優(yōu)，設(shè)置尺度系數(shù)自適應(yīng)地限制Levy飛行搜索步長(zhǎng)，平衡算法的全局尋優(yōu)能力和局部精細(xì)求解能力，加速算法收斂。

2)利用改進(jìn)烏鴉搜索算法優(yōu)化二維Tsallis熵多閾值圖像分割，能減少計(jì)算量，提高運(yùn)算效率，大大縮短分割時(shí)間。

3)將FA、傳統(tǒng)CSA與本文算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示，改進(jìn)CSA較其他算法分割清晰，細(xì)節(jié)特征保留完好，收斂速度快，計(jì)算時(shí)間短，不易陷入局部最優(yōu)，PSNR與SSIM值均高于其他2種算法，驗(yàn)證了改進(jìn)CSA算法的有效性。