The goal of this thesis is to develop deep learning methods for artwork analysis. More precisely, we focus on three particular tasks: style-invariant patterns retrieval, nearduplicated patterns discovery, and dense image alignment. All the tasks are very challenging from a computer vision point of view, main difficulties include: i) no annotations are available so that the approach we develop needs to be unsupervised ; ii) there are differences in the artistic media (oil, pastel, drawing, etc) of the different depictions we want to analyze, so we face cross-domain problems.

Our first task, style-invariant patterns retrieval aims at finding relevant motifs in a collection of artworks similar to a given query motif. The retrieved motifs should depict the same content but might have different styles. The task is motivated by several image search applications in art images and historical documents. Beyond heritage images, image retrieval has been widely used in image search tools such as Google Image Search 1 .

Our second task, near-duplicated patterns discovery aims at identifying repeated visual patterns in a collection of artworks. The task is motivated by finding visual correspondences among artworks, which might indicate authorship and provenance. Beyond art history, near-duplicated pattern discovery can be used to discover common objects in generic image collection, which can be useful to ease data annotation processes.

Our third task, dense image alignment aims at predicting pixel-level alignment between images. Our goal is to compare two paintings or details of two artworks depicting the same content but with different styles. On natural images, optical flow is also beneficial to two-view geometry estimation and 3D reconstruction.

This thesis includes three technical contributions.

 bru) dataset which allows evaluating one-shot cross-domain art detail detection.

 architecture, and show that employing Poisson Blending (Pérez et al., 2003) and style transfer is crucial for generalization. In terms of results, the trained transformer improves performance on near-duplicated art detail detection and discovery. Additionally, we show that our approach performs well on place recognition and object discovery in natural images.

Our last contribution is a two-stage method for generic image alignment. In the coarse stage, we estimate Homography transformations between a pair of images using standard deep feature matches and RANSAC; in the fine stage, we design and learn a Convolutional Neural Network (CNN) to predict pixel-level alignment using a reconstruction loss. The proposed approach is simple and allows aligning near-duplicated art patterns. On natural images, the proposed approach shows competitive or better performance across different tasks: optical flow estimation, sparse correspondences evaluation, two-view geometry estimation, 3D reconstruction, and aligning Internet images.

Résumé

L'objectif de cette thèse est de développer des méthodes d'apprentissage profond pour l'analyse d'oeuvres d'art. Plus précisément, nous nous concentrons sur trois tâches particulières : la recherche de motifs invariants de style, la découverte de motifs quasi-dupliqués et l'alignement dense d'images. Toutes les tâches sont très difficiles du point de vue de la vision par ordinateur, les principales difficultés incluent : i) aucune annotation n'est disponible, de sorte que l'approche que nous développons doit être non-supervisée; ii) il existe des différences dans les supports artistiques (huile, pastel, dessin, etc.) des différentes représentations que nous voulons analyser, nous sommes donc confrontés à des problèmes inter-domaines.

Notre première tâche, style-invariant patterns retrieval vise à trouver des motifs pertinents dans une collection d'oeuvres d'art similaires à un motif de requête donné. Les motifs récupérés doivent représenter le même contenu mais peuvent avoir des styles différents. La tâche est motivée par plusieurs applications de recherche d'images dans des images d'art et des documents historiques. Au-delà des images patrimoniales, la recherche d'images est largement utilisée par exemple dans les outils de recherche d'images tels que Google Image Search2 .

Notre deuxième tâche, découverte de motifs quasi-dupliqués vise à identifier des motifs visuels répétés dans une collection d'oeuvres d'art. La tâche est motivée par la recherche de correspondances visuelles entre les oeuvres d'art, qui pourraient indiquer la paternité et la provenance. Au-delà de l'histoire de l'art, la découverte de motifs similaires peut être utilisée pour découvrir des objets communs dans une collection d'images naturelles, ce qui peut être utile, par exemple, pour faciliter le processus d'annotation des données.

Notre troisième tâche, alignement dense d'images vise à prédire l'alignement au niveau des pixels entre les images. Notre objectif est de comparer deux tableaux ou des détails d'oeuvres d'art représentant le même contenu mais avec des styles différents. Sur les images naturelles, le flux optique est également bénéfique pour l'estimation de la géométrie à deux vues et la reconstruction 3D.

Cette thèse comprend trois contributions techniques. Notre première contribution est une approche auto-supervisée pour adapter un vi descriptor standard de reseau de neurones pour la correspondance entre domaines en fine-tuning sur la collection d'art spécifique. Plus précisément, nous utilisons la cohérence spatiale entre les correspondances de caractéristiques voisines comme supervision. Le descriptor de reseau de neurones adapté conduit à une correspondance invariante de style plus précise. Nous utilisons de la correspondance de multi-résolution et de la vérification géométrique pour identifier des modèles presque dupliqués dans l'ensemble de données. Parallèlement à l'approche, nous proposons également un ensemble de données que nous appelons Brueghel [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]bru) qui permet d'évaluer la détection des détails de l'art inter-domaines. Notre deuxième contribution est l'apprentissage de la co-segmentation pour une paire d'images sur un jeu de données synthétique. Nous générons des paires d'entraînement en mélangeant des objets dans une image d'arrière-plan et en appliquant un transfert de style à la composition résultante. En conséquence, nous avons accès aux masques de vérité terrain des objets mélangés et aux correspondances entre l'image originale et l'image synthétisée. Nous comparons empiriquement les performances obtenues avec deux réseaux : Sparse Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF] et une architecture à base de transformer [START_REF] Vaswani | Attention is all you need[END_REF], et montrons que l'utilisation de Poisson Blending [START_REF] Pérez | Poisson image editing[END_REF] et de transfert de style est cruciale pour la généralisation. En termes de résultats, le transformer entraîné améliore les performances de détection et de découverte des détails d'art presque dupliqués. De plus, nous montrons que notre approche fonctionne bien sur la reconnaissance de lieux et la découverte d'objets dans les images naturelles.

Notre dernière contribution est une méthode en deux étapes pour l'alignement d'images génériques. Au stade grossier, nous estimons les transformations d'homographie entre une paire d'images en utilisant des correspondances de descriptors standard de reseau de neurones et RANSAC ; au stade avancé, nous concevons et apprenons un réseau de neurones convolutifs (CNN) pour prédire l'alignement au niveau des pixels à l'aide d'une perte de reconstruction. L'approche proposée est simple et permet d'aligner des motifs artistiques presque dupliqués. Sur les images naturelles, l'approche proposée montre des performances compétitives ou meilleures sur différentes tâches : estimation de flux optique, évaluation de correspondances creuses, estimation de géométrie à deux vues, reconstruction 3D et alignement d'images Internet. This thesis would not have been possible without the help and nurturing of many people.

I would like to express my deepest gratitude to my advisor, Mathieu, for your patience, guidance, and support. I have greatly benefited from your wealth of knowledge and meticulous editing. I am very grateful that you took me on as a student and continued to have faith in me over the years. I am also extremely thankful to Alyosha and Armand. I learn a lot from you and feel extremely lucky to work with you. I enjoyed all the discussions with you.

I would like to warmly thank all my committee members. It was not easy to organize the defense across different time zones. Thanks for everyone's effort to make my defense possible. Special thank Prof.Gousseau and Prof.Heutte for the detailed comments on the manuscript. I am also grateful to Dr.Ginosar and Dr.Pérez for having accepted to be part of the jury.

I am fortunate to have been a part of the Imagine group, where I greatly enjoyed my life as a Ph.D. student. Thanks for everyone's effort to create a fantastic lab atmosphere. Some moments have been deeply imprinted on my memory: hiking, football, beer, conference, Christmas meal, etc. Thanks to David and Vincent for leading the lab and handling all the issues of the lab. Thanks to Guillaume, Renaud, Gül, Pascal, Bertrand and Chaohui for all the feedbacks, reviews of my works as well as joyful discussions during coffee sessions. Thanks to Thibault (for the crazy California camping and a lot of things), Theo (for hosting me as a family member), François (for the great collaboration), Abdou (for your patience to answer all my stupid questions), Tom (for organizing foot, student meetings and everything), Georgy (for being the nicest office mate), Yanis (for all the ideas we had brainstormed), Othman and Pierre-Alain (for always being with me in ENPC), Yang (for always waiting for me until 10pm to leave the office), Yumin (for tasty chinese dishes), Thomas (for your kindness vii to help everyone including me in the lab), Xuchong (for the excellent trip in Ile de Ré), Shell (for treating me as a younger brother and helping me on developing research ideas), Simon (for all the cool stuffs you taught me and your excellent football skills), Nguyen (for sharing fascinating vietnamese culture), Michaël (for all the interesting experiences shared with me and valuable comments on my works), Robin (for sharing your only machine with me and being extremely nice to me even I made stupid bugs on the machine), Oumayma (for the great project working together and your interests on chinese culture), Nicolas (for lots of useful suggestions and deep communications), Mathis (for your tips on my works and efforts you made to share knowledge on reading groups), Elliot (for being my excellent foot teammate), Yue (for helping me searching the apartment), Rahima (for being extremely nice to me and sharing all the complicated administrative information with me), Victor (for funny jokes during beer sessions), Romain (for sharing your practical working tools and experiences), Hugo (for tips on interns and interviews), Giorgia (for working, playing and doing sports together). I am not a very talkative person and would like to take this opportunity to thank everyone. I had a lot of great time in lovely Paris.

I also would like to thank my friends Yuan, Yuxiang, Xijun, Tong, Ling, Yi, Yuelu, Dexiong, Huiqin, and many others. Thanks for supporting me, despite the distance.

Last but not least, I want to express special thanks to my grandfather and my parents. Thanks for your love and the courage you had to bring me to this world. Thanks to my brother and my girlfriend. Thank you for your unfailing support and understanding.

Chapter 1 Introduction

Goals

When creating an artwork, it is common for an artist to reuse the same visual elements or motifs. However, the different versions might be differ in terms of color, style, artistic media, and geometric deformation. Identifying repeated patterns yield insights on artworks circulations and provenance, which is important for Art Historians. The goal of this thesis is to develop deep learning methods for artwork analysis with a focus on three tasks: (i) style-invariant patterns retrieval, (ii) discovering near-duplicated visual patterns in a collection of artworks, (iii) dense image alignment. These tasks are illustrated in Fig. 1.1.

Style-invariant patterns retrieval aims at retrieving motifs similar to a given query pattern. The relevant motifs have the same content, whereas styles and context might be different. An example from the Venus collection [START_REF] Shen | Spatially-consistent feature matching and learning for art collections and watermark recognition[END_REF] is shown in Fig. 1.1a. We can see the top retrieved artworks contain the same motif as the queries but have a very different appearance.

Near-duplicated patterns discovery aims at identifying near-duplicated patterns in a collection of images independently of any queries. Unlike image clustering, we do not assume that every image in the collection is associated to a unique pattern and we also aim at localizing the repeated patterns. An example on the Brueghel [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]bru) dataset is given in Fig. 1.1b. We are interested in identifying the groups of repeated visual details (shown in red, blue and green circle), they might be present in only a couple of images, an image may contain different details and most images do not contain any.

Dense image alignment aims at estimating pixel-level alignment between images that depict similar content. We design a generic image alignment algorithm, with a specific focus on the capacity to align images from different visual domains, e.g. artwork depicting the same content with different styles. An example on the Brueghel [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]bru) dataset can be seen in Fig. 1.1c.

The above three tasks can be complementary for artwork analysis. On artwork analysis, if queries are available, we could retrieve artworks containing relevant motifs and focus on analyzing on top retrieved artworks. If no queries are available, we could perform discovery on the dataset and study the discovered clusters. For both cases, detailed analysis is possible through dense alignment.

Motivations

Although this thesis mainly focuses on artworks analysis, the three tasks addressed in the thesis are core computer vision problems. They are also motivated by a number of applications beyond artworks analysis.

Image retrieval. Retrieving relevant images is an important problems in computer vision. The task has several applications I tackled during my PhD but are not discussed in details in this thesis: place recognition (Shen et al., 2021a), historical watermark recognition (Shen et al., 2020b), sketch-based image retrieval (Shen et al., 2020b) and matching illustrations in copied manuscripts [START_REF] Kaoua | Image collation: Matching illustrations in manuscripts[END_REF]):

• Place recognition (Fig. 1.2a, (Shen et al., 2021a)). Given a query image and a database of geolocated images, the goal is to retrieve an image of the same place. One challenge is that the images can have very different appearance, e.g. images taken during day-time and night-time.

• Historical watermark recognition (Fig. 1.2b, (Shen et al., 2020b)). Queries are photographs of historical documents and the searching database consists of drawings of watermarks, the goal is to identify the watermark in the database (a) Place recognition. Given a query image and a database of geolocated images, the goal is to retrieve an image of the same place.

(b) Historical watermark recognition. Given a query historical document and a database of drawings of watermarks, the goal is to identify the drawing in the database which corresponds to the historical document.

(c) Sketch-based image retrieval. Given a query sketch and a database of natural images, the goal is to retrieve natural images correspond to the content of sketch.

(d) Matching illustrations in copied manuscripts. Given illustrations from copied manuscripts, the goal is to match illustrations in manuscripts. which can be seen in the photograph. The watermark provides clues to date and locate paper, which is useful for historians. The main challenges include fine-grained search, lack of annotations and the fact that watermarks in the query photographs have a very different appearance compared to the drawings in the database.

• Sketch-based image retrieval (Fig. 1.2c, (Shen et al., 2020b)). Given a query sketch and a database of natural images, the goal is to retrieve natural images correspond to the content of sketch. The application can be a tool for image search when looking for a specific instance of an object, e.g. a specific type of shoes, because it is easier to draw characteristics than describe them. The task is challenging as the search is fine-grained, cross-domain and some details might not be drawn in the query sketches.

• Matching illustrations in copied manuscripts (Fig. 1.2d, [START_REF] Kaoua | Image collation: Matching illustrations in manuscripts[END_REF]). Historical manuscripts often exist in different versions made by different copyists and illustrations might even be re-used in different texts. The goal of this task is to find corresponding illustrations in several manuscripts. In the case of scientific manuscripts (e.g. botanical), retrieving corresponding illustrations might help historians to understand the evolution of scientific knowledge. The task is difficult because the order of the illustrations might differ in different manuscripts and content and styles might be changed in corresponding illustrations.

Object discovery. The task is to automatically discover repeated objects in a dataset without any human annotations. Most visual analysis deep learning works rely on annotations [START_REF] He | Deep residual learning for image recognition[END_REF][START_REF] Luo | Geodesc: Learning local descriptors by integrating geometry constraints[END_REF], which are costly. It would be much more efficient to be able to directly analyze a collection of images and identify the repeated objects. The main application of object discovery is to automatically collect dataset annotations.

Imagine for example we want to collect segmentation annotations of cars. First, we can search relevant images correspond to a key word "Car" through an image search engine such as Google Search 1 . The gathered images are noisy i.e. it might Object discovery allows automatically collecting annotations from Internet images. Examples are from [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF]. A noisy dataset can be gathered via Internet searching engine then discovering common objects can remove distractors and obtain segmentation annotations.

include irrelevant images such as images of wheel, logos of cars etc. An image discovery algorithm should be able to take this noisy non-annotated dataset, identify the relevant car images and even provide pixel-level annotations. A classical approach to this task is the one of [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF] • Autonomous driving (Fig. 1.4a, [START_REF] Geiger | Are we ready for autonomous driving? the kitti vision benchmark suite[END_REF]). Estimating the optical flow between images taken by cameras in a vehicle could be leveraged for autonomous driving applications. The input images often have little appearance difference and the dense optical flow yield insights into the geometric layout of a scene as well as its decomposition into individually moving objects.

• 3D reconstruction (Fig. 1.4b, (Shen et al., 2020a;Truong et al., 2021a)).

Dense optical flow can be useful for two-view geometry estimation and reconstructing meaningful 3D models from a pair of images (Shen et al., 2020a) (Fig. 1.4, left). Dense optical flow can also replace keypoints matches and be used in multi-view 3D reconstruction (Truong et al., 2021a) (Fig. 1.4, right).

• Medical image alignment (Fig. 1.4c, [START_REF] Hill | Medical image registration[END_REF]). In medical applications, multiple medical images can be acquired at different times. To compare (a) Autonomous driving. Optical flow (2nd row) provides insight to segment moving objects (1st row). Images from (Menze and Geiger, 2015b).

(b) 3D reconstruction. Dense flow field between a pair of images allows 3D reconstruction (left, two-view geometry estimation (Shen et al., 2020a)). Dense flow can also replace keypoint matches for multi-view 3D reconstruction (right, 3D reconstruction of Aachen [START_REF] Sattler | Benchmarking 6dof outdoor visual localization in changing conditions[END_REF]Truong et al., 2021a) ) .

(c) Medical images alignment. Axial slices from average images produced from MR scans, alignment using rigid registration (left), affine registration (middle) and non-rigid registration (right).

Figures from [START_REF] Hill | Medical image registration[END_REF]. the images and analyze their evolution, it would be useful to be able to align densely the images.

Challenges

To solve our tasks, we will face three important challenges: lack of supervision, handling domain gap between the depictions, and a scalability issue. These challenges are illustrated in Fig. 1.5.

Lack of supervision.

One critical challenge is that we cannot assume any annotations are available. Indeed, it is expensive and time consuming to collect annotations. For patterns retrieval, the annotations need to be specific to a collection and it is hard for a human expert to find the same motifs when the size of the collection becomes large. For discovery, the annotation process is even more difficult, as one needs to identify all repeated patterns in a collection and the annotations should include segmentation. For dense image alignment, the annotations would need to be done pixel-wise. Indeed, the defomations happenning during the copy process are far from being parametric or rigid, for example in the example of Fig. 1.5a, the three characters groups are clearly moving with respect to each other. Note that collecting annotations is also a general challenge for many other applications in vision, such as object detection [START_REF] Lin | Microsoft coco: Common objects in context[END_REF], semantic segmentation [START_REF] Zhou | Scene parsing through ade20k dataset[END_REF] and 3D reconstruction [START_REF] Li | Megadepth: Learning single-view depth prediction from internet photos[END_REF] etc.

Diversity of depiction styles. For artists, it is common to reuse the same visual patterns. However, the depiction styles might be different. An example is shown in Fig. 1.5b, the same content (Man on Egg) is repeated in four artworks but depicted using different media and with different styles. Note that handling domain gap is also an important and general challenge in computer vision. Related active research topics include domain adaptation [START_REF] Saenko | Adapting visual category models to new domains[END_REF] and domain generalization [START_REF] Li | Deeper, broader and artier domain generalization[END_REF].

Scalability. We also face a scalability issue for patterns retrieval and discovery problem. For retrieval, we aims at retrieving the same patterns at any scales in a large dataset. For discovery, in addition to the scale issue, the repeated patterns might be present only in a couples of images in a large collection of artworks. An (c) Scalability. We want to identify repeated patterns (horse in green circle) in a large dataset that could have any scales in the images, which is very computationnaly difficult. example is shown in Fig. 1.5c, the horses (in green circle) are repeated but with very different scales in the images, and they are present only in a few images of a large dataset (∼ 20 occurences over 1,587 images). Our algorithm thus has to scale to large datasets, without missing rare occurence of small details.

Contributions

In this thesis, we have three main technical contributions.

Self-supervised style-invariant feature learning. Our first contribution is a self-supervised feature fine-tuning strategy to address style-invariant feature matching. Our key insight is leveraging spatial consistency to identify positive and negative training pairs. The training pairs are then used to optimize a standard triplet loss, which leads to features adapted to the training set for correspondences. We show that the proposed approach enables matching features across different domains. We validate our fine-tuning strategy on artwork datasets as well as geo-localization datasets.

Learning co-segmentation from synthetic data. Our second contribution is an approach of learning co-segmentation from synthetic data. To generate the synthetic data, we blend objects to background images using style transfer and Poisson blending [START_REF] Pérez | Poisson image editing[END_REF]. We also propose a transformer-based architecture [START_REF] Vaswani | Attention is all you need[END_REF] for co-segmentation. We demonstrate that it is important to include correspondences in the objective function. The approach is validated on various tasks including one-shot art detail detection and place recognition.

