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\left( i \right)=\rm{round}\left( \mathit{M}*\mathit{rand} \right), $

(1)

$ y\left( i \right)=\rm{round}\left( \mathit{N}*\mathit{rand} \right), $

(2)

其中：x(i)、y(i)分别为鸟巢初始位置的x坐标和y坐标；M、N为鸟巢位置的边界值；rand为[0, 1]的随机数；round为取整函数.初始鸟巢的位置可由式(1)和(2)随机分配得到.

1.3 Lévy飞行产生新鸟巢

在Lévy飞行中，较小步长的短距离行走与偶尔较大步长的长距离行走相互交替.搜索前期，大步长用于探索发现，有利于扩大搜索范围，搜索后期，小步长使得群体在小范围内收敛于全局最优解.Lévy飞行搜索路径的公式为

$ X_{i}^{t+1}=X_{i}^{t}+\alpha \oplus L\left( \lambda \right), $

(3)

其中：X_i^t+1为第i个鸟巢在第t+1代的位置；X_i^t为第i个鸟巢在第t代的位置；α为步长控制量，用于控制搜索范围，其值服从标准正态分布；⊕是点对点乘法；L(λ)为随机搜索路径，L(λ)~U=t^-λ(1＜λ≤3).由于Lévy分布是一个复杂的问题，Mantegna R N给出一个数学表达式描述Lévy随机分布，即定义步长$S=\frac{u}{{{\left| v~ \right|}^{1/\beta }}~}$，可得

$ L\left( \lambda \right)=\frac{au}{{{\left| v~ \right|}^{1/\beta }}~}(X_{\rm{best}}^{t}-X_{i}^{t}), $

(4)

其中：a通常取值为0.01；β=1.5；X_best^t是当前的最优鸟巢位置；u和v服从标准正态分布.

1.4 寄生蛋被发现

根据发现概率Pa，当P=rand＞Pa时，表示寄生蛋被发现，则更新鸟巢的路径为

$ X_{i}^{t+1}=X_{i}^{t}+r(X_{j}^{t}-X_{i}^{t}), $

(5)

其中:r是[0, 1]之间均匀分布的随机数；X_j^t是X_i^t附近的一个鸟巢.反之，则不更新鸟巢位置.

2 基于CS算法的图像匹配

图像匹配的过程中，特征表示、搜索策略以及相似性度量是其关键的3个要素.基于CS算法的图像匹配可以看作，在待匹配图像中以CS算法搜索候选图像，使用特征描述方法表示目标或候选图像块，并用相似度量函数测量候选图像块与目标的相似程度，保留每次与目标相似度值最大的候选图像块，直到达到停止条件，此时最大相似度值所对应的图像块即为匹配目标.

2.1 特征提取

HOG特征是边缘的结构特征，能够很好地描述图像局部的形状信息.HOG特征将位置和方向量化为梯度幅值和方向，从而对图像的平移和旋转活动都具有适应性，且对光照变化具有鲁棒性，因此本文使用HOG特征作为目标或候选图像块的特征描述，像素点(x, y)处的梯度幅值m(x, y)和梯度方面θ(x, y)为：

$ m\left( x, y \right)=\sqrt{G_{x}^{2}+G_{y}^{2}}~, $

(6)

$ \theta \left( x, y \right)={\rm{arctan}}(\frac{{{G}_{y}}~}{{{G}_{x}}}), $

(7)

式中G_x、G_y分别表示水平方向和竖直方向的梯度.首先，依据式(6)和(7)计算目标或候选图像块中每个像素的梯度幅值和方向.然后，将目标或候选图像块均匀地划分成多个单元图像块(CELL)，梯度方向分为9个BIN，统计其梯度方向直方图，得到CELL的HOG特征.相邻的CELL组成一个BLOCK，将BLOCK归一化得到BLOCK的HOG特征.统计BLOCK的梯度方向直方图，完成图像块的特征提取.

2.2 相似度测量

相似度函数是为了测量目标图像块的HOG特征与候选图像块的HOG特征的相似或相关程度.我们使用相关系数来衡量它们的相似程度，假设X代表目标图像块的HOG特征，Y代表候选图像块的HOG特征，用

$ \rho \left( X,Y \right)=\frac{{\rm{cov}}\left( X,Y \right)}{\sqrt{D\left( X \right)}\sqrt{D\left( Y \right)}} $

运算关系来计算它们的相关系数，其中：D(·)代表方差；cov(·)代表协方差；ρ(X, Y)的取值范围是[-1, 1]，当ρ(X, Y)的绝对值越大，说明X与Y相关度越高，目标图像块与候选图像块的相似性就越大，反之，则相似性就越小.

