Matching with PROSAC – Progressive Sample Consensus

PROSAC（Progressive Sample Consensus）是一种用于计算机视觉中匹配问题的鲁棒性匹配算法。该方法在建立临时对应关系时，利用相似性函数对对应点集合进行线性排序，并从排名较高的对应点集合中逐步抽取样本，而不是像RANSAC那样从全部对应点集合中均匀随机地抽取样本。通过对对应点进行预排序，PROSAC算法可以在保证正确匹配概率的情况下，显著减少计算量，并且在最坏的情况下趋向于RANSAC算法。实验表明，PROSAC通常比RANSAC算法快很多，有时甚至可以快上百倍。这种方法特别适用于宽基线立体匹配、结构与运动估计、图像检索和物体识别等计算机视觉问题。 PROSAC算法假设相似性度量比随机猜测更能预测匹配的正确性。其核心思想是通过一个逐步增加的样本大小，从最可靠的匹配开始，逐步加入更不可靠的匹配，直到达到所需的样本数量。在宽基线立体匹配问题中，PROSAC算法能够有效地找到可靠的匹配对，即使在存在遮挡、深度不连续性和重复模式等情况下也是如此。 PROSAC算法的一个关键优势在于其效率。由于从最可靠的对应点开始样本抽取，因此能够快速收敛到包含正确匹配的假设，并且在确认足够数量的正确匹配后快速终止，从而节省了计算资源。这与RANSAC算法形成了鲜明对比，后者在整个数据集上均匀采样，无论对应点的可靠性如何。 在计算机视觉领域，找到两幅或多幅图像中可靠的对应点是一项困难且关键的步骤，是许多问题如立体匹配、结构与运动估计、图像检索和物体识别等的基础。在初期的匹配过程中，通常只有局部图像描述符可以比较，所以不可避免地会引入一些不正确的匹配，这些不正确的匹配可能由于遮挡、深度不连续性和重复模式等现象造成。为了去除这些错误匹配，研究者们通常会使用鲁棒的假设和验证方法，比如随机样本共识（RANSAC）和类似的方法，它们已成为去除异常值的首选方法。 例如，在宽基线立体视觉问题中，通过PROSAC算法寻找两幅图像之间的可靠对应点，可以在一幅图像中找到连续的对应点，即使在诸如长城这样的场景中存在遮挡，也能有效地进行匹配。算法通过逐渐增加样本集合的大小，从可信度最高的对应点开始进行采样，从而在保证高匹配质量的同时，显著提高了效率。 此外，PROSAC算法在计算机视觉的其他应用中也表现出了强大的鲁棒性，如在结构与运动估计问题中，通过可靠匹配来重建场景的三维结构；在图像检索中，通过匹配找到相似的图像；在物体识别中，通过匹配不同图像中的同一物体来识别物体。所有这些应用都需要可靠的特征匹配作为基础，而PROSAC算法提供了一种有效的解决方案。 PROSAC算法通过引入预排序并逐步增加样本集合的方式，大大提高了匹配算法的效率和可靠性，尤其适用于那些需要处理大量数据且对匹配质量有严格要求的计算机视觉任务。