特征点提取、描述与匹配

SIFT特征点检测-Part I

• 图像变化的类型
  • 几何变化
    • 旋转（欧式变换包含旋转和平移）
    • 相似（旋转（实际是欧式变换） + 各向相同的尺度缩放）
    • 仿射（各向不同的尺度缩放，物体局部为近似平面）
  • 灰度变化
    • 仿射灰度变化（$I \to a I + b$I→aI+b）
• SIFT——Scale Invariant Feature Transform
  • DoG特征检测 + SIFT描述子
  • 性质
    • 不变性
      • 旋转和尺度不变性
      • 三维视角变化和光照变化的适应性
      • 局部特征，在遮挡和场景杂乱时保持不变性
    • 辨别力强
      • 特征之间互相区分能力强，利于匹配
    • 数量较多
    • 扩展性强
  • 算法流程
    • 多尺度空间极值点检测
    • 关键点的精确定位
    • 关键点的主方向计算
    • 描述子的构造
• 尺度空间
  • 检测在尺度变化时仍然稳定的特征
  • 尺度空间：$L(x, y, \sigma) = G(x, y, \sigma) \ast I(x, y)$L(x,y,σ)=G(x,y,σ)∗I(x,y)
    • $G(x, y, \sigma) = \frac {1}{2 \pi \sigma^2} e^{-(x^2 + y^2) / 2 \sigma^2}$G(x,y,σ)=2πσ21​e−(x2+y2)/2σ2
  • 高斯差分尺度空间：$D(x, y, \sigma) = (G(x, y, k\sigma) - G(x, y, \sigma)) \ast I(x, y)$D(x,y,σ)=(G(x,y,kσ)−G(x,y,σ))∗I(x,y)
  • 高斯差分时对尺度归一化LoG的很好近似，尺度归一化的LoG空间具有真正的尺度不变性
    • 计算效率更高
  • 高斯金字塔
    • 同组内，上层图像分别为下层图像的升$k$k的尺度变换
    • 上组为下组的下采样（$\sigma$σ增加一倍）
    • 同组内，相邻层图像的差分得到DoG金字塔
• 多尺度空间极值点检测
  • 建立三位尺度空间形式（上述高斯差分金字塔）
  • 极值点检测，搜索每个点的26邻域（上9+中8+下9）
  • 局部极值点作为候选关键点
• 关键点精确定位
  • 搜索到的极值点不一定是真实空间的极值点
  • 对DoG函数进行曲线拟合，计算曲线极值点，实现精确定位
  • 三元二次函数拟合（P17）
  • 去除
    • 对比度低的点（设置阈值）
    • 边缘上的点（Hessian矩阵，特征值关系，类似Harris，边缘点的比值明显较大）

特征点描述与匹配

• 匹配：确定不同图像中对应空间同一物体的投影的过程
  • 基于多幅图像视觉问题的基本步骤
• 类型
  • 点匹配
  • 直线匹配
  • 曲线匹配
  • 区域匹配
• 点匹配基本原则
  • 利用点周围的信息描述点（灰度、颜色、梯度等）
  • 进行相似性度量
• Cross Correlation
  • 利用相关函数，评价特征点邻域的灰度相似性
  • 确定相关窗口，在定义的搜索区域内搜索
  • 特性
    • 基于图像灰度
    • 确定窗口的大小和形状
    • 没有旋转不变性（搜索区域的确定）
    • 对光照变换敏感
    • 计算代价很大
• 匹配过程
  • 左图每个特征点对应右图的一个候选特征集
  • 右图每个特征点对应左图的一个候选特征集
  • 二者基本相似
  • 可以通过寻找两张图像的特征点集进行后续的匹配（特征向量集——对应点集）

SIFT特征点检测-Part II

• 主方向计算
  • 解决特征描述对于旋转的不变性
  • 特征点圆周邻域，划分角度区间
  • 统计各角度区间的梯度赋值和
  • 最大复制占据的角度区间作为主方向
• 主方向校正
  • 沿着主方向确定描述的内容
