Martin Averseng

New preconditioners for Laplace and Helmholtz integral equations on open curves II. Theoretical analysis

This paper is the second part of a work on Laplace and Helmholtz integral equations in 2 space dimensions on open curves. A new Galerkin method in weighted L 2 spaces together with new preconditioners for the weighted layer potentials are studied. This second part provides the theoretical analysis needed to establish the results announced in the first part. The main novelty is the introduction of a pseudo-differential calculus on open curves that allows to build parametrices for the weighted layer potentials. Contrarily to more classical approaches where the Mellin transform is used, this new approach is well-suited to the specific singularities that appear in the problem.

Introduction

We are concerned with the numerical resolution of the problems of Helmholtz and Laplace scattering by open curves in the plane, with Dirichlet or Neumann boundary data. In the first part of this work [START_REF] Alouges | New preconditioners for Laplace and Helmholtz integral equation on open curves: I. Analytical framework and numerical results[END_REF], after recasting the classical first-kind integral equations into a form involving weighted versions of the usual layer potentials, the authors have introduced a Galerkin method in weighted L 2 spaces and some new efficient preconditioners for the resulting linear systems. A discussion on existing literature and the relation of this method to other works can be found in [START_REF] Alouges | New preconditioners for Laplace and Helmholtz integral equation on open curves: I. Analytical framework and numerical results[END_REF]. This second part is devoted to the mathematical analysis of the method. More precisely, on the one hand, we establish the announced optimal orders of convergence for the Galerkin method, and on the other hand, we analyze the parametrices for the weighted layer potentials that underlie the construction of the preconditioners. This involves the introduction of two classes of pseudo-differential operators on open curves with an associated symbolic calculus, transported from the usual pseudo-differential calculus available on 1 the torus [START_REF] Turunen | On symbol analysis of periodic pseudodifferential operators[END_REF]. The way we deal with the singularity of the change of variable is new, to the best of our knowledge. The resulting classes of operator are particularly simple, enjoy all the usual pseudo-differential properties and could therefore present an interest in other contexts.

The outline is as follows. In the first section, we define two scales of interpolating Hilbert spaces, T s and U s and analyze their properties. Some of this analysis is applied in the second section to establish the optimal orders of convergence of the Galerkin method. In the third section, we introduce the new classes pseudo-differential operators on open curves, respectively in the scales T s and U s . This allows us analyze the parametrices for the weighted layer potentials in the fourth and last section.

Remark 1. Throughout all this article, we use repeatedly the letter C in estimates of the form a ≤ Cb. From line to line, the value of the constant C may change but is independent of the relevant parameters defining a and b.

Spaces T s and U s

All the analysis of this work takes place in two interpolating scales of Hilbert spaces T s and U s that we define now, before establishing some of their properties.

Definitions

The Chebyshev polynomials of first and second kinds (see e.g. the book [START_REF] Mason | Chebyshev polynomials[END_REF]) are respectively given by T n (x) = cos(n arccos(x)), U n (x) = sin((n + 1) arccos(x))

√ 1 -x 2
for x ∈ [-1, 1] and n ∈ N. Letting ∂ x the derivation operator and ω the operator u(x) → ω(x)u(x) with ω(x) = √ 1 -x2 , T n and U n satisfy the following identities:

-(ω∂ x ) 2 T n = n 2 T n , (1)
-(∂ x ω) 2 U n = (n + 1) 2 U n . ( 2
)
Notice that here and in the following, ∂ x ω denotes the composition of operators ∂ x and ω and not the function x → ∂ x ω(x). One can also check the identities

∂ x T n = nU n-1 , (3)
-ω∂ x ωU n = (n + 1)T n+1 .

(

) 4
The first one is obtained for example from the definition of T n , from which we deduce the second one after using -(ω∂ x ) 2 T n+1 = (n + 1) 2 T n+1 .

Both T n and U n are polynomials of degree n, and provide respectively a basis of the following Hilbert spaces

L 2 1 ω := u ∈ L 1 loc (-1, 1) 1 -1 |u(x)| L 2 ω := u ∈ L 1 loc (-1, 1) 1 -1 |u(x)| 2 1 -x 2 dx < +∞ .
Following the notations of [START_REF] Mclean | Strongly elliptic systems and boundary integral equations Cambridge university press[END_REF], we denote the Banach duality products of L 2

(u, v) 1 ω = u, v 1 ω := 1 π 1 -1 u(x)v(x) ω(x) dx , (u, v) ω = u, v ω := 1 π 1 -1 u(x)v(x)ω(x)dx .
The Chebyshev polynomials satisfy

(T n , T m ) 1 ω =    0 if n = m, 1 if m = n = 0, 1/2 otherwise, (5)
and

(U n , U m ) ω = 0 if n = m, 1/2 otherwise, (6)
from which we obtain the so-called Fourier-Chebyshev decomposition: any u ∈ L 2

1 ω can be decomposed through the first kind Chebyshev series

u(x) = +∞ n=0 ûn T n (x) , (7)
where the Fourier-Chebyshev coefficients of the first kind are given by ûn = (u,

T n ) 1 ω (T n , T n ) 1 ω
and satisfy the Parseval equality

∀(u, v) ∈ L 2 1 ω (u, v) 1 ω = û0 v0 + 1 2 +∞ n=1 ûn vn .
When u is furthermore a smooth function, one can check that the series [START_REF] Wendland | A hypersingular boundary integral method for two-dimensional screen and crack problems[END_REF] converges uniformly to u. Similarly, any function v ∈ L 2 ω can be decomposed along the (U n ) n as

v(x) = +∞ n=0 vn U n (x)
where the Fourier-Chebyshev coefficients of the second kind vn are given by vn The preceding analysis can be used to define Sobolev-like spaces.

:= (v, U n ) ω (U n , U n ) ω
Definition 1. We define T s as the set of (formal) series

u = n∈N ûn T n
where the coefficients ûn satisfy n∈N

(1 + n 2 ) s |û n | 2 < +∞ .
Let T ∞ = ∩ s≥0 T s and T -∞ = ∪ s∈R T s . For u ∈ T s when s ≥ 0, the series defining u converges in L 2

1 ω and the Fourier-Chebysehv coefficients of the first kind of u coincide with ûn , allowing to identify T s to a subspace of L 2

1 ω with

T 0 = L 2 1 ω
. For all u ∈ T s , we define the linear form u,

• 1 ω by ∀ϕ ∈ T ∞ , u, ϕ 1 ω = 1 2 û0 φ0 + 1 2 +∞ n=1 ûn φn . ( 8
)
This linear form has a unique continuous extension on T -s , and the dual of T s is the set of linear forms u, • 1 ω where u ∈ T -s . Endowed with the scalar product

(u, v) T s := û0 v0 + 1 2 +∞ n=1 (1 + n 2 ) s ûn vn ,
T s is a Hilbert space for all s. A homogeneous semi-norm on T s can be defined as

|u| 2 T s := 1 2 +∞ n=1 n 2s |û n | 2 .
Definition 2. In a similar fashion, we define U s as the set of formal series

u = n∈N ǔn U n
where the coefficients ǔn satisfy n∈N

(1 + n 2 ) s |ǔ n | 2 < +∞ . Let U ∞ = ∩ s∈R U s and U -∞ = ∪ s∈R U s .
For u ∈ U s when s ≥ 0, the series defining u converges in L 2 ω and the Fourier-Chebyshev coefficients of the second kind of u coincide with ǔn , allowing to identify U s to a subspace of L 2 ω with U 0 = L 2 ω . For all u ∈ U s , we define the linear form u,

• ω by ∀ϕ ∈ U ∞ , u, ϕ ω := 1 2 +∞ n=0 φn ǔn . ( 9
)
This linear form has a unique continuous extension on U -s , and the dual of U s may be identified to U -s with respect to the bilinear form •, • ω . Endowed with the scalar product

(u, v) U s := 1 2 n∈N 1 + (n + 1) 2 s ǔn vn , U s is a Hilbert space for all s ∈ R. Let s 1 , s 2 ∈ R , θ ∈ (0, 1) and let s = θs 1 + (1 -θ)s 2 . It is easy to check that ∀u ∈ T ∞ , u T s ≤ u θ T s 1 u 1-θ T s 2 and ∀u ∈ U ∞ , u U s ≤ u θ U s 1 u 1-θ U s 2 .
Therefore, (T s ) s∈R and (U s ) s∈R are exact interpolation scales.

Basic properties

Links with smooth functions and continuous inclusions For any real s, if u ∈ T s , the sequence of polynomials

u N (x) = N n=0 ûn T n (x)
converges to u in T s . The same assertion holds for u ∈ U s when T n is replaced by U n . Therefore:

Lemma 1. C ∞ ([-1, 1]) is dense in T s and U s for all s ∈ R.
The polynomials T n and U n are connected by the following formulas:

T 0 = U 0 , T 1 = U 1 2 , and ∀n ≥ 2, T n = 1 2 (U n -U n-2 ) , ( 10
) ∀n ∈ N, U 2n = 2 n j=0 T 2j -1, U 2n+1 = 2 n j=0 T 2j+1 . ( 11
)
This leads us to introduce the map

I : T ∞ → U ∞ defined by Iϕ 0 = φ0 - φ2 2 , Iϕ j = φj -φj+2 2 for j ≥ 1.
I is bijective has the explicit inverse

I -1 ϕ 0 = +∞ n=0 φ2n , I -1 ϕ j = 2 +∞ n=0 φj+2n for j ≥ 1.
Lemma 2. For all real s, I has a unique continuous extension from T s to U s and for s > 1 2 , I -1 has a continuous extension from U s to T s-1 .

Before starting the proof, we introduce the Cesàro operator C defined on l 2 (N * ) by

(Cu) n = 1 n n k=1 u k .
As is well-known, this is a linear continuous operator on the Hilbert space l 2 (N * ). Its adjoint

(C * u) n = +∞ k=n u k k ,
is therefore also continuous on l 2 (N * ). In other words, for all (u n ) n ∈ l 2 (N),

+∞ n=1 +∞ k=n u k k 2 ≤ C +∞ k=1 u 2 k .
Proof. The first result is immediate from the definition of T s , U s and I. When u ∈ U s for s > 1/2, the series

|ǔ n | is converging thus I -1 u is well defined. By definition, u ∈ U s means that the sequence (1 + n 2 ) s/2 |ǔ n | n≥1 is in l 2 (N * ).
Thus, using the continuity of the adjoint of the Cesàro operator mentioned previously, the sequence (r n ) n defined by

∀n ≥ 0, r n := +∞ k=n (1 + k 2 ) s-1 2 |ǔ k |
is in l 2 (N) with a l 2 norm bounded by u U s . We now write

I -1 u 2 T s-1 = +∞ n=0 (1 + n 2 ) s-1 I -1 u n 2 ≤ 4 +∞ n=0 (1 + n 2 ) s-1 +∞ k=n |ǔ k | 2 ≤ 4 +∞ n=0 +∞ k=n (1 + k 2 ) s-1 2 |ǔ k |) 2 = 4 (r n ) n 2 l 2 .
We saw that the last quantity is controlled by u 2 U s so the result is proved.

Let

u = n∈N ûn T n , v = n∈N vn U n .
When Iu = v, we identify u and v. The previous results have shown that this identification is compatible with the equality of functions in L 2

1 ω
or L 2 ω . The mapping I is then the identity mapping and its properties just established can be rephrased as follows.

Corollary 1. For all s ∈ R, T s ⊂ U s and for all s > 1 2 , U s ⊂ T s-1 with continuous inclusions.

One immediate consequence of the previous result is that T ∞ = U ∞ . Moreover, there holds Lemma 3.

T ∞ = C ∞ ([-1, 1]) . Proof. If u ∈ C ∞ ([-1, 1]
), then we can obtain by induction using integration by parts and (1), that for any

k ∈ N ûn = (-1) k n 2k 1 -1 (ω∂ x ) 2k u(x)T n (x) ω(x) dx.
Noting that (ω∂

x ) 2 = (1 -x 2 )∂ 2 x -x∂ x , the function (ω∂ x ) 2k u is C ∞ ,
and since T n ∞ = 1, the integral is bounded independently of n. Thus, the coefficients ûn have a fast decay, proving that

C ∞ ([-1, 1]) ⊂ T ∞ .
For the converse inclusion, if u ∈ T ∞ , the series

u(x) = n=0 ûn T n (x) is normally converging since T n ∞ = 1, so that u is a continuous function. This proves T ∞ ⊂ C 0 ([-1, 1]
). It now suffices to show that ∂ x u ∈ T ∞ and apply an induction argument. Applying term by term differentiation, since

∂ x T n = nU n-1 for all n (with the convention U -1 = 0), ∂ x u(x) = +∞ n=1 nû n U n-1 (x). Therefore, ∂ x u is in U ∞ = T ∞ which proves the result.
The next result shows that nothing that can be done about the case s ≤ 1 2 : Lemma 4. For s ≤ 1 2 , the functions of U s cannot be identified to functions in

T -∞ . Proof. Let s ≤ 1 2
, and let us assume by contradiction that the functions of U s can be identified to elements of T -∞ . Then, there must exist a continuous map

I from U s to T -∞ with the property ∀u ∈ C ∞ ([-1, 1]), Iu = u.
We introduce the function u defined by ǔn =

1 n ln(n) . One can check that u ∈ U 1 2 ⊂ U s , thus Iu must be element of T -∞ . For all N , the function u N = N n=0 ǔn U n is in U ∞ and (u N ) N ∈N converges to u in U s . By continuity of I, the sequence ( Iu N , T 0 1 ω ) N ∈N must converge with limit Iu, T 0 1 ω . But since Iu N = u N , Iu N , T 0 1 ω = u N , T 0 1 ω = N n=0 ǔn U n , T 0 1 ω = N 2 k=0 1 2k ln(2k) ,
where, in the last equality, we have used the identity

