Vadim Fedorov
email: vadim.fedorov@upf.edu

Pablo Arias
email: pablo.arias@cmla.ens-cachan.fr

Gabriele Facciolo
email: facciolo@cmla.ens-cachan.fr

Coloma Ballester
email: coloma.ballester@upf.edu

Exemplar-Based Image Inpainting using an Affine Invariant Similarity Measure

Patch-based approaches are used in state-of-the-art methods for image inpainting. This paper presents a new method for exemplarbased image inpainting using transformed patches. The transformation is determined for each patch in a fully automatic way from a surrounding texture content. We build upon a recent affine invariant patch similarity measure that performs an appropriate patch comparison by automatically adapting the size and shape of the patches. As a consequence, it intrinsically extends the set of available source patches to copy information from. We incorporate this measure into a variational formulation for inpainting and present a numerical algorithm for optimizing it. We show that our method can be applied to complete a perspectively distorted texture as well as to automatically inpaint one view of a scene using other view of the same scene as a source. We present experimental results both for gray and color images, and a comparison with some exemplar-based image inpainting methods.

Introduction

Image inpainting, also known as image completion, disocclusion or object removal, refers to the recovery of occluded, missing or corrupted parts of an image in a given region so that the reconstructed image looks natural. It has become a key tool for digital photography and movie post-production where it is used, for example, to eliminate unwanted objects that may be unavoidable during filming. Automatic image inpainting is a challenging task that has received significant attention in recent years from the image processing, computer vision, and graphics communities. Remarkable progress has been achieved with the advent of exemplar-based methods, which exploit the self-similarity of natural images by assuming that the missing information can be found elsewhere outside the inpainting domain. Roughly speaking, these methods work by copying patches taken from the known part of the image and pasting them smartly in the inpainting domain. These methods can obtain impressive results but many of them rely on the assumption Fig. 1. Self-similarity under different distortions. On the left: two views of the same scene related by a projective transformation. On the right: self-similar texture underwent a severe fish-eye lens distortion. that the required information can be copied as it is, without any transformations. Therefore, applicability of such methods is limited to the scenes in which objects are in a fronto-parallel position with respect to the camera.

In the image formation process, textured objects may appear distorted by some complex transformation (see Fig. 1). This is a pervasive phenomenon in our daily life. In fact, any person can mentally fill-in occluded parts of an image, even if the missing information is available to them under a different perspective. Our brain is able to appropriately transform the available information to match the perspective of the occluded region. For instance, in Fig. 1 one can easily infer what is hidden behind the red rectangle in the graffiti scene on the left, or use the non-trivially distorted context in the right image to fill-in the hole.

In this work we address this issue by transforming known patches before pasting them in the inpainting domain. The transformation is determined for each patch in a fully automatic way. Moreover, instead of searching for an appropriate transformation in a high dimensional space, our approach allows us to determine a single transformation from the surrounding texture content. As opposed to some previous works which only consider rotations and scalings, we can handle full affinities, which in principle extends the applicability of the method to any transformation that can be locally approximated by an affinity, such as perspective distortion.

We follow the approach recently proposed in [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF], where affine covariant structure tensor fields computed a priori in each image are used to define an affine invariant similarity measure between patches. We incorporate this measure into a variational inpainting formulation. The affine covariant structure tensors determine elliptical patches at each location of the image domain. Due to the affine covariance property of the structure tensors, these patches transform appropriately when computed on an affinely transformed version of the image. Fig. 2 illustrates the patches defined by the affine covariant structure tensors of [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF], computed for a set of corresponding points in two images related by a homography. Note that even though the transformation is not an affinity, the patches still match, since a homography can be locally approximated by an affinity. The paper is organized as follows. In Section 2 we review the related work. Then in Section 3 we summarize the results of [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF] which motivates the definition of the similarity measure that we use. Section 4 is devoted to the proposed inpainting method. Section 5 covers some implementation details. In Section 6 we present experiments, asserting the validity of our theoretical approach, together with a comparison with well-known exemplar based methods. Finally, Section 7 concludes the paper.

Related work

Most inpainting methods found in the literature can be classified into two groups: geometry-and texture-oriented, depending on how they characterize the redundancy of the image. The geometry-oriented methods formulate the inpainting problem as a boundary value problem and the images are modeled as functions with some degree of smoothness expressed, for instance, in terms of the curvature of the level lines [START_REF] Masnou | Level lines based disocclusion[END_REF][START_REF] Ballester | Filling-in by joint interpolation of vector fields and gray levels[END_REF][START_REF] Masnou | Disocclusion: a variational approach using level lines[END_REF][START_REF] Cao | Geometrically guided exemplar-based inpainting[END_REF], with propagation PDE's [START_REF] Bertalmío | Image inpainting[END_REF], or as the total variation of the image [START_REF] Chan | Mathematical models for local nontexture inpaintings[END_REF]. These methods perform well in propagating smooth level lines or gradients, but fail in the presence of texture or big inpainting domains. Texture-oriented (also called exemplar-based) methods were initiated by the work of Efros and Leung [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF] on texture synthesis. In that work the idea of self-similarity is exploited for direct and non-parametric sampling of the desired texture. The self-similarity prior is one of the most influential ideas underlying the recent progress in image processing and has been effectively used for different image processing and computer vision tasks, such as denoising and other inverse problems [START_REF] Foi | Foveated self-similarity in nonlocal image filtering[END_REF][START_REF] Buades | A non local algorithm for image denoising[END_REF][START_REF] Gilboa | Nonlocal operators with applications to image processing[END_REF][START_REF] Peyré | Manifold models for signals and images[END_REF][START_REF] Pizarro | Generalised nonlocal image smoothing[END_REF]. It has also found its application to inpainting: the value of each target pixel x in the inpainting domain can be sampled from the known part of the image or even from a vast database of images [START_REF] Hays | Scene completion using millions of photographs[END_REF].

