自適應分級粒子群算法的閾值圖像分割研究

魯 俊，鄔春學，高 華

(1.上海理工大學 光電信息與計算機工程學院；2.上海理工大學 教務處,上海 200093)

自適應分級粒子群算法的閾值圖像分割研究

魯 俊1，鄔春學1，高 華2

(1.上海理工大學 光電信息與計算機工程學院；2.上海理工大學 教務處,上海 200093)

提出了一種改進型的粒子群算法,并與閾值法相結合應用于圖像分割。該改進粒子群算法通過調節慣性權重而獲得合理有效的收斂速度；采用分級思想對粒子進行分類并對普通粒子速度更新公式進行修改，從而有效避免了優化過程中粒子的早熟現象；結合遺傳算法中的交叉思想增加種群的多樣性，增強全局搜索能力從而避免算法陷入局部最優解。將其應用于的閾值圖像分割，試驗結果表明：相對于標準PSO算法，該自適應分級粒子群算法具有較強的全局尋優能力，且收斂速度快、魯棒性好，能很好地應用于閾值圖像分割。

圖像分割；聚類分析；自適應分級；粒子群算法；閾值

0 引言

圖像分割是自動圖像模式識別和場景分析的重要預處理環節。隨著模式識別、計算機視覺、虛擬現實與仿真、衛星遙感圖像技術的發展，越來越多的學者開始研究圖像分割技術，提出了很多具有代表性的圖像分割方法。圖像分割問題復雜，每種方法都有一定的局限性，還沒有能適用于所有圖像的通用算法[1-3]。閾值法是一種簡單高效的圖像分割方法，它通過若干個閾值將圖像的灰度級劃分為幾部分，認為屬于某一區間的像素就是同一物體。閾值法簡單高效，但是很難確定最優閾值，分割效果不穩定。

目前已有諸多閾值選取方法，如P-tile法、最大類間方差法(也稱Otsu法)、最小誤差法等。其中，日本學者Otsu在1979年提出的Otsu方法，通過灰度值來分割圖像，將圖像分為目標和背景，通過求它們之間的最大類間方差得到最佳閾值，與目標和背景分布模型無關，適用于各類圖像，有很好的分割效果[4]。但是Otsu對每一個灰度值都要計算方差，運算時間長，很難適應實時圖像分割。

粒子群算法(Particle Swarm Optimization,簡稱PSO)是一種基于群體智能的啟發式優化算法，具有廣泛的通用性和適應性。它根據速度搜索，充分發揮其記憶功能，利用個體及群體最優信息并行搜索問題最優解，廣泛應用于函數優化問題的求解。但由于PSO算法易陷入局部最優解且收斂速度慢[5-6]，加之圖像分割問題本身的復雜性，使得PSO算法在閾值圖像分割結果上不理想。

本文在對標準 PSO算法進行深入學習和研究的基礎上，提出一種改進粒子群算法( AGPSO)，它運用線性自適應慣性權重，在速度更新的過程中采用分級思想，針對普通粒子提出一種修正速度公式，同時采用交叉思想來更新速度，并將該算法與閾值法相結合應用于圖像分割問題。通過與Otsu算法及標準PSO算法進行比較，表明AGPSO算法具有較高的可行性和有效性。

1 Otsu算法

Otsu是在最小二乘法的原理上衍生的一種基于分類類別函數，通過選取圖像灰度閾值t將圖像分割為幾部分。計算圖像各個灰度值的概率Pi，并在此基礎上計算圖像最大類間方差值，通過最大類間方差值來確定圖像分割的灰度最佳閾值t[7]，算法流程如下：

設待處理圖像的灰度集：G={0,1,2,…,L-1}，灰度t∈(G)的個數ni，總的像素N為：

(1)

灰度值為t的像素點出現的Pi為：

(2)

顯然，

(3)

通過選取閾值灰度值ts將圖像劃分為兩部分，灰度級處于t∈[0,ts-1]的稱為背景部分類(C0)；灰度級處于t∈[ts,L-1]的稱為目標部分類(C1)，表示圖像中的目標物。

背景部分類出現概率m0和灰度均值x0分別為：

(4)

目標部分類出現概率m1和灰度均值x1分別為：

(5)

圖像總的灰度均值xS為：

(6)

則背景部分類C0和目標部分類C1的類間方差σ2可表示為：

(7)

由式(4)至式(7)可進一步推出：

(8)

由式(1)～式(8)可以得出類間方差σ2是關于閾值變量t的函數，Otsu算法就是以σ2為判別函數，選取t使σ2最大得到圖像的最佳閾值。閾值的選擇是基于灰度的統計，與具體圖像沒有關系，有較高的通用性，但是Otsu對每一個灰度都要計算其σ2，運算量大，很難進行實時圖像分割。

2 AGPSO算法基本原理

2.1 基本PSO算法

