SIFT算法实现原理步骤

SIFT算法实现步骤 ：1 关键点检测、2 关键点描述、3 关键点匹配、4 消除错配点

参考链接：

1关键点检测

1.1 建立尺度空间

根据文献《Scale-space theory: A basic tool for analysing structures at different scales》我们可知，高斯核是唯一可以产生多尺度空间的核，一个图像的尺度空间，L（x,y,σ) ,定义为原始图像I(x,y)与一个可变尺度的2维高斯函数G(x,y,σ) 卷积运算。

(xxi)2(yyi)21高斯函数 Gxi,yi,exp2222

Lx,y,Gx,y,*Ix,y

高斯金字塔

Octave 5Octave 4Octave 3…高斯金字塔的构建过程可分为两步：

4（1）对图像做高斯平滑；

（2）对图像做降采样。

2为了让尺度体现其连续性，在简单 下采样的基础上加上了高斯滤波。 一幅图像可以产生几组（octave） 图像，一组图像包括几层 （interval）图像。 高斯图像金字塔共o组、s层， 则有：

sSS(s)2 o1o

σ——尺度空间坐标；s——sub-level层坐标；σ0——初始尺度；S——每组层数（一般为3~5）。

当图像通过相机拍摄时，相机的镜头已经对图像进行了一次初始的模糊，所以根据高斯模糊的性质：

0initinitprepre

 init-第0层尺度  pre--被相机镜头模糊后的尺度

高斯金字塔的组数: O  log min M ,N 3 M、N分别为图像的行数和列数

2

高斯金字塔的组内尺度与组间尺度:

组内尺度是指同一组（octave）内的尺度关系，组内相邻层尺度化简为：

1

s1s2S

…8…Octave 2…Octave 1…1

-

组间尺度是指不同组直接的尺度关系，相邻组的尺度可化为： ssSsSS(s)02o22o2S

最后可将组内和组间尺度归为：

1 Si12n1k22(,k,k,k)

i—金字塔组数 n—每组层数

上一组图像的底层是由前一

组图像的倒数第二层图像隔点采样生成的。这样可以保持 尺度的连续性。

二维卷积：

差分高斯金字塔

Lindeberg在文献《Scale-space theory: A basic tool for analysing structures at different scales》指出尺度规范化的LoG算子具有真正的尺度不变性。

LoG算子即（Laplacion of Gaussian）,可以由高斯函数梯度算子GOG构建 尺度规范化的GoG算子：

2G2G2 G22xy

尺度规范化的LoG算子：  22GLOG算子与高斯核函数的关系

Gauss(x,y,k)Gauss(x,y,)

LOG(x,y,)22G 2(k1) Gx,y,kGx,y,k122G

通过推导可以看出，LOG算子与高斯核函数的差有直接关系，由此引入一种新的算子DOG（Difference of Gaussians），即高斯差分算子。

DoG（Difference of Gaussian）函数： 2

-

Lx,y,Gx,y,*Ix,yDx,y,Gx,y,kGx,y,*Ix,yLx,y,kLx,y,DoG在计算上只需相邻尺度高斯平滑后图像相减，因此简化了计算。

对应DOG算子，我们要构建DOG金字塔

我们可以通过高斯差分图像看出图像上的像素值变化情况。（如果没有变化，也就没有特征。特征必须是变化尽可能多的点。）DOG图像描绘的是目标的轮廓。

在Lowe的论文中，将第0层的初始尺度定为1.6，图片的初始尺度定为0.5，则图像金字塔第0层的实际尺度为 1.61.60.50.51.52

1.2 DoG的局部极值点检测

关键点是由DOG空间的局部极值点组成的。为了寻找DoG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。

中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。

在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，我们在每一组图像的顶层继续用高斯模糊生成了3幅图像，高斯金字塔有每组S+3层图像。DOG金字塔每组有S+2层图像。 3

-

1.3 关键点精确定位

由于DoG值对噪声和边缘较敏感,因此,在上面DoG尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点。

去除低对比度的极值点

