柳長(zhǎng)安，馮雪菱，孫長(zhǎng)浩，趙麗娟

(華北電力大學(xué) 控制與計(jì)算機(jī)工程學(xué)院，北京 102206)

引 言

圖像分割是圖像處理的關(guān)鍵步驟[1]，分割依據(jù)主要包括閾值[2-3]、區(qū)域[4-5]、邊緣[6-7]。閾值分割原理是根據(jù)某種規(guī)則求出最優(yōu)閾值，根據(jù)最優(yōu)閾值進(jìn)行分割，因其性能相對(duì)穩(wěn)定且實(shí)現(xiàn)簡(jiǎn)單而得到廣泛使用。1979年提出的Otsu法只考慮了灰度信息。后來提出的最大Kapur熵分割法優(yōu)于Ostu算法，但抗噪性較差[8]。除了Kapur熵，一些學(xué)者引入交叉熵[9]、Renyi熵[10]等進(jìn)行圖像分割,雖然提升了圖像分割質(zhì)量，但是1維分割方法性能提升有限。LIU等人[11]針對(duì)1維分割精度較低的情況提出2維Otsu算法，考慮像素鄰域信息，改善了1維Otsu算法性能。ABUTALEB[12]提出2維最大熵方法，在分割性能上優(yōu)于1維最大熵分割方法，但是大大增加運(yùn)算時(shí)間。

群體智能優(yōu)化算法以其獨(dú)特的生物群體行為生存方式，提供了更多優(yōu)化問題的新思路。自“群體智能”概念被首次提出，眾多學(xué)者提取生物種群特征，凝練出新的群智能優(yōu)化算法。隨著近些年群體智能優(yōu)化算法的蓬勃發(fā)展，群體智能算法廣泛應(yīng)用于解決參量最優(yōu)化問題上，其中包括蟻群算法(ant colony optimization,ACO)[13]與粒子群算法(particle swarm algorithm,PSO)[14]兩大經(jīng)典優(yōu)化算法，以及螢火蟲算法(firefly algorithm，F(xiàn)A)[15]、灰狼算法(grey wolf optimization，GWO)[16]、蟻獅算法(ant lion optimizer,ALO)[17]、鯨魚算法(whale optimization algorithm，WOA)[18]、正弦余弦算法(sine cosine algorithm,SCA)[19]等新型優(yōu)化算法。

受麻雀在自然中覓食策略的啟發(fā)，2020年,XUE等人提出麻雀搜索算法(sparrow search algorithm，SSA)[20]。SSA算法相比其它算法具有穩(wěn)定性較高、收斂精度較好和一定程度上避免陷入局部最優(yōu)等優(yōu)點(diǎn)，但是SSA算法收斂速度較快容易導(dǎo)致陷入局部最優(yōu)解的情況，依然有概率得到不可行解。因此,本文中提出了基于精英反向的改進(jìn)型t分布麻雀算法(improvedt-distribution SSA,ITSSA)，加強(qiáng)麻雀粒子之間的交流，加快算法收斂速度，同時(shí)使用精英反向?qū)W習(xí)策略保證麻雀種群均勻性并且增強(qiáng)全局搜索的能力，引入t分布算法前期增加全局搜索能力，后期增加局部尋優(yōu)能力，采用螢火蟲算法，進(jìn)一步增加種群多樣性。將ITSSA算法應(yīng)用于最大2維熵分割中，實(shí)驗(yàn)表明，此方法可提高圖像分割實(shí)時(shí)性，在峰值信噪比和特征相似度上得到極大提升。

1 麻雀搜索算法

SSA是一種新型的群體智能優(yōu)化算法，每只麻雀位置對(duì)應(yīng)一個(gè)解，更新方式可分為向當(dāng)前最優(yōu)位置靠近和向原點(diǎn)靠近。作為群居鳥類的麻雀，與其它鳥類相比，具有聰明且記憶力強(qiáng)的特點(diǎn)。麻雀搜索算法通過麻雀搜索食物和反捕食操作進(jìn)行參量?jī)?yōu)化，初始位置用以下矩陣表示：

式中，n是麻雀的個(gè)數(shù)，d是待優(yōu)化變量的維度。第i只麻雀位置為Xi=[xi,1,…,xi,j…,xi,d]。麻雀的適應(yīng)度表示如下：

