SLAM入门之回环检测

12 回环检测

12.1 回环检测概述

• 意义

  • 前端提供特征点的提取和轨迹、地图的初值，而后端负责对这所有的数据进行优化。然而，如果像 VO 那样仅考虑相邻时间上的关联，那么，之前产生的误差将不可避免地累计到下一个时刻，使得整个 SLAM 会出现累积误差
  • 回环检测模块能够给出除了相邻帧之外的，一些时隔更加久远的约束，如 $x_1 − x_{100}$x1​−x100​ 之间的位姿变换。之所以它们之间会有约束是因为我们察觉到相机经过了同一个地方， 采集到了相似的数据。而回环检测的关键，就是如何有效地检测出相机经过同一个地方这件事。如果我们能够成功地检测这件事，就可以为后端的 Pose Graph 提供更多的有效数据，使之得到更好的估计，特别是得到一个全局一致（Global Consistent）的估计。
  • 回环检测一方面关系到我们估计的轨迹和地图在长时间下的正确性。另一方面，由于回环检测提供了当前数据与所有历史数据的关联，在跟踪算法丢失之后，我们还可以利用回环检测进行重定位。因此，回环检测对整个 SLAM 系统精度与鲁棒性的提升是非常明显的。

• 方法

  • 最简单的方式就是对任意两张图像都做一遍特征匹配，根据正确匹配的数量确定哪两个图像存在关联：缺点在于，我们盲目地假设了“任意两个图像都可能存在回环”，使得要检测的数量实在太大在大多数实时系统当中是不实用的
  • 另一种朴素的方式是随机抽取历史数据并进行回环检测，比如说在n 帧当中随机抽 5 帧与当前帧比较。这种做法能够维持常数时间的运算量，但是这种盲目试探方法在帧数 N 增长时，抽到回环的几率又大幅下降，使得检测效率不高。
  • 我们至少希望有一个“哪处可能出现回环”的预计，才好不那么盲目地去检测。这样的方式大体分为两种思路：基于里程计的几何关系（Odometry based），或基于外观（Appearance based）。基于几何关系的做法假设了“相机回到之前位置附近”，才能检测回环有倒果为因的嫌疑。基于外观的方法仅根据两张图像的相似性确定回环检测关系。这种做法摆脱了前后端数据和估计的累计误差，使回环检测模块成为 SLAM 系统中一个相对独立的模块（当然前端可以为它提供特征点），成为了视觉 SLAM 中主流的做法。
  • 核心问题是如何计算图像间的相似性。比如对于图像 $A$A 和图像 $B$B，我们要设计一种方法，计算它们之间的相似性评分：$s(A，B)$s(A，B)。这个评分会在某个区间内取值，当它大于一定量后我们认为出现了一个回环。
  • 直接让两个图像相减$s(A，B) = ||A-B||$s(A，B)=∣∣A−B∣∣，然后取某种范数行不行呢？像素灰度是一种不稳定的测量值，它严重受环境光照和相机曝光的影响。当相机视角发生少量变化时，即使每个物体的光度不变，它们的像素也会在图像中发生位移。这个函数不能很好的反映图像间的相似关系。

• 相似关系的评价：

1. 回环检测的结果分类
   假阳性又称为感知偏差，假阴性称为感知变异。记缩写 TP 为 True Positive

算法 \ 事实	是回环	不是回环
是回环	真阳性（True Positive）TP	假阳性（False Positive）FP
不是回环	假阴性（False Negative）FN	真阴性（True Negative）TN

