François Benoît-Marand

Laurent Signac

Thierry Poinot

Jean-Claude Trigeassou

IDENTIFICATION OF NON LINEAR FRACTIONAL SYSTEMS USING CONTINUOUS TIME NEURAL NETWORKS

Keywords: Neural networks, Non integer integrator, Non linear fractional systems, Output error identification

Fractional systems allow us to model the processes governed by a diffusive equation. The simulation of such processes can be realized by using a non integer integrator. The aim of this paper is to estimate, in the time domain, both the non integer derivative order and the physical law of a non linear fractional system. To achieve this goal, we use Continuous Time Neural Networks. Ctnn are dynamical neural structures that differ from the classical recurrent neural networks on the use of integrator blocks rather than delay blocks. This difference allows us to access the physical law of the system rather than only having a black box model. A non-integer Ctnn is composed of a neural network and a non integer integrator. The identification stage -which consists in finding the good parameters for the neural network and for the integrator block-will be performed by using an output error identification. At the end of the procedure, a model reduction stage can be performed in order to revert from the neural network to a more realistic expression of the physical law of the process. To illustrate the method we'll give some simulation results.

INTRODUCTION

Fractional systems are used to model the physical processes governed by a diffusive equation and have already been used in many different fields like thermics [START_REF] Battaglia | Méthodes d'identification de modèles à dérivées d'ordre non entier et de réduction modale[END_REF][START_REF] Cois | Systèmes linéaires non entier et identification par modèle non entier : application en thermique[END_REF], electrochemistry (Lin et al., 2000a) or electromagnetism (Lin et al., 2000b;[START_REF] Retière | Modeling of electric machines by implicit derivative half-order systems[END_REF]. The works in progress at the Laii * are based on the definition of a non integer integrator [START_REF] Lin | Modélisation et identification de systèmes d'ordre non entier[END_REF] that allows us to simulate linear and non linear fractional systems [START_REF] Poinot | Modelling and simulation of fractional systems[END_REF]. In this paper, we will focus on the modeling and the identification of non linear fractional systems by using neural networks.

An original method using neural networks has already been developed in the case of non linear integer systems [START_REF] Benoît-Marand | Non linear identification of continuous time systems using neural networks[END_REF]. This method, referred to as Ctnn, combines a neural network with an integer integrator block. Contrary to the classical recurent neural networks, that use delay blocks and only give a black box model of the process, Ctnn, by separating the non linear static part of the process (the neural network) from the dynamical one (the integrator block), allows us to access the physical law of the process.

In this article, we will show how, by using a non integer integrator in the Ctnn structure, it is possible to extend the previous method to fractional systems. During the identification stage, we will not only have to estimate the parameters of the network which characterize the system's law but to estimate the derivative order of the system too. These parameters will be found by using an output error identification technique with temporal data.

First, we point out the definition of the non integer integrator and its state space representation. Then we show the principles of Ctnn and their extension to fractional systems. Then, the identification stage is exposed. Finally, we illustrate our method by simulation results.

FRACTIONAL SYSTEMS AND NON INTEGER INTEGRATOR

Simulation of fractional systems

Let us consider the following integer differential equation (u (t) and y (t) are the input and the output of the system):

dy (t) dt = f (u (t) , y (t)) (1)
This differential equation, generally non-linear, may be integrated with the help of an operator I(s) = 1 s , which performs time integration of dy(t) dt (in order to give y(t) at its output). Practically, we use a numerical integrator (Euler,Runge-Kutta 4,...) instead of an analog one ( 1 s ). Then, let us consider the fractional differential equation (n is the non integer derivative order):

d n y (t) dt n = f (u (t) , y (t)) (2)
Assume that a fractional integrator I n (s) = 1 s n is available (its input is equal to d n y(t) dt n so that its output is equal to y(t)).

Thus, I n (s) generalizes to fractional systems the previously presented simulation principle. As a conclusion, integration of fractional systems simulation essentially relies on the definition of a fractional integrator, which will be a generalization of the conventional one.

Notice that this technique applies either to linear or to non-linear fractional systems, which is the main interest of the non-integer operator.

Definition of the non integer integrator

The ideal fractional integrator is defined by using the transfer function I n (s) = 1 s n which corresponds to a magnitude's slope equal to -n × 20 dB/decade and to a phase equal to -n × 90 o for any frequency. This theoretical frequency response can be approximated on a limited band [ω b , ω h ] (according to the desired accuracy) using cascade phase lead filters [START_REF] Oustaloup | La dérivation non entière : théorie, synthèse et applications[END_REF], associated with an 1/s integrator [START_REF] Poinot | A method for modelling and simulation of fractional systems[END_REF].

Consider the following approximation of the theoretical non integer integrator [START_REF] Lin | Modélisation et identification de systèmes d'ordre non entier[END_REF] which corresponds to the Bode diagram on figure 1:

În (s) = G s N i=1 1 + s ω ′ i 1 + s ωi (3) b ω h ω ω log b ω h ω ω log θ dB ρ °× -90 n °-90 Fig. 1. Bode diagram of În (s)
Its frequency response is a suitable approximation of the theoretical one :

• The intermediate zone (ω b < ω < ω h ) corresponds to the non integer behavior of the integrator, characterized by n. • For low and high frequencies, the behavior of the integrator is conventional, with n = 1.

Finally, given N , n, ω b , ω h , the operator introduced by ( 3) is completely defined by the following relations 1 :

ω ′ 1 = ω b , ω N = ω h , ω u = √ ω b ω h , ω i = α ω ′ i , ω ′ i+1 = η ω i , n = 1 - ln α ln α η (4) v(t) = d n y(t) dt n x N +1 (t) = y(t) 1+ s ω ′ 1 1+ s ω 1 1+ s ω ′ N 1+ s ω N v(t) x N +1 (t) G s x 1 (t) • • • Fig. 2. În (s) block diagram
Using the block diagram shown in figure 2, În (s) can be described by the following state-space representation [START_REF] Poinot | A method for modelling and simulation of fractional systems[END_REF]:

• x = A * x + B * v (5)
1 In (3) G is defined so that the magnitude of În (s) is equal to the magnitude of 1 s n for the frequency ωu.

where

A * = M -1 A, B * = M -1 B, B T = [Gn 0 • • • 0], M =     1 0 • • • 0 -α . . . . . . . . . . . . . . . 0 0 • • • -α 1     , A =     0 0 • • • 0 ω1 -ω1 . . . . . . . . . . . . 0 0 • • • ωN -ωN    

CONTINUOUS TIME NEURAL NETWORKS

There are two main approaches to simulate dynamical systems with a neural network. The first one consists in using dynamical units (continuous time neurons). Many models have been proposed [START_REF] Hopfield | Neural networks and physical systems with emergent collective computational abilities[END_REF][START_REF] Pearlmutter | Gradient calculation for dynamic recurrent neural networks: a survey[END_REF][START_REF] Kos | High-order neural network structures for identification of dynamical systems[END_REF] and complex processes have been simulated or controlled by such networks. Nevertheless, the physical law of the process can not be extracted because dynamical and static components of the model are not separated.

The second approach is based on the use of a static net associated with an external dynamical component. Delay blocks (figure 3) may be used [START_REF] Narendra | Identification of nonlinear dynamical systems using neural networks[END_REF] in order to obtain a discrete representation of the system: ŷk+1 = g(u k , ŷk ) where g is the function computed by the net.

z -1 Network Neural u k y k y k+1
Fig. 3. Discrete time neural network Such models have been successfully investigated in process control [START_REF] Narendra | Adaptative control of dynamical systems using neural networks[END_REF] but don't give direct access to the physical law of the system 2 . An enhanced design has been proposed [START_REF] Wang | Rungekutta neural network for identification of dynamical systems in high accuracy[END_REF] to obtain a discretization of the process using the Runge-Kutta 4 (Rk4) scheme: the net approaches the physical law of the system with an high accuracy. Nevertheless, by using a discrete representation of the process, the whole neural structure and the identification procedure have to be adapted according to the desired accuracy (Euler, Rk4) or to the desired task.

We proposed a method [START_REF] Benoît-Marand | Non linear identification of continuous time systems using neural networks[END_REF][START_REF] Benoît-Marand | Neural identification of physical processes: Analysis of disruptive factors[END_REF], referred to as Ctnn: we use a static feed-forward neural network followed by a continuous integration method (figure 4). Our model is directly related with 2 Suppose dy(t) dt = f (u(t), y(t)) = au(t) + by(t), then the function computed by the static net is not equal to f but to e aT x(t) + b a (1 -e -aT )u(t), and in the non linear case we do not have such relation to revert to the physical law.

the continuous equation of the system: dy(t) dt = g (u(t), ŷ(t)) where g is the function computed by the net. Obviously, we can separate the static part of the process (the function computed by the net) from the dynamical one [START_REF] Benoît-Marand | Neural identification of physical processes: Analysis of disruptive factors[END_REF]. By definition the net gives us direct access to the physical law of the simulated process. The idea is simple but powerful. Indeed, we need to adapt neither the net structure nor the principles of the identification procedure if we change the integration method. In particular, the integrator may be a fractional integrator.

Presentation

In the following, we will consider a Ctnn dedicated to single input single output fractional systems. We use the single hidden layer static net described figure 5 followed by a non integer integrator (figure 6). Adjustable parameters of the model, called θ, are the 4N c parameters of the net which characterize the physical law and parameter α characterizing the derivative order of the fractional integrator. The aim of the identification stage is to find θ * which minimizes the following criterion 3 :

θ T = [w 1,1 • • • w 3,Nc b 1 • • • b Nc α] y u 1 tanh tanh tanh n 1 n j n N c b 1 b i b N c w 1,i w 2,i w 3,i s
J = K k=1 (y * k -y k ) 2 = k=K k=1 e 2 k 4.2 The Levenberg-Marquardt algorithm
We solve the previous optimization problem using the iterative Levenberg-Marquardt algorithm [START_REF] Marquardt | An algorithm for leastsquares estimation of non-linear parameters[END_REF][START_REF] Hagan | Training feedforward networks with the marquardt algorithm[END_REF]:

θ i+1 = θ i + ∆θ with ∆θ = ( H θ + λI) -1 J ′ θ J ′
θ is the gradient of J with respect to θ, H θ is the pseudo-hessian matrix of J with respect to θ, and λ is a control parameter of the algorithm. J ′ θ and H θ are computed using the following relations:

J ′ θ = -2 k=K k=1 e k • ∂ y k ∂θ H j,l = 2 K k=1 ∂ y k ∂θ j • ∂ y k ∂θ l
Let's define the value of the sensitivity function of the parameter p for the sample k as σ p (k) = ∂ y k ∂θp . To solve the optimization problem we have to compute this value for all p and all k.

Calculus of the sensitivity functions associated with the parameters of the neural network

This calculus is referred to as dynamic back propagation [START_REF] Narendra | Gradient methods for the optimization of dynamical systems containing neural networks[END_REF] and has already been successfully used in the case of integer Ctnn [START_REF] Benoît-Marand | Non linear identification of continuous time systems using neural networks[END_REF]. It can directly be extended to fractional Ctnn (0 < n < 1). We simply write:

d n σ p (t) dt n = ∂ ∂θ p d n y dt n (θ, u(t), y(θ, t)) = ∂ ∂θ p (s(θ, u(t), y(θ, t)) = ∂s(t) ∂θ p + ∂s(t) ∂ y(t) • ∂ y(t) ∂θ p = ∂s(t) ∂θ p + ∂s(t) ∂ y(t) • σ p (t)
So, the sensitivity functions associated with the neural network parameters can be simulated by 3 K is the size of the data set using the non integer integrator used in the Ctnn model.

The computation of ∂s(t) ∂θp is performed with the well-known back propagation algorithm [START_REF] Cun | Une procédure d'apprentissage pour réseau à seuil assymétrique[END_REF][START_REF] Rumelhart | Learning representations by backpropagating errors[END_REF]

4 : ∂s(k) ∂b i = tanh(n i (k)) ∂s(k) ∂w i,j = r i (k) • tanh ′ (n j (k)) • b j The value of ∂s(t) ∂ y(t)
is easy to compute:

∂s(t) ∂ y(t) = i=N c i=1 w 1,i • tanh ′ (n i (t)) • b i

Calculus of the sensitivity function associated with the parameter of the non integer integrator

To evaluate σ α (t) = ∂ ŷ(t) ∂α we derivate the state space representation (5) with respect to α. Extending the state space vector with x (N +1+i) (t) = ∂xi(t) ∂α , we obtain the following modified state space representation:

• x = C * x + D * v (6)
where:

v T = f (u(t), ŷ(t), θ) ∂f ∂ ŷ(t) σα(t) C * = R -1 C D * = R -1 D ŷ(t) = x (N+1) (t) σα(t) = x (2N+2) (t) D = D 1 0 D 2 D 1 R = M 0 R 1 M C = A 0 C 1 A
M , A are the matrices defined in (5). D 1 , D 2 (vectors of size N + 1) and R 1 , C 1 (square matrices of size N + 1) are defined as follows:

D 1 T = G 0 • • • D 2 T = ∂G ∂α 0 • • • R 1 =     0 -1 . . . . . . . . . -1 0     C 1 =      0 ∂ω 1 ∂α - ∂ω 1 ∂α . . . . . . ∂ω N ∂α - ∂ω N ∂α      ∂ω 1 ∂α = ω b ∂ω i ∂α = αη ∂ω i-1 ∂α + ω i-1 η + α ∂η ∂α ∂η ∂α = ω h ω b 1 N -1 N 1 -N α 2N -1 1-N Finally, let's calculate ∂G ∂α . G is such that magnitudes of În (ω) = G jω 1+ jω ω ′ k 1+ jω ω k
and 1 (jω) n are equal if ω = ω u . As a consequence:

G = ω 1-n u 1 G k
Where G k is the magnitude of the k th cell of În (s). Then :

∂G ∂α = -ln(ω u ) ∂n ∂α G + 1 2 G k=N k=1 G 2 k ∂ ∂α 1 G 2 k ∂ ∂α 1 G 2 k = {ω 2 k +α 2 ω 2 u } -2 2ω k ∂ω k ∂α (ω 2 k +α 2 ω 2 u ) -(ω 2 k +ω 2 u ) 2ω k ∂ω k ∂α +2αω 2 u ∂n ∂α = η + α ∂η ∂α ln(α) -η ln(αη) αη [ln(αη)] 2
Often, ω b and ω h are such that ω u = √ ω b ω h = 1. In this particular case :

∂G ∂α = 1 2 G k=N k=1 G 2 k ∂ ∂α 1 G 2 k ∂ ∂α 1 G 2 k = 2(α 2 -1) ∂ω k ∂α ω k -2α(ω 2 k + 1) (ω 2 k + α 2 ) 2
We are now able to evaluate the sensitivity function ∂ ŷ ∂α .

SIMULATION RESULTS

We simulated the following system 5 : d n y (t) dt n = au (t) + by 2 (t) with a = 1, b = -1, n = 0.6, ω b = 10 -4 rad/s, ω h = 10 4 rad/s and N = 20. Noise free and noisy data sets are plotted on figures 7 and 8. The network has been initialized using a simple heuristic and n has been initialized to 0.3.

5 All simulations have been perfomed by using MATLAB R and SIMULINK R products. In this article, we introduced the fractional Ctnn model, based on the use of a static neural network followed by a non integer integrator block. Our results show that fractional Ctnn allow to estimate, with an high accuracy, both the non integer derivative order and the physical law of a non linear fractional system.

At present, we are validating our identification method of fractional systems using Ctnn on a real heat transfer system. Moreover, we are trying to extend the equation error method (Eei) to the identification of fractional order n. Indeed, we already experimented, in the case of integer systems, that a combination of Eei and Oei drastically reduces the identification time (which is the main problem encountered with the Oei method).

  Fig. 4. A Continuous Time Neural Network Ctnn

Fig. 5 .Fig. 6 .

 56 Fig. 5. The static neural network used in the Ctnn

Fig. 7 .

 7 Fig. 7. Noise free data set

Fig. 8 .Fig. 10 .

 810 Fig. 8. Noisy data set (white noise, S/B = 10) Ctnn optimization results using either noise free or noisy data are plotted on figure 9 and 10. We performed 60 iterations of the Levenberg-Marquardt algorithm.

In the following equation r i (k) represents the input i of the net for the sample k. For example r 1 (k) = ŷ(k). Notice that tanh ′ (x) = 1 -tanh 2 (x)

In this particular case, the function to be identified is known but in more realistic cases we should try different expressions and see which one is the more adapted to the system.


Andrey Polyakov
email: andrey.polykov@inria.fr

On Expansion of Regularity of Nonlinear Evolution Equations by Means of Dilation Symmetry

Keywords:

The paper present a dilation symmetry based approach to expansion of regularity of nonlinear evolution equations. In particular, it is shown that a symmetry of an operator, which describes a right-hand side of a nonlinear evolution equation, is inherited by solutions of this equation. In the case of dilation symmetry, the latter implies that global-in-time existence of solutions for small initial data always imply global-in-time existence of solutions for large initial data. As an example, we consider the problem of expansion of regularity of the Navier-Stokes equations (in R n ) accepting that the existence of global-in-time solutions for small initial data is already proven.

Introduction

According to the classical concept of homogeneity introduced by Leonhard Euler in 18th century, homogeneity is a sort of symmetry of an object (e.g. a function or a set) with respect to a group of transformations knows today as dilations. For example, a function f in R n is homogeneous in the classical (standard) sense if it is symmetric with respect to a uniform dilation of an argument, i.e. there exists ν ∈ R such that f (e s u) = e (ν+1)s f (u), u ∈ R n , s ∈ R.

Homogeneity of a function is inherited by other objects induced by this function. For example, the Euler's Homogeneous Function Theorem implies that any derivative of f is homogeneous too. Similarly, if u(•) : [0, +∞) → R n is a classical solution of du dt = f (u), t > 0 with the initial condition u(0) = u 0 then u s (t) := e s u(e νs t) is defined on [0, +∞), then, due to symmetry, we derive dus dt = e (ν+1)s f (u(e νs t)) = f (u s (t)), t > 0, i.e. u s is a classical solution of the same differential equation with the initial condition u s (0) = e s u 0 , where s ∈ R.

Let ∃ε > 0 such that a classical solution of the differential equation exists on [0, +∞) for any initial value u(0) = u 0 ∈ B ε := {u ∈ R n : u < ε}. Hence, exploiting the symmetry we derive existence of a classical solution for any initial condition u(0) = u 0 ∈ s∈R e s B ε = R n .

For non-linear evolution system, it may be simpler to prove existence and uniqueness of a regular solution for small initial data. In this paper we show that the dilation symmetry can be utilized for global expansion of regularity non-linear evolution equations in a Banach space B provided that a dilation group is properly introduced in B. As an example, we consider the problem of expansion of regularity of the Navier-Stokes equations (in R n ) accepting that the existence of global-in-time solutions for small initial data is already proven. In particular, we present a necessary and sufficient conditions for expansion of regularity of Navier-Stokes equation by means of dilation symmetry.

Mainly, the standard notation is utilized through the paper, e.g. R is the field of real numbers; L 1 loc ((0, T )×R n , R) denotes the space of locally integrable functions (0,

T ) × R n → R; L p (R n , R m ), 1 ≤ p ≤ +∞ is a Lebesgue space of function R n → R m with the norm • p ; C ∞ c ((0, T ) × R n , R m ) is a space of smooth functions (0, T ) × R n → R m with compact support and C ∞ 0 ([0, T ) × R n , R m
) is a space of smooth functions which vanish at infinity, where 0 < T ≤ ∞. For composition of operators A, B we also use the notation A • B.

Let L p µ (R n , R m ) denotes the following normed vector space of functions

R n → R m L p µ (R n , R m ) := {u : u p,µ < +∞} , µ ∈ R u p,µ := R n |x| µp |u(x)| p dx 1/p , 0 < p < ∞ u ∞,µ := ess sup(|x| µ u(x)), p = ∞,
which can be treated as a wighted L p . The notation a.e.

∈ and

a.e.

= is utilized in order to indicate that an inclusion or identity is fulfilled almost everywhere on a domain.

Symmetry of nonlinear operators

Dilation group

Let X be a (linear) vector space and {d(s)} s∈R be a family of operators d(s) : X → X. If

• d(0) = I, where I is an identity operator (i.e. Iz = z for all z ∈ X);

• d(t + s)z = (d(t) • d(s))z = (d(s) • d(t))z for all t, s ∈ R, z ∈ X then, by definition, d is a group. Using the group properties for t = -s we derive (d(-s) • d(s))z = (d(s) • d(-s))z = z, the operator d(s) is invertible and [d(s)] -1 = d(-s).
Moreover, d(s) maps X onto X for any s ∈ R. Indeed, suppose the contrary, i.e. ∃z * ∈ X and such

s * ∈ R such that z * / ∈ d(s * )X. Since u * := d(-s * )z * ∈ X then z * = d(s)d(-s * )z * = d(s)u * ∈ d(s)X.
Definition 1 A group d of operators on a normed vector space X is said to be a dilation group (or simply dilation) on X if d(s) 0 = 0 for any s ∈ R and the following limit property holds lim inf s→-∞ d(s)z = 0 and lim sup s→+∞ d(s)z = ∞ for z = 0 .

The limit property given above specifies a group being a dilation in an abstract space. We refer the reader to [START_REF] Husch | Topological characterization of the dilation and the translation in frechet spaces[END_REF] for more details about topological characterization of dilations. where r i > 0, i = 1, 2, ..., n. 3) Geometric dilation (see e.g. [START_REF] Khomenuk | On systems of ordinary differential equations with generalized homogenous right-hand sides[END_REF], [START_REF] Rosier | Etude de quelques problèmes de stabilization[END_REF], [START_REF] Kawski | Geometric homogeneity and stabilization[END_REF]) is a flow generated by an Euler vector field1 .

The uniform dilation d(s) = e s I ∈ B, s ∈ R is the simplest example of a dilation in any normed vector space. Let us consider a few other examples.

Example 2 Let B be a space of bounded uniformly continuous functions R n → R m with the supremum norm. A dilation group d in B can be defined as follows

(d(s)z)(x) = e αs z(x + βs),
where s ∈ R is the group parameter, z ∈ X, x ∈ R and α > 0 and β ∈ R are a constant parameters. Indeed, d(s)z ∈ X if z ∈ B, s ∈ R and for v = d(s)z we have

(d(t)•d(s)z)(x) = (d(t)v)(x) = e αt v(x+βt) = e αt e αs z(x+βs+βt) = (d(s+t)z)(x).
The limit property also holds since

where s ∈ R, z is a function R n → R m , x ∈ R n and α, β ∈ R are constant parameters, is -a linear bounded invertible operator on L p (R n , R m ), d(s)z p = e (α-nβ/p)s z p , z ∈ L p (R n , R m ), s ∈ R, -a linear bounded invertible operator on L p µ (R n , R m ), d(s)z p,µ = e (α-β(µ+n/p))s z p,µ , z ∈ L p µ (R n , R m ), s ∈ R, where 0 < p ≤ ∞. The inverse operator is given by [d(s)] -1 = d(-s). Proof Notice that L p = L p 0 . Let 1 ≤ p < ∞. If z ∈ L p µ (R n , R m ) then R n |x| µp |z(x)| p dx < +∞ and R n |x| µp |z(x)| p dx = e nβs R n |e βs x| µp |z(e βs x)| p dx = e ((n+µp)β-αp)s R n |x| µp (d(s)z)(x)| p dx < +∞. Since e ((n+µp)β-αp)s > 0 for any α, β, p, s ∈ R then d(s)z ∈ L p µ (R n , R m ) for any s ∈ R. Obviously, d(s) is a linear operator on L p µ , i.e. d(s)(µ 1 z 1 + µz 2 ) = µ 1 d(s)z 1 + µ 2 d(s)z 2 , for any µ 1 , µ 2 ∈ R and z 1 , z 2 ∈ L p µ (R n , R m ). (1)
Moreover, the latter identities imply that

d(s)z p,µ = e (α-(n/p+µ)β)s z p , z p,µ := R n |x| µp |z(x)| p dx 1/p .
Hence, the operator d(s) :

L p (R n , R m ) → L p (R n , R m ) is bounded for any s ∈ R . Let p = ∞. If z ∈ L ∞ µ (R n , R m

d-homogeneous operators

In this section we introduce a notion of d-homogeneous (symmetric with respect to a group d) operators in a vector space X and present a couple of examples.

Definition 2 An operator F : D(F ) ⊂ X → X is said to be d- homogeneous of degree µ ∈ R if d(s)D(F ) ⊂ D(F ) for any s ∈ R and (F • d(s))u = e µs (d(s) • F )u for s ∈ R, u ∈ D(F ), (2)
where d is a group of invertible operators on X.

A lot of examples of d-homogeneous vector-field for X = R n can be found in control literature (see e.g. [START_REF] Zubov | On systems of ordinary differential equations with generalized homogenous right-hand sides[END_REF], [START_REF] Rosier | Etude de quelques problèmes de stabilization[END_REF], [START_REF] Kawski | Geometric homogeneity and stabilization[END_REF] and references therein). For example, the vector function

(x 1 , x 2 ) → x 1 + x 2 2 , |x 2 | sin x 1 -x 2 2 |x 1 | + x 2 2 , (x 1 , x 2 ) ∈ R 2 is d-homogeneous of degree 0 with d(s)(x 1 , x 2 ) → (e 2s x 1 , e s x 2 ), s ∈ R.
All linear and lot of nonlinear models of mathematical physics are d-homogeneous under a proper selection of a dilation group (see e.g. [START_REF] Polyakov | On homogeneous distributed parameters equations[END_REF]). Notice that, the identity (2) can always be understood in the weak sense. For shortness we omit R n in the notations for

R n , L 2 (R n , R n ),L 1 loc (R n , R n ) and C ∞ 0 (R n , R n ) in the examples below.

Example 3 (d-homogeneity of the Laplace operator)

Let us consider the Laplace operator

∆ : D(∆) ⊂ L 2 → L 2 ,
with the domain

D(A) = u ∈ L 2 : ∃f ∈ L 1 loc such that u • ∆φ = f • φ, ∀φ ∈ C ∞ c .
Let us show that ∆ is d-homogeneous of degree 2β provided that the dilation d is given by [START_REF] Fushchych | Symmetry reduction and exact solutions of the navierstokes equations[END_REF]. By Lemma 1, d is a group of linear invertible operators on C ∞ c and, consequently (see the beginning of Section 2),

d(s) maps C ∞ c onto C ∞ c . Notice that if φ ∈ C ∞ c then, obviously, (∆ • d(s))φ)(x) = e (α+2β)s (∆φ)(e βs x) = e 2βs ((d(s) • ∆)φ)(x), s ∈ R, x ∈ R n .
In other words, the Laplace operator is d-homogeneous as operator

C ∞ c → C ∞ c . Since C ∞ c is dense in L 2 then it is d-homogeneous as an operator L 2 → L 2 . Let us prove this claim more rigorously. Let u ∈ D(∆) and ∆u = f ∈ L 1 loc (in the weak sense). Since d(s)f ∈ L 1 loc
then using the change-of-variable theorem (see e.g. [START_REF] Netuka | The change-of-variables theorem for the lebesgue integral[END_REF]) in the Lebesgue integral we derive

e 2βs (d(s)f )•φ = e (α+2β)s f (e βs x)•φ(x)dx = e (α+(2-n)β)s f (x)•φ(e -βs x)dx = e (2α+(2-n)β)s f • φ = e (2α+(2-n)β)s u • ∆ φ = e (2α+(2-n)β)s u • (∆ • d(-s))φ = e (α-nβ)s u(x) • ∆φ(e -βs x)dx = e αs u(e βs x) • ∆φ(x)dx = (d(s)u) • ∆φ, where φ = d(-s)φ ∈ C ∞ c . Hence, d(s)u ∈ D(∆) and (∆•d(s))u = e 2βs d(s)f = e 2βs (d(s) • ∆)u (in the weak sense) for any s ∈ R, u ∈ D(∆).
3 Symmetry of Evolution Equations

Linear evolution equation

The dilation symmetry of an operator is inherited by other objects induced (generated) by this operator.

Φ(t) • d(s) = d(s) • Φ(e µs t), ∀t ≥ 0, ∀s ∈ R. ( 3
)
Proof Since Φ is generated by A then Φ(e µs t)u ∈ D(A) for any u ∈ D(A) (see e.g. [8, page 5]). Let s ∈ R and u ∈ D(A) be selected arbitrary. Since the operator A is dhomogeneous then D(A) is invariant with respect to the transformation d(s), i.e. d(s)z ∈ D(A), ∀z ∈ D(A), and, consequently,

y 1 (t) := (Φ(t)•d(s))u ∈ D(A)
d dt Φ(t)z = (A • Φ(t))z = (Φ(t) • A)z, ∀t > 0, ∀z ∈ D(A).
Taking into account that A is d-homogeneous of degree µ and d(s) is a linear bounded operator on B, we derive

d dt y 2 (t) = e µs (d(s) • A • Φ(e µs t))u = (A • d(s) • Φ(e µs t))u = Ay 2 (t), ∀t > 0.
On the other hand, we have

d dt y 1 (t) = (A • Φ(t) • d(s))u = Ay 1 (t), ∀t > 0.
Since y 1 (0) = y 2 (0) = d(s)u then due to uniqueness of the semigroup Φ generated by A (see [8, page 6]) we derive y 1 (t) = y 2 (t) for all t ≥ 0 and

(Φ(t) • d(s))u = (d(s) • Φ(e µs t))u, ∀t ≥ 0, ∀u ∈ D(A).
Since Φ(t) • d(s) and d(s) • Φ(e µs t) are bounded linear operators and D(A) is dense in B then the latter identity holds for all u ∈ B and all t ≥ 0.

It is well-known (see e.g. [8, page 100]) that u(t, u 0 ) = Φ(t)u 0 , t ≥ 0 is a unique solution of the linear evolution equation

du dt = Au
with the initial condition u(0) = u 0 ∈ B. The latter lemma, obviously, proves the symmetry of these solutions:

u(t, d(s)u 0 ) = d(s)u(e µs t, u 0 ), s ∈ R
Below we prove this result for non-linear operators too.

Nonlinear evolution equation

Let us consider the non-linear evolution system

du dt = Au + Gu, t > 0, (4)
where a densely defined closed linear operator

A : D(A) ⊂ B → B
generates a strongly continuous semigroup Φ of linear bounded operators on B, and

G : D(G) ⊂ B → B
is a possibly nonlinear operator.

Definition 3 A continuous function u : [0, T ) → B is said to be a mild solution of the system (4) if Gu ∈ L 1 ((0, T ), B) and

u(t) = Φ(t)u(0) + t 0 (Φ(t -τ ) • G)u(τ ) dτ, t ∈ (0, T ); (5)
a strong solution of the evolution equation ( 4) if u ∈ C([0, T ), B), u is differentiable almost everywhere on (0, T ), du dt , Gu ∈ L 1 ((0, T ), B) and ( 4) is satisfied almost everywhere on (0, T ); a classical solution of the evolution equation ( 4

) if u ∈ C([0, T ), B), du dt ∈ C((0, T ), B), u(t) ∈ D(A) ∩ D(G)
for all t ∈ (0, T ) and ( 4) is satisfied on (0, T ). The latter integral is understood in the sense of Bochner ([13, page 132]).

Theorem 1 Let d be a group of linear bounded invertible operators on B and let A and G be d-homogeneous operators of a degree µ ∈ R.

If u : [0, T ) → B is a mild (or strong) solution of the evolution equation (4) and u(t)

a.e.

∈ D(G), t ∈ (0, T ), then the function u s : [0, e -µs T ) → B defined as

u s (t) = d(s)u(e µs t), t ∈ [0, e -µs T )
is also a mild (resp. strong) solution of the evolution equation (4) and

u s (t)
a.e.

∈ D(G), t ∈ (0, e -µs T ),

for any s ∈ R. Moreover, the claim remains true for classical solutions and the above inclusions hold everywhere on (0, T ) and (0, e -µs T ), respectively.

Proof If u(t) ∈ D(G) then due to d-homogeneity of the operator G we have d(s)D(G) ⊂ D(G) and u s (e -µs t) ∈ D(G).

1) The case of mild solutions.

