Biswanath Sethi
email: sethi.biswanath@gmail.com

Nazim Fatès
email: nazim.fates@loria.fr

Sukanta Das
email: sukanta@it.becs.ac.in

Reversibility of Elementary Cellular Automata Under Fully Asynchronous Update

Keywords: asynchronous cellular automata, reversibility, recurrence, Markov chain modelling, classification

We investigate the dynamics of Elementary Cellular Automata (ECA) under fully asynchronous update with periodic boundary conditions. We tackle the reversibility issue, that is, we want to determine whether, starting from any initial condition, it is possible to go back to this initial condition with random updates. We present analytical tools that allow us to partition the ECA space into three classes: strongly irreversible, irreversible and recurrent.

I Introduction

Cellular automata (CA) are spatially-extended dynamical systems which evolve in discrete time and space. They have been extensively studied as models of physical systems and as models of massively parallel computing devices.

Cellular automata are classically defined with a synchronous update, that is, all the cells simultaneously apply the local transition rule to produce the new state of the automaton. This definition has however been questioned in various works and different models of asynchronous cellular automata have been proposed. There are numerous reasons for studying asynchronism, such as: designing robust distributed algorithms (e.g. for self-stabilisation), studying the robustness of discrete models of natural phenomena, obtaining a better understanding of the dynamics of cellular automata, etc. Interested readers may refer to a recent survey paper for an overview of this field [START_REF] Fatès | A guided tour of asynchronous cellular automata[END_REF].

Our aim is to study how the notion of reversibility in the context of simple asynchronous CA with a stochastic updating. We focus on Elementary Cellular Automata (ECA), that is, binary, one-dimensional CA, where the next state of a cell after an update is determined by the current states of the left and right neighbors and the state of the cell itself.

Reversibility of synchronous deterministic cellular automata has been studied for decades [START_REF] Amoroso | Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures[END_REF][START_REF] Das | Classification of CA rules targeting synthesis of reversible cellular automata[END_REF][START_REF] Das | Characterization of 1-d periodic boundary reversible CA[END_REF][START_REF] Richardson | Tessellations with local transformations[END_REF][START_REF] Toffoli | Computation and construction universality of reversible cellular automata[END_REF]. However, the study of reversibility of asynchronous cellular automata has been only recently explored. Two different aspects have been studied: on the one hand, the question was asked as to how to update an asynchronous CA so that the system returns to its initial condition. It was shown that it is possible to find an answer for a given subset of one-dimensional asynchronous CA [START_REF] Das | Synthesis of reversible asynchronous cellular automata for pattern generation with specific hamming distance[END_REF][START_REF] Sarkar | On the Reversibility of 1-dimensional Asynchronous Cellular Automata[END_REF][START_REF] Sarkar | Reversibility in asynchronous cellular automata[END_REF]. The construction of the arguments was possible under the hypothesis that the sequence of updates is chosen. This introduction of update patterns relies on the hypothesis that an external operator is allowed to choose the cells to update in order to return to a given initial condition.

On the other hand, given a CA rule and a type of updating, it was asked to which extent it is possible to construct another rule whose transition graph would be an "inverse" of the transition graph of the original rule. Formally, this means that, given a rule f , we want to know if there is a rule f such that if for f a state y is reachable from x, then, for f , x is reachable from y [START_REF] Wacker | On completeness and decidability of phase space invertible asynchronous cellular automata[END_REF].

We now tackle a different case: we consider that the ECA are updated in a (stochastic) fully asynchronous mode, that is, at each discrete time step, a single cell is chosen randomly and uniformly for update. In this context, as we will see below, studying reversibility amounts to answering the following question: can we decide whether an asynchronous cellular automaton is recurrent, that is, if the system will almost surely return to the initial condition?

Using the definitions from the theory of Markov chains, we propose a full characterisation of the ECA rules into three classes: the strongly irreversible, irreversible, and recurrent rules. Intuitively, these class respectively correspond to the following behaviours: no possibility to return to the initial condition, a possibility to return to the initial condition a finite number of times and, an infinite number of returns to the initial condition.

(7) (6) (5) (4) (3) (2) (1) (0) f(x,y,z) 0 1 0 1 0 1 1 1 87 f(x,y,z) 0 1 1 0 0 0 1 1 99 f(x,y,z) 0 1 1 0 1 1 1 0 110

II Definitions

The cellular automata we consider use periodic boundary conditions: cells are arranged as a ring and we denote by L = Z/nZ the set of cells. The global state of the system at a given time will be represented by an element of {0, 1} L ; for example, for a ring of n = 6 cells, we will simply write x = 011001 a particular state and denote by x i the state of a particular cell i ∈ L. We denote by 0 and 1 the two homogeneous states with cell state 0 and 1, respectively. Similarly, 01 denote a state of even size in which cell states 0 and 1 alternate, 001 a state whose size is a multiple of three, where two 0s are followed by a 1, etc. An ECA is defined by a local transition function f : {0, 1} 3 → {0, 1} ; it is common to define such a function with a look-up table (see Table 1). There are 2 8 = 256 ECA rules, each one referred to with the number that corresponds to the decimal equivalent of the binary number formed by the sequence of its transitions results [START_REF] Wolfram | Theory and applications of cellular automata[END_REF]. Three such rules (87, 99 and 110) are shown in Table 1.

Definition 1

The association of the neighbourhood x, y, z to the value f (x, y, z), which represents the result of the updating function, is called Rule Min Term (RMT). Each RMT is associated to a number R(x, y, z) = 4x + 2y + z. An RMT R(x, y, z) is active f (x, y, z) = y and otherwise passive.

For example, for rule 110, RMT 1 is active and RMT 6 is passive (see Table 1).

We now consider fully asynchronous updating, that is, the case where only a single cell is updated randomly and uniformly at each time step. While a synchronous CA is a deterministic system, in an asynchronous CA (ACA), the next state not only depends on the local rule but also on the cells which are updated.

We denote by u t the cell that updated at time t ; the sequence U = (u t ) t∈N is called an update pattern. For an initial condition x and an update pattern U , the evolution of the system is given by the sequence of states (x t ) obtained by successive applications of the updates of U . Formally, we have: x t+1 = F (x t , u t ) and x 0 = x, with:

x t+1 i = f (x t i-1 , x t i , x t i+1 ) if i = u t x t i otherwise.
This evolution can be represented in the form of a state transition diagram. For example, Fig. 1 shows a partial state transition diagram of rule 110 with state ... x = 1010 and update pattern U = (2, 1, 4, 3, 1, 3, . . .). The index of the cell that is updated is noted over the arrows.

Definition 2 A state x is reachable if it has at least one predecessor, that is, if there exists a CA state y ∈ E n and an update position u ∈ L such that F (y, u) = x ; otherwise the state is non-reachable (or a garden-of-Eden state).

For instance, for ECA 110, the state 1110 is reachable as it has 1010 as a predecessor (see Fig. 1). By contrast, for ECA 87, 1111 is non-reachable (see Fig. 2). Indeed, if it had a predecessor, it would necessarily be equal to 1101, up to shifts, as only one cell can change at a time. But as the transition 101 (RMT 5) is passive, the last 0 can not disappear. Remark that a system may contain both types of states, reachable and non-reachable.

A state x is converted to an RMT sequence x with: xi = R(x i-1 , x i , x i+1 ) for all i ∈ L. For example, the state x = 001010 is associated to the RMT sequence x = 012524. RMT sequences will be used to establish the proofs of recurrence or irreversibility of the ECA rules.

III (Ir) reversibility of ACA

The issue of reversibility of CA has given rise to the use of various terms to name the same properties; for instance, the term "invertible" has been used as a synonymous of "reversible" [START_REF] Toffoli | Invertible cellular automata: A review[END_REF]. This variety of terms comes from the proximity between the physical notion of reversibility and its equivalent in discrete dynamical systems. We emphasise that, in the CA context, reversibility informally denotes the possibility to "invert" the evolution of a cellular automaton, by using potentially another cellular automaton and not the fact that the evolution of the system is similar when it is run "backwards". The term time-symmetric has been recently used to qualify the rules whose evolution is similar if the arrow of time is "inverted" [START_REF] Gajardo | On time-symmetry in cellular automata[END_REF]. As there are multiple views on reversible CA, we note that in the deterministic synchronous case, the following statements are equivalent:

1. Each CA state has exactly one predecessor.

2. There exists no CA state that is non-reachable.

3. Each CA state lies on a cycle. [START_REF] Das | Characterization of 1-d periodic boundary reversible CA[END_REF]. Each CA state is returned back in the course of dynamic evolution.

However, these definitions can not be transposed in a straightforward way to asynchronous cellular automata and in that case, the classical definition of reversibility needs to be revisited. One solution was that proposed consisted in associating the notion of reversibility with a given update pattern, that is, to a sequence of updates decided in advance [START_REF] Sarkar | Reversibility in asynchronous cellular automata[END_REF]. However, in the case where cells are updated randomly, new difficulties arise. For instance, in the ACA case, Statement 4 also implies Statement 2 and Statement 3, but does not imply Statement 1. This leads us to search for another definition of reversibility for an ACA. Here, we choose to start from Statement 4 for defining the reversibility of ACA: we require that in an asynchronous reversible CA, each state has to be returned back almost surely during the evolution of the system.

As we use the fully asynchronous updating, the evolution of our ACA is described by a Markov chain over the space of CA states Q L . We thus define the reversibility properties using the classical tools from Markov chain theory, which leads to identify reversibility and recurrence.

Definition 3 For a couple of states x, y ∈ Q L , we say that y is reachable from x if there is a sequence of updates that leads from x to y, that is:

∃k ∈ N * , U = (u 0 , . . . , u k-1 ), x 0 = x, x k = y and x i+1 = F (x i , u i ) for all i ∈ {0, . . . , k -1}.
We now introduce the main tool of our study :

Definition 4 A state x ∈ Q L is recurrent if for every state y that is reachable for x,
x is also reachable from y. A state that is not recurrent is transient.

Intuitively, a transient state is such that a particular sequence of updates may bring into a particular state from which it will never be possible to return back to the initial state. More formally, if y is reachable from x and x is reachable from y, we say that x and y communicate. By convention, all states communicate with themselves. Clearly, the relationship "communicate" is an equivalence relation; this relation partitions the set of states into communication classes. In words, two major behaviours exist: for the transient states, the system remains for an almost surely finite time in the communication class, then "escapes" this class and never returns back to it. In contrast, when the system is in a recurrent state, it remains in the communication class for ever.

We can now define the (ir)reversible cellular automata:

Definition 5 An ACA is recurrent if each CA state is recurrent, otherwise it is irreversible.
The definitions above allow us to know if some irreversibility is present in the system but they do not say anything about the "degree of irreversibility" of the system. Indeed, it may well be that the system does possess a transient state but that the sequence of updates that leads to observe the irreversibility is never observed in practice when the updates are random. This is a difficult problem to tackle in all generality. As first step, we propose here to deal with the states where it is not possible to return back whatever the sequence of updates. Definition 6 A state x is evanescent if it is not reachable from itself. An ACA that possesses an evanescent state is strongly irreversible.

It is interesting to remark that the set of evanescent and non-reachable states are equal. Indeed, by definition a non-reachable state is evanescent. To see why the converse is true, let us assume by contradiction that x is an evanescent state that is reachable from y. We say that the cell i ∈ L of a state x ∈ Q L is active if the transition which applies in i is active, that is, if f (x i-1 , x i , x i+1 ) = x i . Note that x is a fully unstable state (all its cells are active). It is then easy to see that y is also reachable from x (as the two states differ in only one cell) and thus, that x is reachable from itself, which contradicts the evanescence hypothesis.

As a consequence, if a rule is strongly irreversible it possesses at least one non-reachable state. However, the converse is not true: for instance, for rule 51 (the NOT rule), all states are fully unstable but the rule is reversible.

Fig. 3 depicts an example for a recurrent CA. In the state transition diagram of ECA 99, each state can be returned to with some given update of cells noted over the arrows. It can be shown (e.g., with an exhaustive search) that all the states of rule 99 ACA are recurrent.

IV Identifying the strongly irreversible rules

We first present the theorem that allows us to identify strongly irreversible ECA:

Theorem 1 An ECA is strongly irreversible if and only if one of the following conditions is verified:

1. RMT 0 (resp. RMT 7) is active and RMT 2 (resp. RMT 5) is passive.

Proof :

First, let us prove the "if" part, that is, if one of the conditions is verified then the ECA is strongly irreversible. We proceed by examining the conditions one by one and by exhibiting for each case a non-reachable (and thus an evanescent) state.

Case 1: Let us show that 0 (with RMT 0 only) is non-reachable. Assume that y is a predecessor of 0. First y = 0 as 0 is fully unstable (RMT 0 is active). The CA state y thus contains a single 1 (as the number of ones can only vary by 1 in the fully asynchronous update) and the transition from y to 0 was applied on the single 1 and with RMT 2. However, this is impossible as RMT 2 is passive. The case of RMT 5 and 7 is identical up to the 0/1 exchange.

Case 2: Let us show that 01 (with RMT 2 and 5 only) is non-reachable. First, if RMTs 2 and 5 are active, then this CA state is fully unstable. Now, assume that there is a CA state x = 01 and an updated cell i such that F (x, i) = 01, then, as x and 01 differ on only cell, it is easy to see that either RMT 0 or 7 produced a change of state on i, which is impossible if RMT 0 and RMT 7 are both passive.

Case 3: Let us show that 001 (with RMT 1, 2 and 4 only) is non-reachable. First, we note that this CA state is fully unstable as its RMT sequence is 124. Again, if 001 had a predecessor x = 001, then the last update on x is either a 0 changed into a 1 (application of RMT 0) or a 1 changed into a 0 (application of RMT 3 or 6 ), which in both cases can not happen if RMTs 0, 3 and 6 are all passive. The proof for the RMTs shown into parentheses is identical up to the 0/1 exchange.

2 Let us now show that the three conditions above of Th. 1 are also necessary for an ECA to be strongly irreversible.

Proof :

Let us consider an ECA that has a non-reachable state x. We will show that x has only four "forms" (up to the 0/1 exchange) that each brings us to the three conditions of the theorem. Let x be a non-reachable state. First, let us note that x is fully unstable and that no transition can lead to x. As a consequence, we can state an exclusion rule : x, the RMT sequence of x, can not contain two transitions in one of the following couples of RMTs {0, 2}, {1, 3}, {4, 6} and {5, 7}. To see why, assume for example that RMTs 0 and 2 are both present in x, that is, ∃i, j ∈ L, xi = 0 and xj = 2. As x is fully unstable, RMT 0 and 2 are both active, then, it can be remarked that two successive updates on i (or j) make the system return to x, that is, F (F (x, i), i) = x, which is in contradiction with the fact that x is non-reachable. Now, let us discuss the various possibilities for x.

Case a: Let us assume that x contains a 0. If x contains at least one 1, that is, if x = 0, then, we can note that x contains either the sequence 00010 or the sequence 00011, that is, x either contains the sequence 012 or the sequence 013. However, the two cases lead to a contradiction due to the exclusion rule. The only possibility is then x = 0, which implies that RMT 0 is active and RMT 2 is passive (due to the exclusion rule). We are thus in case 1 of the theorem. The case with RMTs 5 and 7 is symmetric by 0/1 exchange. Now, let us assume that x does not contain RMT 0 nor RMT 7. This implies that x contains at least one 01 pattern. We need to distinguish several sub-cases.

Case b: If x does not contain the 00 or 11 pattern, that is x = 01 and x = 25, we can deduce that RMT 0 and 5 are active and that RMT 1 and 7 are passive (exclusion rule); we are then verifying Case 2 of the theorem.

Case c: Let us now assume that x = 01, and without loss of generality, that x contains the 00 pattern. Then, x necessarily contains the pattern 1001 (otherwise, it would contain the pattern 000) which means that x thus contains the RMTs 4 and 1, and, because of the exclusion rule, does not contain RMT 3 nor 6. Two possibilities are now offered :

