Morphological Hierarchies: A Unifying Framework with New Trees

Abstract

Morphological hierarchies constitute a rich and powerful family of graph-based structures that can be used for image modeling, processing and analysis. In this article, we focus on an important subfamily of morphological hierarchies, namely the trees that model partial partitions of the image support. This subfamily includes in particular the component-tree and the tree of shapes. In this context, we provide some new graph-based structures (one directed acyclic graph and three trees): the graph of valued shapes, the tree of valued shapes, the complete tree of shapes and the topological tree of shapes. These new objects create a continuum between the two notions of component-tree and tree of shapes. In particular, they allow to establish that these two trees (together with a third notion of adjacency tree generally considered in topological image analysis) can be defined and handled in a unified framework. In addition, this framework enables to enrich the component-tree with additional information, leading on the one hand to a topological description of grey-level images that relies on the same paradigm as persistent homology, and on the other hand to the proposal of a topological version of tree of shapes. This article provides a theoretical analysis of these new morphological hierarchies and their links with the usual ones. It also proposes an algorithmic description of two ways of building these new morphological hierarchies, and a discussion on the links that exist between these morphological hierarchies and certain topological invariants and descriptors.

1 Introduction

1.1 Context

Hierarchical paradigms provide efficient solutions for modeling, handling or analysing numerical images. In particular, over the last 50 years, many hierarchical structures—generally trees—have been proposed for various purposes, e.g. topological modeling (adjacency tree [49]), efficient navigation (quad/octrees [60]) or multiscale analysis (irregular pyramids [28]).

In the field of mathematical morphology [32], the development of the framework of connected operators [54] has led to the proposal of a rich family of graph-based hierarchical structures. These structures model finite sets of partitions of the image support, organized with respect to the refinement order relation.

The most popular are trees, i.e. rooted, connected acyclic graphs. It is possible to classify them with respect to the partitions they model. On the one hand, these partitions can be total. This is the case of the binary partition tree and its variants [45, 52], the $\alpha$-tree [56] or the hierarchical watersheds [31, 55]. On the other hand, these partitions can be partial [47]. This is the case of the component-tree and its variants [22, 44, 53] or the tree of shapes and its variants [9, 27, 57].

Other hierarchical structures are directed acyclic graphs (DAGs). This is, for instance, the case of the component-hypertree [39], the component-graph [41], the braid of partitions [19] and the directed component hierarchy [43].

The partitions modeled by these hierarchical structures are composed of connected sets. The notion of connectivity is then of paramount importance and was thoroughly investigated (an exhaustive overview is beyond the scope of this discussion, see e.g. [6, 46]). It is generally expected that a numerical (discrete) image content be structurally organized with respect to the usual topological paradigms of the underlying (continuous) space that it represents. Under this hypothesis, the notion of connectivity is generally expressed in topological frameworks designed to be well-fitted with digital grids (e.g. Cartesian space [50], cubical complex space [21]) or more general discrete spaces (e.g. meshes, tesselations). In this context, efforts were geared towards making these discrete topological frameworks compliant between them [26] and with the standard topology in Euclidean spaces [25], from the point of view of connectivity, but also with respect to important properties such as the Jordan-Brouwer separation property [23].

1.2 Motivations

In this article, we focus on the partial partitions which are of paramount interest, especially for grey-level imaging. In this paradigm, the two most important trees are the component-tree [53] and the tree of shapes [27]. The component-tree models the inclusion relation of the connected components of the successive threshold sets of the image, whereas the tree of shapes models the isolines of the image, seen as a topographic map. The tree of shapes is generally presented as a self-dual version of the component-tree.

Although both trees carry topological information related to the content of the modeled image, especially via the notion of connectedness, the available topological information remains incomplete and may sometimes be insufficient to perform high-level topological analysis of the modeled images. In particular, hierarchical structures are generally less informative than high-level topological invariants / descriptors, e.g. the homology groups / persistent homology [14]. Enriching these trees to allow the embedding of supplementary topological information is then a relevant purpose.

Then, we aim to investigate new hierarchical structures in the perimeter of partial partition modeling, to better understand and to improve the notions of component-tree and tree of shapes.

Table 1 Index of the principal notations

1.3 Contributions

In this article, which is an extended and improved version of the conference paper [36], we introduce a new family of hierarchical structures, including one DAG and three trees, namely:

• the graph of valued shapes;

• the tree of valued shapes;

• the complete tree of shapes;

• the topological tree of shapes;

dedicated to the modeling of grey-level images.

They aim to gather (i) connectedness / intensity information carried by component- (min- and max-) trees [53] and (ii) topological information carried by the adjacency tree, a classical graph-based topological invariant [49].

Basically, we first build a DAG which is composed by the min-tree and the max-tree (the two dual versions of the component-tree) of a grey-level image, and we enrich the nodes of these two trees by the adjacency tree at each grey-level, leading to the notion of a graph of valued shapes. Then, we establish that the graph of valued shapes can be turned into a tree by discarding some transitive, redundant edges. This leads to a simpler structure called tree of valued shapes. By factorizing some spatially equivalent nodes, we then define a more compact structure, called the complete tree of shapes. We establish that this complete tree of shapes can be reduced in two different ways, leading on the one hand to the usual tree of shapes and on the other hand to the new topological tree of shapes.

We provide a thorough description of these structures and we explicit their links with other usual hierarchies. We provide algorithmic solutions for building them. We also discuss on the links that exist between new structures and certain topological invariants and descriptors.

1.4 Organization of the Article

This article is organized as follows.

• Section 2 provides basic definitions and notations.

• Section 3 defines a collection of useful orders and gives the links between these orders and hierarchical graph-based objects (trees, forests...).

• Section 4 describes the hypotheses on the handled images.

• Section 5 provides the definitions of the classical notions of component-tree, valued component-tree, tree of shapes and adjacency tree in a unique formalism used to further define the new hierarchical structures.

• Section 6 is a description of the new hierarchical structures.

• Section 7 is a discussion about the links that exist between the new and the usual hierarchical structures.

• Section 8 deals with the algorithmic aspects of the construction of these new hierarchical structures by building upon the usual ones.

• Section 9 provides a discussion and focuses on the links that exist between the proposed hierarchies and other topological invariants and descriptors.

• Section 10 concludes the article.

For the sake of readability, the technical parts of the article are deported in appendix. In particular:

• Appendix A provides technical results on tree homeomorphism that allow to factorize various proofs that rely on similar hypotheses.

• Appendix B provides the proofs of the most important results, stated as “propositions”. (The proofs of other results stated as “properties” are less technical and left to the reader.)

Table 2 Index of secondary notations

2 Notations and Basic Notions

In this section, we recall usual notions and we introduce the associated notations. More specific notions and notations will be introduced in the next sections. For the sake of readability, they are gathered and indexed in Tables 1, 2. For the sake of coherence, some notations used in this article may sometimes differ from those used in [36].

The power set of a set $A$ is noted $2^A$. If $A$ is a finite set, we note $|A|$ the number of elements in $A$.

A (binary) relation $\propto$ on a set $A$ is a subset of $A\times A$. We note $a\propto b$ to express the fact that $(a,b) \in \ \propto$. A subrelation of $\propto$ is a subset of $\propto$. If $A$ is finite, the couple $(A,\propto )$ is a (directed) graph.

A function $f$ from $A$ to $B$ is a subset of $A\times B$ such that for all $a\in A$ there exists at most one $b\in B$ which satisfies $(a,b) \in f$. We note $b= f(a)$ to express the fact that $(a,b) \in f$. A function from $A$ to $A$ is a relation on $A$.

An application $f$ from $A$ to $B$ is a function such that for all $a\in A$ there exists $b\in B$ which satisfies $(a,b) \in f$. We note $b= f(a)$ to express the fact that $(a,b) \in f$. An application $f$ from $A$ to $A$ is a relation on $A$.

A function / application $f$ from $A$ to $B$ is noted $f: A\rightarrow B$. The restriction of $f$ to a subset $A' \subseteq A$ is noted $f_{\mid A'}$. If $f$ is bijective, we note $f^{-1}: B\rightarrow A$ its inverse function / application. If $f$ is not bijective, we define the reverse function / application $f^{-1}: 2^B\rightarrow 2^A$ associated to $f$ by $f^{-1}(C) = \{a\in A\mid f(a) \in C\}$. If $C= \{c\}$, we sometimes note $f^{-1}(c)$ instead of $f^{-1}(\{c\})$ for the sake of concision.

An equivalence relation ${\sim }_{}$ on $A$ is a relation on $A$ which is reflexive, transitive and symmetric. For any $a\in A$, the equivalence class of $a$ is noted $[a]_{{\sim }_{}}$. The quotient set of all the equivalence classes of $A$ with respect to ${\sim }_{}$ is noted $A/\mathord {{\sim }_{}}$.

An order relation $\sqsubseteq ^{}_{}$ on $A$ is a relation on $A$ which is reflexive, transitive and antisymmetric. We say that $(A,\sqsubseteq ^{}_{})$ is an ordered set.

The dual order relation $\sqsupseteq$ associated to $\sqsubseteq ^{}_{}$ is defined by $(a\sqsupseteq b) \Leftrightarrow (b\sqsubseteq ^{}_{} a)$. The strict order relation $\sqsubset$ associated to $\sqsubseteq ^{}_{}$ is defined by $(a\sqsubset b) \Leftrightarrow (a\sqsubseteq ^{}_{} b\wedge a\ne b)$.

For any $a\in A$ and any order $\sqsubseteq ^{}_{}$ we note $a_{\sqsubseteq ^{}_{}}^\uparrow = \{b\in A\mid a\sqsubseteq ^{}_{} b\}$ and $a_{\sqsubseteq ^{}_{}}^\downarrow = a_\sqsupseteq ^\uparrow$.

If $(A,\sqsubseteq ^{}_{})$ is an ordered set and $B\subseteq A$, we note $\sqsubseteq ^{}_{B}$ the induced order on $B$. (We may remove the subscript $_B$ when there is no ambiguity.)

If $(A,\sqsubseteq ^{}_{})$ is an ordered set, a suborder $\widehat{\sqsubseteq ^{}_{}}$ of $\sqsubseteq ^{}_{}$ is an order on $A$ which is a subset of $\sqsubseteq ^{}_{}$.

If $B\subseteq A$, we note $\bigvee ^{\sqsubseteq ^{}_{}} B$ (resp. $\bigwedge ^{\sqsubseteq ^{}_{}} B$) the supremum (resp. the infimum) of $B$ in $A$ with respect to $\sqsubseteq ^{}_{}$ when it exists. If $\bigvee ^{\sqsubseteq ^{}_{}} B\in A$ (resp. $\bigwedge ^{\sqsubseteq ^{}_{}} B\in A$), then it corresponds to the maximum (resp. the minimum) of $B$ with respect to $\sqsubseteq ^{}_{}$. We note $\bigtriangledown ^{\sqsubseteq ^{}_{}} B$ (resp. $\bigtriangleup ^{\sqsubseteq ^{}_{}} B$) the set of the maximal elements (resp. the set of the minimal elements) of $B$ with respect to $\sqsubseteq ^{}_{}$ when they exist. (We may remove the superscript $^{\sqsubseteq ^{}_{}}$ when there is no ambiguity.)

We say that $\sqsubseteq ^{}_{}$ is a total order (and that $(A,\sqsubseteq ^{}_{})$ is a totally ordered set) if for all $a, b\in A$, we have $a\sqsubseteq ^{}_{} b$ or $b\sqsubseteq ^{}_{} a$. We say that $\sqsubseteq ^{}_{}$ is a partial order (and that $(A,\sqsubseteq ^{}_{})$ is a partially ordered set) if $\sqsubseteq ^{}_{}$ is not a total order. If $(A,\sqsubseteq ^{}_{})$ is a totally ordered set and $a, b\in A$ with $a\sqsubseteq ^{}_{} b$, we note $\llbracket a,b\rrbracket _{\sqsubseteq ^{}_{}} = \{c\in A\mid a\sqsubseteq ^{}_{} c\sqsubseteq ^{}_{} b\}$ and $\rrbracket a,b\llbracket _{\sqsubseteq ^{}_{}} = \{c\in A\mid a\sqsubset c\sqsubset b\}$ (and we can combine both open and closed bound symbols to build ad hoc intervals). (We may remove the subscript $_{\sqsubseteq ^{}_{}}$ when there is no ambiguity.)

If the relation $\vartriangleleft ^{}_{}$ is the reflexive-transitive reduction of the order relation $\sqsubseteq ^{}_{}$, we note $\sqsubseteq ^{}_{} \ \searrow _{RT}\ \vartriangleleft ^{}_{}$ or $(A,\sqsubseteq ^{}_{}) \searrow _{RT}(A,\vartriangleleft ^{}_{})$. The relation $\vartriangleleft ^{}_{}$ is then called the Hasse relation associated to $\sqsubseteq ^{}_{}$ and $(A,\vartriangleleft ^{}_{})$ is called the Hasse diagram of $(A,\sqsubseteq ^{}_{})$. In the sequel, for each order relation noted $\sqsubseteq ^{}_{A}$ on $A$, the associated Hasse relation will be noted $\vartriangleleft ^{}_{A}$. If $A$ is finite, then the Hasse diagram $(A,\vartriangleleft ^{}_{})$ is a directed acyclic graph (DAG). Reversely, if $(A,\vartriangleleft ^{}_{})$ is a DAG, then its reflexive-transitive closure $\sqsubseteq ^{}_{}$ is an order relation on $A$.

If $\mathfrak G= (A,\propto )$ is a directed graph and $a\in A$, the inner (resp. outer) degree of $a$, noted $\partial ^{-}_{\propto }(a)$ (resp. $\partial ^{+}_{\propto }(a)$) is equal to $|\{b\in A\mid b\propto a\}|$ (resp. $|\{b\in A\mid a\propto b\}|$). The inner (resp. outer) degree of a graph $\mathfrak G= (A,\propto )$, noted $\partial ^{-}_{}(\mathfrak G)$ or $\partial ^{-}_{}(\propto )$ (resp. $\partial ^{+}_{}(\mathfrak G)$ or $\partial ^{+}_{}(\propto )$) is equal to $\bigvee ^\le \{\partial ^{-}_{\propto }(a)\}_{a\in A}$ (resp. $\bigvee ^\le \{\partial ^{+}_{\propto }(a)\}_{a\in A}$).

If $(A,\propto _A)$ is a (directed) graph, we say that $(B, \propto _B)$ is an induced subgraph of $(A,\propto _A)$, and we note $(B, \propto _B) \Subset (A,\propto _A)$ if $B\subseteq A$ and $\propto _B\ = \ \propto _A\cap \ B\times B$. If $\widehat{\propto }_A$ is a subrelation of $\propto _A$, we say that $(A,\widehat{\propto }_A)$ is a partial graph of $(A,\propto _A)$.

3 Orders and Trees

In this section, we introduce four families of orders, which will be used in the sequel of this study. These families of orders are: the total orders, the piecewise total orders, the hierarchical orders and the piecewise hierarchical orders. In particular, the Hasse diagrams related to all these orders are tree-based structures: degenerate trees, degenerate forests, trees and forests, respectively. We state the links between these families (see Fig. 1 for an overview). At the end of this section, we also introduce two important notions related to suborders of a (piecewise) hierarchical order: first, the notion of maximal piecewise total suborders, which will be important to establish the links between morphological hierarchies and persistent homology (Sect. 9.2); second, the notion of induced piecewise total suborders, which will be the cornerstone to explicit the (quasi-)homeomorphisms that exist between various morphological hierarchies (Appendix A).

Fig. 1

Lattice structure of the inclusion links between the four kinds of (piecewise) total orders and (piecewise) hierarchical orders, and associated structure of the Hasse relations (trees vs. forests, degenerate vs. non-degenerate)

Fig. 2

A set $A$ endowed with various orders, represented via their Hasse relation / function. a A degenerate tree $(A,\vartriangleleft ^{}_{0})$ corresponding to a total order $\sqsubseteq ^{}_{0}$ on $A$. b A tree $(A,\vartriangleleft ^{}_{1})$ corresponding to a hierarchical order $\sqsubseteq ^{}_{1}$ on A. c A forest $(A,\vartriangleleft ^{}_{2})$ corresponding to a piecewise hierarchical order $\sqsubseteq ^{}_{2}$ on $A$ which is a suborder of $\sqsubseteq ^{}_{1}$. d A degenerate forest $(A,\vartriangleleft ^{}_{3})$ corresponding to a (non-maximal) piecewise total order $\sqsubseteq ^{}_{3}$ on $A$ which is a suborder of $\sqsubseteq ^{}_{2}$. e A degenerate forest $(A,\vartriangleleft ^{}_{4})$ corresponding to a piecewise total order $\sqsubseteq ^{}_{4}$ on $A$ which is a maximal piecewise total suborder of $\sqsubseteq ^{}_{1}$. f A degenerate forest $(A,\vartriangleleft ^{}_{5})$ corresponding to a piecewise total order $\sqsubseteq ^{}_{5}$ on $A$ which is the induced piecewise total suborder of $\sqsubseteq ^{}_{1}$. The round nodes depict the elements of $A$. The arrows depict the Hasse relations $\vartriangleleft ^{}_{i}$. The green nodes are maximal elements (maxima in (a,b)). The red nodes are minimal elements (minimum in (a)). The yellow nodes are simultaneously minimal and maximal elements (Color figure online)

Definition 1

(Piecewise hierarchical order) Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ an order on $A$ with $\sqsubseteq ^{}_{} \ \searrow _{RT}\ \vartriangleleft ^{}_{}$. Let us suppose that $\partial ^{+}_{}(\vartriangleleft ^{}_{}) \le 1$. We then say that $\sqsubseteq ^{}_{}$ is a piecewise hierarchical order on $A$.

Remark 2

If $\sqsubseteq ^{}_{}$ is a piecewise hierarchical order on $A$, then $(A,\vartriangleleft ^{}_{})$ is a forest, such as defined in the graph theory literature.

An example of piecewise hierarchical order depicted by its forest is illustrated in Fig. 2c.

Property 3

Let $\sqsubseteq ^{}_{}$ be a piecewise hierarchical order on $A$. For any $a\in A$, $(a_{\sqsubseteq ^{}_{}}^\uparrow ,\sqsubseteq ^{}_{})$ is a totally ordered set.

Property 4

Let $A$ be a finite set. Let $\sqsubseteq ^{}_{1}$ and $\sqsubseteq ^{}_{2}$ be two piecewise hierarchical orders on $A$, and $\vartriangleleft ^{}_{1}$, $\vartriangleleft ^{}_{2}$ their respective Hasse relations. We have

$$\begin{aligned} \sqsubseteq ^{}_{2} \ \subseteq \ \sqsubseteq ^{}_{1} \ \Longleftrightarrow \ \vartriangleleft ^{}_{2}\ \subseteq \ \vartriangleleft ^{}_{1} \end{aligned}$$

(1)

i.e. $\sqsubseteq ^{}_{2}$ is a suborder of $\sqsubseteq ^{}_{1}$ iff the forest $(A,\vartriangleleft ^{}_{2})$ is a partial graph of the forest $(A,\vartriangleleft ^{}_{1})$.

Definition 5

(Hasse function) Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ a piecewise hierarchical order on $A$. The Hasse relation $\vartriangleleft ^{}_{}$ associated to $\sqsubseteq ^{}_{}$ is also a function from $A$ to $A$. This function is called the Hasse function and it is noted $\zeta ^{}_{\sqsubseteq ^{}_{}}: A\rightarrow A$ or $\zeta ^{}_{\vartriangleleft ^{}_{}}: A\rightarrow A$. It is defined by

$$\begin{aligned} \zeta ^{}_{\sqsubseteq ^{}_{}}(a) = b\Longleftrightarrow a\vartriangleleft ^{}_{} b\end{aligned}$$

(2)

In particular, this function is a surjective application from $A{\setminus } \bigtriangledown ^{\sqsubseteq ^{}_{}} A$ to $A{\setminus } \bigtriangleup ^{\sqsubseteq ^{}_{}} A$. We will note $Z_{\vartriangleleft ^{}_{}}: 2^A\rightarrow 2^A$ the application defined by $Z_{\vartriangleleft ^{}_{}}(B) = \zeta ^{-1}_{\vartriangleleft ^{}_{}}(B)$.

Definition 6

(Hierarchical order) Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ a piecewise hierarchical order on $A$. If $(A,\sqsubseteq ^{}_{})$ admits a maximum, then we say that $\sqsubseteq ^{}_{}$ is a hierarchical order. In particular, the Hasse function $\zeta ^{}_{\sqsubseteq ^{}_{}}$ is then a surjective application from $A{\setminus } \{\bigvee ^{\sqsubseteq ^{}_{}} A\}$ to $A{\setminus } \bigtriangleup ^{\sqsubseteq ^{}_{}} A$.

Remark 7

If $\sqsubseteq ^{}_{}$ is a hierarchical order on $A$, then $(A,\vartriangleleft ^{}_{})$ is a tree, such as defined in the graph theory literature. (In particular, a tree is a forest.)

An example of hierarchical order depicted by its tree is illustrated in Fig. 2b.

Remark 8

Let $A$ be a finite set. Let $\sqsubseteq ^{}_{1}$ be a hierarchical order and $\sqsubseteq ^{}_{2}$ a piecewise hierarchical order on $A$, and $\vartriangleleft ^{}_{1}$ and $\vartriangleleft ^{}_{2}$ their respective Hasse relations. Eq. (1) holds, i.e. $\sqsubseteq ^{}_{2}$ is a suborder of $\sqsubseteq ^{}_{1}$ iff the forest $(A,\vartriangleleft ^{}_{2})$ is a partial graph of the tree $(A,\vartriangleleft ^{}_{1})$.

Figure 2b, c provides an example of a forest (c) which is a partial graph of a tree (b), and equivalently a piecewise hierarchical order which is a suborder of a hierarchical order.

Definition 9

(Piecewise total order) Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ a piecewise hierarchical order on $A$. If the Hasse function $\zeta ^{}_{\sqsubseteq ^{}_{}}$ is an injective (and then bijective) application from $A{\setminus } \bigtriangledown ^{\sqsubseteq ^{}_{}} A$ to $A{\setminus } \bigtriangleup ^{\sqsubseteq ^{}_{}} A$ or, equivalently, if $\partial ^{-}_{}(\vartriangleleft ^{}_{}) \le 1$, then we say that $\sqsubseteq ^{}_{}$ is a piecewise total order.

Property 10

Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ a piecewise total order on $A$. For any $a\in A$, and a fortiori for any $a\in \bigtriangledown ^{\sqsubseteq ^{}_{}} A$, $(a^\downarrow _{\sqsubseteq ^{}_{}}, \sqsubseteq ^{}_{})$ is a totally ordered set. In particular, if $(A,\sqsubseteq ^{}_{})$ admits a maximum, then $\sqsubseteq ^{}_{}$ is a total order on $A$.

Remark 11

If $\sqsubseteq ^{}_{}$ is a total order on $A$, then $(A,\vartriangleleft ^{}_{})$ is a degenerate tree, such as defined in the graph theory literature. If $\sqsubseteq ^{}_{}$ is a piecewise total order on $A$, then $(A,\vartriangleleft ^{}_{})$ is a forest of degenerate trees (or degenerate forest, for brief), such as defined in the graph theory literature.

An example of total order depicted by its degenerate tree is illustrated in Fig. 2a. An example of piecewise total order depicted by its degenerate forest is illustrated in Fig. 2d.

Remark 12

Let $A$ be a finite set. Let $\sqsubseteq ^{}_{1}$ be a piecewise hierarchical order and $\sqsubseteq ^{}_{2}$ a piecewise total order on $A$, and $\vartriangleleft ^{}_{1}$ and $\vartriangleleft ^{}_{2}$ their respective Hasse relations. Eq. (1) holds, i.e. $\sqsubseteq ^{}_{2}$ is a suborder of $\sqsubseteq ^{}_{1}$ iff the degenerate forest $(A,\vartriangleleft ^{}_{2})$ is a partial graph of the forest $(A,\vartriangleleft ^{}_{1})$.

Figure 2c, d provides an example of a degenerate forest (d) which is a partial graph of a forest (c), and equivalently a piecewise total order which is a suborder of a piecewise hierarchical order.

Definition 13

