夏星宇， 高 浩， 王創(chuàng)業(yè)

(1.南京郵電大學 自動化學院，江蘇 南京 210046; 2.安徽省蚌埠市供電局，安徽 蚌埠 233000)

0 引言

圖像分割的目的是將一幅圖像劃分成有意義的區(qū)域或部分，其中每部分區(qū)域具有相似的特征.近幾年來，學者們提出了很多較為有效的圖像分割技術(shù)[1].它們大致可以分為兩類：一類是利用圖像的灰度直方圖，通過其特征來決定分割的最佳閾值[2].另一類是構(gòu)造一個適應(yīng)度函數(shù)，通過優(yōu)化適應(yīng)值函數(shù)來決定最優(yōu)的閾值，如基于熵的閾值分割技術(shù),貝葉斯誤差最小化等.這些技術(shù)在醫(yī)學圖像、人臉識別、計算機視覺等領(lǐng)域已經(jīng)取得了不錯的效果.然而，其中的一些方法計算非常耗時，如Kapur和Otsu算法[3-4]的運算時間相當長，且隨著閾值數(shù)目的增加運算時間呈指數(shù)增長，其窮舉的搜索策略限制了它在處理實際多閾值問題中的應(yīng)用.

近年來，為縮短運算時間，研究人員已經(jīng)成功地將很多優(yōu)化算法引入到閾值圖像分割中來.作為基于種群的優(yōu)化策略，進化算法受自然界生物的啟發(fā)，主要采用3個主要操作(選擇、變異和交叉)來產(chǎn)生后代.由于有著運算速度快和全局搜索能力較強等特點，近幾年，進化計算已經(jīng)廣泛地應(yīng)用到了圖像分割領(lǐng)域.Tao等[5]采用蟻群算法來優(yōu)化基于熵的目標分割適應(yīng)值函數(shù)，尋找最優(yōu)的閾值.Yin等[6]提出一種改進的遺傳算法來縮短多閾值分割的時間.Gao等[7]將粒子群優(yōu)化算法引入到圖像閾值分割領(lǐng)域，實驗證明它可以取得和窮舉搜索相近的實驗結(jié)果.Yin[8]將基于協(xié)作策略的量子粒子群算法QPSO應(yīng)用到圖像分割中來，實驗證明當處理同一分割問題時，該算法可以取得比其他同比優(yōu)化算法更好的效果.

作為較為流行的進化算法之一，粒子群算法兼有進化計算和群智能的特點.與其他進化算法相類似，該算法模擬鳥群集體飛行覓食的行為，通過鳥之間的集體協(xié)作與競爭使群體達到目的.算法已經(jīng)成功地應(yīng)用到工業(yè)生產(chǎn)、模式識別、醫(yī)學處理等多個領(lǐng)域[9-10].但由于粒子群算法具有早熟收斂的缺點，因此筆者提出一種基于均衡策略的粒子群算法(particle swarm optimization with an equilibrium strategy,EPSO)，在提出一個有價值的引導(dǎo)點的同時，合理地賦予粒子在全局和局部搜索的可能性，較好地均衡了算法的全局和局部搜索能力.同時把改進后的粒子群算法應(yīng)用到基于Kapur最大熵圖像分割中，有效地解決圖像閾值分割耗時長這一問題.

1 粒子群進化算法

作為一種基于種群的進化算法，粒子群進化算法[11]操作簡便，近年來，受到了廣泛的關(guān)注.在粒子群中，固定規(guī)模的種群代表了一系列的可行解.每個備選解被稱為一個“粒子”，多個粒子共存，合作尋優(yōu)，近似鳥群尋找食物.算法先生成初始種群，即在可行解空間中隨機初始化一群粒子，每個粒子都為優(yōu)化問題的一個可行解，并由目標函數(shù)為之確定一個適應(yīng)值.在每一次迭代過程中，粒子將跟蹤兩個極值，一個為粒子本身迄今找到的最優(yōu)解Pp，另一為全種群迄今找到的最優(yōu)解Pg.基本迭代公式為：

vid(t+1)=vid(t)+c1r1·(ppid-xid(t))+

c2r2·(pgd-xid(t))；

(1)

xid(t+1)=xid(t)+vid(t+1)，

(2)

