Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper provides a thorough investigation of how accurate detection regions can be mapped to each other.  The detection regions are typically represented by noisy vectors with outliers, and those problems can be formulated as how to finding the matching map between two sets of d-dimensional vectors. The investigation shows that the LSL estimator is robust to noise and outliers for both problems of detection and estimation. 
main_review: This is an investigation which follows Collier and Dalalyan's work to explore the stability of noise observations. The paper is easy to read and understand; however, the originality and significance is more incremental. 
limitations_and_societal_impact: 1. It only provides theoretic analysis and experiments to study how robust of the existing approach to the noisy observation. There is no attempt to further improve the existing algorithms, such as exploring the accuracy of LSL estimator with different error measurement. 
2. The author should consider the experimental evaluation with larger public known datasets.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper studies the problem of finding matches between two observations, one of which has outliers. It provides theoretical analysis about the conditions when using the Least Sum of Logarithms estimator can lead to optical solution. It studies different situation with regards to different cases of observations, providing the upper bound and lower bound theoretically. Experiments are conducted on synthetic datasets and one real image matching dataset.
main_review: Strengths
+: The paper gives theoretical analysis to an important problem in computer vision.
+: Numerical results validate the theoretical results.

Weaknesses
-: While the theoretical studies should be encouraged, the present one seems to be less influentially in practice. The assumptions make the obtained results can not be a good guide to practical image matching problem, especially the challenging ones.
-: Some obtained results from the theoretical analysis are well known ones, thus making the paper have less practical merits. For example, L312 “This implies that the larger the outlier rate the harder it is to find the correct match” L316 “We have shown that the presence of outliers in one of the two sequences has a strong negative impact on the detection region.”
-: From the given theoretical results, it seems that the image matching problem should be better solved by optimizing the Least Sum of Logarithms estimator, instead of the widely used Least Sum of Euclidean distances. However, it does not the advantages of using LSL in real data experiments. In real data experiments, it compared with an OpenCV matcher, which is the bruteforce NN matcher based on Euclidean distances. For a fair comparison, the compared matcher should also be the Hungarian algorithm, because the better matching results can be caused by such advanced matching algorithm instead of the simplest NN matcher.
-: Eq.(2) is not true in practice, especially for feature matching. In feature matching, although the matched features have identical original features \theta, the observed features are most likely to be with different variance, i.e., \sigma_i is not equal to \sigma^{#}_{\pi(i)} as shown in the latter of Eq.(2). Therefore, the theoritical results obtained by the paper is meaningless, or less useful in practice.
-: The studied case described in L161 log(nm) = O(d) does not usually hold for keypoint matching problems.

Other comments:
1. Why use the Hamming loss to evaluate the matching performance in image matching problem? What is the definition of this loss?
2. In supplement material, it would be better also provide the image matching results by the OpenCV matcher.


============= post rebuttal =======================

I appreciate the authors' feedbacks for my concerns, however, I didn't find them helpful.

(1) After reading the reply of 1 and other reviews, I still can not get the main contributions having practical influence.
About the reply of 2, I have clearly stated in the previous concerns that the real image matching experiments, the competitive method is the OpenCV matcher which is based on NN, not the LSS with Hungarian algorithm. "In real data experiments, it compared with an OpenCV matcher, which is the bruteforce NN matcher based on Euclidean distances. For a fair comparison, the compared matcher should also be the Hungarian algorithm, because the better matching results can be caused by such advanced matching algorithm instead of the simplest NN matcher." -- This is the original comment.

(2) The reply confuses my inital comment. For this point, I clearly pointed out that it is the variance being different, and of course, I mean the noise in descriptor. Please let me give an example, for image of RGB and NIR images, the descriptors of a same 3D point in the RGB images have a different variance to those of the same 3D point in the NIR images. This could also be the case of matching RGB images with different imaging conditions, such as by different cameras, different illuminations, etc.

(3) For the case log(nm) = O(d), as the authors' given example shows, 8log(10) < 20 is much less than 128, about one order of magnitude smaller. Meanwhile, in many cases, the number of keypoints is about 2k, for this case, this does not hold. In addition, even in the authors' real experiments, they used 100 vectors per pair (see also the reply to Reviewer YuHQ), which apparently violates such conditions. Is this experiment non-meaningful? or there is no way to support the theoretical results by real image matching experiments?

To sum up, the feedbacks did not address my comments, I downgrade the initial score to reject. 
limitations_and_societal_impact: n/a
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of matching two sets of vectors where the second set consists of a noisy version of the first set (inliers) together with outliers. Under a statistical framework, the paper develops theoretical bounds on the inlier-inlier and inlier-outlier separation that enable correct matching for a class of estimators including the Least-Sum-of-Logarithms (LSL). The approach follows Collier and Dalalyan, 2016, who considered the same problem without outliers. The LSL estimator is also evaluated using synthetic data, as well as in a semi-synthetic computer vision experiment using the IMC-PT-2020 real dataset for the task of feature matching towards obtaining point correspondences from two views.  
main_review: The paper considers an interesting problem with many applications. It is very clearly written and the theoretical results appear to be original and have significance. The experiments show that LSL is an interesting estimator and are on par with the theory in the paper. 

On the other hand, the paper would have been stronger if the authors had given results about the more general and practically relevant case, where both sets contain outliers. How much more difficult is that case? 
Moreover, the authors could have motivated the problem more from a general machine learning point of view. That is, they could have discussed several different machine learning applications. Instead, the application aspect of the paper including the real data experiment comes from computer vision. While this is not necessarily a drawback, there is a huge literature in computer vision regarding feature matching and from that point of view, the experiment is more of a proof of concept than anything else (e.g., one would have to also consider algorithm complexity, running times, parameter tuning e.t.c. to actually conclude that LSL outperforms OpenCV in this experiment). In my opinion it would have been more interesting to investigate a less explored and upcoming application, such as record linkage (e.g., see the work of Slawski and Ben-David already cited in the submission).

Overall, this is a very well written theoretical paper, with good results, but also with plenty of room for improvement. 

********** POST-REBUTTAL *****************
I thank the authors for their response, and I am glad my comments were well-taken. 

 

limitations_and_societal_impact: No issues as far as I can see.
review_title: null

Meta-review: While this paper considers an interesting twist on the matching problem, and is well written, the reviewers seem to indicate it would be of somewhat limited practical interest due to the existence of a much more powerful method (using a much heavier model) in openCV. And on the flip side the theoretical contributions are somewhat straightforward as they are primarily the analysis of a known (non-outlier) algorithm, but when used with assumptions on the outliers.


Decision: Reject