U-Match: Two-view Correspondence Learning with Hierarchy-aware Local Context Aggregation

1 Introduction

Identifying reliable correspondences between two-view images and retrieving the camera motion encoded by the essential matrix, continues to be an important and general problem in computer vision, with applications to Simultaneous Localization and Mapping (SLAM) [Ma et al., 2021], Structurefrom-Motion (SfM) [Schonberger and Frahm, 2016], visual localization [Sattler et al., 2018], image registration and fusion [Tang et al., 2022]. Given a pair of images, the most standard pipeline to address the correspondence learning task follows a three-step strategy, i.e., feature detection, feature description, and feature matching. Specifically, keypoints are first detected from each image and then patches centered at these ones are used to generate corresponding visual descriptors by means of off-the-shelf detector-descriptors [Lowe, 2004; DeTone et al., 2018]. Finally, a Nearest Neighbor (NN) matcher is typically applied to establish point-to-point correspondences between images. Nevertheless, the generated set of putative matches is inevitably largely dominated by false ones (i.e., outliers), as a result of the ambiguity of visual descriptors, especially in the case of extreme situations, including poor texture, repetitive elements, viewpoint change, illumination variation, and motion blur. Therefore, many recent researches have been dedicated to designing accurate and robust correspondence learning methods, with the purpose of rejecting spurious matches while maintaining as many true ones (i.e., inliers) as possible.

∗Corresponding author

As the most prevalent paradigm among hand-engineered techniques for correspondence learning, RANSAC [Fischler and Bolles, 1981] and its variants [Raguram et al., 2012; Barath et al., 2020] seek inliers by finding the largest subset conforming to a task-specific geometric model such as affine, homography, or epipolar geometry. However, the theoretical running time of such methods increases exponentially with respect to the outlier rate. Thus, another line of research explores smoothness constraints to handle this drawback [Ma et al., 2014; Bian et al., 2017; Ma et al., 2019]. Nevertheless, these constraints are tough to uphold in the case of large outlier rates, resulting in dramatically degraded performance.

Due to the astonishing performance achieved by the recent developments in deep learning, end-to-end trainable MultiLayer Perceptrons (MLPs) have been widely applied for twoview correspondence learning to address the irregular and unordered characteristics of sparse matches. Motivated by PointNet [Qi et al., 2017], the pioneering work PointCN [Yi et al., 2018] adopts a PointNet-like architecture to process each correspondence individually and predict the inlier likelihood scores of correspondences. Wherein, a non-parametric operation called Context Normalization is introduced to capture global context, realized by just simply normalizing the distribution of the feature maps with their mean and variance. To mitigating the impact of outliers on Context Normalization, PointACN [Sun et al., 2020] proposes to weigh the importance of each feature map during the normalization step. However, both of them neglect the underlying local geometric relations among tentative correspondences and impeding the correspondence learning performance. To mitigate this downside, a plethora of follow-ups have made notable contributions to the design of delicate local geometric extractors. Particularly, OANet [Zhang et al., 2019] designs a clustering module, which maps correspondences to a set of clusters in a soft assignment manner, for local context capturing. CLNet [Zhao et al., 2021] stacks multiple local-to-global consensus learning layers to progressively reject mismatches, where an annular convolutional operation is introduced to aggregate local features. LMCNet [Liu et al., 2021] presents coherence residual and local coherence layers to model motion coherence property for correspondence learning. MS2DG-Net [Dai et al., 2022] introduces dynamic sparse semantic graphs to capture local topology among correspondences. While these methods demonstrate attractive performance in some generic scenarios, most of them typically extract local context by means of explicit neighborhood relation modeling (e.g., k-nearest neighbors), which is limited and inflexible for the correspondence learning task due to two reasons: 1) putative matches are typically non-uniformly distributed across the image domain, and 2) the number of inliers varies with different scenarios, resulting in that locally consistent geometric cues cannot be fully captured.

