張煥龍， 張秀嬌， 賀振東， 張建偉

(1.鄭州輕工業(yè)學(xué)院 電氣信息工程學(xué)院 河南 鄭州 450002； 2.鄭州輕工業(yè)學(xué)院 軟件學(xué)院 河南 鄭州 450002)

DOI: 10.13705/j.issn.1671-6841.2017192

基于布谷鳥(niǎo)搜索的圖像匹配方法研究

張煥龍1， 張秀嬌1， 賀振東1， 張建偉2

(1.鄭州輕工業(yè)學(xué)院 電氣信息工程學(xué)院 河南 鄭州 450002； 2.鄭州輕工業(yè)學(xué)院 軟件學(xué)院 河南 鄭州 450002)

針對(duì)傳統(tǒng)群智能方法在圖像匹配應(yīng)用中參數(shù)較多且調(diào)節(jié)復(fù)雜的問(wèn)題，將布谷鳥(niǎo)搜索(cuckoo search，CS)機(jī)制引入到圖像匹配過(guò)程．CS方法具有較少的模型參數(shù)、簡(jiǎn)單的調(diào)節(jié)方式，因此圖像匹配效果獲得了較大的提高．該方法首先將目標(biāo)匹配過(guò)程轉(zhuǎn)化為對(duì)組合優(yōu)化問(wèn)題的求解；然后通過(guò)提取圖像塊的方向梯度直方圖(histogram of oriented gradient, HOG)，實(shí)現(xiàn)目標(biāo)的全局性特征匹配；最后通過(guò)仿真實(shí)驗(yàn)，證明了CS方法在圖像匹配應(yīng)用中的可行性和有效性．

圖像匹配； CS算法； HOG； 最優(yōu)解

DOI: 10.13705/j.issn.1671-6841.2017192

0 引言

圖像匹配是指在一幅未知圖像中搜尋與已知目標(biāo)圖像相似區(qū)域的過(guò)程，目前已成功地應(yīng)用到計(jì)算機(jī)視覺(jué)、醫(yī)學(xué)圖像和遙感圖像等多個(gè)領(lǐng)域．一般實(shí)現(xiàn)圖像匹配的研究方法有很多，其中基于灰度信息和基于特征信息的研究方法受到較多關(guān)注．前種方法實(shí)現(xiàn)簡(jiǎn)單，精確度較高[1-3]，采用像素值矩陣進(jìn)行匹配，數(shù)據(jù)維數(shù)高，計(jì)算代價(jià)大．后種方法采用目標(biāo)特征進(jìn)行匹配[4-5]，數(shù)據(jù)維數(shù)減少，運(yùn)算量有所降低．但這兩種方法均采用窮盡式搜索策略，匹配效率較低.為此，文獻(xiàn)[6-8]分別采用圖像塊編碼、特征描述算子和金字塔分層匹配等方法，以提高圖像匹配的效率．

上述研究方法在一定程度上提高了圖像匹配算法的效率，但遍歷式的搜索策略，產(chǎn)生了大量的匹配點(diǎn)對(duì)，使匹配效率難以再次提高．近年來(lái)，研究者嘗試將群優(yōu)化算法引入到圖像匹配領(lǐng)域，相比于其他方法，群優(yōu)化算法的非遍歷搜索方式，減少了匹配圖像塊的數(shù)量和計(jì)算量，且具有較好的魯棒性，獲得了更優(yōu)的匹配效果．文獻(xiàn)[9]利用蟻群算法的聚類特性，將各像素進(jìn)行聚類，設(shè)置聚類中心，以減少搜索時(shí)間，提高了匹配效率.文獻(xiàn)[10]將改進(jìn)后的粒子群算法(particle swarm optimization, PSO)與歸一化互相關(guān)算法(normalized cross correlation,NCC)結(jié)合，提出將匹配區(qū)域分割，在每個(gè)分割區(qū)域內(nèi)分配粒子群并行尋找最優(yōu)解，并使用禁忌搜索和加入隨機(jī)擾動(dòng)算子的改進(jìn)，使匹配精度、速度和抗噪性能都有提高．

