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

呂 鑫, 慕曉冬, 張 鈞

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

0 引 言

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

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

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

1 ISSA

1.1 SSA

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

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

發現者位置更新如下：

(1)

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

加入者位置更新如下：

(2)

偵察者位置更新如下:

(3)

1.2 SSA的改進

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

(4)

(5)

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

由于SSA中發現者在R2

故將SSA中發現者位置更新公式改進為

(6)

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

(7)

ISSA的簡單流程為

步驟 1初始化；

步驟 2計算麻雀種群個體適應度;

步驟 3得到當前最佳位置,最差位置和最差適應度;

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

步驟 6若算法達到最大迭代次數,則算法尋優結束,否則轉到步驟3。

圖1 發現者搜索策略Fig.1 Search strategy of producers

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

2.1 多閾值分割

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

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

(8)

(9)

?

(10)

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

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

(11)

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

(12)

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

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

(13)

(14)

?

(15)

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

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

(16)

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

(17)

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

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

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

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

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

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

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

步驟 6執行ISSA算法。

步驟 7若算法達到預設最大迭代次數MaxCycle或最佳適應度持續保持在迭代總數的10%,則算法尋優結束,并返回最佳適應度的麻雀位置信息,即為最佳閾值分割向量;否則跳轉至步驟5。

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

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

3 實驗結果與分析

為驗證ISSA的算法性能,設計了基準函數對比實驗,基于ISSA的圖像多閾值分割實驗和圖像多閾值分割對比實驗。基準函數對比實驗旨在驗證改進算法的通用性能提升。基于ISSA的圖像多閾值分割實驗旨在檢驗ISSA應用于圖像多閾值分割的可行性,同時對比了基于Otsu和Kapur熵多閾值分割方法的優劣。圖像多閾值分割對比實驗旨在驗證基于ISSA的圖像多閾值分割方案對比現有多閾值分割方法的優越性。文中實驗均基于Windows7 64位操作系統,2.50 GHz CPU和4 GB內存的PC機,Matlab R2015a開發軟件。

3.1 基準函數對比實驗

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

表1 基準函數

函數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)。實驗中算法的通用參數設置為:種群規模NP=30,最大迭代次數MaxCycle=100,發現者個數pNum和偵察者個數sNum均取NP的20%。

SSA和ISSA在4個基準函數上的收斂曲線如圖3所示,從圖中可以看出ISSA在收斂速度和收斂精度上均優于SSA。

圖3 基準函數收斂圖Fig.3 Convergence graphs of the benchmark function

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

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

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

表2 算法性能比較

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

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

(18)

(19)

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

(20)

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

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

表3 基于Otsu方法的分割結果

表4 基于Kapur方法的分割結果

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

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

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

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

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

秩和檢驗結果如表5所示,從檢驗結果可以看出,P值均小于0.05,則拒絕H0,接受H1,兩種方法的PSNR值之間存在顯著差異,同時Otsu方法在圖像分割中表現更好,能夠獲得更高的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 圖像多閾值分割對比實驗

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

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

基于Otsu的對比結果可以看出,ISSA相較GWO、SSA1和ABC算法,100%能夠得到更大的類間方差,且穩定性表現最優。同時,79.17% ISSA能夠取得更高的PSNR值。基于Kapur的對比結果可以看出,ISSA相較其他算法,在穩定收斂的基礎上,95.83%能夠取得更大的熵值,79.17% PSNR值最優。綜上所述,ISSA應用在多閾值圖像分割上,分割精度更高,分割質量更好,算法穩定性更強,綜合分割性能最優。

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

表6 4種算法基于Otsu方法的對比結果

表7 4種算法基于Kapur方法的對比結果

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

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

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

4 結 論

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

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

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

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