In this paper, we propose a simple yet surprisingly effective Attentional Graph Neural Network dubbed U-Match to address the above challenges. Specifically, we present local context pooling (LCPool) and unpooling (LCUnpool) operations to build a UNet-like multi-level architecture (thereby we name our method U-Match), i.e., hierarchy-aware graph representation (HAGR) module, flexibly encoding and decoding high-level features for implicit local context aggregation. The LCPool layer adaptively selects several nodes to form a coarse-grained graph for local context encoding. The LCUnpool layer restores the coarse-grained graph into its original size for local context decoding. Considering that global context is also conducive to correspondence learning and works collaboratively with local context, we further introduce an orthogonal fusion (OF) module to combine complementary local and global context, thus generating redundancy-free compact feature representations. Comprehensive experiments on real-world tasks such as relative pose estimation, homography estimation, and visual localization reveal that our method outperforms long lines of prior work.

To sum up, our main contributions are as follows:

• Instead of explicitly capturing local context as most existing studies have done, we introduce an HAGR module, which has the flexibility to enable implicit local context awareness at multiple levels, thus fully exploring underlying local geometric cues.
• We propose an OF module to integrate complementary local and global context without redundancy.
• We design an attentional graph neural network for twoview correspondence learning, which can remove spurious matches from candidate ones effectively.
• We achieve state-of-the-art results on relative pose estimation, homography estimation, and visual localization.

2 U-Match

We propose a top-performing graph neural network termed as U-Match for two-view correspondence learning. As illustrated in Fig. 1, our network contains: 1) HAGR module that enables implicit local context awareness at multiple levels, and 2) OF module that realizes the complementary of local and global context without redundancy. In the following parts, the general formulation of our problem will be introduced first, followed by detailed description of each module.

2.1 ProblemFormulation

Give an image pair (I, I′ ) depicting the same visual content, the objective of our task is to seek accurate and geometrically consistent correspondences and utilize them to recover the relative camera pose accordingly. To this end, any off-the-shelf detector-descriptors can be first used to detect 2D keypoints and generate their corresponding visual descriptions, either handcrafted methods (e.g., SIFT [Lowe, 2004]) or learning-based ones (e.g., SuperPoint [DeTone et al., 2018]). Then, a group of N initial correspondences C can be generated via an NN matcher:

where ci = (xi, yi, x′i , y′i ) is a correspondence, (xi, yi) and (x′i , y′i ) are coordinates of keypoints in the image pair, both of which are normalized to [-1, 1] with the camera intrinsics.

Following the de facto standard [Yi et al., 2018; Zhang et al., 2019], we formulate the two-view correspondence learning task as an inlier/outlier classification problem and an essential matrix regression problem. An overview of U-Match's workflow is illustrated in Fig. 1. Given the initial correspondences C as input, a shared-weight MLP first processes them to generate C-dimension feature vectors (here we choose C = 128), which are subsequently fed into six HAGR modules and two OF modules, respectively. Then, the features output by the last HAGR module are possessed with an inlier predictor (i.e., a shared-weight MLP followed by tanh and ReLU activation functions), to output the probability set w = [w1,w2, · · · ,wN]⊤ ∈ RN×1 , where wi ∈ [0, 1) indicates the inlier probability of correspondence ci, i.e., wi = 0 represents an outlier. Lastly, the weighted eight-point algorithm [Yi et al., 2018] is leveraged to directly regress the essential matrix ̂E grounded on the probability set w. The whole procedure described above can be summarized as:

where z denotes the logit values used for classification, fφ(·) represents our U-Match with parameters φ, σ(·) consists of tanh and ReLU activation functions, and g(·, ·) denotes the weighted eight-point algorithm that is more robust to outliers than the traditional one, as it has taken into account the inlier confidence of each correspondence, to alleviate the adverse effect of outliers on the regression process.

Next, we discuss the proposed HAGR and OF modules.

2.2 Hierarchy-aware Graph Representation