式中，f(Xi)表示麻雀?jìng)€(gè)體的適應(yīng)度。

麻雀群體分為3種角色：發(fā)現(xiàn)者、追隨者、警戒者。發(fā)現(xiàn)者通常負(fù)責(zé)整個(gè)麻雀群體食物來源的尋找并且為加入的追隨者提供覓食方向。當(dāng)報(bào)警值大于安全值，發(fā)現(xiàn)者將追隨者帶到安全區(qū)域。在每次迭代中，發(fā)現(xiàn)者的位置更新如下：

式中，R是當(dāng)前迭代次數(shù)，Rmax是最大迭代次數(shù)，α1是(0,1]范圍的隨機(jī)數(shù)，Q是服從正態(tài)分布的隨機(jī)數(shù)，L是各元素都為1的1行多維矩陣。Ra∈[0,1]和Rs∈[0.5,1.0]分別代表預(yù)警值和安全閾值。

在每次迭代中，追隨者位置更新如下：

式中，Xb和Xw分別表示最優(yōu)位置和最劣位置，A是元素為1或-1的1行多維矩陣。

隨機(jī)產(chǎn)生麻雀群體的警戒者，占整個(gè)麻雀群體的10%～20%，其位置更新如下：

Xi(R+1)=

式中，β1是步長(zhǎng)控制參量，服從(0,1)的正態(tài)分布；α2是[-1,1]范圍的隨機(jī)數(shù)；β2是最小常數(shù)，避免當(dāng)fn=fb時(shí)，分母為0的情況發(fā)生。fn,fb和fw分別代表當(dāng)前適應(yīng)度、最佳適應(yīng)值和最劣適應(yīng)度。

2 融合自適應(yīng)t分布的多策略麻雀搜索算法

2.1 自適應(yīng)t分布

t分布[21]又稱為學(xué)生分布，其曲線形態(tài)和自由度參量k有關(guān)，概率密度函數(shù)如下：

當(dāng)k=1時(shí)，t分布為柯西分布；當(dāng)k→∞時(shí)，t分布為高斯分布。t分布融合柯西分布和高斯分布的特點(diǎn)，在算法運(yùn)行過程中通過改變k的值可以獲得不同的變異幅度。在算法運(yùn)行的初始階段，t分布因?yàn)閗值較小近似于柯西分布變異，t分布具有較強(qiáng)的全局探索能力；在算法運(yùn)行的中間階段，t分布從柯西分布變異向高斯分布變異逐漸過渡，結(jié)合兩者優(yōu)勢(shì)；在算法運(yùn)行后期，t分布因?yàn)閗值較大近似于高斯分布，t分布具有較強(qiáng)的局部搜索能力，有利于算法高效找到全局極值點(diǎn)。

本文中采用自適應(yīng)t分布變異，第i個(gè)體原位置Xi變異公式如下：

XiT=Xi+ζ·t(R)

(7)

式中，XiT代表t變異后個(gè)體位置，ζ代表自適應(yīng)因子，t(R)為以當(dāng)前迭代次數(shù)R為參量的t分布。

2.2 精英反向?qū)W習(xí)策略

反向?qū)W習(xí)策略(opposition-based learning,OBL)[22]已被證實(shí)可以有效提高智能優(yōu)化算法搜索能力，提高近50%找到全局最優(yōu)解的概率，其主要思想是求問題可行解的反向解，對(duì)原可行解和反向解進(jìn)行評(píng)估，選出更優(yōu)解作為下一代個(gè)體。精英反向?qū)W習(xí)(elite opposition-based learning,EOBL)利用精英個(gè)體包含更多信息的特點(diǎn)，構(gòu)造當(dāng)前種群的反向種群，選取當(dāng)前種群和反向種群中更優(yōu)質(zhì)的個(gè)體作為初始解。設(shè)當(dāng)前群體的精英個(gè)體位置為:

Xi′=[xi,1′,…,xi,j′,…,xi,d′]

(8)

則精英個(gè)體的反向解為:

Xi′*=α3[min(xi,j′)+max(xi,j′)]-Xi′

(9)