The exemplar-based approach to inpainting has been intensively studied [START_REF] Demanet | Image inpainting by correspondence maps: a deterministic approach[END_REF][START_REF] Criminisi | Region filling and object removal by exemplar-based inpainting[END_REF][START_REF] Wexler | Space-time completion of video[END_REF][START_REF] Kawai | Image inpainting considering brightness change and spatial locality of textures and its evaluation[END_REF][START_REF] Aujol | Exemplar-based inpainting from a variational point of view[END_REF][START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF]. However, many such methods are based on the assumption that the information necessary to complete the image is available elsewhere and can be copied without any modification but a translation. Some works consider a broader family of transformations. Drori et al. [START_REF] Drori | Fragment-based image completion[END_REF] used heuristic criteria to vary the scale of patches. Mansfield et al. [START_REF] Mansfield | Transforming image completion[END_REF] and Barnes et al. [START_REF] Barnes | The generalized PatchMatch correspondence algorithm[END_REF] extended the space of available patches by testing possible rotations and scales of a source patch. The search in the space of available patches is usually performed by a collaborative random search. However, this implies that for each query patch, the position of the matching patch as well as the parameters of the transformation (scale, rotation angle, tilt, etc) must be determined. The high dimensionality of the parameter space makes the search problem very computationally expensive and the excessive variability of candidates may lead to unstable results. In order to restrict the search space, the authors of [START_REF] Cao | Geometrically guided exemplar-based inpainting[END_REF] propose to combine an exemplar-based approach that includes all rotated patches, with a geometric guide computed by minimizing Euler's elastica of contrasted level lines in the inpainted region. Several authors [START_REF] Pavić | Interactive image completion with perspective correction[END_REF][START_REF] Huang | Transformation guided image completion[END_REF] have addressed this issue using some user interaction to guide the search process. For example, the user provides information about the symmetries in the image, or specifies 3D planes which are then used for rectification and the rectified planes in turn are used to look for correspondences. Recently, Huang et al. [START_REF] Huang | Image completion using planar structure guidance[END_REF] proposed a method for automatic guidance that searches for appropriately transformed source patches. It starts by detecting planes and estimating their projection parameters, which are then used to transform the patches. This allows one to handle perspective transformations, in situations when representative planes can be detected. Most of those works use a similarity measure, either explicitly or implicitly, to compute a matching cost between patches. We propose to use an affine invariant similarity measure which automatically distorts the patches being compared [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF]. Our method considers a rich patch space that includes all affine-transformed patches, furthermore, for each pair of patches the transformations are uniquely determined using the image content. This effectively limits the search space, making the method more stable. Since the patch distortions depend on the texture content of the image, our technique is related in that sense to a shape-from-texture approach [START_REF] Gårding | Shape from texture for smooth curved surfaces in perspective projection[END_REF][START_REF] Gårding | Direct computation of shape cues using scale-adapted spatial derivative operators[END_REF][START_REF] Ballester | Affine invariant texture segmentation and shape from texture by variational methods[END_REF]. In this paper we extend the variational framework described in [START_REF] Wexler | Space-time completion of video[END_REF][START_REF] Kawai | Image inpainting considering brightness change and spatial locality of textures and its evaluation[END_REF][START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF] proposing a new energy and an optimization algorithm for affine invariant exemplar-based inpainting. Let us finally note that [START_REF] Wang | Image affine inpainting[END_REF] proposed a self-similarity measure for image inpainting, comparing dense SIFT descriptors on square patches of a fixed size. However, the method is not fully affine invariant, for example, neither the dense SIFT descriptors nor the square patches are scale invariant. Several authors have addressed the affine distortion and affine invariance problem in other contexts such as image comparison [START_REF] Mikolajczyk | Scale & affine invariant interest point detectors[END_REF], object recognition [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF], and stereo [START_REF] Garding | Direct estimation of local surface shape in a fixating binocular vision system[END_REF].

An affine invariant similarity measure

Non-local self-similarity is an accepted prior for natural images. To formalize it, a patch similarity or comparison measure is needed. Let us consider the general problem of comparing patches on two images u : Ωu → R and v : Ωv → R, Ωu, Ωv ⊆ R 2 (for simplicity, we can assume the image domains to be R 2 ). A widely used comparison measure between two patches centered respectively at x and y is the weighted squared Euclidean distance

