从 Harris 到 SIFT#在上一篇中我们详细介绍了 Harris 角点探测其首次系统性地用结构张量来描述局部特征。但其终究只是一个“原始基座”一个很明显的问题是无人机从不同高度拍摄同一片农田或者用不同分辨率传感器对同一区域成像时同一个角点为什么就检测不到了这就是 Harris 最核心的问题没有尺度不变性。Harris 的窗口大小是固定的比如 7×7。当我们把图像放大原来 7×7 窗口里的细节就变了一个角点在原图里看是角点放大后可能变成了平滑的边缘或者变成了更复杂的纹理。尺度变了特征就变了。除此之外Harris 还有另一个问题Harris 能告诉你这里有个角点但说不出来这个角点长什么样因此也就没法在另一张图像中找到同一个角点。换句话说它只有检测器没有描述子而拼接算法的核心步骤之一就是跨图像匹配同一特征。因此在 Harris 诞生后的十几年里计算机视觉领域一直在寻找一种更好的局部特征于是而 1999 年 Lowe 提出了 SIFTScale-Invariant Feature Transform 。其核心贡献在于它同时解决了尺度不变性和特征描述两个问题并且对旋转、光照、仿射变化都有很强的鲁棒性。2004 年其正式发表定稿版论文 Distinctive Image Features from Scale-Invariant Keypoints即使在今天 DL 方法盛行的背景下SIFT 在图像拼接、SLAM、三维重建等领域依然被广泛使用。尺度空间理论Scale Space Theory#展开 SIFT 具体步骤前的一个基础问题是尺度不变这件事到底怎么做到的直观上一个物体在不同尺度下看起来是不同的。远处的树是一个轮廓近处的树能看到每一片叶子。以此出发问题就是能不能构造一种表示方法让同一个特征在不同尺度下都能被稳定识别这就引出了尺度空间理论其核心想法很简单引入一个连续参数尺度参数通过逐渐模糊图像模拟出从近到远、从细节到轮廓的视觉变化过程。模糊的程度由控制越小保留的细节越多越大图像越模糊只剩大尺度结构。而实现这一模糊过程最常用的工具还是上一篇里见过的高斯卷积其中概括来说高斯核是唯一能保证尺度空间生成的线性核。 列举几个它的重要性质半群性质先用模糊再用模糊等价于直接用模糊。这保证了不同尺度的变换可以叠加。非增局部极值高斯模糊不会产生新的局部极值只会消除已有的极值。这保证了特征随尺度变化而消失是单调的不会凭空冒出新特征。各向同性高斯核是圆对称的不会引入方向偏好。但其实本质上还是加权平均来看一个例子对于当前中心点和偏移点的权重比例代几个值如下含义几乎只有中心像素参与计算邻近区域开始产生影响更大范围像素参与平均远处像素与中心像素影响接近显然 随着增大中心权重不断下降说明像素值不再主要由自身决定而是越来越多地受到周围更大范围像素的影响因此图像会变得越来越模糊。bebc36b3-4ba9-478a-a4ff-ac9e0db99a1a.png总结来说就是随着增大高斯核的权重分布会逐渐变得平坦。更大范围内的像素都会参与平均从而逐步“抹平”图像细节只保留较大的结构轮廓。这样我们就能模拟出一个特征在不同分辨率不同距离下的视觉效果。尺度空间理论还有更多细节之后遇到再展开。从 Harris 的角点到 SIFT 的尺度特征#现在我们知道了尺度空间的概念那一个很容易得到的想法就是Harris 已经能检测角点了SIFT 是不是直接把 Harris 搬到尺度空间里对同一张图的多个尺度空间内检测到的角点进行分析处理来获得尺度不变性实际上这种思路确实存在例如后来的 Harris-Laplace 就是在多尺度下运行 Harris 检测器但其更像是一种“遍历”并没有较根本地解决尺度不变性问题。展开来说由于不进行尺度空间的相关操作Harris 输出实际上只是特征点坐标。而一个角点无论尺度如何变化Harris 都可能给出较强响应。那么问题来了哪一个尺度才是真正对应这个结构的尺度或者说哪个尺度才是描述这个角点的最优尺度就像拍照时调整镜头焦距一样。焦距太近时只能看到树叶的纹理焦距太远时整棵树又缩成一个轮廓。只有在某个合适的观察尺度下目标结构才会呈现出最稳定、最容易识别的形态。因此为了真正获得尺度不变性SIFT 的思路是这样的找到某个局部结构最自然、最稳定的观察尺度。只有确定了这个尺度后续才能在与尺度相匹配的邻域内构造特征描述从而实现不同分辨率图像之间的稳定匹配。最终SIFT 在这一环节的输出变成了。这里的不是人为指定的参数而是需要由算法自动发现的特征属性。是特征最稳定的尺度。6ac08f51-e169-4940-ab97-c8cb15ca43ba.png现在就到了下一个问题如何在尺度空间中自动找到每个局部结构对应的最佳尺度高斯差分 DoG#我们已经知道尺度不变性的关键在于找到局部结构最稳定的观察尺度。现在同样对比来看Harris 本来就能检测特征点为什么不直接用 Harris 在尺度空间里的最大响应值作为最佳尺度问题出在 Harris 所依赖的本质信息上简单来说就是最大相应值并不代表最优尺度二者的语义不是对应的。回顾结构张量其中全部来自图像的一阶导数代表亮度变化有多剧烈。检测的是梯度能量聚集的位置。如果尺度变化那么和都会变化。最终响应值也会变化。问题是这个变化没有一个统一规律。 即使在多个尺度下运行 Harris 并选取响应最大的结果也不能保证找到结构真正对应的最佳尺度。因此我们需要一个具有明确尺度意义响应的检测器。4.1 高斯拉普拉斯 LoG#理论证明高斯拉普拉斯Laplacian of GaussianLoG 恰好具备这样的性质其过程如下首先对图像进行我们上面提到的高斯平滑然后计算拉普拉斯算子即在各坐标方向的二阶偏导和合起来就是这是比较理论的步骤实际计算中会先对高斯函数求二阶导得到 LoG 核后截断只对原图像做一次卷积得到响应值两者等价而在真正应用时还会加入一步尺度归一化这是因为二阶导天然会随着尺度增大而衰减例如比如同一个位置尺度 LoG50205即使结构完全一样响应也会因为模糊越来越强而变小这样我们根本没法比较不同尺度。尺度空间理论证明对于阶导数应乘进行归一化。这便是 LoG 在理论上的完整步骤现在再来看看原理。4.2 为什么 LoG 响应峰值对应最优尺度#LoG 本质上是对高斯平滑后的图像计算二阶导数而二阶导数描述的并不是亮度大小而是图像灰度变化本身的变化速度也就是曲率。因此 LoG 本质上是在找灰度变化最剧烈的局部特征现在再联系到尺度假设图像中存在一个亮圆斑我们现在在其中心使用一个很小的 LoG按照惯例其对应检测器尺寸为如果这个亮斑的尺寸很大那么检测器只能看到局部区域看不到亮斑边缘此时检测器内部几乎全是亮区域中心与周围差异不大。因此响应很弱继续增大尺度LoG 检测器同样变大开始覆盖整个圆斑结构。而 LoG 核具有典型的“墨西哥帽”结构中心权重为正外围环形区域权重为负mexican_hat_filter_laplacian_of_gaussian.png此时中心正权重区域恰好覆盖亮斑主体。得到大量正贡献。而外围负权重区域落在边缘背景尺度合适的情况下背景接近 0负贡献就会很小。此时达到极大值。而如果尺度继续增大外围负环就会开始覆盖大量亮区域和背景正负贡献互相抵消响应就会开始下降。因此同一个位置就会在不同尺度下出现不同响应尺度 LoG响应1 82 253 654 1205 956 607 20因此LoG 值其实反应的是在当前尺度下目标与背景之间的对比结构是否最明显。这里很容易有这一个问题LoG 好像只是不断换一个更大的检测器去扫描图像那为什么不直接遍历检测器尺寸反而要依靠呢但这其实是搞错了主角截断 LoG 的尺寸只是因为高斯核在外无限接近 0我们真正是在遍历在不同的模糊程度下去找到这个位置的局部结构和背景对比最明显的尺度。4dcbe9af-171f-4075-b7dd-449692557533.png4.3 实际方案DoG#LoG 的理论很好但就和 Harris 为什么要对结构张量进行工程优化一样其计算代价相当高。因此我们在实际工程中使用的是其近似版本高斯差分Difference of GaussianDoG对于尺度空间如果取两个相邻尺度和直接做差看起来只是简单相减但根据尺度空间理论可以证明也就是说它实际上近似于尺度归一化后的 LoG这也是 SIFT 中真正使用的方法在下面的具体步骤中我们就可以看到它的位置。SIFT 特征点检测#下面就开始 SIFT 的实际构建了这部分逻辑十分复杂步骤也较多但可以说是最标准化的流程后续的几个出名算法其实本质上就是针对不同目标对 SIFT 的简化改进。5.1 DoG 金字塔#一个很明显的道理是尺度空间不可能无限大如果一直增大图像最终会被模糊成一团灰色继续计算没有意义。因此 SIFT 采用了一个方法当尺度增大到一定程度后不再继续增大而是直接缩小图像。一个需要注意的是原论文中原始图像在开始处理前会先通过插值放大一倍来进行更密集的采样而随着现代成像技术的提升这点并不强制了。回到主线假如尺寸为 1024×1024 的初始图在处理中会逐渐减小到 512×512再到 256×256、128×128 等。而这样做的效果其实与继续增大尺度非常接近。假设图像中有一个半径的圆斑在初始图中它占据很大面积但如果直接缩小图像一半那么圆斑半径也变成相当于目标自动变小了。其核心逻辑是目标变小与检测器变大本质上都是在改变二者的相对尺度。这便形成了 SIFT 的金字塔结构其中存在两个核心设计Octave 和 Interval。SIFT 将尺度空间划分成多个组每个组称为一个 Octave八度。每经过一个 Octave图像尺寸缩小一半这样整个尺度空间被分解成多个层级小尺度特征主要在前几个 Octave 中检测而大尺度特征则在后几个 Octave 中检测。但仅有 Octave 还不够因为同一个 Octave 内仍然需要搜索最佳尺度所以每个 Octave 内还会划分多个 Interval尺度间隔。原论文中设注意这里的并不是后面马上要提到的 Gaussian 层数或者 DoG 层数而是和下一部分检测有关它是指一个 Octave 中真正参与尺度搜索的 Interval 数量。展开来说为了让一个 Octave 恰好覆盖尺度翻倍我们定义一个尺度倍率当时因此尺度会按照如下方式增长例如初始尺度取则对应层号0 1.601 2.022 2.543 3.20这样便定义出了一个 Octave 中的尺度划分方式。接下来需要构建对应的高斯图像如果只考虑这 3 个 Interval那么理论上只需要生成对应尺度的 Gaussian 图像即可。但后面还需要构建 DoG 图像并进行三维尺度空间极值检测因此 SIFT 会额外生成若干高斯层作为边界缓冲。最终每个 Octave 实际会生成个 Gaussian 图像。当时生成结果就如下Gaussian层作用1.60 有效尺度层2.02 有效尺度层2.54 有效尺度层3.20 有效尺度层达到也是下一 Octave 的起始来源4.03 边界缓冲层用于构建 DoG5.08 边界缓冲层用于构建 DoG 与极值检测最终多个 Octave 的 Gaussian 图像共同组成高斯金字塔Gaussian Pyramid。得到高斯金字塔后在每个 Octave 内对相邻 Gaussian 图像做差例如Gaussian层 Gaussian尺度 DoG层 DoG对应尺度一般情况下个个而这些 DoG 图像会共同组成 DoG 金字塔Difference of Gaussian Pyramid。之所以需要额外生成两层 DoG是因为后面寻找极值点时需要同时比较当前层、上一层和下一层总计的三维邻域。最顶层和最底层 DoG 无法参与极值检测只能作为边界层存在这样以来最终真正参与尺度空间搜索的 DoG 层数恰好为这也正好对应最开始设定的 Interval 数量这样我们就完成了极值检测的所有准备。9de0d1aa-b7e5-4e3f-9819-09d28393549a.png5.2 尺度空间极值检测#这一步相对简单得到 DoG 金字塔后其最顶层和最底层 DoG 不参与检测假设当前考察点位于现在这个点周围有当前层 8 个邻居、上一层 9 个邻居以及下一层 9 个邻居总计26个邻居。SIFT 要求当前点必须同时大于或小于全部 26 个邻居。遍历整个金字塔这样的点才能被保留。这一步就是尺度空间极值检测Scale Space Extrema Detection也就是说只有中心点同时成为空间和尺度两个方向上的极值才能成为候选关键点。此时得到的结果已经包含了前两维说明位置显著第三维说明尺度显著并且我们还可以通过尺度系数和检测器大小的关系估计出特征尺寸。e4423bd6-5c37-4419-ad9a-b54c97fdb691.png到这里我们已经成功提取出了候选关键点但 SIFT 仍然还有相当一部分内容我们继续。5.3 关键点精确定位#现在我们已经获得了一批候选关键点但这里有一个问题DoG 金字塔本质上是离散采样的尺度空间而真实极值点的位置并不一定刚好落在采样网格上。比如某个位置附近的 DoG 响应如下位置 DoG8010095按照规则已经是局部最大值。但真正的峰值有可能位于这时更符合关键点要求的应该是离散坐标导致了这一误差。同样的问题也会出现在尺度方向由于离散取值真实最佳尺度可能位于两层之间。所以如果直接把离散极值点作为最终结果会导致定位误差较大且容易保留大量不稳定噪声点。最终从候选点到最终特征点间 SIFT 会再进一步进行亚像素级优化具体可划分为三步5.3.1 亚像素定位#这步涉及到的数学原理和公式较多这里先概述一下其核心逻辑使用泰勒展开和差分近似候选点附近的特征值来估计真正极值点相对于当前采样点的偏移量由此进行后续的修正和筛选。4c269d98-d02e-48c4-8319-ef843b81e002.png展开来设候选点为则 DoG 函数在该点附近可以近似写成记当前位置到真实极值点的偏移量为现在这个式子可以写成关于求导使结果为 0