Maxime Crochemore

Costas S Iliopoulos

Solon P Pissis
email: pississo@dcs.kcl.ac.uk

A Parallel Algorithm for Fixed-length Approximate String-Matching with k-mismatches

Keywords: string algorithms, parallel algorithms, approximate stringmatching

This paper deals with the approximate string-matching problem with Hamming distance. The approximate string-matching with kmismatches problem is to find all locations at which a query of length m matches a factor of a text of length n with k or fewer mismatches. The approximate string-matching algorithms have both pleasing theoretical features, as well as direct applications, especially in computational biology. We consider a generalisation of this problem, the fixed-length approximate string-matching with k-mismatches problem: given a text t, a pattern x and an integer ℓ, search for all the occurrences in t of all factors of x of length ℓ with k or fewer mismatches with a factor of t. We present a practical parallel algorithm of comparable simplicity that requires only O( nm⌈ℓ/w⌉ p ) time, where w is the word size of the machine (e.g. 32 or 64 in practice) and p the number of processors. Thus the algorithm's performance is independent of k and the alphabet size |Σ|. The proposed parallel algorithm makes use of message-passing parallelism model, and word-level parallelism for efficient approximate string-matching.

Introduction

The problem of finding factors of a text similar to a given pattern has been intensively studied over the last thirty years and it is a central problem in a wide range of applications, including file comparison, spelling correction, information retrieval, and searching for similarities among biosequences.

One of the most common variants of the approximate string-matching problem is that of finding factors that match the pattern with at most k-differences. The first algorithm addressing exactly this problem is attributable to Sellers [START_REF] Seller | The theory and computation of evolutionary distances: Pattern recognition[END_REF]. Sellers algorithm requires O(mn) time, where m is the length of the query and n is the length of the text. One of the first intensive study on the question is by Ukkonen [START_REF] Ukkonen | Finding approximate patterns in strings[END_REF]. A thread of practice-oriented results exploited the hardware word-level parallelism of bit-vector operations. Wu and Manber in [START_REF] Wu | Fast text searching allowing errors[END_REF] showed an O(knm/w) algorithm for the k-differences problem, where w is the number of bits in a machine word. Baeza-Yates and Navarro in [START_REF] Baeza-Yates | A faster algorithm for approximate string matching[END_REF] have shown a O(knm/w) variation on the Wu-Manber algorithm, implying O(n) performance when km = O(w). Another general solution based on existing algorithms can be found in [START_REF] Crochemore | Speeding up Hirschberg and Hunt-Szymanski LCS algorithms[END_REF].

In this paper, we consider the following versions of the sequence comparison problem: given a solution for the comparison of A and B = b B, can one incrementally compute a solution for A versus B? and given a solution for the comparison of A and B, can one incrementally compute a solution for A versus Bc? Here b and c are additional symbols. By solution we mean some encoding of a relevant portion of the traditional dynamic programming matrix D computed for comparing A and B.

Landau, Myers and Schmidt in [START_REF] Landau | Incremental String Comparison[END_REF] demonstrated the power of efficient algorithms answering the above questions, with a variety of applications to computational problems such as "the longest common subsequence problem","the longest prefix approximate match problem", "approximate overlaps in the fragment assembly problem", "cyclic string comparison" and "text screen updating".

The above ideas are the bases of the fixed-length approximate string-matching problem: given a text t of length n, a pattern x of length m and an integer ℓ, compute the optimal alignment of all factors of x of length ℓ with factors of t. Iliopoulos, Mouchard and Pinzon in [START_REF] Iliopoulos | The Max-Shift algorithm for approximate string matching[END_REF] presented the Max-Shift algorithm, a bit-vector algorithm that requires O(nm⌈ℓ/w⌉) time and its performance is independent of k. As such, it can be used to compute blocks of dynamic programming matrix as the 4-Russians algorithm (see [START_REF] Wu | A subquadratic algorithm for approximate limited expression matching[END_REF]).

In this paper, we consider the fixed-length approximate string-matching with k-mismatches problem: given a text t, a pattern x and an integer ℓ, search for all the occurrences in t with k or fewer mismatches of all factors of x of length ℓ. There has been ample work in the literature for devising parallel algorithms for different models and platforms, for the approximate string-matching problem [START_REF] Bertossi | A parallel solution to the approximate string-matching problem[END_REF], [START_REF] Galper | Parallel similarity search and alignment with the dynamic programming method[END_REF], [START_REF] Huang | A space-efficient parallel sequence comparison algorithm for a Message-Passing Multiprocessor[END_REF], [START_REF] Landau | Fast parallel and serial approximate string matching[END_REF], [START_REF] Dos Reis | Approximate string-matching algorithm using parallel methods for molecular sequence comparisons[END_REF]. We design and analyse a practical parallel algorithm for addressing the fixed-length approximate string-matching problem with k-mismatches in O( nm⌈ℓ/w⌉ p ) time. Thus the algorithm's performance is independent of k and the alphabet size |Σ| (provided that a letter fits in a computer word). The proposed algorithm makes use of message-passing parallelism model, and word-level parallelism for efficient approximate string matching.

The rest of the paper is structured as follows. In Section 2, the basic definitions that are used throughout the paper are presented. In Section 3, we formally define the problem solved in this paper. In Sections 4 and 5, we present the sequential and the parallel algorithm, respectively. In Section 6, we present the experimental results of the proposed algorithm. Finally, we briefly conclude in Section 7.

Basic Definitions

A string or sequence is a succession of zero or more symbols from an alphabet Σ of cardinality s; the string with zero symbols is denoted by ǫ. The set of all strings over the alphabet Σ is denoted by Σ * . A string x of length m is represented by x[1 . . m], where x[i] ∈ Σ for 1 ≤ i ≤ m. The length of a string x is denoted by |x|. We say that Σ is bounded when s is a constant, unbounded otherwise. A string w is a factor of x if x = uwv for u, v ∈ Σ * .

Consider the sequences x and y with

x[i], y[i] ∈ Σ ∪ {ǫ}. If x[i] = y[i]
, then we say that x[i] differs from y[i]. We distinguish among the following three types of differences:

1. A symbol of the first sequence corresponds to a different symbol of the second one, then we say that we have a mismatch between the two characters, i.e.,

x[i] = y[i]. 2.
A symbol of the first sequence corresponds to "no symbol" of the second sequence, that is x[i] = ǫ and y[i] = ǫ. This type of difference is called a deletion. 3. A symbol of the second sequence corresponds to "no symbol" of the first sequence, that is x[i] = ǫ and y[i] = ǫ. This type of difference is called an insertion.

As an example of the types of differences, see Figure 1. Another way of seeing this difference is that one can transform the x sequence to y by performing operations. The edit distance, δ E (x, y), between strings x and y, is the minimum number of operations required to transform x into y. These operations are Replacement of a mismatched symbol, a Deletion or an Insertion of a symbol. The edit distance is symmetrical, and it holds 0

≤ δ E (x, y) ≤ max(|x|, |y|). Let t = t[1 . . n] and x = x[1 .
. m] with m ≤ n. We say that x occurs at position q of t with at most k-differences (or equivalently, a local alignment of x and t at position q with at most k-differences), if t[q] . . . t[r], for some r > q, can be transformed into x by performing at most k of the following operations: inserting, deleting or replacing a symbol.

The Hamming distance δ H is defined only for strings of the same length. For two strings x and y, δ H (x, y) is the number of places in which the two strings differ, i.e. have different characters. Formally

δ H (x, y) = |x| i=1 1 x[i] =y[i] , where 1 x[i] =y[i] = 1, if x[i] = y[i] 0, otherwise (1)
The Hamming distance is symmetrical, and it holds 0 ≤ δ H (x, y) ≤ |x|.

Problem Definition

The focus is on computing matrix M , which contains the number of mismatches of all factors of pattern x of length ℓ and any contiguous factor of the text t of length ℓ.

Example. Let the text t = x = GGGT CT A and ℓ = 3. Table 1 shows the matrix M . Example. Let the text t = GT GAACT , x = GT CACGT and ℓ = 3. Table 2 shows the matrix M .

0 1 2 3 4 5 6 7 ǫ G G G T C T A 0 ǫ 0 0 0 0 0 0 0 0 1 G 1 0 0 0 1 1 1 1 2 G 2 1 0 0 1 2 2 2 3 G 3
The fixed-length approximate string-matching with at most k-mismatches problem can be formally defined as follows.

Problem 1. Given a text t of length n, a pattern x of length m and an integer ℓ, find all factors of x of length ℓ that match any contiguous factor of t of length ℓ with at most k-mismatches.

0 1 2 3 4 5 6 7 ǫ G T G A A C T 0 ǫ 0 0 0 0 0 0 0 0 1 G 1 0 1 0 1 1 1 1 2 T 2 2 0 2 1 2 2 1 3 C 3 3 3 1 3 2 2 3 4 A 3 3 3 3 1 2 3 2 5 C 3 3 3 3 3 2 1 3 6 G 3 2 3 2 3 3 2 1 7 T 3 3 1 3 2 3 3 2 Table 2: Matrix M for t = GT GAACT , x = GT CACGT and ℓ = 3.
4 The Bit-Vector-Mismatches Algorithm

Iliopoulos, Mouchard and Pinzon in [START_REF] Iliopoulos | The Max-Shift algorithm for approximate string matching[END_REF] presented the Max-Shift algorithm, a bit-vector algorithm that solves the fixed-length approximate string-matching problem: given a text t of length n, a pattern x of length m and an integer ℓ, compute the optimal alignment of all factors of x of length ℓ and a factor of t. The focus of the Max-Shift algorithm is on computing matrix D ′ , which contains the best scores of the alignments of all factors of pattern x of length ℓ and any contiguous factor of the text t.

The Max-Shift algorithm makes use of word-level parallelism in order to compute matrix D ′ efficiently, similar to the manner used by Myers in [START_REF] Myers | A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming[END_REF]. The algorithm is based on the O(1) time computation of each D ′ [i, j] by using bitvector operations, under the assumption that ℓ ≤ w, where w is the number of bits in a machine word or O(ℓ/w)-time for the general case. The algorithm maintains a bit-vector matrix B[0 . . m, 0 . . n], where the bit integer B[i, j], holds the binary encoding of the path in D ′ to obtain the optimal alignment at i, j with the differences occurring as leftmost as possible.

Here the key idea is to devise a bit-vector algorithm for the fixed-length approximate string-matching with at most k-mismatches problem. We maintain the bit-vector B[i, j] = b ℓ . . b 1 , where b λ = 1, 1 ≤ λ ≤ ℓ, if there is a mismatch of a contiguous factor of the text t[i -ℓ + 1 . . i] and x[j -ℓ + 1 . . j] in the λ th position. Otherwise we set b λ = 0.

Given the restraint that the integer ℓ is less than the length of the computer word w, then the bit-vector operations allow to update each entry of the matrix B in constant time (using "shift"-type of operation on the bit-vector). The maintenance of the bit-vector is done via operations defined as follows:

1. shiftc(x): shifts and truncates the leftmost bit of x.

δ H (x, y): returns the minimum number of replacements required to transform

x into y

The Bit-Vector-Mismatches algorithm for computing the bit-vector matrix B and matrix M is outlined in Figure 2.

