改進人工蜂群算法在圖像分割中的應用

宋　錦，高　浩，王保云

(1.南京信息職業技術學院 通信學院，江蘇　南京　210023;2.南京郵電大學 自動化學院，江蘇　南京　210023)

?

改進人工蜂群算法在圖像分割中的應用

宋錦1，2，高浩2，王保云2

(1.南京信息職業技術學院 通信學院，江蘇南京210023;2.南京郵電大學 自動化學院，江蘇南京210023)

作為圖像處理技術的一個分支，多閾值圖像分割技術已經越來越吸引人們的注意。然而，很多閾值分割技術計算時間較長，且其隨著維數的增加而呈指數性增長。因此，為了提高分割的效率，引入基于改進人工蜂群優化算法的多閾值圖像分割技術。在分析了標準人工蜂群算法缺陷的基礎之上，從雇傭蜂和觀察蜂的搜索公式進行改進，使其能夠更有效率地收斂至全局最優，同時采用最大類間方差法(Otsu)作為測試改進算法性能好壞的標準。實驗證明，改進后的算法更好地平衡了全局搜索和局部尋優能力，在加快收斂速度的同時提高了尋優精度，獲得了良好的圖像分割效果。

圖像分割；人工蜂群；多閾值；計算時間；最大類間方差法

作為圖像處理的基礎，圖像分割是從低層次圖像處理到較高層次圖像分析、更高層次圖像理解的關鍵步驟。圖像處理的后續步驟，如特征提取、目標檢測等都十分依賴于分割的結果和精度，因此，圖像分割技術的發展和完善對圖像處理技術具有十分重要的作用和研究價值。所謂圖像分割，就是根據圖像前景和背景一些特征，或閾值色彩信息的不同，在一幅圖像中提取出有意義的一部分。近幾年來，很多圖像分割技術被提了出來。在所有目前存在的分割技術中，圖像閾值分割技術由于其易用性、穩定性及高精度等特性，已經成為一個研究熱點。圖像閾值分割技術大致可以分為兩類：一類是通過分析圖像的直方圖特性來決定最優閾值的選取[1-2]；另一類是通過設計一個評測函數，采用優化算法尋求它的最優解，從而決定最優閾值[3-5]。這些方法包括最大熵法[3]、最小貝葉斯誤差法[4]、最大類間方差法(Otsu)[5]等。其中，最大類間方差法是利用將圖像分為幾類，以閾值信息為輸入構造一個函數，使得類內方差最小，類間方差最大，它是一個最大化的閾值分割函數。然而，由于窮舉搜索算法分割時間較長，且其復雜度隨著維數的升高而呈指數形式增長。因此，很多科學家將智能優化算法引入進來。常用的有粒子群算法(Particle Swarm Optimization)[6]、差分進化算法(Differential Evolution)[7]、人工蜂群算法(Artificial Bee Colony)[8]、蟻群算法(Ant Colony Optimization)[9]等。其中，人工蜂群算法由于其較強的全局搜索能力已經被廣泛運用于各個應用領域。但是其本身收斂速度慢，尋優精度不高，因此也限制了它的一些性能。本文針對這些特點，提出了一種基于群體經驗的改進型人工蜂群算法(Social Experience Based Artificial Bee Colony Algorithm， SEABC)，從而加快收斂速度和提高尋優精度。

1　Otsu閾值分割方法

1978年，科學家Otsu提出了一種比較典型的圖像分割方法——最大類間方差法(Otsu)。該算法假設將一幅圖片可以分為好幾部分，利用類內方差最小、類間方差最大的特點，在灰度直方圖的基礎上采用最小二乘法推導出來一個最大化函數，具有統計意義上的最佳分割。具體表述如下：設一幅圖片有N個像素數，灰度值最小為0，最大為L。每個灰度級i對應的像素數為Ni，令Pi表示每個灰度級出現的概率，則有

(1)

其中

(2)

0≤t1≤t2≤…≤tM-1≤L

(3)

其中

(4)

(5)

(6)

2　人工蜂群算法

