GRAPH NEURAL NETWORKS FOR MULTI-IMAGE MATCHING
Year: 2019

Abstract:
In geometric computer vision applications, multi-image feature matching gives more accurate and robust solutions compared to simple two-image matching. In this work, we formulate multi-image matching as a graph embedding problem, then use a Graph Neural Network to learn an appropriate embedding function for aligning image features. We use cycle consistency to train our network in an unsupervised fashion, since ground truth correspondence can be difficult or expensive to acquire. Geometric consistency losses are added to aid training, though unlike optimization based methods no geometric information is necessary at inference time. To the best of our knowledge, no other works have used graph neural networks for multi-image feature matching. Our experiments show that our method is competitive with other optimization based approaches.

heading: 1 INTRODUCTION
text: Feature matching is an essential part of Structure from Motion and many geometric computer vision applications. The goal in multi-image feature matching is to take 2D feature positions from three or more images and find which ones correspond to the same point in the 3D scene. Methods such as SIFT feature matching (Lowe, 2004) combined with RANSAC (Fischler & Bolles, 1981) have been the standard for decades. However RANSAC-based approaches are limited to matching pairs of images, which can lead to global inconsistencies in the matching. Other works, such as Wang et al. (2018), have shown improvement in performance by optimizing cycle consistency, i.e. enforcing the pairwise feature matches to be globally consistent.
However, these multi-view consistency algorithms struggle in distributed and noisy settings. Having image features suited for this task would help improve performance, and deep learning has revolutionized how image features are computed (Yi et al., 2016). In this paper, we want to leverage the power of deep representations in order to compute feature descriptors that are robust across multiple views.
Unfortunately, there are obstacles to applying multi-view constraints directly to deep learning. Multi-view constraints are formulated in terms of sparse features, which traditional convolutional neural nets are not designed to handle. Thus we will need a new architecture to handle such constraints. More fundamentally, deep neural networks need large amounts of labeled data to train. Consequently unsupervised training is a more practical approach. In the absence of direct supervision, the additional signal of geometric constraints can help disambiguate visually similar features and reject outliers. Thus incorporating such constraints is important in training a network to solve this task.
In this work, we address these concerns using Graph Neural Networks (GNNs). The proposed method works directly on the graph of correspondences between the image features, which is agnostic to how the correspondences were computed, thus allowing the algorithm to work in a broad class of environments. To the best of our knowledge this work is the first to apply deep learning to the multi-view feature matching problem. We use an unsupervised loss, the cycle consistency loss, to train the network. We use geometric consistency losses to aid training, though no geometric information is used at inference time. Although our network is simple, it shows promising results compared to baselines which optimize for cycle-consistency without learned embeddings, using a matrix factorization loss (Zhou et al., 2015b; Leonardos et al., 2017). Furthermore, since inference requires only a single forward pass over the neural network, our approach is faster to achieve
comparable accuracy than methods which must solve an optimization problem every time. We perform experiments on the Rome16K dataset (Li et al., 2010) to test the effectiveness of our method compared to optimization based methods. Our contributions in this work are:
• We use a novel architecture to address the multi-image feature matching problem using GNNs with graph embeddings.
• We introduce an unsupervised multi-view cycle consistency loss that does not require labeled correspondences to train.
• We demonstrate the effectiveness of geometric consistency losses in improving training.

heading: 2 RELATED WORK

heading: 2.1 FEATURE MATCHING
text: Image feature matching has a rich history of research in computer vision. Much work has be done using hand-crafted feature descriptors such as SIFT (Lowe, 2004), SURF (Bay et al., 2006), BRIEF (Calonder et al., 2012), or ORB (Mur-Artal et al., 2015). RANSAC Fischler & Bolles (1981) is the most widely used robust estimation technique to filter out outliers from the matches. The combination of RANSAC and hand-crafted feature descriptors has constituted the bulk of the matching literature for the last 40 years. More recently Suh et al. (2015) and Hu et al. (2016) have shown graph matching of the features can be added for more robust matches between images.