式中：i=1,2,…,S；d=1,2,…,n；r1和r2是服從U(0,1)分布的隨機數(shù)；學習因子c1和c2為非負常數(shù)，c1=c2=2；vid=[-vmax,vmax]，vmax是由用戶設(shè)定的速度上限;ppid以及pgd分別代表個體最優(yōu)和群體最優(yōu)在第d維上的解.

2 基于均衡策略的粒子群算法

以往的研究成果表明，傳統(tǒng)的粒子群算法具有早熟收斂的缺陷，為在保持粒子群算法收斂速度快的基礎(chǔ)上提升算法的全局搜索能力，筆者提出了一種新方法.首先，為了在算法運行過程中一直能夠為粒子群提供一個較大的搜索能力，使得粒子群能夠保持跳出當前局部搜索區(qū)域的概率，筆者提出了一個均衡因子：

g=abs(r3(0,a1)/r4),

(3)

式中：r3為符合高斯分布的隨機序列;r4是服從U(0，1)分布的隨機數(shù)；a1為該高斯分布的標準差.實驗結(jié)果表明,當a1為0.35時,改進后的粒子群算法能夠取得較優(yōu)的實驗結(jié)果，并保證算法在迭代初期獲得較強的全局搜索能力和在后期具有較優(yōu)的局部搜索能力.

粒子群迭代公式：

xid(t+1)=Qd±α·g·(Pmd-xid(t)),

(4)

其中,Qd=r1·ppid+(1-r1)·pgd+r3·

(Pgd-round(Pgd)).

(5)

與以往算法不同的是式(5)不僅包含了文獻[12]證明的粒子群收斂進化方向Qd=r1·ppid+(1-r1)·pgd，同時還給出了一個擾動因子r3·(pgd-round(pgd)).r1是服從[0,1]的均勻分布的隨機數(shù)，r3是服從標準正態(tài)分布的隨機數(shù).這樣不僅給粒子進化提供了一個有效的方向，同時能夠保證個體在運行過程中特別是在ppid=pgd的情況下，通過借鑒群體歷史最優(yōu)解Pg的數(shù)值產(chǎn)生一個相對較小的值，給予個體一個較小的擾動，保證個體能夠在局部區(qū)域進行有效搜索.

圖1 g∈[-2,2]之間的分布圖Fig.1 The distribution of g∈[-2,2]

圖2 g?[-2,2]的分布圖Fig.2 The distribution of g?[-2,2]

通過對圖1和PSO算法的c1以及c2比較，相對于c1以及c2的取值范圍[-2,2]之間的均勻采樣，很容易發(fā)現(xiàn)EPSO算法能夠在[-1,1]之間產(chǎn)生更多的解(大致為40 000次)，從而能夠在Qd確定的局部區(qū)域產(chǎn)生更為集中的解，這樣就可以使得種群獲得更多的局部搜索機會；而圖2的結(jié)果表明相對于標準的PSO算法的c1以及c2的取值范圍，EPSO能夠產(chǎn)生數(shù)值更大的備選解，最大值可達到3.2×104，這就意味著種群在尋優(yōu)過程中能夠獲得更多跳出局部最優(yōu)解的能力.

EPSO算法步驟如下.

(1)依照初始化過程，對粒子群的隨機位置和速度進行初始設(shè)定;

(2)計算每個粒子的適應(yīng)值;

(3)對于每個粒子將其適應(yīng)值與所經(jīng)歷過的最好位置Pp的適應(yīng)值進行比較，若較好，則將其作為當前的最好位置;

(4)對于每個粒子將其適應(yīng)值與全局所經(jīng)歷的最好位置的適應(yīng)值進行比較，若最好，則將其作為當前的全局最好位置;

(5)根據(jù)方程(4)和方程(5)對粒子的速度和位置進行進化;

(6)如未達到結(jié)束條件通常為足夠好的適應(yīng)值或達到一個預(yù)設(shè)最大代數(shù)，則返回步驟(2).

3 對比試驗

3.1 標準測試函數(shù)試驗設(shè)計及結(jié)果

