PointTruss: K-Truss for Point Cloud Registration

Point cloud registration is a fundamental task in 3D computer vision. Recent advances have shown that graph-based methods are effective for outlier rejection in this context. However, existing clique-based methods impose overly strict constraints and are NP-hard, making it difficult to achieve both robustness and efficiency. While the k-core reduces computational complexity, which only considers node degree and ignores higher-order topological structures such as triangles, limiting its effectiveness in complex scenarios. To overcome these limitations, we introduce the $k$-truss from graph theory into point cloud registration, leveraging triangle support as a constraint for inlier selection. We further propose a consensus voting-based low-scale sampling strategy to efficiently extract the structural skeleton of the point cloud prior to $k$-truss decomposition. Additionally, we design a spatial distribution score that balances coverage and uniformity of inliers, preventing selections that concentrate on sparse local clusters. Extensive experiments on KITTI, 3DMatch, and 3DLoMatch demonstrate that our method consistently outperforms both traditional and learning-based approaches in various indoor and outdoor scenarios, achieving state-of-the-art results.

Authors

• Yue Wu
• Jun Jiang
• Yongzhe Yuan MoE Key Lab of Collaborative Intelligence Systems, Xidian University School of Computer Science and Technology, Xidian University
• Maoguo Gong School of Electronic Engineering, Xidian University, Xi’an 710071, China Key Laboratory of Collaborative Intelligence Systems, Ministry of Education, Xi’an 710071, China
• Qiguang Miao MoE Key Lab of Collaborative Intelligence Systems, Xidian University School of Computer Science and Technology, Xidian University
• Hao Li Shanghai Artificial Intelligence Laboratory & Northwestern Polytechnical University
• Mingyang Zhang School of Electronic Engineering, Xidian University, Xi’an 710071, China Key Laboratory of Collaborative Intelligence Systems, Ministry of Education, Xi’an 710071, China
• Wenping Ma School of Artificial Intelligence, Xidian University

Keywords

No keywords are indexed for this paper.