一种蚁群优化的改进SIFT特征点的图像配准算法

侯坚，张明（上海海事大学信息工程学院，上海 201306）

一种蚁群优化的改进SIFT特征点的图像配准算法

侯坚，张明
（上海海事大学信息工程学院，上海 201306）

为减少图像配准的匹配时间，提高图像配准的匹配率，提出一种蚁群优化的SIFT图像配准算法。首先采用内核投影算法Walsh-Hadamard对SIFT特征描述子进行降维，然后采用优化的蚁群算法针对初匹配点进行提纯，提高匹配率。实验结果证明，改进后的算法与采用RANSAC算法提纯的SIFT算法相比，不仅提高匹配的正确性，而且也有效缩短算法的运算时间。

SIFT；图像配准；蚁群优化算法；内核投影

0　引言

图像拼接技术作为计算机视觉领域研究最早和最广泛的方向之一，在虚拟现实、医学图像处理、三维重建、遥感图像处理中有着极其广泛的应用和研究［1］。图像拼接是将多幅有重叠区域的图像匹配融合为一张高分辨率的宽视角的图像，以极大地满足了人们对大视野的要求。但是拼接所处理的图像会因为各种因素而存在不同的差异性，如时间、光照、分辨率、拍照角度、传感器等。拼接的主要目的就是消除这些差异性，得到自然平滑的拼接图像。国内外学者已提出多种图像拼接算法，其改进都是为了提高拼接的速度和配准的精度，以得到最好的效果为最终目的。

图像拼接的主要流程为：对图像进行去噪等预处理、采用特征点检测算法进行特征点的检测与提取、针对特征点进行特征匹配、采用图像融合算法对匹配后的图像进行拼接。其中，图像配准作为拼接的核心，配准的速度和精度直接影响到后续的融合过程。一般情况下，将图像配准划分成以灰度信息、变换域和特征为特点的三类配准算法。在图像拼接中，根据特征的图像配准方法应用最为广泛。而Lowe D.G提出了一种引入尺度空间理论的尺度不变特征变换（SIFT）算法［2］，经过1999年的理论提出，以及2004年完善后的发表使得尺度不变性特征开始应用到特征点的检测中。SIFT算子本身具有尺度不变性和旋转不变性，此外对于仿射变换和光照变化也具有较好的不变性，使其被广泛应用于图像配准和图像拼接等技术中。

研究者们在对SIFT算法的研究中发现，SIFT算法生成的特征描述算子高达128维，高维使得计算复杂度更高，而在特征匹配阶段，也会使得误匹配率增大。人们针对这一问题，引入RANSAC来改善误匹配增高。但是传统的RANSAC算法［3］在误匹配点比例较大的情况时，会增加特征优化迭代的次数，这样使得匹配时间延长，从而较大地降低了匹配的效率。

针对传统的SIFT算法产生高维描述算子，以及RANSAC算法存在的无法快速地收敛到最佳解时，就会通过迭代的次数的增加来求解，这样就极大地影响了配准的效率。本文提出一种蚁群优化的改进SIFT特征描述子的图像配准算法，对SIFT特征描述子，采用内核投影算法来对SIFT算子进行特种描述，从而避免了SIFT描述子的高维灾难，使得初始匹配时的计算量大大减少；在特征匹配阶段，利用改进的蚁群算法来优化初始匹配点对。仿真实验证明，改进后的图像配准方法不仅有效地剔除误匹配点对，降低了误匹配点对数，而且也有效地缩短了配准过程中的匹配的时间。

1　传统的SIFT算法

1.1SIFT特征点提取

（1）尺度空间极值点检测

SIFT算法首先将原图像放大为原来的两倍，然后通过对图像进行不同尺度的高斯平滑（模糊）处理和降采样，得到高斯金字塔，即高斯尺度空间。

其中，I（x，y）为输入的图像，*为卷积，σ为可变核，即尺度空间因子，σ的大小决定了图像的平滑程度，它对应了图像的概貌特征和细节特征。当σ连续变化时，L（x，y，σ）构成的图像组即为尺度空间。

