基于閾值和粒子群聚類算法結(jié)合的圖像分割方法作業(yè).

1、基于粒子群優(yōu)化算法的最佳熵閾值圖像分割摘 要：圖像分割是自動目標(biāo)識別的關(guān)鍵和首要步驟。群智能作為一類新興的演化計算技術(shù)已被越來越多的研究者關(guān)注。論文研究將群智能中的粒子群優(yōu)化算法應(yīng)用到圖像分割中，提出了一種新的圖像分割算法。新方法基于最佳熵閾值分割技術(shù)，用粒子群優(yōu)化算法自適應(yīng)選取分割閾值。在仿真實驗中，針對camera基準(zhǔn)圖像，將遺傳算法與粒子群優(yōu)化算法分別獨立運行10次，對10次得到的閾值以及均值、方差進行了比較，并將運行時間作為算法復(fù)雜度的評價指標(biāo)。統(tǒng)計結(jié)果顯示，論文算法不僅能夠?qū)D像進行準(zhǔn)確的分割，而且運行時間明顯較短。仿真結(jié)果表明，基于粒子群優(yōu)化的圖像分割算法是可行的、有效的。關(guān)鍵詞：

2、圖像分割；粒子群優(yōu)化；最佳熵；遺傳算法0 引言圖像分割是圖像處理和前期視覺中的基本技術(shù)，是大多數(shù)圖像分析和視覺系統(tǒng)的重要組成部分。圖像分割應(yīng)用一種或多種運算將圖像分成一些具有類似特性（如顏色、紋理、密度等）的區(qū)域，主要有閾值方法、邊緣檢測法、區(qū)域跟蹤法等。其中，閾值方法因其簡單且性能穩(wěn)定而成為圖像分割中的基本技術(shù)之一。Otsu等人為控制圖像分割造成的信息損失而提出的一種基于信息論熵準(zhǔn)則的圖像閾值自動選取方法引起了人們的極大關(guān)注，其理論研究及實際應(yīng)用均獲得重大突破1。粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是由Kennedy和Eberhart于1995年提

3、出的一種基于群智能（SwarmIntelligence）的演化計算技術(shù)。PSO的優(yōu)點在于流程簡單易實現(xiàn)，算法參數(shù)簡潔，無需復(fù)雜的調(diào)整，因此，在短短10年內(nèi)，PSO被迅速地應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制、數(shù)據(jù)聚類等領(lǐng)域3。但是國內(nèi)外將PSO用于圖像處理的相關(guān)研究成果尚不多見。本文將粒子群優(yōu)化算法應(yīng)用到圖像分割中，提出了一種基于最佳熵閾值分割技術(shù)的圖像分割算法。仿真實驗表明，新算法不僅能夠?qū)D像進行準(zhǔn)確的分割，而且能夠以較少的計算代價得到最優(yōu)閾值。1 粒子群優(yōu)化算法1995年，美國的Kenney博士和Eberhart博士從對鳥群捕食的行為觀察研究受到啟發(fā)，提出了一種新的仿生類智能優(yōu)化算

4、法粒子群優(yōu)化算法（Particle Swarm Optimization, PSO）。粒子群算法將每個個體看作是D維搜索空間中的一個沒有體積沒有質(zhì)量的粒子，在搜索空間中以一定的速度飛行，并根據(jù)對個體和集體的飛行經(jīng)驗的綜合分析來動態(tài)調(diào)整這個速度5。1.1 基本原理PSO對鳥群的捕食行為過程進行模擬，由此得到啟發(fā)并應(yīng)用于解決優(yōu)化問題。在此，我們首先給出以下兩個定義：（1）粒子：在d維搜索空間中的每只鳥可看是待優(yōu)化問題的一個解，每只鳥被稱之為“粒子”，粒子x是d維搜索空間的粒子。（2）粒子群：由n個粒子共同組成的一個群體(粒子允許重復(fù))，簡稱粒子群。n是粒子群的規(guī)模。在PSO算法中，粒子以一定的速度

5、在搜索空間中飛行，并根據(jù)自己的飛行經(jīng)驗及同伴的飛行經(jīng)驗來調(diào)整相應(yīng)的速度和方向，這種調(diào)整表現(xiàn)在粒子使用個體極值和全局極值來更新自己，這兩個極值分別來自粒子本身飛行到的最好位置pbest（即粒子所經(jīng)歷的最優(yōu)解）和整個種群目前所經(jīng)歷的最好位置pgbest。對粒子當(dāng)前位置的好壞可以由有一個被優(yōu)化的函數(shù)決定的適應(yīng)度值來作出判斷。此外，若采用粒子群體中的一部分作為粒子的鄰居，則鄰居粒子局部極值中的最優(yōu)值為全局極值。粒子在飛行過程中，通過個體與種群間不斷的相互交流和學(xué)習(xí)進行自我更新，最終飛至最優(yōu)解位置或其鄰近區(qū)域。在粒子每次迭代(飛行)中，粒子遵循由Shi Y和Eberhart RC提出的全局優(yōu)化模型，即：

