一種新的粒子群優(yōu)化的圖像匹配算法

王長清 朱進進 張佳偉

摘 ?要： 針對粒子群算法在圖像匹配中易陷入局部最優(yōu)、搜索速度慢以及匹配精度不高的問題，提出一種新的粒子群優(yōu)化的圖像匹配算法。首先，以改進的非線性慣性權(quán)重對粒子群算法進行優(yōu)化，以此來平衡粒子在全局和局部的搜索能力;其次，提出添加動態(tài)擾動項對速度進行擾動，避免粒子在算法后期速度停滯為零而陷入局部最優(yōu)。仿真結(jié)果表明，該算法提高了粒子的全局搜索能力和收斂精度，有效防止早熟現(xiàn)象，與基于標準的PSO圖像匹配算法相比，所提算法具有收斂速度快、魯棒性好以及匹配精度高的特點。

關(guān)鍵詞： 圖像匹配; 粒子群算法; 慣性權(quán)重; 速度擾動; 搜索速度; 收斂精度

中圖分類號： TN911.73?34; TP391 ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2018）10?0081?04

Abstract： In allusion to the problems that the particle swarm algorithm is prone to fall into local optimum， and has slow searching speed and low matching precision in image matching， a new image matching algorithm based on particle swarm optimization is proposed. The particle swarm algorithm is optimized by using the improved nonlinear inertia weight to balance the global and local searching capability of particles. The addition of the dynamic disturbance term is proposed to disturb the velocity so that the local optimum can be avoid when the velocity of particles falls to zero at the later stage of the algorithm. The simulation results show that this algorithm can improve the global searching capability and convergence precision of particles which can effectively prevent the premature phenomenon， and has the characteristics of faster convergence speed， better robustness， and higher matching precision in comparison with the standard PSO image matching algorithm.

Keywords： image matching; particle swarm algorithm; inertia weight; velocity disturbance; searching speed; convergence precision

0 ?引 ?言

圖像匹配[1?3]是計算機視覺和圖像處理中的一項重要技術(shù)，圖像匹配方法目前主要有兩大類：一類是基于灰度相關(guān)的匹配， 直接利用圖像的灰度進行匹配， 匹配率較高，但計量大，速度較慢;另一類是基于特征的匹配， 需先對 圖像提取特征，然后再對提取特征后的圖像進行匹配，一般匹配速度較快，但匹配精度不高。利用群體智能算法對圖像匹配算法進行優(yōu)化，以達到提高速度的目的，成為近年來圖像匹配算法領(lǐng)域研究的熱點。粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）作為一種群體智能算法，通過群體和個體之間的協(xié)作和信息共享來實現(xiàn)復(fù)雜空間最優(yōu)解的搜索，目前對PSO算法的改進已成為研究的熱點。吳潤秀等人提出了一種具有高斯擾動的局部引導(dǎo)粒子群優(yōu)化算法[4]，增加全局最優(yōu)粒子控制的高斯擾動項，提高了算法的全局搜索能力。Lu等人提出了通過引進收縮因子k對慣性權(quán)重進行調(diào)整的異步改進的粒子群算法[5]，提高了算法的穩(wěn)定性。文獻[6]提出一種新的鄰域拓撲結(jié)構(gòu)，降低粒子之間的聯(lián)系，減緩粒子向最優(yōu)粒子聚集的速度，提高了種群的多樣性。文獻[7]利用自組織層與時變加速系數(shù)對粒子群進行優(yōu)化，用于增強粒子的全局搜索能力。 Liu等人基于側(cè)抑制混沌研究粒子群優(yōu)化的圖像匹配[8]，將側(cè)抑制應(yīng)用于提取的邊緣圖像的銳化，能夠很好地突出原圖像的特征。但以上算法都存在匹配精度、收斂速度和魯棒性不能共存的問題?？紤]到粒子群算法在改進中存在的問題及其在圖像匹配中存在的缺陷，為了提高圖像匹配的精度和速度，本文提出基于慣性權(quán)重和帶有速度擾動項的粒子群算法的圖像匹配。所提算法以歸一化積相關(guān)函數(shù)作為適應(yīng)度函數(shù)，改進的慣性權(quán)重用于平衡全局和局部搜索能力，并添加速度擾動項保證粒子在搜索后期具有跳出局部最優(yōu)的能力，進而提高了算法的收斂速度、匹配精度和魯棒性。

