Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry

Subhransu S. Bhattacharjee; Dylan Campbell; Rahul Shome

cs.CVOct 7, 2026

Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry

Authors: Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome

Organizations: School of Computing, Australian National University

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.

Figures & tables

Figure 2: Rubix on an exact six-point example. (a) The permutation polygon is the convex hull of matching correlations

z_{\sigma}=\sum_{i}\bar{x}_{i}y_{\sigma(i)}

. An assignment query in direction

u

finds an extreme correlation beyond an unexplored chord (dashed); 36 queries recover all 18 vertices. The farthest vertex

z^{\star}

gives the optimal matching and rotation

\theta^{\star}=-\Arg z^{\star}

; AM stops at

z_{\mathrm{AM}}

. (b) The objective

J(\theta)=\min_{\sigma}\{S-2\operatorname{Re}(e^{\mathrm{i}\theta}z_{\sigma})\}/n

over one turn, where

S=\sum_{i}|x_{i}|^{2}+\sum_{j}|y_{j}|^{2}

. Each smooth piece belongs to one polygon vertex. AM (orange) reaches a local minimum; dashed arrows join its reassigned iterates. The global minimum is blue. Rubix never samples this illustrative landscape. (c) Fixed

X

and rotated

Y

at the initial pose, AM fixed point and global optimum, each with its minimizing matching, in a common frame and scale.

Figure 3: A fixed phase budget bounds the number of matching changes (

n=7

). (a) While one matching stays optimal, the phase

\Psi

decreases with slope

-\binom{n}{2}

; when the optimal matching changes, it jumps by

\Delta\Psi=\pi(L-1+2I)

. The number above each jump is

\Delta\Psi/\pi

. Over one turn, the continuous decrease and the jumps both total

42\pi

. Each jump is at least

\pi

, so the 16 polygon vertices of this example satisfy the bound

n(n-1)=42

. (b) The highlighted jump of

6\pi

: its reassignment cycle visits

L=5

points counterclockwise and encloses

I=1

further point (star).

Figure 4: Gravity reduces 3D alignment to a bounded yaw search. A nine-point complete-matching example. (a) Gravity directions

g_{x},g_{y}

give leveling rotations

A_{x},A_{y}

, leaving yaw

\theta

about

e_{3}

; heights (stems) remain in every edge cost. (b) Rubix bounds the blue arc from

u_{-}

u_{+}

u(\theta)=(\cos\theta,\sin\theta)

by querying its endpoints and tangent intersection

u_{A}

. (c) The affine interpolant stays below the residual, nearly reaching its minimum (

2.734

versus

2.765

); the minimum vertex value (

1.458

) and independent-edge bound (

1.547

) are looser. (d) Algorithm 2 prunes arcs whose bound reaches incumbent

U

and refines the rest. Nine evaluations close the gap at

48.2^{\circ}

. Residuals are summed squared errors. Partial matching fixes translation or uses Section 7.2 .

Input and correspondences	Pose variables	Assignment oracle	Scope of the construction
Known gravity; complete bijection	Yaw; translation by centering	Square linear assignment	Global yaw, translation, and matching
Known gravity; partial matching	Yaw at supplied translation	Prescribed-cardinality or penalized assignment	Global conditional on that translation
Known gravity; partial matching	Yaw and translation	Partial assignment with a forced anchor	Global joint search over a finite anchor cover
Unrestricted rotation; complete bijection	Proper rotation; translation by centering	Square linear assignment	Global complete SE(3) registration
Unrestricted rotation; partial matching	Proper rotation at supplied translation	Prescribed-cardinality or penalized assignment	Global conditional on that translation

Table 1: Scope of the spatial constructions. “Global” refers to the stated objective and to a search in exact arithmetic that is run to a positive tolerance. Partial matching means either a prescribed cardinality or a penalty on unmatched points.

Figure 5: Bounding rotations through quaternion lifts. (a) An illustrative chart cell

\tilde{q}=(1,\xi_{1},\xi_{2},\xi_{3})

with

\xi_{1},\xi_{2},\xi_{3}\in[-\tfrac{1}{2},\tfrac{1}{2}]

. Its eight raw corners (teal) define the cell, and its central segment

\xi_{1}=\xi_{2}=0

(blue) contains the pure yaw rotations. (b) On this yaw section, in the coordinates

(Q_{00}-Q_{33},2Q_{03})

Q=qq^{\top}

and not of the raw quaternion, the endpoint lifts

Q_{\pm}

and the exterior cross lift

B_{-+}

enclose the arc of physical rotations (blue). Assignment values at these query matrices bound the correlation score throughout the region. The full three-dimensional construction uses at most 36 queries per box before reuse; the illustrated section uses three.

Figure 6: Observed polygon sizes remain below the worst-case bound. Gaussian, MNIST-digit and noisy-copy pairs, timed serially on one thread. (a) Median vertex count (dots) and range across the three families, with the sharp bound

n(n-1)

(dashed). (b) Median time per pair for full polygon reconstruction, the pruned Rubix search, a 360-angle grid and AM (PCA). Full reconstruction stops at

n=200

Method	Excess (%)	Time ratio	Excess (%)	Time ratio	Excess (%)	Time ratio
	MPEG-7 ( $n=64$ )		Gaussian ( $n=50$ )		Lattice ( $n=24$ )
AM (PCA) [ 2 ]	29.5	$0.33\times$	58.0	$0.32\times$	81.0	$0.48\times$
Fiedler–W, original [ 2 ]	63.0	$\mathbf{1.54}\times$	81.5	$\mathbf{2.04}\times$	87.5	$\mathbf{6.02}\times$
Fiedler–W, reproduced [ 2 ]	63.0	$0.75\times$	81.5	$0.85\times$	88.0	$\mathbf{1.96}\times$
Ping-Pong, reproduced [ 25 ]	77.0	$\mathbf{33.6}\times$	89.5	$\mathbf{27.0}\times$	88.5	$\mathbf{22.3}\times$
Stochastic WP, LAP variant [ 28 ]	79.5	$\mathbf{289}\times$	91.0	$\mathbf{254}\times$	94.0	$\mathbf{301}\times$

