基于改進飛蛾撲火算法的多閾值彩色圖像分割

馬 軍 賈鶴鳴

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

0 引 言

圖像分割是圖像處理中的重要技術(shù)，是計算機視覺領(lǐng)域的前沿研究方向，是圖像分析中關(guān)鍵的預(yù)處理步驟之一，現(xiàn)已廣泛應(yīng)用于醫(yī)學(xué)、農(nóng)學(xué)、工業(yè)生產(chǎn)等眾多領(lǐng)域[1]。圖像分割的主要目的是將圖像中的關(guān)鍵信息提取出來，以供研究人員后續(xù)分析時使用。目前，圖像分割的方法大致可分為基于閾值處理分割、基于邊緣檢測分割、基于區(qū)域分割等[2-3]。其中，閾值處理憑借其簡單高效、性能穩(wěn)定等優(yōu)勢被廣泛應(yīng)用。基于閾值分割技術(shù)的難點在于閾值的選取，而最大類間方差法(Otsu法)因其較高的實用性被廣泛應(yīng)用于生產(chǎn)技術(shù)當中。圖像分割可分為單閾值分割與多閾值分割，單閾值分割是指將圖像分割為黑白兩個區(qū)域，而多閾值分割將圖像分成幾個不同的區(qū)域，適用于復(fù)雜圖像的分割。當圖像從單閾值擴展至多閾值時，最重要的限制是算法運行時間與分割準確率[4]。Otsu方法的原理是遍歷搜索256個灰度級中的類間方差最大時的灰度級即為圖像分割閾值。但遍歷窮舉的方法顯然計算量非常大，計算量隨閾值數(shù)量的增加呈現(xiàn)指數(shù)級增長，難以實際應(yīng)用。

智能優(yōu)化算法能解決許多優(yōu)化類問題，更好地尋找出所求函數(shù)的最大值或最小值，將智能優(yōu)化算法與圖像分割結(jié)合可以提高分割效率。應(yīng)用傳統(tǒng)優(yōu)化方法處理簡單的灰度圖像的確可以得到較好的效果，然而在處理復(fù)雜的彩色圖像分割時卻十分受限。并且彩色圖像分割是目前極具挑戰(zhàn)的一個領(lǐng)域，一幅彩色圖像需要分別考慮紅、綠、藍三類顏色分量的處理過程，再合成得到最終完整的分割圖像。為了解決上述問題，可引進新型的元啟發(fā)式算法，利用這些算法嘗試對彩色圖像進行閾值處理。

近年來，許多學(xué)者從自然界中的生物上發(fā)現(xiàn)靈感并建立相應(yīng)的數(shù)學(xué)模型，提出了眾多新穎的群智能優(yōu)化算法。比如螢火蟲算法[5](Firefly algorithm，F(xiàn)A)、布谷鳥搜索算法[6](Cuckoo Search algorithm，CS)、細菌覓食算法[7](Bacterial Foraging Optimization algorithm，BFO)等。目前，已有學(xué)者將這些新型的優(yōu)化算法應(yīng)用于圖像分割領(lǐng)域，比如吳鵬[8]應(yīng)用螢火蟲算法結(jié)合最大熵方法進行圖像分割，通過螢火蟲算法對目標函數(shù)進行優(yōu)化搜索得到圖像的最佳分割閾值;柳新妮等[9]基于布谷鳥算法結(jié)合Otsu方法用于多閾值圖像分割;廖艷萍等[10]將細菌覓食算法結(jié)合PCNN對圖像進行分割，采用該算法搜索PCNN的最優(yōu)模型參數(shù)。上述成果表明新型的元啟發(fā)式優(yōu)化算法能在選取的圖像中取得較好的分割效果，但上述學(xué)者都未將算法應(yīng)用到彩色圖像上進行實驗。本文為了探索解決彩色圖像分割的問題，以飛蛾撲火算法[11]為基礎(chǔ)并對該算法進行改進，增強其尋優(yōu)能力和效率，最終應(yīng)用到彩色圖像分割中。

1 標準飛蛾撲火算法

MFO算法是一種新型的元啟發(fā)式優(yōu)化算法，該算法模擬了自然界中飛蛾的導(dǎo)航行為。飛蛾在夜間具有獨特的導(dǎo)航方式，它們依靠月光利用橫向定向機制，相對于月亮保持固定的角度進行直線飛行，如圖1所示。然而在現(xiàn)實生活中，飛蛾經(jīng)常被人造光干擾，若仍借助橫向定向機制試圖與人造光保持確定的角度飛行，則最終會聚于光源，如圖2所示。

