Thomas Batard

Michel Berthier

Clifford Fourier Transform and Spinor Representation of Images

Keywords: Mathematics Subject Classification (2010). Primary 68U10, 53C27; Secondary 53A05, 43A32. Keywords. Image Processing, Spin Geometry, Clifford Fourier Transform

come

Introduction

The idea of this paper is to perform grey-level image processing using the geometric information given by the Gauss map variations of image graphs. If it is well known that one can parametrize the Gauss map of a minimal surface by a meromorphic function (see below), it is a much more recent result (see [START_REF] Friedrich | On the spinor representation of surfaces in Euclidean 3-space[END_REF]) that such a parametrization can be extended to arbitrary surfaces of R 3 when dealing with spin geometry. Let us first recall that a minimal surface Σ immersed in R 3 , that is a surface with constant mean curvature equal to zero, can be described with one holomorphic function ϕ and one meromorphic function ψ such that the product ϕψ 2 is holomorphic. This is the so-called Weierstrass representation of Σ (see [START_REF] Lawson | Lectures on minimal manifolds[END_REF] or [START_REF] Osserman | A survey of minimal surfaces[END_REF] for details). The involved function ψ is nothing else but the composition of the Gauss map of Σ with the stereographic projection from the unit sphere to the complex plane. The main result of T. Friedrich in [START_REF] Friedrich | On the spinor representation of surfaces in Euclidean 3-space[END_REF] states that there is a one to one correspondance between spinor fields ϕ * of constant length on a Riemannian surface (Σ, g) and satisfying

Dϕ * = Hϕ * (1.1)
where D is a Dirac operator in one hand, and isometric immersions of Σ in R 3 with mean curvature equal to H, on the other hand. The Weierstrass representation appears to be the particular case corresponding to H ≡ 0. Let us describe now the method introduced in the following. Let

χ : Ω ⊂ R 2 -→ R 3 (x, y) -→ (x, y, I(x, y)) (1.2)
be the immersion in the 3-dimensional Euclidean space of a grey-level image I defined on a domain Ω of R 2 . The first step (see Sec. 2) consists in computing the spinor field ϕ * that describes the image surface Σ. We follow here the paper of T. Friedrich ([6]): ϕ * is obtained from the restriction to the surface Σ of a parallel spinor φ on R 3 . The computation of ϕ * necessitates to deal with irreducible representations of the complex Clifford algebra C 3,0 ⊗C and with the generalized Weierstrass representation of Σ based on period forms. In practice, ϕ * is given by a field of elements of C 2 . As said before, the spinor field ϕ * characterizes the geometry of the surface Σ immersed in R 3 by the parametrization (1.2). In the same way that the normal of a minimal surface is parametrized by the meromorphic function ψ, the normal of the surface Σ is parametrized by the spinor field ϕ * . This last one explains how the tangent plane to Σ varies in the ambient space.

There are many reasons to believe that such a generalized Weierstrass parametrization may reveal to be an efficient tool in the context of image processing.

1. The field ϕ * of elements of C 2 (see formula (2.26)) encodes the Riemannian structure of the surface Σ in a very tractable way (although the definition of ϕ * may appear quite complicated). 2. The geometrical methods based on the study of the so-called structure tensor involve only the eigenvalues of this one, that means in some sense the values of the first fundamental form of the surface. The spinor field ϕ * contains both intrinsic and extrinsic information. Studying the variations of ϕ * allows to get not only information about the variations (derivative) of the first fundamental form, but also about the geometric embedding of the surface Σ and in particular about the mean curvature. 3. We are dealing here with first order instead of zero order geometric variations of Σ. As shown later, this appears to be more relevant by taking into account both edges and textures. 4. As it will be detailed in the sequel, the spinor field ϕ * can be decomposed as a series of basic spinor fields using a suitable Clifford Fourier transform. This series corresponds to an harmonic decomposition of the surface Σ adapted to the Riemannian geometry. This is in fact the main novelty of this paper since usual Fourier analysis doesn't involve geometric data.

One can envisage to perform diffusion in this context. The usual Laplace

Beltrami operator can be replaced by the squared Atiyah Singer Dirac operator (the Atiyah Singer Dirac operator acting as an elliptic operator of order one on spinor fields).

To illustrate some of these ideas, we investigate rapidly in Sec. 3 applications to segmentation and more precisely to edge and texture detection. As said before, the basic idea is to replace the order 1 usual structure tensor by an order 2 structure tensor called spinor tensor obtained from the derivative of the spinor field ϕ * . This spinor tensor measures to the variations of the unit normal of the image surface. Experiments show that this approach is particularly well adapted to texture detection. We define in Sec. 4 the Clifford Fourier transform of a spinor field. For this, we follow the approach of [START_REF] Batard | Clifford Fourier Transform for Color Image Processing[END_REF] that relies on a spin generalization of the usual notion of group character. We are led to compute the group morphisms from Z/M Z × Z/N Z to Spin(3). Since this last group acts on the sections of the spinor bundle, a Clifford Fourier transform can be defined by averaging this action. One of the key ideas here is to split the spinor bundle of the surface according to the Clifford multiplication by the bivector coding the tangent plane to the surface. This has two advantages: the first one is to involve the geometry in the process, the second one is to reduce the computation of the Clifford Fourier transform to two usual complex Fourier transforms.

It is important to notice that although the Fourier transform we propose is as usual a global transformation on the image, the way it is computed takes into account local geometric data. We finally introduce the harmonic decomposition mentioned above and show results of filterings on standard images. The reader will find in the appendix the mathematical definitions and results used throughout the text.

Spinor Representation of Images

This section is devoted to the explicit computation of the spinor field ϕ * of a given surface immersed in the Euclidean space. It is obtained as the restriction of a constant spinor field of R 3 the components of which are determined using period forms.

Spinors and Graphs

Let I : Ω -→ R be a differentiable function defined on a domain Ω of R 2 . We consider the surface Σ immersed in R 3 by the parametrization:

χ(x, y) = (x, y, I(x, y)) (2.1)
Let also g be the metric on Σ induced by the Euclidean metric of R 3 . The couple (Σ, g) is a Riemannian surface of global chart (Ω, χ). We denote M the Riemannian manifold (R 3 , 2 ) and (z 1 , z 2 , ν) an orthonormal frame field of M with (z 1 , z 2 ) an orthonormal frame field on Σ and ν the global unit field normal to Σ. One can choose (z 1 , z 2 , ν) with the following matrix representation

               I x (I 2 x + I 2 y )(I 2 x + I 2 y + 1) -I y I 2 x + I 2 y -I x I 2 x + I 2 y + 1 I y (I 2 x + I 2 y )(I 2 x + I 2 y + 1)
I x I 2 x + I 2 y -I y I 2 x + I 2 y + 1 I 2 x + I 2 y (I 2 x + I 2 y )(I 2 x + I 2 y + 1) 0 1 I 2 x + I 2 y + 1                (2.2)
Note that z 2 is not defined when I x = I y = 0. This has no consequence in the sequel since we deal only with the normal ν.

Following [START_REF] Friedrich | On the spinor representation of surfaces in Euclidean 3-space[END_REF] the surface Σ can be represented by a spinor field ϕ * with constant length satisfying the Dirac equation:

Dϕ * = Hϕ * (2.3)
where H denotes the mean curvature of Σ. We recall here the basic idea (see Appendix A. for notations and definitions). Let φ be a parallel spinor field of M , i.e. satisfying ∇ M X φ = 0 (2.4) for all vector fields X on M . Let also ϕ be the restriction φ |Σ of φ to Σ. The spinor field ϕ decomposes into

ϕ = ϕ + + ϕ - (2.5) with ϕ + = 1 2 (ϕ + iν • ϕ) ϕ -= 1 2 (ϕ -iν • ϕ) (2.6)
and satisfies

Dϕ = -H • ν • ϕ (2.7)
This last equation reads

D(ϕ + + ϕ -) = -H • ν • (ϕ + + ϕ -) (2.8)
and implies

Dϕ + = -iHϕ - Dϕ -= iHϕ + (2.9)
If we set ϕ * = ϕ + -iϕ -then Dϕ * = Hϕ * and ϕ * is of constant length.

Proposition 2.1. The spinor fields ϕ + , ϕ -and ϕ * are given by

ϕ + = 1 2             1 - I y 1 + I 2 x + I 2 y   u +   I x -i 1 + I 2 x + I 2 y   v   1 + I y 1 + I 2 x + I 2 y   v +   I x + i 1 + I 2 x + I 2 y   u          
(2.10)

