sift
[小白学习教程之] 理解SIFT
在这篇教程中，我们通过对SIFT由简至繁的解释，来一步一步认识它。
什么是图像？
呐，你拿起手机，打开相机，对准目标，咔嚓一下。一幅图像就诞生了喔~。它保存在了你的手机里面，当然是以数字的形式喔。例如，下面这张奥巴马的照片就是图像，而它右边的数字就是保存在计算机里面的东西喔。
什么是特征？
特征是对一件事物的描述，例如：奥巴马的皮肤是黑色的，他是美国人。在这一描述中，黑色皮肤和美国人，就是我们提炼出来的关于奥巴马的特征。使用特征的目的，是便于将事物简化，而便于归类和区分，以快速地对一件事物进行识别，减少记忆负担。出现了两个人，一个皮肤白，一个皮肤黑，问，谁是奥巴马？我们能很快地通过皮肤黑，知道黑皮肤那个人是奥巴马。这是特征的区分性功能。还有一个功能是不变性。奥巴马可是会动的喔，他可以有不同的动作姿势，穿不同的衣服，在这些情况下，我们都要能识别出来，这个人是奥巴马喔。于是皮肤是黑色的这个特征就是奥巴马一直都不会变的一个特点喔，那记住这一点是不是很方便，在各种情况下都可以帮助我们去认出他。
对图像进行特征提取也是同样的目的。对于一幅图像或其中的某些区域，我们希望能通过一些数学运算，将原本由一大堆数字描述的图像或图像区域，变成由几十或几千个数字来描述，能方便我们用这些特征去对图像进行识别。
总结：特征是为识别服务的，有用的特征需要同时具备一定程度上的区分性和不变性。 |
什么是局部特征（local feature）？
局部是一个相对的概念，SIFT中提取的局部特征是组成一件事物的小块图像单元。例如，把图像中奥巴马的整个身体看做是一件事物，而其图像中的嘴角、眼角等小区域提取得到的特征，就是局部特征。
再比如，下面这幅图中，对ABCDEF这样子的小块图像进行特征提取，得到的特征就是局部特征。
为什么要提取局部特征呢？
| 因为：变量越少，观察结果上变化的可能性就越小。 |
有没有被吓到？“啊，为什么突然不友好了，放了一句晦涩难懂的话出来。”
没关系，睁大眼睛，请完成下面这个实验：请找出以下所有图片中，它们相似的地方。你会发现答案，一定是在局部。（呐，如果你学过概率统计，就懂方框中那句话了。这句话的道理还存在于其他算法思想中，读者可记住之后自行发散思维哟^_^）有没有被吓到？“啊，为什么突然不友好了，放了一句晦涩难懂的话出来。”
Step2: SIFT是scale Invariant Feature Transform的缩写
在Step1中，我们理解了，想要从成千上万张图像中，找出跟我们想要找的事物相似的图像，我们可以提取图像的局部特征，我们找到相同的局部特征，比对它们，就可以知道哪张图像是我们期望找出来的图像。
然而，历史上出现过的局部特征提取方法，可并不只有SIFT这一种喔，那么SIFT究竟有什么特别之处？而为什么又要这么做呢？在这个步骤中，我们将更加深入地理解局部特征，解答这两个疑惑。
下面回到建筑物这幅图，继续做实验：请在图中有出现过ABCDEF的地方，打上对应的标记。你会发现，ABCD的标记特别多，而EF的标记是唯一的。有木有。有！于是EF很特别。特别带来的好处是，定位准确，容易识别。
使用这些特别的图像局部区域，去匹配寻找相似的图像，能够防止其他无关图像的信息的干扰。于是，SIFT方法，致力于寻找到这样特别的局部图像区域，并对其进行准确的描述。
如何从图像中找到这些特别的局部区域？
方法：使用高斯差分函数（DoG）。 |
这里省略过多的数学介绍，只列举关键的几条公式。更多地我们直接从效果来看功能吧。
DoG的公式，是下面几条：
这里，看不懂公式不要紧，可以直接先跳过，等你有数学基础了，公式就很容易看懂了。你可以记住选用DoG的好处是：计算很方便，做两次图像高斯模糊，然后相减。
（图中：蓝色线是G(x,y,k*sigma)，红色线是G(x,y,sigma)，绿色线是G(x,y,k*sigma)-G(x,y,sigma)）
看上面这幅图，然后我们重点关注下绿色这条线。有没有疑惑，我想干嘛？我想以最直观的方式，带你走进数字的世界。
绿色线的数值从左到右为：
0.0000 0.0011 0.0505 -0.0516 -0.0516 0.0505 0.0011 0.0000
这些数值直接相加，其和约等于0，这意味着具有同样大小的8个数值，与绿色线对应相乘后求和的值依旧会约等于0。这种区域对应着图像中的一致区域，如建筑物图中的A小块。进一步，我们可以想象更多数值可能的变化，这里我简单先总结了一下，使用绿色这条线去与一个同样大小的信号对应相乘再求和，其会得到的结果可以为：
² 信号值的大小一致，则结果为0
² 信号值的大小与绿色线趋势完全一致，则结果很大
² 信号值的大小与绿色线趋势完全相反，则结果很小
² 其他情况，在中间
你有可能还不是很看得懂，不过没关系。下面，我们分析下图像信号中的情况，灰度图像信号的数值一般为0到255（或1（归一化后为1））之间的数（这里只想强调没有负数）；接着，我们可以重点关注下绿色线中间，3,4,5,6这四个位置上的值就相当于是在进行相邻位置上值的比大小的操作。3比4大，就会得到一个大值，相差越大值越大；同理，5比6小，也会得到一个大值，也是相差越大值越大。
说明：进行这种方式的思考总结，是为了能更好地理解实际应用中，可能会出现的情况。因为我们并不能用人脑所认知的，如“边缘”，“轮廓”，去想象，算法发生了什么，计算机处理的是数字，不要死记硬背“算法理论”。 |
好，下面继续。看几幅DoG运算（上面三条公式）的实验结果图。
左边是实验输入的原图像，右边是经过DoG计算后的图像。右图中，越亮值越大，越暗值越小。于是，可以很直观地看到，DoG图像中的大值和小值出现在图像区域发生较大变化的边缘处，没有变化的区域响应则接近于0，呈灰色。这与前面的分析一致，下面继续看下面两幅图。
这两幅图显示了上面两幅图的具体数值，其中红色方框标记的位置，恰巧是图像的拐角处，传说中的角点，也就是Step2最前面的EF图像块。而拐角处的DoG值，恰巧是最小的那个值。为什么呢？前面我们分析了一维的DoG是在比较中间和两边的大小，二维的DoG呢，实际上就是在比较，中间和周围的大小，统计了各个方向的变化（参考下图）。平缓的边缘处，图像区域的变化反向比较单一，而拐角处图像区域的变化则体现为多个方向，于是多个方向都有变化的区域会在数值上表现为极大或极小。通过找到这些极大或极小的值，就能找到一些想要的特别的图像局部区域，使用DoG检测图像中的特别的局部区域的原理就是这样。（注：图中（40,40），（20,20）是因为图像放大了2倍）
然而，是否能成功地使用DoG寻找到图像中特别的局部区域，有一个非常关键的参数：公式中像黄豆长出了一点芽的那个符号，sigma。这个参数，调整着算法观察图像区域的窗口大小（如果你把二维DoG看作帽子，说的就是帽子口有多大），当这个观察窗很小的时候，例如0.5，是有很大可能性不会出现局部极值的，这一点在后面的内容中有解释。另外是，要记得计算时把图像数值类型转换为有符号型，毕竟DoG计算后的结果是有正有负的，极值既可能是大的正数，也可能是小的负数，这取决于变化区域是由小变大还是由大变小。（笔者认为这些东西是需要留意的细节，额，笔者在写这篇教程的时候，曾在此处栽了跟头。）
为何提出尺度不变性特征（ScaleInvariant Feature）？
| 因为：随着物体在图像中大小发生变化，属于该物体的局部区域的大小也发生了变化。 |
对于一个局部图像区域，这里以角为例：如下图中所示，若是采用同样的局部大小窗对图片进行观察，左边的小角，在变大之后的右边再观察，就看不出是一个角了。于是，必须提出具有尺度不变性的特征，才能在物体大小发生变化后，依然能进行正确地匹配。
如何实现尺度不变特征的提取？
行业内大家一直在用的方法：多尺度遍历。具体地，将一张图像缩放为多个分辨率图像，对多个分辨率的图像进行处理，然后从多个分辨率的图像处理结果中整合出最后的结果。此处的学名叫尺度空间，别处的学名叫图像金字塔。Orz，别想太多。 |
从上一小节中，我想大家应该有一个直观的印象，说观察窗口小了，那么把窗口放大点或者把图像缩小点不就好了。对，其实很多问题的解决方案就是这么直接的，别想太多！
然而，大神们厉害的地方就在于，把如此直观的东西，总结整理成了理论（传说中的Scale Space Theory）。然而，大神们写的理论，笔者并没有完全看懂，要是你看懂了，来，教教笔者。但是呢，为了继续下去，笔者暂且脑补了一下尺度空间的想法：
大神们通过观察物理世界发现，不同尺度去观察事物时，会得到不同的类别划分。例如，站在远处看到，一大片竖着的绿色，我们说是森林；走近一点，我们说是一棵树；再近一点，我们说是树干、树枝和叶子。于是，大神们认为，对图像进行多尺度的特征描述是很有必要的。并且，大神们还认为，观察尺度变大的过程中，图像细节方面的信息逐渐被抑制，但图像区域与区域间的间隔将会在多个尺度上得到保留，并且在观察尺度发生变化的过程中，没有新的图像信息产生（如下图中所示）。这与人眼的机制一致，当我们离被观察的事物越来越远时，事物的成像就会越来越模糊，变得只看得清一个大概；而离得很近的时候，就能将细节看得很清楚。在图像识别的应用中，如果一个物体出现在图像中的尺寸大，此时，我们可以使用细节方面的局部特征去对其进行识别；当一个物体出现在图像中的尺寸很小时，此时就相当于远距离看这个事物，我们使用大尺度上的特征去对其进行识别。大神们提出了，满足上面所述的这些条件的尺度空间理论，并且证明说，只有高斯函数符合用来构造这样子的尺度空间所需的条件。
于是乎，为了获取尺度不变的特征，SIFT将在这样的尺度空间中，去寻找不同尺度的特别的局部图像块。比较方便的是，现在，尺度空间的构建和特别的局部图像块检测都是用高斯函数了，就一起算就好了。于是，如下面这张图（figure1）所示，从初始图像开始，作者以一个常数k（DoG公式中），递增地去产生尺度空间图像，然后将尺度空间中相邻的两张图像相减就得到了对应的DoG图像。以一个固定的大小，将尺度空间划分为多个octaves，每一个octave能产生s个有效的局部块检测尺度，每一个octave必须有s+3张尺度空间图像，并令k=2^(1/s)。下一个octave的图像大小是上一个octave图像大小的1/2。这样的设计，使得高斯函数sigma的取值，能够连续覆盖整个尺度空间，同时减少了计算量（后面解释）。
上面介绍的尺度空间，还有一个特点是，前面小节介绍过的DoG图像的极值点，在这样的尺度空间中会在对应尺度上呈现极值，而在相邻尺度上偏移离开极值。原因，可以想象到，窗口小一点包含的变化就少了一点，窗口大一点细节丢失包含的变化同样也少了一点。于是，尺度空间中的局部极值检测，如下面下面的图（Figure2）中所示，只需要比较自己和相邻尺度的局部区域，就可以了。于是乎，想要获得一个尺度空间极值点必须有3张DoG图像，想检测s个尺度空间的极值点，需要s+2张DoG图像，而想获得s+2张DoG图像，需要s+3张尺度空间图像。于是解释了前面提到的，为什么一定是s+3张尺度空间图像。接着，我们来看k值和octave的设计，为什么说k值和octave的设计满足了尺度空间极值检测的空间连续性。证明：需求s个尺度空间极值点，上一个octave的最后一个极值尺度简写为k^s=(2^(1/s))^s=2，下一个octave的第一个极值尺度简写为2*k=(k^s)*k，由此极值点检测的尺度空间是严格按照k呈等比递增的，证毕。
（如果到这里，你看懂了，已经可以为SIFT的作者鼓掌了，因为前面所讲的每一步设计都很巧妙。同时也鼓励下自己，你看懂了。）
多尺度的特别局部图像块检测还需要后处理？
使用前面提到的DOG方法，可以获得图像中很多特别的局部图像块。然而，DOG方法不仅会对特别的局部图像块有极值响应，对于噪声和强边缘也同样会有响应。为了获得对于图像匹配和识别来说，更加稳定的局部图像块。SIFT中，还会对DOG的检测结果，进行后处理，去除低对比度的，和边缘上的局部图像块。
1. 去除低对比度的局部图像块
图像局部块的对比度，SIFT中，用DOG响应的绝对值大小来度量。这很说得通，因为DOG运算的本质是度量一个像素点和其周围像素的不同，值越大则对比度越高。去除小的值的点，保留有较大响应的点。
SIFT通过构建尺度空间来计算不同尺度下观察到的特别的局部图像块，由于尺度采样操作的存在，极值点的位置存在偏移，为了得到更精确的极值点的位置和其响应值。SIFT中，假定了DOG响应局部区域的连续性，用二阶泰勒展开式来拟合并估计DOG的响应值。
如上图中所示，假定D(x)是一条山丘形状的平滑的曲线，在山顶和山谷的地方，分别是D(x)真正的极值点。DOG运算中，获得了极值点附近的点。通过已检测的点计算真正的极值点的方向，可迭代获得真正的极值点的位置和其更准确的响应值。（#TODO：这里的补充知识是牛顿迭代法，结合文中公式去了解学习）
2. 去除边缘上的局部图像块
边缘局部图像块的特点是，边缘的梯度值是朝同一个方向的，于是会呈现明显的梯度主方向。SIFT寻找的局部图像块，期望局部块中的主梯度方向与其他方向的梯度相差不要太大。通过计算DOG的二阶导数，得到主梯度方向和其他方向的比值，保留该比值小于一定数值的局部特征点。（具体参见论文中的公式）
计算关键点的方向
为了获得具有旋转不变性的特征描述子，还需要计算每一个检测到的关键点的方向信息。具体做法是：对于以关键点为中心的一个局部区域，计算其中每个位置的边缘的梯度方向（orientation）及其幅值（magnitude），梯度方向划分为36个bin进行统计，相当于每个bin的区间为10度；随后使用高斯权值，将局部区域中每个位置上的直方图，进行高斯加权的幅值相加，得到最终该关键点的梯度方向直方图。随后，选择最大和80%的次大值为该关键点的方向。最后，对于每个关键点，有三个信息：位置、所处尺度、方向。
关键点特征描述
通过前面的步骤，已经获取了关键点的三个信息：位置，尺度和方向。这三个信息，为图像的特征描述提供了不变性。对关键点进行特征描述，对应于以下步骤：
1. 计算整幅DOG图像的梯度（包括梯度幅值及其方向）；
2. 对以关键点为中心的窗口（16x16 pixel）内的坐标，按照关键点的方向进行旋转；
3. 同样使用高斯权值对对应像素进行统计加权，进行方向直方图统计，得到4x4小格，8方向的描述子；为了保证直方图的统计平滑，使用三线性插值进行统计；
4. 为了减小光照变化的影响，对得到的4x4x8=128维特征向量，进行单位长度归一化；图像对比度的变化，相当于图像梯度乘以了一个常数，进行归一化会去除对比度变化的影响；然而，归一化并不能去除，非线性的光照变化的影响；为了减少大梯度带来的影响，约束特征向量的数值不大于0.2，然后重新归一化；这意味着，大的梯度幅值不那么重要，梯度方向分布信息得到强化。
Step？: 读SIFT的实现代码
实现步骤：
1. 关键点检测：获取关键点的位置及其尺度
a) 计算尺度空间图像
i. 图像归一化0~1之间
ii. 将原始图像放大2倍，作为尺度空间的初始图像
iii. 按照相应的尺度参数，计算尺度空间高斯平滑图像
b) 计算DoG图像：将相邻尺度空间图像相减
c) 通过极大极小值，求取关键点
d) 去除不好的关键点
2. 对关键点进行描述：计算关键点的特征向量
a) 计算关键点特征主方向
b) 将坐标轴旋转为关键点方向，以确保旋转不变性
c) 对于一个关键点产生128个数据，即最终形成128维的SIFT特征向量
1. 局部特征的概念
2. 尺度空间技巧
3. DOG算子
4. 插值技巧
5. 过滤边缘的主梯度方向比技巧
6. 直方图统计技巧
7. 高斯加权累加技巧
8. 三线性插值平滑统计直方图的技巧
9. 特征向量归一化技巧
参考资料：
[1] http://OpenCV-Python-tutroals.readthedocs.org/en/latest/py_tutorials/py_feature2d/py_features_meaning/py_features_meaning.html
[2] http://opencv-python-tutroals.readthedocs.org/en/latest/py_tutorials/py_feature2d/py_sift_intro/py_sift_intro.html
[3] http://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf
[4] http://www.pa-portal.org/smash/get/pa2:457189/FULLTEXT01.pdf
[5] http://homepages.inf.ed.ac.uk/rbf/HIPR2/log.htm
[6] http://blog.csdn.net/zddblog/article/details/7521424
相关阅读
罗德里格斯公式（Rodriguez formula）是计算机视觉中的一大经典公式，在描述相机位姿的过程中很常用。公式：R=I+sin(θ)K+(1−cos(θ
概念:最小二乘法是一种熟悉而优化的方法。主要是通过最小化误差的平方以及最合适数据的匹配函数。 作用：（1）利用最小二乘法可以得到
https://blog.csdn.net/feilong_csdn/article/details/64128443logistic回归，又叫对数几率回归（从后文中便可此名由来）。首先给大家
entrySet是java中的一个对象，一般可以通过map.entrySet()得到。1，entrySet实现了Set接口，里面存放的是键值对。一个K对应一个V。2，用
插值法就是一个从已知点近似计算未知点的近似计算方法，即构造一个多项式函数，使其通过所有已知点，然后用求得的函数预测位置点。下面