改進人工蜂群算法在數(shù)字圖像相關(guān)中的應(yīng)用

摘 要： 針對人工蜂群算法存在的收斂速度較慢，易陷入局部最優(yōu)解的問題，提出一種改進的人工蜂群優(yōu)化算法，并應(yīng)用于數(shù)字圖像相關(guān)的整像素位移搜索中。該算法借助相關(guān)度值的變化來動態(tài)調(diào)整跟隨蜂的搜索步長，平衡其全局和局部的搜索能力；偵察蜂利用遺傳算法的交叉運算產(chǎn)生新解，改善全局搜索能力。實驗結(jié)果表明，改進的算法能有效地提高收斂速度，改善整像素位移搜索的性能。

關(guān)鍵詞： 人工蜂群算法； 數(shù)字圖像相關(guān)； 變形； 整像素位移； 動態(tài)步長； 交叉運算

中圖分類號： TN919?34； TP301.6 文獻標(biāo)識碼： A 文章編號： 1004?373X（2013）24?0070?03

Application of improved artificial bee colony algorithm in digital image correlation

YANG Song1，2， SHAO Long?tan1， JIN Feng3， SHI Peng?hui4， CHI Jian?wei5

（1. State Key Laboratory of Industrial Equipments， Dalian University of Technology， Dalian 116024， China；

2. Education Technology Computing Center， Dalian Ocean University， Dalian 116023， China；

3. Dalian Municipal Meteorological Bureau， Dalian 116001， China； 4. College of Information Engineering， Dalian Ocean University， Dalian 116023， China；

5. College of Science， Dalian Ocean University， Dalian 116023， China）

Abstract： Aiming at the problems of slow convergence speed and easy to fall into local optimal solution， which exist in artificial bee colony algorithms， an improved artificial bee colony optimization algorithm is proposed for the pixel displacement search in digital image correlation. In the algorithm， the search step of the following bee is adjusted dynamically according to the changes of the correlation to balance the capability of global search and local search， and the scout bee employs crossover operation of genetic algorithm to generate new solution for improving the global search capacity. The experimental results show that the improved algorithm can enhance the convergence capability effectively and improve the performance of integer pixel displacement search.

Keywords： artificial bee colony algorithm； digital image correlation； deformation；pixel displacement； dynamic step； crossover operarion

數(shù)字圖像相關(guān)方法（Digital Image Correlation Method，DICM），又稱為數(shù)字散斑相關(guān)方法 （Digital Speckle Correlation Method，DSCM） 是現(xiàn)代光學(xué)測量技術(shù)的重要方法之一[1]，用于實現(xiàn)物體表面的位移和變形的測量。數(shù)字圖像相關(guān)方法在1980年由Peters，Ranson和Yamaguchi同時獨立提出的。該方法不僅具有其他光學(xué)測量方法所具有的全場、非接觸測量等優(yōu)點外，還具有光路簡單、對測量環(huán)境要求低、便于開展工程現(xiàn)場測量等優(yōu)點[2]，是一種很有應(yīng)用前途的光學(xué)測量方法。

數(shù)字圖像相關(guān)法研究的核心內(nèi)容是相關(guān)搜索方法。早期采用逐點搜索法，這會花費大量時間，后來很多學(xué)者對其進行改進，相繼提出了Newton?Rapson算法[3]、爬山法[4]、十字搜索法[5]、小波變換法[6]和神經(jīng)網(wǎng)絡(luò)法[7]等，這些算法嚴(yán)重依賴于初值的選取，且部分在理解和實現(xiàn)上比較復(fù)雜。相比之下，群智算法有諸多優(yōu)點，可直接把目標(biāo)函數(shù)值作為搜索信息，避免函數(shù)求導(dǎo)，可解決目標(biāo)函數(shù)較復(fù)雜的問題。目前應(yīng)用的主要有差分進化（DE）算法[8]、遺傳（GA）算法[9]、粒子群（PSO）算法[10]等，這些算法無需計算梯度和二階導(dǎo)數(shù)，是對圖像相關(guān)搜索方法的有益補充。近年來一些新興群智優(yōu)化算法的出現(xiàn)，為圖像相關(guān)搜索方法的研究增添了新的動力。