ϕ -= 1 2             1 + I y 1 + I 2 x + I 2 y   u -   I x -i 1 + I 2 x + I 2 y   v   1 - I y 1 + I 2 x + I 2 y   v -   I x + i 1 + I 2 x + I 2 y   u           (2.11) and ϕ * = 1 2 (1 -i)             1 - iI y 1 + I 2 x + I 2 y   u +   1 + iI x 1 + I 2 x + I 2 y   v   1 + iI y 1 + I 2 x + I 2 y   v +   iI x -1 1 + I 2 x + I 2 y   u           (2.12)
where u and v are (constant) complex numbers.

Proof. Since φ is a parallel spinor field on M , φ = (u, v) where u and v are two (constant) complex numbers. Let ρ 2 be the irreducible complex representation of Cl(3) described in Appendix A.1. Recall that

ν = 1 ∆ (-I x e 1 -I y e 2 + e 3 ) (2.13)
where ∆ = I 2 x + I 2 y + 1, so that

ρ 2 (ν) = - I x ∆ 0 i i 0 - I y ∆ -i 0 0 i + 1 ∆ 0 -1 1 0 (2.14)
By definition:

ν • ϕ = ρ 2 (ν) u v (2.15)
Simple computations lead now to the result.

The next step consists in computing the components (u, v) of the constant field φ. This is done by considering a quaternionic structure on the spinor bundle S(Σ) of the surface Σ and period forms.

Quaternionic Structure and Period Forms

Let I be the complex structure on S(Σ) given by the multiplication by i. A quaternionic structure on S(Σ) is a linear map J that satisfies J 2 = -Id and IJ = -JI. In the sequel J is given by

J ϕ 1 ϕ 2 = -ϕ 2 ϕ 1 (2.16)
If we write ϕ 1 = α 1 + iβ 1 and ϕ 2 = α 2 + iβ 2 , the corresponding quaternion is given by

ϕ 1 + ϕ 2 j = (α 1 + iβ 1 ) + (α 2 + iβ 2 )j = α 1 + iβ 1 + α 2 j + β 2 k
(2.17) and j(ϕ 1 + ϕ 2 j) = -ϕ 2 + ϕ 1 j (2.18) i.e. J is the left multiplication by j. Since

S + (Σ) = ϕ 1 ϕ 2 , ϕ 1 = I x -i I y + ∆ ϕ 2 (2.19)
and

S + (Σ) = ϕ 1 ϕ 2 , ϕ 1 = I x -i I y -∆ ϕ 2 (2.20) then JS + (Σ) ⊂ S -(Σ) and JS -(Σ) ⊂ S + (Σ).
We denote also J the quaternionic structure (obtained in the same way) on S(M ).

Let us consider φ = (u, v) a constant spinor field on M and ϕ * its restriction on Σ. Let also f : R 3 -→ R and g : R 3 -→ C be the functions defined by

f (m) = -(m • φ, φ) (2.21) and g(m) = i(m • φ, J(φ)) (2.22)
where ( , ) denotes the Hermitian product. Using the representation ρ 2 , one can check that

m • φ =   -im 2 u + (im 1 -m 3 )v (im 1 + m 3 )u + im 2 v   (2.23)
for m = (m 1 , m 2 , m 3 ). The equations f (m) = m 1 and g(m) = m 2 + im 3 are equivalent to:

|u| 2 = |v| 2 uv = - 1 2 (2.24) and uv = - 1 2 u 2 + v 2 = 1 u 2 = v 2 (2.25)
This implies u = ±1/ √ 2 and v = -u.

Definition 2.2. The spinor representation of the image given by the parametrization (2.1) is defined by

ϕ * = 1 2 √ 2 (1 -i)             1 - 1 + i(I x + I y ) 1 + I 2 x + I 2 y   -   1 + 1 + i(-I x + I y ) 1 + I 2 x + I 2 y             (2.26)
This means that u = 1/ √ 2 and v = -1/ √ 2 in the expression (2.12).

The two 1-forms

η f (X) = 2 (X • (ϕ * ) + , (ϕ * ) -) = -(X • ϕ, ϕ) (2.27) η g (X) = i(X • (ϕ * ) + , J((ϕ * ) + )) + i(X • (ϕ * ) -, J((ϕ * ) -)) = i(X • ϕ, J(ϕ)) (2.28)
are exact and verify d(f |Σ ) = η f , d(g |Σ ) = η g . The generalized Weierstrass parametrisation is actually given by the isometric immersion:

(η f , η g ) : Σ -→ M (2.29)

Dirac Equation and Mean Curvature

We only mention here some result that can be used when dealing with diffusion. We do not go into further details since we will not treat of this problem in the present paper. Let (Σ, g) be an oriented 2-dimensional Riemannian manifold and ϕ a spinor field without zeros solution of the Dirac equation Dϕ = λϕ. Then ϕ defines an isometric immersion

( Σ, |ϕ| 4 g) -→ R 3 (2.30)
with mean curvature H = λ/|ϕ| 2 (see [START_REF] Friedrich | On the spinor representation of surfaces in Euclidean 3-space[END_REF]).

Spinors and Segmentation

The aim of this section is to introduce the spinor tensor corresponding to the variations of the unit normal and to show its capability to detect both edges and textures.

The Spinor Tensor

We propose here to deal with a second order version of the classical approach of edge detection based on the so-called structure tensor (see [START_REF] Zenzo | A Note on the Gradient of a Multi-Image[END_REF]). Instead of measuring edges from eigenvalues of the Riemannian metric, we focus here on the eigenvalues of the tensor obtained from the derivative of the spinor field ϕ * . More precisely let

ϕ = ϕ 1 ϕ 2 (3.1)
be a section of the spinor bundle S(Σ) given in an orthonormal frame, i.e.

|ϕ| 2 = |ϕ 1 | 2 + |ϕ 2 | 2
and let X = (X 1 , X 2 ) be a section of the tangent bundle T (Σ). We consider the connexion ∇ on S(Σ) given by the connexion 1-form ω = 0. Thus

∇ X ϕ =      X 1 ∂ϕ 1 ∂x + X 2 ∂ϕ 1 ∂y X 1 ∂ϕ 2 ∂x + X 2 ∂ϕ 2 ∂y      (3.2)
and

|∇ X ϕ| 2 = X 2 1 ∂ϕ 1 ∂x 2 + 2X 1 X 2 ∂ϕ 1 ∂x ∂ϕ 1 ∂y + X 2 2 ∂ϕ 1 ∂y 2 + X 2 1 ∂ϕ 2 ∂x 2 + 2X 1 X 2 ∂ϕ 2 ∂x ∂ϕ 2 ∂y + X 2 2 ∂ϕ 2 ∂y 2 (3.3)
If we denote

G ϕ =       ∂ϕ 1 ∂x 2 + ∂ϕ 2 ∂x 2 ∂ϕ 1 ∂x ∂ϕ 1 ∂y + ∂ϕ 2 ∂x ∂ϕ 2 ∂y ∂ϕ 1 ∂x ∂ϕ 1 ∂y + ∂ϕ 2 ∂x ∂ϕ 2 ∂y ∂ϕ 1 ∂y 2 + ∂ϕ 2 ∂y 2       (3.4) then (X 1 X 2 )G ϕ (X 1 X 2 ) T = |∇ X ϕ| 2 (3.5) G ϕ is a field of real symmetric matrices.
As in the case of the usual structure tensor (i.e. Di Zenzo tensor, see [START_REF] Zenzo | A Note on the Gradient of a Multi-Image[END_REF]) the optima of |∇ X ϕ| 2 under the constraint X = 1 (for the Euclidean norm) are given by the field of eigenvalues of G ϕ . Applying the above formula to the spinor ϕ * of Definition 2.2 leads to Note that as already mentioned this last tensor corresponds to the tensor involved in the measure of the variations of the unit normal ν introduced in Sec. 2.1. Indeed, we have

