Jean Bourgain
email: bourgain@math.ias.edu

Haim Brezis
email: brezis@math.rutgers.edu

Petru Mironescu
email: mironescu@math.univ-lyon1.fr

A new function space and applications

Keywords: BMO, VMO, BV, Sobolev spaces, integer-valued functions, constant function, isoperimetric inequality 2002 AMS classification subject. 46E35

We define a new function space B, which contains in particular BMO, BV, and W 1/p,p , 1 < p < ∞. We investigate its embedding into Lebesgue and Marcinkiewicz spaces. We present several inequalities involving L p norms of integer-valued functions in B. We introduce a significant closed subspace, B 0 , of B, containing in particular VMO and W 1/p,p , 1 ≤ p < ∞. The above mentioned estimates imply in particular that integer-valued functions belonging to B 0 are necessarily constant. This framework provides a "common roof " to various, seemingly unrelated, statements asserting that integer-valued functions satisfying some kind of regularity condition must be constant.

Introduction

Let Ω be a connected domain in R n . Recall that if f : Ω → Z is a measurable function which satisfies one of the following regularity properties:

1. f ∈ VMO (Ω); 2. f ∈ W 1,1 (Ω); 3. f ∈ W 1/p,p (Ω), with 1 < p < ∞,
then f is constant [START_REF] Brezis | Degree theory and BMO. I. Compact manifolds without boundaries[END_REF]Comment 2,, [START_REF] Bourgain | Lifting in Sobolev spaces[END_REF]Theorem B.1]. The original motivation for this article was to provide a "common roof" to all these cases, and which yields in particular the following Theorem 1. Assume that f : Ω → Z is measurable and can be written as f = f 1 + f 2 + f 3 , with f 1 ∈ VMO (Ω; R), f 2 ∈ W 1,1 (Ω; R) and f 3 ∈ W 1/p,p (Ω; R) for some 1 < p < ∞. Then f is constant.

The proof of Theorem 1 relies heavily on the introduction of a new space of functions, which might be of interest well beyond the scope of Theorem 1.

In what follows we denote by Q the unit cube (0, 1) n . For 0

< ε < 1, Q ε (a) is the ε-cube centered at a. Given f ∈ L 1 (Q; R) and an ε-cube Q ε ⊂ Q, we set M( f ,Q ε ) = Q ε | f -f Q ε |, where f Q ε = Q ε f , (1)
and

M * ( f ,Q ε ) = Q ε Q ε | f (y) -f (z)| d ydz. (2)
Clearly, we have

M( f ,Q ε ) ≤ M * ( f ,Q ε ) ≤ 2 M( f ,Q ε ). (3)
Note that if f = 1 A , with A ⊂ Q measurable, then

M( f ,Q ε ) = M * ( f ,Q ε ) = 2 |A ∩ Q ε | (|Q ε | -|A ∩ Q ε |) |Q ε | 2 ≤ 1 2 . ( 4
)
The following quantity plays an important role:

[ f ] ε = sup F ε n-1 j∈J M( f ,Q ε (a j )) . (5)
Here, F denotes a collection of mutually disjoint ε-cubes, F = (Q ε (a j )) j∈J , such that #J = cardinality of J ≤ 1/ε n-1 (instead of #J we sometimes write #F ) and the sup in [START_REF] Sarason | Functions of vanishing mean oscillation[END_REF] is taken over all such collections. We then introduce the space

B = f ∈ L 1 (Q; R); sup 0<ε<1 [ f ] ε < ∞ ,
and the corresponding norm (modulo constants)

f B = sup 0<ε<1 [ f ] ε . ( 6
)
The definition of B is inspired by the celebrated BMO space of John-Nirenberg [START_REF] John | On functions of bounded mean oscillation[END_REF] equipped with the norm (modulo constants)

f BMO := sup 0<ε<1 sup a∈Q {M( f ,Q ε (a)); Q ε (a) ⊂ Q}. ( 7
)
Here are several examples of functions in B.

Example 1. BMO ⊂ B with continuous injection. Indeed, using (7) we find that f B ≤ f BMO .

When n = 1, we clearly have B = BMO ; however, when n ≥ 2, B is strictly bigger than BMO (see e.g. Example 2 below).

Example 2. BV ⊂ B with continuous injection. Indeed, by Poincaré's inequality

Q ε | f -f Q ε | ≤ c n ε n-1 ˆQε |∇ f |, so that j∈J M( f ,Q ε (a j )) ≤ c n ε n-1 ˆ∪j∈J Q ε (a j ) |∇ f | (8)
and

[ f ] ε ≤ c n ˆQ |∇ f |. (9)
Example 3. W 1/p,p ⊂ B, 1 < p < ∞, with continuous injection. Indeed, for every fixed α > 0 we have

ˆQε ˆQε | f (y) -f (z)| d ydz ≤ n α/2 ε α ˆQε ˆQε | f (y) -f (z)| |y -z| α d ydz.
Choosing α = (n + 1)/p and applying Hölder's inequality gives

M * ( f ,Q ε ) ≤ c n ε (n-1)/p ˆQε ˆQε | f (y) -f (z)| p |y -z| n+1 d ydz 1/p , with c n = n (n+1)/2 ,
and since #J ≤ 1/ε n-1 we obtain

ε n-1 j∈J M * ( f ,Q ε (a j )) ≤ c n j∈J ˆQε (a j ) ˆQε (a j ) | f (y) -f (z)| p |y -z| n+1 d ydz 1/p . (10) Therefore [ f ] ε ≤ c n f W 1/p,p .
An important quantity associated with B is defined by

[ f ] = lim ε→0 [ f ] ε . ( 11
)
The subspace

B 0 = { f ∈ B; [ f ] = 0} ( 12
)
plays a key role in this article.

Example 1'. VMO ⊂ B 0 . This is clear, since VMO functions (see [START_REF] Sarason | Functions of vanishing mean oscillation[END_REF]) are characterized by

lim ε→0 sup a∈Q {M( f ,Q ε (a)); Q ε (a) ⊂ Q} = 0. Moreover, VMO = B 0 when n = 1. Example 2'. W 1,1 ⊂ B 0 .
This is clear from (8) and the fact that

∪ j∈J Q ε (a j ) ≤ ε. Example 3'. W 1/p,p ⊂ B 0 , 1 < p < ∞.
This is an immediate consequence of (10) and the fact that

∪ j∈J Q ε (a j ) × Q ε (a j ) ≤ ε n+1 .
In particular we see that

VMO +W 1,1 + W 1/p,p ⊂ B 0 . ( 13
)
2 Some properties of B

The main result of this section is Theorem 2. Let n ≥ 2. Then we have B ⊂ L n/(n-1),w , and

f - Q f L n/(n-1),w ≤ C n f B , ∀ f ∈ B. ( 14
)
In Theorem 2, the Marcinkiewicz space L n/(n-1),w cannot be replaced by L n/(n-1) , as a consequence of the next result.

Proposition 3. Let n

≥ 2. There exists some f ∈ B such that f ∈ L n/(n-1) .
Proof of Theorem 2. We may assume that

f B ≤ 1 and Q f = 0. ( 15
)
We also temporarily make the additional assumption that f ∈ L ∞ .

Under these assumptions, we will prove that

f L n/(n-1),w ≃ sup t>0 t |{| f | > t}| (n-1)/n ≤ C n . ( 16
)
For this purpose it suffices to consider, in (16), only t 1.

We first note that, by (15), we have

ˆQ | f | ≤ 1. (17)
In view of (17) we may consider, for t > 1, a Calderón-Zygmund decomposition at height t, i.e., we consider families

F j (with j ≥ 1) of mutually disjoint cubes Q 2 -j ⊂ Q of size 2 -j such that, if we set F = ∪ j≥1 F j , then Q * | f | ≃ t for every Q * ∈ F (18)
and

| f | ≤ t a.e. in R := Q \ ∪ Q * ∈F Q * . ( 19
)
We next decompose f = g + h, with

g = f 1 R + Q * ∈F Q * f 1 Q * , h = j≥1 h j , and h j = Q * ∈F j f - Q * f 1 Q * .
By (18) and (19), we have

|g| ≤ Ct and thus {| f | > 2Ct} ⊂ {|h| > Ct}. ( 20
)
Using (20), we see that (16) amounts to the following:

sup t>1 t |{|h| > Ct}| (n-1)/n ≤ c. ( 21
)
We now proceed with the proof of (21). Since f B = 1, for every family

G ⊂ F j such that #G ≤ 1/(2 -j ) n-1 = 2 j(n-1) , we have 2 -j(n-1) Q * ∈G Q * f - Q * f ≤ 1.
By covering F j with mutually disjoint sets G as above, we find that

Q * ∈F j Q * f - Q * f ≤ 2 j(n-1) + #F j , (22)
and thus

h j L 1 ≤ 2 -j + 2 -n j #F j . ( 23
)
On the other hand, we have (using (18))

1 ≥ f L 1 ≥ j≥1 Q * ∈F j ˆQ * | f | = j≥1 Q * ∈F j 2 -n j Q * | f | j≥1 2 -n j t #F j . ( 24
)
From ( 23) and (24), we deduce that

j≥1 h j L 1 1 t + F j = 2 -j . ( 25
)
We next recall that

f L n/(n-1),w = sup A⊂Q |A| -1/n ˆA | f |. (26)
If F j = and Q * ∈ F j , then (26) applied with A = Q * , combined with (18), implies that

2 -j f L n/(n-1),w t 1/(n-1) . (27)
By ( 25) and (27), we have

h L 1 ≤ j≥1 h j L 1 1 t + f L n/(n-1),w t 1/(n-1) . ( 28
)
In turn, (28) implies that (with C as in (21))

|{|h| > Ct}| ≤ h L 1 Ct 1 t 2 + f L n/(n-1),w t n 1/(n-1) , (29)
and thus

t |{|h| > Ct}| (n-1)/n t (2-n)/n + f 1/n L n/(n-1),w ≤ 1 + f 1/n L n/(n-1),w . (30)
By taking, in (30), the supremum over t > 1, we find that

f L n/(n-1),w 1 + f 1/n L n/(n-1),w ,
and therefore f L n/(n-1),w 1. We complete the proof by removing the assumption that f ∈ L ∞ . Let

Φ N (s) =        s, if |s| ≤ N N, if s > N -N, if s < -N and set f N := Φ N ( f ). By (3), we have f N B ≤ 2 f B .
In addition, f N is bounded and thus satisfies (14), i.e.,

f N - Q f N L n/(n-1),w ≤ 2C n f B . (31)
Using (26) and passing to the limit as N → ∞ in (31) yields ( 14) for every

f ∈ B. Proof of Proposition 3. Set ϕ(x) = (1 -|x|) + , ∀ x ∈ R n
and

N m = 2 2 m , ∀ m ≥ 1.
f m (x) = N n-1 m ϕ(N m (x -b m )), ∀ m ≥ 1 (32)
and

f (x) = m≥1 f m (x). ( 33
)
We will prove that f ∈ B and f ∈ L n/(n-1) . Note that

supp f m = B(b m , 1/N m ),
and that the sets supp f m , m ≥ 1, are mutually disjoint. Clearly,

f m L 1 (Q) = C N m , ∀ m ≥ 1, (34)
and thus f ∈ L 1 (Q); here and in what follows we denote by C a generic constant depending only on n, We have

f m n/(n-1) L n/(n-1) (Q) = C, ∀ m ≥ 1, so that f ∈ L n/(n-1) (Q). Given 0 < ε < 1 and integers M 1 = M 1 (ε) ≥ 1 and M 2 = M 2 (ε) > M 1 (ε)
to be defined later, we write

f = S 1 + S 2 + S 3 , (35)
with

S 1 = m≤M 1 f m , S 2 = M 1 <m≤M 2 f m , S 3 = m>M 2 f m . ( 36
)
We now estimate separately

[S 1 ] ε , [S 2 ] ε and [S 3 ] ε . Estimate of [S 1 ] ε . Here we use the fact that if h ∈ Lip (Q) then M(h,Q ε (a)) ≤ n ε h Lip , (37)
and thus

[h] ε ≤ n ε h Lip .
In particular,

[ f m ] ε ≤ C ε (N m ) n . ( 38
)
Using ( 38) and the fact that

p i=1 X i ≤ X p+1 X -1 , ∀ X > 1,
we deduce that

[S 1 ] ε ≤ C ε 2 n 2 M 1 , ∀ ε ∈ (0, 1). ( 39
) Estimate of [S 2 ] ε . Applying (9) to f m yields [ f m ] ε ≤ C, ∀ m ≥ 1, ∀ ε ∈ (0, 1),
and in particular

[S 2 ] ε ≤ C(M 2 -M 1 ), ∀ ε ∈ (0, 1). ( 40
) Estimate of [S 3 ] ε . Clearly [h] ε ≤ 2 ε h L 1 (Q) , ∀ h ∈ L 1 . ( 41
)
From (34) we deduce that

[ f m ] ε ≤ C ε N m . ( 42
)
Using (42) and the fact that

∞ i=p Y i = Y p 1 -Y , ∀ Y ∈ [0, 1),
we see that

[S 3 ] ε ≤ C ε 2 2 M 2 . ( 43
)
We now explain how to choose M 1 (ε) and M 2 (ε). Given 0 < ε < 1, we denote by

M 1 = M 1 (ε) the largest integer ℓ ≥ 1 such that 2 n 2 ℓ ≤ 2 2n ε . ( 44
)
Equivalently, we have

2 n 2 M 1 ≤ 2 2n ε (45)
and

2 2 n 2 M 1 > 2 2n ε . ( 46
)
Combining ( 39) and (45) yields

[S 1 ] ε ≤ C, ∀ ε ∈ (0, 1). (47)
From ( 45) and ( 46) we obtain

|M 1 (ε) -log 2 log 2 (1/ε)| ≤ C, ∀ ε ∈ (0, 1/2). ( 48
)
Next we denote by

M 2 = M 2 (ε) the smallest integer ℓ ≥ 1 such that 2 2 ℓ ≥ 4 ε . (Note that M 2 > M 1 since 2 2 M 1 < 4/ε.) Equivalently, we have 2 2 M 2 ≥ 4 ε ( 49
)
and

2 2 M 2 -1 < 4 ε . ( 50
)
Combining ( 43) and (49) yields

[S 3 ] ε ≤ C, ∀ ε ∈ (0, 1). ( 51
)
From ( 49) and (50) we obtain

|M 2 (ε) -log 2 log 2 (1/ε)| ≤ C, ∀ ε ∈ (0, 1/2). ( 52
)
Therefore,

|M 2 (ε) -M 1 (ε)| ≤ C, ∀ ε ∈ (0, 1). ( 53
)
(Inequality (53) is deduced from (48) and (52) when ε ∈ (0, 1/2), and from (50) when ε ∈ [1/2, 1).) It follows from ( 40) and (53) that

[S 2 ] ε ≤ C, ∀ ε ∈ (0, 1). ( 54
)
Putting together (47), ( 51) and (54) we conclude that

[ f ] ε ≤ C, ∀ ε ∈ (0, 1),
and thus f ∈ B.

3 Some properties of B 0 and

[ f ] Our first result is Theorem 4. Let f be a Z-valued function on Q such that f ∈ B 0 . Then f is constant.
Combining Theorem 4 with (13) we obtain Theorem 1.

When n = 1 we have B 0 = VMO and we may then invoke the fact that functions in VMO (Q; Z) are constant (for any n ≥ 1); see [START_REF] Brezis | Degree theory and BMO. I. Compact manifolds without boundaries[END_REF]Comment 2,. Therefore it suffices to prove Theorem 4 when n ≥ 2. Next, we observe that it suffices to prove Theorem 4 when f = 1 A for some

A ⊂ Q. In- deed, let k ∈ Z be such that | f -1 (k)| > 0. Set A = f -1 (k) and g = 1 A . Clearly M * ( f ,Q ε ) ≥ M * (g,Q ε ) for every ε-cube Q ε . Since f ∈ B 0 , we deduce that g ∈ B 0 .
If Theorem 4 holds for g, then g ≡ 1, and thus f ≡ k.

Hence it remains to prove Theorem 4 when n ≥ 2 and f = 1 A . In this case we have the following quantitative improvement of Theorem 4.

Theorem 5. Let n ≥ 2. There exists a constant C n such that if f

= 1 A with A ⊂ Q measurable, then f - Q f L n/(n-1) (Q) ≤ C n [ f ]. ( 55
)
Remark 6. A much more precise result (see [1]) asserts that there exist two