人工蜂群算法（Artificial Bee Colony，ABC）是由土耳其埃爾吉耶斯大學(xué)的Karaboga在2005年提出的一種基于蜜蜂群智搜索行為的隨機優(yōu)化算法[11]。蜂群算法采用勞動分工和協(xié)作的機制，具有控制參數(shù)少，計算簡潔及易于實現(xiàn)等優(yōu)點，既能解決連續(xù)優(yōu)化問題，又能解決組合優(yōu)化問題[12]。函數(shù)優(yōu)化測試表明[13]，人工蜂群算法比遺傳算法、差分進化算法和粒子群算法具有更好的優(yōu)化性能，且容易與其他算法相結(jié)合進行改進。本文提出改進人工蜂群算法（IABC），應(yīng)用于數(shù)字圖像相關(guān)搜索中，有效提高了整像素位移的搜索能力。

1 數(shù)字圖像相關(guān)法基本原理

數(shù)字圖像相關(guān)法借助物體變形前后兩幅圖像的局部相關(guān)性來計算得到點的位移值，即在變形前圖像中以特定點[x，y]為中心取[2M+1×2M+1]個像素的區(qū)域，通過一定的搜索方法在變形后的圖像上尋找同樣大小子區(qū)域的中心[x*，y*]，兩點位移差為[u，v]，見式（1）。位移量[u，v]的計算要考慮兩個區(qū)域的相關(guān)度，見式（2）。

[x*=x+u， y*=y+v] （1）

[C=y=-My=Mx=-Mx=Mfx，y-fmgx*，y*-gmy=-My=Mx=-Mx=Mfx，y-fm2?y=-My=Mx=-Mx=Mgx*，y*-gm2] （2）

式中：[M]為樣本區(qū)域半徑；[fx，y]為圖像上點[x，y]處的灰度值；[gx*，y*]為圖像上點[x*，y*]處的灰度值；[fm]，[gm]為對應(yīng)區(qū)域的灰度均值。相關(guān)度[c]取值范圍為[-1，1]，當(dāng)參數(shù)[u]和[v]為適當(dāng)值時，兩個區(qū)域的相關(guān)度達到全局最大。搜索位移值[u，v]的過程是求2個區(qū)域相關(guān)度極值的過程。要計算每個點精確的位移值，可以通過兩步法：先粗定位，后細定位。即先計算出整像素位移，然后計算精確的亞像素位移。數(shù)字圖像相關(guān)的搜索時間主要取決于粗定位。相關(guān)系數(shù)[c]是關(guān)于位移值[u，v]的函數(shù)，粗定位問題可以看成兩個離散整數(shù)變量關(guān)于相關(guān)函數(shù)[c]的優(yōu)化問題，且[u]和[v]被限定在搜索范圍內(nèi)。細定位可以根據(jù)相關(guān)系數(shù)的單峰性近似滿足高斯分布的特點，采用相關(guān)函數(shù)曲面擬合法求極值點來計算亞像素位置[14]。

2 基本人工蜂群算法

人工蜂群算法主要模擬蜂群的智能采蜜行為，蜜蜂根據(jù)各自的分工進行不同的采蜜活動，并實現(xiàn)蜜源信息的共享和交流，從而找到問題的最優(yōu)解。在基本人工蜂群算法中，蜜蜂主要有引領(lǐng)蜂、跟隨蜂和偵察蜂。人工蜂群算法在求解優(yōu)化問題時，蜜源位置被抽象成解空間中的點，蜜蜂采蜜的過程也就是搜尋最優(yōu)解的過程。引領(lǐng)蜂和跟隨蜂根據(jù)式（3）進行蜜源位置的更新：

[υij=xij+rijxij-xkj] （3）

式中：[k∈1，2，…，N]，[j∈1，2，…，d]，[k]和[j]都是隨機選取的，且[k≠i]，[N]表示解的個數(shù)；[rij∈][-1，1]之間的隨機數(shù)，它控制[xij]鄰域的生成范圍。

跟隨蜂通過觀察引領(lǐng)蜂的搖擺舞來判斷蜜源的收益率，并依據(jù)收益率來選擇蜜源。收益率由式（4）可得：

[Pi=fυiji=1Nfυij] （4）

式中[fυi]表示蜜源[υi]的相關(guān)度。跟隨蜂選擇收益率大的蜜源，根據(jù)式（3）進行搜索。搜索完畢后，采用貪心選擇機制，計算全局最優(yōu)蜜源位置。

若連續(xù)經(jīng)過limit次迭代后，某個蜜源的相關(guān)度沒有得到改善，表明此蜜源已陷入局部最優(yōu)，應(yīng)該被放棄，與這個蜜源對應(yīng)的引領(lǐng)蜂轉(zhuǎn)換成偵察蜂，新蜜源位置由式（5）產(chǎn)生：

[xji=xjmin+rxjmax-xjmin] （5）

式中：[xjmax]和[xjmin]分別表示變量的最大值和最小值；[r]是[0，1]之間隨機數(shù)。通過如此重復(fù)搜索，最終找到最優(yōu)解。