G ϕ * = 1 2(1 + I 2 x + I 2 y ) 2   G 11 ϕ * G 12 ϕ * G 21 ϕ * G 22 ϕ *   ( 3
(X 1 X 2 )G ϕ * (X 1 X 2 ) T = d X ν 2 (3.8)

Experiments

We compare on Fig. 1 the edge and texture detection methods based on the usual structure tensor (Fig. 1(b) and 1(d)) and on the spinor tensor (Fig. 1(e) and 1(f)).

The structure tensor only takes into account the first order derivatives of the function I. The subsequent segmentation method detects the strongest grey-level variations of the image. As a consequence, this method provides thick edges, as can de observed.

The spinor tensor takes into account the second order derivatives of the function I too. By definition, it measures the strongest variations of the unit normal to the surface parametrized by the graph of I. We observe that this new approach provides thiner edges than the first one. It appears also to be more relevant to detect textures.

Spinors and Clifford Fourier Transform

We first define a Clifford Fourier transform using spin characters that is group morphisms from R 2 to Spin(3). Then, we introduce the spinor field decomposition leading to the harmonic decomposition of the image. Finally we show results of filterings.

Clifford Fourier Transform with Spin Characters

Let us recall the idea of the construction of the Clifford Fourier transform for color image processing introduced in [START_REF] Batard | Clifford Fourier Transform for Color Image Processing[END_REF]. From the mathematical viewpoint, a Fourier transform is defined through group actions and more precisely through irreducible and unitary representations of the involved group. This is closely related to the well known shift theorem stating that:

Ff α (u) = e iαu Ff (u) (4.1)
F(ϕ)(u, v) = n∈Z/N Z m∈Z/M Z ρ u,v,z1∧z2 (m,n) (-m, -n) • ϕ(m, n) (4.6)
where (z 1 , z 2 ) is an orthonormal frame of T (Σ).

Since the spinor bundle of Σ splits into

S(Σ) = S + z1∧z2 (Σ) ⊕ S - z1∧z2 (Σ) (4.7)
we have

ρ u,v,z1∧z2(m,n) (-m, -n) • ϕ(m, n) = e 2πi(um/M +vn/N ) ϕ + (m, n) v -i (m, n) + e -2πi(um/M +vn/N ) ϕ -(m, n) v i (m, n) (4.8
) where v -i , resp. v i is the unit eigenspinor field of eigenvalue -i, resp i relatively to the operator z 1 ∧ z 2 • (here • denotes the Clifford multiplication). Consequently

F(ϕ)(u, v) = ϕ + -1 (u, v), ϕ -(u, v) (4.9)
in the frame (v -i , v i ), where and -1 denote the Fourier transform on L 2 (Z/M Z × Z/N Z, C), also called discrete Fourier transform, and its inverse.

Spinor Field Decomposition

The inverse Clifford Fourier transform of ϕ reads

F -1 (ϕ)(u, v) = n∈Z/N Z m∈Z/M Z ρ u,v,z1∧z2(m,n) (m, n) • ϕ(m, n) (4.10)
This means that every spinor field ϕ may be written as a superposition of basic spinor fieds, i.e.

ϕ = ϕ m,n (4.11)
where

ϕ m,n : (u, v) -→ ρ u,v,z1∧z2(m,n) (m, n) • F(ϕ)(m, n) (4.12)
Following the splitting

S(Σ) = S + z1∧z2 (Σ) ⊕ S - z1∧z2 (Σ), we have ϕ m,n = ϕ + m,n , ϕ - m,n
in the frame (v -i , v i ), with

ϕ + m,n : (u, v) -→ e -2πi(um/M +vn/N ) ϕ + -1 (m, n) and ϕ - m,n : (u, v) -→ e 2πi(um/M +vn/N ) ϕ -(m, n) Moreover, |ϕ m,n | 2 = |ϕ + m,n | 2 + |ϕ - m,n | 2 since S + z1∧z2 (
Σ) and S - z1∧z2 (Σ) are orthogonal.

Experiments

Let us give now an example of applications of the Clifford Fourier transform on spinor fields to image processing. In order to perform filterings with the decomposition (4.11), we proceed as follows. Let I be a grey-level image, and ϕ * be the corresponding spinor representation given in Def. 2.2. We apply a Gaussian mask T σ of variance σ in the spectrum Fϕ * of ϕ * . Then, we consider the norm of its Fourier inverse transform, i.e. |F -1 T σ Fϕ * | and the function |F -1 T σ Fϕ * | I. We can see on the left columns of Fig. 2 and Fig. 3 that the filtering acts through ϕ * as a smoothing of the geometry of the image. More precisely, when σ is small, the modulus |F -1 T σ Fϕ * | is small on points corresponding to nearly all the geometric variations of the image. When σ increases the modulus is affected only on points corresponding to the strongest geometric variations, i.e. to both edges and textures (and also where the noise is high). The right columns of Fig. 2 and Fig. 3 show that the filtering acts through |F -1 T σ Fϕ * | I as a diffusion that leaves the geometric data untouched (the higher is σ the more important is the diffusion). This appears clearly on Fig. 4 (compare the plumes of Lena's hat) or on Fig. 5 (compare the hair of Tiffany). These experiments show that our approach is pertinent to deal with harmonic analysis together with Riemannian geometry.

Conclusion.

Spin geometry is a powerful mathematical tool to deal with many theoretical and applied geometric problems. In this paper we have shown how to take advantage of the generalized Weierstrass representation to perform grey-level image processing, in particular edge and texture detection. Our main contribution is the definition of a Clifford Fourier transform for spinor fields that relies on a generalization of the usual notion of character (the spin character). One important fact is that this new transform takes into account the Riemannian geometry of the image surface by involving the spinor field that parametrizes the normal and the bivector field coding the tangent plane. We have also introduced what appears to be a harmonic decomposition of the parametrization and investigated applications to filtering. Note that there are only two cases where the Grassmannian G n,2 of 2planes in R n admits a rational parametrization. In fact, one can show that G 3,2 CP 1 and G 4,2 CP 1 × CP 1 (see [START_REF] Taimanov | Two-dimensional Dirac operator and surface theory[END_REF]). The case treated here corresponds to G 3,2 . As a consequence the generalization to color images is not straightforward. Nevertheless, a quite different approach is possible to tackle this problem and will be the subject of a forthcoming paper. Let us also mention that one may envisage to perform diffusion on grey-level images through the heat equation given by the Dirac operator. This last one is well known be a square root of the Laplacian. Preliminary results are discussed in [START_REF] Batard | Spinor representation of images[END_REF] that show that this diffusion better preserves edges and textures than the usual Riemannian approaches.

Figure 1 .

 1 Figure 1. Segmentation: structure tensor vs spinor tensor

Definition 4 . 1 .

 41 The Clifford Fourier transform of a spinor ϕ of S(Σ) is given by

Fig. 2 and

 2 Fig. 3 show results of this process for different values of σ (left column |F -1 T σ Fϕ * | and right column |F -1 T σ Fϕ * | I). It is clear that for σ sufficiently high, we have |F -1 T σ Fϕ * | I I and |F -1 T σ Fϕ * | 1 since |ϕ * | = 1. This explains why the two left bottom images are almost white and the two right bottom images are almost the original ones.

Figure 2 .Figure 3 .

 23 Figure 2. Left: |F -1 (T σ Fϕ * )| for σ = 100, 1000, 10000, 100000 (from top to bottom). Right: |F -1 (T σ Fϕ * )|I

  2I xx I xy I x I y 2I yy I xy I x I y G 12 ϕ * = I xx I xy + I xy I yy + I xx I xy I 2 y + I xy I yy I 2 x -I 2 xy I x I y -I xx I yy I x I y Definition 3.1. The tensor G ϕ * is called the spinor tensor of the surface Σ.

	with
	G 11 ϕ * = I 2 xx + I 2 xy + I 2 xx I 2 y + I 2 xy I 2 x -G 22 ϕ * = I 2 yy + I 2 xy + I 2 yy I 2 x + I 2 xy I 2 y -G 21 ϕ * = G 12 ϕ *
	(3.7)
	.6)

This work was partially supported by the ONR Grant N00014-09-1-0493.

Appendix A. Mathematical Background

We recall here some definitions and results concerning spin geometry. The reader may refer to [START_REF] Lawson | Spin Geometry[END_REF] for details and conventions. We focus on the particular case of an oriented surface immersed in R 3 .

A.1. Complex Representations of C 3,0 ⊗ C Let (e 1 , e 2 , e 3 ) be an orthonormal basis of R 3 . The Clifford algebra C 3,0 is the quotient of the tensor algebra of the vectorial space R 3 by the ideal generated by the elements u ⊗ u + Q(u) where Q is the Euclidean quadratic form. It can be shown that C 3,0 is isomorphic to the product H × H of two copies of the quaternion algebra. The complex Clifford algebra

where C(2) denotes the algebra of 2×2-matrices with complex entries. This decomposition is given by

Thomas Batard and Michel Berthier

and ω 3 is the pseudoscalar e 1 e 2 e 3 . More precisely, the subalgebra (C 3,0 ⊗C) + is generated by the elements and an isomorphism with C(2) is given by sending these elements to the matrices

In the same way, (C 3,0 ⊗ C) -is generated by and an isomorphism is given by sending these elements to the above matrices

Let us denote ρ the natural representation of C(2) on C 2 . The two equivalent classes ρ 1 and ρ 2 of irreducible complex representations of C 3,0 ⊗C are given by ρ

They are characterized by

For the sake of completeness, let us explicit these representations:

The complex spin representation of Spin(3) is the homomorphism

given by restricting an irreducible complex representation of C 3,0 ⊗ C to the spinor group Spin(3) ⊂ (C 3,0 ⊗ C) 0 (see for example [START_REF] Batard | A Metric Approach to nD Images Edge Detection with Clifford Algebras[END_REF] for the definition of the Spin group). Note that ∆ 3 is independant of the chosen representation.

A.2. Spin Structures and Spinor Bundles

Let us denote M the Riemannian manifold R 3 and P SO (M ) the principal SO(3)-bundle of oriented orthonormal frames of M . A spin structure on M is a principal Spin(3)-bundle P Spin (M ) together with a 2-sheeted covering

that is compatible with SO(3) and Spin(3) actions. The Spinor bundle S(M ) is the bundle associated to the spin structure P Spin (M ) and the complex spin representation ∆ 3 . More precisely, it is the quotient of the product P Spin (M ) × C 2 by the action

that sends (τ, p, z) to (pτ -1 , ∆ 3 (τ )z). We will write

It appears that the fiber bundle S(M ) is a bundle of complex left modules over the Clifford bundle Cl(M ) = P Spin (M ) × Ad Cl(3) of M . In the sequel

denotes the corresponding multiplication for u ∈ T (M ) and φ a section of S(M ).

We consider now an oriented surface Σ embedded in M . Let us denote (z 1 , z 2 ) on orthonormal frame of T (Σ) and ν the global unit field normal to Σ. Using the map

it is possible to pull back the bundle P Spin (M ) |Σ to obtain a spin structure

the algebra C 2,0 ⊗ C acts on C 2 via ρ 2 . This representation leads to the complex spinor representation ∆ 2 of Spin( 2). It can be shown that the induced bundle

coincides with the spinor bundle of the induced spin structure on Σ. Once again S(Σ) is a bundle of complex left modules over the Clifford bundle Cl(Σ) of Σ: the Clifford multiplication is given by the map

for v ∈ T (Σ) and ϕ a section of T (Σ). The Spinor bundle S(Σ) decomposes into [START_REF] Friedrich | On the spinor representation of surfaces in Euclidean 3-space[END_REF]). Since ρ 2 (z 1 z 2 ν) is minus the identity, this is equivalent to