Case d: x contains the pattern 10011 : this is excluded because of the exclusion rule as this would imply that x contains RMT 1 and 3.

Case e: x contains the pattern 10010 but does not contain pattern 000 (RMT 0), nor 011 (RMT 3), nor 110 (RMT 6). This means that x contains 1, 2 and 4 (if x = 001) and possibly RMT 5 (if x contains 100101). In both cases, this means that RMT 1, 2 and 4 are active and that RMT 0, 3, 6 are passive and the last case of the theorem is proved.

The parts of the theorem presented into parentheses are symmetric to the cases discussed above by the 0/1 exchange.

2 As a consequence, it can be seen that the RMT sequence of a non-reachable state necessarily verifies one of the four following combinations of RMTs: (a) only RMT 0 (or only RMT 7) There are 132 such strongly irreversible rules; they are listed in Table 2.

Example 1 Let us consider ECA 87, a rule which satisfies the conditions of Th. 1 as RMT 7 is active and RMT 5 is passive (see Table 1). Consider the evolution of state 1. If a cell is updated with RMT 7, then one 0 appears and it is easy to see that afterwards the last 0 cannot disappear as RMT 5 is passive. Hence, 1 is non-reachable and is evanescent which makes the rule strongly irreversible.

V Identification of the recurrent rules

This section identifies the set of rules which are irreversible and, by complementation, those which are recurrent. We proceed by identifying the rules for which particular states are transient.

Theorem 2 A rule R is irreversible if one of the following conditions is verified:

1. RMT 0 (resp. RMT 7) is active and RMT 2 (resp. RMT 5) is passive or RMT 2 (resp. RMT 5) is active and RMT 0 (resp. RMT 7) is passive.

2. RMTs 0, 1, 2 and 4 (resp. RMTs 3, 5, 6 and 7) are passive and RMT 3 or 6 (resp. RMT 1 or 4) are active.

3. RMTs 0, 2, 3 and 6 (resp. RMTs 1, 4, 5 and 7) are passive and RMT 1 or 4 (resp. RMT 3 or 6) are active.

Proof :

Case 1: If RMT 0 is active and RMT 2 is passive, as shown the proof of Case 1 of Th. 1, 0 is evanescent and thus transient. If RMT 2 is active and RMT 0 is passive, let us consider the state x = 00100. If the third cell is updated, the system reaches 0, which is a fixed point, and which implies that x transient.

Case 2: Now, consider x = 001100; its RMT sequence is x = 013640. If RMT 3 is active, y = 000100 can be reached by updating the third cell. This a fixed point as its RMT sequence contains only 0, 1, 2 and 4, which all correspond to passive RMTs. Similarly, if RMT 6 is active the fixed point y = 001000 can be reached; which shows that x is transient. Case 3: We start with x = 00100; its RMT sequence is x = 01240. As RMT 1 and 4 are active, y = 00110 or y = 01100 can be reached. However, from any CA state that contains two or more 1s, it is not possible to return to x as RMTs 2, 3 and 6 are passive. (This implies that a 1 that has at least one 0 next to it can not disappear). Hence, x is transient.

The proofs for the RMTs mentioned in the parentheses is identical by exchanging the cell states 0 and 1.

2 By rewriting the conditions of the theorem, it can be verified that the rules for which it does not apply verify the following conditions: RMTs 0 and 2 (resp. 5 and 7) are either both active or both passive, and : a) there is at least one couple of active RMTs in the following sets: {2, 5}, {1, 6}, {3, 4}, {1, 3}, {4, 6} or b) RMTs 1, 3, 4 and 6 are all passive. There are 46 rules which verify these conditions, which are listed in Table 3. Our conjecture is that all these rules are recurrent, that is, all their states are recurrent.

The 210 rules which satisfies at least one condition of Th. 2 are irreversible. We have already identified 132 rules (Tab. 2) as strongly irreversible. The remaining 78 irreversible ACA are listed in Table 4; we conjecture that they are not strongly irreversible, that is, they have at least one transient state but no evanescent state.

VI Conclusion

We reported a classification of the ECA space according to reversibility properties under fully asynchronous update with periodic boundary conditions. The main step now consists in completing this classification by showing that the list of recurrent rules presented are closed. This could be done analysing the communication classes of the state space of these rules. While the classifications based on the convergence time to a fixed point remain mainly open [START_REF] Fatès | A note on the classification of the most simple asynchronous cellular automata[END_REF], achieving this result would represent an important step in the understanding of the dynamics of asynchronous CA.

As usual in the field of CA, one may ask how to extend the results to other types of asynchronism and to the CA spaces with a higher radius or higher dimension. As suggested by I. Marcovici, the classification can also be refined by considering "escaping states", that is, states where there is a possibility to stay but for which once this state is leaved, it can not be returned to.

Another question is to know if the reversibility issues presented here are similar to other views, for instance the one recently studied by Wacker and Worsch [START_REF] Wacker | On completeness and decidability of phase space invertible asynchronous cellular automata[END_REF].

Figure 1 :Figure 2 :

 12 Figure 1: Partial state transition diagram of rule 110 with n = 4. The cells updated during evolution are noted over arrows (convention kept).

Figure 3 :

 3 Figure 3: Transition diagram for ECA 99 with n = 4

2 .

 2 RMTs 2 and 5 are active and RMTs 0 and 7 are passive. 3. RMTs 1, 2 and 4 (resp. RMTs 3, 6 and 5) are active, and RMTs 0, 3 and 6 (resp. 1, 4 and 7) are passive.

  , (b) only RMTs 2 and 5 (c) only RMTs 1, 2 and 4 (or only RMTs 3, 5 and 6), (d) only RMTs 1, 2, 4 and 5 (or only RMTs 2, 3, 5 and 6).

Table 1 :

 1

		Look-up table for rule 87, 99 and 110
	x,y,z	111 110 101 100 011 010 001 000 Rule
	RM T

Table 2 :

 2 List of the 132 strongly irreversible rules that verify Theorem 1. Bold fonts show the minimal representative rules (rules with the smallest code among the group of rules that are obtained by left-right and 0-1 exchange).

	0	1	2	3	4	5	6	7	8	9
	10	11	12	13	14	15	16	17	18	19
	20	21	22	23	24	25	26	27	28	29
	30	31	37	39	45	47	53	55	61	63
	64	65	66	67	68	69	70	71	72	73
	74	75	76	77	78	79	80	81	82	83
	84	85	86	87	88	89	90	91	92	93
	94	95	101 103 109 111 117 119 122 125
	127 133 135 141 143 149 151 157 159 160
	161 162 164 165 167 168 170 173 175 176
	178 181 183 184 186 189 191 197 199 205
	207 213 215 218 221 223 224 226 229 231
	232 234 237 239 240 242 245 247 248 250
	253 255

Table 3 :

 3 List of the 46 rules that are conjectured to be recurrent.

	33	35	38	41	43	46	49	51	52	54
	57	59	60	62	97	99	102 105 107 108
	113 115 116 118 121 123 131 134 139 142
	145 147 148 150 153 155 156 158 195 198
	201 204 209 211 212 214

Table 4 :

 4 List of the 78 remaining rules: conjectured to be the irreversible ACA that are not strongly irreversible.

	32	34	36	40	42	44	48	50	56	58
	96	98	100 104 106 110 112 114 120 124
	126 128 129 130 132 136 137 138 140 144
	146 152 154 163 166 169 171 172 174 177
	179 180 182 185 187 188 190 192 193 194
	196 200 202 203 206 208 210 216 217 219
	220 222 225 227 228 230 233 235 236 238
	241 243 244 246 249 251 252 254

This work is supported by DST Fast Track Project Fund (No.SR/FTP/ETA-0071/2011)


Cyril Masselot

Cimeos Ea

Olivier Galibert

T Movida

Digital socialization in a Territorial Intelligence case: The Fontaine d'Ouche area in Dijon (Burgundy, France)

Keywords: Social network, sustainable consumption, Web 2.0, participation, territorial intelligence, communication

