Pierre Hyvernat

Some Properties of Inclusions of Multisets and Contractive Boolean Operators

Keywords: multiset, system of representative, boolean operators 2000 MSC: 06A06, 06E30, 94C10

Consider the following curious puzzle: call an n-tuple X = (X 1 , . . . , X n ) of sets smaller than another ntuple Y if it has fewer unordered sections. We show that equivalence classes for this preorder are very easy to describe and characterize the preorder in terms of the simpler pointwise inclusion and the existence of a special increasing boolean operator f : B n → B n . We also show that contrary to increasing boolean operators, the relevant operators are not finitely generated, which might explain why this preorder is not easy to describe concretely.

Introduction: a puzzle

Let N be a (fixed) set and n be a (fixed) natural number. We can consider the following partial order on P * (N ) n , the collection of n-tuples of nonempty subsets of N :

X ⊆ Y def = 1≤i≤n X i ⊆ 1≤i≤n Y i
where i X i is the usual cartesian product. Because we restrict to nonempty subsets, this preorder coincide with pointwise inclusion:

(X 1 , . . . , X n ) ⊆ (Y 1 , . . . , Y n ) ⇐⇒ ∀1 ≤ i ≤ n, X i ⊆ Y i .
We now consider a commutative version of the cartesian product where instead of the usual ordered n-tuples, we take "unordered n-tuples".

Definition 1. If X = (X 1 , . . . , X n ) is an n-tuple of nonempty subsets of N , define S X , the set of unordered sections of X, as

S X def = 1≤i≤n X i S n , (1)
where /S n denotes quotienting by the action of the symmetric group S n .

Strictly speaking, S n does not really act on i X i but on N n . The notion is well-defined because the orbit of an element of i X i exists even if not all its elements are themselves in i X i . From now on, we will drop the adjective "unordered" and refer to an element of S X simply as a section of X. We now define the preorder ⊑ on P * (N ) n : Definition 2. If X and Y are n-tuples of nonempty subsets of N , we define X ⊑ Y to mean S X ⊆ S Y .

We write X ≈ Y for "X ⊑ Y and Y ⊑ X", that is, for S X = S Y .

The relation ⊑ is only a preorder because it is not antisymmetric: X σ(1) , . . . , X σ(n) ≈ (X 1 , . . . , X n ) for any permutation σ.

The aim of this note is to answer the following questions:

1. When do we have X ≈ Y ? 2. What is the relation between X ⊑ Y and X ⊆ Y ?

The problem is subtler than it appears and the first question makes for an interesting puzzle: while elementary, the proof is more complex than what most people initially think. Readers are thus encouraged to spend a couple of minutes playing with the problem before reading on.

Related notions. The notion of system of representatives was introduced by P. Hall in 1935 [START_REF] Hall | On representatives of subsets[END_REF]. A system of representatives for the n-tuple of sets X is simply an n-tuple x such that there is a permutation σ satisfying x i ∈ X σ(i) for each i ∈ {1, . . . , n}. Equivalence classes of those under permutations are exactly the unordered sections of X of Definition 1. A lot of attention has been devoted to systems of distinct representatives, also called transversals, where the components of x are pairwise distinct [START_REF] Mirsky | Transversal theory; an account of some aspects of combinatorial mathematics[END_REF]. Rather than looking at them individually, we look here at the collection of all possible systems of representatives. This shift of focus seems to be new in itself, as is the notion of contractive increasing boolean operator that appears later. Relating the two will give a concise answer to the second question. This work can also be seen as a first step toward a factor theory for commutative regular algebra [START_REF] Conway | Regular Algebra and Finite Machines[END_REF]. In his book on regular languages, John Conway develops a fascinating theory of factorization: if R is a regular set, a subfactorization is tuple of sets X of words satisfying X 1 • . . . • X n ⊆ R, where • denotes concatenation of regular sets. A subfactorization is a factorization if each X i is maximal and a factor of R is any such X i . Conway shows in particular that a regular set has only finitely many factors, and that they are all regular.

Conway devotes a chapter to commutative regular algebra, i.e. the theory arising from regular algebra when word concatenation is made commutative. Factor theory isn't part of this chapter, probably because "Commutative regular algebra is notable for the number of results whose proofs one would expect to be trivial, but which turn out to be very subtle." ( [START_REF] Conway | Regular Algebra and Finite Machines[END_REF], page 95). Commutative factor theory certainly looks very subtle and this work only gives a very partial answer: given the regular set Y 1 • . . . • Y n where each Y i is a set of symbols, we characterize it factorizations consisting of exactly n factors.

The initial motivation for this work comes from a very different area: denotational models of linear logic. In [START_REF] Hyvernat | Predicate transformers and linear logic: yet another denotational model[END_REF], the relation S X ⊆ T played an important role, where the set T was an arbitrary collection of n-multisets. Understanding this relation was necessary to compute small examples, and the preorder "⊑" naturally appeared in this way. (Note that the results of this paper are not to make those computation any easier than they were...) Notation. To make formulas less verbose, we will abuse the vector notation by lifting "∈" pointwise: just as X ⊆ Y means "∀1 ≤ i ≤ n, X i ⊆ Y i ", the notation a ∈ X is a synonym for "a i ∈ X i for all 1 ≤ i ≤ n". The (left) action of S n on n-tuples is written with a dot and is defined as σ • a def = a σ -1 (1) , . . . , a σ -1 (n) . When talking about n-multisets (orbits for the action of S n ), we identify an n-tuple with its orbit. In particular, a ∈ S X means that σ • a ∈ X for some permutation σ, i.e., that a i ∈ X σ(i) for all 1 ≤ i ≤ n.

The equivalence relation

The first question has a simple answer: equivalence is just equality up to a permutation of the sets. In other words, the failure of antisymmetry is captured by the remark coming after Definition 2. Proposition 1. Given any X and Y in P * (N ) n , we have

X ≈ Y ⇐⇒ ∃σ ∈ S n , σ • X = Y . ( 2
)
This proposition is slightly surprising because the left side is definitionally equal to

∀a ∈ X, ∃σ ∈ S n , σ • a ∈ Y and ∀b ∈ Y , ∃σ ′ ∈ S n , σ ′ • b ∈ X , (3)
while the right side is definitionally equal to

∃σ ∈ S n , ∀a ∈ X, σ • a ∈ Y and ∀b ∈ Y , σ -1 • b ∈ X .
That the latter implies the former is trivial. Proposition 1 asserts the converse: in (3), we can choose the permutation uniformly for all the a ∈ X and b ∈ Y ! Lemma 1. We have

1. If X ⊑ Y then, for all 1 ≤ j ≤ n, there is some 1 ≤ i ≤ n s.t. X i ⊆ Y j . 2. If X ≈ Y then X i0 = Y j0 for some pair i 0 , j 0 .
Proof. For the first point, suppose that there is some j 0 satisfying X i ⊆ Y j0 for all 1 ≤ i ≤ n. This means that there is an a ∈ X s.t. a i / ∈ Y j0 for all i. This a cannot be a section of Y . Contradiction! The second point follows easily: starting from Y 1 and repeatedly using the first point, we can construct an infinite sequence i 1 , j 2 , i 3 , j 4 , . . . satisfying:

• • • ⊆ X i 2k+1 ⊆ Y i 2k ⊆ • • • ⊆ X i3 ⊆ Y j2 ⊆ X i1 ⊆ Y 1
Because there are only finitely many possible indices, there are k and k ′ , with k < k ′ and i 2k = i 2k ′ . This implies that the sets X i 2k and Y j 2k+1 are equal. Thus, if X ≈ Y , one of the sets appears on both sides and we can start the construction of σ in (2). To finish the proof of Proposition 1 by induction on n, we need to show the following implication:

(Z, X 2 , . . . , X n ) ≈ (Z, Y 2 , . . . , Y n ) ⇒ (X 2 , . . . , X n ) ≈ (Y 2 , . . . , Y n ) . (4)
If the collection of unordered sections is seen as a "commutative cartesian product", the next definition would be the corresponding "division". Definition 3. Let T be a collection of n-multisets and Z ∈ P * (N ) we put

T ÷ Z def = (a 2 , . . . , a n ) | ∀a ∈ Z, (a, a 2 , . . . , a n ) ∈ T .
When Z = {a}, it is a commutative version of Brozozowski's derivative [START_REF] Brzozowski | Derivatives of regular expressions[END_REF], and in the general case, it corresponds to the commutative notion of factor of T with respect to Z [START_REF] Marin | On the computation of quotients and factors of regular languages[END_REF]. Implication (4) above follows from the following lemma:

Lemma 2. We have: S (X 1 , X 2 , . . . , X n ) ÷ X 1 = S (X 2 , . . . , X n ) . (5)
Proof. The "⊇" inclusion follows from the definition.

For the "⊆" inclusion, suppose (a 2 , . . . , a n ) ∈ S X ÷ X 1 and choose b ∈ X 1 . By hypothesis, we necessarily have (b, a 2 , . . . , a n ) ∈ S X , i.e., there is a permutation τ s.t. (b, a 2 , . . . , a n ) ∈ (X τ (1) , . . . , X τ (n) ).

If τ (1) = 1, then τ defines a permutation on {2, . . . , n} and we have (a 2 , . . . , a n ) ∈ (X τ (2) , . . . , X τ (n) ). We can conclude directly.

If τ (1) = 1, up to permuting the sets X 2 , . . . , X n and choosing an appropriate element in the orbit of (a 2 , . . . a n ), we can assume that τ (1) = 2, τ (2) = 1 and τ (i

) = i when 2 < i ≤ n, or in other words, that b ∈ X 2 , a 2 ∈ X 1 and a i ∈ X i whenever 2 < i ≤ n. Put a 1 def = a 2 . Because a 1 = a 2 ∈ X 1 , we have (a 1 , a 2 , . . . , a n ) ∈ S X by hypothesis, that is, σ • a ∈ X
for some permutation σ. Note that since a 1 = a 2 , we can interchange the values σ(1) and σ(2) and still have σ

• a ∈ X. Let k def = min i | i > 0, σ i (1) ∈ {1, 2} .
Up to changing the values of σ(1) and σ(2), we can assume that σ k (1) = 1 and that the set I def = {1, σ(1), . . . , σ k-1 (1)} is the cycle containing 1. We define the set I c as {1, . . . , n} \ I. Rearrange the columns of