作為一種進化算法，人工蜂群算法(Artificial Bee Colony)在2005年由土耳其學者Karaboga提出，該算法模擬蜜蜂群體尋找食物源的行為進行尋優，是一種仿生智能計算方法。

2.1人工蜂群算法機理

人工蜂群算法建立在自然界中蜜蜂采蜜的機理之上，按照不同的分工將蜜蜂分為雇傭蜂(employed bees)、觀察蜂(onlooker bees)和偵察蜂(scouts)。

人工蜂群算法中，雇傭蜂和觀察蜂的數量相等，均等于食物源的數量。一個食物源對應著一個雇傭蜂和若干觀察蜂。食物源的價值越高，觀察蜂選擇其進行精細搜索的概率越大。在圖像分割問題中，所有閾值構成問題的一個可行解，作為每個食物源的位置編碼在人工蜂群算法中。而每個食物源價值的衡量，對應于分割問題中Otsu方法所求得的函數值。由上所述，Otsu圖像閾值分割是一個最大化的問題，因此對應的函數值越大，說明食物源的價值越高，對應的食物源的位置，及圖像分割的閾值分割效果越好。

2.2人工蜂群算法步驟

1)初始化

用N來表示食物源的個數，則雇傭蜂和觀察蜂的數量均為N。設置循環的最大迭代次數maxCycle，食物源連續不更新最大容忍次數Limit。令L和U分別表示搜索空間的上限和下限值，即圖像分割問題中被分割圖像所有灰度的最小值和最大值，則每個食物源的位置可以初始化為

(7)

式中：D表示搜索空間的維數，在圖像分割問題中，D=M-1。

2)雇傭蜂

每個雇傭蜂腦海中保留一個食物源的記憶，并在每一次迭代中對此食物源進行更新，更新時主要是通過向自己的鄰居學習，從而決定下一代的位置，更新公式如下

(8)

式中：φ為服從均勻分布的在區間[-1,1]內隨機產生的隨機數；i=1,2,…,N；j為區間[1,M-1]內的一個整數，隨機選取。在人工蜂群算法中，采用貪婪更新的原則，當且僅當本次迭代中更新的新位置比原來的位置適應值更大的時候，才將其替代原來的位置并參與到下一代的迭代中來。

3)輪盤賭

每個食物源對應一個適應值，適應值越大，其被觀察蜂選中并在其周圍區域進行精細搜索的概率就越大。每個食物源被選中的概率計算如下

(9)

式中：i=1,2,…,N表示第i個食物源；Fiti為由式(3)計算出來的第i個食物源的適應值。

3)觀察蜂

觀察蜂根據雇傭蜂所尋找到的食物源的適應值，依照輪盤賭原則選擇食物源進行精細搜索，其搜索公式和觀察蜂相同，如式(8)所示。

4)偵察蜂

當一個食物源連續Limit代不再進行更新時，算法認為此食物源位置無效，相應的雇傭蜂轉化為偵察蜂，在搜索空間內重新初始化，即重新開采一個位置來代替原來的位置。

3　改進的人工蜂群算法

3.1傳統人工蜂群算法的不足

每一次迭代過程中，傳統蜂群算法的雇傭蜂和觀察蜂都只參考一個鄰居的信息，在搜索空間中廣泛搜索，全局搜索能力強。然而，它們在搜索過程中并不記錄歷史所找過的最優值，不受它們引導，因而搜索具有一定的盲目性，也造成了收斂速度慢，局部尋優能力差的特點。

為了深入研究人工蜂群算法的搜索性能，對食物源每相鄰兩代的變化幅度(稱其為速度)進行研究。由于每只蜜蜂均采用搜索式(8)更新食物源，因此食物源位置在每一維上的變化可以表述為

(10)

圖1　標準ABC算法的速度變化曲線

從圖1可以看出，標準人工蜂群算法中，每個食物源在相鄰兩代的變化幅度至始至終都保持一個很大的值。而在智能優化過程中，最理想的情況為在優化初期速度值較大，從而在搜索空間中進行廣泛的搜索，而在搜索后期速度變化較小，從而在可能的最優解附近進行精度尋優。這與希望的情況所不相符。

