# Multivalued component tree: New results and a bridge between partial and total partition trees

Nicolas Passat, Romain Perrin, Jimmy Francky Randrianasoa, Camille Kurtz, Benoît Naegel

► To cite this version:

Nicolas Passat, Romain Perrin, Jimmy Francky Randrianasoa, Camille Kurtz, Benoît Naegel. Multi-valued component tree: New results and a bridge between partial and total partition trees. Journal of Mathematical Imaging and Vision, 2025, 67 (6), pp.57. 10.1007/s10851-025-01264-8. hal-05185418

HAL Id: hal-05185418

https://hal.science/hal-05185418v1

Submitted on 24 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Multivalued Component Tree: New Results and a Bridge Between Partial and Total Partition Trees

Nicolas Passat · Romain Perrin · Jimmy Francky Randrianasoa · Camille Kurtz · Benoît Naegel

the date of receipt and acceptance should be inserted later

**Abstract** Tree-based structures constitute an efficient way of representing images for manipulation, processing and analysis purposes. In this context, a wide range of such trees has been proposed in the framework of mathematical morphology. These so-called morphological trees are partition trees, i.e. trees where each cut corresponds to a (partial or total) partition of the support of the image. Some of these trees belong to the subfamily of the component tree, that models an image via its successive threshold sets. The component tree and its variants were natively designed for handling grey-level images, i.e. images with values organized as a totally ordered set. Ten years ago, the notion of a multivalued component tree was introduced to extend the component tree beyond this total order hypothesis. In particular, it was shown that a component tree could be built on images with values structured by a (partial) hierarchical order. In this article, we continue

and complete the study of the multivalued component tree. We observe that this tree has the unusual property of possibly being a total partition tree or a partial partition tree. Based on this fact, the first part of this article is dedicated to establish a common framework to describe the partial partition trees (e.g. the component tree and related trees) and the total partition trees (e.g. the binary partition tree and related trees). In this framework, the multivalued component tree belongs to a family that bridges both kinds of (total / partial) partition trees. Regarding the notion of multivalued component tree itself, our contributions are twofold: (1) we propose a new algorithm for the construction of the multivalued component tree; and (2) we describe two strategies for building hierarchical orders from sets of values not natively endowed with an order relation. Codes are available at: https://github.com/bnaegel/multivalued_component_tree.

**Keywords** image modeling · hierarchical ordering · total / partial partition trees · multivalued component trees · component trees · binary partition trees · connected operators · mathematical morphology

## 1 Introduction

Using trees for representing [1, 2] and analysing [3–5] images is a historical research issue. The transition from regular to irregular pyramids for image representation in the early 90’s [6] paved the way to the development of a rich and powerful framework for image modeling and analysis based on hierarchical structures. This framework was mainly developed in the field of mathematical morphology [7–9].

To be successfully constructed, it benefited from solid foundations based on three pillars: (1) the explo-

<footnote>N. Passat (corresponding author)</footnote>

<footnote>Université de Reims Champagne Ardenne, CRESTIC, Reims, France</footnote>

<footnote>Tel: (+33) 3.26.91.33.89</footnote>

<footnote>E-mail: nicolas.passat@univ-reims.fr</footnote>

<footnote>R. Perrin</footnote>

<footnote>Université de Strasbourg, CNRS, ICube, Strasbourg, France
E-mail: romain.perrin@unistra.fr</footnote>

<footnote>J. F. Randrianasoa</footnote>

<footnote>EPITA Research Laboratory (LRE), Le Kremlin-Bicêtre, France, and Université de Strasbourg, CNRS, ICube, Strasbourg, France</footnote>

<footnote>E-mail: jimmy.randrianasoa@epita.fr</footnote>

<footnote>C. Kurtz</footnote>

<footnote>Université Paris Cité, LIPADE, Paris, France
E-mail: camille.kurtz@u-paris.fr</footnote>

<footnote>B. Naegel</footnote>

<footnote>Université de Strasbourg, CNRS, ICube, Strasbourg, France
E-mail: b.naegel@unistra.fr</footnote>
ration of connectivity (investigated from the discrete
topology [10–13] and the morphology points of view
[14–18]) for describing the structure of an image; (2) a
thorough study of partial and total partitions and their
ordering [19–22] for designing relevant decompositions
of an image; (3) efficient solutions based on graph mod-
eling and algorithmics for the design and construction
of graph- and tree-based structures [23–26].

The trees developed in the framework of morpho-
logical hierarchies model in a compact fashion a wide
space of possible partitions of an image induced by its
mixed spatial-spectral composition. These trees can be
subdivided into two families: (1) those which model to-
tal partitions, and (2) those which model partial par-
titions. The archetype of the first family is the binary
partition tree [27]. The archetype of the second is the
component tree [28].

The proposal of a rich family of trees allowing to
model images led to the development of a wide range
of image processing and analysis approaches, dedicated
in majority to filtering and segmentation tasks, gath-
ered under the name of connected operators [29–31].
The success of morphological trees and the induced con-
nected operators relies in particular on their low cost
in terms of construction and manipulation. Regarding
their construction, the principal trees can be built in
quasi-linear time with respect to the size of the im-
age [27, 32, 33]. Regarding their involvement in image
processing / analysis tasks, two main paradigms were
investigated. The first consists of selecting nodes of the
tree based on descriptive attribute analysis [34,35]. The
second consists of selecting a cut in the tree which op-
timizes a given energy [36,37]. In both paradigms, the
processing can be carried out in linear time with respect
to the size of the tree.

Over the last years, many efforts were geared to-
wards enriching the framework of morphological hier-
archies with new structures which generalize or extend
the classical ones, especially to relax some constraints
related to the images that could be modeled (e.g. order-
ing on values, topological structure of the image sup-
port). In this context, the notion of a multivalued com-
ponent tree [38] was proposed as a generalization of
the classical component tree [28]. This new tree had
been designed in order to allow the construction of an
analogue of the component tree on images where val-
ues are organised with respect to a (partial) tree-based
order relation, whereas the standard component tree
requires a total order on values. In this article, which
is an extended and improved version of the conference
paper [39], we continue and complete the study of the
multivalued component tree.

This article is subdivided in four main parts.

- The first part (Sections 2–4) has a tutorial value. In Section 2 we provide a state of the art of the main trees proposed in the framework of morphological hierarchies, and we discuss on their properties. In Section 3, we recall basic mathematical notions required to make this article self-contained. In Section 4, we explain how a digital image can be modeled as a valued graph, since the considered trees are not restricted to images, but can more generally deal with such graphs.

- The second part (Section 5) has a theoretical value. We show that the multivalued component tree establishes a bridge between the two families of total partition trees and partial partition trees. In particular, the multivalued component tree can be seen as a way to unify the framework of morphological hierarchies.

- The third part (Section 6) has an algorithmic value. We propose a new way for building the multivalued component tree. By contrast with a previous algorithm [38] (which required to express a multivalued image as a grey-level image to use a standard component tree construction algorithm), we can now build the multivalued component tree directly from its native multivalued image.

- The fourth part (Section 7) has a methodological value. We describe two solutions for endowing a set of values with hierarchical (pre)order relations, necessary to design multivalued images as a prerequisite to the construction of multivalued component trees. Both strategies consist of building a morphological tree on/from a set of values considered itself as an image.

## 2 Some Morphological Trees

In this section, we summarize the principal hierarchical
structures developed in the framework of mathematical
morphology. This summary is not intended to be ex-
haustive (the interested readers may refer e.g. to [40]
and the herein references).

Most of these structures are trees (although a few
ones may be directed acyclic graphs—DAGs). All these
trees are *partition trees*. This means that they are cre-
ated by stacking a finite sequence of partitions of a set
Ω, where each partition refines the previous one, from
a trivial singleton partition (the root of the tree) to a
final partition (the set of the leaves of the tree). By
side effect, these trees are also *inclusion trees*. Indeed,
each partition is composed of subsets, that constitute
the nodes (root, internal nodes, leaves) of the tree, and
a tree models the inclusion relation ($\subseteq$) between them, via its compact representation as a Hasse diagram.

Although being built from a limited number of partitions, these trees intrinsically model a huge family of potential partitions. Indeed, each cut of a tree, namely each set of non-comparable nodes (i.e. non-intersecting subsets) defines a new partition obtained by sampling the initial partitions from which the tree was originated.

In the sequel, we consider each tree as a representation of an image $\mathcal{F}: \Omega \to \mathcal{V}$, defined on a support $\Omega$ and taking its values in $\mathcal{V}$. These trees can be classified in two main families: those originated from total partitions of $\Omega$ (Section 2.1) and those originated from partial partitions of $\Omega$ (Section 2.2).

## 2.1 Total partition trees

The archetypal of the total partition trees is the so-called binary partition tree [27]. As suggested by its name, this tree is binary, which means that, except the leaves, each node is a (connected) subset $X$ of $\Omega$ which has two children nodes $X_1$ and $X_2$ that form a partition of $X$, leading to a top-down binary decomposition of the root $\Omega$ of the tree into subsets of decreasing size. The construction of such trees is guided by one or many [41] criteria which determine(s) the order of merging of the smallest subsets provided by an initial partition of $\Omega$, that defines the leaves of the tree. These criteria may be determined by a prior knowledge related to the relevant way of merging these nodes. Under such hypotheses, the tree is not an intrinsic model, i.e. it is not deterministically derived from $\mathcal{F}$. (Alternatively to the binary partition tree, the concept of braid of partitions [42,43], aims to replace the requirement of a refinement total order between the successive partitions by the constraint that suprema of the pairwise partitions be hierarchically organized; the braids are no longer trees, and their interest remained mainly theoretical until now.)

A second family of total partition trees is composed by trees similar to the binary partition tree. The main two differences lie in the fact that (1) they are not necessarily binary, and (2) they are intrinsic models, i.e. the only knowledge of $\mathcal{F}$ is sufficient to define them. Two trees are representative examples of this family. The first one is the $\alpha$-tree [44]. Similarly to the standard binary partition tree, the definition of the $\alpha$-tree is determined by a merging criterion. However, this criterion is directly linked to the similarity between the values of $\mathcal{V}$ that compose the subsets $X$ of $\Omega$ to be merged, leading to the so-called notion of quasi-flat zone. The second tree within this family is the watershed tree [45]. Here, the merging criterion is linked to a saliency measure between the regions to be merged, which is expressed

as the height of the watershed [46] between them. The links between watershed trees, saliency maps and the notion of quasi-flat zone were demonstrated in [47].

## 2.2 Partial partition trees

The archetypal of the partial partition trees is the so-called component tree [28]. Basically, the component tree is built from successive threshold sets, at each value of $\mathcal{V}$ of the image $\mathcal{F}$. The component tree models the inclusion relation between the connected components of these threshold sets. Each node is a subset $X$ of $\Omega$ corresponding to such connected component at a certain value $v \in \mathcal{V}$. If $X$ is not a flat zone of the image, its has $k \ge 1$ child(ren) node(s) $X_i$ ($1 \le i \le k$) that form(s) a partition of a strict subset $Y \subset X$, which corresponds to the part of $X$ where the values of $\mathcal{F}$ are strictly greater than $v$. The component tree can be declined as two dual trees, namely the max-tree and the min-tree, depending on the order $\le$ or $\ge$ considered for the thresholding operation that generates the partitions of $\Omega$.

The component tree has been declined in various versions. One can cite the hyperconnection tree [48], that relies on hyperconnections instead of the standard notion of (topological or morphological) connections, and the multivalued component tree [38] that is the subject of this article. Other non-tree structures were also derived from the notion of component tree. These structures are DAGs. One can cite the component-graph [49] that generalizes the notion of component tree to the case where the value set $\mathcal{V}$ is endowed with a partial order instead of a total one.

The tree of shapes [50] is a second important structure within the family of the partial partition trees. It is often presented as a self-dual version of the component tree. The tree of shapes was initially defined as a tree built from the union of the nodes of both the max-tree and the min-tree, where each of these nodes undergoes a saturation (i.e. a “hole-filling” operation). It follows from this definition that, contrary to the other trees presented above, the tree of shapes not only requires the definition of a connectivity on $\Omega$, but it also need that $\Omega$ be structured as a topological space where the Jordan-Brouwer property [51, 52] holds. Similarly to the component tree, the tree of shapes was initially designed for handling images for which the value set $\mathcal{V}$ is endowed with a total order. A multivalued version of the tree of shapes was defined in [53]. Other variants of the tree of shapes were also proposed in the literature. One can cite the monotonic tree [54], which is a compact version of the tree of shapes that mainly models the topological modifications within the tree. It is
worth mentioning that the adjacency tree [55], a topological descriptor defined twenty years before the tree of shapes, is indeed a tree of shapes applied to a binary image.

In a recent work [56], the links that exist between the two families of component trees and trees of shapes were formally established. In particular, a new tree, called the complete tree of shapes was defined as a unifying tree that contains the union of the nodes of the max- and the min-tree. From this tree, both the component tree and the tree of shapes can be retrieved. It is notably observed that the tree of shapes, the topological tree of shapes (another topological tree introduced in [57]) and the monotonic tree can be obtained from the complete tree of shapes by decreasing homeomorphisms derived from specific equivalence relations on their nodes.

## 2.3 Partition trees in the framework of graphs

Except the subfamily of the trees of shapes [50, 53, 54, 57] that build upon topological closing and thus require to fulfill adequate topological hypotheses, the (total or partial) partition trees evoked above can model an image $\mathcal{F}: \Omega \to \mathbb{V}$ provided that the support $\Omega$ is endowed with a connectivity relation. In particular, this hypothesis is satisfied if the structure of $\Omega$ is a (non-directed) graph. In other words, a partition tree can be built not only on an image, but more generally on a (valued) graph.

Since, the partition trees are defined as Hasse diagrams, i.e. as graphs, it is indeed possible to build morphological trees from/on other morphological trees. The idea to build “trees on trees” was declined under different forms. In [58, 59], a forest of component trees obtained from a same image by a sequence of monotonic connectivities was endowed with a forest of (total) partition trees linking the nodes at a same threshold set among the various component trees, leading to the notion of a component hypertree. In [60], the paradigm of shaping proposed to build, from an initial component tree endowed with a (descriptive) valuation on nodes, a second component tree in order to facilitate the attribute-based filtering of the first tree. The shaping paradigm was generalized from “trees on trees” to “trees on graphs” by building a tree of shapes on a graph of shapes in [61]. In a least extent, the asymmetric hierarchies proposed in [62] also follow a “trees on trees” paradigm. Indeed, the DAG proposed in this approach, which extends the notion of component tree to the case of non-symmetric adjacency relations, can be generated from a strongly connected component tree

(i.e. a partial partition tree obtained from strongly connected components) enriched, at each threshold set, by a second tree that models the acyclic links between these strongly connected components.

It follows from this last discussion that a hierarchical model can be built whenever a graph endowed with a valuation is available. This allows, of course, to build morphological trees from images, but also morphological trees from morphological trees. This paradigm will also be useful to build (hierarchical) orders on sets of values $\mathbb{V}$, that will be required to further define the multivalued component trees that we investigate in this article (Section 7).

# 3 Orders, Trees and Partitions

In this section, we recall notions that mainly lie in the frameworks of set and graph theories. They constitute the basic tools for this study, since both images and morphological hierarchies will be handled as graphs.

## 3.1 Relations

Let $X$ be a set. Let $\alpha_X$ (or simply $\alpha$ when there is no ambiguity) be a (binary) relation on $X$, i.e. a subset of $X \times X$. In particular, if $x, y \in X$, we note $x \alpha y$ to express that $(x, y) \in \alpha$. For any $x \in X$, we note $\sigma_\alpha(x) = \{y \in X \mid x \alpha y\}$.

We say that $\alpha$ is:

- reflexive if $\forall x \in X, x \alpha x$;

- irreflexive if $\forall x \in X, \neg(x \alpha x)$;

- transitive if $\forall x, y, z \in X, (x \alpha y) \wedge (y \alpha z) \Rightarrow (x \alpha z)$;

- antisymmetric if $\forall x, y \in X, (x \alpha y) \wedge (y \alpha x) \Rightarrow (x = y)$;

- symmetric if $\forall x, y \in X, (x \alpha y) \Leftrightarrow (y \alpha x)$;

- total if $\forall x, y \in X, (x \alpha y) \lor (y \alpha x)$;

- partial if it is not total.

The dual relation $\infty$ induced by the relation $\alpha$ is defined such that $\forall x, y \in X, (x \infty y) \Leftrightarrow (y \alpha x)$.

Let $Y \subseteq X$. The restriction of $\alpha$ to $Y$ is the relation defined by $\alpha_Y = \alpha \cap (Y \times Y)$. (If there is no ambiguity, it is still noted $\alpha$ instead of $\alpha_Y$.)

## 3.2 Equivalences, partitions

