C9 B Delezoide

F Precioso

P Gosselin

M Redi

B Merialdo

L Granjon

D Pellerin

M Rombaut

H Jégou

R Vieux

A Bugeau

B Mansencal

J Benois-Pineau

H Boujut

S Ayache

B Safadi

F Thollard

G Quénot

H Bredin

M Cord

A Benoît

Words for Object Recognition -International Conference on Multimedia Modeling

Résumé des activités de recherche

Ce chapitre décrit l'ensemble de mes activités de recherche depuis l'obtention de mon doctorat en 2007. Ces activités s'articulent autour de trois axes: l'estimation de données manquantes, la segmentation et le suivi d'objets, le traitement et l'analyse de vidéos pour les sciences humaines et sociales. Les chapitres suivants détailleront plus en détail le premier axe qui constitue ma thématique de recherche principale.

I -Estimation de données manquantes

Ma thématique de recherche principale concerne l'estimation de données manquantes à des fins de restauration d'images et vidéos ou de fusion d'informations multi-modales.

I.1 -Inpainting d'images et de vidéos

Ces recherches ont débuté lors de mon post-doctorat au sein de la fondation Barcelona Media de novembre 2007 à juin 2010 dans le cadre du projet espagnol i3media. Ce projet regroupant de nombreux partenaires universitaires et industriels, avait pour objectif la création et la gestion automatique de contenus audiovisuels intelligents. Plus précisément mon post-doctorat, encadré par M. Bertalmìo et V. Caselles, Pr Université Pompeu Fabra, Barcelone, traitait du problème de l'inpainting: étant donnée une image dégradée, il s'agit de reconstruire les zones abîmées de cette image de telle sorte que l'image finale ait l'air naturelle.

Inpainting d'images

Les méthodes de l'état de l'art peuvent être décomposées en deux catégories principales. Les méthodes de la première catégorie, communément appelées méthodes basées-patchs ou à patchs, reposent sur la comparaison de petites zones carrés de l'images. Plus précisément, elles recherchent dans les zones non dégradées de l'image la couleur de substitution des pixels dégradés, en fonction de leur voisinage (section 1.3). Ces méthodes s'adaptent très bien à des régions texturées (eau, herbe, sable ...) mais ne permettent pas vii Résumé des activités de recherche de bien reconstruire les structures d'une image, c'est-à-dire les forts contours. La deuxième catégorie, qui a des propriétés inverses, regroupe les méthodes dites géométriques. Leur principe est de diffuser les couleurs connues sur le bord de la région à reconstruire vers l'intérieur de cette région en suivant les contours extérieurs (section 2.1.1). Aucune des méthodes existantes ne permet cependant de reconstruire correctement tout type d'image.

Inspirés par [START_REF] Bertalmio | Simultaneous structure and texture image inpainting[END_REF], nous avons tout d'abord proposer de combiner ces deux types d'approches en décomposant l'image à restaurer en la somme d'une image de texture et d'une image de structure. L'image de texture est tout d'abord reconstruite par une méthode à patchs tandis que l'image de structure est reconstruite par une méthode géométrique. L'algorithme mis en place donne de bons résultats sur une grande variété d'images mais reste trop dépendant de la méthode géométrique utilisée [START_REF] Bugeau | Combining texture synthesis and diffusion for image inpainting[END_REF]. Nous avons par la suite combiné les deux types d'approches de manière plus directe. Ceci est fait en considérant une fonction d'énergie contenant trois termes principaux, un pour chaque type d'approche et un augmentant la cohérence entre pixels voisins. Cette énergie est minimisée de manière itérative sous un schéma multi-résolution. Cette méthode a permis d'obtenir des résultats encourageants sur un grand nombre d'images (Bugeau et al., 2010a). Elle a été étendue à l'inpainting d'images stéréo dans [START_REF] Hervieu | Stereoscopic Image Inpainting: Distinct Depth Maps and Images Inpainting[END_REF][START_REF] Hervieu | Stereoscopic image inpainting using scene geometry[END_REF].

Inpainting de vidéos

J'ai par la suite étudié le problème d'inpainting de vidéos. La difficulté réside ici dans l'ajout de cohérence temporelle entre les reconstructions successives d'images. Pour que cette reconstruction ait l'air naturelle, il est indispensable de prendre en compte des informations sur le mouvement. Nous avons proposé une méthode basée sur un lissage de Kalman [START_REF] Bugeau | Coherent Background Video Inpainting through Kalman Smoothing along Trajectories[END_REF]. Les observations sont les images de la vidéo complétées une à une par une méthode d'inpainting d'image. Les prédictions sont obtenues en appliquant une méthode d'inpainting géométrique sur le flot optique entre deux frames successives .

I.2 -Colorisation d'images et de vidéos

Depuis 2012, je m'intéresse également à la colorisation d'images, i.e. à l'estimation des canaux de couleur de chaque pixel d'une image en niveaux de gris.

Méthodes à patchs pour la colorisation d'images

Il existe dans la littérature deux approches principales. La première se base sur la diffusion des couleurs : l'utilisateur choisit manuellement la couleur d'un certain nombre de pixels de l'image puis ces couleurs sont automatiquement diffusées aux pixels voisins (e.g. Levin et al., 2004, section 3.1). Cette méthode est limitée à des images simples contenant peu d'objets. Le second type d'approches concerne la colorisation dite par l'exemple. Elle est issue des méthodes de synthèse de texture à patch [START_REF] Efros | Texture Synthesis by Non-parametric Sampling[END_REF]. Il s'agit ainsi de copier dans l'image en niveau de gris les teintes ou chrominances d'une image source en couleur (e.g. Welsh et al., 2002, section 1.4). L'avantage est que, mis à part la sélection de l'image couleur de référence, ces méthodes sont entièrement automatiques. Ces approches par l'exemple reposent sur la comparaison entre les luminances de l'image en niveau de gris et celles de l'image couleur. Cette comparaison est classiquement effectuée en calculant la (dis-)similarité entre le voisinage d'un pixel à coloriser avec l'ensemble ou un sousensemble des patchs de l'image couleur. De nombreuses métriques et descripteurs existent pour comparer des patchs mais aucune étude exhaustive portant sur l'influence de chaque métrique sur les résultats de colorisation n'a été publiée. Une des raisons est qu'il n'existe pas de mesure quantitative adaptée permmettant de valider les résultats de colorisation. Dans ce contexte, en collaboration avec V.-T. Ta, MCF LaBRI/Bordeaux INP, nous avons proposé une méthode permettant de calculer pour chaque pixel la meilleure couleur à lui transférer pour différents descripteurs d'un patch. Chaque pixel a ainsi plusieurs couleurs candidates possibles, une pour chacune des métriques. Dans [START_REF] Bugeau | Patch-based image colorization[END_REF], la sélection de la couleur finale se fait tout simplement en prenant la couleur médiane de l'ensemble des candidats possibles.

Modèles variationnels pour la colorisation d'images et de vidéos basée patch

Nous avons par la suite, en collaboration avec N. Papadakis, CR CNRS/IMB, proposé la sélection automatique du meilleur candidat par une méthode variationnelle permettant l'ajout d'une contrainte spatiale sur la sélection [START_REF] Bugeau | Variational Exemplar-Based Image Colorization[END_REF]. Ces travaux ont été poursuivis dans le cadre de la thèse de Fabien Pierre, dirigée par J.-F. Aujol, Pr Université de Bordeaux/IMB et co-encadrée par V.-T. Ta et moi-même (section 1.4.3). Une étude sur le calcul d'une combinaison linéaire optimale de métriques entre patchs pour la colorisation d'images a tout d'abord été menée [START_REF] Pierre | Combinaison lineaire optimale de metriques pour la colorisation d'images[END_REF]. Il apparait, avec cette méthode, que le choix de la métrique optimale est trop dépendant de l'image à coloriser et qu'une sélection au sein d'un modèle variationnel [START_REF] Bugeau | Variational Exemplar-Based Image Colorization[END_REF] apporte de meilleurs résultats. Nous avons donc poursuivi dans cette direction (chapitre 3). Un défaut majeur des résultats de colorisation existants est qu'ils sont globalement ternes.

Nous avons analysé les raisons et proposés des solutions applicables à l'ensemble des méthodes de l'état-de-l'art. Lors de la colorisation d'images, l'image originale en niveaux de gris est considérée comme un canal de luminance et les couleurs sont créées en modifiant les deux canaux de chrominance. Le résultat luminance/chrominance obtenu est ensuite converti en RGB pour pouvoir être observé. Néanmoins les conversions des espaces de luminance/chrominance vers RGB ne permettent pas toujours de conserver correctement la teinte de l'image colorisée. La première solution que nous avons proposé consiste à travailler directement dans l'image RGB. Le modèle variationnel [START_REF] Bugeau | Variational Exemplar-Based Image Colorization[END_REF] a été modifié de façon à estimer une image RGB tout en respectant la contrainte de luminance (luminance de l'image finale égale aux niveaux de gris de l'image initiale) [START_REF] Pierre | Exemplarbased colorization in RGB color space[END_REF]. Dans cette méthode, la projection de la couleur RGB estimée sous contrainte de luminance est réalisée avec une projection orthogonale. Malheureusement cette projection ne conserve pas correctement la teinte de la couleur RGB initiale. Une étude approfondie des espaces de couleur et de leurs propriétés géométriques nous a amené à proposer une projection oblique menant à des résultats de colorisation faisant maintenant parti de l'état de l'art (Pierre et al., 2015c;Pierre et al., 2015a). Similairement aux travaux sur l'inpainting, nous avons également travaillé sur la combinaison des deux grandes catégories d'approches de colorisation d'images. Nous avons ainsi unifié dans un seul modèle les approches par l'exemple et les approches basées sur la diffusion de couleurs marquées par un utilisateur (Pierre et al., 2014a;Pierre et al., 2015a). Ces travaux ont fait l'objet d'un dépôt logiciel appelé "Colociel". L'extension de ces travaux (section 3.2.1) à la colorisation de vidéos, obtenue avec l'ajout dans nos fonctionnelles d'un terme encourageant la cohérence temporelle sur les couleurs candidates, a enfin été proposée (Pierre et al., 2017b).

Application au rehaussement de contraste