Due to the variety of data, explicitly aggregating local context has a deficiency in modeling underlying complex local context. Therefore, we propose the HAGR module, to achieve implicit multi-level local context awareness flexibly in an encoder-decoder manner, as shown in Fig. 2(a). The encoder is built by stacking several encoding layers (i.e., LCPool layers), each of which coarsens the graph to encode higher-order local context, as shown in Fig. 2(b). In the decoder part, we stack the same number of decoding layers (i.e., LCUnPool layers), each of which refines the graph into a higher resolution structure to decode fine-grained local context, as shown in Fig. 2(c). Additionally, there are skip-connections between corresponding levels of LCPool and LCUnPool layers, used to conduct encoder-decoder communication.

Local Context Pooling Layer. Given the node features F(ℓ) = {f (ℓ) i }Ni=1 ∈ RN×C at level ℓ input to the LCPool layer, we coarsen the graph with the desire to preserve nodes that can characterize the graph best. For this purpose, we introduce a trainable projection vector p(ℓ) ∈ RC to measure the importance of each node to the graph and a sampling ratio λ(ℓ) ∈ (0, 1] to control the size of the new coarse-grained graph. Specifically, we first calculate the scalar projection value of each node onto p(ℓ) and then adaptively sample a subset of nodes F(ℓ) S as follows:

where ‖ · ‖ denotes L2-norm, top-rank(y, k(ℓ) ) is a function that returns the indices I of the top-k values in the projection score set y, and k(ℓ) = round(λ(ℓ)N) indicates the number of sampled nodes at level ℓ.

After that, these selected nodes F(ℓ) S retrieves information from full nodes F(ℓ) to achieve local context encoding:

where P(·) denotes ResNet block [Zhao et al., 2021] used for pre-processing, ˜y is the gate vector that not only controls information flow but also makes the projection vector p(ℓ) trainable by back-propagation, 1C ∈ RC is a vector with all elements being 1, ⊙ represents Hadamard product, and Cgg(·, ·) denotes the context aggregation layer in light of an attention mechanism [Vaswani et al., 2017]. Concretely, in a C-dimension feature space, there are M vectors, i.e., X ∈ RM×C , to be updated, and N vectors, i.e., Y ∈ RN×C , to be attended to. The attentional aggregation Cgg(·, ·) can be described as:

where Q is linear projection of X, K and V are linear projection of Y. By attentional aggregation, each element in X can retrieve and aggregate context from elements in Y.

By performing the procedures described above, the output F(ℓ+1) have encoded hierarchical local context from F(ℓ) . Notably, for better local context decoding, before feeding F(ℓ+1) into LCUnPool layers, we conduct an intra-graph communication at the coarsest level with a context aggregation layer:

where L is the number of levels and F′ (L) denotes the updated feature nodes input to subsequent LCUnPool layers.

Local Context Unpooling Layer. After the progressive local context encoding with LCPool layers and message exchange between coarsest-level node features via the context aggregation layer, we adopt a straightforward way to implement the LCUnPool layer at level ℓ as follows:

where F′ (ℓ) denotes the decoded node features at the same level of F(ℓ) . As is evident, the favorable and hierarchical local context encoded in F′ (ℓ) is propagated back to all nodes F(ℓ-1) at level ℓ - 1, to achieve local context decoding with compact message passing.

Notably, refer to other learning-based methods [Sun et al., 2020; Zhao et al., 2021], we insert inlier predictors into each HAGR module during the training phase but only preserve the last one at inference.

2.3 Orthogonal Fusion

Given a set of intermediate feature vectors F = {fi}Ni=1 which can be deemed as local features, the global representation vector fg ∈ RC can be simply generated with global average pooling, which however is ill-suited for the correspondence learning task, since it treats each correspondence equally - in other words, it overlooks the negative impact of considerable outliers included in the tentative set, making the global representation vector fg not robust. To tackle this issue, we propose to weigh the importance of each correspondence in light of the probability set (t)w output by the t-th HAGR module, to guide the network to embed more robust global context. To this end, we extend global average pooling to a weighted formulation as follows:

where G(·, ·) is the weighted global average pooling. After obtaining fg, we feed it into a bottleneck with two MLPs whose output channels are 32 and 128, respectively, to generate a global context-enhanced vector fg′ . Then, we calculates the projection fi,proj of each feature vector fi onto the global representation fg′ . Mathematically, the projection can be written as:

As demonstrated in Fig. 3(b), the orthogonal component is the difference between each feature vector fi and its projection vector fi,proj, therefore, we can obtain the component orthogonal to fg′ by:fi,orth = fi - fi,proj. (10)

Afterwards, we append to each fi,orth with fg′ and then the new vector is fed into an MLP whose output channel is 128. By doing so, a compact feature vector, where local and global information is well integrated, is generated. The workflow of our orthogonal fusion module is presented in Fig. 3(a).

2.4 Loss Formulation

Following previous studies [Yi et al., 2018; Zhang et al., 2019], the optimization objective of our network is to minimize a hybrid loss function as follows:

where superscript (t) means the t-th HAGR module, and α balances two loss terms. Lcls(·, ·) denotes a binary cross entropy loss for the classification term:

where N is the number of tentative matches, µi is the perlabel weight to balance positive and negative examples, B represents the binary cross entropy, w is the reasoned probability set, and L = {li}Ni=1 denotes weakly supervised labels which are generated based on the geometric error [Hartley and Zisserman, 2003] with a threshold of 10-4 . Lreg(·, ·) is the regression loss between the estimated essential matrix ̂E and the ground-truth one E, which is also based on the geometric error:

where pi and p′i are two keypoints forming the correspondence ci, and v[i] denotes the i-th element of vector v.

2.5 Implementation Details

In our implementation, the input to our model is N × 4 putative correspondences established by an NN matcher with SIFT detector-descriptors, typically N = 2000, unless otherwise specified. The number of levels is set to L = 4, i.e., each HRGA module contains three LCPool layers with the sampling ratios of 0.125, 0.5, 0.5, respectively. We use 4-head attention in the context aggregation layer. We implement our model with Pytorch and adopt Adam optimizer with a learning rate of 10-4 and a batch size of 32 in optimization. Weight α is set to 0 at the start and to 0.5 after first 20k iterations. All experiments are conducted on Ubuntu 18.04 with GeForce RTX 3090 GPUs.

3 Experiments

In the following sessions, we first evaluate U-Match on three diverse problems which heavily rely on two-view correspondence learning, namely: relative pose estimation, homography estimation, and visual localization. Then, a comprehensive analysis is provided for better understanding U-Match.

3.1 Relative Pose Estimation

Relative pose estimation, which refers to accurately estimate the relative position relationship (i.e., rotation and translation) between different camera views with identified inliers, plays a pivotal role in computer vision.

Datasets. As in the previous work [Zhang et al., 2019], we resort to two popular datasets, YFCC100M [Thomee et al., 2016] and SUN3D [Xiao et al., 2013], to demonstrate the correspondence learning ability of our method in outdoor and indoor scenes, respectively. YFCC100M contains 100 million images from Internet, which are split into 72 sequences according to different tourist spots. We choose 68 sequences as training and validation data, and the remaining sequences are used for testing. SUN3D is a large-scale RGB-D video dataset with relative camera motions retrieved by generalized bundle adjustment. It is comprised of 254 indoor image sequences with poor texture, repetitive elements, and selfocclusions, where 239 sequences are adopted for training and validation, and the rest sequences are used for testing.

Evaluation Protocols. We report the area under the cumulative error curve (AUC) of the pose error at multiple thresholds (5◦ , 10◦ , 20◦ ), where the pose error is the maximum of the angular error in rotation and translation. Importantly, relative poses are recovered by estimating essential matrix with both the weighted eight-point algorithm and RANSAC.