Let $X$ be a set. Let $\sim$ be a relation on $X$. We say that $\sim$ is an equivalence if it is reflexive, transitive and symmetric.
Let $x \in X$. The equivalence class of $x$ is defined by $[x]_{\sim} = \{y \in X \mid x \sim y\}$. The quotient set of $X$ with respect to $\sim$ is defined by $X/\sim = \{[x]_{\sim} \mid x \in X\}$.

We note $2^X = \{Y \mid Y \subseteq X\}$ the set of all the subsets of $X$. Let $\mathcal{P} \subseteq 2^X$. We say that $\mathcal{P}$ is a total partition of $X$ if the following three properties hold:

1. $\emptyset \notin \mathcal{P}$;

2. $\forall Y, Z \in \mathcal{P}, (Y \cap Z \neq \emptyset) \Rightarrow (Y = Z)$;

3. $\bigcup_{Y \in \mathcal{P}} Y = X$.

We say that $\mathcal{P}$ is a partial partition of $X$ if $\mathcal{P}$ is a total partition of $Y \subset X$. We say that $\mathcal{P}$ is a general partition of $X$ if $\mathcal{P}$ is a total partition of $Y \subseteq X$.

We note $\hat{\Pi}(X)$ (resp. $\tilde{\Pi}(X)$, resp. $\Pi(X)$) the set of the total (resp. partial, resp. general) partitions of $X$. We have:

$$ \left. \begin{array}{l} \hat{\Pi}(X) \\ \tilde{\Pi}(X) \end{array} \right\} \subseteq \Pi(X) \subseteq 2^{2^x} \qquad (1) $$

and $\{\hat{\Pi}(X), \tilde{\Pi}(X)\}$ is a total partition of $\Pi(X)$ if $X$ is a non-trivial set. In the sequel, the terminology “partition” will refer to “general partition”.

The quotient set $X/\sim$ associated to an equivalence relation $\sim$ on $X$ is a total partition of $X$. Reversely, any total partition $\mathcal{P}$ of $X$ induces an equivalence relation $\sim_{\mathcal{P}}$ defined by:

$$ \forall x, y \in X, (x \sim_{\mathcal{P}} y) \iff (\exists Y \in \mathcal{P}, \{x, y\} \subseteq Y) \qquad (2) $$

### 3.3 (Pre)orders

Let $X$ be a set and $\sqsubseteq$ a relation on $X$. We say that $\sqsubseteq$ is a preorder (and that $(X, \sqsubseteq)$ is a preordered set) if $\sqsubseteq$ is reflexive and transitive. We say that $\sqsubseteq$ is an order (and that $(X, \sqsubseteq)$ is an ordered set) if $\sqsubseteq$ is reflexive, transitive and antisymmetric. A (pre)order can be either total or partial.

Let us suppose that $\sqsubseteq_X$ is a preorder on $X$. Let $\sim$ be the equivalence relation on $X$ induced by the non-antisymmetry of $\sqsubseteq_X$:

$$ \forall x, y \in X, (x \sim y) \iff (x \sqsubseteq_X y \land y \sqsubseteq_X x) \qquad (3) $$

The preorder relation $\sqsubseteq_X$ induces an order relation $\sqsubseteq_{X/\sim}$ on the quotient set $X/\sim$ defined by:

$$ \forall [x]_{\sim}, [y]_{\sim} \in X/\sim, ([x]_{\sim} \sqsubseteq_X [y]_{\sim}) \iff (x \sqsubseteq_X y) \qquad (4) $$

If $\sqsubseteq$ is an order on $X$, we note $\prec$ the reflexive-transitive reduction of $\sqsubseteq$. The set $X$ endowed with $\prec$, namely $(X, \prec)$ is the Hasse diagram of $(X, \sqsubseteq)$.

### 3.4 Hierarchical (pre)orders, trees

Let $X$ be a set. Let $\sqsubseteq$ be an order on $X$. We say that $\sqsubseteq$ is a upper-hierarchical (resp. lower-hierarchical) order on $X$ if for all $x \in X$, $(\sigma_{\sqsubseteq}(x), \sqsubseteq)$ (resp. $(\sigma_{\sqsupseteq}(x), \sqsubseteq)$) is a totally ordered set. We say that a preorder $\sqsubseteq$ on $X$ is a upper-hierarchical (resp. lower-hierarchical) preorder on $X$ if the order relation $\sqsubseteq_{X/\sim}$ is a upper-hierarchical (resp. lower-hierarchical) order on $X/\sim$.

Let $X$ be a finite set. Let $\sqsubseteq$ be a upper (resp. lower) hierarchical order on $X$ such that $(X, \sqsubseteq)$ admits a maximum $\bigvee^{\sqsubseteq} X$ (resp. a minimum $\wedge^{\sqsubseteq} X$). The Hasse diagram $(X, \prec)$ of $(X, \sqsubseteq)$ (resp. $(X, \sqsupseteq)$), also noted $\mathfrak{T}_{(X, \prec)}$ (or simply $\mathfrak{T}$ when there is no ambiguity) is called a upper-tree (resp. a lower-tree). The maximum $\bigvee^{\sqsubseteq} X$ (resp. the minimum $\wedge^{\sqsubseteq} X$) is called the root of $\mathfrak{T}$. The minimal (resp. maximal) elements gathered in the set noted $\Delta^{\sqsubseteq} X$ (resp. $\nabla^{\sqsubseteq} X$) are called the leaves of $\mathfrak{T}$.

Let $x \in X$. If $x = \bigvee^{\sqsubseteq} X$ (resp. $x = \wedge^{\sqsubseteq} X$), then we have $\sigma_{\prec}(x) = \emptyset$; otherwise, $\sigma_{\prec}(x)$ is a singleton set, and we note, by abuse of notation $\sigma_{\prec}(x) = y$ instead of $\sigma_{\prec}(x) = \{y\}$. In particular, $\sigma_{\prec}$ can be handled as a function from $X$ to $X$.

### 3.5 Hierarchies of partitions, partition trees

Let $X$ be a set. Let $\mathcal{P}_1, \mathcal{P}_2 \in \Pi(X)$ be two general partitions of $X$.

