# Learning Feature Matching via Matchable Keypoint-Assisted Graph Neural
Network

Zizhuo Li and Jiayi Ma, _Senior Member, IEEE_

###### Abstract

Accurately matching local features between a pair of images corresponding to
the same 3D scene is a challenging computer vision task. Previous studies
typically utilize attention-based graph neural networks (GNNs) with fully-
connected graphs over keypoints within/across images for visual and geometric
information reasoning. However, in the context of feature matching, a
significant number of keypoints are non-repeatable due to occlusion and
failure of the detector, and thus irrelevant for message passing. The
connectivity with non-repeatable keypoints not only introduces redundancy,
resulting in limited efficiency (quadratic computational complexity _w.r.t._
the keypoint number), but also interferes with the representation aggregation
process, leading to limited accuracy. Targeting towards high accuracy and
efficiency, we propose MaKeGNN, a sparse attention-based GNN architecture
which bypasses non-repeatable keypoints and leverages matchable ones to guide
compact and meaningful message passing. More specifically, our _Bilateral
Context-Aware Sampling_ (BCAS) _Module_ first dynamically samples two small
sets of well-distributed keypoints with high matchability scores from the
image pair. Then, our _Matchable Keypoint-Assisted Context Aggregation_
(MKACA) _Module_ regards sampled informative keypoints as message bottlenecks
and thus constrains each keypoint only to retrieve favorable contextual
information from intra- and inter- matchable keypoints, evading the
interference of irrelevant and redundant connectivity with non-repeatable
ones. Furthermore, considering the potential noise in initial keypoints and
sampled matchable ones, the MKACA module adopts a matchability-guided
attentional aggregation operation for purer data-dependent context
propagation. By these means, we achieve the state-of-the-art performance on
relative camera estimation, fundamental matrix estimation, and visual
localization, while significantly reducing computational and memory complexity
compared to typical attentional GNNs.

###### Index Terms:

Feature matching, graph neural network, matchability, message passing.

##  I Introduction

Feature matching which refers to establishing reliable correspondences between
images depicting the same visual content, continues to be a cornerstone for a
board range of downstream vision applications [1], such as Simultaneous
Localization and Mapping (SLAM) [2], Structure-from-Motion (SfM) [3], visual
localization [4], and image fusion [5]. Given a pair of images, the most
standard pipeline starts with detecting keypoints and constructing local
descriptors, so that point-to-point correspondences can be generated by
searching the nearest neighbor (NN) in line with the similarity of feature
descriptors. However, due to visual ambiguity caused by poor texture,
repetitive elements, viewpoint change, illumination variation, and motion
blur, the matches given by an NN matcher are inevitably dominated by false
ones (_i.e._ , outliers), resulting in unpromising accuracy [6, 7]. To
alleviate this issue, a crowd of approaches recently focus on designing
learnable outlier rejection strategies [8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18] to filter spurious matches from candidate ones. Specifically, most of them
adopt a PointNet-like [19] architecture, _i.e._ , multi-layer perceptrons
(MLPs), to process each correspondence individually and infer the probability
of correspondences to be correct ones (_i.e._ , inliers). Despite the
inspiring progress, these methods are inherently limited by the following two
aspects: 1) Their inputs are putative correspondences provided by an NN
search, so it is impossible to retrieve correct matches beyond these ones,
which means that the upper bound on the performance is limited by the quality
of initial matches; 2) Local visual descriptors and correspondence coordinates
are separately used for match generation and mismatch rejection, respectively,
neglecting the interaction between visual information from high-level image
representation and geometric information from 2D keypoint distribution,
calling for the research towards the design of effective feature matching
methods to break the limitation of vanilla nearest neighbor correspondences.
To this end, a line of research directly learns to find the partial assignment
between two sets of local features with an attention-based Graph Neural
Network (GNN) [20, 21]. Representatively, SuperGlue [6] constructs densely-
connected graphs over intra- and inter-image keypoints and performs message
passing by means of self- and cross-attention. Since SuperGlue encodes both
spatial relationships of keypoints and their associated visual appearance, it
essentially produces more discriminative representations for feature matching.
However, the remarkable performance of SuperGlue comes with high computational
complexity of $\mathcal{O}(N^{2})$ for matrix multiplications and memory
occupation of $\mathcal{O}(N^{2})$ to save the attention weights, where $N$
denotes the number of nodes, substantially degrading its efficiency in real-
time applications and making it unsuitable for mobile deployment.
Additionally, a large number of detected keypoints are non-repeatable and thus
do not have correspondences in the other image (about 70% of 2$k$ keypoints in
YFCC100M dataset [22]) due to occlusion, viewpoint change, and failure of the
detector, _etc._ , which often occur in feature matching. This means that such
fully-connected graphs actually introduce too many redundant and meaningless
connections, which to some degree limit the networks’ capability for fine-
grained feature update. To mitigate these downsides, a plethora of follow-ups,
such as SGMNet [23] and ClusterGNN [24], have made notable contributions to
the design of more efficient and compact context aggregation operations by
relaxing densely-connected graphs into sparsely-connected ones, but they are
significantly less accurate. In particular, SGMNet initially generates a set
of seed matches using an NN matcher, which are unfortunately contaminated by
heavy outliers, making the aggregated information not pure. Although a
weighted attentional aggregation is further introduced to alleviate this
problem, it subsequently results in massive loss of contextual cues during the
unpooling process. Also, ClusterGNN conducts cluster-wise matching using a
learnable coarse-to-fine paradigm. However, the generated clusters lack clear
geometric meanings, and the clustering process does not exclude non-repeatable
keypoints.

In the context of feature matching, a keypoint aggregates contextual
information from nodes connected to it through an attentional GNN. However, as
stated above, the connectivity with non-repeatable keypoints is unnecessary
and distracting, which not only reduces efficiency but also degrades accuracy.
_Thus, it is natural to ask that: can a keypoint only exchange messages with
repeatable and informative keypoints (matchable keypoints 111A keypoint that
exists in co-visible areas and has a correspondence in the other image, is
considered matchable. Matchable keypoints can provide fruitful geometric and
visual cues, which are of great benefit for feature matching.) to achieve
fine-grained feature update?_

Following this train of thought, we propose a Matchable Keypoint-Assisted
Graph Neural Network (MaKeGNN) that accounts for both accuracy and efficiency
to learning feature matching. First, we introduce a _Bilateral Context-Aware
Sampling_ (BCAS) _Module_ to dynamically sample two set of well-distributed
matchable keypoints from a pair of images, as shown in Figs. 1 and 2. Second,
we design a _Matchable Keypoint-Assisted Context Aggregation_ (MKACA) _Module_
whose graph structure is greatly sparse to achieve efficient and effective
message passing. In particular, rather than conducting communication with all
features within and across images, the MKACA module considers the selected
matchable keypoints as bottlenecks and constrains each keypoint only attend to
intra- and inter- matchable ones, avoiding the interference of irrelevant
connections, relieving the computational burden, and retrieving compact and
fine-grained context. Meanwhile, we notice that the potential noise in initial
keypoints and sampled matchable ones may lead to impure information broadcast
and thus integrate a matchability-guided attentional aggregation mechanism
into the MKACA module for cleaner and sharper data-dependent message
propagation. Importantly, with the proposed BCAS and MKACA modules, the
computational complexity of attention is significantly reduced from
$\mathcal{O}(N^{2})$ to $\mathcal{O}(N\textit{k})$, where k is the number of
sampled matchable keypoints from each image. Comprehensive experiments on
multiple visual tasks such as relative camera estimation, fundamental matrix
estimation and visual localization reveal that our method outperforms long
lines of prior work.

We summarize our contributions as follows:

  * •

We propose a _Bilateral Context-Aware Sampling_ (BCAS) _Module_ , which
enables the model to dynamically select well-distributed keypoints with high
matchability scores, to guide compact and robust context aggregation.

  * •

We introduce a _Matchable Keypoint-Assisted Context Aggregation_ (MKACA)
_Module_ for message passing. Instead of constructing fully-connected graphs,
we leverage the sampled informative keypoints as bottlenecks, so that each
keypoint only communicates with intra- and inter- matchable ones to update
per-keypoint feature elegantly, which not only increases efficiency but also
accuracy.

  * •

Our MakeGNN shows superior performance over the state-of-the-arts on relative
camera estimation, fundamental matrix estimation, and visual localization.

##  II Previous Arts

###  II-A Local Feature Matching

Matching local features between a pair of images is key to various
applications including relative pose estimation and visual localization.
Traditionally, keypoints are first detected from each image and then patches
centered at these ones are used to generate corresponding visual descriptors
with hand-crafted methods such as SIFT [25] and ORB [26]. Finally, an NN
matcher and its variants, _e.g._ , mutual nearest neighbor (MNN) check and
ratio test (RT) [25] are used to establish correspondences between two sets of
keypoints. With the advent of the deep learning era, the robustness of local
features under illumination variation and viewpoint change can be
significantly improved by learning-based methods, such as SuperPoint [27],
D2-Net [28], R2D2 [29], and AWDesc [30]. In addition to learning-based
detector-descriptors, some works recently focus on learning local feature
matching [6, 23, 20, 24, 21, 31]. As a pioneering work, SuperGlue [6] requires
two sets of keypoints and their visual descriptors as input and learns their
correspondences using an attentional GNN with complete graphs over keypoints
within and across images. Albeit the impressive performance, the computational
and memory complexity of SuperGlue is quadratic to the number of keypoints,
severely limiting its practicality to real-time or large-scale visual tasks.
Some follow-ups try to address this problem by relaxing densely-connected
graphs into sparsely-connected ones. Particularly, SGMNet [23] which draws
inspiration from guided matching methods [32] and graph pooling operations
[33], first generates a set of correspondences as seeds using an NN matcher,
and then adopts a seeded GNN to perform message passing. Besides, ClusterGNN
[24] adopts a learnable hierarchical clustering strategy to partition
keypoints into different sub-graphs, and then performs message passing merely
within these sub-graphs. In spite of improving the efficiency, both of them
suffer from significant accuracy loss, as analyzed in Sec. I.

