Annalisa Massaccesi

Edouard Oudet

Bozhidar Velichkov

Numerical Calibration of Steiner trees

Keywords: Calibration, Minimal surface, Steiner tree problem. 2010 Mathematics Subject Classification: 49J45, 35R35, 49M05, 35J25

come

Introduction

In the present paper we consider variational problems related to one dimensional models arising in several fields among which graph theory, shape optimization, optimal transport and elastoplasticity. More specifically, we address the question to certify the optimality of a given one dimensionnal structure for some specific costs. Whereas the identification of an optimal structure may be an NP-hard problem like in the case of the optimal Steiner tree problem for instance, we introduce in this article a new algorithm based on the so called notion of calibration which, on cases under study, has been able to establish optimality from both a numerical and a theoretical point of view.

Our approach is rather flexible and applies to models with some common features: the objects under investigation can be represented by means of 1-dimensional rectifiable sets with suitable "labels" and the cost to be optimized, depending both on the support of the object and its labels, has a "subadditive" behavior. Among these problems, we can list k-means clustering, image processing, irrigation and the Steiner tree problem. Here below we discuss the statement of the problem in some of them, the original motivation for the paper being the latter. The reason for such a treatment of the aforementioned problems is the availability of well-established results and tools which are typical of Calculus of Variations and Geometric Measure Theory.

The celebrated Steiner tree problem can be summarized as follows: in the Euclidean space R d we are given n points {x 1 , . . . , x n } and we have to find the shortest connected set containing these points. More precisely, one would like to solve the following variational problem inf H 1 (Σ) : Σ ⊂ R d is a connected set and {x 1 , . . . , x n } ⊂ Σ .

(1.1)

From an exquisitely theoretical point of view, the Steiner tree problem is well understood : a solution always exists, though it may not be unique, in general. Moreover, the graph which minimizes the problem (1.1) is a union of segments, meeting either at the boundary points {x 1 , . . . , x n } or in the so-called "Steiner points". In R 2 , the segments meeting at a Steiner point are always three, forming angles of 2π/3 radiants, and Steiner points are at most n -2 (see, for instance, [START_REF] Gilbert | Steiner minimal trees[END_REF] and [START_REF] Ivanov | Minimal networks. The Steiner problem and its generalizations[END_REF]).

The situation may seem complete: indeed, in R 2 there are very efficient algorithms which allow to explicitly construct the solution of (1.1) (see for instance [8]). Nonetheless, the computability of the Steiner tree problem is a very difficult task. In fact, the problem is NP-complete, as one can see in [START_REF] Karp | Reducibility among combinatorial problems, Complexity of computer computations[END_REF].

We propose to attack the Steiner tree problem borrowing some tools from Geometric Measure Theory. More precisely, we show that the Steiner tree problem is equivalent to the classical massminimization problem with prescribed boundary (see Section 2.3 or [START_REF] Marchese | The Steiner tree problem revisited through rectifiable G-currents[END_REF], too), provided that the object of our study is 1-dimensional polyhedral chains (that is, finite collections of segments) with "weights" chosen in a suitable normed group G. The key-point is the meaning we assign to the concepts of mass and boundary for such a class of objects. In particular, the mass of a 1-dimensional polyhedral G-chain is the weighted length of its support. Our ideal reference is the classical variational problem of mass-minimization among currents with prescribed boundary, also known as Plateau problem. Nonetheless, these kind of problems are significantly simpler when the dimension of the current is 1: in particular, we can forget about currents and simply deal with polyhedral chains.

g 3 g 1 g 2 g 1 + g 3 -g 1 -g 2 -g 3 g 1 + g 2 + g 3 × g 3 × g 2 × g 1 + g 3 × g 1 Polyhedral G-chain
Moreover, it turns out that sometimes the mass-minimization problem has good computability properties in the (relatively) easy case of dimension 1. The reason is the calibration technique, that is, a sufficient (but, unfortunately, not necessary) condition for the minimality of a polyhedral chain. Indeed, the existence of a calibration associated with a certain polyhedral chain guarantees that the latter is a mass-minimizer for its boundary. Roughly speaking, having a "robust" candidate for the mass-minimization problem, one may try to explicitly build a calibration associated with this candidate: if we succeed, then the candidate is a genuine solution to the mass-minimization problem.

The constructions of the group and the equivalent objects are completely explicit, and the construction of a possible calibration is explicit, too. Thus we can pass to a numerical implementation of an algorithm which looks for calibrations of a candidate minimizer (in many cases, it is well-known that we are looking for calibration of true minimizers).

Back to a wider class of variational problem, from the point of view of applications this method is very flexible and its flexibility is based on the choice of the normed group G. The algebraic relations among the elements of the group, which are also the coefficients for the polyhedral chains, and the norm, which plays a crucial role in the computation of the mass of a polyhedral chain, can be chosen in such a way that the candidates in the mass-minimization problem have specific properties.

2 Steiner's candidates as polyhedral chains with coefficients in a group

2.1 Origin of difficulties: why coefficients in a group are needed?

It is easy to imagine how the Steiner tree problem can be rephrased as a mass-minimization problem for polyhedral chains, but it is less trivial to exhibit a group that preserves the two main features of the problem: connectedness of the set and the prescribed boundary datum at {x 1 , . . . , x n }. In fact, the first "natural" attempt G = Z gives problems even in the simplest cases, as one can see in the pictures below.

1 -1 -2 1 1 1 1 1 1 1 1 -1 1 1 1 1 -3 1 1 2 1
is not selected because of multiplicity 2 on the vertical segment.

The mass-minimizer is not even a connected set! attempt to set a boundary. Extra boundary point with multiplicity -3.

The "good" solution admissible! See (2.1) -"Symmetric" -but not With easy heuristic arguments, one can see that the group G should be chosen with the following properties (see Remark 2.14):

(1) ∃ g 1 , . . . , g n ∈ G (with g i = g j if i = j) such that g 1 + . . . + g n = 0 and g i 1 + . . .

+ g i k = 1 for every k ≤ n -1 and 1 ≤ i 1 < . . . < i k ≤ n; (2) ∀ g ∈ G \ {0} g ≥ 1.
In Section 2.3 we build a normed group with the properties above and we obtain an equivalence result between the Steiner tree problem and the variational problem given by the massminimization among polyhedral G-chains with a suitably chosen boundary.

Polyhedral chains with coefficients in a group

We will denote by d ∈ N the dimension of the ambient space R d where the Steiner tree problem is posed. In this section we consider the following general setting: let • be a norm in R m , for some m ∈ N, and G < R m an additive subgroup of R m that inherits the same norm • . In our construction we will set m = n, where n is the number of boundary points, and Definition 2.1. A 1-dimensional polyhedral G-chain T is a collection of oriented and Gweighted segments {σ i } Nσ i=1 in R d which intersect only at endpoints1 . More precisely, we will denote by T a triple (Σ, τ, θ) where

1. Σ = Nσ i=1 σ i ⊂ R d is the support of the chain T and σ i = x i y i ; 2. τ : Nσ i=1 σi → S d-1 is the orientation of T (thus τ (x) = (y i -x i )/|y i -x i | for every x ∈ σi );
3. θ : Σ → G is the multiplicity of T . For our convenience, we can assume θ to be constantly equal to θ i ∈ G on each segment σ i .

Definition 2.2. Given a 1-dimensional polyhedral G-chain T = (Σ, τ, θ), with Σ = Nσ i=1 σ i , we define the mass of T as

M(T ) := Nσ i=1 θ i Length(σ i ) . Definition 2.3. Given a 1-dimensional polyhedral G-chain T = (Σ, τ, θ) in R d , with Σ = Nσ i=1 σ i and σ i = x i y i ,
g i = 0 . (2.1) Indeed, if ({x i } n i=1 , g) is the boundary of a polyhedral G-chain T , then n i=1 g i = x∈B   - {i: x i =x} θ i + {j: y j =x} θ j   = Nσ i=1 (-θ i + θ i ) = 0 .
On the other hand, if (2.1) holds (that is, g n = -n-1 i=1 g i ) then we can build a polyhedral G-chain with Σ = n-1 i=1 x i x n and multiplicity θ i = -g i in every segment x i x n . Condition (2.1) will be called the admissibility condition. In this context, a quite natural variational problem arises: namely, given a pair ({x i } n i=1 , g) satisfying (2.1), find a mass-minimizing 1-dimensional G-chain with boundary ({x i } n i=1 , g). Given a bounded matrix-valued function M : R d → R m×d , we can define the action of a G-chain T on M as

