Keywords: Mathematics Subject Classification. Primary 37B10; Secondary 68R15 Dynamical systems, word combinatorics, interval exchanges. 1

COMBINATORIAL METHODS FOR INTERVAL EXCHANGE TRANSFORMATIONS

S ÉBASTIEN FERENCZI ABSTRACT. This is a survey on the big questions about interval exchanges (minimality, unique ergodicity, weak mixing, simplicity) with emphasis on how they can be tackled by mainly combinatorial methods.

Interval exchange transformations, defined in Definition 1 below, constitute a famous class of dynamical systems; they were introduced by V. Oseledec [START_REF] Oseledets | On the spectrum of ergodic automorphisms[END_REF], and have been extensively studied by many famous authors; up to now, the main results in this swifly-evolving field can be found in the two excellent courses [START_REF] Viana | Dynamics of interval exchange maps and Teichműller flows[END_REF] and [START_REF] Yoccoz | Échanges d'intervalles[END_REF]. To study interval exchanges, three kind of methods can be used: by definition, these systems are one-dimensional, and the first results on them naturally used one-dimensional techniques; then the strongest results on interval exchanges have been obtained by lifting the transformation to higher dimensions and using deep geometric methods. However, many of these results have been reproved by using zero-dimensional methods; these use the codings of orbits to replace the original dynamical system by a symbolic dynamical system, as in Definition 4 below. Now, most of the existing texts, including the two courses mentioned above, focus on the geometric methods; the present survey wants to emphasize what can be achieved by the two other kinds of methods, which have both a strong flavour of combinatorics. The one-dimensional methods yield the basic results, some of which the reader will find in Section 2 below, but also the famous Keane counter-examples described in Section 4, and a very nice new result of M. Boshernitzan which is the object of our Section 6; Sections 3 and 5 are devoted to the zero-dimensional methods; the necessary definitions of word combinatorics, symbolic and measurable dynamics are given in Section 1. All those sections are also retracing the colourful history of the theory of interval exchanges, made with big conjectures brilliantly solved after long waits; thus we finish the paper by explaining in Section 7 the last big open question in the domain.

This paper stems from a course given during the summer school Dynamique en Cornouaille, which took place in Fouesnant in june 2011; the author is very grateful to the organizer, R. Leplaideur, for having commandeered it.

