sift 算法介绍:
1999年 British Columbia大学大卫 . 劳伊(David G.Lowe教授总结了现有的基于不变量技 术的特征检测方法, 并正式提出了一种基于尺度空间的、 对图像缩放、 旋转甚至仿射变换保 持不变性的图像局部特征描述算子-SIFT (尺度不变特征变换 , 这种算法在 2004年被加以 完善。
sift 算法的从一幅图像中根据设定的阈值找到一个局部特征向量集, 这些 特征向量具有平移、 缩放、旋转不变性,同时对光照变化、仿射及投影变换也有一定不变性。具有很好的鲁棒 性。 sift 算法具有独特性好、多量性和可扩展性。不过原始的 sift 算子在时间性上的表现不 尽如人意,在后来被改进的 sift 算法在这一点上有所改善。
sift 算法的实质可以归为在不同尺度空间上查找关键点的问题。 sift 算法的实现步骤:
1、检测关键点。所谓关键点,就是在不同尺度空间的图像下检测出的具有方向信息的局部 极值点。具有三个特征:尺度、方向、大小;
要检测关键点,首先对图像进行降采样,生成高斯金字塔,然后生成 DoG 。 而要寻找的关键点就是由 DoG 空间的局部极值点组成。为 了寻找 DoG 函数的极值点,每 一个像素点要和它所有的 26个相邻点比较,看其是否比它的图像域和尺度域的相邻点大或 者小。这样能确保 在尺度空间二维图像空间都检测到极值点。
同时,由于 DoG 值对噪声和边缘较敏感 , 因此 , 在上面 DoG 尺度空间中检测到局部极值 点还要经过进一步的检验才能精确定位为特征点。
首先,去除那些对比度较低的不稳定极值点。 Lowe 的试验显示,所有取值小于 0.04的 极值点均可抛弃(像素灰度值范围 [0, 1]
然而, 仅仅去除低对比度的极值点对于极值点的对于特征点稳定性是远远不够的。 DoG 函数在图像边缘有较强的边缘响应,因此我们还需要排除边缘响应。 DoG
函数的(欠 佳的 峰值点在横跨边缘的方向有较大的主曲率, 而在垂直边缘的方向有较小的主曲率。 主 曲率可以通过计算在该点位置尺度的 2×2的 Hessian 矩阵得到,导数由采样点相邻差来估 计。
2、关键点方向分配:
通过尺度不变性求极值点, 可以使其具有缩放不变的性质, 利用关键点邻域像素的梯度方 向分布特性, 我们可以为每个关键点指定方向参数方向, 从而使描述子对图像旋转具有不变 性。一般 通过求每个极值点的梯度来为极值点赋予方向。
确定关键点的方向采用梯度直方图统计法,统计以关键点为原点,一定区域内的图像像 素点对关键点方向生成所作的贡献。
方向分配的主要步骤:
1 . 确定计算关键点直方图的高斯函数权重函数参数 ;
2 . 生成含有 36柱的方向直方图,梯度直方图范围 0~360度,其中每 10度一个柱。由半径为 图像区域生成;
3 . 对方向直方图进行两次平滑; 4 . 求取关键点方向(可能是多个方向 ;
5 . 对方向直方图的 Taylor 展开式进行二次曲线拟合,精确关键点方向; 此时, 图像的关键点已检测完毕,每个关键点有三个信息:位置、尺度、方向; 同时也就使关键点具备平移、缩放、和旋转不变性。
3、关键点描述:
描述的目的是在关键点计算后, 用一组向量将这个关键点描述出来, 这个描述子 不但包括关键点, 也包括关键点周围对其有贡献的像素点。 用来作为目标匹配的 依据,也可使关键点具有更多的不变特性,如光照变化、 3D 视点变化等。
思路:通过对关键点周围图像区域分块,计算块内梯度直方图,生成具有独特 性的向量,这个向量是该区域图像信息的一种抽象,具有唯一性。
Lowe 实验结果表明:描述子采用4×4×8=128维向量表征,综合效果最优(不 变性与独特性 。
l128维关键点描述子生成步骤 1 、确定计算描述子所需的图像区域 2 、将坐标移至主方向
3 、 在图像半径区域内对每个像素点求其梯度幅值和方向, 然后对每个梯度幅值
乘以高斯权重参数,生成方向直方图。
4 、 在窗口宽度为 2X2的区域内计算 8个方向的梯度方向直方图, 绘制每个梯度方 向的累加值,即可形成一个种子点。然后再在下一个 2X2的区域内进行直方图统 计,形成下一个种子点,共生成 16个种子点。
5 、 描述子向量元素门限化及门限化后的描述子向量规范化。 描述子向量元素门 限化:方向直方图每个方向上梯度幅值限制在一定门限值以下 (门限一般取 0.2 。 关键点描述子向量的规范化正是可去除满足此模型的光照影响。 对于图像灰度值 整体漂移 ,图像各点的梯度是邻域像素相减得到,所以也能去除。
4、关键点匹配
分别对模板图 (参考图, reference image 和实时图 (观测图, observation image 建立关键点描述子集合。目标的识别是通过两点集内关键点描述子的比对来完 成。具有 128维的关键点描述子的相似性度量采用欧式距离。
?关键点的匹配可以采用穷举法来完成,但是这样耗费的时间太多,一般都采用 一种叫 kd 树的数据结构来完成搜索。 搜索的内容是以目标图像的关键点为基准, 搜索与目标图像的特征点最邻近的原图像特征点和次邻近的原图像特征点。
5、消除错配点:
RANSAC (Random Sample Consensus,随机抽样一致 是一种鲁棒性的参数估 计方法。
基本思想:
首先根据具体问题设计出某个目标函数, 然后通过反复提取最小点集估计该函数 中参数的初始值, 利用这些初始值把所有的数据分为“内点” ( inlier 和“外 点“(outlier ,最后用所有的内点重新计算和估计函数的参数。
sift算法介绍概要
