Ignacio Rocco
email: ignacio.rocco@inria.fr

Relja Arandjelovic

Josef Sivic
email: josef.sivic@inria.fr

Relja Arandjelović

Convolutional neural network architecture for geometric matching

Keywords: Convolutional neural network, geometric matching, image alignment, category-level matching. !

come

INTRODUCTION

E STIMATING correspondences between images is one of the fundamental problems in computer vision [START_REF] Forsyth | Computer vision: a modern approach[END_REF], [START_REF] Hartley | Multiple view geometry in computer vision[END_REF] with applications ranging from large-scale 3-D reconstruction [START_REF] Agarwal | Building Rome in a day[END_REF] to image manipulation [START_REF] Hacohen | Nonrigid dense correspondence with applications for image enhancement[END_REF] and semantic segmentation [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF]. Traditionally, correspondences consistent with a geometric model such as epipolar geometry or planar affine transformation, are computed by detecting and matching local features (such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] or HOG [START_REF] Dalal | Histogram of Oriented Gradients for Human Detection[END_REF], [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF]), followed by pruning incorrect matches using local geometric constraints [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF], [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] and robust estimation of a global geometric transformation using algorithms such as RANSAC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] or Hough transform [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], [START_REF] Lamdan | Object recognition by affine invariant matching[END_REF], [START_REF] Leibe | Robust object detection with interleaved categorization and segmentation[END_REF]. This approach works well in many cases but fails in situations that exhibit (i) large changes of depicted appearance due to e.g. intra-class variation [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF], or (ii) large changes of scene layout or non-rigid deformations that require complex geometric models with many parameters which are hard to estimate in a manner robust to outliers.

In this work we build on the traditional approach and develop a convolutional neural network (CNN) architecture that mimics the standard matching process. First, we replace the standard local features with powerful trainable convolutional neural network features [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF], [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF], which allows us to handle large changes of appearance between the matched images. Second, we develop trainable matching and transformation estimation layers that can cope with noisy and incorrect matches in a robust way, mimicking the good practices in feature matching such as the second nearest neighbor test [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], neighborhood consensus [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF], [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] and Hough transform-like estimation [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], [START_REF] Lamdan | Object recognition by affine invariant matching[END_REF], [START_REF] Leibe | Robust object detection with interleaved categorization and segmentation[END_REF].

The outcome is a convolutional neural network architecture trainable for the end task of geometric matching, which can handle large appearance changes, and is therefore suitable for both instance-level and category-level matching problems. The contributions of this work are three-fold. First, we propose a convolutional neural network architecture for geometric matching, which mimics the standard steps of feature extraction, matching and simultaneous inlier detection and model parameter estimation, while being trainable end-to-end. Second, we demonstrate that the network parameters can be trained from synthetically generated imagery without the need for manual annotation and that our matching layer significantly increases generalization capabilities to never seen before images. Finally, we show that the same model can give state-of-the-art results on several challenging datasets for category-level image alignment.

All training and evaluation code, as well as our trained networks, is available online [16].

RELATED WORK

The classical approach for finding correspondences involves identifying interest points and computing local descriptors around these points [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF], [START_REF] Harris | A combined corner and edge detector[END_REF], [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF], [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF], [START_REF] Berg | Shape matching and object recognition using low distortion correspondence[END_REF], [START_REF] Bay | Surf: Speeded up robust features[END_REF]. While this approach performs relatively well for instance-level matching, the feature detectors and descriptors lack the generalization ability for category-level matching.

Recently, convolutional neural networks have been used to learn powerful feature descriptors which are more robust to appearance changes than the classical descriptors [START_REF] Jahrer | Learned local descriptors for recognition and matching[END_REF], [START_REF] Simo-Serra | Discriminative learning of deep convolutional feature point descriptors[END_REF], [START_REF] Han | MatchNet: Unifying feature and metric learning for patch-based matching[END_REF], [START_REF] Zagoruyko | Learning to compare image patches via convolutional neural networks[END_REF], [START_REF] Balntas | PN-Net: Conjoined triple deep network for learning local image descriptors[END_REF], [START_REF] Noh | Large-scale image retrieval with attentive deep local features[END_REF]. However, these works are focused on learning descriptors [START_REF] Jahrer | Learned local descriptors for recognition and matching[END_REF], [START_REF] Simo-Serra | Discriminative learning of deep convolutional feature point descriptors[END_REF], [START_REF] Balntas | PN-Net: Conjoined triple deep network for learning local image descriptors[END_REF], [START_REF] Noh | Large-scale image retrieval with attentive deep local features[END_REF], or a similarity measure between descriptors [START_REF] Han | MatchNet: Unifying feature and metric learning for patch-based matching[END_REF], [START_REF] Zagoruyko | Learning to compare image patches via convolutional neural networks[END_REF], [START_REF] Altwaijry | Learning to match aerial images with deep attentive architectures[END_REF], and do not target the problem of finding the transformation relating the two input images. In this work, we go a step further from CNN descriptors, and seek to also learn to estimate the geometric transformation.

Related are also network architectures for estimating interframe motion in video [START_REF] Weinzaepfel | DeepFlow: Large displacement optical flow with deep matching[END_REF], [START_REF] Fischer | FlowNet: Learning optical flow with convolutional networks[END_REF], [START_REF] Thewlis | Fully-trainable deep matching[END_REF] or instance-level homography estimation [START_REF] Detone | Deep image homography estimation[END_REF], however their goal is very different from ours, targeting high-precision correspondence with very limited appearance variation and background clutter. Closer to us is the network architecture of [START_REF] Kanazawa | WarpNet: Weakly supervised matching for single-view reconstruction[END_REF] which, however, tackles a different problem of fine-grained category-level matching (different species of birds) with limited background clutter and small translations and scale changes, as their objects are largely centered in the image. In addition, their architecture is based on a different matching layer, which we show not to perform as well as the matching layer used in our work.

Some works, such as [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF], [START_REF] Berg | Shape matching and object recognition using low distortion correspondence[END_REF], [START_REF] Liu | SIFT Flow: Dense correspondence across scenes and its applications[END_REF], [START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF], [START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF], [START_REF] Long | Do convnets learn correspondence?[END_REF], have addressed the hard problem of category-level matching, but rely on traditional non-trainable optimization for matching [START_REF] Berg | Shape matching and object recognition using low distortion correspondence[END_REF], [START_REF] Liu | SIFT Flow: Dense correspondence across scenes and its applications[END_REF], [START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF], [START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF], [START_REF] Long | Do convnets learn correspondence?[END_REF], or guide the matching using object proposals [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF]. On the contrary, our approach is fully trainable in an endto-end manner and does not require any optimization procedure at evaluation time, or guidance by object proposals.

Others [START_REF] Learned-Miller | Data driven image models through continuous joint alignment[END_REF], [START_REF] Shokrollahi Yancheshmeh | Unsupervised visual alignment with similarity graphs[END_REF], [START_REF] Zhou | FlowWeb: Joint image set alignment by weaving consistent, pixel-wise correspondences[END_REF] have addressed the problems of instance and category-level correspondence by performing joint image alignment. However, these methods differ from ours as they: (i) require class labels; (ii) don't use CNN features; (iii) jointly align a large set of images, while we align image pairs; and (iv) don't use a trainable CNN architecture for alignment as we do.