1. PRELIMINARIES 1.1. Interval exchange transformations. Definition 1. Let r ≥ 2. Let Λ r be the set of vectors (λ 1 , ...λ r ) in IR r such that 0 ≤ λ i ≤ 1 for all i and Σ r i=1 λ i = 1. An r-interval exchange transformation, or iet for short, is given by a vector λ ∈ Λ r and a permutation π of {1, 2, . . . , r}. The map T λ,π is the piecewise translation defined by partitioning the interval X = [0, 1[ into r sub-intervals of lengths λ 1 , λ 2 , . . . , λ r and rearranging them according to the permutation π; or, formally, T λ,π x = x + π -1 j<π -1 i λ j -j<i λ j when x is in the interval

X i = j<i λ j , j≤i λ j .
Throughout this paper, we denote T λ,π simply by T when there is no ambiguity; we call β i , 1 ≤ i ≤ r -1, the i-th discontinuity of T -1 , namely β i = π -1 j≤π -1 i λ j , while γ i is the i-th discontinuity of T , namely γ i = j≤i λ j . We shall use also γ 0 = 0, γ r = 1. Then X i is the interval [γ i-1 , γ i [.

Warning: roughly half the texts on interval exchanges re-order the subintervals by π -1 ; as it is not always clear to which half a given text belongs, we insist that the present definition corresponds to the following ordering of T X i : from left to right, T X π(1) , ...T X π(r) . It makes sense to re-order also the X i , thus defining T by two permutations π 0 and π 1 (though of course sometimes π -1 0 and π -1 1 are used...); this is done in most recent texts, such as [START_REF] Viana | Dynamics of interval exchange maps and Teichműller flows[END_REF] [34], but would not be really useful in the present combinatorial context.

Note that T λ,π is not continuous, and thus if we apply the definitions strictly (X, T λ,π ) is not a topological dynamical system; there are ways to get rid of this problem, for example by the natural coding defined in Definition 5 below; but in the present context, it is enough for us that notions like minimailty and unique ergodicity (see Definition 4 below) can be defined for interval exchanges.

v = v 1 v 2 ... if w 1 = v i , ...w k = v i+k-1 .
We say that w is a factor of v. When it is finite, we denote by N (w, v) the number of occurrences of w in v. The empty word is a factor of any v. Prefixes and suffixes are defined in the usual way. A language L is a set of words such that if w is in L, all its factors are in L, and wb is in L for at least one letter b of A. A language L is uniformly recurrent if for each w in L there exists n such that w occurs in each word of length n of L. The language L(u) of an infinite sequence is the set of all its finite factors. Definition 3. Let L be a fixed language. A word w is right special, resp. left special if there exist at least two different letters x such that xw, resp. wx, is in L. The complexity of L is the function p L which to each positive integer n associates the number of different words of length n in L. The Rauzy graph of length n of L is the graph whose vertices are the words of length n in L, with an edge w → w if there exists a word v of length n -1 such that w = av, w = vb, and avb ∈ L.

Note that the Rauzy graphs should not be confused with the Rauzy diagrams used in [START_REF] Viana | Dynamics of interval exchange maps and Teichműller flows[END_REF] [START_REF] Yoccoz | Échanges d'intervalles[END_REF] to describe the induction on interval exchanges. 1.3. Dynamical systems. Definition 4. The symbolic dynamical system associated to a language L is the one-sided shift S(x 0 x 1 x 2 ...) = x 1 x 2 ... on the subset X L of A IN made with the infinite sequences such that for every s < t, x s ...x t is in L. For a word w = w

1 ...w k in L, the cylinder [w] is the set {x ∈ X L ; x 0 = w 1 , ...x k-1 = w k }. (X L , S) is minimal if L is uniformly recurrent. (X L , S
) is uniquely ergodic if there is one S-invariant probability measure µ; then the frequency of the word w is the measure µ[w].

Starting from any dynamical system (X, T ) (in most cases, geometric in origin), we can get a symbolic dynamical system: Definition 5. For a transformation T defined on a set X, partitioned into X 1 , ... X r , and a point x in X, its trajectory is the infinite sequence (x n ) n∈IN defined by

x n = i if T n x falls into X i , 1 ≤ i ≤ r.
The language L(T ) is the set of all finite factors of its trajectories. The coding of (X, T ) by the partition {X 1 , ...X r } is the symbolic dynamical system (X L(T ) , S). The natural coding of an r-interval exchange is its coding by the partition into the intervals X i , 1 ≤ i ≤ r defined above.

If the transformation T is minimal (i.e. every orbit is dense), all its trajectories have the same finite factors, and the language L(T ) is uniformly recurrent; the special words depend on the language and not on the individual trajectories; thus they are defined by any trajectory of T . If there is no periodic orbit, every word w is a factor of a bispecial word; hence the bispecial words determine the finite factors of the trajectories, and thus the symbolic dynamical system (X L(T ) , S).

If (X L(T ) , S) is the natural coding of an interval exchange T λ,π , it is not topologically conjugate to ([0, 1[, T λ,π ), but it shares all its properties of minimality and unique ergodicity, and any invariant measure for one of these systems can be carried to the other one. Definition 6. The induced map of any transformation T on a set Y is the map y → T r(y) y where, for y ∈ Y , r(y) is the smallest r ≥ 1 such that T r y is in Y (in all cases considered in this paper, r(y) is finite). Definition 7. Let (X, T, µ) be a finite measure-preserving dynamical system. It is ergodic if every invariant subset A (i.e. such that µ(T -1 A∆A) = 0) is trivial, i.e. has zero or full measure.

A complex number θ is an eigenvalue of T (denoted multiplicatively) if there exists a nonconstant f in L 2 (X, I C) such that f • T = θf in L 2 (X, I C); f is then an eigenfunction for the eigenvalue θ. θ = 1 is not an eigenvalue iff T is ergodic. T is weakly mixing if it has no eigenvalue.

We shall use the famous ergodic theorem, attributed to Birkhoff (1931) though the Russian school prefers to call it the Khinchin theorem:

Proposition 1. If (X, T, µ) is ergodic, g a function in L 1 (X), then when N → +∞ 1 N N -1 n=0 g • T n → µ(g) in L 1 and
almost everywhere. Definition 8. In (X, T, µ), a (Rokhlin) tower is a collection of disjoint measurable sets called levels F , T F , . . . , T h-1 F .

MINIMALITY

The question of minimality of interval exchanges is an old one, for which we find useful to give a quick reminder. The following fundamental lemma is proved in [START_REF] Keane | Interval exchange transformations[END_REF] and [START_REF] Katok | Standardness of automorphisms of transposition of intervals and fluxes on surfaces[END_REF]; note that it was first stated as an independent lemma in [START_REF] Katok | Interval exchange transformations and some special flows are not mixing[END_REF], but with the improved, though unfortunately false, bound r + 1.

Lemma 2. The induced map U J of an r-interval exchange T on an interval J is an s-interval exchange for some s ≤ r + 2.

Proof We look at the (at most) r + 1 points made by the γ i and the two endpoints of J; if x is any of these points, let s(x) be the largest negative integer s such that T s x is in the interior of J; we partition J by the (at most) r + 1 points T s(x) x. Then on each of these (at most) r + 2 intervals U J is continuous and is of the form T j for a constant j. Definition 9. T λ,π satisfies the i.d.o.c. property [START_REF] Keane | Interval exchange transformations[END_REF] if the negative orbits of the discontinuity points γ i , 1 ≤ i ≤ r -1, are infinite and disjoint.

Proof

We show first that there is no periodic point: if T m x = x, let b be the T n γ j nearest to x on the left, for 0

≤ j ≤ r -1, 0 ≤ n ≤ m -1. Then T m b = b as each T i , 1 ≤ i ≤ m -1, is an isometry on [b,
x]; this contradicts the i.d.o.c. unless b = T a 0, and 0 is itself an image of a discontinuity if π1 = 1, while π1 = 1 contradicts also the i.d.o.c. (in different ways, depending whether π2 = 2, or π2 = 2 and π3 = 3, etc...).

Given an interval J, we make the induction castle of J: J is partitioned into s subintervals J t ,

1 ≤ t ≤ s, the T j J t , 1 ≤ t ≤ s, 0 ≤ j ≤ h t -1, are disjoint intervals, T ht J t = U J J t ⊂ J. Let Y be ∪ 1≤t≤s ∪ 0≤j≤ht-1 T j J t ;
Y is a union of intervals, let G be the union of their left ends. Then T Y = Y , and for x ∈ G, either T x ∈ G or x = γ j for some 0 ≤ j ≤ r -1. Because G is finite and T aperiodic, for all x ∈ G there exists n such that T n x = γ j for some 0 ≤ j ≤ r -1. Similarly for x ∈ G, either T -1 x ∈ G or T -1 x = β j for some 1 ≤ j ≤ r -1, and there exists m such that T -m x = β j for some 1 ≤ j ≤ r -1. The only possibility for x which does not contradict the i.d.o.c. is x = γ 0 , thus Y = X. Now if the orbit of x is not dense, its closure does not intersect an interval J, which contradicts the fact that the induction castle of J fills X.

It is well known and proved in [START_REF] Keane | Interval exchange transformations[END_REF] that, if the permutation π is irreducible (π{0, ...l} = {0, ...l} if l = r), then total irrationality (the λ i satisfy no rational relation except Σλ i = 1) implies the i.d.o.c. condition. But the i.d.o.c. condition is strictly weaker than total irrationality: for three intervals it means that λ 1 and λ 2 do not satisfy any rational relation of the forms pλ 1 + qλ 2 = p -q, pλ 1 + qλ 2 = p -q + 1, or pλ 1 + qλ 2 = p -q -1, for p and q integers. Also, the i.d.o.c. condition is not equivalent to minimality, here is a counter-example from [START_REF] Viana | Dynamics of interval exchange maps and Teichműller flows[END_REF]:

k = 4, π = (4321) (i.e. π1 = 4, π2 = 3, etc...), λ 1 = λ 3 , λ 2 = λ 4 , λ 1 λ 2 = λ 3 λ 4 is irrational. The i.d.o.c
. condition ensures that each trajectory u is uniformly recurrent, (X u , S) is minimal, and the language L(u) is the same for all the trajectories. Proposition 4. The language of the natural coding of an r-interval exchange satisfying the i.d.o.c. condition has complexity (r -1)n + 1 for all n ≥ 0.

Proof The cylinder [w 1 ...w n ] is the set ∩ n-1 i=0 T -i X w i+1
. By induction on n, these are either empty sets or intervals, and the partition of X into nonempty cylinders of length n is the partition of X by the points T -i γ j , 1 ≤ j ≤ r -1, 0 ≤ i ≤ n -1. The i.d.o.c. condition ensures that all these points are different.

Note that the left special words of length n are the prefixes of length n of the trajectories of the β i , 1 ≤ i ≤ r -1. Thus when n is large enough, there are r -1 left special words of length n, with two extensions for each one -and the same for right special words by looking at T -1 .

INVARIANT MEASURES

The question of unique ergodicity was the first big problem to be considered for interval exchanges; before tackling it, we look at what information can be obtained, by purely combinatorial considerations, on invariant measures for interval exchanges. A similar study on more general classes of systems can be found in [START_REF] Ferenczi | Infinite words with uniform frequencies, and invariant measures[END_REF].

We shall need first the fundamental

Lemma 5. p L (n + 1) -p L (n) = Σ w∈RSn (#D(w) -1)
where RS n is the set of right special words of length n and D(w) is the set of letters a such that wa is in L.

Proof p L (n + 1) = Σ w∈Ln #D(w), thus p L (n + 1) -p L (n) = Σ w∈Ln (#D(w) -1), and #D(w) -1 = 0 whenever w is not in RS n .
A consequence of Lemma 5 is a famous result of M. Morse and G. Hedlund [START_REF] Morse | Symbolic Dynamics[END_REF]:

Proposition 6. If p L (n) ≤ n for at least one n, then L is the union of a finite number of L(u j )
where each infinite sequence u j is ultimately periodic, (namely, there exist positive integers n j and t j such that u j n+t j = u j n for all n > n j ), and p L (n) is bounded. Proof Then either p(1) = 1 or there exists m with p(m + 1) = p(m). There is no right special word of length m, and a loop in each connected component of the Rauzy graph.

The following proposition is the first of many contributions from M. Boshernitzan to this survey: Proposition 7. [3] A minimal symbolic system such that p(n + 1) -p(n) = r for all n has at most r -1 ergodic invariant measures.

Proof

We begin by showing that there are at most r invariant measures. By Lemma 5, for each n there are at most r right special words of length n; we denote them by d n,1 , ...d n,r , possibly with repetitions.

For a word w, we define

ν n,i (w) = lim t→+∞ N (w,d t n,i )
t|d n,i | . By taking subsequences, we ensure the ν n,i converge to a probability µ i on X L , 1 ≤ i ≤ r.

We remark that if n is large enough every word in L of length at least (r + 2)n contains one of the d n,i , because, in such a word, words of length n can occur at (r + 1)n places at least, hence the words at two of these occurences must be equal, and if there is no right special words among them this creates a loop in the Rauzy graph thus X L contains ultimately periodic sequences, which is impossible for a minimal system of complexity rn + s.

Let µ be an ergodic invariant probability on X L . By the ergodic theorem, we choose an x ∈ X L such that for every w ∈ L, µ([w]) = lim t→+∞ N (w,x 0 ...x t-1 ) t

. We fix n and cut x into disjoint words of length (r+2)n, each of which contains a d n,i .Thus there exists t(n) such that d n,t(n) occurs in the j-th word for a set of j of upper density at least 1 r , and we choose t such that t(n) = t for infinitely many n. For those n and m large, N (w, x 0 ...x m(r+2)n-1 ≥ m 2r N (w, d n,t ). Dividing by the lengths and letting m then n tend to infinity we get µ([w]) ≥ 1 2r(r+2) µ t ([w]). Thus µ = cµ t + (1 -c)µ for some positive measure µ and, as ergodic measures are extremal, µ = µ t .

To improve the bound, we notice that if for infinitely many n there are at most r -1 right special words of length n, the above reasoning implies that there are at most r -1 ergodic invariant measures. Thus we can assume that for each n large enough there are exactly r right special words, and thus by Lemma 5 each of them can be extended by two letters only. We shall show now that there exist K and 1 ≤ j ≤ r such that for infinitely many n every word in L of length at least Kn contains one of the d n,i , i = j; then again the above reasoning implies our result.

Indeed, we suppose the above assertion is not satisfied; then for every j, and n large enough, there is a path in the Rauzy graph of length n, going from d n,j to d n,j , not meeting any d n,i except at the two ends; by minimality and because there are only two letters extending d n,j , this is the only path satisfying these conditions, and our hypothesis implies that it can be followed q n,j times consecutively, with q n,j tending to infinity with n. By following this path, we define a word g n,j such that d n,j g n,j begins and ends with d n,j , with no other occurrence of any d n,i , and the word g q n,j n,j occurs in L; our hypothesis implies also that q n,j |g n,j | n tends to infinity with n. If we take q n,j maximal, then g q n,j -1 n,j is right special, thus is identified with some d n 1 ,i ; by unicity of the path, g n 1 ,i is identified with g n,j , thus q n 1 ,i with q n,j ; but then

q n 1 ,i |g n 1 ,i | n 1 ≤ q n,j
q n,j -1 is smaller than 2 for some arbitrarily large n 1 , which contradicts our hypothesis. This result is not optimal: the hypothesis can be weakened [START_REF] Boshernitzan | A unique ergodicity of minimal symbolic flows with linear block growth[END_REF], and the optimal bound for the number of invariant measures for an rinterval exchange is [ r 2 ] [17] [START_REF] Veech | Interval exchange transformations[END_REF]. But it is enough for our purpose, as it implies that, under the i.d.o.c. condition, three-interval exchanges are uniquely ergodic, and four-interval exchanges have at most two invariant ergodic measures.

Note that unique ergodicity is a strong notion, because of the following classic result, which is stronger than the ergodic theorem and has a simple proof: Proposition 8. If (X, T ) is uniquely ergodic, µ its invariant probability measure, g a continuous function on X, then when N tends to +∞

1 N N -1 n=0 g • T n → µ(g) uniformly.
Proof Otherwise, there exist δ > 0, f continuous, a sequence n k → +∞ and a sequence of points x n k such that

1 n k n k -1 n=0 g(T n x) -µ(g) > δ.
By compacity, there exists a subsequence m k of n k such that for every continuous g,

lim k→+∞ 1 m k m k -1 n=0 g • T n
exists and defines a measure ν. ν is then a T -invariant probability, hence ν = µ, which contradicts the assumption.

KEANE'S COUNTER-EXAMPLES

It was conjectured by M. Keane [START_REF] Keane | Interval exchange transformations[END_REF] that the i.d.o.c. condition implies unique ergodicity for every r; when it was made this conjecture had already been disproved by W. Veech [START_REF] Veech | Strict ergodicity in zero dimensional dynamical systems and the Kronecker-Weyl theorem mod. 2[END_REF]. Veech's counter-example was a five-interval exchange. Then Keane [START_REF] Keane | Non-ergodic interval exchange transformations[END_REF] lowered the number of intervals required for a counter-example to four, which is optimal in view of Proposition 7. But his paper uses very different techniques, and there appear for the first time two ideas which were to be named and systematically studied later: one is the induction, a different form of which will give the Rauzy induction and is the starting point of the geometric methods; the other one is the use of matrices for adic systems.

The remainder of this section is an adapted version of [START_REF] Keane | Non-ergodic interval exchange transformations[END_REF], where some proofs have been expanded and some terminology updated. Lemma 9. Let T be the 4-interval exchange with vector (λ 1 , ...λ 4 ) and permutation π sending

1 → 4, 2 → 2, 3 → 1, 4 → 3 (denoted by (4213)). Suppose • λ 1 < λ 4 < λ 3 , λ 4 < λ 1 + λ 2 , • for 1 ≤ k < m T k-1 [γ 1 , β 1 [⊂ X 2 , then T m-1 [γ 1 , β 1 [ ⊂ X 2 and T m-1 [γ 1 , β 1 [⊂ X 2 ∪ X 3 , • for 1 ≤ k < p T k [γ 2 , γ 2 +λ 4 [⊂ X 3 , then T p [γ 2 , γ 2 +λ 4 [ ⊂ X 3 and T p [γ 2 , γ 2 +λ 4 [⊂ X 3 ∪X 4 .
Then the induced map U of T on [γ 3 , 1[ is a 4-interval exchange on an interval of length λ 4 , with permutation (2431) and vector (λ 4 , λ 3 , λ 2 , λ 1 ) such that, if λ = (λ 1 , λ 2 , λ 3 , λ 4 ), then λ = A m,p λ , where m and p are nonnegative integers and A m,p is the matrix

    0 0 1 1 m -1 m 0 0 p p p -1 p 1 1 1 1     .
Proof We make the induction castle of X 4 = [P 0 , P 4 [.

Let P 2 = T -1 γ 1 ; by T , [P 0 , P 2 [ goes to [0, γ 1 [= X 1 , which goes by T to [β 2 , β 3 [⊂ X 3 .
On the right of the picture,

T [P 2 , P 4 [= [γ 1 , β 1 [⊂ X 2 . Let P 3 = T -m γ 2 , thus m is the smallest k such that T -k γ 2 is in ]P 2 , P 4 [. For 1 ≤ k < m T k [P 2 , P 4 [⊂ X 2 , then T m [P 2 , P 3 [= [T m P 2 , γ 2 [⊂ X 2 , which is further sent by T to [T m+1 P 2 , β 2 [⊂ X 3 , while T m [P 3 , P 4 [= [γ 2 , T m P 4 [⊂ X 3 . Note that T m+1 P 2 = T m P 4 as the image of γ 1 to the right is β 1 . Thus J = [γ 2 , γ 2 + λ 4 [ is the union of the successive intervals T m [P 3 , P 4 [, T m+1 [P 2 , P 3 [, T 2 [P 0 , P 2 [. And P 1 = T -p-2 γ 3 is thus in ]P 0 , P 2 [. Then p is the smallest k such that T -k γ 3 is in ]γ 2 , γ 2 + λ 4 [, J, ...T p-1 J are in X 3 while T p [γ 2 , T 2 P 1 [⊂ X 3 , T p [T 2 P 1 , γ 2 + λ 4 [⊂ X 4 , and finally T p+1 [γ 2 , T 2 P 1 [⊂ X 4 .
Thus we know the induced map U on X 4 : on Let λ 4-i be the length of the interval [P i , P i+1 [; then we get the required matrix equality, because, for example, the images T i [P 3 , P 4 [, of length λ 1 , are in X 2 m -1 times then in X 3 p times before returning to X 4 , etc...

[P 0 , P 1 [ U = T p+3 , on [P 1 , P 2 [ U = T p+2 , on [P 2 , P 3 [ U = T m+p+1 ,

Lemma 10.

Let Ω be the open positive cone in IR 4 . Then for any pair of positive integers (m, p) and any vector λ ∈ A m,n Ω, there exists a unique λ such that λ = A m,p λ , and T λ,π satisfies all the requirements of Lemma 9 with these values of m and p.

Proof

We check that A m,p is of determinant one and maps Ω into Ω, and the matrix equality implies the conditions on the lengths.

Lemma 11. For every infinite sequence of matrices

A m k ,p k , the set ∩ k∈IN A m 1 ,p 1 ...A m k ,p k Ω is nonempty.

Proof

We check that any product of two successive A has all its entries strictly positive. Let Ω be the closed positive cone in IR 4

, K n = A m 1 ,p 1 ...A mn,pn Ω, K n = A m 1 ,p 1 ...A mn,pn Ω, K n = K n \ {0}; we have K n ⊂ K n ⊂ K n . But if v is in Ω with at least one strictly positive coordinate, then A m n-1 ,p n-1 .A mn,pn v is in Ω, thus ∩ n≥1 K n = ∩ n≥1 K n \ {0} = ∩ n≥1 K n .
Also, each K n is invariant by v → λv for any scalar λ, thus the K n are decreasing compact sets in a projective space, thus their infinite intersection is non-empty; thus ∩ n≥1 K n is non-empty. Proposition 12. Let E be the set ∩ k∈IN A m 1 ,p 1 ...A m k ,p k Ω normalized by λ 1 + ...λ 4 = 1. For every λ ∈ E, there exists a decreasing sequence of intervals J k such that the induced map U k of the four-interval exchange T λ,π on J k is the four-interval exchange T λ (k) ,π (after renormalization, and with reversed order if k is odd), with

λ = A m 1 ,p 1 ...A m k ,p k λ (k) .
T λ,π is minimal if the first coordinate of λ (2k+1) or the last coordinate of λ (2k) tend to 0 when k → +∞.

Proof

When we renormalize and reverse the order of the intervals the induced map U of Lemma 9 is exactly T λ ,π , and we iterate the construction. At each stage, the induction castle (for T ), of J k fills all the space, thus if it is made of small intervals we can make the reasoning of Proposition 3 to prove minimality. Proposition 13. For any λ in E, the trajectories of T λ,π are adic words. Namely there exist finite words B n,1 , . . . , B n,4 such that, for all n, all the trajectories are infinite concatenations of B n,i , with

• B 0,i = i, 1 ≤ i ≤ 4,
• for each 1 ≤ i ≤ 4, there exist an integer t(n, i) > 0, and t(n, i)

integers 1 ≤ k s (n, i) ≤ 4 such that B n,i = Π t(n,i) s=1 B n-1,

ks(n,i)

The matrix A mn,pn has on its i-th line, 1 ≤ i ≤ 4, and j-th column, 1 ≤ j ≤ 4, the number of 1 ≤ s ≤ t(n, j) such that k s (n, j) = i.

Each point µ in the set ∩ k∈IN A m 1 ,p 1 ...A m k ,p k Ω normalized by µ 1 +...µ 4 = 1, defines an invariant probability measure on ([0, 1[, T λ,π ) such that µ(X i ) = µ i ; every invariant probability measure on ([0, 1[, T λ,π ) is of that form.

Proof

For 1 ≤ i ≤ 4 we define F n,i to be the subinterval of J n labelled i in the definition of U n . By construction, for each given n, the T j F n,i , 1 ≤ i ≤ 4, 0 ≤ j ≤ |h n,i | -1 form a partition of [0, 1[ into k Rokhlin towers; these partitions are increasing (the atoms of the n + 1-th partition are subsets of atoms of the n-th partition), and, except possibly for a countable number of points, two points belonging to the same atom of the n-th partition for every n are the same; we say that the system ([0, 1[, T λ,π ) is of rank at most 4. Moreover, if x ∈ F n,4 , resp F n,3 , resp. F n,2 , resp. F n,1 , the nonnegative trajectory of x under U n-1 , for the natural coding given by Proposition 12, begins with 413 pn+1 , resp. 413 pn , resp. 42 mn 3 pn , resp. 42 mn 3 pn-1 . By iterating this process, if x ∈ F n,i , the nonnegative trajectory of x under T begins with a word denoted by B n,i . It follows from the definitions that F n-1,i is a union of images by T of the F n,j , 1 ≤ j ≤ k, and thus the B n,i are made by the above concatenation rules, and we check the matrix. This is enough to ensure that a measure on [0, 1[ is determined by its values on the atoms of these partitions, thus, if it is T -invariant, by its values on the F n,i . We check also that if v n = (µ(F n,1 ), ...µ(F n,k )), we get v n-1 = A mn,pn v n . Thus the measure µ is completely determined by the vector v 0 . Proposition 14. If p 1 ≥ 9 and 3(p n + 1) ≤ m n ≤ 1 2 (p n+1 + 1) for all n, T is minimal and not uniquely ergodic.

Proof

The condition of minimality is satisfied as p n → +∞ and every coordinate of λ n is smaller than

1 pn-1 .
We define M n = A mn,pn , Mn x = Mnx |Mnx| where |y| = 4 i=1 y i . Let Bk be the mapping M1 . . . Mk . We note that for i = 1 or i = 4, and any x,

(M n x) i ≤ 1 while |M n (x)| ≥ p n + 1 thus ( Mn x) i ≤ 1 pn+1 .
Suppose 2m n ≤ p n+1 + 1 for all n and let e 3 = (0, 0, 1, 0); we prove that then for n ≥ 1, ( Bn e 3 ) 3 ≥ 1 -3 p 1 +1 . Let x k+1 = e 3 , x j-1 = M j-1 x j , for 2 ≤ j ≤ k + 1; then, in view of the previous result, it is enough to prove that x j 2 ≤ 1 p 1 +1 for j = 1, and we shall prove it by induction on j ; this is true for j = k + 1, and under the induction hypothesis

x j 2 = (m j -1)x j+1 1 + m j x j+1 2 p j + 1 + (m j -1)x j+1 1 + m j x j+1 2 + x j+1 4 ≤ 2m j (p j + 1)(p j+1 + 1) ≤ 1 p j + 1 .
Suppose m n ≥ 3(p n + 1) and let e 2 = (0, 1, 0, 0); we prove now that for n ≥ 1, ( Bn e 2 ) 2 ≥ 1 3 . This is done in the same way as in the previous paragraph, by defining a sequence x i , with the induction hypothesis x j+1

2 ≥ 1 3 ,
We define now µ by a vector which is a limit (on a subsequence) of the A m 1 ,p 1 ...A m k ,p k e 2 , and ν in the same way with A m 1 ,p 1 ...A m k ,p k e 3 . Then if µ = ν, it would give measure at least 1 -3 n 1 +1 to the set X 3 and at least 1 3 to the set X 2 which is a contradiction as soon as n 1 ≥ 9.

These examples can satisfy the requirement of total irrationality, which was not satisfied by Veech's examples: it is proved in [START_REF] Keane | Non-ergodic interval exchange transformations[END_REF] that for any given hyperplane H we can find sequences (m n , p n ) satisfying the conditions of Proposition 14 and such that ∩ k∈IN A m 1 ,p 1 ...A m k ,p k Ω does not intersect H, and we can avoid a countable family of hyperplanes.

Keane's examples have been generalized to any number r ≥ 4 of intervals by J.-C. Yoccoz [START_REF] Yoccoz | Échanges d'intervalles[END_REF].

There is a duality between the lengths of the intervals and the values of the invariant measures on them: with the notations of Section 4, for any λ ∈ E, every invariant probability measure on ([0, 1[, T λ,π ) is defined from a vector µ ∈ E by giving measure µ i to the i-th interval. Under the above conditions on the m k , p k , E is not reduced to a point but is a segment, whose two endpoints give the two invariant ergodic measures. If we choose λ to be in the interior of this segment, these two ergodic measures are absolutely continouous with respect to the Lebesgue measure but different from it; if we choose λ to be an endpoint, one ergodic measure is the Lebesgue measure and the other one is singular; a recent work of J. Chaika [START_REF] Chaika | Hausdorff dimension for ergodic measures of interval exchange transformations[END_REF] has proved that this singular measure can have a support of arbitrarily small Hausdorff dimension.

UNIQUE ERGODICITY AFTER BOSHERNITZAN

We call m the normalized Lebesgue measure on Λ r , and ρ the Lebesgue measure on [0, 1[. Theorem 15. For a given irreducible π, T λ,π is uniquely ergodic for m-almost every λ ∈ Λ r .

This result was the first big conjecture on interval exchanges, stated as a question by M. Keane in [START_REF] Keane | Non-ergodic interval exchange transformations[END_REF] and proved independently by W. Veech [START_REF] Veech | Gauss measures for transformations on the space of interval exchange maps[END_REF] and H. Masur [START_REF] Masur | Interval exchange transformations and measured foliations[END_REF]. The proofs of Veech and Masur use elaborate geometric methods; but a later proof of M. Boshernitzan uses mainly combinatorial methods; it is published in [START_REF] Boshernitzan | A condition for minimal interval exchange maps to be uniquely ergodic[END_REF] but can be simplified (and made purely combinatorial) by using [START_REF] Boshernitzan | A condition for unique ergodicity of minimal symbolic flows[END_REF]. Thus we give here this simplified proof, with an updated vocabulary: in particular, the Rauzy graphs are used without being named im [START_REF] Boshernitzan | A condition for minimal interval exchange maps to be uniquely ergodic[END_REF], and as far as we know this is the first published paper where they are mentioned. Definition 10. Let (X L , S) be a minimal symbolic system. If µ is an S-invariant probability measure, for each natural integer n, we denote by e n (S, µ) the smallest positive measure of the cylinders defined by words of length n of L. Proposition 16. [START_REF] Boshernitzan | A condition for unique ergodicity of minimal symbolic flows[END_REF] If for some invariant probability measure µ, ne n (S, µ) does not tend to 0 when n tends to +∞, then the system (X L , S) is uniquely ergodic.

Proof

Then for infinitely many n we have e n ≥ a n and thus p(n) ≤ (C -1)n, thus lim inf n→+∞ p(n) -Cn = -∞. Thus on a subsequence p(n+1)-C(n+1) ≤ p(n)-Cn and p(n+1)-C(n+1) ≤ 0. On this subsequence we have both p(n) ≤ p(n + 1) ≤ C(n + 1) ≤ C n for n large enough and p(n + 1) -p(n) ≤ C thus at most C right special words. By the reasoning of the first part of the proof of Proposition 7 we conclude that there is a finite number of ergodic invariant measures.

Thus if (X L , S) is not uniquely ergodic there are two invariant ergodic measures µ i and a finite word w such that µ

1 [w] < µ 2 [w] and in the interval ]µ 1 [w], µ 2 [w][ there is no ν[w] for ν any ergodic invariant measure. We fix µ 1 [w] < t < s < µ 2 [w]. Let E n = {x; N (w,x 0 ...x n-1 ) n ∈]t, s[}. As N (w,x 0 ...x n-1 ) n → ν[w] ν-almost everywhere, we get ν(E n infinitely often) = 0, thus ν(E n ) → 0 when n → +∞, thus also µ(E n ) → 0 by convex combination.
By genericity, we choose x and y such that N (w,x 0 ...x n-1 ) n < t < s < N (w,y 0 ...y n-1 ) n for n large enough. We choose in the Rauzy graph of length n a path from x 0 ...x n-1 = v 1 to y 0 ...y n-1 = v p , through v i , 2 ≤ i ≤ p-1; it exists by minimality and can be chosen of minimal length thus without loops.

Then

|N (w, v i ) -N (w, v i+1 )| ≤ 1.
To go from below tn to above sn by moving by 1 at a time, we need to be at least n(s -t) -2 times between tn and sn. Thus [v i ] is in E n for at least n(s -t) -2 values of i, and the v i are all distinct. We get µ(E n ) ≥ (n(s -t) -2)e n and thus ne n → 0, contradiction.

For a given interval exchange T λ,π , the Lebesgue measure ρ on the interval [0, 1[ defines an invariant measure ρ for its natural coding (X u , S), and we denote by e n (T λ,π ) the quantity e n (S, ρ ) defined for this symbolic system.

Proposition 17. [2] Let U n, be the set of λ ∈ Λ r such that e n (T λ,π ) ≤ n . If is small enough, m(U n, ) ≤ 3r 3 .

Proof

Let G n (λ) be the Rauzy graph of length n of the language of T λ,π . As the complexity of any trajectory is (r -1)n + 1, by Lemma 5 G n has at most 3r -3 branches, as a branch starts at a left or right special factor, and there are at most respectively r -1 and 2r -2 in each case.

We recall that ψ is a weight function on a graph if it is positive on each vertex, the sum of its values on vertices in 1, and it can be extended to the edges such that for every vertex ψ(w) = incoming edges ψ(e) = outcoming edges ψ(e).

We define a function ψ λ on the vertices of G n (λ) by associating to the vertex w 1 ...w n the measure of the cylinder, ρ[w 1 ...w n ]; ψ λ is a weight function on the graph G n (λ), and the weight of an edge w 1 ...w n+1 is also ρ[w 1 ...w n+1 ].

We fix now a Rauzy graph G of length n; let Λ(G) be the set of λ ∈ Λ r such that G n (λ) = G. For a given word w = w 1 ...w n , ψ λ (w 1 ) is just λ w 1 ; for all λ ∈ Λ(G), all the Rauzy graphs G i (λ), 1 ≤ i ≤ n, are fixed, and determine the way the measures of cylinders of length i + 1 are computed from those of length i, through the defining equalities of the weight function ψ λ on G i (λ); thus the numbers ψ λ (w 1 ...w i ), 1 < i ≤ n can be computed inductively; they depend linearly on λ. Because T λ,,π preserves the measure ρ, ψ λ (w 1 ...w n ) = ψ λ (w 1 ...w n ) if w 1 ...w n and w 1 ...w n are on the same branch of G; hence, for fixed λ, ψ λ (w 1 ...w n ) takes 1 ≤ t ≤ 3r -3 values, which we denote by φ 1 (λ), ..., φ t (λ); the φ j are linear functionals, e n (T λ,π ) is just the smallest of the φ j (λ), 1 ≤ j ≤ t. Furthermore, again through the defining equalities of the successive weight functions on G i (λ), we can retrieve λ from the values ψ λ (w) on all the vertices of G; thus Λ(G) is a convex set and every weight function ψ on G yields a λ ∈ Λ(G) such that ψ λ = ψ.

We want to estimate the measure m({λ ∈ Λ(G); φ i (λ) ≤ n }); for this, we use a general result for which we refer the reader to [START_REF] Boshernitzan | A unique ergodicity of minimal symbolic flows with linear block growth[END_REF], Corollary 7.4: If φ is the restriction of a linear functional to a convex set K of dimension d, taking values between 0 and A, then, if V denotes the volume,

V (π -1 [0, B[) ≤ dB A V (K).
We apply it with K = Λ(G), restricting ourselves to those with m(Λ(G)) > 0, φ = φ i , B = n ; the dimension is r -1, the volume is the Lebesgue measure; we need an estimate on A; for this, we claim that for each vertex s of G, there exists a weight function such that ψ(s) ≥ 1 rn . To do this, we choose a λ ∈ Λ(G) such that T λ,π is minimal, which is possible as m(Λ(G)) > 0; this implies that G is strongly connected and thus we can find a loop s 0 → ..s k → s 0 in G; by taking it of minimal length, we ensure it has no repetition. Then we define ψ to be 1 k+1 on the s i and 0 on the other vertices; ψ is not a weight function as it may be 0 on some vertices, but ψ = (1 -δ)ψ + δψ λ is a weight function, and as k ≤ (r -1)n + 1 we can choose δ such that our claim is proved.

Thus we have A ≥ 1 rn , and thus, for all G with m(Λ(G)) > 0 and hence for all G,

m({λ ∈ Λ(G); φ i (λ) ≤ n }) ≤ (r -1)r m(λ(G)).
As t ≤ 3r -3,

m({λ ∈ Λ(G); min 1≤i≤t φ i (λ) ≤ n }) ≤ 3(r -1) 2 r m(λ(G)),
which implies the proposition.

Proof of Theorem 15 For small 0 < and n ≥ 1, we put V n, = Λ r \ U n, , and

V = ∩ N ≥1 ∪ n>N V n, ∩ {λ; T λ,π i.d.o.c.}.
If λ is in V , there are infinitely many n such that e n (T λ,π ) ≥ n , hence ne n (T λ,π ) → 0 when n → +∞, and T λ,π is uniquely ergodic by Proposition 16. Thus m({λ; T λ,π is uniquely ergodic}) is at least m(V ) ≥ 1 -3r 3 , and thus is one as is arbitrary.

The above proof does not use any of the geometric properties of interval exchanges; what it needs is only that it is a class of symbolic systems on an r-letter alphabet, of complexity at most sn for a fixed s, with a common invariant measure ρ such that the vector (ρ [START_REF] Avila | Weak mixing for interval exchange maps and translation flows[END_REF], ...ρ[r]) takes all possible values in Λ r .

Note that explicit constructions of uniquely ergodic interval exchanges are not very difficult to make, for example by adapting the methods of [START_REF] Keane | Interval exchange transformations[END_REF], as exposed in Section 4 above, to get one invariant measure.

WEAK MIXING AFTER BOSHERNITZAN [5]

The second big conjecture on interval exchanges was about weak mixing: for any given primitive permutation π which is not a circular permutation (a circular permutation is such that i ≡ πi mod r, for all 1 ≤ i ≤ r), T λ,π is weakly mixing for m-almost every λ ∈ Λ r . This was stated as a question in [START_REF] Veech | The metric theory of interval exchange transformations I[END_REF] (W. Veech never makes conjectures) and resisted more than twenty years before being proved by A. Avila and G. Forni [START_REF] Avila | Weak mixing for interval exchange maps and translation flows[END_REF]. The recent result we give now is not known to be equivalent, but has at least a similar flavour and its proof is quite short; the proof we give is adapted, with modifications, from [START_REF] Boshernitzan | A condition for weak mixing of induced IETs[END_REF].

Definition 11. For 0 < t < 1, φ(t) is the largest s > 0 such that for infinitely many n there is a Rokhlin tower of total measure 4s, made of 2n + 1 intervals, with t in the middle of the middle level; φ(t) is defined to be 0 if no such s exists. Proposition 18. If T λ,π is ergodic for the Lebesgue measure ρ, and φ(t) > 0, the induced map of T on [0, t[ is weakly mixing for the Lebesgue measure on [0, t[.

Proof

For infinitely many m, we build a tower of total measure > a > 0, made of 2m + 1 intervals, with t in the middle of the middle level. The intersection of this tower with [0, t[ consists of about mt (by the ergodic theorem for T -1 ) full levels below the one containing t, the left half of the level containing t, and about mt (by the ergodic theorem for T ) full levels above the one containing t; we trim it to get exactly n levels below and above, called Y n,k , for -n ≤ k ≤ n; this yields infinitely many values of n.

Suppose the induced map U om [0, t[ has an eigenfunction f for the eigenvalue θ. Because the Y n,k are small intervals, there exists a sequence of maps f n such that ||f -f n || 1 → 0 and f n has a constant value f n,k on each Y n,k . The f n,k can be taken of modulus 1.

Let Z be the tower made with the left halves of the Y n,k , -n ≤ k ≤ -1; it has total measure at least a 5 . If r n is the translation taking the left half to the right half of each Y n,k , and if x is in a level of Z, we have f n (U n+1 x) = f n (U n r n x). Then, for any given and n large enough,

ρ(Z)|θ -1| = -1 k=-n |θ n+1 f n,k -θ n f n,k |ρ(Y n,k ) = Z |θ n+1 f n (x) -θ n nf n (r n x)|dx ≤ 2 + Z |θ n+1 f ( x) -θ n f (r n x)|dx = 2 + Z |f (U n+1 x) -f (U n r n x)|dx ≤ 4 + Z |f n (U n+1 x) -f n (U n r n x)|dx = 4 .
Letting n tend to infinity, we get θ = 1. But U is ergodic, as, if there is a non-trivial invariant set for U , we can use the induction castle to build a non-trivial invariant set for T ; thus θ = 1 is excluded.

Proposition 19. If T λ,π is minimal and ergodic for the Lebesgue measure, the set of t such that φ(t) > 0 is residual and of full Lebesgue measure.

Proof

By making the induction castle of a small subinterval, for any given N we can make towers of at least N intervals of total measure at least 1 r+2 . Let Y n be a sequence of such towers, with h n intervals, and Z n be the middle ninth (=middle third in length and height) of Y n . Let Z be {Z n infinitely often}. Z is residual and ρ(Z) is at least 1 10(r+2) , while if z is in Z n there is a Rokhlin tower of total measure at least 1 6(r+2) , made of h n → +∞ intervals, with z in the middle of the middle level.

As the set of t such that φ(t) > 0 is T -invariant, we conclude by ergodicity.

Note that Proposition 19 does not give a way to find suitable values of t; explicit constructions (as opposed to existence theorems of sets of full measure) of weakly mixing r-interval exchanges are rather scarce: the only ones we have been able to find in the literature are for r = 3 [START_REF] Katok | Approximations in ergodic theory[END_REF][13], r = 4 [START_REF] Ferenczi | Eigenvalues and simplicity of interval exchange transformations[END_REF][27], and r = 6 [START_REF] Ya | Weak mixing in interval exchange transformations of periodic type[END_REF], while [START_REF] Ferenczi | Billiards in regular 2n-gons and the self-dual induction[END_REF] gives a construction for every value of r and the permutation πi = r + 1 -i, and [START_REF] Ferenczi | The self-dual induction for every interval exchange transformation[END_REF] gives a construction for every value of r and a quite different permutation.

SIMPLICITY: THE LAST FRONTIER?

The third big conjecture on interval exchanges is still open, and we end this paper by stating it as Question 1 below, with the necessary historical background.

One recurrent preoccupation of ergodicians in the last twenty years has been with joinings: the notion of self-joinings of a system has been introduced by D. Rudolph in [START_REF] Rudolph | An example of a measure-preserving map with minimal self-joinings, and applications[END_REF], to generalize some useful invariants of measure-theoretic isomorphism such as the factor algebra and the centralizer. Definition 12. A self-joining (of order two) of a system (X, T, µ) is any measure ν on X × X, invariant under T × T , for which both marginals are µ. Definition 13. An ergodic system (X, T, µ) has minimal self-joinings (of order two) if any ergodic self-joining (of order two) ν is either the product measure µ × µ or a diagonal measure defined by ν(A × B) = µ(A ∩ T i B) for an integer i.

A transformation which has minimal self-joinings has trivial centralizer and no nontrivial proper factor, and can be used to build a so-called counter-example machine [START_REF] Rudolph | An example of a measure-preserving map with minimal self-joinings, and applications[END_REF] with surprising properties. The first example of a transformation with minimal self-joinings was given in [START_REF] Rudolph | An example of a measure-preserving map with minimal self-joinings, and applications[END_REF], and a little later the famous Chacon map was shown in [START_REF] Junco | Chacon's automorphism has minimal self-joinings[END_REF] also to have minimal self-joinings. However, both these examples may seem built on purpose, and they have no "natural", i.e. geometric, realization. Then geometric examples of transformations with minimal self-joinings were sought in the category of interval exchanges. And indeed A. del Junco [START_REF] Junco | A family of counterexamples in ergodic theory[END_REF] built a one-parameter family of three-interval exchanges, depending on an irrational γ, and proved that whenever this γ has bounded partial quotients in its continued fraction expansion the system has minimal self-joinings (the interested reader is warned that he will not find the terms "three-interval exchange" or "minimal self-joinings" in del Junco's paper; the systems which he describes as two-point extensions of rotations are indeed three-interval exchanges, and the notion of "simplicity" he proves is only slightly weaker than the original notion of minimal self-joinings, and has been standing as the current definition of "minimal self-joinings " since [START_REF] Junco | A rank-one, rigid, simple, prime map, Ergodic[END_REF]).

But in the meantime, W. Veech [START_REF] Veech | The metric theory of interval exchange transformations I[END_REF] had shown that almost all interval exchanges (in the sense: for a fixed permutation, for Lebesgue-almost all values of the lengths of the intervals) are rigid: Definition 14. A system (X, T, µ) is rigid if there exists a sequence s n → ∞ such that for any measurable set A µ(T sn A∆A) → 0.

Simple systems have uncountable centralizers and cannot have minimal self-joinings; thus Veech devised in [START_REF] Veech | A criterion for a process to be prime[END_REF] a weakened notion of minimal self-joinings to allow for a nontrivial centralizer; the new notion, which Veech called "property S", is now known as simplicity (in the sense of Veech): Definition 15. An ergodic system (X, T, µ) is simple of order two if any ergodic self-joining of order two ν is either the product measure µ × µ or a measure defined by ν(A × B) = µ(A ∩ S -1 B) for some measurable transformation S commuting with T .

Simplicity is strong enough to keep many of the properties of systems with minimal selfjoinings, though proving this required a lot of work [START_REF] Junco | On ergodic actions whose self-joinings are graphs[END_REF] [START_REF] Veech | A criterion for a process to be prime[END_REF]. And Veech asked the following question (4.9 of [START_REF] Veech | A criterion for a process to be prime[END_REF]) Question 1. Are almost all interval exchange transformations simple?

The notion of simplicity having been devized just for that, the tacit conjecture is that indeed almost all interval exchanges are weakly mixing, simple and rigid.

But, while Veech's question stood unanswered, examples of simple transformations remained very scarce: there were of course the systems with minimal self-joinings, and some systems without minimal self-joinings but naturally related to these systems (such as the time-one map of a flow which, as a flow, has minimal self-joinings); at last in [START_REF] Junco | A rank-one, rigid, simple, prime map, Ergodic[END_REF], a natural generalization of the Chacon map was (very cunningly!) shown to be simple and rigid. It remains to this day the main explicit example of a simple and rigid map; some more three-interval exchanges, beside del Junco's, were proved to have minimal self-joinings [START_REF] Ferenczi | Joinings of three-interval exchange transformations[END_REF]; and at long last some three- [START_REF] Ferenczi | Joinings of three-interval exchange transformations[END_REF] and four- [START_REF] Ferenczi | Eigenvalues and simplicity of interval exchange transformations[END_REF] interval exchanges were proved to be simple and rigid, but they are proved to be so because they are measure-theoretically isomorphic to the del Junco-Rudolph map.

Thus an answer to Veech's question seems still to be a very difficult problem, which also fell a little out of fashion; the result of Avila-Forni was a necessary step towards a positive answer, but their proof of weak mixing does not seem to imply anything in the direction of simplicity. However, the result of Boshernitzan in Section 6 above may give a faint glimmer of new hope, as it proves weak mixing by the "Chacon trick" of building two towers of heights differing by one, and it is this trick which implies the weak mixing of the Chacon and del Junco-Rudolph maps, but also the minimal self-joinings of the Chacon map and (after long manipulations using the full knowledge of the system, and not only local towers), the simplicity of the del Junco-Rudolph map.

1. 2 .Definition 2 .

 22 Word combinatorics. We look at finite words on a finite alphabet A. A word w 1 ...w k , is of length k and we write |w| = k. The concatenation of two words w and w is denoted by ww . The empty word is the unique word of length zero. A word w = w 1 ...w k occurs at place i in a word v = v 1 ...v s or an infinite sequence

Proposition 3 .

 3 [START_REF] Keane | Interval exchange transformations[END_REF] The i.d.o.c. condition implies minimality.

  on [P 3 , P 4 [ U = T m+p . The order of the image intervals is, from left to right, U [P 1 , P 2 [, U [P 3 , P 4 [, U [P 2 , P 3 [, U [P 0 , P 1 [.


Siddhartha Chandra
email: siddhartha.chandra@inria.fr

Grigorios G Chrysos
email: grigoris.chrysos@gmail.com

Iasonas Kokkinos
email: iasonas.kokkinos@inria.fr

Surface Based Object Detection in RGBD Images

Viewpoint variation is one of the main challenges for object-detection frameworks. In this work we describe strategies to improve object detection pipelines by introducing viewpoint based mixture components. We learn accurate mixtures of object detectors for RGB-Depth (RGBD) data using the latent SVM framework. Our contributions are threefold. First, we use surface-based object representations (3D mesh models) from available 3D object model repositories to learn strongly supervised viewpoint classifiers. These are used to guide the first stages of model learning, and help avoid inaccurate local minima of latent SVM training. Second, we develop a geometric dataset augmentation scheme that uses scene geometry to 'take another look' at the training data, simulating the effect of camera viewpoint changes. Third, to better exploit depth information, we develop a novel depth-based dense feature extraction method that provides a robust statistical description of scene geometry. We evaluate our learned detectors on the NYU dataset, and demonstrate that each of our advances results in systematic performance improvements over the traditional HOG-based detection pipeline.

Introduction

Intra-class variation in object detection is due to both intrinsic (texture and shape), and extrinsic (viewpoint and illumination) factors. Information about all such factors is rarely available. The recent enthusiasm about commercial RGBD sensors can be understood as being due to the reduction in intra-class variability: depth maps are invariant to texture and illumination changes, leaving us mostly with shape and viewpoint variation. This simplification was at the root of the success of Kinect's entirely depth-based pose estimation system [START_REF] Shotton | Real-time human pose recognition in parts from single depth images[END_REF] and has led to a proliferation of works around holistic scene analysis through shape, appearance and even physics-based cues [START_REF] Lin | Holistic scene understanding for 3d object detection with rgbd cameras[END_REF][START_REF] Zhang | Estimating the 3d layout of indoor scenes and its clutter from depth sensors[END_REF][START_REF] Zheng | Beyond point clouds: Scene understanding by reasoning geometry and physics[END_REF]. While many recent approaches to learning from depth data have either exploited only RGB information from 3D object models [START_REF] Pepik | Teaching 3d geometry to deformable part models[END_REF] or only partially used surface information [START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF], we assume that depth is available both at training, and test time. In this work we use a mixture of object detectors for RGBD data. The mixture components in our model correspond to viewpoints and are treated as latent variables. We make three contributions. First, in section 3, we develop efficiently computable displacement features that statistically encode the shape of a surface within a sliding window. These complement the Histogram-Of-Gradient (HOG) [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] and the Histogram-of-Depth Gradient (HOD) [START_REF] Spinello | People detection in rgb-d data[END_REF] features.

Second, in section 4, we exploit publicly available 3D object datasets that contain handcrafted surface models of objects. We use these to construct a synthetic dataset comprising (a) depth maps from the rendered objects and (b) ground truth information regarding the viewpoint of an object. These datasets allow us to train viewpoint classifiers in a strongly supervised manner. We employ these classifiers to initialize the viewpoint components of natural images in our mixture model, so as to guide the first stages of model learning. Effectively these classifiers make an 'informed guess' about the viewpoints of objects. Our experiments indicate that this strategy consistently helps improve the detection accuracy.

Third, in section 5, we exploit the scene geometry for dataset augmentation. For this we simulate the effects of camera viewpoint changes by a combination of re-rendering and inpainting. This allows us to train detectors that are more tolerant to viewpoint changes at test time, by accommodating their variability at training-time.

We start by formally introducing our mixture of components model for object detection. We will be separately presenting prior works relevant to the aforementioned three advances.

Viewpoint Mixture Model

Our object detection framework consists of a mixture model where each mixture component corresponds to a viewpoint. Formally, we denote the parameters of our mixture model by w = {w 1 , • • • , w C }, where C is the total number of mixture components (C = 3 in our experiments). Given a bounding box x of an RGBD image, as well as a component ID c ∈ {1, • • • ,C}, the model provides a score, which is equal to the dot product of its parameters w c and the feature vector of the bounding box Ψ(x). The feature vector Ψ(x) consists of two types of features: (i) the gradient and/or color features for the bounding box x, which we denote by φ g (x); (ii) the depth features for the bounding box x, which we denote by φ d (x). In other words, the score s w (x, c) for a bounding box x, and component ID c is given by

s w (x, c) = w ⊤ c Ψ(x), Ψ(x) = [φ g (x); φ d (x)] (1)
We use HOG [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] to define φ g (x)and a combination of HOD [29] and our novel displacement features to define φ d (x). We describe these features in the next section. We will describe our learning framework in detail after the model description.

Surface Description using Displacement Features

Most standard feature extraction schemes, for example [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF][START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF], employ a sequence of differentiation and L2-norm normalization; these two steps discard the effects of additive and multiplicative illumination changes respectively. This processing is combined with spatial pooling to render the descriptors robust with respect to small translations. Even though the aforementioned steps yield increased robustness, a substantial part of the signal information is lost during the processing steps. This information loss is considered to be partially responsible for the saturation of HOG-based detection performance [START_REF] Vondrick | Hoggles: Visualizing object detection features[END_REF].

More dedicated point cloud descriptors have been proposed [START_REF] Bo | Depth kernel descriptors for object recognition[END_REF][START_REF] Bo | Unsupervised feature learning for rgb-d based object recognition[END_REF][START_REF] Frome | Recognizing objects in range data using regional point descriptors[END_REF][START_REF] Edie | Using spin images for efficient object recognition in cluttered 3d scenes[END_REF][START_REF] Radu | Fast point feature histograms (fpfh) for 3d registration[END_REF][START_REF] Socher | Convolutional-recursive deep learning for 3d object classification[END_REF]. However, these point cloud descriptors are not efficient to compute densely and are primarily used either globally or at interest points.

Inspired by the success of simple depth comparision based features in [START_REF] Shotton | Real-time human pose recognition in parts from single depth images[END_REF], we propose efficient, densely computable depth features which complement gradient based features with surface-based information. Instead of relying on the few, and variable, positions where the depth signal changes, as in HOG/HOD, we describe our signal within a window in terms of the depth displacements with respect to its center.

Given a region/bounding box x in a depth image, and a cellsize s, we first subsample x using average pooling. In other words, we replace each non-overlapping s × s cell in x by the average depth value of the pixels in the cell. We denote the subsampled image region by x. Given x, we compute the displacement of each pixel p i in x from the center pixel p 0 . This displacement is given by, δ i = d p 0 -d p i , where d p i is the depth value at pixel p i .

We quantize δ i into a set of N displacement bins, using a hard quantization function: q(δ ) : R → R N . Since δ i can assume both positive and negative values, we have symmetric displacement bins corresponding to the positive and negative values. Thus δ i is expressed as a sparse-indicator-feature vector of size N. We concatenate these sparse vectors to get the displacement feature of x. In our experiments, hard quantization outperformed soft quantization schemes. Hard quantization also yields sparse features, enabling us to speed up convolutions. The number of displacement bins N was set with cross-validation. The cellsize s was set equal to the size of HOG cells. The motivation for these features is illustrated intuitively in Figure 1. A feature extraction pipeline that relies on signal gradients (Figure 1 (d) ) will either consider their nonoverlapping gradient signals distinct, or resort to smoothing to make them comparable. Instead, our displacement-based features (Figure 1, (e),(f) ) quantize the signal's domain into regions that are 'far' or 'near' from the center of the signal in depth, delivering features that exhibit a smaller amount of intra-class variation. In a certain sense both our displacement-based and the gradient-based representations contain the same information, but in different 'formats': intuitively, our displacement features are more appropriate when the boundaries are variable, but the depth variability is consistent, while the HOD features could be more appropriate for well localized boundaries but potentially a larger breadth of depth differences.

Learning A Viewpoint Mixture Model

Mixture models are often used in object detection systems [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] to cope with viewpoint variations of objects in the data. Most training datasets for object detection do not contain any viewpoint information about the samples. In the absence of explicit ground truth annotations, viewpoints as commonly treated as latent variables.

In particular, given a training dataset

D = {(x i , y i ), i = 1, • • • , N},
we wish to estimate the parameters of our mixture model such that it provides accurate detections for previously unseen test images. Here x i is a training sample (specifically, a bounding box of an RGBD image) and y i ∈ {+1, -1} indicates whether the sample x i belongs to the object class or the background class. For convenience, we denote the indices of all object samples as O and the indices of all background samples as B.

In the absence of viewpoint information, we estimate the parameters of the model using weak supervision. We employ the following latent support vector machine (latent SVM) formulation [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Yu | Learning structural svms with latent variables[END_REF]:

min w 1 2 ||w|| 2 +C O ∑ i∈O ξ i +C B ∑ j∈B ξ j , s.t. max c w ⊤ c Ψ(x i ) ≥ 1 -ξ i , ξ i ≥ 0, ∀i ∈ O, max c w ⊤ c Ψ(x j ) ≤ -1 + ξ j , ξ j ≥ 0, ∀ j ∈ B (2)
where c denotes the viewpoint of the sample. Intuitively, the above problem considers the maximum score of a sample over all viewpoints. This score is encouraged to be larger than 1 for an object sample and smaller than -1 for a background sample. The hyperparameters C O and C B are the relative weights for the classification error of the object and background samples respectively. The above optimization problem is a difference-of-convex program whose local minimum or saddle point solution can be obtained using the CCCP algorithm [START_REF] Yuille | The concave-convex procedure[END_REF].

The CCCP algorithm starts by initializing the viewpoints (or component IDs) and then alternatively estimates the model parameters w and viewpoints in an iterative manner. The main challenge in using this algorithm is that the initialization of the viewpoints greatly affects the performance in practice. In order to better initialize the viewpoints, we propose a novel approach in the next subsection, which exploits the availability of 3D models.

Component Initialization with 3D Models

The intuition behind using a mixture model for object detection is that each component can capture the statistics of an object category specific to one viewpoint. For example, in order to detect a 'car', we may use a mixture of three components, one each for the front, back and side view of a car, since each of these views has significantly different appearance. In order to capture this intuition, Felzenszwalb et al. [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] proposed to cluster the object samples into C clusters according to the aspect ratios of their corresponding bounding boxes. While the aspect ratio of the bounding box is an informative cue for the viewpoint of an object, it is not always accurate. For example, it can help distinguish between the front and the side views of a car, but not the front and the back. In order to overcome this deficiency, we exploit the fact that our training samples contain depth information.

The idea of using 3D information to guide model learning has been recently explored in several works. For instance [START_REF] Pepik | Teaching 3d geometry to deformable part models[END_REF] used a 3D CAD model to guide the part placement for cars in RGB images, by rendering the CAD model from different viewpoints and predicting where its parts should be in the image. More recently [START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF] used the depth field to guide the training of DPMs [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] on RGBD images, but evaluated their models using RGB images. Recent literature also discusses reasoning in 3D from 2D images. Fidler et al. [START_REF] Fidler | 3d object detection and viewpoint estimation with a deformable 3d cuboid model[END_REF] extend DPMs to predict 3D bounding boxes around objects, while [START_REF] Aubry | Seeing 3d chairs: exemplar part-based 2d-3d alignment using a large dataset of cad models[END_REF] uses a large number of colour images rendered from synthetic 3D models to learn exemplar SVMs and perform 3D-2D registration. Zia et al. [START_REF] Zia | Are cars just 3d boxes? -jointly estimating the 3d shape of multiple objects[END_REF] use 3D scene modeling to localize objects in RGB images using more detailed shapes than 2D bounding boxes. Unlike these approaches, we aim at a fullblown RGBD training algorithm that uses depth during both training and testing.

Specifically, we develop a two step strategy to initialize the component IDs for the object samples O. First, we use 3D models of object categories from the Google Warehouse to generate synthetic samples with known viewpoints. The synthetic samples are used to learn a viewpoint classifier. Next the cues obtained by the viewpoint classifier are combined with the aspect ratio information in order to obtain the component IDs of the object samples.

Learning a Viewpoint Classifier

min µ λ 2 ||µ|| 2 + M ∑ i=1 ξ i , s.t. µ ⊤ c ′ i φ d (x ′ i ) -µ ⊤ c φ d (x ′ i ) ≥ ∆(c ′ i , c) -ξ i , ∀c ∈ {1, • • • ,C}, ∀i ∈ {1, • • • , M}. (3)
The loss function ∆(•, •) is the standard 0-1 loss, that is,

∆(c ′ i , c) = 0 if c ′ i = c, 1 otherwise. (4)
Intuitively, the above problem learns the classifier µ that gives a high score to the correct component ID for each synthetic sample. The hyperparameter λ is the relative weight of the regularizer. Note that we only use the depth features φ d (•) to learn the viewpoint classifier. This is due to the fact that while the RGB information that is sometimes provided in the 3D CAD models is not realistic, the depth information is highly accurate.

Computing Component Initialization

Having learnt the viewpoint classifiers as described in the previous subsection, we now turn to combining them with the aspect ratio cues in order to obtain an accurate initialization of the component IDs. Intuitively, our method tries to assign component IDs to the samples based on the viewpoint classifier scores, while also trying to constrain samples having similar aspect ratios to belong to the same component. To this end, we specify a random field

G = (X O ∪ X C , E O ∪ E C ).
Variables of the Random Field. The variables of the random field are of two types. The variable X i ∈ X O represents the i-th object sample x i where i ∈ O. The variable X j ∈ X C represents the j-th cluster center of the clustering obtained using the aspect ratio of the object samples as proposed in [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], where j ∈ {1, • • • ,C}. Each variable can be assigned a label from the set L = {l 1 , • • • , l C }, where the label l a represents component ID a. The unary potentials are defined as follows:

θ i (l a ) = -µ ⊤ a φ d (x i ), ∀X i ∈ X O , l a ∈ L, θ j (l a ) = 0, ∀X j ∈ X C , l a ∈ L. (5)
Thus, the unary potentials are the negative of the viewpoint classifier scores for the variables representing the samples, and 0 for the cluster centers.

Edges of the Random Field. We have two types of edges. Edges E i j ∈ E O connect the sample X i ∈ X O to the cluster center X j ∈ X C . The pairwise potentials for these edges are:

θ i j (l a , l b ) = 0 if a = b, -d(A(X i ), A(X j )) otherwise, (6)
where A(•) is the aspect ratio of the bounding box corresponding to the variable, and d(•, •) is the difference between the aspect ratios. Thus, the pairwise potential is 0 if the object sample is assigned to the cluster center, and is proportional to the negative of the difference in their aspect ratios otherwise. The edges E j j ′ ∈ E C connect the two cluster centers X j , X j ′ ∈ X C . The pairwise potentials corresponding to these edges are as follows:

θ j j ′ (l a , l b ) = ∞ if a = b, 0 otherwise. ( 7
)
In other words, two cluster centers are prohibited from belonging to the same component.

Labeling. We represent a labeling of the above random field by a function f :

X O ∪ X C → L, that is, the variable X ∈ X O ∪ X C takes the label f (X).
The energy of the labeling f is given by the sum of the corresponding unary and pairwise potentials, that is,

Q( f ) = ∑ X i ∈X O θ i ( f (X i )) + ∑ X j ∈X C θ i ( f (X j )) + λ   ∑ (X i ,X j )∈E O θ i j ( f (X i ), f (X j )) + ∑ (X j ,X j ′ )∈E C θ j j ′ ( f (X j ), f (X j ′ ))   . ( 8
)
The hyperparameter λ is the relative weight of the aspect ratio cue with respect to the viewpoint classifier cue. When λ = 0, the inferred components correspond to the highest scoring viewpoint, and when λ = ∞, the inferred components are equal to the initialization of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. In our experiments, we determined the value of λ through cross-validation.

Energy Minimization. In order to obtain the initial viewpoint of each object sample x i , i ∈ O, we wish to minimize the energy function [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. To this end, we observe that given the variables X C , the variables in X O are conditionally independent of each other. Since C is typically very small, this implies that the cardinality of the variable set X C and the label set L is small. This observation allows us to minimize the energy function over all possible labellings by exhaustively searching for all labellings of X C and obtaining the best label for each X i ∈ X O independently. The labeling with the minimum energy provides us with the initial component IDs of all the object samples. In our experiments C = 3 and the exhaustive search takes a few minutes for each experiment.

Dataset Augmentation with Geometric Jittering

Having exploited 3D models, in the last section, to learn more accurate object detectors, we now describe a strategy to make object detectors more robust to viewpoint variations. Camera viewpoint variation is a major challenge in object recognition; camera rotations affect object appearance radically and mixtures of viewpoint-tuned classifiers are imperative for multi-view detection. This challenge remains with RGBD sensors, as they only record the side of the object's surface facing the camera. Here we exploit depth information to learn robust detectors by accommodating variability due to moderate camera rotations. We propose a dataset augmentation scheme that uses geometric information to take 'a different look' at objects in our training set. We simulate the effects of small camera rotations around the object, and obtain new samples that see the object from novel viewpoints. Our technique can be understood as a generalization of the 'jittering' technique that is known to drastically improve detection accuracy by using translated/scaled/rotated samples of an object during training. All these transformations assume that the azimuth and elevation of the camera stays fixed; here instead we let azimuth and elevation vary moderately (±10 o ) and use the resulting images to enhance the variability of our training set.

We use Depth-Image-Based Rendering (DIBR) [START_REF] Do | Quality improving techniques for free-viewpoint dibr[END_REF][START_REF] Fehn | Depth-image-based rendering (dibr), compression, and transmission for a new approach on 3d-tv[END_REF][START_REF] Müller Karsten | View synthesis for advanced 3d video systems[END_REF][START_REF] Ha | Image-based rendering with depth information using the propagation algorithm[END_REF] which is common in applications [START_REF] Hassner | Viewing real-world faces in 3d. ICCV[END_REF] that require the synthesis of novel "virtual" views of an image, based on its intensity and depth values. Even though the geometric transformations involved in DIBR are straightforward, a host of image processing problems emerge [START_REF] Sun | An overview of free view-point depth-image-based rendering (dibr)[END_REF], involving ghost contours, cracks, and most importantly, disocclusions, namely areas that cannot be viewed from the original viewpoint. More recently, [START_REF] Rematas | Imagebased synthesis and re-synthesis of viewpoints guided by 3d models[END_REF] use structural information from 3D models to synthesize novel-views of cars from images, which are used to amplify training data for DPMs.

However, the method proposed in [START_REF] Rematas | Imagebased synthesis and re-synthesis of viewpoints guided by 3d models[END_REF] requires alignment of real images with 3D models, which they achieve manually. In this work, we use the free viewpoint rendering method described in [START_REF] Do | Quality improving techniques for free-viewpoint dibr[END_REF] to render both depth and RGB images of our objects. These rendered views suffer from the presence of holes. The existing literature describes several image inpainting techniques [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF][START_REF] Getreuer | Total variation inpainting using split Bregman[END_REF][START_REF] Herrera | Depth map inpainting under a second-order smoothness prior[END_REF][START_REF] Papandreou | Image inpainting with a wavelet domain hidden markov tree model[END_REF] to remedy these holes. We post-process the RGB image renderings by performing an inverse warping of the missing pixels to retrieve the textures as described in [START_REF] Do | Quality improving techniques for free-viewpoint dibr[END_REF], and the depth renderings using the bilateral filtering approach as proposed in [START_REF] Silberman | Indoor segmentation and support inference from rgbd images[END_REF].

Experimental Results

Method Bed Chair M.+TV Sofa Table Avg. gdpm [START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF] 0.3339 0.1372 0.0928 0.1104 0.0405 0.1430 rgbd-hog + sparse [START_REF] Ren | Histograms of sparse codes for object detection[END_REF] 0 We now describe our experimental setup and empirical results. We used the NYU Depth v2 dataset [START_REF] Silberman | Indoor segmentation and support inference from rgbd images[END_REF] that contains 1449 RGB images with aligned depth maps. The dataset comes with train-test splits and pixel-wise object labels. From the pixel-wise labels we generate tight bounding box ground truth annotations for 5 object categories: bed, chair, monitor + television (M.+TV), sofa, and table as in [START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF]. We acquired 3-5 synthetic models for each class from the Google 3D warehouse, and rendered depth images centered around three landmark viewpoints: one frontal and two side views (Figure 2). We used these depth images to initialize viewpoints for our real samples. We compute HOG features at a spatial bin size of 8. The displacement features were computed using a bin size of 15. Our view-point initialization method was trained using depth HOG and displacement feature descriptors.

For the mixture model, we learn 3 components as in [START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF]. Our augmented data was rendered by simulating the effect of the camera moving to the left, and top from the original orientation (Figure 3). This rendering is done offline, and takes approximately 2 seconds for each pair of images (RGB+Depth) on a single-core machine.As in [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF] we use lateral flipping of training images, so we do not render views where the camera moves to the right. We evaluate the various methods outlined in this paper on the task of 2-D Object Detection with RGBD images on the NYU dataset. In Table 1, we report the Average Precision values for different methods. We also compare our results to the methods published in [START_REF] Ren | Histograms of sparse codes for object detection[END_REF] and [START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF]. While [START_REF] Ren | Histograms of sparse codes for object detection[END_REF] uses sparse coding features with DPM supervision, [START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF] uses depth information to weakly supervise the latent update step in the latent SVM formulation. Authors in [START_REF] Ren | Histograms of sparse codes for object detection[END_REF] report using only RGB data; We used their framework with RGBD data. Figure 6 shows the precision-recall curves for the competing methods.

We get systematic improvements in detection performance as we introduce displacement features (+disp), augmented data (+aug), and viewpoint initialization (+vp) to the baseline detector. Our results also outperform those in [START_REF] Ren | Histograms of sparse codes for object detection[END_REF][START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF], even though [START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF] uses a deformableparts model. Compared to the rgbd-hog baseline, we show an average improvement of 7.7%. While the displacement features allow us to better capture the depth variations of the surface, the augmentation and viewpoint initialization allow us to better model viewpoint effects, as reflected by the sharper templates in Figure 5. We visualized our detector mistakes using the techniques proposed in [START_REF] Hoiem | Diagnosing error in object detectors[END_REF]. These mistakes are shown in Figure 4 as top false positive detections. It can be observed that our detector makes fewer mistakes, while just the rgbdhog detector makes several obvious mistakes, such as firing on random objects, and parts of objects. Both the detectors often mistake a sofa for a bed, which is a reasonable mistake. mentation which relies on rendering novel views from 2-D images, and a strategy for using existing 3D object models to initialize viewpoints in a latent SVM formulation. Our contributions systematically improve detection performance on a popular benchmark RGBD dataset. In this work, we exploited available 3D models to estimate the view-points of objects of interest in natural images. We rendered synthetic images with known viewpoints and used these to train viewpoint classifiers for natural images. The synthetic data we generated was clean of all clutter, while the natural images usually have objects surrounded by clutter. Learning viewpoint classifiers that are invariant to clutter is the next natural extension of this approach. The number of viewpoints dictates the number of components in our mixture model, and thus controls the model complexity. In the future we would like to develop models where we can express the viewpoint/orientation of an object in continuous space, while at the same time keeping a check on the model complexity. We would also like to extend our objective to solve the tasks of object detection and pose estimation simultaneously. Finally, we would like to use these strategies in the context of deep learning.

c 2015 .

 2015 This work has been partially funded by the EU Project MOBOT FP7-ICT-2011-600796.

Figure 1 :

 1 Figure 1: Gradient-versus-Displacement based features for two synthetic 'flatland', 2D shapes: as seen from above, their respective 'depth' signals would correspond to the functions shown on the top right. Gradient-based features like HOG (d) are sensitive to shape variation and alignment, while displacement-based features (e,f) encode relative depth, which is similar for both shapes on a larger extent of their domains.

Figure 2 :

 2 Figure2: Depth images rendered from the synthetic 3D models showing the three candidate view-points used to initialize our mixture components. We first align each model to the fronto-parallel view, then rotate it to get the desired view. We rotate these samples by small angles (< 10 • ) around random unit vectors to generate more samples for a view.

Figure 3 :

 3 Figure 3: We render novel views using the free viewpoint rendering method described in [6]: (a) original image, (b) zoomed in area of interest, and two views rendered by moving the camera to the left and top respectively. Despite some noticeable distortions in the rendered images, we empirically demonstrate that performing this geometric dataset augmentation during training is beneficial.

Figure 4 :

 4 Figure 4: Top false positive detections for 'bed' for the baseline rgbd-hog detector, and our final rgbd-hog+disp+aug+vp detector. The green box shows the detection, the red shows the ground truth if present. Our overall approach makes fewer, more reasonable mistakes.

  (a) rgb-hog (b) rgbd-hog (c) rgbd-hog+disp (d) rgb-hog+aug (e) rgbd-hog+disp+aug+vp (f) vp classifier

Figure 5 :

 5 Figure 5: Hoggles [31] visualization of model parameters learnt by our 3 component mixture of detectors for "M.+TV" for methods in Table 1. Filters in (c)-(e) resemble the object shape more than those in (a),(b). (f) shows the viewpoint classifiers learnt using 3D models.

Figure 6 :

 6 Figure 6: Precision recall curves for the detection task for the 5 classes

Table 1 :

 1 Average Precision for the Detection Task on the NYU Dataset. rgb-hog uses only HOG features, rgbd-hog uses HOG+HOD, disp indicates displacement features, aug indicates the use of augmented data, vp indicates the viewpoint initialization using 3D models.

		.4835 0.2435 0.2769 0.2869 0.1726 0.2927
	rgb-hog	0.2337 0.1335 0.1339 0.1094 0.0376 0.1296
	rgbd-hog	0.4660 0.2773 0.2480 0.2295 0.1430 0.2628
	rgbd-hog + disp	0.5178 0.2771 0.2591 0.3440 0.1683 0.3133
	rgbd-hog + disp + aug	0.5406 0.2919 0.2583 0.3470 0.1653 0.3206
	rgbd-hog + disp + aug + vp 0.5675 0.3023 0.3093 0.3719 0.1957 0.3493
	improvement over rgbd-hog 0.1015 0.0250 0.0613 0.1424 0.0527 0.0766

Acknowledgement: We would like to thank M. Pawan Kumar for providing his insights and expertise that greatly assisted this work.

Conclusions

In this paper, we have proposed strategies to improve object detection in RGBD images. Our contributions include our novel displacement features, a scheme for training data aug-


Guillaume Noyel
email: guillaume.noyel@ensmp.fr

Jesús Angulo
email: jesus.angulo@ensmp.fr

Dominique Jeulin
email: dominique.jeulin@ensmp.fr

Random Germs and Stochastic Watershed for Unsupervised Multispectral Image Segmentation

Keywords: multispectral image, unsupervised segmentation, mathematical morphology, stochastic watershed

This paper extends the use of stochastic watershed, recently introduced by Angulo and Jeulin [1], to unsupervised segmentation of multispectral images. Several probability density functions (pdf), derived from Monte Carlo simulations (M realizations of N rsandom markers), are used as a gradient for segmentation: a weighted marginal pdf a vectorial pdf and a probabilistic gradient. These gradient-like functions are then segmented by a volume-based watershed algorithm to define the R largest regions. The various gradients are computed in multispectral image space and in factor image space, which gives the best segmentation. Results are presented on PLEIADES satellite simulated images.

Introduction

Watershed transformation is one of the most powerful tools for image segmentation. Starting from a gradient, the classical paradigm of watershed segmentation consists in determining markers for each region of interest. The markers avoid the over-segmentation as a region is associated to each marker. When the markers cannot be easily defined several hierarchical approaches exist. They are mainly divided in two hierarchical techniques: 1) non-parametric waterfalls algorithm [START_REF] Beucher | Watershed, hierarchical segmentation and waterfall algorithm[END_REF] and 2) hierarchies based on extinction values, which allow to select the minima used in the watershed according to morphological criteria (dynamics, surface and volume) [START_REF] Meyer | An overview of Moprhological Segmentation[END_REF][START_REF] Vachier | Extinction value: a new measurement of persistence[END_REF]. Usually, the volume criteria is the most powerful.

In [START_REF] Angulo | Stochastic watershed segmentation[END_REF], Angulo and Jeulin, defined a new method: stochastic watershed. In the present paper, the method involving Monte Carlo simulation on the image is extended to multispectral images.

Random germs and stochastic watershed segmentation

One of the main artefacts of classical watershed is that small regions strongly depend on the position of the markers, or on the volume, i.e. the integral of the gray levels of the catchment basin, associated to their minima. In fact, there are two kinds of contours associated to the watershed of a gradient: 1st order contours, which correspond to significant regions and which are relatively independent from markers; and 2nd order contours, associated to "small", "low" contrasted or textured regions, which depend strongly on the location of markers. Stochastic watershed aims at enhancing the 1st order contours from a sampling effect, to improve the result of watershed.

Let us consider {mrk i (x)} M i=1 a series of M realizations of N uniform or regionalized random germs. Each one of these binary images is considered as the marker for a watershed segmentation of a scalar gradient or a vector gradient. Therefore, a series of segmentations is obtained, i.e. {sg mrk i (x)} M i=1 . Starting from the M realizations of contours, the probability density function pdf (x) of contours is computed by the Parzen window method [START_REF] Duda | Pattern Classification and Scene Analysis[END_REF]. The smoothing effect of the Gaussian convolution kernel (typically σ = 3 working on contours of one pixel width) is important to obtain a function where closed contours, such as textured regions or associated to small regions, are added together. The pdf (x) is thresholded to obtain the most prominent contours.

Moreover, we segment the pdf (x) image, using a watershed segmentation with a volume criteria in order to select the largest regions.

3 Multispectral image space (MIS) vs. factor image space (FIS)

In the current paper, multispectral images are used. Multispectral images are multivariate discrete functions with typically fewer than ten bands. In a formal way, in each pixel of a 2D multispectral image is considered a vector with values in wavelength. To each wavelength corresponds an image in two dimensions called channel. The number of channels depends on the nature of the specific problem under study (satellite imaging, microscopic images, etc).

Let

f λ : E → T L (x → f λ (x) = (f λ1 (x), f λ2 (x), . . . , f λ L (x))
), be a multispectral image, where: E ⊂ R 2 , T ⊂ R and T L = T × T × . . . × T ; x = x i \ i ∈ {1, 2, . . . , P } is the spatial coordinates of a vector pixel f λ (x i ) (P is the pixels number of E); f λj \ j ∈ {1, 2, . . . , L} is a channel (L is the channels number); f λj (x i ) is the value of vector pixel f λ (x i ) on channel f λj .

Due to the redundancy of channels, a data reduction is usually performed using Factor Correspondence Analysis (FCA) [START_REF] Benzécri | L'Analyse Des Données[END_REF]. We prefer a FCA in place of a Principal Component Analysis (PCA), because image values are positive and the spectral channels can be considered as probability distributions. As for PCA, from selected factorial FCA axes the image can be partially reconstructed. The metric used in FCA is the chi-squared, which is adapted to probability laws and normalized by channels weight. FCA can be seen as a transformation going from image space to factorial space. In factorial space the coordinates of the pixels vector on each factorial axis are called pixels factors. The pixels factors can be considered as another multispectral image whose channels correspond to factorial axes:

ζ : T L → T K /K < L (f λ (x) → c f α (x) = (c f α1 (x), . . . , c f α K (x)))
A limited number K of factorial axes is usually chosen. It is smaller than the channels number L. Therefore FCA can be seen as a projection of initial vector pixels in a factor space with a lower dimension. Moreover FCA can be used to reduce noise in the image [START_REF] Green | A Transformation for Ordering Multispectral Data in terms of Image Quality with Implications for Noise Removal[END_REF][START_REF] Noyel | Morphological Segmentation of hyperspectral images, Submitted to Image Analysis and Stereology[END_REF]. Consequently, we have two spaces for the multivariate segmentation: the multispectral image space (MIS) and the factor image space (FIS). Fig. 1 gives an example of a five bands satellite simulated image PLEIADES, acquired by the CNES (Centre National d'Etudes Spatiales, the French space agency) and provided by Flouzat [START_REF] Laporterie-Déjean | Thematic and statistical evaluations of five panchromatic/multispectral fusion methods on simulated PLEIADES-HR images[END_REF], and its corresponding FCA representation. Its channels are the following: f λ1 blue, f λ2 green, f λ3 red, f λ4 near infrared and f λ5 panchromatic. The panchromatic channel, initially of size 1460 × 1460 pixels with a resolution of 0.70 meters, was resized to 365 × 365 pixels. Therefore, the resolution is 2.80 meters in an image of 365×365×5 pixels. In order to represent a multispectral image in a synthetic way, we have created a synthetic RGB image using channels f λ3 red, f λ2 green and f λ1 blue. . In order to define a gradient, two approaches are considered: the standard symetric morphological gradient on each marginal channel and a metric-based vectorial gradient on all channels. The morphological gradient can only be applied on scalar images and is defined as the difference between dilation and erosion with a unit structuring element

f λ 1 blue f λ 2 green f λ 3 red f λ 4 near inf.-red f λ 5 panchrom.
B [2], i.e. (f λj (x)) = δ B (f λj (x)) -ε B (f λj (x)
). The metric-based gradient is a vectorial gradient defined as the difference between the supremum and the infimum of a defined distance on a unit neighbourhood B(x):

d (f λ )(x) = ∨[d(f λ (x), f λ (y)), y ∈ B(x)] -∧[d(f λ (x), f λ (y)), y ∈ B(x)],
where d :

T L × T L → [0, ∞[
is the metric distance used to calculate the difference between points in the neighborhood B. Various metric distances, useful for multispectral images, are available for this gradient such as: the Eu- 2 and the Chi-

clidean distance: d E (f λ (x), f λ (y)) = L j=1 (f λj (x) -f λj (y))
squared distance: d χ 2 (f λ (x i ), f λ (x i )) = L j=1 S f .λ j f λ j (xi) fx i . - f λ j (x i ) fx i . 2 with f .λj = P i=1 f λj (x i ), f xi. = L j=1 f λj (x i ) and S = L j=1 P i=1 f λj (x i ).
Besides, marginal gradients from spectral bands can be combined (by addition or supremum) to define new gradients. If all factor axes are kept, the chi-squared distance in MIS is equivalent to the Euclidian distance in FIS [START_REF] Benzécri | L'Analyse Des Données[END_REF]. Therefore, the vector metric-based gradient is more appropriate in MIS, with the chi-squared distance d χ 2 and in FIS, with the Euclidian distance d E .

(f λ 3 ) χ 2 (f λ ) E (c f α ) (c f α 1 ) (c f α 2 ) (c f α 3 )
Fig. 2. Morphological gradient (f λ 3 ) on channel 3, metric-based vectorial gradient in image space χ 2 (f λ ), the same in factor space E (c f α ) (3 axes) and morphological gradients of each components of factor space (c f α 1 ), (c f α 2 ), (c f α 3 ).

In the example of figure 2, we notice that the morphological gradients of the pixels factors on the axes 2, (c f α2 ), and 3, (c f α3 ), contain less information than the morphological gradient of the pixels factors on axis 1, (c f α1 ). Besides, the inertia of axes 2 and 3, 8.7 % and 6.2 % respectively, are very small. Therefore, we will only keep the first factor axis.

Weighted marginal pdf, vectorial pdf and probabilistic vectorial gradient

In the sequel, we define functions used as gradients g for segmentation: the weighted marginal probability density function mpdf , the vectorial pdf vpdf and the probabilistic vectorial gradient prob . The weighted marginal pdf mpdf is computed as follows:

• For the morphological gradient of each channel (f λj ), j ∈ [1, . . . , L], throw M realizations of N uniform random germs, i.e. the markers {mrk j i } j=1...L i=1...M , generating M ×L realizations. Get the series of segmentations, {sg j i (x)} j=1...L i=1...M , by watershed associated to morphological gradients of each channel (f λj ).

• Get the marginal pdf on each channel pdf j (x) = 1 M M i=1 sg j i (x) * G σ . • Obtain the weighted marginal pdf mpdf (x) = L j=1 w j pdf j (x), with w j = 1/L, j ∈ [1, . . . , L] in MIS and w j equal to the inertia axes in FIS.

The vectorial pdf vpdf is obtained as follows:

• For the vectorial gradient d (f λ ), throw M × L realizations of N uniform random germs, i.e. the markers {mrk i } i=1...M ×L , with L the channels number. Get the segmentation, {sg i (x)} i=1...M ×L , by watershed associated to the vectorial gradient d (f λ ), with

d = d χ 2 in MIS or d = d E in FIS. • Obtain the probability density function vpdf (x) = 1 M ×L M ×L i=1 sg i (x) * G σ .
The probabilistic vectorial gradient is defined as prob = mpdf + d : after normalization in [0, 1] of the weighted marginal pdf mpdf and the metric-based gradient d .

After computing them, these three functions are used as a gradient g of a new watershed with volume constraint R, i.e. the R regions with the largest volume, to obtain the segmentation contours of the image.

Application: unsupervised segmentation of multi-band satellite images

We compare 4 methods of segmentation in MIS based on the volume-based watershed on functions used as a gradient g. g takes several values, giving the associated watershed segmentations, such as: the chi-squared metric based gradient χ 2 : seg vol ( χ 2 (f λ ), R) (the reference segmentation), the weighted marginal pdf mpdf : seg vol (mpdf (f λ ), R), the vectorial pdf vpdf : seg vol (vpdf (f λ ), R), and the probabilistic gradient prob : seg vol ( prob (f λ ), R). The results are presented in synthetic RGB images made with channels f λ3 red, f λ2 green and f λ1 blue. Besides, more details are available in [START_REF] Angulo | Stochastic watershed segmentation[END_REF] about the execution time and the influence of the three parameters on the number: of realizations M , of regions R and of germs N .

In figure 3, we notice that the segmentation results are much better (i.e. more homogenous in space) for the watershed on probabilistic functions (mpdf , vpdf , prob ) than on the standard vector gradient χ 2 , which is used for the classical watershed. Therefore the stochastic watershed is better than the classical one. Besides, the probabilistic gradient prob , which combines a vectorial gradient d and the weighted marginal pdf mpdf , is adapted to segment the 1st order contours (the largest regions) and recover some of the 2nd order contours (the "small", "low" contrasted or textured regions).

Moreover, we have tested in the factor image space (FIS) the watershed with a volume constraint (fig. 4). As explained before, we will only use the first factor axis. As we keep only the first factor axis, the Euclidian metric based gradient E is very close to the morphological gradient. We compute the watershed segmentation on the functions used as gradients g: the morphological gradient : seg vol ( (c f α1 ), R), the weighted marginal pdf mpdf (i.e; the morphological gradient pdf): seg vol (mpdf (c f α1 ), R) and the probabilistic gradient prob : seg vol ( prob (c f α1 ), R). We notice that the contours on morphological gradient are comparable to those on weighted marginal pdf mpdf and on probabilistic gradient prob . In fact, due to FCA, the noise is rejected on the factor axes of smaller inertia [START_REF] Green | A Transformation for Ordering Multispectral Data in terms of Image Quality with Implications for Noise Removal[END_REF][START_REF] Noyel | Morphological Segmentation of hyperspectral images, Submitted to Image Analysis and Stereology[END_REF]. However segmentations of 1st order contours on mpdf and prob visually seems a bit better than on . Therefore, working on the firsts axes improves the segmentation as they contain less noise. Besides, by observing several segmentation results in various images (fig. 5), we notice that segmentations on weighted marginal pdf mpdf have contours more regular than on vectorial pdf vpdf . Consequently, the weighted marginal pdf mpdf seems to be the best approach for extracting area with smooth contours, like roads, buildings, fields, ... in satellite images.

χ 2 (f λ ) mpdf (f λ ) vpdf (f λ ) prob (f λ ) seg vol ( χ 2 (f λ ), R) seg vol (mpdf (f λ ), R) seg vol (vpdf (f λ ), R) seg vol ( prob (f λ ), R)
(c f α 1 ) mpdf (c f α 1 ) prob (c f α 1 ) seg vol ( (c f α 1 ), R) seg vol (mpdf (c f α 1 ), R) seg vol ( prob (c f α 1 ), R)

Conclusions and perspectives

We have shown the interest of using stochastic watershed segmentation to unsupervised segment multispectral images. Several variants are available to calculate the functions used as gradient g for the watershed segmentation: a weighted marginal pdf mpdf , a vectorial pdf vpdf or a probabilistic gradient prob . These gradients like functions are used for stochastic watershed to improve the classical watershed applied on a vector gradient. In fact, the weighted marginal pdf gives the best segmentation results and the probabilistic gradient is useful to find the principal and the secondary contours. Moreover, working in factorial image space FIS is generally better for segmentation than working in multispectral image space MIS. In the future we are thinking of using regionalized germs to build the pdf in order to segment a target in an image.

3 Fig. 1 .

 31 Fig. 1. Channels of multispectral image f λ "Roujan", synthetic RGB representation, FCA factors pixels c f α on axes 1,2 and 3 with respective inertias 84.1 %, 8.7 %, 6.2 %

Fig. 3 .

 3 Fig. 3. Top: Gradients and pdf; bottom: associated watershed segmentations on image "Roujan", in MIS, with N = 50 points , M = 100 realizations, R = 50 regions.

Fig. 4 .

 4 Fig. 4. Segmentation watershed in FIS with N = 50 points, M = 100 realizations and R = 50 regions.

Acknowledgments: The authors are grateful to Prof. Guy Flouzat (Laboratoire de Télédétection à Haute Résolution, LTHR/ ERT 43 / UPS, Université Paul Sabatier, Toulouse 3) for his collaboration on PLEIADES satellite simulated images in the framework of ORFEO program (Centre National d'Etudes Spatiales, the French space agency).