Unsupervised two-stage robust dense image alignment. Our last contribution is an unsupervised approach for robust dense image alignment. Our approach contains two stages: in the first stage, we estimate Homography transformations based on standard multi-scale feature matching and RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF]; in the second stage, we learn a Convolutional Neural Network (CNN) through the optimization of a reconstruction loss between target images and warped source images. The entire pipeline is unsupervised. We show that our approach performs well on various tasks, including standard optical flow estimation, sparse correspondences evaluation, two-view geometry estimation, and 3D reconstruction.

Thesis Outline

This thesis is organized as follows.

Chapter 2: Related Work. We first review deep learning-based approaches for artworks analysis in Sec. 2.1. In Sec. 2.2, we study related works on image retrieval.

We then provided analysis on object discovery and co-segmentation approaches that are related to this thesis in Sec. 2.3. Finally, we review deep-learning based approach for dense image alignment in Sec. 2.4.

Chapter 3: Learning Features for Artworks Analysis. This chapter presents the first contribution of this thesis : our self-supervised feature fine-tuning strategy.

We explain the feature learning strategy in Sec. 3.3. We leverage it to perform object discovery using a simple approach based on multi-scale feature matching and RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF], which is detailed in Sec. 3.4. In Sec. 3.5, we introduce the Brueghel dataset [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] and present experimental results of the feature fine-tuning strategy and of the discovery approach on various art image datasets as well as geo-localisation datasets.

Chapter 4: Learning Co-segmentation for Art Pattern Discovery. This chapter is about the second contribution of this thesis: learning co-segmentation from synthetic data. Our training data generation, as well as two architectures, are detailed in Sec. 4.3. In Sec. 4.4, we present how to employ the output of the networks to perform image retrieval. The approach is validated on two completely different tasks: one-shot art detail detection and place recognition. We finally show how to leverage the output of the networks for object discovery with using classical spectral clustering on a correspondence graph in Sec. 4.5.

Chapter 5: Unsupervised Dense Image Alignment. This chapter includes the last contribution of this thesis: Unsupervised two-stage robust dense image alignment. In Sec. 5.3, we present our two-stage image alignment approach. Beyond qualitative results on artworks alignment, we validate the approach on various tasks including: optical flow evaluation (Sec. 5.4.1), sparse correspondences evaluation (Sec. 5.4.1), two-view geometry estimation (Sec. 5.4.2) and day-night visual Localization (Sec. ??).

With the precise optical flow, we also explore several applications in Sec. 5.4.3, such as: texture transfer and Internet images alignment.

Chapter 6: Conclusion. We conclude with a summary of contributions of this thesis, discussion and suggestions on future research directions.

Publication List

This thesis presents the contribution made in four papers [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF](Shen et al., , 2021a(Shen et al., , 2020a[START_REF] Shen | Spatially-consistent feature matching and learning for art collections and watermark recognition[END_REF]):

• Xi Shen We open-sourced and maintained implementations corresponding to the four papers2 , the implementation of ArtMiner [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] and RANSAC-Flow (Shen et al., 2020a) on GitHub received 100 and 307 stars respectively.

We also extend the discovery score in the first publication [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] to weakly supervised watermark recognition and unsupervised image collation, which led to the following publications (Shen et al., 2020b;[START_REF] Bounou | A web application for watermark recognition[END_REF][START_REF] Kaoua | Image collation: Matching illustrations in manuscripts[END_REF] During my Ph.D., I also worked on learning with weak supervision (weakly supervised learning) and few samples (few-shot learning), which results in the following publications which are not directly related to the work presented in this thesis [START_REF] Yuan | Marginalized average attentional network for weakly-supervised learning[END_REF][START_REF] Hu | Empirical bayes transductive meta-learning with synthetic gradients[END_REF]Shen et al., 2021b):

• Xi Shen, Yang Xiao, Shell Xu Hu, Othman Sbai and Mathieu Aubry.

Re-ranking for Image Retrieval and Transductive Few-shot Classification.

Chapter 2

Related Work

Deep Learning for Artwork Analysis

There is a long-standing and fruitful collaboration between computer vision and art.

For artists and art historians, deep learning becomes a practical tool to analyze and create art. In this section, we discuss deep learning approaches on four topics which are related to artworks analysis: i) artwork retrieval and artistic influence discovery; ii) artwork attributes classification; iii) object detection in artworks; iv) creating art. These topics outline some main research trends and directions.

Artwork retrieval and artistic influence discovery. An important task for art historians is identifying similarity relationships between artworks of different artists and painting schools. These relationships enable art historians to discover the provenance and influences from an artistic movement to another [START_REF] David | From brueghel to warhol: Ai enters the attribution fray[END_REF]. Previous works on this topics can be roughly divied into two directions: i) artwork retrieval: when a query artwork is given and it is required to retrieve relevant artworks; ii) artwork clustering: we are asked to analyse relationships of artworks in a dataset without using any annotations.

For artwork retrieval, based on traditional handcraft features, [START_REF] Shrivastava | Data-driven visual similarity for cross-domain image matching[END_REF] computed visual similarity between images cross different domains and show that the proposed algorithm worked also for art images. In deep era, [START_REF] Crowley | Face painting: querying art with photos[END_REF] aimed at matching photos of a person to paintings of the same person. It showed that Convolutional Neural Network (CNN) representations perform clearly better than traditional descriptors. Training on manually annotated artworks, [START_REF] Seguin | Visual link retrieval in a database of paintings[END_REF] has shown that a pre-trained CNN performs better than a classic bagof-words method in predicting whether pairs of paintings are visually related to each other. DeepArt [START_REF] Mao | Deepart: Learning joint representations of visual arts[END_REF] learned visual art representations for retrieval by a triplet-based deep ranking method. [START_REF] Dovgalecs | Spot it! finding words and patterns in historical documents[END_REF] proposed a system for patterns spotting in historical documents, which aimed at detecting the same patterns, based on a user made query. The system employed a two-stage approach: an offline feature extraction based on SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] and bag-of-words features and an online query search phase. The performance can be improved through a siamese neural network [START_REF] Wiggers | Image retrieval and pattern spotting using siamese neural network[END_REF] and feature pyramid networks [START_REF] Ubeda | Improving pattern spotting in historical documents using feature pyramid networks[END_REF]. Beyond the advancement in research, several projects have built search engines for artworks (img; tim).

For artwork clustering, [START_REF] Gultepe | Predicting and grouping digitized paintings by style using unsupervised feature learning[END_REF] employed k-means on the top of features which were then fed into a spectral clustering algorithm to group paintings. Similarly, [START_REF] Castellano | Towards a tool for visual link retrieval and knowledge discovery in painting datasets[END_REF]Castellano et al., 2021;Castellano and Vessio, 2021) proposed a method aimed at finding visual links among paintings in a completely unsupervised way. Their methods are built upon visual attributes learned by a deep pre-trained model. Furthermore, they showed that influences between painters could be exploited from the retrieved paintings.

Artwork attributes classification. In visual art, another research direction aims at recognizing some artwork attributes such as artist, genre, period, etc. A pioneer work is [START_REF] Karayev | Recognizing image style[END_REF], which showed that a pre-trained CNN is able to predict the painting school of an artwork. Beyond the quantitative results, [START_REF] Karayev | Recognizing image style[END_REF] also observed that the predicted style of a painting is highly correlated with the content of the painting. [START_REF] Van Noord | Toward discovery of the artist's style: Learning to recognize artists by their artworks[END_REF] focused on the artist attribution task, which aimed at attributing an unseen artwork to the artist who created it. [START_REF] Van Noord | Toward discovery of the artist's style: Learning to recognize artists by their artworks[END_REF] trained on a large collection of paintings using AlexNet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]. Interestingly, for paintings with multiple authorship, it is possible to distinguish areas created by different artists via visualizing the importance of regions for the predictions. [START_REF] Saleh | Large-scale classification of fine-art paintings: Learning the right metric on the right feature[END_REF] investigated different features (classical and CNN features) and learned to predict a painting's style, genre, and artist. [START_REF] Tan | Ceci n'est pas une pipe: A deep convolutional network for fine-art paintings classification[END_REF] aimed at solving the same tasks, and considered training on each task individually. They observed that all the tasks can benefit from CNN models pre-trained on ImageNet [START_REF] Deng | Imagenet: A largescale hierarchical image database[END_REF]. [START_REF] Saleh | Toward automated discovery of artistic influence[END_REF] trained a style classification model and obtained the most appropriate features to classifier styles by empirically validated on artwork datasets for the style classification. [START_REF] Chen | Recognizing the style of visual arts via adaptive cross-layer correlation[END_REF] showed that combining features from both lower and higher layers improved the performance of style classification. OmniArt [START_REF] Strezoski | Omniart: multi-task deep learning for artistic data analysis[END_REF] proposed to solve multiple attributes predictions directly through a multi-output CNN model. The overall training is carried out by minimizing an aggregated loss obtained as a weighted combination of the separate losses.

Object detection in artworks. Several works aim at finding out when a specific object first appeared in a painting or how the representation of an object evolved over time. A pioneering work is [START_REF] Crowley | In search of art[END_REF], which proposed a system that retrieves training samples given an input query by crawling Google Images onthe-fly. These are then used to learn a classifier. The final output of the classifier is a ranked list of paintings containing the queried object. The approach has been improved by moving from image-level classifiers to object detection systems [START_REF] Crowley | The art of detection[END_REF]. [START_REF] Yin | Object recognition in art drawings: Transfer of a neural network[END_REF] used the same Brueghel data (bru; [START_REF] Honig | Jan Brueghel and the Senses of Scale[END_REF] as us and annotate it to train detectors for five object categories (carts, cows, windmills, rowboats, and sailboats). [START_REF] Westlake | Detecting people in artwork with cnns[END_REF] focused on detecting people in artworks, they showed that deep features trained on natural images lead to severe overfitting issue and fine-tuning on artwork dataset achieves clearly better generalization. Similarly, [START_REF] Ginosar | Detecting people in cubist art[END_REF] aimed at detecting people but with a focus on Cubist paintings and empirically found that the deformable partbased models (DPM) outperforms other classical detectors such as RCNN [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]. [START_REF] Gonthier | Weakly supervised object detection in artworks[END_REF] proposed a weakly supervised approach that can learn to detect objects based only on image-level annotations. [START_REF] Crowley | Of gods and goats: Weakly supervised learning of figurative art[END_REF] started from a large dataset of images of vases with text descriptions and aimed at detecting gods and animals. It developed a weakly supervised learning approach to solve the correspondence problem between the descriptions and unknown image regions.

Different from detecting objects of pre-defined categories, one-shot detection aims at detecting visual details that are similar to given queries details.The task is interesting for art historians, as it is possible to track the circulation of these visual patterns over long spatial and temporal migrations, as they are progressively copied by several generations of painters. [START_REF] Seguin | Tracking transmission of details in paintings[END_REF] detected duplicated art details with using CNN features and sliding window proposals. Beyond matching 2D art details, [START_REF] Aubry | Painting-to-3d model alignment via discriminative visual elements[END_REF] showed that it is possible to align non-photographic depictions to their 3D model. More precisely, [START_REF] Aubry | Painting-to-3d model alignment via discriminative visual elements[END_REF] proposed to learn a set of visual elements that match in 2D depictions of the scene despite large variations in rendering style (e.g. watercolor, sketch, historical photograph) and structural changes (e.g. missing scene parts, large occluders) of the scene. The proposed visual elements allowed automatically finding an approximate viewpoint of paintings with respect to a 3D model of the site.

Creating art. On the synthesis side, promising results have been obtained for transferring artistic style to a photograph. [START_REF] Gatys | Texture synthesis using convolutional neural networks[END_REF] found that optimizing Gram matrix can be used to generate texture. Based on this idea, [START_REF] Gatys | Image style transfer using convolutional neural networks[END_REF] first explored transfer the style of one image (style image) to another image(content image). The output stylized image is obtained through optimizing two distances: features between the generated image and the content image and the Gram matrix between the generated image and the style image. However, as the stylized image is obtained by iterative optimization until it matches the desired statistics, t [START_REF] Gatys | Image style transfer using convolutional neural networks[END_REF] is computationally inefficient. To address the issue, [START_REF] Johnson | Perceptual losses for real-time style transfer and super-resolution[END_REF] proposed to learn an image transformation network to transform input images into output images through a perceptual loss, which is similar to [START_REF] Gatys | Image style transfer using convolutional neural networks[END_REF]. Beyond the task of style transfer, the proposed method is shown to be effective on single-image super-resolution. Instead of optimizing the Gram matrix, the image translation problem can also be properly addressed using GAN [START_REF] Goodfellow | Generative adversarial nets[END_REF]. Cycle-GAN (Zhu et al., 2017) is a representative work, which leverages cycleconsistency between two domains without image-pair annotations. [START_REF] Elgammal | Can: Creative adversarial networks, generating" art" by learning about styles and deviating from style norms[END_REF] even tried to create art. [START_REF] Elgammal | Can: Creative adversarial networks, generating" art" by learning about styles and deviating from style norms[END_REF] proposed Creative Adversarial Network (CAN): a variant of a classic GAN which generated novel artworks by maximizing the deviation from established styles and minimizing the deviation from art distribution. The generated art was assessed by human evaluators, who regularly confused the generated art with human art.

Image Retrieval

Given a query image, image retrieval searches for similar images in a set of test images. In this section, we review some approaches from using handcrafted features to deep learning techniques.

Handcrafted features. Video Google [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF] consists of three steps for image retrieval: i) computing SIFT keypoints [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]; ii) building a visual vocabulary by K-means clustering with k clusters (visual words); iii) the collection of visual words are used in Term Frequency Inverse Document Frequency (TF-IDF) scoring of the relevance of an image to the query. More precisely, the image

d is represented by a k-vector V d = [t 1 , t 2 , ...t k ],
where t i is :

t i = n id n d log( N n i ) (2.1)
where n id is the number of occurrences of word i in image d, n d is the total number of words in the image d, n i is the number of images which contains word i and N is the total number of images in the whole database. The weighting is a product of two terms: the word frequency n id n d , and the inverse document frequency log( N n i ). The intuition is that the word frequency weights words occurring often in a particular document, whilst the inverse document frequency downweights words that appear often in the database.

Video Google [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF] can be improved through different directions. [START_REF] Nister | Scalable recognition with a vocabulary tree[END_REF] proposed a hierarchical TF-IDF scoring using hierarchically defined visual words that form a vocabulary tree, which allowed the use of a larger vocabulary and showed a significant improvement of retrieval. [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] improved the efficiency by two aspects: i) it proposed to replace the direct nearest neighbor computation in K-means by an approximated K-means using kd-trees; ii) it showed that a re-ranking stage using spatial verification can efficiently improve the performance. [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] proposed to aggregate local descriptors through a Vector of Locally Aggregated Descriptors (VLAD), which can be seen as a simplification of the Fisher kernel [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]. The idea of the VLAD descriptor is to accumulate, for each visual word µ i , the differences x j -µ i of the vectors x j assigned to µ i . This characterizes the distribution of the vectors with respect to the center. The pseudo-code to compute VLAD is shown in Algo. 1 [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF] showed that three techniques can largely improve the retrieval performance: i) RootSIFT instead of SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]; ii) Reranking with discriminative query expansion; iii) Database-side feature augmentation.

Algorithm 1: Computation of the VLAD [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF]

descriptor

Data: A set of descriptors {x 1 , ... x T } extracted from an image. The set {µ 1 ,... µ K } of centroids is learned on a training set using K-means. Both x i and µ i are d-dimenstional vectors.

Result: VLAD descriptor V =[v 1 , ...v K ],
where v i is a d-dimension vector. Initialized v i with 0 for t = 1, ..., T do i = arg min ||x t -µ j ||; [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF] Deep learning based approaches. In the deep era, approaches focus on learning a good global representation of images to map similar samples closer to each other against dissimilar ones.

v i := v i + x t -µ i end / * Power normalization * / for u = 1, ..., Kd do V u := sign(V u )|V u | α end / * L 2 normalization * / V := V ||V || 2 Figure 2.1: Proposed siamese network in
( [START_REF] Tolias | Particular object retrieval with integral maxpooling of cnn activations[END_REF] employed a pre-trained CNN network and extracted Regional Maximum Activation of Convolutions (R-MAC) descriptors for image retrieval. The R-MAC was an aggregation of max-pooled features of different regions at different scales. Even without any training, the R-MAC was shown to be effective on different image retrieval benchmarks.

One challenge in landmark retrieval is the lack of training set. A landmark dataset was proposed by [START_REF] Babenko | Neural codes for image retrieval[END_REF], which is a large-scale image dataset that contains approximately 214k images of 672 famous landmark sites. The images were collected through textual queries in an image search engine without thorough verification. Based on this dataset, [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF] obtained a relatively clean dataset by matching keypoints, spatial verification, and some post-processing within the images of each landmark class. In addition, [START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF]) also proposed to learn a siamese network based on standard triplet loss, which can be illustrated in Fig. 2.1. [START_REF] Radenović | Fine-tuning cnn image retrieval with no human annotation[END_REF] leverages a structure-from-motion (SfM) pipeline [START_REF] Schonberger | From single image query to detailed 3d reconstruction[END_REF] to clean the dataset. [START_REF] Radenović | Fine-tuning cnn image retrieval with no human annotation[END_REF]) also proposed Generalized-mean pooling (GeM) to compute image-level descriptor. Let X k be the set of W × H activations for feature map k ∈ {1...K}, where K is the total number of channels. The descriptor f (g) after GeM is defined as:

f (g) = [f (g) 1 , f (g) 2 , ...f (g) K ], f (g) k = ( 1 |X k | x∈X k x p k ) 1 p k (2.2)
where p k is the pooling parameter, which can be manually set or learned since this operation is differentiable and can be part of the back-propagation. From a pretrained network, [START_REF] Radenović | Fine-tuning cnn image retrieval with no human annotation[END_REF] conducted fine-tuning using a contrastive loss. The full pipeline is illustrated in 2.2. (Revaud et al., 2019a) investigated a new type of ranking loss that directly optimize mAP. (Revaud et al., 2019a) leverages a histogram binning approximation, the AP can be differentiated and thus employed to end-to-end learning.

Beyond learning global pooled descriptors, NetVLAD [START_REF] Arandjelovic | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] proposed a new generalized VLAD layer inspired by the classical VLAD [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] descriptor. The key insight is to replace the hard assignment in the clustering with a learnable soft assignment. The descriptor is defined as follows:

V j,k = N i=1 exp(w T k x i + b k ) k exp(w T k x i + b k ) (x i (j) -µ k (j)) (2.3)
where {w k }, {b k } and {µ k } are learnable parameters. NetVLAD [START_REF] Arandjelovic | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] was trained with weak supervision, e.g. GPS labels, and validated on place recognition benchmarks.

To mitigate the noise with weak GPS labels, NetVLAD [START_REF] Arandjelovic | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF]) only utilized the easiest top-1 image of the query for training, [START_REF] Ge | Self-supervising fine-grained region similarities for large-scale image localization[END_REF] proposed to improve the performance by exploring hard training samples. Recently, Patch-NetVLAD [START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] improved the performance of NetVLAD [START_REF] Arandjelovic | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] through multi-scale local patches matching and geometric verification.

Object Discovery and Co-segmentation

There are a number of approaches aiming at discovering, localizing, and segmenting objects from unlabelled images. Many methods [START_REF] Tang | Co-localization in real-world images[END_REF][START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF][START_REF] Vo | Unsupervised image matching and object discovery as optimization[END_REF][START_REF] Vo | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF] use bounding box proposals and formulate the object discovery as an optimization problem. This relies on the quality of proposals that are typically not adapted for non-photorealistic data, such as artworks.

Recently, LOST [START_REF] Siméoni | Localizing objects with self-supervised transformers and no labels[END_REF] showed promising performance on object discovery using self-supervised transformer DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF]. Their approach extracts DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] features of patches and computes the similarities of the patches. The patch with the smallest number of positive correlations with other patches is considered as the initial seed for foreground regions. LOST [START_REF] Siméoni | Localizing objects with self-supervised transformers and no labels[END_REF] extends the initial seed to a region by adding patches that have positive correlations with the initial seed. The final object proposal is obtained by extracting the connected component that contains the initial seed. Although without any learning procedures, LOST [START_REF] Siméoni | Localizing objects with self-supervised transformers and no labels[END_REF] improves the state-of-the-art by a large margin.