式中，α3是(0,1)范圍的隨機(jī)數(shù)。利用隨機(jī)生成的α3值可以生成多個(gè)精英反向解，如果生成的反向解超出上下邊界值，則重置反向解。

2.3 螢火蟲算法

螢火蟲算法[15]模擬螢火蟲發(fā)光行為，亮度弱的螢火蟲受亮度強(qiáng)的螢火蟲吸引，進(jìn)行移動(dòng)從而更新位置得到新的位置，亮度強(qiáng)的螢火蟲進(jìn)行擾動(dòng)操作。螢火蟲亮度L和吸引力r如下式所示：

式中，f(Xi)代表第i只螢火蟲適應(yīng)度值,也是其亮度，γmax代表螢火蟲間的最大吸引度,μ是光強(qiáng)系數(shù)，lA,B表示兩個(gè)螢火蟲之間的距離。

當(dāng)螢火蟲A被螢火蟲B吸引時(shí)，螢火蟲A的位置如下式：

XA=XA+γ×(XA-XB)+λ(α4-0.5)

(11)

式中，XA和XB分別表示螢火蟲A和螢火蟲B的位置。λ∈[0,1]為步長(zhǎng)因子，α4為(0,1)服從均勻分布的隨機(jī)數(shù)。

最亮螢火蟲S的位置更新公式如下：

XS=XS+λ(α4-0.5)

(12)

式中，XS表示最亮螢火蟲的位置，(12)式讓螢火蟲一定程度上避免過早陷入局部最優(yōu)。

2.4 融合自適應(yīng)t分布的多策略麻雀搜索算法

針對(duì)麻雀算法的不足，首先利用反向?qū)W習(xí)策略生成反向解加入種群，擴(kuò)大算法搜索范圍。將迭代次數(shù)作為t分布的自由度參量，增加種群多樣性，提高算法的全局探索能力和局部開發(fā)能力。與此同時(shí)，選擇多個(gè)最優(yōu)個(gè)體，利用精英反向?qū)W習(xí)策略選擇發(fā)現(xiàn)者，提高種群質(zhì)量，提高算法收斂速度。追隨者位置更新易受發(fā)現(xiàn)者位置更新情況影響，為進(jìn)一步提高收斂精度和尋優(yōu)效果，利用螢火蟲機(jī)制擾動(dòng)追隨者，改善爭(zhēng)奪覓食過程中易陷入全局優(yōu)化能力。在保留麻雀算法3種角色和競(jìng)爭(zhēng)機(jī)制的前提下，采取動(dòng)態(tài)策略，設(shè)置轉(zhuǎn)換概率p，將精英反向策略與螢火蟲算法和自適應(yīng)t分布變異在一定概率下交替執(zhí)行，動(dòng)態(tài)更新位置，改善基礎(chǔ)麻雀算法容易陷入局部最優(yōu)的缺陷，達(dá)到增強(qiáng)全局尋優(yōu)能力的目的，得到更優(yōu)質(zhì)的解。具體實(shí)現(xiàn)步驟如下。

(1)初始化參量：種群數(shù)量、最大迭代次數(shù)Rmax、轉(zhuǎn)換概率p、發(fā)現(xiàn)者比例Dp、警戒者比例Ds、警戒者預(yù)警值Rs等;(2)應(yīng)用第2.2節(jié)中的反向?qū)W習(xí)策略生成反向解加入麻雀初始種群，選取最優(yōu)個(gè)體作為最終的初始種群;(3)計(jì)算每只麻雀適應(yīng)度并排序;(4)應(yīng)用第2.2節(jié)中的反向?qū)W習(xí)選擇策略選擇發(fā)現(xiàn)者，其余作為追隨者，獲取精英麻雀動(dòng)態(tài)邊界，更新發(fā)現(xiàn)者和追隨者的位置,隨機(jī)選擇偵察警戒者，更新其位置;(5)計(jì)算并更新每只麻雀適應(yīng)度值;(6)判斷變異條件:若隨機(jī)數(shù)r∈[0,1]小于轉(zhuǎn)換概率p，則利用第2.1節(jié)中的自適應(yīng)t變異公式更新每只麻雀適應(yīng)度值；若r≥p,則應(yīng)用第2.2節(jié)中的精英反向策略更新發(fā)現(xiàn)者，應(yīng)用第2.3節(jié)中的螢火蟲算法擾動(dòng)追隨者，應(yīng)用原式更新警戒者的適應(yīng)度值;(7)對(duì)步驟(6)的越界個(gè)體做越界處理,比較新適應(yīng)度值和原值，若新適應(yīng)度值優(yōu)于原值，則更新位置和適應(yīng)度值，反之，則保留;(8)判斷當(dāng)前迭代次數(shù)R是否達(dá)到最大迭代次數(shù)，若是，則循環(huán)結(jié)束，輸出結(jié)果，反之，返回步驟(6)。

