特征匹配

目标：

1. 同时识别3D中的对象及其姿态：这意味着我们不仅要识别出对象，还要确定它在三维空间中的位置和方向。
2. 在多个视图中跟踪特征：在不同的图像或视频帧中，要能够识别和追踪同一个特征。

挑战：

1. 由于姿态、光线等的变化，特征在每个视图中的外观会有所不同：例如，由于光线的角度或强度变化，或是对象从不同的角度拍摄，同一个物体的同一个特征在不同的图像中可能会有不同的外观。
2. 在一个视图中可见的某些特征在另一个中可能会缺失：例如，当物体旋转时，之前可见的某个特征可能被遮挡或移出视野。
3. 背景可能包含类似的“匹配”特征：这意味着背景中可能有与要跟踪的对象相似的特征，这可能会导致误匹配或混淆。

特征匹配作为模型拟合（Feature matching as model fitting）

1. 不仅仅是寻找相同的特征，而是寻找相同的空间排列的特征：这意味着在进行特征匹配时，我们不仅要看这些特征是否相似，还要看它们之间的相对位置或排列是否相似。

2. 模型拟合问题：

   • 提出一个模型来解释匹配点之间的对应关系：简单地说，就是找到一个数学模型或公式，使得通过这个模型，我们可以解释或预测一组点在另一个图像或视角下的位置。
   • 找到符合模型的点/测量拟合度/找到模型参数：这个步骤涉及到实际地利用模型去找到或验证匹配的点，并对模型的准确性进行评估，还可能包括优化模型参数以获得更好的匹配结果。

3. 问题：

   • 离群值 (数据不被模型解释 - Outliers) ：在实际数据中，总会有一些点或特征与大多数数据不符或不适用于我们的模型，这些点称为离群值。
   • 模型所解释的数据中的噪声 (Noise)：即使某些数据点被模型很好地解释了，但由于各种原因（如传感器误差、环境因素等），这些数据点可能仍然包含噪声或误差。

霍夫变换（Hough Transform）

• 每个边缘点“投票 (vote)”给经过该点的直线。
• 识别得票最多的直线。

• 如果点的位置没有噪声，那么识别得票最多的参数是容易的。
• 通常情况下，存在一些噪声。

• 解决噪声的方法：参数分箱
• 点为分箱投票

为了应对由于噪声导致的不准确性，可以使用“参数分箱”的方法。也就是说，不是让每个点为一个具体的参数值投票，而是为一个参数范围或“箱子”投票。这样，即使由于噪声导致点的位置有些偏离，它仍然会落入相应的箱子内，从而提高了检测的稳定性和准确性。

另一个问题：斜率和截距 (m,b) 是无界的。

解决方案：使用 (m,b) 的极坐标表示法。

参数

1. 分箱大小：在参数空间中，将连续的值划分为离散的“箱子”或范围。这有助于减少噪声对直线检测的影响。
2. 峰值阈值：这是确定一个分箱是否包含一个有效直线的最小票数。只有当票数超过这个阈值的分箱才被认为是代表一个有效的直线。
3. 峰值数量（= 直线数量） ：这是你想从霍夫变换中检测到的直线的最大数量。
4. 最小直线/线段长度：检测到的直线或线段应该至少有这么长才会被考虑。
5. 允许的最大间隙：如果两个线段之间的距离小于这个值，它们可以被视为同一条直线的一部分。

Hough 变换中的峰值

当我们对图像中的边缘点进行霍夫变换时，每个边缘点都会为可能经过它的所有直线投票。这些投票在参数空间中累积。当某个区域的投票数达到一个显著的高值（即峰值），这意味着图像中有许多边缘点支持该区域表示的直线存在。

因此，通过在霍夫空间中寻找峰值，我们可以确定图像中存在的直线及其参数。每一个峰值都对应于图像中的一个或多个直线。这些峰值的高度（即票数）可以用于过滤出强烈支持的直线，并舍去只是由噪声或其他不相关因素导致的假阳性直线。

Hough 变换的效率

1. 霍夫变换是一种对参数的网格搜索：这意味着霍夫变换实际上是在参数空间的离散网格上进行搜索，试图找到最佳的参数组合（即直线、圆或其他形状的参数），这些参数组合可以最好地匹配输入图像中的数据。
2. 当N个参数增加时会发生什么？ ：随着参数数量N的增加，搜索空间（即参数空间）的维度也会增加。这意味着计算的复杂度将显著增加。具体地说，如果每个参数都需要相同数量的网格单元，那么总的网格单元数量将成指数地增长。这会导致霍夫变换需要更多的计算资源和时间。此外，随着维度的增加，可能还会遇到所谓的“维度的诅咒”问题，这意味着在高维空间中，数据的分布和行为可能与低维空间中的情况完全不同，这可能会影响检测的准确性。

小结

• 霍夫变换是一种用于检测图像中结构的方法。
• 每个像素为参数“投票”。
• 常见应用：
  • 直线检测
  • 圆检测
• 本质上是对每个参数的所有可能值进行的网格搜索，所以仅限于少数几个参数。