We say that $\mathcal{P}_1$ refines $\mathcal{P}_2$ and we write $\mathcal{P}_1 \subseteq \Pi(X)$ ($\mathcal{P}_2$ (or simply $\mathcal{P}_1 \in \mathcal{P}_2$ when there is no ambiguity) if $\forall X_1 \in \mathcal{P}_1, \exists X_2 \in \mathcal{P}_2, X_1 \subseteq X_2$. The relation $\subseteq \in \Pi(X)$ is an order on $\Pi(X)$. Its restriction $\subseteq \in \hat{\Pi}(X)$ (resp. $\subseteq \in \tilde{\Pi}(X)$) is an order on $\hat{\Pi}(X)$ (resp. $\tilde{\Pi}(X)$).

Let $\Pi_p(X) = \{\mathcal{P}_i\}_{i=0}^p (p \ge 0)$ be a nonempty set of general partitions of $X$, such that $\{X\} \in \Pi_p(X)$ and $\subseteq \in \Pi_p(X)$ is a total order on $\Pi_p$. Up to re-indexing, we can assume that:

$$ \forall i, j \in [0, p], (i \le j) \Rightarrow (\mathcal{P}_j \in \mathcal{P}_i) \qquad (5) $$

In particular, we then have $\{X\} = \mathcal{P}_0$. We say that $\Pi_p(X)$ is a hierarchy of general partitions. See Figs. 1(a) and 2(a).

Let $\Theta = \bigcup_{i=0}^p \mathcal{P}_i$. Then $(\Theta, \sqsubseteq)$ is a partially ordered set. More precisely, $\sqsubseteq$ is a upper-hierarchical order on $\Theta$ which admits as maximum $\bigvee^{\sqsubseteq} \Theta = X$. The Hasse diagram $\mathfrak{T} = (\Theta, \prec)$ of $(\Theta, \sqsubseteq)$ is then a upper-tree, called the partition tree of $\Pi_p(X)$. If $\Pi_p(X) \subseteq \hat{\Pi}(X)$, then we say that $\mathfrak{T}$ is a total partition tree. If $\Pi_p(X) \subseteq \tilde{\Pi}(X)$, then we say that $\mathfrak{T}$ is a partial partition tree. See Figs. 1(b) and 2(b).

Let $Y \in \Theta$. We set $\Theta_Y = \{Z \in \Theta \mid Z \subseteq Y\}$. The Hasse diagram $\mathfrak{T}_Y = (\Theta_Y, \prec)$ of the ordered set
<figure><img src="image_2.png" /><figcaption>**Fig. 1** A set $X$ composed of 7 elements, depicted by 7 distinct colours. (a) A set $\{\mathcal{P}_i\}_{i=0}^5$ of total partitions of $X$ that form a hierarchy of total partitions. For each $i \in [0, 5]$, each subset $Y$ of $\mathcal{P}_i$ is depicted by elements of $X$ linked by horizontal black edges. The partition $\mathcal{P}_0$ is the trivial partition $\{X\}$. (b) The total partition tree $\mathcal{T}_X = (\Theta, \prec)$ associated to the hierarchy of total partitions $\{\mathcal{P}_i\}_{i=0}^5$. Each element $Y \in \Theta = \bigcup_{i=0}^5 \mathcal{P}_i$ is depicted once. The relation $\prec$ is represented by the vertical black edges.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Fig. 2** A set $X$ composed of 7 elements, depicted by 7 distinct colours. (a) A set $\{\mathcal{P}_i\}_{i=0}^5$ of partial partitions of $X$ that form a hierarchy of partial partitions. For each $i \in [0, 5]$, each subset $Y$ of $\mathcal{P}_i$ is depicted by elements of $X$ linked by horizontal black edges. The partition $\mathcal{P}_0$ is the trivial partition $\{X\}$. (b) The partial partition tree $\mathcal{T}_X = (\Theta, \prec)$ associated to the hierarchy of partial partitions $\{\mathcal{P}_i\}_{i=0}^5$. Each element $Y \in \Theta = \bigcup_{i=0}^5 \mathcal{P}_i$ is depicted once. The relation $\prec$ is represented by the vertical black edges.</figcaption></figure>

($\Theta_Y, \subseteq$) is the subtree of $\mathcal{T} = (\Theta, \prec)$ of root $Y$. It is, by definition, a general partition tree. If $\mathcal{T}$ is a total partition tree, then $\mathcal{T}_Y$ is also a total partition tree. By contrast, if $\mathcal{T}$ is a partial partition tree, then $\mathcal{T}_Y$ may be either a total or a partial partition tree.

# 4 Image Modeling

In this section, we show that the components of a digital image, namely its support and its value space, can be handled as graphs. This will allow us to further develop our study in the general framework of (valued) graphs, that will encompass images.

Let $\Omega$ and $\mathcal{V}$ be two sets. An image is defined as a function $\mathcal{F}: \Omega \to \mathcal{V}$. The set $\Omega$ is the support of the image $\mathcal{F}$. The elements $\mathbf{x} \in \Omega$ are the points of $\mathcal{F}$. The set $\mathcal{V}$ is the value space of the image $\mathcal{F}$. The elements $\mathbf{v} \in \mathcal{V}$ are the values of $\mathcal{F}$. We assume that both $\Omega$ and $\mathcal{V}$ are finite, which is a hypothesis compliant with the use cases of digital imaging.

## 4.1 Structure of the image support

In most imaging applications, the support of an image is a finite part $\Omega$ of the Cartesian grid $\mathbb{Z}^d$ ($d \ge 1$), and each point $\mathbf{x} \in \Omega$ is called a pixel. The modeling of a digital image by a hierarchical model requires to endow this discrete support $\Omega$ with a structure that may

be compliant with the topology of the underlying Euclidean space $\mathbb{R}^d$. Various topological frameworks were proposed to reach that goal. The most popular is the framework of digital topology [10] which symbolically models the adjacency relation between points as a non-directed graph. Alternatively, the framework of cubical complexes [11] models points in $\mathbb{Z}^d$ as open hypercubes in $\mathbb{R}^d$ and explicitly represents the adjacency relation between them via a combinatorial complex (which can be seen as a hypergraph). These two topological frameworks of $\mathbb{Z}^d$ present the advantage of being mutually compliant [13] and also compliant with the underlying continuous topology in $\mathbb{R}^d$ [12]. They can be generalized to less regular supports: non-Cartesian (e.g. hexagonal, triangular) grids, general complex models (e.g. simplcial models, meshes), etc. They also present the advantage of endowing the image support $\Omega$ with two important topological notions: (1) the connectedness, which is mandatory to define the connected components that will be the cornerstone for building partitions of $\Omega$, and (2) the Jordan-Brouwer property that allows to avoid ill-defined topological organization of the connected components. The first (connectedness) property is mandatory for all the morphological trees. The second (Jordan-Brouwer) is required only for the morphological trees within the family of the tree of shapes.

The multivalued component tree is an extension of the component tree. In particular, it handles images that need not to fulfill the Jordan-Brouwer property. In this context, the only notion of connectedness is manda-
tory. Although satisfied by the two frameworks of digital topology and cubical complexes, the connectedness is more generally provided by any framework based on (non-oriented) graphs. In the sequel, we will then assume that the support $\Omega$ of the handled images is organized as a graph. This hypothesis remains compliant with the standard topological frameworks designed in [10, 11], while it also enables the use of multivalued component trees on mathematical objects that may not be images, provided that they are designed as valued graphs.

Based on the previous discussion, we assume that $\Omega$ is endowed with an adjacency (i.e. irreflexive and symmetric) relation $\wedge$. The couple $\mathcal{G} = (\Omega, \wedge)$ is then a (non-directed) graph. The connectedness relation $\leftrightarrow$ on $\Omega$ induced by the adjacency $\wedge$ is the reflexive-transitive closure of $\wedge$. By construction, $\leftrightarrow$ is an equivalence relation on $\Omega$. Without loss of generality, we can assume that $(\Omega, \leftrightarrow)$ is a connected graph, i.e. that $\Omega/\leftrightarrow = \{\Omega\}$. Let $X \subseteq \Omega$ be a part of the image support. The restriction of $\leftrightarrow$ to $X$ is still an equivalence relation on $X$. The connected components of $X$ are the induced equivalence classes. The set of these connected components is noted $\mathcal{C}[X]$ and is then defined as $\mathcal{C}[X] = X/\leftrightarrow$. This set $\mathcal{C}[X]$ is, in particular, a partition of $X$ (except if $X = \emptyset$). There is an isomorphism between the inclusion relation $\subseteq$ on subsets of $\Omega$ and the partition refinement relation $\supseteq$ on their connected components:

$$ \forall Y, Z \in 2^X, (Y \subseteq Z) \iff (\mathcal{C}[Y] \subseteq \mathcal{C}[Z]) \quad (6) $$

## 4.2 Structure of the value space

In an image, each point $\mathbf{x} \in \Omega$ is associated to a value $\mathcal{F}(\mathbf{x}) = v$ where $v$ belongs to the value space $V$.

The morphological trees that allow to represent / model images $\mathcal{F}$ can be classified into three categories, depending on the kind of information involved in their construction:

1. extrinsic information;

2. metric information;

3. value information.

The first category corresponds to morphological trees built by defining hierarchies of partitions based on information that do not necessarily derive from the image values. This is for instance the case of the binary partition tree, which is built from a user-defined criterion computed from the different connected components. For such trees, there is generally no need to endow the value set $V$ with a specific structure.

The second category corresponds to morphological trees built by defining hierarchies of partitions based

on information that undirectly derive from the values of the points of the image. This is for instance the case of the watershed trees or the $\alpha$-trees, that merge regions with respect to their value proximity ($\alpha$-trees) or to a gradient / saliency measure between them (watershed tree). For such trees, it is required to endow $V$ with a (pseudo)distance, typically a function $\Delta: V \times V \to \mathbb{R}$.

The third category corresponds to morphological trees built by defining hierarchies of partitions based on information that directly derive from the values of the points of the image. This is for instance the case of the component tree and the tree of shapes, that merge regions with respect to the ordering of the values at successive threshold sets (component tree) or level sets (tree of shapes). Considering “successive” sets implies that the values be ordered in a convenient way. In practice, the trees in this category are designed to handle images where the value set $V$ is endowed with a total order $\leq$. Certain value sets are physically / semantically associated to total order relations. This is for instance the case in thermic imaging or nuclear imaging, where $\leq$ is related to the magnitude of a physical parameter, with an induced semantics. However, many other value sets are not natively associated to total order relations. This is often the case when $V$ is part of a Cartesian space $\mathbb{R}^k$ ($k \geq 2$), for instance in natural, medical, remote sensing, biological imaging, where the sets of values are often vectorial with homogeneous (e.g. RGB, multispectral, hyperspectral) or heterogeneous (e.g. multimodal) bands. It may also happen when $V$ is part of a scalar space $\mathbb{R}$ where the canonical order $\leq_{\mathbb{R}}$ does not directly relates to a specific meaning (e.g. magnetic resonance imaging).

In this context, the definition of ad hoc total order relations is an important research topic that led to many contributions over the last decades. (A complete discussion on this topic is beyond the scope of this article; see e.g. [63–65].) This issue is, a fortiori, important in the field of mathematical morphology, where the availability of a lattice structure for images (natively available with totally ordered values) is mandatory [66].

Having access to a total order on $V$ provides a sufficient condition for conveniently dealing with various concepts of mathematical morphology, including the morphological hierarchies related to the component tree and the tree of shapes. By contrast, a partial order on $V$ generally leads to more complex image models such as the component-graph [49] which is the extension of the component tree to partially ordered valued images. The component-graph is a DAG, which is then harder to build and handle than the component tree [67].

At the frontier between total and partial orders, the notion of a hierarchical order allows to provide a rich
<figure><img src="image_4.png" /><figcaption>**Fig. 3** A set $\Omega$ defined as $\llbracket 0, 5 \rrbracket^2$, endowed with the adjacency $\wedge$ associated to the 4-adjacency, leading to the graph $\mathcal{G} = (\Omega, \wedge)$. The elements of $\Omega$ are depicted by squares. The associated $\alpha$ values are given in these squares. The elements of $\wedge$ are depicted by edges. The associated $\beta$ values are given on the right of above these edges. The graph $\mathcal{G} = (\Omega, \wedge)$ is endowed with three distinct sets of functions $\alpha$ and $\beta$ in (a-c) which satisfy Eq. (11). The functions $\alpha$ and $\beta$ in (a) satisfy Eq. (12), whereas they do not in (b,c). The functions $\alpha$ and $\beta$ in (b) satisfy Eq. (13), whereas they do not in (a,c). In (c), the edges that violate Eq. (13) are depicted in red.</figcaption></figure>

organization of the values of $V$ that remains however
compliant with the modeling of images by a morpho-
logical tree. Then, we propose to endow the value set $V$
with a hierarchical order. One may keep in mind that a
total order is also a hierarchical order, and the proposed
framework is then a relevant extension of the existing
total order paradigms previously proposed in the liter-
ature.

When a set of values $V$ is endowed with a hierar-
chical order $\leq$, the analogue of the component tree of
an image $\mathcal{F}: \Omega \to V$ becomes a so-called multival-
ued component tree. Unusually, this tree may be a par-
tial, a total or a general partition tree. This ability of a
morphological tree—and in particular of a multivalued
component tree—to be possibly a total or a partial par-
tition tree invites us to investigate the links that may
exist between these two families of trees. Before focus-
ing our study on the multivalued component tree itself
(Sections 6–7), we then propose, in Section 5, a discus-
sion on the way to express the morphological total /
partial partition trees in a unified way.

5 Total / Partial Partition Trees: A Common Definition Framework

In this section, we show that partial and total partition
hierarchies can be expressed in a unified framework,
from both structural and algorithmic points of view.
In this context, we will observe that the multivalued
component tree appears as a missing brick to fill the
gap between these two families of partition hierarchies.

Partition trees model the inclusion relation $\subseteq$ of the
elements $X \in 2^\Omega$ of successive partitions $\mathcal{P} \in \Pi(\Omega)$
totally ordered with respect to the refinement relation
$\subseteq$.

In both—partial or total—paradigms, the first par-
tition that we consider is $\mathcal{P}_0 = \{\Omega\}$, i.e. the partition
composed of a unique set which is $\Omega$ itself. This set $\Omega$ is
the maximum of the ordered set $(\Theta, \subseteq)$ defined by ag-
gregating in $\Theta$ all the elements of all the partitions, and
then the root of the induced (partial or total) partition
tree $(\Theta, \subset)$.

We pointed out that defining a partition of a set is
equivalent to defining an equivalence relation on that
set. In particular, the first partition $\mathcal{P}_0 = \{\Omega\}$ is the
partition associated to the equivalence relation $\leftrightarrow_0 =
\Omega \times \Omega$, and equivalently to the complete graph $(\Omega, \leftrightarrow_0
) = (\Omega, \Omega \times \Omega)$.

An equivalence relation is reflexive, transitive and symmetric. In particular, it can be defined as the transitive closure of an adjacency (i.e. reflexive, symmetric) relation. Here, we suppose that a given equivalence relation $\leftrightarrow_i$ is induced by the transitive closure of an adjacency $\wedge_i$. In particular, we can assume that the partition $\mathcal{P}_0 = \{\Omega\}$ and the associated complete graph $(\Omega, \leftrightarrow_0)$ are induced by transitive closure from an adjacency graph $(\Omega, \wedge)$.

It is then possible to characterize the construction of
a set $\Pi_p = \{\mathcal{P}_i\}_{i=0}^p (p \ge 0)$ of general partitions totally
ordered with respect to the refinement relation $\subseteq$ via
a set of subgraphs<fnref n="1" /> of $(\Omega, \wedge)$ obtained by successive

<footnote n="1">¹ Here, given a graph $(X, \wedge_X)$, a subgraph is defined as a graph $(Y, \wedge_Y)$ such that $Y \subseteq X$ and $\wedge_Y \subseteq \wedge_X$. In particular, for the sake of concision, this definition of a subgraph</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 4 The subgraphs $\mathcal{G}_i = (X_i, \frown_i) = (\Lambda_i(\alpha), \Lambda_i(\beta))$, for $i \in [0, 4]$, obtained from the graph $\mathcal{G} = (X, \frown)$ and the functions $\alpha$ and $\beta$ depicted in Fig. 3(a). The two connected components in red in $(X_2, \frown_2)$ and $(X_3, \frown_3)$ are the same in (c,d) whereas the incident edges are distinct. They correspond to a unique node (in red) in the total partition tree of Fig. 7(a).</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 5 The subgraphs $\mathcal{G}_i = (X_i, \frown_i) = (\Lambda_i(\alpha), \Lambda_i(\beta))$, for $i \in [0, 4]$, obtained from the graph $\mathcal{G} = (X, \frown)$ and the functions $\alpha$ and $\beta$ depicted in Fig. 3(b). The two connected components in red in $(X_3, \frown_3)$ (c) correspond to flat zones of maximal value. They correspond to leaf nodes (in red) in the partial partition tree of Fig. 7(b) defined at a threshold value (3) strictly lower than the maximum (4). This can only occur in partial partition trees.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6 The subgraphs $\mathcal{G}_i = (X_i, \frown_i) = (\Lambda_i(\alpha), \Lambda_i(\beta))$, for $i \in [0, 4]$, obtained from the graph $\mathcal{G} = (X, \frown)$ and the functions $\alpha$ and $\beta$ depicted in Fig. 3(c). The connected components in red in $(X_3, \frown_3)$ and $(X_4, \frown_4)$ form a subtree which is a total partition tree, depicted in red in Fig. 7(c). As a consequence, the partial partition tree of Fig. 7(c) is impure.</figcaption></figure>

thresholdings of two couples of valuation functions:

$$ \alpha : \Omega \to [0, p] \qquad (7) $$

$$ \beta : \frown \to [0, p] \qquad (8) $$

defined on the elements of $\Omega$ and the adjacency links of $\frown$, respectively. (Three examples of such valued graphs are given in Fig. 3.) Given a function $f : A \to \mathbb{N}$, the thresholding of $f$ at value $\nu \in \mathbb{N}$ is defined by:

$$ \Lambda_{\nu}(f) = \{a \in A \mid \nu \le f(a)\} \qquad (9) $$

This definition of thresholding for the ordered set $(\mathbb{N}, \le)$ holds for any other ordered set.

Let us suppose that the graph $(\Omega, \frown)$ is endowed with two valuation functions $\alpha$ and $\beta$. For all $i \in \mathbb{N}$,

merges the two usual notions of subgraph and partial graph commonly considered in the literature.

we define $X_i = \Lambda_i(\alpha)$ and $\frown_i = \Lambda_i(\beta)$. We can then build a sequence of subgraphs $\{(X_i, \frown_i)\}_{i=0}^p$ (Figs. 4-6) associated to a sequence $\{(X_i, \leftrightarrow_i)\}_{i=0}^p$, with $\leftrightarrow_i$ the reflexive-transitive closure of $\frown_i$ on $X_i$, and then also associated to a sequence $\{\mathcal{P}_i\}_{i=0}^p$ where $\mathcal{P}_i$ is the partition associated to the quotient set $X_i/\leftrightarrow_i$. For any $i, j \in [0, p]$ we have:

$$ (i \le j) \implies (\mathcal{P}_j \in \mathcal{P}_i) \qquad (10) $$

In order to obtain coherent results from the thresholdings of $\alpha$ and $\beta$ at each value $i \in [0, p]$, i.e. to ensure that $(X_i, \frown_i)$ is a graph, it is mandatory that the following property that links $\alpha$ and $\beta$ be satisfied:

$$ \forall \mathbf{x}, \mathbf{y} \in \Omega, (\mathbf{x} \frown \mathbf{y}) \implies \left( \beta((\mathbf{x}, \mathbf{y})) \le \bigwedge \{\alpha(\mathbf{x}), \alpha(\mathbf{y})\} \right) $$
<figure><img src="image_8.png" /><figcaption>**Fig. 7** The partition trees $\mathcal{T} = (\Theta, \triangleleft)$ associated to the three valued graphs of Fig. 3, and induced by the subgraphs of Figs. 4–6. The threshold values (0–4) are depicted on the left of the trees. Each black square corresponds to an element of $\Theta$. Each edge corresponds to an element of $\triangleleft$. (a) The total partition tree (similar to a watershed tree) associated to Fig. 3(a) and Fig. 4. (b) The (pure) partial partition tree (similar to a component-tree) associated to Fig. 3(b) and Fig. 5. (c) The impure partial partition tree associated to Fig. 3(c) and Fig. 6. The red parts in these trees correspond to the red connected components discussed in Figs. 4–6.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Algorithm 1:** Partition tree construction</figcaption></figure>

(11)

In practice, the definitions of $\alpha$ and $\beta$ contribute to determine the nature of the induced partition tree. In

<figure><img src="image_10.png" /><figcaption>**Function Collapse($\mathfrak{G}$, $\alpha, \beta, \mathcal{E}$)**</figcaption></figure>

particular, let us consider the following two properties,
<figure><img src="image_11.png" /><figcaption>**Fig. 8** Example of the application of Function Collapse on the input valued graph depicted in (a), with the same conventions as in Fig. 3. The red edge corresponds to $\mathcal{E}$ and the red vertices are the two collapsed ones. The green edges and their $\beta$ values are those impacted by the function. The output valued graph is depicted in (b).</figcaption></figure>

that allow to satisfy Eq. (11):

$$ \forall \mathbf{x} \in X, \alpha(\mathbf{x}) = p \qquad (12) $$

$$ \forall (\mathbf{x}, \mathbf{y}) \in \mathcal{C}, \beta((\mathbf{x}, \mathbf{y})) = \bigwedge \{\alpha(\mathbf{x}), \alpha(\mathbf{y})\} \qquad (13) $$

Two cases can occur.

1. If Eq. (12) holds true (see Fig. 3(a)), then for any $i \in [0, p]$ we have $X_i = \Omega$ (see Fig. 4), and the induced partition tree $\mathcal{T}$ is then a total partition tree (see Fig. 7(a)). The binary partition tree and the watershed tree are typical examples of total partition trees. Note that if both Eqs. (12–13) hold true then $\mathcal{T}$ is the trivial tree ($\{\Omega\}, \emptyset$), composed of one node which is both the root and the unique leaf.

2. If Eq. (12) holds false (see Fig. 3(b,c)), then we have $X_i \neq \Omega$ for some $i \in [1, p]$ (see Figs. 5–6) and the induced partition tree $\mathcal{T}$ is not a total partition tree (see Fig. 7(b,c)). Then, two subcases can occur.

(a) If for each non-leaf node $X \in \Theta \setminus \Delta^c \Theta$, the set $\{Y \in \Theta | Y \triangleleft X\}$ is a partial partition of $X$, then we say that $\mathcal{T}$ is a partial partition tree (see Figs. 5 and 7(b)). The component tree is a typical example of partial partition tree.

(b) If there exists a non-leaf node $X \in \Theta \setminus \Delta^c \Theta$ such that the set $\{Y \in \Theta | Y \triangleleft X\}$ is a total partition of $X$, then we say that $\mathcal{T}$ is an impure partial partition tree (see Figs. 6 and 7(c)). If this subcase occurs then Eq. (13) holds false.

In the sequel, we will sometimes use the terminology “pure partial partition tree” for “partial partition tree”.

Both the total partition trees and the partial partition trees (see Fig. 7(a,b)) are currently used in the framework of morphological hierarchies. The impure partial partition trees (see Fig. 7(c)) are much less considered, despite their potential usefulness. They also provide a way to establish a continuum between total partition trees and partial partition trees, leading to a unifying framework for describing morphological trees.

The unification of these various kinds of trees is notably characterized by the fact that we can rely on a same algorithm for building the total and (pure / impure) partial partition trees. This construction process is given in Algorithm 1 and the associated Function Collapse. In this algorithm and the next ones, we use the following notations:

- “$A := B$” means that $A$ is set with $B$;

- “$A \leftarrow B$” means that $B$ is added to $A$;

- “$A \to B$” means that $B$ is set as an element removed from $A$.

Note that in Algorithm 1 and Function Collapse, the elements of $\Omega$ are handled as sets. This does not induce any issue by assuming that the set $\Omega$ given as input of Algorithm 1 is modeled as the equivalent set $\{\{x\} | x \in \Omega\}$.

Basically, this algorithm builds the partition tree $\mathcal{T} = (\Theta, \triangleleft)$ associated to a graph $\mathcal{G} = (\Omega, \mathcal{C})$ endowed with two valuation functions $\alpha$ and $\beta$ in a bottom-up fashion, i.e. from the leaves of the partition tree to its root. In practice, Algorithm 1 models iteratively (Line 5) the merging at threshold value $i$ of the nodes of the tree that exist at threshold value $i+1$. To do so, it adds to these nodes the vertices of $\alpha$ value $i$, i.e. those that “appear” at value $i$ (Lines 11–12). Then it merges the nodes that are linked by edges of $\beta$ value $i$ (Line 13), leading to new nodes of $\Theta$ and updates the $\triangleleft$ links accordingly. The creation of these new nodes of $\Theta$ is carried out by pairwise merging of nodes, thanks to the Function Collapse, which modifies locally the part of the graph in the neighbourhood of the merged nodes, as exemplified in Fig. 8.

Of course, this construction process is far from optimal. In particular its time cost does not reach the quasi-linear time of the standard construction schemes for component trees, binary partition trees, etc. Its interest lies in its ability to formalize the construction of the trees of each family the same way, i.e. as an iterative graph collapsing procedure (which is also the paradigm frequently used for building binary partition trees, alpha trees, etc.).

The multivalued component tree may be any (pure / impure partial or total) partition tree. In the next sections, we propose a study of this morphological tree.

# 6 Building the Multivalued Component Tree

In this section, we explain how to build the multivalued component tree (Sections 6.2–6.3). Before this algorithmic discussion, we first recall the definition of the multivalued component tree.
<figure><img src="image_12.png" /><figcaption>**Fig. 9** A set of values $\mathbb{V} = \{a,b,c,d,e,f,g,h,i\}$, endowed with a lower-hierarchical order $\leq$ such that the minimum is a and the maximal elements are d, e, f, h, i. This ordered set is depicted as its Hasse diagram, which is a lower-tree.</figcaption></figure>

## 6.1 Multivalued component tree

Let $\Omega$ be a finite set and $\frown$ an adjacency relation on $\Omega$ that induces the connectedness relation $\leftrightarrow$. The couple $\mathfrak{G} = (\Omega, \frown)$ is a non-directed graph. We assume that $\mathfrak{G}$ is connected. Let $\mathbb{V}$ be a finite set and $\leq$ a lower-hierarchical order on $\mathbb{V}$. (If $\leq$ is a upper-hierarchical order, we can substitute $\geq$ to $\leq$, and the following definitions still hold.) Let us consider an image $\mathcal{F}$ defined as a function $\mathcal{F}: \Omega \to \mathbb{V}$. An example of lower-hierarchically ordered set $(\mathbb{V}, \leq)$ is given in Fig. 9. Three examples of images $\mathcal{F}_i: \Omega \to \mathbb{V}$ ($1 \leq i \leq 3$) are given in Fig. 10, for a support $\mathfrak{G} = (\Omega, \frown)$ similar to that of Fig. 3.

Note that if $\leq$ is a total order, the following definitions are those of the standard component tree.

We set:

$$ \Theta = \bigcup_{v \in \mathbb{V}} \mathcal{C}[\Lambda_v(\mathcal{F})] \qquad (14) $$

which gathers the connected components at each threshold set $\Lambda_v(\mathcal{F})$ ($v \in \mathbb{V}$). The threshold set $\Lambda_v(\mathcal{F}_i)$ of the three images $\mathcal{F}_i$ of Fig. 10 are depicted in Figs. 11–13.

The elements of $\Theta$ are called the nodes of the multivalued component tree. A node may be generated at many threshold values (see examples in Figs. 11–13). In particular, for any $X \in \Theta$, we set:

$$ \mathbb{I}(X) = \{v \in \mathbb{V} \mid X \in \mathcal{C}[\Lambda_v(\mathcal{F})]\} \qquad (15) $$

The set $\mathbb{I}(X)$ is a nonempty interval, i.e. it is a totally ordered set and for any $v, v', v'' \in \mathbb{V}$ with $v \leq v' \leq v''$, if $v, v'' \in \mathbb{I}(X)$ then we have $v' \in \mathbb{I}(X)$. For any $X \in \Theta$, we set:

$$ \omega(X) = \bigvee_{\leq} \mathbb{I}(X) \qquad (16) $$

and we define the remanence $\tau(X)$ of $X$ as:

$$ \tau(X) = |\mathbb{I}(X)| \qquad (17) $$

The inclusion relation $\subseteq$ is a upper-hierarchical order on $\Theta$. We note $\triangleleft$ the reflexive-transitive reduction of $\subseteq$

with respect to $\Theta$. The couple $(\mathfrak{T}, \triangleleft)$ is a upper-tree called the multivalued component tree. The multivalued component trees $\mathfrak{T}_{\mathcal{F}_i}$ ($1 \leq i \leq 3$) of the images $\mathcal{F}_i$ of Fig. 10 associated to the nodes induced by the connected components of the threshold sets of Figs. 11–13 are given in Fig. 14. These three examples shed light on the fact that a multivalued component tree can be a total partition tree (Fig. 14(a)), a pure partial partition tree (Fig. 14(b)) or an impure partial partition tree (Fig. 14(c)).

For any $X \in \Theta$, we define the proper part $\rho(X) \subseteq \Omega$ of $X$ as:

$$ \rho(X) = X \setminus \bigcup_{Y \triangleleft X} Y \\ = \{\mathbf{x} \in \Omega \mid \mathcal{F}(\mathbf{x}) = \omega(X)\} \qquad (18) $$

For any $v \in \mathbb{V}$, we set:

$$ \Theta_v = \{X \in \Theta \mid \omega(X) = v\} \qquad (19) $$

In particular, we have $\Theta = \bigcup_{v \in \mathbb{V}} \Theta_v$.

The multivalued component tree $\mathfrak{T}$ is an image model of the image $\mathcal{F}$. Indeed, one can reconstruct $\mathcal{F}$ from $\mathfrak{T}$ as follows:

$$ \forall \mathbf{x} \in \Omega, \mathcal{F}(\mathbf{x}) = \bigvee_{X \in \Theta} \mathbf{1}_{(X, \omega(X))}(\mathbf{x}) \qquad (20) $$

where $\mathbf{1}_{(A,u)}: \Omega \to \mathbb{V}$ is the function defined by $\mathbf{1}_{(A,u)}(\mathbf{x}) = u$ if $\mathbf{x} \in A \subseteq \Omega$ and $\bigwedge \leq \mathbb{V}$ otherwise.

As mentioned above, the definitions given for the multivalued component tree are actually the same as for the standard component tree. The only differences are the following:

- $\leq$ is a hierarchical order whereas it is a total order in the case of the component tree;

- it may happen that $\rho(X) = \emptyset$ (when a node $X$ is totally partitioned by nodes at greater values) whereas we have $\rho(X) \neq \emptyset$ in the case of the component tree.

Here, we assumed that $\leq$ is a lower-hierarchical order on $\mathbb{V}$. This corresponds to the definition of the multivalued component tree as an extension of the so-called max-tree. It is also possible to define $\leq$ as a upper-hierarchical order on $\mathbb{V}$ (leading to trivial modifications of the above definitions, left to the reader). In that case, the induced multivalued component tree as an extension of the so-called min-tree.

## 6.2 A previous algorithm

In [38], a first strategy had been proposed for building the multivalued component tree. Its description and
<figure><img src="image_13.png" /><figcaption>**Fig. 10 (a-c)** Three images defined as functions $\mathcal{F}_i : \Omega \to \mathbb{V} (1 \le i \le 3)$. The set $\Omega$ is defined as $[[0,5]]^2$ and endowed with the adjacency $\wedge$ associated to the 4-adjacency, leading to the graph $\mathcal{G} = (\Omega, \wedge)$. The elements of $\Omega$ are depicted by squares. The elements of $\wedge$ are depicted by black lines. The set of values $\mathbb{V}$ is defined as in Fig. 9 with the same hierarchical order relation $\le$. The value $\mathcal{F}_i(\mathbf{x})$ of each point $\mathbf{x}$ is given in the corresponding square, and associated to the color according to Fig. 9.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>**Fig. 11** The threshold sets $\Lambda_v(\mathcal{F}_1)$ for the image $\mathcal{F}_1$ of Fig. 10(a). The squares depicted in color (resp. white) belong (resp. do not belong) to $\Lambda_v(\mathcal{F}_1)$. A connected component is common to the threshold sets $\Lambda_c(\mathcal{F}_1)$, $\Lambda_g(\mathcal{F}_1)$. A connected component is common to the threshold sets $\Lambda_c(\mathcal{F}_1)$, $\Lambda_g(\mathcal{F}_1)$, $\Lambda_h(\mathcal{F}_1)$. A connected component is common to the threshold sets $\Lambda_c(\mathcal{F}_1)$, $\Lambda_g(\mathcal{F}_1)$, $\Lambda_i(\mathcal{F}_1)$. For each connected component (which is not a flat zone) at a given value, there is a total partition of connected components at greater values.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>**Fig. 12** The threshold sets $\Lambda_v(\mathcal{F}_2)$ for the image $\mathcal{F}_2$ of Fig. 10(b). The squares depicted in color (resp. white) belong (resp. do not belong) to $\Lambda_v(\mathcal{F}_2)$. A connected component is common to the threshold sets $\Lambda_c(\mathcal{F}_2)$, $\Lambda_g(\mathcal{F}_2)$, $\Lambda_h(\mathcal{F}_2)$. For each connected component (which is not a flat zone) at a given value, there is a non-total partition of connected components at greater values.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>**Fig. 13** The threshold sets $\Lambda_v(\mathcal{F}_3)$ for the image $\mathcal{F}_3$ of Fig. 10(c). The squares depicted in color (resp. white) belong (resp. do not belong) to $\Lambda_v(\mathcal{F}_3)$. A connected component is common to the threshold sets $\Lambda_c(\mathcal{F}_3)$, $\Lambda_g(\mathcal{F}_3)$, $\Lambda_h(\mathcal{F}_3)$. For one connected connected component of $\Lambda_b(\mathcal{F}_3)$, there is a total partition of connected components at greater values (d,e). For one connected connected component of $\Lambda_g(\mathcal{F}_3)$, there is a total partition of connected components at greater values (h,i). For each other connected component (which is not a flat zone) at a given value, there is a non-total partition of connected components at greater values.</figcaption></figure>

proof of correctness are given in [38], so we only summarize it hereafter.

The main idea of this construction approach is to rewrite the image $\mathcal{F}: \Omega \to \mathbb{V}$ as an image $\hat{\mathcal{F}}: \hat{\Omega} \to \hat{\mathbb{V}}$ where $\hat{\Omega} \supseteq \Omega$ and $\hat{\mathbb{V}} = [[0, p]] \subset \mathbb{N}$ with $p \le |\mathbb{V}|$. The set
<figure><img src="image_17.png" /><figcaption>**Fig. 14** Multivalued component trees. Each disk / hexagon corresponds to a node $X$ of $\Theta$ (when a node $X$ is an hexagon, it corresponds to many occurrences of a same connected component at successive threshold sets, i.e. $\tau(X) > 1$). The color of the disk corresponds to the value $\omega(X)$ of the node. Each edge corresponds to a link of $\langle$ (the grey edges correspond to total partitions, the black edges to non-total partitions). (a) The multivalued component tree corresponds to the image of Fig. 10(a) and the nodes correspond to the connected components depicted in Fig. 11. This tree is a total partition tree. (b) The multivalued component tree corresponds to the image of Fig. 10(b) and the nodes correspond to the connected components depicted in Fig. 12. This tree is a pure partial partition tree. (c) The multivalued component tree corresponds to the image of Fig. 10(c) and the nodes correspond to the connected components depicted in Fig. 13. This tree is an impure partial partition tree.</figcaption></figure>

$\hat{V}$ is endowed with the (total) order $\leq$ on $\mathbb{N}$ such that there is a homomorphism from $(V, \leq)$ to $(\hat{V}, \leq)$ induced by the equivalence relation on $V$ that gathers the values of equal distance with respect to the minimum $\wedge \leq V$ in the Hasse diagram of $(V, \leq)$. The set $\hat{\Omega}$ is endowed with an adjacency $\frown \hat{\Omega}$ such that there is an increasing homeomorphism from the graph $(\Omega, \frown)$ to the graph $(\hat{\Omega}, \frown \hat{\Omega})$ defined by adding a new vertex $\varepsilon_{\{x,y\}}$ in $\hat{\Omega}$, and replacing the adjacency link $x \frown y$ by the two links $x \frown \varepsilon_{\{x,y\}}$ and $\varepsilon_{\{x,y\}} \frown y$, whenever the two vertices $x, y \in \Omega$ are such that $x \frown y$ while $F(x)$ and $F(y)$ are non-comparable with respect to $\leq$. It is proved that the component tree (max-tree) $\hat{\mathcal{T}}$ of $\hat{F}$ is isomorphic to the multivalued component tree $\mathcal{T}$ of $F$.

It is then possible to build a multivalued component tree by using any algorithm dedicated to the construction of the component tree, at the cost of the preprocessing step that builds $\hat{F}$ from $F$, and a post-processing step that retrieves $\mathcal{T} = (\Theta, \langle)$ from $\hat{\mathcal{T}} = (\hat{\Theta}, \widehat{\langle})$ by removing from the proper part $\rho(X)$ of each node $X \in \hat{\Theta}$ the elements of $X \setminus \Omega$ and by substituting the threshold values of $V$ to those of $\hat{V}$.

## 6.3 A new algorithm

The algorithm summarized in the previous section requires to modify the considered image $F$ in order to make it compliant with existing component tree construction algorithms that act on grey-level images. We now present a new, alternative algorithm that no longer requires such pre-conditioning of the image $F$. This construction scheme, detailed in Algorithm 2 and Function Flood, is derived from the component tree construction proposed by Salembier et al. in [28]. It also

<caption>**Algorithm 2:** Building the multivalued component tree</caption>

**Input:** Graph $(\Omega, \frown)$
**Input:** Lower-hierarchically ordered set $(V, \leq)$
**Input:** Function $F: \Omega \to V$
**Output:** Multivalued component tree $\mathcal{T} = (\Theta, \langle)$
1. Build nodes
2. Build points
3. Build status
4. Build nb_nodes
5. Build index
6. Build progress
7. $v_{\min} := \wedge \leq V$
8. Choose $\mathbf{x}_{\min} \in \Omega$ such that $F(\mathbf{x}_{\min}) = v_{\min}$
9. points[$v_{\min}$].add($\mathbf{x}_{\min}$)
10. progress[$v_{\min}$] := true
11. Flood($v_{\min}$)

finds inspiration in the mask-based algorithm developed by Ouzounis et al. in [68]. The difference with the algorithm proposed by Salembier et al. lies in the way of handling adjacent points with non-comparable values.

In Algorithm 2, without loss of generality, we assume that there exists $\mathbf{x}_{\min} \in \Omega$ such that $F(\mathbf{x}_{\min}) = \wedge \leq V$ (Line 8). The proposed algorithm relies on the following data structures:

- **nodes**: a 2D array which stores the nodes of the multivalued component tree. The first dimension is indexed by the values of $V$. The second dimension is indexed by the identifiers of the nodes. In other words, **nodes** encodes $\Theta$; **nodes**[$v$] encodes the nodes of $\Theta$ at value $v$; and **nodes**[$v$] [$i$] encodes the $i$th node of $\Theta$ at value $v$;

- **points**: a 2D array which stores the processed points of the image. The first dimension is indexed by the
Function Flood

Input: $u \in \mathbb{V}$: current level

Output: $w \in \mathbb{V}$: value of the parent node of the root of the built (partial) multivalued component tree at value $u$ (or $\varepsilon$ if the node has no parent)

1 while $!(points[u].empty())$ do
2     $x := points[u].remove()
3     if index[u] > nb_nodes[u] then
4         nb_nodes[u] := index[u] // nb_nodes[u]++
5         $X := create_node() // new node in $\Theta$
6         nodes[u].insert($X$)
7     if $\mathcal{F}(x) \neq u$ then
8         $w := \mathcal{F}(x)$
9         points[w].add($x$)
10        progress[w] := true
11     while $u < w$ do
12         $w := \text{Flood}(w)$
13 else
14     status[x] := index[u]
15     nodes[u][index[u]].add_to_proper_part(x)
16     foreach $y \cap x$ do
17         $w := \mathcal{F}(y)$
18         if status[y] = -1 then
19             if $u \le w$ then
20                 $\hat{w} := w$
21             else
22                 $\hat{w} := \bigwedge \{u, w\}$
23         points[$\hat{w}$].add(y)
24         status[y] := 0
25         progress[$\hat{w}$] := true
26     while $u < \hat{w}$ do
27         $\hat{w} := \text{Flood}(\hat{w})$

28 if $u = v_{\min}$ then
29     $w := \varepsilon$
30 else
31     $w := \bigwedge \{w' \in \mathbb{V} \mid w' < u\}$
32     while progress[w] = false do
33         $w := \bigwedge \{w' \in \mathbb{V} \mid w' < w\}$
34     create_edge nodes[u][index[u]], nodes[w][index[w]]
35     // new edge in $\triangleleft$
36 progress[u] = false
37 index[u]++
38 return $w$

values of $\mathbb{V}$. In other words, `points[v]` encodes all the points $x \in \Omega$ currently processed “at value $v$”;

- `status`: a 1D array which stores the status of each point of the image. For any point $x \in \Omega$, we have `status[x] = -1` if $x$ is unprocessed; `status[x] = 0` if $x$ belongs to `points`; and `status[x] = i > 0` if $x$ belongs to the proper part $\rho(X)$ of the node $X$ stored in `nodes[$\mathcal{F}(x)$]` [i];

- `nb_nodes` and `index`: two 1D arrays which store the number of nodes already fully built and the index of the node currently built at each value of $\mathbb{V}$, respectively;

- `progress`: a 1D array which indicates if there exists a node at value $v$, currently under construction or to be built, which is an ancestor of the node at value $u$ currently being defined.

By comparison with the component tree construction method proposed by Salembier et al., the one proposed here for multivalued component tree construction differs with regard to Function Flood. In particular, the core of Algorithm 2 is globally the same as in [28]. In Function Flood, the additional parts compared to [28] are the following:

- In [28], we have $x \in \text{nodes}[\mathcal{F}(x)]$. Here (Lines 7-12), we may have $x \in \text{nodes}[u]$ with $u \neq \mathcal{F}(x)$. This happens when $x$ is stored in `nodes` as the neighbour of another point with a non-comparable value. In such case, the chosen value $u$ is the infimum of these two non-comparable values, and we have in particular $u < \mathcal{F}(x)$.

- For two adjacent points $x \cap y$, it may occur that $\mathcal{F}(x)$ and $\mathcal{F}(y)$ be non-comparable. In particular, the “else” case at Line 21 means that either $u > w$ or $u$ and $w$ are non-comparable. In the first case, $\hat{w}$ is set to $w$. In the second case, $\hat{w}$ is the infimum of $u$ and $w$, distinct from them. In this last case, the point $y$ of value $w$ is added to `nodes[$\hat{w}$]` and not to `nodes[w]`. This will further result in the scenario discussed above (Lines 7-12).

An example of the behaviour of this algorithm is given in Figs. 15-16. For the image $\mathcal{F}: \Omega \to \mathbb{V}$ of Fig. 15(a), the order of processing of the points of $\Omega$ in Algorithm 2 is given in Fig. 15(b), from the first (1) to the last one (36). Fig. 16 shows the progression of the construction of the multivalued component tree of $\mathcal{F}$ with respect to the processed points.

A proof of correctness of Algorithm 2 and Function Flood is given in Appendix A.

We discuss hereafter on the space and time cost of this construction scheme. In this analysis, we assume that $|\cap| = \mathcal{O}(|\Omega|)$, which is the case in digital images. We note $\kappa(\mathbb{V})$ the time cost required to compare two elements of $\mathbb{V}$ or to compute their infimum. Depending on the way $(\mathbb{V}, \leq)$ is modeled, $\kappa(\mathbb{V})$ may vary from $\mathcal{O}(1)$ (with a space cost of $\mathcal{O}(|\mathbb{V}|^2)$) to $\mathcal{O}(\log|\mathbb{V}|)$ or $\mathcal{O}(|\mathbb{V}|)$ (depending on the equilibrium of the Hasse diagram, with a space cost of $\mathcal{O}(|\mathbb{V}|)$). We note $h(\mathbb{V}) \in \mathbb{N}$ the height of the Hasse diagram of $(\mathbb{V}, \leq)$.

Regarding the data structures:

- The size of `nodes` is $\mathcal{O}(|\Omega|)$. It is initialized with a time cost $\mathcal{O}(1)$. When accessing `nodes[v]` for reading or writing, the induced time cost is $\mathcal{O}(\log(|\Omega|))$.

- The size of `points` is $\mathcal{O}(|\Omega|)$. It is initialized with a time cost $\mathcal{O}(|\Omega| \cdot \kappa(|\mathbb{V}|))$. When accessing a set
<figure><img src="image_18.png" /><figcaption>Fig. 15 (a) An image $\mathcal{F}: \Omega \to \mathcal{V}$, following the same conventions as in Fig. 10. (b) The order of processing of the points of $\Omega$ by Algorithm 2, from the first processed point (labeled as “1”) to the last processed point (labeled as “36”). At Line 15 of Algorithm 2, the points y adjacent to x are considered in the clockwise order, starting from the point on the right of x.</figcaption></figure>

points[v] for reading or writing, the induced time cost is $O(1)$.

- The size of status is $O(|\Omega|)$. It is initialized with a time cost $O(|\Omega|)$. Accessing it for reading or writing has a time cost $O(1)$.

- The size of nb_nodes and index is $O(|\Omega|)$. They are initialized with a time cost $O(1)$. Accessing them for reading or writing has a time cost $O(\log(|\Omega|))$.

- The size of progress is $O(h(\mathcal{V}))$. It is initialized with a time cost $O(1)$. Accessing it for reading or writing has a time cost $O(\log(h(\mathcal{V})))$.

Based on these considerations, the time cost for Alg. 2 (except Line 11) is $O(|\Omega| \cdot \kappa(|\mathcal{V}|))$.

The time cost of Flood depends on:

- the size of $\Theta$. In particular, for each node of $\Theta$, Flood is called once, with an induced time cost $O(\log(|\Omega|)+\log(h(\mathcal{V})))$ related to Lines 1 and 35–36;

- the size of $\triangle$. In particular, for each edge of $\triangle$, Flood is called once, with an induced time cost $O(\tau(X) \cdot (\log(h(\mathcal{V}))) + \kappa(|\mathcal{V}|))$ related to Lines 28–34 (where X is the node associated to the processed edge $(X, Y)$);

- the number of points of $\Omega$. In particular, for each point $\mathbf{x} \in \Omega$, the while loop of Flood (Lines 2–27) is run once or twice, with an induced time cost $O(\log(|\Omega|) + \log(h(\mathcal{V}))) + \kappa(\mathcal{V}))$.

