基于改進(jìn)非洲禿鷲優(yōu)化算法的圖像閾值分割研究

張嘯宇, 方忠慶, 杜 義, 孔維賓, 王玉婷, 程子耀

(鹽城工學(xué)院信息工程學(xué)院, 江蘇 鹽城 224051)

0 引言(Introduction)

元啟發(fā)式算法是一類獨(dú)立于問(wèn)題的優(yōu)化算法,能夠有效探索一個(gè)搜索空間并找到全局最優(yōu)解。這類算法主要通過(guò)模擬自然界優(yōu)勝劣汰的規(guī)律以及生物行為,實(shí)現(xiàn)種群的整體進(jìn)步,最終求解最優(yōu)解。典型算法有遺傳算法(GA)[1]、差分進(jìn)化算法(DE)[2]、粒子群算法(PSO)[3]、灰狼算法(GWO)[4]、鯨魚優(yōu)化算法(WOA)[5]、金豺狼優(yōu)化算法(GJO)[6]等。

按閾值對(duì)圖像分割是一種常用的圖像分割方法,目前國(guó)內(nèi)外已經(jīng)有很多學(xué)者將元啟發(fā)式算法用于圖像的閾值分割優(yōu)化中。KHAIRUZZAMAN等[7]將灰狼優(yōu)化算法應(yīng)用于圖像的多級(jí)閾值分割,取得了很好的效果。于洋等[8]為了解決紅外相機(jī)采集行人圖片時(shí)圖像分割效果問(wèn)題,提出一種自適應(yīng)粒子群優(yōu)化二維OSTU的閾值分割算法,能夠快速且準(zhǔn)確地得到最佳閾值,提高了圖像預(yù)處理的分割效果。UPADHYAY等[9]將Kapur熵作為適應(yīng)度函數(shù),并通過(guò)烏鴉搜索算法求得最大Kapur熵,達(dá)到最優(yōu)閾值。

非洲禿鷲算法(AVOA)[10]是受非洲禿鷲覓食和導(dǎo)航行為啟發(fā)而提出的高性能智能算法,具有求解精度高的優(yōu)點(diǎn),但其全局搜索能力弱、易陷入局部。本文通過(guò)分段線性混沌映射(PWLCM)進(jìn)行種群初始化,增強(qiáng)種群多樣性;在全局搜索階段引入β分布更好地控制種群在搜索空間上的重新劃分;提出了新的基于饑餓率的全局搜索策略,用于增強(qiáng)算法搜索能力。將改進(jìn)算法運(yùn)用在二維Otsu圖像閾值分割任務(wù)中取得了不錯(cuò)的效果。

1 基礎(chǔ)非洲禿鷲優(yōu)化算法(Basic African Vulture Optimization Algorithm)

非洲禿鷲優(yōu)化算法(AVOA)是通過(guò)對(duì)非洲禿鷲的覓食行為和生活習(xí)慣進(jìn)行模擬和建模而提出的。在AVOA中,非洲禿鷲的生活習(xí)慣和覓食行為主要包括以下4個(gè)階段。

1.1 階段一:隨機(jī)選擇最佳禿鷲

初始化種群后首先計(jì)算種群的適應(yīng)度,其次選擇最優(yōu)個(gè)體為最優(yōu)禿鷲,選擇次優(yōu)個(gè)體作為次優(yōu)禿鷲。每次的最佳禿鷲會(huì)在這兩個(gè)個(gè)體中通過(guò)如下公式計(jì)算產(chǎn)生,同時(shí)在每次更新迭代后重新計(jì)算整個(gè)總體。

(1)

其中,L1和L2為搜索操作之前給定的參數(shù),其值介于0～1且兩個(gè)參數(shù)之和為1。選擇最優(yōu)解的概率pi使用如下公式的輪盤賭方式獲得,并為每組選擇最優(yōu)解。

(2)

1.2 階段二:計(jì)算禿鷲的饑餓率

禿鷲的饑餓率由如下公式計(jì)算得出:

(3)

(4)

其中,F表示禿鷲的饑餓率,l表示當(dāng)前的迭代次數(shù),maxiterations表示最大迭代次數(shù),z為介于-1～1且每代變化的隨機(jī)數(shù),h是介于-2～2的隨機(jī)數(shù),rand1是介于0～1的隨機(jī)數(shù)。

