Keywords: Image representation, image retrieval, kernel methods, neural networks, region matching, semantic matching, Fisher vectors. v vi Image representation, image retrieval, kernel methods, neural networks, region matching, semantic matching, Fisher vectors

The problem of image representation is at the heart of computer vision. The choice of feature extracted of an image changes according to the task we want to study. Large image retrieval databases demand a compressed global vector representing each image, whereas a semantic segmentation problem requires a clustering map of its pixels. The techniques of machine learning are the main tool used for the construction of these representations. In this manuscript, we address the learning of visual features for three distinct problems: Image retrieval, semantic correspondence and image classification.

First, we study the dependency of a Fisher vector representation on the Gaussian mixture model used as its codewords. We introduce the use of multiple Gaussian mixture models for different backgrounds, e.g., different scene categories, and analyze the performance of these representations for object classification and the impact of scene category as a latent variable.

Our second approach proposes an extension to the exemplar SVM feature encoding pipeline. We first show that, by replacing the hinge loss by the square loss in the ESVM cost function, similar results in image retrieval can be obtained at a fraction of the computational cost. We call this model square-loss exemplar machine, or SLEM. Secondly, we introduce a kernelized SLEM variant which benefits from the same computational advantages but displays improved performance. We present experiments that establish the performance and efficiency of our methods using a large array of base feature representations and standard image retrieval datasets.

Finally, we propose a deep neural network for the problem of establishing semantic correspondence. We employ object proposal boxes as elements for matching and construct an architecture that simultaneously learns the appearance representation and geometric consistency. We propose new geometrical consistency scores tailored to the neural network's architecture. Our model is trained on image pairs obtained from keypoints of a benchmark dataset and evaluated on several standard datasets, outperforming both recent deep learning architectures and previous methods based on hand-crafted features.

We conclude the thesis by highlighting our contributions and suggesting possible future research directions.

Résumé

Le problème de représentation d'image est au coeur du domaine de vision. Le choix de représentation d'une image change en fonction de la tâche que nous voulons étudier. Un problème de recherche d'image dans des grandes bases de données exige une représentation globale compressée, alors qu'un problème de segmentation séantique nécessite une carte de partitionnement de ses pixels. Les techniques d'apprentissage statisque sont l'outil principal pour la construction de ces représentations. Dans ce manuscrit, nous abordons l'apprentissage des représentations visuels dans trois problèmes différents: la recherche d'image, la correspondance sémantique et classification d'image.

Premièrement, nous étudions la représentation vectorielle de Fisher et sa dépendence sur le modèle de mélange Gaussien employé. Nous introduisons l'utilisation de plusieurs modèles de mélange Gaussien pour différents types d'arrière-plans, e.g., différentes catégories de scène, et analyser la performance de ces représentations pour objet classification et l'impact de la catégorie de scène en tant que variable latente.

Notre seconde approche propose une extension de la représentation l'exemple SVM pipeline. Nous montrons d'abord que, en remplaçant la fonction de perte de la SVM par la perte carrée, on obtient des résultats similaires à une fraction de le coût de calcul. Nous appelons ce modèle la « square-loss exemplar machine », ou SLEM en anglais. Nous introduisons une variante de SLEM à noyaux qui bénéficie des même avantages coputationnelles mais affiche des performances améliorées. Nous présentons des expériences qui établissent la performance et l'efficacité de nos méthodes en utilisant une grande variété de représentations de base et de jeux de données de recherche d'images.

Enfin, nous proposons un réseau neuronal profond pour le problème de l'établissement sémantique correspondance. Nous utilisons des boîtes d'objets en tant qu'éléments de correspondance pour construire une architecture qui apprend simultanément l'apparence et la cohérence géométrique. Nous proposons de nouveaux scores géométriques de cohérence adaptés à l'architecture du réseau de neurones. Notre modèle est entraâiné sur des paires d'images obtenues à partir des points-clés d'un jeu de données de référence et évaluées sur plusieurs ensembles de données, surpassant les architectures d'apprentissage en profondeur récentes et méthodes antérieures basées sur des caractéristiques artisanales. Nous terminons la thèse en soulignant nos contributions et en suggérant d'éventuelles directions de recherche futures.

Mots-clés : Représentation d'image, modèle à noyaux, recherche d'image, réseau de neurone, correspondance de région, correspondance sémantique, vecteurs de Fisher. vii viii Chapter 1

Introduction

The growing availability of data is one of the main drivers on innovation in the domain of computer vision. Thanks to social media, the widespread use of surveillance technology and the success of medical imagery, we produce more data than ever and ease the process of annotation.

The increase in volume and complexity of the data we use is shown in the types of datasets we use over time. Caltech 101 [START_REF] Fei-Fei | Learning generative visual models from few training examples: an incremental bayesian approach tested on 101 object categories[END_REF] was, at time of its publication in 2004, the main benchmark dataset for object detection, object recognition and image classification. It contains around 9000 instances of objects in 101 different classes and each instance is a cropped image centered on the main object and negligible background. Three years later, the PASCAL Visual Objects Classes Challenge [START_REF] Everingham | The pascal visual object classes challenge 2007[END_REF] introduced a dataset for the same tasks of 12 thousand instances with non-centered objects with rich background information. This category of images makes the PASCAL dataset more complex and tasks of classification and detection more challenging. More recently, the ImageNet database [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF] assembles 12 million images. This dataset also allows hierarchical labeling, adding a layer of complexity to the aforementioned classification and detection problems, where we are comparing and contrasting instances of the same category.

The sheer number of images and labels renders the recognition and classification tasks more difficult, but the content of their images has also made these datasets more challenging. Comparing Fig. 1-1, 1-2 and 1-3, we first notice a difference in resolution. Looking more carefully, we see in the more recent datasets more complex poses, noisy background information, blurry boundaries between foreground and background and instances of objects of a category different from the main object. The evolution of these datasets mirrors the boosting diversity of data available today both to research proposes and to commercial ventures.

The increasing complexity of these datasets demands an equally increasing complexity of the feature representations we employ to its images. Indeed, the increase of object poses, viewpoints and positions on a dataset demands a feature more robust to this variability. Similarly, exploring large datasets is time-consuming and demands more compact features that do not loose much information when reduced to a lower dimension.

The goal of this thesis is to explore the image representation problem. This is a wide subject that can take many different forms according to the task we want to address. For example, large image retrieval databases demand a compressed global visual feature representation of an image, whereas a semantic segmentation problem requires a clustering map of its pixels. Additionally, tasks that use similar representations may be interested in different types of information. Indeed, object classification and image retrieval use a global visual feature representation of its images. However, an object classification feature is not interested in representing the background information of the scene of the image, whereas the background is important for retrieval since it serves as the context of the image. Furthermore, designing good representations requires some common knowledge or annotated data. Most modern approaches are based on supervised machine learning methods that demand some kind of annotation of the data.

In this thesis, we present three different works in image representation in three different computer vision tasks: Object classification, image retrieval and semantic correspondence. We briefly introduce each work in the following sections.

Image classification with contextual Fisher vectors (CFV)

We consider the problem of image classification, i.e., we wish to associate to a given image one or more semantic categories based on the image's content. We are more particularly interested in the object classification task, where the semantic categories correspond to objects present in the image. This task is one of the most fundamental problems of image understanding and is presented as a clear case of machine learning applied to a computer vision problem: Given an object category and a database of images previously labeled as +1 (contains the object) or 0 (does not contain the object), can we predict the label of a unlabeled image? Since this is a well established task in machine learning, which provides us good candidates to classification algorithm (SVM, kernel SVM, kNN) we concentrate in the construction of a robust image representation pipeline.

We propose in Chapter 2 two methods of improving the existing Fisher vector encoding pipeline:

-a generalization of Fisher vectors where we introduce the concept of multiple background types, each one providing a Fisher encoding.

-a projection of the original Fisher vector that minimizes the background information of the image.

The use of feature vector encoding a full image, such as Bag-of-words [START_REF] Csurka | Visual categorization with bag of keypoints[END_REF] or VLAD features [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF], was the first very successful method for feature construction for image classification. Fisher vectors often get the spotlight due to high-order statistics and easy generalization of a probability law as a Gaussian mixture model (GMM). However, this generalization of a probability law over many images may fail to represent individual images if they do not share the same type of background information. For example, a probability law calculated over two images, one indoor and one outdoor, will fail to represent the background of both, turning the Fisher vector's strength into a weakness. In order to address this issue, we introduce the Contextual Fisher Vector (CFV) generalization, that considers different GMM for different scene categories, in order to better represent each category and thus eliminate the background information, improving its results in object classification.

We are also interested in the learning of the GMM used as probability law. More specifically, we question which descriptors are used to learn the distribution and also in how much the final feature representation is independent of background information, i.e., descriptors of parts of the image that do not contain relevant information of the object category. Following the theoretical assumption that the Fisher encoding erases background descriptors, we suggest modifications in the standard Fisher vector pipeline in order to obtain a representation dependent only on the object foreground of an image.

Our experiments suggest the following: First row encapsulates the construction of a base feature for a query image, which usually consists of extracting, embedding and aggregating local descriptors into a vector, here written as 𝑥 0 . After repeating the process of base feature calculation a database of sample images and obtaining a matrix 𝑋 of base features, we solve a exemplar classifier by labeling 𝑥 0 as the lonely positive example (called exemplar ) and the columns of 𝑋 as negatives. The solution 𝜔 to this classification problem, which is a function of 𝑥 0 and 𝑋, is our SLEM encoding of the query image.

-Our two central assumptions (Gaussian mixture model calculated separately on different contexts and only in background images) can slightly improve the foreground/background ratio of the Fisher vector representation, but do not improve classification results in fairly simple object classification tasks.

-We obtain significant improvements projecting Fisher vectors in a subspace that eliminates most of the background information, with or without depending on the foreground information. These results however come with no implicit theoretical justification and can overfit the training examples' background.

1.2 Image retrieval with square-loss exemplar machine (SLEM)

Chapter 3 addresses the problem of image retrieval by proposing a new feature encoding pipeline that represents an image by the solution of an exemplar classification problem. The exemplar classifier, most specifically the exemplar SVM (ESVM), was introduced to be used in ensembles of weighted classifiers for object detection [START_REF] Malisiewicz | Ensemble of exemplar-svms for object detection and beyond[END_REF]. It consists of solving a unbalanced classification problem, of one positive exemplar against a large pool of negative samples. The premise is that an ESVM classifier learns discriminative information of the exemplar image instead of the image's object class. Such premise is used here to justify the use of the exemplar classifier as image representation. Indeed, recent work by Zepeda and Pérez has introduced the use of ESVM as a feature encoder for image retrieval [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF]. This chapter presented here is an extended version of the paper "Square-loss exemplar machines for image retrieval" by Rezende, Zepeda, Ponce, Bach and Pérez published in CVPR 2017 [START_REF] Rezende | Square loss exemplar machines for image retrieval[END_REF]. Our work extends the approach of [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF] in several directions: We first show that replacing the hinge loss by the square loss in the ESVM cost function significantly reduces encoding time with negligible effect on accuracy. We call this model square-loss exemplar machine, or SLEM. Then we introduce a kernelized SLEM which can be implemented efficiently through low-rank matrix decomposition, and displays improved performance. An important source of inefficiency of a kernel classifier with respect to a linear classifier is the computation of the kernel matrix. However, both kernelized and non-kernelized SLEM exploit the fact that the negative examples are fixed, so most of the SLEM computational complexity is relegated to an offline process independent of the positive examples. For kernel SLEM, fixing all but one sample across classifiers means simplifying the online calculations from 𝑂(𝑛 2 ) computation of a (𝑛 + 1) × (𝑛 + 1) kernel matrix to a 𝑂(𝑛) computation of the column and row corresponding to the positive exemplar.

Our experiments establish the performance and computational advantages of our approach. Our experiments are performed on three standard datasets for image retrieval, namely INRIA Holidays dataset [START_REF] Jegou | Hamming embedding and weak geometry consistency for large scale image search[END_REF], Oxford 5k buildings dataset and Oxford 105k buildings dataset [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. We demonstrate both the time efficiency and the improvement of retrieval results using a large array of base features, both hand-crafted features (VLAD features [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF]) and neural network learned (last convolutional layer outputs of AlexNet architecture [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], VGG+SPoC architecture [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF] and NetVLAD features [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF]) as well as densely extracted local descriptors. Our approach is tested for a several combinations of kernel functions and ranks of decompositions.

The contributions of this work are threefold:

-We introduce a kernelized variant of SLEM that enjoys similar computational advantages and improves retrieval performances.

-We propose a low-rank factorization of the kernel matrix for computational and storage efficiency.

-Our experiments show improved results on a variety of base features and we obtain state-of-the-art results for Inria Holidays dataset.

Semantic correspondence with convolutional neural networks (SCNet)

Chapter 4 addresses the problem of establishing semantic correspondences between images depicting different instances of the same object or scene category. Include different instances means a much larger change in appearance and spatial layout than the pictures of the same scene used in stereo vision, which we take here to include broadly not only classical (narrow-baseline) stereo fusion (e.g., [START_REF] Okutomi | A multiple-baseline stereo[END_REF][START_REF] Rhemann | Fast cost-volume filtering for visual correspondence and beyond[END_REF]), but also optical flow computation (e.g., [START_REF] Horn | Determining optical flow: A retrospective[END_REF][START_REF] Revaud | Deepmatching: Hierarchical deformable dense matching[END_REF][START_REF] Weinzaepfel | Deepflow: Large displacement optical flow with deep matching[END_REF]) and wide-baseline matching (e.g., [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF][START_REF] Yang | Daisy filter flow: A generalized discrete approach to dense correspondences[END_REF]). Due to such a large degree of variations, the problem of semantic correspondence remains very challenging. Most previous approaches to semantic correspondence [START_REF] Bristow | Dense semantic correspondence where every pixel is a classifier[END_REF][START_REF] Hur | Generalized deformable spatial pyramid: Geometry-preserving dense correspondence estimation[END_REF][START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF][START_REF] Liu | SIFT flow: Dense correspondence across scenes and its applications[END_REF][START_REF] Taniai | Joint recovery of dense correspondence and cosegmentation in two images[END_REF][START_REF] Yang | Daisy filter flow: A generalized discrete approach to dense correspondences[END_REF] focus on combining an effective spatial regularizer with hand-crafted features such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], DAISY [START_REF] Tola | Daisy: An efficient dense descriptor applied to wide-baseline stereo[END_REF] or HOG [START_REF] Uijlings | Selective search for object recognition[END_REF]. With the remarkable success of deep learning approaches in visual recognition, several learningbased methods have also been proposed for both stereo vision [START_REF] Fischer | Flownet: Learning optical flow with convolutional networks[END_REF][START_REF] Han | MatchNet: Unifying feature and metric learning for patch-based matching[END_REF][START_REF] Žbontar | Computing the stereo matching cost with a convolutional neural network[END_REF][START_REF] Zbontar | Stereo matching by training a convolutional neural network to compare image patches[END_REF] and semantic correspondence [START_REF] Choy | Universal correspondence network[END_REF][START_REF] Kim | Fcss: Fully convolutional self-similarity for dense semantic correspondence[END_REF][START_REF] Zhou | Learning dense correspondence via 3d-guided cycle consistency[END_REF]]. Yet, none of these methods exploits the geometric consistency constraints that have proven to be a key factor to the success of their hand-crafted counterparts. Geometric regularization, if any, occurs during post-processing but not during learning (e.g., [START_REF] Žbontar | Computing the stereo matching cost with a convolutional neural network[END_REF][START_REF] Zbontar | Stereo matching by training a convolutional neural network to compare image patches[END_REF]).

Conv layers

(r 1 , …, r p )

I A F A ROI pooling c (r 1 ,w) … c (r p ,w) Conv layers (s 1 , …, s p ) I B F B ROI pooling FC L 2 Norm c (s 1 ,w) … c (s p ,w) z (m 1 ,w) … z (m n ,w) ×K ReLU f (m 1 ,w) … f (m n ,w) FC g L 2 Norm FC L 2 Norm FC g L 2 Norm ReLU f g (m 1 ,w) … f g (m n ,w) c g (r 1 ,w) … c g (r p ,w) c g (s 1 ,w) … c g (s p ,w)
Figure 1-5: The SCNet architectures. Three variants are proposed: SCNet-AG, SCNet-A, and SCNet-AG+. The basic architecture, SCNet-AG, is drawn in solid lines. Colored boxes represent layers with learning parameters and the boxes with the same color share the same parameters. "×𝐾" denotes the voting layer for geometric scoring. A simplified variant, SCNet-A, learns appearance information only by making the voting layer an identity function. An extended variant, SCNet-AG+, contains an additional stream drawn in dashed lines. SCNet-AG learns a single embedding 𝑐 for both appearance and geometry, whereas SCNet-AG+ learns an additional and separate embedding 𝑐 𝑔 for geometry.

We propose a convolutional neural network (CNN) architecture, called SCNet, for learning geometrically plausible semantic correspondence based on probabilistic Hough matching (PHM), which allows us to handle a large degree of intra-class and scene variations. Following the proposal flow approach to semantic correspondence of Ham et al. [START_REF] Ham | Proposal flow[END_REF], we use object proposals [START_REF] Manen | Prime object proposals with randomized Prim's algorithm[END_REF][START_REF] Uijlings | Selective search for object recognition[END_REF][START_REF] Zitnick | Edge boxes: Locating object proposals from edges[END_REF] as matching primitives, and explicitly incorporate the geometric consistency of these proposals in our loss function. Unlike [START_REF] Ham | Proposal flow[END_REF] with its hand-crafted features, however, we train our system in an endto-end manner using image pairs extracted from the PASCAL VOC 2007 keypoint dataset [START_REF] Everingham | The pascal visual object classes challenge 2007[END_REF]. A comparative evaluation on several standard benchmarks demonstrates that the proposed approach substantially outperforms both recent deep architectures and previous methods based on hand-crafted features. This part of the chapter is an extended version of the paper "SCNet: Learning semantic correspondence" by Han, Rezende, Ham, Wong, Cho, Schmid and Ponce published in ICCV 2017 [START_REF] Han | Scnet: Learning semantic correspondence[END_REF] and was made in collaboration with another PhD student, Kai Han, from the University of Hong Kong. The extent of the contribution of each of us is further identified in Chapter 4.

Additionally, we present a ongoing work of a new model of geometric consistency. We take inspiration from the local offset matching (LOM) of [START_REF] Ham | Proposal flow[END_REF], which is not suited to a differentiable CNN architecture. We propose a new geometric model for local best appearance matching (LBAM) similar to LOM but adapted to the SCNet architecture (as presented in Fig. 12345). The results presented show improved results with respect to PHM for hand-crafted appearance features, but incomplete results when applied to the SCNet learning pipeline.

Our main contributions can be summarized as follows:

-We introduce a simple and efficient model for learning to match regions using both appearance and geometry of matching object proposals.

-We propose a convolutional neural network, SCNet, to learn semantic correspondence with region proposals.

-We achieve state-of-the-art results on several benchmarks, clearly demonstrating the advantage of learning both appearance and geometric terms.

Chapter 2

Contextual Fisher Vectors

The problem of constructing a feature representation for object classification is connected to the elimination of background information. Indeed, the goal of object classification is to ensemble images based on the class of the foreground object, and the different contexts in which this object appears can act as distracting information. This chapter is dedicated to our study of an alternative formulations of Fisher vectors and how they can improve upon the existing pipeline. We first propose to calculate the codewords used as embedding from local descriptors that do not include foreground information. Later, we study how to reduce Fisher to the components that minimize the background information. Finally, we introduce the contextual Fisher vector, which consists of a concatenation of projected Fisher vectors calculated for different contexts of scene categories. Our experiments in a diverse group of dataset images show inconsistent results and we conclude this work is unsuccessful.

Introduction

We consider the problem of image classification, i.e.we wish to associate to a given image one or more semantic categories based on the image's content. We are more particularly interested in the object classification task, where the semantic categories correspond to objects present in the image. This task is one of the most fundamental problems of image understanding and is presented as a clear case of machine learning applied to a computer vision problem: Given an object category and a database of images previously labeled as +1 (contains the object) or 0 (does not contain the object), can we guess the label of a unlabeled image? Since this is a well established task in machine learning, which provides us good candidates to classification algorithm (SVM, kernel SVM, kNN) we concentrate in the construction of a robust image representation pipeline.

Fisher vectors follow a similar pipeline of many images features used in computer vision, such as Bag of Visual Words [START_REF] Csurka | Visual categorization with bag of keypoints[END_REF], VLAD [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF] and Super Vector [START_REF] Zhou | Image classification using supervector coding[END_REF]. These features are built upon a set of local descriptors (SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] or color features [START_REF] Clinchant | Xrce's participation to imageval[END_REF]). For a given image, local descriptors are first extracted and then mapped by a function parameterized by the distribution of these descriptors. These mapped descriptors are then pooled (either max-pooled, average pooled or some mixture, such as generalized max-pooling [START_REF] Murray | Generalized max pooling[END_REF]) and adapted (e.g. whitening, normalizations, linear operations) before inputted to a classification algorithm (linear SVM, Nearest Neighbors, amount others classification algorithms). The resulting feature is a well established handcrafted representation for image retrieval [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vector[END_REF] and image classification [START_REF] Perronnin | Improving the fisher kernel for largescale image classification[END_REF]. This chapter tries to explore the object classification problem, which consists corresponds to a classify images according to the category of the main object in the image.

We are interested in the distribution used in the mapping of these descriptors and, more specifically, in the descriptors used to learn the distribution and also in how much the final feature representation is independent of background information, i.e., descriptors of parts of the image that do not contain relevant information to the image classification task. Following the theoretical assumption that the Fisher encoding erases background descriptors, we suggest modifications in the standard Fisher vector pipeline in order to obtain a representation dependent only on the object foreground of an image.

Since we start from a theoretical interpretation of how Fisher vectors work, we test our implementation in a variety of datasets, each one representing a different level of complexity:

-A toy dataset where both foreground and background follow their assigned probability distribution and are i.i.d..

-EPFL Car Database [START_REF] Ozuysal | Pose estimation for category specific multiview object localization[END_REF], where different instances of the same object appear in the same background.

-Scene Understanding Database [START_REF] Xiao | Sun database: Largescale scene recognition from abbey to zoo[END_REF], a large dataset categorized by scene types, which we use as a shared background for the foreground objects normally found in these scenes.

Our experiments suggest that two of our central assumptions (Gaussian mixture model calculated separately on different contexts and only in background images) can slightly improve the ratio foreground/background on FV representation, but do not improve classification results in fairly simple object classification tasks. We obtain significant improvements projecting the FV in a subspace that eliminates most of the background information, with or without depending on the foreground information. These results however come with no implicit theoretical justification and can overfit the training example's background.

The contributions of this work are presented as follows:

-We propose a new framework of application of Fisher vectors to context-independent tasks, by aiming to eliminate the background information.

-We introduce a measurement of the foreground-background ratio of information present in a Fisher vector and propose a projection that maximizes it.

-We present results that contradicts the claims of our method and shed light on the statistical formulation used to justify the normalization of Fisher vectors.

Background

We consider the application of Fisher vector and similar image representations to the image classification task. Many hand-crafted image representations consist of extracting, embedding and aggregating local descriptors. These local descriptors, normally SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], RootSIFT [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF] or local color statistics [START_REF] Clinchant | Xrce's participation to imageval[END_REF], can be computed densely or only at interest points. Then, a "visual vocabulary" is learned in an unsupervised way, by applying a clustering algorithm to a set of descriptors and associate each cluster to a "visual word", normally its geometric center. This vocabulary is then used for embedding and aggregation of the local descriptors of an image. The simplest method is the Bag-of-Visual Words (BoW) [START_REF] Csurka | Visual categorization with bag of keypoints[END_REF], where the vocabulary is learned by k-means and each local descriptor is hard-assigned to the word of the vocabulary to which it is the closest. The global feature is given by the average occurrence count of the words, leading to a histogram of visual words appearances. The BoW is amount the most popular pipelines for image classification and, due in part to its simplicity, has been multiple times extended, with soft-assignment [START_REF] Perronnin | Adapted vocabularies for generic visual categorization[END_REF][START_REF] Vangemert | Visual word ambiguity[END_REF][START_REF] Winn | Object categorization by learned visual dictionary[END_REF] that allows for a more complex feature, sparse coding for the visual vocabulary representation of images [START_REF] Boureau | Learning mid-level features for recognition[END_REF][START_REF] Wang | Locality-constrained linear coding for image classification[END_REF][START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF] and implementation of some spatial information of the codewords occurrence with spatial pyramids [START_REF] Labeznik | Beyond bag of features: Spatial pyramid matching for recognizing natual scenes categories[END_REF].

