sift算法简介.doc

SIFT特征匹配算法简介1、SIFT算法基本概念Sift是David Lowe于1999年提出的局部特征描述子，可以处理两幅图像之间发生平移、旋转、仿射变换情况下的匹配问题，具有良好的不变性和很强的匹配能力。SIFT算法是一种提取局部特征的算法，也是一种模式识别技术，其基本思想是在尺度空间寻找极值点，提取位置，尺度，旋转不变量，它主要包括两个阶段，一个是Sift特征的生成，即从多幅图像中提取对尺度缩放、旋转、亮度变化无关的特征向量；第二阶段是Sift特征向量的匹配。Sift及其扩展算法已被证实在同类描述子中具有最强的健壮性，目前是国内外研究的热点。2、SIFT算法的主要特点：a) SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变 性，对视角变化、仿射变换、噪声也保持一定程度的稳定性，而对物体运动、遮 挡、噪声等因素也保持较好的可匹配性，从而可以实现差异较大的两幅图像之间 特征的匹配。b)独特性(Distinctiveness)好，信息量丰富，适用于在海量特征数据库中进行 快速、准确的匹配，比原有的harris点匹配方式具有更高的匹配准确度。c) 多量性，即使少数的几个物体也可以产生大量SIFT特征向量。 d) 高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。 e) 可扩展性，可以很方便的与其他形式的特征向量进行联合。SIFT算法基于图像特征尺度选择的思想，建立图像的多尺度空间，在不同尺度下检测到同一个特征点，确定特征点位置的同时确定其所在尺度，以达到尺度抗缩放的目的。剔除一些对比度较低的点以及边缘响应点，并提取旋转不变特征描述符以达到抗仿射变换的目的。3、SIFT算法步骤：1） 构建尺度空间，检测极值点，获得尺度不变性；2） 特征点过滤并进行精确定位；3） 为每个关键点指定方向参数4） 生成关键点的描述子5） 当两幅图像的Sift特征向量生成以后，下一步就可以采用关键点特征向 量的欧式距离来作为两幅图像中关键点的相似性判定度量。取一幅图中的某个关键点，通过遍历找到另一幅图中的距离最近的两个关键点。在这两个关键点中，如果次近距离除以最近距离小于某个阙值，则判定为一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。4、SIFT算法发展历程：Sift算子最早是由David.G.Lowe于1999年提出的，当时主要用于对象识别。2004年David.G.Lowe对该算子做了全面的总结及更深入的发展和完善，正式提出了一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子Sift（ Scale Invariant Feature Transform )算子，即尺度不变特征变换。Rob Hess 基于GSL和Opencv编写了相应的C语言程序，后来Y.Ke将其描述子部分用PCA代替直方图的方式，对其进行改进。在Mikolajczyk对包括Sift算子在内的十种局部描述子所做的不变性对比实验中，Sift及其扩展算法已被证实在同类描述子中具有最强的健壮性。主要文献：1）David G. Lowe, Object recognition from local scale-invariant features, International Conference on Computer Vision, Corfu, Greece2）David G. Lowe, Distinctive image features from scale-invariant keypoints, International Journal of Computer Vision, 3）Y. Ke and R. Sukthankar. PCA-SIFT: A More Distinctive Representation for Local Image Descriptors.Computer Vision and Pattern Recognition, 20045、关于局部不变特征1)局部不变特征的概念局部不变特征就是由局部邻域所构成的一个图像模式。局部不变特征可以是点集，也可以是边缘集合，或者一些小的图像块集合，甚至是上述集合的复合体。局部不变特征认为图像中总是存在一些特殊的区域，这些区域中的特征比其它图像区域的特征更加稳定，信息含量更高，能够表征图像的内容。局部不变特征的局部是指特征只是图像的局部区域，不变性是指该特征不会因为图像经历了各种变换而发生变化。2）局部不变特征特点局部不变特征的种类繁多，适合不同的特征提取场合，各自独立性较强，相互之间可以组合和借鉴。复合类型的局部不变特征可能会增加计算负担，但是能够取得更好的性能。3）局部不变特征的应用局部不变特征是一种十分有效的工具，大量研究表明它能够适应各种图像处理的应用场合，特别是在模拟人类视觉系统的物体识别领域，拥有强大的应用性。从直观的人类视觉印象来看，人类视觉对物体的描述也是局部化的，基于局部不变特征的图像识别方法十分接近于人类视觉机理，通过局部化的特征组合，形成对目标物体的整体印象，这就为局部不变特征提取方法提供了生物学上的解释，因此局部不变特征也得到了广泛应用。4）特征描述符特征描述符(Featrue Descriptors)指的是检测图像的局部特征（比如边缘、角点、轮廓等），然后根据匹配目标的需要进行特征的组合、变换，以形成易于匹配、稳定性好的特征向量，从而把图像匹配问题转化为特征的匹配问题，进而将特征的匹配问题转化为特征空间特征向量的聚类问题。5）局部不变特征检测与局部不变特征区域的概念局部不变特征检测就是从图像中检测出具有某种几何和光学不变性(geometric and photometric invariant)的局部不变特征区域。局部不变特征区域是以特征点(feature point or key point)为中心带有尺度信息的图像局部区域。局部不变特征认为，在大多数的图像中总能找到一些性质特殊的区域，它们可以稳定的提取，并且对各种图像变化具有良好的鲁棒性且包涵更多的图像内容信息。6、基于局部不变特征的图像处理理论和技术主要包括四个部分：1）图像尺度空间：图像数据包含大量混杂在一起的特征信息，按照局部不变特征的思想，这些特征信息是归属于不同类型不同属性的目标物体，其位置和控制区域各不相同，不同分布和参数的特征相互叠加和组合，这使得特征提取变得困难，所以需将这些特征进行一定的“分离”操作，将各类特征分散到整个图像数据空间中去，图像尺度空间就是为图像的各种不同类特征分离提供的一种数据表示法。2）局部不变特征检测：在尺度空间内构造不变特征检测函数，生成对应尺度下的局部不变特征空间，检测其中具有一定特征显著性的局部不变特征区域，并把它作为特征描述的目标区域，确定每个特征的尺度系数，局部不变特征结构的位置和尺度范围。这些局部区域及其包含的信息形成对图像语义结构信息的表示，为进一步的特征描述提供图像内容的结构和范围信息。3）局部不变特征描述：局部不变特征检测获得的特征仅仅给出了图像内容的结构信息，局部不变特征区域还需要从图像尺度空间表示的数据形式转化特征描述向量。局部不变特征描述就是用局部不变特征描述符(Local feature descriptor)去描述局部不变特征区域，用尽可能相互独立和完备的特征描述数据来表示复杂组合的目标物体，完整详细地描述图像内容，给出图像的语义信息。4）特征匹配和检索：特征提取的最终目的是使用这些特征来进行目标识别和特征的检索，通过对特征描述空间中的特征数据进行分类、匹配和检索，实现各种图像识别应用。由于其良好的鲁棒性和抗干扰性，使的它作为目标识别中机器学习样本描述的首选特征，图像和视频检索方法也大都采用局部不变特征作为学习和检索的依据。7、局部不变特征发展方向目前，局部不变特征主要分为两个发展方向：1)结构化的局部不变特征提取模型，也就是特征提取模型分为四个较为清晰的处理模块（上文中有提到）。在局部不变特征检测方面，D.Lowe提出基于扩散方程的尺度不变的SIFT特征检测方法，以及由角点检测发展而来的Multi-scale Harris检测，具有仿射不变性的Harris-Laplace/Affine检测等，目前局部不变特征检测方法逐渐向着检测具有多种不变性和抗干扰性强的局部不变特征的方向发展。局部不变特征描述技术更加广泛，其中以SIFT，GLOH,Steerable Filters,Shape Context,Complex Filters等为主要特征描述符。特征检索和匹配模块一般是面向图像模式识别的具体应用场合，如图像检索，机器学习的样本特征集合，目标识别中的样本特征数据库等，同时在视频的检索领域也获得不错的效果。2)模仿人类的视觉系统，通过模仿人类视觉系统的运作原理提出了显著性区域理论。这一理论认为图像中的每个局部区域的重要性和影响范围并非同等重要，即特征不是同等显著的，其主要理论来源是Marr的计算机视觉理论和Treisman的特征整合理论，一般也称为“原子论”。该理论认为视觉的过程开始于对物体的特征性质和简单组成部分的分析，是从局部性质到大范围性质，图像中的每个局部不变特征的视觉显著性是不同的，所以在局部不变特征的提取和描述时也遵循与人眼视觉注意选择原理相类似的机制（Visual Selective Attention Mechanism）。8、软件：SIFT Keypoint Detector该软件是可以在Linux或Windows系统中运行的汇编代码形式的SIFT特征点检测器， 它可以输出特征点和可以匹配到一个简单的ASCII格式文件需要的所有信息。 所提供的MATLAB程序和示例C代码可以读取特征点并根据它们对两幅图片进行匹配。9、应用前景SIFT算法是模式识别的一种高效手段，凡模式识别的应用方面都可运用SIFT算法来改进识别速度。医学：运动学人体机能研究仿生学：人工模拟生物人工智能：智能机器人、智能驾驶刑侦技术：跟踪军事用途：敌友识别（战机、战舰、潜艇、雷达跟踪等等）SIFT算法的一些基本概念降采样：对于一幅图像而言的降采样就是每隔几行、几列得到取一点，组成一个新的图像。以比例因子为2（fact of 2）的降采样来说：就是対一幅图像每隔一行一列取一点。对于nn的图像就变为n/2n/2的图像了。比例因子为2的降采样是SFIT要用到的！升采样：其实一种插值，就是在一幅图像里利用相关的插值运算得到一幅大的图像！比如比例因子为2的升采样就是每个相邻像素点种插值出一个像素（这里包括X、Y两个方向）。对于nn的图像就变为2n2n的图像了。顺便说下插值，就是一种利用已有数据对位置数据的估计。比如我第10秒走了12米，第20走了30，那么我用线性插值估计我第15秒走了（30-12）/2+12=21米，当然插值的方法有很多！图像金字塔：简单的说是一个图像集，由一个原始图像经过降采样得到一幅图像，再对新的图像做降采样，重复多次构成的一组集合。如果形象的把这些图像摞起来就想一个金字塔，故此得名。高斯卷积：就是权函数为高斯函数的卷积模板运算，高斯卷积有一次和二次.。通常做高斯卷积后的图像会比原图像平滑但也会模糊，所以又称高斯模糊！因为这不能写公式，很多的细节可以看下面的附件里的图片！高斯金字塔：高斯金字塔里有两个概念：组（Octave）和层（Level或Interval），每组里有若干层！高斯金字塔的构造是这样的，第一组的第一层为原图像，然后将图像做一次高斯平滑（高斯卷积、高斯模糊）高斯平滑里有一个参数，在SIFT里作者取1.6，然后将乘一个比例系数k作为新的平滑因子来平滑第一组第二层得到第三层。重复若干次，得到L层他们分别对应的平滑参数为：0，k，k2.。然后将最后一幅图像做比例因子为2的降采样得到第二组的第一层，然后对第二组的第一层做参数是的高斯平滑，对第二层做k的平滑得到第三层.这里一定注意：每组对应的平滑因子是一样的！而不是像有的资料上说的持续递增。这样反复形成了O组L层。一般模糊的高斯模板长宽都约为6（这里为当次的平滑因子，就是可能是k，k2.）DoG（Difference of Gaussian）金字塔：他是由高斯金字塔构造出来的，他的第一组第一层是由高斯金字塔的第一组第二层减第一组第一层，他的第一组第二层是由高斯金字塔的第一组第三层减第一组第二层得到，（说的这么繁琐是为了大家能理解的直观点）。没组都这样就生成了DoG金字塔。顺便说一下，DoG金字塔每组图像几乎都是一片黑，但仔细看你能看出轮廓的。两个金字塔在SIFT算法里的特殊说明：1、在SIFT里高斯金字塔的第一组第一层通常是由一个原图像长宽扩大一倍开始的，这样做是为了可以得到更多的特征点2、大家可以发现如果用每组5层的高斯金字塔构造一个DoG金字塔的的话，DoG的每组的层数是4。3、对于DoG金字塔，特征点的搜索从每组的二层到倒数第二层的（后面说明为什么），所以如果实际用n层那么DoG金字塔应该有n+2层，那么对应的高斯金字塔应该有n+3层。4、由于这样所以高斯金字塔从第二组开始的每组第一层是由上一组的倒数第二层降采样得到的。梯度：就是一个有方向和长度的向量，它的意义是一个函数的某一点上数值变化最大的方向和变化量。在图像中一个像素点的梯度是由它周围的8个点计算得到的。（公式见附件的图）K-d树：一种数据结构，用于搜索高维最邻近点，他是一种二叉树，每个节点是一个高维向量。对于他的具体说明我没仔细看呢，如果做到最后需要请大家参考这个：顺便说下维基百科不错！/wiki/Kd-tree尺度：这个概念最让我郁闷，现在弄的不是很清楚。我现在的理解就是（这不是它的概念）：1、表示同一事物所用到的图像像素量，用的多尺度就小，用的少尺度就大。2、它和图像的清晰程度有关，如上面说的高斯模糊，那么因子越大得到的图像越模糊，那么尺度越大！3、图像的旋转、平移尺度是不变的，但是放大、缩小、尺度就变了。算法简介：Sift 主要包括两个有价值的部分：1.提供了一个detector，也就是说提供了一种在一张图片上寻找有价值点的方法。这里“有价值”有些ambiguous，我现在的水平也不能清楚具体的说明什么样是有价值。2.提供了一个旋转不变并且对整体光照变化不明感的descriptor。【detector】在选取特征（feature）这一步中，David（creator of sift）使用了blob detctor中的一种方法，叫做difference of gauss（DOG），这种方法是laplacian of gauss的近似。这是因为高斯函数是扩散方程的近似，而扩散方程的左边就是差分（difference），右边就是laplacian operator。这种方法是对DOG函数或者LOG函数在尺度和空间维计算极值点，并且将极值点作为特征提取出来。关于blob detector和LOG，DOG可以参考：blob detection wiki /wiki/Blob_detection在使用了DOG选出特征之后，为了能够增加特征点的稳定性（就是在噪声影响下仍然能够被检测出来的性能，原文中叫做repeatability），david又做了两件事情：排除边缘点，和排除对比度差的点。排除对比度差的点是因为低对比度对噪声很敏感，排除边缘点是因为边缘点对整体光照不是很robust（这一点我不是很确定。）【descriptor】Orientation assignment 为了能够实现旋转不变性，david在feature point的neighbor block中计算所有点的梯度方向，并且