為充分研究食物源在搜索空間中的分布情況，以兩維為例，食物源個數為100，在sphere函數上畫出食物源在搜索空間中分分布圖，如圖2所示。由圖可以看出，在標準ABC算法中，蜂群在搜索空間中的分布一直都是一個很廣泛的狀態，因而可以得出它的收斂速度則比較緩慢。

3.2 改進的人工蜂群算法

如上文分析，標準人工蜂群算法的搜索公式全局搜索能力強，但收斂速度慢，精度尋優能力差。由于在標準ABC算法中，食物源在更新時只向一個隨機選擇的鄰居學習，其可利用并且有效的信息較少，造成了收斂速度慢的缺陷。此外，較慢的收斂速度影響了最后的尋優精度。因此，為了提高人工蜂群算法的搜索性能，本文提出一種改進的人工蜂群算法，使得雇傭蜂和觀察蜂在進行食物源的探索過程中，向整個種群學習的同時，也受全局最優的引導。搜索公式如下

圖2　標準ABC算法中食物源在搜索空間內的分布圖

(11)

式中：φ∈[-1,1],φ∈[0,1.5]，均為均勻分布；best為適應值最大的食物源的位置；ave代表所有食物源位置的平均值，表述如下

(12)

式中：把第一部分稱為記憶項，作為雇傭蜂和觀察蜂對原來食物源位置的記憶；第二項為社會學習項，φ為社會學習因子，這一部分為每只蜜蜂向整個群體學習，由ave記錄的位置為所有食物源信息的集合；第三部分為最優學習項，φ為最優學習因子。此部分的引入是為了讓蜜蜂在搜索過程中可以參考價值最佳食物源的信息，從而得到最優位置的引導，在加快收斂速度的同時也可以提高尋優精度。

雇傭蜂和觀察蜂在搜索過程中，如果沒有自己對原來食物源位置的記憶，那么每次新的搜索都無法繼承上一代的經驗，搜索將會變的盲目。如果只有第二項沒有第三項，蜜蜂在搜索過程中雖然向全體成員學習，但由于是取平均值，沒有全局最優的指引，所以學習程度不夠，依然造成收斂速度慢，精度尋優能力弱的缺點。此外，如果只有第三項而沒有第二項，那么收斂速度雖然提高了，但缺乏其他信息的指引，算法會較易造成早熟收斂的現象，從而陷入局部最優，不利于全局搜索。綜上，新提出的改進算法中，三項互相補充，缺一不可。

此外，由于ave和best向量的引入，加大了蜜蜂在尋找食物源過程中可利用的有效信息，從而使得收斂速度更快，精度尋優更好。

4　仿真實驗結果

通過測試其在一系列圖片上的分割效果，進而獲得SEABC算法的性能。測試圖像包括4幅經典的分割圖像[10-11]和4幅Berkeley數據庫的分割圖像[12]，如圖3所示,圖a～圖d為經典分割圖像，圖e～圖f為Berkeley數據庫的4幅圖像。

圖3　示例標準圖像

實驗具體分為兩組，第一組為SEABC與傳統的Otsu算法相比，主要在M-1=2和M-1=3上進行測試，而當分割閾值大于4時，由于Otsu計算時間太長，無法獲得其結果。另外由于篇幅限制，只列出了在Berkeley數據庫的4幅圖像的比較結果，如表1所示。可以看出，當分割閾值M-1=2和M-1=3時，SEABC基本可以取得與Otsu相同的函數值和優化閾值，但時間卻要短得多，由此驗證了算法的有效性。表1中Otsu的運行時間即為運行1次Otsu算法的時間，SEABC算法的運行時間是將其運行20次之后所取的平均時間。

表1SEABC與傳統Otsu算法的比較