. Spinor Connections and Dirac Operators

Let ∇ M and ∇ Σ be the Levi Civita connections on the tangent bundles T (M ) and T (Σ) respectively. The classical Gauss formula asserts that

where X and Y are vector fields on Σ. A similar formula exists when dealing with spinor fields. Let us first recall that one may construct on S(M ) and S(Σ) some spinor Levi Civita connections compatible with the Clifford multiplication, that is connections still denoted ∇ M and ∇ Σ verifying

when X and Y are vector fields on M and ϕ is a section of S(M ) and a similar formula for ∇ Σ . The analog of Gauss formula reads

for ϕ a section of S(Σ) and X a vector field on Σ (see [START_REF] Bar | Metrics with harmonic spinors[END_REF] for a proof). If (z 1 , z 2 ) is an orthonormal frame of T (Σ), following [START_REF] Friedrich | On the spinor representation of surfaces in Euclidean 3-space[END_REF], the Dirac operator on S(Σ) is defined by

and it can be verified that DS ± (Σ) ⊂ S ∓ (Σ).

Let now φ and ϕ be respectively a section of S(M ) and the section of S(Σ) given by the restriction φ |Σ . We obtain from Gauss spinor formula

where H is the mean curvature of Σ, it follows that


Amélie Cordier
email: amelie.cordier@liris.cnrs.fr

Emmanuelle Gaillard
email: emmanuelle.gaillard@loria.fr

Emmanuel Nauer
email: emmanuel.nauer@loria.fr

Man-Machine Collaboration to Acquire Cooking Adaptation Knowledge for the TAAABLE Case-Based Reasoning System

Keywords: I.2.6 [Artificial Intelligence]: Learning-knowledge acquisition, H.2.8 [Database Management]: Database Applications-Data mining, H.3.3 [Information Storage and Retrieval]: Information Storage and Retrieval-relevance feedback Man-machine collaboration, adaptation knowledge acquisition, semantic wiki, case-based reasoning, knowledge discovery

come

L'archive ouverte

INTRODUCTION

This paper presents an architecture for improving the collaboration between humans and machines in the framework of the system Taaable 1 . Taaable is a case-based reasoning (CBR) system which adapts cooking recipes to users constraints [START_REF] Badra | Taaable: Text Mining, Ontology Engineering, and Hierarchical Classification for Textual Case-Based Cooking[END_REF], using cooking knowledge encoded in a semantic wiki, called WikiTaaable 2 [START_REF] Cordier | Wikitaaable: A semantic wiki as a blackboard for a textual case-based reasoning system[END_REF]. Storing the cooking knowledge into a wiki allows to better manage knowledge: users are fully involved in the knowledge acquisition part of the system instead of only using the Taaable system. The idea is that if users increase the quantity and the quality of the knowledge in the wiki, the results of the Taaable adaptation process improves. For this, automated processes, like the Taaable adaptation process and other knowledge extraction processes, can be used to feed the wiki with new knowledge. Our objective, in this paper, is to consider [START_REF] Badra | Taaable: Text Mining, Ontology Engineering, and Hierarchical Classification for Textual Case-Based Cooking[END_REF] the "knowledge" part (WikiTaaable) and the "reasoning" part (Taaable) of a CBR system as a whole, (2) that these two parts can mutually and continuously benefits one from the other, and (3) that users play a key role for managing the interactions between these two parts.

This paper proposes an architecture that improves the acquisition of adaptation knowledge (AK), a specific kind of knowledge a CBR system can use to improve its results. The Taaable/WikiTaaable cooking application is chosen as concrete use case. Section 2 gives the minimal requirements about this application context and the motivations for acquiring AK. Section 3 gives the architecture for the collaboration between automatic processes and users for improving the AK acquisition and shows how this architecture has been instantiate in our use case. Section 4 presents related works and section 5 concludes the paper and discusses ongoing works.

CONTEXT AND MOTIVATION

Taaable is a CBR system that has been designed for participating to the Computer Cooking Contest3 , an international contest which aims at comparing CBR system results on a common domain: cooking. Several challenges are proposed in this contest. Among them, two challenges (won by Taaable in 2010):

• the main challenge, asking CBR systems to return recipes satisfying a set of constraints given by the user, such as inclusion or rejection of ingredients, the type or the origin of the dish, the compatibility with some diets (vegetarian, nut-free, etc.). For example: a user may ask for "a dessert, with rice and fig", as illustrated in Figure 1. Systems have to search into a set of limited (approximately 1500) recipes for recipes satisfying the constraints, and if there is no recipe satisfying all the constraints, the systems have to adapt existing recipes into new ones.

• the adaptation challenge, asking CBR systems to adapt a given recipe to specific constraints. For example, "adapt the My strawberry pie recipe because I do not have strawberry". Like many CBR systems [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF], Taaable uses an ontology to retrieve the source cases that are the most similar to a target case (i.e. the query). Taaable retrieves and creates cooking recipes by adaptation. According to the user constraints, the system looks up, in the recipe base (which is a case base), whether some recipes satisfy these constraints. Recipes, if they exist, are returned to the user; otherwise the system is able to retrieve similar recipes (i.e. recipes that match the target query partially) and adapts these recipes, creating new ones. Searching similar recipes is guided by several ontologies, i.e. hierarchies of classes (ingredient hierarchy, dish type hierarchy, etc.), in order to relax constraints by generalising the user query. The goal is to find the most specific generalisation (with the minimal cost) for which recipes exist in the case base. Adaptation consists of substituting some ingredients of the source cases by the ones required by the user. It is important to notice that Taaable is based on an hypothetical reasoning and not deductive one. So, it is possible that some adaptations proposed by the system may be irrelevant (i.e. not cookable).

TAAABLE principles

For dealing with the adaptation of a specific recipe (which is the adaptation challenge problem), Taaable uses the same hierarchy based generalisation/specialisation mechanism on a recipe base containing only the recipe that has to adapted. For example, when adapting the "My Strawberry Pie" recipe (in which strawberries are required) to the constraint "no strawberry", Strawberry is generalised on Berry, which is then specialised in another berry (Raspberry, Blueberry, Blackberry, etc.). Substitutions (e.g substitute Strawberry by Raspberry) are proposed to the user.

