基于改進PSO的三維Tsallis熵圖像分割

吳浩然

(合肥工業大學 數學學院，安徽 合肥 230601)

0 引 言

圖像分割就是把圖像分成若干個特定的、具有獨特性質的區域并提出人們感興趣目標的技術和過程。現有的圖像分割方法主要分以下幾類：基于閾值的分割方法、基于區域的分割方法以及基于邊緣的分割方法。其中基于閾值的分割方法是最常見的方法，該方法根據圖像中目標與背景的灰度值的差異，通過設置一個或幾個閾值來將圖像分割成多個區域。目前比較成功的閾值方法有聚類方差法、熵方法等[1]。在這之中熵閾值分割方法又因為實現簡單且性能穩定而得到了廣泛的應用。20世紀80年代，學者們就開始將熵的概念應用在閾值選擇上。Pun首先將熵的概念引入圖像的閾值分割，提出了最大后驗熵法[2]，Kapur等人提出了一維最大Shannon熵閾值法[3]，Li和Lee提出了最小交叉熵閾值法[4]。

上述基于熵的閾值分割法中一般采用的都是一維Shannon熵，但Shannon熵具有廣延性，其會忽略兩個子系統之間的相互作用，放在圖像分割中就是忽略了目標和背景之間的相關性[1]。為了解決這個問題，Tsallis擴展了Shannon熵并提出了Tsallis熵[5]，Tsallis熵具有非廣延性，使用Tsallis熵進行圖像分割可以取得更好的結果。除此之外，由于一維熵閾值分割法是利用圖像的一維直方圖進行計算的，這在得到最佳分割閾值的過程中沒有利用到圖像的空間信息，因此圖像分割結果容易受到噪聲的干擾，而利用圖像的局部空間信息可以在一定程度上改善分割結果[6]，有學者據此引入了像素的鄰域灰度信息，提出了多種基于圖像二維直方圖的熵閾值分割方法，如二維Renyi熵閾值法[7]、二維Tsallis熵閾值法[8]等。擴展的二維方法能較好地抵抗高斯噪聲的干擾，但卻無法抵抗椒鹽噪聲的干擾[9]，因此有學者引入了鄰域中值提出了三維分割算法，如三維Otsu法[10]、三維Tsallis熵法[11]等。上述三維閾值分割方法都是利用圖像的原始灰度，鄰域平均灰度，以及鄰域中值組成圖像的三維直方圖，并未利用到圖像的梯度信息，這存在著一定的局限性[9]。受文獻[9]啟發，該文引入了梯度信息，將其與圖像像素的鄰域均值、鄰域中值結合構成圖像的三維直方圖，并結合Tsallis熵理論提出了三維Tsallis熵閾值分割方法。將提出的新的三維Tsallis熵閾值分割法與該文提出的一種新的改進粒子群優化算法結合進行圖像閾值選擇，取得了較好的分割結果。由上所述，相對于一維熵閾值分割法，二維熵閾值法進行分割可以取得更好的結果，但同時分割步驟也變得更加繁瑣，計算量也變得更大，從而運算時間也變得更長。因此為了提高分割效率，有學者提出了利用元啟發式算法結合二維熵來進行閾值選擇。與二維熵閾值分割法相比，三維熵閾值分割法的計算量更大，因此該文同樣使用元啟發式算法對三維熵閾值分割法進行優化以提高分割效率。

啟發式算法(heuristic algorithm)是一種基于人的主觀經驗或自然規律所構造的算法，能夠在可接受的計算花費(如計算時間)下給出待解決組合優化問題的一個較優的可行解，但該可行解與目標問題的最優解之間的誤差一般無法預計。元啟發式算法(meta-heuristic algorithm)是啟發式算法的改進，由于元啟發式算法較少依賴算法本身組織結構，因此其通用性強、泛化性更好[12]。遺傳算法[13]是(genetic algorithm，GA)較早提出來的一種元啟發式算法，文獻[14]就將遺傳算法與二維最大熵法結合進行圖像分割，在分割精度明顯優于一維最大熵法的情況下分割速度與一維最大熵法基本相同。除此之外，文獻[15-16]也都將遺傳算法應用于圖像分割領域。鯨魚優化算法[17](whale optimization algorithm，WOA)是一種受鯨魚社會行為啟發的元啟發式算法，文獻[18]將鯨魚優化算法與多閾值Otsu法結合進行圖像分割，實現了更高的分割精度。除此之外，文獻[19-20]也將改進的鯨魚優化算法與熵閾值法結合進行圖像分割。

