毕业设计(论文)-基于数字图像处理的SIFT算法的研究.doc

太原科技大学毕业设计（论文）

太原科技大学

毕 业 设 计（论 文）

设计(论文)题目：基于数字图像处理的SIFT算法的研究

姓 名
学院（系） 电子信息工程学院
专 业 测控技术与仪器
年 级
指导教师

2016年 6月 日

基于数字图像处理的SIFT算法的研究

电子信

摘要：人类获取信息的方式都包括触觉、嗅觉、视觉、听觉等，而视觉更是人类获取外界信息最重要的方式,受视觉的启发,人类开始着手研究如何让机器拥有一套类似于视觉的获取外界信息的渠道,于是在二十世纪五十年代计算机视觉领域应运而生,无数人都在这一门崭新的领域内倾尽心血进行探索,随后,Marr教授在总结前人的基础上提出了最为具体的计算机视觉理论框架体系。在计算机视觉理论当中,关于图像特征点的提取就是一个经典难题,为了更好的提取稳定的特征点,学者们做出了众多的探索,SUSAN算子、Harris算子和SIFT算子等特征点的提取方法就是在这不断探索中诞生的一小部分。在众多特征点的提取方法中,SIFT算法因其先天具有的多样优势从众多方法之中脱颖而出并且得到了较为广泛的应用,但是SIFT算法并没有做到尽善尽美，在实际运用中还存在着各种缺陷,计算维度过大导致运用SIFT算法在处理特征点的提取与匹配时无法满足我们对于算法实时性的要求,之后不断有学者对SIFT算法的缺点提出改进来加快原始SIFT算法的运算速度,常见的PCA-SIFT、SURF等改进算法就是这一时期基于SIFT算法提出改进所获得的果实。
本文首先简单介绍了计算机视觉和SIFT算法的发展背景和现状,在特征点的提取之中将SIFT算子和SUSAN、Harris算子进行横向比较突出SIFT算法的优越性,然后详细介绍SIFT算子的构建过程并通过仿真来展示特征点的提取效果,针对SIFT算法存在的实时性不强的缺点,本文将通过纵向比较的方法来简要介绍近年来学者们对于SIFT算法改进中运用较为广泛的的PCA-SIFT算法和SURF算法,随后通过使用计算机来模拟仿真实验展示两种改进算法对于特征点的提取效果，并具体说明在算法的改进之中所取得的成果。
关键词: SIFT， 特征点， 计算机视觉

The SIFT algorithm based on digital image processing research

College of Electronical and Information Engineering measurement and control 121202 YanTengfei Director：WangQinggang

Abstract：Human access to information in a way that includes a touch, smell, sight, hearing and, while vision is for people to obtain information from outside the most important way,
I

inspired by the vision, humans began to begin to study how to make the machines have a similar to visual access to outside information channels, so in the field of computer vision, in the fifties of the 20th century came into being, millions of people are in the a new field of introverted try hard to explore. Subsequently, Professor Marr on the basis of summarizing the proposed the specific computer vision theory framework. In the theory of computer vision, on the image feature points extraction is a classical problem, in order to better extract stable feature points, scholars have made many exploration, SUSAN operator and Harris operator and SIFT operator feature point extraction method is in this continuously penetrating the cable was born in a small part. In many feature points extraction methods, SIFT algorithm because of its innate has various advantages stand out from many methods and get more extensive application, but the SIFT algorithm did not achieve perfection. Various defects still exist in the practical application, dimension calculation through to use the SIFT algorithm in processing of feature points extraction and matching cannot meet we for real-time requirements. Later, scholars of SIFT algorithm improve shortcoming to accelerate the speed of operation of the original SIFT algorithm, common PCA-SIFT, SURF and improved algorithm is the period based on SIFT algorithm is proposed to improve the fruit.
This paper introduces the development background and present situation of computer vision and SIFT algorithm, the superiority of the more prominent SIFT algorithm in transverse feature extraction in SUSAN, SIFT operator and Harris operator, and then introduces the construction process of the SIFT operator and the simulation to demonstrate the extraction of feature points, according to the real-time SIFT algorithm the existence of weak, this will be through the longitudinal comparison method to introduce scholars in recent years for the more extensive PCA-SIFT algorithm and SURF algorithm with the improved SIFT algorithm, and then through the use of computer simulation experiments show the two algorithms for the extraction of feature points, and illustrates the fruit in the algorithm.
Key Words： SIFT, feature point, computer vision
II