Table 2: Published planar solvers on 600 fixed pairs. Each family has 200 pairs. Excess is the percentage of costs more than

1\%

above Rubix’s double-precision reference. Ratios are paired median solver/Rubix times including initialization; bold marks minimum excess and ratios above one. Both Fiedler–W implementations use identical inputs and processor, timed separately against Rubix. Every output is valid; Section F.7 gives adaptations.

Method	Excess	LAPs	ms	Excess	LAPs	ms	Excess	LAPs	ms
	MPEG-7 ( $n=64$ )			Gaussian ( $n=50$ )			Lattice ( $n=24$ )
APM [ 46 ]	0.0	551	245.1	0.0	562	179.2	0.0	556	133.8
RPM-PA [ 48 ] , $\varepsilon_{\mathrm{RPM}}=0.3$	45.5	10	10.6	66.0	10	9.3	53.0	10	8.2
RPM-PA [ 48 ] , $\varepsilon_{\mathrm{RPM}}=0.01$	4.5	26	27.9	13.5	36	33.1	5.0	38	32.1
RPM-PA [ 48 ] , $\varepsilon_{\mathrm{RPM}}=0$	0.0	50	59.7	0.0	60	57.8	0.0	54	46.5
Rubix	0.0	25	5.8	0.0	30	4.2	0.0	31	1.2

Table 3: Global solvers on 600 planar pairs. Complete similarity matching on Table 2 ’s inputs. Excess is the percentage of costs more than

1\%

above the reference; assignments and milliseconds are single-core medians. RPM-PA is our implementation, sharing Python and SciPy assignment with Rubix; original APM runs under Octave with C++ assignment ( Section F.7 ). RPM-PA’s published tolerance is

\varepsilon_{\mathrm{RPM}}=0.3

; zero tolerance exceeds 120 s on 70 pairs. Bold marks the fewest assignments and lowest time among zero-excess methods.

Distance	Bullseye (%)	1-NN (%)	mAP (%)
Rubix	67.4	92.5	59.2
AM (PCA) [ 2 ]	65.5	91.6	57.1
AM (GW) [ 4 ]	56.4	88.6	48.1
GW [ 4 , 26 ]	56.3	88.6	47.3
SEINT [ 52 ]	36.2	63.1	24.1
SEINT, best setting [ 52 ]	41.6	67.4	29.4

Table 4: Retrieval on all 1,400 MPEG-7 silhouettes (

n=64

), measured by bullseye score, leave-one-out 1-NN accuracy and mean average precision (%). The first three rows are PW distances computed by the named solver. GW is the Gromov–Wasserstein distance, SEINT [ 52 ] is an SE(2)-invariant transport metric, shown in its original classification setting and in the best of its 14 tested settings, and

W_{2}

is the 2-Wasserstein distance without rotation. Bold marks the highest score in each column.

Method	$\sigma_{\mathrm{noise}}=0.04$	$0.08$	$0.12$	$0.16$	$0.20$
Fiedler–W, original [ 2 ]	$85.0\pm 2.2$	$77.7\pm 3.6$	$67.0\pm 2.5$	$55.3\pm 5.0$	$41.5\pm 3.5$
Ping-Pong, reproduced [ 25 ]	$85.0\pm 6.4$	$77.7\pm 4.5$	$66.8\pm 5.0$	$57.3\pm 3.5$	$42.5\pm 4.8$
Rubix	$\mathbf{97.8}\pm 0.8$	$\mathbf{92.7}\pm 2.8$	$\mathbf{88.7}\pm 1.9$	$\mathbf{82.3}\pm 2.5$	$\mathbf{64.0}\pm 6.1$

Table 5: Published solvers as distance subroutines for lattice classification. Accuracy is the mean

\pm

sample standard deviation (%) across three draws, which total 600 tests per noise level. Bold marks a higher mean accuracy than both other solvers. These draws are shared with the descriptor and GW comparisons and differ from the five draws of Table A.5 ( Section F.7 ).

Figure 7: Rotation error against overlap, controlled and real. (a) Every test instance of the anchored planar sets that share the given fraction of points (200 per fraction, validation-selected settings), offset horizontally by method. (b,c) All identified ETH scan pairs of Li et al. with the reference translation supplied, each GW method at its best setting, against (b) the fraction of source voxels with a target voxel within $0.3$ m at the reference pose and (c) the number of source points that the penalized model matches at the reference pose. The dashed line marks the $5^{\circ}$ success threshold; errors below $0.03^{\circ}$ are drawn at $0.03^{\circ}$ .

	Partial overlap				Defective lattices
	Rotations (%), shared			Failures	Accuracy (%), defect rate
Method	0.75	0.5	0.3	solver/obj.	0	0.1	0.2	0.3
Rubix, unbalanced	99.5	99.0	99.0	0/5	100.0	99.0	94.5	90.5
Rubix, balanced	59.5	28.5	10.5	0/403	98.0	80.5	66.5	60.0
AM, 16 starts	99.5	98.5	88.5	26/3	95.5	99.0	94.5	90.5
UGW [ 68 ]	83.5	43.0	20.0	207/100	100.0	94.0	78.0	69.0

Table 6: Penalized matching with global search. Left:

5^{\circ}

rotation recovery on anchored synthetic sets (200 tests per overlap), and solver/objective failures over all 800. Right: lattice 1-NN accuracy at noise

0.08