U n , T 0 1 ω = 1 if n is even , 0 otherwise .
which can be checked for example using eq. ( 11). The last sum diverges to +∞ when N goes to infinity, giving the contradiction.

Lemma 5. For all ε > 0, if u ∈ T 1 2 +ε , then u is continuous and

∃C : ∀x ∈ [-1, 1], |u(x)| ≤ C u T 1/2+ε .
Similarly, if u ∈ U 3/2+ε , then u is continuous and

∃C : ∀x ∈ [-1, 1], |u(x)| ≤ C u U 3/2+ε . Proof. Let x ∈ [-1, 1]. Using triangular inequality, |u(x)| ≤ +∞ n=0 |û n |
since for all n, T n L ∞ = 1. Applying Cauchy-Schwarz's inequality, one gets

|u(x)| ≤ +∞ n=0 1 (1 + n 2 ) 1 2 +ε u T 1 2 +ε .
The second statement is deduced from the first and the continuous inclusion U s ⊂ T s-1 stated in Corollary 1.

Derivation operators

We now extend the definition of the derivation operators ∂ x and ω∂ x ω appearing in eqs (3) and (4). Lemma 6. For all real s, the operator ∂ x can be extended into a continuous map from T s+1 to U s defined by

∀v ∈ C ∞ ([-1, 1]), ∂ x u, v ω := -u, ω∂ x ωv 1 ω .
In a similar fashion, the operator ω∂ x ω can be extended into a continuous map from U s+1 to T s defined by

∀v ∈ C ∞ ([-1, 1]), ω∂ x ωu, v 1 ω := -u, ∂ x v ω .
Proof. Using eqs (3) and ( 4), one can check that the formulas indeed extend the usual definition of both operators for smooth functions. We now show that the map ∂ x extended this way is continuous from

T s+1 to U s . The definition ∀v ∈ U ∞ , ∂ x u, v ω := -u, ω∂ x ωv 1 ω gives a sense to ∂ x u for all u in T -∞ , as a duality T -∞ ×T ∞ product, because if v ∈ U ∞ (= C ∞ ([-1, 1]), then ω∂ x ωv = (1-x 2 )v -xv also lies in C ∞ ([-1, 1])(= T ∞ ). Letting w = ∂ x u, we have by definition for all n wn = w, U n ω = -u, ω∂ x ωU n 1 ω = n u, T n+1 1 ω = nû n+1 .
This implies the announced continuity with

w U s ≤ u T s+1 .
The properties of ω∂ x ω on T s are established similarly.

Corollary 2. The operator ∂ x is continuous from T s+2 to T s for all s > -1/2 and from U s+2 to U s for all s > -3/2. On the other hand, ω∂ x ω is continuous from T s+1 to T s and from U s+1 to U s for all s ∈ R.

Proof. For the continuity of ∂ x from T s+2 to T s , we use the continuity of ∂ x from T s+2 to U s+1 and then of the identity from U s+1 to T s . For the continuity of ∂ x from U s+2 to U s , we use the same arguments in reverse order.

On the other hand, we have, for n ≥ 2,

ω∂ x ωT n = ω∂ x ω U n -U n-2 2 = (n + 1)T n+1 -(n -1)T n-1 2 .
Therefore ω∂ x ω is continuous from T s+1 to T s . Finally, ω∂ x ω is continuous from U s+1 to T s and the inclusion T s ⊂ U s is continuous thus ω∂ x ω is continuous from U s+1 to U s .

Equivalent norms on T n and U n

We now provide a characterization of the spaces T n and U n in terms of weighted L 2 norms of the derivatives and give equivalent norms on those spaces when n is an integer. This is done by studying the properties of the operators (ω∂ x ) n and (∂ x ω) n . The main results are propositions 1 and 2.

Lemma 7. The operator ω is a bijective isometry from U 0 to T 0 with inverse

1 ω .
Proof. This result follows from

ωu 2 1 ω = 1 π 1 -1 |(ωu)| 2 ω = 1 π 1 -1 ω |u| 2 = u 2 ω , valid for all u ∈ L 2 ω .
Combining this with the continuity of ∂ x from T 1 to U 0 and of ω∂ x ω from U 1 to T 0 (see Lemma 6) we obtain:

Corollary 3. The operators ω∂ x : T 1 → T 0 and ∂ x ω : U 1 → U 0 are continuous.
Note however that those two operators do not send smooth functions to smooth functions so we cannot expect a continuity of the form

∀s ∈ R, ω∂ x : T s → T s-1 .
For this reason, in the analysis of (ω∂ x ) n and (∂ x ω) n , we must treat separately the cases of an even or odd integer n. Definition 3. For an even integer n, the operator

(ω∂ x ) n : T -∞ → T -∞ is defined by (ω∂ x ) 0 = I d , ∀k > 0, (ω∂ x ) 2k := (ω∂ x ω)∂ x (ω∂ x ) 2k-2 .
The operator (∂ x ω) n : U -∞ → U -∞ is defined in an analogous way. Lemma 8. Let n an even integer. For all s ∈ R, (ω∂ x ) n is continuous from

T s to T s-n and (∂ x ω) n is continuous from U s to U s-n .
Proof. Those results follow from the definition of the operators and by induction using the mapping properties of ∂ x and ω∂ x ω established in Lemma 6. Definition 4. For an odd integer n, the operator (ω∂ x ) n : T n → T 0 is defined by

(ω∂ x ) n := ω∂ x (ω∂ x ) n-1 .
The operator (∂ x ω) n : U n → U 0 is defined in an analogous way.

Using Corollary 3, one can show:

Corollary 4. The operators (ω∂ x ) n and (∂ x ω) n are well defined and continuous respectively from T n to T 0 and from U n to U 0 .

Proposition 1. Let n ∈ N. If n is even, T n = u ∈ L 2 1 ω (ω∂ x ) n u ∈ L 2 1 ω . If n is odd, T n = u ∈ L 2 1 ω ∂ x (ω∂ x ) n-1 u ∈ L 2 ω . Moreover u → u 2 1 ω + (ω∂ x ) n u 2 1 ω
defines an equivalent norm on T n , and for all u ∈ T n , |u|

T n = (ω∂ x ) n u L 2 1 ω
.

Proof. The direct inclusions follow from the mapping properties established in Lemma 6, Lemma 8 and Corollary 4. For the converse inclusions, let u in L 2

1 ω . If n is even, say n = 2k, the assumption is that (ω∂ x ) n u ∈ L 2 1 ω . The Fourier- Chebyshev coefficients of a = (ω∂ x ) n u are given for j > 0 by âj = (ω∂ x ) 2k u(x), T j 1 ω (T n , T n ) 1 ω = u(x), (ω∂ x ) 2k T j 1 ω (T n , T n ) 1 ω = (-1) k j 2k ûj .
while for j = 0, âj = 0. Applying Parseval's equality to the function a, this gives 1 2

j>0 j 2n |û j | 2 = (ω∂ x ) n u 2 1 ω . ( 12
)
On the other hand, if n is odd,

say n = 2k + 1, let b := ∂ x (ω∂ x ) 2k u.
The assumption is now that b ∈ L 2 ω , and by Lemma 7, ωb (= (ω∂ x ) n u) ∈ T 0 with

ωb 1 ω = (ω∂ x ) n u 1 ω = b ω . One can write bj = 2 ∂ x (ω∂ x ) 2k u, U j = -2 u, (ω∂ x ) 2k (ω∂ x ω)U j .
Using -ω∂ x ωU j = (j + 1)T j+1 , we obtain bj = (-1) k (j + 1) 2k+1 ûj+1 .

Parseval's equality then implies that (12) also holds for odd n. This establishes that u ∈ T n and |u|

T n = (ω∂ x ) n u 1 ω
. For the norm equivalence, adding the Parseval equality for u ∈ L 2 1 ω to (12), we get

|û 0 | 2 + 1 2 j>0 (1 + j 2n ) |û j | 2 = u 2 1 ω + (ω∂ x ) n u 2 1 ω . ( 13
)
There are two constants c and C such that c(1

+ j 2 ) n ≤ (1 + j 2n ) ≤ C(1 + j 2 ) n .
Injecting this in (13), we obtain

c 2 u 2 T n ≤ u 2 1 ω + (ω∂ x ) n u 2 1 ω ≤ C u 2 T n ,
and the equivalence of the norms follows.

Proposition 2. Let n ∈ N. If n is even, then U n = u ∈ L 2 ω (∂ x ω) n u ∈ L 2 ω . If n is odd, then U n = u ∈ L 2 ω ω∂ x ω(∂ x ω) n-1 u ∈ L 2 1 ω . Moreover, u → 1 -1 ω|(∂ x ω) n u| 2 defines an equivalent norm on U n .
Proof. The direct inclusions follow from the mapping properties established in Lemma 6, Lemma 8 and Corollary 4. For the converse inclusion, if n is even, let a = (∂ x ω) n u, we assume that a ∈ L 2 ω . One has ǎj = (-1) k (1 + j) n ǔj , so, by Parseval's equality,

1 2 +∞ j=0 (j + 1) 2n |ǔ j | 2 = (∂ x ω) n u 2 ω . ( 14
) If n is odd, the assumption is that b = ω∂ x ω(∂ x ω) n-1 u is in L 2 1 ω
. By calculations similar to those in the proof of the preceding lemma, we find that for j > 0, bj = j 2n ǔj-1 .

while b0 = 0. By Lemma 7, b ω (= (∂ x ω) n u) ∈ U 0 . Applying Parseval's equality to b in L 2 1 ω and using b ω ω = b 1 ω
, we find that (14) also holds when n is odd, and thus the inclusion is proved. Finally, there exists two constants c and C such that for all j ∈ N,

c(1 + (j + 1)) 2n ≤ (j + 1) 2n ≤ C(1 + (j + 1)) 2n .
This implies the equivalence of the norms.

Link with Periodic Sobolev spaces

In this paragraph, we show how the spaces T s and U s are related to Sobolev spaces of periodic even and odd functions respectively through the change of variables x = cos θ. The main result is Proposition 3.

We briefly recall here the definition of the periodic Sobolev spaces on the torus T 2π := R/2πZ. A smooth function u on T 2π can be decomposed in Fourier series

u(θ) = n∈Z Fu(n)e inθ
with the Fourier coefficients defined by

Fu(n) := 1 2π π -π u(θ)e -inθ dθ.
For n ∈ Z, let e n : θ → e inθ . We define the Fourier coefficients of any periodic distribution u on T 2π , by Fu(n) := u, e -n . For all s, the space H s is the set of periodic distributions on T 2π for which

u 2 H s := n∈Z (1 + n 2 ) s |Fu(n)| 2 < +∞ .
Introducing the duality product

u, v T2π = n∈Z Fu(n)Fv(-n) , (15)
H -s is identified to the dual of H s and

H 0 = L 2 (T 2π ). For u, v ∈ H 0 , u, v T2π = 1 2π π -π u(x)v(x)dx.
The space H s is the direct sum H s e ⊕ H s o where

H s e := {u ∈ H s | Fu(n) = Fu(-n)} , H s o := {u ∈ H s | Fu(n) = -Fu(-n)} . Note that when u is continuous, u ∈ H s e ⇐⇒ ∀θ ∈ T 2π , u(-θ) = u(θ) , u ∈ H s o ⇐⇒ ∀θ ∈ T 2π , u(-θ) = -u(θ) . Definition 5. We define the operators C : T -∞ → H -∞ e by ∀n ∈ Z, F(Cu)(n) = û0 if n = 0, û|n| 2
otherwise, and S :

U -∞ → H -∞ o by ∀n ∈ Z, F(Su)(n) = 0 if n = 0, sign(n) û|n|-1 2 otherwise.
Lemma 9. The operators C and S map smooth functions to smooth functions. For all

(u, v) ∈ T -∞ × T ∞ , u, v 1 ω = Cu, Cv T2π . For all (u, v) ∈ U -∞ × U ∞ , u, v ω = Su, Sv T2π .
Proof. The first assertion is obvious from the definition of C and S. 8) and (15),

