基于改進麻雀搜索算法的多閾值圖像分割

呂 鑫, 慕曉冬, 張 鈞

(1. 火箭軍工程大學(xué)作戰(zhàn)保障學(xué)院, 陜西 西安 710025; 2. 北京遙感設(shè)備研究所, 北京 100854)

0 引 言

圖像分割是圖像處理的關(guān)鍵環(huán)節(jié),其目的是從圖像中提取出感興趣的目標(biāo)區(qū)域[1]。閾值分割作為一種簡單有效的分割方法,被廣泛應(yīng)用于各領(lǐng)域的圖像處理,主要包括最大類間方差法和Kapur熵等分割方法。常見閾值分割方法采取窮盡搜索進行圖像多閾值分割,計算時間長,局限性大,如何快速準(zhǔn)確地找到最佳閾值成為閾值分割的關(guān)鍵。

隨著群智能優(yōu)化算法的興起和發(fā)展,由于其具有全局尋優(yōu)和收斂速度快等特點,被廣泛應(yīng)用于圖像分割,起到了減少分割時間和提高分割精度的作用。Akay[2]將粒子群優(yōu)化(particle swarm optimization, PSO)算法和人工蜂群(artificial bee colony, ABC)算法應(yīng)用到多閾值圖像分割,選擇Kapur熵和Otsu作為適應(yīng)度函數(shù)來搜索閾值以獲取最佳分割效果。Yao[3]將優(yōu)良點集應(yīng)用到灰狼優(yōu)化(grey wolf optimization, GWO)算法,并將最大熵作為目標(biāo)函數(shù)進行全局優(yōu)化,具有良好的全局收斂性和魯棒性,有效避免了陷入局部最優(yōu),同時應(yīng)用到多閾值圖像分割,分割閾值更加穩(wěn)定,分割質(zhì)量更高。Wang[4]將萊維飛行引入樽海鞘群算法(salp swarm algorithm, SSA1),分別使用Kapur熵、Otsu和Renyi熵作為適應(yīng)度函數(shù)進行全局尋優(yōu),表現(xiàn)出良好的搜索能力和開拓能力,多閾值圖像分割更優(yōu),并定量分析了Kapur熵分割結(jié)果優(yōu)于其他兩種方法。其他將群智能優(yōu)化算法[5～9]應(yīng)用到多閾值圖像分割也均表現(xiàn)出良好的分割性能。

薛建凱和沈波于2020年開發(fā)的麻雀搜索算法[10](sparrow search algorithm, SSA)是一種模擬麻雀覓食行為和反捕食行為的新型群智能優(yōu)化算法。SSA能夠取得比PSO、GWO等算法更好的尋優(yōu)性能,但是其運行時間較長,且仍存在陷入局部最優(yōu)的缺陷。所以,結(jié)合鳥群算法[11](bird swarm algorithm, BSA)的思想設(shè)計改進麻雀搜索算法(improved sparrow search algorithm, ISSA),以此來縮短算法運行時間,并提高其搜索能力和開拓能力,取得更好的全局尋優(yōu)性能。同時,將Otsu和Kapur熵作為ISSA的目標(biāo)函數(shù)進行閾值尋優(yōu),并對比Otsu和Kapur熵兩種方法的優(yōu)劣性。最后,將ISSA與現(xiàn)有的分割方法展開多組對比實驗,驗證ISSA在分割性能上的提升。實驗結(jié)果表明,ISSA能更穩(wěn)定、準(zhǔn)確、高效地找到最佳閾值,綜合性能更優(yōu)。

1 ISSA

1.1 SSA

在自然界中,麻雀作為群居鳥類,聰明且記憶力強,種群內(nèi)部存在明顯的分工,一部分麻雀負責(zé)尋找食物并為整個種群提供覓食區(qū)域和方向,剩余麻雀則利用前者來獲取食物。同時,當(dāng)有麻雀意識到危險時,會及時發(fā)出警報信號,整個種群會立刻做出反捕食行為。