粒子群優化算法[21](particle swarm optimization，PSO)是由Kennedy和Eberhart于1995年提出的一種基于群體智能的元啟發式優化算法，由于操作簡單、收斂速度快而得到了廣泛的應用，文獻[22]就將PSO與二維最大Tsallis熵結合進行閾值選擇，取得了較好的結果。雖然PSO算法收斂速度快，但仍存在早熟收斂的問題,并且具有種群多樣性隨迭代數增加下降過快、有可能不收斂到全局最優解等缺點，這將會導致分割閾值選取不夠精確，從而圖像分割精度較低。因此有學者通過不斷改進這些元啟發式算法以獲得更好的效果。該文通過修改粒子群優化算法的粒子迭代方式，得到了一種在低維環境下可以有效避免局部最優的改進粒子群優化算法，然后將其與三維Tsallis熵結合對圖像進行分割，取得了更好的分割精度。

1 三維Tsallis熵的圖像分割原理

1.1 二維Tsallis熵閾值分割

取圖像自身的灰度值以及對應的鄰域平均灰度值構造二維直方圖，如圖1所示。

圖1 二維直方圖

在圖1中，(s,t)為假設的閾值向量，可以看出，向量(s,t)將上圖分割為四個部分，其中區域A和B表示目標或背景，區域C和E表示邊界點或噪聲。

則目標和背景兩類的二維Tsallis熵分別為：

(1)

(2)

式中，L為圖像灰度級，q為待定系數，其代表了Tsallis熵的非廣延性，文中q取0.8。由此可得圖像總的二維Tsallis熵為：

(3)

以上公式為文獻[8]和文獻[23]的工作。

1.2 三維Tsallis熵分割原理

假設f為大小M×N、灰度級為L的一幅圖像，用f(x,y)表示位于圖像(x,y)處的像素點的灰度值，g(x,y)表示以(x,y)為中心的3×3的像素鄰域的平均灰度值。在此基礎上再設h(x,y)為以(x,y)為中心的3×3鄰域灰度中值，z(x,y)為以(x,y)為中心的3×3鄰域的梯度值。其中梯度的計算如下所示：

z(x,y)=9|f(x,y)-g(x,y)|

(4)

該文則將g(x,y)、h(x,y)與z(x,y)三個元素作為三維Tsallis熵的組成部分構成三維直方圖，如圖2所示。

圖2 三維直方圖

由圖2可以看出，假設的三個閾值(s,t,q)將圖中像素劃分為8個部分。其中區域0，1，2，3位于梯度閾值q的下方，即位于該區域的灰度值梯度較小，這表示該區域的像素之間灰度值變化不大，所以一般認為目標與背景位于該區域。反之區域4，5，6，7的梯度值則較大，這表示該區域像素之間灰度值變化較大，一般認為邊緣和噪聲位于該區域。因為位于目標或背景的灰度值比較相似，因此位于目標或背景的像素點處的鄰域平均灰度值與中值則會非常接近，從而在區域0，1，2，3中，位于對角線處的區域0，1便代表背景和目標(假設區域0為背景，區域1為目標)，區域2，3則因為像素點很少而可以忽略不計。與之同理，邊緣和噪聲點主要出于區域4，5之中，區域6，7則可以忽略不計。其中區域4中的邊緣信息為背景區域向目標區域過度的邊緣信息，區域5為目標區域向背景區域過度的邊緣信息[9]。

每個像素對(i,j,k)出現的聯合概率為：

(5)

式中，rijk表示像素對(i,j,k)出現的次數。則區域0，1，4，5的聯合密度分別為：

(6)

(7)

(8)

(9)

則根據上述公式以及上節的Tsallis熵公式可得區域0，1，4，5的三維Tsallis熵分別為：

(10)

(11)

(12)

(13)

據上所述，該文將區域0，4作為背景，1，5作為目標，根據Tsallis熵的定義，提出了以下圖像總的熵的公式：

(14)

只需求出式(14)最大值即可得到最優閾值，在求得最優閾值(s*,t*,q*)之后按以下公式對圖像進行分割：

(15)

由上文所述，圖像的背景與目標均處于閾值q*以下，所以公式(15)未利用到閾值q*。

2 改進粒子群優化算法

2.1 粒子群優化算法

(16)

(17)

式中，d為粒子的某一個維度。c1和c2為加速度系數，二者通常情況下都取2，R1(t)與R2(t)為[0,1]之間的隨機數。ω為慣性權重，通常是隨著迭代次數的增加而線性減小，最大值一般取ωmax=0.9，最小值一般取ωmin=0.4，ω的公式如下：

(18)

式中，Max_iter為最大迭代次數。

2.2 綜合學習改進粒子群優化算法

如式(16)、(17)所示，在粒子群優化算法中，每次迭代每個粒子都只向當前位置，自身的歷史最優位置pbesti以及所有粒子所發現的全局歷史最優位置gbest進行學習，這導致粒子在更新時其余粒子信息使用不足[25]。且每當有粒子陷入局部最優時，由于gbest的存在，其他粒子都會向該粒子學習，這將會導致算法陷入局部最優。因此為了避免算法陷入局部最優，該文引入了綜合學習策略[26]并同時修改PSO中粒子的學習方式，使粒子在更新時盡量減少其對gbest的依賴并增加對其他粒子信息的使用。