Let (u, v) ∈ T -∞ × T ∞ . By definition of •, • 1 ω and •, • T2π eqs. (
Cu, Cv T2π = n∈Z F(Cu)(n)F(Cv)(-n) = û0 v0 + n∈Z,n =0 û|n| 2 v|n| 2 = û0 v0 + 1 2 +∞ n=1 ûn vn = u, v 1 ω .
.

The second identity is proved similarly.

Proposition 3. For all s ∈ R, the operators C and S induce bijective isometries respectively from T s to H s e and from U s to H s o . Additionally, for u ∈ T s ,

|u| T s = |Cu| H s . ( 16
) For u ∈ C ∞ ([-1, 1]), Cu(θ) = u(cos θ) and Su(θ) = sin θ u(cos θ) . ( 17
) Let v e , v o ∈ C ∞ (T 2π
), an even and an odd function respectively. Then

C -1 v e (x) = v e (arccos x) and S -1 v o (x) = v o (arccos x) ω(x) . ( 18
)
Proof. Let J T s , J U s and J H s the linear continuous mappings defined respectively on T -∞ , U -∞ and H -∞ by

J T s T n = (1 + n 2 ) s 2 T n , J U s U n-1 = (1 + n 2 ) s 2 U n-1 , J H s e n = (1 + n 2 ) s 2 e n .
By definition, for u ∈ T s and v ∈ U s ,

u 2 T s = J T s u, J T s u 1 ω and v 2 U s = J U s v, J U s v ω , while for w ∈ H s , w 2 H s = J H s w, J H s w T2π .
Moreover, notice that

CJ T s = J H s C, SJ U s = J H s S .
The isometric property of C may now be deduced from Lemma 9 as follows. Let

u N = N n=0
u n T n . There holds

J T s u, J T s u N 1 ω = CJ T s u, CJ T s u N T2π = J H s Cu, J H s Cu N T2π .
Sending N to infinity, by continuity of J T s , J H s and C, this yields

u 2 T s = Cu 2 H s .
The property (16) and the isometric property of S are established in a similar manner. Let us now prove eq. ( 17). For the first identity, consider some smooth function u on [-1, 1]. Since Cu is smooth, the Fourier series of Cu converges pointwise to Cu. Thus, for all θ ∈ T 2π ,

Cu(θ) = n∈Z F(Cu)(n)e inθ = û0 + n∈Z,n =0 û|n| 2 e inθ = û0 + 1 2 +∞ n=1 ûn e inθ + e -inθ = +∞ n=0 ûn T n (cos θ) .
The last sum also converges pointwise to u(cos θ) since u ∈ T ∞ . Similar calculations show that Su(θ) = sin θ u(cos θ). To prove the bijectivity of S and C, one can check that they have the explicit inverses C -1 and S -1 respectively defined on H s e and H s o by

∀n ∈ N, (C -1 u) n = Fu(0) if n = 0, 2Fu(n) otherwise, and ∀n ∈ N, (S -1 u) n = 2Fu(n + 1) .
Finally, identities (18) are simply deduced by inverting (17).

Generalization to a curve

All of the previous analysis can be generalized to define two families of spaces T s (Γ) and U s (Γ) of functions defined on a smooth curve Γ by means of a C ∞ diffeomorphism.

Parametrization of the curve

We now introduce some notation that will be used at several points in the remainder of this work.

Let Γ a smooth open curve in R 2 parametrized by a C ∞ diffeomorphism r : [-1, 1] → Γ. We assume that |r (x)| = |Γ| 2 for all x ∈ [-1, 1],
where |Γ| is the length of Γ. This parametrization is related to the curvilinear abscissa M (s) through

r(x) = M |Γ| 2 (1 + x) . Let R : C ∞ (Γ) -→ C ∞ ([-1, 1]) defined by Ru(x) = u(r(x)) .
The tangent and normal vectors on the curve, τ and n, are respectively defined by

τ (x) = ∂ x r(x) |∂ x r(x)| , n(x) = ∂ x τ (x) |∂ x τ (x)| . Let N : Γ → R 2 such that N (r(x)) = n(x), that is, N = R -1 n. Let κ(x) the signed curvature of Γ at the point r(x). Frenet-Serret's formulas give r(y) = r(x) + (y -x) |Γ| 2 τ (x) + (y -x) 2 2 |Γ| 2 4 κ(x)n(x) + (x -y) 3 6 |Γ| 3 8 (κ (x)n(x) -κ(x) 2 τ (x)) + O (x -y) 4 , so that |r(x) -r(y)| 2 = |Γ| 2 4 (y -x) 2 - (y -x) 4 192 |Γ| 4 κ(x) 2 + O(x -y) 5 . ( 19
)
For u, v ∈ L 2 (Γ), we have by change of variables in the integral

u, v L 2 (Γ) = |Γ| 2 Ru, Rv L 2 (-1,1) .
The tangential derivative ∂ τ on Γ satisfies

∂ τ = 2 |Γ| R -1 ∂ x R . ( 20
)
We also define a "weight" on the curve as

ω Γ := |Γ| 2 R -1 ωR . ( 21
)
Finally, the uniform measure on Γ is denoted by dσ.

Spaces T s (Γ) and U s (Γ)
The definition of the spaces T s can be transported on the curve Γ, replacing the basis (T n ) n and (U n ) n by (R -1 T n ) n and (R -1 U n ) n . The spaces T s (Γ) and U s (Γ) are thus defined as the sets of formal series respectively of the form

u = n∈N ûn R -1 T n , v = n∈N vn R -1 U n ,
where Ru = ûn T n ∈ T s and Rv = vn U n ∈ U s . To u and v are associated the linear forms

∀ϕ ∈ C ∞ (Γ), u, ϕ 1 ω Γ := Ru, Rϕ 1 ω , ∀ϕ ∈ C ∞ (Γ), v, ϕ ω Γ := |Γ| 2 4
Rv, Rϕ ω .

The results of the previous section are easily extended to this new setting:

Lemma 10. For all s ∈ R, T s (Γ) and U s (Γ) are Hilbert spaces for the scalar products

(u, v) T s (Γ) = (Ru, Rv) T s , (u, v) U s (Γ) = |Γ| 2 2 (Ru, Rv) U s .
With these definitions,

(u, v) T 0 (Γ) = u, v 1 ω Γ = Γ u(x)v(x) ω Γ (x) dx , (u, v) U 0 (Γ) = u, v ω Γ = Γ ω Γ (x)u(x)v(x)dx . In particular T 0 (Γ) = L 2 1 ω Γ and U 0 (Γ) = L 2 ω Γ . For s ∈ R, the dual of T s (Γ) is the set of linear forms u, • 1 ω Γ
where u ∈ T -s (Γ), and the dual of U s (Γ) is the set of linear forms u, • ω Γ where u ∈ U -s (Γ). For s < t, the injections T t (Γ) ⊂ T s (Γ) and U t (Γ) ⊂ U s (Γ) are compact. (T s (Γ)) s∈R and (U s (Γ)) s∈R are two Hilbert interpolation scales. For an integer n, equivalent scalar products on T n (Γ) and U n (Γ) are given respectively by

(u, v) → Γ u(x)v(x) + (ω Γ ∂ τ ) n u(x)(ω Γ ∂ τ ) n v(x) ω Γ (x) dσ(x) , (u, v) → Γ (∂ τ ω Γ ) n u(x)(∂ τ ω Γ ∂) n v(x)ω Γ (x)dσ(x) . For all s ∈ R, T s (Γ) ⊂ U s (Γ) and for all s > 1 2 , U s (Γ) ⊂ T s-1 (Γ) with continuous inclusions. For ε > 0, T 1/2+ε (Γ) ⊂ C 0 (Γ) and U 3/2+ε ⊂ C 0 (Γ) with continuous inclusions. Finally, T ∞ (Γ) = U ∞ (Γ) = C ∞ (Γ).

Weighted Galerkin method for the problem of scattering by open curves

In this section, we present the first-kind integral equations arising in the study of wave scattering by open curves with Dirichlet or Neumann conditions and introduce the weighted layer potentials. We then apply the theory of the first section to the analysis of the Galerkin method described in [START_REF] Alouges | New preconditioners for Laplace and Helmholtz integral equation on open curves: I. Analytical framework and numerical results[END_REF] in the case of a zero wavenumber and flat geometry (this can be extended to the general case by standard perturbation arguments).

First-kind integral equations

Recall the definition and parametrization of the curve Γ detailed in section 1.5. We consider the following boundary integral equations (BIEs)

S k λ = u D , N k µ = u N , ( 22
)
where S k and N k are respectively the single-layer and hypersingular operators.

We refer the reader to [START_REF] Alouges | New preconditioners for Laplace and Helmholtz integral equation on open curves: I. Analytical framework and numerical results[END_REF] and references therein for more details on the connection between eqs. ( 22) and the problem of wave scattering by the curve Γ. The operators S k and N k admit the integral representations

(S k λ)(x) = Γ G k (x -y)λ(y)dσ(y) , (N k µ)(x) = lim ε→0 + Γ N (y) • ∇G k (x + εN (x) -y)µ(y)dσ y . ( 23
)
for x ∈ Γ, with the Green function G k defined by

     G 0 (z) = - 1 2π ln |z| , if k = 0, G k (z) = i 4 H 0 (k|z|), if k > 0, (24)
where H 0 is the Hankel function of the first kind. It is known that S k maps continuously H-1/2 (Γ) to H 1/2 (Γ) [7, Theorem 1.8] and N k maps continuously H1/2 (Γ) to H -1/2 (Γ) [START_REF] Wendland | A hypersingular boundary integral method for two-dimensional screen and crack problems[END_REF]Theorem 1.4]. In the case k = 0, the Helmholtz scattering reduces to the Laplace problem. The kernel of the hypersingular operator has a non-integrable singularity, but computations are facilitated by the following formula, valid for smooth functions µ and ν that vanish at the extremities of Γ:

N k µ, ν = Γ×Γ G k (x -y)∂ τ µ(x)∂ τ ν(y) -k 2 G k (x, y)µ(x)∂ ν (y)n(x) • n(y)dσ(x)dσ(y) . ( 25
)
For the geometry under consideration, the solutions λ and µ of the BIEs (22) have singularities (even for C ∞ data u D and u N ) due to the edges of the scatterer. It is now classical to introduce weighted versions of the usual layer potentials, known to enjoy better mapping properties than S k and N k . Namely, we define

S k,ω Γ := S k 1 ω Γ , N k,ω Γ := N k ω Γ , ( 26
)
and recast the BIEs (22) as

S k,ω Γ α = u D , N k,ω Γ β = u N . ( 27
)
where the unknowns α and β are related to λ and µ by

λ = α ω Γ , µ = ω Γ β .
Equation (25) give the following relation between N k,ω Γ and S k,ω Γ .

Lemma 11. There holds

N k,ω Γ = -∂ τ S k,ω Γ ω Γ ∂ τ ω Γ -k 2 V k ω 2 Γ
where V k is the integral operator defined by

V k u = Γ G k (x -y)N (x) • N (y)u(y) ω Γ (y) dσ(y) .
Proof. Eq. ( 25) can be rewritten equivalently as

N k u = -∂ τ S k ∂ τ u -k 2 Γ G k (x -y)N (x) • N (y)u(y)dσ(y) .
Using the definitions of N k,ω Γ and S k,ω Γ , the results follow from simple manipulations on this expression.

Weighted layer potentials on the flat segment

In this section, we consider the case where the wavenumber k is equal to 0 and Γ = [-1, 1] × {0}. The parametrization r is then the constant function equal to 1, ∂ τ = ∂ x and ω Γ = ω. In this context, the weighted potentials are thus denoted by S 0,ω and N 0,ω . Some explicit properties of those operators allow us to characterize T s and U s for s = ± 1 2 .

Single layer potential. The operator S 0,ω takes the form

S 0,ω α(x) = 1 -1 ln |x -y| α(y) 1 -y 2 dy .
There holds

S 0,ω T n = σ n T n ( 28
)
where

σ n =      ln(2) 2 if n = 0, 1 2n
otherwise.

Those identities are fundamental in our analysis. A proof can be found in [2, Theorem 9.2]. We deduce easily Lemma 12. The operator S 0,ω is a positive bicontinuous bijection from T s to T s+1 for all s ∈ R.

In particular, S 0,ω maps T ∞ to itself, so the image of a smooth function by S 0,ω is a smooth function. We now proceed to show the following characterization of T -1/2 and T 1/2 . The next result, and Lemma 15 stated below are equivalent to results formulated in [START_REF] Jerez-Hanckes | Explicit variational forms for the inverses of integral logarithmic operators over an interval[END_REF] (see equations (4.77-4.86), and Propositions 3.1 and 3.3 therein).

Lemma 13. We have T -1/2 = ω H-1/2 (-1, 1) and for all u ∈ H-1/2 (-1, 1),

u H-1/2 ∼ ωu T -1/2 .
Moreover, T 1/2 = H 1/2 (-1, 1) and

u H 1/2 = u T 1/2 .
Proof. Since the logarithmic capacity of the segment is 1 4 , the (unweighted) single-layer operator S 0 is positive and bounded from below on H-1/2 (-1, 1), (see [START_REF] Mclean | Strongly elliptic systems and boundary integral equations Cambridge university press[END_REF] chap. 8). Therefore the norm on H-1/2 (-1, 1) is equivalent to

u H-1/2 ∼ S 0 u, u .
On the other hand, the explicit expression (28

) implies that if α ∈ T -1/2 , then α T -1/2 ∼ S 0,ω α, α 1 ω .
It remains to notice that, since α = ωu, S 0,ω α, α 1 ω = S 0 u, u . This proves the first result. For the second result, we know that,

(H 1/2 (-1, 1)) = H-1/2 (-1, 1)
([3, Chap. 3] taking the identification with respect to the usual L 2 duality denoted by •, • ) and therefore

u H 1 2 = sup v =0 u, v v H-1 2 .
According to the previous result, for all v ∈ H- 1 2 , the function

α = ωv is in T -1/2 , and v H-1/2 ∼ α T -1/2 , while u, v = u, α 1 ω . Thus u H 1/2 ∼ sup α =0 u, α 1 ω α T -1/2 .
The last quantity is the T 1/2 norm of u since T 1/2 is identified to the dual of

T -1/2 for •, • 1 ω
, concluding the proof.

Hypersingular operator. In the present context, the identity (11) takes the form

N 0,ω β, β ω = S 0,ω (ω∂ x ω)β, (ω∂ x ω)β 1 ω . Noticing that (ω∂ x ω)U n = -(n + 1)T n+1 , we have, for all n = m, N 0,ω U n , U m ω = 0 . Therefore, N 0,ω U n = ν n U n with ν n U n 2 ω = (n + 1) 2 σ n+1 T n+1 2 1 ω
, that is, ν n = (n+1) 2 . We deduce the following: Lemma 14. The operator N 0,ω is a positive bicontinuous bijection from U s to U s-1 for all s ∈ R.