a 1 • a 2 • . . . a i • . . . a n • |∈ |∈ |∈ |∈ • X σ(1) • X σ(2) . . . • X σ(i) . . . • X σ(n)
into two parts:

a 1 • a σ(1) • . . . a σ k-1 (1) • |∈ |∈ |∈ • X σ(1) • X σ 2 (1) . . . • X σ k (1) = X 1 I a 2 • . . . a i • . . . |∈ |∈ • X σ(2) . . . • X σ(i) . . . I c
.

The indices of X on the left are exactly those in I, and so are the indices of a. Thus, the indices of X and a on the right are exactly those in I c . This shows that (a i ) i∈I c is a section of (X i ) i∈I c . Also, because each of σ(1), . . . , σ k-1 (1) is strictly more than 2 (by the definition of k), we have a σ i (1) ∈ X σ i (1) for all 1 ≤ i ≤ k -1 by a previous hypothesis. This shows that the permutation ρ : {2, . . . , n} → {2, . . . , n}, ρ(i)

def = i if i ∈ {σ(1), . . . , σ k-1 (1)} σ(i) otherwise satisfies ρ • (a 2 , . . . , a n ) ∈ (X 2 , . . . , X n ).
This finishes the proof that (a 2 , . . . , a n ) is indeed a section of (X 2 , . . . , X n ).

The preorder

The initial question was not very formal and read as: "What is the relation between X ⊑ Y and X ⊆ Y ? " It is obvious that X ⊆ Y implies X ⊑ Y , but unfortunately, the converse does not hold, even if we consider ntuples of sets up to permutations. For example, we have

X := {3}, {1, 2, 3} ⊑ Y := {1, 3}, {2, 3}
because the sections of X are all sections of Y : [START_REF] Dedekind | Über Zerlegungen von Zahlen durch Ihre grössten gemeine-samen Theiler. Unknown[END_REF][START_REF] Conway | Regular Algebra and Finite Machines[END_REF], [START_REF] Dedekind | Über Zerlegungen von Zahlen durch Ihre grössten gemeine-samen Theiler. Unknown[END_REF][START_REF] Dedekind | Über Zerlegungen von Zahlen durch Ihre grössten gemeine-samen Theiler. Unknown[END_REF] .

S X = [3, 1], [3, 2], [3, 3] ⊂ S Y = [1, 2], [1, 3],
Lemma 1 asserts that each set on the right is a superset of some set on the left. This is indeed the case as both {1, 3} and {2, 3} are supersets of the same set {3}. However, one set on the left side is strictly bigger than all the sets on the right side: {1,

(Y i , Y j ) → (Y i ∩ Y j , Y i ∪ Y j )
on any pairs of coordinates, 4 will satisfy F (Y ) ⊑ Y . For example,

F (Y 1 , Y 2 , Y 3 ) def = Y 1 ∩ Y 3 , Y 2 ∩ (Y 1 ∪ Y 3 ), Y 2 ∪ (Y 1 ∪ Y 3 ) ⊑ Y 1 ∩ Y 3 , Y 2 , Y 1 ∪ Y 3 ⊑ Y 1 , Y 2 , Y 3 .
We will characterize (Proposition 3) which operators F on P * (N ) n satisfy F (Y ) ⊑ Y by looking at functions acting on tuples of booleans, i.e., boolean operators. We write elements of B n as words: for example, "011101 ∈ B 6 ". Definition 5. If a ∈ N and X ∈ P * (N ) n , the characteristic word of a along X is an element of B n . It is written χ X (a) and is defined by χ X (a

) i = 1 iff a ∈ X i .
Thus, χ X (a) describes in which components of X the element a appears, and |χ X (a)| is the number of the components of X which contain a. There is a necessary condition for X ⊑ Y : "for all a ∈ N , if a appears in k components of Y , then it appears in at most k components of X". Concisely, this condition can be written as "|χ X (a)| ≤ |χ Y (a)| for all a ∈ N ". This condition is reminiscent of the condition appearing in Hall's celebrated "marriage theorem" [START_REF] Hall | On representatives of subsets[END_REF]. Like in the marriage theorem, this condition is also sufficient in the appropriate setting: Proposition 2. Given X and Y two n-tuples of non-empty subsets of N that satisfy

1. the function a → χ Y (a) is bijective from N to B n \ {0 • • • 0}, 2. the function f : χ Y (a) → χ X (a), with domain B n \ {0 • • • 0} is increasing;
we have X ⊑ Y if and only if χ X (a) ≤ χ Y (a) for all a ∈ N .

Looking at the example {3}, {1, 2, 3} ⊑ {2, 3}, {1, 3} might help to understand the conditions of the proposition. The first condition means that there is exactly one element that belongs only to Y 1 ("2"), exactly one element that belongs only to Y 2 ("1") and exactly one element that belongs to both ("3"). When the first condition is satisfied, the second condition amounts to "when a appears in more sets than b on the right side, then a appears in more sets than b on the left side". The graph of the resulting function f can be read below a : We can extend this graph with a harmless 0

• • • 0 → 0 • • • 0 to obtain the function (b 1 , b 2 ) → (b 1 ∧ b 2 , b 1 ∨ b 2 ).
Proposition 2 follows from a more general lemma:

Lemma 3. We have X ⊑ Y iff f (u) def = χ Y (a)≤u χ X (a) satisfies |f (u)| ≤ |u| for all u.
The function f is the least increasing function (for the extensional order) satisfying f χ Y (a) ≥ χ X (a) for any a.

Proof. For the "⇐" implication, suppose that a ∈ X. We want to show that σ • a ∈ Y for some permutation σ. If we look at the bipartite graph

G a,Y G a,Y def = a 1 • a 2 • . . . a n • • Y 1 • Y 2 . . . • Y n
, with an edge between a i and Y j when a i ∈ Y j , finding a σ s.t. σ • a ∈ Y is equivalent to finding a perfect matching in G a,Y . By Hall's marriage theorem, this is equivalent to "every subset of {a 1 , . . . , a n } of cardinality p has at least p neighbors". Take some subset U ⊆ {a 1 , . . . , a n } of cardinality p. Because a is a section of X, this set has at least p neighbors in the corresponding G a,X graph. Let

u def = a∈U χ Y (a), if a ∈ U , then χ Y (a) ≤ u by definition of u, so that χ X (a) ≤ f (u) by definition of f . We thus have a∈U χ X (a) ≤ f (u). We get p ≤ a∈U χ X (a) # of neighboors of U in G a,X . ≤ |f (u)| ≤ |u| def = a∈U χ Y (a) # of neighboors of U in G a,Y .
, which concludes the "⇐" implication.

For the "⇒" implication, let X ⊑ Y and p = |u| < |f (u)|. By definition of f , we can find a set {a 1 , . . . , a k } ⊆ N which satisfies χ Y (a i ) ≤ u for i = 1, . . . , k and i≤k χ X (a i ) > p. In particular, we have

1≤i≤k χ Y (a i ) ≤ p < 1≤i≤k χ X (a i ) .
For each 1 in i≤k χ X (a i ) take one element of {a 1 , . . . , a k } that accounts for this 1. Call the resulting tuple a. Note that this might not be an n-tuple, but its length is strictly greater than p (and may contain repetitions). It is only a partial section of X: to complete it into a section of the whole X, simply add one element from each of the remaining (non-empty) sets. The result is also a section of Y and in particular, each element of a needs to fit in one component of Y . This is impossible because there are at most p sets Y j that can contain the elements of the tuple a. Contradiction! Lemma 3 does characterize the ⊑ preorder but still looks a little ad-hoc. We now give a more concise characterization that relates ⊑ with ⊆, thus answering our initial question. First note that we can lift any f : B n → B m to a function P(N ) n → P(N ) m :

Definition 6. Suppose f : B n → B m , define f : P(N ) n → P(N ) m as f Y def = X with a ∈ X i iff f χ Y (a) has a 1 at coordinate i .
This transformation is, in a precise categorical sense, natural. It amounts to lifting the boolean operations ∧ and ∨ to their set theoretic versions ∩ and ∪ in a way that is compatible with function composition. For example, with the "and/or" function

(b 1 , b 2 ) → (b 1 ∧ b 2 , b 1 ∨ b 2 ) we obtain (Y 1 , Y 2 ) → (Y 1 ∩ Y 2 , Y 1 ∪ Y 2 ).
Definition 7. Call an increasing function f :

B n → B n contractive if it satisfies |f (u)| ≤ |u| for all u ∈ B n .
A corollary to Lemma 3 is: Proposition 3. For any X and Y , we have

X ⊑ Y ⇐⇒ X ⊆ f Y for some increasing, contractive f : B n → B n .
Proof. We know that X ⊑ Y is equivalent to having |f (u)| ≤ |u| for all u in B n , where f is defined as in Lemma 3. This function f satisfies X ⊆ f (Y ): use

u def = χ Y (a) to check that a ∈ X i is an element of the i-th set of f (Y ).
For the converse, suppose f is contractive increasing with X ⊆ f (Y ) and let χ Y (a) ≤ u. Suppose that χ X (a) contains a 1 in position i. This means that a ∈ X i and thus a is in the i-th set of f (Y ). We can conclude that f χ Y (a) contains a 1 in position i. This implies that f (u) also contains a 1 in position i.

Contractive functions are not finitely generated

If one had a simple representation of contractive increasing boolean operators from B n to itself, then Proposition 3 would give a simple representation of the ⊑ preorder. It is well known that all boolean operators B n → B m with n inputs and m outputs can be represented by a boolean circuit using only "and", "or" together with "not" cells. Strictly speaking, we also need constant values and need a way to forget or duplicate inputs. The complete set of cells is depicted in Figure 1, where the last cells are:

• constants 1 and 0 (zero input, one output),

• drop (one input, zero output),

• duplicate (one input, two outputs),

• crossing (two inputs, two outputs). These cells, together with a finite set of relations expressing properties of the operations (associativity, etc.), give a finite presentation of the monoidal category of boolean operators. 5 We can generate the subcategory of increasing operators by removing the "not" cell from the generators. Unfortunately, no such thing is possible for contractive increasing boolean operators. In other words, any finite set of cells will either miss some contractive boolean operator, or generate some non contractive boolean operator.

First, a preliminary lemma:

Lemma 4. Let f : B n → B n be an increasing contractive boolean operator; the following are equivalent:

1. f is the action of a permutation u → σ • u for some σ ∈ S n , 2. f is bijective, 3. f is injective on words of weight 1.

Proof. Trivially, 1 implies 2 and 2 implies 3. Suppose now that f is increasing and contractive on B n . Suppose moreover that f is injective on words of weight 1. We can define a permutation σ on {1, . . . , n} by putting τ (i) = j iff f (e i ) = e j where e i represents the word with a single 1 in position i. If u contains a 1 in position i, then, because f is increasing, f (u) must contain a 1 in position τ (i). Because f is contractive, f (u) cannot contain more 1s than there are in u. Thus, the 1s of f (u) correspond exactly to the images of the 1s of u along τ : f is indeed the action of a permutation.

Proof (Proposition 4). Suppose, by contradiction, that there is a finite set of cells that generates all increasing contractive boolean operator, and write m for the maximal arity of the cells in this set. Any non-invertible function has a representation as in Figure 2 where

• the topmost rectangle contains only crossings (and invertible cells which are, by Lemma 4, equivalent to crossings),

• the cell C is not invertible and has arity c ≤ m,

• and the lowermost rectangle contains the rest of the circuit. By Lemma 4, we know that the cell C is not injective on inputs of weight 1. It means there are two input wires i 1 and i 2 s.t. C gives the same value on the two elements of B n consisting of 0s and a single 1 in position i 1 or i 2 . Because this is independent of the inputs v on the n -m remaining wires, we obtain:

Claim. Supposing contractive increasing boolean operators were finitely generated with a cells of arity less than m, then for any non-invertible contractive increasing boolean operator f :

B n → B n , with n ≥ m, we have: ∃σ ∈ S n ∀v ∈ B n-m f σ(01.0.v) = f σ(10.0.v) .
The permutation σ is used to simplify the notation: it reorders the wires to put i 1 and i 2 in positions 1 and 2, and the remaining input wires for C in positions 3, . . . , c.

For any maximal arity m, we will construct a (large) n together with a function f : B n → B n that contradicts this fact: whenever we choose input wires i 1 and i 2 and put any m -2 other input wires to 0, we can complete the remaining input wires in such a way that putting i 1 def = 0 and i 2 def = 1, or putting i 2 def = 0 and i 1 def = 1 makes a difference in the output of the function. Thus, this function will not be representable using the given set of cells. In almost all cases, this is better (and much easier to write) than the naive approach that checks if each a ∈ X is a section of Y , even if we are allowed to use an oracle to guess the permutations.

Definition 4 .

 4 Let B def = {0, 1} equipped with the order 0 ≤ 1. This is a complete lattice with operations written ∨ and ∧. The lattice structure is lifted pointwise to B n . If u ∈ B n , the weight of u is the number of 1s in u. It is written |u|.

1 Figure 1 :

 11 Figure 1: boolean cells

Proposition 4 .

 4 Contractive increasing boolean operators are not finitely generated.

  Figure 2: Circuits

  def c h e c k (N, n , X, Y ) : # N i s a set , n i s a n i n t e g e r , X / Y a r e t u p l e s o f s e t s . def c o m b i n a t i o n s (w ) : # g e n e r a t e s a l l v e c t o r s o f w e i g h t w # o m i t t e d ( s e e K n u t h , o r u s e y o u f a v o r i t e m e t h o d ) def sup ( u , v ) : # c o m p l e x i t y : O ( n ) # c o m p u t e s t h e p o i n t w i s e " o r " o n n -t u p l e s # o m i t t e d ( s i m p l e ) def w e i g h t ( u ) : # c o m p l e x i t y : O ( n ) # c o m p ut e s t h e w e i g h t o f a n n -t u p l e # o m i t t e d ( s i m p l e )def c h i ( a , Z ) : # c o m p l e x i t y : O ( n l o g ( z ) ) ( z i s c a r d i n a l i t y o f Z ) f o r i in r a n g e ( n ) :# w e u s e P y t h o n b u i l t i n " s e t " t y p e i f a inZ [ i ] : # s o t h a t " a i n Z [ i ] " m e a n " a b e l o n g s t o Z [ i ] " u [ i ] = 1 return u F = {} # F i s a f i n i te m a p w i t h a t m o s t 2 ^n e l e m e n t s , # a c c e s s i s l o g a r i t h m i c : O ( l o g ( 2 ^n ) ) = O ( n ) f o r a in N : # c o m p l e x i t y : c * chiX = c h i ( a , X) # n l o g ( x ) chiY = c h i ( a , Y) # + n l o g ( y ) F [ chiY ] = sup (F [ chiY ] , chiX ) # + 2 n f o r w in r a n g e ( n + 1 ) : # g e n e r a t i n g a l l t u p l e s f o r u in c o m b i n a t i o n s (w ) : # c o m p l e x i t y : a b o u t 2 ^n *v = F [ u ] # n f o r i in r a n g e ( n ) : # + n * i f u [ i ] == 1 : # u [ i ] = 0 # v = sup ( v , F [ u ] ) # n ^2 u [ i ] = 1 # F [ u ] = v # i f w e i g h t ( v ) > w : # + n return F a ls e return True # i f w e r e a c h e d t h i s far , t h e c o n d i t i o n i s s a t i s f i e d If N has cardinality c and the components of X and Y have cardinalities at most x and y; and if we suppose that the standard operations on sets and finite functions have logarithmic complexity, the hints in the comments give a total complexity of roughly O cn log(x) + log(y) + 2 n n 3 . Because both x = O(c) and y = O(c), we get a complexity of O nc log(c) + 2 n n 3 . If c is fixed, this is O(n 3 2 n ); if n is fixed, this is O c log(c) .

  More generally, Y 1 ∩Y 2 , Y 1 ∪Y 2 ) ⊑ Y 1 , Y 2 and any operator F on n-tuples of sets obtained by composing functions

