Olivier Glassey
email: olivier.glassey@idheap.unil.ch

A One-Stop Government prototype based on use cases and scenarios

INTRODUCTION

In previous work we defined a conceptual model of a One-Stop Public Administration, putting the accent on both the structural and behavioural aspects of such a system. We had decided to work on such a model because we believe that there is a need for conceptual methodologies in that field: various researches are being conducted, such as the GAEL (Guichet Administratif En Ligne) project in Switzerland [Chappelet & Le Grand, 2000] or the BTÖV (Bedarf für Telekooperation in der Öffentlichen Verwaltung) method in Germany [Gräslund & al., 1996]. Indeed many researchers and public administrations need a stable model of processes that can help public administrations managing the complexity and the rapid evolution of new technologies. This is also what a Swiss working group on egovernment appointed by the federal government thinks [GSCI, 2000]. Furthermore this group identifies the definition of patterns for such applications as one of three essential action domains for e-government.

During our modelling work, we took into account the internal processes of an administration, its relations with the customers and the expectations of the citizens: we made a six month survey in the "Administration Cantonale Vaudoise" (ACV), a large public administration at the cantonal level in Switzerland. There we met project managers, domain managers, departmental managers and users representatives for a total of 28 formal interviews. We also had many casual talks with different civil servants. Moreover we conducted two online surveys (1998 and 2000) in order to discover the expectations of the citizens in the field of electronic administrative services and we had close to 500 questionnaires to analyze. We also took into account the different targets that a One-Stop public administration can have (citizens, businesses, civil servants, other administrations, etc.) and the different distribution canals (Internet, wireless, public kiosks, administration's Intranet and so on). Using that field data we filled in "summary cards", inspired by CRC cards (Class-Responsibilities-Collaborators). For more information on this technique, we recommend [Bellin & al., 1997]. First these cards helped us collecting the input from the various people we met and transforming it into a structural model through an iterative abstraction process. We defined this class model using the Unified Modeling Language (UML), developed by [START_REF] Booch | [END_REF]. Then we used the cards to create use cases and scenarios following the methodology developed by [START_REF] Kulak | [END_REF]]. We will not go into the details of this model because it is not the aim this paper where we want to explain how we built a prototype based on this model. In order to validate and to refine the conceptual model we decided to build a small system of a one-stop public administration and throughout this paper we will explain the different steps of this work. It has to be noted that it is only small prototype will limited functionalities, because we lacked the resources to develop a full-scale system. However we think that the interest of this paper is focused on the methodology we used to build the prototype rather that on the final system. That is also why we will not show any implementation details and we will stay at the general software architecture level.

USE CASES AND SCENARIOS

We wanted to illustrate rather typical Information-Communication-Transaction administrative services and we selected ten functionalities that we wanted to be part of the prototype. For each one of these we built use cases, scenarios and sequence diagrams. Here we shortly explained why we chose these particular functionalities even though they may seem quite simple :

 Content publication : this functionality is typical of Information services and it demonstrates problems of content management, validation, update and access rights, as well as the ability of non-technical persons to publish content without specific knowledge.  Directory : this service is at the border of Information and Communication services as the clients can get in contact with the administration from within the directory by email, but they can also phone, fax or send postal mail; we also found during our surveys of the citizens that it was one of the most expected service.  Calendar : this tool illustrates typical problems of dynamic content (Information) management and interfaces with databases; it is also at the interface with the following point, as a client can add public events to his personal agenda and, by doing so, receive a reminder.  Appointments and personal agenda : the ability for a user to have his own agenda is a limited personalization capability in the prototype; the fact that a client can propose an appointment to a civil servant is the beginning of a very simple workflow (or very limited Transaction services).  Validation and acceptation of an appointment : this shows limited workflow functionalities and interactions with a human actor, for the system checks for conflicts in appointments and a person in charge validates it before the user receives a confirmation.  Discussion forums : this Communication service is an interesting feature because many forums are third party software and sometimes remotely hosted, so it allowed us to show the integration of commercial components or application in a One-Stop public administration.  Chat : basically we chose to add a chat to the prototype for the same reasons as above, with the idea of a future integration with the agenda, allowing the client to make an appointment for a official chat with a civil servant, which would provide advance Communication services.  Search engine : this is a very useful feature to find one's way in the mass of information provided by online government and it shows the ability to integrate distant functionalities within our prototype; a search engine is quite simple, but we can imagine to add a payment or a certification "engine" in a real system, which are necessary tools to support complex Transaction services.  Official forms : official forms are the bases of a public administration's operations and they are at the convergence of Information, Communication and Transaction services; they are also the most requested feature that came out of our surveys.  Tax declaration : this is the only really Transaction service of the prototype and we added it because it helped us illustrate the integration of legacy systems (we developed a prototype of tax declaration in 1997).

For each of these ten functionalities we created use case diagrams such as shown in Fig. 1 and we developed basic scenarios [Fig. 2], but here we will only show them for the first feature of the prototype. The use case diagrams and the scenarios are very useful to have a common language between technical persons, users, managers and leaders. They also provide a solid basis for a posteriori tests and validation of a system.

Figure 1 : Use case diagram

Use case name Content publication

Abstract

The public worker (or service provider in our terminology) publishes content on the Web: news, job offers, etc. The client can consult this content online after it as been validated by a person in charge.

Normal sequence of events

1. The provider publishes new content 2. The content is validated 3. The content is made available online 4. The client consults the content he is interested in.

Alternate sequence

4. The client does not consult any content

Exception handling

At step 2, the content does not go online if it is not validated. A specific procedure begins.

Triggers Assumptions Preconditions

New content has to be published.

Postconditions

Content is accessible on line.

Authors and date

Olivier Glassey, February 12th, 2002

Figure 2 : Basic scenario

In order to complete the scenarios, which show in what order a procedure is accomplished, we defined business rules [Fig. 3] to explain how a particular activity is conducted, using the methodology developed by [Ross, 1997].

Business rule Job offer publication

Short description

All job positions to be filled must be made publicly available, event if they are filled internally later on.

Source

Job regulation in public administrations As we mentioned above, we created such diagrams for each of the ten functionality of the prototype, then we used our structural model in conjunction with a CASE tool to create the class model of our prototype. This allowed us to generate its software "backbone", but we also needed to define logical software architecture before we started to really implement this system.

Type

ARCHITECTURE OF THE PROTOTYPE

We needed a software architecture that allowed us to take into account the following constraints, that we had found were very strong in public administrations :  Ability to access heterogeneous applications and platforms  Simple user interface and openness to the Internet  Use of standard and robust technologies  Modularity et scalability

To create the middleware layer we chose a distributed component architecture because it fitted our needs best and because there are really strong standards on the market. We will not present the characteristics of this architecture here, but we recommend [Fingar & Stikeleather, 1996] which is one of the foundation papers of this model. The three main components communication models are CORBA from the Object Management Group, COM+ (and now .NET) from Microsoft and Java/RMI for Sun Microsystems. Neither will we discuss these here, as there is an excellent comparison in [Suresh Raj, 1998]. Let us just say that for reasons of resources and simplicity we built our prototype using the COM+ model for the back-office applications. To be able to distribute these services to the clients we decided to build a dynamic Web interface based on the PHP/MySQL couple (respectively a server script language and a database, both of which are Open Source). The output displayed in the enduser interface is pure HTML, which means that it can be read by any browser such as Internet Explorer, Netscape or Opera. Figure 5 shows the general logical architecture of the prototype and of its functionalities. For most of the system, we adapted existing PHP applications (which can be seen also as components) : forum, chat, calendar, directory, content publication tools and access to the official forms. On the other hand, the tax declaration application we built in 1997 was written in Delphi and used the ODBC gateway to connect to a Microsoft Access database and a Logic Server to retrieve calculation rules in Prolog. We simply wrote a COM component that encapsulates this application and is able to be distributed over the Internet using the ASP scripting language. We also added a commercial component called ASLogin that allowed us the secure the tax declaration pages. Finally we added the Google search engine in our prototype. We will not go into anymore details regarding the implementation of this prototype as this is rather a "toy" compared to real systems and because we think the interesting concept here is the general architecture : it allowed us to integrate various commercial and Open Source components and applications into what appears to be a unified and transparent system with a single interface.

OPERATION OF THE PROTOTYPE

The prototype can be tested at http://uts.unil.ch/vade/, but it is only available in French. Here we will briefly describe its operation and show how users with different access rights can accomplish various tasks within a single interface. Let us mention that we made no particular work on the ergonomics of the prototype as it was not our intent. We used very classical navigation techniques with a left menu based on the Information-Communication-Transaction typology and an upper menu that shows the hierarchy of the pages. We realise that this is not entirely satisfying and we will work on a different interface in the future, most likely based on the "life events" metaphor.

The first screen [Fig. 6] shows the interface that a regular client (with no particular rights) sees when he chooses to see the latest news. The second one [Fig. 7] shows how a user with specific access right can publish new content within the same interface. Without any HTML knowledge he or she can publish text, links or images that will be validated before going online. Another example (not shown here) of clients with different access rights using a similar interface is the directory : a regular client can only browse or search the directory when selected civil servants have the access to add, edit or delete entries, in that case with additional links in the interface. The prototype in itself does not show anything very impressive, but we think that its strong point is the concept of a single and universal interface that can be used via any distribution channel and by any type of client.

CONCLUSIONS

What we have shown in this paper is the application of a conceptual model and methodology to a practical case of One-Stop Government. The result of this work is a simple but functional prototype. We now want to emphasize what we believe are the strong points of this work.

First we think that it is almost necessary to find a common language between technical persons, users and managers, and we found that the use of graphical models developed in UML provide a good way to achieve that. We also found that scenarios and sequence diagrams, although they are simple enough to be understood by anyone, are a great basis for software engineers to conceptualise and implement information systems that satisfy the needs of their users. We also realised that we needed a solid and standard logical architecture in order to integrate heterogeneous applications and software components into a seemingly unique One-Stop Government system. Furthermore we think that, in order for this system to be accessible from anywhere and by anyone via a standard user interface, the best choice was to use a middleware layer interfaced with the Internet. In the future it is also very likely that this middleware will have to be interfaced with wireless technologies. Thus the architecture we chose allowed us to build a dynamic and universal interface that constitutes a single entry point to very heterogeneous electronic administrative services, providing true One-Stop Government capabilities.

FactFigure 3

 3 Figure 3 : Business rule

Figure 4 :

 4 Figure 4 : Sequence diagram

Figure 5 :

 5 Figure 5 : Architecture of the prototype

Figure 6 :

 6 Figure 6 : Interface to access content

Figure 7 :

 7 Figure 7 : Interface to publish content


Basarab Mateï
email: matei@math.univ-paris13.fr

Sylvain Meignen
email: sylvain.meignen@imag.fr

Anastasia Zakharova
email: anastasia.zakharova@gmail.com

Interpolatory Nonlinear and Non-Separable Multi-scale Representation: Application to Image Compression

Keywords: Nonlinear multi-scale representation, image compression, EDICS Category:TEC-MRS B, Multi-Resolution Analysis

In this paper, we introduce the notion of nonlinear and non-separable multi-scale representation. We show how it can be derived from nonlinear and non-separable subdivision schemes associated to a non-diagonal dilation matrix. We focus on nonlinear multi-scale decomposition where the dilation matrix is either the quincunx or the hexagonal matrix. We then detail the encoding and decoding algorithm of the representation and, in particular, how the EZW (Embedded Zero-tree Wavelet) algorithm adapts in that context. Numerical experiments on image compression conclude the paper.

I. INTRODUCTION

Due to the hierarchical structure of visual information, the multi-scale representations are widely applied in image processing [START_REF] Cohen | Quasi-linear Subdivision Schemes with Applications to ENO Interpolation[END_REF][1] [START_REF] Chan | ENO-Wavelet Transforms for Piecewise Smooth Functions[END_REF]. Images are bidimensional complex objects made of homogeneous regions separated by smooth singularities. It is then natural to process them using techniques which are intrinsically bidimensional and are adapted to the information contained in an image. The multi-scale representations based on the tensor product of wavelet bases are not well adapted to process efficiently an image near the singularities. In order to have a better treatment of singularities, A. Harten in [START_REF] Harten | Discrete Multiresolution Analysis and Generalized Wavelets[END_REF] [START_REF] Harten | Uniformly high order accurate essentially non-oscillatory schemes III[END_REF] introduced a general framework to multi-scale data representations. The idea is to associate to any function v, a set of sequences Mv := (v 0 , d 0 , d 1 , d 2 , . . .), where the sequence v 0 := (v 0 k ) k∈Z d is the coarsest approximation of v and the sequences d j := (d j k ) k∈Z d , with j ≥ 0, are additional detail coefficients which represent the fluctuations of v between two successive levels of resolution.

There exist many ways to build such nonlinear representations. In most papers, the multi-scale structure is associated to dyadic levels of resolution [START_REF] Harten | Discrete Multiresolution Analysis and Generalized Wavelets[END_REF] [START_REF] Cohen | Quasi-linear Subdivision Schemes with Applications to ENO Interpolation[END_REF]. In [START_REF] Chappelier | Oriented Wavelet Transform for Image Compression and Denoising[END_REF], the quincunx matrix is used to define the levels, and then a multi-scale representation is proposed. In the present paper, we build multi-scale representations either based on quincunx or hexagonal dilation matrices. The general philosophy of the approach, is to predict at a fine level using only coarser levels and to memorize prediction errors as detail coefficients.

The approach we propose is therefore well adapted to progressive transmission of data.

We first recall some definitions about nonlinear subdivision operators in a non-separable framework and we will explain how this entails the convergence of multi-scale representations associated to such operators. We will then give applications to interpolatory multi-scale representations corresponding to quincunx or hexagonal dilation matrices. In particular, we will study affine interpolatory scheme and also interpolation using polynomial of total degree two. The whole procedure from the encoding of the representation, to the compression step and, finally, to the decoding step will be detailed. In particular, we will show how the EZW (embedded zero-tree wavelets) adapts in our context. Some illustrations on image compression conclude the paper.

II. NOTATIONS AND MULTI-RESOLUTION ANALYSIS DEFINITION

A. Notations

Let ℓ(Z d ) be the space of all sequences indexed by Z d . The subspace of bounded sequences is denoted by ℓ ∞ (Z d ) and u ℓ ∞ (Z d ) is the supremum of {|u k | : k ∈ Z d }. We denote ℓ 0 (Z d ) the subspace of all sequences with finite support (i.e. the number of non-zero components of a sequence is finite). As usual, let ℓ p (Z d ) be the Banach space of sequences u on Z d such that u ℓ p (Z d ) < ∞, where

u ℓ p (Z d ) := k∈Z d |u k | p 1 p for 1 ≤ p < ∞.
For any w ∈ ℓ p (Z d ) d we will denote w ℓ p (Z d ) d , the supremum of the ℓ p -norm of the components of w. As in the discrete case, we denote by L p (R d ) the space of all measurable functions f such that 1) The subspaces are embedded V j ⊂ V j+1