6、 (1-1) (1-2)其中，vk是粒子的速度矢量，xk 表示粒子當(dāng)前的位置，pbestk 表示粒子自己找到的最優(yōu)解的位置，pgbestk 表示整個種群目前所找到的最優(yōu)解的位置。vk+1 是vk 、pbestk-xk 和pgbest-xk 的矢量和。在此，粒子的各維速度均被限定在最大速度vmax與最小速度vmin 內(nèi)，若更新后的某一維速度超過限定的速度范圍，則該維的速度將按下述方式重新設(shè)置，即: (1-3)另外，粒子群參數(shù)還包括慣性權(quán)重，加速常數(shù)c1和c2，稱為學(xué)習(xí)因子。兩個隨機數(shù)r1和r2 。1.2 參數(shù)的描述和分析（1）是粒子群優(yōu)化算法搜索能力的極其重要的參數(shù)，粒子飛行過程中，若粒子察覺伙

7、伴狀況較好時，則自動對進行某種方式的調(diào)整。設(shè)定較大的慣性權(quán)值有助于搜索一個新的區(qū)域，而較小的慣性權(quán)值則有利于在當(dāng)前搜索區(qū)域進行仔細(xì)搜索。實驗中，通常設(shè)定的取值范圍介于0.9,0.4之內(nèi)，其動態(tài)調(diào)整方式為: (1-4)其中，max表示慣性權(quán)重的最大值；min表示慣性權(quán)重的最小值；itermax表示最大迭代次數(shù)，iter表示當(dāng)前迭代次數(shù)。通過動態(tài)的調(diào)整自我，能夠保證粒子在飛行前期具有很強的全局搜索能力，當(dāng)接近搜索結(jié)束時，在局部范圍內(nèi)又能夠做精細(xì)的搜索。（2） 加速常數(shù)c1和c2的作用在于增強粒子自身及粒子群體在飛行中的指導(dǎo)性，加速粒子向 pbest和pgbest的運動。設(shè)定較小的值能夠使得粒子在被

8、搜索空間內(nèi)之前在目標(biāo)區(qū)域外徘徊，而高的值易導(dǎo)致粒子突然沖向或越過當(dāng)前的目標(biāo)區(qū)域。c1和c2分別被稱為認(rèn)識系數(shù)和稱為社會系數(shù)。PSO算法中包含3個權(quán)重因子：慣性權(quán)重、及加速常數(shù)c1 和c2。慣性權(quán)重旨在讓粒子保持自身的運動慣性，并使粒子能進一步擴展搜索空間，從而有能力搜索新的區(qū)域。c1 和c2 表示將每個粒子推向pbest和pgbest位置的一種統(tǒng)計加速項的權(quán)重。低的值使得粒子在被拉回搜索空間之前，可以在目標(biāo)區(qū)域外徘徊，設(shè)定較高的值則易導(dǎo)致粒子突然越過或沖向目標(biāo)區(qū)域。若沒有后面的兩部分，即c1和c2 都為 0，粒子以當(dāng)前的速度一直作勻速飛行，直至抵到邊界。由于搜索僅在有限的區(qū)域內(nèi)進行，所以較難找

9、到較好的解。若第一部份=0，粒子的速度取決于其當(dāng)前位置 pbest 和所經(jīng)歷的最好位置pgbest ，速度本身并不具有記憶性。如果某個粒子位于全局最好位置，此時，該粒子將保持靜止。而種群中其它粒子飛向自己最好位置 pbest 和全局最好位置pgbest 的加權(quán)中心。由此，粒子群體將搜索到當(dāng)前全局最好位置，類似一個局部算法。當(dāng)加上第一部分后，粒子能夠?qū)Ξ?dāng)前的搜索空間進行擴展，即第一部分具有一定的全局搜索能力。在某種程度上，使得能夠針對不同的搜索問題，對算法的全局及局部搜索能力進行平衡調(diào)整。若省略第二部分，即c1=0，此時，粒子缺少認(rèn)知能力，即“只有社會”的模型。然而，在粒子群體間的相互作用下，粒