, vacancy rate as shown and half as many interstitials, against defect-free references (200 queries per column). Settings are validation-selected; Tables A.11 and A.12 retain every cell, best test baselines and SEINT. Bold marks the best value.

Figure 8: Partial alignments found by Rubix and missed by unbalanced GW. (a) 40-point sets with 30% overlap: targets are rings (shared targets dark); rotated sources are solid when shared. Titles give rotation errors. (b) A noisy square neighborhood ( $\sigma_{\mathrm{noise}}=0.08$ ): observed atoms are rings and the site a cross-hair. Each nearest reference is aligned and bonded, solid when matched, hollow otherwise; unmatched observations are crossed. Predicted classes appear below. Balanced Rubix uses 24 atoms. (c) Planar scans, with gray targets and reported pose errors. (d) ETH Office from above, floor/ceiling removed, with gray targets, supplied reference translation and reported yaw errors. Each panel uses the first dataset-ordered case where Rubix succeeds and displayed baselines fail ( Section F.9 ).

Method	Time (s)	Nodes	Paired speedup	Pose success
GLORES [ 20 ]	2.330	2,374.5	$1.000\times$	189/212
GLORES + vertex bound [ 20 ]	2.315	2,263	$0.996\times$	189/212
GLORES + Rubix arc bound [ 20 ]	2.103	2,035	$\mathbf{1.067}\times$	189/212
GLORES + Rubix, common translation [ 20 ]	1.608	1,352	$\mathbf{1.331}\times$	190/212

Table 7: Replacing the bound inside native GLORES [ 20 ] . All four variants complete the 240 configurations at the same numerical tolerance of

1\%

, with the same trimmed objective and numerical safeguards ( Section F.8 ). Times and nodes are medians; the speedup is the median paired ratio of the native time to the time of the variant, with preprocessing and bound evaluation included. Bold marks improvements over native GLORES. Pose success requires a translation error of at most

0.25

m and a yaw error of at most

2^{\circ}

on the 212 configurations with motion-capture references; the 28 configurations without references count toward the runtime only. Native PLICP [ 16 ] , which has its own point-to-line objective and no global bound, registers 146 configurations in a median of 0.0118 s from the zero pose and 185 in 0.2286 s from 16 initial yaws.

Subsolver	Reference attained	Gap closed	Assignments	Total (s)	Median (ms)
AM	22/96	0/96	338	0.062	0.58
Independent-edge bound	96/96	96/96	224,508	13.910	138.78
Vertex bound	96/96	96/96	5,544	0.232	2.44
Rubix interpolant	96/96	96/96	2,226	0.144	1.46

Table 8: Gravity matching on ETH subsets. Six pairs and 16 yaws give 96 fixed 32-point problems per solver. Global solvers share the host and target mean-squared gap

10^{-5}

m 2 within five seconds on one core; AM supplies no lower bound. Assignments and total time sum all problems; bold marks reductions from the vertex bound ( Section F.10 ).

Figure 9: Faster yaw search under three matching models. Median times and interquartile ranges over 72 scenes, including unresolved runs: (a) complete matching after centering; (b) prescribed-cardinality and (c) penalized matching at fixed translation. Rubix and the vertex bound close every gap. From coarse to fine targets, the independent-edge bound closes 72, 72, 50 gaps in (a), 72, 72, 67 in (b), and all 72 in (c). At

10^{-6}

, paired median vertex/Rubix time ratios are

1.38

1.35

1.21

Figure 10: Witness bounds close more joint yaw–translation gaps. Each curve counts solved scenes out of 24 under (a) prescribed-cardinality and (b) penalized matching, at a summed-squared gap of

10^{-4}

. Triangles mark unresolved runs’ last observed times; the dotted line marks 10 s. Full-face closes 20 and 15 gaps, one-assignment 18 and 15, the independent-edge bound 11 and 9, and gated bounds 17 and 15. All 192 runs are included.

Figure 11: Rubix closes every spatial-alignment gap. Complete SE(3) alignment with a 15 s limit and mean-squared gap target

10^{-5}

. (a) Solved scenes against time. (b) Paired times; points below the diagonal favor Rubix, and triangles mark nine host timeouts whose completion times are unknown. Both variants return identical poses and matchings throughout; total CPU time includes initialization, assignments, bounds and feasible updates.

Appendix figures & tables32 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	Representative matchings or couplings	Algorithm and reference
$d=1$ , reflections $\{\pm 1\}$	Two: sorted and reversed	$\mathcal{O}(n\log n)$ by sorting
$d=2$ , rotations, uniform weights, $n\geq 2$	At most $n(n-1)$ ; tight	$\mathcal{O}(n^{5})$ ; at most $2n(n-1)$ assignments (Theorem 2 )
$d=2$ , rotations and reflections, $n\geq 2$	At most $2n(n-1)$	$\mathcal{O}(n^{5})$ (Corollary 10 )
$d=2$ , rotations, uniform weights, $n$ versus $m$ points	At most $\max\{1,N_{\mathrm{uni}}(N_{\mathrm{uni}}-1)\}$ , where $N_{\mathrm{uni}}=\operatorname{lcm}(n,m)$	Polynomial by duplication (Corollary 8 )
$d=2$ , rotations, rational weights with denominator $N$	At most $\max\{1,N(N-1)\}$ ; can exceed $n(n-1)$	Pseudo-polynomial by duplication (Corollary 8 )
$d=2$ , linear maps; planar GW with inner-product costs	Vertices of a polytope of dimension at most four; can exceed $n(n-1)$	Conjectured superpolynomial vertex count; no polynomial bound ( Section B.3.1 )

Appendix

Table A.1: Bounds on representative matchings or transport plans and arithmetic complexity of global alignment.

method	LAPs	fail	$>1\%$	LAPs	fail	$>1\%$	LAPs	fail	$>1\%$
	MPEG-7			Gauss.			lattice