In particular, N 0,ω maps smooth functions to smooth functions. As before, we obtain a characterization of U s for s = ± 1 2 from the previous formula.

Lemma 15. We have U 1/2 = 1 ω H1/2 (-1, 1) and for all u ∈ H1/2 (-1, 1),

u H1/2 ∼ u ω U 1/2 . Moreover, U -1/2 = H 1/2 (-1, 1)
and

u H 1/2 = u U 1/2 .

Optimal orders of convergence for the weighted Galerkin method

A Galerkin method based on a refined mesh and weighted L 2 scalar products is described in [START_REF] Alouges | New preconditioners for Laplace and Helmholtz integral equation on open curves: I. Analytical framework and numerical results[END_REF] to solve eqs. ( 27) and orders of convergences are announced for the Laplace problem (k = 0) when Γ = [-1, 1] × {0}. In this section we provide the proofs for those statements. Let us consider the following discretization of the segment [-1, 1]

-1 = x 0 < x 1 < • • • < x N = 1 ,
where x i = cos(i π N ).

Dirichlet problem

Let V h the Galerkin space of (discontinuous) piecewise affine functions with breakpoints at (x i ) 0≤i≤N . Let α h the unique solution in V h to the variational problem (S 0,ω α h , α h )

1 ω = (u D , α h ) 1 ω , ∀α h ∈ V h . ( 29
)
Let λ h = α h ω and α 0 = ωλ. Theorem 1. If the data u D is in T s+1 for some -1 2 ≤ s ≤ 2, then there holds:

λ -λ h H-1/2 ≤ Ch s+1/2 ωλ T s ≤ Ch s+1/2 u D T s+1 .
The proof of this theorem is similar in structure to the standard proof in non-weighted L 2 -spaces. What we expose below borrows many ideas from [START_REF] Sauter | Boundary element methods (Chap. 4)[END_REF]. The only difference, and source of difficulty, comes from the fact that the seminorms |P | T n of polynomials P do not vanish on each segment contrary to the non-weighted L 2 case. For this reason, an additional estimate, eq. (37), is required to establish the result.

Proof. Let us denote by Π h the operator that maps a function

α ∈ T -1/2 to the element α h ∈ V h such that (S 0,ω α h , α h ) 1 ω = (S 0,ω α, α h ) 1 ω ∀α h ∈ V h .
Since S 0,ω is coercive in T -1/2 by Lemma 12, we have an analog of Céa's lemma in our context:

∀α ∈ T -1/2 , α -Π h α T -1/2 ≤ C inf α h ∈V h α -α h T -1/2 . ( 30
)
From this we deduce, taking α h = 0 in the infimum:

∀α ∈ T -1/2 (I d -Π h )α T -1/2 ≤ C α T -1/2 .
In addition, we are going to show

∀α ∈ T 2 , (I d -Π h )α T -1/2 ≤ Ch 5/2 α T 2 . ( 31
)
By interpolation, this implies for all s ∈ -1 2 , 2

∀α ∈ T s , (I d -Π h )α T -1/2 ≤ Ch s+1/2 α T s .
The result then follows from this, since, on the one hand

λ -λ h H-1/2 ≤ C α 0 -α h T -1/2
by Lemma 13, with α h = Π h α 0 and, on the other hand, ωu = α 0 = S -1 0,ω u D which by Lemma 12, gives

α 0 T s ≤ C u D T s+1 .
We prove (31) by studying the properties of two particular operators: the L 2

1 ω orthonormal projection P h on V h and the interpolation operator I h which maps a continuous function α to the (continuous) function of V h that matches α at the breakpoints x i . Because of Céa's lemma, we have

∀α ∈ T -1/2 , (I d -Π h )α T -1/2 ≤ C (I d -P h )α T -1/2 .
Therefore, it suffices to show (31) where Π h is replaced by P h to establish the theorem. We shall first show that ∀α ∈ T s ,

(I d -P h )α L 2 1 ω ≤ Ch s α T s (32)
for s ∈ [0, 2]. The estimate in T -1/2 norm is then deduced by the classical duality method:

α -P h α T -1/2 = sup η∈T 1/2 ,η =0 (α -P h α, η) 1 ω η T 1/2 ,
and since P h is an orthonormal projection on L 2

1 ω , α -P h α T -1/2 = sup η∈T 1/2 ,η =0 (α -P N α, η -P h η) 1 ω η T 1/2 .
This, by Cauchy-Schwarz equality and (32), gives

∀α ∈ T 2 , α -P h α T -1/2 ≤ Ch 2 α T 2 sup η∈T 1/2 ,η =0 h 1/2 η T 1/2 η T 1/2 ,
implying the desired etimate. Let us prove (32). First, since P h is an orthonormal projection on L 2

1 ω ∀α ∈ L 2 1 ω , (I d -P h )α L 2 1 ω ≤ C α L 2 1 ω
.

Using again an interpolation argument, it is thus sufficient to show ∀α ∈ T 2 ,

(I d -P h )α L 2 1 ω ≤ Ch 2 α T 2 . ( 33
)
To this aim, we establish the following estimate:

∀α ∈ T 2 , (I d -I h )α L 2 1 ω ≤ Ch 2 α T 2 , ( 34
)
and conclude with ( by Proposition 3. If CI h α were affine on each segment [θ i , θ i+1 ], this inequality would simplify to

I d -P h )α L 2 1 ω ≤ (I d -I h )α L 2
(I d -I h )α 1 ω ≤ Ch 2 |α| T 2 . ( 36
)
This does not occur in our, which is the main difference with the standard proof. Nevertheless, if we show that

N -1 i=0 θi+1 θi |∂ θθ CI h α(θ)| 2 ≤ C α 2 T 2 , ( 37
)
then eq. (34) follows by triangular inequality. The expression of

CI h α on [θ i , θ i+1 ] is CI h α(θ) = α(x i ) + α(x i ) -α(x i+1 ) cos(θ i+1 ) -cos(θ i ) (cos(θ) -cos(θ i )), thus θi+1 θi |∂ θθ CI h α(θ)| 2 dθ = α(x i ) -α(x i+1 ) cos(θ i+1 ) -cos(θ i ) 2 θi+1 θi cos(θ) 2 dθ.
We can rewrite

|α(x i+1 ) -α(x i )| 2 = xi+1 xi ∂ x α(x)dx 2 ,
and apply Cauchy-Schwarz's inequality and the change of variables x = cos(θ) to find

|α(x i+1 ) -α(x i )| 2 ≤ xi+1 xi |∂ x α(x)| 2 ω(x) dx θi+1 θi sin(θ) 2 dθ.
Notice that the quantity

θi+1 θi cos(θ) 2 θi+1 θi sin(θ) 2 (cos(θ i+1 ) -cos(θ i )) 2
is bounded uniformly in (θ i , θ i+1 ). Indeed, since cos is injective on [0, π], the only problematic case is the limit when θ i = θ i+1 . It is easy to check that the fraction then takes the limit cos(θ i ) 2 , which is indeed uniformly bounded in θ i . We deduce

N -1 i=0 θi+1 θi |∂ θθ CI h α(θ)| 2 ≤ C ∂ x α 2 1 ω
.

By Corollary 2, one has 34) is established, concluding the proof.

∂ x α 1 ω ≤ C α T 2 , thus (

Neumann problem

Let W h the Galerkin space of continuous piecewise affine functions on the mesh (x i ) 0≤i≤N defined above, and β h the unique solution in W h to

(N 0,ω β h , β h ) ω = (u N , β h ) ω , ∀β h ∈ W h . ( 38
) Let µ h = β h ω and β 0 = µ ω . Theorem 2. If u N ∈ U s-1 , for some 1 2 ≤ s ≤ 2, there holds µ -µ h H1/2 ≤ Ch s-1 2 µ ω U s ≤ Ch s-1 2 u N U s-1 .
Proof. Like before, let us denote by Π h the operator that maps a function

β ∈ U 1/2 to the element β h ∈ W h such that (N 0,ω β h , β h ) = (N 0,ω β, β h ) ∀β h ∈ W h .
The operator N 0,ω being coercive on U 1/2 by Lemma 15, we have a Céa's lemma:

∀β ∈ U 1 2 , β -Π h β U 1/2 ≤ C inf β h ∈W h β -β h U 1/2 .
In particular taking β h = 0 in the infimum,

∀β ∈ U 1/2 , (I d -Π h )β U 1/2 ≤ C β U 1/2 .
Once we prove

∀β ∈ U 2 (I d -Π h )β U 1/2 ≤ Ch 3 2 β U 2 , ( 39
)
we get by interpolation

∀β ∈ U s , (I d -Π h )β U 1/2 ≤ Ch s-1 2 β U s for all s ∈ [ 1 2 , 2]
. The result follows since on the one hand,

µ -µ h H1/2 = β 0 -β h U 1/2 ,
by Lemma 15, with Π h β 0 = β h and, on the other hand, µ ω = β 0 = N -1 0,ω u N which, by Lemma 14, implies

β 0 U s ≤ C u N U s-1 .
Like before, the proof of (39) involves the study of the interpolation operator I h . Namely, if we have

∀β ∈ U 2 , (I d -I h )β ω ≤ Ch 2 β U 2 , (I d -I h )β U 1 ≤ Ch β U 2 , ( 40
)
then, by interpolation, we obtain

(I d -I h )β U 1/2 ≤ Ch 3/2 u U 2 ,
which gives (39) after applying Céa's lemma. Let us show the first estimate in (40). Applying Proposition 3 and using again the property of H 2 functions vanishing at the boundary (35) one can write

xi+1 xi ω |(I d -I h )β| 2 ≤ C(θ i+1 -θ i ) 4 θi+1 θi |∂ θθ (Sβ -SI h β)| 2 ≤ Ch 4 2 θi+1 θi |∂ θθ Sβ| 2 + 2 θi+1 θi |∂ θθ SI h β| 2 .
Summing for i = 0, • • • , N -1, by Proposition 3, we get

(I d -I h )β ω ≤ Ch 2   β U 2 + N -1 i=0 θi+1 θi |∂ θθ SI h β(θ)| 2 dθ   . ( 41
)
Just like for the Dirichlet problem, the proof would end here if SI h u were affine on each segment, because the second term in the right hand side would be 0. Here, we need to show that this term is controlled by β U 2 . Using the expression of I h , one can write

θi+1 θi |∂ θθ SI h β| 2 ≤ C |β(x i )| 2 θi+1 θi sin 2 θdθ + β(x i+1 ) -β(x i ) cos θ i+1 -cos θ i 2 θi+1 θi sin 2 θ(1 + cos 2 θ)dθ . ( 42
)
We can estimate the first term, thanks Lemma 5:

|β(x i )| ≤ C β U 2 ,
while for the second term, the numerator of the fraction is estimated as follows:

|β(x i+1 ) -β(x i )| 2 = xi+1 xi ∂ x β 2 ≤ xi+1 xi ω |∂ x β| 2 xi+1 xi 1 ω = |θ i+1 -θ i | xi+1 xi ω |∂ x β| 2 .
Observe that the quantity

|θ i+1 -θ i | θi+1 θi sin 2 θ(1 + cos 2 θ)dθ (cos θ i -cos θ i+1 ) 2
is bounded by a constant independent of θ i and θ i+1 . Indeed, in the limit θ i+1 → θ i , the fraction takes the value 1 + cos 2 θ i . Therefore, (41) leads to

(I d -I h )β ω ≤ Ch 2 ( β U 2 + ∂ x β ω ) .
Recalling Corollary 2, the second term in this estimate is controlled by β U 2 and the first estimate of ( 40) is established. The second estimate of (40) can be shown in a similar manner, concluding the proof.

Estimates in the weighted L 2 norms

We have just established the optimal orders of convergence of the Galerkin method in the energy norms. It is also possible to prove optimal order of convergence in the weighted L 2 norm of the problem, using inverse estimates and Aubin-Nitsche's duality method. The proofs do not differ in any essential way from the standard theory, so they are omitted.

Proposition 4. For all s ∈ [0, 2],

α 0 -α h 1 ω ≤ Ch s α 0 T s , β 0 -β h ω ≤ Ch s β 0 U s .
and for all s ∈ [1, 2],

β 0 -β h U 1 ≤ Ch s-1 β 0 U s .

Pseudo-differential operators on open curves

This section is devoted to the introduction of two classes of pseudo-differential operators on open curves, which, to the best of our knowledge, have not been studied elsewhere in the literature. Our approach can be summarized as follows.

Through the change of variables x = θ, an operator on the segment can be viewed as an operator on the torus T 2π (where T 2π = R/2πZ as in section 1.4). On this geometry, a simple algebra of pseudo-differential operators exists [START_REF] Turunen | On symbol analysis of periodic pseudodifferential operators[END_REF]. However, the inverse change of variables, θ = arccos(x) has singularities at x = -1 and x = 1, preventing the transfer of the properties of this algebra back to the segment. We solve this difficulty by using some parity arguments.

Loosely speaking, we first remove the problematic part of the operators before applying the pullback change of variables. As a result, two classes of operators emerge, related to pseudo-differential operators on the torus that stabilize even and odd functions respectively. We start by collecting some facts on periodic pseudo-differential operators in section 3.1. We then introduce a first class of pseudo-differential operators on the segment (and more generally on smooth open curves) in section 3.2, which is based on the scales of Hilbert spaces (T s ) s∈R presented in section 1. We show that the usual properties of pseudo-differential operators hold in this class. The pseudo-differential operators based on (U s ) s∈R are introduced in section 3.3.

Periodic pseudo-differential operators

On the family of periodic Sobolev spaces H s , a class of periodic pseudo differential operators (PPDO) is studied in [START_REF] Turunen | On symbol analysis of periodic pseudodifferential operators[END_REF]. We briefly reproduce here the material needed for our purposes. A PPDO of order α on H s is an operator of the form

Au(θ) = n∈Z σ A (θ, n)Fu(n)e inθ for a "prolongated symbol" σ A ∈ C ∞ (T 2π × R) satisfying ∀j, k ∈ N, ∃C j,k > 0 : D j θ D k ξ σ A (θ, ξ) ≤ C j,k (1 + |ξ|) α-k . ( 43
)
Here, as in section 1.4, Fu(n) = 1 2π π -π u(t)e -inθ dθ are the usual Fourier coefficients of u and

D θ := 1 i ∂ ∂θ , D ξ := 1 i ∂ ∂ξ .
The class of symbols that satisfy (43) is denoted by Σ α , and Σ ∞ := ∪ α∈Z Σ α . The operator defined by a symbol σ is denoted by Op(σ) and the set of PPDOs of order α is denoted by Op(Σ α ).

The prolongated symbol is not unique but determined uniquely at integer values of ξ by (see [START_REF] Turunen | On symbol analysis of periodic pseudodifferential operators[END_REF]):

σ A (θ, n) = e -n (θ)Ae n (θ) , ( 44
)
where we recall the notation e n (θ) = e inθ . This justifies the terminology of "prolongated symbol". The operator A is in Op(Σ α ) if and only if

∀j, k ∈ N, ∃C j,k > 0 : D j θ ∆ k n σ A (θ, n) ≤ C j,k (1 + |n|) α-k , ( 45
)
where

∆ n φ(θ, n) = φ(θ, n + 1) -φ(θ, n).
That is, if the symbol defined in (44) satisfies (45), then there exists a prolongated symbol satisfying (43). Because of this, we write σ ∈ Σ p a symbol σ(θ, n) that can be prolongated to a symbol σ(θ, ξ) ∈ Σ p . An operator in Op(Σ α ) maps H s to H s-α continuously for all s ∈ R. The composition of two operators in Op(Σ α ) and Op(Σ β ) gives rise to an operator in Op(Σ α+β ). If two symbols a and b in Σ ∞ satisfy a -b ∈ Σ α , we write a = b + Σ α . Definition 6. Let a ∈ Σ ∞ . If there exists a sequence of reals (p j ) j∈N such that p j+1 < p j and a sequence of symbols a j ∈ Σ pj such that for all N , a = N i=0

a i + Σ p N +1 , we write a = +∞ i=0 a i .
This is called an asymptotic expansion of the symbol a.

The symbol of the composition of two PPDOs A and B is denoted by σ A #σ B and satisfies the asymptotic expansion [START_REF] Turunen | On symbol analysis of periodic pseudodifferential operators[END_REF]

σ A #σ B (t, ξ) = +∞ j=0 1 j! ∂ ∂ξ j σ A (θ, ξ)D j θ σ B (θ, ξ) . ( 46
)
We also need the following result.