Baselines. We compare U-Match with 1) traditional handcrafted approaches, including the NN matcher, USAC [Raguram et al., 2012], VFC [Ma et al., 2014], LPM [Ma et al., 2019], and GMS [Bian et al., 2017], 2) learning-based ones, including PointCN [Yi et al., 2018], OANet [Zhang et al., 2019], CLNet [Zhao et al., 2021], LMCNet [Liu et al., 2021], and MS2DG-Net [Dai et al., 2022]. To provide a fair evaluation, all learning-based methods are re-trained in the same training setting. Considering that SuperGlue [Sarlin et al., 2020] is the most popular learning-based feature matching method, we also deliver the results of SIFT+SuperGlue on YFCC100M with RANSAC.

Results of Outdoor Pose Estimation. As presented in the first two rows of Fig. 4, several visualization results of outdoor scenes reveal that the proposed U-Match is capable of rejecting spurious correspondences while preserving correct ones effectively. The quantitative results with the weighted eight-point algorithm and RANSAC are reported in Tables 1 and 2, respectively. Clearly, U-Match outperforms other baselines at all error thresholds by a significant margin in both evaluation modes, even surpassing SuperGlue, which requires extra visual descriptors as input, in terms of AUC@5◦ . Surprisingly, U-Match is the first model to pass the 60% AUC@5◦ bar, which without RANSAC even excels all prior models with RANSAC at each threshold. We attribute the top performance to implicit multi-level local context captured in an encoder-decoder manner with the HAGR module. Moreover, the OF module also contributes to the estimation accuracy by integrating complementary local and global context without redundancy.

Results of Indoor Pose Estimation. Compared to outdoor scenes, texture-less scenes of indoor environments are more challenging to relative pose estimation. Even so, visualization shown in the last two rows of Fig. 4 qualitatively demonstrates that U-Match can achieve impressive performance. Further looking at Tables 3 and 4, as with YFCC100M, U-Match consistently achieves the best accuracy at all AUC thresholds, irrespective of using the weighted eight-point algorithm or RANSAC. Intriguingly, U-Match without RANSAC is still more powerful than other baselines with RANSAC according to all metrics.

3.2 Homography Estimation

Homography estimation aims to find a linear image-to-image mapping in the homogeneous space, acting as a crucial prerequisite for a board range of downstream applications. In the following, we evaluate the performance of U-Match with both robust (RANSAC) and non-robust Direct Linear Transform (DLT) estimators on this task.

Dataset. We resort to the HPatches dataset [Balntas et al., 2017] for evaluation, which contains 52 sequences changing largely in viewpoint and 56 sequences varying significantly in illumination conditions. Each consists of one reference image and five query ones, with ground-truth homographies. Importantly, we extract up to 4000 keypoints with SIFT followed by an NN matcher to establish tentative matches.

Evaluation Protocols. Following the corner correctness metric used in [DeTone et al., 2018], we report the percentage of correctly estimated homographies whose average error is below 3/5/10 pixels.

Results. Table 5 presents the all-sided quantitative evaluation on HPatches. Clearly, U-Match achieves best results at all thresholds, no matter with DLT or RANSAC estimators, proving that our method is well-suited for this task.

3.3 Visual Localization

Given a query image, visual localization aims to estimate its 6-DOF camera pose with respect to the corresponding 3D scene model. In the following, we integrate U-Match into the official HLoc [Sarlin et al., 2019] pipeline to investigate how our model directly benefits the visual localization task.

Dataset. We adopt Aachen Day-Night benchmark [Sattler et al., 2018] which contains 4328 reference images from a European old town and 922 (824 daytime, 98 nighttime) query images taken by mobile phone cameras, to validate the effectiveness of our network on visual localization.

Evaluation Protocols. Consistent with the official benchmark, we report the percentage of correctly localized queries at specific distance and orientation thresholds. Importantly, we extract up to 4096 keypoints per image with SIFT, establish putative correspondences with an NN matcher, triangulate an SfM model from day-time images with known poses, and register night-time query images with 2D-2D matches provided by correspondence learning methods and COLMAP [Schonberger and Frahm, 2016].