為了分析筆者提出的EPSO的總體性能，筆者設(shè)計了多種測試實驗對PSO[12]、QPSO[13]、HRPSO[14]、HWPSO[15]、CCPSO[16]以及 EPSO進行了對比分析. 同時使用8個標準測試函數(shù)[11]問題來進行多方面考察和比對.筆者測試所有算法使用的個體總?cè)簜€數(shù)都設(shè)為20(ABC算法根據(jù)算法流程個體總數(shù)設(shè)置為10).測試函數(shù)中f1-f3是單模函數(shù)，f4-f6是具有多個局部最小點的多模函數(shù)，函數(shù)的評估次數(shù)設(shè)置為2 000×測試函數(shù)維數(shù).f7-f8是低維函數(shù)，函數(shù)的評估次數(shù)設(shè)置為10 000.所有測試函數(shù)的理論最優(yōu)解均為0.最好的對比結(jié)果在表2和表4中加黑顯示.

對于單模函數(shù)來說，由于EPSO使用了Qd點指引整個群體進行搜索，在整個粒子進化過程中一直給予粒子進化提供了一個有價值的方向，特別是當出現(xiàn)Ppd=Pgd的情況時，擾動因子依然能夠提供給粒子在局部區(qū)域更多的搜索機會.相對于同樣使用文獻[10]提出收斂點的QPSO來說，由于EPSO算法使用了擾動因子，能夠提供給粒子群體更多的局部搜索機會.另外，根據(jù)圖2的實驗結(jié)果，相對于傳統(tǒng)的學習因子，EPSO算法的g因子能夠在[-2, 2]局部范圍內(nèi)提供給粒子以更多的在小范圍內(nèi)搜索的機會，因此粒子可以在Q點定義的局部范圍內(nèi)進行精確搜索，從而在單模函數(shù)上獲得較快和較為精確的解.對于復(fù)雜的多模函數(shù)，同其他比較算法相比，由于EPSO算法使用了均衡因子，使得個體能夠獲得更大的解，具有較強的跳出局部最小點的能力，從而提高了算法特別是在迭代后期搜索整個解空間的可能性.此外由于算法的局部搜索能力也較為優(yōu)異，在全局和局部搜索能力上獲得了較好的平衡，因此在多模函數(shù)上獲得了更為精確和滿意的結(jié)果.表1為標準測試函數(shù)，表2為各種比較算法在測試函數(shù)的比較結(jié)果.根據(jù)表2的研究結(jié)果表明，EPSO在低維函數(shù)上依然取得較優(yōu)的結(jié)果.因此，可以得出結(jié)論，EPSO不僅在高維函數(shù)上，同時在低維函數(shù)上表現(xiàn)出了較優(yōu)的搜索能力.

3.2 圖像函數(shù)測試設(shè)計及結(jié)果分析

由Kapur提出的基于熵準則的圖像分割方法由于可以針對基于直方圖的圖像提供良好的圖像分割而得到了大量應(yīng)用.傳統(tǒng)的Kapur方法是基于雙閾值的圖像分割方法，近年來它已經(jīng)被成功地應(yīng)用到多閾值分割領(lǐng)域.具體描述如下.

f([t1,t2,…,tM-1])=H0+H1+…+HM-1；

(6)

(7)

(8)

Pi=h(i)/N,

(9)

其中,N代表圖像包含的像素個數(shù);L=255表示最大的灰度級;h(i)表示的是在第i灰度級上圖像像素的個數(shù).在0～L間改變對應(yīng)的各個閾值，求滿足式(6)為最大值的{t1,t2,…,tM-1}，此時的{t1,t2,…,tM-1}便是最佳閾值.顯然要得到arg max{f(t1,t2,…,tM-1)}，必須對區(qū)間所有的灰度值進行多級熵值計算，最后比較得到最大的熵值，其計算量較大，而且隨著分割閾值數(shù)目的增加其時間復(fù)雜度為O(255M-1)，這將嚴重阻礙了Kapur方法的應(yīng)用以及推廣.為了減少標準Kapur算法的運算量，筆者利用EPSO快速收斂特性解決標準Kapur算法存在的這一難題.此外，為了驗證EPSO算法的具體性能，筆者設(shè)計了5類比較試驗：①ACO算法[17]；②GA-L算法[18]；③ABC算法[5]；④PSO算法[11]；⑤CQPSO[9]算法；⑥QPSO[13]算法；⑦EPSO算法.這些算法的參數(shù)設(shè)置都嚴格按照相對應(yīng)的文獻進行處理.所有算法的比較在Core 2 Duo 3.2GHZ電腦使用MATLAB語言完成.分割的閾值分別設(shè)為2、4、6，對應(yīng)的函數(shù)評價次數(shù)為2 000.測試的圖像分別采用比較算法中最常用的圖像以及伯克利大學提供的標準測試圖像，圖3為示例圖像.此外，由于標準Kapur算法在閾值數(shù)超過4以后的運算時間過長，因此只列出閾值數(shù)為2和4的結(jié)果.