Proposition 5. (see [START_REF] Turunen | On symbol analysis of periodic pseudodifferential operators[END_REF]) Consider an integral operator K of the form

K : u → 1 2π π -π a(θ, θ )h(θ -θ )u(θ )dθ ,
where a is 2π-periodic and C ∞ in both arguments and h is a 2π-periodic distribution. Assume that the Fourier coefficients Fh(n) of h can be prolonged to a function ĥ(ξ) on R such that

∀k ∈ N, ∃C k > 0 : ∂ k ξ ĥ(ξ) ≤ C k (1 + |ξ|) α-k
for some α. Then K is in Op(Σ α ) with a symbol satisfying the asymptotic expansion

σ K (θ, ξ) = +∞ j=0 1 j! ∂ ∂ξ j ĥ(ξ)D j t a(t, θ) |t=θ . (47)
In particular, taking h ≡ 1, we see that for any functions a ∈ C ∞ (T 2 2π ), the operator

K : u → 1 2π π -π a(θ, θ )u(θ )dθ is in Op (Σ -∞ ).

Pseudo-differential operators on T s (Γ)

We now introduce a new class of pseudo-differential operators on the segment [-1, 1], which is based on the scale of Hilbert spaces (T s ) s∈R . Those operators are characterized in Theorem 3 in terms of PPDOs, and from this we deduce the main properties needed for our purposes in Corollary 5. Those definitions and results are then generalized to smooth open curves.

Definitions and main results

Definition 7. A an operator on T -∞ and assume that there exists a couple of functions a 1 and a 2 defined on [-1, 1] × N, that are C ∞ in the first variable and such that for all n ∈ N,

AT n = a 1 (x, n)T n -ω 2 a 2 (x, n)U n-1 , (48)
with, by convention, U -1 = 0. The operator defined by the previous formula is denoted by Op T (a 1 , a 2 ). Define the symbol σ(a 1 , a 2 ) on T 2π × Z by

σ(a 1 , a 2 )(θ, n) := a 1 (cos θ, |n|) + i sin θ sign(n)a 2 (cos θ, |n|) .
We say that (a

1 , a 2 ) ∈ S α T if σ(a 1 , a 2 ) ∈ Σ α .
In this case, we say that A is a pseudo-differential operator on T s and that the couple of functions (a 1 , a 2 ) is a pair of symbols for A. We denote

S ∞ T := ∪ α∈R S α T and S -∞ T = ∩ α∈R S α T . The set of pseudo-differential operators (of order α) in T -∞ is denoted by Op(S ∞ T ) (by Op(S α T )).

Remark 2. It is easy to construct non-trivial symbols in S -∞

T for the null operator. For example, for some m ∈ N, take a

(x, n) = δ n=m ω 2 (x)U m-1 (x) and b(x, n) = δ n=m T m (x).
Because of this, a pair of symbol for a pseudo-differential operator on T s is not unique. Definition 8. For a PPDO Ã of symbol σ Ã, we define a 1 ( Ã) and a 2 ( Ã) by

a 1 ( Ã)(x, n) = σ(arccos(x), n) + σ(arccos(x), -n) 2 , a 2 ( Ã)(x, n) = σ(arccos(x), n) -σ(arccos(x), -n) 2i √ 1 -x 2 ,
where

σ(θ, n) = σ Ã(θ, n) + σ Ã(-θ, -n) 2 .
We can now state the main results of this section. Recall the definition of the operator C from Proposition 3.

Theorem 3. Let A : T ∞ → T -∞ .
Assume that for some PPDO Ã ∈ Op(Σ α ), there holds CA = ÃC (49)

as an equality of operators on T ∞ . Then A has a unique continuous extension as an element of Op(S α T ), and (a 1 ( Ã), a 2 ( Ã)) is a pair of symbols for A. Reciprocally let A = Op T (a 1 , a 2 ) ∈ Op(S α T ). Then (49) holds, taking for à the PPDO of order α given by the symbol

σ Ã = σ(a 1 , a 2 ) .
We immediately derive the following properties of those new pseudo-differential operators as an easy consequence of the previous result.

Corollary 5. If A ∈ Op(S α

), then for all s ∈ R,

A : T s → T s-α is continuous. Moreover, A ∈ Op(S α T ) and B ∈ Op(S β T ) =⇒ AB ∈ Op(S α+β T ) .
Finally, if A and B admit the pairs of symbols (a 1 , a 2 ) and (b 1 , b 2 ) respectively, then AB admits the pair of symbol (a 1 ( C), a 2 ( C)) where

C = Op(σ(a 1 , a 2 ))Op(σ(b 1 , b 2 )) .
Proof of Corollary 5. Let A ∈ Op(S α T ), and let à a PPDO of order α such that (49) holds. Let u ∈ T s for some s ∈ R. Applying the isometric property of C (cf. Proposition 3) and the continuity of à from H s to H s-α ,

Au T s = CAu H s = ÃCu H s ≤ C Cu H s-α = C u T s-α .

This establishes the first claim. Let

A = Op T (a 1 , a 2 ) ∈ S α T , B = Op T (b 1 , b 2 ) ∈ S β
T and let à = Op(σ(a 1 , a 2 )), B = Op(σ(a 1 , a 2 )). We have Remark 4. We have already stated that a pseudo-differential operator on T s always admits several distinct symbols. Theorem 3 gives another way to view this fact, by observing that, when A ∈ Op(S α T ), there is an infinite number of operators à satisfying CA = ÃC. Indeed, if B is any PPDO that vanishes on the set of even functions, one has

CAB = ÃCB = Ã BC .
CA = ( Ã + B)C .
In light of this, a natural idea to define uniquely the symbol of A would be to set

a 1 = a 1 ( Ã * ), a 2 = a 2 ( Ã * ) ,
where à * is the operator defined by