雖然這些群優(yōu)化算法取得了較好的效果，但都存在參數(shù)較多，難以調(diào)節(jié)的缺點(diǎn)．CS算法是一種較新穎的群優(yōu)化算法，具有搜索能力強(qiáng)、調(diào)節(jié)參數(shù)少的優(yōu)點(diǎn)，并采用Lévy飛行的隨機(jī)游走與發(fā)現(xiàn)概率隨機(jī)游動(dòng)相結(jié)合的搜索方式，能夠?qū)崿F(xiàn)全局最優(yōu)化．目前CS算法已應(yīng)用于圖像的很多領(lǐng)域[11-13]，本文將詳細(xì)介紹基于CS算法的圖像匹配方法，該方法把圖像匹配看作一個(gè)優(yōu)化問(wèn)題，采用優(yōu)化策略完成匹配．

1 CS算法介紹

CS算法是文獻(xiàn)[14]提出的一種仿生智能算法，其思想源于對(duì)布谷鳥(niǎo)寄生育雛行為以及果蠅覓食Lévy飛行行為的模擬．CS算法中，假設(shè)在固定數(shù)量的鳥(niǎo)巢中，每只布谷鳥(niǎo)隨機(jī)選取一個(gè)鳥(niǎo)巢，每次下一個(gè)蛋(稱為寄生蛋)，并保留適應(yīng)度最好的鳥(niǎo)巢至下一代，其他鳥(niǎo)巢根據(jù)Lévy飛行的隨機(jī)搜索路徑，產(chǎn)生新的鳥(niǎo)巢．根據(jù)發(fā)現(xiàn)概率Pa(Pa∈[0,1])，一些寄生蛋會(huì)被宿主鳥(niǎo)發(fā)現(xiàn)，此時(shí)宿主鳥(niǎo)將寄生蛋移出鳥(niǎo)巢或遺棄當(dāng)前鳥(niǎo)巢，建立新的鳥(niǎo)巢，則布谷鳥(niǎo)重新尋找下一個(gè)鳥(niǎo)巢產(chǎn)蛋．

1.1 初始化CS算法參數(shù)

CS算法的第一步是設(shè)置參數(shù)，主要包括初始鳥(niǎo)巢數(shù)量n，發(fā)現(xiàn)概率Pa以及停止條件．

1.2 生成初始鳥(niǎo)巢

x(i)=round(M*rand)，

(1)

y(i)=round(N*rand)，

(2)

其中：x(i)、y(i)分別為鳥(niǎo)巢初始位置的x坐標(biāo)和y坐標(biāo)；M、N為鳥(niǎo)巢位置的邊界值；rand為[0,1]的隨機(jī)數(shù)；round為取整函數(shù)．初始鳥(niǎo)巢的位置可由式(1)和(2)隨機(jī)分配得到.

1.3 Lévy飛行產(chǎn)生新鳥(niǎo)巢

在Lévy飛行中，較小步長(zhǎng)的短距離行走與偶爾較大步長(zhǎng)的長(zhǎng)距離行走相互交替.搜索前期，大步長(zhǎng)用于探索發(fā)現(xiàn)，有利于擴(kuò)大搜索范圍，搜索后期，小步長(zhǎng)使得群體在小范圍內(nèi)收斂于全局最優(yōu)解．Lévy飛行搜索路徑的公式為

⊕L(λ)，

(3)

(4)

1.4 寄生蛋被發(fā)現(xiàn)

根據(jù)發(fā)現(xiàn)概率Pa，當(dāng)P=randgt;Pa時(shí)，表示寄生蛋被發(fā)現(xiàn)，則更新鳥(niǎo)巢的路徑為

(5)

2 基于CS算法的圖像匹配

圖像匹配的過(guò)程中，特征表示、搜索策略以及相似性度量是其關(guān)鍵的3個(gè)要素．基于CS算法的圖像匹配可以看作，在待匹配圖像中以CS算法搜索候選圖像，使用特征描述方法表示目標(biāo)或候選圖像塊，并用相似度量函數(shù)測(cè)量候選圖像塊與目標(biāo)的相似程度，保留每次與目標(biāo)相似度值最大的候選圖像塊，直到達(dá)到停止條件，此時(shí)最大相似度值所對(duì)應(yīng)的圖像塊即為匹配目標(biāo)．