• 准确率和召回率
  • 由于我们希望算法和人类的判断一致，所以希望 TP 和 TN 要尽量的高，而 FP和 FN 要尽可能的低。所以，对于某种特定算法，我们可以统计它在某个数据集上的 TP、TN、 FP、 FN 的出现次数，并计算两个统计量： 准确率（Precision) 和召回率 (Recall）。
    Precision = $TP/(TP + FP)$TP/(TP+FP)， Recall = $TP/(TP + F N)$TP/(TP+FN)
    准确率：算法提取的所有回环中，确实是真实回环的概率。
    召回率：在所有真实回环中，被正确检测出来的概率。
  • 准确率和召回率通常来说是一个矛盾。一个算法往往有许多的设置参数。当我们提高某个阈值时，算法可能变得更加“严格”，检出更少的回环，使准确率得以提高。但同时，由于检出的数量变少了，许多原本是回环的地方就可能被漏掉了，导致召回率的下降。反之，如果我们选择更加宽松的配置，那么检出的回环数量将增加，得到更高的召回率，但其中可能混杂了一些不是回环的情况，于是准确率下降了。
  • 为了评价算法的好坏，我们会测试它在各种配置下的 P 和 R 值，然后做出一条Precision-Recall 曲线
  • 在 SLAM 中，我们对准确率要求更高，而对召回率则相对宽容一些。假阳性的（检测结果是而实际不是的）回环将在后端的 Pose Graph 中添加根本错误的边，有些时候会导致优化算法给出完全错误的结果。召回率低一些，则顶多有部分的回环没有被检测到，地图可能受一些累积误差的影响——然而仅需一两次回环就可以完全消除它们了。

12.2 词袋模型

词袋，也就是 Bag-of-Words（BoW），目的是用“图像上有哪几种特征”来描述一个图像。

• 如果某个照片，我们说里面有一个人、一辆车，而另一张则有两个人、一只狗。根据这样的描述，可以度量这两个图像的相似性。再具体一些，我们要做以下几件事：

  1. 确定“人、车、狗”等概念——对应于 BoW 中的“单词”（Word），许多单词放在一起，组成了“字典”（Dictionary）。
  2. 确定一张图像中，出现了哪些在字典中定义的概念——我们用单词出现的情况（或直方图）描述整张图像。这就把一个图像转换成了一个向量的描述。
  3. 比较上一步中的描述的相似程度。

• 例如：首先通过某种方式得到了一本“字典”。字典上记录了许多单词，例如“人”、“车”、“狗”都是记录在字典中的单词，记为 $w_1,w_2, w_3$w1​,w2​,w3​。然后，对于任意图像 A，根据它们含有的单词，可记为：$A = 1\cdot w_1+1\cdot w_2+0\cdot w_3$A=1⋅w1​+1⋅w2​+0⋅w3​ 字典是固定的，所以只要用 $[1,1,0]^T$[1,1,0]T 这个向量就可以表达 A 的意义。

• 向量描述的是“图像是否含有某类特征”的信息，比单纯的灰度值更加稳定。又因为描述向量说的是“是否出现”，而不管它们“在哪儿出现”，所以与物体的空间位置和排列顺序无关，因此在相机发生少量运动时，只要物体仍在视野中出现，就仍然保证描述向量不发生变化。强调的是 Words 的有无，而无关其顺序。

• 根据两个向量，设计一定的计算方式，就能确定图像间的相似性了，如：$s(a,b) = 1-\frac{1}{W}||a-b||_1$s(a,b)=1−W1​∣∣a−b∣∣1​
  其中范数取 L1 范数，即各元素绝对值之和。请注意在两个向量完全一样时，我们将得到 1，完全相反时（a 为 0 的地方 b 为 1）得到 0。这样就定义了两个描述向量的相似性，也就定义了图像之间的相似程度

12.3 字典

12.3.1 字典结构

• 字典由很多单词组成，而每一个单词代表了一个概念。一个单词与一个单独的特征点不同，它不是从单个图像上提取出来的，而是某一类特征的组合。所以，字典生成问题类似于一个聚类（Clustering）问题
• 聚类问题是无监督机器学习中一个特别常见的问题，用于让机器自行寻找数据中的规律的问题。当我们有 N 个数据，想要归成 k 个类，可用 K-means 来做

K-means（K 均值）算法

1. 随机选取 k 个中心点： $c_1,\ldots ,c_k$c1​,…,ck​;
2. 对每一个样本，计算与每个中心点之间的距离，取最小的作为它的归类；
3. 重新计算每个类的中心点。
4. 如果每个中心点都变化很小，则算法收敛，退出；否则返回 1。

• k 叉树字典：类似于层次聚类，是 k-means 的直接扩展。假定我们有 N 个特征点，希望构建一个深度为 d，每次分叉为 k 的树，那么做法如下：

1. 在根节点，用 k-means 把所有样本聚成 k 类（实际中为保证聚类均匀性会使用k-means++）。这样得到了第一层。
2. 对第一层的每个节点，把属于该节点的样本再聚成 k 类，得到下一层。
3. 依此类推，最后得到叶子层。叶子层即为所谓的 Words。

12.4 相似度计算

• 利用DBoW3 可以生成字典，有了字典之后，给定任意特征 $f_i$fi​，只要在字典树中逐层查找，最后都能找到与之对应的单词 $w_j$wj​。这种做法中，我们对所有单词都是“一视同仁”的——有就是有，没有就是没有。
• 不同的单词在区分性上的重要性并不相同，我们希望对单词的区分性或重要性加以评估，给它们不同的权值以起到更好的效果。
• 在文本检索中，常用的一种做法称为 TF-IDF（Term Frequency– Inverse Document Frequency），或译频率-逆文档频率。
  TF 部分的思想是，某单词在一个图像中经常出现，它的区分度就高。
  IDF 的思想是，某单词在字典中出现的频率越低，则分类图像时区分度越高。
  一个是单词在图像中的频率，一个是在字典中频率。
• 词袋模型的第二步依据字典用单词出现的情况描述图像
  • （在建立字典时可以考虑 ）统计某个叶子节点 $w_i$wi​ 中的特征数量 $n_i$ni​ 相对于所有特征数量 $n$n 的比例，作为 IDF 部分： $\text{IDF}_i = \log\dfrac{n}{n_i}$IDFi​=logni​n​
  • TF 部分则是指某个特征在单个图像中出现的频率。假设图像 A 中，单词 $w_i$wi​ 出现了 $n_i$ni​ 次，而一共出现的单词次数为 $n$n，那么 TF 为：$\text{TF}_i = \dfrac{n_i}{n}$TFi​=nni​​
  • $w_i$wi​ 的权重等于 TF 乘 IDF 之积： $\eta_i = \text{TF}_i×\text{IDF}_i$ηi​=TFi​×IDFi​
  • 考虑权重以后，图像 A的特征点可对应到许多个单词，组成它的 Bag-ofWords：$A = \{ (w_1,\eta_1),(w_2,\eta_2),\ldots(w_N,\eta_N)\} \triangleq \pmb{v}_A$A={(w1​,η1​),(w2​,η2​),…(wN​,ηN​)}≜vvvA​
  • 用单个向量 $\pmb{v}_A$vvvA​ 描述了一个图像 A。由于相似的特征可能落到同一个类中，因此实际的 $\pmb{v}_A$vvvA​ 中会存在大量的零。这个向量 $\pmb{v}_A$vvvA​ 是一个稀疏的向量，它的非零部分指示出图像 A 中含有哪些单词，而这些部分的值为 TF-IDF 的值
  • 给定 $\pmb{v}_A$vvvA​ 和 $\pmb{v}_B$vvvB​，如何计算它们的差异呢？如$s(\pmb{v}_A-\pmb{v}_B) = 2\sum_{i=1}^N |\pmb{v}_{Ai}|+|\pmb{v}_{Bi}|-|\pmb{v}_{Ai}-\pmb{v}_{Bi}|$s(vvvA​−vvvB​)=2∑i=1N​∣vvvAi​∣+∣vvvBi​∣−∣vvvAi​−vvvBi​∣

12.5 分析与评述

• 增加字典规模
  当字典规模增加时，无关图像的相似性明显变小了。而相似的图像，例如图像 1 和 10，虽然分值也略微下降，但相对于其他图像的评分，却变得更为显著了。这说明增加字典训练样本是有益的。

• 相似性评分的处理

  • 有些环境的外观本来就很相似，像办公室往往有很多同款式的桌椅；另一些环境则各个地方都有很大的不同。考虑到这种情况，我们会取一个先验相似度 $s (v_t, v_{t−∆_t})$s(vt​,vt−∆t​​)，它表示某时刻关键帧图像与上一时刻的关键帧的相似性。然后，其他的分值都参照这个值进行归一化：$s (v_t, v_{t_j})' = s (v_t, v_{t_j})/ s (v_t, v_{t−∆_t})$s(vt​,vtj​​)′=s(vt​,vtj​​)/s(vt​,vt−∆t​​)
  • 如果当前帧与之前某关键帧的相似度，超过当前帧与上一个关键帧相似度的 3 倍，就认为可能存在回环。这个步骤避免了引入绝对的相似性阈值，使得算法能够适应更多的环境

• 关键帧的处理

  • 用于回环检测的帧最好是稀疏一些，彼此之间不太相同，又能涵盖整个环境。
  • “相近”的回环聚成一类，使算法不要反复地检测同一类的回环。

• 检测之后的验证

  • 外观相似的图像容易被当成回环，且由于词袋不在乎单词顺序容易引发感知偏差。验证部分通常是必须的
  • 验证的方法，如：其一是设立回环的缓存机制，认为单次检测到的回环并不足以构成良好的约束，而在一段时间中一直检测到的回环，才认为是正确的回环。这可以看成时间上的一致性检测。
  • 另一方法是空间上的一致性检测，即是对回环检测到的两个帧进行特征匹配，估计相机的运动。然后，再把运动放到之前的 Pose Graph 中，检查与之前的估计是否有很大的出入

• 与机器学习的关系

  • 回环检测本身非常像是一个分类问题。回环检测也相当于对“图像间相似性”概念的一个学习。
  • 从词袋模型来说，它本身是一个非监督的机器学习过程——构建词典相当于对特征描述子进行聚类，而树只是对所聚的类的一个快速查找的数据结构而已。
  1. 是否能对机器学习的图像特征进行聚类，而不是 SURF、 ORB 这样的人工设计特征
     进行聚类？
  2. 是否有更好的方式进行聚类，而不是用树结构加上 K-means 这些较朴素的方式？
  • 结合目前机器学习的发展，二进制描述子的学习和无监督的聚类，都是很有望在深度学习框架中得以解决的问题。陆续有利用机器学习进行回环检测的工作。尽管目前词袋方法仍是主流，但深度学习方法很有希望打败这些人工设计特征的，“传统”的机器学习方法 。毕竟词袋方法在物体识别问题上已经明显不如神经网络了，而回环检测又是非常相似的一个问题