Subdivision schemes are widely used for rapid curve or surface generation. Recent developments have produced various schemes, in particular non-linear, noninterpolatory or non-uniform.

To be used in compression, analysis or control of data, subdivision schemes should be incorporated in a multiresolution analysis that, mimicking wavelet analyses, provides a multi-scale decomposition of a signal, a curve, or a surface. The ingredients needed to define a multiresolution analysis associated with a subdivision scheme are decimation scheme and detail operators. Their construction is straightforward when the multiresolution scheme is interpolatory. This thesis is devoted to the construction of decimation schemes and detail operators compatible with general subdivision schemes. We start with a generic construction in the uniform (but not interpolatory) case and then generalize to nonuniform and non-linear situations. Applying these results, we build multiresolution analyses that are compatible with many recently developed schemes. Analysis of the performances of the constructed analyses is carried out. We present numerical applications in image compression. 1

where I had such a wonderful time which I would cherish for the whole rest of my life. I still remember the first time we met in your office, the first time we discuss in my office, how time flies, it's time to say, yeah, to say thank you, not goodbye yet. Thank you, for your great support and encourage morally and technically, for your patience, passion and immense knowledge. I would also like to thank Jean BACCOU for your great help, for helpful advices, your patience and careful guidance in detail. Especially for your work during the review of this manuscript. Remember the day we stuck in CMI with alarm roaring, all became good memories.

Thank you again, for the beautiful sunset we have experienced together.

f j = (f j k )
k∈Z data sequence at level j d j = (d j k ) k∈Z detail sequence at level j e j = (e j k ) k∈Z prediction error sequence at level j V j space of data sequences at level j W j space of detail sequences at level j M h , M h mask of subdivision h, decimation h δ j,0 Kronecker delta, δ j,0 = 1 if j = 0, 0 otherwise T t ( h) translation operator of parameter t applied to the decimation operator h, ( hk-t ) k∈Z

∆ 2 f k second order difference (f k+1 -f k ) -(f k -f k-1 )
H(x, y) harmonic mean H(x, y) =

) k =    u i , k = 2i + 1 v i , k = 2i T matrix of τ λ scaling operator (λf ) i = λ i f i , i ∈ Z, λ i ∈ R

Résumé

Les schémas de subdivision sont largement utilisés pour la génération rapide de courbes ou de surfaces. Des développements récents ont produit des schémas variés, en particulier non-linéaires, non-interpolants ou non-homogènes.

Pour pouvoir être utilisés en compression, analyse ou contrôle de données, ces schémas de subdivision doivent être incorporés dans une analyse multiresolution qui,

Présentation du travail en Français

La thèse est organisée en 4 parties.

La première fait une revue sur les schémas de subdivision et les analyses multiresolutions qui leur sont associées.

