SIFT-FCACO算法的图像配准

　　摘  要： 为了降低图像配准误匹配率以及减少RANSAC算法特征优化迭代次数，提出了SIFT-FCACO的图像配准算法，用快速收敛的蚁群算法对图像匹配后的特征点对进行优化。实验结果表明，该算法不仅减少了匹配时间，而且提高了匹配的准确率。

　　关键词： SIFT-FCACO算法；蚁群算法；图像配准

　　图像配准是指将采集到的两幅或多幅图像进行空间变换，利用相关性寻找像素间的对应关系，从而确定几何变换模型的过程。一般将图像的配准方法分成基于灰度信息的图像配准方法、基于变换域的图像配准方法、基于特征的图像配准方法三种[1-2]，其中基于特征的图像配准方法在图像拼接中得到了广泛的应用。2004年LOWE D G提出的尺度不变特征变换算法（SIFT）[3]对图像的尺度和旋转具有不变形，被广泛应用于图像拼接。但传统的SIFT算法在图像配准阶段误匹配率比较高，并且传统RANSAC算法[4]在误匹配点比例较大时，特征优化迭代次数多，大大影响了拼接算法的效率。20世纪90年代初，意大利的DORIGO M、MANIEZZO V和COLORNI A等著名学者提出一种用来在图像中搜索优化路径的机率型仿生进化算法——蚁群算法（Ant Colony Algorithm）[5]，该算法是群体智能领域主流的新型研究方法。

　　针对传统的SIFT算法在图像配准阶段误匹配率比较高以及RANSAC算法特征优化迭代次数多，从而导致图像拼接后在重叠区域容易出现拼接缝的问题，本文提出SIFT-FCACO的图像配准算法，对SIFT特征匹配算法进行了改进，利用快速收敛的蚁群优化算法FCACO（Fast Convergence Ant Colony Optimization Algorithm）来优化匹配点对。仿真实验证明，改进后的匹配方法不仅能有效地剔除误配点，而且减少了匹配时间。

　　1 SIFT算法

　　1.1 尺度空间极值点检测

　　SIFT算法建议，在某一尺度通过引入一种新算子——DOG算子（Difference of Gaussians，高斯差分算子）来检测特征点，该算子只需对平滑后的相邻尺度高斯图像作减法计算，得到相邻尺度图像的差异信息，其优点是计算简单、速度快[6]。DOG函数表达式为：

　　

　　其中，k是常数，表示相邻层之间的间隔距离，k=21/s，本文中s=2。

　　对高斯差分金字塔尺度空间中的每个像素点和与它相同层的8个相邻像素点以及与其相邻上下两层的18个像素点，总共26个相邻像素点进行比较，看此像素点是否为它的图像空间或者尺度空间的极大值或者极小值，如果该点是极值点，则确定该点作为候选点。

　　1.2 精确定位特征点

　　由于上述特征检测是在离散空间进行的，得到的候选极值点中有许多不是真正的极值点，而是随机噪声和边缘响应[7]，因此需要进一步优化匹配点对以使匹配的稳定性更好，提高算法的抗噪声能力。通过拟合三维二次函数来精确确定特征点的位置和尺度，即对泰勒二次展开式（2）求极值，同时去除低对比度的极值点，并利用Hession矩阵的迹与行列式的比值去除不稳定的边缘响应点。

　　

　　1.3 生成特征描述符

　　为了使检测到的特征点保持一定的方向不变性，需要根据图像的局部特征规定每个特征点的方向。特征点（x，y）处的梯度幅值和相位按式（3）、（4）进行计算：

　　

　　其中，m（x，y）表示特征点的梯度幅值，θ（x，y）表示其相位方向。

　　为了使特征点可以适应图像的方向变化，需要将特征点沿主方向顺时针旋转角度θ，提取特征点的特征向量过程如下：

　　（1）以特征点为中心，选取大小为16×16的窗口区域，高斯加权图像窗口区域（窗口大小为8×8）内各像素点（不包括像素点所在行和列的点）与特征点间隔距离越小，对其贡献越大，反之则越小。生成的特征点描述符如图1所示。