D(t, x, y) = R 2 gt(h)(u(x + h) -v(y + h)) 2 dh, (1)
where gt is a given window that we assume to be Gaussian of variance t. The Gaussian gt represents a weighted characteristic function of both patches being compared and determines the size of the patches or, in other words, the scale. In many occasions, similar patches exist in the image but have undergone a transformation, for example due to a different position with respect to the camera. The Euclidean distance is not appropriate for detecting these similarities. Consider for example a simple case in which v is a rotated version of image u. If the rotation is known, we should use the Euclidean distance between patches in u and rotated patches in v, namely

D R (t, x, y) = R 2 gt(h)(u(x + h) -v(y + Rh)) 2 dh. (2)
In a more realistic scenario, one does not know the appropriate transformation that matches both patches being compared and even whether it exists. Some previous works addressed this issue by searching among all possible transformations [START_REF] Barnes | The generalized PatchMatch correspondence algorithm[END_REF][START_REF] Mansfield | Transforming image completion[END_REF] which involves probing of all the parameters (scale, rotation angle, etc). The high dimensionality of the parameter space makes the problem very difficult. In this paper we use an affine invariant similarity measure, introduced in [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF], that automatically deduces this transformation from the local texture context. The similarity measure defined in [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF] is based on affine covariant structure tensor fields a priori computed in each image. It was derived as an approximation to a more general framework introduced in [START_REF] Ballester | Multiscale analysis of similarities between images on riemannian manifolds[END_REF], where similarity measures between images on Riemannian manifolds are studied.

In the remainder of this section we present an alternative, self-contained overview of this similarity measure. We first briefly discuss the concept of affine covariant structure tensors. Then we describe an algorithm to compute them. Finally, we show how they are used to define the affine invariant similarity measure and establish the relation between our derivation and the theory of [START_REF] Ballester | Multiscale analysis of similarities between images on riemannian manifolds[END_REF][START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF].

Affine Covariant Structure Tensors

Given a real-valued image u, we consider an image-dependent structure tensor field Tu as a function that associates a structure tensor (a symmetric, positive semi-definite 2 × 2 matrix) to each point x in the image domain. As before, for simplicity we assume the image domain to be R 2 .

The structure tensor field is said to be affine covariant if, for any affinity

A, Tu A (x) = A T Tu(Ax)A, (3)
where uA(x) := u(Ax) denotes the affinely transformed version of u.

Given a structure tensor Tu(x) we can associate with it an elliptical region of "radius" r centered at x Bu(x, r) = {y :

Tu(x)(y -x), (y -x) ≤ r 2 }. (4)
When the structure tensor is affine covariant, we have that

ABu A (x, r) = Bu(Ax, r).
This implies that the structure tensors can be used to define regions that transform appropriately via an affinity (Fig. 2). As shown in [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF], given two affine covariant structure tensors we can extract the affine transformation between the corresponding elliptical patches up to some rotation. Indeed, for any affine transformation A, there exists an orthogonal matrix R such that

A = Tu(Ax) -1 2 RTu A (x) 1 2 . ( 5
)
This last equation provides an intuitive geometric relationship between the structure tensors, the associated elliptical regions and the affinity. Consider a point x and the corresponding affine covariant elliptic neighborhood Bu A (x). Mapping Bu A (x) by the affinity yields Bu(Ax). The application of A can be decomposed in three steps. First, applying Tu A (x)

1 2 , we transform Bu A (x) into a circle or radius r. We refer to the resulting patch as a normalized patch. Then, a rotation is applied to the normalized patch. Finally, Tu(Ax) -1 2 maps the rotated normalized patch to the elliptical neighborhood Bu(Ax).

To fully determine the affinity A, one needs to find the rotation R. Any rotation would yield an affinity that maps the elliptical neighborhood associated with Tu A at x to the one associated with Tu at Ax. For a wrong value of the rotation, the image content inside both neighborhoods will not match. Therefore, the right value for the rotation can be computed by aligning the image content of both patches. For this aim, we decompose the rotation as

R = Ru(Ax)R -1 u A (x), (6)
where Ru(Ax) and Ru A (x) are estimated from the image content in the patches. In practice, we calculate them by aligning the dominant orientation of the normalized patches to the horizontal axis. To compute the dominant orientation we use histograms of gradient orientations as in the SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF].

Computation of Affine Covariant Structure Tensors

The following iterative algorithm introduced in [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF] allows us to compute a dense field of affine covariant structure tensors and the associated Fig. 3. An affine invariant patch comparison which is achieved by normalizing the patches to discs and aligning them with suitable rotations.

neighborhoods on an image u:

T (k) u (x) = B (k-1) u (x,r) Du(y) ⊗ Du(y) dy Area(B (k-1) u (x, r)) , ( 7
)
where u is the given image and B

(k) u

is the elliptical patch related to T (k) u , defined by

B (k) u (x, r) = {y : T (k) u (x)(y -x), (y -x) ≤ r 2 } (8)
for k ≥ 1, and