Bit-Vector-Mismatches ⊲Input: t, n, x, m, ℓ ⊲Output: B, M 1). Assume that the bit-vector matrix B[0 . . m, 0 . . n] is given. We can use the function ones(v), which returns the number of 1's (bits set on) in the bit-vector v, to compute matrix M (see Figure 2, line 11).

1 begin 2 ⊲ Initialisation 3 for i ← 0 until n do 4 B[0, i] ← 0; M [0, i] ← 0 5 for i ← 0 until m do 6 B[i, 0] ← min(i, ℓ) 1's; M [i, 0] ← min(i, ℓ) 7 ⊲ Matrix B and Matrix M computation 8 for i ← 1 until m do 9 for j ← 1 until n do 10 B[i, j] ← shiftc(B[i -1, j -1]) or δH(x[i], t[j]) 11 M [i, j] ← ones(B[i, j]) 12 end
0 1 2 3 4 5 6 7 ǫ G G G T C T A 0 ǫ 0 0 0 0 0 0 0 0 1 G 1 0 0 0 1 1 1 1 2 G 11
Theorem 1. Given the text t = t[1 . . n], the pattern x = x[1 . . m], the motif length ℓ, and the size w of the computer word, the Bit-Vector-Mismatches algorithm correctly computes the matrix M in O(nm⌈ℓ/w⌉) units of time.

Proof. Without loss of generality, assume that we want to compute cell

M [i, j],
where

M [i, j] = δ H (x[i -ℓ + 1 . . i], t[j -ℓ + 1 . . j]) (2)
It is not difficult to see that, [START_REF] Baeza-Yates | A faster algorithm for approximate string matching[END_REF]) be an operation that returns the leftmost bit of the bitvector b. It follows that,

