Correspondence-Free Fast and Robust Spherical Point Pattern Registration

Current methods to estimate the rotation between two spherical (S 2 ) patterns typically rely on maximizing their spherical cross-correlation. However, these approaches exhibit computational complexities greater than cubic O(n 3 ) 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 S 2 domain and in correspondence-free settings, our algorithms are over 10x faster and over 10x 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