B (0) u (x, r) = {y : |Du(x)(y -x)| ≤ r} (9)
for k = 0. Throughout this paper we follow the notation of [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF] and denote by Tu(x) the affine covariant structure tensor T (k) u (x) for a fixed value of k (k = 30 in all the experiments) and a given value of r (r > 0 is a free parameter which is in range [250,350] in our experiments). We denote by Bu(x) the affine covariant neighborhood B (k) u (x, r). Notice that the structure tensor ( 7) is guaranteed to be affine covariant at any iteration of the scheme, therefore, the purpose of it is not to enforce affine covariance property, but rather to diminish dependency on the very first iteration.

An Affine invariant Patch Similarity

Previously in this section we were considering two images u and uA, related by a global affinity. For the patch comparison problem we can generalize our reasoning and consider two arbitrary images u and v. Let x and y be two given points in images u and v respectively. The structure tensors Tu(x) and Tv(y) define elliptical patches BT u (x) and BT v (y) around these points. In order to compare the patches, equations ( 5) and [START_REF] Barnes | Patch-Match: a randomized correspondence algorithm for structural image editing[END_REF] suggest the following mapping between the elliptical patches:

P (x, y) = Tv(y) -1 2 Rv(y)R -1 u (x)Tu(x) 1 2 . ( 10
)
We can interpret P (x, y) as an affinity, mapping the elliptical patch associated with Tu(x) into the one associated with Tv(y). If u in the vicinity of x is an affinely transformed version of v in the vicinity of y, then P (x, y) recovers the true affinity. An affine invariant patch similarity measure could be built by computing the distance between the elliptical patch at y and the elliptical patch at x transformed by P (x, y). In practice, it is more convenient to transform both elliptical patches to the circle of radius r (Fig. 3) and compare the aligned normalized patches:

D a (t, x, y) = ∆ t gt(h) u(x + T -1 2 u Ru(x)h) -v(y + T -1 2 v Rv(y)h) 2 dh, ( 11
)
where ∆t is a disc centered at the origin with radius proportional to the scale t > 0 and big enough to contain the effective support of the weighting function gt. The distance D a provides an affine invariant distance between the patches pu(x) and pv(y). Here the patch pu(x) := pu(x, •) is defined by pu(x, h) := u(x + Tu(x) -1 2 h), with h belonging to ∆t. We will apply it in Section 4 to exemplar-based inpainting. Let us also remark that formula [START_REF] Chan | Mathematical models for local nontexture inpaintings[END_REF] has the same complexity as the patch comparison formula [START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF]. The similarity measure corresponding to [START_REF] Chan | Mathematical models for local nontexture inpaintings[END_REF] was derived in [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF] as a computationally tractable approximation of the linear case of the multiscale similarity measures introduced in [START_REF] Ballester | Multiscale analysis of similarities between images on riemannian manifolds[END_REF]. There, the authors show that all scale spaces of similarity measures D(t, x, y) satisfying a set of appropriate axioms are solutions of a family of degenerate elliptic partial differential equations (PDE) in the variables (x, y). Images are considered in those papers as Riemannian manifolds endowed with a metric defined by a tensor field. If this tensor field is affine covariant, the resulting similarity measure is affine invariant. In this Riemannian framework P (•, •) defines an isometry between the tangent spaces in two manifolds. The authors refer to it as the a priori connection, since it is related to the notion of connection appearing in parallel transport (see [START_REF] Ballester | Multiscale analysis of similarities between images on riemannian manifolds[END_REF] for details). WKB approximation method, named after Wentzel, Kramers and Brillouin, was used in [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF] to find the approximate solution to a linear partial differential equation with spatially varying coefficients as a convolution with a short-time space-varying kernel. The affine invariant patch distance [START_REF] Chan | Mathematical models for local nontexture inpaintings[END_REF] is used in the following section in a variational formulation for exemplar-based image inpainting and Section 6 will present inpainting results for both gray and color images. Let us note that for the color case we consider a generalization of (11) to multi-channel images. Let -→ u : Ωu → R M and -→ v : Ωv → R M , Ωu, Ωv ⊆ R 2 be multi-channel images (e.g., M = 3 for color images), then the corresponding affine invariant similarity measure is defined as

D a,M (t, x, y) = ∆ t gt(h) -→ u (x + T -1 2 u Ru(x)h) --→ v (y + T -1 2 v Rv(y)h) 2 2 dh, ( 12
)
where • 2 denotes the Euclidean norm of vectors in R M and the affine covariant structure tensors and neighborhoods are computed using the corresponding gray-value images associated to -→ u and -→ v by the iterative algorithm of Section 3.2.

Inpainting formulation

Exemplar-based inpainting methods aim at filling-in the image so that each patch in the inpainting domain is similar to some known patch. This requires comparing known patches with partially or completely unknown patches. For this we extend the variational framework described in [START_REF] Wexler | Space-time completion of video[END_REF][START_REF] Kawai | Image inpainting considering brightness change and spatial locality of textures and its evaluation[END_REF][START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF] by using the affine invariant similarity measure D a given in [START_REF] Chan | Mathematical models for local nontexture inpaintings[END_REF]. We formulate the problem of inpainting from affinely transformed patches via the minimization of the following energy functional