Since the d-homogeneous operator A generates a strongly continuous semigroup Φ, then according Lemma 2 we have

Φ(t) • d(s) = d(s) • Φ(e µs t), ∀t ≥ 0, ∀s ∈ R.
It is well known [13,

(Φ(t -σ) • d(s) • G)u(e µs σ)) dσ = (Φ(t) • d(s))u(0) + t 0 (Φ(t -σ) • G)(d(s)u(e µs σ)) dσ,
where the linearity of the operator Φ(t -σ) and the d-homogeneity of the operator G are utilized on the last step. Therefore, we have shown that

u s (t) = Φ(t)u s (0) + t 0 (Φ(t -σ) • G)u s (σ) dσ,
i.e. u s is a mild solution of (4).

2) The case of strong and classical solutions. Let u be a strong solution. Since u(t) is differentiable almost everywhere and d(s) is a linear bounded operator then for τ = e µs t we have = e µs d(s)(Au(τ )+G(u(τ ))

a.e.

= Au s (t)+G(u s (t)).

In the case of the classical solution the latter identity holds everywhere. Moreover, if u(t) ∈ D(A) then due to d-homogeneity of the operator A we always have u s (t) ∈ D(A). Finally, taking into account that the operator d(s) is bounded we conclude u s ∈ C([0, T ), B) provided that u ∈ C([0, T ), B and d dt u s ∈ C((0, T ), B) provided that d dt u ∈ C((0, T ), B, i.e. u s is also a classical solution.

Remark 1 The proven symmetry of solutions of the evolution equation ( 4) allows us to guarantee that a local result holds globally. For example, let us consider the initial value problem u(0) = u 0 for (4). If D(G) = B then an existence of a solution for any u 0 ∈ B(r) implies existence of solutions for all u 0 ∈ B, where B(r) is a ball in B of the radius r > 0. Indeed, using the limit property of the dilation d we derive that for any u 0 ∈ B there exists s ∈ R such that d(s)u 0 < r, i.e. d(s)u 0 ∈ B(r). By Theorem 1, if u(t, d(-s)u 0 ) is a solution of the initial value problem u(0) = d(-s)u 0 ∈ B(r) then u s (t, u 0 ) := d(s)u(e µs t, d(-s)u 0 ) is also a solution of the evolution equation ( 4). Since

d(s)u(0, d(-s)u 0 ) = d(s)d(-s)u 0 = u 0 then u s is a solution of the initial value problem u(0) = u 0 ∈ B for (4).
Notice that if all solutions with u 0 ∈ B(r) exist on [0, +∞) then all solutions with u 0 ∈ B also exist on [0, +∞). Below we show possible cases when such an approach allows to expand regularity of solutions of the Navier-Stokes equations provided that it is already proven for small initial data (see e.g. [START_REF] Leray | Sur le mouvement d'un liquide visqueux que limitent des parois[END_REF] and [START_REF] Ozanski | Leray's fundamental work on the Navier-Stokes equations: a modern review of "Sur le mouvement d'un liquide visqueux emplissant l'espace[END_REF]). Some other applications of a dilation symmetry in evolution equations, for example, to problems of mathematical control theory can be found in [START_REF] Polyakov | On homogeneous distributed parameters equations[END_REF], [START_REF] Polyakov | On homogeneous finite-time control for linear evolution equation in hilbert space[END_REF].

Nonlinear implicit evolution equation

Let X = B × X, where B is Banach space and X is a linear (vector) space. Let us consider the nonlinear implicit evolution equation

du dt = Au + G(u, p), 0 = Q(u, p), t > 0, ( 6
)
where a densely defined closed linear operator

A : D(A) ⊂ B → B
generates a strongly continuous semigroup Φ of linear bounded operators on B, and

G : D(G) ⊂ X → B and Q : D(Q) ⊂ X → X
u(t) = Φ(t)u(0)+ t 0 (Φ(t -τ ) • G)(u(τ ), p(τ )) dτ, 0 a.e. = Q(u(t), p(t)), t ∈ (0, T ); (7)
a strong solution of the implicit evolution equation ( 6) if u ∈ C([0, T ), B), u is differentiable almost everywhere on (0, T ), du dt , G(u, p) ∈ L 1 ((0, T ), B) and ( 6) is satisfied almost everywhere on (0, T ); a classical solution of the evolution equation ( 6 6) is satisfied on (0, T ).

) if u ∈ C([0, T ), B), du dt ∈ C((0, T ), B), u(t) ∈ D(A) and (u(t), p(t)) ∈ D(G) ∩ D(Q) for t ∈ (0, T ) and (
A symmetry of solutions of the implicit evolution equation ( 6) is also preserved provided that the operator, which defines its right-side is d-homogeneous.

Theorem 2 Let a group d of invertible operators on X be defined as follows

d(s)(u, p) = (d 1 (s)u, d 2 (s)p), s ∈ R, u ∈ B, p ∈ X,
where d 1 is a group of linear bounded invertible operators on B, d 2 is a group of invertible operators on X such that

d 2 (s) 0 = 0, s ∈ R. Let us denote F := (G, Q) and D(F ) := D(G) ∩ D(Q), F : D(F ) ⊂ X → X.
Let A be a d 1 -homogeneous operator of a degree µ ∈ R and F be dhomogeneous operator of the same degree µ.

If the pair (u, p) with u : [0, T ) → B and p : [0, T ) → X is a mild (or strong) solution of the implicit evolution equation (6) such that (u(t), p(t))

a.e ∈ D(F ), t ∈ (0, T ), then the pair (u s , p s ) with u s : [0, e -µs T ) → B and p : [0, T ) → X defined as follows (u s (t), p s (t)) := d(s)(u(e µs t), p(e µs t)) with t ∈ [0, e -µs T ) is also a mild (resp. strong) solution of the evolution equation ( 4) and (u s (t), p s (t))

a.e ∈ D(F ), t ∈ (0, e -µs T ) for any s ∈ R.

Moreover, the claim remains true for classical solutions and the above inclusions hold everywhere on (0, T ) and (0, e -µs T ), respectively.

Proof Since the operator F is d homogeneous then

d(s)D(F ) ⊂ D(F ) and G(d 1 (s)u, d 2 (s)p) = e µs (d 1 (s) • G)(u, p), ∀(u, p) ∈ D(F ), ∀s ∈ R, Q(d 1 (s)u, d 2 (s)p) = e µs (d 2 (s) • Q)(u, p), ∀(u, p) ∈ D(F ), ∀s ∈ R. Hence, if (u(t), p(t)) ∈ D(F ) we conclude (u s (e -µ s t), p s (e -µ s t)) ∈ D(F ).
1) The case of mild solutions.

Since the d 1 -homogeneous operator A generates a strongly continuous semigroup Φ, then according Lemma 2 we have

Φ(t)d 1 (s) = d 1 (s)Φ(e µs t), ∀t ≥ 0, ∀s ∈ R.
It is well known [13, page 134] that K t 0 ξ(s)ds = t 0 Kξ(s)ds for any bounded linear operator K : B → B and any Bochner integrable function ξ. Hence, using G(u, p) ∈ L 1 ((0, T ), B) we derive

d 1 (s) t 0 G(u(τ ), p(τ ))dτ = t 0 d 1 (s)G(u(τ ), p(τ ))dτ = e -µs t 0 G(d 1 (s)u(τ ), d 2 (s)p(τ ))dτ = e -µs t 0 G(d 1 (s)u(e µs τ ), d 2 (s)p(e µs τ ))dτ = e -µs t 0 G(u s (τ ), p s (τ ))dτ, i.e. G(u s , p s ) ∈ L 1 ((0, e -µs T ), B). Similarly, we derive d 1 (s)u(e µs t) = (d 1 (s)•Φ(e µs t))u(0)+d 1 (s) e µs t 0 (Φ(e µs t-τ )•G)(u(τ ), p(τ )) dτ = (Φ(t) • d 1 (s))u(0) + e µs t 0 (d 1 (s) • Φ(e µs t -τ ) • G)(u(τ ), p(τ )) dτ = (Φ(t) • d 1 (s))u(0) + e µs t 0 (d 1 (s) • Φ(e µs (t -σ)) • G)(u(e µs σ), p(e µs σ)) dσ = (Φ(t) • d 1 (s))u(0) + e µs t 0 (Φ(t -σ) • d 1 (s) • G)(u(e µs σ), p(e µs σ)) dσ = (Φ(t) • d 1 (s))u(0) + t 0 (Φ(t -σ) • G)(d 1 (s)u(e µs σ), d 2 (s)p(e µs σ)) dσ,
where the linearity of Φ(t -σ) and a homogeneity of the operator G is utilized on the last step. Therefore, we have shown that

u s (t) = Φ(t)u s (0) + t 0 Φ(t -σ)g(u s (σ), p s (σ)) dσ.
Finally, since (u, p) is a mild solution on [0, T ) then

Q(u(t), p(t))
a.e. = 0, ∀t ∈ [0, T ) and using the identity d 2 (s) 0 = 0 we derive

Q(u s (τ ), u s (τ )) = Q((d 1 (s)u)(τ ), (d 2 (s)p)(τ )) = e µs (d 2 (s) • Q)(u(e µs τ ), p(e µs τ )) a.e. = 0, τ ∈ [0, e -µs T ).
2) The case of strong and classical solutions. Let (u, p) be a strong solution. Since u(t) is differentiable almost everywhere and d(s) is a linear bounded operator then for τ = e µs t we have a.e.

= Au s (t)+G(u s (t), p s (t)).

In the case of the classical solution the latter identity holds everywhere. Moreover, if u(t) ∈ D(A) then due to d-homogeneity of the operator A we always have u s (t) ∈ D(A), i.e. u s is a classical solution. The classical idea of analysis is to prove, initially, an existence and regularity of weak solutions and next to show that any weak solution is smooth. For Navier-Stokes equations this scheme has been realized by Jean Leray in 1938 (see, e.g. [START_REF] Leray | Sur le mouvement d'un liquide visqueux que limitent des parois[END_REF] and the recent review [START_REF] Ozanski | Leray's fundamental work on the Navier-Stokes equations: a modern review of "Sur le mouvement d'un liquide visqueux emplissant l'espace[END_REF]). We follow the same way having in mind d-homogeneity (dilation symmetry) of Navier-Stokes equations (see e.g. [1, formula (1.5)]), which will guarantee a global expansion of all local results.

Dilation Symmetry of Navier-Stokes equation in R n

Let V be a set of the so-called weakly divergence free velocity fields:

V := u ∈ L 2 : u • ∇φ = 0, ∀φ ∈ C ∞ 0 .
Due to this the Navier-Stokes equations can be equivalently represented in the form of the d-homogeneous implicit evolution equation ( 6) with the operators

A = ∆, G(u, p) = -∇p -(u • ∇)u, Q(u, p) = divu having the domains D(Q) = V × L 1 loc (R n , R), D(A) = u ∈ L 2 : ∃f ∈ L 1 loc such that u • ∆φ = f • φ, ∀φ ∈ C ∞ 0 , D(G) = (u, p) ∈ V ×L 1 loc : ∃f ∈ L 1 loc , u•(u•∇)φ-pdivφ+f •φ = 0, ∀φ ∈ C ∞ 0 . Lemma 3 Let d(s) : X → X with X := L 2 × L 1 loc (R n , R) be defined as d(s)(u, p) = (d 1 (s)u, d 2 (s)p), s ∈ R, u ∈ L 2 , p ∈ L 1 loc (R n , R),
where d 1 is a group of linear bounded invertible operators on L 2 ,

(d 1 (s)u)(x) = e s u(e s x), u ∈ L 2 , x ∈ R n ,
and d 2 is a group of linear invertible operators on L 1 loc (R n , R) given by

(d 2 (s)p)(x) = e 2s p(e s x) p ∈ L 1 loc , x ∈ R n .
Then the operator

F : D(F ) ⊂ X → X with D(F ) = D(G) ∩ D(Q) and F = (G, Q) is d-homogeneous of degree 2.
Proof To complete the proof we must show that

G(d 1 (s)u, d 2 (s)p) = e 2s (d 1 (s) • G)(u, p), ∀(u, p) ∈ D(G), ∀s ∈ R, Q(d 1 (s)u, d 2 (s)p) = e 2s (d 2 (s) • Q)(u, p), ∀(u, p) ∈ D(Q), ∀s ∈ R.
e (n-3)s (d 1 (s)u) • (∇d 1 (s)φ) = 0, ∀φ ∈ C ∞ 0 . Since d 1 (s) maps C ∞ 0 onto C ∞ 0 then d 1 (s)V ⊂ V for any s ∈ R and (Q • d(s))(u, p) = 0 = e 2s d 2 (s) 0 = e 2s (d 2 (s) • Q)(u, p)
1 for all s ∈ R and, at least, on D(Q).

2) The identity Therefore, F is, indeed, d-homogeneous of degree 2.

G(u, p) = f ∈ L 1 loc (in the weak sense) means u•(u•∇)φ -p divφ+f • φ = 0, ∀φ ∈ C ∞ 0 . If p ∈ L 1 loc and u ∈ L 2 then from Lemma 1 we derive d 1 (s)u ∈ L
The d-homogeneity of the Laplace operator ∆ is studied in Example 3. Therefore, the Navier-Stokes equation satisfy all conditions required for application of Theorem 2. In other words, if it has mild, strong or classical solutions defined on [0, +∞) for small initial values then it has, respectively, mild, strong or classical solutions defined on [0, +∞) for large initial values.

Notice that taking µ 1 = µ 2 = 0 we derive the usual L q1 and L q2 spaces in the latter corollary.

Let us consider also the well-known weak form (see e.g. [START_REF] Leray | Sur le mouvement d'un liquide visqueux que limitent des parois[END_REF] and the recent review u(t) ∞ is bounded as t → 0 + and ( 9) is satisfied.

According to [START_REF] Ozanski | Leray's fundamental work on the Navier-Stokes equations: a modern review of "Sur le mouvement d'un liquide visqueux emplissant l'espace[END_REF] the considered solution can be treated as a mild solutions obtained using the so-called Oseen kernel.

Let us mention the following properties of the solutions introduced by Definition 5 (proven for n = 3):

-Global-in-time existence for small initial data [7, Corollary 3.13 and Lemma 3.10] There exist ε > 0 and C > 0 such that for any u 0 ∈ {u ∈ V : u 2 2 u ∞ < ε} [START_REF] Polyakov | On homogeneous finite-time control for linear evolution equation in hilbert space[END_REF] or u 0 ∈ {u ∈ V : u 2 ∇u 2 < ε} [START_REF] Polyakov | On homogeneous distributed parameters equations[END_REF] or u 0 ∈ {u ∈ V : u 2(q-3) 2 u q q < ε}, q > 3 (

a strong solution (u, p) with the initial data u(0) = u 0 exists on [0, +∞) and u(t) ∞ ≤ C u 0 ∞ . -Uniqueness of strong solutions [START_REF] Ozanski | Leray's fundamental work on the Navier-Stokes equations: a modern review of "Sur le mouvement d'un liquide visqueux emplissant l'espace[END_REF]Theorem 3.9] For any u 0 ∈ V ∩ L ∞ a strong solution with u(0) = u 0 is unique.

Example 1 1 ) 2 )e

 112 Let us recall a few well-know dilation groups in R n : Uniform dilation (L. Euler, 18th century): d(s) = e s I, s ∈ R where I is the identity matrix R n×n . Weighted dilation [14]: r1s 0 ... 0 0 e r2s ... 0 ... ... ... ... 0 ... ... e rns

Lemma 1

 1 d(s)z = sup x∈R n |e αs z(x + s)| = e αs sup x∈R n |z(x + βs)| = e αs z . The next lemma introduces the most common dilation in functional spaces. The operator d(s) given by (d(s)z)(x) = e αs z(e βs x),

  ) then ess sup|z(x)| = ess sup(|e βs x| µ |z(e βs x)|) < +∞ for any β, s, µ ∈ R and d(s)z ∞ = e (α-βµ)s z ∞ for any s ∈ R. Therefore, d(s) is also a linear bounded operator on z ∈ L ∞ (R n , R m ). Obviously, (d(s) • d(-s))z = (d(-s) • d(s))z for any z : R n → R n and any s ∈ R and we derive [d(s)] -1 = d(-s).

Lemma 2

 2 Let a linear closed densely defined operator A : D(A) ⊂ B → B generate a strongly continuous semigroup Φ := {Φ(t)} t≥0 of linear bounded operators on B and d be a group of linear bounded invertible operators on B. If the operator A is d-homogeneous of degree µ then

  , and y 2 (t) := (d(s)•Φ(e µs t))u ∈ D(A), t ≥ 0. Being generated by A the semigroup Φ satisfy (see e.g. [8, page 5])

  page 134] that K t 0 ξ(s)ds = t 0 Kξ(s)ds for any bounded linear operator K : B → B and any Bochner integrable function ξ ∈ L 1 ((0, T ), B). Hence, using G(u) ∈ L 1 ((0, T ), B) we derive d(s) t 0 G(u(τ ))dτ = t 0 d(s)G(u(τ ))dτ = e -µs t 0 G(d(s)u(τ ))dτ = e -µs t 0 G(d(s)u(e µs τ ))dτ = e -µs t 0 G(u s (τ ))dτ, i.e. G(u s ) ∈ L 1 ((0, e -µs T ), B). Similarly, we derive d(s)u(e µs t) = (d(s) • Φ(e µs t))u(0) + e µs t 0 (d(s) • Φ(e µs t -τ ) • G)u(τ ) dτ = (Φ(t) • d(s))u(0) + e µs t 0 (d(s) • Φ(e µs t -τ ) • G)u(τ ) dτ = (Φ(t) • d(s))u(0) + e µs t 0 (d(s) • Φ(e µs (t -σ)) • G)u(e µs σ)) dσ = (Φ(t) • d(s))u(0) + e µs t 0

  are a (possibly) nonlinear operators. Definition 4 A pair (u, p) with u : [0, T ) → B and p : [0, T ) is said to be a mild solution of the implicit evolution equation (6) if u ∈ C([0, T ), B), G(u, p) ∈ L 1 ((0, T ), B) and

