图像匹配算法研究之sift算法

 

 

Sent to you by Zhiyuan via Google Reader:

 

 

图像匹配算法研究之sift算法

via 博客园_首页 by blue_lg on 7/16/12

SIFT算法由D.G.Lowe 1999年提出，2004年完善总结，论文发表在2004年的IJCV上，主要用于提取具有图像旋转不变性和伸缩不变性的特征点。

这项技术可以推广到图像识别、图像拼接以及图像恢复等。

 David G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, 60, 2 (2004), pp. 91-110

论文详细地址：lowe sift算法

 

算法主要分为4个步骤：

• scale-space extrema detection--尺度空间上的极值检测

• keypoint localization--关键点的定位
  
  
• orientation assignment --为关键点标定方向
  
  
• keypoint descriptor--提取特征点描述符

 

 

$1.  尺度空间上的极值检测

      在介绍这一部分的时候，先引入几个概念：

•       降采样：对于一幅图像而言的降采样就是每隔几行、几列得到取一点，组成一个新的图像。以比例因子为2的降采样来说：就是対一幅图像每隔一行一列取一点。
•       升采样：其实一种插值，就是在一幅图像里利用相关的插值运算得到一幅大的图像！比如比例因子为2的升采样就是每个相邻像素点种插值出一个像素（这里包括X、Y两个方向），最常用的插值方法有线性插值等。
•       图像金字塔：由一个原始图像经过降采样得到一幅图像，再对新的图像做降采样，重复多次构成的一组集合。以采样因子2为例说明，如果形象的把这些图像摞起来就想一个金字塔，每次之间长和宽大小恰好为2倍关系，故此得名。
•       高斯卷积：就是权函数为高斯函数的模板进行卷积运算。通常做高斯卷积后的图像会比原图像平滑但也会模糊，所以又称高斯模糊！
•       高斯金字塔：高斯金字塔里有两个概念：组（Octave）和层（Level或Interval），每组里有若干层！高斯金字塔的构造是这样的，第一组的第一层为原图像，然后将图像做一次高斯平滑（高斯卷积、高斯模糊）高斯平滑里有一个参数δ,在SIFT里作者取1.6 。然后将δ乘一个比例系数k作为新的平滑因子来平滑第一组第二层得到第三层，重复若干次，得到L层（L一般取5）他们分别对应的平滑参数为：0，δ，kδ，k²δ，k³δ。然后将最后一幅图像做比例因子为2的降采样得到第二组的第一层，然后对第二组的第一层做参数是δ的高斯平滑，对第二层做kδ的平滑得到第三层.....这里一定注意：每组对应的平滑因子δ是一样的,而不是像有的资料上说的持续递增。这样反复形成了O组L层的高斯金字塔。一般模糊的高斯模板长宽都约为6δ（这里δ为当次的平滑因子，就是可能是kδ，k²δ..）
•       DoG（Difference of Gaussian）金字塔：是由高斯金字塔构造出来的，他的第一组第一层是由高斯金字塔的第一组第二层减第一组第一层，他的第一组第二层是由高斯金字塔的第一组第三层减第一组第二层得到。每组都这样就生成了一个DoG金字塔。顺便说一下，DoG金字塔每组图像几乎都是一片黑，但仔细看你能看出轮廓的。
  
  

  

  
  

         最后关于金字塔具体处理的说明：

           1）在SIFT里高斯金字塔的第一组第一层通常是由一个原图像长宽扩大一倍开始的，这样做是为了可以得到更多的特征点 ；

           2）大家可以发现如果用每组5层的高斯金字塔构造一个DoG金字塔的的话，DoG的每组的层数是4 ；

           3）对于DoG金字塔，特征点的搜索从每组的二层到倒数第二层的（后面说明为什么），所以如果DoG金字塔有效层数目为n的话，那么DoG金字塔应该有n+2层，那么对  应的高斯金字塔应该有n+3层 ；

           4）高斯金字塔从第二组开始的每组第一层是由上一组的倒数第二层降采样得到的，如下所示。

 

        

 

             讲了这么多概念，现在正式开始讲解如何在尺度空间里寻找特征点啦。

             由于图像进行伸缩等变换后尺度空间发生变化，所以为了方便找出匹配点，需要将图像在不同的尺度空间里进行平滑，并相减得到更多的边缘等高频信息（特征点的集中　域）。高斯平滑并计算dog金字塔利用下面的3个计算公式：

                

 

             至于为什么用DOG算子来提取额特征点，而不是hessian或者其他角点方法比如Harris，是因为Mikolajczyk (2002)发现通过

                           计算出来的局部区域极大值和极小值与上述几种角点相比能产生更加稳定的特征点。

 

             但是上面的公式和DOG又有素描关系呢？看下面的公式就知道了：

             

             进一步得到=》

             两者之间只是相差了（k-1）δ² 倍而已，不影响特征点的寻找。

             还有一点需要说明的是，这里不同的δ就是代表不同的尺度，0（本身），δ，kδ,等等...   δ的值越大，意味着尺度空间越大。具体该怎么理解尺度这个概念呢，就是需要描述的像素灰度分布越广，尺度越广，也就是说越模糊的图像尺度也越大。举个例子，有两个灰度值分别为0和1，模糊后变为0.4和0.6，要表示这两个灰度值需要更多的参数，尺度变大。更简单的说尺度就是频率，高斯模糊越明显，尺度越大，因为这时图像是低频的。

 

            剩下的只需要在DOG金字塔里寻找3X3X3邻域的极值即为我们所要寻找的feature points.如下图所示，

                             

 