粒子群算法將每個個體Xi=(xi1，xi2，…，xiD)認為是在D維空間中的一個無體積和重量的收索粒子，并以特定的速度Vi=(vi1，vi2，…，viD)飛行在搜索空間，將Xi帶入目標函數即可求出其適應度，粒子的飛行速度由個體的最佳坐標Pi=(pi1，pi2，…，piD)和群體的最佳坐標Pg=(pg1，pg2，…，pgD)進行動態調整。粒子速度位置更新公式如下：

(9)

(10)

其中，g為迭代次數，i=1，2，……G，為種群數目；d=1，2，…，D為搜索空間維數；w為慣性權重，代表父代的粒子速度對子代的速度作用；c1、c2為學習因子，用來確定粒子最優位置和全局最優位置對粒子速度更新的影響。

2.2 改進粒子群算法AGPSO

基本PSO算法不足之處是容易陷入局部最優。每個粒子參照Pid和Pgd來優化速度和位置，一旦Pgd陷入局部最優，則整個種群會陷入局部極值。本文通過3個方面的改進來保證種群的多樣性以及收斂速度：①慣性權重的線性調整；②分級思想的引入并對普通粒子采用改進的速度更新公式；③仿照遺傳算法對粒子速度進行交叉操作。

2.2.1 慣性權重的自適應調整

慣性權重w代表了粒子父代的速度對子代速度的作用。通過設置其取值大小可改變PSO 算法的全局與局部尋優能力。對于全局優化問題，通常的做法是在算法前期采用較大的慣性權重以提高粒子的探索(exploration)能力。在算法的后期，為加快收斂速度而使粒子擁有較高的開發(exploitation)能力，采用較小的慣性權重[8-10]。本文采用自適應的線性遞減權重(linearly decreasing weight)策略，隨著迭代次數的增多，線性減少w值的大小，公式如下：

(11)

式(11)中，w0為慣性權重的初始值，wG為進化到最大代數時的慣性權重，G為迭代次數的最大值，g為當前代數。參數設定：w0=0.9，wG=0.4。

2.2.2 基于分級思想的普通粒子速度更新修正公式

采用分級思想優化粒子群的信息交互模型，將原全局尋優算法變為局部信息交換算法。分級原理是將適應值相近的個體劃分在同一級，各級之間相似性依據適應值之間的歐氏距離來確定[11-12]。先將適應值從大到小排序，以最好適應值和最差適應度之差將粒子動態分級，按照粒子的適應度值將粒子評定為優秀、一般、較差3類，它們所占比例分別為40%、40%、20% 。

針對一般粒子提出修正的更新公式：

(12)

其中Pbd為優秀粒子的個體最優位置，一般粒子隨機選取優秀粒子作為進化方向，表現越好的粒子被選中的概率越高，從而確保了越優秀的粒子被選中的機會越大。具體計算方法如下：

(13)

(14)

i=1,2，…,bp為優秀粒子按照適應度大小排列而來的序列數,則p1+p2+…+pbp=1,對于優秀粒子的選中概率，可以以[0,1]區間內的隨機數r來表示，如果Pi

2.2.3 采用交叉的速度更新

通過學習生物進化思想，粒子群中的每個粒子都有一個雜交概率，這個雜交概率的大小是隨機的，與粒子個體無關。在沒代迭代中，依據雜交概率選取相應數目粒子。這些粒子隨機兩兩雜交，生成等數目的子代粒子，雜交過的個體不能再次雜交，保證每個個體都有變異機會，同時只保留雜交后的子代，以保持種群數目的穩定[13-14]。經過雜交操作后，由親代個體隨機生成兩個新的速度，因此子代速度只有方向上的改變，數量上沒有改變。

(15)

(16)

式中r的取值為均勻分布在[0，1]之間的隨機數，雜交變異的經驗值此處選0.2。

2.2.4 AGPSO閾值圖像分割

Otsu算法本質就是找到一個最佳的灰度閾值t，使得式(8)達到最大值。但是傳統的Otsu算法有計算量大、時間復雜度高的不足。本文將AGPSO算法與Otsu結合，以類間方差σ2作為AGPSO的適應度函數；使用灰度閾值t作為粒子位置，根據公式(10)更新粒子位置；采用分級和生物進化雜交變異思想，根據公式(9)來更新優秀粒子和普通粒子速度，同時對普通粒子采用公式(12)來更新速度。然后選取粒子按照公式(15)、(16)進行交叉變異操作；使用公式(11)自動調整慣性權重值，在一維灰度空間中迭代搜索使σ2最大的灰度值，算法步驟如下：①令t=Rand(0,255)，初始化每個粒子的速度和位置，隨機生成一個規模為POP的種群，隨機生成粒子初始速度Vi在[-Vdmax,Vdmax]范圍內；②輸入圖像，根據式(3)計算圖像中各灰度出現的概率。設圖像總像素數為N，根據式(1)至式(6)計算其大小；③根據式(8)計算每個粒子的適應度；④將適應度與它經過的最好位置Pid比較，若優于Pid，則將其替換最好位置Pid；⑤計算每個粒子的適應度并與群體所經過的最好位置Pgd比較，若優于Pgd，則將其替換全局最好位置Pgd； ⑥按照粒子適應度大小排序，使用分級思想對粒子進行分類；⑦根據公式(9)來更新優秀粒子和一般粒子的速度，對一般粒子采用公式(12)來更新速度，完畢后選取粒子按照公式(15)、(16)進行交叉變異操作；⑧按照公式(10)更新粒子位置；⑨判斷是否滿足終止條件，若滿足則終止；否則，轉向步驟③繼續執行；⑩根據得到的閾值Pgd對圖像進行分割。