(Maximal piecewise total suborders) Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ a piecewise hierarchical order on $A$. Let $\widehat{\sqsubseteq ^{}_{}}$ be a piecewise total order on $A$ such that $\zeta ^{}_{\widehat{\sqsubseteq ^{}_{}}} \ \subseteq \ \zeta ^{}_{\sqsubseteq ^{}_{}}$. We say that $\widehat{\sqsubseteq ^{}_{}}$ is a maximal piecewise total suborder of $\sqsubseteq ^{}_{}$ if for any piecewise total order $\widetilde{\sqsubseteq ^{}_{}}$ on $A$ such that $\zeta ^{}_{\widehat{\sqsubseteq ^{}_{}}} \subseteq \zeta ^{}_{\widetilde{\sqsubseteq ^{}_{}}} \subseteq \ \zeta ^{}_{\sqsubseteq ^{}_{}}$, we have $\widehat{\sqsubseteq ^{}_{}} = \widetilde{\sqsubseteq ^{}_{}}$. We note $\mathcal M(\sqsubseteq ^{}_{})$ the set of all the Hasse functions of maximal piecewise total suborders of $\sqsubseteq ^{}_{}$.

Remark 14

Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ a piecewise hierarchical order on $A$ with $\sqsubseteq ^{}_{} \ \searrow _{RT}\ \vartriangleleft ^{}_{}$. Let $\widehat{\sqsubseteq ^{}_{}}$ be a maximal piecewise total suborder of $\sqsubseteq ^{}_{}$ with $\widehat{\sqsubseteq ^{}_{}} \searrow _{RT}\widehat{\vartriangleleft ^{}_{}}$. The partial graph $(A,\widehat{\vartriangleleft ^{}_{}})$ of $(A,\vartriangleleft ^{}_{})$ is a degenerate forest and it is maximal for this property.

Figure 2e provides an example of a degenerate forest corresponding to a piecewise total order which is a maximal piecewise total suborder of the piecewise hierarchical order corresponding to the forest of Fig. 2b. (Note that the degenerate forest of Fig. 2d is not a maximal piecewise total suborder of the piecewise hierarchical order corresponding to the forest of Fig. 2b since it is a (strict) partial graph of the degenerate forest of Fig. 2e.)

Property 15

Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ a piecewise hierarchical order on $A$ with $\sqsubseteq ^{}_{} \ \searrow _{RT}\ \vartriangleleft ^{}_{}$. We have

$$\begin{aligned} |\mathcal M(\sqsubseteq ^{}_{})| = \mathop {\prod }\limits _{a\in A\setminus \bigtriangleup ^{\sqsubseteq ^{}_{}} A} \partial ^{-}_{\vartriangleleft ^{}_{}}(a) \end{aligned}$$

(3)

Property 16

Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ a piecewise hierarchical order on $A$. We have

$$\begin{aligned} \zeta ^{}_{\sqsubseteq ^{}_{}} = \bigvee ^\subseteq \mathcal M(\sqsubseteq ^{}_{}) = \bigcup \mathcal M(\sqsubseteq ^{}_{}) \end{aligned}$$

(4)

Remark 17

If $\sqsubseteq ^{}_{}$ is a piecewise total order, then we have $\mathcal M(\sqsubseteq ^{}_{}) = \{\zeta ^{}_{\sqsubseteq ^{}_{}}\}$. Otherwise, we have $\zeta ^{}_{\sqsubseteq ^{}_{}} \notin \mathcal M(\sqsubseteq ^{}_{})$ and $\zeta ^{}_{\sqsubseteq ^{}_{}}$ is then defined as a supremum, but not a maximum.

Definition 18

(Induced piecewise total suborder) Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ a piecewise hierarchical order on $A$. The piecewise total suborder induced by $\sqsubseteq ^{}_{}$, noted , is defined by its Hasse function as

(5)

Figure 2f provides an example of a degenerate forest corresponding to a piecewise total order which is the induced piecewise total suborder of the piecewise hierarchical order corresponding to the forest of Fig. 2b.

Remark 19

If $\sqsubseteq ^{}_{}$ is a piecewise total order, then we have . Otherwise, we have and is then defined as an infimum, but not a minimum.

Property 20

Let $A$ be a finite set and $\sqsubseteq ^{}_{}$ a piecewise hierarchical order on $A$. For any $\zeta ^{}_{\widehat{\sqsubseteq ^{}_{}}} \in \mathcal M(\sqsubseteq ^{}_{})$, we have

(6)

The following three definitions are given for trees, but they also hold for forests. (The usual notion of homeomorphism is generally defined on graphs, but it is not required here to provide such a general definition.)

Definition 21

(Elementary homeomorphism on trees) Let ${\mathfrak T}_{A} = (A,\vartriangleleft ^{}_{A})$ and ${\mathfrak T}_{B} = (B,\vartriangleleft ^{}_{B})$ be two trees associated to the hierarchical orders $\sqsubseteq ^{}_{A}$ and $\sqsubseteq ^{}_{B}$, respectively. We say that there is an elementary decreasing homeomorphism from ${\mathfrak T}_{A}$ to ${\mathfrak T}_{B}$, and we write ${\mathfrak T}_{A} \searrow _{EH}{\mathfrak T}_{B}$, if there exist $a, b, c\in A$ with $a\vartriangleleft ^{}_{A} b\vartriangleleft ^{}_{A} c$, such that

$$\begin{aligned}&B= A\setminus \{b\} \end{aligned}$$

(7)

$$\begin{aligned}&Z_{\vartriangleleft ^{}_{A}}(b) = \{a\} \end{aligned}$$

(8)

$$\begin{aligned}&\forall x\in B\setminus \Big \{a, \bigvee ^{\sqsubseteq ^{}_{A}}A\Big \}, \zeta ^{}_{\vartriangleleft ^{}_{B}}(x) = \zeta ^{}_{\vartriangleleft ^{}_{A}}(x) \end{aligned}$$

(9)

$$\begin{aligned}&\zeta ^{}_{\vartriangleleft ^{}_{B}}(a) = \zeta ^{}_{\vartriangleleft ^{}_{A}}(\zeta ^{}_{\vartriangleleft ^{}_{A}}(a)) = c\end{aligned}$$

(10)

We say that there is an elementary increasing homeomorphism from ${\mathfrak T}_{A}$ to ${\mathfrak T}_{B}$ if there exists a elementary decreasing homeomorphism from ${\mathfrak T}_{B}$ to ${\mathfrak T}_{A}$.

Definition 22

(Homeomorphism on trees) Let ${\mathfrak T}_{A} = (A,\vartriangleleft ^{}_{A})$ and ${\mathfrak T}_{B} = (B,\vartriangleleft ^{}_{B})$ be two trees. We say that there is a decreasing homeomorphism from ${\mathfrak T}_{A}$ to ${\mathfrak T}_{B}$, and we write ${\mathfrak T}_{A} \searrow _{H}{\mathfrak T}_{B}$, if there exists a finite sequence of trees $\langle {\mathfrak T}_{i} \rangle _{i=1}^t$ ($t\ge 1$) such that ${\mathfrak T}_{1} = {\mathfrak T}_{A}$, ${\mathfrak T}_{t} = {\mathfrak T}_{B}$ and for any $1 \le i\le t-1$, we have ${\mathfrak T}_{i} \searrow _{EH}{\mathfrak T}_{i+1}$. We say that there is an increasing homeomorphism from ${\mathfrak T}_{A}$ to ${\mathfrak T}_{B}$ if there exists a decreasing homeomorphism from ${\mathfrak T}_{B}$ to ${\mathfrak T}_{A}$.

Fig. 3

a A tree ${\mathfrak T}_{A}$ corresponding to the one depicted in Fig. 2b. b A tree ${\mathfrak T}_{B}$ such that there is a decreasing homeomorphism from ${\mathfrak T}_{A}$ to ${\mathfrak T}_{B}$ (composed here as a sequence of 7 elementary decreasing homeomorphisms). c A tree ${\mathfrak T}_{C}$ such that there is a decreasing quasi-homeomorphism from ${\mathfrak T}_{A}$ to ${\mathfrak T}_{C}$

Definition 23

(Quasi-homeomorphism on trees) Let ${\mathfrak T}_{A} = (A,\vartriangleleft ^{}_{A})$ and ${\mathfrak T}_{B} = (B,\vartriangleleft ^{}_{B})$ be two trees associated to the hierarchical orders $\sqsubseteq ^{}_{A}$ and $\sqsubseteq ^{}_{B}$, respectively. We say that there is a decreasing quasi-homeomorphism from ${\mathfrak T}_{A}$ to ${\mathfrak T}_{B}$, and we write ${\mathfrak T}_{A} \searrow _{QH}{\mathfrak T}_{B}$, if ${\mathfrak T}_{A} \searrow _{H}{\mathfrak T}_{B}$ or ${\mathfrak T}_{A} \searrow _{H}\widehat{{\mathfrak T}_{B}}$ with $\widehat{{\mathfrak T}_{B}} = (B\cup \{\varepsilon \},\vartriangleleft ^{}_{B} \! \cup \ \{(\bigvee ^{\sqsubseteq ^{}_{B}} B,\varepsilon )\})$ for a given element $\varepsilon \notin B$. We say that there is an increasing quasi-homeomorphism from ${\mathfrak T}_{A}$ to ${\mathfrak T}_{B}$ if there exists a decreasing quasi-homeomorphism from ${\mathfrak T}_{B}$ to ${\mathfrak T}_{A}$.

The notions of homeomorphism and quasi-homeomorphism are illustrated in Fig. 3.

Remark 24

The notion of quasi-homeomorphism authorizes the existence of an extra edge located at the root of the tree. In practice, two trees linked by a quasi-homeomorphism are then “nearly homeomorphic”, since the location of this extra edge at an extremity of the tree may allow to symbolically omit it for further manipulations. The notion of quasi-homeomorphism will be useful in particular when we will establish some structural links between various morphological hierarchies.

Definition 25

(Isomorphism on graphs) Let $\mathfrak G_A= (A,\propto _A)$ and $\mathfrak G_B= (B,\propto _B)$ be two graphs. We say that there is an isomorphism between $\mathfrak G_A$ and $\mathfrak G_B$, and we write $\mathfrak G_A\equiv \mathfrak G_B$, if there exists a bijective application $\gamma : A\rightarrow B$ and for any $a, b\in A$

$$\begin{aligned} a\propto _{A} b\Longleftrightarrow \gamma (a) \propto _B\gamma (b) \end{aligned}$$

(11)

Remark 26

Let ${\mathfrak T}_{A}, {\mathfrak T}_{B}, {\mathfrak T}_{C}$ be trees. If there is a (decreasing or increasing) homeomorphism from ${\mathfrak T}_{A}$ to ${\mathfrak T}_{B}$ and if there is an isomorphism between ${\mathfrak T}_{B}$ and ${\mathfrak T}_{C}$ then, by abuse of language, we will also say that there is a (decreasing or increasing) homeomorphism from ${\mathfrak T}_{A}$ to ${\mathfrak T}_{C}$.

4 Definitions and Hypotheses

In this section, we provide the hypotheses under which we define and handle the objects considered in this study.

Let $\mathbb U$ be an unbounded space endowed with a topological structure. It satisfies the following two hypotheses:

• (H1) the topology defined on $\mathbb U$ provides a notion of connectedness (and the derived notion of connected component);

• (H2) the topology defined on $\mathbb U$ is compliant with the Jordan-Brouwer separation property [7, 59].

In practice, we will consider $\mathbb U$ as a digital space, i.e. $\mathbb Z^d$ ($d\ge 1$) endowed with the usual digital topology framework [50] (or more restrictive frameworks, e.g. the well-composedness [23]). It was proved that the framework of cubical complexes [26] and more generally the continuous topology on $\mathbb R^d$ [25] are indeed compliant with digital topology.

As a consequence, although our purpose and associated algorithms will deal with digital topology ($\mathbb U= \mathbb Z^d$)—with straightforward adaptations to other digital grids or complex spaces—we will establish our theoretical results in a continuous framework ($\mathbb U= \mathbb R^d$).

4.1 Connected Components and Jordan Manifolds

Let $\varLambda ^{}_{} \subseteq \mathbb U$ be a (closed or open) subset of $\mathbb U$. If $\varLambda ^{}_{} \ne \emptyset$, the connected components (i.e. the maximally connected subsets) of $\varLambda ^{}_{}$ form a partition of $\varLambda ^{}_{}$, noted $\varPi [\varLambda ^{}_{}]$. If $\varLambda ^{}_{} = \emptyset$, we set $\varPi [\varLambda ^{}_{}] = \emptyset$.

From now on, we only consider some sets $\varLambda ^{}_{} \subseteq \mathbb U$ which are either empty or composed by a finite number $k\ge 1$ of connected components. In that second case, we assume that at least $k-1$ connected components are bounded and at most one is unbounded. A bounded connected component $X$ of $\varLambda ^{}_{}$ is bounded by one external Jordan manifold (hypersurface) ${\mathcal J}^{+}_{}(X)$ and possibly by $t\ge 0$ internal Jordan manifold(s) ${\mathcal J}^{-}_{i}(X)$ ($1 \le i\le t$) [35]. An unbounded connected component $X$ of $\varLambda ^{}_{}$ is not bounded by any external (Jordan or not) manifold and is possibly bounded by $t\ge 0$ internal Jordan manifold(s) ${\mathcal J}^{-}_{i}(X)$ ($1 \le i\le t$). In both cases, the $t$ internal Jordan manifolds ${\mathcal J}^{-}_{i}(X)$ are the external Jordan manifolds that bound the connected components that form the “holes” of $X$. Note that if $X$ is closed (resp. open), then the putative manifolds ${\mathcal J}^{+}_{}(X)$ and ${\mathcal J}^{-}_{i}(X)$ ($1 \le i\le t$) are inside (resp. outside) of $X$.

Let ${\mathcal J}^{}_{}$ be a Jordan manifold. We note $\mathbb U^+({\mathcal J}^{}_{})$ (resp. ) and $\mathbb U^-({\mathcal J}^{}_{})$ (resp. ) the parts of $\mathbb U$ that lie outside and inside of ${\mathcal J}^{}_{}$ and that include (resp. exclude) ${\mathcal J}^{}_{}$, respectively.

Let $X$ be a connected component of $\varLambda ^{}_{}$. We define the hole-closed set $\tau (X)$ associated to $X$ as

$$\begin{aligned} \tau (X) = X\cup \bigcup _{i=1}^t\mathbb U^-({\mathcal J}^{-}_{i}(X)) \end{aligned}$$

(12)

and this definition can be generalized to $\varLambda ^{}_{} \subseteq \mathbb U$ with respect to its $k$ connected components $X_j$ ($1 \le j\le k$) as

$$\begin{aligned} \tau (\varLambda ^{}_{}) = \bigcup _{j=1}^k\tau (X_j) \end{aligned}$$

(13)

Note in particular that $\tau (\emptyset ) = \emptyset$ and $\tau (\varLambda ^{}_{}) = \mathbb U$ whenever $\varLambda ^{}_{}$ is unbounded (with, in particular, $\tau (\mathbb U) = \mathbb U$).

4.2 Stacks and Grey-Level Images

Let $\mathbb K$ be a non-empty set endowed with a total order $\leqslant _\mathbb K$ with $\leqslant _\mathbb K\ \searrow _{RT}\ \vartriangleleft ^{}_{\mathbb K}$. Let $\mathbb V\subseteq \mathbb K$ be a non-empty finite subset of $\mathbb K$ and $\leqslant _\mathbb V$ (or simply $\leqslant$) the total order induced by $\leqslant _\mathbb K$ on $\mathbb V$ with $\leqslant _\mathbb V\ \searrow _{RT}\ \vartriangleleft ^{}_{\mathbb V}$ (or simply $\vartriangleleft ^{}_{}$). We set $\bot = \bigwedge ^\leqslant \mathbb V$ and $\top = \bigvee ^\leqslant \mathbb V$. We set $\varDelta = |\mathbb V|$.

We note $\leqslant ^\circ \ = \ \leqslant$ and $\leqslant ^\bullet \ = \ \geqslant$ with $\leqslant ^\circ \ \searrow _{RT}\ \vartriangleleft ^{\circ }_{}$ and $\leqslant ^\bullet \ \searrow _{RT}\ \vartriangleleft ^{\bullet }_{}$. For any $v\in \mathbb V{\setminus } \{\top \}$ (resp. $\mathbb V{\setminus } \{\bot \}$), we note ${\sigma }^{\circ }(v) = \zeta ^{}_{\vartriangleleft ^{\circ }_{}}(v)$ (resp. ${\sigma }^{\bullet }(v) = \zeta ^{}_{\vartriangleleft ^{\bullet }_{}}(v)$).

Let $\langle \varLambda ^{\circ }_{v} \rangle _{v\in \mathbb V}$ be a non-empty finite sequence of closed subsets of $\mathbb U$, bounded by Jordan manifolds, such that

• $\varLambda ^{\circ }_{\bot } = \mathbb U$

• $\varLambda ^{\circ }_{\top } = \emptyset$

• $\forall v\in \mathbb V, v> \bot \Rightarrow \varLambda ^{\circ }_{v}$ is bounded

• $\forall u, v\in \mathbb V, u< v\Rightarrow \varLambda ^{\circ }_{v} \subset \varLambda ^{\circ }_{u}$

From this sequence, we can build the complement sequence $\langle \varLambda ^{\bullet }_{v} \rangle _{v\in \mathbb V}$ of open subsets of $\mathbb U$ bounded by Jordan manifolds, such that for all $v\in \mathbb V$, we have $\varLambda ^{\bullet }_{v} = \overline{\varLambda ^{\circ }_{v}} = \mathbb U{\setminus } \varLambda ^{\circ }_{v}$. It is plain that we have

• $\varLambda ^{\bullet }_{\bot } = \emptyset$

• $\varLambda ^{\bullet }_{\top } = \mathbb U$

• $\forall v\in \mathbb V, v> \bot \Rightarrow \varLambda ^{\circ }_{v}$ is unbounded

• $\forall u, v\in \mathbb V, u< v\Rightarrow \varLambda ^{\bullet }_{u} \subset \varLambda ^{\bullet }_{v}$

Both kinds of sequences will be also called stacks.

Definition 27

Let $\mathcal F: \mathbb U\rightarrow \mathbb V$ be the application defined, for any $\textbf{x} \in \mathbb U$, by

$$\begin{aligned} \mathcal F(\textbf{x})&= \bigvee ^{\leqslant ^\circ } \{v\in \mathbb V\mid \textbf{x} \in \varLambda ^{\circ }_{v}\} \end{aligned}$$

(14)

$$\begin{aligned}&= {\sigma }^{\bullet }\Big ( \bigvee ^{\leqslant ^\bullet } \{v\in \mathbb V\mid \textbf{x} \in \varLambda ^{\bullet }_{v}\}\Big ) \end{aligned}$$

(15)

This application can be seen as a grey-level image defined on $\mathbb U$ and taking its values in $\mathbb V$. In this context, the stack $\langle \varLambda ^{\circ }_{v} \rangle _{v\in \mathbb V}$ (resp. $\langle \varLambda ^{\bullet }_{v} \rangle _{v\in \mathbb V}$) defines the set of the upper (resp. lower) threshold sets of the image associated to $\mathcal F$

$$\begin{aligned} \varLambda ^{\circ }_{v}&= \{ \textbf{x} \in \mathbb U\mid v\leqslant ^\circ \mathcal F(\textbf{x})\} \end{aligned}$$

(16)

$$\begin{aligned} \varLambda ^{\bullet }_{v}&= \{ \textbf{x} \in \mathbb U\mid {\sigma }^{\bullet }(v) \leqslant ^\bullet \mathcal F(\textbf{x}) \} \end{aligned}$$

(17)

The notions of stacks and image are illustrated in Fig. 4.

Fig. 4

a An application / grey-level image $\mathcal F:\mathbb U\rightarrow \mathbb V$. Here we have $\mathbb U= \mathbb Z^2$ endowed with the digital topology, and $\mathbb V= \llbracket 0,7\rrbracket \subset \mathbb Z$. We then have $\bot = 0$ and $\top = 7$. Note that for any $\textbf{x} \in \mathbb U$ not depicted in this finite illustration, we have $\mathcal F(\textbf{x}) = 0$. b–i The two stacks composing the threshold sets of $\mathcal F$: the closed (resp. open) subsets $\varLambda ^{\circ }_{v}$ in white ($\varLambda ^{\bullet }_{v}$ in black), for $v= 0$ (b) to 7 (i). In (b) (resp. in (c–i)), the unbounded set $\varLambda ^{\circ }_{0}$, in white (resp. $\varLambda ^{\bullet }_{v}$, in black), is partly depicted

5 Usual Hierarchical Structures

In this section, we recall some usual hierarchical structures: (valued) component-trees, adjacency tree and tree of shapes. We define these trees in a unified formalism in order to further ease their handling and to facilitate the unifying study between them and with the new hierarchical structures introduced in Sect. 6.

Let $\langle \varLambda ^{\circ }_{v} \rangle _{v\in \mathbb V}$ with $\varLambda ^{\bullet }_{v} = \overline{\varLambda ^{\circ }_{v}} = \mathbb U{\setminus } \varLambda ^{\circ }_{v}$ for all $v\in \mathbb V$, and $\mathcal F: \mathbb U\rightarrow \mathbb V$ be such as defined in Sect. 4.2. In the sequel, $\star$ stands for both $\circ$ and $\bullet$.

From now on, when dealing with space and time costs, we will assume that $\mathbb U$ is discrete and that for any $v> \bot$, we have $|\varLambda ^{\circ }_{v}| \le n$. In particular, $n$ will be considered as the size of the finite support $\mathbb S{}{} \subset \mathbb U$ of the image.

5.1 Component-Trees

The definitions of (valued) component-trees given in this section require hypothesis (H1) but not hypothesis (H2). Of course, they remain valid when (H2) holds, and we will consider them in this context.

5.1.1 Min-tree and Max-tree

For any $v\in \mathbb V$, we set

$$\begin{aligned} \varTheta ^{\star }_{v} = \varPi [\varLambda ^{\star }_{v} ] \end{aligned}$$

(18)

i.e. $\varTheta ^{\star }_{v}$ is the partition of the connected components of $\varLambda ^{\star }_{v}$. We then define

$$\begin{aligned} \varTheta ^{\star }_{} = \bigcup _{v\in {\mathbb V}} \varTheta ^{\star }_{v} \end{aligned}$$

(19)

and

$$\begin{aligned} \varTheta ^{}_{} = \varTheta ^{\circ }_{} \cup \varTheta ^{\bullet }_{} \end{aligned}$$

(20)

We consider the two applications ${{\square }}: \varTheta ^{}_{} \rightarrow \{\circ , \bullet \}$ and $\blacksquare : \varTheta ^{}_{} {\rightarrow } \{\circ , \bullet \}$ defined such that $X\in \varTheta ^{{\square }(X)}_{}$ and $X\notin \varTheta ^{\blacksquare (X)}_{}$. When there is no ambiguity, we simply write ${\square }$ (resp. $\blacksquare$) instead of ${\square }(X)$ (resp. $\blacksquare (X)$).

Remark 28

The only element that belongs to both $\varTheta ^{\circ }_{}$ and $\varTheta ^{\bullet }_{}$ is $\mathbb U$. By abuse of definition, we consider that we may have ${\square }(\mathbb U) = \circ$ or $\bullet$ and $\blacksquare (\mathbb U) = \circ$ or $\bullet$.

Remark 29

An element $X\in \varTheta ^{{\square }}_{}$ may belong to many sets $\varTheta ^{\square }_{v}$.

Property 30

We have

$$\begin{aligned} |\varTheta ^{\star }_{}|&\le \sum _{v\in \mathbb V} |\varTheta ^{\star }_{v}| \end{aligned}$$

(21)

$$\begin{aligned} |\varTheta ^{}_{}|&= |\varTheta ^{\circ }_{}| + |\varTheta ^{\bullet }_{}| - 1 \end{aligned}$$

(22)

We define the partial order(s) $\sqsubseteq ^{}_{\varTheta ^{\star }_{}}$ on $\varTheta ^{\star }_{}$ as

$$\begin{aligned} X\sqsubseteq ^{}_{\varTheta ^{\star }_{}} Y\Longleftrightarrow X\subseteq Y\end{aligned}$$

(23)

with $\sqsubseteq ^{}_{\varTheta ^{\star }_{}} \searrow _{RT}\ \vartriangleleft ^{}_{\varTheta ^{\star }_{}}$

Fig. 5

Component-trees of the grey-level image $\mathcal F$ of Fig. 4. Left: max-tree. Right: min-tree. Each node (square) corresponds to an element $X$ of $\varTheta ^{{\square }}_{}$. The white part of the node corresponds to $X$. The blue-bordered nodes correspond to unbounded $X$. The nodes are organised with respect to the values (threshold sets) $v\in \mathbb V$ at which they are generated. The values of $\mathbb V$ are depicted on the left (round boxes). Since an element $X\in \varTheta ^{{\square }}_{}$ may correspond to threshold sets at many values, it is depicted at the level of the value $\omega ^{{\varTheta ^{{\square }}_{}}}_{X}$, see Eq. (26). The green arrows correspond to the $\vartriangleleft ^{}_{\varTheta ^{\star }_{}}$ relations (Color figure online)