$2.   关键点的精确定位

 

       通过拟和三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，以增强

匹配稳定性、提高抗噪声能力。
     

       ①空间尺度函数泰勒展开式如（4 ）所示:

        

         对（4）求导,并令其为0,得到精确的位置（5)。

        ②在已经检测到的特征点中,要去掉低对比度的特征点和不稳定的边缘响应点。去除低对比度的点：把公式(5)代入公式(4)，可得（6）。

           若（6）的值大于0.03 ，该特征点就保留下来，否则丢弃。
       
        ③边缘响应的去除
          一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率通过一个2×2 的Hessian矩阵H求出:

                                                
            导数由采样点相邻差估计得到。D的主曲率和H的特征值成正比，令α为最大特征值，β为最小的特征值，则

                                            

              令α=rβ   则：

                                             

             (r + 1)²/r的值在两个特征值相等的时候最小，随着r的增大而增大，因此，为了检测主曲率是否在某域值r下，只需检测。

 在Lowe的文章中，取r＝10。

          

$3.   关键点方向分配

        利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。

        梯度大小和方向计算公式如下：

（7）

       orientation histogram的生成，将0~360度分到36个区间中，每个区间的高度计算如下：∑m(x_i,y_i)*g(x₀,y₀,1.5δ)  其中δ为当前的尺度，（x₀,y₀）为当前特征点的坐标而g(x₀,y₀,1.5δ)则是高斯滤波系数，计算公式➹（2）。

       主方向定义为拥有最高峰hm的那个区间，而其他区间高度为0.8*hm之上的区间方向可以认为是该特征点的辅方向，这样就增强了匹配的鲁棒性。

       这样，每个关键点key points就有三个信息：位置（x₀,y₀）、所处尺度δ、方向。

       若表示出来，效果如下：

                   

                                       图1

 

$4.  提取特征描述子

      

                                    图2

 

•           首先将坐标轴旋转为关键点的方向，以确保旋转不变性；
•           为了方便起见，在$3部分利用公式7计算梯度时，应该计算全体像素点的梯度方向及大小；
•           lowe建议选取16X16邻域，然后将这个大区域分为16个4X4区域，再分别对每个区域中16个像素点的梯度大小乘上高斯模板系数（此时的δ为0.5*4=2）；
•           将16个单位方向向量按照常规的8方向分布，并乘上上一步计算的幅值叠加起来，得到类似图2右边的效果。

 最后，一共有4X4X8=128维向量来表征这个特征点。

此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。

 

$5.  后续匹配工作

           当两幅图像的SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找

出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，

SIFT匹配点数目会减少，但更加稳定。为了排除因为图像遮挡和背景混乱而产生的无匹配关系的关键点。Lowe提出了比较最近邻距离与次近邻距离的方法,距离比率

ratio小于某个阈值的认为是正确匹配。因为对于错误匹配,由于特征空间的高维性,相似的距离可能有大量其他的错误匹配,从而它的ratio值比较高。Lowe推荐ratio的

阈值为0.8。但作者对大量任意存在尺度、旋转和亮度变化的两幅图片进行匹配，结果表明ratio取值在0. 4~0. 6之间最佳，小于0. 4的很少有匹配点，大于0. 6的则

存在大量错误匹配点。作者建议ratio的取值原则如下:

             ratio=0. 4　对于准确度要求高的匹配；

             ratio=0. 6　对于匹配点数目要求比较多的匹配； 

             ratio=0. 5　一般情况下。

 

也可按如下原则:当最近邻距离<200时ratio=0. 6，反之ratio=0. 4。ratio的取值策略能排分错误匹配点。                  

 

 

至此，整个sift算法完毕。

 

转载请注明：blue_lg 博客园 http://www.cnblogs.com/blue-lg/archive/2012/07/17/2594868.html

       

本文链接

 

 

Things you can do from here:

• Subscribe to 博客园_首页 using Google Reader
• Get started using Google Reader to easily keep up with all your favorite sites