第二部分讲解特征匹配、鲁棒性和应用。主要是视觉里程计中的各种点特征检测和离群点去除算法。特别重点讲解了随机采样一致性算法（RANSAC）和加快运算速度的策略。其他的议题包括，误差模型构建、回环检测（或位置识别）、和捆集调整。开源代码可以从网上下载。本文数学符号和公式在第一部分已经提到，这里就不重复了。
有两种方法可以查找特征点和它们的对应关系。第一种是查找一张图像上的特征，用局部查询方法在后面的图像中跟踪这些特征，比如相关分析。第二种是单独检测所有图像中的特征，基于相似特征匹配它们的特征描述子。当图像的拍摄视角非常相近时，前一种方法更适合；当运动幅度较大或视角变换大时，后一种方法更合适。视觉里程计早期的研究多采用前一种方法，如论文2-5，最近10年的研究工作更倾向于后一种方法，如论文1,6-9。主要由于早期的研究工作主要是小场景环境，图像拍摄的角度较小，最近几十年的研究主要集中在大场景环境下，图像拍摄尽可能大同时限制运动偏移相关问题。
在特征检测的过程中，需要搜索图像的显著特征点，这样可以在其他图像上进行良好的匹配。局部特征是一种图像模式，它能从相邻的图像中从亮度，颜色和纹理方面进行区别。对视觉里程计，点云检测，比如角点或圆斑，非常重要，因为它们在图像中的位置可以精确测量。
两个或多个边缘相交的点就是角点。斑点通过亮度，颜色和纹理比较来区别它和邻近的图像模式。它不是边缘也不是角点。优秀的特征检测应该具有以下特征：定位精准（包括位置和尺度），可重复（比如，大量的特征可以在下一幅图像中被再次检测到），计算效率高，鲁棒（对噪声，压缩损伤，图像模糊），具有特殊性（这样特征可以在不同的图像间精确匹配），不变性【对光度测量方面（比如亮度）和几何上的变化【旋转，尺度（缩放），透视变形】】。
视觉里程计采用各种点特征检测器，比如，角点检测（如Harris，Shi-Tomasi，FAST）和斑点检测（SIFT，SURF和CENSURE）。对这些检测方法的概述如论文17分析所示。每种检测方法都有自己的优势和劣势。角点检测计算速度更快，但特征更少；但斑点检测特征更多，计算速度较慢。另外，角点检测在图像内位置的定位更好，但在尺度上的定位稍差。这意味着角点不能像斑点那样在尺度和视图大幅变化情况下，经常重复检测。但在某些环境中斑点并非总是正确的选择，例如SIFT会自动忽略角点，但在城市环境中这些角点非常丰富。基于这些原因，选择合适的特征检测，应该仔细考虑如下问题：计算资源，实时性要求，环境类型和运动状况（比如，相邻图像之间的远近距离）。图1是不同焦点和斑点特征检测的特点和性能对比。SIFT，SURF和CENSURE不是仿射不变检测器，但对视角变换具有不变性。论文18和论文9,19分别评估了室内和室外的特征检测和特征描述。
图1 Comparison of feature detectors: properties and performance.
每个特征检测都有两个阶段组成。先用特征响应函数处理整个图像【比如哈尔斯检测中的角点响应函数或者SIFT中的高斯差分DoG（difference-of-Gaussian）操作符】。然后，用非极大值抑制算法处理第一步输出的结果。目的就是为了识别特征响应函数的局部最小值（或最大值）。非极大值抑制算法输出的结果表示的是检测出来的特征。为了使检测对尺度变换不变的方法是在同一图像的小尺度和大尺度上使用检测器，如图2（a）。透视变换的不变性可以估计仿射变换中的透视扭曲获得。
SIFT特征最开始是用于物体和位置识别，对视觉里程计的效果也非常好。SIFT检测器用高斯差分操作处理图像的高尺度和低尺度，然后获取尺度和空间上的输出的局部最大或最小值（如图2）。SIFT的优势是鲁棒的描述子，后面会详细介绍。SURF是建立在SIFT基础之上的，但是用盒子滤波去近似高斯操作，相比SIFT计算速度更快，可以用积分图像获得。
图2. 原始图像（a,左边）用4个不同sigmas值的高斯滤波平滑处理，
可以重复降采样2层处理图像。最后，
（b）DoG 高斯差分图像可以用两个连续的不同的高斯平滑图像计算得到。
SIFT特征是DoG高斯差分图像尺度和空间上的局部最小或最大值。
在特征描述阶段中，每个特征邻域会转化成精简的描述子用于匹配，而不是其他的描述子来匹配。最简单的特征描述子是贴图外观，也就是特征点附近区域的像素亮度。在这里，误差的度量，比如SSD差值平方和或NCC归一化互相关分析可以用于比较亮度。与SSD相比，NCC对轻微亮度改变的补偿更好。一种更鲁棒的图像相似度测量方法是非参数变换，可以将每个图像区块转换成二进制向量表示，其中向量邻居的亮度值高于或低于中心像素的亮度。区域的相似度就可以通过汉明距离计算。
在很多例子中，特征的局部贴图外观并不是携带特征信息得最好的描述子，因为外观可能会随着方向，尺度和视角变化。实际上，SSD和NCC并不是对任意变化都不变，因此它的应用只局限于特征位置附近。点特征最流行的描述子是SIFT。SIFT描述子基本上是局部梯度方向的直方图。特征附近的区域被分解成一个4x4的网格。每个象限中，构建包含8个梯度方向的直方图。所有这些直方图联系在一起形成一个含有128个元素的描述向量。为了减小光照变化的影响，描述子会归一化成单位长度。
图3 SIFT特征方向和尺度
SIFT描述子对光照，旋转，尺度变换，甚至到60o的变化比较稳定。SIFT特征的例子如图3所示。显示了每个特征的方向和尺度。SIFT描述子通常可以计算角点特征和斑点特征;但性能在计算角点特征时会降低，因为，角点的定义是边缘的交点。因此，描述子不如斑点那么明显，依赖于图像纹理明显的区域。
2010-2011年，发明了3个新的描述子，比SIFT和SURF计算速度快。一个简单的二值描述子BRIEF比较流行：它用关键点附近的区块采样的亮度对比。除了提取和对比速度非常快之外，对旋转和尺度变化性能非常好。由于BRIEF的成功，开发了ORB，处理方向不变性，优化了亮度值比值的取样算法。与此同时，基于FAST的BRISK关键点检测器，对尺度和旋转不变，其二值描述子可以配置采样模式。
图4 SIFT特征跟踪
特征匹配在另外一幅图像上搜索对应的特征。图4显示了在第一幅图像上的特征在多个帧上SIFT特征匹配。对应同一特征的一组匹配称为特征跟踪。最简单的匹配两幅图像间特征的方法是对比第一幅图像中所有的特征描述子和第二幅图像中所有其他的特征描述子。
描述子的对比用相似度测量。如果描述子是特征的局部外观贴图，比较好的测度方法是SSD或NCC。对SIFT描述子来说，就是欧氏距离。
比较两幅图像中所有的特征描述子后，在第二幅图像中选择最优对应特征就是选择距离或相似度上最近的描述子。但在这个过程中可能导致第二幅图像中的特征匹配了第一幅图像中的不止一个特征。为了决定选择哪个匹配，就需要采用相互一致性确认。这个方法存在于用第一幅图像中的特征去匹配第二幅图像中的每个特征过程中。只有相互认为是优选匹配的对应特征对才会被认为是正确的特征匹配。
这种穷尽匹配的劣势是计算复杂度是特征数量的二次方，当特征的数量很大的时候，比如几千个时，这种方法就变得不切实际。一种更好的方法是使用索引结构，比如多维搜索树或哈希表，用于在给定的特征附近快速搜索特征。一种更快的特征匹配方法是在第二幅图像中可能的区域搜索潜在的对应关系。这些区域用运动模型或3D特征位置（如果有的话）寻找。比如，在第一部分中描述的3D到2D的运动估计。运动估计还可以使用附带的传感器，比如IMU，里程计，激光，GPS，或者也可以从前一位置估计一个常量速度模型，如论文26所示。那么，特征区域就可以从运动的不确定性和3D点云中作为误差椭圆计算。
还有一种方法，如果只知道运动模型而不知道3D特征位置，那么对应关系就可以在第二幅图像中沿着对极线进行搜索。这个过程称为对极几何匹配。如图5所示，一个2D特征和两个相机中心点形成了3D空间中的一个平面，这个平面和两幅图像相交于两条直线，这两条直线成为对极线。对极线可以从2D特征和相关的相机运动计算出来，如第一部分中介绍的。第一幅图像中的每个特征在第二幅图像中都有不同的对极线。
图5. 对极几何约束
在立体视觉中，通常不是对每个候选特征计算对极线，而是对图像进行矫正。图像矫正是将图像对重投影到一个新的图像对上，其中左右两边的图像对极线是水平的且相互对齐。既然对极线不需要从每个特征中计算：特征的对应关系可以从左右两个图像中交叉搜索，它们都在同一行上，这样图像匹配/对应关系搜索就非常有优势。图像矫正可以在GPU上高效执行。在立体视觉中，两个相机的相对位置是精确已知的。但是如果运动受到不确定性的影响，对极搜索通常会从对极线扩展到一个特定距离的矩形区域中。在立体视觉中，SSD，NCC和统计变换，广泛地用来计算对极几何匹配的相似度度量。
在所有候选图像上查找特征，然后匹配它们具体操作是先在第一幅图像上检测特征，再在后续的图像上搜索对应的匹配。这种检测后跟踪的方法非常适合视觉里程计应用，拍摄的图像都是在相近的位置，它们的连续帧间的运动和外观形变比较小。针对这种运用，SSD和NCC工作良好。
然而，如果特征跟踪是工作在一个很长的图像序列上，它们的外观变化很大。这种情况下，针对每个特征采用仿射形变模型是一种解决方案。一种可行的跟踪算法是KLT跟踪法。
SIFT特征匹配，论文14的作者最初使用距离比值，用于位置和目标检测。如果最近的和第二近的匹配的比值低于用户指定的阈值，距离比值算法就会使用最近的这个匹配（最小的欧几里得距离）。这种删除匹配的方法可能不是一直有用，比如在重复的场景结构情况下。用于检测的比值只能是启发式的，不幸运的猜测可能会删除正确的匹配。因此，很多例子中，不是用比值测试，而使用RANSAC处理离群点可能更好一些。
视觉里程计中除了点特征方法，还可以使用直线和小边。在结构化环境中，他们可以用作点特征的附加信息，可以提供更多有用的线索，比如方向（直线或小边的）平面或正交约束。相比点云，直线更难匹配，直线更容易被遮挡。然而，小边线段的起点和终点可能不存在（比如，遮挡和水平直线）。
图像中的特征会显著影响视觉里程计的效果。特征越多，运动估计效果越稳定，这就需要关键点在图像中的分布尽可能平均。为了达到这样的目的，图像可以被分成网格，每个格子中的特征检测会调整检测阈值，知道每个子图像中取得最少数量的特征。一个成功的规则是，一个640x480分辨率中有1000个特征。
除了稀疏特征提取方法外，还可以使用稠密方法，比如光流法，或无特征方法。光流法主要用于跟踪，每个像素或整幅图像中的子集（比如，用于指定的网格中的所有像素）。但与特征跟踪类似，它要求帧之间的运动较小，因此，不适用于视觉里程计，它的运动累积误差会迅速增加。另一种替代方法是无特征运动估计方法：使用谐波傅里叶变换计算两幅图像的相对运动。这种方法对低纹理图像优势明显，但计算复杂度高（可能需要好几分钟）运动恢复精度也比基于特征的低。
本文中我们翻译了视觉里程计的特征选择和特征匹配，在【泡泡机器人翻译专栏】视觉里程计——第二部分：匹配、鲁棒、优化和应用(下)中，我们将翻译离群点移除、误差传播及相机位姿优化等余下内容。
长按下图，识别图中二维码，关注“泡泡机器人SLAM”（ID：paopaorobot_slam）公众号，我们将会持续推出这个翻译系列的文章。翻译的全文PDF及原文下载链接在【泡泡机器人翻译专栏】视觉里程计——第二部分：匹配、鲁棒、优化和应用(下)中给出，敬请关注。
【版权声明】泡泡机器人SLAM的所有文章全部由泡泡机器人的成员花费大量心血制作而成的原创内容，希望大家珍惜我们的劳动成果，转载请务必注明出自【泡泡机器人SLAM】微信公众号，否则侵权必究！同时，我们也欢迎各位转载到自己的朋友圈，让更多的人能进入到SLAM这个领域中，让我们共同为推进中国的SLAM事业而努力！
【注】商业转载请联系刘富强（[email protected]）进行授权。普通个人转载，请保留版权声明，并且在文章下方放上“泡泡机器人SLAM”微信公众账号的二维码即可。