δ H (x[i-ℓ+1 . . i], t[j-ℓ+1 . . j]) = δ H (x[i-ℓ+1 . . i-1], t[j-ℓ+1 . . j-1])+δ H (x[i], t[j]) (3) Let last(b[ℓ] . . b
δ H (x[i-ℓ+1 . . i-1], t[j -ℓ+1 . . j -1]) = M [i-1, j -1]-last(B[i-1, j -1]) (4)
From Equations 2, 3 and 4,

M [i, j] = M [i -1, j -1] -last(B[i -1, j -1]) + δ H (x[i], t[j]) (5)
Equation 5 is equivalent to line 10 of the Bit-Vector-Mismatches algorithm.

⊓ ⊔ Hence, this algorithm runs in O(nm) under the assumption that ℓ ≤ w and its space complexity is reduced to O(n) by noting that each row of B depends only on its immediately preceding row.

The Parallel-Bit-Vector-Mismatches Algorithm

The next proposed parallel algorithm makes use of the message-passing parallelism model by using p processors. The following assumptions for the model of communications in the parallel computer are made. The parallel computer comprises a number of nodes. Each node comprises one or several identical processors interconnected by a switched communication network. The time taken to send a message of size n between any two nodes is independent of the distance between nodes and can be modelled as t comm = t s + nt w , where t s is the latency or start-up time of the message, and t w is the transfer time per data. The links between two nodes are full-duplex and single-ported: a message can be transferred in both directions by the link at the same time, and only one message can be sent and one message can be received at the same time.

We will use the functional decomposition, in which the initial focus is on the computation that is to be performed rather than on the data manipulated by the computation. We assume that both text t and pattern x are stored locally on each processor. This can be done by using a one-to-all broadcast operation in (t s + t w (n + m)) log p communication time, which is asymptotically O(n log p).

The key idea behind parallelising the Bit-Vector-Mismatches algorithm, is that cell B[i, j] can be computed only in terms of B[i -1, j -1]. Based on this, if we partition the problem of computing matrix B (and M ) into a set of diagonal vectors ∆ 0 , ∆ 1 , . . , ∆ n+m , as shown in Equation 6, the computation of each one of these would be independent, and hence parallelisable.

∆ ν [x] =    B[ν -x, x] : 0 ≤ x ≤ ν, (a) B[m -x, ν -m + x] : 0 ≤ x < m + 1, (b) B[m -x, ν -m + x] : 0 ≤ x < n + m -ν + 1, (c) (6)
where, (a

) if 0 ≤ ν < m (b) if m ≤ ν < n (c) if n ≤ ν < n + m + 1
It is possible that in a certain diagonal ∆ ν , ν > 0, a processor will need a cell or a pair of cells, which were not computed on its local memory in diagonal ∆ ν-1 . We need a communication pattern in each diagonal ∆ ν , for all 0 ≤ ν < n + m, which minimises the data exchange between the processors. It is obvious, that in each diagonal, each processor needs only to communicate with its neighbours. In particular, in each diagonal, each processor needs to swap the boundary cells with its left and right neighbour processor.

An outline of the Parallel-Bit-Vector-Mismatches algorithm in each diagonal ∆ ν , for all 0 ≤ ν < n + m + 1, is as follows:

Step 1. Each processor is assigned with |∆ ν |/p cells (without loss of generality).

Step 2. Each processor computes each allocated cell using the Bit-Vector-Mismatches algorithm.

Step 3. Processors communication involving point-to-point boundary cells swaps. ⊓ ⊔ Hence, the parallel algorithm runs in O( nm p ) under the assumption that ℓ ≤ w, and its space complexity is reduced to O(n) by noting that each diagonal vector ∆ ν of matrix B, for all 2 ≤ ν ≤ n + m, depends only on ∆ ν-2 .

Experimental Results

In order to evaluate the parallel efficiency of our algorithm, we implemented the Bit-Vector-Mismatches algorithm in ANSI C language and parallelised it with the use of the MPI library. Both implementations, the sequential and the parallel algorithm, are available at a website 1 , which has been set up for maintaining the source code and the documentation.

Experimental tests were run on 1 up to 16 processing nodes (2.6 GHz AMD Opteron) of a cluster architecture. As an input, DNA sequences of the mouse chromosome X were used, retrieved from the Ensembl genome database. Experimental results regarding the execution time and measured speed-up are illustrated in Figures 3 and4, respectively. The speed-up is calculated as the ratio of elapsed time with p processors to elapsed time with one processor. The presented experimental results demonstrate a good scaling of the code. The proposed algorithm scales well even for small problem sizes. As expected in some cases, when increasing the problem size, the algorithm achieves a linear speed-up, confirming our theoretical results. Further tests were conducted for different values of fixed-length ℓ, with no difference observed, regarding the execution time.

Conclusion

We have presented a practical parallel algorithm that solves a generalisation of the approximate string-matching problem. In particular, the proposed parallel algorithm solves the fixed-length approximate string matching with k-mismatches 1 http://www.dcs.kcl.ac.uk/pg/pississo/ ) time, which is O( nm p ), in practical terms. It is considerably simple and elegant, it achieves a theoretical and practical linear speed-up, it does not require text preprocessing, it does not use/store look up tables and it does not depend on the number of differences k and the alphabet size |Σ|.

Fig. 1 :

 1 Fig. 1: Types of differences: mismatch in position 2 (A, C), deletion in position 4 (F, ǫ), insertion in position 6 (ǫ, B)

Table 1 :

 1 Matrix M for t = x = GGGT CT A and ℓ = 3.

Fig. 2 :

 2 Fig. 2: The Bit-Vector-Mismatches algorithm for computing matrix B and matrix M

Theorem 2 .

 2 Given the text t = t[1 . . n], the pattern x = x[1 . . m], the motif length ℓ, the size w of the computer word, and the number of processors p, the Parallel-Bit-Vector-Mismatches algorithm computes the matrix M in O( nm⌈ℓ/w⌉ p ) units of time.Proof. We partition the problem of computing matrix B into a set of n + m + 1 diagonal vectors, thus O(n) supersteps. In step 1, the allocation procedure runs in O(1) time. In step 2, the cells computation requires O( m⌈ℓ/w⌉ p ) time. In step 3, the data exchange between the processors involves O(1) point-to-point message transfers. Hence, asymptotically, the overall time is O( nm⌈ℓ/w⌉ p ).

Fig. 3 :

 3 Fig. 3: Execution time for t = x and ℓ = 20

Fig. 4 :

 4 Fig. 4: Measured speed-up for t = x and ℓ = 20

Table 3 :

 3 The bit-vector matrix B for t = x = GGGT CT A and ℓ = 3.

			10	00	00	01	11	11	11
	3	G	111 110 100 000 001 011 111 111
	4	T	111 111 101 001 000 011 110 111
	5	C	111 111 111 011 011 000 111 101
	6	T	111 111 111 111 110 111 000 111
	7	A	111 111 111 111 111 101 111 000


Laurent Najman #
email: l.najman@esiee.fr

Fernand Meyer #

A short tour of mathematical morphology on edge and vertex weighted graphs

Introduction

Mathematical morphology is a discipline of image analysis that was introduced in the mid-1960s by two researchers at the École des Mines in Paris: Georges Matheron [START_REF] Matheron | Random sets and integral geometry[END_REF] and Jean Serra [START_REF] Serra | Image analysis and mathematical morphology[END_REF][START_REF] Serra | Image analysis and mathematical morphology[END_REF]. Historically, it was the first consistent non-linear image analysis theory, which from the very start included not only theoretical results but also many practical aspects. Due to the algebraic nature of morphology, the space on which the operators are defined can be either continuous or discrete. However, it was only in 1989 [START_REF] Vincent | Graphs and mathematical morphology[END_REF] that researchers from the CMM at the École des Mines began to study morphology on graphs, soon formalized in [START_REF] Heijmans | Graph morphology in image analysis[END_REF]. Fairly recent development [START_REF] Falcão | The image foresting transformation[END_REF][START_REF] Meyer | Morphological operators for flooding, leveling and filtering images using graphs[END_REF][START_REF] Meyer | Micro-viscous morphological operators[END_REF][START_REF] Ta | Partial difference equations over graphs: Morphological processing of arbitrary discrete data[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF][START_REF] Bloch | Mathematical morphology on hypergraphs: Preliminary definitions and results[END_REF][START_REF] Dias | Some morphological operators on simplicial complexes spaces[END_REF] in this direction has several motivations and beneficial consequences that we are going to review in this chapter. Rather than trying to cover every aspect of the theory, we choose to present a comprehensive subset based on a recent unifying graph theoretical framework developed by the A3SI team of the LIGM at Paris-Est University. The presentation is roughly divided in three parts, dealing respectively with basic operators (mainly based on [START_REF] Cousty | Some morphological operators in graph spaces[END_REF]), hierarchical segmentation (mainly based on [START_REF] Cousty | Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle[END_REF] and [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF]), and optimization (mainly based on [START_REF] Couprie | Power Watersheds: A Unifying Graph Based Optimization Framework[END_REF]). For the reader interested in a more complete presentation of morphology, we recommend [START_REF] Soille | Morphological Image Analysis[END_REF] and the recent [START_REF]Mathematical morphology: from theory to applications[END_REF].

One of the fundamental ideas of mathematical morphology is to compare unkown objects with known ones. We begin by presenting the tools that make such an idea practicable: mathematical structures called lattices (Section 1.2), allowing us to compare weighted and non-weighted edges and vertices. We then present (Section 1.3) several dilations and erosions, that always come in pairs (they are called adjunct operators). From there, we can build (Section 1.4) some morphological filters, called opening or closing. During the presentation of those various operators, we often give an interpretation of classical graph-operators in morphological terms. We conclude this part by presenting (Section 1.5) some connected operators based on pruning a tree representation of the image, illustrating their usage for image filtering and simplification.

The second part of the chapter deals with hierarchical segmentation. During the course of the chapter's first part, several times the minimum spanning tree appears. This tree is the oldest combinatorial optimization problem [START_REF] Nesetril | Otakar Boruvka on Minimum Spanning Tree problem: Translation of both the 1926 papers, comments, history[END_REF][START_REF] Choquet | étude de certains réseaux de routes[END_REF]. Since the seminal work of Zahn [START_REF] Zahn | Graph-theoretical methods for detecting and descibing Gestalt clusters[END_REF], the minimum spanning tree has been extensively used in classification. Its first appearance in image processing dates from 1986, in a paper by Morris et al. [START_REF] Morris | Graph theory for image analysis: an approach based on the shortest spanning tree[END_REF]. Meyer was the first to explicitely use it in a morphological context [START_REF] Meyer | Minimum spanning forests for morphological segmentation[END_REF]. A strong momentum to its usage in segmentation has been provided thanks to a 2004 paper by Felzenswalb and Huttenlocher [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF].

In the second part of the chapter, we revisit the watershed [START_REF] Vincent | Watersheds in digital spaces: An efficient algorithm based on immersion simulations[END_REF], and show that in the framework of edgeweighted graphs, the watershed has very strong links with the minimum spanning tree (Section 1.6). Thanks to such links, we can use the watershed for building hierarchies of segmentations (Section 1.7), relying on the filtering tools seen in the first part of the chapter.

The main principle of morphology, comparison, is rather different from the optimization paradigm. However, rather than opposing these two viewpoints, it is more fruitful to explore their connections. In the last part of the chapter (Section 1.8), we turn towards optimization and show that the watershed presented in the previous part can be extended to be used as an optimization tool.

Graphs and lattices

In mathematical morphology, we compare objects one with respect to each other. The mathemathical structure that allows us to make such an operation effective is called a lattice. Recall that a (complete) lattice is a partially ordered set, that also has a least upper bound, called supremum, and a greatest lower bound, called infimum. More formally, a lattice [START_REF] Birkhoff | Lattice Theory[END_REF] (L, ≤) is a set L (the space) endowed with an ordering relationship ≤, which is reflexive (∀x ∈ L, x ≤ x), anti-symmetric (x ≤ y and y ≤ x =⇒ x = y) and transitive (x ≤ y and y ≤ z =⇒ x ≤ z). This ordering is such that for all x and y, we can define both a larger element x ∨ y and a smaller element x ∧ y. Such a lattice is said to be complete if any subset P of L has a supremum P and an infimum P that both belongs to L. The supremum is formally the smallest amongst all elements of L that are greater than all the elements of P, and conversely the infimum is the largest element of L that is smaller than all the elements of P.

Most of the morphological theory can be presented and developed at this abstract level, without making references to the properties of the underlying space. However, studying what impact such properties have can indeed be interesting in some situations. In the sequel, we study some lattices that can be built from graph spaces, and what kind of (morphological) operators can be built from such lattices.

Lattice of graphs

We define a graph as a pair

G = (V(G), E(G)) where V(G) is a set and E(G) is composed of unordered pairs of distinct elements in V(G), i.e., E(G) is a subset of {{v 1 , v 2 } ⊆ V(G) | v 1 = v 2 }. Each element of V(G) is called a vertex or a point (of G)
, and each element of E(G) is called an edge (of G). In the sequel, to simplify the notations, e i j stands for the edge {v i , v j } ∈ E(G).

Let G 1 and G 2 be two graphs. If V(G 2 ) ⊆ V(G 1 ) and E(G 2 ) ⊆ E(G 1 ), then G 1 and G 2 are ordered and we

write G 2 G 1 . If G 2 G 1 , we say that G 2 is a subgraph of G 1 , or that G 2 is smaller than G 1 and that G 1 is greater than G 2 .
Important remark. Hereafter, the workspace is a graph G = (V(G), E(G)) and we consider the sets V(G), E(G) and G of respectively all subsets of V(G), all subsets of E(G) and all subgraphs of G. We also use the

classical notations V = V(G) and E = E(G).
Let S 0 , S 1 ⊆ G be the sets of respectively the graphs made of a single vertex and the graphs made of a pair of vertices linked by an edge, i.e., S 0 = {({v}, / 0)

| v ∈ V(G)} and S 1 = {({v i , v j }, {e i j }) | e i j ∈ E(G)}. We set S = S 0 ∪ S 1 . Any graph G 1 ∈ G is generated by the family F = {G 1 , . . . , G } of all elements in S smaller than G 1 : G 1 = ( i∈[1, ] V(G i ), i∈[1, ] E(G i ))
; we say that the elements of F are the generators of G 1 [START_REF] Cousty | Some morphological operators in graph spaces[END_REF]. Conversely, any family F of elements in S generates an element of G. Hence, S (sup-) generates G.

Clearly, the ordering on graphs amount to say that G 2 G 1 when all generators of G 2 are also generators of G 1 . Therefore, ordering provides a lattice structure on the set G. Indeed, the largest graph smaller than a family F = {G 1 , . . . , G } of elements in G is the graph generated by the generators common to all G i , i ∈ [1, ]; this infimum is denoted by F . Similarly, the supremum F is generated by the union of the families of generators of all

G i , i ∈ [1, ]. If V(G 1 ) ⊆ V(G) (resp. E(G 2 ) ⊆ E(G)), we denote by V(G 1 ) (resp. E(G 2 )) the complementary set of V(G 1 ) (resp. E(G 2 )) in V(G) (resp. E(G)), that is V(G 1 ) = V(G) \ V(G 1 ) (resp. E(G 2 ) = E(G) \ E(G 2 )).
Observe that, if G 1 is a subgraph of G, then, except in some degenerated cases, the pair (V(G 1 ), E(G 1 )) is not a graph.

Property 1 ([10])

The set G of the subgraphs of G form a complete lattice, sup-generated by the set S = S 0 ∪ S 1 , but not complemented. The supremum and the infimum of any family

F = {G 1 , . . . G } of elements in G are given by respectively F = ( i∈[1, ] V(G i ), i∈[1, ] E(G i )) and F = ( i∈[1, ] V(G i ), i∈[1, ] E(G i )).

Lattice of weights

As a fixed grid is able to represent images by assigning grey tones to pixels, the graph G is able to generate a number of derived graphs by assigning weights to the vertices and edges of the graph G. According to the applications, the weights can be real or integer, taking their values in R, R + , N, [-n, +n] , [0, +n]. The weight of a vertice v i is written w i , while the one of an edge e i j is written w i j . The set of all (edges and vertices)

weights is written w. The case where the weights are binary, belonging to {0, 1} may be interpreted as presence/absence: w i j = 1 and w k = 1 express respectively the existence of an edge e i j and of a vertice v k .

All edges and vertices of G with weight 0 do not exist in this weighted graph.

A possible lattice structure on the weights is given by the following. Let w 1 and w 2 be two sets of weights, we have w 1 ≺ w 2 whenever w 1 i j < w 2 i j and w 1 k < w 2 k . The supremum (resp. infimum) of a family of sets of weights is a set of weights where the weight of a given element is the greatest (resp. lowest) possible weight of the weights of the same element in the family.

Remark 2

In a graph, there may be isolated vertices, that is vertices which are not adjacent to an edge. On the contrary, each edge is adjacent to two vertices. For this reason not any binary distribution of weights on the vertices and edges of G represents a graph. It is the case if and only if each edge with weight 1 is adjacent to two vertices with weight 1. The same holds for any weight distributions. w correspond to a graph if each edge with weight w i j is such that w i j ≤ w i and w i j ≤ w j . In other words, this is the case if the extremities of an edge have weights which are not lower than the weight of the edge. Graphs may be used for modelling many different structures. In some cases vertex weight only have a physical meaning and the edge weights simply serve for storing intermediate results in the computation of the weights of the vertices. In other cases it is the converse. In such situations one does not care whether the weights represent a graph. In other situations on the contrary, one cares to define operators transforming an graph into another graph.

Neighborhood operations on graphs

Morphology really starts if one considers the neighborhood relations between vertices and edges. We now define operators taking as arguments such neighborhoods. The construction is incremental, from the smallest neighborhood to larger neighborhoods.

Adjunctions on graphs

In the graph G, we can consider sets of points as well as sets of edges. Therefore, it is convenient to consider operators that go from one kind of sets to the other one. In this section, we investigate such operators and we study their morphological properties. Then, based on these operators, we propose several dilations and erosions acting on the lattice of all subgraphs of G.

Let V(G 1 ) be a subset of V(G), we denote by G V(G 1 ) the set of all subgraphs of G whose vertex set is V(G 1 ). Let E(G 2 ) be a subset of E(G). We denote by G E(G 2 ) the set of all subgraphs of G whose edge set is E(G 2 ).

Definition 3 (edge-vertex correspondences, [10])

We define the operators δ EV , ε EV from E(G) into V(G) and the operators ε VE , δ VE from V(G) into E(G) as follows:

E(G) → V(G) V(G) → E(G)
Provide the object with a graph structure

E(G 1 ) → δ EV (E(G 1 )) such that (δ EV (E(G 1 )), E(G 1 )) = G E(G 1 ) V(G 1 ) → ε VE (V(G 1 )) such that (V(G 1 ), ε VE (V(G 1 ))) = G V(G 1 )
Provide its complement with a graph structure

E(G 1 ) → ε EV (E(G 1 )) such that (ε EV (E(G 1 )), E(G 1 )) = G E(G 1 ) V(G 1 ) → δ VE (V(G 1 )) such that (V(G 1 ), δ VE (V(G 1 ))) = G V(G 1 )
In other words, if

V(G 1 ) ⊆ V(G) and E(G 2 ) ⊆ E(G), (δ EV (E(G 2 )), E(G 2 )) is the smallest subgraph of G whose edge set is E(G 2 ), (V(G 1 ), ε VE (V(G 1 ))) is the largest subgraph of G whose vertex set is V(G 1 ), (ε EV (E(G 2 )), E(G 2 ))
is the smallest subgraph of G whose edge set is E(G 2 ), and

(V(G 1 ), δ VE (V(G 1 ))) is the largest subgraph of G whose vertex set is V(G 1 ).
These operators are illustrated in Figs. 1.1a-f. The following property locally characterizes them.

Property 4 ([10])

For any E(G 1 ) ⊆ E(G) and V(G 2 ) ⊆ V(G):

1. δ EV : E(G) → V(G) is such that δ EV (E(G 1 )) = {v i ∈ V(G) | ∃e i j ∈ E(G 1 )}; 2. ε VE : V(G) → E(G) is such that ε VE (V(G 2 )) = {e i j ∈ E(G) | v i ∈ V(G 2 ) and v j ∈ V(G 2 )}; 3. ε EV : E(G) → V(G) is such that ε EV (E(G 1 )) = {v i ∈ V(G) | ∀e i j ∈ E(G), e i j ∈ E(G 1 )};
. δ VE : V(G) → E(G) is such that δ VE (V(G 2 )) = {e i j ∈ E(G) | either v i ∈ V(G 2 ) or v j ∈ V(G 2 )}.
In other words, δ EV (E(G 1 )) is the set of all vertices which belong to an edge of E(G 1 ), ε VE (V(G 2 )) is the set of all edges whose two extremities are in V(G 2 ), ε EV (E(G 1 )) is the set of all vertices which do not belong to any edge of E(G 1 ), and δ VE (V(G 2 )) is the set of all edges which have at least one extremity in V(G 2 ).

From this characterization, we can recognize the general graph version of some operators introduced by Meyer and Angulo [START_REF] Meyer | Micro-viscous morphological operators[END_REF] (see also [START_REF] Meyer | Morphological operators for flooding, leveling and filtering images using graphs[END_REF]) for the hexagonal grid. By translating supremum and infimum of the graph lattice to the corresponding supremum and infimum of the lattice of weigths, we obtain the weighted version of these operators. The four basic operators of Definition 3 translate to:

(δ EV (w)) i = max{w i j | e i j ∈ E}, ε EV (w) i = min{w i j | e i j ∈ E}, (δ VE (w)) i j = max{w i , w j } and (ε VE (w)) i j = min{w i , w j }.
Before further analyzing the operators defined above, let us briefly recall some algebraic tools which are fundamental in mathematical morphology [START_REF] Ronse | Algebric foundations of morphology[END_REF].

Given two lattices L 1 and L 2 , an operator δ : L 1 → L 2 is called a dilation when it preserves the

supremum (i.e. ∀X ⊆ L 1 , δ(∨ 1 X ) = ∨ 2 {δ(x) | x ∈ X },
where ∨ 1 is the supremum in L 1 and ∨ 2 the supremum in L 2 ). Similarly, an operator which preserves the infimum is called an erosion.

Two operators ε : L 1 → L 2 and δ : L 2 → L 1 form an adjunction (ε, δ) when for any x in L 2 and any y in L 1 , we have δ(x) ≤ 1 y ⇔ x ≤ 2 ε(y), where ≤ 1 and ≤ 2 denote the order relations on respectively L 1 and L 2 . Given two operators ε and δ, if the pair (ε, δ) is an adjunction, then ε is an erosion and δ is a dilation.

Given two complemented lattices L 1 and L 2 , two operators α and β from L 1 into L 2 are dual (with respect to the complement) of each other when, for any x ∈ L 1 , we have β(x) = α(x). If α and β are dual of each other, then β is an erosion whenever α is a dilation.

Property 5 (dilation, erosion, adjunction, duality, [START_REF] Cousty | Some morphological operators in graph spaces[END_REF]) Let us compose these dilations and erosions to act on V(G) and E(G).

1

Definition 6 (vertex-dilation, vertex-erosion)

We define δ and ε that act on

V(G) (i.e., V(G) → V(G)) by δ = δ EV • δ VE and ε = ε EV • ε VE .
As compositions of respectively dilations and erosions, δ and ε are respectively a dilation and an erosion.

Moreover, by composition of adjunctions and dual operators, δ and ε are dual and (ε, δ) is an adjunction.

In fact, it can be shown that δ and ε correspond exactly to the usual notions of an erosion and of a dilation of a set of vertices in a graph [START_REF] Vincent | Graphs and mathematical morphology[END_REF][START_REF] Heijmans | Graph morphology in image analysis[END_REF]. It means, in particular that, when V(G) is a subset of the grid points Z d and when the edge set E(G) is obtained from a symmetrical structuring element, then the operators defined above are equivalent to the usual binary dilation and erosion by the considered structuring element.

For instance, in Fig. 1.1, V(G) is a rectangular subset of Z 2 and E(G) corresponds to the basic "cross" structuring element. It can be verified that the vertex sets in Fig. 1.1g and h, obtained by applying δ and ε to V(G 1 ) (Fig. 1.1b), are the dilation and the erosion by a "cross" structuring element of V(G 1 ).

We now consider a dual/adjunct pair of dilation and erosion acting on E(G).

Definition 7 (edge-dilation, edge-erosion, [START_REF] Cousty | Some morphological operators in graph spaces[END_REF])

We define ∆ and E that act on E(G) by ∆ = δ VE • δ EV and E = ε VE • ε EV .

Definition 8 ([10])

We define the operators δ ∆ and ε E by respectively

(δ(V(G 1 )), ∆(E(G 1 ))) and (ε(V(G 1 )), E(E(G 1 ))), for any G 1 ∈ G.
For instance, Figs. 1.1f and 1.1g present the results obtained by applying the operator δ ∆ and the opera-

tor ε E to the subgraph G 1 (Fig. 1.1b) of G (Fig. 1.1a).
Theorem 9 (graph-dilation, graph-erosion, [START_REF] Cousty | Some morphological operators in graph spaces[END_REF])

The operators δ ∆ and ε E are respectively a dilation and an erosion acting on the lattice (G, ). Furthermore, (ε E,δ ∆) is an adjunction.

Note that since lattice G is sup-generated by set S, it suffices to know the dilation of the graphs in S for characterizing the dilation of the graphs in G.

Compared to classical morphological operators on sets, the dilations and erosions introduced in this section furthermore convey some connectivity properties different than the ones which can be deduced from classical dilations and erosions. Observe, for instance, in Fig. 1.1g, that some 4-adjacent vertices of δ(V(G 1 )) are not linked by an edge in the graph δ ∆(G 1 ). These properties can be useful in further processing involving for instance connected operators [START_REF] Salembier | Flat zones filtering, connected operators, and filters by reconstruction[END_REF][START_REF] Ronse | Set-theoretical algebraic approaches to connectivity in continuous or digital spaces[END_REF][START_REF] Braga-Neto | Connectivity on complete lattices: new results[END_REF][START_REF] Ouzounis | Mask-based second-generation connectivity and attribute filters[END_REF].

Thanks to the operators presented in Definition 3, other intersecting adjunctions (hence dilations/erosions) can be defined on G:

1. (α 1 , β 1 ) such that ∀G 1 ∈ G, α 1 (G 1 ) = (V(G), E(G 1 )) and β 1 (G 1 ) = (δ EV (E(G 1 )), E(G 1 )); 2. (α 2 , β 2 ) such that ∀G 1 ∈ G, α 2 (G 1 ) = (V(G 1 ), ε VE (V(G 1 ))) and β 2 (G 1 ) = (V(G 1 ), / 0); 3. (α 3 , β 3 ) such that ∀G 1 ∈ G, α 3 (G 1 ) = (ε EV (E(G 1 )), ε VE • ε EV (E(G 1 )))
and

β 3 (G 1 ) = (δ EV • δ VE (V(G 1 )), δ VE (V(G 1 ))).
The adjunction (α 3 , β 3 ) is illustrated in Fig. 1.1i and 1.1j. Note also that, using usual graph terminologies, β 1 (resp. α 2 ) can be defined as the operator which associates to a graph the graph induced by its edge set (resp.

vertex set).

A more general version of those operators can be obtained in the framework of complexes [START_REF] Dias | Some morphological operators on simplicial complexes spaces[END_REF], allowing us to deal for example with meshes. There also exist other recent graph-based approaches to morphology, for example based on hypergraphs [START_REF] Bloch | Mathematical morphology on hypergraphs: Preliminary definitions and results[END_REF] or on discrete differential equations [START_REF] Ta | Partial difference equations over graphs: Morphological processing of arbitrary discrete data[END_REF].

Filters

In mathematical morphology, a filter is an operator α acting on a lattice L, which is increasing (i.e. ∀x, y ∈

L, α(x) ≤ α(y) whenever x ≤ y) and idempotent (i.e. ∀x ∈ L, α(α(x)) = α(x)). A filter α on L which is extensive (i.e. ∀x ∈ L, x ≤ α(x)
) is called a closing on L whereas a filter α on L which is anti-extensive (i.e.

∀x ∈ L, α(x) ≤ x) is called an opening on L. It is known that composing the two operators of an adjunction yields an opening or a closing depending on the order in which the operators are composed [START_REF] Ronse | Algebric foundations of morphology[END_REF]. In this section, the operators of Section 1.3 are composed to obtain filters on V(G), E(G) and G.

Definition 10 (opening, closing, [START_REF] Cousty | Some morphological operators in graph spaces[END_REF])

1. We define γ 1 and φ 1 , that act on V(G), by 3. We define the operators γ Γ 1 and φ Φ 1 by respectively In fact, by composing δ EV with ε VE and δ EV with ε VE , we obtain smaller filters.

γ 1 = δ • ε and φ 1 = ε • δ. 2. We define Γ 1 and Φ 1 , that act on E(G), by Γ 1 = ∆ • E and Φ 1 = E • ∆. a: G 2 b: γ Γ 1 (G 2 ) c: γ Γ 1/2 (G 2 ) d: β 3 • α 3 (G 2 ) e: G 3 f: φ Φ 1 (G 3 ) g: φ Φ 1/2 (G 3 ) h: α 3 • β 3 (G 3 )
γ Γ 1 (G 1 ) = (γ 1 (V(G 1 )), Γ 1 (E(G 1 ))) and φ Φ 1 (G 1 ) = (φ 1 (V(G 1 )), Φ 1 (E(G 1 ))) for any G 1 ∈ G.
Definition 11 (half-opening, half-closing, [START_REF] Cousty | Some morphological operators in graph spaces[END_REF])

1. We define γ 1/2 and φ 1/2 , that act on V(G), by γ 1/2 = δ EV • ε VE and φ 1/2 = ε EV • δ VE . 2. We define Γ 1/2 and Φ 1/2 , that act on E(G) by Γ 1/2 = δ VE • ε EV and Φ 1/2 = ε VE • δ EV .
3. We define the operators γ Γ 1/2 and φ Φ 1/2 by respectively

γ Γ 1/2 (G 1 ) = (γ 1/2 (V(G 1 )), Γ 1/2 (E(G 1 ))) and φ Φ 1/2 (G 1 ) = (φ 1/2 (V(G 1 )), Φ 1/2 (E(G 1 ))), for any G 1 ∈ G.
Thanks to Property 4, the operators defined above can be locally characterized.

Let V(G 1 ) ⊆ V(G)
and E(G 2 ) ⊆ E(G), we have:

γ 1/2 (V(G 1 )) = {v i ∈ V(G 1 ) | ∃e i j ∈ E(G) with v j ∈ V(G 1 )} = V(G 1 ) \ {v i ∈ V(G 1 ) | ∀e i j ∈ E(G), v j / ∈ V(G 1 )} Γ 1/2 (E(G 2 )) = {e i j ∈ E(G) | {e ik ∈ E(G)} ⊆ E(G 2 )} = E(G 2 ) \ {e ∈ E(Y ) | ∀v i ∈ e, ∃e i j ∈ E(G) with e i j / ∈ E(G 2 )} φ 1/2 (V(G 1 )) = {v i ∈ V(G) | either v i ∈ V(G 1 ) or ∀e i j ∈ E(G), v j ∈ V(G 1 )} = V(G 1 ) ∪ {v i ∈ V(G 1 ) | ∀e i j ∈ E(G), v j ∈ V(G 1 )} Φ 1/2 (E(G 2 )) = {e i j ∈ E(G) | ∃e ik ∈ E(G 2 ) and ∃e jl ∈ E(G 2 )} = Y ∪ {e i j ∈ E(G 2 ) | v i ∈ δ EV (E(G 2 )) and v j ∈ δ EV (E(G 2 ))}.
Informally speaking, γ 1/2 removes from G 1 its isolated vertices whereas Γ 1/2 removes from G 2 the edges which do not contain a vertex completely covered by edges in G 2 . It may be furthermore seen that γ 1/2 (resp. 1. The operators γ 1/2 and γ 1 (resp. Γ 1/2 and Γ 1 ) are openings on V(G) (resp. E(G)) and φ 1/2 , and Φ 1 (resp. Φ 1/2 and φ 1 ) are closings on V(G) (resp. E(G)).

Γ 1/2 ) is the dual of φ 1/2 (resp. Φ 1/2 ). Thus, φ 1/2 adds to G 1 the vertices of V(G 1 )

The family

G is closed under γ Γ 1/2 , φ Φ 1/2 , γ Γ 1 , and φ Φ 1 .
3. The operators γ Γ 1/2 and γ Γ 1 are openings on G and φ Φ 1/2 and φ Φ 1 are closings on G.

Composing the operators of the adjunctions (α i , β i ), defined at the end of Section 1.3, also yields remarkable openings and closings. Indeed, it can be easily seen that: assigns to each edge the highest weight of its adjacent vertices; but each adjacent vertice has been assigned by ε EV the weight of its lowest edge. So if w i j is left unchanged by Γ 1/2 , it means that the edge e i j is (one of) the lowest edges of v i or of v j , say v i . Its weight is higher or equal to the weight of the lowest edge of v j . Thus, using some well-known properties of minimum spanning trees (see Section 1.6.3 for a precise definition of a minimum spanning tree), it can be shown that the graph induced by the set of edges that are left invariant by Γ 1/2 is the union of all mininimum spanning trees of this graph, closely related to the Gabriel graph [START_REF] Gabriel | A new statistical approach to geographic variation analysis[END_REF].

α 1 • β 1 = α 1 , α 2 • β 2 = α 2 , β 1 • α 1 = β 1 and β 2 • α 2 = β 2 .
It is possible to associate with any lattice L, the lattice of all increasing operators on L. In this context, two filters ϕ 1 and ϕ 2 on the lattice L are said ordered if, for any ∈ L, ϕ 1 (x) ≤ ϕ 2 (x) or if, for any x ∈ L, ϕ 2 (x) ≤ ϕ 1 (x). A usual way to build a hierarchy of filters (i.e. an ordered family of filters) from an adjunct pair (α, β) of erosion and dilation consists of building the dilations and erosions obtained by iterating several times α and β. In general, composing these iterated versions of α and β leads to hierarchies of filters when the number of iterations increases. By combining and iterating the operators that we have defined in this section, we obtain [START_REF] Cousty | Some morphological operators in graph spaces[END_REF] hierarchies of filters in the lattice G that perform better than the classical ones, in the sense that they are able to remove more noise (see Fig. 1.3.)

Connected operators and filtering with the component tree

Gray-level connected operators [START_REF] Salembier | Flat zones filtering, connected operators, and filters by reconstruction[END_REF] act by merging neighboring "flat" zones. They cannot create new contours and, as a result, they cannot introduce in the output image a structure that is not present in the input image. Furthermore, they cannot modify the position of existing boundaries between regions, and therefore have very good contour preservation properties.

To create "flat" zones, a simple operation on a weighted graph is thresholding, that produces a level set.

For λ ∈ R + , the level-sets of an edge-weighted graph are denoted

w < E [λ] = {e i j ∈ E|w i j ≤ λ}. We define C < E (a)
w < E [λ]
. We note that one can reconstruct w from C < E ; more precisely, we have:

w i j = min{λ | [λ,C] ∈ C < E , e i j ∈ E(C)} (1.1)
One can remark that two elements of C < E are either disjoint or nested, thus it is easy to order the elements of C < E in a tree. This tree is called the (min) component tree, and there exists fast algorithms to compute it [START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF][START_REF] Najman | Building the component tree in quasi-linear time[END_REF].

Using C < E allows us to deal with specific components of w. For example, a minimum of w is a component

C such that there exists λ with [λ,C] ∈ C < E and it does not exist [λ 1 ,C 1 ] ∈ C < E with C 1 C and C 1 = C.
Observe that a minimum of w is a graph. The set of all minima of w is denoted M. Similarly, we can define C > E allowing us to deal with maxima of edge-weighted graphs, C < V and C > V allowing us to deal with node-weighted graphs, and C < VE and C < VE allowing us to deal with node-and-edge weighted graphs. We mention that other trees are possible, for example the binary partition tree [START_REF] Salembier | Binary partition tree as an efficient for image processing, segmentation and information retrieval[END_REF], the tree of level lines also known as the inclusion tree or the tree of shapes [START_REF] Caselles | Geometric Description of Images as Topographic Maps[END_REF], etc. The interest of the tree of shapes is that it allows us to interact both with maxima and minima, in a self-dual manner. See [START_REF] Salembier | Connected operators based on tree pruning strategies[END_REF] for a survey of the usage of those trees in image processing. Here, we illustrate the usage of the component tree for filtering. Given Eq. (1.1), filtering a graph can be seen as equivalent to removing some components of (say) C < E . Such a filtering is called flooding. One way to make this idea practicable is to design an attribute that tells us if a given component should be kept or not. Among the numerous attributes that can be computed, three are natural: the height, the area, and the volume (Fig. 1

.4). Let [λ,C] ∈ C < E . We define height([λ,C]) = max{λ -w i j |e i j ∈ E(C)} (1.2) area([λ,C]) = |V(C)| (1.3) volume([λ,C]) = ∑ e i j ∈E(C) (λ -w i j ) (1.4)
For example, removing all the components whose area is lower than a threshold is a closing of w (Fig. 1.4.e).

Remark that a filtering with either the height or the volume is not a closing, as such a filtering is not idempotent. As the components of the level sets can be ordered into a tree, they form a hierarchy of components. In the context of classification [START_REF] Benzécri | L'Analyse des données: la Taxinomie[END_REF], hierarchies are widely studied, and the morphological framework can shed some light on the tools that are developed in that community. For example, let us look at the application Ψ that associates to any set of edge-weights w the map Ψ(w) such that for any edge e i j ∈ E, Ψ(w)(e

i j ) = min{λ | [λ,C] ∈ C < E , v i ∈ V(C), v j ∈ V(C)}.
Intuitively, and using a geographical metaphore, Ψ(w)(e i j ) is the lowest altitude to which one has to climb to go from v i to v j . It is straightforward to see that Ψ(w) ≤ w, that Ψ(Ψ(w)) = Ψ(w) and that if w ≤ w, Ψ(w ) ≤ Ψ(w). Thus Ψ is an opening [START_REF] Leclerc | Description combinatoire des ultramétriques[END_REF]. We remark that the subset of strictly positive maps that are defined on the complete graph (V, V × V) and that are open with respect to Ψ is the set of ultrametric distances on V. The mapping Ψ is known under several names, including "subdominant ultrametric" and "ultrametric opening". It is well known that Ψ is associated to the simplest method for hierarchical classification called single linkage clustering [START_REF] Jardine | Mathematical taxonomy[END_REF][START_REF] Gower | Minimum spanning tree and single linkage cluster analysis[END_REF], closely related to Kruskal's algorithm [START_REF]On the shortest spanning subtree of a graph and the traveling salesman problem[END_REF] for computing a minimum spanning tree.

