总览

在过去的几十年中，已经发现拐角及其空间排列(spatial arrangement)以及拐角周边的局部强度(local intensity)/颜色分布(colour distribution)携带了大量有关物体的分析。

Harris拐角检测器(Harris Corner Detector)

思路：我们应该能够通过一个小窗口(window)轻松定位拐点。在该点上，任何方向上的移动都会产生很大的强度变化(large change in intensity)。

• "平坦"区域(flat region): 从各个方向切换窗口均无变化。
  
• “边缘”区域(edge region): 沿边缘方向的移动窗口无变化。
  
• “拐角”区域(corner region): 沿各个方向的移动窗口都有显著变化。
  
  通过将图像数据移动 [u, v] 引起的强度的窗口平均变化：
  
  窗口函数(Window function) w(x, y) 选项如下：
  
  通过一系列的数学公式转换，我们可以获得图像的特征值(eigenvalue)。
  由于原公式非常耗时间，因此我们可以使用其近似公式，使用Taylor series进行转换，并将其转化成矩阵形式。
  
  
  
  E(u, v)的等强度线(Iso-intensity contour)。
  
  位移窗口中的强度变化: 特征值分析 (eigenvalue analysis) 。
  
• 当 λ2 >> λ1 或 λ1 >> λ2, 则是 edge
• 当 λ1 和 λ2 都很小; 并且E在各个方向都基本是常量，则是 flat。
• 当 λ1 和 λ2 都很大; 并且E在各个方向都增加，则是corner。
  

求拐角响应度 (measure of corner response)

k - 经验常数，k = 0.04 ~ 0.06。

R仅依赖于M的特征值(eigenvalue)。

• 当R很大时 (R >> 0)，此点为corner。
• 当R是负数且有大的强度值时 (R << 0)，此点为edge。
• 当R的绝对值很小时 (R ≈ 0)，此点为flat。
  

算法

1. 计算并查找具有大边角响应函数 (large corner response function) R的点(R > threshold)。
   
   
2. 取 R 的局部最大值。
   
   

拐角的使用

图像内容被转换为在检测到的拐角处提取的局部特征，该局部特征在平移，旋转，缩放以及照明变化的情况下不变。

比例不变特征变换 (Scale-invariant Feature Transform - SIFT)

SIFT的简要表示是Harris-corner-like关键点 (keypoint) 的梯度直方图(histogram of gradient)。
关键点在比例 (scale)，旋转 (rotation)，明度变化 (illumination changes)，噪声中的变化时是保持不变性(invariant)的。

过滤方式 (Filtered Approach)

• 比例空间机制检测(Scale-space extrema detection)：确定在比例和方向上不变 (invariant to scale & orientation) 的潜在点。并获得高斯差分函数 (Difference-of-Gaussian function)。
• 关键点定位 (keypoint localization)：通过拟合二次方 (fitting a quadratic) 来改进位置估计。使用极限阈值来滤除无关紧要点或边缘点。
• 方向分配 (orientation assignment): 基于局部梯度 (local gradient) 分配给每个关键点和相邻像素的方向。
• 关键点描述符构造 (Keypoint Descriptor Construction) ：基于局部邻域梯度的特征向量 (feature vector)。

比例空间 (Scale Space)

我们使用高斯内核 (Gaussian Filter) 对图像进行不同比例的表达。


研究表明，标度拉普拉斯算子 (scaled Laplacian) 的最大值 (maxima) 和最小值 (minima) 提供了最稳定的比例不变特征 (most stable invariant features)。

我们可以使用比例改变的图片来近似这个操作。

高效计算：我们需要平滑的图像L (smoothed images L)，并可以通过简单的图像减法来计算D。
高斯差分是一种特征增强算法，涉及从原始图像的另一个模糊版本中减去原始图像的一个模糊版本。让相同尺寸的不同模糊度图像进行依次相减。


一般都设置为：

问：我们需要缩放图像多少次，并且每个缩放图像需要创建多少后续的模糊图像 (subsequent blur images)？
理想的octaves应为四个，并且对于每个octave，模糊图像的数目应为五个。

比例空间总结

比例空间是从单个图像生成的具有不同比例的图像的集合。
构建 比例空间 我们需要：

• 滤除所有噪声(ignoring any noise)：使用高斯模糊技术来减少图像中的噪点。从图像中删除纹理和次要细节，仅保留诸如形状和边缘之类的信息。
• 此外，我们需要确保这些特征和图像比例无关。我们通过创建"比例空间"在多个比例上搜索这些特征。

比例空间极值检测 (Scale-Space Extrema Detection)

检测 3 x 3 x 3 邻域中的最大值和最小值作为关键点的候选项。

需要多少个Octave？

图像的第 0 个 octave

缩放直到图像太小

第 0 个 Octave 的高斯差分 (DoGs)

其他octaves的高斯差分