10、子有能力進入新的搜索空間。并且它的收斂速度相比標(biāo)準(zhǔn)版本更快，對復(fù)雜問題，比標(biāo)準(zhǔn)版本更易陷入局部最優(yōu)點。若省略第三部分，即c2 =0，則粒子間沒有社會信息共享，即“只有認(rèn)知”的模型。由于個體間缺少交互，一個規(guī)模為n的粒子群體相當(dāng)于進行了n個單獨粒子的運行，求得解的幾率非常小。過去，將設(shè)定為 1，c1和c2均設(shè)定為2，因此，需要調(diào)節(jié)的唯一參數(shù)是vmax ，通常，將每維變化設(shè)定在10% 20%。引入慣性權(quán)重可在某種程度上消除對vmax的需要，由于其作用都是維護全局和局部搜索能力的平衡。這樣，當(dāng)vmax增加時，平衡搜索通過減小來達到。但的減小會讓所需的迭代次數(shù)變小。因此，可設(shè)定每維變量的變化范圍為vm

11、ax，僅對進行調(diào)節(jié)。研究表明：若慣性權(quán)重值較大，則有利于跳出局部極小點；反之，則有利于算法收斂。因此，可以采用一種自適應(yīng)調(diào)整的策略，即伴隨著迭代的進行，的值以線性方式遞減取值。對全局搜索而言，良好的方法是在搜索前期以較高的探索能力去得到合適的種子，而在搜索后期以較高的開發(fā)能力達到加快收斂速度的目的。因此，可設(shè)定隨時間線性減小，比如由1.3到0，或由0.8到0.4，或由0.96到0.3等。1.3 粒子群優(yōu)化算法的實現(xiàn) 算法具體步驟描述如下：Step 1：參數(shù)初始化，設(shè)定粒子群規(guī)模為n，產(chǎn)生n個隨機初始解，并隨機產(chǎn)生n個初始速度；Step 2：根據(jù)各個粒子的當(dāng)前位置及速度產(chǎn)生每個粒子的新位置；Wh

12、ile (迭代次數(shù)規(guī)定迭代次數(shù)) doStep 3：計算各粒子新位置的適應(yīng)值；對于每個粒子，如果粒子的適應(yīng)值優(yōu)于粒子原先的個體極值pbest，則用當(dāng)前適應(yīng)值替換掉個體極值pbest；Step 4：由粒子群體的各個體極值pbest求解出全局極值pgbest；Step 5：根據(jù)（1-14）式重新設(shè)定粒子的速度，并限制在vmax內(nèi)；Step 6：根據(jù)（1-15）式，重新設(shè)定當(dāng)前的位置。End2 基于粒子群算法的最佳熵閾值圖像分割2.1 熵和信息量假定有一組離散的符號集v1，v2，.，vm ,每個符號具有不同的出現(xiàn)概率Pi 。為了測定由這組符號組成的特定序列的隨機特性（不確定性或不可預(yù)測性），一種離散

13、分布的熵定義如下： (2-1)其中，對數(shù)采用2為底數(shù)，熵的單位為“比特”。若是連續(xù)的狀態(tài)，則常采用以e(=2.71828)的底數(shù)，此時，熵的單位被稱之為“奈特”(nat)。若一個符號的出現(xiàn)概率是0，定義 0log0 = 0 (因lim PlogP = 0)。通常情況下，對于答案為是否(yes/no)的問題，出現(xiàn)其一的概率為0.5, 那么此時的熵為 1(比特)。式(2-1)采用數(shù)學(xué)期望算子的形式，可以改寫為：H = E log(1/ P)?？梢詫?P 看作為一個隨機性的變量， 其值可以取為P1, P2,.,Pm。log2 1/ P 可稱為驚奇率: 若只有一個符號vk的概率Pk不為0，而其余符號的

14、概率都為0，即僅僅Pk =1 ,那么當(dāng)符號vk 以一定的概率出現(xiàn)時,就不存在任何的驚奇了,由于已經(jīng)知道別的符號均不可能出現(xiàn)。熵的值一般并不依賴于符號自身，而只依賴于符號自身的出現(xiàn)概率。對于m個給定的符號，若不同符號出現(xiàn)的概率相同時，則對應(yīng)的熵值將會達到最大。即每個符號的出現(xiàn)概率均相同(為 1/m)時,下一個將出現(xiàn)某個符號的不確定性程度將會達到最大程度。另一種極端的情況是：當(dāng)某個符號的概率為1,而其它的符號的概率均為 0 時，熵將達到最小值0比特，此時可以完全準(zhǔn)確預(yù)測下一個將要出現(xiàn)的某個符號。就連續(xù)的情況而言，熵的定義為 (2-2)若用數(shù)學(xué)期望的形式來描述，則H=EIn(1/P)。需指出的是，在