f L p (R d ) < ∞,
2) f ∈ V j if and only if f (M.) ∈ V j+1

3)

∪ j∈Z V j = V . 4) ∩ j∈Z V j = {0} 5)
We assume the existence of a compactly supported function ϕ ∈ V 0 such that the family of their translates {ϕ(• -k)} k∈Z d forms a Riesz basis for V 0 .

From V 0 ⊂ V 1 , it follows that the function ϕ, called scaling function, satisfies:

ϕ(x) = n∈Z d g n ϕ(M x -n), with n g n = m. (1)
To build the approximation of a given function v at level j, we adopt the biorthogonal point of view that is we assume the existence of a dual function φ with compact support satisfying:

φ(x) = k∈Z d h k φ(M x -k), with k h k = m, (2)
and such that the following duality property holds < φ(x -n), ϕ(x -k) >= δ n,k , where δ n,k denotes the Kronecker symbol and < ., . > the Euclidean inner product. The approximation at level j can be obtained by projection of v on V j as follows:

v j = n∈Z d v j n ϕ(M j x -n) (3)
where v j k = m j < v, φ(M j x -k) >. Note that when φ is fixed, ϕ is a priori not unique which leads to potentially different v j .

III. MULTI-SCALE REPRESENTATION USING DILATION MATRIX M

Let (Γ j ) j=0,•••,J be the set of embedded grids with Γ j = {M -j k, k ∈ Z d }, J corresponding to the finest level of resolution. We now define the projection and prediction operators on these grids.

A. Projection and Prediction Operators

Let (Γ j ) j=0,•••,J be the multiresolution structure defined above and then v J = (v J k ) k∈Z d the data at the finest level J. The value v J k is associated to the location M -J k on the grid Γ J . In order to build the multi-scale representation of v J , we assume the existence of two discrete interscale operators:

1) the projection P j j-1 operator acting from fine to coarse level. If vj is an approximation of v j on Γ j , we define v j-1 = P j j-1 vj . This operator is always assumed to be linear. In our context, φ defined in (2) fixes the projection operator as follows:

v j-1 k := (m) -1 n∈Γ j h n-M k vj n . (4)
2) the prediction P j-1 j operator acting from coarse to fine level. This operator computes vj = P j-1 j v j-1 and may be nonlinear.

We further assume that these two operators satisfy the consistency property: the projection of v j on Γ j-1 coincides with v j-1 , i.e.

P j j-1 P j-1 j = I. (5)
Note that the prediction error e j = v j -vj , is not arbitrary data on Γ j . Indeed, from ( 5), one has