constants 0 < c n ≤ c n < ∞ such that if f = 1 A , then c n min 1, ˆQ |∇ f | ≤ [ f ] ≤ c n min 1, ˆQ |∇ f | , (56)
with the convention that

´Q |∇ f | = ∞ if f ∈ BV . Note that f - Q f L n/(n-1) (Q) ≤ C ˆQ |∇ f | (57)
by the Sobolev embedding, and that clearly

f - Q f L n/(n-1) (Q) ≤ 2 when f = 1 A . ( 58
)
Therefore

f - Q f L n/(n-1) (Q) ≤ C min 1, ˆQ |∇ f | ≤ C ′ [ f ] by (56).
In fact, using a variant of the definition (5) involving ε-cubes of general orientation, one obtains a quantity

[ f ] * ε satisfying [ f ] ε ≤ [ f ] * ε ≤ C 1 [ f ] C 2 ε
for some constants C 1 > 1, C 2 > 1 depending only on n (see [1]). The main

result in [1] asserts that if f = 1 A , then lim ε→0 [ f ] * ε = 1 2 min 1, ˆQ |∇ f | ; (59)
the ingredients of the proof of (59) are much more sophisticated than the arguments presented below. We acknowledge that it was Theorem 5 which prompted one of us to conjecture that (59) holds.

The main tool in the proof of Theorem 5 is

Lemma 7. Let n ≥ 2. Let U = ∪ j∈J Q ε (a j ) be a union of ε-cubes. Then Q \ U contains a connected set S of measure ≥ 1 -α n (#J) n/(n-1)
ε n , for some positive constant α n depending only on n.

Here, the ε-cubes are not necessarily mutually disjoint, and we do not assume that these cubes are completely contained in Q.

Remark 8. The conclusion of Lemma 7 is optimal. Indeed, consider a ball B ⊂ Q of (small) radius R. We may cover the sphere Σ = ∂B by a union of ε-cubes as above with #J

ε n-1 ≃ R n-1 . Then |B| ≃ R n ≃ (#J) n/(n-1) ε n .
Granted Lemma 7, we turn to the Proof of Theorem 5. Let f = 1 A , with A ⊂ Q. Fix any λ ∈ (0, 1/2), e.g. λ = 1/4.

In view of (58), we may assume that

0 ≤ [ f ] < 2λ(1 -λ), ( 60
)
for otherwise the conclusion is clear with

C n = 1 λ(1 -λ) .
Note that, by (4),

M( f ,Q ε ) = 2 f Q ε (1 -f Q ε ).
Therefore,

M( f ,Q ε ) < 2λ(1 -λ) =⇒ either f Q ε < λ, or f Q ε > 1 -λ. ( 61
)
With ε small and Q = (ε, 1-ε) n , consider a maximal family J = J ε of points a ∈ Q such that the cubes Q ε (a) are mutually disjoint and satisfy

M( f ,Q ε (a)) ≥ 2λ(1 -λ), ∀ a ∈ J. ( 62
)
Let ν > 0 (to be chosen arbitrarily small later). We claim that for ε sufficiently small (depending on ν) we have

#J ≤ δ/ε n-1 , with δ = [ f ] + ν 2λ(1 -λ) . ( 63
)
Indeed, we first see that, for ε sufficiently small,

#J ≤ 1/ε n-1 . (64)
Otherwise, we may choose a subfamily J such that # J = I(1/ε n-1 ), where I(t) denotes the integer part of t.

Then [ f ] ε ≥ ε n-1 (# J) 2λ(1 -λ) ≥ ε n-1 1 ε n-1 -1 2λ(1 -λ),
which, by (60), is impossible for ε small. From (64) and the definition of [ f ] ε we have

[ f ] ε ≥ ε n-1 (#J) 2λ(1 -λ),
which yields (63) for ε sufficiently small. Set U := ∪ a∈J Q 2ε (a). By Lemma 7 and a scaling argument, Q \ U contains a connected set S = S ε such that

|S ε | ≥ (1 -2ε) n -α ′ n δ n/(n-1) , (65)
where α ′ n = 2 n α n . We next note that (by the maximality of J) U contains the set

V = V ε := {b ∈ Q; M( f ,Q ε (b)) ≥ 2λ(1 -λ)}, ( 66
)
and thus S ⊂ Q \ V . We consider the continuous function

f ε : Q → R, f ε (a) = f Q ε (a) .
By (61) and (66), in the set

Q \ V the function f ε takes values into [0, λ) ∪ (1 - λ, 1]. S ⊂ Q \ V being connected, we find that either f ε < λ, or f ε > 1 -λ in S.
We assume e.g. that f ε < λ in S ε along a sequence ε m → 0. Clearly,

ˆA∩ Q |1 -f ε | → 0 as ε → 0,
and thus

(1 -λ) S ε m ∩ A ≤ ˆSε m ∩A (1 -f ε m ) → 0 as m → ∞. ( 67
)
On the other hand, by ( 65) and (67) we have

|A| = S ε m ∩ A + Q \ S ε m ∩ A + Q \ Q ∩ A ≤ α ′ n δ n/(n-1) + o(1) as m → ∞,
and thus |A| ≤ α ′ n δ n/(n-1) , so that

|A| (n-1)/n ≤ α ′′ n δ = α ′′ n [ f ] + ν 2λ(1 -λ) , with α ′′ n = α ′ n (n-1)/n .
Since ν > 0 can be chosen arbitrarily small, we deduce that

|A| (n-1)/n ≤ α ′′ n [ f ] 2λ(1 -λ) . (68)
Finally, we note that

f -f L n/(n-1) = |A|(1 -|A|) n/(n-1) + (1 -|A|)|A| n/(n-1) (n-1)/n ≤ 2 min |A| (n-1)/n , |A c | (n-1)/n . ( 69
)
Combining ( 68) and ( 69) yields (55).

For further use, let us note that the proof of Theorem 5 leads to the following result.

Lemma 9. Let n ≥ 2 and λ ∈ (0, 1/2). Let A ⊂ Q be measurable and set f := 1 A .

Assume that there exists a sequence ε m → 0 and families

J m ⊂ Q m := (3ε m , 1 -3ε m ) n
of points a with the following property: 1) .

If b ∈ Q m \ ∪ a∈J m Q 2ε m (a), then M( f ,Q ε m (b)) < 2λ(1 -λ). Let δ := lim m→∞ ε n-1 m #J m . Then either |A| ≥ 1 -c n δ n/(n-1) , or |A c | ≥ 1 -c n δ n/(n-
Proof of Lemma 7. Recall a standard "relative" isoperimetric inequality. Let B ⊂ Q satisfy |B| ≤ 1/2. By (57) (applied with f = 1 B ) and (69), we have

|B| ≤ c n ˆQ |∇ 1 B | n/(n-1) = c n [P(B)] n/(n-1) , ( 70
)
where P(B) represents the perimeter of B relative to Q. When B is a Lipschitz domain (which will be the case in what follows), P(B) is the (surface) measure of ∂B ∩ Q.

We now turn to the proof of the lemma.

Set δ = (#J) ε n-1 . Let (A i ) i∈I be the connected components of the open set Q \ ∪ j∈J Q ε (a j ). A 1 A 2 A 3 Figure 1: The components of Q \ ∪ j∈J Q ε (a j ).
Note that each A i is Lipschitz, and that

∪ i∈I (∂A i ∩ Q) ⊂ ∪ j∈J (∂Q ε (a j ) ∩ Q). ( 71
)
Let

G j := {x ∈ ∂Q ε (a j ) ∩Q;
x does not belong to the (n -2) skeleton of ∂Q ε (a j )}.

Note that

[∪ i∈I (∂A i ∩ Q)] \ ∪ j∈J G j has zero H n-1 -measure.
Since a point x ∈ G j belongs to at most one ∂A i , we find, using (71), that

i∈I P(A i ) ≤ j∈J P(Q ε (a j )) ≤ c ′ n δ. ( 72
)
We claim that if δ < δ n (a positive number depending only on n), then there exists some i 0 ∈ I such that |A i 0 | > 1/2. Indeed, argue by contradiction and assume that |A i | ≤ 1/2, ∀ i ∈ I. By (70) and (72), we have

1 -|U| = |Q \ U| = i∈I |A i | ≤ c n i∈I [P(A i )] n/(n-1) ≤ c n i∈I P(A i ) n/(n-1) ≤ c n (c ′ n δ) n/(n-1) = c ′′ n δ n/(n-1) . ( 73
)
On the other hand

|U| ≤ (#J) ε n = δε < δ. ( 74
)
Combining ( 73) and ( 74) we obtain 1) ; this is impossible when δ < δ n , where δ n is the solution of

1 ≤ δ + c ′′ n δ n/(n-
1 = δ n + c ′′ n (δ n ) n/(n-1) ,
and thus the claim is established when δ < δ n . Set S = A i 0 , which is clearly connected and contained in Q \ U. Applying (70) to B = S c we find (using (72)) 1) , which is the desired conclusion when δ < δ n . Finally, we observe that

1 -|S| ≤ c n [P(S c )] n/(n-1) = c n [P(S)] n/(n-1) ≤ c ′′ n δ n/(n-
1 - 1 (δ n ) n/(n-1) δ n/(n-1) ≤ 0
when δ ≥ δ n and therefore Lemma 7 holds with 1) .

α n = max c ′′ n , 1 (δ n ) n/(n-

An extension of Theorem 5 to Z-valued functions

Our main result in this section is

Theorem 10. Let n ≥ 2. There exists a positive constant c (independent of n) such that if f is a Z-valued function in B and [ f ] < c, then f ∈ L n/(n-1) (Q) and f - Q f L n/(n-1) (Q) ≤ C n [ f ] , (75)
for some constant C n depending only on n.

Theorem 5 can be deduced from Theorem 10. Indeed, let f = 1 A . Then either [ f ] ≤ c, and Theorem 10 applies, or [ f ] > c, and then

f - Q f L n/(n-1) (Q) ≤ 2 ≤ (2/c)[ f ].
The smallness condition on [ f ] in Theorem 10 is essential, as shown by the following improvement of Proposition 3.

Proposition 11. Let n

≥ 2. There exists a Z-valued function f ∈ B such that f ∈ L n/(n-1) (Q).
Proof of Theorem 10. Step 1. Decomposition of f as a sum of characteristic functions. We temporarily assume that f ≥ 0. Then f is a sum of characteristic functions. Indeed, set

A k := {x ∈ Q; f (x) ≥ k}, ∀ k ∈ N * , and let g k := 1 A k . Then we claim that f = k>0 g k (76)
and

| f (x) -f (y)| = k>0 |g k (x) -g k (y)|, ∀ x, y ∈ Q. ( 77
)
Indeed, on the one hand (76) follows from

k>0 g k (x) = 0<k≤ f (x) 1 = f (x).
On the other hand, assuming e.g. that f (x) ≥ f (y), we have g k (x) = g k (y) provided either k ≤ f (y) or k > f (x), and thus

k>0 |g k (x)-g k (y)| = f (y)<k≤ f (x) |g k (x)-g k (y)| = f (y)<k≤ f (x) 1 = f (x)-f (y) = | f (x)-f (y)|;
that is, (77) holds.

We next note that (77) implies

M * ( f ,Q ε ) = k>0 M * (g k ,Q ε ), (78)
and in particular

M(g k ,Q ε ) ≤ M * ( f ,Q ε ), ∀ k > 0. ( 79
)
Step 2. Construction of maximal families of "bad" cubes. Fix some λ ∈ (0, 1/2) and consider a sequence ε m → 0. Let Q m := (3ε m , 1-3ε m ) n . Let J m be a maximal family of points a ∈ Q m such that the cubes Q ε m (a), a ∈ J m , are mutually disjoint and satisfy

M * ( f ,Q ε m (a)) ≥ 2λ(1 -λ).
By the maximality of J m and by (79), we have

M(g k ,Q ε m (b)) ≤ M * ( f ,Q ε m (b)) < 2λ(1 -λ), ∀ b ∈ Q m \ ∪ a∈J m Q 2ε m (a). ( 80
)
We next associate to each k an appropriate subfamily extracted from J m . More specifically, let

J k m := {a ∈ J m ; 3 2n M * (g k ,Q 3ε m (a)) ≥ 2λ(1 -λ)}. ( 81
)
We claim that

M(g k ,Q ε m (b)) < 2λ(1 -λ), ∀ b ∈ Q m \ ∪ a∈J k m Q 2ε m (a). (82)
Indeed, (80) implies that (82) holds for b ∈ Q m \ ∪ a∈J m Q 2ε m (a). It remains to establish (82) when b ∈ Q 2ε m (a) for some a ∈ J m \ J k m . In this case, we have

Q ε m (b) ⊂ Q 3ε m (a) and thus M * (g k ,Q ε m (b)) ≤ 3 2n M * (g k ,Q 3ε m (a)) < 2λ(1 -λ).
This completes the proof of (82).

Step 3. A first estimate of f - ffl Q f L n/(n-1)
. By (69), (82), and Lemma 9, we have

g k - Q g k L n/(n-1) ≤ 2 ( c n ) (n-1)/n lim m→∞ (ε m ) n-1 #J k m . ( 83
) Thus k>0 g k - Q g k L n/(n-1) ≤ 2 ( c n ) (n-1)/n lim m→∞ (ε m ) n-1 k>0 #J k m , (84)
and therefore

f - Q f L n/(n-1) ≤ 2 ( c n ) (n-1)/n lim m→∞ (ε m ) n-1 k>0 #J k m . ( 85
)
Step 4. A second estimate of f -´Q f L n/(n-1) .

In this step, we assume that

[ f ] < d := λ(1 -λ), with λ chosen as in Step 2. ( 86
)
Under this assumption, we will prove that

c ′ n lim m→∞ (ε m ) n-1 k>0 #J k m ≤ [ f ] for some constant c ′ n > 0. ( 87
)
Granted this estimate, we obtain (using (85)) that