第二組實驗為SEABC與其他智能優化算法比。為充分驗證SEABC的性能，將其與經典的粒子群算法(PSO)[6]、差分進化算法(DE)[7]、人工蜂群算法(ABC)[8]、以及一些人工蜂群算法的改進版本GABC算法[13]、QABC算法[14]和MRABC算法[15]進行比較。分割閾值取M-1=3,4,7,8，對于低維的圖像分割M-1=3,4，最大迭代次數為100，對于高維的圖像分割M-1=7,8，最大迭代次數取200。種群規模統一設置為20。為體現算法的公平性，所有的算法均獨立運行20次，以平均值進行比較。實驗結果如表2所示。另外本文只列出閾值數目為7時SEABC的分割效果圖，如圖4所示。

表2基于Otsu的幾種不同優化算法的比較

ImagesM-1適應度值(標準方差)PSODEABCGABCQABCMRABCSEABCa310724.13129339.862210726.081310726.154710724.856610724.225710726.5866(6.5653)(818.2353)(1.2002)(0.9172)(2.6536)(3.3479)(0.0645)411836.363010371.637211844.180711846.019611844.893311846.496311846.9601(16.2519)(662.9939)(5.8197)(4.7366)(5.2880)(2.6398)(4.5546)713530.362912013.267813592.450013590.594313582.960013572.903713594.4170(50.7036)(419.1322)(19.9031)(16.8539)(16.6237)(19.3606)(14.4549)813826.072312317.498513882.906913881.502113877.537513856.150313883.5862(66.5906)(309.1737)(16.8714)(23.5888)(16.0022)(27.4612)(17.1166)b39088.10688137.48959089.07329089.28139089.14929086.49839089.3220(3.5665)(401.9401)(0.6114)(0.2067)(0.3191)(5.6163)(0.0292)49905.07008958.96419903.10699905.13989903.35409897.11109907.3058(6.7532)(409.5844)(6.4911)(5.3079)(4.5541)(14.7919)(3.7093)711030.016810033.359411077.589911074.325311074.327911055.399611080.0629(34.9555)(359.8501)(7.7245)(12.8972)(10.5035)(23.7200)(12.7541)811191.773810241.596611239.459811240.844211238.753911230.040211247.2505(37.2258)(335.4079)(11.2995)(13.5849)(12.9588)(16.9984)(8.3266)

ImagesM-1適應度值(標準方差)PSODEABCGABCQABCMRABCSEABCc311050.68749571.429411049.641411050.059611050.188711048.505311051.0355(1.2959)(708.8131)(2.3696)(0.0055)(2.0476)(5.6948)(0.1050)412292.472710542.250312293.698612294.735712294.555712268.003812300.3651(11.9924)(626.4165)(4.5228)(7.7339)(10.1395)(32.5309)(4.3004)713976.946412222.572214024.072714036.270914038.327913951.531014036.5326(50.6286)(463.3574)(21.6549)(18.9242)(14.2172)(75.3597)(11.1856)814194.530912470.237814297.862314310.100114305.921114217.714514310.1158(101.9472)(369.5747)(18.0447)(19.5704)(18.0412)(92.6425)(16.2406)d36420.88955646.64816423.89576425.38456424.99916423.47746425.5659(5.2075)(412.7067)(3.6028)(2.1525)(2.6858)(3.3721)(2.2795)46955.13796245.50166964.28006967.81886963.20396963.18406968.5380(16.5411)(214.0008)(7.2682)(4.6238)(9.6807)(10.4129)(6.0799)77699.67206832.50247740.30507734.11047735.40507723.14517741.9377(31.1951)(213.6403)(8.8278)(13.0711)(12.6904)(14.3028)(11.3800)87792.46547041.22207864.00137857.74967856.12477838.90737864.5368(40.4094)(202.8842)(22.6004)(19.9562)(18.3237)(27.1457)(14.9466)e322052.708013976.584922052.401522052.700622052.583716740.182722052.70800.0000498.53640.53630.03240.44263486.79260.0000423697.024314986.332123689.349023696.514723689.379515805.943123698.28691.1112407.36338.25755.36187.54721823.60193.4007725963.600616579.178425960.717725962.000525965.831017823.375125969.651620.9602500.583116.003412.914513.89521916.60009.1314826297.873716937.184026291.059626300.920826287.509917917.934326299.015631.0172536.731523.067017.137323.29841966.974815.8563f38412.83116825.95178415.17478415.44198415.08048414.31978417.4419(10.7400)(640.0900)(0.7800)0.0000(0.8000)(3.2400)0.000049328.70827449.15399339.81839340.69459338.71659341.46569343.1244(19.8300)(626.3100)(3.4700)(4.5600)(6.8200)(2.6000)(1.7700)710603.45618907.685810653.228910653.692110653.706410655.286510662.8263(39.8300)(582.9300)(12.7900)(14.7700)(13.6800)(16.6500)(9.0000)810701.16509201.970710858.151210859.609610866.239010846.635610870.0086(116.7900)(402.3400)(13.0000)(13.0300)(15.3400)(21.7500)(14.5200)g36098.30005109.48006099.38006099.53006099.01006099.47006099.63(3.4500)(435.3200)(0.5100)(0.4100)(0.7000)(0.3700)0.000046754.19085585.86886761.23926762.63656762.18346763.53386765.4644(11.8700)(489.4000)(6.0800)(5.9900)(4.6400)(4.8500)(2.3100)77647.48256574.89267681.11597688.72177682.85477667.63187694.3490(29.1000)(383.8400)(12.0600)(10.6200)(11.4000)(28.4500)(8.0400)87775.05846727.75387831.05207836.84637829.91997812.70167839.1212(53.3000)(349.0100)(5.0300)(8.5800)(8.6800)(21.5700)(7.6400)

