Jean-François Aujol

Saïd Ladjal
email: ladjal@enst.fr

Simon Masnou
email: masnou@ann.jussieu.fr

Exemplar-based inpainting from a variational point of view

Among all methods for reconstructing missing regions in a digital image, the so-called exemplar-based algorithms are very efficient and often produce striking results. They are based on the simple idea -initially used for texture synthesis -that the unknown part of an image can be reconstructed by simply pasting samples extracted from the known part. Beyond heuristic considerations, there have been very few contributions in the literature to explain from a mathematical point of view the performances of these purely algorithmic and discrete methods. More precisely, a recent paper by Levina and Bickel [64] provides a theoretical explanation of their ability to recover very well the texture, but nothing equivalent has been done so far for the recovery of geometry. Our purpose in this paper is twofold:

1. To propose well-posed variational models in the continuous domain that can be naturally associated to exemplar-based algorithms;

2. To investigate their ability to reconstruct either local or long-range geometric features like edges.

In particular, we propose several optimization models in R N , we discuss their relation with the original algorithms, and show the existence of minimizers in the framework of functions of bounded variation. Focusing on a simple 2D situation, we provide experimental evidences that basic exemplar-based algorithms are able to reconstruct a local geometric information whereas the minimization of the proposed variational models allows a global reconstruction of geometry and in particular of smooth edges. The derivation of globally minimizing algorithms associated to these models is still an open problem. Yet the results presented in this paper are a first step towards new inpainting algorithms with an improved quality of geometry reconstruction and no loss of quality for texture reconstruction.

Introduction

Image inpainting has become a generic term to refer to the process of restoring missing and/or damaged areas in digital images. The problem can be stated as follows : given a region A to be restored, use the valid surrounding information for synthesizing the most plausible data in A. Several classes of methods have been developed in the past ten years. In the first category of approaches, the focus has been on recovering the geometry. One of the very first contributions in this direction is [START_REF] Masnou | Level lines based disocclusion[END_REF] (see also [START_REF] Masnou | Disocclusion : a variational approach using level lines[END_REF]), where the geometry is recovered in a way similar to our brain's ability to "see" occluded contours, the so-called amodal completion process studied by G.Kanizsa [START_REF] Kanizsa | Organization in Vision: Essays on Gestalt Perception[END_REF] and 1 introduced in the context of digital image interpretation in [START_REF] Nitzberg | The 2.1-D Sketch[END_REF]. The model proposed in [START_REF] Masnou | Level lines based disocclusion[END_REF] is variational and related to generalizations of the celebrated Willmore functional [START_REF] Ambrosio | A direct variational approach to a problem arising in image reconstruction[END_REF]. The word inpainting has appeared for the first time in this context in [START_REF] Bertalmio | Image inpainting[END_REF], where a PDE model has been proposed to model a convection of the valid information from outside the inpainting domain towards the inside, in the spirit of the real "inpainting" operation used by conservators in art restoration. In the subsequent years, many contributions have been proposed, either variational or involving a PDE [START_REF] Ballester | Filling-in by joint interpolation of vector fields and gray levels[END_REF][START_REF] Chan | Mathematical models for local deterministic inpaintings[END_REF][START_REF] Chan | Non-texture inpainting by curvature-driven diffusion (CDD)[END_REF][START_REF] Chan | Euler's elastica and curvature based inpainting[END_REF][START_REF] Esedoglu | Digital image inpainting by the Mumford-Shah-Euler image model[END_REF][START_REF] Grossauer | Using the complex Ginzburg-Landau equation for digital inpainting in 2D and 3D[END_REF][START_REF] Oliveira | Fast digital image inpainting[END_REF][START_REF] Bertozzi | Inpainting of binary images using the cahn-hilliard equation[END_REF][START_REF] Bertalmio | Navier-stokes, fluid dynamics and image and video inpainting[END_REF][START_REF] Auroux | A one-shot inpainting algorithm based on the topological asymptotic analysis[END_REF][START_REF] Galić | Image compression with anisotropic diffusion[END_REF][START_REF] Rares | Edge-based image restoration[END_REF]. To our best knowledge, the most efficient methods falling in the category of variational/PDE approaches are [START_REF] Tschumperlé | Fast anisotropic smoothing of multi-valued images using curvature-preserving PDE's[END_REF], which gives very nice results when the parameters have been carefully chosen and, most of all, [START_REF] Bornemann | Fast image inpainting based on coherence transport[END_REF] which is a very efficient, fast and reliable method based on the combination of a first order advection equation and a fast marching algorithm. The drawbacks of all these methods is their well-known incapacity to restore texture.

In parallel to these geometry-oriented approaches and roughly at the same time, the late 90's, a category of very powerful methods have appeared in the context of texture synthesis. Before then, the traditional way to texture synthesis was to model the texture as a Markov Random Field, to learn its statistics on the known part of the image and to resample it on the unknown part [START_REF] Besag | Spatial interaction and the statistical analysis of lattice systems[END_REF][START_REF] Cross | Markov random fields texture models[END_REF]. Other approaches try to constrain different kinds of statistics or inter-scale dependencies [START_REF] De | Multiresolution sampling procedure for analysis and synthesis of texture images[END_REF][START_REF] Heeger | Pyramid based texture analysis/synthesis[END_REF][START_REF] Simoncelli | Texture characterisation via joint statistics of wavelet coefficient magnitudes[END_REF]. The main drawbacks of all these methods are their inability to reproduce large-scale structured patterns and the well-known difficulty to find the correct parameters. In contrast, the so-called exemplar-based methods that were initially proposed in [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF][START_REF] Freeman | Learning low-level vision[END_REF][START_REF] Wei | Fast texture synthesis using tree-structured vector quantization[END_REF], appear to be much more efficient. They basically exploit the locality and the stationarity at a certain scale of any texture. 1The first celebrated algorithms in the class of exemplar-based methods, due to Efros and Leung on one hand [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF], Wei and Levoy on the other hand [START_REF] Wei | Fast texture synthesis using tree-structured vector quantization[END_REF], both involve the notion of patch, i.e. a square window of size r × r, and use as the distance between two patches Γ(p), Γ(q) centered at p, q the sum of squared differences :

D(Γ(p), Γ(q)) = i∈[-r,r] 2 ∩Z k∈{1,2,3} |I k (p + i) -I k (q + i)| 2
where I = (I 1 , I 2 , I 3 ) maps a pixel onto a vector value in any color representation, for instance RGB, YCrCb or Lab. To synthesize a pixel p at the boundary of the unknown domain, the algorithm picks one central value I(q) among all patches Γ(q) with smallest distance to Γ(p). This core algorithm is proposed with different variants in [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF] and [START_REF] Wei | Fast texture synthesis using tree-structured vector quantization[END_REF], see also [START_REF] Harrison | A non-hierarchical procedure for re-synthesis of complex texture[END_REF][START_REF] Bornard | Missing data correction in still images and image sequences[END_REF]: a multiscale approach, a random selection of the central value among a larger class of patches, a careful synthesis order, etc. All these papers are essentially dedicated to texture synthesis, yet an example of inpainting is given in [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF]. Previously, a parametric synthesis approach had been proposed in [START_REF] Igehy | Image replacement through texture synthesis[END_REF] for illustrating an inpainting application. To the best of our knowledge, the first explicit and systematic application to inpainting of a non parametric synthesis method can be found in [START_REF] Bornard | Missing data correction in still images and image sequences[END_REF]. Despite the great improvements with respect to the previous contributions to texture synthesis and despite the huge quantity of variants that have been proposed, a well-known problem of the exemplar-based methods that we have mentioned comes from the synthesis of only one pixel at a time, which may sometimes result in "cycling" effects like the constant propagation of an erroneous synthesis or the formation of much too repetitive patterns. Surprisingly, because it amounts to reduce the space of interpolation possibilities, much better results can be obtained by synthesizing not only the central pixel but entire patches. It also considerably reduces the computational time. Many contributions have been proposed in this direction with several variants [START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF][START_REF] Guo | Chaos mosaic: fast and memory efficient texture synthesis[END_REF][START_REF] Liang | Real-time texture synthesis by patch-based sampling[END_REF][START_REF] Criminisi | Object removal by exemplar-based inpainting[END_REF][START_REF] Drori | Fragment-based image completion[END_REF][START_REF] Pérez | PatchWorks: Example-based region tiling for image editing[END_REF][START_REF] Jia | Image repairing: Robust image synthesis by adpative ND tensor voting[END_REF][START_REF] Wexler | Space-time completion of video[END_REF][START_REF] Komodakis | Image completion using efficient belief propagation via priority scheduling and dynamic pruning[END_REF][START_REF] Ashikhmin | Synthesizing natural textures[END_REF]]:

• on the location of the patches to be synthesized (using a fixed grid or not, with either no overlap, a smooth or a sharp overlap between adjacent patches),

• on the filling order (raster scan, concentric layers, incorporation of geometric or intensity constraints),

• on the searching domain (reinitialized at each iteration or constrained by the previously chosen sample patch),

• on the distance between patches and the way to find a minimizing candidate (enumeration, belief propagation, etc.),

• on the artificial extension of the space of samples by introducing rotated and rescaled versions of the existing patches.

The results are often amazing (see for instance Figure 1) and can be obtained in a very reasonable time, even for large inpainting domains, if suitable cost-reducing techniques are used (for instance restricting the computation to a fixed grid of patches). Most approaches in this category are not only able to reproduce a texture but are also very good at restoring a geometric information whenever it can be obtained elsewhere in the image. In the case when the interpolation requires the synthesis of a new geometry or a long-range geometry that does not appear elsewhere, some additional, geometry-oriented steps are necessary. Different approaches have been proposed in combination with an exemplar-based inpainting, either based on a manual intervention by the user [START_REF] Sun | Image completion with structure propagation[END_REF], or trying to combine texture and geometric interpolation in the most automated possible way [START_REF] Bertalmio | Simultaneous structure and texture image inpainting[END_REF][START_REF] Cao | Geometrically guided exemplar-based inpainting[END_REF][START_REF] Drori | Fragment-based image completion[END_REF][START_REF] Ni | Variational PDE-based image segmentation and inpainting with applications in computer graphics[END_REF].

Figure 1: An image with several missing domains and the reconstruction with the method from [START_REF] Pérez | PatchWorks: Example-based region tiling for image editing[END_REF].

Until now, we have described three classes of inpainting methods : the geometry-oriented, the exemplar-based and the hybrid methods. A fourth category gathers all approaches involving the optimization of one or several criterions in a transform domain, e.g. Fourier, wavelet or framelet domain, see for instance [START_REF] Hirani | Combining frequency and spatial domain information for fast interactive image noise removal[END_REF][START_REF] Cai | A framelet-based image inpainting algorithm[END_REF][START_REF] Chan | Total variation wavelet inpainting[END_REF] and the inspiring [START_REF] Elad | Simultaneous cartoon and texture image inpainting using Morphological Component Analysis[END_REF] (see also [START_REF] Guleryuz | Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising: Part I -Theory[END_REF][START_REF] Guleryuz | Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising: Part II -Adaptive algorithms[END_REF]) where a simultaneous geometry/texture inpainting is performed by optimizing suitable mappings onto different transform domains, one giving a sparse representation of the geometry (the curvelets domain) and the other adapted to the texture (the DCT domain).

Among all the works we have cited, some of them have been first formulated as variational, PDE or stochastic models in the continuous domain. This may help understanding, at least partially, the pros and cons of the method. The continuous formulation may also give rise to different discretizations whose quality and performances can be discussed on a theoretical basis.

The case of the exemplar-based methods is different: they all start from a discrete algorithm whose performances can be experimentally observed. These approaches are obviously very efficient despite well-known limitations, for example the crucial dependence to an appropriate choice of patches' size, the difficulty to adapt this size locally, the difficulty to find a filling order that fits anywhere in the image, etc. The major reason why it works so well most of the time is obvious: to synthesize something similar to a given sample, it is enough to copy it or part of it. This subjective statement has been confirmed by theoretical arguments in a very inspiring paper due to Levina and Bickel [START_REF] Levina | Texture synthesis and non-parametric resampling of random fields[END_REF]. The authors prove indeed that if a texture sample is modeled as a Markov Mesh Model (a variant of Markov Random Fields) and its size goes to infinity then the following properties hold for the texture synthesized with an algorithm similar to Efros-Leung's :