E(u, ϕ) = O D a (t, x, ϕ(x)) dx, ( 13
)
where O ⊂ Ω ⊂ R 2 is the inpainting domain, û : Ω \ O → R is the known part of the image, O includes all the centers of patches intersecting O and O c is its complement, that is, O c contains centers of fully known patches (see Fig. 4). The minimization of ( 13) aims at finding a visually plausible completion u of û in the unknown region O. The additional variable ϕ : O → O c determines for each unknown target patch the location of a source patch from which the information will be copied. This energy compares patches defined on elliptical regions centered at x and ϕ(x). In the known part of the image, these regions are defined by the affine covariant structure tensors T û. Since the image is unknown inside the inpainting domain we have to estimate the structure tensors together with the image. The relationship between u and Tu introduces a complex dependency in the energy [START_REF] Demanet | Image inpainting by correspondence maps: a deterministic approach[END_REF], which complicates its minimization. Therefore, we propose to relax it and consider instead the minimization of the energy

E(u, ϕ, G) = O ∆ t gt(h) u(x + G(x) -1 2 h) -û(ϕ(x) + T û(ϕ(x)) -1 2 R û(ϕ(x))h) 2 dhdx (14)
where G(x) is an invertible 2 × 2 matrix, ∀x ∈ O. For now, we will not restrict the tensor field G to be given by the structure tensors Tu. Instead, we consider it as an additional variable, in principle independent of u. In this way, we do not have to deal with the complex dependency between Tu and u. In practice, due to the properties of the affine covariant structure tensors, it turns out that the G(x) can be estimated from Tu(x) and the additional rotation Ru(x) , as will be explained later in this section. We compute a local minimum of the energy with an alternating optimization scheme on the variables u, G and ϕ which is summarized in Algorithm 1.

Image Update Step

In the image update step, ϕ and G are fixed, and the energy is minimized with respect to u. With the change of variables z = x + G(x) -1 2 h, the Euler-Lagrange equation leads to the following expression:

u(z) = 1 (z) O gt G(x) 1 2 (z -x) û ϕ(x) + T û(ϕ(x)) -1 2 R û(ϕ(x))G(x) 1 2 (z -x) G(x) 1 2 dx, (15)
where (z) is normalization factor such that the sum is an average. The field G determines elliptical patches centered at each x ∈ O. For each one of these patches a matching patch centered at ϕ(x) is known, as well as its shape which is given by the structure tensor T û(ϕ(x)). The corresponding patch is then warped via the affinity

P (ϕ(x), x) = G(x) -1 2 R -1 û (ϕ(x))T û(ϕ(x)) 1 2
and aggregated in the inpainting domain. Note that if G(x) is given by Tu(x), then P (ϕ(x), x) coincides with Equation (10).

Affine Correspondence Update Step

Given a fixed u, the minimization of the energy with respect to (ϕ, G) can be performed as independent minimization of the patch distance function D a for each x ∈ O. This problem is very complex to solve since it is a nearest neighbor search where we also optimize for the affine transformation of the patch at x, given by G.

We will exploit the properties of the affine covariant structure tensors to obtain an approximate solution. For that, let us consider a completion candidate u and assume that a local vicinity of x on u is an affinely transformed version of a local vicinity of ϕ(x) on û. That is, u(x + h) = û(ϕ(x) + Ah), which is the case when x and ϕ(x) do actually correspond. Setting G(x) such that G -1 2 (x)R -1 û (ϕ(x))T û(ϕ(x))

1 2 = A will lead to a correct mapping and thus to the zero patch distance. On the other hand, using [START_REF] Cao | Geometrically guided exemplar-based inpainting[END_REF] we can find this affinity as A = Tu(x) -1 2 RT û(ϕ(x))

1 2 where R is some orthogonal 2×2 matrix and Tu is calculated on u.

Then G(x) such that G 1 2 (x) = R(x)T 1 2
u (x), together with ϕ(x), will be global minimizers of the patch distance function D a at x. Therefore, we need to search only for ϕ(x) and R(x). An approximate ϕ(x) can be found efficiently using our modified version of the PatchMatch algorithm [START_REF] Barnes | Patch-Match: a randomized correspondence algorithm for structural image editing[END_REF], detailed in Section 5. The additional rotation R(x) is determined as described in Section 3.1, in the same way as for the known part of an image. Notice that for notation consistency we should write R(x) := Ru(x) -1 . Of course, if the neighborhood of x does not match any affinely transformed patch, then the estimated G might not minimize the patch distance D a .

Algorithm 1: Approximate minimization of E(u, ϕ, G).

Input: Initial condition u 0 at O, tolerance τ > 0 Output: Image completion u repeat
Compute affine covariant structure tensors T u k-1 (x) and rotations R u k-1 (x) for all x ∈ O; Estimate optimal correspondences ϕ k using the modified PatchMatch (see Section 5.2); Update image

u k = arg min u E(u, ϕ k , G k ), subject to u k = û in O c ; until u k -u k-1 < τ ;
Another interpretation of the approximate minimization can be given by adding to the minimization of E(u, ϕ, G) the constraint that G

1 2 (x) = Ru(x) -1 T 1 2
u (x) for all x ∈ O and for some rotation matrix Ru(x), namely,

min E(u, ϕ, G) subject to G 1 2 = R -1 u T 1 2
u .

