魯 俊，鄔春學(xué)，高 華

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

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

魯 俊1，鄔春學(xué)1，高 華2

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

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

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

0 引言

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

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

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

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

1 Otsu算法

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

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

(1)

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

(2)

顯然，

(3)

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

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

(4)

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

(5)

圖像總的灰度均值xS為：

(6)

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

(7)

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

(8)

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

2 AGPSO算法基本原理

2.1 基本PSO算法

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

(9)

(10)

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

2.2 改進(jìn)粒子群算法AGPSO

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

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

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

(11)

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

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

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

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

(12)

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

(13)

(14)

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

2.2.3 采用交叉的速度更新

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

(15)

(16)

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

2.2.4 AGPSO閾值圖像分割

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

3 實(shí)驗(yàn)分析

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

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

表1 Lena圖像

表2 飛機(jī)圖像

4 結(jié)語(yǔ)

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

[1] 盧振泰，陳武凡，呂慶文.基于互信息量的寄生蟲(chóng)卵圖像自動(dòng)優(yōu)化分割[J].計(jì)算機(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].中國(guó)圖象圖形學(xué)報(bào)，2011，16(3)：377-381.

[4] 張新娟.基于改進(jìn)粒子群算法的閾值圖像分割[J].中國(guó)圖象圖形學(xué)報(bào),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] 劉申曉，王學(xué)春，常朝穩(wěn).基于改進(jìn)粒子群優(yōu)化算法的Otsu圖像分割方法[J].計(jì)算機(jī)科學(xué)，2015(6)：125-129.

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

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

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

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

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

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

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

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

(責(zé)任編輯：杜能鋼)

國(guó)家自然科學(xué)基金項(xiàng)目(61202376) ; 上海市教育基金會(huì)晨光計(jì)劃基金項(xiàng)目(10CG49)

魯俊(1990-)，男，安徽蕪湖人，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院碩士研究生，研究方向?yàn)閳D像分割、人工智能；鄔春學(xué)(1964-)，男，上海人，博士，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院教授、碩士生導(dǎo)師，研究方向?yàn)榍度胧较到y(tǒng)及應(yīng)用、計(jì)算機(jī)控制技術(shù)及工程、軟件工程及軟件開(kāi)發(fā)技術(shù)；高華(1989-)，女，上海人，碩士，上海理工大學(xué)教務(wù)處助理工程師,研究方向?yàn)閳D像分割、機(jī)器學(xué)習(xí)。

10.11907/rjdk.162590

TP317.4

A

1672-7800(2017)003-0170-03