arXiv：cs.LG· Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome·· 4 小时前AI 评分48
Rubix：通过分配几何实现全局无对应点集对齐
Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry
AI 导读
Rubix 提出一种在平方欧氏损失下全局求解等权平面点集对齐的方法，每个匹配定义复相关，其凸包构成"排列多边形"，最远顶点即全局最优对齐。团队证明了 n≥2 时 n(n-1) 个顶点的紧界，回答了 Rote 的旋转-分配开放问题，精确算术下以 O(n^5) 次操作恢复该多边形。在 MPEG-7 形状对上，Rubix 平均 12 ms 达到所有数值参考值，比旋转网格法快 50 倍。
正文
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.
| Comments: | 67 pages, 20 figures. Includes full proofs and experimental appendices |
| Subjects: | Computer Vision and Pattern Recognition (cs.CV); Computational Geometry (cs.CG); Machine Learning (cs.LG); Robotics (cs.RO); Optimization and Control (math.OC) |
| MSC classes: | 68T45 (Primary) 68U05, 90C26 (Secondary) |
| ACM classes: | I.2.10; F.2.2; G.1.6 |
| Cite as: | arXiv:2610.10408 [cs.CV] |
| (or arXiv:2610.10408v1 [cs.CV] for this version) | |
| https://doi.org/10.48550/arXiv.2610.10408 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Subhransu S. Bhattacharjee Mr. [view email]
[v1]
Wed, 7 Oct 2026 16:55:12 UTC (6,837 KB)
来源：arXiv：cs.LG · arxiv.org