Fernand Meyer

Adjunctions on the lattice of dendrograms and hierarchies

Morphological image processing uses two types of trees. The min-tree represents the relations between the regional minima and the various lakes during ‡ooding. As the level of ‡ooding increases in the various lakes, the ‡ooded domain becomes larger.

A second type of tree is used in segmentation and is mainly associated to the watershed transform. The watershed of a topographic surface constitutes a partition of its support. If the relief is ‡ooded, then for increasing levels of ‡oodings, catchment basins merge. The relation of the catchment basins during ‡ooding also obeys a tree structure.

We start by an axiomatic de…nition of each type of tree, min and max tree being governed by a single axiom ; for nested catchment basins, a second axiom is required.

There is a one to one correspondance between the trees and an ultrametric half distance, as soon one introduces a total order compatible with the inclusion.

Hierarchies obey a complete lattice structure, on which several adjunctions are de…ned, leading to the construction of morphological …lters.

Hierarchies are particular useful for interactive image segmentation, as they constitute a compact representation of all contours of the image, structured in a way that interesting contours are easily extracted.

The last part extends the classical connections and partial connections to the multiscale case and introduces taxonomies.

Introduction

Hierarchies are the classical structure for representing a taxinomy. The most famous taxonomy, the Linnaean system classi…ed nature within a nested hierarchy, starting with three kingdoms. Kingdoms were divided into Classes and they, in turn, into Orders, which were divided into Genera (singular: genus), which were divided into Species (singular: species). Below the rank of species he sometimes recognized taxa of a lower (unnamed) rank (for plants these are now called "varieties").

Hierarchies are also useful in the domain of image processing. In the …eld of mathematical morphology, two basic hierarchies appear. The …rst is the mintree structuring the successive lakes of a ‡ooding and its dual counterpart, the max-tree. It has been introduces by Ph.Salembier [START_REF] Salembier | Connected operators based on region-tree pruning[END_REF] as a useful condensation of information and support of powerful image …ltering methods, based on the pruning of branches of this tree. During ‡ooding, lakes grow and merge ; the ‡ooded area also becomes larger, but does not necessarily occupy the whole domain.

Hierarchies are also at the core of hierarchical segmentation, as they represent in a condensed way nested partitions obtained through image segmentation. Hierarchies appear quite naturally in the …eld of morphological segmentation, which uses as tool the watershed of gradient images. As a matter of fact, the catchment basins of a topographic surface form a partition. If a basin is ‡ooded and does not contain a regional minimum anymore, it is absorbed by a neighboring basin and vanishes from the segmentation. A hierarchy is hence obtained by considering the catchment basins associated to increasing degrees of ‡ooding, producing for each particular ‡ooding a partition. For increasing ‡oodings, the partitions become coarser and are nested. They structure the image into a multiscale representation ; the nested partitions permit to weight the contours : the importance of a contour being measured by the level of the hierarchy where it disappears [START_REF] Meyer | An overview of morphological segmentation[END_REF].

Both types of tree share a common structure, that of a tree. However they di¤er by their support : successive lakes while ‡ooding a relief do not cover the complete domain of the relief ; furthermore the covered area increases as the lakes grow higher. On the other hand, the catchment basins of this same relief associated to the successive ‡oodings all partition the domain of the relief. In the …rst case, we speak of dendrogram or partial hierarchy, in the second case of hierarchy or covering hierarchy.

Often one is not interested in partitioning the total domain of the image, but one wants to get the masks of some objects of interest. These masks are disjoint sets but do not partition the domain ; they constitute a partial partition as introduced by Ch. Ronse [START_REF] Ronse | Partial partitions, partial connections and connective segmentation[END_REF]. The paper is organized as follows.

The …rst part starts with the axiomatic de…nition of trees, dendrograms and hierarchies due to Benzecri [START_REF] Benzécri | L'analyse des données 1. La taxinomie[END_REF]. Dendrograms are based solely on the intersection axiom and correctly model min and max-trees. Hierarchies are obtained by adding a second axiom, the union axiom.

We show in this paper, that this second axiom very often is not necessary and that most useful properties derive from the intersection axiom alone. Adding the union axiom obliges …lling the empty spaces left by an operator like an erosion applied to a hierarchy ; in contrast, the intersection axiom alone allows an automatic adjustment of the support during the erosion.

Dendrograms may be further structured by adding a complete preorder relation, compatible with inclusion order, called strati…cation level. Strati…ed hierarchies are the basis of taxonomy. A partial ultrametric distance is then associated to each couple (dendrogram, strati…cation).

A third part establishes that partial hierarchies form a complete lattice.

The fourth part de…nes two adjunctions on partial hierarchies. The …rst extends the adjunction de…ned by J.Serra for partitions [START_REF] Serra | Morphological operators for the segmentation of colour images[END_REF], where each tile of a partition is eroded and dilated separately, empty spaces being …lled with singletons. Ch. Ronse described the adjoint dilation [START_REF] Ronse | Reconstructing masks from markers in non-distributive lattices[END_REF] and also adapted this de…nition to partial partitions, where the empty spaces are kept outside of the support of the result [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF]. We extend the adjunction de…ned by J.Serra and Ch. Ronse to partial hierarchies. As the support of partial hierarchies and dendrograms may vary, the de…nition of erosions and dilations is easier on a dendrogram as on a hierarchy.

We also de…ne a second adjunction which directly relies on the complete lattice structure of PUHD. The supremum of translated PUHD yields the erosion by a structuring element equal to the set of translations ; the in…mum of translated PUHD yields the dilation. This second adjunction is …ner than the …rst.

In a …fth part, we show how some interactive segmentation tools may be derived from a hierarchy.

The last part of the document extends the connections de…ned for partitions to hierarchies and de…nes taxonomies. The algebraic structure of partitions has been studies by Serra, Heijmans, Ronse ([3], [START_REF] Serra | A lattice approach to image segmentation[END_REF], [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF]). The same set may be partitioned into distinct partitions according the type of connectivity one adopts. Serra has laid down the adequate framework for extending the topological notion of connectivity by de…ning connective classes later called connections ( [START_REF] Serra | Image Analysis and Mathematical Morphology. II: Theoretical Advances[END_REF], [START_REF] Serra | A lattice approach to image segmentation[END_REF]). Taxonomies, like connections are generated by the union of sets with a non empty intersection ; a taxonomy class possesses an strati…cation index, which can be interpreted as the diameter for an ultrametric distance. The diameter of a family of sets with an empty intersection being the largest diameter of a set in the family. Connected classes are then simply the sets with diameter 0 for a binary ultrametric distance.

Dendrograms

The axiomatic de…nition of dendrograms and hierarchies is due to Benzecri [START_REF] Benzécri | L'analyse des données 1. La taxinomie[END_REF]. It entirely relies on set intersection or union and on the inclusion order relation between sets. The construction is very progressive : starting with the inclusion order relation alone and adding axioms in order to successively de…ne trees, hierarchies and …nally strati…ed hierarchies.

The structure associated to an order relation

Let E be a domain whose elements are called points. Let X be a subset of P(E), on which we consider an arbitrary order or preorder relation relation (the inclusion between sets is an example, but what follows is valid for any preorder relation). The union of all sets belonging to X is called support of X : supp(X ): The subsets of X may be structured into: the summits : Sum(X ) = fA 2 X j 8B 2 X : A B ) A = Bg the leaves : Leav(X ) = fA 2 X j 8B 2 X : B A ) A = Bg the nodes : Nod(X ) = X Leav(X ) the predecessors : Pred(A) = fB 2 X j A Bg the immediate predecessors : ImPred(A) = fB 2 X j fU j U 2 X ; A U and U Bg = (A; B)g the successors : Succ(A) = fB 2 X j B Ag the immediate successors : ImSucc(A) = fB 2 X j fU j U 2 X ; B U and U Ag = (A; B)g

The leaves are disjoint sets ; so are also the summits. The summits of X constitute a partition of supp(X ). This is not necessarily the case of the leaves : a set B A may be a leave, but the remaining points of A do not necessarily belong to a leave. It will only be the case if the union axiom is satis…ed, yielding covering hierarchies (see below).

The leaves are successors of the summits and local minima ; the summits are predecessors of the leaves and local maxima. The name predecessor and successor supposes that one explores the …liations between nodes in a direction going from the summits to the leaves, from coarse to …ne.

Dendrograms

We now structure X as a tree or a dendrogram. We also use "partial hierarchy" as an alternative name for dendrogram.

Dendrograms : X is a dendrogram if and only if the set Pred(A) of the predecessors of A; with the order relation induced by is a total order. The maximal element of this family is a summit, which is the unique summit containing A:

There exist several equivalent characterization of dendrograms which are instructive.

Nota bene: From now on we take as preorder relation on P(E) the ordinary inclusion between sets.

Proposition 1

The following properties are equivalent:

1)X is a dendrogram 2) U; V; A 2 X : A U and A V ) U V or V U 3) U; V 2 X : U " V and V " U ) U \ V = ? Proof. 1) ) 2) : Suppose that X is a dendrogram, i.e. for all A 2 X : Pred(A) is completely ordered for U; V; A 2 X : A U and A V means that U 2 Pred(A) and V 2 Pred(A) and since Pred(A) is completely ordered for ; we have U V or V U 2) ) 3) : Suppose now that U; V; A 2 X : A U and A V ) U V or V U:
This implication is equivalent with the following where each predicate has been negated: U; V 2 X : U " V and V " U ) @A 2 X : A U and A V But this last predicate implies that U \ V which is included both in U and in V is empty :

U \ V = ? 3) ) 2) : Suppose that U; V 2 X : U " V and V " U ) U \ V = ? ; inverting the predicates yields the equivalent implication U \ V 6 = ? ) U V or V U: But then if there exists A such that A U and A V; it means that U \ V 6 = ? implying U V or V U 2) ) 1) : Suppose now that U; V; A 2 X : A U and A V ) U V or V U: Consider a set A and two sets U; V 2 Pred(A): This means that A U and A V; implying that U V or V U; showing that Pred(A) is indeed well ordered.
Proposition 2 A family (A i ) i2I of sets in X with a non empty intersection is completely ordered for :

Proof.

Suppose that there exists a set U included in each A i : We may then apply the criterion 2 characterizing dendrograms to any couple A j ; A k showing that A j A k or A k A j and that the family (A i ) i2I is completely ordered for :

Consider now a point p belonging to supp(X ); i.e. there exists a set A 2 X such that p 2 A: The set fpg is included in the family of all sets of X containing p: This family is thus completely ordered for and contains a smallest element, which we call home(p). We call Pred(p) the set of predecessors of home(p) : Pred(p) = Pred(home(p))

Representation of a dendrogram as a tree

In the case where X is …nite, then X is a dendrogram if and only if any element A 2 X Sum(X ) possesses a unique immediate predecessor.

A dendrogram is said to be connected if it possesses a unique summit : Card Sum(X ) = 1

Finite dendrograms are classically represented as a tree : each element A 2 X is a node of the tree, and is linked by an edge with its unique immediate predecessor.

Consider the topographic surface represented in …g.1, ‡ooded by a ‡ood of uniform altitude. As the altitude increases, lakes appear at the position of the regional minima and progressively …ll the catchment basins. When the lowest pass point of a catchment basin is reached, two neighboring lakes merge, forming a new lake. The mintree [START_REF] Salembier | Connected operators based on region-tree pruning[END_REF] represents the evolution of the lakes during ‡ooding. Each lake is represented as a node : the leaves are the lakes as they appear at the location of the regional minima and are represented as red dots. The lakes created by merging of two preexisting lakes are represented as blue dots. Finally, the unique lake which covers everything is the root of the tree Figure 1: Left : the mintree of a topographic surface. The horizontal mosaic image at the bottom represents the extension of the catchment basins of the relief. Right : A hierarchy associated to the mintree : each node of the mintree is replaced on the catchment basins of the relief associated to all successors of this node. The altitude of each region represents one possible strati…cation of this hierarchy Figure 2: Partial hierarchy of the critical lakes, i.e. the lakes appearing at the minima or the lakes which immediately resulted from the fusion of two smaller lakes.

and is represented as a green dot. Each node, except the summit is linked by an edge with its unique predecessor, the lake formed by merging with another lake. The catchment basins of the relief are represented as coloured mosaic at the bottom of the relief.

We may now associate two distinct families of sets belonging to P(E): The …rst one is represented in the right part of …gure 1, where each node has been replaced by the union of catchment basins which cut the corresponding minimum or lake. In this case, as one goes down the hierarchy, the regions split but constitute a partition of the domain. The second is represented in …g.2, where each node is replaced by the regional minimum or the lake created at this node. In this second case, as one goes down the hierarchy, the domain covered by the lakes or the minima becomes smaller and smaller. In the binary case, there are only one level : disjoint sets cover the domain E; and constitute a partition. Alternatively, they are disjoint but without covering E; then they constitute a partial partition.