heading: 2.2 MULTI-IMAGE MATCHING
text: Multi-image matching has traditionally been done using optimization based methods minimizing a cycle consistency based loss (see Section 3.3). Pachauri et al. (2013) and Arrigoni et al. (2017) use the eigenvectors of the matching matrix to obtain a low dimensional embedding. However, the assumption of low Gaussian noise is not realistic. Zhou et al. (2015b) and ? use more sophisticated optimization techniques on the matching matrix and thus produce more robust solutions. Leonardos et al. (2017) implement a distributed optimization scheme to solve for cycle consistency. Swoboda
et al. (2019) implement a convex relaxation of the low dimensional embedding problem. Shi et al. (2016) use tensor power iterations to solve the matching problem, also taking into account the intraimage matching graph. As an alternative to optimization based techniques, Tron et al. (2017) used density based clustering techniques to compute multi-image correspondence. Fathian et al. (2019) use a similar technique but formulates it as a generalized Rayleigh quotient problem to achieve better results. Moving away from feature matching, Zach et al. (2010) uses cycle-consistency-like constraints on pose graphs quite effectively. To the best of our knowledge, we are the first to use graph neural networks for multi-image matching.

heading: 2.3 DEEP LEARNING FOR MATCHING
text: Previous attempts to improve image matching techniques using machine learning have focused on learning the descriptors given ground truth correspondence from curated datasets such as Zagoruyko & Komodakis (2015); Yi et al. (2016); and Brachmann et al. (2017). Rocco et al. (2018) use a dense matching tensor with a weakly supervised loss to learn good features for matching. Zhou et al. (2019) has shown that these learned representations have limited ability for improving SfM tasks.
There are other methods to build correspondences such as Choy et al. (2016), but they only handle two-view constraints and require dense correspondences. Most similar to our work, Zhang & Lee (2019) use graph neural networks to do intra-image feature processing before doing two image inter-image feature similarity. However, their work only trains for pairs of image, while ours is explicitly trained for multi-image matching. Also similarly, Yi et al. (2018) attempts to improve correspondences by learning match probabilities for two-view RANSAC for greater robustness and speed. Like us Zhu et al. (2017) use cycle consistency in their loss; however their method is for image generation and is restricted to pairwise cycle consistency. Our method can be applied to 3 or more images. Hartmann et al. (2017) learns multi-image matching but requires heavy supervision from 3D object reconstructions, which can be difficult or expensive to obtain. Zhou et al. (2015a), unlike our method, uses dense correspondence, but uses cycle consistency to find semantic matches accross multiple views. Suwajanakorn et al. (2018) find 3 dimensional latent keypoints, trained using ground truth rotation and translation. However, their method is restricted to a limited number of object categories, which is different from the SfM setting we are considering here.

heading: 2.4 GRAPH NEURAL NETWORKS
text: Graph neural networks, true to their name, are deep neural networks operating in graph domains. Multi-image matching is novel application of them, as they are more typically used for applications such as citation networks or recommendation systems. They have received more attention recently (Bronstein et al., 2017; Defferrard et al., 2016; Kipf & Welling, 2017; Scarselli et al., 2009; Gama et al., 2018b;a; Battaglia et al., 2018). The first methods to learn neural networks over graphs were the so-called Spectral methods. They used the eigenvectors of the graph Laplacian to compute convolutions, which can learn graph specific convolution kernels (as in Bruna et al. (2013)), but require an a-priori known graph structure. Newer non-spectral methods do not require a-priori knowledge, as seen in Bronstein et al. (2017); Kipf & Welling (2017); Scarselli et al. (2009); and Gama et al. (2018a). Most of these methods use polynomials of the graph Laplacian to compute neighborhood averages. Gama et al. (2018b;a) formalize this notion and generalize it beyond the use of the graph Laplacian. To improve performance, more sophisticated aggregation techniques and global information passing can be used as discussed in Battaglia et al. (2018). The closest work on Graph Neural Networks to ours is Kipf & Welling (2016), which uses GNNs to reconstruct adjacency matrices, though not in a geometric context.