Some approaches focus on the co-segmentation task and try to predict masks of salient objects directly [START_REF] Rother | Cosegmentation of image pairs by histogram matching-incorporating a global constraint into mrfs[END_REF][START_REF] Vicente | Object cosegmentation[END_REF][START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF][START_REF] Taniai | Joint recovery of dense correspondence and cosegmentation in two images[END_REF][START_REF] Yuan | Deep-dense conditional random fields for object cosegmentation[END_REF]Li et al., 2018;[START_REF] Hsu | Co-attention cnns for unsupervised object co-segmentation[END_REF][START_REF] Li | Group-wise deep object co-segmentation with co-attention recurrent neural network[END_REF]Chen et al., 2020b).

A representative work is [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF], which works well in the presence of significant amounts of noise images (images not containing a common object), as typical for datasets collected from Internet search. The main idea behind [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF] is that common object patterns should be salient, while being sparse with respect to smooth transformations across images. To capture the salient part in an image, it employed an off-the-shelf saliency measure proposed in [START_REF] Cheng | Global contrast based salient region detection[END_REF]. Given a normalized saliency map M i for the image i, the saliency term Φ saliency at the position x = (x, y) is defined as:

Φ i saliency (x) = log(M i (x)) (2.4)
To establish reliable correspondences between pixels in foreground regions present in different images, [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF] proposed a weighed SIFT objective function. Formally, let F i→j denote the flow field from the image i to the image j, which is computed using SIFT Flow [START_REF] Liu | Sift flow: Dense correspondence across scenes and its applications[END_REF]. Using F i→j as the warping function, x is the transformed position of x, therefore x = F i→j (x). Given the binary masks b i , b j , the weighed SIFT flow objective function E f low becomes:

E f low (F i→j ; b i , b j ) = x b i (x)(b j (x)||S i (x) -S j (x)|| 1 L f eat + C 0 (1 -b j (x) L mask )+ y∈N i x α||F i→j (x) -F i→j (y)|| 2 Lr ) (2.5)
where S i are the dense SIFT descriptors of the image i, N i

x is the neighborhood of x, α weighs the smoothness term, and C 0 is a large constant. The objective function contains three parts: L f eat computes dense feature similarities between two images considering displacement; L mask pushes the estimated masks to be 1; L r regularizes the flow. The difference between this objective function and the original SIFT flow [START_REF] Liu | Sift flow: Dense correspondence across scenes and its applications[END_REF] is that it encourages matching foreground pixels between two images.

Based on the saliency and the computed correspondences, the foreground likelihood at x of the image i is :

Φ i (x) =    Φ i saliency (x) + λ match 1 |N i | j∈N i ||S i (x) -S j (x)|| , b i (x) = 1 β , b i (x) = 0
where N i is a set of similar images for the image i computed using global descriptors. β and λ match are two hyper-parameters.

Three regularization terms are considered: i) intra-image compatibility between adjacent pixels; ii) inter-image compatibility between two matched pixels; iii) color model.

For the intra-image compatibility term, it is defined as follows:

Φ i intra (x, y) = 1 y∈N i x , b i (x) =b i (y) exp(-||I i (x) -I i (y)|| 2 2 Intensity Diff. ) (2.6)
where 1 is the indicator function.

For the inter-image compatibility term, it is defined as follows:

Φ i,j inter (x, x) = 1 b i (x) =b j (x) exp(-||S i (x) -S j (x)|| 1 Feature Diff. ) (2.7)
where x is the corresponded pixel of x in the image j.

For the color model, once the masks are obtained, the color histograms of the background and foreground regions of the image i can be estimated, denoted h 0 i and h 0 j . the term considering the color model is :

Φ i color (x) = -log h b i (x) i (x) (2.8) Denote B = {b i }, F = {F i→j }, H = {h 0 i , h 1 i }, the final cost function is: E total (B; F, H) = N i=1 x (Φ i (x) + λ color Φ i color (x) + λ intra y Φ i intra (x, y) + λ inter j∈Ni Φ i,j inter (x, x)) (2.9)
where N i is a set of similar images for the image i. λ color , λ intra and λ inter are three hyper-parameters. The algorithm alternates between optimizing the correspondences F (Eqn. 2.5), and the binary masks B (Eqn. 2.9). Some similar objective functions are also employed in the deep era for object (Li et al., 2018). MC is a mutual correlation layer, which is similar to Flownet [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF].

discovery. In (Chen et al., 2020b), the training losses contain five components:

L = L match + λ cycle L cycle + λ triplet L triplet + λ contrast L contrast + λ mask L mask (2.10)
where L match is the foreground-guided matching loss which minimizes the distance between corresponding features based on the estimated geometric transformation. Both the forward-backward consistency loss L cycle and transitivity consistency loss L triplet regularize the network training by enforcing the predicted geometric transformations to be consistent across a pair of images (L cycle ) and three images (L triplet ).

L contrast optimizes the masks such that they are with higher inter-image foreground similarity and large intra-image figure-ground separation. L mask penalizes the inconsistency of the predicted object masks of an input image pair and the estimated geometric transformations between that pair.

The solution of co-segmentation becomes much simpler if training data and annotations are available. (Li et al., 2018) proposed a pure CNN framework for object co-segmentation, which is illustrated in Fig. 2.3. MC is a mutual correlation layer, which is similar to Flownet [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF][START_REF] Ilg | Flownet 2.0: Evolution of optical flow estimation with deep networks[END_REF]. In detail, the mutual correlation layer performs a pixel-wise comparison between two feature maps f A and f B . Given a point (i, j) and a point (m, n) inside a patch around (i, j), the correlation between feature vectors f A (i, j) and f B (m, n) is defined as:

C AB (i, j, k) = f A (i, j)f B (m, n) (2.11)
where k = (n -j)D + (m -i) and D × D is patch size. Since the common objects can locate at any place on the two input images, the patch size is set to

D = 2 max(w-1, h-1)+1
, where w and h are the width and height of the feature maps f A and f B . The object co-segmentation is thus a binary image labeling problem and can be optimized using the standard cross-entropy loss function to train the network.

To train the network, (Li et al., 2018) adapted the PASCAL dataset [START_REF] Everingham | The pascal visual object classes (voc) challenge[END_REF] and created approximately 161K, 42K, 40K pairs for training, validation, and testing. Another research direction is to discover discriminative patches in a dataset without using annotations. The desired patches need to satisfy two requirements: i) they need to occur frequently enough in the dataset; ii) they need to be different enough from the rest of the dataset. [START_REF] Singh | Unsupervised discovery of mid-level discriminative patches[END_REF] proposed to solve the problem with an iterative algorithm.

For initialization, the input to the algorithm is a "discovery dataset" D as well as a much larger "natural world dataset" N . Both D and N are divided into two equal, non-overlapping subsets (D 1 , N 1 and D 2 , N 2 ). S patches are randomly sampled from D 1 at multiple scales, disallowing highly overlapping patches or patches with no gradient energy (e.g. sky patches). [START_REF] Singh | Unsupervised discovery of mid-level discriminative patches[END_REF] proposed to run standard kmeans clustering in HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] space of the patches with k quite high to have more pure clusters. Clusters with less than 3 patches are removed.

For the iterative algorithm, given an initial set of clusters, a linear SVM classifier is trained for each cluster, using patches within the cluster as positive examples and all patches of N 1 as negative examples. The trained discriminative classifiers are then run on the held-out validation set D 2 , and new clusters are formed from the top m firings of each detector. The new clusters are then used to train linear SVMs for the next iteration. The algorithm will be stopped if the clusters are unchanged. The final output clusters can be ordered according to their purity and discriminativeness.

As follow-up work, [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF] developed an extension of the classic mean-shift algorithm to density ratio estimation, showing that the resulting algorithm could be used for element discovery. [START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF]) also proposed the Purity-Coverage plot as a principled way of experimentally analyzing and evaluating different visual discovery approaches.

Dense Image Alignment

One classical approach is Lucas-Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] is one classical approach that estimates a dense flow field between a pair of images under a brightness constancy assumption. The main limitation is that it tends to work only for small displacements. This has been partially addressed with hierarchical flow estimation [START_REF] Szeliski | Image alignment and stitching: A tutorial[END_REF], as well as using local features in addition to pixels to increase robustness [START_REF] Brox | Large displacement optical flow[END_REF][START_REF] Revaud | Epicflow: Edge-preserving interpolation of correspondences for optical flow[END_REF][START_REF] Bailer | Flow fields: Dense correspondence fields for highly accurate large displacement optical flow estimation[END_REF][START_REF] Hu | Efficient coarse-to-fine patchmatch for large displacement optical flow[END_REF]. However, all such methods are still limited to aligning very similar images, where the brightness constancy assumption mostly holds.

SIFT-Flow [START_REF] Liu | Sift flow: Dense correspondence across scenes and its applications[END_REF] was an early method that aimed at expanding optical flow-style approaches for matching pairs of images across physically distinct, and visually different scenes. SIFT-Flow [START_REF] Liu | Sift flow: Dense correspondence across scenes and its applications[END_REF] proposed to extend SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] descriptors to pixel-wise SIFT features S. The energy function for SIFT flow is defined as:

E SIF T -F low (F 1→2 ) = x min(||S 1 (x) -S 2 (F 1→2 • x)|| 1 , t) Feat. Diff + η||F 1→2 • x -x|| 1 Small Displ. ) + y∈N 1 x min(α||F 1→2 (x) u -F 1→2 (y) u || 1 , d) Smoothness along u ) + y∈N 1 x min(α||F i→j (x) v -F 1→2 (y) v || 1 , d) Smoothness along v ) (2.12)
where F 1→2 is the flow field from image 1 to image 2, which can be also used as the warping function. x is the pixel position at (x, y). u and v correspond to the horizontal and vertical direction of the flow. N 1

x denotes the neighborhood of x in the image 1. t, η, α, and d are hyper-parameters. The Feat. Diff. term in Eqn. 2.12 constrains the SIFT descriptors to be matched along with the flow vector. The Small Displ. term constrains the flow vectors to be as small as possible. The smoothness terms constrain the flow vectors of adjacent pixels to be similar.

SIFT-Flow [START_REF] Liu | Sift flow: Dense correspondence across scenes and its applications[END_REF] was later generalized to joint image set alignment using cycle consistency in (Zhou et al., 2015).

In the deep era, flows can be learned in a completely supervised way using synthetic data. Representative works are Flownet1 [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF] and Flownet2 [START_REF] Ilg | Flownet 2.0: Evolution of optical flow estimation with deep networks[END_REF]. In Flownet1 [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF], it proposed two architectures to learn optical flow, which are illustrated in Fig. 2.4. A simple choice is to stack the two input images together and feed them through a CNN to extract the motion information. This is referred as FlowNetSimple in Fig. 2.4 (top). Another choice is to process the correlation between features, which is the architecture FlowNetCorr in Fig. 2.4 (bottom). Formally, denote f 1 and f 2 as feature maps in image 1 and image 2. The correlation of two features at x 1 in the first map and x 2 in the second map is then defined as:

c(x 1 , x 2 ) = o∈[-k,k]×[-k,k] f 1 (x 1 + o)f 2 (x 1 + o) (2.13)
where k defines the kernel size to compare features.

To train the networks, [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF] created a simple synthetic dataset, named Flying Chairs, by applying affine transformations to images collected from Flickr and a publicly available rendered set of 3D chair models.

Flownet2 [START_REF] Ilg | Flownet 2.0: Evolution of optical flow estimation with deep networks[END_REF] improved over Flownet1 [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF] via three points: i) a learning schedule consisting of multiple datasets; ii) a warping operation that allows stacking multiple networks; iii) a special training dataset and a specialized network for small, subpixel motion and real-world data. Generating synthetic data is also a key component to learning dense flow field between images with very different appearances. A pioneer work is [START_REF] Rocco | Convolutional neural network architecture for geometric matching[END_REF], which generates image pairs with randomly sampled affine and thin-plate spline (TPS) transformations. The proposed architecture is illustrated in Fig. 2.5. The network first estimates an affine transformation then a more complex TPS transformation with the warped images. Similar to Flownet1 [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF], the motion prediction is obtained through process correlations between features, which is the matching layer in Fig. 2.5. [START_REF] Rocco | Convolutional neural network architecture for geometric matching[END_REF] proposed measuring loss on an imaginary grid of points which is being deformed by the transformation. More precisely, a grid of points G in image A is transformed using the ground truth and neural network estimated transformations T θ GT and T θ with parameters θ GT and θ, respectively, and measure the discrepancy between the two transformed grids:

L( θ, θ GT ) = ||T θ GT • G -T θ • G|| 2 2 (2.14)
Similarly, DGC-Net [START_REF] Melekhov | Dgc-net: Dense geometric correspondence network[END_REF] learned from images pairs generated with synthetic transformation. DGC-Net adapted a coarse-to-fine strategy and included a feature correlation layer in a U-Net [START_REF] Ronneberger | U-net: Convolutional networks for biomedical image segmentation[END_REF] architecture to progressively improve flow resolution. The idea is illustrated in Fig. 2.6. Note that the largest resolution of the flow field predicted by DGC-Net is 240 × 240.

The follow-up work [START_REF] Laskar | Geometric image correspondence verification by dense pixel matching[END_REF] improved DGC-Net by constraining the matching layer to be locally and globally consistent and leveraging a better universal decoder.

Local and global correlation layers have also shown to be effective in GLU-Net [START_REF] Prune | GLU-Net: Global-local universal network for dense flow and correspondences[END_REF]. The local correlation c l between the target F l t ∈ R H l ×W l ×d l and source F l s ∈ R H l ×W l ×d l is defined as:

c l (x, d) = F l t (x) T F l s (x + d), ||d|| ∞ ≤ R (2.15)
where x is a coordinate in the target feature map and d is the displacement from this location. The displacement is constrained to ||d|| ∞ ≤ R, i.e. the maximum motion in any direction is R. The resulting 3D correlation volume c l thus has a dimensionality of H l × W l × (2R + 1) 2 .

A global correlation layer evaluates the pairwise similarities between all locations in the target and source feature maps. The resulting 3D correlation volume C l thus has a dimensionality of

H l × W l × H l × W l .
The Global-Local architecture is present in Fig. 2.7. Note that the input images have two resolutions and the global correlation is only computed for low-resolution pairs. (Rocco et al., 2018a) fine-tuned the model from [START_REF] Rocco | Convolutional neural network architecture for geometric matching[END_REF] on real-world datasets with weak supervision, namely, only matched (positive) pairs are provided and no annotations of correspondences are available. The key insight is to maximize the sum of soft-inlier for positive pairs. (Rocco et al., 2018b). (Rocco et al., 2018b) introduced the idea of using 4D convolutions on the feature correlations to learn to filter neighbor consensus. The idea is illustrated in Fig. (?). A fully convolutional neural network is used to extract dense image descriptors f A and f B for images A and B, respectively. All pairs of individual feature matches f A i,j and f B k,l are represented in the 4D space of matches (i, j, k, l) (here shown as a 3D perspective for illustration), and their matching scores stored in the 4D correlation tensor c. These matches are further processed by 4D convolutions to produce the final set of output correspondences.

Chapter 3 Learning Features for Artworks Analysis

Discovering near duplicate patterns in large collections of artwork is harder than standard instance mining due to differences in the artistic media (oil, pastel, drawing, etc), and imperfections inherent in the copying process. The key technical insight is to adapt a standard deep feature to this task by fine-tuning it on the the specific art collection using self-supervised learning. More specifically, spatial consistency between neighbouring feature matches is used as supervisory fine-tuning signal. The adapted feature leads to more accurate style-invariant matching, and can be used with a standard discovery approach, based on geometric verification, to identify duplicate patterns in the dataset. The approach is evaluated on several different datasets and shows surprisingly good qualitative discovery results. For quantitative evaluation of the method, we annotated 273 near duplicate details in a dataset of 1587 artworks attributed to Jan Brueghel and his workshop. Beyond artwork, we also demonstrate improvement on localization on the Oxford5K photo dataset as well as on historical photograph localization on the Large Time Lags Location (LTLL) dataset. Code and data are available at http://imagine.enpc.fr/~shenx/ArtMiner

Introduction

Visiting a world-class art museum might leave one with an impression that each painting is absolutely unique and unlike any other. In reality, things are more complicated. While working on a painting, an artist would typically create a number of preliminary sketches and studies to experiment with various aspects of the composition. Many of these studies also find their way into (usually more provincial) museums. Some artists enjoy returning time and again to the same subject matter (e.g. Claude Monet and his series of 25 paintings of the same haystacks). Moreover, during the Renaissance, it was not uncommon for an artist (or an apprentice in his workshop) to reuse the same visual elements or motifs (an angel, a cart, a windmill, etc) in multiple paintings, with little or no variation. For example, Flemish painter Jan Brueghel is believed to have created many paintings that were imitations, pastiches, or reworkings of his own works, as well as these of his father, Pieter Breughel the Elder [START_REF] Honig | Jan Brueghel and the Senses of Scale[END_REF]. Art historians are keenly interested in mapping out such visual connections between artworks to discover influences, find provenance, and even establish authorship. Currently, this is being done entirely by hand, with researchers spending months or even years in museum archives hoping to discover common visual patterns.

This chapter presents an approach for automatically discovering repeated visual patterns in art collections, as shown on Fig. 3.1. We propose to learn a deep visual feature able to find correspondences between near-duplicate visual elements across different artworks. This task is quite challenging, requiring a feature that is both highly discriminative (i.e. tuned to find copies of the same object instance rather then samples of an object category), but also invariant to changes in color, style, artistic media, geometric deformation, etc. Manually collecting and labelling a large enough artwork dataset containing enough variability requires enormous effort by professional art historians, which is exactly what we are trying to avoid. Therefore, we propose a method which learns in a self-supervised way, adapting a deep feature to a given art collection without any human labelling. This is done by leveraging neighbourhood spatial consistency across matches as free supervisory signal.

Using our trained feature, we demonstrate that a simple voting and regression procedure, in line with classic verification step of instance recognition [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], lets us discover visual patterns that are repeated across artworks within the dataset. We demonstrate our visual pattern discovery approach on several collections of artwork, including a new annotated dataset of 1587 works attributed to the Brueghel family. To further evaluate the generality of our method, we have also evaluated it on a set of historical and modern architecture photographs, resulting in state-of-the-art localization task performance on the Large Time Gap Location dataset [START_REF] Fernando | Location recognition over large time lags[END_REF].

Our main contributions are: 1) a self-supervised approach to learn a feature for matching artistic visual content across wide range of styles, media, etc; 2) the introduction of a large new dataset for evaluating visual correspondence matching; 3) an approach to discover automatically repeated elements in artwork collections.

Related Work

Computer vision and art.

There is a long standing and fruitful collaboration between computer vision and art. On the synthesis side, promising results have been obtained for transferring artistic style to a photograph [START_REF] Hertzmann | Image analogies[END_REF][START_REF] Gatys | Image style transfer using convolutional neural networks[END_REF]Zhu et al., 2017), or even trying to create art [START_REF] Elgammal | Can: Creative adversarial networks, generating" art" by learning about styles and deviating from style norms[END_REF][START_REF] Hertzmann | Can computers create art? In Arts[END_REF]. On the analysis side, there are several efforts on collection and annotation of large-scale art datasets [START_REF] Karayev | Recognizing image style[END_REF][START_REF] Mensink | The rijksmuseum challenge: Museum-centered visual recognition[END_REF][START_REF] Picard | Challenges in content-based image indexing of cultural heritage collections[END_REF][START_REF] Wilber | Bam! the behance artistic media dataset for recognition beyond photography[END_REF][START_REF] Strezoski | Omniart: multi-task deep learning for artistic data analysis[END_REF][START_REF] Mao | Deepart: Learning joint representations of visual arts[END_REF], and using them for genre and authorship classification [START_REF] Karayev | Recognizing image style[END_REF][START_REF] Tan | Ceci n'est pas une pipe: A deep convolutional network for fine-art paintings classification[END_REF][START_REF] Strezoski | Omniart: multi-task deep learning for artistic data analysis[END_REF]. Others focus on applying and generalizing visual correspondence and object detection methods to paintings using both classical [START_REF] Shrivastava | Data-driven visual similarity for cross-domain image matching[END_REF][START_REF] Crowley | Of gods and goats: Weakly supervised learning of figurative art[END_REF][START_REF] Aubry | Painting-to-3d model alignment via discriminative visual elements[END_REF][START_REF] Ginosar | Detecting people in cubist art[END_REF][START_REF] Ginosar | The burgeoning computerart symbiosis[END_REF], as well as deep [START_REF] Crowley | Face painting: querying art with photos[END_REF][START_REF] Crowley | The art of detection[END_REF][START_REF] Westlake | Detecting people in artwork with cnns[END_REF][START_REF] Gonthier | Weakly supervised object detection in artworks[END_REF]. Most closely related to us is work of Yin et al. [START_REF] Yin | Object recognition in art drawings: Transfer of a neural network[END_REF], which used the same Brueghel data (bru), annotating it to train detectors for five object categories (carts, cows, windmills, rowboats and sailbaots).