ARCHITECTURE FOR GEOMETRIC MATCHING

In this section, we introduce a new convolutional neural network architecture for estimating parameters of a geometric transformation between two input images. The architecture is designed to mimic the classical computer vision pipeline (e.g. [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]), while using differentiable modules so that it is trainable end-to-end for the geometry estimation task. The classical approach consists of the following stages: (i) local descriptors (e.g. SIFT) are extracted from both input images, (ii) the descriptors are matched across images to form a set of tentative correspondences, which are then used to (iii) robustly estimate the parameters of the geometric model using RANSAC or Hough voting.

Our architecture, illustrated in Fig. 2, mimics this process by: (i) passing input images I A and I B through a siamese architecture consisting of convolutional layers, thus extracting feature maps f A and f B which are analogous to dense local descriptors, (ii) matching the feature maps ("descriptors") across images into a tentative correspondence map f AB , followed by a (iii) regression network which directly outputs the parameters of the geometric model, θ, in a robust manner. The inputs to the network are the two images, and the outputs are the parameters of the chosen geometric model, e.g. a 6-D vector for an affine transformation.

In the following, we describe each of the three stages in detail.

Feature extraction

The first stage of the pipeline is feature extraction, for which we use a standard CNN architecture. A CNN without fully connected layers takes an input image and produces a feature map f ∈ R h×w×d , which can be interpreted as a h × w dense spatial grid of d-dimensional local descriptors. A similar interpretation has been used previously in instance retrieval [START_REF] Azizpour | Factors of transferability from a generic ConvNet representation[END_REF], [START_REF] Babenko | Aggregating local deep features for image retrieval[END_REF], [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF], [START_REF] Arandjelović | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF] demonstrating high discriminative power of CNNbased descriptors. Thus, for feature extraction we use the VGG-16 network [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF], cropped at the pool4 layer (before the ReLU unit), followed by per-feature L2-normalization. We use a pre-trained model, originally trained on ImageNet [START_REF] Deng | ImageNet: A large-scale hierarchical image database[END_REF] for the task of image classification. As shown in Fig. 2, the feature extraction network is duplicated and arranged in a siamese configuration such that the two input images are passed through two identical networks which share parameters.

Matching network

The image features produced by the feature extraction networks should be combined into a single tensor as input to the regressor network to estimate the geometric transformation. We first describe the classical approach for generating tentative correspondences, and then present our matching layer which mimics this process.

Tentative matches in classical geometry estimation

Classical methods start by computing similarities between all pairs of descriptors across the two images. From this point on, the original descriptors are discarded as all the necessary information for geometry estimation is contained in the pairwise descriptor similarities and their spatial locations. Secondly, the pairs are pruned by either thresholding the similarity values, or, more commonly, only keeping the matches which involve the nearest (most similar) neighbors. Furthermore, the second nearest neighbor test [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] prunes the matches further by requiring that the match strength is significantly stronger than the second best match involving the same descriptor, which is very effective at discarding ambiguous matches.

Matching layer

Our matching layer applies a similar procedure. Analogously to the classical approach, only descriptor similarities and their spatial locations should be considered for geometry estimation, and not the original descriptors themselves.

To achieve this, we propose to use a correlation layer followed by normalization. Firstly, all pairs of similarities between descriptors are computed in the correlation layer. Secondly, similarity scores are processed and normalized such that ambiguous matches are strongly down-weighted.

In more detail, given L2-normalized dense feature maps f A , f B ∈ R h×w×d , the correlation map c AB ∈ R h×w×(h×w) outputted by the correlation layer contains at each position the scalar product of a pair of individual descriptors f A ∈ f A and f B ∈ f B , as detailed in Eq. [START_REF] Forsyth | Computer vision: a modern approach[END_REF].

c AB (i, j, k) = f B (i, j) T f A (i k , j k ) (1)
where (i, j) and (i k , j k ) indicate the individual feature positions in the h × w dense feature maps, and k = h(j k -1) + i k is an auxiliary indexing variable for (i k , j k ).

A diagram of the correlation layer is presented in Fig. 3. Note that at a particular position (i, j), the correlation map c AB contains the similarities between f B at that position and all the features of f A .

As is done in the classical methods for tentative correspondence estimation, it is important to postprocess the pairwise similarity scores to remove ambiguous matches. To this end, we apply a channel-wise normalization of the correlation map at each spatial location to produce the final tentative correspondence map f AB . The normalization is performed by ReLU, to zero out negative correlations, followed by L2-normalization, which has two desirable effects. First, let us consider the case when descriptor f B correlates well with only a single feature in f A . In this case, the normalization will amplify the score of the match, akin to the nearest neighbor matching in classical geometry estimation. Second, in the case of the descriptor f B matching multiple features in f A due to the existence of clutter or repetitive patterns, matching scores will be down-weighted similarly to the second nearest neighbor test [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. However, note that both the correlation and the normalization operations are differentiable with respect to the input descriptors, which facilitates backpropagation thus enabling end-to-end learning.

Discussion

The first step of our matching layer, namely the correlation layer, is somewhat similar to layers used in DeepMatching [START_REF] Weinzaepfel | DeepFlow: Large displacement optical flow with deep matching[END_REF] and FlowNet [START_REF] Fischer | FlowNet: Learning optical flow with convolutional networks[END_REF]. However, DeepMatching [START_REF] Weinzaepfel | DeepFlow: Large displacement optical flow with deep matching[END_REF] only uses deep RGB patches and no part of their architecture is trainable. FlowNet [START_REF] Fischer | FlowNet: Learning optical flow with convolutional networks[END_REF] uses a spatially constrained correlation layer such that similarities are are only computed in a restricted spatial neighborhood thus limiting the range of geometric transformations that can be captured. This is acceptable for their task of learning to estimate optical flow, but is inappropriate for larger transformations that we consider in this work. Furthermore, neither of these methods performs score normalization, which we find to be crucial in dealing with cluttered scenes.

Previous works have used other matching layers to combine descriptors across images, namely simple concatenation of descriptors along the channel dimension [START_REF] Detone | Deep image homography estimation[END_REF] or subtraction [START_REF] Kanazawa | WarpNet: Weakly supervised matching for single-view reconstruction[END_REF]. However, these approaches suffer from two problems. First, as following layers are typically convolutional, these methods also struggle to handle large transformations as they are unable to detect long-range matches. Second, when concatenating or subtracting descriptors, instead of computing pairwise descriptor similarities as is commonly done in classical geometry estimation and mimicked by the correlation layer, image content information is directly outputted. To further illustrate why this can be problematic, consider two pairs of images that are related with the same geometric transformation -the concatenation and subtraction strategies will produce different outputs for the two cases, making it hard for the regressor to deduce the geometric transformation. In contrast, the correlation layer output is likely to produce similar correlation maps for the two cases, regardless of the image content, thus simplifying the problem for the regressor. In line with this intuition, in Sec. 7.3 we show that the concatenation and subtraction methods indeed have difficulties generalizing beyond the training set, while our correlation layer achieves generalization yielding superior results.

Regression network

The normalized correlation map is passed through a regression network which directly estimates parameters of the geometric transformation relating the two input images. In classical geometry estimation, this step consists of robustly estimating the transformation from the list of tentative correspondences. Local geometric constraints are often used to further prune the list of tentative matches [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF], [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] by only retaining matches which are consistent with other matches in their spatial neighborhood. Final geometry estimation is done by RANSAC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] or Hough voting [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], [START_REF] Lamdan | Object recognition by affine invariant matching[END_REF], [START_REF] Leibe | Robust object detection with interleaved categorization and segmentation[END_REF].