SIFT算法通过在同一尺度下对两个相邻的高斯尺度空间的相减，从而得到高斯差分（DoG）的响应值，即高斯差分尺度空间D（x，y，σ），然后通过对高斯尺度空闲图像进行局部最大化搜索，根据空间位置和尺度空间确定局部特征点。D（x，y，σ）表达式如下：

其中，k为常数因子，表示相邻的两个尺度空间的间隔。

在高斯差分尺度空间中，关键点的确定是以比较空间内的是否为极值点确定的。每个待检测像素点与当前所在图像中的8邻域内像素点，以及9个邻域规模的上下相邻的同一组的像素点进行比较。只有当它大于或者小于这些邻域点时，才被认为是极值点，这样的操作不会带来很大的成本，由此可以得到候选关键点。

（2）关键点定位

由于关键点是在离散空间中进行计算，得到的候选关键点中存在许多不是真正的极值点，而是随机产生的噪声点和以及图像的边缘响应［4］，如低对比度的关键点，因为DoG的边缘相应而产生的不稳定的边缘响应点等。因此在得到候选关键后，需要将其拟合到像素附近的位置、尺度和主曲率。这个操作可以允许其过滤掉具有低对比度或沿边缘被定位不佳的响应点。算法通过三维二次拟合函数来精确关键点的位置和尺度，同时设置阈值来去除不稳定的相应点。

算法由三维二次拟合函数来精确关键点的位置和尺度，具体做法是对（3）式的泰勒二次展开式求极值。

对⑷式进行求导，得到极值点以及对应的极值，通过对X进行修改已得到的局部最优点，剔除低对比度的极值点，并利用Hessian矩阵的迹与行列式的比值表示的主曲率来剔除不稳定的边缘响应点。其中，Hessian矩阵为：

Hessian矩阵的迹和行列式为：

实验中主曲率的选取范围一般为6～10。

（3）确定关键点的方向

根据关键点的图像属性像素为每一个关键点分配一个一致的方向，然后关键点描述符可以相对于这个方向来描述，这样实现图像的旋转不变性。像素点处的梯度值（x，y，σ）以及方向θ（x，y）的计算如下：

一个方向直方图通过围绕关键点邻域内进行采样获取梯度方向生成的。将360°平分成36柱，然后对每一个邻近特征点的采样点进行σ为1.5倍的高斯加权圆形窗口加权，按照相对于中心关键点梯度方向的信息贡献，设置权值的变化，即随着采样点距离关键点的增加而变小。方向直方图的峰值对应于局部梯度的主方向。此外，其他任何局部峰值也就是最高峰值的80%用来创建幅方向。虽然仅有约15%被分配了多个方向，但是这些贡献增强了匹配的稳定性。如下图所示，使用lena图进行检测，提取出SIFT特征点的关键点方向显示图。由图（1）中显示的特征描述算子可以看出，存在有多个方向的特征点。

图1　SIFT算法生成的主方向特征图

（4）特征描述符

首先为了实现取向不变性，特征点的坐标和梯度方向是相对于关键点的主方向转动的。然后如图2中2×2种子点图像所示，在以关键点为中心的区域，取8× 8的窗口，在图2中第一幅图像的梯度幅值和取向围绕关键点位置进行采样，使用关键点的尺度来选择高斯模糊来对图像进行滤波。然后采用三线性插值来计算每个梯度样本的值并将其累加到箭头代表的方向上，从而得到第二幅图中显示的直方图。高斯模糊计算后就得到了一个种子点。这样描述符就从包含梯度直方图的向量中生成了。图2中一个关键点由2×2个种子点组成，每个种子点具有8个方向的向量信息。但是为了使算法的匹配性能更稳定，Lowe使用了4×4个种子点来描述特征点，这样每个特征点就形成了4×4×8= 128维的描述子。

图2　图像特征点梯度方向及高斯加权后的主方向

图3　SIFT特征描述子构造窗口

通过SIFT算法生成的SIFT特征描述子，就具有了特征点的位置信息、尺度信息和方向信息，而且向量去除了尺度变化和旋转变化对特征点的影响。通过将特征描述子进行归一化处理，可以去除光照变化的影响。

1.2SIFT特征匹配

SIFT算法采用欧氏距离作为两幅图像特征描述子的相似性度量方法。

