Nathalie Aubrun

Marie-Pierre Béal

Sofic and Almost of Finite Type Tree-Shifts

HAL is

Introduction

In a previous article [START_REF] Aubrun | Decidability of conjugacy of tree-shifts of finite type[END_REF], we introduced the notion of tree-shifts of finite type defined as sets of infinite trees avoiding a finite number of forbidden patterns. Infinite trees have a natural structure of one-sided symbolic systems equipped with several shift transformations. The ith shift transformation applied to a tree gives the subtree rooted at the child number i of the tree. Tree-shifts are highly interesting to study as they constitute an intermediate class between one-sided shifts of infinite sequences and multidimensional shifts.

The conjugacy of multidimensional shifts of finite type, also called textile systems or tiling systems (see for instance [START_REF] Lind | Symbolic and algebraic dynamical systems[END_REF], [START_REF] Nasu | Textile Systems for Endomorphisms and Automorphisms of the Shift[END_REF], [START_REF] Johnson | The decomposition theorem for twodimensional shifts of finite type[END_REF], [START_REF] Coven | The symbolic dynamics of multidimensional tiling systems[END_REF]), is undecidable. However, the conjugacy of (one-sided) shift spaces of finite type of infinite sequences is decidable ( [START_REF] Williams | Classification of subshifts of finite type[END_REF], see also [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]). In [START_REF] Aubrun | Decidability of conjugacy of tree-shifts of finite type[END_REF], we extended William's result to trees, showing that the conjugacy of irreducible tree-shifts of finite type is decidable.

In this paper, we focus on sofic tree-shifts, which are shifts of infinite trees accepted by finite (bottom-up) tree automata, and thus whose set of patterns is a recognizable set of finite trees. The goal is to extend to trees some results of sofic shifts of infinite sequences, to define a hierarchy a sofic tree-shifts and characterize each level of this hierarchy.

We introduce the notion of irreducible sofic tree-shifts. We show, that, unlike for sofic shifts of sequences, an irreducible sofic tree-shift may be accepted by several minimal deterministic irreducible tree automata. This is due to the lack of a synchronizing block, even in minimal irreducible automata. We introduce the notion of synchronized tree automaton and the notion of Shannon cover of an irreducible sofic tree-shift. We prove that the Shannon cover is the unique minimal synchronized tree automaton accepting an irreducible sofic tree-shift.

The existence of the Shannon cover allows us to introduce the class of almost finite type tree-shifts, which extends the known notion of almost of finite type shifts of sequences. The almost of finite type concept was introduced by Marcus in [START_REF] Marcus | Sofic systems and encoding data[END_REF] for coding purposes. The class of almost of finite type shifts is a meaningful class of shifts between irreducible shifts of finite type and irreducible sofic shifts (see [START_REF] Boyle | A note on minimal covers for sofic systems[END_REF], [START_REF] Williams | Covers of non-almost-finite type sofic systems[END_REF], [START_REF] Jonoska | Minimal presentations for irreducible sofic shifts[END_REF], [START_REF] Béal | A hierarchy of shift equivalent sofic shifts[END_REF], [START_REF] Bates | Reducibility of covers of AFT shifts[END_REF]). The class contains strictly the class of irreducible shifts of finite type and is strictly contained in the class of sofic shifts. The class is stable by conjugacy and it is also invariant by a flow equivalence [START_REF] Fujiwara | Sofic systems and flow equivalence[END_REF]. We characterize the Shannon cover of an almost of finite type tree-shift and design an algorithm to check whether a sofic tree-shift is almost of finite type.

The paper is organized as follows. In Section 2.1 and Section 2.2, we give basic definitions about tree-shifts and conjugacies. In Section 3, we define the notion of automaton accepting a tree-shift. We refer to [START_REF] Comon | Tree automata techniques and applications[END_REF], [START_REF] Thomas | Automata on infinite objects[END_REF], [START_REF] Perrin | Infinite words[END_REF] for more general trees and automata on finite and infinite trees. The notion of Shannon cover is introduced in Section 3.4. The characterization of almost of finite type tree-shifts is done in Section 4. In the algorithmic issue, Section 5, we give a construction of the Shannon cover of a sofic tree-shift. We design a polynomialtime algorithm to check whether a sofic tree-shift given by its Shannon cover is almost of finite type. Some proofs are omitted in this version of the paper.

Definitions

Tree-shifts

We first recall some basic definitions of symbolic dynamics on infinite trees (see [START_REF] Aubrun | Decidability of conjugacy of tree-shifts of finite type[END_REF] for more details). We consider infinite trees whose nodes have a fixed number of children and are labeled in a finite alphabet. We restrict to binary trees, but all result extend to the case of trees with d children for all d ≥ 1.

Let Σ = {0, 1}. An infinite tree t over a finite alphabet A is a complete function from Σ * to A. Unless otherwise stated, a tree is an infinite tree. A node of a tree is a word of Σ * . The empty word, that corresponds to the root of the tree, is denoted by ǫ. If x is a node, its children are xi with i ∈ Σ. Let t be a tree and let x be a node, we shall denote t(x) by t x . When Σ is fixed, we denote by T (A) the set of all infinite trees on A, hence the set A Σ * .

We define the shift transformations σ i for i ∈ Σ from T (A) to itself as follows. If t is a tree, σ i (t) is the tree rooted at the i-th child of t, i.e. σ i (t) x = t ix for all x ∈ Σ * . The set T (A) equipped with the shift transformations σ i is called the full shift of infinite trees over

A. A sequence of words (x k ) k≥0 of Σ * is called a path if for all k, x k+1 = x k i k with i k ∈ Σ.
A pattern is a function p : L → A, where L is a finite prefix-closed 1 subset of Σ * . The set L is called the support of the pattern. A block of height n is a pattern with support Σ ≤n , where n is some nonnegative integer, and Σ ≤n denotes the words of length at most n of letters of Σ. The height of a block u is denoted by height(u). A leaf of a pattern is a node with no child.

We say that a block u of support L is a block of a tree t if there is a word x ∈ Σ * such that t xy = u y for all words y ∈ Σ * . We say that u is a block of t rooted at the node x. If u is not a block of t, one says that t avoids p.

We define a tree-shift space (or tree-shift) X of T (A) as the set X F of all trees avoiding each element of a set of blocks F. If the set of trees on A is equipped with the usual product topology, where the topology in A is the discrete one, a tree-shift space is closed and invariant for any shift transformation σ i . A treeshift of finite type (SFT) X of T (A) is a set X F of all trees avoiding each block of a finite set of blocks F. The set F is called a set of forbidden blocks of X.

We denote by L(X) the set of patterns of all trees of the tree-shift X, by B(X) the set of all blocks of X and by B n (X) the set of all blocks of height n of X. If u is a block of height n with n ≥ 1, we denote by σ i (u) the block of height n -1 such that σ i (u) x = b ix for x ∈ Σ ≤n-1 . The block u is written u = (u ε , σ 0 (u), σ 1 (u)).

Example 1. In Figure 1 is pictured an infinite tree of a tree-shift X on the alphabet {a, b}. The forbidden blocks are those containing an even number of a between two b on any path in the tree. This tree-shift is not of finite type. Fig. 1. An infinite tree of the tree-shift XF , where F is the set of patterns containing an even number of a between two b on any path in the tree.

Block maps and conjugacies

Let A, A ′ be two finite alphabets, X be a tree-shift of T (A) and m be a positive integer. A map Φ : X ⊆ T (A) → T (A ′ ) is called an m-local map (or an m-block map) if there exists a function φ : B m (X) → A ′ such that, for all x ∈ Σ * , Φ(t) x = φ(t xΣ ≤m-1 ), where t xΣ ≤m-1 is the block q such that q y = t xy for all y ∈ Σ ≤m-1 . The smallest integer m -1 such that Φ is an m-block map, is called the memory of the block map. A block map is a map which is an m-block map for some nonnegative integer m. The image of X by a block map is also a tree-shift, and is called a factor of X. A one-to-one and onto block map from a tree-shift X onto a tree-shift Y has an inverse which is also a block map, as for shifts of sequences. It is called a conjugacy from X onto Y . The tree-shifts X and Y are then conjugate. We call sofic a tree-shift which is a factor of a tree-shift of finite type.

