基于改進蜻蜓算法的多閾值彩色圖像分割

鮑小麗 賈鶴鳴 郎春博

(東北林業(yè)大學(xué)機電工程學(xué)院 黑龍江 哈爾濱 150040)

0 引 言

圖像分割是從圖像處理到分析的關(guān)鍵步驟，分割的質(zhì)量會影響到后續(xù)的圖像分類、模式識別等工作。圖像分割的目的在于將圖像中的像素點劃分為若干個各具相似特性的類別區(qū)域并提取出有用的目標(biāo)[1]。目前常用的圖像分割方法有基于閾值的圖像分割、基于區(qū)域的圖像分割、基于邊緣檢測的圖像分割、基于聚類技術(shù)的圖像分割等[2]。其中閾值分割方法因?qū)崿F(xiàn)簡單、運算效率高和性能較穩(wěn)定等優(yōu)點而被廣泛應(yīng)用于很多領(lǐng)域。例如：對醫(yī)學(xué)CT圖像的分割在臨床肺部疾病判斷中具有關(guān)鍵作用[3]；對森林火災(zāi)圖像的分割為檢測實時火情奠定堅實基礎(chǔ)[4]；對農(nóng)田作物圖像的分割為后期的病害防治工作提供參考和依據(jù)[5]。由于傳統(tǒng)的單閾值分割方法在比較復(fù)雜的圖像分割上難以獲得理想的分割效果，因此一些學(xué)者利用迭代的方式將其擴展到多閾值圖像分割中。

多閾值Otsu圖像分割是以類間方差最大為準(zhǔn)則來選取最優(yōu)閾值組合，但隨著閾值個數(shù)的增加，其計算量也呈指數(shù)增長，直接影響了圖像分割的效率。因此，一些學(xué)者將閾值選取問題視為以準(zhǔn)則函數(shù)為目標(biāo)函數(shù)的優(yōu)化問題，并借鑒仿生算法來提高優(yōu)化效率。例如：由柳新妮等提出的布谷鳥搜索算法在多閾值圖像分割中的應(yīng)用；王鈦等提出的基于離散灰狼算法的多閾值圖像分割等。但由于優(yōu)化算法本身的局限性，在分割圖像時仍存在穩(wěn)定性較差，容易陷入局部最優(yōu)等問題[6]。

蜻蜓算法(Dragonfly Algorithm,DA)是由Seyedali Mirjalili在2015年提出的一種新穎的群智能優(yōu)化算法[7]。該算法的靈感來源于自然界中的蜻蜓靜態(tài)和動態(tài)群體行為。在靜態(tài)群體行為中蜻蜓會分成幾個子群體在不同區(qū)域中捕食昆蟲，其特征為局部移動和飛行路徑的突變，這有利于進行局部開發(fā)；在動態(tài)群體行為中的蜻蜓會聚集成一個大的群體并向著統(tǒng)一的方向飛行，這有利于進行全局搜索。蜻蜓通過分離、結(jié)隊、聚集、覓食和避敵這五種行為來更新當(dāng)前所在位置。雖然蜻蜓算法對于優(yōu)化問題表現(xiàn)出良好的性能，但仍存在求解精度較差、早熟收斂等問題[8]。

本文提出一種改進蜻蜓算法(Improved Dragonfly Algorithm,IDA)并將其應(yīng)用到多閾值圖像分割領(lǐng)域。為解決標(biāo)準(zhǔn)DA算法中全局搜索能力較差且后期局部開發(fā)受限的問題，在保證算法運行效率的同時提高圖像分割的精度，進行了以下兩部分改進：1) 混沌初始化蜻蜓的初始位置，提高初始蜻蜓種群的質(zhì)量；2) 引入反向?qū)W習(xí)策略增加可選蜻蜓的數(shù)量，并擇優(yōu)選取蜻蜓，在增大隨機性的同時提高蜻蜓種群的進化速度。實驗選取6幅伯克利圖像，對比PSO、SCA、BA、HSO與ALO五種優(yōu)化算法。結(jié)果表明，IDA提高了蜻蜓種群的收斂速度，而且算法的求解精度得到有效提高，其PSNR、FSIM、SSIM、最優(yōu)適應(yīng)度函數(shù)值及運行時間等指標(biāo)均優(yōu)于5種對比算法，為后續(xù)的圖像處理工作奠定了良好的基礎(chǔ)。