How to mobilize citizens around eco-responsible conducts? With the "Transition Towns MOVIDA" project (http://programme-movida.fr), we wish to identify levers related to a most sustainable consumption, in reference to the Transition initiated by Rob Hopkins. The present proposal consider all possible "socio-technical communicational" devices that can support the socio-ecological transition in a local area such as Fontaine d'Ouche in Dijon: reflexivity spaces (fear and hopes, actions and attitude) in a dialogical base for decisionmaking ( a t i n d i v i d u a l a n d c o l l e c t i v e l e v e l ) . What kind of ICT devices should allows inhabitants of the Fontaine D'ouche area to be more resilient? I n t h i s c a s e , how information and communication sciences can participate to a project of territorial intelligence?

Through our research field, the area of Fontaine d'Ouche in the city of Dijon (Burgundy, France), we propose to consider the ideology of democratic participation through a double injunction c o m i n g f r o m t h e I n t ernet imaginary and the principles of sustainable development, based on a Facebook Page Design focused on the themes of the « ecocitizens consumption ».

Submission content :

Framework of our research program : « Transition Towns, the case of Fontaine d'Ouche », MOVIDA Program In May 2011, has been published on the website of the Ministry of Environment, Sustainable Development, Transport and Logistics of France (MEDDTL), a call for funding research projects in order to understand the levers of sustainable cosumption. This program, named MOVIDA, aims to assist the government policy in accompanying consumerist changes provoced by taking into account the ecological imperative. We decided to study the consumption practices of an area of the city of Dijon in Burgundy (France), mixing condo in big buildings, residential areas of individual houses, green spaces. In this interdisciplinary research program whitch also gathers psychosociologists, economists, geographs, one of the research issue is to consider the role of communications tools 2.0 , particularly in mobilizing and assisting inhabitants towards sustainable consumption practices. Our project has been laureate of this funding program and we began the scientifc work since the first of January 2012.

The Web 2.0 in order to involve inhabitants in the eco-consumption path ?

Our research on Web 2.0 tools is part of a participatory and co-constructive approach. It aims to involve all stakeholders in the creation and dissemination of eco-citizens consumtion practices in the field of mobility, leisure (sport and culture) and food. The social utility of the project is to support the implementation of concrete initiative as known as « transition experiences ». For Rob Hopkins, "[...] transition experiences represent a new evolutionary approach to sustainability for a community [...]. Although the peak oil and climate change is undoubtedly enormous challenges they carry with them the possibility of an economic, cultural and social innovation. We will see a blossoming of local businesses, local solutions and skills and an explosion of creativity and cunning. " Obviously, we can not predict the development of these micro-level initiatives in the territories. The solutions expected by Hopkins displayed the predominance of micro-level actions. It is the accumulation of small and spontaneous experiments whitch must be generalized to enhance social innovation through the socio-ecological transition rules. This is a global change from a "top-down" to a "Bottom up" governance. How a social network as Facebook could be a good communication plateform to initiate, stimulate or help this transitionnal experimentation of sustainable consumption ? Do the inhabitants have enough skills in using the Web 2.0 ? What kind of community management is required to succeed in this task of environmental education ? All these questions deal with the participation issue : What kind of communication devices and services are the best to enhance participation of the inhabitants ? What are the forms and norms of this participation ? Why is it so important to involve inhabitants and stake-olders in a debate ? How to animate and moderate the discussions in order to respect a communicationnal ethic (Habermas, 1987) ?

In this paper we want to highlight the participation issue in the release of sustainable consumption good practices and representation. Through our research field, we propose to consider the ideology of democratic participation through a double injunction coming from the Internet imaginary and the principles of sustainable development.

On the one hand, we have identified, in a previous research on the e-community ideology (Galibert, Lepine-Nguyen, Pelissier, 2011) an injunction for internet users to get involved in discussion process on line. On the other hand, all the international charts, like for example the Agenda 21 principles, deal with the staring role of participative process in order to enhance the eco-citizenship. Does this sustainable and technological injunction enhance ecological behaviour in a district as Fontaine d'Ouche ?

methods and first results

Our methods crossover 3 empirical approaches : First, we have realised, in march 2012, a quantitative inquiry on a representative sample of the district inhabitants. These first results show us an important « digital culture » of the inhabitants, especialy young peoples. Particularely, it's interesting to notice that the inhabitants, despite their « working class » membership, are involved in the 2.0 uses, as same as the whole population. We also observe that the inhabitants are very recepteive to food safety issues. However, a s a b e n c h m a r k i n g o f l o c a l s w e b s i t e a n d F a c e b o o k p a g e s s h o w e d u s , t h e inhabitants are not currently involved in environmental communication 2.0. This first « quantitative » step in the knowledge of threads and opponities for collaborative, discursive and participative communication tools to accompagny people on the sustainable consumption shape a favourable situation to 2.0 ecological education.

Secondly, since september 2012, in order to validate our hypothesis, we figured out an « Openned questions » interviews. Within a qualitative inquiry framewok, we make profitable the Internet most valuable users in the Fontaine d'Ouche district, identified in our first inquiry, to know if the pionneers of the local community management, for example the inhabitants who uses to administrate facebook group pages or other websites, an expert knowledge of the inhabitants involvement in the Thirdly, In the same time, we planned an experimental ethnographical process based on a Facebook Page Design focused on the themes of the « eco-citizens consumption ».


Ezequiel Geremia

Darko Zikic

Olivier Clatz

Bjoern H Menze

Ben Glocker

Ender Konukoglu

Jamie Shotton

O M Thomas

S J Price

Tilak Das

R Jena

N Ayache

A Criminisi

Classification Forests for Semantic Segmentation of Brain Lesions in Multi-channel MRI

come

Introduction

In this chapter, we demonstrate with two applications how classification forests can be used to develop state of the art segmentation systems for medical image analysis. Specifically, in Section 1.2 we discuss a method for segmentation of the individual tissues of high-grade brain tumors, and in Section 1.3 we present a method for segmentation of multiple-sclerosis (MS) lesions. These two methods employ classification forests as the major building block, and achieve high quality results in their respective domains, using multi-channel magnetic resonance (MR) images as input.

From a methodological point of view, the tumor segmentation application investigates an integration of initial probabilities as an additional input for the classification forest. The MS lesions segmentation application uses the classification forest directly, though employs different feature types. Further, for the MS application, we present an analysis of the forest parameters and the discriminative power of the individual feature types and input channels.

Why use classification forests for medical image analysis?

We choose to employ classification forests because of (1) their efficiency in handling high-dimensional feature spaces, (2) their ability to perform simultaneous multi-label classification, and (3) their good generalization properties. In some more detail:

1. The efficiency of classification forests in dealing with high-dimensional spaces allows us to use non-local and context-aware features, which describe spatial locations based on a larger surrounding, and span a very high-dimensional feature space. Context-aware features have two possible advantages. First, these features have the potential to successfully classify labels which cannot be distinguished in a lower-dimensional feature space. Second, our experiments indicate that learning based on context-aware features has an inherent regularizing effect on the results. The interesting property of this regularization is that it is not explicitly modeled, but learned from the training data, resulting in a form of application-specific regularization. 2. Classification forests are inherently multi-label classifiers. This property allows us to classify different tissues simultaneously, simplifying the modeling of the distributions of the individual classes. This is in contrast to other classifiers such as SVMs which are inherently binary classifiers. In order to separate multiple classes, these classifiers usually employ a certain multi-class strategy (e.g. hierarchically, or in the one-versus-all manner). For these strategies, several classes have to be grouped together, which can make the distribution inside the aggregate group more complex than the distribution of each individual class. 3. The good generalization ability of classification forests is important in the medical image analysis field in general and our setting in particular, because of the inherent challenges in collecting and annotating large amounts of data for supervised learning.

Classification forests for segmentation of brain tumor tissues

In this section, we present our work in which we use classification forests as a major building block to perform tissue-specific segmentation of brain tumors in multichannel MR images. 1 1 We focus on high-grade glioma tumors. These tumors grow rapidly, infiltrate the brain in an irregular way, and often create extensive vasculature networks. The fast growth and the high blood consumption by the active cells (AC) causes the death of the cells on the inside of the tumor, which then form the so-called necrotic cores (NC). Therefore, the necrotic core is surrounded by a varyingly thick layer of active cells. Together, the necrotic core and the active cells form the gross tumor (GT). Usually, the tumor itself is surrounded by a varying amount of edema (E), in which there is an increased risk of finding isolated tumor infiltration. Due to the complexity of the bio-mechanical processes involved, high-grade gliomas have extremely irregular shape, heterogeneous appearance and varying location -for an example, please compare the figs. 1.1 and 1.3. For further information on high-grade gliomas, please see [START_REF] Barnett | High-Grade Gliomas[END_REF].

In standard clinical routine, the diagnosis and treatment of high-grade gliomas is based on multi-channel MR images. The single channels are 3D MR scans obtained with different protocols. Multi-channel scans are used since each protocol captures different properties of the tumor. The standard clinical modalities are: T1 after injection of gadolinium contrast agent (T1-gad), T1, T2, and FLAIR. As an example of the complementary nature of the modalities, one can observe that T1-gad highlights the active cells as high-intensities, while T2 and FLAIR better visualize the edema (cf. Figure 1.1). Additionally, in our work, we consider two further channels from diffusion tensor imaging (DTI), which have the potential to provide further information about the tumor structure: the so-called DTI-p and DTI-q maps [START_REF] Price | Tissue signature characterisation of diffusion tensor abnormalities in cerebral gliomas[END_REF]. We will refer to the multi-channel MR data by I = (I T1-gad , I T1 , I T2 , I FLAIR , I DTI-q , I DTI-p ).

Our goal is to segment high-grade gliomas as well as the individual tissue components automatically and reliably. This would (1) speed-up the inter-active delineation of the tissue components through fast and accurate initialization, and (2) allow direct volume measurements. Delineation of tissue components is crucial for radiotherapy and surgery planning and is currently performed manually in a labor intensive fashion. Volume measurements are critical for the evaluation of treatment [START_REF] Wen | Updated response assessment criteria for high-grade gliomas: response assessment in neuro-oncology working group[END_REF], but are seldom performed since manual tumor segmentation is often impractical in a routine clinical setting.

While most previous research has focused on the segmentation of gross tumor [START_REF] Gorlitz | Semi-supervised tumor detection in magnetic resonance spectroscopic images using discriminative random fields[END_REF][START_REF] Menze | A generative model for brain tumor segmentation in multi-modal images[END_REF][START_REF] Wels | A discriminative model-constrained graph-cuts approach to fully automated pediatric brain tumor segmentation in 3D MRI[END_REF], or tumor and edema [START_REF] Corso | Efficient multilevel brain tumor segmentation with integrated bayesian model classification[END_REF][START_REF] Gooya | Joint segmentation and deformable registration of brain scans guided by a tumor growth model[END_REF][START_REF] Prastawa | A brain tumor segmentation framework based on outlier detection[END_REF][START_REF] Verma | Multi-parametric tissue characterization of brain neoplasm and their recurrence using pattern classification of MR images[END_REF], we perform a tissue-specific segmentation of three relevant tissues types: active cells (AC), necrotic core (NC), and edema (E) -as also do [START_REF] Bauer | Fully automatic segmentation of brain tumor images using support vector machine classification in combination with hierarchical conditional random field regularization[END_REF][START_REF] Verma | Multi-parametric tissue characterization of brain neoplasm and their recurrence using pattern classification of MR images[END_REF]. Distinguishing between volumes of individual tissue types, especially active cells and necrotic core, is an important step for assessment of treatment response. For example, an effective drug might not change the gross tumor volume while still transforming active into necrotic cells. To detect this change, the volumes of both of these tissues must be monitored.

Motivation for using classification forests

The efficiency of classification forests in dealing with high-dimensional spaces allows us to use non-local and context-aware features. These features span a much larger space than those considered by previous learning-based works on tumor segmentation, which use features which represent spatial points in the patient only very locally [START_REF] Bauer | Fully automatic segmentation of brain tumor images using support vector machine classification in combination with hierarchical conditional random field regularization[END_REF][START_REF] Lee | Segmenting brain tumors using pseudo-conditional random fields[END_REF][START_REF] Schmidt | Segmenting brain tumors using alignment-based features[END_REF][START_REF] Verma | Multi-parametric tissue characterization of brain neoplasm and their recurrence using pattern classification of MR images[END_REF][START_REF] Wels | A discriminative model-constrained graph-cuts approach to fully automated pediatric brain tumor segmentation in 3D MRI[END_REF]. Context-aware features have two potential advantages. First, they enable the method to classify labels which cannot be distinguished in a lower-dimensional feature space. Second, our experiments suggest that learning based on context-aware features has an inherent regularizing effect on the results, which is enhanced in our approach through the additional use of initial probabilities.

The inherent multi-label ability of classification forests is in contrast to most classifiers previously employed for tumor segmentation. Work which classifies multiple labels often uses SVMs [START_REF] Bauer | Fully automatic segmentation of brain tumor images using support vector machine classification in combination with hierarchical conditional random field regularization[END_REF][START_REF] Verma | Multi-parametric tissue characterization of brain neoplasm and their recurrence using pattern classification of MR images[END_REF], which are inherently binary classifiers. In order to classify different tissues, they are applied hierarchically [START_REF] Bauer | Fully automatic segmentation of brain tumor images using support vector machine classification in combination with hierarchical conditional random field regularization[END_REF], or in the one-versus-all manner [START_REF] Verma | Multi-parametric tissue characterization of brain neoplasm and their recurrence using pattern classification of MR images[END_REF]. For these approaches, several classes have to be grouped together, and this step can make the distribution of the aggregate group more complex than the distribution of each individual class. For example, the intensity distribution of a tumor consisting of AC and NC tissues, which have very different representations in the multi-channel data (cf. Figure 1.1), is likely to be more complex than the distributions of the single classes. We circumvent this potential problem by classifying all tissues simultaneously, which requires us only to handle distributions of individual classes.

Method: Classification forests with initial probabilities

Our approach is based on classification forests as presented in Chapter ??. Previously, several works have applied discriminative learning techniques to tumor segmentation [START_REF] Bauer | Fully automatic segmentation of brain tumor images using support vector machine classification in combination with hierarchical conditional random field regularization[END_REF][START_REF] Corso | Efficient multilevel brain tumor segmentation with integrated bayesian model classification[END_REF][START_REF] Gorlitz | Semi-supervised tumor detection in magnetic resonance spectroscopic images using discriminative random fields[END_REF][START_REF] Schmidt | Segmenting brain tumors using alignment-based features[END_REF][START_REF] Verma | Multi-parametric tissue characterization of brain neoplasm and their recurrence using pattern classification of MR images[END_REF][START_REF] Wels | A discriminative model-constrained graph-cuts approach to fully automated pediatric brain tumor segmentation in 3D MRI[END_REF]. Mostly, a learning method using comparably local features is combined with a regularization step, for example by modeling the boundary [START_REF] Ho | Level-set evolution with region competition: automatic 3-D segmentation of brain tumors[END_REF][START_REF] Popuri | 3D variational brain tumor segmentation using dirichlet priors on a clustered feature set[END_REF], or by applying a variant of a random field spatial prior (MRF/CRF) [START_REF] Corso | Efficient multilevel brain tumor segmentation with integrated bayesian model classification[END_REF][START_REF] Gorlitz | Semi-supervised tumor detection in magnetic resonance spectroscopic images using discriminative random fields[END_REF][START_REF] Wels | A discriminative model-constrained graph-cuts approach to fully automated pediatric brain tumor segmentation in 3D MRI[END_REF].

The schematic overview of our approach is given in Figure 1.2. Besides using application-specific feature types to represent the input data, we adapt the standard classification forest by providing it with rough initial class probabilities as input, additionally to the raw input data. In its effect, this step is similar to the idea of auto-context from [START_REF] Tu | Auto-context and its application to high-level vision tasks and 3D brain image segmentation[END_REF] and Chapter ??. In contrast to auto-context, we do not use the same type of classifier for the initial probabilities and the actual classification. Instead, for the estimation of initial probabilities, we use posterior probabilities based on intensity-based Gaussian Mixture models (GMM) for the single tissues. In comparison to computing the initial probabilities by classification forests, the GMMbased modeling has the advantage of a faster training, at the cost of a lower quality of the probability estimates (cf. Figure 1.5). We describe the estimation of the initial probabilities in Section 1.2.2.1.

The advantage of an auto-context-type approach is that is has an applicationspecific regularizing effect, which is learned based on the input data. With such a regularization approach, we achieve high-quality results without using an explicit regularization model. This not only results in a more application-specific inherent regularization, but due to the omission of an explicit regularization module, our approach has a low model complexity.

Besides the use of initial tissues probabilities, the second important characteristic of our approach is that we use spatially non-local and context-aware features, with their advantages as discussed above. We describe the types of the the context-aware features that we use in Section 1.2.2.2.

As described in the introduction, we classify the four classes C = {B, AC, NC, E} for background (B), active cells (AC), necrotic core (NC), and edema (E). Based on the tissue-specific segmentation results, we define the gross tumor as GT=AC∪NC. The MR data I = (I T1-gad , I T1 , I T2 , I FLAIR , I DTI-q , I DTI-p ) serves as input data, while the learning is based on expert voxel-wise manual annotations of the training data set.

Estimating initial probabilities

As the first step of our approach, we estimate the initial class probabilities for a given patient as posterior probabilities based on the likelihoods obtained by training a set of GMMs on the training data. For each class c ∈ C, we train a single GMM, which captures the likelihood p(I|c) of the multi-dimensional intensity for this class. For a given testing data set I, the GMM-based posterior probability p GMM c for the class c is estimated for each point p∈R 3 by

p GMM (c|p) = p(I(p)|c) p c ∑ c j p(I(p)|c j ) p c j , (1.1)
with p c denoting the prior probability for the class c, based on its relative frequency.

We can now use the probabilities p GMM c (p)= p GMM (c|p) directly as input for the decision forests, in addition to the multi-channel MR data I. So now, our data for one patient becomes

C=(I T1-gad , I T1 , I T2 , I FLAIR , I DTI-q , I DTI-p , p GMM AC , p GMM NC , p GMM E , p GMM B ) . (1.2)
For simplicity, we will denote single channels by C j .

Please note that we can use the GMM-based probabilities for maximum a posteriori classification by ĉ = arg max c p GMM (c|p). We will use this for a base line comparison in Section 1.2.3.

Spatially non-local and context-aware feature types

We employ three features types, which are intensity-based and parameterized. These features describe a point to be labeled based on its non-local neighborhood, which makes them context-aware. We denote the parameterized feature types by x type params .

During training, the type and parameters for the features are randomly drawn at every node. Every instantiated and selected feature x type params with its unique parameters corresponds to one dimension of the feature space F with dimension d . Our feature space is much higher-dimensional than those used in previous work.

We use the following notation: p is a spatial location to be assigned a class label, and C j is an input channel. R l (p) denotes a p-centered and axis aligned 3D box region in C j with edge lengths l = (l x , l y , l z ), and u∈R 3 is an offset vector.

• Feature Type 1 -Intensity difference: This feature type measures the intensity difference between p in a channel C j 1 and an offset point p + u in a channel C j 2

x probe j 1 , j 2 ,u (p,C) = C j 1 (p) -C j 2 (p + u) . (1.3)
• Feature Type 2 -Mean intensity difference: This feature type measures the difference between intensity means of a box around p in C j 1 , and a box around an offset point p + u in the (potentially different) channel C j 2

x box j 1 , j 2 ,l 1 ,l 2 ,u (p,C) = 1 |R l 1 | ∑ p ∈R l 1 (p) C j 1 (p ) - 1 |R l 2 | ∑ p ∈R l 2 (p+u) C j 2 (p ) . (1.4)
• Feature Type 3 -Intensity range along ray: This feature type captures the intensity range along a 3D line between p and p+u in one channel. This type is designed with the intuition that structure changes can yield a large intensity change, e.g. NC being dark and AC bright in T1-gad.

x ray j,u (p,C) = max λ (C j (p + λ u)) -min λ (C j (p + λ u)) with λ ∈ [0, 1] . (1.5)

Evaluation

We evaluate our approach on a set of multi-channel 3D MR data for 40 patients suffering from high-grade gliomas. All data is acquired prior to treatment on the same MR scanner. For all 40 patients, a manual segmentation of the three classes of AC, NC, and E is obtained in 3D with an interactive segmentation tool. We try to keep the amount of data pre-processing at a minimum. We perform skull stripping of MR channels [START_REF] Smith | Fast robust automated brain extraction[END_REF], and for each patient we perform an affine intra-patient registration of all channels to the T1-gad image. We also avoid a full bias-field correction, and only align the mean intensities of the images within each channel by a global multiplicative factor. All these steps are fully automatic.

The evaluation reports the Dice score between the manual segmentations and the results. Besides the the tissue-specific segmentation results, we also evaluate the segmentation quality for the gross tumor (GT) by defining it as GT=AC∪NC.

Experiments

We perform an extensive series of cross-validation experiments to evaluate our method. For this, the 40 patients are randomly split into non-overlapping training and testing data sets. To investigate the influence of the size of the training set and generalization properties of our method, we perform experiments with following training/testing sizes: 10/30, 20/20, 30/10. For each of the three ratios, we perform 10 tests, by randomly generating 10 different training/testing splits.

To demonstrate the influence of the single components of the method, we also perform tests on forests without GMMs, and compare to the results of GMM only. Finally, we investigate the influence of using DTI, by performing all experiments also with MR input only. Overall, this results in 30 random training sets, and 600 tests for each of the 6 approaches. The evaluation is performed with all images sampled to isotropic spatial resolution of 2mm, and forests with T =40 trees of depth D=20. With these settings, the training of one tree takes 10-25 min, and testing 2-3 min, depending on the size of training set and the number of channels. The algorithm and feature design were done on an independent 20/20-fold.

Figure 1.3 shows a visual example of the results, while the quantitative evaluation and more details are given in Figure 1.4. We observe an improvement of the segmentation accuracy by the proposed method (Forest(GMM,MR,DTI)) compared to the other tested configurations.

Comparison to quantitative results of other approaches is difficult for a number of reasons, most prominently the different input data. To provide some indicative context, we cite results of a recent work from [START_REF] Bauer | Fully automatic segmentation of brain tumor images using support vector machine classification in combination with hierarchical conditional random field regularization[END_REF]. There, the mean and standard deviation for a leave-one-out cross-validation on 10 glioma patients, based on multichannel MR are as follows: GT: 77±9, AC: 64±13, NC: 45±23, E: 60±16. Our results compare favorably. For our 30/10-tests we get: GT: 90±9, AC: 85±9, NC: 75±16, E: 80±18, and for the more challenging 10/30-tests (less training data), we get GT: 89±9, AC: 84±9, NC: 70±19, E: 72±23.

Classification forests for segmentation of MS lesions

In this section, we present the application of classification forests to the challenging task of segmentation of multiple sclerosis lesions. 2Multiple Sclerosis (MS) is a chronic, inflammatory and demyelinating disease that primarily affects the white matter of the central nervous system [START_REF] Calabresi | Multiple sclerosis and demyelinating conditions of the central nervous system[END_REF]. Automatic detection and segmentation of MS lesions can help diagnosis and patient follow-up. It offers an attractive alternative to manual segmentation which remains a timeconsuming task and suffers from intra-and inter-expert variability. However, MS lesions show a high variability in appearance and shape which makes automatic segmentation a challenging task. In particular, MS lesions lack common intensity and texture characteristics, their shapes are variable and their location within the white matter varies across patients.

Our segmentation problem can be formalized as a binary classification of voxel samples into either background or lesions. Taking advantage of context-aware features in the classification task is key to detect the appearance differences of MS lesions with respect to healthy brain tissue. Subsequently, we use the classification forest technique for MS lesion segmentation. We exploit a specific discriminative symmetry feature which stems from the assumption that the healthy brain is approximately symmetric with respect to the mid-sagittal plane and that MS lesions tend to develop in asymmetric ways. We then show how the forest combines the most discriminative channels for the task of MS lesion segmentation.

Data

The MICCAI 2008 Grand Challenge (MSGC) [START_REF] Styner | 3D segmentation in the clinic: A grand challenge II: MS lesion segmentation[END_REF] makes publicly available two datasets through their website: a public dataset of labeled MR images which can be used to train a segmentation algorithm; and a private dataset of unlabeled cases on which the algorithm should be tested. The public dataset contains 20 cases which are labeled by a medical expert rater. The private dataset contains 25 cases, each annotated by three expert raters. For each case, 3 MR volumes are provided: a T1weighted image, a T2-weighted image and a FLAIR image.

We sub-sample and crop the images so that they all have the same size, 159 × 207 × 79 voxels, and the same resolution, 1 × 1 × 2 mm 3 . RF acquisition field inhomogeneities are corrected [START_REF] Prima | Maximum likelihood estimation of the bias field in MR brain images: Investigating different modelings of the imaging process[END_REF] and inter-subject intensity variations are normalized [START_REF] Rey | Détection et quantification de processus évolutifs dans des images médicales tridimensionnelles : application à la sclérose en plaques[END_REF]. The images are then aligned on the mid-sagittal plane [START_REF] Prima | Computation of the mid-sagittal plane in 3D brain images[END_REF]. A spatial prior is added by registering the MNI atlas [START_REF] Evans | 3D statistical neuroanatomical models from 305 MRI volumes[END_REF] to the anatomical images, each voxel of the atlas providing the probability of belonging to the white matter (P WM ), the grey matter (P GM ) and the cerebrospinal fluid (P CSF ). Please see also Figure 1.6.

Both anatomical images and spatial priors will be treated under the unified term channel, and denoted C ∈ (I T1 , I T2 , I FLAIR , P WM , P GM , P CSF ).

Feature types

For the segmentation of MS lesions, we compute three types of intensity-based features. The actual feature types differ from the ones used for brain tumors in Section 1.2.2.2 in order to match the specifics of the MS lesion segmentation. However, it is interesting to note that the feature types for both tasks are similar in nature, and most importantly, both use the idea of spatial context-awareness.

Of the following feature types, the first one is local, measuring only the local intensity in one single channel, while the other two are non-local and context-aware.

x cont j 1 , j 2 ,R 1 ,R 2 (p) = C j 1 (p) - 1 |R 1 | ∑ p ∈R 1 C j 2 (p ) - 1
|R 2 | ∑ p ∈R 2 C j 2 (p ) , (1.7)
where C 1 and C 2 can be both, intensity or prior channels. The regions R 1 and R 2 are sampled randomly in a large neighborhood of the voxel v (cf. Figure 1.7). The sum over these regions is efficiently computed using integral volume processing [START_REF] Shotton | TextonBoost for image understanding: Multi-class object recognition and segmentation by jointly modeling texture, layout, and context[END_REF]. • Feature type 3 -Symmetry: The second context-aware feature compares the voxel of interest at p with its symmetric counterpart with respect to the mid- sagittal plane, noted S(p)

𝑅 1 𝑅 2 𝑝 𝑆(𝑝) (a) (e) (b) (c) (d) (f) (g) (h) (i)
x sym j (p) = C j (p) -C j • S(p) , (1.8)
where C j is restricted to be an intensity channel. Instead of comparing with the exact symmetric S(p) of the voxel, we consider, respectively, its 6, 26 and 32 neighbors in a sphere S (cf. Figure 1.7), centered on S(p). We obtain a softer version of the symmetric feature which which loosens the hard symmetric constrain and reads

x sym C,S (p) = min p ∈S {C(p) -C(p )} . (1.9)

Experiments

We train a classification forest on the whole public dataset from the MS Lesion Challenge, i.e. 20 labeled cases. Forest parameters are fixed to the following values: number of random regions |T | 950, number of trees T = 30, tree depth D = 20, lower bound for the information gain I min = 10 -5 , and the posterior threshold τ posterior = 0.5. Considerations that lead to these parameter values are detailed in Section 1.3.4.2.

The MSCG website carried out a complementary and independent evaluation of our algorithm on the previously unseen private dataset. The results, reported in Table 1.1, confirm a significant improvement over [START_REF] Souplet | An automatic segmentation of T2-FLAIR multiple sclerosis lesions[END_REF] which won won the MICCAI MS Segmentation Challenge 2008. The presented approach achieves, on average, a slightly higher true positive rate (TPR), which is beneficial, and a comparable false positive rate (FPR), but with lower volume difference (VD) and surface distance (SD) values (see Table 1.1). Pair-sample p-values were computed for the t-test on the private dataset. Results show significant improvement over the method presented in [START_REF] Souplet | An automatic segmentation of T2-FLAIR multiple sclerosis lesions[END_REF] on SD, p = 4.2 • 10 -6 and p = 6.1 • 10 -3 for CHB and UNC raters respectively.

Rater Metric [%] Souplet et al. [START_REF] Souplet | An automatic segmentation of T2-FLAIR multiple sclerosis lesions[END_REF] [START_REF] Souplet | An automatic segmentation of T2-FLAIR multiple sclerosis lesions[END_REF]. The relative mean improvement over the algorithm from [START_REF] Souplet | An automatic segmentation of T2-FLAIR multiple sclerosis lesions[END_REF] on the private dataset is defined as RI = (score RFscore Souplet )/score Souplet , as well as the p-value.

The independent quantitative evaluation confirms an improvement over [START_REF] Souplet | An automatic segmentation of T2-FLAIR multiple sclerosis lesions[END_REF], with significant improvements in boldface. Our approach achieves a slightly higher true positive rate (TPR) and a comparable false positive rate (FPR), but with much lower volume difference (VD) and surface distance (SD) values.

Discussion

Interpretation of segmentation results

Although segmentation results include most MS lesions delineated by the expert (see Figure 1.8), we observe that some MS lesions are missing. Missed MS lesions are located in specific locations which are not represented in the training data, e.g. in the corpus callosum (see Figure 1.8, slice 38). This is a limitation of the supervised approach. In this very case, however, the posterior map highlights the missed lesion in the corpus callosum as belonging to the lesion class with high uncertainty. Low confidence (or high uncertainty) reflects the incorrect spatial prior inferred from an incomplete training set. Indeed, in the training set, there are no examples of MS lesions appearing in the corpus callosum. On the contrary, the classification forest is able to detect suspicious regions with high certainty. Suspicious regions are visually very similar to MS lesions and widely represented in the training data, but they are not delineated by the expert, e.g. the left frontal lobe lesion again in Figure 1.8, slice 38. The appearance model and spatial prior implicitly learned from the training data points out that hyper-intense regions in the FLAIR MR sequence which lie in the white matter can be considered as MS lesions with high confidence.

Influence of forest parameters

This section aims at understanding the effect of the number of trees T and their depth D on the quality of segmentation results.

A 3-fold cross-validation on the public dataset is carried out for each parameter combination. Segmentation results are evaluated for each combination using two different metrics: the area under the receiver operating characteristic (ROC) curve 3 The results are reported in Figure 1.9. This analysis was carried out a posteriori using out-of-bag samples. We observe that 1) for a fixed depth, increasing the number of trees leads to better generalization; 2) for a fixed number of trees, low depth values lead to underfitting while high depth values lead to overfitting; 3) overfitting is reduced by increasing the number of trees.