表1 標準測試函數(shù)

表2 各種比較算法在測試函數(shù)的比較結(jié)果(平均值(方差))Tab.2 The comparison results between different algorithm on benchmark functions (Mean values (Standard deviation))

圖3 測試圖像Fig.3 Tested images

從表3和4的結(jié)果可以看出，筆者提出的EPSO算法獲得了與標準Kapur算法最為接近的適應(yīng)度值，同時根據(jù)表3得到的結(jié)果，基于EPSO算法的Kapur分割方法所耗費的CPU時間隨著閾值的增加并不特別明顯，遠遠降低了標準Kapur算法的時間復(fù)雜度，因此，相對于標準算法，筆者提出的算法有效地提高了算法的運行效率.此外，如表4所示，與ABC、 ACO、PSO、CQPSO、GA、QPSO 6個基于進化算法的圖像分割方法相比，EPSO在4幅圖片上均取得了最佳的適應(yīng)度值和方差，這主要是和各自算法的搜索策略有關(guān).由于ABC算法采用單維的搜索策略，使得算法在每一維上都能夠進行精細的搜索，保證了算法的可靠性.同時由于使用了貪婪搜索策略，能夠給群體進化提供一個較優(yōu)的方向，在全局和局部搜索能力上獲得了較好的平衡，因此獲得了較好的尋優(yōu)結(jié)果.蟻群算法由于使用了信息素的概念，個體在尋優(yōu)的過程中比遺傳算法獲得更多的借鑒群體最優(yōu)解的機會，因此在比較的圖像上獲得比遺傳算法更好的結(jié)果，但相對于其他群體算法，信息素的更新較為緩慢，因此在有限的迭代次數(shù)內(nèi)分割效果差于其他的基于群體算法的分割方法.而遺傳算法相對于其他比較算法來說，個體在尋優(yōu)過程中只和父代進行經(jīng)驗交換，因此收斂速度最慢，在規(guī)定的時間內(nèi)無法獲得優(yōu)異的成績，效果最差.PSO以及QPSO算法雖然相對于其他進化算法有著收斂速度快的優(yōu)點，但卻易于陷入局部最優(yōu)，因此雖然相對于GA和ACO算法來說獲得較好的實驗結(jié)果，但相對于ABC和改進的粒子群算法卻成績較差.CQPSO算法由于使用了協(xié)作策略，因此能夠在一定程度上克服維數(shù)的束縛，在高維上(除去筆者提出的算法)獲得了較好的試驗結(jié)果.筆者提出的算法由于使用了均衡因子，在算法迭代過程中(特別是迭代后期)能夠獲得更多的在全局范圍內(nèi)搜索的機會，相對于PSO及其改進算法提升了全局搜索能力，從而能夠保證最終獲得解的可靠性.同時，由于算法仍然使用了群體和個體歷史最優(yōu)解的概念，因此繼承了PSO算法收斂速度快的特點.此外，由于在搜索方向上引入了擾動因子，能夠在算法迭代過程中不斷地給予個體一個微動力，使得個體能夠在局部范圍內(nèi)獲得更多的搜索機會，因此具有搜索更為精確解的能力.圖4給出了各種比較算法在Berkely標準圖像分割測試庫上測試獲得的名次排名總和(越小越好)，EPSO算法相對于其他算法獲得了最好的名次，同樣驗證了算法的有效性.結(jié)合表3所示結(jié)果，PSO和EPSO算法在2維和4維上的分割耗費的時間為同一量級，而分割效果遠遠優(yōu)于PSO算法，進一步說明本方法改進的必要性.同時，對于標準方差這一考核指標，EPSO也取得了比其他5種算法更為優(yōu)異的穩(wěn)定性，這說明筆者所提出的優(yōu)化算法在分割過程中更加穩(wěn)定，魯棒性好.圖5為EPSO算法在示例圖像閾值為6時的分割結(jié)果.整體而言，EPSO在整個測試圖片4個閾值上都取得了最好的優(yōu)化成績和標準偏差，說明該算法可以取得更好的分割效果和更穩(wěn)定的分割性能.

表3 標準Kapur、PSO、EPSO在示例圖的比較結(jié)果

表4 基于進化算法的Kapur分割方法的比較結(jié)果