3 ?仿真實驗

為了驗證本文提出的改進的粒子群（Improved Particle Optimization，IPOS）算法的有效性，測試環(huán)境為英特爾Pentium（奔騰） G645 @ 2.90 GHz雙核，Windows XP專業(yè)版。在Matlab中編寫程序，將本文算法與PSO圖像匹配算法的仿真結(jié)果進行對比，各項試驗參數(shù)如下：粒子數(shù)N為40，加速度因子C1=C2=2，最大迭代次數(shù)為80，[wmax=0.9]，[wmin=0.4]，理想適應(yīng)度值為1，實驗中取待匹配分辨率為512×512 的Lena圖像，以該圖坐標（200，200）為左上角，截取分辨率為100×100的子圖作為模板圖，即理想的匹配位置為（200，200）。新算法基本流程圖如圖1所示。

在無噪聲環(huán)境下，原圖像和模板圖分別如圖2a）、圖2b）所示，利用本文IPSO算法進行圖像匹配，實驗的匹配結(jié)果如圖2c）所示，圖中的綠色線框部分為模板圖，將圖2b）模板圖放在匹配位置時，圖像匹配邊緣銜接光滑，紋理自然完整，可以實現(xiàn)匹配位置的精確定位。

為了驗證IPSO算法的有效性，將IPSO算法的粒子迭代次數(shù)與適應(yīng)度值的關(guān)系仿真結(jié)果和PSO算法進行比較，實驗結(jié)果如圖3所示。由圖3可知，此次對PSO算法的測試在32代達到全局最優(yōu)，有4次陷入局部最優(yōu)解，而IPSO算法在第8代達到全局最優(yōu)解，即達到收斂的理想位置（200，200），沒有陷入局部最優(yōu)，之后，粒子的適應(yīng)度值曲線呈水平直線。對本文IPSO算法和PSO算法總共進行30次試驗，其性能如表1所示。

由表1可知，本文IPSO算法在匹配精度和搜索速度上比PSO算法性能更強。為了測試IPSO算法的魯棒性能，在Lena原圖像中加入均值為0，方差為0.008的Gaussian噪聲，如圖4a）所示。通過利用IPSO算法進行圖像匹配，實驗匹配結(jié)果如圖4b）所示。圖中的綠色線框部分為模板圖，見圖4c）。將圖4c）模板放入匹配位置時，圖像匹配邊緣銜接光滑，可以實現(xiàn)匹配位置的精確定位。

為了驗證IPSO算法在Gaussian噪聲下的魯棒性，將IPSO算法的粒子迭代次數(shù)與適應(yīng)度值的關(guān)系仿真結(jié)果和PSO算法進行比較，實驗結(jié)果如圖5所示。

由圖5可知，此次對PSO算法的測試在43代達到全局最優(yōu)，有6次陷入局部最優(yōu)解，而IPSO算法在第10代達到全局最優(yōu)，達到收斂的理想位置（200，200），僅有兩次很短的時間陷入局部最優(yōu)解，此后，粒子的適應(yīng)度值曲線呈水平直線。對本文IPSO算法和PSO算法總共進行30次試驗，其性能如表2所示。

由表2知，當原圖像受到噪聲環(huán)境干擾時，本文的IPSO算法依然能夠得到精確的匹配結(jié)果，并且在算法的搜索速度上依然大于PSO算法，驗證了本文算法具有較好的魯棒性。

4 ?結(jié) ?論

本文通過研究圖像匹配算法中PSO算法的不足，以提高算法的匹配精度、收斂速度以及抗干擾能力為研究目標，提出一種新的粒子群優(yōu)化的圖像匹配算法。新算法對粒子群算法的速度更新公式進行改進，使其具有跳出局部最優(yōu)進行全局搜索的能力。實驗仿真表明，在搜索速度和精度上，本文提出的算法比PSO算法顯著提升了性能，并且具有一定的抗干擾能力。

參考文獻

[1] 劉瑩，曹劍中，許朝暉，等. 基于灰度相關(guān)的圖像匹配算法的改進[J].應(yīng)用光學(xué)，2007，28（5）：536?540.

LIU Ying， CAO Jianzhong， XU Zhaohui， et al. Improvement of image matching algorithm based on gray correlation [J]. Journal of applied optics， 2007， 28（5）： 536?540.

