Anis Theljani
email: thaljanianis@gmail.com

Zakaria Belhachmi
email: zakaria.belhachmi@uha.fr

Moez Kallel
email: moez.kallel@ipeit.rnu.tn

Maher Moakher
email: maher.moakher@enit.rnu.tn

MULTISCALE FOURTH-ORDER MODEL FOR IMAGE INPAINTING AND LOW-DIMENSIONAL SETS RECOVERY

Keywords: 2010 Mathematics Subject Classification. 65M32, 65M50, 65M22, 94A08, 65N22, 35G15, 35Q68 Image inpainting, Inverse problems, Regularization procedures, Mixed finite elements

whether they are published or not. The documents may come

1. Introduction. The digital image inpainting started with the works of engineers and computer scientists in the mid-nineties of last century and it refers to the restoration of a scratched or damaged image. In the image processing, this task is very important and has many applications in various fields (painted canvas and movies restoration, augmented reality, . . . ). Let Ω ⊂ R 2 denotes the entire image domain and let D ⊂ Ω be a damaged part of Ω. The basic idea in the image inpainting is to fill-in D, in such a manner that a viewer can not detect the restored part from the rest of the image. Different techniques have been applied to solve such a problem, e.g. some heuristic "copy-paste" procedures [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF], statistical approaches [START_REF] Armstrong | Nonlinear interpolation of missing data using min-max functions[END_REF][START_REF] Geman | Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images[END_REF], we refer to the review article [START_REF] Bertalmio | Inpainting, Encyclopedia of Computer Vision[END_REF] and the references therein for an exhaustive overview on this problem. Among the various methods, the Partial Differential Equations (PDEs) are now widely used and are proven to be efficient in this fields [START_REF] Belhachmi | Weighted harmonic and complex Ginzburg-Landau equations for gray value image inpainting[END_REF][START_REF] Bertalmio | Navier-Stokes, fluid dynamics, and image and video inpainting[END_REF][START_REF] Bertalmio | Image inpainting[END_REF][START_REF] Bertozzi | Unconditionally stable schemes for higher order inpainting[END_REF][START_REF] Chan | Mathematical models for local non-texture inpainting[END_REF][START_REF] Esedoglu | Digital image inpainting by Mumford-Shah-Euler model[END_REF][START_REF] Kallel | The Cauchy problem for a nonlinear elliptic equation: Nash-game approach and application to image inpainting[END_REF][START_REF] Masnou | Disocclusion a variational approach using level lines[END_REF][START_REF] Masnou | Level-lines based disocculusion[END_REF]. The underlying idea in the PDE-based methods is to interpolate with a differential operator the data given outside of D. A large number of differential operator have been considered, in particular, several second-order diffusion equations have been proposed in the literature [START_REF] Bertozzi | Unconditionally stable schemes for higher order inpainting[END_REF][START_REF] Chan | Mathematical models for local non-texture inpainting[END_REF][START_REF] Esedoglu | Digital image inpainting by Mumford-Shah-Euler model[END_REF]. Such operators have the advantage of being well-established theoretically and to lead to various simple numerical methods. However, they may suffer from major drawbacks such as the disconnection of level lines over large distances (violating the connectivity principle), the smooth propagation of the edges into the damaged domain (blurring effect), or the failure in reproducing some high-order features (curvatures, . . . ). Note also that these methods do not work when the damaged region D touches the boundary of Ω. In such a situation, the authors in [START_REF] Kallel | The Cauchy problem for a nonlinear elliptic equation: Nash-game approach and application to image inpainting[END_REF] proposed an inpainting method based on the data completion with a nonlinear Cauchy problem.

The shortcomings of the second-order partial differential equations gave rise to a class of high-order diffusion models which in general perform better, particularly for restoring the curvatures and for matching edges across large distances. In fact, the supplementary information on the level lines directions which may be provided from the use of boundary conditions both on the solution and its gradient enhance the quality of the reconstruction. In addition, in the homogeneous areas of Ω the high-order of the operator damps the noise faster than any second order one.

Overview on higher-order PDE models. Bertalmio et al. [START_REF] Bertalmio | Image inpainting[END_REF] pioneered a two dimensional fourth-order PDE which consists in propagating both the gradient direction (geometry) and the gray-scale values of the image inside the region to be filled-in by solving the following equation:

(1)

∂ t u -∇ ⊥ • ∇∆u = 0, in D, u = f, on ∂D,
where ∇ ⊥ denotes the perpendicular gradient (-∂ y , ∂ x ) and f is the initial damaged image. This model was the subject of other improvements in [START_REF] Bertalmio | Navier-Stokes, fluid dynamics, and image and video inpainting[END_REF] based on the Navier-Stokes equations. IOther authots [START_REF] Masnou | Level-lines based disocculusion[END_REF][START_REF] Nitzberg | Filtering, segmentation and depth[END_REF][START_REF] Shen | Euler's elastica and curvature-based inpainting[END_REF] considered the Euler's elastica functional to minimize the following energy:

(

2) ∥u -f ∥ L 2 (Ω) + ∫ K (a + bκ 2 ) dH 1 (x),
where H 1 denotes the Hausdorff measure, K is a closed regular subset of Ω and