P j j-1 e j = P j j-1 v j -P j j-1 vj = v j-1 -v j-1 = 0.
Hence, e j ∈ Ker(P j j-1 ). It follows that we may write this error in a non-redundant way using a basis of Ker(P j j-1 ). The coefficients of the errors in this kernel gives the detail coefficients d j-1 . Consequently, the data v j is completely equivalent to (v j-1 , d j-1 ). Iterating this process from the initial data v J , we obtain its nonlinear multi-scale representation

Mv J = (v 0 , d 0 , • • • , d J-1 ).

B. Interpolatory Multi-scale Representations

We now introduce interpolatory multi-scale representations. In that context, the data at level j is:

v j k = v(M -j k),
for any k in Z d . From this, we directly obtain the form of the projection operator (P j j-1 ):

v j-1 k = v(M -j+1 k) = v j M k
In that context, the principle of the multi-scale representation is based on the prediction of v j M k+ε for ε = 0 using the values of v j-1 on Γ j-1 0 . Knowing the prediction operator P j-1 j , we then replace the value of v j M k+ε , ε = 0 by the error: e j M k+ǫ = v j M k+ǫ -(P j j-1 v j-1 ) M k+ǫ . The multi-scale representation can then directly be written as

Mv J = (v 0 , d 0 , • • • , d J-1 ), where d j-1 = e j M k+ε , ε = 0, k ∈ Z d .

IV. THEORETICAL RESULTS ON NONLINEAR MULTI-SCALE REPRESENTATIONS

A. Definition of the Prediction Operator

The definition of the multi-scale representation is related to that of P j j-1 , the prediction operator. In the present paper, we allow the definition and the use of quasi-linear prediction operator defined by: Definition 1. A quasi-linear prediction operator is a function which associates to each w ∈ ℓ ∞ (Z d ) a linear operator S(w) defined by

(S(w)u) k := {l∈Z d , k-M l ∞<K } a k-M l (w)u l , for any u ∈ ℓ ∞ (Z d ) where • ∞ denote the sup norm in Z d and |a k-M l (w)| < C ∀w.
The constants K and C are independent of the data w.

Note that the recursive action of the quasi-linear prediction operator Su := S(u)u on the initial data u = u 0 , defines a nonlinear subdivision scheme:

u j := Su j-1 = S(u j-1 )u j-1 = . . . = S(u j-1 ) . . . S(u 0 )u 0 = S j u 0 .
We assume that the general form of the prediction operator for the given data v j-1 is then given by:

vj k = (P j-1 j v j-1 ) k = (S(v j-1 )v j-1 ) k = l∈Z d a k-M l (v j-1 )v j-1 l .
The consistency property imposes that a k,l (v j-1 ) satisfies

k∈Z d a k-M p (v j-1 )h k-M i = mδ p-i . (6)
In an interpolatory framework, h = mδ k,0 and (6) amounts to a M k (v j-1 ) = δ k,0 .

B. Definitions of Schemes for the Differences and of Joint Spectral Radius

We say that the quasi-linear subdivision operator S reproduces the constants when:

p∈Z d a k-M p (u) = 1 ∀k ∈ Z d and ∀u ∈ ℓ ∞ (Z d ).
Then, the following result holds:

Proposition 1. Let S be a quasi-linear prediction operator reproducing the constants and assume u j = Su j-1 defined in [START_REF] Harten | Uniformly high order accurate essentially non-oscillatory schemes III[END_REF]. Then there exists a local and bounded operator S 1 such that ∇u j := S 1 (u j-1 )∇u j-1 . where

∇u k = (u k -u k-e1 , • • • , u k -u k-ed ).
PROOF: Consider

u j k+ei -u j k = p∈V (k+ei) V (k) (a k+ei-M p (u j-1 ) -a k-M p (u j-1 ))u j-1 p = p∈V (k+ei) V (k) α k-M p (u j-1 )u j-1 p ,
where

V (k) = {p, k -M p ∞ < K}. Note that p∈V (k+ei) V (k)
α k-M p (u j-1 ) = 0, we then deduce that, since

∇ l δ n,β , n ∈ V (k + e i ) V (k), β ∈ Z d , l = 1, • • • , d (with ∇ l u k = u k -u k-el ) spans α k-M p (u j-1 ) p∈V (k+ei) V (k) [7], u j k+ei -u j k = β∈Z d p∈V (k+ei) V (k) d l=1 c p-β,l ∇ l u j-1 p
, where (c k ) is a finite sequence. Computing the differences for other directions e i , we obtain the desired result .

C. Convergence Theorem for the Multi-scale Representation

In this section, we state a convergence result for the multi-scale representation when the matrix M is isotropic which corresponds to the following definition: Definition 2. We say that a matrix M is isotropic if it is similar to the diagonal matrix diag(σ 1 , . . . , σ d ),

i.e. there exists an invertible matrix Λ such that

M = Λ -1 diag(σ 1 , . . . , σ d )Λ,
v ∈ R d C 1 σ n v ≤ M n v ≤ C 2 σ n v .
The convergence theorems we now state involve Besov spaces. Let us briefly recall the definition of such spaces. First consider the modulus of smoothness of order N ∈ Z in L p (Z d ) of a function v, given by

ω N (v, t) L p = sup h∈Z d : h 2≤t ∇ N h v L p (R d ) ,
where . 2 is the Euclidian norm and where ∇ N h is the finite differences operator of order N in the direction h:

∇ N h v(x) := N β=0 (-1) β C β N v(x -βh)
We now introduce the Besov space B s p,q (R d ). Let N be any integer, N > s. For p, q > 0 and s > 0, the space

B s p,q (R d ) contains functions v ∈ L p (R d ) such that (2 js ω N (v, 2 -j ) L p ) j≥0 ∈ ℓ q (Z d ). The norm in B s p,q (R d ) is then given by v B s p,q (R d ) := v L p (R d ) + (2 js ω N (v, 2 -j ) L p ) j≥0 ℓ q (Z d ) .
If we consider an isotropic dilation matrix M , we define from v the set v j ,j ≥ 0 converging to v following (3) and then the nonlinear multi-scale representation. Then, we have the following theorem: Theorem 1. If the prediction operator reproduces the constants, then for all 0 < s < 1, one has the

inequality v 0 . ℓ ∞ (Z d ) + (σ sj d j-1 . ℓ ∞ (Z d ) ) j≥0 ℓ q (Z d ) < ∼ v B s ∞,q (R d ) .
PROOF: First, we show that the consistency property implies that

e j ℓ ∞ (Z d ) < ∼ ∇v j ℓ ∞ (Z d ) d . We recall that e j k := v j k -vj k = v j k - k-M l ∞≤K a k-M l (v j-1 )v j-1 l .
Using (4), we write the prediction error in the form

e j k = v j k -m -1 l: k-M l ∞≤K a k-M l (v j-1 ) p: p-M l ∞≤P hp-Ml v j p = v j k -m -1 p: k-p ∞≤K +P v j p l: k-M l ∞≤K a k-M l (v j-1 ) hp-Ml = p∈F (k) b k,p (v j-1 )v j p ,
where

F (k) = {p : p -k ∞ ≤ P + K} is a finite set for any given k. Let us define, for each k ∈ Z d , a vector b k (w) = (b k,n (w)) n∈F (k)
. By hypothesis, e j = 0 if v j k = k, since the prediction operator reproduces the constants. Since,

{(∇ i δ n-l ) n∈F (k) , l ∈ Z d , i = 1, • • • , d} spans the orthogonal to the family (l qi i ) l∈F (k),i=1,•••,d,qi≤1
, by denoting c l (w) the coordinates of b k (w) in this basis and after simple computations we obtain that

e j k = n∈F (k) d i=1 c n,i (v j-1 )∇ i v j n .
This proves that e j ℓ ∞ (Z d ) < ∼ ∇v j ℓ ∞ (Z d ) since the sequence c is finitely supported. We get from this that

v 0 ℓ ∞ (Z d ) + (σ sj d j-1 . ℓ ∞ (Z d ) ) j≥0 ℓ q (Z d ) < ∼ v 0 ℓ p (Z d ) + (σ sj ∇v j . (ℓ ∞ (Z d )) d ) j≥0 ℓ q (Z d ) . (7)
Then

remark that v 0 ℓ ∞ (Z d ) = v(.) ℓ ∞ (Z d ) < ∼ v L ∞ (R d )
and also, since the matrix is isotropic, we can show that

∇v j ℓ ∞ (Z d ) d < ∼ ω 1 (v, Cσ -j t) < ∼ ω 1 (v, σ -j t)
, the last inequality being a property of the modulus of smoothness. Finally, replacing in equation ( 7), we get that:

v 0 ℓ ∞ (Z d ) + (σ sj d j-1 . ℓ ∞ (Z d ) ) j≥0 ℓ q (Z d ) < ∼ v B s ∞,q (R d ) .
Note that the joint spectral radius is not involved in the above inequality but is of crucial importance for the inverse theorem which we now state. We study the reconstruction process of a function v r , where r stands for "reconstruction", from its coefficients v 0,r and d j,r . In the case of nonlinear representations, it is still possible to study the reconstruction algorithm of the function v r from its coefficients by iteratively using the reconstruction step

v j,r = P j-1 j v j-1,r + e j = P j-1 j v j-1,r + Ed j-1,r .
In that context, the function v r is the limit (when it exists) of v j,r defined by:

v j,r (x) = k∈Z d v j,r k ϕ(M j x -k)
where ϕ was defined in [START_REF] Amat | Nonlinear Harten's Multiresolution on the Quincunx Pyramid[END_REF]. The following theorem gives a sufficient condition for the limit function to exist in Besov space:

Theorem 2. Let S be a quasi-linear prediction operator reproducing the constants. If ρ ∞ (S 1 ) < σ -s for some s > 0 and if (v 0,r , d 0,r , d 1,r , . . .) are such that

v 0,r . ℓ ∞ (Z d ) + (σ sj d j,r . ℓ ∞ (Z d ) ) j≥0 ℓ q (Z d ) < ∞,
and assume that

k∈Z d ϕ(x -k) = 1, where φ satisfies (1), then the function v belongs to B s ∞,q (R d ) and v B s ∞,q < ∼ v 0 ℓ ∞ (Z d ) + (σ sj d j . ℓ ∞ (Z d ) ) j≥0 ℓ q (Z d ) .
The proof of the inverse theorem is much more involved and details are available in [START_REF] Matei | Smoothness Characterization and Stability in Nonlinear Multi-scale Framework: Theoretical Results[END_REF]. Note that the inverse theorem requires that the joint spectral radius of the difference operator be smaller than 1.

We will design in the following sections examples of prediction operators that satisfy this property.

D. Stability of Nonlinear Multi-scale representations

The stability of nonlinear multi-scale decomposition is strongly related to that of the associated prediction operator. We recall the important notion of the stability of quasi-linear prediction operator [START_REF] Cohen | Quasi-linear Subdivision Schemes with Applications to ENO Interpolation[END_REF]:

Definition 3. A quasi-linear prediction operator is stable if for every v, w in ℓ ∞ (Z d ): S(v) -S(w) ℓ ∞ (Z d ) ≤ C v -w ℓ ∞ (Z d )
where C depends in a non-decreasing way on v ℓ ∞ (Z d ) .

The stability of the quasi-linear prediction operator is essential for the stability of the multi-scale representation Mv J . We will tell when this property holds for the prediction operators we will consider, but the study of the stability of the associated multi-scale representation is beyond the scope of the present article.

V. BIDIMENSIONAL INTERPOLATORY QUASI-LINEAR PREDICTION OPERATORS

The nonlinear representations we will study are essentially based on edge non-oscillatory (ENO) approach in an interpolatory framework. ENO methods consist in computing a cost function denoted by C j (k) that determines the best prediction operator among a group of potential ones. Each of these prediction operators are associated to interpolation polynomials on different stencils, the cost function C j (k) being a function computed on the stencils. An arbitrarily small change at the round off level would be sufficient to change the stencil chosen for the prediction and thus the prediction operator. For that reason, the ENO scheme is not stable [START_REF] Matei | Smoothness Characterization and Stability in Nonlinear Multi-scale Framework: Theoretical Results[END_REF]. Such a drawback can be avoided using weighted-ENO (WENO)

interpolation which provides a smooth transition between prediction operators. The WENO formulation is based on a convex combination of potential prediction operators given by the ENO method, that is: where a r :=

vj k := m-1 r=0 α r vj,
1 ε+C j (r)
, where C j (r) is the cost function of the corresponding rule. We will see, on examples that the WENO prediction is continuously dependent on the data.

In the following, we build nonlinear multi-scale decompositions using the quincunx or the hexagonal dilation matrix which are particular cases of isotropic matrices. A similar approach using the quincunx matrix was proposed in [START_REF] Chappelier | Oriented Wavelet Transform for Image Compression and Denoising[END_REF] in a lifting scheme framework, we will emphasize the differences with our method when necessary. In one dimension and in a dyadic scales framework, the lifting scheme is made of an update step at even locations and a prediction step at odd locations but, when one considers interpolatory scheme to predict, as we will do, no update is required. Since we consider an interpolatory scheme, h = mδ 0 and the consistency property leads to a M k = δ k,0 . Consequently, we only define a M k+ε when ε is a non-zero coset vector of M .

A. Nonlinear Affine Prediction Using the Quincunx Matrix

The quincunx matrix is defined by

M =   -1 1 1 1   ,
whose coset vectors are ε 0 = (0, 0) T and ε 1 = (0, 1) T . Note that a 0,0 = 1 since the scheme is interpolatory

(this corresponds to v j M k = v j-1 k
) and since the nonlinear prediction operators reproduce the constants we shall have i a M i+ǫ = 1 for all coset vectors ǫ. We consider prediction operators based on interpolation by polynomials of degree 1 (i.e. a + bx + cy) on Γ j-1 , leading the following four potential stencils which in turn entails the following prediction rules:

vj,1 M k+ε1 = 1 2 (v j-1 k + v j-1 k+e1+e2 ) (8) vj,2 M k+ε1 = 1 2 (v j-1 k+e1 + v j-1 k+e2 ) (9)
Now, as M 2 = 2Id, after double iteration these subdivision schemes could be associated with a limit function of the kind:

Ψ(x) = p k (a ↑M ) k a p-k Ψ(2x -p)
where

(a ↑M ) p =    a k if p = M k 0 otherwise,
and, therefore, we can draw a comparison between the different cases in terms of limit functions. On Figure 1.C, we display the limit function corresponding to the separable case (i.e. Ψ(x) =

2 i=1 max(0, 1 - |x i |))
where the predictions (8) and ( 9) are applied successively, while we display on Figure 1. A (resp.

B), the limit function corresponding to prediction (8) (resp. ( 9)). To relate this to the general biorthogonal framework of section II, we shall say that the limit function corresponding to the separable case is the function ϕ and the other predictions define other limit functions that are still orthogonal to φ.

March 25, 2010 DRAFT We now pass on to ENO prediction, which consists in choosing between the two prediction rules [START_REF] Amat | C Trillo Analysis of a New Nonlinear Subdivision Scheme Application in Image Processing[END_REF] and [START_REF] Amat | Liandrat On the stability of the PPH Nonlinear Multiresolution[END_REF]. In [START_REF] Chappelier | Oriented Wavelet Transform for Image Compression and Denoising[END_REF], the choice of stencils corresponds to:

min |v j M k+ε1 - 1 2 (v j-1 k+e1 + v j-1 k+e2 )|, |v j M k+ε1 - 1 2 (v j-1 k + v j-1 k+e1+e2 )| .
The above cost function assumes that the true values at level j are known before prediction which is not relevant in a progressive data transmission context. To avoid this, we define the cost function as follows:

C j (k) = min(|v j-1 k+e1 -v j-1 k+e2 |, |v j-1 k -v j-1 k+e1+e2 |).
When the minimum of C j (k) corresponds to the first (resp. second) argument the prediction (9) (resp. is not intersected by an edge, the gain between choosing one direction or the other is very small [START_REF] Chappelier | Oriented Wavelet Transform for Image Compression and Denoising[END_REF]. Therefore, we will only apply this procedure for stencil selection only when:

argmin k ′ =k,k+e1,k-e1 |v j-1 k ′ -v j-1 k ′ +e1 | + |v j-1 k ′ -v j-1 k ′ +e2 | + |v j-1 k ′ +e2 -v j-1 k ′ +e1+e2 | +|v j-1 k ′ +e1 -v j-1 k ′ +e1+e2 | + |v j-1 k ′ -v j-1 k ′ +e1+e2 | + |v j-1 k ′ +e1 -v j-1 k ′ +e2 | = 1 or argmin k ′ =k,k+e2,k-e2 |v j-1 k ′ -v j-1 k ′ +e1 | + |v j-1 k ′ -v j-1 k ′ +e2 | + |v j-1 k ′ +e2 -v j-1 k ′ +e1+e2 | +|v j-1 k ′ +e1 -v j-1 k ′ +e1+e2 | + |v j-1 k ′ -v j-1 k ′ +e1+e2 | + |v j-1 k ′ +e1 -v j-1 k ′ +e2 | = 1 (10)
which corresponds to the case where the average first order differences are locally maximum in the vertical or horizontal direction. We will also test another possible choice to detect the cells where the nonlinear prediction is potentially interesting which is the following:

argmin k ′ =k,k+e1+e2,k-e1-e2 (|v j-1 k ′ -v j-1 k ′ +e1+e2 |) = 1 or argmin k ′ =k,k+e1-e2,k-e1+e2 (|v j-1 k ′ +e1 -v j-1 k ′ +e2 |) = 1 (11)
which corresponds to the case where the first order differences are locally maximum is the direction of prediction. When the cell does not satisfy this property, we will apply the linear prediction method.

As far as the WENO approach is concerned, no cost function is needed since we have:

ṽj M k+ε1 = a 1 2(a 1 + a 2 ) (v j-1 k+e1 + v j-1 k+e2 ) + a 2 2(a 1 + a 2 ) (v j-1 k + v j-1 k+e1+e2 )
with

a 1 = 1 ǫ + |v j-1 k+e1 -v j-1 k+e2 | , a 2 = 1 ǫ + |v j-1 k -v j-1 k+e1+e2 | . ( 12
)
The ENO and WENO prediction are such that ρ ∞ (S 1 ) < 1 since they satisfy the following property:

Proposition 2. • when k = M k ′ , we can show that: v j,1 M k+ε1 -v j M k l ∞ (Z 2 ) ≤ 1 2 ∇v j-2 . (l ∞ (Z 2 )) 2 v j,2 M k+ε1 -v j M k l ∞ (Z 2 ) ≤ ∇v j-2 . (l ∞ (Z 2 )) 2
• when k = M k ′ + ε 1 , we can show that:

v j,2 M k+ε1 -v j M k l ∞ (Z 2 ) ≤ 1 2 ∇v j-2 . (l ∞ (Z 2 )) 2 v j,1 M k+ε1 -v j M k l ∞ (Z 2 ) ≤ ∇v j-2 . (l ∞ (Z 2 )) 2
The proof is available in Appendix B. The same result can be shown for other differences on the grid Γ j , which proves that ρ ∞ (S 1 ) < 1 and then enables us to apply Theorem 2.

B. Nonlinear Affine Prediction Using the Hexagonal Dilation Matrix

We now focus on the construction of nonlinear multi-scale decompositions using as dilation matrix the hexagonal matrix

M =   2 1 0 -2   ,
with coset vectors ε 0 = (0, 0) T , ε 1 = (1, 0) T , ε 2 = (1, -1) T , ε 3 = (2, -1) T . We compute the prediction of v j for the different coset points using an affine interpolant of the neighboring points associated to values computed on the grid Γ j-1 . To do so, we use the following four different stencils on the grid

Γ j-1 : V j,1 k = M -j+1 {k, k + e 1 , k + e 2 }, V j,2 k = M -j+1 {k, k + e 2 , k + e 1 + e 2 }, W j,1 k = M -j+1 {k + e 1 , k + e 2 ), k + e 1 + e 2 }, W 2 k = M -j+1 {k, k + e 1 , k + e 1 + e 2 }.
We determine to which stencils each point of Γ j belongs to, and we then define the prediction as its barycentric coordinates. Note, first, that the prediction rule at M k and M k + ε 1 is independent of the choice of the stencil, and we always have:

v j M k = v j-1 k and v j M k+ε1 = 1 2 v j-1 k + 1 2 v j-1 k+e1 . ( 13
)
When one considers the prediction for the coset vector ε 2 , V 1 k or V 2 k can be used to predict leading respectively to:

v j,1 M k+ε2 = 1 4 v j-1 k+e1 + 1 2 v j-1 k+e2 + 1 4 v j-1 k v j,2 M k+ε2 = 1 2 v j-1 k + 1 4 v j-1 k+e2 + 1 4 v j-1 k+e1+e2 . ( 14
)
When one considers the prediction rules for the coset vector ε 3 , W 1 k or W 2 k can be used leading to the following two predictions:

v j,1 M k+ε3 = 1 4 v j-1 k+e2 + 1 4 v j-1 k+e1+e2 + 1 2 v j-1 k+e1 v j,2 M k+ε3 = 1 4 v j-1 k + 1 4 v j-1 k+e1 + 1 2 v j-1 k+e1+e2 (15)
when the stencils W 1 k and W 2 k are used respectively.

This leads to four different linear prediction rules depending on the choice for the prediction operator for coset vector ε 2 and ε 3 . The corresponding limit functions are shown on Figure 2. To relate this to the general biorthogonal framework of section II, the function ϕ would be associated to the predictions (14.1) and (15.1) while other prediction rules defines other limit function that are still biorthogonal to φ.

The proposed nonlinear subdivision operator is such that ρ ∞ (S 1 ) < 1 since we have: Proposition 3. The prediction defined by ( 13), ( 14), (15) satisfies:

(A) (B) (C) (D)
(E) (F) (G) (H)
∇v j M.+ǫi (l ∞ (Z 2 )) 2 ≤ 3 4 ∇v j-1 (l ∞ (Z 2 )) 2
The proof is given in Appendix C.

The choice of stencil in the ENO method is determined by minimizing a certain cost function, which is different for ε 2 and ε 3 since these coset points belong to different stencils. We will consider the following cost function to predict at ε 2 :

C j,ε2,1 H (k) = min(|v j-1 k+e1 -v j-1 k+e2 | + |v j-1 k+e1 -v j-1 k |, |v j-1 k -v j-1 k+e1+e2 | + |v j-1 k+e1+e2 -v j-1 k+e1 |).
When the minimum corresponds to the first (resp. second) argument, the stencil V 1 k (resp. V 2 k ) is used. Similarly, when one considers the prediction at ε 3 , we will compute:

C j,ε3,1 H (k) = min(|v j-1 k+e1 -v j-1 k+e2 | + |v j-1 k+e1+e2 -v j-1 k+e2 |, |v j-1 k -v j-1 k+e1 | + |v j-1 k+e1+e2 -v j-1 k |).
When the minimum corresponds to the first (resp. second) argument, the stencil W 1 k (resp. W 2 k ) is used. The above cost function to determine which stencil to use will apply only on cells Q j-1 k containing an edge. Such cells are determined in the same way as in the quincunx case finding local maxima of first order differences computed on the cell. When the hexagonal dilation matrix is used, to compute the cost function in the direction of prediction as in the quincunx case does not make sense since the direction of prediction does not exist strictly speaking. Therefore, to compute edge cells we will only consider formula [START_REF] Matei | Smoothness Characterization and Stability in Nonlinear Multi-scale Framework: Theoretical Results[END_REF].

As far as WENO prediction is concerned, we may write that:

ṽj M k+ε2 = ( α 1 1 4 + α 1 2 2 )v j-1 k + α 1 1 4 v j-1 k+e1 + ( α 1 1 2 + α 1 2 4 )v j-1 k+e2 + α 1 2 4 v j-1 k+e1+e2 , ṽj M k+ε3 = ( α 2 1 4 + α 2 2 4 )v j-1 k+e1 + α 2 2 2 v j-1 k + ( α 2 1 2 + α 2 2 4 )v j-1 k+e1+e2 + α 2 1 4 v j-1 k+e2 , with a 1 1 = 1 ε + |v j-1 k+e1 -v j-1 k+e2 | , a 1 2 = 1 ε + |v j-1 k -v j-1 k+e1+e2 | , a 2 1 = 1 ε + |v j-1 k+e1 -v j-1 k+e2 | , a 2 2 = 1 ε + |v j-1 k -v j-1 k+e1+e2 | . (16)
The WENO predictions satisfy the following stability property:

Theorem 3. If a r are defined by (12) for quincunx matrix and ( 16) for hexagonal matrix, the corresponding WENO subdivision schemes are stable.

The proof is given in Appendix A.

C. Prediction Operators Using Higher Degree Polynomials

We now introduce prediction rules based on higher degree polynomials. Prediction Operators build using an affine interpolation suffers from the drawback that the prediction inside a given cell does not depend on neighboring cells. To consider higher degree polynomials enables to build more sophisticated prediction operators but results in spurious oscillations close to edges due to Gibbs phenomenon. In [START_REF] Amat | C Trillo Analysis of a New Nonlinear Subdivision Scheme Application in Image Processing[END_REF],

the PPH scheme is introduced and aims at limitating oscillations close to the edges. It is derived from the one dimensional prediction operator defined as follows on a dyadic grid:

v j 2k+1 =    v j-1 k+1 +v j-1 k 2 -1 4
∇ 2 v j-1 k ∇ 2 v j-1 k+1 ∇ 2 v j-1 k +∇ 2 v j-1 k+1 if ∇ 2 v j-1 k ∇ 2 v j-1 k+1 > 0 v j-1 k+1 +v j-1 k 2 otherwise March 25, 2010 DRAFT
where ∇ 2 v j-1 k is the second order divided difference based on x j-1 k-1 , x j-1 k , x j-1 k+1 . From this prediction operator, one can derive a bidimensional prediction operator using a tensor product approach. The convergence of the one dimensional subdivision scheme was shown in [START_REF] Amat | C Trillo Analysis of a New Nonlinear Subdivision Scheme Application in Image Processing[END_REF] and also the stability in [START_REF] Amat | Liandrat On the stability of the PPH Nonlinear Multiresolution[END_REF]. The philosophy of the PPH approach is different from that we propose next in that the prediction operator is neither quasi-linear nor non-separable. Furthermore, the convergence of the bidimensional scheme derived by tensor product remains an open issue.