15、連續(xù)概率密度函數(shù)中，如果均值u和方差2都設(shè)定為某固定值，高期分布將會使熵達到最大值（比特）。若均方差趨近于0,即降低x的分布程度，則高斯函數(shù)將趨向于狄拉克函數(shù)： 和 (2-3) 很明顯，此時的熵將取最小值，為負(fù)無窮大(H =比特)。而函數(shù)的概率分布，可以很明確的確定出 a就是每次出現(xiàn)的x的值。2.2 圖像分割的最優(yōu)熵閾值最大熵（entroy）閾值法是圖像閾值分割的一種常用方法，由Kapur等人首次提出，基本思想是在圖像分割中應(yīng)用來自于信息論中的Shannon熵（香農(nóng)熵）的概念，像素的灰度作為變量，通過測量灰度直方圖中的熵值，最終得到待分割圖像的的最佳閾值，其基本方式是使圖像中目標(biāo)與背景分布的信

16、息量達到最大。對于較為復(fù)雜的圖像而言，閾值分割方法的困難在于如何選取合適的閾值。當(dāng)前，國內(nèi)外不少學(xué)者針對該問題進行了深入的研究，并提出了許多新的方法，如近年來的自動選取閾值方法中，受人矚目的重要方法之一是基于最大熵原則選擇閾值。該方法的基本思想是將圖像的灰度直方圖劃分成兩個或多個獨立的類，這樣各類的總值將會達到最大，這樣選擇閾值將獲得最大的信息量。信息論中用熵作為一種不確定性的度量方式，已經(jīng)被應(yīng)用于不同的研究領(lǐng)域，最大熵閾值法是將信息控制論中的香農(nóng)熵的概念應(yīng)用于圖像分割中，在灰度直方圖的基礎(chǔ)上，以灰度為變量，通過計算灰度直方圖的熵，從而找出圖像分割的最佳閾值。在某種程度上，這種方法將會使圖像中

17、目標(biāo)與背景分布的信息量達到最大。信息控制論中，香農(nóng)熵的具體定義： (2-4)其中，p ( x )是連續(xù)性變量x的概率密度函數(shù)。而在數(shù)字圖像中，隨機變量x通常對應(yīng)著圖像中的灰度或區(qū)域灰度等特征。當(dāng)將香農(nóng)熵的概念應(yīng)用于圖像分割時，通過計算灰度直方圖的熵總值，從而得到分割圖像的最佳閾值。在數(shù)字圖像中，對于灰度范圍在0，L-1的圖像，其熵為 (2-5)其中，pi 為灰度級i出現(xiàn)的概率。假定圖像中A與B分別代表目標(biāo)和背景，其分割這兩類的閾值為t。區(qū)間0，t 和 t + 1， L1的像素概率分布分別是： 其中，上式兩個分布對應(yīng)的熵HA(t )和HB(t )分別為： (2-6) (2-7)在此，我們以H (

18、t )作為為HA(t )和HB(t )之圖像熵之和，即： (2-8)上式中，分割目標(biāo)與背景的最佳閾值就是滿足熵H (t )取得最大值的t。在許多復(fù)雜圖像分割中，二維熵分割方法也是常用的一種圖像分割方法，其基本思想是：首先以像素的每一個像素與其鄰域的四個像素組合成一個區(qū)域，該像素點的灰度值i和其鄰域的灰度均值 j 組合成一個二維向量(i , j )，計算(i , j )的發(fā)生概率pij 。假定數(shù)字圖像的灰度級數(shù)為L，那么pij (i , j= 0,1,., L1)就構(gòu)成了數(shù)字圖像關(guān)于點灰度區(qū)域灰度均值的相應(yīng)的二維直方圖4。在一幅給定的圖像中，目標(biāo)和背景兩個區(qū)域中的像素點占有絕大多數(shù)，同時，這兩個

19、區(qū)域中的像素點的灰度級比較均勻，并且像素點的灰度值與其鄰域灰度均值的差別不大。通常，數(shù)字圖像相應(yīng)的二維直方圖pij會集中在i ,j平面的對角線的附近，以下我們描述了一個在XOY平面上的二維直方圖： 圖2-1 XOY平面上的二維直方圖假定分割圖像的閾值為( s , t )，則A區(qū)、B區(qū)概率分別為： (2-9) (2-10)則A區(qū)和B區(qū)的二維熵分別為： (2-11) (2-12)在二維直方圖的基礎(chǔ)上，分別計算不同的( s , t )，分割圖像的最佳閾值是H ( s , t)達到最大的( s , t )。該方法實現(xiàn)的函數(shù)和一維最大熵算法是相似的，其區(qū)別在于圖像二值化時，圖像的像素點在考慮灰度值的時候