Our goal, however, is to go further and focus on the computational analysis of relationships between individual artworks. Seguin et al. [START_REF] Seguin | Visual link retrieval in a database of paintings[END_REF][START_REF] Seguin | Tracking transmission of details in paintings[END_REF] propose to find visual relationships in collections of paintings. However, while they use off-the-shelf CNNs trained in a supervised manner, we focus on the design of a new self-supervised feature learning specifically trained for the task. This allows us to focus on near-exact reproduction of detail, rather than a more generic visual similarity, which is what most art historians are actually interested in regards to specific corpora, such as the works of Brueghel family [START_REF] Honig | Jan Brueghel and the Senses of Scale[END_REF].

Spatial consistency as supervisory signal. Spatial consistency is a widely used signal in many computer vision tasks from geometry to retrieval. The classic work of Sivic et al. [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF] performs instance retrieval based on the extraction of spatially consistent local feature matches. This direction has been further developed with specially adapted features for place recognition across large visual changes [START_REF] Fernando | Location recognition over large time lags[END_REF][START_REF] Hauagge | Image matching using local symmetry features[END_REF][START_REF] Verdie | Tilde: A temporally invariant learned detector[END_REF][START_REF] Aubry | Painting-to-3d model alignment via discriminative visual elements[END_REF]. Beyond instances, this idea has been extended to discovering object categories [START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF] and their segmentations [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF]. Our discovery of repeated patterns through correspondence consistency is reminiscent of the line of work on mid-level visual element discovery [START_REF] Singh | Unsupervised discovery of mid-level discriminative patches[END_REF][START_REF] Doersch | Mid-level visual element discovery as discriminative mode seeking[END_REF][START_REF] Doersch | Context as supervisory signal: Discovering objects with predictable context[END_REF]. These idea have been used in the context of temporal and spatial image collection analysis, to discover the elements characteristic of a specific location [START_REF] Doersch | What makes paris look like paris[END_REF], or the evolution of these elements over time (Jae [START_REF] Lee | Style-aware mid-level representation for discovering visual connections in space and time[END_REF].

Spatial consistency has also been used to learn deep visual features for object category in a self-supervised way, either by predicting the spatial configuration of patches [START_REF] Doersch | Unsupervised visual representation learning by context prediction[END_REF] or predicting the patch given its context [START_REF] Pathak | Context encoders: Feature learning by inpainting[END_REF]. In a similar spirit, Rocco et al. (Rocco et al., 2018b) recently demonstrated how to learn visual representations through geometric consistency to predict object-category-level correspondences between images. We, on the other hand, aim at learning features for matching only stylistically different versions of the same instance.

Dataset-specific Feature Learning

This section describes our strategy for adapting deep features to the task of matching artworks across styles in a specific dataset. Starting with a standard ImageNet pretrained deep features, our idea is to extract hard-positive matching regions form the dataset that we then use in a metric learning approach to improve the features. Our two key hypothesis are that: (i) our dataset includes large parts of images that are copied from each other but are depicted with different styles, and (ii) the initial feature descriptor is good enough to extract some positive matches. Our training thus alternates between two steps that we described bellow: (1) mining for hardpositive training samples in the dataset based on the current features using spatial consistency, and (2) updating the features by performing a single gradient step on the selected samples.

Mining for positive feature pairs

For our approach to work, it is crucial to select positive matching examples that are both accurate and difficult. Indeed, if the features are trained with false matches, training will quickly diverge, and if the matches are too easy, no progress will be made.

To find these hard-positive matching features, we rely on the procedure visualized in Fig. 3.2.

Candidate sampling. Proposal regions are randomly sampled from each image in the dataset to be used as query features. These are matched densely at every scale to all the images in the dataset using cosine similarity in feature space. This can be done efficiently and in parallel for many queries using a normalization and a convolution layer, with the weights of the convolution defined by the query features. For each query we select one of its top K matches as candidate correspondences (Fig. 3.2a). These candidates contain a high proportion of bad matches, since most of the queries are likely not repeated K times in the dataset and since our feature is imperfect.

Candidate verification. To verify the quality of candidate matches given by the previous step, we rely on special consistency: a match will be considered valid if its neighbours agree with it. More precisely, let's assume we have a candidate match between features from the proposal region p A in image A and a corresponding region p B in image B, visualized in red in Fig. 3.2b. We define a verification region around p A , visualized in blue. Every feature in this region is individually matched in image B, and votes for the candidate match if it matched consistently with p B . Summing the votes of all the features in the verification region allows us to rank the candidate matches. A fixed percentage of the candidates are then considered verified. The choice of the verification region is, of course, important to the success of this verification step.

The key aspect is that the features in the verification region should be, as much as possible, independent of the features in the proposal region. On the other hand, having them too far apart would reduce the chances of the region being completely matched. For our experiments, we used the 10x10 feature square centred around the query region (Fig. 3.2b).

Generating hard positives. Finally, given a set of verified correspondences, we have to decide which features to use as positive training pairs. One possibility would be to directly use features in the proposal region, since they have been verified. However, since the proposal region has already been "used" once (to verify the matches), it does not bring enough independent signal to make quality hard positives. Instead, we propose to sample positives from a different positive region. We evaluated different configurations for the positive region, as visualized in Fig. 3.3 (in green). We choose to keep only 4 positive pairs per verified proposal, positioned at the corners of a square and denote the different setups as P2 to P14, the number corresponding to the size of the square. We will show in the experiments that P12 and P14 perform better than the alternatives in Sec 3.5.3. The features from the positive regions (Fig. 3.2b in green) are then used as hard positives for feature fine-tuning (Fig. 3.2c).

Feature fine-tuning

After each selection of positive feature pairs, we update of our feature using a single gradient step of the following triplet metric learning loss:

L(P 1 , P 2 , {N i }) = -min(λ, s(P 1 , P 2 )) + 1 N neg Nneg i=1 max(s(P 1 , N i ), 1 -λ) (3.1)
where P 1 and P 2 are corresponding features in the positive regions, {N i } {i=1,2...Nneg} are negative samples, s is the cosine similarity metric and λ is a hyper-parameter. We select the negatives as the set of top matches to P 1 in P 2 's image. This selects hard negatives and avoids any difference in the distribution of the depiction styles in our positive and negative samples. We chose a relatively high number of negative N neg to account for the fact that some of them might in fact correspond to matching regions, for example in the case of repeated elements, or for location near the optimal match. Implementation details. In all of our experiments, we used conv4 features of the ResNet-18 [START_REF] He | Deep residual learning for image recognition[END_REF] architecture. We resized all images such that their maximum spatial dimension in the feature map was 40, leading to approximately 1k features per image at the maximum scale. For each image, we used 7 different scales, regularly sampled at two octaves with 3 scales per octave. For positive sampling, we used square queries of 2 × 2 features, K = 10 candidate matches for each query. From these candidate, the top 10% with the most votes from neighbours were considered verified. Note that these parameters might need to be adjusted depending on the diversity and size of the dataset, but we found that they performed well both for the Brueghel (bru) and LTLL [START_REF] Fernando | Location recognition over large time lags[END_REF] datasets. For training on Oxford5K [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]

Spatially Consistent Pattern Mining

In this section, we describe how our algorithm discovers repeated patterns in a dataset given style-invariant features learned in the previous section. We follow the classic geometric verification approach [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]: for all pairs of images in the dataset, we first compute features and match them between the two images, then select consistent matches, and finally find image regions that have many consistent feature matches. This allows us to build a graph between all corresponding image regions, from which we extract clusters of related images and repeated elements. In the following, we present briefly each of these steps.

Identifying region correspondences

Our discovery procedure for a pair of images is visualized in Fig. 3.4. We start by computing dense correspondences between the two images using our learned feature. These will be quite noisy. We first use Hough voting to identify potential groups of consistent correspondences. As a first approximation, each correspondence votes for a translation and change in scale. We then extract the top 10 translation candidates, and, using a permissive threshold, focus on the correspondences in each group independently. Within each group, we use RANSAC to recover an affine transformation and the associated inliers. This allows to account for some deformation in the copy process, but also variations in the camera viewpoint with respect to the artwork.

Scoring correspondences

After deformations between image regions are identified, we score the correspondence based both on the quality of the match between the features and geometric criteria. We use the following weighted average of the feature similarity:

S(I) = 1 N i∈I e (- e 2 i 2σ 2 ) s i (3.2)
where I is the index of the inlier correspondences, e i is the error between correspondence i and the geometric model, s i the similarity of the associated descriptors and 1 N is normalization by the number of features in the source image.

Region correspondences graph

Using the score S, we can separate our dataset into clusters of connected images. These clusters are already interesting and visually appealing, especially for dataset with few repeated details. However, to avoid obtaining very large clusters when many details are repeated in overlapping sets of images, one needs to individually identify each detail region. To do that we built a graph from all the connected image pairs. The nodes are the regions that are mapped between pairs of images. Each image can contain several overlapping regions. We connect regions that are matched to each other as well as regions in the same image that overlap with an Intersection over Union (IoU) score greater than a given threshold (0.5 in our experiments). Finally, we extract the connected components in this graph. Each of them corresponds to a different detail that is repeated in all images of the group.

Experiments

In this section, we analyse and evaluate our approach. We first present the main datasets we used, including our new annotations of the Brueghel dataset (bru) specifically targeted toward the new task we propose. Second, we provide detailed results and analysis for the task of one-shot visual pattern detection. Finally, we present quantitative and qualitative results for our discovery procedure.

Datasets

Brueghel. We introduce new annotations for the Brueghel dataset (bru), that we will release together with the images we used. Indeed, to the best of our knowledge, no other annotation for the task of near duplicate detection in artwork is currently available.

The Brueghel dataset contains 1,587 artworks done in different media (e.g. oil, ink, chalk, watercolour) and on different materials (e.g. paper, panel, copper), describing a wide variety of scenes (e.g. landscape, religious, still life) This dataset is especially adapted for our task since it assembles paintings from artists related to the same workshop, who thus had many interaction with each other, and includes many copies, preparatory drawings, and borrowed details. With the help of our art history collaborators, we selected 10 of the most commonly repeated details in the dataset and annotated the visual patterns in the full dataset using the VGG Image Annotator tool [START_REF] Dutta | VGG image annotator (VIA)[END_REF]. The 10 annotated patterns can be seen in Fig. 3.5 as queries (blue boxes), and our full annotation are visible in the project page http://imagine.enpc.fr/~shenx/ArtMiner. We were careful to select diverse patterns, and for each of them to annotate only duplicates, and not full object classes. Note for example that for the horses and lion classes, we annotated separately two variants of the details (front and back facing lion, front and right facing horse). This resulted in 273 annotated instances, with a minimum of 11 and a maximum of 57 annotations per pattern.

These annotations allow us to evaluate one-shot duplicate detection results. In our evaluation, we use an IoU threshold of 0.3 for positives, because precise annotations of the bounding boxes in different environment is difficult and approximate detections would be sufficient for most applications. In practice, our detected bounding boxes, visualised in Fig. 3.5 (green boxes) often appear more consistent than the annotations. We compute the Average Precision for each query, average them per class and report class level mean Average Precision (mAP).

Large Time Lags Locations (LTLL). While our discovery algorithm targets copy detection in art, it should also be able to detect same object instances in photographs as well. We thus test our algorithm on the LTLL [START_REF] Fernando | Location recognition over large time lags[END_REF] dataset. It contains historic and modern photographs captured from 25 locations over a time interval of more than 150 years. In total the dataset contains 225 historical and 275 modern photographs of the same locations. The task proposed in LTLL is to recognize the location of an old picture using annotated modern photographs. We use our discovery procedure to find the images most similar to the query. As in the original paper [START_REF] Fernando | Location recognition over large time lags[END_REF], we report classification accuracy.

Oxford5K. We also evaluate our approach on Oxford buildings [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] dataset. The dataset contains 5062 images for 11 different landmarks. We follow the standard evaluation protocol and report retrieval mAP for the 55 queries.

DocExplore. The DocExplore dataset [START_REF] En | New public dataset for spotting patterns in medieval document images[END_REF], which is dedicated to spotting repeated patterns in manuscripts and is the closest existing dataset related to our task and provides extensive comparisons. However the repeated patterns in this dataset are rare and small, all exactly in the same style, with the same colors, and most of the data is text. We thus used it to validate our baseline one-shot detection approach, but could not use it for feature training. DocExplore contains over 1500 images with 1464 instances of 35 different details. For our experiments, we only considered the 18 largest details (the other ones corresponding to small letters).

WikiArt. To show the generality of our approach, we ran our discovery algorithm on paintings of other artists (Peter Paul Rubens, Dante Gabriel Rossetti and Canaletto) that we collected from WikiArt (wik, a,b) (respectively 387, 195 and 166 artworks).

One-shot detection

We evaluated our feature learning strategy using one-shot detection. This was performed simply by computing densely features on the dataset and computing their cosine similarity with the features corresponding to the query. The query was resized so its largest dimension in the feature map would be 8. Note that unlike standard deep detection approaches [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF][START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF], we do not use region proposals because we want to be able to match regions which do not correspond to objects. Examples results using this approach for each of the 10 details we annotated on the Brueghel dataset are shown in Fig. 3.5. It gives a sense of the difficulty of the task we target and the quality of the results we obtain. Note for example how the matches are of different styles, and how the two types of lions (top row) and the two types of horses (bottom row) are differentiated. In the following, we compare these results with baselines and analyse the differences.

Validation on DocExplore (doc). To validate that our one-shot detection approach is competitive with classical methods for finding repeated details, we ran it on the DocExplore (doc) dataset with ResNet-18 features trained on ImageNet. Our cosine-similarity based dense approach resulted in mAP of 55% on the 18 categories we considered, a clear improvement compared to the best performance of 40% obtained in [START_REF] En | New public dataset for spotting patterns in medieval document images[END_REF] with classical approaches.

Comparison and analysis on Brueghel. Here, we compare the one shot detection performance with different features using cosine similarity and the score described in Eqn.3.2. In Fig. 3.6, we present the top 6 matches from the same query using different approaches. On this example, it can be seen that while ImageNet feature only gets the matches in similar styles, our trained feature obtains duplicated horses in different styles, showing that the learned feature is more invariant to style. More- over, the matching can still be improved with the discovery score. The corresponding quantitative results are presented in Tab. 3.1 and confirm these observations. Indeed learning features improves the score by approximately 30%. The discovery procedure and score provides a small additional boost, which is a first validation of our discovery procedure. We also report results for two baselines that we re-implemented: the classical Video Google [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF] approach and deep feature learnt with Context Prediction [START_REF] Doersch | Unsupervised visual representation learning by context prediction[END_REF]. With the Video Google [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF]) baseline, we obtained only 21.53% as retrieval mAP, showing the difficulty to address our task with SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] features. Some failure examples are visualized in Fig. 3.7. For Context Prediction, we trained the network using the Brueghel dataset and the same ResNet18 architecture and ImageNet initialization as for our method. We only obtain an improvement of 0.8% compared to ImageNet feature, much lower than the 17% provided by our method. Interestingly, training our feature on the LTLL dataset also gave a boost in performance compared to the ImageNet feature, but is clearly worst than training on the Brueghel data, showing the dataset specific nature of our training.

Positive region configuration

We now focus on evaluating the different positive region settings described in Sec. 3.3.1 and Fig. 3.3. For each of them, we analyse the performance of the features on oneshot learning on the Brueghel dataset and its evolution during training. The results can be seen in Fig. 3.8. Interestingly, the performance initially always improves over ImageNet features. However, when the positive region is close to the proposal region, the performance decreases after some iterations of our training procedure, and ends up with worse performance than the initial features. But if the positive region is far enough from the query (P12 and P14), the performance improves much more and does not subsequently deteriorate. We thus use P12 for all our other experiments.

Visual pattern discovery

In this part, we focus more specifically on our discovery procedure, show qualitative results on various datasets, and evaluate quantitatively for place recognition on the LTLL dataset.

Training visualization. To visualise the influence of the feature training for our discovery task, we selected a pairs of matching images and ran discovery on them with the features at different steps of training. Fig. 3.9 visualises the results on a pair of images from the LTLL dataset. During training, larger and larger parts of the images can be matched in a consistent way, and be discovered as similar elements by our method. This shows both the efficiency of our feature training and it's relevance for our task.

Quantitative analysis on one-shot localisation. We evaluate our approach on one-shot localisation for both the LTLL and Oxford5K datasets. The results are reported in Tab. 3.2. We compare our discovery score to cosine similarity with standard max-pooled features as well as the state of the art results of [START_REF] Fernando | Location recognition over large time lags[END_REF] on LTLL and [START_REF] Radenović | Fine-tuning cnn image retrieval with no human annotation[END_REF] on Oxford5K.

On LTLL, we use the class of the nearest neighbour in modern photographs to localise the historical images. Using the discovery score provides a very important boost compared to the results of [START_REF] Fernando | Location recognition over large time lags[END_REF] and the max-pooled features. Using our fine-tuning procedure on the LTLL dataset improves again the results, demonstrating again the interest of our proposed dataset specific fine-tunning procedure.

Similarity, on the Oxford5K dataset, we obtain an important boost using the discovery score compared to cosine similarity with max-pooled features. Fine-tuning the features on Oxford5K improves the mAP by 0.7%. This improvement is less important than on LTLL, which is expected since there is no specific domain gap between queries and targets in the Oxford5K dataset. Our result on Oxford5K is also comparable to the state-of-the-art result obtained in [START_REF] Radenović | Fine-tuning cnn image retrieval with no human annotation[END_REF] which performs fine-tuning on a large image collection with ResNet101. As expected the retrieval mAP is better when fine-tuning on the Oxford dataset than on LTLL.

Qualitative analysis. We show example of our discovery results in Fig. 3.10. More results are available in our project webpage http://imagine.enpc.fr/ ~shenx/ArtMiner. Computational cost. We implement an efficient algorithm for the single shot detection by considering query features as convolutional kernels. We can thus match one query to 53 images/sec on a single GPU (Geforce GTX 1080 Ti). The discovery step is slower, since it requires matching all the features of one image to another, and takes approximately 0.2 seconds/pair of images on a single GPU. It takes about 40 minutes to query one image on Oxford5K using discovery procedure on one GPU and the discovery on the whole dataset of Brueghel took approximately 20 hours using 4 GPUs.

Limitations and Discussion

When performing discovery on different datasets, we observed some interesting failure modes visualized in Fig. 3.11. In the Brughel dataset, we discovered the identical circular frame of a set of paintings as a repeated pattern, as well as matched the faces in a set of similar but not identical paintings from portrait collections of Peter Paul Rubens.

More generally our method has several limitations. First, the time to perform discovery is important, which makes our approach impractical for applications such as localization. Moreover, the time for performing complete discovery on a dataset is quadratic in the number of images in this dataset, which limits the size of the datasets we can handle to a few thousands images. Second, our discovery procedure relies on an affine transformation model, which might not always be rich enough. Finally, our feature learning requires having access to a dataset which includes many repeated patterns and a good feature initialization.

Conclusion

We have introduced a new approach to adapt features for instance matching on a specific dataset without human supervision. We have demonstrated quantitatively the promise of our method both for one-shot cross-modal detection and for cross-modal instance discovery. Last but not least, we demonstrate diverse near duplicate discovery results in several artwork datasets, including some that have not been detected by humans.

Chapter 4