2, 3} ⊃ {2, 3} and {1, 2, 3} ⊃ {1, 3}!

This work was partially funded by the French ANR project récré ANR-11-BS02-0010. Email address: Pierre.Hyvernat@univ-savoie.fr (Pierre Hyvernat) URL: http://lama.univ-savoie.fr/~hyvernat/ (Pierre Hyvernat)

provided the intersection isn't empty to agree with Definition 1

All of this has a precise algebraic meaning, see[START_REF] Lafont | Towards an algebraic theory of boolean circuits[END_REF] for details.

The complete file is available from http://lama.univ-savoie.fr/ ~hyvernat/research.php

Given a (large) n, define f : B n → B n as:

1 0 n-1 if |u| = 1

(2)

1110 0 n-4 if |u| = 3 but u not of the previous shape (5)

1 2k 10 0 n-2k-2 in all the remaining cases.

(

This function is contractive because we have |f (u)| = |u|. Moreover, it is increasing because whenever v is a successor 6 of u, we have f (v) > f (u):

Suppose input wires k 1 , . . . , k m-2 are fixed to 0 and we want to differentiate between input wires i 1 and i 2 , with i 1 < i 2 . By putting some 1s in the appropriate remaining wires, we can make f give different results when "i

• If there are two consecutive wires between i 1 and i 2 (but not touching i 2 ) which are not among k 1 , . . . , k m-2 , we put those two wires to 1 and all the other wires to 0. By lines (4) and (5) from the definition of f , we will get two different results.

• If not, the wires i 1 and i 2 cannot be too far apart. (There are at most 2m -2 wires between them...) If we can find a sequence of 2 k consecutive wires at distance 2 k to the left of i 1 , or a sequence of 2 k consecutive wires at distance 2 k to the right of i 2 , we can put those wires to 1 and the rest to 0. By lines [START_REF] Hall | On representatives of subsets[END_REF] and [START_REF] Knuth | A of The Art of Computer Programming[END_REF] or [START_REF] Hyvernat | Predicate transformers and linear logic: yet another denotational model[END_REF] and [START_REF] Knuth | A of The Art of Computer Programming[END_REF] of the definition of f , we will also get different results.

For this to work, we have to make sure n is big enough. At worst, the wires k 1 ,. . . , k m-2 can prevent us from finding an appropriate sequence m -2 times. In particular, if i 1 is big enough (bigger than 2 m+1 ), such a sequence is bound to happen. The same is true when i 2 is small enough compared to n. In the end, choosing n bigger than, say, 2 2m+2 plus an additional ε will guarantee that we can differentiate any i 1 and i 2 among any set of m wires. A more careful analysis shows that it is in fact enough to take n def = 2 m+1 + 4. This concludes the proof.

Appendix A. An algorithm

Proposition 3 is more elegant but Lemma 3 has an interesting byproduct: it gives a concrete algorithm to check if X ⊑ Y . For that, construct the function f from Lemma 3 and check that it satisfies the condition. Just as a proof of concept, here is the main part of the algorithm, in the Python programming language. Minor alterations have been made to make it more readable. The most difficult (and fun) part was to write the function combinations that generates all the vectors of length n and weight w using one of the subtle algorithms from [8]! 7


Vincent Duval
email: vincent.duval@ceremade.dauphine.fr

A comparative analysis of the TVL1 and the TV-G models

In this paper, we analyze the fine properties of the minimizers of the TVL1 and the TV-G models used in image processing. We describe the solutions of TVL1 by means of elementary morphological operations, and we exhibit a strong constraint on the structure part and the texture part of the data which is neccessary to obtain exact decompositions using the TV-G model.

For the past two decades, much interest has been given in variational models for image restoration (see [START_REF] Andreu-Vaillo | Parabolic quasilinear equations minimizing linear growth functionals[END_REF] and references therein). In the seminal work [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF] in image denoising, Rudin, Osher and Fatemi (ROF) proposed to find, given u ∈ L 2 (R 2 ), the function u which minimizes the energy

|Du| + 1 2λ |f -u| 2 . ( 1
)
Studying the above model in [START_REF] Meyer | Oscillating patterns in image processing and nonlinear evolution equations[END_REF], Meyer proposed to replace the L 2 fidelity term with norms which favor oscillations, so as to get a solution u which contains the structure and the geometric features of f , and a residual fu which contains the oscillating patterns of f , namely the texture and possibly some noise. This new paradigm has lead many researchers to investigate the use of various norms for the fidelity term. To our knowledge, the first attempt to perform numerically such decomposition was made by Vese and Osher in [START_REF] Vese | Modeling textures with total variation minimization and oscillating patterns in image processing[END_REF] by approximating the G space proposed by Meyer (the divergence of L ∞ vector fields) and the corresponding norm. Another approach to deal with the TV-G model (i.e. [START_REF] Allard | Total variation regularization for image denoising I: Geometric theory[END_REF] where the square L 2 norm is replaced with the norm of the G space) is proposed in [START_REF] Aujol | Image decomposition into a bounded variation component and an oscillating component[END_REF]. Variants of this model using decompositions with three terms (structure, texture and noise) have been investigated in [START_REF] Gilles | Noisy image decomposition: a new structure, texture and noise model based on local adaptivity[END_REF][START_REF] Gilles | Image decomposition: Theory, numerical schemes, and performance evaluation[END_REF]. In [START_REF] Osher | Image decomposition and restoration using total variation minimization and the H -1 norm[END_REF], another variant of this model is proposed which corresponds to the space W -1,2 . This approach is generalized in [START_REF] Aujol | Dual norms and image decomposition models[END_REF][START_REF] Aujol | Constrained and SNR-based solutions for TV-Hilbert space image denoising[END_REF], where T V + H decompositions are considered, with H a Hilbert space. In this context, negative Sobolev spaces have drawn a lot of attention: see [START_REF] Aujol | Dual norms and image decomposition models[END_REF][START_REF] Lieu | Image restoration and decomposition via bounded total variation and negative Hilbert-Sobolev spaces[END_REF][START_REF] Kim | Image recovery using functions of bounded variation and sobolev spaces of negative differentiability[END_REF]. Two other spaces initially proposed by Meyer are E (the dual of the Besov space Ḃ1

1,1 ) investigated in [START_REF] Aujol | Dual norms and image decomposition models[END_REF][START_REF] Garnett | Image decompositions using bounded variation and generalized homogeneous besov spaces[END_REF], and F (the divergence of vector fields in BMO) studied in [START_REF] Le | Image decomposition using total variation and div(bmo)[END_REF].

Yet, the search for new fidelity terms did not focus only on oscillating norms, and Chan and Esedoglu considered in [START_REF] Chan | Aspects of total variation regularized L 1 function approximation[END_REF] the following energy

|Du| + λ R 2 |f -u|, (2)
importing in image processing a model which had been introduced in signal processing by Alliney [START_REF] Alliney | Recursive median filters of increasing order : a variational approach[END_REF][START_REF] Alliney | Digital filters as absolute norm regularizers[END_REF] and studied by Nikolova [START_REF] Nikolova | Minimizers of cost-functions involving non-smooth data-fidelity terms. application to the processing of outliers[END_REF][START_REF] Nikolova | A variational approach to remove outliers and impulse noise[END_REF][START_REF] Nikolova | Weakly constrained minimization. application to the estimation of images and signals involving constant regions[END_REF]. In dimension N = 1, an important property of the model, highlighted in [START_REF] Nikolova | Minimizers of cost-functions involving non-smooth data-fidelity terms. application to the processing of outliers[END_REF], is its ability to preserve exactly some signals. In dimension N 2, this property still holds, but contrary to the dimension N = 1, the geometry has a strong influence on the solutions, as studied in [START_REF] Chan | Aspects of total variation regularized L 1 function approximation[END_REF][START_REF] Haddad | Texture separation: BV -G and BV -L 1 models[END_REF][START_REF] Yin | The total variation regularized L 1 model for multiscale decomposition[END_REF][START_REF] Vixie | Some properties of minimizers for the Chan-Esedoglu L 1 TV functional[END_REF][START_REF] Morgan | L 1 TV computes the flat norm for boundaries[END_REF]. In particular, the link with the flat norm used in geometric measure theory is observed in [START_REF] Morgan | L 1 TV computes the flat norm for boundaries[END_REF]. Probably, the most remarkable property of this model, observed by Darbon in [START_REF] Darbon | Total variation minimization with L 1 data fidelity as a contrast invariant filter[END_REF], is its contrast invariance. Namely, if g is an increasing function and u is a solution for data f , g • u is a solution associated to g • f . Such a property is fundamental in image processing, and has been highly considered from the early years of image processing and mathematical morphology (see below) to the axiomatic approach to PDE's in image processing [START_REF] Alvarez | Axioms and fundamental equations of image processing[END_REF][START_REF] Guichard | Contrast invariant image analysis and PDE's[END_REF] and the tree of shapes studied in [START_REF] Monasse | Scale-space from a level lines tree[END_REF][START_REF] Ballester | The tree of shapes of an image[END_REF] (see also [START_REF] Caselles | Geometric Description of Images As Topographic Maps[END_REF] and references therein). Meanwhile, tremendous progress has been made in the understanding of the Rudin-Osher-Fatemi (ROF) model and the total variation flow, thanks to the work of Caselles and his collaborators [START_REF] Andreu | Minimizing total variation flow[END_REF][START_REF] Andreu | The dirichlet problem for the total variation flow[END_REF][START_REF] Andreu | Some qualitative properties for the total variation flow[END_REF][START_REF] Bellettini | The total variation flow in R N[END_REF][START_REF] Bellettini | Explicit solutions of the eigenvalue problem div Du |Du| = u in R 2[END_REF][START_REF] Alter | Evolution of convex sets in the plane by minimizing the total variation flow[END_REF][START_REF] Caselles | The discontinuity set of solutions of the tv denoising problem and some extensions[END_REF], and to the work of Allard [START_REF] Allard | Total variation regularization for image denoising I: Geometric theory[END_REF][START_REF] Allard | Total variation regularization for image denoising II: Examples[END_REF][START_REF] Allard | Total variation regularization for image denoising III: Examples[END_REF]. Giving a rigorous meaning to the total variation flow [START_REF] Andreu | Minimizing total variation flow[END_REF][START_REF] Andreu | The dirichlet problem for the total variation flow[END_REF]

∂u ∂t = div Du |Du| , (3)
Caselles and his coauthors have proved existence and uniqueness of a solution for any initial data u 0 ∈ L 2 (R 2 ). The solution vanishes in finite time and, up to a renormalization, it converges to a solution of the eigenvalue problem:

u = -div Du |Du| . (4)
The solutions of (4) are the functions which evolve at constant speed in (3) and the functions that evolve in (1) by the multiplication of a constant. Focussing on characteristic functions of sets which satisfy (4), the authors of [START_REF] Bellettini | The total variation flow in R N[END_REF][START_REF] Bellettini | Explicit solutions of the eigenvalue problem div Du |Du| = u in R 2[END_REF] were lead to study the class of calibrable sets. It turns out that these sets are intimately linked with the so-called Cheeger sets. Given a domain Ω, a Cheeger set of Ω is a solution to the problem inf

E⊆Ω Per E |E| , ( 5
)
where |E| is the N -dimensional Lebesgue measure of E and Per E its perimeter (see below). If the domain Ω is convex, Ω is itself a solution to [START_REF] Alliney | Recursive median filters of increasing order : a variational approach[END_REF] if and only if it is calibrable (see [START_REF] Andreu-Vaillo | Parabolic quasilinear equations minimizing linear growth functionals[END_REF]). The deep results in [START_REF] Alter | Evolution of convex sets in the plane by minimizing the total variation flow[END_REF][START_REF] Alter | A characterization of convex calibrable sets in R N[END_REF] and later in [START_REF] Caselles | Some remarks on uniqueness and regularity of cheeger sets[END_REF][START_REF] Alter | Uniqueness of the cheeger set of a convex body[END_REF] yield a characterization of Cheeger sets in convex domains by their mean curvature, as well as a uniqueness result for non trivial convex bodies (i.e. convex compact sets with nonempty interior). They also describe precisely the evolution of convex sets by the total variation flow (eq. ( 3)) and the Rudin-Osher-Fatemi problem (eq. ( 1)). Independently, Allard has also proposed a thorough study of the models TV+L p (p 1) in [START_REF] Allard | Total variation regularization for image denoising I: Geometric theory[END_REF][START_REF] Allard | Total variation regularization for image denoising II: Examples[END_REF][START_REF] Allard | Total variation regularization for image denoising III: Examples[END_REF], obtaining similar results, notably in the case of convex sets. The present paper summarizes several results developed in the PhD thesis [START_REF] Duval | Variational and non-local methods in image processing: a geometric study[END_REF]. Our purpose is to describe as precisely as possible the solutions of the TVL1 (eq. ( 2)) and the TV-G models. In particular, we relate the TVL1 model with morphological openings, and we give examples of structure-texture decomposition using the TV-G model. Incidentally, the proposed results provide an extension of the comparison initiated by Haddad in [START_REF] Haddad | Texture separation: BV -G and BV -L 1 models[END_REF] and Yin et al. in [73] between both models. Whereas [START_REF] Haddad | Texture separation: BV -G and BV -L 1 models[END_REF] emphasizes the similitudes between the two models, we highlight fine properties of the minimizers which make the models eventually different. An illustration is given in Figure 1. Both models are able to separate the stripes from the clothes, but the solution provided by the TV-G model looks more inflated than the one of the TVL1 model (which looks flat). Our analysis gives some insight on the qualitative difference between both results.

The first section deals with preliminaries and notations. The second one is devoted to the TVL1 model, and it covers material published in [START_REF] Duval | The TVL1 Model: a Geometric Point of View[END_REF]. Relying on the deep results mentioned above (in particular [START_REF] Bellettini | Explicit solutions of the eigenvalue problem div Du |Du| = u in R 2[END_REF][START_REF] Alter | Evolution of convex sets in the plane by minimizing the total variation flow[END_REF][START_REF] Alter | A characterization of convex calibrable sets in R N[END_REF]) we show the link between TVL1 and the Cheeger problem, and we obtain a characterization of the solutions in terms of morphological openings. This provides some insight on the behavior of the solutions as well as a way to compute approximations of solutions by means of classical morphological operators. Moreover it explains the good behavior of the model for structure-texture decomposition. In the third section, we analyze the TV-G model. After recalling the characterization of solutions, we exhibit toy examples which predict a perfect decomposition between structure and texture. Then we point out a limitation of the model which prevents perfect decompositions to happen in the general case: oscillations must appear in the texture part around the edges of the image. This phenomenon, which explains the inflated look of the decompositions, does not affect the TVL1 model.

Preliminaries 1.Functions of bounded variations

We briefly recall some properties of functions of bounded variations and sets of finite perimeter. We refer the reader to [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems. Oxford mathematical monographs[END_REF] for a comprehensive treatment of the subject.

Definition 1. A function u ∈ L 1 (R 2
) is said to be of bounded variation if its distributional gradient is a vector valued Radon measure with finite total

|Du|(Ω) = sup R 2 u div ϕ/ ϕ ∈ C 1 c (Ω, R 2 ), ∀x ∈ Ω, |ϕ(x)| 1 (6)
(where for v = (v 1 , v 2 ) ∈ R 2 , |v| 2 = v 2 1 + v 2 2
). When Ω = R 2 , this quantity is called the total variation of u, and will be denoted by |Du| or |u| T V .

The mapping u → |Du|(Ω) is L 1 loc (R 2 ) lower semi-continuous. If E is a measurable set, we denote by |E| the 2-dimensional Lebesgue measure of a set E ⊆ R 2 , and by

H 1 (E) its 1-dimensional Hausdorff measure in R 2 .
The set E is said to be of finite perimeter if ( 6) is finite (with Ω = R 2 ) when u is replaced with the characteristic function 1 E of E. Its perimeter is defined as

Per E = |D1 E |.
If E ⊆ R 2 is a Lebesgue measurable set, and x ∈ R 2 , the upper and lower densities of E at x are respectively defined by:

D(x, E) := lim sup r→0 |B(x, r) ∩ E| |B(x, r)| , D(x, E) := lim inf r→0 |B(x, r) ∩ E| |B(x, r)| ,
where B(x, r) is the Euclidean closed ball with radius r > 0 and center x.

Lebesgue's density theorem states that for any measurable set E both quantities are equal to 1 at almost every point of of E. Hence, the set {x ∈ R 2 , D(x, E) = D(x, E) = 1} is a Lebesgue representative of E, independent of the choice of representative for E. We shall choose this precise representative, and ∂E, E shall refer respectively to the topological boundary and interior of this representative.

Following the framework of [START_REF] Andreu-Vaillo | Parabolic quasilinear equations minimizing linear growth functionals[END_REF], we rely on the results of [START_REF] Anzellotti | Pairing between measures and bounded functions and compensated compactness[END_REF] for a generalization of the Gauss-Green theorem. Let Ω ⊆ R 2 be an open subset, and for p ∈ [1, +∞],

X p (Ω) := {z ∈ L ∞ (Ω, R 2 ), div z ∈ L p (Ω)}. ( 7
)
If z ∈ X p (Ω) and w ∈ L q (Ω) ∩ BV(Ω) with p -1 + q -1 = 1, we define the functional (z, Dw) : C ∞ c (Ω) → R by the formula:

(z, Dw), ϕ := - Ω wϕ div zdx - Ω wz • ∇ϕdx. (8)
In fact, (z, Dw) is a Radon measure in Ω, and for all Borel set B ⊂ Ω:

B (z, Dw) B |(z, Dw)| z ∞ B |Dw|. (9)
Moreover, if

w ∈ L q (Ω) ∩ W 1,1 , Ω (z, Dw) = Ω z • ∇wdx.
The following theorem is proved in [START_REF] Anzellotti | Pairing between measures and bounded functions and compensated compactness[END_REF]:

Theorem 1. Let Ω ⊂ R 2 be
a bounded open set with Lipschitz boundary. Let u ∈ BV(Ω) ∩ L q (Ω) and z ∈ X p (Ω). Then there exists a function

[z • ν Ω ] ∈ L ∞ (∂Ω) such that [z • ν Ω ] L ∞ (∂Ω) z L ∞ (Ω,R 2 ) ,
and

Ω u div zdx + Ω (z, Du) = ∂Ω [z • ν Ω ]udH 1 .
When Ω = R 2 , we have the following formula [START_REF] Anzellotti | Pairing between measures and bounded functions and compensated compactness[END_REF], for z ∈ X p (R 2 ) and w ∈ L q (R 2 ) ∩ BV(R 2 ):

R 2 w div zdx + R 2 (z, Dw) = 0. ( 10
)
Using the above integration by parts, it is possible to describe the subdifferential ∂| • | T V of the total variation. This is done in particular in [START_REF] Andreu | Minimizing total variation flow[END_REF][START_REF] Andreu-Vaillo | Parabolic quasilinear equations minimizing linear growth functionals[END_REF] in order to define the meaning of the total variation flow.

Let p ∈ L ∞ (R 2 ), then p ∈ ∂| • | T V (u) if and only if there exists z ∈ L ∞ (R 2 , R 2 ) such that z ∞ 1, p = -div z and R 2 -div z(x)u(x)dx = |Du|. (11)
In view of ( 10), the last equality may be rewritten R 2 (z, Du) = |Du|.

The G-space

Yves Meyer introduced the G-space in [START_REF] Meyer | Oscillating patterns in image processing and nonlinear evolution equations[END_REF] while studying the ROF problem, so as to model oscillating patterns like textures. Several variants of the definition have been used in the literature (see [START_REF] Aujol | Modeling very oscillating signals. Application to image processing[END_REF] for a definition on a bounded domain), we adopt the one in [START_REF] Kindermann | Denoising by bv-duality[END_REF].

Definition 2. A function f ∈ L 2 (R 2 ) belongs to G if and only if there exists a vector field g ∈ L ∞ (R 2 , R 2 ) such that div g = f . The G-norm is defined as: f G := inf g ∞ , f = div g, g ∈ L ∞ (R 2 , R 2 ) . (12)
In fact, this infimum is a minimum, i.e. there exists g ∈ L ∞ (R 2 , R 2 ) such that div g = f and g ∞ = f G . In that case we say that g is adapted to v.

The G-norm can alternatively be written in a "dual" form (see [START_REF] Haddad | An improvement of rudin-osher-fatemi model[END_REF][START_REF] Kindermann | Denoising by bv-duality[END_REF]),

f G = sup u∈BV(R 2 )\{0} R 2 f u |Du| . (13)
The G-norm defines a coarser topology than the L 2 norm. More precisely, it is proved in [START_REF] Haddad | An improvement of rudin-osher-fatemi model[END_REF][START_REF] Kindermann | Denoising by bv-duality[END_REF]

that f G 1 2 √ π f 2 for all f ∈ L 2 (R 2
). The main motivation for introducing the G-norm is indeed that it does not penalize oscillating patterns. For instance, as explained in [START_REF] Meyer | Oscillating patterns in image processing and nonlinear evolution equations[END_REF]

, if f (x 1 , x 2 ) = 1 [0,1] 2 (x 1 , x 2 ) cos (N πx 1 ), then f G = 1 N . More generally, Proposition 1 ([47], Corollary 3.4). Let Q = [0, 1] 2 , f ∈ L 2 (R 2 ) and µ ∈ L ∞ (R 2 ) such that Q+k µ(x)dx = 0, for all k ∈ Z 2 . Then, f (•)µ(N •) G → 0 when N → +∞.
Following the method used in [START_REF] Andreu-Vaillo | Parabolic quasilinear equations minimizing linear growth functionals[END_REF] to characterize the subdifferential of the total variation, we may compute the subdifferential of the G-norm by observing that it is the support function of the closed convex set

A = {u ∈ L 2 (R 2 ), |Dv| 1}. Thus, given p ∈ L 2 (R 2 ), u ∈ G, p ∈ ∂ • G (u) if and only if |Dp| 1 and R 2 p(x)u(x)dx = u G . ( 14
)

Mathematical morphology

Mathematical morphology is a theory of image analysis initiated by Matheron and Serra in the 1960's. Its main focus is the contrast-invariance in image processing, and the consequence is that morphological operators can be equivalently seen as operators on functions (images) or on sets (their level-sets). For instance, some of the most famous morphological operators are respectively the erosion and dilation: for

X ⊆ R 2 , E r X = x ∈ R 2 , B(x, r) ⊂ X , D r X = y ∈ R 2 , ∃x ∈ E, y ∈ B(x, r) , (15)
where r > 0 and B(x, r) is the Euclidean closed ball with radius r. These operators on sets are associated with functional operators:

∀u ∈ R R 2 , ∀x ∈ R 2 , E r u(x) = inf y∈B(0,r) u(x + r), D r u(x) = sup y∈B(0,r) u(x + r). (16)
As a matter of fact, it is equivalent to apply each functional operator to a function f or to apply the corresponding set operator on the upper level-sets of f , F t = {x ∈ R 2 , f (x) t}, to obtain sets U t for t ∈ R and then reconstruct u by the formula:

∀x ∈ R 2 , u(x) = sup{t ∈ R, x ∈ U t }. (17)
From dilations and erosions, two other basic operators are constructed: openings (defined as D r • E r ) and closings (defined as E r • D r ). The corresponding set operators may be written as: for

X ⊆ R 2 , O r X = {B(x, r), B(x, r) ⊂ X}, C r X = {B(x, r), B(x, r) ⊂ X C } C , (18)
where

X C = R 2 \ X.
Standard references about mathematical morphology are the book by Matheron [START_REF] Matheron | Random Sets and Integral Geometry[END_REF] and those by Serra [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]. From the fundamental axioms established by Matheron and Serra, and the basic operations such as erosions, dilations, openings and closings, mathematical morphology has grown into a wellestablished theory from which derive algorithms for image denoising [START_REF] Cheng | An adaptive morphological filter for image processing[END_REF][START_REF] Vincent | Grayscale area openings and closings, their efficient implementation and applications[END_REF], segmentation [START_REF] Beucher | Use of watersheds in contour detection[END_REF][START_REF] Bouraoui | Fully automatic 3d segmentation of coronary arteries based on mathematical morphology[END_REF], texture analysis [START_REF] Vanrell | Mathematical morphology, texture perception and granulometries[END_REF][START_REF] Hanbury | Analysis of oriented textures using mathematical morphology[END_REF], etc.

A geometric characterization of solutions for TVL1 model 2.1 A geometric equivalence property

Given f ∈ L 1 (R 2 ), the TVL1 model consists in solving the variational problem

inf u∈BV(R 2 ) R 2 |Du| + λ R 2 |f -u| . (P λ (f ))
Existence of a solution follows from the direct method of the calculus of variations. Since the problem is not strictly convex, Problem (P λ (f )) may have more than one solution.

Following the fruitful approach of [START_REF] Chambolle | An algorithm for mean curvature motion[END_REF][START_REF] Alter | A characterization of convex calibrable sets in R N[END_REF] for the study of the Rudin-Osher-Fatemi problem, Chan and Esedoglu have observed in [START_REF] Chan | Aspects of total variation regularized L 1 function approximation[END_REF] (see also [START_REF] Darbon | Image restoration with discrete constrained total variation part I: Fast and exact optimization[END_REF]) that the energy in (P λ (f )) may be written as a sum of energies for the level sets of u,

|Du| + λ |f -u| = +∞ -∞ Per U t + λ|U t ∆F t |dt, (19)
where

U t = {x ∈ R 2 , u(x) t} denotes the t-upper level set of u and F t = {x ∈ R 2 , u(x) t} is the t-upper level set of F .
This consequence of the coarea formula has lead several authors (see [START_REF] Chan | Aspects of total variation regularized L 1 function approximation[END_REF][START_REF] Darbon | Image restoration with discrete constrained total variation part I: Fast and exact optimization[END_REF][START_REF] Yin | The total variation regularized L 1 model for multiscale decomposition[END_REF][START_REF] Allard | Total variation regularization for image denoising I: Geometric theory[END_REF][START_REF] Duval | The TVL1 Model: a Geometric Point of View[END_REF]) to study the connection between (P λ (f )) and the geometric problem

inf U ⊆R 2 Per U + λ|U ∆F | (G λ (F ))
where

F ⊆ R 2 is a measurable set such that L 2 (F ) < +∞ or L 2 (R 2 \ F ) < +∞.
In fact, applying the general method detailed in [START_REF] Chambolle | An introduction to Total Variation for Image Analysis[END_REF], one may show that

u ∈ L 1 (R 2 ) is a solution to (P λ (f )) if and only if for all t ∈ R, its level set U t is a solution to G λ (F t ), where F t = {x ∈ R 2 , u(x) t}.
Instead of solving (P λ (f )), one may study the solutions of G λ (F t ) for all t ∈ R, and then reconstruct u by the formula:

u(x) = sup {t ∈ R, x ∈ U t }, (20)
as done in [START_REF] Yin | The total variation regularized L 1 model for multiscale decomposition[END_REF][START_REF] Allard | Total variation regularization for image denoising I: Geometric theory[END_REF][START_REF] Morgan | L 1 TV computes the flat norm for boundaries[END_REF][START_REF] Duval | The TVL1 Model: a Geometric Point of View[END_REF].

TVL1 Geometric Measure Theory

A remarkable property of Problem (G λ (F )) is the fact that its solutions have smooth boundary. This was derived by Allard in [START_REF] Allard | Total variation regularization for image denoising I: Geometric theory[END_REF], and independently in [START_REF] Duval | The TVL1 Model: a Geometric Point of View[END_REF][START_REF] Duval | Variational and non-local methods in image processing: a geometric study[END_REF] by the present author with coauthors by applying results from [START_REF] Ambrosio | Corso introduttivo alla teoria geometrica della misura ed alle superfici minimime[END_REF].

Proposition 2. Let F ⊆ R 2 , and let U ∈ R 2 be a solution of G λ (F ). Then ∂U is a C 1,1 hypersurface. Its curvature κ is defined H 1 -
almost everywhere and for

H 1 -almost every x ∈ F (resp. x ∈ ˚ (R 2 \ F )), κ(x) = -λ (resp. +λ). Moreover for H 1 -a.e. x ∈ ∂U , |κ(x)| λ.
An interpretation of Proposition 2 is that as soon as ∂U drifts away from ∂F , it is made of arcs of circles with radius 1 λ . The enlightening example of the union of two discs is studied in [START_REF] Allard | Total variation regularization for image denoising III: Examples[END_REF][START_REF] Caselles | Tv denoising of the characteristic function of two balls in the plane[END_REF] (see Figure 2). It is shown that for two discs that are sufficiently close to each other, the solution is either the two disc, the empty set or the figure obtained by joining the discs with arcs of radius 1 λ , depending on the value of λ. In contrast with the above example, some sets F do not evolve when solving G λ (F ) for large values of λ, and then suddenly vanish when λ is below a certain threshold λ F . This is for instance the case of a single disc, as studied in [START_REF] Chan | Aspects of total variation regularized L 1 function approximation[END_REF]. As we observed in [START_REF] Duval | The TVL1 Model: a Geometric Point of View[END_REF], such sets are necessarily Cheeger in themselves.

Proposition 3. Let F ⊆ R 2 be a nonempty set such that there exists λ F > 0 such that

• F is a solution of G λ (F ) for λ > λ F , • ∅ is a solution of G λ (F ) for λ < λ F . Then, λ F = Per F |F | , and F is Cheeger in itself, i.e. it is a solution of the problem inf U ⊆F Per U |U | . (C(F ))
Moreover, the solution to G λ (F ) for λ = λ F is unique, and both ∅ and F are solutions to G λ F (F ).

As we shall see below, the connection between the TVL1 problem and the Cheeger problem is in fact very deep, just as it is for the ROF problem (see for instance [START_REF] Bellettini | Explicit solutions of the eigenvalue problem div Du |Du| = u in R 2[END_REF][START_REF] Alter | A characterization of convex calibrable sets in R N[END_REF][START_REF] Carlier | Approximation of maximal cheeger sets by projection[END_REF]).

In the particular case where F is convex, Per(U ∩ F ) Per U for all U ⊂ R 2 with finite perimeter. Hence we may assume that the solution U ⊆ F , and Problem (G λ (F )) is then equivalent to inf

U ⊆F Per U -λ|F |. (G ′ λ (F ))
This family of problems is precisely the one that appears naturally in the study of both the Cheeger problem and the ROF problem when the input is f = 1 F with F convex. The characterization of the solutions to these problems by their curvature and ratio perimeter/area is given in [START_REF] Alter | A characterization of convex calibrable sets in R N[END_REF], and the link between the curvature of a convex set and its invariance by openings in [START_REF] Andreu | Minimizing total variation flow[END_REF]. It is used in [START_REF] Alter | Evolution of convex sets in the plane by minimizing the total variation flow[END_REF] (and independently in [START_REF] Kawohl | Characterization of cheeger sets for convex subsets of the plane[END_REF]) to characterize the solutions of the Cheeger problem: if F is a convex set, the solution to Problem (C(F )) is given by the morphological opening

O 1/λ * F = {B(x, 1 λ * ), x ∈ F and B(x, 1 λ * ) ⊆ F } for some value λ * characterized by Per O 1λ * F |O 1/λ * F | = 1 λ * .
Concatenating these results, we observed in [START_REF] Duval | The TVL1 Model: a Geometric Point of View[END_REF]: Theorem 2 (Solution for convex data). Let F ⊆ R 2 be a nonempty bounded convex set, and let λ * > 0 defined above. The set of solutions to G λ (F ) is

• {O 1/λ F } for λ > λ * , • {∅, O 1/λ * F } for λ = λ * (where O 1/λ * F is the Cheeger set of F ),
• {∅} for λ < λ * .

Link with Mathematical Morphology

The fact that TVL1 is a morphological filter (i.e. contrast invariant and idempotent) is a consequence of the geometric equivalence property. It was first noticed in [START_REF] Darbon | Total variation minimization with L 1 data fidelity as a contrast invariant filter[END_REF], and several related properties were independently observed in [START_REF] Yin | The total variation regularized L 1 model for multiscale decomposition[END_REF].

Proposition 4 ([36, 74]). Let f ∈ L 1 (R 2 ), u ∈ BV(R 2 ). • For all τ ∈ R 2 , u(• -τ ) is a solution to P λ (f (• -τ )) if and only if u is a solution to P λ (f )
• For all Lipschitz homomorphism g : R → R, g • u is a solution to P λ (g • f ) if and only if u is a solution to P λ (f ).

The second point of Proposition 4 not only means that the filter is invariant by contrast change, but also that it is self-dual (choosing g = -Id). All these axioms of mathematical morphology (see [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF][START_REF] Guichard | Contrast invariant image analysis and PDE's[END_REF]) satisfied by the model strongly advocate for its use in image processing.

The main interest of Theorem 2 is that it gives the explicit form of the morphological operator involved (at least when the level sets of f are convex). Since λ > λ * is equivalent to Per O λ F |O λ F | < λ, the solution to TVL1 amounts in this case to a morphological opening, and a "thresholding" on the ratio perimeter/area of the result: if it is greater than λ, the level set should be replaced with ∅ (see Section 2.4). The theorem also highlights the importance of the scale of objects in the behavior the model.

The notion of scale is intrinsically linked with the development of mathematical morphology. In order to measure the petrographic distribution of oolites and chlorite cement in Lorraine iron ores (see [START_REF] Matheron | The birth of mathematical morphology[END_REF]) Matheron and Serra have introduced operations like erosions, dilations and openings and defined the concept of granulometry that allows to discriminate objects by their size (see [START_REF] Matheron | Etude théorique des granulométries[END_REF][START_REF] Haas | Morphologie mathématique et granulométries en place[END_REF]). Since then, the use of mathematical morphology and granulometries has spread to various areas of image processing especially in the study of textures in general [START_REF] Soille | Morphological Image Analysis: Principles and Applications[END_REF] (an example is shown in Figure 3). Recently, a similar approach was introduced by Vixie et al. (see [START_REF] Vixie | Multiscale flat norm signature for shapes and images[END_REF]) in order to classify shapes using TVL1. Introducing (among other signatures) the shape signature s F : λ

→ |U λ ∆F | |F |
where U λ is a solution to G λ (F ), they plot λ → s F ( 1 λ ), and they show that this curve gives information about the scales of the object F . In particular, they notice the importance of the jumps of s F and they propose to examine the derivative λ → d dλ s F ( 1 λ ). This is precisely the philosophy of granulometries and granulometric spectra, and Theorem 2 shows that the examined quantities are in fact almost the same.

An Algorithm using the Fast Level Set Transform

In order to numerically compare the solutions of TVL1 with the result of openings, we have built an algorithm which is based on the Fast Level Set Transform (FLST) introduced in [START_REF] Monasse | Scale-space from a level lines tree[END_REF]. A shape is defined as the union of a connected component of an upper or lower set together with its holes. Monasse and Guichard have proved in [START_REF] Monasse | Scale-space from a level lines tree[END_REF] that, in the discrete framework, shapes have a tree structure for the inclusion relation (which was extended in [START_REF] Ballester | The tree of shapes of an image[END_REF] by Ballester et al. to the continuous case), and they have proposed a fast algorithm to compute it. More detail about the tree of shapes can be found in the book by Caselles an Monasse [START_REF] Caselles | Geometric Description of Images As Topographic Maps[END_REF].

We only sketch the principle of our algorithm, and we refer the reader to [START_REF] Duval | The TVL1 Model: a Geometric Point of View[END_REF] for more detail.

From Theorem 2 (which only deals with convex sets) and the self-duality of the model, we infer that the result of TVL1 is similar to a closing in locally concave parts. The example of the two discs (see Figure 2) is also in favor of such a behavior. A good compromise between openings with radius 1/λ in convex regions and closings in concave parts is given by the alternate sequential filter (ASF). This filter consists, given a small value r 0 , in performing alternatively an opening and a closing of radius nr 0 until nr 0 1/λ. When r 0 is small enough, the operator is much more symmetric than a single opening-closing step, and starting with either an opening or a closing makes little difference.

The openings and closings are computed for all level sets simultaneously by using their formulation for functions. Then, the "thresholding" on the ratio perimeter/area is adapted by testing whether the energy of the connected component is less than the energy of the empty set (this variation of energy is denoted by ∆E). The advantage of using the fast level set transform is that the procedure is automatically self-dual and that it allows to deal with all similar level sets at a time. The algorithm is summarized in Figure 4.

A visual comparison with a gradient descent is given in Figure 5. The result are quite similar but since the coarea formula does not hold for the discretized isotropic total variation, the latter yields a blurry image. We have also compared our procedure with the graph-cut algorithm by Darbon and Sigelle [START_REF] Darbon | Image restoration with discrete constrained total variation part I: Fast and exact optimization[END_REF]. The total variation is then an anisotropic total variation. It is proved in [START_REF] Duval | Variational and non-local methods in image processing: a geometric study[END_REF] by relying on results from [START_REF] Bellettini | Characterization of facet-breaking for nonsmooth mean curvature flow in the convex case[END_REF], that Theorem 2 holds for crystalline anisotropic total variations when replacing balls with the Wulff shape (see [START_REF] Duval | Variational and non-local methods in image processing: a geometric study[END_REF] for more details). Here, the openings with balls are replaced with openings with squares of side 2/λ. The similarity between the exact result [START_REF] Darbon | Image restoration with discrete constrained total variation part I: Fast and exact optimization[END_REF] and the result of the FLST-based algorithm is striking.

The TVG model

Observing the behavior of the G-norm for oscillating functions, Y. Meyer proposed to use the G space to model textures, decomposing an image f ∈ L 2 (R 2 ) into a structure (or cartoon) part u and a texture part v = fu using the following variational problem:

inf u∈BV(R 2 ) |Du| + λ f -u G . (Q λ (f ))
The existence of a solution follows from the direct method of the calculus of variations. The solution to Q λ (f ) is not necessarily unique (see [START_REF] Haddad | An improvement of rudin-osher-fatemi model[END_REF]). Kindermann, Osher and Xu have characterized the optimality of solutions for Q λ (f ) in [START_REF] Kindermann | Denoising by bv-duality[END_REF]. Using the subdifferential of the G-norm derived in [START_REF] Andreu | Some qualitative properties for the total variation flow[END_REF], we may obtain the same result straightforwardly, writing 0

∈ ∂| • | T V (u) + λ∂ • G (f -u).
Algorithm FLST-based TVL1

Inputs: Image f Parameters: Fidelity parameter λ Output: Approximate solution u

Perform Alternate Sequential Filter: a := ASF (f ) Compute the Level Set Transform: T := F LST (a) for all shape s of the tree T do Remove the children t of s such that

V t = V s . if (∆E < 0) then Remove s. end if end for Reconstruct u := F LST -1 (T ).
Figure 4: An algorithm to compute an approximate solution of TVL1 using openings and the Fast Level Set Transform. The tree is visited from the leaves to the root. Proposition 5 ([51]). The decomposition (u, v) is optimal if and only if:

∃z ∈ X ∞ , |z| 1 and -u div z = |Du|, (21) ∃p
∈ BV(R 2 ), |Dp| 1 and pv = v G , (22)
such that div z + λp = 0.

Haddad and Meyer have studied the case where the whole signal is in the texture part (u = 0, v = f ). Conversely they have also proved that if |Dp| < 1 in [START_REF] Bellettini | The total variation flow in R N[END_REF], the solution must be (u, v) = (f, 0). Let us also mention that they have deeply investigated the radial case using Proposition 5, expliciting in particular the decomposition of the radial function f (r) = e -r .

The rationale behind Problem (Q λ (f )) is of course that if an image f is the sum of a structure part and a texture part, one expects to get the former in the solution u of Q λ (f ) part and the latter in v = fu. Indeed, the total variation is low for cartoon-like images and high for oscillating images, and conversely for the G-norm. This approach has had a certain success in practical applications (see [START_REF] Aujol | Image decomposition into a bounded variation component and an oscillating component[END_REF][START_REF] Yin | A comparison of three total variation based texture extraction models[END_REF][START_REF] Gilles | Noisy image decomposition: a new structure, texture and noise model based on local adaptivity[END_REF]).

The aim of this section is to discuss the limitations of the above paradigm. Can this model actually separate texture from structure? Is there any constraint on the texture and structure part? 4). Five row: result of the FLST based algorithm, using a square as structuring element. All pictures were computed with λ = 1/9, except the first column (λ = 1/6, the small component is kept, contrary to the second column).

3.1 When it works. . . [START_REF] Bellettini | The total variation flow in R N[END_REF] according to [START_REF] Haddad | An improvement of rudin-osher-fatemi model[END_REF]. Now, let g ∈ L ∞ (R 2 , R 2 ) be a vector field adapted to v, i.e. div g = v and g ∞ = v G . By integration by parts, ( 22) is equivalent to

Let (u, v) be a decomposition of f using (Q λ (f )). If v = 0, then |Dp| = 1 in
-(g, Dp) = g ∞ |Dp|, i.e. 0 = (g, Dp |Dp| ) + g ∞ d|Dp|. ( 24
)
This means that |Dp|-almost everywhere, |g| must reach its maximum, and g must be pointing in the opposite direction from Dp.

To build examples of exact decompositions, it is therefore sufficient to define vector fields z and g which satisfy [START_REF] Bellettini | Characterization of facet-breaking for nonsmooth mean curvature flow in the convex case[END_REF] with p = -1 λ div z. In the radial case, we have proved in [START_REF] Duval | Variational and non-local methods in image processing: a geometric study[END_REF] the following result which guarantees a successful decomposition. Let us write z(x) = z(r)e r , g(x) = g(r)e r , u(x) = ũ(r), etc.

Proposition 6. Let g ∈ W 1,∞ (R + , R) with g(0) = 0. Assume that there are val- ues 0 < r j * < . . . < r 0 < . . . < r k * with r 0 = 1 such that g(r k ) = (-1) k+1 g ∞ for k ∈ {j * , . . . 0, . . . k * } and r k+1 -r k r k for j * k k * -1. Then, for 4π λ 4π   1 + k * -1 k=j * r k+1 + r k r k+1 -r k   , (25)
the radial function f defined by f (r) = 1 [0,1] (r) + β 1 r ∂rg(r) ∂r has a perfect decomposition (u, v) given by:

ũ(r) = 1 [0,1] (r) ṽ(r) = β 1 r ∂rg(r) ∂r
.

Here is a typical example of the result. Let N ∈ N * be an odd number, and consider the function f defined by

f (r) = 1 [0,1] (r) -β sin(N πr) - 1 πN r cos(N πr) 1 [1/2,3/2] (r),
so that we may choose r k = 1 + k N and k * = -j * = N -1 2 . For 4π λ 4π 2N 2 -2N + 1 , f has an optimal decomposition given by:

ũ(r) = 1 [0,1] (r), ṽ(r) = -β sin(N πr) - 1 πN r cos(N πr) 1 [1/2,3/2] (r).
This decomposition is illustrated in Figure 6 and the constructed z and p are shown in Figure 7. Incidentally, let us observe the effect of the frequency (N or 1 r k+1 -r k above) on the decomposition: the faster the oscillation, the larger the interval of λ for which the decomposition is perfect. 3.2 . . . and when it does not.

It should be observed that in the above example, in the original function f , there is some texture near the edge of the cartoon part (at r = 1). This is not a coincidence and the aim of this section is to prove that this property is necessary to obtain a perfect decomposition.

First, we consider the one-dimensional setting and we recall the argument given in [START_REF] Duval | Mathematical modeling of textures: Application to color image decomposition with a projected gradient algorithm[END_REF]. Assume that we want to decompose a function

f ∈ L 1 (R) ∩ L 2 (R) using (Q λ (f )) (replacing BV(R 2 ) with BV(R)). The G-norm can be computed as v G = inf C∈R sup t∈R t -∞ v(s)ds + C . The function V : t → t -∞ v(s)ds is continuous, bounded (for v ∈ L 1 (R)) and 16 the optimal C is C = -sup V +inf V 2 .
To fix ideas, let us consider a rectangular function perturbed with some textures (see Figure 8)

f (x) = 1 (0,1) (x) + β sin(8pπx)1 1 4 |x| 3 4 .
The ideal decomposition one would expect is a perfect step u(x) = 1 (0,1) (x), t 0 1 4pπ . Yet, replacing u on [-1 4 , 1 4 ] with any non-decreasing function u * with the same limits at ± 1 4 , say, a ramp x → ( 1 2 + 1 2η x)1 [-η,η] (x) as in Figure 8, last row), one still gets the same cartoon energy |Du * | = 2. As for the texture part, we should notice that one extra oscillation is added near the discontinuity of the original function f . But since the G-norm favors oscillations, this change in the texture part is not penalized. Indeed,

f t 0 1 u t v x -∞ v(t)dt t 1 u * t v * x -∞ v (t)dt
v * G = max β 4pπ , 0 -η ( 1 2 + 1 2η t)dt = β 4pπ (26)
for η small enough (0 η min( 1 4 , β pπ )). Therefore, we see on this example that given any decomposition with sharp edges, there exists a decomposition with the same energy where halos around edges appear in the texture part. This explains why some edges appear in the texture part in Figure 1. This phenomenon may also explain the kind of halo that appears in smooth areas: replacing the ramp with a slow gradation, one may alter smooth parts without changing the energy.

Texture edges

In the above example we have observed that, if the perfect decomposition were optimal, another optimal decomposition would have "shadow edges" in the texture part: depending on luck or on the choice of the algorithm, this artifact may not appear. Now we advocate the fact that in the two-dimensional framework, and for typical images of the model, the artifact is bound to appear : there should always be some texture in the v part around the points where u has jumps. One may prove (see [START_REF] Duval | Variational and non-local methods in image processing: a geometric study[END_REF] for the proof) that:

Proposition 7. Let f ∈ L 2 (R 2 ) be a radial function, u = 1 B(0,1) and v = f -1 B(0,1) such that v = 0. Let ε > 0 and C (-ε,ε) = {x ∈ R 2 , 1-ε < |x| < 1+ε}. If v |Ω (-ε,ε) = 0, then the decomposition (u, v) is not optimal.
More generally, for any convex set C ⊂ R 2 and ε > 0, let us define

C -ε = {x ∈ C, d(x, ∂C) ε} and C -ε,ε = {x ∈ R 2 , d(x, ∂C) < ε}.
The following result holds (see Proposition 5.2.14 in [START_REF] Duval | Variational and non-local methods in image processing: a geometric study[END_REF]):

Proposition 8. Let C ⊂ R 2 be a C 1,1 convex body, f ∈ L 2 (R 2 ) \ {1 C }, u = 1 C and v = f -1 C . Assume that Supp v ⊂ C and that the decomposition (u, v) is optimal. Then Supp v ∩ ∂C = ∅, where Supp v is the support of v.
Proof. Assume by contradiction that d(Supp v, ∂C) > 0, so that there exists ε > 0 such that Supp v ⊆ C ε . . As (u, v) is optimal, equations ( 21), ( 22), ( 23

) hold. Since R 2 pv |Dp| = v G = sup w∈BV(R 2 )\0 R 2 wv |Dw| , p is a non-trivial minimizer of G(w) := |Dw|-R 2 v v G w.
The level sets (E t ) t∈R of p are thus solutions to the prescribed mean curvature problem associated to

-v v G : inf E⊂R 2 Per E - E v v G .
Now, we replace p with p * = p1 Cε , so that {p * t} = E t ∩ C ε for t 0, and

{p * < t} = E t ∩ C ε for t < 0. Since C ε is convex, Per (E t ∩ C ε ) Per E t , with strict inequality if |E t \ C ε | > 0.
By Lemma 1 below, |Dp|(C (-ε,ε) ) > 0, and the coarea formula implies that the set

B = {t > 0, |E t ∩ C (-ε,ε) | > 0} has positive Lebesgue measure. Since Per (E t ∩ C ε ) < Per E t for all t ∈ B, |Dp * | < |Dp|. Since p * v = pv, we see that G(p * ) < G(p), which is a contradiction.
The following lemma is a consequence of the Gauss-Green theorem (see [START_REF] Duval | Variational and non-local methods in image processing: a geometric study[END_REF]Lemma 5.2.13]): Lemma 1. Under the same assumptions as in Proposition 8, if p is the function defined in Equations ( 22),( 23) and ε > 0, then |Dp|(C (-ε,ε) ) > 0.