=

  e µs d(s) du(τ ) dτ a.e. = e µs d(s)(Au(τ )+G(u(τ ), p(τ ))

4

  Example: On necessary and sufficient conditions of global existence solutions of Navier-Stokes Equations in R n The Navier-Stokes equations, ∂ t u = ν∆u -(u • ∇)u -∇p, 0 = divu where u denotes the velocity of a fluid, p denotes the scalar pressure and ν > 0 denotes viscosity of the fluid, is the the classical model of the flow of an incompressible viscous fluid. Without loss of generality ([7, page 4])we can assume ν = 1. Below for shortness we omit R n in the notations of R n , L p , C ∞ c and C ∞ 0 spaces if the context is clear.

  and the domain D(F ) is invariant with respect to d(s), ∀s ∈ R. 1) According to the definition of Q, the identity Q(u, p) = 0 ∈ L 1 loc (in the weak sense) means u • ∇φ = 0, ∀φ ∈ C ∞ 0 . and using a change-of-variable theorem in Lebesque integral we derivee ns u 4 2 u(e s x) • (∇φ)(e s x) = 0, ∀φ ∈ C ∞ 0 .By Lemma 1 we have d 1 (s)u ∈ L 2 for any s ∈ R. Taking into account ∇(d 1 (s)φ)(x) = e 2s (∇φ)(e s x) we obtain