Learning Co-segmentation for Art Pattern Discovery

The goal of this chapter is to efficiently identify visually similar patterns from a pair of images, e.g. identifying an artwork detail copied between an engraving and an oil painting, or matching a night-time photograph with its daytime counterpart. Lack of training data is a key challenge for this task. We present a simple yet surprisingly effective approach to overcome this difficulty: we generate synthetic training pairs by taking object segments from COCO and copy-pasting them into another image.

We then learn to predict the repeated object masks. We find that it is crucial to predict the correspondences as an auxiliary task and to use Poisson blending and style transfer on the training pairs to generalize on real data. We analyse results with two deep architectures relevant to our joint image analysis task: a transformerbased [START_REF] Vaswani | Attention is all you need[END_REF] architecture and Sparse Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF], a recent network designed to predict coarse correspondences using 4D convolutions. We show our approach provides clear improvements for artwork details retrieval on the Brueghel dataset (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] and achieves competitive performance on two place recognition benchmarks, Tokyo247 [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] and Pitts30K [START_REF] Torii | Visual place recognition with repetitive structures[END_REF]. We then demonstrate the potential of our approach by performing object discovery on the Internet object discovery dataset [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF] and the Brueghel dataset (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]. 50

Introduction

Identifying repeated patterns lies at the very heart of the computer vision problem, and is a key component of Intelligence itself. Yet, in practice, our best methods for performing such a fundamental task often leave a lot to be desired. E.g. while we now have good methods for discovering exact pattern matches (used extensively to find copyright infringements), as well as approximate matches of salient objects (see object discovery and co-segmentation approaches in Section 2), detecting visually similar details within a larger visual context remains surprisingly difficult. Spotting the repetition of visual detail has several applications. E.g. identifying copied details in artworks allows art historians to discover influences, find provenance, and establish authorship [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]. Matching repeated details can boost performances in visual localisation for place recognition [START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF].

Reliable pair-wise image co-segmentation and correspondence identification could also enable object discovery in image collections (Chen et al., 2020b). However, identifying repeated content in image pairs remains challenging, especially in the cases where images appear very different from each other. Moreover, there is no available generic training dataset for this task.

In this chapter, we show it is possible to learn to detect repeated visual patternsjointly predicting co-segmentation and correspondences -without any human-labelled correspondences. Instead, we generate synthetic correspondence pairs via automatic data augmentation. More precisely, we use a "segment swapping" approach, where we blend object segments in a random background using Poisson blending and apply style transfer to the resulting image to obtain challenging training image pairs (Fig. 4.1a). We compare using as image segments either COCO [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] instance segmentation or unsupervised segments, which produced slightly lower but comparable results. On the generated image pairs, we have access to the ground-truth matchability masks as well as the correspondences which we use as supervisions for training a network (Fig. 4.1b). Surprisingly, we find that models trained on such a dataset generalize well to real data. We experimented with two network architectures which we adapt to predict co-segmentation and correspondences in image pairs: the recent Sparse Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF] architecture, designed for predicting image coarse correspondences, and an architecture based on Transformers [START_REF] Vaswani | Attention is all you need[END_REF] which we refer to as cross-image transformer.

We analyze the effectiveness of our data generation process, architectures and

(a) Data generation by "segment swapping". Instead of directly pasting an object from a source image on a background (3rd column), we use Poisson blending [START_REF] Pérez | Poisson image editing[END_REF] and add style transfer [START_REF] Huang | Arbitrary style transfer in real-time with adaptive instance normalization[END_REF] to the result (4th column).

(b) We train our cross-image transformer or Sparse Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF] on the generated pairs. Both networks jointly predict masks and correspondences. training strategy on two types of tasks. First, we perform retrieval tasks using the predicted pair-wise co-segementation masks and correspondences. We show clear performance improvement for artwork details retrieval on the Brueghel [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] dataset and results comparable to state of the art for visual localization on two challenging place recognition benchmarks, Tokyo247 [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] and Pitts30K [START_REF] Torii | Visual place recognition with repetitive structures[END_REF]. This last result is especially impressive, since these benchmarks are very competitive, and many dedicated methods leveraging geo-referenced images or real correspondence for supervision have been proposed. On the contrary, our approach is generic and relies solely on our synthetic "segment swapping" training. We further make use of the predicted masks and correspondences to build a candidate correspondence graph and perform discovery with spectral clustering [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF][START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF]. We demonstrate results on par with state-of-the-art on the standard co-segmentation Internet [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF] dataset and show qualitative results on the challenging Brueghel [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] dataset. Our full code is available at our project page https://imagine.enpc.fr/ ~shenx/SegSwap/.

Related Work

Learning correspondences between different images. SIFT-Flow [START_REF] Liu | Sift flow: Dense correspondence across scenes and its applications[END_REF] was an early method that aligns visually distinct scenes by incorporating visual features, such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], into optical flow style approaches. More recently, many deep learning based approaches have been developed to predict correspondences from correlations of input features [START_REF] Rocco | Convolutional neural network architecture for geometric matching[END_REF][START_REF] Melekhov | Dgc-net: Dense geometric correspondence network[END_REF][START_REF] Prune | GLU-Net: Global-local universal network for dense flow and correspondences[END_REF]Shen et al., 2020a;Truong et al., 2021b,a). Of particular interest, architectures based on attention mechanisms and Transformers [START_REF] Vaswani | Attention is all you need[END_REF] have been introduced to predict image correspondences. SuperGlue [START_REF] Sarlin | Superglue: Learning feature matching with graph neural networks[END_REF] is an attention-based graph neural network for key-point matching. Closer to this chapter, COTR [START_REF] Jiang | Cotr: Correspondence transformer for matching across images[END_REF] is an sequence-to-sequence transformer architecture that takes an image and 2D coordinates of a query points as inputs to predict correspondences. Finally, LoFTR [START_REF] Sun | Loftr: Detector-free local feature matching with transformers[END_REF] adopts a coarse-to-fine approach to matching with a transformer encoder. As opposed to our work, these transformer-based methods are trained on a large dataset with ground-truth poses and depth while we only train on a synthetic dataset. Additionally, our model is only composed of an encoder and outputs a mask of the common regions along with the correspondences.

Learning correspondences without annotated data. There is a large body of work that use synthetic images [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF] or images with synthetic deformations [START_REF] Rocco | Convolutional neural network architecture for geometric matching[END_REF][START_REF] Seo | Attentive semantic alignment with offset-aware correlation kernels[END_REF][START_REF] Melekhov | Dgc-net: Dense geometric correspondence network[END_REF][START_REF] Prune | GLU-Net: Global-local universal network for dense flow and correspondences[END_REF] to learn correspondences without real annotated training data. However, these approaches do not try to identify the matchable regions, which are essential to discover visual details. Some other approaches train directly on real images using proxy signals for correspondences, such as photometric or cycle consistency (Zhou et al., 2015;Wang et al., 2018b;[START_REF] Janai | Unsupervised learning of multi-frame optical flow with occlusions[END_REF]Shen et al., 2020a;Truong et al., 2021b,a). Again, they focus on the quality of the correspondences and are not designed to predict matchable regions in vastly different images. On the contrary, the core of our approach is to discover these similar regions. This makes our approach particularly suited for retrieval tasks.

Our approach is also inspired by related data augmentation techniques, specifically, the CopyPaste augmentation used by [START_REF] Ghiasi | Simple copy-paste is a strong data augmentation method for instance segmentation[END_REF] for instance segmentation and the stylised-ImageNet augmentation used in Geirhos et al. [START_REF] Geirhos | Imagenet-trained cnns are biased towards texture; increasing shape bias improves accuracy and robustness[END_REF] to increase shape bias in neural networks.

Object discovery and co-segmentation.

There is a wide variety of approaches aiming at discovering objects and their location from unlabelled images. Many methods [START_REF] Tang | Co-localization in real-world images[END_REF][START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF][START_REF] Vo | Unsupervised image matching and object discovery as optimization[END_REF][START_REF] Vo | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF] use bounding box proposals and formulate the object discovery as an optimization problem. This relies on the quality of proposals which are typically not adapted for non-photorealistic data, such as artworks. Other approaches [START_REF] Rother | Cosegmentation of image pairs by histogram matching-incorporating a global constraint into mrfs[END_REF][START_REF] Vicente | Object cosegmentation[END_REF][START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF][START_REF] Taniai | Joint recovery of dense correspondence and cosegmentation in two images[END_REF][START_REF] Yuan | Deep-dense conditional random fields for object cosegmentation[END_REF]Li et al., 2018;[START_REF] Hsu | Co-attention cnns for unsupervised object co-segmentation[END_REF][START_REF] Li | Group-wise deep object co-segmentation with co-attention recurrent neural network[END_REF]Chen et al., 2020b) focus on predicting masks of salient objects directly. Some [START_REF] Yuan | Deep-dense conditional random fields for object cosegmentation[END_REF]Li et al., 2018[START_REF] Li | Group-wise deep object co-segmentation with co-attention recurrent neural network[END_REF] require foreground masks for training, while others [START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF][START_REF] Joulin | Multi-class cosegmentation[END_REF][START_REF] Vicente | Object cosegmentation[END_REF][START_REF] Hsu | Co-attention cnns for unsupervised object co-segmentation[END_REF][START_REF] Li | Group-wise deep object co-segmentation with co-attention recurrent neural network[END_REF]Chen et al., 2020b) are designed to segment common repeated objects in a image collection. These approaches make strong assumptions about the frequency of appearance of an object, while, in many practical scenarios, common objects are rare and discovering them is about seeking a needle in a haystack (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]. Our approach is related to [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF][START_REF] Taniai | Joint recovery of dense correspondence and cosegmentation in two images[END_REF], as we both leverage dense correspondences to discover objects. As opposed to our work, Taniai et al. [START_REF] Taniai | Joint recovery of dense correspondence and cosegmentation in two images[END_REF] focuses on a single pair of images while we also show results over an entire collection of images. Rubinstein et al. [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF] makes the assumption that the common object is also the most salient in the image. This works well with images form internet queries but does not apply to artworks where the common object can be a detail in a richer scene.

Co-segmentation by Segment Swapping

We show an overview of our approach in Fig. 4.1. In Sec. 4.3.1, we introduce our "segment swapping" data generation process (Fig. 4.1a). We then present in Section 4.3.2 the two architectures we use (Fig. 4.1). We discuss our loss and training strategy in Section 4.3.3.

(2) we compute a simple saliency for each feature in the bounding box, i.e. for each Moco (Chen et al., 2020a) Conv4 feature (i,j) inside the box we use as saliency its average cosine distance with its neighbours, which is illustrated in Equ. 4.1.

Saliency(i, j) = 1 |N (i, j)| (m,n)∈N (i,j) 1 -cos(F(i, j), F(m, n)) (4.1)
where N (i, j) is the set containing neighbours of (i, j), cos denotes the cosine similarity and F(i, j) is the Conv4 feature at position (i, j). We only keep boxes which average saliency is high enough (≥ 0.5);

(3) the final mask for each box is obtained using GrabCut [START_REF] Rother | grabcut" interactive foreground extraction using iterated graph cuts[END_REF]) initialized by the saliency map.

The examples of unsupervised segments are provided in Fig. 4.2.

Architectures

Our networks take as input a source image I s and a target image I t , from which features maps F s and F t of spatial dimension W × H are extracted by a feature extraction backbone. These feature maps are then processed either by our cross-image transformer or our sparse Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF] architecture to predict both the masks of the repeated objects in the source and target images, M s ∈ [0, 1] W ×H and M t ∈ [0, 1] W ×H respectively, and the correspondences both from source to target C s→t and target to source C t→s . Both C s→t and C t→s are represented as matrices of size W × H × 2. To simplify notation, we sometime use the masks as continuous 2D functions, which in practice is done by performing bilinear interpolation.

Cross-image transformer. We built an architecture based on the classic transformer encoder [START_REF] Vaswani | Attention is all you need[END_REF] which alternates multi-headed attention and fully connected feed-forward networks (FFN) blocks. The FFN blocks contain two layers with a ReLu non-linearity. Similar to [START_REF] Sarlin | Superglue: Learning feature matching with graph neural networks[END_REF], we use two types of attention layers: one is the standard self-attention (SA) layer, the other one is a cross attention (CA) layer where the attention is only computed between features from different images. We include the same 2D positional encoding as DeTR [START_REF] Carion | Endto-end object detection with transformers[END_REF] on top of the feature map before SA. Our transformer alternates these two types of attention layers as shown in Fig. 4.1b, with a total of five attention and FFN blocks. Each attention layer has 2 heads and the dimension of the features is 256. Our last layer is followed by a sigmoid and has three outputs, that we interpret as masks and correspondences for each image. We provide an ablation study of this architecture in the project page.

Sparse Nc-Net. Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF] is designed to learn coarse correspondences under weak supervision. It takes as input the correlations between F s and F t , seen as a 4D volume of affinities A input ∈ R W ×H×W ×H , and processes them with 4D convolutions. The final 4D convolution predicts affinities A pred ∈ R W ×H×W ×H , on which softmax functions are applied in dimensions corresponding to source and target giving A s pred (i, j, k, l) = exp(A pred (i,j,k,l))

k,l exp(A pred (i,j,k,l)) and A t pred (i, j, k, l) = exp(A pred (i,j,k,l))

i,j exp(A pred (i,j,k,l)) . We use the maxima of these affinities as source and target masks, i.e., M s (i, j) = max k,l A s pred (i, j, k, l) and M t (k, l) = max i,j A t pred (i, j, k, l). Correspondences are obtained with soft-argmax:

C s (i, j) =   k,l k W A s pred (i, j, k, l), k,l l H A s pred (i, j, k, l)   C t (k, l) =   i,j i W A t pred (i, j, k, l), i,j j H A t pred (i, j, k, l)   . (4.2)
Since 4D convolutions are computational heavy, we instead use sparse 4D convolutions with the same architecture as Sparse Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF].

Loss and training

On our synthetic training data we have access to the ground truth masks M s gt and M t gt and ground truth correspondences C s→t gt and C t→s gt on the source and target images. Our loss is the sum of two symmetric terms for source and target, for simplicity we write only the source loss L s sup . It includes a cross-entropy (CE) loss on the predicted mask L mask and the transported mask L tmask , as well as a regression loss L corr on the correspondences:

L s sup = CE(M s gt , M s ) L mask + CE(M s gt , M t (C s→t )) L tmask + η 1 i,j M s gt (i, j) i,j M s gt (i, j) C s→t (i, j) -C s→t gt (i, j) Lcorr (4.3)
where i and j correspond to the feature coordinates, η is a scalar hyper-parameter, and

CE(M gt , M) = -1 W ×H i,j M gt (i, j) log(M(i, j)) + (1 -M gt (i, j)) log(1 -M(i, j)).
Note that this loss is computed both for positive pairs (source and target pairs generated by segment swapping) and negative pairs (sampled from two different pairs, without repeated objects) for which M s gt = M t gt = 0 and by convention L corr = 0.

Implementation details. We implement our approach using the Pytorch library and our full implementation is available in the project page https://imagine. enpc.fr/~shenx/SegSwap/. We use as backbone features the conv4 features of a ResNet-50 [START_REF] He | Deep residual learning for image recognition[END_REF] trained on ImageNet [START_REF] Deng | Imagenet: A largescale hierarchical image database[END_REF] with MOCO-v2 (Chen et al., 2020a). We freeze the backbone during the training, as learning backbone features leads to overfiting on the synthetic training set. For all the experiments, we optimise the loss defined in Eqn. 4.3 with η = 8 and use the Adam optimiser [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] with momentum terms β 1 = 0.5 and β 2 = 0.999.

At each iteration, we sample 5 positive and 15 negative pairs. For the transformer architecture, after training 200k iterations with learning rate 2e-4, we train with hard negative pairs and learning rate 1e-5 for 5k iterations. Hard negatives are obtained by sampling a pool of N pool = 500 images from different synthetic pairs, computing predicted masks for all the pairs of images in the pool, and keeping those with mask prediction higher than a threshold τ = 0.04 in a hard negative pair pool for K hard = 1000 iterations of training. For Sparse Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF] training 200k iterations with learning rate 2e-4 without hard negative mining leads to the best performance. The entire trainings of the transformer and Sparse Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF]) take approximately 30 hours and 15 hours respectively on a single GPU Tesla-V100-16GB. An ablation study of the architectures and more training details are provided in the project page.

Application to Image Retrieval

In this section, we show how our model can be used for retrieval tasks. We first explain how we use it to compute an image similarity score in Sec. 4.4.1. We then present experimental results in Sec. 4.4.2, including art detail retrieval on the Brueghel dataset (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] and place recognition on Pitts30k [START_REF] Torii | Visual place recognition with repetitive structures[END_REF] and Tokyo 24/7 [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF].

Table 4.1: Art detail retrieval and detection on Brueghel [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]bru). For detection, we employ ArtMiner (Brueghel [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] + cos [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]) as a post-processing and reports results with IoU > 0.3 [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] Feat. + Methods mAP Retrieval Det.(IoU > 0.3) Brueghel [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] + cos [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] 75.5 75.3 Brueghel [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] + discovery [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] 76.6 76.4 MocoV2 (Chen et al., 2020a) + cos [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] 79.0 78.7 MocoV2 (Chen et al., 2020a) + discovery [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] 80

Score between a pair of images

We propose the following score S to measure the similarity between a pair of images based on predicted correspondences and masks. S is the sum of weighted local features similarities, where our predicted correspondences are used to associate features and the weight M s joint is the product of the source and transported target mask

M s joint (i, j) = M t (C s→t (i, j))M s (i, j): S(I s , I t ) = i,j M s joint (i, j) Mask cos(F s (i, j), F t (C s→t (i, j)))
Feat. similarity (4.4)

Experiments

Qualitative results on our different datasets can be seen in Fig. 4.3. The predicted masks, shown with transparency, are able to capture repeated regions even in challenging cases, such as large difference of scale, viewpoints, lightening conditions and depiction styles. More visual results are provided in the project page https: //imagine.enpc.fr/~shenx/SegSwap/.

Art detail retrieval. We evaluate our approach on the Brueghel dataset (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] in Tab. 4.1. Our score allows us to directly retrieve images from a selected query detail. To further compare with the detection performance in Art-Miner [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF], we crop a 320 × 320 patch around the predicted regions [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] and Pitts30k [START_REF] Torii | Visual place recognition with repetitive structures[END_REF]. We follow Patch-NetVLAD [START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] and re-rank the top-100 images ranked by NetVLAD [START_REF] Arandjelovic | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF] features.

Method Supervision

Tokyo 24/7 Pitts30k-test R@1 R@5 R@10 R@1 R@5 R@10 AP-GEM (Revaud et al., 2019a;[START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] Image location 40.3 55.6 65.4 75.3 89.3 92.5 DenseVLAD [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF][START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] Image location 59.4 67.3 72.1 77.7 88.3 91.6 NetVLAD [START_REF] Arandjelovic | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF][START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] Image location 73.3 82.9 86.0 86.0 93.2 95.1 CRN (Kim et al., 2017a;[START_REF] Ge | Self-supervising fine-grained region similarities for large-scale image localization[END_REF] Image location 75.2 83.8 87.3 ---SARE [START_REF] Liu | Stochastic attraction-repulsion embedding for large scale image localization[END_REF][START_REF] Ge | Self-supervising fine-grained region similarities for large-scale image localization[END_REF] Image location 79.7 86.7 90.5 ---IBL [START_REF] Ge | Self-supervising fine-grained region similarities for large-scale image localization[END_REF] Image location 85.4 91.1 93.3 ---Re-ranking Top-100 from NetVLAD [START_REF] Arandjelovic | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF][START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] Patch-NetVLAD [START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] Image location 81.9 85.7 87.9 88.6 94.5 95.8 Patch-NetVLAD [START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] + RANSAC Image location 86.0 88.6 90.5 88.7 94.5 95.9 SuperGlue [START_REF] Sarlin | Superglue: Learning feature matching with graph neural networks[END_REF][START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] and use ArtMiner [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] as a post-processing to obtain the bounding box prediction. The correspondences are more accurate for the cross-image transformer which achieves much better results for detection. We also observe that, in this benchmark, the performances with unsupervised segments are close to the ones using COCO [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] instance annotations, which suggests that our approach does not depend on human annotations. Note that the best performance of ArtMiner is obtained with a discovery score which is expensive to compute and involves multiscale feature matching and RANSAC. Our approach is thus simpler, faster and more effective.