Let X be a tree-shift and m a positive integer. We denote by X (m) the higher block presentation of X. It is a tree-shift on the alphabet B m (X). For each tree t in X (m) , there is tree t ′ in X such that, for each node x, t x is the block of height m of t ′ rooted at x. The shifts X and X (m) are conjugate (see [START_REF] Aubrun | Decidability of conjugacy of tree-shifts of finite type[END_REF]).

3 Sofic tree-shifts

Tree automata

In this section we consider bottom-up automata of infinite trees. Such an automaton starts its computation from the infinite branches and moves upward. A tree automaton is here a structure A = (V, A, ∆) where V is a finite set of states, A is a finite set of input symbols, and ∆ is a set of transitions of the form (q 0 , q 1 ), a → q, with q, q i ∈ V , a ∈ A. A transition (q 0 , q 1 ), a → q is called a transition labeled by a, going out of the pair of states (q 0 , q 1 ) and coming in the state q. A transition (q 0 , q 1 ), a → q will be pictured by a : q q 0 q 1

Note that no initial nor final states are specified. This means that all states are both initial and final. Such an automaton is deterministic if for each pair of states (q 0 , q 1 ) and for each a ∈ A, there is at most one transition (q 0 , q 1 ), a → q. Then the set of transitions defines a partial function δ from V 2 × A to V .

A (bottom-up) computation of A on the infinite tree t is an infinite tree C on V such that, for each node x, there is a transition

(C x0 , C x1 ), t x → C x ∈ ∆.
A tree t is accepted by A if there exists a computation of A on t. The set of infinite trees accepted by A is a tree-shift. Given a tree automaton A, it is always possible to transform it into a deterministic tree automaton which accepts the same set of trees (this process is called determinization, see for instance [START_REF] Comon | Tree automata techniques and applications[END_REF] for details). In the sequel, we assume that all states of an automaton are accessible, i.e. each state ends some computation of the automaton.

A (bottom-up) finite computation of A on the complete finite tree t is a complete finite tree C on V such that, for each node x which is not a leaf, there is a transition

(C x0 , C x1 ), t x → C x ∈ ∆.
A tree automaton is called an edge tree automaton is all transitions have distinct labels. An edge tree-shift is a tree-shift (of finite type) accepted by an edge tree automaton.

Example 2. We define a tree automaton A with three state q b , q 0 and q 1 which accepts the tree-shift X of Example 1. The two states q 0 and q 1 only label nodes with an a, and they control the parity of the number of a encountered from any last b below. The state q b only labels nodes with a b. The transitions of the tree automaton A are a : q 1 q 0 q 0 a : q 0 q 1 q 1 a : q 0 q b , q 1 q b , q 1 b : q b q b , q 1 q b , q 1

The proofs of the following proposition is similar to the one for shifts of infinite or bi-infinite sequences (see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF], [START_REF] Kitchens | Symbolic dynamics. Universitext[END_REF]). Proposition 1. A tree-shift is sofic if and only if it is accepted by a tree automaton.

Irreducible tree-shifts

In this section, we define a notion of irreducibility which is suitable for tree-shifts.

A finite complete prefix code of Σ * is a prefix set2 P of finite words in Σ * such that each word of Σ * longer than the words of P has a prefix in P .

A tree-shift X is irreducible if for each pair of blocks u, v ∈ B(X), there is a tree t in X and a finite complete prefix code P ⊂ Σ ≥height(u) , such that u is a subtree of t rooted at ε, and v is a subtree of t rooted at x for all x ∈ P . q q q q p Fig. 2. (left) An irreducible tree-shift. Let t denotes the tree pictured. If u denotes the black block and v the white one, u is a subtree of t rooted at ε, and v is a subtree of t rooted at each x ∈ P , where P is the complete prefix code {00, 010, 011, 1}. (right) An hyperpath from q to p in a tree automaton.

A tree automaton is irreducible if for each pair of states p, q, there is a finite complete prefix code P of Σ * and a finite computation C of the automaton on a pattern u such that C ε = p and C x = q for each x ∈ P . We say in this case that there is an hyperpath from q to p labeled by u. For two states p, q of a tree automaton, we say that p is accessible from q if there is a hyperpath from q to p. Proposition 2. An irreducible automaton accepts an irreducible sofic tree-shift. Conversely, for any irreducible sofic tree-shift, there is an irreducible automaton accepting it. Proposition 3. Let S and T be two conjugate tree-shifts. Then S is irreducible if and only if T is irreducible.

Synchronizing blocks

We define below the notion of synchronizing block3 of a deterministic tree automaton.

Let A = (V, A, ∆) be a deterministic tree automaton accepting a sofic treeshift X, and u be a block (resp. pattern). We say that u is a synchronizing block (resp. pattern) of A if all computations of A on u terminate at the same state q ∈ Q. We say that u focuses to the state q. A deterministic tree automaton which has a synchronizing block is called synchronized.

Minimal deterministic tree automata

Let X be a tree-shift. A context c is a finite pattern with a marked leaf. If u is a pattern, c(u) is the pattern c where the marked leaf is replaced by u. If c(u) ∈ L(X), we say that c is a context of u in X. Given a block u, we denote by cont X (u) the set of all the contexts of u in X.

Given a tree automaton A = (V, A, ∆) accepting a sofic tree-shift X, the context of a state q ∈ V in A is the set of patterns u with a marked leaf x on which there exists a finite computation C of A with C x = q and x is a leaf of C. We denote it by cont A (q). Note that the context of a pattern u of X is the union of the contexts of the states p such that there is a computation of A on u ending in p. As a consequence, a sofic tree-shift has only a finite number of distinct contexts.

Let A = (V, A, ∆) be a deterministic automaton accepting a sofic tree-shift X. We denote by δ(p, q, a) the unique state r such that (p, q), a → r ∈ ∆ when such a transition exists. We define a deterministic automaton M A accepting X called the minimization of the automaton A as follows. The states of M A are the classes of the coarsest partition of V such that if p, q belong to the same class, then for each letter a and each state r, δ(p, r, a) and δ(q, r, a) (resp. δ(r, p, a) and δ(r, q, a)) belong to the same class, and δ(p, r, a) (resp. δ(r, p, a)) is defined if and only if δ(q, r, a) (resp. δ(r, q, a)) is defined. Let [p] denotes the class of the state p. The transition ([p], [q]), a → [δ(p, q, a)] is a transition of M A if and only if δ(p, q, a) is defined. It can be shown that this definition is consistent, i.e. does not depend on the choice of the leader in each class. A deterministic automaton is minimal if it is equal to its minimization.

For any deterministic tree automaton, two states in a same class have the same context. If A is moreover irreducible and synchronized, it is minimal if and only if any two states have distinct contexts.

The minimization algorithm for deterministic tree automata accepting languages of finite trees, which is for instance described in [5, Section 1.5], can be applied to the tree automata accepting tree-shifts. Remember that all states in tree automata accepting tree-shifts are both initial and final.

In the framework of shifts of bi-infinite words, irreducible sofic shifts have a unique minimal deterministic automaton (i.e. all minimal deterministic automata accepting the shift are equal up to a renaming of the states), see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF].

The situation is quite different for trees since, as is shown below in Example 3, irreducible sofic tree-shifts may have several minimal deterministic tree automata. Indeed, contrary to the situation that we have for shifts of infinite or bi-infinite sequences, an irreducible minimal deterministic tree automaton may not have a synchronizing block.

Example 3. Let X be the full tree-shift on the alphabet A = {a, b}. It is accepted by a trivial one-state automaton. It is also accepted by the deterministic irreducible tree automaton A = (V, A, δ) described by the following transitions and which is minimal.

a : p 1 p 0 p 0 a : q 1 q 0 q 0 b : p 1 p 0 p 0 b : p 1 p 1 p 1 b : q 1 p 1 q 1 a : q 0 p 1 p 1 a : p 1 p 1 q 1 a : q 1 q 1 p 1 a : p 0 q 1 q 1
One can overcome this difficulty with the notion of Shannon cover for irreducible tree-shifts.

