Frédéric Cao
email: fcao@dxo.com

Yann Gousseau
email: gousseau@enst.fr

Simon Masnou
email: masnou@ann.jussieu.fr

Patrick Pérez
email: perez@irisa.fr

Patrick Pérez Geometrically

Geometrically guided exemplar-based inpainting

Keywords: Inpainting, texture synthesis, level lines, image geometry, Euler spirals

come

Introduction and motivations

The last ten years have witnessed many contributions to the inpainting problem in digital images, i.e. the problem of recovering entire regions where the information either has been lost or is partially occluded by undesired objects. The two main applications of inpainting methods are image restoration (e.g. the suppression of scratches and blotches in old pictures and movies) and image manipulation (e.g. the removal of objects in postproduction).

There are basically three categories of methods in the literature. The variational or PDE-based approaches enable in favorable cases a good reconstruction of the global geometry of an image but fail at correctly synthesizing the texture. In contrast, the methods of the second category were initially designed for texture synthesis. Some of them that we will describe later, called exemplar-based, can produce visually striking results but often do not permit the interpolation of non repetitive global image structures such as long edges. Finally, methods in the third category do not involve any explicit interpolation in the image domain but rather in one or several transform spaces, relying e.g. on wavelets or Fourier transform. They usually perform well for sparse missing data or thin domains.

Recently, there have been several attempts to combine variational/PDE methods with exemplar-based algorithms in order to deal with those situations where the latter alone fail at recovering the geometry. This is the spirit of the method presented here that first completes the geometry for a simplified version of the image then uses it as a weakly constraining guide for a complete reconstruction.

State of the art

Geometric methods

The different approaches to geometrical inpainting are all based on the prior that geometry can be recovered from the close neighborhood of the inpainting domain. They divide into two categories:

1. the variational methods that involve a criterion of regularity of the reconstruction; 2. the pure PDE methods that try to diffuse and/or advect progressively the information from the boundary.

The first variational approach to geometrical inpainting has been proposed in 1998 in [START_REF] Masnou | Level lines based disocclusion[END_REF], see also [START_REF] Masnou | Disocclusion : a variational approach using level lines[END_REF], following an inspiring work by Nitzberg, Mumford and Shiota [START_REF] Nitzberg | Filtering, segmentation and depth[END_REF] on amodal completion and depth computing based on Kanizsa's vision theory [START_REF] Kanizsa | Organization in Vision: Essays on Gestalt Perception[END_REF]. The basic idea of [START_REF] Masnou | Level lines based disocclusion[END_REF] is that the geometry can be reconstructed in the inpainting domain by simply interpolating -using short and not too oscillating curves -all level lines that touch the domain boundary. This appears to be equivalent to minimizing a functional involving the curvature to a power p. Further details will be given in Section 4. A globally minimizing scheme is proposed in [START_REF] Masnou | Level lines based disocclusion[END_REF] for the case p = 1 while the local minimization in the case p > 1 is addressed in [START_REF] Chan | Euler's elastica and curvature based inpainting[END_REF]. Starting from the same model, an interesting relaxed formulation is proposed in [START_REF] Ballester | Filling-in by joint interpolation of vector fields and gray levels[END_REF] that yields a second-order Euler-Lagrange equation. This last equation is much more convenient for numerical computation than the fourth-order equation of [START_REF] Chan | Euler's elastica and curvature based inpainting[END_REF].

A totally different approach has been proposed by Bertalmio, Sapiro, Caselles and Ballester in [START_REF] Bertalmio | Image inpainting[END_REF], where the term inpainting has been proposed for the first time in this context. The idea is to mimic the way professionals do inpainting for real paintings restoration. It consists in progressively advecting the valid information from the boundary of the inpainting domain inwards using a third-order advection-type equation. This equation transports the image values along continuations of edges, an additional anisotropic diffusion being used to avoid shocks. An interesting interpretation of the model is given in [START_REF] Bornemann | Fast image inpainting based on coherence transport[END_REF] and the connections with the classical Navier-Stokes equation of fluid dynamics are shown in [START_REF] Bertalmio | Navier-Stokes, fluid dynamics, and image and video inpainting[END_REF].

Using a more global approach, Chan and Shen propose in [START_REF] Chan | Mathematical models for local deterministic inpaintings[END_REF] a denoising/interpolation model based on the joint minimization of a quadratic fidelity term and a total variation criterion. This latter makes actually sense only for thin inpainting domains because its minimizers are images having the shortest level lines. A variant of the associated Euler-Lagrange equation is studied in [START_REF] Chan | Non-texture inpainting by curvaturedriven diffusion (CDD)[END_REF].

Elder and Goldberg propose in [START_REF] Elder | Image editing in the contour domain[END_REF] an approach to image editing based on the manipulation of the edge map. A possible application is the removal of objects in some simple situations: the corresponding edges are first removed from the edge map, the remaining edges are completed if necessary with, possibly, the help of the user, and the final image is obtained by a linear interpolation out of the edges.

Esedoglu and Shen propose in [START_REF] Esedoglu | Digital image inpainting by the Mumford-Shah-Euler image model[END_REF] to interpolate in the inpainting domain using a piecewise smooth function that minimizes the Mumford-Shah functional with an additional penalization, so that the discontinuity set has small Euler's elastica energy (see below), i.e. is short and not too curvy, see [START_REF] Esedoglu | Threshold dynamics for shape reconstruction and disocclusion[END_REF] for an interesting implementation of the model.

Grossauer and Scherzer study in [START_REF] Grossauer | Using the complex Ginzburg-Landau equation for digital inpainting in 2D and 3D. In Springer[END_REF] an inpainting model based on Ginzburg-Landau's equation. In [START_REF] Tschumperlé | Vector-valued image regularization with PDE's : a common framework for different applications[END_REF], Tschumperlé and Deriche propose an efficient secondorder anisotropic diffusion equation that preserves curvature and gives good results. The approach of D. Auroux and M. Masmoudi in [START_REF] Auroux | A one-shot inpainting algorithm based on the topological asymptotic analysis[END_REF] uses the PDE techniques that have been developed for the inverse conductivity problem in the context of crack detection. In [START_REF] Atzori | Error concealment in video transmission over packet networks by a sketch-based approach[END_REF][START_REF] Rares | Edge-based image restoration[END_REF] a prior segmentation of the edges outside the inpainting domain is performed. Then edges are interpolated -using splines in [START_REF] Atzori | Error concealment in video transmission over packet networks by a sketch-based approach[END_REF], arc of circles in [START_REF] Rares | Edge-based image restoration[END_REF] -and the inpainting is completed using a smooth interpolation between edges. The tricky part of such an approach is the careful choice of pairs of edges that will be connected.

