魯 俊，鄔春學，高 華

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

自適應(yīng)分級粒子群算法的閾值圖像分割研究

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

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

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

圖像分割；聚類分析；自適應(yīng)分級；粒子群算法；閾值

0 引言

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

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

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

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

1 Otsu算法

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

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

(1)

灰度值為t的像素點出現(xiàn)的Pi為：

(2)

顯然，

(3)

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

背景部分類出現(xiàn)概率m0和灰度均值x0分別為：

(4)

目標部分類出現(xiàn)概率m1和灰度均值x1分別為：

(5)

圖像總的灰度均值xS為：

(6)

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

(7)

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

(8)

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

2 AGPSO算法基本原理

2.1 基本PSO算法

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

(9)

(10)

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

2.2 改進粒子群算法AGPSO

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

2.2.1 慣性權(quán)重的自適應(yīng)調(diào)整

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

(11)

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

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

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

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

(12)

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

(13)

(14)

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

2.2.3 采用交叉的速度更新

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

(15)

(16)

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

2.2.4 AGPSO閾值圖像分割

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

3 實驗分析

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

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

表1 Lena圖像

表2 飛機圖像

4 結(jié)語

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

[1] 盧振泰，陳武凡，呂慶文.基于互信息量的寄生蟲卵圖像自動優(yōu)化分割[J].計算機應(yīng)用研究,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] 黃港，李俊，潘金貴.基于粒子群優(yōu)化方法的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] 劉申曉，王學春，常朝穩(wěn).基于改進粒子群優(yōu)化算法的Otsu圖像分割方法[J].計算機科學，2015(6)：125-129.

[7] 韋鋼.電力系統(tǒng)分析基礎(chǔ)[M].第1版.北京：中國電力出版社，2006.

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

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

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

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

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

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

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

(責任編輯：杜能鋼)

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

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

10.11907/rjdk.162590

TP317.4

A

1672-7800(2017)003-0170-03