为了提高关键点的稳定性，需要对尺度空间DoG函数进行曲线拟合。利用DoG函数在尺度空间的Taylor展开式：

T D1T2DXXXXDT2ˆD其极值点： Xx,y,X2X在计算过程中，分别对图像的行、列及尺度三个量进行了修正，其修正结果如下：

T D1T2DDXDXXX2 X2X求解得 T2DD X(2)1  XX X为修正值。 将修正后的结果代入式

T D1T2DDXDXXX X2X2T 1DDXDX 2X

上式去除那些对比度较低的不稳定极值点。Lowe的试验显示，所有取值小于0.04的极值点均可抛弃（像素灰度值范围[0，1]）。

去除边缘响应

仅仅去除低对比度的极值点对于极值点的对于特征点稳定性是远远不够的。DoG函数在图像边缘有较强的边缘响应，因此我们还需要排除边缘响应

DoG函数的（欠佳的）峰值点在横跨边缘的方向有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率可以通过计算在该点位置尺度的2×2的Hessian矩阵得到，导数由采样点相邻差来估计：

DxxDxy HDDxyyy

Dxx 表示DOG金字塔中某一尺度的图像x方向求导两次。 D的主曲率和H的特征值成正比，为了避免直接的计算这些特征值，而只是考虑它们

的之间的比率。令 为最大特征值， 为最小的特征值，则

r

TrHDxxDyy

DetHDxxDyyDxyDxy 222TrHr1 DetHr

4

-

 r1 2r 在两特征值相等时达最小，随r的增长而增长。Lowe论文中建议r取10。

22Tr H  r 1时将关键点保留，反之剔除。 DetHr

2 关键点描述

2.1 关键点方向分配

通过尺度不变性求极值点，可以使其具有缩放不变的性质，利用关键点邻域像素的梯度方向分布特性，我们可以为每个关键点指定方向参数方向，从而使描述子对图像旋转具有不变性。 通过求每个极值点的梯度来为极值点赋予方向。 像素点的梯度表示

IIgradIx,y,

xy 22mx,yLx1,yLx1,yLx,y1Lx,y1 梯度幅值：

1Lx,y1Lx,y1 梯度方向： x,ytanLx1,yLx1,y

方向直方图的生成

确定关键点的方向采用梯度直方图统计法，统计以关键点为原点，一定区域内的图像像素点对关键点方向生成所作的贡献。 直方图以每10度方向为一个柱，共36个柱，柱所代表的方向为像素点梯度方向，柱的长短代表了梯度幅值。 根据Lowe的建议，直方图统计半径采用3*1.5*σ 在直方图统计时，每相邻三个像素点采用高斯加权，根据Lowe的建议，模板采用[0.25,0.5,0.25]，并连续加权两次。

关键点的主方向与辅方向

关键点主方向：极值点周围区域梯度直方图的主峰值,也是特征点方向

关键点辅方向：在梯度方向直方图中，当存在另一个相当于主峰值80%能量的峰值时，则将这个方向认为是该关键点的辅方向。 这可以增强匹配的鲁棒性，Lowe的论文指出大概有15%关键点具有多方向，但这些点对匹配的稳定性至为关键。 5

-

方向分配实现步骤

1. 确定计算关键点直方图的高斯函数权重函数参数 ；

2. 生成含有36柱的方向直方图，梯度直方图范围0~360度，其中每10度一个柱。由

半径为图像区域生成；

3. 对方向直方图进行两次平滑；

4. 求取关键点方向（可能是多个方向）；

5. 对方向直方图的Taylor展开式进行二次曲线拟合，精确关键点方向； 图像的关键点已检测完毕，每个关键点有三个信息：位置、尺度、方向；同时也就使关键点具备平移、缩放、和旋转不变性。

2.2 生成特征描述符