Let X be a sofic tree-shift. The context tree automaton of X is the deterministic automaton S = (V, A, ∆), where V is set of contexts of finite blocks of X. Since X is sofic, V is finite. The transitions of S are (cont X (u), cont X (v)), a → cont X (a, u, v), where u, v ∈ B(X). Proposition 4. The context tree automaton of a sofic tree-shift is synchronized.

Proof. Let S be the context tree automaton of a sofic shift X. There is a finite computation C 1 in S on some block u 1 ending in cont X (u 1 ). Let us assume that u 1 is not a synchronizing block of S. Hence there is another computation C 2 of S on u 1 ending in cont X (u 2 ) for some block u 2 = u 1 . We get cont X (u 2 ) cont X (u 1 ) since cont X (u 2 ) = cont X (u 1 ). If u 2 is not a synchronizing block of S, there is another computation C 2 of S on u 2 ending in cont X (u 3 ). We get cont X (u 3 ) cont X (u 2 ). By iterating this process, we either get a synchronizing block for S or an infinite strictly decreasing sequence of contexts. Hence, since the number of contexts is finite, there is a synchronizing block.

We define the Shannon cover of an irreducible sofic tree-shift X as the unique irreducible component S of its context tree automaton C obtained by keeping the states accessible from cont C (z), where z is a synchronizing block of C. Since z is synchronizing and C is deterministic, each state in this component is the context of some synchronizing block.

Let us show that the states accessible from cont C (z) form an irreducible component and that it is the unique irreducible component of S. It is enough to prove that there is a hyperpath from any state to cont C (z). Let p = cont C (u) be a state. Since X is irreducible, there is a pattern w of X and a finite complete prefix code P of Σ ≥height(z) , such that z is a subtree of w rooted at ε, and u is a subtree of w rooted at x for all x ∈ P . Let C be a computation of C on w.

We have C ε = cont C (z), and for all x ∈ P , C x = p. Hence there is an hyperpath from p to cont C (z). Finally, it is easy to check that the automaton S accepts X by using the irreducibility of X.

We now prove that the Shannon cover is the unique minimal deterministic irreducible and synchronized tree automaton accepting an irreducible sofic treeshift.

Proposition 5. Two minimal deterministic irreducible and synchronized tree automata accepting the same irreducible sofic tree-shift are equal up to a renaming of the states.

Almost of finite type tree-shifts

The following notion of almost of finite type tree-shift extends to trees the notion of almost of finite type shift of bi-infinite sequences. The class contains strictly the class of irreducible tree-shifts of finite type and is strictly contained in the class of irreducible sofic tree-shifts.

Let X, Y be two tree-shifts. A block map Φ : X → Y is left closing if there are non negative integers m, a (m for memory and a for anticipation) such that, whenever

Φ(s) = s ′ , Φ(t) = t ′ with s ′ x = t ′
x for all x ∈ Σ i with 0 ≤ i ≤ (a+1+m), and s x = t x for all x ∈ Σ i with 0 ≤ i ≤ a, then s x = t x for any x ∈ Σ (a+1) . The map Φ is left resolving if m can be chosen equal to 0.

A tree automaton A = (V, A, ∆) is left closing if any two computations of A on a same tree and ending in a same state are equal. Equivalently, there is a nonnegative integer m such any two finite computations

C, C ′ of A on a same block u ∈ B m+1 (X) such that C ε = C ′ ε satisfy C x = C ′
x for all x ∈ {0, 1}. Hence a deterministic and left closing tree automaton corresponds, for trees, to the notion of automata of words which are both deterministic and co-deterministic with a finite delay.

A block map Φ : X → Y is right closing if there are non negative integers m, a such that, whenever Φ(s) = s ′ , Φ(t) = t ′ with s ′ x = t ′ x for all x ∈ Σ i with 0 ≤ i ≤ (a + 1 + m), and s x = t x for all x ∈ Σ i with a + 1 ≤ i ≤ (a + 1 + m), then s x = t x for all x ∈ Σ a . The map Φ is right resolving if a can be chosen equal to 0.

Let X be a tree-shift. Let u be a block in B m (X). A cylinder C[u] of X with basis u is the set of trees t in X such that t x = u x for all x ∈ Σ * of length at most m.

A sofic tree-shift is almost of finite type (AFT) if it is the image of an irreducible tree-shift of finite type via a block map which is right resolving, left closing, and is one-to-one on a cylinder (equivalently, the map is one-to-one on a non trivial open set). Proposition 6. Let S and T be two conjugate irreducible sofic tree-shifts. Then S is AFT if and only if T is AFT.

Proof. (sketch) It is easy to check that the composition of a right resolving map with a conjugacy is still right resolving. The composition of a left closing map with a conjugacy is still left closing. A conjugacy also keeps the property of being one-to-one on a cylinder. We say that an automaton is an almost of finite type automaton (AFT automaton) if it is deterministic, irreducible, left closing and synchronized. Proposition 7. A tree-shift is AFT if and only if it is accepted by an AFT automaton.

Proof. Let S be an AFT tree-shift on the alphabet A. Let Φ : X → S be a block map from an irreducible tree-shift of finite type X onto S which is right resolving, left closing and one-to-one on a cylinder of S. Without loss of generality (by changing X into a higher block presentation of X), we can assume that X is an edge tree-shift and that Φ is a one-block map. Again by changing X into a higher block presentation of X, we can assume that Φ is left closing with parameters a ′ = 1, m ′ .

Let A = (V, E, ∆) be an irreducible edge tree automaton accepting X. Let B = (V, A, ∆ ′ ) where (p, q, φ(e), r) ∈ ∆ ′ if and only if (p, q, e, r) ∈ ∆.

Since Φ is a one-block right-resolving map (with some parameter m), B is a deterministic automaton.

We now prove that B has a synchronizing block. Since Φ is one-to-one on a cylinder C[z 0 ] of S, for any tree t ∈ C[z 0 ], any two computations of B on t are equal and thus end in a same state p. As a consequence, and by compacity arguments, there is a finite subtree z such that z 0 is a subtree of z at ε and such that each finite computation of B on z ends in the same state p z , i.e. z is a synchronizing block of B. Let us keep in B only the states accessible from p z . Since S is irreducible, B remains irreducible and still accepts S.

Let us now show that B is left closing. If B were not left closing, there would be two distinct computations C, C ′ of B on a same tree t ending in a same state p. Let (p, q, e, r) ∈ ∆ a transition going out of (p, q) for some states p, r ∈ V (if there is none, there is a transition going out of (q, p) since A is irreducible). We get two distinct computations (r, C, D), (r, C ′ , D) of B ending in r on a same tree u = (φ(e), t, t ′ ) for some tree t ′ . These two distinct computations of B are also two distinct computations of A on two trees s, s ′ of X with s ε = s ′ ε = e and such that Φ(s) = Φ(s ′ ) = u. Since Φ is left closing with parameters a ′ = 1, m ′ , we get s = s ′ and thus C = C ′ .

Conversely, if S is accepted by an AFT automaton A = (V, A, ∆), let X be the edge tree-shift accepted by T = (V, ∆, ∆ ′ ), whose transitions are (p, q, (p, q, a, r)) → r for (p, q, a, r) ∈ ∆. Let Φ be the one-block map from X onto S defined by φ(p, q, a, r) = a. This map is right resolving since A is deterministic. It is left closing since A is left closing. It is one-to-one on a cylinder since A is synchronized. As a consequence, S is AFT.

Corollary 1. An irreducible sofic tree-shift is AFT if and only if its Shannon cover is AFT.

Proof. Let X be an irreducible sofic tree-shift. By Proposition 5, any irreducible sofic tree-shift is accepted by an irreducible deterministic synchronized automaton S equal to the Shannon cover of X.

Let us assume that X is AFT. By Proposition 7, S is equal to the minimization of an AFT automaton A. Let us show that S is left closing. If it is not left closing, then there is a tree t ∈ X and two distinct computations of S on t ending in a same state. As a consequence, there are two distinct computations of A on t ending in two states p, p ′ which have the same context.

