程 红，陈 文 剑

禁忌搜索算法在图像匹配中的应用研究

程 红，陈 文 剑

（中国人民解放军空军航空大学特种专业系，吉林 长春 130022）

搜索策略是图像匹配研究的主要问题之一，对匹配算法的执行速度和最终的匹配精度都有很大的影响。该文将禁忌搜索算法的思想用于图像匹配的搜索过程，并进行了改进，构造了永久禁忌和暂时禁忌两种禁忌表，每次搜索都将候选解中的点分别放入不同的禁忌表中，再利用基于灰度的匹配方法，以归一化积相关为相似性度量准则，克服了传统的归一化积相关图像匹配算法耗时过长的缺点，可以在不失匹配精度的条件下，大大减少匹配所用的时间，实现了准确而快速的图像匹配。

图像匹配;禁忌搜索;归一化积相关

图像匹配属于人工智能的范畴，是人类视觉认知的一种延伸。图像匹配技术的应用领域相当广，如医学图像分析、导弹的地形和地图匹配制导、武器投射系统的寻的等;同时图像匹配技术也是其它一些图像分析技术（如立体视觉、运动分析、数据融合等）的基础。因此，开展图像匹配技术研究具有重要的理论意义和实用价值［1，2］。

所谓图像匹配，就是在机器识别事物的过程中，将已知图像与陌生图像的全部或部分在空间上对准，根据已知模式的图像在一幅陌生图像中寻找对应模式的子图像的过程［2，3］。图像匹配主要研究的问题有特征空间、相似性度量和搜索策略3方面。其中，搜索策略是指用合适的搜索方法在搜索空间又准又快地找出平移、旋转等变化参数的最优估计，使得图像之间经过变换后的相似性最大。搜索策略有穷尽搜索、分层搜索、模拟退火算法、遗传算法、粒子群算法等，后几种算法都属于智能优化方法，是近年发展起来的非常活跃的研究领域［4］。本文提出了一种基于禁忌搜索算法的图像匹配方法，利用图像的整体灰度值，以归一化积相关作为相似性度量准则，在搜索策略上使用经过改进的禁忌搜索算法，构造了永久禁忌和暂时禁忌两种禁忌表，既能避免重复搜索，又不至于陷入局部最优，从而实现了准确、快速的图像匹配。

1 归一化积相关图像匹配方法

归一化积相关算法是一种基于灰度的图像匹配方法。大量研究表明：尽管归一化积相关系数的计算量比较大，但它具有很强的抗噪声能力，对于灰度变化和较小的几何畸变具有不变特性，因而仍是图像匹配较好的相似性度量准则之一［5－8］。设实时图像为g，大小为M×N，基准图像为f，大小为W×H。归一化积相关算法计算每个可能的匹配位置处的相关系数，并找出其中的最大值点即为匹配点。

归一化积相关系数定义为：

式中：ρ（r，c）表示将实时图像平移至基准图像（r，c）位置处时，子图像与实时图像的相关系数的大小，并且有1≤r≤W－M＋1、1≤c≤H－N＋ 1;gij表示实时图像g中第i行、第j列的像素值;fi＋r，j＋c表示基准图像f中第i＋r行、第j＋c列的像素值;¯g为实时图像g所有像素的灰度平均值;将基准图像f中以（r，c）为左上角点，尺寸大小为M×N的区域定义为（r，c）处的基准子图，记作frc，则¯frc表示基准子图frc内所有像素的平均值［9］。

2 禁忌搜索算法

禁忌搜索算法（Tabu Search或Taboo Search，TS）是继遗传算法之后出现的又一种元启发式优化算法，最早于1977年由Glover提出。禁忌搜索算法模仿人类的记忆功能，使用禁忌表封锁刚刚搜索过的区域以避免迂回搜索，同时赦免禁忌区域中的一些优良状态，进而保证搜索的多样性，从而达到全局优化。

由于禁忌搜索算法的渴望水平、选择策略以及停止准则等都可以有多种设定方式，禁忌搜索算法的步骤多种多样。最基本的步骤［4］如下：1）初始化。给出初始解，禁忌表设为空。2）判断是否满足停止条件。如果满足，输出结果，算法停止;否则继续下一步。3）对于候选解集中的最好解，判断其是否满足渴望水平。如果满足，更新渴望水平，更新当前解，转至第5步;否则继续下一步。4）选择候选解集中不被禁忌的最好解作为当前解。5）更新禁忌表。6）转至第2步。

3 基于禁忌搜索算法的图像匹配方法