Les travaux sur les espaces couleurs et sur la préservation de la teinte ont été étendus au problème de réhaussement de contraste suite à une collaboration avec G. Steidl, Pr. université de Kaiserslautern, Allemagne. La mesure du contraste est ici définie comme une moyenne pondérée des différences locales entre pixels voisins. Le réhaussement est alors obtenu par minimisation d'un modèle variationnel augmentant cette mesure de contraste par un facteur donné tout en préservant la teinte de l'image initiale (Pierre et al., 2017a;[START_REF] Pierre | Hue-preserving perceptual contrast enhancement[END_REF] (figure 1).

x Résumé des activités de recherche

Image initiale Image rehaussée

Figure 1: Résultats de rehaussement de contraste (Pierre et al., 2017a).

I.3 -Enrichissement et complétion de nuages de points LIDAR

La dernière application entamée dans le cadre de mes recherches sur l'estimation de données manquantes concerne la densification de nuages de points LiDAR. Ces travaux sont réalisés en collaboration avec J.-F. Aujol et M. Brédif, chercheur à l'IGN. L'équipe MATIS de l'IGN a développé un système de cartographie mobile (MMS), équipé de détecteur laser (LiDAR), de capteurs optiques, d'un GPS et d'une centrale inertielle. L'objectif à terme est de construire des cartes 3D extrêmement précises des zones urbaines. Les acquisitions LiDAR fournissent des informations de profondeur et de réflectance permettant la reconstruction d'un nuage de points 3D éparse de l'environnement, contenant des millions de points par minute d'acquisition. En complément, les capteurs optiques apportent de nombreuses images HD avec différents angles de vue.

Enrichissement des images optiques

Dans le cadre du post-doctorat de Marco Bevilacqua, nous nous sommes intéressés au couplage des nuages de points LiDAR avec les images optiques. Plus précisément, nous avons travaillé sur l'enrichissement des images optiques en leur ajoutant un canal de profondeur u et de réflectance r provenant des points LiDAR préalablement projetés sur les coordonnées des pixels de l'image optique (figure 2). Les nuages de points LiDAR (r S et u S ) n'étant pas denses et ayant des coordonnées sous pixelliques dans l'image, l'estimation de la profondeur et de la réflectance en chaque pixel n'est pas directe. Nous avons donc proposé un modèle variationnel encourageant les contours de la reconstruction LiDAR à correspondre aux contours de l'image et s'assurant de la cohérence spatiale des valeurs de profondeurs [START_REF] Bevilacqua | Visibility estimation and joint inpainting of lidar depth maps[END_REF] et de réflectances [START_REF] Bevilacqua | Joint inpainting of depth and reflectance with visibility estimation[END_REF]. Pour cela une carte de visibilité dans l'image v de chacun des points projetés est estimée.

Complétion de nuages de points LiDAR

Dans le cadre de la thèse de Pierre Biasutti débutée en septembre 2016, nous nous sommes intéressés à la suppression d'objets non permanents de la scène tels que des objets en xi Résumé des activités de recherche Figure 2: Méthode d'enrichissement des images optiques à partir des données de réflectance et de profondeur issues du capteur LiDAR [START_REF] Bevilacqua | Joint inpainting of depth and reflectance with visibility estimation[END_REF].

mouvement ou des voitures garées. Pour cela nous avons proposé une représentation 2D en topologie capteur du nuage de points 3D. La segmentation de l'histogramme de cette nouvelle image permet ensuite d'extraire semi-automatiquement le masque des objets à supprimer. Une méthode d'inpainting géométrique a alors été proposée pour estimer la profondeur des zones occultées [START_REF] Biasutti | Disocclusion of 3D LiDAR point clouds using range images[END_REF]Biasutti et al., 2018, section 2.1.2).

Création d'orthoimages à partir de points LiDAR

La complétion de nuages de points LiDAR peut également s'appliquer à la création d'orthoimages. Une orthoimage est une image de la surface terrestre exempte de toute distorsion, généralement acquise par des vecteurs satellites ou aériens. Dans le cadre du stage de Master 2 de Pierre Biasutti, nous avons proposé une méthode générant une orthoimage de réflectance et de hauteur à très grande résolution (1cm) à partir des points LiDAR fournis par un système de cartographie mobile. La projection verticale (sur le sol) du nuage de points LiDAR sur une grille de pixels 2D étant éparse, des algorithmes d'inpainting sont appliqués afin d'obtenir une reconstruction dense des cartes de hauteur et de réflectance [START_REF] Biasutti | Diffusion anisotrope et inpainting d'orthophotographies LiDAR mobile[END_REF]Biasutti et al., 2017a, section 2.1.3).

II -Segmentation et suivi d'objets

Depuis mon doctorat, je m'intéresse également à la segmentation et au suivi d'objets. Dans l'ensemble de ces travaux, ce problème est vue comme un problème d'étiquetage, l'objectif étant d'attribuer à chaque pixel une étiquette "fond" ou "objet". [START_REF] Bugeau | Joint Tracking and Segmentation of Objects using Graph Cuts[END_REF]Bugeau et al., 2008a;[START_REF] Bugeau | Track and Cut: Simultaneous Tracking and Segmentation of Multiple Objects with Graph Cuts[END_REF]. Cette méthode a néanmoins le défaut de nécessiter deux étapes. J'ai poursuivi mes recherches sur ce sujet et mis en place, en collaboration avec V. Caselles et N. Papadakis, un algorithme de suivi ne requérant qu'une seule minimisation pour tous les objet et étant capable de bien gérer les occultations partielles et globales. Pour cela un objet est divisé en deux parties : une région visible et une région occultée. Elles sont toutes deux suivies conjointement de part la minimisation d'une seule fonction d'énergie par un algorithme de coupe minimale/flot maximal (Papadakis et al., 2011, figure 3).

Application à l'indexation d'images

Ces recherches sur la segmentation par coupe de graphes ont été appliquées à l'indexation d'images avec une méthode reposant sur les sacs de descripteurs et les sacs de mots (Bag of Features and Bag of Words). Comme dans le cadre de la recherche textuelle, le principe des sacs de mots consiste à représenter une image par une distribution discrète des "mots visuels" qui la composent. Pour cela, des descripteurs visuels sont extraits localement des images puis quantifiés à l'aide d'un dictionnaire visuel obtenu par classification Kmeans. Ce dernier permet d'associer à chaque image un histogramme de ses descripteurs. Ces méthodes ont le défaut de ne pas tenir compte de l'information spatiale des images, ou plus précisément de la position dans l'image de chacun des descripteurs intervenant dans la construction de l'histogramme. Dans [START_REF] Karaman | Multi-layer Local Graph Words for Object Recognition[END_REF][START_REF] Benois-Pineau | Visual Indexing and Retrieval[END_REF], nous avons donc proposé d'intégrer l'information spatiale explicitement au sein des descripteurs, c'est-à-dire avant la création de l'histogramme. Ces descripteurs sont des graphes multi-échelle obtenus par triangulation de Delaunay appliquées aux points SURF [START_REF] Bay | Surf: Speeded up robust features[END_REF] de l'image. Afin d'ajouter une information spatiale au moment de la construction de l'histogramme de mots visuels, l'utilisation de pyramides spatiales a été proposé dans la littérature [START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF]. Cette méthode, qui a largement contribué aux avancées dans le domaine de la recherche d'images, n'est néanmoins pas invariante aux transformations affines des images. Dans le cadre de la thèse de Yi Ren, co-encadrée par J. Benois-Pineau, Pr LaBRI/Université de Bordeaux, nous avons travaillé sur le découpage de l'image en régions cohérentes, chaque région étant ensuite représentée par son propre histogramme de mots visuels. L'histogramme global d'une image, appelé "Bag-of-Bags of Words", est alors obtenu par concaténation des histogrammes de chaque région. Pour segmenter les images en régions cohérentes, nous avons proposés des énergies ensuite minimisées par un algorithme de coupe minimale/flot maximal (Y. [START_REF] Ren | Bag-of-bags of words irregular graph pyramids vs spatial pyramid matching for image retrieval[END_REF]Y. Ren et al., 2014a, xiv Résumé des activités de recherche figure 4).

Figure 4: Méthode pour la création des "Bag-of-Bags of Words" (Y. [START_REF] Ren | Bag-of-bags of words irregular graph pyramids vs spatial pyramid matching for image retrieval[END_REF]Y. Ren et al., 2014a).

II.2 -Segmentation par étiquetage de superpixels

Un autre travail de recherche sur la segmentation d'une image à partir d'une base d'images étiquetées à été proposé en collaboration avec R. Giraud, doctorant LaBRI, V.-T. Ta, N. Papadakis et P. Coupé, CR CNRS/LaBRI. Ce travail repose sur la décomposition de l'image en superpixels (petites zones connexes et de couleur homogène de l'image) avec la méthode SLIC [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF]. En introduisant un algorithme rapide et robuste de mise en correspondances de "patch de superpixels" (appelés superpatch), nous sommes capables de classifier chacun des superpixels d'une image à segmenter [START_REF] Giraud | SuperPatch-Match: an Algorithm for Robust Correspondences of Superpixel Patches[END_REF], figure 5).

III -Traitement et analyse de vidéos pour les sciences humaines et sociales

Ma troisième thématique de recherche est multidisciplinaire et repose sur plusieurs collaborations avec des chercheurs de sciences cognitiques et de sciences humaines et sociales. L'ensemble de ces travaux sur l'anonymisation fine de visages dans les image fixes ont été publiés dans [START_REF] Letournel | Face de-identification with expressions preservation[END_REF].

III.1 -Anonymisation fine de visages

III.2 -Caractérisation visuelle des affects sociaux

En parallèle de ces travaux, j'ai travaillé sur la caractérisation visuelle des affects sociaux. Ce dernier projet a été réalisé de part l'encadrement du post-doctorant Zuheng Ming et en collaboration avec T. [START_REF] Ming | Facial Action Units Intensity Estimation by the Fusion of Features with Multi-kernel Support Vector Machine[END_REF]. Ces recherches nous ont amené à établir une collaboration avec T. Nishida, Université de Kyoto, Japon, avec qui nous avons défini un scénario pour l'acquisition de vidéos de ces attitudes sur plusieurs personnes placées simultanément dans des environnements immersifs en réseau [START_REF] Nishida | Synthetic Evidential Study as Augmented Collective Thought Process[END_REF].

Introduction

The purpose of image post-production is to generate a modified image from an original one by recovering or adding missing information to the image in order to improve its visual quality or modify its style. It involves processes such as image restoration (i.e. denoising or deblurring), contrast or color enhancement, loss data completion, stylization, etc. Digital data post-production is a common problem in any field involving signal processing and applications may thus range from computational photography to medical imaging or satellite imaging.

Image post-production is generally an ill-posed problem. Indeed recovering missing or damaged data cannot be done without any prior assumption. Inspired by the studies made on the visual human system, many methods rely on the predictability or redundancy of images. The notion of redundancy in natural images appeared more than fifty years ago in the context of human vision [START_REF] Attneave | Some informational aspects of visual perception[END_REF][START_REF] Barlow | Possible Principles Underlying the Transformations of Sensory Messages[END_REF]. According to these studies, the visual system seeks to represent an image with the smallest possible number of information. This is made possible as there exist statistical dependencies across space in any natural image. In order to be efficient, the human visual system reduces these redundancies by removing the statistical dependencies.

Different types of redundancies are present in natural images, each of them leading to different approaches for automatic image processing. For details on natural image statistics we refer the reader to [START_REF] Simoncelli | Natural image statistics and neural representation[END_REF]. In particular, we can differentiate spatial and spectral redundancy. Local spatial redundancy means that there is a strong correlation between neighboring pixels, i.e. predictability in local image neighborhood. Spectral redundancies means that there is a strong correlation among the colors or the spectrum within an image. Another important type of redundancy, which will be at the core of this document, corresponds to the self-similarity principle, meaning that an image contains a lot of repetitions of local information (see figure 0.1).

Image redundancy is exploited in many image processing and analysis tasks. For image and video compression, it is only natural to compress the data by removing spatial and temporal redundancy. For denoising, today most powerful methods replace noisy areas by averaging the values of other similar areas in the same image, thus exploiting the self-similarity principle. In the context of image retrieval, object detection or action recognition, the goal is to retrieve images or areas containing similar representations. Methods usually rely on local spatial redundancy but the self-similarity principle also happens to be useful [START_REF] Shechtman | Matching Local Self-Similarities across Images and Videos[END_REF].

In the field of image post-production, methods exploiting the self-similarity principle are often referred to as patch-based approaches or non-local approaches. The assumption lying behind is that, similar to the human visual system, a computer is also able to predict missing data exploiting the visual redundancy present in a single image or across several similar images. All the works in this trend are inspired by Shannon's work on modeling the English language. In [START_REF] Shannon | A Mathematical Theory of Communication[END_REF], a Markov model is used to generate an English text by computing the probability distributions of each letter given the previous ones in a large English text. Then, starting from a given letter (the seed), successive letters are found by sampling this Markov chain. This idea has first been extended to images in [START_REF] Efros | Texture Synthesis by Non-parametric Sampling[END_REF] for the purpose of texture synthesis. The texture is modeled as a Markov Random Field assuming that the probability distribution of brightness values for one pixel given the brightness values of its spatial neighborhood is independent from the rest of the image. The neighborhood is a square window called a patch. As we will see all along this document this work is at the origin of many others in various applications. A non exhaustive list of improvements that have been proposed in the literature is: study of similarities between patches, higher-level representation of patches, order in which the pixels (seeds) are sampled, introduction of geometric constraints for better sampling, use of non square window. Despite these various improvements, most patch-based methods remain one-path greedy algorithm: pixels are processed one after the others without being further modified. This property leads to the well known growing garbage problem: errors are propagating from one pixel to the next. The only way to prevent this issue Introduction from happening is to consider multi-pass (or iterative) algorithms. The difficulty becomes to demonstrate the convergence of such algorithm. In order to better understand the behavior and convergence of the algorithms, problems are generally modeled as the minimization of energy functions or solutions of partial derivative equations (PDE). Several energy functions will presented and discussed in this document.

While we will mention other applications of image post-production we will concentrate on image inpainting and image colorization. Inpainting aims at reconstructing a part of an image in a way that is not (easily) detectable by an ordinary observer. Image colorization consists in turning a grayscale image into a color one that must seems natural.

Additionally to these two applications that concern the restoration and retrieval of natural images, we will also mention results concerning the completion of laser detection and ranging (LiDAR) clouds of points for orthoimages production and dense depth maps generation.

In chapter 1 we will see in details how the initial texture synthesis approach has been extended for the tackled applications. Chapters 2 and 3 study several models to solve the inpainting and colorization problems with non-greedy algorithms. Finally the last chapter concludes this presentation and opens several new perspectives of research.

Chapter 1

Exploiting the self-similarity principle for image post-production

Every natural image contains redundant information. The human visual system is able to use the redundant information within an image or from previously memorized images in order to predict the content of a missing part of the scene. In this chapter we will see how this behavior translates into algorithm for recovering missing data in the context of image post-production. We will concentrate on patch-based methods that consider the selfsimilarity principle, assuming that an image has a lot of repetitions of local information.

While there is no clear definition of self-similarity, it is generally understood as follows: if any small template in an image can be approximated by one or several other small templates in that same image, then the image is self-similar. The small templates are generally considered to be small square windows, also called patches, but other less regular shapes may also be considered. In both cases, they are small image parts that capture local color statistics, texture and structure information.

In the context of image restoration and enhancement, the exploitation of patch redundancy started with the seminal work by [START_REF] Efros | Texture Synthesis by Non-parametric Sampling[END_REF], for texture synthesis. We will detail this method in section 1.1, and the metrics that can be used to compare patches in section 1.2. This work is at the origin of a huge number of research for various applications. A good survey for paper before 2009 is L.-Y. [START_REF] Wei | State of the Art in Examplebased Texture Synthesis[END_REF], and for after is [START_REF] Barnes | A survey of the state-of-the-art in patch-based synthesis[END_REF] Let us briefly mention some applications here, without going into details: denoising (with the famous NonLocal-Means algorithm from [START_REF] Buades | A non-local algorithm for image denoising[END_REF], super-resolution [START_REF] Freeman | Example-based super-resolution[END_REF], stereo-matching [START_REF] Scharstein | A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms[END_REF]Lu et al., 2013), stylization [START_REF] Bénard | Stylizing Animation by Example[END_REF], style transfer [START_REF] Elad | Style Transfer Via Texture Synthesis[END_REF][START_REF] Frigo | Split and Match: Example-Based Adaptive Patch Sampling for Unsupervised Style Transfer[END_REF], segmentation and labeling [START_REF] Coupé | Patch-based segmentation using expert priors: Application to hippocampus and ventricle segmentation[END_REF], optical flow estimation [START_REF] Fortun | Aggregation of local parametric candidates with exemplar-based occlusion handling for optical flow[END_REF], stereoscopic image inpainting [START_REF] Hervieu | Stereoscopic Image Inpainting: Distinct Depth Maps and Images Inpainting[END_REF][START_REF] Hervieu | Stereoscopic image inpainting using scene geometry[END_REF] etc.

PATCH-BASED TEXTURE SYNTHESIS

In this chapter, we will concentrate on applications to image inpainting (section 1.3) and colorization of grayscale images (section 1.4).

Patch-based texture synthesis

The seminal paper [START_REF] Efros | Texture Synthesis by Non-parametric Sampling[END_REF] presented a simple yet effective patch-based texture synthesis method. The objective is to generate a new texture image u : Ω → R 3 from a small texture sample u S : Ω S → R 3 (figure 1.1). The texture is modeled as a Markov Random Field assuming that the probability distribution of brightness values for one pixel given the values of its spatial neighborhood is independent from the rest of the image. The neighborhood is a square window (patch) around the pixel and its size is a global parameter of the algorithm. The input of the algorithm is a set of sample image patches (all patches entirely belonging to the sample texture domain Ω S ). The task is to select an appropriate patch within this set for each of the unknown pixels so as to predict their value. This is done by computing a distance between the known neighborhood of an unknown pixel and each of the sample patches.

The unknown pixel is filled-in with the value of the center of the most appropriate patch.

In the following, let u : Ω → R 3 be a color image (or u : Ω → R an intensity image) and u S the sample grayscale or color image. We denote as Ψ s (p) a patch centered at pixel p = (x, y), of size N = (2s + 1) × (2s + 1) such that

Ψ s (p) = {p + k, k ∈ P s } with P s = {(i, j), i = -s • • • s, j = -s • • • s}.
For the sake of clarity we will equivalently CHAPTER 1. EXPLOITING THE SELF-SIMILARITY PRINCIPLE FOR IMAGE POST-PRODUCTION use the notation Ψ s (p) and Ψ(p). We also denote as

Ψ u s (p) = (u(p 1 ), • • • , u(p N )) , p i ∈ Ψ s (p) (1.1)
the vector of image values within the patch Ψ s (p).

As described in [START_REF] Demanet | Image Inpainting by Correspondence Maps: a Deterministic Approach[END_REF], the texture synthesis problem as just described is akin to finding the correspondence map (also called nearest neighbor field, NNF, in [START_REF] Barnes | PatchMatch: a randomized correspondence algorithm for structural image editing[END_REF], ϕ : Ω → Ω S , that associates each pixel of the target domain Ω of the image to a pixel from the sample domain Ω S such that

ϕ(p) = argmin q∈Ω S d (Ψ u s (p), Ψ u S s (q)) (1.2)
where d is a distance between the image value of patches Ψ s (p) and Ψ s (q) centered at p and q respectively. Details on possible distances are discussed in section 1.2.

There have been many improvements to the initial patch-based method from [START_REF] Efros | Texture Synthesis by Non-parametric Sampling[END_REF]. We here briefly describe some common tools which are later used in this document.

Patch-wise approaches

The pixel-wise texture synthesis approach as just described is time consuming as synthesizing each pixel requires an exhaustive search among all pixels from the sample image. To speed up the process and better reproduce the input local structures, patch-wise methods synthesize entire patches instead of pixels [START_REF] Efros | Image Quilting for Texture Synthesis and Transfer[END_REF][START_REF] Kwatra | Graphcut Textures: Image and Video Synthesis Using Graph Cuts[END_REF]Criminisi et al., 2004;[START_REF] Lefebvre | Parallel controllable texture synthesis[END_REF]. The common default is the increasing amount of garbage regions and the necessity to add a blending stage to remove discontinuities between adjacent pacth copies.

Multi-resolution scheme Another trend for accelerating and improving texture synthesis algorithm is to incorporate it into a multi-resolution scheme. The unknown image is iteratively approximated using some guidance from coarse to fine levels (L. [START_REF] Wei | Fast texture synthesis using tree-structured vector quantization[END_REF][START_REF] Drori | Fragment-based image completion[END_REF].

Approximate Nearest Neighbor (ANN) Over the years, several other strategies have been proposed to accelerate directly pixel-wise approaches, mostly leading to approximate nearest neighbor search (ANN). Note that all the methods in this trend have been extended to a multi-resolution scheme. While it is possible to accelerate exact nearest neighbor algorithms by avoiding any useless calculation [START_REF] Xiao | Fast Exact Nearest Patch Matching for Patch-Based Image Editing and Processing[END_REF], the search remains quite inefficient in comparison to ANN. Among ANN methods we can 1.2. MEASURING SIMILARITY BETWEEN PATCHES mention tree-based techniques (L. [START_REF] Wei | Fast texture synthesis using tree-structured vector quantization[END_REF][START_REF] Di Blasi | Fast colorization of gray images[END_REF][START_REF] Olonetsky | TreeCANN -k-d Tree Coherence Approximate Nearest Neighbor Algorithm[END_REF][START_REF] He | Computing nearest-neighbor fields via Propagation-Assisted KD-Trees[END_REF] or methods taking advantage of spatial coherence. These latter reduce the search space making the assumption that neighbor pixels in the output are likely to have neighbor correspondences in the input [START_REF] Ashikhmin | Synthesizing Natural Textures[END_REF][START_REF] Tong | Synthesis of bidirectional texture functions on arbitrary surfaces[END_REF][START_REF] Busto | Instant Texture Synthesis by Numbers[END_REF]. The first such work [START_REF] Ashikhmin | Synthesizing Natural Textures[END_REF] proposed to perform texture synthesis by looking for the best match for pixel p ∈ Ω not in all Ω S but only among the set {ϕ(p + k) -k} of shifted candidates. The idea, as stated by the author, was to increase performance by not "starting the search process from scratch at each new pixel".

In practice it also imposes a certain coherence in the mapping function ϕ which clearly improves the visual quality of many synthesis results. This approach was extended to k-coherence by [START_REF] Tong | Synthesis of bidirectional texture functions on arbitrary surfaces[END_REF] Exploiting spatial coherence, [START_REF] Barnes | PatchMatch: a randomized correspondence algorithm for structural image editing[END_REF] proposed the now famous approximate nearest neighbor algorithm called patchmatch. The assumption made is that the correspondence map is most likely to be piece-wise constant. The algorithm has three steps: 1) random initialization of the correspondane map 2) propagation exploiting spatial coherence 3) random search to avoid getting stuck into local minima. Its convergence rate to exact NN has been studied in [START_REF] Arias | Analysis of a Variational Framework for Exemplar-Based Image Inpainting[END_REF].

Measuring similarity between patches

The underlying questions behind any patch-based methods are: i) how to find a discriminant and compact representation of the local statistics lying within a patch? ii) how to measure the similarity between these representations? In this section we only focus on the comparison between patches of pixels but other metrics have been designed for more complex templates. For instance, in [START_REF] Giraud | SuperPatch-Match: an Algorithm for Robust Correspondences of Superpixel Patches[END_REF], we have designed metrics for patches of superpixels.

