基于SIFT算法改进的图像匹配算法

章雷 王国明

摘要：传统SIFT图像匹配算法约束条件较为单一，导致SIFT算法在原图像中存在相似特征很多的情况下，误匹配问题比较明显，不能有效剔除误匹配点。为解决这个问题，提出了一种基于SIFT特征点构建近邻图结构和增加向量约束条件的图像匹配方法。首先，使用K-mean方法对SIFT的特征点集进行聚类，进而生成K近邻图结构完成初始匹配。然后，在欧氏距离约束条件的基础上，增加向量相似度约束对传统SIFT算法约束条件进行改进，并根据相关系数进行匹配点的筛选，完成精确匹配。实验结果表明，该算法有效。

关键词：SIFT;向量相似度;K-mean;约束条件;欧式距离

中图分类号：G623        文献标识码：A        文章编号：1009-3044（2019）01-0185-03

Improved Image Matching Algorithm Based on SIFT Algorithm

ZHANG Lei，WANG Guo-Ming

（College of Computer Science and Engineering，Anhui University of Science &Technology， Huainan 232001，China）

Abstract：The constraint condition of the traditional SIFT image matching algorithm is relatively single， which leads to the fact that the SIFT algorithm has many similar features in the original image， the problem of mismatched is relatively obvious， and the mismatched points cannot be effectively eliminated.To solve this problem， an image matching method based on SIFT operator fusion vision dictionary and adding vector constraints is proposed.First， k-mean method is used to cluster the feature point set of SIFT， and then the k-nearest neighbor graph structure is generated to complete the initial matching.Then， on the basis of the Euclidean distance constraint， the constraint condition of the traditional SIFT algorithm was improved by adding the vector similarity constraint， and the matching point was screened according to the correlation coefficient to complete the accurate matching.Experimental results show that the algorithm is effective.

Key word：SIFT;Vector similarity; K-mean;Constraint Condition; Euclidean distance

近些年，计算机视觉领域发展迅速。图像匹配技术是计算机视觉领域中的一项重要的技术[1，2]。目前已经在许多领域得到了应用，诸如人脸识别、图像三维重建、计算机视觉等。

图像匹配指的是利用相关的匹配算法将两幅图像同一的位置点关联在一起的过程[3]。在实际应用中，由于目标位置以及相机视角的变化，光照强度不同等诸多干扰因素导致重复特征多，亮度变化大、干扰特征多等问题，给图像的精确匹配带来了不小的挑战[4]。

传统SIFT算法中采用的约束条件是与样本最近邻特征点欧式距离与次近邻特征点比值小于0.8来提取匹配点[5]，传统SIFT图像匹配算法约束条件较为单一，在原图像中存在相似特征较多的情况下，误匹配问题比较明显，不能有效剔除误匹配点，易出现错配和误配情况。

针对以上提出的问题，本文提出了一种基于SIFT特征点构建近邻图结构和增加向量约束条件的改进的SIFT算法图像匹配方法。该方法分两步，第一步，在初始匹配阶段，使用K-mean方法对SIFT的特征点集进行聚类，进而生成K近邻图结构[6]，完成初始图匹配，从图集合中筛选出可能与原图匹配的候选图;第二步，精确匹配阶段，候选图的特征点集在欧式距离的约束下，增加对SIFT算法中特征向量进行向量相似度的计算，增加向量的相似性约束，然后根据相关系数进行匹配点的筛选，最终完成精确匹配。

1 初始阶段

本节首先介绍了SIFT算法基本原理，然后定义图匹配的模型，最后说明了初始匹配阶段的主圖匹配算法过程。

1.1 SIFT算法基本原理

尺度不变特征变换（SIFT）[7]的基本思想是在尺度空间概念构建尺度空间提取位置、尺度和旋转无关量。具体做法是先构建尺度空间，在尺度空间中寻找局部极值点，确定关键点的主方向，生成关键点的描述子，最后进行匹配。以下是SIFT算法的5个主要步骤：

STEP 1  尺度空间的极值检测

首先将图像转换到尺度空间上，采用高斯函数[Gx，y，σ]与图像[Ix，y]进行卷积运算，将二维图像[Ix，y]转换到尺度空间图像[Lx，y，σ]，[σ]为空间尺度因子。

[Lx，y，σ=Gx，y，σ*Ix，y       ]                    （1）

[  Gx，y，σ=12πσ2exp-x2+y22σ2]                      （2）

为了进行尺度空间的极值检测，可以采用高斯函数（DOG）与图像[Ix，y]进行卷积计算得到尺度空间的极值点，其计算过程为：

[D（x，y，σ）=（G（x，y，kσ）-G（x，y，σ））*I（x，y）]    （3）

其中，k为乘数因子，用于改变相邻尺度的尺度大小。

STEP 2  关键点定位

对于关键点的定位可以对DOG函数进行二次泰勒展开进行运算，并对采样点进行计算：