Again, this hierarchy-based adaptation can produce bad substitutions. Indeed, adding a new ingredient in a recipe may be incompatible with some other ingredients(s) of the recipe and/or may require the addition of new ingredient(s). Another problem, when adapting a given recipe is that Taaable is not able to choose, during the specialisation step, which ingredient is the best for substituting another one. In the previous example, Taaable is not able to determine whether it is better to replace Raspberry by Strawberry, by Blueberry or by any other berry. This lack has been corrected by building a special knowledge discovery process which is detailed in section 2.4.

WikiTAAABLE

WikiTaaable is a semantic wiki that uses Semantic Me-diaWiki [START_REF] Krötzsch | Semantic mediawiki[END_REF] as support for encoding knowledge associated to wiki pages. WikiTaaable contains the set of resources required by the Taaable reasoning system, in particular: an ontology of the domain of cooking, and recipes. The cooking ontology is composed of 6 hierarchies: a food hierarchy (related to ingredients used in recipes, e.g. Berry, Meat, etc.), a dish type hierarchy (related to the types of recipes, e.g. PieDish, Salad, etc.), a dish moment hierarchy (related to when eating a dish, e.g. Snack, Starter, Dessert, etc.), a location hierarchy (related to the origins of recipes, e.g. France, Asia, etc.), a diet hierarchy (related to food allowed or not for a specific diet, e.g Vegetarian, NutFree, etc.), an action hierarchy (related to cooking ac- tions used for preparing ingredients, toCut, toPeel, etc.). In the semantic wiki, each concept of a hierarchy is encoded as a category page Category : < conceptname >. For example, the concept of berry is encoded in the Category:Berry page, as shown in Figure 2. Each concept is described by a short description, lexical variants (used by the annotation bot, for searching concepts in the full text of recipes), his sub-categories and super-categories. For berries, the wiki page indicates that Berry is a sub-concept of Fruit (corresponding to the Category : F ruit page), and sub-categories of Berry (e.g. Raspberry, Blueberry, etc.) are listed.

The set of recipes contained in WikiTaaable are those provided by the contest, that have been semantically annotated according to the domain ontology. Each recipe, as the one given in example in Figure 3, is encoded as a wiki page, composed of several sections: a title, which is the name of the recipe, an "Ingredients" section containing the list of ingredients used in the recipe, each ingredient being linked to its corresponding Category page in the food hierarchy, a "Textual Preparation" section describing the preparation process, some possible "substitutions" which are adaptation knowledge, and "other information" like the dish type, for example.

Adaptation knowledge

Improving the current results of Taaable could be done by acquiring adaptation knowledge (AK). In CBR systems, using AK is a classical approach for producing more fine grain adaptations [START_REF] Lopez De Mantaras | Retrieval, reuse, revision and retention in case-based reasoning[END_REF]. In the Taaable/WikiTaaable context, an AK is a substitution of some ingredients by other ones (e.g. in "My Strawberry Pie" recipe, Strawberry could be replaced by Raspberry). Formally, an adaptation knowledge is a 4-tuple (context, replace, by, origin), where:

• context represents the recipe or the class of recipes on which the substitution can be applied. An AK is specific if its context is a single recipe and generic if its context is a class of recipes (a specific type of dish, for example). In this paper, only specific AK are considered.

• replace and by are respectively the set of ingredients that must be replaced and the set of replacing ingredients.

• origin is the source the AK comes from. Currently, four sources have been identified:

1. Taaable, when AK results from a proposition of adaptation given by the reasoning process of Taaable. 2. AK extractor, when AK results from a specific knowledge discovery system called "AK Extractor" (which is detailed in the next section). 3. user, when AK is given by a user by editing the wiki, as it is usually done in cooking web site, when users add comments about ingredient substitution on a recipe. See, for example, http://en.wikibooks.org/wiki/Cookbook: substitutions.

4. recipe, when the AK is directly given by the original recipe when a choice between ingredients is mentioned (e.g. "100g butter or margarine"). This particular substitutions are taken into account by a wiki bot which runs through the wiki for automatically extracting them.

According to this definition, ("My Strawberry Pie", Strawberry, Raspberry, Taaable), is an AK obtained from Taaable, meaning that strawberries can be replaced by raspberries in the "My Strawberry Pie" recipe. In Wiki-Taaable, each substitution is encoded as a wiki page like the one given in Figure 4. A semantic query is used to feed automatically the Substitutions section of a recipe page, as visible in Figure 3.

Adaptation knowledge extractor

Semi-automatic extraction of AK for adapting cooking recipe has been studied in [START_REF] Gaillard | Adaptation knowledge discovery for cooking using closed itemset extraction[END_REF]. An operational system that proposes ingredient substitutions for adapting a given recipe to additional constraints has been implemented. Figure 5 shows an example of results for adapting the "My Strawberry Pie" recipe without strawberry. AK Extractor proposes a set of substitutions like replacing Strawberry and CoolWhip by Raspberry and FoodColor, or by Peach and LemonJuice, etc. The AK Extractor is founded on a typical knowledge discovery in databases (KDD) process. The main steps of a KDD process are data selection and preparation, datamining, and interpretation of the extracted units of information [START_REF]Advances in Knowledge Discovery and Data Mining[END_REF]. The step of interpretation requires usually an expert of the domain for validating the extracted units for giving them a status of knowledge (for cooking, many web users could be considered as experts). In traditional KDD approaches, the KDD process produces a huge amount of information units which can be turned into knowledge. Experts have then to process these information units in order to validate the "good" ones, which become knowledge. This is a tedious task for experts. In addition, they face situations where they cannot decide if an information unit is appropriate or not because they lack context information to decide. By contrast, the AK approach we describe in this paper is interactive and opportunistic [START_REF] Cordier | Interactive and Opportunistic Knowledge Acquisition in Case-Based Reasoning[END_REF]. Users use the same interface for querying the system and for validating knowledge. In addition, they validate knowledge on the fly, in context, which is more convenient than dealing with a huge amount of candidate knowledge (information units) out of any context. AK Extractor is based on a comparison of ingredients between the recipe to adapt, and a set of similar recipes. The system selects first recipes which have a minimal number of ingredients in common and a minimal number of different ingredients with the recipe that has to be adapted. Closed itemsets [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] are extracted from variations between recipes, starting from variations between each selected recipe of the previous step and the recipe to adapt. The closed itemsets are then filtered and ranked with specific rules (which are detailed in [START_REF] Gaillard | Adaptation knowledge discovery for cooking using closed itemset extraction[END_REF]). The system displays the propositions for ingredient substitutions coming from the first five better ranked closed itemsets. Finally, user can give feedback for validating or not some of these propositions.

Objectives

In a semantic wiki, knowledge is in continuous evolution. Usually, this evolution results from users that feed the wiki. The main objective of this work is to increase the acquisition of AK by establishing a collaborative environment between users and automatic processes supported by machines. An interesting point is that the reasoning system (Taaable) is not only seen as the consumer of the wiki knowledge but also as the producer of new knowledge that will be added to the wiki.

Automatic processes and collective intelligence must be coordinated. The better machines and users will collaborate, the better the acquisition process succeed. Indeed, machines are able to compute lot of things (for example, substitution propositions for Taaable and AK Extractor) but the results cannot be considered as knowledge before they are validated as such by a human expert. Indeed, the crucial step of the KDD process [START_REF]Advances in Knowledge Discovery and Data Mining[END_REF] is that the results produced by the machine must be interpreted and validated by a (human) expert. So, users will be asked to play the role of the expert for validating automatic results produced by machine and a proposition of substitution becomes an AK only when it is validated by a user.

The next section details our approach for enhancing the collaboration between humans and machines, by plugging together automatic systems (Taaable, WikiTaaable and AK Extractor) under the control of users.

Increasing the quantity and quality of AK in the wiki will improve the results of the reasoning system. However, this requires a smooth modification of the reasoning process for taking into account the AK for computing adaptation (this is a short-term work). Besides, to ensure the nonregression of the system, the impact of the continuously new AK produced on the system results must be evaluated by test sets. In this paper, we focus on AK acquisition. A way for evaluating how knowledge evolution can be managed for improving the results of a reasoning process is studied in [START_REF] Skaf-Molli | Knowledge Continuous Integration Process (K-CIP)[END_REF].

COLLABORATIVE ENVIRONMENT FOR ACQUIRING AK FROM VARIOUS SOURCES

The approach

Currently, users are already involved in Taaable, Wi-kiTaaable and AK Extractor systems when they use them, but these three systems are separated. If they were integrated, each could benefit from the others. Some interactions between these systems have to be developed. For example, Taaable and AK Extractor return substitution propositions, and users can validate these propositions as being relevant or not. Each system has is own storage for taking into account the user feedbacks, but there is no common space for storing together all the AK that can be produced. The architecture proposed in Figure 6 aims at plugging together the three systems (WikiTaaable, Taaable and AK Extractor) and WikiTaaable will be used to store the results of AK acquisition produced by humans as well as produced by machines.