Let z be a synchronizing pattern of A focusing to the state q z . Since A is irreducible, there is an hyperpath from p to q z labeled by some pattern w such that z is a subtree of w rooted at ε. Since p and p ′ have the same context, there is also a hyperpath from p ′ to q labeled by w. Since z is synchronizing, q = q z . This gives two distinct computations of A on a same tree ending in the same state q z , which contradicts the fact that A is left closing. This proves that the Shannon cover of an AFT is left closing.

Conversely, if S is AFT, then X is AFT by Proposition 7.

Corollary 2. Let S be an irreducible sofic shift accepted by a deterministic tree automaton. It is decidable whether S is AFT.

Proof. One can compute the Shannon cover of the sofic tree-shift and check whether it is AFT as explained in Section 5.

The algorithmic issue

In this section, we design algorithms to check whether a deterministic tree automaton is synchronized, and whether it is left closing. We also describe an algorithm to compute the Shannon cover of an irreducible sofic tree-shift given by a deterministic tree automaton that accepts it.

Computation of the Shannon cover

Let A = (V, A, δ) be a deterministic automaton. We define the deterministic tree automaton D(A) as the accessible part from the state V of the tree automaton (P(V ), A, δ ′ ), where for, P, Q ∈ P(V ), δ ′ (P, Q, a) = {δ(p, q, a) | p ∈ P, q ∈ Q} if this set is nonempty, and is not defined otherwise.

Proposition 8. It can be checked in polynomial time whether a tree automaton is irreducible.

Proposition 9. It is decidable whether a deterministic tree automaton is synchronized.

Proof. The automaton A is synchronized if and only if D(A) contains a singleton state. The time and space complexity of this algorithm is exponential in the number of states of A.

Proposition 10. Let A = (V, A, δ) be a deterministic automaton accepting an irreducible sofic tree-shift X. The Shannon cover of X is computable from A.

Proof. Let D(A) = (P(V ), A, δ ′ ) and R be a minimal state of D(A) for the inclusion. Let u the label of a hyperpath from V to R. Then u a synchronizing pattern of D(A). Indeed, any finite computation of D(A) ends in R by minimality of R. We keep in D(A) only the states accessible from R and get an irreducible and synchronized automaton accepting X. Its minimization gives the Shannon cover of X by Proposition 5.

We now describe algorithms to check whether an irreducible deterministic automaton is left closing.

The pair graph of a tree automaton

Given a deterministic tree automaton A = (V, A, ∆), we define the square automaton of A, denoted by A × A = (V × V, A, ∆ ′ ), as the deterministic automaton whose transitions are (p, p ′ ), (q, q ′ ), a → (r, r ′ ) if and only if (p, q), a → r and (p ′ , q ′ ), a → r ′ are transitions of A. A diagonal state of A × A is a state (p, p) for some p ∈ V .

Square automata of finite words (see for instance [16, p. 647]) are used to check properties of pairs of paths. We extend this notion, together with a notion a pair graph, to trees, to check properties of pairs of computations. Seidl [START_REF] Seidl | On the finite degree of ambiguity of finite tree automata[END_REF] used branch automata to check the degree of unambiguity of finite tree automata. Proposition 11. A deterministic tree automaton is not left closing if and only if there is a computation in the square automaton ending in a diagonal state and containing a non diagonal one.

Proof. By definition of A × A, the existence of a computation in A × A ending in a state (p, p) and containing a state (r, s) with r = s is equivalent to the existence of two distinct computations of A on a same tree.

In order to check the above property, we build the pair graph

G A = (V G , E G ) of A, where V G ⊆ (V 2 ×V 2 )∪V 2 is the set of vertices, E G ⊆ V G ×{0, 1}×A×V G
is the set of edges labeled by 0 or 1 and a letter from A. For more convenience, an edge labeled by 1 is noted by a plain arrow -→ and is called a plain edge, and an edge labeled by 0 is noted by a dashed arrow and is called a dashed edge. For each pair of transitions (p, q), a → r and (p ′ , q ′ ), a → r ′ of A, ((r, r ′ ), (s, s ′ )) 0,a --→ ((p, p ′ ), (q, q ′ )), ((s, s ′ ), (r, r ′ ))

1,a --→ ((p, p ′ ), (q, q ′ )), (r, r ′ ) 0,a --→ ((p, p ′ ), (q, q ′ )), (r, r ′ ) 1,a --→ ((p, p ′ ), (q, q ′ )), are edges of G A , for each pair (s, s ′ ).

A vertex of G A is useful if it has at least one outgoing plain edge and at least one outgoing dashed edge. We keep the essential part of the pair graph obtained by discarding vertices which are not useful, and their incoming and outgoing edges. A vertex ((p, q), (r, s)) of G A is called non diagnonal if either p = q or r = s. Proposition 12. A deterministic tree automaton is not left closing if and only its there is a path in its pair graph starting at a vertex (p, p) and ending in a non diagonal vertex. Each vertex (p, q) is identified with the vertex (p, q)(p, q). For the test, the pair ((p, q), (r, s)) may not be represented if ((r, s), (p, q)) does. The tree-shift X accepted by A satisfies the property of Proposition 12 since there is no path from a diagonal state to a non diagonal one. Then A is a left closing automaton and as a consequence the tree-shift X is AFT.

The number of vertices of G A is at most O(|V | 4 ) and its number of edges of G A is at most O(|V | 6 ). The property of Proposition 12 can be checked in a linear time in the size of G A . As a consequence, it can be checked in polynomial time whether the Shannon cover of an irreducible sofic tree-shift is AFT. Note that Seidl's check of the finite degree of ambiguity of tree automata in [START_REF] Seidl | On the finite degree of ambiguity of finite tree automata[END_REF] has a similar complexity (the cube of the size of the transitions of the tree automaton). The pair graph for the tree automaton A of Example 1 is given in Figure 3.

Conclusion

In this article, we have shown that tree-shifts differ from one-sided shifts of infinite sequences at least concerning the following property: there may be more than one minimal deterministic irreducible tree automata accepting the same irreducible sofic tree-shift. The reason is that such automata do not always have a synchronizing block. For irreducible sofic tree-shifts, the Shannon cover remedy for this lack and allows us to define the class of almost finite type tree-shifts. In further work we will focus on topological and syntactic properties of AFT tree-shifts.

