Home / 机器人经典基础 / TEASER：错误匹配占多数时，怎样配准点云并检查答案

096｜TEASER：错误匹配占多数时，怎样配准点云并检查答案

论文：Heng Yang、Jingnan Shi、Luca Carlone，TEASER: Fast and Certifiable Point Cloud Registration，2020。原文 v2 · 官方代码 · 官方使用文档。

先接住前作的问题

Horn配准能高效解正确对应下的最小二乘，RANSAC则在极低内点率时付出昂贵抽样；TEASER把几何不变量、截断估计和认证组合起来处理这一瓶颈。

五个前置概念

刚体变换：旋转和平移保持点之间距离。
内点与外点：前者符合共同观测模型，后者不服从该模型。
鲁棒损失：限制大残差对估计的影响，但不会修复错误模型。
松弛与对偶证书：借助更易检查的问题给出目标值或最优性信息。
可辨识性：即使计算无限精确，观测也必须能区分所求参数。

一、问题设定：大量错误对应下怎样分解变换并检查鲁棒解

扫描同一房间两次，怎样知道第二次扫描相对第一次转了多少、移了多远？如果对应点都正确，求一个刚体变换并不难。真正麻烦的是，算法可能把不同椅子的椅脚配到一起，把重复窗框当成同一个位置。

问题定义：先写清楚输入承诺

令输入对应为 $(a_i,b_i)$ ，理想情况下：

$b_i=sRa_i+t+\epsilon_i, \qquad R^TR=I,\quad \det R=1,\quad s>0.$

其中 $R$ 是旋转、 $t$ 是平移、 $s$ 是尺度。用同一类已标定传感器扫描，往往可直接固定 $s=1$ ；不同来源的数据可能还要估计尺度。对应点不一定正确，因此该关系只应约束内点，而不能强迫所有输入都服从它。

这属于几何估计，不需要策略、动作、奖励或训练回合。输出是一组变换参数及相关诊断信息。它可以服务于机器人定位，但单次点云配准并不自动构成完整 SLAM。

普通平方误差会给极大残差极大影响。一个离群点的残差从 10 增到 100，平方损失从 100 增到 10000；几个错误对应就可能压过大量小残差。另一方面，随机抽样也受内点比例影响：若每次需抽中三个内点，内点比例 $w$ 下单次成功概率约为 $w^3$ 。这是独立抽样的教学近似，说明为何极低内点率很昂贵，不是 RANSAC 所有实现的精确运行时间模型。

二、利用不变量分离变量，再求截断估计和证书

截断损失究竟改变什么

一种标准截断最小二乘写法是：

$\min_{s,R,t}\sum_i\min\left( \frac{\|b_i-sRa_i-t\|^2}{\beta_i^2},c^2\right).$

$\beta_i$ 表示允许的噪声尺度， $c^2$ 是损失上限。超过阈值以后，残差继续增大也不再无限增加代价。它改变了数学目标中的异常值权重；并没有直接让非凸优化变容易，也不能知道每个点的真实标签。

例如两个候选变换分别产生残差 $[0.1,0.1,8]$ 和 $[2,2,2]$ 。平方和会偏向第二组，截断上限设为 1 时，第一组为 1.02，第二组为 3。这个自构例子体现了“解释一个一致子集”的倾向；如果错误对应本身形成更大的伪一致集，这种倾向也可能选错。

用相减消掉平移

对两个正确对应相减：

$b_i-b_j=sR(a_i-a_j)+(\epsilon_i-\epsilon_j).$

平移 $t$ 消失了。再取长度，利用旋转保长度性质，可以得到尺度线索。已知尺度时则可直接跳过尺度求解。这里的思想是消去不需要的未知量，而不是同时在七维变换空间中盲搜。

代价也可从公式直接看出：两个带噪点相减，噪声不会神奇消失；不同差分若共享原点，误差还会相关。过短基线的长度比也可能不稳定。实现时必须携带适合差分观测的噪声界，不能把原始点噪声参数不加思考地复制过去。

尺度线索还有可计算的区间。设原始内点满足 $\|\epsilon_i\|\le\beta_i$ ，记 $A_{ij}=\|a_i-a_j\|>0$ 、 $B_{ij}=\|b_i-b_j\|$ 。反三角不等式给出 $|B_{ij}-sA_{ij}|\le\beta_i+\beta_j$ ，所以该对点允许的尺度范围是

$s\in\left[\frac{B_{ij}-\beta_i-\beta_j}{A_{ij}},\frac{B_{ij}+\beta_i+\beta_j}{A_{ij}}\right]\cap(0,\infty).$