κ = ∇ • (∇u/|∇u|) is the curvature of the level sets γ r := {x ∈ K | u(x) = r}
and a, b being two positive constants. In this high-order variational model, the regularization term (Euler's elastica) combines the total variation, sensitive to the length of the isolines, and the square of the curvature, which favors curved lines rather than the straight ones. Minimizing (2) leads to a highly nonlinear PDE and therefore its numerical solution is usually a non trivial task. It was the subject of many numerical investigations [START_REF] Ambrosio | A direct variational approach to a problem arising in image reconstruction[END_REF][START_REF] Chung | A fast algorithm for Euler's elastica model using augmented Lagrangian method[END_REF][START_REF] Esedoglu | Digital image inpainting by Mumford-Shah-Euler model[END_REF][START_REF] Masnou | Filtrage et désocclusion d'images par méthodes d'ensembles de niveau[END_REF]. In the same spirit, Esedoglu and Shen proposed in [START_REF] Esedoglu | Digital image inpainting by Mumford-Shah-Euler model[END_REF] the Mumford-Shah-Euler image inpainting model which is a highorder correction of the Mumford-Shah model, incorporating the Willmore energy (integral of the square of the curvature). They propose a numerical scheme based on the Γ-convergence approximation of Ambrosio and Tortorelli [START_REF] Ambrosio | Approximation of functional depending on jumps by elliptic functional via γ-convergence[END_REF][START_REF] Ambrosio | On the approximation of free discontinuity problems[END_REF]. Another high-order approach was proposed in [START_REF] Bertozzi | Inpainting of binary images using the Cahn-Hilliard equation[END_REF] based on the Cahn-Hilliard equation for binary images inpainting. This semi-linear fourth-order PDE originally introduced in material sciences by John W. Cahn and John E. Hilliard in [START_REF] Cahn | Free energy of a nonuniform system. I. Interfacial free energy[END_REF] describes the evolution of an interface separating two stable states. A variant named T V -H -1 model was proposed in [START_REF] Burger | Cahn-Hilliard inpainting and a generalization for grayvalue images[END_REF] as a generalization to the gray-scale images. In [START_REF] Cherfils | A CahnHilliard System with a Fidelity Term for Color Image Inpainting[END_REF][START_REF] Cherfils | Finite-dimensional attractors for the Bertozzi-Esedoglu-Gillette-Cahn-Hilliard[END_REF], the authors studied the existence of global attractors to some generalized Cahn-Hilliard equations and the effect of the non-linear potential on the model.

The multiscale approach.

It ressorts from this overview that most high-order approaches to the inpainting problem lead to the minimization of an energy of type [START_REF] Ambrosio | A direct variational approach to a problem arising in image reconstruction[END_REF]. Such models are generally highly nonlinear and require some sophisticated discretizations to be solved numerically. In another hand, the easiest way to obtain a fourth-order PDE is to minimize [START_REF] Blake | Visual Reconstruction[END_REF][START_REF] Carriero | Free gradient discontinuity and image inpainting[END_REF][START_REF] Zanetti | The Blake-Zisserman model for digital surface models segmentation[END_REF] which leads to solve the isotropic fourth-order (stationary) diffusion equation:

∫ D |∆u| 2 dx
(3) ∆ 2 u = 0, in D, u = f + another boundary condition on ∂D.
Of course, because of its strong smoothing effect, this model cannot capture some relevant features of the image like the corners and the edges which belong to the singular set of the image f . In this article, we consider the following equation:

     ∂ t u + ∆(∆ α u) + λ D (u -f ) = 0, in R + × Ω, u = ∆ α u = 0, on R + × ∂Ω, u(0, x) = f, in Ω, (4)
where ∆ α u = div(α(x)∇u) and λ D = λ 0 χ Ω\D for λ 0 ≫ 0 and χ Ω\D is the indicator function of the sub-domain Ω \ D. The values of the diffusion function α, which encodes different scales in the image, are dynamically and locally chosen in order to control the "amount" of smoothing of the operator. Note that the homogeneous boundary condition for u is not a restrictive condition and general boundary data can be handled by a lifting operator.

As the model remains linear with respect to u, it seems not well suited for capturing fine geometric structures of an image at a first glance. However, we prove that this approach allows us to restore such relevant features. The reason for this, is that the adaptive process which is the key of the method is in fact a nonlinear process, where the values of α are modified during the resolution. Together with a mesh adaption technique, we construct a nonlinear discrete approximation to make the method sensitive to the low-dimensional sets contained in the singular set of u. In addition, the process turns out to be Γ-convergent. Loosely speaking, the method allows us to adjust the model by modifying locally the diffusion coefficients instead of using a priori some nonlinear diffusion law or some nonlinear potential like in the Cahn-Hilliard based equations. This yields -and it is not a small advantagea simple numerical method which consists of solving only linear problems on u and updating the diffusion parameters from the informations given by some error indicators. In addition, we emphasize that a strong point in this approach is that it conciliates a local character of the parameter selection which enhance the accuracy and the global character given by the PDEs framework which ensures the coherence of the reconstruction for large features. Thus, it constitutes, as showed by the numerical simulations a balance between the performances of the local methods, mainly based on "copy-paste" procedures and well suited for textured images, and the performances of global methods (typically PDEs).

Organization of the paper. The remainder of this article is organized as follows: In Section 2, we prove by standard variational techniques and a fixed point theorem the existence of H 1 -solutions for the image inpainting problem. We obtain our equation as the gradient flow of an energy based on an H -1 -fidelity term. In Section 3, we describe in details the adaptive strategy. In particular, we show that it is a two-step approach where, a mesh-adaptation based on the metric error indicator is used first to fit the geometry of the computed solution, and second a residual type error indicator is used to locally select the value of α. We perform the Γ-convergence analysis of this process and we show that the solution u generated by the adaptive strategy approximates a solution of a new model which combines the Mumford-Shah functional and the H -1 -fidelity term. In Section 4, we recall the Cahn-Hilliard equation for image inpainting that we will use for the comparison with our model. Finally, in Section 5 we implement our approach and treat several numerical examples to test its efficiency and robustness.

2. Image inpainting problem. We study in this section the image inpainting problem by considering the system (4). For the sake of clarity, in the rest of the paper we omit the time dependence of functions and we use the notation u instead of u(t).

2.1. H 1 -weak solution of the stationary equation. Assume that Ω is a bounded open set of R 2 with piecewise smooth boundary ∂Ω. We recall that the operator ∆ -1 is the inverse of the negative Laplacian with homogeneous Dirichlet boundary conditions, i.e., u = ∆ -1 g is the unique solution of:

(5)

{

-∆u = g, in Ω, u = 0, on ∂Ω.

Let H -1 (Ω) be the dual space of H 1 0 (Ω) with corresponding norm ∥u∥ -1 = ∥∇∆ -1 u∥ 2 and inner product ⟨u, v⟩ -1 = ⟨∇∆ -1 u, ∇∆ -1 v⟩ 2 , where ⟨•, •⟩ 2 and ∥•∥ 2 are the classical inner product and its corresponding norm in the space L 2 (Ω).

We consider the solution of the following stationary problem:

(6) { ∆(∆ α u) + λ D (u -f ) = 0, in Ω, u = ∆ α u = 0, on ∂Ω,
which can be seen as stationary solution of ( 4). Problem ( 6) can be rewritten as follows:

(7)

{ ∆ α u + ∆ -1 (λ D (f -u)) = 0, in Ω, u = ∆ α u = 0, on ∂Ω,
or equivalently as a coupled elliptic system:

(8)      -∆ α u = w, in Ω, -∆w = λ D (f -u), in Ω, u = w = 0, on ∂Ω.
The weak formulation of problem ( 7) is:

Find u ∈ H 1 0 (Ω) such that: (9) ⟨α∇u, ∇ϕ⟩ 2 -⟨(λ D (f -u), ϕ⟩ -1 = 0, ∀ϕ ∈ H 1 0 (Ω).
Throughout the paper, we suppose that he domain Ω is partitioned into I disjoint sub-domains (Ω ℓ ) ℓ such that α is given by the piecewise constant scalar function:

α = α ℓ , in Ω ℓ , ℓ = 1, . . . , I.
We denote α m = min

1≤ℓ≤I α ℓ > 0 and α M = max 1≤ℓ≤I α ℓ .
Note that even if f ∈ L 2 (Ω), from the elliptic regularity results, one has w ∈ H 2 ∩ H 1 0 (Ω) however, the solution u might be only H 1 0 (Ω) since α is only bounded and measurable. In fact, we recall the following regularity result for the operator -div(α∇(•)):[9, Proposition 2.5] Proposition 1. There exists a constant c depending only on the geometry of Ω, such that a weak solution u of the associated Dirichlet problem belongs to H s+1 (Ω), for all real numbers s < s 0 , where s 0 is given by:

s 0 = min { 1 2 , c| log(1 - α m α M )| } .
Following the methodology used in [START_REF] Burger | Cahn-Hilliard inpainting and a generalization for grayvalue images[END_REF], we now prove the existence of the H 1weak solution of the stationary problem by means of Schauder's fixed-point theorem.

Proposition 2 (Schauder's fixed-point theorem [START_REF] Evans | Partial Differential Equations[END_REF]). Let X be a Banach space and K ⊂ X be a compact and convex set of X. Assume that the operator T : K -→ K is continuous. Then T admits a fixed point.

For R > 0, to be chosen later, we define the convex set:

V = {u ∈ H 1 0 (Ω)
; ∥u 2 ∥ ≤ R}, and we consider the following minimization problem: [START_REF] Belhachmi | Control of the effects of regularization on variational optic flow computations[END_REF] min

u∈H 1 0 (Ω) J (u, v), where (11) J (u, v) =    ∫ Ω α(x) 2 |∇u| 2 dx + 1 2λ0 ∥λ 0 u -λ D f -Λ D v∥ 2 -1 , if u ∈ V, +∞, otherwise,
with f and v ∈ L 2 (Ω) and where we set Λ D = λ 0 -λ D for brevity.

Proposition 3. Let v ∈ L 2 (Ω), the functional J (•, v) admits a unique minimizer u ∈ V .
Proof. The functional J (•, v) is strictly convex. In fact, let u 1 and u 2 be two functions in

H 1 0 (Ω) such that u 1 ̸ = u 2 and t ∈]0, 1[, we have: tJ (u 1 , v) + (1 -t)J (u 2 , v) -J (tu 1 + (1 -t)u 2 , v) = t(1 -t) 2 [∫ Ω α(x)|∇u 1 | 2 dx + ∫ Ω α(x)|∇u 2 | 2 dx -2 ∫ Ω α(x)∇u 1 • ∇u 2 dx ] + t(1 -t) 2λ 0 [ ∥λ 0 u 1 -λ D f -Λ D v∥ 2 -1 + ∥λ 0 u 2 -λ D f -Λ D v∥ 2 -1 ] - t(1 -t) λ 0 [∫ Ω ∇∆ -1 (λ 0 u 1 -λ D f -Λ D v) • ∇∆ -1 (λ 0 u 2 -λ D f -Λ D v)dx ] = t(1 -t) 2 ∫ Ω α(x)|∇(u 1 -u 2 )| 2 dx + t(1 -t) 2λ 0 ∥λ 0 (u 1 -u 2 )∥ 2 -1 > 0.
Furthermore, J (•, v) is weakly lower semi-continuous in H 1 (Ω). We consider a minimizing sequence (u n ) n∈N of J (•, v), i.e.,

J (u n , v) -→ n→∞ inf u∈V J (u, v) = L.
Then, there is a constant M > 0 such that ∫ Ω α(x)|∇u n | 2 dx ≤ M for all n ≥ 0, and also we have ∥u n ∥ 2 ≤ R (otherwise J (u n , v) would not be finite). Then, using the boundedness of α(x), we get that the sequence (u n ) n∈N is uniformly bounded in H 1 (Ω). Therefore, there exists a subsequence, still denoted (u n ) n∈N , such that

u n ⇀ n→∞ u weakly in H 1 (Ω) and u n -→ n→∞ u in L 2 (Ω), with ∥u∥ 2 ≤ R. Thanks to the continuity of the operator ∆ -1 : H -1 (Ω) -→ L 2 (Ω), we get: J (u, v) ≤ lim inf n→∞ J (u n , v).
The limit u is then a minimizer for J (•, v). The uniqueness is guaranteed by the strict convexity of J (•, v).

The Euler-Lagrange equation corresponding to [START_REF] Belhachmi | Control of the effects of regularization on variational optic flow computations[END_REF] reads:

(12) { -∆ α u -∆ -1 (λ D (f -u) + Λ D (v -u)) = 0, in Ω, u = ∆ -1 (λ D (f -u) + Λ D (v -u)) = 0, on ∂Ω.
Its weak formulation is: 2 (Ω) be the operator such that T (v) = u where u is the unique solution of [START_REF] Bertalmio | Navier-Stokes, fluid dynamics, and image and video inpainting[END_REF]. Therefore, if there exists a fixed point u = v of the operator, it will be a solution of problem [START_REF] Belhachmi | Mortar spectral element discretization of nonhomogeneous and anisotropic Laplace and Darcy equations[END_REF]. Proposition 4. The operator T admits a fixed point u ∈ V . Moreover, u is H 1weak solution of the equation [START_REF] Auroux | Application of the topological gradient method to color image restoration[END_REF].

Find u ∈ H 1 0 (Ω) such that: (13) ⟨α∇u, ∇ϕ⟩ 2 -⟨(λ D (f -u) + Λ D (v -u)), ϕ⟩ -1 = 0, ∀ϕ ∈ H 1 0 (Ω). Let T : L 2 (Ω) -→ L
Proof. Let v ∈ B(0, R) (where B(0, R) denotes the ball in L 2 (Ω) with center 0 and radius R). From Proposition 3, the minimization problem (11) admits a unique minimizer u = T (v) in the space H 1 (Ω) such that u ∈ B(0, R). Since the embedding H 1 (Ω) → L 2 (Ω) is compact, the operator T then maps L 2 (Ω) → K, where K is a compact subset of L 2 (Ω). Thus we have:

T : B(0, R) -→ B(0, R) ∩ K = K,
where K is a compact and convex subset of L 2 (Ω). To apply Schauder's fixed-point theorem, it remains to prove that T is continuous in B(0, R). Let (v k ) k≥0 be a sequence which converges to v ∈ L 2 (Ω) and T (v k ) = u k . The function u k is then the unique minimizer of (11) associated with v k , and we have:

J (u k , v k ) ≤ J (0, v k ), i.e., J (u k , v k ) ≤ 1 2λ0 ∥λ D f + Λ D v k ∥ 2 -1 . Since L 2 (Ω) → H -1 (Ω), we get ∥v k ∥ -1 ≤ C∥v k ∥ L 2 (Ω) ≤ CR and also ∥λ D f ∥ -1 ≤ C ′ for
some given constants C, C ′ > 0. Accordingly, we obtain the following estimate:

J (u k , v k ) ≤ C ′ + CR 2 ,
and then (u k ) k≥0 is uniformly bounded in H 1 (Ω). Thus, we can consider a convergent subsequence

u kj ⇀ j→∞ u ∈ H 1 (Ω) and u kj -→ j→∞ u in L 2 (Ω). Hence, the unique (weak) solution T (v k ) = u k of: { -∆ α u k -∆ -1 (λ D (f -u k ) + Λ D (v k -u k )) = 0, in Ω, u k = ∆ -1 (λ D (f -u k ) + Λ D (v k -u k )) = 0, on ∂Ω,
weakly converges to the unique weak solution u of [START_REF] Belhachmi | Weighted harmonic and complex Ginzburg-Landau equations for gray value image inpainting[END_REF]. From the uniqueness of the solution in V , we obtain u = T (v). We then deduce that T is continuous in L 2 (Ω) and the existence of a stationary solution u follows from Schauder's fixedpoint theorem. In addition, this solution satisfies [START_REF] Auroux | Contour detection and completion for inpainting and segmentation based on topological gradient and fast marching algorithms[END_REF], or equivalently, is a stationary solution of the problem (4).

Remark 1. The solution u of equation ( 6) verifies the estimate:

α m ∥∆u∥ 2 + λ 0 2 ∥u∥ 2 ≤ λ 0 2 ∥f ∥ 2 .
Therefore, we may choose R = ∥f ∥ 2 .

2.2. The evolution equation. Now, observe that the previous existence proof of a stationary solution applies to show that the following unbounded operator (in L 2 ):

A(u) = ∆(∆ α u) + λ D u,
is maximal. Moreover, we have:

⟨A(u), u⟩ 2 ≥ I ∑ ℓ=1 α m ⟨∆u, ∆u⟩ L 2 (Ω ℓ ) + ⟨λ D u, u⟩ 2 ≥ 0,
which means that it is monotone. Thus it follows from the theory of maximal monotone operators [START_REF] Brézis | Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert[END_REF], that the evolution problem (4) admits a unique solution u ∈ L 2 (0, T ;

H 1 0 (Ω) ∩ H 1 (0, T ; H -1 (Ω)) ∩ C([0, T ] ; L 2 (Ω)).
As in the stationary case, problem (4) can be splitted into two second-order equations by introducing an auxiliary function w such that:

(14)          ∂ t u -∆w + λ D (u -f ) = 0, in R + × Ω, -∆ α u = w, in R + × Ω, u = w = 0, on R + × ∂Ω, u(0, x) = f (x),
in Ω.

The weak formulation reads then: Find a pair (u, w) ∈ L 2 (0, T ;

H 1 0 (Ω)∩H 1 (0, T ; H -1 (Ω)))×L 2 (0, T ; H 1 0 (Ω)), u(0, x) = f (x), such that: (15) { ⟨∂ t u, ϕ⟩ 2 + ⟨∇w, ∇ϕ⟩ 2 + ⟨λ D u, ϕ⟩ 2 = ⟨λ D f, ϕ⟩ 2 , ∀ϕ ∈ H 1 0 (Ω), ⟨α∇u, ∇ψ⟩ 2 -⟨w, ψ⟩ 2 = 0, ∀ψ ∈ H 1 0 (Ω).
Let u the solution of problem (4). Then, it is easy to verify that the pair (u, -∆ α u), is a weak solution of [START_REF] Bertalmio | Image inpainting[END_REF]. We consider another solution (u 1 , w 1 ) ∈ H 1 0 (Ω) × H 1 0 (Ω) of the system (15), we then have:

{ ⟨∂ t (u -u 1 ), ϕ⟩ 2 + ⟨∇(w -w 1 ), ∇ϕ⟩ 2 + ⟨λ D (u -u 1 ), ϕ⟩ 2 = 0, ∀ϕ ∈ H 1 0 (Ω), ⟨α∇(u -u 1 ), ∇ψ⟩ 2 -⟨(w -w 1 ), ψ⟩ 2 = 0, ∀ψ ∈ H 1 0 (Ω).
Let (ζ ℓ ) I ℓ=1 be a partition of unity associated to the decomposition (Ω ℓ ) I 1 , and picking

ψ = α -1 ℓ ζ ℓ (w -w 1 )
, in the second equation, we have the identity:

∫

Ω ℓ α -1 ℓ ζ ℓ (w-w 1 ) 2 dx = ∫ Ω ℓ α ℓ ∇(u-u 1 ) α -1 ℓ ∇ζ ℓ (w-w 1 ) dx, ∀l = 1, • • • , I.
Summing up, we get (after integrating by parts twice the right-hand side):

(17)

I ∑ ℓ=1 α -1 ℓ ∫ Ω ℓ ζ ℓ (w -w 1 ) 2 dx = ∫ Ω ∇(u -u 1 ) ∇(w -w 1 ) dx ≥ 0.
By choosing the test function ϕ = u -u 1 in the first equation and using [START_REF] Bertozzi | Inpainting of binary images using the Cahn-Hilliard equation[END_REF] and the positivity of λ D , we obtain:

⟨∂ t (u -u 1 ), u -u 1 ⟩ 2 = -⟨∇(u -u 1 ), ∇(w -w 1 )⟩ 2 -⟨λ D (u -u 1 ), (u -u 1 )⟩ 2 ≤ 0. So that ∂ t (∥u(t) -u 1 (t)∥ 2 2 ) = 2⟨∂ t (u -u 1 ), u -u 1 ⟩ 2 ≤ 0. It follows that the function t → ∥u(t) -u 1 (t)∥ 2
2 is decreasing on R + . Since u(0) = u 1 (0), we get u = u 1 which implies that w = w 1 . Thus, problems (4) and ( 15) are equivalent.

Semi-discrete time problem. For the discretization of the time derivative

∂ t u, we use the forward Euler scheme. Let u -u old ∆t be an approximation of

∂ t u,
where ∆t is a time step, u old and u are the solutions at time t old and t = t old + ∆t, respectively. Therefore, time discretization together with splitting scheme (14) leads to the following time-stepping problem:

(18)

   ⟨ u -u old ∆t , ϕ⟩ 2 + ⟨∇w, ∇ϕ⟩ 2 + ⟨λ D u, ϕ⟩ 2 = ⟨λ D f, ϕ⟩ 2 , ∀ϕ ∈ H 1 0 (Ω), ⟨α∇u, ∇ψ⟩ 2 -⟨w, ψ⟩ 2 = 0, ∀ψ ∈ H 1 0 (Ω).
Proposition 5. For a fixed u old ∈ H 1 0 (Ω), the problem ( 18) admits a solution (u, w) ∈ H 1 0 (Ω) × H 1 0 (Ω). Proof. For a given v ∈ L 2 (Ω), u old ∈ H 1 0 (Ω) and ∆t > 0, we define:

λ ′ D = λ D + 1 ∆t and f ′ = 1 λ ′ D ( λ D f + u old ∆t
) .

We then consider the following problem:

(19) { -∆ α u -∆ -1 (λ ′ D (f ′ -u)) = 0, in Ω, u = ∆ α u = 0, on ∂Ω.
Similarly to Proposition 3, we can prove the existence of H 1 -solution of ( 19) such that the pair (u, -∆ α u) satisfies the system [START_REF] Bertozzi | Unconditionally stable schemes for higher order inpainting[END_REF]. To prove the uniqueness, let (u 1 , w 1 ) ∈ H 1 0 (Ω) × H 1 0 (Ω) be another solution of the system (18), we then have: { ⟨∇(w -w 1 ), ∇ϕ⟩ 2 + ⟨λ ′ D (u -u 1 ), ϕ⟩ 2 = 0, ∀ϕ ∈ H 1 0 (Ω), ⟨α∇(u -u 1 ), ∇ψ⟩ 2 -⟨(w -w 1 ), ψ⟩ 2 = 0, ∀ψ ∈ H 1 0 (Ω). Following the same lines than for the system (15) and using the inequality [START_REF] Bertozzi | Inpainting of binary images using the Cahn-Hilliard equation[END_REF], we obtain:

⟨λ ′ D (u -u 1 ), (u -u 1 )⟩ 2 = -⟨∇(u -u 1 ), ∇(w -w 1 )⟩ 2 ≤ 0.
From the nonnegativity of λ ′ D , we get: ⟨λ ′ D (u -u 1 ), (u -u 1 )⟩ 2 = 0. Therefore u = u 1 and consequently w = w 1 .

3. Fully discrete problem and the adaptive strategy. We assume that the domain Ω is polygonal and we consider a regular family of triangulations T h made of element which are triangles (or quadrilaterals) with a maximum size h, satisfying the usual admissibility assumptions, i.e., the intersection of two different elements is either empty, a vertex, or a whole edge. For h > 0, we introduce the following discrete space:

X h = { v h ∈ C(Ω)|∀K ∈ T h , v h | K ∈ P 1 (K) } ∩ H 1 0 (Ω).

The discretized version of the splitted problem (15) leads to finding a pair

(u h , w h ) ∈ X h × X h solution of: (20)    ⟨ u h -u old h ∆t , ϕ h ⟩ 2 + ⟨∇w h , ∇ϕ h ⟩ 2 + ⟨λ D u h , ϕ h ⟩ 2 = ⟨λ D f h , ϕ h ⟩ 2 , ∀ϕ h ∈ X h , ⟨α∇u h , ∇ψ h ⟩ 2 -⟨w h , ψ h ⟩ 2 = 0, ∀ψ h ∈ X h ,
where f h is a finite element approximation of f associated with T h . Since X h ⊂ H 1 0 (Ω), the well-posedness of the problem (20) follows from (18).

3.1. Γ-convergence analysis and the adaptive algorithm. In this section, we will prove that the approach considered in the article allows us to approximate, in the Γ-convergence sense, a new model that couples a Mumford-Shah functional with an H -1 -term, which we will call MS-H -1 . Γ-convergence analysis. A Γ-convergence study of this adaptive strategy was presented in [START_REF] Belhachmi | An adaptive approach for segmentation and TV edgeenhancement in the optic flow estimation[END_REF] for optic flow estimation. The authors proved that this algorithm is equivalent to the adaptive one introduced by Chambolle-Dal Maso [START_REF] Chambolle | Discrete approximation of the Mumford-Shah functional in dimension two[END_REF] and Chambolle-Bourdin [START_REF] Chambolle | Implementation of an adaptive finite-element approximation of the Mumford-Shah functional[END_REF] where a numerical discrete approximation of the Mumford-Shah energy was proposed. This approach, based on finite-element discretization and adaptive mesh strategy, is a good approximation, in the Γ-convergence sense [START_REF] Braides | Oxford Lecture Series in Mathematics and its Applications[END_REF] of the Mumford-Shah energy [START_REF] Mumford | Optimal approximations by piecewise smooth functions and associated variational problems[END_REF] (see [START_REF] Chambolle | Discrete approximation of the Mumford-Shah functional in dimension two[END_REF] for more details). We briefly recall the results and the numerical approximation of this method. For a fixed angle 0 < θ 0 ≤ 2π/3, a constant c ≥ 6, and for ϵ > 0, let T ϵ (Ω) = T ϵ (Ω; θ 0 ; c) be the set of all triangulations of Ω whose triangles K have the following characteristics: (i) The length of each of the three edges of K is between ϵ and ϵc.

(ii) The three angles of K are greater than or equal to θ 0 . Let V ϵ (Ω) be the set of all continuous functions u : Ω -→ R such that u is affine on each triangle K of a triangulation T ∈ T ϵ (Ω). For a given u, we define T ϵ (u) ⊂ T ϵ (Ω) as the set of all triangulations adapted to the function u, i.e., such that u is piecewise affine on T. We consider a non-decreasing continuous function g : [0, +∞) -→ [0, +∞) such that:

lim t→0 g(t) t = 1, lim t→+∞ g(t) = g ∞ < +∞.
For any u ∈ L p (Ω), (p ≥ 1) and T ∈ T ϵ (Ω), the authors in [START_REF] Chambolle | Discrete approximation of the Mumford-Shah functional in dimension two[END_REF] introduced the following minimization problem:

(21) G ϵ (u) = min T∈Tϵ(Ω) Gϵ (u, T),
where

Gϵ (u, T) =    ∑ K∈T |K ∩ Ω| 1 h K g(h K |∇u| 2 ), u ∈ V ϵ (Ω), T ∈ T ϵ (Ω), +∞, otherwise.
When ϵ goes to zero and provided θ 0 is less than some Θ > 0, it was proven that the energy G ϵ Γ-converges to the Mumford-Shah functional:

G(u) =    ∫ Ω |∇u(x)| 2 dx + g ∞ H 1 (S u ), u ∈ L 2 (Ω) ∩ GSBV (Ω), +∞, u ∈ L 2 (Ω)\GSBV (Ω),
where is GSBV (Ω) the generalized special function of bounded variation (see [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF]).

Remark 2. If F : X -→ [-∞, +∞] is continuous and (G ϵ ) ϵ Γ-converges to G then (F + G ϵ ) ϵ Γ-converges to F + G.
From the result of the Γ-convergence of G ϵ to G, see [START_REF] Chambolle | Discrete approximation of the Mumford-Shah functional in dimension two[END_REF]Theorem 2], the continuity of the second term of the functional in L 2 (Ω) (which follows from the continuity of ∆ -1 , i.e., the stability in the elliptic problems) and Remark 2, we have: Proposition 6. Let f and v in L 2 (Ω) be two given functions and ϵ > 0 be a positive parameter. Therefore, the sequence of functionals

G ϵ (u ϵ ) + 1 2λ0 ∥λ 0 u ϵ -λ D f -(λ 0 -λ D )v∥ 2 -1 , Γ-converges for ϵ -→ 0 in the topology of L 2 (Ω) to G(u) + 1 2λ0 ∥λ 0 u -λ D f -(λ 0 -λ D )v∥ 2 -1 .
In the theorem we note that the variable α do not appear explicitly in G or G ϵ . To introduce such an α, let ψ be the Legendre-Fenchel transform of g. For a given triangulation T ϵ , it was proven in [START_REF] Chambolle | Discrete approximation of the Mumford-Shah functional in dimension two[END_REF] that the minimization of G ϵ is equivalent to the minimization of the following functional:

G ′ ϵ (u, v, T ϵ ) = ∑ K∈Tϵ |K ∩ Ω| 1 h K ( v K |∇u| 2 + ψ(v K ) h K ) ,
over all u ∈ V ϵ (Ω) and v = (v K ) K∈Tϵ (Ω), piecewise constant on each K ∈ T ϵ . For a fixed u, it follows from standard convex analysis that the minimizer over each v is explicitly given by:

(22) v K = g ′ (h K |∇u| 2 ).
Choosing α = v leads to the adaptive strategy that we describe now..

Remark 3.

The analysis presented here is carried out with the Neumann boundary conditions on u, which is the framework used in [START_REF] Belhachmi | An adaptive approach for segmentation and TV edgeenhancement in the optic flow estimation[END_REF][START_REF] Chambolle | Implementation of an adaptive finite-element approximation of the Mumford-Shah functional[END_REF][START_REF] Chambolle | Discrete approximation of the Mumford-Shah functional in dimension two[END_REF] for a denoising problem or optic flow estimation. The application to the Dirichlet case requires some (tedious but non-essential) modifications and the result still holds.

3.2. Adaptive procedure. For each element K ∈ T h , the following local discrete energy:

(23) η K = α 1 2 K ∥∇u h ∥ L 2 (K)
, contains some information on the error distribution of the computed solution u h . In fact, the discontinuities (edges) are contained in regions where the brightness changes sharply and consequently where this error indicator is large. Moreover, it may be proven that the gradient of u h captures this change in brightness and its magnitude provides an information about the "strength" of the edges (see [START_REF] Belhachmi | Control of the effects of regularization on variational optic flow computations[END_REF]). Thus, the quantity (23) acts as an edge detector and locates such regions. Furthermore, this local error indicator is in some sense equivalent to the energy norm mostly used as an edge detection in the topological gradient based-methods [START_REF] Auroux | Application of the topological gradient method to color image restoration[END_REF][START_REF] Auroux | Contour detection and completion for inpainting and segmentation based on topological gradient and fast marching algorithms[END_REF][START_REF] Auroux | Image processing by topological asymptotic expansion[END_REF]. This particularity makes it well suited to control and locally select the diffusion coefficient α using the following algorithm: Algorithm 1. Start with the initial grid T 0 h corresponding to the image.

Adaptive steps:

• Compute u 0 h on T 0 h with a large constant α = α 0 by solving [START_REF] Braides | Oxford Lecture Series in Mathematics and its Applications[END_REF]. • Build an adapted mesh T 1 h (in the sense of the finite element method, i.e., with respect to the parameter h) with a metric error indicator (to solve [START_REF] Brézis | Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert[END_REF]). • In the triangles where η K is large (with respect to its mean value), we perform a local choice of α(x) on T 1 h to obtain a new function α 1 (x) following [START_REF] Burger | Cahn-Hilliard inpainting and a generalization for grayvalue images[END_REF]. 3. Go to steps 1. and 2. and compute u 1 h on T 1 h .

We emphasize that we have to solve only linear problems on u and then to update α. Actually, in place of introducing a function g like in the theorem, we use the following formula for the update of α in each triangle K:

(24) α k+1 K = max      α k K 1 + τ * (( η K ∥η∥ ∞ ) -0.1 ) + , α trh      ,
where α trh is a threshold parameter and τ is a coefficient which controls the rate of decrease in α, u + = max(u, 0). Here η is the piecewise-constant function such that η| K = η k , ∀K ∈ T 1 h . Remark 4. There are other several possibles choices of functions g to compute α. The formula [START_REF] Carriero | Free gradient discontinuity and image inpainting[END_REF] corresponds to min(t, g ∞ ) and is the one we implemented for the numerical computations here. Loosely speaking, it may be understood as follows: in regions of high gradients, it decreases the values of α when the error indicator deviates more then 10% from its mean value. α decreases nearly as a geometric sequence with the iteration number, until a given threshold is attained.

Let us give more details on the implementation of this algorithm. First, we build an adapted mesh T 1 h as follows: close to the jump sets of u h , the error is large, we then cut the element K into a finite number of smaller elements to decrease such an error and to fit the edges, while, far from these jump sets, there is no restriction on how to choose the triangles and the initial grid is coarsened. The adopted meshes have small number of degrees of freedom in the homogeneous regions which makes the method considerably fast. Second, we perform an "optimal" choice of the function α following the map furnished by the error indicator (η K ) K∈T h , on each element K and in accordance with [START_REF] Carriero | Free gradient discontinuity and image inpainting[END_REF] in order to correctly approximate edges.

To conclude this section let us try to interpret in term of a PDE the Γ-limit G. We may say that the sequence (u ϵ , α ϵ ) constructed by the adaptive algorithm is Γ-convergent to a Mumford-Shah-H -1 functional (MS-H -1 ) and that it solves ∆(∆ αϵ u ϵ ) + λ D (u ϵ -f ) = 0, in Ω, after eliminating w ϵ from the mixed formulation [START_REF] Braides | Oxford Lecture Series in Mathematics and its Applications[END_REF]. Of course there are others Γ-convergent approximation functionals to the MS-H -1 , e.g. The Cahn-Hilliard model.

4. Cahn-Hilliard equation. For the sake of completeness, we will make a comparison with the Cahn-Hilliard model [START_REF] Bertozzi | Analysis of a two-scale Cahn-Hilliard model for image inpainting[END_REF][START_REF] Bertozzi | Inpainting of binary images using the Cahn-Hilliard equation[END_REF][START_REF] Bertozzi | Unconditionally stable schemes for higher order inpainting[END_REF] that we now recall. The Cahn-Hilliard equation [START_REF] Cahn | Free energy of a nonuniform system. I. Interfacial free energy[END_REF] originally refers to John W. Cahn and John E. Hilliard [START_REF] Cahn | Free energy of a nonuniform system. I. Interfacial free energy[END_REF] and was introduced to phenomenologically describe phase separation, i.e., the change from one state to another. It is a fourth-order semi-linear PDE and is obtained as the H -1 -gradient flow of the following Ginzburg-Landau energy: [START_REF] Chambolle | Implementation of an adaptive finite-element approximation of the Mumford-Shah functional[END_REF] 1 2

∫ Ω |∇u| 2 dx + 1 ϵ 2 W (u),
where phase separation is modeled by the smooth free energy, e.g., double-well potentials W such that:

(26) W (u) = (1 -u 2 )u 2 ,
or a non-smooth free energy as follows:

(27) W (u) = ψ(u) + I [0,1] (u),
where ψ(u) = 1 2 u(1 -u), and

I [0,1] (u) := { 1 2 u(1 -u), 0 ≤ u ≤ 1, +∞, otherwise.
The analogy between the Cahn-Hilliard model in material sciences and Cahn-Hilliard model in image inpainting is that the two state phases are considered as two homogeneous regions and the interface is considered as an edge. In image inpainting, it was exploited by Bertozzi et al. in [START_REF] Bertozzi | Inpainting of binary images using the Cahn-Hilliard equation[END_REF] and afterwards in [START_REF] Bertozzi | Analysis of a two-scale Cahn-Hilliard model for image inpainting[END_REF][START_REF] Bertozzi | Unconditionally stable schemes for higher order inpainting[END_REF][START_REF] Burger | Cahn-Hilliard inpainting and a generalization for grayvalue images[END_REF] by considering the following equation:

(28)    ∂ t u + ∆(ϵ∆u -1 ϵ W ′ (u)) + λ D (u -f ) = 0, in R + × Ω, u = f and ϵ∆u -1 ϵ W ′ (u) = 0, on R + × ∂Ω, u(0, x) = f,
in Ω, which was obtained by incorporating the data fidelity term λ D (f -u). Note that the classical Chan Hilliard equation ( 28) is only appropriate for two-scale (binary) images inpainting due to the double well potential W which vanishes on only the values 0 and 1.

Remark 5.

For the time discretization of Cahn-Hilliard equation, we use a convexity splitting scheme (see [START_REF] Bertozzi | Unconditionally stable schemes for higher order inpainting[END_REF][START_REF] Burger | Cahn-Hilliard inpainting and a generalization for grayvalue images[END_REF]). The idea is to divide the energy functional into two parts; a convex part plus a concave one. The convex part is then treated implicitly while the concave part is treated explicitly.

Numerical experiments.

In this work, all the PDEs are solved with the open source software FreeFem++ [START_REF] Hecht | New development in freefem++[END_REF]. In all examples, the damaged/missed regions are delimited by the red contour. We give some examples for the application of our proposed approach to image inpainting. The goal is to reconstruct the missing information in the red parts, i.e., D, by the diffusion of the information from the intact part, i.e, Ω\D. In all examples, we set λ 0 = 10 7 , and ∆t = 0.1 and an initial guess u(0, x) = 0.5, ∀x ∈ D. Curvature inpainting. We present the numerical results for the adaptive inpainting approach in order to illustrate the effectiveness of the proposed algorithm for the inpainting of curvature. In Fig. 1, we present the reconstruction of quarter of a circle. We display the evolution of the restored image for iterations 1, 5 and 20. In the first iteration (α is constant), we solved a biharmonic equation which gives a curved, but a very smooth (blurred), edge in D. By iterations, we can see the efficiency of the adaptation process in the damaged region where the edge was inpainted sharply by simultaneously keeping its curvature.

Other examples are presented in Fig. 2 and Fig. 4. The curvature in Fig. 2 is well inpainted which proves that our approach, based on fourth-order linear diffusion model, allows us to obtain a very interesting result that one might expect by solving comlpex PDEs like the Euler's elastica [START_REF] Shen | Euler's elastica and curvature-based inpainting[END_REF], which is highly nonlinear and numerically difficult to solve. We give in Fig. 5 a zoom caption in the damaged region 2 which proves that the missing part is well restored and is very close to the original one.

"Real world"-image inpainting. The experiments in Fig. 6 show the efficiency of the proposed method in a real image inpainting. The portions of unknown pixels are 45%, 55% and 75%, respectively. From these experiments, we can see that the proposed model can successfully recover the inpainting domain even when up to 75% of pixels are unknown.

Comparison with the Cahn-Hilliard model. In Fig. 7, we have chosen the same image presented by Bertozzi, Esedoglu and Gillette (see [START_REF] Bertozzi | Inpainting of binary images using the Cahn-Hilliard equation[END_REF]). We give the result obtained by solving the Cahn-Hiliard equation and the one obtained using our approach. We display the evolution of the restored image at iteration 1, 5 and 10 which show that the edges are progressively and sharply approximated and the four corners are very accurately matched. Notice that the image for Cahn-Hilliard equation is computed in a two-steps process. In the first step, the authors solved their equation with a large value of ϵ, e.g., ϵ = 0.1, until the numerical scheme is close to a steady state. In this step, the level lines are continued into the missing domain. In a second step, they used the previous result as an initial time condition u 0 for a smaller ϵ (e.g., ϵ = 0.01) in order to sharpen the contours. This is an adaptive choice for ϵ, however, subjected to a hand tuning and being uniform in the entire domain.

Broken three bars. In Fig. 8, we show the inpainting result for a synthetic image which represents three broken bars forming a T -junction. We give the restored images using total variation, harmonic and biharmonic models, respectively. As excepted, total variation inpainting model is unable to connect the edges between the three bars because it does not fulfill the connectivity principle. Harmonic and biharmonic inpainting models produce a smooth solution u in D, blurring the edges. However, the proposed approach is able to sharply connect the edges between three bars while enforcing the curvature.

Conclusion.

In this article, we have investigated a multiscale approach to a diffusion operator of fourth-order for the image inpainting. The model is linear with respect to the variable u representing the image to be reconstructed and is depending on a spatially varying diffusion function. We introduced an adaptive approximation procedure based on some a posteriori error indicators, which allows us to select the diffusion coefficient using the available data and the informations on the computed solution. We analyzed this approach from the variational point of view and we established its connections with a Mumford-Shah-like energy, in the sense of the Γ-convergence. We have implemented the considered model to test the method, we have also made some comparisons with existing approaches to demonstrate its capabilities. We have underlined, in the presented tests, the good quality in the recovery of low-dimensional sets (edges, corners) and of the curvature (of edges) in the inpainted zones. We emphasize that in our approach the adaptive selection of the diffusion coefficients is:

(i) Fully automatic, i.e., no external intervention on the algorithm is required.

(ii) Objective and a posteriori, i.e., the scale of α (the rate of decreasing its values) is explicitly obtained from computable quantities (error indicators) which are sensitive to the singularities of the solution. Thus, no a priori guess is necessary (iii) Local, i.e., made at each location in the computation domain (finite-element cell, thus the pixel scale). (iv) Low-cost, in the sens of the number of degrees of freedom, thanks to the coarsening of the mesh in the homogeneous parts of the domain. In addition, the method may be improved straightforwardly by considering α, the diffusion function, as a matrix which introduces some anisotropy in the models and the overall approach is easy to implement in the framework of variational methods of approximation.

Figure 1 .

 1 Figure 1. Top row: Original and damaged images. Middle row:Restored image using the model (4) and adaptation at iterations 1, 5 and 20, respectively. Bottom row: Mesh evolution at iterations 1, 5 and 20, respectively.

Figure 2 .

 2 Figure 2. Form left to right: Original, damaged and restored images using model (4) and adaptation.

Figure 3 .

 3 Figure 3. Mesh evolution at iterations 2, 5 and 10, respectively.

Figure 4 .

 4 Figure 4. Top row: Original, damaged and restored images using model (4) and adaptation., respectively. Bottom row: The evolution of the mesh at iterations 1, 5 and 20, respectively.

Figure 5 .

 5 Figure 5. Zoom on the damaged region 2: Original and restored.

Figure 6 .

 6 Figure 6. The damaged, mask and restored images, respectively. Over: 45% of pixels are damaged-Middle: 55% of pixels are damaged. Below: 75% of pixels are damaged.

Figure 7 .

 7 Figure 7. Top row: Damaged and restored images using model (4) and adaption (iterations 1 and 5). Bottom row: Restored images using model (4) and adaption (iterations 10 and 20) and Cahn-Hilliard model.

Figure 8 .

 8 Figure 8. Top row: Damaged image and restored ones using total variation and harmonic models, respectively. Bottom row: Restored images using biharmonic model and our approach at iterations 5 and 20, respectively.


published or not. The documents may come

An extension of the Tusnady inequality for general distributions

Ion

An extension of the Tusnady inequality for general distributions Ion Grama

Université de Bretagne Sud, France ion.grama@univ-ubs.fr

Under mild assumptions an analog of Tusnady's inequality for conditional distributions of partial sums of independent nonidentically distributed r.v.'s is obtained. These type of inequalities provide very sharp bounds for couplings of random variables via quantile transformations, which are main tools for proving various strong invariance principles for sums of independent random variables. We reffer to Komlós, Major andTusnády (1975, 1976), Sakhanenko (1984), Zaitsev (1996), Grama, I. andNussbaum, M. (2002), Carter andPollard (2004) and to references therein for details. Recently quantile transformations have been applied for establishing a constructive asymptotic equivalence of statistical experiments, see Brown, Carter, Low and Zhang (2004).

Let (Ω, F, P ) be a probability space and λ be a real number satisfying 0 < λ < ∞. Denote by D(λ) the subset of all real valued random variables S on the probability space (Ω, F, P ), which admits for some n ≥ 1, a representation of the form S = X 1 + ... + X n , where X 1 , ..., X n are independent r.v.'s, satisfying assumptions A1 The r.v.'s X 1 , ..., X n are of means zero and finite variances:

EX i = 0, 0 < EX 2 i < ∞, i = 1, ..., n.

A2

The following Sakhanenko's condition holds true:

λE |X i | 3 exp {λ |X i |} ≤ EX 2 i , i = 1, ..., n.
Let i = √ -1 and ε, ν be real numbers, such that 0 < ε ≤ 1/96 and 0 < ν < ∞. Denote by D 1 (λ) the subset of all r.v.'s S ∈ D(λ) which additionally satisfy the smoothness assumption

S1 The r.v. S is such that, sup |h|≤λ |t|>ελ E exp {(it + h)S} E exp {hS} dt ≤ ν λES 2 .
Denote by D 2 (λ) the subset of all r.v.'s S ∈ D(λ) which take discrete values a + ∆k, k ∈ {0, ±1, ±2, ...} with maximal span ∆, where 0 ≤ a < ∆ and λ∆ ≤ π/ε, and which additionally satisfy the assumption (S2)

S2 The r.v. S is such that, sup |h|≤λ ελ<|t|≤π/∆ E exp {(it + h)S} E exp {hS} dt ≤ ν λES 2 . 1 Let us agree that X is the range of a r.v. S in the class D 1 (λ) or D 2 (λ), i.e. X = R, if S ∈ D 1 (λ) and X = {a + ∆k : k = 0, ±1, ±2, ...} , if S ∈ D 2 (λ).
Assume that we are given three r.v.'s S 0 , S 1 and S 2 with mean 0 and finite variance, so that S 1 and S 2 are independent and

S 0 = S 1 + S 2 , S i ∈ D(λ). Set B 2 k = ES 2 k , k = 0, 1, 2 and B = B 1 B 2 /B 0 . Let Ψ k (h) be the cumulant generating function of the r.v. S k , i.e. Ψ k (h) = log E exp{hS k }, |h| ≤ λ, k = 0, 1, 2. It is easy to see that Ψ 0 (h) is strictly increasing, for |h| ≤ λ. Let H 0 (x) = h be the solution of the equation Ψ 0 (h) = x, for x in the range of Ψ 0 (h). Set B = B 1 B 2 /B 0 , µ(y) = Ψ 1 (H 0 (y)) = y -Ψ 2 (H 0 (y)),
and

σ 2 (y) = Ψ 1 (H 0 (y))Ψ 2 (H 0 (y))/Ψ 0 (H 0 (y)).
Define the conditional distrubution function

F (x|y) = P (S 1 ≤ x|S 0 = y) .
In the sequel c i , i = 0, 1, ... denote positive absolute constants and

θ i , i = 1, 2, ... real numbers satisfying |θ i | ≤ 1. Theorem 1. Assume that S 0 , S 1 , S 2 ∈ D 1 (λ) or S 0 , S 1 , S 2 ∈ D 2 (λ)
, for some 0 < λ < ∞. Then, for any x, y ∈ X satisfying |x| ≤ c 0 λB 2 and |y| ≤ c 0 λB 2 , we have

F (x + µ(y)|y) = Φ x σ(y) + θ 1 c 1 λσ(y) 1 + x 2 σ 2 (y) ,
provided λB ≥ c 2 . Moreover, for y ∈ X satisfying |y| ≤ c 0 λB 2 , we have

µ(y) = β 1 y + θ 2 c 3 y 2 λB 2 , 1 σ 2 (y) = 1 B 2 + θ 3 c 4 |y| λB 4 ,
where

β 1 = B 2 1 /B 2 0 .
In the case case of sums of i.i.d. r.v.'s we get the following result. Let ξ 1 , ..., ξ n , n ≥ 1 be a sequence of i.i.d. r.v.'s of means 0 and finite variances σ 2 = Eξ 2 i < ∞, obeying one of the two conditions (G1) or (G2) below:

G1 For some 0 < λ < ∞ and q ≥ 1, sup |h|≤λ ∞ -∞ |E exp((it + h)ξ i )| q dt < ∞.
G2 The r.v. ξ i takes values on the lattice a + ∆k, k ∈ Z with maximal span ∆ and for some 0 < λ < ∞,

E exp(λ |ξ i |) < ∞.
The common cumulant generating function of ξ i -th is denoted by ψ(t) = log E exp(tξ i ), for |t| ≤ λ. Let h(x), |x| ≤ λ/8 be the inverse of the monotone function ψ (t), |t| ≤ λ/4. Assume that n 1 , n 2 are positive integers such that n 1 + n 2 = n. Set S 1 = ξ 1 +...+ξ n 1 , S 0 = ξ 1 +...+ξ n and F (x|y) = P (S 1 ≤ x|S 0 = y) .

Theorem 2. For any |x| ≤ c 0 λnσ 2 and |y| ≤ c 0 λnσ 2 , we have

F (x + µ(y)|y) = Φ x σ(y) + θ 1 c 1 λσ(y) 1 + x 2 σ 2 (y)
.

where

µ(y) = n 1 n y, σ 2 (y) = n 1 n 2 n ψ h y n .
Proofs of Theorems 1 and 2 rely on Lemmas 1 and 2 below, which are of independent interest.

Assume that we are given a real valued r.v. X, which has a density p(x) w.r.t. Lebesque measure on the real line. We shall impose conditions (C1-C2) below, where γ 0 , ..., γ 4 > 0 and σ > 1 denote real quantities not depending on x.

C1 For any |x| ≤ γ 0 σ, p(x) = 1 √ 2π exp - x 2 2 + θ 1 γ 1 2 x 3 σ 1 + θ 2 γ 2 1 + |x| σ ,
where

|θ i | ≤ 1, i = 1, 2.
C2 For any |x| ≤ γ 0 σ and any real z satisfying zx ≥ 0,

p (x + z) ≤ γ 3 exp - x 2 2 + γ 1 2 x 3 σ -γ 4 zx .
Lemma 1. Assume that the density p(x) satisfies conditions (C1-C2). Then, for any x satisfying |x| ≤ c 0 σ, we have

Φ x -c 1 1 + x 2 σ ≤ P (X ≤ x) ≤ Φ x + c 1 1 + x 2 σ ,
provided σ ≥ c 2 , where c 0 , c 1 and c 2 are constants depending only on γ 0 , ..., γ 4 . Let ∆ 0 > 0 and ∆ ∈ (0, ∆ 0 ]. Assume that we are given a r.v. X, which takes discrete values a k = a + k∆, k ∈ {0, ±1, ±2, ...} , with maximal span ∆ and with a ∈ [0, ∆). In the sequel we shall impose conditions (D1-D2) below, where we assume that γ 0 , ..., γ 4 > 0 and σ > 1 denote real quantities not depending on values a k , k ∈ {0, ±1, ±2, ...} . For the sake of brevity we set

x k = a k /σ. D1 For any integer k satisfying |x k | ≤ γ 0 σ, P (X = a k ) = ∆ √ 2πσ exp - x 2 k 2 + θ 1 γ 1 2 x 3 k σ 1 + θ 2 γ 2 1 + |x k | σ .
D2 For any integers k, j satisfying |x k | ≤ γ 0 σ and (x k+j -x k )x k ≥ 0,

P (X = a k+j ) ≤ γ 3 ∆ σ exp - x 2 k 2 + γ 1 2 x 3 k σ -γ 4 (x k+j -x k )x k .
Lemma 2. Assume that conditions (D1-D2) are satisfied. Then, for any

x k satisfying |x k | ≤ c 0 σ, Φ x k -c 1 1 + x 2 k σ ≤ P (X ≤ a k ) ≤ Φ x k + c 1 1 + x 2 k σ ,
provided σ ≥ c 2 , where c 0 , c 1 and c 2 are constants depending only on γ 0 , ..., γ 4 and ∆ 0 .

Note that condition ∆ ∈ (0, ∆ 0 ] is used to assure the uniformity of the assertion of the lemma in ∆.

1 4. Komlós, J., Major, P. and Tusnády, G. An approximation of partial sums of independent rv's and the sample df. I Z. Wahrsch. verw. Gebiete, 32, (1975). p. 111-131. 5. Komlós, J., Major, P. and Tusnády, G. An approximation of partial sums of independent rv's and the sample df. II Z. Wahrsch. verw. Gebiete, 34 (1976). p. 33-58. 6. Sakhanenko, A. The rate of convergence in the invariance principle for non-identically distributed variables with exponential moments. Limit theorems for sums of random variables: Trudy Inst. Matem., Sibirsk. Otdel AN SSSR, Vol. 3 (1984). p. 3-49 (in Russian).

7. Zaitsev, A. Bounds for quantiles of smooth conditional distributions and multidimensional invariance principle. Sibirskii Matematicheskii Jurnal, 37 (1996). p. 807-831 (in Russian).

  . Brown, L., Carter, A., Low, M. and Zhang, C.-H. Equivalence theory for density estimation, Poisson precesses and Gaussian white noise with drift. Annals of statistics, 32 (2004) p. 2074-2097. 2. Carter, A. and Pollard, D. Tusnady's inequality revisited. Annals of statistics, 32 (2004) p. 2731-2741. 3. Grama I. and Nussbaum M. A nonstandard Hungarian construction for partial sums. Ann. I. H. Poincar -PR, 38, No. 6 (2002) p. 923-957.