Before concluding the section, let us mention another flooding that has been used as a preprocessing step for watershed segmentation with markers. It is called geodesic reconstruction from the markers [START_REF] Meyer | Morphological segmentation[END_REF][START_REF] Beucher | The morphological approach to segmentation: the watershed transformation[END_REF],

where the markers is a subgraph. It consists in removing all the components of C < E that are not marked (i.e. that do not contain a vertice of the markers) and is given as a function w R such that, for every edge e, we set w R (e) to be equal to the level λ of the lowest component of w containing e and at least one vertice of the markers. Observe that any component of w R indeed contains at least one vertice of the markers. Given some markers, the geodesic reconstruction is a closing. Such a closing is also useful as an efficient preprocessing for a fast power-watershed optimization algorithm (see [START_REF] Couprie | Power Watersheds: A Unifying Graph Based Optimization Framework[END_REF] and Section 1.8).

Watershed cuts

There exist many possible ways for defining a watershed [START_REF] Vincent | Watersheds in digital spaces: An efficient algorithm based on immersion simulations[END_REF][START_REF] Najman | Watershed of a continuous function[END_REF][START_REF] Roerdink | The watershed transform: Definitions, algorithms and parallelization strategies[END_REF][START_REF] Bertrand | On topological watersheds[END_REF][START_REF] Cousty | Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle[END_REF][START_REF] Cousty | Watershed cuts: thinnings, shortest-path forests and topological watersheds[END_REF]. Intuitively, the watershed of a function (seen as a topographical surface) is composed of the locations from which a drop of water could flow towards different minima. The framework of edge-weighted graph allows the formalization of this principle and the proof of several remarkable properties [START_REF] Cousty | Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle[END_REF] that we review in the sequel of the section. We first show that watershed cuts can be equivalently defined by their "catchment basins" (through a steepest descent property) or by the "dividing lines" separating these catchment basins (through the drop of water principle). As far as we know, in discrete frameworks, a similar property does not hold. The second property establishes the optimality of watershed-cuts: there is an equivalence between the watershed-cuts and the separations induced by a minimum spanning forest relative to the minima.