　　（2）将大小为16×16的窗口平均分成16个小块，每个小块的大小为4×4，对每小块8个方向的梯度进行计算并且对其累加，于是在特征点大小为16×16的窗口内总共能够生成4×4×8=128个数据，即每个特征点可以生成128维的特征向量，用特征点描述符A=（α1，α2，…，α128）来表示。

　　（3）为了去掉光照变化的影响，将特征向量的长度进行归一化。假如一幅图像共有n个特征点，那么这幅图像的全部特征向量就组成了初始匹配数据的矩阵集合，大小为128×n，其中的每一列就表示一个特征点描述子。

　　1.4 SIFT特征匹配

　　（1）本文采用欧式距离作为待匹配图像和模板图像中生成的128维特征向量描述子的相似性度量方法[8]，任意两个待匹配描述子的欧氏距离为：

　　

　　2 FCACO特征点对优化算法

　　通过上述特征匹配后得到了一系列特征点对，但是在匹配过程中由于受到各种外界或者内在因素的影响，容易产生大量的误配点，影响后续的图像拼接过程。同时，现有提纯误配点的RANSAC算法在求解最佳模型的过程中，假如初始数据集合内点概率较低时，不仅需要比较多的迭代次数，而且还可能无法收敛到最优解，因此要对匹配的特征点对进行优化。本文提出一种用FCACO算法优化匹配点对的方法，具体过程如下：

　　（1）初始化参数：包括蚂蚁数量m、信息素重要程度因子α、启发函数重要程度因子β、信息素蒸发系数ρ、信息素总量Q、最大迭代次数iter_max、迭代次数初始值iter=1。

　　（2）构建蚂蚁城市模型：在两幅图像上利用蚁群作为搜索窗口，SIFT算法匹配出的特征点Ri（i=1，2，…，m）被看作m只蚂蚁，根据图像S中的窗口在模板图像R中搜索食物的迭代过程建立“i只蚂蚁的城市模型”，将m只蚂蚁Ri随机放于n个城市（m≤n），并将蚂蚁聚类到j个聚类中心Sj（j=1，2，…，k），为每只蚂蚁建立禁忌表tabuk（k=1，2，…，m），并用禁忌表中存储的初始节点信息来记录蚂蚁目前已经走过的城市。假如算法中的每一只蚂蚁都有一定的记忆功能，可以按照两幅待拼接图像上的灰色关联度大小来引导蚂蚁搜索并且向特定的方向移动，最终朝着灰色关联度最大的方向搜索，从而确定出两幅图像之间匹配点对。

　　（3）构造蚂蚁灰色关联度Di，j，并将灰色关联度作为相似性函数，从距离空间的角度反映系统因素间的关联性：

　　

　　其中，d（Ri，Sj）为待优化特征点对间灰色关联度距离；min d（Ri，Sj）为待优化特征点对间灰色关联度距离的最小值，maxd（Ri，Sj）为待优化特征点对间灰色关联度距离的最大值。

　　（4）蚂蚁搜索过程：搜索过程当中的状态转移概率由道路上的信息量和路径的启发信息决定，i城市的第k只蚂蚁选择下一个城市j的概率分别为：

　　

　　其中，p为状态转移概率；α为信息素的重要程度因子，其值越大，表示信息素的浓度在转移中起的作用越大；β为启发函数重要程度因子，其值越大，表示启发函数在转移过程中所起的作用越大；allowk为第k只蚂蚁可以访问的城市集合，初始状态，allowk中有n-1个集合，也就是包括除去蚂蚁k出发城市的其余所有城市，随着时间的推移，allowk中的元素逐渐减少，直到所有的城市全部访问完成之后变为空集；η为启发函数表达式，代表蚂蚁由城市i转移到城市j的期望程度，由两个特征点对之间的灰色关联度大小Di，j决定。

　　（5）更新信息素重要程度因子：当信息素达到某一临界值后，随着信息素重要程度因子α逐渐变大，这条路径被选择的概率逐渐变小，算法的全局搜索能力由弱变强，慢慢地跳出局部最优解，直到求得全局最优解。当算法在N次循环之内没有改进当前最优解时，信息素重要程度因子的取值范围进行变换，即：

　　