We again mimic the classical approach using a neural network, where we stack two blocks of convolutional layers, followed by batch normalization [START_REF] Ioffe | Batch Normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] and the ReLU non-linearity, and add a final fully connected layer which regresses to the parameters of the transformation, as shown in Fig. 4. The intuition behind this architecture is that the estimation is performed in a bottom-up manner

f AB conv1 BN1 ReLU1 conv2 BN2 ReLU2 FC 7×7×225×128 5×5×128×64 5×5×64×P
Fig. 4. Architecture of the regression network. It is composed of two convolutional layers without padding and stride equal to 1, followed by batch normalization and ReLU, and a final fully connected layer which regresses to the P transformation parameters.

somewhat like Hough voting, where early convolutional layers vote for candidate transformations, and these are then processed by the later layers to aggregate the votes. The first convolutional layers can also enforce local neighborhood consensus [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF], [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] by learning filters which only fire if nearby descriptors in image A are matched to nearby descriptors in image B, and we show qualitative evidence in Sec. 7.5 that this indeed does happen.

Discussion

A potential alternative to a convolutional regression network is to use fully connected layers. However, as the input correlation map size is quadratic in the number of image features, such a network would be hard to train due to a large number of parameters that would need to be learned, and it would not be scalable due to occupying too much memory and being too slow to use. It should be noted that even though the layers in our architecture are convolutional, the regressor can learn to estimate large transformations. This is because one spatial location in the correlation map contains similarity scores between the corresponding feature in image B and all the features in image A (c.f. equation ( 1)), and not just the local neighborhood as in [START_REF] Fischer | FlowNet: Learning optical flow with convolutional networks[END_REF].

GEOMETRIC TRANSFORMATIONS

Three different parametric geometric transformations were employed in this work: affine, homography and thin-plate spline. The details of their parametrizations are presented next. As images are warped using the reverse mapping, the transformations map coordinates from the target image B to the source image A.

Affine transformation

An affine transformation is a 6 degree-of-freedom linear transformation capable of modeling translation, rotation, non-isotropic scaling and shear. It can be parametrized by a 6 dimensional vector θ AFF :

θ AFF = [a 11 , a 12 , a 21 , a 22 , t x , t y ], (2)
such that points P B = [x B , y B ] T are mapped to points P A = [x A , y A ] T according to:

P A = a 11 a 12 a 21 a 22 P B + t x t y . (3)

Homography transformation

A homography transformation deforms a given quadrilateral (pinhole projections) of a 3-D plane. We adopt the 4-point homography parametrization from [START_REF] Detone | Deep image homography estimation[END_REF], which consists of defining the quadrilateral Q B of the target image to be the outer edge of the image, and using the coordinates of the quadrilateral Q A of the source image as the 8-dimensional vector θ HOM :

Q B = {Q B1 , . . . , Q B4 } into any other given quadrilateral Q A = {Q A1 , . . . , Q A4 },
θ HOM = [x Q A1 , . . . , x Q A4 , y Q A1 , . . . , y Q A4 ]. (4)
This parametrization can be converted to the 3×3 homography matrix H [START_REF] Hartley | Multiple view geometry in computer vision[END_REF], which is used to perform the actual transformation:

x A = h 11 x B + h 12 y B + h 13 h 31 x B + h 32 y B + h 33 , y A = h 21 x B + h 22 y B + h 23 h 31 x B + h 32 y B + h 33 , (5)
where, h ij are elements of the homography matrix H.

Thin-plate spline transformation

The thin-plate spline (TPS) transformation [START_REF] Bookstein | Principal warps: Thin-plate splines and the decomposition of deformations[END_REF]

θ TPS = [x C A1 , . . . , x C A9 , y C A1 , . . . , y C A9 ]. (6)
Then, the thin-plate spline transformation maps points

P B = [x B , y B ] T to points P A = [x A , y A ] T according to: x A = a x + b x x B + c x y B + k i=1 w xi U ( P B -C Bi ), y A = a y + b y x B + c y y B + k i=1 w yi U ( P B -C Bi ). (7)
Here, U (z) = z 2 log z 2 and the parameters a, b, c and w are computed from θ TPS by:

[w x1 , . . . , w xk , a x , b x , c x ] T = L -1 [x C A1 , . . . , x C Ak , 0, 0, 0] T [w y1 , . . . , w yk , a y , b y , c y ] T = L -1 [y C A1 , . . . , y C Ak , 0, 0, 0] T , (8)
where L -1 is a constant matrix which needs to be computed only once, as it depends only on the fixed control points C B . Please refer to [START_REF] Bookstein | Principal warps: Thin-plate splines and the decomposition of deformations[END_REF] for further details. . Estimating progressively more complex geometric transformations. Images A and B are passed through a network which estimates an affine transformation with parameters θ AFF (see Fig. 2). Image A is then warped using this transformation to roughly align it with B, and passed along with B through a second network which estimates a thin-plate spline (TPS) transformation that refines the alignment.

Hierarchy of transformations

A commonly used approach when estimating image to image transformations is to start by estimating a simple transformation and then progressively increase the model complexity, refining the estimates along the way [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF], [START_REF] Berg | Shape matching and object recognition using low distortion correspondence[END_REF], [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. The motivation behind this method is that estimating a very complex transformation could be hard and computationally inefficient in the presence of clutter, so a robust and fast rough estimate of a simpler transformation can be used as a starting point, also regularizing the subsequent estimation of the more complex transformation. We follow the same good practice and start by estimating an affine transformation (or alternatively a homography) which performs a rough alignment. The estimated affine transformation is then used to align image A to image B using an image resampling layer [START_REF] Jaderberg | Spatial Transformer Networks[END_REF]. The aligned images are then passed through a second geometry estimation network which estimates the parameters of a thin-plate spline transformation. The final estimate of the geometric transformation is then obtained by composing the two transformations. The process is illustrated in Fig. 6, and detailed in Algorithm 2.

Iterative refinement

When input images are related by a large transformation, it is difficult to obtain many good matches, so a single pass through the geometry estimation network might produce a poor alignment. In such cases, performing several iterations of the estimation can be beneficial, as illustrated in Fig. 7, since it allows the number of matches to progressively grow. This approach has proven to be particularly useful for instance-level alignment, as detailed in section 6.4.

TRAINING

In order to train the parameters of our geometric matching CNN, it is necessary to design the appropriate loss function, and to use suitable training data. We address these two important points next, and also provide details about the implementation.

Loss function

We assume a fully supervised setting, where the training data consists of pairs of images and the desired outputs in the form of the parameters θ GT of the ground-truth geometric transformation. The loss function L is designed to compare the estimated transformation θ with the ground-truth transformation θ GT and, more importantly, compute the gradient of the loss function with respect is initialized to identity). A fine alignment, θ (i) , between image B and the warped image A is estimated and chained onto θ to the estimates ∂L ∂θ . This gradient is then used in a standard manner to learn the network parameters which minimize the loss function by using backpropagation and Stochastic Gradient Descent.

