Yoann Gelineau
email: gelineau@math.univ-lyon1.fr

AND Heesung Shin
email: hshin@math.univ-lyon1.fr

Jiang Zeng

BIJECTIONS FOR ENTRINGER FAMILIES

André proved that the number of alternating permutations on {1, 2, ..., n} is equal to the Euler number En. A refinement of André's result was given by Entringer, who proved that counting alternating permutations according to the first element gives rise to Seidel's triangle (E n,k ) for computing the Euler numbers. In a series of papers, using generating function method and induction, Poupard gave several further combinatorial interpretations for E n,k both in alternating permutations and increasing trees. Kuznetsov, Pak, and Postnikov have given more combinatorial interpretations of E n,k in the model of trees. The aim of this paper is to provide bijections between the different models for E n,k as well as some new interpretations. In particular, we give the first explicit one-to-one correspondence between Entringer's alternating permutation model and Poupard's increasing tree model.

Introduction

The Euler numbers E n are defined by the generating function n≥0 E n

x n n! = tan(x) + sec(x)

= 1 + x + x 2 2! + 2

x 3 3! + 5

x 4 4! + 16

x 5 5! + 61

x 6 6! + 272

x 7 7! + 1385

x 8 8! + • • • .
Let A n be the set of alternating permutations of [n] := {1, 2, . . . , n}, that is, the permutations π = π 1 π 2 . . . π n on [n] satisfying π 1 > π 2 < π 3 > π 4 < • • • , in an alternating way. For example, the alternating permutations of [4] are:

2 1 4 3, 3 2 4 1, 3 1 4 2, 4 2 3 1, 4 1 3 2.

André [START_REF] André | Développement de sec x et tan x[END_REF] proved that E n is the cardinality of the set A n . A recent survey on alternating permutations and Euler numbers is given by Stanley [START_REF] Stanley | A Survey of Alternating Permutations[END_REF]. The Entringer numbers [START_REF] Entringer | A combinatorial interpretation of the Euler and Bernoulli numbers[END_REF] were introduced to enumerate the alternating permutations according to the first term. More precisely, let A n,k be the set of permutations π ∈ A n such that π 1 = k and E n,k the cardinality of A n,k . The first values of E n,k are given in Table 1.

n \ k 1 2 3 4 5 6 7 1 1 2 0 1 3 0 1 1 4 0 1 2 2 5 0 2 4 5 5 6 0 5 10 14 16 16 7 0 16 32 46 56 61 61 Theorem 1.1 (Entringer). The numbers (E n,k ) ( n ≥ k ≥ 1) satisfy

E 1,1 = 1, E n,1 = 0 (n ≥ 2), E n,k = E n,k-1 + E n-1,n-k+1 . (1)
Iterating the above recurrence, we get E n+1,n+1 = E n,n + E n,n-1 + • • • + E n,1 , which is equal to E n by André's result. Hence the Euler numbers E n = E n+1,n+1 are the diagonal entries in Table 1.

If we display the Entringer numbers E n,k in a suitable way as follows,

E1,1 E2,1 → E2,2 E3,3 ← E3,2 ← E3,1 E1,1 → E4,2 → E4,3 → E4,4 E5,5 ← E5,4 ← E5,3 ← E5,2 ← E5,1 • • • ⇐⇒ 1 0 → 1 1 ← 1 ← 0 0 → 1 → 2 → 2 5 ← 5 ← 4 ← 2 ← 0 • • •
then the recurrence relation (1) leads to Seidel's scheme [START_REF] Seidel | Über eine einfache Entstehungsweise der Bernoullischen Zahlen und einiger verwandten Reihen[END_REF] for computing Euler numbers, which was rediscovered later by Kempner [START_REF] Kempner | On the shape of polynomial curves[END_REF].

A sequence of sets (X n,k ) 1≤k≤n is called an Entringer family if for 1 ≤ k ≤ n, the cardinality of X n,k is equal to E n,k .

Let X = {x 1 , . . . , x n } < be an ordered set such that x 1 < • • • < x n . An increasing tree on X is a spanning tree of the complete graph on X, rooted at x 1 and oriented from the smallest vertex x 1 , such that the vertices increase along the edges. Let T n be the set of 0-1-2 increasing trees T on [n], i.e. the increasing trees such that at most two edges go out from every vertex (see Figure 1). Foata and Schützenberger proved in [START_REF] Foata | Nombres d'Euler et permutations alternantes, A survey of combinatorial theory[END_REF]§5] that the Euler number E n is the cardinality of T n . A one-to-one correspondance between A n and T n was soon constructed by Donaghey [START_REF] Donaghey | Alternating permutations and binary increasing trees[END_REF] (see also [START_REF] Callan | A note on downup permutations and increasing 0-1-2 trees[END_REF]). However the tree counterpart of Entringer's result was found only in 1982 by Poupard [START_REF] Poupard | De nouvelles significations énumératives des nombres d'Entringer[END_REF]. If T is a 0-1-2 increasing tree and if (i, j) is an edge in T , i < j, we call i the father of j, and j a child of i. If i has no child, we say that i is an endpoint of T . A path in T is a sequence of vertices (a i ) such that a i is a child of a i-1 in T, and the main path of T is the path (a i ) 1≤i≤ℓ such that a 1 = 1, a i (i = 2 . . . ℓ) is the smallest child of a i-1 and a ℓ is an endpoint, denoted by p(T ). Let's denote by T n,k the set of trees T ∈ T n such that p(T ) = k.

Theorem 1.2 (Poupard). The sequence (T n,k ) 1≤k≤n is an Entringer family.

Note that contrary to the case of alternating permutations, it is not easy to interpret identity (1) in the model of 0-1-2 increasing trees. Indeed, Donaghey's bijection doesn't induce a bijection between A n,k and T n,k and Poupard's proof in [START_REF] Poupard | De nouvelles significations énumératives des nombres d'Entringer[END_REF] was analytic in nature. Finding a direct explanation in the model of trees was then raised as an open problem in [START_REF] Kuznetsov | Increasing trees and alternating permutations[END_REF]. The first aim of this paper is to build a bijection between A n,k and T n,k and answer the above open problem.

Theorem 1.3. For all n ≥ 1 and k ∈ [n], there is an explicit bijection Ψ :

A n,k → T n,k satisfying ∀π ∈ A n,k , π 1 = p(Ψ(π)).
Poupard [START_REF] Poupard | De nouvelles significations énumératives des nombres d'Entringer[END_REF][START_REF] Poupard | Two other interpretations of the Entringer numbers[END_REF] gave also other interpretations for Entringer numbers E n,k (see Section 4) in increasing trees and alternating permutations with induction proofs. Our second aim is to provide simple bijections between the other interpretations of Poupard in alternating permutations and the original interpretation in A n,k . Note that some other interpretations of Entringer numbers E n,k in the model of increasing trees were given in [START_REF] Kuznetsov | Increasing trees and alternating permutations[END_REF]. Recently, two new interpretations of Euler numbers were given by Martin and Wagner [START_REF] Martin | Updown numbers and the initial monomials of the slope variety[END_REF] in the model of G-words and R-words. We shall give the corresponding interpretations of the Entringer number E n,k in the later models.

The rest of this paper is organized as follows. In Section 2, we introduce an intermediate model D n,k and present a bijection ψ between A n,k and D n,k . In Section 3, we describe a bijection ϕ between D n,k and T n,k so that Ψ = ϕ • ψ provides the bijection for Theorem 1.3. As an application, in Subsection 3.2, we give a direct interpretation of (1) in the model of increasing trees. In Section 4, we recall the other interpretations of E n,k found by Poupard and establish simple bijections between these models. In Section 5, we give some new interpretations for E n,k , first refining the results of Martin and Wagner [START_REF] Martin | Updown numbers and the initial monomials of the slope variety[END_REF] in their model of G-words and R-words, and secondly introducing the new model of U-words.

The left-to-right coding ψ of alternating permutations

For n ≥ 2, let A n be the set consisting of ordered pairs (j, i) (1 ≤ i < j ≤ n), starred ordered pairs (j, i) * (1 ≤ i < j ≤ n), and the element (n) * = (n, n) * :

A n = {(j, i), (j, i) * , (n) * : 1 ≤ i < j ≤ n}. Definition 2.1. A sequence (∆ k ) of elements in A n is an encoding sequence of [n] if the following conditions are verified: (i) if ∆ k = (j, i) * and ∆ k+1 ∈ {(m, n), (m, n) * }, then i < m, (ii) if ∆ k = (j, i) and ∆ k+1 ∈ {(m, n), (m, n) * }, then i = m, (iii) if ∆ k = (j, i) *
, then the integers i and j don't appear in every ∆ ℓ , for ℓ > k, (iv) if ∆ k = (j, i), then the integers ℓ such that i < ℓ < j appear in an element ∆ ℓ , for ℓ > k, with ∆ ℓ ∈ {(j, i) * : 1 ≤ i < j ≤ n}. We denote by D n the set of encoding sequences of [n], and by D n,k the subset of D n consisting of encoding sequences starting with an element in {(k, i), (k, i) * , 1 ≤ i < k -1}.

For example, the elements in D 4 are: ((2, 1) * , (4, 3) * ), ((3, 2) * , (4, 1) * ) and ((3, 2), (2, 1) * , (4, 3) * ) , ((4, 3), (3, 2) * , (4, 1) * ) , ((4, 3), (3, 2), (2, 1) * , (4, 3) * ) .

Let π be an alternating permutation on an ordered set I = {a 1 , a 2 , . . . , a n } < such that π 1 > π 2 < π 3 > π 4 < . . . (that can be interpreted by an element of A n ). Suppose π 1 = a k and π 2 = a j with a k > a j . If we apply successively the elementary transpositions (a k , a k-1 ), (a k-1 , a k-2 ), . . . , (a j+2 , a j+1 ) to π:

π (1) = (a k , a k-1 ) • π, π (2) = (a k-1 , a k-2 ) • π (1) , . . . π (k-j-1) = (a j+2 , a j+1 ) • π (k-j-2) ,
then we obtain a permutation starting with a j+1 a j (from left-to-right). Clearly all the permutations π (1) , . . . , π (k-j-1) are alternating permutations. Deleting the first two elements in π (k-j-1) , noted as (a j+1 , a j ) * , we get an alternating permutation, say π (k-j) , on I \{a j+1 , a j }. So we can apply the same procedure to the resulted permutation, and iterate this algorithm until we obtain the empty permutation. Clearly the last deletion is (n) * if n is odd. In others words, we can write the algorithm as follows:

(1) Start with ∆(π) = ∅ and I (2) While Card(A) ≥ 2, do: (a) While there is no i such that (π 1 , π 2 ) = (a i+1 , a i ), do:

∆(π) ← (∆(π), (a i+1 , a i )), π ← (a i , a i+1 ) • π. (b) If there is i such that (π 1 , π 2 ) = (a i+1 , a i ), do: ∆(π) ← (∆(π), (a i+1 , a i ) * ), π ← π 3 π 4 . . . π n (eventually π = ∅), I ← I \ {a i , a i+1 }. (3) If Card(I) = 1 with I = {a n }, do: D π ← (∆(π), (a n ) * ), π ← ∅, I ← ∅.
We call the sequence of the successive operations in the above algorithm the LR-code of π, which is a sequence ψ(π) = ∆(π) made of

• the transpositions (j, i), 1 ≤ i < j ≤ n,

• the deletions (j, i) * , 1 ≤ i < j ≤ n (or the deletion (n) * ).

Example 2.2. Let's take π = 7 4 8 5 9 1 6 2 3 ∈ A 9,7 .

Step π ∆(π) i 0 7 4 8 5 9 1 6 2 3 ∅ 1 6 4 8 5 9 1 7 2 3 (7, 6) 2 5 4 8 6 9 1 7 2 3 (6, 5) 3 8 6 9 1 7 2 3 (5, 4) * 4 7 6 9 1 8 2 3 (8, 7) 5 9 1 8 2 3 (7, 6) * 6 8 1 9 2 3 (9, 8) 7 3 1 9 2 8 (8, 3) 8 2 1 9 3 8 (3, 2) 9 9 3 8 (2, 1) * 10 8 3 9 (9, 8) 11 9 (8, 3) * 12 ∅ (9) * Thus, the LR-code of π is ∆(π) = ((7, 6), (6, 5), (5, 4) * , (8, 7), (7, 6) * , (9, 8), (8, 3), (3, 2), (2, 1) * , (9, 8), (8, 3) * , (9) * ) .

Theorem 2.3. For all n ≥ 1 and k ∈ [n], the LR-coding mapping ψ is a bijection between A n,k and D n,k .

Proof. It suffices to show that the sequence ψ(π) verifies the points (i)-(iv) of Definition 2.1.

• When ∆ k = (j, i) * , we have π 1 = j and π 2 = i. Since π is alternating, we know that m = π 3 > i. The first operation that follows is either a transposition (m, n), or a deletion (m, n) * , thus (i) is verified. • When ∆ k = (j, i), we are in the while loop of the algorithm, and π 1 becomes i. Either the loop is not over, and then i is changed with a transposition (i, k), or the loop is over, and then i is deleted with a deletion (i, k) * . Thus (ii) is verified.

• When ∆ k = (j, i) * ,
in the algorithm, i and j are erased from I. Then, they don't appear in any operation later, thus (iii) is verified. • When ∆ k = (j, i), we are in the while loop of the algorithm, and i and j must be consecutive elements in I. Then, the integers ℓ such that i < ℓ < j must have been erased from I before, thus (iv) is verified. It results that ψ(π) ∈ D n . Moreover, ψ(π) starts with (π 1 , j) or (π 1 , j) * with j < π 1 , so ψ(π) ∈ D n,k . The processus is clearly invertible so ψ is a bijection between A n,k and D n,k .

The previous theorem yields immediately a new interpretation for Entringer numbers.

Corollary 2.4. The sequence (D n,k ) 1≤k≤n is an Entringer family.

Remark 2.5. Denote the largest integer less than x by ⌊x⌋ and the number of ordered pairs (i, j) ∈ {1, . . . , n} such that i + 1 < j and π i > π i+1 < π j < π i by 31-2(π). Then, one can show that the length of the sequence ψ(π) is equal to

31-2(π) + n + 1 2 .
Indeed, 31-2(π) corresponds to the number of occurences of terms (j, i), j > i, in ψ(π), and there are n + 1 2 occurences of terms (j, i) * , j > i, in ψ(π). Note that various formulae for counting 31-2-patterns in alternating permutations are given in [Che08, JV10, SZ10].

Remark 2.6.

Let n ≥ 2 and k ≥ 2. An element ∆ ∈ D n,k begins either with (k, k -1) or (k, k -1) * . If ∆ 1 = (k, k -1), then, the remaining sequence (∆ 2 , ∆ 3 , . . .) is still an encoding sequence of [n], starting with ∆ 2 ∈ {(k -1, i), (k -1, i), 1 ≤ i ≤ k -2}. Thus, there are E n,k-1 encoding sequences starting by (k, k -1).
If ∆ 1 = (k, k -1) * , then, the remaining sequence (∆ 2 , ∆ 3 , . . .) doesn't contain the elements k and k + 1 and starts with an element in {(i, j), (i, j) * , 1 ≤ j ≤ i -1} with i ≥ k + 1. In other words, this is an encoding sequence of n -2 elements, starting with an integer i that must be greater than the k -2 first elements. Thus, there are

E n-2,k-1 + E n-2,k + • • • E n-2,n-2 = E n-1,n-k+1 encoding sequences starting by (k, k -1) * .
Finally, the decomposition according to the nature of the first element of ∆ ∈ D n,k gives(1).

3. The left-to-right coding of increasing trees

3.1. The bijection ϕ : D n,k → T n,k . Starting from an encoding sequence ∆ = (∆ i ) 1≤i≤ℓ ∈ D n,k
, we construct a tree T = ϕ(∆) ∈ T n,k by reading the sequence ∆ in reverse order, i.e., from right to left. More precisely, for m = ℓ, ℓ -1, . . . , 1, we shall construct an increasing tree T m corresponding to each sequence (∆ m , . . . , ∆ ℓ ) such that

∆ m = (j m , i m ) or (j m , i m ) * =⇒ p(T m ) = j m , (2)
and define T = T 1 := ϕ(∆). The algorithm goes as follows:

• If the last element of ∆ is a singleton (n) * , construct the tree T ℓ with only one vertex n; if the last element of ∆ is a deletion (n, i) * , construct the increasing tree T ℓ with only one edge i → n. Clearly (2) is verified. Now, suppose that we have constructed a tree T m-1 corresponding to the sequence (∆ m-1 , . . . , ∆ ℓ ) with the property (2). • ∆ m = (j m , i m ) * with j m > i m , we add i m and j m in the tree T m-1 to obtain T m .

Suppose that the main path of T m-1 is (a 1 , . . . , a pm ).

-If i m < a 1 , add the edges (i m , a 1 ) and (i m , j m ) to the tree T m-1 . Then, the tree T m is an increasing tree rooted at i m with (i m , j m ) as the main path.

j m i m a 2 a 1 A B a 2 a 1 A B -If i m > a 1
, by induction hypothesis and property (ii) of encoding sequences, we see that a 1 < m. Hence, there exists k ∈ {1, . . . , p m -1} such that a k < i m < a k+1 . Then, erase the edge (a k , a k+1 ), create the edges (a k , i m ), (i m , a k+1 ) and (i m , j m ). Clearly, the tree T m is an increasing tree with (i m , j m ) as the last edge of the main path.

jm im a k+1 a k a k a k+1 A A B B C C
• ∆ m = (j m , i m ) with j m > i m , by induction hypothesis and property (iii) of encoding sequences, we derive that i m is at the end of the main path. Then, we transform the tree T m-1 according to the two following situations: -Case A : if i m and j m are not siblings in T , just exchange the places of i m and j m in T . The tree remains increasing because Then j m is at the end of the main path in T . If m 1 denotes the parent of i m and j m in T , erase the edge (m 1 , j m ), create an edge (i m , j) m , then if A and B are the two subtrees starting from j m with min(A) < min(B) (eventually B is empty), cut the subtree A from j m and add it as a direct subtree of m 1 , cut the subtree B from j m and add it as a direct subtree of i m . The procedure can be illustrated with the following picture:

im jm B m1 A im jm m1 A B C C Theorem 3.1. For all n ≥ 1 and k ∈ [n], the mapping ϕ : D n,k -→ T n,k is a bijection.
Proof. It is sufficient to construct the inverse mapping of ϕ to show that this is a bijection.

Given T an increasing tree on the ordered set {a 1 , . . . , a n } with a 1 < • • • < a n , such that p(T ) = a k (that can be interpreted by an element of T n,k ), we construct an encoding sequence ∆ = ϕ -1 (T ) of [n] recursively as follows:

Case A. If a k-1 is the father of a k in T , then let m (m > a k ) be the other child of a k-1 (m = ∞ if a k is the only child of a k-1
) and s (s > k) be a sibling of a k-1 (s = ∞ if a k-1 has no sibling), and j the father of a k-1 in T . Case A-1. If m < ∞ and m < s, then define ϕ -1 (T ) = (a k , a k-1 ) * , ϕ -1 (T ′ ) , where T ′ is the tree obtained from T by deleting the vertices a k-1 , a k and their adjacent edges in T , and adding a new edge between m and j.

T

a k a k-1 B m j A s T ′ B m j A s C C
Case A-2. In the other cases (m = ∞ or m > s), then define ϕ -1 (T ) = (a k , a k-1 ), ϕ -1 (T ′ ) , where T ′ is the tree obtained from T by erasing the edges (a k-1 , a k ), (a k-1 , m) and (j, s) in T , and adding the edges (j, a k ), (a k , s), (a k , m). The procedure can be illustrated with the following picture:

T a k a k-1 B m j A s T ′ a k-1 a k j A m B s C C Case B. If a k-1 is not the father of a k in T , then define ϕ -1 (T ) = (a k , a k-1 ), ϕ -1 (T ′ )
, where T ′ is the tree obtained from T by exchanging the labels a k-1 and a k in T .

a k-1 a k A B a k a k-1 A B T T ′
It remains to prove that the obtained sequence ∆ verifies the points (i)-(iv) of Definition 2.1.

• If an element (j, i) * appears in ∆, that corresponds to the case A-1, when we delete the vertices i and j from the tree T . Then the next elements in ∆ don't contain neither i nor j since they corresponds to ϕ -1 (T ′ ). Moreover, if we are in the case A-1, the main path in the tree T ′ contains at least one element m with m > j > i, so the next element in ∆ must be (m, k) with m > k. Thus (i) and (iii) are verified. • If an element (j, i) appears in ∆, in both Case A-2 or Case B, the tree T ′ has i as endpoint of the main path. Then, the next element in ∆ must be (i, k) with i > k.

Moreover, i and j must be consecutive elements in the ordered set of labels in T . Then the elemnts ℓ such that i < ℓ < j don't appear in T . Thus (ii) and (iv) are verified.

Let Ψ = ϕ • ψ. Then Ψ : A n,k → T n,k is a bijection satisfying π 1 = p(Ψ(π)) for all π ∈ A n,k . Thus Theorem 1.3 is proved.
Example 3.2. Continuing the Example 2.2, we apply Ψ to π by using the known LR-code of π = 7 4 8 5 9 1 6 2 3. The details are given in Figure 2.