目录

第1章 绪论 1
1.1 研究背景及意义 1
1.2 国内外研究现状 2
1.3 本文结构 2
第2章 SIFT算法 3
2.1 常见特征点提取算法的比较： 3
2.2 SIFT算子的建立过程 5
2.2.1 构建尺度空间 5
2.2.2特征点的选取 10
2.2.3特征点方向的确定 13
2.2.4生成特征点描述子 14
2.3 特征点的匹配 16
2.4 SIFT特征点的提取效果展示 16
2.4.1 尺度变化 16
2.4.2旋转变化 18
2.4.3亮度变化 20
2.5 SIFT算法的特点以及优劣势分析 21
2.5.1 SIFT算法的优点： 21
2.5.2 SIFT算法的缺点： 22
第3章 SIFT改进算法 22
3.1 PCA-SIFT(基于主成分分析的SIFT匹配算法) 22
3.2基于快速鲁棒性特征（SURF）的图像匹配技术 23
3.3三种算法的效率比较： 25
第4章 总结与展望 26
致谢 29
附录 30

III

第1章 绪论
1.1 研究背景及意义
视觉是生物获取信外界信息的重要方式。借助于光线,人与动物可以通过视觉去感知外物的明暗、大小、运动状态、颜色、条纹等特征信息,再借助大脑对这些信息加以加工处理。据统计,对于人类来说,多达80%的外界信息都是通过视觉来获取的。
受到视觉这种获取信息的重要方式启发,人们思考在进入计算机时代后,能否通过一系列的手段使计算机实现类似的效果。由此,计算机视觉应运而生。具体的说,计算机视觉就是使用摄像机来代替眼睛来获取图像,利用计算机来代替大脑去分析处理,并以此来实现图像处理、模式识别、图像理解等相关用途的一门科学。
计算机视觉的相关理论在二十世纪五十年代就已经出现,当时的理论主要用于分析识别二维图像,并且隶属于统计模式识别[1]之中。后来,直到二十世纪六十年代才开始将计算机视觉用于理解三位场景,此时最具有代表性的事件就是1965年Robert利用计算机来理解三维积木。随后,在1977年Marr教授提出了至今为止最为系统的视觉系统理论框架,即计算视觉理论(Computational Vision)[2]。在Marr教授的框架中,计算机视觉的分为三个层次:
1.计算理论,第一个层次用来研究系统各组成部分的职能和其各自信息流之间的联系。
2.表达与算法,第二个层次主要用来介绍系统实现功能的步骤,过程,详细地对算法的实现原理尽享讲解。
3.实现,第三个层次则是从硬件和软件两个方面来实现某个系统的功能。
同时,Marr教授讲立体视觉系统由低到高分成三个阶段:
1.初级视觉阶段,此阶段主要实现提取二维数字图像的特征信息,如角点、边沿、边界等,并将提取出的这些信息集合转变为要素图,本文研究的SIFT算法即位于此阶段。
2.中级视觉阶段,此阶段可以实现向系统之中输入二维图像与第一阶段提取出的要素图后,部分恢复图像拍摄场景的深度信息。
3.高级视觉阶段,此阶段可以实现想系统输入两幅图像,要素图后,得到关于场景的三维表达。
计算机视觉的运用及其广阔,可以用于对于照片或视频资料的解释,比如通过天体照片、航空资料就可以很具体的分析出卫星天体的三位特性,而且在精确制导、智能机器人、医学诊断、视觉导航、智能人机接口等众多领域领域也起到了非常重要的作用。
在计算机视觉领域中的一个经典难题就是特征的提取与匹配,如何在各种不同的环境条件下获取到稳定的特征描述点一直是都一个经久不衰的热门话题。因此,在十九世纪八十年代,计算机视觉领域形成了视觉不变量理论的崭新研究方向。视觉不变量理论旨在寻找在光线改变、尺度变换、物体的三维移动、放射、透视等等条件下仍能保持不变的特征。随后在角点特征的提取方面应运而生地出现了诸如SIFT算子、SUSAN算子、Harris算子等一系列的算法研究,而本文将要主要研究的就是现今应用最为广泛的SIFT算法。
1.2 国内外研究现状
对于计算机视觉,目前计算机视觉理论发展迅速,近年来不断取得崭新的理论成果。日本大阪的Mioru研究出更为先进的双目视觉系统可以智能的实现对于运动物体的实时追踪[3];美国华盛顿大学设计出可以用来探测外形的"探测者"系统可以根据图像的视觉差重建物体的三维构造[4];美国麻省理工大学开发出的交通传感系统可以准确的对高速车辆进行区分和提取[5]等等。
对于SIFT算法,翻译过来也就是具有尺度不变特征变换匹配算法(Scale Invariant Feature Transform),该算法由加拿大英属哥伦比亚大学的罗伊教授(David G.Lowe)于1999年发表于计算机视觉国际会议(International Conference on Computer Vision,ICCV)上[6],随后他又在总结完善后于2004年在计算机视觉国际期刊(International Journal of Computer Vision,IJCV)上发表相关的总结文章[7]。这种算子对于数字图像的亮度改变、尺度改变、旋转改变都可以保持相当的稳定性,而且由于SIFT算子在立体空间和频域空间内都可以很好的被局部化,可以降低噪声的干扰,基于该算法所具有的种种优点,目前SIFT算法比较广泛的被应用于人脸识别[8]、图像配准[9]、图像拼接[10]、创建地图[11]与定位机器人[11]、目标的识别[12]等各个领域,(参考文献见基于SIFT算法的图像匹配_刘佳)是现如今应用最为广阔的一种局部特征描述算子。近年来,M.Brown在其文章Recognising Panoramas中使用SIFT算法,自动完成实现了图像配准;Grabner尝试利用积分图像对SIFT算法进行改进加快运算速度;Delponte尝试利用SVD来实现特征点的匹配;Mikolajczy提出了GLOH(梯度的位置和方向直方图)。另外由于SIFT算法的实时性比较差，在运用到实际操作时无法满足实时性的要求,因此近几年不断有学者尝试对SIFT算法进行改进，应运而生出如PCA-SIFT,SURF,GLOH等各种关于SIFT的改进算法。可以毫不夸张的说,SIFT算法的提出,在特征点的提取方面起到了里程碑式的重要作用，为计算机视觉画下了浓墨重彩的一笔
1.3 本文结构
第一章 绪论。本章内容主要简单的介绍了计算机视觉的背景及发展意义,并由此引入了本文将要重点探讨的内容,SIFT算法的提出背景和主要研究内容等。
第二章 SIFT算法。本章是本文的主体内容,将会重点介绍SIFT算法的相关内容。本章分为四个小节：1.第一小节内容是有关于常用特征点提取算法的比较的,本节会介绍集中常见的特征点提取方法并与SIFT算法进行全方面多角度的比较,并表现SIFT算子的优越性。2.第二小节将会从理论角度具体介绍SIFT算子的建立过程,详细介绍SIFT算子的建立实现过程。3.从理论上解释了SIFT算子的提取方法之后,第三小节将会通过计算机仿真来展示实际应用时
4.SIFT算法所提取的特征点的实际效果,分别展示数字图像在发生旋转变化、尺度变化、亮度变化时使用SIFT算法提取特征点进行匹配的实际效果，证实该算法所具有的稳定性。4.第四小节内容是SIFT算法的特点及优劣势分析,本小节具体总结SIFT算法提取特征点的特点以及优缺点。
第三章SIFT改进算法,本章将简要介绍近几年人们对于SIFT的几种改进算法,如PCA-SIFT、SURF算法,并通过模拟仿真来观察其改进的实际效果。
第四章 总结与展望，总结写本文的收获以及对于还领域未来发展方向的展望。
第2章 SIFT算法
2.1 常见特征点提取算法的比较：
1.SUSAN算子:SUSAN(Smallest Univalue Segment Assimilating Nucleus)是由Simith.S.M和Brady.J.M提出的[13],该算法通过使用一个拥有37个像元的圆形模板来计算检测位于模板范围内的USAN(核同值)的面积大小,并以此判断该像素点是否是图像之中的角点。由图可以看出,该算法提取的角点对噪声不敏感,抗噪能力比较好,提取角点较为集中,但是在一些区域的信息冗余而且有假点出现。SUSAN对于图像的特征点提取效果如图2.1所示。
2.Harris算子:Harris是由C.Harris和J.Stephens于1998年提出一种经典的特征点检测算子[14],该算法是一种关于角点特征的提取算法,Harris算子在处理纹理信息较少的数字图像时会提取到比较少的特征点,可是如果数字图像的纹理信息丰富，那么使用Harris算子则可以在数字图像种提取到大量有用的特征点,同时利用Harris算子所提取的角点包含有较多的结构信息,所提取的角点多集中在边缘和边缘的交叉地带,角点的分布平均且合理,定位精度达像素级,而且如果图形发生平移变化、旋转变换,Harris算子依旧能够稳定的找到对应的特征角点。
Harris角点的定义式见（式2-1）:
（式2-1）
式中:M：和自相关函数关联的矩阵
K：经验常数,通常情况下经验常数k的取值会在0.04到0.06之间合理选取
在应用通过计算图像之中每个像素的梯度,人为的设定一个用来比较的阈值,如果数字图像之中某个像素点最终计算所得的R值大于预先设定的阈值并且取得邻域的最大值,那么这个像素点就是我们需要的Harris角点。当然,Harris角点的提取在这里只是简要的提到了一下,这里不作为重点去讨论。Harris算法对于图像的处理效果如图2.2所示。
3. SIFT算法则可以提取具有丰富的纹理和尺度信息的多尺度亚像素级特征点(SUSAN算子和Harris算子提取出的角点都是像素级的),由于空间维度大，计算的复杂程度也比之前两种算法要高,耗费时间理所当然的也会长些,作为耗时久的收获,使用SIFT算法提取出的特征点相比于前面两种算法所提取出的特征点具有更好的鲁棒性。关于SIFT算法的详细内容我们会在下一小节的内容之中详细介绍。SIFT算子的提取效果如图2.3所示。
图 2. 1 SUSAN算子 图 2. 2 Harris算子
图 2. 3 SIFT算子
2.2 SIFT算子的建立过程
SIFT算子的建立过程大体上如图2.4所示,可以分为构建尺度空间、特征点的选取、特征点方向的确定、生成特征点描述子四个步骤,接下来本文将详细介绍每一个步骤的原理及方法。