2.1 特征提取

HOG特征是邊緣的結(jié)構(gòu)特征，能夠很好地描述圖像局部的形狀信息．HOG特征將位置和方向量化為梯度幅值和方向，從而對(duì)圖像的平移和旋轉(zhuǎn)活動(dòng)都具有適應(yīng)性，且對(duì)光照變化具有魯棒性，因此本文使用HOG特征作為目標(biāo)或候選圖像塊的特征描述，像素點(diǎn)(x,y)處的梯度幅值m(x,y)和梯度方面θ(x,y)為：

(6)

(7)

式中Gx、Gy分別表示水平方向和豎直方向的梯度．首先，依據(jù)式(6)和(7)計(jì)算目標(biāo)或候選圖像塊中每個(gè)像素的梯度幅值和方向.然后，將目標(biāo)或候選圖像塊均勻地劃分成多個(gè)單元圖像塊(CELL)，梯度方向分為9個(gè)BIN，統(tǒng)計(jì)其梯度方向直方圖，得到CELL的HOG特征．相鄰的CELL組成一個(gè)BLOCK，將BLOCK歸一化得到BLOCK的HOG特征．統(tǒng)計(jì)BLOCK的梯度方向直方圖，完成圖像塊的特征提取．

2.2 相似度測(cè)量

相似度函數(shù)是為了測(cè)量目標(biāo)圖像塊的HOG特征與候選圖像塊的HOG特征的相似或相關(guān)程度．我們使用相關(guān)系數(shù)來(lái)衡量它們的相似程度，假設(shè)X代表目標(biāo)圖像塊的HOG特征，Y代表候選圖像塊的HOG特征，用

運(yùn)算關(guān)系來(lái)計(jì)算它們的相關(guān)系數(shù)，其中：D(·) 代表方差；cov(·) 代表協(xié)方差；ρ(X,Y)的取值范圍是[-1,1]，當(dāng)ρ(X,Y) 的絕對(duì)值越大，說(shuō)明X與Y相關(guān)度越高，目標(biāo)圖像塊與候選圖像塊的相似性就越大，反之，則相似性就越?。?/p>

2.3 基于CS算法的圖像匹配

基于CS算法的圖像匹配有幾個(gè)主要組成部分：產(chǎn)生初始候選圖像塊并提取特征，計(jì)算候選圖像塊與目標(biāo)的相似度值，找出相似度值最大的圖像塊并保存；依據(jù)Lévy飛行公式產(chǎn)生候選圖像塊，與初始候選圖像塊的相似度對(duì)比，保留兩者中相似度較大的圖像塊，在所有保留下來(lái)的圖像塊中找出相似度最大的圖像塊并保存；根據(jù)發(fā)現(xiàn)概率，隨機(jī)更新圖像塊，并保存更新后與目標(biāo)最相似的圖像塊．基于CS算法的圖像匹配方法如算法1所示.

算法1 基于CS的圖像匹配方法Algorithm．1 Image matching method based on CS

基于CS算法的圖像匹配，從優(yōu)化問(wèn)題的角度出發(fā)，利用CS算法的局部搜索和全局搜索相結(jié)合的搜索方式，使候選目標(biāo)圖像塊收斂至全局最優(yōu)，實(shí)現(xiàn)圖像匹配．

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)運(yùn)行環(huán)境：CPU為Intel 酷睿i3 M380；2.53 GHz；內(nèi)存為2 GB；操作系統(tǒng)是Windows XP. 軟件平臺(tái)是Matlab R2010b．實(shí)驗(yàn)圖像大小為320×240，選取圖中以79行，76列為左上點(diǎn)坐標(biāo)，大小為64×52的圖像塊為模板圖像．

3.1 參數(shù)選擇