20、，還須考慮該像素點鄰域的灰度均值2。圖像的單閾值分割往往只適用于灰度直方圖是較為理想的雙峰模型圖像。然而，實際中的某些圖像中并不具有簡單的雙峰模型，尤其是對于較為復(fù)雜的圖像。采用多閾值的分割方法往往可以獲得較為理想的效果。多閾值圖像分割是一種對單閾值圖像分割的推廣。將熵的概念應(yīng)用于多閾值圖像分割中，圖像的熵描述如下： (2-13)其中，k是閾值的個數(shù)。這樣，最佳閾值向量可以描述為： (2-14)多閾值圖像分割問題可以通過上述的基于信息熵的方法來求解。然而，實際中的問題在于計算量往往巨大，采用窮舉法來得到最佳閾值將會是一件非常耗時的工作，不能較好的應(yīng)用于實際當(dāng)中，尤其是對于一些需實時處理的圖像問

21、題，因此，通過其它方式尋求一種高效的方來求解此問題顯得急為必要。2.3 圖像分割的最佳閾值選擇策略將信息控制論中的熵概念應(yīng)用于圖像閾值分割中，其閾值確定的最佳依據(jù)是:如果圖像中目標(biāo)與背景分布的信息達到最大時,我們可以得到最佳的閾值。其步驟如下：對于單閾值情況，假定一幅灰度范圍為0,1,l1的圖像,圖像在隨機給定閾值t的前提下，劃分成背景(c1 )與目標(biāo)(c2 )兩個區(qū)域。其中 (2-15)其中,pi為灰度級i出現(xiàn)的概率，第i個灰度所占有的像素數(shù)是ni，Nimage是圖像中總的像素個數(shù)。在灰度直方圖的基礎(chǔ)上，圖像的熵定義為：，并且背景和目標(biāo)的熵分別定義為 (2-16)如果閾值t* 的能夠使圖像的

22、總熵取最大值，則t* 即為最佳閾值，即： (2-17)將上式擴展到圖像的多閾值分割,假定t1、t2、，tk 是分割的閾值,(t1t2，tk )，則圖像的總的熵值為： (2-18)其中，在此，如果總熵取得最大值就是最佳閾值： (2-19)在雙閾值情況下,假定t1 t2，則目標(biāo)和背景的總熵為： (2-20)最佳閾值， 為將會使熵取得最大值： (2-21)2.4 圖像分割的粒子群聚類算法步驟粒子具有較好的求解優(yōu)化問題的能力,對于某一具體的優(yōu)化問題而言,通過種群的最優(yōu)位置確定對應(yīng)問題的最優(yōu)解.由此,我們將圖像分割的問題看作是粒子群體尋找最優(yōu)解的一種優(yōu)化問題,通過粒子間的互相學(xué)習(xí),不斷交流,直至尋求到最

23、優(yōu)解位置,從而確定圖像分割中的最佳閾值。1）個體粒子及種群的數(shù)據(jù)結(jié)構(gòu)設(shè)計:在基于粒子群聚類算法的圖像分割中,個體粒子和粒子群體的數(shù)據(jù)結(jié)構(gòu)分別設(shè)計如下：Typedef struct Particle /個體粒子的結(jié)構(gòu).Int xd; /粒子在搜索空間中的位置. Int vd; /粒子當(dāng)前的飛行速度. Int pbestd; /粒子所經(jīng)歷的最好位置. Int pbfit; /評價粒子當(dāng)前位置xd所對應(yīng)的適應(yīng)度值.；Typedef struct Particle SwarmInt pgbestd; /粒子群體目前所找到的最優(yōu)解的位置. Int pgfit /最優(yōu)解對應(yīng)的適應(yīng)度值. Int x_num； /用于標(biāo)記當(dāng)前對應(yīng)于pgbestd 的粒子索引號.；2）算法步聚由于圖像的灰度級數(shù)為 0255,粒子的初始位置及速度,及每次迭代中粒子的位置與速度均限定在0,255。(1) 初始化參數(shù)：設(shè)定粒子數(shù)np ,隨機設(shè)定粒子的初始階段速度和位置(1k np )，且每個粒子的pbest均設(shè)定為初始位置。將適應(yīng)度最好的pbest中設(shè)為pgbest ，nmax為最大迭代次數(shù)，迭達計數(shù)器