3 基于ITSSA的2維最大熵圖像分割

圖像分割的最佳閾值即為徹底分離目標(biāo)和背景的像素邊界?；谧畲箪氐拈撝捣指罘椒ň褪菍㈧刂底鳛槟繕?biāo)函數(shù)，讓圖像分割后的目標(biāo)區(qū)域和背景區(qū)域熵的和達(dá)到最大值。1維最大熵雖然處理速度較快，但是僅考慮自身像素的灰度信息，而忽略區(qū)域相關(guān)性，當(dāng)噪聲嚴(yán)重時(shí)，因此表現(xiàn)出較差的分割效果以及抗噪性能。2維最大熵應(yīng)運(yùn)而生，結(jié)合像素點(diǎn)和區(qū)域灰度特征，提取圖像有用信息。

2維最大熵[23-24]原理如下：假設(shè)輸入圖像大小為M×N，待分割圖像為I(x,y)，像素點(diǎn)8×8鄰域灰度均值為g(x,y),且1≤x≤M，1≤y≤N。設(shè)I(x,y)=u，g(x,y)=v，且1≤u,v≤L-1(灰度范圍L=256)。

式中，quv表示圖像值為u且區(qū)域灰度均值為v的像素點(diǎn)數(shù)頻率,puv是其對(duì)應(yīng)的概率[20]。

輸入圖像2維直方圖如圖1所示。

Fig.1 2-D histogram

區(qū)域1和區(qū)域2代表目標(biāo)和背景，區(qū)域3和區(qū)域4代表噪聲和邊界。假設(shè)分割的閾值為(s,t)，則區(qū)域1目標(biāo)區(qū)域和區(qū)域2背景區(qū)域概率分別為：

區(qū)域1和區(qū)域2的2維熵分別為：

定義分割圖像的2維熵函數(shù)為：

H=H1+H2

(16)

當(dāng)2維熵函數(shù)取最大值時(shí)，對(duì)應(yīng)的最優(yōu)分割閾值(s*,t*)應(yīng)滿足:

H(s*,t*)=max{H}

(17)

式中，0

為了解決2維閾值分割計(jì)算時(shí)間長(zhǎng)及傳統(tǒng)智能優(yōu)化算法常陷入局部最優(yōu)、收斂速度慢的問題，提出一種基于精英反向的自適應(yīng)t分布麻雀算法的2維最大熵圖像分割方法。

令I(lǐng)TSSA的適應(yīng)度函數(shù)為:

fITSSA=H

(18)

通過融合自適應(yīng)t分布的多策略麻雀搜索算法讓適應(yīng)度函數(shù)取最大值，此時(shí)的s值和t值為最優(yōu)解，即為圖像最優(yōu)分割閾值(s*,t*)。具體步驟如圖2所示。

Fig.2 Flow chart of maximum 2-D entropy based on ITSSA

4 實(shí)驗(yàn)仿真和結(jié)果分析

4.1 基準(zhǔn)函數(shù)測(cè)試