3 實驗分析

為了檢驗AGPSO算法的有效性，在相同的硬件和軟件條件下，選取圖像分別對經典Otsu算法、基于標準PSO+Otsu分割算法和本文算法進行測試。參數設置為：P0P(種群)大小為30，G(最大迭代次數)為100次，慣性權重采用式(10)進行調整，加速因子c1=c2=2。Vdmax=256，實驗結果如圖1所示。

表1和表2分別列舉了幾種算法在不同圖像中20次實驗結果的平均數據。從表1和表2的結果容易得出，相較于傳統Otsu算法，本文算法有迭代次數少、效率高的優點；相較于標準PSO+Otsu算法，本文算法得出的閾值t更好，且運算效率更高。

表1 Lena圖像

表2 飛機圖像

4 結語

本文針對傳統粒子群算法收斂速度慢、易陷入局部最優的問題，提出了自適應分級的AGPSO算法，將其與閾值法結合應用于圖像分割。AGPSO是一種高效且全局搜索能力強的優化算法，通過AGPSO算法實驗并與其它算法對比，表明AGPSO算法在一定程度上有效避免了局部最優現象，收斂速度較快，精度較高，最終結果符合圖像分割預期。將其應用于閾值圖像分割，可提高閾值圖像分割的準確率及分割速度，可很好地應用于實時圖像分割。

[1] 盧振泰，陳武凡，呂慶文.基于互信息量的寄生蟲卵圖像自動優化分割[J].計算機應用研究,2007,24(11):301-302.

[2] GARC A-P REZ L,GARC A-ALEGRE M C,MARCHANT J,et al.Dy-namic threshold selection for image segmentation of natural struc -tures based upon a performance criterion[C].Proc of 3ECPA-3 European Conference on Precision Agriculture,2001.

[3] 黃港，李俊，潘金貴.基于粒子群優化方法的2維Otsu快速圖像分割算法[J].中國圖象圖形學報，2011，16(3)：377-381.

[4] 張新娟.基于改進粒子群算法的閾值圖像分割[J].中國圖象圖形學報,2013(6)：36-40.

[5] CHUN-AN LIU.New dynamic constrained optimzation PSO algorithm[C].Jinan(China),Proceedings 4th International Conference on Natural Computation(ICNC2008),2008.

[6] 劉申曉，王學春，常朝穩.基于改進粒子群優化算法的Otsu圖像分割方法[J].計算機科學，2015(6)：125-129.

[7] 韋鋼.電力系統分析基礎[M].第1版.北京：中國電力出版社，2006.

[8] 林玉娥.粒子群優化算法的改進及其在管道保溫優化設計中的應用[D].大慶：大慶石油學院，2006.

[9] 栗然，唐凡，劉英培，等.基于自適應變異粒子群算法的雙饋風電機組等值建模[J].電力系統自動化，2012，36(4)：22-27.

[10] 張庭場，耿光飛.基于改進粒子群算法的中壓配電網無功優化[J].電網技術，2012，36(2)：158-162.

[11] 劉世成，張建華，劉宗岐.并行自適應粒子群算法在電力系統無功優化中的應用[J].電網技術，2012，36(1)：108-112.

[12] 張磊.基于分級的粒子群優化算法研究[D].廣州：廣東工業大學，2011.

[13] 周雙喜，楊彬劉.實現無功優化的新算法——遺傳算法[J].電力系統自動化，1995，11(19)：19-21.

[14] 向鐵元，周青山，李富鵬，等.小生境遺傳算法在無功優化中的應用研究[J].中國電機工程學報，2005，25(17)：48-51.

(責任編輯：杜能鋼)

國家自然科學基金項目(61202376) ; 上海市教育基金會晨光計劃基金項目(10CG49)

魯俊(1990-)，男，安徽蕪湖人，上海理工大學光電信息與計算機工程學院碩士研究生，研究方向為圖像分割、人工智能；鄔春學(1964-)，男，上海人，博士，上海理工大學光電信息與計算機工程學院教授、碩士生導師，研究方向為嵌入式系統及應用、計算機控制技術及工程、軟件工程及軟件開發技術；高華(1989-)，女，上海人，碩士，上海理工大學教務處助理工程師,研究方向為圖像分割、機器學習。

10.11907/rjdk.162590

TP317.4

A

1672-7800(2017)003-0170-03