T (M ) := Σ (M x τ (x)) • θ(x) dH 1 (x) , (2.2)
where • is the standard scalar product in R m . In this sense, T is a current with coefficients in G, i.e., a continuous, linear functional on the space of smooth R m -valued 1-forms. Moreover, as a current T has finite mass, rectifiable support and multiplicity in G, and its boundary ∂T have the same properties, too, thus T is a rectifiable current with coefficients in G. This is the (more abstract) approach followed in [START_REF] Marchese | The Steiner tree problem revisited through rectifiable G-currents[END_REF]. Let us briefly recall what is important for us of that approach:

Definition 2.5. Given a map M ∈ C 1 (R d ; R m×d ), we denote by M (j) ∈ C 1 (R d ; R d ) the j th row of the matrix M , for j = 1, . . . , m. M is said to be curl free if curl M (j) = 0 2 for every j = 1, . . . , m.
(M r -M l )t(x) = 0 ∀ x ∈ ∂C r ∩ ∂C l , (2.3)
where t ∈ R2 is the tangent vector to ∂C r .

Proposition 2.7. If S is a polyhedral G-chain without boundary and M : R d → R m×d is either

• curl free or

• piecewise constant and compatible in the sense of (2.3) for some partition {C r } r≥1 of R 2 , then S(M ) = 0.

Proof. Observe that this fact is nothing but a generalized version of Stokes' Theorem. We give here a short proof when d = 2 and M is curl free, for the complete proof of this fact (which requires to handle higher dimensional currents) we refer to [START_REF] Marchese | The Steiner tree problem revisited through rectifiable G-currents[END_REF].

Since ∂S = 0, we can decompose

3 S = (Σ, τ, θ) in a finite sum of 1-dimensional polyhedral G-cycles S k = (Σ k , τ k , θ k ) with constant multiplicity θ k = (θ (1) k , . . . , θ (m)
k ) ∈ G. Thus, using the definition in (2.2), we obtain

S(M ) = Σ M x τ (x) • θ(x) dH 1 (x) = Nc k=1 Σ k M x τ k (x) • θ k dH 1 (x) = Nc k=1 m j=1 θ (j) k Σ k M (j) τ k (x) dH 1 (x)
Nonetheless, each Σ k is a closed Lipschitz curve, so it is the (topological) boundary of a polygon P k . The Stokes' Theorem allows to conclude that

S(M ) = Nc k=1 m j=1 θ (j) k P k curl M (j) dL 2 = 0 .
Definition 2.8. A bounded, matrix-valued map ω : R d → R m×d is a calibration associated with a polyhedral G-chain T = (Σ, τ, θ) if the following conditions hold:

(i) either ω is curl free (i') or d = 2 and ω satisfies the compatibility condition (2.3) for some partition {C r } r≥1 ;

(ii) for H 1 -a.e. x ∈ Σ we have that

ω(x)τ (x) • θ(x) = θ(x) ; (2.4) (iii) finally sup x∈R d sup t∈S d-1 g∈G, g =1 ω(x)t • g ≤ 1 .
Definition 2.9. Given ε > 0, a bounded, matrix-valued map ω : R d → R m×d is an ε-quasi calibration associated with a polyhedral G-chain T = (Σ, τ, θ) if conditions (i) (or (i')) and (ii) in Definition 2.8 are fulfilled and (2.5)

(iii') sup x∈R d sup t∈S d-1 g∈G, g =1 ω(x)t • g ≤ 1 + ε .
Therefore

M(T ) = Nσ i=1 θ i Length(σ i ) (ii) = Σ ω(x)τ (x) • θ(x) dH 1 (x) = T (ω) (2.5) = T (ω) = Σ ω(x)τ (x) • θ (x) dH 1 (x) (iii) ≤ Nσ i=1 θ i Length(σ i ) = M(T ) .
Proposition 2.11. If ω is an ε-quasi calibration for some polyhedral G-chain T and some ε > 0, then

M(T ) -M(T 0 ) ≤ εM(T 0 ) ,
where T 0 is the mass-minimizing polyhedral G-chain with boundary ∂T .

Proof. As in the proof of Theorem 2.10:

M(T ) (ii) = T (ω) (i) = T 0 (ω) (iii ) ≤ (1 + ε)M(T 0 ) .
Remark 2.12. Theorem 2.10 gives a powerful sufficient condition for the mass-minimization: the existence of a calibration. Whether this condition is also necessary is a delicate issue. In fact, with purely functional analytical arguments, one can prove the following: given a massminimizing normal current N with coefficients in R m , there exists a generalized calibration Ω associated to N . A normal current N with coefficients in R m is a continuous, linear functional on the space of smooth R m -valued forms (see (2.2)) which can be represented as

N (M ) = M x τ (x) • m(x) dµ(x) ,
where τ is a vectorfield in R d , m ∈ L 1 (R d ; R m ) and µ is a Radon measure on R d . A generalized calibration for N is a continuous functional on the space of normal currents with the following properties:

(i) Ω(S) = 0 for every normal current S with coefficients in R m with ∂S = 0;

(ii) Ω(N ) = M(N );

(iii) Ω(N ) ≤ M(N ) for every normal current N with coefficients in R m .

This result has major drawbacks:

1. First of all, the construction of such a Ω is completely abstract (it relies on Hahn-Banch Theorem) and gives very little information on N (notice that Ω(N ) = M(N ) is far from being as significant as (2.4)).

2. The mass-minimization problem among normal currents is different from the mass-minimization problem among rectifiable currents with coefficients in G (or even polyhedral G-chains), the latter being a smaller class of the class of normal currents.

Calibration in Steiner's context

In Section 2 we have introduced a variational problem for 1-dimensional polyhedral G-chains: namely, the minimization of the mass among G-chains with a prescribed boundary. Moreover, a powerful sufficient condition for minimality has been introduced: the calibration (see Definition 2.8 and Theorem 2.10). These tools can be brought back to the framework of the Steiner tree problem, provided we have a result of equivalence between the Steiner tree problem and the mass-minimization problem for 1-dimensional polyhedral G-chains (see Theorem 2.15): roughly speaking, we describe a way to convert a candidate for the Steiner tree problem in a 1-dimensional polyhedral G-chain and viceversa. This construction depends on a suitable choice of the group G.

Definition 2.13. Fix n ∈ N \ {0} and consider the following seminorm in R n :

u := max i=1,...,n u i -min i=1,...,n u i ∀ u = (u 1 , . . . , u n ) ∈ R n . Now consider the map π : R n → R n-1 associating (u 1 , . . . , u n ) → (u 1 -u n , . . . , u n-1 -u n ). The seminorm • induces a norm • in R n-1 via π.
If {e 1 , . . . , e n } is a standard orthonormal basis of R n , we take g i := π(e i ) for i = 1, . . . , n-1 and we define the suitable group for a Steiner tree problem of n points as G = span(g 1 , . . . , g n-1 ) .

The group G is naturally endowed with the norm • .

Remark 2.14. By construction, the following properties hold:

(P1) for every k ≤ n -1 and 1 ≤ i 1 < . . . < i k ≤ n -1 we have that

g i 1 + . . . + g i k = 1 .
In particular, g i = 1 for every i = 1, . . . , n;

(P2) g ≥ 1 for every g ∈ G.

The basic construction for the equivalence theorem 2.15 describes how to pass from a connected set Σ ⊂ R d to a 1-dimensional polyhedral G-chain: we put it here for the convenience of the reader. In fact, it is very useful to know this construction for the numerical implementation of the problem. It is not restrictive to assume that Σ is a finite union of segments {σ i } Nσ i=1 and has no loops, its endpoints are exactly {x 1 , . . . , x n }. Then we define the 1-dimensional polyhedral G-chain T Σ = (Σ, τ, θ) associated with Σ in the following way: for every i = 1, . . . , n -1 take the (injective) path Π i in Σ connecting x i with x n and define the auxiliary G-chain P i := (Π i , τ i , g i ) with orientation τ i going from x i to x n and constant multiplicity g i . Now set T Σ := n=1 i=1 P i and notice that • the support of T is the original set Σ;

• the multiplicity of T Σ has always unit norm thanks to property (P1) in Remark 2.14. Theorem 2.15. Consider n points x 1 , . . . , x n ∈ R d and the normed group (G, • ) in Definition 2.13, which depends4 only on n. Set g n := -(g 1 +. . .+g n-1 ) and consider the admissible boundary (B, g) = {(x i , g i )} n i=1 . A connected set Σ ⊃ {x 1 , . . . , x n } solves the Steiner tree problem with datum {x 1 . . . , x n } if and only if the 1-dimensional G-chain T Σ described above solves the massminimization problem with boundary (B, g). This theorem is proved in [START_REF] Marchese | The Steiner tree problem revisited through rectifiable G-currents[END_REF], we provide here only the main ideas of the relevant implication, that is, if T Σ is a mass-minimizer then Σ solves the Steiner tree problem.

Proof. Consider a connected competitor Σ ⊂ R d : as before, it is not restrictive to assume that Σ is a finite union of segments, has no loops and its endpoints are exactly {x 1 , . . . , x n }. Therefore we can construct the associated polyhedral G-chain T Σ ; since the multiplicity has always unit norm, then H 1 (Σ ) = M(T Σ ). On the other hand, property (P2) from Remark 2.14 guarantees that M(T Σ ) ≥ H 1 (Σ). Finally, by construction ∂T Σ = ∂T Σ and since T Σ is a mass-minimizer among polyhedral G-chains with the same boundary we conclude that

H 1 (Σ ) = M(T Σ ) ≥ M(T Σ ) ≥ H 1 (Σ) .
Once we established this equivalence, we can try to solve the Steiner tree problem via calibrations. In fact, given a "candidate minimizer" Σ for a set a points {x 1 , . . . , x n } ⊂ R d and the corresponding 1-dimensional polyhedral G-chain T Σ , it is sufficient to check the existence of a calibration associated with T Σ . To this aim, it is useful to rephrase condition (iii) in Definition 2.8 as sup

x∈R d sup t∈S d-1 ω(x)t * ≤ 1 , (2.6)
where

• * is the dual norm in (R n-1 , • ).
Proposition 2.16. Given n ∈ N \ {0} and the norm • on R n-1 introduced in Definition 2.13, the dual norm • * on R n-1 is characterized by the formula

w * = w P ∨ w N ,
where w = (w 1 , . . . , w n-1 ) and w p := n-1 i=1 w i ∨ 0 and w

N := -n-1 i=1 w i ∧ 0.
The proof is very short and can be found in [START_REF] Marchese | The Steiner tree problem revisited through rectifiable G-currents[END_REF]. Nonetheless, we rewrite the proof here for the reader's ease. Proof. Given w ∈ R n-1 , we have to compute sup v =1 w • v. If w P > w N , then the supremum is reached for v = n-1 i=1 (w i ∨ 0)/w i g i , which implies w • v = w P . If w N > w P instead, the supremum is reached for v = n-1 i=1 (w i ∧ 0)/w i g i , which implies w • v = w N .

Discrete parametrization of calibrations

Consider T = (Σ, τ, θ) a polyhedral one dimensional G-chain where G is the normed group defined in Definition 2.13. In this section, we are interested in the numerical investigation of the optimality of the Steiner tree defined by the support of T . To this purpose, we consider a polygonal partition P associated to the support of the polyhedral chain T . More precisely, we require that the weighted segments {σ i } Nσ i=1 are all covered by the edges of P. Notice that this assumption is not mandatory but it could help to describe discontinuous matrix fields. Consider now the matrix fields ω which are piecewise constant on the N C polygons {C r } 1≤r≤N C of P. If we are able to identify a matrix field ω which satisfies the divergence constraints (i') and the additional conditions (ii) and (iii) of Definition 2.8, Theorem 2.10 ensures that T is globally optimal. Since we can not expect to satisfy exactly this set of constraints from a numerical point of view, we relax this constraint satisfaction problem in a convex non smooth optimization problem which consists in minimizing the real ε with respect to couples (ε, (ω r ) 1≤r≤N C ) which satisfy

(i) ω r ∈ R m×2 , ∀ 1 ≤ r ≤ N C , (i') (ω r -ω l ).τ r,l = 0 ∀ x ∈ ∂C r ∩ ∂C l ,
where τ r,l is a tangent vector of the common edges of C r and C l ,

(ii) ω r(k) τ k • θ k = θ k , ∀ 1 ≤ k ≤ N σ and all C r(k) cells such that C r(k) ∩ σ k is not empty, (iii) sup 1≤r≤N C sup t∈S 1 ||ω r t|| * ≤ 1 + ε.
In this setting, the closeness of 0 of parameter ε can be interpreted as a qualitative indicator of the optimality of the support of T for our original Steiner tree problem. This interpretation is supported by our stability Proposition 2.11. Notice that we do not claim that every Steiner tree admits a calibration. Nevertheless, Theorems 2.10 and 2.11 assert that, if we are able to exhibit numerically a ε-calibration with ε small enough, then T is close to be optimal in term of its cost value. We observe that conditions (i') and (ii) represent a finite set of linear equality constraints with respect to the unknown discrete matrix field (ω r ) 1≤r≤N C . On the other hand, condition (iii) cannot easily be taken into account numerically due to the mixing of l 1 and l 2 types norms. In order to tackle that difficulty, we define a new set of linear constraints which ensures that condition (iii) is satisfied: let (t i ) 1≤i≤Nt be the vertices of a convex regular exterior tangent polygon to S 1 which contains the unit disk. We look for a field (ω r ) 1≤r≤N C which satisfies the linear equality constraints

sup 1≤r≤N C sup t 1 ,...,t N t ||ω r t i || * ≤ 1 + ε. (3.1)
for ε as small as possible. By convexity of the norm || • || * , it is clear that condition (3.1) implies condition (iii), which makes (ε, (ω r ) 1≤r≤N C ) be an admissible discrete ε-calibration.

A non smooth convex programming framework

From the previous section, we deduce that the identification of an exact discrete calibration reduces to solve a large scale finite dimensional convex minimization problem of type

F (K((ω r ) 1≤r≤N C )) + H((ω r ) 1≤r≤N C ) (4.1)
where F is the convex characteristic function of the set of equality constraints (i') and (ii), the linear operator K : (R n×2 ) N C → (R n ) N C ×Nt is induced by the product with vectors (t i ) 1≤i≤Nt and H is the vectorial convex characteristic function of the product of ball of radius 1 for the norm || • || * , that is, B(|| • || * , 1) N C ×Nt . H corresponds to the strongest constraint (3.1). As it has been mentioned, there is no proof of the fact that every optimal Steiner tree has an associated discrete calibration. As a consequence, the previous optimization problem may be ill posed, in the sense that it does not exist a matrix field in the intersection of the convex sets defined by (i'), (ii) and (3.1). In order to consider a well posed constraint satisfaction problem we relax problem (4.1) in considering the minimization problem

L((ω 1 r ) 1≤r≤N C ), (ω 2 r ) 1≤r≤N C )) = F (K((ω 1 r ) 1≤r≤N C )) + H((ω 2 r ) 1≤r≤N C ) + ||(ω 1 r -ω 2 r ) 1≤r≤N C || 2 . (4.2) Defining the vectorial variable Ω = ((ω 1 r ) 1≤r≤N C , (ω 2 r ) 1≤r≤N C
) and the projection operators π 1 and π 2 on the first and second matrix fields, problem (4.2) can be seen as a minimization problem of type

F ( K((Ω))) + H(Ω) (4.3) where K = K • π 1 , H(Ω) = H(π 2 (Ω)) + ||π 1 (Ω) -π 2 (Ω)|| 2 .
We recall in the next section an efficient algorithm adapted to the minimization of previous non smooth convex functions.

Proximal algorithms

Several algorithms have been developed in the last decades to solve non smooth convex satisfaction problems of type (4.3). A standard approach is to use the so called ADMM algorithm Algorithm 1 Alternating-direction method of multipliers (ADMM)

Input σ, τ, θ > 0

Initialization Ω 0 ∈ ((R n×2 ) N C ) 2 , Y 0 ∈ ((R n ) N C ×Nt ) 2 , Ω t = Ω 0 For n = 0, 1, . . . Y n+1 = prox σ F * (Y n + σ K(Ω t )) Ω n+1 = prox τ H(Ω n -τ K * (Y n+1 )) Ω t = Ω n + θ(Ω n+1 -Ω n )
(Alternating-direction method of multipliers). The version of the algorithm that we describe below (see [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] for a convergence study) is able to handle functions that are easily proximable (see Definition 4.1) and do not require to solve a system involving K * K, which is a crucial issue in our large scale setting. To describe ADMM algorithm more in details, we recall the definition of proximal operator:

Definition 4.1. The proximal operator associated to a convex function M : R m → R is defined by:

prox γ M (y) = arg min x∈R m M (x) + 1 γ ||x -y|| 2 . (4.4)
In our case, F is the indicator function of a convex set, and prox γ F coincides with the projection operator on this set. Analogously, the proximal operator of function H is very closely related to the projection operator on the affine subspace defined by conditions (i') and (ii) (see Section 4.2). We give a complete description of ADMM approach applied to our context in 1, where we used the notation F * to denote the Legendre transform of F . Notice that Moreau's identity makes it possible to deduce prox γ F * from prox γ F for every τ, x by a simple may we recall it? may we recall it? computation, since:

x = prox τ M * (x) + τ prox 1 τ M (x/τ )
In all our experiments we used the parameters σ = 10, τ = 0.9 σn K and θ = 1, where n K stands for a numerical evaluation of the operator norm of K * K.

The proximal operator of H

For completeness, we recall a very standard approach to project on an affine subspace which corresponds to the constraints induced by equalities (i') and (ii). In this context, we need to solve a projection problem of the type min

(x,y), Ax=b ||x -x 0 || 2 + ||y -y 0 || 2 + ||x -y|| 2 (4.5)
where x 0 ∈ R p , A ∈ R q×p and b ∈ R q are the data of the problem. The first order optimality condition with respect to y gives

y = x + y 0 2 (4.6)
while the first optimality condition with respect to x ensures that 2(2x -x 0 -y) + A * λ = 0 (4.7)

for some unknown Lagrange multiplier λ ∈ R q . Multiplying this last equality and using the fact that Ax = b, we observe that the identification of λ is equivalent to solve the linear system

AA * λ = 3b -A(2x 0 + y 0 ).
In our case it is straightforward to establish that the matrix AA * is non singular, by providing an algorithm to compute λ and then x by equality (4.7). Thus, projecting on an affine subspace is equivalent to solve a linear equation. Since the linear system does not change during iterations, we used a prefactorization approach to speed up the resolution of these linear systems.

Projection on the unit ball of E *

In this short section we describe the projection operator with respect to the l 2 norm onto the unite ball of E * . Let v ∈ R n-1 . We want to find w ∈ R n-1 which minimizes ||v -w|| 2 2 and satisfies ||w|| * ≤ 1 where || • || * is described in Proposition 2.16. Up to a permutation of the coordinates, we can assume that v = (v + , v -) where v + and -v -are vectors with non-negative coefficients. Notice that v + v -do not have necessarily the same number of elements. In this setting, it is straightforward to check that the components of the optimal vector w have the same sign as the ones of v, because removing a non zero component of w preserves the vector in the unit ball of E * . Thus, we have to solve the minimization problem min

w + ≤1, -w -≤1, w + ≥0, -w -≥0 ||v + -w + || 2 + ||v --w -|| 2 .
Since the latter problem is separable with respect to the positive and negative parts, we conclude that the projection w is simply equal to ( w+ , w-) where w+ and w-are respectively the projections on the unit ball of vectors w + and w -.

Numerical results

We present below some results obtained by our approximation strategy for geometrical configurations drawn in Figure 7. Motivated by the theoretical results obtained in [START_REF] Marchese | The Steiner tree problem revisited through rectifiable G-currents[END_REF], we drew a special attention in identifying calibrations which are piecewise constant on large subsets of our fixed mesh. Considering the well known fact that a calibration for a given tree is also a calibration for every other globally optimal tree, we enforce not only the mesh to cover the edges of the tree but also to cover every edges obtained by "symmetric" trees which are also known to be globally optimal. By imposing these constraints to the mesh, we hope to minimize dramatically the number of triangles needed to approximate precisely piecewise constant calibrations in symmetric configurations. As it can be observed in Figures 3 and4, we were able to recover the theoretical piecewise constant matrix field which had been introduced in [START_REF] Marchese | The Steiner tree problem revisited through rectifiable G-currents[END_REF] to prove the optimality of Steiner trees associated to the vertices of an equilateral triangle and the vertices of a square. Observe that in the latter case we recover the symmetries imposed by both global optimal solutions. As mentioned previously, by imposing that edges of the mesh cover exactly all optimal trees, we reduce the number of parameters to describe piecewise constant calibrations.

In Figures 5 and6 we illustrate the behavior with respect to non optimal trees. The optimal values obtained after the same number of iterations were of order 10 -2 which is significantly different from best values obtained by optimal trees.

When the set of data points has many symmetries, we may suspect that it is more likely that a calibration does not exist since a calibration has to be optimal for every globally optimal tree. It has been suspected by many authors that the vertices of a regular pentagon or of a regular hexagon may be one of the simplest situation where non existence occurs. Surprisingly, our experiments do not confirm this intuition. Actually in all our experiments, the minimal value of our cost function 4.2 was less than 10 -5 after 10 6 iterations which may suggest that in all these cases a calibration exists. We represent the coefficients of the optimal matrix fields obtained by our algorithm: see the figure 4 and the figures of the appendix.

One unexpected fact is the existence of apparently non piecewise constant calibration for the case of the of the pentagon and of the hexagon (see Figures 3 and4). 5: Representation of an optimal matrix field which does not calibrate the non optimal tree on the right (optimal value >> 1) Figure 6: Representation of an optimal matrix field which does not calibrate the non optimal tree on the right (optimal value >> 1) ware required to generate constraint meshes. Édouard Oudet gratefully acknowledges the support of the ANR, through the projects COMEDIC, GEOMETRYA, PGMO and OPTIFORM.

T+Figure 1 :

 1 Figure 1: A polyhedral chain with its boundary and mass

Figure 2 :

 2 Figure 2: The mass-minimization problem with G = Z

  we define the boundary of T as the pair (B, g) =: ∂T , where 1. B = Nσ i=1 {x i , y i } ⊂ R d is the unsuitable support of the boundary of T ; 2. g : B → G is the multiplicity of the boundary of T and maps x → g(x) := -{i: x i =x} θ i + {j: y j =x} θ j ; 3. B = {x ∈ B : g(x) = 0} is the support of the boundary of T . Remark 2.4. Given a finite number of points {x 1 , . . . , x n } ⊂ R d with a multiplicity g : {x 1 , . . . , x n } → G, the pair ({x i } n i=1 , g) is the boundary of some polyhedral G-chain T if and only if n i=1

Definition 2 . 6 .

 26 Assume d = 2 and consider a locally finite partition {C r } r≥1 of R 2 , where the cells C r are pairwise disjoint, connected open sets with Lipschitz boundary. Given a piecewise constant map M : R 2 → R m×2 associated with {C r } r≥1 (i.e., M |Cr ≡ M r ∈ R m×2 ), we say that M fulfills the compatibility condition if

Theorem 2 .

 2 10. Consider a 1-dimensional polyhedral G-chain T = (Σ, τ, θ) with boundary ∂T . If there exists a calibration ω associated with T in the sense of Definition 2.8, then T minimizes the mass among 1-dimensional polyhedral G-chain with boundary ∂T . Proof. Consider a polyhedral G-chain T = (Σ , τ , θ ) with ∂T = ∂T as a competitor. Then the sum S := T -T has no boundary and we can apply Proposition 2.7, obtaining T (ω) = T (ω) .

Figure 3 :Figure 4 :

 34 Figure 3: Representation of an optimal calibration associated to three equilateral points

Figure

  Figure 5: Representation of an optimal matrix field which does not calibrate the non optimal tree on the right (optimal value >> 1)

Figure 9 :

 9 Figure 9: Representation of an optimal calibration associated to the six vertices of an Hexagon (see the second mesh of figure 7)

The endpoints of each segment σi will be denoted by xi and yi ∈ R d (with orientation from xi to yi).

When d >

3, the curl above stands for the exterior derivative of the 1-form associated with M (j) .

The existence of such a decomposition is known for 1-dimensional currents (see[START_REF] Federer | Geometric measure theory[END_REF]) and consequently for 1-dimensional polyhedral G-chains (see[START_REF] Marchese | The Steiner tree problem revisited through rectifiable G-currents[END_REF]). Heuristically, for a finite number of segments (as in the case of polyhedral G-chains), one may explicitly perform the decomposition following the path of a fixed coefficient. This path has to close up to prevent the formation of boundary.

Notice that the group G is independent from the position of the points x1, . . . , xn ∈ R d .

Acknowledgements

We would like to thank the MmgTools team (see https://github.com/MmgTools/mmg): Charles Dapogny, Cécile Dobrzynski, Pascal Frey and Algiane Froehly) for providing the remeshing soft-

Appendices


Seifeddine Bouallegue

B R Kaouthar

Sethom

Guy Pujolle

Energy Saving by Handoff Classification in Femtocells Network

Keywords:

A femtocell is a radio equipment hich aims to improve the quality of the telecommunications network in customers' homes and / or in places that do not support the coverage of macro network. We focused our work on the issue of saving the energy consumed by femto-cells. In this paper, we introduce an energy efficient solution, to the cited issue, based on the removal of unwanted mobility events by classifying them according to their probabilistic importance in the context of BWA (Broadband Wireless Access) networks. We derived the analytical model of the solution. The first simulation results seem to confirm the advantage of our solution in reducing energy consumption.

INTRODUCTION

Before the mass commercial deployment of femtocells, operators need to ensure that new femtocell deployments should meet regulatory requirements [START_REF]Load Balancing with Reduced Unnecessary Handoff in Hierarchical Macro/Femto-cell WiMAX Networks[END_REF] and enable smooth integration with the macro networks. However, there are still some problems in the process of carrying out this new technology. Because, femtocells are deployed randomly by users, these plug-and-play residential base station will be on or off self-willed and are possible to move anywhere at any moment. Such issue will lead to an unknowable change of the network topology. Therefore the handover scheme between femtocells and macrocells is very crucial [START_REF] Zhou | A Network-based global mobility management architecture[END_REF][START_REF]Prioritised predicted region based cache replacement policy for location dependent data in mobile environment[END_REF]. In order to improve user's QoS and maintain a low outage rate, lower handover rate is absolutely necessary. This will enhance the throughputs of femtocells and macrocells [START_REF] Oh | A seamless handover scheme in IPv6-based mobile networks[END_REF][START_REF]Novel handoff decision algorithm in hierarchical Macro/Femto-cell networks[END_REF].

POWER SAVING ALGORITHM

A WiMAX macro cell of 1.2 km radius is considered along with multiple femto cells deployed randomly at a distance of at least 'R' meter from the macro BS (figure 1). During operation, information on the number of mobility events and their time are collected and used for further refinement of the coverage by self-optimization of the pilot power of the femtocell. We here propose an optimization method that takes decision based on unwanted mobility events from transient users into account that briefly hand over to the femtocell and hand back immediately after passing.

We hereafter give a brief overview of the proposed algorithm and system model: 1. No femtocell is considered within 'R' meter of radius of the macro base station (BS) because the RSS of mobile within this area is assumed to be quite high. A number of mobile users are deployed randomly under the coverage of the macro BS with varied velocity and undergoing calls of varied service type.

Fig. 1: Femtocell deployment 2. Initially, the femtocells are considered to be in the idle mode with all the pilot transmissions and associated radio processing at lower power sniffer (Eidle). The femtocell become active only when any end user is active under its coverage. This idle/active status aims to enhancing the energy consumption.

Case I: When the mobile user is moving at a very high velocity, no handoff from the macro to the femto is executed. The mobile remains attached to the Macrocell. As a user with very high velocity it undergoes huge number of macro/femto handoff within a very short period of time. The overhead of the macro BS thus increases unnecessarily. Hence, in this paper we have considered a velocity threshold 'Vth' of 30 Kmph (non motor vehicular speed).

Case II: If the mobile user is undergoing a real-time traffic, the number of handoff encountered degrades the call quality proportionately. Hence, in our scenario, no handoff between the macrocell and the femto is triggered for them in order to maintain the call quality. The mobile remains attached to the Macrocell.

Case III: If V< Vth and no real-time traffic, a power saving is performed:

The objective is to eliminate unwanted mobility events from transient users that briefly hand over to the femtocell and hand back immediately after passing the house. If the number of unwanted mobility events of passing users exceeds a pre-defined value of n1 events per time t1 the femto reduces its pilot power to E1. The femtocell then starts a new mobility event count for the updated configuration. If the number of unwanted events is smaller or equal to a pre-defined acceptable value of n2 events for a time t2, the femtocell increases its pilot power to E2, to provide improved indoor coverage.

PERFORMANCES EVALUATION

The energy consumed by l handoffs during the time period T can be expressed as:

(1) )ܶ(ܧ = ܧ ଶ × ܲ ௩ (݈ < ݊2) + ܧ ଵ × ܲ ௩ (݈ > ݊1) + ܧ ்ூா × ܲ ௩ (݊1 < ݈ < ݊2) + ܧ ୢ ܲ ୢ (2) ܲ ୢ = 1 -(ܲ ௩ (݈ < ݊2) + ܲ ௩ (݈ > ݊1) +ܲ ௩ (݊1 < ݈ < ݊2))
The probability of s new users in a time period of length T is modeled in this article by a Poisson process:

,ݏ(ܲ λܶ) = ܲ ௦ = (λT) ௦ . ݁ ି !ݏ
(3) where λ denotes the intensity of such process.

Assuming that the users' holding time is exponentially distributed, the probability of exactly one user leaving a femtocell in a time period of length T is:

(4) ܲ ௩ = 1 -e-µT where µ denotes the users' mean holding time. Therefore, the probability of exactly l users leaving a specific femtocell, which has exactly Z connected users, in a time period of length T can be described as follows:

(5)

ܲ ௩ (݈) = (ܲ ௩ ) . (1 -ܲ ௩ ) ି . ൬ ܼ ݈ ൰
Some initial simulations were conducted through Matlab. Main results are shown in the following figures [START_REF] Zhou | A Network-based global mobility management architecture[END_REF][START_REF]Prioritised predicted region based cache replacement policy for location dependent data in mobile environment[END_REF]. They show the adaptative behavior in femtocell power consumption. Figure 3 demonstrates a considerable energy saving through our proposal compare to classical approach [START_REF] Zhou | A Network-based global mobility management architecture[END_REF] that doesn't make power adaptation in active state.

Fig. 2 :Fig. 3 :

 23 Fig. 2: Energy consumption in the proposed solution


Jacques M Bahi
email: jacques.bahi@femto-st.fr

Nicolas Friot
email: nicolas.friot@femto-st.fr

Christophe Guyeux
email: christophe.guyeux@femto-st.fr

Topological study and Lyapunov exponent of a secure steganographic scheme

Keywords: Information Hiding, Steganography, Security, Topology, Lyapunov Exponent

come

INTRODUCTION

The first fundamental work in information hiding security was realized by Cachin in the early '00s, in the context of steganography [START_REF] Cachin | An information-theoretic model for steganography[END_REF]: attempts of an attacker to make the distinction between an innocent image and a stego-content was rewritten in this article as a hypothesis testing problem. The basic properties of a stegosystem are defined by Cachin using the notions of entropy, mutual information, and relative entropy. At the same time, Mittelholzer has proposed the first theoretical framework for analyzing the security in the second category of algorithms studied by the information hiding community, namely the digital watermarking [START_REF] Mittelholzer | An information-theoretic approach to steganography and watermarking[END_REF]. These efforts to bring a theoretical framework for security in steganography and watermarking have been followed up by Kalker, who tries to clarify the concepts (robustness vs. security), and the classifications of watermarking attacks [START_REF] Kalker | Considerations on watermarking security[END_REF]. This work has been deepened by Furon et al., who have translated Kerckhoffs' principle (Alice and Bob shall only rely on some previously shared secret for privacy), from cryptography to data hiding [START_REF] Furon | European Project IST-1999-10987 CERTIMARK[END_REF]. They used Diffie and Hellman methodology, and Shannon's cryptographic framework [START_REF] Shannon | Communication theory of secrecy systems[END_REF], to classify the watermarking attacks into categories, according to the type of information Eve has access to [START_REF] Perez-Freire | Secret dither estimation in latticequantization data hiding: A set-membership approach[END_REF], namely: Watermarked Only Attack (WOA), Known Message Attack (KMA), Known Original Attack (KOA), Constant-Message Attack (CMA), and Estimated Original Attacks (EOA). Levels of security have been recently defined in these setups. The highest level of security in WOA is called stego-security [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF], whereas topological security tends to improve the ability to withstand attacks in KMA, KOA, and CMA setups [START_REF] Guyeux | Chaotic iterations versus spread-spectrum: chaos and stego security[END_REF]. It has been previously established that, in order to enlarge the knowledge of the level of security of a steganographic scheme, the quantity of disorder generated by the chaos of its topological security can be measured evaluating the well-known Lyapunov exponent [START_REF] Martínez-Ñonthe | Cryptosystem with one dimensional chaotic maps[END_REF][START_REF] Mao | An encryption algorithm of chaos based on sine square mapping[END_REF][START_REF] Bahi | Lyapunov exponent evaluation of a digital watermarking scheme proven to be secure[END_REF]. The evaluation of this exponent allow to characterize the ability of the scheme to face an attacker in the context of an EOA.

The first contribution of this article consists in a relation established between how fine is a topology and the chaotic behavior of a dynamical system described with this topology. The second contribution is the security study of a previously released stego and topologically secure steganographic scheme called C I S 2 , on a new topological space, namely the real line numbers R. On this new space, the topological security of C I S 2 is firstly evaluated, and its Lyapunov exponent is then computed, in order to quantify its level of disorder. Incidentally, this computation allows to measure the resistance of the C I S 2 scheme against a category of attacks called Estimated Original Attack. This study follows a same canvas than a previous work dealing with digital watermarking, but it is conducted here for a steganographic scheme. To achieve this work, a new semi-conjugacy model must be written for the scheme C I S 2 , which is then established and proven here.

This document is organized as follows. Notions and firsts results concerning the mathematical theory of chaos are introduced in the next section. Then, in Section 3, security notions and classes of attacks under consideration in the information hiding community are recalled. In Section 4, the steganographic scheme studied in this document is presented, and the formalization allowing its topological security evaluation is given in the next section. This model is then used in Section 6 to design a new semi-conjugacy allowing its security study on a new space (Sect. 7), and its Lyapunov exponent is finally evaluated in Section 8. This paper ends by a conclusion section where our contribution is summarized and intended future researches are given.

THE MATHEMATICAL THEORY OF CHAOS

Notations and Terminologies

In what follows, B denotes the Boolean set {0, 1}, S n stands for the n th term of a sequence S, V i is for the i th component of a vector V , and 0; N is the integer interval {0, 1, . . . , N}. Furthermore, the following definitions will be used in this document.

Definition 1

The discrete Boolean metric is the application δ : B -→ B defined by δ(x, y) = 0 ⇔ x = y.

Definition 2

The vectorial negation is the function

f 0 : B N -→ B N defined by f 0 (b 0 , • • • , b N-1 ) = (b 0 , • • • , b N-1 )
, where x is the negation of the Boolean x.

Definition 3 A strategy adapter is a sequence which elements belong into 1, k , where k ∈ N * . The set of all strategies having terms in 1, k is denoted by S k .

Definition 4 For k ∈ N * , the initial function is the map i

k : S k -→ 1, k defined by i k (S n ) n∈N = S 0 . Definition 5 Let k ∈ N * . The shift function is the map σ k : S k -→ S k defined by σ k (S n ) n∈N = (S n+1 ) n∈N .
It is now possible to give some recalls in the field of the mathematical topology [START_REF] Schwartz | Analyse: topologie générale et analyse fonctionnelle[END_REF] to make this document self contained.

The Chaotic Dynamical Systems

Let (X , τ) be a topological space and f a continuous function on (X , τ).

Definition 6 f is said to be topologically transitive if, for any pair of open sets U,V ⊂ X , there exists k > 0

such that f k (U) ∩V = ∅. Definition 7 (X , f ) is regular if the set of periodic points is dense in X .
It is now possible to introduce the well-established mathematical definition of chaos [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF].

Definition 8 A function f : X -→ X is said to be chaotic on X if it is regular and topologically transitive.

If the topological space is indeed a metric space (X , d), then the sensibility of the system under iterations, regarding its initial conditions, can be quantified as follows.

Definition 9 f has sensitive dependence on initial conditions if there exists δ > 0 such that, for any x ∈ X and any neighborhood V of x, there exist y ∈ V and n 0 such that d f n (x), f n (y) > δ. δ is called the constant of sensitiveness of f . This property is implied by both the regularity and transitivity presented above [START_REF] Banks | On devaney's definition of chaos[END_REF]. And so, when f is chaotic, fundamentally different behaviors are possible for the system, and they occur in an unpredictable way.

Let us state now some basic results that surprisingly cannot be found in the literature. To simplify the presentation, some notations must be firstly introduced: X τ will stand for the topological space (X , τ), whereas V τ (x) is the set of neighborhoods of x for the topology τ (in unambiguous cases, we will simply use

V (x)).
Theorem 1 Let X be a set, and τ, τ two topologies on X such that τ is finer than τ. Let f : X → X , continue for both τ and τ .

If (X τ , f ) is chaotic in the sense of Devaney, then

(X τ , f ) is also chaotic. Proof 1 Let ω 1 , ω 2 two open sets of τ. Then ω 1 , ω 2 ∈ τ , because τ is finer than τ. As f is τ -transitive, then ∃n ∈ N, ω 1 ∩ f (n) (ω 2 ) = ∅. As a consequence, f is τ-transitive.
Let us now establish the regularity of (X τ , f ), i.e., for all x ∈ X and all τ-neighborhood V of x, there exists a periodic point for f in V . Let x ∈ X , and V ∈ V τ (x) a τ-neighborhood of x. By definition of a neighborhood, ∃ω ∈ τ, x ∈ ω ⊂ V . However τ ⊂ τ , so ω ∈ τ , and then V ∈ V τ (x). But (X τ , f ) is regular, So there exists a periodic point for f in V , and the regularity of (X τ , f ) is proven.

Let us finally recall another topological quantitative property of chaos:

Definition 10 A function f is said to be expansive if ∃ε > 0, ∀x = y, ∃n ∈ N, d( f n (x), f n (y)) ε.
Sometimes, instead of trying to prove properties directly on the system itself, it is preferable to reduce the initial problem to another one whose characteristics are known or appear more accessible. Such a reduction tool is called, in the mathematical theory of chaos, the semi-conjugacy.

The topological semi-conjugacy

Definition 1 The discrete dynamical system (X , f ) is topologically semi-conjugate to the system (Y , g) if it exists a function ϕ : X -→ Y , both continuous and onto, such that:

ϕ • f = g • ϕ,
that is, which makes commutative the following diagram [START_REF] Formenti | Automates cellulaires et chaos : de la vision topologique la vision algorithmique[END_REF].

X f ----→ X ϕ     ϕ Y ----→ g Y
In this case, the system (Y , g) is called a factor of the system (X , f ).

Various dynamical behaviors are inherited by systems factors [START_REF] Formenti | Automates cellulaires et chaos : de la vision topologique la vision algorithmique[END_REF]. They are summarized in the following proposition:

Proposition 1 Let (Y , g) a factor of the system (X , f ). Then: 1. for all j k, p ∈ Per k ( f ) =⇒ ϕ(p) ∈ Per j (g),
where Per n (h) stands for the set of points of period n for the iteration function h

. 2. (X , f ) regular =⇒ (Y , g) regular, 3. (X , f ) transitive =⇒ (Y , g) transitive. So if (X , f ) is chaotic as defined by Devaney, then (Y , g) is chaotic too.

The Lyapunov Exponent

Some dynamical systems are very sensitive to small changes in their initial conditions, which is illustrated by both the constants of sensitiveness to initial conditions and of expansiveness introduced respectively in Definitions 9 and 10. However, these variations can quickly take enormous proportions, grow exponentially, and none of these constants can illustrate that. Alexander Lyapunov has examined this phenomenon and introduced an exponent that measures the rate at which these small variations can grow.

Definition 11 Given f : R -→ R, the Lyapunov exponent of the system composed by x 0 ∈ R and

x n+1 = f (x n ) is defined by: λ(x 0 ) = lim n→+∞ 1 n n ∑ i=1 ln f x i-1 .
Consider a dynamical system with an infinitesimal error on the initial condition x 0 . When the Lyapunov exponent is positive, this error will increase exponentially (situation of chaos), whereas it will decrease if λ(x 0 ) 0.

Let us now recall the information hiding security framework developed this last decade.

INFORMATION HIDING SECURITY

In the prisoner problem of Simmons [START_REF] Simmons | The prisoners' problem and the subliminal channel[END_REF], Alice and Bob are in jail, and they want to devise an escape plan by exchanging hidden messages in innocent-looking cover contents. These messages are to be conveyed to one another by a common warden, Eve, who over-drops all contents and can choose to interrupt the communication if they appear to be stego-contents.

In the steganography framework, in the context of the Simmons' prisoner problem, attacks have been classified in [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF] as follows:

• A Watermark-Only Attack WOA occurs when an attacker has only access to several watermarked contents.

• A Known-Message Attack (KMA) occurs when an attacker has access to several pairs of watermarked contents and corresponding hidden messages.

• A Known-Original Attack KOA is when an attacker has access to several pairs of watermarked contents and their corresponding original versions.

• A Constant-Message Attack CMA occurs when the attacker observes several watermarked contents and only knows that the unknown hidden message is the same in all contents. • Finally, an Estimated Original Attacks (EOA) occurs when the attacker has access to an estimation of the original host signal, with possibly some estimation errors.

In the framework of WOA, the stegosecurity [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF] is relevant to evaluate the security of information hiding processes. It is the highest security level in WOA setup. To recall it, the following notations must firstly be introduced: K is the set of embedding keys, p(X) is the probabilistic model of N 0 initial host contents, p(Y |K 1 ) is the probabilistic model of N 0 watermarked contents. Furthermore, it is supposed in this context that each host content has been watermarked with the same secret key K 1 and the same embedding function e.

It is now possible to define the notion of stegosecurity: Definition 12 (Stego-Security) In the Watermark-Only Attack framework, the embedding function e is stego-secure if and only if:

∀K 1 ∈ K, p(Y |K 1 ) = p(X).
In the other frameworks (KOA, KMA, and CMA), the topological security should be investigated [START_REF] Friot | Chaotic iterations for steganography -stego-security and chaos-security[END_REF]. In this article, we focus more specifically on this topological security, which is recalled below.

To check whether an information hiding scheme S is topologically secure or not, S must be written as an iterate process x n+1 = f (x n ) on a metric space (X , d). This formulation is always possible [START_REF] Bahi | A chaos-based approach for information hiding security[END_REF]. So, Definition 13 (Topological Security) An information hiding scheme S is said to be topologically secure on (X , d) if its iterative process has a chaotic behavior according to Devaney. Thus a data hiding scheme is secure if it is unpredictable. Its iterative process must satisfy the Devaney's chaos property and its level of topological security increases with the number of chaotic properties satisfied by it.

This new concept of security for data hiding schemes has been proposed in [START_REF] Bahi | A chaos-based approach for information hiding security[END_REF] as a complementary approach to the existing framework. It contributes to the reinforcement of confidence into existing secure data hiding schemes. Additionally, the study of security in KMA, KOA, and CMA setups is realizable in this context. Finally, this framework can replace stego-security in situations that are not encompassed by it. In particular, this framework is more relevant to give evaluation of data hiding schemes claimed as chaotic.

In the EOA framework, the evaluation of the Lyapunov exponent, which is the subject of this research work, is relevant to quantify the level of security of steganographic processes proven to be topologically secure. Indeed, the Lyapunov exponent participates to the measurement of this topological security. In an EOA setup, the attacker has only access to estimations of the original content. With just this knowledge, he or she should not be in measure to recover any information about the secret message or the secret key. The topological security, with the two other notions of sensibility and expansiveness introduced in Definitions 9 and 10, are relevant to face attacks in this context. However, these two topological properties give no precise quantification of the security of the scheme, which justifies the consideration of the Lyapunov exponent.

THE STEGANOGRAPHIC SCHEME C I S 2

To explain how to use chaotic iterations for information hiding, we must firstly define the significance of a given coefficient, and the notion of most and least significant coefficients (MSCs and LSCs).

We first notice that terms of the original content x that may be replaced by terms taken from the secret message y are less important than other ones: they could be changed without be perceived as such. For a given host content x, MSCs are then ranks of x that describe the relevant part of the image, whereas LSCs translate its less significant parts. These two definitions are illustrated on Figure 1, where the LSCs correspond to the last three bits of each pixel.

The steganographic scheme C I S 2 that generalizes the watermarking scheme based on chaotic iterations can now be recalled. In this part the following notations will be used: x 0 ∈ B N is the N LSCs of a given cover media C, m 0 ∈ B P is the secret message to embed into x 0 , S p ∈ S N is the place strategy, S c ∈ S P is the choice strategy, and lastly S m ∈ S P is the mixing strategy.

The steganographic scheme is defined by ∀(n, i, j) ∈ N * × 0; N -1 × 0; P -1 : and

x n i = x n-1 i if S n p = i m S n c if S n p = i,
m n j =      m n-1 j if S n m = j m n-1 j if S n m = j.
where m n-1 j is the Boolean negation of m n-1 j . The new LSCs of the stego-content are the Boolean vector y = x P ∈ B N .

TOPOLOGICAL MODEL FOR

C I S 2 AND SECURITY ANALYSIS ON X 2 In this section is recalled the topology used in order to model the steganographic scheme C I S 2 by a discrete dynamical system in a topological space [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF]. Let

F : 0; N -1 × B N × 0; P -1 × B P -→ B N (k, x, λ, m) -→ δ(k, j).x j + δ(k, j).m λ j∈ 0;N-1
where + and . are the Boolean addition and product operations.

Consider the phase space X 2 defined as follow: X 2 = S N × B N × S P × B P × S P , where S N and S P are the sets introduced in Section 2.1.

The map G f 0 : X 2 -→ X 2 is defined by:

G f 0 S p , x, S c , m, S m = σ N (S p ), F (i N (S p ), x, i P (S c ), m), σ P (S c ), G f 0 (m, S m ), σ P (S m ) .
Then C I S 2 can be described by the iterations of the following discrete dynamical system:

X 0 ∈ X 2 and X k+1 = G f 0 (X k ).
By comparing X 2 and X 1 , it has been proven in [START_REF] Friot | Chaotic iterations for steganography -stego-security and chaos-security[END_REF] that:

Proposition 1 X 2 has, at least, the cardinality of the continuum.

A new distance has been defined on X 2 as follow: ∀X, X ∈ X 2 , if X = (S p , x, S c , m, S m ) and X = ( Šp , x, Šc , m, Šm ), then:

d 2 (X, X) = d B N (x, x) + d B P (m, m)+ d S N (S p , Šp ) + d S P (S c , Šc ) + d S P (S m , Šm )
, where:

• d B N (E, Ě) = N-1 ∑ k=0 δ(E k , Ěk ) ∈ 0; N , • and d S N (S, Š) = 9 N ∞ ∑ k=1 |S k -Šk | 10 k ∈ [0; 1]
are respectively distances on B N and S N (∀N ∈ N * ).

To demonstrate that C I S 2 is another example of topological chaos in the sense of Devaney, it has been firstly established in [START_REF] Friot | Chaotic iterations for steganography -stego-security and chaos-security[END_REF] that,

Proposition 2 G f 0 is continuous on (X 2 , d 2 ).
Then it has been proven that (X 2 , G f 0 ) is topologically transitive, regular, and has sensitive dependence on initial conditions. Then we have the result:

Theorem 1 G f 0 is a chaotic map on (X 2 , d 2 ) in the sense of Devaney, and consequently the scheme C I S 2 is topologically secure.

Another theorem about the security of C I S 2 has been established in [START_REF] Friot | Chaotic iterations for steganography -stego-security and chaos-security[END_REF].

Theorem 2 C I S 2 is stego-secure.

A TOPOLOGICAL SEMI-CONJUGACY BETWEEN

X 2 AND R

In this section, by using a topological semiconjugacy, we show that C I S 2 modeled by G f 0 on X can be described as iterations on a real interval.

As our researches are inspired by the work of [START_REF] Bahi | Lyapunov exponent evaluation of a digital watermarking scheme proven to be secure[END_REF], the proofs detailed in this document will follow a same canvas. To do so, some notations and terminologies must be introduced another time.

Let X (N;P) = S N × B N × S P × B P × S P . In what follows and for easy understanding, we will assume that N = 3 and P = 2. So N + P = 5 and NP 2 = 12. However, an equivalent formulation of the following can be easily obtained by replacing the bases 5 and 12 by any base (N + P) and (NP 2 ). N has only to be greater than P. Definition 14 The function ψ : 1, N × 1, P × 1, P → 0, NP 2 -1 is defined by: ψ S i p , S i c , S i m = (S i p -1)P 2 + (S i c -1)P + (S i m -1). This function aims to convert a strategy of triplets in a simple strategy of integers expressed in a different base. Obviously, ψ is a bijective function, the reverse operation will be denoted by ψ -1 . The three projections of ψ -1 are denoted by: ψ -1 Definition 15 Let us define ϕ :

1 ψ S i p , S i c , S i m = S i p , ψ -1 2 ψ S i p , S i c , S i m = S i c , and
ψ -1 3 ψ S i p , S i c , S i m = S i m . Base Base Base Base N = 3 P = 2 P = 2 NP 2 = 12 S i p S i c S i m ψ S i p , S i c , S i m 1 1 1 0 1 1 2 1 1 2 1 2 1 2 2 3 2 1 1 4 2 1 2 5 2 2 1 6 2 2 2 7 3 1 1 8 3 1 2 9 3 2 1 10 3 2 2 11
X (3;2) = S 3 × B 3 × S 2 × B 2 × S 2 -→ 0, 2 5 , as follows. If S p , E, S c , M, S m = (S 0 p , S 1 p , . . .); (E 0 , E 1 , E 2 , E 3 ); (S 0 c , S 1 c , . . .); (M 0 , M 1 ); (S 0 m , S 1 m , . . .) , then ϕ S p , E, S c , M, S m is the real number: • whose integral part e is 2 ∑ k=0 2 4-k E k + 4 ∑ k=3 2 4-k M k-3 , that is, the binary digits of e are E 0 E 1 E 2 M 0 M 1 . • whose decimal part s is equal to: s = 0, ψ S 0 p , S 0 c , S 0 m ψ S 1 p , S 1 c , S 1 m ψ S 2 p , S 2 c , S 2 m . . . = ∑ +∞ k=1 12 -k S k-1 . s is thus expressed in base 12.
ϕ realizes the association between a point of X (3;2)

and a real number into 0, 2 5 . We must now translate the steganographic process C I S 2 , which is represented by G f 0 iterations on this real interval. To do so, two intermediate functions over 0, 2 5 denoted by e and s must be introduced.

Definition 16 Let x ∈ 0, 2 5 and:

• e 0 , . . . , e 4 the binary digits of the integral part of x:

x = 4 ∑ k=0 2 4-k e k .
• (s k ) k∈N the digits of x, expressed in base 12, where the chosen decimal decomposition of x is the one that does not have an infinite number of

11: x = x + +∞ ∑ k=0 s k 12 -k-1 .
e and s are thus defined as follows:

e : 0, 2 5 -→ B 3 × B 2 x
-→ ((e 0 , e 1 , e 2 ); (e 3 , e 4 ))

and s : 0, 2 5 -→ 0, 11 N x -→ (s k ) k∈N
We are now able to define the function g, whose goal is to translate the steganographic process C I S 2 represented by G f 0 on an interval of R.

Definition 17 g : 0, 2 5 -→ 0, 2 5 is such that g(x)

is the real number of 0, 2 5 defined below:

• its integral part has a binary decomposition equal to e 0 , . . . , e 4 , with ∀i ∈ 0, 2 :

e i =      e(x) i if i = ψ -1 1 s 0 e(x) 2+ψ -1 2 (s 0 ) if i = ψ -1 1 s 0
and ∀i ∈ 3, 4 :

e i =    e(x) i if i = ψ -1 3 s 0 e(x) i + 1 (mod 2) if i = ψ -1 3 s 0 ,
• whose decimal part is s(x) 1 , s(x) 2 , . . .

In other words, if x = 4 ∑ k=0 2 4-k e k + +∞ ∑ k=0 s k 12 -k-1 , then: g(x) = 2 ∑ k=0 2 4-k e k δ(k, ψ -1 1 (s 0 )) + 1 (mod 2) +e 2+ψ -1 2 (s 0 ) δ(k, ψ -1 1 (s 0 )) + 4 ∑ k=3 2 4-k (e k + δ(k, ψ -1 3 (s 0 ) (mod 2)) + +∞ ∑ k=0 s k+1 12 -k-1 ,
where δ is the discrete Boolean metric introduced in Definition 1.

Numerous metrics can be defined on the set 0, 2 5 , the most usual one being the Euclidian distance ∆(x, y) = |y -x| 2 . This Euclidian distance does not reproduce exactly the notion of proximity induced by our first distance d 2 on X 2 . Indeed d 2 is richer than ∆. This is the reason why we have to introduce the following metric.

Definition 18 Given x, y ∈ 0, 2 5 , D denotes the function from 0, 2 5 2 to R + defined by: D(x, y) = D e e(x), e(y) + D s s(x), s(y) , where:

D e (e, ě) = 4 ∑ k=0 δ(e k , ěk ), and D s (s, š) = ∞ ∑ k=1 |s k -šk | 12 k .
Proposition 3 D is a distance on 0, 2 5 .

PROOF The three axioms defining a distance must be checked.

• D 0, because everything is positive in its definition. If D(x, y) = 0, then D e (x, y) = 0, so the integral parts of x and y are equal (they have the same binary decomposition). Additionally, D s (x, y) = 0, then ∀k ∈ N * , s(x) k = s(y) k . In other words, x and y have the same k-th decimal digit, ∀k ∈ N * . And so x = y.

• Obviously, ∀x, y, D(x, y) = D(y, x).

• Finally, the triangle inequality is obtained due to the fact that both δ and |x -y| satisfy it.

The convergence of sequences according to D is not the same than the usual convergence related to the Euclidian metric. For instance, if x n → x according to D, then necessarily the integral part of each x n is equal to the integral part of x (at least after a given threshold), and the decimal part of x n corresponds to the one of x "as far as required". D is richer and more refined than the Euclidian distance, and thus is more precise.

ϕ has been constructed in order to be continuous and onto, so we obtained the following theorem:

Theorem 3 The steganographic process C I S 2 represented by G f 0 , X 2 can be considered as simple itera- tions on R, which is illustrated by the semi-conjugacy given below: All the points of I n have the same integral part e and the same decimal part s 0 : on the set I n , functions e(x) and x → s(x) 0 of Definition 16 only depend on n. So all the images g(x) of these points x:

X (3;2) , d 2 G f 0 ----→ X (3;2) , d 2 ϕ     ϕ 0, 2 5 , D ----→ g 0,
• Have the same integral part, which is e, except probably the bit number s 0 . In other words, this integer has approximately the same binary decomposition than e, the sole exception being the digit s 0 (this number is then either e + 2 12-s 0 or e -2 12-s 0 , depending on the parity of s 0 , i.e., it is equal to e + (-1) s 0 × 2 12-s 0 ). • A shift to the left has been applied to the decimal part y, losing by doing so the common first digit s 0 . In other words, y has been mapped into 12 × ys 0 . To sum up, the action of g on the points of I is as follows: first, make a multiplication by 12, and second, add the same constant to each term, which is 1 12 e + (-1) s 0 × 2 12-s 0s 0 .

We are now able to evaluate the Lyapunov exponent of our digital watermarking scheme based on chaotic iterations, which is now described by the iterations on R of the g function introduced in Definition 17.

7 TOPOLOGICAL SECURITY OF C I S 2 ON R According to Theorem 1, C I S 2 represented by the function G f 0 on X 2 is topologically secure, that is to say G f 0 , X 2 is chaotic in the sense of Devaney. We can deduce the same property for C I S 2 represented by the g function on R for the order topology. Indeed G f 0 , X 2 and g, [0, 2 5 [ D are semi-conjugate by ϕ as proven in the previous section. So g, [0, 2 5 [ D is a chaotic system according to Devaney, because the semi-conjugacy preserves this character (Proposition 1 in Section 2.3). However the topology generated by D is finer than the topology generated by the Euclidean distance ∆, which is the order topology. Finally, according to Theorem 1, we can affirm that the steganographic process C I S 2 represented by g is chaotic in the sense of Devaney for the order topology on R.

Having these assertions in mind, we can formulate the following theorem:

Theorem 2 The steganographic process C I S 2 represented by g on R is chaotic in the sense of Devaney, when the usual topology of R is used (the order topology).

This result is weaker than Theorem 1, which establish the chaotic property of C I S 2 for a finer topology. It is as if the chaos observed using usual tools like the Euclidian distance is still preserved when considering more powerful tools (higher resulution, i.e., finer topologies).

The result contained in Theorem 2 is however interesting, as it confirms that the followed approach does not lead to weaker properties. Indeed, this study has taken place in a system other than the one usually considered (X 2 instead of R), in order to be as closed as possible to the final computer machines. By doing so, we prevent from any loss of chaotic properties when computing the scheme written in mathematical terms. However, it might be feared that the choice of a discrete mathematics approach leads to a disorder of lower quality. In other words, we have achieved to prevent from a situation of great disorder lost during the computation into machines. However, the cost of such achievement were probably to obtain a disorder of poor quality. Theorem 2 proves exactly the contrary.

EVALUATION OF THE LYAPUNOV EXPONENT

Let L = x 0 ∈ 0, 2 5 ∀n ∈ N, x n / ∈ I , where I is the set of points in the real interval where g is not differentiable (as it is explained in Proposition 4). Then, Theorem 4 ∀x 0 ∈ L, the Lyapunov exponent of C I S 2 having x 0 for initial condition is equal to λ(x 0 ) = ln(12) > 0.

PROOF g is piecewise linear, with a slop of 12 (g (x) = 12 where the function g is differentiable).

Then ∀x ∈ L, λ(x) = lim n→+∞

1 n ∑ n i=1 ln g x i-1 = lim n→+∞ 1 n ∑ n i=1 ln |12| = lim n→+∞ 1 n n ln |12| = ln 12.
Remark 1 The set of initial conditions for which this exponent is not calculable is countable. This is indeed the initial conditions such that an iteration value will be a number having the form n 12 , with n ∈ N. Moreover, for a system having N + P cells (a number of LSCs equal to N and a secret message to embed of width equal to P), we will find, mutatis mutandis, an infinite uncountable set of initial conditions x 0 ∈ 0; 2 N+P such that λ(x 0 ) = ln(NP 2 ).

So, it is possible to make the Lyapunov exponent of the scheme C I S 2 as large as possible, depending on the number of least significant coefficients of the cover media we decide to consider, and on the width of the message to embed. As proven in [START_REF] Guyeux | Chaotic iterations versus spread-spectrum: chaos and stego security[END_REF], a large Lyapunov exponent makes it impossible to achieve the well-known "Estimated Original Attacks" [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF].

CONCLUSION AND FUTURE WORK

A new quantitative evaluation for the steganographic scheme C I S 2 is now available: its Lyapunov exponent is equal to ln(NP 2 ), where N is the number of least significant coefficients of the cover media and P the width of the secret message to embed. This exponent allows to quantify the amplification of the ignorance on the exact initial condition (the media without watermark) after several iterations of the steganographic process. It illustrates the disorder generated by iterations of the process, reinforcing its chaotic nature. Thanks to its topological security, this scheme is already able to face an attacker in the context of Known-Message Attack, Known-Original Attack, and Constant-Message Attack. In addition, this result implies that it is also able to resist in the context of an Estimated Original Attacks.

Using the semi-conjugacy described here, it will be possible in a future work to compare the topological behavior of C I S 2 on X 2 and R, and to explore the topological security of the steganography scheme using this new topology. Then, an analogue study of the two other topologically secure schemes cited here will be conducted in order to compare these processes, being thus able to choose the best one according to the type of applications under consideration. Finally, security in steganography context will be investigated too, and topological security will be applied in this framework.

Figure 1 :

 1 Figure 1: Most and least significant coefficients of Lena.

Table 1 :

 1 Illustration of the function ψ (see Definition 14).