Patch-based descriptors

Many representations of patches have been proposed in the literature. Our goal here is not to make an exhaustive list but to mention the most famous ones and the ones used later in this document. It is important to highlight that the use of these representations highly depends on the targeted application, either we need to find color, texture or structure similarity.

The first low-level feature is the raw pixel intensity or color values themselves. This is the most widely used representation in patch-based methods.

In order to capture local color statistics, the mean and standard deviations of pixel values CHAPTER 1. EXPLOITING THE SELF-SIMILARITY PRINCIPLE FOR IMAGE POST-PRODUCTION within the patch is a very compact representation, though not highly discriminant. Higher dimensional representation are the intensity or color histograms, normalized histograms or cumulative histograms.

Several representations capturing frequencies of important structures can be obtained in the Fourier domain: Discrete Fourier Transform (DFT), Discrete Cosine Transfrom (DCT) for instance. The DFT is combined to other representation for image colorization in [START_REF] Bugeau | Patch-based image colorization[END_REF]. In the same trend, Gabor filters have been used for image colorization in [START_REF] Chia | Semantic Colorization with Internet Images[END_REF] and [START_REF] Gupta | Image colorization using similar images[END_REF].

A simple way to capture intensity or color variation within a template is to rely on image derivatives: intensity gradients and/or magnitude of gradients. Use of these features for image inpainting can be found in (Y. [START_REF] Liu | Exemplar-Based Image Inpainting Using Multiscale Graph Cuts[END_REF] and [START_REF] Newson | Video inpainting of complex scenes[END_REF]. Higher order derivatives can also be considered. For instance region covariance [START_REF] Tuzel | Region Covariance: A Fast Descriptor for Detection and Classification[END_REF] computed over the first and second intensity derivatives is used for colorization and color transfer in [START_REF] Arbelot | Automatic Texture Guided Color Transfer and Colorization[END_REF].

Finally, when measuring similarity across different images, it is often necessary to rely on scale, orientation and illumination invariant representations. Well known descriptors in this trend, built from gradient orientations, are SIFT [START_REF] Lowe | Patch Match Filter: Efficient Edge-Aware Filtering Meets Randomized Search for Fast Correspondence Field Estimation[END_REF], SURF [START_REF] Bay | Surf: Speeded up robust features[END_REF] or DAISY [START_REF] Tola | A fast local descriptor for dense matching[END_REF]. These descriptors are well suited for matching highly structured image areas such as corners or keypoints. SIFT has been used for patch-based denoising [START_REF] Lou | Nonlocal Similarity Image Filtering[END_REF] and colorization [START_REF] Chia | Semantic Colorization with Internet Images[END_REF], and DAISY for image colorization [START_REF] Cheng | Deep colorization[END_REF].

None of these representations is well suited for all possible types of textured, structured or uniform areas of natural images. This is mostly why, in the context of image restoration, most methods rely directly on raw pixel values.

In the following, the patch representation computed on Ψ s (p) is denoted by Ψ f s (p) and is stored as a vector of size N :

Ψ f s (p) = (f (p 1 ), • • • f (p N )) , p i ∈ Ψ s (p). (1.3)
For instance in case the representation are the raw pixels themselves, we have

Ψ f s (p) = Ψ u s (p) = (u(p 1 ), • • • u(p N )) , p i ∈ Ψ s (p).

Similarity metrics

Many metrics exist to compute the similarity between patch representations. The most widely used for image restoration is the squared ℓ 2 norm of the difference between patches, 1.2. MEASURING SIMILARITY BETWEEN PATCHES called sum of squared differences (SSD). For two pixels p and q, it is defined as:

d SSD (Ψ u (p), Ψ u (q)) = k∈Ps u(p + k) -u(q + k) 2 .
A Gaussian weighted version, d SSDG is also sometimes considered (as in [START_REF] Efros | Texture Synthesis by Non-parametric Sampling[END_REF] in order to give more importance to central pixels. Other classical measures include the ℓ 1 norm of the difference between patches, known as the sum of absolute differences (SAD), or zero normalized cross-correlation.

Before going any further, let us analyze the influence of the SSD on an inpainting example. Figure 1.2, taken from (Bugeau et al., 2010a), demonstrates the limitation of the SSD when comparing textures. The textured patch P 0 is, in its overall appearance, very similar to P 2 . But, pixel-wise, as the SSD is computed, the difference between pixels at the same location in both patches is greater than the difference between the pixels in P 0 and the average value of P 0 . Think of the difference between two sinusoids of average µ which are 180 • out of phase: although they look exactly the same, their SSD is greater than the SSD between either sinusoid and the constant function of value µ. This is why patch P 4 , which is rather uniform and does not resemble at all P 0 , is more similar in terms of SSD to P 0 than P 2 is to P 0 . This problem was later discussed in [START_REF] Newson | On Video Completion: Line Scratch Detection in Films and Video Inpainting of Complex Scenes[END_REF] with the following explanation. Assume two patches Q 1 and Q 2 made of i.i.d. pixels with a normal distribution N(µ, σ 2 ) and a constant patch Q 3 , with the constant equal to µ. The SSD patch distance between Q 1 and Q 2 follows a chi-square distribution χ 2 (0, 2σ 2 ) while the one between Q 1 and Q 3 follows χ 2 (0, σ 2 ). Patch Q 3 is therefore more likely to be chosen as the best candidate for patch Q 1 . To cope with this problem, in (Bugeau et al., 2010a), we have defined a new similarity CHAPTER 1. EXPLOITING THE SELF-SIMILARITY PRINCIPLE FOR IMAGE POST-PRODUCTION measure:

d SSDB (Ψ u (p), Ψ u (q)) := 1 N d SSD (Ψ u (p), Ψ u (q)) • d H (Ψ u (p), Ψ u (q)) , (1.4)
where, for a given pair of patches Ψ s (p), Ψ s (q), d H (Ψ u (p), Ψ u (q)) denotes the Hellinger distance:

d H (Ψ u (p), Ψ u (q)) = 1 - B i=1 ρ p (i)ρ q (i), (1.5)
where ρ p , ρ q are the histograms of the image u computed on the patches Ψ u (p), Ψ u (q), respectively, and B is the number of bins of the histograms. The Hellinger distance is a modified version of the Bhattacharyya probability density distance so that it satisfies the triangle inequality. In practice a histogram is computed on each patch by using 8 bins for each color dimension (i.e. 512 bins in case of color images). Let us comment on the rationale behind this choice for d, which combines the SSD and the Hellinger distance.

While the Hellinger distance permits to distinguish a smooth patch from a textured one because they have different distributions, it is rotation invariant and we still need the SSD to permit distinction in that case. As later noticed by [START_REF] Le Meur | Super-Resolution-Based Inpainting[END_REF], when two patches have the same distribution, their distance d SSDB is zero. The authors therefore propose a variant to cope with this limit:

d SSDB (Ψ u (p), Ψ u (q)) := 1 N d SSD (Ψ u (p), Ψ u (q)) • (1 + d H (Ψ u (p), Ψ u (q))) . (1.6)
This metric is also well adapted for patch-based image denoising [START_REF] Ebdelli | Analysis of patch-based similarity metrics: Application to denoising[END_REF].

As mentioned before, we do not wish to draft an extensive list of all existing similarity metrics. Let us however mention that studies for comparing noisy patches, assuming known the noise model, have been conducted [START_REF] Deledalle | How to Compare Noisy Patches? Patch Similarity Beyond Gaussian Noise[END_REF].

As for patch representation, the quality of a similarity metric often depends on the types of data and desired application. This is why most recent papers for image inpainting and image colorization prefer to rely on several types of patch representations thus defining new metrics to compute similarity between patches. We will discuss this matter later in this document. [START_REF] Bertalmio | Image Inpainting[END_REF]. In the art domain, it is also called retouching. The problem was brought to the image processing community by [START_REF] Masnou | Level Lines based Disocclusion[END_REF] where it was named image disocclusion. The term inpainting was invented for art restorations (Emile-Male et al., 1976) and was first used for digital image restoration in [START_REF] Bertalmio | Image Inpainting[END_REF].

Inpainting is an ill-posed inverse problem which does not have a unique solution. A good solution is one that is undetectable by a human observer. To solve the inpainting problem, some priors must be considered. The commonly assumed prior is that any pixel in an image share the same geometrical and color statistics than its surrounding pixels (local spatial redundancy). Depending on the other priors considered, image completion techniques can be divided into three basic groups: 1) examplar-based or patch-based methods exploiting the self-similarity principle. Recent survey describing this category can be found in [START_REF] Buyssens | Exemplar-Based Inpainting: Technical Review and New Heuristics for Better Geometric Reconstructions[END_REF]; 2) geometrical or diffusion-based methods considering a smoothness prior (see section 2.1.1); 3) hybrid methods combining the two previous types of approaches. Recent surveys describing all these categories can be found in [START_REF] Bertalmío | Inpainting[END_REF][START_REF] Guillemot | Image Inpainting : Overview and Recent Advances[END_REF][START_REF] Newson | On Video Completion: Line Scratch Detection in Films and Video Inpainting of Complex Scenes[END_REF]. We only focus in this section on the first category: patch-based methods for image inpainting.

Patch-based image inpainting methods, first introduced in [START_REF] Bornard | Missing data correction in still images and image sequences[END_REF], all extend the texture synthesis algorithm of [START_REF] Efros | Texture Synthesis by Non-parametric Sampling[END_REF]. The extension to inpainting is straightforward: given an image u defined on the set Ω with a hole H, fill-in each pixel inside H with a value (or combination of values) taken from the known area of the image

Ω S = Ω \ H (see figure 1.3).
Filling order Generally, layers of the unknown mask are inpainted successively in an onion peel strategy. As first highlighted in [START_REF] Drori | Fragment-based image completion[END_REF], the order with which POST-PRODUCTION the pixels are filled strongly influence the results. Criminisi et al., 2004, designed a clever ordering procedure with priorities depending on edge strength. The priority order at a pixel is the product of a confidence term, which measures the amount of reliable information surrounding the pixel, and a data term, that encourages linear structures to be synthesized first. The confidence term is the ratio of the number of known pixels divided by the total number of pixels in the patch. The data term is defined as

D(p) = |∇u ⊥ (p).n p | α (1.7)
where ∇ ⊥ is the orthogonal gradient, α a normalization factor (equal to 255 for grayscale images) and n p a unit vector orthogonal to the inpainting area. It encourages the linear structures to be synthesized first and depends on the isophotes (contours) that eventually pass by p.

In [START_REF] Bugeau | Combining texture synthesis and diffusion for image inpainting[END_REF], we have proposes a new data term based on the structure tensor [START_REF] Di Zenzo | A Note on the Gradient of a Multi-image[END_REF]) computed on the structure image after texture/structure decomposition [START_REF] Vese | Modeling Textures with Total Variation Minimization and Oscillating Patterns in Image Processing[END_REF]. Stucture tensors were also used in the geometry-aware data term proposed in [START_REF] Buyssens | Exemplar-Based Inpainting: Technical Review and New Heuristics for Better Geometric Reconstructions[END_REF]. In [START_REF] Le Meur | Examplar-based inpainting based on local geometry[END_REF], the data term is modified to rely on structure tensor, which better captures the local geometry. In (Xu et al., 2010), a sparsity-based priority has been proposed in order to further improve the data term from [START_REF] Le Meur | Examplar-based inpainting based on local geometry[END_REF].

Post-processing Despite all the great improvements made to patch-based inpainting (see chapter 2 for details on more advanced techniques), a common remaining problem concerns illumination discontinuities at the border of the mask. This problem may have two reasons: there are no candidate patches of the right color or the metric used is not adapted. To deal with this defect, as in [START_REF] Sun | Image completion with structure propagation[END_REF], we have proposed in (Bugeau et al., 2010a) to add a post-processing step of Poisson image editing [START_REF] Pérez | Poisson image editing[END_REF].

FROM PATCH-BASED TEXTURE SYNTHESIS TO PATCH-BASED IMAGE COLORIZATION

The final colors are obtained by solving:

min û H∪∂H ∇û -∇u(ϕ(p)) 2 2 with û| ∂H = u| ∂H
where ∂H is the outer boundary of H.

Other post-processing approach relies on color histogram equalization, which is a well known tool for contrast enhancement [START_REF] Kim | Contrast enhancement using brightness preserving bi-histogram equalization[END_REF][START_REF] Nikolova | Fast ordering algorithm for exact histogram specification[END_REF][START_REF] Pierre | Hue-preserving perceptual contrast enhancement[END_REF]. Nevertheless, as histograms do not include any information on the spatial repartition of colors, their application to local image editing problems remains limited. To cope with this lack of spatial information, spatiograms have been proposed for tracking purposes [START_REF] Birchfield | Spatiograms versus Histograms for Region-Based Tracking[END_REF]. A spatiogram is an image descriptor that combines a histogram with the mean and variance of the position of each color. In [START_REF] Papadakis | Image Editing With Spatiograms Transfer[END_REF], we have addressed the problem of local retouching of images by proposing a variational method for spatiogram transfer. More precisely, a reference spatiogram, computed on Ω S is used to modify the color values within H of a given region of interest of the processed image. From figure 1.4, we can see that the spatiogram transfer allows correcting the default of patch-based inpainting results while preserving the textures. This combination produces really plausible reconstructions (see Fig. 1.5(c) for details on the tree example).

From patch-based texture synthesis to patch-based image colorization

Image colorization consists in recovering a color image from a grayscale one. This application attracts a lot of attention in the image-editing community in order to restore or colorize old grayscale movies or pictures. While turning a color image into a gray-scale one is only a matter of standard, the reverse operation is a strongly ill-posed problem as no information on which color has to be added is known. Therefore priors must be added.

In literature, there exist two kinds of priors leading to two different types of colorization methods. In the first category, initiated by [START_REF] Levin | Colorization using optimization[END_REF], the user manually adds initial colors through scribbles to the grayscale image. The colorization process is then performed by propagating the input color data to the whole image (section 3.1). The second category, called automatic or patch-based colorization, consists in transferring color from one (or many) initial color image considered as example.

For both, the initial grayscale image is considered as the luminance channel which is not modified during the colorization. The objective is then to reconstruct the two chrominance channels, before turning back to the RGB color space. Different luminance-chrominance spaces exist and have been used for image colorization: lαβ [START_REF] Ruderman | Statistics of cone responses to natural images: Implications for visual coding[END_REF] as in [START_REF] Welsh | Transferring color to greyscale images[END_REF], Lab as in [START_REF] Charpiat | Automatic Image Colorization via Multimodal Predictions[END_REF], YCbCr as in [START_REF] Yatziv | Fast image and video colorization using chrominance blending[END_REF], or YUV as in [START_REF] Bugeau | Patch-based image colorization[END_REF]. In all of our works, we have used the YUV space 1.4. FROM PATCH-BASED TEXTURE SYNTHESIS TO PATCH-BASED IMAGE COLORIZATION since its conversion to RGB is linear.

