馮 浩

宿州學(xué)院機(jī)械與電子工程學(xué)院，安徽宿州，234000

基于自適應(yīng)粒子群優(yōu)化的圖像匹配算法

馮 浩

宿州學(xué)院機(jī)械與電子工程學(xué)院，安徽宿州，234000

結(jié)合圖像匹配技術(shù)特點(diǎn)，引入粒子群優(yōu)化(PSO)算法，在此基礎(chǔ)上提出了一種基于自適應(yīng)粒子群優(yōu)化(APSO)的圖像匹配算法。該算法通過(guò)建立非線性遞減慣性權(quán)值動(dòng)態(tài)模型，并結(jié)合變異思想增加種群多樣性，實(shí)現(xiàn)對(duì)個(gè)體粒子進(jìn)行自適應(yīng)過(guò)濾，避免產(chǎn)生早熟收斂現(xiàn)象，降低局部極小的可能性，從而更好地優(yōu)化由局部到全局的開(kāi)放式搜索性能。將APSO算法運(yùn)用于圖像匹配過(guò)程中，可實(shí)現(xiàn)圖像的快速準(zhǔn)確匹配。實(shí)驗(yàn)結(jié)果表明，APSO算法能夠減少圖像匹配處理時(shí)間，并在匹配精度和抗干擾性能指標(biāo)上優(yōu)于對(duì)比算法。

圖像匹配；粒子群優(yōu)化算法；慣性權(quán)值；變異；自適應(yīng)

作為數(shù)字圖像處理和計(jì)算機(jī)視覺(jué)研究領(lǐng)域的重要技術(shù)之一的圖像匹配，在醫(yī)學(xué)圖像分析、衛(wèi)星遙感、目標(biāo)跟蹤、視覺(jué)數(shù)據(jù)挖掘、資源分析等領(lǐng)域均有廣泛的應(yīng)用[1]。圖像匹配是指將模板圖像與基準(zhǔn)圖像進(jìn)行匹配分析，并計(jì)算二者的相似度，從而達(dá)到圖像識(shí)別或定位的目的[2]。

目前常用的圖像匹配方法大致分為兩類(lèi)：一類(lèi)是基于特征的圖像匹配算法[3]，另一類(lèi)是基于灰度(像素灰度值)的圖像匹配算法[4]。第一類(lèi)算法主要是通過(guò)提取模板圖像和基準(zhǔn)圖像中的共有特征(包括點(diǎn)、線和面等匹配單元)，建立兩幅圖像的對(duì)應(yīng)關(guān)系，算法匹配速度較快，但是匹配精度不高，常用算法有Hausdorff距離匹配法、金字塔小波算法等。第二類(lèi)算法無(wú)需進(jìn)行圖像的特征點(diǎn)提取，該算法主要利用圖像的像素灰度值信息進(jìn)行匹配，通過(guò)一定的相似性度量準(zhǔn)則實(shí)現(xiàn)最優(yōu)匹配，其優(yōu)點(diǎn)是匹配精度高，缺點(diǎn)是匹配速度較慢，常用算法有平均絕對(duì)差(MAD)算法、歸一化互相關(guān)(NCC)算法以及序貫相似檢測(cè)(SSDA)算法等。另外，國(guó)內(nèi)外學(xué)者也提出多種圖像匹配智能優(yōu)化算法，包括模擬退火算法(SA)、遺傳算法(GA)[5]、自適應(yīng)遺傳算法(AGA)[6]等。其中，遺傳優(yōu)化算法具有非遍歷隨機(jī)搜索機(jī)制，可以代替?zhèn)鹘y(tǒng)的圖像匹配算法(SIFT算法等)，但是其適應(yīng)度受限較大，存在局部搜索能力不足的缺陷，容易陷入局部極小，產(chǎn)生早熟收斂現(xiàn)象。

本文在分析以上算法特點(diǎn)的基礎(chǔ)上，提出了一種基于自適應(yīng)粒子群優(yōu)化(Adaptive Particle Swarm Optimization，APSO)的圖像匹配算法。實(shí)驗(yàn)結(jié)果證明，該算法能夠使各粒子以較大概率跳出局部最優(yōu)，進(jìn)行全局最優(yōu)位置搜索，在保證匹配精準(zhǔn)率的前提下，實(shí)現(xiàn)圖像的最優(yōu)位置匹配。