(Fig. 3 .

 3 Fig.3. The pair graph for the tree automaton of Example 1. A thick edge represents a plain edge and a dashed edge with the same label. The non useful edges and vertices are drawn in grey. Each vertex (p, q) is identified with the vertex (p, q)(p, q). For the test, the pair ((p, q), (r, s)) may not be represented if ((r, s), (p, q)) does. The tree-shift X accepted by A satisfies the property of Proposition 12 since there is no path from a diagonal state to a non diagonal one. Then A is a left closing automaton and as a consequence the tree-shift X is AFT.

each prefix of L belongs to L.

i.e. no word is prefix of another one.

also called a homing pattern or a magic pattern.


Guillaume Blin
email: gblin@univ-mlv.fr

Maxime Crochemore
email: maxime.crochemore@univ-mlv.fr

Sylvie Hamel
email: sylvie.hamel@umontreal.ca

Stéphane Vialette
email: vialette@univ-mlv.fr

Finding the median of three permutations under the Kendall-tau distance

  L'archive ouverte pluridisciplinaire

Indroduction

The problem of finding the median of a set of m permutations of [n] under the Kendall-τ distance is best known in the literature as the Kemedy Score Problem. In this problem we have m voters that have to order n candidates from their best-liked candidate to their least-liked one. The problem then consist in finding a "Kemedy consensus", i.e, an order of the candidates that agree the most with the order of the m voters, i.e., that minimizes the sum of the disagreements. This problem has been proved to be NP-complete when m ≥ 4 [START_REF] Dwork | Rank Aggregation Methods for the Web[END_REF] (the complexity is unknown for m = 3 and polynomial-time solvable for m = 2) and some approximation algorithms have been derived. First, a randomized algorithm with approximation factor 11/7 [START_REF] Ailon | Aggregating inconsistent information: Ranking and clustering[END_REF] and then a deterministic one with approximation factor 8/5 [START_REF] Williamson | Deterministic algorithms for rank aggregation and other ranking and clustering problems[END_REF]. In 2007, a PTAS result has been obtained [START_REF] Kenyon-Mathieu | How to rank with few errors[END_REF] and a year later, some fixed-paramater algorithms have been described [START_REF] Betzler | Fixed-Parameter Algorithms for Kemeny Scores[END_REF]. Here, we focus on m = 3.

This article is organized as follow. In Section 2, we gives some basic definitions for the problem. In Section 3, we show how we can reduce the search space for the brute force algorithm by deriving some combinatorial properties of the median. Finally we present our heuristic and what still need to be done in section 4 and 5. This work is a work in progress. Since it is an extended abstract, all the proofs has been omitted but are available on request.

Definitions and Notations

A permutation π is a bijection of [n] = {1, 2 . . . , n} onto itself. The set of all permutations of [n] is denoted S n . As usual we denote a permutation π of [n] as ⋆ supported by NSERC through an Individual Discovery Grant π = π 1 π 2 . . . π n . The identity permutation correspond to the identity bijection of [n] and is denoted ı = 12 . . . n. A pair (π i , π j ) of elements of the permutation π is called an inversion if π i > π j and i < j. The number of inversion of a permutation π is denoted inv(π). 1The Kendall-τ distance, denoted d KT , counts the number of pairwise disagreements between two permutations and can be defined formally as follows: for permutations π and σ of [n], we have that

d KT (π, σ) = |(i, j) : i < j and [(π[i] < π[j] and σ[i] > σ[j]) or (π[i] > π[j] and σ[i] < σ[j])|,
where π[i] denote the position of integer i in permutation π. Note that we can easily computed inv(π) as inv(π) = d KT (π, ı). The problem consider in this article will be called median of three problem under the Kendall-τ distance and can be stated as follow:

Given π 1 , π 2 and π 3 , we want to find π * such that

d KT (π * , π 1 )+d KT (π * , π 2 )+d KT (π * , π 3 ) ≤ d KT (π, π 1 )+d KT (π, π 2 )+d KT (π, π 3 ), for all π ∈ S n ,
In order to represent the disagreements between pairs of element in the median with respect to π 1 , π 2 and π 3 , we introduce here the notion of disagreements graph.

Definition 1 We call the disagreements graph of the median π

* = π * 1 π * 2 . . . π * n with respect to π 1 = π 1 1 . . . π 1 n , π 2 = π 2 1 . . . π 2 n and π 3 = π 3 1 . . . π 3 n , denoted G(π *
), the graph obtained from π * by drawing weighted edges between each pairs (π * i , π * j ), with i < j. The weight of an edge (π * i , π * j ), denoted w(π * i , π * j ), represent the number of disagreements of this pair in π * with the same pair of elements in π 1 , π 2 and π 3 , i.e., the distance contribution of this pair in the total Kendall-τ distance.

Example 1 Given π 1 = 2134, π 2 = 4123 and π 3 = 4231 we can compute (since here n is small) the median π * by choosing, in all permutation of 4 elements, the one that minimize the Kendall-τ distance. Doing that, we know here that the median is π * = 4213. The disagreements graph for this π * is given Figure 1.

Reducing the search space

When dealing with permutations, searching the whole set of permutations quickly becomes impossible since there are n! permutations of [n]. To be able to compare our heuristic with the brute force algorithm for permutations of [n] where n > 12, we need to reduce the search space so that the computation will take place in a reasonable time. Here, given three permutation π 1 , π 2 and π 3 , we derived some combinatorial properties of their median π * which will considerably reduce the search space.

Combinatorial properties of the median

Theorem 1 Let π * = π * 1 . . . π * n be the median of π 1 , π 2 and π 3 , three permutations of [n], with respect to the Kendall-τ distance. Then, for all pairs (i, j) such that i < j and

π k [i] < π k [j] for all 1 ≤ k ≤ 3, (respectively π k [i] > π k [j] for all 1 ≤ k ≤ 3), we have π * [i] < π * [j] (respectively π * [i] > π * [j]).
This first theorem states that all the pairs of elements that appears in the same order in π 1 , π 2 and π 3 should also appears in that order in the median π * . Note that this theorem has already been stated and proved in the area of applied finance and uses what they called an Extended Condorcet Criterion [START_REF] Truchon | An Extension of the Condorcet Criterion and Kemeny Orders, Internal Report[END_REF]. To the best of our knowledge, this is the first time that this result is proved in the context of permutations.

Theorem 2 Let π * = π * 1 . . . π * n be the median of π 1 , π 2 and π 3 , three permutations of [n], with respect to the Kendall-τ distance. Without loss of generality, suppose that π 1 is the permutation that is the closest of the two others, i.e,

d KT (π 1 , π 2 ) + d KT (π 1 , π 3 ) ≤ d KT (π 2 , π 1 )+d KT (π 2 , π 3 ) and d KT (π 1 , π 2 )+d KT (π 1 , π 3 ) ≤ d KT (π 3 , π 1 )+ d KT (π 3 , π 2 ). Then inv(π * ) ≤ inv(π 1 ) + inv(π 2 ) + inv(π 3 ) + d KT (π 1 , π 2 ) + d KT (π 1 , π 3 ) 3 and inv(π * ) ≥ inv(π 1 ) + inv(π 2 ) + inv(π 3 ) -d KT (π 1 , π 2 ) -d KT (π 1 , π 3 ) 3 .
Theorem 2 gives upper and lower bounds on the number of inversion in the median π * . This is really interesting since there exist a CAT-algorithm that computes all permutation of [n] having exactly k inversions [START_REF] Effler | A CAT algorithm for generating permutations with a fixed number of inversions[END_REF]. Table 1 compares the computation time needed to find the median of 3 permutations of [n], for 4 ≤ n ≤ 11, using 1) the brute force algorithm and 2) the brute force algorithm optimize by the results of Theorem 1 and 2.

Our heuristic

The idea of our algorithm is to apply a series of "good" cyclic movements on the starting permutations to make them closer to the median. Formally we have the following definitions and algorithm. Table 1. Running time, in seconds, of the brute force algorithm with and without the optimizations Definition 2 Given π = π 1 . . . π n , we call cyclic movement of a segment π[i..j] of π, denoted c[i, j](π), the cycling shifting of one position to the right (c r [i, j]) or to the left (c ℓ [i, j]) of the segment inside the permutation π:

c r [i, j](π) = π 1 . . . π i-1 π i+1 . . . π j π i π j+1 . . . π n , c ℓ [i, j](π) = π 1 . . . π i-1 π j π i . . . π j-1 π j+1 . . . π n
When j = i + 1, a cyclic movement correspond to a transposition.

Definition 3 Given three permutations π 1 ,π 2 and π 3 , we will say that a cyclic movement is a k-move if

3 m=1 d KT (c[i, j](π), π m ) = 3 m=1 d KT (π, π m ) + k. Definition 4 A good cyclic movement c[i, j] is a k-move, where k < 0.
This means that if we apply a good cyclic movement to π we obtain a permutation that is closer to the median than π, i.e., we have Theorem 3 Let π 1 ,π 2 and π 3 be three permutations. Let π be a starting permutation from which we want to derive π * , the median of π 1 ,π 2 and π 3 with respect to the Kendall-τ distance. We have that c r

[i, j](π) (resp. c ℓ [i, j](π)) is a k-move, k ∈ Z, iff j -i ≡ k mod 2 and j t=i+1 w G(π) (π i , π t ) resp. j-1 t=i w G(π) (π t , π j ) = 3(j -i) + k 2 .
Now, we present our heuristic whose pseudo-code is depicted in Figure 2. The idea is to begin our search for the median in any of the starting permutation π 1 , π 2 or π 3 and to apply good movements to this starting point till there is no more possible good movement. We apply three time our pseudo-code, with π = π m , 1 ≤ m ≤ 3 and our "median" is the best result we obtain from these three runs. We tested this heuristic on all possible triplets of premutations of [n] for 3 ≤ n ≤ 5, and on 2000 random triplets, for 6 ≤ n ≤ 12. Table 2 shows that the percentage of errors of our heuristic slowly increases from 0 to 1.6 %, as n increases from 3 to 12. Table 2 also shows that, in the case, when our heuristic does not find the real median π * , the difference between the Kendall-τ distance of our median and π * is always one.

