Multi-scale Consistency for Robust 3D Registration via Hierarchical Sinkhorn Tree

We thank the reviewer for your valuable comments and suggestions.

Response to Weakness 1: Thank you for pointing out this issue. We apologize for any misunderstanding caused by the term "inlier correspondence" in Eq. (1). It should be revised as "putative inlier correspondences". As you mentioned, the definition of inlier correspondence refers to points in two point clouds that are sufficiently close given a ground truth transformation. Actually our original intention in using 'inlier correspondence' here was to convey that, since the ground truth transformation is not provided beforehand, we often have to design a method to estimate the inlier correspondence set. A common approach is to do feature matching, as you mentioned. Therefore, in Eq. (1) we aim to describe how we could solve this problem from the Multi-scale Consistency (MSC) perspective, so the "inlier correspondence" here should be revised as "putative inlier correspondence", representing the inlier correspondence inferred by MSC. We will fix it to "putative inlier correspondence" in the revised version.

Response to Weakness 2: Thanks for your feedback regarding the lack of explanation of $T_{ij}$. Here $T_{ij}$ is the element from the assignment matrix $T \in R^{(|\mu_{ov}|+1)\times(|\nu_{ov}|+1)}$ of optimal transport problem, indicating the pairwise matching (overlap) score from source to target point cloud. The row and column sum of the matrix $T$ are respectively subject to the augmented marginal distributions $\mu_{ov}$ and $\nu_{ov}$ to ensure the allocation constraints. $T$ is the optimization variable in the calculation of the Overlap-aware Sinkhorn Distance and can be efficiently solved by the Sinkhorn algorithm. We will include the above explanation in the revised version.

Response to Weakness 3: Thank you for your suggestions on better illustrating the optimization of HST. We will include a detailed diagram in the revised version that illustrate the forward computation process and the backward gradient flow to thoroughly demonstrate the optimization process of HST.

Response to Limitations : Thank you for your insightful feedback on our work!
We understand your concern that Multi-scale Consistency (MSC) may hinder the model's ability to learn multi-scale descriptive features because it requires the features of two point clouds to exhibit similarity across multiple scales. In fact, we also observe this issue in our experiments. Therefore, we introduce a layer-wise overlap-aware circle loss (please refer to lines 253-255 in the paper) to help maintain the descriptiveness of features at each layer. This ensures that the backbone does not learn overly uniform features while still preserving MSC.
As for the concern that MSC might fail in test data with extremely low overlap, we design a set of experiments targeting overlap ratios of less than 10% and compare the performance with GeoTransformer to validate the robustness of HST when facing extremely low overlap. Please note that the currently available preprocessed datasets, 3DMatch (overlap > 30%) and 3DLoMatch (10% < overlap < 30%), do not include samples with such extremely low overlap (overlap<10%). Therefore, we access the 3DMatch raw dataset and collect a set of point cloud pairs with overlap < 10%, which we refer to as 3DExtremeLoMatch (3DExMatch) dataset, containing a total of 1,343 samples. We first test the model pre-trained on 3DMatch directly on 3DExMatch, and the results can be found in the following table:

We then randomly divide the 3DExMatch into training, validation, and test sets with proportions of 60% (805 samples), 10% (134 samples), and 30% (404 samples), respectively. We fine-tune GeoTransformer and HST for 3 epochs on the training set, and then evaluate the models on the test set. The results can be found in the following table. Both results clearly demonstrate that HST maintains strong performance even under low overlap conditions, confirming the effectiveness of our method.

Regarding the potential need to adjust hyperparameters like the number of levels and grid size for optimization, we believe that the adjustment of the number of levels primarily involves balancing performance and latency. As shown in the ablation study in Table 4, increasing the number of levels enhances performance but also slightly increases inference time. If the application scenario requires more real-time processing, the number of levels can be reduced to accelerate the model without significantly sacrificing performance. Similar to other coarse-to-fine methods, such as GeoTransformer, hyperparameters like grid size also require fine-tuning based on the specific scenario and the source of the point clouds.

All the above discussions will be added in the revised version. We hope the above responses address your concerns.

We first would like to thank the reviewer for giving us valuable comments.

Response to the comments on our work (first paragraph of Weaknesses): Thank you for your insightful comments on our work. We understand your concern that our method builds upon the foundation laid by existing work. However, we would like to emphasize that modeling the multi-scale consistency (MSC) is non-trivial due to the challenges in ensuring both effectiveness and efficiency. To achieve this, we proposed a series of methods to improve performance while maintaining low complexity, such as a lightweight overlap prediction module, Overlap-aware SD with Overlap Filtering and Overlap-aware Marginals, pruned HST, and others. Our extensive experiments on both indoor and outdoor benchmarks have demonstrated their scene-agnostic effectiveness. HST shows significant improvement compared to SOTAs, maintaining robust performance even under low overlap (please refer to the 3DLoMatch results in Tab. 1 & 2, as well as our response to Question 2 below), while introducing only a slight, acceptable time overhead.
As for your concern that we might suffer from poor initial correspondences, we believe that by modeling MSC, our method improves the quality of the correspondence set and thus suffers less performance degradation compared to others. All current coarse-to-fine-based methods heavily depend on coarse matching, and if the coarse correspondences are poor, they will face performance loss. Please refer to our response to Weakness 2. Under extremely low overlap, GeoTransformer shows significant performance degradation, whereas HST suffers less.

