FSAC-IA: A Hierarchical Constructed SAC-IA Algorithm for Point Cloud Alignment Acceleration

Point cloud alignment plays a crucial role in numerous fields and applications, enabling the integration, analysis, and reconstruction of 3D data. SAmple Consensus Initial Alignment (SAC-IA), a coarse alignment algorithm, provides the initial position for precise alignment. While SAC-IA can effectively capture both global and local information, it incurs high computational costs associated with the correspondence matching of high-dimensional features. To address this challenge, we propose FSAC-IA, a faster SAC-IA-based algorithm designed to accelerate LiDAR point cloud alignment. FSAC-IA introduces a light Fast Point Feature Histogram (FPFH) descriptor to optimize the feature presentation, ensuring high matching speed without sacrificing accuracy. We also replace the original k-d tree structure in the SAC-IA, with a Hierarchical Navigable Small World (HNSW) structure for descriptor-matching, enabling efficient large-scale point cloud alignment. Experiments on fine-grained LiDAR point clouds demonstrate that FSAC-IA achieves a 7x speedup over traditional k-d tree-based alignment algorithms, establishing a new benchmark for efficient and accurate point cloud alignment.