Since this article is a work in progress, there is still a lot of question we need to answer. Stating only a few, we have the following ones: Starting in one permutation and applying any combinations of good and 0-moves, do we always end in the same permutation? Is our heuristic + 0-moves an exact algorithm and if so what is its complexity? Can we find combinatorial properties that will completely described the set of 0-moves that can make us move out of a local minimum?

Fig. 1 .

 1 Fig. 1. Disagreements graph of π * = 4213 with π 1 = 2134, π 2 = 4123 and π 3 = 4231.

3 m=1d

 3 KT (c[i, j](π), π m ) < 3 m=1 d KT (π, π m ). Theorem 3 gives us a way to easily find these good moves (in fact any k-move) on a starting permutation π by summing the weights of the edges, in the disagreements graph G(π) that are change by these moves.

Since the inversions are generators of Sn, we can view Sn with these generators as a Coxeter group. In this context, the number of inversions of a permutation π is called the length of π and is denoted by ℓ(π). See Chapter 5 of[START_REF] Humphreys | Reflection Groups and Coxeter Groups[END_REF] for more details.

Acknowledgements

We thanks Quentin Dejean and Anthony Estebe who programmed all the algorithms and tests as an internship project for their patience with our numerous demands and they really did great work.

Algorithm FindMedian (π, [π 1 , π 2 , π 3 ]) n ← length(π) bool ← 0 (will be change to 1 if there is no more possible "good" movement) chang ← 0 (will tells us if some movements where made) Considering 0-moves When our heursitic does not find the median π * , it means that we are stuck in a local minimum and there is no more possible good move that we can make. We decide in this case to apply a fixed number of 0-moves in hope that these moves will help us go out of the local minimum. Given a permutation π, we can easily find these 0-moves with Theorem 3. Among these 0-moves, if at least one has the property described in Theorem 4 we are guaranteed to move out of the local minimum. So, the 0-moves with this properties will be call "good".

Theorem 4 Let π 1 ,π 2 and π 3 be three permutations. Let π be a starting permutation from which we want to derive π * , the median of π 1 ,π 2 and π 3 with respect to the Kendall-τ distance.

To try to see if we always find the median π * by applying alternatively our heuristic and 0-moves (good or random), we tested this idea, with a permitted number of 0moves of at most 2, on 400 random triplets of permutations of [n], 7 ≤ n ≤ 14. In all of those computed examples, we did found the median π * .


Sławomir B Ąk

Etienne Corvee

Francois Brémond

Monique Thonnat

Multiple-shot Human Re-Identification by Mean Riemannian Covariance Grid

Human re-identification is defined as a requirement to determine whether a given individual has already appeared over a network of cameras. This problem is particularly hard by significant appearance changes across different camera views. In order to re-identify people a human signature should handle difference in illumination, pose and camera parameters. We propose a new appearance model combining information from multiple images to obtain highly discriminative human signature, called Mean Riemannian Covariance Grid (MRCG). The method is evaluated and compared with the state of the art using benchmark video sequences from the ETHZ and the i-LIDS datasets. We demonstrate that the proposed approach outperforms state of the art methods. Finally, the results of our approach are shown on two other more pertinent datasets.

Introduction

Human re-identification is one of the most challenging and important problems in computer vision and pattern recognition. Only knowledge about identities of tracked persons can allow a system to fully understand the scene. The human re-identification problem can be defined as a determination whether a given person of interest has already been observed over a network of cameras. This issue is also called the person re-identification problem.

Person re-identification can be considered on different levels depending on information cues which are currently available in the system. Biometrics such as face, iris or gait can be used to recognize identities. Nevertheless, in most video surveillance scenarios such detailed information is not available due to video low-resolution or difficult segmentation (crowded environments, e.g. airports, metro stations). Therefore a robust modeling of a global appearance of an individual is necessary to re-identify a given person of interest. In these identification techniques (named appearance-based approaches) clothing is the most reliable information about an identity of an individual (there is an assumption that individuals wear the same clothes between different sightings). The model of an appearance has to handle differences in illumination, pose and camera parameters to allow matching appearances of the same individual observed in different cameras.

The main topic of this paper is a novel appearance-based approach which builds a specific human signature model to re-identify a given individual. In our approach a human detection algorithm is used to find out people in video sequences. Then, the detected individual is tracked to gather as many frames as possible. Our method belongs to the group of multiple-shot approaches where multiple images of a person are used to extract discriminative signature.

This paper makes the following contributions:

• We propose to use the Mean Riemannian Covariance (MRC) matrices blending the appearance information from multiple images. This mean covariance matrix keeps not only information about feature distribution but also carries out essential cues about temporal changes of an appearance (Section 3.2).

• We offer a novel kind of feature, i.e., the Mean Riemannian Covariance Grid (MRCG) (Section 3.3). Our idea is to combine efficiency of the mean riemannian covariance descriptor with a spacial information carried out by a dense grid structure.

• We present an efficient method to enhance discriminative features to improve matching accuracy (Section 3.4). The experimental results show that we outperform existing methods without adopting any of complex machine learning schemes such as boosting [START_REF] Bak | Person reidentification using haar-based and dcd-based signature[END_REF][START_REF] Gray | Viewpoint invariant pedestrian recognition with an ensemble of localized features[END_REF] or RankSVM [START_REF] Prosser | Person reidentification by support vector ranking[END_REF].

• We introduce a new dissimilarity measure between signatures which is able to hold discriminative power coming from the informative dense grid structure of the MRC-s (Section 3.5).

We evaluate our approach in Section 4 before discussing related work and concluding.

Problem Definition

We lay the problem as the following. We generate human signature for each person detected and tracked in our video surveillance system. Let us denote a signature as s c i , where i encodes the person identity and c denotes the camera. The task is to find for each signature its corresponding signature in another camera. It is realized by querying the database of signatures s c ′ j , where c = c ′ with a signature of interest s c i . The results of the query is the list of the most similar signatures ordered by increasing dissimilarity (see Fig. 1). The position in the list of the true match is called the rank score.

Human Appearance Model

In this section we propose a new appearance model based on the MRC matrices extracted from tracks of a specific individual. The input of our approach is a set of cropped images corresponding to human detection and tracking results. We handle color dissimilarities caused by camera illumination difference by applying the histogram equalization [START_REF] Hordley | Illuminant and device invariant colour using histogram equalisation[END_REF] to each of the color channels (RGB). Then, such a normalized image is divided into a grid structure of overlapping cells. Nevertheless, before explaining details concerning cells of the grid, we present a brief overview of the covariance descriptor.

Covariance descriptor

In [START_REF] Tuzel | Region covariance: A fast descriptor for detection and classification[END_REF] the covariance of d-features has been proposed to characterize a region of interest. The descriptor encodes information of the variances of the defined features inside the region, their correlations with each other and a spatial layout. It is shown that the performance of the covariance features is superior to other methods as rotations and illuminations changes are absorbed by the covariance matrix.

Covariance matrix as a positive definite and symmetric matrix can be seen as a tensor. The main problem is that such defined tensor space is a manifold that is not a vector space with the usual additive structure (do not lie on Euclidean space). Hence, many usual operations (like the mean or the distance) need a special treatment. Therefore, our covariance manifold is specified as Riemannian to determine a powerful framework using tools from differential geometry [16]. We use the distance definition proposed by [START_REF] Förstner | A metric for covariance matrices[END_REF] to compute the dissimilarity between two covariance matrices C i and

C j ρ(C i , C j ) = d k=1 ln 2 λ k (C i , C j ) (1)
where λ k (C i , C j ) k=1...d are the generalized eigenvalues of C i and C j , determined by

λ k C i x k -C j x k = 0, k = 1 . . . d (2)
and x k = 0 are the generalized eigenvectors.

Mean Riemannian Covariance (MRC)

Let C 1 , . . . , C N be a set of covariance matrices. The Karcher or Fréchet mean is the set of tensors minimizing the sum of squared distances. In the case of tensors, the manifold M has a non-positive curvature, so there is a unique mean value µ µ = arg min

