改進分數(shù)階達爾文粒子群的多Renyi熵圖像分割算法

袁玉珠

(福建工程學院交通運輸學院，福建 福州 350118)

隨著空間觀測技術的不斷發(fā)展，高分辨率遙感圖像已經(jīng)廣泛應用于地質(zhì)勘察、城市規(guī)劃、災害檢測等領域[1]。遙感圖像分割是提取遙感信息的前提和基礎。近幾十年圖像分割技術的發(fā)展，產(chǎn)生了大量遙感圖像的分割方法。如基于閾值的分割[2-3]、基于邊緣檢測的分割[4-5]、基于模糊聚類的分割[6-7]、基于神經(jīng)網(wǎng)絡的分割[8]、基于深度學習的分割[9-10]、基于馬爾科夫隨機場分割[11]等。其中閾值分割是一種性能較好且應用廣泛的圖像分割算法，閾值分割的關鍵是以一定的準則迅速找到最優(yōu)閾值，實現(xiàn)圖像準確分割。20世紀80年代初，學者們開始將信息論中的熵引入閾值分割中，其中以最大Shannon熵求取閾值為最常用方法，但因其未考慮圖像中目標與背景的相互關系，對背景目標相近圖像分割時精度不是很高。Renyi熵是Shannon熵的廣義形式，與Shannon熵相比，其引入了可調(diào)節(jié)的參數(shù)α，使得對信息的度量更具靈活性和一般性。

文獻[12]提出了基于二維Renyi熵的閾值分割方法，取得了較好的分割效果；文獻[13]提出了基于分解的二維Renyi熵值分割方法，在選取合適的參數(shù)α下，取得了不錯的分割效果；文獻[14]利用粒子群優(yōu)化算法選取最優(yōu)Renyi熵值，利用最優(yōu)Renyi熵閾值分割圖像；文獻[15]提出了分解二維Renyi熵圖像閾值分割方法，并采用快速遞推公式降低閾值選取準則函數(shù)的計算復雜度；文獻[16]利用自適應人工魚群搜索方法提出了一種參數(shù)α的自適應選取方法，在分割紅外圖像試驗中獲得了理想的分割效果。國內(nèi)外學者針對Renyi熵的閾值分割研究較少，特別對可調(diào)節(jié)參數(shù)α的選取多為手動，Renyi熵閾值分割的計算復雜度較高。

基于此，本文提出一種新的閾值分割算法，算法利用自適應加速系數(shù)和變異控制機制動態(tài)調(diào)整分數(shù)階次α系數(shù)以加強算法跳出局部最優(yōu)的能力，并將改進的分數(shù)階達爾文粒子群算法應用于二維Renyi多閾值熵的搜索，將搜索到的最優(yōu)多閾值進行圖像分割，獲得了較好的結果。

1 基于Renyi熵的圖像分割

1.1 二維Renyi熵單閾值分割

設灰度級L-1的遙感圖像P大小為M×N，f(x,y)表示遙感圖像P在(x,y)處的灰度值。像素灰度級i與鄰域平均灰度級j組成的二元組(i,j)出現(xiàn)的頻數(shù)設為Numi,j，p(i,j)表示二值灰度概率密度

(1)

p(i,j)構成了遙感圖像P的二維直方圖如圖1所示。

設閾值(s,t)將遙感圖像分成4個矩形區(qū)域，圖像的亮像素為背景區(qū)(A區(qū))、圖像的暗像素為目標區(qū)(B區(qū))、C區(qū)和D區(qū)表示邊界和噪聲[17],圖像二維熵過程中通常忽略兩區(qū)，故假定PC+PD≈0，背景區(qū)和目標區(qū)灰度級所對應的概率分別為PA(s,t)和PB(s,t)

(2)

參數(shù)為α的二維Renyi熵為

(3)

二維Renyi目標熵和背景熵為

(4)

(5)

(6)

1.2 二維Renyi熵多閾值分割

傳統(tǒng)的二維直方圖閾值分割只考慮待測圖像的背景與目標區(qū)域，忽略了圖像中的邊緣和噪聲信息。雖然圖像中的邊緣和噪聲信息分量較少，但直接忽略不僅不能真實地反映待測圖像的像素分布，還會導致圖像分割不夠精確。

由于遙感圖像中目標較為隱蔽，目標與背景邊緣模糊不清，利用單閾值分割往往難以將目標和背景分割精確，本文改進閾值劃分形式，并將單閾值分割擴展到多閾值分割，利用n-1個灰度級對圖像P進行多閾值劃分，改進二維多閾值直方圖劃分如圖2所示。