The drop of water principle

Definition 13 (from Def. 12 in [START_REF] Bertrand | On topological watersheds[END_REF])

Let G 1 and G 2 be two non-empty subgraphs of G. We say that G 2 is an extension of G 1 (in G) if G 1 G 2 and if any component of G 2 contains exactly one component of G 1 .
The notion of extension is very general. Many segmentation algorithms iteratively extend some seed components in a graph: they produce an extension of the seeds. Most of them terminate once they have reached an extension which cover all the vertices of the graph. The separation which is thus produced is called a graph cut. Let S ⊆ E. We denote by S the complementary set of S in E, i.e., S = E \ S. Recall that the graph induced by S, given by the dilation β 1 , is the graph whose edge set is S and whose vertex set is made of all points which belong to an edge in S, i.e., ({v ∈ V | ∃e ∈ S, v ∈ e}, S). In the following, the graph induced by S is also denoted by S.

Definition 14

Let G 1 G and S ⊆ E. We say that S is a (graph) cut for G 1 if S is an extension of G 1 and if S is minimal for this property, i.e., if T ⊆ S and T is an extension of G 1 , then we have T = S.

We introduce the watershed cuts of an edge-weighted graph. To this end, we formalize the drop of water principle. Intuitively, the catchment basins constitute an extension of the minima and they are separated by "lines" from which a drop of water can flow down towards distinct minima.

Let π = (v 0 , • • • , v n ) be a path. The path π is descending if, for any i ∈ [1, l -1], w(v i-1 , v i ) ≥ w(v i , v i+1 ).
Definition 15 (drop of water principle, [START_REF] Cousty | Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle[END_REF])