To conclude this section, let us observe that the TVL1 model is not concerned with such a limitation, as the following example shows (see [START_REF] Duval | Variational and non-local methods in image processing: a geometric study[END_REF] for the proof). Let N ∈ N * . For 2 λ 2N , the radial function f defined by

f (r) = 1 [0,1] (r) -β sin(N πr)1 [2,3] (r), (27)
has an optimal decomposition given by: ũ

(r) = 1 [0,1] (r), ṽ(r) = -β sin(N πr)1 [2,3] (r).
The corresponding decomposition is illustrated in Figure 9.

Conclusion

We have presented the analysis of the TVL1 and TV-G models developed in [START_REF] Duval | Variational and non-local methods in image processing: a geometric study[END_REF]. On the one hand, the behavior of the TVL1 model relies on geometric considerations. Our study shows the connection between the model and morphological openings. The decomposition produced by TVL1 is quite similar to granulometries, and the crucial notion to distinguish texture or noise from structure is the scale.

On the other hand, the key notion used by the TV-G model is the oscillation of a pattern. While in some cases the TV-G model is able to separate oscillating textures from the geometric structure of images, we have highlighted a serious limitation of the model: in the original signal, there must be some texture in the neighborhood of edges for the decomposition to be perfect. Otherwise, shadows of edges or gradations appear in the texture part, resulting in an inflated aspect of the result.