同時(shí),當(dāng)F的絕對(duì)值大于1時(shí),算法進(jìn)入探索階段;當(dāng)F的值小于或等于1時(shí),算法進(jìn)入開發(fā)階段。

1.3 階段三:探索

AVOA的探索階段禿鷲有兩種不同的搜索策略,在兩組最佳禿鷲之一的周圍區(qū)域?qū)ふ沂澄锖透鶕?jù)其饑餓程度在環(huán)境中隨機(jī)搜索。

P(i+1)=R(i)-D(i)×F

(5)

D(i)=|X×R(i)-P(i)|

(6)

公式(5)模擬了在兩組最佳禿鷲之一的周圍區(qū)域?qū)ふ沂澄?其中P(i+1)為下一次迭代的位置,F是由公式(4)計(jì)算得出的禿鷲的饑餓率,R(i)是由公式(1)給出的最佳禿鷲,D(i)為到兩組最佳禿鷲之一的隨機(jī)距離,通過(guò)公式(6)計(jì)算得到。在公式(6)中,R(i)是由公式(1)給出的最佳禿鷲。X被用作增加隨機(jī)運(yùn)動(dòng)的系數(shù)向量,由X=2×rand計(jì)算得到,其中rand為介于0～1的隨機(jī)數(shù)。P(i)為當(dāng)前禿鷲的位置。

P(i+1)=R(i)-F+rand2×((ub-lb)×rand3+lb)

(7)

公式(7)模擬了禿鷲根據(jù)其饑餓程度在環(huán)境中隨機(jī)搜索,其中rand2是介于0～1的隨機(jī)值,lb和ub表示變量的上界和下界,rand3是用于增加隨機(jī)性的系數(shù)。

這兩種策略會(huì)根據(jù)P1的值進(jìn)行選擇,P1是介于0～1的數(shù)。設(shè)randP1為介于0～1的隨機(jī)數(shù)。如果randP1的值小于或等于P1,則使用公式(5),反之,使用公式(7)。

1.4 階段四:開發(fā)

1.4.1 開發(fā)(第一階段)

當(dāng)F的絕對(duì)值介于0.5～1時(shí),AVOA進(jìn)入開發(fā)階段的第一階段。在開發(fā)階段的第一階段,執(zhí)行緩慢圍攻和旋轉(zhuǎn)飛行兩種不同的策略。

(1)緩慢圍攻:當(dāng)|F|≥0.5時(shí),禿鷲相對(duì)能量充足。當(dāng)許多禿鷲聚集在一個(gè)食物源上時(shí),會(huì)在食物獲取上引起嚴(yán)重的沖突。身體強(qiáng)壯的禿鷲不喜歡分享食物,而弱小的禿鷲試圖聚集并引發(fā)小沖突以便獲取食物,如下兩個(gè)公式模擬了這兩個(gè)過(guò)程。

P(i+1)=D(i)×(F+rand4)-d(t)

(8)

d(t)=R(i)-P(i)

(9)

公式(8)中,D(i)為到兩組最佳禿鷲之一的隨機(jī)距離,通過(guò)公式(6)計(jì)算得出,rand4為介于0～1的隨機(jī)值。公式(9)中,R(i)是在當(dāng)前迭代中使用公式(1)選擇的最佳禿鷲。

(2)旋轉(zhuǎn)飛行:禿鷲經(jīng)常進(jìn)行旋轉(zhuǎn)飛行,可用于模擬螺旋運(yùn)動(dòng)。所有禿鷲與最佳和次佳禿鷲中的一只建立了一個(gè)螺旋方程,公式如下所示:

(10)

(11)

P(i+1)=R(i)-(S1+S2)

(12)

其中,rand5和rand6是介于0～1的隨機(jī)數(shù),最后通過(guò)公式(12)更新禿鷲的位置。

這兩種策略會(huì)根據(jù)P2的值進(jìn)行選擇,P2是介于0～1的數(shù)。設(shè)randP2為介于0～1的隨機(jī)數(shù)。如果randP2的值小于或等于P2,則根據(jù)公式(8)實(shí)施緩慢圍攻策略,反之,使用公式(12)執(zhí)行旋轉(zhuǎn)飛行策略。

1.4.2 開發(fā)(第二階段)

當(dāng)|F|<0.5時(shí),AVOA進(jìn)入開發(fā)階段的第二階段,禿鷲開始進(jìn)行聚集圍攻和爭(zhēng)奪食物。

