改進烏鴉算法的二維Tsallis熵多閾值圖像分割算法

常君杰，李東興，鐘欣，杜文漢，王倩楠

(山東理工大學 機械工程學院，山東 淄博 255049)

圖像分割是指把圖像分成具有不同特性的各個區域，提取出所需目標的過程[1]。閾值法因簡單、高效，在圖像分割領域應用廣泛[2]。近幾年，閾值分割方法大都與熵結合使用，Tsallis熵受非廣延統計物理的啟發，通過引入參數q來度量系統的不可擴展性[3-4]。Sahoo等[5]提出了基于二維Tsallis熵的圖像閾值分割方法，充分利用了圖像的灰度分布、空間鄰域分布等信息，分割效果好，但存在速度慢、計算時間長的缺點。

為加快閾值選取速度，人們將啟發式優化算法與熵結合，用于圖像分割，取得了較好的效果[6]。文獻[7]將螢火蟲算法(firefly algorithm, FA)與二維熵結合對圖像進行快速分割，減少了運行時間，但需設置的參數多，適用性不強；文獻[8]利用自適應布谷鳥算法和二維最大類間方差法進行閾值分割，進一步縮短運行時間，卻易陷入局部最優；文獻[9]將烏鴉搜索算法用于多閾值圖像分割，需設置的參數少，容易實現，可沿較優路徑搜索，但傳統烏鴉算法位置更新策略為個體隨機搜索，存在盲目性，導致烏鴉算法收斂速度慢和易陷入局部最優[10]。

針對烏鴉算法存在的問題，本文提出改進烏鴉算法優化二維Tsallis熵多閾值圖像分割法，利用Levy飛行策略優化烏鴉搜索算法，將改進烏鴉搜索算法與二維Tsallis熵結合用于圖像分割，以提高二維Tsallis熵多閾值圖像分割效率和精度。

1 烏鴉搜索算法及其改進

1.1 烏鴉搜索算法

烏鴉搜索算法(crow search algorithm, CSA)由Askarzadeh[11]提出，是一種基于烏鴉覓食過程的智能算法。烏鴉i為了獲取更多食物，會跟蹤其他烏鴉j并偷取食物，若烏鴉j發現被跟蹤，則會隨機飛行迷惑跟蹤者i，保護食物不被發現。烏鴉i的位置可表示為

xi,iter+1=

(1)

式中：ri、rj是0和1之間的隨機數；iter表示當前迭代次數；mi,iter表示烏鴉i記憶中最優的位置；xi,iter表示烏鴉i當前位置；fli,iter表示飛行長度；APj,iter是迭代時j的感知概率。

更新mi,iter的公式為

(2)

式中f(·)表示適應度函數。

1.2 改進的烏鴉搜索算法

CSA具有結構簡單、易于實現的優點，已成功應用于配電網導體選擇[12]、極限學習機參數優化[13]等多個領域。但傳統烏鴉算法位置更新策略存在個體隨機搜索、具有一定盲目性的問題，導致烏鴉算法收斂速度慢和易陷入局部最優。

1.2.1 Levy飛行機制

Levy飛行是一種隨機步長服從Levy分布的方法，具有隨機游走、隨機發現的特性[14]。利用Levy飛行優化CSA，可以在擴大算法的搜索范圍、保持局部搜索能力的同時，有效避免算法陷入局部最優。其冪次形式為

levy(λ)～|s|-λ，1<λ<3。

(3)

本文采用Mantegna提出的Levy步長公式[15]

(4)

(5)

式中δμ、δν定義為

(6)

其中Γ為標準Gamma函數。

1.2.2 自適應Levy飛行策略優化烏鴉搜索算法

利用自適應Levy飛行策略對烏鴉的位置進行更新,即

xi,iter+1=

(7)

式中：⊕表示點乘積；α(iter)為自適應尺度系數，且

(8)

其中β是限制因子，通常為大于1的數。圖1為不同β時α(iter)的變化曲線。圖1表明，不同的β值均能使α(iter)滿足在前期保持一個相對較大的初值，并隨迭代進行逐漸減小的條件，且隨β值增大，α(iter)后期衰減速率越快，效果越好；但β值的增大使算法計算量增加，影響算法的實時性。通過大量實驗驗證可知，β=3時可以使α(iter)有較快衰減速率的同時保證算法的實時性。

由計算所得的軸承靜載荷及動載荷,選取軸承型號為22310C/W33,其額定動載荷為175 kN,靜載荷為210 kN,滿足要求.

圖1 尺度系數變化圖

圖1顯示，α(iter)的變化是非線性的，在算法初期，迭代次數較少，α(iter)在較長的時間內保持較大的值，使得Levy飛行以較大步長進行搜索，全局搜索能力較強，便于找到近似的全局最優解；算法運行后期，解接近最優解時，α(iter)的值急劇減小，自適應縮小搜索步長，利于在最優解附近精細搜索，加速算法收斂。

傳統CSA中，當rj

2 改進CSA優化Tsallis熵分割算法

2.1 二維多閾值Tsallis熵分割算法

假設I(x,y)為待處理圖像，用n個灰度級閾值(s1,t1)，…，(sn,tn)將I(x,y)的二維直方圖P(i,j)劃分為n+1個類{A1,A2,...,An+1}，如圖2所示。

圖2 二維多閾值直方圖

目標區Ak中灰度級所對應的概率為

(9)

2.2 改進CSA優化Tsallis熵分割算法