Fisher vectors (FV) are, along side with the vector of locally aggregated descriptors (VLAD) [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF], the handcrafted aggregation of local descriptors that succeed all the variants of BoW. Similarly to BoW, both are aggregation of hard-assigned embedded local descriptors. They differ in their methods for clustering descriptors (VLAD uses K-means, FV uses Gaussian mixtures model) and the residual vector they accumulate (VLAD accumulate derivatives w.r.t. the mean of the clusters, FV accumulate derivatives w.r.t. the mean and standard deviation of the clusters).

Neural network have consistently outperformed handcrafted features in classifications ever since Krizhevsky et al. [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] obtained state-of-the-art of the most challenging classification dataset. Most works that achieve comparable results to [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] nowadays extract low and mid-level descriptors as activations of a similar convolutional architecture [START_REF] Simonyan | Very deep convolutional networks for largescale visual recognition[END_REF][START_REF] Szegedy | Going deeper with convolutions[END_REF]. However, many handcrafted features are still used as part of a neural network architecture. Arandjelović et al. [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] constructed a network with a differentiable VLAD layer aggregate activations of mid-level (conv5) convolutional layers of an existing architecture, and He et al. [START_REF] He | Spatial pyramid pooling in deep convolutional networks for visual recognition[END_REF] used spatial pyramids kernel aggregate activations of convolutional layers of images of different sizes without resizing them.

Fisher vectors

The Fisher vector encoding of an image is based on fitting a Gaussian mixture model (or any other parametric generative model) to a densely computed set of local descriptors, and then encoding first and second-order information as the derivatives of the log-likelihood of the model with respect with to its parameters.

Given an image, we wish to encode it as a Fisher vector (FV). We extract a set 𝑋 = {𝑥 𝑛 } 1≤𝑛≤𝑁 of local descriptors of dimension 𝐷. Let 𝑢 𝜆 denote a probabilistic density function of a Gaussian mixture parametrized by 𝜆 = [𝜆 1 , 𝜆 2 , ..., 𝜆 𝐾 ] 𝑇 , where every 𝜆 𝑖 = {𝜇 𝑖 , 𝜎 𝑖 , 𝛾 𝑖 }, 1 ≤ 𝑖 ≤ 𝐾 is the parameter of one of the Gaussian distributions in the mixture distribution:

𝑢 𝜆 (𝑥) = 𝐾 ∑ 𝑖=1 𝛾 𝑖 𝒩 (𝑥|𝜇 𝑖 , Σ 𝑖 ), (2.1
) The Fisher score 𝑍 𝜆 of the sample 𝑋 is the mean of the score function of all the local descriptors:

𝒩 (𝑥|𝜇 𝑖 , Σ 𝑖 ) = (2𝜋) -𝐷 2 |Σ 𝑖 | -1 2 𝑒 -1 2 (𝑥-𝜇 𝑖 ) 𝑇 Σ -1 𝑖 (𝑥-𝜇 𝑖 ) , (2.2
𝑍 𝜆 (𝑋) = 1 𝑁 𝑁 ∑ 𝑛=1 𝑧 𝜆 𝑛 . (2.4)
Since 𝑓 (𝜆) = log 𝑢 𝜆 (𝑥 𝑛 ) is a scalar function and 𝜇 𝑖 , 𝜎 𝑖 are R 𝐷 vectors, ∇ 𝜇 𝑖 𝑓 (𝜆) and ∇ 𝜎 𝑖 𝑓 (𝜆) are R 𝐷 vectors. Therefore, 𝑍 𝜆 is a R 2𝐷𝐾 vector. We are interested in relative distances between Fisher scores, so we must also find a metric for R 2𝐷𝐾 . Jaakkola and Haussler [START_REF] Jaakkola | Exploiting generative models in discriminative classifiers[END_REF] proposed the metric given by the inner product 𝐾 𝐹 𝐾 (𝑍, 𝑍 ′ ) = 𝑍𝐹 -1 𝜆 𝑍 ′ , where 𝐹 𝜆 is the Fisher information matrix

𝐹 𝜆 = E 𝑥∼𝑢 𝜆 [ ∇ 𝜆 log 𝑢 𝜆 (𝑥)(∇ 𝜆 log 𝑢 𝜆 (𝑥)) 𝑇 ] . (2.5)
Since, by its definition, 𝐹 𝜆 is a symmetric positive-definite matrix, we can obtain a lower-triangular matrix 𝐿 𝜆 by the Cholesky decomposition of the Fisher Information Matrix: 𝐹 -1 𝜆 = 𝐿 𝜆 𝐿 𝑇 𝜆 . Finally, we can obtain the Fisher vector of the samples 𝑋 as

Ψ 𝜆 (𝑋) = 𝐿 𝜆 𝑍 𝜆 (𝑋). (2.6)
Ψ 𝜆 (𝑋) is a 2𝐷𝐾 vector whose relative distance to another Fisher vector can be measured using the 𝑙 2 norm in R 2𝐷𝐾 .

1. In Eq. (2.3), the gradient w.r.t. 𝛾 was omitted on propose. Most applications of Fisher vectors exclude this gradient because it does not add useful information to the derivative w.r.t. the means and variances, as seen on Figure 4 of [START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF]. Also, for an efficient calculation of the encoding of a couple of samples, it is useful to compare their gradients w.r.t. the same Gaussian distribution. Indeed, it can be done, following SSE2 CPU instructions, only if the encoding dimensions is divisible by 4 [START_REF] Kantorov | Efficient feature extraction, encoding and classification for action recognition[END_REF]. By excluding the gradient w.r.t. 𝛾 and choosing 𝐾 even, we speed up our code considerably.

Normalization

Perronnin et al. [START_REF] Perronnin | Improving the fisher kernel for largescale image classification[END_REF] introduced several practices to obtain better results from FV. Here we highlight the practice of normalization, which improves results in classification as seen in [START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF]. These improvements are obtained by applying the following functions to the feature calculated in Eq. (2.6):

𝜙 1 (𝑥) = 𝑠𝑖𝑔𝑛(𝑥)|𝑥| 1 2 ,
(2.7) (2.9)

𝜙 2 (𝑥) = 1 ||𝑥|| 2 𝑥. ( 2

Application of Fisher vectors to classification

Fisher vectors are normally applied on classification using the following interpretation: Let 𝑋 = {𝑥 1 , 𝑥 2 , ..., 𝑥 𝑁 } be the sample of local descriptors of in R 𝐷 an image and 𝑢 𝜆 a function from R 𝐷 to R that represents a Gaussian Mixture Model distribution (GMM) parametrized by 𝜆 = {𝜇 𝑖 , 𝜎 𝑖 , 𝛾 𝑖 } 1≤𝑖≤𝐾 . The Fisher vector Ψ 𝜆 (𝑋) of 𝑋 with respect to 𝜆 is given by the product of the Fisher information matrix 𝐿 𝜆 and global score 𝑍 𝜆 (𝑋): We now assume that we can decompose 𝑝 into two parts, depending on the image: a proportion 𝜔 of the image contains class-specific information, and its descriptors follow a distribution 𝑝 𝑓 𝑔 , whereas the remaining 1 -𝜔 of the image is filled with class-independent background, which follows the distribution 𝑝 𝑏𝑔 . Hence, we write 𝑝(𝑥) = 𝜔𝑝 𝑓 𝑔 (𝑥) + (1 -𝜔)𝑝 𝑏𝑔 (𝑥) and rewrite (2.11) as

𝑧 𝜆 𝑛 = ∇ 𝜆 log 𝑢 𝜆 (𝑥 𝑛 ), 𝑍 𝜆 (𝑋) = 1 𝑁 𝑁 ∑ 𝑛=1 𝑧 𝜆 𝑛 . ( 2
𝑍 𝜆 (𝑋) 𝑎.𝑠. -→𝜔∇ 𝜆 ∫ 𝑥∈R 𝐷 𝑝 𝑓 𝑔 (𝑥) log 𝑢 𝜆 (𝑥)𝑑𝑥 + (1 -𝜔)∇ 𝜆 ∫ 𝑥∈R 𝐷 𝑝 𝑏𝑔 (𝑥) log 𝑢 𝜆 (𝑥)𝑑𝑥.
(2.12) Sánchez et al. [START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF] and many other works suppose that the background descriptors of any image follow the the same probabilistic distribution as the GMM 𝑢 𝜆 used to compute its Fisher vector. Hence, 𝜆 is estimated in order to eliminate the dependency of the global score from the background descriptors, which, from Eq. ( 2 The last equality follows from the fact that 𝜆 maximizes the log-likelihood of the data generated by 𝑢 𝜆 . This allows us to erase the background information of the image. A 𝑙 2 -normalization is proposed by [START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF] as a way to eliminate the proportion 𝜔, thus making the FV encoding robust to changes in scale of the object.

Our model for Fisher vectors

The first problem of Eq. (2.12) is the assumption that the background follows the distribution 𝑢 𝜆 . The distribution 𝑢 𝜆 is learned so that the GMM represent a codebook of the database and must represent discriminative keywords of the classes in the database. Indeed, [START_REF] Jaakkola | Exploiting generative models in discriminative classifiers[END_REF][START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF] learn 𝜆 by optimizing a maximum likelihood with an EM algorithm using local descriptors collected over the whole images. Therefore, the foreground descriptors do not follow a distribution 𝑝 𝑓 𝑔 different from 𝑢 𝜆 ; both foreground and background descriptors follow 𝑢 𝜆 .

We propose to calculate the distribution 𝑢 𝜆 using only the background samples, using object bounding boxes as the boundary between foreground and background.

An alternative modification to the encoding pipeline is to project the non-normalized Fisher vectors along the linear space that maximizes the ratio foreground over background information. This projection is obtained by solving a generalized eigenvalue problem.

Another important problem of the interpretation of Section 2.3 is the variability of the backgrounds. The strength of model is that we can erase the background information, but when a database contains different types of scenes (indoor and outdoor, city and countryside, Brazil and China, etc.), the background information of an image will not be the same as the average information of all the images and the background term in (2.12) will not cancel out. We suggest to solve this by separating images according to the type of background information.

In the following subsections, we are going to detail these modifications to the Fisher encoding.

Separation of foreground and background local features

For a sample of local descriptors 𝑋, we write 𝑋 = 𝑋 𝑓 𝑔 ∪𝑋 𝑏𝑔 , where 𝑋 𝑓 𝑔 ∩𝑋 𝑏𝑔 = ∅, where 𝑋 𝑓 𝑔 and 𝑋 𝑏𝑔 are respectively the set of foreground and background descriptors in 𝑋. In practice, this separation is done using the ground-truth object proposal: 𝑋 𝑓 𝑔 is the set of local descriptors extracted inside the object proposal and 𝑋 𝑏𝑔 = 𝑋∖𝑋 𝑓 𝑔 is its complementary subset of 𝑋. Hence we assume for a dataset of 𝑁 images we use for computing 𝑢 𝜆 , we have the sets of local descriptors {𝑋 (1) , 𝑋 (2) , ..., 𝑋 (𝑁 ) } of images {1, 2, ..., 𝑁 }, and for each sample, the foreground groundtruth is known, i.e., for each image 𝑛 , 𝑋 (𝑛) 𝑓 𝑔 and 𝑋 (𝑛) 𝑏𝑔 are known. Since 𝑢 𝜆 is a GMM, the parameter 𝜆 is obtained by maximizing a log-likelihood problem

We wish to compare two methods of calculation of the distribution 𝑢 𝜆 ; -Full-image (fg+bg) GMM, where all local descriptors are used and proposal ground-truth is unnecessary:

𝜆 𝑓 𝑔+𝑏𝑔 = arg max 𝜆 ⎛ ⎝ 𝑁 ∑ 𝑛=1 ∑ 𝑥∈𝑋 (𝑛) log 𝑢 𝜆 (𝑥) ⎞ ⎠ . (2.15)
-Background (bg) GMM, where we restrict the learning of the distribution to background descriptors:

𝜆 𝑏𝑔 = arg max 𝜆 ⎛ ⎜ ⎝ 𝑁 ∑ 𝑛=1 ∑ 𝑥∈𝑋 (𝑛) 𝑏𝑔 log 𝑢 𝜆 (𝑥) ⎞ ⎟ ⎠ . (2.16)
(Eq. 2.13) is true only if 𝑢 𝜆 = 𝑝 𝑏𝑔 , which implies 𝑢 𝜆 must be parametrized by 𝜆 𝑏𝑔 . However, previous Fisher vectors applications [START_REF] Cinbis | Image categorization using fisher kernerls of non-iid image models[END_REF][START_REF] Perronnin | Large-scale image retrieval with compressed fisher vector[END_REF][START_REF] Perronnin | Improving the fisher kernel for largescale image classification[END_REF][START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF] did not make distinction between foreground and background descriptors, implying their GMM is parametrized by 𝜆 𝑓 𝑔+𝑏𝑔 . We wish to compare both methods of GMM calculation in order to understand if the choice of probability distribution 𝑢 𝜆 influences the result on background information deletion and object classification results. For simplicity of notation, we denote by 𝑢 𝑓 𝑔+𝑏𝑔 and 𝑢 𝑏𝑔 the GMM parametrized by 𝜆 𝑓 𝑔+𝑏𝑔 and 𝜆 𝑏𝑔 , respectively.

Foreground projection

In this section, we propose a linear projection designed to eliminate background information as much as possible preserving foreground information. This projection is inspired by the Linear discriminant analysis algorithm. We expect to see an improvement in object classification as a result of using the projected feature.

For any set 𝑋 of local descriptors, let Ψ(𝑋) be the 2𝐷𝐾-dimension image feature of the sample 𝑋. In training time, we have the sets of local descriptors {𝑋 (1) , 𝑋 (2) , ..., 𝑋 (𝑁 ) } of image samples {1, 2, ..., 𝑁 }, and for each sample, separable in foreground and background descriptors. We define the matrices 𝑀 𝑓 𝑔 and 𝐵 such that

𝑀 𝑓 𝑔 = [ Ψ(𝑋 (1)
𝑓 𝑔 ), Ψ(𝑋

𝑓 𝑔 ), ..., Ψ(𝑋

(𝑁 ) 𝑓 𝑔 ) ] , (2.17) 𝐵 = [ Ψ(𝑋 (1)
𝑏𝑔 ), Ψ(𝑋

𝑏𝑔 ), ..., Ψ(𝑋

(𝑁 ) 𝑏𝑔 ) ] , (2.18)
i.e., the 𝑖-th column of 𝑀 𝑓 𝑔 and 𝐵 are the image feature of, respectively, the foreground and the background of image 𝑖, 𝑖 in {1, 2, ..., 𝑁 }.

We want to find a 𝑑 dimensional projection that maximizes the ratio between the average squared norm of foreground encoding over the average squared norm of background encoding, for some 𝑑 < 2𝐷𝐾. The value of 𝑑 is chosen so that we maximize classification precision. We can write this as finding a R 2𝐷𝐾×𝑑 matrix 𝐴 * argument of the problem basis of its image space:

𝐴 * = 𝑎𝑟𝑔𝑚𝑎𝑥 𝐴∈R 2𝐷𝐾×𝑑 𝑁 ∑ 𝑛=1 ||𝐴 𝑇 Ψ(𝑋 (𝑛) 𝑓 𝑔 )||
𝐴 * = 𝑎𝑟𝑔𝑚𝑎𝑥 𝐴∈R 2𝐷𝐾×𝑑 , 𝑎 𝑇 𝑗 𝐵𝑇 𝑎 𝑗 =1, 1≤𝑗≤𝑑 𝑡𝑟 ( 𝐴 𝑇 𝐹 𝐴 ) (2.23) ℒ(𝐴, 𝜈) = 𝑡𝑟 ( 𝐴 𝑇 𝐹 𝐴 ) + 𝜈 ( 1 -𝑡𝑟 ( 𝐴 𝑇 𝐵𝐴 )) (2.24) = 𝑑 ∑ 𝑗=1 𝑎 𝑇 𝑗 𝐹 𝑎 𝑗 + 𝑑 ∑ 𝑗=1 𝜈 𝑗 ( 1 -𝑎 𝑇 𝑗 𝐵𝑎 𝑗 ) (2.25) 𝜕 𝜕𝑎 𝑗 ℒ(𝐴, 𝜈) = 2𝐹 𝑎 𝑗 -2𝜈 𝑗 𝐵𝑎 𝑗 , (2.26)
𝜕 𝜕𝑎 𝑗 ℒ(𝐴, 𝜈) = 0 ⇒ (𝐹 -𝜈 𝑗 𝐵)𝑎 𝑗 = 0, (2.27)
i.e., 𝑎 𝑗 is an eigenvector of the matrix 𝐵 -1 𝐹

Contextual Fisher vectors

Groups of images and context A solution to the problem of variability of the backgrounds is to separate the training images accordingly with different types of image depending on their background type (i.e., contextual information about where the photo was taken), learn a mixtures of Gaussians for each of these groups and calculate the Fisher vector of an image w.r.t. each of these GMM. We assume we can divide any set of images in different contexts, where a context is defined as a subset of images that share the same type of image, in such a way that an image in this set is contained in exactly one context. Under this assumption, having one GMM for every context and calculating, for every image, the FV with respect to each GMM, every image we will have only one background-free Fisher vector, i.e. one Fisher vector for which (2.12) and (2.14) are true. This is the FV corresponding to the context in which the image is contained. Also, we can not concatenate these different FV into one vector, or else the size can become a prohibitive factor.

Separation by context We will assume that each one of the training image is associated to one context 𝑐 ∈ {1, 2, ..., 𝐶} out of 𝐶 possible ones in the training images set. We fix the number 𝐾 of Gaussians we want every mixture to have. Each context 𝑐 is then associated to a probabilistic density 𝑢 𝜆𝑐 , with parameters 𝜆 𝑐 = [𝜆 𝑐1 , 𝜆 𝑐2 , . . . , 𝜆 𝑐𝐾 ] is calculated as the GMM parameter learned from the images of this context. Here, 𝜆 𝑐𝑘 = (𝜇 𝑐𝑘 , 𝜎 𝑐𝑘 , 𝛾 𝑐𝑘 ) is the parameters of the 𝑘-th gaussian of the c-th context.

Moment matrices In (2.12), the background information was erased because 𝜆 was optimized such that

∇ 𝜆 E 𝑥∼𝑢 𝜆 [log 𝑢 𝜆 (𝑥)] = ∇ 𝜆 ∫ 𝑥∈R 𝐷 𝑢 𝜆 (𝑥) log 𝑢 𝜆 (𝑥)𝑑𝑥 = 0. (2.28)
However, in the presence of many contexts and since the context of an image is hidden information, Eq. (2.28) does not hold for every couple samples-context. We obtain the elimination of the background term in (2.12) if the samples 𝑋 are in the same context with respect which we calculate the Fisher vector. We therefore denote the moment matrix between the contexts 𝑖, 𝑗 ∈ {1, 2, ..., 𝐶}, by

𝐴 𝑖𝑗 = 𝐷 𝜆 𝑖 ( E 𝑥∼𝑢 𝜆 𝑗 [log 𝑢 𝜆 𝑖 (𝑥)] ) = 𝐷 𝜆 𝑖 (∫ 𝑥∈R 𝐷 𝑢 𝜆 𝑗 (𝑥) log 𝑢 𝜆 𝑖 (𝑥)𝑑𝑥 ) , (2.29)
where

𝐷 𝜆 𝑓 (𝜆) = ( ∇ 𝜇 1 𝑓 (𝜆) ∇ 𝜇 2 𝑓 (𝜆) . . . ∇ 𝜇 𝐾 𝑓 (𝜆) ∇ 𝜎 1 𝑓 (𝜆) ∇ 𝜎 2 𝑓 (𝜆) . . . ∇ 𝜎 𝐾 𝑓 (𝜆) ) . (2.30)
Note that 𝐴 𝑖𝑖 = 0 and 𝐴 𝑖𝑗 is a 2𝐷 × 𝐾 matrix, where each one of the 𝐾 columns is a vector in R 2𝐷 and the 𝑘-th column corresponds to the derivative with respect to 𝜆 𝑖𝑘 . Consider the following homogeneous system under constraints on 𝑣 in R 𝐾 :

{ 𝐴 𝑖𝑗 𝑣 = 0, ∀1 ≤ 𝑗 ≤ 𝐶, 𝑗 ̸ = 𝑖, ||𝑣|| 2 = 1. (2.31)
We call 𝑁 𝑖 , one of the solutions of Eq. (2.31), the normal to the residual moment of the context 𝑖. We can only guarantee the existence of a solution to Eq. (2.31) if 2𝐷(𝐶 -1) < 𝐾. Otherwise, we can not guarantee the existence of a non-trivial solution of a homogeneous system of 𝐾 variables and 2𝐷(𝐶 -1) equations. The values of 𝐷, 𝐾 and 𝐶 must be chosen such that this inequality is true.

Construction of CFV We denote by 𝜓 𝑖 (𝑋), 𝑖 ∈ {1, 2, ..., 𝐶} a 2𝐷 × 𝐾 matrix constructed by rearranging in order the entries of the Fisher vector Ψ 𝜆 𝑖 (𝑋) along the lines of the matrix, i.e.,

𝒵 𝑖 (𝑋) = ⎛ ⎜ ⎜ ⎜ ⎝ 𝑍 𝜆 𝑖 (𝑋) 1 𝑍 𝜆 𝑖 (𝑋) 2𝐷+1 . . . 𝑍 𝜆 𝑖 (𝑋) 2𝐷(𝐾-1)+1 𝑍 𝜆 𝑖 (𝑋) 2 𝑍 𝜆 𝑖 (𝑋) 2𝐷+2 . . . 𝑍 𝜆 𝑖 (𝑋) 2𝐷(𝐾-1)+2 . . . . . . . . . . . . 𝑍 𝜆 𝑖 (𝑋) 2𝐷 𝑍 𝜆 𝑖 (𝑋) 4𝐷 . . . 𝑍 𝜆 𝑖 (𝑋) 2𝐷𝐾 ⎞ ⎟ ⎟ ⎟ ⎠ . (2.32)
We can rewrite Eq. (2.11) for 𝒵 𝑖 (𝑋) by equally rewriting Eq. ( 2.3) with a different arrangement. We have

𝒵 𝑖 (𝑋)→ 𝑎.𝑠. 𝐷 𝜆 𝑖 (∫ 𝑥∈R 𝐷 𝑝(𝑥) log 𝑢 𝜆 𝑖 (𝑥)𝑑𝑥 ) , (2.33)
for any 𝑖 in {1, 2, ..., 𝐶}. Let 𝑞 denote once again the distribution followed by the local descriptors of an object class. Now, from our hypothesis that every image is contained in exactly one context, there is an 𝜔 in [0, 1] and 𝑗 in {1, 2, ..., 𝐶} such that 𝑝(𝑥) = 𝜔𝑞(𝑥) + (1 -𝜔)𝑢 𝜆 𝑗 (𝑥). Then, we can introduce this equality in equation above, obtaining an equivalent to (2.12)

𝒵 𝑖 (𝑋)→ 𝑎.𝑠. 𝜔 ∇ 𝜆 𝑖 ∫ 𝑥∈R 𝐷 𝑞(𝑥) log 𝑢 𝜆 𝑖 (𝑥)𝑑𝑥 ⏟ ⏞ 𝑓 𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑞 𝑎𝑛𝑑 𝑖 +(1 -𝜔)𝐴 𝑖𝑗 .
(2.34)

𝒵 𝑖 (𝑋)𝑁 𝑖 → 𝑎.𝑠. 𝜔 ( ∇ 𝜆 𝑖 ∫ 𝑥∈R 𝐷 𝑞(𝑥) log 𝑢 𝜆 𝑖 (𝑥)𝑑𝑥 ) 𝑁 𝑖
The first thing to note in (2.34) is that it is valid for context 𝑖, independent if it is the background type of the samples 𝑋. Secondly, the first term depends only on the class-specific function 𝑞 and context 𝑖 with respect which we calculated the Fisher encoding. Finally, the last term is proportional to the moment matrix corresponding to 𝑖 and 𝑗, and all of its lines are orthogonal to 𝑁 𝑖 , independent of 𝑗.

𝜓 𝑖 (𝑋) = 𝐿 𝜆 𝒵 𝑖 (𝑋) (2.35)
Thus, 𝜓 𝑖 (𝑋)𝑁 𝑖 is a 2𝐷 + 1 vector and converges almost surely to a function that does not depend on its background type, which means we are able to erase its background information.

We can finally define the CFV of the sample 𝑋 as given by

Φ(𝑋) = [𝜓 1 (𝑋)𝑁 1 ; 𝜓 2 (𝑋)𝑁 2 ; ..., 𝜓 𝐶 (𝑋)𝑁 𝐶 ]. (2.36)
Φ(𝑋) is a vector of dimension 2𝐷𝐶.

Datasets

Toy database

Firstly, we test our hypothesis in artificially generated data that simulates perfectly the assumptions of Subsection 2.3.2:

-Local descriptors of an image are i.i.d..

-Background descriptors follow a mixture of 128 Gaussian distributions; -We suppose foreground descriptors follow a GMM of 𝑞 Gaussian distributions.

-The parameters of both 𝑝 𝑓 𝑔 and 𝑝 𝑏𝑔 are randomly generated.

-For a sample of size 𝑁 of an image, ⌊𝜔𝑁 ⌋ of these descriptors are foreground descriptors and the remaining ⌈(1 -𝜔)𝑁 ⌉ are background descriptors. We fix the descriptors' dimensions 𝐷 = 64 to imitate the PCA-SIFT dimension.

EPFL car database

For the preliminary experiences, in used the EPFL multi-views Car Database [START_REF] Ozuysal | Pose estimation for category specific multiview object localization[END_REF]. This dataset contains 20 sequences of cars as they rotate 360 degrees. There is one image approximately every 3-4 degrees. For our experiment, we grouped some cars that share the same background and make it a context, as seen in Fig. 2-1. We created 2 contexts from 6 cars; context 1 contains 436 images of 4 cars and context 2 contains 234 images of 2 cars. For each context, we calculated a context specific GMM. The general context GMM is learned from samples from both contexts and samples from the remaining images not included in any context. Using the fact that this database has ground-truth bounding boxes for the objects, we can calculate the GMM of each context using only background local descriptors, as described in Eq. (2.16), and compare the Fisher encoding for 𝑢 𝑓 𝑔+𝑏𝑔 and 𝑢 𝑏𝑔 .

SUn database

Scene Understanding (or SUn) [START_REF] Xiao | Sun database: Largescale scene recognition from abbey to zoo[END_REF] database consists of 130k images labeled in about 900 scenes categories and 4000 object categories. The object boundaries are handily labeled by the online annotation tool LabelMe. We use images of the same scene category as images of the same context and calculate one GMM for each context. Differently from the previous dataset, SUn database's images present more variability in scenes and objects, and hence is more suited to report classification results.

Our experiments are conducted in images of four scene categories (highway, street, bathroom and building facade) and three object classes (person, car and toilets).

These scenes and object categories are chosen such that each object can be associated to at least one context (toilet to bathroom, person to street, car to street and highway) and pairs of contexts can be identified as similar and therefore more ambiguous (such as street and highway) or distinct and easier to differentiate (such as highway and bathroom).

Experiments

Experimental setup

All images in each dataset are resized at 1000 × 1000. The sample of local descriptors we used in this work is dense SIFT. These descriptors are extracted from 6 × 6, 12 × 12 and 24 × 24 patches on a regular grid every 4 pixels. The 128 dimensional SIFT descriptor is reduced to 64 dimensions using PCA.

One inconvenient of using SIFT of such small patches is the proportion of null gradient patches, giving a null local descriptor. These null descriptors represent an important proportion of the samples and do not cluster with any other local descriptor. By calculating the a GMM using these samples, the biggest Gaussian (by number of elements generated) have zero mean and a variance much smaller than other clusters. Sánchez et al. [START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF] deal with null descriptors with what they call 'variance flooring': impose a minimum value to the variance of the clusters. However, the gradient of the log-likelihood w.r.t. the variance where the mean is zero does not depend on its variance nor on the samples size, meaning it does not converge as expected in Eq. (2.12). We decided then to dropout the null local descriptors.

On training time, we first separate images according to context. This is usually done using labels of scenes categories as label of context. Using ground-truth bounding boxes, we extract dense SIFT over the background of images only to compute background GMM. We gather around 10 6 descriptors of each context, reduce dimensionality with PCA and learn 𝜆 by solving Eq. 2.16. We also calculate a general context GMM, using samples of all contexts and solving Eq. 2.15, to compare its performance to the context specific GMM.

Following the observations of Sánchez et al. [START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF] that the gradient w.r.t. the prior probabilities does not impact the average precision of Fisher vectors in classification takes and slows down Fisher vector calculation, we consider only the gradients w.r.t. the mean and the variance of each Gaussian distribution. The final encoding of a samples has thus size 2𝐷𝐾, where 𝐷 = 64 is the dimension of the resized PCA-SIFT descriptor and 𝐾 is the number of Gaussian distribution.

Foreground-background ratio

In order to measure the elimination of background information of a samples 𝑋, we define the ratio 𝑟 of the FV calculated over the foreground descriptors and the FV calculated over the background descriptors. We define 𝑟 as a function of the separable sample 𝑋 = 𝑋 𝑓 𝑔 ∪ 𝑋 𝑏𝑔 as being

𝑟(𝑋, 𝜆) = ||Ψ 𝜆 (𝑋 𝑓 𝑔 )|| ||Ψ 𝜆 (𝑋 𝑏𝑔 )|| . (2.37)
Given our theoretical assumptions stated in Section 2.4, we expect to obtain higher values of foreground-background ration:

-For background GMM-calculated FV w.r.t. full-image GMM-calculated FV.

-For context-specific GMM-calculated FV w.r.t general-context GMM-calculated FV.

Toy experiments.

In each of the following experiments, after fixing 𝑞 and randomly assign the parameters of a GMM of 𝑞 Gaussian distributions as the probability distribution of the foreground descriptors, we generate foreground and background descriptors following its respective distributions. We learn a GMM of 𝐾 Gaussian distributions from the background descriptors, for 𝐾 in {2, 4, 8, 16, 32, 64, 128}. for several foreground classes, each following a randomly generated functions 𝑞 where we increase the number of Gaussian distributions. We observe that the complexity of the foreground distribution 𝑞 does not impact the ratio as much as the complexity of the background distribution. Indeed, we observe a linear drop in 𝑙𝑛(𝑟) -thus an exponential drop in 𝑟 -for exponential increases of 𝐾. These results indicate that the hypothesis of a Fisher vector mostly independent of background information applies better to simple background information, and this can be noted in our simplified data.

Figure 2-8 presents changes in other simulated variable, namely the size 𝑁 of the sample 𝑋 and the fraction 𝜔 of foreground descriptors in 𝑋. The ration 𝑟 increases as the size 𝑁 increases and as the proportion 1 -𝜔 of the background descriptors increases. These indicate that as the sheer number of background descriptors increases we are closer to the convergence hypothesized in Eq. (2.11). For all cases, we observe decreasing average value of 𝑟 as 𝐾 increases. Despite measuring the dependency of a representation to the foreground information, 𝑟 does not measure if this representation of the foreground is discriminative. Indeed, higher values of 𝐾 better approximate the background distribution and improve classification results [START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF].

Background GMM vs full image GMM

Calculating the GMM parameter 𝜆 only on background descriptors is our first assumption. For each of the following experiments, we compare the average and standard deviation of 𝑟(𝑋, 𝜆 𝑏𝑔 ) and 𝑟(𝑋, 𝜆 𝑓 𝑔+𝑏𝑔 ) over a set of images. We calculate these GMM for different numbers of Gaussian distributions 𝐾 and plot the 𝑙𝑛(𝑟) over 𝐾.

Toy database. Figure 2-9 compares the ratios for a set of 𝑁 = 10000 descriptors, generated from two mixtures of 128 Gaussian models each; 1000 from the foreground GMM, 9000 from the background GMM (i.e., 𝜔 = 0.1). We learn 𝜆 𝑏𝑔 and 𝜆 𝑓 𝑔+𝑏𝑔 from these descriptors for different values of 𝐾 and plot 𝑙𝑛(𝑟) for each 𝐾. We observe a higher ratios 𝑟 on background GMM (in blue) for all values of 𝐾 w.r.t. full-image GMM (in red).

EPFL cars. We repeat the experiment for EPFL cars. We solve Eq.(2.15) and Eq. (2.16) on general context, i.e., we do not separate descriptors in their contexts. Results are shown in Fig. 23456789. On average, ratio 𝑟 is higher for background GMM, but contrary to the results for toy database, we observe a higher standard deviation and a large overlap of ratios. The results also show smaller values of 𝑟 compared to toy database, and that both 𝑟(𝜆 𝑏𝑔 ) and 𝑟(𝜆 𝑓 𝑔+𝑏𝑔 ) increase for larger number of Gaussian distributions 𝐾, contrary to toy database. Interestingly, the average ratio 𝑟(𝜆 𝑏𝑔 ) is bigger than 1, (i.e., the norm of the foreground feature is bigger than the background feature), whereas the average 𝑟(𝜆 𝑓 𝑔+𝑏𝑔 ) is smaller than one (the norm of the background feature is bigger than the foreground feature).

Context GMM

The experiments in this subsection test the hypothesis of context-specific GMM improving the ratio 𝑟 w.r.t. general-context GMM.

EPFL cars. We compare the ratio 𝑟(𝜆 𝑏𝑔 ) for each of the contexts of EPFL cars database. We calculate one GMM for each context and one general-context GMM. Fig. 2-10 compares the ratio for all three GMM: in blue, the GMM of the correct context, in red the wrong context (i.e., the GMM calculated on the images of the other context) and in black the general context. We obtain the expected ratio improvements. Indeed, the proper-context GMM consistently perform higher average ratio then both general-context GMM and the GMM for the other context. For context 1, we obtain a clear separation, whereas context 2 has higher standard deviation and the improvement w.r.t. the general-context GMM is smaller. Instead, we observe a higher number of images with foreground-background ratios smaller than 1 and also a higher standard deviation. SUn database. We repeat this experiment for SUn database, that present a higher variability intra-context. We calculate one GMM for each of the four contexts and one general-context GMM, taking descriptors from the background all four contexts. We compare, for each context, 𝑟(𝜆 𝑏𝑔 ) of its proper context GMM (in blue) and 𝑟(𝜆 𝑏𝑔 ) of the general-context GMM. Results are shown in Fig. 2-12. Differently for EPFL cars, we observe no improvement of ratio when using context-specific GMM. The generalcontext GMM obtain similar average ratios (around exp(0.5)) across all contexts. The context-specific GMM for highway and building facade obtain higher average ratios then general-context but within its standard deviation. It is interesting to note that bathroom, despite being the most distinguishable among the contexts (e.g., for being the only indoor scene category), has the least amount of change of ratio from context GMM to general-context GMM. We conclude from these experiments that the context separation is only significant relative simpler, more uniform scene categories as context. For a complex database such as SUn, the distribution of local descriptors' intra-context is as good for modeling one particular image's background as the distribution of local descriptors from all contexts.

Since the context-specific GMM failed to eliminate background information better than general-context GMM, we do not proceed the application of CFV to classification, as we have no theoretical grounding.

Classification with projected Fisher vector

In this subsection, we compare object classification results for FV as implemented in [START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF] and our projected FV in SUn database. For simplicity, we learn a 16-Gaussian distributions GMM. We classify with a linear SVM and compare methods by their average accuracy. For each experiment, we restrict the set of images to the images of a scene category. For example, we classify toilet for images of bathroom and cars for images of highway.

In these experiments, we plot the average accuracy by the dimension 𝑑 of our projection. Figure 2-13 and Figure 2-14 show the results of the projected FV (in blue) against the results of FV (in black) 3 . The experiments of cars in highway and toilet in bathroom are the only that show the expected result: a curve on 𝑑 that ascends above the performance of FV at a small dimension (around 𝑑 = 300 for both cases) before descending and coinciding with FV for 𝑑 = 2𝐷𝐾. unsuccessful applications of our projection.

Conclusion

We propose a novel framework for Fisher vectors as a context-independent image representation, which is useful for object-based application such as object classification. We start from a statistical formulation present over most of the literature that justifies the elimination of background local descriptors and try to modify our representation in order to better fit this formulation. These modifications consist of:

-Gaussian mixture models that describe only background descriptors instead of full images.

-Projection of Fisher vectors over components that eliminate background information.

-Separation of images in contexts and calculation of one Fisher vector per context for all images, concatenated in a new context-free image representation called Although the modifications proposed improve the foreground-background ratio for a hypothetical data that follows all assumptions and simple image contexts, these ratio improvements are not observed for more complex datasets that are coherent with the datasets used for classification today. While we are able to create larger foreground-background ratios with a projected Fisher vector, these do not improve performance for object classification.

The work presented in this chapter presents no published material as we judge our negative results are not fitting to most conferences. However, we believe our experiments present an interesting counter-argument to the formulation of Subsection 2.3.2, as we suppose it consists of an a posteriori formulation used to justify the normalization of Fisher vectors for improving performance in a classification task. Furthermore, the improved performance obtained by addition of background components to our projected Fisher vector suggests that contextual information is indeed useful for object-based classification.

Chapter 3

Square-loss Exemplar Machines for Image Retrieval

Zepeda and Pérez [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF] have recently demonstrated the promise of the exemplar SVM (ESVM) as a feature encoder for image retrieval. This paper extends this approach in several directions: We first show that replacing the hinge loss by the square loss in the ESVM cost function significantly reduces encoding time with negligible effect on accuracy. We call this model square-loss exemplar machine, or SLEM. We then introduce a kernelized SLEM which can be implemented efficiently through low-rank matrix decomposition, and displays improved performance. Both SLEM variants exploit the fact that the negative examples are fixed, so most of the SLEM computational complexity is relegated to an offline process independent of the positive examples. Our experiments establish the performance and computational advantages of our approach using a large array of base features and standard image retrieval datasets. This chapter is an extended version of the paper "Square-loss examplar machines for image retrieval " by Rezende, Zepeda, Ponce, Bach and Pérez published in CVPR 2017 [START_REF] Rezende | Square loss exemplar machines for image retrieval[END_REF].

Introduction

The exemplar support vector machine (ESVM), originally proposed by Malisiewicz et al. [START_REF] Malisiewicz | Ensemble of exemplar-svms for object detection and beyond[END_REF], leverages the availability of large, unannotated pools of images within the context of supervised learning. It uses a large generic pool of images as a set of negative examples, while using a single image (the exemplar ) as a positive example. Given these training sets, an SVM classifier is learned that can generalize well, despite the drastically limited size of the set of positive examples. This classifier has successfully been used in classification, object detection and label transfer [START_REF] Malisiewicz | Exemplar-svms for visual object detection, label transfer and image retrieval[END_REF]. Zepeda and Pérez [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF] have proposed to treat instead the weights of the resulting classifier as a new feature vector for image retrieval. An ESVM feature is computed for each database and query image, by treating it as the only positive sample while keeping a fixed pool of generic negative images. Searching amounts to computing distances between the query and database ESVM features. Note that ESVM features can be derived from arbitrary base features (e.g., CNN activations) of the exemplar and the images in the generic negative pool.

One drawback of the ESVM feature encoding approach is that computing the classifier requires solving an optimization problem for each positive example (i.e., each query and each database image). This can be time consuming for the large negative pool sizes required for good ESVM feature performance. In this work, we propose using the square loss instead of the hinge loss, in effect converting the ESVM problem into a ridge regression, one that can be solved in closed form. We dub the corresponding classifier a square-loss exemplar machine (or SLEM). The square loss has been used before to replace the hinge loss in classification tasks (e.g., [START_REF] Suykens | Least squares support vector machines[END_REF][START_REF] Ye | Svm versus least squares svm[END_REF]), and to compare ESVMs to classical classifiers such as the linear discriminant analysis (LDA) [START_REF] Kobayashi | Three viewpoints toward exemplar-svm[END_REF]. In contrast, we propose here to use SLEMs as feature encoders for image retrieval.

Since computing the SLEM features requires inverting a large matrix related to the training set's covariance matrix, we propose an efficient way to compute this inverse. Similarly to the cross-validation method of residual error of [START_REF] Cawley | Efficient cross-validation of kernel fisher discriminant classifiers[END_REF], we exploit the fact that only a single (positive) example changes in the training set when computing SLEM features for different images. We show experimentally that our representation matches and even improves upon the performance of ESVM features on three standard datasets using a wide range of base features at a fraction of the original computational cost.

The contributions of this work are threefold:

-We introduce a kernelized variant of SLEM that enjoys similar computational advantages and improves retrieval performances.

-We propose a low-rank factorization of the kernel matrix for computational and storage efficiency.

-Our experiments show improved results on a variety of base features and we obtain state-of-the-art results for Inria Holidays dataset.

Background

Exemplar classification

The exemplar support vector machine, originally proposed by Malisiewicz et al. [START_REF] Malisiewicz | Ensemble of exemplar-svms for object detection and beyond[END_REF], leverages the availability of large, unannotated pools of images within the context of supervised learning. This classifier has successfully been used in classification, object detection and label transfer [START_REF] Malisiewicz | Exemplar-svms for visual object detection, label transfer and image retrieval[END_REF].

Shrivastava et al. [START_REF] Shrivastava | Data-driven visual similarity for cross-domain image matching[END_REF] incorporates a linear exemplar classifier in an image matching framework. The classifier obtained is used as scoring function, as it is obtained from discriminating the sample positive image (called exemplar) from the pool of "background" images. Aytar and Zisserman [START_REF] Aytar | Enhancing exemplar svms using part level transfer regularization[END_REF][START_REF] Aytar | Part level transfer regularization for enhancing exemplar svms[END_REF] propose an enhanced ESVM framework for pose-based object retrieval. It fits the exemplar classifier to a ridge regression of a learned vocabulary of part-level features. This formulation suppresses false negatives successfully, but its usefulness is constrained by the learning of this vocabulary, which requires more positive data for a supervised learning the parts (or, in case of parts learned from a different dataset, a compatible set of objects) and a geometryaware feature representation (i.e. HOG descriptors [START_REF] Dalal | Histogram of oriented gradients for human detection[END_REF]).

Zepeda and Pérez [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF] have proposed to treat instead the weights of the resulting classifier as a new feature vector for image retrieval. Where previous methods used the exemplar classifier for ranking the established representations, i.e. scoring the images by the inner product of its representation and the classifier, this work suggests to use the classifier as the representation: The inner product of two classifiers measures the similarity between the corresponding images.

Image retrieval

A suitable image representation for content-based image retrieval must support effective (discriminative) and efficient (fast) comparisons between a query picture and images stored in some large database. These representations must be robust to large image variations due to camera pose, color differences and scene illumination, amongst others.

Many successful approaches to image retrieval rely on unsupervised models of codebook learning, such as 𝐾-means [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF] or Gaussian mixtures [START_REF] Perronnin | Improving the fisher kernel for largescale image classification[END_REF][START_REF] Sánchez | Image classification with fisher vector: Theory and practice[END_REF]. These approaches aggregate local descriptors of an image by weighted average [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vector[END_REF], triangular embedding [START_REF] Jégou | Triangulation embedding and democratic aggregation for image search[END_REF] or generalized max-pooling [START_REF] Murray | Generalized max pooling[END_REF] into a global feature descriptor. Before the neural networks renaissance, these representations usually outperformed methods that exploit supervised learning of image features directly [START_REF] Bilen | Learning sparsity inducing analysis operators for discriminative similarity metrics[END_REF][START_REF] Rana | Feature learning for the image retrieval task[END_REF].

Today, with the success of convolutional architectures, global image descriptors are often obtained by aggregating and/or pooling their last convolutional layers, by fine-tuning existing models or by addition of new differentiable layers to an existing architecture. Babenko and Lempitisky [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF] introduced the idea of a weighted sumpooling, called SPoC, of the final layer of the state-of-the-art architecture for image recognition trained on ImageNet [START_REF] Simonyan | Very deep convolutional networks for largescale visual recognition[END_REF]. This model is effective and yet very simple. Later works built upon this idea by proposing the learning of the convolutional layers and more sofisticated pooling methods. Kalanditis et al. [START_REF] Kalantidis | Cross-dimensional weighting for aggregated deep convolutional features[END_REF] introduced a crossdimensional weighted (CroW) aggregation, with spatially-localized pooling followed weighted sum-pooling across all channels. Tolias et al. [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF] encodes several image regions, max-pools and aggregates them into a compact feature. This aggregation method, called RMAC, is choosen by Gordo et al. [START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF] as a pooling method in an end-to-end learned architecture.

Radenović et al. [START_REF] Radenović | Cnn image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF] fine-tunes a CNN from a large set of unlabeled images. A 3D model of these images is obtained from a Structure from Motion (SfM) method. This model is used to determine the selection of training data for the fine-tuning of the neural network. Finally, Arandjelović et al. [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] implements a differentiable variant of a VLAD [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF] layer in order to learn end-to-end a robust feature for scene recognition.

The resulting neural network produces state-of-the-art features for some of the most important benchmarks datasets for content-based retrieval. Even if the produced global feature is not as compact as some of the previously mentioned above, a lower dimension representation is obtained by PCA and whitening.

The square-loss exemplar machine

In this section, we revisit the exemplar SVM model proposed in [START_REF] Malisiewicz | Ensemble of exemplar-svms for object detection and beyond[END_REF] as an instance of a more general family of classifiers. Then, we introduce the square loss exemplar machine (SLEM) as a simple variant of this model and study its properties.

Exemplar classifiers

We are given base features in R 𝑑 at training time, one positive example 𝑥 0 in R 𝑑 and a set of negative examples 𝑋 = [𝑥 1 , 𝑥 2 , ..., 𝑥 𝑛 ] in R 𝑑×𝑛 , each column of 𝑋 representing one example by a vector in R 𝑑 . We are also given a loss function 𝑙 : {-1, 1} × R → R + . Learning an exemplar classifier from these examples amounts to minimizing the function

𝐽(𝜔, 𝜈) = 𝜃 𝑙(1, 𝜔 𝑇 𝑥 0 + 𝜈) + 1 𝑛 𝑛 ∑ 𝑖=1 𝑙(-1, 𝜔 𝑇 𝑥 𝑖 + 𝜈) + 𝜆 2 ‖𝜔‖ 2 , (3.1)
w.r.t. 𝜔 in R 𝑑 and 𝜈 in R. In Eq. (3.1), 𝜆 and 𝜃 are respectively a regularization parameter on 𝜔 and a positive scalar adjusting the weight of the positive exemplar.

Given a cost 𝑙, we define the corresponding exemplar classifiers of 𝑥 0 with respect to 𝑋 as the weights 𝜔 ⋆ (𝑥 0 , 𝑋) that minimizes the loss function 𝐽:

( 𝜔 ⋆ , 𝜈 ⋆ ) = arg min (𝜔,𝜈)∈R 𝑑 ×R 𝐽(𝜔, 𝜈). 1 (3.2)
The exemplar SVM [START_REF] Malisiewicz | Ensemble of exemplar-svms for object detection and beyond[END_REF][START_REF] Malisiewicz | Exemplar-svms for visual object detection, label transfer and image retrieval[END_REF] is an instance of this model where 𝑙 is the hinge loss, which is convex. The solution of Eq. (3.2) can thus be found by stochastic gradient descent [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF] individually for each positive sample, as it has been done by Malisiewicz et al. [START_REF] Malisiewicz | Ensemble of exemplar-svms for object detection and beyond[END_REF][START_REF] Malisiewicz | Exemplar-svms for visual object detection, label transfer and image retrieval[END_REF] and Zepeda and Pérez [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF]. The next section shows how to calculate all exemplar classifiers simultaneously by changing the loss function.

The square loss

Now, let us study the same learning problem for the square-loss function 𝑙(𝑦, ŷ) = 1 2 (𝑦 -ŷ) 2 . As in the case of the hinge loss, the minimization of Eq. (3.1) is a convex problem.

1. Depending on the loss function 𝑙, 𝜈 ⋆ (𝑥 0 , 𝑋) may not be unique.

However it is now a ridge regression problem, whose unique solution can be found in closed form as

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 𝜔 ⋆ = 2𝜃 𝜃 + 1 𝑈 -1 (𝑥 0 -𝜇), 𝜈 ⋆ = 𝜃 -1 𝜃 + 1 - 1 𝜃 + 1 (𝜃𝑥 0 + 𝜇) 𝑇 𝜔 ⋆ , (3.3)
where:

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ 𝜇 = 1 𝑛 ∑ 𝑛 𝑖=1 𝑥 𝑖 , 𝑈 = 1 𝑛 𝑋𝑋 𝑇 -𝜇𝜇 𝑇 + 𝜃 𝜃+1 (𝑥 0 -𝜇)(𝑥 0 -𝜇) 𝑇 + 𝜆Id 𝑑 , (3.4)
where Id 𝑑 is the identity matrix of size 𝑑. Woodbury identity. We can simplify Eq. (3.3) by modifying 𝑈 in Eq. (3.4). Let us define 𝐴 = 1 𝑛 𝑋𝑋 𝑇 -𝜇𝜇 𝑇 + 𝜆Id 𝑑 as the regularized covariance matrix and assume its inverse 𝐴 -1 known. The matrix 𝑈 now reads 𝑈 = 𝐴 + 𝜃 𝜃+1 𝛿𝛿 𝑇 , where 𝛿 = 𝑥 0 -𝜇 is the centered (w.r.t. the negatives' mean) positive sample. The Woodbury identity [START_REF] Woodbury | Inverting modified matrices[END_REF] gives us

𝑈 -1 = 𝐴 -1 - 𝜃 𝜃𝛿 𝑇 𝐴 -1 𝛿 + 𝜃 + 1 𝐴 -1 𝛿𝛿 𝑇 𝐴 -1 . (3.5)
Substituting (3.5) in (3.3) yields

𝜔 ⋆ = 2𝜃 𝜃 + 1 ( 𝐴 -1 𝛿 - 𝜃 𝜃𝛿 𝑇 𝐴 -1 𝛿 + 𝜃 + 1 𝐴 -1 𝛿(𝛿 𝑇 𝐴 -1 𝛿) ) = 2𝜃 𝜃𝛿 𝑇 𝐴 -1 𝛿 + 𝜃 + 1 𝐴 -1 𝛿. (3.6)
Equation (3.6) shows how to compute many exemplar classifiers simultaneously, by solving a single linear system in 𝐴. Also note that the positive sample weight 𝜃 does not influence the direction of the optimal vector 𝜔 ⋆ , only its norm. This means that if search and ranking are based on the normalized feature 1 ‖𝜔 ⋆ ‖ 𝜔 ⋆ , e.g., using cosine similarity, 𝜃 does not influence the matching score of the SLEM vectors of two different images. This sets SLEM appart from ESVM which requires this parameter to be calibrated [START_REF] Malisiewicz | Ensemble of exemplar-svms for object detection and beyond[END_REF][START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF]. We can thus set the value of 𝜃 to any positive real number.

LDA and SLEM

It is interesting to note the relationship between SLEM and the classical linear discriminant analysis (LDA). Let us return to Eq. (3.1) and suppose that we have multiple positive samples. It can be shown that in this case, the corresponding linear classifier of Eq. (3.1) for the square loss is also given by (3.3), where 𝑥 0 denotes this time the center of mass of the positive samples if the positives have the same covariance matrix Σ as the negative samples 𝑋.

This equal-covariance assumption is of course quite restrictive, and probably unrealistic in general. It is interesting to note, however, that this is exactly the assumption made by linear discriminant analysis. As shown in [START_REF] Hastie | The elements of statistical learning[END_REF] for example, LDA is a (nonregularized) linear classifier with decision function 𝜔 𝑇 𝑥 + 𝜈, where

𝜔 = Σ -1 (𝑥 0 -𝜇), 𝜈 = - 1 2 (𝑥 0 + 𝜇) 𝑇 𝜔. (3.7)
This shows that, for a single positive sample, SLEM and LDA are very similar: Indeed, taking 𝜆 = 0 (i.e.no regularization) and 𝜃 = 1, we have 𝜈 ⋆ = 𝜈, 𝐴 = Σ and that the vectors 𝜔 of Eq. (3.7) and 𝜔 ⋆ of Eq. (3.6) have the same direction, reducing SLEM to LDA. Many interesting properties of LDA have been used recently for classification tasks [START_REF] Gharbi | A Gaussian approximation of feature space for fast image similarity[END_REF][START_REF] Hariharan | Discriminative decorrelation for clustering and classification[END_REF]. With our simple generalization of LDA, we hope to obtain superior results. The importance of robustness in post-processing methods for image retrieval has been addressed by Jégou and Chum [START_REF] Jégou | Negative evidences and co-occurrences in image retrieval: The benefit of pca and whitening[END_REF].

Recursive square loss exemplar machine?

One interesting process proposed in [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF] is the recursive exemplar SVM encoding (or RESVM). The proposed idea is to implement the encoding pipeline 𝑘 times, 𝑘 > 0, taking the output of the (𝑘-1)-th ESVM pipeline as input of the 𝑘-th ESVM pipeline. Here, we consider the base features as the output of the of the 0-th ESVM pipeline. Indeed, if write 𝜔 ⋆ as a function of the positive exemplar 𝑥 0 and the pool of negative examples 𝒩 = {𝑥 1 , 𝑥 2 , ..., 𝑥 𝑛 }2 , i.e., 𝜔 ⋆ (𝑥 0 , 𝒩 ) = arg min

𝜔∈R 𝑑 ( 𝜃 𝑙(1, 𝜔 𝑇 𝑥 0 + 𝜈 ⋆ ) + 1 𝑛 ∑ 𝑥 𝑖 ∈𝒩 𝑙(1, 𝜔 𝑇 𝑥 𝑖 + 𝜈 ⋆ ) + 𝜆 2 ‖𝜔‖ 2 ) , (3.8)
and we denote the baseline encodings as 𝜔 (0) = 𝑥 0 and 𝒩 (0) = 𝒩 , the 𝑘-th recursion of ESVM is given by 𝜔 (𝑘) (𝑥 0 , 𝒩 ) = 𝜔 ⋆ (𝜔 (𝑘-1) , 𝒩 (𝑘-1) ), where 𝒩 (𝑘) = {𝜔 ⋆ (𝑧, 𝒩 (𝑘-1) ∖ {𝑧}), 𝑧 ∈ 𝒩 (𝑘-1) }. Note that the application of the 𝑘-th pipeline depends on the application of the (𝑘 -1)-th pipeline on the negative examples. In [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF], this means taking the pool of negatives equals to 𝒩 ∖{𝑥 𝑖 } for each negative example 𝑥 𝑖 . However, for SLEM, it means recalculating the matrix 𝐴 for each different pool of negative examples. This makes a recursive SLEM much more time costly than a regular SLEM, negating the computational advantages of our approach. Thus, we have not implemented recursive SLEM. One could also imagine keeping the positive example among the negative ones, which would avoid recomputing A at each iteration, but does not make much sense. Indeed, it would mean solving a classification problem where the only positive example is also a negative example.

The kernel SLEM

Kernel methods

Let us recall a few basic facts about kernel methods for supervised classification. We consider a reproducing kernel Hilbert space (RKHS) 𝐻 formed by real functions over some set 𝑋, and denote by 𝑘 and 𝜙 the corresponding reproducing kernel and feature map (which may not admit a known explicit form) over 𝑋, respectively. We address the following learning problem over 𝐻 × R:

min ℎ∈𝐻,𝜈∈R 1 𝑛 𝑛 ∑ 𝑖=1 𝑙(𝑦 𝑖 , ⟨𝜙(𝑥 𝑖 ), ℎ⟩ + 𝜈) + 𝜆 2 ‖ℎ‖ 2 𝐻 , (3.9)
where the pairs (𝑥 𝑖 , 𝑦 𝑖 ) in 𝑋 × {-1, 1}, 𝑖 = 1 . . . 𝑛 are training samples, and ⟨ℎ, ℎ ′ ⟩ is the inner product of element ℎ and ℎ ′ in 𝐻. We dub problems with the general form of (3.9) affine supervised learning problems since, given some fixed element ℎ of 𝐻 and some scalar 𝜈, ⟨ℎ, ℎ ′ ⟩ + 𝜈 is an affine function of ℎ ′ , whose zero set defines an affine hyperplane of 𝐻 considered itself as an affine space.

Let 𝐾 denote the kernel matrix with entries 𝑘 𝑖𝑗 = ⟨𝜙(𝑥 𝑖 ), 𝜙(𝑥 𝑗 )⟩ and rows 𝑘 𝑇 𝑖 = [𝑘 𝑖1 , 𝑘 𝑖2 , ..., 𝑘 𝑖𝑛 ], 𝑖 in {1, . . . , 𝑛}. We assume from now on that 𝑙 is convex and continuous. Under this assumption, Eq. (3.9) admits an equivalent formulation

min 𝛼∈R 𝑛 , 𝜈∈R ( 1 𝑛 𝑛 ∑ 𝑖=1 𝑙(𝑦 𝑖 , 𝑘 𝑇 𝑖 𝛼 + 𝜈) + 𝜆 2 𝛼 𝑇 𝐾𝛼 ) , (3.10)
and any solution (𝛼 ⋆ , 𝜈 ⋆ ) to (3.10) provides a solution (ℎ ⋆ , 𝜈 ⋆ ) to (3.9) with ℎ ⋆ = ∑ 𝑛 𝑖=1 𝛼 ⋆ 𝑖 𝜙(𝑥 𝑖 ) + 𝜈 ⋆ . This result follows from the Riesz representation theorem [START_REF] Schölkopf | A genelarized representer theorem[END_REF][START_REF] Washba | Spline models for observational data[END_REF]. Assuming our reproducing kernel is semidefinite positive, 𝐾 is a semidefinite positive matrix and can be decomposed as 𝐾 = 𝐵𝐵 𝑇 . Using this factorization, the kernelized problem can be expressed as

min 𝛽∈R 𝑟 ,𝜈∈R ( 1 𝑛 𝑛 ∑ 𝑖=1 𝑙(𝑦 𝑖 , 𝑏 𝑇 𝑖 𝛽 + 𝜈) + 𝜆 2 ‖𝛽‖ 2 ) , (3.11)
where 𝑏 𝑇 𝑖 denotes the 𝑖-th row of 𝐵 and 𝑟 is the number of columns of 𝐵. If (𝛽 ⋆ , 𝜈 ⋆ ) is the solution of Eq. (3.11), the corresponding vector 𝛼 ⋆ (or, more correctly, a corresponding vector of dimension 𝑛 ≥ 𝑟) can be computed by 𝛼 ⋆ = 𝑃 𝛽 ⋆ , where 𝑃 is the pseudoinverse of 𝐵 𝑇 .

Note that Eq. (3.11) is written as the usual form of a linear classifier. In particular, it allows us to write the kernel learning problem (3.9) as an instance of Eq. (3.1) by setting 𝜃 = 1 𝑛 (we set this value of 𝜃 for the remaining of this work) and 𝑦 𝑖 = -1 for all but one training sample. For our approach, we wish to solve (3.11) for many positive exemplars against the same set of negative training samples. In the following subsections, we show how to take advantage of the fixed negative samples to efficiently solve (3.11).

Offline preprocessing of negative samples

Let us now return to the (kernelized) SLEM, taking 𝑙 as the square loss. In order to calculate offline all operations that are dependent only on negative samples, let us denote by 𝐾 the kernel matrix of the negative samples 𝑋. The preprocessing phase consists of the calculation of the decomposition 𝐵 and the constants of Eq. (3.6):

⎧ ⎨ ⎩ 𝜇 = 1 𝑛 ∑ 𝑛 𝑖=1 𝑏 𝑇 𝑖 , 𝐴 = 1 𝑛 𝐵 𝑇 𝐵 -𝜇𝜇 𝑇 + 𝜆Id 𝑟 .
(3.12)

These operations are done offline and their results are stored.

Online addition of a positive sample

We now wish to write Eq. (3.11) as an exemplar classifier, with one positive example 𝑥 0 and 𝑛 negative examples 𝑋. We denote by 𝐾 ′ the augmented kernel matrix obtained by adding this sample,

𝐾 ′ = [ 𝑘 00 𝑘 𝑇 0 𝑘 0 𝐾 ] , (3.13)
where 𝑘 00 = ⟨𝜙(𝑥 0 ), 𝜙(𝑥 0 )⟩ is a scalar and

𝑘 0 = [⟨𝜙(𝑥 0 ), 𝜙(𝑥 𝑖 )⟩] 1≤𝑖≤𝑛 is a vector in R 𝑛 .
The following lemma shows how the factorization of 𝐾 ′ can be derived from the factorization of its sub-matrix 𝐾 and the solution of a 𝑛 × 𝑛 linear system.

Lemma 1. The augmented kernel matrix 𝐾 ′ can be factorized as 𝐾 ′ = 𝐵 ′ 𝐵 ′𝑇 with

𝐵 ′ = [ 𝑢 𝑣 𝑇 0 𝐵 ] , 𝑣 = 𝐵 † 𝑘 0 , 𝑢 = √ 𝑘 00 -||𝑣|| 2 , (3.14)
where 𝐵 † is the pseudoinverse of 𝐵.

Proof. For 𝐵 ′ defined by (3.14), we have that

𝐵 ′ 𝐵 ′𝑇 = [ 𝑢 2 + ‖𝑣‖ 2 𝑣 𝑇 𝐵 𝑇 𝐵𝑣 𝐵𝐵 𝑇 ] = [ 𝑘 00 𝑣 𝑇 𝐵 𝑇 𝐵𝑣 𝐾 ] . (3.15)
Since 𝐾 ′ is positive semidefinite, 𝑘 0 must lie in the column space ℬ of 𝐵. Indeed, if we suppose 𝑘 0 does not belong to ℬ, then it can be decomposed uniquely as 𝑘 0 = 𝑠+𝑡, 𝑠 ∈ ℬ and 𝑡 ∈ ℬ ⊥ , with 𝑡 ̸ = 0. In one hand, 𝐾 ′ being semidefinite positive implies that [1, -𝑎𝑡 𝑇 ]𝐾 ′ [1; -𝑎𝑡] = 𝑘 00 -2𝑎‖𝑡‖ 2 ≥ 0 for all real value 𝑎. Here, we use matlab notation for horizontal and vertical staking. In the other hand, for 𝑎 large enough, 𝑘 00 -𝑎‖𝑡‖ 2 ≤ 0, which is a contradiction. Hence 𝑣 = 𝐵 † 𝑘 0 is an exact solution of 𝐵𝑣 = 𝑘 0 . The fact that 𝑘 00 -‖𝑣‖ 2 is non-negative comes from the fact that the Schur complement 𝐾 -𝑘 0 𝑘 𝑇 0 /𝑘 00 of 𝑘 00 in 𝐾 ′ is itself positive semidefinite. Indeed, since the matrix 𝑘 00 𝐾 -𝑘 0 𝑘 𝑇 0 = 𝐵(𝑘 00 Id 𝑟 -𝑣𝑣 𝑇 )𝐵 𝑇 is also positive semidefinite. Thus 𝑣 𝑇 (𝑘 00 Id 𝑟 -𝑣𝑣 𝑇 )𝑣 = ‖𝑣‖ 2 (𝑘 00 -‖𝑣‖ 2 ) ≥ 0.

This lemma allows us to add a positive sample to Eq. (3.11)

α ] = [ 1 𝑢 0 𝑇 -1 𝑢 𝑃 𝑣 𝑃 ] [ 𝛽 0 β ] .
(3.17)

Similarity score

Once the optimal parameters (𝛽, 𝜈) from (3.16) and the coordinates 𝑢, 𝑣 of 𝑏 ′ 0 from (3.14) have been found 3 , they can be used directly for measuring similarity between matching images.

Suppose two image descriptors 𝑥 0 and 𝑥 ′ 0 are given and we wish to calculate the similarity score between their SLEM representations ℎ and ℎ ′ , denoted by 𝑠(ℎ, ℎ ′ ). We write ℎ ′ = 𝛼 ′ 0 𝜙(𝑥 ′ 0 ) + ∑ 𝑛 𝑖=1 𝛼 ′ 𝑖 𝜙(𝑥 𝑖 ) + 𝜈 ′ . Using Eq. (3.17) and ignoring biases 𝜈 and 𝜈 ′ which have empirically no influence, 𝑠(ℎ, ℎ ′ ) is given by:

𝑠(ℎ, ℎ ′ ) = ⟨ℎ, ℎ ′ ⟩ = α𝑇 𝐾 α′ + 𝛼 0 𝑘(𝑋, 𝑥 0 ) 𝑇 α′ + 𝛼 ′ 0 𝑘(𝑋, 𝑥 ′ 0 ) 𝑇 α + 𝛼 0 𝛼 ′ 0 𝑘(𝑥 0 , 𝑥 ′ 0 ) = β𝑇 β′ + 𝜆 -2 (𝑘(𝑥 0 , 𝑥 ′ 0 ) -𝑣 𝑇 𝑣). (3.18)
For a given image whose descriptor is 𝑥 0 , we need to store 𝑥 0 , β and 𝑣 to calculate its similarity score to whichever other image for SLEM. Since we assume the base feature 𝑥 0 has dimension 𝑑 and β and 𝑣 each have dimension 𝑟, we store a vector of dimension 𝑑 + 2𝑟 for each image.

Efficient implementation

When compared to the linear square-loss classifier of Section 3.3.2, one drawback of the kernelized approach is that the dimension of our problem grows with the number 3. We drop the "⋆" in this subsection to avoid cluttering the notation. 𝑛 of negative samples. The offline factorization 𝐵𝐵 𝑇 of 𝐾 demands 𝑂(𝑛𝑟) storage and 𝑂(𝑛𝑟 2 ) time. This factorization can be obtained in two ways: full-rank and lowrank decomposition. In this section we propose three different decompositions of 𝐾 and discuss their respective merits.

Full-rank decomposition

CCD: The complete Cholesky decomposition (CCD) is the most used factorization of positive-definite matrices in kernel-based learning due to its time efficiency [START_REF] Bach | Kernel independent component analysis[END_REF]. We use it as our default decomposition. We make sure 𝐾 is positive-definite by adding 𝜖 to its diagonal, where 𝜖 = min(0, -𝜆 𝑚𝑖𝑛 ) and 𝜆 𝑚𝑖𝑛 is the smallest eigenvalue of 𝐾 4 . Therefore, 𝐵 also has rank 𝑛 and can be calculated by CCD from the identity 𝐵𝐵 𝑇 = 𝐾 + 𝜖Id 𝑛 .

Low-rank decomposition

One of the major constraints of large scale retrieval is the minimization of storage. As discussed in Section 3.4.4, for each database image we store its base representation plus a 2𝑟 vector. Hence, we aim to decompose 𝐾 at a small rank 𝑟. Two classical methods can be used to obtain a low-rank decomposition of K.

ICD: The incomplete Cholesky decomposition (ICD) is widely used in machine learning [START_REF] Bach | Kernel independent component analysis[END_REF][START_REF] Fine | Efficient SVM training using low-rank kernel representations[END_REF]. It is similar to CCD, and greedily chooses which column of 𝐾 to add to the decomposition based on the gain in approximation error [START_REF] Bach | Predictive low-rank decomposition for kernel methods[END_REF]. The algorithm stops after 𝑟 steps, obtaining the factor 𝐵 in time 𝑂(𝑛𝑟 2 ). KPCA: Kernel PCA (KPCA) [START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF] computes the factor 𝐵 by performing a singular value decomposition of 𝐾 (truncated singular value decomposition for very small values of 𝑟), and making each column of the factor correspond to one of the top 𝑟 singular vectors. The resulting matrix 𝐵 is guaranteed to be the best 𝑟-rank approximation of 𝐾 according to the Frobenius norm. The computational cost of KPCA is, however, 𝑂(𝑛 2 𝑟) [START_REF] Golub | Matrix computations[END_REF].

We plot in Fig. 3-1 the residue tr(𝐾 -𝐵𝐵 𝑇 )/tr(𝐾) when we vary the number of columns 𝑟 of 𝐵 and we see a faster convergence for the kernel PCA decomposition when 𝑟 goes to 𝑛. We also compare their computation time, which shows that KPCA is slower than ICD for small values of 𝑟 and faster for values of 𝑟 such that the residue is small.

When comparing computation time, KPCA is slower than ICD for small values of 𝑟 and faster for values of 𝑟 such that the residue is small. Also, as discussed above, KPCA gives a smaller residue tr(𝐾 -𝐵𝐵 𝑇 )/tr(𝐾). From these comparisons, we set KPCA as our default low-rank decomposition. The only case ICD is more appropriated than KPCA is for very large number of negatives 𝑛, for which the time complexity of KPCA becomes an issue, and very small rank 𝑟. This particular case is further studied in Section 3.6.5.

Experimental evaluation

Datasets and evaluation protocol

We perform experiments on three standard datasets for image retrieval.

-The INRIA Holidays dataset [START_REF] Jegou | Hamming embedding and weak geometry consistency for large scale image search[END_REF] consists of 1491 images divided in 500 groups of matching images. We manually rotate by 90 degrees some images that are not in their natural orientation to compensate for the fact that CNN features are not rotation invariant [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF][START_REF] Babenko | Neural codes for image retrieval[END_REF][START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF][START_REF] Kalantidis | Cross-dimensional weighting for aggregated deep convolutional features[END_REF][START_REF] Radenović | Cnn image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF]]. -The Oxford5k dataset [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] consists of 5063 images separated in 55 groups of matching images, each group associated to a landmark of Oxford. We use the "full" crop, ignoring the region of interest of each image. -The Oxford105k dataset [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] is a large-scale dataset containing the same images and queries from Oxford5k plus Flickr100k, a collection of 10 5 distractor Flickr images. As pool of negative images to build SLEMs, we use the Flickr100k for both Holidays and Oxford5k. When evaluating Oxford105k, where Flickr100k is part of the database, we us instead the Paris dataset [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] as negative samples.

Kernels

For the experiment of SLEM as a feature encoder, we have tested two different kernels, each with a scalar parameter 𝛾. Gaussian SLEM:

𝑘 1 (𝑥, 𝑦) = 𝑒 -𝛾‖𝑥-𝑦‖ 2 ; (3.19)
Poly SLEM:

𝑘 2 (𝑥, 𝑦) = 𝑥 𝑇 𝑦 + 𝛾(𝑥 𝑇 𝑦) 2 . (3.20)
Note the non-kernel version of SLEM is equivalent to a SLEM for the linear kernel.

In order to distinguish it from other versions, we will refer to the non-kernel version as Linear SLEM for the remaining of this work.

Base visual features

We test our feature encoder for four different base features: the hand-crafted VLAD image representation and three learned features derived from the activation coefficients of deep Convolutional Neural Networks.

We use the same VLAD variant of [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF] used in [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF] that relies on densely-extracted rootSIFT [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF] local descriptors, per-cluster normalization, PCA-based rotations, and root normalization. Like [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF], we use 64 clusters, for a final feature of size 8192.

The first CNN features we use consist of the activation coefficients of the previousto-last layer of the AlexNet architecture [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], based on a publicly available pre-trained model [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF]. These are also the features used in [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF].

The SPoC features [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF], which are tailored specifically for the image retrieval application, consist of spatially-weighted sums of the activations of the last convolutional layer of the 19-layer VGG network [START_REF] Simonyan | Very deep convolutional networks for largescale visual recognition[END_REF].

Finally, we use the NetVLAD features [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF], trained for place recognition. These features are obtained by adding a differentiable version of the VLAD algorithm [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF] as a layer at the end of a convolutional architecture. for VLAD [START_REF] Delhumeau | Revisiting the vlad image representation[END_REF], sum-pooling of convolutional features (SPoC) [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF], activation coefficients from the previous-to-last CNN layer (AlexNet) [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] and activation of NetVLAD layer [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF]. In parentheses, the rank of he decomposition ('fr' for full rank decomposition). For each column, we show in bold the best results and index the second and third best.

Image retrieval results

We use all the those base features of the previous subsection as baseline. Since Babenko and Lemptisky [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF] and Arandjelović et al. [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] have improved retrieval results by applying PCA followed by whitening to their features, we also apply this postprocessing to our base features as a second baseline (PCAW), compressing base feature dimension to half of the original. We then compare the baselines with the original ESVM, LDA and several variants of our approach (SLEM), since all the those methods are based on similar ideas. For LDA, we follow our description in section 3.3.3 and calculate Σ as the convariance of the negative samples. The results are presented in Table 3.1. For the large-scale dataset that is Oxford105k, we limit our experiments to our best performing base features, SPoC and NetVLAD.

The version of each feature used as baseline changes according to the dataset. For VLAD and AlexNet, we considere the version presented in [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF] as baseline and a rotated, whitened and compressed to half its original dimensions as PCAW. For SPoC, we apply LDA, ESVM and SLEM to the baseline 512 dimensions feature, as a replacement of PCAW used in [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF] For NetVLAD, we use the rotated and compressed version of the trained networks correspondent to each dataset as suggested by [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF]. For Holidays we obtain better results with whitened NetVLAD features and for Oxford5k, non-whitened.

Linear SLEM performs similarly to ESVM while being much more time efficient (Fig. 34). The fact that a hinge-loss classifier does not outperform a square-loss classifier can seem counter-intuitive, but both have been shown to be equivalent for We use 𝑇 = 10 5 iterations for all 𝑛 to report mAP for ESVM, as suggested by [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF], but report timings using 𝑇 = 1.66𝑛 and the values reported in Table 1 of [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF]. Left: mAP; Right: computation time in solid line, online computational cost in dashed line.

binary classification under mild constraints [START_REF] Ye | Svm versus least squares svm[END_REF]. We use both Gaussian SLEM and Polynomial SLEM with two decompositions: one full-rank CCD decomposition indicated by (fr) and two low-rank KPCA decompositions indicated by the rank of the decomposition. We train our exemplar classifiers for 15000 negative samples. For all the experiments we calibrate the regularization cost 𝜆, as well as the parameter 𝛾 similarly to the calibration in [START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF].

The full-rank variant outperforms all methods for all base features, although the gains when compared to linear SLEM are not always significant (e.g. for VLAD features). We notice significant improvement for SPoC in both Holidays and Oxford and for AlexNet and NetVLAD in Oxford.

Time and storage scalability

In this section we compare the time efficiency of our method and the ESVM, as well as discuss which method and decomposition to use according to the number of negative samples.

In Fig. 34, we see that the linear SLEM efficiency does not change with 𝑛. Indeed, if 𝑑 is the dimension of the base representation, 𝐴 is a 𝑑 × 𝑑 matrix for linear SLEM, whereas for a full-rank kernel, 𝐴 is 𝑛 × 𝑛. This explains the increasing running time for Gaussian and polynomial kernels: storage and solving a 𝑛 × 𝑛 system does not scale for large number of negative samples.

Retrieval results for full-rank kernelized SLEM in Fig. 3-4 suggest we can benefit from larger sets of negative samples. We, however, limit our full-rank experiments to 𝑛 = 15000 negative samples due to the 𝑂(𝑛 3 ) complexity of the offline step. When we consider only the online procedure of our model, i.e. the calculation of 𝛽 ⋆ , our 200 400 600 800 1,000 76 At this high number of negative images, KPCA is constraint by its computation time, making ICD the only viable low-rank decomposition.

kernelized model has a similar time efficiency to ESVM. Therefore, we can process the kernel SLEM for the Gaussian and polynomial kernels in similar running time to ESVM if we pre-process our negative samples offline. For low-rank decompositions, we present in Fig. 3-5(a) a comparison in average precision between KPCA and ICD decompositions using SPoC on the Holidays dataset, fixing 𝑛 and varying 𝑟.

The superior results justify our preference for KPCA, despite its less efficient offline step. The only advantage of ICD over KPCA is its time complexity, linear in the number of negative samples, that allows a bigger number of negative samples. In Fig. 3-5(b) we show results for ICD for bigger pools of negative samples, to which a KPCA decomposition would be too time consuming. The results suggest that the performance of ICD SLEMs are not sensitive to the number of negative examples at a fixed small rank.

As shown by Fig. 3-5(a), the mAP for the low-rank KPCA approximation increases with the rank. Its maximum value for the features of the figure is 86.3 for full rank, 𝑟 = 15, 000 (Table 3.1, col. 2). Figure 345) also shows, however, that reasonable mAP values (around 84) are obtained for a much smaller rank of 200. In keeping with the usual practice in image retrieval, we limit even further the rank in the results shown in Tables 3.1 and 3.4, with very small ranks (16 and 32) that yield a total feature dimension similar to the base representation, and allow a direct comparison to methods using these features directly. This rather extreme compression is also justified in part by the fact that these very-low rank factorizations already capture a reasonable part of the problem structure. Indeed, the relative residual error for SPoC features on Holiday with 15,000 negatives is only 0.39 for 𝑟 = 16 and 0.31 for 𝑟 = 32. For reference, the relative error decreases to 0.08 for 𝑟 = 600, and 0.05 for 𝑟 = 1024.

Low-rank decomposition evaluation

We present a more complete evaluation of low-rank decomposition kernel SLEM for higher ranks. In Section 3.6.4, we limit our experiments to ranks equal to 16 and 32 for a best comparison to the state of the art. In this section, we use SPoC features as our base encoding, the polynomial kernel as our kernel function, Holidays dataset images as positives and 𝑛 = 15000 images of Flickr100k as negative samples. The results for a low-rank KPCA decomposition are presented in Fig. 3456, varying the rank 𝑟 through a higher range of values, and compared to the full-rank Cholesky decomposition. As 𝑟 increases, average precision increases and quickly approaches the full-rank performance. As reference, we obtain mAP 80.0 for 𝑟 = 16, 84.0 for 𝑟 = 128, 85.4 for 𝑟 = 1600, 86.2 for 𝑟 = 3200 and to the mAP 86.3 for full rank. However, the computational cost eventually overcomes that of the full-rank method. This is due to the higher complexity of the singular value decomposition. For values of 𝑟 bigger than 64, a KPCA is more time consuming than CCD.

As seen in 3.1, a low-rank decomposition of Poly SLEM obtain the same results as the full rank for NetVLAD features. We thus expand this experiment to higher ranks. The results are shown in Table 3.2.

Spatial pyramid matching kernel

All previous kernel functions take as input image representations in a fixed sized linear space. In this section, we propose using the spatial pyramid kernel [START_REF] Grauman | The pyramid match kernel: Discriminative classification with sets of image features[END_REF], that takes as input a set of local descriptors and its coordinates in the image.

We revisit the spatial pyramid scheme presented in [START_REF] Labeznik | Beyond bag of features: Spatial pyramid matching for recognizing natual scenes categories[END_REF] using the generalized [START_REF] Boughorbel | Generalized histogram intersection kernel for image recognition[END_REF]. We test this kernel for rootSIFT extracted in multiscales, as used in [START_REF] Labeznik | Beyond bag of features: Spatial pyramid matching for recognizing natual scenes categories[END_REF], and learn 200 codewords with K-means. Inspired by the results of [START_REF] He | Spatial pyramid pooling in deep convolutional networks for visual recognition[END_REF], we also test it for activations of the last convolutional layer of the network of [START_REF] Simonyan | Very deep convolutional networks for largescale visual recognition[END_REF]. Each neuron of the last layer correspond to a codeword. The results are presented in Table 3.3. As baseline, we compare with the spatial pyramid matching model presented in [START_REF] Labeznik | Beyond bag of features: Spatial pyramid matching for recognizing natual scenes categories[END_REF]. The improvements obtained with respect to the baseline are significantly larger then others kernels, and its use must be further studied.

Comparison to the state-of-the-art

We compare the state-of-the-art global descriptors for Holidays and Oxford 5k to both SPoC and NetVLAD features improved by linear SLEM and low-rank Poly SLEM in Table 3.4. We do not include re-ranking nor query expansion. We perform PCA and whitening to compress both descriptors to 256 and 512, as done in [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF][START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF] and compare the results by brackets of dimension. We also add a bracket of the full 4096-dimension NetVLAD for completeness, so we include our best performance. Our approach outperforms the state of the art for Holidays by 2.5 points in 256 dimensions and 0.8 in 512 dimensions, despite not using the best performing descriptors [START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF] as base features. Table 3.4: Compared results to state-of-the-art features at similar dimensions, without re-ranking or query augmentation. The results using Poly SLEM add 32 or 64 dimensions to the original feature (for 𝑟 = 16 or 𝑟 = 32, respectively). Underlined results are the best at each dimension bracket and bold results are the general best.

† indicates the previous state-of-the-art.

Conclusion and future work

In this chapter, we have addressed the problem of image retrieval using the kernelized square-loss exemplar machines, and its efficient implementation. The main novelty of the paper is two-fold: First, using the square loss, which avoids retraining for each additional positive training example and calibrating one of its parameters; second, kernelizing the method while keeping a reasonable memory footprint through the use of low-rank approximations. Similar ideas have of course been used in other contexts in machine learning [START_REF] Bach | Kernel independent component analysis[END_REF][START_REF] Fine | Efficient SVM training using low-rank kernel representations[END_REF][START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF][START_REF] Suykens | Least squares support vector machines[END_REF][START_REF] Ye | Svm versus least squares svm[END_REF]. Our work is, however, to our knowledge, the first to apply these ideas to examplar-based classifiers, in particular in the context of image retrieval. We have obtained significant improvements over the base features we tested and outperformed similar encoders on different datasets. As future work, we plan to work on a convolutional implementation similar to [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] so its parameters can be learned in a supervised manner. The use of other kernel functions is worth investigating. The polynomial kernel performs similarly to the Gaussian kernel, even though the Hilbert space obtained from the Gaussian kernel has infinite dimensions and the Hilbert space obtained from the polynomial kernel does not. The spatial pyramid kernel can be used to improve representations based on local descriptors and it offers the better boosts when compared with its baseline. Experimentation of kernels that allow different base features are worth pursuing. Finally, our method constructs a generic feature encoding and therefore can be used in many other computer vision problems, such as object classification and scene recognition.

49

Chapter 4

Learning Proposal Flow

This chapter addresses the problem of establishing semantic correspondences between images depicting different instances of the same object or scene category. Previous approaches focus on either combining a spatial regularizer with hand-crafted features, or learning a correspondence model for appearance only. We propose instead a convolutional neural network architecture, called SCNet, for learning a geometrically plausible model for semantic correspondence. SCNet uses region proposals as matching primitives, and explicitly incorporates geometric consistency in its loss function. It is trained on image pairs obtained from the PASCAL VOC 2007 keypoint dataset, and a comparative evaluation on several standard benchmarks demonstrates that the proposed approach substantially outperforms both recent deep learning architectures and previous methods based on hand-crafted features.

This chapter is an extended version of the paper "SCNet: Learning semantic correspondence" by Han, Rezende, Ham, Wong, Cho, Schmid and Ponce published in ICCV 2017 [START_REF] Han | Scnet: Learning semantic correspondence[END_REF]. This work was done in collaboration with another PhD student, Kai Han, from the University of Hong Kong. The extent of the contribution of each of us is found at the beginning of each section.

Introduction

The goal of this chapter is to establish semantic correspondences across images that contain different instances of the same object or scene category, and thus feature much larger changes in appearance and spatial layout than the pictures of the same scene used in stereo vision, which we take here to include broadly not only classical (narrow-baseline) stereo fusion (e.g., [START_REF] Okutomi | A multiple-baseline stereo[END_REF][START_REF] Rhemann | Fast cost-volume filtering for visual correspondence and beyond[END_REF]), but also optical flow computation (e.g., [START_REF] Horn | Determining optical flow: A retrospective[END_REF][START_REF] Revaud | Deepmatching: Hierarchical deformable dense matching[END_REF][START_REF] Weinzaepfel | Deepflow: Large displacement optical flow with deep matching[END_REF]) and wide-baseline matching (e.g., [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF][START_REF] Yang | Daisy filter flow: A generalized discrete approach to dense correspondences[END_REF]). Due to such a large degree of variations, the problem of semantic correspondence remains very challenging. Most previous approaches to semantic correspondence [START_REF] Bristow | Dense semantic correspondence where every pixel is a classifier[END_REF][START_REF] Hur | Generalized deformable spatial pyramid: Geometry-preserving dense correspondence estimation[END_REF][START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF][START_REF] Liu | SIFT flow: Dense correspondence across scenes and its applications[END_REF][START_REF] Taniai | Joint recovery of dense correspondence and cosegmentation in two images[END_REF][START_REF] Yang | Daisy filter flow: A generalized discrete approach to dense correspondences[END_REF] focus on combining an effective spatial regularizer with hand-crafted features such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], DAISY [START_REF] Tola | Daisy: An efficient dense descriptor applied to wide-baseline stereo[END_REF] or HOG [START_REF] Dalal | Histogram of oriented gradients for human detection[END_REF]. With the remarkable success of deep learning approaches in visual recognition, several learning-based methods have also been proposed for both stereo vision [START_REF] Fischer | Flownet: Learning optical flow with convolutional networks[END_REF][START_REF] Han | MatchNet: Unifying feature and metric learning for patch-based matching[END_REF][START_REF] Žbontar | Computing the stereo matching cost with a convolutional neural network[END_REF][START_REF] Zbontar | Stereo matching by training a convolutional neural network to compare image patches[END_REF] and semantic correspondence [START_REF] Choy | Universal correspondence network[END_REF][START_REF] Kim | Fcss: Fully convolutional self-similarity for dense semantic correspondence[END_REF][START_REF] Zhou | Learning dense correspondence via 3d-guided cycle consistency[END_REF]]. Yet, none of these methods exploits the geometric consistency constraints that have proven to be a key factor to the success of their hand-crafted counterparts. Geometric regularization, if any, occurs during post-processing but not during learning (e.g., [START_REF] Žbontar | Computing the stereo matching cost with a convolutional neural network[END_REF][START_REF] Zbontar | Stereo matching by training a convolutional neural network to compare image patches[END_REF]).