圖4 基于進化算法的Kapur分割方法在Berkeley標準測試庫測試的名次Fig.4 The ranking of EAs based Kapur algorithm on Berkeley image database

4 結(jié)論

筆者根據(jù)粒子群進化算法本身的特點，首先提出了一個新的均衡策略，使得算法可以在保證全局搜索能力的條件下加快收斂速度.然后在此基礎(chǔ)上采用了一個新的引導(dǎo)個體，使得個體能夠在局部范圍內(nèi)更為精確地搜索，從而得到更優(yōu)的優(yōu)化效果.改進算法在標準測試函數(shù)以及圖像閾值分割中取得了比其他算法更好的成績，從而證明了其有效性.以后的工作將繼續(xù)關(guān)注如何在保證分割時間較短的情況下更高地提高算法的優(yōu)化效果.

圖5 EPSO在閾值為6時的分割圖Fig.5 The segmented images with six thresholding by EPSO

[1] 王忠勇,賈萌,候中新,等.基于形態(tài)學特征的顆粒圖像分割和計數(shù)[J]. 鄭州大學學報(工學版), 2015, 36(2): 80-84.

[2] 劉松濤,殷福亮.基于圖割的圖像分割方法及其新進展[J]. 自動化學報, 2012, 38(6): 911-922.

[3] SAHOO P K, KAPUR J N, WONG A K C. A new method for gray-level picture thresholding using the entropy of the histogram[J]. Computer vision graphics image processing, 1985, 29(3): 273-285.

[4] OTSU N. A threshold selection method from gray-level histograms[J]. IEEE transactions on system, man and cybernetics, 1979, 9(1): 62-66.

[5] TAO W B, JIN H and LIU L M. Object segmentation using ant colony optimization algorithm and fuzzy entropy[J]. Pattern recognition letter，2007, 28 (7): 788-796.

[6] YIN P Y, CHEN L H. A fast iterative scheme for multilevel thresholding methods [J]. Signal process, 1997, 60 (3): 305-313.

[7] GAO W F, LIU S Y, HUANG L L. A novel artificial bee colony algorithm based on modified search equation and orthogonal learning [J]. IEEE transactions on cybernetics, 2013, 43(3), 1011-1024.

[8] YIN P Y. Multilevel minimum cross entropy threshold selection based on particle swarm optimization [J]. Applied mathematics and computation, 2007, 184 (2): 503-513.

[9] GAO H, XU W, SUN J, et al. Multilevel thresholding for image segmentation through an improved quantum-behaved particle swarm algorithm [J]. IEEE transactions on instrumentation and measurement, 2010, 59 (4): 934-946.

[10] 朱曉東,劉丹,李廣.基于混合優(yōu)化算法的模糊系統(tǒng)辨識[J]. 鄭州大學學報(工學版), 2015, 36(4): 10-14.

[11] KENNEDY J, BLACKWELL T. Particle swarm optimization [J]. Swarm intelligence, 2007, 1(1):33-57.

[12] CLERC M, KENNEDY J. The particle swarm-explosion, stability, and convergence in a multi-dimensional complex space [J]. IEEE transactions on evolutionary computation, 2002, 6(1): 58-73.

[13] SUN J, FENG B, XU W. Particle swarm optimization with particle having quantum behavior [C]// Congress on Evolutionary Computation. Portland, OR:IEEE Press, 2004: 325-331.

[14] GAO H, XU W B. A new particle swarm optimization and its globally convergent modifications [J]. IEEE transactions on system, man, and cybernetics, Part B, 2011, 41(5): 1334-1351.

[15] LING S H, IU H H C, CHAN K Y, et al. Hybrid particle swarm optimization with wavelet mutation and its industrial applications [J]. IEEE transactions on system, man and cybernetics, Part B, 2008, 38(3): 743-763.

[16] PARK J B, JEONG Y W, SHIN J R, et al. An improved particle swarm optimization for nonconvex economic dispatch problems[J]. IEEE transaction on power systems, 2010, 25(1): 156-166.

[17] AKAY B. A study on particle swarm optimization and artificial bee colony algorithms for multilevel thresholding [J]. Applied soft computing, 2012, 13(6): 3066-3091.

[18] CAO L, BAO P, SHI Z K. The strongest schema learning GA and its application to multilevel thresholding [J]. Image vision computing, 2008, 26(5): 716-724.