Fig. 6

Valued component-trees of the grey-level image $\mathcal F$ of Fig. 4. Left: valued max-tree. Right: valued min-tree. Each node (square) corresponds to an element $K= (X,v)$ of $\varXi ^{{\square }}_{}$. The white part of the node corresponds to $X$. The blue-bordered nodes correspond to unbounded $X$. The nodes are organised with respect to the values (threshold sets) $v\in \mathbb V$ at which they are generated. The values of $\mathbb V$ are depicted on the left (round boxes). The green arrow correspond to the $\vartriangleleft ^{}_{\varXi ^{\star }_{}}$ relations (Color figure online)

Definition 31

(Component-tree [53]) The tree ${\mathfrak T}_{\varTheta ^{\star }_{}} = (\varTheta ^{\star }_{},\vartriangleleft ^{}_{\varTheta ^{\star }_{}})$ is called the component-tree of $\langle \varLambda ^{\star }_{v} \rangle _{v\in \mathbb V}$.

Definition 32

(Min-tree, max-tree [53]) The component-tree

${\mathfrak T}_{\varTheta ^{\circ }_{}} = (\varTheta ^{\circ }_{},\vartriangleleft ^{}_{\varTheta ^{\circ }_{}})$ of $\langle \varLambda ^{\circ }_{v} \rangle _{v\in \mathbb V}$ is also called the max-tree of $\mathcal F$. The component-tree ${\mathfrak T}_{\varTheta ^{\bullet }_{}} = (\varTheta ^{\bullet }_{},\vartriangleleft ^{}_{\varTheta ^{\bullet }_{}})$ of $\langle \varLambda ^{\bullet }_{v} \rangle _{v\in \mathbb V}$ is also called the min-tree of $\mathcal F$.

The min-tree and max-tree of the image $\mathcal F$ of Fig. 4 are illustrated in Fig. 5.

The elements of $\varTheta ^{\star }_{}$ are generally referred to as the nodes of the component-tree. The elements of $\vartriangleleft ^{}_{\varTheta ^{\star }_{}}$ are generally referred to as the edges of the component-tree. We will use this terminology for all the hierarchical structures considered in this study.

Definition 33

((External) proper part of a node) For any $X\in \varTheta ^{{\square }}_{}$, we define the proper part of $X$ (in the component-tree) as

$$\begin{aligned} \rho ^{\varTheta ^{{\square }}_{}}_{X} = X\setminus \bigcup _{X= \zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{{\square }}_{}}}(Y)} Y\end{aligned}$$

(24)

and the external proper part of $X$ (in the component-trees) as

$$\begin{aligned} \rho ^{\varTheta ^{}_{}}_{X} = X\setminus \bigcup _{X= \zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{{\square }}_{}}}(Y)} \tau (Y) \end{aligned}$$

(25)

Property 34

The set $\{\rho ^{\varTheta ^{\star }_{}}_{X}\}_{X\in \varTheta ^{\star }_{}}$ is a partition of $\mathbb U$.

Remark 35

The set $\{\rho ^{\varTheta ^{}_{}}_{X}\}_{X\in \varTheta ^{}_{}}$ may not be a partition of $\mathbb U$. Indeed, we have $\bigcup _{X\in \varTheta ^{}_{}} \rho ^{\varTheta ^{}_{}}_{X} = \mathbb U$ and for any two distinct $X, Y\in \varTheta ^{}_{}$ we have $\rho ^{\varTheta ^{}_{}}_{X} \cap \rho ^{\varTheta ^{}_{}}_{Y} = \emptyset$. However, it may happen that $\rho ^{\varTheta ^{}_{}}_{X} = \emptyset$.

Property 36

Let $X\in \varTheta ^{{\square }}_{}$. There exist $\alpha ^{\varTheta ^{{\square }}_{}}_{X}, \omega ^{\varTheta ^{{\square }}_{}}_{X} \in \mathbb V$ such that

$$\begin{aligned} \llbracket \alpha ^{\varTheta ^{{\square }}_{}}_{X}, \omega ^{\varTheta ^{{\square }}_{}}_{X}\rrbracket _{\leqslant ^{\square }} = \{v\in \mathbb V\mid X\in \varTheta ^{{\square }}_{v}\} \end{aligned}$$

(26)

Definition 37

(Remanence of a node) For any $X\in \varTheta ^{{\square }}_{}$, we note $\mathbb I^{\varTheta ^{{\square }}_{}}_{X} = \llbracket \alpha ^{\varTheta ^{{\square }}_{}}_{X}, \omega ^{\varTheta ^{{\square }}_{}}_{X}\rrbracket _{\leqslant ^{\square }}$ and we define the remanence of $X$ (in the component-tree) as

$$\begin{aligned} \delta ^{\varTheta ^{{\square }}_{}}_{X} = |\mathbb I^{\varTheta ^{{\square }}_{}}_{X}| \end{aligned}$$

(27)

Definition 38

(Average remanence) The average remanence $\delta ^{}_{\varTheta ^{\star }_{}} \in \mathbb Q$ of the component-tree ${\mathfrak T}_{\varTheta ^{\star }_{}}$ is defined as

$$\begin{aligned} \delta ^{}_{\varTheta ^{\star }_{}} = \frac{1}{|\varTheta ^{\star }_{}|} \sum _{X\in \varTheta ^{\star }_{}} \delta ^{\varTheta ^{\star }_{}}_{X} \end{aligned}$$

(28)

The average remanence $\delta ^{}_{} \in \mathbb Q$ of the image $\mathcal F$ is defined as

$$\begin{aligned} \delta ^{}_{} = \frac{1}{|\varTheta ^{}_{}|} \sum _{X\in \varTheta ^{}_{}} \delta ^{\varTheta ^{{\square }}_{}}_{X} \end{aligned}$$

(29)

Property 39

We have

$$\begin{aligned} 1 \le \delta ^{}_{\varTheta ^{\star }_{}}, \delta ^{}_{} \le \varDelta \end{aligned}$$

(30)

i.e. the average remanence and the component-trees and of the image are lower than the size $\varDelta$ of $\mathbb V$.

The component-tree ${\mathfrak T}_{\varTheta ^{\star }_{}} = (\varTheta ^{\star }_{},\vartriangleleft ^{}_{\varTheta ^{\star }_{}})$ is composed of a number of nodes (and edges) lower than the size $n$ of the image support. It generally stores each point of the image support once by associating each node $X\in \varTheta ^{\star }_{}$ with its proper part $\rho ^{\varTheta ^{\star }_{}}_{X}$. This justifies the following result.

Property 40

We have

$$\begin{aligned} |\varTheta ^{\star }_{}| = |\mathord {\vartriangleleft ^{}_{\varTheta ^{\star }_{}}}| + 1 = \mathcal O(n) \end{aligned}$$

(31)

Property 41

We can store ${\mathfrak T}_{\varTheta ^{\star }_{}}$ with a space cost $\mathcal O(n)$.

There exist numerous algorithms to compute the component-tree. The most efficient (sequential) ones present a quasi-linear time cost [8].

Property 42

The construction of ${\mathfrak T}_{\varTheta ^{\star }_{}}$ can be done with a time cost $\mathcal O(n\log n)$.

Remark 43

In the component-tree ${\mathfrak T}_{\varTheta ^{\star }_{}}$, each node $X\in \varTheta ^{\star }_{}$ is generally endowed with its “maximal value” $\omega ^{\varTheta ^{\star }_{}}_{X} \in \mathbb V$ (and equivalently with $\mathbb I^{\varTheta ^{\star }_{}}_{X}$). In particular, this information allows one to model $\mathcal F$ as a component-tree in a lossless way.

Property 44

([17, 53]) The image $\mathcal F: \mathbb U\rightarrow \mathbb V$ can be recovered from either its max-tree or min-tree by setting, for any $\textbf{x} \in \mathbb U$

$$\begin{aligned} \mathcal F(\textbf{x}) = \bigvee ^{\leqslant _\mathbb V}_{X\in \varTheta ^{\star }_{}} \mathbf{{1}}_{\big (\rho ^{\varTheta ^{\star }_{}}_{X}, \kappa ^\star \big (\omega ^{\varTheta ^{\star }_{}}_{X}\big )\big )}(\textbf{x}) \end{aligned}$$

(32)

with

$$\begin{aligned} \kappa ^{\square }= \left\{ \begin{array}{ll} \text {id}_{\mathbb V} &{} \text { if } {\square }= \circ \\ {\sigma }^{\bullet } &{} \text { if } {\square }= \bullet \end{array} \right. \end{aligned}$$

(33)

and where $\textbf{1}_{(A,u)}: \mathbb U\rightarrow \mathbb V$ is the cylinder function of support $A\subseteq \mathbb U$ and value $u\in \mathbb V$ defined by $\textbf{1}_{(A,u)}(\textbf{x}) = u$ if $\textbf{x} \in A$ and $\bot$ otherwise.

5.1.2 Valued Min-tree and Valued Max-tree

For any $v\in \mathbb V$, we set

$$\begin{aligned} \varXi ^{\star }_{v} = \varTheta ^{\star }_{v} \times \{v\} \end{aligned}$$

(34)

Property 45

We have

$$\begin{aligned} \varXi ^{\circ }_{\top }&= \varXi ^{\bullet }_{\bot } = \emptyset \end{aligned}$$

(35)

$$\begin{aligned} \varXi ^{\circ }_{\bot }&= \{(\mathbb U,\bot )\} \end{aligned}$$

(36)

$$\begin{aligned} \varXi ^{\bullet }_{\top }&= \{(\mathbb U,\top )\} \end{aligned}$$

(37)

For any $v\in \mathbb V\setminus \{\bot , \top \}$, we have

$$\begin{aligned} \varXi ^{\star }_{v} \ne \emptyset \end{aligned}$$

(38)

Based on the definition of Eq. (34), we set

$$\begin{aligned} \varXi ^{\star }_{} = \bigcup _{v\in \mathbb V} \varXi ^{\star }_{v} \end{aligned}$$

(39)

Property 46

We have

$$\begin{aligned} \varXi ^{\star }_{} = \bigcup _{X\in \varTheta ^{\star }_{}} \bigcup _{v\in \mathbb I^{\varTheta ^{\star }_{}}_{X}} \{(X,v)\} \end{aligned}$$

(40)

We define the partial order(s) $\sqsubseteq ^{}_{\varXi ^{\star }_{}}$ on $\varXi ^{\star }_{}$ as

$$\begin{aligned} (X,v) \sqsubseteq ^{}_{\varXi ^{\star }_{}} (Y,w) \Longleftrightarrow X\subseteq Y\wedge w\leqslant ^\star v\end{aligned}$$

(41)

with $\sqsubseteq ^{}_{\varXi ^{\star }_{}} \searrow _{RT}\ \vartriangleleft ^{}_{\varXi ^{\star }_{}}$

Definition 47

(Valued component-tree [41]) The tree ${\mathfrak T}_{\varXi ^{\star }_{}} = (\varXi ^{\star }_{},\vartriangleleft ^{}_{\varXi ^{\star }_{}})$ is called the valued component-tree of $\langle \varLambda ^{\star }_{v} \rangle _{v\in \mathbb V}$.

Definition 48

(Valued min-tree, valued max-tree [41]) The valued component-tree ${\mathfrak T}_{\varXi ^{\circ }_{}} = (\varXi ^{\circ }_{},\vartriangleleft ^{}_{\varXi ^{\circ }_{}})$ of $\langle \varLambda ^{\circ }_{v} \rangle _{v\in \mathbb V}$ is also called the valued max-tree of $\mathcal F$. The valued component-tree ${\mathfrak T}_{\varXi ^{\bullet }_{}} = (\varXi ^{\bullet }_{},\vartriangleleft ^{}_{\varXi ^{\bullet }_{}})$ of $\langle \varLambda ^{\bullet }_{v} \rangle _{v\in \mathbb V}$ is also called the valued min-tree of $\mathcal F$.

The valued min-tree and valued max-tree of the image $\mathcal F$ of Fig. 4 are illustrated in Fig. 6.

Property 49

We have

$$\begin{aligned} |\varXi ^{\star }_{}| = \sum _{v\in \mathbb V} |\varXi ^{\star }_{v}| = |\varTheta ^{\star }_{}| \cdot \delta ^{}_{\varTheta ^{\star }_{}} \end{aligned}$$

(42)

Property 50

We have

$$\begin{aligned} |\varXi ^{\star }_{}| = |\mathord {\vartriangleleft ^{}_{\varXi ^{\star }_{}}}| + 1 = \mathcal O(n\cdot \delta ^{}_{\varTheta ^{\star }_{}}) \end{aligned}$$

(43)

Definition 51

((External) proper part of a node) For any $P= (X,v) \in \varXi ^{\star }_{}$, we define the proper part of $P$ (in the valued component-tree) as

$$\begin{aligned} \rho ^{\varXi ^{\star }_{}}_{P} = \left\{ \begin{array}{ll} \rho ^{\varTheta ^{\star }_{}}_{X} &{} \text { if } v= \omega ^{\varTheta ^{\star }_{}}_{X} \\ \emptyset &{} \text { if } v\ne \omega ^{\varTheta ^{\star }_{}}_{X} \end{array} \right. \end{aligned}$$

(44)

and the external proper part of $X$ (in the valued component-trees) as

$$\begin{aligned} \rho ^{\varXi ^{}_{}}_{P} = \left\{ \begin{array}{ll} \rho ^{\varTheta ^{}_{}}_{X} &{} \text { if } v= \omega ^{\varTheta ^{\star }_{}}_{X} \\ \emptyset &{} \text { if } v\ne \omega ^{\varTheta ^{\star }_{}}_{X} \end{array} \right. \end{aligned}$$

(45)

Proposition 52

There is a decreasing homeomorphism from the valued component-tree to the component-tree.

These homeomorphisms can be observed by comparison between the max-tree (resp. min-tree) and the valued max-tree (resp. valued min-tree) in Figs. 5 and 6.

The valued component-tree ${\mathfrak T}_{\varXi ^{\star }_{}} = (\varXi ^{\star }_{},\vartriangleleft ^{}_{\varXi ^{\star }_{}})$ contains more nodes (and edges) than the component-tree. However, since exactly one connected component $X$ appears into the interval of values $\mathbb I^{\varTheta ^{\star }_{}}_{X}$, it may be sufficient to model all the nodes $(X,v)$ for $v\in \mathbb I^{\varTheta ^{\star }_{}}_{X}$ and all the edges between these successive nodes as a single node $X$ endowed with the two values $\alpha ^{\varTheta ^{\star }_{}}_{X}$ and $\omega ^{\varTheta ^{\star }_{}}_{X}$ (in practice, $\omega ^{\varTheta ^{\star }_{}}_{X}$ is sufficient, since $\llbracket \alpha ^{\varTheta ^{\star }_{}}_{X},\omega ^{\varTheta ^{\star }_{}}_{X}\rrbracket _{\leqslant ^\star } = \rrbracket \omega ^{\varTheta ^{\star }_{}}_{\zeta ^{}_{\vartriangleleft ^{}_{\varXi ^{\star }_{}}}(X)},\omega ^{\varTheta ^{\star }_{}}_{X}\rrbracket _{\leqslant ^\star }$. In such case, the space cost is the same as for the component-tree and the algorithms for building the component-tree allow to build the valued component-tree.

Property 53

We can store ${\mathfrak T}_{\varXi ^{\star }_{}}$ with a space cost $\mathcal O(n)$.

Property 54

The construction of ${\mathfrak T}_{\varXi ^{\star }_{}}$ can be done with a time cost $\mathcal O(n\log n)$.

5.2 Trees of Shapes

The definitions of adjacency tree and tree of shapes given in this section require both hypotheses (H1) and (H2).

5.2.1 Adjacency Tree

For any $v\in \mathbb V$, we set

$$\begin{aligned} \varTheta ^{}_{v} = \varTheta ^{\circ }_{v} \cup \varTheta ^{\bullet }_{v} \end{aligned}$$

(46)

(see Eq. (18)).

We define the order $\sqsubseteq ^{}_{\varTheta ^{}_{v}}$ on $\varTheta ^{}_{v}$ as

$$\begin{aligned} X\sqsubseteq ^{}_{\varTheta ^{}_{v}} Y\Longleftrightarrow \tau (X) \subseteq \tau (Y) \end{aligned}$$

(47)

with $\sqsubseteq ^{}_{\varTheta ^{}_{v}} \searrow _{RT}\ \vartriangleleft ^{}_{\varTheta ^{}_{v}}$.

Definition 55

(Adjacency tree [49]) The tree ${\mathfrak T}_{\varTheta ^{}_{v}} = (\varTheta ^{}_{v},\vartriangleleft ^{}_{\varTheta ^{}_{v}})$ is called the adjacency tree of $\varLambda ^{\circ }_{v} \cup \varLambda ^{\bullet }_{v}$.

We note $\mathbb U_v$ the maximum of ${\mathfrak T}_{\varTheta ^{}_{v}} = (\varTheta ^{}_{v},\vartriangleleft ^{}_{\varTheta ^{}_{v}})$. It is a node of $\varTheta ^{\bullet }_{v}$ and the only unbounded node of $\varTheta ^{}_{v}$.

The adjacency tree of a threshold set of the image $\mathcal F$ of Fig. 4 is illustrated in Fig. 7.

Fig. 7

Adjacency-tree of the binary image obtained by thresholding $\mathcal F$ at value 3, corresponding to the sets $\varLambda ^{\circ }_{3}$ and $\varLambda ^{\bullet }_{3}$ (see Fig. 4e). Each node (square) corresponds to an element $X$ of $\varTheta ^{}_{3}$. The white part of the node corresponds to $X$. The blue-bordered node corresponds to the unbounded node $\mathbb U_3$. The red arrows correspond to the $\vartriangleleft ^{}_{\varTheta ^{}_{3}}$ relation

Remark 56

Since $\varLambda ^{\bullet }_{v}$ is deducted from $\varLambda ^{\circ }_{v}$, and vice versa (see Eqs. (16–17)), we may also consider that the adjacency tree is defined for either $\varLambda ^{\bullet }_{v}$ or $\varLambda ^{\circ }_{v}$.

Remark 57

In general, the adjacency tree is natively defined for a binary image decomposed into a foreground $\varLambda ^{\circ }_{}$ and a background $\varLambda ^{\bullet }_{}$. In Definition 55, we choose to define it for a binary image obtained by thresholding a grey-level image. This definition remains compliant with the usual definition by simply considering that $\mathbb V= \{\bot ,\top \}$ with $\bot \ne \top$ and by setting $v= \top$.

Property 58

We have

$$\begin{aligned} |\varTheta ^{}_{v}| = |\varTheta ^{\circ }_{v}| + |\varTheta ^{\bullet }_{v}| = |\mathord {\vartriangleleft ^{}_{\varTheta ^{}_{v}}}| + 1 = \mathcal O(n) \end{aligned}$$

(48)

The adjacency tree ${\mathfrak T}_{\varTheta ^{}_{v}} = (\varTheta ^{}_{v},\vartriangleleft ^{}_{\varTheta ^{}_{v}})$ is composed of a number of nodes (and edges) lower than the size $n$ of the image support. It generally stores each point of the image support once, in the unique set $X$ of $\varLambda ^{\circ }_{v} \cup \varLambda ^{\bullet }_{v}$ that contains that point. This justifies the following result.

Property 59

We can store ${\mathfrak T}_{\varTheta ^{}_{v}}$ with a space cost $\mathcal O(n)$.

There exist various simple ways for building an adjacency tree [49], e.g. from a connected component labelling process or by developing a variant of minimal spanning tree construction on a binary-valued graph. Such algorithms present a linear time cost.

Property 60

The construction of ${\mathfrak T}_{\varTheta ^{}_{v}}$ can be done with a time cost $\mathcal O(n)$.

5.2.2 Tree of Shapes

We set (see also Eq. (20))

$$\begin{aligned} \varTheta ^{}_{} = \varTheta ^{\circ }_{} \cup \varTheta ^{\bullet }_{} = \bigcup _{v\in {\mathbb V}}\varTheta ^{}_{v} \end{aligned}$$

(49)

and

$$\begin{aligned} \varTheta ^{\tau }_{} = \tau (\varTheta ^{}_{}) \end{aligned}$$

(50)

Remark 61

An element $X\in \varTheta ^{\tau }_{}$ may be induced by elements from many sets $\varTheta ^{}_{v}$.

We define the order $\sqsubseteq ^{}_{\varTheta ^{\tau }_{}}$ on $\varTheta ^{\tau }_{}$ as

$$\begin{aligned} X\sqsubseteq ^{}_{\varTheta ^{\tau }_{}} Y\Longleftrightarrow X\subseteq Y\end{aligned}$$

(51)

with $\sqsubseteq ^{}_{\varTheta ^{\tau }_{}} \searrow _{RT}\ \vartriangleleft ^{}_{\varTheta ^{\tau }_{}}$.

Definition 62

(Tree of shapes [27]) The tree ${\mathfrak T}_{\varTheta ^{\tau }_{}} =(\varTheta ^{\tau }_{},\vartriangleleft ^{}_{\varTheta ^{\tau }_{}})$ is called the tree of shapes of $\mathcal F$ (with $\mathcal F$ defined in Definition 27).

Remark 63

Since $\mathcal F$, $\langle \varLambda ^{\circ }_{v} \rangle _{v\in \mathbb V}$ and $\langle \varLambda ^{\bullet }_{v} \rangle _{v\in \mathbb V}$ contain equivalent information, we may also consider that ${\mathfrak T}_{\varTheta ^{\tau }_{}}$ is the tree of shapes of either $\langle \varLambda ^{\circ }_{v} \rangle _{v\in \mathbb V}$ or $\langle \varLambda ^{\bullet }_{v} \rangle _{v\in \mathbb V}$.

Property 64

We have:

$$\begin{aligned} |\varTheta ^{}_{}| \ge |\varTheta ^{\tau }_{}| = |\mathord {\vartriangleleft ^{}_{\varTheta ^{\tau }_{}}}| + 1 = \mathcal O(n) \end{aligned}$$

(52)

Let ${\pi }^{\varTheta ^{}_{}}_{\varTheta ^{\tau }_{}}: \varTheta ^{}_{} \rightarrow \varTheta ^{\tau }_{}$ be the surjective application defined by ${\pi }^{\varTheta ^{}_{}}_{\varTheta ^{\tau }_{}}(X) = \tau (X)$.

Let ${\sim }_{T}$ be the equivalence relation on $\varTheta ^{}_{}$ defined by

$$\begin{aligned} X{\sim }_{T} Y\Longleftrightarrow {\pi }^{\varTheta ^{}_{}}_{\varTheta ^{\tau }_{}}(X) = {\pi }^{\varTheta ^{}_{}}_{\varTheta ^{\tau }_{}}(Y) \end{aligned}$$

(53)

We set

$$\begin{aligned} T= \varTheta ^{}_{}/\mathord {{\sim }_{T}} \end{aligned}$$

(54)

Let ${\pi }^{T}_{\varTheta ^{\tau }_{}}: T\rightarrow \varTheta ^{\tau }_{}$ be the application defined by ${\pi }^{T}_{\varTheta ^{\tau }_{}}([X]_{{\sim }_{T}}) = {\pi }^{\varTheta ^{}_{}}_{\varTheta ^{\tau }_{}}(X)$.

Property 65

${\pi }^{T}_{\varTheta ^{\tau }_{}}$ is bijective.

This property allows us to define the relation $\sqsubseteq ^{}_{T}$ on $T$ by

$$\begin{aligned} J\sqsubseteq ^{}_{T} K\Longleftrightarrow {\pi }^{T}_{\varTheta ^{\tau }_{}}(J) \sqsubseteq ^{}_{\varTheta ^{\tau }_{}} {\pi }^{T}_{\varTheta ^{\tau }_{}}(K) \end{aligned}$$

(55)

with $\sqsubseteq ^{}_{T} \searrow _{RT}\ \vartriangleleft ^{}_{T}$.

Property 66

We have

$$\begin{aligned} (T,\vartriangleleft ^{}_{T}) \equiv (\varTheta ^{\tau }_{},\vartriangleleft ^{}_{\varTheta ^{\tau }_{}}) \end{aligned}$$

(56)

This property motivates the following alternative definition of the tree of shapes.

Definition 67

(Tree of shapes (alternative)) The tree ${\mathfrak T}_{T} =(T,\vartriangleleft ^{}_{T})$ is called the tree of shapes of $\mathcal F$.

Property 68

Let $K\in T$. For all $X\in K$, we have either ${\square }(X) = \circ$ or ${\square }(X) = \bullet$.

This property allows us to extend the definition of ${\square }$ and $\blacksquare$ to the nodes of $\varTheta ^{\tau }_{}$ such that for all $X\in \varTheta ^{}_{}$, we have ${\square }(\tau (X)) = {\square }(X)$ and $\blacksquare (\tau (X)) = \blacksquare (X)$. By convention, we set ${\square }(\mathbb U) = \circ$ and $\blacksquare (\mathbb U) = \bullet$.

Fig. 8

Tree of shapes of the grey-level image $\mathcal F$ of Fig. 4. Each node (square) corresponds to an element $X$ of $\varTheta ^{}_{}$ such that $\tau (X) \in \varTheta ^{\tau }_{}$. The white part of the node corresponds to $X$. The blue-bordered nodes correspond to the unbounded $X$. The yellow arrows correspond to the $\vartriangleleft ^{}_{\varTheta ^{\tau }_{}}$ relation (Color figure online)

Property 69

The maximum of the tree of shapes ${\mathfrak T}_{\varTheta ^{\tau }_{}} =(\varTheta ^{\tau }_{},\vartriangleleft ^{}_{\varTheta ^{\tau }_{}})$, namely $\mathbb U$, corresponds to the equivalence class $[\mathbb U]_{{\sim }_{T}} = \{\mathbb U_v\}_{v\in \mathbb V}$, i.e. the set of all the maxima of the adjacency trees of $\mathcal F$ at each threshold set.

The tree of shapes of the image $\mathcal F$ of Fig. 4 is illustrated in Fig. 8. In this figure, each element of $\varTheta ^{\tau }_{}$ is depicted as an element $X\in \varTheta ^{}_{}$ such that $\tau (X) \in \varTheta ^{\tau }_{}$.

Property 70

Let $X\in \varTheta ^{\tau }_{}$. There exist $\alpha ^{\varTheta ^{\tau }_{}}_{X}, \omega ^{\varTheta ^{\tau }_{}}_{X} \in \mathbb V$ such that

$$\begin{aligned} \llbracket \alpha ^{\varTheta ^{\tau }_{}}_{X}, \omega ^{\varTheta ^{\tau }_{}}_{X}\rrbracket _{\leqslant ^{\square }}&= \bigcup _{Y\in [X]_{{\sim }_{T}}} \llbracket \alpha ^{\varTheta ^{{\square }}_{}}_{Y}, \omega ^{\varTheta ^{{\square }}_{}}_{Y}\rrbracket _{\leqslant ^{\square }} \end{aligned}$$

(57)

$$\begin{aligned}&= \llbracket \bigwedge ^{\leqslant ^{\square }}_{Y\in [X]_{{\sim }_{T}}} \alpha ^{\varTheta ^{{\square }}_{}}_{Y},\bigvee ^{\leqslant ^{\square }}_{Y\in [X]_{{\sim }_{T}}} \omega ^{\varTheta ^{{\square }}_{}}_{Y} \rrbracket _{\leqslant ^{\square }} \end{aligned}$$

(58)

Definition 71

(Remanence of a node) For any $X\in \varTheta ^{\tau }_{}$, we note $\mathbb I^{\varTheta ^{\tau }_{}}_{X} = \llbracket \alpha ^{\varTheta ^{\tau }_{}}_{X}, \omega ^{\varTheta ^{\tau }_{}}_{X}\rrbracket _{\leqslant ^{\square }}$ and we define the remanence of $X$ (in the tree of shapes) as

$$\begin{aligned} \delta ^{\varTheta ^{\tau }_{}}_{X} = |\mathbb I^{\varTheta ^{\tau }_{}}_{X}| \end{aligned}$$

(59)

Remark 72

It is possible to determine ${\square }: \varTheta ^{\tau }_{} \rightarrow \{\circ , \bullet \}$ and $\blacksquare : \varTheta ^{\tau }_{} \rightarrow \{\circ , \bullet \}$ without knowledge on ${\square }: \varTheta ^{}_{} \rightarrow \{\circ , \bullet \}$ and $\blacksquare : \varTheta ^{}_{} \rightarrow \{\circ , \bullet \}$, by applying recursively the following rules from the root $\mathbb U$ of the tree of shapes:

• if $X= \mathbb U$, then $\alpha ^{\varTheta ^{\tau }_{}}_{X} = \omega ^{\varTheta ^{\tau }_{}}_{X} = \bot$ and ${\square }(X) = \circ$;

• if $X\ne \mathbb U$ and $\mathbb I^{\varTheta ^{\tau }_{}}_{X} \cap \mathbb I^{\varTheta ^{\tau }_{}}_{\zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{}_{}}{\tau }{}}(X)} = \emptyset$, then ${\square }(X) = {\square }(\zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{\tau }_{}}}(X))$ and we have $\alpha ^{\varTheta ^{\tau }_{}}_{X} = {\sigma }^{{\square }}(\omega ^{\varTheta ^{\tau }_{}}_{\zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{\tau }_{}}}(X)})$;