ImagesM-1適應度值(標準方差)PSODEABCGABCQABCMRABCSEABCh35216.49304712.29815216.81745216.96185216.92165216.39555216.9658(1.2100)(216.7800)(0.5200)(0.0200)(0.1600)(2.4800)0.000045683.42755137.61295688.44465690.75555687.33605689.02905690.1510(8.2100)(198.7100)(2.8300)(1.7200)(3.2100)(2.9800)(2.5100)76289.48975728.79426323.43746323.47966324.95576300.07306328.8935(28.7300)(210.6300)(6.6600)(7.9100)(11.3000)(19.0800)(8.5000)86353.57315818.75936402.87296399.62906401.36746396.70916406.7394(25.8200)(207.7500)(6.0300)(9.1800)(8.1600)(12.7800)(6.7700)

圖4　SEABC算法在8幅圖片上的分割結果，M-1=7

從結果可以看出，在這8幅圖像和4個維數的測試上，SEABC在大部分實驗中都取得了最大的函數適應值以及最小的方差，分割效果最好。這主要歸功于它的搜索策略。式(11)中社會學習項使得蜜蜂在搜索過程中搜集所有食物源的信息，綜合考慮每個食物源的意見，從而降低向適應值差的食物源學習的機會，避免迭代浪費。此外，觀察蜂和雇傭蜂在搜索過程中很大程度地受全局最優的引導，搜索具有方向性，收斂速度加快，精度尋優能力升高。而對于其他的算法，PSO在優化過程采用全維更新的策略，存在維度束縛的缺陷。DE向隨機選擇的3個個體進行學習，有強大的全局搜索能力，但是其收斂速度特別慢。以人工蜂群算法為基準的幾個算法中，均繼承了ABC的優點，但它們都是向一個或有限的幾個個體學習，并沒有利用群體經驗的信息，因此尋優精度不如SEABC。

5　結束語

由于傳統人工蜂群算法存在易陷入局部最優的不足，本文在采蜜蜂和觀察蜂的鄰域搜索策略上進行了改進，引入了當前迭代的全局最優解和平均最優解，并將這種方法應用到圖像分割中來。實驗結果表明，改進后的SEABC算法在保證全局搜索的條件下加快了收斂速度，提高了尋優精度。

[1]HERTZ L，SCHAFER R W. Multilevel thresholding using edge matching[J]. Computer vision， graphics，and image processing，1988，44(3)：279-295.