3.2. Interpretation of Entringer's formula (1) in T n . Following the interpretation of (1) in D n (cf Remark 2.6) and the bijection ϕ, we must consider the decomposition of the set T n,k either the first step in the construction of ϕ -1 would consist in either removing the elements k -1 and k, either transform the tree to obtain another tree of T n .

For T be an element of T n,k , we say that the edge (k -1, k) is removable if k -1 is the parent of k and if k -1 has another child m that is not greater than the sibling of k -1 (if such a sibling exists). For a visual representation, a tree T has its edge (k -1, k) revovable if it corresponds to the case A-1 in the proof of Theorem 3.1. If the edge (k -1, k) is not removable, the tree obtained after the first operation in the construction of ϕ -1 will be an increasing tree with n elements such that k -1 is the endpoint of the main chain. Then, there are exactly E n,k-1 trees such that the edge (k -1, k) is not removable.

ϕ • ψ(π)
If the edge is removable, the tree obtained with the first operation in the construction of ϕ -1 will be an increasing tree with n -2 elements (without the elements k -1 and k), and the end of the main path must be an element i greater than the k -2 first elements. Thus, there are

E n-2,k-1 + E n-2,k + • • • E n-2,n-2 = E n-1,n-k+1 increasing trees such that the edge (k -1, k) is removable.
Finally, an interpretation of (1) appears in the model of T n . The decomposition according to the removability of the edge (k -1, k) in T ∈ T n,k gives (1).

Poupard's other Entringer families

4.1. Another interpretation in increasing trees. Let T ′ n,k be the set of trees T ∈ T n such that the father of n in T is k -1. By using recurrence relations Poupard proved that E n,k is also the number of trees in T ′ n,k . A bijection ϕ ′ between T n,k and T ′ n,k was given in [KPP94, §6] for a more general class of increasing trees that they call geometric.

Another interpretation in alternating permutations. If π is a permutation of

A n,k , define θ(π) as follows :

• if k < n -k + 1 + π 2 , then θ(π) = (n -k + 1 + π 2 , n -k + π 2 , . . . , k + 1, k) • π, • if k > n -k + 1 + π 2 , then θ(π) = (n -k + 1 + π 2 , n -k + 2 + π 2 , . . . , k -1, k) • π. Since π is alternating, π 2 < k = π 1 . If k < n -k + 1 + π 2 , π 2 is unchanged by the cycle and then σ(π) 2 = π 2 . Thus σ(π) 2 < k < n -k + 1 + π 2 = σ(π) 1 and θ(π) is still alternating. If k > n -k + 1 + π 2 , since k ≤ n, then n -k + 1 + π 2 ≥ π 2 + 1, so π 2 is unchanged by the cycle, σ(π) 1 = n -k + 1 + π 2 > π 2 = σ(π) 2 and θ(π) is still alternating. Let's denote by A ′ n,k the set of permutations π ∈ A n such that π 1 -π 2 = n + 1 -k. Theorem 4.1. For all n ≥ 1 and k ∈ [n], the mapping θ is a bijection from A n,k to A ′ n,k . Moreover, for every π ∈ A n,k , θ(π) 2 = π 2 . Proof. By construction, θ is clearly inversible. Moreover, if σ ∈ A n with σ 1 -σ 2 = n -k + 1, • if k < n -k + 1 + σ 2 , then θ -1 (σ) = (k, k + 1, . . . , n -k + σ 2 , n -k + 1 + σ 2 ) • σ, • if k > n -k + 1 + σ 2 , then θ -1 (σ) = (k, k -1, . . . , n -k + 2 + σ 2 , n -k + 1 + σ 2 ) • σ. and then θ -1 (σ) ∈ A n,k .
With Theorem 4.1, the following interpretation of Poupard, proved in [START_REF] Poupard | Two other interpretations of the Entringer numbers[END_REF] by recurrence relations, can be recovered.

Corollary 4.2. The sequence (A ′ n,k ) 1≤k≤n is an Entringer family. Note that A ′ n,k ⊂ A n . Then, define θ 2 (π) for π ∈ A n . Actually, θ appears to be an involution on A n .

The result can also be generalized with the following observation. For any π ∈ A n , define the complement permutation π with

π i = n + 1 -π i for i ∈ [n]. Denote by A * n the set of permutations π such that π ∈ A n . Corollary 4.3. For n ≥ 1, we have π∈A * n q π 1 p π 2 -π 1 = π∈A * n p π 1 q π 2 -π 1 .
Proof. The mapping π → θ(π) is a bijection between {π ∈ A * n : π 1 = k} and {π ∈ A * n : π 2π 1 = k}. Thus, the two statistics π 1 and π 2π 1 are equidistributed on A * n . Indeed, with proof of Theorem 4.1, π → θ(π) is a bijection between {π ∈ A * n : π 1 = k, π 2π 1 = ℓ} and {π ∈ A * n : π 1 = ℓ, π 2π 1 = k}. Thus, there is also a symmetry between both statistics. 4.3. Interpretations in direct alternating permutations. Let's introduce the set DAP n of direct alternating permutations of [n], that is, the permutations π of [n] such that π -1

1 < π -1 n and π 1 > π 2 < π 3 > • • • or π 1 < π 2 > π 3 < • • • .
For example, the direct alternating permutations of [4] are 1 4 2 3, 1 3 2 4, 3 1 4 2, 2 3 1 4, 2 1 4 3.

Denote by DAP

n,k the set of π ∈ DAP n such that |π 1 -π 2 | = n -k + 1. The set A ′ n,k can be split in two disjoint subsets A ′ n,k,1n which is the set of permutations in A ′ n,k ∩ DAP n and A ′ n,k,n1 = A ′ n,k \ A ′ n,k,1n . If π ∈ A ′ n,k,1n , define β(π) = π, and if π ∈ A ′ n,k,n1 , define β(π) = π. Thus β(π) ∈ DAP n and β(π) 1 -β(π) 2 = -(n -k + 1).
Theorem 4.4. For all n ≥ 1 and k ∈ [n], the mapping β is a bijection between A ′ n,k and DAP n,k .

With the previous theorem, the interpretation of Poupard, proved in [START_REF] Poupard | Two other interpretations of the Entringer numbers[END_REF] by recurrence relations, can be recovered. Denote by DAP ′ n,k the set of π ∈ DAP n such that the term immediately before 1 is k, if k ≤ n -1, and DAP ′ n,n the set of π ∈ DAP n such that π 1 = 1. We want to construct a bijection ρ between A n,k and DAP ′ n,k . If k = n, it suffices to define for π ∈ A n,n , ρ(π) = π. Then, ρ(π) ∈ DAP ′ n,n . Assume that k ≤ n -1. The set A n,k can be split in two disjoint subsets A n,k,1n which is A n,k ∩ DAP n and A n,k,n1 := A n,k \ A n,k,1n . For an ordered set I = {a 1 , . . . , a n } with a 1 < • • • < a n , denote by σ I the permutation:

σ I = a 1 a 2 • • • a n a n a n-1 • • • a 1
Then, for a permutation π = π 1 . . . π n on the ordered set I, denote by π the complement permutation on the set I, that is π := σ I • π, and π R the reverse permutation:

π R := π n π n-1 . . . π 1 .
Note that when I = [n], the definition of the complement permutation coincides with the one in the Remark of Subsection 4.2.

Then, for a permutation

π ∈ A n,k , • If π ∈ A n,k,1n , we can write π = σ 1 1 σ 2 . Then, define ρ(π) = σ R 1 1 σ 2 . Since 1 < π 1 > π 2 , ρ(π) is still alternating, and the term just before 1 in ρ(π) is π 1 = k. • If π ∈ A n,k,n1 , we can write π = σ 1 n σ 2 . Then, define ρ(π) = σ R 1 1 σ 2 . Since 1 < π 1 > π 2
and σ 2 is alternating, ρ(σ 1 ) is still alternating, and the term just before 1 in ρ(π) is π 1 = k.

Theorem 4.6. For all n ≥ 1 and k ∈ [n], the mapping ρ is a bijection between A n,k and DAP ′ n,k . Proof. In order to prove that ρ is a bijection, it suffices to describe the inverse of ρ. Let π be an element in DAP n such that the term immediately before 1 in k. Following the construction of ρ, we have:

• If π ∈ A n,k , write π = τ 1 1 τ 2 . Then, ρ -1 (π) = τ R 1 1 τ 2 . • If π ∈ A n,k , write π = τ 1 1 τ 2 . Then, ρ -1 (π) = τ R 1 n τ 2 .
With the previous theorem, the following interpretation of Poupard, proved in [START_REF] Poupard | Two other interpretations of the Entringer numbers[END_REF] by recurrence relations, can be recovered.

Corollary 4.7. The sequence (DAP ′ n,k ) 1≤k≤n is an Entringer family. Denote by DAP ′′ n,k the set of π ∈ DAP n such that the term immediately after

n is n+1-k, if k ≤ n -1, and DAP ′′ n,n the set of π ∈ DAP n such that π n = n. Denote by ρ ′ the mapping defined for π ∈ DAP ′′ n,k by ρ ′ (π) = π R . Theorem 4.8. For all n ≥ 1 and k ∈ [n], the mapping ρ ′ is a bijection between DAP ′ n,k and DAP ′′ n,k . Proof. For k ≤ n -1, π ∈ DAP n has k just before 1 if and only if ρ ′ (π) has n + 1 -k just after n.
Corollary 4.9. The sequence (DAP ′′ n,k ) 1≤k≤n is an Entringer family.

New Entringer families

Interpretations in G-words and R-words. A permutation

π of I = {a 1 , . . . , a n } with a 1 < • • • < a n is called a G-word if (i) π 1 = a n , π n = a n-1 , (ii) π 2 > π n-1 (if n ≥ 4). Similarly, a permutation π of I is called an R-word if the previous condition (i) is verified and if (ii) is replaced by (ii') π 2 < π n-1 (if n ≥ 4
). A G-word (resp. an R-word) is said to be primitive if for any (i, j) ∈ [n] 2 , neither the word π i π i+1 . . . π j nor the word π j π j-1 . . . π i is a G-word (resp. an R-word). Denote respectively by G n and R n the set of primitive G-words on [n] and primitive R-words on [n]. For examples, the G-words in G n are: 6 3 4 2 1 5, 6 4 2 3 1 5, 6 2 3 4 1 5, 6 4 3 2 1 5, 6 2 4 3 1 5, and the R-words in R n are: 6 2 1 4 3 5, 6 2 3 1 4 5, 6 1 4 2 3 5, 6 3 1 2 4 5, 6 2 4 1 3 5. These permutations were introduced in [START_REF] Martin | The slopes determined by n points in the plane[END_REF] with the following problem. Let I n be the ideal of all algebraic relations on the slopes of all lines that can be formed by placing n points in a plane. Then, under two orders, I n is generated by monomials corresponding to respectively primitive G-words and primitive R-words.