heading: 3 METHOD
text: Our goal is to learn optimal features that capture multiple image views by filtering out noisy feature matches. The input to our algorithm is a set of features and noisy correspondences, and the output is a new set of features where the pairwise similarities of these features correspond to the true matches. An outline of our approach can be seen in figure 1. We do this by training the new set of feature embeddings to be cycle consistent. We formulate this problem in terms of the correspondence graph of the features. Graphs G = (V, E) have a set of vertices V and of directed edges E ⊆ V × V .
For a vertex v ∈ V we use N h(v) to denote the h-hop neighbors of v, with the superscript left out for 1-hop neighbors. Similarly E(v) is used to denote the edges associated with v. To denote the vertices connected to an edge e ∈ E we write e(v1, v2).

heading: 3.1 CORRESPONDENCE GRAPH
text: We assume there is an initial set of feature matches represented as a graph G = (V, E), with an associated adjacency matrix A. The graph is constructed from putative correspondences of image features across images, typically constructed using feature descriptor distance (e.g. SIFT feature distance). While there are many interesting methods for computing these putative correspondences (Suh et al., 2015; Yi et al., 2018), we do not explore them in this work. Typically putative correspondences are matched probabilistically, meaning a feature in one image matches to many features in another. The ambiguity in the matches could come from repeated structures in the scene, insufficiently informative low-level feature descriptors, or just an error in the matching algorithm. Filtering out these noisy matches is our primary learning goal.
Each vertex of the graph v ∈ V is an image feature, corresponding to some ground truth 3D point p(v). Each edge e = (v1, v2) ∈ E is a potential correspondence. Associated with each vertex v is an embedding fv ∈ R
m, which can include the visual feature descriptor, position, scale, orientation, etc. Similarly, each edge e has an associated feature fe ∈ R
p (in this work, initially just the weight of the feature association). We use these features as the initialization for our learning algorithm.
In the absence of noise or outliers, this graph would have a connected component for each visible point in the world, all mutually disjoint. Without noise, vertices v would only match with other vertices v′ that correspond to the same 3D point in the scene. Since features in this case represent unique locations in the scene, no points in the same image would have edges e between them. Mathematically, this can be expressed as e = (v1, v2) ∈ E =⇒ P (v1) = P (v2). In the noisy case we expect this structure to be corrupted, i.e. there are some edges e = (v1, v2) ∈ E such that P (v1) 6= P (v2). Thus we need to prune the erroneous edges.
However, standard CNNs cannot operate on this general graph structure. Thus we cannot use standard convolutional nets to learn features for this task. Instead we use graph networks to learn feature representations on this space, which we describe in the next section.

heading: 3.2 GRAPH NEURAL NETWORKS FOR FEATURE MATCHING
text: As input to our method we are given a graph G = (V, E) with the features described in Section 3.1: fv ∀v ∈ V and fe ∀e ∈ E . As with any neural network, GNNs have layered outputs. We describe the output of layer k as f (k) v ∈ Rmk ∀v ∈ V and f (k) e ∈ Rpk ∀e ∈ E , with the initial embeddings denoted f (0) v = fv and f (0) e = fe. To aid future analysis, we will represent the features as matrices, denoting the vertex embedding matrix as F (k) V and the edge embedding matrix as F (k) E . If a superscript is not specified then it refers to the final output of the network.
First we describe older methods of GNNs to give context, then we describe the method we use in this work. Many older methods assume we have the adjacency matrix A of the graph known a-priori Bruna et al. (2013), and can encode graph convolutions using the eigenvectors of A (these are known as spectral methods). However, we do not have this luxury, as the correspondence structure changes from image set to image set, and thus we use non-spectral Graph Neural Networks. Newer models use non-spectral methods, which often ultimately amount to transforming each node with learned weights then averaging each node’s representation with its neighbors, known as a message pass (Kipf & Welling, 2017; Defferrard et al., 2016; Gama et al., 2018b;a). Some works such as Gama et al. use pooling operations on the vertices to make the graph smaller and thus aid computation, but as we need labels on every vertex of the original graph, we cannot use this. Most GNNs used in these works can be expressed mathematically as:
f̃ (k+1)v = σ