(1)幾種禿鷲在食物源上的聚集。

描述禿鷲這種運(yùn)動(dòng)的公式如下所示:

(13)

(14)

(15)

公式(13)和公式(14)中,BestVulture1(i)是當(dāng)前迭代中第一組的最佳禿鷲,BestVulture2(i)是當(dāng)前迭代中第二組的最佳禿鷲。用公式(15)計(jì)算得到下一代禿鷲的位置P(i+1)。

(2)對(duì)食物的激烈競(jìng)爭(zhēng)。

當(dāng)|F|<0.5時(shí),領(lǐng)頭的禿鷲變得饑餓和虛弱,沒(méi)有足夠的能量對(duì)抗其他禿鷲。而其他禿鷲會(huì)從不同方向朝著領(lǐng)頭禿鷲的位置移動(dòng),可以使用如下公式模擬該現(xiàn)象:

P(i+1)=R(i)-|d(t)|×F×Levy(d)

(16)

其中,d(t)表示禿鷲與兩組中最佳禿鷲之間的距離,該距離通過(guò)公式(9)計(jì)算得出。萊維飛行機(jī)制用于提高公式(16)中AVOA算法的有效性,萊維飛行生成的隨機(jī)分量用以下公式計(jì)算。

(17)

其中

(18)

公式(17)、公式(18)中,α為固定值1.5。u和v服從正態(tài)分布:

(19)

第二階段的兩種策略會(huì)根據(jù)P3的值進(jìn)行選擇,P3是介于0～1的數(shù)。設(shè)randP3是介于0～1的隨機(jī)數(shù),如果randP3小于或等于P3,則根據(jù)公式(15)更新位置;反之由公式(16)實(shí)施對(duì)食物的激烈競(jìng)爭(zhēng)。

2 改進(jìn)非洲禿鷲優(yōu)化算法(Improved African Vulture Optimization Algorithm)

針對(duì)非洲禿鷲算法全局搜索能力不足、局部搜索策略冗余及收斂速度慢等缺點(diǎn),β-PAVOA主要做了以下改進(jìn)。

2.1 基于PWLCM混沌映射的種群初始化

混沌映射是生成混沌序列的一種方法,被廣泛地應(yīng)用于各種算法中。PWLCM[11]作為混沌映射的典型代表,其數(shù)學(xué)形式簡(jiǎn)單,具有遍歷性和隨機(jī)性。如圖1所示,PWLCM在空間中的分布非常均勻。

(a)PWLCM混沌映射圖

通過(guò)PWLCM初始化種群,可以使β-PAVOA在初始化種群時(shí)更好地搜索整個(gè)解空間。PWLCM映射的描述如公式(20)所示:

(20)

公式(20)中,PZ=0.4,如果t≥2,則z(t)值可根據(jù)公式(20)計(jì)算得到,如果t=1,則z(1)為映射的初始值,z(1)取值是介于0～1的隨機(jī)數(shù)。

將生成的值映射到解空間,如下公式所示:

P(i)=(ub-lb)×z(i)+lb

(21)

其中,P(i)是映射后的種群位置,ub和lb分別是位置的上界和下界,z(i)是由公式(20)得到介于0～1的混沌映射隨機(jī)值。

2.2 基于β分布的全局增強(qiáng)搜索策略

β分布[12]是指一組定義在區(qū)間[0,1]的連續(xù)概率分布。在使用元啟發(fā)式算法解決工程問(wèn)題時(shí),將β分布用于其中很有效,它可以近似模擬包括正態(tài)高斯分布在內(nèi)的幾種分布,也允許近似線性或指數(shù)遞減的分布,可以是一維的,也可以是多維。一維β分布表達(dá)式如下:

(22)

(23)

其中,通過(guò)改變參數(shù)p和q就可以得到可能的β分布的多樣性?；讦路植嫉娜衷鰪?qiáng)搜索策略如公式(24)所示:

P(i+1)=(ub-lb)×betarand+lb

(24)

其中,P(i+1)為更新后的位置,betarand是p=1、q=1的情況下生成的β隨機(jī)數(shù)。

2.3 基于饑餓率F的改進(jìn)搜索策略

在測(cè)試過(guò)程中發(fā)現(xiàn),AVOA在探索階段的全局搜索表現(xiàn)不佳,因此提出了基于禿鷲饑餓率的改進(jìn)搜索策略如公式(25)所示,用于改善這一問(wèn)題。