1 多閾值Otsu圖像分割

基于最大類間方差的Otsu算法是由日本學(xué)者大津提出的一種自適應(yīng)的閾值選擇方法，其基本原理是根據(jù)圖像的灰度直方圖，以目標(biāo)和背景之間的類間方差最大為準(zhǔn)則來確定圖像的分割閾值[9]。

對于一幅圖像(大小為M×N)，灰度級為L，各個灰度值為0到L-1，灰度值為i的像素總數(shù)為ni，像素總數(shù)可以表示為：

(1)

任意像素灰度值為i出現(xiàn)的概率為：

(2)

設(shè)閾值t將整幅圖像分為前景和背景兩部分，則類間方差σB2是t的函數(shù)：

σB2(t) =P0×(m0-mG)2+P1×(m1-mG)2

(3)

將其推廣到多閾值中，假設(shè)要將圖像分成n部分，則閾值可以表示為T=(T1,T2,…，Tn-1)。對于這n個部分來說，每部分總像素出現(xiàn)概率分別是P0,P1,…,Pn-1。其中：

(4)

(5)

圖像的灰度均值為：

(6)

類間方差為：

(7)

圖像的類間方差越大，分割效果越好，所以使σB2(T)達到最大的閾值組合即為所求的最優(yōu)閾值。Otsu方法的本質(zhì)是采用窮舉法選取最佳閾值組合，其不足是隨著閾值個數(shù)的增加，計算量會以指數(shù)形式增長，為提高算法的運行效率，現(xiàn)采用基于混沌初始化和反向?qū)W習(xí)策略的改進蜻蜓算法對選取多閾值的過程加以優(yōu)化。

2 蜻蜓算法

為了使蜻蜓算法更快地收斂于全局最優(yōu)，其搜索半徑會隨迭代次數(shù)的增加而線性遞增，直到整個蜻蜓群體全部相鄰。

利用DA算法求解優(yōu)化問題的思路為：在N維空間中初始化產(chǎn)生個體數(shù)量為m的蜻蜓種群，種群中第i(i=1,2,…,m)個蜻蜓的位置表示Xi=(Xi1,Xi2,…,XiN)，通過計算蜻蜓種群對應(yīng)的適應(yīng)度函數(shù)值f(x)并加以比較，選擇當(dāng)前適應(yīng)度值最大的蜻蜓位置作為食物源的位置，適應(yīng)度值最小的蜻蜓位置作為天敵的位置，然后根據(jù)蜻蜓的5種行為更新當(dāng)前個體所在位置。具體公式如下：

1)分離行為:避免蜻蜓和相鄰個體之間發(fā)生碰撞。

(8)

式中：X是當(dāng)前蜻蜓所在位置；Xj是第j個相鄰蜻蜓所在位置；W是鄰近蜻蜓的個數(shù)。

2) 結(jié)隊行為：相鄰個體之間趨于相同的速度。

(9)

式中：Vj是第j個相鄰蜻蜓的速度。

3)聚集行為：蜻蜓傾向于向相鄰個體的中心聚攏。

(10)

4)覓食行為：食物對蜻蜓的吸引力。

Fi=X+-X

(11)

式中：X+是食物源所在位置。

5)避敵行為：蜻蜓對天敵的排斥力。

Ei=X-+X

(12)

式中：X-是天敵所在位置。

步長向量指示蜻蜓的步長和運動方向，其定義如下：

ΔXt+1=(sSi+aAi+cCi+fFi+eEi+ωΔXt)