1 自適應(yīng)粒子群優(yōu)化(APSO)算法

1.1 基本粒子群優(yōu)化算法

假設(shè)在D維空間中的某個(gè)群體由n個(gè)粒子組成，其中，用Xi=(xi1,xi2,…,xid)T表示第i個(gè)粒子在D維空間中的當(dāng)前位置；用Vi表示第i個(gè)粒子在D維空間中的飛行速度，記作Vi=(vi1,vi2,…,vid)T；用Pi=(Pi1,Pi2,…,Pid)T表示第i個(gè)粒子在D維空間中搜索到的最優(yōu)位置；整個(gè)粒子群在D維空間中搜索到的最優(yōu)位置用Pg=(Pg1,Pg2,…,Pgd)T表示。則基本粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法可以由以下更新迭代公式表示[7]：

(1)

(2)

其中，i=1,2,…,n；d=1,2,…,D。

1.2 自適應(yīng)粒子群優(yōu)化(APSO)算法

在基本PSO算法中，慣性權(quán)值、學(xué)習(xí)因子均為常數(shù)，而參數(shù)設(shè)置不同對(duì)算法影響較大，對(duì)于慣性權(quán)值ω的設(shè)置，較大的ω有助于加快算法收斂速度，而較小的ω有助于提高算法的收斂精度。本文結(jié)合標(biāo)準(zhǔn)PSO算法搜索進(jìn)程的非線性特點(diǎn)，改變慣性權(quán)值常用的遞減策略，隨著迭代次數(shù)的增加，建立慣性權(quán)值的自適應(yīng)調(diào)節(jié)模型，如式(3)所示：

ω=ωmax-(ωmax-ωmin)

(3)

其中，ωmax、ωmin分別為最大、最小慣性權(quán)值，一般取ωmax=0.9，ωmin=0.4；σ1、σ2為校準(zhǔn)系數(shù)，用于調(diào)節(jié)慣性權(quán)值的變化率；k表示粒子當(dāng)前迭代次數(shù)；kmax為最大迭代次數(shù)；該數(shù)學(xué)模型可限定慣性權(quán)值ω在(0.4,0.9)區(qū)間上進(jìn)行動(dòng)態(tài)調(diào)節(jié)。

為了進(jìn)一步降低局部極小的可能性，本文引入變異機(jī)制對(duì)粒子的最優(yōu)解進(jìn)行選擇過(guò)濾。

通過(guò)對(duì)算法初期的初始化粒子最優(yōu)值數(shù)據(jù)進(jìn)行衡量，計(jì)算粒子最優(yōu)適應(yīng)度值的平均值，并將其與每個(gè)粒子的最優(yōu)適應(yīng)度值進(jìn)行比較，若當(dāng)前粒子最優(yōu)位置值次于平均值，則對(duì)粒子的當(dāng)前位置進(jìn)行變異重生操作，反之則更新該粒子的當(dāng)前位置和速度。當(dāng)需要執(zhí)行變異時(shí)，對(duì)粒子當(dāng)前位置采用式(4)進(jìn)行重生。

(4)

其中，γ為(0,1)之間服從高斯分布的隨機(jī)數(shù)。

利用這種自適應(yīng)的變異機(jī)制，可以增加粒子的多樣性，加大算法跳出局部極小的幾率，避免產(chǎn)生早熟收斂現(xiàn)象，提升全局尋優(yōu)能力。

2 基于自適應(yīng)粒子群優(yōu)化(APSO)算法的圖像匹配

2.1 模板相關(guān)匹配

在圖像識(shí)別和處理方法中，模板相關(guān)匹配法被廣泛應(yīng)用于圖像匹配，其計(jì)算簡(jiǎn)單、容易實(shí)現(xiàn)且抗干擾性能強(qiáng)。設(shè)基準(zhǔn)圖像S大小為M×N，模板T大小為X×Y，待匹配的目標(biāo)子圖記為Si,j，i,j表示目標(biāo)子圖左上角像素點(diǎn)在基準(zhǔn)圖S中的坐標(biāo)，其中1≤i≤M-X+1,1≤j≤N-Y+1。