Forest parameters were selected in a safety-area with respect to under-and overfitting. The safety-area corresponds to a sufficiently flat region in the evolution of the areas under the ROC and precision-recall curves. We also observe that the performance of the classifier stabilizes for sufficiently large forests. The ideal classifier would ensure area under the curve to be equal to 1 for both curves. We observe that 1) for a fixed depth, increasing the number of trees leads to better generalization; 2) for a fixed number of trees, low depth values lead to underfitting while high values lead to overfitting; 3) overfitting is reduced by increasing the number of trees.

Analysis of the relevance of feature types and channels

Unlike other classifiers, classification forests provide an elegant way of ranking the employed features according to their discriminative power. In this section, we aim at better understanding which are the most discriminative feature types (local, contextrich or symmetric) and input channels for the task of MS lesion segmentation.

As a first step of the analysis, we compute the statistics of how often the single feature types are selected, without taking into account the depth at which the features are chosen. We observe that local features were selected in 24% of the nodes, context-rich features were selected in 71% of the nodes whereas symmetry features were selected in 5% of the nodes.

In the second step of the analysis, we focus on the depth at which a given feature was selected. We find that for every tree in the forest, the root node always applies a local test on the FLAIR sequence. This means that out of all available features types, with all randomly drawn parameters, x loc FLAIR was found to be the most discriminative. At the second level of the tree, a context-rich feature on spatial priors (x cont WM,GM ) appears to be the most discriminative over all trees in the forest. The major effect of this feature is to discard all voxels which do not belong to the white matter.