(13)

式中：s、a、c、f、e分別對應(yīng)于5種行為的權(quán)重；ω是慣性權(quán)重；t是當(dāng)前迭代次數(shù)。

當(dāng)兩個蜻蜓之間的歐氏距離小于搜索半徑r，則認為兩個蜻蜓是相鄰的；反之則不相鄰，此時蜻蜓通過隨機游走的方式圍繞搜索空間飛行。

搜索半徑r的定義如下：

r=Δb/4+(Δb×(t/max_iteration)×2)

(14)

式中：Δb=ub-lb,ub和lb分別表示搜索半徑的上界和下界；max_iteration為最大迭代次數(shù)。

蜻蜓位置向量的計算如下：

當(dāng)有鄰近蜻蜓時：Xt+1=Xt+ΔXt+1

(15)

當(dāng)無鄰近蜻蜓時：Xt+1=Xt+Levy(d)×Xt(16)

式中：t是當(dāng)前迭代次數(shù)；d表示位置向量的維度。

(17)

式中：r1和r2是[0,1]內(nèi)的隨機數(shù)；β為常數(shù)，這里取值為1.5。

(18)

3 改進蜻蜓算法

3.1 混沌初始化

種群初始化對DA算法的求解精度和收斂速度起著至關(guān)重要的作用。標(biāo)準(zhǔn)DA算法初始化時一般是采取隨機初始化的方法來確定蜻蜓的位置和移動步長，存在的弊端是當(dāng)蜻蜓遠離食物源時會影響收斂速度?；煦邕\動具有規(guī)律性、隨機性和遍歷性等特點，這個過程不收斂但有界，并對外部參數(shù)和初始值極其敏感，所以基于混沌的種群初始化可以在一定范圍內(nèi)按自身規(guī)律不重復(fù)地遍歷搜索空間，使算法在求解精度和收斂速度方面得到顯著的提升[10]。這里選用Logistic映射方程進行種群初始化操作，其表達式如下：

cxn+1=μcxn(1-cxn)

(19)

式中：μ∈(0,4]，cxn∈(0,1)，μ越大混沌性越高，μ=4時系統(tǒng)完全處于混沌狀態(tài)。

x(i,j)=xmin+rand(i,j)×(xmax-xmin)

(20)

混沌初始化種群的基本原理：首先給定一個cx初值，通過式(19)Logistic映射方程產(chǎn)生初始化所需要的混沌變量，然后利用混沌變量取代標(biāo)準(zhǔn)初始化方程中的隨機數(shù)，即式(20)中的rand(i,j)，直到遍歷完所有蜻蜓個體的每一維度為止。

3.2 反向?qū)W習(xí)策略

反向?qū)W習(xí)是由Tizhoosh在2005年提出的一種優(yōu)化學(xué)習(xí)策略，同時根據(jù)概率定理證明每個隨機產(chǎn)生的候選解有50%的概率比它的反向解更靠近最優(yōu)解[11]。本文應(yīng)用反向?qū)W習(xí)策略的主要思想是：在DA算法迭代尋優(yōu)過程中設(shè)置一個反向概率p，每次迭代執(zhí)行完蜻蜓種群更新后，產(chǎn)生一個0到1的隨機數(shù)r3，若r3>p則結(jié)合反向?qū)W習(xí)策略優(yōu)化種群。在搜索空間中通過當(dāng)前個體產(chǎn)生反向個體，并從兩者中選擇較優(yōu)秀的個體進入下一代，從而吸引種群向最優(yōu)個體逼近，在增大隨機性的同時降低算法復(fù)雜度，公式如下：

(21)

3.3 算法描述

混沌初始化策略能夠提高初始蜻蜓種群的質(zhì)量和種群分布的隨機性，反向?qū)W習(xí)策略能夠增加蜻蜓種群多樣性，通過比較選取其中適應(yīng)度較好的個體，可以增強算法的尋優(yōu)能力，提高種群進化速度和算法的運行效率，其流程如圖1所示。