(7)

二維Renyi總熵為

Hα((t1,s1),(t2,s2),…,(tn-1,sn-1))=

(8)

(9)

二維Renyi熵多閾值選取的計算過程較為復雜，計算量也頗大，為了避免中間變量的重復計算，提高算法的速度，很多文獻中都會將二維Renyi熵多閾值選取分解為多個一維Renyi熵閾值相加的形式。本文在此不再贅述，二維Renyi熵多閾值分解過程參見文獻[15]。

二維Renyi熵多閾值分割就是根據(jù)利用最優(yōu)閾值組合將待分割圖像分割成各類的總熵值最大。為了縮短尋找最優(yōu)閾值的時間，本文利用改進的分數(shù)階達爾文粒子群算法對二維Renyi熵最優(yōu)閾值進行搜索。

2 粒子群優(yōu)化算法及其衍化

粒子群優(yōu)化算法(partical swarm optimization,PSO)是一種群體智能全局尋優(yōu)的算法[18]。該智能優(yōu)化算法在優(yōu)化組合、多目標尋優(yōu)、聚類分析等領域應用廣泛且效果突出[19-21],與其他智能優(yōu)化算法一樣，粒子群優(yōu)化算法也存在易陷入局部最優(yōu)、搜索精度不高、后期收斂慢等問題。針對這些問題，國內(nèi)外學者進行了深入的研究，提出了多種改進算法。文獻[22]將達爾文進化理論引入粒子群優(yōu)化算法中，提出了一種達爾文粒子群優(yōu)化算法(Darwinian partical swarm optimization，DPSO)；文獻[23]將分數(shù)階微分理論引入粒子群優(yōu)化算法中，提出了分數(shù)階粒子優(yōu)化算法(fractional order partical swarm optimization，F(xiàn)OPSO),通過重排原始速度修正速度導數(shù)，以便控制優(yōu)化算法的收斂速度，取得了不錯的效果；受文獻[23]的啟發(fā)，學者Micael將分數(shù)階微分和達爾文進化理論相結合，集中二者的優(yōu)點應用于粒子群優(yōu)化算法中，提出了分數(shù)階達爾文粒子群算法(fractional order Darwinian partical swarm optimization，F(xiàn)ODPSO)，試驗結果表明與其他智能優(yōu)化算法相比，該算法通過分數(shù)階次α來控制計算精度與收斂速度，該算法由于過度依賴分數(shù)階次α，容易造成局部最優(yōu)[24]。針對FODPSO依賴分數(shù)階次α調(diào)節(jié)算法的弊端，本文利用自適應加速系數(shù)和隨機擾動控制機制動態(tài)調(diào)整分數(shù)階次α系數(shù)以實現(xiàn)精確計算和快速收斂。

在一個M維目標空間中，Nnum個粒子組成群落，每個粒子的速度和位置更新公式

(10)

(11)

第i個粒子位置向量為Xi=(xi1,xi2,…,xiD)，速度向量為Vi=(vi1,vi2,…,viD)，第i個粒子經(jīng)歷過的位置中最優(yōu)位置Wi=(wi1,wi2,…,wiD)，整個粒子群最優(yōu)位置Wg=(wg1,wg2,…,wgD)。式(10)中，ω表示慣性系數(shù)；c1、c2表示加速系數(shù)；R1d、R2d為[0,1]間的隨機數(shù)；wid表示粒子個體最優(yōu)值；wgd表示粒子群整體最優(yōu)值。

DPSO將自然選擇理論引入算法中，對于能找到較好適應值的粒子群，延長其生命，對于無法找到較好適應值的粒子群，壽命就會縮短，同時遍歷粒子群，刪除性能較差的粒子。設置粒子搜索計數(shù)器SC用于追蹤粒子群適應值沒有改變次數(shù)。創(chuàng)建新粒子群時，粒子群內(nèi)所有搜索計數(shù)器SC=0，在粒子群適應度沒有提高時，其中的粒子被刪除后，該粒子群的搜索計數(shù)器不置為0，而是根據(jù)式(12)將其設置為與最大計數(shù)值SCmax相近的值

(12)

式中，Nkill表示粒子群適應值沒變化期間被刪除的粒子數(shù)。若一個粒子群中所有粒子被刪除，并且當前粒子群數(shù)沒有超過種群設置數(shù)，則創(chuàng)建新粒子群的概率為

p=r/Nunm

(13)

式中，r為[0,1]間隨機數(shù)；Nunm表示種群粒子數(shù)。文獻[24]給出了分數(shù)階次α調(diào)整公式