2.3 基于CS算法的图像匹配

基于CS算法的图像匹配有几个主要组成部分：产生初始候选图像块并提取特征，计算候选图像块与目标的相似度值，找出相似度值最大的图像块并保存；依据Lévy飞行公式产生候选图像块，与初始候选图像块的相似度对比，保留两者中相似度较大的图像块，在所有保留下来的图像块中找出相似度最大的图像块并保存；根据发现概率，随机更新图像块，并保存更新后与目标最相似的图像块.基于CS算法的图像匹配方法如算法1所示.

算法 1 基于CS的图像匹配方法

Algorthm. 1 Image matching method based on CS

基于CS算法的图像匹配
初始化：
发现概率Pa；迭代次数K or停止条件；目标图像T；由式(1)和(2)初始化n块候选图像块X(i)(i=1, 2，…，n)；计算X(i)与T的相似度值R(i)；保存最大相似值对应的坐标Xbest；
While k＜最大迭代次数K or停止条件
for i=1：n
选择X(i)，由公式(3)得到X′(i)；
计算X′(i)与T的相似度R′(i)；
if R′(i)＞R(i) then
X′(i)的值取代X(i)的值；
end if
end for
for i=1：n
if rand＞Pa
更新图像块，由式(5)得到X″(i)；
计算X″(i)与T的相似度R″(i)；
end if
end for
保存最大相似值对应的坐标Xbest；
end while

基于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进行调整.

为了确定发现概率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.

为了确定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)所示.

3.2 实验结果与分析

由参数选择部分我们得出，设定初始图像块数量n=250，迭代次数K=100，Lévy步长a=0.5，发现概率Pa=0.5，可获得较好的匹配结果，我们采用这组参数作为实验参数.

此次实验，为了说明文中方法的可行性，在同样环境下，使用基于粒子群(PSO)的匹配算法、基于模拟退火(simulated annealing, SA)的匹配算法以及文中方法对原图像进行匹配，并观察实验结果.为了测试算法的抗干扰性能，再次实验时，原图像中加入均值为0、方差为0.01的高斯噪声，比较3种方法的匹配结果.

实验一  原始图像和模板图像质量较好, 不存在噪声干扰.

原始图像如图 2(a)，模板图像如图 2(b)，文中方法实现匹配效果图如图 2(c).将本文方法与基于PSO的匹配方法、基于SA的匹配方法结果进行比较，表 3为3种匹配方法的性能比较.由表 3可以看出，在原图像未加入噪声的匹配环境下, 文中方法可较好地实现匹配.从匹配精度上来说，文中方法虽然在时间上落后于基于PSO的匹配方法，但是在匹配精度上却有明显的优势.基于PSO的匹配方法，以PSO算法为搜索策略，在迭代初期收敛速度较快，易产生早熟收敛现象，陷入局部极小，从而使得算法的收敛精度不高，全局寻优能力较差.而文中方法使用CS算法为搜索策略，利用其局部搜索与全局搜索相结合的搜索方式，搜索过程中更容易跳出局部最优解，收敛至全局最优，从而实现精确匹配.从匹配速度来说，虽然文中方法与基于SA的匹配方法都达到了匹配精度，但在匹配速度上文中方法提升了50%.基于SA的匹配方法，使用SA算法作为搜索策略，其单个初始退火点，使得算法的收敛速度慢，CS算法初始化较多的图像块数量，可同时搜索候选图像块，加快了搜索速度.

实验二  模板图像质量较好，原始图像加入高斯噪声.

图 3(a)为加入噪声后的原始图像，图 3(b)为加入噪声后的匹配效果图，比较3种方法的匹配结果，可得出表 4.由表 4我们看出，在加入噪声干扰的情况下，文中方法和基于PSO的匹配方法在运行时间上几乎没有变化，但在匹配精度上文中算法仍然保持着最优匹配.基于SA的匹配虽保证了精度，在匹配时间上增加了4 s.实验结果表明，文中方法在图像匹配中具有一定的抗干扰性，是一种稳健的匹配算法.

以上实验，分别从匹配精度和匹配速度以及抗干扰3个方面表明了文中算法的有效性和可行性.

4 结束语

本文将CS算法引入图像匹配问题，以HOG特征提取为输入特征方法，以相关系数为相似度量函数，以CS算法为搜索策略，弥补了传统群智能优化算法在图像匹配中参数多、难以调节的缺点，通过求解全局最优解实现了在较少调节参数下的图像匹配，并通过仿真实验验证了文中方法的有效性.但CS算法固定的参数设置使算法缺少灵活性，未来的工作我们将针对CS算法在图像匹配领域的参数进行自适应设计.