　　其中，ρ为信息素蒸发系数，0≤ρ≤1；τ为窗口信息素含量，?驻τijk为第k只蚂蚁在城市i与城市j连接路径上释放的信息素浓度；?驻τij为所有蚂蚁在城市i与城市j连接路径上释放的信息素浓度之和；Q为常数，为蚂蚁循环一次所释放的信息素总量。

　　由于信息素挥发因子ρ的参数取值范围小，因此需要对它进行微调。当ρ过小时，在各路径上残留的信息素过多，导致以前搜索过的路径被选择的概率增大，使全局搜索能力减小；当ρ过大时，各路径的信息素堆积速度慢，以牺牲收敛速度为代价来增强算法的全局搜索能力。本文算法将自适应地修改ρ：

　　

　　其中，ρmax=0.9；δ是一个常数，δ≥1，经试验，本文取δ=1.01。

　　（7）判断是否停止搜索：如果iter≤iter_max，则令iter+1，清空蚂蚁经过路径的禁忌表，返回步骤（2）；否则停止搜索，输出结果。

　　SIFT-FCACO算法优化匹配点对的流程图如图2所示。

　　3 实验结果及分析

　　为了验证本文算法对光照的鲁棒性，采用本文提出的SIFT-FCACO图像匹配算法与一般的SIFT-RANSAC图像匹配算法进行对比实验。实验所用的图像为不同光照强度下拍摄的两幅图像，尺寸大小均调整为400×300，图像格式为JPG，图像如图3所示，其中图3（a）为天气晴朗的中午拍摄的图像，图3（b）是下午五点左右拍摄的图像，分别利用SIFT-RANSAC图像匹配算法和SIFT-FCACO图像匹配算法进行实验，效果如图4、图5所示。

　　图4（c）是采用经典的SIFT-RANSAC算法得到的匹配效果图，图5（c）为本文算法得到的匹配效果图。从提取的特征点进行分析，图4（a）中提取的特征点比图5（a）中的特征点要多一些；从匹配的特征点数进行分析，图4（b）、4（c）中的特征点虽然多，但是误匹配也多，这将导致误匹配率较高；图5（b）、5（c）在特征点几乎相同的情况下错误匹配并未增加，从而降低了误匹配率。

　　不同工作状态的计算机硬件设备对软件运行速度的影响会有一定的差异，因此表1中的数据是在对整个实验运行10次计算平均值的结果，其中匹配率为优化后匹配对数与特征个数中较小值之比。从表1可以得出，SIFT-FCACO算法提纯的误配点对比较多，对光照、位移、尺度变化均保持一定的鲁棒性，经过本文算法优化误配点对后，有效地提高了匹配效率，减少了匹配时间，更有利于后续的图像拼接过程。

　　针对一般的SIFT和RANSAC算法在配准精度与速度上的不足，本文提出了一种SIFT-FCACO的图像匹配算法，凭借SIFT特征对于旋转和尺度的不变性以及对于噪声、亮度变化等鲁棒性良好的优势进行特征提取和匹配，并设计了一种FCACO算法进一步优化SIFT匹配的特征点对，从而提取出具有较大信息量的匹配点对，有利于图像拼接的进行。

　　参考文献

　　[1] ZITOVA B， FLUSSER J. Image registration methods： a survey[J]. Image and Vision Computing（S0262-8856），2003，21（11）：977-1000.

　　[2] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision（S0920-5691），2004，60（2）：91-110.

　　[3] Deng Rongfeng， Li Xiying. Robust image mosaic algorithm based on SIFT feature matching[J]. Journal of Computer Applications， 2009，29（6）：219-221.

　　[4] Chen Fuxing， Wang Runsheng. Fast RANSAC with preview model parameters evaluation[J]. Journal of Software，2005，16（8）：1431-1437.

　　[5] 何志明.群体智能算法在图像匹配中的应用[D].西安：陕西师范大学，2010.

　　[6] 王静.基于SIFT和角点检测的自动图像配准方法研究[D].武汉：华中科技大学，2010.

　　[7] Sun Wei， Guo Baolong. A robust object detecting and tracking method[C]. Fifth International Conference on Fuzzy Systems and Knowledge Discovery， USA， IEEE Computer Society， 2009：121-125.

　　[8] 曹建秋.基于SIFT图像拼接技术研究[D].重庆：重庆交通大学，2012.