f - Q f L n/(n-1) ≤ C n [ f ], with C n = 2 ( c n ) (n-1)/n /c ′ n . ( 88
)
We now proceed to the proof of (87). We first note that (by ( 3)) we have

M( f ,Q ε m (a)) ≥ λ(1 -λ), ∀ a ∈ J m . (89)
Repeating the proof of (64) (and using ( 86) and ( 89)), for large m we have

#J m ≤ 1/(ε m ) n-1 . ( 90
)
We next rely on the following lemma, well-known to the experts, whose proof is omitted.

Lemma 12. Let {Q ε (a); a ∈ J} be a family of mutually disjoint ε-cubes. Then there exists a constant N = N(n) such that 1. J = J 1 ∪ J 2 ∪ . . . J N .

2. For every j, the cubes Q 3ε (a), a ∈ J j , are mutually disjoint.

3. For every j, we have #J j ≤ #J/3 n-1 .

By Lemma 12, for every family of mutually disjoint

ε-cubes Q ε (a), a ∈ J ⊂ (3ε, 1 -3ε) n , such that #J ≤ 1/ε n-1 , we have (3ε) n-1 a∈J M(h,Q 3ε (a)) ≤ N [h] 3ε , ∀ h : Q → R. (91)
In particular, for large m we have (using (90) and ( 91))

(ε m ) n-1 a∈J m M( f ,Q 3ε m (a)) ≤ N/3 n-1 [ f ] 3ε m . (92)
Combining (92) with (3), we see that

(ε m ) n-1 a∈J m M * ( f ,Q 3ε m (a)) ≤ 2N/3 n-1 [ f ] 3ε m (93)
We now use successively (93), ( 78) and ( 81) and obtain that

[ f ] 3ε m ≥ 3 n-1 /(2N) (ε m ) n-1 a∈J m M * ( f ,Q 3ε m (a)) = 3 n-1 /(2N) (ε m ) n-1 a∈J m k>0 M * (g k ,Q 3ε m (a)) ≥ 3 n-1 /(2N) (ε m ) n-1 k>0 a∈J k m M * (g k ,Q 3ε m (a)) ≥ λ(1 -λ)/(3 n+1 N) (ε m ) n-1 k>0 #J k m = c ′ n (ε m ) n-1 k>0 #J k m , (94)
with c ′ n := λ(1 -λ)/(3 n+1 N). We derive (87) by letting m → ∞ in (94).

Step 5. We remove the assumption f ≥ 0. We note that f = f + -f -, and that

| f ± (x) -f ± (y)| ≤ | f (x) -f (y)|, ∀ x, y ∈ Q. ( 95
)
By ( 3) and (95), we have