P(i+1)=(rand-F)×X(randi(1,pop_size))

(25)

其中,P(i+1)為更新后的位置,rand為介于0～1的隨機(jī)值。X為種群的歷史最優(yōu)位置,randi(1,pop_size)為1至種群大小之間的隨機(jī)整數(shù)值。

2.4 改進(jìn)局部搜索策略

β-PAVOA針對(duì)局部搜索策略冗余、收斂慢的缺點(diǎn),對(duì)開發(fā)階段策略進(jìn)行了精簡(jiǎn),整個(gè)開發(fā)階段只使用AVOA在開發(fā)階段的第二階段中的更新策略,rand是介于0～1的隨機(jī)數(shù)。如果rand小于0.3,則根據(jù)公式(15)更新位置;反之由公式(16)實(shí)施對(duì)食物的激烈競(jìng)爭(zhēng)。β-PAVOA的算法流程如圖2所示。

3 實(shí)驗(yàn)仿真與結(jié)果分析(Experimental simulation and result analysis)

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

β-PAVOA在8個(gè)基準(zhǔn)測(cè)試函數(shù)上進(jìn)行了測(cè)試,選取了非洲禿鷲算法(AVOA)、金豺狼優(yōu)化算法(GJO)、灰狼算法(GWO)、鯨魚優(yōu)化算法(WOA)和粒子群算法(PSO)作為對(duì)比算法。測(cè)試函數(shù)分為兩類:F1～F4為單峰函數(shù),F5～F8為多峰函數(shù),測(cè)試函數(shù)設(shè)置見表1,算法默認(rèn)參數(shù)設(shè)置見表2。將測(cè)試結(jié)果進(jìn)行秩和檢驗(yàn),確定β-PAVOA獲得結(jié)果的平均值與對(duì)比算法之間是否存在顯著差異,當(dāng)ρ>0.05時(shí),認(rèn)為β-PAVOA與對(duì)比算法的尋優(yōu)性能相當(dāng)。種群大小設(shè)置為50,最大迭代次數(shù)為1 000次,測(cè)試維度為30。為了減少不確定性,每個(gè)測(cè)試獨(dú)立進(jìn)行30次,計(jì)算30次測(cè)試的平均數(shù)和方差。實(shí)驗(yàn)是在配備32 GB RAM與i7-12700H處理器的個(gè)人計(jì)算機(jī)上進(jìn)行的。

表1 測(cè)試函數(shù)設(shè)置Tab.1 Benchmark function settings

表2 算法參數(shù)設(shè)置Tab.2 Algorithm parameter settings

3.2 精度與收斂性分析

β-PAVOA與其他算法的測(cè)試結(jié)果見表3和表4。在F1～F8上,β-PAVOA展現(xiàn)出了極強(qiáng)的優(yōu)勢(shì),從表3和表4中可以看出,相比其他算法在F3、F4、F7、F8上的測(cè)試結(jié)果,β-PAVOA有著領(lǐng)先幾個(gè)量級(jí)的精度,在F1、F2、F5、F6上的測(cè)試結(jié)果相近的情況下,其穩(wěn)定性有著明顯的優(yōu)勢(shì)。同時(shí),從圖3和圖4中的算法收斂曲線可以明顯看出,β-PAVOA在F1～F8上的收斂精度與收斂速度均優(yōu)于其他算法。

表3 各類算法在 F1～F4上的測(cè)試結(jié)果Tab.3 Test results of various algorithms on F1～F4

表4 各類算法在F5～F8上的測(cè)試結(jié)果Tab.4 Test results of various algorithms on F5～F8

(a)F1函數(shù)的收斂對(duì)比曲線

(b)F2函數(shù)的收斂對(duì)比曲線

(c)F3函數(shù)的收斂對(duì)比曲線

(d)F4函數(shù)的收斂對(duì)比曲線圖3 不同算法的F1～F4收斂曲線對(duì)比Fig.3 Comparison of convergence curves of different algorithms on F1～F4

(a)F5函數(shù)的收斂對(duì)比曲線

(b)F6函數(shù)的收斂對(duì)比曲線

(c)F7函數(shù)的收斂對(duì)比曲線

(d)F8函數(shù)的收斂對(duì)比曲線圖4 不同算法的F5～F8收斂曲線對(duì)比Fig.4 Comparison of convergence curves of different algorithms on F5～F8