Finally, in an attempt to improve the fast but limited method proposed by A. Telea [START_REF] Telea | An image inpainting technique based on the fast marching method[END_REF], F. Bornemann and T. März described in [START_REF] Bornemann | Fast image inpainting based on coherence transport[END_REF] a fast first-order equation that advects the image information along the characteristics of a coherence vector field that extends inside the inpainting domain the dominant directions of the outside gradient. The method is based on a fast-marching scheme and thus very fast. In terms of speed and quality of the results, it is one of the best PDE approaches to the inpainting problem, together with [START_REF] Tschumperlé | Vector-valued image regularization with PDE's : a common framework for different applications[END_REF].

There is however a common drawback to all PDE or variational methods that we have presented so far: they are unable to properly restore the texture, in contrast to the approaches that we will now describe.

From texture synthesis to inpainting: exemplar-based methods

For a long time, texture synthesis has been formulated as a problem of learning then sampling a probability distribution [START_REF] Besag | Spatial interaction and the statistical analysis of lattice systems[END_REF][START_REF] Cross | Markov random fields texture models[END_REF][START_REF] Zhu | Filters, random fields and maximum entropy (FRAME)[END_REF]. This approach may provide good results but is usually computationally expensive and the choice of a suitable model distribution is very sensitive . De Bonet studies in [START_REF] De | Multiresolution sampling procedure for analysis and synthesis of texture images[END_REF] a multiresolution technique where interscale dependencies of texture samples are constrained. Drawing their inspiration from psychophysics experiments, Heeger and Bergen [START_REF] Heeger | Pyramid based texture analysis/synthesis[END_REF] propose to synthesize a texture by constraining the marginals of overcomplete wavelet decompositions. This work has been followed by others in which not only the marginals but also more complicated statistics on wavelet decompositions were constrained, see [START_REF] Simoncelli | Texture characterisation via joint statistics of wavelet coefficient magnitudes[END_REF]. All these methods may provide good results but not for all situations: highly structured patterns are usually badly synthesized.

New models have been proposed in the late 90's that appear to be much more efficient [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF][START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF][START_REF] Wei | Fast texture synthesis using treestructured vector quantization[END_REF]. Exploiting the locality and the stationarity at a certain scale 1 of the texture, they achieve a degree of realism that was beyond the reach of previous approaches. The first celebrated algorithms in the class of exemplarbased methods, due to Efros and Leung [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF] and Wei and Levoy [START_REF] Wei | Fast texture synthesis using treestructured vector quantization[END_REF], both involve the notion of patch, i.e. a square window of size r × r. The basic idea is that in order to synthesize the value at a pixel whose neighborhood is partially known, one looks for similar patches in a sample image (when performing texture synthesis) or in a valid part of the image (when performing inpainting). The gray or color value at the pixel is simply chosen as the value of the central pixel of the most resembling patch or sampled from a set of very similar patches, the similarity between patches being generally measured with a weighted L 2 metric. 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 treestructured 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], involving for instance a multiscale approach and a careful synthesis order. 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 dedication 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, 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 reducing the space of interpolation possibilities, 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: Examplebased 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], 1]:

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

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 and obtained in a very reasonable time, even for large inpainting domains. Most approaches of this kind are not only able to reproduce a texture but are also very good at restoring a local geometric information whenever it can be obtained elsewhere in the image.

Optimizing in a transform domain

There have been in recent years several contributions where the inpainting problem is formulated as an optimization task in a transform domain, e.g. Fourier, wavelets, framelets, etc. It usually amounts to finding the reconstructed image whose representation in the transform domain is optimal. For instance, a simultaneous geometry/texture inpainting is performed in [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]) by optimizing the decomposition in two different transform domains, one giving a sparse representation of the geometry (the curvelets domain) and the other adapted to the texture (the DCT domain). Other approaches in this category are [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]. All these methods are usually very efficient when the unknown part of the image is a sparse set of pixels.

In case where the inpainting domain is large, however, they are clearly outperformed by exemplar-based methods.

Combining texture synthesis and geometric reconstruction

Several papers on inpainting have been concerned with the combination of a PDE or variational model for the reconstruction of the geometry together with an exemplar-based algorithm for the reconstruction of texture. In [START_REF] Bertalmio | Simultaneous structure and texture image inpainting[END_REF], the image is first decomposed into a geometric and a texture component using a technique described in [START_REF] Vese | Modeling textures with total variation minimization and oscillating patterns in image processing[END_REF]. The geometric component is inpainted by the model in [START_REF] Bertalmio | Image inpainting[END_REF], the texture component is restored using the Efros-Leung's algorithm [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF] and the final image is the sum of both reconstructions. There is no such explicit decomposition in [START_REF] Drori | Fragment-based image completion[END_REF] but rather a prior fast estimate of the colors of the hidden region by a multiscale filtering approach that guides the exemplar-based inpainting. This is also the spirit of [START_REF] Do | Inpainting d'images couleurs par lissage anisotrope et synthèse de textures[END_REF] except that the guide is obtained with the very efficient PDE model for geometrical inpainting of [START_REF] Tschumperlé | Vector-valued image regularization with PDE's : a common framework for different applications[END_REF] that we presented above. The method presented in [START_REF] Jia | Image repairing: Robust image synthesis by adpative ND tensor voting[END_REF] consists in a prior edge segmentation in the known part of the image followed by a completion of the edges in the inpainting domain. This yields a partition of the domain that guides the final reconstruction done with a tensor voting technique.

The exemplar-based approach of [START_REF] Criminisi | Object removal by exemplar-based inpainting[END_REF] has been an inspiration for our paper. It involves indeed a local geometrical guiding though a priority term that forces the reconstruction of strong edges first. In the current paper, we build instead a global geometrical guiding.

Eventually, in [START_REF] Sun | Image completion with structure propagation[END_REF], the user manually draws the geometric structure in the inpainting domain then exemplarbased inpainting is performed, first along the edges then in the rest of the domain.

Our contribution

