SIFT特征点提取与匹配算法

1、二特征点提取算法1、基于 SIFT (Scale Invariant Feature Transform )方法的图像特征匹配参看 David G. Lowe 的 "Distinctive Image Features from Scale-Invariant Keypoints ”基于SIFT方法的图像特征匹配可分为特征提取和特征匹配两个部分，可细化分为五个部分： 尺度空间极值检测(Scale-space extrema detection)； 精确关键点定位(Keypoint localization ) 关键点主方向分酉己(Orientation assignment) 关键点

2、描述子生成 ( Keypoint descriptor generation ) 比较描述子间欧氏距离进行匹配( Comparing the Euclidean distance of the descriptors for matching)1.1尺度空间极值检测特征关键点的性质之一就是对于尺度的变化保持不变性。因此我们所要寻找的特征点必须具备的性质之一，就是在不同尺度下都能被检测出来。要达到这个目的，我们可以在尺度空间内寻找某种稳定不变的特性。Koenderink和Lindeberg已经证明，变换到尺度空间唯一的核函数是高斯函数。因此一个图像的尺度空间定义为： L(x, y,。)，是由可变

3、尺度的高斯函数G(x, y,。)与输入图像I(x, y)卷积得到，即:(1.1)L(x, y,；)=G(x, y," I(x, y)其中:G(x, y,。)二1 p 4x2 寸)/疽 ke差分高斯尺度空间在实际应用中，为了能计算的相对高效，所真正使用的是(difference of Gaussian ) D(x, y,o)。其定义如下：D(x,y,。)=(G(x,y,k；)-G(x,y,二)I (x, y)(1.2)= L(x, y,k。)-L(x, y,。)如上式，D即是由两个相邻的尺度的差(两个相邻的尺度在尺度上相差一个相乘系数k)。工名;野;Difference ofGauss

4、ianGaussian (DOG)图1.1图1.1所展示的是建立 DOG的一种实用的方法。初始图像与不同b值的高斯函数卷积，得到一垛模糊后的图像，然后将这一垛模糊图像临近两两相减即得所对应的DOG。这些模糊后的图像以k为系数在尺度空间里被分隔开，并且该垛内最高的尺度应是最低尺度的2倍。为了能开展后续工作（与尺度空间极值检测相关，将在后续文章中作出解释）并满足上述要求，每垛需要通过卷积得到 s+3个模糊后的图像，并且 s和k需要具有关系k = 21/s。在一垛图像建立完毕后，还需要降采样得到下一垛图像的DOG。在实际操作中首先用2倍于第一垛图像的b值建立出模糊图像，然后再将此垛图像降二采样，即每

5、2个像素抽出一个像素，就可以得到下一垛图像的DOG。在上述工作完成后，所要完成的就是尺度空间的极值检测。DOG上的某个像素要和本尺度的8个相邻像素以及上下相邻尺度各9个相邻像素比较。这样做的目的是为了确保图像在尺度空间和二维图像空间均检测到极值点。如果该像素点在这所有参与比较的点中有最大值或者最小值，则认为该像素点是尺度空间的极值点之一。图1.2表示这种极值检测的原理。图1.2另外需要注意的是，上述的尺度空间极值点检测在每一个垛中都要进行。最后获得的极值点总和是所有垛中所检测到的极值点的集合。那么如果这个极值点处在降采样后的垛中，则需要在找出他后将其坐标变换到原始大小的原图上。容易写出这个变换

6、公式为：乂=20如。迁。伽 +0,.O1,、肴0,.&1冬0,.M。1(1.3)其中A是原始大小图像即原始图像上的坐标，经采样变换后变为X;。是处于垛的阶数(即处于第几个垛中)；0mm= 0或者-1,当第一垛图像为原图经过尺寸加倍后的图像生成时值为1,不经过加倍则为 0。另外在建立尺度空间的过程中有两个较为重要的参数要确定。可以将之描述为尺度空间抽样频率和空间域抽样频率。尺度空间抽样频率表现为每个DOG垛所含有的DOG数目。由于每个DOG垛中最大尺度已经确定是最小尺度的2倍，则在这个范围内的 DOG数目越多，抽样频率就越高。这个频率影响着特征提取的效果。Lowe教授在其文章中论述了对于

7、该参数所做的实验。Irogsc4020LcMuqteKrpdrpll-50034567Number :f sea ms samp H per octave1图1.3实验表明在每个垛中有3个抽样时特征点提取效果是最好的（从图 1.3左图可以看出,无论是变化过的图像中能取到与原图中相同的特征点的比例，还是所取到的特征点与数据库内特征点匹配上的比例都是最高）。而之所以更高的抽样频率不能带来更好的匹配效果，是 因为抽样频率越高， 虽然提取的特征点越多， 但这样的特征点大多是不稳定的，因此无法提高匹配的成功率，这从图 1.3右图可以看出。另外一个参数是空间域抽样频率。表现为b的数值。由于图像与高斯函数的

8、卷积可以看作是空间滤波，则 b与滤波的截止频率有很大的关系。b越大，截止频率就越小，能够看到的抽样值频率也越小。100801i->1niiiii1Matching location 】 Nearest descriptor in1ind scalle database<L_ii1F1.21.4161.62Prior smoothing for each octave (sigma)图1.4Lowe教授在文章中也对 b的取值做了相关实验，实验结果表明当b取1.6时所得到的匹配效果最好，这从图 1.4中可以看出（同样的，在变化过的图像中能取到与原图中相同的O另外他还特征点的比例，还是所

9、取到的特征点与数据库内特征点匹配上的比例都是最高）证明，在建立尺度空间的第一垛图像时，先将原始图像的尺寸加倍，则可以使稳定的特征点的数目达到原来的 4倍。1.2精确关键点定位极值点确定之后，必须进行有效的后续工作对这些点进行筛选；因为此时往往会有可观数量的极值点具有很低的对比度或者处于不理想的边缘。我们把这些极值点成为备选关键点，而后续工作的目的就是去掉那些对比度低的以及处于不理想边缘处的备选关键点（keypoint candidate ），以得到最终参与匹配的特征关键点（ keypoint）。1.2.1更精确的关键点位置描述早期的关键点定位方法比较粗糙。目前所采用较多的方法是由Brown教授

10、所提出的三维二次曲线（3D quadratic function ）展开。该方法将 DOG在所关注的像素点处用三维泰勒级数展开（展开到 2次方项），然后再精确定位极值的位置至亚像素级。展开式如下：D(x)二旦x 1xT气,.x 22 x:x2(1.4)-f£2DcPc2D1dxc 2八一一dxcxycx§,、T cDcD82D2 _2 _2 _d D & D d D其中：X =(x,y,cr),=-_ 2_cX为以2cyxcy阴cD82D cD32DM 11一一一 2衣 xcyc<y：2x,y x,yx,y x,y当 = （Dz Dk 二（1心5 ） ,（ k

11、指当前k层，k-1指k的下层，k+1指上一层）-2x 1,yx J,yx 1,y x4,y:-D （Dk 1 - Dk 1 ） -（Dj -Dk】）：'x； 了4可以看到，所有的偏导数值都由像素值的差分来近似；后面会涉及到的Hessian算子中的相关计算也是由像素值的差分来近似的。按照泰勒级数的定义，其中 D和D的偏导数都是在展开点所计算的值，而x是估计点到展开点的偏移量，即：x = （x-x0, y-y0,；）其中被减值是估计点的坐标，减数为展开点的坐标。那么要求得D的极值，则自然想到对这样展开后的D对x求导，然后使导数为 0,即求得了局部的极值。在这种理念下，则极值点对于展开点的偏

12、移量(1.5)?=-(空广Dx则容易由此得到极值点的坐标。容易想到，如果三维向量X在任何一个维度的值大于0.5,那么这个极值点会更接近另外一个像素点,而不是本身的这个展开点。那么此时就将展开点换做更接近的那个点，然后再次展开计算偏移量O最后偏移量的值被加到展开点上以得到关键点的最终位置。 当然这个最终位置的坐标不一定是整数，所以这个关键点的位置是种修正过的，或说插值过(interpolated )的估计值。需要注意的是，SIFT特征匹配最终也不需要有一个整数的坐标值。在生成了关键点描述子之后，在匹配时与具体的坐标就不相关 了。1.2.2去除对比度低的不稳定关键点在精确定位了特征关键点之后，该特

13、征关键点的DOG函数可以由其临近的像素点的DOG展开获得，即式(1.1)。研究表明，特征关键点的DOG函数值D(X)可以用来去除那些因为对比度偏低而不稳定的关键点。其值越低，则越不稳定越应该忽略。在实际操作中,用来求D(X)的函数并不是(1.1),而是在此基础上继续忽略2阶项后所得:(1.6)< 0.03的点全部去除。在Lowe教授的研究中，这个阈值为0.03,亦即所有 D(01.2.3去除由边缘响应所带来的不稳定关键点为了增强特征点的稳定性，仅仅去除低对比的点是不够的。DOG函数有着较强的边缘响应，如果关键点被定位在边缘，那么这个关键点很有可能是不稳定的,尤其容易受到噪声的影响，即是是

14、少量的噪声也会影响匹配的稳定性。一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率,而在垂直边缘的方向有较小的主曲率。那么我们只需要求出关键点主曲率便可以决定是否因其处于边缘而舍去他。主曲率可以通过2 x 2的Hessian矩阵H来计算，其中:_ Dxx DxyH 一 _Dxy Dyy该点的两个主曲率是与Hessian矩阵的两个特征值成比例的。而在实际应用中并不用计算出r便可以确定H的特征值，因为我们可以只考虑他们中较大的特征值比较小的特征值的比例该点是不是处于边缘 (因为在横跨边缘的地方有较大的主曲率，对应一个大特征值； 而在垂直边缘的方向有较小的主曲率，对应一个较小特征值， 比

15、例只要足够大， 就可以认为该点满足处于边缘的性质)。设a为较大的特征值，3为较小的特征值，则c(=rE。由于(1.7)(1.8 )(1.9 )Tr(H) = Dxx Dyy =：:Det(H) = DxxDyy (Dxy)2 = "：我们构建ratio=lK = (_) = 5Det( H)： ：r则如果我们考虑r > r0时则认为该点处于边缘， 那在具体判定时，我们可以不用计算2(ro 1)“ 人-出其具体特征值，而是只用等效判断是否有rati。>即可。计算一个二阶矩阵ro的迹以及其行列式，要比计算其特征值的代价小得多，只用进行20次不到的浮点操作即可。一般情况下，阈值

16、 r0取为10。1.3关键点主方向分配给一个关键点分配主方向，并将主方向纳入关键点的描述子特性之中，那么这个关键点就具有了旋转不变性。描述主方向需要用到像素点的梯度。梯度的模和方向如下以像素差分的方法定义和计算:m( x, y) = J(L(x+1,y) L(x1,y)2 +(L(x, y + 1) L(x, y 1)2( 110)1e(x,y) =tan (L(x, y+1) - L(x, y 1)/(L(x + 1, y) L(x 1,y) (1.11)关键点的主方向是通过统计以关键点为中心的一个邻域之内所有点梯度方向来确定。在实际计算中，这种统计通过梯度方向直方图来确定。梯度直方图将36

17、0分为36个柱, 每个柱为10°。其中出现的梯度方向峰值就是这个关键点的主方向。在邻域内的点的方向被纳入直方图时，还要经过一次高斯加权；这个加权的高斯函数是以关键点为中心，1.5 b为标准差的，其中 b就是这个关键点所在的尺度。若当梯度直方图中存在的次高峰，其模值大于等于最高峰的80%,那么就将该次高峰对应的方向定为该点的辅方向。 如果一个特征点有辅方向， 那么就建立另外一个新的特征点，这个特征点和原特征点有着同样的坐标， 但是方向不同。也就是说这样会出现一些坐标相同 但是主方向不同的特征点。实验表明，虽然只有15%的特征点存在辅方向，但是给具有辅方向的关键点生成新关键点，能极大的提

18、高匹配的稳定性。最后，如果还想进一步提高峰值位置的精度，可以用最接近峰值的3个直方图值做抛物线拟合，将拟合出的抛物线最大值的位置作为精确的峰值位置，亦即精确的主方向角度。 1.4关键点描述子生成前面的工作我们已经指定了 特征关键点的位置、尺度和方向，这样特征点就已经对于这些参数的变化保持了不变性。下一步就是要生成一种能描述这样特征的描述子，并尽可能让这种描述子对于其他一些变化也有一定的不变性，如光照和三维视角变化。在建立描述子时，要将描述子的主方向坐标旋转到关键点的主方向上来，这样才能保证具有旋转不变性。之后选择以关键点为中心的16X 16区域（图1.5）,计算出其中每一点的梯度值；然后将这个

19、区域所有的梯度值用一个中心在该区域中央的高斯函数加权（高斯函数的标准差为1.5倍的区域宽度）。接下来将整个区域分为 16个4 X 4的小区域（图1.5中红 色区域），在这个小区域中统计梯度直方图，直方图分为8个方向；那么整个描述子所覆盖的区域含有的信息就是16X 8=128个，则整个描述子可以看做是一个128维的向量，即特征向量。生成描述子的过程可以由图1.6表示。最后将特征向量归一化，则可以去掉光照变化产生的影响。如果光照变化是对比度变化，则相当于是对每个点的梯度乘上了一个常数，那么标准化后这个常数就被消除了；如果光照变化是亮度的变化， 那么相对于对每个点的像素值加上了一个常数，对梯度的变化

20、没有任何影响。但是由于一些非线性的光照变化会使某些像素的梯度模值产生较大变化，同时对梯度方向没有影响，因此我们在统计梯度直方图时将所有大于某个阈值的梯度模值都置为这 个阈值，就可以降低光照变化的影响。要注意的是，向量归一化是在所有模值经过阈值的限制之后进行的。因为这样的操作相当于降低了大模值点的模值在匹配中的权重。这个阈值一般选为0.2。图1 .6至此SIFT特征全部集中在 SIFT向量，亦即特征描述子之上。作为图像的局部特征一种表征，他决定了基于特征的各种后续处理方法的效果。1.5比较描述子间欧氏距离进行匹配在描述子生成完毕之后，特征提取阶段即告结束。完成图像匹配，接下来要做的是对这些特征运用适当的比较方法来找到对应关系。由于特征点描述子可以看做为128维的向量，则可以通过向量的相关概念来抽象出比较描述子的方法。最直观的便是两个向量间的欧氏距离，我们可以容易的想出，两个相同的向量其欧式距离为0,那么两个完全相同的特征点描述子，其欧氏距离也为 0。不过很显然，由于噪声以及其他图像变换的存在，同一个点对应在不同图像上的特征描述子不可能完全相同，那么如何确定两个描述子匹配呢?首先应该想到，描述子距离越近，越应该认为其匹配。但是为了达到稳健的匹配，仅仅有“最近”是不够的