馮 浩，李現(xiàn)偉

(1.宿州學(xué)院機(jī)械與電子工程學(xué)院，安徽宿州234000；2.早稻田大學(xué)國(guó)際情報(bào)通信研究科，東京169-8050)

基于改進(jìn)粒子群算法的圖像匹配技術(shù)研究

馮 浩1，李現(xiàn)偉2

(1.宿州學(xué)院機(jī)械與電子工程學(xué)院，安徽宿州234000；2.早稻田大學(xué)國(guó)際情報(bào)通信研究科，東京169-8050)

在分析基本粒子群優(yōu)化算法的基礎(chǔ)上，對(duì)學(xué)習(xí)因子進(jìn)行非線性異步策略調(diào)整，改變其固定常數(shù)模式，平衡算法在迭代過程中的局部和全局搜索能力；同時(shí)引入活力因子，對(duì)失活粒子執(zhí)行變異操作，提高種群多樣性。改進(jìn)算法可以提升對(duì)多維空間的全局尋優(yōu)能力，避免粒子產(chǎn)生早熟收斂現(xiàn)象。將改進(jìn)粒子群算法引入圖像匹配優(yōu)化問題中，提出了一種基于改進(jìn)粒子群算法的圖像匹配算法，實(shí)驗(yàn)結(jié)果表明，該算法具有更快的匹配速度以及更高的匹配精度，具有強(qiáng)魯棒性。

粒子群優(yōu)化算法；圖像匹配；學(xué)習(xí)因子；活力因子

D01∶10.19329/j.cnki.1673-2928.2016.06.008

引言

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，圖像匹配技術(shù)日漸趨于成熟。作為圖像處理的重要技術(shù)之一，圖像匹配在目標(biāo)識(shí)別、立體視覺、飛行器制導(dǎo)等領(lǐng)域得到較為廣泛的應(yīng)用[1]。目前針對(duì)圖像匹配方法的研究主要集中于匹配精度、匹配速度以及匹配算法的抗干擾性能等方面。

在圖像匹配過程中，特征空間、搜索策略以及相似性度量是其關(guān)鍵的三個(gè)要素。針對(duì)不同要素選擇合適的匹配方法，有利于提高圖像匹配的效率。本文以灰度值作為圖像匹配特征，同時(shí)將模板匹配與粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法相結(jié)合，在研究改進(jìn)PSO算法的基礎(chǔ)上，構(gòu)建基準(zhǔn)圖像與模板圖像之間的相似性度量數(shù)學(xué)模型，實(shí)現(xiàn)對(duì)目標(biāo)圖像的精確匹配。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的PSO算法提高了種群多樣性，具有更高的收斂精度和收斂速度，全局尋優(yōu)能力突出。在此基礎(chǔ)之上，改進(jìn)算法可以實(shí)現(xiàn)灰度圖像的快速匹配，其匹配精度、速度以及抗干擾性均優(yōu)于對(duì)比算法。

1 粒子群優(yōu)化(PSO)算法

PSO算法是由Kenndy博士和Eberhart博士于1995年提出，它是在研究鳥類群體覓食行為的基礎(chǔ)上所提出的一種群智能進(jìn)化算法，該算法通過模仿鳥群覓食，利用群體協(xié)作和信息共享找到食物最優(yōu)位置[2]。在PSO算法中，單個(gè)粒子代表搜索空間中的一個(gè)解，并且每個(gè)粒子都具有一定的飛行速度，則在D維空間中，假設(shè)種群大小為N，每個(gè)粒子的飛行速度可表示為vi=(vi1,vi2,···,vid)T，粒子的位置表示為xi=(xi1,xi2,···,xid)T，則第i個(gè)粒子根據(jù)式(1)、式(2)更新自身速度及位置[3]：

其中：i=1,2,···,N；d=1,2,···,D。w表示慣性權(quán)值，取值范圍為[0.4,0.9]；c1和c2表示學(xué)習(xí)因子，反映粒子個(gè)體極值和全局極值對(duì)下一狀態(tài)的影響；r1和r2為[0,1]之間的隨機(jī)數(shù)；k表示第k次迭代；在第k次迭代中，表示第i個(gè)粒子的飛行速度；表示第i個(gè)粒子的位置；表示第i個(gè)粒子的個(gè)體最優(yōu)位置；則表示整個(gè)粒子群的全局最優(yōu)位置。

2 改進(jìn)粒子群優(yōu)化算法

2.1 學(xué)習(xí)因子調(diào)整策略