傳統二維Tsallis熵多閾值分割采用窮舉的搜索模式，設圖像的灰度級數為L，閾值個數為n，則時間復雜度為O(L2n)，復雜度隨著閾值數的增加呈指數級增長[17]。本文提出改進CSA的二維Tsallis熵多閾值圖像分割方法，把分割閾值選擇的問題轉變為改進CSA對二維Tsallis熵函數Sq((s1,t1),(s2,t2),...，(sn,tn))的尋優問題。設算法的種群規模為N，問題維度為n，迭代次數為itermax，則算法的整體復雜度為O(itermax×N×n)，遠遠小于O(L2n)，因此改進算法能在較短時間內給出可行解或者近似最優解。

改進CSA的二維Tsallis熵多閾值圖像分割算法流程圖如圖3所示，具體步驟如下：

圖3 多閾值分割流程

步驟1：初始化基本參數，即種群數量N、最優閾值向量的維數n(根據選取的閾值個數確定)、感知概率AP、飛行長度fl及最大迭代次數itermax；

步驟2：隨生成N只烏鴉的初始位置，算法初期由于烏鴉都沒有“記憶位置”，所以令mi=xi；

步驟3：利用式(7)對烏鴉位置x進行更新，并計算新位置的適應度；

步驟4：根據式(2)更新記憶位置m，若f(xi,iter+1)≥f(mi,iter)，則mi,iter=xi,iter+1，否則保持不變；

步驟5：判斷是否滿足條件，若未滿足最大迭代次數，回到步驟3，反之繼續進行步驟6；

步驟6：輸出最優閾值(s*,t*)，并以此分割圖像。

3 實驗結果與分析

為驗證改進CSA在圖像分割效果和計算時間上的優越性，本文將Lena和Peppers典型圖像作為實驗對象進行多閾值圖像分割。通過大量實驗驗證，本文選取參數種群規模N=20，最大迭代次數itermax=100,感知概率AP=0.4，飛行步長fl=2。

3.1 多閾值圖像分割實驗

用改進CSA對Lena圖進行二維Tsallis熵的分割，分割結果如圖4所示。從圖4中可以看出，采用單閾值分割圖像時，分割結果粗糙，背景中的細節被忽略，頭發細節處分割模糊；采用二閾值分割時，背景中被忽略的細節有所體現，但帽子處的分割效果不理想；采用三閾值分割時，分割效果較好，分割結果清晰，局部細節好。因此，本文算法能有效分割復雜圖像，且隨閾值的增加，分割效果越好，得到的有用信息越多。

(a) 原圖 (b) 單閾值

為進一步驗證改進CSA的性能，將改進CSA與文獻[7]中的FA和文獻[9]中的經典CSA進行二維Tsallis熵分割對比實驗，對Peppers圖像進行分割，以閾值n=3為例，分割結果如圖5所示。

(a) 原圖 (b) FA結果

從圖5中可以看出，FA分割后青椒上的細節嚴重丟失，傳統CSA分割后局部區域過亮和過暗，分割效果不理想；改進CSA分割后圖像局部細節明顯好于其他2種算法，展現的信息更為清晰，分割效果更好。

3.2 分割性能對比

為定量分析3種算法的性能，采用峰值信噪比(peak signal to noise ratio, PSNR[18])與結構相似性 (structural similarity index, SSIM[19])對分割后圖像的性能進行比較。灰度圖像x(i,j)及閾值分割后圖像y(i,j)的PSNR定義為

(10)

式中：

(11)

通常分割效果越好，PSNR值越大。

SSIM用來衡量兩幅圖像的相似度。原始圖像x與分割后的圖像y的結構相似性可按照下式求出：

(12)

表1中數據顯示，當閾值個數為1時，各算法均順利找到了最佳閾值，分割效果相近。但當閾值個數為2、3時，本文算法的優勢體現出來，分割結果更加準確。以3閾值為例，本文算法分割Peppers圖像后的PSNR較FA與傳統CSA分別提高了12.68%、4.41%；SSIM分別提高了15.58%、12.73%。因此，相較對比算法，改進后CSA在分割精度上具有明顯優勢。

表1 閾值、PSNR及SSIM的對比

為了直觀反映3種算法的收斂過程，在itermax=100，n=3的情況下，繪制出Peppers圖的收斂曲線，如圖6所示。表2為不同算法在不同閾值條件下的分割結果。

圖6 Peppers收斂過程圖

從圖6中可以看出,FA和傳統CSA分別在第18次、第22次進行局部精細求解，陷入局部最優，雖最終均跳出了局部最優，但迭代次數增加，收斂速度較慢。表2中數據顯示，對Peppers圖像進行3閾值分割時，改進算法在第35次迭代時已經收斂到最優值，明顯早于其他算法，且算法運行時間最短，FA與傳統CSA所用時間分別是改進算法的2.76倍、1.14倍。

表2 適應度值、運性時間以及迭代次數的對比

綜合圖6與表2中的數據可知：改進后的CSA在運行過程中未陷入局部最優，迭代次數少、收斂速度快，且收斂后的目標函數值遠高于其他2種算法；改進后的CSA能較好地引導個體趨于全局最優解，相較其他2種算法在收斂速度以及分割精度上都有明顯改善。

4 結論

1)建立了一種自適應Levy飛行搜索策略。利用Levy飛行隨機游走的特性幫助CSA跳出局部最優，設置尺度系數自適應地限制Levy飛行搜索步長，平衡算法的全局尋優能力和局部精細求解能力，加速算法收斂。

2)利用改進烏鴉搜索算法優化二維Tsallis熵多閾值圖像分割，能減少計算量，提高運算效率，大大縮短分割時間。

3)將FA、傳統CSA與本文算法進行對比實驗。實驗結果顯示，改進CSA較其他算法分割清晰，細節特征保留完好，收斂速度快，計算時間短，不易陷入局部最優，PSNR與SSIM值均高于其他2種算法，驗證了改進CSA算法的有效性。