这一过程有些类似于我们之前在 DL 中优化算法部分从 SGD 不断演进到 Adam 的思路在原有框架上持续优化各个组成部分最终形成工程实践中的默认选择。而在误匹配剔除这一环节USAC 已经成为现代计算机视觉中最主流的通用 RANSAC 框架被 OpenCV 等主流视觉库默认采用。这里提前说明一点USAC 的原论文在 12 年发表但其中组件也在不断更新本文介绍的是 OpenCV 的现代 USAC 管道因此出现年份更新的论文和技术是正常的。RANSAC 的局限#还是老样子标准 RANSAC 仍然存在一些明显的局限问题 影响随机采样完全盲目对所有匹配点一视同仁 浪费大量迭代在低质量匹配上内点判定使用固定硬阈值 无法适应不同场景的噪声分布只选最多内点的模型不区分模型好坏 对低内点率场景不够鲁棒没有局部优化步骤 最终模型精度有限超参数需要人工设定 实际使用不够自适应基于这些局限在 RANSAC 提出后的四十多年里大量研究工作开始围绕这些问题不断改进。但就 RANSAC 本身而言它的使命非常明确从包含噪声的数据中稳健地估计正确的几何模型。由此它的改进也始终围绕一个核心问题展开如何更快、更准、更鲁棒地从误匹配中找到正确的单应性矩阵由此我们从 USAC 的各个组件开始介绍最终组成完整的 USAC 框架。PROSAC有优先级的采样#基本的退化检测就不再展开了不同模型的内容并不相同但思想都是一样的。首先标准 RANSAC 的一个突出问题在于采样的盲目性。在 SIFT 匹配之后我们已经拿到了描述子距离靠近的描述子往往更可能是正确的匹配。但标准 RANSAC 在随机采样时完全忽略了这些信息对每一对匹配点一视同仁。改进想法由此而生能否利用匹配质量信息优先选择那些看起来就更可靠的匹配点来采样05 年论文 Matching with PROSAC – Progressive Sample Consensus 提出的 PROSACProgressive Sample Consensus 便是针对这一问题的著名改进。它的核心思路相当直观既然我们有 SIFT 匹配时的距离信息比率测试的结果为什么不优先从那些距离最近、质量最高的匹配点中采样其针对采样环节的具体优化是这样的排序 将所有匹配点按照 SIFT 描述子间的欧式距离从小到大排序。渐进采样 初始时只从前个质量最高的匹配点中随机采样随着迭代次数增加逐渐扩大值将质量稍差的点也纳入采样范围。cda37db5-6b82-4db7-a704-7ec5b631298b.png这样初期大部分采样都集中在高质量的匹配点上早期就能快速找到正确的模型。实验结果也表明在相同置信度下PROSAC 通常只需要标准 RANSAC 1/2 到 1/10 的迭代次数。SPRT快速模型验证#PROSAC 解决了采样效率低的问题下一个环节就是模型验证。标准 RANSAC 的验证过程较直接依次计算每个匹配点到当前模型的重投影误差统计最终有多少属于内点。假设共有个匹配点那么每生成一个候选模型都需要完成次误差计算耗时较多。而改进思路是这样的既然很多错误模型在验证初期就会暴露为什么还要坚持验证所有匹配点同样是 05 年发表的论文 Randomized RANSAC with Sequential Probability Ratio Test 将统计学中的 SPRTSequential Probability Ratio Test 引入 RANSAC对这一阶段进行了优化。它的核心思想是边验证边判断当前模型是否还有继续验证的必要。具体来说对于一个候选模型SPRT 不再一次性验证全部匹配点而是按照一定顺序逐个检查其流程如下随机取一个匹配点计算重投影误差并判断内外点。根据当前累计得到的内点、外点情况不断更新模型正确的概率。如果统计结果表明该模型几乎不可能成为正确模型则立即停止验证直接进入下一次采样。显然算法的关键在于如何评估当前模型的正确率其内容就是开始提到的 SPRT:把模型验证看成一个统计假设检验问题而不是简单地统计最终内点数。对于每一个候选模型SPRT 建立两个互斥假设Good Model当前模型是真正的好模型。Bad Model当前模型只是随机产生的错误模型。在此基础上维护一个似然比当前所有观测当前所有观测显然如果公式结果那么这些数据更像是好模型产生的。对于一个真正正确的模型它产生内点的概率较高因此定义其中表示好模型的预期内点率经验上可能取说明一个正确模型大约有 60%~80% 的匹配属于内点。而对于一个错误模型大部分匹配都会失败因此定义其中例如表示随机错误模型只有约 10% 的概率碰巧解释一个匹配点。现在设当前验证到第个匹配若该匹配属于内点则累计似然比乘上这代表好模型解释这个点的概率更多反之若属于外点则乘上最终累计似然比不断更新继续SPRT 设置了一个拒绝阈值SPRT 本身其实还有一个接受阈值但在这里不使用如果说明数据越来越支持好模型继续验证反之则说明模型更符合错误模型此时立刻终止当前模型的验证回到采样阶段进行下一轮。关于最终的判断不同方法间会有所差异但其思想都是相同的。500c2ad1-90d4-4c22-8d5a-63544b53a5ba.png这样一个错误模型可能只验证二十几个匹配点就被丢弃而无需继续检查剩余几百个匹配。MAGSAC更加鲁棒的模型评分#经过 PROSAC 与 SPRT 的优化USAC 已经能够更好地生成候选模型并更快地淘汰错误模型。而下一步改进在模型评分环节标准 RANSAC 的做法十分直接统计内点数量选择内点最多的模型作为最终结果。这种方法实现简单但也存在明显问题它把所有内点都视为同样优秀而所有外点都直接舍弃没有考虑误差大小带来的差异。19 年论文 MAGSAC: Marginalizing Sample Consensus 提出了 MAGSACMarginalizing Sample Consensus对模型评分进行了改进。它不再简单统计有多少内点而是综合考虑每个匹配点的误差大小对模型进行更加精细的评分。首先传统 RANSAC 的评分可以理解为一个 0/1 损失函数误差只要超过阈值贡献立即变为 0只要低于阈值无论误差大小都贡献 1。而 MAGSAC 则认为匹配误差越小对模型可信度的贡献应该越大误差越大贡献应逐渐降低而不是突然变成 0。而从这个思路出发一个很直接的想法就是用总误差排序但仔细想想这种方法受离群点影响严重很容易出现“99 个完美匹配被 1 个极大误差拖后腿”的情况因此无法真实应用。为此 MAGSAC 引入了一个概念噪声标准差这其实是内外点阈值的上层逻辑它是指相机精度本身造成的误差比如工业相机精度较高同一个特征点每次检测的结果间可能存在的误差。其目的是说明当前数据本身允许多大的误差。现在假如而重投影误差说明正常误差只有半个像素结果却出现 3 个像素这个点应该扣很多分。但如果代表正常情况下大家都有5像素误差那 3 像素反而很好应该给高分。而 RANSAC 里面的阈值其实就是依据噪声标准差定下的通常经验公式是因此标准 RANSAC 其实隐含着一个前提我认为就是某一个固定值。 所以直接输入一个阈值作为权威标准指导评分。但实际上不同设备不同数据的噪声标准差完全不同。所以 MAGSAC 说既然不知道σ是多少那就不要猜。其表现出的最终算法说直白点其实就是遍历阈值后加权求和作为最终评分论文里的公式是这样的但这是理想的积分形式真实实现中都是按不同步长的加权求和b8fe5726-e65e-44da-b566-43fefc43efad.png举个例子噪声标准差可能如下σ 概率1 0.22 0.33 0.34 0.2以此我们对于同一个模型 M分别计算得分σ 内点数量1 502 633 714 75那么最终评分就是这样我们可以避免不切实际的阈值对结果一刀切让越可能出现的噪声水平对最终评分影响越大。而如果没有先验的话直接平均也是一个常见选择。LO-RANSAC在迭代中局部优化#继续下一步优化03 年论文 Locally Optimized RANSAC 提出了 LO-RANSACLocally Optimized RANSAC其目标是进一步提高最终模型精度。我们知道标准 RANSAC 只会对最后迭代完成得到最优模型再使用所有内点进行一次最小二乘优化来提升最终精度。但问题是RANSAC 每次迭代生成模型时本身只使用了最小采样集其计算得到的内点只用于评分。但一个真实场景往往存在几十甚至上百个正确匹配仅利用其中 4 个点即使模型正确也不可避免会受到采样噪声的影响。于是一个很自然的优化思路产生了既然已经找到了大量内点为什么不在迭代过程中就利用这些内点重新估计一次模型它并没有改变 RANSAC 的整体流程而是在发现一个比历史最优模型更好的候选模型时额外插入一次局部优化整个流程如下使用当前最优模型找出全部内点。从这些内点中重新随机采样利用新的采样重新估计模型。再次统计新的内点集合重复上述过程直到模型不再继续改善。最后对当前最优模型进行一次全内点的最小二乘优化并更新为最优模型继续外层整体迭代。这里要说明一点原始 LO-RANSAC 的采样其实本质只是缩小了搜索范围其内部仍然是最小采样集只是在局部优化的最后增加了一次最小二乘优化。而在现代管道中非最小估计技术更加成熟局部优化会使用全部内点直接重新拟合更高效。26dfefb4-7b54-4387-8b1e-03f85eed4f65.png6.自适应终止策略#我们在上一篇就提到了这个问题标准 RANSAC 的做法十分直接提前设定最大迭代次数达到次数后直接结束。优化方向自然产生既然已经找到了一个非常好的模型为什么不能提前结束算法事实上标准 RANSAC 本身已经提出了这一思想就是我们上一篇推导的终止公式但问题是这个公式只能指导我们选择迭代次数真正的内点率是未知的只有在运行中才能不断估计。因此现代 USAC 采用了更加合理的策略每当找到新的最佳模型就重新估计当前内点率并重新计算还需要多少次迭代。比如如最开始的模型计算得到需要约1800次迭代继续迭代发现一个更好的模型再计算只需要约 190 次迭代如果此时已经完成了更多次迭代那么已经超过理论所需迭代次数可以直接结束算法。而且这种提前结束是具有概率保证的设定意味着算法结束时已经有至少 99% 的概率采样过一次全部由内点组成的最小采样集。因此即使提前停止也不会明显降低算法成功率。3a6baa67-115e-4dad-a3da-a8da1a147d89.pngUSAC 统一框架#至此我们已经分别介绍了 USAC 的各个组成模块12 年论文 USAC: A Universal Framework for Random Sample Consensus 提出了 USACUniversal Sample Consensus它并不是一种全新的 RANSAC 算法而是把上述的多种经典改进方法统一整合到同一个框架中这正是其名称中 Universal统一 的含义。09d479db-f38f-438f-b0d4-3707fc087b96.png