Let S ⊆ E. We say that S is a watershed cut (or simply a watershed) if S is an extension of M and if for any

e i j = {v i , v j } ∈ S, there exist π 1 = (v 1 0 = v i , • • • , v 1 n ) and π 2 = (v 2 0 = v j , • • • , v 2 m
) which are two descending paths in S such that v 1 n and v 2 m are vertices of two distinct minima of w; and w i j ≥ w({v

1 0 , v 1 1 }) (resp. w i j ≥ w({v 2 0 , v 2 1 })), whenever π 1 (resp. π 2 ) is not trivial.
We illustrate the previous definition on the edge-weighted graph depicted in Fig. and by e = {v 1 , v 2 } the only edge whose altitude is 8. It may be seen that S (in bold Fig. 1.6b) is an extension of M. We also remark that there exists π 1 (resp. π 2 ) a descending path in S from v 1 (resp. v 2 ) to the minimum at altitude 1 (resp. 3). The altitude of the first edge of π 1 (resp. π 2 ) is lower than the altitude of e. It can be verified that the previous properties hold true for any edge in S. Thus, S is a watershed of F.

Catchment basins by a steepest descent property

A popular alternative to Definition 15 consists of defining a watershed exclusively by its catchment basins and the paths of steepest descent of w [START_REF] Meyer | Topographic distance and watershed lines[END_REF][START_REF] Najman | Watershed of a continuous function[END_REF][START_REF] Soille | An efficient algorithm for drainage networks extraction on DEMs[END_REF][START_REF] Roerdink | The watershed transform: Definitions, algorithms and parallelization strategies[END_REF] and does not involve any property of the divide. The following theorem [START_REF]Mathematical morphology: from theory to applications[END_REF] establishes the consistency of watershed cuts in edge-weighted graphs: they can be equivalently defined by a steepest descent property on the catchment basins (regions) or by the drop of water principle on the cut (border) which separate them. As far as we know, there is no definition of watershed in vertex-weighted graphs that verifies a similar property. This theorem thus emphasizes that the framework of edge-weighted graphs is adapted for the study of discrete watersheds.

Let π = (v 0 , • • • , v l ) be a path in G. The path π is a path of steepest descent (for w) if, for any i ∈ [1, l], w(v i-1 , v i ) = (ε EV w) i-1 = min{w i j |∀ j such that e i j ∈ E}.

Definition 16 ([13])

Let S ⊆ E be a cut for M. We say that S is a basin cut (of w) if, from each point of V to M, there exists, in the graph induced by S, a path of steepest descent for w. If S is a basin cut of w, any component of S is called a catchment basin (of w, for S).

Theorem 17 (consistency, [START_REF] Cousty | Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle[END_REF])

Let S ⊆ E be a cut for M. The set S is a watershed if and only if S is a basin cut of w.

Minimum spanning forests

We establish the optimality of watersheds. To this end, we introduce the notion of minimum spanning forests rooted in some subgraphs of G. Each of these forests induces a unique graph cut. The main result of this study (Th. [START_REF] Choquet | étude de certains réseaux de routes[END_REF]) states that a graph cut is induced by a minimum spanning rooted in the minima of a function if and only if it is a watershed of this function.

Definition 18 (rooted MSF, [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF])

Let G 1 and G 2 be two nonempty subgraphs of G. We say that G 2 is rooted in We say that G 2 is a minimum spanning forest (MSF) rooted in

G 1 if V(G 1 ) ⊆ V(G 2 )
G 1 if (1) G 2 is spanning for V, (2) G 2 is rooted in G 1 , and (3)
the weight of G 2 is less than or equal to the weight of any graph G 3 satisfying ( 1) and

(2) (i.e., G 3 is both spanning for V and rooted in G 1 ). The set of all minimum spanning forests rooted in G 1 is denoted by MSF(G 1 ).

The above definition of rooted MSFs allows the usual notions of graph theory based on trees and forests to be recovered. In particular, if v is a vertex of V , it can be seen that any element in MSF({v}, / 0) is a minimum spanning tree of (G, w), and that, conversely, any minimum spanning tree of (G, w) belongs to MSF({v}, / 0).

Let us consider the edge-weighted graph G and the subgraph M (in bold) of Fig. 1.6a. It can be verified that the graph G 1 (in bold in Fig. 1.6c) is an MSF rooted in M.

We now have the mathematical tools to present the main result of this section (Th. [START_REF] Choquet | étude de certains réseaux de routes[END_REF]) which establishes the optimality of watersheds.

Let G 1 be a subgraph of G and let G 2 be a spanning forest rooted in G 1 . There exists a unique cut for G 2 and this cut is also a cut for G 1 . We say that this unique cut is the cut induced by G 2 .

Theorem 19 (optimality, [START_REF] Cousty | Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle[END_REF])

Let S ⊆ E. The set S is a cut induced by a MSF rooted in M if and only if S is a watershed cut.

Illustrations to segmentation

In this subsection, we illustrate the versatility of the proposed framework to perform segmentation on different kinds of geometric objects. Firstly, we show how to segment triangulated surfaces by watershed cuts, and secondly we apply the watershed cuts to the segmentation of diffusion tensors images, which are medical images associating a tensor to each voxel.

3D shape acquisition and digitizing have received more and more attention for a decade, leading to an increasing amount of 3D surface-models (or meshes) such as the one in Fig. 1.7d. In a recent work [START_REF] Philipp-Foliguet | Artwork 3D Model Database Indexing and Classification[END_REF], a new search engine has been proposed for indexing and retrieving objects of interests in a database of meshes (EROS 3D) provided by the French Museum Center for Research. One key idea of this search engine is to use region descriptors rather than global shape descriptors. In order to produce such descriptors, it is then essential to obtain meaningful mesh segmentations.

Informally, a mesh M in the 3D Euclidean space is a set of triangles, sides of triangles and points such that each side is included in exactly two triangles (see Fig. 1.7a). In order to perform a watershed cut on such a mesh, we build a graph G = (V, E) whose vertex set V is the set of all triangles in M and whose edge set E is composed by the pairs e i j = {v i , v j } such that v i and v j are two triangles of M that share a common side (see Fig. 1.7a). The graph G is known under the name of 2-dual of the surface mesh [START_REF] Grady | Discrete Calculus: Applied Analysis on Graphs for Computational Science[END_REF].

To obtain a segmentation of the mesh M thanks to a watershed cut, we need to weight the edges of G (or equivalently the sides of M) by a map whose values are high around the boundaries of the regions that we want to separate. We have found that the interesting contours on the EROS 3D meshes are mostly located on concave zones. Therefore, we weight the edges of G by a weighting w which behaves like the inverse of the mean curvature of the surface (see [START_REF] Philipp-Foliguet | Artwork 3D Model Database Indexing and Classification[END_REF] for more details). Then, we can compute a watershed cut (in bold in Fig. 1.7b) which leads to a natural and accurate mesh segmentation in the sense that the "borders" of the regions are made of sides of triangles (in bold in Fig. 1.7c) of high curvature.

The direct application of this method on the mesh shown Fig. 1.7d leads to a strong over-segmentation (Fig. 1.7e) due to the huge number of local minima. By using the methodology introduced in section 1.5 to remove from w all the minima which have a depth lower than a predefined threshold (here 50) A watershed cut of the filtered w is depicted in Fig. 1.7f.

In the medical context, Diffusion Tensor Images (DTIs) [START_REF] Basser | MR diffusion tensor spectroscopy and imaging[END_REF] provide a unique insight into oriented structures within tissues. A DTI T maps the set of voxels V ⊆ Z 3 (i.e. V is a cuboid of Z 3 ) into the set of 3 × 3 tensors (i.e. 3 × 3 symmetric positive definite matrices). The value T (v) of a DTI T at a voxel v ∈ V describes the diffusion of water molecules at v. For instance, the first eigenvector of T (v) (i.e. the one whose associated eigenvalue is maximal) provides the principal direction of water molecules diffusion at point x and its associated eigenvalue gives the magnitude of the diffusion along this direction. Since water molecules highly diffuse along fiber tracts and since the white matter of the brain is mainly composed of fiber tracts, DTIs are particularly adapted to the study of brain architecture. Fig. 1.8a shows a representation of a cross-section of a brain DTI where the tensors are represented by ellipsoids. Indeed, the data of a tensor is equivalent to the one of an ellipsoid. In the brain, the corpus callosum is an important structure made of fiber tracts connecting homologous areas of each hemisphere. In order to track the fibers that pass through the corpus callosum, it is necessary to segment it first. The next paragraph briefly reviews how to reach this goal thanks to watershed cuts [START_REF] Cousty | Watershed cuts: thinnings, shortest-path forests and topological watersheds[END_REF].

We consider the graph G = (V, E) induced by the 6-adjacency and defined by e

i j ∈ E iff v i ∈ V, v j ∈ V and Σ k∈{1,2,3} |v k i -v k j | = 1, where v i = (v 1 i , v 2 i , v 3 i ) and v j = (v 1 j , v 2 j , v 3 j ).
In order to weight any edge e i j of G by a dissimilarity measure between the tensors T (v i ) and T (v j ), we choose the Log-Euclidean distance which is known to satisfy interesting properties [START_REF] Arsigny | Log-Euclidean metrics for fast and simple calculus on diffusion tensors[END_REF]. Then, we associate to each edge e i j ∈ E the weight

w i j = log(T (v i )) -log(T (v j ))
, where log denotes the matrix logarithm and . the Euclidean (sometimes also called Frobenius) norm on matrices. To segment the corpus callosum in this graph, we extract (thanks to a statistical atlas), markers for both the corpus callosum and its background and we compute an MSF-cut for these markers. An illustration of this procedure is shown in Figs. 1.8. To conclude this section, let us mention that spatio-temporal graphs are also feasible. For example, in [START_REF] Cousty | Segmentation of 4D cardiac MRI: automated method based on spatio-temporal watershed cuts[END_REF], a 3D+t segmentation of the left-ventricle on cine-MR images was computed, showing an improvemnt with respect to the segmentation of each 3D volume separately.

MSF cut hierarchy and saliency maps

We now study some optimality properties of hierarchical segmentations (see [START_REF] Meyer | The dynamics of minima and contours[END_REF][START_REF] Najman | Geodesic saliency of watershed contours and hierarchical segmentation[END_REF][START_REF] Guigues | Scale-sets image analysis[END_REF][START_REF] Arbeláez | A metric approach to vector-valued image segmentation[END_REF][START_REF] Meyer | Segmentation, minimum spanning tree and hierarchies[END_REF][START_REF] Najman | On the equivalence between hierarchical segmentations and ultrametric watersheds[END_REF] for examples of hierarchical segmentations) in the framework of edge-weighted graphs, where the cost of an edge is given by a dissimilarity between two points of an image. Since the pioneering work of [START_REF] Jardine | Mathematical taxonomy[END_REF][START_REF] Gower | Minimum spanning tree and single linkage cluster analysis[END_REF] stating an equivalence between hierarchies and minimum spanning trees (MST), a large number of hierarchical schemes rely on the construction of such a tree (see [START_REF] Morris | Graph theory for image analysis: an approach based on the shortest spanning tree[END_REF] for one of the oldest). We formalize a fundamental operation called uprooting that allows us to merge a marked region with one of its neighbors with the cheapest cost. When applied sequentially on the weighted graph of neighboring regions, the uprooting builds a MST of this neighboring graph. Intuitively, one can see that, if one starts from a minimum spanning forest (MSF) rooted in the minima of the image (or, equivalently, from a watershed cut), then one builds a hierarchy of MSFs of the original image itself, the last uprooting step giving an MST of this original image.