描述的目的是在关键点计算后，用一组向量将这个关键点描述出来，这个描述子不但包括关键点，也包括关键点周围对其有贡献的像素点。用来作为目标匹配的依据，也可使关键点具有更多的不变特性，如光照变化、3D视点变化等。 通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。 下图是一个SIFT描述子事例。其中描述子由2×2×8维向量表征，也即是2×2个8方向的方向直方图组成。左图的种子点由8×8单元组成。每一个小格都代表了特征点邻域所在的尺度空间的一个像素，箭头方向代表了像素梯度方向，箭头长度代表该像素的幅值。然后在4×4的窗口内计算8个方向的梯度方向直方图。绘制每个梯度方向的累加可形成一个种子点，如右图所示：一个特征点由4个种子点的信息所组成。

关键点周围区域图像梯度关键点描述子 x

x

yy 6

3oct3oct3oct3oct -

Lowe实验结果表明：描述子采用4×4×8＝128维向量表征，综合效果最优（不变性与独特性）。

128维关键点描述子（就是特征描述符）生成步骤

1. 确定计算描述子所需的图像区域 描述子梯度方向直方图由关键点所在尺度的模糊图像计算产生。图像区域的半径通过下式计算：

32d11 radiusoct2

oct 是关键点所在组（octave）的组内尺度，d  4 2. 将坐标移至关键点主方向

x

x

yy 那么旋转角度后新坐标为：

ˆcossinxx ˆysincosy

3.在图像半径区域内对每个像素点求其梯度幅值和方向，然后对每个梯 度幅值乘以高斯权重参数，生成方向直方图。 dr 1-dcdc 1-dr

22 xkykweightgradIx,yexp1dr1dc1do 2w7

-

x k 该点与关键点的列距离 y k 该点与关键点的行距离  w 等于描述子窗口宽度 3  ×直方图列数（取4）的一半 4.在窗口宽度为2X2的区域内计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点。然后再在下一个2X2的区域内进行直方图统计，形成下一个种子点，共生成16个种子点。 5.描述子向量元素门限化及门限化后的描述子向量规范化。

描述子向量元素门限化：方向直方图每个方向上梯度幅值限制在一定门限值以下（门限一般取0.2）。

描述子向量元素规范化： W w1, w2, ,w 为得到的128描述子向量 128 L   l1 , l , l 128  为规范化后的向量 2,128

ljwj/wij1,2,128

i1 关键点描述子向量的规范化正是可去除满足此模型的光照影响。对于图像灰度值整体漂移 ，图像各点的梯度是邻域像素相减得到，所以也能去除。

3 关键点匹配

分别对模板图（参考图，reference image）和实时图（观测图，observation image）建立关键点描述子集合。目标的识别是通过两点集内关键点描述子的比对来完成。具有128维的关键点描述子的相似性度量采用欧式距离。

Riri1,ri2,,ri128 模板图中关键点描述子：

实时图中关键点描述子： Sisi1,si2,,si128128 2dR,Srsiiijij 任意两描述子相似性度量：

j1 要得到配对的关键点描述子， d R, S需满足：

ij 实时图中距离 Ri 最近的点 SjThreshold 实时图中距离 Ri 的次最近点 Sp 关键点的匹配可以采用穷举法来完成，但是这样耗费的时间太多，一般都采用一种叫kd树的数据结构来完成搜索。搜索的内容是以目标图像的关键点为基准，搜索与目标图像的特征点最邻近的原图像特征点和次邻近的原图像特征点。 Kd树是一个平衡二叉树

8

-

关键点匹配并不能标志着算法的结束，因为在匹配的过程中存在着大量的错配点。

图中交叉的绿线为错配点

4 消除错配点

RANSAC（Random Sample Consensus，随机抽样一致 ）是一种鲁棒性的参数估计方法。 RANSAC实质上就是一个反复测试、不断迭代的过程。 RANSAC的基本思想： 首先根据具体问题设计出某个目标函数，然后通过反复提取最小点集估计该函数中参数的初始值，利用这些初始值把所有的数据分为“内点”（ inlier ）和“外点“（outlier），最后用所有的内点重新计算和估计函数的参数。 9

-

RANSAC事例

如何估计最佳直线？

拟合直线：y=kx+b

重复进行，拟合最优直线 10