PointTruss: K-Truss for Point Cloud Registration
Yue Wu, Jun Jiang, Yongzhe Yuan, Maoguo Gong, Qiguang Miao, Hao Li, Mingyang Zhang, wenping ma
Point cloud registration is a fundamental task in computer vision and remote sensing. Recent advances have shown that graph-based approaches are effective for outlier removal 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, it 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 to jointly evaluate the coverage and uniformity of inliers, thus avoiding solutions where inliers are spatially clustered. 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.