RANSAC

1. RANSAC = RANdom Sample Consensus（随机抽样一致性） ：RANSAC是一种迭代方法，用于从包含许多离群点的数据中估算数学模型的参数。

2. 像霍夫变换一样，点“为解释它们的模型投票” ：这意味着在RANSAC中，我们不是简单地为一个参数组合或模型投票，而是检查哪个模型最好地解释了数据点的集合。

3. 迭代地：

   • 随机抽取N个点：为了估计模型，首先随机选择数据中的N个点。
   • 计算模型参数：使用这N个点来计算模型的参数。
   • 计算被模型解释的点数（内点） ：之后，检查整个数据集中有多少点符合这个模型，这些点被称为内点。
   • 最佳模型 = 解释最多点的模型：在多次迭代中，那个解释了最多点的模型被视为最佳模型。

RANSAC方法特别适用于那些数据中含有大量噪声或离群点的情况，它可以有效地找到最有可能的模型参数。

线拟合过程（Line fitting）

1. 随机从数据中抽取少数点（例如，对于直线拟合，抽取2个点）
2. 找到线的参数（Line Parameters）
3. 计算内点数量（跟线拟合的点）

重复以上步骤直到达到最大迭代次数

最终的模型：拥有最高的 N 的模型

运行第一步：随机从数据中抽取少数点（例如，对于直线拟合，抽取2个点）

运行第二步：找到线的参数（Line Parameters）

运行第三步：计算内点数量（跟线拟合的点）

一直重复以上步骤，最后返回 $N_{inlier}$ 最大的模型

RANSAC 的参数

1. 迭代次数（Number of iterations）：应当足够多，保证在所有迭代中有高概率（如0.99）至少得到一个无离群点的样本。

   • 考虑因素：如果数据中离群点较多，需要增加迭代次数以获得良好的模型。

2. 内点阈值（Threshold for inliers）：设定一个距离阈值，确定哪些点与估计的模型足够接近，从而可以被视为内点。

   • 选择原则：即使在噪声的影响下，良好的数据点也应有高概率（如0.95）被认为是内点。

应用（Application）

问题：很多关键点，很多相似的特征 - 很可能出现错误匹配。

💡 为了更稳健的匹配，可以考虑使用比率（ratio），即最佳匹配的相似性与次佳匹配的相似性之比。

减少错误的匹配

匹配

全面匹配的问题：

• 使用穷举法进行特征匹配非常慢，其时间复杂度为O(m*n)。其中，m和n分别是两张图片中关键点的数量。

更高效的选择：

• 使用近似的最近邻方法。
• 这种方法更快，但可能无法找到最接近的匹配。
• 即使使用比率匹配，错误匹配的比例可能仍然很高。

第三步：使用RANSAC方法：

• 用RANSAC找到可以由某种变换模型解释的匹配子集。

变换（Transformations）

仿射变换（Affine transformation）

仿射变换是一种二维或三维空间中的线性变换，它保持了点、直线和平面之间的平行关系。这意味着平行的线在变换后仍然是平行的。常见的仿射变换包括平移（移动物体而不旋转或改变其大小）、缩放（增大或减小物体的大小）、旋转（围绕一个点旋转物体）和剪切（沿一个轴将物体斜切）等。通过组合这些基本变换，我们可以实现更复杂的空间变换效果。

射影变换（Projective transformation）

射影变换，也被称为单应性变换或透视变换，是图像处理和计算机视觉中的一种更为通用的变换。与仿射变换不同，射影变换不仅可以进行平移、缩放、旋转和剪切，还可以进行透视扭曲，使得物体在透视投影下看起来是真实的。射影变换在处理相机拍摄的真实场景图片时特别有用，因为相机通常会引入透视扭曲。简单地说，射影变换能够处理图像的深度和透视效果，使得远处的物体看起来更小，而近处的物体看起来更大。

仿射变换 Vs. 射影变换

仿射变换：

• 直线映射为直线。
• 平行线仍保持平行。
• 比例得以保持。

射影变换：

• 直线映射为直线。
• 平行线可能不再保持平行。
• 比例不再得以保持。

2D 平面变换（2D planar transformations）

需要多少点来定义一个射影变换

射影变换可以包括缩放（scaling）、旋转（rotation）、仿射位移（affine shift）和射影扭曲（warp）的任意组合。

一个点不足以识别任何变换

两个点 - 无法区分缩放（scaling）、位移（shift）和扭曲（warp）的不同组合

三个点 - 足够识别仅为仿射的变换。 但无法区分仅为仿射和射影变换

四个点 - 唯一的解决方案！

小结

• 使用RANSAC的特征匹配在不同的图片中找到匹配的关键点。

• 在不同的视图中找到匹配点，并计算关联这些点的变换。

• 应用：

  • 实例识别（Instance recognition）
  • 视频稳定化（Video stabilisation）
  • 全景图拼接（Panorama stitching）
  • 在图像中找到平面、消失点等（Finding planes, vanishing points, etc. in images）
  • 3D重建（3D reconstruction）