人們總能從自然界生物中得到靈感，MFO算法由Seyedali Mirjalili在2015年提出[11]，該算法參數(shù)較少并且具有良好的尋優(yōu)能力，一經(jīng)提出便受到國內(nèi)外學(xué)者的廣泛關(guān)注。在該算法中，變量是空間中飛蛾的位置，飛蛾改變它們的位置矢量在超維空間中飛行。值得注意的是，飛蛾和火焰都是問題的解決方案，它們之間的區(qū)別在于算法迭代和更新的方式不同。飛蛾是實際在空間中進行搜索的個體，而火焰是到目前為止飛蛾獲得的最佳位置。

在MFO算法中，選擇對數(shù)螺旋作為飛蛾更新位置的主要機制，公式為：

Mi=Di·ebθ·cos(2πθ)+Fj

(1)

式中：b是用于定義對數(shù)螺旋形狀的常數(shù);θ是[-1，1]之間的隨機數(shù);Mi表示第i個飛蛾;Fj表示第j個火焰;Di表示第i個飛蛾與第j個火焰之間的距離，公式為：

Di=|Fj-Mi|

(2)

利用上述方程模擬飛蛾螺旋飛行的路徑。方程中的參數(shù)θ為收斂常數(shù)，定義飛蛾的下一個位置接近火焰的程度，θ=-1是距離火焰最近的位置;θ=1是距離最遠的，如圖3所示。

圖3 參數(shù)θ的分布意義

式(1)僅定義了飛蛾朝向火焰飛行的過程，因此容易造成算法收斂過快，陷入局部最優(yōu)。為了避免上述情況，飛蛾在初始化位置、計算適應(yīng)度值之后，火焰依據(jù)適應(yīng)度值進行排序，飛蛾通過式(1)更新位置，依次迭代。這樣，每只飛蛾對應(yīng)一個火焰，第一只飛蛾總是相對于最好的火焰進行位置更新，最后一只飛蛾相對于最差的火焰更新位置。依照這種機制，可以有效避免MFO算法陷入局部最優(yōu)。

為了提高最優(yōu)解的尋找效率，對火焰提出一種自適應(yīng)減少的機制，當?shù)阶詈笠淮螘r，保留的唯一火焰就是全局最優(yōu)解。公式如下：

(3)

式中：N為初始火焰數(shù)量;t為當前迭代次數(shù);T為最大迭代次數(shù)。

2 改進飛蛾撲火算法

飛蛾撲火算法是近幾年來最新提出的優(yōu)化方法且性能良好，但是相較于其他成熟的尋優(yōu)算法，仍然存在容易陷入局部最優(yōu)導(dǎo)致算法過早收斂的問題。借鑒其他成熟算法的改進方式，本文將從兩方面對MFO算法進行改進。一是加入自適應(yīng)權(quán)重，使算法在迭代前期可以使飛蛾在較大的范圍內(nèi)搜索，在迭代后期可以提高飛蛾的尋優(yōu)精度。二是應(yīng)用Lévy飛行策略，保證飛蛾可跳出局部環(huán)境朝著最優(yōu)的方向飛行，提高了算法的整體性能。

2.1 引入自適應(yīng)權(quán)重

借鑒粒子群算法中的慣性權(quán)重思想，慣性權(quán)重ω影響種群的搜索機制。ω越大，算法全局范圍內(nèi)搜索力度越大;ω越小，算法局部范圍內(nèi)搜索精度越高。因此，ω的變化影響著種群的整體尋優(yōu)能力。在LSMFO算法中，飛蛾位置采用對數(shù)螺旋進行更新并引入自適應(yīng)權(quán)重ω，公式為：

(4)

式中：t為當前迭代次數(shù);T為最大迭代次數(shù);a、b為常數(shù)。

通過多次試驗，當a=30、b=5時，本文提出的非線性自適應(yīng)權(quán)重取得的效果較好，如圖4所示，其中虛線表示傳統(tǒng)線性遞減更新策略，實線表示本文提出的非線性遞減更新策略。該策略在迭代初期和迭代后期均能保持較長時間的穩(wěn)定，使飛蛾在前期全局尋優(yōu)和后期局部尋優(yōu)中均取得較好效果。將該慣性權(quán)重應(yīng)用到飛蛾位置更新公式中：

Mi=Di·ebn·cos(2πn)+ω·Fj

(5)

圖4 慣性權(quán)重遞減函數(shù)曲線

2.2 引入Lévy飛行

Lévy Fight是由法國數(shù)學(xué)家Paul Lévy最早提出的一種隨機游走方式，其中的步長服從重尾概率分布[12]，如下式所示：

(6)

式中：通常γ=1;0<λ≤2;s代表移動步長;Γ(λ)為標準伽馬函數(shù)。