It follows that the overall time cost of the construction process (Alg. 2 and Func. Flood) is

$$ \mathcal{T} = O(|\Omega| \cdot (\log(|\Omega|) + h(\mathcal{V}) \cdot \log(h(\mathcal{V}))) + h(\mathcal{V}) \cdot \kappa(|\mathcal{V}|)) \quad (21) $$

If the Hasse diagram of $(\mathcal{V}, \leq)$ is well balanced, the time cost becomes

$$ \mathcal{T} = O(|\Omega| \cdot (\log(|\Omega|) + (\log(|\mathcal{V}|))^2)) \quad (22) $$

The algorithms dedicated to build the standard component tree present a quasi-linear computational cost $O(|\Omega| \cdot \log(|\Omega|))$. The initial algorithm dedicated to build the multivalued component tree [38] (Section 6.2) relies on such quasi-linear time cost algorithms. In addition, it requires a pre- and a post-processing step. During the pre-processing, the support of the image is extended from $\Omega$ to $\hat{\Omega}$, and the time cost of the subsequent component tree construction is then $O(|\hat{\Omega}| \cdot \log(|\hat{\Omega}|))$. We have $|\hat{\Omega}| \geq |\Omega|$, and the size of $\hat{\Omega}$ depends on the size of the subset of edges of $\triangle$ that link vertices of $\Omega$ with non-comparable values. More precisely, we have $|\hat{\Omega}| = |\Omega|$ in the best scenario, i.e. when all the couples of adjacent vertices $\mathbf{x} \triangleleft \mathbf{y}$ are such that $\mathcal{F}(\mathbf{x})$ and $\mathcal{F}(\mathbf{y})$ are comparable. By contrast, we have $|\hat{\Omega}| = |\Omega| + O(|\triangle|)$ when all the couples of adjacent vertices $\mathbf{x} \triangleleft \mathbf{y}$ are such that $\mathcal{F}(\mathbf{x})$ and $\mathcal{F}(\mathbf{y})$ are non-comparable. This last case may generally occur whenever the Hasse diagram of $(\mathcal{V}, \leq)$ is well-balanced. In the case of a $d$-dimensional digital image, the size of $\triangle$ is $d \cdot |\Omega|$. In this context, the overall time cost of the computation of the multivalued component-tree is $O(d \cdot |\Omega| \log |\Omega|)$. We observe in particular that the initial algorithm [38] and the new one proposed here are not sensitive to the same parameters. The first has a time cost that progressively degrades while the dimension of the image increases, while the second has a time cost that progressively degrades while the size of the value space increases. It follows that both algorithms are complementary, and may be considered depending on the application hypotheses.
<figure><img src="image_19.png" /><figcaption>**Fig. 16** Construction of the multivalued component tree of the image $\mathcal{F}: \Omega \to \mathbb{V}$ of Fig. 15(a). The number(s) in the subfigure captions (a–x) correspond to the points $x \in \Omega$ processed by Algorithm 2 at the current stage, and depicted in Fig. 15(b). At a current stage: a plain coloured node is fully built; a contour-coloured node is in construction; a non-coloured node has not been considered yet; a black edge is built; a light gray edge is not built.</figcaption></figure>

