精读笔记

Problem Setting

论文标题：CliReg: Clique-Based Robust Point Cloud Registration（IEEE Transactions on Robotics / 2025）。

这篇论文针对的是已给定或可预处理得到候选对应关系的刚体点云配准，而不是 correspondence-free registration。真正难点不是 SE(3) 上的最小二乘，而是候选 correspondence 中 outlier 比例高、局部特征不可靠、并且点云局部/全局对称会产生大量“pairwise 看起来一致但整体变换错误”的假结构。

关键矛盾是：图上的 pairwise consistency 是一个很强的离散过滤器，但它不是 maximum consensus objective 本身。一个 clique 只能说明这些匹配在两两距离上可兼容，不保证 LSQ 后在原始点云上得到最多 inliers。以前的 clique-based 方法容易把“最大团”当成最终过滤结果，而这篇论文明确指出最大团在 presence of outliers / symmetry / descriptor ambiguity 下可能是错的。

Motivation

已有方法各有卡点：RANSAC 的问题是高 outlier 下有效采样概率急剧下降；FGR/robust LS 的问题是非凸鲁棒目标在坏 correspondence 下不够稳；Go-ICP 这类全局 BnB 在原始连续空间上搜索过重；TEASER++ 虽然把图结构引入 registration，但其 clique 阶段仍偏向 maximum clique pruning，隐含了最大团接近真实 inlier structure 的假设。

CliReg 的核心观察更细：真实 inlier set 一定诱导 clique，但 clique 不一定是真实 inlier set；而且最大 clique 不一定给出最大 consensus registration。缺口就在这里——已有 clique-based registration 更关注“找最大的一致子集”，而不是“找能诱导最好全局刚体变换的候选子集”。因此作者选择枚举 large maximal cliques，再用 registration fitness 重新排序候选。

Core Idea

论文真正改变的是建模方式：不再把 correspondence graph 的 maximum clique 视为 registration 的等价解，而把 clique 视作 SE(3) hypothesis generator。图结构提供刚体距离不变量的离散筛选，LSQ 将 clique 转成连续变换，maximum consensus fitness 再决定该变换是否真的好。

这个 inductive bias 很合理：pairwise distance consistency 是刚体配准中最廉价、最稳定的约束之一，能大幅减少候选空间；但只用 pairwise consistency 会保留对称性和局部伪解，所以必须回到全局点云层面评估。CliReg 的本质区别不是“用了 clique”，而是把 clique 从 answer 退回到 proposal，并把最终选择权交给 maximum consensus。

Method

1. Correspondence graph：每个顶点是一个 feature-based matching hypothesis，边表示两对匹配在源/目标点云中的内部距离差低于阈值。它解决的是在估计变换前先利用刚体不变量过滤明显不可能共存的匹配。核心变化是把连续 SE(3) 搜索转成稀疏图上的组合候选搜索。

2. Large maximal clique enumeration：CliReg 不枚举所有 maximal cliques，也不只取 maximum clique，而是借用现代 MCP BnB 技术枚举大 maximal cliques。它解决的是候选数量爆炸的问题。必要性在于：所有 maximal cliques 枚举不可行，而单个 maximum clique 又可能错误。

3. Fitness-driven selection：每个枚举到的 clique 通过 LSQ 得到刚体变换，再计算满足 residual threshold 的 inliers。它解决的是 clique size 与 registration quality 不一致的问题。这个步骤是方法的关键闭环：图搜索只负责提出候选，consensus 才是最终目标。

4. KNN / Mutual correspondence control：KNN 控制候选图大小，CliRegMutual 用 mutual nearest feature match 进一步压缩图。它们解决的是 scalability，而不是配准目标本身。这里的贡献更偏 engineering / search budget control。

Key Insight / Why It Works

最重要 insight 是：registration 的好坏不应由 clique size 决定，而应由 clique 诱导出的 transformation 在原始点云上的 consensus 决定。这个判断直接修正了 TEASER++ 式 maximum clique pruning 的一个隐含前提。

方法有效的原因主要有三层。第一，刚体变换保持点间距离，因此真实 inlier 子集天然形成 clique；这给了图搜索一个强 inductive bias。第二，真实数据中的 correspondence graph 经验上很稀疏，outlier 增多反而可能降低图密度，使 MCP/BnB 在实践中比最坏复杂度温和很多。第三，最终用 LSQ+consensus evaluation 把图上的局部一致性转回全局几何一致性，避免最大团被局部对称或 descriptor 假匹配劫持。

我认为核心贡献是“large maximal clique proposal + consensus reranking”这一目标重构，而不是具体用了 partial MaxSAT bound、bitset、vertex ordering 等 clique solver 技术。后者重要但更像借用了成熟 MCP engineering。非增量 branching 顺序、KNN 控图、CliRegMutual 都是有效的工程化加速，但不是最本质的新思想。

从机制归因看，这不是 data scaling，也不是 representation learning；更像是 better inductive bias + test-time combinatorial search。它把 registration 中的 latent structure——匹配之间的刚体一致关系——显式图化，并用 test-time compute 枚举高可信候选。增益有一部分来自现代 clique solver 的 scaling ability，文中没有完全剥离 solver modernization 与建模改变各自贡献。