###  II-B Efficient Attention

Transformer [34] architectures have received extensive interest during the
past few years. Particularly, in the context of attentional GNNs, Transformer
serves as a graph-like model for broadcasting information across nodes in
fully-connected graphs [35]. In spite of its remarkable performance on a
plethora of visual tasks [36, 37, 38, 39], the major drawback of Transformer
is the quadratic complexity of the attention mechanism _w.r.t._ the input
size, significantly hampering its application to large-scale tasks.

In recent years, many works have spent great efforts to tackle the efficiency
problem of attention mechanism. Specifically, they reduce computational
complexity by the learning of partitioning or grouping on input elements [40,
41], linear projection functions [42, 43], or attention sharing [44], to name
just a few. Please refer to a comprehensive survey [45] for more details.
Despite showing promising efficiency, such works typically concentrate on
self-attention, where both queries and keys come from the same set of
elements, and thus cannot be generalized well to the feature matching problem,
which requires cross-attention to conduct cross-image communication.

Figure 1: The network architecture of MaKeGNN, which consists of four
components. The initialization Context Aggregation (ICA) module (Sec. III-B)
first performs coarse intra- and inter-graph message passing. Then the BCAS
module (Sec. III-C) and MKACA module (Sec. III-D) reason about visual
appearance similarity, neighborhood consensus, as well as the guidance
provided by well-distributed matchable keypoint in the image pair jointly, to
update per-node feature in a compact and robust manner. Finally, the optimal
matching (OM) module (Sec. III-E) utilizes Sinkhorn algorithm to derive the
assignment matrix.

###  II-C Outlier Rejection

Among traditional methods, RANSAC and its variants [46, 47, 48, 49] are still
the most popular outlier rejection methods. However, their major drawbacks are
slow convergence and low accuracy in the case of high outlier rates. Due to
the impressive performance achieved by the recent developments in deep
learning, learning-based outlier rejection methods receive a continuous influx
of attention. PointCN [8] introduces Context Normalization to capture global
contextual information. PointACN [10] further improves the robustness of
Context Normalization by weighing the importance of each feature map during
the normalization step. OANet [9] maps matches to a set of clusters in a soft
assignment manner, for local context exploring. CLNet [11] adopts a local-to-
global consensus learning strategy to filter outliers progressively. LMCNet
[12] and ConvMatch [15] learn the coherence and smoothness of the motion filed
for outlier rejection. MS2DG-Net [13] injects semantic information into a GNN
to extract local context. U-Match [16] employs an encoder-decoder
architecture, implicitly capturing the local context from different levels.
However, these methods reason about visual appearance and geometric
distribution separately and their performance strongly relies on the quality
of candidate matches. Instead, our method can jointly process them and predict
reliable correspondences end-to-end.

##  III Methodology

We present Matchable Keypoint-Assisted Graph Neural Network, shorten as
MaKeGNN, for learning reliable correspondences between two sets of keypoints
with their corresponding visual descriptors. As illustrated in Fig. 1, the
core modules of our framework are 1) _Bilateral Context-Aware Sampling_ (BCAS)
_Module_ that dynamically samples two sets of well-distributed matchable
keypoints from the image pair to guide the context aggregation process, and 2)
_Matchable Keypoint-Assisted Context Aggregation_ (MKACA) _Module_ that
considers sampled informative keypoints as attention bottlenecks for per-
keypoint fine-grained feature update. In the following parts, we first present
an overview of our network architecture, and then describe each module in
detail.

###  III-A Overview

We assume that a pair of images $\mathbf{A}$ and $\mathbf{B}$ depicting the
same 3D structure have $M$ and $N$ keypoints and associated visual
descriptors, respectively, which are indexed by $\alpha:=\\{1,\dots,M\\}$,
$\beta:=\\{1,\dots,N\\}$, and extracted by off-the-shelf handcrafted features
(_e.g._ , SIFT [25] and ORB [26]) or learned ones (_e.g._ , SuperPoint [27]
and R2D2 [29]). The goal of our task is to establish geometrically consistent
point-to-point correspondences between two images.

Following the _de facto_ standard [6, 23], we formulate the feature matching
task as a graph matching problem, where nodes are extracted keypoints from
each image. Instead of employing an attentional GNN with complete graphs, we
consider that matchable keypoints with the favorable property of being located
in co-visible regions and having a true match in the other image can provide
valuable matching priors. Thus we can dynamically sample two sets of well-
distributed matchable keypoints from two images as message bottlenecks to
guide the compact and robust context propagation across nodes in two graphs
for subsequent matching. As we will show, this crucial difference increases
not only accuracy but also efficiency.

An overview of MaKeGNN’s workflow is illustrated in Fig. 1. Given two sets of
local features $\\{\mathbf{K}_{\mathbf{A}}^{i}\\}_{i=1}^{M}$ and
$\\{\mathbf{K}_{\mathbf{B}}^{i}\\}_{i=1}^{N}$ as input,
$\mathbf{K}_{\mathbf{I}}^{i}=(\mathbf{p}_{\mathbf{I}}^{i},\mathbf{d}_{\mathbf{I}}^{i})$,
where $\mathbf{I}\in\\{\mathbf{A},\mathbf{B}\\}$,
$\mathbf{p}_{\mathbf{I}}^{i}=(x_{\mathbf{I}}^{i},y_{\mathbf{I}}^{i})\in\mathbb{R}^{2}$
is the image coordinate of keypoint $i$ in image $\mathbf{I}$, and
$\mathbf{d}_{\mathbf{I}}^{i}\in\mathbb{R}^{D}$ a $D$ dimensional visual
descriptor associated with keypoint $i$ in image $\mathbf{I}$, a position
encoder first possesses them to obtain the initial representation vectors
${}^{(0)}\mathbf{F}^{i}_{\mathbf{A}}$ and
${}^{(0)}\mathbf{F}^{i}_{\mathbf{B}}$ by combining the visual appearance and
location as [6, 23, 24]:

$^{(0)}\mathbf{F}^{i}_{\mathbf{I}}=\mathbf{d}_{\mathbf{I}}^{i}+f_{enc}(\mathbf{p}_{\mathbf{I}}^{i}),\;\mathbf{I}\in\\{\mathbf{A},\mathbf{B}\\},$
(1)

where $f_{enc}(\cdot)$ encodes the position of each keypoint into a high
dimensional feature vector using an MLP. Then, $L_{1}$ _Initialization Context
Aggregation_ (ICA) _Modules_ are stacked sequentially to perform coarse
message passing, enabling each feature to roughly perceive intra- and inter-
image contextual information. Subsequently, BCAS and MKACA modules that reason
about visual appearance similarity, neighborhood consensus, as well as the
guidance provided by well-distributed matchable keypoints in the image pair
jointly, are stacked alternately $L_{2}$ times to achieve fine-grained feature
update progressively. Finally, reliable correspondence are established by an
_Optimal Matching_ (OM) _Module_ which formulates the assignment matrix using
the Sinkhorn algorithm [50].

Next, we will provide the detailed description of our MakeGNN.

###  III-B Initialization Context Aggregation Module

Sampling two sets of well-distributed matchable keypoints from the image pair
lays the foundation for subsequently compact and efficient message passing.
However, it is impossible to directly predict the matchability score of each
keypoint for sampling in light of the initial feature vectors
${}^{(0)}\mathbf{F}^{i}_{\mathbf{A}}$ and
${}^{(0)}\mathbf{F}^{i}_{\mathbf{B}}$, since they only encode intra-image
geometric and visual cues and do not perceive inter-image ones. To this end,
we introduce an ICA module, which enables the representation vector of each
keypoint to roughly perceive intra- and inter-image contextual information.
Specifically, similarly to [6, 24], the ICA module constructs complete graphs
over keypoints within and across images, and lets them communicate with each
other to retrieve coarse intra- and inter-image context for per-node feature
update based on an attentional GNN [51]. This realizes the attentional
aggregation using the standard attention mechanism [34] combined with the
feed-forward network (FFN) and shortcut connection. In particular, in a
$D$-dimensional feature space, there are $M$ vectors, _i.e._ ,
$\mathbf{X}\in\mathbb{R}^{M\times D}$, to be updated, $N$ vectors, _i.e._ ,
$\mathbf{Y}\in\mathbb{R}^{N\times D}$, to be attended to, and an optional
weight vector $\mathbf{w}\in\mathbb{R}^{N}$, to adjust the importance of each
element in $\mathbf{Y}$. The attentional aggregation operation
$\mathcal{G}(\cdot,\cdot,\cdot)$ is defined as:

$\mathcal{G}(\mathbf{X},\mathbf{Y},\mathbf{w})=\mathbf{X}+\text{FFN}(\mathbf{X}||\mathcal{A}(\mathbf{X},\mathbf{Y},\mathbf{w})),$
(2)

where

$\mathcal{A}(\mathbf{X},\mathbf{Y},\mathbf{w})=\theta(\mathbf{Q}\mathbf{K}^{\top})\mathbf{W}\mathbf{V},\mathbf{W}=\text{Diag}(\mathbf{w}),\mathbf{W}\in\mathbb{R}^{N\times
N},$ (3)

$||$ means concatenation along row dimension, $\theta(\cdot)$ means Softmax
operation, $\mathbf{Q}$ is linear projection of $\mathbf{X}$, and
$\mathbf{K}$, $\mathbf{V}$ are linear projections of $\mathbf{Y}$.

Based on this definition, the initialization context aggregation process of
ICA module in layer $\ell$ can be described as:

$\displaystyle^{(\ell-1)}\mathbf{F}^{1}_{\mathbf{I}}=\mathcal{G}(^{(\ell-1)}\mathbf{F}_{\mathbf{I}},^{(\ell-1)}\mathbf{F}_{\mathbf{I}},\mathbf{1}),$
${}^{(\ell)}\mathbf{F}_{\mathbf{I}}=\mathcal{G}(^{(\ell-1)}\mathbf{F}^{1}_{\mathbf{I}},^{(\ell-1)}\mathbf{F}^{1}_{\mathbf{J}},\mathbf{1}),\;\mathbf{I},\mathbf{J}\in\\{\mathbf{A},\mathbf{B}\\},\mathbf{I}\neq\mathbf{J},$
(4)

where $\mathbf{1}$ is an all-one vector, meaning that no weights are used in
the aggregation process.

After being processed by several ICA modules, the updated feature vectors
encode both the coarse visual and geometric context of each graph, and are fed
into subsequent operations, _i.e._ , BCAS and MKACA modules, for compact
message passing and robust matching.

###  III-C Bilateral Context-Aware Sampling Module

As analyzed above, in the context of feature matching, there are a significant
number of non-repeatable keypoints in the image pair due to occlusion and
failure of the detector. Consequently, employing densely-connected graphs not
only has no contributions to feature matching, but also introduces excessive
redundant and pointless information interaction, which may impair the
network’s representation capability. To mitigate these problems, considering
that matchable keypoints which are located in co-visible regions and have true
matches in the other image, can provide valuable matching priors, we propose a
sampling module that is capable of selecting well-distributed keypoints with
high matchability scores dynamically, to guide the network for compact and
meaningful message. Specifically, the proposed BCAS module consists of two
procedures: matchability score prediction and matchable keypoint sampling, as
presented in Fig. 2.

Figure 2: Bilateral context-aware sampling module.

####  III-C1 Matchability Score Prediction

In the first stage, instead of relying solely on the feature of each keypoint
for prediction, we also consider additional geometric information from both
two images $\mathbf{A}$ and $\mathbf{B}$ to enhance the bilateral context
awareness of per-keypoint feature, rendering the inferred matchability scores
more reliable. In particular, given two sets of intermediate features
${}^{(\ell-1)}\mathbf{F}_{\mathbf{A}}$ and
${}^{(\ell-1)}\mathbf{F}_{\mathbf{B}}$, we could first generate the global
representation vectors ${}^{(\ell-1)}\mathbf{f}_{\mathbf{A}}^{g}$,
${}^{(\ell-1)}\mathbf{f}_{\mathbf{B}}^{g}\in\mathbb{R}^{D}$ with a simple
average pooling operation, which however is ill-suited for the feature
matching task, since it overlooks the negative impact of a large portion of
non-repeatable keypoints, making ${}^{(\ell-1)}\mathbf{f}_{\mathbf{A}}^{g}$
and ${}^{(\ell-1)}\mathbf{f}_{\mathbf{B}}^{g}$ not robust. To tackle this
issue, we propose to weigh the importance of each keypoint based on the
matchability scores
${}^{(\ell-1)}\boldsymbol{{\gamma}}_{\mathbf{A}}\in\mathbb{R}^{M}$ and
${}^{(\ell-1)}\boldsymbol{{\gamma}}_{\mathbf{B}}\in\mathbb{R}^{N}$ which are
generated by the previous stage and elaborated later on, guiding the network
to embed more robust global context. Following this train of thought, we
extend average pooling to a weighted formulation as follows:

$^{(\ell-1)}\mathbf{f}_{\mathbf{I}}^{g}=\textstyle{\sum_{i}}\theta(^{(\ell-1)}\boldsymbol{{\gamma}}_{\mathbf{I}})^{i}\cdot{{}^{(\ell-1)}\mathbf{F}_{\mathbf{I}}^{i}},\;\mathbf{I},\mathbf{J}\in\\{\mathbf{A},\mathbf{B}\\},$
(5)

where $\theta$ means Softmax operation. Importantly, both
${}^{(L_{1})}\boldsymbol{{\gamma}}_{\mathbf{A}}\in\mathbb{R}^{M}$ and
${}^{(L_{1})}\boldsymbol{{\gamma}}_{\mathbf{B}}\in\mathbb{R}^{N}$ are all-one
vectors. After obtaining ${}^{(\ell-1)}\mathbf{f}_{\mathbf{A}}^{g}$ and
${}^{(\ell-1)}\mathbf{f}_{\mathbf{B}}^{g}$, we concatenate them with per-
keypoint feature accordingly, followed by a Context Normalization (CN) [8]
branch as the predictor to fuse the above hybrid features and predict new
matchability scores ${}^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{I}}$ for each
keypoint in image $\mathbf{I}\in\\{\mathbf{A},\mathbf{B}\\}$, which will be
used to the select matchable keypoints in the later sampling stage. The
prediction process can be summarized as follows:

$^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{I}}^{i}=\phi(^{(\ell-1)}\mathbf{F}^{i}_{\mathbf{I}}||^{(\ell-1)}\mathbf{f}_{\mathbf{I}}^{g}||^{(\ell-1)}\mathbf{f}_{\mathbf{J}}^{g}),\;\mathbf{I},\mathbf{J}\in\\{\mathbf{A},\mathbf{B}\\},\mathbf{I}\neq\mathbf{J},$
(6)

where $\phi(\cdot)$ (_i.e._ , matchability predictor) is comprised of
lightweight stacked CN [8] blocks, whose detailed structure is reported in
Fig. 3. The input/output channel numbers of five MLPs are 3$D$/3$D$, 3$D$/$D$,
$D$/$D$, $D$/1, 3$D$/1, respectively, where $D$ denotes the dimension of
initial visual descriptors.

Figure 3: The structure of CN block and matchability predictor.

####  III-C2 Matchable Keypoint Sampling

In the second stage, keypoints in each image with top-k matchability scores
are sampled as candidates, to provide guidance for message passing. Also, we
employ a simple yet effective Non-Maximum Suppression (NMS) post-process to
ensure a better spatial distribution of selected keypoints. The NMS’s radius
for image $\mathbf{A}$ is
$\frac{\sigma}{|\alpha|(|\alpha|-1)}\sum\limits_{(i,j)\in\alpha\times\alpha,i\neq
j}d^{ij}_{\mathbf{A}}$, where $\alpha$ is the index list for all keypoints in
image $\mathbf{A}$, $d^{ij}_{\mathbf{A}}$ is the distance between keypoint $i$
and $j$ in image $\mathbf{A}$, $|\cdot|$ denotes the cardinality of a set, and
$\sigma$ controls the radius, which is set to $5\times 10^{-2}$ for all
experiments.

The BCAS module at the $\ell$-th layer outputs
${}^{(\ell)}\boldsymbol{{\gamma}}=(^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{A}},^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{B}})$,
where ${}^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{A}}\in[0,1]^{M}$ and
${}^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{B}}\in[0,1]^{N}$ are matchability
score sets for keypoints in each image, and
${}^{(\ell)}\mathbf{M}=(^{(\ell)}\mathbf{M}_{\mathbf{A}},^{(\ell)}\mathbf{M}_{\mathbf{B}})$,
where ${}^{(\ell)}\mathbf{M}_{\mathbf{A}}$ and
${}^{(\ell)}\mathbf{M}_{\mathbf{B}}$ are index lists for well-distributed
matchable keypoints in each image.

###  III-D Matchable Keypoint-Assisted Context Aggregation Module

As discussed above, the MKACA module utilizes selected well-distributed
matchable keypoints as attention bottlenecks, so that each keypoint only
exchanges messages with intra- and inter- bottlenecks for compact and robust
context aggregation. To this end, we adopt an infusion-enhancement-
broadcasting strategy in each MKACA module, fleshed out by the following three
operations.

####  III-D1 Guided Global Context Infusion

Assuming that the MKACA module in layer $\ell$ 222It should be mentioned that
the proposed BCAS and MKACA modules are inseparable. Therefore, we group a
BCAS module followed by an MKACA module into the same GNN layer and regard
them as a processing unit. takes features
${}^{(\ell-1)}\mathbf{F}_{\mathbf{A}}$ and
${}^{(\ell-1)}\mathbf{F}_{\mathbf{B}}$ with index sets
${}^{(\ell)}\mathbf{M}=(^{(\ell)}\mathbf{M}_{\mathbf{A}},^{(\ell)}\mathbf{M}_{\mathbf{B}})$
as input, the features for matchable keypoints, _i.e._ ,
${}_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{A}}$,
${}_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{B}}\in\mathbb{R}^{\textit{k}\times
D}$, are first retrieved by ${}^{(\ell)}\mathbf{M}$:

$_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{I}}=^{(\ell-1)}\mathbf{F}_{\mathbf{I}}[^{(\ell)}\mathbf{M}_{\mathbf{I}}],\;\mathbf{I},\mathbf{J}\in\\{\mathbf{A},\mathbf{B}\\},$
(7)

where $[\cdot]$ denotes the indexing operation. Then, we infuse contextual
information from every keypoint in each graph into intra-matchable ones
through a matchabilty score-guided attentional aggreagtion, which enables
valuable matching priors to guide the gathering process, suppressing
interference of considerable non-repeatable keypoints caused by occlusion and
failure of the detector, contributing to the robustness of our network to the
potential noise in initial keypoints, and resulting in cleaner and sharper
per-node feature update:

$_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{I}}^{1}=\mathcal{G}(_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{I}},^{(\ell-1)}\mathbf{F}_{\mathbf{I}},^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{I}}),\;\mathbf{I},\mathbf{J}\in\\{\mathbf{A},\mathbf{B}\\}.$
(8)

By doing so, the updated features
${}_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{A}}^{1}$ and
${}_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{B}}^{1}$ encode both visual and
geometric context from their respective corresponding graphs.

####  III-D2 Global Context Refinement

To further enhance the encoded global context, we propose to conduct intra-
graph information interaction among well-distributed matchable keypoints. More
specifically, the intra-graph attentional aggregation is applied to the
features of matchable keypoints
${}_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{I}}^{1}$ for global context
refinement:

$_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{I}}^{2}=\mathcal{G}(_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{I}}^{1},_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{I}}^{1},\mathbf{1}),\;\mathbf{I},\mathbf{J}\in\\{\mathbf{A},\mathbf{B}\\},$
(9)

where ${}_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{A}}^{2}$ and
${}_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{B}}^{2}$ are the features of
matchable keypoints with enhanced global context.

####  III-D3 Guided Global Context Back-broadcasting

After the intra-graph message interaction among matchable keypoints, every
keypoint on each side retrieves fine-grained global context from both intra-
matchable and inter-matchable keypoints through a matchabilty score-guided
attentional aggreagtion:

$\displaystyle^{(\ell-1)}\mathbf{F}^{1}_{\mathbf{I}}=\mathcal{G}(^{(\ell-1)}\mathbf{F}_{\mathbf{I}},_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{I}}^{2},_{\mathbf{M}}^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{I}}),$
${}^{(\ell)}\mathbf{F}_{\mathbf{I}}\\!=\\!\mathcal{G}(^{(\ell-1)}\mathbf{F}^{1}_{\mathbf{I}},_{\mathbf{M}}^{(\ell)}\mathbf{F}_{\mathbf{J}}^{2},_{\mathbf{M}}^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{J}}),\;\mathbf{I},\mathbf{J}\in\\{\mathbf{A},\mathbf{B}\\},\mathbf{I}\\!\neq\\!\mathbf{J},$
(10)

where
${}_{\mathbf{M}}^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{I}}=^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{I}}[^{(\ell)}\mathbf{M}_{\mathbf{I}}]$.

It should be mentioned that leveraging the matchabilty scores
${}_{\mathbf{M}}^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{A}}$ and
${}_{\mathbf{M}}^{(\ell)}\boldsymbol{{\gamma}}_{\mathbf{B}}$ into the
backpropagation process can suppress adverse message passing from mis-sampled
matchable keypoints, ensuring the robustness of our network to the potential
noise in bottlenecks.

The MKACA module at the $\ell$-th layer outputs the updated keypoint features
${}^{(\ell)}\mathbf{F}_{\mathbf{A}}$ and ${}^{(\ell)}\mathbf{F}_{\mathbf{B}}$
with favorable visual and geometric context from both images $\mathbf{A}$ and
$\mathbf{B}$, conducive to subsequent matching.

###  III-E Optimal Matching Module

After passing through $L$ processing units, we can obtain the final keypoint
features of the image pair, _i.e._ ,
${}^{(L)}\mathbf{F}_{\mathbf{A}}\in\mathbb{R}^{M\times D}$ and
${}^{(L)}\mathbf{F}_{\mathbf{B}}\in\mathbb{R}^{N\times D}$. Following
SuperGlue [6], we first compute the similarity matrix
${\mathbf{S}=}^{(L)}\mathbf{F}_{\mathbf{A}}^{(L)}\mathbf{F}_{\mathbf{B}}^{\top}$
and then augment $\mathbf{S}$ to $\hat{\mathbf{S}}$ by appending a new row and
column as dustbins, filled with a single learnable parameter $z$. Finally,
Sinkhorn [50] algorithm is applied on $\hat{\mathbf{S}}$ to generate the
assignment matrix $\mathbf{P}\in[0,1]^{M\times N}$:

$\displaystyle\hat{S}_{i,j}=\left\\{\begin{aligned} &{S}_{i,j},\;i\leq M,j\leq
N\\\ &z,\;\text{otherwise}\\\
\end{aligned},\;\hat{\mathbf{S}}\in\mathbb{R}^{(M+1)\times(N+1)},\right.$ (11)
$\displaystyle\hat{\mathbf{P}}=\text{Sinkhorn}(\hat{\mathbf{S}}),\;\mathbf{P}=\hat{\mathbf{P}}_{1:M,1:N},$
(12)

where $\mathbf{P}=\hat{\mathbf{P}}_{1:M,1:N}$ denotes the first $M$ rows and
$N$ columns of matrix $\hat{\mathbf{P}}$.

After deriving the assignment matrix $\mathbf{P}$, the reliable matches can be
established by an MNN check with a predefined inlier threshold.

###  III-F Loss Formulation

We formulate our loss as two parts: 1) _Matching Loss_ , which enforces the
network to predict as many correct matches as possible, and 2) _Binary
Classification Loss_ , which guides the BCAS module to produce reliable
matchability scores, ensuring that the sampled keypoints are matchable. Given
the indices of ground truth matches
$\mathbf{C}_{\mathbf{m}}=\\{(i,j)\\}\in\alpha\times\beta$ and non-repeatable
keypoints $\mathbf{C}_{\mathbf{nA}}$, $\mathbf{C}_{\mathbf{nB}}$, where a
keypoint is regarded as non-repeatable (unmatchable) if there are no
corresponding keypoints in the other image, our _Matching Loss_
$\mathcal{L}_{match}$ is defined as:

$\displaystyle\mathcal{L}_{match}=-\frac{1}{|\mathbf{C}_{\mathbf{m}}|}\sum_{(i,j)\in\mathbf{C}_{\mathbf{m}}}\log(\hat{\mathbf{P}}_{i,j})$
$\displaystyle-\frac{1}{2|\mathbf{C}_{\mathbf{nA}}|}\sum_{i\in\mathbf{C}_{\mathbf{nA}}}\log(\hat{\mathbf{P}}_{i,N+1})-\frac{1}{2|\mathbf{C}_{\mathbf{nB}}|}\sum_{j\in\mathbf{C}_{\mathbf{nB}}}\log(\hat{\mathbf{P}}_{M+1,j}).$
(13)

As for the _Binary Classification Loss_ $\mathcal{L}_{cls}$ that is used to
train the matchability predictor in Sec. III-C, we adopt a cross entropy loss
for matchable/non-repeatable keypoint binary classification. Specifically, a
keypoint whose index belongs to the index list $\mathbf{C}_{\mathbf{nA}}$ or
$\mathbf{C}_{\mathbf{nB}}$ will be labeled as 0 (_i.e._ , non-repeatable),
otherwise it will be labeled as 1 (_i.e._ , matchable keypoints). Details of
$\mathcal{L}_{cls}$ can refer to some learning-based outlier rejection methods
[9].

To sum up, the optimization objective of our network is to minimize a hybrid
loss function as follows:

$\mathcal{L}=\mathcal{L}_{match}+\lambda\sum_{\ell=L_{1}+1}^{L}{{}^{(\ell)}\mathcal{L}_{cls}},$
(14)

where ${{}^{(\ell)}\mathcal{L}_{cls}}$ means the _Binary Classification Loss_
of $\ell$-th processing unit, $L_{1}$ and $L$ are the total number of
initialization processing units and GNN layers cascaded in the network,
respectively, and $\lambda$ is a weight to balance the two loss terms.

##  IV Experiments

In the following sessions, we first present the implementation details of our
MaKeGNN, then evaluate it on three diverse tasks which heavily rely on the
quality of matches established by feature matching methods, namely: relative
camera estimation, fundamental matrix estimation, and visual localization.
Finally, a comprehensive analysis is provided for better understanding
MaKeGNN.

###  IV-A Implementation Details