图 2. 4 SIFT算子的建立
2.2.1 构建尺度空间
构建尺度空间当人类用肉眼观察某一特定物体时，在能视范围内不管我们距离物体有多远，我们都可以得出一定的结论。就拿狗来举例，无论我们是在1米的距离观察，还是在10米的距离观察，我们的大脑最后都会意识到，这是一条“狗”。可是计算机不同，在使用计算机视觉分析一个未知的场景时，计算机并没有办法提前预知物体的实际尺寸，这就要求我们应该提前将同一物体在不同尺度下呈现出的图像画面输送给计算机，并告知计算机这些图像画面指的是同一物体。深究起来，人类的视觉也是同样道理，人眼之所以能够在不同尺度下区分出同一物体，正是因为人类自身已经在不知不觉间建立起了一个在任何尺度下都不换会发生改变的特征库（比如说猫的外形，猫身上的条纹等等）。而构建SIFT算子的第一步构建尺度空间就是描述图像在所有尺度下的表示，向计算机输入同一物体在不同尺度下的情形。
1、LOG尺度空间
David Lowe在其文章中提到高斯卷积核是实现初步变换的唯一线性核。一幅数字图像在不同尺度下的尺度空间表示可以用数字图像与高斯核的卷积得到，见（式2-2）:
（式2-2）
公式中：
*:卷积运算。
(x,y):图像中像素点的坐标。
:输入图像。
:是图像的尺度空间。
:尺度可变的高斯函数。
函数变量σ是尺度因子，σ的取值较小时最终处理得到的数字图像被平滑程度小，可以反映图像的细节信息；σ取值较大时最终处理得到的图像被平滑程度大，可以反映图像的概貌信息。
以下几张图（图2.5-图2.9）是尺度因子σ由小到大取值时生成的图像，可以很直观的看到图像处理的效果
图 2. 5 原图
图 2. 6 σ=0.5 图 2. 7 σ=2
图 2. 8 σ=3.5 图 2. 9 σ=5
2、DOG尺度空间
LOG算子的构造对于每一个尺度空间都要计算,需要巨大的计算量,为了更加高效地找出稳定的特征点的位置,Lowe提出了利用高斯差分卷积函数来构造尺度空间。
高斯差分函数DOG(Different of Gaussian)在SIFT算法之中通常被定义为两个不同尺度的高斯核的差分。
DOG算子的定义见（式2-3）:
（式2-3）
上式中，k为两个相邻层间尺度相差的比例因子。
DOG是归一化LOG（Laplacian of Gaussian）算子的近似，而LOG算子也就是对高斯函数进行拉普拉斯变换（式2-4）：
(式2-4)
他们之间近似的关系如(式2-5)所示：
(式2-5)
通常简写为（式2-6）：
(式2-6)
K：比例因子,作为一个常量,k的取值并不会对极值的寻找产生干扰。
在得到DOG图像之前,首先我么需要着手构造一个高斯金字塔。在说高斯金字塔前我们首先需要来介绍一下图像金字塔。
图像金字塔是同一组图像在不同分辨率下抽样得到的结果,一般的讲。图像金字塔化由两步构成:
1. 使用低通滤波器对图像进行平滑处理,直观的讲,进行这一步骤以后图像会变的模糊,就好像人无法看清晰某件物体一样。如图2.10和2.11所示效果。
图 2. 10 处理前 图 2. 11 处理后
2.对经过第一步骤后平滑处理的图像进行降采样，从而生成一系列不同尺寸的数字图像。通常来说,抽样比例我们会选择1:2.如图2.12所示
图 2. 12 降采样示意图
而高斯金字塔则是在进行上述步骤的第一步时,我们则是使用不同的对图像金字塔的每层图像进行处理生成高斯图像,在获得高斯图像以后,对图像进行降采样，生成高斯金字塔。
我们将高斯金字塔的数字图像假设分为m阶,而同阶图像又可以分为n层,同阶内不同层之间的数字图像的尺度大小存在差异,相邻层的图像之间相差一个比例因子K，也就是说是相邻层间的图像是通过一个比例为k亚采样得到的。假设我们即将构造的高斯金字塔每阶图像有m层,那么k的取值就应当是。与此同时,在金字塔高一层的图像通常情况下是由前一层数字图像进行因子为2的降采样所得,根据前面介绍的相关内容我们已经了解到了DOG图像的生成则是通过高斯金字塔图像相减得到的。所以如果想要在DOG尺度空间的p层中检测极值点就需要p+2层的DOG尺度空间,此时,相对应的LOG尺度空间就需要有p+3层,这样做的原因我们将会在下一小节特征点的选取部分详细说明。差分高斯金字塔的构建步骤参照图2.13所示

