科学是靠intuition、logic、experience、trick逐渐构筑的。

做科研可以站在巨人的肩膀上，很多idea可以相互借鉴。

目录

  1. 引言
  2. scale-space extrema detection
  3. accurate keypoint localzation
  4. orientation assignment
  5. keypoint descriptor
  6. object recognition
  7. conclusion

引言

这篇文章发布在IJCV 2004年，全文一共28页，是CV界引用最多(4w+)的文章之一。SIFT全称scale invariant feature transform，即是尺寸不变性特征转换。它可以将图像数据转化成与尺寸无关的本地特征。该特征很稳定，图像尺寸、旋转角度、纺射曲折、视角变化、噪音以及光照变化对该特征的影响都比较小。

这篇文章主要讲两个事情：如何提取SIFT descriptor以及如何利用它做object recognition。

scale-space extrema detection

关键点检测的第一步是找到它们在不同物体视野情况下都不变的位置和大小。要想找到对尺寸无关的特征，可以在很多不同尺寸的图像中寻找稳定的共同特征，这就是尺度空间的来源（scale space）。图像的尺度空间就是由一组经过不同参数的高斯滤波后的图像矩阵构成。

Marr Hildreth在谈到Laplacian of Gaussian filter时谈到：

Zero crossings that coincide over several scales are physically significant.

同时，实验也表明，尺寸正则化后的LoG中的极值是最稳定的图像特征。

因此计算LoG应该可以获得SIFT特征。LoG可以理解为图像矩阵的二阶导数，但是计算二阶导数代价大，因此作者提出一种逼近的方式（DoG，difference of Gaussian）来得到LoG。

下面是这种逼近方式的理论基础：

在物理世界中，经过对一些现象的研究，科学家发现：

frac{partial G}{partial sigma} = sigmaDelta^2G

而根据导数的定义：

frac{partial G}{partial sigma} = frac{G(x,y,ksigma)-G(x,y,sigma)}{ksigma-sigma}

所以我们可以得到DoG与LoG的关系：

DoG=G(x,y,ksigma)-G(x,y,sigma)=(k-1)sigma^2Delta^2G=(k-1)LoG

这样做的好处是用只需要做减法的DoG代替了求导的LoG。

下面作者给出计算DoG的方法：

上图左边是scale space。它通过不同参数的Gaussian filter与原图像做卷积操作得到。右边是相邻的Gaussian 矩阵相减后得到的矩阵，即是DoG。

那么什么是我们要找的尺度不变性的关键点呢？

作者提出对比DoG像素点相邻的26个邻域，选最大值或最小值作为candidate keypoint。

上图绿色的circle就是26个邻域。

作者通过实验得出，对于一个size的image，3个scale的Gaussian是最好的，同时 sigma 取1.6，k取 sqrt2 。

Accurate keypoint localization

通过上述步骤，我们就找到了candidate keypoint的location以及对应的scale。这样的keypoint是有很多的。下面我们需要进一步精确找到keypoint以及筛选keypoint。

怎么在这些location和scale里面精确找到keypoint呢？作者借鉴别人的想法，使用了泰勒展开式。上一步可以看做是离散的极值，而泰勒展开找到的极值可以理解为连续的极值，是更精确的。

对scale space function进行泰勒展开：

其中D和偏导数是在采样点计算的，而x则是这个采样点的偏移量。

那么x取得极值的条件为它的一阶偏导数为0的时候，此时x取值为：

这就是精确的location。

此外，作者还提出过滤掉对比度底的candidates以及在edge上的keypoint。

过滤掉low contrast的keypoint是因为他们可能对scale敏感。

low contrast的keypoint通过计算 |D(x)| 来判定，低于0.03将会认定为low contrast，我们会丢弃它。

由于边上的keypoint是不稳定的，我们要过滤它。因为scale space function沿著边是有很大的principle curvature而与边垂直的方向则很小。通过这个性质，我们可以找到一个方法来过滤掉这些keypoint。

principle curvature可以通过计算一个矩阵来获得，即是Hessian matrix H:

这个矩阵的特征值跟principle curvature成正比。因此计算求H的特征值将会帮组我们。借鉴harris Corner detection的优化，通过计算行列式的迹以及行列式的值可以代替求特征值。

通过检查上述公式即可过滤。其中r是大特征值与小特征值的比。当r>10时，将过滤掉这个keypoint。

上图是处理后的结果。

Orientation assignment

作者提出，通过给关键点一个方向，那么提取出的本地特征将会对图像的旋转变化不敏感。

上图是orientation assignment的过程。

首先通过计算image的gradient，包括了梯度的大小以及梯度的方向。然后对于一个采样点，划定固定的小方框，对梯度方向进行加权投票，权数为梯度大小，最后得到了一个八个方块的梯度方向直方图。由于是对方向进行计数，这种特征对少量的位移是稳定的。

keypoint descriptor

上图右侧就是keypoint的描述子。

经过试验，4*4+8bin的descirptor是最好的，因此每个关键点将会产生128维的特征向量。

得到特征向量还需要对它正则化，让他对光照不敏感。

object recognition

目标检测的流程主要是这样的：

第一步：对所有资料库的图片进行SIFT，然后作为匹配库。

第二步：提取待识别图片的SIFT keypoint descriptor，然后查找匹配库，欧几里得距离最近的邻居将作为输出，如果有超过三个关键点匹配构成的群体，即为识别出的目标。

但是这里面有很多的trick。

第一个trick就是最近邻的选择，它不是取一个全局的阈值，然后大于这个threshold的就认定为最近邻。因为一些描述子可能更容易辨别，需要低的threshold。而另一个描述子则更难辨别，需要高的threshold。这里作者提出了更好的办法：计算最近邻距离与第二近邻距离的比例。

如果两个候选者都很像，就会有歧义，不知道哪个更好，如果两个候选者差别很大，说明区分度很高，这个好的匹配。

第二个trick是查找演算法的改进。在128维的特征向量里面寻找最近邻，即使是像kd树这样的演算法也不会加快查找。因此作者提出了BBF（best-bin-first）的演算法。这个演算法修改了kd树查找的优先顺序。当查找的节点超过200个时以及两个节点距离很近时，将会进行剪枝操作。这提高了查找速度。

第三个trick是在pose space用hough transform对features进行聚类。

最后使用最小乘方法对其进行几何验证，得出匹配结果。

下面是一些识别的样例：

可以看出效果还是很不错的。

conclusion

现在我们总结一下SIFT的过程：

  • 生成图像的尺寸空间
  • 检测尺寸空间的极值
  • 使用泰勒展开精确定位关键点
  • 使用一些方法筛选关键点
  • 方向赋值
  • 计算关键点附近16*16大小的梯度大小和方向
  • 构成关键点4*4大小8个bin的descriptor

可以看出，这个过程是十分繁琐的，而且必须要有大量实验来确定每一个参数的值。我来做可能要死==。像梯度、泰勒展开依然是很重要的基础。而且作者也有借鉴一些物理学以及其他人做实验的结论来指导论文的思想。这篇论文讲得很详细，每一个过程都讲了原理、参数的选择。最后是一些实验结果，总结。

reference

  1. SIFT video
  2. SIFT paper

推荐阅读：

相关文章