Rubix	27	0.0	0.0	30	0.0	0.0	31	0.0	0.0
AM (PCA) [ 2 ]	7	53.0	33.4	7	72.4	62.2	5	78.5	77.2
AM (10 random) [ 2 ]	62	51.6	35.0	36	55.3	44.1	24	51.8	48.5
AM (GW) [ 4 ]	3	72.3	61.3	3	85.7	80.8	2	88.7	87.7
grid 36	36	72.9	12.6	36	59.0	10.7	36	3.8	1.3

Appendix

Table A.2: Failure rates on real and structured pairs. Each family has 1,000 pairs: MPEG-7 (

n=64

), Gaussian (

n=50

), and lattice neighborhoods (

n=24

). LAPs are mean numbers of assignments; “fail” and “

>1\%

” are the percentages of pairs with a numerical failure and with more than

1\%

excess, respectively. Bold marks fewer failures than every AM variant or fewer LAPs than both grids.

method	Gauss.	mixt.	circle	copy .05	copy .2	copy .5
AM (identity) [ 2 ]	97	87	98	90	92	93
AM (PCA, 4 starts) [ 2 ]	69	21	80	1	12	53
AM (10 random) [ 2 ]	70	24	80	28	40	62
grid 36	48	52	37	2	38	44
grid 360	5	8	1	0	2	3
B&B ( $10^{-6}$ )	0	0	0	0	0	0

Appendix

Table A.3: Failure rates (%) against the reference value on 1,560 centered

\mathrm{O}(2)

instances of synthetic families, pooled over

n\in\{20,50,100,200\}

(branch-and-bound, B&B:

n\leq 50

). “Copy

\sigma_{\mathrm{noise}}

” aligns a Gaussian point set with a noisy transformed copy of itself at noise level

\sigma_{\mathrm{noise}}

Set	Rubix	Grid ( $N_{\mathrm{grid}}$ )	AM (100) [ 2 ]
MPEG-7	11.8	296 (720)	288 (11.5%)
Gauss.	8.3	82.6 (360)	99.0 (6.5%)
lattice	2.2	3.9 (72)	21.2 (2.5%)

Appendix

Table A.4: Mean time (ms) per pair , 200 pairs per set, one core, including initialization. For grids, the table reports the smallest tested number of angles with at most two numerical failures. Parentheses give the number of angles or, for AM with 100 starts, the percentage of failed pairs. Bold marks the shortest time in each row.

Figure A.1: Accuracy and computation in planar applications. (a) Fraction of 200 MPEG-7 pairs that attain the numerical reference against mean time, including initialization: AM with 1–100 random starts, grids with 36–1,440 angles, AM (PCA), and Rubix. (b) 1-NN accuracy on noisy lattice neighborhoods; the solver curves and their bands of

\pm 1.96

standard errors use five draws, while GW and the bond-order descriptor use three separate draws ( Sections F.5 and F.6 ).

Figure A.2: MPEG-7 alignment and retrieval. The silhouettes are aligned from 64 boundary points, and the full outlines are shown. (a) Three pairs of the same class aligned to the gray target by AM (PCA, orange) and by Rubix (blue), with the mean squared PW costs $J$ and one scale per class. (b) A selected apple query and its four nearest neighbors in their computed orientations; $\times$ marks shapes of other classes. AM and Rubix retrieve 0 of 4 and 4 of 4 same-class neighbors here; Table 4 evaluates all queries.

	Noise $\sigma_{\mathrm{noise}}$
PW solver	0.08	0.12	0.16
AM (PCA) [ 2 ]	88.1	77.0	65.4
AM (10 starts) [ 2 ]	91.1	83.5	74.8
Grid 36	94.2	88.9	82.0
Rubix	94.2	88.9	81.9

Appendix

Table A.5: Noisy 2D lattice classification accuracy (%). Each column pools the same 1,000 test neighborhoods across five draws, with ten labeled neighborhoods per class and

n=24

. All four rows use 1-NN with PW distances and differ only in the alignment solver. Full noise curves appear in Figure A.1 (b). Bold marks the highest accuracy in each column.

Table 26

	MPEG-7 retrieval			Lattice 1-NN accuracy (%) at $\sigma_{\mathrm{noise}}$
Setting	Bullseye	1-NN	ms	0.04	0.08	0.12	0.16	0.20	ms
SEINT, 50 refs	36.2	63.1	0.22	97.7	81.0	50.0	36.3	26.3	0.17
SEINT, 100 refs	36.0	62.3	0.28	97.8	81.3	51.3	34.5	26.3	0.20
SEINT, 200 refs	35.9	61.8	0.43	98.0	82.7	53.5	34.2	28.2	0.25
SEINT, 500 refs	36.7	63.1	0.78	99.7	87.5	55.0	34.5	29.2	0.40
SEINT, 1000 refs	36.6	63.0	1.58	99.2	87.5	51.5	34.2	31.3	0.64

Appendix

Table A.8: SEINT at matched error rates. Accuracy (%) and median time in milliseconds per distance for 14 settings of SEINT [ 52 ] and for Rubix, on all 1,400 MPEG-7 silhouettes and three lattice draws ( Table A.7 ). The times use the same 300 pairs and processor core. ISEINT averages the discrepancies over the references, and SEINT takes their maximum.

Figure A.3: Fewer classification errors across three polycrystals. The rows show the three scenes, and the columns show the true lattice labels and the predictions with AM (PCA) and with Rubix. Black rings mark errors. Gray atoms are not scored: their neighborhoods cross a grain boundary, or they lie within 3.5 units of the boundary of the domain. Both methods score the same 1,190, 1,071 and 1,006 atoms, drawn at a common physical scale. The errors fall from 285 to 139, from 257 to 149 and from 255 to 179, which is 330 fewer overall; in the first scene, Rubix corrects 186 errors of AM and introduces 40.

		$\sigma_{\mathrm{noise}}=0.08$		$\sigma_{\mathrm{noise}}=0.12$		$\sigma_{\mathrm{noise}}=0.16$