分母越短，区间越宽，说明近邻短基线未必是好的尺度测量。这些区间只有在两端都为内点时才必须包含真值；外点也可能偶然投票到同一区域。

原创标量 TLS 手算。 假设三个尺度测量为 $1,1.2,5$ ，噪声尺度均为 $0.2$ 、截断上限为 1。它们对应区间 $[0.8,1.2]$ 、 $[1,1.4]$ 、 $[4.8,5.2]$ 。在前两个区间的重叠部分，未截断项的最小二乘解是均值 1.1，总代价为 $0.25+0.25+1=1.5$ ；只满足第三个测量时，最优取 5，总代价为 2；只满足一个前部测量也至少有两个饱和项，无法低于 2。因此 1.1 是此例全局解。

原文VII节算法2用排序后的区间端点枚举不同一致集合，再比较候选的 TLS 代价。它不只是选“票数最多”的区间中心；相同内点数还要比较区间内拟合质量。这个标量可精确求解的结构解释尺度和平移分量为何较易处理，不能据此推论三维旋转也变成同一种一维投票问题。

兼容图、旋转求解和证书

把对应关系视为顶点，把几何相容关系视为边，就能寻找彼此相容的候选集合。相容只是必要筛选线索，不应被读成“图中每条边都是真实对应”。最大团也不是任意规模上都有廉价保证的问题。

论文 §VI–VIII 给出 TEASER 的分解与松弛路线，§X 则给出 TEASER++ 的快速实现。理解两者最实用的方式，是把它们分成“产生候选解”和“判断候选解质量”。快速迭代取得一个旋转估计，不代表默认调用已经完成所有认证步骤。

官方文档的接口输入是两份按列对应的 $3\times N$ 矩阵，并暴露噪声界、是否估计尺度和旋转求解设置。由此可见，核心求解器并不替用户解决特征检测、数据单位、传感器标定和全部对应构造问题。

不变量分解改变求解对象，鲁棒目标和证书仍有各自条件。下面检查输出是否满足目标与几何承诺，再读高外点率实验。

三、执行筛选与求解，用错误对应检查目标含义

输入：候选对应 A、B；噪声界；尺度是否已知
检查坐标单位、对应列和退化几何
构造消去平移的差分几何约束
若尺度未知：鲁棒估计尺度
利用几何兼容关系筛选候选对应
鲁棒求解旋转：TEASER 与 TEASER++ 使用不同求解路线
在尺度、旋转确定后估计平移
若业务需要证书：单独运行对应认证，并记录覆盖范围
输出变换、残差、筛选结果及认证状态

这是模块级教学伪代码，不是论文 Algorithm 的逐行复制。“未获证书”应保留为一个状态，不能自动翻译成“物理位置错误”；反过来，“证书通过”也不是传感器和场景绝不会出错的证明。

一个自构检查与五个前置概念

构造一组不对称四面体点，施加已知旋转和平移，再加噪声和错误对应；另构造一个高度对称方格。保持点数与异常值比例相同，比较真值误差、目标值、认证状态和用时。这个未运行的实验用来追问：决定成功的是异常值比例，还是剩余信息是否足以唯一确定答案？只画一条平均成功率曲线会掩盖这个差别。

进阶检查：几何歧义为什么不能靠异常值比例排除

这项进阶追问的参考答案： 异常值比例只描述污染量，不能单独保证变换可辨识。不对称四面体的充分非共线正确对应通常能约束唯一刚体变换；高度对称点集若又允许交换对应，则多个变换可能具有相同几何一致性。应固定噪声界与正确对应数量，分别改变几何对称性，并同时检查真值旋转／平移误差、候选目标值及认证间隙；若目标值相近、认证通过而真值误差大，先检查对称等价和对应假设，而不是把证书解释成传感器真值保证。这个结论是实验设计的条件性预期，实际成功率仍须运行后报告。

四、读外点比例、几何与时间的联合条件

Fig. 6：按列区分已知尺度、极端异常值与未知尺度，再按行比较旋转、平移、尺度误差与时间 — 原论文结果图／表摘引：Heng Yang、Jingnan Shi、Luca Carlone（2020），Fig. 6，PDF 第 15 页；核对原文。原版权保留。

读图：按列区分已知尺度、极端异常值与未知尺度，再按行比较旋转、平移、尺度误差与时间。鲁棒区域与计算成本要共同读，合成异常值比例不能替代任意真实错误对应分布。

认证只回答指定目标是否优化到位；对称场景的可辨识性、噪声界和接受覆盖率仍要另外检查。

