酸菜鱼的SLAM之旅（4）

2019年3月27日：视觉里程计 - 特征点法

keyword：图像特征点、极几何、PNP问题、ICP问题、三角化

特征点法

视觉SLAM主要分为视觉前端和优化后端，前端也称为视觉里程计（VO）。它根据相邻图像的信息，估计出粗略的相机运动，给后端提供较好的初始值。

• 按照是否需要提取特征区分VO的实现方法:
  • 需要提取特征：特征点法的前端（主流方法)
    • 运行稳定
    • 对光照、动态物体不敏感
  • 不提取特征：直接法前端

特征点

VO的主要问题是如何根据图像来估计相机运动。由于图像本身是一个由亮度和色度组成的矩阵，因此很难直接从矩阵层面考虑运动估计。因此，常见做法如下:

1. 从图像中选取比较有代表性的点，主要体现在这些点在相机视角发生少量变化后保持不变，即我们在连续的各个图像中都能找到相同的点。
2. 在这些点的基础上讨论相机的位姿估计问题和这些点的定位问题。
3. 在经典SLAM模型中，这些有代表性的点称为路标；在视觉SLAM中，路标则是指图像特征（Features）。

图像特征是一组与计算任务相关的信息，计算任务取决于具体的应用。 —— 维基百科

• 特征是图像信息的另一种数字表达形式（如单个图像像素也是一种“特征”)
• 在OV中，希望特征点在相机运动之后保持稳定。而灰度值（像素)受外界因素影响严重，在不同图像之间变化很大。因此我们需要对图像提取特征点（图像里一些特别的地方）。
• 特征点：从不同的图像间存在更强的辨识度，如角点。一种直观的提取特征的方式就是在不同图像间辨认角点（不满足视觉SLAM的需求），确定它们的对应关系。在这种做法中，角点就是所谓的特征。

---

CV中设计了比角点更稳定的局部图像特征，需要拥有以下特性：

1. 可重复性（Repeatability）：相同的“区域”可以在不同的图像中被找到。
2. 可区别性（Distinctiveness）：不同的“区域”有不同的表达。
3. 高效率（Efficiency）：同一图像中，特征点的数量应远小于像素的数量。
4. 本地性（Locality）：特征仅与一小片图像区域相关。

e.g. SIFT[30], SURF[31], ORB[32]

---

特征点由关键点（Key-point）和描述子（Descriptor）两部分组成。比方说，当我们
谈论 SIFT 特征时，是指“提取 SIFT 关键点，并计算 SIFT 描述子”两件事情。

具体结构如下:

• 特征点：
  • 关键点 (Key-point)：该特征点在图像里的位置，可能包括朝向、大小等信息
  • 描述子 (Descriptor)：按照某种人为设计的方式描述该关键点周围像素的信息。
    • 原则：外观相似的特征应该有相似的描述子
    • 两个特征点的描述子在向量空间上的距离相近，就可以认为它们是同样的特征点

一些图像特征：

• 尺度不变特征转换(SIFT)
  • Scale-invariant feature transform
  • 是一种机器视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变数。
  • 它充分考虑了在图像变换过程中出现的光照，尺度，旋转等变化，但随之而来的是极大的计算量。
  • 普通PC的CPU还无法实时地计算SIFT特征，进行定位与建图。所以在SLAM中我们甚少使用这种“奢侈”的图像特征。
  • 通过GPU加速的SIFT可以满足实时计算要求，但成本提升。

---

• FAST关键点
  • 属于计算特别快的一种特征点
  • 没有描述子，因此不具有方向性

---

• ORB特征
  • Oriented FAST and Rotated BRIEF
  • 非常具有代表性的实时图像特征，对于实时性要求很高的SLAM来说是一个很好的选择。
  • 它改进了FAST 检测子[33] 不具有方向性的问题，并采用速度极快的二进制描述子BRIEF，使整个图像特征提取的环节大大加速。
  • 保持了特征子具有旋转、尺度不变性的同时，速度方面提升明显，是质量与性能之间较号的折中。

ORB特征

ORB特征的结构如下:

• ORB特征

  • 关键点：Oriented FAST， 是一种改进的Fast角点

  • 描述子：BRIEF（Binary Robust Independent Elementary Features）

提取ORB 特征分为两个步骤：