(14)

通過大量試驗可知分數(shù)階次α在[0.5,0.8]之間時，F(xiàn)ODPSO算法可取的較快的收斂速度。但是通過式(14)可以看出：隨著迭代次數(shù)的加大，分數(shù)階次α會線性減小，這勢必會使粒子群陷入局部最優(yōu)和低速收斂。本文通過改變分數(shù)階次α的調(diào)整方式和陷入局部最優(yōu)的跳出方式，對FODPSO進行改進。

3 改進分數(shù)階達爾文粒子群算法

3.1 基于進化信息調(diào)整分數(shù)階次α

(15)

(16)

(17)

基于粒子進化因子fev∈[0,1]，利用高斯圖函數(shù)得出分數(shù)階次α的調(diào)整公式

(18)

通過式(18)可知，分數(shù)階次α的調(diào)整不再依賴迭代次數(shù)，而是依據(jù)粒子自身的進化信息，這可避免算法因分數(shù)階次α線性減小而引起的局部最優(yōu)和收斂緩慢。

設慣性系數(shù)ω為1，根據(jù)分數(shù)階微分方程的格林瓦德-列特尼科夫(G-L)定義，粒子速度更新策略變?yōu)?/p>

(19)

粒子的位置更新依據(jù)式(11)進行，其中加速系數(shù)滿足3≤(c1+c2)≤4。

3.2 基于Levy飛行特征的局部最優(yōu)

當粒子群陷入局部最優(yōu)時，算法極易出現(xiàn)過早收斂，為了克服尋優(yōu)算法早熟收斂，及時跳出局部最優(yōu)，本文將Levy飛行特性引入改進的FODPSO中，利用Levy飛行特性擴展搜索空間，根據(jù)局部最優(yōu)概率因子popt對算法取得的局部最優(yōu)wg進行位置擾動。

定義局部最優(yōu)概率因子popt

(20)

wgd=wgd(1+levy(ξ)tanh(fev))

(21)

式中,Levy(ξ)是隨機搜索路徑;步長的大小通過levy分布隨機數(shù)產(chǎn)生且1≤ξ≤3，0≤fev≤1，0≤tanh()≤1。

4 仿真試驗與對比分析

4.1 最優(yōu)閾值尋優(yōu)流程

(1) 初始化粒子群，隨機生成粒子速度Vi和位置Xi，確定種群個數(shù)Nnum，目標空間維數(shù)M，最大迭代次數(shù)Tmax，加速系數(shù)c1、c2等參數(shù)。

(2) 對粒子群中每個粒子進行適應度評估，將粒子個體的最優(yōu)值wid設為當前位置，全局最優(yōu)值wgd設為群體最優(yōu)粒子位置。

(3) 開始迭代，迭代次數(shù)加1。

(4) 計算每個粒子對應的Renyi熵值，找出最優(yōu)粒子位置；并根據(jù)式(15)、式(16)、式(17)和式(18)計算粒子平均進化狀態(tài)信息。

(5) 根據(jù)式(21)、式(10)、式(11)更新粒子的位置和速度。

(6) 更新粒子適應度值，與當前個體極值進行對比。若粒子當前適應度值優(yōu)于個體極值，將wid設為該粒子位置；若所有粒子中個體極值最優(yōu)者優(yōu)于全局極值，則將該粒子的位置設為wgd。

(7) 對比粒子群的適應度，對粒子群適應度變優(yōu)的增加其壽命，對粒子群適應度變差的刪除粒子，并按式(12)重置搜索計數(shù)器。若創(chuàng)建新的粒子群，根據(jù)式(14)計算概率；否則，執(zhí)行下一步驟。

(8) 根據(jù)式(22)計算局部最優(yōu)概率因子popt，若局部最優(yōu)概率因子popt大于隨機產(chǎn)生的隨機數(shù)，則按式(23)進行Levy飛行擾動;否則，執(zhí)行下一步驟。

(9) 判斷算法是否達到收斂或達到最大迭代次數(shù)，若是，執(zhí)行下一步驟;否則，執(zhí)行步驟(3)。

(10) 輸出全局最優(yōu)值，算法結束。

為了驗證本文改進算法的優(yōu)越性，從兩個方面進行對比分析：①利用4種測試函數(shù)對比尋優(yōu)效果；②通過分割遙感圖像對比分割效果。編程平臺為Windows 7 Microsoft VS 2013和OpenCV 3.0，仿真平臺為Matlab 2014a,CPU為i5-4460T@2.7 GHz,RAM為4 GB。

