Correspondence-Free Fast and Robust Spherical Point Pattern Registration

Current methods to estimate the rotation between two spherical ($\mathbb{S}^{2}$) patterns typically rely on maximizing their spherical cross-correlation. However, these approaches exhibit computational complexities greater than cubic $O\left(n^{3}\right)$ with respect to rotation space discretization. We propose a rotation estimation algorithm between two spherical patterns with linear time complexity $O(n)$. Unlike existing methods, we explicitly represent spherical patterns as discrete 3D point sets on the unit sphere, reformulating rotation estimation as a spherical point-set alignment (i.e., the Wahba problem for 3D unit vectors). We introduce three novel algorithms: (1) SPMC (Spherical Pattern Matching by Correlation), (2) FRS (Fast Rotation Search), and (3) a hybrid approach (SPMC+FRS) that combines the advantages of the previous two methods. Our experiments demonstrate that in the $\mathbb{S}^{2}$ domain and in correspondence-free settings, our algorithms are over $10 x$ faster and over $10 x$ more accurate than current state-of-the-art methods for the Wahba problem with outliers. We validate our approach through extensive simulations on a new dataset of spherical patterns, the “Robust Vector Alignment Dataset.” Furthermore, we adapt our methods to two real-world tasks: (i) Point Cloud Registration (PCR) and (ii) rotation estimation for spherical images. In the PCR task, our approach successfully registers point clouds exhibiting overlap ratios as low as 65%. In spherical image alignment, we show that our method robustly estimates rotations even under challenging conditions involving substantial clutter (over 19%) and large rotational offsets. Our results highlight the effectiveness and robustness of our algorithms in realistic, complex scenarios. Our dataset and code are available at: https://github.com/ARLab-VT/Robust-Vector-Set-Alignment