Rubix speeds up global point set alignment without known matches
Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry
Computer Vision and Pattern RecognitionComputational GeometryMachine LearningRobotics
Summary
Aligning two sets of points to find their best match and rotation is a challenge when you don't know which points correspond. The authors created Rubix, a method that solves this alignment exactly and quickly by considering a geometric shape formed by possible matches. This approach is faster and more accurate than previous methods, and it works well on real 3D scans and shape comparisons. They also proved new mathematical limits on the complexity of the problem.
What this means in practice
- •For 3d modeling teams: Improve alignment of 3D scans to enhance shape comparison and registration accuracy using Rubix’s faster global matching algorithm.
- •For computer vision engineers: Accelerate shape retrieval systems by integrating Rubix to achieve global alignment without requiring known point correspondences.
Authors
Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome
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 $σ$ of two centered $n$-point sets defines a complex correlation $z_σ=\sum_i\bar x_i y_{σ(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.