基于SIFT算法的图像特征匹配

周颖

（四川大学计算机学院，成都 610065）

基于SIFT算法的图像特征匹配

周颖

（四川大学计算机学院，成都 610065）

SIFT特征匹配算法的原理在于生成特征点的SIFT特征向量，通过对特征向量之间的匹配来实现图像之间的匹配。SIFT特征是一种尺度不变的局部图像特征，阐述生成SIFT特征向量的具体过程，包含尺度空间构建、关键点的检测和精确定位、关键点方向向量的确定和最终SIFT特征描述子的形成等步骤，以及根据形成的特征描述子进行图像的匹配。根据实验结果得出SIFT算法可以有效准确地实现图像之间的匹配。

图像匹配；SIFT特征匹配；尺度空间；方向向量；特征描述子

0 引言

随着计算机行业的不断发展，二十世纪七十年代末MARR提出计算机视觉理论，认为计算机视觉是一种信息处理的过程，经过这一过程通过硬件计算机从图像中了解和发现外部世界的信息。并提出信息处理的三个层次，第一个层次为信息进行处理所依据的理论，即研究对什么进行处理和为什么进行信息处理；第二个层次为实现处理的实现算法，即如何实现处理，为实现设计相应的算法；第三个层次为研究实现这一处理过程所依赖的硬件设备，例如在人类的视觉系统中，这一层次的内容为人类复杂的神经网络，即人类视觉系统对所获取的信息进行处理依赖的硬件是人类的大脑神经网络，这一层次也是界定不同领域视觉系统的关键因素，计算机视觉系统依赖的硬件则是计算机。计算机视觉理论的发展极大地推动了图像处理领域对图像特征进行匹配的研究工作进展，使得图像匹配问题成为计算机视觉和图像处理领域的热点，图像匹配技术指的是把已知的图像同未知的陌生图像进行三维空间上的配准，根据某种规则在待匹配图像上找寻对应于已知图像的子图像。例如在双目视觉系统中，根据左右摄像机拍摄到的同一三维物体不同角度的左右两幅图像，已知左图像，在右图像中按照某种匹配准则寻找对应左图像的特征的过程就是简单的图像匹配，两幅图像中的匹配对应于三维空间物体的同一点或者图像块。

图像匹配的技术现在被广泛应用在各个领域，包括了辅助医疗影像分析协助诊断、雷达跟踪系统、工业分析检测、智能交通管理系统、流水线智能监控、图像的检索，等等。图像匹配技术按照算法类别属性的不同可以分为基于图像像素灰度的匹配、基于图像特征，基于神经网络和语义网络[3]，基于各类遗传算法等多种匹配算法。各种算法都有其适用的领域和环境。SIFT算法[1]是Lowe提出的一种基于局部特征不变的特征匹配算法，具有尺度不变的特点。SIFT算子对应的是图像的局部的特征描述，对图像发生的各类变化，该特征都具有良好的稳定性，图像发生视角的变化、旋转、图像放大或者缩小，或者是由于客观因素例如光照的变化，噪声的干扰造成的图像的变化，SIFT特征对这些变化都保持不变。所以在复杂情况下进行图像之间的匹配，SIFT特征具有良好的鲁棒性，对匹配表现出良好的效果。同时SIFT特征较其他图像特征还具有独特的特性[2]，并且具有很好的扩展特性。近年来，基于SIFT算法的图像特征匹配在很多重要领域都取得了不错的成绩，得到了广泛的应用，包括了图像的拼接技术、遥感图像的匹配、物体的识别系统、机器人智能导航和定位、三维重建系统、运动目标提取和跟踪，以及指纹识别、人脸识别等[3]。SIFT算子对图像发生平移、旋转、缩放，图像发生视角变化、投影仿射变化、光照和噪声条件改变，以及有目标遮挡等场景有较好的匹配效果。

1 SIFT特征描述子

SIFT特征具有尺度不变化特性，对图像而言是图像的局部特征，是计算机视觉中用来检测和描述二维图像中的局部性的特征[2]。SIFT特征匹配算法的原理就是通过构建图像尺度空间，在尺度空间中寻找极值点并且筛选出稳定良好的极值点作为关键点，再对关键点加上方向参数的描述，进而构建出SIFT特征描述子。匹配的过程即是通过对SIFT特征向量之间的欧氏距离进行求解的过程。欧氏距离越小表明两个向量之间的相似度越高，即匹配程度越接近。因此使用SIFT算法来实现图像之间的配准所需要的主要步骤包括了：尺度空间[4]的构造、构建图像高斯金字塔以及图像的高斯差分金字塔、尺度空间极值点的检测、获取稳定可靠的极值点作为关键点，即对关键点的精确定位、为关键点分配方向向量并生成关键点的描述向量作为SIFT特征向量、利用SIFT特征向量进行特征匹配。