Clustering	Distance	ARI	NMI	ARI	NMI	ARI	NMI
k-medoids	Rubix	0.55	0.68	0.52	0.60	0.39	0.43
	AM (PCA) [ 2 ]	0.35	0.40	0.22	0.26	0.06	0.08
	SEINT [ 52 ]	0.21	0.27	0.06	0.09	0.01	0.03
	SEINT, best setting [ 52 ]	0.70	0.72	0.28	0.31	0.07	0.11
average linkage	Rubix	0.68	0.80	0.66	0.80	0.10	0.20

Appendix

Table A.9: Unsupervised clustering of 200 lattice neighborhoods (50 per lattice), using PW and SEINT [ 52 ] distances. ARI and NMI measure the agreement with the true types, averaged over three draws. SEINT uses its original classification setting and its best tested setting (deterministic ISEINT; Section F.6.1 ). Bold marks the highest score per column within each clustering method.

Family	APM [ 46 ] (ms)	Rubix (ms)	Ratio
MPEG-7	259.0	8.12	$\mathbf{32.4}\times$
Gaussian	191.6	4.41	$\mathbf{43.7}\times$
Lattice	144.7	0.74	$\mathbf{194.6}\times$

Appendix

Table A.10: Similarity alignment against original APM. Both optimize a bijection, translation, rotation and nonnegative scale on 200 pairs per family. All objectives agree within APM’s mean tolerance

10^{-6}

. Times are median milliseconds including setup; ratios are paired APM/Rubix medians. Bold marks lower Rubix times and ratios above one. Language and solver details appear in Section F.7 .

$\rho_{\mathrm{share}}$	$\sigma_{\mathrm{noise}}$	Rubix-U	Rubix-B	AM-U	UGW	FUGW	PGW	$p$
1	0.01	100	100	99 (100)	100 (100)	100 (100)	98 (100)	1.00
1	0.03	100	100	99 (100)	100 (100)	100 (100)	93 (93)	1.00
0.75	0.01	100	61	100 (100)	83 (83)	97 (97)	38 (38)	1.00
0.75	0.03	99	58	99 (99)	84 (84)	95 (95)	27 (29)	1.00
0.5	0.01	100	29	98 (98)	49 (49)	86 (86)	13 (15)	0.50
0.5	0.03	98	28	99 (99)	37 (37)	62 (62)	14 (14)	1.00

Appendix

Table A.11: Synthetic partial-overlap results. Rotation recovery within

5^{\circ}

(%), with 100 tests per overlap/noise cell. Entries use validation-selected settings; parentheses give each baseline’s best test value. The last column compares Rubix-U with the best competitor by McNemar’s test.

$p_{\mathrm{def}}$	$\sigma_{\mathrm{noise}}$	Rubix-U	Rubix-B	AM-U	UGW [ 68 ]	FUGW [ 72 ]	PGW [ 17 ]	SEINT [ 52 ]	$p$
0	0.08	100	98	95.5 (100)	100 (100)	99.5 (100)	63.5 (63.5)	94.5	1.00
0.1	0.08	99	80.5	99 (99)	94 (94)	90.5 (91.5)	60 (60)	50.5	1.00
0.2	0.08	94.5	66.5	94.5 (94.5)	78 (78)	79.5 (79.5)	56.5 (56.5)	41.5	1.00
0.3	0.08	90.5	60	90.5 (90.5)	69 (69)	70 (70)	45.5 (57)	26	1.00

Appendix

Table A.12: Defective-lattice results. 1-NN accuracy (%) on 200 queries per defect/noise cell against defect-free references. Entries use validation-selected settings; parentheses give each baseline’s best test value. SEINT compares 24-atom neighborhoods. The last column compares Rubix-U with the best competitor by McNemar’s test.

Method	1	0.75	0.5	0.3	All	Median s
	Shared fraction
Rubix, unbalanced	100.0	100.0	100.0	100.0	100.0	0.505
AM, 60 starts	100.0	78.0	56.0	34.0	67.0	0.018
UGW [ 68 ]	100.0	82.0	16.0	0.0	49.5	0.053
Fused UGW [ 72 ]	100.0	94.0	86.0	38.0	79.5	0.016
Partial GW [ 17 ]	100.0	36.0	12.0	2.0	37.5	0.002

Appendix

Table A.13: Partial overlap under full 3D rotation. Rotations recovered within

5^{\circ}

(%) from 24-point sets that share the given fraction of points (50 test instances per column), with validation-selected settings. The last column is the median, over the four fractions, of the median time in seconds per solve on one core. Bold marks the highest recovery rates.

	Rubix, unbalanced				AM, 16 starts
Planar, $10^{4}\lambda$	1	0.75	0.5	0.3	1	0.75	0.5	0.3
2	100	97.5	88.5	74.5	52.5	47	43	36.5
5	100	99.5	99	88	66	57.5	52.5	50
10	100	100	100	94.5	84.5	74.5	62	59.5
20	100	100	100	99	93	86	79.5	72.5
50	100	100	100	99	99	98	95.5	87.5

Appendix

Table A.14: Sensitivity to the unmatched-point penalty. Rotation recovery within

5^{\circ}

(%) for Rubix and AM at each

\lambda

, using the same penalized objective: 200 planar tests per overlap fraction, pooled over noise, and 50 full-3D tests per fraction.

	Reference		Front end
Method	Exact	Offset	Li [ 43 ]	RAP [ 57 ]	Quatro [ 51 ]
Rubix	27	25	20	23	8
AM	22	20	17	17	5
UGW [ 68 ]	10	9	6	7	7
Fused UGW [ 72 ]	23	19	19	20	10
Partial GW [ 17 ]	6	7	5	6	6