C∈M N i=1 ρ 2 (C, C i ). ( 3
)
where ρ is the covariance matrix distance (Eq. 1). Since covariance matrices lay in a Riemannian manifold we use the intrinsic Newton gradient descent algorithm to compute the approximation mean covariance at step t + 1

µ t+1 = exp µt 1 N N i=1 log µt (C i ) (4)
where exp µt and log µt are specific operators uniquely defined on the Riemannian manifold. This iterative gradient descent algorithm usually converges very fast (in experiments 5 iterations were enough, which is similar to [16]).

Mean Riemannian Covariance Grid (MRCG)

In this section we define the novel Mean Riemannian Covariance Grid (MRCG) and explain its merits. The proposed human signature has been designed to deal with low resolutions images and crowded environments where more specialized techniques (e.g. based on body parts detectors) might fail. We combine dense descriptors philosophy [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] with extremely effectiveness of the MRC descriptor.

Once color has been normalized, we scale every human image into a fixed size W × H pixels. Then, an image is divided into a dense grid structure with overlapping spatial square regions (cells). First, such dense representation makes the signature robust to partial occlusions. Second, as the grid structure, it contains a relevant information about spatial correlations between the MRC cells which is essential to carry out discriminative power of the signature. Moreover, as we use covariance matrices to describe characteristic of the cells, it is an efficient fusion of different types of features and their modalities. Let C p 1 , . . . , C p N be a set of covariance matrices extracted during tracking of N frames corresponding to image square regions at position of the cell p. We define the MRC as the mean covariance of these covariance matrices (see Section 3.2) computed using Riemannian space (see Fig. 2). The mean covariance matrix as an intrinsic average blends appearance information from multiple images. This mean covariance matrix keeps not only information about features distribution but also carries out essential cues about temporal changes of the appearance related to the position of the cell p. All MRC cells compose a full grid, named as Mean Riemannian Covariance Grid (MRCG). We prove efficiency of MRCG in the experimental results in Section 4.

MRC Discriminants

The goal of using discriminants is to identify the relevance of MRC cells. We present an efficient way to enhance discriminative features to improve matching accuracy.

Given a set of signatures S c = {s c i } n i=1 where s c i is a signature i from camera c, MRCG is represented by s c i = {µ c i,1 , µ c i,2 , . . . , µ c i,m } and m is the number of cells in the grid. For each µ c i,j we compute the variance between the human signatures from camera c defined as

σ c i,j = 1 n -1 n k=1;k =i ρ 2 (µ c i,j , µ c k,j ). (5)
Hence for each human signature s c i we obtain the vector of discriminants related to our MRC cells,