由于基本PSO算法在迭代初期收斂速度較快，易產(chǎn)生早熟收斂現(xiàn)象，陷入局部極小，從而使得算法的收斂精度不高，全局尋優(yōu)能力較差。因此，國(guó)內(nèi)外大量研究學(xué)者對(duì)標(biāo)準(zhǔn)PSO算法做了改進(jìn)和優(yōu)化，如Shi等學(xué)者在文獻(xiàn)[4]中對(duì)慣性權(quán)值進(jìn)行線性調(diào)節(jié)；Clerc等學(xué)者在文獻(xiàn)[5]中提出帶收縮因子的PSO算法；姜長(zhǎng)元等人在文獻(xiàn)[6]中提出慣性權(quán)重正弦調(diào)整的粒子群算法；董平平等人在文獻(xiàn)[7]中提出一種改進(jìn)的自適應(yīng)慣性權(quán)值粒子群優(yōu)化算法等等，上述算法在收斂性能指標(biāo)上均有顯著提高。

大量實(shí)驗(yàn)表明，學(xué)習(xí)因子的非線性變化可以

更好地解決各種非線性優(yōu)化問題。本文在此基礎(chǔ)上對(duì)學(xué)習(xí)因子進(jìn)行非線性異步調(diào)整，主要思想是：在算法迭代過程中，學(xué)習(xí)因子c1隨迭代次數(shù)的增加進(jìn)行非線性遞減，而學(xué)習(xí)因子c2進(jìn)行非線性異步遞增。通過調(diào)整，使得粒子在算法初期的自身調(diào)節(jié)能力增強(qiáng)，種群多樣性增加；而在算法后期，粒子的協(xié)作能力逐步提升，社會(huì)經(jīng)驗(yàn)增強(qiáng)，有利于進(jìn)行全局最優(yōu)搜索。調(diào)整后的學(xué)習(xí)因子數(shù)學(xué)模型如下式所示：其中，α(k)表示如下：

實(shí)驗(yàn)證明，學(xué)習(xí)因子上下限在如下范圍內(nèi)變化，算法的收斂速度以及精度可得到較大提升。

2.2 活力因子的引入

本文在構(gòu)造學(xué)習(xí)因子策略模型的同時(shí)，對(duì)標(biāo)準(zhǔn)PSO算法作進(jìn)一步改進(jìn)。由PSO算法更新公式可知，當(dāng)粒子當(dāng)前位置逐步接近全局最優(yōu)位置，即二者距離趨于零時(shí)，粒子的飛行速度逐漸減小并趨于零，此時(shí)粒子運(yùn)動(dòng)活力降低，產(chǎn)生停滯現(xiàn)象；反之，二者距離越大，粒子飛行速度也隨之加快。因此，可以通過對(duì)粒子當(dāng)前位置進(jìn)行變異操作來更好地控制粒子飛行速度，從而增加種群多樣性，使粒子能夠跳出局部極值。為此，引入粒子活力因子σ（σ≥0），通過選擇合適的σ，使得當(dāng)粒子的當(dāng)前位置與全局最優(yōu)位置小于σ時(shí)，對(duì)當(dāng)前位置執(zhí)行變異操作，增強(qiáng)全局搜索能力。

在第k次迭代過程中，粒子i的當(dāng)前位置xi(k)和全局最優(yōu)位置pg(k)之間的距離定義為d(k)，其數(shù)學(xué)模型如下：

式（6）中，當(dāng)d(k)＜σ時(shí)，粒子的飛行速度將會(huì)以較大概率產(chǎn)生停滯現(xiàn)象，造成算法的陷入局部極值，此時(shí)，對(duì)粒子i的當(dāng)前位置xi(k)執(zhí)行變異操作，改變粒子的飛行方向，通過初始化當(dāng)前失活粒子的位置來增加種群多樣性，使粒子能夠以較大概率跳出局部最優(yōu)。

3 基于AMPSO算法的圖像匹配

3.1 圖像的模板匹配

由于模板匹配方法具有運(yùn)算簡(jiǎn)單、抗干擾性能強(qiáng)的優(yōu)點(diǎn)，已被廣泛應(yīng)用于圖像匹配技術(shù)。如圖1所示，模板匹配即是在待匹配的基準(zhǔn)圖像S中，搜索與模板T最為接近的目標(biāo)子圖Si,j的位置。其中，S大小為M×N，模板T大小為X×Y，i,j為目標(biāo)子圖左上角像素點(diǎn)在基準(zhǔn)圖S中的坐標(biāo)，i,j滿足1≤i≤M-X+1，1≤j≤N-Y+1。

圖1 基準(zhǔn)圖和模板圖

本文將改進(jìn)粒子群優(yōu)化算法與模板匹配方法進(jìn)行融合，則圖像的模板匹配可以轉(zhuǎn)化為運(yùn)用PSO算法在二維空間中搜索最優(yōu)匹配位置，基本流程如圖2所示。

圖2 基于AMPSO算法的圖像匹配流程圖