不失一般性，考慮以下最小化問題：

minf=f(x)

(19)

在綜合學習策略中，粒子在更新時，每個維度都會向不同的粒子學習。具體規則如下所述：在粒子更新時，粒子的每個維度都會對應生成一個隨機數，然后將隨機數與學習概率Pc進行比較，若隨機數較大，則粒子該維度將之從自身pbest的對應維度進行學習。若學習概率Pc更大，粒子該維度則向其他粒子對應的維度進行學習，而學習的對象則通過競爭選擇而來。競爭選擇的具體規則如下所述：首先隨機選擇兩個粒子，然后比較這兩個粒子的歷史最優值(將兩個粒子的pbest帶入評價函數求得的適應值)，選擇適應值較好的一個將其pbest對應的維度當成粒子更新時某個維度的學習對象。

受綜合學習策略的啟發，該文提出了綜合學習改進粒子群優化算法(comprehensive learning improved particle swarm optimization，CLIPSO)，具體原理如下：首先，將粒子按行組為一個矩陣，每個粒子為一行，行順序隨機確定，然后將所有粒子按標準PSO的迭代規則迭代一次。這之后位于矩陣第一行的粒子先按照PSO的迭代法則更新自身位置，即該粒子的學習對象為自身歷史最優位置pbesti與全局歷史最優位置gbest，然后剩下的粒子按照矩陣的行順序從上往下依次更新位置，但這些粒子的學習對象與第一個粒子不同，它們在更新位置之前會生成一個隨機數，然后將該隨機數與事先設定的學習概率Pc(文中Pc取0.8)進行比較，若學習概率較大，則粒子只向自身的歷史最優值pbesti進行學習。反之若隨機數較大，則在該粒子上方隨機挑選兩個粒子，再對這兩個粒子的當前適應值進行對比，選擇較優的粒子作為當前更新位置的粒子的學習對象，其中i={2,3,…,N}。

在上述CLIPSO的迭代步驟中，除了位于矩陣第一行的粒子會向全局歷史最優值gbest學習外，其余粒子均不會向gbest學習，雖然這會避免粒子被gbest吸引而輕易地陷入局部最優，但由于粒子是隨機分布的且在算法開始的時候粒子矩陣的行順序也是隨機確定的，因此粒子在迭代過程中可能會缺少全局信息，從而導致算法收斂速度變慢。該文將所有粒子都更新過一次位置之后迭代一次，然后每隔一定的迭代次數(設為m代)，就對所有的粒子整體進行一次PSO迭代以獲取全局最優信息，文中m取15。

CLIPSO具體的迭代公式如下：

(20)

(21)

(22)

式中，2≤i≤N,1≤j

3 CLIPSO實驗與分析

3.1 實驗準備

為了驗證綜合學習改進粒子群優化算法的尋優能力以及跳出局部最優的能力，使用了5個經典的測試函數來驗證CLIPSO的性能。這5個測試函數中，f1為單峰函數，其余為多峰函數，所有函數解空間均設為2維，各函數參數如表1所示。

表1 函數參數

續表1

3.2 對比結果與分析

在這一部分，將CLISPO與PSO本體以及量子粒子群優化算法(quantum-inspired particle swarm optimization，QPSO)[27]、遺傳算法、鯨魚優化算法在五個測試函數上的測試結果進行比較。所有算法均使用相同的種群大小40和最大迭代次數7 500。每個算法都在測試函數上運行30次，然后取平均值。實驗環境為：Intel(R) Core(TM)i7-6700HQ CPU @2.60 GHz。RAM 8.00 GB，Windows10操作系統，MatlabR2016a。運行結果見表2。

表2 各算法在測試函數上的比較

表2中，mean表示算法運行30次所得結果的平均值，min表示這30次結果中的最優值，max表示這30次結果中的最差值，std表示這30次結果的標準差，time表示算法運行的時間。由表2數據可以發現，CLIPSO在這5個基準函數上的平均表現比較優異。在單峰函數f1上，CLIPSO、QPSO、WOA每次都可以發現函數的最優值，同時PSO與GA則多次陷入了局部最優。在函數f2上，CLIPSO多次陷入了局部最優，但在該函數上只有WOA算法每次都達到了全局最優。在函數f3上，只有CLIPSO每次都能收斂到全局最優值，其余算法均不同程度地陷入了局部最優。在函數f4上，CLIPSO與QPSO、WOA均能次次達到全局最優，PSO與GA算法則多次陷入了局部最優。在函數f5上，所有算法均陷入了局部最優，但CLIPSO所能達到的效果最接近全局最優值。由此可以得知，CLIPSO可以在一定程度上避免局部最優。但從表中也可以看出，CLIPSO的運行時間要長于其他算法，這也是未來需要改進的方向。