The optimal decision sequence found while training the forest can thus be thought of as a threshold on the FLAIR MR sequence followed by an intersection with the white matter mask. Interestingly, this sequence matches the first and second step of the pipeline proposed by the winner method of the MICCAI 2008 challenge [START_REF] Souplet | An automatic segmentation of T2-FLAIR multiple sclerosis lesions[END_REF]. Note that in our case, this sequence is automatically generated by the forest during the training process.

Chapter Summary and Discussion

In this chapter, we have demonstrated the power of classification forests when applied to the difficult tasks of segmenting high-grade brain tumors and MS lesions. We show how classification forests can be adapted to medical image analysis settings, such that they achieve high-quality results. Furthermore, we analyze of the influence of the forest parameters, and present an investigation of the importance of the single features and input channels.

Classification forests allow us to use non-local and context-aware features, to perform simultaneous classification of the individual tissues, and to generalize well to unseen data, even with only a relatively small training set. We leverage these advantageous properties of classification forests to achieve highly accurate results in both applications.

For the segmentation of brain tumors, we use classification forests as a fundamental building block and augment it by integrating the initial test-specific probabilities for the single tissues. Since our approach has an inherent regularizing effect, which is data and application based, we can omit an explicit regularization module, which results in a system with a comparably low model complexity.