归一化积相关图像匹配方法就是在某一邻域内搜索实时图像的最佳匹配位置，其解可以看成是一个二维坐标（行和列），这实际上就是一个离散优化的过程，而禁忌搜索算法一般仅用于离散优化的情况，排斥实优化，并且它的各个构成要素正好与匹配过程的某一方面对应。因此，可以考虑应用禁忌搜索算法实现匹配。另外，为了尽可能地加强算法的鲁棒性和提升匹配速度，需要对标准的禁忌搜索算法进行改进。本文提出的基于禁忌搜索算法的图像匹配方法的实现过程说明如下：

3.1 获取初始值

初始值的确定对最终的匹配速度和结果影响很大。为使算法在刚开始时具有较好的全局寻优性能，第一次迭代的初始值一般取搜索空间的中心坐标。

设实时图像为g，大小为M×N，基准图像为f，大小为W×H，则第一次迭代的初始值为（‖r/2‖，‖c/2‖），其中1≤r≤W－M＋1，1≤c≤H－N＋ 1;第二次迭代选取第一次迭代过程中产生的最优搜索状态对应的坐标为初始值（如果中心坐标产生的结果最优，则选取次优搜索状态对应的坐标作为初始值）;以后的迭代过程则选取不在禁忌表中的最优值作为下一次迭代的初始值。

3.2 构造候选解邻域

候选解邻域是指某次迭代过程中所有可能的解的集合，这里将其看作是以该次迭代的初始值为中心的一定大小的区域，如3×3、5×5、7×7等，区域大小与参与匹配的图像大小有关，并能够影响迭代的速度和最终的匹配耗时。另外，当邻域中心靠近搜索空间的边缘时，可能得不到一个完整的邻域，这时将搜索空间看成以r行、c列为周期的二维离散周期函数，从而仍可确定出一个指定大小的区域。

设搜索空间大小为r×c，某次迭代的邻域中心（即初始值）为（x0，y0），邻域大小为（2R＋1）×（2R＋1），则邻域是指满足式（2）的像素点的集合，其中－R≤i，j≤R，i，j∈Z。如图1所示，图中阴影部分分别是以A、B点为中心的3×3大小的邻域区域。

图1 候选解邻域的确定Fig.1 The determination of the candidate solution neighborhood

3.3 构造适值函数及禁忌表

本文直接用目标函数，即实时图像与对应的基准子图的归一化积相关系数作为适值函数，评价候选解邻域内所有可能的匹配点的优劣。

为了尽可能充分地实现全局搜索和局部搜索，本算法构造了两种禁忌表：永久禁忌表和暂时禁忌表。永久禁忌表中的点在接下来的迭代过程中不再作为初始值，而暂时禁忌表中的点只在一定迭代次数之内禁忌被作为初始值，过了一定迭代次数后，这些点就可以成为迭代初始值，用来构建候选解邻域。也就是说，将本次迭代的初始值（候选解邻域的中心点）放入永久禁忌表中，将邻域中的其它点赋予某个禁忌长度，并放入暂时禁忌表中。

3.4 渴望水平及停止准则

本算法将每次迭代产生的所有搜索状态与历史最优值作比较，如果优于历史最优值，则将本次迭代产生的最优搜索状态作为新的历史最优值。

本算法以迭代次数达到某一阈值为停止准则。为了避免适值函数的重复计算，本算法构造了两个r×c大小的矩阵，一个用来保存已经计算过的坐标点对应的适值函数值，另一个用来标记哪些点的适值函数值已经计算过。在某次迭代过程中，需要把候选解的适值函数值与历史最优解进行比较，如果该候选解的适值函数值在之前的迭代过程中已经计算过，则可以直接使用，避免再一次重复计算。另外，由于搜索过程实际上是在包含多个极值“山峰”的空间内移动，寻找最高的峰值，本算法在某次迭代完成后就将该次迭代所访问的区域“削平”，即把该区域内所有点的适值函数值赋为零，这样的处理可以使算法尽可能地呈“发散状”向外搜索，从而避免陷入局部最优的情况。

3.5 对比实验

将本文算法与传统的归一化积相关匹配方法进行对比实验，以验证本文算法的可靠性和优越性。在使用本文算法时邻域大小、禁忌长度等参数都取大量实验得出的经验最优值，在3.6节详细讨论这些参数的确定过程。

实验条件：CPU：Intel（R）Core（TM）i 5;主频：2.40 GHz;内存：2.00 GB;操作系统：Windows 7家庭普通版;编程环境：Matlab 7.1。

测试图像和实验对比结果分别如图2和表1所示。测试图像中，第一组图像的最佳匹配点位于中心点上方，第二组图像的最佳匹配点位于左上角，且右侧存在一块相似的干扰区域;表1中的收敛次数是指算法收敛到最佳匹配点所需的最少迭代次数。