# 7 Hierarchical Value (Pre)Ordering

In this section, we discuss on two ways to endow a set of values $\mathbb{V}$ with a hierarchical (pre)order $\leq$. Indeed, the multivalued component tree of an image $\mathcal{F}: \Omega \to \mathbb{V}$ requires that $\mathcal{F}$ be itself a multivalued image where $\mathbb{V}$

is organized with a hierarchical order. (Note that $\leq$ will be defined here as a lower-hierarchical order; the case where $\leq$ would be defined as an upper-hierarchical order is trivially symmetric and left to the reader.)

We propose two strategies:
<figure><img src="image_20.png" /><figcaption>**Fig. 17** Illustration of the construction of a hierarchical preorder on a value set (see Sect. 7.1). (a) Top: an image $\mathcal{F}: \Omega \to \mathbb{V}$. The set $\Omega$ is equal to $[[0, 4]]^2$ and is endowed with an adjacency relation $\sim$ corresponding to the 4-adjacency. Bottom: the set $\mathbb{V}$ composed of 9 values. (b) Top: the histogram of the image $\mathcal{F}$, used as function $\delta_{\mathbb{V}}: \mathbb{V} \to \mathbb{N}$. Bottom: the set $\mathbb{V}$ is endowed with an adjacency $\sim_{\mathbb{V}}$. (c) The component tree of $(\mathbb{V}, \delta_{\mathbb{V}})$ seen as an image from the set of values $\mathbb{V}$ to $\mathbb{N}$ where $\mathbb{V}$ is endowed with $\sim_{\mathbb{V}}$. This component tree defines a hierarchical preorder $\leq$, where the red value is the minimum, the dark blue, yellow and grey values are the maximal elements, and where the three values light blue, green and fuchsia are mutually greater and lower. Once $\mathbb{V}$ is endowed with $\leq$, it becomes possible to compute the multivalued component tree of the image $\mathcal{F}: \Omega \to \mathbb{V}$ of (a) with respect to $\leq$.</figcaption></figure>

- building a preorder $\leq$ on the only values of $\mathbb{V}$. This will most often<fnref n="2" /> lead to the construction of multivalued component trees as partial partition trees (similar, e.g. to component trees). This approach is described in Section 7.1;

- enriching $\mathbb{V}$ with additional values leading to a larger set $\mathbb{W}$ and defining an order $\leq$ on $\mathbb{W}$ so that the values of $\mathbb{V}$ will be the maximal elements of $(\mathbb{W}, \leq)$. This will lead to the construction of multivalued component trees as total partition trees (similar, e.g. to binary partition trees). This approach is described in Section 7.2.

By analogy, the first strategy relates to spanning tree problems, whereas the second relates to Steiner tree problems.

## 7.1 (Pre)ordering the value set

In this section, we aim to build a hierarchical preorder $\leq_{\mathbb{V}}$ on $\mathbb{V}$. Equivalently, this means that we must set:

- an equivalence relation $\sim$ on $\mathbb{V}$ that gathers values that are mutually and symmetrically comparable, leading to a quotient set $\mathbb{V}/\sim$, noted $\mathbb{K}$, where each element, i.e. each equivalence class of $\mathbb{V}$ with respect to $\sim$ is called a *metavalue*;

- a hierarchical order $\leq_{\mathbb{K}}$ on $\mathbb{K}$.

This preorder $\leq_{\mathbb{V}}$ is then defined by:

$$ \forall u, v \in \mathbb{V}, (u \leq_{\mathbb{V}} v) \iff ([u]_{\sim} \leq_{\mathbb{K}} [v]_{\sim}) \quad (23) $$

(If we want to define $\leq_{\mathbb{V}}$ as an order instead of a preorder, it is sufficient to set $\sim$ as $=$, leading to a trivial isomorphism between the orders $(\mathbb{V}, \leq_{\mathbb{V}})$ and $(\mathbb{K}, \leq_{\mathbb{K}})$.)

Let us come back to the notion of a component tree. Let us consider a graph $\mathfrak{G}_{\Delta} = (\Delta, \frown_{\Delta})$ where $\Delta$ is a finite set and $\frown_{\Delta}$ and is an adjacency on $\Delta$, and a function $\delta: \Delta \to \mathbb{N}$ (with $\mathbb{N}$ endowed with the usual $\leq$ relation). One can build the component tree $\mathfrak{T}_{\Delta} = (\Theta_{\Delta}, \frown_{\Delta})$ of $(\mathfrak{G}_{\Delta}, \delta)$.

The set $\Theta_{\Delta}$ is a cover of $\Delta$. More precisely, we have $\bigcup \Theta_{\Delta} = \Delta$ and $\forall A \in \Theta_{\Delta}, A \neq \emptyset$. However, two distinct elements $A, B \in \Delta$ may have a non-empty intersection. Indeed, for all $A, B \in \Delta$ we have $A \cap B \neq \emptyset \Rightarrow A \subseteq B \lor B \subseteq A$. This last point may forbid $\Theta_{\Delta}$ to be a partition of $\Delta$. Nonetheless, one can define the set $\Delta^*$ from $\Delta$ composed of the proper parts of the nodes of $\Theta_{\Delta}$. Given a node $A \in \Theta_{\Delta}$, the subset $A^* = \rho(A) \subseteq A$ is defined as in Eq. (18). The set $\Theta_{\Delta}^*$ is then defined as

$$ \Theta_{\Delta}^{*} = \{A^{*} | A \in \Theta\} \quad (24) $$

In particular, the application that maps $\Theta_{\Delta}$ onto $\Theta_{\Delta}^*$ is a bijection, and $\Theta_{\Delta}^*$ is a partition of $\Delta$. It follows that $\Theta_{\Delta}$ intrinsically defines an equivalence relation $\sim_{\Delta}$ on $\Delta$.

The component tree $(\Theta_{\Delta}, \frown_{\Delta})$ is the Hasse diagram of the ordered set $(\Theta_{\Delta}, \subseteq)$. Since $\Theta_{\Delta}$ and $\Theta_{\Delta}^*$ are in bijection, one can derive the order $\subseteq^*$ on $\Theta_{\Delta}^*$ by:

$$ (A^* \subseteq^* B^*) \iff (A \subseteq B) \quad (25) $$

<footnote n="2">² The only case which would lead to multivalued component trees being total partition trees is when $\mathcal{F}(\Omega) \subseteq \nabla \leq_{\mathbb{V}} \mathbb{V}$.</footnote>
The Hasse diagram $(\Theta_{\Delta}^{*}, \triangleleft_{\Delta}^{*})$ of $(\Theta_{\Delta}^{*}, \subseteq^{*})$ is then isomorphic to the Hasse diagram $(\Theta_{\Delta}, \triangleleft_{\Delta})$, i.e. the component tree of $(\mathfrak{G}_{\Delta}, \delta)$.

Following the notations given at the beginning of this section, and setting $\Delta = \mathbb{V}$, $\sim_{\Delta} = \sim$, $\mathbb{K} = \Theta_{\Delta}^{*}$ and $\subseteq^{*} = \mathbb{L}_{\mathbb{K}}$, we can define a hierarchical preorder $\mathbb{L}_{\mathbb{V}}$ on $\mathbb{V}$ from a component tree. In particular, it is only required that $\mathbb{V}$ be endowed with the two elements necessary for building this component tree, namely:

- an adjacency relation $\wedge_{\mathbb{V}}$, allowing to map a graph structure on $\mathbb{V}$;

- a function $\delta_{\mathbb{V}} : \mathbb{V} \to \mathbb{N}$, allowing to associate to each element of $\mathbb{V}$ a value within the totally ordered set $(\mathbb{N}, \leq)$.

**Example** Let us consider a colour image $\mathcal{F}: \Omega \to \mathbb{V}$ where the colour values are encoded in the 8-bit per band RGB space $\mathbb{V} = [0, 255]^3$. We model $\mathbb{V}$ as the RGB cube, where each colour $v = (r, g, b) \in [0, 255]^3$ corresponds to a point in the Cartesian space. We endow $\mathbb{V}$ with the standard 6-adjacency $\wedge_{\mathbb{V}}$ defined in digital topology [10], that models the distance 1 between two colours with respect to the $l_1$ norm. We set $\mathfrak{G}_{\Delta} = (\mathbb{V}, \wedge_{\mathbb{V}})$. Let us define $\delta_{\mathbb{V}}$ as the histogram of the image $\mathcal{F}$. In other words, for any colour $v \in \mathbb{V}$, we set $\delta_{\mathbb{V}}(v) = |\{\mathbf{x} \in \Omega \mid \mathcal{F}(\mathbf{x}) = v\}|$. Based on the above discussion, the component tree $\mathfrak{T}_{\Delta} = (\Theta_{\Delta}, \triangleleft_{\Delta})$ built from $(\mathfrak{G}_{\Delta}, \delta_{\mathbb{V}})$ defines the Hasse diagram of a hierarchical preorder $\mathbb{L}_{\mathbb{V}}$ on $\mathbb{V}$. This example is illustrated in a simplified version in Fig. 17. From $\mathcal{F}$ and $\mathbb{L}_{\mathbb{V}}$, it is then possible to build the multivalued component tree of $\mathcal{F}$ induced by its histogram.

## 7.2 Ordering the enriched value set

In this section, we aim to build a hierarchical preorder $\mathbb{L}_{\mathbb{W}}$ on a superset $\mathbb{W}$ of $\mathbb{V}$ so that the elements of $\mathbb{V}$ be the maximal elements of $\mathbb{L}_{\mathbb{W}}$, i.e. $\mathbb{V} = \bigvee^{\mathbb{L}_{\mathbb{W}}} \mathbb{W}$.

The smallest set $\mathbb{W}$ that satisfies this assumption is $\mathbb{W} = \mathbb{V} \cup \{\perp\}$ where $\perp \notin \mathbb{V}$ is a unique element added to $\mathbb{V}$ that acts as minimum for $\mathbb{L}_{\mathbb{W}}$ (such paradigm was investigated, e.g. in [69]). The induced hierarchical preorder (which is indeed an order) is the relation $\mathbb{L}_{\mathbb{W}}$ defined as $\{(\perp, v) \mid v \in \mathbb{V}\}$ with $\perp = \bigwedge^{\mathbb{L}_{\mathbb{W}}} \mathbb{W}$ and $\mathbb{V} = \bigvee^{\mathbb{L}_{\mathbb{W}}} \mathbb{W}$. It is of course possible to build larger supersets $\mathbb{W}$ and to endow them with hierarchical preorders $\mathbb{L}_{\mathbb{W}}$ that also fulfill the above assumption. Such sets $\mathbb{W}$ can be of arbitrary size, and potentially infinite.

In the current context, we first observe that defining a preorder instead of an order is not relevant, by contrast with the previous section.

Let $\mathbb{W}$ be a set and $\mathbb{L}_{\mathbb{W}}$ a hierarchical preorder on $\mathbb{W}$. We assume that $\bigvee^{\mathbb{L}_{\mathbb{W}}} \mathbb{W} = \mathbb{V}$ and $\bigwedge^{\mathbb{L}_{\mathbb{W}}} \mathbb{W} = \perp$, with $\perp \in \mathbb{W} \setminus \mathbb{V}$. For any $w \in \mathbb{W}$, we set $\mathbb{V}_w = \{v \in \mathbb{V} \mid w \leq_w v\}$ (note that $\mathbb{V}_w \neq \emptyset$).

