Joris Van Der Hoeven
email: joris@texmacs.org

Faster relaxed multiplication *

Keywords: power series, multiplication, on-line algorithm, FFT, computer algebra A.M.S. sub ject classification: 68W30, 30B10, 68W25, 33F05, 11Y55, 42-04

published or not. The documents may come

Introduction

Relaxed resolution of recursive equations

Let A be an effective (possibly non-commutative) ring; i.e., we assume data structures for representing the elements of A and algorithms for performing the ring operations +, ¡ and . The aim of algebraic complexity theory is to study the cost of basic or more complex algebraic operations over A (such as the multiplication of polynomials or matrices) in terms of the number of operations in A.

The algebraic complexity usually does not coincide with the bit complexity, which also takes into account the potential growth of the actual coefficients in A. Nevertheless, understanding the algebraic complexity usually constitutes a first useful step towards understanding the bit complexity. Of course, in the special case when A is a finite field, both complexities coincide up to a constant factor.

One of the most central operations is polynomial multiplication. We will denote by M A (n) the number of operations required to multiply two polynomials of degrees <n in A[x]. If A admits primitive 2 p -th roots of unity for all p, then we have M A (n) = O(n log n) using FFT multiplication, which is based on the fast Fourier transform [START_REF] Cooley | An algorithm for the machine calculation of complex Fourier series[END_REF]. In general, it has been shown [START_REF] Schönhage | Schnelle Multiplikation großer Zahlen[END_REF][START_REF] Cantor | On fast multiplication of polynomials over arbitrary algebras[END_REF] that M A (n) = O(n log n log log n). The complexities of most other operations (division, Taylor shift, extended g.c.d., multipoint evaluation, interpolation, etc.) can be expressed in terms of M A (n). Often, the cost of such other operations is simply O ˜(M A (n)) = O ˜(n), where O ˜(T (n)) stands for O(T (n) (log T (n)) O (1) ); see [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF][START_REF] Bini | Polynomial and matrix computations[END_REF][START_REF] Zur Gathen | Modern Computer Algebra[END_REF] for some classical results along these lines.

The complexity of polynomial multiplication is fundamental for studying the cost of operations on formal power series in A [[z]] up to a given truncation order n. Clearly, it is possible to perform the multiplication up to order n in time O(M A (n)): it suffices to multiply the truncated power series at order n and truncate the result. Using Newton's method, and assuming that Q A, it is also possible to compute exp, sin, etc. up to order n in time O(M A (n)). More generally, it has been shown in [START_REF] Brent | Fast algorithms for manipulating formal power series[END_REF][START_REF] Van Der Hoeven | Relax, but don't be too lazy[END_REF][START_REF] Sedoglavic | Méthodes seminumériques en algèbre différentielle ; applications à l'étude des propriétés structurelles de systèmes différentiels algébriques en automatique[END_REF][START_REF] Van Der Hoeven | Newton's method and FFT trading[END_REF] that the power series solutions of algebraic differential equations with coefficients in A [[z]] can be computed up to order n in time O(M A (n)). However, in this case, the "O" hides a nontrivial constant factor which depends on the expression size of the equation that one wants to solve.

The relaxed approach for computations with formal power series makes it possible to solve equations in quasioptimal time with respect to the sparse expression size of the equations. The idea is to consider power series f 2 A[[z]] as streams of coefficients f 0 ; f 1 ; ... and to require that all operations are performed "without delay" on these streams. For instance, for a multiplication h = f g of two power series f ; g 2 A[[z]], we require that h n is computed as soon as f 0 ; g 0 ; ...; f n ; g n are known. Any algorithm which has this property will be called a relaxed or online algorithm for multiplication.

Given a relaxed algorithm for multiplication, it is possible to let the later coefficients f n+1 ; g n+1 ; f n+2 ; g n+2 ; ... of the input depend on the known coefficients h 0 ; ...; h n of the output. For instance, given a power series f 2 A[z] with f 0 = 0, we may compute g = exp f using the formula

g = Z f 0 g; (1)
provided that Q A. Indeed, extraction of the coefficient of z n in g and R f 0 g yields

g n = 1 n (f 0 g) n¡1 ;
and (f 0 g) n¡1 only depends on g 0 ; ...; g n¡1 . More generally, we define an equation of the form

f = Φ(f ) (2)
to be recursive , if Φ(f ) n only depends on f 0 ; ...; f n¡1 . Replacing A by A r , we notice that the same terminology applies to systems of r equations. In the case of an implicit equation, special rewriting techniques can be implied in order to transform the input equation into a recursive equation [START_REF] Van Der Hoeven | From implicit to recursive equations[END_REF][START_REF] Van Der Hoeven | Relaxed resolution of implicit equations[END_REF][START_REF] Berthomieu | Relaxed p-adic hensel lifting for algebraic systems[END_REF].

Let R A (n) denote the cost of performing a relaxed multiplication up to order n. If Φ is an expression which involves s multiplications and t other "linear time" operations (additions, integrations, etc.), then it follows that (2) can be solved up to order n in time

O(s R A (n) + t n). If we had R A (n) = O(M A (n))
, then this would yield an optimal algorithm for solving [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF] in the sense that the computation of the solution would essentially require the same time as its verification.

Known algorithms for relaxed multiplication

The naive O(n 2 ) algorithm for computing h = f g, based on the formula

h n = f 0 g n + f 1 g n¡1 + + f n g 0 ;
is clearly relaxed. Unfortunately, FFT multiplication is not relaxed, since h 0 ; ...; h n are computed simultaneously as a function of f 0 ; g 0 ; ...; f n ; g n , in this case.

In [START_REF] Van Der Hoeven | Lazy multiplication of formal power series[END_REF][START_REF] Van Der Hoeven | Relax, but don't be too lazy[END_REF] it was remarked that Karatsuba's O(n log 3/log 2 ) algorithm [START_REF] Karatsuba | Multiplication of multidigit numbers on automata[END_REF] for multiplying polynomials can be rewritten in a relaxed manner. Karatsuba multiplication and its relaxed version thus require exactly the same number of operations. In [START_REF] Van Der Hoeven | Lazy multiplication of formal power series[END_REF][START_REF] Van Der Hoeven | Relax, but don't be too lazy[END_REF], an additional fast relaxed algorithm was presented with time complexity

R A (n) = O(M A (n) log n). (3)
We were recently made aware of the fact that a similar algorithm was first published in [START_REF] Fischer | Fast on-line integer multiplication[END_REF]. However, this early paper was presented in a different context of online (relaxed) multiplication of integers (instead of power series), and without the application to the resolution of recursive equations (which is quite crucial from our perspective).

An interesting question remained: can the bound (3) be lowered further, be it by a constant factor? In [START_REF] Van Der Hoeven | Relaxed multiplication using the middle product[END_REF], it was first noticed that an approximate factor of two can be gained if one of the multiplicands is known beforehand. For instance, if we want to compute g = exp f for a known series f with f 0 = 0, then the coefficients of f 0 are already known in the product f 0 g in (1), so only one of the inputs depends on the output. An algorithm for the computation of h = f g is said to be semi-relaxed , if h n is written to the output as soon as f 0 ; ...; f n are known, but all coefficients of g are known beforehand. We will denote by S A (n) the complexity of semi-relaxed multiplication. We recall from [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF] (see also Section 3) that relaxed multiplication reduces to semi-relaxed multiplication:

R A (n) = O(S A (n)).
It has recently been pointed out [START_REF] Lebreton | A simple and fast online power series multiplication and its analysis[END_REF] that the factor 2 that was gained in the case of semi-relaxed multiplication can also be gained in the general case.

The first reduction of (3) by a non-constant factor was published in [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF], and uses the technique of FFT blocking (which has also been used for the multiplication of multivariate polynomials and power series in [START_REF] Van Der Hoeven | Relax, but don't be too lazy[END_REF]Section 6.3], and for speeding up Newton iterations in [START_REF] Bernstein | Removing redundancy in high precision Newton iteration[END_REF][START_REF] Van Der Hoeven | Newton's method and FFT trading[END_REF]). Under the assumption that A admits primitive 2 k -th roots of unity for all k (or at least for all k with 2 k 6 n), we showed that

R A (n) = O(n log n e 2 log 2 p log log n p ). (4)
The function e 2 log 2 p log log n p has slower growth than any strictly positive power of log n. It is convenient to write