We propose a convolutional neural network (CNN) architecture, called SCNet, for learning geometrically plausible semantic correspondence, which allows us to handle a large degree of intra-class and scene variations. Following the proposal flow approach to semantic correspondence of Ham et al. [START_REF] Ham | Proposal flow[END_REF], we use object proposals [START_REF] Manen | Prime object proposals with randomized Prim's algorithm[END_REF][START_REF] Uijlings | Selective search for object recognition[END_REF][START_REF] Zitnick | Edge boxes: Locating object proposals from edges[END_REF] as matching primitives, and explicitly incorporate the geometric consistency of these proposals in our loss function. Unlike [START_REF] Ham | Proposal flow[END_REF] with its hand-crafted features, however, we train our system in an end-to-end manner using image pairs extracted from the PASCAL VOC 2007 keypoint dataset [START_REF] Everingham | The pascal visual object classes challenge 2007[END_REF]. A comparative evaluation on several standard benchmarks demonstrates that the proposed approach substantially outperforms both recent deep architectures and previous methods based on hand-crafted features.

Our main contributions can be summarized as follows:

-We introduce a simple and efficient model for learning to match regions using both appearance and geometry.

-We propose a convolutional neural network, SCNet, to learn semantic correspondence with region proposals.

-We achieve state-of-the-art results on several benchmarks, clearly demonstrating the advantage of learning both appearance and geometric terms.