Let $w_1, w_2 \in \mathbb{W}$. Let us suppose that $w_1 \leq_w w_2$. Let $v_2 \in \mathbb{V}_{w_2}$. We have $w_2 \leq_w v_2$ and then $w_1 \leq_w v_2$. If follows that $v_2 \in \mathbb{V}_{w_1}$ and then that $\mathbb{V}_{w_2} \subseteq \mathbb{V}_{w_1}$. Consequently, for any $w_1, w_2 \in \mathbb{W}$, we have:

$$w_1 \leq_w w_2 \implies \mathbb{V}_{w_2} \subseteq \mathbb{V}_{w_1} \qquad (26)$$

$$w_1 \leq_w w_2 \wedge w_2 \leq_w w_1 \implies \mathbb{V}_{w_2} = \mathbb{V}_{w_1} \qquad (27)$$

The image $\mathcal{F}: \Omega \to \mathbb{V}$ takes its values within the set $\mathbb{V}$. However, this set $\mathbb{V}$ is embedded in a superset $\mathbb{W}$, and the image can then be seen as a function $\mathcal{F}: \Omega \to \mathbb{W}$, where $\mathbb{W}$ is endowed with a (pre)order $\mathbb{L}_{\mathbb{W}}$. For any $w \in \mathbb{W}$, we have (see Eq. (9)):

$$\begin{aligned} \Lambda_w(\mathcal{F}) &= \{\mathbf{x} \in \Omega \mid w \leq_w \mathcal{F}(\mathbf{x})\} \\ &= \{\mathbf{x} \in \Omega \mid \mathcal{F}(\mathbf{x}) \in \mathbb{V}_w\} \end{aligned} \qquad (28)$$

Now, let us consider two distinct values $w_1, w_2 \in \mathbb{W}$ such that $w_1 \leq_w w_2$ and $w_2 \leq_w w_1$. From Eq. (27), we have $\mathbb{V}_{w_1} = \mathbb{V}_{w_2}$, and it follows from Eq. (28) that $\Lambda_{w_1}(\mathcal{F}) = \Lambda_{w_2}(\mathcal{F})$ and thus that $\mathcal{C}[\Lambda_{w_1}(\mathcal{F})] = \mathcal{C}[\Lambda_{w_2}(\mathcal{F})]$. In other words, relaxing the antisymmetry property to define a preorder instead of an order is useless, since it leads to define many times the same nodes, which are then modeled once, into the set $\Theta$ of the multivalued connected component (see Eq. (14)).

Based on this discussion, we assume that $\mathbb{L}_{\mathbb{W}}$ is a hierarchical order. Although $\mathbb{W}$ may be of arbitrary size, and potentially infinite, we will now observe that it is indeed sufficient to define some finite sets $\mathbb{W}$. We will also conclude that $\mathbb{W}$ may not be much larger than twice the size of $\mathbb{V}$. Let us set $\mathbb{V}_{\mathbb{W}} = \{\mathbb{V}_w \mid w \in \mathbb{W}\} \subseteq 2^{\mathbb{V}}$.

We define the equivalence relation $\equiv_{\mathbb{W}}$ on $\mathbb{W}$ by:

$$(w_1 \equiv_{\mathbb{W}} w_2) \iff (\mathbb{V}_{w_1} = \mathbb{V}_{w_2}) \qquad (29)$$

Let $w \in \mathbb{W}$. Let $v \in \mathbb{V}_w$. Since $(\mathbb{W}, \mathbb{L}_{\mathbb{W}})$ is a lower-hierarchical order, the set $\mathbb{W}_v = \{w \in \mathbb{W} \mid w \leq_w v\}$ is totally ordered by $\mathbb{L}_{\mathbb{W}}$. We have $[w]_{\mathbb{L}_{\mathbb{W}}} \subseteq \mathbb{W}_v$. It follows that $[w]_{\mathbb{L}_{\mathbb{W}}} = \text{totally ordered by } \mathbb{L}_{\mathbb{W}}$. We set $\hat{w} = \bigvee^{\mathbb{L}_{\mathbb{W}}}[w]_{\mathbb{L}_{\mathbb{W}}}$. We note $\hat{\mathbb{W}} = \{\hat{w} \mid w \in \mathbb{W}\}$.

Let $w_1, w_2 \in \mathbb{W}$. Let us suppose that $w_1 \leq_w w_2$. Since $w_2 \leq_w \hat{w}_2$, we have $w_1 \leq_w \hat{w}_2$. Let $v_2 \in \mathbb{V}_{w_2}$. We have $w_2 \leq_w v_2$ and then $w_1 \leq_w v_2$. Then, we have $v_2 \in \mathbb{V}_{w_1} = \mathbb{V}_{\hat{w}_1}$, and it follows that $\hat{w}_1 \leq_w v_2$. Since $\mathbb{V}_{w_2} = \mathbb{V}_{\hat{w}_2}$, we also have $\hat{w}_2 \leq_w v_2$. Since $(\mathbb{W}, \mathbb{L}_{\mathbb{W}})$ is a upper-hierarchical order, the set $\mathbb{W}_{v_2} = \{w \in \mathbb{W} \mid w \leq_w v_2\}$ is totally ordered by $\mathbb{L}_{\mathbb{W}}$. It follows that $\{\hat{w}_1, \hat{w}_2\}$ is totally ordered by $\mathbb{L}_{\mathbb{W}}$. Thus, we have $\hat{w}_1 \leq \hat{w}_2$ or $\hat{w}_2 \leq \hat{w}_1$. Let us suppose that $\hat{w}_2 \leq \hat{w}_1$. From Eq. (26),
<figure><img src="image_21.png" /><figcaption>**Fig. 18** Illustration of the construction of an order on a value set (see Sect. 7.2). (a) Top: an image $\mathcal{F}: \Omega \to \mathbb{V}$. The set $\Omega$ is equal to $[0, 4]^2$ and is endowed with an adjacency relation $\wedge$ corresponding to the 4-adjacency. Bottom: the set $\mathbb{V}$ composed of 9 values, without initial ordering. (b) Top: the co-occurrence matrix of the image $\mathcal{F}$, used as a priority function $\delta_{\wedge}: \wedge \to \mathbb{N}$. Bottom: the set $\mathbb{V}$ is endowed with an adjacency $\wedge_{\mathbb{V}}$. (c) The binary partition tree of $(\mathbb{V}, \wedge_{\mathbb{V}})$ induced by $\delta_{\wedge_{\mathbb{V}}}$. This binary partition tree defines a hierarchical order $\leq_W$ on an enriched set of values $\mathbb{W}$ where the values of $\mathbb{V}$ are the maximal elements.</figcaption></figure>

we have $V_{\hat{w}_1} \subseteq V_{\hat{w}_2}$. But since we have $w_1 \leq_W w_2$, from Eq. (26), we also have $V_{w_2} \subseteq V_{w_1}$. By definition, we have $V_{\hat{w}_1} = V_{w_1}$ and $V_{\hat{w}_2} = V_{w_2}$. It follows that $V_{w_1} = V_{w_2}$ and thus $\hat{w}_1 = \hat{w}_2$. Consequently, for any $w_1, w_2 \in \mathbb{W}$, we have:

$$ (w_1 \leq_W w_2) \implies (\hat{w}_1 \leq_W \hat{w}_2) \qquad (30) $$

In other words, there is a homomorphism from $(\mathbb{W}, \leq_W)$ to $(\hat{\mathbb{W}}, \leq_{\hat{W}})$ where $\leq_{\hat{W}}$ is the restriction of $\leq_W$ to $\hat{\mathbb{W}}$.

By construction, the set $\hat{\mathbb{W}}$ is in bijection with $V_{\mathbb{W}}$. Since $\mathbb{V} = \bigvee^{\leq_W} \mathbb{W}$, we also have $\mathbb{V} \subseteq \hat{\mathbb{W}}$. Following Eq. (14), we set $\Theta_{\mathbb{W}} = \bigcup_{w \in \mathbb{W}} C[\Lambda_w(\mathcal{F})]$ and $\Theta_{\hat{\mathbb{W}}} = \bigcup_{w \in \hat{\mathbb{W}}} C[\Lambda_w(\mathcal{F})]$. Since $\hat{\mathbb{W}} \subseteq \mathbb{W}$, we have $\Theta_{\hat{\mathbb{W}}} \subseteq \Theta_{\mathbb{W}}$. Let $X \in \Theta_{\mathbb{W}}$. There exists $w \in \mathbb{W}$ such that $X \in C[\Lambda_w(\mathcal{F})]$. Since $V_w = V_{\hat{w}}$, it follows from Eq. (28) that $X \in C[\Lambda_{\hat{w}}(\mathcal{F})]$. Then, we have $X \in \Theta_{\hat{\mathbb{W}}}$. It follows that we have $\Theta_{\mathbb{W}} \subseteq \Theta_{\hat{\mathbb{W}}}$ and thus $\Theta_{\mathbb{W}} = \Theta_{\hat{\mathbb{W}}}$. As a corollary, we have $(\Theta_{\mathbb{W}}, \subseteq) = (\Theta_{\hat{\mathbb{W}}}, \subseteq)$. It follows that the multivalued component trees $\mathfrak{F}_{\mathbb{W}} = (\Theta_{\mathbb{W}}, \prec_{\mathbb{W}})$ and $\mathfrak{F}_{\hat{\mathbb{W}}} = (\Theta_{\hat{\mathbb{W}}}, \prec_{\hat{\mathbb{W}}})$ are equal.

A direct conclusion of the above discussion is that instead of using a set $\mathbb{W}$, arbitrarily large and potentially infinite, the same multivalued component tree is obtained by considering the set $\hat{\mathbb{W}}$, which is finite. Indeed, from the definition of $\equiv$, $\hat{\mathbb{W}}$ is in bijection with $V_{\mathbb{W}} \subseteq 2^{\mathbb{V}}$.

The bijection between $\hat{\mathbb{W}}$ and $V_{\mathbb{W}}$ induces an isomorphism between $(\hat{\mathbb{W}}, \leq_{\hat{W}})$ and $(V_{\mathbb{W}}, \supseteq)$. Let $\hat{w}_1, \hat{w}_2 \in \hat{\mathbb{W}}$. Let us suppose that $\hat{w}_1 \leq_W \hat{w}_2$. From Eq. (26), we have $V_{\hat{w}_1} \supseteq V_{\hat{w}_2}$. Now, let $V_{\hat{w}_1}, V_{\hat{w}_2} \in V_{\mathbb{W}}$. Let us suppose that $V_{\hat{w}_1} \supseteq V_{\hat{w}_2}$. Two cases can occur. First, let us suppose that $V_{\hat{w}_1} = V_{\hat{w}_2}$. In that case, from the definition of $\equiv$, we have $\hat{w}_1 = \hat{w}_2$ and it follows that $\hat{w}_1 \leq_{\hat{W}} \hat{w}_2$.

Second, let us suppose that $V_{\hat{w}_1} \supseteq V_{\hat{w}_2}$. Let $v_2 \in V_{\hat{w}_2}$. We then have $v_2 \in V_{\hat{w}_1}$. Since $(\hat{\mathbb{W}}, \leq_{\hat{W}})$ is a lower-hierarchical order, the set $\hat{\mathbb{W}}_{v_2} = \{w \in \hat{\mathbb{W}} | w \leq_{\hat{W}} v_2\}$ is totally ordered by $\leq_{\hat{W}}$. We have $\hat{w}_1, \hat{w}_2 \in \hat{\mathbb{W}}_{v_2}$, and it follows that $\{\hat{w}_1, \hat{w}_2\}$ is totally ordered by $\leq_{\hat{W}}$. We then have $\hat{w}_1 \leq_{\hat{W}} \hat{w}_2$ or $\hat{w}_2 \leq_{\hat{W}} \hat{w}_1$. Let us suppose that $\hat{w}_2 \leq_{\hat{W}} \hat{w}_1$. From Eq. (26), we have $\hat{V}_{w_2} \subseteq \hat{V}_{w_1}$, in contradiction with the hypothesis $V_{\hat{w}_1} \supseteq V_{\hat{w}_2}$. It follows that $\hat{w}_2 \leq_{\hat{W}} \hat{w}_1$. The isomorphism between $(\hat{\mathbb{W}}, \leq_{\hat{W}})$ and $(V_{\mathbb{W}}, \supseteq)$ follows.

Let us now focus on the nature of the Hasse diagram of $(V_{\mathbb{W}}, \subseteq)$. The inclusion $\subseteq$ on $V_{\mathbb{W}}$ is a upper-hierarchical order. The Hasse diagram $(V_{\mathbb{W}}, \prec)$ is, in particular, a partition tree. The fact that $\mathbb{V} = \bigvee^{\leq_W} \mathbb{W}$ implies that $\{\{v\} | v \in \mathbb{V}\} = \Delta^\subseteq V_{\mathbb{W}}$. It follows that $(V_{\mathbb{W}}, \prec)$ is a total partition tree. A corollary of this property is that $|V_{\mathbb{W}}| < 2|\mathbb{V}|$.

To conclude on this analysis, it appears that for building a hierarchical order $\leq_W$ on a superset $\mathbb{W}$ of $\mathbb{V}$ so that the elements of $\mathbb{V}$ be the maximal elements of $\leq_W$, i.e. $\mathbb{V} = \bigvee^{\leq_W} \mathbb{W}$, the most simple, yet general solution is to build a total partition tree from the initial, finest partition of $\mathbb{V}$, namely $\{\{v\} | v \in \mathbb{V}\}$. This can be done by considering any dendrogram construction process. A possible way may be, in particular, to build a (binary) partition tree, following the standard construction algorithms proposed in the literature [27, 41]. To this end, it is only required that $\mathbb{V}$ be endowed with:

- an adjacency relation $\wedge_{\mathbb{V}}$, allowing to map a graph structure on $\mathbb{V}$;

- a priority function $\delta_{\wedge_{\mathbb{V}}}: \wedge_{\mathbb{V}} \to \mathbb{N}$, allowing to determine the couples of nodes to be merged in priority.
*Example* Let us consider an image $\mathcal{F}: \Omega \to \mathbb{V}$. The support $\Omega$ is endowed with an adjacency relation $\wedge$. The value space $\mathbb{V}$ is endowed with the adjacency relation $\wedge_{\mathbb{V}}$ so that $\mathfrak{G}_{\Delta} = (\mathbb{V}, \wedge_{\mathbb{V}})$ is an irreflexive complete graph (i.e. $\forall u, v \in \mathbb{V}, u \neq v \Leftrightarrow u \wedge_{\mathbb{V}} v$). We define the co-occurrence matrix [70] of the image $\mathcal{F}$. This matrix $\mathcal{M} = (m_{u,v})_{u,v \in \mathbb{V}}$ is of dimension $|\mathbb{V}| \times |\mathbb{V}|$. For each couple $(u, v) \in \mathbb{V} \times \mathbb{V}$, it is defined by $m_{u,v} = |\{(\mathbf{x}, \mathbf{y}) \in \Omega \times \Omega \mid \mathbf{x} \wedge \mathbf{y} \wedge \mathcal{F}(\mathbf{x}) = u \wedge \mathcal{F}(\mathbf{y}) = v\}|$. We define the priority function $\delta_{\wedge_{\mathbb{V}}} : \wedge_{\mathbb{V}} \to \mathbb{N}$ so that for any $(u, v) \in \wedge_{\mathbb{V}}$, i.e. for any $u \wedge_{\mathbb{V}} v$, we have $\delta_{\wedge_{\mathbb{V}}}((u, v)) = m_{u,v}$. Based on the above discussion, the partition tree $\mathfrak{T}_{\Delta} = (\Theta_{\Delta}, \langle \Delta \rangle)$ built [27] from $(\mathfrak{G}_{\Delta}, \delta_{\wedge_{\mathbb{V}}})$ defines the Hasse diagram of a hierarchical order $\leq_{\mathbb{V}}$ on $\mathbb{V}$. This example is illustrated in a simplified version in Fig. 18. From $\mathcal{F}$ and $\leq_{\mathbb{V}}$, it is then possible to build the multivalued component tree of $\mathcal{F}$ induced by its co-occurrence matrix.

## 8 Conclusion

In this article, we have deepened our study of the multivalued component tree [38], a morphological tree that can be seen as an extension of the well-known component tree [28]. From a theoretical point of view, we emphasized the contribution of the multivalued component tree to fill the gap between the two subfamilies of total partition trees and partial partition trees, that compose the family of the morphological trees. From a practical point of view, we showed that we could leverage the notions of component trees and (binary) partition trees to build relevant hierarchical orders leading to the further definition of multivalued component trees. We also proposed a new algorithmic scheme to build the multivalued component tree, once again by leveraging the existing algorithmics on the usual component tree.