For the segmentation of MS lesions, we employ three types of features based on multi-channel intensity, and tissue priors. These features result in a context-aware classification forest, which improves the results on one of the state of the art algorithms on the public MS challenge dataset.

Regarding the input channels, in the MS lesion example, we employ prior tissue probabilities as input, additionally to the specific patient test data. In the tumor segmentation example, we have seen that using tissue-specific initial probabilities as additional input can have a beneficial and regularizing effect.

The choice of feature types depends heavily on the application. However, this step can be decoupled from the core forest functionality which makes the approach very flexible. While the particular choice of the feature types varies in our two examples, the chosen intensity-based features are similar in nature. They are intensity-based and efficient to compute, and demonstrate convincingly the potential of context-aware features in medical image analysis applications.

Fig. 1 . 1

 11 Fig. 1.1 Example of one of 40 patients in our high-grade glioma database, with tissues labeled as active cells (red), necrotic core (green), and edema (yellow). The figure shows a representative slice of the 3D image volumes.

•Fig. 1 . 2

 12 Fig. 1.2 Schematic Method Overview: Based on the input data (A), we first roughly estimate the initial probabilities for the single tissues (B), based on the local intensity information alone. In a second step, we combine the initial probabilities (B) with the input data from (A), resulting in a higher-dimensional multi-channel input for the classification forest. Through a simultaneous multi-label classification, based on non-local and context-aware features as well as initial tissue probabilities, the forest yields high-quality segmentation results (C).