Appendix

Table A.15: Partial overlap on real 3D scans. Yaw recoveries within

5^{\circ}

on the identified ETH pairs, given reference, offset or front-end translations. GW settings are selected at the reference translation; AM uses 16 starts. Native Li et al., RAP and Quatro recover 25, 25 and 6 yaws. Bold marks the most recoveries.

Method	1	0.75	0.5	0.3	All
	Shared fraction
Rubix	0/0	0/1	0/2	0/2	0/5
Balanced Rubix	0/0	0/81	0/143	0/179	0/403
AM, 16 starts	2/0	1/0	3/0	20/3	26/3
UGW	0/0	33/0	101/13	73/87	207/100
Fused UGW	0/0	8/0	49/3	6/105	63/108

Appendix

Table A.16: Failure diagnostic by overlap. Solver/objective failures among 200 tests per fraction ( Section F.9.2 ). A GW objective failure means no better correct-rotation witness was found. Both Rubix variants close every gap.

Method	Success	Median s
GLORES [ 20 ] + Rubix	190	1.61
GLORES [ 20 ]	189	2.33
PLICP [ 16 ] , 16 yaws	185	0.23
PLICP [ 16 ] from zero	146	0.01
UGW [ 68 ] + ICP	169	0.86
Partial GW [ 17 ] + ICP	151	0.37

Appendix

Table A.17: Registration of real laser scans with partial overlap. Pose successes within

0.25

m and

2^{\circ}

among the 212 configurations with a reference, and median seconds per configuration. GLORES [ 20 ] and PLICP [ 16 ] use the native C++ implementations of Section 8.4.1 ; UGW [ 68 ] and partial GW [ 17 ] run in Python at their best setting on these configurations, with optional refinement by trimmed ICP. Bold marks the most successes.

Figure A.4: Unbalanced alignment across all conditions. (a) Rotations recovered within

5^{\circ}

against the shared fraction, over 200 synthetic tests per fraction. (b) Lattice 1-NN accuracy against the defect rate at thermal noise

0.08

. (c) Pose success on the 212 laser-scan configurations with a reference. The settings are validation-selected in (a,b); the GW pipelines use their best test setting in (c).

Pair	AM (ms)	Edge (ms)	Vertex (ms)	Rubix (ms)	Rotation ( ∘ )	Translation (m)
Office 1–2	175.9	266.9	176.1	176.6	0.546	0.124
Office 2–3	205.2	300.2	225.9	200.0	86.237	7.254
Office 3–4	142.9	227.7	142.4	143.1	179.164	2.894
Courtyard 1–2	181.5	368.1	182.0	182.4	0.046	0.037
Courtyard 2–3	260.6	497.1	266.7	273.4	0.909	1.365
Courtyard 3–4	179.3	392.6	185.2	182.5	0.047	0.029

Appendix

Table A.18: Complete pipelines on six ETH pairs. Single-core times include all stages on identical observations ( Section F.10 ). Solvers return identical poses; success requires errors at most

5^{\circ}

and

0.5

m. Bold marks Rubix times below the vertex bound’s.

Figure A.5: Gravity-aligned matching on ETH scans. AM and Rubix start from the same initial yaw on 32-point subsets, with the nominal vertical of the scanner as the gravity direction. From AM to Rubix, the mean squared 3D residual falls from

8.461

0.695

m 2 in the Office example and from

286.3

11.805

m 2 in the Courtyard example. Each row shows every point and every matched edge from one viewpoint and at one scale, with the heights retained. The examples are selected for large errors of AM; Table 8 reports all 96 initializations.

Quatro [ 51 ]
Refinement after the native method	Closed gaps	LAPs	Stage (ms)	Total (s)	Success
Projected native + gravity ICP	0/527	0	0	0.678	6/31
AM + gravity ICP	0/527	1,066	0.64	0.657	11/31
AM (multistart) + gravity ICP	0/527	32,505	24.7	0.685	11/31
Edge bound + gravity ICP	527/527	2,656,883	468	1.158	11/31
Vertex bound + gravity ICP	527/527	32,165	14.8	0.669	11/31

Appendix

Table A.19: A common matching stage after three front ends. Every global solver closes all subset gaps within one second each at mean-squared tolerance

10^{-5}

m 2 plus roundoff allowance. LAPs are total assignments; times are medians, including all stages in “Total.” Projected native poses solve no subset problem; AM supplies no lower bound. Bold marks reductions from the vertex bound. Success requires

5^{\circ}

and

0.5

m; native success counts are 4/31, 37/62 and 23/31 ( Section F.11 ).

Native method	Success / 31	Median RE ( ∘ )	Median TE (m)	Native time (s)
Quatro [ 51 ]	4	81.521	7.281	0.289
RAP, trial 1 [ 57 ]	19	1.161	0.368	12.097
RAP, trial 2 [ 57 ]	18	1.143	0.294	11.181
Li et al., $N_{\mathrm{cand}}=10$ [ 43 ]	23	0.150	0.064	2.921
Cai et al., corrected FMP+BnB [ 13 ]	24	0.175	0.041	4.472
Cai et al., corrected BnB [ 13 ]	24	0.175	0.041	3.671

Appendix

Table A.20: Native methods on the identified ETH scan pairs. The results precede any added stage; the last two rows are ICP alone. Success requires a rotation error (RE) of at most

5^{\circ}

and a translation error (TE) of at most

0.5

m. The medians include every valid output. The native time is the wall time of the process, summed over the ICP starts. The methods differ in input, objective and hardware, which limits direct comparisons of runtime; Sections F.12 and F.1 give the hardware and the preprocessing that the times omit.