結(jié)合APSO算法的粒子化特點(diǎn)以及全局尋優(yōu)特性，模板匹配問(wèn)題可以轉(zhuǎn)化為利用APSO算法搜索目標(biāo)子圖Si,j位置的最優(yōu)解。在粒子位置和速度更新過(guò)程中，利用式(3)計(jì)算慣性權(quán)值ω，學(xué)習(xí)因子c1=c2=2。

選用平均絕對(duì)差(MAD)算法作為適應(yīng)度評(píng)價(jià)函數(shù)，該算法耗時(shí)少且易實(shí)現(xiàn)，公式如下：

(5)

式(5)中，d(x,y)為相似性度量函數(shù)，表示偏移量為(x,y)時(shí)所對(duì)應(yīng)的匹配度量值，其中1≤x≤M-X+1，1≤y≤N-Y+1。當(dāng)d(x,y)取最小值時(shí)，能夠得到最佳匹配位置(x,y)。

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

本文選取經(jīng)典圖像Lena作為實(shí)驗(yàn)仿真對(duì)象，其中Lena基準(zhǔn)圖像S大小為254×254，如圖1(a)所示；模板T大小為64×76，如圖1(b)所示。實(shí)驗(yàn)中選取粒子規(guī)模為50，最終的圖像匹配結(jié)果如圖1(c)所示。

圖1 基于APSO算法的圖像匹配結(jié)果

實(shí)驗(yàn)所用計(jì)算機(jī)配置如下：CPU：Intel Core i5-4590；主頻：3.3GHz；內(nèi)存：8G；仿真軟件：MATLAB 7.0。

本文選取APSO算法中的迭代次數(shù)分別為20、30、40和50，并與基于灰度的MAD算法、歸一化互相關(guān)(NCC)算法的運(yùn)行結(jié)果進(jìn)行對(duì)比，實(shí)驗(yàn)次數(shù)30次。實(shí)驗(yàn)結(jié)果如表1所示。

從表1對(duì)比結(jié)果可知，本文所設(shè)計(jì)的APSO算法匹配速度快，且表現(xiàn)出較好的匹配準(zhǔn)確率，其他兩種算法在匹配速度方面劣勢(shì)明顯，當(dāng)匹配精度同時(shí)達(dá)到100%時(shí)，APSO算法平均運(yùn)行時(shí)間是MAD算法的1/15左右、NCC算法的1/30左右。同時(shí)對(duì)于APSO算法，隨著迭代次數(shù)的遞增，匹配精度提高，但是算法的平均運(yùn)行時(shí)間也相應(yīng)增加。通過(guò)大量的實(shí)驗(yàn)分析發(fā)現(xiàn)，算法的迭代次數(shù)應(yīng)選取適當(dāng)，迭代次數(shù)過(guò)多會(huì)降低運(yùn)算效率，若過(guò)少則會(huì)影響匹配精度；對(duì)于粒子數(shù)目的選取亦應(yīng)適當(dāng)，粒子數(shù)目的多少直接影響算法的全局尋優(yōu)能力。

表1 APSO算法與MAD算法、NCC算法的匹配結(jié)果比較

為測(cè)試APSO算法的魯棒性能，本文在Lena基準(zhǔn)圖像S中加入了Gaussian噪聲(均值0，方差0.02)，如圖2(a)所示。通過(guò)利用APSO算法進(jìn)行圖像匹配，可以實(shí)現(xiàn)匹配位置的準(zhǔn)確定位。匹配結(jié)果如圖2(c)所示。

圖2 Gaussian噪聲下的APSO算法匹配結(jié)果

在Gaussian噪聲環(huán)境下，將APSO算法與MAD算法、NCC算法的運(yùn)行結(jié)果進(jìn)行對(duì)比，測(cè)試幾種算法的魯棒性能。其中，選取APSO算法的粒子規(guī)模為50，最大迭代次數(shù)為40，實(shí)驗(yàn)次數(shù)30次。結(jié)果如表2所示。

表2 加噪環(huán)境下幾種算法的魯棒性能比較