Martin and Wagner proved [MW09] that E n is the number of primitive G-words (resp. the number of primitive R-words) on [n + 2]. Actually, this result can be refined to Entringer numbers, introducing a statistic on G-words.

Given a primitive G-word or an R-word π, define the route of π the sequence (α i ) defined with the following procedure:

•

α 1 = π 1 = a n , α 2 = π 2 = a n-1 , • for k ≥ 2, if α k = i, then
α k+1 = max {j ≤ i, π j < π i , π j , π j+1 , . . . , π i-1 , π i ∈ {α 1 , . . . , α k }} ∪ {j ≤ i, π j > π i , π i , π i+1 , . . . , π j-1 , π j ∈ {α 1 , . . . , α k }} One can represent the route of a G-word or an R-word π as a graph with the vertices π 1 , π 2 , . . . , π n ordered in a line, with only one path starting from n drawn upon the line and going successively, if it's possible, to n -1, n -2, . . . 1 without crossings (see Figure 3 for an example). Denote G n,k (resp. R n,k ) the set of primitive G-words π on [n + 2] (resp. primitive R-words π on [n + 2]) such that α n+2 = n + 1k. Proof. Use the bijection δ between G n and T n present in [START_REF] Martin | Updown numbers and the initial monomials of the slope variety[END_REF]. For π a primitive G-word on {a 1 , . . . , a n+2 with a 1 < • • • < a n+2 , denote by π ′ the word π 2 . . . π n+1 . If π ′ is a word on {a 1 , . . . , a n }, with a 1 < • • • < a n and a n = π ′ k for k ∈ {1, . . . , n}, define T = α(π ′ ) as the tree with root a 1 , from which two subgraphs go out, that are α(π ′ 1 π ′ 2 . . . π ′ k-1 ) and α(π ′ k+1 π ′ k+2 . . . π ′ n ) (eventually one of them of both are empty). The tree δ(π) = α(π ′ ) is a 0-1-2 increasing tree and the application δ is a bijection from G n to T n (see [START_REF] Martin | Updown numbers and the initial monomials of the slope variety[END_REF] for further details).

Moreover, it is easy to see that the labels upon the main path of T = δ(π) are successively (n + 1a 1 ), (n + 1a 2 ), . . . , (n + 1a m ), where a 1 . . . , a m (a 1 > • • • > a m ) are the different values that appear in the route of π. Thus, the end-point of the main path is k. Then, δ is a bijection between G n,k and T n,k .

For example, one can construct the tree that corresponds with the G-word π = 82546317 with this construction :

⇒

The analogue result for the R-word can be proved using the same method with the bijection δ ′ between R n and T n present in [START_REF] Martin | Updown numbers and the initial monomials of the slope variety[END_REF].

Interpretations in U-words.

Definition 5.2. A U-word of length n is a sequence u = (u i ) 1≤i≤n such that u 1 = 1 and ∀i ∈ {2, . . . , n}, u i + u i-1 ≤ i. We denote by U n the set of U-words of length n.

For example, the U-words of length 4 are:

1 1 1 1, 1 1 1 2, 1 1 1 3, 1 1 2 1, 1 1 2 2.
Denote by U n,k the set of U-words (u i ) ∈ U n such that u n = n + 1k.

Theorem 5.3. The sequence (U n,k ) 1≤k≤n is an Entringer family.

Proof. For any finite set X, let #X denotes its cardinality. For π ∈ A n,k , let γ(π) = w R , where w = w 1 . . . w n is the word defined by

w i = #{j ≥ π i , j ∈ {π 1 , π 2 , . . . , π i-1 }}, if i is odd, #{j ≤ π i , j ∈ {π 1 , π 2 , . . . , π i-1 }}, if i is even.
For example, if π = 6 3 5 1 7 2 4 ∈ A 7,6 , then the word w is computed as follows:

• {j ≥ 6} = {6, 7}, so w 1 = 2, • {j ≤ 3, j = 6} = {1, 2, 3}, so w 2 = 3, • {j ≥ 5, j ∈ {3, 6}} = {5, 7}, so w 3 = 2, • {j ≤ 1, j ∈ {3, 5, 6}} = {1}, so w 4 = 1,
• {j ≥ 7, j ∈ {1, 3, 5, 6}} = {7}, so w 5 = 1,

• {j ≤ 2, j ∈ {1, 3, 5, 6, 7}} = {2}, so w 6 = 1,

• {j ≥ 4, j ∈ {1, 2, 3, 5, 6, 7}} = {4}, so w 7 = 1, Then, w = 2 3 2 1 1 1 1 and γ(π) = 1 1 1 1 2 3 2. We show that the mapping γ is a bijection between A n,k and U n,k . Following the construction, γ(π) n = w 1 = n + 1π 1 = n + 1k. Moreover, when γ(π) i = w n+1-i is written, ni elements have been read in π before ; thus the number of elements counted by γ(π) i must be less than i. Moreover, the numbers counted by γ(π) i-1 and γ(π) i are in the ni elements that have not been read in π and are two disjoint sets since π is alternating. Thus γ(π) i + γ(π) i-1 must be less than i. Finally, γ(π) ∈ U n,k .

Conversely, if u ∈ U n,k , the permutation π = γ -1 (u) ∈ A n,k can be found back with:

• π 1 = n + 1 -u n • ∀n ≥ 1, π 2i is the u n-2i+1 -st smallest element in [n] \ {π 1 , . . . , π 2i-1 }. • ∀n ≥ 1, π 2i+1 is the u n-2i -st greatest element in [n] \ {π 1 , . . . , π 2i }.
Denote by U ′ n,k the set of U-words (u i ) ∈ U n such that u n+1 + u n = k.

Theorem 5.4. The sequence (U ′ n,k ) 1≤k≤n is an Entringer family.

Proof. There are two possibilities to prove the previous result. The mapping γ also induces a bijection between

A ′ n,k and U ′ n,k . For π ∈ A ′ n,k , there exists j ∈ [n] such that π ∈ A n,j , so we can define v = γ(π) ∈ U n,j ⊂ U n . It suffices to show that v ∈ U ′ n,k .
In the construction of γ(π), v n is the number of elements that are greater than π 1 , and v n-1 is the number of elements that are less than π 2 . Then

v n = n + 1 -π 1 and v n-1 = π 2 , and v n-1 + v n = n + 1 -(π 1 -π 2 ) = k since π ∈ A ′ n,k . Actually, it is easy to construct a bijection α : U n,k -→ U ′ n,k . For u = (u 1 , . . . , u n ) ∈ U n,k , let α(u) = (u 1 , u 2 , . . . , u n-1 , n + 1 -u n-1 -u n ). Since u ∈ U n,k , u n -u n-1 ≤ n + 1, so we have α(u) ∈ U n . Moreover, the last element α(u) n = n + 1 -u n-1 -(n + 1 -k) = k -u n-1 = k -α(u) n-1 , so α(u) ∈ U ′ n,k
. The mapping α is then clearly a bijection between U n,k and U ′ n,k .

6. Concluding remarks 6.1. List of bijections for Entringer families. In what follows, we list all the twelve interpretations for Entringer families along with the bijections dicussed in this paper:

(1) the permutation π ∈ A n,k such that π 1 = k, (2) the encoding sequence ∆ ∈ D n,k , obtained by ∆ = ψ(π), where ψ is the bijection described in Section 2, then k is the first element read in ∆, (3) the 0-1-2 increasing tree T ∈ T n,k , obtained by T = ϕ(∆), where ϕ is the bijection described in Section 3, then k is the end-point of the main path of T , (4) the 0-1-2 increasing tree T ′ ∈ T ′ n,k , obtained by T ′ = ϕ ′ (T ), where ϕ ′ is the bijection described in [KPP94, §6], then k -1 is the father of n in T ′ , (5) the alternating permutation σ ∈ A ′ n,k , obtained by σ = θ(π), where θ is the bijection described in Subsection 4.2, then k = n + 1σ 1 + σ 2 , (6) the direct alternating permutation σ ′ ∈ DAP n,k , obtained by σ ′ = β(σ), where β is the bijection described in Subsection 4.3, then k = n + 1 -|σ 1σ 2 |, (7) the direct alternating permutation τ 1 ∈ DAP ′ n,k , obtained by τ 1 = ρ(π), where ρ is the bijection described in Subsection 4.3, then k is the term immediately before 1 (or n if τ 1 starts with 1), (8) the direct alternating permutation τ 2 ∈ DAP ′′ n,k , obtained by τ 2 = ρ ′ (τ 2 ), where ρ ′ is the bijection described in Subsection 4.3, then n + 1k is the term immediately after n (or 1 if τ 2 ends with n), (9) the G-word π ′ ∈ G n,k , obtained by π ′ = δ -1 (T ), where δ is the bijection described in Subsection 5.1, then n + 1k is the end of the route of π ′ , (10) the R-word π ′′ ∈ R n,k , obtained by π ′′ = (δ ′ ) -1 (T ), where δ ′ is the bijection described in Subsection 5.1, then n + 1k is the end of the route of π ′ , (11) the sequence u ∈ U n,k , obtained by u = γ(π), where γ is the bijection described in Subsection 5.2, then n + 1k is the last element of u, (12) the sequence v ∈ U ′ n,k , obtained by v = γ(σ) = α(u), where α and γ are the bijections described in Subsection 5.2, then k is the sum of the two last elements of v. We summarize the bijections of this paper in the diagram of Figure 4, where at the left we gather all the models in alternating permutations, and at the right we gather the models in the increasing trees. Poupard [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF] proved that t n is the number of 0-2 increasing trees (i.e. the trees in T n such that every vertex has 0 or 2 children). However, it seems that there is no interpretation à la André for t n in alternating permutations. Furthermore, let t n,k denote the number of 0-2 increasing trees such that the end-point of the main path is k, then the sequence (t n,k ) is obviously a refinement of t n as Entringer numbers for Euler numbers. Let s n (resp. s n,k ) be the number of split-pair arrangements of [n], that are arrangements σ of the multi-set {0, 0, 1, 1, 2, 2, . . . , n, n} such that σ(1) = n (resp. σ(1) = σ(k + 1) = n)

Figure 1 .

 1 Figure 1. The 0-1-2 trees on [4]

-

  Case B : if i m and j m are siblings in T , transform T with the following procedure.

Figure 2 .

 2 Figure 2. The construction of the tree Ψ(7 4 8 5 9 1 6 2 3)

Corollary 4. 5 .

 5 The sequence (DAP n,k ) 1≤k≤n is an Entringer family.

Figure 3 .

 3 Figure 3. The route of the G-word π = 82546317

Figure 4 .

 4 Figure 4. The bijections mentioned in the paper

Table 1 .

 1 The first values of Entringer numbers E n,k

Acknowledgement

