RANSAC与鲁棒核函数：解决特征匹配和点云配准中的异常值问题

做特征匹配、点云配准或者位姿估计的同学大概率都遇到过这种场景数据看着还行逻辑也清晰可拟合出来的结果就是“歪”得离谱。我第一次踩这个坑是在做一个两视角位姿估计的Demo两张图上匹配了百来个特征点重叠率很高按理说基础矩阵应该非常稳定但用最小二乘求解后极点位置飞到了图像外面重投影误差大得没法看。后来逐点检查才发现一百多个匹配里混进了三个错匹配就是这三颗“老鼠屎”把整个解给拽跑了。为什么三个点就能带偏一百多个点问题出在最小二乘的代价函数上。这篇内容围绕RANSAC和鲁棒核函数展开这两样东西是处理带异常值数据的两种经典思路一个负责硬剔除一个负责软降权。做SLAM、三维重建、特征匹配、点云配准的同学不管是入门还是要系统复习这篇文章都能给你一条完整的脉络。1. 一个能复现的糟糕例子为什么最小二乘会被一个点带偏1.1 平方项把异常值“超倍放大”最小二乘优化的目标函数是残差平方和E Σ rᵢ²这里的 rᵢ 是每个数据点与当前模型之间的残差。平方项是一个非线性放大器残差是 1 的时候贡献 1残差是 2 的时候贡献 4残差是 5 的时候贡献 25。一个误差为 5 的离群点在代价函数里的“话语权”相当于 25 个误差为 1 的普通点。这还不是最狠的——误差为 10 的离群点话语权相当于 100 个误差为 1 的点。在正常的拟合问题里内点噪声的残差通常在 1 到 2 个像素量级而误匹配的残差经常是几十甚至上百像素。把这种残差平方之后异常值对整个优化梯度的主导作用几乎是压倒性的。模型为了照顾这个异常值宁可牺牲几十个普通点的精度也要把参数挪到能让异常值残差稍微下降的位置。这就是“一票顶十票”的数学根源。1.2 面对异常值两条不同的处理路线既然平方损失会放大异常值的影响就有两条自然的解决思路。路线A干脆不认这部分数据。既然误匹配是错的那就不让它参与运算。于是我们有了RANSAC——随机采样一致性算法。它的思路简单粗暴但有效多次随机抽取小样本集拟合成模型统计有多少数据支持这个模型最后挑支持者最多的模型。支持者就是“内点”剩下的直接忽略。路线B保留数据但把代价函数换掉。最小二乘对残差“按平方记功”如果我们换成不那么激进的损失形式——比如残差大了之后代价按线性增长甚至趋于饱和那么异常值虽然还在数据里但对优化的牵引力会被压下来。这就是鲁棒核函数做的事情。这两条路线不是互斥的实际工程里经常串联使用先用RANSAC把明显的外点清掉再用鲁棒核函数做精优化。后面我会详细展开这套组合流程先把每个部分单独讲透。2. RANSAC的采样—投票机制它不是暴力搜索而是概率策略RANSAC全称是Random Sample Consensus中文常翻译为“随机采样一致性”。它诞生已经有几十年了到今天依然是特征匹配、基础矩阵估计、点云配准初始化里最常用的鲁棒估计手段。它之所以长盛不衰是因为把“模型拟合”这个优化问题转换成了“少数服从多数”的投票问题。2.1 三步循环最小子集假设、一致性评估、最优更新RANSAC的每一次迭代就做三件事。第一步从全部数据中随机抽取一个“最小子集”。最小子集的意思是恰好能唯一确定模型参数的最少点数。拟合一条直线需要2个点估计单应矩阵需要4对点估计基础矩阵用8点法需要8对点用5点算法就是5对拟合一个平面需要3个点求刚体变换需要3对点。最小子集虽然小但在随机抽取时“所有点都属于内点”这件事发生的概率是最高的因为内点占多数时抽到外点的概率远低于抽到内点。第二步用这个最小子集计算出一个模型参数。第三步用这个模型去评估全部数据。计算每个点到模型的残差残差小于某个阈值的记作内点大于阈值的记作外点。统计这次假设的内点总数。如果这次的内点数比之前所有迭代的最好成绩都好就更新最优模型。重复上述循环直到达到约定的迭代次数或者满足提前终止条件。一个经常被忽略的细节是RANSAC最后通常不会直接输出最后一次内点最多的那个模型而是拿“最大内点集”里的所有内点再拟合一次模型。因为只用最小子集拟合的模型精度有限而内点集里所有点重新拟合精度会高很多。这个“refit”步骤在实际工程里非常关键我见过不少人只把RANSAC当成一个分类器取出内点之后忘了再拟合结果精度总是差一口气。2.2 迭代次数不是拍脑袋定的一个经典公式很多人写RANSAC时迭代次数随手写个100或者500。其实迭代次数应该根据内点比例和最小子集大小来计算公式是k log(1 - p) / log(1 - wⁿ)其中 w 是数据中内点所占比例n 是每次抽取的最小子集大小p 是你希望“至少有一次采样全是内点”的成功概率通常取 0.99。来算几个具体的数直观感受一下w 0.5n 2p 0.99 时k log(0.01) / log(0.75) ≈ 16 次w 0.5n 4k ≈ 72 次w 0.5n 8k ≈ 1177 次w 0.3n 8k ≈ 5012 次w 0.2n 8k ≈ 16850 次这个表一拉出来马上能看出两个趋势第一最小子集越大需要迭代的次数越爆炸式增长第二内点比例越低迭代次数也涨得飞快。所以对基础矩阵这种 n8 的任务如果内点比例只剩50%1177次迭代只是理论底线实际为了稳妥通常会跑两三千次。而对 n2 的直线拟合就算数据里只有一半是内点16次采样理论上就够了这就解释了为什么直线拟合的RANSAC可以开得飞快。公式的推导逻辑也不复杂单次采样全部是内点的概率是 wⁿ至少有一个外点的概率就是 1 - wⁿ。连续 k 次采样都至少包含一个外点的概率是 (1 - wⁿ)ᵏ。我们要让这个“全失败”的概率小于 1 - p解不等式就能得到上式。理解了推导你就能解释很多工程现象——比如为什么高维模型难鲁棒为什么外点率一高就跑不动。2.3 阈值和内点比例两个需要先验经验的参数RANSAC里最需要经验的参数是“内点判定阈值”也就是第二步里那个控制内外点划分的距离上限。这个阈值如果给大了外点会被当成内点模型被污染给小了真正的内点又被排除模型可能欠拟合。常用的做法是根据噪声水平来标定。如果已知传感器噪声的标准差是 σ阈值一般取 2σ 到 3σ。在视觉特征匹配场景重投影误差阈值通常给 1 到 3 像素在点云配准场景常用体素分辨率的 1 到 2 倍作为阈值。如果你对噪声水平完全没有先验可以用“从小到大扫一遍阈值观察内点数量的拐点”来粗估计拐点附近往往是内点/外点分界比较清晰的位置。内点比例 w 也存在同样的问题。工程上常用的技巧是“自适应迭代次数”先给一个乐观的 w或者直接给个中等值 0.5跑几轮后用当前最优模型的内点数量除以总点数得到新的 w再代入公式重新计算还需要多少轮 k。如果新算出来的 k 小于已经迭代的轮数就提前退出。这样既保证了理论上的坏概率可控又不会在数据干净时浪费大量时间。我在做特征匹配时几乎总是开着这个自适应因为它能把平均迭代时间省下 30% 到 50%。3. 鲁棒核函数不删除异常值而是“削权”后再优化RANSAC像一位严格的安检员非黑即白能过的算内点不能过的直接扔出去。但真实数据往往没有这么黑白分明——有些点误差大一点但还是有效观测有些点误差恰好卡在阈值边缘。硬切一刀的结果是阈值两侧的样本在优化中的命运截然不同模型可能因此不稳定。鲁棒核函数是另一种哲学不赶人走但根据误差大小动态调整每个人说话的分量。3.1 常见核函数的数学形态与行为对比鲁棒核函数的核心改变是把代价函数从 r² 替换成 ρ(r)其中 ρ 是一个增长速度受限的函数。优化问题变成argmin Σ ρ(rᵢ)下面几个核函数是工程里最常见的核函数公式大残差行为特点最小二乘ρ(r) r²二次增长对异常值过分敏感Huberr≤δ 时 r²/2否则 δ(Cauchyρ(r) σ²/2 · log(1 (r/σ)²)对数增长带饱和对远残差压制强Tukeyr≤σ 时 σ²/6 · (1-(1-(r/σ)²)³)否则 σ²/6Geman-McClureρ(r) σ²r²/(σ² r²)趋于常数温和饱和常用于配准Huber核在残差小于 δ 时几乎是最小二乘当残差超过 δ 后代价改成线性增长不会因为一个巨大的残差把整个优化拉起。它保留了二次区间的效率又限制了异常值的破坏力是多视角几何和SLAM里最常用的默认选项。Cauchy核和Geman-McClure核的代价随着残差增大而逐渐饱和残差再大对总代价的贡献也有限。Tukey核更极端残差一旦超过 σ代价直接固定成常数再大的残差也不会再增加代价——这就和“软剔除”差不多了。要理解这些核函数在优化里到底做了什么光看 ρ 还不够要看它对梯度的实际影响。在高斯牛顿或者LM迭代中每个残差项会被配一个等价权重 ωᵢ ρ′(rᵢ) / (2rᵢ)。对最小二乘ρ′(r) / 2r 1每个点的权重都一样对Huber核残差超过 δ 的点权重变成 δ/(2|r|)残差越大权重越小对Tukey核残差超过 σ 的点权重直接变成 0完全不参与更新。这个视角很直观核函数本质上是在给每个残差动态地配权重。3.2 为什么SLAM与几何配准都离不开核函数在SLAM里一个非常典型的场景是后端图优化。相机位姿和地图点构成节点观测构成边每条边是一个残差项。如果特征匹配阶段漏掉了一些误匹配这些错误的边会让位姿朝错误方向移动。最坏情况下一个误差很大的错误观测会在信息矩阵里产生极大的贡献把整个地图拖变形。给每条边挂一个鲁棒核函数目的就是限制这种错误观测的影响。这也是主流SLAM框架图优化接口里默认保留核函数设置的原因。点云配准里的ICP迭代也是如此。两组点云的重叠区域里经常有一些未成对点或者激光打出去的飞点。如果不加核函数配准结果会被这些飞点拽出一条长长的尾巴。我实践中的做法是在ICP每次迭代的对应点筛除之后再用Huber核或Geman-McClure核重新加权效果比单纯用距离阈值硬切要好不少尤其在重叠率不高、飞点较多的时候。4. RANSAC与鲁棒核的接力先清场再精修前面分别讲完了两种工具现在说的是它们最常见的协作方式。在我的经验里把RANSAC和鲁棒核函数当成接力而不是二选一几乎适用于所有带有外点的高维估计问题。4.1 一条典型的工作流以视觉SLAM初始化里的基础矩阵估计为例完整链条是这样特征提取与粗匹配产出几百到几千对初始匹配。这一步会混入大量误匹配误配率20%到50%都很常见。用RANSAC估计基础矩阵。通过迭代采样和一致性投票把误匹配区分为内点与外点。这一步的目标不是拿到最高精度的矩阵而是拿到一个“靠谱的支持集”。用RANSAC筛出的内点重新估计基础矩阵。这时可以用更精细的方法比如归一化8点法把所有内点一起做一次最小二乘拟合。以这个矩阵为初始值进行基于鲁棒核函数的非线性优化。残差用重投影误差或极线距离核函数选择Huber或Cauchy尺度参数用内点残差的标准差来标定。优化收敛后再根据残差分布做一次外点剔除比如3σ原则最后用干净内点跑一次不加核的最小二乘作为最终精化。步骤5看起来有些繁琐但它是精度最高的收尾方式。原因是鲁棒核函数在压制外点影响的同时也会轻微扭曲内点的噪声分布一旦外点被反复筛选干净回归普通最小二乘可以让统计效率回到最优。4.2 为什么不能二选一而必须接力只用RANSAC不加核函数的问题在于第一RANSAC给出的内外点判断是硬二值阈值边缘的样本会被武断归类。第二RANSAC模型本身是由最小子集或内点集拟合出来的它没有对噪声大小做精细建模精度的上限有限。第三当任务从“粗匹配”进入到“非线性优化”阶段RANSAC这种“离散搜索硬投票”的框架无法直接嵌入连续优化必须在连续优化的框架里继续精细化。只用鲁棒核函数不加RANSAC的问题在于核函数对初值非常敏感。如果初始模型差得离谱残差分布整体偏移核函数的权重分配会被“系统性偏差”主导最终收敛到局部最优。举个例子基础矩阵估计时如果直接用全部误匹配做加了Huber核的非线性优化经常会被误匹配较多的区域吸引收敛到一个人造的“伪模型”看起来代价函数下降了实际上内点支持率并不高。RANSAC的作用正是先用一种对外点几乎免疫的投票方式把模型初值拉到全局最优附近给后续的鲁棒优化一个可靠的起点。所以完整的接力逻辑是RANSAC负责“粗筛定初值”鲁棒核函数负责“细调防漏网”最后回归最小二乘负责“精修保证统计效率”。三个环节各司其职缺一个效果都会打折扣。5. 实战调参、踩坑记录与效果对照到了实操层面参数怎么设、坑在哪里往往是文档里很少写的东西。这里整理一份可以照着用的速查表和我踩过的几个典型案例。5.1 关键参数速查与建议默认值参数建议默认值/策略备注RANSAC最大迭代次数先按 w0.5 和公式估算再乘1.5~2倍用自适应提前终止更省时期望成功率 p0.99追求极致稳定可设0.999重投影误差阈值2~3像素角点定位精度较高时1像素根据图像分辨率和噪声调整核函数类型默认Huber误配率高用Tukey配准常用Geman-McClure没有先验就从Huber起步核函数尺度 δ/σ用MAD估计1.4826 × median(rᵢ - median(r)最终精化外点剔除干净后回归最小二乘别让核函数一直“在线”关于MAD多说一句直接用内点残差的标准差去设定核函数尺度容易被残余外点抬高导致核函数不够敏感用中位数绝对偏差MAD估计出来的尺度对外点更稳。我自己常用的流程是RANSAC后先算一次MAD用这个值初始化Huber核的 δ跑两轮优化再用内点标准差细调。5.2 我踩过的几个坑第一个坑是把RANSAC迭代次数写死成固定值。在一组内点率70%的数据上固定300次足够换到内点率30%的场景同样的迭代次数会导致采样覆盖不足模型质量明显下降。后来我改成自适应迭代把内点率作为变量在循环里更新效果立刻稳定下来。第二个坑是核函数尺度设得太小。有一次给配准任务设了一个非常激进的Tukey阈值结果真正的外点被压制了但相当一部分不差的内点也被“截断”成零权重迭代基本空转收敛速度肉眼可见地变慢。退一步说核尺度偏大的后果是接近最小二乘、抗外点能力下降偏小的后果是信息利用率下降、结果可能不收敛。找尺度时我建议先用MAD定一个初始值放在优化过程中看残差分布再调整别一锤定音。第三个坑是内外点阈值用“单边距离”。在基础矩阵估计里有些同学只算左图重投影到右图的单向像素误差这样阈值会漏掉左右不对称的异常情况。稳妥做法是使用双边残差比如对称极线距离或者两图的平均重投影误差。虽然计算量翻倍但在挑剔的场景里值得。第四个坑是RANSAC不固定随机种子。调试算法时如果不固定随机种子每次运行内点数不一样几乎没法定位到底是算法问题还是运气问题。我调试阶段一定固定种子基准效果确认后再放开随机性做统计评估。5.3 从模拟数据到真实数据的效果对照为了直观说明我整理了一张在不同数据状态下的方法效果对照表。需要说明的是这是我从多个项目里总结出来的经验规律具体的量化数字会随场景变化但排序关系基本稳定。数据状态纯最小二乘RANSAC 最小二乘最小二乘 鲁棒核RANSAC 鲁棒核接力干净数据高斯噪声最优稍差阈值误杀少量内点稍差核函数轻微扭曲噪声与纯最小二乘接近少量外点10%明显偏移好较好最好大量外点30%~50%完全失效较好敏感于初值容易局部最优最好有渐变离群值无清晰内外点偏移硬切会损失信息较好最好对我个人而言最省心的组合是先用固定随机种子的RANSAC粗筛选Huber核做优化优化后按残差分布再剔一轮外点最后用最小二乘收尾。这套流程我在视觉里程计初始化、激光点云配准和结构光重建里反复用过稳定性和精度都比较令人满意。最后再分享一个小技巧在Tukey核里把 σ 设成接近RANSAC内点阈值它就变成了一个“软RANSAC”状态既保留了RANSAC的剔除效果又让阈值边缘的数据有机会通过权重渐变参与优化。这个用法在一些内外点边界模糊的点云场景里特别有效。如果你正在调试基础矩阵或者点云配准总是不稳可以先从检查这四个问题开始随机种子固定了吗内点阈值给了物理意义吗核尺度是用MAD估的吗RANSAC之后做了refit吗把这四个点逐一落实鲁棒估计的坑就能避掉大半。