圖1 改進蜻蜓算法流程圖

改進蜻蜓算法(IDA)的基本步驟如下：

Step1隨機生成種群規(guī)模為m初始種群，利用式(19)和式(20)混沌初始化每個粒子的位置，預(yù)先設(shè)定算法執(zhí)行所需參數(shù)。

Step2計算出每個蜻蜓的適應(yīng)度值f(i)，從中選出最優(yōu)個體的位置定義為食物源的位置，其適應(yīng)度值為ffood；選出最差的個體的位置定義為天敵的位置，其適應(yīng)度值為fenemy。

Step3更新參數(shù)，其中包括搜索半徑r,慣性權(quán)重w,分離度權(quán)重s，對齊度權(quán)重a,凝聚度權(quán)重c,食物吸引度權(quán)重f和天敵驅(qū)散度權(quán)重e。

Step4計算步長向量，當(dāng)有鄰近蜻蜓時根據(jù)式(15)更新蜻蜓的位置；當(dāng)無鄰近蜻蜓時根據(jù)式(16)更新蜻蜓的位置，同時將其限制在最大范圍[0,L-1]內(nèi)。

Step5將更新后的各蜻蜓的位置代入適應(yīng)度函數(shù)得到新的適應(yīng)度值f(i+1)。

Step6若rand>p，則根據(jù)式(21)執(zhí)行反向?qū)W習(xí)操作，并在當(dāng)前個體與反向個體中擇優(yōu)選出進入下一代的個體。

Step7將個體的適應(yīng)度值分別與最優(yōu)值ffood和最差值fenemy比較，若優(yōu)于ffood則將其更新食物的位置，若差于fenemy則更新天敵的位置。

Step8判斷是否滿足終止迭代的條件，若滿足則退出循環(huán)，否則轉(zhuǎn)向Step3。

4 伯克利經(jīng)典圖像分割實驗

4.1 實驗背景

多閾值的圖像分割可以看成一種單目標(biāo)優(yōu)化問題，結(jié)合群智能優(yōu)化算法的尋優(yōu)過程實際上是求解Otsu算法多閾值適應(yīng)度函數(shù)的最優(yōu)閾值組合。實驗選取6幅伯克利經(jīng)典圖像進行分析研究，并與SCA、PSO、BA、HSO和ALO算法進行比較。本文通過峰值信噪比(PSNR)、特征相似性(FSIM)、結(jié)構(gòu)相似性(SSIM)、適應(yīng)度函數(shù)值及運行時間這5種指標(biāo)來評估IDA算法與其他5種算法的性能差異。

峰值信噪比(PSNR)是基于對應(yīng)像素點間的誤差來衡量圖像失真程度的指標(biāo)，PSNR的值越大，圖像的失真程度越小[12]。其定義如下：

(22)

式中：MSE表示原圖像與分割圖像的均方誤差。

特征相似性(FSIM)是一種基于圖像的相位一致性和與圖像的空域梯度特征來評價圖像質(zhì)量的指標(biāo)[13]。其定義如下：

(23)

式中：Ω表示圖像的整個空域；SL(x)用來評價圖像的相似性；PCm(x)表示相位相似性。

PCm(x)=max(PC1(x),PC2(x))

(24)

式中：PC1(x)和PC2(x)分別表示參考圖像和被評測圖像的相位一致性。

SL(x)=[SPC(x)]α·[SG(x)]β

(25)

式中：

(26)

(27)

其中：SPC(x)表示圖像的特征相似性；SG(x)表示圖像的梯度相似性；G1(x)和G2(x)分別表示參考圖像和被評測圖像的梯度幅值、α、β、T1和T2均為常量。

結(jié)構(gòu)相似性(SSIM)是利用圖像的亮度，對比度和結(jié)構(gòu)信息的冪乘積作為測度來客觀評價圖像的質(zhì)量，其范圍為0到1，其值越大，說明分割后的圖像與原圖像越相似[14]。其定義如下：