Machines and humans will work together for a common objective which is AK acquisition. In our approach, users are essential for controlling and integrating AK produced by automatic processes in WikiTaaable. Indeed, additionally to their wiki editing, users will trigger automatic processes and validate their results. They play the role of cooking expert when validating substitution propositions as AK being stored in the wiki. Besides, different users can, in parallel, start Taaable, AK Extractor on a specific recipe page, or edit new substitution pages in the wiki. The new AK integrated in the wiki will be used, at short term, by the reasoning process of Taaable. Thus, this loop ensures the continuous knowledge building and the improvement of the results in Taaable.

Figure 6 shows the interaction between the different resources and their integration into a global system. In this system, a user can (1) directly edit a wiki substitution page for adding, removing, modifying AK.

When a user (2) queries Taaable, (3) Taaable computes adaptation propositions thanks to (4) knowledge stored in WikiTaaable. These propositions are presented to the user who has (5) to evaluate whether a proposition is relevant or not. If the proposition is relevant (i.e. "OK" has been activated), this proposition becomes an AK which will automatically (6) feed a new substitution page, which context is the recipe concerned by the adaptation.

A similar process holds when a user ( 7) queries the AK Extractor, which (8) computes substitution propositions, submitted to the user (5) evaluation and which will (6) feed the wiki with AK if relevant.

Finally, the possibility of ( 9) trigger the AK Extractor for a given recipe is added in all recipe pages. In that case, the sequence [START_REF] D'aquin | Adaptation Knowledge Discovery from a Case Base[END_REF][START_REF] Cordier | Interactive and Opportunistic Knowledge Acquisition in Case-Based Reasoning[END_REF][START_REF] Cordier | Interactive Knowledge Acquisition in Case Based Reasoning[END_REF] takes place again.

The communication between Taaable and WikiTaaable is performed through the RDF store linked to Semantic Media Wiki. On one side, Taaable, as well as AK Extractor, read RDF data from this store when using knowledge of the wiki. On the other side, results provided by Taaable and AK Extractor are written as RDF triple, for feeding the RDF store, and, by extension, the wiki.

Even if the architecture is presented in a specific domain with specific systems, this kind of organisation can be reproduced in various domain, because it is a generic organisation. Indeed, inference engines, KDD engines and wikis can collaborate together under the control of users, who play a key role in the organisation.

Implementation of the architecture in TAAABLE/WIKITAAABLE

The proposed architecture has been instantiated to integrate Taaable feedback and the AK Extractor process in WikiTaaable. Some screenshots are given to show how it looks like in the wiki. Figures 7,8, and 9 illustrate how the AK Extractor process has been integrated as a wiki extension. Figure 7 shows the first step of the AK Extractor process in which the user has to give constraints on the recipe to adapt. This interface is triggered by a special link that has been added on each recipe page. The interface given in example was obtained from the "My Strawberry Pie" recipe page. The user enters constraints (e.g. -Strawberry means that the user does not want strawberries). When clicking on "Compute adaptations", the AK discovery process is run. This process produces a wiki page with some AK propositions, as it is illustrated in Figure 8. The user may validate some proposition(s) as being relevant by clicking on "OK". Optionally, some adjustments could be made thanks to the checkboxes: if not checked, an ingredient will not take part of the substitution4 . Figure 9 shows the page resulting from the validation of the first proposition of substitution. This page announces that a substitution page, like the one presented in Figure 4, has been created and that this substitution will automatically appear in the recipe page as an AK, as illustrated in Figure 10.

RELATED WORK

Previous works deal with man-machine collaboration where knowledge is obtained by a knowledge extraction process which is guided or/and validated by human. In this section, we present several systems based on KDD or on CBR or even both that demonstrate this collaboration.

KDD systems

The KDD process requires to be supervised by an expert, who could interact at various levels. One of the most usual problems in a KDD is to control the over-abundance of results generated by the KDD process. The expert could, for example, interact for better selecting the data that will be mined as it is described in [START_REF] Chen | Query construction for user-guided knowledge discovery in databases[END_REF] which proposes an approach for optimising the formulation of the problem to solve. Another approach consists in filtering and ranking of numerous results obtained by the data mining algorithms. For example, [START_REF] Silberschatz | On subjective measures of interestingness in knowledge discovery[END_REF] proposes subjective measures of interestingness for evaluating the datamining results. These measures depend on the user profile and a result is considered as interesting for a user according to two major reasons unexpectedness (if the user is "surprised" by the results) and actionability (if the user can exploit the results). The paper focuses on unexpected results which are results in contradiction with beliefs of the user. So, a result which may revise beliefs of a user is relevant.

Another usual problem of the KDD process is the selection of relevant information units among the large set of information units produced, for transforming them into knowledge. Many approaches for taking into account this step of the KDD process have been proposed. For example, [START_REF] Bendaoud | Formal Concept Analysis: A unified framework for building and refining ontologies[END_REF] presents a methodology for KDD in the context of building a semi-automatic ontology from heterogeneous textual resources. [START_REF] Bendaoud | Formal Concept Analysis: A unified framework for building and refining ontologies[END_REF] uses formal concept analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] for classifying objects according to their properties which are extracted from various textual resources (e.g thesaurus, full texts, dictionaries, etc.). The results of the FCA process is translated in description logics for representing the ontology concepts. Experts are involved at each step of the KDD process. For example, when the properties describing the objects are produced by an automatic extraction process, experts have to validate and filter the most representative properties, i.e. that described the best the objects. At the last step of the process, experts have to validate the formal concepts that have been produced, by selecting those which makes sense in their domain.

The integration of the AK Extractor follows the same principle. AK Extractor implements a KDD process which produces a set of substitution propositions. These substitutions have to be validated in order to be stored as AK.

CBR systems

CBR [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF] is a method for solving new problems thanks to adaptation of previously solved problems. However, the step of adaptation may fail. Consequently, CBR systems integrating users are built in order to repair irrelevant adaptations. The systems presented in the following involve user in an opportunistic way, the goal is to repair adaptations that have failed, by acquiring AK or by increasing the domain knowledge (on which the reasoning is based) itself.

DIAL [START_REF] Leake | Acquiring Case Adaptation Knowledge: A Hybrid Approach[END_REF] focuses on an interactive acquisition of AK in the domain of disaster response planning. When the system returns a solution that is inconsistent, the response planning is returned with a description of the elements that need to be adjusted in the planning. For example, a response planning for an earthquake in Los Angeles indicates that National Guard must be called. When this plan is used for an earth-quake in Indonesia, a problem arises because there is not National Guard in Indonesia. So, the response plan must be adapted. DIAL is composed of three kinds of adaptation process:

• case-based adaptation: which reuses adaptations which previously performed,

• rule-based adaptation: which determines elements that have to be adapted and the transformation to apply (e.g substitute an element) by the generation of a generic rule. The generic rule is then instantiated by searching relevant knowledge in the knowledge base.

In the previous example, it consists in building a rule meaning that national guard must be substituted, and instantiate this rule by a substituting element searched in the knowledge base,

• manual adaptation: from an interface, a user may select a generic transformation to apply and navigate in the knowledge base to search relevant knowledge for instantiating the generic transformation. This third adaptation method is a man-machine collaboration for AK acquisition triggered opportunistically. Indeed, in case of failure of the case-based and rule-based adaptations, the system proposes the user to guide the adaptation process. After being solved, the AK is memorised. An AK corresponds to the transformation applied (e.g substitute an element) with the links in the knowledge base toward relevant knowledge uses to make the transformation.

In DIAL, adaptation is manually transformed if automatic adaptations fail. Conversely, WebAdapt [START_REF] Leake | Mining Large-Scale Knowledge Sources for Case Adaptation Knowledge[END_REF] proposes two independent adaptations modes: one automatic and one manual. WebAdapt is a system for personalising adaptations based on learned information about user preferences. WebAdapt is used in the domain of sightseeing itinerary planning. The system adapts a proposed itinerary, corresponding to a list of locations, with one of these two independent adaptation modes. Either, the user of WebAdapt indicates a location to substitute and if the location must be substitute by criteria of similarity or criteria of nearness. Then, WebAdapt computes an automatic adaptation without intervention of the user. Either, the itinerary proposed by the process is customized by user preferences. The user selects constraints (e.g. "I would like to visit building of the 16th century") in order to adapt locations proposed by the system.

