PROSAC：提升鲁棒匹配效率的随机样本一致性算法

PROSAC论文翻译探讨了一种新颖的鲁棒匹配算法——随机样本一致性（PROSAC），它旨在解决计算机视觉中的关键问题，如窄基线和宽基线立体匹配、结构和运动估计以及图像检索和对象识别。相较于传统的RANSAC算法，PROSAC方法有以下几个关键特性： 1. 线性排序利用：PROSAC利用一组对应关系上的线性排序，通过构建临时对应关系中的相似性函数，这使得它能够更有效地预测匹配的正确性，比随机猜测更准确。 2. 样本选择策略：与RANSAC不同，PROSAC平等对待所有对应关系，从整个集合中均匀地抽取随机样本。与RANSAC一次性抽取大量样本不同，PROSAC逐步增加排序最高的对应关系，这样在一定程度上减少了错误匹配的可能性。 3. 计算效率提升：通过利用U（试探性对应集合）的线性排序，PROSAC实现了显著的计算效率提升，理论上可以达到RANSAC的几百倍速度。这意味着在实际应用中，它的运行时间大大减少，尤其适用于对速度有较高要求的场景。 4. 最坏情况性能：尽管在最坏情况下，PROSAC的样本数量可能会接近RANSAC，但整体性能优于后者，尤其是在处理宽基线匹配问题时，其强大的能力得到了验证。 5. 算法设计：PROSAC并不是简单地对局部匹配过程进行建模，而是作为一个生成暂定对应关系的黑盒，通过比较局部描述符来找出可能的匹配。当找到优秀解决方案的概率低于预设阈值时，才会进入假设-测试循环。 6. 与RANSAC对比：虽然两者都是基于抽样和测试的鲁棒方法，但PROSAC在利用有序信息上具有优势，使得其在处理大规模数据集时能提供更快的结果。 PROSAC算法凭借其利用线性排序和高效样本选择的优势，在鲁棒匹配任务中表现出优异的性能，特别是在处理复杂场景和对速度敏感的应用中，具有显著的竞争优势。