In a context where image processing and analysis is principally dominated by deep learning, morphological hierarchies remain a topic of paramount importance. Indeed, whereas automatic segmentation is one of the principal purposes of deep learning applied on images, interactive segmentation remains a mandatory task for efficiently (i.e. accurately and rapidly) build annotations on large image datasets [71]. Many efforts were recently geared towards the development of efficient segmentation from morphological hierarchies, with a specific focus on evaluation frameworks and interactive / marker-based approaches [72–77]. In addition, before supporting image processing / analysis methods, morphological hierarchies are first image models. As such they allow to describe imaging data, especially from a

structural / topological point of view. Indeed, morphological trees such as the component tree are directly related [56,78] to the notion of homology persistence [79], which is a crucial concept in topological data analysis. More generally, other kinds of trees, such as the topological tree of shapes [57] constitute topological descriptors. A recent trend of deep learning goes towards the embedding of topological features, in particular by defining topological loss functions [80,81]. Recent works investigated the ability of the component tree to be involved as a topological loss [82]. Other kinds of trees, including the multivalued component tree, could be used for such purpose. From an algorithmic point of view, intensive investigations have been conducted to accelerate the computation and handling of morphological hierarchies. The first attempts aimed to leverage distributed architecture [83–85]. More recently, some approaches were proposed to take advantage of out of core paradigms [86, 87] and GPU facilities [88]. The development of such material-accelerated strategies, coupled with efficient algorithms may allow to involve the morphological hierarchies in general, and the multivalued component tree in particular, in the next generation of image analysis and computer vision paradigms.

## Acknowledgments

This work was supported by the French Agence Nationale de la Recherche (Grants ANR-20-THIA-0006, ANR-20-CE45-0011, ANR-22-CE45-0034 and ANR-23-CE45-0015).

## A Proof of correctness the multivalued component tree construction algorithm (Algorithm 2 and Function Flood)

In this appendix, we provide a proof of correctness of the multivalued component tree construction process given in Algorithm 2 and Function Flood. For the sake of readability, we provide some formalized, yet equivalent, versions of Algorithm 2 and Function Flood in Algorithm 3 and the alternative Function Flood, respectively. The notations used in the proofs will be those provided there.

Before starting that proof, we recall the role of the different data involved in the construction process.

- For each $v \in \mathbb{V}$, $\Theta_v$ models the nodes of the multivalued component tree at value $v$. In practice, $\Theta_v$ is in bijection with the set of the connected components of $\mathcal{F}$ at value $v$, and each element of $\Theta_v$ contains the proper part $\rho(X)$ of one of these connected components $X$.

- For each $v \in \mathbb{V}$, $Q_v$ contains some points of $\Omega$ which have not yet been included in a node of $\Theta$.

- For each point $\mathbf{x} \in \Omega$ of value $\mathcal{F}(\mathbf{x}) = v$, $\lambda_x$ indicates to which connected component of $\Theta_v$ it belongs. Initially, the value 0 indicates that this assignment has not been made.
<caption>**Algorithm 3:** Building the multivalued component tree</caption>

**Input:** Graph $(\Omega, \frown)$
**Input:** Lower-hierarchically ordered set $(\mathbb{V}, \leq)$
**Input:** Function $\mathcal{F}: \Omega \to \mathbb{V}$
**Output:** Multivalued component tree $\mathcal{T} = (\Theta, \triangleleft)$
with $\Theta = \bigcup_{v \in \mathbb{V}} \Theta_v$ and $\Theta_v = \{X_v^i\}_{i=1}^{t_v}$

1. $\{\Theta_v\}_{v \in \mathbb{V}} := \{\emptyset\}_{v \in \mathbb{V}}$
2. $\{Q_v\}_{v \in \mathbb{V}} := \{\emptyset\}_{v \in \mathbb{V}}$
3. $\{\lambda_x\}_{x \in \Omega} := \{0\}_{x \in \Omega}$
4. $\{s_v\}_{v \in \mathbb{V}} := \{1\}_{v \in \mathbb{V}}$
5. $\{t_v\}_{v \in \mathbb{V}} := \{0\}_{v \in \mathbb{V}}$
6. $\{\ell_v\}_{v \in \mathbb{V}} := \{\perp\}_{v \in \mathbb{V}}$
7. $v_{\min} := \bigwedge^{\leq} \mathbb{V}$
8. Choose $x_{\min} \in \Omega$ such that $\mathcal{F}(x_{\min}) = v_{\min}$
9. $Q_{v_{\min}} \leftarrow x_{\min}$
10. $\ell_{v_{\min}} := \top$
11. Flood($v_{\min}$)

- For each $v \in \mathbb{V}$, $s_v$ is the label of the potential next connected component of $\Theta_v$ to be set. Its definition may be ongoing, or not yet started.

- For each $v \in \mathbb{V}$, $t_v$ is the number of connected components of $\Theta_v$.

- For each $v \in \mathbb{V}$, $\ell_v$ indicates if a connected component at value $v$ is currently in construction or to be constructed.

It is important to notice that the data $\{\Theta_v\}_{v \in \mathbb{V}}$, $\{Q_v\}_{v \in \mathbb{V}}$, $\{\lambda_x\}_{x \in \Omega}$, $\{s_v\}_{v \in \mathbb{V}}$, $\{t_v\}_{v \in \mathbb{V}}$, $\{\ell_v\}_{v \in \mathbb{V}}$, $v_{\min}$, are handled as global variables. In practice, Function Flood is then called for an input value $v$, and with a given configuration of these global data.

Let us first state some invariant properties.

$$ (I_0) \quad \forall v, \ell_v \iff (Q_v \neq \emptyset) $$

**Proof of (I₀)** – In Algorithm 2, Lines 9–10, in Function Flood, Lines 8–9 and 22–23, $\ell_v$ is set to $\top$ when a point is added to $Q_v$. In Function Flood, Line 33, $\ell_u$ is set to $\perp$ when $Q_u$ becomes empty (end of the while loop of Lines 1–25). ■

When Function Flood($u$) starts, the input configuration of the global variables satisfies:

$$ (S_1) \quad Q_u \neq \emptyset $$

$$ (S_2) \quad \forall v > u, Q_v = \emptyset $$

$$ (S_3) \quad \exists X \in C[\Lambda_u(\mathcal{F})], Q_u \subseteq X $$

$$ (S_4) \quad \forall x \in \rho(X), \lambda_x = 0 $$

$$ (S_5) \quad \forall v \ge u, s_v = t_v + 1 $$

$$ (S_6) \quad \forall v > u, \ell_v = \perp $$

where, for all $v \in \mathbb{V}$, $s_v$, $t_v$ are the values of $s_v$, $t_v$, respectively, when Function Flood($u$) starts.

When Function Flood($u$) ends, the output configuration of the global variables satisfies:

$$ (E_1) \quad Q_u = \emptyset $$

$$ (E_2) \quad \forall v > u, Q_v = \emptyset $$

$$ (E_3) \quad \forall x \in X, \forall y \in \Omega \setminus X, (y \frown x) \implies (y \in Q \trianglelefteq \{\mathcal{F}(x), \mathcal{F}(y)\}) $$

$$ (E_4) \quad \forall x \in X, \lambda_x \neq 0 $$

$$ (E_5) \quad \forall v \ge u, s_v^+ = t_v^+ + 1 $$

$$ (E_6) \quad \forall v > u, \ell_v = \perp $$

$$ (E_7) \quad s_u^+ = s_u + 1 $$

$$ (E_8) \quad t_u^+ = t_u + 1 $$

For all $v \in \mathbb{V}$, we note $\Theta_v^* = \{X_v^i\}_{i=t_v^-+1}^{t_v^+}$. We also note $\Theta^* = \bigcup_{v \ge u} \Theta_v^*$ and $\triangleleft^*$ the relation on $\Theta^*$ such that $(\Theta^*, \triangleleft^*)$ is the Hasse diagram of $(\Theta^*, \subseteq)$.

When Function Flood($u$) ends:

## Function Flood

**Input:** $u \in \mathbb{V}$: current level

**Output:** $w \in \mathbb{V}$: value of the parent node of the root of the built (partial) multivalued component tree at value $u$ (or $\varepsilon$ if the node has no parent)

1. while $Q_u \neq \emptyset$ do

2. $Q_u \to x$

3. if $s_u > t_u$ then

4. $t_u := s_u$
5. $\Theta_u \leftarrow X_u^{s_u} := \emptyset$

6. if $\mathcal{F}(x) \neq u$ then

7. $w := \mathcal{F}(x)$

8. $Q_w \leftarrow x$

9. $\ell_w := \top$

10. while $u < w$ do
11. $w := \text{Flood}(w)$

12. else

13. $\lambda_x := s_u$
14. $X_u^{s_u} \leftarrow x$

15. foreach $y \frown x$ do
16. $w \leftarrow \mathcal{F}(y)$
17. if $y \notin \bigcup_{v \in \mathbb{V}} Q_v$ and $\lambda_y = 0$ then
18. if $u \le w$ then
19. $\hat{w} := w$
20. else
21. $\hat{w} := \bigwedge^{\le} \{u, w\}$
22. $Q_{\hat{w}} \leftarrow y$
23. $\ell_{\hat{w}} := \top$
24. while $u < \hat{w}$ do
25. $\hat{w} := \text{Flood}(\hat{w})$

26. if $u = v_{\min}$ then

27. $w := \varepsilon$

28. else

29. $w := \sigma_{\triangleleft}(u)$

30. while $\neg \ell_w$ do

31. $\lfloor w := \sigma_{\triangleleft}(w) \rfloor$

32. $\triangleleft \leftarrow (X_u^{s_u}, X_u^{s_w})$

33. $\ell_u := \perp$

34. $s_u := s_u + 1$

35. return $w$

(P₁) it has built $(\Theta^*, \triangleleft^*)$ which is the multivalued component tree of the subgraph $(X, \frown)$ of $(\Omega, \frown)$ induced by $X$, and the function $\mathcal{F}$, with respect to the lower-hierarchically ordered set $\leq$;

(P₂) if $u \neq v_{\min}$ then it has built an edge between $X = X_u^{t_u}$ and the node $X_w^{t_w}$ such that $u > w$ and for all $u > v > w$, we have $X \in C[\Lambda_v(\mathcal{F})]$; and

(P₃) if $u \neq v_{\min}$ then it returns $w$.

**Proof of (S₁)** – In Algorithm 2, when Function Flood($v_{\min}$) is called at Line 11, we have $Q_{v_{\min}} \neq \emptyset$ from Line 8. In Function Flood, when Function Flood($w$) is called at Line 11 for the first iteration of Line 10, we have $Q_w \neq \emptyset$ from Line 8. In Function Flood, when Function Flood($w$) is called at Line 11 for the next iterations of Line 10, the value $w$ is the output of the previous call of Function Flood and this value $w$ satisfies $\ell_w$. It follows from (I₀) that $Q_w \neq \emptyset$. The same reasoning
holds for Lines 22,24–25 ■

**Proof of (E₁)** – In Function Flood(u), the while loop of Lines 1–25 ends when $Q_u = \emptyset$. No element is added to $Q_u$ in Lines 26–35. ■

**Proof of (S₂) and (E₂)** – In Algorithm 2, when Function Flood($v_{min}$) is called at Line 11, we have $Q_v = \emptyset$ for any $v > v_{min}$ from Line 2. In Function Flood(u), when a point x such that $F(x) = v > u$ is added to $Q_v$ (Lines 8 and 22), Function Flood(v) is then called (Lines 11 and 25). The result follows by induction from (E₁). ■

**Proof of (S₃) and (E₃)** – In Algorithm 2, when Function Flood($v_{min}$) is called at Line 11, we have $Q_{v_{min}} = \{x_{min}\}$ from Line 8. In Function Flood(u), when Function Flood(w) is called (Lines 11 or 25), from (S₂), the adjacency property of Line 15, and the fact that $w > u$, it follows that there exists exactly one connected component X of $\Lambda_w(F)$ such $Q_w \subseteq X$. Still in Function Flood(u), from Lines 6/12 and 15, it follows that all the points of the connected component X of $\Lambda_u(F)$, i.e. all the points x such that $F(x) \ge u$ are processed, either by Function Flood(u) itself or by an occurrence of Function Flood(w) (Lines 10–11 or 24–25). From Lines 15 and 20–21, it follows that all the points y adjacent to a point x ∈ X such that $F(y) \ge u$ are stored in $Q_{\Lambda \le \{F(x), F(y)\}}$. The result follows by induction. ■

**Proof of (S₄) and (E₄)** – Following the same reasoning as for the proof of (S₃) and (E₃), we prove by induction that for the considered connected component X of $\Lambda_u(F)$ such that $Q_u \subseteq X$, any x ∈ $\rho(X)$ satisfies $\lambda_x = 0$ when Function Flood(u) starts, and x ∈ X satisfies $\lambda_x \ne 0$ when it ends. ■

**Proof of (S₅) and (E₅)** – In Algorithm 2, when Function Flood($v_{min}$) is called at Line 11, we have $s_v = 1$ and $t_v = 0$ for all v (from Lines 4–5). In Function Flood(u), when Function Flood(w) is called at Lines 11 and 25, the value w is set to v. At the end of Function Flood(u), from Lines 3–4 and 34, we have $s_u^+ = t_u^+ + 1$. From the same lines, it follows that $s_u$ and $t_u$ are only modified by Function Flood(u). The result follows by induction. ■

**Proof of (S₆) and (E₆)** – In Algorithm 2, when Function Flood($v_{min}$) is called at Line 11, we have $\ell_v = \perp$ for any $v > v_{min}$ from Line 6. At the end of Function Flood(u), $\ell_v$ is set to $\perp$ from Line 26. In Function Flood(u), when Function Flood(w) is called at Lines 11 and 25, we have $w > u$ from Lines 10 and 24, respectively, and the only value $v > u$ for which $\ell_v$ is set to $\top$ is w. The result follows by induction. ■

**Proof of (E₇) and (E₈)** – Property (E₇) results from Line 34 of Function Flood(u) and the fact that $s_u$ is modified by Function Flood only for the parameter u. Property (E₈) derives from Properties (S₅) and (E₇). ■