2 and d 2

 2 (s)p ∈ L 1 loc .Using the change-of-variable theorem in the Lebesgue integral we derive e ns u(e s x) •(u(e s x)•(∇φ)(e s x)) + p(e s x) (divφ)(e s x)+ f (e s x) • φ(e s x) dx = 0. or, equivalently,(d 1 (s)u)•(d 1 (s)u•∇)d 1 (s)φ+(d 2 (s)p) div(d 1 (s)φ)+e 2s (d 1 (s)f )•(d 1 (s)φ) = 0, for all φ ∈ C ∞ 0 . Since d 1 (s) maps C ∞ 0 onto C ∞ 0 then we conclude that d(s)D(G) ⊂ D(G) and the identity G(d 1 (s)u, d 2 (s)p) = e s d 1 (s)f = e 2s d 1 (s)G(d 1 (s)u, d 2 (s)p)holds for any s ∈ R and, at least, on D(G).

  [START_REF] Ozanski | Leray's fundamental work on the Navier-Stokes equations: a modern review of "Sur le mouvement d'un liquide visqueux emplissant l'espace[END_REF]) of Navier-Stokes equationsu(0) • φ(0) + T 0 u • (φ t + ∆φ) + p divφ = T 0 u • (u • ∇)φ, ∀φ ∈ C ∞ 0 (9)with u(t) ∈ V for t ∈ (0, T ).Definition 5 [7, Definition 3.7] A pair (u, p) is said to be a solution of the Navier-Stokes equations on [0,T ) if p ∈ L 1 loc ((0, T ) × R n , R)), u(t) ∈ V , t ∈ (0, T ) u ∈ C([0, T ), L 2 ) ∩ C((0, T ), L ∞ ),