Figure A.6: Less search for the same SE(3) alignment. One favorable example per geometry, selected from all 72 scenes, including those on which the host reaches the time limit. The columns show the observations, the common fitted pose with its residuals, and the solve times; each row uses one viewpoint and scale. Hollow bars mark the limit of 15 s. At a target of

10^{-5}

for the numerical gap in the mean squared error, Rubix closes all three cases, whereas the host with its rotation-cap bounds alone stops above the target in (b,c). Both variants return identical poses and matchings throughout the study.

Solver and baseline	Runs	Without	With Rubix	Paired ratio
Timed host (s)
GLORES [ 20 ] : native bound	240	2.330	1.608	$\mathbf{1.3313}\times$
Cai FMP [ 13 ] : common host	31	2.396	2.413	$\mathbf{1.0004}\times$
Cai BnB [ 13 ] : common host	31	1.230	1.232	$0.9275\times$
Conditional yaw TLS loss (m 2 )
Quatro [ 51 ] : native GNC yaw	31	1.5396	1.4816	$\mathbf{1.0073}\times$

Appendix

Table A.21: Published solvers with and without Rubix bounds. Values are medians; paired ratios divide baseline by Rubix runtime or Quatro yaw loss. Bold marks improvements. GLORES includes preprocessing/bounds at

1\%

tolerance; Cai timings exclude features and use common hosts with identical consensus. Quatro’s clipped yaw loss improves by more than

10^{-8}

on 17/31 pairs, by at most

0.879821

m 2 , with unchanged success (4/31 before, 6/31 after ICP); it is not timed.

Native method: baseline bound	Stage (ms)	Stage ratio	Total (s)	Total ratio	Success
Quatro [ 51 ] : edge	$468\to\mathbf{10.4}$	$\mathbf{46.94}\times$	$1.158\to\mathbf{0.667}$	$\mathbf{1.617}\times$	$11/31\to 11/31$
Quatro [ 51 ] : vertex	$14.8\to\mathbf{10.4}$	$\mathbf{1.47}\times$	$0.669\to\mathbf{0.667}$	$\mathbf{1.006}\times$	$11/31\to 11/31$
RAP [ 57 ] : edge	$466\to\mathbf{10.4}$	$\mathbf{46.31}\times$	$12.302\to\mathbf{11.827}$	$\mathbf{1.033}\times$	$32/62\to 32/62$
RAP [ 57 ] : vertex	$14.8\to\mathbf{10.4}$	$\mathbf{1.48}\times$	$11.834\to\mathbf{11.827}$	$1.000\times$	$32/62\to 32/62$
Li et al. [ 43 ] : edge	$461\to\mathbf{10.4}$	$\mathbf{45.79}\times$	$25.759\to\mathbf{25.332}$	$\mathbf{1.011}\times$	$20/31\to 20/31$
Li et al. [ 43 ] : vertex	$14.7\to\mathbf{10.4}$	$\mathbf{1.46}\times$	$25.339\to\mathbf{25.332}$	$1.000\times$	$20/31\to 20/31$

Appendix

Table A.22: Matching stages with baseline and Rubix bounds. Arrows show baseline

\to

Rubix under identical subsets, starts, objectives, pose selection and ICP. Edge and vertex denote the independent-edge and vertex bounds. Times are medians; ratios are paired baseline/Rubix medians. Totals add identical front-end times. Quatro and Li run once per pair; RAP runs twice. All 2,108 global subset gaps close with unchanged

5^{\circ}

0.5

m success counts; bold marks time improvements.

Figure A.7: Gravity-aligned registration of ETH scans. Office scans 1–2 (a,b; ceiling removed) and Courtyard scans 3–4 (c,d), before and after registration with the nominal vertical of the scanner as the gravity direction. All four solvers return the same pose. Relative to the independent-edge bound, Rubix reduces the time of the complete pipeline from 267 to 177 ms and from 393 to 182 ms; the rotation and translation errors are $0.546^{\circ}$ and $0.124$ m for Office and $0.047^{\circ}$ and $0.029$ m for Courtyard. Each row uses one viewpoint, one scale and one set of displayed points, and the projected scale bars are in meters. The two pairs are selected among the successful ones; Table A.18 reports all six.

Subset selection	Bound	Gap closed	Cells	CPU (s)	Median (ms)	Pose success
RAP full pose	Rotation-cap host	31/31	28,074	9.73	203.1	10/31
RAP full pose	With Rubix	31/31	8,302	12.10	300.5	10/31
Centroid control	Rotation-cap host	31/31	39,920	15.23	393.7	0/31
Centroid control	With Rubix	31/31	12,232	18.72	553.0	0/31

Appendix

Table A.23: SE(3) matching on real ETH subsets. All identified pairs use 32-point subsets, 15 s and mean-squared gap target

10^{-5}

m 2 . Cells include initial regions. CPU time excludes common subset preparation and RAP; medians are elapsed solver times. Both bounds return identical poses and matchings; success requires

5^{\circ}

and

0.5

Figure A.8: Less search inside native GLORES [ 20 ] . Scans from the Slippage and Navigation sequences before registration and after fitting with the native bound and with the Rubix bound.

J

is the sum of squared residuals over the retained points, in m 2 ; hollow points are trimmed (216 of 239 and 220 of 244 points are retained). Both solvers reach the

1\%

tolerance with equivalent poses. Rubix reduces the nodes from 1,800 to 917 and from 2,650 to 1,170, and the times from 2.85 to 1.96 s and from 3.97 to 2.29 s. Each row uses one display rotation and scale. For each sequence we show the case with the largest objective before registration among those with 256 beams and

\rho_{\mathrm{keep}}=0.9

on which both poses succeed; Table 7 covers all 240 configurations.