Partitions and partial partitions

Consider a dendrogram

verifying : A 2 supp( ) ) Pred(A) = A: Such a dendrogram is called partial partition (partial partitions have been introduced by Ch. Ronse in [START_REF] Ronse | Partial partitions, partial connections and connective segmentation[END_REF]). If supp( ) = E; then it is called partition.

Let U; V 2 and U 6 = V . As Pred(U ) = U and Pred(V ) = V we necessarily have U " V and V " U , implying according criterion 3 of dendrograms that U \ V = ?:

Inversely consider a subset of P(E) such that any two sets U; V 2 verify U = V or U \V = ?: Consider now two sets A; B2 such that B 2 Pred(A): As A B; we have A \ B 6 = ?; leaving as only possibility A = B; showing that Pred(A) = A:

Strati…cation indices and ultrametric half distances

The collection of regions depicted in red in the right part of …g.1 obviously represents a dendrogram: the region at each node is included in all its predecessors. This partial order relation governs the hierarchical structure of the tree. This inclusion order can be made more precise, by the adjunction of a total order compatible with it. Such a …ner partial order between the regions has been introduced in …g.1, where each catchment basin is represented at the altitude of the ‡ooding for which this catchment basin appears for the …rst time. If a catchment basin is included in another, the its altitude where the …rst appears is smaller than the altitude where it gets absorbed by the second. For this reason, we say that the altitude constitutes a total order between the catchment basins compatible with the partial inclusion order. We call it a strati…cation index of the hierarchy. All nodes with the same altitude represent a strati…cation level of the hierarchy. Let us de…ne precisely what we mean by strati…cation index.

Strati…cation index

X is a strati…ed dendrogram (or partial hierarchy), if it is equipped with an index function st from X into the interval [0; L] of R which is strictly increasing with the inclusion order: 8A; B 2 X : A B and B 6 = A ) st(A) < st(B): It will be useful to set st(?) = L: We suppose that for all A 2 X : st(A) < L:

There are many strati…cation indices compatible with a given hierarchy. Fig. 3 presents two strati…cation indices compatible with the same dendrogram: On the left, we consider the watershed segmentation if one takes as marker the minima, ordered by their altitude. The coarsest level covers the domain. The next level is associated to the two lowest minima taken as markers. The successing levels progressively introduce more minima until all minima are used as markers, cyielding the …nest segmentation. On the right, the coarsest and …nest segmentations are the same, in between we consider a ‡ooding with uniform and growing altitude over the domain E: As lakes merge, cachment basins also merge.

This example shows two radically di¤erent strati…cation indices, that is total order, compatible with the partial order induced by inclusionf of sets expressed by the dendrogram.

Extremal strati…cation indices

Among all possible strati…cation indices compatible with a hierarchy, there exist two extremal strati…cation indices.

The largest strati…cation index assigns the maximal value L to the summits and decreases as one goes down to the successors. The smallest strati…cation level assigs 0 to alll leaves and increases as one goes up along the predecessors of the leaves.

If the hierarchy X is …nite, the maximal and minimal strati…cation levels may be computed as follows.

Maximal strati…cation :

st(summits) = L 8A 2 X : st(A) = st(ImPred(A)) 1
Minimal strati…cation :

st(Leaves) = 0 8A 2 X : st(A) = st(ImSucc(A)) + 1
Any linear combination between the maximal and minimal strati…cation is still a valid strati…cation. On the left, we consider the watershed segmentation if one takes as marker the minima, ordered by their altitude. The coarsest level covers the domain. The next level is associated to the two lowest minima taken as markers. The successing levels progressively introduce more minima until all minima are used as markers, cyielding the …nest segmentation. On the right, the coarsest and …nest segmentations are the same. Here we consider a ‡ooding with uniform and growing altitude over the domain E: As lakes merge, cachment basins also merge. The order of merging is however quite di¤erent from the left …gure.

A partial ultrametric distance associated to each dendrogram

De…nition 3 is a partial ultrametric distance as: 8p; q 2 E : (p; q) = (q; p) 8p; q; r 2 E : (p; q) max f (p; r); (r; q)g Proposition 4 Each dendrogram X with a strati…cation index st induces on the points of E a partial ultrametric distance de…ned as follows:

for p; q 2 E; p = 2 supp(X ) : (p; p) = L and (p; q) = L for p; q = 2 supp(X ) : if no set of X contains both p and q; then (p; q) = L:

for p; q 2 supp(X ) : let A be a set of X containing both p and q: Thus the family (A i ) i2I of sets of X containing both p and q is not empty and has a non empty intersection ; as established above is completely ordered for and possesse a smallest element. The distance (p; q) is the strati…cation level of the smallest set in this family.

Proof. Let us prove that indeed is a partial ultrametric distance.

The symmetry is obvious.

Let us establish the ultrametric inequality (p; q) max f (p; r); (r; q)g : a) if r = 2 supp(X ); then (p; r) = (r; q) = L and the ultrametric inequality holds b) p or q does not belong to supp(X ), say p : then (p; q) = (p; r) = L and the ultrametric inequality holds c) p; q; r 2 supp(X ) :

(p; r) is the strati…cation index of a set A 1 2 X containing p and r: Hence A 1 2 Pred(r) Similarly (r; q) is the strati…cation index of a set A 2 2 X containing q and r and belongs to Pred(r): But Pred(r) is well ordered for ; hence

A 1 A 2 or A 2 A 1 Suppose A 1 A 2 : then A 2
is the smallest set of Pred(r) containing r and q; but also contains p: Hence (p; q) (r; q) = st(A 2 ) since (p; q) is the strati…cation index of the smallest set of X containing both p and q:

This last inequality is called ultrametric inequality, it is stronger than the triangular inequality.

De…nition 5 For p 2 E the closed ball of centre p and radius is de…ned by Ball(p; ) = fq 2 E j (p; q)

g : The open ball of centre p and radius is de…ned by Ball(p; ) = fq 2 E j (p; q) < g :

Remark 6
Every triangle in a domain where an ultrametric distance is de…ned is isosceles. Let us consider three distinct points p; q; r and suppose that the largest edge of this triangle is pq: Then d(p; q) d(p; r) _ d(r; q); showing that the two larges edges of the triangle have the same length.

Properties of the balls of a partial ultrametric distance

Lemma 7 Each element of a closed ball Ball(p; ) is centre of this ball Proof. Suppose that q is an element of Ball(p; ). Let us show that then q also is centre of this ball. If r 2 Ball(p; ) : (q; r) max f (q; p); (p; r)g = ; hence r 2 Ball(q; ); showing that Ball(p; ) Ball(q; ): Exchanging the roles of p and q shows that Ball(p; ) = Ball(q; ) Lemma 8 Two closed balls Ball(p; ) and Ball(q; ) with the same radius are either disjoint or identical.

Proof. If Ball(p; ) and Ball(q; ) are not disjoint, then they contain at least one common point r: According to the preceding lemma, r is then centre of both balls Ball(p; ) and Ball(q; ), showing that they are identical.

Lemma 9

The radius of a ball is equal to its diameter.

Proof. Let Ball(p; ) be a ball of diameter ; that is the maximal distance between two elements of the ball is . Thus : Let q and r be two extremities of a diameter in Ball(p; ) : = (q; r) (q; p) _ (p; r) = : Hence = :

Remark 10 Instead of closed balls, we could have taken open balls. The results are the same.

Typology of the points of E

Partial hierarchy A strati…ed dendrogram X structures the domain E into various categories of points : -a point p is an alien if p = 2 supp(X ); for such a point that (p; p) = L -a point p is a singleton if p 2 supp(X ) and home(p) = fpg ; for such a point : (p; p) < (p; q) for q 6 = p -all other points of supp(X ) are regular points of X Due to the ultrametric inequality, we also have (p; p) (p; q) _ (q; p) = (p; q): Hence (p; p) V q6 =p (p; q): Partial partitions We de…ne aliens and singletons of a partial partition :

Singletons are characterized by: 8p; q 2 E ; p 6 = q; : (p; q) = 1 and (p; p) = 0:

Aliens are characterized by: 8p 2 E : (p; p) = 1 implying 8p; q 2 E : (p; q) = 1 the support of is the set of points p verifying : (p; p) = 0

Inversely: a dendrogram associated to each partial ultrametric distance

Consider now a partial ultrametric distance :

Proposition 11 The closed balls of a partial ultrametric distance form a dendrogram X

Proof.

We have to show that for any set A belonging to X , Pred(A) is well ordered for : Consider two sets B 1 = Ball(p; ) and B 2 = Ball(q; ) containing both A: We have to show that they are comparable for : Let r be a point of A. This point belongs to both Ball(p; ) and Ball(q; ); hence it is centre of each of these balls : Ball(p; ) = Ball(r; ) and Ball(q; ) = Ball(r; ): If = ; then Ball(p; ) and Ball(q; ) are identical. If < ; then Ball(p; ) = Ball(q; ). This establishes that Pred(A) is well ordered for Proposition 12 We have a one to one correspondance between partial ultrametric distances and strati…ed dendrograms X

Partial partitions

Consider a dendrogram

verifying : A 2 supp( ) ) Pred(A) = A: Let us verify that such a dendrogram is a partial partition, as they have been called by Ch. Ronse in [START_REF] Ronse | Partial partitions, partial connections and connective segmentation[END_REF].

Its partial ultrametric distance is now a binary, taking its values in f0; 1g : It veri…es (pp1) : for p; q; r 2 supp( ) : (p; q) = (q; p) (q; r) _ (r; p) : symmetry and ultrametric inequality (pp2) for p = 2 supp( ); 8q 2 E : (p; q) = 1

This last relation is also true for p itself : for p = 2 supp( ) : (p; p) = 1 The domain supp( ) = fp 2 E : (p; p) = 0g is called support of the partial partition. If this domain equals E; then is a partition. Otherwise is a partial partition.

Consider now a point p = 2 supp( ): We call such points "aliens". For any q 2 E; we have 1 = (p; p) (p; q) _ (q; p) = (p; q); showing that the ultrametric distance between an alien and any other point is 1:

Remark 13 Aliens should not be mixed up with the singletons, which duly belong to the support. The singleton fxg is a set of P(E) reduced to the point x: Singletons are characterized by: 8q 2 E ; p 6 = q; : (p; q) = 1 and (p; p) = 0:

We call cl(p) the closed ball of centre p and of radius 0 associated to : Relation (pp2) implies that for p = 2 supp( ) the class cl(p) is empty. Consider now p; q 2 E such that q 2 cl(p). This shows that p; q 2 supp( ) and (p; q) = 0: If r 2 cl(p); then (p; r) = 0 and (q; r) (q; p) _ (p; r) = 0 showing that r 2 cl(q): Similarly r 2 cl(q) ) r 2 cl(p):

Hence for any p; q 2 E ; q 2 cl(p) ) cl(q) = cl(p): But these are precisely the criteria given by Ch. Ronse for de…ning partial partitions:

(P1b) for any p 2 E ; cl(p) = ? or p 2 cl(p) (P2a) for any p; q 2 E ; q 2 cl(p) ) cl(q) = cl(p)

Partial equivalence relations

Associated to ; we may de…ne a partial equivalence relation de…ned by p R q , (p; q) = 0; which is symmetric and transitive but not re ‡exive. The support of a partial equivalence relation R is precisely supp( ) ; it also is the set of all points p 2 E for which there exists a point q 2 E verifying p R q. Ch. Ronse introduced this partial equivalence in [START_REF] Ronse | Partial partitions, partial connections and connective segmentation[END_REF].

Order relation between hierarchies and partial hierarchies

Let A and B be two dendrograms with their associated PUD : A and B : The following relation de…nes an order relation between the hierarchies: B A , 8p; q 2 E A (p; q) B (p; q)

It follows that 8p 2 E : Ball B (p; ) Ball A (p; ): We say that the hierarchy A is coarser than the hierarchy B and that the hierarchy B is …ner than the hierarchy B.

For each p = 2 supp(A) : A (p; p) = L which implies that B (p; p) = L; indicating that supp(A) supp(B); or equivalently supp(B) supp(A)

The smallest partial hierarchy has an empty support and contains only aliens, i.e. points p verifying 8q 2 E ; (p; q) = L: The largest hierarchy is E itself, whose PUD veri…es: 8p; q 2 E : (p; q) = 0:

In the case where there are no aliens, that is supp(A) = E; then the largest hierarchy veri…es (p; q) = L for p 6 = q; and (p; p) < L: It contains only singletons. If the strati…cation index of the singletons is 0 then (p; p) = 0:

To binary PUDs A and B correspond partitions and partial partitions. Their closed balls verify : Ball B (p; 0) Ball A (p; 0); the aliens remaining outside the balls. Hence the tiles of the …ner partition B are included in the tiles of the coarser partition A which is coherent with the usual de…nition of the order between partitions.

Partial partitions by thresholding partial hierarchies

Summary : Increasing thresholds of a partial hierarchy produce increasing partial partitions. Inversely to a series of increasing partial partitions may be associated partial hierarchies which di¤er only by their strati…cation index.

Decomposition into partial partitions of a partial hierarchy Consider a partial hierarchy X with its associated PUD : By thresholding the PUD at level one obtains a partial binary ultrametric half distance (PBUD):

(x; y) = 1 if (x; y) > 0 if (x; y)
associated to a partial partition :

For increasing thresholds ; the series of PUD is decreasing and the associated partial partitions increasing, i.e. coarser:

) ) It is easy to verify that if is a PUD, then each also is a PUD. Let us check the ultrametric inequality.

For p; q; r 2 E : (p; r) (p; q) _ (q; r):

If (p; r) ; then (p; r) = 0 (p; q) _ (q; r) If (p; r) > ; then
(p; r) = 1 and (p; q) _ (q; r) > ; implying that (p; q) > or (q; r) > ; hence (p; q) = 1 or (q; r) = 1

Reconstructing a hierarchy from nested partial partitions

Inversely, to a family ( i ) i2I of increasing partial partitions may be associated a series of partial hierarchies sharing the same undelying dendrogram but with strati…cation indices which di¤er one from each other by an increasing anamorphosis. Let i the PUD associated to i :

If is an increasing anamorphosis, the partial hierarchy associated to ( i ) i2I and has for PUD : = P (i) i .

Aliens and singletons

Both aliens and singletons play a particular role in the half distance, as they play no role in the the ultrametric inequality. The relation : p; q 2 E : (p; q) (p; p) _ (p; q) is true for any value of (p; p) On the other hand, the distance between an alien and any other of its neighbors is at least as high that its own strati…cation index. For any q 2 E; we have = (p; p) (p; q) _ (q; p) = (p; q); showing that the ultrametric distance between p and any other point is larger than or equal to :

Partial hierarchies

Consider now a hierarchy X with its PUD and its thresholds at level : We de…ne its open and closed supports at level :

Its open support at level is supp ( ) = fp j (p; p) < g and its closed support supp ( ) = fp j (p; p) g : For increasing values of ; the partial partitions obtained by thresholding have increasing supports supp ( ) = fp 2 E : (p; p) g : This means that a point p may be outside the support of partition and inside the support of partition for > : Similarly, as the partitions become coarser for increasing ; a point p may be a singleton up to level and not a singleton anymore for higher levels. Let us analyse more precisely this behaviour.

Let p 2 E be a point verifying (p; p) = and the partition obtained by thresholding at the level : And consider = V q6 =p (p; q): Since (p; p) (p; q) _ (q; p); we have : We are now to analyse the role played by p in the partition for increasing values of : case 1: < : (p; p) = 1 and p is an alien case 2: < : (p; p) = 0 but for q 6 = p; (p; q) = 1 and p is a singleton case 3:

: (p; p) = 0 and there exists q 6 = p such that (p; q) = 0 showing that p is a regular node and not a singleton.

Particular cases

a "forever singleton" is a singleton for all : It is characterized by p 2 E : (p; p) = 0 and 8q 2 E ; p 6 = q : (p; q) = L: In this case = 0 and = L a "singleton from on" is a singleton for all for : It is characterized by p 2 E : (p; p) = and 8q 2 E ; p 6 = q : (p; q) = L:

In this case = L a "never singleton" : if (p; p) = V q6 =p
(p; q); then case 2 does not happen and p is never a singleton a "never alien" is characterised by p 2 E : (p; p) = 0 a "forever alien" is an alien for all : It is characterized by p 2 E : (p; p) = L: In this case = = L 6 Pruning of dendrograms Consider now a grain opening and a dendrogram X : A grain opening applied on a set A takes it or leaves it : (A) 2 fA; ?g

As any opening, is anti-extensive, increasing and idempotent.

Proposition 14 If we apply to each A 2 X we obtain a family (A) which again is a dendrogram written (X ).

Proof.

Consider a set B 2 (X ): There exists a set A 2 X such that B = (A): As X is a dendrogram, Pred(A) is completely ordered for : As is anti-extensive and increasing, Pred( A) is obtained by applying to each set X belonging to Pred(A) yielding (X) = X: Hence Pred( A) also is completely ordered for :

See [START_REF] Salembier | Connected operators based on region-tree pruning[END_REF] for an overview of the various pruning strategies of mintrees.

7 Partitions and Hierarchies

Partitions and partial partitions

All partial partitions and partitions verify the union axiom.

Proposition 17 Partial partitions are hierachies.

Proof.

A partial partition has been de…ned as a dendrogram for which each A 2 veri…es Pred(A) = fAg : But then each A 2 is a leave and the support of is the union of the leaves of : If furthermore supp( ) = E; then the partial partition becomes a partition. Hierarchies which verify supp(H) = E are called covering hierarchies, since each point of E belongs to a leave of H:

Covering hierarchies

Consider a covering hierarchy H with a strati…cation index st and the derived partial ultrametric distance :

Let supp(H) = E; then for all p 2 E : (p; p) < L If furthermore we impose that the strati…cation index of all leaves is equal to 0; then for all p 2 E : (p; p) = 0: In such a situation is a half distance, as de-…ned by L. Schwartz in [START_REF] Schwartz | Analyse : topologie générale et analyse fonctionnelle, chapter 3[END_REF]. His de…nition of half-distances and half-metric spaces is given below. Furthermore the open support supp ( ) = fp j (p; p) < g and closed support supp ( ) = fp j (p; p) g are invariant with and are equal to supp(H): A half metric space is then a topological space de…ned as follows : a subset O of E is open, if for each point x 2 O; there exists a half ball B i (x; R) centered at x; with a positive radius entirely contained in O.

Half distances and half metric spaces

If the triangular inequality is replaced by the ultrametric inequality, we call it ultrametric half-distance or ultrametric ecart. To any hierarchy X de…ned on subsets of P(E) is thus associated an ultrametric half-distance or ultrametric ecart.

Exchanging aliens and singletons

Singletons play a particular role in the work of J.Serra and Ch. Ronse on partitions and partial partitions. For instances, for eroding a partition, J.Serra proposes to erode each tile separately and to …ll the empty spaces with singletons [START_REF] Serra | Morphological operators for the segmentation of colour images[END_REF]. Ch. Ronse proposes an operator RS, removing the singletons and transforming a partition into a partial partition [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF]. The same operation becomes simpler by using aliens : singletons are simply turned into aliens.

In this section we de…ne two operators exchanging aliens and singletons in dendrograms. These operators form an adjunction. Let and be the PUD of two dendrograms (partial hierarchies) Z and X . 7.5.1 An operator s2a transforming all singletons of Z into "never singletons"

We de…ne an operator s2a which transforms all singletons of Z into "never singletons". The PUD of s2a(Z) is de…ned by: For

p 2 E; s2a (p; p) = V q6 =p (p; q) =
For p; q 2 E; p 6 = q : s2a (p; q) = (p; q) For any threshold < of s2a (p; p); we get a partial partition for which p is an alien, i.e is outside the support. And for any threshold ; p in incorporated in the support without becoming a singleton, since it belongs to a region with at least two points.

It is easy to check that if is a PUD, then s2a still is a PUD. As a matter of fact, and s2a di¤er only on the singletons and aliens, which, following the remark made earlier, play no role in the propagation of the half distances through the ultrametric inequality.

Remark 20 In the binary case, if p is a singleton, for p 6 = q : (p; q) = 1 and s2a (p; p); showing that p becomes an alien and exits the support.

An operator a2s transforming all aliens of X into "never aliens"

The operator a2s simply transforms all aliens of X into "never aliens" by doing: for p 2 E : a2s (p; p) = 0: Obviously the operator a2s transforms a partial hierarchy into a covering hierarchy, by adding singletons outside its support.

The following lemma is the counterpart of Lemma8.2 in [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF].

Lemma 21 If X is a hierarchy and X 0 a partial hierarchy and , 0 their associated PUDs, then a2s X 0 X ) X 0 X Proof. We suppose a2s X 0 X , i.e. a2s 0 : But a2s 0 0 ; after transforming the aliens into "never aliens". Hence a2s 0 0 ) X 0 X

The operators a2s and s2a form an adjunction

We have to prove that for any pair and of PUDs, we have : a2s , s2a : The operator s2a is then an erosion on the PUDs and a dilation on the corresponding partial hierarchy. And the operator a2s is then a dilation on the PUD and an erosion on the corresponding partial hierarchy. Proof. We …rst consider the case p; q 2 E; p 6 = q : a2s (p; q) = (p; q) and (p; q) = s2a (p; q) Hence a2s (p; q) (p; q) , (p; q) s2a (p; q) Consider now the pair (p; p) :

1) Suppose a2s s2a (p; p) = V q6 =p (p; q) but a2s hence s2a (p; p) = V q6 =p (p; q) V q6 =p a2s (p; q)
And for p; q 2 E; p 6 = q : a2s (p; q) = (p; q) hence V

q6 =p a2s (p; q) = V q6 =p (p; q)
(p; p) the last inequality deriving from the ultrametric inequality (p; p)

(p; q) _ (q; p) Hence s2a (p; p) = V q6 =p (p; q) V q6 =p a2s (p; q) = V q6 =p (p; q) (p; p)
2) Suppose s2a For all p 2 E : a2s (p; p) = 0 and (p; p) 0; hence a2s (p; p) (p; p) Finally we have proved that a2s ( s2a

Discussion

The couple (s2a; a2s) is an adjunction on the PUDs, (a2s; s2a) on the corresponding partial hierarchies. The operator s2a is an erosion on the PUDs and a dilation on the corresponding partial hierarchies. And the operator a2s is then a dilation on the PUD and an erosion on the corresponding partial hierarchies. This last erosion transforms any partial hierarchy into a hierarchy.

In the binary case, where the PUD take only values 0 and 1; we get the operators already introduced by Ch. Ronse in [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF]. The operator s2a transforms all singletons into aliens, in other words it removes all singleton blocks from the partial partition. Hence it is identical with the operator RS introduced by Ch. Ronse in [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF]. Similarly the operator a2s …lls a partial partition by singleton blocks outside its support, hence it is identical with the operator F S in [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF].

Theorem 9 in [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF] establishes a number of properties of F S and RS: As we take s2a and a2s as operators between partial hierarchies, we do not have to consider the operator IN and the results become simpler.

Here are some properties which are equivalent with properties of theorem 9; transposed in our framework. the operator a2s is increasing and anti-extensive on PUD : it is an opening on PUDs and a closing on the corresponding partial hierarchies. the operator s2a is increasing and extensive on PUD : it is a closing on PUDs and an opening on the corresponding partial hierarchies. a2s(s2a) = a2s , showing again that a2s is an opening and s2a(a2s) = s2a is a closing on PUD.

An adjunction based on aliens and singletons of high rank

In some cases, one wants to apply the preceding operators only to singletons and aliens with a strati…cation level higher than a given value :

The operator s2a is de…ned by : for p; q 2 E; s2a (p; p) = V q6 =p (p; q) if (p; p) and s2a (p; p) = (p; p) otherwise. This operator transforms only singletons with a strati…cation level higher than into "never singletons".

The operator a2s is de…ned by : for p; q 2 E; a2s (p; p) = (p; p) ^ : It transforms aliens with a strati…cation level higher than into "never aliens above ".

The couple (s2a ; a2s ) also is an adjunction on the PUDs.

The blending and grinding operators

In this section, we extend to partial hierarchies the blending and grinding operators presented by Ch. Ronse p.358-360 of [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF] 7.6.1 The identity hierarchy of A and the universal hierarchy of A:

For A 2 P(E); we de…ne the identity hierarchy of A (we write 0 F (A)) through its PUHD 0 A by the following relations :

for p 2 A : 0 A (p; p) = for p = 2 A : 0 A (p; p) = L for p 6 = q 2 E : 0 A (p; q) = L
Interpretation of the partial hierarchy 0 F (A) :

Inside A : up to level ; 0 F (A) has only aliens and above only singletons.

Outside A; it has aliens at all levels.

In the binary case, = 0 and L = 1 and 0 A is identical with 0 A de…ned by Ch. Ronse p.354, which partitions A into its singletons, and …lls the complement of A with aliens.

For A 2 P(E); we de…ne the universal hierarchy of A (we write 1 F (A)) through its PUHD 1 A by the following relations :

for p; q 2 A : 1 A (p; q) = 0 for p = 2 A or q = 2 A : 1 A (p; q) =
Interpretation: For all levels up to ; the partial hierarchy 1 F (A) has one block identical with A and aliens outside A: For the levels above ; it has one block identical with E. In the binary case, = 1 and 1 F (A) is identical with 1 A de…ned by Ch. Ronse p.354, representing a partial partition with only one block equal to A:

We now consider two mappings from P(E) into the PUHDs of partial hierarchies :

1 F : A 1 A 0 F : A 0 A Notation: We write 1 F (A) (resp. 0 F (A))
for the partial hierarchy associated to the PUHD 1 A (resp. 0 A )

The open and closed supports of a partial hierarchy

Consider now a hierarchy X with its PUHD : We de…ne its open and closed supports at level : Its open support at level is supp ( ) = fp j (p; p) < g and its closed support supp ( ) = fp j (p; p) g

Two adjunctions between P(E) and the partial hierarchies

The adjunction (0 F ; supp ) We have to show that for any A 2 P(E) and any partial hierarchy X , with a PUHD ; we have : The adjunction ( supp ; 1 F ) We have to show that for any A 2 P(E) and any partial hierarchy X , with a PUHD ; we have : supp

A supp ( ) , 0 F (A) X We know that 0 F (A) X , 0
( ) A , X 1 F (A)
We know that X 1 F (A) , 1 A ; so we have to prove that supp ( ) A , 1 A Proof. 1) Suppose that supp ( ) A: For p = 2 supp ( ); we have by de…nition (p; p) For p = 2 supp ( ) or q = 2 supp ( ) and p 6 = q we also have (p; q) : But for any p; q we have 1 A (p; q); it follows that (p; q) 1 A (p; q): For p; q 2 supp ( ) we have 1 A (p; q) = 0 (p; q) 2) Suppose now 1 A Take p verifying p 2 supp ( ) ; then (p; p) < : And as then 1 A we have 1 A (p; p) < ; showing that p 2 A: Hence supp ( ) A