图 2. 13 DOG的构建
2.2.2特征点的选取
在构造完差分金字塔以后我们就要开始着手于检测DOG的局部极值点。总的来说,检测出符合标准的局部极值点作为特征点待用大体上需要两个步骤，如图2.14所示。

图 2. 14 构建特征点流程图
1.取尺度空间的极值点：生成尺度空间以后，将各采样点与同层尺度空间的8个像素点以及上下层尺度空间的18个像素点（上层尺度空间和下层尺度空间各有9个像素点）的灰度值进行比较，如果采样点的灰度值均大于或者小于与之相比较的其余26个像素点，就记录下该采样点的位置和其待在的尺度作为候选特征点，等待进行后续操作。具体对比方法可以参考图2.15。

图 2. 15 空间极值点的选取
在进行灰度值的极值比较时，由于每阶图像的第一层和最后一层都缺少一个向邻近的图像层，所以这两层是无法进行灰度极值比较的，此时我们需要将每一阶图像的最顶层继续用高斯模糊生成三张图像。具体的来说，假设每组图像有3层，s=3，按照前面的公式可以计算得出，第一阶LOG尺度空间对应的三层图像、、，第二阶LOG尺度空间对应的三层图像、、。按照之前步骤生成的第一阶DOG尺度空间上的图像为、，第二阶DOG尺度空间上的图像为、。我们无法对这两层图像进行极值比较，此时我们应该在LOG尺度空间内的每一层都继续使用高斯模糊额外生成三张图像，经过这一步后，第一阶LOG尺度空间上的图像为、、、、、，第二阶LOG尺度空间上的图像为、、、、、。由这两阶图像相减分别可以得到第一阶DOG尺度空间为、、、、，第二阶DOG尺度空间为、、、、。这样，在做极值检测时，我们就可以选择有两个临近层的图像进行比较，在本例中分别选取、、和、、的图像进行极值检测。具体过程见图2.16。
图 2. 16 检测示意图
2.上述的提取步骤很明显对噪声以及边缘会比较敏感，因此提取出的候选特征点中有一部分是需要去除掉的。也就是说我们对提取出的每一个候选特征点验证其是否是噪声点或者边缘点，如果属于，那么就应该去除掉；如果不属于上述两个种干扰点，那么就应该保留该候选特征点并且对其精准定位，使之精度达到亚像素级别[15]。具体步骤如下：
(1)剔除低对比度的点
因为上述候选特征点是从离散的DOG尺度空间提取出的，而离散空间是对连续空间抽样采集的结果，所以在离散空间判断出的极值点不一定是连续空间上的极值点，因而我们应该将不符合我们期望的点去除，Lowe教授为此就提出拟合三位二次方程的办法，这里就需要利用二元函数的泰勒展开式，对DOG算子的定义式进行泰勒展开（式2-7）：
（式2-7）
上式中，x:比较的得到的极值点
:极值点的偏移量
当的倒数为零时即，就可以得到DOG函数的极值点，解方程（式2-8）:
（式2-8）
可以得到候选特征点的精确位置和尺度，将其带入式2-7中得到
（式2-9）
设定对比度阈值(在Lowe的文章中设定为=0.03)，将计算得到的结果和阈值进行对比，如果，那么对应的候选特征点符合特征点要求;反之,如果,那么对应的候选特征点应该作为低对比度点被剔除出去。
（2） 剔除边缘点
由于DOG算在对于边缘很敏感，所以应该设法剔除边缘效应的影响。根据数字图形的相关基础知识，像素点如果位于图像边缘的话，那么该点在沿边缘梯度方向上会有较小的的主曲率值，而在垂直于边缘梯度方向上则会有较大的主曲率值，所以DOG函数在边缘上提取到的待选特征点的主曲率值会大于在非边缘上提取的候选特征点的主曲率值。因此，我们利用这一性质，可以设定一个阈值，如果某一候选特征点的主曲率值大于这一阈值，那么这一候选特征点将看作是位于边缘上而剔除，如果某一候选特征点的主曲率值小于这一阈值，那么这个候选特征点将看作不位于边缘上保留下来。具体方法如下：
为了表示候选特征点的主曲率，我们需要引入一个2x2的Hessian矩阵H（式2-10），
（式2-10）
在矩阵H中，Dxx,Dyy,Dxy,Dyx表示候选特诊点的邻域内的像素差分
DOG函数D（x）的主曲率和Hessian矩阵H的特征值成正比。如果直接计算矩阵H的特征值的话计算量会很大，这里采用一种叫简便的办法，假设矩阵H中较大的特征值为a,矩阵H种较小的特征值为b，那么利用矩阵的相关知识可以得到式2-11、式2-12：
矩阵H的迹： （式2-11）
矩阵H的行列式： （式2-12）
令c为较大特征值与较小特征值的比值即式2-13：
（式2-13）
那么D（x）主曲率的比值将和c成正比关系，所以式2-14成立：
（式2-14）
上式的值与特征值的数值无关，只与特征值之间的比值有关。当矩阵H的两个特征值相等时，式取得最小值，随着特征值比值c的增加其最终的取值也越来越大。因此，我们如果想要剔除主曲率值大的点，只需要剔除比率大于某一阈值的候选特征点即可（Lowe在其文章中取c=10），即判断式2-15是否成立即可。
（式2-15）
若是式2-15成立，则候选特征点满足要求。
若是式2-15不成立，则候选特征点作为边缘点剔除。
2.2.3特征点方向的确定
挑选出合适的特征点以后，为了实现特征点在图像发生旋转时提取依旧稳定，就需要为选择出的合适的特征点添加方向描述，SIFT算法采用的是参考Schmid的方向不变的描述方法[16]，利用关键点邻域像素的梯度直方图来确定特征点的主方向和副方向。
前面的步骤在定位特征点的位置的同时，也就确定了特征点的尺度σ，根据σ，选择最接近的高斯图像,从前面的章节我们知道，高斯图像的生成式2-16：
（式2-16）
之后，以每一个特征点L(x,y)为圆心，1.5σ为半径，计算特征点邻域内的像素的梯度模值（式2-17）和方向（式2-18）
梯度模值： （式2-17）
方向： （式2-18）
计算完毕后，以梯度方向角为横轴将360°分为10个区域，对应方向角上梯度幅值的累加值为纵坐标绘制梯度直方统计图。指的注意的一点是，为了增强临近特征点的邻域像素点对于特征点的影响，特征点邻域的像素点其权重由高斯权重来确定，也就是说，距离特征点越远的像素，其对于梯度直方图的贡献也就越小。
在生成梯度直方图后，选择峰值最高的方向角作为特征点的主方向，如果在梯度方向直方图上还有另外一个或以上的峰值的取值达到了主方向上峰值的80%以上，就称其对应的梯度方向为副方向。一般来说，大约15%左右的特征点都具有多个方向。
在确定特征点的主方向后，现在特征点的描述包含四个参数x,y,σ,θ，接下来就到了生成特征点描述子的时候了。
2.2.4生成特征点描述子
在前面步骤中，我们已经为特征点赋予了位置信息、尺度信息、方向信息。接下来我们就利用一组向量来将这个特征点描述出来了，这一步走也就称之为特征点描述自身的生成。Lowe在生成特征点描述子时采用了一种遗传学算法，需要分三步来进行：
1. 校正旋转主方向
校正旋转主方向，是为了保证算子的旋转不变性，将坐标轴以特征点为圆心，将其邻域旋转θ°。（θ也就是特征点的主方向对应的角度），旋转后的坐标轴发生改变式2-19：
（式2-19）
2. 生成描述子
以特征点为中心选取一个16×16像素的矩形窗口（也可以选择其他大小的矩形窗口，但是从运算速度和匹配稳健性角度上来讲，建议采用16×16的矩形像素区域）。利用前面章节的内容，计算窗口中每一个像素点的梯度方向和梯度幅值，有一点值得注意，这里的梯度方向划分与前面章节不同，在对特征点进行方向赋值时，我们将梯度方向划分为10个方向，而此时我们则是将梯度方向划分为8个方向。随后将这16×16的像素区域均匀地分成16个4×4大小的小像素区域，利用以特征点为中心的高斯窗口，利用加权运算分别计算每一个小像素区域的梯度方向和梯度幅值信息，随后生成一个具有4×4个划分的梯度信息矩阵块，称此时我们有了16个种子点描述。此时，对于一个特征点来说，就有了4×4×8=128（16个种子点和8个梯度方向）个数据的描述数据，即生成了128维的特征向量。图2.17非常鲜明的展示了这一计算过程，