M * ( f ± ,Q ε ) ≤ M * ( f ,Q ε ) ≤ 2M( f ,Q ε ), and thus [ f ± ] ≤ 2[ f ].
By the first part of the proof of this theorem, we have

f ± - Q f ± L n/(n-1) ≤ C n [ f ± ] ≤ 2 C n [ f ], (96) provided
[ f ] < c := d/2.
Finally, (96) implies that

f -ˆQ f L n/(n-1) ≤ C n [ f ] provided [ f ] < c, with C n := 4 C n .
The proof of Theorem 10 is complete.

Proof of Proposition 11. We use the same notation and the same strategy as in the proof of Proposition 3, with some minor modifications. Set

g m (x) = I( f m (x)), ∀ m ≥ 1
, where I(t) denotes the integer part of t, and

g(x) = m≥1 g m (x).
Clearly,

g m L 1 (Q) ≤ f m L 1 (Q) = C N m (97)
(by (34)), so that g ∈ L 1 (Q). On the other hand

g m n/(n-1) L n/(n-1) (Q) ≥ f m -1 n/(n-1) L n/(n-1) ([ f m >1]) ≥ α > 0, ∀ m ≥ 1,
and thus g ∈ L n/(n-1) (Q).

We will now prove that g ∈ B. Write

g = T 1 + T 2 + T 3 ,
with

T 1 = m≤M 1 g m , T 2 = M 1 <m≤M 2 g m , T 3 = m>M 2 g m ,
where M 1 = M 1 (ε) and M 2 = M 2 (ε) are defined exactly as in the proof of Proposition 3.

Estimate of [T 1 ] ε . Since g m ∈ Lip (Q), we need to modify the argument. We claim that, for sufficiently small ε (depending only on n), given any cube Q ε (a) there exists at most one integer m ≤ M 1 (ε) such that We deduce the claim using (99) and the fact that the balls B(b m , 2/N m ) are mutually disjoint.

Therefore, for ε ≤ ε 0 we have For ε ∈ [ε 0 , 1), we use (41) to assert that

M(T 1 ,Q ε (a)) ≤ Q ε (a) Q ε (a)
[T 1 ] ε ≤ 2 ε 0 T 1 L 1 (Q) ≤ 2 ε 0 g L 1 (Q) . (104)
Combining ( 103) with (104) we deduce that

[T 1 ] ε ≤ C, ∀ ε ∈ (0, 1). ( 105
)
Estimate of [T 2 ] ε . We claim that

ˆQ |∇g m | ≤ C, ∀ m ≥ 1, (106)
and this implies via (9) that

[g m ] ε ≤ C, ∀ m ≥ 1, ∀ ε ∈ (0, 1), so that [T 2 ] ε ≤ C(M 2 -M 1 ) ≤ C, ∀ ε ∈ (0, 1) (107)
(by ( 53)).

In order to prove (106), note that (108)

ˆQ |∇g m | = (N m ) n-1 k=1 H n-1 ([ f m = k]) = C (N m ) n-1 -1 k=1 1 - k (N m ) n-1 n-1 1 (N m ) n-1 = C (N m ) n-1 -1 ℓ=1 ℓ (N m ) n-1 n-1 1 (N m ) n-1 ≤ C.
Combining ( 105), ( 107) and (108) yields g ∈ B.

  Consider a sequence of points (b m ) m≥1 such that the open balls B(b m , 2/N m ) are contained in Q and mutually disjoint. (We may e.g. choose the points b m on a line segment parallel to the x 1 -axis.) Set

Q

  ε (a) ∩ (supp g m ) = . (98) Indeed, if (98) holds, thenQ ε (a) ∩ B(b m , 1/N m ) = ,and thusQ ε (a) ⊂ B(b m , 2/N m ) hand, (45) implies that N M 1 ≤ 4 ε 1/n ,and thus (100) holds when ε ≤ ε 0 := 1 4 n/(n-1) n n/[2(n-1)] .

  |g m (y) -g m (z)| d ydz (101) for some m ≤ M 1 (ε). If y, z ∈ Q ε (a), we have | f m (y) -f m (z)| ≤ |y -z| f m Lip ≤ (N m ) n n ε ≤ C(by (45)). Hence|g m (y) -g m (z)| ≤ C,(102)since|I(t) -I(s)| ≤ |t -s| + 1, ∀ t, s.Combining (101) and (102) yields M(T 1 ,Q ε (a)) ≤ C and therefore [T 1 ] ε ≤ C, ∀ ε ∈ (0, ε 0 ). (103)

  Estimate of [T 3 ] ε . The technique for estimating [S 3 ] ε in the proof of Proposition 3 gives[T 3 ] ε ≤ C, ∀ ε ∈ (0, 1).

Acknowlegments

The first author (JB) was partially supported by NSF grant DMS-1301619. The second author (HB) was partially supported by NSF grant DMS-1207793 and also by grant number 238702 of the European Commission (ITN, project FIRST). The third author (PM) was partially supported by the ANR project "Harmonic Analysis at its Boundaries", ANR-12-BS01-0013-03. PM thanks Saïd Jabrane for providing Figure 1.


M El-Abed

R Giot

B Hemery

C Charrier

C Rosenberger
email: christophe.rosenberger@greyc.ensicaen.fr

A SVM-Based Model For The Evaluation Of Biometric Sample Quality

Keywords: Biometrics, quality assessment, performance, Support Vector Machine (SVM), Scale-Invariant Feature Transform (SIFT)

One of the main factors affecting the performance of biometric systems is the quality of the acquired samples. Poorquality samples increase the enrollment failure, and decrease the system performance. Therefore, it is important for a biometric system to estimate the quality of the acquired biometric samples. Toward this goal, we present in this paper a multi-class SVMbased method to predict sample quality. The proposed method uses two types of information: the first one is based on the image quality and the second is a pattern-based quality using the SIFT keypoints extracted from the image. For the experiments, we use four large and significant face databases to show the efficiency of the proposed method in predicting the system performance illustrated by the Equal Error Rate (EER).

I. INTRODUCTION

Biometrics is considered as a promising solution among traditional methods based on "what we own" (such as a key) or "what we know" (such as a password) [START_REF] Mahier | Biometric authentication[END_REF]. It is based on "what we are" and "how we behave". Biometric authentication systems have many applications [START_REF] Jain | Biometrics: A grand challenge[END_REF] such as border control and e-commerce. The main benefits of this technology are to provide a better security and to facilitate the authentication process for a user. By contrast to traditional authentication methods (providing a 0% verification error), biometric systems are subject to errors computed by many metrics such as Failure to Acquire Rate (FTA), False Acceptance Rate (FAR) and False Rejection Rate (FRR) [START_REF]Information technology biometric performance testing and reporting[END_REF]. This inaccuracy is due to the variations of human characteristics (such as occlusions for iris recognition systems [START_REF] Krichen | A new probabilistic iris quality measure for comprehensive noise detection[END_REF]), environment factors (i.e., variation of acquisition conditions such as illuminations for face recognition systems [START_REF] Zhang | Asymmetry-based quality assessment of face images[END_REF]) and cross-device matching [START_REF] Poh | Quality-based score normalization with device qualitative information for multimodal biometric fusion[END_REF]. These kinds of variations may deeply affect biometric raw data quality. Poor-quality samples increase the enrollment failure rate, and decrease the system performance [START_REF] Zhang | Asymmetry-based quality assessment of face images[END_REF]. Therefore, quality assessment is considered as an important factor to take into account in both the enrollment and verification phases. Towards this goal, we propose a multi-class SVM-based method, to assess biometric raw data, which combines the use of image and pattern-based quality. Using quality information, the bad quality samples can be removed during the enrollment step or rejected during verification. Such information could also be used in soft biometrics or multimodal approaches [START_REF] Poh | A multimodal biometric test bed for quality-dependent, cost-sensitive and client-specific score-level fusion algorithms[END_REF], [START_REF] Poh | Benchmarking quality-dependent and cost-sensitive score-level multimodal biometric fusion algorithms[END_REF].

The outline of the paper is defined as follows. We present related previous research concerning biometric raw data quality in section II. Section III presents the proposed method. Section IV illustrates the experimental results on four large face benchmark databases. We conclude and give some perspectives of this work in section V.

II. BACKGROUND