1. FAST 角点提取：找出图像中的” 角点”。相较于原版的FAST, ORB 中计算了特征点的主方向，为后续的BRIEF 描述子增加了旋转不变特性。
2. BRIEF 描述子：对前一步提取出特征点的周围图像区域进行描述。

FAST特征点：

(图中显示的就是检测一个像素点P是否FAST点的过程）

FAST是一种角点：

• 思想：如果一个像素与它的邻域的像素差别过大（过亮/过暗），那么它更可能是角点
• 方法：主要检测局部像素灰度变化明显的地方
• 优势：只需要比较像素亮度的大小，速度快
• 测试过程前可以进行预测试操作，快速排除绝大多数不是角点的元素：
  • 对于每个像素，直接检测邻域圆上的第1，5，9，13 个像素的亮度。只有当这四个像素中有三个同时大于Ip + T 或小于Ip - T 时，当前像素才有可能是一个角点，否则应该直接排除。
• 正常检测过程:
  1. 在图像中选取像素p，假设它的亮度为Ip。
  2. 设置一个阈值T(比如Ip 的20%)。
  3. 以像素p为中心, 选取半径为3的圆上的16 个像素点。
  4. 假如选取的圆上，有连续的N个点的亮度大于Ip + T 或小于Ip - T，那么像素p可以被认为是特征点(N 通常取12，即为FAST-12。其它常用的N取值为9和11，他们分别被称为FAST-9，FAST-11)。
  5. 循环以上四步，对每一个像素执行相同的操作。
• FAST角点的一些原始问题:
  • 原始Fast角点经常出现“扎堆”现象，即同一片区域出现多个角点，因此需要使用非极大值抑制（Non-maximal suppression），在一定区域内仅保留响应极大值的角点，避免角点集中的问题。
  • FAST特征点数量很大且不确定
  • FAST角点不具有方向信息
  • 固定取半径为3的圆，存在尺度问题：远处看着像是角点的地方，接近后看可能就不是角点了
• ORB对原始FAST算法的改进
  • 先指定最终要提取的角点数量N，对原始FAST角点分别计算Harris响应值，然后选取前N个具有最大响应值的角点，作为最终的角点集合。
  • ORB 添加了尺度和旋转的描述。尺度不变性由构建图像金字塔，并在金字塔的每一层上检测角点来实现。

---

BRIEF 描述子

BRIEF 是一种二进制描述子，它的描述向量由许多个 0 和 1 组成，这里的 0 和 1 编码了关键点附近两个像素（比如说 p 和q ）的大小关系：如果 p 比 q 大，则取1，反之就取0。如果我们取了128个这样的p，q，最后就得到128维由 0，1 组成的向量。

• BRIEF使用了随机选点比较，速度快
• 使用二进制表达，存储方便，适用于实时的图像匹配
• 原始的BIRIEF描述子不具有旋转不变性，在图像发生旋转时容易丢失
• ORB在FAST特征点提取阶段计算了关键点的方向，所以可以利用方向信息，计算旋转之后的“steer BRIEF”特征，使得ORB的描述子具有较好的旋转不变性

特征匹配

宽泛地说，特征匹配解决了SLAM中的数据关联问题（data association），即确定当前看到的路标与之前看到的路标之间的对应关系。

考虑两个时刻的图像的匹配问题：

1. 从两幅图像中分别提取到特征点的集合
2. 寻找这两个集合元素的对应关系，即特征匹配
   • 暴力匹配（Brute-Force Matcher）：对于集合A中的所有元素，依次与集合B中的所有元素进行遍历测量描述子的距离（表示了两个特征点之间的相似程度），排序，选择最近的一个作为匹配点。
     • 浮点类型的描述子：使用欧式距离
     • 二进制的描述子:使用汉明距离（两个二进制串之间不同位数的个数）
   • 快速近似最优邻算法（FLANN）
     • 适合匹配点数量极多的情况（暴匹运算量太大）

实践

• 待填

2D-2D:对极几何

对极约束

代数角度解释几何关系的过程：

本质矩阵（E，Essential Matrix）

求解方法略

基础矩阵（F，Fundamental Matrix）

求解方法略

单应矩阵（H，Homography Matrix）

除了基本矩阵和本质矩阵，我们还有一种称为单应矩阵（Homography）H 的东西，它描述了两个平面之间的映射关系。若场景中的特征点都落在同一平面上（比如墙，地面等），则可以通过单应性来进行运动估计。这种情况在无人机携带的俯视相机，或扫地机携带的顶视相机中比较常见。单应矩阵通常描述处于共同平面上的一些点，在两张图像之间的变换关系。

单应性在SLAM 中具重要意义。当特征点共面，或者相机发生纯旋转的时候，基础矩阵的自由度下降，这就出现了所谓的退化（degenerate）。现实中的数据总包含一些噪声，这时候如果我们继续使用八点法求解基础矩阵，基础矩阵多余出来的自由度将会主要由噪声决定。为了能够避免退化现象造成的影响，通常我们会同时估计基础矩阵F和单应矩阵H，选择重投影误差比较小的那个作为最终的运动估计矩阵。

实践：通过Essential矩阵求解相机运动

• 待填

程序输出分解得到R，t的四种可能，并使用三角检测角点的深度是否为正选出正确的解。

（R，t）即从第一个图到第二个图的坐标变换矩阵的参数。

• E（本质矩阵)本身具有尺度等价性，认为分解得到的t，R也有尺度等价性。认为t具有一个尺度。通常对t进行归一化，使它的长度等于1。
• 对t的长度的归一化导致了单目视觉的尺度不确定性（Scale Ambiguity)
• 在单目视觉中，对两张图像的t归一化，相当于固定了尺度，但不知道实际长度为多少，以此时的t为单位1。这称为单目SLAM的初始化。
• 除了对t进行归一化之外，另一种方法是令初始化时所有的特征点平均深度为1，也可以固定一个尺度。
• 单目初始化不能只有纯旋转，必须要有一定程度的平移。如果没有平移，单目将无法初始化。在实践当中，如果初始化时平移太小，会使得位姿求解与三角化结果不稳定，从而导致失败。相对的，如果把相机左右移动而不是原地旋转，就容易让单目SLAM 初始化。因而有经验的SLAM 研究人员，在单目SLAM 情况下，经常选择让相机进行左右平移以顺利地进行初始化。
• 给定的点数多于8对时，计算最小二乘解。当可能存在误匹配的情况时，我们会更倾向于使用随机采样一致性（Random Sample Concensus, RANSAC）来求，而不是最小二乘。
  • RANSAC 是一种通用的做法，适用于很多带错误数据的情况，可以处理带有错误匹配的数据。