The correspondence update step corresponds to the constrained minimization of the energy with respect to ϕ, G for a fixed image u. In the image update step the energy is minimized with respect to u, but without enforcing the constraint. Therefore, our approximate minimization can be seen as an alternating minimization applied to a constrained problem. The constraint is enforced only when minimizing with one of the variables (the pair ϕ, G). There are no theoretical guarantees for the convergence of such a scheme, although we have not yet encountered a practical case where the algorithm failed to converge.

5 Numerical Implementation

Image Update Step

The actual implementation of ( 15), that we use in our method, is [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF] where

u(z) = 1 C(z) x∈ O gt(T 1 2 u (x)(z -x)) mc(x)w(x, z) û ϕ(x) + P (x, ϕ(x))(z -x) |T 1 2 u (x)|,
P (x, ϕ(x)) = T -1 2 û (ϕ(x))R û(ϕ(x))R -1 u (x)T 1 2
u (x) is the estimated affinity mapping the target patch at x onto the source patch at ϕ(x). The structure tensor field Tu is computed using the inpainted image u from the previous iteration. Of course, in the discrete setting some kind of interpolation needs to be done after transforming one elliptical patch into another by P (x, ϕ(x)). For that we use the Nadaraya-Watson estimator [START_REF] Nadaraya | On estimating regression[END_REF][START_REF] Watson | Smooth regression analysis[END_REF] with Gaussian kernel. The extra term mc in ( 16) is a so-called confidence mask that takes values from 1 to 0, exponentially decreasing with the distance to the set of known pixels O c . This mask is usual in exemplar-based inpainting, for instance, it is used in [START_REF] Criminisi | Region filling and object removal by exemplar-based inpainting[END_REF][START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF]. It helps to guide the flow of information from the boundary towards the interior of the inpainting domain, eliminating some local minima and reducing the effect of the initial condition. More precisely, we compute the confidence mask as

mc(x) = (1 -c0)exp - d(x, O c ) ct + c0,
where d(x, O c ) is the distance from a point x to the boundary of the O c set, such that d(x, O c ) = 0 when x ∈ O c . Parameter c0 > 0 defines the smallest (asymptotic) value that mc can take and ct > 0 controls the rate of decay. This confidence mask never changes during the inpainting process and can be precomputed for a given inpainting domain.

There is also another additional weighting term w(x, z) in [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF]. In principle, all patches containing a pixel z contribute to its color value. To control the amount of contributors, we introduce the auxiliary Gaussian weight, that depends on the patch distance between a contributing patch and its corresponding known patch

w(x, z) = exp - D a (t, x, ϕ(x)) -min(D(z)) 2 2σ 2 cut-off (z) , (17)
where D(z) = {D a (t, y, ϕ(y)) : z ∈ BT u (y)} is a set of patch distances to known patches, computed among all patches contributing to z, and σ cut-off (z) defines a soft threshold for the patch distance values. This To compute σ cut-off (z) we begin by computing the first estimate for the cut-off distance

D a 1 (z) = γ cut-off max(D(z)) -min(D(z)) ,
where γ cut-off ∈ (0, 1) is a parameter of the method. Since distance values are usually distributed unevenly, the initial distance threshold D a 1 might discard too few or too many contributors. Therefore, we very roughly estimate the density of values that fall below D a 1 and refine the initial cut-off distance by

D a 2 (z) = γ cut-off D a 1 |D(z)| N1 ,
where |D(z)| stands for the total number of elements in the set D(z) and N1 = |{D a ∈ D(z) : D a -min(D(z)) < D a 1 (z)}| is the number of distance values retained by D a 1 . Then the final cut-off threshold is given by

σ cut-off (z) = 1 6 D a 1 (z) + D a 2 (z) .
The factor 1 6 in the formula above implies that the Gaussian (17) approaches zero at the average cut-off distance between the first and second estimates. Fig. 5 illustrates the cut-off distances for two different cases of distance values distribution. The energy ( 13) is non-convex and might have several local minima. As a consequence, there is a dependency on the initialization. To alleviate this dependency, we try to promote the propagation of information from the boundary towards the interior of the inpainting domain during the very first iterations of inpainting. Recall that the extended domain O contains the centers of all elliptical patches overlapping the inpainting domain. We enlarge O by a few pixels to capture a narrow stripe O + = ( O ⊕ B) \ O around the inpainting domain, that contains centers of completely known elliptical patches. Obviously, these elliptical patches in O + do not intersect the inpainting domain. To make them contribute to the inpainting we should enlarge them first. For that we recompute them doubling the value of r. Notice that we use r = 2r only for the points within the stripe O + and only in the image update step. We do not recompute the corresponding structure tensors, thus we only increase the sizes of these elliptical patches and do not modify their shapes. This additional contribution from elliptical patches, that do not depend by any means on the inpainting domain, boosts the information propagation at the boundaries of the inpainting domain. The width of the stripe O + is set to 6 pixels in all our experiments.

Affine Correspondence Update Step