[DX=D+?DT?XX+12XT?2D?DX2X]                 （4）

其中，为极值点到样本数据点的偏移量，對求导后取极值可获得极值点的位置。

STEP 3 关键点方向分配

SIFT变换过程中为图像局部特征的每个关键点都设定了一个相对方向，因此可以实现对图像的旋转的不变性。关键点方向参数通过求该关键点相邻像素的梯度方向分布特性得到。

STEP 4  特征点生成

首先计算关键点附近像素点的梯度模值和方向，以每个关键点为中心取16×16像素窗口，并在每个窗口中取4×4像素种子点来描述，单个关键点就形成了128维的描述特征向量。

STEP 5  特征点匹配

SIFT特征描述符向量生成后，求查询样本到目标样本最近邻特征点欧氏距离与次近邻特征点欧氏距离。如果最近邻特征点欧氏距离与次近邻特征点欧氏距离比值小于某一阈值时，认为该特征点对匹配成功，否则匹配失败。此处的阈值一般设定为0.8。

1.2 图匹配

在基于图模型的应用中，图匹配[8]是一项基础而又重要的技术。在本文中图模型的节点是图像的特征点，图模型[9]的边用来描述特征点之间的关系。利用图模型描述图像特征以后，图像的特征匹配问题就可以转化为图的顶点匹配问题[10]。以下是主图匹配的算法步骤：

输入：目标图像P，图像集合Qm

输出：候选图Gw

步骤：

Step1 对目标图像P进行SIFT特征点提取，生成特征点集MP={mi};

Step2 分别对图像集合Qm进行SIFT特征点提取，生成特征点集W={M1，M2，...，Mn};

Step3 对特征点集MP={mi}进行聚类操作，生成新的点集Mp={mi};

Step4 对特征点集W={M1，M2，...，Mn}进行聚类操作，生成新的点W={M1，...，Mn};

Step5 生成近邻图Gm=（VM，EM）。其中VM是图节点，EM={eij}，当i点和j是点近邻并且两点之间的距离小于所有点集之间的距离平均值时，点和点之间构成一条无向边eij;

Step6 运用Step5中的方法，为点集W={M1，M2，...，Mn}生成K近邻图集合Gw={Gm1，Gm2，...，Gmn};

Step7 将Gm与Gw中的每个元素进行匹配，选出候选图Gw={G1，G2，...，Gm}，其中m<=n。

2 精确匹配

本节介绍了精确匹配阶段需要的向量相似度计算理论，然后说明了将向量的相关系数融入传统SIFT算法中，对SIFT算法进行了改进。

2.1 向量相似度计算

相似度是指两个对象之间的类似的程度[11]。在本文中，采用的是SIFT特征点描述符，由于它是128维向量组成，故采用一般向量的相似度函数来度量相似程度[12，13]。假设对于任意两向量[X，Y]，从向量的大小和方向的角度综合表征两向量的相似程度[14]。可定义向量之间的关系如下：

定义1：向量[X，Y]的长度相似度（[αX，Y]），长度相似度是衡量向量大小的标准。

设存在向量[X=x1，x2，…，xn]，[ Y=y1，y2，…，yn]，则向量[X，Y]的长度相似度为

[αX，Y=1-X-YX] 其中[X]表示向量[X]的范数（5）

定义2：向量[X，Y]的方向相似度（[βX，Y]），方向相似度是衡量向量之间夹角大小的标准。

设存在向量[X=x1，x2，…，xn]，[ Y=y1，y2，…，yn] 则[βX，Y]为

[βX，Y=1-θ90°] ，其中

[θ=arccosX，YXY   0≤θ≤180°]                （6）

定义3：设存在向量

[X=x1，x2，…，xn]，[ Y=y1，y2，…，yn]，则向量[X，Y]的相似度（[γX，Y]为

[γX，Y=αX，Y?βX，Y]                 （7）

其中（[γX，Y∈1，-1]  ，当[θ=90°]时，两个向量正交，此时相似度系数[γX，Y=0];当[θ=0°] 时，并且范数相同时，两向量的相似度系数[γX，Y=1];当[θ=180°]时，并且范数相同时，两向量的相似度系数[γX，Y=-1] 。

2.2 向量的相关系数

在主图匹配完成后，筛选出符合条件的候选图，将候选图在SIFT初始匹配的点集M={mi}和W={wi}与待匹配的图的特征点集进行匹配。

SIFT算法在相似区域较多的图像以及特征信息很相似时，容易出现错配和误配情况。原SIFT算法中采用与样本最近邻特征点欧式距离来提取匹配点，没有考虑到特征向量间的相关性。欧式距离[15]是一种距离度量法，通过度量向量空间距离来表示向量间的相似程度，距离越近则向量越相似;当相似特征很多时，会有多个向量之间在向量空间距离是近似相等的，便会出现误配现象。在原有的约束条件下，运用相关系数法，增加向量间的相似性度量，提高了其匹配的精准度。