Response to Question 1: Thanks for your suggestions about comparing HST with outlier rejection methods. We are also very interested in the comparison. For fairness, we replace HST directly with GC-RANSAC, MAC, and FastMAC. Results on both 3DMatch and 3DLoMatch can be found in the following table.

Response to Question 2: Thank you for your constructive suggestions to test the HST under extremely low overlap. We design a set of experiments targeting overlap ratios of less than 10% and compare with GeoTransformer. Please note that the currently available preprocessed datasets, 3DMatch (overlap>30%) and 3DLoMatch (10%<overlap<30%), both do not include samples with such extremely low overlap. Therefore, we access the 3DMatch raw dataset and collect a set of pairs with overlap<10%, which we refer to as 3DExtremeLoMatch (3DExMatch), containing a total of 1,343 samples. We first test the model pre-trained on 3DMatch directly on 3DExMatch, and the results can be found in the following table:

We then randomly divide the 3DExMatch into training, validation, and test sets with proportions of 60% (805 samples), 10% (134 samples), and 30% (404 samples), respectively. We fine-tune GeoTransformer and HST both for 3 epochs on the training set and then evaluate on the test set. The results are as follows:

Response to Question 3: Thank you for your feedback on Eq. (2). We apologize for the typo and for any misunderstandings it may have caused.
Our purpose of Eq. (2) is to find the k-NN of any given point $x_i^{l}$ in its next layer to form the local patch. We provide the following explanations in hopes of resolving your confusion.
(1) We mistakenly used $argmax$ instead of $argmin$ operator in the formula. We should use the $argmin$ on $K$ to find the k nearest points to form the local patch.
(2) Our initial intention is to use a more mathematical $argmin$ operator to represent the k-NN search instead of directly using $kNN(\cdot)$. However, such an expression might be hard to understand and could lead to ambiguities, such as the definition of the set $S$ in the formula. Therefore, we take a compromise approach by replacing the $argmin$ with the $argtopk$ operator to make it more intuitive.
The following is the revised Eq. (2) and will be included in the revised version.
Given $\mathbf{x}_i^{(l)}$, its local patch $\mathbf{P}_i^{(l+1)}$ is defined as:

Lack of ablation on top-q: We apologize for the lack of ablation on top-q for overlap points filtering. The performance of HST is not sensitive to the selection of q. The RR of varying q can be found in the following table.

Citing other overlap score-guided Sinkhorn method: Thank you for your suggestion. We will cite OCFNet in our revised version.

We thank the reviewer for the insightful comments and feedback. We hope that our responses can address your concerns.

Response to Weakness 1: Thanks you for your valuable comments. First, we would like to emphasize that modeling multi-scale consistency (MSC) is non-trivial, even with the help of a coarse-to-fine strategy for modeling the neighborhood. We understand your concern that our method might simply be applying the coarse-to-fine procedure across multiple scales. But our proposed method is not simply a repetition of the coarse-to-fine strategy, as merely repeating such an operation would result in an $O(n^l)$ complexity, where $l$ is the number of scales. This level of complexity is unacceptable, posing a major challenge in practical applications. Additionally, this naive approach could introduce a large number of non-overlapping noisy points, negatively impacting the model's robustness and performance, and could even degrade the quality of the correspondence set compared to the original.
To address these issues, we proposed a series of designs to improve the model's feasibility and performance, which distinguishes it from the mentioned models. First, we design a lightweight Patch Overlap Prediction module to efficiently predict overlap. Next, we propose Overlap-aware Sinkhorn Distance with Overlap Points Filtering and Overlap-aware Marginal Prior to effectively retain the most likely overlapping points based on the prediction, filtering out a large number of potential non-overlapping points. Finally, we perform the above methods with local exploration layer-wisely to prune the K-ary tree rooted at the superpoint, thereby constructing the HST to model the MSC of correspondences. Our extensive experiments on both indoor and outdoor benchmarks have demonstrated the scene-agnostic effectiveness of our proposed method.
Finally, we would like to emphasize our key contributions as follows: 1) To the best of our belief, our work is the first to introduce MSC into point cloud registration tasks to mitigate the effects of low overlap and high noise. 2) We propose a method for modeling MSC called HST, which introduces a pruned tree structure to efficiently characterize the similarity of potential overlapping points in the vicinity areas layer by layer and aggregates them into MSC. 3) We introduce an overlap-aware Sinkhorn Distance with Overlap Points Filtering and Overlap-aware Marginal Prior to focus optimal transport processes only on potential overlapping points, significantly enhancing the robustness of consistency calculations while reducing solution complexity.
The above discussions will be included in the revised version.