The method presented in this paper is in the spirit of some of the approaches above. Our motivation is to propose an algorithm that exploits the performances of the best exemplar-based methods in addition with the ability to recover long-range geometric structures, possibly more complex than straight lines. The first step of our method is the creation of a simplified representation of the valid part of the image -a sketch -that essentially contains the important geometric features (Section 3). The sketch is then interpolated in the inpainting domain using a variational model that computes an "optimal" set of curves completing the "broken" level lines (Section 4). Finally, in Section 6, the fully reconstructed sketch is used as a data term in an optimization formulation that extends the exemplarbased method from [START_REF] Pérez | PatchWorks: Examplebased region tiling for image editing[END_REF] that we present in Section 5. As will be clear from a few experiments that we will present, this approach enables, in some situations, to take into account the geometry in a much more global way than classical exemplar-based methods. As we previously mentioned, the latter already have the ability to locally restore the geometry. Is there a way to assert this fact theoretically? We provide a partial answer in Section 5.2 where we investigate the ability to asymptotically recover a curve starting from patches made of straight lines.

Computing a sketch of the image

By sketch of a gray level image (the color case will be addressed later on), we mean a piecewise constant approximation obtained with a suitable segmentation procedure. The segmentation used in this paper is derived from the topographic map of the image [START_REF] Caselles | Topographic maps and local contrast changes in natural images[END_REF] and, more precisely, from the meaningful level lines defined in [START_REF] Desolneux | Edge detection by Helmohltz principle[END_REF] (other segmentation procedures could be used to compute a sketch). Recall that the topographic map of a gray level image I is the collection of all its level lines, that we define here as the connected components of the boundaries of upper levels sets X t (I) = {x : I(x) ≥ t} (similar results would be obtained with the lower level sets). Since

I(x) = sup{t : x ∈ X t (I)}, (1)
the image can be completely reconstructed from its level lines. This complete representation has several advantages. First, it is invariant with respect to increasing contrast changes and, secondly, the topographic map can be associated with a nested tree structure that is very useful for image denoising [START_REF] Monasse | Fast computation of a contrastinvariant image representation[END_REF], shape extraction and comparison [START_REF] Lisani | On the theory of planar shape[END_REF] or compression [START_REF] Froment | A compact and multiscale image model based on level sets[END_REF].

A sketch of the initial gray level image is obtained by keeping only the most significant level lines, i.e. those that are contrasted enough according to an a contrario criterion [START_REF] Desolneux | Edge detection by Helmohltz principle[END_REF]. Roughly speaking, meaningful lines are lines having a contrast that is very unlikely to be encountered in a white noise image. More precisely, we only keep lines L for which

N H(c(L)) l(L) ≤ ǫ, ( 2
)
where N is the total number of level lines in the image, H is the cumulative histogram of the modulus of the gradient over the image, l(L) is the length of the line, c(L) is the minimum contrast along the line, and ǫ is a positive number. In practice, we use a refinement of this approach as presented in [START_REF] Cao | Extracting meaningful curves from images[END_REF]. It consists in using a local estimation of the cumulated gradient histogram H to assert for the meaningfulness of a curve. We chose to use this refinement because it yields less detection in textured area, a desirable property for the application considered in this paper.

Remark that extracting the most significant level lines does not mean extracting the objects in the image but constructing a piecewise constant image whose dynamics are very close to the original. However, as observed in [START_REF] Lisani | On the theory of planar shape[END_REF], boundaries of objects usually locally coincide with pieces of level lines, so that the most salient objects will appear in the sketch representation. We did not specify until now how a piecewise constant image can be obtained from a collection of curves: relying on the nested structure of the topographic map, we simply define the value of the sketch at a pixel x as the level associated with the smallest level line that encloses x.

The above procedure for computing a sketch is valid for gray level images only but can be extended to color images thanks to the following heuristic argument (see [START_REF] Caselles | Geometry and color in natural images[END_REF]): the geometric information contained in a real world color image is essentially carried by the luminance channel of any classical luminance/chrominance color representation, e.g. YUV, L*a*b, etc. Therefore, a color sketch associated to a color image can be obtained in the following way: first compute a sketch of the luminance component and consider the associated partition of the domain; then, for each chrominance channel, re-place every pixel value by the average value computed on the corresponding component of the partition. An example of meaningful lines and color sketch is shown in Figure 1, using a value of ǫ = 1 in Formula (2), as in all experiments to be displayed in this paper.

It must be emphasized however that this extension to color is useless for the global inpainting method presented in this paper. Since we are interested in a geometric guiding of the exemplar-based inpainting method to be presented in Section 5, we will actually use as a geometric guide the reconstruction of a gray level sketch computed from the luminance channel of the original image to be inpainted (the YUV color model has been used in all experiments presented below). Let us now describe in detail two geometry-oriented inpainting methods that will be used for the reconstruction of the sketch image. Both of them are based on the interpolation of the broken level lines.

Level lines completion, image inpainting and sketch reconstruction

We describe in this section two geometrical inpainting methods for color images, i.e. two methods essentially devoted to the reconstruction of geometry. The first one, introduced in [START_REF] Masnou | Level lines based disocclusion[END_REF], is based on the completion of level lines by straight curves, whereas the second approach is new and uses Euler spirals as completion curves. We will see at the end of the section that both methods can be used for the reconstruction of a sketch image aimed to be a geometric guide for the global inpainting algorithm to be presented in Section 6.

The notion of level lines is clear for gray level images (see the previous section) but not for color images. Like in the previous section, we will actually generalize to color a method designed for gray level images. More precisely, given a method that interpolates the broken level lines of a scalar image, the reconstruction of a color image will be performed by independently processing the luminance and both chrominance channels in a suitable luminance/chrominance representation (YUV, L*a*b, etc.). Note that using a luminance/chrominance representation instead of the usual RGB is crucial for limiting the creation of false colors.

We now show how an inpainting method can be derived from shape completion techniques.

From amodal completion to inpainting

Recall that, given a regular curve C in the plane parameterized by arc-length, the elastica functional 2

