图像特征点检测算法之——SURF算法(与SIFT算法的性能)

时间:2024-04-03 19:14:17

图像特征点提取算法的算法研究(SURF和SIFT算法)

1. 摘要

    计算机视觉中,很大一部分研究集中在图像特征提取和特征生成算法上。对图像的优化,不同于一般数学问题的优化方法,图像的优化是对像素点,在某一个小的邻域内,进行特征的提取或者图像的分析,该优化主要是进行局部区域的优化,要寻找局部极值,而不像传统的优化算法那样进行全局的优化求解。

由于相同物体在不同状态下所产生的图像不同,使得不同图像具有不同亮度,不同旋转方向和不同尺度的差异。想要提取出具有代表性且性质鲁棒的特征点,一直是学术研究的焦点之一。为了引入尺度不变的特征,将检测到的每个特征点都计算其对应的尺寸因子,方便特征点匹配和图像拼接等后续图像应用,Bay于2006年提出了SURF(Speeded Up Robust Features)特征检测算法。该算法具有较好的尺度不变性和旋转不变性,并且具有快速的计算能力,一直是图像拼接、图像检测和恢复等应用采用的主流算法之一。

本文主要叙述SURF特征点提取的优化步骤,将其与SIFT特征点提取算法,进行分析和比较,最后给出了关于图像亮度,图像的旋转和图像的尺度等三个方面的性能比较,验证了SURF特征点检测算法优化性能。

SIFT(Scale invariant feature Transform)算法是由David Lowe提出的尺度不变特征转换算法,其目标是解决低层次特征提取及其图像匹配中的实际问题。该算法是一种基于尺度空间,对图像缩放变换保持不变性的图像局部特征描述子。其主要分为三部分进行图像的特征点提取和描述。

SIFT算法的优点是特征稳定,对旋转、尺度变换、亮度保持不变性,对视角变换、噪声也有一定程度的稳定性;缺点是实时性不高,并且对于边缘光滑目标的特征点提取能力较弱,不够优化。因此,更加鲁棒的快速特征提取算法SURF应运而生,由于SURF运算简单,效率高,特征计算时间短,到今天都还受欢迎。

SURF算法是对SIFT算法的加强版本,同时能够加速提取更加鲁棒的特征,是SIFT算子的速度的三倍以上,并且提取出的特征点更有代表性。同时也对描述子的生成以及特征点的匹配进行了优化。其主要采用了Harr特征以及积分图像,加快了程序搜索和运行的时间,优化了特征点提取的理论算法。


2. 优化过程

SURF算法的特征点检测优化过程如下:

2.1 构建积分图像,在图像每个像素点上,生成积分图像。

     其中,在一个特征点x=(x,y)的邻域上,计算其积分图像I(x,y):

图像特征点检测算法之——SURF算法(与SIFT算法的性能)


在图像上,积分图像的意义如下图1所示。


                  图像特征点检测算法之——SURF算法(与SIFT算法的性能)

2.2 对当前的积分图像I,构建Hessian矩阵,进行逼近,提取特征点。

构建Hessian矩阵的目的是为了生成图像稳定的边缘点,描述图像的局部变化。给定点积分图像中一点,则关于X点在尺度因子 下的Hessian矩阵定义为:

图像特征点检测算法之——SURF算法(与SIFT算法的性能)

其中,Lxx(x,sigma)表示在积分图像I的点X处的高斯二阶微分的卷积,同理,Lxy(x,sigma)表示对图像的卷积。

当Hessian矩阵的判别式取得局部极大值时,判定当前点是比周围邻域内其他点更亮或更暗的点,由此来定位关键点的位置。在离散数字图像中,x方向的一阶导数是相邻像素的灰度差:

                                    图像特征点检测算法之——SURF算法(与SIFT算法的性能)

x方向的二阶导数为:

          图像特征点检测算法之——SURF算法(与SIFT算法的性能)

由于在连续函数中,可以通过判断Hessian矩阵的特征值的符号来判断当前点是否为极值点,Hessian矩阵的判别式为:

                                 图像特征点检测算法之——SURF算法(与SIFT算法的性能)

在图像的处理中,由于要特征点的尺度不变性,就需要利用高斯滤波,让特征点与尺度无关,随后在进行Hessian 矩阵的构造。高斯滤波公式如下:

                             图像特征点检测算法之——SURF算法(与SIFT算法的性能)

为了加速处理,采用Box滤波器对高斯二阶微分模板进行近似处理。

图像特征点检测算法之——SURF算法(与SIFT算法的性能)

图2:从左到右依次为y方向的二阶高斯微分模板;xy方向的二阶高斯微分模板;

对y方向近似的Box滤波器;对xy方向进行的Box滤波器。