具体做法：在目标图像与待匹配图像之间的某一组特征描述满足于欧氏距离比小于0.8的前提下，进一步来计算这两组向量之间的相关系数R，其中R的取值范围为[0，1]，当相关系数越大时，说明两向量越相似。以下是精确匹配阶段的算法步骤：

输入：候选图Gw

输出：是否找到目标图像P的匹配图像P

步骤：

Step1  对目标图像P特征点集MP={mi}，进行向量相关系数计算;

Step2  对候选图Gw={G1，G2，...，Gm}在W={M1，M2，...，Mn}对应的特征点集进行向量相关系数计算;

Step3  将向量相关系数约束融入SIFT匹配算法中，完成匹配。

3 實验结果与分析

3.1实验环境

实验硬件环境为CPU 为Intel CORE I5，内存为4G的PC机。仿真实验环境是Windows8.1下的Matlab2016（a）软件，实验所采用的图像为Daniel Scharstein和Richard Szeliski立体匹配试验时使用的图像，从中选取了Bull、ohta 、venus、poster等四组试验图像。

本次实验从每组图像中选取两张图像，一张图像作为目标图像，一张图像作为待匹配图像，在待匹配图像中匹配到目标图像。由于图像的中心事物不变，导致两张图像存在大量相似区域。选用这些图像能有效地检验算法的匹配能力。选取的图像如图2所示：

3.2 试验结果分析

图3是传统的SIFT算法对bull图进行图像匹配的效果图，图4是改进的算法进行图像匹配的效果图。由图3和图4可见，对于重复和相似的特征点的问题，改进的算法有效地缓解了这一问题。表1是对试验图特征点结果的统计。

综合分析， 由表1试验结果统计结果可知，对Daniel Scharstein和Richard Szeliski立体匹配试验时使用的bull、ohta 、venus、poster等四组图像，本文中算法减少了重复特征点的数目，提高了匹配正确率，解决了由于相似区域较多带来的误匹配点多的问题，使用本文算法后，能捕获到更多的正确匹配点。试验结果基本满足算法设计目的。

4 结语

本文在传统的SIFT算法的基础上，针对SIFT图像匹配算法误配率比较高的问题，提出了增加向量约束条件的图像匹配方法。首先对SIFT的特征点集进行聚类，生成K近邻图结构，对K近邻图进行匹配操作。匹配成功后，在欧式距离的约束下，进一步对SIFT算法中特征向量增加了向量的相似性约束，保证了特征点的质量，减少了重复特征点的数目，提高了匹配的正确率，减少了误匹配点。实验结果表明，该算法有效。

参考文献：

[1] 罗斌.数字图像的结构图建模、特征描述和匹配研究[J].安徽大学学报（自然科学版）， 2017， （1）： 1-2.

[2] 项英倬，谭菊仙，韩杰思，等.图匹配技术研究[J].计算机科学，2018，（6）：27-31，45.

[3] 江波，汤进，罗斌.计算机视觉中的图匹配方法研究综述[J].安徽大学学报（自然科学版）， 2017， （1）：29-36.

[4] 谢宜婷，王爱平，邹海.基于局部近邻图的特征描述与特征匹配算法研究[J].计算机应用与软件，2017，（8）：185-190，196.

[5] 白廷柱，侯喜报.基于SIFT算子的图像匹配算法研究[J].北京理工大学学报，2013， （6）： 622-627.

[6]  Park， Youngki，Park， Sungchan，Jung， Woosung， et al.Reversed CF： A fast collaborative filtering algorithm using a k-nearest neighbor graph[J].Expert Systems with Application， 2015，

[7]  LOWE D G.Distinctive image features from scale-invarlant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-100.

[8] 白雪冰，陈凯，郭景秋， 等.基于k-mean聚类与灰度梯度最大熵的树木图像分割[J].森林工程，2014，（6）：84-88.

[9] 赵一丹，肖秦琨，高嵩.基于模糊神经网络和图模型推理的动作识别[J].计算机技术与发展，2018，（8）：80-85.

[10] 张文静，王备战，张志宏.基于图的特征选择算法综述[J].安徽大学学报（自然科学版）， 2017， （1）：10-20.

[11] Image quality assessment method based on nonlinear feature extraction in kernel space[J].信息与电子工程前沿（英文版），2016，（10）：1008-1017.

[12] 贺飞跃，田铮，段西发，等.高效的图模型点模式匹配算法[J].计算机工程与应用，2013， （24）： 19-23.

[13] 张宇，刘雨东，计钊.向量相似度测度方法[J].声学技术，2009，28（4）：532-536.

[14] 花小朋，徐森，李先锋.Least squares weighted twin support vector machines with local information[J].中南大学学报（英文版），2015，（7）：2638-2645.

[15] 张明，田娜，纪志成.基于适应值欧式距离比的均衡蜂群算法[J].系统仿真学报，2015， （5）： 980-989.