• if $X\ne \mathbb U$ and $\mathbb I^{{\varTheta ^{\tau }_{}}}_{X} \cap \mathbb I^{{\varTheta ^{\tau }_{}}}_{\zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{\tau }_{}}}(X)} \ne \emptyset$, then ${\square }(X) = \blacksquare (\zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{\tau }_{}}}(X))$ and we have $\alpha ^{\varTheta ^{\tau }_{}}_{X} = \omega ^{\varTheta ^{\tau }_{}}_{\zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{\tau }_{}}}(X)}$ with in particular $\mathbb I^{{\varTheta ^{\tau }_{}}}_{X} \cap \mathbb I^{{\varTheta ^{\tau }_{}}}_{\zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{\tau }_{}}}(X)} = \big \{\alpha ^{\varTheta ^{\tau }_{}}_{X}\big \} = \big \{\omega ^{\varTheta ^{\tau }_{}}_{\zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{\tau }_{}}}(X)}\big \}$.

Definition 73

(Proper part of a node) For any $X\in \varTheta ^{\tau }_{}$, we define the proper part of $X$ (in the tree of shapes) as

$$\begin{aligned} \rho ^{\varTheta ^{\tau }_{}}_{X} = X\setminus \bigcup _{X= \zeta ^{}_{\sqsubseteq ^{}_{\varTheta ^{\tau }_{}}}(Y)} Y\end{aligned}$$

(60)

Property 74

The set $\{\rho ^{\varTheta ^{\tau }_{}}_{X}\}_{X\in \varTheta ^{\tau }_{}}$ is a partition of $\mathbb U$.

Property 75

Let $X\in \varTheta ^{\tau }_{}$. Let $\widehat{X}= \bigwedge ^{\sqsubseteq ^{}_{\varTheta ^{{\square }}_{}}} ({\pi }^{T}_{\varTheta ^{\tau }_{}})^{-1}(X)$. We have

$$\begin{aligned} \rho ^{\varTheta ^{}_{}}_{\widehat{X}}&= \rho ^{\varTheta ^{\tau }_{}}_{X} \end{aligned}$$

(61)

$$\begin{aligned} {\forall Y\in [\widehat{X}]_{{\sim }_{T}} \setminus \{\widehat{X}\}, \rho ^{\varTheta ^{}_{}}_{Y}}&= \emptyset \end{aligned}$$

(62)

Remark 76

From Eq. (61), we have access to the external proper parts of (the nodes of) the component-trees from the proper parts of (the nodes of) the tree of shapes, and vice versa, with a time cost $\mathcal O(n)$.

The notion of tree of shapes generalizes the notion of adjacency tree.

Property 77

If $\mathbb V= \{\bot , \top \}$ with $\bot \ne \top$, then there is an isomorphism between the tree of shapes ${\mathfrak T}_{\varTheta ^{\tau }_{}} =(\varTheta ^{\tau }_{},\vartriangleleft ^{}_{\varTheta ^{\tau }_{}})$ and the adjacency tree ${\mathfrak T}_{\varTheta ^{}_{\top }} = (\varTheta ^{}_{\top },\vartriangleleft ^{}_{\varTheta ^{}_{\top }})$.

$$\begin{aligned} \varDelta = 2 \Longrightarrow {\mathfrak T}_{\varTheta ^{}_{\top }} \equiv {\mathfrak T}_{\varTheta ^{\tau }_{}} \end{aligned}$$

(63)

The tree of shapes ${\mathfrak T}_{\varTheta ^{\tau }_{}} =(\varTheta ^{\tau }_{},\vartriangleleft ^{}_{\varTheta ^{\tau }_{}})$ generally stores each point of the image support once by associating each node $X$ with its proper part $\rho ^{\varTheta ^{\tau }_{}}_{X}$. This justifies the following result.

Property 78

We can store ${\mathfrak T}_{\varTheta ^{\tau }_{}}$ with a space cost $\mathcal O(n)$.

There exist numerous algorithms to compute the tree of shapes. The most efficient (sequential) ones present a quasi-linear complexity [16].

Property 79

The construction of ${\mathfrak T}_{\varTheta ^{\tau }_{}}$ can be done with a time cost $\mathcal O(n\log n)$.

Remark 80

In the tree of shapes, each node $X\in \varTheta ^{\tau }_{}$ is generally endowed with its “maximal value” $\omega ^{\varTheta ^{\tau }_{}}_{X} \in \mathbb V$. In particular, with $\rho ^{\varTheta ^{\tau }_{}}_{X}$ and $\omega ^{\varTheta ^{\tau }_{}}_{X}$ known for any node $X\in \varTheta ^{\tau }_{}$ it is possible to model $\mathcal F$ as a tree of shapes in a lossless way.

Property 81

The image $\mathcal F: \mathbb U\rightarrow \mathbb V$ can be recovered from its tree of shapes by setting, for any $\textbf{x} \in \mathbb U$

$$\begin{aligned} \mathcal F(\textbf{x}) = \bigvee ^{\leqslant _\mathbb V}_{X\in \varTheta ^{\tau }_{}} \textbf{1}_{\big (\rho ^{\varTheta ^{\tau }_{}}_{X}, \kappa ^{\square }\big (\omega ^{\varTheta ^{\tau }_{}}_{X}\big )\big )}(\textbf{x}) \end{aligned}$$

(64)

Fig. 9

Graph of valued shapes of the grey-level image $\mathcal F$ of Fig. 4. Each node (square) corresponds to an element $(X,v)$ of $\varXi ^{}_{}$. The white part of the node corresponds to $X$. The blue-bordered nodes correspond to unbounded $X$. The two nodes marked as $\infty$ are identified as a unique node. The nodes are organised with respect to the values (threshold sets) $v\in \mathbb V$ at which they are generated. The values of $\mathbb V$ are depicted on the left (round boxes). The green arrows correspond to the $\vartriangleleft ^{\varphi }_{}$ relation. The red arrows correspond to the $\vartriangleleft ^{\psi }_{}$ relation (Color figure online)

Fig. 10

Reduction of the graph of valued shapes of Fig. 9 (first step). The edges removed from the graph of Fig. 9 (depicted in light grey) are those that correspond to the transitive pattern of Eq. (81) (Color figure online)

Fig. 11

Reduction of the graph of valued shapes of Fig. 9 (second step). The edges removed from the graph of Fig. 10 (depicted in light grey) are those that correspond to the transitive pattern of Eq. (82)

Fig. 12

Tree of valued shapes, defined as the reduction of the graph of valued shapes of Fig. 9 (third step). The edges removed from the graph of Fig. 11 (depicted in light grey) are those that correspond to the transitive pattern of Eq. (83). The green and red arrows correspond to the $\vartriangleleft ^{}_{\varXi ^{}_{}}$ relation

6 New Hierarchical Structures

In this section, we introduce four new hierarchical structures: the graph of valued shapes (Sect. 6.1), the tree of valued shapes (Sect. 6.2), the complete tree of shapes (Sect. 6.3) and the topological tree of shapes (Sect. 6.4). Starting from the valued component-trees and the adjacency trees which model a grey-level image, these structures are defined sequentially until providing information that can lead both to the usual tree of shapes or to the topological tree of shapes.

Let $v\in \mathbb V$. We set

$$\begin{aligned} \varXi ^{}_{v} = \varTheta ^{}_{v} \times \{v\} \end{aligned}$$

(65)

Property 82

We have

$$\begin{aligned} |\varXi ^{}_{v}| = |\varTheta ^{}_{v}| \end{aligned}$$

(66)

We define the order $\sqsubseteq ^{}_{\varXi ^{}_{v}}$ on $\varXi ^{}_{v}$ as

$$\begin{aligned} (X,v) \sqsubseteq ^{}_{\varXi ^{}_{v}} (Y,v) \Longleftrightarrow X \sqsubseteq ^{}_{\varTheta ^{}_{v}} Y \end{aligned}$$

(67)

with $\sqsubseteq ^{}_{\varXi ^{}_{v}} \searrow _{RT}\ \vartriangleleft ^{}_{\varXi ^{}_{v}}$.

We note ${\mathfrak T}_{\varXi ^{}_{v}} = (\varXi ^{}_{v},\vartriangleleft ^{}_{\varXi ^{}_{v}})$ and we call this tree the valued adjacency tree (at value $v$).

Property 83

There is a trivial isomorphism between the adjacency tree and the valued adjacency tree.

$$\begin{aligned} {\mathfrak T}_{\varTheta ^{}_{v}} \equiv {\mathfrak T}_{\varXi ^{}_{v}} \end{aligned}$$

(68)

Remark 84

$\sqsubseteq ^{}_{\varXi ^{}_{v}}$ is a hierarchical order which admits $(\mathbb U_v,v)$ as maximum.

We set

$$\begin{aligned} \varXi ^{}_{} = \bigcup _{v\in {\mathbb V}}\varXi ^{}_{v} = \varXi ^{\circ }_{} \cup \varXi ^{\bullet }_{} \end{aligned}$$

(69)

Remark 85

From now on, we identify $(\mathbb U,\bot )$ and $(\mathbb U,\top )$ which are considered as a unique element of $\varXi ^{}_{}$ noted $\infty$.

We extend the definition of ${\square }$ and $\blacksquare$ to the nodes of $\varXi ^{}_{}$ such that for all $P= (X,v) \in \varXi ^{}_{}$, we have ${\square }(P) = {\square }(X)$ and $\blacksquare (P) = \blacksquare (X)$. By convention, we set ${\square }(\infty ) = \bullet$ and $\blacksquare (\infty ) = \circ$.

Property 86

We have

$$\begin{aligned} |\varXi ^{}_{}| = \sum _{v\in \mathbb V} |\varXi ^{}_{v}| - 1 = |\varXi ^{\circ }_{}| + |\varXi ^{\bullet }_{}| - 1 = \mathcal O(n\cdot \delta ^{}_{}) \end{aligned}$$

(70)

We define the order $\sqsubseteq ^{\psi }_{}$ on $\varXi ^{}_{}$ as $\sqsubseteq ^{\psi }_{} \ = \bigcup _{v\in \mathbb V} \sqsubseteq ^{}_{\varXi ^{}_{v}}$, i.e.

$$\begin{aligned} P\sqsubseteq ^{\psi }_{} Q\Longleftrightarrow \exists v\in \mathbb V, P\sqsubseteq ^{}_{\varXi ^{}_{v}} Q\end{aligned}$$

(71)

with $\sqsubseteq ^{\psi }_{} \ \searrow _{RT}\ \vartriangleleft ^{\psi }_{}$.

We set ${\mathfrak F}_{\varXi ^{}_{}} = (\varXi ^{}_{},\vartriangleleft ^{\psi }_{})$.

Property 87

Up to the identification of $(\mathbb U,\bot )$ and $(\mathbb U,\top )$, there is a trivial isomorphism between $(\varXi ^{}_{},\sqsubseteq ^{\psi }_{})$ and the union of all the $(\varTheta ^{}_{v},\sqsubseteq ^{}_{\varTheta ^{}_{v}})$, namely $(\bigcup _{v\in \mathbb V} \varTheta ^{}_{v},\bigcup _{v\in \mathbb V} \sqsubseteq ^{}_{\varTheta ^{}_{v}}) = {\mathfrak F}_{\varXi ^{}_{}}$. In particular, the Hasse diagram of these structures is a forest that corresponds to the union of the adjacency trees.

Property 88

$\sqsubseteq ^{\psi }_{}$ is a piecewise hierarchical order. The maximal elements of $(\varXi ^{}_{},\sqsubseteq ^{\psi }_{})$ are gathered in the set

$$\begin{aligned} \bigtriangledown ^{\sqsubseteq ^{\psi }_{}} \varXi ^{}_{} = \{(\mathbb U_v,v)\}_{v\in \mathbb V} \end{aligned}$$

(72)

Property 89

We have

$$\begin{aligned} |\mathord {\vartriangleleft ^{\psi }_{}}| = |\varXi ^{}_{}| + 1 - \varDelta \end{aligned}$$

(73)

Property 90

Let $P= (X,v), Q= (Y,w) \in \varXi ^{}_{}$ such that $P\vartriangleleft ^{\psi }_{} Q$. We have ${\square }(Q) = \blacksquare (P)$. We also have $v=w$ and $\tau (X) \in \varPi [\overline{Y}] = \varPi [\mathbb U{\setminus } Y]$.

We define the order $\sqsubseteq ^{\varphi }_{}$ on $\varXi ^{}_{}$ as the union of $\sqsubseteq ^{}_{\varXi ^{\circ }_{}}$ and $\sqsubseteq ^{}_{\varXi ^{\bullet }_{}}$, i.e.

$$\begin{aligned} P\sqsubseteq ^{\varphi }_{} Q\Longleftrightarrow P\sqsubseteq ^{}_{\varXi ^{\circ }_{}} Q\vee P\sqsubseteq ^{}_{\varXi ^{\bullet }_{}} Q\end{aligned}$$

(74)

with $\sqsubseteq ^{\varphi }_{} \ \searrow _{RT}\ \vartriangleleft ^{\varphi }_{}$.

Property 91

Up to the identification of $(\mathbb U,\bot )$ and $(\mathbb U,\top )$, there is a trivial isomorphism between $(\varXi ^{}_{},\sqsubseteq ^{\varphi }_{})$ and the union of $(\varXi ^{\circ }_{},\sqsubseteq ^{}_{\varXi ^{\circ }_{}})$ and $(\varXi ^{\bullet }_{},\sqsubseteq ^{}_{\varXi ^{\bullet }_{}})$, namely $(\varXi ^{\circ }_{} \cup \varXi ^{\bullet }_{},\sqsubseteq ^{}_{\varXi ^{\circ }_{}} \cup \sqsubseteq ^{}_{\varXi ^{\bullet }_{}})$. In particular, the Hasse diagram of these structures is a tree that corresponds to the union of the valued min- and max-trees.

Property 92

$\sqsubseteq ^{\varphi }_{}$ is a hierarchical order that admits $\infty$ as maximum.

Property 93

We have

$$\begin{aligned} |\mathord {\vartriangleleft ^{\varphi }_{}}| = |\varXi ^{}_{}| - 1 \end{aligned}$$

(75)

Property 94

Let $P= (X,v), Q= (Y,w) \in \varXi ^{}_{}$ such that $P\vartriangleleft ^{\varphi }_{} Q$. We have ${\square }(Q) = {\square }(P)$. We also have $X\subseteq Y$ and $v= {\sigma }^{{\square }}(w)$.

For the sake of concision, we will note $\varphi = \zeta ^{}_{\sqsubseteq ^{\varphi }_{}}$, $\varPhi = Z_{\sqsubseteq ^{\varphi }_{}}$, $\psi = \zeta ^{}_{\sqsubseteq ^{\psi }_{}}$ and $\varPsi = Z_{\sqsubseteq ^{\psi }_{}}$.

6.1 Graph of Valued Shapes

Let $\blacktriangleleft _{\varXi ^{}_{}}$ be the relation defined as the union of $\vartriangleleft ^{\varphi }_{}$ and $\vartriangleleft ^{\psi }_{}$, i.e.

$$\begin{aligned} P\blacktriangleleft _{\varXi ^{}_{}} Q\Longleftrightarrow P\vartriangleleft ^{\varphi }_{} Q\vee P\vartriangleleft ^{\psi }_{} Q\end{aligned}$$

(76)

Definition 95

(Graph of valued shapes) The graph of valued shapes is the graph $\mathfrak G_{\varXi ^{}_{}} = (\varXi ^{}_{},\blacktriangleleft _{\varXi ^{}_{}})$.

Remark 96

Since the intersection of $\vartriangleleft ^{\varphi }_{}$ and $\vartriangleleft ^{\psi }_{}$ is empty, we can consider $\mathfrak G_{\varXi ^{}_{}}$ as $(\varXi ^{}_{},\blacktriangleleft _{\varXi ^{}_{}})$ or as $(\varXi ^{}_{},\vartriangleleft ^{\varphi }_{},\vartriangleleft ^{\psi }_{}) = (\varXi ^{}_{},\varphi ,\psi )$.

The graph of valued shapes of the image $\mathcal F$ of Fig. 4 is illustrated in Fig. 9.

Property 97

We have

$$\begin{aligned} |\mathord {\blacktriangleleft _{\varXi ^{}_{}}}| = 2\cdot |\varXi ^{}_{}| - \varDelta \end{aligned}$$

(77)

Proposition 98

$\mathfrak G_{\varXi ^{}_{}}$ is a directed acyclic graph.

We set $\sqsubseteq ^{}_{\varXi ^{}_{}}$ as the reflexive-transitive closure of $\blacktriangleleft _{\varXi ^{}_{}}$.

Property 99

$(\varXi ^{}_{},\sqsubseteq ^{}_{\varXi ^{}_{}})$ is an ordered set that admits $\infty$ as maximum.

The graph of valued shapes allows to establish the (recursive) links between the proper parts of the nodes of the component-trees (Eq. (24)) and the external parts of these nodes (Eq. (25)), which are directly related to the proper part of the nodes of the tree of shapes (Eqs. (61–62)).

Property 100

Let $X\in \varTheta ^{\star }_{}$. We set $P= (X,\omega ^{\varTheta ^{\star }_{}}_{X})$, which satisfies $P\in \varXi ^{}_{}$. We have

$$\begin{aligned} \rho ^{\varTheta ^{\star }_{}}_{X} =&\rho ^{\varTheta ^{}_{}}_{X} \cup \bigcup _{Y\in \varPhi (X)} \bigcup _{Z \in \varPsi (Y)} \rho ^{\varTheta ^{}_{}}_{Z} \end{aligned}$$

(78)

$$\begin{aligned} \rho ^{\varTheta ^{}_{}}_{X} =&\rho ^{\varTheta ^{\star }_{}}_{X} \setminus \bigcup _{Y\in \varPhi (X)} \bigcup _{Z \in \varPsi (Y)} \rho ^{\varTheta ^{}_{}}_{Z} \end{aligned}$$

(79)

Property 101

From the above property, it is possible to build the external proper parts (resp. the proper parts) from the proper parts (resp. the external proper parts) of the nodes in the component-trees with a time cost $\mathcal O(n)$.

6.2 Tree of Valued Shapes

Let $\vartriangleleft ^{}_{\varXi ^{}_{}}$ be the relation on $\varXi ^{}_{}$ defined by

$$\begin{aligned} \blacktriangleleft _{\varXi ^{}_{}} \ \searrow _{RT}\ \vartriangleleft ^{}_{\varXi ^{}_{}} \end{aligned}$$

(80)

Let $P\in \varXi ^{}_{}$. Let us consider the following three equalities

$$\begin{aligned} \psi (P)&= [\varphi \circ \psi \circ \varphi ] (P) \end{aligned}$$

(81)

$$\begin{aligned} \varphi (P)&= [\varphi \circ \psi \circ \psi ] (P) \end{aligned}$$

(82)

$$\begin{aligned} \varphi (P)&= [\varphi ^{\varDelta -2} \circ \psi ](P) \end{aligned}$$

(83)

Remark 102

If $P$ satisfies Eq. (81), then we have $P\blacktriangleleft _{\varXi ^{}_{}} \psi (P)$ and $\lnot (P\vartriangleleft ^{}_{\varXi ^{}_{}} \psi (P))$. If $P$ satisfies Eq. (82) or (83), then we have $P\blacktriangleleft _{\varXi ^{}_{}} \varphi (P)$ and $\lnot (P\vartriangleleft ^{}_{\varXi ^{}_{}} \varphi (P))$.

Proposition 103

Let $P\in \varXi ^{}_{}$ be such that $\varphi (P)$ and $\psi (P)$ exist. One of Eqs. (81–83) is satisfied.

Remark 104

If follows from Proposition 103 that for any $P\in \varXi ^{}_{}$ such that both $\psi (P)$ and $\varphi (P)$ exist, we have $\lnot (P\vartriangleleft ^{}_{\varXi ^{}_{}} \psi (P))$ or $\lnot (P\vartriangleleft ^{}_{\varXi ^{}_{}} \varphi (P))$. Since $(\varXi ^{}_{},\sqsubseteq ^{}_{\varXi ^{}_{}})$ admits a maximum (namely $\infty$), for each $P\in \varXi ^{}_{} {\setminus } \{\infty \}$, we have either $P\vartriangleleft ^{}_{\varXi ^{}_{}} \psi (P)$ or $P\vartriangleleft ^{}_{\varXi ^{}_{}} \varphi (P)$.