-Smothness [ 7 ,

 7 Corollary 3.3]. If (u, p) is a strong solution of the Navier-Stokes equation then∂ k t ∇ m u, ∂ k t ∇ m p ∈ C((0, T ), L 2 ) ∩ C((0, T ), L ∞ ), ∀m, k ≥ 0and, in particular, u, p ∈ C ∞ (R 3 × (0, T )) constitute a classical solution of the Navier-Stokes equations on (0, T ) × R 3 .

A C 1 vector field ν : R n → R n is called Euler if it is complete and -ν is globally asymptotically stable.

Necessary and sufficient conditions for global existence of solutions in R n

Corollary 1 Let q 1 , q 2 ∈ [1, ∞] and r 1 , r 2 , µ 1 , µ 2 ∈ R and

A mild (strong or classical) solution of the Navier-Stokes equations with arbitrary the initial data u(0) = u 0 ∈ V ∩ L q1 µ1 ∩ L q2 µ2 exists on [0, +∞) if and only if there exist ε > 0 such that for any

a mild (resp. strong or classical) solution (u, p) with the initial data u(0) = u 0 exists on [0, +∞).

Proof Let d 1 be defined as in the proof of Lemma 3. Assume that for any

< ε} there exists a global in time mild (strong or classical) solution with u(0) = u 0 and let us show that for any

≥ ε the Navier-Stokes equations also have a mild( resp. strong or classical) solution on [0, +∞).

In the proof of Lemma 3 we have shown that d 1 (s)u 0 ∈ V for any s ∈ R, by Lemma 1 and d 1 (s)u 0 ∈ L q1 µ1 and for d 1 (s)u 0 ∈ L q2 µ1 any s ∈ R. By Lemma 1 we also derive )+r2(1-µ2-n q 2

)) u 0 r1 q1,µ1 u 0 r2 q2,µ2 . Since by assumption r 1 (1 -µ 1 -n/q 1 ) + r 2 (1 -µ 2 -n/q 2 ) = 0 then for any

Hence, if a strong solution (u, p) with u(0) = d 1 (s 0 )u 0 exists on [0, +∞) then by Theorem 2 the pair (ũ, p) given by ũ(t, x) = e -s0 u(e -2s0 t, e -s0 x), p(t, x) = e -2s0 p(e -2s0 t, e -s0 x), t ∈ [0, +∞), x ∈ R n is also a strong solution of the Navier-Stokes equation. Since u(0) = d 1 (s 0 )u 0 means that u(0, x) = e s0 u 0 (e s0 x), x ∈ R n then ũ(0, x) = e -s0 u(0, e -s0 x) = u 0 (x), i.e. ũ(0) = u 0 ∈ V ∩ L q1 µ1 ∩ L q2 µ2 and the proof is complete.

To expand globally the regularity of the Navier-Stokes equation by means of dilation symmetry, the condition (9) must hold.

None of conditions [START_REF] Polyakov | On homogeneous finite-time control for linear evolution equation in hilbert space[END_REF], [START_REF] Polyakov | On homogeneous distributed parameters equations[END_REF], [START_REF] Rosier | Etude de quelques problèmes de stabilization[END_REF] satisfy Corollary 1.

For instance, for n = 3 the conditions like [START_REF] Polyakov | On homogeneous finite-time control for linear evolution equation in hilbert space[END_REF], [START_REF] Polyakov | On homogeneous distributed parameters equations[END_REF], [START_REF] Rosier | Etude de quelques problèmes de stabilization[END_REF] would be appropriate for application of Corollary 1.


Carine Grasset-Simon

Guillaume Damiand
email: damiand@sic.univ-poitiers.fr

Pascal Lienhardt
email: lienhardt@sic.univ-poitiers.fr

nD generalized map pyramids: definition, representations and basic operations

Keywords: irregular pyramid, hierarchical data structure, pyramid of generalized maps, multi-level segmented image

come

Introduction

Hierarchical structures, as graph pyramids, are often used for representing image partitions at different resolution levels. Such pyramids have been widely used to encode partitions within segmentation and connected component analysis frameworks [START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF][START_REF] Jolion | The adaptive pyramid : a framework for 2d image analysis[END_REF][START_REF] Kropatsch | Finding the structure of connected components using dual irregular pyramids[END_REF]. We define pyramids of n-dimensional generalized maps (or n-G-maps) for two main reasons:

• first, to represent the topological information of images at different resolution levels; • second, to have a unique definition valid for any dimension. So 2D, 3D or 4D images (3D plus time for instance) can be processed using a single formalism, without loss of topological information.

Topological structures are often used for representing image partitions, i.e. regions and their adjacency relations. Information described by these structures can be used for computing topological characteristics about the regions (e.g. in order to retrieve all the neighbors of a given region, during a segmentation process by region growing).

Images at different resolution levels can be represented by hierarchical structures. The first level corresponds to the highest resolution (i.e. generally to the initial image), and other levels are obtained by successive simplifications (for instance, regions at level i which are homogeneous according to a given criterion are merged at level i + 1). Irregular pyramids are defined as stacks of reduced graphs (e.g. adjacency graphs, dual graphs), each one being built from the previous one by a sampling or a decimation process. Such structures make it possible to:

• directly access any level;

• at the same time use information contained within different levels;

• modify a region in a particular level without having to rebuild the whole level; • reduce the computational cost of several algorithms by applying them on reduced images; • get a good framework for algorithms based on a divide and conquer strategy.

For image processing, the most popular hierarchical structure is the adjacency graph pyramid [START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF][START_REF] Jolion | The adaptive pyramid : a framework for 2d image analysis[END_REF]. Each level is an adjacency graph, which describes regions of the image at a certain granularity level, and their adjacency relations (more precisely, a node of the graph corresponds to a region, and an edge links two nodes corresponding to adjacent regions). The problem here is the fact that all adjacency relations (simple or multi-adjacency, inclusion: cf. Fig. 1-b) are represented in the same way. Moreover, for nD images, adjacency graphs only represent n-cells (i.e. image regions) and (n -1)-cells (i.e. adjacency between regions): all other cells are not represented, and in the general case, they can not be computed from n and (n -1)-cells, leading thus to a loss of important topological information.

Dual graph pyramids [START_REF] Kropatsch | Finding the structure of connected components using dual irregular pyramids[END_REF][START_REF] Kropatsch | Building irregular pyramids by dual-graph contraction[END_REF] extend 2D adjacency graph pyramids. They have been defined in order to take into account multi-adjacency and inclusion relations (cf. Fig. 1-c). A dual graph is defined as a multi-graph along with its dual (these two graphs have to be connected). However, dual graphs as well as adjacency graphs cannot represent the whole topological information. For instance, in Fig. 2, we can see that dual graphs cannot represent the order of faces around a vertex, and such information can be useful for instance to distinguish between two objects represented in a 2D image.

Brun and Kropatsch have defined combinatorial pyramids, in order to catch the whole topological information for 2D images segmented at different levels [START_REF] Brun | Introduction to combinatorial pyramids[END_REF][START_REF] Brun | Combinatorial pyramids[END_REF][START_REF] Brun | Contraction kernels and combinatorial maps[END_REF]. Each level of a pyramid is a combinatorial map: it can be defined as a planar graph which implicitly encodes the orientation of edges around vertices. More generally, a combinatorial map can represent the topology of any partition of any orientable surface, without loss of topological information. Note that combinatorial pyramids are 2D hierarchical structures, and that they are built in a particular way: they use only 1-removal and 1-contraction operations, and these two type of operations cannot be applied at the same time.

So, existing hierarchical structures (adjacency graph pyramids, dual graph pyramids, combinatorial pyramids) can either lead to a loss of important topological information, or they are defined only for 2D images. We define n-G-map pyramids in order to solve these problems. Generalized maps represent the topology of any partition of any n-dimensional quasi-manifold with or without boundaries [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF]. So, they can represent any partition of any nD image without loss of topological information (all cells are represented, together with all adjacency and incidence relations between cells and topological order: cf. Fig. 1-e and Fig. 2-d). Moreover, generalized maps are homogeneously defined for any dimension: this is another advantage of this structure for which the definition of generic operations and algorithms is easier. The definition of n-G-map pyramids is based upon a general operation for removing and contracting cells of any dimension [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF]. More precisely, each level of a pyramid is a "reduction" of the previous one, computed by applying this operation. From this "principle" we deduce the definition of n-G-map pyramids, several useful notions and properties [START_REF] Grasset-Simon | Receptive fields for generalized map pyramids: the notion of generalized orbit[END_REF].