It is desired for the loss to be general and not specific to a particular type of geometric model, so that it can be used for estimating affine, homography, thin-plate spline or any other geometric transformation. Furthermore, the loss should be independent of the parametrization of the transformation and thus should not directly operate on the parameter values themselves. We address all these design constraints by measuring loss on an imaginary grid of points G = {G i } = {(x i , y i )} i=1...N which is being deformed by the transformation. Namely, we construct a grid of points in image space, transform it using the neural network estimated and ground-truth transformations T θ and T θ GT with parameters θ and θ GT , respectively, and measure the discrepancy between the two transformed grids by summing the squared distances between the corresponding grid points:

L(θ, θ GT ) = 1 N N i=1 G i -G i 2 (9)
where

G i = T θ (G i ) and G i = T θ GT (G i
) are the transformed grid points according to the estimated and ground-truth transformations respectively. The grid points are uniformly distributed in the image using normalized coordinates, i.e.

x i , y i ∈ [-1, 1].
Note that we construct the coordinate system such that the center of the image is at (0, 0) and that the width and height of the The gradient of the loss function with respect to the transformation parameters, needed to perform backpropagation in order to learn network weights, can be computed easily if the location of the transformed grid points G i = T θ (G i ) is differentiable with respect to θ. This is commonly the case, for example, when T is an affine transformation, T θ (G i ) is linear in parameters θ and therefore the loss can be differentiated in a straightforward manner.

Training data

Our training procedure requires fully supervised training data consisting of image pairs and a known geometric relation. Training CNNs usually requires a lot of data, and no public datasets exist that contain many image pairs annotated with their geometric transformation. Therefore, we opt for training from synthetically generated data, which gives us the to gather as many training examples as needed, for any 2-D geometric transformation of interest. Given that this training data is obtained for free, the approach can be classified as unsupervised (or self-supervised), even though the loss function requires the ground-truth transformation parameters.

Synthetic pair generation

We generate each training pair (I A , I B ), by sampling I A from a public image dataset, and generating I B by applying a random transformation T θ GT to I A . More precisely, I A is created from the central crop of the original image, while I B is created by transforming the original image with added symmetrical padding in order to avoid border artifacts; the procedure is shown in Fig. 8.

Synthetic training datasets

The images used for the synthetic pair generation are sampled from the Tokyo Time Machine dataset [START_REF] Arandjelović | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF] which contains Google StreetView images of Tokyo. We select 20k images for training and 20k for validation.

During training, a batch is first selected from the training split of the dataset, and then a random transformation for each image in the batch is sampled independently from reasonable ranges. These ranges depend on the geometric model chosen for training the network.

In the case of the affine transformation, we chose a rotation angle θ ∼ U (-π/12, π/12), a shear angle φ ∼ U (-π/6, π/6), anisotropic scaling factors λ 1 , λ 2 ∼ U (0.75, 1.25), and translations t x , t y ∼ U (-0.25, 0.25). These parameters are defined on the SVD decomposition of the affine transformation (see [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]

a 11 a 12 a 21 a 22 = R(θ)R(-φ)diag(λ 1 , λ 2 )R(φ). (10)
In the case of the homography and thin-plate spline transformations, the target points Q A and C A are obtained by perturbing the fixed Q B and C B with random translations δ x , δ y ∼ U (-0.4, 0.4):

Q Ai = Q Bi + (δ x , δ y ), C Ai = C Bi + (δ x , δ y ). (11)
In all cases, the uniform distribution was used in order not to impose a strong prior on the transformation parameters. The ranges were chosen to roughly cover the observed transformations in the PF-WILLOW dataset.

Implementation details

We use the PyTorch library [START_REF]PyTorch[END_REF] and train the networks using the Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] optimizer with learning rate 10 -3 , and a batch size of 16. There is no need for jittering as instead of data augmentation we can simply generate more synthetic training data. Input images are resized to 240 × 240 producing 15 × 15 feature maps that are passed into the matching layer. Single-stage models specific for each particular geometric transformation (affine, homography or thin-plate spline) are trained, with transformations sampled randomly at training time according to the previously described procedure. Each network is trained until convergence which typically occurs after 20 epochs (25000 iterations), and takes between 4 and 8 hours on a single GPU, depending on the complexity of the geometric model. The training algorithm is detailed in Algorithm 1.

At evaluation time, the single-stage models featuring different geometric transformations can be used in conjunction as illustrated in Fig. 6. Trained networks can also be executed iteratively as described in section 4.5 and illustrated in Fig. 7. The evaluation algorithm is detailed in Algorithm 2.

EXPERIMENTAL RESULTS

In this section we compare our method to baselines and the stateof-the-art for both category-level and instance-level alignment problems.

In the case of category-level alignment, both qualitative and quantitative evaluation is performed on three different datasets previously used for this task: the PF dataset [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF], the TSS dataset [START_REF] Taniai | Joint recovery of dense correspondence and cosegmentation in two images[END_REF] and the Caltech-101 dataset [START_REF] Fei-Fei | One-shot learning of object categories[END_REF].

In the case of instance-level alignment, qualitative and quantitative evaluation is performed on the Graffiti benchmark [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF]. In addition, qualitative alignment results are presented for the Tokyo Time Machine dataset [START_REF] Arandjelović | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF].

A different single-stage model for each of the affine, homography and thin-plate spline transformations was trained independently. Both single-stage (Fig. 2) and two-stage (Fig. 6) alignment strategies were investigated. Furthermore, the iterative refinement procedure described in section 7 was used for the Graffiti benchmark.

PF dataset

This dataset contains image pairs depicting different instances of the same classes, such as ducks and cars, but with large intraclass variations, e.g. the cars are often of different make, or the ducks can be of different subspecies. Furthermore, the images contain significant background clutter, as can be seen in Fig. 9. It contains a total of 2251 image pairs from two subgroups: PF-WILLOW (900 pairs, introduced in [START_REF] Ham | Proposal Flow[END_REF]) and PF-PASCAL (1251 pairs, introduced in [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF]). Images from each pair were manually selected to ensure that objects have similar poses.

Evaluation metric