General pipeline for patch-based image colorization

The first patch-based colorization method was proposed by [START_REF] Welsh | Transferring color to greyscale images[END_REF] It makes the assumption that pixels with similar intensities or similar neighborhood should have similar colors. It extends the texture synthesis approach by [START_REF] Efros | Texture Synthesis by Non-parametric Sampling[END_REF] the final color of one pixel is copied from the most similar pixel in the input color image. The similarity between pixels relies on patch-based metrics. This approach has given rise to many extension in the literature.

In the following, we denote as

• u T : Ω → R the target grayscale image (which is assumed to be a luminance image)

• u : Ω → R 3 the estimated color image, Y u : Ω → R its luminance (that must be equal to u T ), u c = (U u , V u ) : Ω → R 2 its chrominances in the YUV color space, and R u , G u , B u its channels in the RGB color space. • u S : Ω S → R 3 the source color image.

With these notations, the goal of image colorization is to find u under the constraint that it luminance channel Y u is equal to u T . Most patch-based methods for image colorization proposed in the literature can be summarized into a three-steps general pipeline.

Step-1, Pre-Process u S and u T This step consists in converting u S to a luminance-chrominance space and setting Y u = u T . Automatic patch-based image colorization methods rely on a copy/paste of the chrominances from the source image to the target image. In order to select the color to transfer, the luminance of u S ( denoted by Y u S ) and u T should be comparable. Ideally, the transfer process should take into account the global difference in luminance of the two images, i.e., these two images should have similar global statistics such as the mean and the variance. For this purpose, an affine luminance mapping [START_REF] Hertzmann | Image analogies[END_REF] is generally performed on Y u S .

Step-2, Predict Color from u S and transfer to u The second step aims at choosing for each pixel p ∈ Ω the best pixel ϕ(p) ∈ S n which minimizes a distance on the luminance neighborhoods:

ϕ(p) = arg min q∈Sn d(Ψ Yu (p), Ψ Yu S (q)) .
The process is illustrated on figure 1.6. The set S n = {q 1 , . . . , q n } of n possible candidate pixels is either the whole pixel grid Ω S of the source image or a subset of this grid (n ≪ Ω S ). In [START_REF] Welsh | Transferring color to greyscale images[END_REF][START_REF] Bugeau | Patch-based image colorization[END_REF][START_REF] Bugeau | Variational Exemplar-Based Image Colorization[END_REF][START_REF] Pierre | Exemplarbased colorization in RGB color space[END_REF], approximately n = 200 source pixels are selected on a randomly jittered grid (figure 1.6 (b)). Any other acceleration methods for patch search (see section 1.1) can also be used. For instance, in (Pierre et al., 2017a), we rely on patchmatch [START_REF] Barnes | PatchMatch: a randomized correspondence algorithm for structural image editing[END_REF].

Finally, the chrominances of ϕ(p) are transferred to p:

u(p) = (Y u (p), U u S (ϕ(p)), V u S (ϕ(p))).
In [START_REF] Welsh | Transferring color to greyscale images[END_REF], the distance is based on the average of the standard deviation on a 5 × 5 neighborhood and the luminance of the pixel. In [START_REF] Charpiat | Automatic Image Colorization via Multimodal Predictions[END_REF], the color prediction is based on machine learning techniques (either SVM or Parzen windows), discrete optimization, continuous color refinement and image descriptors to capture textures or complex structures.

Step-3, Post-Process u T The last step generally consists in a simple color space re-conversion, i.e., from the luminance-chrominance to the RGB color space.

1.4. FROM PATCH-BASED TEXTURE SYNTHESIS TO PATCH-BASED IMAGE COLORIZATION

Influence of patch representation and metrics

Natural images are composed of different types of complex structures, redundancies and textures, which are not well captured by the SSD distance only nor by simple statistics as the luminance itself or the standard deviation. In [START_REF] Bugeau | Patch-based image colorization[END_REF] and our derived work on image colorization (see chapter 3), we have studied the combination of different patch-based features and their associated metrics to better find good candidates. Let us here present and compare the three features used in our works.

While many metrics to compare patches exist (see section 1.2), in [START_REF] Bugeau | Patch-based image colorization[END_REF] we only concentrated on 3 different features f l and the corresponding distances d l with l ∈ L = {1, 2, 3}. Each of these three features is computed for different size s of patches.

The choice of the metrics and patch descriptors has been made experimentally but they all capture a different characteristic of the grayscale image. In practice, we chose 8 measures, as detailed now. Given a luminance image Y : Ω → R, for any pixel p = (x, y) ∈ Ω, we compute:

RR1. the variance

f 1 (p, s) = ν(Ψ Y (p))
which differentiates constant and textured areas. In the experiments, we used two size of patches for this feature: 3, 5. RR2. the amplitude spectrum of the 2D discrete Fourier transform

f 2 (p, s) = DFT(Ψ Y (p)) 2
where . 2 is the amplitude of the complex number. This feature gives information on the high frequencies of the most important structures. In the experiments, we used three size of patches for this feature: 7, 9, 11; RR3. the cumulative histograms containing H bins with {h 1 , . . . , h H } and ∀i = 1, . . . , H

f 3 (p, s, h i ) = i j=1 q∈Ψs(p) δ(Y (q), h j ) |Ψ s (p)|
where δ(a, h j ) = 1 if the luminance a belongs to the j-th bin h j and δ(a, h j ) = 0 otherwise. This cumulative histogram takes into account the luminance distribution inside the patch. In the experiments, we used three size of patches for this feature: 7, 9, 11.

From the features space, we define the associated distances d l with l = {1, 2, 3} such that CHAPTER 1. EXPLOITING THE SELF-SIMILARITY PRINCIPLE FOR IMAGE POST-PRODUCTION for two pixels p, q, we have:

d 1 (p, q, s) = |f 1 (p, s) -f 1 (q, s)| , d 2 (p, q, s) = ξ |f 2 (p, s, ξ) -f 2 (q, s, ξ)| and d 3 (p, q, s) = H h=1 |f 3 (p, s, h) -f 3 (q, s, h)|.
As we are comparing 1-dimensional grayscale images, we can notice that the ℓ 1 distance d 3 on the cumulative histograms is equivalent to the ℓ 1 Wasserstein distance between the distributions. This metric is therefore robust to illumination changes.

Figure 1.7 demonstrates experimentally that the same feature is not adapted to colorize all kind of images. A patch-based colorization process similar to [START_REF] Welsh | Transferring color to greyscale images[END_REF] is here applied with the different metrics: variance, discrete Fourier transform, Wasserstein and SSD distances. The first feature is computed with 3 × 3 patches and the three others with 11 × 11 patches. This experiment demonstrates the interest of combining different features in patch-based methods. We can also observe that the SSD is not well suited for all images as it requires patches to be similar and aligned. As we here only consider n = 200 samples, the odds of getting similar source and target patches are very small. That is the reason why we did not considered this metric in our future works.

Finding an optimal metric

In (Pierre et al., 2015a), we have studied the possibility of designing an optimal metric as a linear combination of standard pre-defined metrics. The user provides a set of labeled source images, as well as the initial metrics. Distances between all patches extracted from the source images are first computed. Support vector machines (SVM) are next used to compute the coefficients of the linear combination between the different metrics. Results of this methods are promising. One limitation is that the optimal metric has to be learned again each time a new type of texture is present in an image.

Combining different patch representations to improve patchbased image colorization

As there is no optimal metric for all kinds of images, some authors have proposed to combine several metrics in their image colorization process. Unfortunately, as the metrics are of different nature, they are generally not directly comparable and must be combined in a clever way. [START_REF] Welsh | Transferring color to greyscale images[END_REF] Contrary to previous approaches in image colorization, in [START_REF] Bugeau | Patch-based image colorization[END_REF], we proposed not to predict one unique chrominance per pixel but several. From the features and metrics introduced in previous section, we can define, for each pixel, the set of chrominances from which the final chrominance will be computed. For each point p ∈ Ω, each CHAPTER 1. EXPLOITING THE SELF-SIMILARITY PRINCIPLE FOR IMAGE POST-PRODUCTION feature l and each size s, we select the candidate q l,s such that: q l,s = argmin q∈Sn d l (p, q, s), leading to the chrominance set

C(p) = {(U u S (q l,s ), V u S (q l,s ))} .
For the sake of clarity, we rewrite this set as:

C(p) = {c i (p) = (U u S (q i ), V u S (q i )) , ∀i = 1, . . . , N }
where N is the total number of candidates (8 in our case). We now have a reduced set of possible chrominances for each pixel p of the grayscale image.

In [START_REF] Bugeau | Patch-based image colorization[END_REF], we select the best chrominance among C(p) as the median value on the main axis of the PCA of C(p). Once the chrominance for each pixel of u has been found, we apply a post-processing step that regularizes the result with total variation. 2008), with a much simpler approach. As shown in Figure 1.9 and also on the Joconde images, our approach avoids color bleeding along contours thanks to the smoothing effect of regularization post-processing. For the images presented in Figure 1.8(d), the method of [START_REF] Welsh | Transferring color to greyscale images[END_REF] clearly produces inconsistent colorization. [START_REF] Charpiat | Automatic Image Colorization via Multimodal Predictions[END_REF][START_REF] Bugeau | Patch-based image colorization[END_REF] Figure 1.9: Zoom on the zebra image from figure 1.8.

Conclusion and need for non-greedy patch-based methods

In this section we have introduced patch-based methods for texture synthesis, image inpainting and image colorization. Patch-based methods for image inpainting are simple to implement while providing very good results on many different type of images. Automatic patch-based colorization is also simple in essence and able to correctly colorize most grayscale images.

Metrics to compare features of patches have been introduced and we have detailed their use in inpainting and colorization. As we have seen in section 1.4, no optimal metric exists to capture both structure and texture details of all natural images. To cope with this problem, it is often necessary to post-process the results of patch-based algorithms or to propose methods able to combine different metrics as we have done for image colorization. All patch-based methods discussed in this section, are one-pass algorithms: once a pixel is filled, its value remains unchanged. These techniques then suffer from common problems with greedy algorithms, and in particular from the filling order which is often critical. This is reflected for example in the propagation of wrongly reconstructed pixels, often observed as growing garbage, verbatim copy or discontinuities in strong structure (see figure 1.10 ).

While some studies propose clever filling orders, the associated algorithms remain greedy and lead to unrealistic images. Many methods, starting with [START_REF] Demanet | Image Inpainting by Correspondence Maps: a Deterministic Approach[END_REF] and [START_REF] Kwatra | Texture optimization for examplebased synthesis[END_REF] propose iterative optimization algorithms of discrete or variational formulation of the problem in order to address these limitations. This mater will be the topic of chapters 2 and 3 for inpainting and colorization respectively.

Chapter 2

Patch-based models for image inpainting

In previous chapter, we have introduced patch-based methods for texture synthesis, image inpainting and image colorization. In this section, we will concentrate on the inpainting application only. Besides patch-based inpainting methods, another trend to tackle this problem is to rely on "geometric" methods. This category represents PDE and variational models (section 2.1.1). They are well suited to reconstruct structures but fail for textured areas. For this reason, several discrete and variational models, combining both types of approaches, have been proposed over the past ten years. This chapter will give an overview of these approaches. Section 2.1 presents geometric models and provides a qualitative comparison with patch-based approaches. Additionally, we detail how these techniques can be used for inpainting LiDAR point clouds. In section 2.2, we concentrate on the modeling of patch-based inpainting problem from the point of view of energy minimization, that provides non greedy patch-based algorithms.

Patch-based vs. "Geometric" methods

We will start in this section by presenting "geometric" methods for image inpainting and showing qualitative comparisons with patch-based methods (section 2.1.1). Applications to completion of LiDAR point clouds are next explained in section 2.1.2.

Geometric methods