Background

Semantic correspondence

Classical approaches to stereo matching and optical flow estimate pixel-level dense correspondences between two nearby images of the same scene.

SIFT Flow [START_REF] Liu | SIFT flow: Dense correspondence across scenes and its applications[END_REF] extends classical optical flow to establish correspondences across similar but different scenes. It uses dense SIFT descriptors to capture semantic information beyond naive color values, and leverages a hierarchical optimization technique in a coarse-to-fine pipeline for efficiency. Kim et al. [START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF] and Hur et al. [START_REF] Hur | Generalized deformable spatial pyramid: Geometry-preserving dense correspondence estimation[END_REF] propose more efficient generalizations of SIFT Flow. Instead of using SIFT features, Yang et al. [START_REF] Yang | Daisy filter flow: A generalized discrete approach to dense correspondences[END_REF] use DAISY [START_REF] Tola | Daisy: An efficient dense descriptor applied to wide-baseline stereo[END_REF] for an efficient descriptor extraction. Inspired by an exemplar-LDA approach [START_REF] Hariharan | Discriminative decorrelation for clustering and classification[END_REF], Bristow et al. [START_REF] Bristow | Dense semantic correspondence where every pixel is a classifier[END_REF] use whitened SIFT descriptors, making semantic correspondence robust to background clutter.

Recently, Ham et al. [START_REF] Ham | Proposal flow[END_REF] introduces proposal flow that uses object proposals as matching elements for semantic correspondence robust to scale and clutter. This work shows that the HOG descriptor gives better matching performance than deep learning features [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] Simo-Serra | Discriminative learning of deep convolutional feature point descriptors[END_REF]. Taniai et al. [START_REF] Taniai | Joint recovery of dense correspondence and cosegmentation in two images[END_REF] also use HOG descriptors, and show that jointly performing cosegmentation and establishing dense correspondence is helpful in both tasks. Despite differences in feature descriptors and optimization schemes, these semantic correspondence approaches use a spatial regularizer to ensure flow smoothness on top of hand-crafted or pre-trained features.

Deep learning for correspondence

Recently, CNNs have been applied to classical dense correspondence problems such as optical flow and stereo matching to learn feature descriptors [START_REF] Zagoruyko | Learning to compare image patches via convolutional neural networks[END_REF][START_REF] Žbontar | Computing the stereo matching cost with a convolutional neural network[END_REF][START_REF] Zbontar | Stereo matching by training a convolutional neural network to compare image patches[END_REF] or similarity functions [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] Žbontar | Computing the stereo matching cost with a convolutional neural network[END_REF].

FlowNet [START_REF] Fischer | Flownet: Learning optical flow with convolutional networks[END_REF] uses an end-to-end scheme to learn optical flow with a synthetic dataset. The learned network generalizes well to existing benchmark datasets, but is still outperformed by traditional optical flow methods (e.g., EpicFlow [START_REF] Revaud | EpicFlow: Edge-preserving interpolation of correspondences for optical flow[END_REF]). Several recent approaches also use supervision from reconstructed 3D scenes and stereo pairs [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] Žbontar | Computing the stereo matching cost with a convolutional neural network[END_REF][START_REF] Zbontar | Stereo matching by training a convolutional neural network to compare image patches[END_REF]. MC-CNN [START_REF] Žbontar | Computing the stereo matching cost with a convolutional neural network[END_REF] and its efficient extension [START_REF] Zbontar | Stereo matching by training a convolutional neural network to compare image patches[END_REF] train CNN models to predict how well two image patches match and use this information to compute the stereo matching cost. DeepCompare [START_REF] Zagoruyko | Learning to compare image patches via convolutional neural networks[END_REF] learns a similarity function for patches directly from images of a 3D scene, which allows for various types of geometric and photometric transformations (e.g., rotation and illumination changes).

These approaches are inherently limited to matching images of the same physical object/scene. In contrast, Long et al. [START_REF] Long | Do convnets learn correspondence?[END_REF] use CNN features pre-trained for ImageNet classification tasks (due to a lack of available datasets for learning semantic correspondence) with performance comparable to SIFT flow. To overcome the difficulty in obtaining ground truth for semantic correspondence, Zhou et al. [START_REF] Zhou | Learning dense correspondence via 3d-guided cycle consistency[END_REF] leverage 3D models, and uses flow consistency between 3D models and 2D images as a supervisory signal to train a CNN.

Another approach to generating ground truth is to directly augment the data by densifying sparse keypoint annotations using warping [START_REF] Ham | Proposal flow[END_REF][START_REF] Kanazawa | WarpNet: Weakly supervised matching for single-view reconstruction[END_REF]. Although this approach only provides approximate "ground truth" data, we will show that it is good enough to learn semantic correspondence. The universal correspondence network (UCN) of Choy et al. [START_REF] Choy | Universal correspondence network[END_REF] learns semantic correspondence using an architecture similar to [START_REF] Zbontar | Stereo matching by training a convolutional neural network to compare image patches[END_REF], but adds a convolutional spatial transformer networks for improved robustness to rotation and scale changes. Recently, Kim et al. [START_REF] Kim | Fcss: Fully convolutional self-similarity for dense semantic correspondence[END_REF] have combined learned semantic descriptors with the proposal flow [START_REF] Ham | Proposal flow[END_REF] framework and obtained state-of-the-art performance. These approaches to learning semantic correspondence [START_REF] Choy | Universal correspondence network[END_REF][START_REF] Zhou | Learning dense correspondence via 3d-guided cycle consistency[END_REF] or semantic descriptors [START_REF] Kim | Fcss: Fully convolutional self-similarity for dense semantic correspondence[END_REF] typically perform better than traditional hand-crafted ones, but they do not incorporate geometric consistency between regions or object parts in the learning process. In contrast, our network learns semantic correspondence by using both appearance and geometric informations.

Our approach

We consider the problem of learning to match regions with arbitrary positions and sizes in pairs of images. This setting is general enough to cover all cases of region sampling used in semantic correspondence: sampling a dense set of regular local regions as in typical dense correspondence [START_REF] Bristow | Dense semantic correspondence where every pixel is a classifier[END_REF][START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF][START_REF] Liu | SIFT flow: Dense correspondence across scenes and its applications[END_REF][START_REF] Tau | Dense correspondences across scenes and scales[END_REF] as well as employing multi-scale object proposals [START_REF] Arbelaez | Multiscale combinatorial grouping[END_REF][START_REF] Hosang | What makes for effective detection proposals?[END_REF][START_REF] Manen | Prime object proposals with randomized Prim's algorithm[END_REF][START_REF] Uijlings | Selective search for object recognition[END_REF][START_REF] Zitnick | Edge boxes: Locating object proposals from edges[END_REF]. In this work, following proposal flow [START_REF] Ham | Proposal flow[END_REF], we focus on establishing correspondences between object proposal boxes. Subsection 4.3.3 was mainly developped by Han. The remaining of this chapter is equally implemented by both authors or the pre-existing probabilistic Hough matching model from [START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF].

PHM model

Our basic model for matching starts from the probabilistic Hough matching (PHM) approach of [START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF][START_REF] Ham | Proposal flow[END_REF]. In a nutshell, given some potential match 𝑚 between two regions, and the supporting data 𝒟 (a set of potential matches), the PHM model can be written as

𝑃 (𝑚|𝐷) ≈ 𝑃 𝑎 (𝑚) ∑ 𝑥 𝑃 𝑔 (𝑚|𝑥) ∑ 𝑚 ′ ∈𝒟 𝑃 𝑎 (𝑚 ′ )𝑃 𝑔 (𝑚 ′ |𝑥), (4.1)
where 𝑃 𝑎 (𝑚) is the probability that the match 𝑚 = [𝑟, 𝑠] between two regions 𝑟 and 𝑠 is correct based on appearance only, and 𝑃 𝑔 (𝑚|𝑥) is the probability it is correct based on geometry only, computed using the offset 𝑥 (e.g., position and scale change) between the corresponding regions. This turns out to be an effective spatial matching model that combines appearance similarity with global geometric consistency measured by letting all matches vote on the potential offset 𝑥 [START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF][START_REF] Ham | Proposal flow[END_REF].

In our learning framework, we consider similarities rather than probabilities, and rewrite the PHM score for the match 𝑚 as

𝑧(𝑚, 𝑤) = 𝑓 (𝑚, 𝑤) ∑ 𝑥 𝑔(𝑚, 𝑥) ∑ 𝑚 ′ ∈𝒟 𝑓 (𝑚 ′ , 𝑤)𝑔(𝑚 ′ , 𝑥) = 𝑓 (𝑚, 𝑤) ∑ 𝑚 ′ ∈𝒟 [ ∑ 𝑥 𝑔(𝑚, 𝑥)𝑔(𝑚 ′ , 𝑥)]𝑓 (𝑚 ′ , 𝑤), (4.2)
where 𝑓 (𝑚, 𝑤) is a parameterized appearance similarity function between the two regions in the potential match 𝑚, 𝑥 is as before an offset variable (position plus scale), and 𝑔(𝑚, 𝑥) measures the geometric compatibility between the match 𝑚 and the offset 𝑥. Now assuming that we have a total number of 𝑛 potential matches, and identifying matches with their indices, we can rewrite this score as