**Proof of (P₂) and (P₃)** – Let us assume that Function Flood(u) ($u > v_{min}$) ends. Function Flood(u) had been called by another occurrence of Function Flood at a value $u' < u$, at Lines 11 or 25. From (E₃), for all the points y ∈ $\Omega \setminus X$ adjacent to X (E₃) we have $y \in Q_{\Lambda \le \{u, F(y)\}}$ and from $I_0$, $\ell_{\Lambda \le \{u, F(y)\}} = \top$. Let us consider the values $v = F(y)$ that satisfy this property and that are comparable with u. Let us add to this set the value $u'$, which is also comparable with u (and with $\ell_{u'} = \top$). Since $(\mathbb{V}, \le)$ is a lower-hierarchical order, this set of values

is totally ordered. In particular, it has a maximum w. From (S₆) and (E₆), it follows that when Function Flood(u') calls Function Flood(u), we have $\ell_v = \perp$ for all $v > u$. In particular, for any v such that $u < v < w$, we have $X \in C[\Lambda_v(F)]$. The results follows from Lines 26, 28–32 and 35. ■

**Proof of (P₁)** – Let us first suppose that when Function Flood(u) is called, the set $X \in C[\Lambda_u(F)]$ such that $Q_u \subseteq X$ (see (S₃)) is a maximal flat zone of F. In that case, the parts of Function Flood(u) corresponding to Lines 6–11 and 24–25 are not run. In addition, from Line 13, for any x ∈ X, we have $\lambda_x = s_u^- = t_u^+$. It follows that Function Flood(u) has built a set $\Theta_u^* = \{X_u^i\}_{i=t_v^+}^{t_v^+}$ composed of the only node $X_u^{t_u^+} = X$, while the other sets $\Theta_v^*$ for $v > u$ are empty. We then have $\Theta^* = \bigcup_{v \ge u} \Theta_v^* = \{X\}$ and $(\Theta^*, \subset) = (\Theta^*, 0)$ is the Hasse diagram of $(\Theta^*, \subseteq)$. Property (P₁) then holds in that case. Let us now suppose that when Function Flood(u) is called, (P₁) holds for all the occurrences of Function Flood(w) called at Lines 11 and 25. We assume that (P₂) and (P₃) also hold. The result follows by induction. ■

By considering (P₁) for $v = v_{min}$, we have the following result.

**Theorem 1** *Algorithm 2 and Function Flood build $(\Theta, \subset)$ which is the multivalued component tree of the graph $(\Omega, \wedge)$ and the function F, with respect to the lower-hierarchically ordered set $\le$.*

## References

1. N. Alexandridis and A. Klinger, “Picture decomposition, tree data-structures, and identifying directional symmetries as node combinations,” *Computer Graphics and Image Processing*, vol. 8, pp. 43–77, 1978.

2. T. Ichikawa, “A pyramidal representation of images and its feature extraction facility,” *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 3, pp. 257–264, 1981.

3. S. Tanimoto and T. Pavlidis, “A hierarchical data structure for picture processing,” *Computer Graphics and Image Processing*, vol. 4, pp. 104–119, 1975.

4. G. M. Hunter and K. Steiglitz, “Operations on images using quad trees,” *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 1, pp. 145–153, 1979.

5. H. J. Antonisse, “Image segmentation in pyramids,” *Computer Graphics and Image Processing*, vol. 19, pp. 367–383, 1982.

6. A. Montanvert, P. Meer, and A. Rosenfeld, “Hierarchical image analysis using irregular tessellations,” *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 13, pp. 307–316, 1991.

7. J. Serra, *Image Analysis and Mathematical Morphology*. Academic Press, 1982, vol. 1.

8. ——, *Image Analysis and Mathematical Morphology*. Academic Press, 1988, vol. 2.

9. L. Najman and H. Talbot, Eds., *Mathematical Morphology: From Theory to Applications*. ISTE/J. Wiley & Sons, 2010.

10. A. Rosenfeld, “Digital topology,” *The American Mathematical Monthly*, vol. 86, pp. 621–630, 1979.

11. V. A. Kovalevsky, “Finite topology as applied to image analysis,” *Computer Vision, Graphics, and Image Processing*, vol. 46, pp. 141–161, 1989.
12. L. Mazo, N. Passat, M. Couprie, and C. Ronse, "Paths, homotopy and reduction in digital images," *Acta Applicandae Mathematicae*, vol. 113, pp. 167–193, 2011.

13. —, "Digital imaging: A unified topological framework," *Journal of Mathematical Imaging and Vision*, vol. 44, pp. 19–37, 2012.

14. C. Ronse, "Set-theoretical algebraic approaches to connectivity in continuous or digital spaces," *Journal of Mathematical Imaging and Vision*, vol. 8, pp. 41–58, 1998.

15. J. Serra, "Connectivity on complete lattices," *Journal of Mathematical Imaging and Vision*, vol. 9, pp. 231–251, 1998.

16. U. M. Braga-Neto and J. K. Goutsias, "Connectivity on complete lattices: New results," *Computer Vision and Image Understanding*, vol. 85, pp. 22–53, 2002.

17. —, "A theoretical tour of connectivity in image processing and analysis," *Journal of Mathematical Imaging and Vision*, vol. 19, pp. 5–31, 2003.

18. B. Perret, "Inf-structuring functions: A unifying theory of connections and connected operators," *Journal of Mathematical Imaging and Vision*, vol. 51, pp. 171–194, 2015.

19. C. Ronse, "Partial partitions, partial connections and connective segmentation," *Journal of Mathematical Imaging and Vision*, vol. 32, pp. 97–125, 2008.

20. —, "Ordering partial partitions for image segmentation and filtering: Merging, creating and inflating blocks," *Journal of Mathematical Imaging and Vision*, vol. 49, pp. 202–233, 2014.

21. —, "Orders on partial partitions based on block apportioning," *Acta Applicandae Mathematicae*, vol. 141, pp. 69–105, 2016.

22. —, "Orders for simplifying partial partitions," *Journal of Mathematical Imaging and Vision*, vol. 58, pp. 382–410, 2017.

23. J. Cousty, L. Najman, and B. Perret, "Constructive links between some morphological hierarchies on edge-weighted graphs," in *International Symposium on Mathematical Morphology (ISMM), Proceedings*, ser. Lecture Notes in Computer Science, vol. 7883. Springer, 2013, pp. 86–97.

24. L. Najman, J. Cousty, and B. Perret, "Playing with Kruskal: Algorithms for morphological trees in edge-weighted graphs," in *International Symposium on Mathematical Morphology (ISMM), Proceedings*, ser. Lecture Notes in Computer Science, vol. 7883. Springer, 2013, pp. 135–146.

25. L. Najman and J. Cousty, "A graph-based mathematical morphology reader," *Pattern Recognition Letters*, vol. 47, pp. 3–17, 2014.

26. B. Perret, G. Chierchia, J. Cousty, S. J. Ferzoli Guimarães, Y. Kenmochi, and L. Najman, "Hegra: Hierarchical graph analysis," *SoftwareX*, vol. 10, p. 100335, 2019.

27. P. Salembier and L. Garrido, "Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval," *IEEE Transactions on Image Processing*, vol. 9, pp. 561–576, 2000.

28. P. Salembier, A. Oliveras, and L. Garrido, "Anti-extensive connected operators for image and sequence processing," *IEEE Transactions on Image Processing*, vol. 7, pp. 555–570, 1998.

29. P. Salembier and J. Serra, "Flat zones filtering, connected operators, and filters by reconstruction," *IEEE Transactions on Image Processing*, vol. 4, pp. 1153–1160, 1995.

30. H. J. A. M. Heijmans, "Connected morphological operators for binary images," *Computer Vision and Image Understanding*, vol. 73, pp. 99–120, 1999.

31. P. Salembier and M. H. F. Wilkinson, "Connected operators," *IEEE Signal Processing Magazine*, vol. 26, pp. 136–157, 2009.

32. T. Géraud, E. Carlinet, S. Crozet, and L. Najman, "A quasi-linear algorithm to compute the tree of shapes of nD images," in *International Symposium on Mathematical Morphology (ISMM), Proceedings*, ser. Lecture Notes in Computer Science, vol. 7883. Springer, 2013, pp. 98–110.

33. E. Carlinet and T. Géraud, "A comparative review of component tree computation algorithms," *IEEE Transactions on Image Processing*, vol. 23, pp. 3885–3895, 2014.

34. E. J. Breen and R. Jones, "Attribute openings, thinnings, and granulometries," *Computer Vision and Image Understanding*, vol. 64, pp. 377–389, 1996.

35. R. Jones, "Connected filtering and segmentation using component trees," *Computer Vision and Image Understanding*, vol. 75, pp. 215–228, 1999.

36. L. Guigues, J.-P. Cocquerez, and H. Le Men, "Scale-sets image analysis," *International Journal of Computer Vision*, vol. 68, pp. 289–317, 2006.

37. B. R. Kiran and J. Serra, "Global-local optimizations by hierarchical cuts and climbing energies," *Pattern Recognition*, vol. 47, pp. 12–24, 2014.

38. C. Kurtz, B. Naegel, and N. Passat, "Connected filtering based on multivalued component-trees," *IEEE Transactions on Image Processing*, vol. 23, pp. 5152–5164, 2014.

39. N. Passat, R. Perrin, J. F. Randrianasoa, C. Kurtz, and B. Naegel, "New algorithms for multivalued component-trees," in *International Conference on Pattern Recognition (ICPR), Proceedings*, 2024.

40. P. Bosilj, E. Kijak, and S. Lefèvre, "Partition and inclusion hierarchies of images: A comprehensive survey," *Journal of Imaging*, vol. 4, p. 33, 2018.

41. J. F. Randrianasoa, C. Kurtz, E. Desjardin, and N. Passat, "Binary partition tree construction from multiple features for image segmentation," *Pattern Recognition*, vol. 84, pp. 237–250, 2018.

42. B. Kiran and J. Serra, "Braids of partitions," in *International Symposium on Mathematical Morphology (ISMM), Proceedings*, ser. Lecture Notes in Computer Science, vol. 9082. Springer, 2015, pp. 217–228.

43. G. Tochon, M. Dalla Mura, M. A. Veganzones, T. Géraud, and J. Chanussot, "Braids of partitions for the hierarchical representation and segmentation of multimodal images," *Pattern Recognition*, vol. 95, pp. 162–172, 2019.

44. P. Soille, "Constrained connectivity for hierarchical image decomposition and simplification," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 30, pp. 1132–1145, 2008.

45. L. Najman and M. Schmitt, "Geodesic saliency of watershed contours and hierarchical segmentation," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 18, pp. 1163–1173, 1996.

46. S. Beucher and C. Lantuéjoul, "Use of watersheds in contour detection," in *International Workshop on Image Processing, Proceedings*, 1979.

47. J. Cousty, L. Najman, Kenmochi, and S. J. Ferzoli Guimarães, "Hierarchical segmentations with graphs: Quasi-flat zones, minimum spanning trees, and saliency maps," *Journal of Mathematical Imaging and Vision*, vol. 60, pp. 479–502, 2018.

48. B. Perret, S. Lefèvre, C. Collet, and É. Slezak, "Hyperconnections and hierarchical representations for grayscale and multiband image processing," *IEEE Transactions on Image Processing*, vol. 21, pp. 14–27, 2012.
49. N. Passat and N. Naegel, "Component-trees and multi-valued images: Structural properties," *Journal of Mathematical Imaging and Vision*, vol. 49, pp. 37–50, 2014.

50. V. Caselles and P. Monasse, *Geometric Description of Images as Topographic Maps*, ser. Lecture Notes in Mathematics. Springer, 2010.

51. D. W. Woodard, "On two-dimensional analysis situs with special reference to the Jordan curve theorem," *Fundamenta Mathematicae*, vol. 13, pp. 121–145, 1929.

52. L. E. J. Brouwer, "Über Jordansche Mannigfaltigkeiten," *Mathematische Annalen*, vol. 71, pp. 320–327, 1911.

53. E. Carlinet and T. Géraud, "MToS: A tree of shapes for multivariate images," *IEEE Transactions on Image Processing*, vol. 24, pp. 5330–5342, 2015.

54. Y. Song and A. Zhang, "Monotonic tree," in *Discrete Geometry for Computer Imagery (DGCI), Proceedings*, ser. Lecture Notes in Computer Science, vol. 2301. Springer, 2002, pp. 114–123.

55. A. Rosenfeld, "Adjacency in digital pictures," *Information and Control*, vol. 26, pp. 24–33, 1974.

56. N. Passat, J. Mendes Forte, and Y. Kenmochi, "Morphological hierarchies: A unifying framework with new trees," *Journal of Mathematical Imaging and Vision*, vol. 65, pp. 718–753, 2023.

57. N. Passat and Y. Kenmochi, "A topological tree of shapes," in *Discrete Geometry and Mathematical Morphology (DGMM)*, ser. Lecture Notes in Computer Science, vol. 13493. Springer, 2022, pp. 221–235.

58. N. Passat and B. Naegel, "Component-hypertrees for image segmentation," in *International Symposium on Mathematical Morphology (ISMM), Proceedings*, ser. Lecture Notes in Computer Science, vol. 6671. Springer, 2011, pp. 284–295.

59. A. Morimitsu, N. Passat, W. A. Luz Alves, and R. F. Hashimoto, "Efficient component-hypertree construction based on hierarchy of partitions," *Pattern Recognition Letters*, vol. 135, pp. 30–37, 2020.

60. Y. Xu, T. Géraud, and L. Najman, "Connected filtering on tree-based shape-spaces," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 38, pp. 1126–1140, 2016.

61. É. Grossiord, B. Naegel, H. Talbot, L. Najman, and N. Passat, "Shape-based analysis on component-graphs for multivalued image processing," *Mathematical Morphology – Theory and Applications*, vol. 3, pp. 45–70, 2019.

62. B. Perret, J. Cousty, O. Tankyevych, H. Talbot, and N. Passat, "Directed connected operators: Asymmetric hierarchies for image filtering and segmentation," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 37, pp. 1162–1176, 2015.

63. J. Angulo, "Morphological colour operators in totally ordered lattices based on distances: Application to image filtering, enhancement and analysis," *Computer Vision and Image Understanding*, vol. 107, pp. 56–73, 2007.

64. E. Aptoula and S. Lefèvre, "A comparative study on multivariate mathematical morphology," *Pattern Recognition*, vol. 40, pp. 2914–2929, 2007.

65. O. Lézoray, "Complete lattice learning for multivariate mathematical morphology," *Journal of Visual Communication and Image Representation*, vol. 35, pp. 220–235, 2016.

66. C. Ronse, "Why mathematical morphology needs complete lattices," *Signal Processing*, vol. 21, pp. 129–154, 1990.

67. N. Passat, B. Naegel, and C. Kurtz, "Component-graph construction," *Journal of Mathematical Imaging and Vision*, vol. 61, pp. 798–823, 2019.

68. G. K. Ouzounis and M. H. F. Wilkinson, "Mask-based second-generation connectivity and attribute filters," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 29, pp. 990–1004, 2007.

69. C. Ronse and V. Agnus, "Morphology on label images: Flat-type operators and connections," *Journal of Mathematical Imaging and Vision*, vol. 22, pp. 283–307, 2005.

70. R. M. Haralick, K. S. Shanmugam, and I. Dinstein, "Textural features for image classification," *IEEE Transactions on Systems, Man, and Cybernetics*, vol. 3, pp. 610–621, 1973.

71. J. Bragantini, A. X. Falcão, and L. Najman, "Rethinking interactive image segmentation: Feature space annotation," *Pattern Recognition*, vol. 131, p. 108882, 2022.

72. N. Passat, B. Naegel, F. Rousseau, M. Koob, and J. Dietemann, "Interactive segmentation based on component-trees," *Pattern Recognition*, vol. 44, pp. 2539–2554, 2011.

73. J. Pont-Tuset and F. Marqués, "Supervised assessment of segmentation hierarchies," in *European Conference on Computer Vision (ECCV), Proceedings, Part IV*, ser. Lecture Notes in Computer Science, vol. 7575. Springer, 2012, pp. 814–827.

74. B. Perret, J. Cousty, S. J. Ferzoli Guimarães, and D. Santana Maia, "Evaluation of hierarchical watersheds," *IEEE Transactions on Image Processing*, vol. 27, pp. 1676–1688, 2018.

75. E. J. Y. Cayllahua Cahuina, J. Cousty, S. J. Ferzoli Guimarães, Y. Kenmochi, G. Cámara Chávez, and A. de Albuquerque Araújo, "Hierarchical segmentation from a non-increasing edge observation attribute," *Pattern Recognition Letters*, vol. 131, pp. 105–112, 2020.

76. G. Barbosa da Fonseca, B. Perret, R. Negrel, J. Cousty, and S. Jamil Ferzoli Guimarães, "Fuzzy-marker-based segmentation using hierarchies," in *Discrete Geometry and Mathematical Morphology (DGMM), Proceedings*, ser. Lecture Notes in Computer Science, vol. 12708. Springer, 2021, pp. 391–403.

77. J. F. Randrianasoa, P. Cettour-Janet, C. Kurtz, E. Desjardin, P. Gançarski, N. Bednarek, F. Rousseau, and N. Passat, "Supervised quality evaluation of binary partition trees for object segmentation," *Pattern Recognition*, vol. 111, p. 107667, 2021.

78. N. Boutry, L. Najman, and T. Géraud, "Some equivalence relation between persistent homology and morphological dynamics," *Journal of Mathematical Imaging and Vision*, vol. 64, pp. 807–824, 2022.

79. H. Edelsbrunner and J. Harrer, "Persistent homology – A survey," *Contemporary Mathematics*, vol. 453, pp. 257–282, 2008.

80. J. R. Clough, N. Byrne, I. Öksüz, V. A. Zimmer, J. A. Schnabel, and A. P. King, "A topological loss function for deep-learning based image segmentation using persistent homology," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 44, pp. 8766–8778, 2022.

81. A. Malyugina, N. Anantrasirichai, and D. R. Bull, "A topological loss function for image denoising on a new BVI-lowlight dataset," *Signal Processing*, vol. 211, p. 109081, 2023.

82. B. Perret and J. Cousty, "Component tree loss function: Definition and optimization," in *Discrete Geometry and Mathematical Morphology (DGMM), Proceedings*, ser. Lecture Notes in Computer Science, vol. 13493. Springer, 2022, pp. 248–260.

83. M. Götz, G. Cavallaro, T. Géraud, M. Book, and M. Riedel, "Parallel computation of component trees on distributed memory machines," *IEEE Transactions on*
*Parallel and Distributed Systems*, vol. 29, pp. 2582–2598, 2018.

84. U. Moschini, A. Meijster, and M. H. F. Wilkinson, “A hybrid shared-memory parallel max-tree algorithm for extreme dynamic-range images,” *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 40, pp. 513–526, 2018.

85. S. Gazagnes and M. H. F. Wilkinson, “Distributed connected component filtering and analysis in 2D and 3D tera-scale data sets,” *IEEE Transactions on Image Processing*, vol. 30, pp. 3664–3675, 2021.

86. J. Cousty, B. Perret, H. Phelippeau, S. Carneiro, P. Kamlay, and L. Buzer, “An algebraic framework for out-of-core hierarchical segmentation algorithms,” in *Discrete Geometry and Mathematical Morphology (DGMM), Proceedings*, ser. Lecture Notes in Computer Science, vol. 12708. Springer, 2021, pp. 378–390.

87. J. Lefèvre, J. Cousty, B. Perret, and H. Phelippeau, “Join, select, and insert: Efficient out-of-core algorithms for hierarchical segmentation trees,” in *Discrete Geometry and Mathematical Morphology (DGMM), Proceedings*, ser. Lecture Notes in Computer Science, vol. 13493. Springer, 2022, pp. 274–286.

88. N. Blin, E. Carlinet, F. Lemaitre, L. Lacassagne, and T. Géraud, “Max-tree computation on GPUs,” *IEEE Transactions on Parallel and Distributed Systems*, vol. 33, pp. 3520–3531, 2022.