Topological RANSAC for instance verification and retrieval without fine-tuning
Authors: Guoyuan An
Ju-hyeong Seon
Inkyu An
Yuchi Huo
Sung-eui Yoon
Venue: NeurIPS 2023 poster (2023)
Keywords: Landmarks retrieval
non-fine-tuning
spatial verification
explainable AI
hypothesis and test
TL;DR: We combine a hypothesis-testing strategy with topological rules, enhancing explainable retrieval when a fine-tuning set is unavailable.

Abstract: This paper presents an innovative approach to enhancing explainable image retrieval, particularly in situations where a fine-tuning set is unavailable. The widely-used SPatial verification (SP) method, despite its efficacy, relies on a spatial model and the hypothesis-testing strategy for instance recognition, leading to inherent limitations, including the assumption of planar structures and neglect of topological relations among features. To address these shortcomings, we introduce a pioneering technique that replaces the spatial model with a topological one within the RANSAC process. We propose bio-inspired saccade and fovea functions to verify the topological consistency among features, effectively circumventing the issues associated with SP's spatial model. Our experimental results demonstrate that our method significantly outperforms SP, achieving state-of-the-art performance in non-fine-tuning retrieval. Furthermore, our approach can enhance performance when used in conjunction with fine-tuned features. Importantly, our method retains high explainability and is lightweight, offering a practical and adaptable solution for a variety of real-world applications.

