跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2610.27275 · v2

On Maximum Clique and Maximum Consensus Formulations in Point Cloud Registration

首次提交 2026-10-20 04:47
版本更新 2026-11-17 04:27
雷达观测 2026-11-18 19:44
arXiv ↗PDF ↗

摘要

Maximum clique and maximum consensus are widely used formulations for robust point cloud registration. Maximum consensus seeks one transformation that aligns as many matches as possible, while maximum clique selects matches through pairwise distance tests. Maximum clique is often used as a substitute for or an approximation to maximum consensus, with empirical evidence suggesting a close relationship. However, how closely the two formulations agree is not fully understood. We study this relationship theoretically. We show that, at any fixed positive tolerance, a maximum clique can have arbitrarily large alignment error and be arbitrarily larger than a maximum consensus set. When rotation is fixed, we derive sharp error bounds and tests that exactly characterize maximum consensus for the translation subproblem. We also study group-kk consistency, which uses consistency of groups of kk matches, and determine the smallest group sizes that guarantee alignment error bounds independent of point cloud scale and geometry. These are d+1d+1 for rotations and translations and d+2d+2 when reflections are allowed, in dimensions d≥2d\ge2. Finally, our experiments on nearly 8,000 registration examples quantify the frequency of these limitations in practice and show how the derived bounds can be used to check whether a subset of matches can be aligned within a point tolerance.

作者备注:35 pages (22-page main article and 13-page supplementary material), 10 figures. Interactive examples and Lean proof verification: https://ariarobotics.github.io/mc-vs-mc-registration/

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-17 04:27 · 最新观测版本

On Maximum Clique and Maximum Consensus Formulations in Point Cloud Registration

Maximum clique and maximum consensus are widely used formulations for robust point cloud registration. Maximum consensus seeks one transformation that aligns as many matches as possible, while maximum clique selects matches through pairwise distance tests. Maximum clique is often used as a substitute for or an approximation to maximum consensus, with empirical evidence suggesting a close relationship. However, how closely the two formulations agree is not fully understood. We study this relationship theoretically. We show that, at any fixed positive tolerance, a maximum clique can have arbitrarily large alignment error and be arbitrarily larger than a maximum consensus set. When rotation is fixed, we derive sharp error bounds and tests that exactly characterize maximum consensus for the translation subproblem. We also study group-kk consistency, which uses consistency of groups of kk matches, and determine the smallest group sizes that guarantee alignment error bounds independent of point cloud scale and geometry. These are d+1d+1 for rotations and translations and d+2d+2 when reflections are allowed, in dimensions d≥2d\ge2. Finally, our experiments on nearly 8,000 registration examples quantify the frequency of these limitations in practice and show how the derived bounds can be used to check whether a subset of matches can be aligned within a point tolerance.

查看此版本解读 →查看此版本原文 ↗