基于布谷鸟搜索的图像匹配方法研究

张焕龙， 张秀娇， 贺振东， 张建伟

(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