3 基于改進人工蜂群算法的數(shù)字相關(guān)搜索

3.1 改進人工蜂群算法

跟隨蜂在選中的蜜源鄰域內(nèi)按照式（3）進行搜索，其步長具有隨機性，算法尋優(yōu)速度相對較慢，易錯過或陷入全局最優(yōu)解。文獻[15]對搜索步長做線性調(diào)整，隨步長減少，進入局部最優(yōu)解鄰域內(nèi)也很難跳出。這里將跟隨蜂更新蜜源的方法做了修改，步長根據(jù)相關(guān)度函數(shù)值進行動態(tài)調(diào)整，如式（6）～式（8）所示：

[υij=xij+ωnxij-xkj] （6）

[ωn=e-an/an-1，n=0，1，…，Gmax] （7）

[an=1mi=1mfυni-fυnmax， n=0，1，2，…] （8）式中：[ωn]稱為動態(tài)步長因子；[fυni]為[υi]在第[n]次迭代時對應(yīng)的相關(guān)度；[fυnmax]為在第[n]次迭代時對應(yīng)的最優(yōu)相關(guān)度；[Gmax]為最大迭代次數(shù)。當(dāng)[an]為第[n]次迭代時，引領(lǐng)蜂搜索后種群相關(guān)度函數(shù)的平整度因子，其值根據(jù)相關(guān)度值進行變換。

在迭代過程中，為防止[anan-1]的值變化過大，采用工程中常用的[e]作為指數(shù)，可有效降低比值變化的幅值，使得[ωn]的取值范圍在區(qū)間[0，1]內(nèi)。[ωn]的計算充分利用相關(guān)度函數(shù)的信息，在搜索方向上具有一定的啟發(fā)性。當(dāng)[an]變化較大時，[ωn]也就較大，便于大步長搜索；當(dāng)[an]變化較小時，[ωn]也就較小，便于在相關(guān)度極值點附近小步長搜索，這樣可以較好地平衡全局搜索和局部搜索能力，不易陷入局部極值。當(dāng)?shù)螖?shù)大于limit時，偵查蜂根據(jù)式（5）產(chǎn)生新蜜源，式（5）具有一定的隨機性，這里提出將被放棄的蜜源與當(dāng)前的全局最優(yōu)蜜源進行交叉運算，如式（9）所示：

[υlimit=υmax×p+υlimit×1-p] （9）

式中：[υlimit]為經(jīng)limit次迭代后相關(guān)度沒有發(fā)生變化的蜜源；[υmax]為當(dāng)前最優(yōu)蜜源；[p]為遺傳交叉因子。通過運用遺傳交叉運算，改善算法的全局搜索能力。

3.2 改進算法的流程

（1）初始化蜜源[υii=1，2，…，N]，[υi]為2維向量[ui，vi]，根據(jù)式（1），式（2）計算各個蜜源的相關(guān)度；

（2）模擬蜂群行為，引領(lǐng)蜂根據(jù)式（3）搜索最優(yōu)蜜源；

（3）根據(jù)式（4）計算各蜜源的收益率，跟隨蜂選擇收益率高的蜜源，計算[ωn]的值（[a0]為初始時種群相關(guān)度函數(shù)的平整度因子），并利用式（6）繼續(xù)搜索；

（4）采用貪心選擇機制，更新全局最優(yōu)蜜源；

（5）若某個蜜源經(jīng)過limit次迭代后其相關(guān)度仍沒有得到改善，則根據(jù)式（9）得到新的蜜源；

（6）若迭代次數(shù)達到設(shè)置的最大次數(shù)Gmax時，算法結(jié)束，否則轉(zhuǎn)到步驟（2）。

4 實驗結(jié)果與分析

根據(jù)文獻[16]制作兩幅散斑圖像，且第二幅圖像相對第一幅圖像的位移量為（14.3，-5.2）。相關(guān)運算的參數(shù)設(shè)置為：搜索范圍設(shè)定為40×40 pixel區(qū)域，相關(guān)運算模板的大小為21×21 pixel，種群個數(shù)為50（即引領(lǐng)蜂和跟隨蜂各占總數(shù)的一半，均為25個），交叉因子為0.9。所用計算機配置為：Intel Core2 CPU（2.8 GHz），2 GB內(nèi)存。由于優(yōu)化算法具有隨機性，為獲得更為一般的規(guī)律，故采用統(tǒng)計學(xué)方法對隨機點（123，87）進行1 000次整像素位移計算，程序采用Matlab編程實現(xiàn)。