The quality assessment of biometric raw data is receiving more and more attention in biometrics community. Many quality algorithms have been developed mainly for the fingerprint modality [START_REF] Tabassi | A novel approach to fingerprint image quality[END_REF], [START_REF] Vatsa | Quality induced fingerprint identification using extended feature set[END_REF], face [START_REF] Zhang | Asymmetry-based quality assessment of face images[END_REF], [START_REF] Sang | Face image quality evaluation for ISO/IEC standards 19794-5 and 29794-5[END_REF], iris [START_REF] Krichen | A new probabilistic iris quality measure for comprehensive noise detection[END_REF], voice [START_REF] Harriero | Analysis of the utility of classical and novel speech quality measures for speaker verification[END_REF] and signature signals [START_REF] Muller | Evaluating the biometric sample quality of handwritten signatures[END_REF]. These works have demonstrated that the performance of biometric systems is heavily affected by the quality of the acquired biometric data. Tabassi et al. present in [START_REF] Tabassi | A novel approach to fingerprint image quality[END_REF] a method based on the measurement of the matching scores to assess fingerprint quality. The proposed method uses a black box composed of two modules, feature extraction and neural network, which associates the image quality into five classes (excellent, very good, good, fair and poor). He et al. [START_REF] He | A hierarchical model for the evaluation of biometric sample quality[END_REF] present a hierarchical model to compute the biometric sample quality at three levels: database, class and image quality levels. The method is based on the quantiles of genuine and impostor matching score distributions. However, their model could not be used directly on a single capture (i.e., requires a pre-acquired database). Zhang et al. present in [START_REF] Zhang | Asymmetry-based quality assessment of face images[END_REF] an asymmetry-based quality assessment method of face images. The method uses SIFT descriptor for quality assessment. The presented method has shown its robustness against illumination and pose variations. Another asymmetry-based method is presented in [START_REF] Gao | Standardization of face image sample quality[END_REF]. However, this approach supposes the asymmetry hypothesis hence, could not be used for the others types of modalities. Other efforts [START_REF] Poh | A multimodal biometric test bed for quality-dependent, cost-sensitive and client-specific score-level fusion algorithms[END_REF], [START_REF] Poh | Benchmarking quality-dependent and cost-sensitive score-level multimodal biometric fusion algorithms[END_REF] have also been focused on the incorporation of biometric quality information to multimodal fusion approaches. Poh et al. present in [8] a quality-dependent evaluation campaign. It aims at assessing how well fusion algorithms can perform under changing the quality of raw biometric images. The results from this evaluation have shown that the best fusion methods are those that exploit automatically derived quality measurements.

Discussion

The works done in quality assessment are very few in comparison to performance ones [START_REF] Maio | Fvc2004: Third fingerprint verification competition[END_REF]. To our knowledge, most of the existing quality algorithms are modality and matcher dependent. The others, based on the genuine and impostor matching score distributions, could not be used directly on a single capture (i.e., they require a large number of captures for the same person in order to constitute its genuine score distribution). Therefore, the main contribution of this paper is the definition of a method which can be considered as independent from the used matching system. It detects in a reasonable accuracy three types of real alterations that may deeply affect the global performance of the most widely used matching systems. The presented method is not based on asymmetry hypothesis. Thus, it may be used for several types of modalities (such as fingerprint, face, hand and finger veins), and can be used directly on a single capture after training the model.

III. DEVELOPED METHOD

The proposed method is designed to predict the sample quality using two types of information. The first one is based on the image quality (section III-A) and the second is a patternbased quality using the SIFT keypoints extracted from the image (section III-B). The methodology principle is illustrated in figure 1: for an input image, the method constitutes a vector of both information and uses the multi-class Support Vector Machine (SVM) [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF] classifier to assign a class for an image.

A. No-reference image quality

The development of general-purpose no-reference approaches to image quality assessment (NR-IQA) still lags recent advances in full-reference methods. Additionally, most no-reference or blind approaches are distortion-specific, meaning they assess only a specific type of distortion assumed present in the test image (such as blockiness, blur, or ringing). This limits their application domain. Other approaches rely on training a machine learning algorithm. These methods however, are only as effective as the features used to train their learning machines. The used NR-IQA method in this paper is the BLIINDS index introduced by Saad et al. [START_REF] Saad | A DCT statistics-based blind image quality index[END_REF]. This index is based on a DCT framework entirely. This makes it computationally convenient, uses a commonly used transform, and allows a coherent framework. The BLIINDS index is defined from four features that are then pooled together: i) a contrast feature υ 1 , ii) a structure distortion based feature υ 2 and iii) iv) two anisotropic based measures υ 3 , υ 4 . Contrast is a basic perceptual attribute of an image. One may distinguish between global contrast measures and ones that are computed locally (and possibly pooled into one measure post local extraction). The contrast of the k th local DCT patch is computed as follows:

c k (x) = 1 N N i=1 x i AC x DC ( 1
)
where N is the patch size, x DC represents the DC coefficient and the set {x i AC | i = 1 : N } represents the AC coefficients. Then, the local contrast scores from all patches of the image are then pooled together by averaging the computed values to obtain a global image contrast value υ 1 :

υ 1 = 1 M M i=1 c i (x) ( 2
)
where M is the number of local patches. Structure features are derived locally from the local DCT frequency coefficients computed on a patch k. They are based on statistical traits of the DCT histogram for wich the DC coefficient is ignored. To measure these statistical traits of the DCT histograms of the patch k, its kurtosis is computed to quantify the degree of its peakedness and tail weight:

κ k (x AC ) = E(x AC -µ 4 ) σ 4 ( 3
)
where µ is the mean of x AC , and σ is its standard deviation.

Then the resulting values for all patches are pooled together by averaging the lowest tenth percentile of the obtained values to compute the global image kurtosis value υ 2 . As degradation processes damage a scenes directional information, anisotropy measure, which is a directionally dependent quality of images, is computed using the Renyi Entropy on DCT image patches along four different orientations θ = 0, 45, 90, 135 in degrees.

Each patch consists of the DCT coefficients of oriented pixel intensities. We discard the DC coefficient, since the focus is on directional information. Let the DCT coefficients of k th patch of orientation θ be denoted by P θ [k, j], where j is the frequency index of the DCT coefficient. Each DCT patch is then subjected to a normalization of the form:

Pθ [k, j] = P θ [k, j] 2 N j=1 P θ [k, j] 2 (4)
where N is the size of the oriented k th patch. Finally, the associated Renyi entropy R k θ is computed as

R k θ = 1 1 -β log 2 Pθ [k, j] β (5)
where β > 1. Finally, the two measures of anisotropy υ 3 and υ 4 are defined as

υ 3 = σ(E(R k θ )) and υ 4 = max(E(R k θ )), ∀k, ∀θ (6)
Due to the fact that the perception of image details depends on the image resolution, the distance from the image plane to the observer, and the acuity of the observers visual system, a multiscale approach is applied to compute the final global score as:

BLIINDS = M i=1 υ α i 1 1 υ α i 2 2 υ α i 3 3 υ α i 4 4 (7)
constraints by

4 j=1 M i=1 α i j = 1
and where M represents the number of decomposition level used.

B. Pattern-based quality

The pattern-based quality information used to contribute to quality assessment uses the Scales Invariant Feature Transform (SIFT) descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. SIFT algorithm consists of four major stages: i) scale-space extrema detection, ii) keypoint localization, iii) orientation assignment and iv) keypoint descriptor. In the first stage, potential interest points are identified, using a difference-of-Gaussian function, that are invariant to scale and orientation. In the second stage, candidate keypoints are localized to sub-pixel accuracy and eliminated if found to be unstable. The third stage identifies the dominant orientations for each keypoint based on its local image patch. The keypoint descriptor in the final stage is created by sampling the magnitudes and orientations of the image gradients in a neighborhood of each key-point and building smoothed orientation histograms that contain the important aspect of the neighborhood. Each local descriptor is composed of a 4x4 array (histogram). For each coordinate of this array, an 8 orientation vector is associated. A 128elements vector is then built for each keypoint. In other words, each image im is described by a set of invariant features X(im) = {k i = (s i , sc i , x i , y i )| i = 1 : N (im)} where s i is the 128-elements SIFT invariant descriptor computed near keypoints k i , (x i , y i ) its position in the original image im, sc i its scale and N (im) the number of detected keypoints for image im. The features extracted are invariant to image scaling and rotation, and partially invariant to change in illumination and 3D camera viewpoint. From these features, we use the following four metrics that we considered as potentially interesting (see section IV-B) to contribute to quality assessment: 1) keypoints: the number of keypoints detected from image im;