L(C) 0 |κ C (s)| 2 ds, (3)
where κ C denotes the curvature and L(C) the length of the curve, measures the elastic energy stored by the curve. It has been first studied in 1744 by Euler in his work on the physics of thin rods. Much later, it has been proposed by Ullman [START_REF] Ullman | Filling-in the gaps: the shape of subjective contours and a model for their generation[END_REF] and Horn [START_REF] Horn | The curve of least energy[END_REF] in the context of shape completion. Recall that our visual system has the ability to reconstruct missing edges when objects are partially occluded, see the important contribution of G. Kanizsa [START_REF] Kanizsa | Organization in Vision: Essays on Gestalt Perception[END_REF] on the so-called amodal completion. In terms of computer vision, the problem can be rephrased as follows: what is the most "pleasing" curve that joins two points with prescribed tangent boundary conditions. The elasticae, i.e. the curves minimizing the elastica energy, are natural candidates since they are the smoothest curves in regard to the accumulated elastic energy. Elasticae are however hard to compute for they do not admit any analytical expression [START_REF] Mumford | Elastica and computer vision[END_REF]. There have been many attempts to derive efficient approximation methods, either for the elastica energy itself or for variants such as L L(C) 0 |κ| 2 ds which is scale invariant, see [START_REF] Leung | Contour continuity in region based image segmentation[END_REF][START_REF] Nitzberg | Filtering, segmentation and depth[END_REF][START_REF] Sharon | Completion energies and scale[END_REF][START_REF] Thornber | Analytic solution of stochastic completion fields[END_REF][START_REF] Thornber | Characterizing the distribution of completion shapes with corners using a mixture of random processes[END_REF][START_REF] Williams | Stochastic completion fields : A neural model of illusory contour shape and salience[END_REF][START_REF] Citti | A cortical based model of perceptual completion in the roto-translation space[END_REF][START_REF] Bruckstein | Discrete elastica[END_REF].

Although nice completions can be obtained with the elastica model, it has some drawbacks, such as the computational issues we have mentioned but also the incapacity to recover angles or circles, the non existence of a minimizer in some extreme boundary conditions, etc. Other models have therefore been proposed, considering however that no model can always provide the perfect solution, essentially because the problem is illposed: the question whether a curve is "pleasing" or not is somewhat subjective and nothing totally reliable can be said in some extreme situations. We mention however two other models that yield interesting solutions in most common situations:

1. the minimal path/good continuation model of Fantoni and Gerbino that computes an intermediate solution between the straight line and the polygonal line obtained by simply continuing the tangents from each extremity, see [START_REF] Fantoni | Contour interpolation by vector field combination[END_REF] where an exhaustive survey of completion models is provided; 2. the Euler spiral -also called Cornu's spiral or clothoid loop -that has been studied by Euler in his work on freely coiled up elastic springs and accurately

2 more general versions are R (α + β|κ C (s)| 2 )ds.
plotted by Cornu in 1874. In the relaxed position of the spring -modeled as a curve γ -the scalar curvature at each point satisfies κ(s) = C 1 s + C 2 where C 1 , C 2 are constant and s is the arc-length. Euler spirals have already been used in the context of shape completion, see for instance [START_REF] Kimia | Euler spiral for shape completion[END_REF].

Completing one broken curve using one of these two models is not difficult. A more difficult task is to complete many curves because there are n! possible pairwise connections of 2n interrupted lines. Is there a particular family of connections that makes sense in the context of image inpainting? Can it be obtained without using an algorithm with exponential complexity? Let us start with a model that has been initially proposed in [START_REF] Masnou | Level lines based disocclusion[END_REF][START_REF] Masnou | Disocclusion : a variational approach using level lines[END_REF] and that involves straight lines as very basic interpolating curves. 4.2 A simple inpainting algorithm using straight lines [START_REF] Masnou | Level lines based disocclusion[END_REF][START_REF] Masnou | Disocclusion : a variational approach using level lines[END_REF] The algorithm described in [START_REF] Masnou | Level lines based disocclusion[END_REF][START_REF] Masnou | Disocclusion : a variational approach using level lines[END_REF] for the inpainting of gray level images is shown in Table 1. The extension to color images is straightforward by independently restoring each channel in a luminance-chrominance representation.

As discussed in [START_REF] Masnou | Level lines based disocclusion[END_REF][START_REF] Masnou | Disocclusion : a variational approach using level lines[END_REF], this approach is equivalent to finding an image whose level lines in the inpainting domain are minimizers of the functional (α + β|κ|)ds. Despite its limitations -optimal curves are polygonal lines -this model produces interesting results in a reasonable time. The global optimization is indeed performed with a dynamic programming approach thanks to a causality principle satisfied by the T-junctions. More precisely, we impose that for any two pairs of connected T-junctions, the corresponding intervals on the boundary of the inpainting domain are either disjoint or nested. This ensures that the connecting straight lines do not mutually cross so that a function can be easily reconstructed by simple propagation between the reconstructed lines. The causality principle yields a considerable reduction of the optimization, which runs in O(N 3 ) with respect to the number N of T-junctions thus approximately in O(M

2 ) with respect to the number M of pixels in the inpainting domain.

We now describe a new geometrical inpainting approach using Euler spirals for the completion of broken level lines.

Inpainting with straight lines [START_REF] Masnou | Level lines based disocclusion[END_REF][START_REF] Masnou | Disocclusion : a variational approach using level lines[END_REF] 1. extract all termination points on the inpainting domain's boundary of the level lines associated with the sketch; these points are called T-junctions, in reference to the term used by G. Kanizsa [START_REF] Kanizsa | Organization in Vision: Essays on Gestalt Perception[END_REF] to name the points where the edge of a partially occluded object encounters the edge of an occluding object; 2. compute the associated tangents by a simple averaging approach [START_REF] Masnou | Level lines based disocclusion[END_REF][START_REF] Masnou | Disocclusion : a variational approach using level lines[END_REF]; 3. find an optimal set of curves that connect pairs of T-junctions that have the same level, under the constraint that any two curves do not cross and each curve can be generically identified with the boundary of a level set. The optimality criterion takes into account a linear combination of the curves total length and total curvature, including the angles at the extremities; 4. find the generic piecewise constant function associated with the reconstructed family of level lines.

Table 1 Algorithm from [START_REF] Masnou | Level lines based disocclusion[END_REF][START_REF] Masnou | Disocclusion : a variational approach using level lines[END_REF] for the geometrical inpainting of gray level images using straight lines. The inpainting of color images is done by independently processing each channel in a luminance/chrominance representation, e.g. YUV.

A new inpainting method using Euler spirals as interpolation curves

Let us first discuss the computation of a Euler spiral joining two points with prescribed tangents at both ends. Interestingly, there is a close connection between elasticae and Euler spirals as explained in [START_REF] Coope | Curve interpolation with nonlinear spiral splines[END_REF]. Parameterizing a curve γ by arc-length and denoting as ψ the inclination at γ(s), i.e. the oriented angle between the x-axis and the tangent γ ′ (s), the elastica functional reads as

L(γ) 0 |ψ ′ (s)| 2 ds, (4)
from which the following Euler-Lagrange equation can be derived, taking into account the transversality condition due to the unknown length L(γ) [START_REF] Coope | Curve interpolation with nonlinear spiral splines[END_REF]:

(ψ ′ (s)) 2 = λ cos ψ(s) + µ sin ψ(s). (5)
After linearization, one gets

(ψ ′ (s)) 2 = λ + µψ(s), (6)
whose solutions satisfy

ψ(s) = µ 4 (s -α) 2 - λ µ , (7)
where α is a constant of integration, Since the scalar curvature coincides with ψ ′ (s), we deduce that Euler spirals are the solutions of [START_REF] Bertalmio | Image inpainting[END_REF]. Such spirals, which include circles and are rotationally invariant in contrast to splines, can therefore be considered as approximations of elasticae. They have other interesting properties, for example they can serve as C 2 transitions between a segment and an arc of circle, which explains that they are frequently used in very concrete applications, e.g. architecture, road design, typography and even for the design of roller coasters! Integrating [START_REF] Bertalmio | Image inpainting[END_REF], one obtains that the curve can be parameterized as (x(s), y(s)) = (x 0 , y 0 ) + that can be easily approximated from their Taylor expansion. Different methods have been proposed to find a numerical approximation of the Euler spiral joining two points with tangent boundary conditions [START_REF] Meek | A note on finding clothoids[END_REF][START_REF] Bruckstein | Discrete elastica[END_REF].

Here we use the rather simple approximation algorithm proposed in [START_REF] Coope | Curve interpolation with nonlinear spiral splines[END_REF] that involves an iterated Newton's scheme. Additional constraints are necessary to avoid solutions with loops but even in that case uniqueness is not always guaranteed: one can easily find two spirals with same energy that join the point (0, 0) to (1, 0) with initial direction (1, 0) and final direction (-1, 0). In this kind of situation, one may force a particular solution by imposing to the tangent along the curve a suitable range of allowed directions.

Let us now describe the adaptation to Euler spirals of the algorithm presented in the previous section. A first important point -for it influences a lot the shape of the spirals -is a careful computation of the tangent at each T-junction of the "broken" level lines. We follow the method due to F. Bornemann and T. März [START_REF] Bornemann | Fast image inpainting based on coherence transport[END_REF] after the work of J. Weickert [START_REF] Weickert | Anisotropic diffusion in image processing[END_REF][START_REF] Weickert | Coherence-enhancing shock filters[END_REF] on the robust determination of coherence directions in image. Denoting as Ω the image domain, A the inpainting domain (that we assume to be at a positive distance from the boundary of Ω) and I S the sketch on Ω \ A computed according to the previous section, the coherent direction at x ∈ A is defined as the normalized eigenvector associated to the minimal eigenvalue of the structure tensor [START_REF] Bornemann | Fast image inpainting based on coherence transport[END_REF]:

J(x) = K ρ ⋆ 1 Ω\A ∇I S σ ⊗ ∇I S σ (x) K ρ ⋆ 1 Ω\A (x) (11)
where 1 Ω\A is the characteristic function of Ω \ A, K ρ is a smoothing kernel and I S σ is defined by

I S σ = K σ ⋆ 1 Ω\A I S K σ ⋆ 1 Ω\A , (12)
Inpainting with Euler spirals

Due to the exponential complexity, the minimization is performed over all configurations only if the number of T-junctions (at level t) is low (in practice 6 is a reasonable choice). Otherwise the minimization is performed only over the configurations that respect the causality principle on the boundary; (c) build a binary set Et by superposing all subsets enclosed by two interpolating curves, like in Figure 2; 4. get the complete sketch at every pixel x ∈ A by the formula

I S (x) = N 1 + X t∈{N 1 ,••• ,N 2 } 1 E t (x) (10)
Table 2 Algorithm for the inpainting of gray level images with Euler spirals. The inpainting of color images can be done by independently processing each channel in a luminance/chrominance representation, e.g. YUV.

with K σ another smoothing kernel. It can be experimentally observed that this computation yields a reliable estimation of the level lines directions at the Tjunctions (a sensible choice for the convolution parameters is σ = 1.5, ρ = 4).

The second important point is how one can handle several possibly crossing Euler spirals. We mentioned in the previous section that such problem does not occur with straight lines if the connection model satisfies a causality principle: in such case, the inpainting result is obtained by propagation between interpolated curves. If we now use Euler spirals, it is easily checked that the causality principle does not guarantee anymore that any two curves will not mutually cross. In addition, there are cases where crossing curves are the right solution (see Figure 2) so one must handle properly this situation. The new algorithm that we propose for the geometrical inpainting of gray level images is shown in Table 2. Again, the generalization to color can be done by independently processing the three channels in a luminance/chrominance color space.

The reason why we use Formula (10) comes from a classical result: any measurable positive function u :

Ω → R satisfies at almost every point x ∈ Ω, u(x) = +∞ 0 1 {y: u(y)≥t} (x)dt (13) Obviously, if u takes values in [t 1 , t 2 ] then u(x) = t 1 + t2 t1
1 {y: u(y)≥t} (x)dt, [START_REF] Cai | A framelet-based image inpainting algorithm[END_REF] and [START_REF] De | Multiresolution sampling procedure for analysis and synthesis of texture images[END_REF] follows. Remark however that, contrary to what happens with the level sets {y : u(y) ≥ t} t≥0 of the function u, our family of reconstructed sets E t needs not being nested therefore ( 10) is not the exact counterpart of ( 13). Yet our tests show that it is a reasonable choice, much more sensible for instance than the formula I S (x) = sup{t : x ∈ X t } which is very sensitive to completion errors that might occur at the highest levels.

Results and application to sketch reconstruction

We present in Figures 345three examples of geometrical inpainting using either straight lines or Euler spirals. We illustrate in particular in Figure 5 how the technique naturally applies for reconstructing a geometric sketch obtained with the algorithm described in section 3.

It now remains, in order to design a geometry-guided inpainting method, to combine the sketch completion with an exemplar-based inpainting algorithm. We describe in the next section the particular instance of exemplar-based method that we will use.

Fig. 3 Top: original color image with an occluded zone. The transparency of the occlusion is only for information. Only the outer information is used for the reconstruction. Bottom: Result after inpainting with straight lines [START_REF] Masnou | Level lines based disocclusion[END_REF] of each channel in a YUV representation.

A closer look at exemplar-based inpainting

In this section we first detail a robust and efficient exemplar-based inpainting algorithm, the "patchwork" algorithm introduced in [START_REF] Pérez | PatchWorks: Examplebased region tiling for image editing[END_REF], that we will use later on. The inpainting is performed by copying entire patches taken in the valid part of the image, which allows a much better reconstruction of simple geometric structures in comparison the methods that involve only one pixel at a time. Then, in Section 5.2, we state a result showing a theoretical connection between patchbased inpainting and the reconstruction of geometry.