In what follows, we consider polynomials of degree 2 for prediction. These polynomials interpolates v on different stencils which we define below. The approach we propose next is valid both for the quincunx and the hexagonal dilation matrices. The prediction rules we consider are based on the following stencils defined on Γ j-1 :

V 1 = M -j+1 {k, k + e 1 , k + e 2 , k + e 1 + e 2 , k + 2e 1 , k + 2e 2 } V 2 = M -j+1 {k, k + e 1 , k + e 2 ), k + e 1 + e 2 , k -e 1 , k + 2e 2 } V 3 = M -j+1 {k, k + e 1 , k + e 2 , k + e 1 + e 2 , k + 2e 1 , k -e 2 } V 4 = M -j+1 {k, k + e 1 , k + e 2 , k + e 1 + e 2 , k -e 1 , k -e 2 } . (17)
As in the affine case, to detect edge-cells, we check property [START_REF] Matei | Smoothness Characterization and Stability in Nonlinear Multi-scale Framework: Theoretical Results[END_REF]. Then, we use nonlinear affine prediction on edge-cells. Once we have dealt with edge-cells, we apply the following strategy on remaining cells:

• If a cell has a edge-cell as neighboring cell in the vertical or horizontal direction then the prediction is made using stencil selection we describe below,

• otherwise, we apply the stencil V 1 for the prediction. Now, let us explain how we do stencil selection. For each stencil V i , defined in (17), we consider the triangles made of neighboring points inside that stencil. This corresponds to 6 triangles. For instance for stencil V 1 , the triangles are as follows:

M -j+1 {k, k + e 1 , k + e 2 }, M -j+1 {k, k + e 1 , k + e 1 + e 2 }, M -j+1 {k, k + e 2 , k + e 1 + e 2 }, M -j+1 {k + e 1 , k + e 2 , k + e 1 + e 2 }, M -j+1 {k + e 1 , k + 2e 1 , k + e 1 + e 2 )}, M -j+1 {k + e 2 , k + e 1 + e 2 , k + 2e 2 }.
The triangles are defined the same way for other stencils.

We compute a cost function on each triangle as the sum of the first order differences along its edges (for instance, the cost function for the first triangle of

V 1 is |v j-1 k+e1 -v j-1 k | + |v j-1 k+e2 -v j-1 k+e1 | + |v j-1 k+e2 -v j-1 k |).
The cost function C j,i (k) associated to V i is then the sum of the cost functions computed on all the triangles that make up V i . For the prediction, we then use the stencil with minimal cost.

In the case where M is the quincunx matrix, the stencils V i are used to predict v j M k+ε1 , ε 1 = (0, 1) while when M is the hexagonal matrix, the stencils are used to predict v j M k+εi , with ε 1 = (1, 0), ε 2 =

(1, -1), ε 3 = (2, -1). To prove the convergence of such schemes would involve the computation of all the differences in the canonical directions. However, at each coset point we have this time 4 potential predictions, so it would be prohibitive to detail the computation here. We are currently looking for a concise proof of the conjecture that these nonlinear operators satisfy the condition on the joint spectral radius (i.e. ρ ∞ (S 1 ) < 1). Once the prediction operator is chosen, we implement the multi-scale representation Mv J . This is what we deal with next.

VI. MULTI-SCALE REPRESENTATION WHEN M 2 = λId

Note first that since M 2 = λId, the finest resolution level J is considered even. Let

Γ J = {x J k1 , y J k2 } NJ -1 k1,k2=0 , x J k1 = k 1 h J , y J k2 = k 2 h J , h J = 2 -J h 0 , N J = 2 J N 0 where N 0 is some integer and h 0 = 1/N 0 . Since M 2 = λId, we obtain, for k 1 , k 2 = 0, ..., N J /λ -1, x J λk1 = x J-2 k1 and y J λk2 = y J-2 k2
. The connections between the levels J and J -1 or J -1 and J -2 are more elaborate.

A. Encoding and Decoding Algorithm

Let us detail the quincunx case, the hexagonal case can be dealt with the same way. The following encoding and decoding algorithms were originally proposed in [START_REF] Amat | Nonlinear Harten's Multiresolution on the Quincunx Pyramid[END_REF], but we recall it for the sake of consistency.

We recall that the quincunx matrix satisfies M 2 = 2Id. For the first step, we have for k 2 = 0, ..., N J -1

(x J 2k1 , y J k2 ) = (x J-1 k1 , y J-1 k2 ), k 1 = 0, ..., N J /2 -1 if k 2 even, (x J 2k1-1 , y J k2 ) = (x J-1 k1 , y J-1 k2 ), k 1 = 1, ..., N J /2 if k 2 odd,
and for the second

(x J-1 k1 , y J-1 2k2 ) = (x J-2 k1 , y J-2 k2 ), k 1 , k 2 = 0, ..., N J /2 -1.
The following steps are performed similarly. Let us put N j := N J /2 (J-⌊j/2⌋) . We consider v j k1,k2 = v(x j k1 , y j k2 ), where if j is even

0 ≤ k 1 , k 2 ≤ N j -1 and if j is odd 0 ≤ k 2 ≤ 2N j and 1 ≤ k 1 ≤ N j . The projection operators are for j even v j-1 k1,k2 = (P j j-1 v j ) k1,k2 = v j 2k1,k2 if k 2 is even, v j-1 k1,k2 = (P j j-1 v j ) k1,k2 = v j 2k1-1,k2 if k 2 is
odd, and for j odd v j-1 k1,k2 = (P j j-1 v j ) k1,k2 = v j k1,2k2 . In particular, we obtain for j even that the kernel of the linear operator of decimation, P j j-1 , reads Ker(P j j-1 ) = {v j ∈ V j , v j 2k1,k2 = 0, k 2 even , v j 2k1-1,k2 = 0, k 2 odd }, and for j odd Ker(P j j-1 ) = {v j ∈ V j , v j k1,2k2 = 0}. Thus, if we denote by e k the prediction error, we will need to keep when j is even e j 2k1-1,k2 for k 2 even, e j 2k1,k2

for k 2 odd and e j k1,2k2-1 when j is odd. A reconstruction procedure for this discretization is given by operator S(v j-1 ) := S(v j-1 )v j-1 that interpolates the data v j-1 at the grid points of Γ j-1 . We consider three different types of prediction rules: linear prediction, ENO and WENO prediction. Let us remark that in the algorithm given below we denote vj = v j \ v j-1 , that is, for all j = 0, . . . , J, v j = j k=1 vk .

Then, encoding and decoding algorithms take the following form:

Encoding Algorithm

Quincunx Matrix

for j = J-2, . . . , 2; j = j -2

for k 1 ,k 2 = 1, . . . , N j-1 vj-2 k1,k2 = v j 2k1-1,2k2-1 vj-1 k1,2k2 = v j 2k1,2k2 end for k 1 , k 2 =1, . . .,N j-1 e j-1 k1,k2 = v j 2k1,2k2 -S(v j-2 ) 2k1,2k2 end for k 1 = 1, . . . ,N j-1 for k 2 = 1, . . . , N j ; k 2 = k 2 + 2 e j k1,2k2 = v j 2k1,k2 -S(v j-1 ) 2k1,k2 e j k1,k2+1 = v j 2k1-1,k2+1 -S(v j-1 ) 2k1-1,k2+1 end end end

Hexagonal Matrix

for j = J-2, . . . , 2; j = j -2

for k 1 ,k 2 = 1, . . . , N j-1 vj-2 k1,k2 = v j 4k1-3,4k2-3 , vj-1 k1,3k2-2 = v j 4k1-1,4k2-2 vj-1 k1,3k2-1 = v j 4k1-3,4k2-1 , vj-1 k1,3k2 = v j 4k1-1,4k2 end for k 1 , k 2 =1, . . .,N j-1 e j-1 k1,3k2-2 = v j 4k1-1,4k2-2 -S(v j-2 ) 4k1-1,4k2-2 e j-1 k1,3k2-1 = v j 4k1-3,4k2-1 -S(v j-2 ) 4k1-3,4k2-1 e j-1 k1,3k2 = v j 4k1-1,4k2 -S(v j-2 ) 4k1-1,4k2 end for k 1 = 1, . . . ,N j-1 for k 2 = 1, . . . , N j ; k 2 = k 2 + 2 e j 3k1-2,k2 = v j 4k1-2,k2 -S(v j-1 ) 4k1-2,k2 e j 3k1-1,k2 = v j 4k1-1,k2 -S(v j-1 ) 4k1-1,k2 e j 3k1,k2 = v j 4k1,k2 -S(v j-1 ) 4k1,k2 e j 3k1-2,k2+1 = v j 4k1-3,k2+1 -S(v j-1 ) 4k1-3,k2+1 e j 3k1-1,k2+1 = v j 4k1-3,k2+1 -S(v j-1 ) 4k1-3,k2+1 e j 3k1,k2+1 = v j 4k1,k2+1 -S(v j-1 ) 4k1,k2+1 end end end
The encoding algorithm leads to the following representation: Mv J = (v 0 , d 0 , ..., d J-1 ), where d j was defined at the end of section III. Making the same reasoning, we can encode the multiresolution decomposition obtained with the hexagonal sampling matrix.