通过近似后,我们可以得到图像的Hessian矩阵判别式:

                              图像特征点检测算法之——SURF算法(与SIFT算法的性能)

为了平衡使用Box滤波器带来的近似误差,我们在Dxy方向上乘以一个加权系数来抵消误差。因为我们使用的是9*9的高斯模板,标准差为1.2。所以有:

                     图像特征点检测算法之——SURF算法(与SIFT算法的性能)

按照上述的误差因子,在构建的矩阵中,通常不会改变,因此在接下来的特征点判断中,不改变w的值。最后有了判别式:

                           图像特征点检测算法之——SURF算法(与SIFT算法的性能)

通过计算的det(Happrox)值来得到像素点在尺度的响应图像。

2.3 构造尺度空间

由于SURF需要图像在不同的尺度空间下,具有尺度不变性,因此内部需要对图像进行处理,构建出不同尺度的图像,得到更加鲁棒的特征点。具体方法是:构造尺度空间传统的方法即构造一个高斯金字塔,原始图像作为最底层,然后对图像进行高斯模糊再降采样(2倍)作为下一层图像,循环迭代下去。高斯金字塔是对原图像的尺寸是在不断变化的,高斯模板尺寸不变。每一层的建立必须等到上一层构造完毕后才能进行处理,依赖性很强,这样造成速度上很慢。SURF构建尺度金字塔的方法采用原图像大小不变,变化的是模板大小,即采用变化的模板盒子尺寸对原图像进行滤波,构造出尺度空间。同时,SURF可以采用并行运算,对金字塔中的每层图像同时进行处理。通过逐渐增大的盒子尺寸滤波模板与积分图像卷积产生的Hessian矩阵行列式的响应图像,构造出金字塔。

图像特征点检测算法之——SURF算法(与SIFT算法的性能)

图3:左图为高斯金字塔的构建方法;右图为SURF的尺度空间构建方法。

2.4 非极大值抑制

对每层图像上的每个像素与空间邻域内和尺度邻域内的响应值比较,同层上有8个邻域像元,向量尺度空间共有2×9=18个,共计26个像元的值进行比较,如果是极大值则保留下来,作为候选特征点。同时如果特征点的响应值小于Hessian行列式的阈值,也被排除。

2.5 特征点定位于提取

由于是离散空间的极值点,通过拟合方法,准确定位到特征点的位置,每个特征点包含三个参数H(x,y,sigma),即位置与尺度。

                          图像特征点检测算法之——SURF算法(与SIFT算法的性能)

对x求导,并令其为0,可以得到:

                                         图像特征点检测算法之——SURF算法(与SIFT算法的性能)

其中,两个因子的计算式为:

           ,            图像特征点检测算法之——SURF算法(与SIFT算法的性能)

求得的x_hat=(x,y,sigma),即获得在三个方向的偏移量,其中sigma表示特征点所在的尺度空间。

2.6 选取特征点主方向确定

为了保证旋转不变性,在SURF中,不统计其梯度直方图,而是统计特征点领域内的Harr小波特征。即以特征点为中心,计算半径为6s(s为特征点所在的尺度值)的邻域内,统计60°扇形内所有点在x(水平)和y(垂直)方向的Haar小波响应总和(Haar小波边长取4s),并给这些响应值赋高斯权重系数,使得靠近特征点的响应贡献大,而远离特征点的响应贡献小,然后60°范围内的响应相加以形成新的矢量,遍历整个圆形区域,选择最长矢量的方向为该特征点的主方向。这样,通过特征点逐个进行计算,得到每一个特征点的主方向。该过程的示意图如下:

图像特征点检测算法之——SURF算法(与SIFT算法的性能)

图4:对选取的特征点选取主方向,最右边的图为最终主方向。

2.7 生成特征点描述子

在SIFT中,是取特征点周围4×4个区域块,统计每小块内8个梯度方向,用着4×4×8=128维向量作为SIFT特征的描述子。

SURF算法中,也是在特征点周围取一个4×4的矩形区域块,但是所取得矩形区域方向是沿着特征点的主方向。每个子区域统计25个像素的水平方向和垂直方向的Haar小波特征,这里的水平和垂直方向都是相对主方向而言的。该Haar小波特征为水平方向值之和、垂直方向值之和、水平方向绝对值之和以及垂直方向绝对值之和4个方向。该过程示意图如下:

图像特征点检测算法之——SURF算法(与SIFT算法的性能)

图5:特征点描述子的生成示意图。

把这4个值作为每个子块区域的特征向量,所以一共有4×4×4=64维向量作为SURF特征的描述子,比SIFT特征的描述子减少了2倍。

2.8 特征点匹配