• SIFT描述子的构造
  • 按照主方向取邻域
  • $8 \times 8$8×8邻域，分成4个区域
  • 各个区域内16个像素位于8个方向的赋值统计
  • 将这些区域的赋值统计进行编码，得到128维向量
• 描述子特点
  • 直方图统计：提高了对局部形变的适应能力
  • 子区域划分：弥补了丢失的位置信息，增强辨别力
  • 高斯加权，强调中心区域的作用，弱化边缘
• 不变性
  • 尺度不变性（根据关键点尺度选择高斯图像和邻域大小）
  • 旋转不变性（主方向和主方向的校正）
  • 适应复杂的几何变形（分块、高斯加权）
  • 适应复杂的光照变化（先行光照归一化、非线性光照clip为0.2）
• 特征匹配
  • 匹配准则：NNDR（$\frac{d(m, m_1)}{d(m, m_2)}$d(m,m2​)d(m,m1​)​）第一接近距离与第二接近距离的比值
  • 搜索策略：BBF

ORB——BRIEF描述子

• BRIEF：二元特征描述子
• 从确定的特征点的邻域中，随机选取若干对像素点，分别比较没对像素点的灰度大小，赋值为1或0，构造描述子
• 匹配：汉明距离——等长字符中对应位置出现不同字符的个数

基于DNN的特征描述子学习

• 通过提升描述效果，提升匹配精度
• L2-Net
• SOSNet：利用二阶相似性
• 不一定真的有提升？匹配不是最终目的，匹配精度高不一定很重要

ICP——Iterative Closest Point

• 两组点集之间的匹配
• 对齐两个相互交叠的曲线 / 曲面
• 问题：已知对应点集合$X$X和$P$P
• 求解：旋转矩阵$R$R和平移向量$t$t，使$E(R, t) = \arg \min_{R, t} \frac 1n \sum_t \|x_i - R p_i - t\|^2$E(R,t)=argminR,t​n1​∑t​∥xi​−Rpi​−t∥2
• 如果存在正确的对应，那么其相对旋转和平移有闭合解
• 最优解
  • 确定两个集合的质心，并将所有点减去对应的质心得到$X^\prime$X′和$P^\prime$P′
  • $W = \sum_i x_i^\prime {p_i^\prime}^\top$W=∑i​xi′​pi′​⊤
  • 利用SVD求解最优变换$W = UV^T$W=UVT，$t = \mu_x - R \mu_p$t=μx​−Rμp​
• 三维数据点？最近点匹配

• 点集选取
  • 所有点
  • 均匀采样
  • 随机采样
  • 法方向空间均匀采样
• 点集匹配
  • 最近邻点（稳定，慢）
  • 法方向最近邻点（平滑好，对噪声敏感）
  • 投影法（搜索对应点速度快）
• 点集对应权重
  • 固定权重
  • 距离权重
  • 法方向权重
• 每一次迭代，对应点不应准确，误差反应的因此也不是决定的匹配误差，因此迭代实现的使局部最优化求解，在一般的条件下，可以实现收敛

鲁棒匹配的RANSAC框架

• 鲁棒匹配问题
  • 大量外点——直接拟合——存在严重偏差
  • 排除外点数据
• 一般步骤
  • 确定求解模型$M$M，所需要的最小数据点的个数$n$n（取决于空间自由度），由$n$n个数据点组成的子集称为模型$M$M的一个样本
  • 从数据点集$D$D中随机抽取样本$j$j，由该样本计算模型的一个实例$M_p(j)$Mp​(j)，确定与$M_P(j)$MP​(j)之间几何距离小于阈值$t$t的数据点集合$S(M_P(j))$S(MP​(j))，称之为实例$M_P(j)$MP​(j)的一致集
  • 如果一致集中点个数大于阈值$T$T，则使用$S(M_P(j))$S(MP​(j))重新估计$M$M，输出结果；否则继续抽取样本
  • 经过$k$k词抽样（还是没有满足阈值大小的一致集），选择最大的一致集，用其重新估计模型，输出结果