(28)

算法的實驗環(huán)境為Windows10-64bit，1.6 GHz處理器和8 GB內(nèi)存，編程環(huán)境為MATLAB 2014b。為了客觀對比IDA算法與其他5種算法的綜合性能，充分考慮算法的隨機性對實驗結(jié)果的影響，實驗時的各參數(shù)設(shè)置如下：粒子數(shù)目n=30，最大迭代次數(shù)tmax=500，各算法特性參數(shù)設(shè)置如表1所示。

表1 各算法參數(shù)設(shè)置

4.2 實驗設(shè)計

為了驗證本文優(yōu)化算法在處理多閾值圖像分割問題時的優(yōu)勢，在伯克利圖像庫中隨機選取6幅標(biāo)準(zhǔn)圖像，灰度圖像如圖2所示。以類間方差函數(shù)作為每種算法的適應(yīng)度函數(shù)，同時利用優(yōu)化算法對6幅圖像多閾值分割時的閾值選取過程加以優(yōu)化。本次實驗對每幅圖像分別進行4個、6個、8個和10個這4種類型的多閾值圖像分割。

圖2 伯克利灰度圖像

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

5.1 圖像分割精準(zhǔn)度

本文選用PSNR、FSIM、SSIM 和最優(yōu)適應(yīng)度值4個指標(biāo)對各算法圖像分割的精準(zhǔn)度進行定量分析，數(shù)據(jù)結(jié)果如表2-表5所示。首先分析峰值信噪比PSNR指標(biāo),它是基于圖像的灰度值來衡量圖像失真程度的指標(biāo)，PSNR的值越大，圖像的失真程度越低。當(dāng)分割閾值個數(shù)為4或6時，各種優(yōu)化算法的PSNR的值相差較小，但IDA算法仍具有一定優(yōu)勢。當(dāng)閾值分割個數(shù)為8或10時，對于Worker和Massif等這類復(fù)雜的圖像，IDA算法得到了很有競爭力的結(jié)果。例如：對Massif圖像進行10閾值分割時IDA、PSO、SCA、BA、HSO和ALO對應(yīng)的取值分別為28.693 9、26.366 9、27.388 1、26.363 9、27.020 2，直觀地表現(xiàn)出基于IDA算法分割的圖像與其他5種算法相比失真程度小。這說明IDA算法不僅能夠解決多維函數(shù)極值求解的問題，而且在圖像分割領(lǐng)域也有很強的工程實用性。

表2 各算法PSNR指標(biāo)

表3 各算法FSIM指標(biāo)

表4 各算法SSIM指標(biāo)

表5 各算法最優(yōu)適應(yīng)度函數(shù)值

其次對特征相似性FSIM指標(biāo)進行分析，它是基于圖像的相位一致性特征與圖像的空域梯度特征來評價圖像的質(zhì)量的一種指標(biāo)。從表3中的數(shù)據(jù)可以看出，基于IDA算法的多閾值圖像分割得到了較高的FSIM值，隨著閾值個數(shù)的增加，IDA算法的優(yōu)越性越來越顯著。例如，在對Worker這幅圖像進行4個、6個、8個和10個這4種類型的分割時，IDA算法得到的FSIM值分別為0.782 2、0.860 1、0.909 3、0.939 4，得到的值越來越接近于1，其他算法與IDA算法的差距也與越來越明顯，表現(xiàn)出IDA算法尋優(yōu)精度高的優(yōu)點，可以得到較好的分割閾值組合，從而獲得高質(zhì)量的多閾值彩色分割圖像。