Fig. 1 . 3

 13 Fig. 1.3 Examples of results on 8 patients. Obtained by a forest with GMM, MR, and DTI input, with training on 30 patients. The high accuracy of our results is quantitatively confirmed in Figs. 1.4 (AC=red, NC=green, E=yellow). Again, only representative slices of the 3D data set are shown.

Fig. 1 . 4

 14 Fig. 1.4 Average mean and standard deviations of DICE scores, for experiments on 10 random folds, with the training/testing data set sizes of 10/30, 20/20, and 30/10. From left to right, the approaches yield higher mean scores, with lower standard deviations. Our approach (rightmost) shows increased robustness to amount of training data, indicating better generalization.

Fig. 1 . 5

 15 Fig. 1.5 Sensitivity to parameters is tested by varying the number of trees T = [15, 40] and the tree depth D = [12, 20]. The figure shows mean Dice scores for ten random 30/10-cross-validation tests. We observe robustness, in particular the number of trees.

Fig. 1 . 6

 16 Fig. 1.6 Sample case from the public Grand Challenge dataset. From left to right: preprocessed T1-weighted (I T1 ), T2-weighted (I T2 ) and FLAIR MR images (I FLAIR ), the associated ground truth GT and the registered white matter atlas (P WM ).

Fig. 1 .

 1 Fig. 1.7 2D illustration of contextaware features. (a) A context-rich feature with two regions R 1 and R 2 (blue boxes) offset relatively to p (small red square). (b-d) Three examples of randomly sampled features in an extended neighborhood. (e) The symmetric feature with respect to the mid-sagittal plane. (f) The hard symmetric constraint. (g-i) The soft symmetry feature considering neighboring voxels in a sphere of increasing radius.

IFig. 1 . 8

 18 Fig. 1.8 Segmenting Case CHB05 from the public MSGC dataset. From left to right: preprocessed T1-weighted (I T1 ), T2-weighted (I T2 ) and FLAIR MR images (I FLAIR ) overlayed with the associated ground truth GT, the posterior map P lesion displayed using an inverted grey scale and the FLAIR sequence overlayed with the segmentation Seg = (P lesion τ posterior ) with τ posterior = 0.5. Segmentation results show that most of lesions are detected. Although some lesions are not detected, e.g. a lesion in the corpus calossum in slice 38, they appear enhanced in the posterior map. Moreover the segmentations of slices 38 and 42 show peri-ventricular regions, visually very similar to MS lesions, but not delineated in the ground truth.

Fig. 1 . 9

 19 Fig. 1.9 Influence of forest parameters on segmentation results. Both curves were plotted using mean results from a 3-fold cross validation on the public dataset. Left: the figure shows the influence of forest parameters on the area under the precision-recall curve. Right: the figure shows the influence of forest parameters on the area under the ROC curve.The ideal classifier would ensure area under the curve to be equal to 1 for both curves. We observe that 1) for a fixed depth, increasing the number of trees leads to better generalization; 2) for a fixed number of trees, low depth values lead to underfitting while high values lead to overfitting; 3) overfitting is reduced by increasing the number of trees.

Table 1 .

 1 Class. Forest RI [%] p-value 1 Average results computed by the MSGC on the private dataset and compared to the method presented in

		VD	86.48 ± 104.9 52.94 ± 28.63 -38.7 0.094
	CHB	SD TPR	8.20 ± 10.89 57.45 ± 23.22 58.08 ± 20.03 +1.0 5.27 ± 9.54 -35.7 4.2 • 10 -6 0.90
		FPR	68.97 ± 19.38 70.01 ± 16.32 +1.5	0.70
		VD	55.76 ± 31.81 50.56 ± 41.41 -9.4	0.66
	UNC	SD TPR	7.4 ± 8.28 49.34 ± 15.77 51.35 ± 19.98 +3.9 5.6 ± 6.67 -24.3 6.1 • 10 -3 0.54
		FPR	76.18 ± 17.07 76.81 ± 11.70 +0.1	0.83

Segmentation of Brain Lesions from multi-channel MRI

A more detailed description of our work is available in[START_REF] Zikic | Decision forests for tissue-specific segmentation of high-grade gliomas in multi-channel mr[END_REF].

More details can be found in[START_REF] Geremia | Spatial decision forests for MS lesion segmentation in multi-channel magnetic resonance[END_REF].

With TP, FP, TN, and FN denoting the number of true/false positive/negatives respectively, we have TPR= TP/(TP + FN), FPR= FP/(FP + TN), and PPV= TP/(TP + FP).

is funded by a Clinician Scientist Award from the National Institute for Health Research (NIHR) O. M. Thomas is a Clinical Lecturer supported by the NIHR Cambridge Biomedical Research Centre 1 O.Clatz O.Clatz