尺度不变特征变换匹配算法详解
Scale Invariant Feature Transform(SIFT)
Just For Fun
张东东zddmail@https://www.doczj.com/doc/5a3975682.html,
对于初学者，从David G.Lowe的论文到实现，有许多鸿沟，本文帮你跨越。
1、SIFT综述
尺度不变特征转换(Scale-invariant feature transform或SIFT)是一种电脑视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由David Lowe在1999年所发表，2004年完善总结。
其应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对。
此算法有其专利，专利拥有者为英属哥伦比亚大学。
局部影像特征的描述与侦测可以帮助辨识物体，SIFT特征是基于物体上的一些局部外观的兴趣点而与影像的大小和旋转无关。对于光线、噪声、些微视角改变的容忍度也相当高。基于这些特性，它们是高度显著而且相对容易撷取，在母数庞大的特征数据库中，很容易辨识物体而且鲜有误认。使用SIFT特征描述对于部分物体遮蔽的侦测率也相当高，甚至只需要3个以上的SIFT物体特征就足以计算出位置与方位。在现今的电脑硬件速度下和小型的特征数据库条件下，辨识速度可接近即时运算。SIFT特征的信息量大，适合在海量数据库中快速准确匹配。
SIFT算法的特点有：
1.SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；
2.独特性（Distinctiveness）好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；
3.多量性，即使少数的几个物体也可以产生大量的SIFT特征向量；
4.高速性，经优化的SIFT匹配算法甚至可以达到实时的要求；
5.可扩展性，可以很方便的与其他形式的特征向量进行联合。
SIFT算法可以解决的问题：
目标的自身状态、场景所处的环境和成像器材的成像特性等因素影响图像配准/目标识别跟踪的性能。而SIFT算法在一定程度上可解决：
1.目标的旋转、缩放、平移（RST）
2.图像仿射/投影变换（视点viewpoint）
3.光照影响（illumination）
4.目标遮挡（occlusion）
5.杂物场景（clutter）
6.噪声
SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出，不会因光照，仿射变换和噪音等因素而变化的点，如角点、边缘点、暗区的亮点及亮区的暗点等。
Lowe将SIFT算法分解为如下四步：
1.尺度空间极值检测：搜索所有尺度上的图像位置。通过高斯微分函数来识别潜在的对于尺度和旋转不变的兴趣点。
2.关键点定位：在每个候选的位置上，通过一个拟合精细的模型来确定位置和尺度。关键点的选择依据于它们的稳定程度。
3.方向确定：基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向。所有后面的对图像数据的操作都相对于关键点的方向、尺度和位置进行变换，从而提供对于这些变换的不变性。
4.关键点描述：在每个关键点周围的邻域内，在选定的尺度上测量图像局部的梯度。这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变化。
本文沿着Lowe的步骤，参考Rob Hess及Andrea Vedaldi源码，详解SIFT算法的实现过程。
2、高斯模糊
SIFT算法是在不同的尺度空间上查找关键点，而尺度空间的获取需要使用高斯模糊来实现，Lindeberg等人已证明高斯卷积核是实现尺度变换的唯一变换核，并且是唯一的线性核。本节先介绍高斯模糊算法。
2.1二维高斯函数
高斯模糊是一种图像滤波器，它使用正态分布(高斯函数)计算模糊模板，并使用该模板与原图像做卷积运算，达到模糊图像的目的。
N 维空间正态分布方程为：
)σ/(2r 22221
)(?=e r G N πσ（1-1）
其中，σ是正态分布的标准差，σ值越大，图像越模糊(平滑)。r 为模糊半径，模糊半径是指模板元素到模板中心的距离。如二维模板大小为m*n ，则模板上的元素(x,y)对应的高斯计算公式为：
22222)2/()2/(21
),(σπσn y m x e y x G ?+??=（1-2）
在二维空间中，这个公式生成的曲面的等高线是从中心开始呈正态分布的同心圆，如图
2.1所示。分布不为零的像素组成的卷积矩阵与原始图像做变换。每个像素的值都是周围相邻像素值的加权平均。原始像素的值有最大的高斯分布值，所以有最大的权重，相邻像素随着距离原始像素越来越远，其权重也越来越小。这样进行模糊处理比其它的均衡模糊滤波器
更高地保留了边缘效果。
图2.1二维高斯曲面
理论上来讲，图像中每点的分布都不为零，这也就是说每个像素的计算都需要包含整幅图像。在实际应用中，在计算高斯函数的离散近似时，在大概3σ距离之外的像素都可以看作不起作用，这些像素的计算也就可以忽略。通常，图像处理程序只需要计算
)16()16(+×+σσ的矩阵就可以保证相关像素影响。
2.2图像的二维高斯模糊
根据σ的值，计算出高斯模板矩阵的大小()16()16(+×+σσ)，使用公式(1-2)计算高斯模板矩阵的值，与原图像做卷积，即可获得原图像的平滑(高斯模糊)图像。为了确保模板矩阵中的元素在[0,1]之间，需将模板矩阵归一化。5*5的高斯模板如表2.1所示。
表2.15*5的高斯模板(σ=0.6)6.58573e-006
0.0004247810.001703540.000424781 6.58573e-0060.000424781
0.02739840.1098780.02739840.0004247810.00170354
0.1098780.4406550.1098780.001703540.000424781
0.02739840.1098780.02739840.0004247816.58573e-0060.0004247810.001703540.000424781 6.58573e-006
高斯模板是中心对称的。
下图是5*5(0.6=σ)的高斯模板卷积计算示意图。
图 2.2二维高斯卷积
a)原图b)0.6
=σ
c)10.0=σd)10.0=σ(边缘处理)
图2.3二维高斯模糊效果图
2.3分离高斯模糊
如图2.3所示，使用二维的高斯模板达到了模糊图像的目的，但是会因模板矩阵的关系而造成边缘图像缺失(2.3b,c)，σ越大，缺失像素越多,丢弃模板会造成黑边(2.3d)。更重要的是当变大时，高斯模板(高斯核)和卷积运算量将大幅度提高。根据高斯函数的可分离性，可对二维高斯模糊函数进行改进。
高斯函数的可分离性是指使用二维矩阵变换得到的效果也可以通过在水平方向进行一维高斯矩阵变换加上竖直方向的一维高斯矩阵变换得到。从计算的角度来看，这是一项有用的特性，因为这样只需要)()(N M m O N M n O ××+××次计算，而二维不可分的矩阵则需要)(N M n m O ×××次计算，其中，m,n 为高斯矩阵的维数，M,N 为二维图像的维数。
另外，两次一维的高斯卷积将消除二维高斯矩阵所产生的边缘。
图2.4
分离高斯卷积
a)原图b) 2.0
=
σ
图2.5分离高斯模糊效果图
附录1是用opencv2.2实现的二维高斯模糊和分离高斯模糊。表2.2为上述两种方法和opencv2.3开源库实现的高斯模糊程序的比较。
表2.2高斯模糊实现结果比较(lena512*512灰度图)
版
本
σms
方法
σ二维高斯模糊分离高斯模糊
Opencv2.2实现的
高斯模糊Debug
1.6390678116
2.69031112516
3.616062154731
16.0
2102035953125Release
1.6
1094702.6
2186303.6
39094016.0653137532
3、尺度空间极值检测
尺度空间使用高斯金字塔表示。Tony Lindeberg 指出尺度规范化的LoG(Laplacion of Gaussian)算子具有真正的尺度不变性，Lowe 使用高斯差分金字塔近似LoG 算子，在尺度空间检测稳定的关键点。
3.1尺度空间理论
尺度空间(scale space)思想最早是由Iijima 于1962年提出的，后经witkin 和Koenderink 等人的推广逐渐得到关注，在计算机视觉领域使用广泛。
尺度空间理论的基本思想是：在图像信息处理模型中引入一个被视为尺度的参数，通过连续变化尺度参数获得多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。
尺度空间方法将传统的单尺度图像信息处理技术纳入尺度不断变化的动态分析框架中，更容易获取图像的本质特征。尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。
尺度空间满足视觉不变性。该不变性的视觉解释如下：当我们用眼睛观察物体时，一方面当物体所处背景的光照条件变化时，视网膜感知图像的亮度水平和对比度是不同的，因此要求尺度空间算子对图像的分析不受图像的灰度水平和对比度变化的影响，即满足灰度不变性和对比度不变性。另一方面，相对于某一固定坐标系，当观察者和物体之间的相对位置变化时，视网膜所感知的图像的位置、大小、角度和形状是不同的，因此要求尺度空间算子对图像的分析和图像的位置、大小、角度以及仿射变换无关，即满足平移不变性、尺度不变性、欧几里德不变性以及仿射不变性。
3.2尺度空间的表示
一个图像的尺度空间),,(σy x L ，定义为一个变化尺度的高斯函数),,(σy x G 与原图像),(y x I 的卷积。
)
,(),,(),,(y x I y x G y x L ?=σσ(3-1)
其中，?表示卷积运算，22222)2/()2/(21
),,(σπσσn y m x e y x G ?+??=(3-2)
与公式(1-2)相同，m ，n 表示高斯模板的维度(由)16()16(+×+σσ确定)。(x,y)代表图像的像素位置。σ是尺度空间因子，值越小表示图像被平滑的越少，相应的尺度也就越小。大尺度对应于图像的概貌特征，小尺度对应于图像的细节特征。
3.3高斯金字塔的构建
尺度空间在实现时使用高斯金字塔表示，高斯金字塔的构建分为两部分：
1.对图像做不同尺度的高斯模糊；
2.对图像做降采样(隔点采样)
。
图3.1高斯金字塔
图像的金字塔模型是指，将原始图像不断降阶采样，得到一系列大小不一的图像，由大到小，从下到上构成的塔状模型。原图像为金子塔的第一层，每次降采样所得到的新图像为金字塔的一层(每层一张图像)，每个金字塔共n 层。金字塔的层数根据图像的原始大小和塔顶图像的大小共同决定，其计算公式如下：
)}),{min(log ,0[,)},{min(log 22N M t t N M n ∈?=(3-3)
其中M ，N 为原图像的大小,t 为塔顶图像的最小维数的对数值。如，对于大小为512*512的图像，金字塔上各层图像的大小如表3.1所示，当塔顶图像为4*4时，n=7，当塔顶图像为2*2时，n=8。
表3.1512*512图像金字塔顶层图像大小与层数的关系图像大小
51221612864168421金字塔层数123456789
为了让尺度体现其连续性，高斯金字塔在简单降采样的基础上加上了高斯滤波。如图3.1所示，将图像金字塔每层的一张图像使用不同参数σ做高斯模糊，使得金字塔的每层含有多张高斯模糊图像，将金字塔每层多张图像合称为一组(Octave)，金字塔每层只有一组图像，组数和金字塔层数相等，使用公式(3-3)计算，每组含有多张(也叫层Interval)图像。另外，降采样时，高斯金字塔上一组图像的初始图像(底层图像)是由前一组图像的倒数第二张图像(或着倒数第三张)隔点采样得到的。
注：由于组内的多张图像按层次叠放，因此组内的多张图像也称做多层，为避免与金字塔层的概念混淆，本文以下内容中，若不特别说明是金字塔层数，层一般指组内各层图像。
3.3高斯差分金字塔
2002年Mikolajczyk 在详细的实验比较中发现尺度归一化的高斯拉普拉斯函数G 22?σ的极大值和极小值同其它的特征提取函数，例如：梯度，Hessian 或Harris 角特征比较，能够产生最稳定的图像特征。
而Lindeberg 早在1994年就发现高斯差分函数（Difference of Gaussian ，简称DOG 算子）与尺度归一化的高斯拉普拉斯函数G 22?σ非常近似。其中),,(σy x D 和G 22?σ的关系可以从如下公式推导得到：
G G 2?=??σσ
利用差分近似代替微分，则有：
σ
σσσσσ??≈??=
?k y x G k y x G G G ),,(),,(2因此有G
k y x G k y x G 22)1(),,(),,(??≈?σσσ其中k-1是个常数，并不影响极值点位置的求取。
图3.2高斯拉普拉斯和高斯差分的比较
如图3.2所示，红色曲线表示的是高斯差分算子，而蓝色曲线表示的是高斯拉普拉斯算子。Lowe 使用更高效的高斯差分算子代替拉普拉斯算子进行极值检测，如下：
)
,,(),,()
,()),,(),,((),,(σσσσσy x L k y x L y x I y x G k y x G y x D ?=??=(3-4)在实际计算时，使用高斯金字塔每组中相邻上下两层图像相减，得到高斯差分图像，如图3.3
所示，进行极值检测。
图3.3高斯差分金字塔的生成
3.4空间极值点检测(关键点的初步探查)
关键点是由DOG 空间的局部极值点组成的，关键点的初步探查是通过同一组内各DoG
相邻两层图像之间比较完成的。为了寻找DoG 函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图3.4所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。
图3.4DOG 空间极值检测
由于要在相邻尺度进行比较，如图3.3右侧每组含4层的高斯差分金子塔，只能在中间两层中进行两个尺度的极值点检测，其它尺度则只能在不同组中进行。为了在每组中检测S 个尺度的极值点，则DOG 金字塔每组需S+2层图像，而DOG 金字塔由高斯金字塔相邻两层相减得到，则高斯金字塔每组需S+3层图像，实际计算时S 在3到5之间。
当然这样产生的极值点并不全都是稳定的特征点，因为某些极值点响应较弱，而且DOG 算子会产生较强的边缘响应。
3.5构建尺度空间需确定的参数
σ—尺度空间坐标
O —组(octave)数
S —组内层数
在上述尺度空间中，σ和o ，s 的关系如下：
]2,...,0[],1,...,0[2),(0+∈?∈=+S s O o s o S s
o σσ(3-5)
其中0σ是基准层尺度，o 为组octave 的索引，s 为组内层的索引。关键点的尺度坐标σ就是按关键点所在的组和组内的层，利用公式(3-5)计算而来。
在最开始建立高斯金字塔时，要预先模糊输入图像来作为第0个组的第0层的图像，这
时相当于丢弃了最高的空域的采样率。因此通常的做法是先将图像的尺度扩大一倍来生成第-1组。我们假定初始的输入图像为了抗击混淆现象，已经对其进行5.01=?σ的高斯模糊，如果输入图像的尺寸用双线性插值扩大一倍，那么相当于0.11=?σ。
取式(3-4)中的k 为组内总层数的倒数，即
S k 1
2=(3-6)在构建高斯金字塔时，组内每层的尺度坐标按如下公式计算：
2
0120)()()(σσσ??=s s k k s (3-7)
其中0σ初始尺度，lowe 取6.10=σ，3=S ，s 为组内的层索引，不同组相同层的组内尺度坐标)(s σ相同。组内下一层图像是由前一层图像按)(s σ进行高斯模糊所得。式(3-7)用于一次生成组内不同尺度的高斯图像，而在计算组内某一层图像的尺度时，直接使用如下公式进行计算：
]2,...,0[2)(_0+∈=S s s oct S
s σσ(3-8)
该组内尺度在方向分配和特征描述时确定采样窗口的大小。
由上，式(3-4)可记为))
(,,())1(,,()
,()))(,,())1(,,((),,(s y x L s y x L y x I s y x G s y x G y x D σσσσσ?+=??+=(3-9)图3.5为构建DOG 金字塔的示意图，原图采用128*128的jobs 图像，扩大一倍后构建金字塔。
图3.5DOG金字塔的构建示意图
4、关键点定位
以上方法检测到的极值点是离散空间的极值点，以下通过拟合三维二次函数来精确确定关键点的位置和尺度，同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。
4.1关键点的精确定位
离散空间的极值点并不是真正的极值点，图4.1显示了二维函数离散空间得到的极值点与连续空间极值点的差别。利用已知的离散空间点插值得到的连续空间极值点的方法叫做子
像素插值（Sub-pixel Interpolation）。
图4.1离散空间与连续空间极值点的差别
为了提高关键点的稳定性，需要对尺度空间DoG 函数进行曲线拟合。利用DoG 函数在尺度空间的Taylor 展开式(拟合函数)为：
X X D X X X D D X D T T 2
221)(??+??+=(4-1)其中，T
y x X ),,(σ=。求导并让方程等于零，可以得到极值点的偏移量为：
X D X D X ?????=?212?(4-2)对应极值点，方程的值为：
X X
D D X D T ?21)?(??+=(4-3)其中,T
y x X ),,(?σ=代表相对插值中心的偏移量，当它在任一维度上的偏移量大于0.5时（即x 或y 或σ），意味着插值中心已经偏移到它的邻近点上，所以必须改变当前关键点的位置。同时在新的位置上反复插值直到收敛；也有可能超出所设定的迭代次数或者超出图像边界的范围，此时这样的点应该删除，在Lowe 中进行了5次迭代。另外，()x D 过小的点易受噪声的干扰而变得不稳定，所以将()x D 小于某个经验值(Lowe 论文中使用0.03，Rob Hess 等人实现时使用0.04/S)的极值点删除。同时，在此过程中获取特征点的精确位置(原位置加上拟合的偏移量)以及尺度(),(s o σ和)(_s oct σ)。
4.2消除边缘响应
一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。
DOG 算子会产生较强的边缘响应，需要剔除不稳定的边缘响应点。获取特征点处的Hessian 矩阵，主曲率通过一个2x2的Hessian 矩阵H 求出：
??????=yy xy xy xx D D D D H (4-4)
H 的特征值α和β代表x 和y 方向的梯度，
αβ
βα=?=+=+=2)()(,
)(xy yy xx yy xx D D D H Det D D H Tr (4-5))(H Tr 表示矩阵H 对角线元素之和，)(H Det 表示矩阵H 的行列式。假设α是较大的
特征值，而β是较小的特征值，令βαr =，则r r r r H Det H Tr 2
2222)1()()()()(+=+=+=β
ββαββα(4-6)
导数由采样点相邻差估计得到,在下一节中说明。D 的主曲率和H 的特征值成正比，令α为最大特征值，β为最小的特征值，则公式r r /)1(2+的值在两个特征值相等时最小，随着r 的增大而增大。值越大，说明两个特征值的比值越大，即在某一个方向的梯度值越大，而在另一个方向的梯度值越小，而边缘恰恰就是这种情况。所以为了剔除边缘响应点，需要让该比值小于一定的阈值，因此，为了检测主曲率是否在某域值r 下，只需检测
r
r H Det H Tr 2
2)1()()(+<(4-7)
式(4-7)成立时将关键点保留，反之剔除。在Lowe 的文章中，取r ＝10。图4.2右侧为消除边缘响应后的关键点分布图。
图4.2边缘消除响应前后的关键点
4.3有限差分法求导
有限差分法以变量离散取值后对应的函数值来近似微分方程中独立变量的连续取值。在有限差分方法中，我们放弃了微分方程中独立变量可以取连续值的特征，而关注独立变量离散取值后对应的函数值。但是从原则上说，这种方法仍然可以达到任意满意的计算精度。因为方程的连续数值解可以通过减小独立变量离散取值的间格，或者通过离散点上的函数值插值计算来近似得到。这种方法是随着计算机的诞生和应用而发展起来的。其计算格式和程序的设计都比较直观和简单，因而，它在计算数学中使用广泛。
有限差分法的具体操作分为两个部分：
1.用差分代替微分方程中的微分，将连续变化的变量离散化，从而得到差分方程组的数学形式；
2.求解差分方程组。
一个函数在x 点上的一阶和二阶微商，可以近似地用它所临近的两点上的函数值的差分来表示。如对一个单变量函数()x f ，x 为定义在区间],[b a 上的连续变量，以步长x h ?=将
],[b a 区间离散化，我们会得到一系列节点，
b
x x h a h x x a x n n =+=+=+==+1,...,,1121然后求出()x f 在这些点上的近似值。显然步长h 越小，近似解的精度就越好。与节点i x 相邻的节点有h x i ?和h x i +，所以在节点i x 处可构造如下形式的差值：
)()(i i x f h x f ?+节点i x 的一阶向前差分
)()(h x f x f i i ??节点i x 的一阶向后差分
)()(h x f h x f i i ??+节点i x 的一阶中心差分
本文使用中心差分法利用泰勒展开式求解第四节所使用的导数，现做如下推导。函数()x f 在i x 处的泰勒展开式为：
n i i n i i i i i x x n x f x x x f x x x f x f x f )(!
)(...)(!2)())(()()()(2?++?′′+?′+=(4-8)则，
...))((!2)()))((()()(2+??′′+
??′+=?i i i i i i i i x h x x f x h x x f x f h x f (4-9)...))((!
2)()))((()()(2+?+′′+?+′+=+i i i i i i i i x h x x f x h x x f x f h x f (4-10)忽略h 平方之后的项，联立式(4-9)，(4-10)解方程组得：
h h x f h x f x f x f i i x i i
2)()()(??+≈????????=′(4-11)222)(2)()()(h x f h x f h x f x f x f i i i x i i ??++≈??????????=′′(4-12)
二元函数的泰勒展开式如下：
()...),()(),()(3),()(3),()(!31),()(),(2),()(!21),(),(),(,3332322323332222222+????????+?????+?????+???+??
???????+?????+???+???+???+=?+?+y y x f y y x y x f y x y x y x f y x x y x f x y y x f y y x y x f y x x y x f x y
y x f y x y x f x y x f y y x x f 将),(h y h x f i i ++、),(h y h x f i i ++、),(h y h x f i i ++和),(h y h x f i i ++展开后忽略次要项联立解方程得二维混合偏导如下：
)]
,(),(),(),([41),(22h y h x f h y h x f h y h x f h y h x f h y x y x f i i i i i i i i i i +???+???+++≈???(4-13)
综上，推导了4.1,4.2遇到的所有导数计算。同理，利用多元泰勒展开式，可得任意偏导的近似差分表示。12
8
45113
019
72
610图4.2图像中像素0与其领域在图像处理中，取h=1，在图4.2所示的图像中，将像素0的基本中点导数公式整理如下：
h f f x f 2310
?=????????h f f y f 2420
?=??????????20310222h f f f x f ?+=???????
???20420
222h f f f y f ?+=??????????27568024)()(h f f f f y x f +?+=???????????)]()(46[11193104044f f f f f h x f +++?=???????
???)]()(46[1121042040
44f f f f f h y f +++?=??????????
)]()(24[187654321040224f f f f f f f f f h
y x f +++++++?=???????????4.4三阶矩阵求逆公式
高阶矩阵的求逆算法主要有归一法和消元法两种，现将三阶矩阵求逆公式总结如下：若矩阵
????
??????=222120121110020100a a a a a a a a a A 可逆，即0
20110222100121120021
1002201201221100≠???++=a a a a a a a a a a a a a a a a a a A 时，
??????????????????????=?100111000120210011
2021101200100200222002102220121102120102212201122122111)()()
(1a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a A A (4-14)5、关键点方向分配为了使描述符具有旋转不变性，需要利用图像的局部特征为给每一个关键点分配一个基准方向。使用图像梯度的方法求取局部结构的稳定方向。对于在DOG 金字塔中检测出的关键点点，采集其所在高斯金字塔图像σ3领域窗口内像素的梯度和方向分布特征。梯度的模值和方向如下：
))),1(),1())1,()1,(((tan ),())1,()1,(()),1(),1((),(12
2y x L y x L y x L y x L y x y x L y x L y x L y x L y x m ??+??+=??++??+=?θ(5-1)
L 为关键点所在的尺度空间值，按Lowe 的建议，梯度的模值),(y x m 按oct _5.1σσ=的高斯分布加成，按尺度采样的σ3原则，领域窗口半径为oct _5.13σ×。
在完成关键点的梯度计算后，使用直方图统计领域内像素的梯度和方向。梯度直方图将0~360度的方向范围分为36个柱(bins)，其中每柱10度。如图5.1所示，直方图的峰值方向代表了关键点的主方向，(为简化，图中只画了八个方向的直方图)。
图5.1关键点方向直方图
方向直方图的峰值则代表了该特征点处邻域梯度的方向，以直方图中最大值作为该关键点的主方向。为了增强匹配的鲁棒性，只保留峰值大于主方向峰值80％的方向作为该关键点的辅方向。因此，对于同一梯度值的多个峰值的关键点位置，在相同位置和尺度将会有多个关键点被创建但方向不同。仅有15％的关键点被赋予多个方向，但可以明显的提高关键点匹配的稳定性。实际编程实现中，就是把该关键点复制成多份关键点，并将方向值分别赋给这些复制后的关键点，并且，离散的梯度方向直方图要进行插值拟合处理，来求得更精确的方向角度值，检测结果如图5.2所示。
图5.2sift特征
至此，将检测出的含有位置、尺度和方向的关键点即是该图像的SIFT特征点。
6、关键点特征描述
通过以上步骤，对于每一个关键点，拥有三个信息：位置、尺度以及方向。接下来就是为每个关键点建立一个描述符，用一组向量将这个关键点描述出来，使其不随各种变化而改变，比如光照变化、视角变化等等。这个描述子不但包括关键点，也包含关键点周围对其有
3.1.1尺度空间极值检测 尺度空间理论最早出现于计算机视觉领域，当时其目的是模拟图像数据的多尺度特征。随后Koendetink 利用扩散方程来描述尺度空间滤波过程，并由此证明高斯核是实现尺度变换的唯一变换核。Lindeberg ，Babaud 等人通过不同的推导进一步证明高斯核是唯一的线性核。因此，尺度空间理论的主要思想是利用高斯核对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间特征提取。二维高斯函数定义如下： 222()/221 (,,)2x y G x y e σσπσ-+= （5） 一幅二维图像，在不同尺度下的尺度空间表示可由图像与高斯核卷积得到： (,,(,,)*(,)L x y G x y I x y σσ)= （6） 其中(x,y )为图像点的像素坐标，I(x,y )为图像数据, L 代表了图像的尺度空间。σ称为尺度空间因子，它也是高斯正态分布的方差，其反映了图像被平滑的程度，其值越小表征图像被平滑程度越小，相应尺度越小。大尺度对应于图像的概貌特征，小尺度对应于图像的细节特征。因此，选择合适的尺度因子平滑是建立尺度空间的关键。 在这一步里面，主要是建立高斯金字塔和DOG(Difference of Gaussian)金字塔，然后在DOG 金字塔里面进行极值检测，以初步确定特征点的位置和所在尺度。 (1)建立高斯金字塔 为了得到在不同尺度空间下的稳定特征点，将图像(,)I x y 与不同尺度因子下的高斯核(,,)G x y σ进行卷积操作，构成高斯金字塔。 高斯金字塔有o 阶，一般选择4阶，每一阶有s 层尺度图像，s 一般选择5层。在高斯金字塔的构成中要注意，第1阶的第l 层是放大2倍的原始图像，其目的是为了得到更多的特征点；在同一阶中相邻两层的尺度因子比例系数是k ，则第1阶第2层的尺度因子是k σ，然后其它层以此类推则可；第2阶的第l 层由第一阶的中间层尺度图像进行子抽样获得，其尺度因子是2k σ，然后第2阶的第2层的尺度因子是第1层的k 倍即3 k σ。第3阶的第1层由第2阶的中间层尺度图像进行子抽样获得。其它阶的构成以此类推。 (2)建立DOG 金字塔 DOG 即相邻两尺度空间函数之差，用(,,)D x y σ来表示，如公式(3)所示： (,,)((,,)(,,))*(,)(,,)(,,)D x y G x y k G x y I x y L x y k L x y σσσσσ=-=- (7) DOG 金字塔通过高斯金字塔中相邻尺度空间函数相减即可，如图1所示。在图中，DOG 金字塔的第l 层的尺度因子与高斯金字塔的第l 层是一致的，其它阶也一样。
经典算法SIFT实现即代码解释： 以下便是sift源码库编译后的效果图：
为了给有兴趣实现sift算法的朋友提供个参考，特整理此文如下。要了解什么是sift算法，请参考：九、图像特征提取与匹配之SIFT算法。ok，咱们下面，就来利用Rob Hess维护的sift 库来实现sift算法： 首先，请下载Rob Hess维护的sift 库： https://www.doczj.com/doc/5a3975682.html,/hess/code/sift/ 下载Rob Hess的这个压缩包后，如果直接解压缩，直接编译，那么会出现下面的错误提示： 编译提示:error C1083: Cannot open include file: 'cxcore.h': No such file or directory，找不到这个头文件。 这个错误，是因为你还没有安装opencv，因为：cxcore.h和cv.h是开源的OPEN CV头文件,不是VC++的默认安装文件,所以你还得下载OpenCV并进行安装。然后，可以在OpenCV文件夹下找到你所需要的头文件了。 据网友称，截止2010年4月4日，还没有在VC6.0下成功使用opencv2.0的案例。所以，如果你是VC6.0的用户请下载opencv1.0版本。vs的话，opencv2.0,1.0任意下载。 以下，咱们就以vc6.0为平台举例，下载并安装opencv1.0版本、gsl等。当然，你也可以用vs编译，同样下载opencv（具体版本不受限制）、gsl等。 请按以下步骤操作： 一、下载opencv1.0 https://www.doczj.com/doc/5a3975682.html,/projects/opencvlibrary/files/opencv-win/1.0/OpenCV_1.0.exe
SIFT: Scale Invariant Feature Transform The algorithm SIFT is quite an involved algorithm. It has a lot going on and can be come confusing, So I’ve split up the entire algorithm into multiple parts. Here’s an outline of what happens in SIFT. Constructing a scale space This is the initial preparation. You create internal representations of the original image to ensure scale invariance. This is done by generating a “scale space”. LoG Approximation The Laplacian of Gaussian is great for finding interesting points (or key points) in an image. But it’s computationally expensive. So we cheat and approximate it using the representation created earlier. Finding keypoints With the super fast approximation, we now try to find key points. These are maxima and minima in the Difference of Gaussian image we calculate in step 2 Get rid of bad key points Edges and low contrast regions are bad keypoints. Eliminating these makes the algorithm efficient and robust. A technique similar to the Harris Corner Detector is used here. Assigning an orientation to the keypoints An orientation is calculated for each key point. Any further calculations are done relative to this orientation. This effectively cancels out the effect of orientation, making it rotation invariant. Generate SIFT features Finally, with scale and rotation invariance in place, one more representation is generated. This helps uniquely identify features. Lets say you have 50,000 features. With this representation, you can easily identify the feature you’re looking for (sa y, a particular eye, or a sign board). That was an overview of the entire algorithm. Over the next few days, I’ll go through each step in detail. Finally, I’ll show you how to implement SIFT in OpenCV! What do I do with SIFT features? After you run through the algorithm, you’ll have SIFT features for your image. Once you have these, you can do whatever you want. Track images, detect and identify objects (which can be partly hidden as well), or whatever you can think of. We’ll get into this later as well. But the catch is, this algorithm is patented. >.< So, it’s good enough for academic purposes. But if you’re looking to make something commercial, look for something else! [Thanks to aLu for pointing out SURF is patented too] 1. Constructing a scale space Real world objects are meaningful only at a certain scale. You might see a sugar cube perfectly on a table. But if looking at the entire milky way, then it simply does not exist. This multi-scale nature of objects is quite common in nature. And a scale space attempts to replicate this concept
SIFT 特征提取算法总结 主要步骤 1)、尺度空间的生成； 2)、检测尺度空间极值点； 3)、精确定位极值点； 4)、为每个关键点指定方向参数； 5)、关键点描述子的生成。 L(x,y,σ), σ= 1.6 a good tradeoff
D(x,y,σ), σ= 1.6 a good tradeoff
关于尺度空间的理解说明：图中的2是必须的，尺度空间是连续的。在 Lowe 的论文中， 将第0层的初始尺度定为1.6，图片的初始尺度定为0.5. 在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以Lowe 建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。尺度越大图像越模糊。 next octave 是由first octave 降采样得到（如2） ， 尺度空间的所有取值，s为每组层数，一般为3~5 在DOG尺度空间下的极值点 同一组中的相邻尺度（由于k的取值关系，肯定是上下层）之间进行寻找
在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度 变化的连续性，我们在每一组图像的顶层继续用高斯模糊生成了 3 幅图像， 高斯金字塔有每组S+3层图像。DOG金字塔每组有S+2层图像.
If ratio > (r+1)2/(r), throw it out (SIFT uses r=10) 表示DOG金字塔中某一尺度的图像x方向求导两次 通过拟和三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度）？
直方图中的峰值就是主方向，其他的达到最大值80%的方向可作为辅助方向 Identify peak and assign orientation and sum of magnitude to key point The user may choose a threshold to exclude key points based on their assigned sum of magnitudes. 利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备 旋转不变性。以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度 方向。梯度直方图的范围是0～360度，其中每10度一个柱，总共36个柱。随着距中心点越远的领域其对直方图的贡献也响应减小.Lowe论文中还提到要使用高斯函 数对直方图进行平滑，减少突变的影响。
SIFT算法C语言逐步实现详解（上） 引言： 在我写的关于sift算法的前倆篇文章里头，已经对sift算法有了初步的介绍：九、图像特征提取与匹配之SIFT算法，而后在：九（续）、sift算法的编译与实现里，我也简单记录下了如何利用opencv，gsl等库编译运行sift程序。 但据一朋友表示，是否能用c语言实现sift算法，同时，尽量不用到opencv，gsl等第三方库之类的东西。而且，Rob Hess维护的sift 库，也不好懂，有的人根本搞不懂是怎么一回事。 那么本文，就教你如何利用c语言一步一步实现sift算法，同时，你也就能真正明白sift算法到底是怎么一回事了。 ok，先看一下，本程序最终运行的效果图，sift 算法分为五个步骤（下文详述），对应以下第二--第六幅图：
sift算法的步骤 要实现一个算法，首先要完全理解这个算法的原理或思想。咱们先来简单了解下，什么叫sift算法： sift，尺度不变特征转换，是一种电脑视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由David Lowe 在1999年所发表，2004年完善总结。 所谓，Sift算法就是用不同尺度（标准差）的高斯函数对图像进行平滑，然后比较平滑后图像的差别， 差别大的像素就是特征明显的点。 以下是sift算法的五个步骤： 一、建立图像尺度空间(或高斯金字塔)，并检测极值点 首先建立尺度空间，要使得图像具有尺度空间不变形，就要建立尺度空间，sift算法采用了高斯函数来建立尺度空间，高斯函数公式为：
上述公式G(x,y,e)，即为尺度可变高斯函数。 而，一个图像的尺度空间L（x,y,e) ,定义为原始图像I(x,y)与上述的一个可变尺度的2维高斯函数G(x,y,e) 卷积运算。 即，原始影像I(x，y)在不同的尺度e下，与高斯函数G(x,y,e)进行卷积，得到L(x,y,e)，如下： 以上的（x，y）是空间坐标，e，是尺度坐标，或尺度空间因子，e的大小决定平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的e值对应粗糙尺度(低分辨率)，反之，对应精细尺度(高分辨率)。 尺度，受e这个参数控制的表示。而不同的L（x,y,e）就构成了尺度空间，具体计算的时候，即使连续的高斯函数，都被离散为（一般为奇数大小）(2*k+1) *(2*k+1)矩阵，来和数字图像进行卷积运算。 随着e的变化，建立起不同的尺度空间，或称之为建立起图像的高斯金字塔。 但，像上述L(x,y,e) = G(x,y,e)*I(x,y)的操作，在进行高斯卷积时，整个图像就要遍历所有的像素进行卷积(边界点除外)，于此，就造成了时间和空间上的很大浪费。 为了更有效的在尺度空间检测到稳定的关键点，也为了缩小时间和空间复杂度，对上述的操作作了一个改建：即，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分与原始图像I(x,y)相乘，卷积生成。 DOG算子计算简单，是尺度归一化的LOG算子的近似。 ok，耐心点，咱们再来总结一下上述内容： 1、高斯卷积 在组建一组尺度空间后，再组建下一组尺度空间，对上一组尺度空间的最后一幅图像进行二分之一采样，得到下一组尺度空间的第一幅图像，然后进行像建立第一组尺度空间那样的操作，得到第二组尺度空间，公式定义为 L(x,y,e) = G(x,y,e)*I(x,y)
SIFT算法分析 1 SIFT 主要思想 SIFT算法是一种提取局部特征的算法，在尺度空间寻找极值点，提取位置，尺度，旋转不变量。 2 SIFT 算法的主要特点： a)SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。 b)独特性(Distinctiveness)好，信息量丰富，适用于在海量特征数据库中进 行快速、准确的匹配。 c)多量性，即使少数的几个物体也可以产生大量SIFT特征向量。 d)高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。 e)可扩展性，可以很方便的与其他形式的特征向量进行联合。 3 SIFT 算法流程图：
4 SIFT 算法详细 1）尺度空间的生成 尺度空间理论目的是模拟图像数据的多尺度特征。 高斯卷积核是实现尺度变换的唯一线性核，于是一副二维图像的尺度空间定义为： L( x, y, ) G( x, y, ) I (x, y) 其中G(x, y, ) 是尺度可变高斯函数，G( x, y, ) 2 1 2 y2 (x ) 2 e / 2 2 （x，y）是空间坐标，是尺度坐标。大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的值对应粗糙尺度(低分辨率)，反之，对应精细尺度(高分辨率)。 为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成。 D( x, y, ) (G( x, y,k ) G( x, y, )) I ( x, y) L( x, y,k ) L( x, y, ) DOG算子计算简单，是尺度归一化的LoG算子的近似。图像金字塔的构建：图像金字塔共O组，每组有S层，下一组的图像由上一 组图像降采样得到。 图1由两组高斯尺度空间图像示例金字塔的构建，第二组的第一副图像由第一组的第一副到最后一副图像由一个因子2降采样得到。图2 DoG算子的构建： 图1 Two octaves of a Gaussian scale-space image pyramid with s =2 intervals. The first image in the second octave is created by down sampling to last image in the previous
尺度不变特征变换匹配算法详解 Scale Invariant Feature Transform(SIFT) Just For Fun 张东东zddmail@https://www.doczj.com/doc/5a3975682.html, 对于初学者，从David G.Lowe的论文到实现，有许多鸿沟，本文帮你跨越。 1、SIFT综述 尺度不变特征转换(Scale-invariant feature transform或SIFT)是一种电脑视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由David Lowe在1999年所发表，2004年完善总结。 其应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对。 此算法有其专利，专利拥有者为英属哥伦比亚大学。 局部影像特征的描述与侦测可以帮助辨识物体，SIFT特征是基于物体上的一些局部外观的兴趣点而与影像的大小和旋转无关。对于光线、噪声、些微视角改变的容忍度也相当高。基于这些特性，它们是高度显著而且相对容易撷取，在母数庞大的特征数据库中，很容易辨识物体而且鲜有误认。使用SIFT特征描述对于部分物体遮蔽的侦测率也相当高，甚至只需要3个以上的SIFT物体特征就足以计算出位置与方位。在现今的电脑硬件速度下和小型的特征数据库条件下，辨识速度可接近即时运算。SIFT特征的信息量大，适合在海量数据库中快速准确匹配。 SIFT算法的特点有： 1.SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性； 2.独特性（Distinctiveness）好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配； 3.多量性，即使少数的几个物体也可以产生大量的SIFT特征向量； 4.高速性，经优化的SIFT匹配算法甚至可以达到实时的要求；
概率论问题征解报告： （算法分析类） SIFT算法与RANSAC算法分析 班级：自23 姓名：黄青虬 学号：2012011438 作业号：146
SIFT 算法是用于图像匹配的一个经典算法，RANSAC 算法是用于消除噪声的算法，这两者经常被放在一起使用，从而达到较好的图像匹配效果。 以下对这两个算法进行分析，由于sift 算法较为复杂，只重点介绍其中用到的概率统计概念与方法——高斯卷积及梯度直方图，其余部分只做简单介绍。 一． SIFT 1. 出处：David G. Lowe, The Proceedings of the Seventh IEEE International Conference on (Volume:2, Pages 1150 – 1157), 1999 2. 算法目的：提出图像特征，并且能够保持旋转、缩放、亮度变化保持不变性，从而 实现图像的匹配 3. 算法流程图： 原图像 4. 算法思想简介： （1） 特征点检测相关概念： ◆ 特征点：Sift 中的特征点指十分突出、不会因亮度而改变的点，比如角点、边 缘点、亮区域中的暗点等。特征点有三个特征：尺度、空间和大小 ◆ 尺度空间：我们要精确表示的物体都是通过一定的尺度来反映的。现实世界的 物体也总是通过不同尺度的观察而得到不同的变化。尺度空间理论最早在1962年提出，其主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。尺度越大图像越模糊。 ◆ 高斯模糊：高斯核是唯一可以产生多尺度空间的核，一个图像的尺度空间，L （x,y,σ) ,定义为原始图像I(x,y)与一个可变尺度的2维高斯函数G(x,y,σ) 卷积运算 高斯函数： 高斯卷积的尺度空间： 不难看到，高斯函数与正态分布函数有点类似，所以在计算时，我们也是 ()()() ,,,,*,L x y G x y I x y σσ=()22221 ()(),,exp 22i i i i x x y y G x y σπσσ??-+-=- ? ??
SIFT算法和卷积神经网络算法在图像检索领域的应用分析 1、引言 基于内容的图像检索是由于图像信息的飞速膨胀而得到关注并被提出来的。如何快速准确地提取图像信息内容是图像信息检索中最为关键的一步。传统图像信息检索系统多利用图像的底层特征，如颜色、纹理、形状以及空间关系等。这些特征对于图像检索有着不同的结果，但是同时也存在着不足，例如：颜色特征是一种全局的特征，它对图像或图像区域的方向、大小等变化不敏感，所以颜色特征不能很好的捕捉图像中对象的局部特征，也不能表达颜色空间分布的信息。纹理特征也是一种全局特征，它只是物体表面的一种特性，并不能完全反映物体的本质属性。基于形状的特征常常可以利用图像中感兴趣的目标进行检索，但是形状特征的提取，常常受到图像分割效果的影响。空间关系特征可以加强对图像内容的描述和区分能力，但空间关系特征对图像或者，目标的旋转、平移、尺度变换等比较敏感，并且不能准确地表达场景的信息。图像检索领域急需一种能够对目标进行特征提取，并且对图像目标亮度、旋转、平移、尺度甚至仿射不变的特征提取算法。 2、SIFT特征 SIFT（Scale-Invariant Feature Transform，尺度不变特征转换）是一种电脑视觉的算法，用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由David Lowe在1999年所发表，2004年完善总结。 局部特征的描述与侦测可以帮助辨识物体，SIFT特征是基于物体上的一些局部外观的兴趣点，与目标的大小和旋转无关，对于光线、噪声、些微视角改变的容忍度也相当高。使用SIFT特征描述对于部分物体遮蔽的侦测成功率也相当高，甚至只需要3个以上的SIFT 物体特征就足以计算出位置与方位。在现今的电脑硬件速度和小型的特征数据库条件下，辨识速度可接近即时运算。SIFT特征的信息量大，也适合在海量数据库中快速准确匹配。 SIFT算法的特点有： （1）SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变形，是非常稳定的局部特征，现在应用非常广泛。（仿射变换，又称仿射映射，是指在几何中，一个向量空间进行一次线性变换并加上一个平移，变换为另一个向量空间。） （2）独特性（Distinctiveness）好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配； （3）多量性，即使少数的几个物体也可以产生大量的SIFT特征向量； （4）高速性，经优化的SIFT匹配算法甚至可以达到实时的要求； （5）可扩展性，可以很方便的与其他形式的特征向量进行联合。 SIFT算法可以解决的问题：目标的自身状态、场景所处的环境和成像器材的成像特性等因素影响图像配准/目标识别跟踪的性能。 而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,σ) 卷积运算。 高斯函数 高斯金字塔 高斯金子塔的构建过程可分为两步： （1）对图像做高斯平滑； （2）对图像做降采样。 为了让尺度体现其连续性，在简单 下采样的基础上加上了高斯滤波。 一幅图像可以产生几组（octave ） 图像，一组图像包括几层 （interval ）图像。 高斯图像金字塔共o 组、s 层， 则有： σ——尺度空间坐标；s ——sub-level 层坐标；σ0——初始尺度；S ——每组层数（一般为3~5）。 当图像通过相机拍摄时，相机的镜头已经对图像进行了一次初始的模糊，所以根据高斯模糊的性质： -第0层尺度 --被相机镜头模糊后的尺度 高斯金字塔的组数: M 、N 分别为图像的行数和列数 高斯金字塔的组内尺度与组间尺度: 组内尺度是指同一组（octave ）内的尺度关系，组内相邻层尺度化简为： 组间尺度是指不同组直接的尺度关系，相邻组的尺度可化为： 最后可将组内和组间尺度归为： ()22221 ()(),,exp 22i i i i x x y y G x y σπσσ??-+-=- ? ??()()(),,,,*,L x y G x y I x y σσ=Octave 1 Octave 2 Octave 3 Octave 4 Octave 5σ2σ 4σ8 σ 0()2s S s σσ= g 0σ=init σpre σ()() 2log min ,3O M N ??=-?? 1 12S s s σσ+=g 1()2s S S o o s σσ++=g 222s S s S S o o σσ+=g g 121 2(,,,) i n k k k σσσσ--L 1 2 S k =
遥感图像处理在汶川地震中的应用分析 摘要 随着卫星技术的快速发展，遥感技术被越来越广泛的应用于国民经济的各个方面。本文结合汶川地震中遥感技术的应用实例，系统阐述了遥感应用于应急系统中需要解决的一系列关键技术问题。并就数据获取、薄云去除、图像镶嵌、图像解译，以及灾后重建中的若干关键技术问题展开了分析。关键词：遥感；地震；应用；关键技术 1 引言 长期以来，人们不断遭受到各种自然灾害的侵害，如地震、火山、洪水等，同时，由人为因素导致的灾难也不断发生，如火灾、恐怖袭击等。这些灾害具备破坏性、突发性、连锁性、难预报性等特点，往往容易造成重大的人员伤亡和巨大的财产损失。为了有效的应对突发事件，产生了各类应急系统。 灾区数据的实时获取足所有应急系统的基础。对于区域性的灾害，传统的地面调查方式，由于速度慢、面积小、需要人员现场勘查等无法避免的特点，很难满足应急系统的需要。相对而言，遥感技术有其得天独厚的优势：遥感传感器能实时的、大面积的、无接触的获取灾区数据，因此成为绝大多数应急系统中数据获取的主要手段。为了使遥感数据能满足应急系统中基础数据的要求，需要经过数据获取、数据预处理、图像解译等阶段的处理，最终提取出准确的遥感信息。下面将根据这三个阶段的处理技术展开阐述与分析，并以汶川地震为例，介绍遥感技术在应急救灾及灾后重建中的应用。 2 数据获取 灾害发生后，由于地形、气象等客观因素的影响，通过单一的遥感传感器往往很难获得灾区所有数据，需要充分发挥多种传感器的优势，获取灾区的各种类型数据，主要包括光学与SAR卫星遥感影像、光学与SAR航空遥感影像两大类。 2.1 光学与SAR卫星遥感影像的获取 此类数据包括国内外的众多高分辨率光学与SAR卫星遥感影像。从时间上说，重点是灾害发生前后数据的获取，以快速确定灾区的位置和前后的变化。 2.2 光学与SAR航空遥感影像的获取 此类数据是利用高空遥感琶机、无人机和卣升机等高、低空遥感平台，搭载遥感传感器，快速
SIFT（Scale-invariant feature transform）是一种检测局部特征的算法，该算法通过求一幅图中的特征点（interest points, or corner points）及其有关scale 和orientation 的描述子得到特征并进行图像特征点匹配，获得了良好效果，详细解析如下： 算法描述 SIFT特征不只具有尺度不变性，即使改变旋转角度，图像亮度或拍摄视角，仍然能够得到好的检测效果。整个算法分为以下几个部分： 1. 构建尺度空间 这是一个初始化操作，尺度空间理论目的是模拟图像数据的多尺度特征。 高斯卷积核是实现尺度变换的唯一线性核，于是一副二维图像的尺度空间定义为： 其中G(x,y,σ) 是尺度可变高斯函数 （x，y）是空间坐标，是尺度坐标。σ大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的σ值对应粗糙尺度(低分辨率)，反之，对应精细尺度(高分辨率)。为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成。 下图所示不同σ下图像尺度空间：
关于尺度空间的理解说明：2kσ中的2是必须的，尺度空间是连续的。在 Lowe的论文中，将第0层的初始尺度定为1.6（最模糊），图片的初始尺度定为0.5（最清晰）. 在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以Lowe 建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。尺度越大图像越模糊。 图像金字塔的建立：对于一幅图像I,建立其在不同尺度(scale)的图像，也成为子八度（octave），这是为了scale-invariant，也就是在任何尺度都能够有对应的特征点，第一个子八度的scale为原图大小，后面每个octave为上一个octave降采样的结果，即原图的1/4（长宽分别减半），构成下一个子八度（高一层金字塔）。
% [image, descriptors, locs] = sift(imageFile) % % This function reads an image and returns its SIFT keypoints. % Input parameters: % imageFile: the file name for the image. % % Returned: % image: the image array in double format % descriptors: a K-by-128 matrix, where each row gives an invariant % descriptor for one of the K keypoints. The descriptor is a vector % of 128 values normalized to unit length. % locs: K-by-4 matrix, in which each row has the 4 values for a % keypoint location (row, column, scale, orientation). The % orientation is in the range [-PI, PI] radians. % % Credits: Thanks for initial version of this program to D. Alvaro and % J.J. Guerrero, Universidad de Zaragoza (modified by D. Lowe) function [image, descriptors, locs] = sift(imageFile) % Load image image = imread(imageFile); % If you have the Image Processing Toolbox, you can uncomment the following % lines to allow input of color images, which will be converted to grayscale. % if isrgb(image) % image = rgb2gray(image); % end [rows, cols] = size(image); % Convert into PGM imagefile, readable by "keypoints" executable f = fopen('tmp.pgm', 'w'); if f == -1 error('Could not create file tmp.pgm.'); end fprintf(f, 'P5\n%d\n%d\n255\n', cols, rows); fwrite(f, image', 'uint8'); fclose(f); % Call keypoints executable if isunix command = '!./sift '; else command = '!siftWin32 '; end command = [command '
SIFT算法分析 1 SI F T主要思想 S IF T算法就是一种提取局部特征得算法，在尺度空间寻找极值点，提取位置，尺度，旋转不变量。 2 SI FT算法得主要特点 a)SIFT特征就是图像得局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度得稳定性。 b )独特性(Dis t in c t iv e n es s)好，信息量丰富，适用于在海量特征数据库中进行快速、准确得匹配? c) 多量性,即使少数得几个物体也可以产生大量S IFT特征向量。 d) 高速性，经优化得SIF T匹配算法甚至可以达到实时得要求。 e) 可扩展性，可以很方便得与其她形式得特征向量进行联合。 3 SI F T算法流程图: 爹尺度空间扱值点检测 特征点的精确定位 I*
特征点的主方向计算 描述子的构造 特征向童I*
4 SIFT 算法详细 1)尺度空间得生成 尺度空间理论目得就是模拟图像数据得多尺度特征 . 高斯卷积核就是实现尺度变换得唯一线性核，于就是一副二维图像得尺度 空间定义为： 其中就是尺度可变高斯函数， (x ，y )就是空间坐标，就是尺度坐标.大小决定图像得平滑程度，大尺度对 应图像得概貌特征，小尺度对应图像得细节特征。大得值对应粗糙尺度 (低分辨 率)，反之，对应精细尺度(高分辨率)。 为了有效得在尺度空间检测到稳定得关键点，提出了高斯差分尺度空间 (D O G seal e — s p ace ).利用不同尺度得高斯差分核与图像卷积生成。 D(x,y, ) (G(x, y,k ) G(x, y, )) I(x,y) L(x, y,k ) L(x, y,) D OG 算子计算简单，就是尺度归一化得L o G 算子得近似。 图像金字塔得构建：图像金字塔共O 组，每组有S 层，下一组得图像由上一组图 像降采样得到。 图1由两组高斯尺度空间图像示例金字塔得构建， 第二组得第一副图像由第 一组得第一副到最后一副图像由一个因子 2降采样得到。图2 DoG 算子得构建： t o last image in t h e p revio us 图 1 Tw o o ct a ves of a G aus sia n s cale-spac e i ma g e pyr amid with s = 2 inte r vals 、Th e fir s t image i n t h e sec o nd o e t a ve is created b y dow n sa m p l ing Oj-taw J Octave 聖
深度解析：移动机器人的几种视觉算法谈到移动机器人，大家第一印象可能是服务机器人，实际上无人驾驶汽车、可自主飞行的无人机等等都属于移动机器人范畴。它们能和人一样能够在特定的环境下自由行走／飞行，都依赖于各自的定位导航、路径规划以及避障等功能，而视觉算法则是实现这些功能关键技术。 如果对移动机器人视觉算法进行拆解，你就会发现获取物体深度信息、定位导航以及壁障等都是基于不同的视觉算法，本文就带大家聊一聊几种不同但又必不可少的视觉算法组成。 本文作者陈子冲，系Segway Robot架构师和算法负责人。 移动机器人的视觉算法种类 Q：实现定位导航、路径规划以及避障，那么这些过程中需要哪些算法的支持？ 谈起移动机器人，很多人想到的需求可能是这样的：“嘿，你能不能去那边帮我拿一杯热拿铁过来。”这个听上去对普通人很简单的任务，在机器人的世界里，却充满了各种挑战。为了完成这个任务，机器人首先需要载入周围环境的地图，精确定位自己在地图中的位置，然后根据地图进行路径规划控制自己完成移动。 而在移动的过程中，机器人还需要根据现场环境的三维深度信息，实时的躲避障碍物直至到达最终目标点。在这一连串机器人的思考过程中，可以分解为如下几部分的视觉算法： 1．深度信息提取 2．视觉导航 3．视觉避障 后面我们会详细说这些算法，而这些算法的基础，是机器人脑袋上的视觉传感器。 视觉算法的基础：传感器 Q：智能手机上的摄像头可以作为机器人的眼睛吗？ 所有视觉算法的基础说到底来自于机器人脑袋上的视觉传感器，就好比人的眼睛和夜间视力非常好的动物相比，表现出来的感知能力是完全不同的。同样的，一个眼睛的动物
对世界的感知能力也要差于两个眼睛的动物。每个人手中的智能手机摄像头其实就可以作为机器人的眼睛，当下非常流行的Pokeman Go游戏就使用了计算机视觉技术来达成AR 的效果。 像上图画的那样，一个智能手机中摄像头模组，其内部包含如下几个重要的组件：镜头，IR filter，CMOS sensor。其中镜头一般由数片镜片组成，经过复杂的光学设计，现在可以用廉价的树脂材料，做出成像质量非常好的手机摄像头。 CMOS sensor上面会覆盖着叫做Bayer三色滤光阵列的滤色片。每个不同颜色的滤光片，可以通过特定的光波波长，对应CMOS感光器件上就可以在不同位置分别获得不同颜色的光强了。如果CMOS传感器的分辨率是4000x3000，为了得到同样分辨率的RGB 彩色图像，就需要用一种叫做demosaicing的计算摄像算法，从2绿1蓝1红的2x2网格中解算出2x2的RGB信息。
SIFT概述 SIFT特征是非常稳定的图像特征，在图像搜索、特征匹配、图像分类检测等方面应用十分广泛，但是它的缺点也是非常明显，就是计算量比较大，很难实时，所以对一些实时要求比较高的常见SIFT算法还是无法适用。如今SIFT算法在深度学习特征提取与分类检测网络大行其道的背景下，已经越来越有鸡肋的感觉，但是它本身的算法知识还是很值得我们学习，对我们也有很多有益的启示，本质上SIFT算法是很多常见算法的组合与巧妙衔接，这个思路对我们自己处理问题可以带来很多有益的帮助。特别是SIFT特征涉及到尺度空间不变性与旋转不变性特征，是我们传统图像特征工程的两大利器，可以扩展与应用到很多图像特征提取的算法当中，比如SURF、HOG、HAAR、LBP等。夸张一点的说SIFT算法涵盖了图像特征提取必备的精髓思想，从特征点的检测到描述子生成，完成了对图像的准确描述，早期的ImageNet 比赛中，很多图像分类算法都是以SIFT与HOG特征为基础，所有SIFT算法还是值得认真详细解读一番的。SIFT特征提取归纳起来SIFT特征提取主要有如下几步： ?构建高斯多尺度金字塔 ?关键点精准定位与过滤 ?关键点方向指派 ?描述子生成 构建高斯多尺度金字塔 常见的高斯图像金字塔是每层只有一张图像，大致如下： 上述的是通过图像金字塔实现了多分辨率，如果我们在每一层高斯金字塔图像生成的时候，给予不同的sigma值，这样不同的sigam就会产生不同模糊版本的图像，在同一层中就是实现不同尺度的模糊图像，再结合高斯金
字塔，生成多个层多个尺度的金字塔，就是实现了图像的多尺度金字塔。同一张图像不同尺度高斯模糊如下： 为了在每层图像中检测 S 个尺度的极值点，DoG 金字塔每层需 S+2 张图像，因为每组的第一张和最后一张图像上不能检测极值，DoG 金字塔由高斯金字塔相邻两张相减得到，则高斯金字塔每层最少需 S+3 张图像，实际计算时 S 通常在2到5之间。SIFT算法中生成高斯金字塔的规则如下（尺度空间不变性）： 关键点精准定位与过滤 对得到的每层DOG图像，计算窗口3x3x3范围除去中心点之外的26点与中心点比较大小，寻找最大值或者最小值（极值点），如下图：