PointTruss: K-Truss for Point Cloud Registration

Hao Li (University of Minnesota - Twin Cities) · Yue Wu (Princeton University) · Jun Jiang (Xidian University) · Yongzhe Yuan (Xidian University) · Maoguo Gong (Xidian University) · Qiguang Miao (Xidian University) · Mingyang Zhang (Xidian University) · wenping ma (Xidian University)

clique-based methodsconsensus votingcoverage and uniformitygraph-based methodshigher-order topological structuresinlier selectionk-corek-trusslow-scale sampling strategynp-hardoutlier rejectionpoint cloud registrationspatial distribution scorestructural skeletontriangle support

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.