The blending and grinding operators

We now established 0 F (A) X , A supp ( ) and supp ( 0 ) A , X 0 1 F (A)

Replacing A by supp ( 0 ) in the …rst equivalence and by supp ( ) in the second yields 0 F ( supp ( 0 )) X , supp ( 0 ) supp ( ) , X 0 1 F (supp ( )); showing that

h 1 F (supp ( )); 0 F ( supp ( ))
i also form an adjunction on the partial hierarchies, where 0 F ( supp ( )) is the dilation and 1 F (supp ( ) the erosion.

As 0 F ( supp ( )) is anti-extensive and idempotent, it is also an opening. And 1 F (supp ( )) is both an erosion and a closure. The block blending operator 1 F (supp( )) merges all blocks included in the support of and produces aliens outside. It is also a closure.

The block grinding operator 0 F (supp( )) pulverizes each block of the support of into its singletons and produces aliens outside. It is also an opening.

Partial hierarchies

The block blending operator 1 F (supp ( ))produces a dendrogram with two regions. One region supp ( ) with a strati…cation level equal to and one region equal to E with a strati…cation level greater than :

For all levels ; the block grinding operator 0 F ( supp ( )) produces a dendrogram where supp ( ) is pulverized in -singletons (points p verifying (p; p) = ); and outside supp ( ) there are only aliens verifying (p; p) > .

8 The lattice of partial hierarchies.

It is often interesting to combine several hierarchies, in order to combine various criteria or merge the information obtained from diverse sources (colour or multispectral images for instance). We already de…ned an order relation between hierarchies. We show here how this order relation structures them into a complete lattice. As a matter of fact, partial hierarchies and hierarchies have the same structure. The only di¤erence lies in the supports. Hierarchies have the whole domain E as support, hence any combination of hierarchies keeps this same support. On the other hand, partial hierarchies do not occupy the whole domain E and one has to consider the domain of any combination of them.

In what follows we consider the general case of partial hierarchies.

In…mum of partial hierarchies

For the sake of simplicity and pedagogy we …rst consider the case of two hierarchies.

Case of two partial hierarchies

The in…mum of two partial hierarchies A and B is written A ^B and is de…ned by its ultrametric half-distance A^B = A _ B . It is easy to check that it is indeed a half-distance. It is symmtrical and half-positive. Let us check the ultrametric inequality:

( A _ B ) (p; r)_( A _ B ) (r; q) = ( A (p; r) _ A (r; q))_( B (p; r) _ B (r; q)) > ( A (p; q) _ B (p; q)) = A _ B (p; q)
Its balls are de…ned by : 8p 2 E : Ball A^B (p; ) = Ball A (p; ) ^Ball B (p; ).

The aliens of a partial hierarchy X are characterized by 8p; q 2 E : A^B (p; q) = A (p; q) _ B (p; q) = > 0: Hence A (p; q) = or B (p; q) = ; showing that h supp (A ^B)

i C = h supp (A) i C _ h supp (B) i C or equivalently supp (AB )= supp (A) ^ supp (B)
. The aliens of A ^B are the union of the aliens of A and of B.

In…mum of a family of partial hierarchies

Consider now a family of hierarchies (A i ) i2I ; the PUHD of the hierarchy A i being i .

If this family is empty, its in…mum is the greatest hierarchy X , containing only one region, and whose PUHD veri…es 8p; q 2 E; (p; q) = 0.

For a non empty family, the PUHD of the in…mum is de…ned by : ^Ai = W i i , the smallest PUHD larger or equal to each i : And supp (

V A i ) = V i supp (A i ):

Supremum of partial hierarchies

For the sake of simplicity and pedagogy here also we …rst consider the case of two hierarchies.

The subdominant ultrametric half-distance

The supremum of two hierarchies A and B is written A _ B and is the smallest hierarchy larger than A and B.

As A ^ B is not an ultrametric distance, we chose for A_B the largest ultrametric distance which is lower than A ^ B : This distance exists: the set of ultrametric distances lower than A ^ B is not empty, as the distance 0 is ultrametric ; furthermore, this family is closed by supremum, hence it has a largest element. Let us construct it.

Consider a series of points (x 0 ; x 1 ; ; x n ): As A_B should be an ultrametric distance, we have for any path x 0 ; x 1 ; :::; x n A_B ((x 0 ; x n ) A_B (x 0 ; x 1 ) _ A_B (x 1 ; x 2 ) _ _ A_B (x n 1 ; x n ): But for each pair of points x i ; x i+1 we have A_B (x i ; x i+1 ) [ A ^ B ] (x i ; x i+1 ):

Hence A_B (x 0 ; x n ) [ A ^ B ] (x 0 ; x 1 ) _ [ A ^ B ] (x 1 ; x 2 ) _ _ [ A ^ B ] (x n 1 ; x n ):
There exists a chain along which the expression on the right becomes minimal and is equal to the maximal value taken by [ A ^ B ] on two successive points of the chain. This maximal value is called sup section of the chain for A ^ B : For this reason, the chain itself is called chain of minimal sup-section. This valuation being an ultrametric ecart necessarily is the largest ultrametric ecart below A ^ B : Let us verify the ultrametric inequality.

For p; q; r 2 E there exists a chain between p and q along which [ A ^ B ] (p; q) takes its value and another chain between q and r along which [ A ^ B ] (q; r) takes its value. The concatenation of both chains forms a chain between p and q which is not necessarily the chain of lowest sup-section between them, hence:

[ A ^ B ] (p; r) [ A ^ B ] (p; q) _ [ A ^ B ] (q; r):
We Geometrical interpretation Suppose that (x 0 ; x 1 ; ; x n ) is the chain for

which z }| { A ^ B (x 0 ; x n ) = [ A ^ B ] (x 0 ; x 1 ) _ [ A ^ B ] (x 1 ; x 2 ) _ _ [ A ^ B ] (x n 1 ; x n ) is minimal with a value : Then [ A ^ B ] (x i ; x i+1 )
means that the ball Ball A (x i ; ) or the ball Ball B (x i ; ) contains the point x i+1 : If it is Ball A (x i ; ); then x i+1 also is center of this ball. Hence a series of points x k ; x k+1 ; x k+2; all belong to the same ball Ball A (x i ; ), they are all centers of this ball and it is possible to keep only one of them and suppress all others from the list. Like that we get a path where the …rsts two points x 0 ; x 1 belong to one of the balls, say Ball A (x 0 ; ); the couple x 1 ; x 2 belong to the other Ball B (x 2 ; ); and so on. The successive ovelapping pairs of points belong alternatively to balls Ball A or Ball B :

Since

[ A ^ B ] (x i ; x i+1 )
; both points x i and x i+1 are within the closed support supp ( A ) ^supp ( B ) (recall that supp ( ) = fp j (p; p)

g) The necessity of chaining blocks for obtaining suprema of partitions is well known [START_REF] Serra | Image Analysis and Mathematical Morphology. II: Theoretical Advances[END_REF] ; Ronse has con…rmed that it is still the case for partial partitions [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF].

Supremum of a family of hierarchies or partial hierarchies

Consider now a family of hierarchies (A i ) i2I ; the PUHD of the hierarchy A i being i .

If this family is empty, its supremum is the smallest hierarchy X . In the case of hierarchies, this smallest hierarchy only contains singletons, whose PUHD veri…es 8p 6 = q 2 E; (p; q) = L; and 8p 2 E; (p; q) = 0. The smallest hierarchy among the partial hierarchies contains only aliens and its support is empty ; its PUHD veri…es 8p; q 2 E; (p; q) = L:

For a non empty family, the PUHD of the supremum is de…ned by : _Ai = z}|{ V i i ; that is the subdominant partial ultrametric distance associated to the family (A i ) i2I ,.the largest ultrametric distance which is lower than V i i : This distance exists: the set of ultrametric distances lower than V i i is not empty, as it contains the largest hierarchy, containing only one region, and whose PUHD veri…es 8p; q 2 E; (p; q) = 0. Furthermore, this family is closed by supremum, hence it has a largest element.

Its expression may be found in a similar manner as in the case of only two hierarchies. Consider a series of points (x 0 ; x 1 ; ; x n ): As _Ai should be an ultrametric distance, we have for any path x 0 ; x 1 ; :::

; x n _Ai ((x 0 ; x n ) _Ai (x 0 ; x 1 ) _ _Ai (x 1 ; x 2 ) _ _ _Ai (x n 1 ; x n ): But for each pair of points x i ; x i+1 we have _Ai (x i ; x i+1 ) [ V i i ](x i ; x i+1 ): Hence _Ai (x 0 ; x n ) [ V i i ](x 0 ; x 1 ) _ [ V i i ](x 1 ; x 2 ) _ _ [ V i i ](x n 1 ;
x n ): There exists a chain along which the expression on the right becomes minimal and is equal to the maximal value taken by [ V i i ] on two successive points of the chain. This maximal value is called sup section of the chain for V i i : For this reason, the chain itself is called chain of minimal sup-section. This valuation being an ultrametric ecart necessarily is the largest ultrametric ecart below

V i i :
The expression of _Ai (p; q) = inf p=x0;xn=q

n 1 W k=0 V i i (x k ; x k+1
): Nota bene: The in…mum inf p=x0;xn=q has to be taken on all chains of points between p and q:

Illustration

Fig. 4 presents too hierarchies HA and HB through their nested partitions. The supremum and in…mum of both hierarchies also are represented. The in…mum takes for each threshold the intersection of the corresponding partitions, obtained through intersection of the tiles. The supremum is obtained by keeping only the boundaries existing in each component.

Fig. 5 presents an initial image to segment.The H component and the V component of the colour image are segmented separately, yielding two hierarchies. Each hierarchy is illustrated trough one of its thresholds. The in…mum of both hierarchies combines the features of each of the components, yielding a decent segmentation of the initial image.

Lexicographic fusion of strati…ed hierarchies

Let A and B be two strati…ed hierarchies, with their associated distances d A and d B : In some cases, one of the hierarchies correctly represents the image to segment, but with a too small number of nested partitions. One desires to enrich the current ranking of regions as given by A; by introducing some intermediate levels in the hierarchy. The solution is to combine the hierarchy A with another hierarchy B in a lexicographic order.

One produces the lexicographic hierarchy Lex(A; B) by de…ning its ultrametric distance ; it is the largest ultrametric distance below the lexicographic distance d A;B classically de…ned by

Initial Image H component V component Infimum Initial Image H component V component Infimum
d A;B (C; D) > d A;B (K; L) , d A (C; D) > d A (K; L) or d A (C; D) = d A (K; L) and d B (C; D) > d B (K; L)
Fig. 6 present two hierarchies HA and HB and the derived lexicographic hierarchies Lex(A; B) and Lex(B; A): Fig. 7 shows an image which is di¢ cult to segment as it contains small contrasted objects, the cars and the landscape and road which are much larger and less contrasted. Two separate segmentation have been performed. The …rst based on the contrast segments the cars ; the second, based on the "volume" (area of the regions multiplied by the contrast) segments the landscape. The hierarchy of both these segmentations has been thresholded so as to show 30 regions. The lexicographic fusion of both segmentations Lex(Depth; V olume); also thresholded at 30 regions o¤ers a nice composition of both segmentations.

Adjunctions on partial hierarchies

We propose two adjunctions, a …ner and a coarser adjunction on hierarchies or partial hierarchies. The …ner one extends to partial hierarchies the adjunction proposed by J.Serra on partitions [START_REF] Serra | A lattice approach to image segmentation[END_REF], extended by Ch. Ronse on partial partitions [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF]. The coarser one is presented …rst. It is obtained by taking the supremum and in…mum of PUHDs translated by the translations associated to a structuring element.

Everything presented below is valid for hierarchies and partial hierarchies. A hierarchy X 2 X (E) is a collection of sets X i 2 P(E): Through the translation by a vector ! t ; these sets X i ! t form a new hierarcy X ! t : If is the ultrametric ecart associated to X , the ultrametric ecart associated to X ! t will be written ! t :

Depth -30 regions

As the partial hierarchies form a complete lattice X (E), we may use the same mechanism for constructing an erosion and a dilation on hierarchies. We de…ne two operators operating on a hierarchy X . For showing that the …rst

X B = V x2B X !
Ox is an erosion and the second X B = W x2B X ! xO a dilation, we have to show that they form an adjunction.

Proof of the adjunction

We have to prove that for any two hierarchies X ; Y 2 X (E) : X B < Y , X < Y B:

We will prove the adjunction through the half distance associated to the hierarchies X and Y.

We have the following correspondances between the hierarchies and the ultrametric ecarts :

X $ Y $ Y B = V x2B Y ! Ox $ W x2B ! Ox X B = W x2B X ! xO $ z }| { V x2B ! xO X B < Y , X < Y B $ z }| { V x2B ! xO > , > W x2B ! Ox
Let us now prove this last adjunction. For two arbitrary ultrametric ecarts and :

X < Y B , > W x2B ! Ox , 8x 2 B : > ! Ox , 8x 2 B : ! xO > , V x2B ! xO >
Remains to establish :

V x2B ! xO > , z }| { V x2B ! xO > : z }| { V x2B ! xO > ) V x2B ! xO > since z }| { V x2B ! xO is the largest ultrametric ecart below V x2B ! xO Suppose now V x2B ! xO > : Since is an ultrametric ecart below V x2B ! xO ; it is smaller or equal to the largest ultrametric ecart below V x2B ! xO ; that is z }| { V x2B ! xO
This completes the proof :

X < Y B , > W x2B ! Ox , V x2B ! xO > , z }| { V x2B ! xO > , X B < Y
The erosion of a partition by a square structuring element (8 connexity) is illustrated in …g.8, where the smallest squares represent each a pixel.

Figure 8: Erosion of a partition by a structuring element equal to the central point and its ' nearest neighbors. The smallest dots in the right picture show the size of the individual pixels in a square raster. Two neighboring pixels p and q belong to the same region of the eroded partition if there exists a b 2 B such that p + b and q + b both belong to the same tile of the initial partition.

Expression of the erosion and dilation, valid for hierarchies and partial hierarchies

Consider now a partial herarchy X . We have the following correspondances between the hierarchies and the ultrametric ecarts :

X $ X B = V x2B X ! Ox $ W b2B ! Ox X B = W x2B X ! xO $ z }| { V b2B ! xO
The expression of the PUHD is

X B(p; q) = W b2B ! Ox (p; q) = W f (p + b; q + b) j b 2 Bg X B(p; q) = z }| { V b2B ! xO (p; q) = z }| { V f (p b; q b) j b 2 Bg
If p B contains an alien x = p + b with a strati…cation level , then (p + b; q + b) and X B(p; q) .

Illustration

We illustrate the erosion and the opening of a one dimensional hierarchy, …rst by a structuring element reduced to two pixels, then by a structuring element made of three pixels. In the …rst case, the erosion and the dilation have to use the structuring element for the erosion and its transposed version for the dilation.

Erosion and opening by a pair of 2 pixels.

Erosion and opening by a centered segment of 3 pixels.

Adjunction on hierarchies and partial hierarchies, de-…ned on a tile by tile basis

In this section we recall how J.Serra de…ned an adjunction on partitions and how Ch. Ronse adapted it to partial partitions. We illustrate the method and compare with the adjunction presented previously, based on the supremum and in…mum of translated partitions. We then extend to partial hierarchies the adjunction de…ned by Ch. Ronse for partial partition.

Dilation/erosion on partitions

Description of the algorithm J.Serra proposed in [START_REF] Serra | A lattice approach to image segmentation[END_REF] where each tile of the partition is eroded separately. As the resulting collection of sets does not cover the domain E; he completes the empty spaces with singletons.

The adjunct dilation has been de…ned by Ch. Ronse. Il consists in dilating all non singleton sets of a partition, chain all dilated sets with a non empty intersection ; if there are empty spaces, complete with singletons in order to obtain a partition.

Discussion

The proposed erosion does not make the distinction between singletons produced by the erosion of some tile of the initial partition and singletons added to …ll empty spaces. For this reason, the adjunct dilation dilates only the non singleton parts of a partition and chains all dilated sets with a non empty intersection. If there are spaces left empty, they are …lled by singletons.

An opening and a closing can be classically obtained by chaining the erosion and dilation of the preceding adjunction. The singletons produced by a …rst erosion are discarded by the subsequent opening. Like that, a tile which is identical with the structuring element is pulverized into singletons by the opening.

It is to note that the singletons form a role apart from any other set, as the chaining between sets with non empty intersection can never pass through singletons : the intersection of a set and a singleton is always reduced to the singleton itself.

Adjunction on partial partitions

Description of the algorithm Using partial partitions alleviates this dif-…culty as shown by Ch. Ronse. The erosion of a partial partition consists in eroding each tile of the partial partition separately, producing a new partial partition, whose support contains all eroded sets produced, including the singletons. Therefore there is no need to complete the empty spaces with singletons, as the support of the partial partitions varies.

The dilation consists in dilating all tiles of the partial partition (including the singletons) and chain all dilated sets with a non empty intersection. The support of the initial partition may like that also be dilated, in order to contain all sets produced by the dilation. Here again, there is no need to …ll empty spaces with singletons.

Discussion Here, there is no need of …lling singletons, as the support of the partial partition is variable. If after an erosion, there exist singletons in the resulting partial partitions, they duly correspond to eroded sets of the initial partial partition. Therefore they may be dilated to obtain the openings.

Adjunctions on hierarchies and partial hierarchies

In this section, we establish the PUHD (partial ultrametric half distance) for Ronse's adjunction for partial partitions. It happens that the obtained expression is also valid for hierarchies and partial hierarchies.

Let be the PUHD (partial ultrametric half distance) representing a partial hierarchy and (" ; ) the adjunction of the PUHDs.

Adjunctions on partitions and partial partitions

Erosion We illustrate the method with a partition, as illustrated in …g.13. The points p and q belong to the same tile of the partition eroded by a structuring element B, if they are centers of disks entirely included in the same tile of the initial partition. In such a case all pairs x; y 2 B p [ B q belong to the same tile of the partition, hence (x; y) = 0: For the pair p; q we have " (p; q) = 0: Inversely if these conditions are not veri…ed, there exists a pair of pixels x; y 2 B p [ B q which does not belong to the same tile of the partition and (x; y) = 1: It follows from this analysis, that the PUHD " of the eroded hierarchy can be expressed as

" (p; q) = W f (x; y) j x; y 2 B p [ B q g
Consider now a point p such that B p is not included in any tile of the partition . If s 2 B p ; there exists then a t 2 B p such that (s; t) = 1; otherwise B p would belong to the same tile of the partition. For such a point p we have "

(p; p) = W f (x; y) j x; y 2 B p [ B p g = 1;
showing that it is an p q x y Figure 13: The points p and q belong to the same tile of the partition eroded by a disk, as they are centers of disks entirely included in the same tile of the initial partition.

alien in the eroded partition : On the other hand if there exists a tile of the partition containing B p and the erosion of this tile is reduced to a singleton p, then " (p; p) = W f (x; y) j x; y 2 B p [ B p g = 0: This shows that our formulation faithfully represents the proposition of Ch. Ronse for the erosion in partial partitions.

Dilation We illustrate the method with a partition, as illustrated in …g.14. The points x and y belong to the same tile of the partition dilated by a structuring element B, if there exist two nodes p and q belonging to the same tile of this partition and x; y 2 B p [ B p . In such a case (p; q) = 0: As we look for all pairs p and q verifying these conditions, we have to consider V f (p; q) j x; y 2 B p [ B q g : But as soon as there exists a node x belonging simultaneously to B p and B q for two nodes p and q belonging to distinct tiles of the initial partial partition, then B p [ B q also belongs to a unique tile of the dilated partial partition. This is the classical situation where we have an in…mum of PUHD and we have to consider the corresponding subdominant ultrametric distance to represent the …nal result. We thus get for the dilation

(x; y) = z }| { V f (p; q) j x; y 2 B p [ B q g
If a set B p only contains singletons, then V f (p; q) j x; y 2 B p g = 1: If on the contrary p is a singleton, then V f (p; q) j x; y 2 B p g = 0; showing that singletons get dilated. This again is conform to the description of dilations given by Ch. Ronse.

Adjunctions on hierarchies and partial hierarchies As a matter of fact both expressions established for partitions and partial partitions are still valid for hierarchies and partial hierarchies. If X is a partial hierarchy and its associated PUHD, then we have the classical correspondances : to the erosion "X corresponds the dilation of its PUHD p q x y Figure 14: The points x and y belong to the same tile of the dilated partial partition, if there exist two nodes p and q such that B p and B q belong to the same tile of this partition.

to the dilation X corresponds the erosion of its PUHD "

The PUHD of the eroded hierarchy "X can be expressed as

"X $ (p; q) = W f (x; y) j x; y 2 B p [ B q g
If a set B p contains an alien x; for which (x; y) = ; then " (p; q) = W f (x; y) j x; y 2 B p [ B q g (x; y) = ; showing that the pixel x can only appear in the erosion of the hierarchy at a strati…cation level higher than or equal to :

The support supp "X = supp A point p belongs to supp ( X ) as soon as W f (x; y) j x; y 2 B p g < which is equivalent with 8x; y 2 B p : (x; y) < ; which implies 8x 2 B p : (x; x) < ; showing that p belongs to supp (X ) B: Hence supp ( X ) supp (X ) B Dilation We thus get for the dilation :

X $ " (x; y) = z }| { V f (p; q) j x; y 2 B p [ B q g
If a set B p only contains singletons, then V f (p; q) j x; y 2 B p g = 1: If on the contrary p is a singleton, then V f (p; q) j x; y 2 B p g = 0; showing that singletons get dilated. This again is conform to the description of dilations given by Ch. Ronse. the sup-section of any path between p and q is necessarily higher or equal to and p = 2 supp (" ): Finally we have shown that supp (" ) = supp ( X ) = supp ( ) B:

We will give below an equivalent formulation of these operators and show that they indeed form an adjunction. 9.3 Comparison of the three adjunction for partitions and partial partitions.

We have now three distinct adjunctions on partitions. We compare them in …g.15 by …rst eroding a partition and then dilating the result with the adjunct dilation. The structuring element is a cross, made of the central pixel and its four nearest neighbors. Let be a partition. shows that q B belongs to a same tile A as p + u ; then …xing b 2 = v and varying b 1 shows that p B also belongs to this tile A: Hence there exists a tile A of the initial partition such that for each b belonging to B; p + b and q + b belong to A:

We derive from this proposition a new and equivalent expression for the erosion :

"X (p; q) $ (p; q) = W f (p + b 1 ; q + b 2 ) j b 1 ; b 2 2 Bg
Dilation Two points x and y belong to the same tile of the dilated partition by a structuring element B only if there exists a non singleton tile A of the initial partition and two points p and q in A; such that x and y belong to the dilation of these points p B and q B ; this will be the case if and only if empty spaces with singletons. If is the PUHD of a partial partition ; the PUHD of their erosion and dilation esstablished just above is still valid.

Two points p and q belong to the same tile of the eroded partition " ; by a structuring element B if and only if for each b 1 2 B and each b 2 2 B; p + b 1 and q + b 2 belong to the same tile of the initial partition. We derive a new expression for the erosion :

"X (p; q) $ (p; q) = W f (p + b 1 ; q + b 2 ) j b 1 ; b 2 2 Bg
Two points p and q belong to the same tile of the dilated partition if and only if there exist b 1 and b 2 belonging to B such that p b 1 and q b 2 belong to the same tile of the initial partition. After chaining the regions with a non empty intersection, one gets :

X (x; y) $ " (x; y) = z }| { V f (p b 1 ; q b 2 ) j b 1 ; b 2 2 Bg
This couple erosion/opening is presented in the …rst column of two images under the heading "Tile by tile on partial partitions, adjusting the support" in …g.15. Here singletons produced by the erosion remain singletons and constitute a valid tile of the eroded partial partition. This is the case for the green singleton, result of eroding the green square in the original partition. All empty spaces are expelled out of the support of the partial partition and are represented here in grey. The subsequent dilation dilates only the pixels inside the support of the erosion. Like that the green singleton left in the erosion is dilated, extending again the support of the erosion. The pixels left outside the support of the opening are represented in grey. Fig. 16 shows the behaviour of 3 pixels. During the erosion, the pixels p; q and x are expelled from the support of the partial eroded partition, are they are not centers of a structuring element included in a tile of the initial partition. During the subsequent dilation, p and q belong to the dilation of the pixels on their right, belonging to the green tile. The pixel x on the contrary does not belong to any tile of the erosion and remains outside the support of the opening.

Partial hierarchies: supremum and in…mum of PUHD

The adjunction based on the supremum and in…mum of translated hierarchies is illustrated in …g.15 under the heading "By supremum and in…mum of ultrametric 1/2 distances". Two points p and q belong to the same tile of the eroded partition " by a structuring element B if and only if, for for each b belonging to B there exists a tile A of the initial partition , such that p + b and q + b belong to A: This is the case for the pixels p and q in …g.16. The pixel x on the contrary becomes a singleton. Two points x and y belong to the same tile of the dilated partition by a structuring element B only if there exists a tile A of the initial partition, two points p and q in A and a b belonging to B; such that x = p + b and y = q + b: Consider again the pixels p and q in …g.16. They belong to the same tile of the Figure 15: Erosion and opening of a partition, obtained by chaining erosion and dilation. The …rst couple operates tile by tile with completion with singletons (Serra), the second adjusts the domain and works on partial partitions (Ronse), the last is based on the supremum and in…mum of ultrametric half distances (Meyer) dilated partition, as there right neighbors belong to the same tile of the eroded partition. Pixels q and x also belong to a same tile as their upper neighbors belong to the same tile of the eroded partition. Finally, through chaining at q; all three pixels belong to the same tile of the opening.

Ordering the adjunctions on partial hierarchies or partitions

Consider a partial partition X : We have the following correspondances between the hierarchies and the ultrametric ecarts : X $ : We just obtained the expression of the PUHD for the adjunction tile par tile ("X ; X ):

"X =
We earlier obtained the expression of the PUHD for the adjunction (X

B; X B) = V x2B X ! Ox ; W x2B X ! xO :
We have the following correspondances between the hierarchies and the corresponding PUHDs:

X B = V x2B X ! Ox $ W b2B ! Ox = B
Figure 16: Zoom on 3 pixels. Erosion and opening of a partition, obtained by chaining erosion and dilation. The …rst couple operates tile by tile with completion with singletons (Serra), the second adjusts the domain and works on partial partitions (Ronse), the last is based on the supremum and in…mum of ultrametric half distances (Meyer)

X B = W x2B X ! xO $ z }| { V b2B ! xO = B
The expression of the PUHD is

B(p; q) = W f (p + b; q + b) j b 2 Bg B(p; q) = z }| { V f (p b; q b) j b 2 Bg
These expressions may be compared with the tile by tile erosion and dilations, which are expressed by

"X (p; q) $ (p; q) = W f (x; y) j x; y 2 B p [ B q g = W f (p + b 1 ; q + b 2 ) j b 1 ; b 2 2 Bg X (p; q) $ " (p; q) = z }| { V f (x; y) j p; q 2 B x [ B y g = z }| { V f (p b 1 ; q b 2 ) j b 1 ; b 2 2 Bg
These expression verify the following order relations :

W f (p + b; q + b) j b 2 Bg W f (p + b 1 ; q + b 2 ) j b 1 ; b 2 2 Bg ; showing that the partial hierarchy "X is coarser than the partial hierarchy X B z }| { V f (p b 1 ; q b 2 ) j b 1 ; b 2 2 Bg z }| { V f (p b; q b) j b 2
Bg showing that the partial hierarchy X is …ner than the partial hierarchy X B If the origin belongs to the structuring element we have the following order relations between the partial hierarchies : "X X B X X B X

Decomposition and recomposition of hierarchies

The next section proposes an inf-decomposition and a sup decomposition of hierarchies, which are useful for analysing the behaviour of the various adjunctions working on hierarchies, as erosion commute with in…mum and dilation with supremum. Let X be a partial hierarchy with its associated PUHD :

9.4.1 Inf-generation of a partial hierarchy i.e sup-generation of its PUHD For each pair p; q we want to construct a 2 regions hierarchy pq where the distance (p; q) is well represented and all other couple of points r; s take a value which is inferior : pq (r; s) (r; s):

For p; q 2 E; one de…nes A pq = B(p; (p; q)); ; the open ball centered at p and q with a radius (p; q): The hierarchy pq has only two regions A pq and its complement A pq : It is de…ned by: pq (x; y) = 0 if x; y 2 A pq or x; y 2 A pq (p; q) otherwise The inf-generation of X is associated to the PUHD : = W p;q pq Fig. 17 presents the decomposition into three component of a hierarchy with three leaves. The …rst hierarchy is obtained for p belonging to the green region and q to the blue one. The second is obtained by exchanging p and q: The last one is obtained for p belonging to the orange region, q being outside. The values of the boundaries of each partial hierarchy are indicated in red.

Analysis of the erosion of partial hierarchies, i.e. dilation of their PUHDs

Case of X B(p; q) $ W b2B ! Ox (p; q) = W f (p + b; q + b) j b 2 Bg B = W p;q pq ! B = W p;q pq B For
; t) = 0 Case of "X (p; q) $ (p; q) = W f (x; y) j x; y 2 B p [ B q g = W f (p + b 1 ; q + b 2 ) j b 1 ; b 2 2 Bg = W p;q pq ! = W p;q pq For s; t 2 E : pq (s; t) = 0 if 8b 1 ; b 2 2 B : s + b 1 ; t + b 2 2 A or s + b 1 ; t + b 2 2 A (p; q) if 9b 1 ; b 2 2 B : s + b 1 2 A and t + b 2 2
A This analysis shows that as soon one point s + b 1 belongs to A (resp. A), the whole element B has to belong to A (resp. A) to get a value 0 for the dilation of the PUHD.

Sup-generation of a partial hierarchy i.e inf-generation of its PUHD

For each pair p; q we want to construct a 2 regions hierarchy pq where the distance (p; q) is well represented and all other couple of points r; s take a value which is superior : pq (r; s) (r; s): For p; q 2 E; one de…nes A pq = B(p; (p; q)); the closed ball centered at p and q with a radius (p; q): The hierarchy pq has only two regions A pq and its complement A pq : The hierarchy pq is de…ned by pq (x; y) = (p; q) if x; y 2 A pq L otherwise The sup-generation of X is associated to the PUHD : = V p;q pq : Hence = V p;q pq ;which is a PUHD and is identical with its transitive closure: = V p;q pq = z }| { V p;q pq : Fig. 17 presents the decomposition into four component of a hierarchy with three leaves. The values of the boundaries is indicated in red. The …rst hierarchy is associated to a couple of points, both in the green region. The second to a couple of points, both in the blue region. For the third, one point is in the green region and the other in the blue region. The last is associated to two points, one in the orange region and the other in the green region.

This analysis shows that for all pairs of points (s; t) inside B p [ B q ; we have "1 pq (s; t) = (p; q)

10 Some examples of hierarchies Hierarchies associated to a dissimilarity index A series of nested partitions (X i ) ; and hence a hierarchy, may easily be generated from an initial …ne partition X 0 = [R i , i = 1; : : : ; n on which a dissimilarity index is de…ned between a subset G of all couples of tiles. For a couple of tiles which do not belong to G; we de…ne a dissimilarity equal to 1:

If we now take the union of all tiles of X 0 with a dissimilarity index below a given threshold ; we obtain a coarser partition with a strati…cation index equal to . For increasing values of we obtain a series of nested partitions, forming a hierarchy A. The ultrametric distance d associated to this hierarchy is precisely the subdominant ultrametric distance associated to , that is the largest ultrametric distance below (see below the supremum of two hierarchies, where the subdominant ultrametric distance also appears) For two tiles A and B of X 0 ; the subdominant ultrametric distance will be the lowest level for which A and B belong to the same tile (if it does not happen, their distance is 1)

Other possible measures are color distances, various measures of local contrast, or even motion or texture dissimilarity between adjacent catchment basins.

Case of the watershed tesselation If the tessellation is the result of the watershed construction on a gradient image, the dissimilarity measure can be de…ned as the altitude of the pass point separating two adjacent regions. The ultrametric half distance between two minima is then the " ‡ooding distance" : the ‡ooding distance between two points p and q is the altitude of the lowest ‡ooding for which p and q both belong to a common lake.

If the ‡ooding is not uniform but increasing with a time parameter ; then the distance between two points p and q is the time when both points …rst belong to the same catchment basin of the ‡ooded surface.

The stochastic watershed introduced by J.Angulo [START_REF] Angulo | Stochastic watershed segmentation[END_REF] is yet another interesting hierarchy, able to produce …ne segmentations both on medical image as on multimedia images.

Hierarchies for interactive segmentation 11.1 An adjunction associated to a partition

To any partition on E we may associate a dilation . For a point p 2 E; one de…nes (p) = cl(p): One then de…nes (

X) = S f (x) j x 2 Xg = S fC i 2 j X \ C i 6 = ;g
The properties of are the following :

Applications : interactive segmentation

The following examples have been developed within a toolbox for interactive segmentation ( [START_REF] Zanoguera | An interactive colour image segmentation system[END_REF]).

Intelligent brush

An intelligent brush segments an image by "painting" it: it …rst selects a zone of interest by painting. Contrary to conventional brushes, the brush adapts its shape to the contours of the image. The shape of the brush is given by the region of the hierarchy containing the cursor. Moving from one place to another changes the shape of the brush, when one goes from one tile of a partition to its neighboring tile. Going up and down the hierarchy modi…es the shape of the brush. In …g.19, on the left, one shows the trajectory of the brush ; in the centre, the result of a …xed size brush, and on the right the result of a selfadapting brush following the hierarchy. This self adapting brush is nothing by the dilation r by a ball associated to the hierarchy, centered at the position of the mouse and of a radius, also easily modi…ed through the mouse. This method has been used with success in a package for interactive segmention of organs in 3D medical images.

Mouse trajectory Fixed size brush Intelligent brush Mouse trajectory

Fixed size brush Intelligent brush

Figure 19: Comparison of the drawing with a …xed size brush and a self adaptive brush.

Magic wand

The magic wand in a conventional computer graphics toolbox consists in extracting the region which touches the position of the mouse and whose colour lies within some prede…ned limits from the coulour at the mouse position. The next step consists in replacing this set by the smallest set of the hierarchy which contains it. This operation is a dilation and a closing, described by Ch. Ronse as Lemma 8 in [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF]. The result is shown in …g.20

C x = fC : x 2 C Cg
then the union of each non-empty family of sets of C x ; all containing x still belongs to C x ; because of (C2). Hence Inv( x ) = C x [ f?g is the invariant set of an opening x ; called connected opening of origin x: Its expression is Proposition 25 Assume that C is a connectivity on E, then the following conditions are satis…ed: (O1) every x is an opening (O2) x (fxg) = fxg (O3) x (X) \ y (X) = ? or x (X) = y (X) (O4) x = 2 X ) x (X) = ? Conversely if x; x 2 E; is a family of operators satisfying (O1)-(O4) then C = S x2E Inv( x ) de…nes a connectivity.

The principal interest of connection openings lies in the following corollary of [START_REF] Serra | Image Analysis and Mathematical Morphology. II: Theoretical Advances[END_REF] Corollary 26 Openings x partition any X E into the smallest possible number of components belonging to the class C.

Given a set X E; every connected component x (X) of X is called a grain of X: The next result ( [START_REF] Heijmans | Connected morphological operators for binary images[END_REF]) says that every connected subset of X is contained within some grain of X Proposition 27 Given a connectivity on E and a set X E: If C X is a connected set, then C is contained within some grain of X:

Another useful property ( [START_REF] Serra | Image Analysis and Mathematical Morphology. II: Theoretical Advances[END_REF]), shows that x plays no particular role in x (X):

Corollary 28 For all x; y 2 E and all X E we have y 2 x (X) , x (X) = x (X) and in particular y 2 x (X) , x 2 y (X) And …nally the link between connective classes and partitions.

De…nition 29 Given a space E; a function P : E ! P (E) is called a partition of E if (i) x 2 P (x); x 2 E (ii) P (x) = P (y) or P (x) \ P (y) = ?; for x; y 2 E Properties : is a partial ultrametric distance as: 8p; q 2 E : (p; q) = (q; p) 8p; q; r 2 E : (p; q) max f (p; r); (r; q)g The ultrametric half-distance structures the subsets of P(E) by associating to each set A 2 P(E) its diameter : diam(A) = W p;q2A (p; q): If A = 2 supp(X ); then diam(A) = L: Obviously diam(A) is increasing : if A B : diam(A) diam(B); since B contains more pairs of points than A:

The following lemma will establish the link with the connections.

Lemma 33 if A i 2 P(E) and T i2I

A i 6 = ?; then diam( S

i2I A i ) = W i2I diam(A i )
Proof. Two cases are to be considered: a) there exists a point p = 2 supp(X ) and p 2 A k S i2I A i ; then for any 2 E :

(p; q) = L; and diam( S

i2I A i ) = W i2I diam(A i ) = diam(A k ) = L b) S i2I
A i supp(X ): As T i2I A i 6 = ?; let r be an arbitrary point in T i2I A i : Then 8p; q 2 S i2I A i : (p; q) (p; r) _ (r; q): But if p 2 A l ; then (p; r) diam(A l );

and if q 2 A m ; then (r; q) diam(A m ): This shows that if we consider all pairs p; q 2 S i2I A i then (p; q) W i2I diam(A i ):

Inversely, as for each k 2 I : A k S The connected opening of origin x associated to the connection T has the following expression : X 2 of T containing r and q; in particular those for which becomes minimal. Hence (p; q) (p; r) _ (r; q): As we have associated to the taxonomy an ultrametric half-distance, all results presented above become applicable.

Adjacency relations

Reminder : Adjacency based connections An important subclass of connectivity classes is based on adjacency.

De…nition 39 A binary relation on E E is called an adjacency relation if it is re ‡exive (x x for every x) and symmetrical (x y i¤ y x).

Given an adjacency relation on E E; we call x 0 ; x 1 ; :::; x n a path between x = x 0 x ::::

x n = y: De…ne C P(E) as the collection of all C 2 E such that any two points in C can be connected by a path that lies entirely in C: There exists two indices in I such that x 2 C i1 and x 2 C i2 : There exists a path linking x with z in C i1 and a path linking z with y in C i2 : The path between x and y is obtained by concatenating both paths.

Proposition

Grey tone dissimilarity relations

We de…ne a dissimilarity between neighboring points (p; q) verifying :

re ‡exivity : 8p 2 E : (p; p) = 0 symmetry : 8p; q 2 E : (p; q) = (q; p):

As an example we may consider a grey tone image de…ned on a grid and the following dissimilarity for neighboring pixels : (p; q) = jf p f q j : Based on this dissimilarity, we derive the same hierarchy, by very di¤erent means. The …rst method constructs the dendrogram based on the supremum of hierarchies. The second is generative, based on a taxonomy.

The lattice of hierarchies We extend the dissimilarity between two pixels into an ultrametric half distance : pq (p; q) = (p; q) for any other couple of pixels pq (s; t) = L Finally we have de…ned taxonomies, extendeding to hierarchies the connections previously only de…ned for partitions.

Figure 3 :

 3 Figure 3: Two strati…cation indices compatible with the same dendrogram:On the left, we consider the watershed segmentation if one takes as marker the minima, ordered by their altitude. The coarsest level covers the domain. The next level is associated to the two lowest minima taken as markers. The successing levels progressively introduce more minima until all minima are used as markers, cyielding the …nest segmentation. On the right, the coarsest and …nest segmentations are the same. Here we consider a ‡ooding with uniform and growing altitude over the domain E: As lakes merge, cachment basins also merge. The order of merging is however quite di¤erent from the left …gure.

  De…nition 18 A half-distance on a domain E is a mapping d from E E into R + with the following properties: 1) Symmetry : d(x; y) = d(y; x) 2) Half-positivity: d(x; y) 0 and d(x; x) = 0 3) Triangular inequality: d(x; z) d(x; y) + d(y; z) De…nition 19 A half metric space is a set E with a family (d i ) i2I of halfdistances verifying the following condition: the family (d i ) i2I is a directed set, i.e. for any …nite subset J of I; there exists an index k 2 I such that d k d j for all j 2 J The open half balls B i;o (a; R) (resp. closed B i (a; R) of a center a 2 E; of radius R and index i are the sets of all x of E such that d i (a; x) < R (resp. R).

7. 7 . 1 1 :

 711 InterpretationPartial partitions The block blending closure and block grinding operator have been introduced by Ch. Ronse, p.359 in[START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF]. Partial partitions are particular partial hierarchies where the ultrametric 1/2 distance takes only the values 0 and Let be such a partial hierarchy. Its open support at level 1 is supp 1 ( ) = fp j (p; p) < 1g and its closed support at level 0 is supp 0 ( ) = fp j (p; p) 0g are identical with the support supp( ) of :

Figure 4 :

 4 Figure 4: Two hierarchies HA and HB and their derived supremum and in…mum

Figure 5 :Figure 6 :

 56 Figure 5: Supremum of two hierarchies.

Fusion

Figure 7 :

 7 Figure 7: Lexicographic fusion of two hierarchies

Figure 9 :Figure 10 :

 910 Figure 9: Erosion and opening by a pair of pixels: intermediate steps

Figure 11 :Figure 12 :

 1112 Figure 11: Erosion and opening by a segment of 3 pixels: intermediate steps

  The support supp X = supp "A point p belongs to supp (" ) as soon as " (p; p) = : A su¢ cient condition is the existence of a b 2 B such that (p b; p b) = ; this will be the case if p belongs to supp ( ) dilated by B: Hence supp ( ) supp (" ): Inversely if p = 2 supp ( ) B; then there exists a b 2 B; such that (p b; p b) > : But then for any q we have (p b; q) > ; showing that V f (p b 1 ; q b 2 ) j b 1 ; b 2 2 Bg > : In this case,

9. 3 . 1

 31 Partitions : Tile by tile construction, …lling with singletons(Serra, Ronse) Erosion The adjunction on partitions, proposed by J. Serra may be expressed as follows. Two points p and q belong to the same tile of the eroded partition " ; by a structuring element B if and only if there exists a tile A of the initial partition , such that for each b belonging to B; p + b and q + b belong to A: This condition may be reformulated as follows.Proposition 22 Two points p and q belong to the same tile of the eroded partition " ; by a structuring element B if and only if for each b 1 2 B and each b 2 2 B; p + b 1 and q + b 2 belong to the same tile of the initial partition. Proof. a) Suppose that there exists a tile A of the initial partition such that for each b belonging to B; p + b and q + b belong to A: Then p B and q B belong to A and 8b 1 ; b 2 2 B; p + b 1 and q + b 2 belong to A b) Inversely suppose that for each b 1 2 B and each b 2 2 B; p + b 1 and q + b 2 belong to the same tile of the initial partition. Fixing b 1 = u and varying b 2

Figure 17 :

 17 Figure 17: Min-decomposition of a hierarchy into three elementary hierarchies.

: x 2 C

 2 C and C Xg Since any x 2 E belongs to a connected set of C, we have C = S x2E Inv( x )

i2IA

  i ; and as diam is an increasing operator, we have diam(A k ) diam(S i2I A i ): Hence W i2I diam(A i ) diam( S i2I A i ):This shows that indeed diam(S i2I A i ) = W i2I diam(A i ):Corollary 34 The family T P(E) of all sets A verifying diam(A i ) < L forms a partial connection. If the dendrogram is a (covering) hierarchy, then we get a connection.Proof. A i 2 T and T i2I A i 6 = ?; then diam( S i2I A i ) = W i2I diam(A i ) < ; hence S i2I A i 2 T lAs increases, the family T gets larger and its support also increases. The whole P(E) gets structured in connections with increasing indices.In the binary case, we have a binary ultrametric half-distance. And a set verifying diam(A) < 1 is included in one of the classes of the partition. If two sets A and B have a non empty intersection and verify diam(A) = diam(B) = 0; then they belong to the same tile of the partition as diam(A [ B) = diam(A) _ diam(B) = 0: 12.2.2 The connected openings of origin x:

  40 If is an adjacency relation on E E, then C is a connectivity class. Proof. (C1) is obvious. If C i 2 C and z 2 T i2I C i ; we have to show that any two points x; y in S i2I C i can be connected by a path that lies entirely in S i2I C i :

  0 belong to the support of the dendrogram but do not belong to any leave. On the contrary …g.1 also presents a dendrogram, with the same order relation between the regions, but each point of the support of the dendrogram belongs to a leave. Consider a set A 2 X and a point p 2 A supp(X ). There exists B 2 Leav(X ) and x 2 B: If B = A then S fB 2 X j B A ; B 6 = Ag = f;g : On the other hand if B 6 = A then A and B have a non empty intersection, implying A B

	Proof. a) Suppose	S	Leav(X ) = supp(X )
	or B S fB 2 X j B A ; B 6 = Ag = fAg A: As B is a leave, we necessarily have B b) Suppose now that 8A 2 X : S fB 2 X j B A ; B 6 = Ag = fA; ;g A: This shows that It is always true that S home(p) = supp(X )
			p2supp(X )
	Let us show that for any p 2 supp(X ); we have A = home(p) 2 Leav(X ) If home(p) = 2 Leav(X ); then home(p) contains sets B 2 X ; B 6 = A and p = 2 B Hence p = 2 S p2supp(X ) fB 2 X Hence home(p) 2 Leav(X ); and S home(p) = S Leav(X ) = supp(X ):
	De…nition 15 We call hierarchy H a dendrogram verifying: supp(H)	S	Leav(H) =
	Proposition 16 A dendrogram X is a hierarchy if and only if it veri…es the union axiom:
	(Union axiom ) Any element A of X is the union of all other elements of X contained in A:
	8A 2 X :

7.1 De…nition of hierarchies

Fig.

1

presents a hierarchy whereas …g.2 presents a dendrogram, presenting various lakes ‡ooding a topographic surface. Areas which are covered by at least one lake belong to the support of the dendrogram. However, a lake C which contains a smaller lower lake C 0 is not a leave of the dendrogram. The points of C which do not belong to C S fB 2 X j B A ; B 6 = Ag = fA; ;g j B A ; B 6 = Ag showing that the hypothesis S fB 2 X j B A ; B 6 = Ag = fA; ;g is false.

  For p 2 A; we have by de…nition 0 A (p; p) = : As A supp ( ) we also have p 2 supp ( ); hence (p; p) : It follows that for p, we have (p; p) 0 A (p; p): Now for p = 2 A : 0 A (p; p) = L and for p 6 = q 2 E : 0 A (p; p) = L; so here also

	supp ( ) , Proof.	0 A
	1) Suppose that A supp ( ):
	0 A
	2) Supppose now	0 A
	Take p = 2 supp ( ); hence (p; p) > . Hence 0 A (p; p) that p = 2 A It follows that A supp ( )	(p; p) > showing

A ; so we have to prove that A

  s; t 2 E : pq B(s; t) = 0 if 8b 2 B : s + b; t + b 2 A or s + b; t + b 2 A (p; q) if 9b 2 B : s + b 2 A and t + b 2 A This analysis shows that provided each pair s + b; t + b belongs to the same tile A or A; then pq B(s

there exist b 1 and b 2 belonging to B such that x = p + b 1 and y = q + b 2 : This condition may be reformulated as follows.

Proposition 23 Two points x and y belong to the same tile of the dilated partition by a structuring element B if and only if there exist b 1 and b 2 belonging to B such that x b 1 and y b 2 both belong to the same tile of the initial partition.

After transitive closure, one gets :

Adjunction The couple ("X ; X ) forms an adjunction for the partial hierarchies. In order to prove it, we show that (" ; ) forms an adjunction for the PUHDs.

Proof.

We have to show that for any couple of PUHD ; : , " 8p; q 2 E :

(p; q) , 8b 1 ; b 2 2 B : (p; q) (p b1; q b2) , (p; q) V f (p b 1 ; q b 2 ) j b 1 ; b 2 2 Bg And (p; q), being a PUHD smaller than f (p b 1 ; q b 2 ) j b 1 ; b 2 2 Bg is smaller than the subdominant ultrametric smaller than f (p b 1 ; q b 2 ) j b 1 ; b 2 2 Bg ; i.e. (p; q) z }| { V f (p b 1 ; q b 2 ) j b 1 ; b 2 2 Bg :

Illustration This couple erosion/opening is presented in the …rst column of two images under the heading "Tile by tile, …lling with singletons" in …g.15. The singletons which are produced get a uniform yellow colour. Fig. 16 shows the behaviour of 3 pixels. After the erosion, the empty spaces are replaced by singletons, are they are not centers of a structuring element included in a tile of the initial partition. On the contrary, the central square is eroded into a singleton. There is no means to distinguish this singleton from the "…lling singletons" at positions p and q: During the subsequent dilation, p and q belong to the dilation of the pixels on their right, belonging to the green tile. The pixel x on the contrary does not belong to any tile of the erosion and remains a singleton in the opening. The adjunction on partial partitions, identical with the preceding, except that the support of the erosion and dilations varies, avoiding the need to …ll the Figure 18: Max-decomposition of a hierarchy into 4 elementary partial hierarchies

Pulse inf-generation of a PUHD

A pulse inf-generation of a PUHD may be de…ned by considering pairs of pixels, considered as pulses. To each pair p; q 2 E; one associates a PUHD 1 pq taking the value L for all pairs (s; t) 6 = (p; q) and the value (p; q) for the pair (p; q): The PUHD 1 pq veri…es 1 pq with equality for the pair (p; q) : 1 pq (p; q) = (p; q): Hence = V p;q 1 pq ;which is a PUHD, hence the transitive closure is not necessary and = V p;q

Analysis of the dilation of partial hierarchies, i.e. erosion of their PUHDs

For s; t 2 E : 1 pq B(s; t) = (p; q) if 9b 2 B : p b = s and q b = t L otherwise This analysis shows that the erosion by B takes a value di¤erent of L only for the pairs of points for which there exists a b 2 B such that p b = s and

For s; t 2 E : "1 pq (s; t) = (p; q) if 9b 1 ; b 2 2 B : s b 1 = p and t b 2 = q L otherwise is increasing and commutes with union : it is indeed a dilation obvioulsy x 2 (x) ; hence is extensive it is also a closing. The fact that also is a closing seems at …rst sight strange, as the class of invariants of a closing is stable by intersection. But the invariants of are unions of classes of the partition : Hence their class is stable by intersection. It is easy to check that is a dilation-closing :

By duality, we have " = ":

Let us now study the erosion " adjunct to : Y "(X) , (Y ) X:

By duality " is increasing, anti-extensive, idempotent and commutes with intersection, it is an erosion-opening: " = " 11.2 Adjunctions associated to a hierarchy X .

A …rst adjunction for interactive segmentation

The closed balls Ball(x; ) of radius form a partition, for which we may apply the results of the previous paragraph and de…ne the adjunction ( ; " ) de…ned by:

A second adjunction, centered on a point x

The family of balls Ball(x; ) for increasing values of is completely ordered for the inclusion. Thus, as recalled by Ch. Ronse in [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF], the two following operators form an adjunction :

) X is an erosion and an opening. It is the largest ball Ball(x; ) centered in x included in X:

) is a dilation and a closing. It is the smallest ball Ball(x; ) centered in x containing X: These two operators are useful for interactive segmentation. 12 Connectivity and taxonomy classes

The notion of a connected set in E is well de…ned if E is a topological space. In [START_REF] Serra | Image Analysis and Mathematical Morphology. II: Theoretical Advances[END_REF], Serra generalized this concept by the introduction of a connectivity class. Connectivity classes de…ne the subsets of E which are connected. Hence they help decomposing every set X 2 P(E) into its connected components. Connectivity classes have been extensively studied by Serra and Ronse ( [START_REF] Serra | A lattice approach to image segmentation[END_REF], [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF]) ; these authors later called them connections. A clear presentation of the developments linked to connectivity may be found in [START_REF] Heijmans | Connected morphological operators for binary images[END_REF].

In this last section we show how dendrograms and their associated half distance shed a new light on connections.

Reminder on connections

Alternatively, we say that C de…nes a connectivity on E: An element of C is called a connected set. This de…nition is "generative" : larger connected sets are generated from elementary ones with a non empty intersection.

If we drop the condition fxg 2 C for x 2 E; then we get a partial connection. The union of all sets belonging to C is called support of C : supp(C):

Connectivity openings

Serra in [START_REF] Serra | Image Analysis and Mathematical Morphology. II: Theoretical Advances[END_REF] has shown that any connected class C is equivalent with the datum of a connected opening, de…ned through its invariance domain. If C x denotes the subclass of C 2 C that contains a given point ;

If E is endowed with a connectivity C and if P (x) 2 C for every x 2 E; then we say that the partition P is connected.

Given a connective class, every binary image (i.e.set) X E can be associated with a connected partition P (X) where the zones of P (X) are the grains of X and X c : The zone of P (X) containing a point p is :

Corollary 30 For all x; y 2 E and all X E we have y 2 P (X)(x) , P (X)(x) = P (X)(y) and in particular y 2 P (X)(x) , x 2 P (X)(y)

Corollary 31 For all x; y 2 E and all X E we have y = 2 P (X)(x) , P (X)(x) \ P (X)(y) = ?

Proof. If x 2 X and y = 2 X; or vice-versa, then the implication is obvious. Consider the case where x; y both belong to X or both belong to X c : Suppose that there exists a point z 2 P (X)(x) \ P (X)(y) ; this would imply that P (X)(x) = P (X)(z) = P (X)(y) which contradicts the hypothesis

Connected operators

De…nition 32 An operator on P(E) is connected if the partition P ( (X)) is coarser than P (X) for every set X E

Connections associated to a dendrogram 12.2.1 An increasing family of connections

Consider a dendrogram X with a strati…cation index st; which induces on the points of E a partial ultrametric distance de…ned as follows, for p; q 2 E;: p = 2 supp(X ) : (p; p) = L and (p; q) = L for p; q = 2 supp(X ) : If no set of X contains both p and q; then (p; q) = L:

for p; q 2 supp(X ) : let A be a set of X containing both p and q: Thus the family (A i ) i2I of sets of X containing both p and q has a non empty intersection, and as established above is completely ordered for : It possesse a smallest element. The distance (p; q) is the strati…cation level of the smallest set in this family.

x (X) = S fC : x 2 C T and C Xg All C such that x 2 C T ; have a non empty intersection, hence their union belongs also to T :

We recall that Ball(p; ) = fq 2 E j (p; q) < g :

We know that the diameter of a ball is equal to its radius. Hence diam( Ball(x; ) \ X) diam( Ball(x; )) < : Hence Ball(x; ) \ X 2 T and obviously belongs to As a consequence, we get an expression for Ball(x; ) = x (E): This shows that the knowledge of x fully describes the hierarchy, as it helps reconstructing the balls Ball(x; ) which are precisely the sets of the hierarchy. And inversely, knowing the balls Ball(x; ) permits a direct construction of x :

Its expression clearly shows that x (X) = Ball(x; ) \ X is an opening : it is increasing, anti-extensive and idempotent.

The property x (X)\ y (X) = ? or x (X) = y (X) is due to the fact that in Ball(x; ); every point is centre. So if y 2 Ball(x; ); then Ball(x; ) = Ball(y; ) and x (X) = y (X): On the contrary, if y = 2 Ball(x; ); then Ball(x; ) \ Ball(y; ) = ? and x (X) \ y (X) = ?:

As Ball(x; ) is increasing with ; so is x (X):

An adjunction associated to the balls Ball(x; )

The family of balls Ball(x; ) for increasing values of is completely ordered for the inclusion. Thus, as recalled by Ch. Ronse in [START_REF] Ronse | Adjunctions on the lattices of partitions and of partial partitions[END_REF], the two following operators form an adjunction :

) X is an erosion and an opening. It is the largest ball Ball(x; ) centered in x included in X:

) is a dilation and a closing. It is the smallest ball Ball(x; ) centered in x containing X: These two operators are useful for interactive segmentation.

