尺度不变特征变换匹配算法

尺度不变特征变换匹配算法ScaleInvariantFeatureTransform SIFT 报告人 邵妍 2012年2月29日 Sift算法简介 Sift是DavidLowe于1999年提出的局部特征描述子 并于2004年进行了更深入的发展和完善 Sift特征匹配算法可以处理两幅图像之间发生平移 旋转 仿射变换情况下的匹配问题 具有很强的匹配能力 SIFT算法基于图像特征尺度选择的思想 建立图像的多尺度空间 在不同尺度下检测到同一个特征点 确定特征点位置的同时确定其所在尺度 以达到尺度抗缩放的目的 剔出一些对比度较低的点以及边缘响应点以后提取每个稳定关键点周围的局部特征 形成局部描述子并将其用在以后的匹配中 Sift算法简介 sift算法特点 SIFT特征是图像的局部特征 其对旋转 尺度缩放 亮度变化保持不变性 对视角变化 仿射变换 噪声也保持一定程度的稳定性 独特性 Distinctiveness 好 信息量丰富 适用于在海量特征数据库中进行快速 准确的匹配 多量性 即使少数的几个物体也可以产生大量SIFT特征向量 经过优化的SIFT算法可满足一定的速度需求 可扩展性 可以很方便的与其他形式的特征向量进行联合 SIFT算法步骤 1 检测尺度空间极值点2 精确定位极值点3 为每个关键点指定方向参数4 关键点描述子的生成 Sift算法简介 尺度空间的生成 高斯卷积核是实现尺度变换的唯一线性核 于是一幅二维图像的尺度空间定义为 其中 是尺度可变高斯函数 并且有 x y 是空间坐标 是尺度坐标 的大小决定图像的平滑程度 大尺度对应图像的概貌特征 小尺度对应图像的细节特征 大的值对应粗糙尺度 低分辨率 反之 对应精细尺度 高分辨率 为了有效的在尺度空间检测到稳定的关键点 提出了高斯差分尺度空间 DOGscale space 利用不同尺度的高斯差分核与图像卷积生成 高斯差分尺度空间 极值点检测 为了寻找尺度空间的极值点 每一个采样点要和它所有的相邻点比较 看其是否比它的图像域和尺度域的相邻点大或者小 如图3所示 中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9 2个点共26个点比较 以确保在尺度空间和二维图像空间都检测到极值点 精确定位极值点 通过上步检测出了每个尺度上的极值点 现在就需要采用拟合三维二次函数求得极值点在原图像中的位置 并且为了增强特征点匹配时的稳定性和抗噪能力还需要去除低对比度的关键点和边缘响应点 因为DoG算子会产生较强的边缘响应 等不稳定的点 精确定位极值点 定位极值点 令极值点A对进行泰勒展开 1 其中 是到点A的偏移量 对 1 式求X的偏导数 并令偏倒为0 得到 2 如果大于0 5 则意味着这个极值点与另一个采样点离得更近 需采用插值法求得极值点位置的估计值 精确定位极值点 去除低对比度的关键点 将上式 2 带入公式 1 中即可得通过观察实验结果得出 小于0 03的极值点均将被丢弃 阈值越小 则会获得越多的匹配点个数 精确定位极值点 去除边缘上的极值点 曲面上每个点都有两个主方向 并且沿这两个主方向的法曲率 即两个主曲率 分别是曲面在该点法曲率的最大值和最小值 在边缘上的极值点 垂直于边缘的方向上 法曲率最大 沿边缘的方向上 法曲率最小 如果极值点分布在边缘上 该点的法曲率最大值和最小值之比一般情况下要比非边缘点的比值大 根据这种思想 我们可以设一个比值的阈值 当比值大于这个阈值就认为极值点在边缘上 精确定位极值点 去除边缘上的极值点 首先计算待测极值点的Hessian矩阵 设是较大的特征值 是较小的特征值 则由矩阵性质知 设 则可得 判断是否是边缘点只需判断上式左边项是否在某个阈值之下即可 实验表明一般阈值取r 10时 关键点方向分配 SIFT特征实现旋转不变性的基本思想是采用 相对 的概念 先为关键点赋一个方向 定义的关键点描述子均是相对于该方向的 因而可以实现匹配时的旋转无关性 为实现尺度无关 根据关键点所在尺度选择与该尺度最相近的高斯平滑图像L 对L上的每个点L x y 计算梯度和方向 关键点方向分配 以关键点为中心 划定一个邻域 利用所有在此区域内的点的梯度形成一个方向直方图 直方图的横坐标是梯度方向 共36项 每项代表了10度的范围 纵坐标是梯度大小 对于归到横坐标上任一项内所有的点 将其梯度大小相加 其和作为纵坐标 下图所示 关键点方向分配 从直方图中选出纵坐标值最大的一项的方向作为该关键点的主方向 如果存在其他方向 纵坐标的大小大于主方向纵坐标大小的80 也将其作为该关键点的方向 特征点有多个方向的情况下 实际上是在此位置上有多个关键点 他们的方向不同 描述子生成 前面已经为关键点赋予了图像位置 尺度以及方向 这一步将根据关键点周围的局部特征计算得出一个特征描述子 如下图所示 在关键点周围取一个邻域 并对其中点的梯度做高斯加权 这个邻域分为16个子区域 每个子区域取八个方向 实验 实验一特征匹配 实验简介 对两幅商标图像进行高斯差分金字塔的构建 并提取出关键点 最后通过关键点特征向量的欧氏距离作为关键点的相似性度量对两幅图像的关键点进行匹配 高斯差分金字塔构建结果 实验一特征匹配 实验一特征匹配 定位特征点 实验一特征匹配 关键点匹配 图1 两幅相似图像的匹配结果 图二 两幅不相似图像的匹配结果 数据库 100幅二值商标图像 图像的分辨率为111x111在100幅图像中 大致可以分为十种商标 每种商标分别有10幅由旋转 缩放等处理得到的相似图像 实验二图像检索 实验二图像检索 待检索图像 检索结果 实验二图像检索 待检索图像 检索结果 实验二图像检索 在该试验中 随机抽取10幅待检索图像进行检索的查全率为9