SURF算法与相较于SIFT的优缺点分析(一)

在之前,我们了解过了SIFT算法。另一个与SIFT几乎同样常用的方法是SURF方法。在这篇文章中,我们将简要了解SURF方法,并且通过分析它和SIFT方法的优缺点,来决定我们之后在什么解决方案中使用哪种方法。

什么是SURF方法

SURF,即Speeded Up Robust Features,可以被看作是SIFT方法的一种改进。在一般的平台上,SIFT因为涉及大量重复运算,以及描述子维数很高,所以很难达到实际应用中的实时性要求。SURF则使用各种近似方法,强调速度,高速地完成特征点的提取和匹配。

SURF的主要近似方法

与SIFT相比,SURF方法主要用了各种近似来提高其运算速度。它将高斯函数生成的连续,浮点化的数据,近似为离散,整数的数值,极大地简化了运算。具体的简化方法,将在下文详细说明SURF算法的时候一并解释。

SURF用到的处理方法

因为SURF和SIFT的思路一致,都是先构建某种尺度空间,再提取特征点,然后排除混入的噪声点,最后生成描述子,所以不再一步一步分析图像生成的原理,而是直接进入具体操作环节,关注SURF用到的处理方法。

积分图像

积分图像是SURF算法和SIFT的第一个不同之处,SIFT中使用高斯卷积核对图像进行卷积,虽然利用核函数省去了一些运算,但还是涉及到乘除,这些操作在计算机中比较耗费资源。SURF则利用积分图像,将卷积转化为加减,节约了计算量。

积分图像的获得与特点

积分图像是输入的灰度图像经过一种像素间的累加运算得到种新的图像媒介。对于一幅灰度的图像,积分图像中的任意一点\((x,y)\)的值是指从图像的左上角到这个点的所构成的矩形区域内所有的点的灰度值之和。

那么可以想到,既然SURF使用积分图像进行处理,那么和SIFT一样,它也是基于灰度图像的特征提取算法。在我们的应用中,由其他的方法对彩色信息进行处理和分析,而且通过一个模块就可以简单地将彩色图像转换为灰度。所以,这一局限并不是决定性的。同时,可以想到,积分图像和原图的尺寸是一致的,获得的信息与原图的尺度也是一致的。这一步并没有任何的尺度变换。

积分图像的另一个特点就是,它可以很方便的获取一个区域内的像素的累加值。如图:

要获取小矩形ABCD内的像素累加和,根据简单的几何关系,应该有\(\sum=D-B-C+A\)。

Hessian矩阵

在之前学习SIFT的时候,我们已经接触过Hessian矩阵了(就是那个很难看懂的一堆公式)。SIFT使用它来进行边角曲率检测,来排除边缘响应点。而SURF则完全相反,它的核心就是Hessian矩阵,通过找到稳定的边缘响应点来进行特征提取。

构建Hessian矩阵

Hessian矩阵的构建与SIFT类似,不同的是,现在的矩阵是针对任一像素点构建。公式是:

当Hessian矩阵的判别式取得局部极大值时,判定当前点是比周围邻域内其他点更亮或更暗的点,由此来定位关键点的位置,Hessian矩阵的判别式为:

这一点与SIFT类似。由于我们的特征点需要具备尺度无关性,所以在进行Hessian矩阵构造前,需要对其进行高斯滤波。与我们对SIFT算法的改动不同,因为这次是需要求偏导,所以,使用二维卷积核与使用一维卷积核的骗到会有细微差异,所以这次直接使用二维高斯卷积核。这样,经过滤波后再进行Hessian矩阵的计算:

这一公式与上面的区别是,将I与高斯核卷积之后才送入构建Hessian矩阵。

盒子滤波器

由于高斯核是服从正态分布的,从中心点往外,系数越来越低。这样就导致单独运算每一个像素的系数比较麻烦,所以为了提高运算速度,SURF使用了盒子滤波器来近似替代高斯滤波器。 盒子滤波器(Boxfilter)对图像的滤波转化成计算图像上不同区域间像素和的加减运算问题,只需要简单几次查找积分图就可以完成。每个像素的Hessian矩阵行列式的近似值是:

上面在\(Dxy\)上乘了一个加权系数\(w\),是为了平衡因使用盒子滤波器近似所带来的误差。

盒子滤波器是指,用方盒形状的盒子滤波器近似代替高斯滤波板进行卷积计算。本质上是对高斯二维卷积模板的简化,使得简化后的模板只是由几个矩形区域组成,矩形区域内填充同一值。如下图:

盒子滤波器模板中白色区域的值为正数,黑色区域的值为负数,灰度区域的值为0。可以看到,它就是对高斯滤波模板的一个简化。这样,使用近似的高斯滤波,可以获得上面说的原图的卷积,而又不耗费大量的计算资源。

式中的加权系数\(w\)的计算方法是:

其中,F是指矩阵的F-范数,即各元素平方和的开平方根:

可以看到,其实对于参数不同的Hessian矩阵,这个系数其实是不同的,但是为了简化计算,一般可以取\(w=0.9\)左右的数值。


到了这里,SURF方法的一些基础的内容就简单介绍完了。在下一篇文章中,我们将从构建尺度空间开始,继续比较SURF方法和SIFT方法。