基于改進蜉蝣算法優化多閾值圖像分割

賀航, 許連杰, 李高源, 呂容飛, 王喜良

(1.西安衛星測控中心, 西安 710043; 2.太原衛星發射中心, 太原 030031)

隨著科技的突飛猛進,在圖像處理領域中,圖像處理的基礎是圖像分割,同時圖像分割也是計算機視覺領域中一項及具有挑戰性的研究熱點,目前廣泛應用于火災實時監測、農業作物工程、醫學圖像處理、交通運輸控制等各個領域[1]。現如今圖像分割主要方法有聚類分割[2]、閾值分割[3]、區域分割[4]以及人工神經網絡[5]等方法。眾多學者中目前青睞于閾值分割方法,其在分割中具有穩定、簡單、高效率等優點。閾值分割方法的關鍵在于找到精確的閾值數,并且依據閾值個數將閾值劃分為單閾值分割和多閾值分割。前者是指將圖像分割為目標和背景兩類,而后者則是將圖像分成不同的多個區域,使得多個類的類間方差最大[6]。現階段隨著研究者的科研需求與日俱增,單閾值分割效果已不能達到理想效果,因而轉向多閾值分割。但是在解決實際工程問題中需要選取多個閾值,其計算復雜度大大增加,使用傳統的多閾值分割方法達不到期望效果。

近年來,在參數尋優方面智能優化算法有著速度快、效率高、穩定性強等優點,隨著閾值分割技術的發展,越來越多學者將智能優化算法引入最優閾值的尋求過程中[7]。Erdman等[8]在進行多閾值分割中,針對3個級別的閾值分割使用改進的螢火蟲算法,其結果更加接近手動效果。Satapathy等[9]提出一種全新閾值分割方案基于Otsu法和混沌蝙蝠算法,計算的各項指標均取得良好效果。Agarwal等[10]在對直方圖的雙模和多模態閾值分割中,使用蜘蛛優化算法進行分割,在分割時間上得到了有效的提升。Yao等[11]將優良點集應用到灰狼優化(grey wolf optimization, GWO)算法,在全局優化中對最大熵作為目標函數進行優化。有效避免了陷入局部最優,同時應用到多閾值圖像分割,使其分割質量更高。李天平等[12]針對巖石鑄體薄片孔隙分割問題,提出真實的增強型超分辨生成對抗網絡方法提高鑄體薄片圖像分辨率。湯翔中等[13]在解決圖像分割中多數礦石表面不規則、棱角多,粘連等問題種,提出結合注意力與多尺度空洞卷積的Vit Transformer模型研究了礦石圖像分割,最終可以較好地完成礦石圖像分割任務。裴少通等[14]針對紫外圖譜光斑分割提出了一種基于深度學習的紫外圖譜光斑分割提取的方法為紫外光斑的量化提取及電力設備放電缺陷的紫外診斷提供了參考。楊淼[15]提出基于混沌與對立學習正余弦算法COLSCA的多閾值圖像分割方法,增強局部開發能力,有效提升了圖像分割精度和分割效率。郭云云等[16]在彩色圖像分割中利用改進K-means算法更好的取得分割效果,降低了時間上的復雜度。

雖然眾多研究者在圖像分割中不同程度的降低了閾值分割方法的計算復雜度,但是大多數仍然存在計算量大、計算時間長、分割精度低等問題。如何在提高分割精度的準確性的同時又可以提高分割精度,一直是研究者需要去解決的難題,因此,提出改進蜉蝣算法(improved mayfly algorithm, IMA)的指數熵多閾值圖像分割算法,該改進算法具有運用最少迭代次數的優點來求得全局最優性能,因而用來尋找最佳閾值進行圖像分割,并在灰度圖的基礎上進行相關的仿真實驗。為檢驗改進蜉蝣優化算法在圖像多閾值分割方面的可行性及分割精度的優越性,在Berkeley圖像庫中選取6張圖像進行閾值分割實驗。在此基礎上,利用分割時間、適應度值、結構衡量指標(structure similarity index measure,SSIM)和峰值信噪比(peak signal-to-noise ratio, PSNR)等指標評價分割效果,并通過對比灰狼優化算法,鯨魚優化算法和麻雀搜索算法(sparrow search algorithm, SSA),以驗證所提出的圖像分割算法的有效性。