在SSA中,每只麻雀位置對應(yīng)一個解。麻雀在覓食時存在3種行為:① 作為發(fā)現(xiàn)者尋找食物;② 作為加入者跟隨發(fā)現(xiàn)者覓食;③ 作為偵察者決定種群是否放棄食物。其中,發(fā)現(xiàn)者和加入者之間可互相轉(zhuǎn)換,但比例保持恒定,發(fā)現(xiàn)者一般占到種群的10%～20%。發(fā)現(xiàn)者作為覓食的引導(dǎo)者,搜索范圍廣,通過記憶不斷更新自身位置,以獲得食物來源。而加入者則跟隨發(fā)現(xiàn)者不斷進行覓食,以獲取更高的適應(yīng)度。但由于隨時存在捕食者的威脅,種群會隨機選取10%～20%的麻雀作為偵察者進行監(jiān)視,以便在捕食者出現(xiàn)時及時提醒整個種群做出反捕食行為。

發(fā)現(xiàn)者位置更新如下：

(1)

式中,MaxCycle表示算法的最大迭代次數(shù);α為(0,1]之間的均勻隨機數(shù);Q是服從標(biāo)準(zhǔn)正態(tài)分布的隨機數(shù);L表示1×d的矩陣,且元素均為1;R2∈[0,1]和ST∈[0.5,1]分別表示預(yù)警值和安全值。

加入者位置更新如下：

(2)

偵察者位置更新如下:

(3)

1.2 SSA的改進

BSA是Meng等人于2015年受鳥群飛行、覓食和警戒行為啟發(fā)而提出的群智能算法,具有良好的穩(wěn)定性。飛行行為中發(fā)現(xiàn)者和加入者的位置更新公式分別是

(4)

(5)

式中,randn(0,1)表示均值為0,標(biāo)準(zhǔn)差為1的高斯隨機分布;FL∈[0,2]代表加入者跟隨生產(chǎn)者尋找食物的概率;k屬于發(fā)現(xiàn)者。

由于SSA中發(fā)現(xiàn)者在R2

故將SSA中發(fā)現(xiàn)者位置更新公式改進為

(6)

同時,SSA中的加入者在全維度向最佳位置靠近時,雖然能夠達到快速收斂的效果,但是減少了種群多樣性,算法容易陷入局部最優(yōu)。而BSA中的加入者是以一定概率向發(fā)現(xiàn)者靠攏,既保證了全局收斂,又不失種群多樣性,有效跳出局部最優(yōu)。故改進SSA中加入者的位置更新公式如下：

(7)

ISSA的簡單流程為

步驟 1初始化；

步驟 2計算麻雀種群個體適應(yīng)度;

步驟 3得到當(dāng)前最佳位置,最差位置和最差適應(yīng)度;

步驟 4根據(jù)式(6)、式(7)和式(3)依次更新發(fā)現(xiàn)者、加入者和偵察者的位置信息;

步驟 6若算法達到最大迭代次數(shù),則算法尋優(yōu)結(jié)束,否則轉(zhuǎn)到步驟3。

圖1 發(fā)現(xiàn)者搜索策略Fig.1 Search strategy of producers

2 基于ISSA的多閾值圖像分割

2.1 多閾值分割

多閾值分割就是按照某一準(zhǔn)則在待分隔圖像f(x,y)中尋找一組閾值[t1,t2,…,tn](n>0),并將其分割成n+1部分的過程。Otsu和Kapur熵是兩種常見的多閾值分割準(zhǔn)則。

Otsu是由日本學(xué)者大津于1979年提出的一種全局自適應(yīng)閾值選取方法[12]。對于一幅灰度級在[0,1,…,L-1]的給定圖像(L常取256),灰度級為i的像素個數(shù)為ni,像素總數(shù)為N,則圖像中每一部分的灰度均值表示為

(8)

(9)

?

(10)

則此時圖像的類間方差表示為

σ=ω0(u0-uT)2+ω1(u1-uT)2+…+ωn(un-uT)2

(11)

當(dāng)閾值向量滿足式(12)時,即為最佳閾值,可表示為

(12)

基于Kapur熵的閾值化方法就是利用熵量化的值衡量圖像中包含的信息,使圖像分割后目標(biāo)區(qū)域熵和背景區(qū)域熵的和最大化[13]。則基于Kapur熵準(zhǔn)則的分割圖像各部分熵值如下所示:

