基于模拟退火算法与量子遗传算法的图像匹配研究

徐 梅

(安徽新华学院 信息工程学院，安徽 合肥 230088)

随着计算机视觉和图像处理技术的蓬勃发展，图像匹配技术作为其发展过程中的核心载体之一，应用领域进一步扩展，在高精度导航定位、医学器械成像处理、具有真实纹理特性的测绘作业等领域具有不可替代的作用[1-2]。各种图像匹配算法虽然切入点不同，但都基于特征空间、相似性度量、等价变换、最优化变换参数搜寻等四要素。传统的图像匹配算法主要分为基于先验模板和基于个性特征的图像匹配算法，这两类算法具有较好的匹配精度，但是其计算过程繁琐，导致实时性较差；最优化变换参数搜寻易出现早熟收敛且易陷入局部最优陷阱，导致匹配效果不佳[3-5]。在此背景下，综合考虑模拟退火算法与量子遗传算法存在的优势与不足，提出了一种基于模拟退火算法与量子遗传算法的图像匹配混合算法，可以克服模拟退火算法的收敛速度慢与量子遗传算法的局部搜寻能力弱等单一算法的固有劣势，从而较好地解决了传统图像匹配算法存在的诸多问题。通过在Matlab2015b环境下开发GUI验证界面，从多角度验证了论文所提算法的有效性，实际验证结果表明，论文所提算法鲁棒性较好，匹配精度、实时性等评价参数满足设计需求，具有一定的推广价值。

1 图像匹配及最优化核心技术

1.1 图像匹配的通用流程

图像匹配的主要意义在于消除由于图像获取实体不同、外界环境差异等因素对同一实体的影响而造成的外在差异，针对同一实体的图像特征，对两幅不同获取实体、具有明显外界环境差异的图像进行一致化[6]，获取序列图像中的固有相似特征，从而实现高效率图像匹配。图像匹配算法一般涉及以下要素：S1：特征空间，可以分为局部和全局特征空间，特征空间的主要作用是把原始图像的低纬特征映射到高纬度空间，是对具体特征的抽象化；S2：相似性度量，常用的相似性度量函数主要分为代价函数和距离函数，用来度量特征之间的相似程度；S3：搜索空间，搜索空间是图像匹配过程中由相似参数组成的多维空间[7]，是进行全局最优参数搜索的限制空间；S4：搜索策略，选择合适的最优化参数搜寻算法基于搜索空间进行图像变换相似值最大参数搜寻。与图像匹配上述要素相吻合，图像匹配的通用流程如图1所示。

图1图像匹配的通用流程示意图

1.2 图像匹配的相似性测度方法

图像匹配的相似性测度方法较多，合理地选取图像匹配的相似性测度方法对图像匹配的效率和质量至关重要。基于稳定性和精度的考虑，选择归一化互相关算法(NCC)来进行图像匹配的相似性测度，详细步骤如下：S1：对匹配图像和待匹配图像进行平均平滑滤波处理，保证两幅图像相似矩阵具有相关性；S2：基于预处理过的具有相似矩阵的匹配图像和待匹配图像，进行归一化处理，得到归一化互相关矩阵；S3：分别对匹配图像和待匹配图像的归一化互相关矩阵进行对应位置行与列的最大值及索引规则的建立，得出匹配图像中的固定一点与待匹配图像中任意一点相似性极大值；S4：根据步骤S3制定的索引规则，两图像对应点索引一致，则为一对初始匹配点对，至此，索引第一个循环结束；S5：不断重复步骤S1-S4，循环求出一一匹配的点对。经过归一化互相关算法处理过的匹配图像和待匹配图像的归一化互相关矩阵平面图效果如图2所示。

图2经过NCC处理过的归一化互相关矩阵平面效果图

1.3 基于匹配梯度的改进型的归一化互相关算法

图3 基于匹配梯度的改进型的归一化互相关算法流程图

归一化互相关算法(NCC)虽然具有较高的匹配精度和效率，但是由于其计算量较为复杂，导致匹配实时性无法满足航天测绘等对实时性要求较高的领域，一定程度上制约了归一化互相关算法(NCC)的应用范围。基于上述背景，提出了一种基于匹配梯度的改进型的归一化互相关算法(TNCC)，如图3所示，改进后的算法详细步骤如下：S1：对匹配图像和待匹配图像进行平均平滑滤波处理，保证两幅图像相似矩阵具有相关性；S2：引入匹配梯度因子，根据经过平均平滑滤波处理的匹配图像和待匹配图像的空间信息大小和方向确定匹配梯度因子，并确定与索引规则之间的对应关系；S3：对相似矩阵进行归一化处理，得到归一化互相关矩阵，根据匹配梯度因子大小，确定索引规则，确保匹配点索引的实时性；S4：根据索引规则，寻找匹配图像中的固定一点与待匹配图像中任意一点相似性极大值，重复上述步骤，直到识别到初始点为止。根据上述流程，在Matlab环境下编程实现，效果如图4所示。由图可知，基于匹配梯度的改进型的归一化互相关算法的实时性具有较大幅度的提高。

图4基于匹配梯度的改进型的归一化互相关算法处理效果图

2 基于模拟退火算法与量子遗传算法的图像匹配

2.1 算法总体概述