à * Cu = CAu , à * Su = 0 .
However, though A ∈ Op(S α T à * may fail to be a PPDO of order α. To see why, one can check that if à is a PPDO of order α such that CA = ÃC, then the symbol of à * must be given by

σ Ã * (θ, n) = σ Ã(θ, n) + e -2inθ σ Ã(θ, -n) .
In general, this symbol is not in Σ α because of the oscillatory term e -2inθ . In conclusion, there is no clear way how to fix a natural representative in the class of pairs (a 1 , a 2 ) that define the same operator A. However, although unusual, this is not an obstacle for the theory.

Proof of Theorem 3

The proof of Theorem 3 is decomposed through the following lemmas.

Lemma 16. Let A = Op T (a 1 , a 2 ) and let à = Op(σ(a 1 , a 2 )). Then for all n ∈ N,

CAT n = ÃCT n .

Proof. Let A = Op T (a 1 , a 2 ). Let σ = σ(a 1 , a 2 ), and à = Op(σ). Fix n ∈ N.

On the one hand, we can write

AT n (cos(θ)) = a 1 (cos θ, n)T n (cos(θ)) -ω 2 (cos θ)a 2 (cos θ, n)U n-1 (cos θ) = a 1 (cos θ, n) cos(nθ) -sin θa 2 (cos θ, n) sin(nθ) .
On the other hand,

Ã(CT n )(θ) = Ã(e n )(θ) + Ã(e -n )(θ) 2 = σ(θ, n)e inθ + σ(θ, -n)e -inθ 2 = σ(θ, n) + σ(θ, -n) 2 cos(nθ) + i σ(θ, n) -σ(θ, -n) 2 sin(nθ) .
From the definition of σ(a 1 , a 2 ), we see that the first term in parenthesis is equal to a 1 (cos θ, n), and the second is i sin θa 2 (cos θ, n). Therefore,

CAT n = ÃCT n
for all n ∈ N and the result is proved.

Lemma 17. If à = Op(σ Ã) is a PPDO, then the functions a 1 ( Ã) and a 2 ( Ã) are C ∞ in the variable x and there holds the identity

σ(a 1 ( Ã), a 2 ( Ã))(θ, n) = σ Ã(θ, n) + σ Ã(-θ, -n) 2 . Proof. Let σ(θ, n) = σ Ã(θ, n) + σ Ã(-θ, -n) 2 . We decompose σ as σ(θ, n) = f (θ, n) + g(θ, n) where f (θ, n) = σ(θ,n)+σ(θ,-n) 2 and g(θ, n) = σ(θ,n)-σ(θ,-n) 2
By construction, f (resp. g) is even (resp. odd) in both θ and n. For n > 0, there holds

a 1 ( Ã)(x, n) = f (arccos(x), n), a 2 ( Ã)(x, n) = g(arccos(x), n) i √ 1 -x 2 .
Recalling Proposition 3, this is equivalently expressed as

a 1 ( Ã)(•, n) = C -1 f (•, n), a 2 ( Ã)(•, n) = -iS -1 g(•, n) .
Therefore, a 1 ( Ã) and a 2 ( Ã) are C ∞ in x since f (resp. g) is a smooth even (resp. odd) function. By definition, we have

σT (a 1 ( Ã), a 2 ( Ã))(θ, n) = Ca 1 ( Ã)(θ, |n|) + isign(n)Sa 2 ( Ã)(θ, |n|) = f (θ, |n|) + sign(n)g(θ, |n|) = f (θ, n) + g(θ, n) = σ(θ, n) ,
recalling that f (resp. g) is even (resp. odd) in n.

Lemma 18. If à = Op(σ Ã) is a PPDO that stabilizes the set of smooth even functions, then à coincides on this set with B = Op(σ B ) where

σ B (θ, n) = σ Ã(θ, n) + σ Ã(-θ, -n) 2 .
Proof. Let u a smooth even function. Since Au is even, we have

Au(θ) = Au(θ) + Au(-θ) 2 .
Thus

Au(θ) = 1 2 n∈Z σ Ã(θ, n)Fu(n)e inθ + σ Ã(-θ, n)Fu(n)e -inθ = 1 2 n∈Z σ Ã(θ, n)Fu(n)e inθ + σ Ã(-θ, -n)Fu(-n)e inθ = n∈Z σ Ã(θ, n) + σ Ã(-θ, -n) 2 Fu(n)e inθ since Fu(n) = Fu(-n). This proves the claim. Lemma 19. If A : T ∞ → T -∞ is such that there exists a PPDO Ã satisfying ∀n ∈ N, CAT n = ÃCT n , then A = Op T (a 1 ( Ã), a 2 ( Ã)).
Proof. Notice that the assumption implies that à stabilizes the set of smooth even functions. If σ à is the symbol of à and

σ(θ, n) = σ Ã(θ, n) + σ Ã(-θ, -n) 2
then, by Lemma 18, we have ÃC = Op(σ)C. by Lemma 17, we know that σ = σT (a 1 ( Ã), a 2 ( Ã))

and thus, letting B = Op T (a 1 ( Ã), a 2 ( Ã)), Lemma 16 tells us that ∀n ∈ N, CBT n = Op(σ)CT n .

Summing up, we have

∀n ∈ N, CAT n = ÃCT n = Op(σ)CT n = CBT n . This ensures A = B.
The proof of Theorem 3 is concluded as follows. Assume that for any u ∈ T ∞ , CAu = ÃCu where à is some PPDO of order α with a symbol σ Ã. The linear continuous extension of A is uniquely defined for

u ∈ T -∞ by ∀v ∈ T ∞ , Au, v 1 ω = CAu, Cv T2π = ÃCu, Cv T2π .
where the last quantity makes sense since Cu ∈ H -∞ . By Lemma 19, we have

A = Op T (a 1 ( Ã), a 2 ( Ã)). It remains to show that σ := σ(a 1 ( Ã), a 2 ( Ã)) ∈ Σ α . By Lemma 17, if à has a symbol σ Ã, then σ(θ, n) = σ Ã(θ, n) + σ Ã(-θ, -n) 2 ,
and σ Ã ∈ Σ α immediately implies σ ∈ Σ α . This proves the first assertion. The second assertion is an immediate consequence of Lemma 16.

Extension to open curves Definition 9. Let

A : T -∞ (Γ) → T -∞ (Γ). We say that A is a pseudo-dif- ferential operator (of order α) on T -∞ (Γ) if RAR -1 ∈ Op(S ∞ T ) (∈ Op(S α T )
). The set of pseudo-differential operators of order α on T -∞ (Γ) is denoted by Op(S α T (Γ)). We say that (a 1 , a 2 ) is a pair of symbols of A if it is a pair of symbols of RAR -1 .

The properties of Op(S

C = Op(σ(a 1 , a 2 ))Op(σ(b 1 , b 2 )) = Op(σ(a 1 , a 2 )#σ(b 1 , b 2 )) .

Pseudo-differential operators on U s (Γ)

We proceed to introduce an analogous family of pseudo-differential operators defined this time on the spaces U s . Similar properties hold for this new family where the symbol of Sk ∈ Op(Σ -1 ) has the asymptotic expansion

Sk (θ, ξ) = 1 2 |ξ| + k 2 |Γ| 2 sin(θ) 2 16 |ξ| 3 + 3ik 2 |Γ| 2 sin θ cos θ 16ξ 4 sign(ξ) +k 2 |Γ| 2 -768κ(θ) 2 |Γ| 2 sin 4 θ + 112 sin 2 θ + 3k 2 |Γ| 2 sin 4 θ -48 128|ξ| 5
+Σ -6 .

(52)

Proof. The Hankel function admits the following expansion

H 0 (z) = -1 2π ln |z|J 0 (z) + F 1 (z 2 ) ( 53
)
where J 0 is the Bessel function of first kind and 0 and where

F 1 is analytic. Let us define S k,ω := RS k,ω Γ R -1 .
We fix a smooth function u ∈ T ∞ . One has

(S k,ω u) (x) = 1 -1 H 0 (k |r(x) -r(y)|) u(y) ω(y) dy .
Using the change of variables x = cos θ, y = cos θ , we get

S k,ω u(cos θ) = π 0 H 0 (k |r(cos θ) -r(cos θ )|)u(cos(θ))dθ ,
which, in view of (53), can be rewritten as

S k,ω u(cos θ) = -1 2π π 0 ln |cos θ -cos θ | J 0 (k |r(cos θ) -r(cos θ )|)Cu(θ)dθ + π 0 F 2 (cos θ, cos θ )Cu(θ)dθ
where

F 2 (x, y) = ln |r(x) -r(y)| |x -y| + F 1 (k 2 (x -y) 2 )
is a C ∞ function. By parity, the second integral defines an operator

Ku(θ) = 1 2 π -π F 2 (cos θ, cos θ )Cu(θ)dθ.
There holds K = R1 C where, by Proposition 5, R 1 ∈ Op(Σ -∞ ). For the first integral, we make the following classical manipulations. We first write cos θ -cos θ = -2 sin θ+θ 2 sin θ-θ 2 . Thus

ln |cos θ -cos θ | = ln √ 2 sin θ + θ 2 + ln √ 2 sin θ -θ 2 .
We then integrate and apply the change of variables θ → -θ for the second term, yielding S k,ω u(cos θ) = Sk,1 + R1 Cu(θ)

where

Sk,1 u(θ) = -1 2π π -π ln 2 sin θ -θ 2 J 0 (k |r(cos θ) -r(cos θ )|)u(θ )dθ . Let g : θ → -1 2π ln √ 2 sin θ 2 . It is well-known that ĝ(n) = 1 2|n|
for n = 0. We may prolong this by ĝ(ξ) = 1 2|ξ| away from ξ = 0. Let

a(θ, θ ) = J 0 (k |r(cos θ) -r(cos θ )|) ,
which is a smooth function. By Proposition 5, the operator

Sk,1 u(θ) := π -π g(θ -θ )a(θ, θ )u(θ )dθ is in Op(Σ -1
). In particular, Sk,1 u is a smooth function, from which we deduce that θ → S k,ω u(cos θ) is a smooth (even) function. Proposition 3 then ensures

S k,ω u(cos θ) = CS k,ω u(θ) .
This establishes that CS k,ω u = Sk Cu for any smooth function u. By Corollary 5, this implies that S k,ω ∈ Op S -1

T

. We can compute the symbol of Sk,1 using the asymptotic expansion (47). The terms ∂ j s a(t, s) |t=s , can be related to the geometric characteristics of Γ through expansion (19). The asymptotic expansion (52) for Sk,1 is obtained the help of Maple, and we refer the reader to appendix A.1, eq. (1). To simplify the expressions, the computations were only performed for ξ > 0, where ĝ(ξ) = 1 2ξ . In the general case, the 1 ξ 4 term in the asymptotic expansion must be multiplied by sign(ξ) to account for the case ξ < 0. Obviously since R1 ∈ Op(Σ -∞ ), the asymptotic expansion also holds for Sk := Sk,1 + R1 , concluding the proof.

In particular, by Proposition 6, Corollary 7. S k,ω Γ is continuous from T s (Γ) to T s+1 (Γ) for all s ∈ R and thus maps C ∞ (Γ) to itself. A pair of symbols of S k,ω Γ is given by

a 1 (x, n) = 1 2n + k 2 |Γ| 2 ω(x) 2
-(ω Γ ) 2 -k 2 2 Γ = R -1 -(ω∂ x ) 2 -k 2 ω 2 R . Letting D k = -(ω∂ x ) 2 -k 2 ω 2 , D k T n = (n 2 -k 2 |Γ| 2 ω 2 )T n .
The result is then a consequence of Corollary 5.

Theorem 5. The operators -(ω Γ ∂ τ ) 2 -k 2 ω 2 Γ and S k,ω Γ are respectively in Op(S 2 T (Γ)) and Op(S -1 T (Γ)) and satisfy

-(ω Γ ∂ τ ) 2 -k 2 ω 2 Γ S 2 k,ω Γ = I d 4 + T -4 .
Proof. We have shown that -(ω Γ ∂ τ ) 2 -k 2 ω 2 Γ and S k,ω Γ are respectively in Op(S 2 T (Γ)) and Op(S -1 T (Γ)) in the previous two lemmas. Using the symbolic calculus described in section 3, we can compute an asymptotic expansion of the symbol of the pseudo-differential operator

-(ω Γ ∂ τ ) 2 -k 2 ω 2 Γ S 2 k,ω Γ - I d 4 .
The symbol of this operator is found to be in S -4 T (Γ), from which the result follows. Details of the computations can be found in Appendix A.1.

Remark 5. The previous theorem implies the following fact

-(ω Γ ∂ τ ) 2 S 2 k,ω Γ = I d 4 + R
where R is in Op(S -2 T (Γ)). This is also a compact perturbation of the identity. Nevertheless, since R = k 2 ω 2 Γ S 2 k,ω Γ + T -4 the term k 2 ω 2 S 2 k,ω ∈ Op(S -2 T ) can be viewed as the leading first order correction accounting for the wavenumber. In numerical applications, the inclusion of this term in the preconditioners leads to very significant reductions of the number of GMRES iterations to solve the linear systems arising from the Galerkin discretization, as demonstrated in [START_REF] Alouges | New preconditioners for Laplace and Helmholtz integral equation on open curves: I. Analytical framework and numerical results[END_REF].

Neumann problem

We saw in Lemma 11 that N k,ω Γ = N 1 -k 2 N 2 where As a consequence, N 1 admits the pair of symbols

N 1 = -∂ τ S k,ω ω Γ ∂ τ ω Γ and N 2 = V k ω 2 Γ with V k u(x) = Γ G k (x -y)N (x)
a 1 (x, n) = n 2 + k 2 |Γ| 2 ω(x) 2 16n + ã1 , ( 56
)
a 2 (x, n) = k 2 |Γ| 2 x 16n 2 + ã2 , ( 57
)
where (ã 1 , ã2 ) ∈ S -3

U

Proof. This result is obtained by symbolic calculus combining Lemma 22 and Lemma 20. See appendix A.2 eq. ( 1).

A small adaptation of the proof of Lemma 22 yields the following result (see Appendix A.2 eq. ( 2))

Lemma 25. The operator V k is in Op(S -1 T (Γ)) and

CRV k R -1 = Ṽk C
where Ṽk is a PPDO with a symbol σ Ṽk satisfying

σ Ṽk = 1 2|ξ| + Σ -3 .
V k thus admits the pair of symbols

a 1 (x, n) = 1 2n + ã1 (x, n) , a 2 (x, n) = ã2 (x, n) ,
where (ã 1 , ã2 ) ∈ S -3 T .

Applying Lemma 21, we deduce Corollary 8. The operator N 2 is in Op(S -1 U (Γ)) and satisfies

SRN 2 R -1 = Ñ2 S
where the symbol of Ñ2 has the asymptotic expansion

σ Ñ2 = sin 2 θ 2 |ξ| + i sin θ cos θ 2ξ 2 sign(ξ) + Σ -3 . ( 58
)
A pair of symbols for N 2 is thus

a 1 (x, n) = ω(x) 2 2n + ã1 , a 2 (x, n) = x 2n 2 + ã2 ,
where (ã 1 , ã2 ) ∈ S -3 U .

Numerical quadratures:

The numerical quadratures used to discretize the integrals must be modified to take the weight w = 1 ω into account. Explicit Gaussian are available in the case of w(x) = 1 √ 1 -x 2 .

Singular integrals:

The main difficulty is the efficient computation of singular integrals of the form The first term can be computed explicitly, while the second is the integral of a smooth function, which is approximated using the standard Gaussian quadrature.

Finally, the method easily lends itself to formal generalizations. It is not difficult to treat the case of a flat disk in R 3 (this work is in progress). Future works also include the treatment of general angles in R 2 . Eventually, we expect that a suitable change of the weight function could allow to extend the approach to arbitrary geometries. so we just need to use the usual symbol calculus. We obtain the following symbol:

(1)

We then turn to the computation of an asymptotic expansion of the symbol of Ñ2 . We start a procedure to compute the symbol of the operator Ṽk :

The following symbol is obtained for Ṽk : [START_REF] Mason | Chebyshev polynomials[END_REF]

1 ω and L 2 ω

 12 respectively by •, • 1 ω and •, • ω and the inner products respectively by (•, •) 1 ω and (•, •) ω , with the following normalization:

  (a, b) which vanishes on a and b, there holds this result on [θ i , θ i+1 ] to v = (C(I d -I h )u) |[θi,θi+1] and summing those inequalities for i = 0 to Nθθ C(I d -I h )α(θ)| 2 dθ , where on the left hand side, the integral is equal to (I d -I h )α 2 1 ω

Remark 3 .

 3 Applying the properties of the PPDOs, one has à B ∈ Op(Σ α+β ) therefore, by Theorem 3, AB ∈ Op(S α+β T ) establishing the second claim. In addition, by Theorem 3, AB admits the pair of symbols (a 1 ( à B), a 2 ( à B)), concluding the proof. The previous results provide a symbolic calculus on the class S α T (Γ) as follows. If B and C respectively admit the pair of symbols (b 1 , b 2 ) and (c 1 , c 2 ), then BC admits the pair of symbols (b 1 , b 2 )# T (c 1 , c 2 ) := a 1 ( Ã), a 2 ( Ã) where à = Op (σ(b 1 , b 2 )#σ(c 1 , c 2 )). One can use (46) to compute an asymptotic expansion of σ(b 1 , b 2 )#σ(c 1 , c 2 ) which, in turn, gives an asymptotic expansion of (b 1 , b 2 )# T (c 1 , c 2 ).

Proposition 6 .

 6 α T ) are transferred to Op(S α T (Γ)) without difficulty. Let A ∈ Op(S α T (Γ)). Then for all s, A is continuous from T s (Γ) to T s-α (Γ).If A and B respectively belong to Op(S α T (Γ)) and Op(S β T (Γ)), with pairs of symbols (a 1 , a 2 ) and (b 1 , b 2 ), then AB is in Op(S α+β T (Γ)) and admits the pair of symbols a 1 ( C), a 2 ( C) where

2 16n 4

 24 + ã2 , where (ã 1 , ã2 ) ∈ S-5 T . Lemma 23. The operator-(ω τ ∂ τ ) 2 -k 2 ω 2 Γ is in Op(S 2 T (Γ))with the pair of symbolsa 1 (x, n) = n 2 -k 2 |Γ| 2 ω 2 (x) 4 , a 2 (x, n) = 0 . It satisfies CR -(ω τ ∂ τ ) 2 -k 2 ω 2 Γ R -1 = Dk C where Dk ∈ Op(Σ 2 ) has the symbol σ Dk (θ, ξ) = |ξ| 2 -k 2 |Γ| 2 sin 2 (θ) . (54) 36 Proof. Recalling eqs. (20),(21), one has

  where a, b and x are close to 1 or -1. An efficient method is to rewrite this integral asθ b θa ln |sin θ(θ -θ )| dθ + θ b θa ln |cos θ -cos θ | |sin θ(θ -θ )| dθ ,where θ a = arccos(a), θ b = arccos(b) and θ = arccos(x).

  The operator N 1 is in Op(S 2 U (Γ)) andSRN 1 R -1 = Ñ1 Swhere Ñ1 is a PPDO with a symbol σ Ñ1 satisfying

	Lemma 24. σ Ñ1 (θ, ξ) =	|ξ| 2	+	1 16	k |Γ|	• N (y)u(y) ω Γ (y) 2 sin 2 (θ) |ξ| + i k 2 |Γ| 2 sin θ cos θ dσ(y) . 16ξ 2 sign(ξ)	+ Σ -3 .	(55)

√ 1 -x 2 dx < +∞ ,

of pseudo-differential operators. They are stated here but the proofs do not differ any significant way from the previous, and are thus omitted. At the end of this section, we also establish two results linking pseudo-differential operators on T s (Γ) to pseudo-differential operators on U s (Γ). Definition 10. Let A an operator on U -∞ and assume that there exists a couple of smooth functions a 1 and a 2 defined on [-1, 1] × N, that are C ∞ in the first argument and such that for all n ∈ N * ,

The operator defined by the previous formula is denoted by Op U (a 1 , a 2 ). For n ∈ Z and θ ∈ [0, 2π], define the symbol σ(a 1 , a 2 ) as before by

with the convention a 1 (x, 0) = a 2 (x, 0) = 0. We say that (a 1 , a 2 ) ∈ S α U if σ(a 1 , a 2 ) ∈ Σ α . In this case, we say that A is a pseudo-differential operator on U s and the (non-unique) couple of functions (a 1 , a 2 ) is called a pair of symbols of A. We also take the notation

Recall the definition of the isometric mapping S from Proposition 3.

as an equality of operators on U ∞ . Then A has a unique continuous extension as an element of Op(S α U ), and (a 1 ( Ã), a 2 ( Ã)) is a pair of symbols for A. Reciprocally let A = Op U (a 1 , a 2 ) ∈ Op(S α U ). Then (51) holds, taking for à the PPDO of order α given by the symbol

). The set of pseudo-differential operators of order α on U -∞ (Γ) is denoted by Op(S α U (Γ)). We say that (a 1 , a 2 ) is a pair of symbols of A if it is a pair of symbols of RAR -1 .

Corollary 6. Let Γ a smooth open curve and let

and admits the pair of symbols (a 1 ( Ã), a 2 ( Ã)) where

Proof. One can check the following identities:

Let A = RAR -1 and B = RBR -1 . Assuming that CA = ÃC, there holds

Since à can be chosen as a PPDO of order α by Corollary 5, ∂ θ Ã∂ θ is then a PPDO of order α+2 and by Theorem 4, we conclude that B ∈ Op(S α+2 U (Γ)).

Lemma 21. Let A ∈ Op(S α T (Γ)) and let

where sin denotes the operator f (θ) → sin(θ)f (θ).

Proof. This follows from the identities S = sin C, Cω 2 = sin S and the same arguments as in the proof of Lemma 20.

Parametrices for the weighted layer potentials

Here, we apply the pseudo-differential theory on T s (Γ) and U s (Γ) to build parametrices for the weighted layer potentials introduced at the beginning of the second section. Asymptotic expansions are performed with the help of the symbolic calculus software Maple. The proofs of the next results are accompanied by commented Maple worksheets in Appendix A.

Dirichlet problem

Lemma 22. The operator S k,ω Γ belongs to Op(S -1 T (Γ)) and satisfies

It is also easy to check the following result:

where Dk is the operator defined in Lemma 23.

U (Γ)) and Op(S 1 U (Γ))and satisfy