5.1

The "patchwork" algorithm from [START_REF] Pérez | PatchWorks: Examplebased region tiling for image editing[END_REF] We consider a gray-scale or color image I defined on a discrete domain Ω ⊂ Z 2 and we denote as A ⊂⊂ Ω the inpainting domain. Given p ∈ N, the patch Γ p (x) of a point x ∈ A is defined as the discrete (2p + 1) 2square centered at x. Such a neighborhood is called a patch. We will also use this word to refer to the values taken by I on the square. To q > p ∈ N we associate the ring B p,q (x) = Γ q (x) \ Γ p (x). Both sets of patches and rings are endowed with the L 2 metric. If G ⊂ Z 2 , ∂G denotes its inner boundary, that is the set of points that are in G and have at least one neighbor in its complementary set G c . We also consider the set of all centers of neighborhoods that are included in A c ,

E q = {x ∈ Ω : Γ q (x) ⊂ A c }. ( 15
)
Eventually, we consider the set of patches intersecting A and lying on a regular grid with a mesh of size (2p+1) 2 .

That is, we define

F q = {Γ p (x), x = (k(2p + 1) + p, l(2p + 1) + p) , k, l ∈ Z and Γ p (x) ∩ A = ∅}. ( 16
)
The basic idea of the algorithm is that the unknown parts of patches from F q will be sequentially updated using a dictionary made up of patches centered at points of E q .

Given two integers p < q, the algorithm consists in replacing the unknown part of a patch Γ p (x) intersecting A with the values of the patch Γ p (y) where y is such that the distance between the rings B p,q (x) and B p,q (y) is minimal. In other words, the comparison and the copy involve different pixels and the fact that B p,q (x) encloses Γ p (x) avoids blocky effects. Indeed, the patches progressively inpainted by the algorithm do not overlap but the associated rings do overlap. This is an important issue for blocky effects are a noticeable drawback of many exemplar-based methods. The algorithm is summarized in Table 3 for color images (I 1 , I 2 , I 3 ) in a RGB representation. To deal with cases where the inpainting domain touches the border of the image, a prior artificial extension by mirroring of the image domain can be done.

This method gives impressive results on natural images, as may be seen on Figure 6. It essentially depends on two parameters : the size (2p + 1) 2 of the patches to be copied and the size (2q + 1) 2 of the neighborhood used to quantify the similarity of two patches. Usually, small values of p yield good results for weakly structured texture images. The case p = 0 corresponds to the original algorithm of Efros and Leung. Larger values of Exemplar-based algorithm [START_REF] Pérez | PatchWorks: Examplebased region tiling for image editing[END_REF] 1. Let Γp(x 0 ) be a patch from Fq such that the intersection between Bp,q(x 0 ) and A c has maximal area (a selection criterion such as the one proposed in [START_REF] Criminisi | Object removal by exemplar-based inpainting[END_REF] could also be used); 2. Let y 0 be defined as

y 0 = argmin y∈Eq X k=1,2,3 X y i ∈Bp,q (y) y i -y+x 0 ∈A c ˛Ik (y i ) -I k (x 0 -y + y i ) ˛2 (17)
i.e. y 0 is the center of the patch in A c whose associated ring is the most similar to the ring associated with the patch centered at

x 0 ; 3. For each x ∈ Γp(x 0 ) ∩ A, let I k (x) = I k (y 0 + x -x 0 ), k = 1, 2, 3; 4. Replace Fp with Fp \ Γp(x 0 ) and go to 1 if Fp = ∅.
Table 3 Exemplar-based algorithm [START_REF] Pérez | PatchWorks: Examplebased region tiling for image editing[END_REF] for a color image (I 1 , I 2 , I 3 ) in a RGB representation.

p give better results in the presence of geometric structures. Indeed, large patches enable the propagation of straight edges whereas small values of p may lead to the creation of erratically oscillating structures. However, even though edges are somehow preserved when using large patches, two problems remain for achieving a satisfying reproduction of geometry. First, curved edges are not well prolongated if a suitable curvy piece of edge cannot be found elsewhere in the image. A solution would be to enlarge the dictionary of patches by simply taking rotated versions. This sometimes yields nice results but erratic results often occur when the dictionary becomes too rich. Second, exemplar-based methods are local or semi-local and therefore long edges crossing the missing part of the image cannot always be satisfactorily restored. Bottom: reconstructed image using the exemplar-based method from [START_REF] Pérez | PatchWorks: Examplebased region tiling for image editing[END_REF] (with p = 4 and q = 6).

Patches metric and curvature

We now briefly investigate a connection between the exemplar-based approach that we just described and the restoration of geometry. It is obvious from the experiments that exemplar-based inpainting methods do not only restore texture but also a local geometric information. This is not surprising since copying a patch means copying both the texture and the geometry. However, we may wonder whether a theoretical link can be found between the replication of patches and the geometry. This is the purpose of the next proposition (see also [START_REF] Aujol | Exemplar-based inpainting from a variational point of view[END_REF] for a more general variational formulation), where we investigate a very simplified model of replication. More precisely, we prove that the difference between a smooth set and the concatenation of "straight" patches (i.e. intersections between balls and half-planes) can be evaluated using a criterion that involves the curvature. This is not surprising since the curvature measures the variation of the tangents to the set boundary.

Let E be an open, bounded subset of R 2 with C 3 boundary. Given x ∈ R 2 , we call straight patch of size r centered at x any set obtained as the intersection between the disk D r (x) of radius r centered at x and a half-plane. We let P denote the collection of all half-planes in R 2 . We want to quantify asymptotically (as r tends to 0) how much E differs at every point from a straight patch. A natural dissimilarity criterion is defined as

J r (E) = R 2 ( inf P ∈P (E∆P ) ∩ D r (x) p ) dx, ( 18
)
where ∆ is the symmetric difference operator, | • | the Lebesgue measure and p > 0 a parameter.

Proposition 1 There exists C p > 0 such that

J r (E) = C p r 3p+1 ∂E |κ ∂E | p dH 1 + o(r 3p+1 ), (19)
The proof of this proposition is given in Appendix A. This result quantifies the fact (which is obvious from an experimental point of view) that the more oscillating a boundary is, the more difficult it is to recover it using only "straight" patches.