為了獲得較好的匹配參數(shù)，以一幀400×704的圖像為原始圖像，取圖中以309行，23列為左上點(diǎn)的坐標(biāo)，大小為95×65的圖像塊為模板圖像，如圖1(a)為原始圖像，圖1(b)模板圖像．由式(4)可知a通常取值為0.01，為了獲得較好的匹配效果，我們將對(duì)其進(jìn)行調(diào)整．本文中，我們將算法的停止條件設(shè)置為迭代次數(shù)K=100時(shí)即停止，設(shè)置初始圖像塊數(shù)量n=250，并在此環(huán)境下對(duì)Lévy步長(zhǎng)a和發(fā)現(xiàn)概率Pa進(jìn)行調(diào)整．

圖1 匹配結(jié)果Fig．1 Matching result

為了確定發(fā)現(xiàn)概率Pa，在上述環(huán)境下，設(shè)定Lévy步長(zhǎng)a=0.1，將發(fā)現(xiàn)概率Pa分別設(shè)置為0.1、0.3、0.5、0.7，每次實(shí)驗(yàn)30次，比較它們的平均運(yùn)行時(shí)間、正確匹配次數(shù)、最優(yōu)匹配位置、最差匹配位置、匹配成功概率以及最大歐式距離，如表1所示．當(dāng)Pa分別為0.3、0.5、0.7時(shí)，其正確匹配次數(shù)幾乎一樣，即當(dāng)Pa≥0.3時(shí)，Pa的值對(duì)成功匹配次數(shù)的影響已經(jīng)基本不變，再比較3種情況下的平均運(yùn)行時(shí)間和最大歐氏距離可以看出，當(dāng)Pa為0.5時(shí)，其平均運(yùn)行時(shí)間雖然比Pa為0.7時(shí)慢了4 s，但比較它們的最大歐氏距離可以看出，Pa為0.5時(shí)的匹配精度比Pa為0.7時(shí)高很多，綜合考慮，我們選擇Pa=0.5．

表1 不同發(fā)現(xiàn)概率實(shí)驗(yàn)結(jié)果 Tab．1 Experimental results with different discovery probability

為了確定Lévy步長(zhǎng)a，在初始圖像塊數(shù)量n和迭代次數(shù)K不變的情況下，發(fā)現(xiàn)概率取Pa=0.5，將步長(zhǎng)a分別設(shè)置為0.08、0.2、0.5、0.7，針對(duì)每個(gè)步長(zhǎng)a分別實(shí)驗(yàn)30次，得到表2．由表2可知，當(dāng)a為0.5或0.7時(shí)，可實(shí)現(xiàn)30次的完全最優(yōu)匹配．一般來(lái)說(shuō)，步長(zhǎng)越大，匹配速度越快，但在此環(huán)境下，a為0.5和0.7時(shí)，運(yùn)行時(shí)間基本一致，為避免步長(zhǎng)過(guò)大而錯(cuò)過(guò)最優(yōu)解，我們?nèi)=0.5．其最優(yōu)匹配結(jié)果如圖1(c)所示．

表2 不同步長(zhǎng)實(shí)驗(yàn)結(jié)果

3.2實(shí)驗(yàn)結(jié)果與分析

由參數(shù)選擇部分我們得出，設(shè)定初始圖像塊數(shù)量n=250，迭代次數(shù)K=100，Lévy步長(zhǎng)a=0.5，發(fā)現(xiàn)概率Pa=0.5，可獲得較好的匹配結(jié)果，我們采用這組參數(shù)作為實(shí)驗(yàn)參數(shù)．

此次實(shí)驗(yàn)，為了說(shuō)明文中方法的可行性，在同樣環(huán)境下，使用基于粒子群(PSO)的匹配算法、基于模擬退火(simulated annealing, SA)的匹配算法以及文中方法對(duì)原圖像進(jìn)行匹配，并觀察實(shí)驗(yàn)結(jié)果.為了測(cè)試算法的抗干擾性能，再次實(shí)驗(yàn)時(shí)，原圖像中加入均值為0、方差為0.01的高斯噪聲，比較3種方法的匹配結(jié)果．

表3 不同匹配方法實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)一原始圖像和模板圖像質(zhì)量較好,不存在噪聲干擾．