1 蜉蝣算法

蜉蝣算法于2020年由Konstantinos等[17]提出的新型智能優化算法,蜉蝣是古翅目昆蟲的一種,蜉蝣的整個成長過程都是肉眼可以看到的。通常情況下,蜉蝣從卵中到成長為成熟個體,最終進行后代的繁殖,這一過程就是它一生的使命。在進行交配中,雄性蜉蝣為了吸引雌性,它們會聚集在水面上的一定范圍內的高度,通過自己特殊的信號來發射求偶信號。此時,雌性蜉蝣飛入雄性蜉蝣當中,與其進行交配,交配可能只持續幾秒,當結束交配之后,雌性蜉蝣將卵就會落在水面上,它們的生命周期到此結束。

隨機產生兩組蜉蝣,分別代表雄性和雌性種群。作為由d維向量表示的候選解x=(x1,x2,…,xd),并根據預先確定的目標函數f(x)對其性能進行評價。蜉蝣個體的速度v=(v1,v2,…,vd)決定著其位置的變化,其飛行的方向是個體之間的相互經驗以及種群之間的經驗所決定,每個蜉蝣在飛行過程中都會調整自己的飛行軌跡,朝著最有利于自己的位置飛行,即個人最佳位置pbest,以及所有蜉蝣個體匯總信息之后的群體最佳位置飛行gbest。

1.1 雄性蜉蝣的運動

(1)

一般情況下,雄性蜉蝣表演跳舞的高度距水面上幾米處,假設其存在一定的上限速度,隨著時間的變化,雄性蜉蝣位置是不固定的。因而,雄性蜉蝣的速度計算公式為

(2)

距離的計算公式為

(3)

式(3)中:xi為蜉蝣i在搜索空間中的現在位置;Xi為蜉蝣i在搜索空間中的最優位置;xij蜉蝣i在第j次搜索空間中的現在位置;Xij為蜉蝣i在第j次搜索空間中的最優位置;在種群的舞蹈表演中,為了持續不斷的表演上下舞蹈,其速度隨時間的變化而變化,并保持一定范圍的速度,因此,其速度更新計算公式為

(4)

1.2 雌性蜉蝣的運動

(5)

雄性蜉蝣和雌性蜉蝣的吸引是隨機的,假設其存在一個確定性的過程。依據其健康屬性進行互相吸引。即最好的雌性應該被最好的雄性吸引,第二好的雌性應該被第二好的雄性吸引,以此類推,再考慮到極小化問題,因而速度的計算公式為

(6)

1.3 蜉蝣交配

在蜉蝣進行交配中,分別從雄性和雌性群體中個選擇親本,同樣在進行父本母本的選擇中有兩種選擇方式,隨機選取或者基于適應度函數。選用后者來進行,即最好的雌性與最好的雄性繁殖,次好的雌性與次好的雄性繁殖。交叉的結果是兩個后代,其產生計算公式為

(7)

式(7)中:male為父本;female為母本;L為隨機數。

蜉蝣算法流程如下。

Step 1初始化雄性蜉蝣,雌性蜉蝣,設定初始參數。

Step 2計算適應度值,并且排序,獲取pbest和gbest。

Step 3依次更新雄性蜉蝣,雌性蜉蝣位置,并且交配。

Step 4計算蜉蝣適應度,并更新pbest和gbest。

Step 5是否滿足迭代條件,若達到最大迭代次數,輸出結果,否則重復執行Step 3～Step 5。

蜉蝣算法的偽代碼如下,其中,vmi為在第i維度上雄性蜉蝣的速度;vfi為在第i維度上雌性蜉蝣的速度。

Pseudo code of the mayfly algorithm (MA)Objective function f(x),x=(x1,x2,…,xd)TInitialize the male mayfly population xi(i=1,2,…,N) and velocities vmiInitialize the female mayfly population yi(i=1,2,…,M) and velocities vfiEvaluate solutionsFind global best gbestDo While stopping criteria are not metUpdate velocities and solution of males and femalesEvaluate solutionsRank the mayfliesMate the mayfliesEvaluate offspringSeparate offspring to male and female randomlyReplace worst solutions with the best new ones Update pbest and gbestEnd WhilePostprocess results and visualization

2 改進蜉蝣算法

2.1 基于Sobol序列初始化種群位置

