Rubix：通过分配几何实现无需对应关系的全局点集对齐
Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry
Subhransu S. Bhattacharjee · Dylan Campbell · Rahul Shome
中文摘要
Procrustes-Wasserstein 对齐方法在没有给定对应关系的情况下联合估计匹配与旋转，但交替最小化容易停留在次优解。Rubix 在平方欧氏损失下全局求解等权平面问题。两个中心化 n 点集之间的每个匹配 σ 定义一个复相关量 z_σ = Σ_i x̄_i y_{σ(i)}，其凸包构成置换多边形（permutation polygon）：支撑顶点给出固定旋转下的最优匹配，最远顶点给出全局对齐。论文证明了当 n≥2 时凸包顶点数恰为 n(n-1)，回答了 Rote 提出的旋转-分配开放问题。在精确算术下，分配查询可在 O(n⁵) 运算内恢复该多边形。基于分配的界通过分支定界将该方法推广至三维旋转及在给定平移下的部分匹配。在 MPEG-7 形状对的计时测试中，Rubix 平均 12 ms 内达到所有数值参考精度，比同等精度的旋转网格快 50 倍。其距离度量在真实 3D 扫描的重力对齐匹配、形状检索与含噪晶体分类任务上均优于交替最小化。
关键要点
- 01问题：Procrustes-Wasserstein 对齐中的交替最小化会陷入次优解，缺乏全局保证
- 02方法：将匹配编码为复相关量，其凸包（置换多边形）的支撑顶点与最远顶点分别给出最优匹配与全局对齐
- 03结果：在精确算术下 O(n⁵) 恢复凸包，证明顶点上界恰为 n(n-1)；MPEG-7 上平均 12 ms、比旋转网格快 50 倍
- 04结果：在真实 3D 扫描重力对齐、形状检索与含噪晶体分类上均优于交替最小化
- 05推广：通过分支定界将分配界方法推广至三维旋转及给定平移下的部分匹配
解读
尚无解读。
原始英文摘要
arXiv:2610.10408v1 Announce Type: cross Abstract: Procrustes-Wasserstein alignment jointly estimates a matching and rotation without supplied correspondences, but alternating minimization can stop at suboptimal solutions. Rubix solves the equally weighted planar problem globally under squared Euclidean loss. Each matching $\sigma$ of two centered $n$-point sets defines a complex correlation $z_\sigma=\sum_i\bar x_i y_{\sigma(i)}$. Their convex hull is the permutation polygon: supporting vertices give optimal matchings at fixed rotations, and the farthest vertex gives the global alignment. We prove the sharp bound of $n(n-1)$ vertices for $n\ge2$, answering Rote's rotation-assignment open problem. In exact arithmetic, assignment queries recover the polygon in $\mathcal O(n^5)$ operations. Assignment-based bounds extend the approach to three-dimensional rotations and partial matching at a supplied translation through branch-and-bound. On timed MPEG-7 shape pairs, Rubix attains every numerical reference value in 12 ms on average, 50 times faster than a rotation grid at the same accuracy. Its distances improve gravity-aligned matching of real 3D scans, shape retrieval and noisy crystal classification over alternating minimization.