4 Otsu圖像閾值分割(Otsu image threshold segmentation)

Otsu閾值分割常用于圖像二值化或閾值化[13]。圖像閾值化是將灰度圖像轉(zhuǎn)換為二值圖像的過(guò)程,其中每個(gè)像素根據(jù)特定的閾值被賦予黑色或白色值。Otsu閾值分割法簡(jiǎn)單高效,適用于分割、目標(biāo)檢測(cè)和特征提取[14]。Otsu閾值分割法在具有雙峰直方圖的圖像上效果最好,即圖像中有清晰的表示背景和前景像素強(qiáng)度的峰值。對(duì)于具有更復(fù)雜分布的圖像,其他閾值化方法或更高級(jí)的技術(shù)可能更合適。

Otsu閾值分割法是找到能夠使類間方差最大化的閾值,從而有效地將像素分為兩個(gè)類別:前景和背景。類間方差測(cè)量?jī)蓚€(gè)類之間的擴(kuò)展或可分性,并根據(jù)圖像中的像素強(qiáng)度和概率計(jì)算。

4.1 Otsu閾值分割

假設(shè)圖形大小為M×N,圖像灰度范圍為[0,L-1],ni為圖像灰度級(jí)i的像素點(diǎn)數(shù),則灰度級(jí)i出現(xiàn)的概率為pi=ni/(M×N)。在單閾值分割模型中,圖像被分割成兩類,其中C0類像素點(diǎn)灰度級(jí)為[0,T],C1類像素點(diǎn)灰度級(jí)為[T+1,L-1]。P0(T)、P1(T)分別為C0、C1出現(xiàn)的概率,u0(T)、u1(T)分別為C0、C1的平均灰度級(jí),由如下公式計(jì)算得出:

(26)

(27)

(28)

(29)

(30)

(32)

4.2 Otsu多閾值分割

(33)

(34)

(35)

(36)

(37)

圖像的類間方差用公式(36)表示,公式(37)則是最終的目標(biāo)函數(shù)。

4.3 二維Otsu模型測(cè)試結(jié)果及分析

在二維Otsu模型測(cè)試中測(cè)試了β-PAVOA及對(duì)比算法的性能表現(xiàn),測(cè)試選取了2張常用測(cè)試圖片與1張內(nèi)容復(fù)雜的圖片(如圖5所示)。測(cè)試結(jié)果如圖6所示,β-PAVOA在找到最優(yōu)解時(shí),收斂速度與穩(wěn)定性相比其他算法有明顯的優(yōu)勢(shì),這也驗(yàn)證了優(yōu)化策略的有效性。

(a)相機(jī)

(b)人像

(c)月球圖5 測(cè)試用圖Fig.5 The text pictures

(a)相機(jī)二維Otsu測(cè)試結(jié)果

(b)相機(jī)二維Otsu模型迭代曲線

(d)人像二維Otsu模型迭代曲線

(e)月球二維Otsu測(cè)試結(jié)果

(f)月球二維Otsu模型迭代曲線圖6 測(cè)試結(jié)果圖Fig.6 The test results graph

5 結(jié)論(Conclusion)

本文提出了一種基于PWLCM與β分布的非洲禿鷲算法β-PAVOA。首先,通過(guò)PWLCM擴(kuò)大種群在解空間的覆蓋程度,提高尋優(yōu)能力。其次,使用基于β分布的全局增強(qiáng)搜索策略增強(qiáng)算法的全局搜索能力?；陴囸I率F的改進(jìn)搜索策略進(jìn)一步增強(qiáng)了全局搜索能力。最后,通過(guò)簡(jiǎn)化局部搜索策略提升局部收斂速度。為了驗(yàn)證β-PAVOA的有效性,通過(guò)8個(gè)基準(zhǔn)測(cè)試函數(shù)和二維Otsu圖像閾值分割模型與非洲禿鷲算法(AVOA)、金豺狼優(yōu)化算法(GJO)、灰狼算法(GWO)、鯨魚優(yōu)化算法(WOA)和粒子群算法(PSO)進(jìn)行對(duì)比實(shí)驗(yàn),采用均值、標(biāo)準(zhǔn)差與秩和檢驗(yàn)方法進(jìn)行評(píng)估。結(jié)果表明,β-PAVOA算法在探索能力和求解精度上都有顯著優(yōu)勢(shì)。