在元啟發式算法中,算法的收斂速度和尋優精度很大程度上取決于初始解在解空間的分布情況[18]。在種群的初始化過程中,應盡量的使其在搜索空間中均勻的分布,進而可以有效地提高搜索效率,同時也提高算法的多樣性和遍歷性[19]。標準蜉蝣算法(mayfly algorithm,MA)采用隨機方式初始化種群,這種方法遍歷性低、種群分布不均勻和具有不可測性,因而在一定程度影響了該算法的性能。在對算法進行初始化優化時,眾多研究者利用混沌搜索優化初始化序列。王夢娜等[20]利用 Iterative混沌映射方式初始化種群。張達敏等[21]采用 Circle 混沌方法初始化種群。Zhang等[22]引入Cubic 映射算法初始化種群。這些混沌算法雖然就有一定的跳出局部最優能力,但是還存在隨機性強和相鄰點緊密相關等不足。針對以上不足,采用低差異序列采用確定性的低差異序列代替偽隨機序列,又稱為擬蒙特卡洛方法(Quasi-Monte Carlo, QMC)。QMC 通過選擇合理的采樣方向,盡可能地將所填充的區域均勻化,因而在處理概率問題中,具有更好的遍歷性和均勻性。采用一種低差異序列Sobol初始化種群,使用確定性擬隨機數序列代替偽隨機數序列的方法,在多維超立方體中,使其盡可能均勻的排布。設全局解的取值范圍為[ub,lb],由Sobol序列產生的第i個隨機數為Si∈[0,1],則種群初始位置可表示為

Xn=lb+Si(ub-lb)

(8)

式(8)中:ub、lb分別為位置的下限和上限。

假設搜索空間為二維,上下界分別為1和0,種群規模為100,對比偽隨機初始化種群空間分布和Sobol序列初始化種群空間分布如圖1所示。可以看出,通過Sobol序列產生的初始種群分布更加均勻、遍歷性更廣。

橫、縱坐標為將有量綱的數值轉換為無量綱的 數值0-1歸一化后的指標數值

2.2 自適應的慣性權重因子

在群智能算法中,慣性權重的概念是在粒子群算法中提出的,目的是用于控制認知個體與社會的學習能力。在算法迭代初期,較大的慣性權重因子可以增強全局的搜索能力,保持種群的多樣性;在算法迭代晚期,較小的慣性權重因子可以增強算法局部開發能力,并加速向最優解收斂[23]。然而對于多峰值函數,一般原始算法無法在全局搜索階段找到更優解,進而容易陷入局部最優,為了更好地均衡MA的全局與局部搜索能力,引入一種自適應非線性慣性權重機制,定義為

(9)

式(9)中:s為迭代次數;wmax、wmin分別為慣性權重的最大值和最小值,通常取值為0.964和0.396;fmax(s)、fmin(s)分別用為當前迭代s時種群的適應度最大值和最小值;favg(s)為迭代s時種群的適應度均值;fi(s)為迭代s時個體i的適應度值;wi(s)為迭代s時第i次的自適應非線性慣性權重。

將慣性權重因子引入MA中,其雄性蜉蝣的位置更新的表達式為

(10)

式(10)中:w為自適應非線性慣性權重因子。

雌性蜉蝣的位置更新表達式為

(11)

通過添加自適應的慣性權重不斷對雄性蜉蝣和雌性蜉蝣的位置更新,使得在解的搜索空間中不斷計算新的適應度值與舊的適應度值比較,每次迭代比較取最優的適應度值。

3 多閾值圖像分割

3.1 指數熵閾值分割原理

Jin等[24]于1989年提出了指數熵的概念,并給出了最大指數熵閾值的選取算法。

概率為pi的事件所含的信息量為

Eexp=e1-pi

(12)

類比基于Shannon熵的準則函數,能夠得到指數熵準則函數,一維直方圖情況下指數熵的計算式對應于閾值t的目標類和背景類的熵值分別表示為

(13)

(14)

式中:hi為第i次分割后的熵;pi為灰度值為i的像素點出現的概率;w0為初始像素點的概率;wb為第b次像素點的概率。總的熵值可表示為

(15)

最佳閾值為

t*=argmax(0≤t≤L-1)[E(t)]

(16)

式(16)中:E(t)為總的誤差概率。