圖像的模板匹配算法較多，包括平均絕對(duì)差(Mean Absolute Difference，MAD)算法[8]、歸一化積相關(guān)(Normal Cross Correlation，NCC)算法[9]以及序貫相似性檢測(cè)法(Sequential Similarity Detection Algo?rithm，SSDA算法)[10]等?？紤]到匹配速度以及實(shí)現(xiàn)難度問題，本文選用MAD算法作為改進(jìn)PSO算法的適應(yīng)度評(píng)價(jià)函數(shù)。其數(shù)學(xué)公式如下：

式（7）中，d(x,y)表示當(dāng)偏移量為(x,y)時(shí)，所對(duì)應(yīng)的匹配度量值，當(dāng)d(x,y)取最小值時(shí)，可以得到最優(yōu)匹配位置(x,y)。

綜合以上分析，將基于改進(jìn)PSO算法的圖像匹配算法簡(jiǎn)稱為AMPSO算法。

3.2 實(shí)驗(yàn)仿真

在MATLAB7.0環(huán)境下進(jìn)行實(shí)驗(yàn)仿真，同時(shí)與傳統(tǒng)的模板匹配算法進(jìn)行對(duì)比分析，包括MAD算法以及NCC算法。實(shí)驗(yàn)選用Lena灰度圖像作為原始待匹配圖像，選取原始圖像大小254×254，待匹配模板大小為89×86，如圖3(a)和(b)所示。利用AMPSO算法對(duì)Lena原始圖像進(jìn)行匹配，在無(wú)噪聲環(huán)境下，其最佳匹配結(jié)果如圖3(c)所示。

圖3 原始圖像、模板圖像以及匹配結(jié)果

在AMPSO算法中，慣性權(quán)值w選擇線性遞減策略，其中wmax=0.9，wmin=0.4；設(shè)定學(xué)習(xí)因子上下限分別為，調(diào)節(jié)系數(shù)λ=10；活力因子σ根據(jù)實(shí)驗(yàn)情況以及經(jīng)驗(yàn)進(jìn)行相應(yīng)設(shè)置；設(shè)置種群大小為40，最大迭代次數(shù)M分別選擇30、40、50和60。實(shí)驗(yàn)次數(shù)為50次。分別與MAD算法以及NCC算法在平均運(yùn)行時(shí)間、正確匹配次數(shù)、最優(yōu)匹配位置、最差匹配位置以及匹配精度指標(biāo)上進(jìn)行對(duì)比，如表1所示。

由表1可以看出，當(dāng)最大迭代次數(shù)設(shè)置較小時(shí)，AMPSO算法的匹配精度無(wú)法達(dá)到100%，而當(dāng)最大迭代次數(shù)大于50時(shí)，算法的匹配精度可以得到保證；對(duì)于MAD算法和NCC算法，二者匹配精度均可以達(dá)到100%，表明這兩種算法具有較高的匹配率。同時(shí)，可以看出AMPSO算法在平均運(yùn)行時(shí)間指標(biāo)上明顯優(yōu)于MAD算法和NCC算法，特別是在保證匹配精度的前提下，AMPSO算法的平均運(yùn)行時(shí)間大約是MAD算法的1/16，是NCC算法的1/32，匹配速度明顯占優(yōu)。這也表明AMPSO算法具有快速收斂速度，同時(shí)，當(dāng)選擇適當(dāng)?shù)姆N群大小以及最大迭代次數(shù)時(shí)，算法的全局搜索能力會(huì)更加突出，在保證匹配速度的同時(shí)，可以有效提升圖像的匹配精度。

為測(cè)試AMPSO算法的抗干擾性能，在圖3(a)中加入15%的椒鹽噪聲，利用AMPSO算法對(duì)加噪后的Lena圖像進(jìn)行模板匹配，其最佳匹配結(jié)果如圖3(d)所示。大量實(shí)驗(yàn)證明，在選擇合適的種群規(guī)模以及迭代次數(shù)的前提下，AMPSO算法可以實(shí)現(xiàn)對(duì)加噪圖像的精確匹配。

同時(shí)，實(shí)驗(yàn)以加噪圖像作為基準(zhǔn)圖像，在模板圖像保持不變的前提下，將AMPSO算法和MAD算法以及NCC算法進(jìn)行圖像匹配對(duì)比分析。其中，AMPSO算法的種群大小選擇40，最大迭代次數(shù)選擇M=50，其他參數(shù)不變。實(shí)驗(yàn)次數(shù)50次。實(shí)驗(yàn)結(jié)果見表2所示。

表1 三種匹配算法的不同性能指標(biāo)比較

表2 加噪環(huán)境下三種匹配算法的性能比較

