12.1 回环检测概述
前⾯已经介绍过了前端和后端，前端⽤于特征点的提取以及轨迹、地图的初始值，⽽后端负责对这部分数据进⾏优化。考虑到误差的存在，每⼀个时刻存在的误差会不断累积，从⽽产⽣累积误差的问题，使得长期的估计结果不可靠，或者说⽆法得到⼀个全局⼀致的轨迹和地图。
虽然后端能够估计最⼤后验误差，但所谓“好模型架不住烂数据”，只有相邻关键帧数据时，我们能做的事情并不很多，也⽆从消除累积误差。但是，回环检测模块，能够给出除了相邻帧之外的，⼀些时隔更加久远的约束，⽐如说第⼀帧和第⼀百帧之间的位姿变换。这个约束主要是因为相机能够察觉相机经过了同⼀个地⽅，⽽且采集到了相似的数据。
回环检测的关键就是如何有效地检测出相机经过了同⼀个地⽅这件事。如果检测到了回环，就可以为后端的优化提供更多的有效数据，从⽽得到⼀个更好的优化，特别是⼀个全局⼀致的估计，这样我们就可以把偏差根据检测到的回环点，“拉正”到⼀个合适的位置。
回环系统对于SLAM系统意义重⼤，它关系到我们估计的轨迹和地图在长时间下的正确性。⼀些情况下，我们将仅有前端和局部后端的系统称为VO，⽽将带有回环检测和全局后端的称为SLAM。
⼀般提到回环检测，最简单的思路就是将任意的两张图⽚都进⾏⼀遍特征匹配，根据正确匹配的数量来确定哪两个图像之间存在关联。这种思路的问题在于检测的数量实在是太⼤，对于实时系统来说不是很实⽤。另⼀种思路是随机抽取历史数据进⾏回环检测，这种做法能够维持常数时间的运算量，但是这种盲⽬试探⽅法在帧数增长时，抽到回环的⼏率⼜⼤幅下降，使得检测效率不⾼。
在实际情境下，⼤多数的回环检测都是依据下⾯的两个思路：基于⾥程计的⼏何关系和基于外观。
基于⾥程计是指当我们发现当前相机运动到了之前的某个位置附近时，检测它们有没有回环关系。这⾃然是⼀种直观的想法，但是由于累积误差的存在，我们往往没法正确地发现“运动到了之前的某个位置附近”这件事实，回环检测也⽆从谈起。也就是说，理想情况下，当我们根据⾥程计检测到运动回原点附近的时候，⾃然会出现回环，但是因为累积误差，⾥程计本⾝的结果就不⼀定准确，⾥程计回到原点，真实情况下可并不是这样，⾃然⽆法⽤其校正回环。
基于外观则与前端和后端的估计都⽆关，仅仅根据两张图像的相似性来确定回环检测关系，这种⽅式能够有效地在不同的场景下⼯作，所以已经成为了SLAM中的主流做法。
在基于外观的⽅式下，核⼼问题是如何计算图像之间的相似性。⼀般的思路是利⽤相似性评分，当评分⼤于⼀定值的时候认为产⽣了回环。但是我们并不能直接使⽤灰度值，也就是将两个图像的灰度值相减然后套个外壳。
这种⽅式的问题有两个。⾸先，灰度值不是⼀种稳定的测量值，它会受到环境光和相机曝光的影响。另⼀⽅⾯，当相机视⾓发⽣少量变化时，即使每个物体的光度不变，它们的像素也会在图像中发⽣位移，造成⼀个很⼤的差异值。
所以我们说，这个函数s不能很好的反映图像间的相似关系。这⾥牵涉到⼀个“好”和“不好”的定义问题。这⾥可以引出感知偏差和感知变异两个概念。根据回环检测的结果，我们可以产⽣下⾯四种结果：
这其实就是机器学习⾥⾯分类那部分的四种结果，只不过这⾥换了个说法。借⽤医学上的说法，将假阳性称为感知偏差，将假阴性称为感知变异。我们希望TP和TN要尽可能⾼，在此基础上引⼊了准确率和召回率：
从公式字⾯意义上来看，准确率描述的是，算法提取的所有回环中，确实是真实回环的概率，换句话说就是认为是真的判断只能怪有多少是正确的判断。⽽召回率则是说，在所有真实回环中，被正确检测出来的概率，也就是真实情况为真的个例中有多少被正确地判断出来了。这两个统计量本⾝是两个⽭盾。准确率⾼可以表现为只筛选“把握”⾼的个例，这意味着只有⼀⼩部分把握很⾼的个例才会被认为产⽣了回环，所以有⼤量把握不⼤但是真的是回环的帧被落下了，⾃然会导致召回率增⾼。反过来，召回率⾼可以通过将所有帧都看做回环来实现，这种情况下，召回率能达到100%，但是正确率会很低，因为将⼤量不是回环的帧认为是回环。
为了评价算法的好坏，我们会测试它在各种配置下的P和R值，然后做出⼀条Precision-Recall曲线。当⽤召回率为横轴，⽤准确率为纵轴时，我们会关⼼整条曲线偏向右上⽅的程度、100%准确率下的召回率，或者50%召回率时候的准确率，作为评价算法的指标。
lollipop fx在SLAM中，我们对准确率要求更⾼，所以在选择回环检测算法的时候，更加倾向于将参数设置地更
加严格，或者在检测之后加上回环验证的步骤。
12.2 词袋模型
365days两张图像直接相减的⽅法不好，我们完全可以借鉴VO的特征点⽅法。⼀种很类似的⽅法就这样出现了，即词袋模型。
词袋的⽬的是利⽤图上有哪⼏个特征来描述⼀个图像。⽐如说这个图上有⼀辆车⼀条狗，另⼀张图上有⼀匹马和⼀台电脑等。具体来说，我们将车、狗、马、电脑这种概念称为单词，许多单词组成了字典，这样可以根据⼀张图上有什么没有什么，将图像⽤⼀个向量来表⽰，通过向量和字典的⽐较，来表⽰相似程度。
上图就是对⼀张图的简单描述，字典中⼀共有w1w2w3三个特征，对于图⽚A来说，它只有w1和w2两个特征。
利⽤这种向量，来表⽰图像是否含有某类特征，⽐直接使⽤灰度值要准确的多。⼜因为描述向量说的是“是否出现”，⽽不管它们“在哪⼉出现”，所以与物体的空间位置和排列顺序⽆关，因此在相机发⽣少量运动时，只要物体仍在视野中出现，我们就仍然保证描述向量不发⽣变化。
基于这种向量的表⽰，我们可以描述相似性：
其中范数取 L1 范数，即各元素绝对值之和。请注意在两个向量完全⼀样时，我们将得到1；完全相反时（a为0的地⽅b为1）得到0。这样就定义了两个描述向量的相似性，也就定义了图像之间的相似程度。
12.3 字典
根据前⾯的介绍，字典是单词的集合，⼀个单词表⽰⼀个概念，但是⼀个单词并不能与⼀个单独的特征点划等号，它本⾝不是从图像上提取出来的，⽽是⼀类特征的组合，所以字典的⽣成就类似⼀个聚类问题。
假设我们对⼤量的图像提取了N个特征点，我们想⽤这些特征点，去构建⼀个⼤⼩为k的字典，我们的⽅法就是⽤典型的聚类算法Kmeans算法。
利⽤这种⽅法，我们提取到了字典需要的k个单词，现在问题是我们⼊⽿利⽤图像的特征点，去查字典中需要的单词。
⾸先，我们需要明确字典的⼤⼩，显然字典必须要够⼤，这是基于通⽤性的考虑，我们会使⽤⼀个较⼤规模的字典，去保证当前使⽤环境中的特征在字典中都有出现，不能出现“查⽆此词”的现象。所以查字典的过程就是⼀个⼤问题。对于这个问题，我们⼀般使⽤树结构去优化：
最简单的⽅法是⽤k叉树去表⽰：
最终我们仍在叶⼦层构建了单词，⽽树结构中的中间节点仅供快速查时使⽤。这样⼀个k分⽀，深度为d的树，可以容纳k^d个单词。另⼀⽅⾯，在查某个给定特征对应的单词时，只需将它与每个中间结点的聚类中⼼⽐较（⼀共d次），即可到最后的单词，保证了对数级别的查效率。
12.4 相似度计算
有了字典，我们现在对于任何⼀个给定的特征，就可以在字典树⾥⾯查，从⽽得到⼀个对应的单词。这种⽅法的缺点在于，我们对所有的单词都是⼀视同仁的，⽽对于⼀些重要性不同的特征，这种⼀视同仁是及其不公平的。
对于这个问题，我们借鉴⽂本检索中的TF-IDF思想。TF部分的思想是，某单词在⼀个图像中经常出现，它的区分度就⾼。另⼀⽅⾯，IDF的思想是，某单词在字典中出现的频率越低，则分类图像时区分度越⾼。
在词袋模型中，在建⽴字典时可以考虑 IDF 部分。我们统计某个叶⼦节点wi中的特征数量相对于所有特征数量的⽐例，作为IDF部分。假设所有特征数量为n，wi数量为ni，那么该单词的IDF为：
runaway train
欧美歌曲另⼀⽅⾯，TF部分则是指某个特征在单个图像中出现的频率。假设图像A中，单词wi出现了ni次，⽽⼀共出现的单词次数为n，那么TF为：
于是wi的权重等于TF乘IDF之积：
考虑权重以后，对于某个图像A，它的特征点可对应到许多个单词，组成它的词袋就变成下⾯的形式：
这种情况下，差异的计算也会发⽣变化：
12.5 实验分析与评述
多少爱都不要
在SLAM中，我们经常会怀疑是不是字典选择太⼩了。具体来说，当字典规模增加时，⽆关图像的相似性明显变⼩了。⽽相似的图像，虽然分值也略微下降，但相对于其他图像的评分，却变得更为显著了。这说明增加字典训练样本是有益的。
对于⼀些相似度本⾝很⼤的场景，⽐如楼道，利⽤相似性评分的分值的绝对⼤⼩，并不会有很⼤的帮助，这时我们⼀般采⽤⼀个先验相似度，去表⽰某时刻关键帧图像与上⼀个时刻的关键帧的相似性，然后利⽤这个值去对剩下的分值做⼀个归⼀化：
乐谱下载站在这个⾓度上，我们说：如果当前帧与之前某关键帧的相似度，超过当前帧与上⼀个关键帧相似度的3倍，就认为可能存在回环。这个步骤避免了引⼊绝对的相似性阈值，使得算法能够适应更多的环境。
对于回环检测使⽤的帧，从实践上说，⽤于回环检测的帧最好是稀疏⼀些，彼此之间不太相同，⼜能涵盖整个环境。但是对于已经检测到回环的情况，假设是第1帧和第n帧，这两帧检测到了回环，对于优化是有帮助的，但接下去的n+1和n+2都会产⽣回环，产⽣的帮助就没那么⼤了，甚⾄有些多余，这种情况下，我们会把“相近”的回环聚成⼀类，使算法不要反复地检测同⼀类的回环。
词袋的回环检测算法完全依赖于外观⽽没有利⽤任何的⼏何信息，这导致外观相似的图像容易被当成回环。并且，由于词袋不在乎单词顺序，只在意单词有⽆的表达⽅式，更容易引发感知偏差。验证的⽅法有很多。其⼀是设⽴回环的缓存机制，认为单次检测到的回环并不⾜以构成良好的约束，⽽在⼀段时间中⼀直检测到的回环，才认为是正确的回环。这可以看成时间上的⼀致性检测。另⼀⽅法是空间上的⼀致性检测，即是对回环检测到的两个帧进⾏特征匹配，估计相机的运动。然后，再把运动放到之前的位姿图中，检查与之前的估计是否有很⼤的出⼊。总之，验证部分通常是必须的，但如何实现却有很多种⽅法。
发布评论