F (n) = O [ (T (n)) whenever F (n) = O(T (n) (log T (n)) ) for all > 0. In particular, it follows that R A (n) = O [ (n log n).
In Section 3, we will recall the main ideas from [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF] which lead to the complexity bound (4).

In fact, in Section 4, we will see that the complexity bound from [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF] can be further reduced to

R A (n) = O(n log n e 2log 2 p log log n p log log n p ).
Since such complexity bounds involve rather complex expressions, it will be convenient to use the following abbreviations:

R (n) = n log n e 2log 2 p log log n p log log n p R (n) = R (n) log log n R (n) = R (n) (log log n) 2 log log log n. Clearly, R (n) = O(R (n)) = O(R (n)) = O [ (n log n).

Improved complexity bounds

We recall that the characteristic of a ring A is the integer k 2 N such that the canonical ring homomorphism Z ! A has kernel k Z. If A is torsion-free as a Z-module (i.e. k x = 0 ) x = 0 for any k 2 Z n f0g and x 2 A), then we will say that A admits an effective partial division by integers if there exists an algorithm which takes k 2 Z n f0g and x 2 k A on input and which returns the unique y 2 A with x = k y on output. We will count a unit cost for such divisions. The main result of this paper is:

Theorem 1. Assume that one of the following two holds:

A is an effective ring of characteristic zero, which is torsion-free as a Z-module, and which admits an effective partial division by integers.

A is an effective ring of positive characteristic.

Then we have

R A (n) = O [ (n log n). (5)
We notice that the theorem holds in particular if A is an effective field. In Section 8, we will also consider the relaxed multiplication of p-adic numbers, with p 2 N and p > 2. If we denote by I(k) the bit complexity of multiplying two k-bit integers, then [START_REF] Fischer | Fast on-line integer multiplication[END_REF] essentially provided an algorithm of bit complexity O(I(n) log n) for the relaxed multiplication of 2-adic numbers at order O(2 n ). Various algorithms and benchmarks for more general p were presented in [START_REF] Berthomieu | Relaxed algorithms for p-adic numbers[END_REF]. It is also well known [START_REF] Toom | The complexity of a scheme of functional elements realizing the multiplication of integers[END_REF][START_REF] Cook | On the minimum computation time of functions[END_REF][START_REF] Schönhage | Schnelle Multiplikation großer Zahlen[END_REF][START_REF] Fürer | Faster integer multiplication[END_REF] that

I(n) = O [ (n log n). Let R p (n)
denote the bit complexity of the relaxed multiplication of two p-adic numbers modulo p n . In Section 8, we will prove the following new result:

Theorem 2. Let p 2 N with p > 2. Then we have R p (n) = O [ (n log n log p log log p);
uniformly in n and p.

For comparison, the best previously known bound for relaxed multiplication in Z p was

R p (n) = O(I(n (log p + log n)) log n) = ( O [ (n log 3 n) if p = O(n) O [ (n log 2 n log p) if n = O(p)
We thus improved the previous bound by a factor log n/ log log p at least, up to sublogarithmic terms.

The main idea which allows for the present generalizations is quite straightforward. In our original algorithm from [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF], the presence of sufficiently many primitive 2 k -th roots of unity in A gives rise to a quasi-optimal evaluationinterpolation strategy for the multiplication of polynomials. More precisely, given two polynomials of degrees <n, their FFT-multiplication only requires O(n) evaluation and interpolation points, and both the evaluation and interpolation steps can be performed efficiently, using only O(n log n) operations. Now it has recently been shown [START_REF] Bostan | Polynomial evaluation and interpolation on special sets of points[END_REF] that quasi-optimal evaluation-interpolation strategies still exist if we evaluate and interpolate at points in geometric progressions instead of roots of unity. This result is the key to our new complexity bounds, although further technical details have to be dealt with in order to make things work for various types of effective rings A. We also notice that the main novelty of [START_REF] Bostan | Polynomial evaluation and interpolation on special sets of points[END_REF] concerns the interpolation step. Fast evaluation at geometric progressions was possible before using the so called chirp transform [START_REF] Rabiner | The chirp z-transform algorithm and its application[END_REF][START_REF] Bluestein | A linear ltering approach to the computation of discrete Fourier transform[END_REF]. For effective rings A of positive characteristic, this would actually have been sufficient for the proving the bound (5).

Our paper is structured as follows. Since the algorithms of [START_REF] Bostan | Polynomial evaluation and interpolation on special sets of points[END_REF] were presented in the case when A is an effective field, Section 2 starts with their generalization to more general effective rings A. These generalizations are purely formal and contain no essentially new ideas. In Section 3, we give a short survey of the algorithm from [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF], but we recommend reading the original paper for full technical details. In Section 4, we sharpen the complexity analysis for the algorithm from [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF]. In Section 5, we prove Theorem 1 in the case when A has characteristic zero. In Section 6, we turn our attention to the case when A has prime characteristic p. If the characteristic is sufficiently large, then we may find sufficiently large geometric progressions in A \ Z in order to generalize the results from Section 5. Otherwise, we have to work over A F p k for some sufficiently large k. In Section 7, we complete the proof of Theorem 1; the case when the characteristic is a prime power is a refinement of the result from Section 6. The remaining case is done via Chinese remaindering. In Section 8, we will prove Theorem 2.

Acknowledgments. I am grateful to the referees for their detailed comments and suggestions. A special thanks goes to the referee who made a crucial suggestion for the improved complexity analysis in Section 4.

Multipoint evaluation and interpolation

Let D be a (commutative) effective integral domain and let K be its quotient field. Assume that K has characteristic zero. Let M be an effective torsion-free D-module and V = K D M. Elements of K and V are fractions x/s with x 2 D (resp. x 2 M) and s 2 D n f0g, and the operations ¡; +; on such fractions are as usual:

¡ x s = ¡x s x s + y t = t x + s y s t x s y t = x y s t
For x/s 2 K , we also have (x/s) ¡1 = s/x. It follows that K is an effetive field and V an effective K-vector space. Moreover, all field operations in K (and all vector space operations in V) can be performed using only O(1) operations in D (resp. D or M).

We will say that M admits an effective partial division, if for every s 2 D n f0g and x 2 s M, we can compute the unique y 2 M with x = s y. In that case, and we will count any division of the above kind as one operation in M. Similarly, given a fixed s 2 D n f0g, we say that M admits an effective partial division by sx 2 s M, we can compute the unique y 2 M with x = s y. Given n 2 N, we define

M[z] n = fP 2 M[z]: deg P < ng. Given P 2 D[z] n and Q 2 M[z] n ,

Lemma 3. Let D be an effective integral domain and M an effective torsion-free D-module.

There exists a constant K, such that the following holds: for any n > 0, P 2 M[z] n and q 2 D n f0g such that 1; q; ...; q n¡1 are pairwise distinct, and such that D admits effective divisions by q and q ¡ 1; q 2 ¡ 1; ...; q n¡1 ¡ 1, we have: a) We may compute P (1); ...; P (q n¡1 ) from P using K M M (n) operations in D and M.

b) We may reconstruct P from P (1); ...; P (q n¡1 ) using K M M (n) operations in D and M.

Proof. In the case when D = K is a field and M = V = K, this result was first proven in [START_REF] Bostan | Polynomial evaluation and interpolation on special sets of points[END_REF]. More precisely, the conversions can be done using the algorithms NewtonEvalGeom, NewtonInterpGeom, Newton-ToMonomialGeom and MonomialToNewtonGeom in that paper. Examining these algorithms, we observe that general elements in D are only multiplied with elements in Z[q] and divided by elements of the set fq; q ¡ 1; q 2 ¡ 1; ...; q n¡1 ¡ 1g. In particular, the algorithms can still be applied in the more general case when D = K is a field and M = V a vector space.

If D is only an effective integral domain and M an effective torsion-free D-module with an effective partial division, then we define the effective field K and the effective vector space V as above, and we may still apply the generalized algorithms for multipoint evaluation and interpolation in V. In particular, both multipoint evaluation and interpolation can still be done using O(M V (n)) operations in K and V, whence O(M M (n)) operations in D and M. If we know that the end-results of these algorithms are really in the subspace M n of V n (or in the submodule

M[z] n of V[z] n ), then we use the partial division in M to replace their representations in V n (or V[z] n ) by represen- tations in M n (or M[z] n ).

Survey of blockwise relaxed multiplication

Let A be an effective (possibly non-commutative) ring and recall that

A[z] n = fP 2 A[z]: deg P < ng.
Given a power series f 2 A[[z]] and i < j, we will also use the notations

f i; j = f i z i + + f j ¡1 z j ¡1 f ; j = f 0 + + f j ¡1 z j ¡1 f i; = f i z i + f i+1 z i+1 + .
The fast relaxed algorithms from [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF] are all based on two main changes of representation: "blocking" and the fast Fourier transform. Let us briefly recall these transformations and how to use them for the design of fast algorithms for relaxed multiplication.

Blocking and unblocking. Given a block size b > 0, the first operation of blocking rewrites a power series

f 2 A[[z]] as a series in y = z b with coefficients in A[z] b B b (f ) = X i X 06j <b f ib + j z j y i 2 A[z] b [[y]].
Given f ; g 2 A[[z]], we may then compute f g using

f g = B b ¡1 (B b (f ) B b (g));
where and it is classical [START_REF] Cooley | An algorithm for the machine calculation of complex Fourier series[END_REF] that both FFT ! and FFT ! ¡1 can be computed using O(b log b) operations in A. The operations FFT ! and FFT ! ¡1 extend naturally to

B b (f ) B b (g) 2 A[z] 2b [[y]] and B b ¡1 : A[z] 2b [[y]] ! A[[z]] X i P i (z) y i 7 ! X i P i (z) z bi .

Discrete Fourier transforms. Assume now that

A[z] 2b [[y]] via FFT ! X i f i y i = X i FFT ! (f i ) y i . Given f ; g 2 A[[z]],
this allows us to compute f g using the formula

f g = B b ¡1 (FFT ! ¡1 (FFT ! (B b (f )) FFT ! (B b (g)))); (6)
where Relaxed multiplication. In formula (6) the m-th coefficient of the right hand side may depend on the (m + b ¡ 1)-th coefficients of f and g. In order to make (6) suitable for relaxed multiplication, we have to treat the first b coefficients of f and g separately. Indeed, the formula

FFT ! (B b (f )) FFT ! (B b (g)) is a pointwise product in A 2b
f g = f ;b g ;b + f ;b g b; + f b; g ;b + B b ¡1 (FFT ! ¡1 (FFT ! (B b (f b; )) FFT ! (B b (g b; ))))
allows for the relaxed computation of f g at order m b using at most

R A (m b) 6 R A (b) + 2 m S A (b) + 2 b R A (m) + O(m b log b)
operations in A. Similarly, the formula

f g = f ;b g + B b ¡1 (FFT ! ¡1 ()) (7)
= FFT ! (B b (f b; )) FFT ! (B b (g))
allows for the semi-relaxed computation of f g at order m b using at most

S A (m b) 6 m S A (b) + 2 b S A (m) + O(m b log b) (8)
operations in A. For a given expansion order n, one may take b n p , and use the above formula in a recursive manner. This yields [21, Theorem 11]

R A (n) = O(n (log n) log 3/log 2 ).
Remark 4. Since the block size b is chosen as a function of n, the above method really describes a relaxed algorithm for computing the product up to an order n which is specified in advance. In fact, such an algorithm automatically yields a genuine relaxed algorithm with the same complexity (up to a constant factor), by doubling the order n each time when needed.

Reduction to semi-relaxed multiplication. In the above discussion, we both provided bounds for R A (n) and S A (n). In fact, there exists a straightforward reduction of relaxed multiplication to semi-relaxed multiplication. First of all, the relaxed multiplication of two power series f ; g 2 A[[z]] up to order O(z n ) clearly reduces to the relaxed multiplication of the two polynomials f ;n and g ;n up to order O(z 2n ). Now the formula

f ;2n g ;2n = f ;n g ;n + f n;2n g ;n + f ;n g n;2n + f n;2n g n;2n
shows that a relaxed product of two polynomials f ;2n and g ;2 n of degrees <(2 n) reduces to a relaxed product f ;n g ;n of half the size, two semi-relaxed products f n;2n g ;n , f ;n g n;2n , and one non-relaxed product f n;2 n g n;2 n . Under the assumptions that M A (n)/n and S A (n)/n are increasing, a routine calculation thus yields

R A (n) = O(S A (n)).
Multiple block sizes. Instead of using a single block size b, one may use several block sizes. Applying this technique, we proved in [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF]Theorem 12] that

R A (n) = O(S A (n)) = O(n log n e 2 log 2 p log log n p ). (9)

Improved complexity analysis

One of the referees suggested to take b n 2/3 instead of b n p in [START_REF] Bostan | Polynomial evaluation and interpolation on special sets of points[END_REF]. As a matter of fact, it is even better to take b exp (log n/exp ( 2 log 2 p log log n p )). In this section, we will show that this leads to the bound

R A (n) = O(R (n));
which further improves on [START_REF] Brent | Fast algorithms for manipulating formal power series[END_REF]. We will prove a slightly more general result, which is useful for the analysis of algorithms which satisfy complexity bounds similar to [START_REF] Bostan | Polynomial evaluation and interpolation on special sets of points[END_REF].

Φ(k) = k e a log k p log k p (k);
where a = 2 log 2 p . Then there exist constants A > 0 and k 0 such that for all k > k 0 , " 1 ; " 2 2 (¡1; 1), and = k/e a log k p , we have

Φ(k ¡ + " 1 ) + 2 Φ( + " 2 ) 6 Φ(k) ¡ A k (k).
Proof. Notice that k ¡ + " 1 6 k and + " 2 6 k for sufficiently large k. We have

e a log(k ¡+"1) p = e a log k ¡e -a log k √ (1+O(1)) q = e a log k p 1 ¡ a + O(1) 2 log k p e a log k p ! .
For a suitable constant A > 0 and all sufficiently large k, it follows that

Φ(k ¡ + " 1 ) 6 ((k ¡ ) e a log k p log k p ¡ A k) (k). (10)
We also have

a log ( + " 2 ) p 6 a log k ¡ a log k p + O(1/log k) p = a log k p ¡ a 2 2 + a 3 8 log k p + O 1 log k ; whence e a log (+"2) p log ( + " 2 ) p = e a log k p 2 log k p 1 4 a ¡ a 3 8 log k p + O 1 log k
For all sufficiently large k, it follows that e a log (+"2)

p log ( + " 2 ) p 6 e a log k p 2 log k p .
Consequently,

2 Φ( + " 2 ) 6 e a log k p log k p (k). ( 11
)
Adding up ( 10) and ( 11), we obtain

Φ(k ¡ + " 1 ) + 2 Φ( + " 2 ) 6 (e a log k p log k ¡ A) k (k) = Φ(k) ¡ A k (k);
for all sufficiently large k. Then

T(n) = O(R (n) (n)).
Proof. We define functions U; : R > ! R > by

U(k) = T(dexp (k)e) exp (k) (k) = (dexp (k)e)
and let Φ, A and k 0 be as in Lemma 5. Without loss of generality, we may pick k 0 sufficiently large such that k 0 > exp [START_REF] Brent | Fast algorithms for manipulating formal power series[END_REF] and such that (12) holds for n > n 0 := dexp (k 0 )e. Let n 2 N be such that n > n 0 and denote k = log n and = k/e a log k p . For certain " 1 ; " 2 2 (¡1; 1), we have log m = log dexp (log n/e a log log n p )e = + " 2 and log b = log dn/me = k ¡ + " 1 . Now [START_REF] Cooley | An algorithm for the machine calculation of complex Fourier series[END_REF] implies

U(k) 6 U(k ¡ + " 1 ) + 2 U( + " 2 ) + 2 k (k).
Let K = log N and C = max fsup k2K ,k 6k0 U(k)/Φ(k); 2/Ag. Let us prove by induction that U(k) 6 C Φ(k) for all k 2 K. This is clear for k 6 k 0 . Assume now that k > k 0 and U(k 0 ) 6 C Φ(k 0 ) for all k 0 < k. Then, with the above notations, k 0 > exp (9) implies k ¡ + " 1 < k and + " 2 < k, whence

U(k) 6 U(k ¡ + " 1 ) + 2 U( + " 2 ) + 2 k (k); 6 C (Φ(k ¡ + " 1 ) + 2 Φ( + " 2 )) + 2 k (k) 6 C Φ(k) + (2 ¡ C A) k (k) 6 C Φ(k);
as desired. For all n 2 N , we have thus shown that

T(n) 6 C n Φ(log n) = C R (n) (n).

Relaxed multiplication in characteristic zero

Let us now consider the less favourable case when A is an effective ring which does not necessarily contain primitive 2 k -th roots of unity for arbitrarily high k. In this section, we will first consider the case when A is torsion-free as a Z-module and also admits a partial algorithm for division by integers. Given a block size b 2 N and q 2 Z n f¡1; 0; 1g (say q = 2), we will replace the discrete Fourier transform FFT ! at a (2 b)-th primitive root of unity by multipoint evaluation at 1; ...; q 2b¡1 . More precisely, we define

E q, 2b : A[z] 2b ! A 2b
P 7 ! (P (1); P (q); ...; P (q 2b¡1 ))

and the inverse transform E q, 2b ¡1 : im E q, 2b ! A[z] 2b . By Lemma 3, these transforms can both be computed using O(M A (b)) operations in A. In a similar way as for FFT ! and FFT ! ¡1 , we extend E q, 2b and E q, 2b ¡1 to power series in y.

Theorem 7. Let A both be an effective ring and an effective torsion-free Z-module with an effective partial division by elements in

Z n f0g. Then R A (n) = O(R (n)).
Proof. It suffices to prove the complexity bound for semirelaxed multiplication. Instead of [START_REF] Bluestein | A linear ltering approach to the computation of discrete Fourier transform[END_REF], we now compute f g using

f g = f ;b g + B b ¡1 (E q, 2b ¡1 ()); (13)
= E q, 2b (B b (f b; )) E q, 2b (B b (g)).
The bound (8) then has to be replaced by

S A (m b) 6 m S A (b) + 2 b S A (m) + O(m M A (b)). (14)
Plugging in the bound M A (b) = O(b log b log log b) from [START_REF] Cantor | On fast multiplication of polynomials over arbitrary algebras[END_REF] and applying Theorem 6, the result follows.

Relaxed multiplication in prime characteristic

Let A now be an effective ring of prime characteristic p.

For expansion orders n > p, the ring A does not necessarily contain n distinct points in geometric progression. Therefore, in order to apply Lemma 3, we will first replace A by a suitable extension, in which we can find sufficiently large geometric progressions.

Given n, let k = 2 l

log (n + 1)
2 log p m be even with p k > n. Let

P 2 F p [z] be such that the finite field F p k is isomorphic to F p [z]/(P ).
Then the ring

B := A[z]/(P )
has dimension k over A as a vector space, so we have a natural A-linear bijection

Λ: A[z] k ! B A 7 ! A mod P .
The ring B is an effective ring and one addition or subtraction in B corresponds to k additions or subtractions in A. Similarly, one multiplication in B can be done using

O(M A (k)) operations in A.
In order to multiply two series f ; g 2 A[[z]] up to order O(z n ), the idea is now to rewrite f and g as series in B[[u]] with u = z k/2 . If we want to compute the relaxed product, then we also have to treat the first k/2 coefficients apart, as we did before for the blocking strategy. More precisely, we will compute the semi-relaxed product f g using the formula

f g = f ;k/2 g + B k/2 ¡1 (Λ ¡1 ()); = Λ(B k/2 (f k/2; )) Λ(B k/2 (g));
where we extended Λ to A[z] k [[u]] in the natural way:

Λ X i>0 f i u i ! = X i>0 Λ(f i ) u i .
From the complexity point of view, we get

S A (n) 6 2 n k S A k 2 + S B 2 n k O(M A (k)). (15)
Since B contains a copy of F p k, it also contains at least p k ¡ 1 > n points in geometric progression. For the multiplication up to order 2 n/k of two series with coefficients in B, we may thus use the blocking strategy combined with multipoint evaluation and interpolation.

Theorem 8. Let A be an effective ring of prime characteristic p. Then

R A (n) = O(R (n)).
Proof. With the notations from above, we may find a primitive (p k ¡ 1)-th root of unity q in F p k B. We may thus use formula [START_REF] Fischer | Fast on-line integer multiplication[END_REF] for the semi-relaxed multiplication of two series in B[[z]] up to order 2 n/k 6 n. In a similar way as in the proof of Theorem 7, we thus get

S B 2 n k = O R 2 n k = O R(n) k .
Using classical fast relaxed multiplication [START_REF] Van Der Hoeven | Lazy multiplication of formal power series[END_REF][START_REF] Van Der Hoeven | Relax, but don't be too lazy[END_REF][START_REF] Fischer | Fast on-line integer multiplication[END_REF], we also have

S A k 2 = O(k log 2 k log log k);
whence [START_REF] Zur Gathen | Modern Computer Algebra[END_REF] simplifies to 16), so the bound further reduces into

S A (n) = O R (n) MA(k) k . (16)
R A (n) = O(R (n)).
Remark 10. In our complexity analysis, we have not taken into account the computation of the polynomial Similarly, there both exist randomized and deterministic algorithms [START_REF] Shparlinski | On primitive elements in nite elds and on elliptic curves[END_REF][START_REF] Shoup | Searching for primitive roots in nite elds[END_REF] for the efficient computation of primitive (p k ¡ 1)-th roots of unity in F p k. In particular, thanks to [31, Theorem 1] such a primitive root of unity can always be computed in time O ˜(p k/2 ), when using a naive algorithm for factoring p k ¡ 1.

P 2 F p [z] with F p k = F p [z]

Relaxed multiplication in positive characteristic

Let us now show that the technique from the previous section actually extends to the case when A is an arbitrary effective ring of positive characteristic. We first show that the algorithm still applies when the characteristic of A is a prime power. We then conclude by showing how to apply Chinese remaindering in our setting. Theorem 11. Let A be an effective ring of prime power characteristic s = p r . Then

R A (n) = O(R (n)). Proof. Taking k = 2 l log (n + 1) 2 log p m
, let P of degree k be as in the previous section and pick a monic polynomial P ˜of degree k in (Z/s Z)[z] such that the reduction (P ˜) of P modulo p yields P . Then we get a natural commutative diagram

(Z/s Z)[z]/(P ˜) , ¡! A[z]/(P ˜) ¡ π ¡ π F p [z]/(P ) , ¡! (A/p A)[z]/(P );
where stands for reduction modulo p. In particular, we have an epimorphism

: (Z/s Z)[z]/(P ˜) ! F p [z]/(P ) = F p k ;
with ker = (p).

Using the strategy of p-adic blocking, a semi-relaxed product in Z p may then be reduced to one semi-relaxed product in Z p r and one relaxed multiplication with an integer in f0; ...; p r ¡ 1g. In other words, By Lemma 16, we also have

S p r ¡ n r = O ¡ R Z ¡ n r ; log 2 (p r ) = O ¡ I(r log p + log n) n r log n e 2log 2 p log log n p (log log n) 3/2 = O ¡ I(r log p) 1 r R (n) = O((log p) `log `R (n)) Notice that n r S p (r) = O S p r l n r m ;
which completes the proof of the theorem.

Final remarks

For the moment, we have not implemented any of the new algorithms in practice. Nevertheless, our old implementation of the algorithm from [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF] allowed us to gain some insight on the practical usefulness of blockwise relaxed multiplication. Let us briefly discuss the potential impact of the new results for practical purposes.

Characteristic zero.

In characteristic zero, our focus on algebraic complexity makes the complexity bounds more or less irrelevant from a practical point of view. In practice, two cases are of particular interest: floating point coefficients (which were already considered in [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF]) and integer coefficients (rational coefficients can be dealt with similarly after multiplying by the common denominator).

In the case of integer coefficients, it is best to re-encode the integers as polynomials in F p [x] for a prime number which fits into a machine word and such that p admits many 2 k -th roots of unity (it is also possible to take several primes p and use Chinese remaindering). After that, one may again use the old algorithm from [START_REF] Van Der Hoeven | New algorithms for relaxed multiplication[END_REF]. Also, integer coefficients usually grow in size with n, so one really should see the power series as a bivariate power series in F p [[x; z]] with a triangular support. One may then want to use TFT-style multiplication [START_REF] Van Der Hoeven | The truncated Fourier transform and applications[END_REF][START_REF] Van Der Hoeven | Notes on the Truncated Fourier Transform[END_REF] in order to gain another constant factor. Finite fields. For large finite fields, it is easy to find large geometric progressions, so the algorithms of this paper can be applied without the need to consider field extensions. Moreover, for finite fields of the form F p k with p sufficiently large and k > 1, it is possible to choose q 2 F p , thereby speeding up evaluation and interpolation. For small finite fields of the form F p k, it is generally necessary to make the initial investment of working in a larger ring with sufficiently large geometric progressions. Of course, instead of the ring extensions considered in Section 6, we may directly use field extensions of the form F p l with k j l.

Semi-relaxed multiplication. In principle, a factor 2 can be gained in the semi-relaxed (resp. general) case using the technique from [START_REF] Van Der Hoeven | Relaxed multiplication using the middle product[END_REF] (resp. [START_REF] Lebreton | A simple and fast online power series multiplication and its analysis[END_REF]). Unfortunately, the middle product (resp. the FFT-trick used in [START_REF] Lebreton | A simple and fast online power series multiplication and its analysis[END_REF]) is not always easy to implement. For instance, if we rely on Kronecker substitution for multiplications in Z[z], then we will need to implement an ad hoc analogue for the middle product. Since we did not use a fast algorithm for middle products for our benchmarks in [21, Section 5], the timings for the semi-relaxed product in were only about 25% instead of 50% better than the timings for the fully relaxed product. Nevertheless, modulo increased implementation efforts, we stress that a 50% gain should be achievable.

Cache friendliness. So far, we have not investigated the cache friendliness of blockwise relaxed multiplication, and it can be feared that a lot of additional work is required in order to make our algorithms really efficient from this point of view.

Bilinear maps. In order to keep the presentation reasonably simple, we have focussed on the case when A is an effective ring. In fact, a more general setting for relaxed multiplication is to consider a bilinear mapping : M 1 M 2 ! M 3 , where M 1 , M 2 and M 3 are effective A-modules, and extend it into a mapping ˆ:

M 1 [[z]] M 2 [[z]] ! M 3 [[z]
] by ˆ(f ; g) = P i, j (f i ; g j ) z i+ j . Under suitable hypothesis, the algorithms in this paper generalize to this setting. Skew series. The relaxed approach can also be generalized to the case when the coefficients of the power series are operators which commute with monomials z i in a nontrivial way. More precisely, assume that we have an effective ring homomorphism : A ! A such that z a = (a) z for all a 2 K. For instance, one may take A = Q[] with = z @/@z, so that P () z = z P ( + 1). Given a commutation rule of this kind, we define a skew multiplication on A[[z]] by

" X i>0 f i z i #" X j >0 g j z j # = X i, j >0
f i ( i g j ) z i+ j .

If M A (n) denotes the cost of multiplying two polynomials P z i and Q z j in A[z] with deg P ; deg Q < n, then the classical fast relaxed multiplication algorithm from [START_REF] Van Der Hoeven | Relax, but don't be too lazy[END_REF][START_REF] Fischer | Fast on-line integer multiplication[END_REF] generalizes and still admits the time complexity O(M A (n) log n). However, the blockwise algorithm from this paper does not generalize to this setting, at least not in a straightforward way.

Bibliography

  we will denote by M M (n) the number of operations in D and M which are needed in order to compute the product P Q 2 M[z].

A 3 1 / 2 ,P 7 !

 127 that b 2 f1; 2; 4; 8; ...g, and that A admits a primitive (2 b)-th root of unity ! = ! 2b . Then the discrete Fourier transform provides us with an isomorphism FFT ! : A[z] 2b ! A 2b (P (1); P (!); ...; P (! 2b¡1 ));

.

  The first m b coefficients of f g can be computed using at most 2 b M A (m) + O(m b log b) operations in A.

Lemma 5 .

 5 Let : R > ! R > be an increasing function with (k) = O(log k) and let

Theorem 6 .

 6 Let T; : N ! R > be an increasing function with (n) = O(log log n). Assume that T(n) 6 m T(b) + 2 b T(m) + m b log b (b); (12) for all sufficiently large n, where m = dexp (log n/e a log log n p )e b = dn/me.

Remark 9 .

 9 Since M A (k)/k = O(log k log log k) and k = O(log n), the result follows. As long as log n = O(log p), then M A (k)/k = O(1) in (

S

  p (n) 6 n r S p (r) + S p r l n r m + O(n log p); where S p (n) stands for the cost of semi-relaxed multiplication of two p-adic numbers in Z p up to order O(p n ). By [4, Proposition 4], we have S p (r) = O(I(r (log p + log r)) log r) = O(r log n (log n + log p) `log `).

  /(P ). Using a randomized algorithm, such a polynomial can be computed in time O ˜(k 2 log p); see [15, Corollary 14.44]. If k = O(log n), then this is really a precomputation of negligible cost O ˜(log 2 n log p).If we insist on computing P in a deterministic way, then one may use[START_REF] Shoup | New algorithms for nding irreducible polynomials over nite elds[END_REF] Theorem 3.2], which provides us with an algorithm of time complexity O ˜( p p k 4+" ).

* . This work has been partly supported by the French ANR-09-JCJC-0098-01 MaGiX project, and by the Digiteo 2009-36HD grant of the Région Ile-de-France.

Now let q be an element in F p k of order p k ¡ 1. Then any lift q ˜2 (Z/s Z)[z]/ ¡ P ˜ of q with (q ˜) = q has order at least p k ¡ 1. Moreover, q ¡ 1; ...; q p k ¡2 ¡ 1 and q are all invertible. Consequently, q ˜¡ 1; ...; q ˜pk ¡2 ¡ 1 and q ˜do not lie in ker = (p), whence they are invertible as well. It follows that we may still apply multipoint evaluation and interpolation in A[z]/(P ˜) at the sequence 1; q ˜; ...; q ˜pk ¡2 , whence Theorem 8 generalizes to the present case.

Remark 12. For a fixed prime number p, we notice that the complexity bound is uniform in the following sense: there exists a constant K such that for all effective rings of characteristic p r with r 2 f1; 2; ...g, we have R A (n) 6 K R (n). Indeed, the choice of k only depends on n and p, and any operation in F p k or A[z]/(P ) in the case r = 1 corresponds to exactly one lifted operation in (Z/s Z)[z]/(P ˜) or A[z]/(P ˜) in the general case.

Remark 13. Similarly as in Remark 9, the hypothesis log n = O(log p) leads to the improved bound

This bound is uniform in a similar way as in Remark 12. Theorem 14. Let A be an effective ring of non-zero characteristic s. Then

Proof. We will prove the theorem by induction on the number of prime divisors of s. If s is a prime power, then we are done. So assume that s = s 1 s 2 , where s 1 and s 2 are relatively prime, and let k 1 ; k 2 2 Z be such that

Then we may consider the rings

These rings are effective, when representing their elements by elements of A and transporting the operations from A. Of course, the representation of an element x of A 1 (or A 2 ) is not unique, since we may replace it by x + y for any y 2 s 1 A (or y 2 s 2 A). But this is not a problem, since our definition of effective ring did not require unique representability or the existence of an equality test.

By the induction hypotheses, we may compute h 1 and h 2 at order n using

] can still be expanded up to order n with the same complexity. We claim that h = f g. Indeed,

Summing both relations, our claim follows.

Remark 15.

A uniform bound interms of s can be given along similar lines as in Remark 12. This time, such a bound depends linearly on the number of prime factors of s.

Relaxed multiplication of p-adic numbers

Let p > 1 be an integer, not necessarily a prime number, and denote N p = f0; ...; p ¡ 1g. We will regard p-adic numbers a 2 Z p as series a 0 + a 1 p + a 2 p 2 + with a i 2 N p , and such that the basic ring operations +, ¡ and require an additional carry treatment.

In order to multiply two relaxed p-adic numbers a; b 2 Z p , we may rewrite them as series a ˆ; b ˆ2 Z[[z]], multiply these series c ˆ= a ˆbˆ, and recover the product c 2 Z p from the result. Of course, the coefficients of c ˆmay exceed p, so some relaxed carry handling is required in order to recover c from c ˆ. We refer to [4, Section 2.7] for details. In particular, we prove there that c can be computed up to order

Given k > 0, let Z k = fi 2 Z: jij < 2 k ¡1 g, and consider two power series f ; g 2 Z k [[z]]. We will denote by R Z (n; k) (resp. S Z (n; k)) the bit complexity of multiplying f and g up to order O(z n ) using a relaxed (resp. semirelaxed) algorithm.

Lemma 16. We have

Proof. Let be a prime number with log log n. Such a prime can be computed in time O(n) using the polynomial time polynomial primality test from [START_REF] Agrawal | PRIMES is in P[END_REF], together with the Bertrand-Chebychev theorem.

Let

be the reductions of f ; g modulo r . Then f g may be reconstructed up to order O(z n ) from the product f ˆg ˆ. We thus get

By Theorem 11 and Remarks 12 and 13, while using the fact that log n = O(log ), we have

and this bound is uniform in r. Since r n 2 2k , the result follows.

For the above strategy to be efficient, it is important that log n = O(k). This can be achieved by combining it with the technique of p-adic blocking. More precisely, given a p-adic block size b > 1, then any p-adic number in Z p can naturally be considered as a p b -adic number in Z p b, and vice versa . Assuming that numbers in N p are written in base 2, the conversion is trivial if p is a power of two. Otherwise, the conversion involves base conversions and we refer to [4, Section 4] for more details. In particular, the conversions in both directions up to order O(p n ) can be done in time O


Charles-Alban Deledalle

Florence Tupin

Loïc Denis

PATCH SIMILARITY UNDER NON GAUSSIAN NOISE

Keywords: Patch similarity, Likelihood ratio, Bayesian approach, Detection, Matching

Many tasks in computer vision require to match image parts. While higher-level methods consider image features such as edges or robust descriptors, low-level approaches compare groups of pixels (patches) and provide dense matching. Patch similarity is a key ingredient to many techniques for image registration, stereo-vision, change detection or denoising. A fundamental difficulty when comparing two patches from "real" data is to decide whether the differences should be ascribed to noise or intrinsic dissimilarity. Gaussian noise assumption leads to the classical definition of patch similarity based on the squared intensity differences. When the noise departs from the Gaussian distribution, several similarity criteria have been proposed in the literature. We review seven of those criteria taken from the fields of image processing, detection theory and machine learning. We discuss their theoretical grounding and provide a numerical comparison of their performance under Gamma and Poisson noises.

INTRODUCTION

The similarity or dissimilarity between pixel values has been defined in many different ways, depending on the problem at hand (stereo-vision, registration, denoising, . . . ), the noise model and the prior knowledge. We focus in the following on how to compare noisy values, and how similarity criteria can be derived from a given noise distribution. The comparison of noise-free patches and the similarity between a noise-free and a noisy patch (template matching) are out of the scope of the paper.

By x we denote a patch, i.e., a collection of N observations (pixel values). We do not specify here a shape for the patch but consider that the values in vector x are ordered so that when two patches x 1 and x 2 are compared, values with identical index are in correspondence.

We assume that the noise can be modeled by a (known) distribution so that a noisy patch x is a realization of an Ndimensional random variable X. The vector of parameters θ of the pdf is referred in the following as the noise-free patch. We will consider in our experiments white noise, i.e., p(x; θ) = N k=1 p(x k ; θ k ), even if the definitions of all criteria are general enough to deal with correlated noise.

Patch similarity: a pair of (noisy) patches (x 1 , x 2 ) is considered similar (i.e., in-match) when x 1 and x 2 are realizations of independent random variables X 1 and X 2 following the same distribution (of pdf p(.; θ 12 )). The evaluation of the similarity between noisy patches can then be rephrased as the following hypothesis test (a parameter test):

H 0 : θ 1 = θ 2 ≡ θ 12 (null hypothesis), (1)
H 1 : θ 1 = θ 2 (alternative hypothesis). (2)
For a given similarity criterion c, the probability of false alarm (to decide H 1 under H 0 ) and the probability of detection (to decide H 1 under H 1 ) are defined as:

P F A = P(c(X 1 , X 2 ) < τ ; θ 12 , H 0 ), (3)
P D = P(c(X 1 , X 2 ) < τ ; θ 1 , θ 2 , H 1 ). (4)
Note that the inequality symbols are reversed compared to usual definitions since we consider detection of dissimilarities based on the similarity measure c.

According to Neyman-Pearson theorem, the optimal criterion, i.e., the criterion which maximizes P D for any given P F A , is the likelihood ratio (LR) test:

L(x 1 , x 2 ) = p(x 1 , x 2 ; θ 12 , H 0 ) p(x 1 , x 2 ; θ 1 , θ 2 , H 1 ) . ( 5
)
The application of the likelihood ratio test requires the knowledge of the parameters θ 1 , θ 2 and θ 12 (the noise-free patches) which, of course, are unavailable. Our problem is thus a composite hypothesis problem. A criterion maximizing P D for all P F A and all values of the unknown parameters is said uniformly most powerful (UMP). [START_REF] Kendall | The advanced theory of statistics[END_REF] showed that no UMP detector exist in general for our composite hypothesis problem [START_REF] Kendall | The advanced theory of statistics[END_REF], so that any criteria can be defeated by another one at a specific P F A . The research of a universal similarity criterion is then futile. We address in the following the question of how different criteria behave on patches extracted from natural images.

PATCH SIMILARITY CRITERIA

Euclidean distance

The usual way to define the similarity between two noisy patches is to consider their Euclidean distance. The use of an exponential kernel of bandwidth h > 0 leads to the following similarity criterion:

N (x 1 , x 2 ) = exp - x 1 -x 2 2 2 h . (6)
The Mahalanobis distance can be used instead if noise is correlated. As we shall see later, under the assumption of Gaussian noise, all the similarity criteria we consider boil down to this same expression. There are then more than one way to justify or interpret its expression in that case. The advantage to use a metric is that it involves good properties such as the triangle inequality. Under Gaussian assumptions, the distribution of N can be used to choose a threshold τ with a given P F A value. It is a constant false alarm rate detector (CFAR), which means that a constant P F A can be maintained with a same τ whatever the underlying noise-free patches. The performance of this criterion however falls when the noise departs from Gaussian distribution. While h can be set from the noise variance, difficulties arise when the noise variance is signal-dependent, and then can vary between and inside patches. A classical approach to extend the applicability of Euclidean distance to non-Gaussian noises is to apply a transformation to the noisy patches. The transformation is chosen so that the transformed patches follow a (close to) Gaussian distribution with constant variance (hence their name: variance-stabilization transforms). This leads for instance to the homomorphic approach which maps multiplicative noise to additive noise with stationary variance. This is also the principle of Anscombe transform and its variants used for Poisson noise. These approaches are popular and frequently used for patch selection (or block-matching) in many denoising algorithms [START_REF] Mäkitalo | Denoising of single-look SAR images based on variance stabilization and nonlocal filters[END_REF][START_REF] Mäkitalo | On the inversion of the Anscombe transformation in low-count Poisson image denoising[END_REF][START_REF] Boulanger | Patch-based nonlocal functional for denoising fluorescence microscopy image sequences[END_REF]. Given an application s which stabilizes the variance for a specific noise pdf, a similarity criterion is obtained using (6) on the output of s:

S(x 1 , x 2 ) = N (s(x 1 ), s(x 2 )). (7)
Besides the problem of the existence of a suitable s for some noise distributions, an important limitation lies in the nonlinear distortion of noise-free patches. For instance, in the homomorphic approach, the logarithm transforms the contrast of noise-free patches; performances are affected accordingly.

Likelihood ratio extensions

Motivated by optimality guarantees of the LR test (5), similarity criteria can be defined from statistical detectors designed for composite hypothesis problems. The similarity criterion in eq. ( 8) is based on the Bayesian likelihood ratio (BLR)

L B (x 1 , x 2 ) = p(x 1 , x 2 ; H 0 ) p(x 1 , x 2 ; H 1 ) = p(x 1 |θ 12 = t)p(x 2 |θ 12 = t)p(θ 12 = t) dt p(x 1 |θ 1 = t 1 )p(θ 1 = t 1 )dt 1 p(x 2 |θ 2 = t 2 )p(θ 2 = t 2 )dt 2 . ( 8
)
which considers noise-free patches as realizations of random vectors with known prior pdf. Given perfect knowledge of prior pdf p(θ 1 ), p(θ 2 ) and p(θ 12 ), eq. ( 8) leads to an optimal Neyman-Pearson detector. This criterion has been used in the context of classification: Minka [START_REF] Minka | Distance measures as prior probabilities[END_REF] exhibits a relationship between BLR and the canonical distance measure minimizing errors in nearest neighborhood classifiers. He also linked BLR to mutual information: the more additional knowledge is brought by x 2 compared to the observation of x 1 alone, the more dissimilar the underlying parameters are [START_REF] Minka | Bayesian Inference, Entropy, and the Multinomial Distribution[END_REF]. Despite its theoretical performance, this approach suffers from two drawbacks in practice. First, it requires computation of integrals which, depending on the distributions, may not be known in closed form and therefore are time-consuming. Second, it requires knowledge of the prior pdf. In the absence of a statistical model of noise-free patches, a non-informative prior can be used. Jeffreys' prior is independent upon the choice of the noise-free patch space (e.g., testing that two gamma random vectors share identical standard deviations θ 12,k = σ k or identical variances θ 12,k = σ 2 k leads to the same BLR when Jeffreys' prior are used).

Rather than modeling noise-free patches as random variables, the generalized LR (GLR) replaces θ 1 , θ 2 and θ 12 in eq. ( 5) by their maximum likelihood estimates (MLE) under each hypothesis:

L G (x 1 , x 2 ) = sup t p(x 1 , x 2 ; θ 12 = t, H 0 ) sup t 1 ,t2 p(x 1 , x 2 ; θ 1 = t 1 , θ 2 = t 2 , H 1 ) = p(x 1 ; θ 1 = t12 )p(x 2 ; θ 2 = t12 ) p(x 1 ; θ 1 = t1 )p(x 2 ; θ 2 = t2 ) (9)
Asymptotically to the SNR, GLR is optimal due to the efficiency of MLE. Its asymptotic distribution is known and then the P F A values associated to any given threshold τ : GLR is asymptotically CFAR. The GLR test is also invariant [START_REF] Kay | An invariance property of the generalized likelihood ratio test[END_REF]: it does not depend on the arbitrary choice of the noisy patch space (e.g. considering an observed patch of amplitudes

x = (A 1 , • • • , A N ) or intensities x = (A 2 1 , • • • , A 2
N ) lead to the same criterion). While we mention that there is no UMP detectors for our composite hypothesis problem, GLR is asymptotically UMP among invariant tests [START_REF] Lehmann | Optimum invariant tests[END_REF]. Finally, compared to BLR, GLR is easy to implement, since it only requires to computes MLE, and does not require any prior knowledge.

The main drawback of GLR lies in the lack of knowledge on how it behaves in low SNR conditions (i.e., for too small patches according to the noise level). It is known that, for low SNR and specific applications, GLR can be defeated by other invariant detectors [START_REF] Kim | Comparison of GLR and invariant detectors under structured clutter covariance[END_REF]. This drawback lies in its dependency on MLE which behaves poorly for low SNR (e.g. the GLR that two Gaussian random vectors share an identical covariance matrix θ 12 is undefined since MLE of θ 1 from x 1 only would not be positive definite).

Joint likelihood criteria

Other criteria use the joint likelihood of observations under H 0 to evaluate similarities between noisy data. This leads to the Bayesian joint likelihood criteria [START_REF] Yianilos | Metric learning via normal mixtures[END_REF][START_REF] Seeger | Covariance kernels from Bayesian generative models[END_REF][START_REF] Matsushita | A Probabilistic Intensity Similarity Measure based on Noise Distributions[END_REF][START_REF] Deledalle | Iterative Weighted Maximum Likelihood Denoising with Probabilistic Patch-Based Weights[END_REF]:

Q B (x 1 , x 2 ) = p(x 1 , x 2 ; H 0 ) = p(x 1 |θ 1 = t)p(x 2 |θ 2 = t)p(θ 12 = t) dt ( 10
)
or, following the simplification of GLR, the maximum joint likelihood [START_REF] Alter | An intensity similarity measure in low-light conditions[END_REF]:

Q G (x 1 , x 2 ) = sup t p(x 1 , x 2 ; θ 12 = t, H 0 ) = p(x 1 ; θ 1 = t12 )p(x 2 ; θ 2 = t12 ). ( 11
)
Such criteria have been designed to measure the probability of sharing a common parameter. However, they evaluate instead the joint likelihood pdf under H 0 which cannot provide information without knowledge under H 1 . This leads to noninvariance issues and the self recognition paradox [START_REF] Yianilos | Metric learning via normal mixtures[END_REF]: two different noisy patches x 1 , x 2 can be more similar than two identical noisy patches (x 1 = x 1 ). However, Q B offers a useful property: it corresponds to an inner product [START_REF] Seeger | Covariance kernels from Bayesian generative models[END_REF] in the space of functions θ → R, the feature of x being (p(x|θ = t)) t . The "mutual information" kernel is based on this property.

Mutual information kernel

Given the Bayesian joint distribution Q B (x 1 , x 2 ), Seeger [START_REF] Seeger | Covariance kernels from Bayesian generative models[END_REF] defines a covariance kernel linked to the sample mutual information between x 1 and x 2 and defined as:

K B (x 1 , x 2 ) = Q B (x 1 , x 2 ) Q B (x 1 , x 1 )Q B (x 2 , x 2 ) . (12)
Since Q B can be seen as an inner product in the feature space, K B corresponds to a cosine in the feature space

K B (x 1 , x 2 ) = x 1 , x 2 x 1 x 2 .
Seeger shows that it is a kernel covariance matrix and coins it the mutual information kernel. Algorithms can be adapted to the noise pdf using the socalled kernel tricks, i.e., by considering higher dimensional space while never mapping the data in practice. This leads for instance to non-linear support vector machines or non-linear principal component analysis. The mutual information kernel is also invariant. Note also that its prior-less extension using MLE would lead to GLR. Compared to GLR, the main limitation of the mutual information kernel is its dependency on the prior pdf and the lack of asymptotic performance results.

EVALUATION OF SIMILARITY CRITERIA

We evaluate the relative performances of the 7 aforementioned criteria on a dictionary composed of 196 noise-free patches of size N = 8×8. The noise-free patches are obtained using the k-means on patches extracted from the classical 512 × 512 Barbara image. The noisy patches are noisy realizations of the noise-free patches under gamma or Poisson noise with an overall SNR of about 1 dB. All criteria have been derived1 in the case of gamma or Poisson noise (table 1). They are evaluated for all pairs of noisy patches. The process is repeated 200 times with independent noise realizations.

In practice, Bayesian criteria are more difficult to obtain due to integrations over the noise-free patch space. While all criteria are equivalent for Gaussian noise, there are four different expressions for gamma noise and they are all different for Poisson noise. The distinction seems to emerge with the "complexity" induced by the noise distribution, (by considering that gamma noise is more challenging than Gaussian noise, and that Poisson noise is the most challenging).

Numerically, the performances of the similarity criteria are given in term of their receiver operating characteristic (ROC) curve, i.e., the curve of P D with respect to P F A . Results are given in Figure 1. For small P F A , GLR is the most powerful followed by the mutual information kernel, BLR and the variance stabilization criteria. Other criteria behave poorly for such a low SNR. Such behaviors agree with the theoretical predictions. The poor performances of the joint likelihood based criteria can arise from their non-invariance and the induced self-similarity paradox. The low performance of N is certainly due to its non-adaptivity to either the target noise or the target noise variance. The variance stabilization criteria are always defeated by GLR, due to the distortions of the noise-free patches as well as the consideration of the noise variance only, instead of the full noise pdf. The lower performance of Bayesian criteria compared to criteria that use MLE may be due to the low quality of the prior pdf.

CONCLUSION

This paper compares seven similarity criteria designed for noisy data and used in different communities. It has been shown that on 8×8 patches extracted from a natural image and under a high level of gamma or Poisson noise, the GLR detector is the most powerful on low levels of false alarms. It is also easy to implement and theoretically well grounded. Based on this study, we would recommend a broader use of this criterion for measuring patch similarity in computer vision. Future work would be to provide comparisons on smaller patches where GLR is known to behave poorly. We also plan to study the impact of the choice of a similarity criterion on the performance of tasks such as stereo-matching or denoising.

name pdf Q B Q G L B L G K B S N Gaussian e -(x-θ) 2 2σ 2 √ 2πσ e -(x1-x2) 2 Gamma L L x L-1 e -Lx θ Γ(L)θ L 1 x1x2 x1x2 (x1+x2) 2 L x1x2 (x1+x2)

2

 2

2 Table 1 .Fig. 1 .

 211 Fig. 1. (left) Patch dictionary. (center) ROC curve obtained under gamma noise and (right) ROC curve obtained under Poisson noise. In both experiments, the SNR over the whole dictionary is about 1 dB.

the complete derivations are available in http://perso. telecom-paristech.fr/ ˜deledall/patchsim.php


Pierre Maurel

Yann Bertacchini

CONCEPTION, REPRESENTATION & MEDIATION IN PARTICIPATORY LAND PLANNING PROJECTS: 3D PHYSICAL MODELS ARTEFACTS

INTRODUCTION

The concept of sustainable development and its related principles, in particular public participation, changed dramatically in France the way of developing and implementing public policies for spatial planning. It progressively shifted from sectorial, technical and centralized approaches to more holistic, participatory and deliberative approaches. Individual citizens and social groups in interaction are becoming more numerous and diversified, as well as the habitus and social representations. Thus, getting mutual understanding and a share vision of the territory becomes longer and more complex. In this context, the informational and communicational dimension of these widened socio-technical processes turns to play a central role [START_REF] Bertacchini | De l'intelligence territoriale. Théorie, Posture, Hypothèses, Définitions[END_REF]. The emergence of a process of territorial intelligence requires more fluent exchanges of information between the participants and greater confidence in the information exchanged. To face such a challenge, one of the possible solutions is to introduce mediating objects [START_REF] Vinck | Dynamique d'innovation et de conception et rôle des objets intermédiaires[END_REF] able to help formulating and making understandable by other participants different perspectives and kinds of knowledge available among the actors network. But the introduction of innovations in normative territorial planning processes is already in itself a challenge.

Relying on the Diffusion of Innovations (DoI) Theory [START_REF] Rogers | Diffusion of innovations[END_REF] and an Information and Communication Tools (IC-tools) uses theory [START_REF] Proulx | Penser les usages des technologies de l'information et de la communication aujourd'hui : enjeux -modèles -tendances[END_REF], this paper aims to focus on the 3D physical models that have been used to support a participatory land planning project for the Thau territory. This paper will describe how this innovation has been introduced into the territorial intelligence process, the making process itself and the characteristics of the models, the uses initially planned as well as the observed uses and effects (cognitive, procedural, relational, local capacities).

CASE STUDY APPLICATION : A TERRITORIAL INTELLIGENCE PROCESS IN ACTION

An experiment has been launched in the framework of an operational research study integrated in the participatory spatial planning process of the Thau territory. This territory is situated in the Hérault department in the south of France, near the city of Montpellier, the regional capital. To reinforce integrated coastal zone management [START_REF] Vallega | Fundamentals of integrated Coastal Management[END_REF], the local authorities have decided in 2005 to implement simultaneously two new planning tools, a SCOT (territorial dimension) and a SAGE (water dimension). These public policies instruments are driven by the Syndicat Mixte du Bassin de Thau (SMBT) which acts on behalf of the two intercommunal cooperation structures (EPCI) that represent all the municipalities of the territory. In order to anticipate the implementation of the SAGE and the SCOT instruments, the SMBT is also encouraging local stakeholders to translate sustainability principles into action in their professional practices. For instance, the Villeveyrac council situated in the northern part of the Thau territory has decided in 2007 to develop a local agenda 21 in order to reinforce its rural identity in a peri-urban context. A detailed description of the Thau territory, it's governance system and the participatory process has already been presented [START_REF] Maurel | Apprentissage collectif pour décider de l'avenir du territoire de Thau : premiers retours d'une approche combinant politique publique et participation[END_REF]. To support this approach, different animation and facilitation methods combined with several information and communication tools have been used or are still under development (Maurel and Roussillon, 2007). Some of these tools, based on Internet technologies, are particularly sophisticated. Others remain extremely "rudimentary" from a technical perspective but are equally useful and effective in the emergence of a process of territorial intelligence. We will focus in this paper on one of these "rudimentary" tools, the 3D physical scale model.

THE 3D PHYSICAL SCALE-MODEL AS COMMUNICATIONAL ARTEFACT: TOWARDS A REVIVAL ?

A comparative analysis of various spatial representations shown that 3D physical scale-models were presenting intrinsic properties suitable for synchronous, face to face and bidirectional communicational processes and were not requiring heavy decoding tasks [START_REF] Maurel | Les représentations spatiales : concepts de base et éléments de typologie[END_REF]. 3D models turn out to be very powerful and user-friendly communication tools. They can support a variety of collaborative processes that are extremely interactive (free expression of local knowledge, results communication, scenario building, etc.) and multi-sensory (vision, hearing, sense of touch). That kind of artefacts has been widely used in the past centuries, in particular by military to prepare the defence or the siege of strategic sites [START_REF] Warmoes | Le musée des plans-reliefs[END_REF]. It is currently also used in developing countries to support participatory development projects with local people. Very detailed methodologies are now available to make and to use such models [START_REF] Rambaldi | Participatory 3-Dimensional Modelling: guiding principles and applications[END_REF]. There is, however, in France at this time a clear preference for the use of digital or virtual representations. Physical 3D scale-models are rarely used, except for urban or large infrastructures planning projects, but more as marketing tools than for participatory design. To date, four different scale-models have already been manufactured. These models have been used during different events (SCOT technical group workshops and public meetings, educative sessions) with various audiences (elected officials, professional representatives, NGOs, public at large, schoolboys). Their main characteristics are described in the following The following timeline provides an overview of the different phases as well as the concerned actors for the design, the making and different uses of these four 3D scale-models. If we analyse the diffusion process from the Diffusion of Innovations theory, Rogers distinguishes five stages through which an innovation passes: knowledge, persuasion, decision, implementation and confirmation [START_REF] Rogers | Diffusion of innovations[END_REF].

DIFFUSION OF 3D PHYSICAL SCALE-MODELS IN THE THAU TERRITORY PLANNING PROCESS

Knowledge phase: In our particular case, three actors were knowing the potential of 3D scale-models and understanding their functions. They played the role of change agents defined by Rogers. These agents were: 1-A local NGO leader who was already using basic 3D models for educational purposes in the Thau territory. 2-Another NGO, situated closed to the Thau territory, familiar with the use of 3D objects to raise public awareness of urban planning challenges. 3-The Cemagref researcher involved in the design of the Thau participatory process, who was aware of the experiences carried out in developing countries [START_REF] Rambaldi | Participatory 3-Dimensional Modelling: guiding principles and applications[END_REF] and who recently investigated spatial representations properties.

Persuasion and decision phase:

The SMBT technical agents in charge of the planning project were already favourable to innovative approaches, including public participation, and used to deal with geographical reasoning. Their clearly played the role of initial change aides defined by Rogers as the ones who complement the change agents, by having more intensive contacts and more trustworthiness credibility with decision makers (here, the group of mayors involved in the SCOT process). The SMBT facilitated preliminary meeting between the NGOs and the Cemagref researcher and convinced the mayors about the interest of making 3D scale-models.

The three initial technical actors worked together to prepare a proposal for a national call for tender in the field of participatory land management in order to get additional funding. The first proposal was rejected for administrative reasons but the second one submitted in 2008 was successfully accepted.

Implementation phase: These three initial actors then cooperated for the design and the making of the models 1 and 2. These two models have been used in 2007 for several events related to the SCOT process (mayors seminar, a two month open house exhibition and a serie of educational activities). The uses of the models during the open house exhibition are detailed later in this paper.

Confirmation phase:

Positive feedbacks from these first uses allowed then to pass through the "confirmation" stage described by Rogers, which corresponds to a reinforcement of the innovation in the social system. Several new actors asked for using these models or for producing new ones for their own activities. For instance, the representatives of Villeveyrac district in the SCOT process appreciated the two first 3D models and decided to contract with the NGOs already mentioned to make another 3D model covering the Villeveyrac district area. This new model will be used to support participatory activities related to the implementation of the local Agenda 21. It has already been displayed in 2008 during three popular events, raising the visibility of the Villeveyrac council initiative towards sustainable development. The SMBT and the local NGO are also benefiting from this visibility.

The local NGO also produced a 3 rd scale model of a generic river basin with the technical assistance of the Cemagref researcher. To date, this model has been mainly used for several educational activities with local schools to raise awareness in the field of river basin and water management. The SMBT agent responsible for the SAGE process also played the role of change aides for the diffusion of this 3D model since he is very favourable for cooperating locally with the educational system.

3D SCALE-MODELS MAKING PROCESS SEEN AS A SOCIO-TECHNICAL PROCESS

The design of technical objects is in itself a dynamic socio-technical process in which designers, users and environment interact. Then, cultural norms and conventions that have been incorporated into objects work up to guide their uses (Akrich, 1987). For example, the partners of the first Thau scale-models have contributed with their own ideas, skills and values to co-design these artefacts. From a technical point of view, the making process has been adapted compared to the one described in the manual already mentioned [START_REF] Rambaldi | Participatory 3-Dimensional Modelling: guiding principles and applications[END_REF]: Cork material was preferred to corrugated carton board for ecological considerations, contour lines were directly displayed with a video projector at the right scale on the cork sheets instead of using carbon paper, scale-models were made by local NGOs and a researcher instead of inhabitants for socio-cultural reasons.

According to [START_REF] Proulx | Penser les usages des technologies de l'information et de la communication aujourd'hui : enjeux -modèles -tendances[END_REF], designers base their activity on the representations that they have of the virtual users and they translate them into affordances. For instance, in our case, it was considered as fundamental to create an artefact that will encourage the targeted users to think and reason at an inter-district level because they were seen as people who used to think very locally. For that reason, the two first 3D scale-models have been designed to cover the whole Thau territory and the individual districts limits have not been represented on the models.

According to the same author, values, moral and political dimensions are also incorporated into the technical objects. In the Thau case study, the innovators were sharing the same values concerning the way of carrying out territorial projects: vision and choices driven by the sustainable development principles, bottom up approach, linking traditional decision and participatory methods involving all stakeholders and ordinary citizens, transparent access to understandable information, mixing expert and local/tacit knowledge, involving the youngest through educational activities, avoiding digital divide between connected people and the others. Within the range of tools used in the Thau planning project, the choice of "rudimentary" 3D scale-models rather than high-tech digital and dynamic 3D representations of the territory were definitively driven by these values. The same reasons influenced the design of accessories and socio-technical environments of the 3D scale-models. For instance, the 3D models were not placed under a plexiglas protective device but were kept opened and completed by symbolic and movable items for interactive exercises. Another example concerns semiologic choices to represent phenomena on the 3D models. Thau territory is subject to intense demographic pressures leading to rapid urban sprawl and these phenomena are perceived from very different perspectives. If they are seen as positive by some elected people or groups of interest, the designers of the 3D models considered them as dramatic for ecological and social reasons. They decided to represent urban areas in black, as an oil slick, in order to reinforce the negative dimension of urban sprawl phenomenon and to focus participants' attention on it. They also used the red color (associated to "danger" in our society) to produce an interactive map of urban sprawl dynamics between 1944 and 2020 that was displayed on the vertical white 3D model (model n°1) and which really caught the attention of participants.

ANALYSIS OF SOME USES OF THE 3D SCALE-MODELS

We have chosen to detail here how the 2nd scale-model has been used during the touring open-house event designed to present the SCOT diagnosis to the general public from August to October 2007. The two-month exhibition was presented in 7 of the 14 municipalities in the Thau territory, and lasted one or two weeks including the week-end at each location. Each event was preceded by a public meeting chaired by the local mayors assisted by the SCOT project manager. Next, SMBT technicians successively "facilitated" the open house event. A staff member of the NGO that had made the models organized several visits by schoolchildren. A total of 1 300 people attended the public meetings and the exhibition.

Here is a brief description of the informational and communicational support system that has been imagined by the SMBT and the local NGO to present the results of the SCOT diagnosis.

The exhibition itself included 25 posters organised around 6 topics, an interactive map of urban sprawl dynamics between 1944 and 2020 displayed on a vertical white 3D model (model n°1), a urban planner game to lay out a new plot, a GIS on a laptop to display SMBT geographic data upon request, and at least one interactive exercise with the 2nd 3D scale-model (see below a description of this exercise).

Main land use features were already painted on the 3D model: towns, main roads and main rivers, lagoons and the sea, the SCOT and the watershed limits. Small coloured items were also produced to represent several individual real life places or activities such as lodging, work place, shopping centres, sporting and cultural facilities and different means of transport (car, bus, etc.). Visitors to the exhibition were asked to pinpoint these items on the 3D model in order to represent their footprint on the territory in terms of housing, transportation, shopping and leisure (figure 4). Direct observations made during the exhibition and interviews with the facilitators revealed different uses and effects of this 3D model. Some of these findings were expected by those who produced the 3D models, some other uses emerged during the interactions between the facilitators, the visitors and the physical artefacts of the exhibition. We now present six uses of the models that correspond to our main findings.

-Cognitive use: for most of the visitors, Thau territory still was a blurry concept they had heard about through the local media or by listening to the technicians and mayors speeches. The 3D models enabled them to acquire a more accurate representation of the territory, both its natural (perimeter, relief, land use, hydrography) and human dimensions (towns, roads).

-Second cognitive use: the interactive exercise that consisted in positioning small coloured items on the 3D models helped the visitors to link their real-life spaces (mainly made up of local places and transportation axes) with the much wider Thau territory. This exercise also enabled them to visualize their footprint on the territory. The accumulation of coloured items pinpointed by previous visitors helped them discover the diversity of reallife spaces and their cumulative effects in terms of housing, transportation and services. A real learning process was going on in their minds: Thau territory not only started to exist, but they also were deeply embedded in it.

-Third cognitive use: Several authors have already that technical objects with a representational function could act as partners in the cognitive activity of those who used them [START_REF] Norman | Les artefacts cognitifs[END_REF][START_REF] Millerand | La dimension cognitive de l'appropriation des artefacts communicationnels[END_REF]. They can alleviate the cognitive tasks of attention, reasoning, memory insofar as they take over a part of human cognitive activity. They can also replace different cognitive tasks (involving representations and manipulation of symbols) by a direct perception [START_REF] Quéré | La situation toujours négligée ?[END_REF]). In our case, the 3D scale-models clearly played this role by supporting during the SCOT diagnosis exhibition the process of communication between agents with different frames of reference (i.e. mainly between the SMBT technicians and visitors). By presenting the physical space of the Thau territory, the 3D scale-models were offering visual grasp points in the discourse and gestures of the other person to better locate places and understand territorial phenomena that were verbally expressed.

-Relational use: when the 3D model was used at the beginning of the visit, it helped to establish contact between the facilitator and the visitor. During the positioning exercise, the hitherto anonymous visitor revealed to the facilitator his daily life spaces, his practices and his preferences, allowing an interpersonal discussion to start, which helped to create an atmosphere of confidence for the rest of the visit.

-Procedural use, this use derived from the previous one: the interaction mediated by the 3D model enabled the facilitator and the visitor to start a discussion about several territorial issues (housing, urban sprawl, employment, traffic jams, sport and cultural facilities, environmental impacts, etc.). In this case, the 3D model was used by the facilitator to direct the visitor to the exhibition panels for an in-depth discussion about these important issues.

-Last use, which can be qualified as indirect or secondary, was related to the relational capital of the Thau territory. Indeed, several people from different institutions developed a strong partnership to carry out this project based on 3D models. They worked together as a real team to improve the initial idea, to find technical and procedural ways to make the models themselves, to design interactive exercises and finally, to put all these innovations into practice during the exhibition. These activities enabled a relational network based on trust, reciprocity and specific innovative skills to be extended and strengthened. This latent richness could be reactivated later for the benefit of the territory.

DISCUSSION

This paper aimed to describe how the 3D scale-models innovation was introduced into the Thau territorial intelligence process, the making process itself and the characteristics of the models, the uses initially planned as well as the observed uses and effects.

Results shown that the diffusion process of the 3D scale-models was respecting the Diffusion of Innovation Theory proposed by Rogers.

One of the most interesting conclusions to date is that 3D scale-models communicational artefact can definitively help to connect technical representations of the territory with real-life places as perceived by the inhabitants, thus facilitating the dialogue between spatial planners and ordinary citizens. They also helped to strengthen trust between technical staff from the leading institution, local NGOs and the public at large. All these aspects have positive effects on the emergence of a territorial intelligence process.

Numerous studies have shown that even if designers strongly guided uses of communicational artefacts, there could be from users gestures of diversion of these uses originally planned, or even totally new uses [START_REF] Millerand | La dimension cognitive de l'appropriation des artefacts communicationnels[END_REF]. In our case, results to date indicate that the observed uses of the 3D scale-models were widely anticipated by the designers, and predetermined through their design itself, their immediate surrounding environment and the instructions of use proposed by the designers or the facilitators. However, some uses originally planned have not been observed yet, especially those imagined to facilitate technical or political meetings of traditional decision makers (mayors, government and local authorities technical staff, stakeholders representatives).

During the next stage of the SCOT and SAGE processes, we believe that the 3D scale-models could facilitate the dialogue concerning the territorial political project supported by elected officials. Depending on the intensity of use of these models, they might turn to become widely shared symbolic representations of the Thau territory. All that contributes to a process of gradual emergence of territorial ownership.

Figure 1 :

 1 Figure 1: Location of the Thau territory.

  Several actors have contributed to introduce 3D physical scale-models in the participatory planning process of the Thau territory and other related activities (fig 2).

Figure 2 :

 2 Figure 2: Actors network involved in the 3D scale-models innovation process.

  Type of actor: (1) Local authority, (2) Foundation, (3) NGO, (4) Private Cie, (5) Research, (6) Education Role in the process: Fu: Funding, D: Design, M: Making, F: Facilitation, U: Use, A: Assessment

Figure 3 :

 3 Figure 3: Timeline describing the 3D scale-models development process 1: SMBT 2: Cemagref 3: NGO (Galapians, CPIE, Mediaqua) 4: NGO Manufacture des Paysages 6: Mayors 7: Local stakeholders 8: Villeveyrac council 9: Education (scholar students, teachers) 10: Public at large -----Preliminary phases

Figure 4 :

 4 Figure 4: Use of the 3D scale-model in the open-house exhibition for the SCOT diagnosis

Table 1 :

 1 table. Main characteristics of the 3D scale-models.

	N°	Scale	Size (m)	Area	Layout	Accessories
	1	1:25 000 1,6 m x 0,8 Thau	White magnetic paint	-Vertical support
				territory
	2	1:25 000 1,6 m x 0,8 Thau	Coloured geographical features	-Coded small items for
				territory	(administrative limits, land use,	individual real life places
					roads, rivers)	and activities
	3	1:50 000 0,8 m x 0,5 Generic	Coloured land use areas	-Filling up bulb
				river basin		-Small coloured items for
						components of urban water
						system (aqueduc, tank,
						intake, treatment plant, …)
	4	1:5 000	1,6 m x 1,6 Villeveyrac	Coloured geographical features	Horizontal support
				district	(administrative limits, land use,	Transparent plastic sheet
					roads, rivers, irrigation network)	with land use