图 2. 17 描述子生成
图中：
圆形代表高斯窗口
每一个小矩形代表着一个像素点
稍大的矩形表示生成的种子点
矩形内指向八个不同方向箭头代表着梯度信息，箭头的方向代表着梯度方向，箭头的长度代表着梯度的模值。
此时的特征点描述子已经解决了图像在旋转、尺度变化等情形对检测造成的影响。
3. 对特征描述子进行归一化处理
为了解决对于光线变化造成的影响，我么还需要归一化处理每一个特征向量，方法如下：
假设D为特征点描述子，那么根据前面的相关内容我们知道，D是一个128为的向量，即

对D进行归一化处理式2-20：
式（2-20）
2.3 特征点的匹配
SIFT算法在实际应用时，通常会遇到特征点匹配问题。在实际应用中，通常一幅数字图像作为基准图像，另外一幅数字图像作为待匹配图像，特征点的匹配也就是在基准图像和待匹配图像之中分别寻找有着某种对应关系的特征点。特征点的匹配算法多种多样，本文将大致介绍基于欧氏距离的特征匹配。
欧式距离（euclidean metric）是目前应用最为广泛的距离定义，它指的是在一个多维空间内两点之间的真实距离，在我们比较熟悉的二维空间和三位空间之中，两点之间的欧氏距离指的就是这两点之间的实际长度。
根据欧式距离的定义不难看出，基于欧式距离的特征匹配也就需要我们计算各个特征点之间的距离情况，实际操作时的步骤如下：
1. 依次选定每一个特征描述子，计算其余特征点对应的特征向量与选定点的欧氏距离。
2. 记录每一个特征描述子与其他特征向量之间的最小欧氏距离和次下欧氏距离。
3. 计算最小欧氏距离与次小欧氏距离的比值。
4. 设定一个比例阈值用来和3步之中的比值做比较。
5. 如果设定的阈值大于最小欧氏距离与次小欧氏距离的比值，那么对应的两个特征点即匹配成功；反之，如果设定的阈值小于最小欧氏距离与次小欧式距离之间的比值，那么相对应的两个特征即匹配失败。
通常情况下，我们取阈值为0.6，并且如果实际取得阈值增大，那么最终匹配的特征点的数目就是增多，但匹配的正确率会有所下降；如果实际取得的阈值减小，那么最终匹配的特征点的数目就会变少，好处是这样做的话最终匹配的正确率会提高。
2.4 SIFT特征点的提取效果展示
2.4.1 尺度变化
在这一步，我们将会研究图像发生尺度变化（缩放）时，SIFT算法对于特征点的提取效果。图像尺度变化的变换效果如图2.18所示，一幅图像在经过尺度变换之后其大小将会发生改变，会出现水平方向和垂直方向上均匀的拉伸或压缩。

图 2. 18 图像尺度变化
在二维空间中，假设点（x,y）在经过尺度变化之后变换到（x’,y’）那么其对应的变换关系可以由下式来表达：
（式2-21）
上式中：mx:水平方向上的伸缩系数
my:垂直方向上的伸缩系数

图2.19、2.20，则是图像在发