Relation To Prior Work

最接近的是 TEASER / TEASER++ 和其他 correspondence graph / maximum clique based registration。共同点是都利用 pairwise geometric consistency 构图，并用 clique 过滤 outliers。真正差异在于：TEASER++ 更倾向于把 maximum clique 当作 outlier pruning 的核心结果，再进入后续 decoupled estimation；CliReg 则不 decouple rotation/translation，也不相信最大团必然最好，而是枚举多个大 maximal cliques 并用完整 rigid transform 的 consensus 选择。

相对 RANSAC，CliReg 用系统性图搜索替代随机 sampling；相对 FGR，它把鲁棒性更多放在离散候选筛选和 consensus，而不是连续鲁棒核；相对 Go-ICP，它避免在完整连续空间做全局 BnB，而是在 correspondence-induced graph 上做组合 BnB。

看似新的部分中，MCP 的 coloring bound、partial MaxSAT bound、branching-by-partitioning 等并不是 registration 领域原创，而是把 clique optimization 社区的成熟技术迁移进来。实质创新在于 registration objective 与 clique search 的重新耦合方式：不是 solve maximum clique，而是 use clique enumeration as hypothesis generation for maximum consensus registration。

Dataset / Evaluation

实验覆盖 synthetic Stanford models 和真实 3-DMatch，能支撑“在 feature-based correspondence 有大量 outlier 时，CliReg 比常见 baselines 更鲁棒”的 claim。Synthetic 数据有可控 outlier rate 和 ground-truth fitness，适合验证最大团不等于最大共识这一核心论点；3-DMatch 则说明方法在真实 indoor scan matching 上不是纯 synthetic artifact。

不过 evaluation 仍有边界。Synthetic outlier 是通过移动部分点生成，虽然加入 ToF simulation，但仍不等价于真实场景中的重复结构、动态物体、强遮挡和 descriptor domain shift。3-DMatch 使用固定 keypoints/features 和常见 success threshold，主要验证 pairwise registration，不验证长期 SLAM / deployment 稳定性。Go-ICP 被排除的理由偏经验性，公平性上可以理解但不完全令人满意。

实验最有价值的不是具体胜率，而是 component analysis：CliReg 输出的 clique 往往小于 maximum clique，但诱导的 inlier 数更多。这直接验证了论文的核心建模 claim。相比之下，运行时间优势的归因不完全干净，可能混合了图稀疏性、候选规模、solver 工程和 time limit。

Limitation

最核心限制是 correspondence dependency。若 local features 没有把足够真实匹配放进候选集，后续图搜索再强也无法恢复；因此它不是从根本上解决配准，而是解决“给定一个还算覆盖真实匹配的 noisy correspondence set 后如何鲁棒选择”的问题。

第二，ξ 的定义很关键但相对粗糙。它同时用于建图和 consensus threshold，过紧会断开真实 clique，过松会制造大量伪 clique。文中虽用点云 resolution 给出经验定义，但不同传感器噪声、非均匀采样、局部密度变化下是否稳定，文中未充分说明。

第三，scalability 上限仍由 |M|×k 的图规模和 clique search 决定。作者强调 sparse graph 使 MCP easy in practice，但这不是理论保证。对重复结构、高对称 CAD/indoor scenes、低 overlap、dense ambiguous features，图可能出现大量大小相近的 maximal cliques，搜索会退化。文中也观察到低 outlier 时有时更慢，这说明瓶颈不只是 outlier rate，而是 clique plateau 和图结构。

第四，CliRegMutual 的速度来自强剪枝 correspondence，本质上是牺牲 recall 换 runtime。它的鲁棒性上限受 mutual matching 假设限制，在 descriptor 不对称或 partial overlap 严重时可能丢掉关键 inliers。

第五，部分增益可能主要来自 engineering / scaling：现代 MCP solver、bitset、branching、partial MaxSAT bounds 这些对结果很重要，但不是 registration-specific theory。论文没有充分做 ablation 来量化“枚举 maximal cliques + fitness”与“更强 clique solver”分别贡献多少。

Takeaway

• 1. 对 clique-based registration 来说，最大团不是正确目标；更合理的是把 clique 当作 transformation proposal，再用 maximum consensus 选解。
• 2. Pairwise rigidity graph 是一个很强的 test-time inductive bias：它把 noisy correspondences 中的 latent geometric consistency 显式化，适合与 combinatorial search 结合。
• 3. 这个方向未来更值得做的是 weighted / probabilistic correspondence graph，把 descriptor confidence、局部几何可靠性、边的不确定性和 consensus objective 统一起来，而不是继续只追求更快的 unweighted MCP。
• 4. CliReg 的经验成功依赖 graph sparsity 和 correspondence recall。

一句话总结

CliReg 是 clique-based robust registration 从“找最大团过滤 outliers”向“枚举大团生成候选并用最大共识重排序”演化的一步，核心贡献在于纠正了 maximum clique 与 best registration 之间的错误等价。