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

鄭和平，姚 儉

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

0 引言

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

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

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

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

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

(1)

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

系統(tǒng)的Tsallis熵可以用一個(gè)偽加性熵規(guī)則[17]進(jìn)行描述，規(guī)則公式如下：

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

(2)

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

(3)

(4)

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

(5)

(6)

A類、B類的Tsallis熵分別為背景熵、目標(biāo)熵。根據(jù)Tsallis熵的偽加性熵規(guī)則，整個(gè)圖像的Tsallis熵為：

(7)

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

Top=argmax[Sq(t)]

(8)

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

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

(9)

Ak類的Tsallis熵為：

(10)

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

(11)

則此時(shí)最佳閾值向量Topt為：

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

(12)

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

3.1 雞群算法理論概述

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

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

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

(3)一個(gè)群體中的等級秩序、統(tǒng)治關(guān)系、母子關(guān)系將保持不變，這些狀態(tài)每G步更新一次。

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

3.2 雞群算法數(shù)學(xué)表述

具有極好適應(yīng)值的公雞將優(yōu)先獲得食物。簡而言之，該情況可以具體描述為：具有更好適應(yīng)值的公雞比適應(yīng)值差的公雞搜索食物范圍更廣。根據(jù)以上規(guī)則，數(shù)學(xué)表達(dá)式如下：

(13)

(14)

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

母雞跟隨其伴侶公雞搜尋食物，它們也會隨機(jī)偷取其它雞已發(fā)現(xiàn)的食物，占統(tǒng)治地位的母雞在競爭食物時(shí)比溫順的母雞更具有優(yōu)勢。根據(jù)該規(guī)則，數(shù)學(xué)表達(dá)式如下：

(15)

(16)

S2=exp(fr2-fi)

(17)

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

小雞圍繞著它們的母親搜尋食物，根據(jù)該現(xiàn)象得到的數(shù)學(xué)表達(dá)式如下：

(18)

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

將雞群算法引入到基于Tsallis熵的圖像分割中，本質(zhì)上是將Tsallis熵作為雞群算法的目標(biāo)函數(shù)，充分利用雞群算法的尋優(yōu)能力，求解基于Tsallis熵多閾值圖像分割的最佳閾值。算法步驟為：

(1)讀取圖像數(shù)據(jù)。

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

(3)將總Tsallis熵設(shè)置為目標(biāo)函數(shù)，計(jì)算目標(biāo)函數(shù)值，設(shè)定雞群粒子當(dāng)前的全局最優(yōu)值及全局最佳位置，迭代次數(shù)t=1。

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

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

(6)更新雞群當(dāng)前粒子的當(dāng)前最優(yōu)值與當(dāng)前最好位置。

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

4 實(shí)驗(yàn)結(jié)果

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

為了使實(shí)驗(yàn)結(jié)果更加公平，所有實(shí)驗(yàn)均采用Inter(R) P2600 2.13G雙核處理器、4G內(nèi)存、Window7操作系統(tǒng)與Matlab2014a仿真環(huán)境。

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

表1 CSO、PSO、DE參數(shù)

表2 窮舉法、CSO閾值與計(jì)算時(shí)間數(shù)據(jù)

表3 CSO、PSO、DE閾值數(shù)據(jù)

表4 CSO、PSO、DE適應(yīng)值數(shù)據(jù)

表5 CSO、PSO、DE計(jì)算時(shí)間比較

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

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

表3數(shù)據(jù)為CSO、PSO、DE閾值數(shù)據(jù)，因?yàn)楸?顯示CSO與窮舉法在閾值方面完全一致，說明CSO能夠精準(zhǔn)求得最佳閾值。表3數(shù)據(jù)中CSO與PSO求得的閾值完全一致，但與DE所求閾值有一定差別，說明CSO與PSO都能夠精準(zhǔn)地求解基于Tsallis熵的最佳閾值，只有DE無法精準(zhǔn)求取相關(guān)閾值。

表4數(shù)據(jù)為CSO、PSO、DE的適應(yīng)值數(shù)據(jù)。因?yàn)榍拔奶岬?，Tsallis熵與適應(yīng)值函數(shù)一致，最佳閾值與全局最優(yōu)解一致，所以CSO與PSO在閾值方面一致，適應(yīng)值也必然完全一致，表4數(shù)據(jù)證實(shí)了這一點(diǎn)。CSO與PSO適應(yīng)值完全一致，但都大于DE的適應(yīng)值，證明通過DE求得的最佳閾值并不是各圖像的實(shí)際最佳閾值，CSO、PSO在求解閾值的精準(zhǔn)性方面優(yōu)于DE。

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

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

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

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

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

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

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

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

5 結(jié)語

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