The quality of the obtained alignment is assessed by exploiting the keypoint annotation provided with the PF dataset. The task is to predict the locations of predefined keypoints from image A in image B. We do so by estimating a geometric transformation T that warps image A into image B, and applying the same transformation to the keypoint locations P A = {P i A } i=1,...,n in I A , to obtain the estimated keypoint locations {T (P i A )} i=1,...,n in I B . The alignment quality is then computed using the standard evaluation metric for this benchmark, the average probability of correct keypoint (PCK) [START_REF] Yang | Articulated human detection with flexible mixtures of parts[END_REF], being the proportion of keypoints that are correctly matched. A keypoint is considered to be matched correctly if the distance between its predicted location T (P i A ) and its ground-truth position P i B is below a predefined threshold L. Therefore, the PCK is computed as follows:

TABLE 1 Matching accuracy on the PF dataset (PF-PASCAL/PF-WILLOW) measured in terms of the PCK (α = 0.1). All the numbers apart from ours and RANSAC are taken from [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF].

Methods

PF-PASCAL PF-WILLOW

DeepFlow [START_REF] Revaud | DeepMatching: Hierarchical deformable dense matching[END_REF] 0.21 0.20 GMK [START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF] 0.27 0.27 SIFT Flow [START_REF] Liu | SIFT Flow: Dense correspondence across scenes and its applications[END_REF] 0.33 0.38 DSP [START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF] 0.30 0.37 Proposal Flow (SS+NAM) [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF] 0.36 0.52 Proposal Flow (SS+PHM) [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF] 0.42 0.55 Proposal Flow (SS+LOM) [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF] 0

PCK = |{P i A ∈ P A , d(T (P i A ), P i B ) < L}| n , (12)
where the distance threshold is L = α • max(h, w), α = 0.1 and (h, w) are the height and width of the object bounding box, respectively.

Results

We compare our method against SIFT Flow [START_REF] Liu | SIFT Flow: Dense correspondence across scenes and its applications[END_REF], Graph-matching kernels (GMK) [START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF], Deformable spatial pyramid matching (DSP) [START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF], DeepFlow [START_REF] Revaud | DeepMatching: Hierarchical deformable dense matching[END_REF], and all three variants of Proposal Flow (NAM, PHM, LOM) [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF]. As shown in Tab. 1, our method outperforms all others and sets the new state-of-the-art on this data. The best competing methods are based on Proposal Flow and make use of object proposals, which enables them to guide the matching towards regions of images that contain objects. Their performance varies significantly with the choice of the object proposal method, illustrating the importance of this guided matching. On the contrary, our method does not use any guiding, but it still manages to outperform even the best Proposal Flow and object proposal combination. Furthermore, we also compare to affine transformations estimated with RANSAC using the same descriptors as our method (VGG-16 pool4). The parameters of this baseline have been tuned extensively to obtain the best result by adjusting the thresholds for the second nearest neighbor test and by pruning proposal transformations which are outside of the range of likely transformations. Our affine estimator outperforms the RANSAC baseline on this task by a 2% margin.

Fig. 9 illustrates the effectiveness of our method in categorylevel matching, where challenging pairs of images from the Proposal Flow dataset [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF], containing large intra-class variations, are aligned correctly. The method is able to robustly, in the presence of clutter, estimate large translations, rotations, scale changes, as well as non-rigid transformations and some perspective changes.

TSS dataset