6 Using the reconstructed sketch to guide the exemplar-based algorithm Recall that the main motivation for this paper is to adapt an exemplar-based algorithm in order to improve the quality of the restored geometry, and in particular to handle properly long-range geometric features, while maintaining a good ability to reproduce the texture. We saw in Section 3 how to compute a sketch of the image outside the inpainting domain and in Section 4 how to interpolate it, using either straight lines or Euler spirals. Let us now examine how the reconstructed sketch can be used for guiding the exemplar-based algorithm of the previous section. Again, we denote by A the inpainting domain and by I the image known only on Ω \ A (I = (I 1 , I 2 , I 3 ) for color images). We write I S for the interpolated sketch, known on the whole image domain Ω. In the case of color images, I S denotes the interpolation of the gray level sketch obtained from the luminance channel in a YUV representation of the original image. As already mentioned (see also [START_REF] Caselles | Geometry and color in natural images[END_REF]), the luminance channel essentially contains all the geometric information of almost every non synthetic image therefore using color sketches is unnecessary.

Based on the interpolated sketch I S , the core algorithm of our approach is given in Table 4.

Given a point x on ∂A, the algorithm searches y ∈ A c such that, simultaneously,

• the patches Γ q (x) and Γ q (y) are similar in the completion of the sketch luminance channel; • the rings B p,q (x) and B p,q (y) are similar in the original image I.

Geometrically guided exemplar-based algorithm 1. Let Γp(x 0 ) be a patch from Fq such that the intersection between Bp,q(x 0 ) and A c has maximal area (a selection criterion such as the one proposed in [START_REF] Criminisi | Object removal by exemplar-based inpainting[END_REF] could also be used); 2. Let y 0 be defined as

y 0 = argmin y∈Eq n λ " X y i ∈Γq (y) ˛IS V (y i ) -I S V (x 0 + y i -y) ˛2" + (1 -λ) " X k=1,2,3 X y i ∈Bp,q (y) x 0 +y i -y∈A c ˛Ik (y i ) -I k (x 0 + y i -y) ˛2"o ; (20)
3. For each x ∈ Γp(x 0 ) ∩ A, let I k (x) = I k (y 0 + xx 0 ), k = 1, 2, 3; 4. Replace Fp with Fp \ Γp(x 0 ) and go to 1 if A = ∅.

Table 4 Geometry/texture inpainting algorithm proposed in this paper.

The parameter λ weights the respective contributions of the sketch and the original image. Taking λ = 0.5 was a reasonable choice for all the experiments presented below which explains why we will not discuss the correct tuning of this parameter. We nevertheless believe that understanding correctly how λ must be chosen according to the very nature of the image is an interesting challenge.

Experimental results

We display in several examples of image reconstruction where we compare the approach proposed in this paper with the original "patchwork" algorithm from [START_REF] Pérez | PatchWorks: Examplebased region tiling for image editing[END_REF]. In Figures 7 and8, we display examples where the use of a geometrical guide (obtained using straight lines) improves the reconstruction of the geometry. In Figure 8 (e)-(g), we also display a case of failure in presence of a T-junction. Indeed, T-junctions as well as corners are not accounted for in both sketch reconstruction algorithms presented in Section 4. Figure 9 illustrates that, in some situations, the geometric guiding may yields a result not better than with the only "patchwork" algorithm. Remark that, for this rectilinear example, it is preferable to use straight lines rather than Euler spirals for the geometric inpainting. In Figure 10, we present a toy example made of a textured disk, which illustrates the possibility to correctly reconstruct such a curvy geometry while reproducing well the texture part of the image. In Figures 11 and12, we show two examples where the use of a geometrical guide that has been interpolated by means of Euler spirals enables correct inpainting results in difficult cases. For the experiment shown in Figure 13(e), a larger dictionary of patches has been used in Formula (20) by simply considering several rotations of each patch. This larger dictionary permits to closely follow the reconstructed curves of the sketch even though none of the patches from the original image has the correct orientation. It is interesting to note that using geometrically-guided rotated patches yields significantly better results than using rotated patches without guide since, as already mentioned, a richer dictionary of patches without additional constraint often leads erratic results. Lastly, we display in Figure 14 an example of a successful completion of an electron microscope image illustrating the ability of our method to restore properly both the texture and the geometry.

Conclusion

We have presented a new method for the joint restoration of texture and geometry. In many situations, our method has the ability to restore properly long-range geometric features like edges and, simultaneously, to sample and paste correctly the texture information.

What are the limitations of our approach? Although it allows us to recover long-range edges, its performances are somewhat limited when the sketch to be reconstructed is intricate and contains many edges that can hardly be interpolated without ambiguity. In such situation, it appears that a manual intervention is necessary. A natural approach could be to adapt to the level lines framework the contour editing strategy proposed by Elder and Goldberg in [START_REF] Elder | Image editing in the contour domain[END_REF]. The user could simply mark the pairs of lines to be connected and the program would compute the optimal sets of Euler spirals. This would give a more flexible -but no more automaticalgorithm for inpainting.

We conclude by mentioning that several variants of our model can be proposed: a natural one consists in pasting samples in priority along the interpolated curves of the sketch, in the spirit of [START_REF] Sun | Image completion with structure propagation[END_REF] except that in our case the curves are automatically computed and not drawn by the user. A second variant consists in changing the energy in [START_REF] Chan | Non-texture inpainting by curvaturedriven diffusion (CDD)[END_REF], for instance replacing the L 2 norm by another L p norm (see [START_REF] Aujol | Exemplar-based inpainting from a variational point of view[END_REF] for a discussion based on axiomatic requirements). One can also replace the linear combination of the image and sketch energy terms in [START_REF] Chan | Non-texture inpainting by curvaturedriven diffusion (CDD)[END_REF] by a new energy and define the center of a candidate patch as a solution to:

y 0 = argmin y∈Eq max 1 Z 1 yi∈Γq(y) I S V (y i )-I S V (x 0 +y i -y) p , 1 Z 2 k=1,2,3 yi∈Bp,q(y) x0+yi-y∈A c I(y i ) -I(x 0 + y i -y) p (21)
where Z 1 and Z 2 are suitable normalizing constants depending on the dynamic ranges of I S and I, respectively, and on the respective sizes of Γ p (•) and B p,q (•).

The choice of Z 1 and Z 2 is however rather delicate and strongly depends on the type of images but there are obviously situations where this energy would be more adapted.

A Proof of Proposition 1

In this appendix, we give a proof of Proposition 1 which is stated in Section 5.2, where the corresponding notations are also introduced. Let x ∈ R 2 and denote Jr(E, x) = inf P ∈P ˛(E∆P ) ∩ Dr(x) ˛.