On présente en particulier les schémas classiques linéaires et homogènes (interpolants de Lagrange, splines) et le schéma PPH (piecewise polynomial harmonic) qui est un exemple de schéma non-linéaire (on s'intéresse en particulier à sa version non-interpolante). Le cadre général des analyses multiresolutions basé sur une prédiction par subdivision est détaillé ainsi que les propriétés souhaitables pour une telle structure.

La seconde partie présente une approche générique pour construire tous les schémas de décimation consistants avec un schéma de subdivision linéaire et homogène donné. Sa construction s'appuie d'abord sur une inversion matricielle qui conduit à des décimations consistantes dont le masque a une longueur minimale (décimations élémentaires) puis sur la génération de tous les schémas consistants en utilisant des combinaisons convexes de versions translatées des décimations élémentaires. On génère ainsi des opérateurs de décimations consistants avec de nombreux schémas dont certains pour lesquelles de tels opérateurs n'avaient jamais été proposés.

Le chapitre 3 constitue une généralisation du chapitre 2 à des schémas nonlinéaires ou non-homogènes. Dans le cas de schéma adapté à des segmentations de l'axe réel, une analyse locale permet de définir un opérateur de décimation agissant sur un intervalle fixé. Cet opérateur se couple avec un opérateur homogène construit suivant le chapitre précédent afin d'obtenir un schéma défini sur toute la droite et consistant avec la subdivision. Dans le cas de donnés localisées sur un intervalle, une construction global de décimation consistante est proposée. Elle s'appuie sur l'inversion d'une matrice obtenue à partir de la subdivision sur l'ensemble de l'intervalle. Enfin, pour des opérateurs généraux h (en particulier non-linéaire), une troisième approche est introduite. Elle consiste à supposer l'existence d'un opérateur hL linéaire qui est presque un inverse à gauche de h au sens où hL h -I est contractant. Dès que cet opérateur existe, il est alors possible de définir une décimation (non-linéaire) consistante. Sachant que de nombreux schémas non-linéaires (en particulier PPH) sont construits par perturbation d'un schéma linéaire h L , il est naturel de chercher parmi tous les schémas de décimation hL consistants avec h L ceux qui réalisent la contraction. Nous exhibons ainsi des décimations non-linéaires consistantes pour le schéma PPH non-interpolant.

Le chapitre 4 termine la construction des analyses multiresolutions avec l'introduction des opérateurs de détail. On génère ainsi une famille d'opérateurs (subdivision, décimation, détails) compatibles qui permettent de définir une analyse multiresolution. Les propriétés intéressantes des analyses multiresolutions, en vue de leur application en analyse/traitement de données sont la décroissance des détails et la stabilité. Pour ce qui est de la décroissance des détails(avec l'échelle j), une propriété essentielle est la reproduction des polynômes. Nous détaillons les conditions sur h et h pour avoir une telle propriété. Pour la stabilité de l'analyse multiresolution, la difficulté se concentre sur celle de l'opérateur de décimation. Dans le cas linéaire, nous montrons que la stabilité de l'opérateur de décimation correspond à la stabilité d'un opérateur de subdivision construit à partir des coefficients d'une puissance de l'opérateur de décimation. Le chapitre se termine par des exemples numériques et en particulier une estimation numérique des constantes de stabilité pour des schémas linéaire et non-linéaire dans le cadre de la compression d'images.

Une conclusion permet de mettre en évidence quelques perspectives de prolongement de la thèse. On évoque en particulier l'optimisation des opérateurs impliqués (subdivision linéaires, décimation consistante) et un résultat théorique sur la stabilité des opérateurs de décimation non-linéaire. La comparaison des performances des différentes analyses multiresolutions construites est aussi un champ qu'il convient d'explorer.

Chapitre 1. Etat de l'art et revue des principaux résultats

Ce chapitre effectue une revue sur les schémas de subdivision et les analyses multiresolutions qui leur sont associées. La Section 1.2 est dédiée aux schémas de subdivision avec leur définition et le rappel des notions de convergence et de stabilité.

Les exemples historiques de schémas (schémas de Chaikin, interpolant de Lagrange, spline) sont présentés ainsi que des schémas plus récents non-interpolants (Lagrange décalé, PPH décalé). Dans la Section 1.3 est introduit le cadre général des analyses multiresolutions. On commence par les opérateurs de décimation et la relation de consistance qui les lie aux opérateurs de subdivision. On introduit les opérateurs de détails et on définit la notion de compatibilité entre ces quatres opérateurs. Une présentation générale de la décroissance des détails en fonction de j est effectuée.

Cette section s'achève sur les notions de reproduction polynomiale et de stabilité.

Chapitre 2. Décimations linéaires consistantes avec un schéma de subdivision linéaire homogène

Après avoir traduit sur les masques la notion de consistance, on montre tout d'abord que pour un schéma de subdivision fixé, l'ensemble des schémas de décimation linéaires consistants est stable par les opérateurs de translation et de combinaison convexe. Ensuite on prouve que sous une hypothèse d'inversibilité d'une certaine matrice (proche mais généralement de taille plus petite que les matrices de raffinement définies dans [START_REF] Dyn | Subdivision schemes in computer aided geometric design[END_REF]), il existe un nombre fini de schémas de décimation consistants de longueur inférieure à un certain entier 2α lié à la longueur du masque du schéma de subdivision. On appelle ces schémas des schémas de décimation élémentaires. Enfin on démontre que tout schéma consistant s'exprime comme combinaison convexe de translatés de schémas de décimation élémentaires. La Section 2.3 est dédiée à des exemples d'application : on considère tout d'abord des schémas splines et interpolants de Lagrange. On s'intéresse aussi aux schémas de subdivision issus de la construction des ondelettes à support compact. Finalement, on traite le cas des schémas non-stationnaires de Lagrange pénalisés.

Chapitre 3. Schémas de décimations consistants avec des schémas de subdivision généraux

On s'intéresse ici à des schémas de subdivision non-homogènes ou non-linéaires.

Pour les schémas de subdivision non-homogènes, on suppose tout d'abord qu'une segmentation de l'axe réel permet de séparer des zones où le schéma est homogène et des zones, de taille réduite, où le schéma n'est pas homogène. Sur chaque zone non-homogène une analyse locale permet de définir, par inversion matricielle, un opérateur de décimation agissant sur toute la zone.

Conclusion

La conclusion met en particulier en évidence plusieurs propositions de prolongement de ce travail. L'étude théorique de la stabilité des analyses multiresolutions nonlinéaires est bien sûr à effectuer. Compte tenu du large choix et des différentes constructions proposées, un travail de comparaison entre les différentes analyses produites est à faire. 9

General Introduction

Subdivision schemes and multiresolution analyses are extensively investigated in different fields where they are applied for signal analyses, geometric modeling, compression, approximation or numerical analyses. Recent developments of general subdivision operators raise the question of systematical construction of associated multiresolution analysis: this question has to be addressed as soon as the subdivision scheme is non-linear and non-interpolatory. This thesis is devoted to provide some answers to this type of problem.

Background

The story of subdivision schemes started with De Rahm in [START_REF] De | Un peu de mathématiques à propos d'une courbe plane[END_REF], even if a relevant step forward was made by Chaikin [START_REF] Merrill | An algorithm for high-speed curve generation[END_REF] that proposed a method to generate curves.

After that, the extension from subdivision to surfaces and related topics was extensively investigated [START_REF] Catmull | Recursively generated b-spline surfaces on arbitrary topological meshes[END_REF][START_REF] Doo | Behaviour of recursive division surfaces near extraordinary points[END_REF]. After being developed during the following decades, it became popular around the beginning of this century.

Subdivision schemes [START_REF] Alfred S Cavaretta | Stationary subdivision[END_REF][START_REF] Dyn | Subdivision schemes in computer aided geometric design[END_REF] are powerful tools for the fast generation of refined sequences ultimately representing curves or surfaces. Especially subdivision surfaces are one of the most important methods used in Computer Graphics which could eventually replace NURBS in engineering CAD ( [START_REF] Sabin | Recent progress in subdivision: a survey[END_REF]).

Traditional research for subdivision scheme focusses on the construction of new schemes, and generally the properties of the generated curve or surface (smoothness,convexity,etc.) are essentially considered. Other related topics also attract many attention like analysis of new domains and new ranges, adding criteria for judging the quality of a scheme and other solution oriented new propositions.

Multiresolution subdivision has been applied to surface generation which is introduced in [START_REF] Catmull | Recursively generated b-spline surfaces on arbitrary topological meshes[END_REF]. Following a set of fixed refinement rules, each finer mesh is obtained from a coarse mesh by adding details at each level. Several constrained modelling techniques have been developed, such as a cut-and-paste editing technique for mul-tiresolution surfaces proposed in [START_REF] Biermann | Cutand-paste editing of multiresolution surfaces[END_REF], or in [START_REF] Henning Biermann | Sharp features on multiresolution subdivision surfaces[END_REF] a method for creating sharp features and trim regions on multiresolution subdivision surfaces along a set of user-defined curves has been introduced. Various forms of multiresolution subdivision surfaces can be also found in [START_REF] Lee | Displaced subdivision surfaces[END_REF][START_REF] Zorin | Interactive multiresolution mesh editing[END_REF].

Coupled with decimation schemes, a subdivision generates multi-scale transforms largely used in signal/image processing [START_REF] Amat | Analysis of a new nonlinear subdivision scheme. applications in image processing[END_REF][START_REF] Arandiga | Image compression based on a multi-directional map-dependent algorithm[END_REF] that generalize the multiresolution analysis/wavelet framework [START_REF] Daubechies | Ten lectures on wavelets[END_REF]. A decimation could be introduced as the reverse subdivision, for example by M. F. Hassan [START_REF] Mohamed | Reverse subdivision[END_REF], or it could be associated to the scale relation in multi-scale transform of multiresolution analysis.

Above all, the advantage of using subdivision schemes to construct multiresolutions relies on the flexibility of subdivision schemes (a subdivision scheme can be non-stationary, non-uniform, position-dependent, interpolating, approximating, non-linear...) (e.g. [START_REF] Arandiga | Image compression based on a multi-directional map-dependent algorithm[END_REF]). As a counterpart, the construction of suitable consistent decimation operators is not always straightforward. When subdivision schemes are uniform, interpolatory, linear and stationary, the decimation operators can be easily defined. However, more investigations should be done in the other situations. The treatment of such situations is the main motivation of this thesis.

Contributions

The main contributions of this thesis can be summarized as follows, 1. A generic approach is proposed for the construction of linear uniform consistent decimation operators for linear uniform subdivision schemes. Related properties are established;

2. Two generic approaches are proposed for the construction of linear consistent decimation for linear subdivision scheme which can be uniform or not;

3. A generic approach is proposed for the construction of consistent decimation for general subdivision scheme that can be linear or not; 4. A complete framework for multiresolution transform is defined introducing detail operators;

5. Analysis of the properties of the constructed multiresolutions is performed, including compatibility, stability, polynomial approximation and decay of detail/prediction error.

Structure of this thesis

This thesis is organized as follows, In chapter 2, a generic approach is proposed to construct all linear consistent decimation schemes associated to a given linear uniform subdivision scheme. The starting point of the method is the interpretation of the consistency property in terms of a condition on the subdivision and decimation masks. It leads to the construction of consistent elementary decimation operators that can be used to generate all the consistent decimation operators. Several examples are provided at the end of this chapter in the case of standard and non-standard schemes.

In chapter 3, we extend the construction to more general frameworks, including non-uniform and non-linear one. Starting from the uniform case, we show how the construction can be locally adapted to take into account the presence of segmentation points on the real line and guarantee the consistency of the decimation.

A second approach is then proposed to treat the specific case of the interval. It involves the inversion of a matrix constructed from the subdivision on the whole interval. Finally, a third approach is introduced to construct consistent decimations for general subdivision scheme including non linear ones. This method especially focusses on subdivisions that can be expressed as the sum of a linear part and a non-linear one. By establishing a fixed-point equation, a decimation operator can be calculated as soon as a contraction property is satisfied.

In chapter 4, the construction of the complete compatible multiresolution framework is addressed. Based on the couple of subdivision and consistent decimation provided by previous chapters, it is achieved by introducing a couple of compatible details operators (subdivision and decimation). The key point of this construction is that the prediction error belongs to the kernel of an associated linear decimation operator. A theoretical analysis of the properties of the multiresolution is also performed. At the end of the chapter, several numerical tests are conducted to evaluate the capabilities of some new subdivision-based multiresolutions in the framework of image compression.

13

Chapter 1

Overview

Introduction

This chapter provides an overview on the background of the thesis. We introduce many definitions and concepts required for the development of our works. This chapter is divided into two parts, the first part is devoted to subdivision schemes, while the multiresolution framework is introduced in the second part.

Subdivision Schemes

Definitions and Notations

A reference article on subdivision schemes has been published in 1991 [START_REF] Alfred S Cavaretta | Stationary subdivision[END_REF]. Another very nice paper [START_REF] Dyn | Subdivision schemes in computer aided geometric design[END_REF] was published one year later, and is devoted to curve and surface generation.

In this thesis we restrict ourself to binary subdivisions.

Definition 1.1 (Subdivision Schemes).

A univariate linear subdivision scheme h is defined through a real-valued sequence (h k ) k∈Z having a finite number of non-zero values such that h :

     l ∞ (Z) → l ∞ (Z) (f k ) k∈Z → ((hf ) k ) k∈Z with (hf ) k = l∈Z h k-2l f l . (1.1)
Any set of the form {h k :

k 0 ≤ k ≤ k 1 , k ∈ Z} containing all non-zero values of (h k ) k∈Z is called a mask of the operator h of length k 1 -k 0 + 1 and is denoted M h .
Moreover, we define the prediction stencil associated to (hf ) k as the set of indices

{l : h k-2l = 0}.
Subdivision is generally iterated starting from an initial sequence (f j 0 k ) k∈Z to generate (f j k ) k∈Z (j is a scale parameter) as

f j+1 = hf j , j ≥ j 0 . (1.2)
For all value of j, f j is associated to a dyadic grid X j = (k2 -j ) k∈Z .

In this context, the advantage of using subdivision for data prediction relies on the flexibility in the choice of the mask. The simplest strategy consists in considering the same mask for every position, scale and data f j (leading to linear uniform and stationary operators) [START_REF] Deslauriers | Symmetric iterative interpolation processes[END_REF].

Further situations can be considered by defining (h k ) k∈Z according to scale or position,

• a subdivision scheme h is said to be non-uniform if (h k ) k∈Z depends on the position l where it is applied [START_REF] Baccou | Position-dependent lagrange interpolating multiresolutions[END_REF],

• a subdivision scheme h is said to be non-stationary if (h k ) k∈Z depends on the level j [START_REF] Baccou | Kriging-based interpolatory subdivision schemes[END_REF].

A subdivision scheme can also be non-linear [START_REF] Cohen | Quasilinear subdivision schemes with applications to eno interpolation[END_REF] if the sequence (h k ) k∈Z nonlinearly depends on the sequence (f j l ) l∈Z .

Definition 1.2 (Convergence of Subdivision Schemes).

A subdivision scheme h is uniformly convergent if for all f 0 ∈ l ∞ (Z), there exists a

continuous function f ∈ C(R s ) such that lim j→∞ ||h j f 0 -f ( • 2 j )|| ∞ = 0, where f ( • 2 j ) denotes the sequence {f ( k 2 j ) : k ∈ Z s }. The function f is called the limit function of f 0 and is denoted by f ∞ = h ∞ f 0 .

Definition 1.3 (Stability of Subdivision Schemes).

A convergent subdivision scheme h is stable if there exists a constant

C ∈ R such that for all f, f ∈ l ∞ (Z), ∀i ∈ N, ||h i f -h i f || ∞ ≤ C||f -f || ∞ .
Note that if the subdivision h is linear, the stability (∃C ∈ R, ∀i ∈ N, ||h i || ≤ C) is a direct consequence of the convergence of the subdivision scheme.

The remaining of this section is devoted to several examples of subdivision schemes.

Classical 2-point Uniform Subdivision Schemes

A very popular subdivision scheme is the following 2-point scheme also known as corner cutting [START_REF] Dyn | Subdivision schemes in computer aided geometric design[END_REF]. It is defined as

     f j+1 2k = rf j k + (1 -r)f j k f j+1 2k+1 = sf j k + (1 -s)f j k+1
, where 0 ≤ s < r < 1 and corresponds to the mask

M h = {h -2 , h -1 , h 0 , h 1 } = {1 -r, 1 -s, r, s}.
This scheme is known to be uniformly convergent.

2-point Interpolatory Scheme

Taking r = 1 and s = 1 2 , we get the 2-point interpolatory subdivision scheme

       f j+1 2k = f j k f j+1 2k+1 = 1 2 f j k + 1 2 f j k+1
, corresponding to the mask

M h = {h -2 , h -1 , h 0 , h 1 } = {0, 1 2 , 1, 1 2 }.
Note that this scheme can also be considered as a particular Lagrange subdivision scheme (Example 1.2.5 with l = r = 1 and x l = 0, x r = 1/2) or a particular B-spline subdivision scheme (Example 1.2.4 with m = 2).

This scheme is uniformly convergent.

2-point Symmetrical Scheme

Taking r = 3 4 and s = 1 4 , we have the 2-point symmetrical subdivision scheme

       f j+1 2k = 3 4 f j k + 1 4 f j k+1 f j+1 2k+1 = 1 4 f j k + 3 4 f j k+1
corresponding to the mask

M h = {h -2 , h -1 , h 0 , h 1 } = { 1 4 , 3 4 , 3 4 , 1 4
}.

Note that this scheme can also be considered as a particular Lagrange subdivision scheme (Example 1.2.5 with l = r = 1 and x l = 1/4, x r = 3/4) or a particular B-spline subdivision scheme (Example 1.2.4 with m = 3).

This scheme is uniformly convergent.

Classical 4-point Interpolatory Subdivision Schemes

Another classical subdivision studied in [START_REF] Dyn | A 4-point interpolatory subdivision scheme for curve design[END_REF] is the 4-point centered interpolatory subdivision defined as

       f j+1 2k = f j k f j+1 2k+1 = -wf j k-1 + ( 1 2 + w)f j k + ( 1 2 + w)f j k+1 -wf j k+2
corresponding to the mask

M h = {h 3 , h 2 , h 1 , h 0 , h -1 , h -2 , h -3 , h -4 } = {-w, 0, 1 2 + w, 1, 1 2 + w, 0, -w, 0} .
This scheme is known to be uniformly convergent to C 0 limit functions if |w| < 1 4 , and uniformly convergent to C 1 limit functions if 0 < w < 1 8 .

B-spline Subdivision Schemes

B-splines 1 on specific grids are known to satisfy scaling relations that are the starting points to define related subdivision schemes [START_REF] Dyn | Subdivision schemes in computer aided geometric design[END_REF][START_REF] Battle | A block spin construction of ondelettes. Part I: Lemarié functions[END_REF].

The scaling relation satisfied by the B-spline basis functions of order m reads,

B m (t) = k h m k B m (2t -k),
which implies that any spline function

C(t) = k f j k B m (2 j t -k)
with control knots (f j k ) k∈Z , can also be written as

C(t) = k f j+1 k B m (2 j+1 t -k)
1 we call splines of order m (m ≥ 2) relatively to a grid {x k } k∈Z the space of functions f such

that f ∈ C m-2 and f | [x k ,x k+1 ] ∈ P m-1 .
with

f j+1 k = l h m k-2l f j k k ∈ Z . (1.3)
From the definition B m+1 (t) = t t-1 B m (τ )dτ and B 1 (t) = χ [0,1] with χ ω the characteristic function of the domain ω, it follows that the mask of the B-spline subdivision of order m is given by

h m k = 1 2 m-1 m k , k = 0, 1, . . . , m . (1.4)
Note that this mask is usually used with a translation of index.

The B-spline subdivision (1.3) is linear, uniform and converges to spline functions.

Lagrange Subdivision Schemes

Given two integers (l, r) ∈ N * 2 , for a given set of l + r distinct points, the Lagrange interpolating polynomial of a continuous function f is the unique polynomial of degree l+r-1 that coincides with the function at each point. Lagrange subdivision is defined by sampling the Lagrange interpolating polynomial related to dyadic points at specified positions.

If l (resp. r) stands for the number of points at the left (resp. right) side of the targeted interval, the elementary Lagrange polynomials read

∀i ∈ Z, -l + 1 ≤ i ≤ r, L i (x) = r m=-l+1, m =i x -m i -m .
Choosing two distinct points (x l , x r ) with x r -x l = 1 2 , a general Lagrange subdivision scheme h is written as

             f j+1 2k = r n=-l+1 L n (x l )f j k+n f j+1 2k+1 = r n=-l+1 L n (x r )f j k+n .
Its mask is given by

     h 2i = L -i (x l ) h 2i+1 = L -i (x r ) , ( 1.5)
which leads to

M h ={h -2r , h -2r+1 , h -2r+2 , h -2r+3 , . . . , h 2l-2 , h 2l-1 } ={L r (x l ), L r (x r ), L r-1 (x l ), L r-1 (x r ), . . . , L -l+1 (x l ), L -l+1 (x r )}.
In general, two types of Lagrange subdivision are interesting to study, the interpolatory Lagrange subdivision scheme that is obtained by setting x l = 0 and

x r = 1 2 , and the shifted Lagrange subdivision scheme that is obtained by setting x l = 1 4 and x r = 3 4 .

Interpolatory Lagrange subdivision is therefore defined as

   (hf ) 2k = f k (hf ) 2k+1 = r n=-l+1 L n ( 1 2 )f k+n , with    h 0 = 1 h 2i+1 = L -i (1/2), -r ≤ i ≤ l -1 .
Shifted Lagrange subdivision is defined as

   (hf ) 2k = r n=-l+1 L n ( 1 4 )f k+n (hf ) 2k+1 = r n=-l+1 L n ( 3 4 )f k+n , with    h 2i = L -i (1/4), -r ≤ i ≤ l -1 h 2i+1 = L -i (3/4), -r ≤ i ≤ l -1 .
A Lagrange subdivision is linear, uniform and convergent.

4-point Interpolatory Lagrange Scheme

Taking l = r = 2 and x l = 0, x r = 1/2, the centered 4-point interpolatory Lagrange subdivision scheme is written as

       f j+1 2k = f j k f j+1 2k+1 = - 1 16 f j k-1 + 9 16 f j k + 9 16 f j k+1 - 1 16 f j k+2 ,
and corresponds to the mask

M h = {h 3 , h 2 , h 1 , h 0 , h -1 , h -2 , h -3 , h -4 } = {- 1 16 , 0, 9 16 , 1, 9 16 , 0, - 1 16 , 0} . (1.6)
Note that the 4-point interpolatory Lagrange scheme is a special case of the 4-point interpolatory scheme of Example 1.2.5 corresponding to w = 1 16 . This scheme is convergent to C 1 limit functions.

4-point Shifted Lagrange Scheme

Taking l = r = 2 and x l = 1/4, x r = 3/4, the 4-point shifted Lagrange subdivision scheme is defined as

   f j+1 2k = -7 128 f j k-1 + 105 128 f j k + 35 128 f j k+1 -5 128 f j k+2 f j+1 2k+1 = -5 128 f j k-1 + 35 128 f j k + 105 128 f j k+1 -7 128 f j k+2 ,
and corresponds to the mask }.

M h = {h -4 , h -3 , h -2 , h -1 , h 0 , h 1 , h 2 , h 3 } (1.7) = {- 5 128 , - 7
According to [START_REF] Dyn | A c 2 four-point subdivision scheme with fourth order accuracy and its extensions[END_REF], this scheme is convergent and has smoothness C 2 .

PPH Subdivision Schemes

A full description of the original PPH scheme is available in [START_REF] Amat | Analysis of a new nonlinear subdivision scheme. applications in image processing[END_REF].

4-point Shifted PPH Scheme

A shifted PPH Subdivision has been derived in [START_REF] Amat | Analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms[END_REF]. It is a non-linear non-interpolatory subdivision scheme.

Rewriting the Lagrange polynomial as

P k (x) = L -1 (x)f j k-1 + L 0 (x)f j k + L 1 (x)f j k+1 + L 2 (x)f j k+2 + l k (x) -(∆ 2 f k + ∆ 2 f k+1 ) + 2( ∆ 2 f k + ∆ 2 f k+1 2 ) , (1.8) with ∆ 2 f k = (f j k+1 -f j k ) -(f j k -f j k-1 ),
the so-called PPH scheme is obtained by substituting arithmetic mean by harmonic mean in (1.8) as

F j+1 k (x) = L -1 (x)f j k-1 + L 0 (x)f j k + L 1 (x)f j k+1 + L 2 (x)f j k+2 + 2l k (x) H(∆ 2 f k , ∆ 2 f k+1 ) -A(∆ 2 f k , ∆ 2 f k+1 ) , with H(x, y) = xy x + y (sign(xy) + 1), A(x, y) = x + y 2 ,
and

sign(x, y) =    -1, if xy < 0 1, if xy ≥ 0 . Taking l k (x) =    L 2 (x), if |∆ 2 f k | ≤ |∆ 2 f k+1 | L -1 (x), if |∆ 2 f k | > |∆ 2 f k+1 | ,
and denoting

DHA k = H(∆ 2 f k , ∆ 2 f k+1 ) -A(∆ 2 f k , ∆ 2 f k+1 ),
with an evaluation at position x l = 1/4 and x r = 3/4, the 4-point shifted PPH subdivision scheme is defined as

   f j+1 2k = P k ( 1 4 ) + N k ( 1 4 ) f j+1 2k+1 = P k ( 3 4 ) + N k ( 3 4 )
, where .11) Note that the 4-point shifted PPH scheme can be considered as the linear 4-point shifted Lagrange scheme with a non-linear perturbation.

N k (x) =    2L 2 (x)DHA k , if |∆ 2 f k | ≤ |∆ 2 f k+1 | 2L -1 (x)DHA k , if |∆ 2 f k | > |∆ 2 f k+1 | . (1.9) More precisely, if |∆ 2 f k | ≤ |∆ 2 f k+1 |,    f j+1 2k = -7 128 f j k-1 + 105 128 f j k + 35 128 f j k+1 -5 128 f j k+2 -5 64 DHA k f j+1 2k+1 = -5 128 f j k-1 + 35 128 f j k + 105 128 f j k+1 -7 128 f j k+2 -7 64 DHA k , (1.10) if |∆ 2 f k | > |∆ 2 f k+1 |,    f j+1 2k = -7 128 f j k-1 + 105 128 f j k + 35 128 f j k+1 -5 128 f j k+2 -7 64 DHA k f j+1 2k+1 = -5 128 f j k-1 + 35 128 f j k + 105 128 f j k+1 -7 128 f j k+2 -5 64 DHA k . ( 1
In the following, we show that the 4-point shifted PPH scheme can also be considered as the linear 2-point shifted Lagrange scheme with a (different) nonlinear perturbation.

Rewriting (1.8) as

P k (x) =(2L -1 (x) + L 0 (x) -L 2 (x))f j k + (-L -1 (x) + L 1 (x) + 2L 2 (x))f j k+1 + (L 2 (x) -L -1 (x))∆ 2 f k+1 + L -1 (x) • 2( ∆ 2 f k + ∆ 2 f k+1 2 ), or P k (x) =(2L -1 + L 0 (x) -L 2 (x))f j k + (-L -1 (x) + L 1 (x) + 2L 2 (x))f j k+1 + (L -1 (x) -L 2 (x))∆ 2 f k + L 2 (x) • 2( ∆ 2 f k + ∆ 2 f k+1 2 ),
then a scheme involving 2 points in the linear part is obtained by substituting arithmetic mean by harmonic one,

F k (x) =(2L -1 + L 0 (x) -L 2 (x))f j k + (-L -1 (x) + L 1 (x) + 2L 2 (x))f j k+1 + (L 2 (x) -L -1 (x))∆ 2 f k+1 + L -1 (x) • 2H(∆ 2 f k , ∆ 2 f k+1 ),
or

F k (x) =(2L -1 + L 0 (x) -L 2 (x))f j k + (-L -1 (x) + L 1 (x) + 2L 2 (x))f j k+1 + (L -1 (x) -L 2 (x))∆ 2 f k + L 2 (x) • 2H(∆ 2 f k , ∆ 2 f k+1 ).
With the evaluation at position x l = 1/4 and x r = 3/4, the 4-point shifted PPH subdivision scheme can be also defined as

if |∆ 2 f k | ≥ |∆ 2 f k+1 |,    f j+1 2k = 3 4 f j k + 1 4 f j k+1 + 1 64 ∆ 2 f k+1 -7 64 H(∆ 2 f k , ∆ 2 f k+1 ) f j+1 2k+1 = 1 4 f j k + 3 4 f j k+1 -1 64 ∆ 2 f k+1 -5 64 H(∆ 2 f k , ∆ 2 f k+1 ) , if |∆ 2 f k | ≥ |∆ 2 f k+1 |,    f j+1 2k = 3 4 f j k + 1 4 f j k+1 -1 64 ∆ 2 f k -5 64 H(∆ 2 f k , ∆ 2 f k+1 ) f j+1 2k+1 = 1 4 f j k + 3 4 f j k+1 + 1 64 ∆ 2 f k -7 64 H(∆ 2 f k , ∆ 2 f k+1 )
.

Defining the function

R(x, y) =    y -H(x, y) if |x| ≥ |y| -x + H(x, y) if |x| < |y| ,
we finally have

   f j+1 2k = 3 4 f j k + 1 4 f j k+1 + 1 64 R(∆ 2 f k , ∆ 2 f k+1 ) -6 64 H(∆ 2 f k , ∆ 2 f k+1 ) f j+1 2k+1 = 1 4 f j k + 3 4 f j k+1 -1 64 R(∆ 2 f k , ∆ 2 f k+1 ) -6 64 H(∆ 2 f k , ∆ 2 f k+1 )
. (1.12)

4-point Interpolatory PPH Scheme

With an evaluation at position x l = 0 and x r = 1/2, the 4-point interpolatory PPH subdivision scheme is defined as

   f j+1 2k = f j k f j+1 2k+1 = -1 16 f j k-1 + 9 16 f j k + 9 16 f j k+1 -1 16 f j k+2 -1 8 DHA k . (1.13)
In a similar way, the 4-point interpolatory PPH subdivision scheme can be rewritten as the 2-point interpolatory Lagrange subdivision with a non-linear perturbation [START_REF] Amat | Nonlinear thresholding of multiresolution decompositions adapted to the presence of discontinuities[END_REF], The advantage of the PPH scheme is that it is able to avoid the Gibbs phenomenon [START_REF] Amat | On a nonlinear subdivision scheme avoiding gibbs oscillations and converging towards c s functions with s > 1[END_REF] in the vicinity of discontinuous points where oscillations are generated by applying the Lagrange scheme (Figure 1.1).

   f j+1 2k = f j k f j+1 2k+1 = 1 2 f j k + 1 2 f j k+1 -1 8 H(∆ 2 f k , ∆ 2 f k+1 ) . ( 1

Multiresolution Analysis

Decimation Schemes

A decimation operator can be interpreted as the left inverse of a subdivision operator. Similarly to the subdivision schemes, linear uniform decimation schemes are defined as follows,

Definition 1.4 (Decimation Schemes).

A univariate linear decimation scheme h is defined through a real-valued sequence ( hk ) k∈Z having a finite number of non zero values such that h :

     l ∞ (Z) → l ∞ (Z) (f k ) k∈Z → (( hf ) k ) k∈Z with ( hf ) k = l∈Z hl-2k f l .
Any set of the form { hk :

k 0 ≤ k ≤ k 1 , k ∈ Z} containing all non-zero values of ( hk ) k∈Z is called a mask of the operator h of length k 1 -k 0 + 1 and is denoted M h.
Mimicking the subdivision construction, a decimation scheme can be linear or non-linear, stationary or non-stationary, uniform or non-uniform etc.

Definition 1.5 (Stability of Decimation Schemes).

A decimation scheme h is stable if there exists a constant C ∈ R such that for all

f, f ∈ l ∞ (Z), ∀i ∈ N, || hi f -hi f || ∞ ≤ C||f -f || ∞ .
Subdivision and decimation are connected through a consistency property.

Definition 1.6 (Consistent Decimation).

A decimation operator h is said to be consistent with the subdivision scheme h if

hh = I (1.15)
where I stands for the identity operator.

Multiresolution Analysis Framework

Following the definition of Harten [START_REF] Harten | Multiresolution representation of data: A general framework[END_REF], a multiresolution analysis is characterized by the introduction of a family of separable spaces (V j ) j∈Z (j is a scale parameter)

and two families of decimation and prediction operators connecting two successive spaces V j and V j+1 .

These two operators can be constructed from previous decimation and subdi-

vision schemes. If f j ∈ V j is obtained after decimation ( h) of f j+1 ∈ V j+1 , hf j
does not usually coincide with f j+1 . In order to recover f j+1 after a decimation and a prediction, a sequence of prediction errors e j+1 = e j+1 k k∈Z is introduced and defined as:

e j+1 = (I -h h)f j+1 . (1.16) Introducing W j a complementary space of V j in V j+1 , i.e. V j+1 = V j ⊕ W j , if (g, g
) is a couple of operators such that gg = I W j , hg = 0 and gh = 0, we get

gf j+1 ∈ W j and f j+1 = h hf j+1 + ggf j+1 .
The operator g is called a detail subdivision operator and g a detail decimation operator.

A one-scale transform of the multi-scale analysis of Harten can be illustrated as follows,

f j f j+1 d j hf j + gd j || h g h g
The set of operators (h, h, g, g) verifies the exact reconstruction condition,

h h + gg = I. Definition 1.7.
The set of operators (h, h, g, g) is said to be compatible if and only if hh = I, gg = I, hg = 0, gh = 0.

Note that the consistency between subdivision and decimation is a necessary condition for compatibility.

Iterating this process and denoting j > j 0 , multi-scale decomposition and reconstruction transforms can be finally constructed as:

Decomposition : f j → {f j 0 , d j 0 , . . . , d j }, (1.17
)

f j f j-1 f j-2 d j-1 • • • d j-2 h h g g Reconstruction : {f j 0 , d j 0 , . . . , d j } → f j+1 . (1.18) f j 0 f j 0 +1 f j 0 +2 d j 0 • • • d j 0 +1 h h g g
These two transforms are of prime importance in data analysis and compression.

Subdivision-based multiresolution is an appealing framework for data analysis since it inherits the flexibility of the construction of subdivision operators. However, even if the operator h can be easily adapted according to the problem under study, the specification of the full multiresolution process (i.e. the operators h, g and g)

is more involved. For example, the construction of a decimation is still difficult to tackle for non-interpolatory schemes since, generally, a subsampling operator does not satisfy the consistency property. Moreover, the detail sequences can be obtained in the linear case by decomposing the prediction error on a basis of Ker( h) but this approach cannot be applied when h is not linear.

In this thesis, we propose some solutions to circumvent these difficulties.

Polynomial Approximation

The behavior of the prediction error is controlled by the polynomial (quasi) reproduction property which is recalled by the following definitions.

Let π n denote the space of polynomial of degree not larger than n ∈ N.

Definition 1.8 (Polynomial Quasi-reproduction).

An operator

U : l ∞ (Z) → l ∞ (Z) is said to quasi-reproduce polynomials up to degree L if ∀f ∈ π L (R), t i = (k2 -i ) k∈Z , ∃g ∈ π L (R), t j = (k2 -j ) k∈Z , s.t. U f (t i ) = g(t j ) . Definition 1.9 (Polynomial Reproduction). An operator U : l ∞ (Z) → l ∞ (Z) is said to reproduce polynomials up to degree L if ∀f ∈ π L (R), t i = (k2 -i ) k∈Z , ∃t j = (k2 -j ) k∈Z , s.t. U f (t i ) = f (t j ) .
The polynomial reproduction property is actually preserving exactly the sampled polynomial while the polynomial quasi-reproduction property is preserving the degree of the sampled polynomial. In the literature, polynomial quasi-reproduction is also called degree preserving [START_REF] Jetter | Polynomial reproduction in subdivision[END_REF] or polynomial generation [START_REF] Dyn | Polynomial reproduction by symmetric subdivision schemes[END_REF], and polynomial reproduction is also called polynomial preservation [START_REF] Levin | Polynomial generation and quasi-interpolation in stationary nonuniform subdivision[END_REF].

Note that all the schemes considered in this thesis are assumed to reproduce constants since it is a necessary condition for convergence.

Precisely, a scheme U is said to reproduce constants if

∀k ∈ Z, f = C =⇒ ∀k, (U f ) k = C.
It is easy to verify that a linear subdivision scheme reproduces constants if and

only if k∈Z h 2k = k∈Z h 2k+1 = 1 .
Similarly, a linear decimation scheme reproduces constants if and only if k∈Z hk = 1 .

Prediction Errors and Details

For applications in signal processing or approximation, the performance of the multiresolution process is controlled by the behavior of the prediction error with regards to the scale and more precisely by the amount of small prediction error values at each scale. Under some general conditions, the norm of the prediction error exponentially decays with the scale and this decay rate plays a key role in the sparsity of the multiresolution representation. This property is recalled in the following definition.

Definition 1.10 (Decay of the norm of the prediction error).

A prediction error e j is said to decay with a decay rate of p if and only if

||e j || ∞ ≤ C2 -pj ,
where C is a constant that does not depend on j.

Since e j = gd j , and g is usually chosen linear and continuous, in this case, the decay rate of the prediction error implies the same decay rate of the details.

Stability

A key point in practice is also the sensitivity of the multiresolution process to perturbations. It is related to the stability property of the decomposition and reconstruction transforms that is recalled in the next definition.

Definition 1.11 (Stability of the multiresolution).

The reconstruction transform is said to be stable with regards to the norm || . || ∞ if there exists a constant C such that for all {f j 0 , d j 0 , ..., d j-1 } and {f j 0 , d j 0 , ..., d j-1 },

||f j -f j || ∞ ≤ C   ||f j 0 -f j 0 || ∞ + j-1 i=j 0 ||d i -d i || ∞   , ( 1.19)
where {f j 0 , d j 0 , ..., d j-1 } and {f j 0 , d j 0 , ..., d j-1 } stand for the decomposition of f j and f j .

The decomposition transform is said to be stable with regards to the norm || . || ∞ if there exists a constant C such that for all (f j , f j ),

||f j 0 -f j 0 || ∞ + j-1 i=j 0 ||d i -d i || ∞ ≤ C||f j -f j || ∞ , (1.20)
where {f j 0 , d j 0 , ..., d j-1 } and {f j 0 , d j 0 , ..., d j-1 } stand for the decomposition of f j and f j .

The multiresolution is said to be stable if the associated decomposition transform and reconstruction transform are stable.

In the linear case, the stability of the multiresolution is guaranteed as soon as the subdivision and decimation are stable. In the non-linear case, the stability of the multiresolution is not easy to deduce. A condition for the stability of the subdivision scheme and also of the reconstruction was given in [START_REF] Amat | Analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms[END_REF]. It is recalled as follows,

Proposition 1.1.

Let h = h L + h N be a non-linear subdivision scheme with h L denoting the linear part and h N a non-linear perturbation, if there exists M > 0 and c < 1 such that for all

f, f ∈ l ∞ (Z), ||h N f -h N f || ∞ ≤ M ||f -f || ∞ , ||δ(hf -hf )|| ∞ ≤ c||δ(f -f )|| ∞ ,
where δ is a linear operator defined by h N • = F (δ•), then the subdivision scheme h is stable and the associated reconstruction is stable.

Conclusion

The subdivision framework leads to a large family of subdivision operators thanks to the flexibility in the construction of the mask. This is not the case when considering wavelet multiresolution analysis, since the prediction and the decimation 29 are fixed once scaling functions and wavelets are specified. However, for a given subdivision scheme, the construction of a decimation mask leading to a family of consistent decimation operators is more involved and the complete construction of compatible and stable operators (h, h, g, g) is difficult. These topics are addressed in the following chapters. We start in Chapter 2 with an original method to generate consistent decimation operators associated to a fixed subdivision.

Chapter 2 Consistent Decimations for

Uniform Linear Subdivision Schemes

Introduction

This chapter deals with the construction of decimation operators associated to linear uniform subdivision schemes.

Exploiting the consistency condition and the uniform property, a generic approach is introduced following two steps that are fully described in Section 2.2. A special attention is also given to the connection between the matrix involved in this construction and the so-called refinement matrices involved in the analysis of subdivision schemes [START_REF] Dyn | Subdivision schemes in computer aided geometric design[END_REF]. Finally, several examples of decimation construction for standard and non-standard subdivision schemes are provided in Section 2.3.

Most of the content of this chapter has been presented at the 9th International

Conference on Mathematical Methods for Curves and Surfaces in Norway and published in Lecture notes in computer sciences [START_REF] Kui | On the coupling of decimation operator with subdivision schemes for multi-scale analysis[END_REF].

Generic Approach

Consistency Condition

The consistency property (1.15) can be reformulated as a condition satisfied by the masks of the subdivision and decimation operators. It is given by the following proposition, Proposition 2.1.

Let h be a linear subdivision operator with mask

(h k ) k∈Z i.e. ∀j, ∀ f j l l∈Z , hf j k = l∈Z h k-2l f j l . (2.1)
Let h be a linear decimation operator with mask ( hk

) k∈Z i.e. ∀j, ∀ f j+1 l l∈Z , hf j+1 l = k∈Z hk-2l f j+1 k . ( 2

.2)

Then h and h satisfy the consistency relation (1.15) if and only if

∀j ∈ Z, i∈Z h i hi+2j = δ j,0 . (2.3)
where δ j,0 is the Kronecker delta.

Proof.

According to (2.1) and (2.2), the consistency condition (1.15

) implies that ∀ (f j m ) m∈Z , ∀m ∈ Z, f j m = k∈Z hk-2m l∈Z h k-2l f j l = l∈Z ( k∈Z hk-2m h k-2l )f j l which is equivalent to ∀m ∈ Z, k∈Z hk-2m h k-2l = δ m,l
that leads to (2.3).

Remark 2.1.

The proof of Proposition 2.1 can be also performed using Laurent polynomials. It is given in Appendix A.

Corollary 2.1.

Given a couple of subdivision and consistent decimation schemes, if the subdivision scheme reproduces constants, according to the consistency equation ( 2.3), the decimation scheme also reproduces constants.

Notations and Properties

We first introduce the shifted decimation operator defined below,

Definition 2.1 (Shifted Decimation Operator).

If h is a decimation operator constructed from the sequence ( hk ) k∈Z , for t ∈ Z, we denote T t ( h) the decimation operator related to the sequence ( hk-t ) k∈Z .

Using this shifted operator, it is then possible to generate new consistent decimation operators from existing ones by linear combination. Indeed we have,

Lemma 2.1.

Let h be a subdivision operator constructed from the sequence (h k ) k∈Z ,

if h and h are two decimation operators consistent with h and constructed

from the sequences ( hk ) k∈Z and ( h k ) k∈Z , then

∀λ ∈ R, λ h + (1 -λ) h is consistent with h.

if h, h and h are three decimation operators consistent with h and constructed

from the sequences ( hk

) k∈Z , ( h k ) k∈Z and ( h k ) k∈Z , then ∀λ ∈ R, ∀t ∈ Z, h + λT 2t ( h ) -λT 2t ( h )
is consistent with h.

Proof.

With the consistency condition (1.15), it is easy to verify

1. ∀λ ∈ R, k h k+2j (λ h + (1 -λ) h ) k =λ k h k+2j hk + (1 -λ) k h k+2j h k =λδ j,0 + (1 -λ)δ j,0 =δ j,0 . 2. ∀λ ∈ R, ∀t ∈ Z, k h k+2j ( h + λT 2t ( h ) -λT 2t ( h )) k = k h k+2j ( hk + λ h k-2t -λ h k-2t ) =δ j,0 + λδ j+t,0 -λδ j+t,0 =δ j,0 .
As a result, a general construction of consistent decimations is straightforward and provided by the next proposition.

Proposition 2.2.

Let h be a given subdivision operator, denote { hi } i∈I a set of decimation operators which are consistent with h, then a general consistent decimation operator can be constructed as

t∈T i∈I c i,t T 2t ( hi ) (2.4) with ∀t ∈ T , i∈I c i,t = δ t,0 , 0 ∈ T ⊂ Z . Remark 2.2.
Note that different coefficients c i,t may lead to the same operator.

In the next section, we develop a method to construct a specific set of decimation operators consistent with a given subdivision scheme. Then we show that (2.4) can be used to derive, from this set, all consistent decimation operators from this set.

Elementary Decimation Operators

The starting point of the method is the consistency relation (2.3) and its reformulation as a vectorial equation. Since M h and M h can be of different lengths, several situations have to be considered to describe the generic method. They are fully specified in the following, Theorem 1.

Let h be a subdivision operator with mask

M h = {h n-2α , h n-2α+1 , . . . , h n , h n+1 } of length 2(α + 1) with h n-2α h n+1 = 0 or of length 2α + 1 with h n-2α = 0 and h n-2α+1 h n+1 = 0.
Denote H M h the following matrix,

H M h =                   h n h n-2 • • • h n-2α 0 • • • 0 h n+1 h n-1 • • • h n-2α+1 0 • • • 0 0 h n h n-2 • • • h n-2α • • • 0 0 h n+1 h n-1 • • • h n-2α+1 • • • 0 . . . . . . 0 0 • • • h n h n-2 • • • h n-2α 0 0 • • • h n+1 h n-1 • • • h n-2α+1                  
.

If det(H M h ) = 0, there exists 2α consistent decimation operators which masks are of length not larger than 2α.

These masks are given by each row of

H -1 M h . Proof.
First, let us assume that M h is of even length (h n-2α h n+1 = 0) and denote formally for any integer m ∈ Z,

M h = { hn-m , hn-m+1 , . . . , hn-m+2α-2 , hn-m+2α-1 },
the mask of a consistent decimation operator of length not larger than 2α. Here the parameter n controls the centering of the mask M h . The parameter m is related to the shift between the masks M h and M h.

If h is consistent with h then the consistency condition (2.3) is verified. It can be written as

[ hn-m , hn-m+1 , . . . , hn-m+2α-2 , hn-m+2α-1 ]             h n-m-2j h n-m+1-2j . . . h n-m+2α-2-2j h n-m+2α-1-2j             = δ j,0 . (2.5)
To ensure that (2.5) makes sense with a given M h , we should have

{h n-m-2j , h n-m+1-2j , . . . , h n-m+2α-1-2j } {h n-2α , h n-2α+1 , . . . , h n+1 } = ∅, which means    n -m + 2α -1 -2j ≥ n -2α n -m -2j ≤ n + 1 .
and leads to

- m + 1 2 ≤ j ≤ - m + 1 2 + 2α .
When m is odd, (2.5) corresponds to 2α+1 linear equations for j ∈ {-m+1 2 , . . . ,

-m+1 2 + 2α} including hn-m h n+1 = δ m,-1 for j = m + 1 2 and hn-m+2α-1 h n-2α = δ m,4α-1 for j = m + 1 2 + 2α.
Since h n+1 h n-2α = 0, it necessarily leads to hn-m hn-m+2α-1 = 0. If hn-m = 0, then Therefore, m can always be considered as even without losing generality. Since m is even, (2.5) leads to 2α linear equations for j ∈ {-m 2 , -m 2 + 1, . . . , -m 2 + 2α -1} that can be written as

M h is equivalent to { hn-m , hn-m +1 , . . . , hn-m +2α-2 , hn-m +2α-1 }
[ hn-m , hn-m+1 , . . . , hn-m+2α-2 , hn-m+2α-1 ]H M h = [δ m,0 , δ m-2,0 , . . . , δ m-4α+2,0 ]
with

H M h =                   h n h n-2 • • • h n-2α 0 • • • 0 h n+1 h n-1 • • • h n-2α+1 0 • • • 0 0 h n h n-2 • • • h n-2α • • • 0 0 h n+1 h n-1 • • • h n-2α+1 • • • 0 . . . . . . 0 0 • • • h n h n-2 • • • h n-2α 0 0 • • • h n+1 h n-1 • • • h n-2α+1                  
, where the column index corresponds to parameter j.

For m ∈ {0, 2, . . . , 4α -4, 4α -2}, equation (2.5) can be written as

HM h H M h = I 2α with HM h =             M h0 M h2 . . . M h4α-4 M h4α-2             =             h0 n h0 n+1 • • • h0 n+2α-1 h2 n-2 h2 n-1 • • • h2 n+2α-3 . . . . . . h4α-4 n-4α+4 h4α-4 n-4α+5 • • • h4α-4 n-2α+3 h4α-2 n-4α+2 h4α-2 n-4α+3 • • • h4α-2 n-2α+1            
.

Each row of HM h corresponds to a value of m and to a consistent decimation operator. Note that, specifically for the decimation operators defined above, the superscript k for hk controls the shift between M h and M hk . Since det(H M h ) = 0, HM h = H -1 M h , that concludes the proof when M h is of even length. In the case of subdivision mask of odd length, the same proof can be conducted assuming h n-2α = 0 and the same matrix HM h can be deduced if det(H M h ) = 0.

The decimation operators obtained in Theorem 1 are called elementary decimation operators.

If the subdivision mask is of odd length, it can be proved that the last row of HM h can be obtained by a linear combination of translated versions of the decimation masks associated to the other rows. It is therefore enough to focus on the 2α -1 elementary decimation operators. This important result is stated by the next proposition, Proposition 2.3.

Let h be a prediction operator constructed from the mask

M h = {h n-2α+1 , h n-2α+2 , . . . , h n , h n+1 } of length 2α + 1, α ≥ 2 with h n-2α+1 h n+1 = 0.
We note H M h the following matrix

H M h =                h n h n-2 • • • 0 0 • • • 0 h n+1 h n-1 • • • h n-2α+1 0 • • • 0 0 h n h n-2 • • • 0 • • • 0 0 h n+1 h n-1 • • • h n-2α+1 • • • 0 . . . . . . 0 0 • • • h n h n-2 • • • h n-2α+2               
.

If det(H M h ) = 0, there exists 2α -1 consistent elementary decimation operators which masks are of length not larger than 2α -1 . These masks are given by each

row of H -1 M h . Proof.
Following Proposition 1, we construct a similar matrix with h n-2α = 0

H M h =                   h n h n-2 • • • 0 0 • • • 0 h n+1 h n-1 • • • h n-2α+1 0 • • • 0 0 h n h n-2 • • • 0 • • • 0 0 h n+1 h n-1 • • • h n-2α+1 • • • 0 . . . . . . 0 0 • • • h n h n-2 • • • 0 0 0 • • • h n+1 h n-1 • • • h n-2α+1                  
.

Since h n-2α+1 = 0 and det(H M h ) = 0, we have det(H M h ) = 0 and we can introduce

HM h =             M h0 M h2 . . . M h4α-4 M h4α-2             =             h0 n h0 n+1 • • • h0 n+2α-2 0 h2 n-2 h2 n-1 • • • h2 n+2α-4 0 . . . . . . . . . h4α-4 n-4α+4 h4α-4 n-4α+5 • • • h4α-4 n-2α+2 0 h4α-2 n-4α+2 h4α-2 n-4α+3 • • • h4α-2 n-2α h4α-2 n-2α+1             with HM h = H -1 M h .
Note that the last row of HM h denoted M h4α-2 is the only mask with a non-zero last term. Therefore h4α-2 n-2α+1 = 0 according to the consistency condition. In the sequel, we show that the last row of HM h can be obtained by linear combinations of the translated versions of the above ones.

First, note that the set

{ h0 n+2α-2 , h2 n+2α-4 , . . . , h4α-6 n-2α+4 }
has at least one non-zero term, otherwise, according to the consistency condition, all terms in

{ h0 n+2α-3 , h2 n+2α-5 , . . . , h4α-6 n-2α+3 } would be also zero which implies det( HM h ) = 0. So there exists h4α-4-2t n-2α+2+2t = 0 for t ∈ {1, 2, . . . , 2α -2}. Introducing λ = h4α-4 n-2α+2 / h4α-4-2t n-2α+2+2t , we note h * = h4α-4 + λT -2t ( h4α-2-2t ) -λT -2t ( h4α-4-2t )
which can have non-zero value from index n -4α + 2 to n -2α + 2. Calculating the last term gives

h * n-2α+2 = h4α-4 n-2α+2 + λ h4α-2-2t n-2α+2+2t -λ h4α-4-2t n-2α+2+2t = 0 .
It means that h * can have non-zero value from index n -4α + 2 to n -2α + 1.

Since det(H M h ) = 0, h4α-2 is the unique consistent operator with a mask of length not larger than 2α and admitting non-zero values from index n -4α + 2 to n -2α + 1. It therefore implies that h * = h4α-2 .

Thus, eliminating the last row and column of H M h , we construct the matrix

H M h =                h n h n-2 • • • 0 0 • • • 0 h n+1 h n-1 • • • h n-2α+1 0 • • • 0 0 h n h n-2 • • • 0 • • • 0 0 h n+1 h n-1 • • • h n-2α+1 • • • 0 . . . . . . 0 0 • • • h n h n-2 • • • h n-2α+2               
.

Since det(H M h ) = 0, we then get elementary consistent decimation operator masks by considering the rows of H

M h = H -1 M h . By construction, H M h is a (2α -1) × (2α -1) sub-matrix of H M h , H M h =   H M h 0 U h n-2α+1   with U = [0, . . . , 0, h n+1 , h n-1 , . . . , h n-2α-1 ].
According to the blockwise inversion of a matrix,

  A B C D   -1 =   A -1 + A -1 B(D -CA -1 B) -1 CA -1 -A -1 B(D -CA -1 B) -1 -(D -CA -1 B) -1 CA -1 (D -CA -1 B) -1   ,
we have

HM h = H -1 M h =   H M h 0 -h -1 n-2α+1 U H M h h -1 n-2α+1   which means that H M h in Proposition 2.3 is a (2α -1) × (2α -1) sub-matrix of HM h introduced in Theorem 1.
So far, a generic method was proposed to construct a set of consistent decimation operators. It remains to show that it can be used to generate all the consistent decimation operators, which is achieved in the next section by exploiting formula (2.4).

Completeness of Generic Approach

In this section, we prove that the approach of Theorem 1 combined with Proposition 2.2 generates all the consistent decimation operator of any length.

More precisely, we have the following proposition that shows how all consistent decimation operators can be recovered using linear combinations of translated versions of elementary operators. Proposition 2.4.

Given a subdivision scheme h satisfying the hypotheses of Theorem 1, combining elementary decimation operators with formula (2.4) generates all the consistent decimation operators.

Proof.

Let's first consider M h = {h n-2α , h n-2α+1 , . . . , h n , h n+1 } the mask of a given operator h of length 2(α+1) with h n-2α h n+1 = 0. Then, Proposition 1 provides 2α consistent elementary decimation operators of length 2α which can be denoted as

M h2i = { h2i n-2i , h2i n-2i+1 , . . . , h2i n-2i+2α-2 , h2i n-2i+2α-1 } with i = 0, 1, 2, . . . , 2α -1.
Let M h = { hm-2β , hm-2β+1 , . . . , hm , hm+1 } be the mask of an arbitrary decimation operator h consistent with h. The length of M h, 2β +2, is supposed to be larger than 2α that is to say β > α -1 , otherwise h is an elementary operator itself and the proof is completed. Moreover, m in M h is always chosen to ensure n -m even by assuming that hm-2β and hm+1 can be zero. However, { hm-2β , hm-2β+1 } = {0, 0} and { hm , hm+1 } = {0, 0} are always guaranteed.

The consistency of h and h implies directly

n -2α -1 < m < n + 2β + 1.
The aim is to prove that h can be represented as a linear combination of translated version of ( h2i ) 0≤i≤2α-1 .

This will be achieved in two steps. The first step consists in writing h as the sum of a term involving some h2i or its translated versions and of another one denoted h * that is a consistent decimation operator with a shorter mask than M h. The second step is an iteration of this process until h * is an elementary decimation operator.

We restrict the proof to the first step since the second one is straightforward.

The starting point is the consistency condition (2.3). Considering j = m-n 2 -β and j = m-n 2 + α, it leads to

h n hm-2β + h n+1 hm-2β+1 = δm-n 2 -β,0 , (2.6) h n-2α hm + h n-2α+1 hm+1 = δm-n 2 +α,0 . (2.7)
According to α and β, at least one of the two above RHS term is equal to zero. Let us suppose that the RHS of (2.6) is zero, i.e.

h n hm-2β + h n+1 hm-2β+1 = 0. (2.

8)

Since h n+1 = 0, we cannot have h2i n-2i = 0 for all i ∈ {1, 2, . . . , 2α -1} according to the consistency condition.

Let us introduce the two following operators with a mask of length 2α with h m-2β = 0,

M h = { h m-2β , h m-2β+1 , . . . , h 2α-2β+m-2 , h 2α-2β+m-1 } = T m-2β-n+2i ( h2i ), M h = { h m-2β+2 , h m-2β+3 , . . . , h 2α-2β+m , h 2α-2β+m+1 } = T m-2β-n+2i ( h2i-2 )
which are elementary operators with the same translation. The consistency condition implies

h n h m-2β + h n+1 h m-2β+1 = 0. (2.9)
Considering (2.8) and (2.9), hm-2β = 0 leads to hm-2β+1 = 0 which is not allowed. Moreover, hm-2β+1 = 0 implies h n = 0 and then h m-2β+1 = 0. Therefore there exists λ ∈ R/{0} such that The above process actually eliminates the first two terms hm-2β , hm-2β+1 of M h using elementary decimation operators. If we suppose that the RHS of (2.7) is zero, a symmetrical similar process can be performed and the last two terms hm , hm+1 of M h will be eliminated.

λ[ h m-2β , h m-2β+1 ] = [ hm-2β , hm-2β+1 ] . ( 2
To complete the proof in the case of subdivision mask of odd length, we suppose

h n+1 = 0 in (2.8
) and (2.9). It is straightforward that hm-2β = 0, hm-2β+1 = 0 and then h m-2β = 0. Moreover, introducing M h and M h with h m-2β = 0 and h m-2β+1 = 0, there exists λ = 0 verifying (2.10).

Refinement Matrices

In this section, we explore the relation between the refinement matrices A 0 , A 1 introduced in [START_REF] Dyn | Subdivision schemes in computer aided geometric design[END_REF] and the subdivision matrices

H M h , H M h introduced in Theorem
1 and Proposition 2.3.

For a subdivision h with a mask of length 2α + 2

M h = {h n-2α , h n-2α+1 , . . . , h n , h n+1 } if h n-2α h n+1 = 0
, the refinement matrices of dimension (2α + 1) × (2α + 1) are written as

A 0 =                      h n h n-2 • • • h n-2α 0 • • • 0 0 h n+1 h n-1 • • • h n-2α+1 0 • • • 0 0 0 h n h n-2 • • • h n-2α • • • 0 0 0 h n+1 h n-1 • • • h n-2α+1 • • • 0 0 . . . . . . 0 0 • • • h n h n-2 • • • h n-2α 0 0 0 • • • h n+1 h n-1 • • • h n-2α+1 0 0 0 0 0 h n h n-2 • • • h n-2α                      A 1 =                      h n+1 h n-1 • • • h n-2α+1 0 • • • 0 0 0 h n h n-2 • • • h n-2α • • • 0 0 0 h n+1 h n-1 • • • h n-2α+1 • • • 0 0 . . . . . . 0 0 • • • h n h n-2 • • • h n-2α 0 0 0 • • • h n+1 h n-1 • • • h n-2α+1 0 0 0 0 0 h n h n-2 • • • h n-2α 0 0 0 0 h n+1 h n-1 • • • h n-2α+1                     
if h n-2α = 0, the refinement matrices of dimension 2α × 2α are written as

A 0 =                   h n h n-2 • • • 0 0 • • • 0 h n+1 h n-1 • • • h n-2α+1 0 • • • 0 0 h n h n-2 • • • 0 • • • 0 0 h n+1 h n-1 • • • h n-2α+1 • • • 0 . . . . . . 0 0 • • • h n h n-2 • • • 0 0 0 • • • h n+1 h n-1 • • • h n-2α+1                   A 1 =                   h n+1 h n-1 • • • h n-2α+1 0 • • • 0 0 h n h n-2 • • • 0 • • • 0 0 h n+1 h n-1 • • • h n-2α+1 • • • 0 . . . . . . 0 0 • • • h n h n-2 • • • 0 0 0 • • • h n+1 h n-1 • • • h n-2α+1 0 0 • • • 0 h n • • • h n-2α+2                  
if h n+1 = 0, a similar form is easy to be deduced.

It is then straightforward that the subdivision matrix H M h (H M h for masks of odd length) is sub-matrix of refinement matrices.

Exploiting the structure of the refinement matrices, the following results hold.

Proposition 2.5.

All the consistent elementary decimation operators can be deduced by inverting one of the refinement matrix. Moreover, the eigenvalues of each refinement matrix are the eigenvalues of the subdivision matrix H M h (H M h for mask of odd length) plus

the first or last non-zero values of the subdivision mask.

Proof.

Consider the case h n-2α = 0, then

A 0 =   H M h 0 U h n-2α   .
Applying the blockwise inversion of matrix A 0 ,

A -1 0 =   H -1 M h 0 -h -1 n-2α U H -1 M h h -1 n-2α  
and all elementary decimation operators are included in A -1 0 .

Moreover, starting from A 0 , it is straightforward that the eigenvalues of H M h are also the eigenvalues of A 0 and that h n-2α is the eigenvalue of A 0 associated to the eigenvector 0 1 . The proof is achieved by considering all other cases in the same way.

Examples and Applications

We here apply the generic method described in the previous section to construct decimation operators consistent with several subdivision schemes. Depending on the scheme, our method allows to revisit the classical decimation construction, but also provides original ones in situations where there were, up to now, no available decimation (shifted Lagrange, penalized Lagrange, for example). It is a first step in the definition of new multiresolution analyses.

2-point Scheme

A general 2-point uniform scheme is given by the mask

M h = {h -2 , h -1 , h 0 , h 1 } = {1 -r, 1 -s, r, s}.
Since r = s, Theorem 1 can be applied with

H M h =   h 0 h -2 h 1 h -1   =   r 1 -r s 1 -s   .
We get 2 consistent elementary decimation operators defined by

HM h = H -1 M h =   h0 0 h0 1 h2 -2 h2 -1   =   1-s r-s -1-r r-s -s r-s r r-s  

2-point Interpolatory Scheme

By taking r = 1 and s = 1 2 , we get the 2-point interpolatory Lagrange subdivision or B-spline of order 2.

The 2 consistent elementary decimation operators are obtained by

HM h = H -1 M h =   h0 0 h0 1 h2 -2 h2 -1   =   1 0 -1 2   .
Note that the decimation h0 represents a sub-sampling and h2 represents an extrapolation which could also be applied in a symmetrical direction.

2-point Symmetrical Scheme

By taking r = 3 4 and s = 1 4 , we get the 2-point shifted Lagrange subdivision or B-spline of order 3.

The 2 consistent elementary decimation operators are obtained by

HM h = H -1 M h =   h0 0 h0 1 h2 -2 h2 -1   =   3 2 -1 2 -1 2 3 2   .
According to formula (2.4), another consistent decimation can be constructed as follows with λ ∈ R,

[ h-2 h-1 h0 h1 ] = λ[0 0 h0 0 h0 1 ] + (1 -λ)[ h2 -2 h2 -1 0 0] = [-1 2 (1 -λ) 3 2 (1 -λ) 3 2 λ -1 2 λ]
.

Taking λ = 1/2, we get the symmetrical operator

[ h-2 h-1 h0 h1 ] = [- 1 4 , 3 4 , 3 4 , - 1 4 ].
(2.11) Following (2.4), a consistent decimation operator

M h = [ 1 16 , - 3
can be constructed as

h = 1 2 h2 + 1 2 h0 - 1 8 T -2 ( h2 ) + 1 8 T -2 ( h0 ) + 1 8 T 2 ( h2 ) - 1 8 T 2 ( h0 ).
Moreover, the decimation proposed in [START_REF] Cohen | Biorthogonal bases of compactly supported wavelets[END_REF],

M h = [ 3 64 , - 9
can be constructed by formula (2.4) as

h = 1 2 h2 + 1 2 h0 - 3 32 T -2 ( h2 ) + 3 32 T -2 ( h0 ) + 3 32 T 2 ( h2 ) - 3 32 T 2 ( h0 ).
Remark 2.3.

The refinement matrix associated to this 2-point symmetrical subdivision is

A =      3 4 1 4 0 1 4 3 4 0 0 3 4 1 4      .
By inverting A, we can recover the two elementary operators from the first two rows,

A -1 =      M h0 M h2 M h4      =      h0 0 h0 1 h0 2 h2 -2 h2 -1 h2 0 h4 -4 h4 -3 h4 -2      =      3 2 -1 2 0 -1 2 3 2 0 3 2 -9 2 4     
and not surprisingly, the third row can be deduced by combining the first two rows, h4 = 3T -2 ( h0 ) -3T -2 ( h2 ) + h2 .

Lagrange Subdivision Scheme 4-point Interpolatory Lagrange Scheme

The centred 4-point interpolatory Lagrange subdivision scheme corresponds to the mask

M h = {h 3 , h 2 , h 1 , h 0 , h -1 , h -2 , h -3 , h -4 } = {- 1 16 , 0, 9 16 , 1, 9 16 , 0, - 1 16
, 0} .

Applying Theorem 1, since -

H M h =                h 2 h 0 h -2 h -4 0 0 h 3 h 1 h -1 h -3 0 0 0 h 2 h 0 h -2 h -4 0 0 h 3 h 1 h -1 h -3 0 0 0 h 2 h 0 h -2 h -4 0 0 h 3 h 1 h -1 h -3                =                0 1 0 0 0 0 -1 16
1 16                ,
6 consistent elementary decimation operators are obtained by

HM h = H -1 M h =                h0 2 h0 3 h0 4 h0 5 h0 6 h0 7 h2 0 h2 1 h2 2 h2 3 h2 4 h2 5 h4 -2 h4 -1 h4 0 h4 1 h4 2 h4 3 h6 -4 h6 -3 h6 -2 h6 -1 h6 0 h6 1 h8 -6 h8 -5 h8 -4 h8 -3 h8 -2 h8 -1 h10 -8 h10 -7 h10 -6 h10 -5 h10 -4 h10 -3                =                9 -16 9 0 -1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 -1 0 0 -16 9 0 -9 0 80 -144 90 -16               
.

The five first elementary decimation operators defined above correspond to sub-sampling (row 2, 3 and 4 of H M h ) and polynomial extrapolations of degree 3 (from the positions (0, .5, 1, 2) to x = -1 for first row and from the positions (-2, -1, -.5, 0) to x = 1 for fifth row).

These five elementary operators can be also obtained by applying Proposition 2.3,

H M h =            h0 2 h0 3 h0 4 h0 5 h0 6 h2 0 h2 1 h2 2 h2 3 h2 4 h4 -2 h4 -1 h4 0 h4 1 h4 2 h6 -4 h6 -3 h6 -2 h6 -1 h6 0 h8 -6 h8 -5 h8 -4 h8 -3 h8 -2            =           
9 -16 9 0 -1

1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 -1 0 9 -16 9           
.

We verify that h10 = h8 + 9T -2 ( h8 ) -9T -2 ( h6 ) which means that the operator associated to the last row of HM h can be obtained by linear combination of the translated versions of the operators associated to the two rows above.

Note that as for all interpolatory subdivision, sub-sampling provides an optimally stable decimation with l | hl | = 1.

4-point Shifted Lagrange Scheme

The 4-point shifted Lagrange subdivision scheme corresponds to the mask (1.7).

Applying Theorem 1,

H M h =                h 2 h 0 h -2 h -4 0 0 h 3 h 1 h -1 h -3 0 0 0 h 2 h 0 h -2 h -4 0 0 h 3 h 1 h -1 h -3 0 0 0 h 2 h 0 h -2 h -4 0 0 h 3 h 1 h -1 h -3                =               
-7 128                .
We get the 6 elementary decimation operators, h10

HM h = H -1 M h =               
-3                =                24367
              
.

A symmetric consistent decimation operator is obtained by combining the two rows in the middle of HM h , Another symmetric consistent decimation operator of length 12 can be derived as These two last decimation operators are used in the last chapter for the construction of non-linear multiresolution.

M h = { h-4 , h-3 , h-2 , h-1 , h0 , h1 , h2 , h3 } (2.14)
M h = { h-6 , h-5 , h-4 , h-3 , h-2 , h-1 , h0 , h1 , h2 , h3 , h4 , h5 } (2.15) = { 19 16128 , - 19

B-spline Subdivision B-spline Subdivision of Order 4

The B-spline subdivision scheme of order 4 corresponds to the mask

M h = {h 3 , h 2 , h 1 , h 0 , h -1 , h -2 } = { 1 8 , 1 2 , 3 4 , 1 2 , 1 8 , 0}.
We obtain four elementary decimation operators from

H M h =         h 2 h 0 h -2 0 h 3 h 1 h -1 0 0 h 2 h 0 h -2 0 h 3 h 1 h -1         =         1 2 1 2 0 0 1 8 3 4 1 8 0 0 1 2 1 2 0 0 1 8 3 4 1 8         , HM h = H -1 M h =         h0 0 h0 1 h0 2 h0 3 h2 -2 h2 -1 h2 0 h2 1 h4 -4 h4 -3 h4 -2 h4 -1 h6 -6 h6 -5 h6 -4 h6 -3         =         5 2 -2 1 2 0 -1 2 2 -1 2 0 1 2 -2 5 2 0 -5 2 10 -29 2 8        
.

B-spline Subdivision of Order 5

The B-spline subdivision scheme of order 5 corresponds to the mask We obtain four elementary decimation operators from , Other operators of length not larger than 10 can be constructed following (2.4)

M h = {h 3 , h 2 , h 1 , h 0 , h -1 , h -2 } = { 1
H M h =         h 2 h 0 h -2 0 h 3 h 1 h -1 0 0 h 2 h 0 h -2 0 h 3 h 1 h -1         =         5
HM h = H -1 M h =         h0 0 h0 1 h0 2 h0 3 h2 -2 h2 -1 h2 0 h2 1 h4 -4 h4 -3 h4 -2 h4 -1 h6 -6 h6 -5 h6 -4 h6 -3         =         35
using four instance {λ 1 , λ 2 , λ 3 , λ 4 } as [ h-6 h-5 h-4 h-3 h-2 h-1 h0 h1 h2 h3 ] = λ 1 [0 0 0 0 0 0 h0 0 h0 1 h0 2 h0 3 ] + λ 2 [0 0 0 0 h2 -2 h2 -1 h2 0 h2 1 0 0] + λ 3 [0 0 h4 -4 h4 -3 h4 -2 h4 -1 0 0 0 0] + λ 4 [ h6 -6 h6 -5 h6 -4 h6 -3 0 0 0 0 0 0] .
A centred consistent decimation operator of length 6 can be obtained taking

{λ 1 , λ 2 , λ 3 , λ 4 } = {0, 1/2, 1/2, 0}, [ h-4 h-3 h-2 h-1 h0 h1 ] = [ 3 16 - 15 16
5 4 5 4 - 15 16
3 16 ].               
.

We get the 6 elementary decimation operators,

HM h = H -1 M h =               
               =                231
               .
A symmetrical consistent decimation operator of length 8 is obtained by combining the two rows in the middle of HM h ,

M h = { h-4 , h-3 , h-2 , h-1 , h0 , h1 , h2 , h3 } = {- 5

Compactly Supported Wavelet Subdivision

Wavelets and, more precisely, scaling functions for multi-resolutions [START_REF] Daubechies | Ten lectures on wavelets[END_REF], are known to provide subdivision operators.

Orthogonality and zero moment conditions translate on the scaling coefficient

M h = {h 0 , h 1 , . . . , h 2N -1 } as [17]    i h i h i+2j = 2δ j,0 i (-1) i h i i p = 0 (2.16)
for j ∈ Z, p = 0, 1, . . . , N -1.

According to orthogonal compactly supported wavelet theory, the rescaled operators h = √ 2h and h = 1 √ 2 h are consistent subdivision/decimation operators. More precisely, compact support wavelets of length 2N constructed in [START_REF] Daubechies | Ten lectures on wavelets[END_REF] lead to the unique couple (subdivision and decimation) with the same mask (up to √ 2 rescaling) with exponential decay of the error corresponding to L = N -1.

For N = 2 we get from [START_REF] Daubechies | Ten lectures on wavelets[END_REF] [

h 0 h 1 h 2 h 3 ] = [ 1 + √ 3 4 √ 2 3 + √ 3 4 √ 2 3 - √ 3 4 √ 2 1 - √ 3 4 √ 2 ] .
Applying Proposition 1 for h = √ 2h we get

H M h =   h 0 h -2 h 1 h -1   =   3- √ 3 4 1+ √ 3 4 1- √ 3 4 3+ √ 3 4   , HM h =   h0 2 h0 3 h2 0 h2 1   =   3+ √ 3 4 -1+ √ 3 4 -1+ √ 3 4 3- √ 3 4   ,
and therefore two elementary decimation operators h0 and h2 .

For λ = 1 2 √ 3-1 √ 3+1 , the linear combination [ h0 h1 h2 h3 ] = λ[0 0 h0 2 h0 3 ] + (1 -λ)[ h2 0 h2 1 0 0] = [ 1 + √ 3 8 3 + √ 3 8 3 - √ 3 8 1 - √ 3 8 ] provides h = 1 √ 2 h .

Penalized Lagrange Subdivision

We finally consider a non-stationary (i.e. depending on the scale j ) subdivision scheme recently introduced in [START_REF] Si | On four-point penalized lagrange subdivision schemes[END_REF] and focus in the sequel on the associated consistent decimation masks generated by our approach.

Using the notations of [START_REF] Si | On four-point penalized lagrange subdivision schemes[END_REF], the scheme is here constructed from a polynomial P j (x) = 100(2 -2j )x 2 -2 -4j x 4 and a vector of penalization C = (0, 2, 0, 0).

Denoting

M h (j) = {h (j) 3 , h (j) 2 , h (j) 1 , h (j) 0 , h (j) -1 , h (j) -2 , h (j) -3 , h (j) -4 }, it first comes out that lim j→-∞ M h (j) = {- 1 16 , 0, 9 16 , 1, 9 16 , 0, - 1 16 , 0}, (2.17)
and

lim j→+∞ M h (j) = { 1 8 , 1 3 , 0, 0, 9 8 , 1, - 1 4 , - 1 3 } . (2.18)
Therefore, according to the scale j, the subdivision evolves from the classical interpolatory Lagrange subdivision (2.17) to a non-interpolatory one of Lagrangetype. Indeed, the coefficients in (2.18) are the point values at x = 0 or x = 1 2 of the Lagrange functions associated with the stencil {-1, 1, 2}. According to Theorem 1, it is then possible to generate for each j ∈ Z the matrix of associated consistent elementary decimation masks.

Consistent elementary decimations associated to (2.17)

               .
As an example, Figure 2.1 displays the evolution of the third row of the previous matrix for j ∈ [-10, 10]. It appears that the decimation mask quickly converges towards its asymptotical limit which is a sub-sampling ({0, 0, 0, 0, 1, 0}) when j → -∞ and {-54 107 , 144 107 , -9 107 , 24 107 , -6 107 , 8 107 } when j → +∞. It is also interesting to notice that, as expected, these decimations are consistent with the asymptotical subdivision schemes associated with the masks (2.17) and (2.18) respectively.

Conclusion

A generic approach for the construction of decimation operators consistent with a given subdivision scheme has been developed. It is first based on the generation of elementary decimation operators by inverting a matrix obtained from the mask of the subdivision scheme and connected to the so-called refinement matrices. All consistent decimation operators can then be derived by a linear combination of translated versions of elementary ones. This approach has been applied in the case of standard and non-standard schemes. In this last situation, the interest of our method stands in the possibility to generate many consistent decimation operators that was, up to now, not available in the literature. In the next chapter, we extend this construction to more general subdivision schemes. segmentation points. In this work, we focus on a unique segmentation x 0 = 0 and introduce two edge matrices H 0 and H 1 of size l × l and l × l (l and l depend on the stencil length and on the position-dependent strategy) that map {f As shown below, taking 4-point scheme as example, points in circle can be subdivided using uniform scheme while points in rectangle can be decimated using uniform scheme.

j 1 , • • • , f j l } (resp. {f j -l +1 , • • • , f j 0 }) to {f j+1 1 , • • • , f j+1 l } (resp. {f j+1 -l +1 , • • • , f j+1 0 }).
f j 1 f j 2 f j 3 f j 4 f j 5 f j 6 f j+1 1 f j+1 2 f j+1 3 f j+1 4 f j+1 5 f j+1 6 f j+1 7 f j+1 8 f j+1 9 f j+1 10 f j+1 11 f j+1 12 Remark 3.1.
1. The condition on the uniform decimation operator introduced in Proposition 3.2 is always satisfied when hu is elementary.

2. For a fixed uniform decimation, if this condition is not satisfied, a consistent position-dependent decimation can be constructed by locally adapting (i.e. reducing) the length of the decimation mask in the vicinity of the segmentation point.

This approach is exploited in the numerical tests of Section 3.3.3 in the case of a finite sequence to adapt the decimation at the boundaries of the interval containing the data.

Examples

We restrict these examples to the generation of consistent decimation mask on the right of a segmentation point.

4-point Interpolatory Lagrange Scheme

Based on the 4-point Lagrange polynomial, according to (1.5), the adapted interpolatory subdivision in the vicinity of the segmentation point is obtained by taking x r ∈ {-3 2 , -1 2 } and x l ∈ {-1, 0}, which leads to

H 0 =         35
0 1 0 0        
.

Inverting H 0 , we get

        f j 1 f j 2 f j 3 f j 4         =         0 1 0 0 0 0 0 1 -4 15 -20 10 -20 70 -84 35                 f j+1 1 f j+1 2 f j+1 3 f j+1 4        
and the matrix involved in the previous equation provides consistent decimation masks.

Note that the decimation for {f j 3 , f j 4 } can also be calculated by subsampling that can therefore be used for any positions.

4-point Shifted Lagrange Scheme

Based on the 4-point Lagrange polynomial, according to (1.5), the shifted subdivision in the vicinity of the segmentation point is obtained by taking x r ∈ {- .

Inverting H 0 , we get

        f j 1 f j 2 f j 3 f j 4         =         5/
                f j+1 1 f j+1 2 f j+1 3 f j+1 4        
and the matrix involved in the previous equation provides consistent decimation masks.

Note that the decimation for {f j 3 , f j 4 } can also be calculated by a uniform approach without adaption, in this example, only the first two rows are needed to get

{f j 1 , f j 2 } to satisfy the consistency. Remark 3.2.
In practice, it turns out that it is more efficient to replace, when possible, the decimation mask obtained following Proposition 3.1 by the decimation coming from the generic uniform approach. For the 4-point interpolatory and shifted Lagrange schemes, there always exist decimation operators to perform this replacement while holding the consistency. This generalization to other type of schemes remains an open question.

Linear Subdivision Schemes

Global Consistent Decimation

In this section we construct a global decimation operator transforming globally any sequence (f j+1 k ) 1≤k≤2n into a sequence (f j k ) 1≤k≤n . Let us first introduce some notations.

Definition 3.1 (Subsampling, Interlacing and Scaling Operators).

Let (σ, σ ) be a pair of subsampling operators defined as

∀e ∈ l ∞ (Z),      (σe) k = e 2k+1 , (σ e) k = e 2k , k ∈ Z.
and τ be the interlacing operator,

∀u, v ∈ l ∞ (Z), (τ (u, v)) k =      u i , k = 2i + 1, v i , k = 2i, i ∈ Z.
and λ be the scaling operator,

∀f = (f k ) k∈Z ∈ l ∞ (Z), (λf ) i = λ i f i , i ∈ Z, λ i ∈ R.
We have

στ (u, v) = u, σ τ (u, v) = v,
and

τ (σ•, σ •) = I.
A global consistent decimation operator can then be constructed by the following proposition.

Proposition 3.3.

Given h L a linear subdivision operator, we introduce h e and h o two operators associated to even and odd terms of h

L , ∀k ∈ Z, f ∈ l ∞ (Z),      (h e f ) k = (h L f ) 2k , (h o f ) k = (h L f ) 2k+1 .
If there exist a left inverse for the operators h o and h e , denoted (h o ) -1 and (h e ) -1 (i.e. (h o ) -1 h o = I, (h e ) -1 h e = I), then for all scaling operator λ,

hL = λ(h o ) -1 σ + (I -λ)(h e ) -1 σ defines a consistent decimation scheme with h L .
Proof.

The proof is straightforward since h

L = τ (h o •, h e •). Remark 3.3.
The inverse of operators h o and h e exists if the kernel of the subdivision h L is reduced to {0}.

Matrix Representation

In this section, for practical issues, we provide a matrix representation of the operators introduced in Definition 3.1 and Proposition 3.3.

Definition 3.2.

Let X and X stand for the matrix form of operators σ and σ ,

X =          1 0 0 0 • • • 0 0 0 0 1 0 • • • 0 0 . . . . . . . . . . . . 0 0 0 0 • • • 1 0          , X =          0 1 0 0 • • • 0 0 0 0 0 1 • • • 0 0 . . . . . . . . . . . . 0 0 0 0 • • • 0 1          .
Let T be the matrix form of operator τ ,

T =                   1 0 0 0 • • • 0 0 0 0 0 • • • 0 0 0 0 0 • • • 0 1 0 0 0 • • • 0 0 1 0 0 • • • 0 0 0 0 0 • • • 0 0 0 0 0 • • • 0 0 1 0 0 • • • 0 . . . . . . . . . . . . 0 0 0 0 • • • 1 0 0 0 0 • • • 0 0 0 0 0 • • • 0 0 0 0 0 • • • 1                  
.

We get for all matrices U and V with suitable dimensions,

T   XU X U   = U.
and

XT   U V   = U, XT   U V   = V.
Proposition 3.4.

Denoting H the matrix of dimension 2n × n associated to a linear subdivision h

L that maps {f j 1 , f j 2 , . . . , f j n } to {f j+1 1 , f j+1 2 , . . . , f j+1 2n }, then H = T   XH X H  
where XH and X H are square matrices of dimension n × n. If they are invertible, introducing the matrix

Λ =          λ 1 0 • • • 0 0 λ 2 • • • 0 . . . . . . . . . . . . 0 0 • • • λ n         
where ∀i = {1, 2, . . . , n}, λ i ∈ R, then

H = [Λ(XH) -1 (I -Λ)(X H) -1 ]T -1 , (3.1)
is a matrix verifying HH = I, and is associated to a global linear decimation operator consistent with h L .

Example of Construction of Global Consistent Decimation Operators

In this section, we compare the decimation matrix constructed following the two approaches of Section 3.2 and 3.3.1 in the case of the 4-point shifted Lagrange subdivision scheme adapted to the two edges of an interval. Considering an initial sequence of length 8, the matrix H that maps

{f j 1 , f j 2 , . . . , f j 8 } to {f j+1 1 , f j+1 2 , . . . , f j+1 16 } is H =                                               195
                                             
.

Combining the decimation mask (2.14) with the adaption proposed in Section 3.2 and the practical replacement with uniform decimation operators, a global decimation can be constructed from H1 such that

HT 1 =                                      5
                                    
where HT 1 denotes the transpose of H1 . As expected, the same decimation mask is used except for the 2 first and last rows.

On the contrary, when the global approach of Section 3.3 is used, taking Λ = 1 2 I, we get from (3.1) the full matrix H2 representing the global consistent decimation.

HT 2 =                                      967
                                    
where HT 2 denotes the transpose of H2 .

We finally develop in the next section a method to generate a decimation consistent with a given general subdivision scheme. It is exploited in practice to handle the case of some specific non-linear schemes.

General Subdivision Schemes

The subdivision h in this section can be of any type, as long as we know how to calculate the subdivided sequence.

Generic Approach

The following result holds,

Theorem 2.

Let h be a subdivision operator, if there exists a linear decimation hL so that hL h-I is contractive1 , then for any f j+1 ∈ l ∞ (Z), the fixed-point equation

f j = hL f j+1 -( hL h -I)f j (3.2)
has a unique solution.

Moreover, h : f j+1 → f j is a decimation operator consistent with h.

Proof.

The existence and uniqueness of the solution of the fixed-point equation is a consequence of the Banach fixed point theorem since hL h -I is contractive.

Considering f j such that f j+1 = h f j is a solution of equation (3.2), it is then the unique solution for given (h, hL ) and f j+1 . Thus f j is a decimated sequence from f j+1 and (3.2) defines a consistent decimation.

According to the Banach fixed-point theorem,f j = hf j+1 = lim n→∞ (f j ) n can be constructed by induction:

   (f j ) 0 = hL f j+1 (f j ) n+1 = hL f j+1 -( hL h -I)(f j ) n . (3.3)
If a non-linear subdivision scheme h is considered as h = h L + h N where h L is a linear scheme and h N a non-linear perturbation, the previous proposition can be used to exhibit a decimation consistent with h provided hL h N is contractive.

Remark 3.4.

1. Given f j+1 , the different choices of linear decimation operators hL lead to different f j and associated prediction errors. This flexibility is exploited in the numerical tests of Chapter 4.

2. If hL is consistent with h, the fixed-point equation reduces to f j = hL f j+1 .

Examples and Numerical Results

4-point Shifted PPH Scheme

We use Theorem 2 to generate a decimation consistent with the 4-point shifted PPH scheme recalled in Section 1.2.6.

Before introducing the main result in Proposition 3.5, two lemmas are required.

Lemma 3.1. ∀x, y, a, b ∈ R, |(H(x, y) -A(x, y)) -(H(a, b) -A(a, b))| ≤ 2 • max(|x -a|, |y -b|).
Proof.

we distinguish different cases: (

) x, y, a > 0, b < 0, then H(a, b) = 0, |(H(x, y) -A(x, y)) -(H(a, b) -A(a, b))| = a -x 2 + b -y 2 + 2xy x + y ≤ a -x 2 + b 2 + y 2 x -y x + y + 1 2 2xy x + y ≤ 1 2 |x -a| + 1 2 |y -b| + max(|x|, |y|) ≤2 • max(|x -a|, |y -b|). (3) x, y, a, b > 0 or x, y > 0, a, b < 0, |(H(x, y) -A(x, y)) -(H(a, b) -A(a, b))| = ( 2xa (x + y)(a + b) - 1 2 )(y -b) + ( 2yb (x + y)(a + b) - 1 2 )(x -a) ≤max 2xa + 2yb (x + y)(a + b) -1 , 2xa -2yb (x + y)(a + b) • max(|x -a|, |y -b|) ≤2 • max(|x -a|, |y -b|). 2
and we can conclude the other cases by symmetry.

Lemma 3.2.

Given x, y, a, b ∈ R, if (|x| -|y|)(|a| -|b|) < 0, then ∀p, q ∈ R, |p(H(x, y) -A(x, y)) -q(H(a, b) -A(a, b))| ≤ max(|p|, |q|) • max(|x -a|, |y -b|). If p = q = 1, |(H(x, y) -A(x, y)) -(H(a, b) -A(a, b))| ≤ max(|x -a|, |y -b|). (3.4)
Proof.

We first prove (3.4) under the condition (|x| -|y|)(|a| -|b|) < 0 by distinguishing different cases:

(1) xy < 0, ab < 0, then

H(x, y) = H(a, b) = 0, |(H(x, y) -A(x, y)) -(H(a, b) -A(a, b))| ≤ x -a 2 + y -b 2 ≤max(|x -a|, |y -b|).
(

) xy > 0, ab < 0 then H(a, b) = 0, |(H(x, y) -A(x, y)) -(H(a, b) -A(a, b))| ≤ x -y 2 + a + b 2 ≤max(|x -a|, |y -b|). 2
(

) xy > 0, ab > 0, |(H(x, y) -A(x, y)) -(H(a, b) -A(a, b))| = xa + xb + ya -yb 2(x + y)(a + b) (x -a) + -xa + xb + ya + yb 2(x + y)(a + b) (y -b) ≤ 1 2 |x -a| + 1 2 |y -b| ≤max(|x -a|, |y -b|). 3
and we can conclude the other cases by symmetry.

In the other hand, (|x| -|y|)(|a| -|b|) < 0 leads to

|(H(x, y) -A(x, y)) + (H(a, b) -A(a, b))| ≤ max(|x -a|, |y -b|),
and

|H(x, y) -A(x, y)| ≤ max(|x -a|, |y -b|).
Then for p, q ∈ R satisfying,

(1) p > q > 0,

|p(H(x, y) -A(x, y)) -q(H(a, b) -A(a, b))| =|q(H(x, y) -A(x, y)) -q(H(a, b) -A(a, b)) + (p -q)(H(x, y) -A(x, y))| ≤(|q| + |p -q|) • max(|x -a|, |y -b|) ≤p • max(|x -a|, |y -b|).
(

) p > 0 > q, |p| > |q|, |p(H(x, y) -A(x, y)) -q(H(a, b) -A(a, b))| =| -q(H(x, y) -A(x, y)) -q(H(a, b) -A(a, b)) + (p + q)(H(x, y) -A(x, y))| ≤(|q| + |p + q|) • max(|x -a|, |y -b|) ≤p • max(|x -a|, |y -b|). 2
and we can conclude the other cases by symmetry.

We will prove successively that the 4, 8 and 12 point decimations hL of section 2.3 lead to contraction.

Proposition 3.5.

Denote h = h L +h N the 4-point shifted PPH subdivision scheme given by (1.10,1.11), if hL is given by (2.14) or (2.15), then hL h N is contractive.

Proof.

In order to prove the contractivity, we focus on

|| hL h N u -hL h N v|| ∞ .
With the notations N k , DHA k of Section 1.2.6, we get for all l ∈ Z,

( hL h N u) l -( hL h N v) l = k h2k-2l N u k ( 1 4 ) + k h2k+1-2l N u k ( 3 4
)

- k h2k-2l N v k ( 1 4
)

- k h2k+1-2l N v k ( 0

Conclusion

In this chapter, we proposed several new constructions of decimation operators consistent with general subdivision scheme. Adapting the method introduced in Chapter 2, a first approach in the case of linear non-uniform subdivision scheme was developed. It is based on the inversion of the edge matrix obtained from the mask of the subdivision scheme associated to the prediction in the vicinity of segmentation points. A second approach was then described and led to the construction of consistent global decimation for any type of linear subdivision scheme applied on an interval. A matrix representation was also provided for practical issues. Finally, we considered general subdivision and introduced a new method for non-linear scheme based on the resolution of a fixed-point equation. Using the last method we were able to define a non-linear decimation consistent with the shifted PPH for which there was, up to now, no available consistent decimation in the literature.

In the next chapter, these constructions are plugged into the multi-scale framework to derive new multiresolution analysis.

Chapter 4 Multiresolution Analysis

Introduction

This chapter deals with the full construction of multiresolution analysis associated to a given subdivision scheme. Starting from the generation of consistent decimation operators using the methods described in the previous chapters, we introduce a new approach to derive compatible detail subdivision and detail decimation operators according to Definition 1.7. After a description of this construction in Section 4.2, several results related to the analysis of subdivision-based multiresolutions are provided. They first concern the polynomial reproduction property (Section 4.3) then we focus on the stability of the multiresolution transforms as well as on the prediction error decay (Section 4.4). Finally, several numerical results of multiresolution analyses are given in Section 4.5 for linear and non-linear subdivision schemes. Their interest is illustrated by an application in the framework of image compression.

Construction of Compatible Operators

We first establish an important result related to the action of a decimation operator on the sequence of prediction errors. Then, it is exploited to construct detail subdivision and detail decimation operators.

Prediction Errors and Kernel of Decimation

For linear subdivision schemes, the prediction error (1.16) belongs, by construction, to the kernel of the associated consistent decimation operator. This statement guarantees the existence of a couple of detail subdivision and detail decimation operators (g, g) which are compatible with the couple of subdivision and decimation

operators (h, h).

A similar result can be derived for general subdivision and decimation constructed following Theorem 2. It is given by the next proposition, Proposition 4.1.

Let h be a general subdivision operator and h be a consistent decimation operator given by Theorem 2 with hL the involved linear decimation operator. The associated prediction error e j+1 verifies hL e j+1 = 0, (

)

and he j+1 = 0. (4.2)
Proof.

Under the contraction condition, the unique solution for equation (3.2) is denoted

f j = hf j+1 .
Then, the prediction error can be written as

e j+1 = f j+1 -h hf j+1 = f j+1 -h L f j -(h -h L ) f j = (I -h L hL )f j+1 -(I -h L hL )(h -h L ) f j ,
Applying hL and using the consistency relation lead to (4.1).

Suppose w j = he j+1 ,

w j = hL e j+1 -hL (h -h L )w j = -( hL h -I)w j
according to the fixed-point theorem, w j = 0 is the unique solution which leads to (4.2).

Detail Subdivision and Detail Decimation

In this section, we construct a couple of detail subdivision and detail decimation operators (g, g) compatible with (h, h). Using the operators introduced in Definition 3.1, we have Theorem 3.

Let h be a subdivision operator and h a consistent decimation constructed following

Theorem 2, we introduce he and ho the two operators associated to even and odd terms of hL ,

∀k ∈ Z, f ∈ l ∞ (Z),          ( ho f ) k = l hL 2l+1-2k f 2l+1 ( he f ) k = l hL 2l-2k f 2l .
If there exists a linear left inverse operator of he , denoted ( he ) -1 , then (g, g) defined as

     g = σ(I -h h) g = τ (•, -( he ) -1 ho •) (4.3)
are detail operators compatible with (h, h).

Proof.

Thanks to Proposition 4.1, we have h L e j+1 = 0 =⇒ ho σe j+1 + he σ e j+1 = 0.

Taking

d j = σe j+1 , σ e j+1 = -( he ) -1 ho d j ,
Therefore,

e j+1 = τ (σe j+1 , σ e j+1 ) = τ (d j , -( he ) -1 ho d j ).
Thus a pair of detail operators are constructed since

     d j = σe j+1 = gf j+1 e j+1 = gd j
where (g, g) are defined by (4.3).

Finally, we prove the compatibility of (h, h, g, g).

According to Proposition 4.1, we have hL g = 0 and hg = 0. Then

gg = σ(I -h h)g = σg -σh hg = σg = I.
Under the consistency condition hh = I, we have gh = σ(I -h h)h = 0, which concludes the compatibility proof. If h is an interpolatory subdivision, the subsampling operator h = σ is consistent with h and ho stands for the identity operator.

In the sequel, exploiting the notations of Definition 3.2, we provide a practical representation to construct g and g in the case of a finite set of data.

Matrix Representation

In this section we establish the relation between prediction error vector and detail vector using matrix representation which is sufficient to illustrate the details operators previously introduced.

Denoting E the vector of prediction error and HL the matrix associated to hL , according to Proposition 4.1,

HL E = 0, then ( HL X T )(XE) + ( HL X T )(X E) = 0, if HL X T is invertible, X E = -( HL X T ) -1 ( HL X T )(XE).
Therefore, taking the detail vector as

D = XE,
the prediction error becomes

E = T   XE X E   = T   D -( HL X T ) -1 HL X T D   = T   I -( HL X T ) -1 HL X T   D.
Thus, the detail subdivision matrix is

G = T   I -( HL X T ) -1 HL X T   . Remark 4.2.
Proposition 2.2, Theorem 2 and Theorem 3 can be used to construct quadruplet of compatible operators generating a multiresolution associated to a general subdivision scheme. It is then possible to extend classical results for multi-scale analyses to the subdivision-based multiresolution framework. In the linear case, one can for

The two following propositions are interpretations of Definition 1.9 and Definition 1.8 in terms of conditions on the mask of the subdivision and decimation operators.

Proposition 4.2.

A subdivision operator h quasi-reproduces polynomials up to degree L if and only if

∀n ∈ {0, 1, 2, . . . , L}, l∈Z h 2l (2l) n = l∈Z h 2l+1 (2l + 1) n . ( 4.4)
A subdivision operator h reproduces polynomials up to degree L if and only if

∀n ∈ {0, 1, 2, . . . , L}, ∃t ∈ R, l∈Z h 2l (2l) n = l∈Z h 2l+1 (2l + 1) n = t n . (4.5)
where t is a translation factor, such that f ∈ π L becomes f (• -t) in Definition 1.9.

Proof.

If h quasi-reproduces polynomials up to degree L, for all

f (x) = p i=0 a i x i ∈ π p (R), p ≤ L, there exists g(x) = p i=0 b i x i ∈ π p (R) such that ∀k, g((k -t)2 -(j+1) ) = l h k-2l f (l2 -j )
where t denotes a translation factor. That is to say, ∀k, ∀p ∈ {0, 1, 2, . . . , L},

p i=0 b i ((k -t)2 -(j+1) ) i = l h k-2l p i=0 a i (l2 -j ) i . (4.6)
Introducing m = k -2l, then m and k have the same parity,

∀k, ∀p ∈ {0, 1, 2, . . . , L}, m ∈ {• • • , k -2, k, k + 2, • • • }, p i=0 b i (k -t) i 2 -(j+1)i = m h m p i=0 a i i n=0 n i (k -t) n (-m + t) i-n 2 -(j+1)i ,
Removing the arbitrariness of k, for m varying as even or odd, we have

∀i ∈ {0, 1, 2, . . . , L}, b i 2 -(j+1)i = m h m L n=i a n n i (-m + t) n-i 2 -(j+1)n .
Finally, for m varying as even or odd,

∀i ∈ {0, 1, 2, . . . , L}, b i = L n=i a n n n -i m h m (m -t) n-i (-1) n-i 2 -(j+1)(n-i) , (4.7)
expanding this equation for each i, the only condition to ensure the existence of {b i } 0≤i≤L is that m h m (m -t) n-i does not depend on the parity of m, which leads to (4.4).

Further, if h reproduces the polynomials up to degree L, which means ∀i ≤

L, b i = a i , then (4.7) is equivalent to ∀i ∈ {0, 1, 2, . . . , L}, m h m (m -t) i = δ i,0 ,
where m varies as even or odd. According to Lemma 4.1, this is equivalent to (4.5).

Remark 4.3. 1. If i = L in (4.7), we have b L = a L ( m h m )
, that is to say if the subdivision operator reproduces constants, it always preserves the leading coefficient. Other coefficients are given by (4.7).

2. If t = 0, h reproduces the same polynomial without translation, in this case,

∀n ∈ {0, 1, 2, . . . , L}, l∈Z h k-2l (k -2l) n = δ n,0 .
A condition for polynomial quasi-reproduction using Laurent polynomial representation was found in [START_REF] Conti | Polynomial reproduction for univariate subdivision schemes of any arity[END_REF], we prove the equivalence with our mask representation in Appendix A.

Proposition 4.3.

A decimation operator h quasi-reproduces polynomials up to any degree if and only if

l hl = 0. ( 4.8)
A decimation operator h reproduces polynomials up to degree L if and only if

∀n ∈ {0, 1, 2, . . . , L}, ∃t ∈ R l∈Z hl l n = t n , ( 4.9)
where t is a translation factor such that f ∈ π L becomes f (• + t 2 ) in Definition 1.9.

Proof.

If h quasi-reproduces polynomials up to degree L, for all f

(x) = p i=0 a i x i ∈ π p (R), p ≤ L, there exists g(x) = p i=0 b i x i ∈ π p (R) such that ∀k, g((k + t 2 )2 -j ) = l hl-2k f (l2 -(j+1) )
where t 2 denotes a translation factor. That is to say, ∀k, ∀p ∈ {0, 1, 2, . . . , L},

p i=0 b i ((k + t 2 )2 -j ) i = l hl-2k p i=0 a i (l2 -(j+1) ) i . (4.10) Introducing m = l -2k, ∀k,∀p ∈ {0, 1, 2, . . . , L}, p i=0 b i (2k + t) i 2 -(j+1)i = m hm p i=0 a i i n=0 n i (2k + t) n (m -t) i-n 2 -(j+1)i ,
Removing the arbitrariness of k, we have

∀i ∈ {0, 1, 2, . . . , L}, b i 2 -(j+1)i = m hm L n=i a n n i (m -t) n-i 2 -(j+1)n .
Finally, we obtain (4.11) expanding it for each i, the only condition to ensure the existence of {b i } 0≤i≤L is that m hm = 0, which leads to (4.8).

∀i ∈ {0, 1, 2, . . . , L}, b i = L n=i a n n n -i m hm (m -t) n-i 2 -(j+1)(n-i) ,
Further, if h reproduces the same polynomial, which means ∀i ≤ L, b i = a i , then

Given a subdivision operator h and a consistent decimation operator h,

1. if h reproduces polynomials up to degree L, then h reproduces polynomials up to degree L.

2. if h quasi-reproduces polynomials up to degree L and h reproduces polynomials up to degree L, then h reproduces polynomials up to degree L.

Proof.

Under condition (2.3), 1. (4.5) leads to (4.9).

2. (4.9) and (4.4) leads to (4.5).

More details can be found in Appendix B.

Composing Subdivision with Decimation

In this section, we focus on the operator h h.

Proposition 4.5.

Let h be a subdivision operator and h be a decimation operator.

h 2l m∈Z hm (m -2l) n = l∈Z h 2l+1 m∈Z hm (m -2l -1) n = t n . (4. 13
)
where t is a translation factor such that f ∈ π L becomes f (• + t) in Definition 1.9.

Proof.

The proof is similar to the two previous ones, the key equations will be Let h be the B-spline subdivision scheme of order m (mask of length m + 1) given by (1.4), then h quasi-reproduces polynomials up to degree m -1. Moreover, it is the only mask of length m + 1 that leads to the quasi-reproduction of polynomials up to degree m -1.

∀k, g((k + t)2 -(j+1) ) = l h k-2l m hm-2l f (m2 -(j+1) ) by changing index, ∀i ∈ {0, 1, 2, . . . , L}, b i = L n=i a n n n -i l h l m hm (m -l -t) n-i 2 -(j+1)(n-i) ,

Proof.

This proof is performed in two steps, first, we prove that the mask (1.4) verifies (4.4), then, we prove its uniqueness.

We first prove by induction that

m+1 k=0 m + 1 k k n (-1) k = 0, ∀n ≤ m, (4.16) i) it is easily verified for m = 1, n = 0, 2 0 + 2 1 • (-1) + 2 2 = 0, n = 1, 2 0 • 0 + 2 1 • (-1) + 2 2 • 2 = 0. ii) suppose ∀n ≤ m -1, m k=0 m k k n (-1) k = 0, then m+1 k=0 m + 1 k k n (-1) k = m k=1 m + 1 k k n (-1) k + (m + 1) n (-1) m+1 = m k=1 ( m k + m k -1 )k n (-1) k + (m + 1) n (-1) m+1 = m k=0 m k k n (-1) k + m k=0 m k (k + 1) n (-1) k+1 = m k=0 m k (k n - n i=0 n i k i )(-1) k = (-1) n-1 i=0 n i ( m k=0 m k k i (-1) k ) = 0.
Splitting (4.16) with respect to even and odd indices leads to (4.4).

To prove uniqueness, we rewrite (4.4) as

A             h 0 -h 1 h 2 -h 3 . . .             =             2 0 0 0 . . .             with A =             1 -1 1 -1 • • • 1 1 1 1 • • • 0 1 2 3 • • • 0 1 2 2 2 3 2 • • • . . . . . . . . . . . .             .
The determinant of A is given by

det(A) = 1 1 1 • • • 1 2 3 • • • 1 2 2 3 2 • • • . . . . . . . . . . . . + 1 1 1 • • • 0 2 3 • • • 0 2 2 3 2 • • • . . . . . . . . . . . . + 1 1 1 • • • 0 1 3 • • • 0 1 2 3 2 • • • . . . . . . . . . . . . + • • •
each determinant is the determinant of a Vandermonde matrix, so det(A) ≥ 0 and

{h i } 0≥i≥m+1 is uniquely determined. Remark 4.7.
For a subdivision operator with fixed length, the B-spline scheme is the scheme which gives the highest degree of polynomial quasi-reproduction.

Proposition 4.7.

Let h be a p-point Lagrange subdivision scheme given by (1.5) (of length 2p), then h reproduces polynomials up to degree p -1. Moreover, it is the only mask of length 2p which leads to the reproduction of polynomials up to degree p -1.

Proof.

The proof also includes two parts, first we verify the polynomial reproduction condition (4.5) with the mask given by (1.5), then we prove the uniqueness of this mask with fixed length.

Taking l + r = p and denoting x l = -t/2, thus x r = -t/2 + 1/2, with a little calculation, we find that ∀n ∈ {0, 1, 2, . . . , l + r -1}

l-1 i=-r h 2i (2i) n = l-1 i=-r r k=-l+1, k =-i -t/2 -k -i -k (2i) n = t n . l-1 i=-r h 2i+1 (2i + 1) n = l-1 i=-r r k=-l+1, k =-i -t/2 + 1/2 -k -i -k (2i + 1) n = t n .
which verify (4.5).

To prove uniqueness, we rewrite (4.5) with (1.5) as

A             h -2r h -2r+2 . . . h 2l-4 h 2l-2             =             1 t . . . t l+r-2 t l+r-1             and B             h -2r+1 h -2r+3 . . . h 2l-3 h 2l-1             =             1 t . . . t l+r-2 t l+r-1             , with A =             1 1 • • • 1 1 -2r -2r + 2 • • • 2l -4 2l -2 . . . . . . . . . . . . . . . (-2r) l+r-2 (-2r + 2) l+r-2 • • • (2l -4) l+r-2 (2l -2) l+r-2 (-2r) l+r-1 (-2r + 2) l+r-1 • • • (2l -4) l+r-1 (2l -2) l+r-1             , B =             1 1 • • • 1 1 -2r + 1 -2r + 3 • • • 2l -3 2l -1 . . . . . . . . . . . . . . . (-2r + 1) l+r-2 (-2r + 3) l+r-2 • • • (2l -3) l+r-2 (2l -1) l+r-2 (-2r + 1) l+r-1 (-2r + 3) l+r-1 • • • (2l -3) l+r-1 (2l -1) l+r-1            
.

Since A and B are invertible Vandermonde matrices the uniqueness is straightforward.

Remark 4.8.

For a subdivision operator with fixed length, Lagrange scheme is the scheme which gives the highest degree of polynomials reproduction.

Proposition 4.7 states that a p-point Lagrange subdivision always reproduces (and also quasi-reproduces) polynomials of degree p -1. In the symmetrical case, it gains one more degree for polynomial quasi-reproduction, which is clarified in the following proposition.

Proposition 4.8.

Let h be the shifted 2p-point symmetric Lagrange subdivision operator, then h reproduces polynomials up to degree 2p -1 with a translation of 1/2 and quasi-reproduces polynomials up to degree 2p.

Proof.

It is easy to verify that ∀n = 0, 1, 2, . . . , 2p -1,

p-1 i=-p L i ( 1 4 ) 2i + 1 2 n = p-1 i=-p L i ( 3 4 ) 2i + 1 + 1 2 n = δ n,0 ,
and

p-1 i=-p L i ( 1 4 )(2i) 2p = p-1 i=-p L i ( 3 4
)(2i + 1) 2p .

the proof is completed according to Proposition 4.2.

Stability of the Multiresolution and Decay of the Prediction Errors

Stability of the Multiresolution

In the linear case, since the subdivision is assumed to be convergent, we focus on the stability study of the decimation operator.

The following proposition provides a condition to ensure this property.

Proposition 4.9.

A linear decimation operator h is stable if the subdivision whose mask is constructed from sequence 2( hl ) l∈Z is stable.

Proof.

For all (f j l ) l∈Z ∈ V j subdivided from V 0 by successively applying a subdivision operator h,

f j l = l j-1 h l-2l j-1 l j-2 h l j-1 -2l j-2 • • • l 1 h l 2 -2l 1 l 0 h l 1 -2l 0 f 0 l 0 = l 0 h j l-2 j l 0 f 0 l 0 .
If h is stable, there exists C ∈ R, such that ∀l,

l 0 h j l-2 j l 0 ≤ C, (4.17) then l l 0 h j l-2 j l 0 ≤ l C.
In the non-linear case, since the decimation is not always a subsampling operator, the stability of the decomposition is not straightforward and a numerical test is provided in Section 4.5.2.

Decay of the Prediction Errors

The next proposition provides a condition to deduce the decay rate of the prediction error for linear uniform subdivision schemes.

Proposition 4.11.

Let h be a linear uniform stable subdivision operator and h be a linear stable decimation operator.

If (4.15) is satisfied, i.e.

∀k, n ∈ {0, 1, 2, . . . , L},

l h k-2l m hm-2l (m -k) n = δ n,0 ,
then for sufficiently large j ∈ Z,

||e j || ≤ C2 -(L+1)j , ( 4.19)
where C does not depend on j.

Proof.

Condition (4.15) is equivalent to

∀1 ≤ n ≤ L, k n = l h k-2l m hm-2l m n ,
and implies that

∀j ∈ Z, ∀1 ≤ n ≤ L, (k2 -j ) n - l h k-2l m hm-2l (m2 -j ) n = 0 . (4.20)
Moreover, for any j, one can introduce f j ∈ C L 0 (R) with L 0 >> L such that

f j k = f j (k2 -j
). We postpone to the end of the proof the construction of a particular f j to get the expected result of the proposition.

Using Taylor expansion, it then comes out,

f j k = f j (k2 -j ) = L+1 n=0 1 n! f (n) j (0)(k2 -j ) n + o((2 -j ) L+1 )
and the prediction error (1.16) can be rewritten

e j k = L+1 n=1 1 n! f (n) j (0) (k2 -j ) n - l h k-2l m hm-2l (m2 -j ) n + o((2 -j ) L+1 ).
According to (4.20),

e j k = 1 (L + 1)! f (L+1) j (0) (k2 -j ) L+1 - l h k-2l m hm-2l (m2 -j ) L+1 + o(2 -j(L+1) ). (4.21)
To finish the proof we introduce a particular f j such that ∀i ≤ L 0 , ||f

(i)
j || ∞ is controlled independently of j that leads to a constant C independent of j such that

||e j || ≤ C2 -j(L+1) . For any j ∈ [J 0 , J max -1], f j is constructed from f Jmax ∈ C L 0 (R).
More precisely, starting from (f Jmax k

) k∈Z with f Jmax k = f Jmax (k2 -Jmax ), (f Jmax-1 k ) k∈Z is written f Jmax-1 k = (D Jmax-1 Jmax f Jmax ) k = l∈Z hl-2k f Jmax l = l∈Z hl f Jmax l+2k = l∈Z hl f Jmax ((l+2k)2 -Jmax ),
f Jmax-1 can therefore be defined as ∀x ∈ R

f Jmax-1 (x) = l hl f Jmax (l2 -Jmax + x),
and it is straightforward that ∀i ≤ L 0 ,

||f (i) Jmax-1 || ∞ ≤ ( l | hl |)||f (i) Jmax || ∞ . ( 4.22)
Iterating this process, ∀j ∈ [J 0 , J max -1],

||f (i) j || ∞ ≤ ( l | hl |) Jmax-j ||f (i) Jmax || ∞ . ( 4

.23)

Since h is stable, there exists C > 0 does not depends on j such that

||f (i) j || ∞ ≤ C||f (i) Jmax || ∞ ,
and (4.21) leads to

||e j || ≤ C2 -(L+1)j .
Remark 4.9.

According to Theorem 4, in the case of a consistent decimation, condition (4.15) in the previous proposition can be replaced by an assumption of quasi-reproduction of the subdivision operator.

Proposition 4.11 is extended to the case of non-linear subdivision schemes.

Proposition 4.12.

Let h be a non-linear subdivision scheme with h = h L +h N where h L quasi-reproduces polynomials up to degree p, and h be a stable consistent decimation operator constructed according to Theorem 2. If there exists q ∈ N such that for any polynomial P q-1 of degree (q -1), defining (f j k ) k∈Z = (P q-1 (k2 -j ) + j k ) k∈Z ,

h N f j = O( j ),
then the decay rate of the associated prediction error is at least min(p, q).

Proof.

For a consistent couple (h, h),

f j = hf j+1 = hL f j+1 -hL h N f j .
The associated prediction error can be written as

e j+1 = (I -h L hL )f j+1 -(I -h L hL )h N f j , since (I -h L hL
) is a linear operator and h is stable,

e j+1 = O(2 -min(p,q)j ),
the proof is achieved.

Examples

4-point Shifted Lagrange Scheme

Since

               1 1 1 1 2 0 -2 -4 2 2 0 2 (-2) 2 (-4) 2 2 3 0 3 (-2) 3 (-4) 3 2 4 0 4 (-2) 4 (-4) 4 2 5 0 5 (-2) 5 (-4) 5                        -7 128 105 128 35 128 -5 128         =                1 -1 2 (-1 2 ) 2 (-1 2 ) 3 -13 2 59 2                               1 1 1 1 3 1 -1 - 3
3 2 1 2 (-1) 2 (-3) 2 3 3 1 3 (-1) 3 (-3) 3 3 4 1 4 (-1) 4 (-3) 4 3 5 1 5 (-1) 5 (-3) 5                        -5 128 35 128 105 128 -7 128         =                1 -1 2 (-1 2 ) 2 (-1 2 ) 3 -13 2 13 4               
, this scheme reproduces polynomials of degree 3 and quasi-reproduces polynomials of degree 4, thus the decay rate of the associated prediction error is 5.

Proposition 4.13.

The decimation operator given by (2.14) is stable.

Proof.

The proof is straightforward since the subdivision operator constructed from 2( h3 l ) l∈Z is convergent. Indeed, following the algorithm proposed in [START_REF] Dyn | Subdivision schemes in geometric modelling[END_REF] and with the same notations, we have

max i∈Z j∈Z |b [9] i-2 9 j | = 0.983338 < 1.
It means that S b is contractive after 9 iterations and therefore that the scheme is convergent.

2-point Shifted Lagrange Scheme, B-spline of order 3

Since

        1 1 0 -2 0 2 (-2) 2 0 3 (-2) 3           3 4 1 4   =         1 -1 2 1 -2         ,         1 1 1 - 1
1 2 (-1) 2 1 3 (-1) 3           1 4 3 4   =         1 -1 2 1 -1 2        
, this scheme reproduces polynomials of degree 1 and quasi-reproduces polynomials of degree 2, thus the decay rate of the associated prediction error is 3.

Proposition 4.14.

The decimation operator given by (2.12) is stable.

Proof.

The stability is ensured since the subdivision operator constructed from 2( h2 l ) l∈Z is convergent. The convergence is verified because

∀i 1 , i 2 , i 3 , i 4 ∈ {0, 1}, max ( 1 2 ) 4 ||A (1) i 1 A (1) i 2 A
(1)

i 3 A (1) i 4 || = 0.71987 < 1,
where A

(1) 0 , A

1 are associated refiniment matrices for differences.

Proposition 4.15.

The decimation operator given by (2.13) is stable.

Proof.

The stability is ensured since the subdivision operator constructed from 2( h2 l ) l∈Z is convergent. The convergence is verified because

∀i 1 , i 2 , i 3 , i 4 , i 5 ∈ {0, 1}, max ( 1 2 ) 5 ||A
(1)

i 1 A (1) i 2 A
(1)

i 3 A (1) i 4 A (1) i 5 || = 0.86584 < 1,
where A

(1) 0 , A

1 are associated refiniment matrices for differences.

4-point Interpolatory Lagrange Scheme

Since            1 1 1 1 3 1 -1 - 3
3 2 1 2 (-1) 2 (-3) 2 3 3 1 3 (-1) 3 (-3) 3 3 4 1 4 (-1) 4 (-3) 4                    -1 16 9 16 9 16 -1 16         =            1 0 0 0 -9           
, this scheme reproduces polynomials of degree 3 and quasi-reproduces polynomials of degree 3, thus the decay rate of the associated prediction error is 4.

B-spline Scheme of Order 4

Since

           1 1 1 2 0 - 2
2 2 0 2 (-2) 2 2 3 0 3 (-2) 3 2 4 0 4 (-2) 4                 1 2 1 2 0      =            1 1 2 4 8            ,            1 1 1 3 1 -1 3 2 1 2 (-1) 2 3 3 1 3 (-1) 3 3 4 1 4 (-1) 4                 1 8 3 4 1 8      =            1 1 2 4 11           
this scheme reproduces polynomials of degree 1 and quasi-reproduces polynomial of degree 3, thus the decay rate of the associated prediction error is 4.

B-spline Scheme of Order 5

Since

               1 1 1 2 0 - 2
2 2 0 2 (-2) 2 2 3 0 3 (-2) 3 2 4 0 4 (-2) 4 2 5 0 5 (-2) 5                     5 16 5 8 1 16      =                1 1 2 3 2 2 6 8                ,                1 1 1 3 1 -1 3 2 1 2 (-1) 2 3 3 1 3 (-1) 3 3 4 1 4 (-1) 4 3 5 1 5 (-1) 5                     1 16 5 8 5 16      =                1 1 2 3 2 2 6 31 2               
, this scheme reproduces polynomials of degree 1 and quasi-reproduces polynomials of degree 4, thus the decay rate of the associated prediction error is 5.

B-spline Scheme of Order 7

Since

                     1 1 1 1 2 0 -2 -4 2 2 0 2 (-2) 2 (-4) 2 2 3 0 3 (-2) 3 (-4) 3
2 4 0 4 (-2) 4 (-4) 4

2 5 0 5 (-2) 5 (-4) 5

2 6 0 6 (-2) 6 (-4) 6

2 7 0 7 (-2) 7 (-4) 7                              7 64 35 64 21 64 1 64         =                      1 -1 2 2 -11 4 11 -23 92 -284                                           1 1 1 1 3 1 -1 - 3
3 2 1 2 (-1) 2 (-3) 2 3 3 1 3 (-1) 3 (-3) 3 3 4 1 4 (-1) 4 (-3) 4
3 5 1 5 (-1) 5 (-3) 5

3 6 1 6 (-1) 6 (-3) 6

3 7 1 7 (-1) 7 (-3) 7                              1 64 21 64 35 64 7 64         =                      1 -1 2 2 -11 4 11 -23 92
-821 4                     
, this scheme reproduces polynomials of degree 1 and quasi-reproduces polynomials of degree 6, thus the decay rate of the associated prediction error is 7.

Numerical Tests

Several tests are performed in this section to study the multiresolution analyses associated to the 4-point shifted Lagrange and PPH schemes. The two first ones are related to the numerical investigation of the prediction error decay and of the stability of the multi-scale decomposition transform. The last one is devoted to the evaluation of the performance of the new multiresolutions for image compression.

Decay Rate of the Prediction Error

Starting from a point value discretization of the function displayed in Figure 3.1, a multi-scale decomposition transform is applied from a fine level j = 12 to a coarse one j 0 = 7. Figure 4.1 provides the evolution of the prediction error (in log-scale)

with respect to the level. It appears that the decay rate is larger for the linear approach (slope of 5.0379, to be compared with the theoretical value of 5) than for the non-linear one (slope of 4.21979). This can be explained by the presence of the non-linear perturbation term that reduces the degree of polynomial approximation.

As a comparison, the interpolatory Lagrange approach leads to a slope of 4.00717, to be compared with the theoretical value of 4.

Estimation of the stability constant

Given a sequence f j = (f j k ) k∈Z , we denote f j = ( f j k ) k∈Z a perturbed sequence and { f j 0 , dj 0 , dj 0 +1 , . . . , dj-1 } its associated decomposition. The decomposition stability constant is defined as Since the linear shifted Lagrange decomposition is known to be stable, the similarity between the stability constants associated to the two schemes is a good tendency that leads to think that the non-linear shifted PPH decomposition is stable. with respect to the compression ratio which is the ratio between the size of the original image and the size of the compressed image.

C s = ||f j -f j || 1 ||f j 0 -f j 0 || 1 + j-1 i=j 0 ||d i -di

Image Compression

The results on the first image (Figure 4.7) show that the shifted schemes (that are non-interpolatory) exhibit a better performance than that of interpolatory ones.

Moreover, the shifted PPH scheme outperforms the linear shifted one.

For a sketchy image (Figure 4.8), we get more significant compression ratios while the shifted PPH scheme still outperforms the linear shifted one. In this case, non-interpolatory approaches lead to better results for high compression ratio. It appears that the choice of the linear decimation has a non negligible effect on the capability of the multiresolution. In this test, the decimation given by (2.14) leads to the best results. This clearly indicates that in practice, the construction of 97 the linear decimation has to be carefully chosen before applying Theorem 2. This point will be studied in future investigations.

compression ratio

Conclusion

A generic approach was developed in this chapter to fully construct multiresolution analysis associated to general subdivision scheme. Starting from consistent decimation operators following Theorem 2 of Chapter 3, detail subdivision and detail decimation operators are introduced by exploiting the action of some specific linear decimation on the so-called prediction error. Several theoretical results were then established to ensure polynomial quasi-reproduction and reproduction. This property is important since it controls the prediction error decay rate which was further studied. A special attention was also devoted to the stability of the multi-scale transforms. In order to show the interest of these new developments for practical issues, we finally focussed on two linear (shifted Lagrange) and non-linear (shifted PPH) schemes. The last application illustrated that it is now possible to exploit the advantages of these non-standard subdivision schemes in the framework of image compression.

Conclusion and Perspectives

This thesis was devoted to the construction of a compatible multiresolution framework based on a given subdivision scheme. Because of the diversity of subdivision schemes, different approaches were developed to deal with different kinds of subdivision scheme that can be linear or non-linear. We first focussed on the construction of decimation operators. Exploiting the consistency property between subdivision and decimation, a first approach was introduced in the linear uniform framework.

It was then extended to non-uniform (position-dependent) strategies. Its advantages first stand in the simplicity of its implementation since it relies on the inversion of matrices constructed from the subdivision masks. Moreover, the length of the decimation mask can be fixed beforehand which allows, similarly to subdivision, integrating only the information in the vicinity of the point of interest. For more general linear subdivision scheme, we proposed in a second approach a global method for decimation construction in the sense that it takes into account all the available data in a given interval. It can then be used for any kind of linear subdivision scheme without adapting locally the decimation. This approach remains limited to a small size of data since it involves the inversion of a full matrix. It is therefore more efficient when it is coupled with a zone-dependent strategy [START_REF] Si | Construction and analysis of zone-dependent interpolatory/non-interpolatory stochastic subdivision schemes for non-regular data[END_REF].

Finally, a last approach was proposed in the case of general subdivision scheme (linear or non-linear). Given a subdivision h, the key point is the existence of linear decimation operator hL such that hh -I satisfies a contraction property. Besides the genericity of this method, its main advantage stands in the flexibility of the choice of hL that, as it was shown in numerical studies, can have some influence on the capabilities of the associated multiresolution. To fully complete that connection with subdivision-based multiresolution, so-called detail decimation and subdivision operators were introduced and the resulting multiresolution analyzed (polynomial approximation, prediction error decay, stability of the multi-scale transforms). For practical issues, several examples of standard and non-standard schemes (linear or non-linear) were studied. The last promising test of this thesis showed that it is now possible to define new multiresolution analysis and exploit the advantages offered by subdivision schemes in the framework of image compression.

Future works concern :

• The full analysis of the multiresolution in the non-linear framework : the multi-scale transforms have been constructed but the theoretical analysis of the decomposition stability still remains an open question. Further investigations are also required to derive the prediction error decay rate in the case of the shifted PPH scheme that has only been studied numerically in this thesis.

• The choice of the linear operator in the general method for the construction of consistent decimations : we proposed a method that can be applied in both linear and non-linear frameworks provided there exists a linear decimation hL such that hL h -I satisfies a contraction property. It is therefore important to clarify the relation between hL and the prediction error behavior. It will then be interesting to construct an automatic selection of this linear operator in order to optimize the multiresolution capability. It will also include a theoretical analysis of the contraction property for every considered decimation.

• The coupling between subdivision-based multiresolution and classical strategies used in the wavelet framework : it is now possible to construct the four operators involved in multiresolution analysis. One can then exploit existing strategies such as the lifting scheme [START_REF] Sweldens | The lifting scheme: A custom-design construction of biorthogonal wavelets[END_REF] in order to improve their compression capability.

• The application to image compression : a first numerical test was conducted to decompose and reconstruct images using shifted Lagrange and PPH schemes.

It appeared that non-interpolatory approaches are promising to improve the compression ratio for a fixed PSNR. However, further tests on geometric and real images are necessary to confirm this conclusion. It would be also interesting to consider multiresolutions associated to other non-standard schemes such as the penalized Lagrange one [START_REF] Si | On four-point penalized lagrange subdivision schemes[END_REF] or the kriging one [START_REF] Baccou | Kriging-based interpolatory subdivision schemes[END_REF] that offer the possibility to combine interpolatory and non-interpolatory predictions. A benchmarking of all these different approaches would be valuable to better clarify their advantages and limitations as well as the specific situations where they should be used.

Otherwise, k p i=0 p i j hj (j -t) i (-1) i h 2k+j (2k + j -t) p-i = δ p,0 , if h 2k+j (2k + j -t) p-i does not depend on the parity of j, By expanding it with respect to each n ≤ L, we know that for h being fixed, l h k-2l (k -2l) i should not depend on the parity of k for all i ≤ L which leads to (4.4).

Let us first introduce the following notations,

  Thanks to China Scholarship Council (CSC) for their financial support. i List of Figures 1.1 Left: Interpolatory Lagrange subdivision with Gibbs phenomenon, Right: Interpolatory PPH subdivision avoiding the Gibbs phenomenon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Six coefficients of the mask of a decimation operator consistent with the penalized Lagrange subdivision scheme for scale -10 ≤ j ≤ 10. 3.1 Left : Discontinuous test function, Right : Construction of the nonlinear decimation operator : log 2 ||f j n -f j n-1 || ∞ versus n for the fixedpoint algorithm (3.3). . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Logarithm of the prediction error versus scale for different schemes : 4-point shifted PPH, 4-point shifted Lagrange and 4-point interpolatory Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Various test functions : from top to bottom, the function is less regular. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Evolution of the prediction error (log-scale) versus scale in the vicinity of point x 0 = 0.5 associated to the test functions of Figure 4.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Test functions with discontinuity at point x 0 = 0.5. . . . . . . . . . 4.5 Evolution of the prediction error (log-scale) versus scale in the vicinity of point x 0 = 0.5 associated to test functions of Figure 4.4 . . . 4.6 Perturbed sequence constructed from the 10-th column of image stream (left) and image texmos3 (right), noise in blue and origin data in green . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Left : test image stream, Right : PSNR versus compression ratio for interpolatory Lagrange, shifted Lagrange, interpolatory PPH and shifted PPH multiresolutions. . . . . . . . . . . . . . . . . . . . . . vii 4.8 Left : test image texmos3, Right : PSNR versus compression ratio for interpolatory Lagrange, shifted Lagrange, interpolatory PPH and shifted PPH multiresolutions. . . . . . . . . . . . . . . . . . . . . . 97 4.9 PSNR versus compression ratio for the 4-point shifted PPH subdivision scheme with three different consistent decimation operators, stream image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 viii Notations h, h L , h N subdivision operator, linear, non-linear subdivision h, hL decimation operator, linear decimation g detail subdivision operator g detail decimation operator I identity operator, identity matrix

  xy ≤ 0 2xy x+y , if xy > 0 A(x, y) arithmetic mean A(x + y) = x+y 2 π n space of polynomials of degree no more than n k = e 2k+1 (σ e) k = e 2k X, X matrix of σ, σ τ (•, •) interlacing operator (τ (u, v)

  imitant les analyses en ondelettes, fournit une décomposition multi-échelle d'un signal, d'une courbe ou d'une surface. Les ingrédients nécessaires à la définition d'une analyse multiresolution associée à un schéma de subdivision sont des schémas de décimation et de détails. Leur construction est facile quand le schéma de multiresolution est interpolant. Cette thèse est consacrée à la construction de schémas de décimation et de détails compatibles avec un schéma de subdivision le plus général possible. Nous commençons par une construction générique dans le cas d'opérateurs homogènes (mais pas interpolants) puis nous généralisons à des situations non-homogènes et nonlinéaires. Nous construisons ainsi des analyses multiresolutions compatibles avec de nombreux schémas récemment développés. L'analyse des performances des analyses ainsi construites est effectuée. Nous présentons des applications numériques en compression d'images.

Chapter 1

 1 is devoted to an overview of the different mathematical elements involved in multiresolution associated to subdivision, including decimation and details. Definitions and related properties are provided. Different examples of subdivisions including interpolatory, non-interpolator, linear, non-linear, uniform, non-uniform as well as examples related to wavelet multiresolution analysis are described. Meanwhile, some well known results for those examples are also mentioned.

Figure 1 . 1 :

 11 Figure 1.1: Left: Interpolatory Lagrange subdivision with Gibbs phenomenon, Right: Interpolatory PPH subdivision avoiding the Gibbs phenomenon.

  where m is even by considering { hn-m+1 , . . . , hn-m+2α-2 , hn-m+2α-1 , 0}, and replacing m -1 by m . The same kind of argument holds when hn-m+2α-1 = 0 by considering {0, hn-m , . . . , hn-m+2α-2 , hn-m+2α-2 } .

. 10 )

 10 According to Proposition 2.1, h * = h-λ h + λ h is consistent with h. Since M h has length 2β + 2, M h * has length 2β from index m -2β + 2 to m + 1. If β = α,M h * and M h have the same length and indices. According to Proposition 1, h * = h and h = λ h + (1 -λ) h , which leads to the expected result with a zero second term. If β > α, M h * has a shorter length than M h and h = λ h -λ h + h * , that allows us to iterate by replacing h with h * and then to conclude.

Figure 2 . 1 :

 21 Figure 2.1: Six coefficients of the mask of a decimation operator consistent with the penalized Lagrange subdivision scheme for scale -10 ≤ j ≤ 10.

Proposition 3 . 1 . 1 0and H - 1 1Proposition 3 . 2 .

 311132 l and l are supposed to be large enough to take into account at least a uniform prediction for the last (resp. first) element of the previous finite sets. The following result then holds, Let h be a linear position-dependent subdivision scheme. If H 0 and H 1 are invertible, H -provide decimation masks consistent with the subdivision in the vicinity of the segmentation point. Introducing the set of index I 0 ⊂ {1, 2, . . . , l} (resp. I 1 ⊂ {-l +1, -l +2, . . . , 0}) such that each element of {f j+1 k } k∈I 0 (resp. {f j+1 k } k∈I 1 ) is predicted using a uniform subdivision, we then have, Let h be a linear position-dependent subdivision scheme satisfying the assumption of Proposition 3.1 and hu a decimation operator consistent with the associated uniform subdivision. Denoting k * 0 = min(I 0 ) and k * 1 = max(I 1 ), if ( hu k ) k∈Z is such that hu n-2(l+1) = 0, ∀n ≤ k * 0 and hu n+2l = 0, ∀n ≥ k * 1 , then the decimation constructed from Proposition 3.1 and Theorem 1 is consistent with the position-dependent subdivision operator.

( 1 )

 1 x, a > 0, y, b < 0, then H(x, y) = H(a, b) = 0, |(H(x, y) -A(x, y)) -(H(a, b) -A(a, b))| ≤|A(x, y) -A(a, b)| ≤max(|x -a|, |y -b|).

Figure 3 . 1 :

 31 Figure 3.1: Left : Discontinuous test function, Right : Construction of the nonlinear decimation operator : log 2 ||f j n -f j n-1 || ∞ versus n for the fixed-point algorithm (3.3).

Remark 4

 4

( 4 .

 4 [START_REF] Catmull | Recursively generated b-spline surfaces on arbitrary topological meshes[END_REF]) is equivalent to ∀i ∈ {0, 1, 2, . . . , L}, m hm (m -t) i = δ i,0 .According to Lemma 4.1, this is equivalent to (4.9). Remark 4.4. 1. If i = L in (4.11), we have b L = a L ( m h m ), that is to say if the decimation operator reproduces constants, it always preserves the leading coefficient. Other coefficients are given by (4.11). 2. If t = 0, h reproduces the same polynomial without translation, in this case, ∀n ∈ {0, 1, 2, . . . , L}, l∈Z hl l n = δ n,0 . The following proposition exhibits the connection between polynomial (quasi) reproduction of consistent subdivision and decimation, Proposition 4.4.

( 4 . 14 )

 414 with l and k of same parity. (4.12) is deduced directly and (4.13) follows from the equivalence to ∀n ∈{0, 1, 2, . . . , L},l∈Z h 2l m∈Z hm (m -2l -t) n = l∈Z h 2l+1 m∈Z hm (m -2l -1 -t) n = δ n,0 under the condition ∀i ≤ L, b i = a i .Remark 4.5. If t = 0, h h reproduces the same polynomial without translation, in this case, ∀n ∈{0, 1, 2, . . . , L}, l∈Z h 2l m∈Z hm (m -2l) n = l∈Z h 2l+1 m∈Z hm (m -2l -1) n = δ n,0 . (4.15) By considering the definition of subdivision and decimation, a more commonly used formulation of (4.15) is ∀k, n ∈ {0, 1, 2, . . . , L}, l h k-2l m hm-2l (m -k) n = δ n,0 .According to Proposition 4.

Figure 4 . 1 :Figure 4 . 2 :

 4142 Figure 4.1: Logarithm of the prediction error versus scale for different schemes : 4-point shifted PPH, 4-point shifted Lagrange and 4-point interpolatory Lagrange

Figure 4 . 3 :Figure 4 . 4 :

 4344 Figure 4.3: Evolution of the prediction error (log-scale) versus scale in the vicinity of point x 0 = 0.5 associated to the test functions of Figure 4.2.

Figure 4 . 5 :

 45 Figure 4.5: Evolution of the prediction error (log-scale) versus scale in the vicinity of point x 0 = 0.5 associated to test functions of Figure 4.4

Figure 4 . 6 :

 46 Figure 4.6: Perturbed sequence constructed from the 10-th column of image stream (left) and image texmos3 (right), noise in blue and origin data in green

Four multiresolution frameworks are

  considered in this section. They are associated to the following subdivisions and decimations, interpolatory Lagrange the 4-point interpolatory Lagrange subdivision scheme associated to the mask (1.6) and the consistent subsampling decimation. shifted Lagrange the 4-point shifted Lagrange subdivision scheme associated to the mask (1.7) and the consistent decimation associated to the mask (2.14). interpolatory PPH the 4-point interpolatory PPH subdivision scheme and the consistent subsampling decimation. shifted PPH the 4-point shifted PPH subdivision scheme given by (1.10,1.11) and the consistent decimation constructed from Theorem 2 involving the linear decimation (2.14).Starting from an image of size 512 × 512 (j = 9), several decompositions are first performed until j 0 = 5. Then, after truncation of the detail coefficients with different thresholds, the reconstruction transform is applied and the resulting image is compared to the original one. The performance of each tested approach is evaluated by computing the so-called PSNR (Peak Signal Noise Ratio) defined as

Figure 4 . 7 :

 47 Figure 4.7: Left : test image stream, Right : PSNR versus compression ratio for interpolatory Lagrange, shifted Lagrange, interpolatory PPH and shifted PPH multiresolutions.

Figure 4 . 8 :

 48 Figure 4.8: Left : test image texmos3, Right : PSNR versus compression ratio for interpolatory Lagrange, shifted Lagrange, interpolatory PPH and shifted PPH multiresolutions.

Figure 4 .

 4 9 displays the evolution of the PSNR with respect to the compression ratio for those multiresolutions.

Figure 4 . 9 :

 49 Figure 4.9: PSNR versus compression ratio for the 4-point shifted PPH subdivision scheme with three different consistent decimation operators, stream image

jLemma B. 2 . 1 .

 21 hj (j -t) p = δ p,0 =⇒ k h 2k+j (2k + j -t) p = δ p,0 , which completes the proof.The Proof of Theorem 4 is based on the following lemma.We have, 1. (4.15) leads to (4.4).2. (2.3) and (4.4) leads to (4.15).Proof. According to equation (4.15), ∀k, n ≤ L, ((m -2l) -(k -2l)) n 2l) i (k -2l) n-i (-1) n-i = i n i l h k-2l (k -2l) n-i m hm-2l (m -2l) i (-1) n-i .

h

  -2l -1) n .108where E e,o is associated with even indices of M h and odd indices of M h.First we will prove that the consistency condition(2.3) implies ∀n ∈ N, E n e,e + E n o,o = δ n,0 . (B.1)It is easy to verify that for n = 0, E 0 e,e + E 0 o,o = 1. Moreover, for any n ∈ N * , the consistency condition leads toj ( i h i-2j hi )(2j) n = j δ j,0 (2j) n , i ( j h i-2j (2j) n ) hi = 0 .Splitting the previous sum with respect to even and odd indices, we geti ( j h 2i-2j (2j) n ) h2i + i ( j h 2i+1-2j (2j) n ) h2i+1 = 0, l h 2l k h2k (2k -2l) n + l h 2l+1 k h2k+1 (2k -2l) n = 0,which is precisely, E n e,e + E n o,o = 0 . Considering (B.1), condition (4.15) with ∀0 ≤ n ≤ L, E n e,e + E n e,o = δ n,0 , E n o,e + E n o,o = δ n,0 . (B.2) becomes ∀n ∈ {0, 1, 2, . . . , L} l h 2l kh2k (2k -2l) n = l h 2l+1 k h2k (2k -2l -1) n , i (2k) n-i (2l + 1) i , ) i (2k + 1) n-i (2l + 1) i . 2l (2l) il h 2l+1 (2l + 1) i ) k h2k+1 (2k + 1) n-i = 0,which shows the equivalence between (4.4) and (4.15) under condition (2.3).

Table 4 .

 4 || 1 2: Estimation of the stability constant for the decomposition associated to the shifted PPH and the shifted Lagrange schemes based on image texmos3 This constant is evaluated for different columns of the images stream (Figure 4.7)

	.

and texmos3 (Figure

4

.8) where the perturbation is obtained by adding a white gaussian noise (N (0, 10)). Figure 4.6 shows an example of f j constructed from the 10-th column of each image. The numerical estimations of the decomposition stability constant are shown in

Table 4.1 and Table 4.2 for each image considering shifted PPH (SPPH) and shifted Lagrange schemes (SLAG).

Operator U : l ∞ (Z) → l ∞ (Z) is said to be contractive if there exists c ∈ R, 0 < c < 1, for all (u, v) ∈ (l ∞ (Z))

, such that ||U u -U v|| ≤ c||u -v||.

).

Acknowledgements

I would like to express my sincere gratitude firstly to my supervisor, Professor Jacques LIANDRAT, for giving me this opportunity to do my research in France

Remark 2.4.

The values {λ 1 , λ 2 , λ 3 , λ 4 } = { 1 100 , 47 300 , 47 60 , 1 20 } minimize 3 i=-6 | hi | to the value 163 40 . The corresponding decimation operator gets a smaller stability constant than any of the elementary decimation for which the stability constants are [START_REF] Cohen | Biorthogonal bases of compactly supported wavelets[END_REF][START_REF] Baccou | Position-dependent lagrange interpolating multiresolutions[END_REF][START_REF] Baccou | Position-dependent lagrange interpolating multiresolutions[END_REF][START_REF] Cohen | Biorthogonal bases of compactly supported wavelets[END_REF].

B-spline Subdivision of Order 7

The B-spline subdivision scheme of order 7 corresponds to mask Applying Theorem 1, Chapter 3

Consistent Decimations for

General Subdivision Schemes

Introduction

A general subdivision scheme can be non-linear, non-uniform, non-stationary etc..

In this chapter, several approaches are introduced to construct consistent decimations for those types of schemes.

The first approach (Section 3.2) is devoted to an extension of the previous uniform generic method to handle the decimation associated to linear non-uniform subdivision scheme following a position-dependent strategy [START_REF] Baccou | Position-dependent lagrange interpolating multiresolutions[END_REF]. In Section 3.3, we introduce a global approach that can be exploited for any kind of linear subdivision scheme applied on an interval. Finally, a last contribution is provided in Section 3.4 that allows the construction of decimation for non-linear frameworks.

Non-Uniform Subdivision Schemes

Construction

We focus on specific non-uniform subdivision schemes constructed following a positiondependent strategy [START_REF] Baccou | Position-dependent lagrange interpolating multiresolutions[END_REF]. This type of scheme was developed for non-regular data.

The construction relies on the adaption of the prediction stencil to avoid crossing segmentation points and generating Gibbs oscillation in the vicinity of these points.

The subdivision process involves the so-called refinement matrices studied in Section 2.2.5 as well as edge matrices that are associated to the prediction around

(

(

combining the previous cases with (2.14) leads to

Moreover, if the decimation mask is given by (2.15), we have

Proposition 3.6.

Denote h = h L +h N the reformulation of the 4-point shifted PPH subdivision scheme given by (1.12), if hL is given by (2.11), then hL h N is contractive.

Proof.

With the same notations as in the previous proof, we have

And

According to proposition 2 of [START_REF] Amat | On a nonlinear subdivision scheme avoiding gibbs oscillations and converging towards c s functions with s > 1[END_REF],

Numerical Convergence of the Fixed-point Iteration

Starting from a discretization of the discontinuous function displayed in Figure 3.1 left, we investigate the numerical convergence of the fixed-point algorithm (3.3) in the case of the 4-point shifted PPH when hL is given by (2.14).

The slope of the curve displayed in the right of Figure 3.1 exhibits the convergence rate of the algorithm. It appears that very few iterations (less than 17) are required for convergence.

example exploit the work of [START_REF] Sweldens | The lifting scheme: A custom-design construction of biorthogonal wavelets[END_REF] on the lifting scheme and consider the compatible operators (h, h + sg, g -sh, g), s ∈ R. Similarly, one can show that (h + sg, h, g, g -

All these strategies allow integrating more flexibility in the construction and could be interesting to increase the performance of multiresolution analysis in practical situations. This last point has not been tested in this thesis and remains an open question for further investigation.

Polynomial Reproduction of Linear Uniform Multiresolution

We first establish a series of results on the polynomial reproduction and quasireproduction of subdivision and decimation operators. Then we focus on the operator h h that is involved in the multiresolution transform in Section 4.3.2.

Subdivision and Decimation Operators

Let us first prove the following lemma, Lemma 4.1.

For a finite set {c

Proof.

It is easy to verify that

For all (f 0 l 0 ) l 0 ∈Z ∈ V 0 decimated from V j by hj ,

hj l-2 j l 0 f j l .

(4.18)

Since (h l ) l∈Z is constructed by 2( hl ) l∈Z , we have

which leads to the stability of decimation h.

The assumption on the stability of the subdivision associated to 2( hl ) l∈Z can be replaced by a general condition that can be more easily satisfied in practice. Let us first introduce the following useful lemma.

Lemma 4.2.

Let h be a decimation operator, the operator hi , i ∈ N * stands for its i-th iteration.

Then the decimation operator h is stable if and only if hi is stable.

Proposition 4.10.

The decimation operator h is stable if and only if there exists i ∈ N * , such that the subdivision h constructed from sequence 2( hi l ) l∈Z is stable.

Proof.

The proof is straightforward by taking j = ik in the proof of Proposition 4.9, since (4.18) can be rewritten as

and the necessity is concluded by Lemma 4.2.

Appendix A Alternative Proofs

Proof of the consistency condition (Proposition 2.1) using

Laurent polynomial

Denote

and

Equation (2.1) leads to

and equation (2.2) leads to

The consistency condition implies that

With a little calculation, i,j

and finally,

Equivalence with polynomial quasi-reproduction using Laurent Polynomial

Denote h(z) = l h l z l , then its d-th derivative is

Let's consider

where s(d, m) denotes the Stirling numbers of the first kind.

By recurrence, we have ∀n ∈ {0, 1, 2, . . . , L}, l∈Z h l l n (-1) l = 0.

which is equivalent to (4.4).

Finally, we have the equivalence between condition (4.4) and ∀d ∈ {0, 1, 2, . . . , L}, h (d) (-1) = 0.

Appendix B Calculation Details

The proof of Proposition 4.4 is based on the following lemma.

Lemma