𝑧(𝑚, 𝑤) = 𝑓 (𝑚, 𝑤) ∑ 𝑚 ′ 𝐾 𝑚𝑚 ′ 𝑓 (𝑚 ′ , 𝑤),
where

𝐾 𝑚𝑚 ′ = ∑ 𝑥 𝑔(𝑚, 𝑥)𝑔(𝑚 ′ , 𝑥), (4.3)
and the 𝑛 × 𝑛 matrix 𝐾 is the kernel matrix associated with the feature vector 𝜙(𝑚) = [𝑔(𝑚, 𝑥 1 ), . . . , 𝑔(𝑚, 𝑥 𝑠 )] 𝑇 , where 𝑥 1 to 𝑥 𝑠 form the finite set of values that the offset variable 𝑥 runs over: indeed

𝐾 𝑚𝑚 ′ = 𝜙(𝑚) • 𝜙(𝑚 ′ ). 1
Given training pairs of images with associated true and false matches, we can learn our similarity function by minimizing with respect to 𝑤

𝐸(𝑤) = 𝑛 ∑ 𝑚=1 𝑙[𝑦 𝑚 , 𝑧(𝑚, 𝑤)] + 𝜆Ω(𝑤), (4.4)
where 𝑙 is a loss function, 𝑦 𝑚 is the the ground-truth label (either 1 [true] or 0 [false]) for the match 𝑚, and Ω is a regularizer (e.g., Ω(𝑤) = ||𝑤|| 2 ). We use the hinge loss and 𝐿 2 regularizer in this work. Finally, at test time, we associate with any region 𝑟 the region 𝑠 maximizing 𝑧([𝑟, 𝑠], 𝑤 * ), where 𝑤 * is the set of learned parameters.

Similarity function and geometry kernel

There are many possible choices for the function 𝑓 that computes the appearance similarity of the two regions 𝑟 and 𝑠 making up match number 𝑚. Here we assume a trainable embedding function 𝑐 (as will be shown later, 𝑐 will be the output of a CNN in our case) that outputs a 𝐿 2 normalized feature vector. For the appearance similarity function between two regions 𝑟 and 𝑠, we then use a rectified cosine similarity:

𝑓 (𝑚, 𝑤) = max(0, 𝑐(𝑟, 𝑤) • 𝑐(𝑠, 𝑤)), (4.5)
that sets all negative similarity values to zero, thus making the similarity function sparser as well as insensitive to negative matches distant enough during training, with the added benefit of giving nonnegative weights in Eq. (4.2). Our geometry kernel 𝐾 𝑚𝑚 ′ records the fact that two matches (roughly) correspond to the same offset: Concretely, we discretize the set of all possible offsets into bins. Let us denote by ℎ the function mapping a match 𝑚 onto the corresponding bin 𝑥, we now define 𝑔 by