Topological RANSAC for instance verification and retrieval without fine-tuning
Guoyuan An', Juhyung Seon', InKyu An! Yuchi Huo and Sung-Eut Eui Yoon
School of Computing, KAIST State Key Lab of CAD&CG, Zhejiang University *Zhejiang Lab
ETTII, Electronics and Telecommunications Research Institute
Abstract
This paper presents an innovative visual reasoning approach to enhancing instance verification and retrieval, partieularly in situations where fine-tuning set unavail- able. The widely-used SPatial verification (SP) method, despite its efficacy, relies on a spatial model and the pepthhesis-tssting strategy for instance recognition, leading to inherent limitations, including the assumption of planar structures and neglect of topological relations among features. To address these shorteomings, we introduce pioneering technique that replaces the spatial model with topo- logical one within the RANSAC process. We propose bio- -ooiinspired saccade and fovea functions to verify the topological consistency among features, effectively circumventing the issues associated with SP's spatial model. Our experimental results demonstrate that our method significantly outperforms SP, achieving state- of-the-art performance in non- non-fine-teee fine-tuning retrieval. Furthermore, our approach can enhance performance when used in conjunction with fine-tuned features. Impor- tantly, our method retains high explainability and is lightweight, offering practical and adaptable solution for variety of real-world applications. Our code be found through this link.
Introduction and related work
content-based image retrieval, a fundamental and long-standing challenge, has seen significant advancements due the rise of deep learning [29, 45, 7, 24]. These data-driven approaches, although successful, often rely heavily on fine-tuning with data from the same domain [24, 46]. However, acquiring such fine-tuning set can be impractical or costly, particularly in open-world private scenarios. Moreover, these methods often fall short in providing explainability, a critical factor for real-world applications where search results are integral decision-making.
In situations where a fine-tuning set absent, the esteemed SPatial verification (SP) [26] method has demonstrated the highest accuracy in verifying image pair [28]. However, its dependency spatial model for recognition exposes vulnerabilities, particularly to viewpoint changes 3D objects and neglect of topological relations among key points (Sect. 2.1). To address these issues, pioneer the replacement of the spatial model with a topological one during the RANdom SAmple Consensus (RANSAC) process. We introduce Homeomorphism Region (Def. 2.1), which cireumvents the mentioned problems, providing size metric superior to the original inlier counts used in SP. Drawing inspiration from human observation, propose innovative saccade and fovea functions to validate topological relations among keypoints within RANSAC [12] iterations (Sect. 3).
Numerous studies have explored SP [2, 31, 21, 36], but none have made such direct modification to the spatial model in RANSAC, possibly because earlier benchmarks presented the issues the spatial model as less severe [28, 26, 27J. However, with the introduction of more challenging benchmarks like ROxford and RParis [28], these problems have become increasingly critical. While some recent
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

deep-learning approaches have explored feature relations, their effectiveness diminishes without fine-tuning set, and they often lack explainability [45, 40]. In contrast, by adopting the hypothesis- testing strategy with topological rules, our method outperforms even large-scale pre-trained methods in fon-finettunnng scenarios, maintaining high explainability and lightweight nature. Moreover, can further enhance performance when used alongside fine-tuned features. These results show our novel attempt at topological-bas based RANSAC is a success.
Our contributions are summarized as follows:
We propose a novel approach to directly modify the underlying common sense in hypothesis testing. Our method is pioneering in adopting topological common sense, diverging from traditional spatial approaches. This shift paves the way for numerous future research opportunities.
Drawing inspiration from the human observation process, we introduce innovative saccade and fovea functions verify topological relations among keypoints
Our method has demonstrated a significant improvement in accuracy by adopting the dypothesis-and-tee strategy with topologiaal rules. Our method surpasses all other methods without fine-tuning. Moreover, our approach can be combined with fine-tuned features to achieve even better performance.
Our method offers a highly explainable and lightweight solution, which is crucial for real-world applications.
2 Motivation and overview
2.1 Spatial verification
RANdom SAmple Consensus (RANSAC) is an effective method for handling noisy data [12]. involves using a hypothesis and test strategy to optimize model parameters to accurately describe inliers iteratively. The model selected is crucial for achieving high inference accuracy. For instance recognition, Spatial verification (SP) [26] employs spatial model to match features in two sets of points, Pi and Pz. It finds applications a variety of contexts, such as reranking in image search [7], facilitating loop closure detection [20], and serving as a preliminary step in 3D reconstruction [35]. By using RANSAC, SP calculates a transformation matrix M to account for the spatial configuration change between different views. The similarity between the two images can then be determined using the following equation:
M p.l < <I],
PIEP:
where pi and pa represent the locations of pi E Pi and ph Ps. respectively, pI is the feature in P2 that is most similar to pf. The threshold for the location disparity is denoted by e.
The spatial model is intrinsically intertwined with RANSAC in the field of computer vision [9, 8]. and it particularly well-suited for tasks such as pose estimation where achieving an accurate homography or fundamental matrix is the primary objective [38, 233. However, despite the wealth of research surrounding the use of RANSAC for pose estimation, its integration within rigid body recognition remains under-discussed in the existing literature. This paper endeavors to address this gap, offering insights into why spatial model may not be ideally suited for recognition tasks.
SP has been the subject of numerous studies [2, 31, 21, 36]. However, none of the existing works have sought to modify the fundamental spatial model. On the other hand, while near-perfect results have been reported on the original Oxford and Paris benchmarks [26, 27]. newer challenges such as complex positives and confusing distractors have recently emerged [28]. To address these challenges, contemporary research often bypasses the RANSAC process, focusing instead on enhancing perfor- mance through tine-tuning [29, 7, 24, 40]. Nevertheless, this strategy may not be feasible in private or dynamic scenarios where fine-tuning datasets are unavailable. As discussed in Section 5, tasks involving con-finettuning recognition are of significant importance. To the best of our knowledge, in the absence of fine-tuning set, RANSAC-based SP still stands as the most effective method [28] in ROxford and RParis. This paper aims to delve into the often-overlooked aspect of enhancing the RANSAC process within rigid instance recognition tasks.

---

#inhune22
(a) SP on correct image pair
(b) SP on incorrect image pair
Generated
Dlacommeetee
Connected
Discomerted
Disconsected
Ours correct image pair
(d) Ours incorrect image pair
Figure 1: This figure presents our novel adaptation of the SPatial model (SP) [26] into the ToPological model (TP), marking the first such transformation in sypothesis-testing Sub-figures (a) and (b) highlight an instance where SP incorrectly assigns more inliers to an erroneous image pair (22 inliers) compared the correct pair (18 inliers). Conversely, sub-figures (c) and (d) demonstrate our model accurately discerns the right image pair and dismisses the wrong pair by iteratively refining the Homeomorphism Regions (HRs) based on patch connections.
In our study, we identified two significant issues when spatial model is deployed for recognition. Firstly, SP assumes that two images depicting the same plane from different perspectives can be matched using affine transformation-aa assumption that may not always hold true. Real-world objects are often dimes-dimnssional, not planar, which means the by 3 affine matrix employed in SP may not accurately represent their variations. Secondly, SP's sparse inlier count of the predicted homography matrix neglects the topologiaal relationships among features and the relevance of other image regions. This issue is evident in Fig. which presents SP results for both a correct and an incorrect image pair. Notably, the incorrect image pair generates more inliers than the correct pair, an outcome that starkly illustrates the limitations of using inlier count as the sole measure of accuracy in image recognition tasks. It is important to note that the two issues we've we've identified with SP primarily originate from the spatial model itself rather than from the hypothesis-testing strategy. This realization motivates us to modify the spatial model while retaining the hypothesis-testing approach.
2.2 Topological verification
In contrast to existing works that rely on fine-tuning to enhance performance [40, 7, 25], our study pioneers the use of topological model in place of the spatial model within RANSAC. Importantly, this approach remains viable even when fine-tuning is not feasible. We introduce the concept of Homeomorphism Region (HR) to address two primary issues associated with the spatial model. Its size is new metric for RANSAC iteration and image pair similarity. The formal definition of HRs is in Definition 2.1.
Definition 2.1 (Homeomorphism region) Let be small image patch of image I, r" and ra be the corresponding patches in I1 and Iz. R₁ = {rl....,ri) ri) and R2 {r?....,T?) r. be the families of patches of images and Iz. Ri and R2 are Homeomorphism regions (HRs), if they satisfy the following conditions:
1. Local consistency: rf E R4 and rā E Rg are identified as the same patches based on their local descriptors. [Two corresponding patches should be similar; they are supposed to depict the same region of object.]
Topological consistency: V(ri rT', rn r2, if and r overlap each other, r and r should also overlap each other, and vice versa. [Parts of an object that are connected should remain so, even when the viewpoint changes.]
3. Connectivity: VrT E 3r Orf! = 0, r E Rí [We do not consider similar but isolated patches. Note that wrong similar patches 2g and ya in Fig. I excluded from the HR in this way.]
Our novel topological perspective effectively circumvents the aforementioned problems, yielding more robust results than its spatial counterpart. In contrast to SP's planar assumption, our approach posits that parts of object that are connected should remain even when the viewpoint changes.
3

---

This assumption holds true for 3D objects. Furthermore, our topological approach considers the topological relationships between patches and leverages more information an image pair. For example, incorrect SP matches can occur when there are numerous repeated patterns, even if these matched pairs aren' 't topologically consistent with other features, as shown in Fig. 1 (b). Our model, however, correctly identifies these as different structures. As demonstrated in Fig. 1 (c) and (d), our method successfully discriminates between correct and incorrect image pairs, highlighting its potential in enhancing image recognition tasks.
3 Method detail
To find HRs, we are inspired by our brain's mechanism of comparing two first-seen objects. Our eye mostly captures low-resolution visual information except for tiny patch called the fovea. The fovea only observes very small area and the entire scene illusion is created by stitching several glimpses of the fovea during eye movements called saccade [17, 14]. Inspired by this process, we design our saccade and fovea functions to detect the HRs that satisfied the Def. 2.1.
Algorithm 1 Topological inference
Input: HypothesisSet: ((r). rr) (3) r3)....
Output: Regions: list of HRs
1: Regions [-
2: for (ri, r5) in HypothesisSet do
3: n T-
4: +' *+(((r)r)))
5:
while x/ is not empty do
6:
(r1. 12)= pop(st)
Algorithm 1 shows the overall pipeline of our method. Traditionally, RANSAC samples a sub- set and computes a hypothesis based on this selection. We modify this approach by using each ratio test matching result as an individual hypothesis. Therefore, the size our sample subset is effectively reduced to one, with each iteration's 's hypothesis being the translation, as opposed to the affine matrix. Instead of counting inliers based on the spatial constraint, we detect HRs for each hypothesis, the size of which is then used as the new iteration metric. We recognize that the sampling strategy and convergence proof the focal points of ongoing RANSAC research. However, the first study to adopt topological perspective, this paper primarily seeks to demonstrate the feasibility and advantages of this paradigm shift.
7:
FI. f2. veri verified=F(ri, r2)
8:
if veri verified- = True then
9:
Add (f1, (2) to x'=S(T)
11: end if
end while
13: add to Regions.
end for
3.1 Topological consistency and connection
To verify the connection and topological consistency, progressively verify and select the patches one by one. can be expressed as follows:
/ met) F(T(),
Te+1
where S is the saccade function to guide the observation place, F is the fovea function to verify two patches, my records the verified patches at /-th iteration, mo the given hypothesis about translation, and ni records the candidate patches generated by S. and T/ are shown using green and purple boxes in Fig. 2. After finishing this verification progress, the final verified region øy will be treated the HR defined in Section 3. The saccade function S makes the new candidate patch intersect with one and only one verified patch in T., as shown Fig. 2. In this way, a series verified patches connected with each other and also satisfy the topological consistency.
Under the assumption that two images are depicting the same object with some transformations (zoom, foreshortening, vertical shearing), the saccade function S predicts the area around the verified patch pair will be similar. For example, A and f22 Fig. are two verified patches, and saccade function S expects the patches around them are also similar. The correspondence patch location and size will refined by F, as shown in the next section. Similar to [26), we do not consider in in-plane image rotations because of the fact that images usually displayed with the correct orientation.

---

Iteration
Generated HRs
Working memory x recording verifted patches
π
π
WWrriin memory x'
recording candidate patches
TE
Fovea function
Saccade function
points
Candidate patch
Candidatee patch rg.
Patch location adjustment
Verifind
Verified patch
Generate candidate patches based on P. and P3
Compute Computesimillrity similarity
patch
Figure 2: The process of finding HRs for each hypothesis. This is an iterative method. Fovea function F verifies the similarity between two candidate patches at each iteration, and saccade function S updates the candidate patches.
3.2 Local consistency
The fovea function concentrates on two patch areas and verifies the query patch ri and test patch r2 are similar based on the local feature sets P1 and P2 images / and /z.
Feature matching. The first step for verification is to match the key points in two images correctly. Traditional geometric verification directly searches the nearest neighbor of keypoint in / from keypoints in Iz based on their descriptors. However, we observe this approach may have many wrong matching points in practice due to the repeated patterns in image, shown in Fig. 1. To address this problem, we restrict the search region when implementing the fovea function. That is, for each key point in patch r1, find its nearest neighhor among keypoints in patch r2 instead of T2. We find that this approach increases the matching performance.
Patch location adjustment. We need to adjust the location and size of the candidate patches here. Because r1 and 72 are candidate patches generated by saccade function only based on the verified region their contents may not be exactly same. As shown in Fig. 2, the scope of patch is different from patch rı. After the feature matching, we treat the r2 region containing the matched points as the adjusted corresponding patch r22, as shown in Fig. 2.
Locally spatial constraint. Two main challenges of object verification are the location disparity of the key points due to the view change of two images and the matching outliers, Fortunately. our saccade function S has separated an object into patches. offers three benefits. Firstly, because the patch size is smaller than the whole image, patch is more likely to depict the 2D plane of 3D object. Locally using the spatial constraint like Eq. (1) can more robust than the origin SP. Secondly, we can assume the center points of patches ri and rl are correct if they share the same pattern. That we assume e = C2 = c, where с₁ and C are the center locations Y1 and r/. Treating e as the reference point, the disparity of two correct matching key points p and P is (M [) - c). where I is the identity matrix. So Eq. (1) can be rewritten as:
F= Σ (p pi) - (M () c)ll c]. BfEm
Like [26]. we do not consider the in-plane rotations and overturn. We try to infer a threshold of disparity (p²2 pi) based on (pí - e) without calculating a correct M. Note that the upper bound of p cl is half of the patch diagonal length.
Thirdly, because fovea function only focuses on the regional patterns, we can assume there is no unrelated object occlusion in r1 and r/z. Thus, we use the inlier ratio to replace the inlier number of SP:
F
Σ (p) -Pi) - (M () - -c)ll < <.]
r
5