Geometric methods for image inpainting are based on color diffusion using Partial Differential Equations (PDE's) and variational formulations. They have been very successfully 2.1. PATCH-BASED VS. "GEOMETRIC" METHODS used, in particular for piecewise smooth images or when the hole H is thinner than the surrounding objects. The first work in this area was by [START_REF] Masnou | Level Lines based Disocclusion[END_REF], whose algorithm performs inpainting by joining with geodesic curves the points of the level lines (iso-value contours) arriving at the boundary of H. They were inspired by the work of Nitzberg et al., 1993, who, in the context of image segmentation, were looking for completion curves in a missing region H which should be as short as possible and should respect Gestalt's principle of good (smooth) continuation (the human visual system completes missing curves with curves that are as short and as smooth as possible). In order to join with a curve C two points p, q lying on the boundary ∂H of H, [START_REF] Nitzberg | Filtering, Segmentation, and Depth[END_REF], proposed to choose the curve minimizing an energy functional called Euler's elastica [START_REF] Mumford | Algebraic Geometry and its Applications[END_REF]. As its minimization leads to a fourth-order PDE, [START_REF] Ballester | Filling-in by joint interpolation of vector fields and grey levels[END_REF] proposed a new functional which is a relaxation of the Elastica. The basic idea is that the level lines of the image are smoothly transferred from a band around H toward the inside of H, while keeping the image values and their gradient direction compatible. Many other functionals or PDE have been proposed (Chan et al., 2001a;Chan et al., 2001b;[START_REF] Chan | Euler's elastica and curvature based inpaintings[END_REF]In practice, these methods are extremely computationally consuming since convergence requires a high number of iterations.

All previous PDEs where based on curvature diffusion. Other PDEs, also relying on the isophotes exist. In [START_REF] Bertalmio | Image Inpainting[END_REF], a third order PDE, solved only inside H with proper boundary conditions on ∂H, was introduced. Its purpose is to propagate image Laplacians in the isophote directions. The edges recovered with this approach are smooth and continuous at the boundary of the hole. Later, in [START_REF] Bertalmio | Strong-continuation, contrast-invariant inpainting with a thirdorder optimal PDE[END_REF], a thirdorder PDE complying with the principle of good continuation was proposed. This PDE does not well permit to handle images containing textures and its high order makes it computationally expensive.

Another PDE method dedicated to anisotropic smoothing was developed by [START_REF] Tschumperlé | Fast Anisotropic Smoothing of Multi-Valued Images using Curvature-Preserving PDE's[END_REF]. Its principle is to retrieve the geometry of the main structures inside the hole using a structure tensor field, and to apply anisotropic diffusion following this geometry.

The global resolution of all the PDEs previously presented is made iteratively, which makes these methods very time consuming. A non iterative method, based on coherence transport, was proposed by [START_REF] Bornemann | Fast Image Inpainting Based on Coherence Transport[END_REF]. It calculates the image values inside the masks by traversing these pixels in just a single pass using the fast marching technique. The mask is filled in a fixed order, from its boundary inwards, using weighted means of already calculated image values. The weights are defined such that the image information is transported in the direction of the isophotes.

The underlying idea behind geometric approaches is to smoothly transport the contours of presents a comparison between a geometric method [START_REF] Tschumperlé | Fast Anisotropic Smoothing of Multi-Valued Images using Curvature-Preserving PDE's[END_REF]) and a patchbased method (Criminisi et al., 2004). We observe the properties that were already mentioned: geometric methods permit to obtain smooth contours and structures but are not able to reconstruct the textures. When looking at the patch-based approach in the fourth column, we observe the opposite, textures are pretty well reconstructed but edges are not continuous.

Application to completion of 3D LiDAR point clouds

In [START_REF] Biasutti | Disocclusion of 3D LiDAR point clouds using range images[END_REF][START_REF] Biasutti | Range-Image: Incorporating sensor topology for LIDAR point clouds processing[END_REF], we have used a geometric method to reconstruct missing LiDAR points. Let us briefly introduce the context of this work before presenting the proposed reconstruction method.

Over the past decade, street-based Mobile Mapping Systems (MMS) have encountered a large success as the onboard 3D sensors are able to map full urban environments with Although MMS lead to very complete 3D mappings of urban scenes by capturing optical and 3D details (pavements, walls, trees, etc.), they often acquire mobile objects that are not persistent to the scene (cars, pedestrians, traffic cones, etc). As LiDAR sensors cannot penetrate through opaque objects, those mobile objects cast shadows behind them where no point has been acquired (Figure 2.3, left). These shadows are also largely visible when the point cloud is not viewed from the original acquisition point of view. They are therefore distracting and confusing for visualization. Thus, the segmentation of mobile objects and the reconstruction of their background remain strategic issues in order to improve the understability of urban 3D scans.

Instead of working directly on the 3D point cloud, making use of the sensor topology, we have proposed in [START_REF] Biasutti | Disocclusion of 3D LiDAR point clouds using range images[END_REF][START_REF] Biasutti | Range-Image: Incorporating sensor topology for LIDAR point clouds processing[END_REF], a new 2D representation of this type of data, called range image (figure 2.4). LiDAR points are ordered along scanlines, yielding the first dimension of the sensor topology, linking each LiDAR pulse to As a first application, we have proposed to use a a contrario method [START_REF] Delon | A nonparametric approach for histogram segmentation[END_REF] to automatically segment objects according to their depth. Next, we tackled the problem of removing one object of the scene. As range images do not contain texture, we decided to rely on a geometric approach by diffusing the range information within the missing area. In urban environment the structures that require disocclusion are likely to evolve horizontally, i.e. smoothly along the x W and y W axis of the real world as defined in figure 2.5. Let us define η, for each point, to be a unitary vector orthogonal to the projection of z W in the range image u. This vector will define the direction in which the diffusion should be done to respect this prior of horizontal structures. Therefore, in our inpainting method, we propose to extend the level lines of u along η. This can be expressed as ∇u, η = 0. Therefore, we define the energy F (u) = 1 2 ( ∇u, η ) 2 . The disocclusion is then computed as a solution of the minimization problem min u F (u). The gradient of this energy is given by ∇F (u) = -(∇ 2 u) η, η = -u η η , where u η η stands for the second order derivative of u with respect to η and ∇ 2 u for the Hessian matrix. The minimization of F can be done by gradient descent. If we cast it into a continuous framework, we end up with the following equation to solve our disocclusion problem:

∂u ∂t -u η η = 0 in H × (0, T ) u(0, x) = u 0 (x) in H (2.1)
where H is the area of the objects to remove and u 0 is the initial range image with the hole.

Inpainting of a pedestrian is shown in figure 2.6. This result is obtained for a sparse point cloud (≈ 10 6 pts) of the KITTI database [START_REF] Geiger | Vision meets Robotics: The KITTI Dataset[END_REF]. We can observe that the disocclusion performs very well as the pedestrian has completely disappeared and the result is visually plausible in the inpainted range image.

The coherence of the reconstruction can be checked by looking how the acquisition lines are connected in 3D (figure 2.7). Note that a similar analysis can be done on the results presented in Figure 2.3. For more qualitative and quantitative analysis, we refer the reader to [START_REF] Biasutti | Range-Image: Incorporating sensor topology for LIDAR point clouds processing[END_REF]. We have here illustrated an application, different from natural image inpainting, for which geometric methods have a strong interest. In next paragraph, we will show that, even in the context of LiDAR point clouds inpainting, it is sometimes suitable to combine geometric methods with patch-based ones.

Application to the production of orthophotographies from LiDAR point clouds

In this section, we tackle another application related to LiDAR point clouds completion, namely the production of orthophotographies. Orthophotography and Digital Terrain Model (DTM), are defined respectively as the color and ground height orthoimages (i.e. raster maps defined on a regular horizontal grid). They are widely used in many application fields such as remote sensing, geographical information and earth observation, mapping, environmental studies... They are often computed from aerial acquisition devices such as satellites, aircrafts and more recently Unmanned Aerial Vehicles (UAVs). Although these techniques provide a very well known and common approach to the problem of orthoimage generation, they are limited in terms of accuracy and resolutions, and suffer from occlusions that are caused by natural and urban environments such as trees, tunnels, tall buildings, etc (figure 2.11 top). Using a Mobile Laser Scan (MLS) coming from a mobile mapping system as presented in previous section can solve these issues. Orthoimage generation from MLS has been scarsely studied in the past. [START_REF] Vallet | Road orthophoto/DTM generation from mobile laser scanning[END_REF], first extract the ground points by considering the lowest points projected in each pixel. Next, they perform Gaussian diffusion to connect sparse pixels. In (Biasutti et al., 2017a), we have The first step consists in extracting ground points and their projection onto a 2D plan, leading to two 2D-images: u 0 for reflectance and h 0 for height. This projection is done by removing the z (height) coordinate and rounding the coordinates to the chosen resolution.

We also build a mask M proj of pixels where at least one point was projected. After this first stage, the projections u 0 and h 0 are sparse as they do not cover all the pixels in the images. We can distinguish 3 classes of holes in these (sparse) images.

RR1. Areas that do not correspond to the ground points (inside of buildings, point that are too far from the sensor, ...). These areas do not require any more processing as they should ideally not be reconstructed.

RR2. Under sampling of the LiDAR sensing. As the holes are here very small, we have chosen to use a diffusion method in order to reconstruct missing data. We rely on a modified version of the anisotropic diffusion from [START_REF] Perona | Scale-space and edge detection using anisotropic diffusion[END_REF],by coupling reflectance and height information. A result is presented on figure 2.9.

RR3. Occlusions that appear when a relatively vertical object was blocking the beams.

Occlusions prevent the sensor from acquiring ground points. The hole being larger, we here rely on a modified version of the patch-based inpainting approach from (Criminisi et al., 2004, section 1.3) by (i) averaging the patch distance over the reflectance and height images; (ii) constraining the selection of candidates to patches that are at a similar distance to the sensor than that of the current patch. A result is shown on figure 2.10.

A comparison between traditional aerial orthophotography and MLS orthoimage using our framework is given in figure 2.11. The resolution provided by the aerial camera is about 50cm 2 per pixel, whereas our reconstruction is done at 1cm 2 per pixel. Fine textures and very accurate details are noticeable in the reconstruction whereas only main structures can be seen in the aerial orthophotography. Moreover, the aerial orthophotography presents various occlusions (due for instance to trees) that do not appear in our result.

Combining geometric and patch-based methods

Both patch-based and geometric methods have their own advantages and limits for image inpainting. It therefore seems natural to combine these two categories of methods. The solution that has been proposed in [START_REF] Bertalmio | Simultaneous structure and texture image inpainting[END_REF] consists in decomposing the initial image into a structure image and a texture one [START_REF] Vese | Modeling Textures with Total Variation Minimization and Oscillating Patterns in Image Processing[END_REF]. The structure image is completed using a geometric method [START_REF] Bertalmio | Image Inpainting[END_REF] and the texture one with a patch-based approach [START_REF] Efros | Texture Synthesis by Non-parametric Sampling[END_REF]. These two images are summed to retrieve the final reconstructed image. An improvement to this method using more recent inpainting methods and enhanced filling order (section 1.3) was later proposed in [START_REF] Bugeau | Combining texture synthesis and diffusion for image inpainting[END_REF]. While being promising, this first way of combining geometric and patch-based methods remains too dependent on the quality of the texture/structure decomposition.

Other works [START_REF] Mairal | Sparse representation for color image restoration[END_REF][START_REF] Elad | Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA)[END_REF][START_REF] Peyre | Learning adapted dictionaries for geometry and texture separation[END_REF][START_REF] Fadili | Inpainting and Zooming Using Sparse Representations[END_REF] perform inpainting in an energy minimization framework with sparsity regularization:

CHAPTER 2. PATCH-BASED MODELS FOR IMAGE INPAINTING
patches inside H are synthesized as a sparse linear combination of elements from an image dictionary. As these approaches are limited to the reconstruction of thin regions, they will not be further discussed in this section.

In the following we present energy functions which minimization lead to iterative patchbased methods.

Discrete patch-based modeling

The first discrete modeling for patch-based inpainting was proposed in [START_REF] Demanet | Image Inpainting by Correspondence Maps: a Deterministic Approach[END_REF]. The authors introduce an energy which is optimized over the correspondence map ϕ and the image u:

E d (ϕ, u) = p∈H V d (p, ϕ(p)) = p∈H d SSD (Ψ u (p), Ψ u (ϕ(p)) (2.2)
This equation being highly non linear, there is no explicit solution or algorithm to find a global minimum. [START_REF] Demanet | Image Inpainting by Correspondence Maps: a Deterministic Approach[END_REF] proposed to approximate the solution by repeating until convergence the basic texture synthesis approach with an "onion peel" strategy. The algorithm updates, for each pixel p, u(p) and ϕ(p) conjointly. Note that the authors suggested as a possible improvement to impose restrictions on the correspondence map by penalizing its total variation and favoring that it behaves locally as a translation, but they did not later pursue this line of thought.

A similar energy was also proposed in [START_REF] Kwatra | Texture optimization for examplebased synthesis[END_REF] for texture synthesis and in [START_REF] Wexler | Space-time video completion[END_REF] for inpainting. The algorithms repeat two steps until convergence:

(1) a nearest neighbor search (thus updating ϕ for all pixels); (2) a reconstruction step updating u. In both methods, the reconstruction is done through patch fusion as a weighted mean of overlapping patches. In [START_REF] Wexler | Space-time video completion[END_REF], this is formulated as:

u(p) = k∈Ψs(p) w(q)u(ϕ(q) + p -q) q∈Ψs(p) w(q)
where w are weights:

w(q) = exp - d SSD (Ψ u (q), Ψ u (ϕ(q))) 2σ 2
σ being a parameter. Such a reconstruction smooths the final image but maintains spatial regularity along contours.

Regarding the nearest neighbor search, in order to decrease the computational time, 2.2. COMBINING GEOMETRIC AND PATCH-BASED METHODS [START_REF] Wexler | Space-time video completion[END_REF], perform ANN search (Arya et al., 1993). The "Content-Aware fill" feature of Photoshop CS6 uses the patchmatch ANN search (see section 1.1) together with the reconstruction from [START_REF] Wexler | Space-time video completion[END_REF].

Modeling through graph models

Instead of imposing spatial regularity through patch fusion, some works prefer to add it as a constraint in the energy formulation, and recast inpainting as a labeling problem. [START_REF] Komodakis | Image Completion Using Global Optimization[END_REF], formulate the inpainting problem as an energy minimization over a graph where the nodes are a subset of pixels whose neighborhood intersects H. The energy reads

E(ϕ, u) = p∈N V d (p, ϕ(p)) + λ (p,q)∈E V c (p, ϕ(p), q, ϕ(q)) (2.3)
where

V d (p, ϕ(p)) = r∈Ψs(p)∪Ψs(q) d (Ψ u (ϕ(p) + r -p), Ψ u (ϕ(q) + r -q)) . (2.4)
λ is a scalar, N is a subset of pixels regularly spread over the pixel grid Ω and E is the set of edges with a 4-neighborhood system. The second term (smoothness term) measures how well two patches Ψ s (ϕ(p)) and Ψ s (ϕ(q)) agree at the resulting region of overlap (blue area in figure 2.12). We name this regularity overlap coherence. This problem is optimized over a set of possible labels through belief propagation leading to very good results on many images. However, there is no assurance that the iterative process converges to a global minimum. Additionally visual artifacts may appear since the method uses a subset of pixels and copy entire patches.

A graph representation was also used in [START_REF] Pritch | Shift-map image editing[END_REF], N being the complete pixel grid. The first term (data term) constraints candidate patches to belong to the known part of the image. The smoothness term enforces the overlap coherence, both in term of color as in [START_REF] Komodakis | Image Completion Using Global Optimization[END_REF] but also in terms of gradients:

V c (p, ϕ(p), q, ϕ(q)) = u(ϕ(q)) -u(ϕ(p) + q -p) 2 + β ∇u(ϕ(q)) -∇u(ϕ(p) + q -p) 2
where β is a scalar. The energy in minimized in a multi-resolution scheme through mincut/maxflow [START_REF] Kolmogorov | What energy functions can be minimized via graph cuts?[END_REF]).

An extension to this approach was later proposed by Y. [START_REF] Liu | Exemplar-Based Image Inpainting Using Multiscale Graph Cuts[END_REF], with a data term similar to (2.2), and a specific treatment for coarsest resolution in order to deal with lost high frequencies.

Figure 2.12: Illustration of the overlap coherence: the two green areas must be consistent.

The blue region corresponds to the overlapping area Ψ s (p) ∪ Ψ s (q) and the two green areas are the ones compared in the second term of equation ( 2.3).

Combining patch-based, geometric and overlap coherence constraints into one model

Aujol et al., 2010, proposed several energy functionals for inpainting with terms related to texture synthesis, spatial coherence (by favoring the mapping function to be locally a roto-translation), and geometry (by minimizing the Total Variation of the "geometry" part of the image, after a cartoon/texture decomposition), but the authors did not actually proposed a minimization algorithm for them.

In (Bugeau et al., 2010a), we proposed a discrete model, made of three terms, also combining texture synthesis, geometry and overlap coherence:

E(ϕ, u) = p∈H V d (p, ϕ(p)) + p∈H V g (p, ϕ(p)) + p∈H V c (p, ϕ(p)) (2.5)
The first term is the same as the one defined in (2.2), with the metric d SSDB (1.4). The second term encourages continuity in geometric structures:

V g (p, ϕ(p)) = d SSD (Ψ v d (p), Ψ u (ϕ(p))), (2.6)
where v d is a diffusion image defined as:

v d (p) = q∈Ψs(p)\p w(p, q)u(q) q∈Ψs(p)\p w(p, q)
where w is a weighting function depending on the type of diffusion used. In our work, 2.2. COMBINING GEOMETRIC AND PATCH-BASED METHODS we used the coherence transport diffusion method of [START_REF] Bornemann | Fast Image Inpainting Based on Coherence Transport[END_REF] for which w(p, q) is higher if the pixel q is in the direction of the level line at p.

