《特征点检测算法.docx》由会员分享，可在线阅读，更多相关《特征点检测算法.docx（11页珍藏版）》请在金锄头文库上搜索。
1、特征点检测算法一、SIFT(Scale Invariant Feature Transform)算法基本原理及主要特征1、SIFT算法基本原理SIFT算子是图像匹配算法中性能较好的算子，基于SIFT算法的特征图像配准可大致分为特征的检测、描述和匹配。特征检测是在尺度空间中进行的，首先生成图像尺度空间，然后检测尺度空间中的局部极值点，再通过剔除低对比度点和边缘响应点对局部极值点进行精确定位；在对特征进行描述时，先计算每个极值点的主方向，对极值点为中心的区域进行直方图梯度方向统计，生成特征描述子；最后，通过特征描述子寻找匹配的特征，建立图像之间的联系。1.1关键点的检测高斯卷积核是实现尺度变换的唯
2、一线性变换核，一幅图像在尺度空间中可表示为图像和可变高斯核函数的卷积，采用高斯金字塔（LaplacianofGaussian，LoG）算子表示如下：其中，I(x,y)为输入的二维图像，为可变高斯核函数，为可变核。图像尺度空间的形成是通过将图像与具有可变核的高斯滤波器进行卷积，从而得到图像的高斯金字塔LoG。David指出，高斯金字塔LoG共分为O组，每组S+3层，S为与之间的层数，S一般取2或3。每组的高斯金字塔的形成是通过输入图像与级联滤波器进行卷积得到，下面以S=2为例，对高斯金字塔LoG的形成过程进行详细说明。当S=2时，每组的高斯金字塔共有5层，共由四级的级联滤波器得到。对于第一组的高
3、斯金字塔LoG形成过程如下图所示：图1-1 级联滤波器的构造如图所示，输入图像由初始图像I经高斯核为的滤波器得到，输出图像（i=1,4）由输入图像分别经级联滤波器、和得到。第一组高斯金字塔LoG为图1中虚线包括的五幅图像，每幅图像对应的高斯核为,表示图像可看成初始图像I经核为的高斯函数得到。第二组高斯金字塔LoG的每层图像大小都是第一组高斯金字塔LoG中图像大小的1/4，其输入图像是第一组高斯金字塔LoG中第S层图像经采样率为2的采样过程得到。当S取2时，第二组高斯金字塔LoG的输入图像为上面提到的图像采样得到的。输入图像再经过四级的级联滤波器得到输出图像,级联滤波器的结构与第一组高斯金字塔L
4、oG一致，图像构成了第二组高斯金字塔LoG。依此类推，共生成O=4组的高斯金字塔LoG。为了有效的在尺度空间检测到稳定的关键，Lowe构造了差分金字塔DoG（DifferenceofGaussian），它是通过对相邻层的卷积结果进行差值处理获得的，其表达式如下：图1-2给出了第一组、第二组高斯金字塔LoG和差分金字塔DoG的构造过程。图1-2 高斯金字塔LoG和差分金字塔DoG的构造过程如图所示，差分金字塔DoG是由高斯金字塔LoG相邻层相减得到的。其中，高斯金字塔LoG共有O组，每组共有S+3层图像；差分金字塔DoG共有O组，每组共有S+2层图像。每个像素点与周围8个像素点以及相邻尺度的29
5、个共26个像素点比较大小，若为极大值点或为极小值点，则该像素点是候选极值点，候选极值点在每组的中间S层中产生。当S=2时，候选极值点在差分金字塔DoG的中间2层产生，如图中红色方框所示。1.2极值点的筛选经过差分金字塔DoG 中的极值检测之后，需要对候选的极值点进行筛选，得到真正的极值点。极值点的筛选包括两部分，一个是低对比度点的抑制，另一个是边缘响应点的去除。低对比度点的抑制是指剔除响应值小于给定阈值的点，边缘响应点的去除是指将候选点中的大曲率的边缘点筛选掉。 由于差分金字塔DoG检测到的极值点的位置坐标均为整数，而实际的特征点不一定位于整数坐标位置上。因此，在进行极值点筛选之前，先要通过三
6、维二次函数对特征点的位置进行精确定位，再通过计算该位置的DoG响应值及曲率来筛选得到真正的极值点。差分金字塔DoG在候选极值点周围的泰勒展开式如下：其中，X=(x,y,)为特征点的位置和尺度信息的向量，X0为候选特征点的位置和尺度信息的向量，D(X0)为该点的差分金字塔DoG值。对上式两边关于(X-X0)求导并令一阶导数为零，则有：计算差分金字塔DoG在候选极值点处的一阶和二阶偏导数，通过上式来估计特征点与候选极值点之间的关系。当X的x或y模值超过0.5时，表明真正的特征点是偏向于周围的另外一点，此时需要对候选极值点的位置进行调整，并重新估计，直到X的x或y模值均在0.5以内为止。对特征点位置
7、进行精确定位后，将X代入上述泰勒展开，则有当 |DX|0.3时，候选极值点将作为低对比度点去除。位于图像边缘处假的特征点在边缘交叉处的主曲率较大，而在垂直方向上主曲率较小，因此可以利用这个性质除去假的特征点。Hessian 矩阵与主曲率存在比例关系，二维 Hessian 矩阵的定义如下：主曲率大小的判别不需要计算Hessian矩阵的特征值，通过矩阵的迹和行列式值的比值就可以判别。设矩阵H的特征值为和，且满足，为比例系数，矩阵H的迹和行列式值计算如下：将特征值的关系带入到矩阵的迹和行列式的比值中得到：以上比值随的增大而增大，故应将该比值设定在一定的范围内，Lowe文章中取。1.3 方向描述子的生
8、成利用关键点邻域像素的梯度分布特性来计算关键点主方向。点坐标为(x，y)处的梯度幅值和方向分别为：在以特征点为中心的邻域窗口内，采用梯度方向直方图表示其邻域像素的梯度方向统计值。梯度方向范围为0360，其中每10在直方图中表示一个柱，共有36柱。梯度方向直方图的峰值代表了该特征点处邻域梯度的主方向，即作为该特征点的主方向。当梯度方向直方图中存在主峰值能量80%的以上的峰值时，该峰值所对应的方向作为辅方向。特征点可以有一个主方向和多个辅方向，这样可以提高特征匹配的稳定性，Lowe指出这些特征点所占的比重约15%左右。特征点方向分配之后，接着生成特征描述子。以特征点为中心取1616的窗口（特征点所
9、在的行和列不取），每个小格代表特征点邻域所在尺度空间的一个像素，采用高斯加权（越靠近特征点的像素，梯度方向信息贡献越大）。在44的图像小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，形成一个种子点。一个特征点由44共16个种子点组成，特征描述子由所有子块的梯度方向直方图构成。因此，最终形成128维的SIFT特征向量就是特征描述符。图1-3给出了特征描述子的生成过程，左图绿色的方型线框大小为88。每个小格代表一个像素点，小格内的带箭头的直线表示像素点的梯度，直线的长度代表梯度的幅值大小，箭头指向代表梯度方向。蓝色圆型线框为进行加权的高斯核函数结构，越靠近特征点权值越大。右图为对每个
10、44的子块统计形成种子点的结果，88的方型线框共产生4个种子点。图1-3 SIFT特征描述子的生成为减少光照变化的影响，应对特征描述子进行必要的修正。光照变化可以分为线性光照变化和非线性光照变化，对特征描述子进行修正可以减少光照变化的影响。对于线性光照变化，相当于对像素点的灰度值进行了乘性和加性的常数，加性常数通过差分后将消失，乘性常数可以通过对特征描述子进行归一化消除；对于非线性光照变化，会影响梯度的幅度而对梯度的方向影响小，因此考虑先对梯度的幅度进行限幅（阈值常取 0.2），再对限幅后的特征描述子进行归一化。通过实验验证，修正后的特征描述子具有很好的光照不变性。1.4特征描述子的匹配特征描
11、述子之间的匹配是通过最近邻（Nearest Neighbor，NN）来定义的，最近邻是指特征描述子之间的欧氏距离最小。一幅图像中的特征点可能在另一幅图像中找不到匹配点，为此需要通过设置阈值来去除这些特征点。由于有些描述子比其它描述子的区分度更高，因此采用最近邻欧氏距离全局阈值并不能获得很好的效果。一个更为有效的方法是通过比较最近邻欧氏距离与次近邻欧氏距离的比值，因为对于一个可靠的匹配来说，正确匹配的最近邻特征肯定比不正确的最近邻特征要近的多。次近邻匹配可以看成在特征空间中对误匹配密度的估计，同时可以作为特征模糊的特例。通过设置欧氏距离比阈值可以去除一些错误的匹配点，但同时一些正确的匹配也有可能
12、会被剔除。David 将该阈值设置为 0.8，这样在损失 5%的正确匹配点同时将减少 90%的错误匹配点值展。特征点建立匹配关系之后，下一步就是求解图像之间的变换关系。仿射变换能够很好的表达图像之间的一般变换，并且最少只需要 3 对匹配点就可以求解。2、SIFT算法主要特征(1) SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。(2) 独特性好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配。(3) 多量性，即使少数的几个物体也可以产生大量SIFT特征向量。(4) 高速性，经优化的SIFT匹配算法甚至可以达到实时
13、的要求。(5) 可扩展性，可以很方便的与其他形式的特征向量进行联合。二、SURF(Speeded Up Robust Features )算法的基本原理及其改进1、SURF算法基本原理基于SURF特征检测算法是由Bay等人提出了。这个算法与SIFT算法的思想非常类似，都是首先检测极值点，后确定特征点的方向，最后生成特征点。与SIFT算法采不同的是该算法是通过Hessian矩阵来检测极值点，这样不仅仅拥很好的鲁棒性，而且大大提高了检测特征点的速度。该算法使用了积分图像的方法。积分图像计算的是某一个矩形区域内的像素和，通过积分图像能快速实现方框状卷积滤波(box type convolution
14、filters)的功能。对于积分图像I中的点(x,y)，如下式所示：利用上式，图2-1中任意矩形区域的面积可由散布加减操作得到：图2-1 快速积分得到图像面积这种方法主要是利用改变图像大小却并不影响计算时间的特性，在对尺度很大的图像进行处理时占有很大优势。1.1 检测尺度空间极值SURF算法检测特征极值点同样是通过尺度空间技术实现的，主要步骤有以下几个方面：(1) 尺度空间金字塔的生成SURF算法是利用盒子滤波(box filter)的方法来建立多尺度空间，不断将其与原始图像进行卷积操作，这个过程类似于SIFT算法利用二阶高斯函数创立多尺度空间的过程。但是两者之间的根本区别在于使用积分图像的技
15、巧。图2-2是比较了盒子滤波与二阶高斯滤波。图2-2 二阶高斯滤波与盒子滤波的对比其中，盒子滤波是加过权重的。在x、y方向上的滤波，对于黑色区域赋权-2，白色区域赋权值1，其余区域没有赋权值；在方向上，黑色部分赋权值-1，白色部分赋权值1。SURF特征提取算法更为快速的主要原因是利用盒子滤波加速卷积的运算。由于SURF算法不需要对图像在迭代的情况下进行采样，盒子滤波的结构是一块一块的，每块连续区域内都有相同的权值，然后把原始图像与各种大小不同的滤波在不同方向上进行卷积操作，从而产生了多尺度的空间函数Dxx，Dyy，Dxy。此外,由于积分图像大小与计算量无关。所以，建立多尺度空间时，SURF特征检测比SIFT特征检测速度得到了大幅提高。由99的盒子滤波计算出尺度空间金字塔的最底层，对应的是尺度s=1.2的初始尺度层，相当于=1.2的高斯二阶偏导滤波。假设最底层为第一层，在第一尺度空间中有4层尺度图像，第一个盒子滤波是99的大小，每一组中的盒子滤波都是成等差数列的，公差为62n-1个像素递增，其中n为层数。如图2-3所示。图2-3 尺度空间金字塔的构造(2) 确定候选极值点建立好尺度空间金字塔后，就是为了求得某一特定尺度下的局部极值。在SURF特征检测算法中，采用了一个非常逼近det(H)的近似表达(H)，使计算量更加的
