MaxCon(最大一致性)

**最大一致性(Maximum consensus)**是RANSAC只能近似求解的优化问题。给定带有残差函数 $r_i(\theta)$ 的一组测量值和一个内点阈值 $\epsilon$,找到与尽可能多的测量值相符的模型:

被最大化的这个集合称为一致集(consensus set),即内点集合。拟合基础矩阵、单应矩阵、相机位姿,或”内点最多”的点云配准,都是这同一个问题的具体实例。

为什么RANSAC不是故事的终点

RANSAC通过随机最小样本采样来攻克最大一致性问题:它能以较高概率返回一个不错的一致集,但是

• 它是随机化的——对同一组数据运行两次可能得到不同的答案;
• 它不提供任何最优性保证——返回的一致集可能小于真正的最大值,在外点比例很高、所需采样数量急剧膨胀的情况下尤为如此;
• 它返回的模型是拟合于一个最小样本得到的,因此在未经细化之前对噪声很敏感。

把最大一致性作为一个正规的优化问题来研究,提出的问题是:要确定性地找到精确的最大化解,需要付出什么代价?

难度与精确算法

坏消息是根本性的:最大一致性在一般情况下是NP难的——这是一个关于该信任哪个测量子集的组合优化问题,除非P=NP,否则没有算法能高效求解所有实例。一致性目标函数在分析性质上也很棘手:它是关于 $\theta$ 的分段常数计数函数,几乎处处梯度为零,因此普通的非线性优化无法直接对其施力。

因此,精确(全局最优)方法要付出指数级的最坏情况代价,但对小规模问题仍可行:

• 分支定界(Branch-and-bound, BnB):递归地划分参数空间(例如旋转/平移空间),剪掉那些一致性上界劣于目前找到最优解的分支。终止时保证获得全局最优解。
• 基于活动集的树搜索:利用此类问题的最优解由一个小的约束*基(basis)*刻画这一事实,用最佳优先(A*风格)策略在各个基之间搜索。
• 混合整数规划:为每个测量引入一个二元变量 $z_i \in \{0, 1\}$,求解

其中 $M$ 是一个足够大的常数,将问题交给一个现成的MIP求解器。

一个有用的重新表述:最大化一致性等价于最小化被违反约束的数量——这是一个 $\ell_0$ 型的目标函数。这一视角把MaxCon与其可处理的替代方案联系起来:将 $\ell_0$ 松弛为 $\ell_1$ 或其他凸损失,得到凸松弛方法;而将鲁棒核函数从凸函数逐步变形为再下降(redescending)函数,则得到渐进非凸性方法(GNC)。这些方法放弃了精确性,换来多项式时间的运行代价,有时还能获得后验最优性证明。

实践图景

对SLAM的意义

SLAM中的每一步几何估计——本质矩阵、PnP、回环检测验证、点云配准——本质上都是一个一致性最大化问题。实时前端会继续使用RANSAC系的启发式方法,但了解精确问题能让你清楚地知道自己牺牲了什么:一个随机化的前端可能悄无声息地接受一个次优的一致集,而建立在其上的一次错误回环就可能扭曲整个地图。这也是可证明鲁棒估计这一研究方向(全局最优旋转搜索、TEASER风格的配准、GNC后端)日益出现在对错误答案代价高昂的SLAM系统中的原因。

相关条目

• RANSAC
• PROSAC
• 凸松弛
• M估计器
• TEASER++