[2] 陳麗芳，劉淵，須文波.改進的歸一互相關(guān)法的灰度圖像模板匹配方法[J].計算機工程與應(yīng)用，2011，47（26）：181?183.

CHEN Lifang， LIU Yuan， XU Wenbo. Improved normalized correlation method of gray image template matching method [J]. Computer engineering and applications， 2011， 47（26）： 181?183.

[3] ZHANG Yi， LU Kai， GAO Yinghui. Fast image matching algorithm based on affine invariants [J]. Journal of Central South University， 2014， 21（5）： 1907?1918.

[4] 吳潤秀，孫輝，朱德剛，等.具有高斯擾動的局部引導(dǎo)粒子群優(yōu)化算法[J].計算機工程與科學(xué)，2016，38（6）：1183?1192.

WU Runxiu， SUN Hui， ZHU Degang， et al. A particle swarm optimization algorithm based on local guidance and Gauss perturbation [J]. Computer engineering & science， 2016， 38（6）： 1183?1192.

[5] LU Y， LIANG M， YE Z， et al. Improved particle swarm optimization algorithm and its application in text feature selection [J]. Applied soft computing， 2015， 35（C）： 629?636.

[6] HUANG V L， SUGANTHAN P N， LIANG J J. Comprehensive learning particle swarm optimizer for solving multiobjective optimization problems [J]. International journal of intelligent systems， 2006， 21（2）： 209?226.

[7] RATNAWEERA A， HALGAMUGE S K， WATSON H C. Self?organizing hierarchical particle swarm optimizer with time?varying acceleration coefficients [J]. IEEE transactions on evolutionary computation， 2004， 8（3）： 240?255.

[8] LIU F， DUAN H， DENG Y. A chaotic quantum?behaved particle swarm optimization based on lateral inhibition for image matching [J]. International journal for light and electron optics， 2012， 123（21）： 1955?1960.

[9] 皮倩瑛，葉洪濤.一種動態(tài)調(diào)節(jié)慣性權(quán)重的粒子群算法[J].廣西科技大學(xué)學(xué)報，2016，27（3）：26?32.

PI Qianying， YE Hongtao. Particle swarm optimization algorithm for dynamic adjustment of inertia weight [J]. Journal of Guangxi University of Science and Technology， 2016， 27（3）： 26?32.

[10] 陳壽文.基于質(zhì)心和自適應(yīng)指數(shù)慣性權(quán)重改進的粒子群算法[J].計算機工程與應(yīng)用，2015，51（5）：58?64.

CHEN Shouwen. Improved particle swarm optimization algorithm based on centroid and self?adaptive exponential inertia weight [J]. Computer engineering and applications， 2015， 51（5）： 58?64.

[11] 謝承旺，鄒秀芬，夏學(xué)文，等.一種多策略融合的多目標粒子群優(yōu)化算法[J].電子學(xué)報，2015，43（8）：1538?1544.

XIE Chengwang， ZOU Xiufen， XIA Xuewen， et al. A multi?objective particle swarm optimization algorithm integrating multiply strategies [J]. Acta electronica sinica， 2015， 43（8）： 1538?1544.

[12] DAS S， KONAR A， CHAKRABORTY U K. Improving particle swarm optimization with differentially perturbed velocity [C]// Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation. Washington： ACM， 2005： 177?184.

[13] ZHAO Xinchao. A perturbed particle swarm algorithm for numerical optimization [J]. Applied soft computing， 2010， 10（1）： 119?124.

[14] LIAN K L， JHANG J H， TIAN I S. A maximum power point tracking method based on perturb?and?observe combined with particle swarm optimization [J]. IEEE journal of photovoltaics， 2014， 4（2）： 626?633.

[15] HAQ A N， KARTHIKEYAN K， SIVAKUMAR K， et al. Particle swarm optimization （PSO） algorithm for optimal machining allocation of clutch assembly [J]. International journal of advanced manufacturing technology， 2006， 27（9/10）： 865?869.

[16] PERLIN H A， CHIDAMBARAM C， LOPES H S. Template matching in digital images with swarm intelligence [J]. Encyclopedia information science and technology， 2015， 10： 1?9.

[17] GUO Y F， KAI H. Efficient image matching algorithm using distance transform and particle swarm optimization [J]. Advanced materials research， 2012， 341/342： 753?757.