為了驗(yàn)證本文中算法的正確性和有效性，使用SCA,ALO,WOA,GWO,SSA和ITSSA分別測(cè)試15個(gè)基準(zhǔn)函數(shù)進(jìn)行比較，充分考察ITSSA算法的尋優(yōu)能力。各算法參量取值見表1，測(cè)試函數(shù)名稱及參量設(shè)置見表2。表1中，b是對(duì)數(shù)螺旋形狀常數(shù)，as是自適應(yīng)調(diào)整常數(shù)，ag是收斂因子。表2中，F(xiàn)1～F7為單峰函數(shù)；F8～F12為不定維多峰函數(shù)；F13～F15為固定維度多峰函數(shù)。其中，α5和α6為u函數(shù)的參量;φi和φi為φ數(shù)組和φ數(shù)組中i位置的數(shù)值;e為常數(shù)。單峰函數(shù)僅有一個(gè)極大值或極小值，用于檢驗(yàn)算法的收斂速度和精度，多峰函數(shù)具有多個(gè)局部或全局最優(yōu)解，用于檢驗(yàn)算法全局探索能力和開發(fā)能力。本文中仿真實(shí)驗(yàn)的運(yùn)行環(huán)境為Core i7 CPU、Windows 10操作系統(tǒng)，內(nèi)存為8GB，處理器速度為3.2GHz。算法在MATLAB R2020a軟件上運(yùn)行。在對(duì)比測(cè)試實(shí)驗(yàn)中，為保證實(shí)驗(yàn)結(jié)果的客觀，設(shè)置各算法種群數(shù)量均為50，最大迭代次數(shù)為100。

Table 1 Algorithm parameter value

Table 2 Benchmark functions

選取各算法在基準(zhǔn)函數(shù)獨(dú)立運(yùn)行20次的均值M和標(biāo)準(zhǔn)差D作為實(shí)驗(yàn)結(jié)果，其中均值反映算法尋優(yōu)能力和精度，標(biāo)準(zhǔn)差反映算法的魯棒性。

本文中的算法ITSSA與其它智能算法實(shí)驗(yàn)結(jié)果對(duì)比見表3，測(cè)試函數(shù)收斂情況見圖3。括號(hào)中為函數(shù)最優(yōu)值。對(duì)于單峰函數(shù)F2,F4,F5和F7，ITSSA尋優(yōu)均值和標(biāo)準(zhǔn)差比其它算法高出多個(gè)數(shù)量級(jí)，說明ITSSA具有較高的求解精度、求解速度和魯棒性。對(duì)于F1和F3，ITSSA和SSA具有相同的標(biāo)準(zhǔn)差，但是ITSSA比SSA的均值高出多個(gè)數(shù)量級(jí)。求解F6時(shí)，SCA和ALO求解能力很差，與理論最優(yōu)值存在較大誤差。而ITSSA在SSA的基礎(chǔ)上，相比WOA和GWO求解表現(xiàn)更好，且尋優(yōu)精度變化不大。

對(duì)于不定維多峰函數(shù)F8，各算法求解能力均不理想，ITSSA尋優(yōu)能力僅次于GWO。對(duì)于F9～F11，ITSSA在迭代次數(shù)20以內(nèi)可以找到最優(yōu)解，不易陷入局部最優(yōu)，優(yōu)于其它算法。對(duì)于F12～F14，ITSSA求解能力最優(yōu)。對(duì)于固定維多峰函數(shù)F15，各算法都收斂到-1.3016，ITSSA標(biāo)準(zhǔn)差最小，具有最好的穩(wěn)定性。

綜上所述，ITSSA算法在單峰和多峰函數(shù)上的尋優(yōu)性能均優(yōu)于SCA,ALO,WOA,GWO和基礎(chǔ)的SSA算法。這主要得益于精英反向策略、自適應(yīng)t分布以及螢火蟲機(jī)制，通過這些方法讓ITSSA算法能有效平衡全局和局部尋優(yōu)能力，一定程度上避免了算法后期陷入局部最優(yōu)，讓ITSSA算法在求解速度、求解精度和穩(wěn)定性方面均表現(xiàn)出較好的性能，具有較好的尋優(yōu)能力。

Table 3 Comparison of test results of six algorithms

4.2 基于ITSSA的2維最大熵分割方法

為驗(yàn)證ITSSA2維最大熵分割的有效性，選取經(jīng)典的rice圖(見圖4)、pepper(見圖5)、伯克利數(shù)據(jù)集中圖86016(見圖6)和113016(見圖7)進(jìn)行對(duì)比分析。采用峰值信噪比(peak signal-to-noise ratio，PSNR)、特征相似性(feature similarity index，F(xiàn)SI)[25]、各算法運(yùn)行時(shí)間對(duì)圖像分割質(zhì)量和算法性能進(jìn)行評(píng)價(jià)。其中，峰值信噪比是基于像素均方差的圖像相似性的評(píng)價(jià)指標(biāo)，PSNR越大，代表圖像失真越少；特征相似性是一種基于圖像低級(jí)特征理解圖像這一事實(shí)的相似性評(píng)價(jià)指標(biāo)，F(xiàn)SI越接近1，代表圖像相似度越強(qiáng)。PSNR和FSI定義如下：