由于上述公式實現(xiàn)較為困難，后有學(xué)者Mantegna將其進行簡化改進，用正態(tài)分布求解隨機數(shù)[13]，模擬生成服從Levy分布的隨機步長，如下式所示：

(7)

式中：β=1.5;μ～N(0,σ2);ν～N(0,1);

Lévy飛行是一種特殊的行為方式，表現(xiàn)為大量的短距離游走和少量的長距離跳躍行為，可用于隨機或偽隨機自然現(xiàn)象的測量和模擬。有研究表明，許多動物甚至人類的某些行為均符合Lévy飛行的特征，因此具有良好的搜索性能。圖5模擬了個體進行100次Lévy飛行的位置更新情況。

圖5 100次Lévy飛行軌跡

將Lévy飛行應(yīng)用到飛蛾撲火算法中：

(8)

式中：rand()表示[0，1]的隨機數(shù);?表示點乘運算。

飛蛾初始化之后，每只飛蛾根據(jù)適應(yīng)度函數(shù)計算此時的適應(yīng)度值，對適應(yīng)度值進行排序后即得到了火焰列表的值，取其中的第一個值作為當前種群的最優(yōu)值。飛蛾首先依據(jù)式(5)的自適應(yīng)權(quán)重策略對位置初步更新，之后采用式(8)的Lévy飛行策略對位置再一次更新。經(jīng)過上述步驟，飛蛾的一次位置更新結(jié)束，依次循環(huán)。

改進后的LSMFO算法較初始的MFO算法提高了全局搜索能力，增強了算法的多樣性，避免了種群陷入局部最優(yōu)。同時，算法運行時間有所降低，算法精度也得到了提升。

3 基于LSMFO的多閾值彩色圖像分割

閾值處理是圖像分割中實用性較強的一種方法，單閾值圖像分割可以看作是單目標規(guī)劃問題，而多閾值則可看成是一個多元目標規(guī)劃尋優(yōu)問題。多閾值圖像分割即利用K個閾值組成的閾值向量T={t1,t2,…,tK}將圖像I分成K+1個區(qū)域{C0,C1,…,CK}，本文用最大類間方差法(Otsu法)選取全局最佳閾值向量T*。

假設(shè)圖像I的大小為M×N，灰度級為L(0

(9)

對每一個區(qū)域Ck，其累計概率wk和平均灰度級μk由下式?jīng)Q定：

(10)

整個圖像的平均灰度μT和最大類間方差公式為：

(11)

遍歷窮舉所有灰度級(1～256)，圖像的最佳閾值向量如下式所示：

(12)

若用窮舉法求取最佳閾值向量，隨著閾值等級的逐漸升高，算法的計算量將呈指數(shù)級增長，運算量驚人。為了提高效率，需要結(jié)合智能優(yōu)化算法求解最佳閾值向量。本文利用提出的LSMFO算法，對多閾值分割中最佳閾值的搜索過程進行尋優(yōu)，數(shù)學(xué)模型如下：

(13)

閾值分割的實質(zhì)就是找出圖像的最佳閾值向量，將Otsu法中的最大類間方差公式(式(11))作為算法的適應(yīng)度函數(shù)進行求解，最大類間方差值表示適應(yīng)度值，多閾值的閾值個數(shù)即表示飛蛾在空間中的位置維數(shù)。尋找出適應(yīng)度值最大時火焰列表中火焰的位置向量F即為圖像所得的最佳閾值向量。整個算法的實現(xiàn)流程如圖6所示。

圖6 基于LSMFO的圖像分割流程圖

4 多閾值彩色圖像分割實驗

本文對整個伯克利大學(xué)圖像數(shù)據(jù)庫中的圖像進行了圖像分割實驗，并從中選定了4幅圖像，如圖7所示。為了驗證所提出的LSMFO算法的優(yōu)劣性，本文選取了另外5種算法作為對比，分別為MFO、SCA(正余弦優(yōu)化算法)[14]、MVO(多元宇宙優(yōu)化算法)[15]、WOA(鯨魚優(yōu)化算法)[16]、PSO(粒子群優(yōu)化算法)[17]。本文對所選的4幅經(jīng)典圖像運用Otsu法取閾值數(shù)K=4，6，8，10，15進行圖像分割，將6種算法的最大迭代次數(shù)設(shè)置為500，初始種群數(shù)量設(shè)置為25，其他具體參數(shù)如表1所示。

(a) Test 1 (b) Test 2

(c) Test 3 (d) Test 4圖7 伯克利實驗圖像

表1 算法參數(shù)

為了更好地評估算法應(yīng)用到圖像分割的性能，本文選用3個常用指標來進行衡量：