Place recognition. In Tab. 4.2 we compare our approach to state of the art for place recognition on the Pitts30k [START_REF] Torii | Visual place recognition with repetitive structures[END_REF] and Tokyo 24/7 [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] datasets. The descriptions of the datasets are in the project page. We follow the standard evaluation protocol [START_REF] Sattler | Image retrieval for image-based localization revisited[END_REF][START_REF] Gronat | Learning and calibrating perlocation classifiers for visual place recognition[END_REF][START_REF] Torii | Visual place recognition with repetitive structures[END_REF][START_REF] Arandjelović | Dislocation: Scalable descriptor distinctiveness for location recognition[END_REF][START_REF] Torii | 24/7 place recognition by view synthesis[END_REF][START_REF] Ge | Self-supervising fine-grained region similarities for large-scale image localization[END_REF]. The query image is correctly localized if one of the top N retrieved database images is within d = 25 meters from the ground truth TUM coordinate of the query. The recall is then reported for N = 1, 5, 10. For Tokyo 24/7, we follow [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF][START_REF] Ge | Self-supervising fine-grained region similarities for large-scale image localization[END_REF] and perform spatial non-maximal suppression on ranked database images before evaluation. To enable fast evaluation, we follow PatchVlad [START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] and

(a) Retrieval results on Brueghel (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]. green bounding-boxes are one-shot detection results.

(b) Retrieval results on Tokyo24/7 [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF].

(c) Retrieval results on Pitts30k [START_REF] Torii | Visual place recognition with repetitive structures[END_REF]. evaluate our score on the top-100 images given by NetVLAD [START_REF] Arandjelovic | Netvlad: Cnn architecture for weakly supervised place recognition[END_REF]. Although our approach is not specifically designed for place recognition, it achieves performances comparable to Patch-NetVLAD [START_REF] Hausler | Patch-netvlad: Multi-scale fusion of locally-global descriptors for place recognition[END_REF] without RANSAC. Note that the competing approaches either employ specific supervisions or more complicated process such as RANSAC, while our approach is trained only with our synthetic segment swapping data. Note that on this task where retrieving discriminative repeated regions is sufficient and correspondence accuracy is not critical, the Nc-Net architecture preforms better. Similar to the Brueghel results, leveraging COCO [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] annotated segments leads to superior performance. Training with unsupervised segments still leads to competitive results using the NC-Net archi-Table 4.3: Ablation study. We report retrieval mAP on Brueghel (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] and R@1 on Tokyo 24/7 [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] with our cross-image transformer using COCO segments [START_REF] Lin | Microsoft coco: Common objects in context[END_REF]. tecture. However, it gives clearly worst results using the transformer architecture on Tokyo 24/7. We think this performance gap could be bridged using more advanced unsupervised segments.

Dataset

Ablation study. An ablation study of our approach using the cross-image transformer architecture is shown in Tab. 4.3 on the Brueghel (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] and Tokyo24/7 [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] datasets. We notice that: (i) Poisson blending [START_REF] Pérez | Poisson image editing[END_REF] and style transfer [START_REF] Huang | Arbitrary style transfer in real-time with adaptive instance normalization[END_REF] are both critical;

(ii) the three terms of the loss are necessary for good performance. More analysis on the importance of learning correspondences for the generalization of the mask predicition, the similarity score and the architectures are provided in the project page https://imagine.enpc.fr/~shenx/SegSwap/.

Application to Object Discovery and Co-segmentation

Correspondences graph and clustering

In the spirit of [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF], we see object discovery as a graph clustering problem, where the vertices V of the graph G = (V, E) are correspondences between images and the weights of the edges encodes consistency between the correspondences. Let us consider a set of N images (I 1 , ..., I N ). For every pair of images our network predicts correspondences that we add to the set of vertices V if the associated mask value is higher than a threshold. Each vertex v i = (s i , t i , x s i , x t i , m i ) [START_REF] Sun | Learning dictionary of discriminative part detectors for image categorization and cosegmentation[END_REF] 0.886 0.36 0.870 0.73 0.876 0.55 0.877 0.55 Joulin et al. [START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF] 0.493 0.15 0.587 0.37 0.638 0.30 0.572 0.27 Kim et al. [START_REF] Kim | Distributed cosegmentation via submodular optimization on anisotropic diffusion[END_REF] 0.802 0.08 0.689 0.00 0.751 0.06 0.754 0.05 Rubinstein et al. [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF] 0.880 0.56 0.854 0.64 0.828 0.52 0.827 0.43 Chen et al. [START_REF] Chen | Enriching visual knowledge bases via object discovery and segmentation[END_REF] 0.902 0.40 0.876 0.65 0.893 0.58 0.890 0.54 Quan et al. [START_REF] Quan | Object co-segmentation via graph optimizedflexible manifold ranking[END_REF] 0.910 0.56 0.885 0.67 0.893 0.58 0.896 0.60 Hati et al. [START_REF] Hati | Image co-segmentation using maximum common subgraph matching and region co-growing[END_REF] 0.777 0.33 0.621 0.43 0.738 0.20 0.712 0.32 Chang et al. [START_REF] Chang | Optimizing the decomposition for multiple foreground cosegmentation[END_REF] 0.726 0.27 0.759 0.36 0.797 0.36 0.761 0.33 Lee et al. [START_REF] Lee | Multiple random walkers and their application to image cosegmentation[END_REF] 0.528 0.36 0.647 0.42 0.701 0.39 0.625 0.39 Jerripothula et al. [START_REF] Jerripothula | Image co-segmentation via saliency cofusion[END_REF] 0.905 0.61 0.880 0.71 0.883 0.61 0.889 0.64 Jerripothula et al. [START_REF] Jerripothula | Object co-skeletonization with co-segmentation[END_REF] in the graph is thus associated to a predicted correspondence and defined by the indices s i and t i of the images it connects, the associated coordinates x s i and x t i and the predicted mask value m i . We use cycle consistency to define the weights of the edges between the different vertices. More precisely, we only connect correspondences which have exactly one image in common. For example, let's assume that we have two vertices v i and v j such that If s i = s j = s and t i = t j . We use our network to predict correspondence fields C t i →t j and C t j →t i and we define the weight i,j of the edge between v i and v j as:

i,j = 1 2 m i m j exp(- x s i -x s j σ ) exp(- x t i -C tj →ti (x t j ) σ ) + exp(- x t j -C ti→tj (x t i ) σ ) (4.5)
where σ is a scalar hyper-parameter. The edges are defined similarly in the cases s i = t j , t i = s j and t i = t j . More details about the way we define the graph and in particular strategies to limit the number of vertices are given in the project page.

Given the correspondence graph, we use the spectral decomposition of its adjacency matrix [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF][START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] either to obtain clusters of correspondences for object discovery, or a foreground potential for co-segmentation. For discovery we first compute N eig principal eigenvectors then performing K-means with K cluster clusters. For co-segmentation, we directly use the first eigenvector to define a foreground potential. Note that because we only consider in the graph correspondences with mask values higher than a threshold, the full graph is extremely sparse that the eigen-decomposition can be efficiently computed.

Experiments

Object co-segmentation on Internet dataset [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF]. We build the correspondences graph using for each image only the correspondences in the five most similar images according to the retrieval score of Eqn. 3.2. We then use the principal eigen-vector of the correspondence graph to define a seed for Grab-Cut [START_REF] Rother | grabcut" interactive foreground extraction using iterated graph cuts[END_REF]. More precisely, for every image we associate to each position the sum of the eigen-vector values for the correspondences at this position. Note that GrabCut [START_REF] Rother | grabcut" interactive foreground extraction using iterated graph cuts[END_REF]) is crucial to achieve good performance on this dataset, and is widely used by competing approaches such as [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF][START_REF] Jerripothula | Image co-segmentation via saliency cofusion[END_REF][START_REF] Quan | Object co-segmentation via graph optimizedflexible manifold ranking[END_REF][START_REF] Hsu | Co-attention cnns for unsupervised object co-segmentation[END_REF]Chen et al., 2020b). More details about the GrabCut [START_REF] Rother | grabcut" interactive foreground extraction using iterated graph cuts[END_REF]) can be found in the project page. We follow the standard evaluation protocol [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF]Chen et al., 2020b) and report pixel-level precision P and the Jaccard index J on three subsets: Airplane, Car, Horse. The precision P measures pixel accuracy. The Jaccard index J is the IoU between the segmented object and ground truth object. Quantitative results are presented in Tab. 4.4 and qualitative results in Fig. 4.4b. Our cross-image transformer obtains performance comparable to the state of the art unsupervised approaches. Again, the performances using annotated COCO [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] segments and unsupervised segments are close, which demonstrates that the success of our approach does not come from implicitly leveraging annotated object segmentations. Sparse Nc-Net performances are clearly worse for this task. This can be understood by looking at qualitative results: the segmentation masks predicted by Nc-Net tend to be more localized in discriminative regions.

Discovery on Brueghel dataset (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]. Images are resized to 640 × 640, as many repeated details in Brueghel (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] are small. We also remove duplicate images and images with similar borders to focus on more interesting repeated details.

Again, we only include in the graph the correspondences from the five most similar images according to the retrieval score to limit the size of the graph and we perform K-means for K cluster = 500 clusters with N eig = 100 principal eigen vectors. The graph has ∼900K nodes and it took 10 hours to compute predictions of all the pairs and 2 hours to perform the eigen-decomposition and clustering. Fig. 4.4b presents some interesting clusters that are not covered by ArtMiner [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] 1 . More results and details are in the project page https://imagine.enpc.fr/~shenx/ SegSwap/.

Conclusion

In this chapter, we presented a "segment swapping" approach to generate pairs of images with repeated patterns from which we show it is possible to train co-segementation and correspondence prediction networks. We evaluated two architectures, a crossimage transformer and Sparse Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF]. We also compared using annotated segments in COCO [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] and segments extracted in a completely unsupervised way, which shows that our approach is not reliant on COCO [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] object annotations. The trained models shows competitive or better performance on various datasets and different tasks, including art detail retrieval, place recognition and object discovery.

Chapter 5 Unsupervised Dense Image Alignment

In the chapter, we consider the generic problem of dense alignment between two images, whether they be two frames of a video, two widely different views of a scene, two paintings depicting similar content, etc. Whereas each such task is typically addressed with a domain-specific solution, we show that a simple unsupervised approach performs surprisingly well across a range of tasks. Our main insight is that parametric and non-parametric alignment methods have complementary strengths. We propose a two-stage process: first, a feature-based parametric coarse alignment using one or more homographies, followed by non-parametric fine pixel-wise alignment. Coarse alignment is performed using RANSAC on off-the-shelf deep features. Fine alignment is learned in an unsupervised way by a deep network which optimizes a standard structural similarity metric (SSIM) between the two images, plus cycle-consistency. Despite its simplicity, our method shows competitive results on a range of tasks and datasets, including unsupervised optical flow on KITTI, dense correspondences on Hpatches, two-view geometry estimation on YFCC100M, localization on Aachen Day-Night, and, for the first time, fine alignment of artworks on the Brughel dataset. Our code and data are available at http://imagine.enpc.fr/~shenx/RANSAC-Flow/.

Introduction

Dense image alignment (also known as image registration) is one of the fundamental vision problems underlying many standard tasks from panorama stitching to optical flow. Classic work on image alignment can be broadly placed into two camps: parametric and non-parametric. Parametric methods assume that the two images are related by a global parametric transformation (e.g. affine, homography, etc), and use robust approaches, like RANSAC, to estimate this transformation. Non-parametric methods do not make any assumptions on the type of transformation, and attempt to directly optimize some pixel agreement metric (e.g. brightness constancy constraint in optical flow and stereo). However, both approaches have flaws: parametric methods fail (albeit gracefully) if the parametric model is only an approximation for the true transform, while non-parametric methods have trouble dealing with large displacements and large appearance changes (e.g. two photos taken at different times from different views). It is natural, therefore, to consider a hybrid approach, combining the benefits of parametric and non-parametric methods together.

In this chapter, we propose RANSAC-flow, a two-stage approach integrating parametric and non-parametric methods for generic dense image alignment. Fig. 5.2 shows an overview. In the first stage, a classic geometry-verification method (RANSAC) is applied to a set of feature correspondences to obtain one or more candidate coarse alignments. Our method is agnostic to the particular choice of transformation(s) and features, but we've found that using multiple homographies and off-the-shelf selfsupervised deep features works quite well. In the second non-parametric stage, we refine the alignment by predicting a dense flow field for each of the candidate coarse transformations. This is achieved by self-supervised training of a deep network to optimize a standard structural similarity metric (SSIM) [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF] between the pixels of the warped and the original images, plus a cycle-consistency loss (Zhou et al., 2016).

Despite its simplicity, the proposed approach turns out to be surprisingly effective. The coarse alignment stage takes care of large-scale viewpoint and appearance variations and, thanks to multiple homographies, is able to capture a piecewise-planar approximation of the scene structure. The learned local flow estimation stage is able to refine the alignment to the pixel level without relying on the brightness constancy assumption. As a result, our method produces competitive results across a wide range of different image alignment tasks, as shown in Fig. 5.1: (a) unsupervised optical flow estimation on KITTI (Menze and Geiger, 2015a) and Hpatches [START_REF] Balntas | Hpatches: A benchmark and evaluation of handcrafted and learned local descriptors[END_REF], (b) visual localization on Aachen Day-Night [START_REF] Sattler | Benchmarking 6dof outdoor visual localization in changing conditions[END_REF], (c) 2-view geometry estimation on YFCC100M [START_REF] Thomee | Yfcc100m: The new data in multimedia research[END_REF], (d) dense image alignment, and applications to (e) detail alignment in artwork and (f) texture transfer. Our code and data are available at http://imagine.enpc.fr/~shenx/RANSAC-Flow/.

Related Work

Feature-based image alignment. The classic approach to align images with very different appearances is to use sparse local image features, such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], which are designed to deal with large viewpoint and illumination differences as well as clutter and occlusion. These features have to be used together with a geometric regularization step to discard false matches. This is typically done using RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF][START_REF] Raguram | Usac: a universal framework for random sample consensus[END_REF][START_REF] Barath | Graph-cut ransac[END_REF]Barath et al., 2019) to fit a simple geometric transformation (e.g. affine or homography) [START_REF] Szeliski | Image alignment and stitching: A tutorial[END_REF]. Recently, many works proposed to learn better local features [START_REF] Luo | Contextdesc: Local descriptor augmentation with cross-modality context[END_REF][START_REF] Detone | Superpoint: Self-supervised interest point detection and description[END_REF][START_REF] Tian | L2-net: Deep learning of discriminative patch descriptor in euclidean space[END_REF][START_REF] Mishchuk | Working hard to know your neighbor's margins: Local descriptor learning loss[END_REF][START_REF] Luo | Geodesc: Learning local descriptors by integrating geometry constraints[END_REF]Revaud et al., 2019b). Differentiable and trainable version of RANSAC have also been developed [START_REF] Zhang | Learning two-view correspondences and geometry using order-aware network[END_REF]Qi et al., 2017a;[START_REF] Plötz | Neural nearest neighbors networks[END_REF][START_REF] Ranftl | Deep fundamental matrix estimation[END_REF].

Using mid-level features [START_REF] Singh | Unsupervised discovery of mid-level discriminative patches[END_REF]Kim et al., 2017b[START_REF] Kim | Recurrent transformer networks for semantic correspondence[END_REF][START_REF] Kim | Semantic attribute matching networks[END_REF]) instead of local keypoints, proved to be beneficial for matching visual content across modalities, e.g. 3D models and paintings [START_REF] Aubry | Painting-to-3d model alignment via discriminative visual elements[END_REF]. Recently, [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] learned deep mid-level features for matching across different visual media (drawings, oil paintings, frescoes, sketches, etc), and used them together with spatial verification to discover copied details in a dataset of thousands of artworks. [START_REF] Rocco | Convolutional neural network architecture for geometric matching[END_REF] used deep feature map correlations as input to a regression network on syn-thetic image deformations to predict the parameters of an affine or thin-plate spline deformation. Finally, transformer networks [START_REF] Jaderberg | Spatial transformer networks[END_REF] can also learn parametric alignment typically as a by-product of optimizing a classification task.

Direct image alignment. Direct, or pixel-based, alignment has its roots in classic optical flow methods, such as Lucas-Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF], who solve for a dense flow field between a pair of images under a brightness constancy assumption. The main drawback is these methods tend to work only for very small displacements. This has been partially addressed with hierarchical flow estimation [START_REF] Szeliski | Image alignment and stitching: A tutorial[END_REF], as well as using local features in addition to pixels to increase robustness [START_REF] Brox | Large displacement optical flow[END_REF][START_REF] Revaud | Epicflow: Edge-preserving interpolation of correspondences for optical flow[END_REF][START_REF] Bailer | Flow fields: Dense correspondence fields for highly accurate large displacement optical flow estimation[END_REF][START_REF] Hu | Efficient coarse-to-fine patchmatch for large displacement optical flow[END_REF]. However, all such methods are still limited to aligning very similar images, where the brightness constancy assumption mostly holds. SIFT-Flow [START_REF] Liu | Sift flow: Dense correspondence across scenes and its applications[END_REF] was an early method that aimed at expanding optical flow-style approaches for matching pairs of images across physically distinct, and visually different scenes (and later generalized to joint image set alignment using cycle consistency (Zhou et al., 2015)). Some approaches such as SCV [START_REF] Cech | Efficient sequential correspondence selection by cosegmentation[END_REF] and MODS [START_REF] Mishkin | Mods: Fast and robust method for two-view matching[END_REF], were proposed to grow matches around initial warping. In the deep era, [START_REF] Long | Do convnets learn correspondence?[END_REF] showed that ConvNet activation features can be used for correspondence, achieving similar performance to SIFT-Flow. [START_REF] Choy | Universal correspondence network[END_REF] proposed to learn matches with a Correspondence Contrastive loss, producing semi-dense matches. (Rocco et al., 2018b) introduced the idea of using 4D convolutions on the feature correlations to learn to filter neighbour consensus. Note that these latter works target semantic correspondences, whereas we focus on the case when all images depict the same physical scene.