The following property derives from these facts.

Property 105

Let $P\in \varXi ^{}_{}$.

• 1. If exactly one of $\varphi (P)$, $\psi (P)$ is defined, then it is $\varphi (P)$ and we have $P\vartriangleleft ^{}_{\varXi ^{}_{}} \varphi (P)$.

• 2. If both $\varphi (P)$ and $\psi (P)$ are defined, then we have either $P\vartriangleleft ^{}_{\varXi ^{}_{}} \varphi (P)$ or $P\vartriangleleft ^{}_{\varXi ^{}_{}} \psi (P)$.

In Proposition 105, the first case corresponds to the nodes $P$ which are maximal elements for the relation $\sqsubseteq ^{\psi }_{}$ and/or for the relation $\sqsubseteq ^{\varphi }_{}$. If $P$ is a maximal element for $\sqsubseteq ^{\varphi }_{}$, then it is the maximum for this order, i.e. $P= \infty$ and in that case $\psi (P)$ is not defined (a contradiction). Otherwise, if $P$ is a maximal element for $\sqsubseteq ^{\psi }_{}$, then it is the maximum $\mathbb U_v$ ($\bot< v< \top$) for the adjacency tree at value $v$ (i.e. one of the blue-bordered nodes in Figs. 9–11, except $\infty$). For such node $\mathbb U_v$, there exists a node $\mathbb U_u$ (with $u$ = ${\sigma }^{\bullet }(v)$) such that $\mathbb U_v\blacktriangleleft _{\varXi ^{}_{}} \varphi (\mathbb U_v) = \mathbb U_u$ and thus $\mathbb U_v\vartriangleleft ^{}_{\varXi ^{}_{}} \varphi (\mathbb U_v) = \mathbb U_u$. The second case corresponds to the nodes $P$ which are neither maximal elements for $\sqsubseteq ^{\psi }_{}$ nor for $\sqsubseteq ^{\varphi }_{}$. This means that both $\varphi (P)$ and $\psi (P)$ exist. From Proposition 103 and Remark 102, we have $\lnot (P\vartriangleleft ^{}_{\varXi ^{}_{}} \psi (P))$ or $\lnot (P\vartriangleleft ^{}_{\varXi ^{}_{}} \varphi (P))$. But we cannot have $\lnot (P\vartriangleleft ^{}_{\varXi ^{}_{}} \psi (P))$ and $\lnot (P\vartriangleleft ^{}_{\varXi ^{}_{}} \varphi (P))$ since $\sqsubseteq ^{}_{\varXi ^{}_{}}$ admits a (unique) maximum distinct from $P$. As a consequence, we have either $\lnot (P\vartriangleleft ^{}_{\varXi ^{}_{}} \psi (P))$ or $\lnot (P\vartriangleleft ^{}_{\varXi ^{}_{}} \varphi (P))$, and equivalently, we have either $P\vartriangleleft ^{}_{\varXi ^{}_{}} \psi (P)$ or $P\vartriangleleft ^{}_{\varXi ^{}_{}} \varphi (P)$. This is illustrated in Fig. 12 by the fact that each black-bordered node presents exactly one (green or red) arrow starting from it and linking it to its successor with respect to the Hasse relation $\vartriangleleft ^{}_{\varXi ^{}_{}}$.

Proposition 106

$(\varXi ^{}_{},\vartriangleleft ^{}_{\varXi ^{}_{}})$ is a tree.

Property 107

$\sqsubseteq ^{}_{\varXi ^{}_{}}$ is a hierarchical order and $\sqsubseteq ^{}_{\varXi ^{}_{}} \ \searrow _{RT}\ \vartriangleleft ^{}_{\varXi ^{}_{}}$.

Property 108

We have

$$\begin{aligned} |\mathord {\vartriangleleft ^{}_{\varXi ^{}_{}}}| = |\varXi ^{}_{}|-1 \end{aligned}$$

(84)

Fig. 13

The complete tree of shapes of the grey-level image $\mathcal F$ of Fig. 4. This tree is obtained by a decreasing homeomorphism from the graph of valued shapes of Fig. 12. Each node (square) corresponds to an element $K= [(X,v)]_{{\sim }_{\varTheta ^{}_{}}}$ of $\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}$, or equivalently an element $X\in \varTheta ^{}_{}$. The white part of the node corresponds to $X$. The blue-bordered nodes correspond to unbounded $X$. The green and red arrows correspond to the $\vartriangleleft ^{}_{\varTheta ^{}_{}}$ relation

Definition 109

(Tree of valued shapes) The tree of valued shapes is the tree ${\mathfrak T}_{\varXi ^{}_{}} = (\varXi ^{}_{},\vartriangleleft ^{}_{\varXi ^{}_{}})$.

Figures 10–12 illustrate the transitive reduction procedure from the graph of valued shapes $\mathfrak G_{\varXi ^{}_{}}$ to the tree of valued shapes ${\mathfrak T}_{\varXi ^{}_{}}$ of the image $\mathcal F$ of Fig. 4. The edges of $\blacktriangleleft _{\varXi ^{}_{}}$ that correspond to the transitive patterns of Eq. (81) are removed in Fig. 10. Then, the edges of $\blacktriangleleft _{\varXi ^{}_{}}$ that correspond to the transitive patterns of Eq. (82) are removed in Fig. 11. Finally, the edges of $\blacktriangleleft _{\varXi ^{}_{}}$ that correspond to the transitive patterns of Eq. (83) are removed in Fig. 12. The edges that remain in Fig. 12 correspond to $\vartriangleleft ^{}_{\varXi ^{}_{}}$ and the associated tree is the tree of valued shapes.

The tree of valued shapes is defined from the set of nodes $\varXi ^{}_{}$. As a consequence, it inherits the notion of external proper part of the valued component-trees to define its own notion of proper part.

Definition 110

(Proper part of a node) For any $P= (X,v) \in \varXi ^{}_{}$, we define the proper part of $P$ (in the tree of valued shapes) as

$$\begin{aligned} \rho ^{\varXi ^{}_{}}_{P} = \left\{ \begin{array}{ll} \emptyset &{} \text { if } P= \zeta ^{}_{\vartriangleleft ^{}_{\varXi ^{}_{}}}((X,{\sigma }^{{\square }}(v))) \\ \rho ^{\varTheta ^{}_{}}_{X} &{} \text { otherwise} \end{array} \right. \end{aligned}$$

(85)

6.3 Complete Tree of Shapes

Let ${\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}: \varXi ^{}_{} \rightarrow \varTheta ^{}_{}$ be the surjective application defined by ${\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}((X,v)) = X$.

Let ${\sim }_{\varTheta ^{}_{}}$ be the equivalence relation on $\varXi ^{}_{}$ defined by

$$\begin{aligned} P{\sim }_{\varTheta ^{}_{}} Q\Longleftrightarrow {\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}(P) = {\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}(Q) \end{aligned}$$

(86)

Property 111

For any $K\in \varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}$, $(K,\sqsubseteq ^{}_{\varXi ^{}_{}})$ is a totally ordered set.

Let $\sqsubseteq ^{}_{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}}$ be the order relation on $\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}$ defined by

$$\begin{aligned} J\sqsubseteq ^{}_{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}} K\Longleftrightarrow \bigwedge ^{\sqsubseteq ^{}_{\varXi ^{}_{}}} J\sqsubseteq ^{}_{\varXi ^{}_{}} \bigwedge ^{\sqsubseteq ^{}_{\varXi ^{}_{}}} K\end{aligned}$$

(87)

Property 112

$(\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}},\vartriangleleft ^{}_{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}})$ is a tree.

Definition 113

(Complete tree of shapes) The complete tree of shapes is the tree $(\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}},\vartriangleleft ^{}_{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}})$.

Let ${\pi }^{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}}_{\varTheta ^{}_{}}: \varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}} \rightarrow \varTheta ^{}_{}$ be the application defined by ${\pi }^{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}}_{\varTheta ^{}_{}}([P]_{{\sim }_{\varTheta ^{}_{}}}) = {\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}(P)$.

Property 114

${\pi }^{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}}_{\varTheta ^{}_{}}$ is bijective.

Fig. 14

The same complete tree of shapes as in Fig. 13, depicted with a tree-like embedding

Fig. 15

The topological tree of shapes of the grey-level image $\mathcal F$ of Fig. 4. This tree is obtained by a decreasing homeomorphism from the complete tree of shapes of Fig. 14. Each node (square) corresponds to an element $[X]_{{\sim }_{H}}$ of $H= \varTheta ^{}_{}/\mathord {{\sim }_{H}}$. The white part of the node corresponds to an element $Y\in [X]_{{\sim }_{H}}$ (which is chosen here arbitrarily). The blue-bordered nodes correspond to unbounded $X$. The green and red arrows correspond to the $\vartriangleleft ^{}_{H}$ relation

Fig. 16

The tree of shapes of the grey-level image $\mathcal F$ of Fig. 4. This tree is obtained by a decreasing homeomorphism from the complete tree of shapes of Fig. 14. The blue-bordered nodes correspond to unbounded $X$. The green and red arrows correspond to the $\vartriangleleft ^{}_{\varTheta ^{\tau }_{}}$ relation. This tree is the same as in Fig. 8 (Color figure online)

This property allows us to define the relation $\sqsubseteq ^{}_{\varTheta ^{}_{}}$ on $\varTheta ^{}_{}$ by

$$\begin{aligned} X\sqsubseteq ^{}_{\varTheta ^{}_{}} Y\Longleftrightarrow \Big ({\pi }^{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}}_{\varTheta ^{}_{}}\Big )^{-1}(X) \sqsubseteq ^{}_{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}} \Big ({\pi }^{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}}_{\varTheta ^{}_{}}\Big )^{-1}(Y) \end{aligned}$$

(88)

with $\sqsubseteq ^{}_{\varTheta ^{}_{}} \ \searrow _{RT}\ \vartriangleleft ^{}_{\varTheta ^{}_{}}$.

Property 115

We have

$$\begin{aligned} |\mathord {\vartriangleleft ^{}_{\varTheta ^{}_{}}}| = |\varTheta ^{}_{}|-1 \end{aligned}$$

(89)

Property 116

We have

$$\begin{aligned} (\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}},\vartriangleleft ^{}_{\varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}}) \equiv (\varTheta ^{}_{},\vartriangleleft ^{}_{\varTheta ^{}_{}}) \end{aligned}$$

(90)

This property motivates the following alternative definition of the complete tree of shapes.

Definition 117

(Complete tree of shapes (alternative)) The complete tree of shapes is the tree ${\mathfrak T}_{\varTheta ^{}_{}} = (\varTheta ^{}_{},\vartriangleleft ^{}_{\varTheta ^{}_{}})$.

Proposition 118

There is a decreasing homeomorphism from the tree of valued shapes to the complete tree of shapes.

The complete tree of shapes of the image $\mathcal F$ of Fig. 4 is illustrated in Fig. 13 and with a tree-like embedding in Fig. 14.

As for the component-trees and the tree of shapes, it is possible to define, for each node $X\in \varTheta ^{}_{}$, an interval $\mathbb I^{\varTheta ^{}_{}}_{X}$ of values at which the connected component $X$ exists in $\mathcal F$ and then a notion of remanence. In particular, this interval and the associated bounding values are the same as in the component-trees.

Definition 119

Let $X\in \varTheta ^{}_{}$. We set $\alpha ^{\varTheta ^{}_{}}_{X} = \alpha ^{\varTheta ^{{\square }}_{}}_{X}$, $\omega ^{\varTheta ^{}_{}}_{X} = \omega ^{\varTheta ^{{\square }}_{}}_{X}$ and $\mathbb I^{\varTheta ^{}_{}}_{X} = \llbracket \alpha ^{\varTheta ^{}_{}}_{X},\omega ^{\varTheta ^{}_{}}_{X}\rrbracket _{\leqslant ^{\square }} = \mathbb I^{\varTheta ^{{\square }}_{}}_{X}$. We define the remanence of $X$ (in the complete tree of shapes) as

$$\begin{aligned} \delta ^{\varTheta ^{}_{}}_{X} = \delta ^{\varTheta ^{{\square }}_{}}_{X} \end{aligned}$$

(91)

The complete tree of shapes is defined from the set of nodes $\varTheta ^{}_{}$. As a consequence, it inherits the notion of external proper part of the valued component-trees to define its own notion of proper part.

Definition 120

(Proper part of a node) For any $X\in \varTheta ^{}_{}$, we define the proper part of $X$ (in the complete tree of shapes) as $\rho ^{\varTheta ^{}_{}}_{X}$ (see Eq. (25)) i.e. as the external proper part of $X$ (in the component-trees).

6.4 Topological Tree of Shapes

Let $X, Y\subseteq \mathbb U$, with $Y\subset X$. We aim to characterize the preservation of topological properties by a decreasing transformation from $X$ to $Y$. A frequent strategy is to consider the notion of homotopic transformation. In particular, if there exists a (decreasing) homotopic transformation from $X$ to $Y$, then $X$ and $Y$ have the same homotopy type. In the discrete frameworks, i.e. when $\mathbb U= \mathbb Z^{d}$ or equivalent combinatorial spaces, this paradigm is tractable for $d= 2$ [20] and under specific conditions for $d= 3$ [2] especially thanks to the notion of simple point [4]. However, it becomes hardly tractable in the general case for $d= 3$ [24, 38] and a fortiori for $d> 3$ [10].

Then, we consider a weaker topological invariant induced by the notion of strongly deletable set introduced in [48].

Definition 121

(Strongly deletable set [48]) Let $\varLambda ^{}_{} \subseteq \mathbb U$. Let $D\subset \varLambda ^{}_{}$. Let $\iota : \varPi [\varLambda ^{}_{} \setminus D] \rightarrow \varPi [\varLambda ^{}_{}]$ and $\overline{\iota }: \varPi [\overline{\varLambda ^{}_{}}] \rightarrow \varPi [\overline{\varLambda ^{}_{} {\setminus } D}]$ be the applications defined by $X\subseteq \iota (X)$ and $Y\subseteq \overline{\iota }(Y)$. We say that $D$ is a strongly deletable set if both $\iota$ and $\overline{\iota }$ are bijective.

Remark 122

In dimension 2 the existence of a strongly deletable set $D\subset X$ implies that there exists a decreasing homotopic transformation from $X$ to $Y= X{\setminus } D$. When $d\ge 3$ this is no longer true in general, since the applications $\iota$ and $\overline{\iota }$ rely on connectedness, but do not handle high level topological features such as tunnels, that appear at dimension 3. Nonetheless, even for $d\ge 3$, the invariance based on strong deletability carries valuable topological information.

Let $P= (X,v), Q= (Y,w) \in \varXi ^{}_{}$ be such that $\zeta ^{}_{\sqsubseteq ^{}_{\varXi ^{}_{}}}(P) = Q$. If $Z_{\sqsubseteq ^{}_{\varXi ^{}_{}}}(Q) = \{P\}$ and $Y{\setminus } X$ is a strongly deletable set for $Y$, then we note $Q\searrow _{D}P$.

Property 123

If $Q\searrow _{D}P$, then we have $\zeta ^{}_{\sqsubseteq ^{}_{\varXi ^{}_{}}}(P) = \varphi (P)$.

Proposition 124

Let $P\in \varXi ^{}_{}$. Let $A= \varPhi (\varphi (P)) \cup \varPsi (\varphi (P))$. Let $B= \{\varphi (P)\} \cup \varPsi (P)$. We have $\varphi (P) \searrow _{D}P$ iff the restricted application $\varphi _{|A}: A\rightarrow B$ is a bijection from $A$ to $B$.

Let ${\sim }_{H}$ be the equivalence relation on $\varXi ^{}_{}$ defined as the reflexive-transitive-symmetric closure of $\searrow _{D}$. We set

$$\begin{aligned} H= \varXi ^{}_{}/\mathord {{\sim }_{H}} \end{aligned}$$

(92)

Property 125

Let $K\in H$. For all $P\in K$, we have either ${\square }(P) = \circ$ or ${\square }(P) = \bullet$.

This property allows us to extend the definition of ${\square }$ and $\blacksquare$ to the nodes of $H$ such that for all $K= [P]_{{\sim }_{T}} \in H$, we have ${\square }(K) = {\square }(P)$ and $\blacksquare (K) = \blacksquare (P)$.

Property 126

We have

$$\begin{aligned} |\varTheta ^{}_{}| \ge |H| = \mathcal O(n) \end{aligned}$$

(93)

Property 127

For all $K\in H$, $(K,\sqsubseteq ^{}_{\varXi ^{}_{}})$ is a totally ordered set.

Let $\sqsubseteq ^{}_{H}$ be the order relation on $H$ defined by

$$\begin{aligned} J\sqsubseteq ^{}_{H} K\Longleftrightarrow \bigwedge ^{\sqsubseteq ^{}_{\varXi ^{}_{}}} J\sqsubseteq ^{}_{\varXi ^{}_{}} \bigwedge ^{\sqsubseteq ^{}_{\varXi ^{}_{}}} K\end{aligned}$$

(94)

with $\sqsubseteq ^{}_{H} \searrow _{RT}\ \vartriangleleft ^{}_{H}$.

Proposition 128

$(H,\vartriangleleft ^{}_{H})$ is a tree.

Property 129

We have

$$\begin{aligned} |\mathord {\vartriangleleft ^{}_{H}}| = |H|-1 \end{aligned}$$

(95)

Definition 130

(Topological tree of shapes) The topological tree of shapes is the tree ${\mathfrak T}_{H} = (H,\vartriangleleft ^{}_{H})$.

Property 131

For any $P, Q\in \varXi ^{}_{}$, we have

$$\begin{aligned} P{\sim }_{\varTheta ^{}_{}} Q\Longrightarrow P{\sim }_{H} Q\end{aligned}$$

(96)

Remark 132

From the above property, we can consider by abuse of notation that ${\sim }_{H}$ is an equivalence relation on $\varXi ^{}_{}$ or on $\varTheta ^{}_{}$, i.e. that $H= \varXi ^{}_{}/\mathord {{\sim }_{H}}$ or $H= \varTheta ^{}_{}/\mathord {{\sim }_{H}}$. In the sequel, we consider $H= \varTheta ^{}_{}/\mathord {{\sim }_{H}}$.

As for the component-trees, the tree of shapes and the complete tree of shapes, it is possible to define, for each node $K\in H$, an interval $\mathbb I^{H}_{K}$ of values at which the node $K$ exists in $\mathcal F$ and then a notion of remanence. In particular, this interval and the associated bounding values are the same as in the component-tree.

The next property has the same structure as Proposition 70 proposed in the case of the tree of shapes.

Fig. 17

a Links between the various hierarchical structures. b Construction of the new hierarchies from the (valued) component-trees and the adjacency trees (Sect. 8.6). c Construction of the new hierarchies from the tree of shapes (Sect. 8.7). Black links: state-of-the-art construction algorithms (Sect. 8.1). Blue links: construction by increasing / decreasing homeomorphism based on intervals (Sect. 8.2). Purple links: construction by decreasing homeomorphism based on equivalence (Sect. 8.5). Green links: construction by aggregation / extraction (Sect. 8.3). Red links: construction by transitive reduction / closure (Sect. 8.4). Pink links: construction by isomorphism (Sect. 8.5). The arrows indicate that one structure can be built from the other. Notations (see also Tab. 1): $\mathcal F$: image, ${\mathfrak T}_{\varTheta ^{\circ }_{}}$: max-tree, ${\mathfrak T}_{\varTheta ^{\bullet }_{}}$: min-tree, ${\mathfrak T}_{\varTheta ^{}_{v}}$: adjacency tree(s), ${\mathfrak T}_{\varXi ^{\circ }_{}}$: valued max-tree, ${\mathfrak T}_{\varXi ^{\bullet }_{}}$: valued min-tree, ${\mathfrak F}_{\varXi ^{}_{}}$: forest of the valued adjacency trees, $\mathfrak G_{\varXi ^{}_{}}$: graph of valued shapes, $\mathfrak G_{\varXi ^{\tau }_{}}$: valued graph of shapes, ${\mathfrak T}_{\varXi ^{\tau }_{}}$: valued tree of shapes, ${\mathfrak T}_{\varXi ^{}_{}}$: tree of valued shapes, ${\mathfrak T}_{\varTheta ^{}_{}}$: complete tree of shapes, ${\mathfrak T}_{H}$: topological tree of shapes, ${\mathfrak T}_{\varTheta ^{\tau }_{}}$: tree of shapes

Property 133

Let $K\in H$. There exist $\alpha ^{H}_{K}, \omega ^{H}_{K} \in \mathbb V$ such that

$$\begin{aligned} \llbracket \alpha ^{H}_{K},\omega ^{H}_{K}\rrbracket _{\leqslant ^{\square }}&= \bigcup _{X\in [K]_{{\sim }_{H}}} \llbracket \alpha ^{\varTheta ^{}_{}}_{X}, \omega ^{\varTheta ^{}_{}}_{X}\rrbracket _{\leqslant ^{\square }} \end{aligned}$$

(97)

$$\begin{aligned}&= \llbracket \bigwedge ^{\leqslant ^{\square }}_{X\in [K]_{{\sim }_{H}}} \alpha ^{\varTheta ^{}_{}}_{X},\bigvee ^{\leqslant ^{\square }}_{X\in [K]_{{\sim }_{H}}} \omega ^{\varTheta ^{}_{}}_{X} \rrbracket _{\leqslant ^{\square }} \end{aligned}$$

(98)

Definition 134

(Remanence of a node) For any $K\in H$, we note $\mathbb I^{H}_{K} = \llbracket \alpha ^{H}_{K},\omega ^{H}_{K}\rrbracket _{\leqslant ^{\square }}$ and we define the remanence of $K$ (in the topological tree of shapes) as

$$\begin{aligned} \delta ^{H}_{K} = |\mathbb I^{H}_{K}| \end{aligned}$$

(99)

Each node of the topological tree of shapes is defined as an equivalence class of nodes of $\varTheta ^{}_{}$. As a consequence, it inherits the notion of proper part of the complete tree of shapes to define its own notion of proper part.

Definition 135

(Proper part of a node) For any $K\in H$, we define the proper part of $K$ (in the topological tree of shapes) as

$$\begin{aligned} \rho ^{H}_{K} = \bigcup _{X\in K} \rho ^{\varTheta ^{}_{}}_{X} \end{aligned}$$

(100)

Remark 136

In practice, it is more convenient to decompose the proper part of $K$ as the sequence of the proper parts of its respective elements, i.e. as

$$\begin{aligned} P^{H}_{K} = \langle \rho ^{\varTheta ^{}_{}}_{K_v} \rangle _{v\in \mathbb I^{H}_{K}} \end{aligned}$$

(101)

where for any $v\in \mathbb I^{H}_{K}$, we have $(K_v,v) \in \varXi ^{}_{}$ and $K_v\in K$. This decomposition will be useful in particular for developing image processing applications from the topological tree of shapes.

Proposition 137

There is a decreasing homeomorphism from the complete tree of shapes to the topological tree of shapes

This homeomorphism can be observed by comparison between the complete tree of shapes and the topological tree of shapes in Figs. 14 and 15.

7 Links Between Usual and New Hierarchies

The graph of valued shapes $\mathfrak G_{\varXi ^{}_{}}$ presents a DAG structure, similarly to other morphological hierarchies, e.g. the component-graph [41], the directed component hierarchy [43] or the braid of partitions [19]. The graph $\mathfrak G_{\varXi ^{}_{}}$ is also organized via two kinds of relations, similarly to the component-hypertree [39] and the directed component hierarchy [43] (where the initial order can be split into two distinct orders).

But, contrary to these morphological hierarchies, $\mathfrak G_{\varXi ^{}_{}}$ can be simplified in a lossless fashion as a tree structure, namely the tree of valued shapes ${\mathfrak T}_{\varXi ^{}_{}}$. This may open the way to efficient construction strategies compared e.g. to the component-hypertree [29], the component-graph [40] or the braid of partitions [58], the construction of which remains complex and/or costly.

Beyond these considerations, the graph of valued shapes $\mathfrak G_{\varXi ^{}_{}}$ and the trees we can derive from it (tree of valued shapes ${\mathfrak T}_{\varXi ^{}_{}}$, complete tree of shapes ${\mathfrak T}_{\varTheta ^{}_{}}$, topological tree of shapes ${\mathfrak T}_{H}$) also allow to build bridges between various morphological trees.

Property 138

The valued max-tree and the valued min-tree are induced subgraphs of the graph of valued shapes.