1. the joint distribution of the pixels in any r × r window 2. and the conditional distribution of the lower right pixel of any r × r window with respect to the other pixels of the window converge to the distributions of the observed texture. Interestingly, the authors claim that this result is a theoretical justification of the visually good performances of Efros-Leung's algorithm since, according to the theories of human perception, the joint distribution of pixels in a window is a key quantity to measure how much two textures are visually similar [START_REF] Julesz | Visual pattern discrimination[END_REF][START_REF] Julesz | Textons, the elements of texture perception and their interactions[END_REF][START_REF] Julesz | Inability of humans to discriminate between visual textures that agree in second-order statistics -revisited[END_REF][START_REF] Malik | Preattentive texture discrimination with early vision mechanism[END_REF]. The work of Levina and Bickel is a stochastic approach to understand the performances of exemplar-based inpainting for the synthesis of texture. Our motivation to address these methods from the point of view of analysis was twofold:

1. to provide a global variational interpretation in the continuous domain; 2. to explain, from a variational point of view, the ability of the method to recover a geometric information and to characterize the type of geometry that can be recovered.

We believe indeed that exemplar-based methods are naturally variational for the simple reason that finding a patch that minimizes a distance to another given patch is already a variational task.

To our best knowledge, the analytical modeling of exemplar-based methods has not been explicitly addressed in the literature, except the interesting model proposed by L. Demanet, B. Song and T. Chan in [START_REF] Demanet | Image inpainting by correspondence maps: A deterministic approach[END_REF] that we will detail later on and that has been the starting point of our work.

Although not dedicated to the same problem, the non local TV model of G. Gilboa and S. Osher could be also an interesting candidate because it involves a metric between patches. Denoting the image domain as Ω, the inpainting domain as A ⊂ Ω and reformulating the type of energy proposed in [START_REF] Gilboa | Nonlocal operators with applications to image processing[END_REF] to fit our problem, we could indeed look for the function u that coincides with the original image u 0 outside A and minimizes the energy

A Ω\A |u(x) -u(y)| 2 w(x, y)dy dx where w(x, y) = exp - G σ * |u(x + •) -u(y + •)| 2 (0) h 2
with G σ a smoothing kernel and h > 0 a filtering parameter. This energy is defined for a gray scale image but it could be easily extended to color images. Anyway, this model is actually too far from exemplar-based inpainting for it does not particularly favor rigid copies of entire patches. Analogously, energies similar to the Non Local Means of A. Buades, T. Coll and J.-M Morel [START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF] could be proposed coupled with additional rigidity constraints. This is in some sense the spirit of the denoising model in [START_REF] Tschumperlé | Defining some variational methods on the space of patches: Application to multi-valued image denoising and registration[END_REF] (see also [START_REF] Peyré | Manifold models for signals and images[END_REF]) that can be adapted to inpainting. In a work in preparation, P. Arias and V. Caselles [START_REF] Arias | Iterative non-local methods for image inpainting[END_REF] show the efficiency of such approach both for texture and geometry recovery. However, these models cannot be considered as the exact counterparts in the continuous domain of exemplar-based algorithms since they are basically related to a non rigid process in contrast to the rigid copy of patches.

A variational model that fits much more with the spirit of exemplar-based algorithms has been proposed by Demanet, Song and Chan in [START_REF] Demanet | Image inpainting by correspondence maps: A deterministic approach[END_REF] and, as mentioned before, it has been the starting point of our work. The presentation of the model in [START_REF] Demanet | Image inpainting by correspondence maps: A deterministic approach[END_REF] is somewhat informal and prospective but can be rephrased as follows: again, let us denote the image domain as Ω, the inpainting domain as A and the original image as u 0 : Ω \ A → R. Demanet, Song and Chan propose to find an optimal correspondence map T : A → Ω \ A that minimizes (in a space that the authors do not specify) the criterion

F 1 (T ) = A Br(0)
|u 0 (T (x + y)) -u 0 (T (x) + y)| 2 dy dx, where B r (0) stands for the ball of radius r centered in 0. Remark that the problem is not rigorously formulated since T (x+y) is not defined when x+y ∈ A and u 0 (T (x)+y) is also not defined whenever T (x) + y ∈ A. Let us keep for the moment an informal point of view. Once a minimizer T has been found -whenever it exists -the interpolated image can be defined in A as u 0 (x) = u 0 (T (x)), ∀x ∈ A. This model is designed for gray level images but can be easily extended to color images. Let us comment on the criterion: since the image on A is defined by u 0 (x) = u 0 (T (x)), we can rewrite the energy, once a minimizer T has been found, as

F 1 ( T ) = A Br(0) u 0 (x + y) -u 0 ( T (x) + y) 2 dy dx
which corresponds exactly to penalizing the distance at each point x between the patches B r (x) and B r ( T (x)). An additional term is proposed in [START_REF] Demanet | Image inpainting by correspondence maps: A deterministic approach[END_REF] in order to favor local rigidity of T which gives the second criterion:

F 2 (T ) = A Br(0) |u 0 (T (x + y)) -u 0 (T (x) + y)| 2 dy dx + α A ∇T (x) -I dx
This new energy tends to favor T to be close to a translation. As mentioned before, the definitions of F 1 and F 2 given in [START_REF] Demanet | Image inpainting by correspondence maps: A deterministic approach[END_REF] are ambiguous since nothing is said about the definition of T (x + y) if x + y ∈ A and the definition of u 0 (T (x) + y) if T (x) + y ∈ A. Now, T cannot be freely chosen otherwise the minimization of F 1 and F 2 would be trivial. Indeed, both F 1 and F 2 vanish for any translation T c (x) = x + c such that T c (A) ⊂ Ω \ (A + B r ). The formulation that we will propose later incorporate additional assumptions in order to make the problem less trivial but the spirit remains the same. To be complete, let us also recall that a third model has been proposed in [START_REF] Demanet | Image inpainting by correspondence maps: A deterministic approach[END_REF] that incorporates the total variation of the interpolated u 0 on A. The motivation was to favor a better reproduction of the geometrical features. We observe however that minimizing the total variation is not compatible with a good recovery of texture, which is the core of all exemplar-based inpainting approaches. But it can make sense in the context of geometry+texture decomposition, as will be seen later.

We will now revisit the first model of [START_REF] Demanet | Image inpainting by correspondence maps: A deterministic approach[END_REF] and give a well posed formulation in any dimension N ≥ 2 that fits our original intention to provide a global variational interpretation in the continuous domain of exemplar-based inpainting algorithms. The underlying main idea is to mimic the exemplar-based methods where pieces of patches are pasted, not only the central pixel, see for instance [START_REF] Liang | Real-time texture synthesis by patch-based sampling[END_REF][START_REF] Pérez | PatchWorks: Example-based region tiling for image editing[END_REF][START_REF] Criminisi | Object removal by exemplar-based inpainting[END_REF]. These methods are sometimes called patch-based. They usually involve only translations of patches but more geometrical features can be recovered if we also introduce rotated patches. So the model we have in mind actually picks pieces of patches in Ω \ A, then rotates and translates them onto A. The overall mapping T is thus a piecewise roto-translation from A to Ω \ A, i.e. T can be decomposed as

T (x) = i∈I R i (x -c i )1 A i
where {A i } i∈I is a partition of A and, for each i ∈ I, R i is a rotation matrix and c i a translation vector.

Let us denote by B r (x) the ball centered in x and with radius r. If the interpolated image in A is defined by u 0 (x) = u 0 (T (x)) for all x ∈ A then a global measure of the distance at each point x between a patch B r (x) and its image B r (T (x)) can be written as A Br(0) |u 0 (x + y) -u 0 (T (x) + ∇T (x) y)| 2 dy dx since, denoting by T x the value of T at x and R x , c x the associated rotation matrix and translation vector, one has

T x (x + y) = R x (x + y -c x ) = T x (x) + R x y = T x (x) + ∇T x y.
Let us turn back to the situation where u 0 is known only outside A. Once T is given, u 0 can be defined on A through the formula u 0 (x) = u 0 (T (x)) for all x ∈ A. One thus gets the criterion A Br(0) |u 0 (T (x + y)) -u 0 (T (x) + ∇T (x) y)| 2 dy dx that depends only on T and coincides with the criterion F 1 of Demanet, Song and Chan when T is a piecewise translation. Like for F 1 , we must prevent T from being a global translation to avoid trivial minimizers. We shall also incorporate the knowledge of the data in a band around A, not only on the boundary ∂A. This is done using a criterion that penalizes the correspondence map T not only on A but on an extended domain A + B r where B r denotes the ball B r (0). Finally, the main criterion that we propose is

• u 0 given on Ω \ A; • T (A + B r ) ⊂ Ω \ (A + B r ); • T = Id on Ω \ (A + B r );
We will show that E 1 can be minimized in the class of piecewise roto-translations from Ω onto itself and we will study several variants.

Plan of the paper

In Section 3, we recall a few definitions and results for BV, SBV and sets of finite perimeter (see [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF] for a detailed treatment of the subject). Section 4 is devoted to the definition of piecewise rototranslations and the proof of a compactness theorem. It is shown in Section 5 that there exists at least a solution to the minimization of Model I, then the uniqueness is discussed as well as the connections of the model with the original algorithm. In Section 6, we propose several extensions with additional first-order terms that focus on the reconstruction of the geometry. In the first variant (Model II), the regularization term concerns the whole image, while in the second variant (Model III) only the geometric part of the image is penalized. A third variant (Model IV) is proposed with a control by the Willmore functional of the geometric part of the reconstruction.

We compare in Section 7 on a particular 2D situation the performances for the reconstruction of geometry of Models I and II on one hand and basic patch-based algorithms on the other hand. We obtain numerical evidences that Models I and II are more efficient for reconstructing certain longrange geometric features, like for instance long edges, straight or non straight. An open problem is the design of algorithms for the global minimization of Models I and II. The numerical results of Section 7 might indicate that such algorithms would outperform the usual patch-based techniques for the reconstruction of geometry without any loss of quality for the reconstruction of texture.

We eventually propose in Section 8 modifications of Models II and III that fulfill some properties of invariance with respect to multiplicative contrast changes or joint rescalings of the image domain, the inpainting domain and the reference patch. We also discuss their asymptotic behaviours as the size of the patch goes to zero.

BV, SBV and sets of finite perimeter

We refer the interested reader to [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF] for a full introduction to the theory of functions of bounded variation. The spaces BV and SBV naturally appear when dealing with functionals with linear growth at infinity. Contrary to the classical Sobolev space W 1,1 , they enjoy very useful compactness properties. The purpose of this section is to provide the reader non familiar with these notions with the material necessary for this paper. All definitions and properties enumerated below are taken from [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF].

In what follows, Ω denotes an open bounded subset of R N with Lipschitz boundary. Definition 3.1 (BV) A function u ∈ L 1 (Ω, R) has bounded variation if its distributional derivative can be represented by a vector-valued Radon measure Du

= (D 1 u, • • • , D N u), i.e. Ω u divφ dx = - N i=1 Ω φ i dD i u ∀φ ∈ C 1 c (Ω, R N )
The total variation of u is defined as

|Du|(Ω) = sup N i=1 Ω u ∂φ ∂x i dx, φ ∈ C 1 c (Ω, R N ), φ ∞ ≤ 1
The space of functions of bounded variation in Ω is denoted as BV(Ω).

This definition can be extended to vector-valued functions, i.e. u ∈ BV(Ω, R m ) if u ∈ L 1 (Ω, R m ) and the distributional derivative of u can be represented as a m × N matrix of measures

D j i satisfying m j=1 Ω u j divφ j dx = - m j=1 N i=1 Ω φ j i dD i u j , ∀φ ∈ C 1 c (Ω, R mN )
Recall that any function u ∈ L 1 (Ω) is approximately continuous L N -almost everywhere in Ω, i.e. for a.e. x ∈ Ω, there exists z ∈ R such that Notice that strict convergence implies weak- * convergence but the converse is false in general.

Functions in BV can have a very complicated distributional derivative [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF] and it is often interesting to restrict oneself to a subspace of BV, the class SBV of special functions of bounded variation, that is composed of all BV functions whose distributional derivative has no Cantor part. Definition 3.5 (SBV) A function u ∈ BV(Ω) is a special function of bounded variation if its distributional derivative can be decomposed as