水法確立了流域與區(qū)域相結(jié)合的水資源管理體制，太湖流域管理局把建立流域與區(qū)域聯(lián)合執(zhí)法機制作為貫徹水法的重要舉措，通過主動與地方開展聯(lián)合巡查、專項聯(lián)合執(zhí)法檢查活動以及重大水事違法案件聯(lián)合查處與監(jiān)督等工作，總結(jié)好的經(jīng)驗與做法，于2005年印發(fā)《太湖流域“一湖兩河”水行政執(zhí)法聯(lián)合巡查制度》，該制度包含了聯(lián)合巡查、定期磋商、案件處理、案件督辦、培訓(xùn)與交流等流域與區(qū)域合作機制，并在《太湖流域管理條例》立法中得到進一步拓展與細化。

(13)

(14)

?

(15)

此時,圖像灰度值的Kapur熵定義為

f([t1,t2,…,tn])=H0+H1+…+Hn

(16)

分割圖像的最佳閾值向量滿足下式：

(17)

2.2 基于ISSA的多閾值分割算法

假設(shè)對圖像進行n維閾值分割,則解向量為T=[t1,t2,…,tn],其取值為正整數(shù)且滿足0

步驟 1讀取待分割圖像f(灰度圖像)。

步驟 2求讀入圖像的灰度直方圖。

步驟 3ISSA參數(shù)初始化。包括種群規(guī)模NP,算法的最大迭代次數(shù)MaxCycle,發(fā)現(xiàn)者個數(shù)pNum,偵察者個數(shù)sNum,欲分割閾值數(shù)n等。

步驟 4麻雀種群初始化。麻雀個體位置表示圖像分割的閾值向量,其為從小到大順序排列的像素灰度值組合,每個向量的分量取值范圍為[0,255],且為整數(shù)。

步驟 5根據(jù)式(11)或式(16)計算種群中所有麻雀的適應(yīng)度值,得到當(dāng)前最佳適應(yīng)度的麻雀個體。

步驟 6執(zhí)行ISSA算法。

步驟 7若算法達到預(yù)設(shè)最大迭代次數(shù)MaxCycle或最佳適應(yīng)度持續(xù)保持在迭代總數(shù)的10%,則算法尋優(yōu)結(jié)束,并返回最佳適應(yīng)度的麻雀位置信息,即為最佳閾值分割向量;否則跳轉(zhuǎn)至步驟5。

步驟 8利用得到的最佳閾值分割向量對灰度圖像進行分割,輸出分割后的圖像g。

圖2 所提分割算法流程圖Fig.2 Flow chart of the proposed segmentation algorithm

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

為驗證ISSA的算法性能,設(shè)計了基準(zhǔn)函數(shù)對比實驗,基于ISSA的圖像多閾值分割實驗和圖像多閾值分割對比實驗?；鶞?zhǔn)函數(shù)對比實驗旨在驗證改進算法的通用性能提升?；贗SSA的圖像多閾值分割實驗旨在檢驗ISSA應(yīng)用于圖像多閾值分割的可行性,同時對比了基于Otsu和Kapur熵多閾值分割方法的優(yōu)劣。圖像多閾值分割對比實驗旨在驗證基于ISSA的圖像多閾值分割方案對比現(xiàn)有多閾值分割方法的優(yōu)越性。文中實驗均基于Windows7 64位操作系統(tǒng),2.50 GHz CPU和4 GB內(nèi)存的PC機,Matlab R2015a開發(fā)軟件。

3.1 基準(zhǔn)函數(shù)對比實驗

為驗證ISSA的搜索能力和開發(fā)能力,本文采用4種不同類型的測試函數(shù),如表1所示。

表1 基準(zhǔn)函數(shù)

函數(shù)F1～F4具有不同的特征[14]:F1單峰變量可分離(unimodal and variables separable, UVS)、F2單峰變量不可分離(unimodal and variables non-separable, UVN)、F3多峰變量可分離(multimodal and variables separable, MVS)、F4多峰變量不可分離(multimodal and variables non-separable, MVN)。實驗中算法的通用參數(shù)設(shè)置為:種群規(guī)模NP=30,最大迭代次數(shù)MaxCycle=100,發(fā)現(xiàn)者個數(shù)pNum和偵察者個數(shù)sNum均取NP的20%。