$$\begin{aligned} {\mathfrak T}_{\varXi ^{\star }_{}} \Subset \mathfrak G_{\varXi ^{}_{}} \end{aligned}$$

(102)

Remark 139

From Proposition 52, there is a decreasing homeomorphism from the valued max-tree (resp. valued min-tree) to the max-tree (resp. min-tree).

$$\begin{aligned} {\mathfrak T}_{\varXi ^{\star }_{}} \searrow _{H}{\mathfrak T}_{\varTheta ^{\star }_{}} \end{aligned}$$

(103)

Property 140

Let $v\in \mathbb V$. From Proposition 83, there is an isomorphism between the adjacency-tree and the valued adjacency-tree at value $v$. In addition, the valued adjacency-tree is an induced subgraph of the graph of valued shapes.

$$\begin{aligned} {\mathfrak T}_{\varTheta ^{}_{v}} \equiv {\mathfrak T}_{\varXi ^{}_{v}} \Subset \mathfrak G_{\varXi ^{}_{}} \end{aligned}$$

(104)

Remark 141

The tree of valued shapes is obtained by transitive reduction of the graph of valued shapes (Sect. 6.2).

$$\begin{aligned} \mathfrak G_{\varXi ^{}_{}} \searrow _{RT}{\mathfrak T}_{\varXi ^{}_{}} \end{aligned}$$

(105)

Remark 142

From Proposition 118, there is a decreasing homeomorphism from the tree of valued shapes to the complete tree of shapes.

$$\begin{aligned} {\mathfrak T}_{\varXi ^{}_{}} \searrow _{H}{\mathfrak T}_{\varTheta ^{}_{}} \end{aligned}$$

(106)

Remark 143

From Proposition 137, there is a decreasing homeomorphism from the complete tree of shapes to the topological tree of shapes.

$$\begin{aligned} {\mathfrak T}_{\varTheta ^{}_{}} \searrow _{H}{\mathfrak T}_{H} \end{aligned}$$

(107)

Proposition 144

There is a decreasing quasi-homeomorphism from the complete tree of shapes to the tree of shapes.

$$\begin{aligned} {\mathfrak T}_{\varTheta ^{}_{}} \searrow _{QH}{\mathfrak T}_{\varTheta ^{\tau }_{}} \end{aligned}$$

(108)

Property 145

If $|\varPi [\tau (\varLambda ^{\circ }_{{\sigma }^{\circ }(\bot )})]| = 1$ (a fortiori if $|\varPi [\varLambda ^{\circ }_{{\sigma }^{\circ }(\bot )}]| = 1$) then there is a decreasing homeomorphism from the complete tree of shapes to the tree of shapes.

$$\begin{aligned} |\varPi [\tau (\varLambda ^{\circ }_{{\sigma }^{\circ }(\bot )})]| = 1 \Longrightarrow {\mathfrak T}_{\varTheta ^{}_{}} \searrow _{H}{\mathfrak T}_{\varTheta ^{\tau }_{}} \end{aligned}$$

(109)

The homeomorphism from the complete tree of shapes to the topological tree of shapes can be observed by comparison between Figs. 14 and 16. Note that in this example, we have $|\varPi [\varLambda ^{\circ }_{{\sigma }^{\circ }(\bot )}]| = 2 \ne 1$ but $|\varPi [\tau (\varLambda ^{\circ }_{{\sigma }^{\circ }(\bot )})]| = 1$, which satisfies the hypothesis of Eq. (109).

The continuum between all the—usual and new—hierarchical structures discussed in this study is illustrated in Fig. 17a.

8 Construction of the Hierarchies

In this section we assume that $\mathbb U$ is discrete and that for any $v> \bot$, we have $|\varLambda ^{\circ }_{v}| \le n$. In particular, $n$ will be considered as the size (i.e. the number of points) of the finite support $\mathbb S$ of the image with $\mathbb S$ connected and $\varLambda ^{\circ }_{v} \subseteq \mathbb S$ for any $v> \bot$.

We discuss on the algorithmic aspects of the construction of the different morphological hierarchies considered in this article. Figure 17 summarizes this discussion.

For the sake of simplicity, we will consider the various trees and graphs defined in their mathematical form. In other words, we will not consider space cost optimization of these structures that would also lead to time cost optimization for their construction.

In the algorithms, we use the following notations:

• “$A:=B$” means that a variable $A$ is set with $B$;

• “$A\leftarrow B$” means that $B$ is added to a variable set $A$;

• “$A\rightarrow B$” means that the variable $B$ is set as an element removed from the variable set $A$.

8.1 Construction of the Usual Hierarchies and Hypotheses

We do not come back to the construction of the usual hierarchies. As already mentioned, there exist efficient algorithms to build from $\mathcal F$:

• the component-tree in $\mathcal O(n\log n)$;

• the tree of shapes in $\mathcal O(n\log n)$;

• the adjacency tree at any threshold value in $\mathcal O(n)$.

We can go from the component-tree (Proposition 44) or from the tree of shapes (Proposition 81) to the initial image $\mathcal F$ with a time cost $\mathcal O(n)$ and from the adjacency-trees at all threshold sets with a time cost $\mathcal O(n\cdot \varDelta )$, with $n$ the size of the image support and $\varDelta$ the number of values of $\mathbb V$.

We assume that for each hierarchy, we have access for any node $X$ to:

• the interval $\mathbb I^{}_{X}$ or equivalently $\alpha ^{}_{X}$ and $\omega ^{}_{X}$;

• the characterizations ${\square }(X)$ and $\blacksquare (X)$;

• the proper part $\rho ^{X}_{}$ of $X$.

The computation of these information has been discussed in Sects. 5–6.

8.2 Construction of Valued Trees from Non-valued Ones (and Vice Versa)

We first give two simple algorithms that allow, on the one hand, the construction of valued trees from non-valued ones, i.e.

• the valued max-tree from the max-tree;

• the valued min-tree from the min-tree;

• the tree of valued shapes from the complete tree of shapes;

• the valued tree of shapes (a technical structure that will be required in Sect. 8.7) from the tree of shapes;

and, on the other hand, the construction of the non-valued trees from the valued ones. Both Algorithms 1 and 2 are presented for the tree of valued shapes vs. the complete tree of shapes; however they remain the same for the other trees. They correspond to the blue arrows in Fig. 17.

Algorithm 1

From $(\varTheta ^{}_{},\vartriangleleft ^{}_{\varTheta ^{}_{}})$ to $(\varXi ^{}_{},\vartriangleleft ^{}_{\varXi ^{}_{}})$

Algorithm 2

From $(\varXi ^{}_{},\vartriangleleft ^{}_{\varXi ^{}_{}})$ to $(\varTheta ^{}_{},\vartriangleleft ^{}_{\varTheta ^{}_{}})$

Property 146

Based on Algorithm 1, we can build:

• the valued min-tree from the min-tree;

• the valued max-tree from the max-tree;

• the tree of valued shapes from the complete tree of shapes;

• the valued tree of shapes from the tree of shapes;

with a time cost $\mathcal O(n\cdot \delta ^{}_{})$.

Property 147

Based on Algorithm 2, we can build

• the min-tree from the valued min-tree;

• the max-tree from the valued max-tree;

• the complete tree of shapes from the tree of valued shapes;

• the tree of shapes from the valued tree of shapes;

with a time cost $\mathcal O(n\cdot \delta ^{}_{})$.

8.3 Construction of the Graph of Valued Shapes from the Component-Trees and Adjacency Trees (and Vice Versa)

The graph of valued shapes is obtained by agglomeration of the nodes of the valued min- and max-trees (or equivalently the nodes of the adjacency-trees) and the edges of the min- and max-trees ($\varphi$) and those of the adjacency-trees ($\psi$). These trivial constructions correspond to the green arrows in Fig. 17.

Property 148

We can build the graph of valued shapes from the valued min- and max-trees and the forest ${\mathfrak F}_{\varXi ^{}_{}}$ which gathers the adjacency-trees (Proposition 87) with a time cost $\mathcal O(1)$.

Property 149

We can build the valued min- and max-trees and the forest ${\mathfrak F}_{\varXi ^{}_{}}$ which gathers the adjacency-trees (Proposition 87) from the graph of valued shapes with a time cost $\mathcal O(1)$.

8.4 Construction of the Tree of Valued Shapes from the Graph of Valued Shapes (and Vice versa)

The graph of valued shapes $\mathfrak G_{\varXi ^{}_{}}$ has the same nodes as the tree of valued shapes ${\mathfrak T}_{\varXi ^{}_{}}$. The difference between both structures lies in the extraction of $\vartriangleleft ^{}_{\varXi ^{}_{}}$ from $\blacktriangleleft _{\varXi ^{}_{}}$ which is a transitive reduction [1] but can be carried out with a lower computational cost due to the specific configurations of $\blacktriangleleft _{\varXi ^{}_{}}$. In particular, based on the analysis proposed in Sect. 6.2, we can perform an exhaustive search of the transitive patterns formalized by Eqs. (81–83), which leads to the procedure described in Algorithm 3. This transitive reduction procedure is reversible, and the reverse procedure described in Algorithm 4 allows to build the graph of valued shapes $\mathfrak G_{\varXi ^{}_{}}$ from the tree of valued shapes ${\mathfrak T}_{\varXi ^{}_{}}$. These procedures correspond to the red arrows in Fig. 17.

Property 150

The tree of valued shapes ${\mathfrak T}_{\varXi ^{}_{}}$ can be built from the graph of valued shapes $\mathfrak G_{\varXi ^{}_{}}$ by Algorithm 3 with a time cost $\mathcal O(n\cdot \delta ^{}_{})$.

Property 151

The graph of valued shapes $\mathfrak G_{\varXi ^{}_{}}$ can be built from the tree of valued shapes ${\mathfrak T}_{\varXi ^{}_{}}$ by Algorithm 4 with a time cost $\mathcal O(n\cdot \delta ^{}_{})$.

Algorithm 3

From $(\varXi ^{}_{}, \blacktriangleleft _{\varXi ^{}_{}})$ to $(\varXi ^{}_{},\vartriangleleft ^{}_{\varXi ^{}_{}})$

Algorithm 4

From $(\varXi ^{}_{},\vartriangleleft ^{}_{\varXi ^{}_{}})$ to $(\varXi ^{}_{},\blacktriangleleft _{\varXi ^{}_{}})$

8.5 Construction of the Tree of Shapes and the Topological Tree of Shapes

The topological tree of shapes ${\mathfrak T}_{H}$ gathers in $H$ the nodes of the complete tree of shapes ${\mathfrak T}_{\varTheta ^{}_{}}$ as equivalence classes, and directly inherits its relation $\vartriangleleft ^{}_{H}$ from $\vartriangleleft ^{}_{\varTheta ^{}_{}}$. In practice, it is convenient to build ${\mathfrak T}_{H}$ from both ${\mathfrak T}_{\varTheta ^{}_{}}{}{}$ (in order to build the edges) and $\mathfrak G_{\varXi ^{}_{}}$ (in order to characterize the equivalence classes of nodes of $\varTheta ^{}_{}$). Indeed, the construction of $H$ can be performed from Proposition 124 by scanning the structure of ad hoc nodes in $\mathfrak G_{\varXi ^{}_{}}$. This procedure is described in Algorithm 5.

Property 152

The topological tree of shapes ${\mathfrak T}_{H}$ can be built from the complete tree of shapes ${\mathfrak T}_{\varTheta ^{}_{}}$ and the graph of valued shapes $\mathfrak G_{\varXi ^{}_{}}$ by Algorithm 5 with a time cost $\mathcal O(n\cdot \partial ^{-}_{}(\psi ))$.

Remark 153

If $\mathbb U= \mathbb Z^2$, the notion of strongly deletable set is equivalent to the notion of simple set [38]. This implies that if $X\setminus Y$ is strongly deletable, then $X$ and $Y$ have the same homotopy type and $Y$ is obtained from $X$ by a decreasing homotopic transformation defined as the iterative removal of a sequence of simple points [4].

This remark straightforwardly leads to the following property.

Property 154

If $\mathbb U= \mathbb Z^2$, then the topological tree of shapes ${\mathfrak T}_{H}$ can be built from the complete tree of shapes ${\mathfrak T}_{\varTheta ^{}_{}}$ with a time cost $\mathcal O(n)$.

The tree of shapes ${\mathfrak T}_{\varTheta ^{\tau }_{}} =(\varTheta ^{\tau }_{},\vartriangleleft ^{}_{\varTheta ^{\tau }_{}})$ is composed by nodes of $\varTheta ^{\tau }_{}$ which are defined as the topological closing of nodes of $\varTheta ^{}_{}$. Equivalently, the tree of shapes can be defined as ${\mathfrak T}_{T} =(T,\vartriangleleft ^{}_{T})$. The equivalence classes of $T$ can be computed from the complete tree of shapes ${\mathfrak T}_{\varTheta ^{}_{}}$, and the tree of shapes directly inherits its relation $\vartriangleleft ^{}_{T}$ from $\vartriangleleft ^{}_{\varTheta ^{}_{}}$. The corresponding procedure is described in Algorithm 6.

Property 155

The tree of shapes ${\mathfrak T}_{\varTheta ^{\tau }_{}}$ can be built from the complete tree of shapes ${\mathfrak T}_{\varTheta ^{}_{}}$ by Algorithm 5 with a time cost $\mathcal O(n)$.

Remark 156

The procedures for building the tree of shapes and the topological tree of shapes both rely on the same algorithmic scheme. They differ only with regard to the considered equivalence relation and the way it leads to gather nodes of $\varTheta ^{}_{}$ as equivalence classes either in $T$ or $H$ (see line 14 in Algorithms 5–6).

Algorithm 5

From $(\varTheta ^{}_{}, \vartriangleleft ^{}_{\varTheta ^{}_{}})$ and $(\varXi ^{}_{},\blacktriangleleft _{\varXi ^{}_{}})$ to $(H,\vartriangleleft ^{}_{H})$

Algorithm 6

From $(\varTheta ^{}_{}, \vartriangleleft ^{}_{\varTheta ^{}_{}})$ to $(\varTheta ^{\tau }_{},\vartriangleleft ^{}_{\varTheta ^{\tau }_{}})$

8.6 Construction of the New Hierarchies from the Component-Trees and Adjacency Trees

Based on the above algorithmic discussion, it appears that we can build the graph of valued shapes, the tree of valued shapes, the complete tree of shapes and the topological tree of shapes from the (valued) min- and max-trees and the forest ${\mathfrak F}_{\varXi ^{}_{}}$ which gathers the adjacency-trees (Proposition 87). The corresponding workflow is illustrated by Fig. 17b.

It is worth mentioning that this algorithmic scheme, which goes from the min- and max-trees to the topological tree of shapes, is somehow similar to the algorithmic scheme proposed in [27] for building the tree of shapes. Basically, in both cases, the initial data are the nodes of two trees (the min- and max-trees), which are then gathered in a same tree. In [27], the nodes of the component-trees are explicitly hole-filled. In our approach, this hole-filling (formalized by the $\tau$ function) is not explicitly carried out and the tree of shapes may be obtained, similarly to the topological tree of shapes, via the definition of a decreasing homeomorphism acting on the complete tree of shapes.

Property 157

The graph of valued shapes, the tree of valued shapes, the complete tree of shapes and the topological tree of shapes can be built from $\mathcal F$ via its (valued) min- and max-trees and its adjacency trees with a time cost $\mathcal O(n.(\log n+ \varDelta + \partial ^{-}_{}(\psi )))$.

Remark 158

In most cases, we have

$$\begin{aligned} \log n+ \partial ^{-}_{}(\psi ) \ll \varDelta \end{aligned}$$

(110)

and then the actual time cost for building the new hierarchies is $\mathcal O(n\cdot \varDelta )$, i.e. it is simultaneously linear with respect to the size of the support ${\mathbb S}$ of the image and the size of the set of values $\mathbb V$.

8.7 Construction of the New Hierarchies from the Tree of Shapes

We now describe an alternative way of building the graph of valued shapes, the tree of valued shapes, the complete tree of shapes and the topological tree of shapes from the tree of shapes. The corresponding workflow is illustrated in Fig. 17c.

This strategy relies on two structures, denoted as ${\mathfrak T}_{\varXi ^{\tau }_{}}$ and $\mathfrak G_{\varXi ^{\tau }_{}}$. The first one, ${\mathfrak T}_{\varXi ^{\tau }_{}}$ is called the valued tree of shapes. It is a valued version of the tree of shapes, defined as follows.

We set $\varXi ^{\tau }_{}$ as

$$\begin{aligned} \varXi ^{\tau }_{} = \bigcup _{X\in \varTheta ^{\tau }_{}} \{X\} \times \mathbb I^{\varTheta ^{\tau }_{}}_{X} \end{aligned}$$

(111)

and the relation $\vartriangleleft ^{}_{\varXi ^{\tau }_{}}$ on $\varXi ^{\tau }_{}$ by

$$\begin{aligned} \forall v\in \mathbb I^{\varTheta ^{\tau }_{}}_{X} \setminus \{\omega ^{\varTheta ^{\tau }_{}}_{X}\}, (X,{\sigma }^{{\square }}(v))&\vartriangleleft ^{}_{\varXi ^{\tau }_{}} (X,v) \end{aligned}$$

(112)

$$\begin{aligned} (X,\alpha ^{\varTheta ^{\tau }_{}}_{X})&\vartriangleleft ^{}_{\varXi ^{\tau }_{}} (\zeta ^{}_{\vartriangleleft ^{}_{\varTheta ^{\tau }_{}}}(X),\omega ^{\varTheta ^{\tau }_{}}_{\zeta ^{}_{\vartriangleleft ^{}_{\varTheta ^{\tau }_{}}}(X)}) \end{aligned}$$

(113)

It is plain that ${\mathfrak T}_{\varXi ^{\tau }_{}}$ is built from ${\mathfrak T}_{\varTheta ^{\tau }_{}}$ by Algorithm 1.

Moreover, we have the following property.

Property 159

We have

$$\begin{aligned} {\mathfrak T}_{\varXi ^{\tau }_{}} \equiv {\mathfrak T}_{\varXi ^{}_{}} \end{aligned}$$

(114)

The second structure, $\mathfrak G_{\varXi ^{\tau }_{}} = (\varXi ^{\tau }_{},\blacktriangleleft _{\varXi ^{\tau }_{}})$ is obtained by applying Algorithm 4 with ${\mathfrak T}_{\varXi ^{\tau }_{}}$ as input. By construction, we then have the following property.

Property 160

We have

$$\begin{aligned} \mathfrak G_{\varXi ^{\tau }_{}} \equiv \mathfrak G_{\varXi ^{}_{}} \end{aligned}$$

(115)

Nevertheless, at this stage, having access to $\mathfrak G_{\varXi ^{\tau }_{}}$ is not equivalent with having access to $\mathfrak G_{\varXi ^{}_{}}$. In particular, for any $P^\tau = (X^\tau ,v) \in \varXi ^{\tau }_{}$, the node $P= (X,v) \in \varXi ^{}_{}$ in bijection with $P^\tau$ (with $X^\tau = \tau (X)$) is not yet characterized since $X$ is unknown.

In a first time, we can check for two nodes $P= (X,v), Q= (W,w) \in \varXi ^{}_{}$ if $X= W$ by observing the nodes $P^\tau = (X^\tau ,v) \in \varXi ^{\tau }_{}$ and $Q^\tau = (W^\tau ,w) \in \varXi ^{\tau }_{}$. This can be done by the following formula:

$$\begin{aligned} X= W\Longleftrightarrow (X^\tau = W^\tau ) \wedge \Big (\bigcup _{(Y,v) \in \varPsi (P)} \{Y^\tau \} = \bigcup _{(Z,w) \in \varPsi (Q)} \{Z^\tau \}\Big ) \end{aligned}$$

(116)

The equalities of the right hand side term can be assessed easily since $\varXi ^{\tau }_{}$ has been built from $\varTheta ^{\tau }_{}$.

For each identified node $X\in \varTheta ^{}_{}$, the external proper part $\rho ^{\varTheta ^{}_{}}_{X}$ of $X$ can be defined from the proper part $\rho ^{\varTheta ^{\tau }_{}}_{X}$ available in the tree of shapes ${\mathfrak T}_{\varTheta ^{\tau }_{}}$ (Proposition 75) and the proper part $\rho ^{\varTheta ^{{\square }}_{}}_{X}$ can be obtained from the external proper part $\rho ^{\varTheta ^{}_{}}_{X}$ (Proposition 100).

Property 161

The graph of valued shapes, the tree of valued shapes, the complete tree of shapes and the topological tree of shapes can be built from $\mathcal F$ via its tree of shapes with a time cost $\mathcal O(n.(\log n+ \delta ^{}_{} + \partial ^{-}_{}(\psi )))$.

Remark 162

In many cases, we have

$$\begin{aligned} \log n\simeq \partial ^{-}_{}(\psi ) \simeq \delta ^{}_{} \end{aligned}$$

(117)

and then the actual time cost for building the new hierarchies is $\mathcal O(n\cdot \delta ^{}_{})$, i.e. it is simultaneously linear with respect to the size of the support ${\mathbb S}$ and the dynamics of the image. Building the new hierarchies from the tree of shapes is, in particular, less costly than from the component-trees and adjacency trees (Sect. 8.6).

9 Discussion

When starting this work, we initially designed the notion of a graph of valued shapes by gathering the min- / max-trees and adjacency trees with a precise idea in mind. Indeed, our initial purpose was to develop adequate tools that would allow us to carry out the topological analysis of objects in non-binary paradigms (e.g. for grey-level images or fuzzy modeling), especially for understanding the topological alterations induced on numerical images by geometric transformations [37].

In this section we provide preliminary elements of discussion related to the links that exist between the proposed hierarchical structures and other topological invariants and descriptors adapted to grey-level image analysis.

9.1 Links with the Topological Monotonic Tree

In [57], the notion of a topological monotonic tree was introduced. In this article, the term “monotonic tree” actually referred to the notion of a tree of shapes. As a consequence, the tree proposed in that work was also a “topological tree of shapes”, such as the topological tree of shapes (Definition 130) proposed in our work. Both trees are related but actually distinct.

The topological monotonic tree proposed in [57] can be seen as a compression of the usual tree of shapes. In particular, it can be defined as follows. Let ${{{\smallfrown _{M}}}}$ be the relation defined in $\varTheta ^{\tau }_{}$ by

$$\begin{aligned} X{{{\smallfrown _{M}}}} Y\Longleftrightarrow Z_{\varTheta ^{\tau }_{}}(X) = \{Y\} \end{aligned}$$

(118)

Let ${\sim }_{M}$ be the equivalence relation obtained by reflexive-transitive-symmetric closure of ${{{\smallfrown _{M}}}}$. We set

$$\begin{aligned} M= \varTheta ^{\tau }_{}/\mathord {{\sim }_{M}} \end{aligned}$$

(119)

Each equivalence class of ${\sim }_{M}$ gathers the nodes of a (maximal) branch without bifurcation of the tree of shapes so that the obtained tree, noted ${\mathfrak T}_{M} = (M,\vartriangleleft ^{}_{M})$ has the same structure as the tree of shapes. In particular, the topological monotonic tree ${\mathfrak T}_{M}$ can be built from the tree of shapes ${\mathfrak T}_{\varTheta ^{\tau }_{}}$ by applying an algorithm similar to Algorithms 5–6, by simply modifying line 14 to introduce the characterization of Eq. (118).

By a proof similar to the proof of Proposition 144, we have the following result.

Property 163

There is a decreasing quasi-homeomorphism from the tree of shapes ${\mathfrak T}_{\varTheta ^{\tau }_{}}$ to the topological monotonic tree ${\mathfrak T}_{M}$.

$$\begin{aligned} {\mathfrak T}_{\varTheta ^{\tau }_{}} \searrow _{QH}{\mathfrak T}_{M} \end{aligned}$$

(120)

In practice, Eq. (118) could be alternatively defined on the nodes of $\varTheta ^{}_{}$, i.e. for the complete tree of shapes, then leading to an equivalence relation ${\sim }_{M}$ on $\varTheta ^{}_{}$. In addition, the equivalence relation ${\sim }_{H}$ is a subrelation of ${\sim }_{M}$, and it is then possible to define the equivalence relation ${\sim }_{M}$ on $H$. In these two cases, the topological monotonic tree ${\mathfrak T}_{M}$ can then also be built from the complete tree of shapes ${\mathfrak T}_{\varXi ^{}_{}}$ and from the topological tree of shapes ${\mathfrak T}_{H}$ by the same algorithm as Algorithms 5–6.

By a proof similar to the proof of Proposition 144, we have the following result.

Property 164

There is a decreasing quasi-homeomorphism from the topological tree of shapes ${\mathfrak T}_{H}$ to the topological monotonic tree ${\mathfrak T}_{M}$.