原始圖像如圖2(a)，模板圖像如圖2(b)，文中方法實(shí)現(xiàn)匹配效果圖如圖2(c)．將本文方法與基于PSO的匹配方法、基于SA的匹配方法結(jié)果進(jìn)行比較，表3為3種匹配方法的性能比較．由表3可以看出，在原圖像未加入噪聲的匹配環(huán)境下,文中方法可較好地實(shí)現(xiàn)匹配．從匹配精度上來(lái)說(shuō)，文中方法雖然在時(shí)間上落后于基于PSO的匹配方法，但是在匹配精度上卻有明顯的優(yōu)勢(shì)．基于PSO的匹配方法，以PSO算法為搜索策略，在迭代初期收斂速度較快，易產(chǎn)生早熟收斂現(xiàn)象，陷入局部極小，從而使得算法的收斂精度不高，全局尋優(yōu)能力較差．而文中方法使用CS算法為搜索策略，利用其局部搜索與全局搜索相結(jié)合的搜索方式，搜索過(guò)程中更容易跳出局部最優(yōu)解，收斂至全局最優(yōu)，從而實(shí)現(xiàn)精確匹配.從匹配速度來(lái)說(shuō)，雖然文中方法與基于SA的匹配方法都達(dá)到了匹配精度，但在匹配速度上文中方法提升了50%．基于SA的匹配方法，使用SA算法作為搜索策略，其單個(gè)初始退火點(diǎn)，使得算法的收斂速度慢，CS算法初始化較多的圖像塊數(shù)量，可同時(shí)搜索候選圖像塊，加快了搜索速度．

圖2 圖像匹配結(jié)果Fig．2 Image matching results

實(shí)驗(yàn)二模板圖像質(zhì)量較好，原始圖像加入高斯噪聲．

圖3(a)為加入噪聲后的原始圖像，圖3(b)為加入噪聲后的匹配效果圖，比較3種方法的匹配結(jié)果，可得出表4．由表4我們看出，在加入噪聲干擾的情況下，文中方法和基于PSO的匹配方法在運(yùn)行時(shí)間上幾乎沒(méi)有變化，但在匹配精度上文中算法仍然保持著最優(yōu)匹配．基于SA的匹配雖保證了精度，在匹配時(shí)間上增加了4 s．實(shí)驗(yàn)結(jié)果表明，文中方法在圖像匹配中具有一定的抗干擾性，是一種穩(wěn)健的匹配算法．

表4加入噪聲的實(shí)驗(yàn)結(jié)果

Tab．4Experimental results with noise

算法名稱匹配位置匹配時(shí)間/s原始位置歐氏距離PSO匹配(78,77)20(76,79)2.8SA匹配(76,79)68(76,79)0文中方法(76,79)32(76,79)0

圖3 加噪后匹配結(jié)果Fig．3 Matching results with noise

以上實(shí)驗(yàn)，分別從匹配精度和匹配速度以及抗干擾3個(gè)方面表明了文中算法的有效性和可行性．

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

本文將CS算法引入圖像匹配問(wèn)題，以HOG特征提取為輸入特征方法，以相關(guān)系數(shù)為相似度量函數(shù)，以CS算法為搜索策略，彌補(bǔ)了傳統(tǒng)群智能優(yōu)化算法在圖像匹配中參數(shù)多、難以調(diào)節(jié)的缺點(diǎn)，通過(guò)求解全局最優(yōu)解實(shí)現(xiàn)了在較少調(diào)節(jié)參數(shù)下的圖像匹配，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了文中方法的有效性．但CS算法固定的參數(shù)設(shè)置使算法缺少靈活性，未來(lái)的工作我們將針對(duì)CS算法在圖像匹配領(lǐng)域的參數(shù)進(jìn)行自適應(yīng)設(shè)計(jì)．

[1] 張煥龍，鄭衛(wèi)東，舒云星.基于增量式互信息的圖像快速匹配方法[J].彈箭與制導(dǎo)學(xué)報(bào)，2015，35(1)：135-138.