單閾值分割可由式(16)求得,但在解決實際工程圖像分割的過程中,單閾值通常不能滿足分割精度的要求,因此現階段研究多閾值的分割較為廣泛,推廣到多閾值則為尋找一組閾值(t0,t1,t2,…,tn)使得熵值最大,即

t(1,2,…,n)*=argmax{H0+H1+…+Hn}

(17)

式(17)中:Hn第n次分割的熵。

3.2 改進蜉蝣算法的指數熵多閾值分割

由于該算法具有運用最少迭代次數的優點來求得全局最優性能,因而由上述多閾值指數熵分割原理可知,計算中通過不斷迭代尋優,可獲得最優熵值。因此,在圖像灰度空間里采用改進蜉蝣算法對適應度函數式(17)進行尋優,從而獲得圖像分割最優閾值向量。通過迭代搜尋使得總熵值取得最大的閾值組合t*,并將其作為圖像分割的閾值,具體操作步驟如下。

Step 1讀取待分割圖像,并求其圖像的灰度直方圖。

Step 2利用Sobol初始化種群xi(i=1,2,…,n),lb、ub、最大迭代次數Maxgen、定義權重wi和欲分割閾值等。

黃劍，詹維納，陳楊黎，等.基于法布里-珀羅干涉的微懸臂偏移檢測系統[J].光子學報，2018，47(12)：1212003

Step 3對圖像進行分割,計算每個蜉蝣的適應度值。

Step 4利用式(10)、式(11)記錄每個蜉蝣位置與個體最優蜉蝣位置,全局最優蜉蝣位置比較,標記個體最優位置與全局最優位置。

Step 5更新蜉蝣位置,并且檢測蜉蝣飛行速度是否越界。

Step 6檢測是否達到最大迭代次數,若達到則返回最佳適應度的蜉蝣位置信息,即為最佳閾值分割向量,否則重復Step 3～Step 5。

Step 7利用得到的最佳閾值分割向量對圖像進行分割,輸出分割后的圖像。

分析可知,本文分割算法流程如圖2所示。

圖2 本文分割算法流程圖Fig.2 Flow chart of theproposed segmentation algorithm

4 圖像分割實驗與分析

為了實驗在平等環境下進行,減少算法隨機性帶來的影響,本實驗均采用CPU為Intel (R)Xeon(R) W-2102 CPU @2.90 GHz,內存為16 GB的計算機,操作系統為 Windows7,編譯軟件為MATLAB 2017b。實驗中其圖像的灰度級為256,分割閾值取值范圍為[0,255],每種算法迭代次數為200,種群規模為40。為了增加實驗的公平性,對選取的算法內參數進行了設置,各算法參數取值如表1所示。

表1 各算法參數Table 1 Algorithm parameter value

結合群智能算法在多閾值分割中實際上是求解分割算法多閾值適應度的最優閾值組合。通過峰值信噪比PSNR,適應度函數值和運行時間這3種指標來評估IMA算法與其他算法的性能差別。

選取Berkeley圖像庫中6幅復雜多目標圖像作為分割對象,每個圖像的大小為481×321,進而對其有效性進行驗證。圖3為6幅圖像的灰度直方圖,可以看出,不同類型的復雜多目標圖像具有不同直方圖的分布。

圖3 原始圖像的灰度直方圖Fig.3 Grayscale histogram of the original image

4.1 不同閾值下算法的分割效果

首先利用提出的分割方法對圖片進行分割測試,對選取的6幅圖像分別選取閾值K=3、4和5對圖像進行分割效果驗證,如圖4所示,在解決復雜多目標圖像的閾值分割中,圖像分割的結果隨著選取閾值個數的增加而更接近原圖,且能提供較多的目標信息。

圖4 原始圖像及其多閾值分割結果Fig.4 Original image and its multi-threshold segmentation results

4.2 分割準確性對比

為了進一步驗證本文方法在分割準確性方面的優勢,分別選取6幅圖像,在不同閾值個數下,進行4種算法的分割對比實驗。表2列出了6幅圖像在4種分割算法下的分割閾值,其值存在一定的差異。

表2 4種方法得出的分割閾值Table 2 Segmentation thresholds obtained by 4 methods

表3列出了6幅圖像在不同分割算法下所獲得的指數熵目標函數值,一般情況下,該值越大,則表明其分割精度越高,分割效果越好。由表3的數據可知,本文方法的指數熵目標函數值高于GWO算法、WOA算法和SSA算法,這充分說明本文方法在閾值分割準確性指標上更優于其他3種算法。