图2 实验所用的图像Fig.2 The images used in experiment

表1 实验参数和结果Table 1 The parameters and results of the experiment

3.6 实验结果分析和参数确定

由表1可知，本文算法能在很短的时间内稳定地收敛到最佳匹配点，但同时也发现，最终的收敛结果和收敛速度受邻域大小、禁忌长度等参数的影响很大。通过在实验中逐一改变各参数的取值，可以得到如图3、图4的关系。

需要说明的是，在图3b和图4b中，邻域大小为5×5的曲线变成了两段，这是因为当禁忌长度为6时算法在迭代4 000次时仍没有找到最佳匹配点，故认为此时算法的运行时间和收敛次数为无穷大。

图3 禁忌长度与运行时间的关系Fig.3 The relationship of tabu size and execution time

图4 禁忌长度与收敛次数的关系Fig.4 The relationship of tabu size and convergence times

由图3、图4可知，邻域大小为5×5时，无论是运行时间还是收敛次数都不稳定，随禁忌长度的变化波动很大;当最佳匹配位置位于搜索空间的4个角时，邻域大小取7×7时的运行时间和收敛次数也不稳定;相比较而言，邻域大小取9×9时较为理想，此时禁忌长度可以取区间［2，7］内的某一个值，算法在迭代150次以内均能稳定地收敛到最佳匹配值，耗时仅0.3 s左右。

用另外几组图像对上述得出的算法参数取值进行验证，结果均能收敛到与传统的归一化积相关算法相同的匹配结果，而耗时仅为传统算法的1/8左右。当参与匹配的图像较大时，邻域大小和禁忌长度也需要进行相应的调整，但也可以通过上述方法确定出算法的最佳参数值，并且能在满足相同匹配精度的情况下，在匹配速度上得到明显的提升。

4 结语

本文针对传统的归一化积相关图像匹配方法执行时间过长的问题，利用智能优化方法中的禁忌搜索算法来优化匹配的搜索过程，通过构造候选解邻域、两种禁忌表、适值函数等实现了准确快速的匹配。但本文提出的算法本质上并不是一种随机搜索算法，首先算法的初值是确定值，其次是算法每次执行都能保证稳定地得到相同的匹配结果。

［1］朱永松，国澄明.基于相关系数的相关匹配算法的研究［J］.信号处理，2003，19（6）：53l－534.

［2］张强.图像匹配算法研究［D］.西安电子科技大学，2006.

［3］BROWN L G.A survey of image registration techniques［J］.ACM Computing Surveys，1992，24（4）：325－376.

［4］汪定伟，王俊伟，王洪峰，等.智能优化方法［M］.北京：高等教育出版社，2007.

［5］陈智.图像匹配技术研究［D］.华中师范大学，2006.

［6］EPPLER W，PAGLIERONI D，HANSON J.GOES landmark positioning system［J］.SPIE Proceedings，1994，2812（2）：189－195.

［7］PRATT W.K.Correlation techniques of image registration［J］.IEEE Trans.Aerospace and Electronics System，1974，10（3）：243－256.

［8］TILION J C.Comparison of registration techniques for GOES visible imagery data［J］.Proceedings of IRW，1997，20（10）：133－136.

［9］韩冰，王永明.基于一种快速归一化积相关算法的图像匹配研究［J］.兵工学报，2010，31（2）：160－165.

Study on Application of Tabu Search Algorithm to Image Matching

CHENG Hong，CHEN Wen－jian
（DepartmentofSpecialty，TheAviationUniversityofAirForce，Changchun130022，China）

Search strategy is one of the main problems of image matching.It has great impacts on the execution speed and the final matching accuracy of the algorithm.In this paper，the idea of tabu search algorithm is applied to the search process of image matching，and it is promoted by constructing two different types of tabu lists：permanent tabu list and temporary tabu list.After each search process，the solutions in the candidate solution neighborhood are placed in different tabu lists.Then it accomplished the image matching accurately and quickly with the normalized product correlation as the criteria for similarity measurement.The results of experiment show that this method can overcome the shortcoming of time-consuming and large calculation amount of the traditional normalized product correlation algorithm，and greatly reduce the time spend in matching without losing the accuracy.

image matching;tabu search（TS）;normalized product correlation

TP751

A

1672－0504（2011）06－0032－04

2011－07- 03;

2011－09－22

全军军事学研究生课题（2010JY0844－500）

程红（1969－），女，博士，教授，硕士生导师，从事遥感信息处理研究。E－mail：nanna1204＠163.com