4.2 尋優(yōu)效果對比分析

將本文算法、文獻[23](FOPSO)和文獻[24](FODPSO)在表1所示的4個標準函數(shù)上[24]對比尋優(yōu)效果。3種粒子群優(yōu)化算法的參數(shù)設置見表2。

表1 4個標準函數(shù)

種群規(guī)模設為50，最大迭代次數(shù)為1000次。3種粒子群優(yōu)化算法運行100次取平均。

表2 參數(shù)設置

圖3為3種智能優(yōu)化算法對表1中4個標準函數(shù)的尋優(yōu)收斂曲線。

由圖3各算法的尋優(yōu)曲線可以看出：FOPSO和FODPSO對Rastrigin標準函數(shù)的尋優(yōu)效果一般，過早陷入了局部最優(yōu)；隨著迭代次數(shù)的增加，F(xiàn)OPSO和FODPSO在多峰Ackley函數(shù)、單峰Sphere、Rosenbrock函數(shù)上，收斂速度緩慢，尋優(yōu)精度不精。而本文改進算法無論是對Sphere、Rosenbrock 2種單峰函數(shù)還是對Rastrigin、Ackley多峰函數(shù)都能在若干次迭代后迅速從局部最優(yōu)中跳出，并快速搜尋到最優(yōu)值，擴大了對最優(yōu)值的全局搜索能力。

4.3 圖像分割效果對比分析

利用本文改進的分割算法、文獻[25]、文獻[26]等3種算法對選取的2幅資源三號衛(wèi)星的遙感圖像進行分割試驗。使用概率Rand指數(shù)、信息變化指數(shù)、全局一致程度誤差等3種傳統(tǒng)圖像分割評價指標[27]定量對比分割效果：

(1) 概率Rand指數(shù)(probabilistic rand index，PRI)是統(tǒng)計分割結果與手動分割結果間像素一致性的比例，比例越大分割精度越高。

(2) 信息變化指數(shù)(variation of information，VOI)是衡量分割結果與標準分割間的平均條件熵,取值越小分割效果越好。

(3) 全局一致程度誤差(global consistency error，GCE)度量分割結果被看作另一個分割子集程度，取值越小分割效果越好。丘陵遙感圖像分割結果如圖4所示。

圖4所示的丘陵遙感圖像中，包括溝壑、綠植、道路等內(nèi)容，輪廓較為清晰，邊界較為分明。從分割結果可以看出：文獻[26]分割算法和本文分割算法均能得到準確的輪廓，邊緣清晰，在小尺度結構區(qū)域都有較高的識別質(zhì)量，但文獻[26]在分割細節(jié)上有待提高；文獻[25]分割的邊緣模糊，紋理不夠清晰，局部區(qū)域偏亮或者偏暗，存在一定的虛警，總體分割效果較差。

圖5所示的港口遙感圖像中包含道路、大海、油罐、船只等內(nèi)容，圖像邊界分明，細節(jié)突出。3種分割算法均能分割得到大致輪廓，分割邊緣都較為清晰，但文獻[25]和文獻[26]在細節(jié)分割上不夠精確，都沒有有效分割出船只等信息。本文算法對細節(jié)的分割較為準確，這是由于本文利用優(yōu)化算法得到最優(yōu)多閾值分割的效果體現(xiàn)。3種分割算法的定量評價指標見表3。

表3 3種分割算法的定量評價

從表3數(shù)據(jù)可以看出，本文分割算法在PRI、VOI、GCE 3種定量標準上都優(yōu)于其他2種分割算法。在PRI指標上，本文分割算法提升了至少7.27%、在VOI指標上降低了至少6.5%、在GCE指標上降低了至少10.4%。說明本文分割算法對遙感圖像的分割結果具有像素一致性，位置偏離誤差小，細節(jié)分割準確到位，并且分割后信息丟失量最少。

5 結 語

本文提出了一種基于改進FODPSO的二維Renyi熵多閾值遙感圖像分割算法，利用進化信息和隨機擾動控制機制動態(tài)調(diào)整分數(shù)階次α系數(shù)，實現(xiàn)了算法精確計算和快速收斂，引入Levy飛行特征加強FODPSO跳出局部最優(yōu)能力，將改進的優(yōu)化算法應用于二維Renyi熵多閾值的最優(yōu)搜索中，最終使用最優(yōu)閾值對試驗遙感圖像進行了分割。結果表明，本文提出的分割算法不僅能對復雜圖像進行準確地分割，還在各項定量評價指標上均比其他2種分割算法優(yōu)越。