Appendix

Proof of Proposition 6. We build the vector field z in [START_REF] Ballester | The tree of shapes of an image[END_REF] and the corresponding p in (23) using λp = 1 r ∂ ∂r (rz(r)). For r ∈ [0, r j * ], we set z(r) = (-1) j * -1 r r j * , so that p(r) = p j * -1 = (-1) j * -1 2 λr j * . By induction on k (with j * k k * -1), we define z on [0, r k ] such that z(r k ) = (-1) k-1 . We set, for r ∈ (r k , r k+1 ], Observe that the fact that z(1) = z(r 0 ) = -1 implies that (z, Du) = |Du|, |Du|-almost everywhere. Moreover, it is easy to check that the condition r k+1r k r k for j * k k * -1 implies that z varies monotonically from (-1) k-1 to (-1) k in [r k , r k+1 ]. Hence we have built z and p which satisfy [START_REF] Ballester | The tree of shapes of an image[END_REF] and [START_REF] Bellettini | Explicit solutions of the eigenvalue problem div Du |Du| = u in R 2[END_REF].

It remains to prove that p satisfies [START_REF] Bellettini | The total variation flow in R N[END_REF]. The total variation of p is equal to Hence, choosing λ = 4π 1 + k * -1 k=j * r k+1 +r k r k+1 -r k , we obtain that |Dp| = 1. Moreover the vector field g is such that g ∞ = v G . Indeed, by symmetry, there exists an optimal vector field g * which is radial, and the difference gg * is radial and divergence free, hence of the form C r . Since both g and g * are bounded, we get C = 0 and g = g * . Observing that g(r k ) = (-1) k+1 g ∞ = -Dp |Dp| ({r k }) g ∞ , we obtain [START_REF] Bellettini | Characterization of facet-breaking for nonsmooth mean curvature flow in the convex case[END_REF] and thus [START_REF] Bellettini | The total variation flow in R N[END_REF].