We are interested here in representing multi-level segmented images. So, we also propose basic algorithms for handling n-G-map pyramids which can be used for building pyramids corresponding to such images, given a segmentation criterion. Note that we do not propose a new segmentation method; our goals (and the results presented in the paper) are:

• the generic definition of n-G-map pyramids (indeed generalized map pyramids can be used in others domains, for example [START_REF] Fradin | Modélisation et simulation d'éclairage à base topologique: application aux environnements architecturaux complexes[END_REF] to model complex architectural environments, or [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF] to handle different representations in discrete geometry); • the conception of basic algorithms which can be used in a segmentation process for constructing a pyramid corresponding to an nD multi-level segmented image; • the definition of generic representations of such pyramids, and conversion algorithms between these representations.

Section 2 is a reminder of the notion of generalized map and the general operation of cell contraction and removal. Generalized map pyramids are defined in section 3. In this section, the definition is general and not devoted to image processing. We discuss in section 4 the construction of a pyramid for nD image, and we propose general algorithms for this construction. We study in section 5 three different representations of generalized map pyramids. We present in section 6 conversion algorithms between these representations. Conclusion and further issues are discussed in section 7.

2 Recalls: n-G-map, cell removal and contraction

A way to describe an image is to consider each cell of the corresponding subdivision. For instance in 3D, we represent voxels (3-cells) and also all cells of voxel boundaries [START_REF] Françon | Topologie de Khalimski et Kovalevski et algorithmique graphique[END_REF][START_REF] Khalimsky | Boundaries in digital planes[END_REF][START_REF] Kovalevsky | Finite topology as applied to image analysis[END_REF]: surfels (2-cells between two 3-cells), linels (1-cells between two 2-cells) and pointels (0-cells between two 1-cells). n-dimensional generalized maps (or n-G-maps) make it possible to describe this type of subdivision, and more generally any subdivision of any quasi-manifold [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]. An n-G-map is a set of abstract elements (called darts), together with applications defined on these darts.

Definition 1 (n-G-map) Let n ≥ 0. An n-dimensional generalized map G = (D, α 0 , . . . , α n ) is defined by:

(1) D a finite set of darts;

(2) ∀k, 0 ≤ k ≤ n, α k an involution1 on D;

(3) ∀k, j, 0 ≤ k < k + 2 ≤ j ≤ n, α k α j is an involution.

Let G be an n-G-map, and S be the corresponding subdivision. Intuitively, a dart of G corresponds to an (n + 1)-tuple of cells (c 0 , . . . , c n ), where c i is an i -dimensional cell that belongs to the boundary of c i+1 (cf. [START_REF] Brisson | Representing geometric structures in d dimensions: topology and order[END_REF] and Fig. 3). α i associates darts corresponding with (c 0 , . . . , c n ) and (c ′ 0 , . . . , c ′ n ), where c j = c ′ j for j = i, and c i = c ′ i (α i swaps the two i -cells that are incident to the same (i -1) and (i + 1)-cells).

Cells are implicitly described as sets of darts through the notion of orbit (see [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF] for more details). Definition 2 (orbit and i-cell) Let {Π 0 , . . . , Π n } be a set of permutations on D. The orbit of an element d ∈ D related to this set of permutations is < Π 0 , . . . , Π n > (d) = {Φ(d), Φ ∈< Π 0 , . . . , Π n >}, where < Π 0 , . . . , Π n > denotes the group of permutations generated by Π 0 , . . . , Π n . Let d ∈ D, N = {0, 1, . . . , n} and let i ∈ N. The i-cell incident to d is the orbit <> N -{i} (d) =< α 0 , . . . , α i-1 , α i+1 , . . . , α n > (d).

In order to define n-G-map pyramids, Damiand and Lienhardt have defined the operation of "simultaneous removals and contractions of cells of any dimension" [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF] which allows to contract and remove a set of cells of any dimension in a simultaneous way (see Fig. 4 for examples and [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF] for more details). With this operation we can merge different regions (using removals of 1-cells in 2D or 2-cells in 3D), or simplify region boundaries (using removals of 0-cells in 2D or 0-cells and 1-cells in 3D).

The formal and general definition of this operation is:

Definition 3 (Simultaneous removal and contraction of any cells) Let G = (D, α 0 , . . . , α n ) be an n-G-map, R 0 , . . . , R n-1 be sets of 0-cells,. . . , (n-1)cells to be removed and C 1 , . . . , C n be sets of 1-cells,. . . , n-cells to be con-

(v 1 , e 1 , f 1 ), dart 8 = 9α 0 corresponds to (v 2 , e 1 , f 1 ), 1 = 8α 1 corresponds to (v 2 , e 2 , f 1 ), and 2 = 1α 2 corresponds to (v 2 , e 2 , f 2 ). The vertex (0-cell) incident to dart 2 is < α 1 , α 2 > (2) = {1, 2, 3, 4, 5, 6, 7, 8}, the edge (1-cell) incident to dart 9 is < α 0 , α 2 > (9) = {7, 8, 9, 10}, and the face (2-cell) incident to dart 2 is < α 0 , α 1 > (2) = {2, 3,
tracted 2 . Let R = ∪ n-1 i=0 R i and C = ∪ n i=1 C i .
Two preconditions have to be satisfied:

(C1) cells are disjoint (i.e. ∀c, c ′ ∈ C ∪ R, c ∩ c ′ = ∅), (C2) "the degree of each cell is locally 3 two", i.e.: -∀i, 0 ≤ i ≤ n -2, ∀d ∈ R i , dα i+1 α i+2 = dα i+2 α i+1 ; -∀i, 2 ≤ i ≤ n, ∀d ∈ C i , dα i-1 α i-2 = dα i-2 α i-1 . ∀i ∈ N, let SD i = (R i ∪ C i )α i -(R i ∪ C i ) (it
is the set of surviving darts "neighbor" of removed and contracted cells). The resulting n-G-map is G ′ = (D ′ , α ′ 0 , . . . , α ′ n ) defined by4 :

• D ′ = D -(C ∪ R); • ∀i ∈ N, ∀d ∈ D ′ -SD i , dα ′ i = dα i ; • ∀i ∈ N, ∀d ∈ SD i , dα ′ i = d ′ = d(α i α k 1 ) . . . (α i α kp )α i , where p is the smallest integer such that d ′ ∈ SD i , and ∀j, 1 ≤ j < p, if d j = d(α i α k 1 ) . . . (α i α k j-1 )α i ∈ R i then k j = i + 1 else (d j ∈ C i ) k j = i -1.

Definition of n-G-map pyramids

An n-G-map pyramid is a hierarchical structure, each level of which is an n-G-map. The first level describes the initial data; the other levels describe successive reductions of the previous ones by removing and/or contracting some cells. In this work we focus on applications in image processing, but since n-G-map pyramids can be used in other domains (architectural environments [START_REF] Fradin | Modélisation et simulation d'éclairage à base topologique: application aux environnements architecturaux complexes[END_REF], discrete geometry [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF] . . . ), we give here a general definition of n-G-map pyramids.

Definition 4 (n-G-map pyramid) Let n, m ≥ 0. An (m+1)-level pyramid P of n-dimensional generalized maps is the set P = {G k } 0≤k≤m where:

(1) ∀k, 0 ≤ k ≤ m, G k =(D k , α k 0 , . . . , α k n ) is an n-G-map; (2) For each k, 0 ≤ k < m, for each i ∈ N, let R k i (resp. C k i ) be sets of i-cells and R k = n i=0 R k i (resp. C k = n i=0 C k i ) with R k n = C k 0 = ∅.
The two preconditions (C1) and (C2) of the definition 3 have to be satisfied;

(3) ∀k, 0 < k ≤ m, G k is obtained from G k-1 by removing the cells of R k-1
and contracting the cells of C k-1 .

In the case of an n-G-map pyramid associated with a multi-level segmented image, level 0 is associated with the initial image (or with a first segmentation). New levels are obtained by merging homogeneous regions (n-cells) then by simplifying region boundaries. Merging and simplification are achieved by removing different cells under some conditions (preconditions of the removal and contraction operation, see definition 3). The choice of removed or contracted cells is realized by an external process (an oracle which depends on the application). Examples of 2D and 3D pyramids are provided in Fig. 5 and Fig. 6. Two major properties of n-G-map pyramids are:

a b c
Proposition 5

(1) Each dart which belongs to a removed or a contracted cell of level k does not belong to another removed or contracted cell at any level. More formally: ∀i, j ∈ N, ∀k, l ∈ [0..m -1] we have:

     R k i ∩ C l j = ∅, R k i ∩ R l j = ∅, with i = j or k = l, C k i ∩ C l j = ∅, with i = j or k = l. (2) Let k, 0 ≤ k < m.
A one to one mapping ϕ k exists between the surviving darts of G k (i.e. the darts which are not removed nor contracted), and the darts of

G k+1 (ϕ k : D k -(R k ∪ C k ) -→ D k+1
). ϕ k is called the successor relation and (ϕ k-1 ) -1 the predecessor relation.

Remark 6

In order to simplify the notations, a dart of G k and its image in G k+1 are denoted by the same name. So,

D k+1 = D k -(R k ∪ C k ).
These properties can be easily deduced from the definition of simultaneous removals and contractions operation [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF], and from the definition of n-G-map pyramids. Moreover these properties are useful for the definition of different representations of n-G-map pyramids.

Construction of a pyramid for nD images

For image processing, pyramids are used in particular in order to keep in memory different segmentations of a same image. In order to build an n-G-map pyramid associated with a multi-level segmented image (called in the following segmentation pyramid ), level 0 is associated with the initial image or segmentation. New levels are built through two steps: first, the cells of the "previous segmentation" corresponding to homogeneous regions (n-cells) are "merged"; second, the resulting n-G-map is simplified. And each segmentation level is obtained by the same process.

In practice, it is not possible to describe the initial image by an n-G-map since it would take too much memory space 5 . We can represent the initial n-G-map implicitly by using a simple matrix. Another idea consists in starting directly with a first segmentation, the corresponding n-G-map being level 0 of the pyramid.

Algorithm 1 achieves the construction of such a pyramid. To build a new level it uses the add level function which takes three input parameters. The first one is the pyramid in which we add the level. The second one is the dimension of the cells to remove in order to build the new level. And the third one is an oracle that allows to know if a cell has to be removed or not.

Algorithm 1: build segmentation pyramid: builds the pyramid corresponding to different segmentation levels of an nD-image. Input: I: the initial nD-image, Output: P : the n-G-map pyramid corresponding to different segmentation levels of I. build level 0 ; while not terminate do add level(P , n -1, region feature) ; for i ← n -2 down to 0 do add level(P , i, local degree two i-cell) ;

In the first step, the merging of regions (n-cells) is achieved by the removal of (n -1)-cells between regions to merge. It is realized according to an homogeneity criterion.

In the second step, the simplification of the region's boundaries, without lead topological modifications 6 , is realized by merging the different cells which composed a same boundary. For example, in 3D, the different faces that composed a boundary are merged into a unique face. The merge of two i-cells (for 1 ≤ i ≤ n -1) is realized by removing the incident (i -1)-cell (which local degree is two). This simplification step concerns all the cells of the boundary and not only the cells of higher dimension. It is necessary to compute the different removals successively, starting by the highest degree cells. Indeed, the removal of an i-cell decreases the degree of the incident (i -1)-cells which could need to be removed. Other simplifications can be made in order to obtain a minimal representation (see [START_REF] Bertrand | Topological map: minimal encoding of 3d segmented images[END_REF]).

It is also possible to modify the choice of removed cells in order to control the topology, for instance in order to avoid disconnections. Note that disconnections occur only when we remove a degree one i-cell (i.e. incident twice to the same (i + 1)-cell). For example, a 2D disconnection comes from the removal of a degree one edge incident twice to the same face, and a 3D disconnection comes from the removal of a degree one face (resp. edge) incident twice to the same volume (resp. face). In order to avoid disconnections, it is enough to modify the oracles such that they return false when the i-cell degree is one.

Algorithm 2 constructs a pyramid level by applying three steps: marking of cells depending on the given oracle, duplication of the last level and removing the marked cells.

Algorithm 2: add level: builds a new pyramid level.

Input: P : an n-G-map pyramid (which levels are G 0 , . . . G m ), i: the dimension of the cells to remove, oracle: the function that knows if an i-cell need to be removed or not, Output: P in which a level is added at the top of the pyramid. mark i cells to remove(G m , i, oracle, m) ; duplicate last level(P ) ; cells removal(G m+1 ) ;

To build a segmentation pyramid, we use two different oracles. The first one indicates if an (n -1)-cell must be removed, that is to say if it separates two regions that have to be merged. Different criteria can be used according to the needs of the application. We do not provide more details about such criteria, since our goal is not the definition of a new segmentation algorithm.

The second oracle is used during the simplification step. Algorithm 3 indicates whether the local degree of a given cell is two or not, by checking for each dart the mathematical expression of a local degree two cell (see section 2).

The marking of removed cells is realized by algorithm 4. This algorithm checks each i-cell of the map by using the given oracle, and marks the cell to remove or not. In order to check each cell only once, a temporary mark is used. When an i-cell is met for the first time, all the darts of this cell are marked. Then, testing if an i-cell incident to a dart was already checked is simply achieved by checking this mark. So each dart is checked only once and this algorithm Algorithm 4: mark i cells to remove: marks i-cells that are going to be removed.

Input: G: an n-G-map, i: the dimension of the cells to remove, oracle: the function indicating if an i-cell needs to be removed or not, l: level of G in this map, Output: G with some i-cells marked.

foreach dart d of G do if not is in an i-cell yet examined(d) then if oracle(G, d, i, l) then foreach dart d ′ of the i-cell incident to d do mark by R i (d ′ , i);
mark examined the i-cell incident to d ;

The duplication of the last level is realized by algorithm 5. This algorithm duplicates each dart of the last level map, links the duplicated dart to the initial dart by the two relations successor and predecessor, and then links the duplicated dart with its neighbor for each involution, if it has been already created. This is achieved by using the same technique as for algorithm 4, with a temporary mark. So this algorithm has a cost O(pn), where p is the number of darts of the last pyramid level and n the dimension of the G-map.

The removals of the marked cells is realized by algorithm 6. The principle of this algorithm is first to link the darts that are not going to disappear for each involution, and second to delete the marked cells. The first step concerns more particularly the neighbor darts of removed cells. In order to know which is the new neighbor of such a dart for an involution, it follows the "path" of marked darts from the dart to its new neighbor by applying the same rules as for the removal operation. We know that these "paths" have no intersection (see [START_REF] Grasset-Simon | Receptive fields for generalized map pyramids: the notion of generalized orbit[END_REF] and [START_REF] Grasset-Simon | Pyramides de cartes généralisées, chemins de connection et orbites généralisées[END_REF]), so darts can be processed in any order without consequences for the final result. Note that algorithms presented here are basic ones and several optimizations can be made. We present here algorithms 7 and 8 which realize the optimized construction of a new pyramid level. The idea consists in only duplicating the darts that are not going to be removed. This is achieved by merging the steps of duplication and cell removals (algorithms 5 and 6). In this unique step, a dart is duplicated only if it is not going to disappear. Then it is linked to its neighbor for each involution, if it has been already duplicated, by using exactly the same rules as for the cells removal algorithm.

Algorithm 7: optimized add level: Optimized construction of a new level.

Input: P : an n-G-map pyramid (which levels are G 0 , . . . G m ), i: the dimension of the cells to remove, oracle: the function that knows if an i-cell need to be removed or not, Output: P in which a level is added at the top. mark i cells to remove(G m , i, oracle, m) ; create new level(P ) ; Algorithm 8 links each dart of the last pyramid level with its neighbor for each involution. This neighbor can be determined by following the "path" of disappeared darts by applying the same rules as for the removal operation. Two distinct "paths" have no intersection (see [START_REF] Grasset-Simon | Pyramides de cartes généralisées, chemins de connection et orbites généralisées[END_REF] for the proof). So, the number of darts processed by following all the "paths" for all the involutions for a given dart is at most k. Note that, in algorithm 8, each "path" linking two darts (d and d.α i ) is followed twice. The first time is when the first dart among d and d.α i is met. At this time, the link is not realized since the copy of the second dart is not yet created. When the second dart is met, the "path" is followed a second time and the link is realized. It is possible to follow each "path" only once by keeping in the second dart which is the copy of the first dart. So algorithms 7 and 8 have a cost O(p(n + k)), p being the number of darts of the last pyramid level, n the dimension of the space and k the number of darts which have disappeared during the construction. Note that the complexity of algorithm 8 corresponds to the addition of the complexities of algorithms 5 and 6. This is due to the fact that this algorithm merges the duplication and cells removal steps realized by these two algorithms. So this optimization does not change the complexity order, but provides a faster algorithm since the constant of the complexity is divided by two (we explore the set of darts only once), and we do not duplicate removed darts. if yet create copy(neighbor) then link by α i (d ′ , copy of(neighbor)) ;

Different representations of n-G-map pyramids

An n-G-map pyramid can be described more or less explicitly according to the expected space/time complexity. We present in this section three possible representations that are equivalent: explicit, hierarchical and implicit (see Fig. 7).

The first one follows immediately the definition, the two others are proposed in order to reduce the cost in memory space. These two last representations generalize similar existing structures proposed in [START_REF] Brun | Implicit encoding of combinatorial pyramids[END_REF][START_REF] Fradin | Modélisation et simulation d'éclairage à base topologique: application aux environnements architecturaux complexes[END_REF]. Note that depending on particular needs, it could be possible to propose other representations.

Description of the representations

Explicit n-G-map pyramid : All levels and one to one mappings between the levels are explicitly represented (see Fig. 7-a). The representation contains thus m + 1 n-G-maps, and each dart is linked with its predecessor (except the darts of level 0) and with its successor (except the darts of the last level and the darts which belong to a removed or contracted cell). Moreover, for each level, two marks are associated with each dart which belongs to a removed or contracted cell: the type of the operation (contraction or removal) and the dimension of the cell.

Hierarchical n-G-map pyramid : This representation contains a single set of darts, i.e. the darts of level 0 map (cf. remark 6). All involutions are explicitly represented for all levels. More precisely, for each dart a table gives the images of this dart by all involutions (see Fig. 7-b). Two marks are associated with When two darts linked by α i are drawn in the same level, their link α i is drawn in the usual way. Otherwise, the links α 1 0 and α 0 0 between two darts of two different levels are represented by lines with ♦ and the link α 0 1 by line with . (c) Implicit. A 2 (resp. a •) marks a dart of a 0-cell of level 0 (resp. a 1-cell of level 1) to be removed.

level 0 α 0 0 α 0 1 α 0 2 1 2 4 1 2 1 5 2 level 1 α 1 0 α 1 1 α 1 2 1 2 4 1 2 1 6 2 level 2 α 2 0 α 2 1 α 2 2 1 3 4 1 level 0 level 1 level 2 α 0 0 α 0 1 α 0 2 α 1 0 α 1 1 α 1 2 α 2 0 α 2 1 α 2 2 1 2 4 1 2 4 1 3 4 1 2 1 5 2 1 6 2 --- α 0 α 1 α 2 1 2 4 1 2 1 5 2 a b c
each dart which belongs to a removed or contracted cell in the same way than for the explicit representation. A possible optimization is the following one: for each dart we only represent distinct images for all involutions and the levels where images change. A structure based upon a similar principle has been proposed in order to model complex architectural environments [START_REF] Fradin | Modélisation et simulation d'éclairage à base topologique: application aux environnements architecturaux complexes[END_REF].

Implicit n-G-map pyramid : This representation contains the map of level 0 with additional information which make possible to compute the other levels. For that three marks are associated with each disappeared dart: the type of the operation (removal or contraction), the dimension of the removed or contracted incident cell, and the level at which the cell disappears. A similar representation is proposed by Brun and Kropatsch [START_REF] Brun | Implicit encoding of combinatorial pyramids[END_REF] for 2D combinatorial pyramids.

Comparison

These three representations are equivalent [START_REF] Grasset-Simon | nD generalized map pyramids: three equivalent representations[END_REF] (in particular, the constraints of the pyramid definition can be easily retrieved for each representation). We can prove it by showing that, for each representation, a dart has the same image for a given involution. Moreover we give in the following section three algorithms allowing to go from a representation to another (explicit → hierarchical → implicit → explicit).

These three representations have different space complexities. Let p be the number of darts of level 0, n be the dimension of the space and m be the number of pyramid levels. Since we have at most pm darts in the explicit representation, and since a dart contains the information concerning its neighbors for all n involutions, the space complexity of this representation is O(mnp). In the hierarchical representation, we have p darts and for each dart we have at most mn neighbors. Then, the space complexity of this representation is O(mnp). But note that if we consider the proposed optimization (for each dart we only represent the distinct images for each involution), most of the time, the average number of different neighbors for each involution and each dart will be smaller than m and depends of the considered pyramid. In the implicit representation, we have p darts and for each of them n involutions. So this representation has a cost O(np). This implies that the memory space of the explicit representation is bigger than the hierarchical one, which is itself bigger than the implicit one. This is due to the fact that the explicit representation is characterized by an important redundancy of information, since all darts and all involutions are present at each level. The information contained in the hierarchical representation is less redundant since the darts are not duplicated. Last, there is no redundant information in the implicit representation since only one level is explicitly represented.

Most operations (construction, features computation . . . ) are realized by exploring some orbits at a level of the pyramid (for example, the color of a region is retrieved by exploring the face orbits which have been merged into this region in order to use the pixel colors). An orbit is explored, dart by dart, with a breath first search algorithm which uses all the involutions of the orbit. Retrieve the neighbor of a dart for an involution is in constant time in the explicit and hierarchical representations since the information is explicitly described. But it is not the case in the implicit representation where it is necessary to compute it by following the "path" of disappeared darts. So the complexity of this computing depends on the number of darts of the "path". In consequence, most operations have a complexity proportional to the number of darts of the examined orbits for the explicit and hierarchical representations, while this complexity is multiplied by the average length of the "paths" for the implicit representation.

We can summarize the main characteristics of the three representations by giving here their main advantage and drawback and their main complexities in Tab. 1:

• explicit: it has, at each level, an n-G-map which can be considered independently. It allows to use swapping techniques in order to only keep in memory the necessary information for the current process. But it takes a lot of memory space; • hierarchical : it takes less memory space than the explicit representation while allowing to directly access any level by using involutions of this level. But the operations are not necessarily local since darts are shared by different levels; • implicit: it minimizes the required memory space, and some modifications are easier. For instance, removing or contracting a given cell is simple, since we do not have to propagate modifications. But a level cannot be directly accessed, it is necessary to compute it when it is required.

h h h h h h h h h h h h h h h h h

Complexity Representation Explicit Hierarchical Implicit

Memory space

O(mnp) O(mnp) O(np) Exploration of orbits O(k) O(k) O(kl) Table 1
Recapitulation of the complexities for each representation. p is the number of darts of level 0, n is the dimension of the space, m is the number of pyramid levels, k is the number of darts of the orbits and l is the average length of "paths" (l depends on the pyramid).

Conversion algorithms

We propose here three algorithms allowing to construct any representation given another one among the three ones presented before. These algorithms are local ones: the output representation (darts, links, and marks) is built by processing each input dart in two steps: first, one or several copies of the dart are created and second, all necessary information is added. These algorithms use different functions tackled in subsection 6.4.

Explicit to hierarchical representation

Algorithm 9 builds the hierarchical representation given the explicit one. The idea consists in "merging" each dart with all its successors. The principle of in the explicit and hierarchical representations. The neighbors of darts are not explicitly represented at each level in the implicit representation. This function follows the "path" of darts, disappeared between level 0 and lev, that separate dart d and its neighbor by using the removal and contraction rules (this is similar to the notion of connecting walk [START_REF] Grasset-Simon | Receptive fields for generalized map pyramids: the notion of generalized orbit[END_REF]). For a given dart, the complexity of this function depends on the length of the "path". This length is bounded by k, the number of disappeared darts in the pyramid. So it has a cost O(k).

Conclusion and Perspectives

Pyramids of n-dimensional generalized maps are here defined as stacks of reduced n-G-maps where each n-G-map is built from the previous level by contracting or removing cells. n-G-maps unambiguously represent the topology of subdivided n-dimensional objects (for instance nD images). So, n-G-map pyramids can be used in order to process 2D, 3D and 4D images with the same formalism.

n-G-map pyramids have several advantages compared with adjacency graph pyramids. Mainly, n-G-maps pyramids describe the topological information about n-dimensional multi-level subdivided objects. This is very important since the reduction between levels (achieved by the applications of removal and contraction operations) leads to particular cases (for instance multi-adjacency) which are usually not well handled by graphs. Moreover n-G-map pyramids can be very useful for applications in which it is necessary to check or to control the (evolution of the) topology of an object, for example for tracking objects in video sequences.

The main drawback of n-G-map pyramids is the fact that they can be very expensive in memory space since the space complexity of an nD image is intrinsically high. Different ways can be explored in order to solve this problem:

• optimized representations can be used for specific levels, depending on the applications (for instance for image processing, lower levels correspond to high resolutions; it is clear that representing the initial image by an n-Gmap is not efficient); • swapping techniques can be conceived in order to only keep in memory the information necessary for the current process; • optimized structures can be deduced for the specific needs of an application: indeed, since topological information is represented by n-G-map pyramids, we can control the loss of topological information acceptable for a given application.

We have shown how to use n-G-map pyramids in order to describe an nD multi-level segmented image. We have described all generic algorithms that allow to build such a pyramid given a segmentation criterion. We have also proposed an optimization which, even if it does not improve the complexity, provides a faster algorithm since the constant of the complexity is divided by two and we do not duplicate removed darts.

n-G-map pyramids can be represented in different ways. We have proposed here three generic representations: explicit, hierarchical and implicit as well as different conversion algorithms. We have presented advantages and drawbacks of these representations. This is particularly important in order to choose an efficient representation according to the needs of an application (complexity in memory space and/or in time). Now we are conceiving operations for handling this structure. A common problem is the propagation of modifications from a level to other ones. For instance, if we add a new cell within a given level, it is necessary to propagate this modification to the bottom of the pyramid. But if we remove or contract a cell, we have to propagate this modification to the top.

We intend to study the use of n-G-map pyramids for 3D and 4D image processing, leading to the study of more specific operations. Our goal is to develop a computer software based on n-G-map pyramids which groups many functionalities: multi-level image segmentation, modification of a given region at a particular level by an expert, extraction of topological and geometrical characteristics. . .

Figure 1 .

 1 Figure 1. Representation of a segmented image. (a) An image. (b) The corresponding region adjacency graph. (c) The corresponding dual graphs (primal graph in black and its dual in grey). (d) The corresponding 2-combinatorial map. (e) The corresponding 2-G-map.

Figure 2 .

 2 Figure 2. A 2D image of a clover. (a) The image. (b) The corresponding dual graphs. We cannot know which is the leaf between the two others. Dual graphs do not represent the topological order of edges around vertices in any case. (c) The corresponding 2-combinatorial map (d) The corresponding 2-G-map.

Figure 3 .

 3 Figure 3. (a) A 2D image. (b) The corresponding 2-G-map. Darts are represented by numbered black segments. Two darts related by α 0 share a little vertical segment (ex. darts14 and 15). Two darts related by α 1 share a same point (ex. darts 2 and 3). Two distinct darts related by α 2 are parallel and close to each other (ex. darts 3 and 4); otherwise, the dart is its own image by α 2 (ex. dart 14). Dart 9 corresponds to (v 1 , e 1 , f 1 ), dart 8 = 9α 0 corresponds to (v 2 , e 1 , f 1 ), 1 = 8α 1 corresponds to (v 2 , e 2 , f 1 ), and 2 = 1α 2 corresponds to (v 2 , e 2 , f 2 ). The vertex (0-cell) incident to dart 2 is < α 1 , α 2 > (2) = {1, 2, 3, 4, 5, 6, 7, 8}, the edge (1-cell) incident to dart 9 is < α 0 , α 2 > (9) = {7, 8, 9, 10}, and the face (2-cell) incident to dart 2 is < α 0 , α 1 > (2) = {2, 3, 11, 12, 13, 14, 15, 16}.

Figure 4 .

 4 Figure 4. An example of simultaneous removals of cells. (a) A 2-G-map corresponding to an image. A • marks a dart of a 1-cell to be removed in order to merge certain 2-cells. (b) The resulting 2-G-map. A 2 marks a dart of a 0-cell to be removed in order to simplify the boundary of regions. (c) The resulting 2-G-map where the region boundaries are simplified.

Figure 5 .

 5 Figure 5. A 2-G-map pyramid composed of three levels. A 2 (resp. a • ) marks a dart of a 0-cells (resp. 1-cells) to be removed.

Figure 6 .

 6 Figure 6. A 3-G-map pyramid composed of three levels. The second level is obtained by removing the 2 faces between the 3 volumes in the foreground (marked by ×). The third level is obtained by removing 6 edges around the volume in the foreground.

Algorithm 3 :

 3 local degree two i-cell: indicates whether the local degree of the i-cell is two or not. Input: G: an n-G-map, i: the dimension of the concerned cells, d: a dart, l: the pyramid level of G, Output: true iff the local degree of the i-cell containing d is two.foreach dart d 1 of <> N -{i} (d) do if d 1 .α i+1 .α i+2 = d 1 .α i+2 .α i+1 then return false ; return true ; has a cost 7 O(p) where p is the number of darts of G.

Figure 7 .

 7 Figure 7. Three representations of a same pyramid. For each representation, the corresponding array shows images by involutions α for the two darts 1 and 2. In explicit, each dart is duplicated. In hierarchical, darts are not duplicated, but involutions exist at each level. Implicit describes only the darts and the involutions of the first level. (a) Explicit. A 2 (resp. a •) marks a dart of a 0-cell (resp. a 1-cell) to be removed. (b) Hierarchical. Removed cells are marked in the same way as in the explicit representation. Each dart is drawn in the last pyramid level where it exists. When two darts linked by α i are drawn in the same level, their link α i is drawn in the usual way. Otherwise, the links α 1 0 and α 0 0 between two darts of two different levels are represented by lines with ♦ and the link α 0 1 by line with . (c) Implicit. A 2 (resp. a •) marks a dart of a 0-cell of level 0 (resp. a 1-cell of level 1) to be removed.

  Algorithm 5: duplicate last level: copies the last pyramid level. Input: P : an n-G-map pyramid (which levels are G 0 , . . . G m ), Output: P in which we have duplicated its last level. foreach dart d of G m do d ′ ← create copy(d, G m+1 ) ;

	link pred succ(d,d ′ ) ;
	for i ← 0 to n do
	if yet create copy(d.α m i ) then link by α i (d ′ ,copy of(d.α m i ))

  Algorithm 8: create new level: Optimized creation of a new level. Input: P : an n-G-map pyramid (which levels are G 0 , . . . G m ), i: the dimension of the cells to remove, Output: P in which a level is added at the top. foreach dart d of G m do if not is marked by R(d) then d ′ ← create copy(d,G m+1 ) ; link pred succ(d, d ′ ) ; for i ← 0 to n do neighbor ← d.α i ; while is marked by R i (neighbor) do neighbor ← neighbor.α i+1 .α i ;

  • the copy of gets the copy of a dart.It has a cost O(1); • link by α i links two darts by an involution. It has a cost O(1); • is marked by R (resp. is marked by C) indicates if a dart is removed (resp. or contracted). It has a cost O(1); • mark by R i (resp. mark by C i ) marks a disappearing dart by two (in the hierarchical and explicit representations) or three marks (in the implicit representation). It has a cost O(1); Other functions are more specific to a particular representation: • top most dart indicates the upper copy of a dart in the explicit representation. This function uses successor links until it reaches a dart with no successor. It has a cost O(m); • last level for dart returns the last level of the pyramid at which a dart exists. It has a cost O(1) in the implicit representation, since the information is contained in the dart. It has a cost O(m) in the explicit and hierarchical representations, since the information is not contained in the dart: it is necessary to use the successor-predecessor relations until a dart without successor is reached in the explicit representation, and it is necessary to examine each level in order to find the level at which the dart has no neighbor for an involution in the hierarchical representation; • link pred succ links two darts of two consecutive levels by the successor and predecessor relations in the explicit representation. It has a cost O(1); • d.α lev i gives the neighbor of dart d by α i at level lev. It has a cost O(1)

An involution f on a finite set S is a one to one mapping from S onto S such that f = f -1 .

R n = ∅ and C 0 = ∅ since it is not possible to remove n-cells nor to contract 0-cells

The degree of an i-cell is the number of distinct incident (i + 1)-cells. The local degree of an i-cell is its degree when we consider the cell locally. For example, the degree of a vertex incident to a loop is one but its local degree is two since locally two edges are incident to this vertex.

When only removals are used (i.e. C = ∅), the definition is simplified:for d ∈ SD i , dα ′ i = d ′ = d(α i α i+1 ) p α i ,where p is the smallest integer such that d ′ ∈ SD i .

For example, in 3D, describing a grey level image by a G-map is about 750 times bigger than encoding the image itself. Indeed, 2 bytes are necessary to directly encode a voxel, while 1500 bytes are approximatively necessary in the G-map (32 bytes for a dart, and 48 darts for each voxel).

For example, the Euler Characteristic for 2D-surfaces

Note that the complexities of these algorithms depend on the used representation (see section 5). They are expressed here only for the explicit representation.

algorithm 9 is the following: for each dart, create a copy of level 0, then copy the involutions at each level and finally report the different marks on the copy. The creation of the representation is achieved dart by dart and in three steps:

(1) The creation of the corresponding dart in the hierarchical representation;

(2) The linking of this corresponding dart to its neighbor for each involution (α i with i ∈ N) and each level if it already exists; (3) If the dart disappears at a level, we mark the dart with the same two marks as those contained in the initial dart in order to indicate how it disappears: removal (R) or contraction (C), and the dimension of the cell (i ∈ N). This algorithm links each dart of the first pyramid level with its neighbor for each involution at each level. In order to compute the last successor of a dart (the top most dart), we explore at most all the levels. So this algorithm has a cost O(pmn), p being the number of darts of the first pyramid level, n the dimension of the G-map and m the number of pyramid levels.

Hierarchical to implicit representation

Algorithm 10 builds the implicit representation given the hierarchical one. The principle of this algorithm is, for each dart:

(1) to create a copy;

18

(2) to copy the level 0 involutions, i.e. to link the copy of the dart to its neighbor for each involution (α i with i ∈ N) if it already exists; (3) then to put on the copy the information contained in the initial dart: the mark if the dart belongs to a removed or a contracted cell, the dimension of the cell, and the level at which the cell disappears (this last mark is not a copy, it is computed).

Algorithm 10: Construction of the implicit representation given the hierarchical one.

Input: Hierarchical representation (whose unique set of darts is D ′ ) Output: Implicit representation (whose unique level is G)

for i ← 0 to n do if yet create copy(dα 0 i ) then link by α i (d ′ , the copy of(dα 0 i )) ;

This algorithm links each dart of the implicit representation with its neighbor for each involution. The cost to compute the last level at which a dart exists is O(m). So this algorithm has a cost O(pmn).

Implicit to explicit representation

Algorithm 11 allows to build the explicit representation given the implicit one. The idea is to distribute the information through the different levels. The principle of algorithm 11 is, for each dart:

(1) to construct all darts of the different levels;

(2) to link them by the successor and predecessor relations;

(3) to link the copies with their neighbors for each involution;

(4) and then to put the information contained in the initial dart on the dart in the last level in which it exists.

This algorithm links each dart with its neighbor for each involution at each level. In order to compute the neighbor of a dart for a given involution, we follow the "path" of disappeared darts between a dart and its neighbor by applying the same rules as in the definition of removal and contraction operation (cf. notion of connecting walk defined iteratively [START_REF] Grasset-Simon | Pyramides de cartes généralisées, chemins de connection et orbites généralisées[END_REF]). This path is composed by at most k darts, k being the number of disappeared darts in the pyramid. So this algorithm has a cost O(pkmn). This is the worst case complexity. In fact, this algorithm has a cost O(pxmn) (with 1 ≤ x ≤ k ≤ p), with x being the average length of the "paths". But the average length depends on the construction of the pyramid and so it depends on the application.

So this third algorithm is a little more costly (O(pkmn)) than the two first ones (O(pmn)). Indeed, since the involutions are explicitly represented in the explicit and hierarchical representations, the neighbor of a given dart for a given involution is directly obtained, while the levels are not explicitly represented in the implicit representation and so the neighbor of a dart for a given involution must be computed.

The different functions used in the algorithms

There are some functions used by the conversion algorithms which are common to the three representations:

• create copy creates a copy of a dart. It has a cost O(1);

• yet create copy indicates if the copy of a dart has been yet created. It has a cost O(1);