Deep Flow methods. Deep networks can be trained to predict optical flow and to be robust to drastic appearance changes, but require adapted loss and architectures. Flows can be learned in a completely supervised way using synthetic data, e.g. in [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF][START_REF] Ilg | Flownet 2.0: Evolution of optical flow estimation with deep networks[END_REF], but transfer to real data remains a difficult problem. Unsupervised training through reconstruction has been proposed in several works, targeting brightness consistency [START_REF] Ahmadi | Unsupervised convolutional neural networks for motion estimation[END_REF]Wang et al., 2018a), gradient consistency [START_REF] Ren | Unsupervised deep learning for optical flow estimation[END_REF] or high SSIM [START_REF] Jason | Back to basics: Unsupervised learning of optical flow via brightness constancy and motion smoothness[END_REF][START_REF] Yin | Geonet: Unsupervised learning of dense depth, optical flow and camera pose[END_REF]. This idea of learning correspondences through reconstruction has been applied to video, reconstructing colors [START_REF] Vondrick | Tracking emerges by colorizing videos[END_REF], predicting weights for frame reconstruction [START_REF] Kong | Multigrid predictive filter flow for unsupervised learning on videos[END_REF][START_REF] Lai | Self-supervised learning for video correspondence flow[END_REF], or directly optimizing feature consistency in the warped images [START_REF] Wang | Learning correspondence from the cycleconsistency of time[END_REF]. Several papers have introduced cycle consistency as an additional supervisory signal for image alignment (Zhou et al., 2016;[START_REF] Wang | Learning correspondence from the cycleconsistency of time[END_REF]. Recently, feature correlation became a key part of several architectures [START_REF] Ilg | Flownet 2.0: Evolution of optical flow estimation with deep networks[END_REF][START_REF] Sun | Pwc-net: Cnns for optical flow using pyramid, warping, and cost volume[END_REF] aiming at predicting dense flows. Particularly relevant to us is the approach of [START_REF] Melekhov | Dgc-net: Dense geometric correspondence network[END_REF] which includes a feature correlation layer in a U-Net [START_REF] Ronneberger | U-net: Convolutional networks for biomedical image segmentation[END_REF] architecture to improve flow resolution. A similar approach has been used in [START_REF] Laskar | Geometric image correspondence verification by dense pixel matching[END_REF] which predicts dense correspondences. Recently, Glu-Net [START_REF] Prune | GLU-Net: Global-local universal network for dense flow and correspondences[END_REF] learns dense correspondences by investigating the combined use of global and local correlation layers.

Hybrid parametric/non-parametric image alignment. Classic "plane + parallax" approaches [START_REF] Sawhney | 3d geometry from planar parallax[END_REF][START_REF] Kumar | Direct recovery of shape from multiple views: A parallax based approach[END_REF][START_REF] Irani | Direct recovery of planar-parallax from multiple frames[END_REF][START_REF] Wulff | Optical flow in mostly rigid scenes[END_REF] aimed to combine parametric and non-parametric alignment by first estimating a homography (plane) and then considering the violations from that homography (parallax). Similar ideas also appeared in stereo, e.g. model-based stereo [START_REF] Debevec | Modeling and rendering architecture from photographs: A hybrid geometry-and image-based approach[END_REF]. Recently, [START_REF] Yin | Geonet: Unsupervised learning of dense depth, optical flow and camera pose[END_REF][START_REF] Cao | Learning independent object motion from unlabelled stereoscopic videos[END_REF] proposed to learn optical flow by jointly optimizing with depth and ego-motion for stereo videos. Our RANSAC-Flow is also related to the methods designed for geometric multi-model fitting, such as RPA [START_REF] Magri | T-linkage: A continuous relaxation of j-linkage for multimodel fitting[END_REF], T-linkage [START_REF] Magri | Multiple structure recovery via robust preference analysis[END_REF] and Progressive-X (Barath and Matas, 2019).

Method

Our two-stage RANSAC-Flow method is illustrated in Fig. 5.2. In this section, we describe the coarse alignment stage, the fine alignment stage, and how they can be iterated to use multiple homographies.

Coarse alignment by feature-based RANSAC

Our coarse parametric alignment is performed using RANSAC to fit a homography on a set of candidate sparse correspondences between the source and target images. We use off-the-shelf deep features (conv4 layer of a ResNet-50 network) to obtain these correspondences. We experimented with both pre-trained ImageNet features as well as features learned via MoCo self-supervision [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF], and obtained similar results. We found it was crucial to perform feature matching at different scales. We fixed the aspect ratio of each image and extracted features at seven scales: 0.5, 0.6, 0.88, 1, 1.33, 1.66 and 2. Matches that were not symmetrically consistent were discarded. The estimated homography is applied to the source image and the result is given together with the target image as input to our fine alignment. We report coarse-only baselines in Sec. 5.4 for both features as "ImageNet [START_REF] He | Deep residual learning for image recognition[END_REF]+H " and "MoCo [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF]+H ".

Fine alignment by local flow prediction

Given a source image I s and a target image I t which have already been coarsely aligned, we want to predict a fine flow F s→t between them. We write F s→t as the mapping function associated to the flow F s→t . Since we only expect the fine alignment to work in image regions where the homography is a good approximation of the deformation, we predict a matchability mask M s→t , indicating which correspondences are valid. In the following, we first present our objective function, then how and why we optimize it using a self-supervised deep network.

Objective function. Our goal is to find a flow that warps the source into an image similar to the target. We formalize this by writing an objective function composed of three parts: a reconstruction loss L rec , a matchability loss L m and a cycle-consistency loss L c . Given the pair of images(I s , I t ) the total loss is:

L(I s , I t ) = L rec (I s , I t ) + λL m (I s , I t ) + µL c (I s , I t ) (5.1)
with λ and µ hyper-parameters weighting the contribution of the matchability and cycle loss. We detail these three components in the following paragraphs. Each loss is defined pixel-wise.

Matchability loss. Our matchability mask can be seen as pixel-wise weights for the reconstruction and cycle-consistency losses. These losses will thus encourage the matchability to be zero. To counteract this effect, the matchability loss encourages the matchability mask to be close to one. Since the matchabiliy should be consistent between images, we define the cycle-consistent matchability at position (x,y) in I t , (x',y') in I s with (x, y) = F s→t (x , y ) as:

M cycle t (x, y) = M t→s (x, y)M s→t (x , y ) (5.2)
where M s→t is the matchability predicted from source to target and M t→s the one predicted from target to source. M cycle t will be high only if both the matchability of the corresponding pixels in the source and target are high. The matchability loss encourages this cycle-consistent matchability to be close to 1:

L m (I s , I t ) = (x,y)∈It |M cycle t (x, y) -1|
(5.3) Note that directly encouraging the matchability to be 1 leads to similar quantitative results, but using the cycle consistent matchability helps to identify regions that are not matchable in the qualitative results.

Reconstruction loss. Reconstruction is the main term of our objective and is based on the idea that the source image warped with the predicted flow F s→t should be aligned to the target image I t . We use the structural similarity (SSIM) [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF] as a robust similarity measure:

L SSIM rec (I s , I t ) = (x,y)∈It M cycle t (x, y) (1 -SSIM (I s (x , y ), I t (x, y))) (5.4)
Cycle consistency loss. We enforce cycle consistency of the flow for 2-cycles:

L c (I s , I t ) = (x,y)∈It M cycle t (x, y) (x , y ), F t→s (x, y) 2 (5.5)
Optimization with self-supervised network. Optimizing objective functions similar to the one described above is common to most optical flow approaches. However, this is known to be an extremely difficult task because of the highly non-convex nature of the objective which typically has many bad local minima. Recent works on the priors implicit within deep neural network architectures [START_REF] Shocher | zero-shot" super-resolution using deep internal learning[END_REF][START_REF] Ulyanov | Deep image prior[END_REF] suggest that optimizing the flow as the output of a neural network might overcome these problems. Unfortunately, our objective is still too complex to obtain good result from optimization on just a single image pair. We thus built a larger database of image pairs on which we optimize the neural network parameters in a self-supervised way (i.e. without need for any annotations). The network could then be fine-tuned on the test image pair itself, but we have found that this singlepair optimization leads to unstable results. However, if several pairs similar to the test pair are available (i.e. we have access to the entire test set), the network can be fine-tuned on this test set which leads to some improvement, as can be seen in our experiments where we systematically report our results with and without fine-tuning.

To collect image pairs for the network training, we simply sample pairs of images representing the same scene and applied our coarse matching procedure. If it led to enough inliers, we added the pair to our training image set, if not we discarded it. For all the experiments, we sampled image pairs from the MegaDepth [START_REF] Li | Megadepth: Learning single-view depth prediction from internet photos[END_REF] scenes, using 20, 000 image pairs from 100 scenes for training and 500 pairs from 30 different scenes for validation.

Multiple homographies

The overall procedure described so far provides good results on image pairs where a single homography serves as a good (if not perfect) approximation of the overall transformation (e.g. planar scenes). This is, however, not the case for many image pairs with strong 3D effects or large objects displacements. To address this, we iterate our alignment algorithm to let it discover more homography candidates. At each iteration, we remove feature correspondences that were inliers for the previous homographies as well as from locations inside the previously predicted matchability masks, and recompute RANSAC again. We stop the procedure when not enough candidate correspondences remain. The full resulting flow is obtained by simply aggregating the estimated flows from each iteration together. The number of homographies considered depends on the input image pairs. For example, the average number of homographies we obtain from pairs for two-view geometry estimation in the YFCC100M [START_REF] Thomee | Yfcc100m: The new data in multimedia research[END_REF] dataset is about five. While more complex combinations could be considered, this simple approach provides surprisingly robust results. In our experiments, we quantitatively validate the benefits of using these multiple homographies ("multi-H").

Architecture and implementation details

In our fine-alignment network, the input source and target images (I s , I t ) are first processed separately by a fully-convolutional feature extractor which outputs two feature maps (f s , f t ). Each feature from the source image is then compared to features in a (2K + 1) × (2K + 1) square neighbourhood in the target image using cosine similarity, similar to [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF][START_REF] Ilg | Flownet 2.0: Evolution of optical flow estimation with deep networks[END_REF]. This results in a W × H × (2K + 1) 2 similarity tensor s defined by:

s(i, j, (m + K + 1)(n + K + 1)) = f s (i, j).f t (i -m, j -n) f s (i, j) f t (i -m, j -n) (5.6)
where m, n ∈ [-K, ..., K] and "." denotes dot product. In all our experiments, we used K = 3. This similarity tensor is taken as input by two fully-convolutional prediction networks which predict flow and matchability.

Our feature extractor is similar to the Conv3 feature extractor in ResNet-18 [START_REF] He | Deep residual learning for image recognition[END_REF] but with minor modifications: the first 7 × 7 convolutional kernel of the network is replaced by a 3 × 3 kernel without stride and all the max-poolings and strided-convolution are replaced by their anti-aliasing versions proposed in [START_REF] Zhang | Making convolutional networks shift-invariant again[END_REF]. These changes aim at reducing the loss of spatial resolution in the network, the output feature map being 1/8th of the resolution of the input images. The flow and matchability prediction networks are fully convolutional networks composed of three Conv+Relu+BN blocks (Convolution, Relu activation and Batch Normalization [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF]) with 512, 256, 128 filters respectively and a final convolutional layer. The output flows and matchability are bilinearly upsampled to the resolution of the input images. Note we tried using up-convolutions, but this slightly decreased the performance while increasing the memory footprint.

We use Kornia [START_REF] Riba | Kornia: an open source differentiable computer vision library for pytorch[END_REF] for homography warping. All images were resized so that their minimum dimension is 480 pixels. The hyper-parameters of our objective are set to λ = 0.01, µ = 1. We provide a study of λ and µ in Sec. 5.4.4. The entire fine alignment model is learned from random initialization using the Adam optimizer [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] with a learning rate of 2e-4 and momentum terms β 1 , β 2 set to 0.5, 0.999. We trained only with L rec for the first 150 epochs then added L c for another 50 epochs and finally trained with all the losses (Eqn. 5.1) for the final 50 epochs. We use a mini-batch size of 16 for all the experiments. The whole training converged in approximately 30 hours using a single GPU Geforce GTX 1080 Ti for [START_REF] Maddern | km: The oxford robotcar dataset[END_REF][START_REF] Larsson | A cross-season correspondence dataset for robust semantic segmentation[END_REF] and MegaDepth [START_REF] Li | Megadepth: Learning single-view depth prediction from internet photos[END_REF]. We report the accuracy over all annotated alignments for pixel error smaller than d pixels. All the images are resized to have minimum dimension 480 pixels.

Method

Direct correspondences evaluation

Optical flow. We evaluate the quality of our dense flow on the KITTI 2015 flow (Menze and Geiger, 2015a) and Hpatches [START_REF] Balntas | Hpatches: A benchmark and evaluation of handcrafted and learned local descriptors[END_REF] datasets and report the results in Table 5.1. On KITTI (Menze and Geiger, 2015a), we evaluated both on the training and the test set since other approaches report results on one or the other. Note we could not perform an ablation study on the test set since the number of submissions to the online server is strictly limited. We report results both on non-occluded (noc) and all regions. Our results are on par with state of the art unsupervised and weakly supervised results on non-occluded regions, outperforming for example the recent approach [START_REF] Cao | Learning independent object motion from unlabelled stereoscopic videos[END_REF][START_REF] Prune | GLU-Net: Global-local universal network for dense flow and correspondences[END_REF]. Unsurprisingly, our method is much weaker on occluded regions since our algorithm is not designed specifically for optical flow performances and has no reason to handle occluded regions in a good way. We find that the largest errors are actually in occluded regions and image boundaries (Fig. 5.3). Interestingly, our ablations show that the multiple homographies is critical to our results even if the input images appear quite similar.

For completeness, we also present results on the Hpatches [START_REF] Balntas | Hpatches: A benchmark and evaluation of handcrafted and learned local descriptors[END_REF]. Note that Hpatches dataset is synthetically created by applying homographies to a set of real images, which would suggest that our coarse alignment alone should be enough. However, in practice, we have found that, due to the lack of feature correspondences, adding the fine flow network significantly boosts the results compared to using only our coarse approach. While these results show that our approach is reasonable, these datasets only contain very similar and almost aligned pairs while the main goal of our approach is to be able to handle challenging cases with strong viewpoint and appearance variations.

Sparse correspondences. Dense correspondence annotations are typically not available for extreme viewpoint and imaging condition variations. We thus evaluated our results on sparse correspondences available on the RobotCar [START_REF] Maddern | km: The oxford robotcar dataset[END_REF][START_REF] Larsson | A cross-season correspondence dataset for robust semantic segmentation[END_REF] and MegaDepth [START_REF] Li | Megadepth: Learning single-view depth prediction from internet photos[END_REF] datasets. In Robotcar, we evaluated on the correspondences provided by [START_REF] Larsson | A cross-season correspondence dataset for robust semantic segmentation[END_REF], which leads to approximately 340M correspondences. The task is especially challeng-ing since the images correspond to different and challenging conditions (dawn, dusk, night, etc.) and most of the correspondences are on texture-less region such as roads where the reconstruction objective provides very little information. However, viewpoints in RobotCar are still very similar. To test our method on pairs of images with very different viewpoints, we used pairs of images from scenes of the MegaDepth [START_REF] Li | Megadepth: Learning single-view depth prediction from internet photos[END_REF] dataset that we didn't use for training and validation. Note that no real ground truth is available and we use as reference the result of SfM reconstructions. More precisely, we take 3D points as correspondences and randomly sample 1 600 pairs of images that shared more than 30 points, which results in approximately 367K correspondences.

On both datasets, we evaluated several baselines which provide dense correspondences and were designed to handle large viewpoint changes, inluding SIFT-Flow [START_REF] Liu | Sift flow: Dense correspondence across scenes and its applications[END_REF], variants of NcNet (Rocco et al., 2018b), DGC-Net [START_REF] Melekhov | Dgc-net: Dense geometric correspondence network[END_REF] and the very recent, concurrently developed approach Glu-Net [START_REF] Prune | GLU-Net: Global-local universal network for dense flow and correspondences[END_REF]. In the results provided in Tab. 5.2, we can see that our approach is comparable to Glu-Net on RobotCar [START_REF] Maddern | km: The oxford robotcar dataset[END_REF][START_REF] Larsson | A cross-season correspondence dataset for robust semantic segmentation[END_REF] but largely improves performances on MegeDepth [START_REF] Li | Megadepth: Learning single-view depth prediction from internet photos[END_REF]. We believe this is because by the large viewpoint variations on MegeDepth is better handled by our method. This qualitative difference between the datasets can be seen in the visual results in Fig. 5.4. Note that we can clearly see the effect of fine flows on the zoomed details.

Evaluation for downstream tasks

Given the limitations of the correspondence benchmarks discussed in the previous paragraph, and to demonstrate the practical interest of our results, we now evaluate our correspondences on two standard geometry estimation benchmarks where many results from competing approaches exist. Note that competing approaches typically use only sparse matches for these tasks, and being able to perform them using dense correspondences is a demonstration of the strength and originality of our method. Two-view geometry estimation. Given a pair of views of the same scene, twoview geometry estimation aims at recovering their relative pose. To validate our approach, we follow the standard setup of [START_REF] Zhang | Learning two-view correspondences and geometry using order-aware network[END_REF] evaluating on 4 × 1000 image pairs for 4 scenes from YFCC100M [START_REF] Thomee | Yfcc100m: The new data in multimedia research[END_REF] dataset and reporting mAP for different thresholds on the angular differences between ground truth and Table 5.3: Two-view geometric estimation on YFCC100M [START_REF] Thomee | Yfcc100m: The new data in multimedia research[END_REF][START_REF] Zhang | Learning two-view correspondences and geometry using order-aware network[END_REF] Method mAP @5 • mAP@10 • mAP@20 • SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] 46.83 68.03 80.58 Contextdesc [START_REF] Luo | Contextdesc: Local descriptor augmentation with cross-modality context[END_REF] 47.68 69.55 84.30 Superpoint [START_REF] Detone | Superpoint: Self-supervised interest point detection and description[END_REF] 30.50 50.83 67.85 PointCN (Moo Yi et al., 2018;[START_REF] Zhang | Learning two-view correspondences and geometry using order-aware network[END_REF] 47.98 --PointNet++ (Qi et al., 2017b;[START_REF] Zhang | Learning two-view correspondences and geometry using order-aware network[END_REF] 46.23 --N 3 Net [START_REF] Plötz | Neural nearest neighbors networks[END_REF][START_REF] Zhang | Learning two-view correspondences and geometry using order-aware network[END_REF] 49.13 --DFE [START_REF] Ranftl | Deep fundamental matrix estimation[END_REF][START_REF] Zhang | Learning two-view correspondences and geometry using order-aware network[END_REF] 49.45 --OANet [START_REF] Zhang | Learning two-view correspondences and geometry using order-aware network[END_REF] 52 predicted vectors for both rotation and translation as the error metric. For each image pair, we use the flow we predict in regions with high matchability (> 0.95) to estimate an essential matrix with RANSAC and the 5-point algorithm [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. To avoid correspondences in the sky, we used the pre-trained the segmentation network provided in [START_REF] Zhou | Scene parsing through ade20k dataset[END_REF] to remove them. While this require some supervision, this is reasonable since most of the baselines we compare to have been trained in a supervised way. As can be seen in Tab. 5.3, our method outperforms all the baselines by a large margin including the recent OANet [START_REF] Zhang | Learning two-view correspondences and geometry using order-aware network[END_REF] method which is trained with ground truth calibration of cameras. Also note that using multiple homographies consistently boosts the performance of our method.

Once the relative pose of the cameras has been estimated, our correspondences can be used to perform stereo reconstruction from the image pair as illustrated in Fig. 5.1(c) and in the project webpage. Note that contrary to many stereo reconstruction methods, we can use two very different input images.

Day-Night Visual Localization. Another task we performed is visual localization. We evaluate on the local feature challenge of the Visual Localization benchmark [START_REF] Sattler | Benchmarking 6dof outdoor visual localization in changing conditions[END_REF][START_REF] Sattler | Image retrieval for image-based localization revisited[END_REF]. For each of the 98 night-time images contained in set is not precisely the same, much more details can be seen in the average of our fine-aligned images.

Artwork analysis. Finding and matching near-duplicate patterns is an important problem for art historians. Computationally, it is difficult because the duplicate appearance can be very different [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]. In Fig. 5.7, we show visual results of aligning different versions of artworks from the Brueghel dataset [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] with our coarse and fine alignment. We can clearly see that a simple homography is not sufficient and that the fine alignment improves results by identifying complex displacements. The fine flow can thus be used to provide insights on Brueghel's copy process. Indeed, we found that some artworks were copied in a spatially consistent way, while in others, different parts of the picture were not aligned with each other. This can be clearly seen in the flows in Fig. 5.9, which are either very regular or very discontinuous. The same process can be applied to more than a single pair of images, as illustrated in Fig. 5.1(e) and 5.8 where we align together many similar details identified by [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]. Visualizing the succession of the finely aligned images allows to identify their differences.

Dependency on λ and µ

Our training has 3 stages (Sec. 5.3.4): the model was firstly learned with the reconstruction loss L rec then added cycle-consistent flow loss L c and finally trained with all the losses (Eqn. 5.1). In Tab. 5.5, we provide an analysis on the weighting parameters λ and µ on sparse correspondences evaluation on MegaDepth [START_REF] Li | Megadepth: Learning single-view depth prediction from internet photos[END_REF] and report the accuracy at 3 pixels. We can see the stage 2 is not very sensitive with respect to µ (Tab. 5.5a), while the stage 3 with adding the mask loss is slightly more sensitive (Tab. 5.5b). Note that we then use the same parameters for fine-tuning on the different datasets.

Conclusion

We have introduced a new unsupervised method for generic dense image alignment which performs well on a wide range of tasks. Our main insight is to combine the advantages of parametric and non-parametric methods in a two-stage approach and to use multiple homography estimations as initializations for fine flow prediction. We also demonstrated it allows new applications for artwork analysis.

Chapter 6

Conclusion

In this chapter, we summarize the main contributions of this thesis and outline some research directions for future work.

Summary of Contributions

In this thesis, we focused on three tasks for artwork analysis: style-invariant patterns retrieval, near-duplicated patterns discovery, and dense image alignment. We have investigated three methods to solve these problems. The technical contributions are detailed below.

In Chapter 3, we proposed a self-supervised feature fine-tuning strategy to address style-invariant feature matching. Our approach consists of leveraging spatial consistency to identify positive and negative training pairs. We optimized a standard triplet loss on these training samples. Our approach can learn features adapted to the training set for matching. In terms of experimental results, we showed that our approach can match features in artworks across different styles. Our approach also improved performance on one-shot art detail detection on (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] as well as geo-localization datasets: LTLL [START_REF] Fernando | Location recognition over large time lags[END_REF] and Oxford [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF].

In Chapter 4, we proposed an approach of learning co-segmentation from synthetic data. To generate the training data, we blended objects to background images using style transfer [START_REF] Huang | Arbitrary style transfer in real-time with adaptive instance normalization[END_REF] and Poisson blending [START_REF] Pérez | Poisson image editing[END_REF]. We also designed an architecture based on transformer [START_REF] Vaswani | Attention is all you need[END_REF] for co-segmentation. The network was learned using masks and correspondences of the blended objects. We also validated the choices of our objective functions and the process of the data generation using Sparse Nc-Net [START_REF] Rocco | Efficient neighbourhood consensus networks via submanifold sparse convolutions[END_REF]. Our approach has been evaluated on various tasks including one-shot art detail detection on Brueghel [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]bru) and place recognition on the Pitts30k [START_REF] Torii | Visual place recognition with repetitive structures[END_REF] and Tokyo 24/7 [START_REF] Torii | 24/7 place recognition by view synthesis[END_REF] datasets.

In Chapter 5, we proposed an unsupervised approach for robust dense image alignment. Our approach is a two-stage approach:: in the first stage, we extract multi-scale features and match them to estimate Homography transformations using RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF]; in the second stage, we designed and learned a Convolutional Neural Network (CNN) through the optimization of a reconstruction loss between target images and warped source images. Our approach is without any supervision. We showed that our approach performs well on various tasks, including standard optical flow estimation on KITTI (Menze and Geiger, 2015a), sparse correspondences evaluation on RobotCar [START_REF] Maddern | km: The oxford robotcar dataset[END_REF][START_REF] Larsson | A cross-season correspondence dataset for robust semantic segmentation[END_REF] and MegaDepth [START_REF] Li | Megadepth: Learning single-view depth prediction from internet photos[END_REF], two-view geometry estimation on YFCC [START_REF] Thomee | Yfcc100m: The new data in multimedia research[END_REF], and 3D reconstruction on Aachen night-time [START_REF] Sattler | Benchmarking 6dof outdoor visual localization in changing conditions[END_REF][START_REF] Sattler | Image retrieval for image-based localization revisited[END_REF]

Future Work

In this section, we analyze some future research directions that could extend the works presented in this thesis.

Interactive annotation system incorporating unsupervised / weakly supervised techniques. As presented in Chapter. 1, the main challenge of artwork analysis is the lack of training data and the main application for object discovery is to automatically collect datasets, it would be useful and efficient to develop annotations tools that can use unsupervised or weakly supervised algorithms. Note that many annotation tools have been developed and made a significant impact on scientific research, representative works are VGG Image Annotator (VIA) [START_REF] Dutta | VGG image annotator (VIA)[END_REF] and LabelMe [START_REF] Russell | Labelme: a database and web-based tool for image annotation[END_REF]. However, these tools only provide a user interface for annotators and no machine learning algorithms are involved. Another advantage is that the task will be better defined by users. In this thesis, we focus on retrieving or detecting near-duplicated patterns. However, for some art historians, obtaining semantically similar patterns might be also interesting. With the system, the task will be better defined and fit to personal interests. This direction seems to be too engineering as a research topic, but there indeed exists some practical problems that are interesting for scientific research. For example, if annotators have a fixed budget, such as labeling 10 samples per class, how to leverage algorithms to recommend these samples to annotators. If annotators label bounding boxes, how to find a robust and efficient way to obtain pixel-level annotations. Besides, as new annotations come, how to efficiently update a model without catastrophic forgetting [START_REF] Kirkpatrick | Overcoming catastrophic forgetting in neural networks[END_REF][START_REF] Kemker | Measuring catastrophic forgetting in neural networks[END_REF] etc.

Learning from synthetic data and weakly supervised pairs. In Chapter 4, we showed that it is possible to learn co-segmentation from synthetic data. Moreover, the learned models achieved promising results on different tasks. One interesting direction would be how to leverage weakly supervised pairs and synthetic data during the training. Positive pairs, which contain repeated segments, are not complicated to obtain. One solution has been presented in Chapter 5, which consists of leveraging multi-scale feature matching and geometric verification. Note that this weakly supervised learning can be done on test sets. Then the problem is highly related to the topic of test time fine-tuning [START_REF] Sun | Test-time training with self-supervision for generalization under distribution shifts[END_REF].

End-to-end dense image alignment. In Chapter 5, we presented a two-stage method for unsupervised dense image alignment. The first stage consists of using RANSAC to estimate Homography transformations, which is not differentiable. As future work, it would be interesting to adapt this coarse-to-fine regime such that the overall approach is fully differentiable. As predicting matchable regions significantly improves the accuracy of the correspondence (in Sec. 5.4.4), It might be interesting to learn both matchable regions and optical flow end-to-end, which is different from other works on learning optical flow. One possible solution would be designing a proper synthetic dataset for training.

  (a) Style-invariant patterns retrieval. Our first goal is to retrieve artworks depicting the same content as given query motifs (blue bounding boxes). (b) Near-duplicated patterns discovery. Our second goal is to identify near-duplicated visual patterns (red, blue and green circle ) in a collection of artworks. (c) Dense image alignment. Our third goal is to estimate pixel-level alignment for patterns that are near-duplicated and are depicted with different styles.

Figure 1 . 1 :

 11 Figure 1.1: The three main tasks addressed in this thesis

Figure 1 . 2 :

 12 Figure 1.2: Applications of image retrieval.

Figure 1 . 3 :

 13 Figure 1.3: Automatic dataset annotation is one of the motivation for object discovery.Object discovery allows automatically collecting annotations from Internet images. Examples are from[START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF]. A noisy dataset can be gathered via Internet searching engine then discovering common objects can remove distractors and obtain segmentation annotations.

  , illustrated on figure 1.3. Dense image alignment. Dense alignment of images, also known as the optical flow problem, is a classical problem in computer vision. Precise optical flow leads to numerous applications, shown in Fig. 1.4:

Figure 1

 1 Figure 1.4: Example of applications of dense image alignment.

( a )

 a Difficulty of annotations. Alignment between related artworks cannot be well approximated by a simple parametric transformation. For example, in this two versions of Diana and Actaeon in the Brueghel[START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] bru) dataset the displacements are very complex, and their alignment would require an extremely tedious pixel-level annotations of the correspondences.(b) Diversity of depiction styles. Four paintings on the topic Man on Egg in the Brueghel[START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF] bru) dataset.