三角测量（三角化）

三角测量是指，通过在两处观察同一个点的夹角，确定该点的距离。在SLAM中，我们主要用三角化来估计像素点的距离。

三角测量由平移得到，纯旋转无法使用三角测量。

3D-2D：PnP

PnP（Perspective-n-Point）是求解3D 到2D 点对运动的方法。它描述了当我们知道 n 个3D空间点以及它们的投影位置时，如何估计相机所在的位姿。

求解方法:（跳过了）

• P3P:用三对点估计位姿
• DLT：直接线性变换
• EPnp（Efficient PnP）
• UPnP
• BA、非线性优化：构建最小二乘问题并迭代求解（Bundle Adjustment）

3D-3D：ICP

这个问题可以用迭代最近点（Iterative Closest Point, ICP）求解。读者应该注意到，3D-3D 位姿估计问题中，并没有出现相机模型，也就是说，仅考虑两组3D点之间的变换时，和相机并没有关系。

求解方法：

• SVD方法
• 非线性优化方法（类似于BA）

特征点法的缺点：

1. 关键点的提取与描述子的计算非常耗时。实践当中，SIFT目前在CPU 上是无法实时计算的，而ORB也需要近20毫秒的计算。如果整个SLAM 以30毫秒/帧的速度运行，那么一大半时间都花在计算特征点上。
2. 使用特征点时，忽略了除特征点以外的所有信息。一张图像有几十万个像素，而特征点只有几百个。只使用特征点丢弃了大部分可能有用的图像信息。
3. 相机有时会运动到特征缺失的地方，往往这些地方没有明显的纹理信息。例如，有时我们会面对一堵白墙，或者一个空荡荡的走廓。这些场景下特征点数量会明显减少，我们可能找不到足够的匹配点来计算相机运动。