Following SGMNet [23], we train our network on GL3D dataset [52] from scratch,
which covers outdoor and indoor scenes, to obtain a generic model. Concretely,
GL3D is originally based on 3D reconstruction of 543 different scenes
including landmarks and small objects, while in its latest version additional
713 sequences of internet tourism photos are added. For each sequence, we
sample 1$k$ pairs of images and retain those with common track ration in the
range of $[0.1,0.5]$ and rotation angle in the range of
$[6^{\circ},60^{\circ}]$, both of which are available in the original dataset,
making sure that the image pairs for training are not too hard or too easy.
Also, we reproject each keypoint to the other image and compute its
reprojection distances with depth maps, to obtain the indices of ground truth
matches and non-repeatable keypoints. To be specific, a keypoint is labeled as
non-repeatable if its reprojection distances with all keypoints in the other
image are larger than 10 pixels, while a pair of keypoints that are nearest to
each other after reprojection and with a reprojection distance lower than 3
pixels, are considered as ground truth matches, and both of the two keypoints
are regraded to be matchable. We further remove image pairs which contains
fewer than 50 ground truth matches. Finally, about 400$k$ image pairs are
generated for training.

We sample 1$k$ keypoints and 128 well-distributed keypoints with high
matchability scores for each image during the training process. We adopt Adam
optimizer with a learning rate of $10^{-4}$ and a batchsize of 16 in
optimization. We utilize a learning decay strategy after 300$k$ iterations
with a decay rate of 0.999996 until 900$k$ iterations. Matchability score
weight $\lambda$ in loss is set to 5. The total number of processing units is
set to $L=9$ ($L_{1}=3$ and $L_{2}=6$). We use 4-head attention in both ICA
and MKACA modules, and perform 100 Sinkhorn iterations to obtain the
assignment matrix. During the testing phase, we sample
$[\frac{128\\#\text{keypoint}}{2000}]$ matchable keypoints, where
$\\#\text{keypoint}$ denotes the number of keypoints, and use an inlier
threshold of 0.2 to keep reliable matches from the soft assignment. All
experiments are conducted on Ubuntu 18.04 with GeForce RTX 3090 GPUs.

###  IV-B Relative Pose Estimation

Relative pose estimation refers to estimate the relative position relationship
(_i.e._ , rotation and translation) between different camera views, the
accuracy of which heavily relies on the quality of model-predicted matching
pairs.

####  IV-B1 Datasets

As in the previous work [23], we adopt two popular datasets, YFCC100M [22] and
ScanNet [53] to evaluate the feature matching ability of our MaKeGNN on this
task in outdoor and indoor scenes, respectively. More specifically, for
YFCC100M which is a large-scale outdoor dataset containing 100 million images
from Internet, we leverage camera poses and sparse 3D models provided by
COLMAP [3] to generate ground truth, and choose 4 sequences for evaluation as
in [9]. ScanNet which is a large-scale indoor dataset widely used for depth
prediction [54], consists of monocular sequences with ground truth poses and
depth images. Following SuperGlue [6], we select 1500 image pairs for
evaluation. We evaluate MaKeGNN using both hand-designed RootSIFT [55, 25] and
learning-based SuperPoint [27] features. Particularly, we detect up to 2$k$
keypoints on YFCC100M for both features, and up to 1$k$ and 2$k$ keypoints on
ScanNet for SuperPoint and RootSIFT, respectively.

####  IV-B2 Evaluation Protocols

Following [6, 23, 24], we report the area under the cumulative error curve
(AUC) of the pose error (_i.e._ , the maximum of the angular error in rotation
and translation) at multiple thresholds ($5^{\circ}$, $10^{\circ}$,
$20^{\circ}$). Importantly, relative poses are recovered by estimating
essential matrix with RANSAC. We also report the mean matching score (M.S.)
[27, 6], _i.e._ , the ratio of correct matches to total keypoints, and the
mean precision (Prec.) [27, 6] of the established matches, to evaluate the
matching performance.

####  IV-B3 Baselines

We compare MaKeGNN with 1) traditional heuristic pruning strategies, including
NN+RT, MNN [25], and AdaLAM [56], and 2) learning-based matching methods,
including OANet [9] and ConvMatch [15], SuperGlue [6], SGMNet [23], and
ParaFormer [31]. For the sake of fairness, we meticulously retrain all the
learning-based methods on the same sequences of GL3D [52] where 1$k$ keypoints
are detected per image.

####  IV-B4 Results of Outdoor Pose Estimation

The challenges of outdoor image matching mainly come from large illumination
variation, extreme viewpoint change, and occlusion. We present several
visualization results of outdoor scenes in Fig. 4. As is evident, in
comparison to SuperGlue and SGMNet, our MaKeGNN can retrieve richer
geometrically consistent matches with fewer mismatches.

Figure 4: Matching results on YFCC100M with SuperPoint features.
Correspondences are in green if they are consistent with the ground truth
epipolar geometry, and in red otherwise. Pose estimation results, M.S., and
Prec. are shown at the top left corner.

The quantitative results with RANSAC post-processing are reported in Tab. I.
It is worth noting that when using SuperPoint for evaluation, we adopt MNN as
the comparative method instead of NN+RT, as the latter would establish
considerably fewer matches [27]. Undoubtedly, the performance of such
heuristic tricks, _i.e._ , NN+RT and MNN, is quite poor. While outlier
rejection methods, AdaLAM and OANet, can greatly improve the precision of
initial matches, their performance is also limited by the quality of the
initial set. Clearly, compared to these above methods, learning-based matchers
achieve significant higher pose accuracy. In particular, our MaKeGNN
consistently outperforms other competitors on pose estimation at all threshold
and delivers competitive matching performance regardless of using RootSIFT or
SuperPoint, due to the compact and robust message passing guided by well-
distributed matchable keypoints.

TABLE I: Evaluation on YFCC100M for outdoor pose estimation. Pose estimation
AUC at different thresholds, M.S., and Prec. are reported. Red indicates the
best, green ranks the second, and blue ranks the third.

Feature | Matcher | Pose estimation AUC | M.S. | Prec.
---|---|---|---|---
@$5^{\circ}$ | @$10^{\circ}$ | @$20^{\circ}$
RootSIFT | NN+RT | 48.53 | 58.16 | 68.13 | 4.44 | 56.38
AdaLAM (4$k$) | 57.78 | 68.01 | 77.38 | 7.92 | 83.15
OANet | 58.00 | 67.80 | 77.46 | 5.84 | 81.80
ConvMatch | 59.23 | 68.54 | 77.56 | 8.03 | 67.91
SuperGlue | 63.20 | 72.71 | 81.86 | 16.60 | 81.71
SGMNet | 62.80 | 72.49 | 81.45 | 17.06 | 86.09
ParaFormer | 61.80 | 71.70 | 81.18 | 17.09 | 76.29
MaKeGNN | 64.73 | 73.91 | 82.78 | 17.54 | 84.59
SuperPoint | MNN | 35.83 | 44.18 | 53.66 | 3.63 | 58.96
AdaLAM (2$k$) | 40.20 | 49.03 | 59.11 | 10.17 | 72.57
OANet | 48.80 | 59.06 | 70.02 | 12.48 | 71.95
ConvMatch | 50.28 | 61.25 | 71.78 | 12.58 | 68.34
SuperGlue | 60.25 | 70.46 | 80.06 | 19.29 | 78.19
SGMNet | 61.13 | 71.06 | 80.18 | 22.06 | 84.61
ParaFormer | 61.75 | 72.03 | 81.23 | 22.31 | 81.28
MaKeGNN | 63.70 | 73.48 | 82.22 | 23.04 | 85.58

####  IV-B5 Results of Indoor Pose Estimation

We also evaluate the performance of our MaKeGNN on ScanNet for indoor pose
estimation, which presents greater challenges compared to outdoor scenes due
to factors such as poor texture and repetitive elements. Even so,
visualization results shown in Fig. 5 qualitatively demonstrate that MakeGNN
can achieve impressive performance. Further looking at Tab. II, as with
YFCC100M, MakeGNN is still more powerful than other baselines at all AUC
thresholds with both RootSIFT and SuperPoint, indicating that well-distributed
matchable keypoints can provide valuable matching priors to guide the context
aggregation process, suppressing interference of considerable non-repeatable
keypoints and enabling accurate pose estimation.

TABLE II: Evaluation on ScanNet for indoor pose estimation. Pose estimation
AUC at different thresholds, M.S., and Prec. are reported. Red indicates the
best, green ranks the second, and blue ranks the third.

Feature | Matcher | Pose estimation AUC | M.S. | Prec.
---|---|---|---|---
@$5^{\circ}$ | @$10^{\circ}$ | @$20^{\circ}$
RootSIFT | NN+RT | 21.59 | 30.82 | 40.56 | 2.33 | 28.26
ConvMatch | 24.76 | 33.43 | 43.02 | 4.28 | 32.20
SuperGlue | 32.47 | 42.53 | 53.20 | 8.43 | 42.22
SGMNet | 32.29 | 42.81 | 54.13 | 8.80 | 45.59
ParaFormer | 32.62 | 43.32 | 54.21 | 9.09 | 38.38
MaKeGNN | 33.69 | 44.05 | 55.13 | 9.29 | 44.68
SuperPoint | MNN | 19.72 | 27.81 | 38.00 | 8.72 | 44.54
ConvMatch | 24.63 | 33.93 | 40.25 | 14.94 | 37.37
SuperGlue | 34.18 | 44.35 | 54.89 | 16.25 | 46.16
SGMNet | 32.42 | 42.88 | 54.58 | 16.63 | 47.63
ParaFormer | 34.96 | 45.66 | 56.85 | 16.62 | 46.64
MaKeGNN | 36.43 | 47.06 | 58.04 | 16.88 | 48.39

Figure 5: Matching results on ScanNet with SuperPoint features.
Correspondences are in green if they are consistent with the ground truth
epipolar geometry, and in red otherwise. Pose estimation results, M.S., and
Prec. are shown at the top left corner.