表3 各算法參數Table 3 Comparison of objective function values obtained by 4 methods

4.3 分割速度對比

表4列出了不同算法的閾值分割時間。由表中數據分析可知,分割所需時間隨著分割閾值個數的增加而增加,同時本文算法分割時間最短。尤其在進行5閾值分割時,本文方法的計算時間比GWO算法、WOA算法、SSA算法分別快1.21倍、1.31倍、1.20倍,說明本文方法在處理復雜多目標圖像分割時,可以實現高效率分割工作。

表4 4種方法的計算時間對比Table 4 Comparison of calculation time of 4 methods

4.4 PSNR值對比

本文衡量算法的性能采用峰值信噪比(PSNR)[25],峰值信噪比依據每個像素的均方差(MSE)來比較分割圖像與原圖像的相似性。PSNR值越大,則失真越少,說明該算法在多閾值分割應用上的性能越好。其計算公式分別為

(18)

(19)

式(19)中:Io為待分割圖像;It為已分割圖像;h為總行數;w為總列數。

表5列出了6幅圖像在4種分割方法分割后計算出的PSNR值。由表5中數據分析可知,采取本文方法分割圖像后PSNR值均高于對比算法。表明本文算法相比其他3種算法在求解精度、分割效果上具有一定的優勢。尤其是進行5閾值分割時,本文方法的PSNR值相比GWO算法、WOA算法、SSA算法分別提高了0.7%、1.4%、0.9%。說明本文方法在求解精度上獲得更好的分割效果。

表5 4種分割方法得出的PSNR值對比Table 5 Comparison of PSNR values obtained by 4 segmentation methods

4.5 SSIM值對比

結構相似性(SSIM)是一種衡量兩幅圖像相似度的指標[26],通常取值范圍[0,1],其值越接近1說明兩幅圖像的相似度越高,在圖像分割中代表分割效果就越好,更好的為后續的圖像處理提供支持。計算SSIM性能指標時,把RGB圖轉換成YCbCr圖,然后再去進行計算,因而其SSIM值結果很低。給出兩幅圖像x和y,定義為

(20)

表6列出了6幅圖像在4種分割方法分割后計算出的SSIM值。由表6中數據分析可知,采取本文方法分割圖像后SSIM值均高于對比算法。表明本文算法相比其他3種算法在求解精度、分割效果上具有一定的優勢。

表6 4種分割方法得出的SSIM值對比Table 6 Comparison of SSIM values obtained by 4 segmentation methods

5 結論

圖像分割是圖像處理中非常重要的預處理步驟。針對傳統多閾值圖像分割方法存在計算量大、復雜度高,分割精度低等問題,提出一種基于IMA的指數熵多閾值圖像分割算法。首先,在初始化階段引入類隨機采樣方法中的 Sobol 序列,增強種群的遍歷性和多樣性;其次,提出一種自適應非線性慣性權重,提高了算法的收斂效率,利于種群向最優解逼近;最后,利用指數熵法構造改進蜉蝣算法的適應度函數,在閾值的求解過程中利用改進蜉蝣算法進行尋優,并應用于圖像的分割,結合最大指數熵多閾值分割方法迭代搜索最優分割閾值。本文改進算法在分割準確性、計算時間、SSIM和PSNR等方面進行了研究,并與其他分割算法進行了對比分析。得出如下結論。

(1)本文改進算法得到的的最大指數熵目標函數值比GWO算法、WOA算法、SSA算法都要高,說明該改進算法能計算出更加準確的分割閾值。尤其在進行5閾值分割時,本文改進算法的PSNR值相比GWO算法、WOA算法、SSA算法分別提高了0.7%、1.4%、0.9%,說明該改進算法的求解精度更高,可以獲得更好的分割效果。

(2)在進行5閾值分割時,本文改進算法的計算時間相比GWO算法、WOA算法、SSA算法分別快1.21倍、1.31倍、1.20倍,說明該改進算法的分割效率較高,針對復雜多目標圖像可以更快地進行多閾值分割。

未來,將研究本文改進算法在更高閾值尋優上的能力,以及解決大規模處理圖像時分割速度問題,在保證精度的同時進一步減少運算時間。