Proof. Gathering the previous lemmas, we have asymptotic expansions available for the symbols of the operators

We can thus compute an asymptotic expansion of the symbol of the operator

Γ which turns out to be in S -2 U (Γ), giving the result. Details of the computations can be found in Appendix A.2.

Conclusion

In this work and [START_REF] Alouges | New preconditioners for Laplace and Helmholtz integral equation on open curves: I. Analytical framework and numerical results[END_REF], we described and analyzed a new method for the numerical resolution of first-kind integral equations modeling wave scattering by open curves, with Dirichlet or Neumann boundary conditions. The equations are discretized with a Galerkin method in weighted L 2 space, with piecewise linear functions defined on an explicitly refined mesh. We have established optimal rates of convergence for the method. We have also introduced an adapted analytic framework with, in particular, a new pseudo-differential calculus on open curves, providing a precise understanding of the weighted layer potentials. A simple and effective symbolic calculus has enabled us to build parametrices for those operators. In turn, those parametrices can be discretized to provide preconditioners for the linear systems. Our numerical results, exposed in [START_REF] Alouges | New preconditioners for Laplace and Helmholtz integral equation on open curves: I. Analytical framework and numerical results[END_REF], are in close agreement with the theoretical predictions. The preconditioners have been tested on various examples, including cases at high frequencies. They indeed lead to great reductions in the number of GMRES iterations for the resolution of the linear systems.

The numerical method is straightforward to implement and is only in a small variant of the standard method. The only differences are summarized below: Mesh refinement: The mesh has to be refined in an explicit way near the edges. In fact, it must be uniform with respect to the weight function, that is the quantity We use the following procedure to compute an asymptotic expansion of the symbol of Sk . K denotes the unknown constant in the next order.

We obtain the following asymptotic expansion up to order 6:

(1)

We can thus compute the symbol of the operator S2 k using symbolic calculus, and keep the terms up to order -6.

(2) now apply symbolic calculus to compute an asymptotic expansion of the symbol of the composition Dk S2 k , keeping only the first two terms

We see that this is of the form 1 4 + σ where σ ∈ Σ -4 .

A.2 Hypersingular operator

Procedure for the (usual) symbolic calculs: We first compute an asymptotic expansion up to order 3 of the symbol of Ñ1 = -∂ θ Sk ∂ θ . We already know the symbol of Sk The operator Ñ2 is then obtained by multiplying left and right by the operator u(x) → u(x)sin(x). We obtain the following asymptotic expantion up to order 3.

(3)

The symbol of Ñk = Ñ1 -k 2 L 2 4 Ñ2 is thus, retaining only the terms up to order 3: (4)

We can now compute the symbol of Ñ 2 k by usual symbolic calculus, retaining terms up to order 2.

(5)

The difference Ñ 2 k -1 4 Dk ,


P Cettour-Janet

C Cazorla

V Machairas

Q Delannoy

N Bednarek

F Rousseau

É Decencière

N Passat

Keywords: waterpixels, superpixels, seeded watershed, 3-dimensional images, Cartesian grid

In this article, we present the n-dimensional version of the waterpixels, namely the watervoxels. Waterpixels constitute a simple, yet efficient alternative to standard superpixel paradigms, initially developed in the field of computer vision for reducing the space cost of input images without altering the accuracy of further image processing / analysis procedures. Waterpixels were initially proposed in a 2-dimensional version. Their extension to 3-dimensions-and more generally n-dimensions-is however possible, in particular in the Cartesian grid. Indeed, waterpixels mainly rely on a seeded watershed transformation applied on a saliency map defined as the linear combination of a gradient map and a distance map. We propose a description of the algorithmics of watervoxels in n-dimensional Cartesian grids. We also discuss its parameters and its time cost. A source code for 2-and 3-dimensional versions of watervoxels is provided, such as a 2-dimensional demonstrator.

Introduction

Superpixels [START_REF] Ren | Learning a classification model for segmentation[END_REF] have emerged as a relevant low-level, pre-processing approach for simplifying large images, especially in the context of computer vision applications, that require rapid (ideally real-time) operators compliant with embedded vision tools.

In theory, the idea of superpixels is rather simple: it consists of reducing the combinatorics of an image (i.e. the number of pixels) whereas altering neither the spectral information (pixel values) nor the pixel organization (pixel topology). In other words, superpixels aim at building a smaller, information lossless image from the initial image, thus allowing to reduce the time cost of further procedures acting on it.

In practice, satisfying the three constraints of (1) image size reduction, (2) information preservation (3) structure non-alteration, is difficult, since they are generally antagonistic.

In this context, many superpixel paradigms have been proposed. Among them, the SLIC superpixels [START_REF] Achanta | SLIC superpixels compared to state-of-the-art superpixel methods[END_REF] are considered as the state of the art. In the meantime, many other superpixel paradigms were investigated. Among these alternatives, the waterpixels, initially proposed in [START_REF] Machairas | Waterpixels: Superpixels based on the watershed transformation[END_REF] and further compared to SLIC superpixels [START_REF] Machairas | [END_REF] exhibit good performances with an efficient, linear time cost.

The paradigm of waterpixels is mainly based on the watershed transformation [START_REF] Beucher | Use of watersheds in contour detection[END_REF][START_REF] Vincent | Watersheds in digital spaces: An efficient algorithm based on immersion simulations[END_REF], and more precisely its marker-based variant that allows one to control the number and position of the regions forming the image partition. Basically, waterpixels consist of computing the seeded watershed transformation of a saliency map built as the linear combination of a gradient map (ensuring the coherence of the superpixels in terms of signal homogeneity and edge-fitting) and a distance map from a set of regularly sampled points (ensuring the geometrical coherence and topological consistency of the partition).

In the pioneering articles [START_REF] Machairas | Waterpixels: Superpixels based on the watershed transformation[END_REF][START_REF] Machairas | [END_REF], the waterpixels were defined in the 2-dimensional Cartesian grid. The proposed concepts remain, however, valid in any n-dimensional Cartesian grid, n ≥ 1. In the current paper, that can be seen as the companion paper of [START_REF] Machairas | [END_REF], we describe the waterpixel construction in dimension n. A demonstrator for building 2-dimensional waterpixels, and a source code for building the so-called watervoxels in 3 dimensions is also provided.

Synthetic description of the method

Let n ∈ N, n > 0 be the dimension of the considered image support. For all

i ∈ [[1, n]], let d i ∈ N, d i > 0 be the size of the image support in the i-th dimension. The support of the image is then the Cartesian product Ω = n i=1 [[0, d i -1]],
that is a finite subset of Z n . In particular, the size of this support is |Ω| = n i=1 d i . Let V be a normed vector space, that will allow us to associate a value to each point of the image support. The existence of a norm on V is indeed required for defining a notion of gradient on the image. For instance, V may be any grey-scale space (R or Z) but also a colour (RGB, HSV), a multi-/hyperspectral space, or more generally a vector space.

The image I is a mapping from Ω to V, namely

I : Ω → V x → I(x) = v (1)
The set of all such images is noted V Ω . The gradient map ∇ on the set of images V Ω is defined, for each image I of V Ω as

∇I : Ω → R + x → ∇I(x) = g (2)
and gives, for each point x of Ω an information on the norm g of the derivatives of I at x. Many definitions of discrete gradients can be designed on Z n . In general, they rely on finite differences with respect to the norm on V, and can be computed in linear time O(|Ω|) with respect to the size of the image support.

Let M ⊆ Ω. The distance map ∆(M ) from M in Ω is defined as

∆(M ) : Ω → R + x → min m∈M x -m (3)
for a given norm • in R n or Z n . For well chosen norms and / or subsets M , such distance maps can be computed in linear time O(|Ω|) with respect to the size of the image support.

Let S = {s j } k j=1 ⊆ Ω be a set of k distinct points of Ω, with 1 ≤ k ≤ |Ω|, used as seeds within Ω. Let F ∈ (R + ) Ω be a positive grey-level mapping on Ω. The seeded watershed W (F, S) is defined as the mapping

W (F, S) : Ω → [[1, k]] x → W (F, S)(x) = w (4)
where w is the index of the seed point s w ∈ S such that x belongs to the catchment basin of s w after the watershed transformation of F with the set of seeds S. In particular, W (F, S) provides a partition of Ω into k connected regions; this partition is total if the watershed is computed in a graph-based fashion, by considering the watersheds on the adjacency links between the points of Ω, following for instance classical adjacencies defined in digital topology [START_REF] Kong | Digital topology: Introduction and survey[END_REF]. The watershed transformation can be computed in linear time O(|Ω|) with respect to the size of the image support of F [9, Chapter 3]. Let I ∈ V Ω be the image to be processed. We choose the way of building the gradient ∇ and the distance map ∆, as meta-parameters. We define the set of markers M ⊆ Ω and the set of seeds S ⊆ Ω (in particular, the size k of S and M and the way they are spatially organized) and the trade-off coefficient α ∈ [0, 1] between the influence of the gradient and the distance map. Then, the watervoxel transformation W of I is defined as

W(I, M, S) = W (α.∇I + (1 -α).∆(M ), S) (5)
This watervoxel transformation can be computed in linear time O(|Ω|) with respect to the size of the image support of I.

Algorithmics and parameters

From an algorithmic point of view, the watervoxel transformation relies on three standard transformations: (1) the gradient, (2) the distance map and (3) the watershed transformation. These three transformations are simply combined together in order to provide the watervoxels, as expressed in Eq. ( 5). In other words, the algorithmic bricks of the watervoxel transformation can be seen as meta-parameters. They are discussed hereafter, together with actual parameters, namely the density of markers and the way to define seeds, and the trade-off between gradient and distance maps. In this section, the discussion is carried out under the most general hypotheses, in terms of image dimensions and value spaces. In the next section, implementation details corresponding to the source codes and demonstrator will be provided in 2-and 3-dimensions, and for grey-level and colour images.