More surprisingly, Th. 23 states that the two processes are equivalent: any MST of the original image can be built from an uprooting sequence on a watershed cut. Thus, watershed cuts are the only watershed that allows the building of hierarchical segmentations that are optimal with respect to the original image, in the sense that they "preserve" the MST of the original image.

Definition 20 (MSF hierarchy, [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF])

Let M = M 1 , . . . , M be a sequence of pairwise distinct minima of w and let T = G 0 , . . . G be a sequence of subgraphs of G. We say that T is an MSF hierarchy for S if for any i ∈ [0, ], the graph G i is an MSF rooted in

[M \ {M j | j ∈ [1, i]}],
and for any i ∈ [1, ], we have G i-1 G i .

Theorem 21 ([61, 14])

Any G i of an MSF hierarchy is a watershed cut of the geodesic reconstruction w R where the markers are the minima rooting the MSF G i .

Uprootings and MSF hierarchies

In this section, we introduce a simple transformation, called uprooting, that allows a forest G 1 rooted in a graph G 2 to be incrementally transformed into a forest G 3 rooted in a graph G 4 obtained by removing some components of G 2 . Through an equivalence theorem, we establish an important link between the uprooting transform and the MSF hierarchies. This result opens the way toward efficient algorithms for computing MSF hierarchies.

Let G 1 be a subgraph of G that is spanning for V, and let v ∈ V. We denote by

CC v (G 1 ) the component of G 1 whose vertex set contains v. Let V ⊆ V, we set CC V (G 1 ) = {CC v (G 1 ) | v ∈ V }.
Let G 1 G, and let e i j = {v i , v j } ∈ E. The edge e i j is outgoing from

G 1 if e i j is made of a vertex in V(G 1 )
and of a vertex in V(G 1 ). In the following, by abuse of notation, we write G 1 {e i j } for the supremum of G 1 and the graph induced by {e i j }: G 1 {e i j } = (V(G 1 ) ∪ e i j , E(G 1 ) ∪ {e i j }).

Let G 1 , G 2 , and G 3 be three subgraphs of G such that G 1 is spanning for V and such that G 1 = G 2 . We say that G 2 is an elementary uprooting of G 1 by G 3 if there exists an edge e of minimum weight among the edges outgoing from CC V(G 3 ) (G 1 ) such that G 2 = G 1 {u}. We also say that G 2 is an elementary uprooting of G 1 by G 3 if G 2 = G 1 and if there is no edge outgoing from CC V(G 3 ) (G 1 ).

Definition 22 ([14])

Let S = M 1 , . . . , M be a sequence of pairwise distinct minima of w. An uprooting by S is a sequence G 0 , . . . , G of graphs such that G 0 ∈ MSF(M) and, for any i ∈ [1, ], G i is an elementary uprooting of G i-1 by M i .

Theorem 23 ([14])

Let S = M 1 , . . . , M be a sequence of pairwise distinct minima of w. Let T = G 0 , . . . G be a sequence of subgraphs of G. The sequence T is an MSF hierarchy for S if and only if the sequence T is an uprooting by S.

Saliency maps

The cuts of the sequence of any MSF hierarchy can be stacked to form a weighting called the saliency map.

The saliency map allows us to easily assess the quality and the robustness of a hierarchical segmentation.

Furthermore, it is a weigthed graph, and can be further processed if needed, for example to remove small regions unwanted in the hierarchy.

Let us give a precise defition of the saliency map [START_REF] Najman | Geodesic saliency of watershed contours and hierarchical segmentation[END_REF][START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF]. We first need to define, for a graph G, the map

φ as φ(G) = {α 2 (G i ) | G i is a component of G}.
In other words, φ(G) is the union of all the graphs induced by the connected components of G. It is easy to see that φ is an opening.

Let M = M 1 , . . . , M be a sequence of pairwise distinct minima of w and Let T = G 0 , . . . G be a

MSF hierarchy for M . The saliency map s for T is the map such that for any e i j ∈ E, either s i j = k if there exists k such that k is the lowest number satisfying e i j ∈ φ(G k ) or s i j = l + 1 if it does not exists any G k such that e i j ∈ φ(G k ). Observe in particular that if e i j ∈ E(φ(G 0 )), s i j = 0 and that s

[λ] = φ(G λ ) for λ ∈ {0, • • • , l}.
Under the term of ultrametric watershed, one can give a computable definition to saliency maps, allowing to show the equivalenve between the set of hierarchical segmentations and the set of saliency maps [START_REF] Najman | On the equivalence between hierarchical segmentations and ultrametric watersheds[END_REF].

Application to image segmentation

To use the framework in practice, we have to design an order on the minima of w. Let µ be an attribute on

C < E (i.e. a function from C < E to R that is increasing on C < E
) such as the area, the volume or the height. We compute an extinction measure [START_REF] Vachier | Extinction value: a new measurement of persistence[END_REF][START_REF] Bertrand | On the dynamics[END_REF] µ e to each minima of w by first definining a strict total order relation ≺ on the set of minima (based for example on the altitude of each minimum) such that M

0 ≺ M 1 ≺ • • • ≺ M l ; then we set µ e (M 0 ) = ∞ and µ e (M i ) = min{µ([λ,C]) | [λ,C] ∈ C < E , there exists M j a minimum of w, M j ≺ M i } (1.5)
The map µ e will define the order ≺ e of the sequence for the hierachy of MSF: M i ≺ e M j whenever µ e (M i ) < µ e (M j ). @ @ @ @ @ q p 0 finite ∞ [START_REF] Couprie | Power Watersheds: A Unifying Graph Based Optimization Framework[END_REF] for image segmentation includes several popular segmentation algorithms as special cases of the parameters p and q. The power watershed may be optimized efficiently with a maximum spanning forest calculation.

where ∇I is the normalized gradient of the image I. The gradient for a grey level image is I i -I j . As the weights are inverted, the maxima are considered instead of minima, and a thalweg is computed instead of watershed. A thalweg is the deepest continuous line along a valley. In the rest of the paper, we continue to use by convention the term "watershed" instead of "thalweg".

Given foreground F and background B seeds, and p, q two real positive values, the energy presented for binary segmentation in [START_REF] Couprie | Power Watersheds: A Unifying Graph Based Optimization Framework[END_REF] is given by

x pq = arg min x ∑ e i j ∈E w p i j |x i -x j | q s.t. x(F) = 1, x(B) = 0. (1.7)
In this energy, w i j can be interpreted as a weight enforcing a regularization of the contours, such that any (usually unwanted) high-frequency content is penalized in x. The energy defined in (1.7) essentially forces

x to remain smooth within the object, while allowing it to vary quickly close to point clusters near the boundary of the object. The data constraints enforce fidelity of x to a specified configuration, taking the values zero and one as the reconstructed object indicator. Observe that the values of x may not necessarily be binary when the value of q is strictly greater than one.

The different values of p and q lead to different algorithms for optimizing the energy. Those algorithms form the underpinning for many of the advanced image segmentation methods in the literature. Table 1.1

gives a reference for the different algorithms generated by various values of p and q. The limit cases are the limit of the minimizers of eq. (1.7), e.g., the case p → ∞ reads

x q = lim p→∞ x pq . (1.8)
Let us highlight the main choices for those parameters.

• When the power on the weight, p, is finite, and the exponent q = 1, we recover [START_REF] Allène | Some links between extremum spanning forests, watersheds and min-cuts[END_REF] the Max-Flow (Graph Cuts) energy which can be optimized by a max flow algorithm.

• When q = 2, we obtain a combinatorial Dirichlet problem also known as the Random walker problem [START_REF] Grady | Random walks for image segmentation[END_REF].

• When q and p converge toward infinity with the same speed, then [START_REF] Sinop | A seeded image segmentation framework unifying graph cuts and random walker which yields a new algorithm[END_REF] a solution to (1.8) can be computed by the shortest path (geodesics) algorithm [START_REF] Falcão | The image foresting transformation[END_REF][START_REF] Peyre | Geodesic methods in computer vision and graphics[END_REF].

• As described in [START_REF] Couprie | Power Watersheds: A Unifying Graph Based Optimization Framework[END_REF], by raising the power p toward infinity and varying the power q we obtain a family of segmentation models which we refer to as power watershed, that we detail below.

A primary advantage of power watershed with varying q is that the main computational burden of these algorithms depends on an MSF computation, which is extremely efficient [START_REF] Chazelle | A minimum spanning tree algorithm with inverse-Ackermann type complexity[END_REF]. For example, interpreted from the standpoint of the Gaussian weighting function in (1.6), it is clear that we may associate β = p to understand that the watershed equivalence comes from operating the weighting function in a particular parameter range. In the case q = 1, an important insight from this connection is that above some value of β we can replace the expensive max-flow computation with an efficient maximum spanning forest computation.

Let us review some important theoretical results. First, we highlight that the cut obtained when minimizing the energy (1.8) is a watershed cut [START_REF] Cousty | Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle[END_REF], and thus a Maximum Spanning Forests [START_REF] Cousty | Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle[END_REF] (MSF). Let x be a solution to (1.8) and s be the segmentation result defined as

s i = 1 if x i ≥ 1 2 , 0 if x i < 1 2 .
. The set of edges e i j such that s i = s j is a q-cut.

Theorem 24 ([15])

For q ≥ 1, any q-cut is a watershed cut of the (geodesically) reconstructed weights. Furthermore, if every connected component of M contains at least a vertex of B ∪ F, and q ≥ 1, then any q-cut when p → ∞ is an MSF cut for w.

An algorithm is presented in Algorithm 1 to optimize the (unique) watershed that optimizes the energy for q ≥ 1 and p → ∞. The set of parameters p → ∞ and q = 2 is particularly interesting.

1. The power watershed algorithm in the case q = 2 has a well-defined behavior in the absence or lack of weight information (presence of plateaus); indeed, as the energy is strictly convex, the solution to (1.8) is unique.

2. The worst-case complexity of the power watershed algorithm in the case p → ∞ is given by the cost of optimizing (1.7) for the given q. In the best-case scenario (all weights have unique values), the power watershed algorithm has the same asymptotic complexity as the algorithm used for a MSF computation (quasi-linear). In practical applications where the plateaus have a size less than some fixed value K, then the complexity of the power watershed algorithm matches the quasi-linear complexity of the standard watershed-cut algorithm.

Algorithm 1: Power watersheds algorithm p → ∞, q > 1 Data: A weighted graph G(V, E) comprising known labels x(B), x(F).

Result: A potential function x (solution of (1.8) thanks to Th. 25.)

while any node has an unknown label do Find a maximal subgraph S ∈ G composed of edges of maximal weight;

if S contains any nodes with known x then Find x S minimizing (1.7) for q on the subset S;

Consider all x S values produced by this operation as known;

else Merge all of the nodes in S into a single node, such that when the value of x for this merged node becomes known, all merged nodes are assigned the same value of x and considered known;