SSA和ISSA在4個基準(zhǔn)函數(shù)上的收斂曲線如圖3所示,從圖中可以看出ISSA在收斂速度和收斂精度上均優(yōu)于SSA。

圖3 基準(zhǔn)函數(shù)收斂圖Fig.3 Convergence graphs of the benchmark function

由于ISSA搜索策略具有隨機性,為定量分析其性能,分別在4個基準(zhǔn)函數(shù)上獨立運行30次,得到尋優(yōu)結(jié)果的最劣值、最優(yōu)值、平均值、標(biāo)準(zhǔn)差和平均運行時間,并與SSA算法運行結(jié)果進行比較,如表2所示。從尋優(yōu)結(jié)果可以得出,ISSA較SSA在尋優(yōu)精度上整體提升了44.20%,穩(wěn)定性整體提升了47.37%,同時平均運行時間整體減少了7.90%,表現(xiàn)出優(yōu)良的尋優(yōu)性能。

3.2 基于ISSA的圖像多閾值分割實驗

為檢驗基于ISSA的多閾值圖像分割算法的可行性,實驗選取閾值分割中經(jīng)典的Cameraman圖、Lena圖、Butterfly圖和Baboon圖作為測試圖像,并基于Otsu和Kapur熵兩種分割準(zhǔn)則依次進行雙閾值、三閾值、四閾值和五閾值圖像分割。

表2 算法性能比較

算法實驗參數(shù)設(shè)置為:種群規(guī)模NP=30,最大迭代次數(shù)MaxCycle=500,個體上下界取[0,255],維數(shù)dim依次取2、3、4和5,發(fā)現(xiàn)者個數(shù)pNum和偵察者個數(shù)sNum均取NP的20%。

為了客觀精確地評價分割算法的穩(wěn)定性和多閾值圖像分割效果,對每幅圖像獨立運行30次,并采用標(biāo)準(zhǔn)差STD和峰值信噪比PSNR作為評價標(biāo)準(zhǔn)[15],分別如下所示：

(18)

(19)

式中,NI是獨立運行次數(shù)(NI=30);bfi是第i次運行的最佳適應(yīng)度;μ是適應(yīng)度bf的平均值；MSE表示大小為m×n的原始圖像f和分割后圖像g的均方誤差，可表示為

(20)

分別將類間方差和Kapur熵作為ISSA的目標(biāo)函數(shù),測試閾值個數(shù)n取2、3、4和5時實驗結(jié)果,記錄最佳分割閾

值、PSNR和STD值,如表3和表4所示。由表3和表4的結(jié)果可以看出,除卻Cameraman圖四閾值分割結(jié)果,其余分割結(jié)果中PSNR值和STD值均與閾值個數(shù)成正比。同時Otsu方法得到的PSNR值普遍高于Kapur方法,但Kapur方法的穩(wěn)定性普遍優(yōu)于Otsu方法。

表3 基于Otsu方法的分割結(jié)果

表4 基于Kapur方法的分割結(jié)果

為直觀了解基于ISSA的多閾值圖像分割結(jié)果,圖4和圖5分別顯示了基于Otsu多閾值分割準(zhǔn)則和Kapur熵多閾值分割準(zhǔn)則的圖像分割結(jié)果。從分割結(jié)果可以看出,ISSA在Otsu和Kapur兩種方法下進行多閾值圖像分割,隨著閾值個數(shù)的增加,圖像分割結(jié)果中細節(jié)更清晰,信息更完整,分割質(zhì)量更高。

比較ISSA基于Otsu方法和Kapur方法的分割結(jié)果,對Otsu和Kapur獨立運行30次得到的PSNR值在顯著性

水平為5%的情況下做Wilcoxon符號秩檢驗。建立假設(shè):

H0:兩種方法的PSNR值之間沒有差異。

H1:兩種方法的PSNR值之間存在顯著差異。

秩和檢驗結(jié)果如表5所示,從檢驗結(jié)果可以看出,P值均小于0.05,則拒絕H0,接受H1,兩種方法的PSNR值之間存在顯著差異,同時Otsu方法在圖像分割中表現(xiàn)更好,能夠獲得更高的PSNR值,且不具偶然性。