Results. As summarized in Table 7, the results show that our approach notably performs on par with or better than its competitors in both day and night scenes at all error thresholds, demonstrating its superiority on this task.

3.4 Understanding U-Match

Impact of Graph Representation Levels. Intuitively, the HAGR module with larger levels enables more complex local context awareness. To investigate the impact of graph representation levels, we further train our U-Match on YFCC100M with 2, 3, 5 levels, respectively. As rows 4-7 shown in Table 8, the models with 2 or 3 levels lead to substantially worse results, since underlying hierarchical local context cannot be fully explored with fewer levels. Also, the 5-level model performs on par with the default model (i.e., 4 levels), indicating that too many layers are unnecessary since the unearthed local context might be redundant.

Efficiency. For an HAGR module, let k(1) , k(2) , and k(3) denote the number of sampled nodes at three levels, respectively, the theoretical complexity of the pooling and unpooling operations at three levels and the context aggregation layer at the bottom is O(Nk(1) ), O(k(1)k(2) ), O(k(2)k(3) ), and O(k(3) 2 ), respectively. Since k(1) , k(2) , k(3) ≪ N, the complexity of an HAGR module can be approximately written as O(N). Table 6 summarizes the average runtime of all learning-based methods for correspondence learning on YFCC100M using a single GeForce RTX 3090 GPU with

24GB memory. Clearly, U-Match achieves comparable efficiency regardless of using the weighted eight-point algorithm or RANSAC. In contrast, LMCNet is time-consuming, whose average runtime without RANSAC is an order of magnitude larger than others due to the calculation of smooth motions via the coherence residual layer. CLNet with RANSAC runs the fastest since it just employs identified inliers from the pruned candidates to estimate the essential matrix.

Generalization Ability. To investigate the generalization ability of U-Match to different combinations of datasets and detector-descriptors, we test all learning-based counterparts on YFCC100M with RootSIFT or SuperPoint, as well as SUN3D with SIFT, RootSIFT or SuperPoint, adopting the models only trained on YFCC100M with SIFT. Notably, we extract up to 2000 and 1000 keypoints per image with RootSIFT and SuperPoint, respectively, followed by an NN matcher to generate putative matches. As reported in Table 9, U-Match substantially outperforms prior state-of-the-arts in all cases, directly reflecting its superior generalization ability.

Ablation Study. In the OF module, we propose to decompose a local feature into two parts, namely fi,proj and fi,orth, where the former is parallel to the global feature fg′ and the latter is orthogonal to fg′ . To demonstrate that such operation is a better choice, we replace the orthogonal decomposition step with concatenation and Hadamard product, respectively,

1st Sampling

2nd Sampling

3rd Sampling

Figure 5: Visualization of sampled nodes by three LCPool layers.

which are commonly used to fuse two feature vectors. As rows 1, 2 and 7 reported in Table 8, the proposed orthogonal fusion achieves the best performance among three fusion strategies, since by doing so, there is no information redundancy in the output local feature fi,orth. In addition, row 3 verifies the effectiveness of the propose OF module to combine complementary local and global context.

Visualization of Sampled Nodes. We visualize the sampled correspondences at three levels, as shown in Fig. 5. U-Match is capable of progressively discovering reliable matches as message bottlenecks, to achieve accurate and robust local context encoding, as evidenced by the gradually increasing inlier ratio of sampled nodes.

4 Conclusion

This paper introduces U-Match for two-view correspondence learning. The main improvement is from two sides: 1) We propose an efficient network structure in an encoder-decoder manner, implicitly capturing the local context from different levels and can be trained integrally. 2) We design an orthogonal fusion module that combines complementary local and global context without redundancy. Experiments on different tasks and datasets show that U-Match brings significant improvement over the state-of-the-art methods.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (62276192), and the Key Research and Development Program of Hubei Province (2020BAB113).

Contribution Statement

Zizhuo Li and Shihua Zhang contributed equally to this work.