Step 1: Up to a translation, we may assume that x = 0 and suppose that, in a neighborhood of 0, E coincides -up to a rotationwith the set of points (x, y) such that y ≥ λ + κ ∂E (0) 2

x 2 for some λ ∈ R. If λ < -r or λ > r or if κ ∂E (0) = 0, then Jr(E, 0) = 0. By symmetry, we can now assume that κ := κ ∂E (0) > 0 and we observe that

Jr(E, 0) = inf (m,p)∈R 2 ˛"{y ≥ m + px}∆{y ≥ λ + κ 2 x 2 } " ∩ Dr(0) ˛. (22)
By symmetry arguments, we observe that for every m ∈ R, p → |({y ≥ m + px}∆{y ≥ λ + κ 2 x 2 }) ∩ Dr(0)| is minimal whenever p = 0. Therefore, the computation of Jr(E, 0) reduces to minimizing m → R Dr (0) |λm + κ 2 x 2 | dx, see Figure 15. Let A be the intersection point between the right branch of the parabola and the circle Cr(0), and B the intersection point with positive x-value between the line y = m and the circle. Clearly, if m minimizes R Dr (0) |λ-m+ κ 2 x 2 | dx, then λ ≤ m ≤ y A . Let P be the patch Dr(0) ∩ {y ≥ m}. Then:

Z x A -x A |λ -m + κ 2 x 2 | dx ≤ |E∆P | ≤ Z x B -x B |λ -m + κ 2 x 2 | dx, ( 23
) therefore inf m∈R Z x A -x A |λ -m + κ 2 x 2 | dx ≤ Jr(E, 0) ≤ inf m∈R Z x B -x B |λ -m + κ 2 x 2 | dx, (24)
Now the minimum of

R x A -x A |λ -m + κ 2 x 2 | dx is reached at m A = the median value of λ+ κ 2 x 2 on [-x A , x A ], i.e m A = λ+ κ 2 " x 2 A 4 « .
R x B -x B |λ -m + κ 2 x 2 | dx is m B = λ + κ 2 " x 2 B 4 « . Plugging into (24) yields κ 4 x 3 A ≤ Jr(E, 0) ≤ κ 4 x 3 B . (25)
Remark that 3 which is positive for r small enough, and therefore

x 2 B = r 2 -λ 2 and x 2 A = r 2 -`λ + κ 2 x 2 A ´2 thus x 2 A ≥ r 2 -λ 2 -κr
κ 4 (r 2 -λ 2 -κr 3 ) 3 2 ≤ Jr(E, 0) ≤ κ 4 (r 2 -λ 2 ) 3 2 . ( 26
)
Step 2: Assume now that E has C 3 boundary and let x ∈ ∂E ⊕Dr. For r small enough and after a suitable change of the coordinates frame, ∂E on Dr(x) can be approximated as a parabola of the form λ + κ 2 x 2 in Dr(0), where κ is the curvature of ∂E at (0, λ) ∈ ∂E in the new coordinates frame. The approximation error is a o(r 2 ) therefore

κ 4 (r 2 -λ 2 -κr 3 ) 3 2 +o(r 3 ) ≤ Jr(E, 0) ≤ κ 4 (r 2 -λ 2 ) 3 2 +o(r 3 ) (27)
Step 3: Let d E denote the signed distance function to ∂E (positive outside E, negative inside). Since d E is smooth in a band containing ∂E and |∇d E | = 1 a.e., we deduce from the coarea formula that [START_REF] Pérez | PatchWorks: Examplebased region tiling for image editing[END_REF] (using p = 6, q = 8, λ = 0.5); (d) image restored using the method introduced in this paper, detailed in Section 6 (using p = 6, q = 8, λ = 0.5, and Euler spirals sketch interpolation).

J R (E) = Z r -r Z ∂{x: d E (x)≥λ} " Jr(E, y) " p dH 1 (y) dλ. (28

Fig. 1 A

 1 Fig.1A digital image (top), its meaningful level lines (middle) and the sketch reconstructed only from these lines (bottom) . The texture has partly disappeared but the geometric structures and the dynamics remain.

0 cos(u 2 ) 0 sin(u 2

 0202 (u))du, s 0 sin(ψ(u))du . (8) This expression involves the Fresnel integrals C(x) = x du and S(x) = x ) du

Fig. 2 A

 2 Fig. 2 A binary situation (left) where the completion of level lines yields curves that mutually intersect (top right). Observing that each curve divides the inpainting domain in two components, one can derive a reasonable reconstructed image (bottom right) from suitable intersections and unions of all components.

Fig. 4

 4 Fig. 4 Left: Uranus in infrared light (courtesy STScl and NASA) with artificial occlusions. Right: after reconstruction with Euler spirals of each channel in a YUV representation.

Fig. 5 A

 5 Fig.5A geometric sketch (see section 4.3) and its reconstruction using Euler spirals.

Fig. 6

 6 Fig.6Top: original image with missing parts (holes) in white. Bottom: reconstructed image using the exemplar-based method from[START_REF] Pérez | PatchWorks: Examplebased region tiling for image editing[END_REF] (with p = 4 and q = 6).

Fig. 15

 15 Fig. 15 Approximation in Dr(0). Jr(E, 0) is the gray area

)"Fig. 7 Z ∂E ˛κ 4 ˛p Z 1 - 1 " ( 1 -Z ∂E ˛κ 4 ˛p Z 1 - 1 "p Z 1 - 1 ( 1 -λ 2 )Fig. 8 Fig. 9 AFig. 10 (Fig. 11 (Fig. 12 (Fig. 13 (Fig. 14 (

 741114111112891011121314 Fig. 7 (a) original image; (b) occluded image; (c) image restored with the exemplar-based method from [59]; (d) image restored using the method introduced in this paper, detailed in Section 6 (using p = 4, q = 6, λ = 0.5). The geometrical interpolation of the sketch (to obtain figure (d)) uses straight lines.

  1. extract all T-junctions on the inpainting domain's boundary ∂A; 2. compute the associated tangents by the Bornemann-März-Weickert method described above; 3. for each level t ∈ {N 1 , • • • , N 2 } represented on ∂A:

	(a) extract the associated T -junctions;
	(b) find a set of Euler spirals (γ t j ) j∈{0,••• ,n t } that pairwise connect the T-junctions and minimize
	n t	Z
	X j=0	j γ t	(α + β|κ| 2 )ds.