The main properties of Algorithm 1 (with q ≥ 1) are summarized in the following theorem. This theorem states that the energy found by the algorithm is the correct one, i.e. x q = x, and that furthermore, the computed cut is a MSF cut.

Theorem 25 ([15])

If q > 1, the potential x obtained by minimizing the energy of (1.7) subject to the boundary constraints converges toward the potential x obtained by Algorithm 1 as p → ∞.

Furthermore, for any q ≥ 1, the cut C defined by the segmentation s computed by Algorithm 1 is an MSF cut for w.

Applications

Minimizing exactly the energy E 1,1 is possible by using the graph cuts (i.e. q = 1) algorithm in the case of two labels, but is NP-hard if constraints impose more than two different labels. However, the other algorithms presented in the framework (and in particular the watershed cuts and the power watershed) can efficiently perform seeded segmentation with as many labels as desired [START_REF] Couprie | Power Watersheds: A Unifying Graph Based Optimization Framework[END_REF]. As several examples of segmentation have already been shown in this chapter, we rather highlight two other applications that take advantage the unique optimization characteristics of the power watershed.

The first example is shape fitting: surface reconstruction from a set of noisy point measurements has been a well studied problem over the last decades. Recently, variational [START_REF] Goldstein | Geometric applications of the Split Bregman Method: Segmentation and surface reconstruction[END_REF][START_REF] Ye | A fast variational method for surface reconstruction from sets of scattered points[END_REF] and discrete optimization [START_REF] Lempitsky | Global Optimization for Shape Fitting[END_REF] approaches have been applied to solve it, demonstrating good robustness to outliers thanks to a global energy minimization scheme. In [START_REF] Couprie | Surface reconstruction using power watershed[END_REF], Couprie et al. use the power watershed framework to derive a specific

Conclusion

We have presented in this paper some applications of mathematical morphology to weighted graphs. The translation of the abstract framework of lattices to graphs allows us to obtain morphological operators thinner (in the sense that they process smaller details) than the usual ones usually defined only on the vertices. We have shown how to filter an image using connected filters based on a tree representation of the image.

We have exhibited the links between watersheds and minimum spanning trees, allowing us to make the equivalence between hierarchical segmentation based on watershed cuts and minimum spanning trees. We conclude the chapter by exploring links between the morphological and the optimization approaches.

For practical applications, we want to stress the importance of having a framework with an open-source generic implementation of existing algorithms, not limited to the pixel framework, but also able to deal transparently with edges, or, more generally, with graphs and complexes [START_REF] Levillain | Why and How to Design a Generic and Efficient Image Processing Framework: The Case of the Milena Library[END_REF].

Figure 1 . 1 :

 11 Figure 1.1: Dilations and erosions.

4

 4

Figure 1 . 2 :

 12 Figure 1.2: Openings and closings (G is induced by the 4-adjacency relation).

Figs. 1 .

 1 Figs. 1.2b and 1.2f present the result of γ Γ 1 and φ Φ 1 for respectively the subgraph of Fig. 1.2a and the one of Fig. 1.2e. The opening γ 1 and the closing φ 1 correspond to the classical opening and closing on the vertices. The closing Γ 1 and the opening Φ 1 are the corresponding edge-version of these operators. By combination, we obtain γ Γ 1 and φ Φ 1 .

  completely surrounded by elements of G 1 whereas Φ 1/2 adds to G 2 the edges of E(G 2 ) whose two extremities belong to at least one edge in G 2 (see for instance Fig.1.2).The family G is closed under the operators presented in Definition 10.3 since they are obtained by composition of operators also satisfying this property. Furthermore, it can be deduced from the local characterization of the operators γ 1/2 , Γ 1/2 , φ 1/2 and Φ 1/2 that the family G is also closed under the operators of Definition 11.3. Hence, thanks to the properties of adjunctions recalled in the introduction of this section, the following theorem can be established.Theorem 12 (graph-openings, graph-closings,[START_REF] Cousty | Some morphological operators in graph spaces[END_REF])

  Thus α 1 and α 2 are both a closing and an erosion and β 1 and β 2 are both a dilation and an opening. This means, in particular, that α 1 and α 2 are idempotent extensive erosions and that β 1 and β 2 are idempotent anti-extensive dilations. The opening and the closing resulting from the adjunction (α 3 , β 3 ) are illustrated in Figs. 1.2d and 1.2h.

Figure 1 . 3 :

 13 Figure 1.3: Illustration of classical versus vertex-edge alternating filter (see [10]).

Figure 1 . 4 :

 14 Figure 1.4: Illustration of respectively a component tree (dashed lines), the height, the area and the volume of a component and an area filtering.

Figure 1 . 5 :

 15 Figure 1.5: (a) Original image. (b) Maxima of image (a), in white. (c) Filtered image. (d) Maxima of image (c), which correspond to the ten most significant lobes of the image (a).

Fig. 1 .

 1 Fig. 1.5 illustrates this kind of filtering. Fig. 1.5.a is an image of a cell, in which we want to extract the ten bright lobes. If we consider that the brighter a pixel is, the higher its weight, then the tree we want to process is C > V . Fig. 1.5.b shows that the image 1.5.a contains numerous maxima. Fig. 1.5.c is the filtered image obtained by a volume-based filtering, and Fig. 1.5.d shows the maxima of this filtered image.

Figure 1 . 6 :

 16 Figure 1.6: An edge-weighted graph G The edges and vertices drawn in bold are: (a), the minima of w; (b), an extension of M; (c), an MSF rooted in M. In (b), the set of dashed edges is a watershed cut of w.

1 . 6 .

 16 The weights w contain three minima (in bold in Fig.1.6a). Let us denote by S the set of dashed edges depicted in Fig. 1.6b

Figure 1 . 7 :

 17 Figure 1.7: Surface segmentation by watershed cut. (a): A mesh in black and its associated graph in gray. (b): A cut on this graph (in bold); and (c), the corresponding segmentation of the mesh. (d): Rendering of the mesh of a sculpture. (e): A watershed (in red) of a map F which behaves like the inverse of the mean curvature and, in ( f ), a watershed of a filtered version of F. The mesh shown in (d) is provided by the French Museum Center for Research.

Figure 1 . 8 :

 18 Figure 1.8: Diffusion tensor images segmentation. (a): A close-up on a cross-section of a 3D brain DTI. (b): Image representation of the markers (same cross-section as (a)), obtained from a statistical atlas, for the corpus callosum (dark gray) and for its background (light gray) (c): Segmentation of the corpus callosum by an MSF-cut for the markers. The tensors belonging to the component of the MSF which extends the marker labelled "corpus callosum" are removed from the initial DTI: thus the corresponding voxels appear black.

Figure 1 . 9 :

 19 Figure 1.9: (a): An edge-weighted graph G, the minima of w are depicted in bold. (b): A watershed cut represented by dashed edges; the watershed cut is equivalent to the graph G 0 ∈ MSF(M) represented in bold. (c,d): two bold graphs called respectively G 1 and G 2 such that T = G 0 , G 1 , G 2 is both an MSF hierarchy for and an uprooting by M 1 , M 2 (where M i is the minimum of w whose altitude is i); their associated cuts are represented by dashed edges. (e): The saliency map of the MSF hierarchy G 0 , G 1 , G 2 .

Figure 1 . 11 :

 111 Figure 1.11: Two applications of power watershed. (a-c) Shape fitting using Power Watershed [69]. (a) Reconstructed bunny. (b) A close-up on one of the ears. (c) A close-up on the set of original scanned noisy points measurements. (d-e) Filtering of a liver image by anisotropic diffusion driven by power watershed [70]. In (e) noise and small vessels are both removed from (d), leading to a result which may be used as a first step before segmentation.

Figure 1 .

 1 11(a-c) shows a surface reconstructed from noisy scanned dot sets using the power watershed algorithm.The second example deals with filtering. In[START_REF] Couprie | Anisotropic Diffusion Using Power Watersheds[END_REF], Couprie et al. reformulate the problem of anisotropic diffusion as an L 0 optimization problem, and show that power watersheds are able to optimize this energy quickly and effectively. This study paves the way for using the power watershed as a useful general-purpose minimizer in many different computer vision contexts. An example of such an L 0 optimization is presented in Fig.1.11(d-e).

  . Both (ε VE , δ EV ) and (ε EV , δ VE ) are adjunctions. 2. Operators ε VE and δ VE (resp. ε EV and δ EV ) are dual of each other. 3. Operators δ EV and δ VE are dilations. 4. Operators ε EV and ε VE are erosions.

  and if the vertex set of any component of G 2 contains the vertex set of exactly one component of G 1 . Recall that the weight of G 1 is the sum of its weight, i.e. ∑ e i j ∈E(G 1 ) w i j

Table 1 .

 1 1: The generalized scheme of

	1	Collapse to seeds Max-Flow (Graph cuts) Power watershed q = 1
	2	2 norm Voronoi	Random walker	Power watershed q = 2
	∞	1 norm Voronoi	1 norm Voronoi	Shortest Path Forest

anisotropic diffusion, 26 catchment basin, 15 closing, 8 component tree, 12 dilation, 6 duality, 7 edge, 3 erosion, 6 extension, 14 extinction, 21 filter, 8 flooding, 12 forest minimum spanning, 16 graph, 3 induced, 14 graph cuts, 23 hierarchy, 13 MSF, 19 infimum, 3 lattice, 3 complete, 3 mesh, 17 minimum spanning tree, 16 MSF, see forest, minimum spanning opening, 8 point, 3 random walker, 24 reconstruction geodesic, 13 saliency map, 21 shape fitting, 25 supremum, 3 tree component, 12 uprooting, 20 vertex, 3 watershed cut, 14 power, 24 ultrametric, 21

Other choices for the ordering are possible: for example waterfall [START_REF] Beucher | Watershed, hierarchical segmentation and waterfall algorithm[END_REF], that consists in computing a sequence of watersheds of watersheds, each step leading to a drastic reduction in the number of basins. Another interesting ordering is done by optimization [START_REF] Guigues | Scale-sets image analysis[END_REF]). Let us consider a two-term-based energy function of the form λC + D, where D is a goodness-of-fit term and C is a regularization term. Finding an optimum of this function is NP-hard in the general case. On the other hand, on a hierarchy (hence, on a watershed cut), when the goodness-of-fit term decreases with the fineness of the partitions, and, inversely, that the regularization term increases with this fineness, we can show that finding an optimum can be done in linear time, by dynamic programming. Such an optimization is an efficient way to control the flooding, that is stopped when the optimum is reached. Varying the λ parameter allows us to obtain a complete hierarchy of segmentations.

Optimization and the Power Watershed

In this section, we review the Power Watershed framework [START_REF] Couprie | Power Watersheds: A Unifying Graph Based Optimization Framework[END_REF] (see also Leo Grady's chapter, this book).

In the previous sections dealing with watershed cuts, the weights encode a dissimilarity such as a gradient.

Classicaly, in the context of segmentation and clustering applications based on optimization, the weights encode affinity such that vertices connected by an edge with high weight are considered to be strongly connected and edges with a low weight represent nearly disconnected vertices. One common choice for generating weights from image intensities is to set a Gaussian weighting such as w i j = exp(-β(∇I) 2 ), (1.6) Index adjunction, 6