Response to Weakness 2: Thank you for your comments regarding the comparative performance. As mentioned by other reviewers and shown in Tab 1, HST gains significant improvements over the state-of-the-art methods on both indoor and outdoor benchmarks. The improvements are even greater on 3DLoMatch, where point cloud pairs share fewer overlaps, suggesting that our model demonstrates better robustness and performance under low-overlap, high-noise scenarios. To validate this, we further design a set of experiments targeting overlap ratios of less than 10% and compare the performance with GeoTransformer. Please note that the currently available preprocessed datasets, 3DMatch (overlap > 30%) and 3DLoMatch (10% < overlap < 30%), do not include samples with such extremely low overlap (overlap<10%). Therefore, we access the 3DMatch raw dataset and collect a set of point cloud pairs with overlap < 10%, which we refer to as 3DExtremeLoMatch (3DExMatch) dataset, containing a total of 1,343 samples. We first test the model pre-trained on 3DMatch directly on 3DExMatch, and the results can be found in the following table:

We then randomly divide the 3DExMatch into training, validation, and test sets with proportions of 60% (805 samples), 10% (134 samples), and 30% (404 samples), respectively. We fine-tune GeoTransformer and HST both for 3 epochs on the training set, and then evaluate the models on the test set. The results can be found in the following table. Both results clearly demonstrate that HST can significantly outperform other methods even under low overlap conditions, further confirming the effectiveness of our method.

Response to Weakness 3: Thank you for your insightful feedback regarding the efficiency of our proposed method. We share your concern on this matter. In fact, we have compared the running time of our method with state-of-the-art approaches under different estimators in the manuscript. Please refer to the last column of Table 2. The results indicate that our method achieves significant performance improvements with only a slight, acceptable increase in latency due to the introduction of new modules. We will highlight this comparison more prominently in the revised version.

Thank you again for your valuable feedback. We hope our responses address your concerns.

We first would like to thank the reviewer for providing us valuable comments and suggestions.

Response to Weakness 1: Thank you for your question regarding Eq. (2) about the k-NN local exploration part. We apologize for the typo in Eq. (2) and for any misunderstandings it may have caused. Your are correct about the understanding of Eq. (2). Its purpose is to search for the k-NN of any given point $x_i^{l}$ from the $l$-th layer in the next layer to form the corresponding local patch. We provide the following explanations in hopes of resolving your confusion.
(1) The term $||x_i^l, x_j^{l+1} ||$ represents the Euclidean distance between the given $l$-th layer's point $x_i^l$ and the $(l+1)$-th layer's point $x_j^{l+1}$. So the operator $||\cdot||$ we used here is actually the L2-norm of coordinates' difference. We will add a subscript 2 to the $||\cdot||$ operator to avoid any potential misunderstandings, i.e., revise $|| x_i^l, x_j^{l+1} ||$ to $|| x_i^l, x_j^{l+1} ||_2$.
(2) We mistakenly used $argmax$ instead of $argmin$ operator in the formula. The set $K$ actually represents the collection of Euclidean distances between all points in $(l+1)$-th layer and the given point in $l$-th layer. We should use the $argmin$ operator on $K$ to search for the k nearest points to form the local patch.
(3) Our initial intention is to use a more mathematical $argmin$ operator to represent the k-NN search instead of directly using $kNN(\cdot)$. However, such an expression might be difficult to understand and could lead to ambiguities, such as the definition of the set $S$ in the formula. Therefore, we take a compromise approach by replacing the $argmin$ operator with the $argtopk$ operator to make it more intuitive and easier to understand.
The following is the revised formula and will be included in the revised version.

Given $\mathbf{x}_i^{(l)}$, its local patch $\mathbf{P}_i^{(l+1)}$ is defined as:

Response to Weakness 2: Thanks for your suggestion about citing relevant outlier rejection-focused registration methods. We will cite approaches like GC-RANSAC [1], MAC [2], VBReg [3], FastMAC [4], etc., and summarize them as fine-level outlier removal methods in our revised version.
[1] Barath, Daniel, and Jiří Matas. "Graph-cut RANSAC." Proceedings of the IEEE conference on computer vision and pattern recognition. 2018.
[2] Zhang, Xiyu, et al. "3D registration with maximal cliques." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023.
[3] Jiang, Haobo, et al. "Robust outlier rejection for 3d registration with variational bayes." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2023.
[4] Zhang, Yifei, et al. "FastMAC: Stochastic Spectral Sampling of Correspondence Graph." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.