Distance map and markers definition

The distance map defined in Eq. ( 3) depends on the chosen norm • . Since we work in Z n , that is viewed as the discrete analogue of R n , it is relevant to consider the space of

k norms • k , defined for z = (z i ) n i=1 ∈ R n as z k = n i=1 |z i | k 1 k (6) for k ∈ N, k > 0 and z ∞ = lim k z k = max i∈[[1,n]] {|z i |} (7)
In general, we mainly focus on the norms 1 , 2 and ∞ , corresponding to the Manhattan, Euclidean and Tchebychev distances.

The induced distance map ∆ on Ω, that is a part of Z n , depends on the position of the chosen set of markers M . In the general case of Z n , with n ≥ 3, the only configurations of markers leading to regular tilings of the image support are indeed the Cartesian samplings. In other words, we choose a gap distance δ ∈ N, δ > 0 that should separate the markers of M in each dimension or, equivalently, we define these markers as the points of (δZ) n ; the density of markers is then δ -n . The induced Voronoi tiling, with respect to any k is composed of hypercubes of size δ n still organized in a Cartesian way. (Note that it is, of course, possible to consider alternatively less regular tilings, for instance inspired from cristallographic configurations [START_REF] Strand | Distance transforms for three-dimensional grids with noncubic voxels[END_REF].)

Then, the distance map ∆(M ) is simply obtained by reproducing in each of these hypercubes, the local distance map corresponding to the k distance of each point to the centre of the hypercube. This computation has a constant cost at each point, as it is directly obtained from the coordinates of the points vs. those of the centre point.

It is worth mentioning that we can combine ∆ with an increasing transformation, for instance the square v → v 2 or exponential mapping v → e v in order to increase the weight of high distances.

Finally, it is important to keep in mind that the values of ∆ will have to be normalized in order to relevantly define their linear combination with the gradient values. In particular, the highest value of ∆ (that should be set to 1 in the normalization process) is obtained at the points located on (δZ + δ 2 ) n if δ is even and (δZ + δ-1 2 ) n if δ is odd.

Gradient computation

The distance map ∆(M ) has to be combined with a gradient map or, more precisely, a map ∇I providing the norm of the gradient of the image I. The way of building the gradient on a discrete image is not unique. In practice, it mainly depends on the composition of the discrete approximation of the derivatives of I along the n orthonormal vectors e i (i

∈ [[1, n]]) of the canonical basis of Z n .
Basically, such derivative in dimension i is generally approximated at x by a finite difference

∇ i I(x) = I(x) -I(x + e i ) ( 8
)
where • is the norm that endows the normed vector space V. Discrete versions of the norm of the gradient can then be designed by combining these n derivatives obtained in each dimension. In other words, we simply have

∇I(x) = (∇ i I(x)) n i=1 k (9)
This way of computing the norm of the gradient is consistent with any dimension n.

Here again, it is important to keep in mind that the gradient map will have to be normalized in order to be combined with the distance map. In particular, the maximal value of ∇I(x) is (max u,v∈V u -v ) n i=1 k , and should be set to 1 in the normalized gradient map. In the case where V has specific properties, for instance when V = R or Z, alternative strategies may also be considered for defining gradient heuristics, for instance via morphological operators.

Seeded watershed and seeds definition

There exist various kinds of watershed algorithms. In particular, the first ones proposed in the literature provided as output a partial partition of the discrete image, since they defined watersheds-i.e. frontiers between the catchment basins-by subsets of pixels / voxels. Recent algorithms (see [START_REF]Mathematical Morphology: From Theory to Applications[END_REF]Chapters 3,[START_REF]Mathematical Morphology: From Theory to Applications[END_REF] and references therein) now define interpixel / voxel watersheds, by considering the image support via the non-oriented graph modeling its topological structure. Under these hypotheses, the watershed transformation is formulated as a graph-cut problem that consists of defining a partition of the vertices (i.e. the pixels / voxels) of the graph, by the dual removal of edges (i.e. the interpixel / voxel adjacency links located on the watersheds).

Here, we rely on such a graph-based paradigm. This requires to define an adjacency relation on Ω, and more generally on Z n . The framework of digital topology provides us with standard adjacency relations, for instance the (2n)-and (3 n -1)-adjacencies that rely on the 1 and ∞ norms, and that lead to the well-known 4-and 8-adjacencies in Z 2 and the 6-and 26-adjacencies in Z 3 . It is important to avoid adjacencies that could lead to spatially non-coherent results. For instance, the (3 n -1)-adjacency could lead to intersections between regions, in violation of the Jordan theorem. Considering the (2n)-adjacency, i.e. following the policy of well-composedness [START_REF] Boutry | A tutorial on well-composedness[END_REF] is then a safe and easy strategy. Other solutions, proposed e.g. by perfect fusion grids [START_REF] Cousty | Fusion graphs: Merging properties and watersheds[END_REF] or regular images [START_REF] Ngo | Topology-preserving rigid transformation of 2D digital images[END_REF] may be alternatively considered.

Watershed transformation has the property of providing oversegmented results. Indeed, in its basic version, any point corresponding to a locally minimal value within the graph leads to a distinct catchment basin. In other words, the cardinality of the partition is equal to the number of local minima in the processed saliency map, with an oversized result in case of noisy input.

In the case of the watervoxels, we wish to obtain the same number of regions within the partition as the number of markers of M initially defined. In addition, for the sake of geometrical and topological coherence, these regions should have positions, size and relationships similar to the ones of the Voronoi tiling of Ω induced by the markers of M . Depending on the application, we can either use the set of markers M as set of seeds, or determine an alternative set of seeds S. (In particular, one may note that the markers of M may not be local minima of the saliency map.)

It is important to choose, for each marker m of M a seed point s of S such that s is located in the Voronoi cell of m, and not too close from the border of this cell, in order to avoid that many seeds be connected, which may yield undesired border effects. To tackle this issue, it is possible to constrain s to be at least at a given distance from the border of the Voronoi cell, by imposing a security distance (see Algorithm 2). Two strategies can be considered for defining s. First, one can define s, within the Voronoi cell, as the regional minimum for the saliency map α.∇I + (1 -α).∆(M ) located the closest to m. Second, one can choose s among the regional minima of the gradient map ∇I within the central part of the Voronoi cell [START_REF] Machairas | [END_REF]. Note that in this second case, it is also possible to recompute a distance map ∆ S from these new seed points. This new distance map can then substituted to ∆ in the linear combination, leading to the so-called m-marker strategy proposed in [START_REF] Machairas | [END_REF].

Trade-off parameter

The trade-off parameter α ∈ [0, 1] allows one to control the influence of the gradient map versus the distance map, in the linear combination forming the saliency map involved in the watershed transformation process.

Following Eq. ( 5), the higher α, the higher the importance of the gradient over the distance map. In the extreme cases, for α = 0, we only consider the distance map, and the watervoxel partitioning will exactly map the Voronoi tiling of the support Ω with respect to the markers M . By contrast, for α = 1, we only consider the gradient map, and the watervoxel partitioning is exactly the seeded watershed transformation induced by the set of seeds S.

Implementation

Description

The proposed implementation of the watervoxel algorithm is based on the following successive steps:

1. Image loading and storage in a Numpy array. The supported image formats are NIFTI, JPEG and PNG.

2. Computation of the gradient norm of the image.

3. Definition of the markers and computation of the distance map.

4. Computation of the linear combination of the distance map and the gradient:

α.image gradient + (1 -α).distance map (10)
5. Computation of the markers.

6. Computation of the marker-based watershed on the linear combination of the gradient norm and of the distance map.

7. Result saving as NIFTI (for 3D images) or PNG (for 2D images).

Requirements

The proposed implementation depends on various Python libraries (see requirements.txt file). These libraries are:

• nibabel (2.3.1), to read and write the NIFTI files.

• numpy (1.15.4), to perform matrix computation.

• scipy (1.1.0), to compute the gradient.

• scikit-image (0.14.1), to compute the watershed and to read and write 2D images.

• matplotlib (3.0.2), to plot the results.

The README file explains how to install the packages required to fulfill these dependencies in a virtualenv, parsing the file requirements.txt with pip.

Inputs

The proposed implementation requires the following input information:

• The path of the image to be computed.

• The size of the supervoxels (i.e. δ).

• The trade-off parameter (i.e. α) for the linear combination of distance map and gradient.

• The gradient type to be used (magnitude gradient, morphological gradient, dilation-image, image-erosion, inverted image, inverted plus erosion).

• The security distance (in case of use of the second strategy; see Section 3.3).

• The result file name.

• The structuring element (i.e. the shape of the structuring element which is used if we compute a morphological gradient).

• The type of distance map (Euclidean, Manhattan, Tchebychev).

• The m-marker Boolean parameter which determines wether we use or not the m-marker recomputed distance map.

In Algorithm 2, we provide the pseudo-code for the computation of markers. For each Voronoi cell, we set a label to the greatest area with minimum value and set the remainder to zero. In the first case, the minimal area is searched in the linear combination of the gradient and the distance map. In the second case, we set a security distance on the edges of the cell and we search the minimum of the gradient only (see Section 3.3).

Results

In this section, we illustrate the behaviour of the watervoxels. In particular, we compare them versus results obtained with SLIC. Our purpose here is not to carry out a comparative study between both. (In the 2-dimensional case, a comparative study was already proposed in [START_REF] Machairas | [END_REF].) Once again, our purpose is not to claim the superiority of one superpixel paradigm over the other, but to emphasize their behaviour differences. We recall, however, that the watervoxel method runs in guaranteed linear time.

2-dimensional example

We first compare the two superpixel approaches on a 2-dimensional colour image; see Figure 1 (the same image was involved in illustration examples in [START_REF] Machairas | [END_REF]). The dimensions of this image are 321 × 481 pixels.

For the watervoxel computation: the distance δ is 9 pixels and we set α to 0.7 which means that the gradient information is 2.5 times stronger than the distance map information. The markers are computed using, on the one hand, the first strategy, i.e. as the minima of the combined map (see Section 3.3); and on the other hand the m-marker strategy, i.e. as the minima of the gradient map with a further recomputated distance map.

For the SLIC computation, we used the Scipy implementation. We consider a similar segmentation, i.e. 321×481 9 2 1900, and a compactness equal to 100. One can observe that both SLIC and classical waterpixel results exhibit a globally similar result. Slight differences can be observed, however. For instance, one can see that the frontiers of superpixels that are adjacent to a strong gradient are completely modified in SLIC, whereas those with waterpixels have their boundary modified only on the strong gradient areas. In other words, the waterpixels remain more regular (or, equivalently, more dependent to the underlying distance map structure), whereas the SLIC superpixels experiment data-driven side effects. By contrast, the waterpixels with m-markers lead to a much less structured superpixel partitioning, that better captures fine gradient details (see, e.g., cloud regions), but with a less regular behaviour in actually constant areas (see, e.g., water regions). Depending on the targeted application, either one or the other behaviour may be prefered.

3-dimensional example

In a second time, we present supervoxel partitioning results on a 3-dimensional image, namely a magnetic resonance image (MRI) of a human brain.

The dimensions of this image are 240 × 320 × 32 voxels, and a binary mask was applied in order to remove the extracranial part (in other words, the background has a homogeneous null value).

For the watervoxel computation: the distance δ is set to 9 voxels and α is set to 0.8, which means the gradient information is 4 times stronger than the distance map information. The markers map is computed using the first strategy (see Section 3.3).

For the SLIC computation, we used the Scipy implementation. We consider similar segments, i.e. Based on a visual inspection, we observe that the classical watervoxels have a satisfactory behaviour, with a good fitting on the salient edges between different kinds of tissues, and a regular shape in homogeneous areas. The m-marker version of watervoxels exhibit the same kinds of properties already observed in the 2D case.

Algorithm 2 :

 2 Markers computation (Markers.py) Input: δ: distance between seeds / supervoxel size secure dist: security distance I: Image begin Decomposition of the image in Voronoi cells (depending on δ) M arker label = 0 N.B.: Initialization of the marker label number N.B.: (x lim, y lim, z lim) are the front upper left corner coordinates of a cubical Voronoi cell for x lim = indice x min to indice x max do for y lim = indice y min to indice y max do for z lim = indice z min to indice z max do thumbnail = I[x lim + secure dist : (x lim + δ) -secure dist, y lim + secure dist : (y lim + δ) -secure dist, z lim + secure dist : (z lim + δ) -secure dist] ind = where(min(thumbnail)) N.B.: flat zone of minimal value and of greatest area in the Voronoi cell M arkers[tuple(ind)] = M arker label M arker label = M arker label + 1 return M arkers

Figure 1 :

 1 Figure 1: Superpixel partitioning on a 2-dimensional image. Top: with the SLIC superpixel algorithm. Middle: with classical waterpixels. Bottom: with waterpixels and the m-marker recomputed distance map.

  a compactness equal to 100.

Figure 2 :

 2 Figure 2: From left to right: input image; SLIC superpixel partitioning; classical watervoxel partitioning; and watervoxel partitioning with the m-marker recomputed distance map. Axial slices of the 3D image volume.

Acknowledgements

The research leading to these results has been supported by the ANR MAIA project, grant ANR-15-CE23-0009 of the French National Research Agency (http://recherche.imt-atlantique.fr/maia) and the American Memorial Hospital Foundation.

Pseudo-code

We provide, in Algorithm 1, the pseudo-code for the whole watervoxel computation process. In particular, it summarizes the discussion of Section 3.