Then, we concatenate matrices v 0 , d 0 , . . . , d J-1 in one matrix V of dimension N J (that is, of the same dimension as v J ). To build V , we start by writing down matrix v 0 in its left upper corner. Then, we write down the matrix d 1 to the right of matrix v 0 and then d 1 below matrices v 0 and d 0 thus getting a square matrix. We proceed in the same way (writing down matrix d j to the right of d j -2 if j is even and below if j is odd) until j = J. The result of this concatenation is represented on Figure 3 Therefore, we are led to encode V . Let us notice that in general the prediction error is larger when the resolution is low. That is, the smaller j, the larger the elements of sub-matrix D j . This naturally leads us to build an EZW (Embedded zero-tree wavelet) encoder adapted to our context.

The EZW (Embedded Zero-tree Wavelet) encoding algorithm is an encoder specially developed to use with wavelet transforms. It is based on progressive encoding: the data is compressed in multiple passes with increasing accuracy. The initial threshold is set to be equal to T 0 = 2 ⌊log 2 (max |V (k1,k2)|)⌋ , where max |V (k 1 , k 2 )| means the maximum element of matrix V . The encoder scans next element, compares it with threshold and gives 'p', 'n', 'z' or 't' as an output; if the absolute value is bigger than the threshold, it outputs either 'p', if the value is positive or 'n', if it is negative, else it constructs a tree with the considered element as the root. If it is a zero-tree (that is, the values in the nodes are smaller or equal to the root), the output is 't', otherwise it is 'z' (isolated zero). We encode an element only if we got 'p' or 'n' as output. In this case, we put it in the so-called 'subordinate list' together with either 3T0 !2 , if it is bigger than T 0 or -3T0 2 (for elements inferior to -T0

2 ) and remove it from V (replace it by 0) so that it will not be encoded again. After we have scanned all the elements, we divide the threshold T 0 by two and start again the procedure till the threshold is not smaller than a fixed value.

Thereby, to apply an encoder based on the same principle as EZW encoder, we need to introduce a tree structure for them. The trees are designed in such a way that every element of the sub-matrix D j is a child of some element of sub-matrix D j-1 , j = 1, . . . , 2 log 2 N J for quincunx matrix, j = 1, . . . , 2 log 4 N J for hexagonal matrix. That is, we get a binary tree for quincunx matrix and a quad-tree for hexagonal matrix. The tree structures for quincunx and hexagonal trees are illustrated on In order that the algorithm works correctly, it is necessary that matrix V be scanned in such a way that sub-matrix D j is scanned before D j+1 , subspace D j being itself scanned using the so-called Morton scan. For each subspace D j , we will denote by T j 1 (resp. T j 2 ) the number of lines (resp. columns) in the matrix D j . The EZW decoding is realized exactly in the same way as for wavelets. We now write the inverse operator v J = M -1 (v 0 , d 0 , ..., d J-1 ).

Decoding Algorithm made the simulation for T 1 = 32, 64, 128 for the 256 × 256 images of Lena (Figure 5.(A)) and of peppers (Figure 5.(B)). We also implemented the WENO prediction method.

The results we depict on Figure 6 (A) and (B) corresponds to the prediction rules [START_REF] Amat | C Trillo Analysis of a New Nonlinear Subdivision Scheme Application in Image Processing[END_REF] and [START_REF] Amat | Liandrat On the stability of the PPH Nonlinear Multiresolution[END_REF]. The cells on which we shall predict nonlinearly either corresponds to the cells where the average first order differences are locally maximum in the vertical or the horizontal directions (C 1 on Figure 6 (A) and (B), corresponding to rule [START_REF] Matei | Smoothness Characterization and Stability in Nonlinear Multi-scale Framework: Theoretical Results[END_REF] or the first order differences are locally maximum in the direction of prediction (C 2 on Figure 6 (A) and (B), corresponding to rule [START_REF] Amat | Nonlinear Harten's Multiresolution on the Quincunx Pyramid[END_REF]).

When the quincunx matrix is used, a significant compression gain is observed when the nonlinear method is used especially at high compression rate (see Figure 6 (A) and (B)). A more careful look shows that one shall predict non linearly a larger number of scales when the image is geometric such as the image of Lena while the number of scales predicted nonlinearly are less importance for natural images such as the image of Lena. Furthermore, we noticed that when one uses the rule (11) instead of [START_REF] Matei | Smoothness Characterization and Stability in Nonlinear Multi-scale Framework: Theoretical Results[END_REF] to determine the points where the prediction is nonlinear, the gain in compression is significant for both images and even more for the image of peppers.

The results on WENO prediction are displayed on Figure 6 (C) and (D). For both images, the effect of using the WENO method is to make the prediction operator closer to the linear model which has the consequence that the compression gain over the linear model is significantly less important than when the ENO method is used. WENO method are important to construct stable multi-scale representation. We are currently looking for a different way to define the weights so as to preserve compression performance. Now, if we switch on to the Hexagonal dilation matrix, the results are displayed on Figure [START_REF] Jia | Convergence of Cascade Algorithms in Sobolev Spaces and Integrals of Wavelets[END_REF].(C), we notice that the nonlinear prediction does not bring any improvement in terms of compression results ( note that due to the greater down-sampling we considered T 1 = 16 or 64 which respectively corresponds to the last four subspaces are predicted nonlinearly or only the last 2). Our insight into these results is that the compression performance is related to m = | det(M )|. Indeed, with the hexagonal matrix the sampling factor is too important and too much information is lost between each scale for the prediction to be efficient. Another possible direction for future research would be the optimization of the cost function that determines the stencil to use.

B. The Quadratic Prediction

We investigated the improvement brought about nonlinear quadratic prediction instead of linear quadratic prediction. The improvement in terms of compression rate occur essentially at intermediate compression rate as shown on Figure 7

(A) (B) and WENO predictions for varying T1 using either C1 or C2 to compute cells of interest for Lena image and when the quincunx matrix is used, (D): the same as (C) but for peppers image high compression rate. We notice again that it is less important to predict nonlinearly more scales with the image of Lena than with the image of peppers for which it appears crucial to predict a sufficient number of scales to get better results than in the linear case (see Figure 7 (B)) .

=32 WENO,C 1 ,T 1 =64 WENO,C 1 ,T 1 =128 WENO,C 2 ,T 1 =32 WENO,C 2 ,T 1 =64 WENO,C 2 ,T 1 =128 (C) (D)
Finally, when one uses the hexagonal matrix, Figure 7 (D) shows that to use higher degree polynomial does not bring any improvement in terms of compression results. In terms of perspective, future work should involve the definition of a cost function to determine which stencil to use that shall depend on the matrix M . To conclude the results section, we obtain significant improvement when the quincunx matrix is used while the hexagonal dilation matrix does not seem a good choice in our framework. We are currently trying to understand why the dilation matrix plays such an important role. We have first emphasized the relation between nonlinear prediction operators and multi-scale representations. We have then shown that the convergence of the multiscale representation is related to some property of the joint spectral radius of the first order difference operator computed from the prediction operator. We March 25, 2010 DRAFT have then built some bidimensional nonlinear multi-scale representations based on interpolatory prediction operators. These were built using either the quincunx or the hexagonal matrix as dilation matrix and were either affine predictors or based on polynomials of degree 2. To show the pertinence of the approach we have proposed an application to image compression. To do so, we have first explained how the embedded-zero-tree wavelet (EZW) algorithm adapts in our context. The compression results show a clear improvement brought about ENO methods when the quincunx matrix is used both with affine or quadratic predictors. However, when the WENO prediction is used, the compression results is very close to the linear one, which let us think that future work should involve a deeper study of the weights in the WENO method. When the hexagonal matrix is used, we did not manage to obtain similar results as with the quincunx case ; we believe that a the down-sampling factor (symbolized in our context by the determinant of the matrix) is the key point, but this still needs further study. In terms of perspectives,

we also are currently investigating potential extension of our approach to non-interpolatory prediction operators.

APPENDIX A PROOF :Let v, ṽ ∈ ℓ ∞ (Z 2 ). By the definition of WENO prediction we have that

a k-M l (v) -a k-M l (ṽ) ℓ ∞ (Z 2 ) ≤ S(v) -S(ṽ) ℓ ∞ (Z 2 ) ≤ |α 1 -α1 | + |α 2 -α2 |,
where α 1 , α1 , α 2 , α2 are the weights of the stencils for v and ṽ respectively. For i = 1, 2 it holds that

|α i -αi | = | a i a 1 + a 2 - ãi ã1 + ã2 | ≤ | a i -ãi a 1 + a 2 | + |ã i ( 1 a 1 + a 2 - 1 ã1 + ã2 )| ≤ | 1 a 1 + a 2 |(|a i -ãi | + ãi ã1 + ã2 |a 1 -ã1 + a 2 -ã2 | ≤ | 1 a 1 + a 2 |2 2 i=1 |a i -ãi |,
then, S(v) -S(ṽ) ℓ ∞ (Z 2 ) ≤ 4 ∼ v ℓ ∞ (Z 2 ) and |b i -bi | ≤ v -ṽ ℓ ∞ (Z 2 ) and it follows that

a 1 + a 2 = 1 ǫ+b1 + 1 ǫ+b1 ≥ 2 ǫ+ v ℓ ∞ (Z 2 )
. Therefore,

i |a i -ãi | < ∼ v -ṽ ℓ ∞ (Z 2 ) ǫ 2
and S(v) -S(ṽ)

ℓ ∞ (Z 2 ) < ∼ ǫ+ v ℓ ∞ ǫ 2 v -ṽ ℓ ∞ (Z 2 ) .
March 25, 2010 DRAFT

  wheref L p (R d ) := R d |f (x)| p dx 1 p for 1 ≤ p < ∞ and f L ∞ (R d ) is the essential supremum of |f | on R d . A matrix M is called a dilation matrix ifit has integer entries and if lim n→∞ M -n = 0. In the following, the invertible dilation matrix is always denoted by M and m stands for | det(M )|. Finally, for two positive quantities A and B depending on a set of parameters, the relation A < ∼ B implies the existence of a positive constant C, independent of the parameters, such that A ≤ CB. Also A ∼ B means A < ∼ B and B < ∼ A.

with |σ 1 | 1 d

 11 = . . . = |σ d | being the eigenvalues of matrix M . For an isotropic matrix holds |σ 1 | = . . . = |σ d | = σ = m . Moreover, for any given norm in R d there exist constants C 1 , C 2 such that for any integer n and for any

r k with α r ≥ 0 and m- 1 r=0 α r = 1 .

 11 A possible form for the weights is given by α r := ar m-1 i=0 ai for r = 0, . . . , m-1

Fig. 1 .

 1 Fig. 1. (A): the limit function associated with prediction (8),(B): the limit function associated with prediction (9); (C): the limit function corresponding to the separable case; (D), (E)and (F): the corresponding contour plots.

( 8 )

 8 ) is used. One motivation for the choice of such a cost function is the following argument: when an edge intersect the cell Q j-1 k delimited by the points M -j+1 {k, k + e 1 , k + e 2 , k + e 1 + e 2 } of the grid Γ j-1 , several cases may happen:1) either the edge intersect [M -j+1 k, M -j+1 (k + e 1 + e 2 )] and [M -j+1 (k + e 1 ), M -j+1 (k + e 2 )] in which case no direction is favored.2) or the edge intersect[M -j+1 k, M -j+1 (k + e 1 + e 2 )] or [M -j+1 (k + e 1 ), M -j+1 (k + e 2 )], in which case the prediction operator should favor the direction which is not intersected by the edge (this is what the cost function does). March 25, 2010 DRAFT When Q j-1 k