b(k) +W k0 f (k) v +
H ∑
h=0
∑
v′∈Nh(v)
fe(v,v′)W k h f (k) v′


The weights/biases W kh , b (k) are all learned, with no learning done on the edge weights fe(v,v′). Note that this is just averages over h-hop neighborhoods, where the weights on the edges remain static through the computation. Given that we are trying to prune edges, we add features over edges to learn which ones to prune and which to keep such as in Scarselli et al. (2009).
In this work we use the method and implementation described in Battaglia et al. (2018). Battaglia et al. (2018) uses message passes between node features as well as edge features, which the model can use to prune unnecessary or erroneous edges. Therefore there is intermediate processing on the edges before information is passed to the vertices.
Mathematically, this is expressed as:
f̃ (k+1) e(v1,v2)
= σ (
a(k) +U (k) 0 f (k) e +U (k) 1 f (k) v1 +U (k) 2 f (k) v2
)
(1)
f̃ (k+1)v = σ

b(k) +W (k) 0 f (k) v +
∑
e∈E(v)
W (k) 1 f (k+1) e

 (2)
Here the learned weights are denoted W and U , and the biases a(k) and b(k). In Battaglia et al. (2018), they allow for more sophisticated aggregation functions, but in this work we simply use the mean function. Each one of these steps we refer to here as a message pass, and it is analogously equivalent to an iteration in a distributed graph based optimization method. Between each of the message passes, we further process the features using MLPs.

heading: 3.3 CYCLE CONSISTENCY
text: Let M be the noiseless set of matches between our features, with Mij being the partial permutation representing the matches between image i and image j. If the pairwise matches are globally consistent, then for all i, j, k:
Mij = MikMkj (3)
In other words, the matches between two images stay the same no matter what path is taken to get there. This constraint is known as cycle consistency, and has been used in a number of works to optimize for global consistency Zhou et al. (2015b); ?); Leonardos et al. (2017). Stated in this form, there are O(n3) cycle consistency constraints to check. A more elegant way to represent cycle
consistency is to first create a ‘universe’ of features that all images match to (see figure 2a). Then, one can match the ith set of features to the universe using a ground-truth matching matrix Xi. Then the cycle consistency constraint becomes:
Mij = XiX ⊤ j (4)
This reduces the number of our constraints from O(n3) to O(n2). This was shown to be equivalent to the original definition of cycle consistency (equation 3) in Huang & Guibas (2013). We try to learn vertex embeddings FV to approximate X - in other words the final embedding should be an encoding of the universe of features. As we do not have the ground truth matches M , we approximate it using the noisy adjacency matrix A of our correspondence graph. Thus our loss would be
L(A,FV ) = D(A,FV F ⊤ V ) (5)
Here D could be an L2 loss, L1 loss, or many others. In this work, we use the L1 loss. Note that because of this formulation, we can determine our embeddings only up to a rotation, as FV R(FV R) ⊤ = FV RR ⊤F⊤V = FV F ⊤ V Thus when visualizing embeddings, we rotate them to make them more interpretable (see figure 2b).