由表2可知，APSO算法在噪聲環(huán)境下能夠準(zhǔn)確無(wú)誤地找到匹配位置，抗干擾能力突出，具有強(qiáng)魯棒性。同時(shí)在運(yùn)行速度方面具有較大優(yōu)勢(shì)，匹配速度更快。

在無(wú)噪聲環(huán)境下，本文對(duì)模板T的大小進(jìn)行隨機(jī)更改，并將APSO算法與MAD算法、NCC算法在平均運(yùn)行時(shí)間方面進(jìn)行比較。實(shí)驗(yàn)中選取APSO算法的粒子規(guī)模為50，最大迭代次數(shù)為40，實(shí)驗(yàn)次數(shù)為30。結(jié)果如表3所示。

表3 不同模板下幾種算法的平均運(yùn)行時(shí)間比較 s

算法模板T1/30×33模板T2/76×64模板T3/97×91APSO算法0.250.340.58MAD算法6.025.377.24NCC算法16.8510.3311.27

由表3可知，在不同模板大小下，APSO算法的平均運(yùn)行時(shí)間均小于其他兩種算法，匹配速度更快。同時(shí)，APSO算法的運(yùn)算時(shí)間與模板大小成正比，模板越小，匹配速度越快，反之速度減慢；而另外兩種算法在模板過(guò)大或過(guò)小的情況下，運(yùn)行時(shí)間均會(huì)增加，相應(yīng)降低了圖像匹配過(guò)程。

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

本文通過(guò)對(duì)粒子群優(yōu)化(PSO)算法的分析研究，提出了一種基于自適應(yīng)粒子群優(yōu)化(APSO)算法。實(shí)驗(yàn)證明該算法具有較好的收斂速度以及更高的收斂精度，能夠跳出局部極小，避免早熟收斂現(xiàn)象，增強(qiáng)全局尋優(yōu)能力，在圖像匹配方面具有更好的匹配速度和匹配精度，且具有強(qiáng)魯棒性，表現(xiàn)出較好的性能。算法后期將以參數(shù)優(yōu)化、算法融合作為改進(jìn)方向，同時(shí)將改進(jìn)后的算法應(yīng)用于其他圖像處理技術(shù)之中。

[1]Guo X,Wang W.Image matching algorithm based on subdivision wavelet and local projection entropy[C]//The 6th World congress on Intelligent Control and Automation.Dalian China,2006:10380-10383

[2]伍慶華，王典洪，顏雪松．一種用于圖像匹配的演化算法研究[J]．計(jì)算機(jī)工程與應(yīng)用，2010，46(23)：181-184

[3]曹耀輝．一種圖像高精度匹配算法[J]．計(jì)算機(jī)仿真，2009，26(9)：203-206

[4]羅鐘鉉，劉成明．灰度圖像匹配的快速算法[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17(5)：966-970

[5]Chalermwat P,Ei G T,Le Moigne J.Two-phase genetic algorithm-based imageregistration on parrallel clusters[J].Journal of Future Generation Computing Systems,2001,17(3):467-476

[6]鄭軍，諸靜．基于自適應(yīng)遺傳算法的圖像匹配[J]．浙江大學(xué)學(xué)報(bào):工學(xué)版，2003，37(6)：61-64

[7]鹿艷晶，馬苗．基于灰色粒子群優(yōu)化的快速圖像匹配算法[J]．計(jì)算機(jī)工程與應(yīng)用，2009，45(10)：157-167

[8]Garnier S,Gautrais J,Theraulaz G.The biological principles of swarm intelligence[J].Swarm Intelligence,2007(1):3-31

(責(zé)任編輯：汪材印)

10.3969/j.issn.1673-2006.2015.11.025

2015-08-01

宿州學(xué)院一般科研項(xiàng)目“瑞利衰落環(huán)境下的頻譜檢測(cè)方法研究”(2014yyb03)；宿州學(xué)院科研平臺(tái)開(kāi)發(fā)課題“基于可信計(jì)算的無(wú)線局域網(wǎng)安全體系結(jié)構(gòu)的研究”(2014YKF44)。

馮浩(1983-)，河南安陽(yáng)人，碩士，助教，主要研究方向:圖像處理、智能算法。

TP391

A

1673-2006(2015)11-0098-04