当设定的阈值T的参数减小时，误匹配点对数目会减少，但是同时也剔除了正确匹配点对的数目；反之，当设定的阈值T增大时，会迅速增加误匹配点对的数目，这将极大影响结果的配准效果。

通过对阈值修改实验表明，当阈值T选取的范围在0.4～0.6之间的时候，特征匹配的效果是最佳的，而Lowe作者选取的0.8的实验效果，虽然得到的匹配的特征点数目多，但是同时也存在着大量的错误匹配点。所以本文根据实验效果将阈值设置为0.6。

通过欧氏距离的到匹配的特征点对后，有学者通过RANSAC算法对这些匹配的特征点对进行提纯，以剔除错误的匹配点对。现有提纯算法RANSAC算法，虽然在通常情况下取得了较好的效果，但是在求解最佳模型的情况时，当出现初始数据集合内的特征点的概率较低的情况时，在增加更多的迭代次数后，其结果可能获取不到收敛到最优解的解决方案，从而导致提纯的特征点对人存在误匹配点对，影响图像拼接的效果。

根据欧氏距离计算两个特征点之间的相似性，若最邻近点与次邻近点的欧氏距离的比值小于所设定的阈值，则认为两特征点匹配成功。

2　改进的SIFT图像配准算法

虽然传统的SIFT算法可以生成大量稳定的特征点，但是主要依赖的是主方向旋转和使用直方图的方法生成的特征描述算子，产生了128维的特征描述子，使得在后期的图像配准进行特征匹配时，增加了极大的运算量，影响了配准算法的时效性。所以现有的改进方法主要针对其高维度的问题进行相关的改进，并且取得了较好的结果。基于现有的改进结果，本文研究决定，采用内核投影对描述子进行降维来降低计算量。

2.1Walsh-Hadamard内核投影

Walsh-Hadamard内核是Gray-Code内核投影的特例。首先，W-H内核投影非常利于生成和应用。一维内核可以通过连续使用二叉树生成相关的内核［5］。在二维的图像处理上，二维内核可以通过一位内核的外积生成。W-H内核的所有坐标都是由+1或者-1组成。因此，W-H内核投影只涉及维度数量的增加和减少，计算速度快。Walsh-Hadamard内核函数采用如下矩阵表达式：

其次，当内核根据增加的信号变化时，实验表明紧致下界可以通过一定小数量的内核得到。所以，我们可以极大地减少相似性度量计算的复杂度，同时获取具有区分的特征向量。图4显示了二维W-H内核按顺序增加的图像。

图4　二维4×4的W-H内核顺序递增的图像，阴影表示值1，白色部分代表值-1

2.2改进的SIFT特征描述算子

改进的SIFT算法主要针对算法的第四步进行改进，在基于像素梯度值统计的基础上得到关于特征点的位置以及主方向的信息后。下面根据特征点的位置和尺度信息，以此特征点为中心选取一个区域作为图像子块，在该区域内，将区域内的像素点的梯度方向调整至主方向，这样就得到图像的规范化区域块。

在得到的区域块内，计算该区域块的方向梯度矩阵Fθ（x，y），其中θ划分为4个方向：0，。在图像子块中，不同方向的梯度矩阵可以通过以下公式得到：

其中，F0（x，y）代表水平梯度，代表竖直梯度。通过对梯度矩阵进行高斯滤波的方法来消除光照和视角变化的影响。

其中，参数σ设为图像子块宽度的四分之一。通过高斯滤波后，可以有效消除距离图像子区域中心的梯度值对最终结果的不利影响。

计算出梯度方向矩阵后，对梯度方向矩阵进行WH内核投影，在投影值中，计算前12个投影值的两个梯度方向水平梯度F0（x，y）、竖直梯度；再取前6个投影值，添加两个梯度方向，即梯度值为y）和。由上述梯度值产生36维的特征描述算子，即12×2+6×2=36维。

2.3改进的特征匹配算法

（1）SIFT初匹配特征点对

为了保证不增加额外的计算量，对改进的SIFT特征描述算子，采用欧氏距离作为相似度准则其进行匹配。任意两个待匹配描述算子的欧氏距离为：