Figure A.9: Sensitivity to a simulated error in the gravity direction. Independent tilts of both supplied directions at six magnitudes give 288 fits on 48 scenes. The horizontal positions are equally spaced and labeled by the tilt angle; faint points show every error, blue lines the medians and bands the interquartile ranges. (a) Full rotation error, and the median of the floor

\angle(R_{*}\widehat{g}_{y},\widehat{g}_{x})

imposed by the constraint (dashed). (b) Translation error after centering, in centimeters. Every fit reaches a gap of

10^{-6}

in the summed squared error.

Added bound	Closed	CPU (s)
None (rotation-cap host)	63/72	189.2
One-assignment difference	63/72	206.8
Full exterior supports	72/72	59.1
Reused assignment duals	61/72	237.5
Adaptive bound selection	67/72	139.2

Appendix

Table A.24: Complete SE(3) alignment on 72 scenes with the same host. Each run has a limit of 15 s and a target of

10^{-5}

for the gap in the mean squared error. The CPU time is summed over all runs, including the unresolved ones; every policy uses one core. Bold marks more closed gaps or less CPU time than the host with its rotation-cap bounds alone.

Explore similar work

Jul 25, 2026cs.CV

SHReg: Strictly Rotation-Equivariant Point Cloud Registration via Spherical Harmonics

Point cloud registration critically depends on local features that are both distinctive and robust to arbitrary 3D rotations. Existing learning-based methods typically approximate rotation invariance via fragile local reference frames or extensive data augmentation, providing only empirical invariance and often degrading under unseen rotational transformations. In this paper, we propose SHReg, a strictly rotation-equivariant point cloud registration framework grounded in the representation theory of

SO(3)

. By representing local geometric features as irreducible representations of

SO(3)

, SHReg guarantees exact equivariance under arbitrary rotations without relying on local reference frames. Built upon a spherical-harmonics-based equivariant backbone, SHReg jointly learns rotation-invariant descriptors for robust correspondence matching and rotation-equivariant features that preserve fine-grained orientation information. The preserved equivariant structure enables each correspondence to directly hypothesize a rigid transformation, reducing reliance on large-scale hypothesis sampling in conventional RANSAC-based pipelines and leading to improved robustness under challenging rotational variations. Extensive experiments on 3DMatch, 3DLoMatch, and KITTI demonstrate that SHReg consistently outperforms state-of-the-art methods in registration accuracy, particularly under large rotational perturbations.

Chongjian Wang, Junjie Gao

College of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao, China · School of Artificial Intelligence, Shandong Women’s University, Jinan, China

Point Cloud Registration Equivariant Neural Networks

Ask PDF

Jul 9, 2026stat.ML

High-Dimensional Procrustes Matching via Tree Counts

Suppose we observe two sets of

n

Gaussian vectors in

\mathbb{R}^d

, with the promise that, after applying a permutation of

[n]

and a rotation of

\mathbb{R}^d

, the two sets are

ρ

-correlated. The Procrustes matching problem asks us to recover the unknown permutation of

[n]

that aligns the two sets. The problem is well-studied in the low-dimensional regime

d=O(\log n)

, but the high-dimensional regime

d\gg \log n

has remained largely uncharted: prior matching guarantees require nearly perfect correlation

ρ=1-o(1)

, even for information-theoretic recovery. Our main result is a polynomial-time algorithm for exact recovery at constant correlation. The algorithm works by computing and comparing weighted counts of a specially chosen family of ``wide'' trees. So long as

d\ge \mathrm{polylog}(n)

, the algorithm succeeds with high probability for any

ρ^2>\sqrtα

, where

α\approx 0.338

is Otter's tree-counting constant. We complement this algorithmic result with an improved information-theoretic guarantee, showing that exact recovery is possible when

ρ^2 \gtrsim \max\{\log n/d,\sqrt{\log n/n}\}

. We also carry out a low-degree advantage calculation, which suggests that the condition

ρ^2 > \sqrtα

is necessary for any tree-counting algorithm.

Xiaochun Niu, Tselil Schramm, Jiaming Xu

The Fuqua School of Business, Duke University, Durham NC, USA · Department of Statistics, Stanford University, Stanford, CA, USA

High-Dimensional Gaussian Primitives Spurious Correlations Counting Trees

Ask PDF

Sep 27, 2024cs.CV

DynaWeightPnP: Toward global real-time 3D-2D solver in PnP without correspondences

This paper addresses a special Perspective-n-Point (PnP) problem: estimating the optimal pose to align 3D and 2D shapes in real-time without correspondences, termed as correspondence-free PnP. While several studies have focused on 3D and 2D shape registration, achieving both real-time and accurate performance remains challenging. This study specifically targets the 3D-2D geometric shape registration tasks, applying the recently developed Reproducing Kernel Hilbert Space (RKHS) to address the "big-to-small" issue. An iterative reweighted least squares method is employed to solve the RKHS-based formulation efficiently. Moreover, our work identifies a unique and interesting observability issue in correspondence-free PnP: the numerical ambiguity between rotation and translation. To address this, we proposed DynaWeightPnP, introducing a dynamic weighting sub-problem and an alternative searching algorithm designed to enhance pose estimation and alignment accuracy. Experiments were conducted on a typical case, that is, a 3D-2D vascular centerline registration task within Endovascular Image-Guided Interventions (EIGIs). Results demonstrated that the proposed algorithm achieves registration processing rates of 60 Hz (without post-refinement) and 31 Hz (with post-refinement) on modern single-core CPUs, with competitive accuracy comparable to existing methods. These results underscore the suitability of DynaWeightPnP for future robot navigation tasks like EIGIs.

Jingwei Song, Maani Ghaffari

United Imaging Research Institute of Intelligent Imaging, Beijing 100144, China, Beijing, 100144, China · University of Michigan, Ann Arbor, 48109, MI, USA

Image Registration Reproducing Kernel Hilbert Spaces Dynawm Perspective Solvers

Ask PDF