1.1 构建尺度空间

尺度空间的构建在整个匹配算法中相当于是初始化的过程，尺度空间理论表明尺度空间模拟的是图像的多尺度特征，并提出高斯核实唯一实现尺度变换的线性核，所以对一幅图像的尺度空间进行定义，如下公式所表示：

其中G是高斯卷积函数，σ是度量尺度的因子。L则代表了图像的尺度空间，I为二维图像。尺度因子σ表征的是图像的平滑程度，σ越大表明图像的概貌特征越明显，即图像越模糊，对应低的分辨率；σ越小表明图像的细节特征越明显，也就是图像对应高的分辨率，图像的细节就越展现出来，对应精确的尺度。

1.2 构建高斯差分尺度空间

由于仅依靠尺度空间对极值点进行检测，容易提取出不稳定的、性能差的边缘点，为了得到稳定的性能优良的极值点作为关键点，可以使用高斯差分尺度空间，利用不同尺度因子下的高斯差分卷积核与图像进行计算[5]，即实现对不同尺度下的图像卷积运算，高斯差分尺度空间的构造公式如下所示：

不同尺度下的图像尺度空间的理论描述可以用下图1来表明：

图1

上图中显示尺度空间中相邻尺度之间的尺度因子关系表明了尺度空间是连续的这一结论。并且Lowe提出的尺度空间理论中初始的尺度定义为1.6[6]，这个尺度对应的图像是最不清晰的，而图像的初始尺度对应于最清楚的图像信息，进行极值点检测之前需要对图像进行高斯滤波，这样会引起高频信号的丢失，基于这一点Lowe得出需要在尺度空间的构建之前对图像进行扩大一倍的处理，以此来保护图像的原始信息，使得检测过程中获取的特征点的数目比较多。

1.3 构建图像金字塔

为了使图像在各个不同的尺度下都有其对应的特征点，需要构建每一层的子八度图像，即对一幅二维图像I建立它在不同尺度下的图像。子八度的第一个图像都是原始图像的大小，而之后的各个子八度则依次对自己的前一个八度进行降采样，降采样[7]指的是对长和宽分别都减一半的操作，因此每后一个子八度的图像大小都是前面的1/4大小，如图2所示。

图2

子八度总的个数取决于图像的大小，而每个子八度中的层数一般为3～5层，每一个八度中从下往上，上面一层的图像是经由下面一层相邻图像高斯卷积而来，对应不同的卷积因子σ。从直接对图像进行观察可以看出，图像是越来越模糊的。

1.4 检测空间极值点

在构建好的尺度空间中寻找极值点，该点不仅要在所在的二维图像中是极值点，并且在相邻的尺度空间比较中也必须是极值点，即该点不仅需要同二维图像中的周围相邻的八个像素点进行比较，还需要同处于同一八度的上下两个尺度的二维图像周围一共18个相邻像素点进行比较，如图3所示。只有同这些点都进行了比较确定是极值点，才可以作为初步的待选关键点。

图3

在进行极值点的检测，由于需要同上下相邻两层以及自身所在层进行比较，可以看出每一组八度中位于底部和顶部的两层是没有办法按照条件进行比较的，然而尺度空间的变化是连续的，因此为了保证该空间的连续性，对每一个八度的图像在顶部继续进行高斯模糊多生成三幅图像[8]，因此在高斯金字塔中每一个八度就多增加了三层，而对应的高斯差分金字塔每一个子八度则多增加了两层。假如初始每个子八度的层数为3，那么如图4所示。

图4

之所以选择使用高斯差分金字塔代替高斯金字塔进行极值点的检测，是因为高斯金字塔虽然可以找到比较多的特征点，但是计算量比较大，计算繁琐，而使用高斯差分金字塔则可以很好地避免过多的计算，它是尺度归一化的LOG算子[7]。

1.5 去除不稳定的特征点

为了去除高斯差分金字塔中检测出的对比度比较低、不稳定的边缘特征点，以及曲率不对称的像素点，采用尺度空间函数泰勒展开，拟合三维二次函数来精确定位关键点到亚像素即确定关键点的对应尺度位置[8]。由此精确定位来实现匹配算法的准确性和稳定性。其中尺度空间的泰勒展开形式如下所示：

