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

袁玉珠

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

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

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

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

1 基于Renyi熵的圖像分割

1.1 二維Renyi熵單閾值分割

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

(1)

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

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

(2)

參數為α的二維Renyi熵為

(3)

二維Renyi目標熵和背景熵為

(4)

(5)

(6)

1.2 二維Renyi熵多閾值分割

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

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

(7)

二維Renyi總熵為

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

(8)

(9)

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

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

2 粒子群優化算法及其衍化

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

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

(10)

(11)

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

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

(12)

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

p=r/Nunm

(13)

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

(14)

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

3 改進分數階達爾文粒子群算法

3.1 基于進化信息調整分數階次α

(15)

(16)

(17)

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

(18)

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

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

(19)

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

3.2 基于Levy飛行特征的局部最優

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

定義局部最優概率因子popt

(20)

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

(21)

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

4 仿真試驗與對比分析

4.1 最優閾值尋優流程

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

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

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

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

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

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

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

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

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

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

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

4.2 尋優效果對比分析

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

表1 4個標準函數

種群規模設為50，最大迭代次數為1000次。3種粒子群優化算法運行100次取平均。

表2 參數設置

圖3為3種智能優化算法對表1中4個標準函數的尋優收斂曲線。

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

4.3 圖像分割效果對比分析

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

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

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

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

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

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

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

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

5 結 語

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