d c i = {σ c i,1 , σ c i,2 , . . . , σ c i,m }.
Here the idea is similar to methods derived from text retrieval where a frequency of terms is used to weight relevance of a word. As we do not want to quantize covariance space, we use σ c i,j of the MRC cell to extract its relevance. The MRC is assumed to be more significant when its variance is larger in the class of humans. Here, it is a kind of "killing two birds with one stone": 1) it is obvious that the most common patterns belong to the background (the variance is small); 2) the patterns which are far from the rest are at the same time the most discriminative (the variance is large). We thought about normalizing the σ c i,j by the variance within the class (similarly to Fisher's linear discriminants). Nevertheless, the results have shown that such a normalization does not improve matching accuracy. We think this is a consequence that the given number of frames per individual is not enough to obtain the reliable variance of MRC within the class. Scalability: Discriminative approaches are often accused of non-scalability (like [START_REF] Lin | Learning pairwise dissimilarity profiles for appearance recognition in visual surveillance[END_REF][START_REF] Schwartz | Learning discriminative appearance-based models using partial least squares[END_REF]). It is true that in these approaches an extensive learning phase is necessary to extract discriminative signatures. This makes these approaches very difficult to apply in real scenario where in every new minute new people appear. Fortunately, our approach by using very simple discriminative method is able to perform in the real system. It is true that every time when a new signature is created we have to update all signatures in the database. Nevertheless, for 10, 000 signatures, the update takes less than 30 seconds. Moreover, we do not expect more than such amount of signatures into database as the re-identification approaches are constraint to one day period (the strong assumption about the same clothes).

Grid Matching

Given the extracted human signatures we introduce a way to effectively distinguish individuals. As already mentioned the human signatures consist of a set of the MRC cells structured into a dense grid. In general the matching of two signatures s A and s B is carried out by maximizing the similarity measure. We shift one signature over another in x and y-direction to reduce body alignment issues. When we shift signature we preserve relative position between MRC cells to avoid wasting of discriminative property. In our experiments the signature is shifted over another not more than width of a cell to maximize similarity. The similarity between two human signatures s A and s B is defined as

S(s A , s B ) = i∈K σ A,i + σ B,i ρ(µ A,i , µ B,i ) / K (6)
where K stands for the set of cells in signature s A which have corresponding cells in signature s B ; ρ is the covariance distance; σ A,i and σ B,i are the discriminants of the corresponding MRC-s.

Experimental results

In this section the extensive evaluation of our approach is presented. The performance is shown using the Cumulative Matching Characteristic (CMC) curve suggested in [10] as the validation method for the re-identification problem. The CMC curve represents the expectation of finding the correct match in the top n matches. In order to provide quantitative results for our MRCG, we consider ETHZ [START_REF] Schwartz | Learning discriminative appearance-based models using partial least squares[END_REF] and i-LIDS [13, 21] datasets.

Experimental setup: Every human image is scaled into a fixed size of 64 × 192 pixels (size of the grid). We extract the MRC cells of 16 × 16 pixels, on a fixed grid of 8 pixels step (it gives in total 161 cells). Feature vector consist of 11 features:

x, y, R xy , G xy , B xy , ∇ R xy , θ R xy , ∇ G xy , θ G xy , ∇ B xy , θ B xy (7)
where x and y are pixel location, R xy , G xy , B xy are RGB channel values and ∇ and θ corresponds to gradient magnitude and orientation in each channel, respectively.

ETHZ dataset

ETHZ dataset was originally used for human detection [5]. In [START_REF] Schwartz | Learning discriminative appearance-based models using partial least squares[END_REF] this data have been adjusted for re-identification purposes 1 The modified dataset consists of three sequences: SEQ. #1 contains 83 pedestrians, SEQ. #2 contains 35 pedestrians and SEQ. #3 contains 28 pedestrians. The main drawback of this dataset is that the re-identification is performed in the same camera. Since the human images are very similar we randomly pick up a set of N = 10 frames from the beginning and from the end of each sequence to maximize challenging aspects and to be comparable with [START_REF] Bazzani | Multiple-shot person re-identification by hpe signature[END_REF]6]. The evaluation was repeated 20 times to obtain reliable statistics. We compare our MRCG with HPE [START_REF] Bazzani | Multiple-shot person re-identification by hpe signature[END_REF], PLS [START_REF] Schwartz | Learning discriminative appearance-based models using partial least squares[END_REF] and SDALF [6] (see Fig. 3). As we can see, our MRCG obtain the best results in all of the sequences. It shows how well the MRC cells can handle appearance variations. As MRCG consist of dense structured grid it is able to handle partial occlusions and small scale changes.

In our belief, despite such challenging aspects as illuminations changes and occlusions, the ETHZ dataset is not challenging enough to evaluate re-identification approaches. One of the most challenging issues in the reidentification problem is due to different camera settings, different color responses, different camera view points and different environments, which is not in this case. Hence, we have also evaluated our approach on images from more challenging i-LIDS (MCTS) dataset.

i-LIDS datasets

The experiments are performed on images from the 2008 i-LIDS Multiple-Camera Tracking Scenario (MCTS) dataset with multiple camera views. The evaluation dataset contains 476 images with 119 individuals automatically extracted by [START_REF] Zheng | Associating groups of people[END_REF]. This dataset is very challenging since there are many occlusions and often only the top part of the person is visible.

We compared our approach with methods which obtained the best performance on this dataset: SCR [START_REF] Bak | Person re-identification using spatial covariance regions of human body parts[END_REF], HPE [START_REF] Bazzani | Multiple-shot person re-identification by hpe signature[END_REF], Appearance Context [START_REF] Zheng | Associating groups of people[END_REF] and SDALF [6]. As SCR belongs to single-shot approaches, we extended SCR to multiple-shot approach by applying "set matching" (the minimal distance between pair of images). This makes our evaluation more fair to SCR method. The extended SCR method is noted as M-SCR. Unfortunately, i-LIDS [START_REF] Zheng | Associating groups of people[END_REF] dataset does not fit very well for multiple-shot signature because the number of images per individual is very low (in average 4). Moreover, for 22 individuals there are only 2 images given (one from each camera). Hence, in evaluation we use maximally N = 2 images to create human signature (like in [6]). Then, we applied simple affine transformation on these images (coordination of transformation matrix were changed by 5% and rotation angle was in range of [-6 • ; 6 • ]) to obtain our MRCG (the power of our descriptor is obtained by an intrinsic average which blends the appearance information).

The results with the state of the art approaches are reported in Fig. 4 (a). Our MRCG outperforms the state of the art. It proves that MRCG is highly informative descriptor which can handle camera differences.

As iLIDS [START_REF] Zheng | Associating groups of people[END_REF] does not fit well for multiple-shot signature we decide to evaluate our approach on two new sets of individuals from i-LIDS data [13]. These datasets finally satisfy all requirements of multiple-shot person reidentfication.

i-LIDS-MA [13]. This dataset contains 40 individuals extracted from two cameras. For each individual 46 frames are annotated manually from both cameras. Therefore we have 40 × 2 × 46 = 3680 annotated images. For each pedestrian we create human signature using N = 1 (for SCR [START_REF] Bak | Person re-identification using spatial covariance regions of human body parts[END_REF]) or N = 10 (for M-SCR and MRCG) randomly selected images. Then, every signature is used as a query to the gallery set of signatures from different camera. The procedures were repeated 10 times and average CMC curves together with our MRCG results are displayed in Fig. 4 (b). MRCG again proves its efficiency. Moreover, in comparison to M-SCR, our MRCG condenses information from the set of frames into compact and highly informative signature. The results show that the MRCG is extremely efficient gathering information using Riemannian manifold.

As i-LIDS-MA is a manually annotated dataset, it still does not reflect real video surveillance scenario where humans are detected and tracked automatically. Consequently, we use second dataset (i-LIDS-AA [13]) where images of humans are extracted automatically using HOG-based detector. In this case, detection and tracking results are noisy which makes the dataset more challenging.

i-LIDS-AA [13]. This dataset contains 100 individuals on 10754 images. The evaluation scheme was the same as for i-LIDS-MA dataset. The performance on this dataset is shown in Fig. 4 (c). The results show again that our descriptors outperform significantly SCR and M-SCR. Nev- ertheless the performance is not very high in comparison with the results obtained on i-LIDS-MA. It shows one of the main limitations that our approach performance directly depends on human detection results (e.g. detected bounding boxes not accurately centered around the people, only part of the people are detected due to occlusion). However, the results show that despite this limitation our descriptor still performs better than the state of the art approaches.

Related Work

Recently, the person re-identification problem became one of the most important tasks in video surveillance. There is a natural consequence of an invention of robust human detection algorithms to extend approaches for recognition purposes. The appearance-based re-identification techniques were focused on associating pairs of images, each containing one instance of individual. These methods are named single-shot approaches [START_REF] Bak | Person re-identification using spatial covariance regions of human body parts[END_REF][START_REF] Park | Vise: Visual search engine using multiple networked cameras[END_REF][START_REF] Wang | Shape and appearance context modeling[END_REF] and until now they were the most popular techniques. Currently researches try to improve identification accuracy by integrating information over many images. The group of methods which employs multiple images of the same person as training data is called multiple-shot approaches.

As to single-shot approaches, in [START_REF] Park | Vise: Visual search engine using multiple networked cameras[END_REF] the clothing color histograms taken over the head, shirt and pants regions together with the approximated height of the person were used as the discriminative feature. Similarly, clothing segmentation together with facial features [8] were employed to recognize individuals. Shape and appearance context model is proposed in [START_REF] Wang | Shape and appearance context modeling[END_REF]. A pedestrian image is segmented into regions and their color spatial information is registered into a co-occurance matrix. This method works well if the system considers only a frontal viewpoint. For more challenging cases, where viewpoint invariance is necessary, the ensemble of localized features (ELF ) [START_REF] Gray | Viewpoint invariant pedestrian recognition with an ensemble of localized features[END_REF] has been proposed. Instead of designing a specific feature for characterizing people appearance, a machine learning algorithm constructs a model that provides maximum discriminability by filtering a set of simple features. Enhancement of discriminative power of each individual signature with respect to the others was also the main issue in [START_REF] Lin | Learning pairwise dissimilarity profiles for appearance recognition in visual surveillance[END_REF]. Pairwise dissimilarity profiles between individuals have been learned and adapted into nearest neighbor classification. Similarly, in [START_REF] Schwartz | Learning discriminative appearance-based models using partial least squares[END_REF], a rich set of feature descriptors based on color, textures and edges has been used to reduce the amount of ambiguity among human class. The high-dimensional sig-nature was transformed into a low-dimensional discriminant latent space using a statistical tool called Partial Least Squares (PLS) in one-against-all scheme. Nevertheless in both methods, an extensive learning phase based on the pedestrians to re-identify is necessary to extract discriminative profiles what makes the approaches non-scalable. The person re-identification problem has been reformulated as a ranking problem in [START_REF] Prosser | Person reidentification by support vector ranking[END_REF]. The authors presented extensive evaluation of learning approaches and show that a ranking relevance based model can improve the reliability and accuracy.

Concerning multiple-shot approaches, in [9] the spatiotemporal graph was generated for ten consecutive frames for grouping spatiotemporally similar regions. Then, clustering method is applied to capture the local descriptions over time and improve matching accuracy. In [START_REF] Bak | Person reidentification using haar-based and dcd-based signature[END_REF], the Ad-aBoost was applied to extract the most discriminative and invariant haar-like features. Here, again one-against-all learning scheme was used to catch human dissimilarities. In [6], the authors proposed to combine three features: 1) chromatic content (HSV histogram); 2) maximally stable colour regions (MSCR) and 3) recurrent highly structured patches (RHSP). The extracted features were weighted by the distance with respect to the vertical axis to minimize effects of pose variations. Recurrent patches were also proposed in [START_REF] Bazzani | Multiple-shot person re-identification by hpe signature[END_REF]. Epitome analysis was used to extract highly informative patches form the set of images.

Conclusions

We have proposed a new approach for the human reidentification problem. The extensive evaluation has been performed on the ETHZ and the i-LIDS datasets. It has been shown that the MRCG computed using a Riemannian manifold theory can extract essential information about an appearance of a human and its variability. The experiments prove efficiency of the approach outperforming state of the art accuracy. In the future work we will investigate how to minimize the influence of noisy human detection and tracking on our human signature. Also we are planing to consider 2D/3D body parts modeling to improve matching of different poses of individuals.

Figure 1 .

 1 Figure 1. The results of the query. The first image on the left is the query image. The true match is on the first position in the list.

Figure 2 .

 2 Figure 2. Computation of the MRCG. Covariances gathered from tracking results are used to compute the MRC using Riemannian manifold space (depicted with the surface of the sphere).

Figure 3 .

 3 Figure 3. CMC curves obtained on ETHZ dataset. Our descriptor is noted as MRCG. We compare our method with the results of HPE[START_REF] Bazzani | Multiple-shot person re-identification by hpe signature[END_REF], PLS[START_REF] Schwartz | Learning discriminative appearance-based models using partial least squares[END_REF] and SDALF [6].

Figure 4 .

 4 Figure 4. CMC curves obtained on i-LIDS datasets; (a) We compare our methods with the results of SCR [2] and M-SCR, HPE [3], SDALF [6] and Appearance context model with Group Context [21]; (b) and (c) We compare our methods with the results of SCR [2] and M-SCR.

ETHZ Dataset for Appearance-Based Modeling: http://www. umiacs.umd.edu/~schwartz/datasets.html

Acknowledgements

This work has been supported by Agence National de la Recherche (ANR), VIDEO-ID and VANAHEIM project.