4 基于三維最大Tsallis熵的圖像分割實驗

4.1 實驗準備

為了驗證CLIPSO結合三維Tsallis熵的分割精度，對Lena、Camera這兩張圖片進行了加噪處理，然后將CLIPSO結合三維Tsallis熵對這些圖片進行分割并將分割結果與CLIPSO結合二維Tsallis熵對這些圖片的分割結果進行對比。實驗中CLIPSO種群數設置為20，最大迭代次數設置為100。實驗環境為：Intel(R) Core(TM)i7-6700HQ CPU @2.60 GHz，RAM 8.00 GB，Windows10操作系統，MatlabR2016a。分割用的圖片如圖3所示。

圖3 分割用圖像

4.2 三維Tsallis熵與二維Tsallis熵分割結果對比

本節將CLIPSO分別結合二維Tsallis熵與三維Tsallis熵對Lena、Camera兩張圖片以及它們的加噪圖片進行分割，操作環境如上所述，圖片的分割結果如圖4和圖5所示。

圖4 Lena分割結果對比

在圖4、圖5中，位于每張圖片下方的是圖片分割的時間與閾值，圖(a)是原圖的分割結果，圖(b)是添加了高斯噪聲的分割結果，圖(c)是添加了椒鹽噪聲的分割結果，圖(d)是添加了混合噪聲的分割結果。

由圖4可以看出，在圖4(a)上，CLIPSO結合三維Tsallis熵的方法清晰地將人臉分割了出來，但CLIPSO結合二維Tsallis熵的方法卻無法完全將人臉與背景分離。在圖4(b)上，二者表現相同但效果較差。在圖4(c)上，二維Tsallis熵方法的分割結果存在著大量的噪聲點，而三維Tsallis熵的分割結果則只有少量的噪聲點。在圖4(d)上，二維Tsallis熵與三維Tsallis熵的分割結果均存在著噪聲點，但三維Tsallis熵的分割圖片上的噪聲點要明顯少于二維Tsallis熵分割圖片上的噪聲點。

在圖5中，二維Tsallis熵與三維Tsallis熵均清晰的分割出了目標與背景，但二維Tsallis熵在添加了圖5(b)上的分割結果中存在著少量的噪聲點，在圖5(c)上的分割結果中存在著大量的噪聲點，在圖5(d)上的分割結果中則幾乎整張圖片都布滿了噪聲點。與此相反，三維Tsallis熵的所有分割結果幾乎沒有區別，僅在添加了混合噪聲的圖片上存在著極少的噪聲點。

圖5 Camera分割結果對比

雖然總體來說三維Tsallis熵閾值分割法可以有效地避免噪聲干擾，但其分割時間卻遠遠大于二維Tsallis熵。這是因為三維Tsallis熵閾值分割法代碼的時間復雜度要遠遠大于二維Tsallis熵閾值分割法代碼的時間復雜度。為了解決三維熵閾值分割法的時間復雜度過大的問題，文獻[9-10]都提出了三維熵的遞推公式以減小算法的時間復雜度。而該文選擇采用元啟發式算法來優化三維Tsallis熵閾值分割法，雖然最終分割時間仍遠大于二維Tsallis熵閾值分割法，但與文[9]提到的三維OTSU法相比，分割時間約為其一半。與同樣是文獻[9]提出的利用遞推公式的三維Renyi熵閾值分割法相比，分割時間則與之相近。

5 結束語

由于二維Tsallis熵閾值分割法難以抵抗部分噪聲的干擾，通過引入圖像的鄰域均值、鄰域中值以及梯度信息構建了三維直方圖，并將其與Tsallis熵理論結合提出了一種三維Tsallis熵閾值分割方法。實驗表明，與二維Tsallis熵閾值分割方法相比，三維Tsallis熵閾值分割法可以有效地抵抗各種噪聲的干擾。

為了更精確地進行圖像分割，提出了一種新的改進粒子群優化算法：綜合學習改進粒子群優化算法，將其與前面提出的三維Tsallis熵結合進行圖像分割。實驗表明，綜合學習改進粒子群優化算法可以在低維環境下有效地避免陷入局部最優，且其與三維Tsallis熵結合可以更精確地進行圖像分割。

雖然綜合學習改進粒子群優化算法與三維Tsallis熵結合可以更精確地分割圖像，三維熵閾值分割方法的時間仍然要遠遠高于二維熵閾值分割方法，因此在后續的改進中，可以嘗試將綜合學習改進粒子群優化算法中穿插的PSO替換成其他更快的PSO變體，或引入如文獻[10]所述的三維熵遞推公式，也許可以加快圖像的分割速度。