As a conclusion, we obtain that the decomposition (u, v) is optimal for (Q λ (f )) with λ = 4π 1 + k * -1 k=j * r k+1 +r k r k+1 -r k . It is not difficult to see that it is also optimal for λ = 4π (consider z(r) = r for 0 r 1, 1 r otherwise, and p = 2 λ 1 (0,1) ). Consequently, it is optimal for all λ such that 4π λ 4π 1 + k * -1 k=j * r k+1 +r k r k+1 -r k .

Figure 1 :

 1 Figure 1: Decomposition of the famous "Barbara" image using the algorithm in [18] (top) and TVL1 (bottom).

Figure 2 :

 2 Figure 2: Two discs interact with arcs of circles of radius 1 λ

Definition 3 .

 3 A granulometry is a family of openings {γ µ } depending on a positive parameter µ, that are decreasing functions with respect to µ:µ 2 µ 1 > 0 ⇒ γ µ2 γ µ1 . The cumulative size distribution of a set F is µ → 1 -|γµF | |F | . Its derivative is called the granulometric spectrum of F : -1 |F | d dµ |γ µ F |.

  dr(gamma(r)/gamma(0)) Granulometric spectrum

Figure 3 :

 3 Figure 3: Examples of granulometries. The granulometric spectrum indicates the characteristic scales of the image.Recently, a similar approach was introduced by Vixie et al. (see[START_REF] Vixie | Multiscale flat norm signature for shapes and images[END_REF]) in order to classify shapes using TVL1. Introducing (among other signatures) the shape signature s F : λ → |U λ ∆F |

