Fast, Robust, Permutation-and-Sign Invariant SO(3) Pattern Alignment

We address the correspondence-free alignment of two rotation sets on (SO(3)), a core task in calibration and registration that is often impeded by missing time alignment, outliers, and unknown axis conventions. Our key idea is to decompose each rotation into its Transformed Basis Vectors (TBVs)-three unit vectors on (S2)-and align the resulting spherical point sets per axis using fast, robust matchers (SPMC, FRS, and a hybrid). To handle axis relabels and sign flips, we introduce a Permutation-and-Sign Invariant (PASI) wrapper that enumerates the 24 proper signed permutations, scores them via summed correlations, and fuses the per-axis estimates into a single rotation by projection/Karcher mean. The overall complexity remains linear in the number of rotations ((O(n))), contrasting with (O(Nr3log Nr)) for spherical/(SO(3)) correlation. Experiments on EuRoC Machine Hall simulations (axis-consistent) and the ETH Hand-Eye benchmark (textttrobotarmreal) (axis-ambiguous) show that our methods are accurate, 6-60x faster than traditional methods, and robust under extreme outlier ratios (up to 90%), all without correspondence search.