为了得到精确的位置信息，对泰勒展开形式进行求导运算并且取值为零可以得出：

结合两式得出决策是否为低对比度以及不稳定边缘点的判定条件式：

比较特征点对应的上式取值绝对值的大小与0.03之间的关系，若大于0.03，则该特征点作为保留特征点，否则丢弃该特征点。同样对于横跨在边缘的像素而言，高斯算子具有比较大的曲率，垂直于边缘有较小的主曲率[8]，求解主曲率的方式由下面的公式给出：

H矩阵称为hessian矩阵，为2×2的一个矩阵。根据曲率与hessian矩阵特征值之间的正比例关系，假设α，β分别对应于比较大的特征值和较小的特征值，有：

再将α=γβ代入上式：

Lowe提出的理论认为当（α+β）/αβ的值大于（r+1）2/r时视为主曲率不在阈值范围内，则丢弃该点。

1.6 为关键点加上方向

上面的步骤中最后剔除了不稳定的、低对比度和边缘的关键点，剩下精确关键点作为最后的特征点，为了保证这些特征算子对旋转平移等变化的稳定性，需要为特征点加上一个方向向量。具体的做法在于首先计算出每个特征点的方向，再通过统计该像素周围领域内一些像素的梯度方向信息，即绘制梯度直方图，梯度直方图的绘制方法在于，根据角度的取值范围是0度到360度，选择十度为一个单位，因此直方图一共有36个统计柱。Lowe认为为了排除一些突然的变化带来的干扰，可以首先对直方图进行高斯平滑[9]。

根据领域梯度方向直方图的统计结果确定一个方向参数赋予该特征点，由此来实现该特征点对于旋转的不变性，由领域梯度方向决定该方向的图示如下。

统计后取直方图取值最大即峰值时对应的方向值为该特征点的主要方向。

图5

图6

对于某一像素点，该点的梯度模值和对应的方向的计算公式如下所示：

L代表的即为上面所述特征点所处在的尺度空间。所以最终得到的关键点的信息就由几部分构成：特征点的位置信息，特征点的方向信息以及特征点对应的尺度信息。为了保证具有旋转不变的特性，将坐标轴移到以特征点的方向为准的方向，这样可以保证对旋转的稳定，并且以特征点为中心位置取周围8×8区域的窗口空间，如图7～8所示，每一个小方格内的箭头指向为该店所在像素即特征点的领域像素对应的梯度方向，而箭头长度的大小则对应该像素梯度的模值大小，取带权的圆形模板覆盖的区域为需要进行高斯运算的范围，再划分的4×4的子区域内统计领域像素梯度方向的直方图，形成种子点，由此可知对于一个特征点而言对应于四个种子点，而每一个种子点又含有八个方向信息[10]。这样处理的目的在于使得匹配算法具有更好的匹配容错能力，对于误匹配的纠错具有良好的效果，并且能够很好地抵抗噪声的干扰

1.7 使用特征描述子进行匹配

待匹配的两幅图像获得各自的特征点以及对应特征点的SIFT特征描述子后，要对两幅图像进行匹配，即是对两幅图的特征描述子进行匹配。由于特征描述子为多维的特征向量，向量之间的匹配方式，在于计算两个向量之间的相似性。度量二者之间的相似程度往往通过构造相似性测度函数，计算度量函数的最值，函数的取值反映的则是参与比较的二者之间的相似性程度。这里由于是对向量的相似性进行比较，因此可以采用几何手段实现，欧氏距离则是反映向量之间距离的度量准则，欧氏距离值越小表明二者越接近，若二者的欧氏距离为0则表示两个向量相同，否则欧氏距离越大，二者的相似程度越低。具体的匹配方法是对其中某一图像的关键点的特征向量，在另外一幅图中寻找与该特征向量欧氏距离最小的两个特征向量对应的关键点。在这两个关键点中距离更小的值与距离次小的值、的比值在某个阈值范围内，则认为该关键点的对应匹配点即为距离最小的特征向量对应的关键点，二者构成一对匹配点对，否则视为非匹配点对，丢弃。匹配结果与阈值大小具有密切的关系，阈值的确定影响匹配的效果，当阈值取值较大时，满足匹配的点会增多，因此会有比较多的误匹配出现，匹配的过程表现得不稳定，反之如果降低阈值的取值，则会使得很多误匹配的点被丢弃，匹配过程稳定，此时满足匹配条件的匹配点的数量则会减少。