---

where |r1 is the number of local features in r1. This change is to use probability to deal with the uncertainty of feature matching. Although difficult guarantee the accuracy of a specific local feature matching, we expect the clear different inlier ratio distributions between the correct patches and in-correct patches with enough matching samples.
Implementation. We simplify Eq. (4) for the easy of computing. For pi E T1, the expectation location of its corresponding point p1 E Er2 is pi (M - () c). Because photos are taken from a restricted range of canonical views, transformation M varies in a restricted space. We try to predict the location P9 based on (p) - e) without calculating correct M. To do so, we divide r1 and r into 3 by 3 sub-patches and each sub -athh contains some points. That is
[aj 02, ... 0g] and by]. where ag and by are correspondence sub-patches. For matching point pair pi and pi E 22 if pi locates in ag we expect its corresponding point p1 will be in bg. In this way, we simplify the Eq. (4) as:
r [b1.
F(r =
[ak; f (ak, bb)) =
Σ
k(pn: ((Pn:Ph);
(5)
lak
Pr Eap
where and ph are two matched points, k(pn, P/a) = 1 if p/n by, otherwise k(pn. P'n. = 0.
4 Experiment
Table 1: Results (% mAP) on the ROxf/RPar datasets and their large-scale versions
ROxf+1M/RPar+1M, with both Medium and Hard evaluation protocols.
ROxf
ROxf+RIM
RPar
RPar+RIM
Method
M
H
M
H
M
H
M
H
compare inference ability using SIFT
VLAD [19]
37.6
21.7
31.4
10.7
83.2
69.1
69.5
44.7
ASMK [42, 48, 45]
49.6
29.1
41.4
18.0
83.6
69.5
66.2
44.4
(with ratio test) [28, 26]
64
42
56.3
30.5
86.3
71.6
70.1
46.4
SP (without ratio test) [28, 26]
44.4
23.3
37.3
13.5
83.7
69.0
66.9
44.2
GCRANSAC [5]
63.3
40.2
55.7
29.7
85.9
71.0
69.6
45.7
TP with SP (Ours)
68.6
46.3
59.2
33.9
86.6
71.7
70.5
46.6
TP without SP (Ours)
69.5
46.9
60.4
34.4
86.5
71.6
70.6
46.8
vs. pre-trained models
CLIP (RNIOI) [30]
46.4
21.9
39.4
12.5
85.1
70.0
68.9
45.7
CLIP (ViT-B/32) [30]
47.5
24.0
38.0
13.2
83.9
68.9
69.2
46.1
Superpoint [10]
66.1
42.4
59.4
33.4
85.9
71.0
70.0
46.1
vs.
large-scale fine-tuned models
GeM
[29] [29] (GLD) [46]
71.0
49.1
57.1
30.3
86.6
72.4
70.2
46.6
GeM 22 +AP [32 (GLD) [6
69.9
48.2
55.1
29.1
86.8
72.7
70.5
47.1
4.1
Experiment setting
In our study, we contrast our novel ToPological verification (TP) approach with established methods like SP, Vector of Locally Aggregated Descriptors (VLAD) [19], and Aggregated Selective Match Kernel (ASMK) [42], employing standard SIFT features for the comparison. For SP, utilize both standard RANSAC and Graph-Cut RANSAC (GCRANSAC) [S], recognized as one of the superior RANSAC methods. The conventional comparison for SP involves reranking the top 100 images found by ASMK using the same local feature [28]. As advanced initial ranking methods can introduce more challenging images and elevate the difficulty [28], we opt for the state-of-the-ar fine-tuned feature DELG [7] over SIFT for initial ranking. For fairness, all methods rerank the top 100. Though our primary focus not on enhancing representative learning, we contrast our method with state-of-fe -fe--o--thherrrr (SOTA) pre- pre-training and fine-tuning techniques to underscore the importance of this inference direction and its potential for future exploration. We benchmark our method against pre-trained methods CLIP [30] and Superpoint [10]. In terms of the fine-tuning approach, we choose methods fine-tuned on the extensive, cleaned Google Landmark Dataset (GLD) [46]. We notice that
some recent studies claim that GLD is not a fair fine-tuning set for ROxford and RParis because there

---

are overlapped landmarks [45]. We agree with this claim. However, we still compare our approach with SOTA methods fine-tuned on GLD because our method does not need any fine-tuning, and the methods fine-tuned on GLD,, although have fairness issues, show the best performance on ROxford and RPairs. We compare our method with the well-known GeM [29]. fine-tuned on GL.D using contrastive loss (CI.) and AP loss (AP) [32]. To demonstrate the generalizability of our TP, we pair with the SOTA fine-tuned features of DELG [7] and the SOTA re-ranking method Hypergraph Propagation (HP) [3]. We notice that there are existing claimed better results than DELG and HP on ROxford and RParis, but combining DELG and HP is the best baseline we can successfully reproduce by the submission date of this paper.
4.2 Quantitative result
As depicted in Table 1, our method notably surpasses SP, GCRANSAC [5], ASMK, and VLAD across all settings. It signifi- cantly outperforms SP by 8.6% and 11.7% on the challenging ROxford under middle and hard settings, respectively. This underlines the fea-
Table 2: Results (% mAP) of HP the ROxford.
sibility and effectiveness of our novel adaptation of the topological model in RANSAC. Given the widespread usage of SP [26, 33, 35, 34] and its competitiveness with other instance recogmition approaches in
Method
M
H
terms of accuracy [28, 7, 24],, this improvement is particularly note- worthy. Our results represent the top mon-fine-tuning performance on ROxford and RParis. While GCRANSAC excels at predicting homography or fundamental matrices [5], it does not surpass stan- dard RANSAC in our recognition task. This may be due to the spatial model's incompatibility with recognition tasks, suggesting that enhancing spatial-based RANSAC may not improve landmark recognition performance. In an ablation study conducted to assess the impact of using SP to filter the hypothesis set, found that incorporating SP surprisingly led to a decrease in final accuracy. Despite our Python-basee method averaging 1.23s per image pair, slower than C- C-implemented SP at 0.53s, we anticipate considerable speed improvements with a C-based implementation of our method.
SP (hopl)
80
61
Our TP (hop1)
81
63
SP (hop2)
85
69
Our TP (hop2)
86
71
Our TP outperforms notable pre-trained models, including CLIP [30] and Superpoint [10], without requiring any training. Although CLIP delivers fair performance, it falls short of both SP and TP. These results underscore the competitive edge of the hypothesis- testing strategy for landmark recognition in highly noisy situations, even against large-scale pre-trut pre-training methods. Despite Superpoint's superiority to SIFT in SP and its enhancement of inference performance, it remains less effective than our TP. These results attest our TP's ability to circumvent the inherent issues of the spatial model for recognition.
Our novel TP method demonstrates competitive results against the renowned GeM [29], fine-tuned on the large cleaned Google landmarked dataset (46.) without any pre-traiee pre-training or fine-tuning. This comparison, while unconventional due to TP being reranking method and GeM initial ranking method, is meaningful. GeM, a state-of-the-art retrieval baseline, marked mile- stone as the first metric learning method to surpass non-fine-tuned SP approaches [28], following a series of improvements from selective search[41] to R-MAC [43]. Since then, non-fine-tuning techniques have seen limited advancements. However, TP breaks this trend, achieving comparable results to GLD-trained GeM. This is not say SIFT is enough for this task but
Query
Target
Accupt (-40
0,22
(40
Terget putches
Seniianta
Paject
Peject (c))
Rejoct (cm)
Figure 3: SP results, TP results, and some TP steps for verifying a correct image pair (upper) and a wrong image pair (down) using SIFT features. The threshold a is set as 0.2.
7

---

Winlired
SP
Minliessti
Ainliens221
Winlters:22
Pinlers::
Ainliers:21
Ours
Figure 4: Hypergraph propagation results using traditional SP (upper) and our method (down). In each triplet, the first image and third image are different. Red lines show SP's wrongly connected local features between the first image and the third image. The orange and green regions show the verified HRs between each image pair. Our method correctly separates the local features of the first and the third images. HR is the union of many verified patches. We only show the outline of key points in HR for ease of observation.
to emphasize the potential of hypothesis testing when combined with a topological model for non-fine-tuning image retrieval.
We acknowledge that advancements in fine-tuning features for ASMK or SP, such as SuperFeature and DELG [45, 7]. have emerged recently. While it is possible to train features for our TP, we leave this for future work, as this work mainly focuses on the non-fine-tus non-fine-tuning retrieval. However, to show method's I generalization capabilities, Hypergraph Propagation (HP) [3]. HP is a fast reranking method that combines verification and diffusion local features. It runs the heavy verification offline and thus achieves fast, low-memory, and high-accuracy reranking online. Table 2 demonstrates that our method outperforms SP on HP, irrespective of propagating among hopl hop2 neighbors; hop1 hop2 is the truncation hyperparameter in diffusion [3]. This improvement is noteworthy, considering it does not necessitate any additional training. This is the SOTA retrieval performance ROxford to the best of our knowledge.
still apply TP to fine-tuned DELG local features and
We understand that readers may have concerns about the practical value of a RANSAC- method in retrieval, given its slower processing time compared to using dot products with lcarned embedding vectors. However, it is important to note that if RANSAC can provide reliable labels without fine-tuning, these labels can be used directly to train the embedding space for any database, eliminating the need for specially collected fine-tuning set. As we shown in Table 2, it can also directly improve HP accuracy. Because verification in HP is offline, the slower speed of RANSAC is acceptable. Furthermore, SP is employed not only in retrieval but also in other tasks mobile devices where model size is crucial, such as loop-closure detection. Our TP. which shares the lightweight nature of SP without involving millions of parameters like models such as ResNet [15], offers enhanced robustness and accuracy. Most importantly, our method is highly explainable, which we will discuss in the following section.
4.3 Qualitative result
In addition to its accuracy, our method exhibits high explainability, a crucial aspect for real-life applications. The explainability of our method can be understood in three aspects:
We can observe how the HRs are constructed step by step, find a correspondence patch for each patch in HR, and check how each candidate patch pair is accepted or rejected by the fovea function F. as shown in Figs. 2 and 3. These characters offer a clear understanding of how our method works.
2. The TP detected HRs and matched patches are easy to comprehend, whether using SIFT (Fig. 3) or DELG (Figs. 1 and 4). As shown in the upper row of Fig. 3, although SP can also give a high inlier number for the correct image pair, its found matchings can be wrong. Our TP gives more reasonable results. This issue of high inlier counts with incorrect matchings is also observed in DELG, suggesting that fine-tuning can improve the similarity of local features for the same object, but cannot guarantee the accuracy of their locations. Additional examples are provided in the supplementary material. Fig. 4 compares the qualitative performance of SP and our TP on HP. The first query and third image in each triplet do not depict the same building. Due to SP's erroneous matching of some local features (indicated by red lines), a search engine using SP mistakenly identifies the third
8

---

image as positive match. In contrast, our method accurately matches the correct similar regions between two images and can correctly determine that the third image unrelated to the query, thereby enhancing retrieval performance.
3. Our approach maintains explainability, even in cases of false positives and negatives, offer- ing valuable insights into the effectiveness and potential issues at each stage. We have visual- ized all false negatives (FN) and positives (FP) in Fig. 5. For more comprehensive review, we provide link for readers to explore further. Interestingly, without context, many FP cases are challenging for the authors to distinguish, signaling the effectiveness of our fovea func- tion in generating reasonable patch similarity results. Upon examining FN cases, recog- nize areas for enhancement. The primary issues lie in incorrect ratio test results and significant size changes. While our method considers size changes, it struggles with handling extreme vari- ations. An easy solution is to multi-rescale each image and traverse all possible matching scales, We refrained from this to avoid significantly reducing speed and to maintain a fair comparison with SP. However, future work could potentially apply this strategy or devise better sampling method to manage extreme scale changes, thereby improving performance.
Quety
Quary
Fb:
Ouers
IN
Figure 5: The false positive (FP) and false nega- tive (FN) cases of our method. We draw the SIFT feature locations in the largest detected HRs for FP cases and the ratio test results for FN cases. Check more examples in the supplementary ma- terial. Check all the FP and FN cases from this link.
5 Discussion about the task value
This paper aims to advance explainable image retrieval in scenarios where a fine-tuning set is unavailable. This pursuit carries significant weight as acquiring large fine-tuning set can often be impractical or costly, especially in open- world or private settings. Therefore, research in this domain has the potential enhance the utility of AI systems across variety of real-world contexts.
Our exploration into non-fine-tuned retrieval is further motivated by the observed gap between human- level performance and that of the state-of-the-ar (SOTA) fine-tuned models [4, 40] on challenging datasets such as ROxford/ RParis [28] and PROxford/ PRParis [3]. Notably, these datasets provide invaluable user study results, as each positive image pair is verified to be identifiable by humans without the need for contextual visual information [28, 4]. Our recent study shows that annotators who are not familiar with European buildings can recognize, localize, and segment the target landmark of all the positive image pairs in ROxford and RParis. We propose the rixel-retrieal task and its first benchmarks PROxford and PRParis, evaluate the pixel-level recognition [4]. Interestingly, humans achieve this remarkable recognition ability without extensive in-domain training, such as learning from the Google Landmarks Dataset (GI.D) [46]. Yet, even the best fine-tuned models [7, 40] trained on the vast GLDD with 4.1 million images have yet to reach human-level accuracy on ROxford/R SeerndRPartt Paris and PROxford/PRParis. This discrepancy prompts us to question how humans excel in such recognition tasks without large-scale fine-tuning.
The process of recognition is a confluence of perception and cognition. The superior instance recognition of humans in the ROxford dataset might be more cognitively inclined, though concrete evidence remains elusive. Cogmition entails reasoning based on existing knowledge for decision- making and the discovery of new knowledge [47, 13, 37]. When summarizing notable human instance recognition experiments [6, 16, 39]. Greyson [1] defines perception as the direct link between an instance and its visual features, while cognition involves understanding the object's changes in viewpoint or state (e.g., background and illumination) [47, 1, 11, 22]. Machine learning methods that align with this definition of cognition include ASMK [42] and SP [26], which further motivates us to explore improvements to SP without fine-tuning. Future research discerning the nuances between perception and cognition could potentially enhance non-fine-tuning methods for world applications.

---

6 Conclusion
Our study highlights the limitations of the SPatial verification (SP) method, particularly its reliance on spatial model for recognition. As a potential alternative, we propose the use of topological common sense, which significantly outperforms SP and achieves unprecedented performance in non-fine-tuning instance recognition. This underscores the potential of hypothesis-teestin inference.
The inspiration for our saccade and fovea function comes from the human process of comparing two newly seen images. In this sense, our topological approach aligns more closely with the human visual system than the spatial approach. While humans don't tt compute transformation matrices like SP when comparing images, they intuitively understand the topological relations among observed objects- for instance, recognizing that a hand is connected to an arm. Notably, topological information is vital to the human visual system, as it is consistently preserved even when visual signals undergo significant deformation during transmission from the retina to the lateral geniculate nucleus and visual cortex [44, 18].
Importantly. our method doesn't It compete with existing fine-tuning methods but complements them. can directly integrate learned features, and future work could even fine-tune features specifically for this topological approach.
While our results are promising, they also pave the way for future exploration. Subsequent work could investigate the incorporation of more complex common sense concepts, both explicit, like our topological model, and implicit, derived from pre- to-itraiiing.... Enhancements in these areas could potentially boost the robustness and adaptability of our method. Further study into the convergence properties of our method and refinement of the hypothesis sampling strategy are also warranted. Through addressing these areas, aspire to advance object recognition and highlight the potential of hypothesis-tesie testisg approaches in artificial intelligence.
Acknowledgments
We would like to thank the anonymous reviewers for their valuable comments and insightful sug- gestions. Sung-Fui Yoon the corresponding author of this paper. This work was supported by the Institute of Information & communications Technology Planning & (valuation(IITP) grant funded by NBSS2023-00237966 Recognition, Action and Interaction Algorithms
the Korea government(MSTT) for Opendworld Robot Service) and the National Research Foundation of Korea(NRF) grant funded by the Korea goVeMmenn(MMSIT) (No. RS-2023-00208506)
References
[1] Greyson Abid. Recognition and the prrception-cognitti divide. Mind & Language, 37(5)777--79,, 2022
[2] Sameer Agarwal, Yasutaka Furukawa, Noah Snavely, lan Simon, Brian Curless, Steven M Seitz, and Richard Szeliski. Building rome a day. Communccations of the ACM, 54(10) 105 112, 2011. 1,2
[3] Guoyuan An, Yuchi Huo, and Sung-Eui Yoon. Hypergraph propagation and community selection for objects retrieval. Advances in Neural Information Processing Systems, 34, 2021. 7,8,9
Guoyuan An, Woo Jae Kim, Saelyne Yang, Rong Li, Yuchi Huo, and Sun-Fui Yoon. Towards content-based pixel retrieval revisited oxford and paris. Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 20507-205 18, 2023. 9
[5] Daniel Barath and Jiří Matas. Graph-cut ransac. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6733-6741, 2018. 6,
[6] Timothy F Brady, Talia Konkle, George A Alvarez, and Aude Oliva. Visual long-term memory has a massive storage capacity for object details. Proceedings of the National Academy of Sciences, 105(38):44325 -43329, 2008. 9
[7] Bingyi Cao, André Araujo, and Jack Sim. Unifying deep local and global features for image search. In European Conference on Computer Vision, pages 726 743. Springer, 2020. 2, 7, 8,
[8] Sunglok Choi, Taemin Kim, and Wonpil Yu. Performance evaluation of ransac family. Journal of Computer Vision, 24(3):271-300, 1997. 2
[9] Konstantinos G Derpanis. Overview of the ransac algorithm. Image Rochester NY, 42):4(11333200 3,200.. 2
10

---

[10] Daniel DeTone. Tomasz Malisiewicz, and Andrew Rabinovich. Superpoint: Self-supervised interest point detection and description. In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pages 224-236, 2018. 6.7
[11] Xiaoxu Fan, Lan Wang. Hanyu Shao, Daniel Kersten, and Sheng He. Temporally flexible feedback signal to foveal cortex for peripheral object recognition. Proceedings of the National Academy of Sciences.
113(41):
2016.9
[12] Martin A Fischler and Robert C Bolles. Random sample consensus: paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6):381-333
1981. 1,2
[13] Michael S Gazzaniga. The cognitive neurosciences. MIT press, 2009.
[14] lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning- MIT press, 2016. 4
[15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
[16] Andrew Hollingworth and John M Henderson, Accurate visual memory for previously attended objects in natural scenes. Journal of Experimental Psychology: Human Perception and Performance, 28(1): 13, 2002. 9
[17] David H Hubel and Torsten N Wiesel. Receptive fields of single neurones in the cat's striate cortex. The Journal of physiology, 14853)5774, 1959. 4
[18] Andrew D Huberman, Marla Feller, and Barbara Chapman. Mechanisms underlying development of visual maps and receptive fields. Annual review of neuroscience, 31:479, 2008. 10
[19] Hervé Jégou, Matthijs Douze, Cordelia Schmid, and Patrick Pérez. Aggregating local descriptors into compact image representation. In 2010 IEEE computer society conference on computer vision and pattern recognition, pages 3304-3311. JEEE, 2010.
[20] Dongjiang Li. Xuesong Shi. Qiwei Long, Shenghui Liu, Wei Yang. Fangshi Wang. Qi Wei, and Fei Qiao. Dxslam: A robust and efficient visual slam system with deep features. In 2020 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4958-4458 4968. IEEE, 2020. 2
[21] Xiaowei Li, Changchang Wu, Christopher Zach, Svetlana Lazebnik, and Jan MinMicl Frahm. Modeling and recognition of landmark image collections using iconic scene graphs. In Computer Vision-ECCV 2008: 10th Eurppan Conference on Computer Vision, Marseille, France, October 12-18, 2008, Proceedings,
Part 1 10, pages 427-440. Springer, 2008. 1,2
[22] Earl K Miller and Jonathan D Cohen. An integrative theory of prefrontal cortex function. Annual review of neuroscience, 24(1):167-202, 2001.
[23] Raul Mur-Artal, Jose Maria Martinez Montiel, and Juan D Tardos. Orb-slam: a versatile and accurate monocular slam system. IEEE transactions robotics, 31 31(5):1147-116) 2015. 2
[24] Hyeonwoo Noh, Andre Araujo, Jack Sim, Tobias Weyand, and Bohyung Han. I Large-scale image retrieval with attentive deep local features. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017. 2.
[25] Hyeonwoo Noh, Andre Araujo, Jack Sim, Tobias Weyand, and Bohyung Han. Large-scale image retrieval with attentive deep local fcatures. In Proceedings of the IEEE international conference on computer vision,
pages 1466-3465, 2017. 3
[26] James Philbin, Ondrej Chum, Michael Isard, Josef Sivic, and Andrew Zisserman. Object retrieval with large vocabularies and fast spatial matching. In 2007 IEEE conference on computer vision and pattern recognition, pages 1-8. IEFF, 2007. 1, 2, 3, 5,5, 6, 7,9
[27] James Philbin, Ondrej Chum, Michael Isard, Josef Sivic, and Andrew Zisserman. Lost in quantization: Improving particular object retrieval in large scale image databases. In 2008 IEEE conference on computer vision and puttern recognition, pages 1-8. IEEE, 2008. 1,2
[28] Filip Radenovié, Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondřej Chum. Revisiting oxford and paris: Large-scale image retrieval benchmarking. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5706-5715, 2018. 1,2, 6, 7.9
[29] Filip Radenović, Giorgos Tolias, and Ondiej Chum. Fine-tuning enn image retrieval with no human annotation. IEEE transuctions on puttern analysis and machine intelligence, 41(7):1655-166, 2018. 1, 2,
6.
[30] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages 8748 8763. PMLR, 2021. 6.

---

[31]
Rahul Raguram, Joseph Tighe. and Jan-Michael Frahm. Improved geometric verification for large scale landmark image collections. In BMVC, pages 1-11, 2012. 1,2
[32] Jerome Revaud, Jon Almazán, Rafael S Rezende, and Cesar Roberto de Souza. Learning with average precision: Training image retrieval with listwise loss. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5107-5116, 2019. 6,
[33] Johannes Lutz Schönberger and Jan-Michael Frahm. Structure-from fro--moooooooo revisited. In Conference on Computer Vision and Pattern Recognition (CVPR), 2016. 7
[34] Johannes Lutz Schönberger, True Price, Torsten Sattler, Jan-Michacl Frahm, and Mare Pollefeys. vote-and-verite strategy for fast spatial verification in image retrieval. In Asian Conference on Computer Vision (ACCV), 2016."
[35] Johannes I Lutz Schönberger, Enliang Zheng, Marc Pollefeys, and Jan-Michael Frahm. Pixelwise view selection for unstructured multi-view steren. In European Conference on Computer Vision (ECCV), 2016.
2,7 7
[36] Xiaohui Shen, Zhe Lin, Jonathan Brandt, Shai Avidan, and Ying Wu. Object retrieval and localization with ppatially-oonstraneee similarity measure and k-nn re-ranking. 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 3013-3020. IEEE, 2012. 1,2
[37] Zhongzhi Shi. Intelligence science: Leading the age of intelligence. Elsevier, 2021. 9
[38]
Jamie Shotton, Ben Glocker, Christopher Zach, Shahram Izadi, Antonio Criminisi, and Andrew Fitzgibbon. Scene coordinate regression forests for camera relocalization in rgb-d images. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2930-29333 2013. 2
[39] Lionel Standing. Jerry Conezio, and Ralph Norman Haber. Perception and memory for pictures: Single-triat trial learning of 2500 visual stimuli. Psychonomic science, 19(2) 74, 1970. 9
[40] Fuwen Tan, Jiangbo Yuan, and Vicente Ordonez. Instance-level image retrieval using reranking transform- ers. In proceedings of the TEEE/CVF international conference on computer vision, pages 12105-12115, 15, 2021. 2, 3,9
[41] Ran Tao, Efstratios Gavves, Coes GM Snock, and Arnold WM Smeulders. Locality in generic instance search from one example. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2091-2098, 2014. 7
[42] Giorgos Tolias, Yannis Avrithis, and Hervé Jégou. To aggregate not to aggregate: Selective match kernels image search. Proceedings of the IEEE International Conference on Computer Vision, pages 1401-1408, 2013. 6, 9
[43] Giorgos Tolias, Ronan Sicre, and Hervé Jégou. Particular object retrieval with integral max-pooling of cnn activations. arXiv preprint urXiv:1511.055 105879,,.......... 2015. 7
[44] Brian A Wandell, Serge O Dumoulin, and Alyssa A Brewer. Visual field maps in human cortex. Neuron, 56(2):366-38) 383, 2007. 10
[45] Philippe Weinzaepfel. Thomas Lucas, Diane Larlus, and Yannis Kalantidis. Learning featurreaturs for image retrieval. arXiv preprint 22 13/82, 2022. 1, 2, 6, 7,8
[46] Tobias Weyand, Andre Araujo, Bingyi Cao, and Jack Sim. Google landmarks dataset v2-a large-scale benchmark for instance-leve recognition and retrieval. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2575-2588 2020. 1, 6, 7,9
[47] Jeremy M Wolfe, Kyle R Cave, and Susan I. Franzel. Guided search: alternative to the feature integration model for visual search. Journal of Experimental Psychology: Human perception and performance, 15(3):419, 1989. 9
[48] Hui Wu, Min Wang, Wengang Zhou, and Houqiang Li. Leamiing deep local features with multiple dynamic attentions for large-scale image retrieval. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11416-11422 2021. 6
12


Reviews:
[{"review_id": "wqBj5FEjdh", "reviewer": "Reviewer_X5kj", "summary": "This paper proposes an approach in the area of image retrieval, more specifically landmark retrieval. Authors propose a new method for spatial verification that replaces standard and commonly used spatial model in RANSAC-based approaches, with topological one. Experiments show SOTA performance using handcrafted features, that even beats pretrained and is comparable to fine-tuned approaches.", "questions": "My first weakness is something that should be addressed in the rebuttal, ie the time and memory analysis. Other two weaknesses: ablate different features and visual geo-localization are improvements that would make paper stronger, but are not necessary. ", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "+ Strong contributions: novel approach in hypothesis testing with RANSAC that is very different than traditional approaches and refreshing, inspiration from bio processes.\n+ Very strong results with hand-crafted SIFT features and well established ranking framework with spatial verification. \n+ Well written paper\n+ Good experimental section, properly set baselines, good comparisons", "weaknesses": "- Time and memory analysis missing. It would be interesting how does this approach compares with standard RANSAC, and also how does the whole framework compare with competitive frameworks during inference\n- This approach could be combined with other local features, even the trained or fine-tuned ones. It would make paper stronger if it was shown how well does it work with features beyond SIFT\n- Spatial verification can be applied and help in visual geo-localizations on benchmarks such as Pittsburg30k and Tokyo24/7, it would be interesting to see how this method works there", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer X5kj,\n\nThank you for your thorough feedback and for recognizing the strength of our contribution. We value your insights and would like to address each of your questions:\n\nTime and Memory Cost: We have provided details on time costs in lines 246-248 of our paper. Our TP, implemented in Python, averages 1.23s per image pair, making it slower than the C-implemented RANSAC SP at 0.53s. Nonetheless, transitioning to a C-based implementation promises substantial speed enhancements. The time distribution across the entire retrieval pipeline can be seen in Table 4 of the attached rebuttal pdf. When compared to the initial ranking stage (0.57s), the reranking stages of SP (53.2s) or TP (123.4s) appear relatively time-consuming. However, this disparity can be attributed to implementation techniques. Parallel implementation of SP/TP verification can drastically cut down time, particularly if the top 100 are verified concurrently. Regarding memory costs, these can be broken down into model size and local feature costs. Both SP and TP are lightweight and mobile-friendly, avoiding the cumbersome millions of parameters seen in models like ResNet. The memory cost for local features is identical for SP and TP. In scenarios where real-time feature calculation is feasible, this cost, such as with SIFT features, is minimized to an average of 0.43 MB per image (in numpy array format) in the Oxford set.  For tasks where memory consumption is a critical factor, the memory costs associated with our method can be mitigated. By leveraging real-time feature calculation, we can bypass storing extensive local features. This on-the-fly computation is about 0.16s per image pair.\n\n\nCompatibility with Other Local Features: We demonstrated the efficiency of integrating TP with DELG local features in paper table 2; our TP+DELG scored 86 and 71 on ROxford, surpassing the 85 and 59 of SP+DELG. In the attached rebuttal PDF, we also provide a comparison between SP+superpoint and TP+superpoint. The results show TP+superpoint scoring 69.5 and 46 on ROxford, as opposed to SP+superpoint's 66.1 and 42.4. Based on these comparisons across SIFT, DELG, and Superpoint, we posit that TP is a superior alternative to SP for rigid-body retrieval tasks.\n\nGeo-localization Experiments: At your suggestion, we conducted an evaluation on geo-localization. We used the renowned MSLS dataset. Our method's efficacy on the challenging MSLS validation set can be seen in table 3 of the attached pdf. Our approach notably outperforms SP when using SIFT features (top1 recall 0.59 vs. 0.74). Considering SP's prowess in geo-localization tasks, our TP's significant performance boost (25% improvement) was a pleasant surprise. After observation, we think the reason is that street views in geo-localization often deviate considerably from the plane assumption inherent in SP. This deviation means that the SP might primarily identify just one side or facet of the street, leading to its limitations in this scenario. In contrast, our TP demonstrates more adaptability under these conditions, making it a more versatile choice for such applications. Notably, our TP paired with SIFT even rivals the performance of the cutting-edge, fine-tuned R2Former model (CVPR '23), with top 1 recalls of 0.74 vs. 0.81, respectively. This experiment underscores our method's versatility.\n\nWe are grateful for your thoughtful review and hope our clarifications prove satisfactory.\n\nWarm regards,\n\nAuthors\n\n"}, {"review_id": "bP7Mypchg9", "reviewer": "Reviewer_WpBp", "summary": "This paper reexamines the classical instance recognition problem in computer vision, a problem that holds great significance in applications such as image retrieval. In recent years, data-driven approaches that relying on fine-tuning pre-trained deep models have drawn much attention. However, these methods not only face the difficulties in obtaining the data for fine-tuning in real-world applications, but also lack explainability. The authors closely examined the vulnerabilities of SPatial verification (SP) method, which remains the most performant method in non-fine-tuning setting, and propose the new Topological verification (TP) model to replace SP in the RANSAC process. Inspired by human vision system, TP-based RANSAC is a region-growing algorithm which seeks and maximizes Homeomorphism region (HR). Starting from some seed patches called Hypothesis Set, the *fovea* and *saccade* function iteratively examines neighboring regions and expands HR by enforcing several important conditions, including *local consistency*, *topological consistency* and *connectivity*. Evaluation on challenging benchmarks, such as ROxf/RPar and ROxf+1M/RPar+1M, demonstrates that the proposed method establishes new SOTA performance across all methods without the need for fine-tuning.", "questions": "1. It is not very clear to me how to obtain the initial hypothesis set? It perhaps has been standardized by previous RANSAC-based SP methods. I still think it appropriate to mention it in the paper for clarity.\n2. How does saccade function work? I assume that it is similar to most advancing front techniques, as illustrated by part of Figure 2. I don't seem to find more details in the supplemental material as well.\n3. How to perform patch location adjustment? I assume that it is accomplished by computing the minimal enclosing bounding box of the matched key points.", "limitations": "Nowadays, the mainstream research seems to lean towards seeking for larger and stronger per-trained models to vectorize everything and simplify the retrieval problem as similarity search by simple operations like dot products. Focusing on right instance recognition, the topological model excels in single modality domain and has little applicability in cross-modality retrieval tasks as popularized by CLIP. On the other hand, inspired by human vision system, this work could also be a great example showing that the pursue of large models might be a detour when solving a cognitive problem.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "After a decade with deep learning techniques dominating the CV/ML/AI world, it is refreshing and delightful to read this paper, which revitalizes the classical algorithms by introducing many insights and advancements. The authors delve into the SP model that has been widely used in the hypothesis testing of RANSAC process and identify its vulnerabilities that were long overlooked by the previous methods. This is remarkable considering the recent trend of pursuing stronger features through fine-tuning. As discussed in Section 5, it is evident that as humans, we can easily determine if the given image pair is a mismatch without too much contextual information. It is intriguing to observe how the topological rules introduced in this paper closely emulate the tactics that humans may leverage to solve this problem. The bio-inspired fovea and saccade functions effectively replicate such brain mechanisms in an algorithmic fashion. Compared to the SP model and fine-tuning methods, the topological model possesses better explainability. Moreover, it retains the characteristic of not necessitating fine-tuning while also being compatible with large-scale pre-trained models. The benchmarking results are exceptional. I particularly like the insightful discussions in Section 5. It is a very good read.", "weaknesses": "If I have to point out one weakness of this paper, I would say that there are still some missing details (some are listed in the Question section of this review) in the main paper and supplemental material, though most of them are minor and does not cause difficulty in understanding the method. However, I still think that the paper could be made a little clearer for readers who do not particularly work on instance recognition and image retrieval problem. For example, I guess not every reader is familiar with the term *hop1* and *hop2* shown in Table 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer WpBp,\n\nThank you for your positive remarks regarding our work. We truly appreciate your support for the direction of classical RANSAC, especially at a time when it isn't the prevailing trend. We concur with your observation that our findings underscore the potential of RANSAC-based methods when combined with novel insights and improvements. Below, we address your queries:\n\nInitial Set: Indeed, the initial set originates from the intermediate phase of the standardized RANSAC process, notably the nearest neighbor with ratio test → SP iteration based on Equation (1) in the manuscript. The initial set can derive either from the ratio test result or the final SP outcome. Our experiments, as depicted in Table 1 in the main body of the paper, compare these two approaches. Notably, we present 'TP with SP' (utilizing the final SP result) and 'TP without SP' (employing the basic ratio test result). The intent was to gauge the impact of SP filtering on the hypothesis set. Interestingly, the integration of SP unexpectedly reduced the final accuracy. A plausible reason might be the incorrect exclusion of numerous prospective positive match pairs by SP.\n\nSaccade Function: Apologies for the oversight in elaboration. Given an initial matching pair (the hypothesis), the saccade function begins its traverse from this pair, covering the entire image region using the Breadth First Search (BFS). Simplistically, imagine it dividing the image into patches similar to the vision transformer. From the initial hypothesis matching patch pair, the saccade function employs BFS across all patches, selecting those that meet the three HR conditions. The actual trajectory is intriguing due to the patch location adjustment phase, resulting in patches of varied sizes and irregular locations compared to transformer's pre-segmented patches.\n\nPatch Location Adjustment: You've hit the mark; it indeed computes the smallest enclosing bounding box of the matched key points.\n\nOn 'Hop 1' and 'Hop 2': We will certainly clarify this in the revised manuscript. To explain them, during image retrieval diffusion or propagation, it's unfeasible to diffuse across the entire database due to computational constraints. As a workaround, we limit the graph and diffuse among, say, the hop 3 neighbors of the query image, optimizing retrieval speed with minimal accuracy compromise. 'Hop 1' and 'Hop 2' denote propagation among hop 1 or hop 2 neighbors for each query, respectively. In our experiments, the hyperparameter was adjusted from hop 3 to hop 2 to curtail offline computational demands. To ensure fairness in comparison, we've included the hop 3 results in the rebuttal PDF. These further emphasize TP's superiority over SP.\n\nOnce again, thank you for your invaluable feedback.\n\nWarm regards,\n\nAuthors\n\n"}, {"review_id": "5m5UJnqb75", "reviewer": "Reviewer_pXos", "summary": "To address the limitations of SPatial verification (SP), the authors introduce the topological consistency to the RANSAC process for image retrieval without fine-tuning. With the socalled homeomorphism regions, the proposed method can achieve better results than some typical methods on four datasets.", "questions": "Please see the weakness.", "limitations": "I think the authors have partly addressed the limitations. However, the speed and computation should be discussed for better future applications.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This work introduces the topological consistency to the RANSAC process. I think it is interesting.\n2. The proposed methods are largely based on existing works. Thus, most of the techniques are correct.\n3. The performance of the proposed methods is better than some typical methods.", "weaknesses": "Some key concerns should be addressed.\n1. Technical contributions\n\nIn fact, the methods of comning RANSAC and topological models are not new in current CV field, especically in image retrieval. I agree with that the SP method has big problems without finetuning sets. However, the authors mainly combines the so-called topological  model and RANSAC. Most of other modules are not new. The defination of HR is common sense. There are no new insights. In my view, this is not a significant contribution, but only a typical combination method for better matching feature representations. Besides, as far as I know, other methods without finetuing can also perform better than the proposed method, such as BLIP, BEiT, ect. The proposed functions in Fig.2 are also naive for HRs. Why them should be that order? There are no full motivation.Thus, the techinical contributions are rather limited, considering most of the used modules are from typical image processing operation. \n\n2. Insufficient experiments\n\nFirst, through the whole experiments, I find that there are no full comparisons with other methods. In fact, the authors only compare with limited methods as shown in Tab.1. As for the methods using SIFT, I suggest to add more comparisions in this aspect. For the pre-trained models, more large-scale models should be added such as BLIP, BEiT, etc. Second, since the title is for image retrieval, I think it is better to perform experiments on different kinds of object retrieval datasets, such as person (Market1501, MSMT2017), Cars (VehicleReID)， Food (Food100k), etc. Third, there are no full analysis on the key modules. For example, how about without using HRs, or just using the visually similar regions? The effects of the proceduce or operation orders in Fig, 2 is missing? As far as I know, there are many different mactching techniques. How about applying the proposed methods in GLUE, SuperGLUE? Is the deep features important in the proposed framework? l think, more experiments will make the proposed method more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer pXos,\n\nThank you for your meticulous feedback. We understand and acknowledge your concerns and have accordingly undertaken additional experiments and provided clearer explanations.\n\n# Main Contribution and Novelty\n\nOur contribution lies in our innovative adaptation of RANSAC. We replace its geometry model with a topological one, rather than a mere fusion. The essence lies in its innate adaptability to any input pair, functioning autonomously, without the necessity of training data.\n\nWhile notable methods such as SuperGlue and R2Former (CVPR 23) utilize topological insights, they do not intrinsically modify RANSAC's architecture. Our method, unlike them, excels without a foundational reliance on prior training data. Referring to Fig.2, it portrays only a single loop iteration in RANSAC, which is variable and not predefined. Page 4 should have clarified this; however, we can provide further elaboration in the discussion stage if required.\n\nPlease note that feedback from other reviewers supports our standpoint:\n\n\"Very interesting\" - JDZk.\n\"Very different than traditional approaches and refreshing\" - X5kj.\n\"Brings many insights and advantages and revitalized the classical algorithms\" - WpBp.\n\n# Scope and Motivation\n\nOur work delves deep into hypothesis-testing processes that function independently of training; this direction is supported by Reviewer WpBp as \"remarkable considering the recent trend of pursuing stronger features through fine-tuning. As discussed in Section 5, it is evident that as humans, we can easily determine if the given image pair is a mismatch without too much contextual information.\" The result that our no-training TP is on par with large-scale refined GeM shows the potential of this direction.\n\nAddressing rigid-body instance retrieval, our findings largely hinge on ROxford and RParis benchmarks. However, based on your insights, we've widened our experimental spectrum to include the geo-localization benchmark MSLS.\n\nThe term \"image retrieval\" in our title aligns with prevailing norms, as many landmark retrieval papers predominantly analyzing Oxford/Paris use such phrasing. Nonetheless, we're open to title revisions to ensure clarity.\n\n# Additional Experiments\n\nResponding to your suggestions, we've taken the following measures (all the result tables are in the rebuttal pdf file):\n\nTable 1 additionally compared our methodology with more techniques such as SIFT-based FisherVector and SMK, and pre-trained alternatives like BLIP and the BEiT series. While BLIP and BEiT's performance might seem unexpectedly subpar, challenges intrinsic to instance retrieval benchmarks like Revisited Oxford/Paris, featuring extreme viewpoints, occlusions, and pattern similarities, could be contributing factors. We've rigorously vetted our BLIP and BEiT implementations, confirming their proficiency in identifying easy cases, but recognizing their limitations in discerning hard positives and negatives.\n\n\nTable 2 assessed our approach's efficacy on the MSLS dataset, an intricate geo-localization benchmark. The results, especially when pitted against the best fine-tuned model R2Former (CVPR23), are telling of our method's prowess. Because we only consider the rigid-body instance retrieval, you mentioned datasets are not in the scope of this paper. (We are open to change the title to avoid misunderstanding) However, the results on the famous ROxford, RParis, and MSLS show that our method has generality on both two representative rigid-body recognition tasks, landmarks retrieval, and geo-localization. \n\nTo further highlight the effectiveness of our proposed HRs, we aligned it with regions established by acclaimed methods such as superpoint+superglue, superpoint + sp, and r2d2 in Table 1, utilizing their pre-existing weightings without fine-tuning on the landmarks in Oxford and Paris. Despite these methods exhibiting strength in tasks like pose estimation and SfM, they couldn't parallel our TP's efficiency. Finally, we would like to humbly mention that our initially selected baselines are the strong and representative methods in the landmark retrieval field; initial feedback from peer reviewers on our experiments has been particularly encouraging:\n\n“The ablation study is a good indication of robustness” - Reviewer JDZk.\n“Very strong results, well-constructed experimental section, apt baselines, and thorough comparisons” - Reviewer X5kj.\n“The benchmarking outcomes are truly exceptional” - Reviewer WpBp.\n\nIn conclusion, your feedback is invaluable, and we genuinely believe our refined explanations and bolstered experimental data should address any lingering concerns.\n\nWarm regards,\n\nAuthors"}, {"review_id": "3VhTNeNQaA", "reviewer": "Reviewer_JDZk", "summary": "This work introduced a new approach of geometrical verification for image retrieval and matching, which is not based on pixel-perfect robust estimation, but on something called \"topological common sense\".  The authors discuss the limitations of the commonly used Spatial Verification strategies, and draw inspiration from how humans compare two images (topological relations vs point level accurate estimation of transformation matrices). Good improvement is shown in ROxf/RPar datasets. ", "questions": "My questions are above in the Weaknesses section, and these are the things I would like to see answered from the authors. ", "limitations": "I did not find that the authors addressed limitations and potential negative societal impact of their work. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- TP is a very interesting idea compare to SP.\n- The biological inspiration for TP is good, and sound. \n- The fact that \"TP without SP (Ours)\" outperforms \"TP with SP (Ours)\", is a good indication of the robustness of the proposed method. \n- The high explainability experiments are interesting and seem technically accurate. ", "weaknesses": "- Why is it claimed that this method offers explainability? To me it seems like the SP methods also offer explainability. Can the authors explain?\n- Why was retrieval only chosen as a proxy task? It seems like TP could be used in other tasks too (e.g. matching, loop closure) which would make this work much more general and thus much stronger. \n- It seems like Hypergraph propagation results are not ideal when using SP. I am wondering if there is any extra loss or consistency regularizer that could be added to SP to make it avoid this. In a sense, is this a fair comparison? Are all pairwise pose estimation consistency losses get into account for the 3 image case? {e.g. L63 RANSAC, SP calculates a transformation matrix M between two views, but is that enforced somehow in the triplet?}", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer JDZk,\n\nThank you for acknowledging the significance of our method and recognizing its merit in terms of its robustness and technical accuracy. We wish to address the concerns you've raised:\n\nExplainability: We'd like to emphasize that we aren't suggesting our method, TP, offers superior explainability in comparison to SP, which is well-regarded for its strong explainability. Instead, our contention is that TP offers improved explainability than other methods that augment SP and often rely heavily on fine-tuning sets and compromising on clarity and transparency. If we were to identify a specific advantage our TP possesses over SP in terms of explainability, it would be its user-friendly reasoning. The HRs generated by TP align more intuitively with human understanding, contrasting with SP's inlier numbers. Without the context provided by the homography matrix, these numbers can sometimes puzzle users in discerning why certain matchings are selected or discarded.\n\nTask Specificity: Our TP is designed to target the rigid-body recognition challenges. The rationale for leveraging retrieval as the proxy task stems from the notorious complexity of datasets like Oxford and Paris. These datasets encompass hard positives and negatives, which while being challenging, have ground truths verifiable by human annotators. As concurred by Reviewer WbBp and discussed in Section 5, the ability of humans to discern these tough cases underscores the importance of our target task. Conversely, other rigid-body benchmarks don't match the complexity of Oxford and Paris or guarantee human recognition. For instance, the geo-localization benchmark MSLS uses images within a 25m radius as ground truth indicators. Regrettably, some pairs lack visual overlap, making human recognition based solely on visual cues unfeasible.\nFurther emphasizing on this, we evaluated our approach against 100 queries from the challenging geo-localization benchmark MSLS val set. As depicted in Table 2 in the rebuttal PDF, our method shows marked improvement over SP with SIFT features. Surprisingly, our TP even rivals the performance of the recent large-scale fine-tuned model R2Former (CVPR 23); it fine-tuned on more than 1.44 million training images in MSLS. This experiment, we believe, reinforces our method's versatility, as we already showed in the submitted paper in page 7 and table 1 w/ GeM fine-tuned on GLD 4 million training set.\n\n\nFairness in Comparison with SP on Hypergraph Propagation: Our commitment to fairness is evident from the consistent use of code, weights, and pre-calculated SP results employed by the hypergraph propagation (HP) research. Given that our parameters mirror those perfected by the HP authors (and remain the best performance in ROxford/RParis benchmarks), it is reasonable to think that the current setting for SP on HP is good and the comparison stands equitable. The sole modification was to change hop 3 to hop2 to reduce computational overhead. We guess your concern about fairness is because the listed performance in our paper is lower than the performance of the HP paper. To address any persisting concerns, we conducted additional tests comparing SP and our TP with propagation set at hop 3 in Table 3 of the rebuttal PDF. We reproduced the reported performance in their paper and our TP outperformed their results, further validating our method's efficacy.\n\nWe hope these clarifications address your concerns, and thank you once again for your constructive feedback.\n\nWarm regards,\n\nAuthors\n\n"}]

Author rebuttal:
Dear Reviewers,

First and foremost, we'd like to thank all the reviewers for the time and effort dedicated to reviewing our work. Your feedback has been instrumental in highlighting areas of improvement, and we've conducted additional experiments in response to your insightful comments.

Additional Experiments:

Table 1 offers a comparison encompassing more SIFT-based methods and those that are pre-trained, providing a broader landscape of performance benchmarks.

In Table 2, we delve into the performance of SP and our TP on the widely-recognized geo-localization benchmark MSLS.

Table 3 elucidates the results when SP and TP are amalgamated with DELG, specifically focusing on the hypergraph propagation among hop 3 neighbors. 

Lastly, Table 4 provides a granular look at the time distribution throughout the retrieval process.

Your detailed feedback has not only enabled us to refine our work but has also guided our direction in conducting these supplementary experiments. We're optimistic that these additions provide a more comprehensive and robust foundation to our research.

Once again, thank you for your invaluable insights. We look forward to any further comments or suggestions you might have.

Warm regards,

Authors

Meta-review: Three reviewers recommended accepts (strong, weak, and borderline), while one reviewer gave a borderline reject. Most of the reviewers appreciated the novelty of the proposed bio-inspired topological verification that replaces traditional spatial verification for image retrieval, as well as solid experimental results, even with hand-crafted SIFT features. There were concerns about missing analyses and comparisons, but the authors successfully addressed most of them in the rebuttal. AC also finds that this paper has a good contribution to the community in the sense that it provides new insight and direction for the standard hypothesis testing process. thus recommending acceptance.
Decision: Accept (poster)