$$\begin{aligned} {\mathfrak T}_{H} \searrow _{QH}{\mathfrak T}_{M} \end{aligned}$$

(121)

9.2 Links with Persistent Homology

Persistent homology [13, 14] aims at analysing the evolution of the homology groups of an object $\mathcal K$ with respect to a given filtration. In general, the analysis takes place in $\mathbb R^{d+1}$ ($d\ge 1$), endowed with its canonical basis $\{\textbf{e}_i\}_{i=0}^{d}$. The object $\mathcal K$ is defined as a subset of $\mathbb U= \mathbb R^{d}$, generated by $\{\textbf{e}_i\}_{i=1}^{n}$, whereas the filtration is defined in $\mathbb K= \mathbb R$ generated by $\{\textbf{e}_0\}$ so that $\mathbb R^{n+1} = \mathbb U\oplus \mathbb K$. In general, the result $\mathcal K_t\in \mathbb U$ of the filtration of $\mathcal K$ at value $t\in \mathbb K$, is defined as $\mathcal K_t= \mathcal K\cap (\textbf{t} + \mathbb U)$ with $\textbf{t} = t\cdot \textbf{e}_0$.

In particular, $\mathcal K_t$ is topologically described by its $d$ homology groups $\langle \mathcal H_i(\mathcal K_t) \rangle _{i=0}^{d-1}$. For each $0 \le i \le d-1$, the evolution of the homology group $\mathcal H_i(\mathcal K_t)$ with respect to $t\in (-\infty ,+\infty )$ is then assessed.

In the context of grey-level imaging, the object $\mathcal K$ corresponds to the image $\mathcal F$ and we set $\mathbb K= \mathbb V$. In particular, for any $v\in \mathbb V$ each $\mathcal K_v$ corresponds to $\varLambda ^{\circ }_{v}$.

The first homology group $\mathcal H_0(\varLambda ^{\circ }_{v})$ corresponds to the connected components of $\varLambda ^{\circ }_{v}$, namely $\varPi [\varLambda ^{\circ }_{v}]$, whereas the $d$th homology group $\mathcal H_{d-1}(\varLambda ^{\circ }_{v})$ corresponds to the “holes” of $\varLambda ^{\circ }_{v}$, i.e. the connected components of $\varLambda ^{\bullet }_{v}$ except the unbounded one, namely $\varPi [\varLambda ^{\bullet }_{v}] \setminus \{\mathbb U_v\}$. When $d> 2$, there exist other homology groups $\mathcal H_i(\varLambda ^{\circ }_{v})$ ($0< i< d$) which are not captured by the notion of connectedness (e.g. the notion of tunnel that corresponds to the second homology group for $d= 3$). We focus here only on the first and $d$th homology groups.

When considering two successive values $u, v\in \mathbb V$ (i.e. $v= {\sigma }^{}(u)$), we say that an element $E$ of a homology group persists if it exists both in $\mathcal H_i(\varLambda ^{\circ }_{u})$ and $\mathcal H_i(\varLambda ^{\circ }_{v})$.

In the case of the first (resp. $d$th) homology group, this means that a connected component in $\varPi [\varLambda ^{\circ }_{u}]$ (resp. $\varPi [\varLambda ^{\bullet }_{u}] \setminus \{\mathbb U_u\}$) still exists in $\varPi [\varLambda ^{\circ }_{v}]$ (resp. $\varPi [\varLambda ^{\bullet }_{v}] \setminus \{\mathbb U_v\}$) possibly with evolution of its geometry, but without being split or merged with other connected components. For each $E$, we then observe its evolution, from its “birth” (by creation, splitting, merging) to its “death” (by deletion, splitting, merging) along the values of $\mathbb K$. In particular, we store the values $b_E, d_E\in \mathbb K$ of birth and death of $E$. The homology persistence diagram is formed by all the elements $E$ for all the homology groups, endowed with their values $b_E, d_E$.

The max-tree ${\mathfrak T}_{\varTheta ^{\circ }_{}}$ (resp. the min-tree ${\mathfrak T}_{\varTheta ^{\bullet }_{}}$) of $\mathcal F$ allows to model the part of the homology persistence diagram corresponding to the first (resp. $d$th) homology group. In particular, the following property formalizes this fact.

Property 165

Let $\mathcal F$ be a grey-level image. Let ${\mathfrak T}_{\varTheta ^{\circ }_{}}$ and ${\mathfrak T}_{\varTheta ^{\bullet }_{}}$ be the max- and min-tree of $\mathcal F$, respectively and let $\sqsubseteq ^{}_{\varTheta ^{\circ }_{}}$ and $\sqsubseteq ^{}_{\varTheta ^{\bullet }_{}}$ be the order relations associated to $\vartriangleleft ^{}_{\varTheta ^{\circ }_{}}$ and $\vartriangleleft ^{}_{\varTheta ^{\bullet }_{}}$, respectively.

• The part of the persistence diagram of $\mathcal F$ corresponding to the first homology group is isomorphic with $(\varTheta ^{\circ }_{},\widetilde{\vartriangleleft ^{}_{\varTheta ^{\circ }_{}}})$ where $\widetilde{\vartriangleleft ^{}_{\varTheta ^{\circ }_{}}} \in \mathcal M(\sqsubseteq ^{}_{\varTheta ^{\circ }_{}})$ is the Hasse function of a maximal piecewise total suborder of $\sqsubseteq ^{}_{\varTheta ^{\circ }_{}}$ (see Definition 13).

• The part of the persistence diagram of $\mathcal F$ corresponding to the $d$th homology group is isomorphic with $(\varTheta ^{\bullet }_{},\widetilde{\vartriangleleft ^{}_{\varTheta ^{\bullet }_{}}})$ where $\widetilde{\vartriangleleft ^{}_{\varTheta ^{\bullet }_{}}} \in \mathcal M((\sqsubseteq ^{}_{\varTheta ^{\bullet }_{}})$ is the Hasse function of a maximal piecewise total suborder of $\sqsubseteq ^{}_{\varTheta ^{\bullet }_{}}$. (In practice, $(\varTheta ^{\bullet }_{},\widetilde{\vartriangleleft ^{}_{\varTheta ^{\bullet }_{}}})$ contains an extra element that corresponds to the unbounded connected components of the background.)

More precisely, each connected set that persists in the diagram corresponds to a degenerate tree of the degenerate forest $(\varTheta ^{\circ }_{},\widetilde{\vartriangleleft ^{}_{\varTheta ^{\circ }_{}}})$ or $(\varTheta ^{\bullet }_{},\widetilde{\vartriangleleft ^{}_{\varTheta ^{\bullet }_{}}})$.

Note that the min- and max-trees were already used years ago as topological invariants for grey-level images (see e.g. [34]), whereas the links between homology persistence and mathematical morphology structures continue to be an active research field [5].

There exist, in general, many maximal piecewise total suborders for a same hierarchical order (Proposition 15). This emphasizes that the way of defining the persistence of the elements of the first and $d$th homology groups is not unique. Indeed, when many connected components of the object (resp. the complementary of the objects) are merged, we consider arbitrarily that one of them persists, whereas the others die.

Modeling the first and $d$th homology groups of a grey-level image via its max- and min-trees is then relevant, since it provides the whole information required to handle these homology groups, plus additional information about:

• the embedding of the elements of the homology groups in $\mathbb U$;

• the information about the elements that are split and merged.

In this context, considering the graph of valued shapes also allows to have access to complementary information regarding the adjacency links between the elements of the first and $d$th homology groups, an important information that is not natively provided by the standard persistence homology diagrams.

10 Conclusion

In this work, we have proposed new hierarchical structures in the framework of mathematical morphology. These new trees and graph allow to establish a continuum between usual morphological hierarchies, in particular the component-tree and the tree of shapes. We also described all these former and new hierarchical structures in a unified framework.

We proposed some algorithmic solutions for building the new hierarchies. This is a preliminary study, and we will investigate some optimized ways for storing them with a lower space cost, but also to construct them with a lower time cost. Indeed, at this stage, we built upon the algorithms of other tree construction, whereas such step may be avoided. We could also investigate some distributed algorithms, for instance by finding inspiration in related works dedicated to the construction of component-trees of very large images (in space or spectrum) [15, 30] and out-of-core approaches for tree structure computation [12].

By side effect, we will also aim to propose some efficient implementations for building and using these new structures. Currently, we developed a first prototype based on Higra [42] and additionally on standard graph manipulation libraries. A full integration in Higra in order to popularize and facilitate the use of these structures is a short term perspective.

We will also develop some new image processing tools based on the proposed hierarchical morphologies, with a specific focus on image simplification / compression and topological noise removal.

In Sect. 9, we started a discussion about the perspectives offered by these new hierarchies with regard to topology. We will deepen the investigations on the links that may be established with persistence homology. In addition, other research trails may be considered. On the one hand, we will study the links that may exist between the notions of topological tree of shapes and the topology-preserving transformations it allows to define, with other paradigms of topology-preserving transformations developed for grey-level or fuzzy images [3, 11, 51]. On the other hand, we will study how some topology-preserving simplifications of grey-level images could allow to use some vectorized versions of images [18], thus opening the way to the extension of paradigms of topology-preserving transformation relying on polygonal representations of digital binary objects [33].

Appendices

A Technical Results on Tree (quasi-)Homeomorphisms

1.1 A.1 (Quasi-)homeomorphisms and Suborders

Let $A$ be a set and $\sqsubseteq ^{}_{A}$ a hierarchical order on $A$.

Let $\sqsubseteq ^{0}_{A}$ and $\sqsubseteq ^{1}_{A}$ be two (piecewise hierarchical) suborders of $\sqsubseteq ^{}_{A}$ with $\sqsubseteq ^{0}_{A} \ \searrow _{RT}\ \vartriangleleft ^{0}_{A}$ and $\sqsubseteq ^{1}_{A} \ \searrow _{RT}\ \vartriangleleft ^{1}_{A}$ such that

$$\begin{aligned} \vartriangleleft ^{0}_{A} \cup \vartriangleleft ^{1}_{A}&= \ \vartriangleleft ^{}_{} \end{aligned}$$

(122)

$$\begin{aligned} \vartriangleleft ^{0}_{A} \cap \vartriangleleft ^{1}_{A}&= \emptyset \end{aligned}$$

(123)

(124)

We also consider the following condition

$$\begin{aligned} \bigvee ^{\sqsubseteq ^{}_{A}} A\in \bigtriangleup ^{\sqsubseteq ^{0}_{A}} A \end{aligned}$$

(125)

that may be fulfilled or not. Eq. (124) means that $\sqsubseteq ^{0}_{A}$ is a suborder of the induced piecewise total suborder of $\sqsubseteq ^{}_{A}$. Eq. (125) means that the maximum of $\sqsubseteq ^{}_{A}$ is a minimal element of $\sqsubseteq ^{0}_{A}$.

Remark 166

From Eq. (124), $\sqsubseteq ^{0}_{A}$ is a piecewise total order, i.e. $(A,\vartriangleleft ^{0}_{A})$ is a degenerate forest.

Let $\alpha ^{}_{A}: \bigtriangleup ^{\sqsubseteq ^{0}_{A}} A\rightarrow \bigtriangledown ^{\sqsubseteq ^{0}_{A}} A$ be the bijective application defined for all $x\in \bigtriangleup ^{\sqsubseteq ^{0}_{A}} A$ by $\alpha ^{}_{A}(x) =\bigvee ^{\sqsubseteq ^{0}_{A}} x_{\sqsubseteq ^{0}_{A}}^\uparrow$.

Let $\widehat{A}= \bigtriangleup ^{\sqsubseteq ^{0}_{A}} A$.

Let $\vartriangleleft ^{}_{\widehat{A}}$ be the relation on $\widehat{A}$ defined by

$$\begin{aligned} x\vartriangleleft ^{}_{\widehat{A}} y\Longleftrightarrow \alpha ^{}_{A}(x) \vartriangleleft ^{}_{A} y\end{aligned}$$

(126)

Property 167

$(\widehat{A},\vartriangleleft ^{}_{\widehat{A}})$ is a tree.

Lemma 168

If the hypotheses of Eqs. (122–125) hold, then we have

$$\begin{aligned} (A,\vartriangleleft ^{}_{A}) \searrow _{H}(\widehat{A},\vartriangleleft ^{}_{\widehat{A}}) \end{aligned}$$

(127)

Proof

The proof is by induction on $p= |\mathord {\vartriangleleft ^{0}_{A}}| \in \mathbb N$.

Initialization – Let $p= 0$, i.e. $\vartriangleleft ^{0}_{A} \ = \emptyset$. The relation $\sqsubseteq ^{0}_{A}$ is $=$ on $A$ and it satisfies Eqs. (124–125). We have $\widehat{A}= \bigtriangleup ^{\sqsubseteq ^{0}_{A}} A= \bigtriangledown ^{\sqsubseteq ^{0}_{A}} A= A$. The application $\alpha ^{}_{A}: A\rightarrow A$ is $\text {id}_{A}$. From Eq. (126) we have $\vartriangleleft ^{}_{\widehat{A}} \ = \ \vartriangleleft ^{1}_{A}$. From Eq. (122) we have $\vartriangleleft ^{1}_{A} \ = \ \vartriangleleft ^{}_{A}$. Then we have $\vartriangleleft ^{}_{\widehat{A}} \ =\ \vartriangleleft ^{}_{A}$. It comes $(A,\vartriangleleft ^{}_{A}) = (\widehat{A},\vartriangleleft ^{}_{\widehat{A}})$ and thus $(A,\vartriangleleft ^{}_{A}) \searrow _{H}(\widehat{A},\vartriangleleft ^{}_{\widehat{A}})$.

Induction – Let $p> 0$. We suppose that the property holds for any $0 \le k\le p-1$. We have $\vartriangleleft ^{0}_{A} \ne \emptyset$. Then there exists $(a,b) \in A\times A$ such that $a\vartriangleleft ^{0}_{A} b$. We choose $a\in A$ accordingly. We have $b= \zeta ^{}_{\vartriangleleft ^{0}_{A}}(a) \notin \bigtriangleup ^{\sqsubseteq ^{0}_{A}} A$. Two cases can occur: (C1) $b\notin \bigtriangledown ^{\sqsubseteq ^{0}_{A}} A$ or (C2) $b\in \bigtriangledown ^{\sqsubseteq ^{0}_{A}} A$. If (C1) there exists $c\in A$ such that $c= \zeta ^{}_{\vartriangleleft ^{0}_{A}}(b)$. If (C2), from Eq. (125) we have $b\ne \bigvee ^{\sqsubseteq ^{}_{A}} A$. Then there exists $c\in A$ such that $c= \zeta ^{}_{\vartriangleleft ^{}_{A}}(b)$. It follows from Eqs. (122–123) that $c= \zeta ^{}_{\vartriangleleft ^{1}_{A}}(b)$.

Let $B= A\setminus \{b\}$. From Eq. (124), we have $Z_{\vartriangleleft ^{}_{}}(b) = \{a\}$. We define the relation $\vartriangleleft ^{}_{B}$ on $B$ as follows: $\zeta ^{}_{\vartriangleleft ^{}_{B}}(x) = \zeta ^{}_{\vartriangleleft ^{}_{A}}(x)$ for any $x\in B{\setminus } \{a, \bigvee ^{\sqsubseteq ^{}_{A}} A\}$ and $\zeta ^{}_{\vartriangleleft ^{}_{B}}(a) = \zeta ^{}_{\vartriangleleft ^{}_{A}}(\zeta ^{}_{\vartriangleleft ^{}_{A}}(a)) = c$. From Definition 21, we have $(A,\vartriangleleft ^{}_{A}) \searrow _{EH}(B,\vartriangleleft ^{}_{B})$. In particular $(B,\vartriangleleft ^{}_{B})$ is a tree. We note $\sqsubseteq ^{}_{B}$ the hierarchical order defined as the reflexive-transitive closure of $\vartriangleleft ^{}_{B}$.

The relation $\vartriangleleft ^{}_{B}$ can be subdivided into $\vartriangleleft ^{0}_{B}$ and $\vartriangleleft ^{1}_{B}$ defined as follows: (C1) $\zeta ^{}_{\vartriangleleft ^{0}_{B}}(a) = \zeta ^{}_{\vartriangleleft ^{0}_{A}}(\zeta ^{}_{\vartriangleleft ^{0}_{A}}(a))$ or (C2) $\zeta ^{}_{\vartriangleleft ^{1}_{B}}(a) = \zeta ^{}_{\vartriangleleft ^{1}_{A}}(\zeta ^{}_{\vartriangleleft ^{0}_{A}}(a))$, and for all $x\in B\setminus \{a, \bigvee ^{\sqsubseteq ^{}_{A}} A\}$, if $x\in \bigtriangledown ^{\sqsubseteq ^{0}_{A}} A$ then $\zeta ^{}_{\vartriangleleft ^{1}_{B}}(x) = \zeta ^{}_{\vartriangleleft ^{1}_{A}}(x)$ and if $x\notin \bigtriangledown ^{\sqsubseteq ^{0}_{A}} A$ then $\zeta ^{}_{\vartriangleleft ^{0}_{B}}(x) = \zeta ^{}_{\vartriangleleft ^{0}_{A}}(x)$. By definition, we have $|\mathord {\vartriangleleft ^{0}_{B}}| = |\mathord {\vartriangleleft ^{0}_{A}}| - 1 = p-1$ and $|\mathord {\vartriangleleft ^{1}_{B}}| = |\mathord {\vartriangleleft ^{1}_{A}}|$. We also have $\vartriangleleft ^{0}_{B} \cup \vartriangleleft ^{1}_{B} \ = \ \vartriangleleft ^{}_{B}$ and $\vartriangleleft ^{0}_{B} \cap \vartriangleleft ^{1}_{B} = \emptyset$.

The order relation $\sqsubseteq ^{0}_{B}$ induced by the reflexive-transitive closure of $\vartriangleleft ^{0}_{B}$ is a suborder of the induced piecewise suborder of $\sqsubseteq ^{}_{B}$ and the maximum of $\sqsubseteq ^{}_{B}$ is a minimal element of $\sqsubseteq ^{0}_{B}$.

Let $\alpha ^{}_{B}: \bigtriangleup ^{\sqsubseteq ^{0}_{B}}B\rightarrow \bigtriangledown ^{\sqsubseteq ^{0}_{B}}B$ be the bijective application defined for all $x\in \bigtriangleup ^{\sqsubseteq ^{0}_{B}}B$ by $\alpha ^{}_{B}(x) =\bigvee ^{\sqsubseteq ^{0}_{B}} x_{\sqsubseteq ^{0}_{B}}^\uparrow$. Since $b\notin \bigtriangleup ^{\sqsubseteq ^{0}_{A}} A$ we have $\bigtriangleup ^{\sqsubseteq ^{0}_{B}}B= \bigtriangleup ^{\sqsubseteq ^{0}_{A}} A$. Let $z= \bigwedge ^{\sqsubseteq ^{0}_{A}} a_{\sqsubseteq ^{0}_{A}}^\downarrow$. For all $x\in \bigtriangleup ^{\sqsubseteq ^{0}_{B}} B\setminus \{z\}$, we have $\alpha ^{}_{B}(x) = \alpha ^{}_{A}(x)$, whereas (C1) $\alpha ^{}_{B}(z) = \alpha ^{}_{A}(z)$ or (C2) $\alpha ^{}_{B}(z) = a$.

We note $\widehat{B}= \bigtriangleup ^{\sqsubseteq ^{0}_{B}}B= \widehat{A}$. Let $\vartriangleleft ^{}_{\widehat{B}}$ be the relation on $\widehat{B}$ defined by $(x\vartriangleleft ^{}_{\widehat{B}} y) \Leftrightarrow (\alpha ^{}_{B}(x) \vartriangleleft ^{1}_{B} y)$. Let $x, y\in \widehat{B}$. If $a\notin x^\uparrow _{\sqsubseteq ^{0}_{B}}$, then we have $x\vartriangleleft ^{}_{\widehat{B}} y$ iff $x\vartriangleleft ^{}_{\widehat{A}} y$. Let us now suppose that $a\in x^\uparrow _{\sqsubseteq ^{0}_{B}}$. If (C1), we have $\alpha ^{}_{A}(x) = \alpha ^{}_{B}(x)$ and then $x\vartriangleleft ^{}_{\widehat{B}} y$ iff $x\vartriangleleft ^{}_{\widehat{A}} y$. If (C2), we have $\alpha ^{}_{A}(x) = b$ and $\alpha ^{}_{B}(x) = a$. By construction, we have $b\vartriangleleft ^{1}_{A} y$ iff $a\vartriangleleft ^{1}_{B} y$. Thus, we have $x\vartriangleleft ^{}_{\widehat{B}} y$ iff $x\vartriangleleft ^{}_{\widehat{A}} y$. As a consequence, we have $\vartriangleleft ^{}_{\widehat{B}} \ = \ \vartriangleleft ^{}_{\widehat{A}}$.

From the induction hypothesis, we have $(B,\vartriangleleft ^{}_{B}) \searrow _{H}(\widehat{B}, \vartriangleleft ^{}_{\widehat{B}})$. But we have $(\widehat{B}, \vartriangleleft ^{}_{\widehat{B}}) = (\widehat{A}, \vartriangleleft ^{}_{\widehat{A}})$ and then $(B,\vartriangleleft ^{}_{B}) \searrow _{H}(\widehat{A}, \vartriangleleft ^{}_{\widehat{A}})$. Since we have $(A,\vartriangleleft ^{}_{}) \searrow _{EH} (B,\vartriangleleft ^{}_{B})$ it follows that $(A,\vartriangleleft ^{}_{}) \searrow _{H}(\widehat{A}, \vartriangleleft ^{}_{\widehat{A}})$. $\blacksquare$

Lemma 169

If the hypotheses of Eqs. (122–124) hold, then we have

$$\begin{aligned} (A,\vartriangleleft ^{}_{A}) \searrow _{QH}(\widehat{A},\vartriangleleft ^{}_{\widehat{A}}) \end{aligned}$$

(128)

Proof

If $\bigvee ^{\sqsubseteq ^{}_{A}} A\in \bigtriangleup ^{\sqsubseteq ^{0}_{A}} A$, then Eq. (125) holds and from Lemma 168, we have $(A,\vartriangleleft ^{}_{A}) \searrow _{H}(\widehat{A},\vartriangleleft ^{}_{\widehat{A}})$ and thus $(A,\vartriangleleft ^{}_{A}) \searrow _{QH}(\widehat{A},\vartriangleleft ^{}_{\widehat{A}})$.

Let us now suppose that $\bigvee ^{\sqsubseteq ^{}_{A}} A\notin \bigtriangleup ^{\sqsubseteq ^{0}_{A}} A$. Let $a= \bigwedge ^{\sqsubseteq ^{}_{A}}(\bigvee ^{\sqsubseteq ^{}_{A}}A)^\downarrow _{\sqsubseteq ^{0}_{A}}$. Let $A_0 = a^\uparrow _{\sqsubseteq ^{}_{A_0}}$ and $\vartriangleleft ^{}_{A_0}$ the restriction of $\vartriangleleft ^{}_{A}$ to $A_0$. Let $A_1 = (A{\setminus } A_0) \cup \{a\}$ and $\vartriangleleft ^{}_{A_1}$ the restriction of $\vartriangleleft ^{}_{A}$ to $A_1$. Both $(A_0,\vartriangleleft ^{}_{A_0})$ and $(A_1,\vartriangleleft ^{}_{A_1})$ subdivide $(A,\vartriangleleft ^{}_{A})$. More precisely, we have $A_0 \cup A_1 = A$ and $A_0 \cap A_1 = \{a\}$, whereas $\mathord {\vartriangleleft ^{}_{A_0}} \cup \mathord {\vartriangleleft ^{}_{A_1}} = \ \vartriangleleft ^{}_{A}$ and $\mathord {\vartriangleleft ^{}_{A_0}} \cap \mathord {\vartriangleleft ^{}_{A_1}} = \emptyset$. On the one hand, $(A_0,\vartriangleleft ^{}_{A_0})$ is a degenerate tree and we trivially have $(A_0,\vartriangleleft ^{}_{A_0}) \searrow _{H}(\{a,\bigvee ^{\sqsubseteq ^{}_{A}} A\}, \{(a,\bigvee ^{\sqsubseteq ^{}_{A}}A) \})$. On the other hand, $(A_1,\vartriangleleft ^{}_{A_1})$ is a tree and it satisfies the hypotheses of Eqs. (122–125) (since $a\in A_1$). From Lemma 168, we have $(A_1,\vartriangleleft ^{}_{A_1}) \searrow _{H}(\widehat{A}_1,\vartriangleleft ^{}_{\widehat{A}_1})$ and it is plain that $\widehat{A}_1 = \widehat{A}$ and $\vartriangleleft ^{}_{A_1} \ = \ \vartriangleleft ^{}_{A}$. By merging $(\widehat{A}_1,\vartriangleleft ^{}_{\widehat{A}_1})$ and $(\{a,\bigvee ^{\sqsubseteq ^{}_{A}} A\}, \{(a,\bigvee ^{\sqsubseteq ^{}_{A}} A)\})$, and by setting $\varepsilon = \bigvee ^{\sqsubseteq ^{}_{A}} A$ it comes $(A,\vartriangleleft ^{}_{A}) \searrow _{H}(\widehat{A}\cup \{\varepsilon \},\vartriangleleft ^{}_{\widehat{A}} \cup \ \{(\bigwedge ^{\sqsubseteq ^{}_{A}}(\bigvee ^{\sqsubseteq ^{}_{A}}A)^\downarrow _{\sqsubseteq ^{0}_{A}},\varepsilon )\})$ and the result follows. $\blacksquare$

1.2 A.2 (Quasi-)homeomorphisms and Equivalences

Let $A$ be a set and $\sqsubseteq ^{}_{A}$ a hierarchical order on $A$.

Let ${\sim }_{}$ be an equivalence relation on $A$ such that

$$\begin{aligned}&\forall K\in A/\mathord {{\sim }_{}}, (K,\sqsubseteq ^{}_{K}) \text { is a totally ordered set} \end{aligned}$$

(129)

$$\begin{aligned}&\forall K\in A/\mathord {{\sim }_{}}, K= \llbracket \bigwedge ^{\sqsubseteq ^{}_{K}} K, \bigvee ^{\sqsubseteq ^{}_{K}} K\rrbracket _{\sqsubseteq ^{}_{A}} \end{aligned}$$

(130)

Let $\sqsubseteq ^{0}_{A} \ = \bigcup _{K\in A/\mathord {{\sim }_{}}} \sqsubseteq ^{}_{K}$ with $\sqsubseteq ^{0}_{A} \ \searrow _{RT}\ \vartriangleleft ^{0}_{A}$.

Remark 170

From Eq. (129), $\sqsubseteq ^{0}_{A}$ is a piecewise total order, i.e. $(A,\vartriangleleft ^{0}_{A})$ is a degenerate forest.

We also assume that

(131)

and we consider the following condition

$$\begin{aligned} \Big \{\bigvee ^{\sqsubseteq ^{}_{}} A\Big \} \in A/\mathord {{\sim }_{}} \end{aligned}$$

(132)

that may be fulfilled or not.

Let $\sqsubseteq ^{}_{A/\mathord {{\sim }_{}}}$ be the relation on $A/\mathord {{\sim }_{}}$ defined by

$$\begin{aligned} J\sqsubseteq ^{}_{A/\mathord {{\sim }_{}}} K\Longleftrightarrow \bigwedge ^{\sqsubseteq ^{0}_{A}} J\sqsubseteq ^{}_{A} \bigwedge ^{\sqsubseteq ^{0}_{A}} K\end{aligned}$$

(133)

Property 171

$(A/\mathord {{\sim }_{}},\vartriangleleft ^{}_{A/\mathord {{\sim }_{}}})$ is a tree.

The following two lemmae are direct corollaries of Lemmae 168 and 169, respectively.

Lemma 172

If the hypotheses of Eqs. (129–132) hold, then we have

$$\begin{aligned} (A,\vartriangleleft ^{}_{}) \searrow _{H}(A/\mathord {{\sim }_{}},\vartriangleleft ^{}_{A/\mathord {{\sim }_{}}}) \end{aligned}$$

(134)

Lemma 173

If the hypotheses of Eqs. (129–131) hold, then we have

$$\begin{aligned} (A,\vartriangleleft ^{}_{}) \searrow _{QH}(A/\mathord {{\sim }_{}},\vartriangleleft ^{}_{A/\mathord {{\sim }_{}}}) \end{aligned}$$

(135)

B Proofs of Propositions

Proof or Proposition 52

Let ${\pi }^{\varXi ^{\star }_{}}_{\varTheta ^{\star }_{}}: \varXi ^{\star }_{} \rightarrow \varTheta ^{\star }_{}$ be the surjective application defined by ${\pi }^{\varXi ^{\star }_{}}_{\varTheta ^{\star }_{}}((X,v)) = X$. Let ${\sim }_{\varTheta ^{\star }_{}}$ be the equivalence relation on $\varXi ^{\star }_{}$ defined by $(P{\sim }_{\varTheta ^{\star }_{}} Q) \Leftrightarrow ({\pi }^{\varXi ^{\star }_{}}_{\varTheta ^{\star }_{}}(P) = {\pi }^{\varXi ^{\star }_{}}_{\varTheta ^{\star }_{}}(Q))$. Let $K\in \varXi ^{\star }_{}/\mathord {{\sim }_{\varTheta ^{\star }_{}}}$. There exists $X\in \varTheta ^{\star }_{}$ such that $K= \llbracket (X,\omega ^{\varTheta ^{\star }_{}}_{X}),(X,\alpha ^{\varTheta ^{\star }_{}}_{X})\rrbracket _{\sqsubseteq ^{}_{\varXi ^{\star }_{}}}$. In particular, the hypotheses of Eqs. (129–130) are satisfied. We have $\bigvee ^{\sqsubseteq ^{}_{\varXi ^{\star }_{}}} \varXi ^{\star }_{} = \infty$. For any $P= (X,v) \in \varXi ^{\star }_{}$, $P{\sim }_{\varTheta ^{\star }_{}} \infty$ implies $X= \mathbb U$, and thus $P= \infty$. Then, we have $[\infty ]_{{\sim }_{\varTheta ^{\star }_{}}} = \{\infty \}$, which satisfies Eq. (132). Let $\vartriangleleft ^{0}_{\varXi ^{\star }_{}} = \bigcup _{K\in \varXi ^{\star }_{}/\mathord {{\sim }_{\varTheta ^{\star }_{}}}} \mathord {\vartriangleleft ^{}_{K}}$ where $\vartriangleleft ^{}_{K}$ is the restriction of $\vartriangleleft ^{}_{\varXi ^{\star }_{}}$ to $K$. Let $P= (X,v), Q= (Y,w) \in \varXi ^{\star }_{}$. Let us suppose that $P\vartriangleleft ^{0}_{\varXi ^{\star }_{}} Q$. From the definition of $\vartriangleleft ^{0}_{\varXi ^{\star }_{}}$, we have $X= Y$, and it follows that $Z_{\sqsubseteq ^{}_{\varXi ^{\star }_{}}}(Q) = \{P\}$, and then . We then have , which satisfies Eq. (131). The result follows from Lemma 172. $\blacksquare$

Proof of Proposition 98

Let $P= (X,v), Q= (Y,w) \in \varXi ^{}_{}$. Let $\langle P_i\rangle _{i=1}^t$ ($t> 1$) be a sequence of elements of $\varXi ^{}_{}$ such that $P_1 = P$, $P_t= Q$ and for all $1 \le i< t, P_i= (X_i, v_i) \blacktriangleleft _{\varXi ^{}_{}} P_{i+1} = (X_{i+1}, v_{i+1})$. Let us suppose that for all $1 \le i< t$, we have $P_i\vartriangleleft ^{\varphi }_{} P_{i+1}$. From Eq. (74), it comes that $X\subset Y$ or ($X= Y$ and $w<^{\square }v$). Let us now suppose that there exists $1 \le i< t$ such that $P_i\vartriangleleft ^{\psi }_{} P_{i+1}$. For all $1 \le i< t$ we have $\tau (X_i) \subseteq \tau (X_{i+1})$. But since $P_i\vartriangleleft ^{\psi }_{} P_{i+1}$, it comes from Eqs. (47) and (67) that $\tau (X_i) \subset \tau (X_{i+1})$ and then $X\subset Y$. The acyclicity of $(\varXi ^{}_{},\blacktriangleleft _{\varXi ^{}_{}})$ follows. $\blacksquare$

Proof of Proposition 103

Let $P= (X,v) \in \varXi ^{}_{}$ be such that $\varphi (P)$ and $\psi (P)$ exist.

Case 1: $\varphi (P) = (\mathbb U,\bot ) = \infty$ and $\psi (P) = (\mathbb U_v,v)$. We have $\varphi ^{\varDelta -2}((\mathbb U_v,v)) = (\mathbb U,\top ) = \infty = \varphi (P)$. Thus Eq. (83) holds.

Case 2: $\varphi (P) = (\mathbb U,\bot )$ and $\psi (P) \ne (\mathbb U_v,v)$. From $\psi (P) \ne (\mathbb U_v,v)$ it comes that $[\psi \circ \psi ](P)$ exists. We have $v= {\sigma }^{\circ }(\bot )$. It follows that $[\varphi \circ \psi \circ ](P) = (\mathbb U,\bot ) = \varphi (P)$. Thus Eq.  (82) holds.

Case 3: $\varphi (P) = (\mathbb U,\top )$. Then, we have ${\square }(P) = \bullet$. By hypothesis, $\psi (P)$ exists. Since ${\square }(P) = \bullet$, $\psi (P)$ is bounded. It follows that $[\psi \circ \psi ](P)$ exists. We have $v= {\sigma }^{\bullet }(\top )$. It follows that $[\varphi \circ \psi \circ \psi ](P) = (\mathbb U,\top ) = \varphi (P)$. Thus Eq.  (82) holds.

Case 4: $\varphi (P) \ne \infty$ and $\psi (P) = (\mathbb U_v,v)$. Then we have ${\square }(P) = \circ$. We have $[\psi \circ \varphi ](P) = (\mathbb U_w,w)$ with $(\mathbb U_v,v) = \varphi ((\mathbb U_w,w))$. It follows that $[\varphi \circ \psi \circ \varphi ](P) = (\mathbb U_v,v) = \psi (P)$. Thus Eq. (81) holds.

Case 5: $\varphi (P) \ne \infty$ and $\psi (P) \ne (\mathbb U_v,v)$. Let us suppose that Eq. (82) does not hold. Let $P_0 =(X_0,u) = P$, $P_1 = (X_1,u) = \psi (P)$, $P_2 = (X_2,u) = [\psi \circ \psi (P)]$. Let $Q_0 = (Y_0,v) = \varphi (P) = \varphi (P_0)$, $Q_1 = (Y_1,v) = [\psi \circ \varphi ](P) = \psi (Q_0)$, $Q_2 = (Y_2,v) = [ \varphi \circ \psi \circ \psi ](P) = \varphi (P_2)$. The set $X_0 \subset \mathbb U$ is connected and externally bounded by the Jordan manifold ${\mathcal J}^{+}_{}(X_0)$. The set $X_1 \subset \mathbb U$ is connected, externally bounded by the Jordan manifold ${\mathcal J}^{+}_{}(X_1)$ and internally bounded by (at least) ${\mathcal J}^{-}_{}(X_1) = {\mathcal J}^{+}_{}(X_0)$. The set $X_2 \subset \mathbb U$ is connected, externally bounded by the Jordan manifold ${\mathcal J}^{+}_{}(X_2)$ and internally bounded by (at least) ${\mathcal J}^{-}_{}(X_2) = {\mathcal J}^{+}_{}(X_1)$. The set $Y_0 \subset \mathbb U$ is connected and externally bounded by the Jordan manifold ${\mathcal J}^{+}_{}(Y_0)$. The set $Y_1 \subset \mathbb U$ is connected, externally bounded by the Jordan manifold ${\mathcal J}^{+}_{}(Y_1)$ and internally bounded by (at least) ${\mathcal J}^{-}_{}(Y_1) = {\mathcal J}^{+}_{}(Y_0)$. The set $Y_2 \subset \mathbb U$ is connected and externally bounded by the Jordan manifold ${\mathcal J}^{+}_{}(Y_2)$. Since Eq. (82) does not hold, we have $\varphi (P) \ne [\varphi \circ \psi \circ \psi ] (P)$ i.e. $Q_0 \ne Q_2$ i.e. $(Y_0,u) \ne (Y_2,u)$. It follows that $Y_0 \ne Y_2$. Since $Q_0 = \varphi (P_0)$ and $Q_2 = \varphi (P_2)$, we have $X_0 \subseteq Y_0$ and $X_2 \subseteq Y_2$. From $X_0 \subseteq Y_0$, it comes that ${\mathcal J}^{+}_{}(Y_0) \subseteq \mathbb U^+({\mathcal J}^{+}_{}(X_0)) = \mathbb U^+({\mathcal J}^{-}_{}(X_1))$. From $Y_0 \ne Y_2$, it comes that $X_0$ and $X_2$ are not connected in $Y_0$. It follows that . Since we have ${\mathcal J}^{+}_{}(Y_0) = {\mathcal J}^{-}_{}(Y_1)$, by merging the two results, we have . It follows that $Y_1 \cap X_1 \ne \emptyset$, and then $Y_1 \subseteq X_1$. This implies $\varphi (Q_1) = P_1$, i.e. $[\varphi \circ \psi \circ \varphi ] (P) = \psi (P)$, hence Eq. (81) holds. $\blacksquare$

Proof or Proposition 106

From Proposition 98, $(\varXi ^{}_{},\blacktriangleleft _{\varXi ^{}_{}})$ is acyclic. Then the reflexive-transitive closure of $\blacktriangleleft _{\varXi ^{}_{}}$, namely $\sqsubseteq ^{}_{\varXi ^{}_{}}$ is an order on $\varXi ^{}_{}$. For any $P\in \varXi ^{}_{} {\setminus } \{\infty \}$, $\varphi (P)$ or $\psi (P)$ exist(s) and from Proposition 105 there is then a unique $Q\in \varXi ^{}_{}$ such that $P\vartriangleleft ^{}_{\varXi ^{}_{}} Q$. It follows that $(\varXi ^{}_{},\vartriangleleft ^{}_{\varXi ^{}_{}})$ is a tree. $\blacksquare$

Proof or Proposition 118

Let ${\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}: \varXi ^{}_{} \rightarrow \varTheta ^{}_{}$ be the surjective application defined by ${\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}((X,v)) = X$. Let ${\sim }_{\varTheta ^{}_{}}$ be the equivalence relation on $\varXi ^{}_{}$ defined by $(P{\sim }_{\varTheta ^{}_{}} Q) \Leftrightarrow ({\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}(P) = {\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}(Q))$. Let $K\in \varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}$. There exists $X\in \varTheta ^{}_{}$ such that $K= \llbracket (X,\omega ^{\varTheta ^{}_{}}_{X}),(X,\alpha ^{\varTheta ^{}_{}}_{X})\rrbracket _{\sqsubseteq ^{}_{\varXi ^{}_{}}}$. In particular, the hypotheses of Eqs. (129–130) are satisfied. We have $\bigvee ^{\sqsubseteq ^{}_{\varXi ^{}_{}}} \varXi ^{}_{} = \infty$. For any $P= (X,v) \in \varXi ^{}_{}$, $P{\sim }_{\varTheta ^{}_{}} \infty$ implies $X= \mathbb U$, and thus $P= \infty$. Then, we have $[\infty ]_{{\sim }_{\varTheta ^{}_{}}} = \{\infty \}$, which satisfies Eq. (132). Let $\vartriangleleft ^{0}_{\varXi ^{}_{}} = \bigcup _{K\in \varXi ^{}_{}/\mathord {{\sim }_{\varTheta ^{}_{}}}} \vartriangleleft ^{}_{K}$ where $\vartriangleleft ^{}_{K}$ is the restriction of $\vartriangleleft ^{}_{\varXi ^{}_{}}$ to $K$. Let $P= (X,v), Q= (Y,w) \in \varXi ^{}_{}$. Let us suppose that $P\vartriangleleft ^{0}_{\varXi ^{}_{}} Q$. From the definition of $\vartriangleleft ^{0}_{\varXi ^{}_{}}$, we have $X= Y$, and it follows that $Z_{\sqsubseteq ^{}_{\varXi ^{}_{}}}(Q) = \{P\}$, and then . We then have , which satisfies Eq. (131). The result follows from Lemma 172. $\blacksquare$