The TSS dataset introduced in [ contains 124 image pairs of bicycles, motorbikes, buses, cars and trains. For all 400 image pairs, approximate ground-truth optical flow data is provided.

Evaluation metric

The evaluation metric used for the TSS dataset is also the PCK, presented in Eq. ( 12), previously presented for the PF dataset. However, the ground-truth optical flow data available in the TSS dataset allows to compute the PCK using a dense set of keypoints

P A = {P i A ∈ M A } i=1,.
..,n , composed by the foreground pixels inside the segmentation mask M A of the object in I A . Therefore, this allows for the alignment to be densely evaluated over the object of interest, in contrast to the PCK computation for the PF dataset, where the alignment is only evaluated in a handful of manually annotated keypoints.

Regarding the distance threshold L = α • max(h, w) used for the PCK computation, the criterion used in [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF], [START_REF] Taniai | Joint recovery of dense correspondence and cosegmentation in two images[END_REF] is adopted, where the reported values are computed with α = 0.05 and with (h, w) being the dimensions of the target image.

Results

The quantitative results for the TSS dataset are presented in Tab. 2, in terms of the mean PCK over the set of image pairs. For each of the 400 pairs, both the forward (from I A to I B ) and backward (from I B to I A ) alignments are computed an evaluated, resulting in a total of 800 evaluation pairs.

The middle columns of Tab. 2 present mean PCK over the three subsets of the TSS dataset: FG3DCar, JODS and PASCAL; and the right-most column presents the mean PCK over the whole TSS dataset. It can be observed that our single-stage models improve the overall average score by up to 3%, while the two-stage models achieve the best results on all the different subsets, and improve by up to 7% over the previously published results.

In Fig. 10 we present qualitative results on the TSS dataset. In order to assess the visual quality of the obtained results, we also present the ground-truth aligned and segmented images provided with the dataset in the right-most column.

As it can be observed, the proposed method can produce good alignments results, which are close to the ground-truth alignment.

Caltech-101 dataset

Following the same procedure as in [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF], [START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF], the alignment quality is also evaluated on the Caltech-101 dataset [START_REF] Fei-Fei | One-shot learning of object categories[END_REF]. For each of the 101 categories, 15 image pairs were chosen randomly, resulting in 1515 evaluation pairs. These pairs are the same as in [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF].

Evaluation metrics

As no keypoint annotations are provided for the Caltech-101 dataset, PCK cannot be used to assess the matching accuracy. Since segmentations masks are provided, we follow [START_REF] Ham | Proposal flow: Semantic correspondences from object proposals[END_REF], [START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF] and evaluate the quality of segmentation mask alignment using the following metrics: label transfer accuracy (LT-ACC), intersectionover-union (IoU), and localization error (LOC-ERR). Let (I A , I B ) be a pair of images with ground-truth segmentation masks (M A , M B ), and T be the estimated transformation from I A to I B . Then, the transferred annotated mask from the source image, M A = T (M A ), is compared with the ground-truth mask in the target image M B to assess the alignment quality.

The label transfer accuracy metric (LT-ACC), measures the number of correctly transferred foreground and background pixels in the following way:

LT-ACC = |{P ∈ I B , M A (P ) = M B (P )}| |P ∈ I B | (13)
Therefore, the numerator of the LT-ACC adds up the number of background pixels which are correctly mapped to background and the foreground pixels which are correctly mapped to foreground.

The intersection-over-union (IoU), or Jaccard index, as the LT-ACC also compares the mask alignment quality. However, contrary to LT-ACC, it only considers the correctly aligned foreground pixels, ignoring the background. It is computed in the following way:

IoU = |M A ∩ M B | |M A ∪ M B | . (14)
Finally, the localization error (LOC-ERR) metric measures the spatial error of each transferred pixel [START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF], assuming that the images are related by a translation and anisotropic scaling transformation which aligns the bounding boxes of the source and target images.

To this end, two normalized coordinates systems are defined relative to the source and target image bounding boxes, such that their origins are set on the top-left corners of the object bounding boxes, and the coordinates are normalized by the widths and heights of the bounding boxes.

Let

O A = (x O A , y O A ) and O B = (x O B , y O B )
be the top-left corners of the objects bounding boxes on I A and I B respectively, and (h A , w A ), (h B , w B ) the bounding box dimensions.

Then LOC-ERR metric measures the disagreement between the coordinates of the original point P A = (x A , y A ) relative to O A , and its transformed coordinates P A = T (P A ) = (x A , y A ) relative to O B , in the following way:

LOC-ERR = 1 |V | (P A ,P A )∈V |x A -x A | + |ŷ A -ŷ A |, (15)
where (x A , ŷA ) and (x A , ŷ A ) are the normalized coordinates of P A and P A = T (P A ):

(x A , ŷA ) = x A -x O A w A , y A -y O A h A (x A , ŷ A ) = x A -x O B w B , y A -y O B h B ( 16
)
and V is the set of all pairs of points (P A , P A ) in which the transformed points P A = T (P A ) fall inside the bounds of image I B .

Results

The quantitative results on the Caltech-101 dataset are presented in Tab. 3. As it can be observed, our approach outperforms the state-of-the-art by a significant margin, obtaining, for example, an IoU of 0.55 compared to the previous best result of 0.50.

In addition, it can be observed that the LOC-ERR metric values do not follow the trend of the other two metrics. This is because the LOC-ERR metric makes the invalid assumption that the images are related with a translation and anisotropic scaling transformation.

The benefit of the two-stage approaches is clear from the more realistic IoU metric, where adding a second stage achieves an IoU of 0.55 compared to 0.53 of the single-stage best performing model.

In Fig. 11, we present a qualitative comparison of the results obtained by our method and other previous methods on images from this dataset. For each example, the second row presents the transferred segmentation mask T (M A ) of I A overlaid with I B , for each of the methods. As it can be visually assessed, the proposed approach achieves a superior alignment than most of the previous methods.

Graffiti benchmark

This section presents the results of the proposed method on the challenging Graffiti instance-level matching benchmark [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF]. This benchmark contains 6 images of the same planar scene with increasingly varying viewpoint, with up to 70 • azimuthal rotation from the reference image. Ground-truth homography transformations from the reference image 1 to images 2-6 are available with the dataset. We employed the same homography estimation CNN used for the category-level alignment datasets, trained from synthetic StreetView image pairs. To overcome the large viewpoint variation in this dataset, we perform iterative refinement, as described in section 4.5, with a total of 5 iterations.

The same CNN model is used for all iterations.

Evaluation metric

In order to measure the quality of the estimated homography transformation, the average endpoint error is used:

AEE(H, H GT ) = 1 N N i=1 G i -G i (17)
where

G i = T H (G i ) and G i = T H GT (G i ) are the transformed sampling points G = [1, 2, . . . , h] × [1, 2
, . . . , w] when applying the estimated and ground-truth homographies, respectively. Note that this is similar to the proposed loss ( 9), but without squaring the distances.

Results

Quantitative results are presented on Tab. 4. The proposed method is compared against state-of-the-art methods for this dataset, such as SIFT features (DoG+SIFT) [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF], SIFT features with affinecovariant detectors (DoG-affine+SIFT) [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF] and ASIFT [START_REF] Yu | ASIFT: An Algorithm for Fully Affine Invariant Comparison[END_REF]. Features are matched and filtered using the second nearest-neighbor test [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] and the homography transformation is estimated with the locally optimized RANSAC algorithm [START_REF] Lebeda | Fixing the locally optimized RANSAC[END_REF] with the following parameter settings: distance threshold θ = 6px, estimation confidence η 0 = 0.999, and the final refinement step using all inliers. The rest of the parameters are set to their default values. The RANSAC algorithm is executed 5 times and the mean error values are reported. In all cases, the standard deviations were below 0.3 pixels. As it can be observed from Tab. 4, although our method does not produce the best results, it still achieves reasonable alignments for pairs (1, 2) up to [START_REF] Forsyth | Computer vision: a modern approach[END_REF][START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF], and fails for pair [START_REF] Forsyth | Computer vision: a modern approach[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. The lower performance of our method when compared to local interest points methods can be explained by the lower resolution of the input image, which is resized from 800 × 640px to 240 × 240px, and also by the low resolution of the extracted CNN features, which is of 15 × 15. In addition, due to the max-pooling operations, the exact positions of the image features cannot be recovered from the CNN features.

However, it is interesting to point out that while DoG-SIFT fails for pair [START_REF] Forsyth | Computer vision: a modern approach[END_REF][START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF], our method does not. This confirms the intuition that CNN feature descriptors have some degree of affine invariance, achieved due to multiple pooling operations. The invariance enables multiple good initial matches to be established, producing a good initial transformation estimate, which is then progressively refined using the iterative procedure.

Qualitative results for the pair (1, 5) of the Graffiti benchmark are shown in Fig. 12. The figure also shows the progression of the alignment as more refinement iterations are performed. As it can be observed, the obtained alignment is qualitatively good.

Tokyo Time Machine dataset

Qualitative results for the Tokyo Time Machine dataset [START_REF] Arandjelović | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF] are shown in Fig. 14. The images have been captured at different points in time which are months or years apart. Note that, by automatically highlighting the differences (in the feature space) between the aligned images, it is possible to detect changes in the scene, such as occlusions, changes in vegetation, or structural differences e.g. new buildings being built.

DISCUSSIONS AND ABLATION STUDIES

In this section we examine the importance of various components of our architecture, and discuss about the impact of the training set, the learned filters and the limitations of the method.

Correlation versus concatenation and subtraction.

Replacing our correlation-based matching layer with feature concatenation or subtraction, as proposed in [START_REF] Detone | Deep image homography estimation[END_REF] and [START_REF] Kanazawa | WarpNet: Weakly supervised matching for single-view reconstruction[END_REF], respectively, incurs a large performance drop, as shown in Tab. 5. The behavior is expected as we designed the matching layer to only keep information on pairwise descriptor similarities rather than the descriptors themselves, as is good practice in classical geometry estimation methods, while concatenation and subtraction do not follow this principle.

Normalization

Generalization

In order to assess the influence on the performance of the trained method with respect to the training dataset used, we train a second model using PASCAL VOC 2011 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2011[END_REF] images, instead of StreetView images. As seen in Tab. 5, our method is relatively unaffected by the choice of training data as its performance is similar regardless whether it was trained with StreetView or PASCAL images. We also attribute this to the design choice of operating on pairwise descriptor similarities rather than the raw descriptors.

Geometric models

Different configurations of the proposed method have been analyzed, varying the geometric models and using both single-stage (as in Fig. 2) and two-stage approaches (as in Fig. 6).

Results from Tables 1, 2, and 3 show that the two-stage homography+TPS is the best performing approach, being slightly superior to affine+TPS. On the other hand, TPS alone is the best single-stage approach, but interestingly, two-iteration TPS performs worse than both affine+TPS and homography+TPS. This confirms the intuition discussed in section 4.4, where using a simpler geometric model to perform the rough alignment is expected to be more robust than using a more complex one.

What is being learned?

We examine filters of size 7 × 7 × 225 from the first convolutional layer of the regressor, which operate directly on the output of the matching layer, i.e. the tentative correspondence map. We observe that two filter properties emerge from training: (i) filters specialize in detecting matches in specific positions in image A, and (ii) filters learn to mimic local neighborhood consensus for robust match estimation. In order to visualize this, each 1 × 1 × 225 1-D slice through the channels of one convolutional filter at a particular spatial location is reshaped as a 15 × 15 image. Recall that the 225 channels correspond to flattened similarities with image A (see Fig. 3 and Eq. ( 1)), therefore these images show the filter's preferences to matches in specific locations in image A. For visualization, we pick the peaks from all slices of filter weights and average them together to produce a single image. Several filters are shown in Fig. 13. It can be observed that matches form clusters, which means that spatially co-located features in image B (within the 7 × 7 support of the filter) respond strongly to spatially consistent locations in image A, therefore confirming that this layer has learned to mimic local neighborhood consensus. Furthermore, it can be observed that the size of the preferred spatial neighborhood varies across filters, thus showing that filters specialize for certain scale changes. Finally, the fact that the location of the highest filter weights (bright yellow) is different for different filters shows that the filters specialize for different locations in image A.

Limitations

Next, we analyze limitations of the proposed method and discuss possible ways of alleviating them.

Robustness to occlusion

The robustness of the proposed method to occlusion was assessed by computing the PCK on the PF-WILLOW dataset when substituting a rectangular portion of each image in the dataset with a crop from a different unrelated image. Both positions and aspect ratios of these rectangles were independently and randomly sampled for each image. The results are shown in Tab. 6. It can be observed that all methods, including Proposal Flow [START_REF] Ham | Proposal Flow[END_REF], degrade significantly when occluding 10% or 20% of the area of the images. Although retraining the proposed method replicating the occlusion procedure helps to improve the performance on the occluded data, it also degrades the performance on the unoccluded case. Therefore, alignment with significant occlusion still presents a challenge for the current methods, including ours.

Multiple objects

Currently, the proposed method can only produce a global alignment of the image pair, and handling multiple objects is still a challenge. This is in line with current datasets on category-level image alignment which contain a single foreground object, and with all competing methods which also make this assumption. This limitation could be addressed by incorporating an attention mechanism.

Learning better features

Although the proposed architecture is fully differentiable, which makes it end-to-end trainable for the task of semantic alignment, we have observed that finetuning the feature extraction CNN does not improve alignment performance. This is because our synthetic dataset used for training does not contain rich appearance variations present in the real category-level alignment datasets used for evaluation. While supervision from synthetic data comes with no cost and is useful to train the regression CNN, it is not suited for learning better image features for alignment. As a solution to this problem, we have developed a combined approach using synthetic data for training the regression CNN and real data for finetuning the feature extraction CNN [START_REF] Rocco | End-to-end weakly-supervised semantic alignment[END_REF].

Confidence in the estimated transformation

The proposed method does not currently produce a measure of the confidence in the estimated transformation. However, the softinlier count presented in [START_REF] Rocco | End-to-end weakly-supervised semantic alignment[END_REF] could be employed for this purpose.

Asymmetry in the method

Given an pair of images I A and I B , the method is trained to produce the alignment in one direction only. In order to make the method more symmetric, the alignments in both directions could be estimated simultaneously and a cycle consistency loss [START_REF] Zhou | Learning dense correspondence via 3d-guided cycle consistency[END_REF],

[62] could be incorporated.

Computational cost

The presented method currently takes about 1.6s per 240 × 240px image pair, which is 1.5× faster than SIFT Flow and 6× faster than Proposal Flow, when run on a modern CPU. Furthermore, the presented method can also be run on the GPU, which allows to obtain an additional 40× speedup.

CONCLUSIONS

We have described a network architecture for geometric matching trainable from synthetic imagery without the need for manual annotations. The architecture is modular and flexible, and can be applied iteratively, in order to estimate large transformations, or in a cascade, enabling estimation of complex transformations. Thanks to our matching layer, the network generalizes well to never seen before imagery, reaching state-of-the-art results on several challenging datasets for category-level matching. The method has also proven useful for instance-level alignment, obtaining reasonable alignment for the challenging Graffiti benchmark. This work opens-up the possibility of applying our architecture to other difficult correspondence problems such as matching across large changes in illumination (day/night) [START_REF] Arandjelović | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF] or depiction style [START_REF] Aubry | Painting-to-3D model alignment via discriminative visual elements[END_REF].