FLST+openingsFigure 5 :

 5 Figure 5: First row: original image. Second row: result of a gradient descent scheme. Third row: result of the FLST-based algorithm with euclidean balls as structuring elements. Fourth row: result obtained with Darbon-Sigelle's algorithm (connectivity 4). Five row: result of the FLST based algorithm, using a square as structuring element. All pictures were computed with λ = 1/9, except the first column (λ = 1/6, the small component is kept, contrary to the second column).

Figure 6 :Figure 7 :

 67 Figure 6: TV-G decomposition predicted by Proposition 6: original image f (left), cartoon part u = 1 B(0,1) (middle), texture part v(x) = sin(N π|x|) + 1 πN cos(N π|x|) 1 [1/2,3/2] (|x|) (right).

Figure 8 : 1 4 |x| 3 4(

 813 Figure 8: Top: original signal f . Middle row: expected decomposition. Bottom decomposition with the same energy. and a pure oscillation v(x) = β sin(8pπx)1 1 4 |x| 3 4 (Figure 8, middle row). The energy of the cartoon part is simply |Du|= u(0 + )u(0 -) + u(1 -)u(1 + ) = 2,whereas the energy of the texture part is given by v G = β

Figure 9 :

 9 Figure 9: T V -L 1 decomposition predicted for (27): original image f (left), cartoon part u = 1 B(0,1) (middle), texture part v(x) =sin(N π|x|)1 [2,3] (|x|) (right).

  z(r) = 1 r r k z(r k ) + λp k 2 (r 2r 2 k ) with p k := (-1) k 2 λ(r k+1r k ) , k-1 r k + (-1) k r 2r 2 k r k+1r k , so that p(r) = p k and z(r k+1 ) = (-1) k . For r ∈ (r k * , +∞), we set z(r) = r k * z(r k * ) r = (-1) k * -1 r k *r , so that p(r) = p k * := 0.

  |Dp| = 2πr j * |p j *p j * -1 | + . . . + 2πr k |p kp k-1 | + . . . + 2πr * k |p k *p k * -1 | = 2πr j * 2 λr j * + 2 λ(r j * +1r j * ) + . . . + 2πr k 2 λ(r kr k-1 ) + 2 λ(r k+1r k ) + . . . + 2πr * k 2 λ(r k *r k-1 )