The third terms enforces the overlap coherence. We consider that the family of values {Ψ u (ϕ(q) + pq) : q ∈ Ψ s (p)} is representative of the value of Ψ u (p) and can be used to estimate it. In order to be less sensitive to the possible aberrant values in the neighborhood of p, we propose to use median instead of mean (as in [START_REF] Komodakis | Image Completion Using Global Optimization[END_REF], leading to:

V c (p, ϕ(p)) = d SSD (Ψ vc (p), Ψ u (ϕ(p))), (2.7)
where v c is a coherence image defined as:

v c (p) = median{Ψ u (ϕ(q) + p -q) : q ∈ Ψ s (p)}.
The multi-resolution algorithm alternates an estimation step and a reconstruction step. The estimation of ϕ simply consists in estimating the nearest neighbor field with respect to the three patch representations (Ψ u , Ψ vc and Ψ v d ) coinjointly. The reconstruction of u simply consists in copying the values of this nearest neighbor for each pixel in H.

Characterizing solutions of patch-based models

For all previous models, there is no proof of convergence to a global minimum. In other words, it is very hard to characterize and improve the solutions of the models. An important contribution was then proposed in [START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF][START_REF] Arias | Analysis of a Variational Framework for Exemplar-Based Image Inpainting[END_REF]. The authors propose a functional optimized not over the correspondence map but over a weighting function w : H × Ω S → R indicating the contribution of each pixel in Ω S to the estimation of u(p), p ∈ H. This formulation is inspired by a variational formulation of non-local means denoising [START_REF] Gilboa | Nonlocal linear image regularization and supervised segmentation[END_REF][START_REF] Gilboa | Nonlocal operators with applications to image processing[END_REF]. It contains two terms: one measuring the similarity between patches in H and patches in Ω S , and the other related to the entropy of the weight distributions:

E(u, w) = H Ω S w(p, q)d(Ψ u (p), Ψ u (q))dqdp -T H Ω S w(p, q) log w(p, q)dqdp (2.8) subject to Ω S w(p, q)dq = 1 ∀p ∈ H
where the sets H is a dilated version of H . The parameter T controls the selectivity of the weighting function w. The algorithm contains two steps repeated until convergence: estimation of w and reconstruction of u. For all pair of pixels p ∈ H and q ∈ Ω S , the CHAPTER 2. PATCH-BASED MODELS FOR IMAGE INPAINTING estimation step computes:

w(p, q) = exp - d(Ψ u (p), Ψ u (q)) T ,
given the current image u. In practice, to avoid prohibitive computation times, a ANN search with patchmatch [START_REF] Barnes | PatchMatch: a randomized correspondence algorithm for structural image editing[END_REF] in first used, and w(p, q) is only computed when q is an approximate nearest neighbor of p. The reconstruction step computes u with an explicit formulation which depends on the distance d: patch non-local means (if d is the Gaussian weighted SSD), patch non-local median (if d is the Gaussian weighted SAD), patch non-local Poisson (if d is the sum of Gaussian weighted SSD over u and ∇u) and a reconstruction from the Affine Invariant Self-Similarity [START_REF] Fedorov | Affine Invariant Self-Similarity for Exemplar-Based Inpainting[END_REF].

Convergence to critical points are discussed in [START_REF] Arias | Analysis of a Variational Framework for Exemplar-Based Image Inpainting[END_REF] Extension of this method to video inpainting was proposed in [START_REF] Newson | Video inpainting of complex scenes[END_REF] with

Results

Figure 2.13 presents a comparison of different inpainting methods discussed previously. All of these methods require the tuning of some parameters. For the method from [START_REF] Tschumperlé | Fast Anisotropic Smoothing of Multi-Valued Images using Curvature-Preserving PDE's[END_REF] as suggested in the original paper, we set the contour preservation parameter p 1 to 0.001, the structure anisotropy p 2 = 100, the time step dt = 150, and the number of iterations nb equal to 100. For the technique from [START_REF] Bornemann | Fast Image Inpainting Based on Coherence Transport[END_REF], we set the averaging radius ǫ = 5, the sharpness parameter κ = 25, the scale parameter for presmoothing σ = 1.4, and for post-smoothing ρ = 4. For all patch-based methods, we used 9×9 patches. We can see that Bugeau et al., 2010a;[START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF] and Content-Aware fill (Photoshop CS5) are able to correctly inpaint the covered lanterns, the text on these lanterns and the red and white striped bars, while the other techniques fail in some of these aspects. This result highlight the importance of using a non-greedy approach and the fusion of geometric and patch-based methods.

Finally, Figure 2.14 shows an image where none of the methods discussed in this document seems to work. The problem here is that diffusion methods [START_REF] Tschumperlé | Fast Anisotropic Smoothing of Multi-Valued Images using Curvature-Preserving PDE's[END_REF][START_REF] Bornemann | Fast Image Inpainting Based on Coherence Transport[END_REF] are able to synthesize new information but they are not able to deal with texture, while patch-based methods (Criminisi et al., 2004) treat texture correctly but are not good at creating new information. Even if the models discussed in this section combine these different approaches, they remain based on image self-similarity principle that may not give good results if the information needed is not already present in the image. For most of the mask, no good candidate patches exist.

Conclusion

This chapter has first presented geometric methods for image completion. We have explained how both patch-based and geometric methods can be used for LiDAR point cloud completion. We have also illustrated the limits of these two types of approaches for image inpainting when taken separately. Several patch-based models that tend to globally optimize the inpainting problem over the whole missing areas have next been discussed and their advantages highlighted. While today providing state-of-the-art results, they are still not able to solve the inpainting problem in case of complex scenes with large holes (figure 2.14). Improved models for image inpainting could probably benefit from constraints on the correspondence map itself to suggest from where the information should be copied.

Another direction of research to cope with complex scene would be to rely on more information than the image itself. There have been several attempts in the literature to extend the self-similarity principle to a larger set of patches or images. Nevertheless using an external dictionary of patches is currently limited to thin holes restoration and prevent constraints such as overlap coherence into the models. Using a larger set of images was There are some limits as seen in figure 2.14. In particular, the method highly rely on the semantic retrieval which is likely to fail at recognizing partly occluded objects or non textured areas (for instance pavement in figure 2.14). More recently deep learning has also been used for inpainting purposes [START_REF] Pathak | Context Encoders: Feature Learning by Inpainting[END_REF]Yang et al., 2017) leading to very promising results, though still a little blurry. As discussed in chapter 4, further research could be conducted in this direction even if it is difficult to characterize the solutions to the problem.

Finally, application to video inpainting is still an open subject. While some methods exist [START_REF] Granados | How Not to Be Seen -Object Removal from Videos of Crowded Scenes[END_REF][START_REF] Newson | Video inpainting of complex scenes[END_REF], the computational time is still prohibitive to enable their use in practice.

Chapter 3

Patch-based models for image colorization

In this chapter we focus on image colorization. As detailed in chapter 1, colorization is an ill-posed problem as the input image does not have any color prior. To solve this issue, patch-based methods (called automatic methods) consider as input a color image, called source, and copy the color of its pixels to the target grayscale image. Patch-based colorization methods suffer from the lack of spatial regularity and the growing garbage problem.

A second category of approaches for colorization, named manual or diffusion methods, consider as input manually added points of color (called scribbles) and propagate these colors to the rest of the image. This is achieved by applying anisotropic diffusion to the chrominance depending on the gradients of the luminance channel. As textures in an image mostly come from the luminance channel, applying diffusion on the chrominance channels produce satisfying results even in texture areas. The main limit of manual methods is the amount of user intervention required.