The FRAKAS system [START_REF] Cordier | Interactive and Opportunistic Knowledge Acquisition in Case-Based Reasoning[END_REF] is also such an opportunistic system, which integrates interactions with an expert during the reasoning for acquiring missing domain knowledge and ensure a better adaptation. The adaptation proposed by the system is evaluated by an expert. From an interface, the expert may detect some inconsistencies between the proposed adaptation and its own knowledge. If an inconsistency is detected, the adaptation failed. At this moment, user completes the domain knowledge by selecting incompatible problem variables and/or solutions variables. Adapted cases and domain knowledge are acquired at the same time during the interactive part between the expert and the system.

Like [START_REF] Cordier | Interactive Knowledge Acquisition in Case Based Reasoning[END_REF], [START_REF] Badra | Opportunistic Adaptation Knowledge Discovery[END_REF] uses an opportunistic approach for AK acquisition. In the second version of Taaable, which implements the approach proposed in [START_REF] Badra | Opportunistic Adaptation Knowledge Discovery[END_REF], users may give some feedback on substitutions for adapting recipes. If a proposition of substitution is judged irrelevant by the user, an interface allows to guide the system for repairing the adaptation. The user may indicate that some ingredient(s) is/are missing when adding an ingredient, or that some ingredients of the recipe are not compatible with an ingredient that must be added. In the case where is ingredient(s) missing, a system of AK acquisition, called Cabamaka [START_REF] D'aquin | Adaptation Knowledge Discovery from a Case Base[END_REF] based on KDD, is triggered. This last step allows to repair the bad adaptation and memorise the AK. The AK is a rule composed of ingredient(s) that have to be removed and ingredient(s) that have to be added, similar to a substitution AK used in WikiTaaable.

In each of the previous systems, knowledge acquisition is triggered when an adaptation failed. The originality of approach is that AK can be triggered in parallel of the adaptation process and that this knowledge can be acquired at any time in a semantic wiki collaborative space.

CONCLUSION

This paper proposes an architecture for improving the man-machine collaboration for collecting AK for a CBR system. Automatic processes are integrated under the control of users for feeding knowledge in a semantic wiki. In the specific context of a CBR system, this approach allows to better collect adaptation knowledge. The CBR engine, which was initially only a consumer of the wiki knowledge, has been turned as a producer as well. Other tools, and especially knowledge discovery ones, can be plugged as wiki extension for helping users to feed the wiki. A single interface is used for viewing, querying, enriching and correcting the knowledge. Moreover, as it is a collaborative wiki interface, everyone will benefit from the experience of the other members of the community.

As our approach produces specific AK (i.e. for adapting a specific recipe), an extension of this work concerns the study and the development of a KDD process for extracting generic adaptations (i.e. for a set of recipes, for a given dish type, for example). Another short-term work concerns the exploitation of irrelevant adaptation propositions. It was shown that when a user validates a adaptation proposition as being relevant, this adaptation becomes an AK and is stored in the wiki. However, when a proposition is irrelevant (i.e. the user disagrees with an automatic adaptation), nothing is currently done for collecting them nor for exploiting them. Some specific interactions with the user could be developed for integrating a process for dealing with rejected adaptations proposed by Taaable or AK Extractor.

Figure 1 :

 1 Figure 1: The TAAABLE interface. Queried for a dessert dish, with rice and fig, TAAABLE proposes to replace mango by fig in the "Glutinous rice with mangoes" recipe. After viewing the adapted recipe, the user can give feedback about the substitution ("OK" or "not OK").

Figure 2 :

 2 Figure 2: The Berry concept in WIKITAAABLE.

Figure 3 :

 3 Figure 3: Example of a WIKITAAABLE recipe.

Figure 4 :

 4 Figure 4: Example of a substitution page.

Figure 5 :

 5 Figure 5: An illustration of the AK extractor interface

Figure 6 :

 6 Figure 6: Architecture for a man-machine AK acquisition in the cooking domain.

Figure 7 :

 7 Figure 7: The AK Extractor query interface.

Figure 8 :

 8 Figure 8: AK propositions computed by the AK Extractor.

Figure 9 :

 9 Figure 9: Generating the AK substitution page.

Figure 10 :

 10 Figure 10: "My Strawberry Pie" substitutions section after the acquisition of a new substitution.

http://computercookingcontest.net/

the "not OK" button does not produce anything yet.

ACKNOWLEDGEMENTS

This work is supported by French National Agency for Research (ANR), program Contint 2011. More information about Kolflow is available on the project website: http: //kolflow.univ-nantes.fr/.


G Fitton
email: fittong@cereve.enpc.fr

I Tchiguirinskaia

D Schertzer

& S Lovejoy

The Anisotropic Multifractal Model and Wind Turbine Wakes

Keywords: Universal Multifractals, Spectral Analysis, Wind Velocity Fluctuations and Power Estimation

INTRODUCTION

A typical routine in wind field resource assessment, at the most basic level, consists of first to third order statistics of times series data. The quality of the time series data can range between 0.05 to 600 seconds. More often than not the frequency of data will be the latter of the two since it is the cumulative power over long periods of time that define the financial return from turbines and thus high-resolution data is deemed unnecessary. It is now evident that such coarse time series data are no longer sufficient for a representative assessment of the wind and that estimations based on such data are associated with inaccurate power curve prediction and turbine damage. In particular it has been suggested that such problems are due to a lack of understanding of the somewhat intermittent nature of the wind velocity fields and the small-scale fluctuations thus associated. In order to address this there has been a significant increase in research involving coupled mesoscale-microscale models and stochastic downscaling methods. Our contribution is a demonstration that a good knowledge of small-scale variability is essential for a better understanding of the atmospheric boundary layer. We discuss the applicability of the stochastic anisotropic multifractal model to the complex conditions of wind farm potential and operational sites.

DATA

Available to us is six-months of wind velocity and temperature measurements at the heights 22, 23 and 43m. The measurements came from 3D sonic anemometers with a 10Hz data output rate positioned on a mast in a wind farm test site subject to wake turbulence effects (see Fig. 1). The quality of the data was of utmost importance so thorough pre-processing and verification was implemented to assure the reliability of the results.

ANALYSIS

The Energy Spectrum and Scaling

A typical first-step-method to determine the overall scaling behaviour is the transformation of the velocity field into Fourier space. We 'should' then be able to observe powerlaw behaviour of the spectrum such that

E(ω) ≡ Aω -β (1)
where ω is the frequency, E(ω) is the energy at a given frequency, A is a coefficient of proportionality and β is the scaling exponent. The review of [START_REF] Marusic | [END_REF] discusses the existence of a -1 power law sub-range over small frequencies, adjoined by a classical Kolmogorov inertial sub-range with β = 5/3. We will present shortly a more in-depth discussion on how our results compare to Kolmogorov's predictions however before this we would like to discuss the fact that there is no unique scaling regime i.e. there are three common scaling features, instead of the predicted universal law (see Figs. 2 and 3 also), that are:

• High frequency scaling range (R HF :∼ 0.1 secs to ∼5 mins) in which all three velocity components, u, v and w, follow (approximately) the same scaling law.

• Mid-frequency w-component departure from scaling at ∼5 minutes. Mid-Frequency, R MF , corresponds to the ranges ∼ 5 mins to ∼1 hour.

• Low frequency scaling reunification (R LF :∼ 1 hr to ∼1 day) for all three velocity components at about an hour. The power law is not the same as that for small scales as will be discussed later.

The focus therefore of our more in-depth analysis is the behaviour of the horizontal uand v-components over the midfrequency-ranges i.e. ∼5 mins to ∼1 day. In fact what we found was that our data fell into two categories; days (i.e., independent samples of 2 19 measurements [≈ 14.5 hours] per day) without a mid-frequency perturbation (Fig. 2) and days with a mid-frequency perturbation (Fig. 3). In the next section we will consider the simpler of the two regimes that are the non-perturbed days.

Non-perturbed Days & The Anisotropic Multifractal Model

The results from spectral analysis on non-perturbed days confirm a unique power law for all three velocity components over higher frequencies up to approximately 40 seconds at which the vertical wind w-component shows a clear scaling break followed by a -1 power law subrange as described in the previous section. Moreover, such a clear separation of power law subranges allows us to obtain an estimate of the integral length scale for the vertical wind component as suggested in [Monin & Yaglom, 1975], which in turn leads to an estimate of the Reynolds number of about 60,000. Thus, from dimensional analysis one may obtain a minimum Reynolds number of about 14,000. These estimates confirm that the investigated wind field exhibits fully developed turbulence. the velocity component u is blue, v is green and w is red. The high-frequency range from ∼ 0.1 sec to 5 mins has spectral slope ∼ 1.4, less than the predicted 5/3. In addition we have highlighted the -1 adjoining range, from 5 mins to an hour, with the scale break being predictable based on the mast height (see [START_REF] Fitton | [END_REF] for more details). Low frequency scaling region is compatible with the -11/5 scaling law.

