SIFT算法
SIFT是Scale-invariant feature transfor的首字母缩写,即尺度不变特征变换。在上一篇博客中(特征点检测(一)Harris角点检测),我们知道Harris角点检测不具有尺度不变性,而SIFT算法很好的解决了这一问题。
SIFT算法主要分为五个步骤:获得尺度空间、寻找极值点、去除边界效应、方向赋值和生成特征描述子。
获得尺度空间(尺度不变性)
获得尺度空间即高斯金字塔,是通过使用不同模糊系数的高斯函数卷积图像得到的。公式如下:
L(x,y,σ)是卷积后的图像;
G(x,y,σ)是高斯函数,σ是高斯模糊系数;值越小尺度也就越小;
I(x,y)是原图像。
寻找尺度空间内的极值点
先使用高斯金字塔每相邻两层相减得到高斯差分金字塔。如下图所示:
得到高斯差分金字塔后,中间的检测点和它同尺度的8个相邻点以及上下相邻尺度对应的9×2个点,一共26个点进行比较,从而获得极值点(即最大值或最小值)。因此高斯差分金字塔的最上层和最下层不做检测点。 具体表示如下图:
关键点精确定位
由上一步骤,我们知道,是在离散的情况下获得的极值点,位置信息不够准确。我们可以通过插值法和对高斯函数拟合,找到精确的极值点,即关键点。
去除边缘效应
高斯差分算子对边缘有很强的响应,所以落在边缘的点并不是稳定的特征点,需要去除。
方向赋值(旋转不变性)
以关键点为中心,计算一定范围内图像梯度的幅值和幅角。绘制梯度直方图,以幅角为x轴,没个10度为间隔,y为幅值。其中y值最大的为主方向,将坐标轴旋转到主方向上,关键点具有了旋转不变性。此时,每个关键点具有了位置、尺度、方向三个信息,由此可以确定一个SIFT特征区域。
生成特征描述子(光照不变性)
以关键点为中心选择邻近区域分成 4×4的窗口,计算各个窗口内的梯度,做出梯度方向直方图,以45度为间隔,每个窗口将得到8维描述向量。所以一个关键点将由448=128维的描述子唯一表示。将这些向量进行归一化处理,会去除光照变化的影响。
SIFT是十分稳定的特征提取方法,应用广泛。
优点
<1> 具有尺度、旋转、光照变换具有不变性;对仿射变换以及噪声也具有一定的稳定性;
<2> 即使少量的物体,也能产生很多SIFT特征;
<3> 可以在海量特征数据库中进行快速、准确的匹配;
缺点
<1> 计算量大,实时性不高;
<2> 对于模糊图像和边缘光滑图像,检测的特征点较少;
之后,有很多算法对SIFT进行了改进,例如SURF。SURF算法使用不同大小的盒子滤波器代替高斯函数卷积原图像,得到大小一致的滤波后图片,用来构成图像金字塔,从而减小了计算量,速度更快。