基于模拟退火算法与量子遗传算法的图像匹配算法主要包括基于模拟退火算法的变换参数全局最优搜寻子算法、基于量子遗传算法的高实时性图像匹配子算法两部分，如图5所示。其中，基于模拟退火算法的变换参数全局最优搜寻子算法用来从全局层面搜寻变换参数的最优解，主要包含温度T的初始值设置子问题、基于退火平衡策略的退火速度设置子问题、温度管理子问题等，可以避免变换参数陷于局部最优；基于量子遗传算法的高实时性图像匹配子算法主要用来解决图像匹配高速率问题，主要包含初始父代染色体选取子问题、与量子位相对应的状态适应度求解子问题、遗传变异代数的选取子问题、最佳适应度终止条件选取子问题等，可以有效改善图像匹配的实时性问题。为了保证算法执行效率，采用接续模式，基于模拟退火算法的变换参数全局最优搜寻子算法、基于量子遗传算法的高实时性图像匹配子算法按序执行，形成具有良性循环的接续结构，使算法整体向着最优解方向迭代。

图5基于模拟退火算法与量子遗传算法的图像匹配算法总体示意图

2.2 基于模拟退火算法的变换参数全局最优搜寻子算法设计

基于模拟退火算法的变换参数全局最优搜寻子算法可以克服量子遗传算法易陷于局部最优这一固有缺点，实现变换参数全局最优搜寻，子算法的详细实现方法如下：S1：确定目标函数，本文对应的目标函数是变换参数全局最优搜寻函数，需要将目标函数编写为M文件或inline函数，以供在Matlab环境下调用；S2：确定退火温度，退火温度一方面可以确定对新解的接受概率，另一方面，限制当前解与新解之间的搜索半径，即确定搜索范围，其中接受新解的概率由Meteopolis准则确定，退火温度的初始值由温度单位时间内下降速率决定；S3：确定退火进度表，退火进度表由温度随着算法迭代的下降速度决定，退火过程越缓慢，SA找到全局最优解的机会就越大，对应的运行时间也会增加。退火进度表包括初始温度和温度更新函数等参数。与上述过程相对应，核心代码如下：

swap(ans.citys[x], ans.citys[y]);

ans.len = 0;

for(int i = 0; i < n - 1; i++) %确定目标搜寻函数

ans.len += w[ans.citys[i]][ans.citys[i + 1]]; %确定退火温度

cout << "nCase = " << nCase << endl;

Print(ans, n);

nCase++; %确定迭代下降速度

c1=c(1);c2=c(2);

%计算代价函数值

df=d(S0(c1-1),S0(c2))+d(S0(c1),S0(c2+1))-d(S0(c1-1),S0(c1))-d(S0(c2),S0(c2+1));

if df<0%接受准则

S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)]；

Sum=Sum+df;

elseif exp(-df/T)>rand(1)%以概率exp(-df/T)接受新的路径%注意时elseif而不是else if

S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)]；

图6基于模拟退火算法的变换参数全局最优搜寻子算法效果图图7基于量子遗传算法的高实时性图像匹配子算法流程图

2.3 基于量子遗传算法的高实时性图像匹配子算法设计

基于量子遗传算法的高实时性图像匹配子算法可以克服模拟退火算法实时性较差、早熟收敛等固有缺点，实现图像匹配的高实时性，如图7所示，子算法的详细实现方法如下S1：根据当前选择的变换参数全局最优搜寻算法确定并初始化父代染色体；S2：对初始父代染色体进行量子位测量并得到与其对应的状态，对每个状态计算适应度，记录最佳个体及适应度；S3：根据上文给出的模拟退火表，确定需要迭代的遗传进化代数，其中采用量子旋转门对每一代染色体进行遗传变异，确保算法实时性；S4：根据图像匹配实时性效果确定迭代终止条件，输出最佳个体及适应度。

3 图像自动匹配系统设计

图8 通用图像自动匹配系统界面示意图

图9 极端环境下的系统效果示意图

为了实际验证上文所提算法的有效性和实用性，本文在Matlab环境下调用图形化开发插件GUI开发了一款通用图像自动匹配系统，该系统可以实现通用匹配图像与待匹配图像之间的格式化预处理、特征参数的提取与描述、相似性参数的提取与描述、基于模拟退火算法的变换参数全局最优搜寻、基于量子遗传算法的高实时性图像匹配等通用图像自动匹配的全流程，系统实际运行界面如图8所示。

为了进一步验证系统在非正常环境下的性能，选取对图像匹配影响较大的因素(选取图像特征点数量和迭代次数)进行控制变量验证，具体做法为：选取具有多维特征点的复杂图像重复上述处理过程，控制迭代次数为标准迭代次数的二分之一，观察图像匹配效果，由此可以得出文中所提算法在极端条件下的性能，对表征系统的整体性能和鲁棒性具有积极意义。试验结果如图9所示。

4 结论

本文提出了一种基于模拟退火算法与量子遗传算法的图像匹配混合算法，该混合算法融合两种算法的优点，克服单一算法的缺点，可以实现全局最优，具有匹配精度高、抗干扰性强、并行搜索效率高等优势。在此基础上，本文在Matlab环境下调用GUI图形化插件开发了一款通用图像自动匹配系统，并对系统的性能进行了实际测试。实际测试表明，基于模拟退火算法与量子遗传算法的图像匹配混合算法精度高、信息需求量较小、匹配效率较高，匹配出的图像信息纹理清晰，配准效果较好，可以满足高精度导航定位、医学器械成像处理、具有真实纹理特性的测绘作业等领域的应用需求，具有一定的实际推广价值。