Taxonomies and connections

We recall once again the de…nition of a connection.

De…nition 36 Let E be an arbitrary nonempty set. A family C P(E) is called a connectivity class or connection if it satis…es (C1) ? 2 C and fxg 2 C for

This de…nition may be reformulated in the following way. We attribute to each subset C P(E) a binary label , verifying: (A1) (?) = 1 and (fxg) = 0 for x 2 E (A2) if A i 2 P(E) and

It is then easy to check that the family of all subsets with label 0 forms a connection.

We now extend this de…nition to taxonomies, where the labels take values in [0; L] : De…nition 37 Let E be an arbitrary nonempty set. A family T

The support of the taxonomy is the union of all sets A with a label smaller than L : (A) < L: The taxonomy class T of level are all sets A with a label smaller than : (A) < : T obviously forms a connection.

A dendrogram associated to the taxonomy T

Proposition 38 An ultrametric half distance is associated to each taxonomy T . It is de…ned by: 8p; q 2 E : (p; q) = V f (X) : X 2 T and p; q 2 Xg : In the case where no set of T contains p and q; then (p; q) = (?) = L: In particular if no set of T contains p then (p; p) = (?) = L; and also for each q 6 = p : (p; q) = (?) = L Proof. a) Obviously (p; q) = (q; p) b) Consider three points p; q; r 2 E: We have to verify the ultrametric inequality:

(p; q) (p; r) _ (r; q) If no set of T contains r; then (p; r) = (r; q) = L and the inequality is satis…ed If no set of T contains p and r (resp. r and q) then (p; r) = L (resp. (r; q) = L) and the inequality is satis…ed Suppose that there exists a set X 1 of T containing p and r and a set X 2 of T containing r and q, then X 1 [ X 2 contains p; q and r and (p; q)

This relation remains true for all sets X 1 of T containing p and r and all sets It is easy to check that pq is an ultrametric half-distance. The minimum in the lattice of ultrametric half-distances is an ultrametric half distance, called single linkage half distance.

z }| { V p;q pq de…nes a hierarchy where the balls Ball(x; ) are the lambda ‡at zones with slope lambda. z }| { V p;q pq (x; y) is the maximal dissimilarity on the path of smallest sup-section between x and y (see above).

A generative construction of a taxonomy We may also consider all pairs of neighboring pixels as a generative family for a taxonomy, governed by the rules given above :

The diameter of an element in the family is the maximal dissimilarity between two neighboring pixels. The associated half distance is 8p; q 2 E :

(p; q) = V f (X) : X 2 T and p; q 2 Xg

Conclusion

Two trees govern multiscale mathematical morphology. On one hand the mintree/max-tree structures the successive thresholds of an image ; on the other hand hierarchical segmentation which produces series of nested partitions. Both are dendrograms, characterized by a simple but constraining axiom : for any set belonging to the dendrogram, Pred(A) is well ordered for the inclusion order : Partitions and partial partitions are even simpler Pred(A) = A: We have developed all usual concepts and tools from this simple axiom, in particular the so useful partial ultrametric distance governing the points of the domain E:

We have shown that dendrograms have the structure of a complete lattice. The successive thresholds of a dendrogram have increasing supports. By adding the union axiom, one obtains hierarchies where the support of all thresholds is identical. If furthermore the support of a hierarchy covers the domain E; we say that it is a covering hierarchy. The catchment basins of a topographic surface, as the relief is progressively ‡ooded, form a covering hierarchy.

The ‡exibility of the supports of a dendrogram permits a simple de…nition of erosions and dilations, the support of the resulting dendrogram increasing or decreasing as needed by the transform. Two adjunctions have been de…ned, a …ner and a coarser one, from which openings, closings and morphological …lters may be derived.

It remains now to implement these operators in order to derive the classical morphological …lters based on openings and closings.

We have reinterpreted some classical tools for interactive image segmentation in the light of the structures studied above.