与SIFT特征点匹配类似,SURF也是通过计算两个特征点间的欧式距离来确定匹配度,欧氏距离越短,代表两个特征点的匹配度越好。不同的是SURF还加入了Hessian矩阵迹的判断,如果两个特征点的矩阵迹正负号相同,代表这两个特征具有相同方向上的对比度变化,如果不同,说明这两个特征点的对比度变化方向是相反的,即使欧氏距离为0,直接予以排除。

3. 特征点检测算法实现效果比较

通过在Windows 7,64位操作系统,Intel Core i7-4790K 4GHz CPU,8GB运存进行实现。采用红色标出特征点,效果如下:

图像特征点检测算法之——SURF算法(与SIFT算法的性能)

图6 :SURF算法特征点提取效果图

通过选取一副参考图像,再选取另外三种分别具有尺度,旋转和明暗改变的图像,对两种特征点检测算法进行测试。改变其中的参数,对其检测出的特征点个数,检测和匹配时间以及准确程度,进行仿真和评估。

3.1 强度变化下的匹配性能评估

本组图像对相同的物体,选取一张相对参考图像较阴暗的匹配图像。其中主要变量是像素的强度,图像的旋转和尺度保持不变。图像匹配的结果和性能参数比较展示在图7和表1中。

图像特征点检测算法之——SURF算法(与SIFT算法的性能)

图7:图像强度变化的匹配效果图

其中,执行时间指的是特征点检测和匹配时间。从表1的实验结果可以看出,在图像强度变化的情况下, SIFT的匹配率较高,为59.0%。但从执行时间来看, SURF的速度是SIFT的4倍,说明SURF的检测和匹配速度较快。

表1 不同强度下的图像匹配结果

算法

执行时间

图1特点

个数

图2特征点

个数

匹配对数

匹配率(%)

SURF

0.3640s

304

286

153

53.5

SIFT

1.3213s

200

200

118

59.0

 

3.2 尺度变化的匹配性能评估

在本组实验中,对参考图像,选取目标相同但具有尺度变化的匹配图像,进行两种算法的评估。图像匹配的结果和性能参数比较展示在图8和表2中。

图像特征点检测算法之——SURF算法(与SIFT算法的性能)

图8:图像尺度变化的匹配结果

从实验的执行时间可以看出,SURF的速度在尺度变换下,依然比SIFT快4倍左右。虽然SIFT的匹配率为41.0%,在不同尺度下的匹配率最高,但结合实验的效果图,可以看出SIFT存在较多的误匹配。相反,虽然SURF的匹配率为30.0%,但其实际匹配效果较SIFT算法好,特征点匹配的精确度高于SIFT算法。在尺度变化下,SIFT的性能已经开始大降。

表2 不同尺度下的图像匹配结果

算法

执行时间

图1特征点

个数

图2特征点

个数

匹配对数

匹配率(%)

SURF

0.3769s

200

200

60

30.0

SIFT

1.3000s

200

200

82

41.0


3..33 旋转变化的匹配性能评估

本组实验,对目标进行旋转,再进行匹配,可以检测出算法的旋转不变性。图像匹配的结果和性能参数比较展示在图9和表3中,其中目标旋转约为45°。

图像特征点检测算法之——SURF算法(与SIFT算法的性能)

图9:图像尺度变化的匹配效果图

从表3可以看出,SURF算法相对于SIFT算法,匹配率在91.0%,说明对于旋转的目标,该算法具有较强的旋转不变性。而SIFT的匹配率最低,为51.0%。从图9的匹配结果可以看出,SIFT算法的匹配结果较差。不能准确的对旋转后的图像进行特征点匹配,且算法执行时间较长。

表3 不同角度下的图像匹配结果

算法

执行时间

图1特征点

个数

图2特征点

个数

匹配对数

匹配率(%)

SURF

0.1268s

200

200

182

91.0

SIFT

1.3386s

200

200

102

51.0

3.4 结论

通过对图像的特征点提取算法进行优化,引入了Hessian矩阵,在特征点的判断中,计算积分图像的2阶偏导数,组成Hessian矩阵。然后通过Hessian矩阵的行列式大小来进行判断。随后对Hessian矩阵求导,通过相关计算可以获得特征点的位置和尺度,这是优化的核心。

4. 参考文献

[1] H. Bay, T. Tuytelaars, and L.Van Gool. Surf: Speeded up robust features. InEuropean Conference onComputer Vision, May 2006. 1, 2

[2] E. Rosten and T. Drummond.Machine learning for highspeed corner detection. In European Conference onComputer Vision, volume 1, 2006. 1

[3] D. G. Lowe. Distinctive imagefeatures from scale-invarian keypoints. International Journal of ComputerVision, 60(2):91–110, 2004. 1, 2