Du = ∇uL N + (u + -u -)ν u H N -1 S u
where S u denotes the approximate discontinuity set, u ± the approximate upper and lower limits of u on S u , ν u the generalized normal to S u defined as lim r↓0 Du(Br(x)) |Du|(Br(x)) , ∇u the approximate gradient of u and H N -1 the N -1-dimensional Hausdorff measure.

The space of special functions of bounded variation in Ω is denoted as SBV(Ω).

Again, this definition can be extended to vector-valued functions and we say that

u ∈ SBV(Ω, R m ) if u ∈ BV(Ω, R m ) and Du = ∇uL N + (u + -u -) ⊗ ν u H N -1 S u .
A very useful compactness theorem due to L. Ambrosio holds in SBV [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF]:

Theorem 3.6 (Compactness in SBV) Let (u n ) n∈N be a sequence of functions in SBV(Ω) such that sup n∈N u n ∞ + Ω ϕ(|∇u n |)dx + H N -1 (S un ) < ∞ where ϕ : [0, ∞[→ [0, ∞]
is a lower semicontinuous, increasing and convex function such that lim t→∞ ϕ(t) t = ∞. Then there exists a subsequence (u h(n) ) n∈N , and a limit function u ∈ L ∞ (Ω) ∩ SBV(Ω) such that

• u h(n) weakly- * converges to u in BV(Ω), • ∇u h(n) weakly converges to ∇u in L 1 (Ω, R N ), • Ω ϕ(|∇u|)dx ≤ lim inf n→∞ Ω ϕ(|∇u h(n) |)dx, • H N -1 (S u ) ≤ lim inf n H N -1 (S u h(n) ).
We shall use later in a proof the notion of trace of BV functions. Let us recall the definition and a couple of important properties [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF]. Theorem 3.7 (Boundary trace theorem) Let u in BV(Ω). Then, for H N -1 almost every x in ∂Ω, there exists T u(x) ∈ R such that:

lim ρ→0 1 ρ N Ω∩Bρ(x) |u(y) -T u(x)| dy = 0 Moreover, T u L 1 (∂Ω) ≤ C u BV(Ω)
for some constant C depending only on Ω. The extension ũ of u to 0 out of Ω belongs to BV(R N ), and viewing Du as a measure on the whole of R N and concentrated on Ω, Dũ is given by :

Dũ = Du + (T u)ν Ω H N -1 ∂Ω
with ν Ω the generalised inner normal to ∂Ω.

Let us now state the different definitions and results that will be useful to define and manipulate piecewise roto-translations. In the BV context, there is a tool particularly suitable for this: the Caccioppoli partitions, which rely on the notion of sets of finite perimeter. Definition 3.8 (Sets of finite perimeter) We say that a measurable set A ⊂ R N has finite perimeter in Ω if 1 A ∈ BV(Ω). The perimeter of A in Ω is defined by

P (A, Ω) = |D1 A |(Ω)
and satisfies

P (A, Ω) = H N -1 (∂ * A ∩ Ω)
where

∂ * A := S 1 A is called the essential boundary of A.
Theorem 3.9 (Coarea formula in BV) If u ∈ BV(Ω), then the set {u > t} has finite perimeter in Ω for a.e. t ∈ R, and for any Borel set B ⊂ Ω we have

|Du|(B) = +∞ -∞ P ({u > t}, B)dt
By partition of a measurable set E ⊂ R N we mean a countable collection of measurable sets

E i ⊂ R N such that E = ∪ i E i up to a Lebesgue negligible set and |E i ∩ E j | = 0, i = j. Definition 3.10 (Caccioppoli partitions) Let Ω ⊂ R N be an open set and I ⊂ N; we say that a partition {E i } i∈I of Ω is a Caccioppoli partition if i∈I P (E i , Ω) < ∞. We say that a Caccioppoli partition is ordered if |E i | ≥ |E j | whenever i ≤ j. Given a (H N -1 , N -1)-rectifiable set K ⊂ Ω, we say that a Caccioppoli partition {E i } i∈I of E is subordinated to K if, ∀i, ∂ * E i ⊂ K up to a H N -1 -negligible set. Remark 3.11 By Theorem 4.17 in [2], if {E i } i∈I is subordinated to K then i∈I P (E i , Ω) ≤ 2H N -1 (K). Theorem 3.12 (Compactness of Caccioppoli partitions) Let {E i,n } i∈I , n ∈ N be Cacciop- poli partitions of a bounded open set Ω with Lipschitz boundary such that sup i∈I P (E i,n , Ω) : n ∈ N < ∞.
Then, if either I is finite or the partitions are ordered, there exists a Caccioppoli partition {E i } i∈I and a subsequence (h(n)) such that (E i,h(n) ) converges in measure to E i for any i ∈ I.

Definition 3.13 (Piecewise constant functions) We say that

u : Ω → R m is piecewise con- stant in Ω if there exists a Caccioppoli partition {E i } i∈I of Ω and a collection {t i } i∈I ⊂ R m such that u = i∈I t i 1 E i . Theorem 3.14 (Characterization of piecewise constant functions) Let u ∈ [L ∞ (Ω)] m . Then, u is (equivalent to) a piecewise constant function if and only if u ∈ [SBV(Ω)] m , Du is concentrated on S u and H N -1 (S u ) < ∞.
Moreover, denoting by {E i } i∈I the level sets of u and t i the associated values (i.e.

E i = {x ∈ Ω : u(x) = t i }) we have u = i t i 1 E i , ∂ * E i ⊂ S u for all i up to H N -1 negligible sets and 2H N -1 (S u ) = i∈I P (E i , Ω). Theorem 3.15 (Compactness of piecewise constant functions) Let (u n ) ⊂ [SBV(Ω)] m be a sequence of piecewise constant functions such that ( u n ∞ + H N -1 (S un )) is uniformly bounded.
Then, there exists a subsequence (u h(n) ) converging in L 1 to a piecewise constant function.

Piecewise roto-translations

We give in this section a suitable definition of piecewise roto-translations and we prove a compactness theorem that will be useful in subsequent proofs. In the sequel, SO(N ) denotes the special orthogonal group of all rotations in R N .

Definition 4.1 (Piecewise roto-translations) We say that u ∈ SBV(Ω, R N ) is a piecewise roto-translation in Ω if there exists a Caccioppoli partition {E i } i∈I of Ω and R i ∈ SO(N ), t i ∈ R N , i ∈ I, such that, for a.e. x ∈ Ω u(x) = i∈I (R i x + t i )1 E i (x)
Remark 4.2 Notice that if u is a piecewise roto-translation, then

S u ⊂ ∪ i∈I ∂ * E i up to a H N -1 negligible set. This is a consequence of |E i ∩ E j | = 0, i = j
and of the fact that, by Theorem 4.17 in [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF],

i∈I

(E i ) 1 ∪ i,j∈I, i =j ∂ * E i ∩ ∂ * E j contains H N -1 -almost all of Ω. Remark 4.3 We use the term roto-translation despite the fact that x → R i x + t i is simply the rotation x → R i (x + R -1 i t i ) of center -R -1 i t i .
Actually, for the sake of clarity, we prefer keeping 0 as the unique reference center so that, in the sequel, we will always mean by roto-translation the combination of a translation and a rotation with respect to 0. Theorem 4.4 (Compactness of piecewise roto-translations) Let (u n ) ⊂ SBV(Ω, R N ) be a sequence of piecewise roto-translations associated with Caccioppoli partitions {E i,n } i∈In such that ( u n ∞ + i∈In P (E i,n , Ω)) is uniformly bounded. Then, there exists a subsequence (u h(n) ) converging in L 1 to a piecewise roto-translation.

Proof By assumption, for each n ∈ N, there exists a Caccioppoli partition

{E i,n } i∈In of Ω such that u n (x) = i∈In (R i,n x + t i,n )1 E i,n (x) where R i,n ∈ SO(N ) and t i,n ∈ R N . Since S un ⊂ ∪ i∈In ∂ * E i,n (see Remark 4.
2) we deduce from the assumptions that sup n∈N H N -1 (S un ) < +∞. By the compactness theorem in SBV there exists a subsequence, still denoted as (u n ), that converges in L 1 (Ω) to u ∈ SBV(Ω, R N ). Using a common set I for the indices of the Caccioppoli partitions -possibly adding sets of measure zero -we order each partition and recall that by assumption sup n∈N i∈I P (E i,n , Ω) < +∞. By the compactness theorem for Caccioppoli partitions (Theorem 3.12) and possibly taking a subsequence still denoted as (E n ), there exists a limit Caccioppoli partition {E i } i∈I such that (E i,n ) converges in measure to E i for any i ∈ I. As in the proof of Theorem 4.25 in [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF], for any ǫ > 0 there exists an integer M depending only on ǫ such that

Ω \ M i=1 E i,n < ǫ, ∀n ∈ N (1)
By a diagonal argument, we can assume that (R i,n ) converges to R i ∈ SO(N ) and (t i,n ) converges to t i ∈ R N for any i ∈ I. Hence, for every δ > 0, there exits n 0 ∈ N such that for every n ≥ n 0

M i=1 |E i,n ∆E i | < ǫ, sup 1≤i≤M |t i,n -t i | < δ and sup 1≤i≤M |R i,n -R i | < δ. Defining v = i∈I (R i x + t i )1 E i , we deduce that there exists a constant C 1 such that |{|u n -v| > δ}| < C 1 ǫ
and since ǫ is arbitrary we conclude by the uniqueness of the limit that

u = i∈I (R i x + t i )1 E i
and the theorem follows.

The following result due to Chambolle, Giacomini and Ponsiglione [START_REF] Chambolle | Piecewise rigidity[END_REF] provides an interesting characterization of piecewise roto-translations that is useful to study the links between rigidity and elastic energy in the context of fracture mechanics. This result could be used to give another proof of the compactness theorem above. We essentially mention it because it is, together with the paper by Demanet, Song and Chan, at the origin of the work presented here: it convinced us that SBV and the Caccioppoli partitions are the appropriate tools for representing and manipulating piecewise roto-translations. Theorem 4.5 (Chambolle, Giacomini, Ponsiglione [START_REF] Chambolle | Piecewise rigidity[END_REF])

If u ∈ SBV(Ω, R N ) is such that H N -1 (S u ) < ∞ and ∇u(x) ∈ SO(N ) for L N -a.e. x ∈ Ω, then there exists a Caccioppoli par- tition (E i ) i∈I subordinated to S u such that u = i∈I (R i x + t i )1 E i where R i ∈ SO(N ) and t i ∈ R N . A Br(T (x)) Br(x) inpainting domain Ω image domain
Figure 2: The original image u 0 is defined on Ω \ A and must be reconstructed in A.

Analysis of Model I

We prove in this section that the functional E 1 involved in Model I is continuous and admits a minimizer in an appropriate space.

The image domain and the inpainting domain are represented by two open bounded subsets A ⊂ Ω ⊂ R N with Lipschitz boundaries (see Figure 2). We assume in addition that there exists r > 0 such that A + 3B r ⊂ Ω where here and in the sequel B r denotes the ball B r (0). The original image u 0 is defined on Ω \ A. Let C > 0 be such that the set

V 1 = T ∈ SBV(Ω, R N ), T is a piecewise roto-translation associated with a Caccioppoli partition {E i } i∈I T such that i∈I T P (E i , Ω) ≤ C, T = Id on Ω\(A+B r ), T (A+B r ) ⊂ (Ω\[(A+B r )∪(∂Ω+B r )])
is not empty.

Existence of a minimizer for Model I and continuity of E 1

Theorem 5.1 (Existence of optimal exemplar-based inpaintings) Let u 0 ∈ L ∞ (Ω\A). Then, the problem Min

T ∈V 1 A+Br Br |u 0 (T (x + y)) -u 0 (T (x) + ∇T (x) y)| 2 dy dx has a solution T opt ∈ V 1 . The function u : Ω → R defined by u(x) = u 0 (x) if x ∈ A u 0 (T opt (x)) if x ∈ Ω \ A
is called an optimal exemplar-based inpainting associated with u 0 . Remark 5.2 For simplicity, the theorem is stated for gray level images. It can be however immediately generalized to color images using the functional Min

T ∈V 1 3 i=1
A+Br Br

|u i 0 (T (x + y)) -u i 0 (T (x) + ∇T (x) y)| 2 dy dx
where u 0 = (u 1 0 , u 2 0 , u 3 0 ) is any color representation, e.g. RGB, YCrCb or Lab, the latter being more robust to the creation of false colors.

Proof Denote the energy as

E 1 (T ) = A+Br Br |u 0 (T (x + y)) -u 0 (T (x) + ∇T (x) y)| 2 dy dx and take a minimizing sequence (T n ) n∈N in V 1 associated with Caccioppoli partitions {E i,n } i∈In such that i∈In P (E i,n , Ω) ≤ C . Since S Tn ⊂ i∈In ∂ * E i,n (see Remark 4.
2), we deduce from the assumptions that sup n H N -1 (S Tn ) ≤ C and, since Ω is bounded, sup n T n ∞ < +∞. Applying the Compactness Theorem 4.4 for piecewise roto-translations, there exists a subsequence, still denoted as (T n ) n∈N , that converges in L 1 (Ω, R N ) to a piecewise roto-translation T ∈ SBV(Ω, R N ) associated with a Caccioppoli partition {E i } i∈I that satisfies, by the semicontinuity of perimeter,

i∈I P (E i , Ω) ≤ C.
In addition, T =Id a.e. on Ω \ (A + B r ) and

T (A + B r ) ⊂ (Ω \ [(A + B r ) ∪ (∂Ω + B r )]) up to a Lebesgue negligible set. Thus T ∈ V 1 . Let us now prove that it minimizes E 1 .
Let ǫ > 0. From Lusin Theorem [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF], there exists a continuous function Since u 0 ∈ L ∞ (Ω) and w ∞ ≤ u 0 ∞ , in order to prove that the left term tends to 0, we will provide a bound for

w ∈ C( Ω) such that w ∞ ≤ u 0 ∞ and D 0 = {x : u 0 (x) = w(x)} satisfies |D 0 | < ǫ.
sup n∈N A+Br Br [1 D 0 (T n (x) + ∇T n (x) y) + 1 D 0 (T (x) + ∇T (x) y)] dy dx.
We observe that

L N ⊗ L N ({(x, y) ∈ (A + B r ) × B r : T n (x) + ∇T n (x) y ∈ D 0 }) = A+Br |{y ∈ B r , y ∈ (∇T n (x)) -1 (D 0 -T n (x))}|dx
which makes sense because ∇T n (x) ∈ SO(N ) almost everywhere. For the same reason, denoting

D 0 (x) = (∇T n (x)) -1 (D 0 -T n (x)), we have L N (D 0 (x)) = L N (D 0 ) ≤ ǫ. Hence L N ⊗ L N ({(x, y) ∈ (A + B r ) × B r : T n (x) + ∇T n (x) y ∈ D 0 }) ≤ ǫ|Ω|
The same argument is true for T instead of T n thus A+Br Br

|u 0 (T n (x) + ∇T n (x) y) -u 0 (T (x) + ∇T (x) y)|dy dx ≤ 4ǫ u 0 ∞ |Ω| + A+Br Br |w(T n (x) + ∇T n (x) y) -w(T (x) + ∇T (x) y)|dy dx It follows from (3) that u 0 (T n (x) + ∇T n (x) y) converges to u 0 (T (x) + ∇T (x) y) in L 1 ((A + B r ) × B r , L N ⊗ L N ).
Let us now prove that

A+Br Br |u 0 (T n (x + y)) -u 0 (T (x + y))|dy dx -→ 0 as n → ∞.
Again we use Lusin Theorem [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF] to obtain the existence of a continuous function Observe that for every x ∈ Ω

w ∈ C( Ω) such that w ∞ ≤ u 0 ∞ and D 0 = {x : u 0 (x) = w(x)} satisfies |D 0 | < ǫ.
Br(x) [1 D 0 (T n (z)) + 1 D 0 (T (z))] dz ≤ |T -1 n (D 0 )| + |T -1 (D 0 )| Recall that T = i∈I (R i x + t i )1 E i where the Caccioppoli partition {E i } i∈I satisfies i∈I P (E i , Ω) ≤ C. Since T : Ω → Ω and T E i is an isometry we have |T (E i )| = |E i |. Therefore, we deduce from |D 0 | < ǫ that |T -1 (D 0 )| ≤ ǫ • #{i ∈ I : |E i | > ǫ} + i∈I |E i |≤ǫ |E i |
where # denotes the counting measure. It follows from Lemma 5.4 below, due to G.P. Leonardi [62], that there exists a constant C depending only on C, N such that

|T -1 (D 0 )| ≤ Cǫ 1 N thus A+Br Br 1 D 0 (T (x + y))dy dx ≤ C|A + B r |ǫ 1 N .
The same argument is valid for any T n in the converging sequence and we conclude that

A+Br Br |u 0 (T n (x + y)) -u 0 (T (x + y))|dy dx ≤ 4 C u 0 ∞ |A + B r |ǫ 1 N + A+Br Br |w(T n (x + y)) -w(T (x + y))|dy dx,
which, in view of (2), proves that u 0 (T n (x+y)) converges to u 0 (T (x+y)) in L 1 ((A+B r )×B r , L N ⊗ L N ). Since we have already seen that u 0 (T n (x) + ∇T n (x) y) converges to u 0 (T (x) + ∇T (x) y) in L 1 ((A + B r ) × B r , L N ⊗ L N ), possibly taking a subsequence and using the Dominated Convergence Theorem, we can conclude that

A+Br Br |u 0 (T n (x + y)) -u 0 (T n (x) + ∇T n (x) y)| 2 dy dx -→ A+Br Br |u 0 (T (x + y)) -u 0 (T (x) + ∇T (x) y)| 2 dy dx as n → ∞. Finally, the minimizing sequence (T n ) converges to T ∈ V 1 with E 1 (T ) = lim n→∞ E 1 (T n ) thus T is a minimizer of E 1 in V 1 .
Remark 5.3 (Continuity of E 1 ) A by-product of the proof above is the continuity of E 1 in V 1 with respect to the weak- * convergence in SBV.

Lemma 5.4 (G.P. Leonardi [62])

Let CP = {{E i,α } i∈Iα } denote a collection of Caccioppoli par- titions of Ω such that sup α i∈Iα P (E i,α , Ω) ≤ C 1 . For every ǫ > 0 and E = {E i } i∈I ∈ CP, let us define ϕ ǫ (E) = ǫ • #{i ∈ I : |E i | > ǫ} + i∈I |E i |≤ǫ |E i |,
where # denotes the counting measure. Then there exists C 2 > 0 such that

sup E∈CP ϕ ǫ (E) ≤ C 2 ǫ 1 N Proof Let E = {E i } i∈I ∈ CP and K ǫ (E) = {i ∈ I : |E i | ≥ ǫ}.
Ω being bounded with Lipschitz boundary, one has H N -1 (∂Ω) < +∞ therefore by adding R N \ Ω to E one obtains a Caccioppoli partition of R N . In addition, by Theorem 3.7,

i∈I P (E i , R N ) = i∈I P (E i , Ω) + H N -1 (∂Ω).
By the isoperimetric inequality in R N , there exists

C 3 > 0 such that ǫ N -1 N #K ǫ (E) ≤ i∈Kǫ(E) |E i | N -1 N ≤ i∈Kǫ(E) C 3 P (E i , R N ) ≤ (C 1 + H N -1 (∂Ω)) C 3 from which we deduce that ǫ#K ǫ (E) ≤ (C 1 + H N -1 (∂Ω)) C 3 ǫ 1 N . Besides, i ∈Kǫ(E) |E i | = i ∈Kǫ(E) |E i | N -1 N |E i | 1 N ≤ ǫ 1 N i ∈Kǫ(E) |E i | N -1 N ≤ (C 1 + H N -1 (∂Ω))C 3 ǫ 1 N ,
and the lemma follows.

Non uniqueness of the minimizers

Relation with patch-based algorithms

It is natural to wonder how the model that we propose relates to basic patch-based algorithms, i.e. algorithms with reasonably sophisticated scans of the inpainting domain (raster scan, spiral scan, most convex points first, edges first, etc.). As will be shown in Section 7, there are partial numerical indications that geometric features could be recovered on a global basis with our model when a basic patch-based method rather works on a local or semi-local basis. We actually believe that the action of a basic patch-based algorithm is equivalent to a locally minimizing flow with respect to our model. It consists indeed in iteratively invading the inpainting domain from outwards to inwards. At each step i an optimal pair (E i , R i x + t i ) is found and u 0 is defined on E i as u 0 (R i x + t i ). At the end, a finite Caccioppoli partition has been built in association with a piecewise roto-translation T and the reconstructed image in A coincides with u 0 (T (•)). Therefore, basic patch-based algorithms can be seen as greedy methods for minimizing the functional, at least locally.

We may also wonder whether a locally minimizing flow can be directly found from the model. Obviously, the derivation of a Euler-Lagrange equation associated with the model, even in a weak form, is a highly non trivial problem. And even if we find one, for example up to a prior regularization of the functional, it will presumably not be able to reconstruct sharp discontinuities in contrast with most patch-based algorithms. Another option would be to try to decrease the energy by a suitable perturbation of a given Caccioppoli partition and of an associated piecewise roto-translation. But this approach is rather difficult to handle and would probably be much too sensitive to local minima.

Eventually, one may directly try to find a globally minimizing scheme: it is a completely open problem to the best of our knowledge. A possible direction of research is given by the interesting [START_REF] Komodakis | Image completion using efficient belief propagation via priority scheduling and dynamic pruning[END_REF] where a criterion related to ours is minimized using a belief-propagation technique in Markov Random Field graphs. As mentioned by the authors, the method is global for tree structured graphs but might not be global if the graph contains cycles, which is usually the case for graphs associated with digital images... The authors claim however that "strong" local minima can be obtained, i.e. local minima that are close to global minima from an experimental point of view. Yet global minima are still unreachable and we believe that it is an interesting direction of research.

Introducing first order penalty terms

The exemplar-based inpainting methods where entire pieces of patches are copied suffer from a well-known problem: blocky effects are visible in the reconstruction when the patch size parameter r does not correspond to the texture scale or, more generally, when the patch size becomes large. Different approaches have been proposed to solve this issue, like finding a "smooth" transition between adjacent patches. We propose an extension of our model that allows further restrictions on the reconstruction.

First, we relax the condition that the reconstructed image in A has to be exactly copied from u 0 . Instead we introduce an interpolating function u with the constraint that u has to coincide with u 0 outside A. This gives a new criterion Ẽ2 (u, T ) = A+Br Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| 2 dy dx that can be easily minimized in the space {(u, T ) :

u ∈ L ∞ (Ω), u ∞ ≤ C 1 , T ∈ V 1 }.
Being the blocky effects characterized by the creation of spurious edges, we penalize the local variations of u as soon as they are larger than the local variations of u 0 . The new criterion makes sense if u 0 , u ∈ L ∞ (Ω) ∩ BV(Ω) and reads as:

Model II E 2 (u, T ) = 1 r N A+Br Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| 2 dy dx + 1 r N -1 A+Br |Du|(B r (x)) -|Du 0 |(B r (T (x))) + dx
where (•) + denotes max(•, 0) and the coefficients 1 r N and 1 r N -1 ensure the homogeneity of the energy. Observe that the second term does not penalize the total variation of u but only prevents the local variations from being larger than those of u 0 . Thus oscillations are still allowed and can be preserved. In particular, texture images can be processed under the condition that they have finite total variation, which is somewhat restrictive -it has been shown in particular in [START_REF] Gousseau | Are natural images of bounded variation ?[END_REF] that some textures might have infinite total variation in the continuous domain -but not absurd.

It is worth noticing also that using (•) + rather than | • | gives some freedom to have a smooth interpolant and, from a mathematical point of view, is much easier to handle. Besides, it is legitimate to wonder why we compare the local total variations of u and u 0 instead of simply minimizing

A+Br(0) |Dv x |(B r )dx
where v x (y) = u(x + y) -u 0 (T (x) + ∇T (x) y). This term is actually much too regularizing and is for example absolutely not adapted for comparing similar but not identical samples of a texture or for the comparison of two geometric samples that coincide up to a small translation. In contrast, comparing the local total variations is much more adapted.

We shall prove in the next section the existence of minimizers of E 2 in a suitable space. Let us stress that the results remain valid when adding to the criterion any lower semicontinuous (and coercive if necessary) functional depending on u. This gives the opportunity to play with the regularity of the reconstructed image. We will propose in section 6.2 a third criterion that aims at constraining even more the geometry.

Minimization of Model II

Assume that u 0 ∈ BV(Ω) ∩ L ∞ (Ω) and define

V 2 = (u, T ), u ∈ BV(Ω) , u ∞ ≤ u 0 ∞ , u = u 0 on Ω \ A, T ∈ SBV(Ω, R N ), T is a piecewise roto-translation associated with a Caccioppoli partition {E i } i∈I T such that i∈I T P (E i , Ω) ≤ C r N -1 , T = Id on Ω \ (A + B r ), T (A + B r ) ⊂ (Ω \ [(A + B r ) ∪ (∂Ω + B r )])
Then we can prove the following theorem Theorem 6.1 The functional E 2 admits a minimizer (u, T ) ∈ V 2 .

The proof of Theorem 6.1 requires preliminary results on measures. The following lemma shows that, given r > 0, a measure on Ω negligible with respect to H N -2 does not charge spheres of radius r except for at most countably many of them. Lemma 6.2 Let ν be a positive measure on Ω negligible with respect to H N -2 , i.e. H N -2 (B) < +∞ implies ν(B) = 0 for any Borel set B ⊂ Ω. For all ǫ > 0, G ǫ := {y / ν(∂B r (y)) > ǫ} is finite thus G := {y / ν(∂B r (y)) > 0} is at most countable.

Proof Let y 1 , y 2 ∈ G ǫ with y 1 = y 2 . Then, since ν is negligible with respect to

H N -2 , ν(Ω) ≥ ν(Ω ∩ (∂B r (y 1 ) ∪ ∂B r (y 2 ))) = ν(∂B r (y 1 )) + ν(∂B r (y 2 )) > 2ǫ. It follows that #{y, ν(∂B r (y)) > ǫ} ≤ ν(Ω) ǫ , hence G ǫ is finite. Since G = n≥1 G 1 n
, G is at most countable.

Lemma 6.3 With the notations of Lemma 6.2, let τ ∈ BV(Ω, Ω) such that det (∇τ ) = 0 a.e., where ∇τ denotes the approximate differential of τ . Then we have Proof It suffices to remark that if u ∈ BV(Ω) then |Du| is a positive measure negligible with respect to H N -2 . The conclusion follows from Lemmas 6.2 and 6.3.

L N ({x ∈ Ω, τ (x) ∈ G}) = 0. Proof Let C := {x ∈ Ω, τ (

Proof of Theorem 6.1:

It is easily seen that there exist pairs (u, T ) ∈ V 2 such that E 2 (u, T ) < ∞. Consider a minimizing sequence (u n , T n ) n≥1 and assume that sup n≥1 E 2 (u n , T n ) ≤ δ. One has

A+Br |Du n |(B r (x)) dx ≤ A+Br |Du 0 |(B r (T n (x))) dx + r N -1 δ ≤ |A + B r | |Du 0 |(Ω) + r N -1 δ (4) 20
Notice that:

|Du n |(Ω) = |Du n |(Ω\(A + B r )) + |Du n |(A + B r ) = |Du 0 |(Ω\(A + B r )) + |Du n |(A + B r ) ≤ |Du 0 |(Ω) + |Du n |(A + B r ) (5) Let {S i } i=1,••• ,k be a covering of A + B r by cubes of side α < r/2 such that |S i ∩ S j | = 0, i = j. Let a = min i=1,••• ,k {|S i ∩ (A + B r )|}.
By the subadditivity of the total variation measure

|Du n |(A + B r ) ≤ k i=1 |Du n |(S i )
By the mean value theorem, for each i ∈ {1, • • • , k} there exists

x i ∈ int(S i ) ∩ (A + B r ) such that |Du n |(B r (x i )) ≤ S i ∩(A+Br) |Du n |(B r (x))dx therefore, since S i ⊂ B r (x i ), |Du n |(A + B r ) ≤ k i=1 |Du n |(B r (x i )) ≤ 1 a k i=1 S i ∩(A+Br) |Du n |(B r (x))dx = 1 a A+Br |Du n |(B r (x))dx
Plugging into (5) yields

|Du n |(Ω) ≤ |A + B r | |Du 0 |(Ω) + r N -1 δ a + |Du 0 |(Ω)
thus the sequence (u n ) n∈N has uniformly bounded total variation. Since in addition u n ∞ ≤ u 0 ∞ and Ω is bounded, we can apply the compactness theorem in BV to deduce the existence of u ∈ BV(Ω) ∩ L ∞ (Ω) such that, up to a subsequence, (u n ) weakly- * converges to u in BV(Ω), u ∞ ≤ u 0 ∞ and u = u 0 on Ω \ A.

The same argument as in the proof of Theorem 5.1 yields that, up to a subsequence, T n weakly- * converges in BV to a piecewise roto-translation T with (u, T ) ∈ V 2 . In addition and since u n → u in L 1 , we can prove with a similar argument as for Theorem 5.1 that Let us now examine the second term of E 2 in Model II. We know from Lemma 6.4 that for a.e.

x ∈ A + B r , |Du 0 |(∂B r (T (x))) = 0. Because T n converges to T in L 1 , we have T n (x) → T (x) a.e. possibly taking a subsequence. Thus, for a.e. x ∈ A + B r , 1 Br(Tn(x)) → 1 Br(T (x)) |Du 0 |-almost everywhere. By the Dominated Convergence Theorem, it follows that for a.e. x ∈ A + B r ,

Ω 1 Br(Tn(x)) d|Du 0 | = |Du 0 |(B r (T n (x))) → Ω 1 Br(T (x)) d|Du 0 | = |Du 0 |(B r (T (x))).
Then, by the lower semicontinuity of the total variation, for every

x ∈ A + B r |Du|(B r (x)) ≤ lim inf n→∞ |Du n |(B r (x)), therefore |Du|(B r (x)) -|Du 0 |(B r (x)) ≤ lim inf n→∞ (|Du n |(B r (x)) -|Du 0 |(B r (T n (x))))
and thus

|Du|(B r (x)) -|Du 0 |(B r (x)) + ≤ lim inf n→∞ |Du n |(B r (x)) -|Du 0 |(B r (T n (x))) + We deduce from Fatou's Lemma that A+Br |Du|(B r (x)) -|Du 0 |(B r (x)) + dx ≤ lim inf n→∞ A+Br |Du n |(B r (x)) -|Du 0 |(B r (T n (x))) + dx
In conclusion, the minimizing sequence (u n , T n ) converges to (u, T ) ∈ V 2 and E 2 (u, T ) ≤ lim inf n→∞ E 2 (u n , T n ) thus (u, T ) is a minimizer of E 2 in V 2 and Theorem 6.1 ensues.

Model III: using a decomposition into geometry+texture

Although Model II allows the processing of all textures with finite total variation, comparing the local variations is more meaningful for a geometric image than for a texture image. We thus propose a third model where the local variation penalty -and possibly others of higher order -is put on the geometric part only. Remark that for compactness reasons we still have to assume a BV control of the whole reconstructed image u -but the bound can be taken arbitrarily large.

Before introducing our third model, let us recall a few basic facts about TV-L 1 image decomposition.

The TV-L 1 decomposition

We refer the reader to [START_REF] Meyer | Oscillating patterns in image processing and in some nonlinear evolution equations[END_REF] for an introduction to the problem of image decomposition. The goal is to write an image as a sum of a geometric component -sometimes called a cartoon imageand a texture component. There is a wide body of literature related to the question of finding the most suitable decomposition spaces and the most efficient numerical method to perform the decomposition, see for instance [START_REF] Vese | Modeling textures with total variation minimization and oscillating patterns in image processing[END_REF][START_REF] Osher | Image decomposition and restoration using total variation minimization and the H -1 norm[END_REF][START_REF] Aujol | Image decomposition into a bounded variation component and an oscillating component[END_REF][START_REF] Aubert | Modeling very oscillating signals. application to image processing[END_REF][START_REF] Aujol | Dual norms and image decomposition models[END_REF][START_REF] Daubechies | Variational image restoration by means of wavelets: simultaneous decomposition, deblurring and denoising[END_REF][START_REF] Le | Image decomposition using total variation and div(BMO)[END_REF][START_REF] Yin | Second-order cone programming methods for total variation based image restoration[END_REF][START_REF] Aubert | Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations[END_REF][START_REF] Chan | Image processing and analysis -Variational, PDE, wavelet, and stochastic methods[END_REF] to name a few. In this paper we will use a TV-L 1 model originally introduced in the context of image denoising [START_REF] Aliney | A property of the minimum vectors of a regularizing functional defined by means of the absolute norm[END_REF][START_REF] Nikolova | A variational approach to remove outliers and impulse noise[END_REF] and studied explicitly as a decomposition model in [START_REF] Aujol | Structure-texture image decompositionmodeling, algorithms, and parameter selection[END_REF][START_REF] Chan | Aspects of total variation regularized l 1 function approximation[END_REF][START_REF] Darbon | Image restoration with discrete constrained total variation part I: Fast and exact optimization[END_REF][START_REF] Yin | A comparison of three total variation based texture extraction models[END_REF] for instance. Starting from a function v ∈ L ∞ (Ω), the principle is to find a decomposition v = v g + (v -v g ) which is optimal with respect to the criterion

|Dv g |(Ω) + λ v -v g L 1 (Ω)
. This model has interesting properties: the stability with respect to a class of contrast changes, the stability of the geometric component as long as λ lies in a certain range of values, and the ability to capture structured patterns in the texture component. For simplicity, we shall take λ = 1 in the sequel but the results remain valid for any λ > 0. Definition 6.5 (Geometric part of a TV-L 1 decomposition) Let v ∈ L ∞ (Ω). We mean by geometric part of v a (possibly non unique) solution v g of Min

v g ∈L ∞ (Ω)∩BV(Ω) |Dv g |(Ω) + v -v g L 1 (Ω) (6)
The existence of solutions to Problem ( 6) is an easy consequence of the lower semicontinuity of the total variation in BV. The fact that several minimizers may exist has been in particular examined in [START_REF] Chan | Aspects of total variation regularized l 1 function approximation[END_REF].

We define now, and once for all, u g 0 as a solution of ( 6) with v = u 0 and such that u g 0 ∞ ≤ u 0 ∞ , which is possible according to the next proposition. When a function f belongs to L ∞ (Ω), we denote by sup Ω f and inf Ω f the essential supremum and the essential infimum, respectively. Proposition 6.6 Let us set α ≤ inf Ω v and β ≥ sup Ω v. If v g is a solution of Problem ( 6), then max α, min(β, v g ) is also a solution of Problem [START_REF] Ashikhmin | Synthesizing natural textures[END_REF]. In particular, max inf Ω v, min(sup Ω v, v g ) is a solution.

In particular, it means that if v g is a solution of Problem ( 6), then, up to a truncation, we can always assume that inf

Ω v ≤ v g ≤ sup Ω v
Proof It is based on a standard truncation argument. We remark that x → |x -a| is decreasing if x ∈ (-∞, a) and increasing if x ∈ (a, +∞). Therefore, if M ≥ a, one always has: | min(x, M )-a| ≤ |x -a|. Hence, if we let M = β, we find that:

Ω | min(v g , β) -v| dx ≤ Ω |v g -v| dx
Moreover, it is a direct consequence of the coarea formula that |D(min(v g , β))|(Ω) ≤ |Dv g |(Ω) which yields that the function min(v g , β) is a solution of Problem [START_REF] Ashikhmin | Synthesizing natural textures[END_REF]. It follows from a similar argument that also max α, min(β, v g ) is solution.

We now introduce the notion of constrained geometric parts whose existence can be proved like for the generic geometric parts. Definition 6.7 (Geometric parts constrained by u 0 ) Let u ∈ L ∞ (Ω) such that u = u 0 on Ω \ A. We mean by geometric part of u constrained by u 0 a (possibly non unique) solution u g of Min

u g ∈L ∞ (Ω)∩BV(Ω) u g =u g 0 on Ω\A |Du g |(Ω) + u -u g L 1 (Ω) (7)
such that u g ∞ ≤ u ∞ .

Model III: penalizing the local variations of the geometric component only

We propose as a third model to minimize the criterion:

Model III E 3 (u, u g , T ) = 1 r N A+Br Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| 2 dy dx + 1 r N -1 A+Br |Du g |(B r (x)) -|Du g 0 |(B r (T (x))) + dx
where we assume that u g is a geometric part of u constrained by u 0 . Let C be such that

V 3 = (u, u g , T ), u ∈ BV(Ω), u ∞ ≤ u 0 ∞ , |Du|(Ω) ≤ C r N -1 , u = u 0 on Ω \ A, u g geometric part of u constrained by u 0 , T ∈ SBV(Ω, R N ) is a piecewise roto-translation associated with a Caccioppoli partition {E i } i∈I T such that i∈I T P (E i , Ω) ≤ C r N -1 , T = Id on Ω \ (A + B r ), T (A + B r ) ⊂ (Ω \ [(A + B r ) ∪ (∂Ω + B r )])
. is not empty. Then we can prove the following Theorem 6.8 E 3 has at least a minimizer (u, u g , T ) ∈ V 3 .

Proof : First remark that, V 3 being not empty, there obviously exist triplets (u, u g , T ) ∈ V 3 such that E 3 (u, u g , T ) < ∞. Consider a minimizing sequence (u n , u g n , T n ) n≥1 and assume that sup n≥1 E 3 (u n , u g n , T n ) < +∞. Since u g n is a solution of Problem ( 7) (with respect to u n ) and the function w that vanishes on A and coincides with u g 0 on Ω \ A satisfies the constraints of Problem ( 7), we have

|Du g n |(Ω) ≤ |Du g n |(Ω) + u n -u g n L 1 (Ω) ≤ |Dw|(Ω) + u n -w L 1 (Ω) . By Theorem 3.7, |Dw|(Ω) ≤ |Du g 0 |(Ω \ Ā) + u g 0 ∞ H N -1 (∂A) and since w L 1 (Ω) = u g 0 L 1 (Ω\ Ā)
, we get that for some γ independent of n

|Du g n |(Ω) ≤ γ + u n L 1 (Ω)
But Ω being bounded, we deduce from our assumptions that

u n L 1 (Ω) ≤ |Ω| u n L ∞ (Ω) ≤ |Ω| u 0 ∞ thus |Du g n |(Ω) ≤ γ + |Ω| u 0 ∞ .
Therefore, the u g n 's are uniformly bounded in BV(Ω) so there exists a subsequence, still denoted as (u g n ), that weakly- * converges in BV to ū

∈ BV(Ω) ∩ L ∞ (Ω) such that ū ∞ ≤ u 0 ∞ .
Besides, since u n is uniformly bounded in BV(Ω), there exists u in L 1 (Ω) such that, up to a subsequence, u n → u in L 1 (Ω).

We now need to show that ū is indeed a geometric part of u constrained by u 0 . This is not immediate due to the constraint ū = u g 0 on Ω \ A but can be done using the theory of Γconvergence [START_REF] Maso | An Introduction to Γ-Convergence[END_REF]. Let us consider the space X = BV(Ω) ∩ {w : w = u g 0 on Ω \ A} endowed with the strong L 1 convergence and, with the notations above, define on X the functionals

F n (w) = |Dw|(Ω) + w -u n L 1 (Ω) .
We will prove that F n Γ-converges on X with respect to the strong topology of L 1 to the functional F defined by F (w) = |Dw|(Ω) + w -u L 1 (Ω) for every w ∈ X. If (w n ) ⊂ X → w ∈ X then the lower semicontinuity of total variation and the convergence in L 1 of u n to u imply that

F (w) ≤ lim inf n→∞ F n (w n )
Observe now that F (w) = lim n→∞ F n (w) therefore F n Γ-converges to F in X with respect to the L 1 (Ω) convergence. By a well-known property of Γ-convergence [START_REF] Maso | An Introduction to Γ-Convergence[END_REF], since (u g n ) is a sequence of minimizers of F n in X that converges in L 1 (Ω) to ū, we conclude that ū is a minimizer of F in X, thus a geometric part of u constrained by u 0 . We denote from now u g := ū.

The same argument as in the proof of Theorem 5.1 yields that, up to a subsequence, T n weakly- * converges in BV to T with (u, u g , T ) ∈ V 3 . In addition and since u n → u in L 1 , we can prove with a similar argument as for Theorem 5.1 that Arguing again like in the proof of Theorem 5.1 -except that we now have to work with the geometric parts -we can prove the lower semicontinuity of the first-order term, i.e.

A+Br |Du g |(B r (x))-|Du g 0 |(B r (T (x))) + dx ≤ lim inf n→∞ A+Br |Du g n |(B r (x))-|Du g 0 |(B r (T n (x))) + dx.
To conclude, the minimizing sequence (u n , u g n , T n ) converge to (u, u g , T ) ∈ V 3 with E 3 (u, u g , T ) ≤ lim n→∞ E 3 (u n , u g n , T n ) and Theorem 6.8 ensues.

Adding further restrictions to the geometric part: the case of the Willmore functional

Let us define the functional

F (u) =    A+Br |∇u| 1 + α div ∇u |∇u| p dx if u ∈ C 2 (Ω) +∞ if u ∈ L 1 (Ω) \ C 2 (Ω)
where α > 0 and p > 1. F is an extension to gray-level images of the celebrated Willmore functional for surfaces S |H S | 2 dH 2 where S is a two-dimensional surface and H S denotes the mean curvature vector. As mentioned in the introduction, F has been proposed in [START_REF] Masnou | Level lines based disocclusion[END_REF] in the context of inpainting following the idea that the interpolation process must mimic the brain ability to reconstruct partially visible objects -the so-called amodal completion. The results obtained in [START_REF] Masnou | Level lines based disocclusion[END_REF][START_REF] Masnou | Disocclusion : a variational approach using level lines[END_REF][START_REF] Chan | Euler's elastica and curvature based inpainting[END_REF][START_REF] Esedoglu | Threshold dynamics for shape reconstruction and disocclusion[END_REF] with an optimization model involving F show that this approach performs well for the inpainting of geometric images. Being not lower semicontinuous, F cannot be directly minimized but must be replaced by the associated relaxed functional [START_REF] Maso | An Introduction to Γ-Convergence[END_REF] defined by :

∀u ∈ L 1 (Ω), F (u) = inf{lim inf n→∞ F (u n ), (u n ) ⊂ C 2 (Ω), u n → u in L 1 (Ω)}
that has been studied in [START_REF] Ambrosio | A direct variational approach to a problem arising in image reconstruction[END_REF][START_REF] Leonardi | Locality of the mean curvature of rectifiable varifolds[END_REF]. The lower semicontinuity of F with respect to the convergence in L 1 yields the following result, which is an easy consequence of Theorem 6.8. Theorem 6.9 Assume that V 3 contains at least a triplet (u, u g , T ) such that F (u g ) < ∞. Then the following functional has a minimizer in V 3 :

Model IV E 4 (u, u g , T ) = 1 r N A+Br Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| 2 dy dx + 1 r N -1 A+Br |Du g |(B r (x)) -|Du g 0 |(B r (T (x))) + dx + F (u g )
Loosely speaking, this theorem provides a theoretical justification of the minimization of Model III plus the additional constraint that the geometric part of the reconstructed image must have rather small and not too oscillating level lines, which agrees with the type of interpolation that our brain can perform.

7 Comparing Models I and II with basic patch-based inpainting algorithms: a toy example in dimension 2

One of the motivations for this paper was to understand what kind of geometry can reconstructed with exemplar-based inpainting methods and whether our different global variational models are able to recover geometric features on a non local basis. Our first results in this direction, through numerical computations performed on a simple example, are very partial but instructive. They indicate that Models I and II could indeed be better suited for the recovery of long-range geometric features.

The simple inpainting situation that we shall study is illustrated in Figure 4: it consists of a two-dimensional binary image from which a rectangular region has been removed. We denote by R the distance between the upper left vertex of the rectangle and each edge termination. We chose this configuration because it gives a clue about which continuation could be favored by the different models in the general situation where two edges with different directions are interrupted by the inpainting domain. First, let us stress that it is virtually impossible to prove that a given inpainting is the best in the sense of our models. Except in very extremely simple cases for which we can find a zero energy configuration, we are not able to prove the optimality of a given inpainting candidate. One of the reasons is the non existence of a simple formula for the gradient of our functional. Therefore, we will restrain ourselves to compare the respective energies -very precisely computed through a numerical scheme -of ad hoc interpolations.

Three inpainting candidates

First, let us recall that a candidate to an inpainting problem in our setting consists in the value of the image inside the unknown region and the definition of the geometrical transformation T that reflects where the copy comes from. In the case of Model I the value of the image inside the inpainting zone is even forced by the choice of T and equals u 0 (T (x)). Three natural inpaintings can be proposed for filling the unknown region of Figure 4. They are shown in Figure 5.

First inpainting: prolonging the edges until they meet The first natural interpolation consists in prolonging the two outer edges until they meet with a 90 degrees angle. This corresponds to a "good continuation" configuration according to the terminology of vision theory [START_REF] Kanizsa | Organization in Vision: Essays on Gestalt Perception[END_REF]. The transformation T that produces such a result is defined as follows: on region α (see Figure 5(a)) it is a vertical translation by a vector long enough to ensure that any point of the unknown region is transported outside A. On region β, T is a horizontal translation with the same constraint on the length of the translation vector.

Such configuration is very close to what would provide a generic patch-based algorithm, except maybe that the algorithm would not reconstruct exactly the right angle, unless it is present elsewhere in the image, but rather returns a "cut" angle.

Second inpainting: connecting with the shortest path The second configuration that we shall study is obtained by connecting the two junctions M and N -i.e. the intersection points between the inpainting domain and the outer edges -with a straight line and filling the unknown region with the value 1 on top of this straight line and zero elsewhere. A possible transformation T that yields this result is, for the interior region, a mere rotation that transforms the segments [M, N ] into some segment of the two edges outside the inpainting domain. It is a 45 degrees rotation and it does obviously not matter which one of the two existing lines is chosen to be copied. Above the bisector of the angle at point N , T is defined as the translation by a vertical vector which is long enough to get out of A + B r . A similar definition holds under the bisector of the angle at point M using instead a horizontal translation.

Third inpainting: connecting with a polygonal line The third interpolation we propose consists in connecting the two end points M and N by a polygonal line, i.e. a rough approximation of a circle. As before, the upper left region is filled with ones and the rest of the unknown region is filled with zeros. The length of each segment composing the polygon is chosen to be equal to r and we do not discuss the fact that the number of segments required may not be an integer because the contribution to the total energy of each segment is small when r is small thus one can neglect The shortest path continuation Figure 7(a) shows the different regions of interest in the case of the completion by the shortest path (we concentrate on one of the end points of the continuation line). Let α and β denote respectively the upper half and the lower half disks -with respect to the bisector -with radius r and centered at the junction point. Recall that T is defined on region α as a vertical translation and on region β as a rotation. For any x in these two regions, the graphs of ϕ x 1 and ϕ x 2 on B r (0) are equivalent to Figure 7(b) and 7(c), respectively. Another region is not shown in the figure: the one situated outside the disk of radius r, on the left with respect to the junction point, above the bisector and below the tangent to the circle which is parallel to the 45 degrees line forming the junction. This region is very small and plays the same role as region δ of Figure 10. The polygonal continuation is given by a map T defined on a partition made of isosceles triangles with base length r, principal height length R, and having as common vertex the top left corner of the inpainting domain. The number of triangles is approximately π 4 asin( r 2R )

. Figure 8(a)

shows the different meaningful regions for the definition of the functions ϕ x 1 and ϕ x 2 . Regions α and β are equivalent: they are defined as the set of points at distance less than r from exactly one of the two endpoints M or N of the base segments of the triangular region under study. Whenever x ∈ α or β, ϕ x 1 and ϕ x 2 are similar to Figures 8(b) and 8(c). When x ∈ γ (points that are at distance less than r from M and N ) they look like Figures 8(d) and 8(e).

Results

The results are given for a patch size r = 1, R = 10 (see Figure 4) and a grid step r/100. Possibly using for E 1 the same homogeneity factor as for the first term of E 2 , it is clear that the comparison will not be qualitatively modified for other values of r. One may object that the polygonal inpainting may depend on the relative values of r and R. In fact our numerical computations show that as far as the ratio R/r is bigger than 10 the value of the functionals are not noticeably modified by a change of the value of r. In any case, the domain A is assumed to be sufficiently large to include at least a ball of radius r centered at the point of intersection of the prolonged lines in 6(a). Recall indeed that outside the regions of interest given in Figures 6(a), 7(a) and 8(a) there is no contribution to the energy. We obtain the following numerical approximations for the respective energies E 1 and E 2 of each inpainting configuration, with the assumption for the computation of E 2 that u coincides with the reconstructed function. Let us first observe that E 1 and E 2 take a higher value for the shortest path continuation than they take for the polygonal continuation because the energy is computed on A + B r . If only A were used, the shortest path continuation would obtain a better score because part of the "bad continuation" information -i.e. the fact that there is an angle between the incoming edge and the interpolating line -is located outside A. Instead, using all the information in a band around A ensures that the compatibility of the interpolation with the outer image is fully considered.

The rectangular continuation is very similar to what classical exemplar-based inpainting algorithms, for example [START_REF] Pérez | PatchWorks: Example-based region tiling for image editing[END_REF], will compute, at least for a sufficiently small size of patch. There probably will be a slight difference at the angle point which should be "cut" by the algorithms. When the size of the patches becomes bigger then the algorithms compute an intermediate solution between the rectangular continuation and the shortest path continuation.

The results above indicate that the polygonal continuation has lower E 1 and E 2 energies than the other configurations. Of course, this does absolutely not prove that the polygonal continuation is a minimizer but at least that it is a better inpainting than the two others! We propose additional experiments in the next section in order to understand this fact.

Why does the polygonal continuation get smaller energy?

This section is devoted to a tentative explanation of why the polygonal continuation has a lower energy than the two others candidates under study. We actually claim that, among binary inpainting candidates whose discontinuity set is a polygonal line with vertices at least at a distance of r apart, those for which the angles at the vertices are more obtuse lower E 1 and E 2 energies. Recall first from the previous sections that, in the particular 2D inpainting situation that we are examining, the energy associated to an inpainting candidate is concentrated in a B r neighborhood of each vertex of the polygonal discontinuity set. We shall therefore provide, to justify our claim, experimental evidences that replacing an angle by two less acute angles like in Figure 9 decreases both E 1 and E 2 . Figure 11: The energies E 1 and E 2 with respect to angle θ (in degrees). Both energies tend to infinity when θ goes to zero, which is consistent with the computations linking them to the curvature of the discontinuity line (see the next section).

α β θ

= β = θ 2 + π 2 .
The contribution of the angle to E 1 for different values of θ is shown again in Figure 12 as a plain curve. We compare with the dashed curve representing the contribution to E 1 of the right configuration in Figure 9 for α, β defined by α = β = θ 2 + π 2 . We can deduce from this experiment that it is more economical to use several small angular jumps than a single large one. Of course, same results hold for the first term of E 2 when u is chosen as the appropriate transform of u 0 .

Interestingly, similar computations yield similar results for the second term of E 2 therefore we can also conclude that configurations with smaller angular jumps will have smaller E 2 energy. In other words, observing that the results will not qualitatively change when r becomes smaller, both E 1 and E 2 will promote smooth curves. As a consequence, the "flattening" or "iterated angle cut" process of Figure 13 decreases both E 1 and E 2 . Observe that, in Figure 13, (a) is the "good continuation" candidate, (b) the shortest path candidate and (f) the polygonal continuation candidate so that the obtained ordering is coherent with the numerical results of the previous section. This might also indicate that the smaller is r, the smoother are the discontinuity sets of the best binary inpainting candidates.

> > > = (c) (b) (a) = (d) (e) (f)
Figure 13: The "flattening" process decreases both E 1 and E 2 . Remark that (a), (b) and (f) coincide with the configurations studied in the previous sections therefore the numerical results obtained in Section 7.3 are confirmed.

To conclude this section, our experimental results on a very simple 2D situation indicate that the minimization of either Model I or II might promote non local and smooth geometric interpolations in contrast with classical exemplar-based algorithms. We already mentioned that the algorithms could correspond to locally minimizing flows for Model I. Our numerical observations clearly show the need for globally minimizing algorithms associated to Models I, II, III and IV.

8 From axiomatics to further extensions of E 2

The functional E 2 involves the L 2 norm of the local differences between u and u 0 , the difference between the local variations of u and u 0 and the homogeneity parameters 1 r N and 1 r N -1 in order to compensate the homogeneity difference between the first and the second terms, and also with the purpose in mind to study the asymptotic behavior of the functional as r → 0. Is there a more suitable way to define the functional? Besides, regarding the numerical results of the previous section, and in particular regarding the fact that E 2 takes very close values for the shortest path continuation and for the polygonal continuation, is there a way to modify its definition in order to promote much more the smoother configuration, i.e. the polygonal continuation?

We will focus on a particular generalization of E 2 , namely (H2) the minimizers of E a,b,c 2 are stable with respect to joint rescalings of the image domain, the inpainting domain and the reference patch B r . We will also discuss the connexion between the values of a, b, c and the smoothness of a geometric reconstruction. Let us first observe that if u 0 is replaced with ũ0 = λu 0 with λ > 0 then

E a,b,c 2 (λu, T ) = 1 r N A+Br Br |λu(x + y) -λu 0 (T (x) + ∇T (x) y)| a dy dx + 1 r N -1+b A+Br |D(λu)|(B r (x)) -|D(λu 0 )|(B r (T (x))) + c dx = 1 r N λ a A+Br Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| a dy dx + λ c r N -1+b A+Br |Du|(B r (x)) -|Du 0 |(B r (T (x))) + c dx.
Therefore, c = a is a sufficient condition for (H1) to be satisfied.

Let us now examine how the energy changes when the images, the domain, the patches and the roto-translations are rescaled by a factor k:

E a,b,c 2 u . k , T . k , kA, kr, u 0 . k = 1 (kr) N k(A+Br) B kr u 1 k (x + y) -u 0 1 k T x k + ∇T x k y a dy dx + 1 (kr) N -1+b k(A+Br) |D (ũ) | (B kr (x)) -|D (ũ 0 ) | B kr T x k + c dx = 1 r N k(A+Br) Br u x k + y -u 0 1 k T x k + ∇T x k y a dy dx + k N (kr) N -1+b A+Br k N -1 |Du| (B r (x)) -|Du 0 | (B r (T (x))) + c dx = k N r N (A+Br) Br |u (x + y) -u 0 (T (x) + ∇T (x) y) | a dy dx + k (N -1)c+1-b r N -1+b A+Br |Du| (B r (x)) -|Du 0 | (B r (T (x))) + c
dx Thus, to be sure that (u( . Remark that the existence of a minimizer can be proven for each triplet of parameters as an easy adaptation of the proof of Theorem 6.1. Experimental indications on the behavior of the different energies are obtained comparing the energies of the three proposed configurations for the 2D toy example of the previous section. Observe first that, u and u 0 being characteristic functions in these configurations, the value of a has no impact on the energy. Besides, taking into account that N = 2 now:

• For the shortest path continuation, the contributions to the energy E a,b,c 2 are concentrated on the balls of radius r centered at both ends of the connecting line. The term

I 1 a = 1 r 2 A+Br Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| a dy dx is therefore a O(r 2 ) whereas I 2 b,c = 1 r 1+b A+Br |Du|(B r (x)) -|Du 0 |(B r (T (x))) + c dx = O( r 2+c r 1+b ).
• For the rectangular continuation, the contribution to the energy is localized in the ball of radius r centered at the intersection point between both continuing segments. Again I For the particular choices of the parameters that we already examined, one gets in Figure 14 the asymptotic behaviours of both energy terms for the three continuations under study.

Observe that, for the particular case of the polygonal approximation, the energies that we obtained either depend on κ = 1 R or on κ 3 = 1 R 3 where R is the radius of the arc of circle that the dx for each continuation proposed as an interpolation of the toy example (see Figures 4 and5). Remark that the first term is always a O(r 2 ).

polygon approximates. The same computation can be done in higher dimensions, in which case the energies depend either on |H| or on |H| 3 where H is the mean curvature of an interpolating sphere.

In view of the chart of Figure 14, the energy obtained with a = c = 2 and b = 1 is the only one that makes a significant difference -asymptotically speaking -between the polygonal continuation on the one hand, and the two other continuations on the other hand. Turning back to the general case of dimension N , all these arguments lead us to the functional: Proof It is a trivial adaptation of the proof of Theorem 6.1.

Model II bis
Numerical computations similar to the previous sections yield the following charts for the values taken by E bis 2 on the three configurations under study for the two-dimensional toy example. These charts confirm that Model II bis has a better behaviour with respect to the polygonal continuation. In the first chart, we simply compute the energy of each configuration (r = 1, R = 10) and compare with Models I and II. dx and the existence of a minimizer in V 3 (for a large enough value of C) can be proven. However, the properties of the TV-L 1 decomposition imply that E bis 3 satisfies (H1) but not (H2).

Model I Model

We end this section with a remark on possible extensions of E 1 . It is inspired by a result of [START_REF] Cao | Geometrically guided exemplar-based inpainting[END_REF] stating that, given a bounded set E ⊂ R 2 with C 3 boundary, one has the equivalence for r small which measures how much E locally differs from patches of the form P ∩ B r (x) where P is a halfplane. Therefore, it gives a link -very logical by the way -between the smoothness of ∂E and its capacity to be recovered using straight patches. In our context, it is easy to change the formulation of E 1 so that the energy of the circle continuation depends on a power of the curvature. which is coherent with the result of [START_REF] Cao | Geometrically guided exemplar-based inpainting[END_REF]. Besides, remark that the existence of minimizers for E bis 1 can be proven as soon as p > 0 by a simple application of the Dominated Convergence Theorem in the last lines of the proof of Theorem 5.1.

Conclusion

The contribution of this paper is a first step toward the understanding of global variational formulations for exemplar-based methods in the continuous domain. We proved that there is a variety of models for which a minimizer exists and that compare favorably with generic exemplar-based algorithms for the reconstruction of geometric features. Future developments could be:

1. To understand more accurately the ability of Models I, II, II bis, III, III bis, and IV to reconstruct non local geometric features without diminishing the capacity to restore correctly the texture; 2. To derive globally minimizing discrete methods that could exploit this ability and hopefully outperform the state of the art inpainting methods;

3. To understand more deeply the asymptotic behaviour of Models II, II bis, III, III bis, and IV as the patch size r tends to 0. It is a well-known fact that, in practice, exemplar-based methods are interesting only for not too small values of r. However, we think that it is a valuable challenge trying to understand through a study of asymptotics whether our models are non local extensions of local evolution models. This could help understanding better their efficiency and their limitations, in particular regarding the recovery of geometry.

  0 (T (x + y)) -u 0 (T (x) + ∇T (x) y)| 2 dy dx with the constraints

lim r→0 +Theorem 3 . 2 (Definition 3 . 4 (

 r→03234 Br(x) |u(y) -z|dy = 0 Approximation by smooth function) Let u ∈ BV(Ω). Then there exists a sequence (u n ) ⊂ C ∞ (Ω) converging to u in L 1 (Ω) and satisfying|Du|(Ω) = lim n→∞ Ω |∇u n |dxBV can be endowed with different topologies. The strong topology does not have good compactness properties, and instead a weaker topology is used. Definition 3.3 (Weak- * convergence) Let u in BV(Ω), and a sequence (u n ) in BV(Ω). Then we say that u n weakly- * converges in BV(Ω) to u if u n converges to u in L 1 (Ω), and Du n weakly- * converges to Du in Ω, i.e. : lim n→+∞ Ω φ Du n = Ω φ Du for all φ in C 0 (Ω).The notion of strict convergence is useful to prove several properties in BV by smoothing arguments. Strict convergence) Let u in BV(Ω), and a sequence (u n ) in BV(Ω). Then we say that (u n ) strictly converges in BV(Ω) to u if (u n ) converges to u in L 1 (Ω) and the variations |Du n |(Ω) converge to |Du|(Ω) as n → +∞.

  Possibly taking a subsequence of (T n ), we deduce from the continuity of w and the Dominated Convergence Theorem that A+Br Br |w(T n (x + y)) -w(T (x + y))|dy dx → 0 (2) and A+Br Br |w(T n (x) + ∇T n (x)y) -w(T (x) + ∇T (x) y)|dy dx → 0 (3) Remark that A+Br Br |u 0 (T n (x) + ∇T n (x) y) -u 0 (T (x) + ∇T (x) y)|dy dx ≤ A+Br Br |u 0 (T n (x) + ∇T n (x) y) -w(T n (x) + ∇T n (x) y)|dy dx+ A+Br Br |w(T n (x) + ∇T n (x) y) -w(T (x) + ∇T (x) y)|dy dx+ A+Br Br |w(T (x) + ∇T (x) y) -u 0 (T (x) + ∇T (x) y)|dy dx

  Then we decompose A+Br Br |u 0 (T n (x + y)) -u 0 (T (x + y))|dy dx ≤ A+Br Br |u 0 (T n (x + y)) -w(T n (x + y))|dy dx+ A+Br Br |w(T n (x + y)) -w(T (x + y))|dy dx+ A+Br Br |w(T (x + y)) -u 0 (T (x + y))|dy dx and try to find a bound for sup n∈N A+Br Br [1 D 0 (T n (x + y)) + 1 D 0 (T (x + y))] dy dx.

Figure 3 :

 3 Figure 3: A simple situation where, for r small enough, two different translations have zero energy E 1 and yield completely different interpolations.

Lemma 6 . 4

 64 x) ∈ G} and C = {x / τ approximately differentiable at x and τ (x) ∈ G} . Obviously, C ⊂ C and L N (C\ C) = 0 because τ is approximately differentiable L N -almost everywhere by the Calderón-Zygmund Theorem [2]. Denoting N (y, C) = #{τ -1 (y) C} and applying the area formula for approximately differential maps (see for instance (5.5.2) in [3]) yield C | det(∇τ (x))| dx = τ ( C) N (y, C) dy = 0 since τ ( C) ⊂ τ (C) ⊂ G, and L N (G) = 0 according to the previous lemma. By assumption, det(∇τ (x)) = 0 L N -a.e., thus L N (C) = L N ( C) = 0 and the proposition ensues. Let u ∈ BV(Ω) and τ like in Lemma 6.3. Then |Du|(∂B r (x)) = 0 and |Du|(∂B r (T (x))) = 0 for L N -almost every x ∈ Ω.

  A+Br Br |u n (x+y)-u 0 (T n (x)+∇T n (x)y)| 2 dy dx → A+Br Br |u(x+y)-u 0 (T (x)+∇T (x) y)| 2 dy dx

  A+Br Br |u n (x+y)-u 0 (T n (x)+∇T n (x)y)| 2 dy dx → A+Br Br |u(x+y)-u 0 (T (x)+∇T (x) y)| 2 dy dx

Figure 4 :

 4 Figure 4: A is the inpainting domain. Outside A, the images takes either value 0 or 1.

Figure 5 :

 5 Figure 5: The three proposed interpolations: 5(a): "Good continuation" of the outer edges. 5(b): Shortest path continuation 5(c) Polygonal continuation (circle approximation).

Figure 6 :and ϕ x 2 look like 6

 626 Figure 6: Rectangular continuation: representation of y ∈ B r → ϕ x 1 (y) and y ∈ B r → ϕ x 2 (y) depending on the position of x in Figure 6(a). When x lives in region α, the graphs of ϕ x 1 and ϕ x 2 look like 6(b) and 6(c), respectively. When x belongs to region β then ϕ x 1 and ϕ x 2 are similar to 6(d) and 6(e).

Figure 7 :

 7 Figure 7: Connecting with a shortest path: the graphs of ϕ x 1 and ϕ x 2 on B r depend on the position of x in Figure 7(a). They are equivalent to 7(b) and 7(c), respectively, when x ∈ α ∪ β.

Figure 8 :

 8 Figure 8: Polygonal continuation: ϕ x 1 and ϕ x 2 are like Figures 8(b) and 8(c), when x is either in region α or in region β of 7(a). They are like Figures 8(d) and 8(e) when x ∈ γ.

Figure 9 :Figure 10 :

 910 Figure 9: As will be shown, "cutting" an angle decreases both E 1 and E 2 .

Figure 12 :

 12 Figure 12: The contribution to energy of the left configuration (plain curve) and right configuration (dashed curve) of Figure 9 for different values of θ, assuming that α = β = θ 2 + π 2 .

E a,b,c 2 (u, T ) = 1 r

 21 N A+Br Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| a dy dx + 1 r N -1+b A+Br |Du|(B r (x)) -|Du 0 |(B r (T (x))) + c dx We are interested in the values of a ≥ 1, b ∈ R and c > 0 for which either one or both following properties are fulfilled:(H1) the minimizers of E a,b,c 2 are stable with respect to any multiplicative contrast change, i.e., if (u, T ) is a minimizer of E a,b,c 2 with respect to u 0 then (λu, T ) is a minimizer of E a,b,c 2 with respect to λu 0 , for any λ > 0.

  k ), T ( . k )) is a minimizer of E a,b,c 2 with respect to kA, kr, u 0 ( . k ), one should have (N -1)c + 1 -b = N , thus b = (N -1)(c -1). Let us examine the different consequences: 1. If, like for the original E 2 , a = 2, b = 0 and c = 1, then (H2) is satisfied but not (H1). 2. If a = c = 1 and b = 0 then both (H1) and (H2) are satisfied, and the corresponding energy is a sort of L 1 -local TV version of exemplar-based inpainting. 3. If a = c = 2 and b = N -1 then both (H1) and (H2) are satisfied.

3 Rr 3 R 2 .

 332 2 ) and I 2 b,c = O( r 2+c r 1+b ). • The polygonal continuation tends as r goes to zero to a continuation with an arc of circle of radius R. Let us compute the energy of this limit continuation for a small patch size r. The contribution to the energy is localized in a band of width 2r covering the arc of circle. If x lies in this band, one can find an approximation of Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| a dy and |Du|(B r (x)) -|Du 0 |(B r (T (x))) + . It is indeed sufficient to observe that, up to a translation and rotation of the coordinates frame, these terms are obtained by comparing in B r (0) the x-axis with the graph y = R -√ R 2 -x 2 of the circle. For r small, the arc of circle can be approximated by the parabola y = x 2 2R . Then Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| a dy coincides with the area between the parabola and the x-axis whereas |Du|(B r (x))-|Du 0 |(B r (T (x))) + is approximately the length difference between the parabola on x ∈ [-r, r] and the segment [-r, r] × {0}. It is easy to calculate that Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| a dy = O r while |Du|(B r (x)) -|Du 0 |(B r (T (x))) Summing on a band of length O(R) and width 2r yields I 1 a = O(r 2 ) and I 2 b,c = O r 3c-b R 2c-1 .

a = 2 , 3 R 5 R 3 Figure 14 : 2

 2353142 Figure 14: Asymptotics of Term 1= 1 r 2 A+Br Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| a dy dx and Term 2= 1 r 1+b A+Br |Du|(B r (x)) -|Du 0 |(B r (T (x)))+ c

1 r 2N - 2 2 dx and to the following result: Theorem 8 . 1

 12281 Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| 2 dy dx + A+Br |Du|(B r (x)) -|Du 0 |(B r (T (x))) + The functional E bis 2 admits a minimizer (u, T ) in V 2

  ∩ B r (x) p dx = C p r 3p+1 ∂E |κ ∂E | p dH 1 + •(r 3p+1 )

Remark 8 . 3

 83 Consider the modified energyE bis 1 (T ) = x∈A+Br y∈Br |u 0 (T (x + y)) -u 0 (T (x) + ∇T (x) y)|dy p dxIf T poly is a generic piecewise rotation realizing the polygonal continuation of the previous section, one easily gets from the calculations above thatE bis 1 (T poly ) = O r 3p+1 R p-1

  In the second chart, we focus on Model II bis and compute E bis 2 /r 2 for different values of r. Coherently with the results of Figure14, E bis 2 /r 2 is constant for the shortest path continuation and the rectangular continuation and slowly decreases for the polygonal continuation. We can easily adapt the previous considerations to model III so that the following modification of E 3 can be proposed: A+Br |Du g |(B r (x)) -|Du g 0 |(B r (T (x)))

	r	Values of E bis 2 /r 2 Shortest path Rectangle Polygon	r	2 /r 2 Values of E bis Shortest path Rectangle Polygon
	1.0000	0.8367	1.3068	0.6454	0.0156	0.8367	1.3068	0.6207
	0.5000	′′	′′	0.6325	0.0078	′′	′′	0.6206
	0.2500	′′	′′	0.6263	0.0039	′′	′′	0.6205
	0.1250	′′	′′	0.6233	0.0020	′′	′′	0.6204
	0.0625	′′	′′	0.6218	0.0010	′′	′′	0.6204
	0.0312	′′	′′	0.6211
	Remark 8.2 Model III bis
	E bis
			+	1 r 2N -2 + 2
						II Model II bis
		Shortest path continuation	0.65	1.22	0.83
		Rectangular continuation	0.76	1.53	1.31
		Polygonal continuation	0.62	1.14	0.65

3 (u, u g , T ) = 1 r N A+Br Br |u(x + y) -u 0 (T (x) + ∇T (x) y)| 2 dy dx

By scale of a texture, we mean a positive number r, as small as possible, such that two arbitrary disjunct r × r windows have similar statistical moments up to a certain order.

Acknowledgements

We warmly thank Luigi Ambrosio and Gian Paolo Leonardi for their help.

This work has been done with the support of the French "Agence Nationale de la Recherche" (ANR), under grant FREEDOM (ANR07-JCJC-0048-01), "Films, REstauration Et DOnnées Manquantes".

the contribution of one last segment of length less than r. A reasonably good map T that produces such result is a piecewise roto-translation based on a triangular partition of the inpainting domain.

Numerical setting

Examining the functionals E 1 and E 2 associated with Models I and II we see that, once the x variable is fixed, the integration over the y variable amounts to the comparison of two functions defined on a ball of radius r. To compute the energies of the different configurations under study we need to evaluate with respect to the variable x the functions ϕ x 1 : y → u 0 (T (x + y)) and ϕ x 2 : y → u 0 (T (x) + ∇T (x) y). For each proposed inpainting we will present the different possible behaviors (with respect to x) of these functions, then a simple program will evaluate the respective energies of our functionals. For this particular choice of interpolations, the only difference between Model I and Model II is that the latter takes into account the length of the discontinuity set of ϕ x 1 and ϕ x 2 .

Prolonging the lines until they meet: the rectangular continuation We will examine in detail the case of the rectangular completion and give a rapid explanation for the other two inpaintings. In Figure 6(a), when x belongs to region α which is defined as the northeast half disk of center the right angle in the reconstruction and of radius r, the function 2 : y ∈ B r (0) → u 0 (T (x) + ∇T (x)y) maps B r to an analog of Figure 6(c). When x lies in region β which is defined as the set of points that do not belong to region α, are at a distance less than r from the horizontal continuation and are situated northwest of the right angle then the graph of ϕ x 1 is equivalent to Figure 6(d) and the graph of ϕ x 2 is equivalent to 6(e). Finally, for region γ we can change the transformation T such that it is a southeast translation of some large vector whenever x is situated at a distance larger than r from the continuation lines (and southeast of them). This does not change the values taken by the energies but yields ϕ x 1 (y) = ϕ x 2 (y) = 0 for every y ∈ B r (0). Of course the same thing happens for the southwest half plane under the diagonal line of Figure 6(a). Outside the described regions and their symmetric counterparts, both functions are identical.

The numerical evaluation of E 1 and E 2 is done as follows: we consider on R 2 a very fine grid

For each point x ∈ Γ ∩ (A + B r ) for which ϕ x 1 and ϕ x 2 may differ, we compute -it is an exact area computation -

using the configurations of ϕ x 1 and ϕ x 2 given in Figure 6. These terms are added for the finitely many x ∈ Γ ∩ (A + B r ) and E 1 ensues. A similar computation is done for E 2 to which the first-order term must be added. This is done using the sum for each x ∈ Γ∩(A+B r ) of the positive part of the difference between the lengths of the discontinuity sets of ϕ x 1 and ϕ x 2 . Again this latter calculation is exact.

Let us now briefly examine the configurations of ϕ x 1 and ϕ x 2 for the other two inpaintings under study.