[2]張辭，馬麗.基于改進的GSA彩色圖像分割方法研究[J].電視技術，2014， 38(13)： 39-42.

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

[4]郭紅.基于混合高斯模型和相似度的閾值分割[J]. 電視技術，2013，37(3)：40-43.

[5]HUANG D Y，WANG C H. Optimal multi-level thresholding using a two-stage Otsu optimization approach[J]. Pattern recognition letter，2009，30(3)：275-284.

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

[7]SARKAR S，DAS S. Multilevel image thresholding based on 2D histogram and maximum tsallis entropy—a differential evolution approach[J]. IEEE transactions on image processing，2013，22(12)：4788-4797.

[8]BHANDARI A K， KUMAR A， SINGH G K. Modified artificial bee colony based computationally efficient multilevel thresholding for satellite image segmentation using Kapur’s，Otsu and Tsallis functions[J]. Expert systems with applications，2015，42(3)：1573-1601.

[9]JU Z W， CHEN J Z， ZHOU J L. Image segmentation based on edge detection using K-means and an improved ant colony optimization[C]//IEEE 2013 International Conference on Machine Learning and Cybernetics(ICMLC). [S.1.]：IEEE，2013：297-303.

[10]GAO H， KWONG S， YANG J， et al. Particle swarm optimization based on intermediate disturbance strategy algorithm and its application in multi-threshold image segmentation[J]. Information sciences，2013(250)：82-112.

[11]MAITRA M，CHATTERJEE A. A hybrid cooperative-comprehensive learning based PSO algorithm for image segmentation using multilevel thresholding [J]. Expert systems with applications， 2008， 34 (2)：1341-1350.

[12]The berkeley segmentation dataset and benchmark[EB/OL].[2016-03-24]. http：//www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/.

[13]ZHU G， KWRONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization problems[J]. Applied mathematics and computation，2010(7)：3166-3174.

[14]KARABOGA D， GORKEMLI B. A quick artificial bee colony algorithm (qABC) and its performance on optimization problems [J]. Applied soft computing， 2014(23)： 227-238.

[15]AKAY B， KARABOGA D. A modified artificial bee colony algorithm for real-parameter optimization [J]. Information sciences, 2012(192)： 120-142.

宋錦(1969— )，女，碩士，副教授，研究領域為人工智能；

高浩(1976— )，博士，副教授，碩士研究生導師，研究領域為進化計算；

王保云(1967— )，博士，教授，博士研究生導師，研究領域為模式識別。

責任編輯：時雯

Multilevel image segmentation based on improved artificial colony algorithm

SONG Jin1，2，GAO Hao2，WANG Baoyun2

(1.DepartmentofTelecommunicationEngineering，NanjingCollegeofInformationTechnology，Nanjing210023，China；2.CollegeofAutomation，NanjingUniversityofPostsandTelecommunications，Nanjing210023，China)

As a branch of image processing，multilevel image segmentation has attracted more and more attentions. However， most of the threshold image segmentation techniques are time consuming and their computation time grows exponentially with dimension increasing. To improve the efficiency，an improved artificial bee colony algorithm (ABC) for the segmentation problem is introduced. Based on analyzing the shortcoming of the traditional ABC，the searching equation of employed bees and onlooker bees are improved for achieving a precise convergence to the global optima. Experimental results on a set of test images demonstrate that the proposed algorithm makes a better balance between exploration and exploitation，which gets higher solution accuracy and accelerates the convergence speed.

image segmentation； artificial bee colony； multi-threshold； computation time； Otsu

TP18

A

10.16280/j.videoe.2016.08.002

國家自然科學基金項目(61571236)；江蘇省高校品牌專業建設工程項目(PPZY2015A092)；江蘇省博士后基金項目(1402018A)

2016-03-24

文獻引用格式：宋錦，高浩，王保云.改進人工蜂群算法在圖像分割中的應用[J].電視技術，2016，40(8)：8-14.

SONG J，GAO H，WANG B Y.Multilevel image segmentation based on an improved artificial colony algorithm [J].Video engineering，2016,40(8)：8-14.