During the update of the correspondence map we compute an approximation of the nearest neighbor field using PatchMatch [START_REF] Barnes | Patch-Match: a randomized correspondence algorithm for structural image editing[END_REF][START_REF] Barnes | The generalized PatchMatch correspondence algorithm[END_REF] Match algorithm speeds up the computation of optimal correspondences by exploiting the correlation between patches so that they can be found collectively. Since we are working with elliptical patches which might be arbitrarily rotated, we adapt the PatchMatch propagation scheme to take this into account. Let x be the current pixel and d1 = (±1, 0), d2 = (0, ±1) be the directions of propagation. Then, the adjacent pixels yi = x-di (i = 1, 2) are tested during the propagation. Assume i = 1 (see Fig. 6). Pixel ŷ = ϕ(y) is the current nearest neighbor candidate for y.

The standard PatchMatch would try to propagate position ŷ + d to pixel x (Fig. 6a). In contrast, we calculate the direction d = P (y, ŷ)d, where P is the a priori connection, and we try a few positions along that direction (Fig. 6b). This generalization gives a more meaningful propagation along edges.

Recall that to compare two elliptical patches we first transform them into discs of the same radius (see Section 3.3). As a result of this normalization we obtain two sets of scattered point, each of which is described by realvalued coordinates and a color value. To be able to compare these sets, we use the Nadaraya-Watson estimator [START_REF] Nadaraya | On estimating regression[END_REF][START_REF] Watson | Smooth regression analysis[END_REF] with Gaussian kernel to interpolate them to a regular grid. At early of our algorithm, the inpainted image may be blurry. This is typical for iterative patch-based inpainting methods and is caused by aggregating patches that do not coincide in their overlap area at the initial iterations. As discussed in [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF], the structure tensors are sensitive to blur, tending to larger elliptical patches in blurry regions. Essentially, smoothing of an image suppresses small details and produces the same effect as scaling the image down. The elliptical patches in turn capture larger areas. To compensate for this, we allow the parameter r to vary during the correspondence map estimation. That is, while T û(ϕ(x)) is always computed with the fixed r, say r0 (a given parameter of the method), in the computation of Tu(x) we consider a few (around five) values of r smaller than r0 and select the one giving the smallest patch distance D a between points x and ϕ(x). Let us note, that to be able to compare patches, computed with different values of r, we scale the normalized patches to discs of radius one.

Experimental results

In this section we present results obtained by the proposed method. For all the experiments in this section, we compare our results with the ones obtained by the multiscale NL-Means method [START_REF] Wexler | Space-time completion of video[END_REF][START_REF] Kawai | Image inpainting considering brightness change and spatial locality of textures and its evaluation[END_REF] which we find to be a representative exemplar-based image inpainting method operating only with translations of patches. Whenever possible, we also compare against the method of [START_REF] Mansfield | Transforming image completion[END_REF] with a single scale and considering rotations, and the method of [START_REF] Huang | Image completion using planar structure guidance[END_REF]. In both cases we use implementations provided by the authors.

As a sanity check we first test the proposed method on a synthetic example, displayed in Fig. 7. We take a textured image and create an affinely transformed version of it. We select a part of the transformed image as the inpainting domain. Instead of using the rest of the transformed image to copy information from, we make the original (not transformed) image to be the source. Let us remark that the ground truth affinity is not provided to the algorithm, hence, we test the ability of the proposed method to identify and copy affinely transformed patches. We do not show any results for [START_REF] Mansfield | Transforming image completion[END_REF] and [START_REF] Huang | Image completion using planar structure guidance[END_REF] for this experiment, since the available implementations do not support the use of a separate image as a source. A more realistic case would be associated with a more general transformation. Since for planar objects a projective transformation can be locally approximated by an affinity, in the second example (shown in Fig. 8) we test the robustness of our method in the reconstruction of an image distorted by perspective. As usual in inpainting applications, in this experiment we use the known part of the image as source. We compare our method with the NL-Means method, that works only with , the result of [START_REF] Huang | Image completion using planar structure guidance[END_REF], and the result of our method. Third row: evolution of the inpainting domain over iterations of our method (every third iteration).

translations, and additionally with the method of [START_REF] Mansfield | Transforming image completion[END_REF] in the mode when the rotations are also considered, and the method of [START_REF] Huang | Image completion using planar structure guidance[END_REF]. Note that the Fig. 9. First row: image with the inpainting domain shown in red. Second row: closeups around the inpainting area of the NL-Means result, the result of [START_REF] Mansfield | Transforming image completion[END_REF] (considering rotations), the result of [START_REF] Huang | Image completion using planar structure guidance[END_REF], and the result of our method. Third row: evolution of the inpainting domain over iterations of our method (every third iteration). latter method successfully determines a single plane in the image and, as expected, achieves a good reconstruction.

The third example (Fig. 9) demonstrates the reconstruction of a texture with some lens distortion applied to it. The known part of the image is used as a source and, like in all other experiments, just a rotation of source patches is not sufficient to obtain a good result. As in the previous case, here we compare our method with the NL-Means method (translations), the method of [START_REF] Mansfield | Transforming image completion[END_REF] (translations and rotations), and the method of [START_REF] Huang | Image completion using planar structure guidance[END_REF] (projective transformation). A final experiment, which is also potentially interesting for real applications, consists in inpainting one view of a scene using information from another view of the same scene. Fig. 10 shows the results of this experiment where we have applied the proposed method to two views related by an unknown homography. As before, we compare our result with the result of the NL-Means method.