heading: 3.4 GEOMETRIC CONSISTENCY LOSS
text: In order to use geometric information, more traditional optimization based methods require the geometric information at inference time, while with learning approaches we can use it to speed up training while not needing it at inference time. Thus geometric consistency losses are one distinct advantage of our method over more traditional optimization based approaches. We use the epipolar constraint, the simplest way to add a geometric consistency loss. The epipolar constraint describes how the positions of features in different images corresponding to the same point should be related. An illustration of this is provided in figure 3a, showing how this loss can help reject erroneous points. Given a relative pose (Rij , Tij) between two cameras i and j (transforms j to i) the epipolar
constraint on corresponding feature locations Xi and Xj : X ⊤ i [Tij ]×RijXj = 0. In this work we use the two pose epipolar constraint (Tron & Daniilidis, 2014):
X⊤i R ⊤ i [Tj − Ti]×RjXj = 0 (6)
The constraint assumes that the Xk are calibrated (i.e. the camera intrinsics are known). Given our vertex embeddings matrix fv , we can formulate a loss between all cameras i and j (the vertices associated with camera i denoted V(i)):
Lij,geom(FV ) = ∑
v∈V(i),u∈V(j)
(fv · fu) ∣ ∣X⊤v R ⊤ i [Tj − Ti]×RjXu ∣ ∣ (7)
For our purposes, since we use low rank embeddings FV , the loss would read (where c(k) is the appropriate camera for point index k):
Lgeom(FV ) = tr(G ⊤FV F ⊤ V ) =
∑
k,l
(FV )k · (FV )l(G)kl (8)
(G)kl = ∣ ∣ ∣X ⊤ k R ⊤ c(k)[Tc(l) − Tc(k)]×Rc(l)Xl ∣ ∣ ∣

heading: 4 EXPERIMENTS

heading: 4.1 SYNTHETIC GRAPH DATASET
text: We first test our method on synthetically generated data as a simple proof of concept. As these were simpler datasets, we the simpler edge-feature free model of (Kipf & Welling, 2017). To generate the data, we generate p points, each with its own randomly generated descriptor. To create the graph, we generate random permutation matrices, with a noise applied to it after it is generated. We initialize the input descriptors using the synthetically generated ground truth descriptor, plus some added Gaussian noise. No geometric losses were added during training for these experiments. However, the method was robust in testing with different noise functions and parameters. The normalized noisy input descriptors are our baseline - they correlate with the true values but do not preserve the structure well. However, the GNN recovered the true structure very well, as shown in Table 1, showing the appropriate edge similarities. With this simple test on synthetic data passed, we now move to more challenging datasets.

heading: 4.2 ROME 16K GRAPH DATASET
text: We use the Rome16K dataset (Li et al., 2010) to test our algorithm in real world settings. Rome16K consists of 16 thousand images of various historical sites in Rome extracted from Flickr, along with the 3D structure of the sites provided by bundle adjustment. While not a standard dataset to test cycle consistency, most standard datasets have tens or hundreds images, not enough to train a GNN on. Rome16K is typically used to test bundle adjustment methods. Therefore, to use our method, we extract 6-tuples and 10-tuples of images with overlap of 80 points or more to test our algorithm, with the points established as corresponding in the given bundle adjustment output. For the initial embedding we use the original 128 dimensional SIFT descriptors, normalized to have unit L2 norm,
the calibrated x-y position, the orientation, and log scale of the SIFT feature. To calibrate we use the focal lengths provided in Rome16K’s data, and we assume the image center is in the center of the image (as none is provided by Rome16K). To construct the graph, we take each feature as a vertex and create edges to the 5 nearest SIFT descriptors for the other images.
For these experiments we train with the L1 norm and geometric consistency losses. We evaluate on a test set using the ground truth adjacency matrix, which we compute from the bundle adjustment given by the Rome16K dataset. However, we do not train with the ground truth adjacency matrix, only with a noisy version of the adjacency matrix. We also add the geometric loss (8) which helps improve testing performance (see figure 3b). We use the L1 and ROC AUC metrics to measure performance. For this method to work, we need the dimension of the embedding to be at least the number of unique points in the scene. Picking the correct number is difficult a-priori, and is a problem with all cycle consistency based methods. Here we use the ground truth dimension of the embedding to test both our method and the baselines.
The network was implemented using the code provided by Battaglia et al. (2018) using Tensorflow 1.11 (Abadi et al., 2015). Our network has 16 layers, with 8 message passing operations placed every other layer. All layers were simple Multi-layer Perceptrons, with no batch norm. The network was trained with the Adam optimizer (Kingma & Ba, 2014) with a learning rate of 10−4, with an exponentially decaying learning rate. We incorporate skip connections between the input, 6th, and 12th layers (all possible pairs).
We compare our method to spectral and optimization based baselines with different maximum iteration cutoffs. Figure 4 illustrates this by plotting the means of various metrics and their 25th and 75th percentiles, with table 2 giving the exact numbers. Our network, though only using 8 message passes, has comparable accuracy to MatchALS (Zhou et al., 2015b) run 35 to 45 iterations, with an equivalent message passing step at each phase. Although our method does not outperform the Projected Gradient Descent - Doubly Stochastic (PGDDS) (Leonardos et al., 2017) method, we perform comparably to them in the ROC AUC metric.