Proof or Proposition 124

Let $X= {\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}(P)$. By definition, $X$ is connected, i.e. $\varPi [X] = \{X\}$. The set $\varPi [\overline{X}]$ is composed by one infinite set $X_0 = \mathbb U{\setminus } \tau (X)$ and $k\ge 0$ set(s) $X_i$ ($1 \le i\le k$) such that $\{X_i\}_{i=1}^{k} = \tau ({\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}(\varPsi (P)))$. Let $Y= {\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}(\varphi (P))$. By definition, $Y$ is connected, i.e. $\varPi [Y] = \{Y\}$. The set $\varPi [\overline{Y}]$ is composed by one infinite set $Y_0 = \mathbb U{\setminus } \tau (Y)$ and $\ell \ge 0$ set(s) $Y_{j}$ ($1 \le j\le \ell$) such that $\{Y_{j}\}_{j=1}^{\ell } = \tau ({\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}(\varPsi (\varphi (P))))$. Let $D= Y\setminus X$.

“$\Rightarrow$” side of the proof. Let us suppose that $\varphi (P) \searrow _{D}P$. Then, we have $\varPhi (\varphi (P)) = \{P\}$. Since $D$ is deletable we have $k= \ell$ and (up to reindexing), for any $i\in \llbracket 0, k\rrbracket$, $Y_i\subseteq X_i$. For each $i\in \llbracket 0, k\rrbracket$, there exists $\widehat{P}_i= (\widehat{X}_i,v) \in \varPsi (P)$ such that $X_i= \tau (\widehat{X}_i)$ and $\widehat{Q}_i= (\widehat{Y}_i,w) \in \varPsi (\varphi (P))$ such that $Y_i= \tau (\widehat{Y}_i)$. We have $Y_i\subseteq X_i$ and then $\tau (\widehat{Y}_i) \subseteq \tau (\widehat{X}_i)$. We set $D_i= D\cap \widehat{X}_i$. We have $\tau (\widehat{X}_i{\setminus } D_i) =\tau (\widehat{X}_i) {\setminus } D_i= \tau (\widehat{Y}_i)$. It follows that $\widehat{Y}_i\subseteq \widehat{X}_i$, and $\varphi$ is then bijective between $\varPsi (\varphi (P))$ and $\varPsi (P)$.

“$\Leftarrow$” side of the proof. Let us suppose that $\varphi$ is bijective between $\varPhi (\varphi (P))$ and $\{\varphi (P)\}$. Then both $P= \varphi (P) \setminus D$ and $\varphi (P)$ are connected and $P\subset \varphi (P)$. Let us suppose that $\varphi$ is bijective between $\varPsi (\varphi (P))$ and $\varPsi (P)$. The function $\tau \circ {\pi }^{\varXi ^{}_{}}_{\varTheta ^{}_{}}$ is a bijection between $\varPsi (P)$ (resp. $\varPsi (\varphi (P))$) and $\{X_i\}_{i=1}^{k}$ (resp. $\{Y_j\}_{j=1}^{\ell }$). It follows that $\varphi (P) \searrow _{D}P$. $\blacksquare$

Proof or Proposition 137

Let $K\in H$. Let $\sqsubseteq ^{}_{K}$ be the restriction of $\sqsubseteq ^{}_{\varTheta ^{}_{}}$ to $K$. Let $X, Y\in K$. From the definition of ${\sim }_{H}$, there exists (up to switching $X$ and $Y$) a sequence $\langle X_i\rangle _{i=1}^t$ ($t\ge 1$) such that $X_1 = X$, $X_t= Y$, $X_i\in \varTheta ^{}_{}$ for all $1 \le i\le t$, and $X_i\searrow _{D}X_{i+1}$ but also $X_{i+1} \vartriangleleft ^{}_{\varTheta ^{}_{}} X_i$ for all $1 \le i< t$. It follows that $Y\subseteq X$ and then $Y\sqsubseteq ^{}_{\varTheta ^{}_{}}{}{} X$. In particular, Eq. (129) is satisfied. By considering the sequence $\langle X_i\rangle _{i=1}^t$ such as defined above with $X_1 = \bigvee ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K$ and $X_t= \bigwedge ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K$, it follows that Eq. (130) is satisfied. We have $\bigvee ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} \varTheta ^{}_{} = \mathbb U$. For any $X\in \varTheta ^{}_{}$, $X{\sim }_{H} \mathbb U$ implies $X= \mathbb U$. Then, we have $[\mathbb U]_{{\sim }_{H}} = \{\mathbb U\}$, which satisfies Eq. (132). Let $\vartriangleleft ^{0}_{\varTheta ^{}_{}} = \bigcup _{K\in \varTheta ^{}_{}/\mathord {{\sim }_{H}}} \vartriangleleft ^{}_{K}$ where $\vartriangleleft ^{}_{K}$ is the restriction of $\vartriangleleft ^{}_{\varTheta ^{}_{}}$ to $K$. Let $X, Y\in \varTheta ^{}_{}$. Let us suppose that $X\vartriangleleft ^{0}_{\varTheta ^{}_{}} Y$. From the definition of $\vartriangleleft ^{0}_{\varTheta ^{}_{}}$, we have $Y\searrow _{D}X$, and it follows that $Z_{\sqsubseteq ^{}_{\varTheta ^{}_{}}}(Y) = \{X\}$, and then . We then have , which satisfies Eq. (131). The result follows from Lemma 172. $\blacksquare$

Proof or Proposition 144

Let $K\in T$. Let $\sqsubseteq ^{}_{K}$ be the restriction of $\sqsubseteq ^{}_{\varTheta ^{}_{}}$ to $T$. Let $X, Y\in T$. We have $X\cap Y\ne \emptyset$ and ${\square }(X) = {\square }(Y)$. It follows that $X, Y\in \varTheta ^{{\square }}_{}$ and thus, up to switching $X$ and $Y$, we have $X\subseteq Y$ and then $X\sqsubseteq ^{}_{\varTheta ^{}_{}} Y$. It follows that Eq. (129) is satisfied. More generally, for any $X\in \llbracket \bigwedge ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K,\bigvee ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K\rrbracket _{\sqsubseteq ^{}_{\varTheta ^{}_{}}}$, we have ${\square }(X) = {\square }(\bigwedge ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K)$, and then $\bigwedge ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K\sqsubseteq ^{}_{\varTheta ^{}_{}} X\sqsubseteq ^{}_{\varTheta ^{}_{}} \bigvee ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K$, i.e. $\bigwedge ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K\subseteq X\subseteq \bigvee ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K$, which implies $\tau (\bigwedge ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K) = \tau (X) = \tau ( \bigvee ^{\sqsubseteq ^{}_{\varTheta ^{}_{}}} K)$. It follows that Eq. (130) is satisfied. Let $\vartriangleleft ^{0}_{\varTheta ^{}_{}} = \bigcup _{K\in \varTheta ^{}_{}/\mathord {{\sim }_{T}}} \vartriangleleft ^{}_{K}$ where $\vartriangleleft ^{}_{K}$ is the restriction of $\vartriangleleft ^{}_{\varTheta ^{}_{}}$ to $K$. Let $X, Y\in \varTheta ^{}_{}$. Let us suppose that $Y\vartriangleleft ^{0}_{\varTheta ^{}_{}} X$. We have $(Y,\alpha ^{\varTheta ^{}_{}}_{Y}) \sqsubseteq ^{}_{\varXi ^{}_{}} (X,\omega ^{\varTheta ^{}_{}}_{X})$. From the definition of $\vartriangleleft ^{0}_{\varTheta ^{}_{}}$, we also have $\tau (X) = \tau (Y)$. Let us suppose that there exists $W\in Z_{\sqsubseteq ^{}_{\varTheta ^{}_{}}}(X)$. If $X= \varphi (W)$ then we have $(W,\alpha ^{\varTheta ^{}_{}}_{Y}) \vartriangleleft ^{}_{\varXi ^{}_{}} (X,\omega ^{\varTheta ^{}_{}}_{X})$. But since $\tau (X) = \tau (Y)$ we have $\tau (W) = \tau (Y)$ and then $W= Y$, or $\tau (W) \subset \tau (Y)$, and then $W\sqsubset _{\varTheta ^{}_{}} Y$: a contradiction. If $X= \psi (W)$ then we have $(W,\omega ^{\varTheta ^{}_{}}_{X}) \vartriangleleft ^{}_{\varXi ^{}_{}} (X,\omega ^{\varTheta ^{}_{}}_{X})$. But then, $\varphi ((W,\omega ^{\varTheta ^{}_{}}_{X})) = (V,\alpha ^{\varTheta ^{}_{}}_{Y})$ is such that $V\sqsubset _{\varTheta ^{}_{}}{}{} Y$: a contradiction. Then, we have $Z_{\sqsubseteq ^{}_{\varTheta ^{}_{}}}(X) = \{Y\}$. It comes that Eq. (131) is satisfied. The result follows from Lemma 173. $\blacksquare$