###  IV-C Fundamental Matrix Estimation

We further apply our method to recover the fundamental matrix (FM) with
uncalibrated cameras, which suits more general-purpose scenes than other
geometric models, _e.g._ , homography and essential matrix.

####  IV-C1 Dataset

We resort to FM-Bench [57] to validate the effectiveness of our network on
fundamental matrix estimation. More specifically, FM-Bench is comprised of
four sub-datasets: TUM [58], KITTI [59], Tanks and Temples (T&T) [60], and
Community Photo Collection (CPC) [61], the details of which are summarized in
Tab. III. We randomly select 1000 matched image pairs from each dataset for
evaluation. In particular, TUM and KITTI provide ground truth camera
intrinsics and extrinsics, enabling us to directly derive the ground truth
fundamental matrix from them. However, for T&T and CPC, where camera
intrinsics and extrinsics are unknown, we apply COLMAP [3] to reconstruct the
image sequences and consequently obtain the ground truth matrix.

TABLE III: Details of the experimental datasets for fundamental matrix estimation. Dataset | Description | #Seq | #Image | Resolution | Baseline
---|---|---|---|---|---
TUM [58] | indoor scenes | 3 | 5994 | 480$\times$640 | short
KITTI [59] | street views | 5 | 9065 | 370$\times$1226 | short
T&T [60] | outdoor scenes | 3 | 922 | 1080$\times$2048 1080$\times$1920 | wide
CPC [61] | internet photos | 1 | 1615 | varying | wide

####  IV-C2 Evaluation Protocols