Fig. 1 .

 1 Fig. 1. Top: The proposed model can be trained from synthetic image pairs, avoiding the need for manual annotation. Bottom: At evaluation time, the trained geometry estimation network automatically aligns two images with substantial appearance differences. It is able to estimate large deformable transformations robustly in the presence of clutter.

Fig. 2 .

 2 Fig.2. Diagram of the proposed architecture. Images I A and I B are passed through feature extraction networks which have tied parameters W , followed by a matching network which matches the descriptors. The output of the matching network is passed through a regression network which outputs the parameters of the geometric transformation.

Fig. 3 .

 3 Fig. 3. Correlation map computation with CNN features. The correlation map c AB contains all pairwise similarities between individual features f A ∈ f A and f B ∈ f B . At a particular spatial location (i, j) the correlation map output c AB contains all the similarities between f B (i, j) and all f A ∈ f A .

Fig. 5 .

 5 Fig. 5. Thin-plate spline control points. Illustration of the 3 × 3 TPS grid of control points used in the thin-plate spline transformation model.

  is a parametric model which performs smooth 2-D interpolation given a set of k corresponding control points C A = {C A1 , . . . , C Ak } and C B = {C B1 , . . . , C Bk } between two images. In this work we use k = 9 and arrange the control points C B in a 3 × 3 uniform grid on the target image, as illustrated in Fig. 5. Because control points C B are fixed for all image pairs, the TPS transformation is parametrized only by the control points C A in the source image:

Fig. 6

 6 Fig.[START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Estimating progressively more complex geometric transformations. Images A and B are passed through a network which estimates an affine transformation with parameters θ AFF (see Fig.2). Image A is then warped using this transformation to roughly align it with B, and passed along with B through a second network which estimates a thin-plate spline (TPS) transformation that refines the alignment.

Fig. 7 .

 7 Fig. 7. Iterative transformation refinement. In iteration i, image A is warped using the cumulative transformation estimate θ (i-1) c obtained from the previous iteration (θ (0) c

Fig. 8 .

 8 Fig. 8. Synthetic image generation. Symmetric padding is added to the original image to enlarge the sampling region, its central crop is used as image A, and image B is created by performing a randomly sampled transformation T θ GT .

Algorithm 1 :

 1 Training procedure using synthetic pairs input : Image database DB CNN model M W output: Trained CNN model M W for training epochs do for I in DB do // Generate synthetic training pair Sample random transformation θ GT I A = central crop of I; I B = T θGT (I); // Estimate transformation θ θ = M W (I A , I B ); // Compute loss and update model L = L(θ, θ GT ); W = update(W, ∂L ∂W ); end end sec. 2.4.3), and must then be composed to obtain the [a ij ] matrix described in section 4.1:

Algorithm 2 :

 2 Transformation estimation using twostage network input : Source and target images (I A , I B ) Stage 1 CNN model M 1 Stage 2 CNN model M 2 output: Aligned image I A // First stage θ 1 = M 1 (I A , I B ); I A = T θ1 (I A ); // Second stage θ 2 = M 2 (I A , I B ); I A = T θ2 (I A );

Fig. 9 .

 9 Fig.9. Qualitative results on the PF dataset. Each row shows one test example from the Proposal Flow dataset. Ground truth matching keypoints, only used for alignment evaluation, are depicted as crosses and circles for images A and B, respectively. Keypoints of same color are supposed to match each other after image A is aligned to image B. To illustrate the matching error, we also overlay keypoints of B onto different alignments of A so that lines that connect matching keypoints indicate the keypoint position error vector. Our method manages to roughly align the images with an affine transformation (column 2), and then perform finer alignment using thin-plate spline (TPS, column 3). The top two examples are from the PF-WILLOW dataset while the bottom one is from PF-PASCAL.

Fig. 10 .Fig. 11 .Fig. 12 .

 101112 Fig. 10. Qualitative results on the TSS dataset. Each row shows one test example from the TSS dataset. The last column shows the ground-truth alignment used for evaluation. Example 1 is from TSS-FG3DCar, examples 2-3 are from TSS-JODS, and 4-7 from TSS-PASCAL.

Fig. 13 .

 13 Fig.13. Filter visualization. Some convolutional filters from the first layer of the regressor, acting on the tentative correspondence map, show preferences to spatially co-located features that transform consistently to the other image, thus learning to perform the local neighborhood consensus criterion often used in classical feature matching. Refer to the text for more details on the visualization.

Fig. 14 .

 14 Fig.14. Qualitative results on the Tokyo Time Machine dataset. Each row shows a pair of images from the Tokyo Time Machine dataset, and our alignment along with a "difference map", highlighting absolute differences between aligned images in the descriptor space. Our method successfully aligns image A to image B despite of viewpoint and scene changes (highlighted in the difference map).

TABLE 2

 2 Matching accuracy on the TSS dataset in terms of PCK (α = 0.05). The three intermediate columns show the results for each subset of the TSS dataset: FG3DCar, JODS and PASCAL. The last column shows the PCK result over the whole dataset.

	Methods	FG3DCar JODS PASCAL	All
	DSP [36]	0.49	0.47	0.38	0.45
	SIFT Flow [34]	0.63	0.51	0.36	0.52
	Taniai et al. [52]	0.83	0.60	0.48	0.67
	Proposal Flow (SS+LOM) [8]	0.79	0.65	0.53	0.68
	Ours (affine)	0.81	0.65	0.51	0.68
	Ours (homography)	0.83	0.66	0.52	0.70
	Ours (TPS)	0.84	0.72	0.51	0.71
	Ours (affine + TPS)	0.89	0.72	0.54	0.75
	Ours (homography + TPS)	0.88	0.72	0.55	0.75
	Ours (2×TPS)	0.86	0.70	0.52	0.72

TABLE 3

 3 Evaluation on the Caltech-101 dataset. Matching quality is measured in terms of LT-ACC and IoU. The best two Proposal Flow methods (RP, LOM and SS, LOM) are included here. All numbers apart from ours are taken from[START_REF] Ham | Proposal Flow[END_REF].

	Methods	LT-ACC	IoU	LOC-ERR
	DeepFlow [56]	0.74	0.40	0.34
	GMK [35]	0.77	0.42	0.34
	SIFT Flow [34]	0.75	0.48	0.32
	DSP [36]	0.77	0.47	0.35
	Proposal Flow (RP, LOM) [54]	0.78	0.50	0.26
	Proposal Flow (SS, LOM) [54]	0.78	0.50	0.25
	Ours (affine)	0.78	0.51	0.24
	Ours (homography)	0.80	0.52	0.24
	Ours (TPS)	0.80	0.53	0.24
	Ours (affine + TPS)	0.79	0.55	0.26
	Ours (homography + TPS)	0.81	0.55	0.25
	Ours (2×TPS)	0.80	0.54	0.26

TABLE 4

 4 Evaluation on the Graffiti benchmark. Matching quality is measured in terms of the AEE (px), being the original image of 640 × 800 px. Our homography estimation model is run recursively five times.

	Methods	Image pair (1, 2) (1, 3) (1, 4) (1, 5) (1, 6)
	DoG+SIFT [19]	0.63	1.61	2.89	fail	fail
	DoG-affine+SIFT [19]	0.60	1.57	1.44	2.40	2.75
	ASIFT [57]	0.45	1.35	1.02	0.96	1.62
	Ours (5×homography)	4.17	4.81	3.17	2.55	fail

Table 5

 5

also shows the importance of the correlation map normalization step, where the normalization improves results from 41% to 48%. The step mimics the second nearest neighbor test used in classical feature matching

[START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]

, as discussed in Sec. 3.2. Note that

[START_REF] Fischer | FlowNet: Learning optical flow with convolutional networks[END_REF]

also uses a correlation layer, but they do not normalize the map in any way, which is clearly suboptimal.

TABLE 5

 5 Ablation studies on the matching layer and effect of the training dataset. Accuracy is measured in terms of the PCK on the PF-WILLOW dataset using the single-stage affine model.

	Methods	PCK
	Subtraction [33]	0.24
	Concatenation [32]	0.34
	Ours (without normalization)	0.41
	Ours (trained on PASCAL)	0.47
	Ours (trained on StreetView)	0.48

TABLE 6

 6 Evaluation of robustness to occlusions in terms of PCK on the PF-WILLOW dataset.

	Methods	0%	Occluded area 10% 20%
	Proposal Flow (SS, LOM) [54]	0.56	0.46	0.30
	Ours (homography+TPS)	0.60	0.46	0.32
	Ours trained with 10% occlusions (hom.+TPS)	0.57	0.47	0.36
	Ours trained with 20% occlusions (hom.+TPS)	0.48	0.43	0.38

ACKNOWLEDGMENTS

This work has been partly supported by ERC grant LEAP (no. 336845), ANR project Semapolis (ANR-13-CORD-0003), the Inria CityLab IPL, CIFAR Learning in Machines & Brains program and ESIF, OP Research, development and education Project IMPACT No. CZ.02.1.01/0.0/0.0/15 003/0000468.