利用k-d树的优先搜索算法进行搜索，搜索特征点P的最近邻和次近邻的特征点Q`、Q``，计算P点与Q`点，P点和Q``点两组算子之间的欧氏距离比γ，设置如果比值γ小于给定的阈值T时，匹配成功，记录初始匹配点对（P，Q`），否则，匹配不成功。根据算法的实验效果，在阈值T为0.8时效果较好。

（2）改进蚁群算法的特征点对优化算法

蚁群算法是一种整体最优化算法，相关的研究表明［6-9］，蚁群算法的离散性和并行性特点在处理求解复杂性优化问题时，尤其对于离散优化问题，显示出了其独特的优越性。这对处理数字图像是十分有利的。

对初匹配特征点对引入快速收敛的蚁群算法来进行优化。具体操作如下：

首先，我们对蚁群算法用到的相关参数进行说明介绍并且符号化：n设为蚂蚁数量，β设为启发式函数重要程度的因子，α设为信息素因子，ρ设为信息素蒸发系数，Q设为信息素总量，iter_max设最大迭代次数，初始值迭代次数iter设为1。

初始化蚂蚁的城市模型：采用蚂蚁作为搜索窗口，在图像A和图像B上，在参考图像B上，将改进的SIFT算法初匹配得到的特征点Xj（i=1，2，…，m）来比作n只蚂蚁，然后，搜索窗口使用图像A中的窗口来表示，将搜索特征点的迭代过程构建为城市模型，则每一个蚂蚁在不同时刻的观测数据，就是城市模型中的点坐标。随机的将n只蚂蚁放在m个城市上，让n只蚂蚁聚集到j个聚类中心Xj（i=1，2，…，m）；灰色关联度看作是相似性函数，构建灰色距离关联度D（i，j），系统因素间的关联性以距离来表示，即：

其中，d（Xi，X'j）表示两个城市i，j之间的距离，这里表示待优化匹配点对间的灰色关联度距离。

假设算法中的蚂蚁具有一定的存储能力，能根据两幅待拼接图像的灰色关联度选择转移的方向，使得灰色关联度值最大的方向为蚂蚁最终的移动方向。在图像匹配中，在参考图像B上，将匹配图像A中的窗口作为搜索窗口，则搜索特征点的迭代过程就可以看做是i只蚂蚁的城市模型，那么蚂蚁爬行的过程中，蚂蚁爬行所获得的每个哈密顿路，都对应着一个灰色关联度最大的组合。优化初匹配点具体过程如下：

①在爬行搜索操作中，禁忌表Tabuk（k=1，2，…，q）记录了蚂蚁当前走过的城市，每只蚂蚁转移的方向则是通过个体路径上的信息量来决定。根据路径的启发信息，以及各路径上的信息量，得到蚂蚁的状态转移概率，即：

②刷新信息素因子：当信息素达到某一临界值后，蚂蚁选择这条路径的概率大小与信息素因子α发热值的大小呈现类似反比的关系。算法的全局搜索能力会随着α的增大而由弱变强，逐渐跳出局部最优解，直到求得全局最优解。如果在N次循环内最优解都没有得到改进，那么就采用如下公式对信息素因子的取值范围进行改进：

其中，λ为常数，取值范围是λ≥1。本文选取λ= 1.0，αmax=5。

③更新信息素挥发因子：因为随着蚂蚁信息素的释放，连接各个城市之间路径上的信息素会逐渐减少，所以蚂蚁完成一次循环之后，每条路径上的信息素浓度就需要进行及时的更新，即：

由于信息素挥发因子ρ的参数的取值范围小，需要对其进行调整。而蚂蚁选择以前搜索的路径的概率会随着各路径上残留信息素的变化而变化，从而影响全局搜索能力的变化。当ρ设置偏小时，就会增加在各路径上残留的信息素，而蚂蚁选择以前搜索的路径的概率也会随着增加，这样全局搜索能力就会变小；当ρ设置偏大时，就会减小在各路径的信息素堆积的速度。为了增强算法的全局搜索能力，算法以牺牲收敛速度的方法为代价来完成。ρ值得自动修改变换如下：

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

④停止搜索的条件：当初始迭代次数iter≤iter_ max，则令iter+1，将蚂蚁经过的路径的禁忌表清空，然后转到步骤（2）；反之停止搜索，输出搜索后的结果。

4　实验结果及分析

实验环境硬件如下：使用的操作系统为Win7，采用的处理器为Intel Celeron CPU N2830@2.16GHz，运行内存4G，仿真平台MATLAB版本为MATLAB （R2010b）。

改进算法主要针对图像配准的精确度和计算时间进行改进，原始SIFT算法初匹配得到的图像表示如下图5所示。

图5　特征初匹配得到的结果图

下面针对本文改进的算法和SIFT-RANSAC算法进行匹配精确度的实验对比，对比结果如图6。

通过对比实验结果，虽然本文改进的算法获得的匹配点数少于SIFT-RANSAC算法获得的匹配点数，但是本文的改进算法却是取得了较好的实验结果，进行匹配的精确度明显好于SIFT-RANSAC算法。

本文对改进后的算法与原始SIFT算法进行了相关实验，针对特征点的匹配时间，以及特征点的匹配效率进行了实验分析，实验结果如表1所示：

图6　SIFT-RANSAC算法得到的结果图像

图7　本文算法进行优化得到的图像

表1　改进算法与SIFT算法在匹配时间和配准率上的实验结果

通过实验结果我们可以发现，改进算法在提取的特征点数量与原算法相同的情况下，虽然降维后，得到的初始匹配的特征点数目减少，但是在使用蚁群优化后，匹配效率上有较好的提高，配准算法运行的总时间也有了很大的提升。

4　结语

针对一般性的SIFT算法和RANSAC算法在配准精度与时间上的不足，本文在原来算法的基础上，通过引入内核投影技术来降低特征描述子的维数，并采用快速收敛的蚁群算法对初始匹配点进行了提纯，较好地提高了配准算法的配准率，同时也较好地提高了算法的计算效率，通过实验取得了较好的实验效果。使得图像配准在精度于与时间上有了极大的提高。

［1］Brown L G.A Survey of Image Registration Techniques［J］.ACM Computing Surveys，1992，24（4）：325-376.

［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］Chen Fuxing，Wang Runsheng.Fast RANSAC with Preview Model Parameters Evaluation［J］.Journal of Software，2005，16（8）：1431-1437.

［4］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.

［5］Yacov Hel-Or，Hagit Hel-Or.Real-Time Pattern Matching Using Projection Kernels［J］.IEEE Computer Society，2005，27（9）∶1430-1445.

［6］何志明.群体智能算法在图像匹配中的应用［D］.西安∶陕西师范大学2010.

［7］段海滨，王道波．蚁群算法的全局收敛性研究及改进［J］．系统工程与电子技术，2004，26（10）．

［8］段海滨，王道波.一种快速全局优化的改进蚁群算法及仿真［J］.信息与控制，2004，33（2）.

［9］林小平，周石琳，张官亮等.一种基于蚁群算法和互信息测度的图像拼接技术［J］.重庆理工大学学报：自然科学，2013，27（1）∶76-81.

SIFT；Image Registration；ACO；Kernel Projection

An Improved Ant Colony Optimization SIFT Feature Points of Image Registration Algorithm

HOU Jian，ZHANG Ming
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

In order to reduce the matching of image registration time and improve the matching rate of the image registration，proposes an ant colony optimization SIFT image registration algorithm.First，uses the kernel projection algorithm Walsh-Hadamard to SIFT feature descriptor for dimension reduction，then uses the optimization of the ant colony algorithm for initial matching points for purification，improves the matching rate.The experimental results show that the improved algorithm is compared with purified SIFT algorithm with RANSAC algorithm，not only to improve the validity of the match，but also effectively shorten the computation time of the algorithm.

1007-1423（2016）20-0078-07

10.3969/j.issn.1007-1423.2016.20.016

侯坚（1989-），男，山东临沂人，硕士研究生，在读研究生，研究方向为模式识别与图像处理

张明（1957-），男，江苏盱眙人，博士，教授，研究方向为多媒体信息处理、计算机视觉、人工智能等

2016-04-25

2016-07-10