(1) 結(jié)構(gòu)相似性(SSIM):一種衡量兩幅圖像相似度的指標[18]。SSIM的取值在[0,1]，越接近1表明兩幅圖像結(jié)構(gòu)越相似，用在圖像分割中表示分割效果越好。給出兩幅圖像x和y，定義如下：

(14)

(2) 峰值信噪比(PSNR):一個表示信號最大可能功率和影響它的表示精度的破壞性噪聲功率的比值的工程術(shù)語[19]，指標值越大，說明圖像分割結(jié)果越好。給出大小為M×N的圖像x和y，PSNR定義如下：

(15)

(16)

(3) 邊緣保持系數(shù)(EPI):表示處理后濾波器對圖像水平或垂直方向邊緣的保持能力，值越高則保持能力越強[20]，其公式如下：

(17)

式中：m為圖像像元個數(shù);GR1和GR2分別為左右或上下的互鄰像元灰度值。

實驗在MATLAB 2016b的環(huán)境下進行，每種算法對4幅伯克利圖像分別運行30次，分割指標取平均值如表2-表5所示。每一種算法自身縱向比較，隨著閾值數(shù)量的提升，SSIM、PSNR、EPI三種指標都隨之增大，表明閾值數(shù)量越大，分割后與原圖越貼合，與此同時，算法運行時間會有所加長。將6種算法進行橫向比較，在SSIM指標上，LSMFO明顯高于其他所有算法，其次MFO、MVO、WOA三種算法較為接近，之后為PSO與SCA，說明LSMFO分割后的圖像與原圖像在結(jié)構(gòu)上更為相似。在PSNR指標上，LSMFO、MVO、WOA指標相近，但LSMFO總體略高于MVO與WOA，之后為SCA與PSO，MFO在該指標的評估中表現(xiàn)不盡如人意，遠低于其他算法。在EPI指標中，MFO優(yōu)勢較為明顯，其次為LSMFO與PSO，之后是SCA、MVO、WOA。在算法運行時間上，SCA整體上時間短于其他算法，究其分割效果不理想的原因是算法過早收斂，LSMFO運行時間略短于PSO，之后分別為MFO、WOA、MVO。對表2-表5中的數(shù)據(jù)進行統(tǒng)計綜合能夠更清晰地展現(xiàn)出LSMFO算法的優(yōu)劣性，將表中數(shù)據(jù)繪制成曲線圖形式，如圖8-圖11所示。綜合以上分析可知，LSMFO具有良好地分割能力與去噪能力，能夠很好地完成彩色圖像分割任務(wù)。

表2 伯克利圖像指標—SSIM

續(xù)表2

表3 伯克利圖像指標—PSNR

續(xù)表4

表5 伯克利圖像指標—CPU Time

圖8 SSIM指標分析曲線圖

圖9 PSNR指標分析曲線圖

圖10 EPI指標分析曲線圖

圖11 CPU TIME指標分析曲線圖

為了對實驗數(shù)據(jù)進行統(tǒng)計意義分析，本文采用ANOVA(Analysis of Variance)測試，將LSMFO與另5種算法進行比較，給定p值為5%，當p值小于0.05時，表明兩者之間存在顯著差異性。對SSIM、PSNR、EPI和CPU Time指標進行ANOVA測試，結(jié)果如表6所示。表中使用(*)標注了p值小于0.05的數(shù)據(jù)，測試結(jié)果說明了LSMFO與其他算法具有顯著差異。

表6 ANOVA測試

通過上述比較，可以看出LSMFO指標整體分割水平高于其他算法，并且在SSIM這一關(guān)鍵指標中表現(xiàn)優(yōu)秀。仔細比較LSMFO與MFO兩種算法的分割結(jié)果，也可以看出改進之后的飛蛾撲火算法有著更好的性能，說明本文提出的LSMFO算法應(yīng)用在彩色圖像分割領(lǐng)域有著更大的優(yōu)勢。

5 結(jié) 語

本文提出基于萊維飛行和改進飛蛾撲火算法(LSMFO)，用于解決彩色圖像多閾值分割問題。將LSMFO算法與MFO、MVO、SCA、WOA、PSO算法進行對比，分別在閾值數(shù)K=4，6，8，10，15時對4幅伯克利大學(xué)經(jīng)典圖像進行分割實驗，采用SSIM、PSNR、EPI三個指標評估分割質(zhì)量，數(shù)據(jù)結(jié)果展現(xiàn)出LSMFO算法的優(yōu)勢性，具有運行速度快、分割精度高的特點，能夠?qū)嶋H應(yīng)用于圖像分割的工程問題。下一步，將繼續(xù)深入研究從不同方面提高彩色圖像分割效率的問題。