This work was partially supported by the French National Research Agency under the grant ANR-08-BLAN-0243-03.

(1) π ∈ A 4,k 2 1 4 3 3 2 4 1 3 1 4 2 4 2 3 1 4 1 3 2

(2)

2 1 4 3 1 4 2 3 3 1 4 2 1 3 2 4 (1) 2 3 2 4 (1) (9) π ′ ∈ G 4,k 6 3 4 2 1 5 6 4 2 3 1 5 6 2 3 4 1 5 6 4 3 2 1 5 6 2 4 3 1 5 (10) π ′′ ∈ R 4,k 6 2 1 4 3 5 6 2 3 1 4 5 6 1 4 2 3 5 6 3 1 2 4 5 6 2 4 1 3 5

and, between the two occurrences of i in σ (0 ≤ i ≤ n -1), the number i + 1 appears exactly once.

Recently, Graham and Zang [START_REF] Graham | Enumerating split-pair arrangements[END_REF] proved that for 1 ≤ k ≤ n, s n,k = t n,k . In particular, s n = t n . There is no bijective proof between Poupard's model and Graham and Zang's model.


Guillaume Colin
email: guillaume.colin@univ-orleans.fr

Gérard Bloch
email: gerard.bloch@esstin.uhp-nancy.fr

Yann Chamaillard

Andrej Ivanco

A real time neural energy management strategy for a hybrid pneumatic engine

Keywords: energy management strategy, fuel saving, hybrid vehicle, hybrid pneumatic engine, optimal control, neural networks, dynamic programming

Various energy management strategies for a hybrid pneumatic engine are reviewed and a real time neural control strategy proposed. This Neural Network strategy learns off line the optimal control given by Dynamic Programming and the resulting control model is applied on line. The different strategies are simulated with a backward vehicle model for various driving cycles and their fuel consumptions compared. The results show that the Neural Network strategy is better than a classical Equivalent Consumption Minimization Strategy (ECMS) and equivalent to a Variable Penalty Coefficient Strategy with Driving Pattern Recognition.

INTRODUCTION

Several concepts have been recently proposed to improve the global powertrain efficiency of Internal Combustion Engines (ICE) and consequently decrease their environmental impact. Among these, the hybrid-pneumatic engine differs significantly from the well-known hybrid-electric configuration by the use of compressed air instead of electrical power. In a hybrid-pneumatic engine (Higelin et al.,

Air tank

Fig. 1. Pneumatic-hybrid scheme 2002), a traditional ICE is internally hybridized, with a built-in pneumatic motor composed of a compressed air tank linked to the combustion chamber by a supplementary pipe and an additional charging valve (see Figure 1). This allows the hybrid engine to store kinetic energy of the vehicle in the air tank without additional compressor and to restore it to produce torque. The hybrid-pneumatic engine could be considered as a parallel hybrid configuration, where both the ICE and pneumatic motor are coupled on This work was partially supported by ANR project ArHyCo, Programme "Systèmes Embarqués et Grandes Infrastructures" -ARPEGE, contract number ANR-2008 SEGI 004 01-30011459.

a single crankshaft and could work separately or together in a supercharging mode. This concept has three main advantages, leading to significant fuel saving: possibility to recuperate kinetic energy; no additional clutch, reducer or continuously variable transmission; reduction in the turbo lag during acceleration and possibility of strong engine downsizing, as studied in [START_REF] Doenitz | Realizing a concept for high efficiency and excellent driveability: The downsized and supercharged hybrid pneumatic engine[END_REF]. To implement the proposed concept it is necessary to optimize not only the pneumatic motor, but also the energy management strategy. Section 2 describes the backward vehicle model used to simulate the control strategies. These ones are summarized in Section 3: the reference given off line by Dynamic Programming, the basic Causal Strategy, the different Penalty Coefficient strategies, including Driving Pattern Recognition techniques for adapting the penalty coefficient, and the proposed Neural Network strategy, which learns off line the reference optimal control and applies it on line. Comparisons for different driving cycles are given in section 4.

VEHICLE MODEL

To simulate and compare the energy management strategies on the vehicle speed profiles of some driving cycles, backward and forward models of vehicle can be used. In the discrete time backward model used here, the desired vehicle speed is interpreted as a torque demand taking into account the models of the vehicle and power transmission. This Hybrid Pneumatic Engine model is presented in Figure 2, where the blocks refer to the equations detailed below. Firstly, from the cycle desired speed v d (m/s), the acceleration Γ (m/s 2 ) is estimated simply by:

Γ(k) = v d (k) -v d (k -1) ∆t (1) (1)
(2) (9)

(5)