heading: 4.2.1 GRAFFITI DATASET
text: We run our trained model on the more Graffiti Dataset from the Affine Covariant Regions dataset (formatted to be able to be input to our model properly). The Graffiti Dataset is the most common benchmark used in feature matching algorithms (e.g. Leonardos et al. (2017); Zhou et al. (2015b)). The results are shown in figure 4 in the rightmost figure. As the graffiti dataset is very small (only 6 views total), we were not able to train on it. We randomly permute the intra-image order of the features to add some variance - by design the GNN outputs the same result each time, while the optimization methods have a very small amount of variance. The transferred results of Graffiti are similar to the test error of Rome16K - smaller L1 error and comparable ROC error. This shows that the GNNs trained in Rome16K generalize similarly to the optimization based methods.

heading: 5 CONCLUSION
text: We have shown a novel method for training feature matching using GNNs, using an unsupervised cycle consistency loss and geometric consistency losses. We have demonstrated end-to-end trainable GNNs have comparable performance the traditional optimization-based baselines. For future work, we will investigate robust losses for better outlier rejection, and using higher order geometric constraints, such as the tri-focal tensor, as additional loss terms. With this new architecture, we have the capability of training multi-image matching pipelines end to end, thus allowing us to train for image features explicitly for this task. We can extend this to distributed settings where we can train for matching images from multiple distributed agents.

heading: A MORE DETAIL ON GNN ARCHITECTURE
text: All experiments were run with a 12 layer GNN with the ReLU nonlinearity and skip connections. The feature vector lengths were 32, 64, 128, 256, 512, 512, 512, 512, 512, 512, 1024, 1024, with skip connections between layers 1 and 6, 6 and 12, and 1 and 12. All were trained with the Adam optimizer (Kingma & Ba, 2014) and a learning rate 10−4 The network was implemented in Tensorflow (Abadi et al., 2015), version 1.11.

heading: B COMPUTING GEOMETRIC LOSS
text: To compute the Geometric Loss during training we use the given rotations and translations from Rome16K to compute the relative poses. In practice, one could just use the relative poses computed. We build up an intermediate Essential Matrix representations P,Q ∈ R3pv×3, with v being the number of views and p being the number of points. The matrix P is defined by the block matrix representation Pi = [Tc(i)]×Rc(i)Xi. The matrix Q is defined by the block matrix representation Qi = Rc(i)Xi. We build the Essential matrices using E = Q ⊤P +P⊤Q, which has 3 by 3 blocks
Eij = (Rc(i)Xi) ⊤[Tc(j)]×Rc(j)Xj + ([Tc(i)]×Rc(i)Xi) ⊤Rc(j)Xj
= X⊤i R ⊤ c(i)[Tc(j)]×Rc(j)Xj −X ⊤ i R ⊤ c(i)[Tc(i)]×Rc(j)Xj
= X⊤i R ⊤ c(i)[Tc(j) − Tc(i)]×Rc(j)Xj
Note that this is the same as equation 6 and thus we have our relative pariwise constraints.

Review summaries:
This paper proposes a multi-image matching method using a GNN with cyclic and geometric losses. The authors use vertex embeddings to exploit cycle consistency constraints in an efficient manner, then the GNN is used to learn the appropriate embeddings in an unsupervised fashion. The geometric consistency loss is used to aid training in addition. Experimental evaluation shows its performance compared to MatchALS (Zhou et al., 2015) and PGDDS (Leonardos et al., 2016).