基于雞群算法的Tsallis熵多閾值圖像分割

鄭和平，姚 儉

(上海理工大學 管理學院，上海 200093)

0 引言

圖像分割是圖像處理過程中非常關鍵的一步，圖像分割質量直接關系到后續圖像的處理與分析，所以要慎重選擇圖像分割算法。圖像分割算法基本上可分為4種：①直方圖閾值分割算法；②圖像特征空間聚類分割算法；③基于區域的圖像分割算法；④基于邊緣的圖像分割算法[1-5]。其中閾值分割技術是最經典與流行的方法之一，也是最簡單的圖像分割方法。閾值分割技術的關鍵是尋找一個或幾個最佳閾值將圖像的灰度值層級分割成兩個或多個部分。近年來，國內外學者提出了很多閾值分割算法，如Kapur′s 熵分割算法、Ostu分割算法、最小交叉熵分割算法、Tsallis熵分割算法等[6-9]。Tsallis熵是被廣泛使用的閾值分割算法之一，其優勢在于簡單、易實現，且容易從單閾值分割擴展到多閾值分割。

閾值分割算法操作簡單，但是隨著閾值個數的增加，計算量呈指數級上升，計算時間也急速上升，難以投入實際應用。因此，很多研究者將優化算法引入到閾值分割領域，將優化算法與閾值分割算法相結合形成新的閾值分割算法。Abdul Kayom Md Khairuzzaman等[10]用狼群算法尋找Kapur′s熵以及Ostu下的最佳閾值；Hao Gao等[11]用改進的人工蜂群算法尋找Ostu下的最佳閾值；Sanjay Agrawal等[12]用布谷鳥搜索算法尋找Tsallis熵下的最佳閾值。

雞群優化算法(Chicken Swarm Optimization，CSO)是Meng Xianbing等[13]于2014年提出的一種基于雞群群體行為的智能優化算法。在文獻[13]中證明了該算法在優化目標函數方面的性能優于粒子群算法(Particle Swarm Optimization, PSO)與差分進化算法(Differential Evolution Algorithm, DE)，而PSO、DE是經常用來與各種熵結合的經典算法。Soham Sarkar等[14]用差分進化算法求解Rényi熵下的最佳閾值；牛孝通等[15]用粒子群算法求解Ostu下的最佳閾值。相比于粒子群算法、遺傳算法以及差分進化算法，雞群算法的優化能力更強，所以本文采用雞群算法求解Tsallis熵函數下的最佳閾值，從而進行復雜圖像分割。

1 基于Tsallis熵的單閾值圖像分割原理

基于多重分形理論[16]，Tsallis熵可以用普通的熵公式推廣到非廣義系統，表達式如下：

(1)

式中，k表示系統的可能性總和，q表示Tsallis參數或熵指數系統的非伸縮度度量。本文中q=0.8。

系統的Tsallis熵可以用一個偽加性熵規則[17]進行描述，規則公式如下：

Sq(A+B)=Sq(A)+Sq(B)+(1-q)Sq(A)Sq(B)

(2)

該技術可用于尋找圖像閾值。假設存在一個圖像I，它有G個灰度{1，2，…，G}，用閾值t將灰度級分成A、B兩個區域，A為背景區域，B為目標區域。則A、B區域的每個像素概率為：

(3)

(4)

根據概率分布，A類、B類的Tsallis熵分別為：

(5)

(6)

A類、B類的Tsallis熵分別為背景熵、目標熵。根據Tsallis熵的偽加性熵規則，整個圖像的Tsallis熵為：

(7)

圖像的Tsallis熵是閾值t的函數，所以由Tsallis熵可以得到圖像的最佳閾值Topt為：

Top=argmax[Sq(t)]

(8)

2 基于Tsallis熵的多閾值分割原理