2) DC coefficient: DC coefficient of the matrix M s , with N (im) rows and 128 columns, related to SIFT invariant descriptor for s i , i = 1 : N (im) where N (im) is the number of detected keypoints for image im;

3) and 4) scales: mean and standard deviation of scales related to the keypoints detected from image im.

Therefore, the vector V used to predict biometric sample quality is a five-dimension vector containing image quality metric and four pattern-based metrics as depicted in table I.

C. Multi-class SVM classification

In order to predict biometric sample quality using both information (image quality and pattern-based quality), we use the Support Vector Machine (SVM). From all existing classification schemes, a SVM-based technique has been selected due to high classification rates obtained in previous works [START_REF] Lebrun | Fast pixel classification by svm using vector quantization, tabu search and hybrid color space[END_REF] and to their high generalization abilities. The SVMs were developed by Vapnik [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF] and are based on the structural risk minimization principle from statistical learning theory. SVMs express predictions in terms of a linear combination of kernel functions centered on a subset of the training data, known as support vectors (SV). In our study, the input vector to SVM is the vector V (as depicted in table I) and the output can belong to ten different classes defined as follows (see table II):

• class 1 illustrates a reference image;

• classes 2 to 10 illustrate 3 types of alterations and 3 levels for each type (see section experimental results for details about the introduced alterations). Suppose we have a training set {x i , y i } where x i is the training pattern and y i the label. For problems with two classes, with the classes y i ∈ {-1, 1}, a support vector machine [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF], [START_REF] Schölkopf | Learning with kernels : support vector machines, regularization, optimization, and beyond[END_REF] implements the following algorithm. First, the training points {x i } are projected into a space H (of possibly infinite dimension) by means of a function Φ(•). The second step is to find an optimal decision hyperplane in this space. The criterion for optimality will be defined shortly. Note that for the same training set, different transformations Φ(•) may lead to different decision functions. A transformation is achieved in an implicit manner using a kernel K(•, •) and consequently the decision function can be defined as :

f (x) = w, Φ(x) + b = ℓ i=1 α * i y i K(x i , x) + b (8)
with α * i ∈ R. The values w and b are the parameters defining the linear decision hyperplane. In SVMs, the optimality criterion to maximize is the margin, that is to say, the distance between the hyperplane and the nearest point Φ(x i ) of the training set. The α * i which optimize this criterion are obtained by solving the following problem :

       max αi ℓ i=1 α i -1 2 ℓ i,j=1 α i α j y i K(x i , x j y j ) with constraints, 0 ≤ α i ≤ C , ℓ i=1 α i y i = 0 . ( 9
)
where C is a penalization coefficient for data points located in or beyond the margin and provides a compromise between their numbers and the width of the margin. In this paper, we use the RBF kernel:

k(x i , x j ) = exp(-γ x i -x j 2 ) (10)
In order to train models with RBF kernels, we use a python script provided by the libsvm library [START_REF] Chang | LIBSVM: a library for support vector machines[END_REF]. This script automatically scales training and testing sets and searches the best couple (C, γ) of the kernel. The search of the best couple (C, γ) is done using a five-fold cross-validation computation.

Originally, SVMs have essentially been developed for the two classes problems. However, several approaches can be used for extending SVMs to multi-class problems. The method we use in this communication, is called one against one. Instead of learning N decision functions, each class is discriminated here from another one. Thus, N (N -1) decision functions are learned and each of them makes a vote for the affectation of a new point x. The class of this point x becomes then the majority class after the voting.

D. Discussion

The goal of the proposed method is to detect, in a reasonable accuracy, three real alterations which may deeply affect the most widely used matching systems. The proposed method may be considered as independent from the used matching system. An example of its practical use is illustrated in figure 2. The method predicts the class of the input image according to table II. Then, depending from the robustness of the used matching system against the predicted alteration, the matching system qualifies the image (good, fair or bad quality).

IV. EXPERIMENTAL RESULTS

In this section, we present the experimental results we obtained of the proposed method. The experimental protocol is presented in section IV-A. In order to validate our choice of the Fig. 2. An example of use of the method 5 used metrics (1 for image quality and the rest for the patternbased quality), we present in section IV-B the effectiveness of these metrics in detecting the three introduced alterations. In order to validate the proposed method, we present in section IV-C the SIFT matching algorithm as a use case. Finally, we show the efficiency of the proposed multi-class SVMbased quality method in predicting the performance of SIFT matching system using the Equal Error Rate (EER) metric. This error rate illustrates the overall system performance and is widely used to compare and evaluate the performance of biometric systems [START_REF]Information technology biometric performance testing and reporting[END_REF].

A. Protocol

In this study, we use four benchmark databases. For each database, we made three types of alterations (blurring, gaussian noise and resize alterations) and three levels for each type. The introduced alterations are commonly realistic during the acquisition of biometric data which may deeply affect the global performance of biometric systems. Finally, we have 40 databases: 4 reference databases and 36 altered databases (i.e., 9 for each reference database):

1) Reference databases:

• FACES94 Database [START_REF] Essex | Faces94 database, face recognition data[END_REF]: This database is composed of 152 individuals and 20 samples per individual. These images have been captured in regulated illumination and the variation of expression is moderated. 2) Altered databases: We generated 36 databases, using matlab, from the four reference databases: FACES94, ENSIB, FERET and AR databases. For each benchmark database, we generate three types of alterations and three levels for each type:

-Blurring alteration: blurring images are obtained using a two-dimensional Gaussian filter. To do so, we use the fspecial ('gaussian', hsize, σ) method which returns a rotationally symmetric Gaussian lowpass filter of size hsize with standard deviation σ; -Gaussian noise alteration: noisy images are obtained using the imnoise (I, 'gaussian', m, v) method. It adds Gaussian white noise of mean m and variance v to the image I; -Resize alteration: such kind of altered images are obtained using the imresize (I, scale, 'nearest') method. It resize the image I using a nearestneighbor interpolation.

Table III presents the parameters required of the used alteration matlab methods, and Figure 7 shows these alterations on a sample from FACES94 database.

B. Metrics behavior with alterations

In this section, we show the robustness of the used five metrics in detecting alterations presented in the previous section. To do so, we use the Pearson's correlation coefficient between two variables as defined in Eq. 11. It is defined as the covariance of the two variables divided by the product of their standard deviation:

P earson(X, Y ) = Cov(X, Y ) σ X σ Y (11)
In order to compute the correlation of the used metrics with the three types of alterations, we define for each type of alteration and for each metric p the variables as follows:

• X p = {X pk | k = 1 : 4} where X p1 is the set of values of metric p for the reference databases images, Table IV shows that our four pattern-based metrics (keypoints, DC coefficient, mean and standard deviation of scales) are pertinent in detecting the three types of alterations: blurring, gaussian noise and resize alterations. The image quality metric BLIINDS has shown to be efficient (with a correlation coefficient more than 0.6) in detecting blurring and gaussian noise alterations. For the resize alteration, BLIINDS has not shown to be efficient which is not a surprising result since resize alteration does not affect image quality (BLIINDS [START_REF] Saad | A DCT statistics-based blind image quality index[END_REF] is a multiresolution NR-IQA algorithm).

C. Biometric matching algorithm