This chapter aims at proposing some models that enable coupling patch-based approaches with diffusion-based ones by imposing spatial regularity and constraint on the gradients of the chrominance channel w.r.t. the luminance ones. Another limit of automatic method is that, as the color prior only depends on the source image, it is worth choosing this image very carefully which is often a difficult task. Therefore several methods have proposed to use multiple registered similar images collected from internet (see X. [START_REF] Liu | Intrinsic colorization[END_REF][START_REF] Zhang | Colorful Image Colorization[END_REF]. In another trend, in (Pierre et al., 2014a), we propose to add user interaction with color scribbles, in order to improve patch-based colorization results.

This chapter is organized as follows. First we review diffusion-based manual methods 3.1. DIFFUSION-BASED MANUAL METHODS (section 3.1) before introducing some models that combine patch-based and diffusionbased approaches (section 3.2). We will use the same notations as in chapter 1. We denote as

• u T : Ω → R the target grayscale image (which is assumed to be a luminance image)

• u : Ω → R 3 the estimated color image, Y u : Ω → R its luminance (that must be equal to u T ), u c = (U u , V u ) : Ω → R 2 its chrominances in the YUV color space, and R u , G u , B u its channels in the RGB color space. • u S : Ω S → R 3 the source color image.

Diffusion-based manual methods

The first manual colorization method based on diffusion was proposed by [START_REF] Levin | Colorization using optimization[END_REF] It solves an optimization problem to diffuse the scribbles chrominances with the assumption that chrominances should have small variations where the luminance has small variations:

E(u c ) = p∈Ω   u c (p) - q∈N(p) w pq u c (q)   2 (3.1)
where N(p) is the 4-neighborhood of pixel p, w pq are weights defined by

w pq ∝ exp - (Y (p) -Y (q)) 2 2σ 2 p
where σ p is the variance in a window around p. A result of this method is presented on Figure 3.1. [START_REF] Lagodzinski | Digital image colorization based on probabilistic distance transformation[END_REF], discriminative textural features [START_REF] Kawulok | Discriminative Textural Features for Image and Video Colorization[END_REF], structure tensors [START_REF] Drew | Improvement of Colorization Realism via the Structure Tensor[END_REF] or non local graph regularization [START_REF] Lézoray | Nonlocal graph regularization for image colorization[END_REF]. As often described in the literature, with these manual approaches, the contours are not well preserved. To cope with this issue, in [START_REF] Ding | Colorization Using Quaternion Algebra with Automatic Scribble Generation[END_REF], scribbles are automatically generated after segmenting the image and the user only needs to provide one color per scribble. computing quaternion wavelet phases so that the color is propagated along equal phase lines.

However, all manual methods suffers from the following drawback: if the target represents a complex scene the user interaction becomes very important. On the other hand these approaches propose a global optimization over the image thus leading to spatial consistency in the resul

Combining patch-based and diffusion methods

In this section we will describe some models for image colorization. The purpose for these models is three folds: (i) add spatial consistency in the results obtained with automatic patch-based methods, (ii) add coupling between luminance and chrominance gradients (iii) increase the set of possible chrominances for each pixel with manual intervention.

To overcome the spatial consistency and coupling problems in automatic methods, several works rely on image segmentation. For instance, [START_REF] Irony | Colorization by example[END_REF] propose to determine the best matches between the target pixels and regions in a pre-segmented source image. With these correspondences, micro-scribbles from the source are initialized on the target image and colors are propagated as in [START_REF] Levin | Colorization using optimization[END_REF]. [START_REF] Gupta | Image colorization using similar images[END_REF] extract different features from the superpixels (X. [START_REF] Ren | Learning a classification model for segmentation[END_REF] of the target image and match them with the source ones. The final colors are computed by imposing spatial consistency as in [START_REF] Levin | Colorization using optimization[END_REF]. These approaches incorporate diffusion into automatic methods but are highly dependent on the quality of the segmentation. In [START_REF] Bugeau | Variational Exemplar-Based Image Colorization[END_REF]Pierre et al., 2015a;Pierre et al., 2014a) and our other papers on image colorization, we have proposed several models to cope with the limitations of automatic patch-based methods. In all these works, we consider that each pixel p in the target image u T can only take its chrominance (or RGB color) among a reduced set of possible candidates: C(p) = c i (p) ∈ Ω S , i = 1, . . . , N . These candidates can either be extracted from the source image as in [START_REF] Bugeau | Patch-based image colorization[END_REF] (see section 1.4.3) or be given by manual intervention (Pierre et al., 2014a).

Colorization is traditionally done in a luminance-chrominance space, estimating the chrominance channels only. This may lead to some issues if the conversion from luminancechrominance space back to RGB gets outside the range of acceptable values in RGB. The

COMBINING PATCH-BASED AND DIFFUSION METHODS

first solution we propose is to constraint the final chrominances to belong to the set of acceptable chrominance values given an input luminance. The second one is to directly solve the colorization problem in the RGB space. These two directions are now discussed.

Colorization in the YUV color space

In [START_REF] Bugeau | Patch-based image colorization[END_REF], we have proposed to set the final chrominance at pixel p as the median of the candidate color set C(p) (see section 1.4.3), which approximates the minimization of

E(u c ) = p∈Ω i=1•••N |u c (p) -c i (p)|.
Unfortunately, when working with d > 1-dimensional data, this ℓ 1 norm separates the distance between dimensions and the median value does not correspond anymore to one of the candidates. In order to have a smooth derivable data term, in [START_REF] Bugeau | Variational Exemplar-Based Image Colorization[END_REF], we considered the ℓ 2 2 norm. Our problem of selecting one single candidate per point, thus avoiding heterogeneous mixing of candidate colors leading to highly unrealistic results, can be re-casted as follows:

E(u c ) = p min i u c (p) -c i (p) 2 2 s.t. u c ∈ R
where R is the standard range of chrominances. In order to minimize this energy, we consider a relaxation by increasing the state dimension with a new variable w(p) = {w i (p), i = 1, . . . , N } which represents the probability of choosing the i-th candidate for each point:

E(u c , w) = p i w i (p) u c (p) -c i (p) 2 2 s.t. u c ∈ R and w ∈ W with W = w(p) : Ω → [0; 1] N , s.t. N i=1 w i (p)=1 .
If w j = 1 and w i = 0 for i = j, then the minimum w.r.t. u c is reached for u c = c j , i.e. when selecting one candidate only. A similar fidelity term was introduced for optical flow estimation from a collection of previously computed motion candidates in [START_REF] Fortun | Aggregation of local parametric candidates with exemplar-based occlusion handling for optical flow[END_REF].

CHAPTER 3. PATCH-BASED MODELS FOR IMAGE COLORIZATION Previous energy thus admits trivial minimizers than can be chosen independently for each pixel p. In our works, we focus on the image colorization problem which involves consistent and spatially coherent image results. In [START_REF] Bugeau | Variational Exemplar-Based Image Colorization[END_REF] a Total Variation (TV) based regularization of the unknown variable u c is introduced in the energy to smooth the solution while keeping sharp discontinuities when required by the data. Unfortunately, this regularization lacks of coupling with the luminance information leading to halo effects in the colorization results (figure 3.2). Hence, in (Pierre et al., 2014a), we introduced the coupled Total Variation which is able to couple the chrominance channels with the luminance one1 :

T V c (u) = p γ∂ x Y 2 + γ∂ y Y 2 + ∂ x U 2 + ∂ y U 2 + ∂ x V 2 + ∂ y V 2 , (3.2)
where γ is a parameter which enforces the coupling.

The energy for colorization finally reads:

E(u c , w) = T V c (u) + λ 2 p i w i (p) u c (p) -c i (p) 2 2 s.t. u c ∈ R and w ∈ W (3.3)
A primal-dual algorithm, inspired by [START_REF] Chambolle | A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging[END_REF] is used to minimize this energy. Its convergence to a fixed-point which is a critical pseudo saddle-point of the problem is demonstrated in (Pierre et al., 2015a). In Figure 3.2 we compare the result with (γ = 25, as in Pierre et al., 2014a) and without the coupled TV (γ = 0, as in [START_REF] Bugeau | Variational Exemplar-Based Image Colorization[END_REF]. The set of candidates C is defined as in section 1.4.2, i.e. using a patch-based search for candidates using 8 different patch features. The coupled TV highly reduces the halos along the contour thus leading to a more realistic result.

Combining automatic and manual colorization

We now present in Figure 3.3 a result when the set of candidates come both from the automatic patch-based method described in section 1.4.3 and from a user manual intervention. At initialization, the weights are uniform for all candidates issued by the patch-based automatic method, while for manual candidates, they depend on the geodesic distance to the scribbles. Using the "automatic candidates" only (Figure 3.3(c)), the sky is not correctly colorized since it appears brown instead of blue as in the ruins main door. Moreover, blue colors appear on the floor. When using only the scribbles ( blue sky but not the color of the ruins. When combining both (Figure 3.3(e)), a realistic result is obtained. Note that instead of the geodesic distance, we could have relied on the sroke similarity mask issued from the edge-aware texture descriptor as proposed in [START_REF] Arbelot | Local texture-based color transfer and colorization[END_REF].

Extension of this method to video colorization was recently proposed in (Pierre et al., 2017b). The method propagates colors from an initial colorized frame to the whole grayscale video sequence. The spatio-temporal model also relies on pre-computed possible candidates per pixel. Here, these candidates are coming (1) from the propagation of initial colors with optical flow or block matching (using patchmatch), ( 2) from manually added scribbles.

Colorization in the RGB color space

One common problem with all image colorization methods that aim at reconstructing the chrominances of the target image is that the recovered chrominances combined with the input luminance may not fall into the RGB cube when converting back to the RGB color space. In the model (3.3), this problem is solved with the constraint u c ∈ R and using the YUV space which conversion back to RGB is linear. In this section we propose to work directly in the RGB color space with constraint on the luminance. Considering that u = (R, G, B), we proposed in [START_REF] Pierre | Exemplarbased colorization in RGB color space[END_REF] the following model: ). We add one constraint when doing this projection in order to preserve the hue of u, which represents the human perception of the pure color. Indeed, an orthogonal projection onto these constraints modifies the hue (3.4). Therefore we detail now an oblique projection that preserves constraints (3.5) and the hue. The hue H in the HSI [START_REF] Gonzalez | Digital image processing 3rd edition[END_REF] color space is defined as

E(u, w) = T V (u) + λ 2 p i w i (p) u -c i (p) 2
H = θ if B ≤ G 360 -θ otherwise, (3.6)
where θ is an angle in degrees, such as: three constraints was achieved in (Pierre et al., 2015c). First, u(p) is projected onto the yellow plan of luminance equal to u T (p) in the direction of I, leading to point u ′ (figure 3.6). Next if u ′ is out of the RGB cube, the Smit's algorithm for raytracing [START_REF] Williams | An efficient and robust raybox intersection algorithm[END_REF] is used to compute the contact point of the RGB cube [0, 255] 3 and the line D containing the green segment intersecting both plans.

θ = arccos      1 2 (R -G) + (R -B) (R -G) 2 + (R -B)(G -B)      . ( 3
Figure 3.7 presents two colorization results obtained by minimizing the model (3.4) with hue constraint and compare them with other methods. The results of [START_REF] Irony | Colorization by example[END_REF] and [START_REF] Charpiat | Automatic Image Colorization via Multimodal Predictions[END_REF] are not realistic. Due to the lack of regularization, images of [START_REF] Welsh | Transferring color to greyscale images[END_REF] show artifacts since areas that were originally homogeneous now present irregularities. The RGB colorization (3.4) with the hue constraint better preserves the homogeneous parts such as the sky. The quality of the results is comparable to the one of [START_REF] Gupta | Image colorization using similar images[END_REF], without requiring any segmentation step.

Conclusion

This chapter has introduced several models for image colorization combining patch-based automatic and manual diffusion-based techniques. We have highlighted the importance of avoiding color bleeding along luminance contours and the necessity of managing correctly conversion between color spaces. The quality of the results are very promising and could probably be further enhanced by proposing even more candidates coming from additional patch representations (such as [START_REF] Arbelot | Automatic Texture Guided Color Transfer and Colorization[END_REF] and more manual intervention.

Automatic image colorization methods rely on the careful selection of the source image. If this source is not close enough to the target in terms of context, luminance or texture statistics, no good results can be expected by automatic patch-based methods. As proposed, this problem can be solved by adding user intervention. Nevertheless, this task can become very time consuming in case of complex images. One solution is to rely not on one source image but on several (e.g. X. [START_REF] Liu | Intrinsic colorization[END_REF], or, as it will be discussed in chapter 4, on deep learning architecture (e.g. R. [START_REF] Zhang | Colorful Image Colorization[END_REF], with the difficulty of characterizing the solutions of the problem and to impose constraints reducing visual artifacts.

Chapter 4 Conclusion and Perspectives

In this manuscript, several models for image inpainting and colorization have been introduced. We have first highlighted the importance of finding a good patch representation and its associated metric in order to capture different properties of the data: high and low frequencies, luminance, color, etc. Secondly we have demonstrated how global optimization can serve the purpose of patch-based approaches. Most discrete and variational models presented incorporate local spatial regularizations of the colors to avoid unrealistic color discontinuities in the final result. Coupled with data terms constraining the set of admissible values for each pixel, these models lead to plausible results with textures and continuous structures. Let us now draw some perspectives.

Fusion of heterogeneous data

We have discussed in section 2 the application of simple image inpainting methods to the completion of LiDAR point clouds. One difficulty with LiDAR depth information is to precisely locate the contours betweens elements of the scene. For instance, when the tire of a car is in contact with the road, the depth of nearby points are very similar. Coupling depth with reflectance enables to better classify the point as part of the road or the tire but this information is not always accurate enough. Nowadays, most vehicles (planes, unmanned air vehicles, trucks) are also equipped of other sensors such as optical cameras, hyperspectral cameras and GPS combined with Inertial Measurement Unit (IMU). Coupling the data together could lead to very precise and complete 3D reconstruction of urban scenes. The first challenge is to align the different data together. The sensors are placed at different locations on the vehicle and acquire asynchronous data at various resolutions. When a very precise GPS combined with Inertial Measurement Unit is present, and if the vehicle has a relatively slow motion, existing registration techniques already provide satisfying results. Otherwise, it becomes necessary to detect common information such as structures within all the data, which requires further investigation depending on the type 4.2. REGULARITY OF THE CORRESPONDENCE MAP of data considered. In [START_REF] Castorena | Autocalibration of LIDAR and Optical Cameras via Edge Alignment[END_REF] for instance, edge alignment between LiDAR and optical data are considered. Nevertheless this methods implies that edges coincide in both modalities which is not always the case in practice.

Once the registration has been done, specific data fusion, depending on the application, must be considered. In previous works [START_REF] Bevilacqua | Visibility estimation and joint inpainting of lidar depth maps[END_REF][START_REF] Bevilacqua | Joint inpainting of depth and reflectance with visibility estimation[END_REF], we have designed a method to add depth information to every pixel of one image. As several LiDAR points may correspond to the same pixel, it is necessary to choose which depth is appropriate for that pixel. We solved this problem through minimization of a variational functional encouraging spatial regularity of the depth information. This work must be extended to consider the multiple images available for the same part of the scene. At the opposite, one may want to add color to the point cloud in order to facilitate its visualization. In this case, one point corresponds to one different pixel in each image. Existing softwares generally choose the color from the image having its optical center closer to the point. This simple approach creates color discontinuities that could be avoided by designing a model including visibility and spatial coherency.

Data fusion must also be investigated in the context of structure from motion (SfM). SfM techniques aim at estimating 3D structures from a sequence of 2D images. This is done by first matching images keypoints before computing transformation matrices then used to reconstruct 3D positions of points. The color associated to each point is the one coming from the camera closest to the point, leading to color discontinuities. Here again a global modeling of the problem could enhance the visual quality of the results.

Regularity of the correspondence map

As any image contains local spatial redundancies, it is natural to consider that a correspondence map should be piecewise constant. A uniform area of the image should indeed correspond to an area of the same shape in the image itself or in another image. In particular, [START_REF] Aujol | Exemplar-based inpainting from a variational point of view[END_REF](and later Arias et al., 2012) claim that the correspondence map should be a roto-translation and propose a corresponding variational model that is highly non linear, without any associated algorithm. Without directly regularizing the map, the overlap constraint defined for inpainting in section 2.2 tends to produce piecewise translations. Even without imposing any constraint within the algorithm or the model, we can observe experimentally that patch-based methods naturally tend to produce correspondence maps that are piecewise constant. Figure 4.1 for instance was obtained with the patchmatch algorithm and clearly demonstrates that entire part of Ω are translated onto H to produce the final result. While it could be argued that this is a consequence of the propagation step of the patchmatch algorithm, let us mention that a similar property is also observed with [START_REF] Efros | Texture Synthesis by Non-parametric Sampling[END_REF]. What is noticeable when looking deeply into the correspondance maps generated by any patch-based method is that in between regular pieces lie much smaller areas, that can be as little as isolated pixels. These areas are the ones causing visual artifacts appearing as noise in many restoration results. Controlling regularity of the correspondence map would undoubtedly improve the quality of patch-based restoration methods. A work in that direction was recently proposed for texture synthesis in [START_REF] Gutierrez Ortega | Optimal Patch Assignment for Statistically Constrained Texture Synthesis[END_REF] where the problem is recasted as an optimal assignment of patches with controls on the permutations. This idea should be further explored to more general problems.

State-of-the-art of deep learning approaches for image and video post-production

The objective of image post-production is to generate an output image given an input image and some application related constraints. In deep networks, the way to infer the output given an input is learnt on training images with groundtruth, given low to high level representations (features) of the input. End-to-end networks directly learn how to compute these features at is then iteratively solved. We can observe that this model in fact combines an a priori on the solution resulting from the context encoder, a patch-based term involving correspondence maps, and spatial regularization term. While the results are still blurry, it is a first step for combining patch-based and geometric models together with convolutional neural networks.

Colorization using deep learning

Recently, CNNs have been used in the context of image colorization. The idea is to automatically learn on a database with groundtruth how to colorize a given grayscale image. [START_REF] Cheng | Deep colorization[END_REF], start by extracting and concatenating low, medium and high level semantic features from the grayscale version of the images in the database. They feed these features into a three-layer fully connected neural network trained with a ℓ 2 loss. In order to remove some ambiguities in the training, the database is clustered into scene category and one network is learned per category. During inference, the grayscale image is assigned to its closest category and colorized using the corresponding network. Chrominances are finally refined with joint bilateral filtering [START_REF] Petschnigg | Digital Photography with Flash and No-flash Image Pairs[END_REF] to remove possible artifacts. The method is highly dependent on the categories present during learning. Deshpande et al., 2015, also Constrained Deep Learning based models for image and video post-production.

While proposing impressive results with a very low computational time, current methods based on deep learning still have some limitations. First, we often observe loss in details and color bleeding or blurring along edges. A perspective is to design a framework combining Deep Learning (either CNNs or autocoders), patch-based and variational approaches together. The framework should be robust to the type of degradation (e.g. type of noise in denoising, size of the hole in inpainting) and to be as generic as possible to be less dependent on the application. The corresponding models and loss functions should include i) spatial regularity constraints to avoid blur and color bleeding; ii) features constraints to avoid loss in details, e.g. by comparing the patch representations of inferred images with those of the groundtruth (in the same trend as the post-processing step in (Yang et al., 2017)); iii) visual quality constraints. Several research directions can be followed for this purpose. The first one consists in designing loss functions which include these constraints. Secondly, it is possible to define post-production as the problem of minimizing a variational model for which the data term (or the regularization term) is learnt with deep learning while the regularization term (resp. the data term)is given explicitly. A first work in that direction is [START_REF] Meinhardt | Learning Proximal Operators: Using Denoising Networks for Regularizing Inverse Imaging Problems[END_REF], where the regularization term is modeled implicitely with a neural networks. Authors of [START_REF] Ulyanov | Deep Image Prior[END_REF] also claim that the term regularization term could be drop if the data term is minimized in a space of images generated by a simple CNN.

Secondly, results inferred by networks are highly dependant on the training images. In the context of image restoration, the data are obtained by degrading high resolution images to serve as groundtruth. The degradations applied may not represent correctly originally degraded data. For instance, in case of image colorization, grayscale images obtained by converting a RGB image into luminance are not completely representative of original grayscale images and this is even more true for old photographs (Figure 4.3, third line). One solution is to incorporate into the database images that have been manually restored. The other solution is to design methods that are able to corrupt appropriately the data, as done for instance in the work of [START_REF] Newson | A stochastic film-grain model for resolutionindependent rendering[END_REF] that approximates the physical reality of film grain.

Finally, there are currently very few works using deep learning for video post-production. [START_REF] Ruder | Artistic style transfer for videos[END_REF] rewards consecutive frames that are consistent with each other by defining a temporal loss function based on optical flow computation [START_REF] Revaud | EpicFlow: Edge-Preserving Interpolation of Correspondences for Optical Flow[END_REF]. We will follow this idea to extend deep learning based models from image to video post-production. In parallel, other networks such as Recurrent Neural Networks (RNN), which have shown to be very powerful for video classification, could be studied to be applied for video post-production.

Visual quality assessment

One difficulty when performing image restoration concerns the validation of the results. As soon as the problem is to recover missing data, it is very difficult to perform quantitative evaluation. It is possible to manually remove some contents from an image, restore and compare it to the original image with measures such as PSNR or SSIM [START_REF] Wang | Image Quality Assessment: From Error Visibility to Structural Similarity[END_REF]. Nevertheless, as shown on figure 4.4, a metric such as PSNR does not characterize the plausibility of the result.

Introduction 1 1

 1 Exploiting the self-similarity principle for image post-production 5 1.1 Patch-based texture synthesis . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Measuring similarity between patches . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 Patch-based descriptors . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Similarity metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 From patch-based texture synthesis to patch-based image inpainting . . . . 12 1.4 From patch-based texture synthesis to patch-based image colorization . . . 14 1.4.1 General pipeline for patch-based image colorization . . . . . . . . . 16 1.4.2 Influence of patch representation and metrics . . . . . . . . . . . . . 18 1.4.3 Combining different patch representations to improve patch-based image colorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5 Conclusion and need for non-greedy patch-based methods . . . . . . . . . . 22 2 Patch-based models for image inpainting 25 2.1 Patch-based vs. "Geometric" methods . . . . . . . . . . . . . . . . . . . . . 25 2.1.1 Geometric methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.2 Application to completion of 3D LiDAR point clouds . . . . . . . . 27 2.1.3 Application to the production of orthophotographies from LiDAR point clouds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Combining geometric and patch-based methods . . . . . . . . . . . . . . . 34 v 2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Patch-based models for image colorization 3.1 Diffusion-based manual methods . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Combining patch-based and diffusion methods . . . . . . . . . . . . . . . . 3.2.1 Colorization in the YUV color space . . . . . . . . . . . . . . . . . 3.2.2 Colorization in the RGB color space . . . . . . . . . . . . . . . . . 3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Conclusion and Perspectives 4.1 Fusion of heterogeneous data . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Regularity of the correspondence map . . . . . . . . . . . . . . . . . . . . . 4.3 Deep Learning for image editing . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 State-of-the-art of deep learning approaches for image and video post-production . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Visual quality assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 3 :

 3 Figure 3: Résultat du suivi d'objets (Papadakis et al., 2011) sur une séquence de la base de données PETS 2001. Les couleurs sombres indiquent les parties visibles des objets suivis, les couleurs clairs indiquant les parties occultées.

Figure 6 :

 6 Figure 6: Chaîne de traitements pour l'anonymisation fine de visages (Letournel et al., 2015): (a) image initiale, (b) détection de visages et localisation de repères faciaux, (c) pondération du traitement des zones d'intérêts, (d) segmentation de la tête, (e) résultat du lissage adaptatif.

Figure 0 . 1 :

 01 Figure 0.1: Illustration of the self-similarity principle. An image contains a lot of repetitions of local information.

Figure 1 . 1 :

 11 Figure 1.1: Texture synthesis: the objective is to generate a new texture image from a small texture sample. Figure taken from L.-Y. Wei et al., 2009.

Figure 1 . 2 :

 12 Figure 1.2: Sum of squared differences between texture and smooth patches: d SSD (P 0 , P 1 ) = 5290 ; d SSD (P 0 , P 2 ) = 5443 ; d SSD (P 0 , P 3 ) = 5416; d SSD (P 0 , P 4 ) = 5070.

H

  Figure 1.3: Known and unknown areas for inpainting. Left: original area, Right: known area in white and unknown area in gray.

  Figure 1.4: Patch-based inpainting correction with spatiogram transfer. (a) Original image and the inpainting mask in red. (b) Result obtained with (Criminisi et al., 2004) using patches of size 9 × 9. (c) Post-processing result obtained in (Papadakis et al., 2012).

  CHAPTER 1. EXPLOITING THE SELF-SIMILARITY PRINCIPLE FOR IMAGE POST-PRODUCTION (a) Search of the candidates. (b) Subsampling on a regular grid.

Figure 1 . 6 :

 16 Figure 1.6: Illustration of color prediction. For each pixel of the target image, we search for the closest patch in the luminance channel of the source image and copy the chrominances of the central pixel of this patch onto u (see (a)).To speed up the algorithm, in[START_REF] Welsh | Transferring color to greyscale images[END_REF] the search is not performed among all pixels, but only on a subsampling (see (b)).

  Figure 1.7: Influence of the features on the colorization result.

Figure 1 . 8 :

 18 Figure 1.8: Some colorization results. (a): source image u S (b): target image u T (c): (Charpiat et al., 2008) (results from the website of the authors) (d): (Welsh et al., 2002) (e): (Bugeau et al., 2012)

  Figure 1.10: Illustration of verbatim copy and contour discontinuities arising with onepass greedy patch-based algorithms.

CHAPTER 2 . 2 Figure 2

 222 Figure 2.1: Patch-based vs. "Geometric" methods. These results illustrate the ability of patch-based methods to reconstruct textures and of geometric methods to reconstruct strong structures

2. 1 .

 1 PATCH-BASED VS. "GEOMETRIC" METHODS a very high accuracy. These systems are now widely used for various applications from urban surveying to city modeling. Several systems have been proposed in order to perform these acquisitions. They mostly consist in optical cameras, 3D LiDAR sensor and GPS combined with Inertial Measurement Unit (IMU), put on a vehicle for mobility purposes(Paparoditis et al., 2012, figure 2.2).

Figure 2 . 2 :

 22 Figure 2.2: Scheme of the Stereopolis-II vehicle[START_REF] Paparoditis | Stereopolis II: A multi-purpose and multi-sensor 3D mobile mapping system for street visualisation and 3D metrology[END_REF]

CHAPTER 2 .

 2 Figure 2.3: Disocclusion of a LiDAR point cloud. (left) original point cloud, (center) segmentation, (right) disocclusion.the immediately preceding and succeeding pulses within the same scanline. The second dimension is obtained by ordering the consecutive scanlines, thus corresponding to a temporal dimension. The value at each pixel of the image is the range of the corresponding 3D point. This generated range image can now be processed with image processing algorithm.

Figure 2 . 4 :

 24 Figure 2.4: Range image computation using sensor topology. (left) Sensor topology, (center) Acquired point cloud (Geiger et al., 2013), (right) Corresponding range map.

  Figure 2.5: Definition of the different coordinates systems (left) and η (right).

Figure 2 . 6 :

 26 Figure 2.6: Result of disocclusion of a pedestrian on the KITTI database (Geiger et al., 2013). (a) is the original range image, (b) the segmented pedestrian (dark), (c) the final disocclusion. Depth scale is given in meters.

CHAPTER 2 .

 2 PATCH-BASED MODELS FOR IMAGE INPAINTING a.b.

Figure 2 .

 2 Figure 2.7: Result of the disocclusion of a pedestrian in 3D. (a) is the original mask highlighted in 3D, (b) is the final reconstruction.

  2.1. PATCH-BASED VS. "GEOMETRIC" METHODS proposed a method to produce high resolution orthoimaging for reflectance and height. The proposed framework is summed up in figure 2.8.

Figure 2 .

 2 Figure 2.8: Full orthoimage production pipeline from MLS. Framed rectangles are processing steps, arrows are exchanged data.

Figure 2 . 9 :Figure 2 .

 292 Figure 2.9: Comparison of different diffusion techniques for filling under sampling holes, without filling the occlusion holes. (a) is the point cloud, (b) its projection (rotated for clarity purpose), (c) is the Gaussian diffusion result, (d) is the Perona-Malik algorithm result and (e) is the result of our proposed modification.We can see that our modification of the Perona-Malik algorithm using both height and reflectance information provides a better conservation of big holes while filling perfectly the stripe holes.

2. 2 .

 2 Figure 2.11: Comparison between aerial orthophotography (top) and MLS orthoimage (bottom). The MLS reconstruction contains ∼ 6.10 6 px in which 72% were obtained by diffusion, and 10% by examplar-based inpainting.

  Figure 2.13: Comparison of several inpainting algorithms.(Bugeau et al., 2010a),[START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF] with nl-poisson (with the implementation from[START_REF] Fedorov | Variational Framework for Non-Local Inpainting[END_REF] and Content-Aware fill are able to correctly reconstruct the covered lanterns, the text on these lanterns and the red and white striped bars, while the other previous techniques fail in some of these aspects.

Figure 2 .

 2 Figure 2.14: Comparison of several inpainting algorithms. None of the aforementioned methods provide a satisfying result on this image. therefore proposed by Hays et al., 2007. The semantically closer images in the database are first retrieved before being aligned and composited.There are some limits as seen in figure2.14. In particular, the method highly rely on the semantic retrieval which is likely to fail at recognizing partly occluded objects or non textured areas (for instance pavement in figure 2.14). More recently deep learning has also been used for inpainting purposes[START_REF] Pathak | Context Encoders: Feature Learning by Inpainting[END_REF] Yang et al., 2017) leading to very promising results, though still a little blurry. As discussed in chapter 4, further research could be conducted in this direction even if it is difficult to characterize the solutions to the problem.

Figure 3

 3 Figure 3.1: A result from the manual method of Levin et al., 2004. The color scribbles are propagated to the rest of the image.

FigureFigure 3 . 2 :

 32 Figure 3.2: Comparison of our methods with state-of-the-art results for images with thin structures. On the left, the source image in color and the target image in grayscale. The second column is a zoom-in that better illustrates the importance of the coupled TV.

  Figure 3.3: Colorization result obtained when (c) using only candidates from the automatic patch-based method (d) using only candidates from the scribbles (e) using both. Neither the automatic approach nor the manual one are able to properly colorize this image with the given priors. The unified method gives a suitable result.

2 s

 2 .t. u ∈ [0, 255] 3 and Y = u T and w ∈ W. (3.4) ∀p ∈ Ω Y (p) = A.u(p) with A = (0.2990, 0.5870, 0.1140). The candidates c i are now defined in the RGB space. The important contribution in this work concerns the respect of both constraints u(p) ∈ [0, 255] 3 and Y (p) = u T (p) ∀p. (3.5) This is equivalent to computing a projection ofu(p) onto the intersection of the cube [0, 255] 3 and the affine plan defined by all 3D points having a luminance equal to u T (p) (dark yellow plan on figure 3.5(a)

Figure 3 . 4 :

 34 Figure 3.4: The orthogonal projection of a color (here dark blue) on the constraint {u(p) ∈ [0, 255] 3 and Y (p) = u T (p)} modifies the hue. The color is here projected on light green instead of blue. An oblique projection is able to avoid this issue.

  Figure 3.5: Geometric properties of color spaces. (a) affine plan defined by all colors having a luminance equal to u T (p) (b) Half plan defined by all colors having the same hue as u(p).

Figure 3

 3 Figure 3.6: Illustration of the projection of u(p) onto the constraints.

Figure 4

 4 Figure 4.1: Regularity of the correspondence map. Inpainting of the image with the patchmatch algorithm leads to a correspondence map which is a piecewise translation. Figure taken from (Arias et al., 2012).

4. 3

 3 Deep Learning for image editing Since 2012, deep learning approaches, and in particular Convolutional Neural Networks (CNNs), have become very popular in the community of computer vision and computer graphics. They have been used for various post-production tasks Mao et al., 2016, such as texture synthesis G. Liu et al., 2016, inpainting Pathak et al., 2016, colorization R. Zhang et al., 2016, style transfer Gatys et al., 2016, super-resolution Dong et al., 2014 or denoising K. Zhang et al., 2017. After a long offline training step, they can infer the output images much faster than previous approaches. Instead of relying on an image model, these approaches require a 'training set', made of images and the corresponding expected output images. During the training phase, the parameters of a Deep Network are optimized by minimizing a loss function on the training set, i.e. by comparing the generated output with the groundtruth. Before presenting our perspectives in this context, let us provide a very brief state-of-the-art of deep learning methods for image post-production.

Figure 4 . 2 : 2 + λ 2 ∇u 2 2 (

 4222 Figure 4.2: Illustration of context encoders result. Figure taken from Pathak et al., 2016.

  Figure 4.3: Comparison of the colorization results from our models in RGB (Pierre et al., 2015a) and in YUV Pierre et al., 2014b and from the fully automatic CNN approach of R. Zhang et al., 2016 (files obtained using http: //demos.algorithmia.com/colorize-photos/ ). CNNs provide very impressive results for this task but some artifacts still remain.

  II.1 -Segmentation et suivi par coupe de graphesLors de ma thèse je me suis intéressée à la segmentation et au suivi temporel d'objets en mouvement. Dans ce cadre, une méthode reposant sur la minimisation d'une énergie par un algorithme de coupe minimale/flot maximal dans un graphe a été mise en place. Elle permet de suivre indépendamment chaque objet et regroupe les avantages d'une grande partie des méthodes de suivi existantes. La méthode ainsi créée est capable d'initialiser automatiquement les cibles et gère les entrées et sorties du champ de la caméra. Ceci est possible de part la prise en compte des détections externes d'objets dans l'énergie.

D'autre part, la méthode est robuste aux changements d'illumination et aux changements de topologie des objets. Comme les méthodes de suivi par filtrage, la cohérence temporelle est basée sur l'utilisation dans la fonction d'énergie de la prédiction des objets. Enfin, une deuxième énergie multi-objets a été mise en place afin de séparer les objets ayant pu fusionner au cours de la première minimisation et permettre d'appréhender les problèmes d'occultation partielle

  Utilisation de la méthode SuperPatchMatch pour la segmentation d'images[START_REF] Giraud | SuperPatch-Match: an Algorithm for Robust Correspondences of Superpixel Patches[END_REF].de réaliser une dé-identification fine des visages présents dans une vidéo. Il s'agit de préserver l'anonymat des personnes tout en conservant au maximum les expressions du visage et de manière plus générale les signes de communications non verbaux. Pour réaliser ce travail, j'ai co-encadré G. Letournel, ingénieur d'étude, avec J.-P. Domenger, Pr. LaBRI/Université de Bordeaux, et V.-T. Ta. Dans un premier temps, nous avons étudié les méthodes de détection automatique de visages ainsi que de points caractéristiques sur les visages. Nous avons ensuite proposé une méthode de dé-identification fine sur image fixe reposant sur un lissage adaptatif du visage (figure6). Les yeux et la bouche sont conservés car indispensables à la reconnaissance des expressions. Le nez est supprimé car il aide à la reconnaissance faciale mais pas à celle des expressions. Le reste du visage est lissé avec une force proportionnelle à la distance aux yeux et à la bouche. L'obtention du résultat est obtenu par minimisation d'un modèle variationnel.

	La validation des résultats est une partie très importante de cette thématique de recherche.
	En effet, il faut s'assurer que les personnes sont effectivement correctement anonymisées
	mais également que leurs expressions sont préservées. Cette validation doit être faite par
	des humains mais aussi par des systèmes automatiques. Nous avons ainsi appliqué des
	algorithmes de reconnaissance de visages de l'état-de-l'art pour valider nos résultats. Il
	apparaît que le taux de reconnaissance passe de 86% avant anonymisation à 51% après
	(soit proche du hasard). Pour la validation humaine, nous nous sommes appuyés sur
	les connaissances en tests de perception de chercheurs en sciences cognitiques. Le co-
	encadrement d'un stagiaire avec V. Lespinet Najib, MCF IMS/ENSC a mené à la mise en
	place d'un protocole de test de perception pour la validation des résultats d'anonymisation
	de visages. Le test proposé évalue la reconnaissance de visage puis la reconnaissance des
	émotions. Il a été testé sur un panel de 22 sujets avec des résultats très prometteurs.

J'ai débuté en 2013 une collaboration avec Maria-Caterina Manes Gallo, Pr en Sciences de l'Information et de la Communication à l'université Bordeaux Montaigne et rattachée au laboratoire MICA (Mediation, Information, Communication, Art). L'objectif était

Figure 5:

  Inpainting is the art of filling an unknwon area of an image or a video in a form that is not (easily) detectable by an ordinary observer. It has become a fundamental area of research in image processing with different applications: restoring missing image blocks (error concealment) in telecommunications, removing scratches or dust in movies, adding or removing elements in images or movies, and image extension. It is an old problem in art restoration as medieval artwork started to be restored as early as the Renaissance (as underlined in

	1.3. FROM PATCH-BASED TEXTURE SYNTHESIS TO PATCH-BASED IMAGE
	INPAINTING
	1.3 From patch-based texture synthesis to patch-based
	image inpainting

1.5. CONCLUSION AND NEED FOR NON-GREEDY PATCH-BASED METHODS

2.3. CONCLUSION

To simplify the notations, the dependence of each values to the position of the current pixel is removed.

3.3. CONCLUSION

Note the in(Larsson et al.,

2016) the authors proposed to retrieve either the chrominances values in the Lab color space or the Hue/Chroma in the HSL (Hue-Saturation-Lightness) space but we do not detail further this point in this document

4.4. VISUAL QUALITY ASSESSMENT

Source

Target [START_REF] Welsh | Transferring color to greyscale images[END_REF][START_REF] Irony | Colorization by example[END_REF][START_REF] Charpiat | Automatic Image Colorization via Multimodal Predictions[END_REF][START_REF] Gupta | Image colorization using similar images[END_REF][START_REF] Bugeau | Variational Exemplar-Based Image Colorization[END_REF]Pierre et al., 2014a RGB colorization Figure 3.7: Comparison of the RGB colorization (3.4) including hue constraint (Pierre et al., 2015c) with state-of-the-art methods.

Texture synthesis using deep learning

The problem of texture synthesis can be formulated as follows: given an input sample of texture u S , generate an output image u which apparently contains the same texture as the input one. In [START_REF] Gatys | Texture Synthesis Using Convolutional Neural Networks[END_REF] and later in (G. [START_REF] Liu | Texture synthesis through convolutional neural networks and spectrum constraints[END_REF], it has been shown that texture synthesis can be defined as a constrained optimization problem using statistical features (represented with a Gram matrix) generated by the VGG network pre-trained for object recognition. Given the j th set of features f u ij (p) at layer i of the VGG network applied on image u, the statistical features are defined as:

The final texture image is obtained by iteratively updating image u, starting from a white noise image, in order to minimize:

w ij denoting weights of loss at layer i and feature j. Constraints on the Fourier spectrum were later added in (G. [START_REF] Liu | Texture synthesis through convolutional neural networks and spectrum constraints[END_REF] to better reconstruct low frequency structures.

Inpainting using deep learning

Deep learning-based methods have also been proposed for inpainting. [START_REF] Pathak | Context Encoders: Feature Learning by Inpainting[END_REF] propose an encoder-decoder pipeline to encode the context information and predict the unavailable content with respect to a learned loss function. This pipeline is called Context Encoders. The encoder is a Convolutional Neural Network (CNNs) trained to learn feature maps from Pascal VOC 2007 images [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 (VOC2007) Results[END_REF] in which random regions are automatically removed. From these feature maps, the decoder generates the value of the missing pixels using aother CNN.

As the traditional ℓ 2 loss tends to blur the result by averaging the multiple modes in predictions (Figure 4.2(c)), the authors propose to combine it with an adversarial loss. The adversarial loss is based on a Generative Adversarial Network [START_REF] Goodfellow | Generative Adversarial Nets[END_REF] that jointly learns a generative model of the data distribution together with a discriminative model which provides loss gradients to the generative models. This loss has the effect of picking a particular mode from the data distribution, resulting in less blurry results (Figure 4.2(d)).

The results from this method often lack of texture details leading to blurry areas at the border of the missing area. Yang et al., 2017 proposed another pipeline made of two networks. The first architecture that is limited to scene categories and trained on a small database of 240 images. The success of these two approaches is limited to simple images without foreground objects. Iizuka et al., 2016, train, in an end-to-end fashion, different features which are fed to the colorization network made of a set of up-convolutional layers. A ℓ 2 loss function is used. In order to remove some ambiguities in the learning, the authors add a classification network within their architecture and use a cross-entropy loss for this task. Therefore, once again, even if a very large database is used, the colorization is more likely to fail once an image from a new category has to be colorized.

Instead of predicting pixel chrominances directly, [START_REF] Larsson | Learning Representations for Automatic Colorization[END_REF][START_REF] Zhang | Colorful Image Colorization[END_REF], predict color histograms. The idea lying behind is that many elements in a image can be colorized with many suitable colors. Therefore, they prefer predicting several possible colors per pixel before estimating the final color (as we did since [START_REF] Bugeau | Patch-based image colorization[END_REF]). The colorization process can be formulated:

where F : Ω → [0, 1] N is a mapping function that associates to each pixel p ∈ Ω a probability distribution over N possible chrominance values 1 . The mapping function G : Ω × N → R 2 estimates the final chrominance for each pixel given its own probability distribution. Let us explain how F, G and N are defined in both papers.

In [START_REF] Larsson | Learning Representations for Automatic Colorization[END_REF], N is the number of bins resulting from the discretization of the luminance/chrominance (in Lab color system) axis by evenly spaced Gaussian quantiles. In (R. [START_REF] Zhang | Colorful Image Colorization[END_REF], they quantize the ab space into bins with grid size 10 and keep the N values which are in gamut (i.e. such that the corresponding Lab value belong to the space of existing values in this color space).

In both paper, the mapping functions F are learned with deep networks whose architectures are not discussed here. During training, the input are the grayscale images from a huge database and the output are the quantized histograms of the corresponding color images. In [START_REF] Larsson | Learning Representations for Automatic Colorization[END_REF], the loss function is the cross entropy while in (R. [START_REF] Zhang | Colorful Image Colorization[END_REF], it is a weighted version of this cross entropy. The weights are based on what they call the pixel color rarity and permits rare colors to be predicted.

Once the network has been learned, we can predict, for each pixel of an input grayscale image u T , a distribution of chrominances: h c = F(u T ). The final step of the algorithm is to estimate the final color u c (p) = G (h c (p)). In [START_REF] Larsson | Learning Representations for Automatic Colorization[END_REF], G is either the median or expectation of h c (p) leading to desaturated prediction. In (R. [START_REF] Zhang | Colorful Image Colorization[END_REF], annealed-mean are introduced:

Conclusion and Perspectives

Up to now, the best way to validate the algorithms is to rely on naive human observers (e.g. Turing test). The question generally asked are how realistic are the images. While this is the best evaluation possible, running such a test is highly time consuming and must be adapted each time a new method or experiment is performed. It would be interesting to design methods allowing for automatic validation. Some works already exist for color transfer application [START_REF] Hristova | Perceptual Metric for color transfer methods[END_REF] and could maybe be adapted for colorization. In another trend, [START_REF] Jin | Image aesthetic predictors based on weighted CNNs[END_REF] propose to measure image aestethics using a CNN. Applications of the measures to image post-production can be considered. Furthermore such metric could be added as constraints in all image postproduction models.