PROSAC

PROSAC（Progressive Sample Consensus，渐进式采样一致性）由Chum与Matas于2005年提出,它利用了一个普通RANSAC所忽略的事实：对应关系成为内点的可能性并不相等,而我们通常拥有一个可以预测这一点的逐匹配质量分数——描述子距离,或者更好的选择,即最近邻与次近邻距离之间的Lowe比值 $d_1 / d_2$ 。

思路

按质量对 $n$ 个候选对应关系进行排序,质量最高的排在最前。PROSAC不是从全部 $n$ 个匹配中均匀采样最小样本集,而是从逐步增长的高排名匹配子集中抽取样本：

早期迭代仅从少数最佳匹配中采样(例如先取前 $s+1$ 个,再取前 $s+2$ 个,以此类推),此处的内点密度最高。
随着迭代推进,采样池逐渐扩展至完整集合,因此在极限情况下,PROSAC的采样分布会收敛到对全部匹配的均匀采样。

形式化地说,存在一个增长函数,决定经过多少次采样后池的大小从 $m$ 增加到 $m+1$ ;每个样本由新加入的匹配加上从前 $m$ 个匹配中抽取的 $s - 1$ 个匹配组成。其设计目标是使PROSAC(近似)抽取与RANSAC相同的样本集,只是顺序不同——由质量驱动,最有希望的样本先被抽取。

算法概要

按质量分数对对应关系排序,最优者在前。
维护当前池大小 $m$ (初始为 $m = s$ )及其增长计划。
每次迭代时,如上所述从前 $m$ 个匹配中形成一个最小样本,拟合模型,并对全部 $n$ 个对应关系进行验证。
按内点数量跟踪最优模型;当满足RANSAC式的置信度准则(非随机的内点数量,加上对当前内点比例估计而言足够的采样次数)时停止。
与标准RANSAC一样,对所有内点用最小二乘重新拟合。

特性

速度：当质量排序具有信息量时(排名靠前的匹配确实大多是内点),通常在最初的几十次抽样内就能找到全内点样本,在整体内点比例较低时比均匀RANSAC快几个数量级。整体内点比例 $w$ 可能很差(比如10%),但前20个匹配中却可能有90%是内点——PROSAC在早期池上的有效 $w^s$ 会显著更高。
最差情况下具有相同保证：如果分数没有信息量,PROSAC会优雅地退化为标准RANSAC行为,采用相同的停止准则

P(\text{success}) = 1 - (1 - w^s)^N \geq 1 - \eta

相同的验证步骤：假设仍然通过全部对应关系上的内点一致性来打分,因此有偏的采样池不会使最终的模型选择产生偏差。

实践要点

质量度量的选择很重要：Lowe比值作为内点预测指标远优于原始的描述子距离。
PROSAC与自适应终止天然搭配——最早出现的良好模型会立即缩短所需的迭代次数。
OpenCV在其USAC框架中提供了PROSAC式的采样(cv::USAC_PROSAC),可用于 findEssentialMat、findHomography、solvePnPRansac 等函数。
需注意早期池退化的问题：排名靠前的匹配往往集中在某个纹理丰富的单一物体或平面上,这可能产生一个局部一致但全局错误的模型(例如,当你想要的是本质矩阵时,却得到了某个平面的单应矩阵);退化性检测依然适用。

对SLAM的意义

实时预算非常紧张：跟踪运行在30-60 Hz,几何验证必须在几毫秒内完成。PROSAC能以远少于典型场景所需迭代次数,达到与RANSAC相当的外点剔除质量。
SLAM前端在匹配过程中已经计算出所需的匹配分数(描述子距离、比值检验值),因此排序几乎不需要额外成本。
在重定位和回环检测中特别有价值,因为这些场景中候选匹配集庞大且严重受污染,均匀RANSAC需要数千次迭代才能收敛。

PROSAC

思路

算法概要

特性

实践要点

对SLAM的意义

相关条目