Fig. 2 .

 2 Fig. 2. (A): the limit function associated to predictions (14.1), (15.1); (B): the limit function associated to predictions (14.1), (15.2); (C): idem with the predictions (14.2), (15.1); (D): idem with prediction (14.2), (15.2) . The corresponding contour plots are depicted on figures (E),(F),(G) and (H) respectively.

Fig. 3 .

 3 Fig. 3. (A): quincunx matrix, (B): hexagonal matrix.

Figure 4 . 2 Fig. 4 .

 424 Fig. 4. (A): Tree structure for quincunx matrix, (B): Tree structure for hexagonal matrix.

Fig. 5 .

 5 Fig. 5. (A): a 256 × 256 Lena image, (B): a 256 × 256 peppers image

Fig. 6 .

 6 Fig. 6. (A): linear prediction (solid line) and ENO prediction for varying T1 using either C1 or C2 to compute cells of interest for Lena image and when the quincunx matrix is used, (B):idem but for the image of peppers (C): linear prediction (solid line)

Fig. 7 .

 7 Fig. 7. (A): The quadratic linear prediction (solid line) is compared to the nonlinear quadratic prediction when the value of T1 varies for Lena image and when the quincunx matrix is used, (B): idem but for the image of peppers, (C): Affine linear prediction (solid line) is compared to the nonlinear affine ENO prediction when the value of T1 varies for both the image of Lena and the image of peppers and when the hexagonal matrix is used ,(D): Same computations as in (C) except that we use quadratic polynomial

a1+a2 2 i=1| ≤ |bi-bi| ǫ 2 .

 22 |a i -ãi |. By simple computations we obtain that: |a i -ãi | = From the definition of b i we have that b i <

March 25, 2010 DRAFT

Quincunx Matrix

for j = 2, . . . , J-1; j = j + 2 for k 1 , k 2 = 1, . . . , N j-1 vj-1 2k1-1,2k2-1 = S(v j-2 ) 2k1-1,2k2-1 vj-1 2k1,2k2 = e j-1 k1,k2 + S(v j-2 ) 2k1,2k2 end for k 1 =1, . . . , N j-1 for k 2 =1, . . . ,N j ; k 2 = k 2 + 2 v j 2k1,k2 = e j k1,k2 + S(v j-1 ) 2k1,k2 v j 2k1-1,k2 = e j k1,k2+1 + S(v j-1 ) 2k1-1,k2+1 end end Hexagonal Matrix for j = 2, . . . , J-1; j = j + 2 for k 1 , k 2 = 1, . . . , N j-1 vj-1 4k1-3,4k2-3 = v j-2 k1,k2 vj-1 4k1-1,4k2-2 = e j-1 k1,3k2-2 + S(v j-2 ) 4k1-1,4k2-2 vj-1

In this section, we study the improvement brought about either by the use of nonlinear affine instead of linear affine interpolant or by using nonlinear quadratic interpolant instead of a linear one. In particular, we will put forward the importance of dealing nonlinearly with the finest scales especially for geometric images. We carry out the study both for the quincunx and hexagonal dilation matrix. We also investigate the importance of the degree of the interpolation polynomial in terms of compression results.

A. Interpolation using Affine Polynomials

We investigated the improvement brought about the use of affine nonlinear prediction schemes instead of linear ones on natural images of Figure 5. In particular, we investigated the importance of nonlinear prediction at fine scales. To do so, we considered nonlinear prediction when T j 1 , the first dimension of D j in the matrix V , is above T 1 and linear prediction elsewhere. For a 256 × 256 image and when the quincunx matrix is used, T 1 = 64 means that we predict nonlinearly the last finest four subspaces. We

APPENDIX B

Let us consider first that k = M k ′ and then we compute (notice that ε 1 = e 2 ):

we then have to consider the different prediction rules for the values v j-1 M (k ′ -e2)+e2 and v j-1 M k ′ +e2 . If the rule ( 8) is used in both cases, we have:

If the prediction rule ( 9) is used in each case, we have:

If prediction ( 8) is used for v j-1 M (k ′ -e2)+e2 and prediction (9) for v j-1 M k ′ +e2 we may write:

If prediction ( 9) is used to predict v j-1 M (k ′ -e2)+e2 and prediction (8) for v j-1 M k ′ +e2 we may write:

From the above equality, we can deduce that when k = M k ′ :

Now, let us consider the case where k = M k ′ + ε 1 . If prediction ( 8) is used we may write:

This corresponds to the same situation as that previously studied, and similar computation leads to:

March 25, 2010 DRAFT If prediction ( 9) is used, we may write:

If prediction ( 8) is used to predict v j-1 M k ′ +ε1 , then we have:

while when prediction ( 9) is used, we get:

From this, we deduce that:

This ends the proof.

APPENDIX C

PROOF: for the sake of simplicity, we will put ∇ i for ∇ ei .

• If we use V 1 k and W 1 k for prediction, then we have the following behavior for the differences:

• When the stencils V 2 k and W 2 k are used for the prediction, we obtain:

• When the stencils V 1 k and W 2 k are used for the prediction

March 25, 2010 DRAFT