[2] 曹茂永，高煒，鄧兆鵬，等.基于前視鉆孔攝像提取全景圖像的方法[J].鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2017，49(2)：78-82.

[3] 曾凡永，顧愛(ài)輝，陳海峰，等.相關(guān)系數(shù)和最小二乘影像匹配算法的實(shí)現(xiàn)與研究[J]. 水利與建筑工程學(xué)報(bào)，2015，13(6)：203-208.

[4] 張震，邵星星.一種SIFT虹膜匹配算法[J].鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2017，49(3)：14-19.

[5] RUBLEE E，RABAUD V，KONOLIGE K，et al.ORB: An efficient alternative to SIFT or SURF [C]//Computer Vision (ICCV).Barcelona，2011：2564-2571.

[6] 李強(qiáng)，張鈸．一種基于圖像灰度的快速匹配算法[J].軟件學(xué)報(bào)，2006，17(2)：216-222.

[7] 唐永鶴，陶華敏，盧煥章，等.一種基于Harris算子的快速圖像匹配算法[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2012，37(4)：406-409.

[8] 吳鵬．結(jié)合小波金字塔的快速 NCC 圖像匹配算法[J]．哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2017，38(5)：1-8.

[9] 石鴻雁，貝肇宇．基于蟻群算法的圖像匹配方法[C]//中國(guó)控制與決策會(huì)議(CCDC).桂林，2009：3888-3891.

[10] 楊昆，張明新，劉永俊．基于優(yōu)化粒子群的NCC模板匹配算法[J].計(jì)算機(jī)應(yīng)用與軟件，2015，32(8)：162-165.

[11] GAO M L，YIN L J，ZOU G F，et al.Visual tracking method based on cuckoo search algorithm[J].Optical engineering，2015，54(7):073105．

[12] 蒲國(guó)林，衛(wèi)洪春，向偉.基于混合ABC-CS算法的彩色圖像多閾值分割[J].計(jì)算機(jī)與數(shù)字工程，2016，44 (7)：1323-1326.

[13] 陳娜．基于改進(jìn)布谷鳥(niǎo)算法的圖像配準(zhǔn)和融合中的參數(shù)優(yōu)化[D].保定：河北大學(xué)，2016.

[14] YANG X S, DEB S. Cuckoo search via Lévy flights [C]//Nature amp; Biologically Inspired Computing.Coimbatore，2009：210-214.

(責(zé)任編輯：方惠敏)

TheStudyonImageMatchingMethodBasedonCuckooSearch

ZHANG Huanlong1, ZHANG Xiujiao1, HE Zhendong1, ZHANG Jianwei2

(1.CollegeofElectricandInformationEngineering,ZhengzhouUniversityofLightIndustry,Zhengzhou450002,China; 2.CollegeofSoftwareEngineering,ZhengzhouUniversityofLightIndustry,Zhengzhou450002,China)

Aiming to solve the problem that the traditional swarm optimization algorithm has parameters in image matching. A swarm optimization algorithm based on cuckoo search (CS) for image matching was introduced. Fewer parameters and simpler adjustion were used in CS to image matching. The image matching was firstly transformed to solve a combinatorial optimization problem. Then, by extracting the gradient feature of the image block, the global image matching was realized. Finally, the feasibility and validity of the proposed method were demonstrated by the experiments.

image matching; CS algorithm; HOG; optimal solution

2017-07-03

國(guó)家自然科學(xué)基金項(xiàng)目(61503173,61672471,61501407)；河南省科技攻關(guān)項(xiàng)目(172102210062，162102210060)；鄭州輕工業(yè)學(xué)院博士基金項(xiàng)目(2016BSJJ002)；河南省杰出青年基金項(xiàng)目(164100510019)．

張煥龍(1981—)，男，河南靈寶人，副教授，主要從事圖像處理與模式識(shí)別研究，E-mail：zhl_lit@163.om；通信作者：張建偉(1971—)，男，河南南陽(yáng)人，教授，主要從事網(wǎng)絡(luò)安全與智能信息處理研究，E-mail:2453651858@qq.com

TP391

A

1671-6841(2017)04-0051-06