图7

1.8 实验结果

实验中使用平行的双目视觉系统对同一时刻的三维空间物体进行拍摄，左、右摄像机由于视角的不同，拍摄到两幅图像分别如下图所示：

图9

图10

对两幅图像进行SIFT算法特征匹配的结果为：

图11

2 结语

根据理论描述以及实验的结果显示，SIFT特征是一种尺度不变的图像局部特征，SIFT特征对于图像的旋转、平移、缩放以及对于光照条件的改变和噪声的干扰都具有较好的鲁棒性，对于实验中视角发生变化的情况，也具有良好的匹配效果，即使是存在目标物体的遮挡，也是实现匹配的有效手段。SIFT在图像匹配领域的优势使得它在图像处理以及机器视觉等各个领域都有着重大的研究意义，越来越成为图像检索、智能交通管理系统、模式识别，甚至是工业应用中的发展热点。图像匹配目前尚不存在可以适用于各种情况的通用匹配算法，各大算法都需要综合匹配算法的计算量、运行所耗费的时间、匹配的准确性以及匹配效果等各方面的因素。多维的SIFT特征包含了图像的很多信息，能够满足匹配效果的要求，并且SIFT算法的匹配时间较短，在一些对实时性要求比较高的应用场合，可以满足对时间性能的要求。SIFT特征匹配是一种快速而且较精准的匹配算法，具有良好的应用价值和重大的研究意义。

[1] L0WE D．Object Recognition from Loca1 Sca1e-Invariant Features[C].Internationa1 Conference on Computer Vision．Greece：ICCV，1999：1150～1157

[2] LOWE D．Distinctive Image Features from Sca1e-Invariant Keypoints[J]．Internationa1 Journa1 of Computer Vision，2004，60（2）：91～110

[3] 张朝伟，周焰，吴思励．基于SIFT特征匹配的监控图像自动拼接[J]．计算机应用，2008，28（1）：191～194

[4] 孙剑，徐宗本．计算机视觉中的尺度空间方法[J]．工程数学学报，2005，22（6）：951～962

[5] LINDEBERG T P．Interna1 Report TRI TA-NA-P8808[R]．Stockho1m，Sweden：Roya1 Institute of Techno1ogy，2000

[6] 李晓明，郑链，胡占义．基于SIFT特征的遥感影像自动配准[J]．遥感学报，2006，10（6）：885～891

[7] WITKIN A P．Sca1e-Space Fi1tering[C].Proc．7th Internationa1 Joint Conference on Artificia1 Inte11igence．[S．I．]：IJCAI，1993：1019～1022

[8] BABAUD J，W1TKIN AP，BAUDIN M，et a1．Uniqueness of the Gaussian Kerne1 for Sca1e-Space Fi1tering E J]．IEEE Transactions on Pattern Ana1ysis and Machine Inte11igence，1986，8（1）：26～33

[9] LINDEBERG Tony．Discrete Derivative Approximations with Sca1e-Space Properties：a Basis for Low-Leve1 Feature Extraction[J]．Journa1 of Mathematica1 Imaging and Vision，1993，3（4）：349～376

[10] LINDEBERG T．Sca1e-Space Theory：a Basic Too1 for Ana1yzing Structures at Different Sca1es EJ]．Journa1 of App1ied Statistics，1994，21（2）：225～270

Image Feature Matching Based on SIFT Algorithm

ZHOU Ying
（Co11ege of Computer Science，Sichuan University，Chengdu 610065）

The princip1e of SIFT feature matching a1gorithm is to generate SIFT feature vector of the characteristic points,through the matching of feature vector to rea1ize the matching of the images.SIFT feature is a kind of 1oca1 image characteristics which is invariant to image sca1e. Expounds the specific process of how SIFT feature vector is generated,inc1uding the bui1ding of the sca1e space,the detection of the key points and accurate1y positioning these points,determines the direction of the feature vector,and fina11y form the SIFT features vector and according to the vector to rea1ize the image matching.According to the experimenta1 resu1ts it is conc1uded that SIFT a1gorithm can effective1y and accurate1y rea1ize the matching of images.

Image Matching;SIFT Feature Matching;Sca1e Space;Direction Vector;Feature Descriptor

1007-1423（2015）05-0063-06

10.3969/j.issn.1007-1423.2015.05.014

周颖，女，四川成都人，研究方向为图形图像处理

2014-12-11

2015-01-20

国家自然科学基金（No.60903118、No.60832011）