基于Tsallis熵的多閾值分割原理是在其單閾值分割原理基礎上得到的[18]。此時假設圖像I的灰度級為G，閾值個數為n-1，閾值向量為{t1,t2,…,tn-1}(0

(9)

Ak類的Tsallis熵為：

(10)

圖像的Tsallis總熵Sq(t1,t2,…,tn-1)為：

(11)

則此時最佳閾值向量Topt為：

Topt= argmax[Sq(t1,t2,…,tn-1)]

(12)

3 基于雞群算法的Tsalis熵多閾值圖像分割

3.1 雞群算法理論概述

雞群算法作為一種新的生物啟發式算法，其模仿雞群的分級秩序與雞群行為。雞群可以被分為幾個小組，不同的雞遵循不同運動規律[19-20]。在特定等級制度下，不同雞之間存在著激烈競爭。簡而言之，雞群算法可以由如下規則進行描述：

(1)在雞群中，將雞群分組，每組包含一只占據優勢地位的公雞，以及幾只母雞和小雞。

(2)在雞群中，如何對雞群進行分組，以及確認每只雞的身份(公雞、母雞、小雞)都取決于每只雞的適應值。排名靠前幾只雞的身份為公雞，每只公雞會成為每組雞的首領，而適應值最差的幾只雞會被指定為小雞，剩余雞都為母雞。母雞會隨機選擇組別，母雞和小雞之間的母子關系也是隨機建立的。

(3)一個群體中的等級秩序、統治關系、母子關系將保持不變，這些狀態每G步更新一次。

(4)母雞會跟隨著伴侶公雞尋找食物，與此同時，也會防止其它組的小雞偷吃它們的食物。假設母雞只會隨機偷走他人已發現的食物，小雞只會在母雞周圍尋找食物，則占統治地位的公雞在食物競爭中更具有競爭力。

3.2 雞群算法數學表述

具有極好適應值的公雞將優先獲得食物。簡而言之，該情況可以具體描述為：具有更好適應值的公雞比適應值差的公雞搜索食物范圍更廣。根據以上規則，數學表達式如下：

(13)

(14)

這里k∈[1,N]，且k≠i，randn(0,δ2)是一個均值為0、標準差為δ的高斯分布。ε是計算機上的最小正常量，用來避免零度空間誤差。k是公雞的索引，是一個隨機整數，代表第k只公雞，是從公雞群中隨機抽取的。f是對應x位置的適應值。

母雞跟隨其伴侶公雞搜尋食物，它們也會隨機偷取其它雞已發現的食物，占統治地位的母雞在競爭食物時比溫順的母雞更具有優勢。根據該規則，數學表達式如下：

(15)

(16)

S2=exp(fr2-fi)

(17)

這里rand是一個[0,1]之間的均勻隨機數，r1∈[1,2,…,N]是公雞的索引，是第i代母雞的伴侶，而r2∈[1,2,…,N]是雞(公雞或母雞)的索引，是隨機在雞群中選擇的，r1≠r2。

小雞圍繞著它們的母親搜尋食物，根據該現象得到的數學表達式如下：

(18)

3.3 基于雞群算法Tsallis熵多閾值分割原理

將雞群算法引入到基于Tsallis熵的圖像分割中，本質上是將Tsallis熵作為雞群算法的目標函數，充分利用雞群算法的尋優能力，求解基于Tsallis熵多閾值圖像分割的最佳閾值。算法步驟為：

(1)讀取圖像數據。

(2)初始化雞群算法，定義雞群算法的維數D(與閾值個數一致)、最大迭代次數M、公雞RN、母雞HN、小雞CN、初始位置x以及迭代次數t。

(3)將總Tsallis熵設置為目標函數，計算目標函數值，設定雞群粒子當前的全局最優值及全局最佳位置，迭代次數t=1。

(4)如果t|G=1，對當前目標函數值排序，建立雞群粒子等級制度，將雞群根據初始化時確定的公雞、母雞、小雞個數分為公雞群、母雞群、小雞群，并在母雞群中隨機選取m只母雞作為小雞群中小雞的母親。這里G代表更新雞群等級制度的代數。

(5) 利用公式(13)～(18)分別更新公雞群、母雞群、小雞群粒子的目標函數值以及對應位置。

(6)更新雞群當前粒子的當前最優值與當前最好位置。

(7)令迭代次數t=t+1，判斷是否達到最大迭代次數，若達到則退出算法；若沒有達到，則轉到步驟(4)。

4 實驗結果

為了驗證雞群算法能否準確、高效地求取基于Tsallis熵多閾值圖像分割的最佳閾值，本文安排4張圖像(rice、sisters、lena、cameraman)作為實驗對象，并分別安排窮舉法、雞群算法(CSO)、粒子群算法(PSO)、差分進化算法(DE)對4張圖像在閾值個數分別為2、3的情況下進行多閾值圖像分割處理。

為了使實驗結果更加公平，所有實驗均采用Inter(R) P2600 2.13G雙核處理器、4G內存、Window7操作系統與Matlab2014a仿真環境。

表1為CSO、PSO、DE參數列表，表2為窮舉法、CSO閾值與計算時間數據，表3為CSO、PSO、DE閾值數據，表4為CSO、PSO、DE適應值數據，表5為CSO、PSO、DE計算時間數據。圖1為rice、cells、lena、cameraman原始圖，圖2-圖5分別為rice、sisters、lena、cameraman圖像分割結果 (上層為二閾值圖像分割結果、下層為三閾值圖像分割結果，從左到右依次為窮舉法、CSO、PSO、DE圖像分割結果)。

表1 CSO、PSO、DE參數

表2 窮舉法、CSO閾值與計算時間數據

表3 CSO、PSO、DE閾值數據

表4 CSO、PSO、DE適應值數據

表5 CSO、PSO、DE計算時間比較

表2數據證明，在求解基于Tsallis熵的最佳閾值方面，CSO的閾值數據與窮舉法完全一致。窮舉法盡管是耗時最長的算法，卻是最精準的算法，這表明CSO能夠準確求解基于Tsallis熵的最佳閾值。在計算耗時方面：①在二閾值的情況下，對于rice圖像，窮舉法耗時約是CSO的4.2倍，對于sisters圖像，窮舉法耗時約是CSO的2.7倍，對于lena圖像，窮舉法耗時約是CSO的3.9倍，對于camerman圖像，窮舉法耗時約是CSO的4.3倍；②在三閾值的情況下，對于rice圖像，窮舉法耗時約是CSO的77.5倍，對于sisters圖像，窮舉法耗時約是CSO的96.1倍，對于lena圖像，窮舉法耗時約是CSO的69.3倍，對于cameraman圖像，窮舉法耗時約是CSO的90.1倍，表明CSO在耗時方面遠遠優于窮舉法。

圖1 rice、sisters、lena、cameraman原始圖像

表3數據為CSO、PSO、DE閾值數據，因為表2顯示CSO與窮舉法在閾值方面完全一致，說明CSO能夠精準求得最佳閾值。表3數據中CSO與PSO求得的閾值完全一致，但與DE所求閾值有一定差別，說明CSO與PSO都能夠精準地求解基于Tsallis熵的最佳閾值，只有DE無法精準求取相關閾值。

表4數據為CSO、PSO、DE的適應值數據。因為前文提到，Tsallis熵與適應值函數一致，最佳閾值與全局最優解一致，所以CSO與PSO在閾值方面一致，適應值也必然完全一致，表4數據證實了這一點。CSO與PSO適應值完全一致，但都大于DE的適應值，證明通過DE求得的最佳閾值并不是各圖像的實際最佳閾值，CSO、PSO在求解閾值的精準性方面優于DE。

表5數據為CSO、PSO、DE的計算耗時數據，計算耗時是判斷算法優越性最重要的測試性能之一。表5數據證明了無論是用2個閾值還是3個閾值分割圖像，CSO在計算耗時方面都優于PSO與DE。

從數據上分析，可以得出CSO在求解最佳閾值方面與精確性最高的窮舉法一致，在耗時方面要優于窮舉法、PSO、DE等經典方法。

圖2-圖5分別為rice、sisters、lena、cameraman圖像分割效果，進一步證實了表2-表5數據所得的結論。在二閾值圖像分割方面可以發現，窮舉法、CSO、PSO的圖像分割結果完全一致，且分割效果都優于DE。在二閾值rice圖像分割結果中，窮舉法、CSO、PSO與DE方法的圖像分割效果差距不明顯，但在二閾值sisters、lena、cameraman圖像分割結果中，可以清楚地發現窮舉法、CSO、PSO在圖像分割效果方面要更接近于原圖像，分割效果更好；在三閾值圖像分割方面，窮舉法、CSO、PSO圖像分割結果依然完全一致，但在DE圖像分割中，rice圖像分割結果有很多模糊的點，sisters、lena、cameraman圖像分割結果都失去了部分像素，證明只有得到最佳閾值才能精準地分割圖像，并且取得最好的分割效果。

圖2 基于Tsallis熵的窮舉法、CSO、PSO、DE二閾值、三閾值rice圖像分割結果

圖3 基于Tsalli熵的窮舉法、CSO、PSO、DE二閾值、三閾值sisters圖像分割結果

圖4 基于Tsallis熵的窮舉法、CSO、PSO、DE二閾值、三閾值lena圖像分割結果

圖5 基于Tsallis熵的窮舉法、CSO、PSO、DE二閾值、三閾值cameraman圖像分割結果

從圖像分割結果上看，窮舉法、CSO、PSO都能夠精準求解基于Tsallis熵的最佳閾值，且能夠獲得較好的分割結果，只有DE無法精確求取基于Tsallis熵的最佳閾值，分割結果較差。

5 結語

為了改善基于Tsallis熵的多閾值分割算法在求解多閾值問題時存在的計算量大、耗時長等問題，本文引入了雞群算法。實驗結果表明：雞群算法在求解基于Tsallis熵的最佳閾值及圖像分割效果方面與最精準的窮舉法、粒子群算法完全一致，但在耗時方面要遠遠優于窮舉法，略優于粒子群算法。與差分進化算法相比，在最佳閾值求解、圖像分割效果、計算耗時方面，雞群算法都要優于差分進化算法。綜上所述，雞群算法能夠精準地求解基于Tsallis熵的最佳閾值，且效果優于窮舉法、粒子群算法以及差分進化算法。