表5 Wilcoxon符號秩檢驗

圖4 基于Otsu方法的多閾值分割效果圖Fig.4 Multi-threshold segmentation effect graphs based on Otsu method

圖5 基于Kapur方法的多閾值分割效果圖Fig.5 Multi-threshold segmentation effect graphs based on Kapur method

3.3 圖像多閾值分割對比實驗

設(shè)計本文算法與GWO、SSA1和ABC的對比實驗,驗證本文算法在圖像多閾值分割上的性能。為保證實驗的公平性,同時保證各算法優(yōu)化效果最佳,且盡量達到穩(wěn)定收斂,對4種算法的通用參數(shù)設(shè)置同第3.2節(jié)。同時,ABC中的交叉系數(shù)cr=0.6,鄰域搜索未發(fā)生改變的最大次數(shù)Limit=50,蜜源數(shù)目foodNumber=15。

4種算法分別基于Otsu和Kapur兩種方法進行圖像多閾值分割,結(jié)果如表6和表7所示。

基于Otsu的對比結(jié)果可以看出,ISSA相較GWO、SSA1和ABC算法,100%能夠得到更大的類間方差,且穩(wěn)定性表現(xiàn)最優(yōu)。同時,79.17% ISSA能夠取得更高的PSNR值?；贙apur的對比結(jié)果可以看出,ISSA相較其他算法,在穩(wěn)定收斂的基礎(chǔ)上,95.83%能夠取得更大的熵值,79.17% PSNR值最優(yōu)。綜上所述,ISSA應(yīng)用在多閾值圖像分割上,分割精度更高,分割質(zhì)量更好,算法穩(wěn)定性更強,綜合分割性能最優(yōu)。

為了更好地反映4種算法的收斂情況,繪制出4幅圖像分割過程的收斂曲線,由于篇幅原因,僅給出4幅圖像基于Otsu的五閾值分割收斂曲線,如圖6所示。

表6 4種算法基于Otsu方法的對比結(jié)果

表7 4種算法基于Kapur方法的對比結(jié)果

由圖6結(jié)果可以看出,ISSA收斂速度更快,收斂精度更高。

綜上所述,ISSA可以穩(wěn)定收斂到最優(yōu)解,相較于GWO、SSA1和ABC,ISSA在算法收斂速度和分割精度上都有一定的提高和改善。

圖6 基于Otsu方法的五閾值分割收斂圖Fig.6 Five-threshold segmentation convergence curve based on Otsu method

4 結(jié) 論

SSA作為一種新型群智能優(yōu)化算法,相較GWO和PSO等算法具有良好的全局收斂性能和魯棒性[9],但依舊存在算法運行時間長、易陷入局部最優(yōu)等缺點。為了進一步提高算法性能,設(shè)計出基于BSA中飛行行為思想的ISSA,借助其優(yōu)勢,運用到圖像多閾值分割中。

(1) ISSA在4種不同類型基準(zhǔn)函數(shù)上進行測試,實驗結(jié)果均能穩(wěn)定收斂到最優(yōu)解,且運行時間提升7.90%,穩(wěn)定性提升47.16%,尋優(yōu)精度提升44.18%,表現(xiàn)出更優(yōu)的尋優(yōu)能力,綜合性能更佳。

(2) ISSA基于Otsu和Kapur兩種方法進行圖像多閾值分割,均能獲得較好的分割結(jié)果,但從Wilcoxon符號秩檢驗結(jié)果可以看出,Otsu相較Kapur方法圖像分割結(jié)果的PSNR存在顯著差異,且基于ISSA的Otsu多閾值分割策略要優(yōu)于Kapur熵多閾值分割策略。

(3) 群智能算法具有隨機性,多次獨立運行結(jié)果能有效避免隨機性帶來的影響。針對Otsu和Kapur熵兩種準(zhǔn)則,ISSA的算法穩(wěn)定性均優(yōu)于其他3種算法,且95%以上的情況下尋優(yōu)效果最佳,79.17%的情況下能夠取得最大的PSNR值,綜合分割性能優(yōu)于其他3種算法。