𝑔(𝑚, 𝑥) = { 1, if ℎ(𝑚) = 𝑥 0, otherwise. (4.6)
Thus, the kernel 𝐾 𝑚𝑚 ′ simply measures whether two matches share the same offset bin or not:

𝐾 𝑚𝑚 ′ = { 1, if ℎ(𝑚) = ℎ(𝑚 ′ ) 0, otherwise. (4.7)
In practice, 𝑥 runs over a grid of predefined offset values, and ℎ(𝑚) assigns match 𝑚 to the nearest offset point. Our kernel is sparse, which greatly simplifies the computation of the score function in Eq. ( 4.3): Indeed, let 𝐵 𝑥 denote the set of matches associated with the bin 𝑥, the score function 𝑧 reduces to

𝑧(𝑚, 𝑤) = 𝑓 (𝑚, 𝑤) ∑ 𝑚 ′ ∈𝐵 ℎ(𝑚) 𝑓 (𝑚 ′ , 𝑤). (4.8)
𝐾𝑓 (𝑤), where 𝑧(𝑤) = (𝑧(1, 𝑤), . . . , 𝑧(𝑛, 𝑤)) 𝑇 , "⊙" stands for the elementwise product between vectors, and 𝑓 (𝑤) = (𝑓 (1, 𝑤), . . . , 𝑓 (𝑛, 𝑤)) 𝑇 .

This trainable form of the PHM model from [START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF][START_REF] Ham | Proposal flow[END_REF] can be used within Eq. (4.4).

Note that since our simple geometry kernel is only dependent on matches' offsets, we obtain the same geometry term value of ∑ 𝑚 ′ ∈𝐵 ℎ(𝑚) 𝑓 (𝑚 ′ , 𝑤) for any match 𝑚 that falls into the same bin ℎ(𝑚). This allows us to compute this geometry term value only once for each non-empty bin 𝑥 and then share it for multiple matches in the same bin. This sharing makes computing 𝑧 several times faster in practice. 2

Gradient-based learning

The feature embedding function 𝑐(𝑚, 𝑤) in the model above can be implemented by any differentiable architecture, for example a CNN-based one, and the score function 𝑧 can be learned using stochastic gradient descent. Let us now consider the problem of minimizing the objective function 𝐸(𝑤) defined by Eq. (4.4). 3 This requires computing the gradient with respect to 𝑤 of the function 𝑧:

∇𝑧(𝑚, 𝑤) = [ ∑ 𝑚 ′ ∈𝒟 𝐾 𝑚𝑚 ′ 𝑓 (𝑚 ′ , 𝑤)]∇𝑓 (𝑚, 𝑤) +𝑓 (𝑚, 𝑤) ∑ 𝑚 ′ ∈𝒟 𝐾 𝑚𝑚 ′ ∇𝑓 (𝑚 ′ , 𝑤). (4.9)
Denoting by 𝑛 the size of 𝒟, this involves 𝑛 evaluations of both 𝑓 and ∇𝑓 . Computing the full gradient of 𝐸 thus requires at most 𝑛 2 evaluations of both 𝑓 and ∇𝑓 , which becomes computationally intractable when 𝑛 is large enough. The score function of Eq. (4.8) with the sparse kernel of Eq. (4.7), however, greatly reduces the gradient computation:

∇𝑧(𝑚, 𝑤) = [ ∑ 𝑚 ′ ∈𝐵 ℎ(𝑚) 𝑓 (𝑚 ′ , 𝑤)]∇𝑓 (𝑚, 𝑤) +𝑓 (𝑚, 𝑤) ∑ 𝑚 ′ ∈𝐵 ℎ(𝑚) ∇𝑓 (𝑚 ′ , 𝑤). (4.10)
Note that computing the gradient for match 𝑚 involves only a small set of matches falling into the same offset bin ℎ(𝑚).

Back-propagation for Hough Voting

Given two images associated with 𝑝 and 𝑞 proposals respectively. The appearance similarity matrix 𝐹 is obtained by considering all possible matches between the two:

𝐹 = ⎡ ⎢ ⎢ ⎢ ⎣
𝑣 𝑝1 𝑣 𝑝2 𝑣 𝑝3 . . . 𝑣 𝑝𝑞 ⎤ ⎥ ⎥ ⎥ ⎦ , (4.12
)

𝑣 𝑖𝑗 = vec(𝐹 ) 𝑇 𝑔 𝑖𝑗 (4.13)
where vec denotes column-wise vectorization, and the geometry voting vector 𝑔 𝑖𝑗 for a match 𝑚 is a (𝑝 × 𝑞) × 1 vector with each element being 0 or 1, such that 𝑣 𝑖𝑗 is a partial sum of the elements in 𝐹 , which corresponds to ∑ 𝑚 ′ ∈𝐵 ℎ(𝑚) 𝑓 (𝑚 ′ , 𝑤) in the paper (Eq. ( 8)).

To learn SCNet, we need to back-propagate for the voting. To achieve this, we need to first calculate 𝑑𝐿/𝑑𝑉 , which is a 𝑝 × 𝑞 matrix, and 𝐿 stands for loss.

According to the chain rule, we have 𝑑𝐿/𝑑𝐹 = 𝑑𝐿/𝑑𝑉 • 𝑑𝑉 /𝑑𝐹 , and 𝑑𝑉 /𝑑𝐹 is a (𝑝 × 𝑞) × (𝑝 × 𝑞) matrix.

𝑑𝐿/𝑑𝑓

ℎ 𝑝1 ℎ 𝑝2 ℎ 𝑝3 . . . ℎ 𝑝𝑞 ⎤ ⎥ ⎥ ⎥ ⎦ , (4.16)
where ℎ 𝑖𝑗 is the offset bin index corresponding to the match 𝑚 = (𝑟 𝑖 , 𝑟 𝑗 ), that is a match between 𝑟 𝑖 in image 𝐼 𝐴 and 𝑟 𝑗 in image 𝐼 𝐵 . Note that there are only 𝑡 unique numbers in 𝐻, which means that there are 𝑡 different offsets among the 𝑝 × 𝑞 pairs of possible matches. For example, 𝐻 can be in the form of

𝐻 = ⎡ ⎢ ⎢ ⎢ ⎣ 𝑥 1 𝑥 2 𝑥 3 . . . 𝑥 4 𝑥 2 𝑥 1 𝑥 2 . . . 𝑥 4 . . . . . . . . . . . . . . . 𝑥 1 𝑥 4 𝑥 4 . . . 𝑥 3 ⎤ ⎥ ⎥ ⎥ ⎦
In this example, since ℎ 11 = ℎ 𝑛1 = ℎ 22 = 𝑥 1 , then 𝑔 vector for offset 𝑥 1 is

𝑔 𝑥 1 = vec( ⎡ ⎢ ⎢ ⎢ ⎣ 1

SCNet architecture

Among many possible architectures implementing the proposed model, we propose using a convolutional neural network (CNN), dubbed SCNet, that efficiently processes regions and learns our matching model. Three variants, SCNet-AG, SCNet-A, SCNet-AG+, are illustrated in Fig. 12345.

In each case, SCNet takes as input two images 𝐼 𝐴 and 𝐼 𝐵 , and maps them onto feature maps 𝐹 𝐴 and 𝐹 𝐵 by CNN layers. Then, given region proposals (𝑟 1 , . . . , 𝑟 𝑝 ) and (𝑠 1 , . . . , 𝑠 𝑝 ) for the two images, parallel ROI pooling layers [START_REF] Girshick | Fast R-CNN[END_REF][START_REF] He | Spatial pyramid pooling in deep convolutional networks for visual recognition[END_REF] extract feature maps of the same size for each proposal. This is an efficient architecture that shares convolutional layers over all region proposals. These architecture were implemented jointly by the main authors, but mostly by Han. Han worked on the implementation of the learned fully-connected layer and the extraction of object proposals and I worked on the implementation of the ROI pooling and normalization layers, both unavailable to the library we used for our code.

SCNet-AG. The proposal features are fed into a fully-connected layer, mapped onto feature embedding vectors, and normalized into unit feature vectors 𝑐(𝑟 𝑖 , 𝑤) and 𝑐(𝑠 𝑗 , 𝑤), associated with the regions 𝑟 𝑖 and 𝑠 𝑗 of 𝐼 𝐴 and 𝐼 𝐵 , respectively. The value of 𝑓 (𝑚, 𝑤) for the match 𝑚 associated with regions 𝑟 𝑖 and 𝑠 𝑗 is computed as the rectified dot product of 𝑐(𝑟 𝑖 ) and 𝑐(𝑠 𝑗 ) (Eq. (4.5)), which defines the appearance similarity 𝑓 (𝑚, 𝑤) for match 𝑚. Geometric consistency is enforced with the kernel described in Sec. 4.3.2, using a voting layer, denoted as "×𝐾", that computes score 𝑧(𝑚, 𝑤) from the appearance similarity and geometric consensus of proposals. Finally, matching is performed by identifying the maximal 𝑧(𝑚, 𝑤) scores, using both appearance and geometric similarities.

SCNet-A. We also evaluate a similar architecture without the geometry term. This architecture drops the voting layer (denoted by ×𝐾 in Fig. 12345) from SCNet-AG, directly using 𝑓 (𝑚, 𝑤) as a score function. This is similar to the universal correspondence network (UCN) [START_REF] Choy | Universal correspondence network[END_REF]. The main differences are the use of object proposals and the use of a different loss function.

SCNet-AG+. Unlike SCNet-AG, which learns a single embedding 𝑐 for both appearance and geometry, SCNet-AG+ learns an additional and separate embedding 𝑐 𝑔 for geometry that is implemented by an additional stream in the SCNet architecture (dashed lines in Fig. 12345). This corresponds to a variant of Eq. (4.8), as follows:

𝑧 + (𝑚, 𝑤) = 𝑓 (𝑚, 𝑤) ∑ 𝑚 ′ ∈𝐵 ℎ(𝑚) 𝑓 𝑔 (𝑚 ′ , 𝑤), (4.17)
where 𝑓 𝑔 is the rectified cosine similarity computed by 𝑐 𝑔 . Compared to the original score function, this variant allows the geometry term to learn a separate embedding function for geometric scoring. This may be beneficial particularly when a match's contribution to geometric scoring needs to be different from the appearance score. For example, a match of rigid object parts (wheel of cars) may contribute more to geometric scoring than that of deformable object parts (leg of horses). The separate similarity function 𝑓 𝑔 allows more flexibility in learning the geometric term.

Implementation details. We use the VGG16 [START_REF] Simonyan | Very deep convolutional networks for largescale visual recognition[END_REF] model that consists of a set of convolutional layers with 3 × 3 filters, a ReLU layer and a pooling layer. We find that taking the first 4 convolutional layers is a good trade-off for our semantic feature extraction purpose without loosing a localization accuracy. These layers output features with 512 channels. For example, if the net takes input of 224 × 224 × 3 images, the convolutional layers produce features with the size of 14 × 14 × 512. For the ROI pooling layer, we choose a 7 × 7 filter following the fast R-CNN architecture [START_REF] Girshick | Fast R-CNN[END_REF], which produces a feature map with size of 7 × 7 × 512 for each proposal. We use randomized prim (RP) algorithm for region proposal [START_REF] Manen | Prime object proposals with randomized Prim's algorithm[END_REF], since it is gives the best results of [START_REF] Ham | Proposal flow[END_REF]. To transform the feature map for each proposal into a feature vector, we use the 𝐹 𝐶 layer with the size of 7 × 7 × 512 × 2048. The 2048 dimensional feature vector associated with each proposal are then fed into the 𝐿 2 normalization layer, followed by the dot product layer, ReLU, our geometric voting layer, and loss layer. The convolutional layers are initialized by the pretrained weights of VGG16 and the fully connected layers have random initialization. We train our SCNet by mini-batch SGD, with learning rate 0.001, and weight decay 0.0005. During training, each mini-batch arises from a pair of images associated with a number of proposals.

In our implementation, we generated 500 proposals for each image, which leads to 500 × 500 potential matches.

For each mini-batch, we sample matches for training as follows.

(1) Positive sampling: For a proposal 𝑟 𝑖 in 𝐼 𝐴 , we are given its ground truth match 𝑟 ′ 𝑖 in 𝐼 𝐵 . We pick all the proposals 𝑠 𝑗 in 𝐼 𝐵 with IoU(𝑠 𝑗 , 𝑟 ′ 𝑖 ) > 𝑇 𝑝𝑜𝑠 to be positive matches for 𝑟 𝑖 . (2) Negative sampling: Assume we obtain 𝑘 positive pairs w.r.t 𝑟 𝑖 . We also need to have 𝑘 negative pairs w.r.t 𝑟 𝑖 . To achieve this, we first find the proposals 𝑠 𝑡 in 𝐼 𝐵 with 𝐼𝑜𝑈 (𝑠 𝑡 , 𝑟 ′ 𝑖 ) < 𝑇 𝑛𝑒𝑔 . Assuming 𝑝 proposals satisfying the IoU constraint, we find the proposals with top 𝑘 appearance similarity with 𝑟 𝑖 among those 𝑝 proposals. In our experiment, we set 𝑇 𝑝𝑜𝑠 = 0.6, and 𝑇 𝑛𝑒𝑔 = 0.4.

Experimental evaluation

In this section we present experimental results with detailed analysis. The experiments and quantitative results presented were divided between the two main authors: Han performed the region matching experiments and I performed the dense matching experiments.

Experimental details

Dataset. We use the PF-PASCAL dataset that consists of 1300 image pairs selected from PASCAL-Berkeley keypoint annotations4 of 20 object classes. We divide the dataset into 700 training pairs, 300 validation pairs, and 300 testing pairs. The image pairs for training/validation/testing are distributed proportionally to the number of image pairs of each object class. In training, we augment the data into a total of 1400 pairs by horizontal mirroring. For region proposals, unless stated otherwise, we choose to use the method of Manen et al.(RP) [START_REF] Manen | Prime object proposals with randomized Prim's algorithm[END_REF]. The use of RP proposals is motivated by the superior result reported in [START_REF] Ham | Proposal flow[END_REF]. In testing we use 1000 proposals for each image as in [START_REF] Ham | Proposal flow[END_REF], while in training we use 500 proposals for efficiency.

Evaluation metric. We use three metrics to compare the results of SCNet to other methods. First, we use the probability of correct keypoint (PCK) [START_REF] Yang | Articulated human detection with flexible mixtures of parts[END_REF], which measures the precision of dense flow at sparse keypoints of semantic relevance. It is calculated on the Euclidean distance 𝑑(𝜑(𝑝), 𝑝 * ) between a warped keypoint 𝜑(𝑝) and ground-truth one 𝑝 *5 . Second, we use the probability of correct regions (PCR). Introduced in [START_REF] Ham | Proposal flow[END_REF] as an equivalent of the the PCK for region based correspondence, PCR measures the precision of a region matching between region 𝑟 and its correspondent 𝑟 * on the intersection over union (IoU) score 1 -IoU(𝜑(𝑟), 𝑟 * ). Both metrics are computed against a threshold 𝜏 in [0, 1] and we measure PCK@𝜏 and PCR@𝜏 as the percentage correct below 𝜏 . Third, we capture the quality of matching proposals by the mean IoU of the top 𝑘 matches (mIoU@𝑘). Note that these metrics are used to evaluate two different types of correspondence. Indeed, PCK is an evaluation metric for dense flow field, whereas PCR and mIoU@𝑘 are used to evaluate region-based correspondences [START_REF] Ham | Proposal flow[END_REF].

Proposal flow components

We use the PF-PASCAL dataset to evaluate region matching performance. This setting allows our method to be tested against three other methods in [START_REF] Ham | Proposal flow[END_REF]: NAM, PHM and LOM. We also compare our SCNet-learned feature against whitened HOG [START_REF] Dalal | Histogram of oriented gradients for human detection[END_REF], the best performing handcraft of [START_REF] Ham | Proposal flow[END_REF]. Additional results on the PF-WILLOW dataset are available in the supplementary material.

Qualitative comparison. Region matching results for NAM, SCNet-A, and SCNet-AG+ are shown in Figure 4-1. In this example, at the IoU threshold 0.5, the numbers of correct matches are shown for all methods. We can see that SCNet models perform significantly better than NAM with HOG feature, and SCNet-A is outperformed by SCNet-AG+ that learns a geometric consistency term.

Quantitative comparison. Figure 4-2 compares (at left) SCNet methods with the proposal flow methods [START_REF] Ham | Proposal flow[END_REF] on the PF-PASCAL dataset. Our SCNet models outperform the other methods that use the HOG feature. Our geometric models (SCNet-AG, SCNet-AG+) substantially outperform the appearance-only model (SCNet-A), and SCNet-AG+ slightly outperform SCNet-AG. This can also be seen from the area under curve (AuC) presented in the legend. This clearly show the effectiveness of deep learned features as well as geometric matching. In this comparison, we fix the VGG16 layer and only learn the FC layers. In our experiment, we also learned all layers including VGG 16 and the FC layers in our model (fully finefuned), but the improvement over the partially learned model was marginal. Figure 4-2 also shows (at right) the performance of NAM, PHM, LOM matching when replacing HOG feature with our learned feature in SCNet-A. We see that SCNet feature greatly improves all the matching methods. Interestingly, LOM using SCNet feature outperforms our best performing SCNet model, SCNet-AG+. However, the LOM method is more than 10 times slower than SCNet-AG+: On average, the method takes 0.21𝑠 for SCNet-A feature extraction and 3.15𝑠 for the actual matching process whereas our SCNet-AG+ only takes 0.33𝑠 in total. Most of the time in LOM is spent in computing its geometric consistency term.

Results with different object proposals. SCNet can be combined with any region proposal methods. In this experiment, we train and evaluate SCNet-AG+ on PF-PASCAL with four region proposal methods: randomized prim (RP) [START_REF] Manen | Prime object proposals with randomized Prim's algorithm[END_REF], selective search (SS) [START_REF] Uijlings | Selective search for object recognition[END_REF], random uniform sampling (US), and sliding window (SW). US and SW are extracted using the work of [START_REF] Hosang | What makes for effective detection proposals?[END_REF], and SW is similar to regular grid sampling used in other popular methods [START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF][START_REF] Liu | SIFT flow: Dense correspondence across scenes and its applications[END_REF][START_REF] Revaud | Deepmatching: Hierarchical deformable dense matching[END_REF]. Figure 4-3 compares matching performance in PCR and mIoU@𝑘 when using the different proposals. RP performs best, and US performs worst with a large margin. This shows that the region proposal process is an important factor for matching performance. Results on PF-WILLOW To evaluate transferability performance of the models, we also test them on PF-WILLOW [START_REF] Ham | Proposal flow[END_REF], and compare with state-of-the-art results on the datasets. In this case direct comparison to other learning-based methods may not be fair in the sense that our models are trained on a different dataset.

Flow field

Given a sparse region matching result and its corresponding scores, we generate dense semantic flow using a densifying technique in [START_REF] Ham | Proposal flow[END_REF]. The results are evaluated on PF-PASCAL dataset. To evaluate transferability performance of the models, we also test them on other datasets such as Caltech-101 [START_REF] Fei-Fei | One-shot learning of object categories[END_REF] and PASCAL Parts [START_REF] Zhou | FlowWeb: Joint image set alignment by weaving consistent, pixel-wise correspondences[END_REF] datasets, and compare with state-of-the-art results on the datasets. In these cases direct comparison to other learning-based methods may not be fair in the sense that our models are trained on a different dataset.

Method PCK@0.05 PCK@0.1 PCK@0.15 SIFT [START_REF] Liu | SIFT flow: Dense correspondence across scenes and its applications[END_REF] 0.247 0.380 0.504 DAISY [START_REF] Yang | Daisy filter flow: A generalized discrete approach to dense correspondences[END_REF] 0.324 0.456 0.555 LSS [START_REF] Schechtman | Matching local self-similarities accross images and videos[END_REF] 0.347 0.504 0.626 DASC [START_REF] Kim | Dasc: Dense adaptative self-correlation descriptor for multi-modal and multi-spectral correspondence[END_REF] 0.255 0.411 0.564 DeepD. [START_REF] Simo-Serra | Discriminative learning of deep convolutional feature point descriptors[END_REF] 0.187 0.308 0.430 DeepC. [START_REF] Zagoruyko | Learning to compare image patches via convolutional neural networks[END_REF] 0.212 0.364 0.518 MatchN [START_REF] Han | MatchNet: Unifying feature and metric learning for patch-based matching[END_REF] 0.205 0.338 0.476 LIFT [START_REF] Moo | Lift: Learned invariant feature transform[END_REF] 0 that is trained on a different subset of PASCAL VOC 2011 dataset. In our benchmark, all SCNet models significantly outperform UCN [START_REF] Choy | Universal correspondence network[END_REF] and all methods in [START_REF] Ham | Proposal flow[END_REF], and SCNet-AG+ performs best. Results on PF-WILLOW. The results are summarized in Table 4.2. On this dataset where the data has a different distribution, SCNet-A slightly outperforms the AG and AG+ variants. We also evaluate UCN-ST with two different models: GoogLenet pretrained model [START_REF] Szegedy | Going deeper with convolutions[END_REF] (denoted by UCN-ST-GL), which is used as initialization for training, and PF-PASCAL trained model (denoted by UCN-ST-PF). We observe that all SCNet models significantly outperform UCN-ST-PF, while both of them have been trained on the same dataset.

Results on Caltech-101. We also evaluate our approach on the Caltech-101 dataset [START_REF] Fei-Fei | One-shot learning of object categories[END_REF]. Following the experimental protocol in [START_REF] Kim | Deformable spatial pyramid matching for fast dense correspondences[END_REF], we randomly select 15 pairs of images for each object class, and evaluate matching accuracy with three metrics: Label transfer accuracy (LT-ACC) [START_REF] Liu | Nonparametric scene parsing via label transfer[END_REF], the IoU metric, and the localization error (LOC-ERR) of corresponding pixel positions. At first row, both instances (source and target) of the pairs are shown with its respective keypoints. At second and third rows, warped images of the source to the target using different methods are visualized. We show the keypoints of the target image in circles and the predicted keypoints of the source in crosses, with a vector that depicts the matching error.

Methods

LT-ACC IoU LOC-ERR NAM HOG [START_REF] Ham | Proposal flow[END_REF] 0.70 0.44 0.39 PHM HOG [START_REF] Ham | Proposal flow[END_REF] 0.75 0.48 0.31 LOM HOG [START_REF] Ham | Proposal flow[END_REF] 0

Future approaches

In this section, we discuss novel models of incorporating geometrical consistency to our SCNet architecture. The model presented in Section 4.3 is fully derived from the probabilistic Hough matching of [START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF] and had been successfully implemented in region based matching in [START_REF] Ham | Proposal flow[END_REF]. We propose new geometric voting strategies based on localized voting and limiting the number of voting matches by their appearance similarity. For the remaining of this section, the set of all possible matches is written as 𝒟 = ℛ × ℛ ′ , where ℛ, ℛ ′ are the set of object proposals from the source and target image, respectively. This section has so far been developed independently from Han and implemented independently from other authors of [START_REF] Han | Scnet: Learning semantic correspondence[END_REF].

New geometric voting strategies

The matching score 𝑧 can be generalized as the product of the appearance matching 𝑓 score and a voting score 𝑣: 𝑧(𝑚, 𝑤) = 𝑓 (𝑚, 𝑤) 𝑣(𝑚, 𝑤|𝒟)

For the voting score of Eq. (4.3), every match 𝑚 ′ in 𝒟 geometric consistent with 𝑚, i.e., has approximately the same offset, 'votes' for 𝑚 and the vote is weighted by its appearance score 𝑓 (𝑚 ′ , 𝑤). It is unclear however if this is the best strategy for select which pairs vote. Indeed, large sets of object proposals contain many outlier regions, resulting in many mediocre matches. Even if an outlier match has low appearance score, it still influences the matching score of the matches of similar offset. Conversely, relative distance between the matching regions of 𝑚 and 𝑚 ′ do not weight on their voting score. We can eliminate these matching by restricting voting to matches with good appearance, matches of neighboring regions in the source image or by measuring geometric compatibility proportionally to the relative position of the matches. Ham et al. [START_REF] Ham | Proposal flow[END_REF] solved this by suggestion a local offset matching (LOM), but this is not suitable for our SCNet architecture since the calculation of the local offset is non-differentiable.

We present below our new voting strategies adapted to our architecture that can minimize the problems of PHM. These voting strategies are then implemented for region matching on PF-WILLOW dataset, using 500 object proposals and HoG [START_REF] Dalal | Histogram of oriented gradients for human detection[END_REF] as appearance feature. We compare the results of region matching of our models with PHM and LOM voting using both measures for region matching: PCR@𝜏 and mIoU@𝑘, as explained in subsection 4.5.1.

kNN-PHM LOM proposes a voting method that truncate voting to the best match of each region in contrast to PHM strategy of unrestricted voting. Truncated voting eliminates background clutter but it also eliminates geometric consistent matches from the voting model. We propose an alternative voting method less restrictive that LOM but that exclude most outliers, call kNN-PHM. For each region 𝑟, we want the the 𝑘 best appearances matches to vote, for a certain constant 𝑘. We define 𝒮 𝑘 (𝑟) as the subset 𝒟 of the matches from 𝑟 with the 𝑘 highest appearance scores. The truncated set of matches 𝒯 𝑘 is defined as the union of these subsets for all proposals :

𝒯 𝑘 = ⋃ 𝑟∈ℛ 𝒮 𝑘 (𝑟). (4.19)
The geometrical score is given then by

𝑣 𝑘𝑁 𝑁 -𝑃 𝐻𝑀 (𝑚, 𝑤|𝒟) = ∑ 𝑚 ′ ∈𝒯 𝑘 𝐾 𝑚𝑚 ′ 𝑓 (𝑚 ′ , 𝑤) (4.20) = ∑ 𝑚 ′ ∈𝒯 𝑘 ∩𝐵 ℎ(𝑚) 𝑓 (𝑚 ′ , 𝑤). (4.21)
Notice in particular that if 𝑝 object proposals are extracted from the source image, 𝒯 𝑝 = 𝒟 and kNN-PHM for 𝑘 = 𝑝 is equivalent to PHM. We test kNN-PHM for different numbers of voting neighbors (10, 50, 100 and 500) and show the results in Fig. 456. Although we see an improvement for a reduced set of voting matches, this improvement negligible. AuC of PCR@𝜏 improves at most 0.005 and AuC of mIoU@𝑘, 0.004. We also see that for 𝑘 too small, we observe worse region matching results than PHM.

Local probabilistic Hough matching (LPHM) We assume geometric consistency is more important for neighbor matching proposals. Objects classes that allow more deformations have little geometric consistency for non-adjacent parts. Hence, we implement the PHM strategy with local voting, i.e., a match 𝑚 ′ = [𝑟 ′ , 𝑠 ′ ] only votes for a match 𝑚 = [𝑟, 𝑠] if its source object proposal 𝑟 ′ has non-zero intersection with 𝑟. We therefore restrict voting to pairs of proposals that allow less geometrical deformation. We notice a marginal improvement for big truncated voting sets (𝑘 = 50, 𝑘 = 100) w.r.t PHM (𝑘 = 500) and a decreasing performance for very small voting sets (𝑘 = 10). The (red) curve representing PHM is not visible since kNN-PHM 500 (green) coincides with it. We print both curves and AuC in order to check our implementation of kNN-PHM.

We define 𝒩 (𝑟) = {r ∈ ℛ | 𝑟 ∩ r ̸ = ∅} as the subset of ℛ with all neighbor proposals of 𝑟, and the geometrical score as

𝒯 𝑘 (𝑟) = ⋃ 𝑟 ′ ∈𝒩 (𝑟) 𝒮 𝑘 (𝑟 ′ ), (4.22)
𝑣 𝐿𝑃 𝐻𝑀 (𝑚, 𝑤|𝒟) = ∑ 𝑚 ′ ∈𝒯𝑝(𝑟) 𝐾 𝑚𝑚 ′ 𝑓 (𝑚 ′ , 𝑤). (4.23)
We compare LPHM to PHM. Again, we observe no improvement. Restricting voting to local regions improves results slightly for non-rigid object classes, i.e., objects that allow for deformations of its parts, (e.g., duck) but shows worse results for rigid object classes (e.g., wine bottle). Since our database matches pairs of images only if they have the same set of non-occluded keypoints, most pairs of images display the same pose and therefore do not contain deformations. The aspect of local voting is fundamental to LOM voting because of the local offset estimation, which is optimized for local matches and would not be robust to the clutter contained in all possible matches. Selecting voting matches locally does not improve geometric voting in the scenario of PHM, where the geometric consistency of a pair of matches is binary and determined by a clustering of the offset space.

Local best appearance matching (LBAM)

The issue with LOM applied to a differentiable pipeline is the use of a offset common to all voting matches. Indeed, the common local offset is the geometric median of the selected matches' offsets, which can not be expressed as a function of these matches. 7 We propose an alternative measure of geometric compatibility of two matches as a function of the distance of their offsets. We denote by 𝐺 the matrix that measures the compatibility of two matches as a Gaussian on the distance of their offsets, i.e.,

𝐺 𝑚𝑚 ′ = 𝑒 -𝐶||𝛾(𝑚)-𝛾(𝑚 ′ )|| , (4.24)
where 𝐶 is a constant. By replacing the binary compatibility kernel 𝐾 by 𝐺, we allow voting matches to be weighted according to the quality of the pairs' geometric compatibility. Similarly to LOM, we also impose that voting matches to be neighbor proposals and only the best appearance match by neighbor proposals, limiting votes for 𝑚 to the subset 𝒯 1 (𝑟) of ℛ. We call our model the local best appearance matching, or LBAM, and define its geometric score as 7. The geometric median is obtained as the argument of minimum of a function of the matches' offsets [START_REF] Chandrasekaran | Open questions concerning weiszfeld's algorithm for the fermat-weber location problem[END_REF].

𝑣 𝐿𝐵𝐴𝑀 (𝑚, 𝑤|𝒟) = ∑ 𝑚 ′ ∈𝒯 1 (𝑟) 𝐺 𝑚𝑚 ′ 𝑓 (𝑚 ′ , 𝑤). (4.25)
Results on PF-WILLOW (Fig. 45678) show that LBAM and LOM perform similarly (AUC of 0.46) and both outperform the established PHM (AuC of 0.40). We repeat this experiment on PF-PASCAL using 1000 proposals. Figure 4 Based on these experiments, the remaining of this section is dedicated to the implementation of a SCNet architecture where LBAM is used as our voting layer for geometric scoring (represented by '×𝐾' in Fig. 12345).

Gradient learning and back-propagation for LBAM

Building a neural network architecture able to learn appearance feature using local best appearance matching requires a differentiable voting layer.

For simplicity of notation, we write 𝑧 𝑚 = 𝑧(𝑚, 𝑤), 𝑓 𝑚 = 𝑓 (𝑚, 𝑤) and 𝑣 𝑚 = 𝑣(𝑚, 𝑤|𝒟). Equations (4.18) and (4.24) can be rewritten as

𝑧 𝑚 = 𝑓 𝑚 𝑣 𝑚 , (4.26
) (4.28)

𝑣 𝑚 = ∑ 𝑚 ′ ∈𝒟 𝑓 𝑚 ′ 𝐺 𝑚𝑚 ′ 𝛿 𝑚𝑚 ′ , ( 4
Therefore, applying the chain rule accordingly: and the 𝑚-th row of ∆ determines the selected matching voting for a given match 𝑚.

𝑑𝐿/𝑑𝑍 = -
Note that two rows are identical if its matches have the same proposal on the source image, which means we only have 𝑝 unique rows to calculate.

Learning with LBAM

This subsection is dedicated to our ongoing work on the SCNet-LBAM architecture.

We have not yet obtained convergence of the LBAM method yet. Figure 4-10 shows objective loss per epoch for different learning rates, and illustrates the objectives convergences we have observed so far: after reduction at the beginning, the training loss stabilizes (and, for the case of learning rate of 5 • 10 -3 , increases) at a relative high value (above 0.9).

Figure 4-11 compares the region matching of SCNet-LBAM with SCNet-AG by epoch. We plot the AuC for PCR evaluated over train, test and validation sets separately. We obtain the expected result of SCNet-AG, i.e., for a converging objective function, we obtain improved region matching for the training images set (in blue) and also for a different set of images (red and green). For SCNet-LBAM, we observe that even when its objective is decreasing, region matching is not being improved (for epochs between 20 and 40). In particular, for epochs after 45, we see that smaller objectives do not imply better region matching for test and validation sets (in red and green).

From the training of our three models of Section 4.4, we observed that our architecture is sensitive to changes in the learning rate. Indeed, SCNet-AG and SCNet-AG+ converge under different parameters. We are considering new values of learning rate to solve this problem. Another possible solution is the implementation of a new loss function, as Fig. 4-10 and 4-11 show a drift between the training criteria (minimizing loss function) and testing criteria (maximizing PCR). We do not exclude the possibility of a problem in our back-propagation implementation, despite having not yet encountered the bug that could justify these results. This work will be continued and we intent to submit it as a journal version of our ICCV paper.

Chapter 5 Conclusion

Summary of the thesis

In this work we proposed three new perspectives in three different tasks on image understanding.

Fisher vectors for classification

In Chapter 2 we propose experiments and introduce an new formulation of Fisher vectors based upon the assumption we could eliminate background information, which is useful for object-based application such as object classification, and hence obtain a feature representation dependent only on the object category. We start from a statistical formulation present over most of the literature that justifies the elimination of background local descriptors and try to modify our representation in order to better fit this formulation. These modifications consist of:

-Gaussian mixture models that describe only background descriptors instead of full images.

-Projection of Fisher vectors over components that eliminate background information.

-Separation of images in contexts and calculation of one Fisher vector per context for all images, concatenated in a new context-free image representation called contextual Fisher vector, or CFV.

Although the modifications proposed improve the foreground-background ratio for a hypothetical data that follows all assumptions and simple image contexts, these ratio improvements are not observed for more complex datasets that are coherent with the datasets used for classification today. While we are able to create larger foreground-background ratios with a projected Fisher vector, these do not improve performance for object classification.

The work presented in this chapter presents no published material as we judge our negative results are not fitting to most conferences. However, we believe our experiments present an interesting counter-argument to the formulation of Subsection 2.3.2, as we suppose it consists of an a posteriori formulation used to justify the normalization of Fisher vectors for improving performance in a classification task. Our experiments suggest that we can not obtain representation free of background information and, furthermore, contextual-specific information can be as useful as foreground information for the construction of an efficient image classification feature. Furthermore, the improved performance obtained by addition of background components to our projected Fisher vector suggests that contextual information is indeed useful for object-based classification.

Exemplar classifiers for image retrieval

In Chapter 3, we have addressed the problem of image retrieval using the kernelized square-loss exemplar machines, inspired by exemplar support vector machines, and its efficient implementation. The main novelty of the paper is two-fold: First, using the square loss, which avoids retraining for each additional positive training example and calibrating one of its parameters; second, kernelizing the method while keeping a reasonable memory footprint through the use of low-rank approximations. Similar ideas have of course been used in other contexts in machine learning. Our work is, however, to our knowledge, the first to apply these ideas to examplar-based classifiers, in particular in the context of image retrieval.

We have obtained significant improvements over the base features we tested and outperformed similar encoders on different datasets.

Finally, our method constructs a generic feature encoding and therefore can be used in many other computer vision problems, such as object classification and scene recognition.

Learning proposal flow for semantic correspondence

In Chapter 4, we have introduced a novel model for learning semantic correspondence, and proposed the corresponding CNN architecture that uses object proposals as matching primitives and learns matching in terms of appearance and geometry. Our architecture allows for a simultaneous learning of the appearance representation of each object proposal and the geometric voting layer used to measure the compatibility of the relative positions of pairs of matches.

The proposed method substantially outperforms both recent deep learning architectures and previous methods based on hand-crafted features. The result clearly demonstrates the effectiveness of learning geometric matching for both region correspondence and semantic correspondence. The robustness of our method is demonstrated by evaluating the transferability of the learned weights over many datasets.

In the work currently been developed, we propose a new model for leverage geometric information between matches and we wish to explore it a improved architecture.

Contributions and future work

For Chapter 2, our contributions are presented as follows:

-We propose a new framework of application of Fisher vectors to context-independent tasks, by aiming to eliminate the background information.

-We introduce a measurement of the foreground-background ratio of information present in a fisher vector and propose a projection that maximizes it.

-We present results that contradicts the claims of our method and shed light on the statistical formulation used to justify the normalization of Fisher vectors.

For Chapter 3, the contributions are threefold:

-We introduce a kernelized variant of SLEM that enjoys similar computational advantages and improves retrieval performances.

-We propose a low-rank factorization of the kernel matrix for computational and storage efficiency.

-Our experiments show improved results on a variety of base features and we obtain state-of-the-art results for Inria Holidays dataset.

As future work, we plan to work on a convolutional implementation similar to [START_REF] Arandjelović | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] so its parameters can be learned in a supervised manner. The use of other kernel functions is worth investigating. The polynomial kernel performs similarly to the Gaussian kernel, even though the Hilbert space obtained from the Gaussian kernel has infinite dimensions and the Hilbert space obtained from the polynomial kernel does not. The spatial pyramid kernel can be used to improve representations based on local descriptors and it offers the better boosts when compared with its baseline. Experimentation of kernels that allow different base features are worth pursuing.

For Chapter 4, our contributions can be summarized as:

-We introduce a simple and efficient model for learning to match regions using both appearance and geometry.

-We propose a convolutional neural network, SCNet, to learn semantic correspondence with region proposals.

-We achieve state-of-the-art results on several benchmarks, clearly demonstrating the advantage of learning both appearance and geometric terms.

For the future, we want to finish implementation of the SCNet-LBAM architecture, demonstrate the evolution of the performance for region correspondence and apply it to semantic matching in order to compare to our existing method. Eventually, we can improve our voting layer by implementing an hierarchical method of geometric consistency, following the work of Yang et al. [START_REF] Yang | Object-aware dense semantic correspondence[END_REF]. Additionally, we wish to improve the efficiency of our architecture calculating the object proposals with a region proposal network (RPN) [START_REF] Ren | Faster R-CNN: Towards real-time object detection with region proposal networks[END_REF].

Résumé

Figure 1 - 1 :

 11 Figure 1-1: Examples of images of Caltech 101.

Figure 1 - 2 :

 12 Figure 1-2: Examples of images of PASCAL VOC.

Figure 1 - 3 :

 13 Figure 1-3: Examples of images of ImageNet.

Figure 1 - 4 :

 14 Figure 1-4: Pipeline of SLEM. First row encapsulates the construction of a base feature for a query image, which usually consists of extracting, embedding and aggregating local descriptors into a vector, here written as 𝑥 0 . After repeating the process of base feature calculation a database of sample images and obtaining a matrix 𝑋 of base features, we solve a exemplar classifier by labeling 𝑥 0 as the lonely positive example (called exemplar ) and the columns of 𝑋 as negatives. The solution 𝜔 to this classification problem, which is a function of 𝑥 0 and 𝑋, is our SLEM encoding of the query image.

Figure 2 - 1 :

 21 Figure 2-1: Examples of images in context 1 of EPFL Car database.

Figure 2 - 2 :

 22 Figure 2-2: Examples of images in context 2 of EPFL Car database.

Figure 2 - 3 :

 23 Figure 2-3: Examples of images classified in no context of EPFL Car database.

Figure 2 - 4 :

 24 Figure 2-4: Examples of images of highway in SUn database.

Figure 2 - 5 :

 25 Figure 2-5: Examples of images of street in SUn database.

Figure 2 - 6 :

 26 Figure 2-6: Examples of images of bathroom in SUn database.

Figure 2 -

 2 [START_REF] Babenko | Neural codes for image retrieval[END_REF] plots 𝑙𝑛(𝑟(𝑋, 𝜆 𝑏𝑔 ))

Figure 2 - 7 :

 27 Figure 2-7: 𝑙𝑛(𝑟(𝑋, 𝜆 𝑏𝑔 )) by number of distributions 𝐾. For convenience of notation, we extrapolate the notation 𝑞 and use it to denote the number of Gaussian distributions used to model the foreground distribution in the legend.

Figure 2 -

 2 Figure 2-8: Examples of images in context 1.

Figure 2 - 9 :

 29 Figure 2-9: Bg GMM vs fg+bg GMM in toy database (left) and EPFL cars (right).

Figure 2 -

 2 [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF] shows that the product by he normal by the residual did not eliminate the background information, as it was intended.

Figure 2 -

 2 Figure 2-10: Average and standard deviation for foreground-background ratio for contexts of EPFL database. In blue, ratio for proper context GMM; in black, ratio for general context GMM; in red, ratio for wrong context GMM.

Figure 2 - 11 :

 211 Figure 2-11: Histograms of values for ln(𝑟(𝑋, 𝜆 𝑏𝑔 ) for context 2, using: context 2 GMM (top-left), general-context GMM (top-right) and the product of context 1 GMM by the normal to the residual to context 1 (bottom).

  Figure 2-12: Average and standard deviation for foreground-background ratio for contexts of SUn database. In blue, ratio for proper context GMM; in red, ratio for general context GMM. Results for bathroom (top-left), highways (top-right), street (bottom-left) and building facade (bottom-right).

Figure 2 -

 2 Figure 2-13: From left to right: Cars in highway images and toilets in bathroom images. Black line gives FV mean average precision, blue line gives projected-FV mean average precision for different values of 𝑑.

Figure 2 - 14 :

 214 Figure 2-14: From left to right: Persons in street images, cars in skyscraper facade images and cars in street images. Black line gives FV mean average precision, blue line gives projected-FV mean average precision for different values of 𝑑.

Figure 3 - 1 :

 31 Figure 3-1: Comparison between complete Cholesky decomposition (CCD, in green), incomplete Cholesky decomposition (ICD, in red) and kernel PCA (KPCA, in blue), varying the rank of 𝐵. Left: Residue for each decomposition. Right: Time of calculation.We use SPoC features[START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF] of 15000 sample images to construct the the kernel matrix 𝐾.

Figure 3 - 2 :

 32 Figure 3-2: Examples of images in INRIA Holidays dataset. The center image is rotated 90 degrees clockwise to their natural orientation.

Figure 3 - 3 :

 33 Figure 3-3: Examples of images in Oxford buildings dataset.

Figure 3 - 4 :

 34  Results for INRIA Holidays, using SPoC features and different variants of full-rank SLEM. We use 𝑇 = 10 5 iterations for all 𝑛 to report mAP for ESVM, as suggested by[START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF], but report timings using 𝑇 = 1.66𝑛 and the values reported in Table1of[START_REF] Zepeda | Examplar SVMs as visual feature encoders[END_REF]. Left: mAP; Right: computation time in solid line, online computational cost in dashed line.

Figure 3 - 5 :

 35 Figure 3-5: mAP for Holidays using SPoC + Poly SLEM for different low-rank decompositionsand value of ranks: At (a), 𝑛 = 15000 negatives. We perform two low-rank decompositions and compare its results at similar ranks. At (b), rank fixed at 𝑟 = 32.At this high number of negative images, KPCA is constraint by its computation time, making ICD the only viable low-rank decomposition.

Figure 3 - 6 :

 36 Figure 3-6: Comparison of results for low-rank decomposition of SLEM, varying the rank 𝑟 (in blue) with full-rank SLEM (in green). Results are shown for INRIA Holidays, using SPoC features and 15000 negative samples; At (a), mAP; at (b), computation time in solid line, online computational cost on dashed line.

)

  Since matches 𝑚 = (𝑟 𝑖 , 𝑟 𝑗 ) with the same offset index have the same gradient 𝑑𝐿/𝑑𝑓 𝑖𝑗 , 𝑑𝐿/𝑑𝑓 𝑖𝑗 can be computed only once by Eq.(4.14) and shared among them.

Figure 4 - 1 :

 41 Figure 4-1: Region matching examples. From left to right: Input image pair; NAM matching result; SCNet-A matching result; SCNet-AG+ matching result. Number of correct matches: Bike (NAM[37], SCNet-A[104], SCNet-AG+[107]); Bird (NAM[63], SCNet-A[124], SCNet-AG+[159]).

Figure 4 - 2 :

 42 Figure 4-2: PCR (top) and mIoU@𝑘 (bottom) plots on PF-PASCAL. AuC is shown in the legend.

Figure 4 - 3 :

 43 Figure 4-3: SCNet-AG+ on PF-PASCAL with different proposals. PCR (top) and mIoU@𝑘 (bottom) plots on PF-PASCAL. AuC is shown in the legend.

Figure 4 -

 4 4 compares (at left) SCNet with proposal flow on the PF-WILLOW dataset. SCNet models outperform the other methods that use HOG features. Figure4-4shows (at right) the performance of NAM, PHM, LOM matching when replacing HOG features with our learned features in SCNet-A. We see that SCNet features significantly improve all the matching methods.

Figure 4 -

 4 [START_REF] Aytar | Part level transfer regularization for enhancing exemplar svms[END_REF] presents six examples of dense semantic matching for PF-PASCAL. Ground truths are presented as circles and predicted keypoints are presented as squares. We observe a better performance of SCNet-AG and SCNet-AG+ in both examples.

Figure 4 - 5 :

 45 Figure 4-5: Quantitative comparison of dense correspondence for PF-PASCAL (𝑎𝑖𝑟𝑝𝑙𝑎𝑛𝑒, 𝑏𝑜𝑡𝑡𝑙𝑒, 𝑏𝑜𝑎𝑡 and 𝑑𝑜𝑔) and PF-WILLOW (𝑐𝑎𝑟 and 𝑚𝑜𝑡𝑜𝑟𝑐𝑦𝑐𝑙𝑒) image pairs.At first row, both instances (source and target) of the pairs are shown with its respective keypoints. At second and third rows, warped images of the source to the target using different methods are visualized. We show the keypoints of the target image in circles and the predicted keypoints of the source in crosses, with a vector that depicts the matching error.

Figure 4 - 6 :

 46  Results comparison for PHM and kNN-PHM on PF-WILLOW, when varying the value of 𝑘. We notice a marginal improvement for big truncated voting sets (𝑘 = 50, 𝑘 = 100) w.r.t PHM (𝑘 = 500) and a decreasing performance for very small voting sets (𝑘 = 10). The (red) curve representing PHM is not visible since kNN-PHM 500 (green) coincides with it. We print both curves and AuC in order to check our implementation of kNN-PHM.

Figure 4 - 7 :

 47 Figure 4-7: Results comparison for LPHM and PHM on PF-WILLOW.

Figure 4 - 8 :

 48 Figure 4-8: Results comparison for PHM, LOM and LBAM on PF-WILLOW. LBAM performs similarly to LOM and outperforms PHM.

Figure 4 - 9 :

 49 Figure 4-9: Results comparison for PHM, LOM and LBAM for PF-PASCAL. We use all dataset, train, validation and test, similarly to the experiments in PF-WILLOW.

  ) and Σ 𝑖 is the square diagonal matrix with main diagonal equals to 𝜎 2 𝑖 . For each local descriptor 𝑥 𝑛 in 𝑋, we can calculate its Fisher score 𝑧 𝜆 𝑛 = ∇ 𝜆 log 𝑢 𝜆 (𝑥 𝑛 ), where 1 ∇ 𝜆 𝑓 (𝜆) = [∇ 𝜇 1 𝑓 (𝜆); ∇ 𝜎 1 𝑓 (𝜆); . . . ; ∇ 𝜇 𝐾 𝑓 (𝜆); ∇ 𝜎 𝐾 𝑓 (𝜆)] .

	(2.3)

  𝜙 2 (𝜙 1 (𝐿 𝜆 𝑍 𝜆 (𝑋))) .

	.8)
	Equation (2.7) is a signed square-rooting, similar to the Hellinger kernel which has
	successfully improved results for Bag of Visual Words features [96]. Equation (2.8)
	is a 𝑙 2 normalization. Its justification is discussed in the subsection 2.3.2 and it is
	also one of the inspirations of this work. The post normalization FV is given by the
	equation
	Ψ 𝜆 (𝑋) =

  .12),

	𝜆 = 𝑎𝑟𝑔𝑚𝑎𝑥	∫	𝑝 𝑏𝑔 (𝑥) log 𝑢 𝜆 (𝑥) ≈ 𝑎𝑟𝑔𝑚𝑎𝑥	∑	log 𝑢 𝜆 (𝑥),	(2.13)
	𝜇 𝑖 ,𝜎 𝑖 ∈R 𝐷 , 𝛾 𝑖 ≥0, ∑ 𝛾 𝑖 =1	𝑥∈R 𝐷		𝜇 𝑖 ,𝜎 𝑖 ∈R 𝐷 , 𝛾 𝑖 ≥0, ∑ 𝛾 𝑖 =1	𝑥∈𝑋, 𝑥∼𝑝 𝑏𝑔
	and under this assumption, we find
			𝑍 𝜆 (𝑋)	𝑎.𝑠. -→ 𝜔∇ 𝜆 E 𝑥∼𝑝 𝑓 𝑔 [log 𝑢 𝜆 (𝑥)].		(2.14)

  Generalized Eigenvalue problem: if 𝐵𝐵 𝑇 is a invertible matrix, there are𝛼 1 > 𝛼 2 > ... > 𝛼 𝑑 > 0 such that, for 1 ≤ 𝑗 ≤ 𝑑, 𝑀 𝑓 𝑔 𝑀 𝑇 𝑓 𝑔 𝑎 𝑗 = 𝛼 𝑗 𝑀 𝑏𝑔 𝑀 𝑇𝑏𝑔 𝑎 𝑗 where 𝑎 𝑗 is the 𝑗-th column vector of 𝐴 * . However, the Generalized Eigenvalue problem does not insure the orthogonality of the column vectors of the matrix 𝐴 * . The linear projection 𝑃 over 𝑑 dimensions corresponding to 𝐴 * is given by 𝑃 = 𝐴 * (𝐴 *𝑇 𝐴 * ) -1 𝐴 *𝑇 .Solving the generalized eigenvalue problem In order to simplify the notation, we call 𝐹 = 𝑀 𝑓 𝑔 𝑀 𝑇 𝑓 𝑔 and 𝐵 = 𝑀 𝑏𝑔 𝑀 𝑇 𝑏𝑔 + 𝜖𝐼𝑑 𝑁 , where 𝐼𝑑 𝑁 is the 𝑁 × 𝑁 identity matrix and 𝜖 is a small positive real number.2

			2
	𝑁 ∑	||𝐴 𝑇 Ψ(𝑋	(𝑛) 𝑏𝑔 )|| 2	= 𝑎𝑟𝑔𝑚𝑎𝑥 𝐴∈R 2𝐷𝐾×𝑑	𝑡𝑟 𝑡𝑟	( ( 𝐴 𝑇 𝑀 𝑓 𝑔 𝑀 𝑇 𝑓 𝑔 𝐴 ) 𝐴 𝑇 𝑀 𝑏𝑔 𝑀 𝑇 𝑏𝑔 𝐴 ) .	(2.19)
	𝑛=1
	Equation (2.19) stats a (2.20)
	Our new image representation is the projection 𝑃 of its Fisher vector:
		Ψ 𝑝 (𝑋) = 𝑃 Ψ(𝑋).			(2.21)
		𝐴 * = 𝑎𝑟𝑔𝑚𝑎𝑥 𝐴∈R 2𝐷𝐾×𝑑	𝑡𝑟 𝑡𝑟 (𝐴 𝑇 𝐵𝐴) ( ) 𝐴 𝑇 𝐹 𝐴	.	(2.22)
	Let us assume 𝐴 is a matrix of rank 𝑑 and can be written as the orthonormal
	2. The following solution requires 𝐵 to be a invertible matrix.

  𝑖 being the (𝑖 + 1)-th row of 𝐵 ′ , 𝑖 in {0, 1, ..., 𝑛}. In particular, 𝑏 ′ 0 = [𝑢; 𝑣] and, for 𝑖 > 0,𝑏 ′ 𝑖 = [0; 𝑏 𝑖 ]. The solution (𝛽 ⋆ , 𝜈 ⋆ ) in R 𝑟+1 × Rcan be computed just as before by Eq. (3.3), replacing 𝑥 0 by 𝑏 ′ 0 , 𝜇 by 𝜇 ′ = 1 𝑖 and 𝑋 by the (𝑟 + 1) × 𝑛 matrix 𝑄 of columns 𝑏 ′ 1 , 𝑏 ′ 2 , ..., 𝑏 ′ 𝑛 . The solution 𝛼 ⋆ is now calculated as 𝛼 ⋆ = 𝑃 ′ 𝛽 ⋆ , where 𝑃 ′ = [𝑢 -1 0 𝑇 ; -𝑢 -1 𝑃 𝑣 𝑃 ] is the pseudoinverse of 𝐵 ′𝑇 . 𝛼 ⋆ can be expressed by

								. With a positive
	exemplar, it now reads
	1 𝑛	(𝑏 ′𝑇 0 𝛽 + 𝜈 -1) 2 +	1 𝑛	𝑛 ∑ 𝑖=1	(𝑏 ′𝑇 𝑖 𝛽 + 𝜈 + 1) 2 +	𝜆 2	‖𝛽‖ 2 ,	(3.16)
	with 𝑏 ′𝑇
					𝑛	∑ 𝑛 𝑖=1 𝑏 ′
	the linear system
		[ 𝛼 0

Table 3 .

 3 1: Mean average precision (mAP) results for INRIA Holidays and Oxford buildings datasets, expressed as percentages. In this table, we present our results

Table 3 .

 3 2: Completed version of the state of the art table of our submission, with higher-rank decompositions.

	Features		rank dim Hol. Ox5k
	Arandjelović et al. [1]	-	4096 88.3 69.1
	NetVLAD + Linear SLEM	-	4096 91.3 72.9
	NetVLAD + Poly SLEM	16	4128 91.3 71.2
	NetVLAD + Poly SLEM	32	4160 91.7 71.7
	NetVLAD + Poly SLEM	64	4224 91.3 71.9
	NetVLAD + Poly SLEM	128 4352 91.2 72.1
	NetVLAD + Poly SLEM	256 4608 91.0 71.9
	NetVLAD + Poly SLEM	512 5120 90.8 72.5
	NetVLAD + Poly SLEM	1024 6144 91.1 73.1
	NetVLAD + Poly SLEM 15000 304096 91.7 74.1
	Dataset	Holidays	Oxford 5k
	Method, feaures rootSIFT CNN rootSIFT CNN
	Baseline (SPM)	53.3	51.8	24.1	36.4
	SP SLEM	66.9	70.2	42.4	45

Table 3 .

 3

3: Results for spatial pyramids kernel when compared with a spatial pyramid matching from the local descriptors intersection function of histograms

  𝑓 11 𝑓 12 𝑓 13 . . . 𝑓 1𝑞 𝑓 21 𝑓 22 𝑓 23 . . . 𝑓 2𝑞 𝑣 11 𝑣 12 𝑣 13 . . . 𝑣 1𝑞 𝑣 21 𝑣 22 𝑣 23 . . . 𝑣 2𝑞

								⎤
			. . .	. . .	. . .	. . .	. . .	⎥ ⎥ ⎦ ⎥	.	(4.11)
		𝑓 𝑝1 𝑓 𝑝2 𝑓 𝑝3 . . . 𝑓 𝑝𝑞
	The geometric similarity matrix 𝑉 contains geometric scores assigned to the
	matches:	⎡
	𝑉 =	⎢ ⎢ ⎢ ⎣	. . .	. . .	. . .	. . .	. . .

  𝑖𝑗 = 𝑑𝐿/𝑑𝑉 • 𝑑𝑉 /𝑑𝑓 𝑖𝑗 = [𝑑𝐿/𝑑𝑣 11 , 𝑑𝐿/𝑑𝑣 21 , . . . , 𝑑𝐿/𝑑𝑣 𝑝𝑞 ] [𝑑𝑣 11 /𝑑𝑓 𝑖𝑗 , 𝑑𝑣 21 /𝑑𝑓 𝑖𝑗 , . . . , 𝑑𝑣 𝑝𝑞 /𝑑𝑓 𝑖𝑗 ] 𝑇 = [𝑑𝐿/𝑑𝑣 11 , 𝑑𝐿/𝑑𝑣 21 , . . . , 𝑑𝐿/𝑑𝑣 𝑝𝑞 ]𝑔 𝑖𝑗 (4.14) By vectorizing 𝑑𝐿/𝑑𝑉 , we simplify the gradient estimation for 𝑑𝐿/𝑑𝐹 (index follows Matlab fashion) as 𝑑𝐿/𝑑𝐹 = [𝑑𝐿/𝑑𝑣 11 , 𝑑𝐿/𝑑𝑣 21 , . . . , 𝑑𝐿/𝑑𝑣 𝑝𝑞 ] 𝑑𝑣 11 /𝑑𝑓 11 𝑑𝑣 11 /𝑑𝑓 21 . . . 𝑑𝑣 11 /𝑑𝑓 𝑝𝑞 𝑑𝑣 21 /𝑑𝑓 11 𝑑𝑣 21 /𝑑𝑓 21 . . . 𝑑𝑣 21 /𝑑𝑓 𝑝𝑞 𝑑𝑣 𝑝𝑞 /𝑑𝑓 11 𝑑𝑣 𝑝𝑞 /𝑑𝑓 21 . . . 𝑑𝑣 𝑝𝑞 /𝑑𝑓 𝑝𝑞 𝑑𝑣 11 , 𝑑𝐿/𝑑𝑣 21 , . . . , 𝑑𝐿/𝑑𝑣 𝑝𝑞 ] [𝑔 11 , 𝑔 21 , 𝑔 31 , . . . , 𝑔 𝑝𝑞 ] For efficiency, we first compute the offset matrix 𝐻 for all candidate matches. 11 ℎ 12 ℎ 13 . . . ℎ 1𝑝 ℎ 21 ℎ 22 ℎ 23 . . . ℎ 2𝑝

	𝐻 =	⎡ ⎢ ⎢ ⎢ ⎣	ℎ . . .	. . .	. . .	. . .	. . .
	⎡						⎤
	⎢ ⎢ ⎢ ⎣ = [𝑑𝐿/(4.15) . . . . . . . . . . . . ⎥ ⎥ ⎥ ⎦

Table 4 .

 4 2: Fixed-threshold PCK on PF-WILLOW. PCK is averaged over all classes.

		.197	0.322	0.449
	LIFT 6 [108]	0.224	0.346	0.489
	VGG [87]	0.224	0.388	0.555
	FCSS [54]	0.354	0.532	0.681
	UCN-ST-GL	0.215	0.334	0.440
	UCN-ST-PF	0.291	0.417	0.513
	SCNet-A	0.390	0.725	0.873
	SCNet-AG	0.394	0.721	0.871
	SCNet-AG+	0.386	0.704	0.853

Table 4

 4 .3 compares quantitatively the matching accuracy of SCNet to the state of the art. It shows that SCNet-AG+ outperforms other approaches, for all metrics. Our results verify that SCNet models successfully learn semantic correspondence.

	Source	Source	Source	Source	Source	Source
	Target	Target	Target	Target	Target	Target
	SCNet-A	SCNet-A	SCNet-A	SCNet-A	SCNet-A	SCNet-A
	SCNet-AG	SCNet-AG	SCNet-AG	SCNet-AG	SCNet-AG	SCNet-AG
	SCNet-AG+	SCNet-AG+	SCNet-AG+	SCNet-AG+	SCNet-AG+	SCNet-AG+
	HOG NAM	HOG NAM	HOG NAM	HOG NAM	HOG NAM	HOG NAM
	HOG PHM	HOG PHM	HOG PHM	HOG PHM	HOG PHM	HOG PHM
	HOG LOM	HOG LOM	HOG

LOM HOG LOM HOG LOM HOG LOM

Table 4 .

 4 3: Results on Caltech-101.

		.78	0.50	0.26
	DeepFlow [77]	0.74	0.40	0.34
	SIFT Flow [59]	0.75	0.48	0.32
	DSP [52]	0.77	0.47	0.35
	SCNet-A	0.78	0.50	0.28
	SCNet-AG	0.78	0.50	0.27
	SCNet-AG+	0.79	0.51	0.25

  -9 shows again LBAM outperforming PHM (AuC of 0.36 for LBAM and 0.32 for PHM), but both are outperformed by LOM (AuC of 0.42).

				PCR plots				mIoU@k plots
		1					1
			PHM [0.404]				PHM [0.525]
			LOM [0.456]				LOM [0.553]
			LBAM [0.464]				LBAM [0.557]
		0.8	Upper bound [0.686]			0.8
	PCR	0.6				mIoU@k	0.6
		0.4					0.4
		0.2					0.2
		0 0	0.2	0.4 IoU threshold, τ 0.6	0.8	1	0	20 Number of top matches, k 40 60 80	100

  1 1 𝑦𝑚-𝑧𝑚≥0 ; (4.29) 𝑑𝐿/𝑑𝑉 = 𝑑𝐿/𝑑𝑍 • 𝐹 ; (4.30) 𝑑𝐿/𝑑𝐹 = 𝑑𝐿/𝑑𝑉 • 𝑑𝑉 /𝑑𝐹 ; (4.31) 𝑑𝐿/𝑑𝑓 𝑚 = ∑ 𝑚 ′ ∈𝒟 𝑑𝐿/𝑑𝑣 𝑚 ′ .𝑑𝑣 𝑚 ′ /𝑑𝑓 𝑚 (4.32) 𝐺 𝑚𝑚 ′ 𝛿 𝑚𝑚 ′ . (4.33) For PHM scores, the gradient computation of 𝑧 𝑚 benefits from the sparsity of matrix 𝐾, as explained in subsection 4.3.3. A similar sparsity is obtained for LBAM due to the restriction to one match by proposal. This sparsity is represented by 𝛿 𝑚𝑚 ′ and allows us to compute only parts of the 𝑛 × 𝑛 matrix 𝐺. We thus consider the sparse 𝑛 × 𝑛 matrix ∆, where 𝛿 11 𝛿 12 𝛿 13 . . . ℎ 1𝑛 𝛿 21 𝛿 22 𝛿 23 . . . 𝛿 2𝑛 𝛿 𝑛1 𝛿 𝑛2 𝛿 𝑛3 . . . 𝛿 𝑛𝑛

			=	∑ 𝑚 ′ ∈𝒟	𝑑𝐿 𝑑𝑣 𝑚 ′
		⎡						⎤
	∆ =	⎢ ⎢ ⎢ ⎣	. . .	. . .	. . .	. . .	. . .	⎦ ⎥ ⎥ ⎥	,	(4.34)

  Le problème de représentation d'image est au coeur du domaine de vision. Le choix de représentation d'une image change en fonction de la tâche que nous voulons étudier. Un problème de recherche d'image dans des grandes bases de données exige une représentation globale compressée, alors qu'un problème de segmentation séantique nécessite une carte de partitionnement de ses pixels. Les techniques d'apprentissage statisque sont l'outil principal pour la construction de ces représentations. Dans ce manuscrit, nous abordons l'apprentissage des représentations visuels dans trois problèmes différents : la recherche d'image, la correspondance sémantique et classification d'image. Premièrement, nous étudions la représentation vectorielle de Fisher et sa dépendence sur le modèle de mélange Gaussien employé. Nous introduisons l'utilisation de plusieurs modèles de mélange Gaussien pour différents types d'arrière-plans, i.e. différentes catégories de scène, et analyser la performance de ces représentations pour objet classification et l'impact de la catégorie de scène en tant que variable latente. Notre seconde approche propose une extension de la représentation l'exemple SVM pipeline. Nous montrons d'abord que, en remplaçant la fonction de perte de la SVM par la perte carrée, on obtient des résultats similaires à une fraction de le coût de calcul. Nous appelons ce modèle la « square-loss exemplar machine », ou SLEM en anglais. Nous introduisons une variante de SLEM à noyaux qui bénéficie des même avantages coputationnelles mais affiche des performances améliorées. Nous présentons des expériences qui établissent la performance et l'efficacité de nos méthodes en utilisant une grande variété de représentations de base et de jeux de données de recherche d'images. Enfin, nous proposons un réseau neuronal profond pour le problème de l'établissement sémantique correspondance. Nous utilisons des boîtes d'objets en tant qu'éléments de correspondance pour construire une architecture qui apprend simultanément l'apparence et la cohérence géométrique. Nous proposons de nouveaux scores géométriques de cohérence adaptés à l'architecture du réseau de neurones. Notre modèle est entraâiné sur des paires d'images obtenues à partir des pointsclés d'un jeu de données de référence et évaluées sur plusieurs ensembles de données, surpassant les architectures d'apprentissage en profondeur récentes et méthodes antérieures basées sur des caractéristiques artisanales. Nous terminons la thèse en soulignant nos contributions et en suggérant d'éventuelles directions de recherche futures. Mots Clés

Représentation d'image, recherche d'image, modèle à noyaux, réseau de neurone, correspondance de région, correspondance sémantique, vecteurs de Fisher.

The dimension of FV does not change with 𝑑, we plot it as a straight line to better compare with the projected FV

In the remaining of this manuscript, we treated the pool of negatives as a matrix 𝑋. Exceptionally in this section, we treat the pool as a set in order to facilitate our notation

𝐾 is, by the definition of a kernel matrix, a positive-semidefinite matrix and so its eigenvalues are non-negative. In practice, when we compute 𝐾 for a Gaussian kernel, a few eigenvalues are negative and of absolute value smaller than 10 -8 , due to floctuations of the Gaussian variables. We set 𝜖 = 10 -8 to avoid the recalculation 𝜆 𝑚𝑖𝑛 .

Putting it all together in an 𝑛-vector of scores, this can also be rewritten as 𝑧(𝑤) = 𝑓 (𝑤) ⊙

If the geometry kernel is dependent on something other than offsets, e.g., matches' absolute position or their neighborhood structure, this sharing is not possible.

We take Ω(𝑤) = 0 for simplicity in this section, but tackling a nonzero regularizer is easy.

http://www.di.ens.fr/willow/research/proposalflow/

To better take into account the different sizes of images, we normalize the distance by dividing by the diagonal of the warped image, as in[START_REF] Choy | Universal correspondence network[END_REF]

Acknowledgements

This work was supported by the ERC grants VideoWorld and the Institut Universitaire de France. ix x

 4.1: Per-class PCK on PF-PASCAL at 𝜏 = 0.1. For all methods using object proposals, we use 1000 RP proposals [START_REF] Manen | Prime object proposals with randomized Prim's algorithm[END_REF].

Evaluation metric for flow field Since matching images vary in sizes, the metric needs to take into account the size of target images in measuring distances between predicted keypoints and groundtruth keypoints, i.e., the predicted keypoint is deemed correct if it lies at most 𝛼𝐿 of the groundtruth keypoint. Ham et al. [START_REF] Ham | Proposal flow[END_REF] set 𝐿 = 𝑚𝑎𝑥(ℎ, 𝑤), where ℎ×𝑤 is the size of the groundtruth object bounding box of the target image, whereas Choy et al. [START_REF] Choy | Universal correspondence network[END_REF] set 𝐿 = √ 𝐻 2 + 𝑊 2 for experiments on CUB2011 and 𝐿 = 𝑚𝑎𝑥(𝐻, 𝑊 ) for all other experiments, with 𝐻 × 𝑊 being the size of the target image. In evaluating PCK, this work follows the protocol of [START_REF] Choy | Universal correspondence network[END_REF].

Results on PF-PASCAL. We compare SCNet-A, SCNet-AG, and SCNet-AG+ with proposal flow methods [START_REF] Ham | Proposal flow[END_REF] and UCN [START_REF] Choy | Universal correspondence network[END_REF] on PF-PASCAL dataset, and summarize the result in Table 4.1. The UCN is retrained on the PF-PASCAL dataset for fair comparison. The results of UCN* are obtained using the author-provided network

Conclusion

We have introduced a novel model for learning semantic correspondence, and proposed the corresponding CNN architecture that uses object proposals as matching primitives and learns matching in terms of appearance and geometry. The proposed method substantially outperforms both recent deep learning architectures and previous methods based on hand-crafted features. The result clearly demonstrates the effectiveness of learning geometric matching for semantic correspondence. In the work currently been done, we propose a new model for leverage geometric information between matches and we wish to explore it a improved architecture.

Abstract

The problem of image representation is at the heart of computer vision. The choice of feature extracted of an image changes according to the task we want to study. Large image retrieval databases demand a compressed global vector representing each image, whereas a semantic segmentation problem requires a clustering map of its pixels. The techniques of machine learning are the main tool used for the construction of these representations. In this manuscript, we address the learning of visual features for three distinct problems: Image retrieval, semantic correspondence and image classification. First, we study the dependency of a Fisher vector representation on the Gaussian mixture model used as its codewords. We introduce the use of multiple Gaussian mixture models for different backgrounds, e.g. different scene categories, and analyze the performance of these representations for object classification and the impact of scene category as a latent variable. Our second approach proposes an extension to the exemplar SVM feature encoding pipeline. We first show that, by replacing the hinge loss by the square loss in the ESVM cost function, similar results in image retrieval can be obtained at a fraction of the computational cost. We call this model square-loss exemplar machine, or SLEM. Secondly, we introduce a kernelized SLEM variant which benefits from the same computational advantages but displays improved performance. We present experiments that establish the performance and efficiency of our methods using a large array of base feature representations and standard image retrieval datasets. Finally, we propose a deep neural network for the problem of establishing semantic correspondence. We employ object proposal boxes as elements for matching and construct an architecture that simultaneously learns the appearance representation and geometric consistency. We propose new geometrical consistency scores tailored to the neural network's architecture. Our model is trained on image pairs obtained from keypoints of a benchmark dataset and evaluated on several standard datasets, outperforming both recent deep learning architectures and previous methods based on hand-crafted features. We conclude the thesis by highlighting our contributions and suggesting possible future research directions.