在二次采样之后以及找到octave的缩放图像之前，先进行1.6的平滑。
为了补偿较高空间频率的损失 (compensate the loss of higher spatial frequencies)，原始图像的大小增加了一倍 (即 octave #0)

准确关键点定位 (Accurate Keypoint Localization)

通过高斯差分局部极值检测 (difference-of-Gaussian local extrema detection)，我们可以获得关键点的近似位置。

为了定位局部最大值和最小值，我们遍历图像中的每个像素，并将其与相邻像素进行比较，“相邻”包括了在 octave 中上一个和下一个图像的9个像素。如某一个点，其周边的八个点，以及同尺寸其他模糊程度的相邻图片的18个点，一共26个点属于其邻点。

这些近似值 (approximation) 最初是直接使用的。但为了改善匹配 (matching) 和稳定性 (stability)，我们使用3D二次函数 (3D quadratic function)。

• 进行比例空间函数D（x，y，σ）的泰勒级数展开。
  

• 阈值化关键点(Thresholding Keypoints): 极值处的函数值用于拒绝不稳定的极值，极值位置的绝对值小于0.03会导致该极值被丢弃(假设图像像素值在[0,1]的范围内)。(也就是低对比度 low contrast 的点被丢弃)

• 消除边缘响应 (Eliminating Edge Response)： 高斯差分会导致边缘很强。沿边缘的某些位置很难确定。并且只是添加少量噪声，也会导致结果不稳定。这些位置将在边缘上具有较大的主曲率 (large principle curvature), 而在垂直于边缘的方向上具有较小的主曲率。因此我们需要计算该位置的主曲率并比较两者。最终会算出一个比率 (ratio)，我们可以通过和阈值比率比较来排除边缘点。(通常该阈值 threshold on ration of principal curvatures r0 = 10)

分配方向 (Assigning an Orientation)

在确定好了关键点之后，我们的下一步就是为关键点分配方向，这用于使匹配技术 (matching technique) 不受旋转影响 (invariant to rotation)。

选择最接近原图像比例的高斯平滑图像L。接着，选择关键点周围区域中的点 (points in region)，并计算其梯度的大小和方向 (magnitude and orientation)。

Gx = 点的左右方向两点的差，
Gy = 点的上下方向两点的差,
magnitude = 根号(Gx^2 + Gy^2)
orientation = atan(Gy / Gx)

接着，创建方向直方图 (orientation histogram)，该直方图由36个bin组成 (0 - 360°)。样本添加到适当的bin中，并通过梯度强度(gradient magnitude)以及高斯加权的圆形窗口 (Gaussian weighted circular window) 加权，其 σ 为关键点尺寸的1.5倍。

在直方图中，找到了方向最高峰以及该最高峰80%之内的其他峰。3个最接近极值的直方图值用于插值(拟合到抛物线 fit to a parabola)到一个更准确的极值 (a better accurate peak)。
截至目前，每个关键点都有4个维度：x位置，y位置，比例和方向。

关键点描述符 (Keypoint Descriptor)

为了鲁棒性，使用关键点周围的区域来进行计算，而不是直接从关键点进行计算。
像之前一样，我们使用最近尺度 (nearest scale) 的L为关键点周围区域的点来计算强度和方向。
为了确保方向不变性 (orientation invariance)，描述符的梯度方向和坐标相对于关键点的方向旋转。
提供了应对 照明(illumination) 和 3D相机视点(viewpoint) 变化的不变性。

方向直方图的 2 x 2 数组 (子区域 subregions)，每个都有 8 个方向bin。

子区域中添加到直方图中的每个点均由以下方式加权：

• 梯度强度 (gradient weight)
• σ，为描述符窗口宽度的一半
• 1 – d，其中d是特定样本到bin中心的距离

研究表明最好的配置是：具有 8 个 bin 的 4x4 子区域，这导致了特征描述符 (feature descriptor) 中具有 4 x 4 x 8 = 128 个元素。(这意味着每个关键点将会有128个特征)

向量归一化 (Vector Normalization)

最后实现以确保 明度变化 的不变性 (invariance to illumination change)。
整个向量都归一化为1。
为了应对非线性照明 non-linear illumination (相机饱和度)，将特征向量中的阈值设置为不大于0.2，然后对向量进行重新归一化 (re-normalized)。

流程总结

1. 通过查找高斯差分的结果，来寻找特征的大致近似(rough approximations)。
2. 更加准确地定位关键点。
3. 将低于阈值的关键点(边缘点)排除。
4. 确定关键点的方向。
5. 计算每个关键点的128特征向量。
6. 结果：(x, y, scale, orientation, 128 visual descriptor)

应用

• 给定两张图片。一幅图像是我们正在寻找的对象的训练样本，另一幅图像是可能包含训练样本实例的世界图片。这两个图像具有跨越不同octave的相关特征。
  
• 给定N张图片，然后判断 Ii 和 Ij 之间有多相似。这个相似应该对 平移和旋转 (translation, rotation)，明度变化 (illumination changes), 比例 (scale)，视点变化，相机 具有不变性 (invariant)。
  1. 从每张图片中提取SIFT关键点和描述符。每张图片被一个 Bag-of-Features 所代表，每个特征具有128个维度。
  2. 两张图片之间的相似度和不相似度能通过测量两张图片SIFT之间的
     距离来确定: dij = dist(SIFTi, SIFTj)。其中，dist测量了两个集合之间的距离(可以使用hausdorff距离计算)。

视觉词袋模型 (Bag-of-Visual-Words Model - Bow)

• 使用SIFT来将图片用 Bag-of-features 来代表。
• 机器学习视觉词汇。将所有特征聚类为K个簇，每个簇代表了一个视觉词汇。通常，k-means是个不错的选择。
  K-mean算法详解
• 为每个图像建立视觉词汇的直方图(histogram of the visual word)。接着比较这些图像的直方图。

计算直方图之间距离 (卡方距离)

给定两个直方图h1和h2，计算其chi-squared距离