式中，I(x,y)和I*(x,y)分別代表原圖像和分割后的圖像。

Fig.3 Convergence graph of the benchmark functions

Fig.4 Segmentation results of image rice

Fig.5 Segmentation results of image pepper

Fig.6 Segmentation results of image 86016

Fig.7 Segmentation results of image 113016

式中，Ψ表示整幅圖像的空間域，C(x)代表最大相位，S(x)代表原圖像和分割后圖像的相似性值。

式中，C1(x)和C2(x)代表原圖像和分割后圖像的相位；F(x)代表圖像特征相似性；G(x)代表圖像梯度相似性；G1(x)和G2(x)代表原圖像和分割后圖像的梯度幅值；ε,δ,K1和K2均為常數(shù)。

在rice圖的分割實(shí)驗(yàn)中，ITSSA優(yōu)化的2維最大熵在2維最大熵基礎(chǔ)上提高了峰值信噪比且在結(jié)構(gòu)相似性指標(biāo)上提升31.2%。由圖4可以看出，本文中算法誤判的像素比其它算法少且米粒輪廓最清晰。在pepper圖的分割實(shí)驗(yàn)中，本文中分割出更清晰的辣椒，且3種指標(biāo)優(yōu)于其它算法，峰值信噪比增加20%。對(duì)于伯克利數(shù)據(jù)集中的86016和113016，雖然2維Otsu比基礎(chǔ)的2維Kapur在峰值信噪比指標(biāo)和特征相似度表現(xiàn)更好，但是保留的圖片細(xì)節(jié)大大減少，耗時(shí)過久。本文中提出的算法不僅在3種評(píng)價(jià)指標(biāo)上表現(xiàn)更好，改善了113016圖錯(cuò)分馬匹的現(xiàn)象，也保留了86016圖和113016圖更多草地和馬匹細(xì)節(jié)，分割輪廓上有更好的表現(xiàn)。與此同時(shí)，大大縮短了2維最大熵分割耗時(shí)時(shí)間，對(duì)于256×256的圖像，將分割圖像總時(shí)間達(dá)到耗時(shí)最少的效果(見表4)。

Table 4 Comparison of values obtained by different segmentation algorithms

5 結(jié) 論

針對(duì)麻雀種群角色少、尋優(yōu)精度不足的現(xiàn)象，提出了一種基于自適應(yīng)t分布的多策略改進(jìn)麻雀算法。首先利用反向機(jī)制引導(dǎo)算法跳出局部最優(yōu)，然后將自適應(yīng)t分布變異引入位置更新，發(fā)揮其擾動(dòng)能力。與此同時(shí)，采用精英反向策略提高發(fā)現(xiàn)者質(zhì)量，擴(kuò)大搜索區(qū)域，引入螢火蟲機(jī)制擾動(dòng)麻雀位置，提高全局優(yōu)化能力并且增加種群多樣性。融合ITSSA和最大2維熵分割方法，縮短了原最大2維熵分割方法分割時(shí)間，并將峰值信噪比、特征相似性作為評(píng)估標(biāo)準(zhǔn)，與2維Otsu法、2維Kapur熵相比，分割性能更好，分割出更清晰目標(biāo)輪廓的同時(shí)保留更多細(xì)節(jié)。實(shí)驗(yàn)表明，基于ITSSA的最大2維熵圖像分割方法在一定程度上解決了麻雀算法后期易陷入局部最優(yōu)的情況和最大2維熵耗時(shí)長(zhǎng)的缺點(diǎn)，具有較好的應(yīng)用價(jià)值，為群體智能優(yōu)化算法應(yīng)用圖像分割領(lǐng)域提供參考。在未來研究中，將嘗試尋找并改進(jìn)出性能更優(yōu)的群體智能優(yōu)化算法，應(yīng)用圖像分割領(lǐng)域提高分割性能效果。