Let us note that the method of [START_REF] Mansfield | Transforming image completion[END_REF] also supports rotations plus scalings. However, we could not obtain meaningful results on these examples for this mode. It seems that the additional variability added by the scalings makes it easier for the algorithm to be trapped in a bad local minimum. For example, a constant region can be produced by scaling a small uniform patch. Finally, we briefly discuss the limitations of the proposed method. Since the transformation between two patches is estimated from the surrounding texture, the method fails when there is not enough textural information (Fig. 11, first row). Severe transformations between pairs of patches may be recovered incorrectly. This can be illustrated by replacing the source image in the last experiment with a much more slanted view (Fig. 11, second row). The proposed method does not exploit the common multiscale scheme which limits the maximum possible size of the inpainting domain (Fig. 11, third row).

Conclusions

In this work we propose a new variational formulation for exemplarbased image inpainting that, for the first time, considers local full affine transformations with a tractable approximate optimization scheme. This is possible thanks to the use of an affine invariant patch similarity measure constructed from affine covariant structure tensors, both introduced in [START_REF] Fedorov | Linear multiscale analysis of similarities between images on riemannian manifolds: Practical formula and affine covariant metrics[END_REF]. These structure tensors provide an efficient way to determine a unique affinity putting in correspondence any pair of patches. If the patches being compared are related by an affinity, then this affinity is recovered. We show that our method can be applied to complete a perspectively distorted color texture as well as to automatically inpaint one view of a scene using other view of the same scene as a source. The problem of exemplar-based inpainting is a complex non-convex problem with many local minima. As pointed out in [START_REF] Cao | Geometrically guided exemplar-based inpainting[END_REF], adding transformations of patches makes it even more complex. Intuitively, the added variability makes it harder to distinguish "good" minima from other minima (a single pixel can be scaled to match a constant patch). The structure tensors are beneficial in this respect, because they constrain the number of ways in which a source patch can be transformed to match a target patch, thus eliminating some of the variability. This also allows us to design faster and more accurate minimization algorithms without the need to search the parameter space of the transformation family.

The proposed method works at a single scale. To better handle larger inpainting domains it would be desirable to develop a multiscale scheme, as is customary in the literature [START_REF] Wexler | Space-time completion of video[END_REF][START_REF] Kawai | Image inpainting considering brightness change and spatial locality of textures and its evaluation[END_REF][START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF]. However, extending the multiscale approach to the problem of inpainting using affinely transformed patches is not trivial, since the filtering with an isotropic Gaussian breaks the affine invariance. Adapting multiscale inpainting approaches to this context is an interesting direction for future research.

Fig. 2 .

 2 Fig. 2. Affine covariant neighborhoods (patches) computed at corresponding points in two images taken from different viewpoints. Despite the change in appearance, patches capture the same visual information.

Fig. 4 .

 4 Fig. 4. Schematic representation of the sets O, O c , O and O c .

Fig. 5 .

 5 Fig. 5. Schematic depiction of two different cases of patch distance distribution. Gray filled-in curves represent histograms of distance values computed between patches overlapping z ∈ O and their most similar known counterparts from O c . Weighting functions are shown in red. In both cases γ cut-off ≈ 0.45.

Fig. 6 .

 6 Fig. 6. Propagation directions in PatchMatch: (a) original scheme, (b) modified scheme.

Fig. 7 .

 7 Fig. 7. First row: source image, target image with the inpainting domain shown in red, and close-ups around the inpainting area of the NL-Means result and the result of our method. Second row: evolution of the inpainting domain over iterations of our method (every second iteration).

Fig. 8 .

 8 Fig. 8. First row: image with the inpainting domain shown in red. Second row: closeups around the inpainting area of the NL-Means result, the result of[START_REF] Mansfield | Transforming image completion[END_REF] (considering rotations), the result of[START_REF] Huang | Image completion using planar structure guidance[END_REF], and the result of our method. Third row: evolution of the inpainting domain over iterations of our method (every third iteration).

Fig. 10 .

 10 Fig. 10. First row: source image, target image with the inpainting domain shown in red, and close-ups around the inpainting area of the NL-Means result and the result of our method. Second row: evolution of the inpainting domain over iterations of our method (every second iteration).

Fig. 11 .

 11 Fig. 11. Failure cases. From top to bottom: insufficient textural information, severe distortion, too big inpainting domain. More details are given in the text.

Acknowledgments. The first, second and fourth authors acknowledge partial support by the MINECO/FEDER project with reference TIN2015-70410-C2-1-R , the MICINN project with reference MTM2012-30772, and by GRC reference 2014 SGR 1301, Generalitat de Catalunya. The second and third authors were partly founded by the Centre National dEtudes Spatiales (CNES, MISS Project), BPIFrance and Région Ile de France, in the framework of the FUI 18 Plein Phare project, the European Research Council (advanced grant Twelve Labours n246961), the Office of Naval research (ONR grant N00014-14-1-0023), and ANR-DGA project ANR-12-ASTR-0035.