由表2可知，在加噪環(huán)境下，AMPSO算法的匹配速度優(yōu)勢(shì)明顯，耗時(shí)少。同時(shí)，AMPSO算法在匹配精度上也優(yōu)于對(duì)比算法，可以精確找到模板圖像的匹配位置坐標(biāo)，表現(xiàn)出較好的抗干擾性。

4 結(jié)束語(yǔ)

通過對(duì)基本PSO算法進(jìn)行改進(jìn)優(yōu)化，改變學(xué)習(xí)因子的固定模式，實(shí)現(xiàn)其非線性異步變化，同時(shí)引入活力因子，增加種群多樣性，使算法有效跳出局部極值，在提升收斂速度的同時(shí)，增強(qiáng)全局尋優(yōu)能力。將改進(jìn)PSO算法引入圖像匹配技術(shù)中，實(shí)驗(yàn)結(jié)果表明，改進(jìn)PSO算法可以在保證匹配速度的前提下，實(shí)現(xiàn)對(duì)目標(biāo)圖像的精確匹配，且抗干擾性能突出，具有強(qiáng)魯棒性，滿足實(shí)際應(yīng)用中對(duì)匹配速度和匹配精度的要求，在圖像匹配問題優(yōu)化方面具有一定的實(shí)際指導(dǎo)意義。

[1]劉佳，傅衛(wèi)平，王雯，等.基于改進(jìn)SIFT算法的圖像匹配[J].儀器儀表學(xué)報(bào)，2013（05）∶1107-1112.

[2]VANDEN BERGH F,ENGELBRECHT A P.Training Prod?uct Unit Networks Using Cooperative Particle Swarm Optimiza?tion[C]//IEEE International Joint Conference on Neural Net?works,Washington DC,USA,2001∶126-131.

[3]KENNEDY J,EBERHART R.Particle swarm optimization [C]//Proceedings of the 4th IEEE International Conference on NeuralNetworks.Piscataway,NJ∶IEEE ServiceCenter,1995∶1942-1948.

[4]SHI Y,EBERHART R.Empirical study of particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolu?tionary Computation,Piscataway,NJ∶IEEE press,1999∶1945-1950.

[5]CLERC M.The swarm and the queen∶towards a determin?stic and adaptive particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computation.Piscat?away,NJ∶IEEE Service Center,1999∶1951-1957.

[6]姜長(zhǎng)遠(yuǎn)，趙曙光，沈士根.慣性權(quán)值正弦調(diào)整的粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（8）∶40-42.

[7]董平平，高東慧,田羽波.一種改進(jìn)的自適應(yīng)慣性權(quán)值粒子群優(yōu)化算法[J].計(jì)算機(jī)仿真，2012，29（12）∶283-286.

[8]劉寶生，閆莉萍，周東華.幾種經(jīng)典相似性度量的比較研究[J].計(jì)算機(jī)應(yīng)用研究，2006（11）∶1-3.

[9]楊通鈺，彭國(guó)華.基于NCC的圖像匹配快速算法[J].現(xiàn)代電子技術(shù)，2010（22）∶107-109.

[10]王杉，陳翔，司寒羽.基于遙感圖像信息特征的單調(diào)遞增SSDA算法[J].華東交通大學(xué)學(xué)報(bào)，2013（01）∶15-21.

Image Matching Technology Based on Improved Particle Swarm Optimization Algorithm

FENG Hao1,LI Xianwei2
(1.Colloge of Mechanical and Electronic Engineering,Suzhou University,Suzhou AnHui 234000,China; 2.Global Information and Telecommunication Institute,Waseda University,Tokyo,169-8050,Japan)

Based on the analysis of the basic particle swarm optimization algorithm,the thesis adjusted the learn?ing factor by the strategy of nonlinear asynchronous,changed the model of fixed constant,and balanced the global and local search ability in the process of iteration;simultaneously the thesis introduced the activity factor to im?prove the population diversity which performed mutation for the particles who lost energy.The improved algorithm can improve the global search capability in the multidimensional space,and avoided premature convergence phe?nomenon.The improved particle swarm algorithm was introduced into image matching optimization problem,and proposed an image matching algorithm based on the improved particle swarm algorithm,the experimental results showed that The algorithm has the advantages of faster matching speed and higher matching accuracy,and has strong robustness.

particle swarm optimization algorithm;image matching;learning factor;activity factor

TP391

A

1673-2928（2016）06-0022-04

（責(zé)任編輯：郝安林）

2016-03-20

宿州學(xué)院一般科研項(xiàng)目(2014yyb03)、宿州學(xué)院科研平臺(tái)開發(fā)課題(2014YKF44)。

馮浩(1983-)，男，河南安陽(yáng)人，宿州學(xué)院講師，碩士，主要研究方向：圖像處理、智能算法。