The matching algorithm used in this paper is a SIFTbased [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] algorithm. The matching similarity principle used is described in previous works [START_REF] Ladoux | Hand vein verification system based on sift matching[END_REF]. Each image im is described by a set of invariant features X(im) as described in section III-B. The verification between two images im 1 and im 2 corresponds to compute a similarity between two sets of features X(im 1 ) and X(im 2 ). We thus use the following matching method which is a modified version of a decision criterion first proposed by Lowe [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Given two keypoints x ∈ X(im 1 ) and y ∈ X(im 2 ), we say that x is associated to y iff:

d(x, y) = min {z ∈ X(im2)} d(x, z) and d(x, y) ≤ C d(x, y′) (12)
where C is an arbitrary threshold, d(•, •) denotes the Euclidean distance between the SIFT descriptors and y′ denotes any point of X(im 2 ) whose distance to x is minimal but greater than d(x, y):

d(x, y′) = min {z ∈ X(im2), d(x,z)>d(x,y)} d(x, z) (13)
In other words, x is associated to y if y is the closest point from x in X(im 2 ) according to the Euclidean distance between SIFT descriptors and if the second smallest value of this distance d(x, y′) is significantly greater than d(x, y). The significance of the necessary gap between d(x, y) and d(x, y′) is encoded by the constant C. Then, we consider that keypoint x is matched to y iff x is associated to y and y is associated to x. Figure 8 illustrates an example of matching results resulting from an impostor and a genuine comparison. The number of associations is used here as a similarity measure.

D. Quality sets definition

The proposed multi-class SVM-based quality method predicts a class for an image. In order to quantify the efficiency of this method, we need first to define the quality sets for the used matching system. Depending on the used matching system, some alterations may not have an impact on it and others may deeply affect its performance. Therefore, we have tested the robustness of the used SIFT-based matching system against the introduced three alterations. We use the first image for the enrollment and the others for the test. We illustrate in table V the impact of adding altered images to the reference database images. We can clearly see that all the introduced alterations have shown an impact on system performance illustrated by the Equal Error Rate (EER). Therefore, we have defined for this study the four quality sets as depicted by table VI. Certainly, we may have choose another definition of sets that will more penalize the resize alteration (i.e., by putting label 9 in quality set IV) since it has the most impact on the used matching system.

E. Validation of the proposed quality method

According to Gother et al. [START_REF] Grother | Performance of biometric quality measures[END_REF], biometric quality measurement algorithms should predict the matching performance. That is, a quality measurement algorithm takes a biometric raw data, and produces a class or a scalar related to error rates associated to that sample. Therefore, we use the Equal Error Rate (EER) which illustrates the overall performance of a biometric system [START_REF]Information technology biometric performance testing and reporting[END_REF]. EER is defined as the rate when both False Acceptance Rate (FAR) and False Reject Rate (FRR) are equal: the lower EER, the more accurate the system is considered to be [START_REF]Information technology biometric performance testing and reporting[END_REF]. In order to validate our method, we proceed as follows: • EER value for each quality set: in order to quantify the effectiveness of our quality method in predicting system performance, we have put each image to a quality set (according to table VI), using its predicted label by our method. Then, we have calculated the EER value for each quality set. The effectiveness of the method is quantified by how well our quality method could predict system performance among the defined quality sets. More generally speaking, the more the images are degraded, the more the performance of the overall system will be decreased (illustrated by an increase of its EER value). Tables VIII and IX illustrate the EER values for each quality set among the four used benchmark databases, using the four multi-class SVM models computed from the four benchmark databases, and the multi-class SVM model computed by examples from the four benchmark databases, respectively. The proposed quality method has shown its efficiency in predicting the used matching algorithm performance. From tables VIII and IX, we can also conclude:

• for FACES94, ENSIB and AR benchmark databases, there were no significant difference between the EERs of the reference database (i.e., which is considered containing images of good quality) and the set predicted as good quality (set I) by our method; • for the FERET benchmark database, there was a difference of 5.62% (table VIII) and 5.64% (table IX). This variation was due to the difficulties of FERET database which contains altered images by resolution. Despite this, our method has also shown to be efficient in predicting system performance in both cases.

V. CONCLUSION AND PERSPECTIVES

The evaluation of biometric raw data is receiving more and more attention in biometrics community. We present in this paper a multi-class SVM-based method for predicting the quality of biometric raw data. The method uses both kinds of information (image and pattern-based quality) to predict sample quality. In order to validate the proposed method, we use four large and significant face databases (FACES94, ENSIB, FERET and AR) and three kinds of real alterations (blurring, gaussian noise and resolution), that affecting the most widely used matching systems. The method has shown efficient in predicting system performance, illustrated by the EER, among the four used benchmark databases. The method can be considered as independent from the used matching system. For example, if the used matching system tolerate resize alteration, we could modify the quality sets definition by putting their labels (i.e., labels 8, 9 and 10) in quality set I (i.e., we consider that the altered image, by resize alteration, may be considered as of good quality for this type of matching system). On the other hand, the method is not based on asymmetry hypothesis. Thus, it may be used for several types of modalities such as hand veins. The method also could be applied directly on a single capture after training the model.

For the perspectives, we would like to quantify the effectiveness of the method on other types of modality (such as iris, fingerprint) to test if the method can be considered as modalityindependent. We would also like to add another metric in order to detect luminance alteration, which also considered as an important alteration affecting biometric systems.

TERMS AND DEFINITIONS

Enrollment: The process of collecting biometric samples from a person and the subsequent preparation and storage of biometric reference templates representing that person's identity. False Acceptance Rate (FAR): Rate at which an impostor is accepted by an authentication system. False Rejection Rate (FRR): Rate at which the authorized user is rejected from the system. Equal Error Rate (EER): This error rate corresponds to the point at which the FAR and FRR cross (compromise between FAR and FRR).

Fig. 1 .

 1 Fig. 1. General scheme of the proposed method

Fig. 3 .

 3 Fig. 3. Samples from FACES94 • ENSIB Database [24]: It is composed of 100 individuals and 40 samples per individual. Each sample corresponds to one pose from the left one to the right.

Fig. 4 .

 4 Fig. 4. Samples from ENSIB • FERET Database [25], [26]: It is composed of 725 individuals with from 5 to 91 samples per individual (the average value is 11). Each sample corresponds to a pose angle, illumination and expression.

Fig. 5 .

 5 Fig. 5. Samples from FERET

Fig. 6 .

 6 Fig. 6. Samples from AR

Fig. 7 .

 7 Fig. 7. Alterations for a reference image from FACES94. From left to right, reference image then alteration level 1, 2 and 3

Fig. 8 .

 8 Fig. 8. Example of matching results resulting from a genuine (on the left) and an impostor comparisons (on the right)

•

  Learning the multi-class SVM models: we learn four multi-class SVM models using the images from the four benchmark databases (1 multi-class SVM per benchmark database illustrated by SV M each ), and 1 multi-class SVM model containing examples from the four benchmark databases (illustrated by SV M all ). In order to train and to test the multi-class SVM models, we split each benchmark database images into two sets S training and S test in a balanced way (i.e., both sets contain the same ratio of reference and altered images). The choice of the kernel used and the selection of the parameters required are presented in section III-C.

TABLE VI

 VI

		CATEGORY OF QUALITY
	Quality set	Predicted quality class by SVM	Description
	I	1	good
	II	2, 5 and 8	fair
	III	3, 6 and 9	poor
	IV	4, 7 and 10	very poor

  Table VII illustrates the accuracy of the produced multi-class SVM models on each benchmark database; • Quality sets definition: we have considered four quality sets as defined in table VI;

TABLE VIII EER

 VIII VALUES OF THE FOUR REFERENCE DATABASES AND OF EACH QUALITY SET AMONG THE FOUR BENCHMARK DATABASES. THESE EER VALUES ARE COMPUTED USING THE FOUR MULTI-CLASS SVM MODELS COMPUTED ON THE FOUR BENCHMARK DATABASES

			EER values (%)
	Database	reference	set I	set II	set III	set	IV
		database	(good)	(fair)	(poor)	(very poor)
	FACES94 0.29	0.62	0.7	1.74	5.89
	ENSIB	10.41	11.45	13.37	16.48	17.77
	FERET	26	31.62	31.82	32.35	35.5
	AR	9.6	10.26	11.82	16.15	16.81

TABLE IX EER

 IX VALUES OF THE FOUR REFERENCE DATABASES AND OF EACH QUALITY SET AMONG THE FOUR BENCHMARK DATABASES. THESE EER VALUES ARE COMPUTED USING THE MULTI-CLASS SVM MODEL COMPUTED USING EXAMPLES FROM THE FOUR BENCHMARK DATABASES

			EER values (%)
	Database	reference	set I	set II	set III	set	IV
		database	(good)	(fair)	(poor)	(very poor)
	FACES94 0.29	0.62	0.72	1.77	5.79
	ENSIB	10.41	11.21	13.4	16.61	17.64
	FERET	26	31.64	31.78	32.27	35.69
	AR	9.6	10.3	11.79	16.1	16.84

ACKNOWLEDGMENT

The authors would like to thank the French Research Ministry for their financial support of this work.