Over the high-frequency range Fig. 3 displays spectral exponents that differ from Kolmogorov's -5/3 law. The difference corresponds to an intermittency correction of spectral slopes and can be taken into account using the universal multifractal framework (Schertzer and Lovejoy, 1987), where:

• the energy density flux is a conserved (at any scale ratio λ ) multifractal field proportional to a power law with singularity, γ, i.e.

ε λ ∝ λ γ , (2)
• the statistical moments of the energy density flux are defined by:

ε q λ ∝ λ K(q) , (3)
• and the scaling moment function K(q) is defined by:

K(q) = C 1 α -1 q α -q . (4)
Here, q, is the order of moment, C 1 is the codimension of the mean singularity and α is the multifractal Lévy index.

The spectral exponent of Eq. 1 now becomes

β = 2H + 1 -K(2) (5)
where H = 1/3 quantifies the degree of non-conservation of velocity increments. For spectra (i.e. for second order statistics), we estimated K(2) = 0.27. Such high intermittency corrections are expected over high frequencies in areas with high Reynolds numbers and complex terrain.

In addition we observed the Bolgiano-Obuhkov -11/5 power law at low frequencies illustrating the influence of largescale vertical motions specific to the topography of our wind farm test site [Faggio & Jolin, 2003].

To take into account the dominant role of the vertical motion of large scale atmospheric structures, one may consider that the buoyancy force variance flux, φ , plays the same role as the energy flux, ε, in 3D turbulence but only along the vertical [Schertzer & Lovejoy, 1984]. This is contrary to the classical 'buoyancy subrange' that postulates an isotropic turbulence [Bolgiano, 1959, Obukhov, 1959] with two different (horizontal and vertical) scaling regimes.

Thus we have the coupled sets of scaling equations [Schertzer & Lovejoy, 1984, Lazarev et. al., 1994]:

∆V (∆x) d = (ε(∆x)) 1/3 ∆x 1/3 ∆V (∆z) d = (φ (∆z)) 1/5 ∆x 3/5 (6) =⇒ (ε(∆x)) 1/3 ≈ (φ (∆z)) 1/5 when ∆x 1/3 ≈ ∆z 3/5 (7)
where ∆V (∆x) and ∆V (∆z) denote the horizontal and vertical shears of the horizontal wind respectively and the symbol d = means equality in probability distribution.

Because the scaling fluctuations of both fluxes are not neglected (due to their explicit scale dependency) we can define anisotropic scaling (as defined by the anisotropic multifractal model [Schertzer & Lovejoy, 1984]) at all significant scales instead of two isotropic regimes, separated by a scaling break (see [START_REF] Fitton | [END_REF] for more details).

Perturbed Days, Wakes and Power Estimation

In [START_REF] Fitton | [END_REF] we put forward the argument that the non-perturbed days were a result of lack of influence of wind turbines justified by the low frequency power law (crossdiagonal mean wind) of the integrated cospectral analysis.

The same argument allowed us to select days that were highly perturbed. By this we mean days where the midfrequency range, R MF , in which the scaling of horizontal velocity components remained the same as described in the previous section, now have significant fluttering (see below [Fig. 3]). The high-frequency range from ∼ 0.1 sec to 5 mins has spectral slope ∼ 1.6 which is much closer to the predicted 5/3. We have highlighted the fluttering for the horizontal components over R MF . We can also see the fluttering of the vertical component is accentuated to a plateau. The 11/5 low frequency scaling regime remains, although with a lower coefficient of proportionality A (Eq. 1).

To see the effect of the turbines we can do a direct comparison of the integrated spectra, ωE(ω), in log-linear coordinates of perturbed and non-perturbed days (11 of each see Fig. 4). This gives us a quantification of the energy per frequency increment making the overall evaluation of the energy gains and losses much easier. We have selected the horizontal u-component since there is no -1 adjoining range for nonperturbed days making it easier to make the comparison. Note the behaviour of the horizontal v-component is very similar (evidence of asymmetry at larger scales). From Fig. 4 we can draw the following intermediate conclusions based on the ranges defined in §3.1:

• High frequency scaling range (∼ 0.1 secs to ∼5 mins) has an injection of energy since perturbed days (blue integrated spectra, light-blue moving average in Fig. 4) have more energy than the unperturbed days (green integrated spectra, red moving average in Fig. 4). This is confirmed by the positive difference of the moving average of the integrated spectra (purple curve of Fig. 4). If we consider the most basic approximation to a turbine, the actuator disc, then we can assume any eddy larger than the disc will be split into smaller eddies. This may explain the increase in high frequency energy. In fact, we can further confirm this idea since the transition of energy peaks at ∼ 5 mins highlighted again in Fig. 4 correspond to the size of the wake shown in Fig. 1.

• Mid-frequency u-component (∼ 5 mins to ∼3 hours) shows evidence of energy pumping from the turbines for the perturbed days. This is more obvious when looking at the negative difference of the two integrated spectra over this range.

• Low frequency (∼ 3 hours to ∼ 1 day [mesoscales]) shows that although there is similar scaling behaviour the energy for the perturbed days (red curve) is greater than the non-perturbed (light-blue curve) since the difference of the two (purple line) is positive. In [START_REF] Fitton | [END_REF] we suggested this was because the two particular types of wind the site was typically subject were strong North-Westerlys and weak South-Easterlys. This meant only the stronger winds would interact with the turbines (see Fig. 1).

In addition we see at ∼ 3 hours the energy of the nonperturbed days becomes greater than perturbed. In the previous section we discussed how topographical features can change the scaling power law over the lower frequency data. This suggests there are similar topographical influences causing the loss of energy e.g. higher mean winds dissipate more energy over complex terrain.

Fig. 5 displays a schematic diagram that illustrates the corresponding inter-relations of different scaling ranges of the energy spectra. Over each of these ranges, two distinct power laws describe the corresponding scaling behaviour, with and without wake effects. Thus, from Eq. 5 we get:

E 1 (ω) = A 1 ω -β 1 , (8)
E 2 (ω) = A 2 ω -β 2 . ( 9
)
Since the estimates of the multifractality parameter, α, remain stable for both perturbed and non-perturbed fields, the ratio of the energy spectra is defined by the second order structure function:

E 1 (ω) E 2 (ω) = A 1 A 2 ω -ζ ∆ (2) (10)
where ζ ∆ = 2(∆H) -(∆C 1 /(α -1)) • (2 α -2) from Eqs. 4 and 5.

CONCLUSION

The aim of this study was to explore the scaling behaviour of atmospheric velocity measurements in a wind farm test site subject to wake turbulence effects. Based on this study we can make the following conclusions:

• Using long time series, 10Hz data, we identified (depending on the direction of the mean wind) two or three scaling sub-ranges.

• Through spectral analysis we found possible relations between wind velocity scaling breaks and associated theories of fully developed turbulence in the atmospheric surface-layer and used the universal multifractal framework to deal with the strong intermittency of the field.

• We have discussed how the anisotropic multifractal model can be applied to near wall atmospheric turbulence over complex terrain how it can be fully validated for days with no interaction with the wind turbine wakes.

• We found empirical evidence of the influence of wakes and suggested reasoning and scaling techniques that enable us to quantify the loss of energy with the potential of taking this into account using the anisotropic multifractal model.

• And finally, we discussed how the pumping of energy from wind turbines over mid-frequency scales, creates additional small-scale eddies which are re-injected as part of the energy over smaller scales. This makes the turbulence more homogeneous over the smaller scales in an analogous way to grid-generated homogeneous turbulence.

Figure 1 :

 1 Figure 1: Schematic of turbine positions and wake effect due to North-Westerly winds (map courtesy of Julien Richard).

Figure 2 :

 2 Figure 2: Averaged spectra for 11 non-perturbed days where

Figure 3 :

 3 Figure3: Averaged spectra for 11 perturbed days where the velocity component u is blue, v is green and w is red. The high-frequency range from ∼ 0.1 sec to 5 mins has spectral slope ∼ 1.6 which is much closer to the predicted 5/3. We have highlighted the fluttering for the horizontal components over R MF . We can also see the fluttering of the vertical component is accentuated to a plateau. The 11/5 low frequency scaling regime remains, although with a lower coefficient of proportionality A (Eq. 1).

Figure 4 :

 4 Figure4: Comparison of perturbed and non-perturbed, ucomponent averaged integrated spectra, ωE(ω), in loglinear coordinates; blue is perturbed days with lightblue moving average, green is non-perturbed with red moving average and purple is the differences of the moving averages.

Figure 5 :

 5 Figure 5: Schematic of the inter-relations of different scaling ranges of the energy spectra in a log-log plot.