基于布谷鳥搜索的圖像匹配方法研究

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

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

DOI: 10.13705/j.issn.1671-6841.2017192

基于布谷鳥搜索的圖像匹配方法研究

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

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

針對傳統群智能方法在圖像匹配應用中參數較多且調節復雜的問題，將布谷鳥搜索(cuckoo search，CS)機制引入到圖像匹配過程．CS方法具有較少的模型參數、簡單的調節方式，因此圖像匹配效果獲得了較大的提高．該方法首先將目標匹配過程轉化為對組合優化問題的求解；然后通過提取圖像塊的方向梯度直方圖(histogram of oriented gradient, HOG)，實現目標的全局性特征匹配；最后通過仿真實驗，證明了CS方法在圖像匹配應用中的可行性和有效性．

圖像匹配； CS算法； HOG； 最優解

DOI: 10.13705/j.issn.1671-6841.2017192

0 引言

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

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

雖然這些群優化算法取得了較好的效果，但都存在參數較多，難以調節的缺點．CS算法是一種較新穎的群優化算法，具有搜索能力強、調節參數少的優點，并采用Lévy飛行的隨機游走與發現概率隨機游動相結合的搜索方式，能夠實現全局最優化．目前CS算法已應用于圖像的很多領域[11-13]，本文將詳細介紹基于CS算法的圖像匹配方法，該方法把圖像匹配看作一個優化問題，采用優化策略完成匹配．

1 CS算法介紹

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

1.1 初始化CS算法參數

CS算法的第一步是設置參數，主要包括初始鳥巢數量n，發現概率Pa以及停止條件．

1.2 生成初始鳥巢

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

(1)

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

(2)

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

1.3 Lévy飛行產生新鳥巢

在Lévy飛行中，較小步長的短距離行走與偶爾較大步長的長距離行走相互交替.搜索前期，大步長用于探索發現，有利于擴大搜索范圍，搜索后期，小步長使得群體在小范圍內收斂于全局最優解．Lévy飛行搜索路徑的公式為

⊕L(λ)，

(3)

(4)

1.4 寄生蛋被發現

根據發現概率Pa，當P=randgt;Pa時，表示寄生蛋被發現，則更新鳥巢的路徑為

(5)

2 基于CS算法的圖像匹配

圖像匹配的過程中，特征表示、搜索策略以及相似性度量是其關鍵的3個要素．基于CS算法的圖像匹配可以看作，在待匹配圖像中以CS算法搜索候選圖像，使用特征描述方法表示目標或候選圖像塊，并用相似度量函數測量候選圖像塊與目標的相似程度，保留每次與目標相似度值最大的候選圖像塊，直到達到停止條件，此時最大相似度值所對應的圖像塊即為匹配目標．

2.1 特征提取

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

(6)

(7)

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

2.2 相似度測量

相似度函數是為了測量目標圖像塊的HOG特征與候選圖像塊的HOG特征的相似或相關程度．我們使用相關系數來衡量它們的相似程度，假設X代表目標圖像塊的HOG特征，Y代表候選圖像塊的HOG特征，用

運算關系來計算它們的相關系數，其中：D(·) 代表方差；cov(·) 代表協方差；ρ(X,Y)的取值范圍是[-1,1]，當ρ(X,Y) 的絕對值越大，說明X與Y相關度越高，目標圖像塊與候選圖像塊的相似性就越大，反之，則相似性就越小．

2.3 基于CS算法的圖像匹配

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

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

基于CS算法的圖像匹配，從優化問題的角度出發，利用CS算法的局部搜索和全局搜索相結合的搜索方式，使候選目標圖像塊收斂至全局最優，實現圖像匹配．

3 實驗與分析

實驗運行環境：CPU為Intel 酷睿i3 M380；2.53 GHz；內存為2 GB；操作系統是Windows XP. 軟件平臺是Matlab R2010b．實驗圖像大小為320×240，選取圖中以79行，76列為左上點坐標，大小為64×52的圖像塊為模板圖像．

3.1 參數選擇

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

圖1 匹配結果Fig．1 Matching result

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

表1 不同發現概率實驗結果 Tab．1 Experimental results with different discovery probability

為了確定Lévy步長a，在初始圖像塊數量n和迭代次數K不變的情況下，發現概率取Pa=0.5，將步長a分別設置為0.08、0.2、0.5、0.7，針對每個步長a分別實驗30次，得到表2．由表2可知，當a為0.5或0.7時，可實現30次的完全最優匹配．一般來說，步長越大，匹配速度越快，但在此環境下，a為0.5和0.7時，運行時間基本一致，為避免步長過大而錯過最優解，我們取a=0.5．其最優匹配結果如圖1(c)所示．

表2 不同步長實驗結果

3.2實驗結果與分析

由參數選擇部分我們得出，設定初始圖像塊數量n=250，迭代次數K=100，Lévy步長a=0.5，發現概率Pa=0.5，可獲得較好的匹配結果，我們采用這組參數作為實驗參數．

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

表3 不同匹配方法實驗結果

實驗一原始圖像和模板圖像質量較好,不存在噪聲干擾．

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

圖2 圖像匹配結果Fig．2 Image matching results

實驗二模板圖像質量較好，原始圖像加入高斯噪聲．

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

表4加入噪聲的實驗結果

Tab．4Experimental results with noise

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

圖3 加噪后匹配結果Fig．3 Matching results with noise

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

4 結束語

本文將CS算法引入圖像匹配問題，以HOG特征提取為輸入特征方法，以相關系數為相似度量函數，以CS算法為搜索策略，彌補了傳統群智能優化算法在圖像匹配中參數多、難以調節的缺點，通過求解全局最優解實現了在較少調節參數下的圖像匹配，并通過仿真實驗驗證了文中方法的有效性．但CS算法固定的參數設置使算法缺少靈活性，未來的工作我們將針對CS算法在圖像匹配領域的參數進行自適應設計．

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

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

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

[4] 張震，邵星星.一種SIFT虹膜匹配算法[J].鄭州大學學報(理學版)，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] 李強，張鈸．一種基于圖像灰度的快速匹配算法[J].軟件學報，2006，17(2)：216-222.

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

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

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

[10] 楊昆，張明新，劉永俊．基于優化粒子群的NCC模板匹配算法[J].計算機應用與軟件，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] 蒲國林，衛洪春，向偉.基于混合ABC-CS算法的彩色圖像多閾值分割[J].計算機與數字工程，2016，44 (7)：1323-1326.

[13] 陳娜．基于改進布谷鳥算法的圖像配準和融合中的參數優化[D].保定：河北大學，2016.

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

(責任編輯：方惠敏)

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

國家自然科學基金項目(61503173,61672471,61501407)；河南省科技攻關項目(172102210062，162102210060)；鄭州輕工業學院博士基金項目(2016BSJJ002)；河南省杰出青年基金項目(164100510019)．

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

TP391

A

1671-6841(2017)04-0051-06