检查项	原文证据与评价方式
任务	§XI 的合成对应、物体定位与 3DMatch 扫描匹配
数据性质	合成异常值率可控；真实对应还受描述子和场景重复结构影响
对比	鲁棒配准、不同预算的 RANSAC，以及求解后认证
学习资源	配准后端本身不是训练过程；3DMatch 比较使用学习描述子生成对应
运行预算	表 II 同时列配准与认证时间，不能只引用最快的一行
指标	几何误差、正确配准比例、运行时间；三者不可互换
重复性	模块认证测试报告 Monte Carlo 重复；真实场景表不能据此假定同样重复协议
未确认项	全部随机种子、完整超参数搜索预算及全流水线延迟未逐项核实

重点看三组证据：

图 6 比较异常值率变化下的误差和时间。它适合观察算法何时开始失效；不能把合成异常值分布替换成任意真实错误分布。
表 II 区分普通求解与认证后的结果。以 MIT Lab 为例，TEASER++ 为 83.1%，RANSAC-10K 为 85.7%；普通 TEASER++ 并非每个场景都领先。表中平均时间分别为 0.059 秒和 0.074 秒，而 CERT 行为 238.136 秒。CERT 的正确率按被认证样本统计，不能与全体样本正确率视为相同分母。
图 10–11 检查错误解和认证状态。场景对称可以让数学上合理的对应集合指向错误物理对齐；这正是“最优性”与“真值正确性”分开的实例。

原论文图10：八个场景中TEASER++认证和未认证解的旋转误差散点 — Heng Yang、Jingnan Shi、Luca Carlone（2020），图 10，PDF 第 17 页；原文与图注。原版权保留。

读图：蓝点带有算法证书但并非都贴近零误差；对称场景会让数学最优与语义配准正确性分离。

原论文图11：Hotel3淋浴间点云真值和TEASER++估计的俯视、侧视对照 — Heng Yang、Jingnan Shi、Luca Carlone（2020），图 11，PDF 第 17 页；原文与图注。原版权保留。

读图：左右相似几何可支持接近180度的错误姿态；证书验证既定目标，不排除数据本身的歧义。

上述数字来自原文表 II；比较范围是该实验的对应、硬件与实现。作者的鲁棒性主张有这些实验支持，但并不形成“任意输入都实时且正确”的结论。

对称性还可以直接验算：无标号点集若恰好是正方形四角，绕中心旋转90度会把它置换回同一集合。集合重合不区分这两个朝向；额外的不对称几何或可信对应才可能消除歧义。这不是“所有方格匹配都会失败”，而是为正文的可辨识性条件提供一个明确的极端构造。

五、区分数学认证、物理对应和噪声承诺

真正值得学习的研究方式，是把结果质量从一句“看起来对了”变成可分析的对象：建模哪些观测可信、哪些子问题能精确求解、什么条件能事后检查。它同时连接几何不变量、鲁棒统计和优化理论。

以下是根据方法作出的分析：如果点云只有一条直线，绕直线的旋转可能无法唯一确定；如果场景充满重复构件，错误对应可能共同支持另一个变换；如果噪声界设得过紧，真实点也会被当作异常。如果阈值过松，鲁棒损失的筛选作用则会减弱。

因此，选择阈值不应只问“哪个数在这一帧最好”，而要问传感器误差、体素降采样和外参误差共同允许多大偏差。最终系统还可结合时间连续性、可见性和其他传感器检验位置，但这些额外约束不属于单次配准结果自动获得的能力。

六、与连续扫描局部配准互补

平行路线：KISS-ICP：把简单基线做好，究竟能走多远。连续扫描用局部预测获得好初值，与全局鲁棒对应估计互补。

七、自测与参考答案

1．为什么相减能去掉平移，却不能保证去掉错误匹配？

答：同一个真实刚体变换中的平移是共享常数，因此相减会消去它。错误对应没有共同变换关系，即使相减后形式相似，也未必满足同一个旋转。代数消元消掉的是未知量，不是数据错误。

2．认证通过，是否足以让机器人相信这就是正确房间位置？

答：不足以。证书针对明确的数学问题及其条件；重复几何、错误传感器模型或另一组更自洽的错配，都可能使优化目标与真实位置不一致。还应检查可辨识性和独立观测。

3．怎样公平比较一个有拒绝机制的方法与一个总输出答案的方法？

答：至少同时报告全体输入数量、接受覆盖率、接受样本正确率、总体正确接受率、错误接受率和总计算时间。只展示被接受子集的高正确率，会隐藏拒绝了多少困难样本，也无法反映系统可用性。