(7) (3) (4) (10) (11) ) (k  ) (k v d ) (k F t ) (k gb  ) (k T e ) (k e  ) (k u mode ) (k p tank ) (k m tank  ) 1 (  k m tank ) 1 (  k p tank ) (k m fuel  Fig. 2.
Global model of the Hybrid Pneumatic Engine where ∆t (s) is the sampling period. Next, considering the forces (N) acting on the vehicle (aerodynamics F a , rolling resistance F r , wheel inertia F w ), the traction force F t is deduced from:

mΓ(k) = -F a (k) -F r (k) -F w (k) + F t (k) (2)
where m (kg) is the vehicle mass. Then the requested engine torque T e (Nm) can be obtained by:

T e (k) = F t (k) • r w ρ gb (k) •η -sign(Ft) gb +T aux (k)+T f riction (k) (3)
where the transmission chain characteristics (final reduction and gear-box ratio ρ gb ), the wheel radius under load r w (m), the gear box efficiency η gb , the auxiliary T aux and friction T f riction torques (Nm) are taken into account.

Next, the engine speed ω e (rpm) is deduced:

ω e (k) = v d (k)ρ gb (k) 30 r w π (4)
In order to compare the fuel consumptions, the gearbox switching strategy of the conventional engine mode is kept for all the energy management strategies.

The control of the produced torque is then divided in two levels. A supervisory level chooses the propulsion mode u mode in order to minimize the fuel consumption. A lowlevel controller manipulates the engine actuators in order to produce the requested torque. In all, four driving modes are considered:

• two propulsive modes u mode : pneumatic µ p and conventional µ c , • one recuperative: pneumatic pump,

• and one alternative: engine stop.

These four modes are characterized in Table 1 versus the mass flowrates of the air trapped in the tank ṁtank and consumed fuel ṁfuel and detailed further. Pneumatic propulsive mode. This mode µ p , where the intake phase is suspended, can produce torque from the compressed air, even from zero engine speed. To reduce the computation times, all the thermodynamic cycles have been recalculated in the form of a cartography shown in Figure 4, giving the consumed air mass flowrate ṁtank (k) (g/cycle):

Mode Pneumatic µp Convent. µc Pump Stop ṁtank < 0 = 0 > 0 = 0 ṁfuel = 0 > 0 = 0 = 0
ṁtank (k) = h (T e (k), ω e (k)) (7)
where the requested engine torque T e is also bounded:

T e min (p tank (k)) ≤ T e (k) ≤ T e max (p tank (k)) (8)
Indeed, the pneumatic motor mode cannot be used (e.g. for stop and start functionality) below a certain value of air-tank pressure p tank min , where the demanded torque could not be delivered. The maximal pressure depends on the compression ratio of the engine and when reached, the pumping mode quickly loses its effectiveness. Then, the tank air mass m tank (kg) is computed by integrating the tank air flowrate ṁtank : Finally, the tank pressure p tank (Pa) is deduced from:

-12 -10 -1 0 -8 -8 -8 -8 -6 -6 -6 -6 -6 -4 -4 -4 -4 -4 -4 -2 -2 -2 -2 0 0 0 .2 0.2 0.2 0.4 0.4 0.4 0.6 0.6 0.8 0.8 1 1 1. 2 1. 4 1 .6

Requested torque (Nm

θ tank (k + 1) = θ amb p tank (k + 1) p amb γ-1 γ (10) p tank (k + 1) = r m tank (k + 1)θ tank (k + 1) V tank (11)
where θ tank (K) is the tank temperature, θ amb (K) and p amb (Pa) the ambient temperature and pressure, γ the specific heat ratio, V tank (m 3 ) the air tank volume and r (J/kg/K) the perfect gas constant.

Recuperative pneumatic mode. This pumping mode is used to transform the kinetic energy from the vehicle to potential energy in the form of compressed air stored in the air-tank. Basically it is the opposite of the pneumatic propulsive mode (capturing air to the air-tank instead of releasing it). More details about the thermodynamic cycles in a pneumatic-hybrid engine could be found in [START_REF] Brejaud | Pneumatic-combustion hybrid engine: a study of the effect of the valvetrain sophistication on pneumatic modes[END_REF].

ENERGY MANAGEMENT STRATEGIES

Introduction

An energy management strategy could be considered as a decision system where the main objective is to minimize the overall fuel consumption [START_REF] Guzzella | Vehicle propulsion systems: Introduction to modeling and optimization[END_REF]. The energy management strategies can be divided into two main groups.

Offline. Knowing the cycle profile from the start to the end yields to the best possible energy savings on this cycle. This knowledge is obviously not available in real time, but it is used by Dynamic Programming to obtain the global optimal solution in order to benchmark the online energy management strategies. Online. Information about the current status of the powertrain, the past driven cycle or from on-board sensors is only available. Causal, Penalty Coefficient and Neural Network are online strategies.

A basic decision system, shown in Figure 5, is used by all the energy management strategies in the case of negative torque demand (T e ≤ 0, decceleration). On one hand, if ω e > ω idle , the chosen mode is the recuperative pneumatic pump (no dissipative vehicle breaking) possibly with classical breaking if the deceleration torque is greater than the maximum of regenerative breaking T pump max .

On the other hand, when ω e ≤ ω idle , if p tank > p tank min (minimal tank pressure to restart the engine), the engine is stopped otherwise conventional idling is engaged. Finally, if the demanded torque T e is positive, one has only to select the conventional µ c or pneumatic µ p propulsive mode, so that u mode ∈ {µ c , µ p }.

Driving cycles

Different driving cycles are used to evaluate the performance of the energy management strategies. The first one is the well known New European Driving Cycle (NEDC) which is a governmental reference for comparative evaluation of fuel consumptions. It is refered here as cycle 1. The other driving cycles used here are shown in Figure 6. The ARTEMIS cycles are selected from [START_REF] André | The ARTEMIS European driving cycles for measuring car pollutant emissions[END_REF] to give a more realistic overview of the driving conditions (Trafficjam, Urban, Road, and Highway, called here cycles 2, 3, 4, 5). Next, a reference cycle, called cycle 10, combines these ARTEMIS cycles. Finally, three other driving cycles (cycles 11, 12, 13), proposed in (Ivanco et al., 2009a), are used to validate extrapolation behavior. Let us consider, on N time steps, the non linear discrete time vehicle model described in the previous section 2:

x k+1 = f (x k , u k , w k ), k = 0, 1, ..., N -1 (12)
where the state x k is the tank pressure p tank (k), the control u k is the propulsive mode u mode (k) ∈ {µ c , µ p } and where w k includes the other inputs of the model (e.g. gear number ρ gb ). Let the cost of using a control sequence π = {u 0 , ..., u N -1 } with the initial state x 0 = x(0) be:

J π (x 0 ) = N -1 k=0 g k (x k , u k , w k ) + h N (x N ) (13)
The cost function g k is the fuel consumption of the combustion engine (5). The final cost h N (x N ) is chosen here zero for equal initial and final pressures, infinite otherwise, thus forcing a charge sustaining solution. Minimizing the cost over the set Π of all admissible control sequences gives the optimal solution:

π * = arg min π∈Π J π (x 0 ) (14)
Bellman's principle of optimality states that an optimal input trajectory for a discrete decision problem from the initial state to the final state is also optimal from the current state to the final state. Based on this, Dynamic Programming proceeds backward in time from the final state to the initial state using:

J i (x i ) = min ui g i (x i , u i , w i ) + J i+1 (f (x i , u i , w i )) (15)
An equivalent Dynamic Programming algorithm which proceeds forward in time is used here [START_REF] Bertsekas | Dynamic Programming and optimal control[END_REF].

Causal strategy

The Causal Strategy (CS) implements a rule-based control with the aim of operating the engine in a high-efficiency region. Though strongly application-dependant [START_REF] Sciarretta | Rule-based and optimal control strategies for energy management in parallel hybrid vehicles[END_REF], it can give results close to the optimal strategy. For the hybrid pneumatic engine, in addition to the common rules described above, the decision is made from the demanded torque T e , engine speed ω e and tank pressure p tank as shown on figure 7, where p tank des represents the desired air tank pressure.

Penalty Coefficient strategies

This type of strategies is often refered to as Equivalent Consumption Minimization Strategy (ECMS) [START_REF] Paganelli | Equivalent consumption minimization strategy for parallel hybrid powertrains[END_REF][START_REF] Guzzella | Vehicle propulsion systems: Introduction to modeling and optimization[END_REF]. It minimises the instantaneous consumption, but includes a chargesustaining penalty bounding the air tank pressure. The energies are compared in J/cycle, with, for the pneumatic mode:

E tank = ṁtank C p θ tank (16)
with ṁtank the compressed air mass flowrate, C p the specific heat capacity and θ tank the tank temperature, and, for the conventional mode:

E f uel = ṁfuel LCV (17)
with ṁfuel the fuel mass flowrate and LCV is the fuel Lower Calorific Value. The chosen mode is the one with the penalized lowest equivalent energy:

u mode = µ c if E tank λ > E f uel µ p else ( 18
)
where λ is the penalty coefficient. As in [START_REF] Ivanco | Energy management strategies for pneumatichybrid engine based on sliding window pattern recognition[END_REF], one can choose a Constant Penalty Coefficient (CPC) or a Variable Penalty Coefficient (VPC):

λ(k) = λ 0 - 2 p tank (k)(p max + p min ) p max -p min n (19)
illustrated in Figure 8, which avoids saturating the tank pressure. Indeed, above a certain tank pressure, no energy can be recuperated, and, under a tank pressure value, the stop mode cannot be used. Both λ in CPC and λ 0 and n in VPC have to be determined off line to obtain the best fuel saving for given driving cycles. The penalty coefficent can also be adapted on line by using a Driving Pattern Recognition (DPR) technique [START_REF] Jeon | Multimode driving control of a parallel hybrid electric vehicle using driving pattern recognition[END_REF][START_REF] Ivanco | Energy management strategies for pneumatichybrid engine based on sliding window pattern recognition[END_REF]. Several driving conditions can be listed, for example from the ARTEMIS cycles: Traffic Jam, Urban, Road and Highway. These driving patterns can be characterized by the empirical distribution of related variables, like torque demand as shown in Figure 9. Histogram-based pattern recognition is widely used for image classification or object tracking. Here, the current driving condition is recognized by comparing histograms

Neural Network energy management strategy

The Neural Network (NN) strategy, proposed here, consists in learning, from the current avalaible variables, the optimal control solution generated by Dynamic Programming and applying the learned control in real time.

As a parsimonious and flexible universal approximator, a perceptron with one hidden layer and a linear output unit is used. For a scalar function, its form is given by:

f nn (ϕ) = n k=1 w 2 k g   p j=1 w 1 kj ϕ j + b 1 k   + b 2 , (20)
where ϕ = [ϕ 1 . . . ϕ p ] T is the regression vector, the w 1 kj , b 1 k are the parameters of the n hidden neurons, the activation function g is the hyperbolic tangent, and the w 2 k , b 2 are the parameters of the output neuron. The useful regressors ϕ j are selected fairly elementary by stepwise regression for a linear model: tank pressure p tank (Pa), traction force F t (N), vehicle speed v d (m/s) and acceleration γ (m/s 2 ), gearshift ρ gb , engine speed ω e (rpm), requested torque without friction and auxiliary T e -T f riction -T aux (Nm), friction torque T f riction (Nm), auxiliary torque T aux (Nm). The outputs to be predicted, i.e. the optimal sequence given by DP, are coded by 1 for the conventional mode µ c and -1 for the pneumatic mode µ p . Training was performed by minimizing the mean squared error with the Levenberg-Marquardt algorithm. The chosen number of hidden neurons corresponds to the minimum of the fuel consumption. Finally, the control to be used on line is given by:

u mode = sign (f nn (ϕ)) (21)

RESULTS

In this section, the strategies are compared on the different cycles, with a backward model of a middle class vehicle (vehicle mass m of 1500kg, 5 speed gear box and 1.6l gasoline engine) and a sampling period ∆t = 0.5s:

• DP: Dynamic Programming (optimal) strategy The initial and final tank pressures are fixed equal (10 bar) for the DP strategy, except for the NEDC cycle, where the final pressure exceeds 10 bar, because the braking energy is always recuperated (see Figure 5) and the NEDC ends with braking (see Figure 10). This initial tank pressure is kept for the real time strategies to compare the resulting consumptions. The differences in the final pressure between all strategies are considered as negligible. Tables 2 and3 show the Fuel Consumption (FC in L/100km) and Final Pressure (FP in bar). They show that the Neural Network strategy yields to results similar to the VPC strategies and better than the Causal and CPC strategies. Figure 10 shows the tank pressure for the optimal DP strategy and the neural strategy on the European Driving Cycle (NEDC). It can be seen that the dynamics are often similar because the chosen modes are often the same as shown on figure 11. Although a precise evaluation of the computational burden and time has not been done, all the presented strategies, including the proposed one, can be used in real time.

Fig. 3 .

 3 Fig. 3. Conventional propulsive mode: fuel flowrate ṁfuel versus engine speed ω e and requested torque T e

Fig. 4 .

 4 Fig. 4. Pneumatic propulsive mode: consumed air massflow ṁtank versus pressure p tank and requested torque T e m tank (k + 1) = m tank (k) + ṁtank (k) ω e (k)∆t 120 10 3 (9)

Fig. 5 .

 5 Fig. 5. Decision tree for all strategies management

Fig. 6 .

 6 Fig. 6. Generated driving patterns

Fig. 7 .

 7 Fig. 7. Decision tree for the Causal Strategy

Fig. 8 .

 8 Fig. 8. Variable Penalty Coefficient versus tank pressure

Fig. 9 .

 9 Fig. 9. Histograms of torque demand for the reference patterns of a moving window with the reference ones, for example by correlation. Then the current penalty coefficient can be chosen as the one previously computed during the off-line optimization for the recognized driving condition, leading to the Constant Penalty Coefficient with Driving Pattern Recognition (CPC-DPR) and Variable Penalty Coefficient with Driving Pattern Recognition (VPC-DPR) strategies.

Fig

  Fig. 10. Tank Pressure (bar) for the Neural Network and Dynamic Programming strategies on the NEDC cycle

Fig. 11 .

 11 Fig. 11. Chosen mode for the Neural Network and Dynamic Programming strategies on the NEDC cycle 5. CONCLUSION We reviewed the energy management strategies for a hybrid pneumatic engine and proposed a real time neural control strategy. This Neural Network strategy learns off line the optimal control given by Dynamic Programming. Note that the presented learning is quite basic and can be enhanced. The different strategies are simulated for various driving cycles and their fuel consumptions compared. The results show that the Neural Network strategy is better than a classical Equivalent Consumption Minimization Strategy (ECMS) and equivalent to a Variable Penalty Coefficient Strategy with Driving Pattern Recognition.Although a precise evaluation of the computational burden and time has not been done, all the presented strategies, including the proposed one, can be used in real time.

Table 1 .

 1 Possible driving modes

	Conventional propulsive mode. This mode µ c involves
	a classical four-stroke combustion cycle, where the effective
	work is adjusted by acting on the air mass flow through the
	throttle. A representative quasi-static model of the engine
	consumption ṁfuel (g/cycle) is derived from test bench

Table 2 .

 2 Strategy comparison for the ARTEMIS cycles (2 to 5) and the combined cycle(10)

		Cycle	2	Cycle	3	Cycle	4	Cycle	5	Cycle	10	Average
	Strategy	FC	FP	FC	FP	FC	FP	FC	FP	FC	FP	FC
	DP	8.51	10.00	7.10	10.00	5.71	10.00	8.94	10.00	7.47	10.00	7.55
	VPC-DPR	8.65	9.73	7.27	9.37	5.76	10.96	8.96	10.97	7.52	11.82	7.63
	VPC	8.67	10.01	7.29	10.39	5.78	12.86	8.97	12.21	7.54	13.08	7.65
	NN	8.56	10.4	7.28	11.05	5.81	15.2	8.96	15.15	7.54	15.05	7.63
	CPC-DPR	9.07	13.52	7.30	8.47	5.78	10.36	8.94	10.97	7.53	11.72	7.72
	CPC	10.33	8.97	7.25	10.63	5.81	14.96	8.96	15.24	7.62	16.11	7.99
	Causal	8.91	9.80	7.53	11.75	5.86	11.42	9.02	11.18	7.61	11.59	7.79
	Conventional	14.51	-	10.41	-	6.24	-	9.10	-	8.31	-	9.71
			Cycle	1	Cycle	11	Cycle	12	Cycle	13	Average
	Strategy	FC	FP	FC	FP	FC	FP	FC	FP	FC
	DP		6.14	17.50	7.54	10.00	7.24	10.00	7.29	10.00	7.05
	VPC-DPR	6.20	19.26	7.62	10.11	7.30	12.86	7.34	10.42	7.12
	VPC	6.23	19.83	7.61	10.84	7.32	13.91	7.36	12.17	7.13
	NN		6.20	17.99	7.67	8.00	7.35	11.55	7.41	12.37	7.16
	CPC-DPR	6.28	18.58	7.72	6.50	7.35	11.30	7.40	9.66	7.19
	CPC	6.35	19.68	7.72	8.68	7.33	12.66	7.39	12.11	7.20
	Causal	6.3	18.94	7.70	12.42	7.40	14.03	7.44	14.03	7.21
	Conventional	7.31	-	8.40	-	8.14	-	8.12	-	7.99

Table 3 .

 3 Strategy comparison for the test cycles 1 (NEDC), 11, 12 and 13


Johan Montagnat

Eduardo Davila

Isabelle E Magnin

3D objects visualization for remote interactive medical applications

3D medical images produced in health centers represent tremendous amounts of data spread over different places. Automatic processing of these data often allow quantitative and repeatable measurements on large databases that are valuable for diagnosis and pathology studies. Grid technologies offer large and distributed computing power suited to medical images analysis. However, the need for human control prevent complete off-line execution of some algorithms. Interactive programs with user supervision are made difficult on a grid architecture due to the remote program execution. In this paper we propose a new framework for interactive execution of remote applications dealing with large 3D medical data sets. Our solution is both efficient and easy to use from the user point of view. It can adapt to almost any medical application requirements. The formal architecture is presented and a prototype is demonstrated.

Interactive applications

.

1. The user sends some input (interactivity result) to the

Context

For years now, health centers have been using an increasing number of digital 3D sensor for medical data acquisition [START_REF] Acharya | Biomedical Imaging Modalities: a Tutorial[END_REF], such as Computed Tomography scanners (CT), Magnetic Resonance Imagers (MRI), Positon Emission Tomography scanners (PET), Single Photon Emission Computed Tomography (SPECT), and recently 3D ultrasound devices (US). The 3D images, or time sequences of 3D images, produced represent tremendous amount of data for which manual inspection and/or processing is tedious, error prone, and subject to inter-operator variability.

In the past decade, an intensive research effort aiming at automatically analyzing 3D medical images was developed. Dedicated 3D image processing algorithms allow quantitative analysis of medical data repeatedly. They also allow mass data processing for large databases analysis as needed by epidemiological studies for instance. However, many of these algorithms still require human supervision for assessing the processing validity and for responsibility reasons. Therefore, many algorithms propose an interface for interactive visualization and guidance by a human operator [START_REF] Delingette | YAV++: a software platform for medical image processing and visualization[END_REF].

Independently, grid technologies have been developing for the past few years [START_REF] Foster | The Anatomy of the Grid: Enabling Scalable Virtual Organizations[END_REF]. The idea is to assemble a wide network of computers that can be seen from the user point of view as a single computational unit. A middleware layer provides facilities to submit jobs [START_REF] Berman | Application-level Scheduling on Distributed Heterogeneous Networks[END_REF], store data [START_REF] Chervenak | The data grid: Towards an architecture for the distributed management and analysis of large scientific datasets[END_REF], and get information from the grid while hiding the underlying grid architecture to the user and physical machines used for storage and computations. Grid technologies offer a platform with many added value for medical image processing, including: an increasing computing power for complex algorithms, such as geometrical and physiological modeling of human organs, that require large amounts of memory and processing resources; a distributed platform with shared resources for different medical partners with similar needs in their data processing; a common architecture to access heterogeneous data and algorithms for processing; and the ability to process very large amounts of data.

However, grid processing introduce some constraints on applications as they are executed on remote machines.

The work presented in this paper is developed as a contribution to the European DataGrid project (EDG) 1 although it is not limited to this architecture and it intends to provide a generic solution for interaction with remote applications. The EDG grid is made of computing units spread in different sites all over Europe (and even beyond) and a middleware layer proposing grid services. Our problem is to port interactive applications on this distributed architecture. Interactive applications have a user interface that should appear on the user interface machine while the application itself is running on a remote computing element. However, direct usage of an X client/server si not admissible for two reasons: X transmission of graphic bitmaps is network intensive (as compared to network transmission of minimal geometric information) and it is not adapted to a high degree of interactivity; 3D graphic visualization is needed and it is usually achieved locally by the user workstation graphic hardware (i.e. contrarily to [START_REF] Engel | A Framework for Interactive Hardware Accelerated Remote 3D-Visualization[END_REF] the remote machine is not supposed to have specific graphic capabilities). Specific developments of an interactive application architecture are therefore needed. The communication between the interface and the computation program should remain as transparent as possible from the programmer point of view to ease the integration of grid-aware medical image processing applications.

Section 2 details medical applications and the issues arising when porting such applications to the grid. Section 3 describes the proposed solution. Finally, section 4 gives prior results on a sample application. In the following paper, the local machine corresponds to the user workstation on which the graphic interface should appear and the remote machine corresponds to the grid computation node.

Grid-aware medical applications

3D data in medical applications

Medical image processing applications manipulate 3D images, or time sequences of 3D images, and 3D models. Most interactive application require the display of one (or more) 3D image on which is overlaid some information proper to the application (e.g. a geometrical model of an anatomical structure). For instance, figure 1 illustrates three different applications. On the left is an MRI slice showing the aorta on which is overlaid a vessel model used for the aorta segmentation. On the right is a 3D mechanical model of the heart left and right ventricles used for heart image registration (courtesy of Q.-C. Pham and P. Clarysse, CREATIS). At the bottom is diagrammed a surgery simulator composed by an interactive console (haptic device and graphic rendering) communicating with a computation server on which is stored an organ bio-physical model.

Visualization of 3D medical images in not straightforward since a user cannot at a glance visualize the interior of a 3D volume. Different visualization techniques exist that transform the original volume in a representable data. This User graphic workstation and haptic device Computing elements

Figure 1. Three interactive medical application examples (see text).

might be a single slice extracted out of the volume as illustrated in top row of figure 1 or a synthesized representation as may be obtained by surface or volume rendering techniques for example [START_REF] Bajaj | Distributed and Collaborative Volume Visualization[END_REF]. Application dependent additional information usually involve geometrical representation of some internal modeling of the data. This information is often much more compact than the complete 3D data set. Therefore, rather few information need to be exchanged between the computing machine and the graphic interface.

In the literature, many works dealing with remote data visualization are reported. Many work concern post-processed data visualization [START_REF] Lefer | A Thin Client Archietcture for Data Visualization on the World Wide Web[END_REF], while other consider interaction with the data [START_REF] Bajaj | Distributed and Collaborative Volume Visualization[END_REF]. Some of them offer asynchronous objects management and real-time constraints [START_REF] Schmidt | An overview of the Real-Time CORBA Specification[END_REF][START_REF] Kim | APIs for Real-Time Distributed Object Programming[END_REF]. However, few of them address the specific needs of medical image processing applications [START_REF] Delingette | YAV++: a software platform for medical image processing and visualization[END_REF], and optimized computing grids for solving medical problems is still an emerging field.

Data sent to algorithm

Data returned to user interface program. This step is non-blocking (no user input may be needed at some point) and might be asynchronous in some cases.

Get user input

Algorithm progression

2. The algorithm progresses taking into account the user input.

3. The updated status of the computation is displayed in the user interface to allow further evaluation/interaction with the algorithm.

Some data need to be exchanged between the algorithm and the user interface on a periodic basis in this loop: when transmitting user inputs to the algorithm and when updating the user interface to reflect the changes in the algorithm status.

Issues in porting interactive applications on grid architectures

On a grid architecture, the user is submitting jobs to the grid using the grid middleware interface. Its jobs are executed on any suitable machine composing the grid without any prior information on the selected target. The application should therefore be able to connect to the user interface in order to exchange user input and graphic information using a communication protocol. In the following section, we propose a generic architecture for interactive applications.

To obtain a high interactivity level, e.g. including realtime requirements such as needed for the surgery simulation application depicted above, communications between the program and the user interface should be as efficient as possible. For some critical applications, a guaranteed network quality of service may even be mandatory.

The communication protocol should be designed to make the user's code as independent as possible of the remote interface system. This is mandatory to ease the transcription of existing applications and to encourage new developments in the grid framework.

Remote 3D visualization and interaction framework

Our implementation is based on C++ libraries developed in our laboratory, although the proposed framework does not depend on this specific language. We first describe the local application framework as it exists on stand-alone machines and we then present its adaptation to the remote application framework.

Stand-alone application

A set of base classes is provided to ease construction of interactive medical applications. Concerning user interface, basic 2D and 3D displaying functionalities are provided as illustrated in figure 3.

Viewer Viewer

Scene

Graphic Graphic Graphic

Data

Data Data A Graphic base class is provided. It is responsible for interaction between the graphic system and the user objects. In particular, a redraw virtual method is provided to be redefined by each graphics component. This method is called each time the user interface need to be refreshed.

A Scene is composed of a list of graphic objects. A scene defines a common frame to assemble different graphic objects in space. Two different scenes represent to different worlds without interactions.

Finally, a Viewer represents a window that displays the graphic content of a scene on the screen. Several viewers may visualize a same scene with different viewing parameters. The viewers allow interaction with user objects by different means (contextual menus, mouse events forwarding...).

The graphic interface is completely disconnected from the user objects. Therefore an application does not depend on a graphic system and may be recompiled to execute offline, without interface. To achieve this, the user writes the object composing its application data separately from the graphic object (that inherits from Graphic). To each data object is associated a graphic object, but the data object has no knowledge about its graphic interface.

The application itself is made of a main loop as illustrated in figure 2. The user can interact with its data through the graphic interface. Periodically, the user input are sent to the algorithm. The algorithm progresses and then ask for an update of the scene. This causes all graphics objects to be redrawn in all windows.

Remote Visualization

In order to achieve remote visualization, the data and the graphic objects should lie on two different machines communicating together: a (local) interface program contains graphic information while a (remote) computation program contains the data. The overall architecture is diagrammed in figure 4.

On the user interface machine, a graphic daemon is waiting for connections on a given port. The user first submits an interactive job from a shell using the grid middleware interface [START_REF] Acharya | Biomedical Imaging Modalities: a Tutorial[END_REF]. Once executing, the remote process connects back to the graphic daemon of the user interface [START_REF] Armstrong | Toward a Common Component Architecture for High-Performance Scientific Computing[END_REF]. The graphic daemon then forks a new interface process (3) to handle interactions with the computational process. A communication channel is opened between the two processes (it may be a simple socket or something more sophisticated such as a CORBA bus [START_REF]Common Object Request Broker Architecture[END_REF] or CCA ports [START_REF] Armstrong | Toward a Common Component Architecture for High-Performance Scientific Computing[END_REF] to handle platforms heterogeneities).

Once the two processes have started and the communication channel is opened, the local program creates a graphic interface and enters a main loop where it iteratively processes graphic events and communication events until it receives an exit message from the computation program. The computation program sends a description of the desired interface and then enters the interactive loop that was diagrammed in figure 2.

Note that in this framework, the interface program is generic and does not depend on a precise application. The graphic interface description is sent by the computational program to the user interface. This is needed because the program may be available from the grid, without the user having to pre-install anything on its machine. The only mandatory component on the user interface is the graphic daemon on which the remote application connects. Technically, the interface may be described by different means such as using java byte code sent through the communication channel. In our implementation we rely on a platformindependent windowing system (wxWindows2 wrapped in the python3 scripting language). The script is sent through the channel and executed on the local machine.

This solution also proves to be very flexible. A program can modify its graphical interface dynamically depending on the algorithm evolution and the user interactions. There is not limitation on the generated interface induced by the system. The internal mechanism (see below) for creating the interface is completely hiding the communication layer to the user. A transparent protocol is defined to communicate graphic object rendering commands to the user interface. It eases the development of user applications and allow to run the program stand-alone or remotely without any change in the user code.

Communication protocols

When comparing the general remote visualization scheme of figure 4 with the general local application scheme of figure 3, it appears that objects should be created on different machines. Indeed, the communication channels comes between the graphic and the data objects. All viewers, scenes, and graphic objects code is executed on the local host while the data objects are part of the remote process. Figure 5 details a remote application structure.

The user program initializes an interface using a scripted description and a display parameter. The system initialization method provided connects to the given machine and the remote graphic daemon forks an interface process. Communicating objects are automatically created on both sides and communication channels are opened. For the sake of clarity, two different communication channels are opened with two different controllers. The first one is used for interface control (interface commands and interaction feedback). The second one is responsible for mapping data from remote data objects to graphic representations on the local machine.

Interface protocol

The user program first sends the interface script and can then create data and graphic objects using the standard C++ new operator. In a stand-alone application (figure 3), the user interface script is evaluated locally and the graphic objects are created on the local machine. In a remote application, the interface is sent to the local machine and the graphic object constructor causes a remote graphic object creation. The remote graphic object is identical to the local graphic object so that the user does not need to change its code whether running stand-alone or remotely. To guarantee minimal prior installation on the user workstation, the graphic object code should be sent from the remote program to the interface dynamically upon object creation. This may be done using java bytecode or dynamic libraries for instance.

An interface protocol allows the user to create or delete interfaces and objects.

The protocol itself is hidden behind standard method calls such as createInterface(interface-script.py). The underlying system exchanges pre-defined messages between the computing and the local machine Messages are interpreted and proper action executed by the interface communicator objects. Messages sent from the remote to the local machine include:

STOP. Stop computation loop.

As illustrated in figure 4, the interface communicators on the local and the remote machines periodically poll the incoming messages to respond these commands.

Graphic protocol

Whenever a viewer window needs to be refreshed (because the viewing parameters changed or the graphic window needs to be redrawn), the graphic system if the local process sends redraw events that cause the redraw method of all graphic objects to be called. This method is responsible for displaying some data and therefore needs to retrieve the data content on the remote machine. A second communication protocol is needed. These communication are blocking: all graphic objects first retrieve their needed data, then the graphic interface is updated.

Since the graphic objects on the local and the remote machine are identical, the local graphic only needs to send one INIT message to initiate data transmission. When receiving this message, the remote graphics communicator causes the remote graphic object redraw method to be called. Each time the remote object fetches some data from the data object, it uses a method that sends the retrieved information to the local host. Each time the local object fetches the same data, the it waits for the information to arrive from the remote object. This is clarified in the following simple example. Suppose that the data object is a polygonal contour. It contains an array of position vectors. The pseudo-code corresponding to the redraw method on the local and the remote host would look like: The corresponding communication diagram is shown in figure 6. The INIT message precedes the entrance into the local redraw code and causes the remote redraw code to start. Only SEND messages from the remote to the local machine are then needed. Both functions end with implicit mutual consent. From the user point of view, message exchanges are hidden in the get/send function calls. Get function calls appear exactly in the same order than send function calls. Get and send functions are defined for every primitive types or array of primitive types needed for exchanging geometrical information (language primitive types, vectors, matrices...).

On a stand-alone execution, both "local" and "remote" code are executed on the same machine. The "remote" code is first executed. To avoid the overhead of a communication channel, the send methods are redefined to push the addresses of "sent" data on a stack. The "local" code then pop the data out of the stack during the get methods. For efficiency reasons, a send function that returns a pointer on a data set acts differently when it is executed stand-alone or remotely. On a remote system, the pointed data have to be transmitted through the communication channel and therefore copied in a temporary buffer on the remote machine.

On a stand-alone execution, only the pointer to the original data is pushed on the stack thus avoiding a useless copy.

SEND(Vector

Interaction with remote applications

The user can interact with the data either by direct mouse action in the graphic window (to select a graphic object for instance) or through graphic controls (menus, buttons...). Our graphic interface proposes 4 different modes to interpret mouse actions (button press and pointer moves) occurring in a viewer window: Viewer mode. The viewing parameters are controlled by mouse motion. Selection mode. A graphic object is selected by a mouse click.

Object motion. The selected object is moved according to mouse motion. Object mode. Mouse controls are captured by the selected object for its internal use.

The viewer mode is completely handled on the local machine as viewers code is locally available.

In selection mode a mouse click selects the "closest" object from the mouse pointer. Similarly to the redraw method a distanceTo method of each graphic may be redefined by the user to determine the distance between a mouse click and each graphic object. When a mouse click occurs in a viewer window, a SELECT message is sent through the communication channel to each remote graphic object causing their distanceTo method to be evaluated on the remote node (since this method usually involve accessing the data object). Distance values are returned and the object corresponding to the minimal distance is selected.

The object motion mode similarly involves code execution on the remote machine to update the data. On the local machine, a translation vector, a scale factor, or a rotation matrix is estimated depending on the mouse motion. TRANSLATE, SCALE, and ROTATE messages are sent to the remote nodes. Data is remotely updated and a RE-DRAW message is sent back to redisplay the moved object.

When selected, a graphic object also pops up some object-related menu entries and controls. Figure 7 shows object-related controls for a 3D image renderer. These menus and controls are created by the graphic object and are therefore transmitted to the local host with the graphic object. Most menu entries and controls act directly on the graphic object parameters and are handled locally. However, some of them may cause changes to happen on the represented data. Since these changes are data dependent, it is important that the graphic communicator interface let the user define its own messages. Thus the system is extensible and the user can add any additional message he needs in its application. A new message is composed of a unique identifier (given by the graphic system on new message creation), a description of parameters to transmit, and an associated method of the remote graphic object. The associated method has a single object parameter that contains a list of transmitted parameters. When the control (menu, button...) is activated, the data to transmit are sent with the message, causing the remote method to get called on the remote node. For transparency reasons, the system proposes a single method to bind a control action with a graphic method. This method creates the new message structure in case of remote execution or simply binds the associated method with the control for direct call in case of stand-alone execution.

Graphic protocol

The graphic protocol therefore includes the following messages sent from the interface to the remote machine: INIT. To start object redraw. SELECT. To compute distance to object. TRANSLATE, SCALE, ROTATE. To modify data.

Conversely, the following messages are sent from the remote to the interface machine: SEND. To send data that need to be drawn.

Object-related menu

Object-related controls REDRAW. To force a graphic object redraw after the data has been modified.

Transparency from the user point of view

The proposed system was designed to be as transparent as possible from the user point of view, while remaining efficient. Indeed, most messages are completely hidden by the graphic system and the user programs call methods that cause the messages to be exchanged. In case of a standalone execution, the behavior of the system changes transparently for efficiency reasons. No messages are then exchanged.

The only difference with a stand-alone code from the user point of view is the need to split the redraw method in a "remote" part that sends data and a "local" part that retrieves data. Although message exchanges themselves are hidden in the get/send functions, two different methods are needed since only the "remote" part can read from the data object.

Results

This section presents preliminary results on a simple deformable contour object used for interactive segmentation of medical images. Figure 8 shows an interface similar to the one of figure 1 on which appears a graphic deformable contour overlaid on one slice out of a 3D carotid MRI. The contour and image data are stored on the remote machine. The window is grabbed from the local machine screen. The widgets at the bottom of the window are used to start and stop the segmentation algorithm.

Discussion

In this paper we presented a 3D object visualization interface for interacting with remote medical applications. The framework is generic and can indeed adapt to many different applications, even outside the medical field. The system is both efficient and transparent from the user point of view. It intends to ease the creation of medical image processing algorithms on emerging grid architectures.

Efficiency is needed to insure maximal performance in application for which interactivity may be critical (real time constraints may be needed). One purpose of grid technologies is to bring additional computing power to the user. The graphical system should therefore not compensate for the computational improvement.

It is mandatory that the system remains easy to use and as transparent as possible for the user in order to ease new algorithm developments. Our system can run stand-alone when no remote server is available without code modification or recompilation. The message exchanges are hidden from the user.

Grid technologies already raised a large interest reflected by many research works on efficient scheduling, data management, and data transmission strategies. It will play a key role in a near future for processing large amounts of data using a limited set of shared resources. The new network generation with increased bandwidth, dedicated services, and guaranteed quality of services will boost management of large and distributed collections of data. This work proposes a software architecture to efficiently process, visualize, and interact with remote 3D medical images. It makes grid technologies available for interactive medical applications.

Figure 2 .

 2 Figure 2. Interactive application general structure.

Figure 3 .

 3 Figure 3. Graphic functionalities provided to the user.

Figure 4 .Figure 5 .

 45 Figure 4. Remote interactive application general diagram (see text).

  TERMINATE. Disconnect and terminate interface program. EVALUATE. Evaluate transmitted script. CREATE. Create a new graphic object. DELETE. Delete a graphic object. Conversely, messages sent from the local to the computing machine include: TERMINATE. Disconnect and terminate computation program. READ. Read new data from a file/stream. WRITE. Write data to a file/stream. START. Start computation loop.

  void Polyon::localRedraw() { int n = getInteger(); Vector v1 = getVector(); for(int i = 1; i < n; i++) { Vector v2 = getVector(); draw(v1, v2); v2 = v1; } } void Polyon::remoteRedraw() { int n = data->getNbVertices(); sendInteger(n); for(int i = 0; i < n; i++) sendVector(data->getVertex(i)); }

Figure 6 .

 6 Figure 6. Communication messages between a local and a remote graphic object.

Figure 7 .

 7 Figure 7. Object-related menu and controls on a 3D+T medical image renderer.

Figure 8 .

 8 Figure 8. Deformable contour object overlaid on a carotid MRI slice. The data are lying on a remote machine and visualized on a local machine.

http://www.eu-datagrid.org

http://www.wxwindows.org

http://www.python.org

Acknowledgments

This work is partly supported by the European DataGrid project (http://www.eu-datagrid.org/).