After establishing matches with feature matching approaches, we can estimate
the fundamental matrix for each image pair with RANSAC. Considering the
different image resolutions, we adopt Normalized Symmetry Geometric Distance
(NSGD) [57] to evaluate the accuracy of the estimated fundamental matrix,
which is defined as the ratio of SGD [62] to the length of the image diagonal.
Importantly, we detect up to 4$k$ keypoints for each image, and determine
whether an estimate is accurate by a threshold (0.05 is used by default) for
the Normalized SGD error. Following FM-Bench paper [57], we present: 1) recall
(%Recall), the ratio of accurate estimates to all estimates evaluated by NSGD,
and 2) mean number of correct correspondences (#Corrs(-m)) after/before
RANSAC. It should be mentioned that #Corrs(-m) is only used for result
analysis rather than performance comparison, since the influence of
correspondence numbers on high-level visual applications like SfM [3] is
debatable [63]. However, too few matches would degrade these applications.
Hence, we give minimal attention to match numbers, as long as they are not
excessively low.

####  IV-C3 Baselines

Similar to the relative pose estimation experiment, we select hand-crafted
heuristics, NN+RT [25] or MNN, learning-based outlier pruners, OANet [62] and
ConvMatch [15], and learning-based matchers, SuperGlue [6], SGMNet [23], and
ParaFormer [31] as the comparative methods.

####  IV-C4 Results

The quantitative results are concluded in Tab. IV. %Recall indicates the
overall performance. Notably, the performance NN+RT or MNN on KITTI is similar
to learning-based matchers, since this sub-dataset is only comprised of short-
baseline image pairs which are easy for the fundamental matrix estimation
task. Obviously, with RootSIFT features, MaKeGNN is capable of achieving the
state-of-the-art performance on all sub-datasets. With SuperPoint features,
our network performs best on the first three sub-datasets (_i.e._ , CPC,
KITTI, and TUM) and ranks the second on T&T.

To sum up, with well-distributed matchable keypoints as bottlenecks to guide
compact and robust message passing, the proposed method yields promising
results, both in short-baseline (TUM and KITTI) or wide-baseline (CPC and T&T)
scenarios.

TABLE IV: Evaluation on FM-Bench for fundamental matrix estimation. %Recall
and #Corrs(-m) after/before RANSAC are reported. Red indicates the best, green
ranks the second, and blue ranks the third. Notably, %Recall indicates the
overall performance.

Feature | Matcher | CPC | KITTI | TUM | T&T
---|---|---|---|---|---
%Recall | #Corrs(-m) | %Recall | #Corrs(-m) | %Recall | #Corrs(-m) | %Recall | #Corrs(-m)
RootSIFT | NN+RT | 54.6 | 110(199) | 90.3 | 866(995) | 62.0 | 454(680) | 82.1 | 246(426)
OANet | 58.6 | 119(167) | 89.0 | 773(854) | 62.3 | 454(396) | 84.7 | 219(306)
ConvMatch | 52.8 | 139(237) | 85.8 | 504(587) | 64.4 | 576(807) | 73.5 | 228(376)
SuperGlue | 59.0 |  254(660) | 90.4 |  1297(2020) | 65.2 |  871(1689) | 86.5 |  451(1032)
SGMNet | 61.6 |  284(664) | 91.1 | 1122(1671) | 66.5 |  942(1651) | 85.6 |  467(947)
ParaFormer | 59.4 | 244(675) | 91.2 |  1264(1883) | 62.0 | 838(1750) | 87.1 | 429(969)
MaKeGNN | 61.7 |  262(658) | 91.6 |  1249(1777) | 66.7 |  882(1515) | 87.4 |  443(915)
SuperPoint | MNN | 34.5 | 152(421) | 88.6 | 848(1490) | 56.7 | 280(420) | 72.8 | 287(717)
OANet | 62.9 | 186(343) | 82.2 | 482(736) | 61.4 | 332(473) | 91.2 | 280(477)
ConvMatch | 55.5 | 242(942) | 85.8 | 848(2061) | 59.9 | 743(1996) | 85.8 | 394(1337)
SuperGlue | 68.0 | 320(991) | 88.1 | 956(2101) | 58.7 | 725(2099) | 93.7 | 456(1305)
SGMNet | 69.3 |  377(987) | 88.0 |  981(2157) | 64.7 |  924(2067) | 93.6 |  506(1260)
ParaFormer | 71.0 |  351(1058) | 88.4 |  984(2178) | 61.5 |  801(2103) | 95.6 |  484(1372)
| MaKeGNN | 72.4 |  364(1021) | 88.8 |  984(2035) | 64.7 |  781(1749) | 94.2 |  498(1319)

###  IV-D Visual Localization

Recent advances in feature matching learning are also conducive to visual
localization, which aims to estimate the 6 degree-of-freedom (6-DOF) camera
pose of a query image in relation to the corresponding 3D scene model. To be
specific, visual localization remains highly challenging particularly for
large-scale environments and in presence of significant illumination variation
and extreme viewpoint change. Consequently, we integrate MaKeGNN into the
official HLoc [4] pipeline to investigate how it benefits visual localization.

####  IV-D1 Dataset

We adopt Aachen Day-Night dataset [64] to evaluate the effectiveness of our
network on visual localization. Specifically speaking, Aachen Day-Night
comprises of 4328 reference images from a European old town and 922 query (824
daytime, 98 nighttime) images taken by mobile phone cameras.

####  IV-D2 Evaluation Protocols

We resort to the official pipeline of Aachen Day-Night benchmark.
Specifically, correspondences between reference images are first used to
triangulate a 3D scene model. Then, correspondences between each query image
and its retrieved reference images are established by feature matching methods
to recover the relative pose. Importantly, we detect up to 8$k$ keypoints with
RootSIFT and 4$k$ keypoints with SuperPoint for each image. In line with the
official benchmark, we report the percentage of correctly localized queries at
different distance and orientation thresholds, _i.e._ , High-precision (0.25m,
2∘), Medium-precision (0.5m, 5∘), and Coarse-precision (5.0m, 10∘), to reflect
the visual localization performance.

####  IV-D3 Baselines

We compare MakeGNN with MNN, SuperGlue [6], SGMNet [23], and ParaFormer [31].
In particular, we perform 50 Sinkhorn iterations for all GNN-based competitors
to ensure efficiency.

####  IV-D4 Results

Tab. V presents the all-sided quantitative evaluation on Aachen Day-Night.
Despite the larger viewpoint and illumination variations typically encountered
in the long-term large-scale localization task, leading to more non-repeatable
keypoints in both query and reference images, MaKeGNN consistently outperforms
other baselines when using both RootSIFT and SuperPoint features. This is
attributed to MaKeGNN’s dynamic sampling of two sets of well-distributed
matchable keypoints as bottlenecks, which avoids the interference of non-
repeatable keypoints and facilitates context aggregation through a compact and
robust attention pattern.

TABLE V: Evaluation on Aachen Day-Night for visual localization. The percentage of correctly localized queries at different thresholds is reported. Red indicates the best, green ranks the second, and blue ranks the third. Feature | Matcher | Day | Night
---|---|---|---
(0.25m, 2°) / (0.5m, 5°) / (5.0m, 10°)
RootSIFT | MNN | 82.3/89.1/92.1 | 43.9/56.1/65.3
SuperGlue |  83.1/90.9/95.6 |  71.4/75.5/85.7
SGMNet | 81.8/90.2/96.1 | 67.3/75.5/93.9
ParaFormer |  83.4/91.1/95.8 |  69.4/75.5/87.8
MaKeGNN |  83.9/91.3/96.9 |  73.2/79.6/95.9
SuperPoint | MNN | 85.4/92.0/95.5 | 75.5/86.7/92.9
SuperGlue |  86.7/93.1/97.1 | 77.6/88.8/98.0
SGMNet |  86.9/93.6/97.1 |  79.6/92.9/99.0
ParaFormer |  86.7/92.4/97.2 |  81.6/90.8/98.0
MaKeGNN |  87.5/93.7/97.2 |  82.6/92.9/98.0

###  IV-E Understanding MaKeGNN

####  IV-E1 Efficiency

We compare the computation and memory efficiency of our network with SuperGlue
[6], SGMNet [23], and ParaFormer [31]. Fig. 6 summarizes the statistical
results _w.r.t._ the number of input 128-D features, using a single GeForce
RTX 3090 GPU with 24GB memory. In particular, memory occupation are averaged
by batch size during the training process. Apparently, since MaKeGNN leverages
well-distributed matchable keypoints as bottlenecks to guide compact message
passing, it reduces the runtime and memory occupation on a large number of
keypoints (10$k$) by 34.77% and 39.14%, respectively, compared to SuperGlue.
Although SGMNet exhibits greater efficiency in terms of time and memory, the
proposed method deliver significantly better performance while maintaining
modest time and memory efficiency. In other words, MaKeGNN achieves an
improved trade-off between accuracy and efficiency, rendering it more suitable
for demanding real-time visual tasks.

Figure 6: Computation and memory efficiency of learning-based matchers on a
single GeForce RTX 3090 GPU. Notably, the memory occupation of SuperGlue is
close to that of ParaFormer.

####  IV-E2 Impact of Sampled Matchable Keypoint Number

At the heart of MaKeGNN lies the dynamic sampling of two sets of well-
distributed keypoints with high matchability scores, which serve as message
bottlenecks for compact and robust message passing. Consequently, the number
of sampled matchable keypoints has a direct impact on both the efficiency and
accuracy of MaKeGNN. To investigate this impact, we further perform a grid
search for different keypoint and sampling numbers, on ScanNet dataset using
RootSIFT features.

As depicted in Fig. 7, maintaining an approximate proportional relationship
between the number of input keypoints and sampled matchable ones delivers the
optimal performance. The reason for this is that sampling an excessive number
of matchable keypoints may introduce several insignificant message
interaction, resulting in less reliable guidance. Conversely, sampling too few
matchable keypoints can result in significant information loss.

Figure 7: The impact of the sampled matchable keypoint number when varying the
input keypoint number. Numbers in grids are AUC@$5^{\circ}$ on ScanNet using
RootSIFT features.

####  IV-E3 Ablation Study

To investigate the contribution of each design presented in our approach, we
conduct a comprehensive variety of ablation studies on ScanNet dataset using
SuperPoint, and the results are concluded in Tab. VI. Row 6 shows our complete
model as a point of reference. Row 3 reveals that compared to only leveraging
per-keypoint feature for matchabilty score prediction, combining it with
bilateral context is a better choice, since this combination results in a
significant improvement in the precision and recall of the sampled matchable
keypoints, as indicated in Tab. VII. Row 4 validates that compared to the
vanilla attention, our matchability score-guided attention that is tailor-made
for the feature matching task, can suppress the interference of non-repeatable
keypoints caused by occlusion and failure of the detector, empowering the
network to achieve cleaner and sharper message passing. Row 5 further proves
that sampling well-distributed matchable keypoints as message bottlenecks
plays an important role, which is capable of guiding information interaction
across images for robust feature matching.

In summary, each component in our network contributes to the final performance
notably.

TABLE VI: Ablation study of MaKeGNN. w/o. B.C. stands for only using per-
keypoint feature instead of concatenating it with Bilateral Context (_i.e._ ,
global representation vectors $\mathbf{f}_{\mathbf{A}}^{g}$ and
$\mathbf{f}_{\mathbf{B}}^{g}$), to predict the matchability score. w/o.
M.G.A.A. stands for replacing the matchability score-guided attention with the
vanilla attention for context aggregation. w. Rand. Sampling means that
sampling keypoints randomly instead of pick the top-k matchability scores
processed by NMS. AUC@$20^{\circ}$, M.S., Prec. on ScanNet using SuperPoint
features are reported. Bold indicates the best.

Matcher | AUC@$20^{\circ}$ | M.S. | Prec.
---|---|---|---
(1) MNN | 38.00 | 8.72 | 44.54
(2) SuperGlue | 54.89 | 16.25 | 46.16
(3) MaKeGNN w/o. B.C. | 56.43 | 16.50 | 48.12
(4) MaKeGNN w/o. M.G.A.A. | 57.12 | 16.61 | 48.33
(5) MaKeGNN w. Rand. Sampling | 51.24 | 15.33 | 39.80
(6) MaKeGNN full | 58.04 | 16.88 | 48.39

TABLE VII: Precision and recall of matchable keypoints sampled by the last BCAS module. A keypoint is considered matchable, if its matchability score larger than 0.5. Sampler | Precision | Recall
---|---|---
BCAS w/o. B.C. | 85.63 | 91.12
BCAS | 96.87 | 96.19

####  IV-E4 Visualization of Sampled Matchable Keypoints

We visualize the sampled matchable keypoints in the image pair, using the
proposed BCAS module, as depicted in Fig. 8. The brightness of green
corresponds to the matchability score, with brighter green indicating higher
scores. Obviously, the sampled keypoints with high matchability scores span
almost the whole meaningful regions and are positioned in significant
structures, thereby providing fruitful geometric and visual cues to facilitate
the context aggregation process.

Figure 8: Example of (a) input keypoints and (b) sampled matchable keypoints.

##  V Conclusion

This paper presents MaKeGNN, a top-performing graph neural network for feature
matching learning. With the proposed _Bilateral Context-Aware Sampling_ (BCAS)
and _Matchable Keypoint-Assisted Context Aggregation_ (MKACA) modules, MaKeGNN
is capable of aggregating context with a compact and robust attention pattern.
Comprehensive experiments on diverse tasks and datasets demonstrate that our
method outperforms the strongest prior model with modest computation and
memory costs.

## References

  * [1] J. Ma, X. Jiang, A. Fan, J. Jiang, and J. Yan, “Image matching from handcrafted to deep features: A survey,” _International Journal of Computer Vision_ , vol. 129, pp. 23–79, 2021.
  * [2] R. Mur-Artal, J. M. M. Montiel, and J. D. Tardos, “Orb-slam: a versatile and accurate monocular slam system,” _IEEE Transactions on Robotics_ , vol. 31, no. 5, pp. 1147–1163, 2015.
  * [3] J. L. Schonberger and J.-M. Frahm, “Structure-from-motion revisited,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 4104–4113.
  * [4] P.-E. Sarlin, C. Cadena, R. Siegwart, and M. Dymczyk, “From coarse to fine: Robust hierarchical localization at large scale,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 12 716–12 725.
  * [5] H. Zhang, H. Xu, X. Tian, J. Jiang, and J. Ma, “Image fusion meets deep learning: A survey and perspective,” _Information Fusion_ , vol. 76, pp. 323–336, 2021.
  * [6] P.-E. Sarlin, D. DeTone, T. Malisiewicz, and A. Rabinovich, “Superglue: Learning feature matching with graph neural networks,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 4938–4947.
  * [7] Y. Lu, J. Ma, L. Fang, X. Tian, and J. Jiang, “Robust and scalable gaussian process regression and its applications,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 21 950–21 959.
  * [8] K. M. Yi, E. Trulls, Y. Ono, V. Lepetit, M. Salzmann, and P. Fua, “Learning to find good correspondences,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 2666–2674.
  * [9] J. Zhang, D. Sun, Z. Luo, A. Yao, L. Zhou, T. Shen, Y. Chen, L. Quan, and H. Liao, “Learning two-view correspondences and geometry using order-aware network,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 5845–5854.
  * [10] W. Sun, W. Jiang, E. Trulls, A. Tagliasacchi, and K. M. Yi, “Acne: Attentive context normalization for robust permutation-equivariant learning,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 11 286–11 295.
  * [11] C. Zhao, Y. Ge, F. Zhu, R. Zhao, H. Li, and M. Salzmann, “Progressive correspondence pruning by consensus learning,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2021, pp. 6464–6473.
  * [12] Y. Liu, L. Liu, C. Lin, Z. Dong, and W. Wang, “Learnable motion coherence for correspondence pruning,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 3237–3246.
  * [13] L. Dai, Y. Liu, J. Ma, L. Wei, T. Lai, C. Yang, and R. Chen, “Ms2dg-net: Progressive correspondence learning via multiple sparse semantics dynamic graph,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 8973–8982.
  * [14] L. Zheng, G. Xiao, Z. Shi, S. Wang, and J. Ma, “Msa-net: Establishing reliable correspondences by multiscale attention network,” _IEEE Transactions on Image Processing_ , vol. 31, pp. 4598–4608, 2022.
  * [15] S. Zhang and J. Ma, “Convmatch: Rethinking network design for two-view correspondence learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2023.
  * [16] Z. Li, S. Zhang, and J. Ma, “U-match: Two-view correspondence learning with hierarchy-aware local context aggregation,” in _Proceedings of the International Joint Conference on Artificial Intelligence_ , 2023.
  * [17] Z. Li, Y. Ma, X. Mei, and J. Ma, “Two-view correspondence learning using graph neural network with reciprocal neighbor attention,” _ISPRS Journal of Photogrammetry and Remote Sensing_ , vol. 202, pp. 114–124, 2023.
  * [18] X. Liu, G. Xiao, R. Chen, and J. Ma, “Pgfnet: Preference-guided filtering network for two-view correspondence learning,” _IEEE Transactions on Image Processing_ , vol. 32, pp. 1367–1378, 2023.
  * [19] C. R. Qi, H. Su, K. Mo, and L. J. Guibas, “Pointnet: Deep learning on point sets for 3d classification and segmentation,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 652–660.
  * [20] S. Suwanwimolkul and S. Komorita, “Efficient linear attention for fast and accurate keypoint matching,” in _Proceedings of the International Conference on Multimedia Retrieval_ , 2022, pp. 330–341.
  * [21] Y. Cai, L. Li, D. Wang, X. Li, and X. Liu, “Htmatch: An efficient hybrid transformer based graph neural network for local feature matching,” _Signal Processing_ , vol. 204, p. 108859, 2023.
  * [22] B. Thomee, D. A. Shamma, G. Friedland, B. Elizalde, K. Ni, D. Poland, D. Borth, and L.-J. Li, “Yfcc100m: The new data in multimedia research,” _Communications of the ACM_ , vol. 59, no. 2, pp. 64–73, 2016.
  * [23] H. Chen, Z. Luo, J. Zhang, L. Zhou, X. Bai, Z. Hu, C.-L. Tai, and L. Quan, “Learning to match features with seeded graph matching network,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2021, pp. 6301–6310.
  * [24] Y. Shi, J.-X. Cai, Y. Shavit, T.-J. Mu, W. Feng, and K. Zhang, “Clustergnn: Cluster-based coarse-to-fine graph neural network for efficient feature matching,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 12 517–12 526.
  * [25] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” _International Journal of Computer Vision_ , vol. 60, pp. 91–110, 2004.
  * [26] E. Rublee, V. Rabaud, K. Konolige, and G. Bradski, “Orb: An efficient alternative to sift or surf,” in _Proceedings of the IEEE International Conference on Computer Vision_. Ieee, 2011, pp. 2564–2571.
  * [27] D. DeTone, T. Malisiewicz, and A. Rabinovich, “Superpoint: Self-supervised interest point detection and description,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 224–236.
  * [28] M. Dusmanu, I. Rocco, T. Pajdla, M. Pollefeys, J. Sivic, A. Torii, and T. Sattler, “D2-net: A trainable cnn for joint description and detection of local features,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 8092–8101.
  * [29] J. Revaud, C. De Souza, M. Humenberger, and P. Weinzaepfel, “R2d2: Reliable and repeatable detector and descriptor,” in _Proceedings of the Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [30] C. Wang, R. Xu, K. Lv, S. Xu, W. Meng, Y. Zhang, B. Fan, and X. Zhang, “Attention weighted local descriptors,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2023.
  * [31] X. Lu, Y. Yan, B. Kang, and S. Du, “Paraformer: Parallel attention transformer for efficient feature matching,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2023.
  * [32] Z. Li, Y. Ma, X. Mei, J. Huang, and J. Ma, “Guided neighborhood affine subspace embedding for feature matching,” _Pattern Recognition_ , vol. 124, p. 108489, 2022.
  * [33] Z. Ying, J. You, C. Morris, X. Ren, W. Hamilton, and J. Leskovec, “Hierarchical graph representation learning with differentiable pooling,” in _Proceedings of the Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [34] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Proceedings of the Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [35] R. Wang, J. Yan, and X. Yang, “Learning combinatorial embedding networks for deep graph matching,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 3056–3065.
  * [36] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” in _Proceedings of the International Conference on Learning Representations_ , 2020.
  * [37] N. Carion, F. Massa, G. Synnaeve, N. Usunier, A. Kirillov, and S. Zagoruyko, “End-to-end object detection with transformers,” in _Proceedings of the European Conference on Computer Vision_ , 2020, pp. 213–229.
  * [38] H. Wang, Y. Zhu, B. Green, H. Adam, A. Yuille, and L.-C. Chen, “Axial-deeplab: Stand-alone axial-attention for panoptic segmentation,” in _Proceedings of the European Conference on Computer Vision_ , 2020, pp. 108–126.
  * [39] J. Sun, Z. Shen, Y. Wang, H. Bao, and X. Zhou, “Loftr: Detector-free local feature matching with transformers,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 8922–8931.
  * [40] N. Kitaev, Ł. Kaiser, and A. Levskaya, “Reformer: The efficient transformer,” in _Proceedings of the International Conference on Learning Representations_ , 2020.
  * [41] Y. Tay, D. Bahri, L. Yang, D. Metzler, and D.-C. Juan, “Sparse sinkhorn attention,” in _Proceedings of the International Conference on Machine Learning_ , 2020, pp. 9438–9447.
  * [42] A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret, “Transformers are rnns: Fast autoregressive transformers with linear attention,” in _Proceedings of the International Conference on Machine Learning_ , 2020, pp. 5156–5165.
  * [43] S. Wang, B. Z. Li, M. Khabsa, H. Fang, and H. Ma, “Linformer: Self-attention with linear complexity,” _arXiv preprint arXiv:2006.04768_ , 2020.
  * [44] B. Chen, P. Li, B. Li, C. Li, L. Bai, C. Lin, M. Sun, J. Yan, and W. Ouyang, “Psvit: Better vision transformer via token pooling and attention sharing,” _arXiv preprint arXiv:2108.03428_ , 2021.
  * [45] Y. Tay, M. Dehghani, D. Bahri, and D. Metzler, “Efficient transformers: A survey,” _ACM Computing Surveys_ , vol. 55, no. 6, pp. 1–28, 2022.
  * [46] M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” _Communications of the ACM_ , vol. 24, no. 6, pp. 381–395, 1981.
  * [47] R. Raguram, O. Chum, M. Pollefeys, J. Matas, and J.-M. Frahm, “Usac: A universal framework for random sample consensus,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 35, no. 8, pp. 2022–2038, 2012\.
  * [48] D. Barath and J. Matas, “Graph-cut ransac,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 6733–6741.
  * [49] D. Barath, J. Noskova, M. Ivashechkin, and J. Matas, “Magsac++, a fast, reliable and accurate robust estimator,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 1304–1312.
  * [50] M. Cuturi, “Sinkhorn distances: Lightspeed computation of optimal transport,” in _Proceedings of the Advances in Neural Information Processing Systems_ , vol. 26, 2013.
  * [51] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” _arXiv preprint arXiv:1710.10903_ , 2017.
  * [52] T. Shen, Z. Luo, L. Zhou, R. Zhang, S. Zhu, T. Fang, and L. Quan, “Matchable image retrieval by learning from surface reconstruction,” in _Proceedings of the Asian Conference on Computer Vision_ , 2019, pp. 415–431.
  * [53] A. Dai, M. Nießner, M. Zollhöfer, S. Izadi, and C. Theobalt, “Bundlefusion: Real-time globally consistent 3d reconstruction using on-the-fly surface reintegration,” _ACM Transactions on Graphics_ , vol. 36, no. 4, p. 1, 2017.
  * [54] G. Bae, I. Budvytis, and R. Cipolla, “Multi-view depth estimation by fusing single-view depth probability with multi-view geometry,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 2842–2851.
  * [55] R. Arandjelović and A. Zisserman, “Three things everyone should know to improve object retrieval,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2012, pp. 2911–2918.
  * [56] L. Cavalli, V. Larsson, M. R. Oswald, T. Sattler, and M. Pollefeys, “Handcrafted outlier detection revisited,” in _Proceedings of the European Conference on Computer Vision_ , 2020, pp. 770–787.
  * [57] J.-W. Bian, Y.-H. Wu, J. Zhao, Y. Liu, L. Zhang, M.-M. Cheng, and I. Reid, “An evaluation of feature matchers for fundamental matrix estimation,” in _Proceedings of the British Machine Vision Conference_ , 2019.
  * [58] J. Sturm, N. Engelhard, F. Endres, W. Burgard, and D. Cremers, “A benchmark for the evaluation of rgb-d slam systems,” in _Proceedings of the IEEE International Conference on Intelligent Robots and Systems_ , 2012, pp. 573–580.
  * [59] A. Geiger, P. Lenz, and R. Urtasun, “Are we ready for autonomous driving? the kitti vision benchmark suite,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern recognition_ , 2012, pp. 3354–3361.
  * [60] A. Knapitsch, J. Park, Q.-Y. Zhou, and V. Koltun, “Tanks and temples: Benchmarking large-scale scene reconstruction,” _ACM Transactions on Graphics_ , vol. 36, no. 4, pp. 1–13, 2017.
  * [61] K. Wilson and N. Snavely, “Robust global translations with 1dsfm,” in _Proceedings of the European Conference on Computer Vision_ , 2014, pp. 61–75.
  * [62] Z. Zhang, “Determining the epipolar geometry and its uncertainty: A review,” _International Journal of Computer Vision_ , vol. 27, pp. 161–195, 1998.
  * [63] J. L. Schonberger, H. Hardmeier, T. Sattler, and M. Pollefeys, “Comparative evaluation of hand-crafted and learned local features,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 1482–1491.
  * [64] T. Sattler, W. Maddern, C. Toft, A. Torii, L. Hammarstrand, E. Stenborg, D. Safari, M. Okutomi, M. Pollefeys, J. Sivic _et al._ , “Benchmarking 6dof outdoor visual localization in changing conditions,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 8601–8610.