Figure 1 . 5 :

 15 Figure 1.5: The three challenges of our tasks: lack of supervision (Fig. 1.5a), diversity of depiction styles (Fig. 1.5b) and scalability issue. (Fig. 1.5c).

Figure 2

 2 Figure2.2: Proposed approach in[START_REF] Radenović | Fine-tuning cnn image retrieval with no human annotation[END_REF]

Figure 2

 2 Figure 2.3: Proposed CNN architecture in(Li et al., 2018). MC is a mutual correlation layer, which is similar to Flownet[START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF].

Figure 2

 2 Figure 2.4: Proposed two CNN architectures in Flownet1 (Dosovitskiy et al., 2015).

Figure 2

 2 Figure2.5: Estimating progressively more complex geometric transformations in[START_REF] Rocco | Convolutional neural network architecture for geometric matching[END_REF].

Figure 2

 2 Figure 2.6: DGC-Net proposed in[START_REF] Melekhov | Dgc-net: Dense geometric correspondence network[END_REF], which is an iterative architecture consisting of four major components: 1) the feature pyramid creator. 2) the correlation layer. 3) the fully convolutional correspondence map decoders. 4) the warping layer. The matchability decoder is a tiny CNN that predicts a confidence map of correspondences.

Figure 2

 2 Figure 2.7: GLU-Net proposed in (Prune et al., 2020).

Figure 2

 2 Figure 2.8: Neighbourhood Consensus Network (Nc-Net) architecture proposed in(Rocco et al., 2018b).

  (a) common detail (dog) discovered in our new Brueghel dataset of 1587 artworks (b) relationship between painting and two studies discovered from collection of 195 artworks by Dante Gabriel Rossetti Figure 3.1: Examples of repeated visual patterns automatically discovered by our algorithm. Sources: (a) left: Nymphs Sleeping After the Hunt, Spied on by Satyr (oil), center: Diana's Nymphs After the Hunt (oil), right: Seventeen Studies of Different Dogs (drawing); (b) The Bower Meadow (left: chalk, center: oil, right: pastel)

  Figure 3.2: Feature Learning Strategy. (a) Our approach relies on candidate correspondences obtained by matching the features of a proposal region (in red) to the full database . (b)The candidate correspondences are then verified by matching the features of the verification region (in blue) of the query in the candidate images and checking for consistency . (c) Finally, we extract features from the positive regions (in green) from the verified candidates and use them to improve the features using a metric learning loss.

  Figure 3.3: Different region configurations. red: query regions, which are used to get proposal regions, blue: verification regions, green: positive regions.

Figure 3

 3 Figure 3.4: Discovery through geometric consistency.

  dataset, the query patches are only sampled inside the annotaed bounding boxes of the 55 query images, and we only find candidate matches in 2000 images randomly sampled in the whole dataset. The hyper-parameters of the triplet loss, N neg and λ, are fixed to 20 and 0.8 respectively. Our models were trained with the Adam (Kingma and Ba, 2015) optimizer with learning rate 1e-5 and β = [0.9, 0.99]. Using a single GPU Geforce GTX 1080 Ti, training converged in approximately 10 hours, corresponding to 200 iterations of the feature selection and training. Most of the time is spent extracting and verifying candidate matches. ImageNet pre-training was used for initialization in all experiments.

Figure 3 . 5 :

 35 Figure 3.5: Detection example with our trained features on the Brueghel dataset. We show the top 4 matches (in green) for one example of query from each of our 10 annotated categories. Notice how the matches style can be different from the one of the query.

  Figure 3.6: From a single query, shown on the left, we show the detection results obtained with cosine similarity with ImageNet feature (a) and our trained features (b) as well as the ones (c) obtained with our features and the discovery score presented in Sec. 3.4.2.

Figure 3 . 7 :

 37 Figure 3.7: Failures of SIFT matching with geometric verification on images where our algorithm succeeds (Fig. 3.1).

Figure 3

 3 Figure 3.8: Evolution of the mean Average Precision for one-shot matching on the Brueghel dataset during training. Performance decreases after a few iterations for settings where we extract positive regions correlated with the proposal region.

Figure 3 .

 3 Figure 3.10: Example of image clusters discovered by our method. The three cluster without artist names correspond to data from the Brueghel dataset (bru)

Figure 3 .

 3 Figure 3.11: Failure examples in paintings of Peter Paul Rubens and Brughel dataset

Figure 4 . 1 :

 41 Figure 4.1: Learning co-segmentation by "segment swapping". We generate training data with "segment swapping" (Fig. 4.1a) and learn co-segmentation either with our cross-image transformer or Sparse Nc-Net (Rocco et al., 2020) (Fig. 4.1b).

Figure 4 . 3 :

 43 Figure 4.3: Visual results for retrieval on different datasets.For each query image (1st column), we show its 3 most similar images with the predicted masks as transparency. For Brueghel (bru;[START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF], we also show the detection results.

  (a) Co-segmentation results in Internet (Rubinstein et al., 2013) dataset for the Horse, Airplane and Car categories. (b) Examples of discovered clustered on Brueghel (bru; Shen et al., 2019).

Figure 4 . 4 :

 44 Figure 4.4: Visual results for object discovery. We show co-segmentation results on the Internet (Rubinstein et al., 2013) in Fig. 4.4a and some discovered clusters in Brueghel (Shen et al., 2019; bru) in Fig. 4.4b.

Figure 5

 5 Figure 5.1: RANSAC-Flow provides competitive results on a wide variety of tasks and enables new challenging applications.

Figure 5 . 2 :

 52 Figure 5.2: Overview of RANSAC-Flow. Stage 1: given a pair of images, we compute sparse correspondences (using off-the-shelf deep features), use RANSAC to estimate a homography, and warp second image using it. Stage 2: given two coarsely aligned images, our self-supervised fine flow network generates flow predictions in the matchable region. To compute further homographies, we can remove matched correspondences, and iterate the process.

  Figure 5.4: Visual results on RobotCar (Maddern et al., 2017) (1st row), Megadepth (Li and Snavely, 2018) (2nd row) and Hpatches (Balntas et al., 2017) (3rd row) using one homography. We show the source and target in (a), (b). The overlapped images after coarse and fine alignment are in (c) and (d) with zoomed details. The coarse (top) and fine (bottom) flows are in (e).

Figure 5

 5 Figure 5.5: Texture transfer : (a) source, (b) target and (c) texture transferred result.

Figure 5 . 6 :

 56 Figure 5.6: Aligning a group of Internet images from the Medici Fountain, similar to (Shrivastava et al., 2011). We show the source images (a), the average image after coarse (b) and fine alignment (c). The GIF animation can be found in our project webpage http://imagine.enpc.fr/~shenx/RANSAC-Flow/.

Figure 5 . 7 :

 57 Figure 5.7: Aligning pairs of similar artworks from the Brueghel (bru): We show the pairs in (a). The average images without alignment, after coarse and fine alignment are in (b), (c) and (d). The coarse (top) and fine (bottom) flows are in (e).

Figure 5 . 8 :

 58 Figure 5.8: Aligning details discovered by (Shen et al., 2019): (a) sources; average from (Shen et al., 2019) (b), with coarse (c) and fine (d) alignment; The GIF animation can be found in our project webpage http://imagine.enpc.fr/~shenx/RANSAC-Flow/.

Figure 5 . 9 :

 59 Figure5.9: Analyzing copy process from flow. The flow is smooth from the middle to the right one, while it is irregular from the middle to the left one.

Table 3 .

 3 1: Experimental results on Brueghel, IoU > 0.3 for both tasks.

	Method (Feature)	Cosine similarity Discovery score (Equ.3.2)
	ImageNet pre-taining	58.0	54.8
	Context Prediction (Doersch et al., 2015)	58.8	64.29
	Ours (trained on Brueghel)	75.3	76.4
	Ours (trained on LTLL)	65.2	69.95

Table 3 .

 3 2: Discovery with image, classification accuracy on LTLL and retrieval mAP on Oxford5K

	Method	LTLL (%) Oxford (%)
	B. Fernando et al.(Fernando et al., 2015)	56.1	-
	F. Radenović et al.(Radenović et al., 2018)	-	87.8
	ResNet18 max-pool, image level	59.8	14.0
	ResNet18 + discovery	80.9	85.0
	Ours (trained LTLL + discovery)	88.5	83.6
	Ours (trained Oxford + discovery)	85.6	85.7

Table 4 .

 4 2: Image-based localization on Tokyo 24/7

Table 4 .

 4 4: Co-segmentation on Internet[START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF]. We report pixel level precision P and Jaccard index J

	Method	Airplane P J	P	Car	J	Horse P	J	P	Avg	J
	DOCS (Li et al., 2018) *	0.946 0.64 0.940 0.83 0.914 0.65 0.933 0.70
	Sun et al.

Table 5 .

 5 2: Sparse correspondences evaluation on RobotCar

https://www.google.com/imghp?hl=fr

https://www.google.com/imghp?hl=fr

https://github.com/XiSHEN0220

http://imagine.enpc.fr/~shenx/ArtMiner/visualRes/brueghel/brueghel.html

Acknowledgments

Code & Project page : http://imagine.enpc.fr/~shenx/SSR/ In Conference on Neural Information Processing Systems (NeurIPS), 2021. • Yuan Yuan, Lyu Yueming, Xi Shen, Tsang Ivor W and Yeung Dit-Yan. Marginalized Average Attentional Network for Weakly-supervised Learning. Code : https://github.com/yyuanad/MAAN In International Conference on Learning Representations (ICLR), 2019. • Shell Xu Hu, Pablo Moreno, Yang Xiao, Xi Shen, Guillaume Obozinski, Neil Lawrence, and Andreas Damianou. Empirical Bayes Transductive Meta-learning with Synthetic Gradients. Code : https://github.com/hushell/sib_meta_learn In International Conference on Learning Representations (ICLR), 2020.

Training data generation by segment swapping

We generate training pairs using the COCO dataset [START_REF] Lin | Microsoft coco: Common objects in context[END_REF]. We first sample a source image, from which we extract one or two objects. We then build the target image by applying geometric transformations to the objects and blending them into a random background image using Poisson blending [START_REF] Pérez | Poisson image editing[END_REF]. The geometric transformations include rotation, translation, scaling, and thin-plate spline (TPS). A style augmentation is then performed on both the source and target images using an AdaIN [START_REF] Huang | Arbitrary style transfer in real-time with adaptive instance normalization[END_REF] model trained on the Brueghel dataset (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]. We provide more examples of training samples in the project page.

Training pairs generation. We generate training pairs using images from the COCO dataset [START_REF] Lin | Microsoft coco: Common objects in context[END_REF]. We first sample a source image, from which we extract one or two segments (as explained below). We then build the target image by applying geometric transformations to the objects and blending them into a random background image using Poisson blending [START_REF] Pérez | Poisson image editing[END_REF]. The geometric transformations include rotation, translation, scaling, and thin-plate spline (TPS). A style augmentation is then performed on both the source and target images using an AdaIN [START_REF] Huang | Arbitrary style transfer in real-time with adaptive instance normalization[END_REF] model trained on the Brueghel dataset (bru; [START_REF] Shen | Discovering visual patterns in art collections with spatially-consistent feature learning[END_REF]. An example of training pair can be seen in Fig. 4.1a and we provide more examples of training samples in the project page https: //imagine.enpc.fr/~shenx/SegSwap/.

Segments definition. The simplest way to define segments for our data generation process is to use the instance annotations from COCO [START_REF] Lin | Microsoft coco: Common objects in context[END_REF]. We compare this approach to a completely unsupervised segment extraction, which we defined using the following strategy:

(1) given an image, we compute bounding box proposals via the Selective Search (Uijlings et al., 2013); Table 5.1: Dense correspondences evaluation on KITTI 2015 (Menze and Geiger, 2015a) and Hpatches [START_REF] Balntas | Hpatches: A benchmark and evaluation of handcrafted and learned local descriptors[END_REF]. We report the AEE (Average Endpoint Error) and Fl-all (Ratio of pixels where flow estimate is wrong by both 3 pixels and ≥ 5%). The computational time for EpicFlow and FlowField is 16s and 23s respectively, while our approach takes 4s. [START_REF] Revaud | Deepmatching: Hierarchical deformable dense matching[END_REF][START_REF] Melekhov | Dgc-net: Dense geometric correspondence network[END_REF] ----5.84 4.63 12.43 12.17 22.55 DSTFlow [START_REF] Ren | Unsupervised deep learning for optical flow estimation[END_REF] 6.96 16.79 -39 -----GeoNet [START_REF] Yin | Geonet: Unsupervised learning of dense depth, optical flow and camera pose[END_REF] 6.77 10.81 -------EpicFlow [START_REF] Revaud | Epicflow: Edge-preserving interpolation of correspondences for optical flow[END_REF][START_REF] Yin | Geonet: Unsupervised learning of dense depth, optical flow and camera pose[END_REF] 4 the 20k image pairs from the MegaDepth. For fine-tuning on the target dataset, we used a learning rate of 2e-4 for another 10K iterations.

Experiments

In this section, we evaluate our approach in terms of resulting correspondences (Sec. 5.4.1), downstream tasks (Sec 5.4.2), applications to texture transfer and artwork analysis (Sec. 5.4.3) as well as analysis of hyper-parameters in the objective function 5.1 (Sec. 5.4.4). We provide more visual results at http://imagine.