分別采用遺傳（GA）算法、粒子群（PSO）算法、基本人工蜂群（ABC）算法和改進人工蜂群（IABC）算法進行計算，得到收斂率隨迭代次數(shù)變化的曲線，如圖1所示。

由圖1可知，改進算法在55代附近開始接近100%收斂，而其他算法還沒達到收斂，表明在種群數(shù)相等的條件下，隨著迭代次數(shù)的增加，改進人工蜂群算法具有更高的收斂率。對計算過程中的迭代時間和收斂率進行擬合，繪制出時間與收斂率的關(guān)系圖，如圖2所示。由圖可知，當(dāng)計算時間在85 s附近時，改進算法已近似100%收斂，而其他算法尚未達到，說明在相同種群數(shù)的條件下，改進算法的收斂時間更短。除此之外，還將此方法引入到高維連續(xù)函數(shù)優(yōu)化應(yīng)用中，取得了更為顯著的優(yōu)化效果。

圖1 迭代次數(shù)與收斂率的關(guān)系圖

圖2 計算時間與收斂率關(guān)系圖

5 結(jié) 語

本文針對人工蜂群優(yōu)化方法收斂速度慢、易陷入局部最優(yōu)解的缺點，提出了基于動態(tài)步長因子的改進人工蜂群算法。新算法通過適應(yīng)度值來動態(tài)調(diào)整搜索步長，改善算法的收斂性能，并借鑒遺傳算法的交叉操作，增強群體的優(yōu)秀特征，加快搜索速度。通過模擬數(shù)字散斑圖像對算法進行驗證表明：本文算法具有較強的全局搜索能力，顯著提高數(shù)字圖像相關(guān)中整像素位移的搜索速度。

參考文獻

[1] PETERS W H， RANSON W F. Digital imaging techniques in experimental stress analysis [J]. Optical Engineering， 1982， 21（3）： 427?431.

[2] 王懷文，亢一瀾，謝和平.數(shù)字散斑相關(guān)方法與應(yīng)用研究進展[J].力學(xué)進展，2005，35（2）：195?203.

[3] BRUCK H A， MCNEIL S R， SUTTON M A， et al. Digital image correlation using Newton? Rapshon method of partial differential correction [J]. Experimental Mechanics， 1989， 29（3）： 261?267.

[4] ZHAO Wen?zhong， JIN Guan?chang. An experimental study on measurement of Poisson’s ratio with digital correlation method [J]. Journal of Applied Polymer Science， 1996， 60： 1083?1088.

[5] 芮嘉白，金觀昌，徐秉業(yè).一種新的數(shù)字散斑相關(guān)方法及其應(yīng)用[J].力學(xué)學(xué)報，1994，26（5）：599?607.

[6] 簡龍暉，林碧森，劉寧，等.基于小波變換的新型數(shù)字散斑相關(guān)方法[J].光學(xué)技術(shù)，2003（7）：216?218.

[7] PITTER M C， SEE C W， SOMEKH M G. Subpixel microscopic deformation analysis using correlation and artificial neutral networks [J]. Optics Express， 2001， 8（6）： 322?327.

[8] 潘兵，謝惠民.基于差分進化的數(shù)字圖像相關(guān)方法[J].光電子·激光，2007，18（1）：100?103.

[9] 陳華，葉東，陳剛，等.遺傳算法的數(shù)字圖像相關(guān)搜索法[J].光學(xué)精密工程，2007，15（10）：1633?1637.

[10] 杜亞志，王學(xué)濱.基于粒子群算法的整像素數(shù)字圖像相關(guān)方法[J].計算機工程與應(yīng)用，2012（6）：200?204，208.

[11] KARABOGA D. An idea based on honey bee swarm for numerical optimization， TR06 [R]. UK： Computer Engineering Department， Engineering Faculty， Erciyes University， 2005.

[12] 王慧穎，劉建軍，王全洲.改進的人工蜂群算法在函數(shù)優(yōu)化問題中的應(yīng)用[J].計算機工程與應(yīng)用，2011（13）：36?39.

[13] 張超群，鄭建國，王翔.蜂群算法研究綜述[J].計算機應(yīng)用研究，2011，28（9）：3201?3205，3214.

[14] 于起峰，尚洋.攝影測量學(xué)原理與應(yīng)用研究[M].北京：科學(xué)出版社，2009.

[15] 劉俊霞，賈振紅，覃錫忠，等.改進人工蜂群算法在信道分配上的應(yīng)用[J].計算機工程與應(yīng)用，2013（7）：119?122.

[16] 金觀昌.計算機輔助光學(xué)測量[M].北京：清華大學(xué)出版社， 2007.