然后對結(jié)構(gòu)相似性SSIM進行分析，它是一種利用亮度、對比度和結(jié)構(gòu)信息的冪乘積作為測度來評價圖像的指標(biāo)。從表4中可以看出，對同一幅待分割的圖像，本文算法得到了最高值。同時，隨著分割閾值個數(shù)的增加，SSIM的值在不斷增大，各算法可以更加準(zhǔn)確地分割出圖像中的主要目標(biāo)，而且包含更多信息，從視覺上更加接近原圖像，其中IDA算法的效果最為顯著。例如：IDA、PSO、SCA、BA、HSO和ALO算法對Giraffe的6閾值分割結(jié)果分別為0.677 8、0.677 3、0.670 0、0.669 1、0.676 0、0.670 0；對Weasel的10閾值分割結(jié)果分別為0.902 1、0.888 0、0.892 1、0.867 3、0.864 4、0.889 5。再次表現(xiàn)出基于IDA算法的多閾值圖像分割可以獲得與原圖像更加相似的圖像，能很好地完成圖像分割的任務(wù)。

最后對各算法的最優(yōu)適應(yīng)度值加以分析：由表5可知，本文算法在這6種算法中所獲得的值最大。適應(yīng)度函數(shù)值表示的是圖像分成的若干個部分間的類間方差，最優(yōu)適應(yīng)度值越大，圖像分割的質(zhì)量也就越高，抗噪性也會不斷提高。例如，IDA、PSO、SCA、BA、HSO和ALO算法對Bridge圖像進行4閾值分割的最優(yōu)適應(yīng)度函數(shù)值分別為8 287.094 2、8 286.998 1、8 281.841 7、8 286.150 4、8 286.328 3、8 287.049 0。雖然ALO算法在閾值個數(shù)較少時，與IDA算法差異很小，獲得的圖像分割質(zhì)量較好，但隨著閾值個數(shù)的增加，ALO易陷于局部最優(yōu),影響圖像分割的效果。這說明改進后的蜻蜓算法的尋優(yōu)能力明顯提升，能夠有效地跳出局部最優(yōu)，更穩(wěn)定快速地收斂于全局最優(yōu)解，從而獲得理想分割閾值。

5.2 運行時間

由表6可知，對于同一幅待分割的圖像，在設(shè)置相同的閾值個數(shù)時，本文算法運行時間最短，SCA算法所消耗的時間略高于IDA，ALO算法的運行時間最長。隨著閾值個數(shù)的增加，各算法的運行都在不斷增加，但IDA算法仍具有一定優(yōu)勢，說明本文算法可以有效提高效率，能夠較快地完成多閾值彩色圖像分割任務(wù)。

表6 各算法運行時間

綜上所述，本文從圖像分割精度和運行時間這兩方面對6種優(yōu)化算法的性能進行對比分析，SCA算法的運行時間雖然和IDA算法差距較小，但其分割精度并不理想；ALO算法雖然可以獲得精度較高的分割圖像，但其運行時間不占優(yōu)勢。本文提出的IDA算法的優(yōu)越性在于不僅提高了多閾值圖像分割的質(zhì)量,而且算法的運行效率也顯著提高，從而驗證了IDA算法在彩色圖像分割問題中的有效性和正確性，能夠勝任復(fù)雜圖像的處理任務(wù)。

6 結(jié) 語

通過引入混沌初始化和反向?qū)W習(xí)策略，本文提出了一種基于改進蜻蜓算法的多閾值彩色圖像分割技術(shù)，以類間方差函數(shù)作為IDA算法的適應(yīng)度函數(shù)，利用蜻蜓種群的兩種行為：覓食行為和遷徙行為來快速搜尋圖像多閾值分割時的最佳閾值。實驗結(jié)果表明，對同一待分割的圖像，在設(shè)置相同的閾值分割個數(shù)時，IDA算法與其他5種算法相比，在全局搜索和快速收斂能力、圖像分割精度、運行時間等方面都表現(xiàn)出顯著的優(yōu)越性。此次實驗隨機地從伯克利圖庫中隨機選取6幅圖像，可以看出本文算法對不同類型的彩色圖像能夠達到實時性處理與分析的要求，具有很好的實用價值。