# Consistent connected operators based on trees of shapes

Julien Mendes Forte, Nicolas Passat, Akinobu Shimizu, Yukiko Kenmochi

## ► To cite this version:

Julien Mendes Forte, Nicolas Passat, Akinobu Shimizu, Yukiko Kenmochi. Consistent connected operators based on trees of shapes. SIAM Journal on Imaging Sciences, 2025, 18 (4), pp.2547-2579. 10.1137/25M174704X . hal-05175270

HAL Id: hal-05175270

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

Submitted on 22 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
Consistent Connected Operators Based on Trees of Shapes*

Julien Mendes Forte†, Nicolas Passat‡, Akinobu Shimizu§, and Yukiko Kenmochi†

**Abstract.** Hierarchical structures provide versatile and efficient solutions for representing, processing and analyzing images. In the framework of mathematical morphology, partial partition trees were proposed in order to model the grey-level images. The most popular are the component tree and the tree of shapes. Both trees are image models, i.e. they represent an image in a lossless, reversible way. Based on this property, they can be used for designing image processing operators. Indeed, by selecting some nodes of these trees and/or by modifying their associated grey-level values, one can define so-called connected operators, that act at the scale of flat zones instead of pixels, and thus avoid the generation of new contours. The definition of connected operators from the component tree has been the subject of an abundant literature. This is not the case of the tree of shapes, despite its high ability to model the topological and differential properties of grey-level images. In this article, we propose an algorithmic scheme to build consistent connected operators based on the tree of shapes. More precisely, the induced connected operators do not modify the differential properties of the image, and they also preserve the equivalence between any image and its tree of shapes. We prove that this algorithmic scheme presents an efficient time cost. We also demonstrate that it generalizes the previous approaches developed for connected operator design from morphological trees. Finally, we show how it opens the way to the development of connected versions of usual pixel-based, linear and non-linear operators. Codes freely available at: https://github.com/jmendesf/ToSConOp.

**Key word.** Tree of shapes, connected operators, grey-level imaging, hierarchical models, mathematical morphology.

**1. Introduction.** Gathering pixels into regions is a convenient way for dealing with various issues in image processing and analysis, for instance for reducing computational cost or for computing relevant shape-based descriptors. Defining regions from pixels has been considered for decades, since pioneering works related e.g. to the watershed transformation [3]. In practice, building regions in an image boils down to defining a partition of its support, generally with the constraint that these regions be connected, for the sake of spatial coherence, as exemplified by the popular paradigm of superpixels [4]. The notions of partitions [49] and connectivity [50] are then cornerstones of such approaches.

On the other hand, building hierarchical representations of images has also been a major concern over the last decades. Such approaches were often motivated by computational cost considerations, but also geared towards multiscale analysis of images. The seminal works related to hierarchical image representations, e.g. quad trees, did not strongly rely on image content. In the 90’s, both paradigms of hierarchical models and region-based approaches converged, leading to the notion of irregular region trees [40]. From this point on, such trees were deeply investigated, in particular in the framework of mathematical morphology.

These trees rely on either total or partial partitions of the image support. They subdivide the

*Funding: This work was funded by Région Normandie (thesis grant RIN), Partenariats Hubert Curien (Sakura, grant 49674RK) and the French Agence Nationale de la Recherche (grants ANR-20-CE45-0011, ANR-22-CE45-0034, ANR-23-CE45-0015). ANATOMIX is an EQUIPEX funded by the Investments for the Future program of the Agence Nationale de la Recherche (grant ANR-11-EQPX-0031).

†Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, F-14050 Caen, France (julien.mendes-forte@unicaen.fr, yukiko.kenmochi@unicaen.fr).

‡Université de Reims Champagne Ardenne, CRESTIC, Reims, France (nicolas.passat@univ-reims.fr)

§Institute of Engineering, Tokyo University of Agriculture and Technology, Koganei, Tokyo, Japan
image into successive partitions composed of regions—often flat zones [17]—that constitute their nodes. Alternatively to pixels, these regions are then used as primitives for defining the image. In particular, they can be involved in the design of so-called connected operators [56] which transform an image without altering its global content. Indeed, connected operators modify the values of the image at the scale of flat zones instead of pixels, thus avoiding the generation of new contours.

Within the large range of morphological trees, the component tree [54] and the tree of shapes [14] allow to model grey-level images. The component tree models the inclusion relation of the connected components of the successive threshold sets of the image. The tree of shapes models the nested relation between the level sets of the image. Despite different intrinsic properties, these trees are strongly related [43]. In particular, both trees are image models. This means that they represent an image in a lossless and reversible way. This property allows to use them as efficient image descriptors.

The fact that the component tree and the tree of shapes be image models also allows to design connected operators, by (1) turning the input image into its modeling tree, (2) modifying this tree, by selecting/discarding nodes and/or modifying their values, and (3) turning back the modified tree into its associated output image. This paradigm, developed by [29] for the component tree, led to the development of numerous applications. Surprisingly, it was not popularized for trees of shapes. This phenomenon may be explained by specific difficulties related to richer but more complex information carried by the tree of shapes, compared to the component tree.

In this article, we describe how connected operators can be built from the tree of shapes of an image. In particular, we propose an algorithmic scheme that extends the one proposed for the component tree, while tackling the difficulties induced by the specific structure of the tree of shapes.

This article, which is an extended and improved version of the conference paper [36], is organized as follows. Section 2 describes previous works dealing with morphological trees, trees of shapes and connected operators. Section 3 provides a minimal set of notions on the tree of shapes and the component tree. Section 4 recalls how connected operators on images can be built from operators on their morphological trees. It discusses the differential and structural issues related to this paradigm. Section 5 proposes a preliminary discussion on previously proposed solutions for building consistent connected operators from morphological trees. The first is a straightforward generalization of the global contrast invariance property of the morphological trees. The second is a state-of-the-art component tree node discarding approach. It is observed that this second strategy, relevant for the component trees, is invalid for the tree of shapes. Section 6 proposes a solution to this problem. It describes how to modify the value of a node of a tree of shapes without altering the structural and differential properties of its associated image. Section 7 provides a general algorithmic scheme that builds upon this elementary node modification to modify iteratively an arbitrary number of nodes of a tree of shapes. The induced algorithmic scheme provides a generic framework for the design of consistent connected operators based on the tree of shapes. Section 8 shows that this generic framework captures the principal paradigms previously proposed in the literature for designing connected operators from morphological trees. Section 9 provides a perspective discussion about the possibility of revisiting standard image filters acting at the scale of pixels in order to design some connected versions of these filters, acting at the scale of the flat zones. Section 10 concludes this article.

## 2. Related works.

### 2.1. Morphological trees.
In order to analyze, model, and more generally describe images, mathematical morphology provides an efficient framework with various hierarchical structures. These
structures, most often trees (i.e. rooted, connected, acyclic graphs), belong to the family of region-based image representations. Within this family, there exist two subfamilies: total partition hierarchies [16] that represent the entire image at each level of the tree, and partial partition hierarchies [43] that represent a subset of the image at each level.

Total partition hierarchies include structures such as the watershed tree [41], which generally captures the regions of influence of the minima of an image, or the binary partition tree [53], which progressively merges regions (starting from the pixels or flat zones) by following a given criterion. This structure was extended through the definition of the so-called α-tree [59]. In this paradigm, non-tree variants were also introduced, such as partition braids [31].

Partial partition hierarchies include trees such as the component tree [54], also known as the max- and min-trees. These structures are defined based on two key elements: a connectivity which determines the formation of connected components, and an order relation which establishes a ranking among the elements of the image. Typically, the component tree is constructed using the theory of set connections [57] for connectivity and a total order relation.

Variants of the component tree have explored generalizations of these foundational elements. Regarding connectivity, a modified component tree was proposed to incorporate the so-called hyperconnections [48]. Additionally, component-hypertrees [44] were developed to represent forests of component trees obtained from different connectivity levels within a single structure.

Regarding variants resulting from different order relations, the extension of the component tree to non-grey-level images, through partial order relations instead of total order relations, was also investigated. Depending on the structure of the Hasse diagram induced by the partial order relation, these generalized component trees may be either trees [33] or DAGs [45].

Another significant structure within the family of partial partition hierarchies is the tree of shapes, discussed in the next section.

**2.2. The tree of shapes.** The tree of shapes [12, 39, 14] is a self-dual hierarchical structure closely related to the component tree. Similarly to the component tree, it is constructed based on the decomposition of an image into threshold sets. However, instead of using the connected components themselves as nodes, the tree of shapes designates the level lines (shapes) of the connected components as the nodes, with the nesting relationship forming the edges between them. Additionally, the self-dual property of the tree of shapes enables it to handle both bright and dark regions of images, where the component tree only handles either bright or dark ones (through the max- and min-tree, respectively).

Initially developed for grey-level images, the tree of shapes was later extended to multivariate images in [10], by combining the trees of shapes of each image channel into a unified structure called the graph of shapes, which would then be derived into the multivariate tree of shapes.

The tree of shapes also gave rise to other morphological partial partition trees. Notably, it can serve as a foundation for building the complete tree of shapes [43], which allows to link both the max- and min-trees while also considering the inner borders of the connected components.

The complete tree of shapes is a central structure within the family of morphological partition trees, providing a means to unify the component tree and the tree of shapes, but also other structures derived from these hierarchies, such as the topological tree of shapes [42] and the monotonic tree [60].

The tree of shapes can be viewed as a generalization of the adjacency tree [51], which represents the inclusion relationships of components in a binary image. The tree of shapes extends this concept to value spaces with more than two classes. Constructing adjacency trees, and thus trees of shapes,
is tractable under convenient topological hypotheses [14, Chapter 2], for instance in the case of well-
composed images [34]. To define the tree of shapes, the notion of connectivity is typically expressed
within topological frameworks that align with digital grids, such as Cartesian spaces [51] or cubical
complex spaces [32]. These frameworks can also support self-duality [24, 6].

Concerning the computational cost of the tree of shapes, the fast level-line transform initially
126
127 guaranteed a quasi-linear time complexity [38]. More recent approaches, including top-down strate-
gies [37], were explored. A construction method based on the union-find algorithm, originally used
128
129 for computing the component tree, was proposed to ensure the tree of shapes construction in quasi-
linear time [25] and later proved for any dimension [23]. Parallel approaches were also investigated
130
131 [18]. Moreover, the connections between the component tree and the tree of shapes allow one to be
132 constructed from the other [9, 63]. The links of the tree of shapes with the topological tree of shapes
133
134 have been leveraged to compute the topological tree of shapes in quasi-linear time complexity [35].

The tree of shapes enjoys a variety of image-based applications, notably due to its capacity to
handle both dark and bright regions and its invariability to local contrast changes. It was widely used in
image analysis and feature extraction [61, 6], region-based image segmentation [1, 5] and interactive
segmentation [11]. Other applications include image editing [20], image simplification [68], image
classification [15], and noise estimation [21]. The tree of shapes can also be used in the case of image
filtering, with the benefit of allowing the definition of connected operators [55, 56].

**2.3. Connected operators based on morphological trees.** Mathematical morphology provides two paradigms for defining operators acting on images [58]. The first relies on the concept of adjunctions on lattices to build high-level morphological operators from low-level ones (dilations / erosions; openings / closings). The second paradigm relies on connectivity [57, 46], where the space is divided into connected components based on a specific criterion. In this article, we focus on the definition of morphological operators through the lens of connectivity.

In particular, this paradigm enabled the development of specific morphological operators, called
connected operators [55, 56]. Unlike usual filters which often operate at the scale of pixels, connected
operators process flat zones of the image. More precisely they act by eliminating/merging flat zones
in the image. Then, they neither create nor move contours in images.

Connected operators are notably well-suited for tasks such as structure and/or image simplification, noise removal, etc. In particular such operators were mostly based on the two notions of component tree [54, 29] and tree of shapes [13]. Since they model sequences of refining partitions, morphological hierarchies were also used for image segmentation. Notably, optimal cuts were studied [28, 30], leveraging the hierarchical structure to achieve optimal segmentations.

Filtering morphological hierarchies typically falls into the category of attributes filters [8], which
often rely on (spectral, geometric, morphological) criteria to determine which nodes should be mod-
ified. A wide literature was dedicated to the definition and computation of these attributes. One can
non-exhaustively mention vector-attributes [64], pattern-based attributes [19], non-flat attributes [26].
The handling of non-increasing attributes was investigated, in particular via the concept of shaping
[67]. Attributes can also define the connectivity upon which morphological hierarchies are built [66].

3. Tree of shapes, component trees: Basic notions.

**3.1. Image.** Let $\mathcal{U}$ be a nonempty discrete set endowed with a topological structure compliant with the hypotheses stated in [14, Chapter 2]. In practice, $\mathcal{U}$ may be e.g. $\mathbb{Z}^d$ ($d \ge 2$) endowed with the
<figure><img src="image_2.png" /><figcaption>**Figure 1.** (a) The set $V$ chosen as $Z$, endowed with the canonical order relation $\leq$. Only a part of $V$ is represented, namely $[[0, 3]]$ which are the values used for defining the image in (c). (b) The set $U$, chosen here is $Z^2$. Only a part of $U$, e.g. $[[0, 21]] \times [[0, 19]]$ is depicted. The set $Z^2$ is endowed with the framework of digital topology. (c) An image $I: U \to V$. We set $\perp = 0$ and $\top = 4$. The image has only $\perp$ values out of the depicted region $[[0, 21]] \times [[0, 19]]$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Figure 2.** The threshold sets of the image $I$ of Fig. 1(c). (a–e) The upper-threshold sets $\Lambda_v^\circ(I)$ (in black) for $v$ from 0 to 4. (f–j) The lower-threshold sets $\Lambda_v^\bullet(I)$ (in black) for $v$ from 0 to 4.</figcaption></figure>

digital topology framework [52].

Let $V$ be a nonempty discrete set endowed with a total order relation $\leq$. In practice, we will handle $V$ as $Z$, endowed with its canonical order relation.

We define an image as a function $I: U \to V$. The set $U$ is called the support of $I$. The set $V$ is called the value set of $I$. Let $\perp, \top \in V$. Without loss of generality, we assume that $I(U) \subseteq [[\perp, \top - 1]]$ and $\{x \in U | I(x) \geq \perp + 1\}$ is finite. These hypotheses are compliant with numerical images. We note $I$ the space of all the images $I: U \to V$, i.e. $I = V^U$. See Fig. 1 for illustrations of these notions.

**3.2. Threshold sets, connected components.** Let $v \in V$. The upper- and lower-threshold sets of $I$ for the value $v$ are defined as

$$ (3.1) \qquad \Lambda_v^\circ(I) = \{x \in U \mid v \leq I(x)\} \quad \text{and} \quad \Lambda_v^\bullet(I) = \{x \in U \mid v > I(x)\} $$

See Fig. 2 for illustrations of these notions.

For any $v \in V$, we note $\Pi[\Lambda_v^\circ(I)]$ (resp. $\Pi[\Lambda_v^\bullet(I)]$) the set of the connected components of $\Lambda_v^\circ(I)$ (resp. $\Lambda_v^\bullet(I)$). If $\Lambda_v^\circ(I) \neq \emptyset$ (resp. $\Lambda_v^\bullet(I) \neq \emptyset$), then $\Pi[\Lambda_v^\circ(I)]$ (resp. $\Pi[\Lambda_v^\bullet(I)]$) is a partition of $\Pi[\Lambda_v^\circ(I)]$ (resp. $\Pi[\Lambda_v^\bullet(I)]$).

We denote by

$$ (3.2) \qquad \Theta^\circ = \bigcup_{v \in V} \Pi[\Lambda_v^\circ(I)] \quad \text{and} \quad \Theta^\bullet = \bigcup_{v \in V} \Pi[\Lambda_v^\bullet(I)] $$

the set of all the connected components obtained through all the upper- and lower-threshold sets, respectively. See Fig. 3 for illustrations of these notions.
<figure><img src="image_4.png" /><figcaption>**Figure 3.** (a–d) The connected components of the upper-threshold sets $\Lambda_v^\circ(I)$ (in colour) for $v$ from 0 to 3. (e–h) The connected components of the lower-threshold sets $\Lambda_v^\bullet(I)$ (in colour) for $v$ from 1 to 4.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 4.** The elements of $X^*$ obtained by saturating the connected components of $\Theta^\circ \cup \Theta^\bullet$.</figcaption></figure>

Let $X \in \Theta^\circ \cup \Theta^\bullet$. Let $\bar{X} = \mathbb{U} \setminus X$. Let $\{\bar{X}_i\}_{i=1}^t$ ($t \ge 0$) be the set of all the finite connected components of $\bar{X}$. We set $X^* = X \cup \bigcup_{i=1}^t \bar{X}_i$ i.e. the set obtained by saturating $X$, i.e. by “filling its holes” and we set $\Theta^* = \{X^* | X \in \Theta^\circ \cup \Theta^\bullet\}$. See Fig. 4 for illustrations of these notions.

**3.3. Component trees, tree of shapes.** We consider the partial order relation $\subseteq$ on $\Theta^\circ$ (resp. $\Theta^\bullet$, resp. $\Theta^*$) and we note $\triangleleft^\circ$ (resp. $\triangleleft^\bullet$, resp. $\triangleleft^*$) its reflexive-transitive reduction. We define the two component trees [54] (namely the max- and min-trees) and the tree of shapes [14] as follows.

**Definition 1 (Component trees: max- and min-trees).** The max-tree of $I$ is the tree $\mathfrak{I}^\circ = (\Theta^\circ, \triangleleft^\circ)$. The min-tree of $I$ is the tree $\mathfrak{I}^\bullet = (\Theta^\bullet, \triangleleft^\bullet)$.

The max- and min-trees are dual versions of component trees.

**Definition 2 (Tree of shapes).** The tree of shapes of $I$ is the tree $\mathfrak{I}^* = (\Theta^*, \triangleleft^*)$.

We note $\mathbb{T}^\circ$ (resp. $\mathbb{T}^*$, resp. $\mathbb{T}^\circ$) the space of all the max-trees (resp. min-trees, resp. trees of shapes) associated to the images of $I$. See Fig. 5 for illustrations of these notions.

For the sake of concision, in the sequel, we will note $\mathfrak{I}^\circ = (\Theta, \triangleleft)$ and $\mathbb{T}$ when dealing with any of these three families of trees. The elements of $\Theta$ are called the nodes of $\mathfrak{I}^\circ$. The node $\mathbb{U}$ is the root of $\mathfrak{I}^\circ$. The elements of $\triangleleft$ are called the edges of $\mathfrak{I}^\circ$.

**3.4. Component trees and tree of shapes as image models.** Let $X \in \Theta$ be a node of $\mathfrak{I}^\circ$. In particular, $X$ is a subset of $\mathbb{U}$, i.e. $X \subseteq \mathbb{U}$. Let $\mathbf{x} \in X$. There may exist a node $Y \triangleleft X$ such that $\mathbf{x} \in Y$. Alternatively, for any $Y \triangleleft X$, we may have $\mathbf{x} \notin Y$. The points $\mathbf{x}$ that satisfy this second case compose the proper part of the node $X$.

**Definition 3 (Proper part of a node).** Let $X \in \Theta$. The proper part of $X$ in the tree $\mathfrak{I} = (\Theta, \triangleleft)$ is defined by

$$ (3.3) \qquad \rho(X) = X \setminus \bigcup_{Y \triangleleft X} Y $$

We note $\rho: \Theta \to 2^\mathbb{U}$ the function that defines the proper part of the nodes of $\Theta$. See Fig. 6 for illustrations of these notions.
<figure><img src="image_6.png" /><figcaption>**Figure 5.** (a) The set $\Theta^\circ$ of the connected components (Fig. 3(a-d)) of the upper-threshold sets of the image $I$ (Fig. 1(c)). (b) The max-tree $\tilde{\mathcal{I}}$ of $I$. (c) The set $\Theta^*$ of the connected components (Fig. 3(e-h)) of the lower-threshold sets of the image $I$. (d) The min-tree $\tilde{\mathcal{I}}^*$ of $I$. (e) The set $\Theta^*$ of the connected components (Fig. 4(a-d)) obtained by saturating the threshold sets (Fig. 3) of the image $I$. (f) The tree of shapes $\tilde{\mathcal{I}}^*$ of $I$. Each square of (b,d,f) corresponds to a node in (a,c,e), respectively. Each segment corresponds to an edge of $\triangle^\circ$ (resp. $\triangle^\bullet$, $\triangle^*)$ in (a) (resp. (c), (e)). The colour and position of each node are related to those of the connected component in (a,c,e).</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Figure 6.** Proper parts of the nodes of the morphological trees associated to the image $I$ (Fig. 1(c)). (a) Proper parts $\rho^\circ(X)$ of the nodes $X \in \Theta^\circ$ of the max-tree $\tilde{\mathcal{I}}$ (Fig. 5(b)) of $I$. (b) Proper parts $\rho^\bullet(X)$ of the nodes $X \in \Theta^\bullet$ of the min-tree $\tilde{\mathcal{I}}$ (Fig. 5(d)) of $I$. (c) Proper parts $\rho^*(X)$ of the nodes $X \in \Theta^*$ of the tree of shapes $\tilde{\mathcal{I}}^*$ (Fig. 5(f)) of $I$.</figcaption></figure>

**Remark 4.** For any $X \in \Theta$, we have $\rho(X) \neq \emptyset$.

**Remark 5.** The set $\rho(\Theta)$ is a partition of $\mathbb{U}$.

Note that the proper part of a node is not necessarily connected, whereas a node is, by definition, connected. This occurs, for instance, in Fig. 7(a), for node D.

Let $X \in \Theta$. By definition, we have $\mathcal{I}(\rho(X)) = \{\mathcal{I}(\mathbf{x}) | \mathbf{x} \in \rho(X)\} = \{\mathbf{v}\}$ for a given $\mathbf{v} \in \mathbb{V}$. In other words, all pixels in the proper part of a node share the same grey-level value. This justifies the following definition.

**Definition 6 (Height of a node).** Let $X \in \Theta$. The height $\eta(X) \in \mathbb{V}$ of $X$ in the tree $\tilde{\mathcal{I}} = (\Theta, \triangle)$ is defined by

$$ (3.4) \qquad \forall \mathbf{x} \in \rho(X), \eta(X) = \mathcal{I}(\mathbf{x}) $$

We note $\eta: \Theta \to \mathbb{V}$ the function that defines the height of the nodes of $\Theta$. See Fig. 5(b,d,f) for illustrations of these notions.
**Remark 7.** The way to compute the height of a node depends on the tree where it lies. More precisely, we have

218

219

220

$$ \eta^{\circ}(X) = \bigvee^{\ll} \{v \in \mathbb{V} \mid X \in \Pi[\Lambda_{v}^{\circ}(I)]\} = \bigvee^{\ll} \{v \in \mathbb{V} \mid X \subseteq \Lambda_{v}^{\circ}(I)\} $$

221

$$ \eta^{\bullet}(X) = \bigwedge^{\ll} \{v \in \mathbb{V} \mid X \in \Pi[\Lambda_{v}^{\bullet}(I)]\} - 1 = \bigwedge^{\ll} \{v \in \mathbb{V} \mid X \subseteq \Lambda_{v}^{\bullet}(I)\} - 1 $$

222

$$ \eta^{\star}(X) = \begin{cases} \bigvee^{\ll} \{\eta^{\circ}(Y) \mid X = Y^{\star}\} & \text{if } \{Y \in \Theta^{\circ} \mid X = Y^{\star}\} \neq \emptyset \\ \bigwedge^{\ll} \{\eta^{\bullet}(Y) \mid X = Y^{\star}\} & \text{if } \{Y \in \Theta^{\bullet} \mid X = Y^{\star}\} \neq \emptyset \end{cases} $$

223

224

225

226

227

228

229

Each node $X \in \Theta$ is associated to its proper part $\rho(X)$ and its height $\eta(X)$ that provide spatial and spectral information on $X$. More precisely, $\rho(X)$ and $\eta(X)$ characterize the contribution of the node $X$ to the definition of the image $I$ associated to the tree $\tilde{I}$.

From now on, we will consider that the tree $\tilde{I}$ is endowed with its proper part and height functions, i.e. we consider $\tilde{I}$ as $(\Theta, \ll, \rho, \eta)$.

From the tree $\tilde{I}$, it is possible to fully reconstruct the image $I$. This reconstruction process is given, for any $x \in \mathbb{U}$, by the following formula

230

$$ \mathcal{I}(\mathbf{x}) = \bigvee_{X \in \Theta} \mathbf{1}_{(\rho(X), \eta(X))}(\mathbf{x}) $$

231

232

233

234

where $\mathbf{1}_{(y,u)}: \mathbb{U} \to \mathbb{V}$ is the cylinder function defined by $\mathbf{1}_{(y,u)}(\mathbf{x}) = u$ if $\mathbf{x} \in Y$ and $\perp$ otherwise. It follows that the tree $\tilde{I}$ is a model of the image $I$, i.e. a lossless representation of the image. The reconstruction formula of Eq. (3.8) is pivotal for designing connected operators based on the morphological trees (component trees, tree of shapes) of an image, as discussed in the next section.

235

# 4. Connected operators based on morphological trees.

236

237

238

239

240

241

242

243

## 4.1. Construction of connected operators.
From an image $I \in \mathbb{I}$, we can build the tree $\tilde{I} \in \mathbb{T}$. Let us set $T_{\square \leftarrow \square} : \mathbb{I} \to \mathbb{T}$ the transformation that consists of building $\tilde{I}$ from $I$, i.e. $\tilde{I} = T_{\square \leftarrow \square}(I)$. From Eq. (3.8), this transformation is bijective. We note $T_{\square \leftarrow \Delta} : \mathbb{T} \to \mathbb{I}$ the inverse transformation, that consists of reconstructing the image $I$ from its tree $\tilde{I}$ from the formula of Eq. (3.8), i.e. $I = T_{\square \leftarrow \Delta}(\tilde{I})$.

241

242

243

The ability to navigate between the space $\mathbb{I}$ of images and the space $\mathbb{T}$ of morphological trees in a lossless way allows to define operators $\Gamma_{\square} : \mathbb{I} \to \mathbb{I}$ on images by building operators $\Gamma_{\Delta} : \mathbb{T} \to \mathbb{T}$ on morphological trees

244

$$ \Gamma_{\square} = T_{\square \leftarrow \Delta} \circ \Gamma_{\Delta} \circ T_{\Delta \leftarrow \square} $$

245

i.e. by defining $\tilde{I} = \Gamma_{\square}(I)$ from $\tilde{\mathfrak{I}} = \Gamma_{\Delta}(\tilde{I})$

246

$$ \begin{array}{ccc} \mathcal{I} & \xrightarrow{\Gamma_{\square}} & \tilde{\mathcal{I}} \\ \downarrow & & \downarrow \\ T_{\Delta \leftarrow \square} & T_{\square \leftarrow \Delta} & T_{\Delta \leftarrow \square} \\ \tilde{\mathfrak{I}} & \xrightarrow{\Gamma_{\Delta}} & \tilde{\mathfrak{I}} \end{array} $$

247

Here, our purpose is to build connected operators. Such operators can be characterized as follows.
Definition 8 (Connected operator). We say that $\Gamma_{\square} : I \to I$ is a connected operator if, for any neighboring points $\mathbf{x}, \mathbf{y} \in U$ with respect to the topological structure of $U$, we have

$$ (4.3) \qquad \mathcal{I}(\mathbf{x}) = \mathcal{I}(\mathbf{y}) \implies \Gamma_{\square}(\mathcal{I})(\mathbf{x}) = \Gamma_{\square}(\mathcal{I})(\mathbf{y}) $$

In order to design a connected operator $\Gamma_{\square}$ on $I$ from an operator $\Gamma_{\Delta}$ on $T$, a convenient way is to ensure that $\Gamma_{\Delta}$ transforms any tree $\tilde{\mathfrak{I}} = (\Theta, \triangleleft, \rho, \eta)$ into a tree $\tilde{\mathfrak{I}} = (\tilde{\Theta}, \tilde{\triangleleft}, \tilde{\rho}, \tilde{\eta})$ so that the partition $\rho(\Theta)$ of $U$ refines the partition $\tilde{\rho}(\tilde{\Theta})$. Indeed, if two neighbouring points $\mathbf{x}, \mathbf{y}$ of $U$ satisfy $\mathcal{I}(\mathbf{x}) = \mathcal{I}(\mathbf{y})$, then they belong to the same proper part $\rho(X)$ of a node $X \in \Theta$ of height $\eta(X) = \mathcal{I}(\mathbf{x}) = \mathcal{I}(\mathbf{y})$ in the tree $\tilde{\mathfrak{I}} = (\Theta, \triangleleft, \rho, \eta)$. It follows that they also belong to the same proper part $\tilde{\rho}(\tilde{X})$ of a node $\tilde{X} \in \tilde{\Theta}$ of height $\tilde{\eta}(\tilde{X})$ in the transformed tree $\Gamma_{\Delta}(\tilde{\mathfrak{I}}) = \tilde{\mathfrak{I}} = (\tilde{\Theta}, \tilde{\triangleleft}, \tilde{\rho}, \tilde{\eta})$. Thus, they satisfy $\Gamma_{\square}(\mathcal{I})(\mathbf{x}) = \Gamma_{\square}(\mathcal{I})(\mathbf{y}) = \tilde{\eta}(\tilde{X})$ from Eq. (3.8).

It follows from this discussion that two paradigms can be considered for defining operators $\Gamma_{\Delta}$ on $T$ that lead to connected operators $\Gamma_{\square}$ on $I$: defining $\tilde{\Theta}$ as a subset of $\Theta$ (i.e. selecting/discarding nodes of $\Theta$), or defining a new height function $\tilde{\eta}$ on $\tilde{\Theta}$. The new relation $\tilde{\triangleleft}$ (which is the reflexive-transitive reduction of $\subseteq$ on $\tilde{\Theta}$) will derive from the definition of $\tilde{\Theta}$. The new proper part function $\tilde{\rho}$ will derive from Eq. (3.3).

**4.2. Issues.** It is then possible to build a connected operator $\Gamma_{\square} : I \to I$ on images via the definition of an operator $\Gamma_{\Delta} : T \to T$ on the associated morphological trees (tree of shapes or component trees). However, this strategy may present two main flaws.

**4.2.1. Differential coherence.** The first issue is related to differential inconsistencies that may occur between the initial image $\mathcal{I}$ and the final image $\Gamma_{\square}(\mathcal{I})$. Indeed, there is no restriction on the way to define the height function $\tilde{\eta}$ of the tree $\Gamma_{\Delta}(\tilde{\mathfrak{I}})$. It follows that for any two points $\mathbf{x}, \mathbf{y}$ of $U$ such that $\mathbf{x} \in \rho(X)$ and $\mathbf{y} \in \rho(Y)$ with distinct nodes $X, Y \in \Theta$, and $\mathbf{x} \in \tilde{\rho}(\tilde{X})$ and $\mathbf{y} \in \tilde{\rho}(\tilde{Y})$ with distinct nodes $\tilde{X}, \tilde{Y} \in \tilde{\Theta}$, we may have $\eta(X) < \eta(Y)$ while $\tilde{\eta}(\tilde{X}) > \tilde{\eta}(\tilde{Y})$ and then

$$ (4.4) \qquad \mathcal{I}(\mathbf{x}) < \mathcal{I}(\mathbf{y}) \quad \text{and} \quad \Gamma_{\square}(\mathcal{I})(\mathbf{x}) > \Gamma_{\square}(\mathcal{I})(\mathbf{y}) $$

In particular, if this occurs for neighbouring points $\mathbf{x}, \mathbf{y}$, then $\Gamma_{\square}$ is not a gradient sign-preserving connected operator. Such a behaviour may alter the differential properties of the processed images.

**4.2.2. Structural coherence.** The second issue is related to structural inconsistencies that may occur between the resulting image $\Gamma_{\square}(\mathcal{I})$ and the tree $\tilde{\mathfrak{I}} = \Gamma_{\Delta}(\tilde{\mathfrak{I}})$ from which it is obtained. The way to define $\tilde{\Theta} \subseteq \Theta$ and/or to set a new height function $\tilde{\eta}$ for the nodes of $\tilde{\Theta}$ results in a new tree $\tilde{\mathfrak{I}} = \Gamma_{\Delta}(\tilde{\mathfrak{I}})$ that may no longer be a tree of shapes (resp. component tree). A fortiori, it may not be the tree of shapes (resp. component tree) $\tilde{\mathfrak{I}}$ of the resulting image $\tilde{\mathcal{I}} = \Gamma_{\square}(\mathcal{I})$.

This phenomenon does not alter the ability to build a correct resulting image $\tilde{\mathcal{I}}$ from such tree $\tilde{\mathfrak{I}}$ (see red configuration in Eq. (4.5)). Indeed, the function $T_{\square \leftarrow \Delta}$ can act on a set of trees larger than $T$, namely the set $\tilde{T}$ of the trees $\tilde{\mathfrak{I}} = (\tilde{\Theta}, \tilde{\triangleleft}, \tilde{\rho}, \tilde{\eta})$ that ensure that (1) $U \in \tilde{\Theta}$, (2) for any $\mathbf{x} \in U$, the set $\{\tilde{X} \in \tilde{\Theta} | \mathbf{x} \in \tilde{X}\}$ is totally ordered by $\subseteq$, (3) $\tilde{\triangleleft}$ is the reflexive-transitive reduction of $\subseteq$ and (4) $\tilde{\rho}$ is defined by Eq. (3.3). With these hypotheses, an image can be obtained from $\tilde{\mathfrak{I}}$ (which may not be a morphological tree) based on the reconstruction formula of Eq. (3.8).
Nonetheless, if the tree $\tilde{\mathfrak{I}}$ is not the tree of shapes (resp. component tree) $\tilde{\mathfrak{I}}_I$ of $\widehat{\mathcal{I}} = \Gamma_{\square}(\mathcal{I})$, it becomes impossible to rely on the modeling properties of the morphological trees to consider relevant image-based information guiding the algorithmic construction of $\Gamma_{\Delta}$ and thus $\Gamma_{\square}$.

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

**4.3. Purpose.** We investigate how to define connected operators $\Gamma_{\square} : \mathcal{I} \to \mathcal{I}$ on images by building operators $\Gamma_{\Delta} : \mathcal{T} \to \mathcal{T}$ on the morphological trees (tree of shapes, component trees) of these images. In particular, our purpose is to guarantee that these connected operators $\Gamma_{\square}$ be consistent from differential and structural points of views, i.e.

($\mathcal{P}_{\text{Diff}}$) they do not induce gradient-sign inversion, i.e. they guarantee that for any neighbouring points $\mathbf{x}, \mathbf{y} \in \mathcal{U}$, we have

$$ (4.6) \qquad \mathcal{I}(\mathbf{x}) \le \mathcal{I}(\mathbf{y}) \implies \Gamma_{\square}(\mathcal{I})(\mathbf{x}) \le \Gamma_{\square}(\mathcal{I})(\mathbf{y}) $$

($\mathcal{P}_{\text{Struct}}$) they rely on operators $\Gamma_{\Delta} : \mathcal{T} \to \mathcal{T}$ that preserve the morphological nature of the tree associated to the images, i.e.

$$ (4.7) \qquad \Gamma_{\Delta}(T_{\Delta \leftarrow \square}(\mathcal{I})) = T_{\Delta \leftarrow \square}(\Gamma_{\square}(\mathcal{I})) $$

(See also blue configuration in Eq. (4.5))

**5. Building connected operators: Preliminary discussion.** Before describing our general algorithmic scheme (Sects. 6–7) for dealing with the objectives stated in Sect. 4.3, let us first consider two partial solutions. The first (Sect. 5.1) is related to contrast invariance properties of the trees of shapes and component trees. The second (Sect. 5.2) is related to a node selection procedure proposed in the seminal works on component tree-based connected operators [8, 54, 29]. We then observe (Sect. 5.3) that this procedure is often not adapted for dealing with trees of shapes, since it may not satisfy the properties ($\mathcal{P}_{\text{Diff}}$) and ($\mathcal{P}_{\text{Struct}}$). This will motivate the general scheme proposed in Sects. 6–7.

**5.1. Connected operators based on contrast invariance.** Let $\gamma : \mathcal{V} \to \mathcal{V}$ be a transformation on the set of values. We say that $\gamma$ is a contrast transformation if it is strictly increasing, i.e. for all $u, v \in \mathcal{V}$ we have

$$ (5.1) \qquad u < v \implies \gamma(u) < \gamma(v) $$

The two images $\widehat{\mathcal{I}} : \mathcal{U} \to \mathcal{V}$ and $(\gamma \circ \widehat{\mathcal{I}}) : \mathcal{U} \to \mathcal{V}$ present isomorphic trees of shapes (resp. component trees). More precisely, if $\tilde{\mathfrak{I}}_I = (\Theta, \prec, \rho, \eta)$ then we have $\tilde{\mathfrak{I}}_{\gamma \circ \widehat{\mathcal{I}}} = (\Theta, \prec, \rho, \gamma \circ \eta)$, i.e. both trees only differ by their height function.
A first strategy to design operators $\Gamma_Δ : \mathbb{T} \to \mathbb{T}$ that lead to consistent connected operators $\Gamma_□ : \mathbb{I} \to \mathbb{I}$ consists of generalizing the above (global) contrast transformation paradigm as a local contrast transformation paradigm. From the tree $\tilde{\mathfrak{I}} = (\Theta, \triangleleft, \rho, \eta)$ of an image $\mathcal{I}$, we build a new tree $\Gamma_Δ(\tilde{\mathfrak{I}}) = \tilde{\mathfrak{I}} = (\Theta, \triangleleft, \rho, \tilde{\eta})$, that differs from $\tilde{\mathfrak{I}}$ only by its height function. This new height function $\tilde{\eta} : \Theta \to \mathbb{V}$ is constrained with respect to the initial height function $\eta : \Theta \to \mathbb{V}$ and the edges $\triangleleft$ of the two trees by assuming that for any $X, Y \in \Theta$ we have

$$ (5.2) \qquad X \triangleleft Y \implies \frac{\tilde{\eta}(X) - \tilde{\eta}(Y)}{\eta(X) - \eta(Y)} > 0 $$

In other words, it is allowed to modify (the distance between) the heights of any two neighbouring nodes as far as the strict positivity/negativity of their difference is not altered. This property is called local contrast invariance.

**Proposition 9.** If $\Gamma_Δ : \mathbb{T} \to \mathbb{T}$ satisfies the local contrast invariance property (Eq. (5.2)), then $\Gamma_□ : \mathbb{I} \to \mathbb{I}$ satisfies $(\mathcal{P}_{Diff})$ and $(\mathcal{P}_{Struct})$.

Of course, building $\tilde{\eta}$ as $\gamma \circ \eta$ is a trivial way to satisfy (Eq. (5.2)), i.e. a global contrast invariance is part of local contrast invariance. This first approach allows to build consistent connected operators which can modify locally the values of images, but these operators are not able to merge flat zones.

**5.2. Connected operators based on component tree node selection.** A second strategy to design operators $\Gamma_Δ : \mathbb{T} \to \mathbb{T}$ that lead to consistent connected operators $\Gamma_□ : \mathbb{I} \to \mathbb{I}$ consists of discarding nodes from the tree $\tilde{\mathfrak{I}}$ of the image $\mathcal{I}$. This approach was initially proposed in the case of component trees [8, 54, 29]. In this section, we describe it for the max-tree. The same paradigm also holds for the min-tree.

From the max-tree $\tilde{\mathfrak{I}}^° = (\Theta^°, \triangleleft^°, \rho^°, \eta^°)$ of an image $\mathcal{I}$, we build a new tree $\Gamma_Δ(\tilde{\mathfrak{I}}^°) = \tilde{\mathfrak{I}}^° = (\hat{\Theta}^°, \triangleleft^°, \hat{\rho}^°, \hat{\eta}^°)$ where the differences with $\tilde{\mathfrak{I}}^°$ derive from the discarding of nodes. We choose a set of nodes $\hat{\Theta}^° \subseteq \Theta^°$. For the sake of structural coherence, we ensure that $\mathbb{U} \in \hat{\Theta}^°$. For each node $X \in \Theta^° \setminus \{\mathbb{U}\}$, we set

$$ (5.3) \qquad \sigma(X) = \bigcap_{\hat{Y} \in \hat{\Theta}^°} \{ X \subset \hat{Y} \} $$

i.e. the lowest of the nodes greater than $X$ and not removed from $\tilde{\mathfrak{I}}^°$ to $\tilde{\mathfrak{I}}^°$. The set of edges $\triangleleft^°$ is simply defined by $\tilde{X} \triangleleft^° \sigma(\tilde{X})$ for any $\tilde{X} \in \hat{\Theta}^° \setminus \{\mathbb{U}\}$. The height function $\tilde{\eta}^° : \hat{\Theta}^° \to \mathbb{V}$ is the restriction of $\eta^°$ to $\hat{\Theta}^°$, i.e. $\tilde{\eta}^° = \eta^°_{\hat{\Theta}^°}$. The height of the nodes is then preserved from $\Theta^°$ to $\hat{\Theta}^°$. In the case of the max-tree, the reconstruction formula of Eq. (3.8) rewrites as

$$ (5.4) \qquad \mathcal{I}(\mathbf{x}) = \bigcap_{X \in \Theta} \mathbf{1}_{(X, \eta(X))}(\mathbf{x}) $$

where we can substitute $X$ to $\rho(X)$. It follows that the proper part of a discarded node $X$ is relevantly transfered to the proper part of $\sigma(X)$. The proper part function $\tilde{\rho}^° : \hat{\Theta}^° \to 2^{\mathbb{U}}$ is then defined, for any $\tilde{X} \in \hat{\Theta}^°$ by

$$ (5.5) \qquad \tilde{\rho}^°(\tilde{X}) = \rho^°(\tilde{X}) \cup \bigcup \{ \rho^°(Y) \mid Y \notin \hat{\Theta}^° \wedge \sigma(Y) = \tilde{X} \} $$
<figure><img src="image_9.png" /><figcaption>**Figure 7.** An image $\mathcal{I}$ (a) and its tree of shapes $\mathcal{I}^*_{\mathcal{I}}$ (b). The removal of $C$ leads to the tree $\tilde{\mathcal{I}}$ (c). Alternatively, setting the height of $C$ to that of $B$ leads to the tree $\tilde{\mathcal{I}}'$ (d). (e) The image $\tilde{\mathcal{I}}$ reconstructed from $\tilde{\mathcal{I}}$ (c) or $\tilde{\mathcal{I}}'$ (d) and its tree of shapes $\mathcal{I}^*_{\tilde{\mathcal{I}}}$ (f). On the one hand, both trees $\tilde{\mathcal{I}}$ (c) and $\tilde{\mathcal{I}}'$ (d) differ from $\mathcal{I}^*_{\tilde{\mathcal{I}}}$ (f). On the other hand, the sign of the gradients has been modified between $\mathcal{I}$ and $\tilde{\mathcal{I}}$ for some contours (e, in red). (Figure adapted from [39].)</figcaption></figure>

where $\rho^\circ(\tilde{X})$ is the proper part of $\tilde{X}$ in the initial tree $\mathcal{I}^\circ$ and the $\rho^\circ(Y)$ are the proper parts of the nodes $Y$ discarded from $\mathcal{I}^\circ$ to $\tilde{\mathcal{I}}^\circ$ such that $\tilde{X}$ is the lowest node in $\tilde{\mathcal{I}}^\circ$ greater than $Y$.

**Proposition 10.** If $\Gamma_\square : \mathbb{T} \to \mathbb{T}$ is built as defined above, then $\Gamma_\square : \mathcal{I} \to \mathcal{I}$ satisfies properties $(\mathcal{P}_{\text{Diff}})$ and $(\mathcal{P}_{\text{Struct}})$.

**5.3. The case of the tree of shapes.** In Sect. 5.2, the key idea is to select some nodes, preserve their height and transfer the proper part of the discarded nodes to their closest preserved parent. This approach leads to correct results when applied on the component trees (min-tree or max-tree).

It was shown by [13] that this strategy could be extended to the tree of shapes, but with the strong restriction of considering only the leaves of the tree, leading to the notion of grain filtering. More generally, when applied on the tree of shapes without such constraints, the strategy described in Sect. 5.2 may lead to inconsistencies: most often, none of $(\mathcal{P}_{\text{Diff}})$, $(\mathcal{P}_{\text{Struct}})$ is satisfied.

These defects are exemplified in Fig. 7. In this example, we consider an image $\mathcal{I}$ (Fig. 7(a)) modeled by its tree of shapes $\mathcal{I}^*_{\mathcal{I}}$ (Fig. 7(b)). This tree of shapes is composed by a set of five nodes $\Theta^* = \{A, B, C, D, E\}$. We define a reduced set of nodes $\tilde{\Theta}^* = \{A, B, D, E\}$ by discarding $C$, leading to a new tree $(\tilde{\Theta}^*, \triangle^*)$ (Fig. 7(c)). The height function $\tilde{\eta}^*$ for this new tree is directly derived from the height function $\eta^*$ of $\mathcal{I}^*_{\tilde{\mathcal{I}}}$, i.e. $\tilde{\eta}^*(X) = \eta^*(X)$ for any $X \in \{A, B, D, E\}$. The proper part function $\tilde{\rho}^*$ is built by following Eq. (5.5). In particular, we have $\tilde{\rho}^*(X) = \rho^*(X)$ for any $X \in \{A, D, E\}$, whereas $\tilde{\rho}^*(B) = \rho^*(B) \cup \rho^*(C)$. The resulting image $\tilde{\mathcal{I}}$ is reconstructed from $\tilde{\mathcal{I}} = (\tilde{\Theta}^*, \triangle^*, \tilde{\rho}^*, \tilde{\eta}^*)$ (Fig. 7(e)).

In this resulting image $\tilde{\mathcal{I}}$, we can observe, on the one hand, that the sign of the gradient has been modified on certain contours, depicted in red. In other words, $(\mathcal{P}_{\text{Diff}})$ is not satisfied. On the other hand, the tree of shapes $\mathcal{I}^*_{\tilde{\mathcal{I}}}$ of the image $\tilde{\mathcal{I}}$ is not the tree $\tilde{\mathcal{I}}$ (Fig. 7(c)). Comparing both trees, we can observe that the node $D$ is now split, while the node $E$ has disappeared, being absorbed by $B$. In other words, $(\mathcal{P}_{\text{Struct}})$ is not satisfied.

This example sheds light on the inability of the strategy proposed in Sect. 5.2 for building consistent connected operators, to be extended from the component trees to the tree of shapes. In the next two sections, we propose a strategy that tackles this issue. It will allow us to build consistent connected operators based on tree of shapes modifications.
<figure><img src="image_10.png" /><figcaption>Figure 8. Illustrative example of the notations of Sect. 6.1. The heights $\eta(\cdot)$ of the nodes are given into brackets.</figcaption></figure>

**6. Building connected operators from the tree of shapes – Step 1: Shifting one node of the tree.** We aim to design consistent connected operators $\Gamma_{\square}$ on images by proposing an algorithmic scheme for defining operators $\Gamma_{\triangle}$ on trees of shapes that guarantee that both ($\mathcal{P}_{\text{Diff}}$) and ($\mathcal{P}_{\text{Struct}}$) remain satisfied along the running of the scheme.

This scheme processes iteratively, and one-by-one, some nodes of the tree of shapes. For each node $X$, it modifies (increases or decreases) its height $\eta(X)$ and performs mergings with neighbouring nodes (with respect to $\triangle$) whenever these mergings are required to ensure that ($\mathcal{P}_{\text{Diff}}$) and ($\mathcal{P}_{\text{Struct}}$) remain satisfied.

**6.1. Definitions and notations.** Let $\mathcal{I}$ be an image and $\tilde{\mathcal{I}}^* = (\Theta^*, \triangle^*, \rho^*, \eta^*)$ its tree of shapes. For the sake of readability, we will omit the $*$ notation, and we will note $\tilde{\mathcal{I}}$ instead of $\tilde{\mathcal{I}}^*$.

Let $X \in \Theta$. In Sect. 5.1, we observed that the tree of shapes is not sensitive to global contrast modification. Without loss of generality, we then assume that $\eta(X) = 0$. All the objects introduced hereafter are related to the node $X$. For the sake of concision, we do not mention $X$ in most of their notations.

**Definition 11 (Parent, children).** The parent set $\mathcal{P}(X) \subset \Theta$ and the children set $C(X) \subset \Theta$ of $X \in \Theta$, are defined as

$$ (6.1) \qquad \mathcal{P}(X) = \{P \in \Theta \mid X \triangleleft P\} \quad \text{and} \quad C(X) = \{C \in \Theta \mid C \triangleleft X\} $$

If $\mathcal{P}(X) = \{P\}$, then $P$ is the parent node of $X$, i.e. $X \triangleleft P$. In that case, by abuse of notation, we will also write $\mathcal{P}(X) = P$. If $\mathcal{P}(X) = \emptyset$, then $X$ is the root of $\mathcal{I}$. We set

$$ (6.2) \qquad h = \begin{cases} \eta(P) \neq 0 & \text{if } \mathcal{P}(X) = \{P\} \\ 0 & \text{if } \mathcal{P}(X) = \emptyset \end{cases} $$

For any $C \in C(X)$, we have $\eta(C) \neq 0$. We set

$$ (6.3) \qquad C^+ = \{C \in C(X) \mid \eta(C) > 0\} \quad \text{and} \quad C^- = \{C \in C(X) \mid \eta(C) < 0\} $$

$$ (6.4) \qquad h^+ = \bigwedge \eta(C^+) \quad \text{and} \quad h^- = \bigvee \eta(C^-) $$

with $\bigwedge \leq \emptyset = +\infty$ and $\bigvee \leq \emptyset = -\infty$. We set

$$ (6.5) \qquad \mu^+ = \begin{cases} \bigwedge \leq \{h^+, h\} & \text{if } h > 0 \\ h^+ & \text{if } h \leq 0 \end{cases} \quad \text{and} \quad \mu^- = \begin{cases} \bigvee \leq \{h^-, h\} & \text{if } h < 0 \\ h^- & \text{if } h \geq 0 \end{cases} $$

$$ (6.6) \qquad \mathcal{M}^+ = \{C \in C^+ \mid \eta(C) = \mu^+\} \quad \text{and} \quad \mathcal{M}^- = \{C \in C^- \mid \eta(C) = \mu^-\} $$
<figure><img src="image_11.png" /><figcaption>**Figure 9.** Effect of the discarding operation of a node X. (a) Initial configuration. The node X has P for parent node (X ⊲ P) and the four $C_i$ ($1 \le i \le 4$) for children nodes ($C_i \subset X$). (b) Final configuration. The node X has been discarded. Its former children nodes $C_i$ become children of its former parent node P ($C_i \subset P$). The proper part of P has absorbed the proper part of X.</figcaption></figure>

**Function Discard**

Input: $\mathfrak{T} = (\Theta, \prec, \rho, \eta)$; $X \in \Theta \setminus \{\cup\}$

Output: $\mathfrak{T} = (\Theta, \prec, \rho, \eta)$ modified by discarding X

1 $P := \mathcal{P}(X)$

2 $\Theta \to X$

3 $\rho(P) := \rho(P) \cup \rho(X)$

4 $\prec \to (X, P)$

5 **foreach** $C \prec X$ **do**

6 $\prec \to (C, X)$

7 $\prec \leftarrow (C, P)$

The value $\mu^+$ (resp. $\mu^-$) is the lowest (resp. greatest) height of the nodes neighbouring X (with respect to $\prec$) and having a height strictly greater (resp. strictly lower) than the height of X. The children nodes of X of height $\mu^+$ (resp. $\mu^-$) are gathered in $M^+$ (resp. $M^-$). See Fig. 8 for illustrations of these notions.

**6.2. Short range shifting of a node.** Let $X \in \Theta$ be a node of the tree of shapes $\mathfrak{T}$. Let us suppose that we want to shift this node $X$, i.e. to set its height $\eta(X)$ to a new value $v \in \mathbb{V}$.

Each neighbouring node of $X$, namely each child or parent node $Y \in \mathcal{P}(X) \cup C(X)$ has a height out of the interval $[[\mu^- + 1, \mu^+ - 1]]$. From this fact and the local contrast invariance property stated in Prop. 9, we have the following result.

**Property 12.** If $\mu^- < v < \mu^+$, then the operator $\Gamma_\Delta$ that modifies the tree $\mathfrak{T}$ by setting $\eta(X) = v$ induces a connected operator $\Gamma_\Delta$ that satisfies $(\mathcal{P}_{\text{Diff}})$ and $(\mathcal{P}_{\text{Struct}})$.

In particular, modifying the height $\eta(X)$ of a node $X$ within the interval $[[\mu^- + 1, \mu^+ - 1]]$ does not alter $\Theta$, $\prec$ and $\rho$.

Let us now suppose that we want to shift the node $X$ so that $\eta(X) = \mu^-$ or $\mu^+$. In this section, we assume that we aim to set $\eta(X) = \mu^+$. The case $\eta(X) = \mu^-$ is symmetric.

Three cases can occur (Fig. 10(d-f)):

(i) $\mu^+ = h \neq h^+$;

(ii) $\mu^+ = h^+ \neq h$;

(iii) $\mu^+ = h = h^+$.

In Cases (i) and (iii), the new height $\eta(X) = \mu^+$ of $X$ becomes equal to the height $h$ of its parent node
<figure><img src="image_12.png" /><figcaption>**Figure 10.** Examples of the three cases of short range shifting for the node X. First row: initial configurations. Second row: heights of the nodes in the initial configurations. Third row: final configurations. (a–f) We have $\mu^{-} = -1$ and $\mu^{+} = 2$. The targeted height is $v = 2$. The nodes involved in the shifting procedure via the discarding operation(s) are depicted in colour: those that will be discarded (in red) and the one that will “absorb” the discarded node(s) (in blue). (g–i) The blue node is the remaining one after the discarding operation(s). The orange edges are those modified in $\triangleleft$ by the discarding operation(s).</figcaption></figure>

<caption>**Algorithm 1:** Short range shifting of a node</caption>

**Input:** $\mathcal{T} = (\Theta, \triangleleft, \rho, \eta)$; $X \in \Theta$; $v \in [[\mu^{-}, \mu^{+}]]$
**Output:** $\mathcal{T} = (\Theta, \triangleleft, \rho, \eta)$ modified by shifting $X$ to height $v$
1 &nbsp; **if** $\mu^{-} < v < \mu^{+}$ **then**
2 &nbsp;&nbsp;&nbsp; $\lfloor \eta(X) \rfloor := v$ \hfill (Prop. 12)
3 &nbsp; **else**
4 &nbsp;&nbsp;&nbsp; $\lfloor \text{if } v = h^{-} \text{ (resp. } h^{+}\text{) then}$
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor \text{foreach } C \in \mathcal{M}^{-} \text{ (resp. } \mathcal{M}^{+}\text{) do}$
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor \text{Discard}(\mathcal{T}, C) \text{ (Case (b), Props. 14, 15)} \rfloor$
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\eta(X) := v$
8 &nbsp; **if** $v = h$ **then**
9 &nbsp;&nbsp;&nbsp; $\lfloor \text{Discard}(\mathcal{T}, X) \text{ (Case (a), Props. 13, 15)} \rfloor$
P. In Cases (ii) and (iii), the new height $\eta(X) = \mu^+$ of X becomes equal to the height $h^+$ of some of its children nodes, gathered in $C^+$.

In any of these cases, some adjacent nodes in the modified tree exhibit an equal value $\mu^+$. The obtained tree $\tilde{\mathcal{Z}}$ is then no longer the tree of shapes of the image $\tilde{\mathcal{I}}$ that would be obtained by applying the reconstruction formula of Eq. (3.8). This means that ($\mathcal{P}_{Struct}$) is no longer satisfied. Despite of this structural flaw, ($\mathcal{P}_{Diff}$) remains satisfied.

In order to ensure the preservation of ($\mathcal{P}_{Struct}$) when setting $\eta(X) = \mu^+$, it is required to merge $X$ with its neighbouring nodes of equal height $\mu^+$.

Merging two nodes $Y \triangleleft Z$ with equal height boils down to discarding the node $Y$, which is “absorbed” by the node $Z$, since $Y \subset Z$. In particular, this is done by adding $\rho(Y)$ to $\rho(Z)$ and assigning the children nodes of $Y$ to $Z$. This atomic operation is illustrated in Fig. 9 and described in Func. Discard.

In Func. Discard, we discard a given node $X \in \Theta$. First, the parent $P$ of $X$ is determined (Line 1). Second, $X$ is removed from $\Theta$ (Line 2). Third, the proper part of the parent $P$ of $X$ absorbs the proper part of $X$ (Line 3). Finally, the edges of $\triangleleft$ are updated. The couple $(X, P)$ does no longer exist (Line 4) and each node $C$ which was a child of $X$ ($C \triangleleft X$) becomes a child of $P$ ($C \triangleleft X$) (Lines 5–7).

In this function and the further algorithms, $A := B$ means that $B$ is assigned to $A$, $A \to B$ means that $B$ is removed from $A$, and $A \leftarrow B$ means that $B$ is added to $A$. For the sake of readability, the input and output are noted the same. In practice, one can consider that the input objects are directly modified.

Let us now come back to the three Cases (i), (ii) and (iii). They can be reformulated from two alternative cases: (a) $\mu^+ = h$ and (b) $\mu^+ = h^+$. Indeed, Case (i) corresponds to (a) only; Case (ii) corresponds to (b) only; Case (iii) corresponds to the conjunction of (a) and (b).

In Case (a), $X$ and its parent node $P$ have the same height, and it is required that $X$ be discarded. In Case (b), $X$ and each of the children nodes $C \in \mathcal{M}^+$ have the same height, and it is required that each $C \in \mathcal{M}^+$ be discarded.

The following three properties establish that applying Func. Discard on the convenient nodes in the three Cases (i), (ii) or (iii) allows to obtain a tree $\tilde{\mathcal{Z}}$ which is the tree of shapes $\tilde{\mathcal{I}}$ of the image obtained by applying the reconstruction formula of Eq. (3.8).

**Property 13 (Case (i)).** If $\mu^+ = h \neq h^+$ then by applying the discarding function on the tree $\tilde{\mathcal{Z}}_I$ to the node $X$, the induced connected operator satisfies ($\mathcal{P}_{Struct}$).

**Property 14 (Case (ii)).** If $\mu^+ = h^+ \neq h$ then by applying the discarding function on the tree $\tilde{\mathcal{Z}}_I$ to the node(s) $C \in \mathcal{M}^+$, the induced connected operator satisfies ($\mathcal{P}_{Struct}$).

**Property 15 (Case (iii)).** If $\mu^+ = h = h^+$ then by applying the discarding function on the tree $\tilde{\mathcal{Z}}_I$ to the nodes $C \in \mathcal{M}^+$ and $X$, the induced connected operator satisfies ($\mathcal{P}_{Struct}$).

This whole process of shifting, called short range shifting of a node is exemplified in Fig. 10 and described in Alg. 1. In this algorithm, Lines 1–2 correspond to the local contrast invariance of Prop. 12, when the height of $X$ is set to a value in the interval $[[\mu^- + 1, \mu^+ - 1]]$. Lines 3–9 correspond to the case where the height of $X$ is set to the value $\mu^-$ or $\mu^+$, which requires discarding some child(ren) node(s) (Case (b), Lines 4–7) and/or $X$ itself (Case (a), Lines 8–9).

Note that short range shifting of a node in a tree corresponds to the classical notion of edge contraction, a fundamental operation in graph theory [27]. Discarding a node $X$ with parent $P = \mathcal{P}(X)$ essentially corresponds to contracting the edge $(X, P)$ in $\triangleleft$. The specificity is here that the resulting
<figure><img src="image_13.png" /><figcaption>**Figure 11.** The successive steps of long-range shifting for a node X (first row) with an initial height $\eta(X) = 1$ and the side effect on the image (second row). The target height is $v = 5$. The blue nodes are shifted, while the red nodes are involved in the intermediate short-range shiftings.</figcaption></figure>

<caption>**Algorithm 2:** Long range shifting of a node</caption>

**Input:** $\mathcal{T} = (\Theta, <, \rho, \eta)$; $X \in \Theta$; $v \in [\perp, \top - 1]$**
**Output:** $\mathcal{T} = (\Theta, <, \rho, \eta)$ modified by shifting $X$ to height $v$
1 &nbsp; **while** $\eta(X) \neq v$ **do**
2 &nbsp;&nbsp;&nbsp;&nbsp; $P := \mathcal{P}(X)$
3 &nbsp;&nbsp;&nbsp;&nbsp; **if** $v > \mu^+$ **then**
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor b := \mu^+ \rfloor$
5 &nbsp;&nbsp;&nbsp;&nbsp; **else if** $v < \mu^-$ **then**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor b := \mu^- \rfloor$
7 &nbsp;&nbsp;&nbsp;&nbsp; **else**
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor b := v \rfloor$
9 &nbsp;&nbsp;&nbsp;&nbsp; Apply **Alg. 1** ($\mathcal{T}, X, b$)
10 &nbsp;&nbsp;&nbsp;&nbsp; **if** $X \notin \Theta$ **then**
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor X := P \rfloor$

node remains $P$ and retains the same height while its proper part absorbs that of $X$.

**6.3. Long range shifting of a node.** In Sect. 6.2, we investigated how to shift the node $X$ so that $\eta(X)$ is assigned a new value $v \in [\mu^-, \mu^+]$, which is called short range shifting. We now assume that we aim to shift $X$ so that its height $\eta(X)$ is assigned a new value $v \in [\perp, \top - 1]$, which is called long range shifting. We still aim to carry out this node shifting so that the induced operator $\Gamma_\Delta$ leads to a connected operator $\Gamma_\square$ that satisfies $(\mathcal{P}_{\text{Diff}})$ and $(\mathcal{P}_{\text{Struct}})$.

We already observed that shifting a node $X$ by modifying its value $\eta(X)$ beyond $[\mu^-, \mu^+]$ without
considering the side effects of this value modification on the structure of the tree of shapes may lead to structural and differential inconsistencies, as illustrated by Fig. 7.

In particular, we observed that when setting $\eta(X)$ to $\mu^-$ or $\mu^+$, it is mandatory that a discarding operation occur, in order to merge $X$ with its parent node and/or some of its children nodes. This is a fortiori the case when setting $\eta(X)$ to a value out of $[\mu^-, \mu^+]$.

Based on the fact that the short range shifting operation satisfies $(\mathcal{P}_{\text{Diff}})$ and $(\mathcal{P}_{\text{Struct}})$, carrying out a long range shifting operation can be written as iteratively performing short range shiftings from the initial value $\eta(X)$ of $X$ to the target height $v$. Let us suppose that $v > \mu^+$ (the same reasoning holds for $v < \mu^-$).

If we apply Alg. 1 to the node $X$ to modify its height to the value $v = \mu^+$, then $X$ is merged with some of its neighbouring nodes (parent and/or children), leading to a new node $\tilde{X}$ that may differ from $X$ but such that $X \subseteq \tilde{X}$. Thus, further modifying $X$ boils down to modifying $\tilde{X}$. This node $\tilde{X}$ is associated to its own interval $[\tilde{\mu}^-, \tilde{\mu}^+]$ with $\tilde{\mu}^+ < \tilde{\mu}^+$. If $v \le \tilde{\mu}^+$, then the process ends by applying Alg. 1 (Lines 1–2 and 9, Prop. 12) with the value $v$. If $\tilde{\mu}^+ < v$, then the process continues one step further by applying Alg. 1 (Lines 3–9, Props. 15–14) with the value $\tilde{\mu}^+$, and so on. This iterative process is described in Alg. 2 (see also Fig. 11). Following graph theory terminology [27], it corresponds to a series of path contractions.

## 6.4. Complexity analysis.

**6.4.1. Data structures.** An image $\mathcal{I}$ is composed by the set of points $\mathcal{U}$ and the function $\mathcal{I}: \mathcal{U} \to \mathcal{V}$ itself. We denote by $p$ the number of points $\mathbf{x}$ of a subset of $\mathcal{S}$ of $\mathcal{U}$ such that $\mathcal{I}(\mathbf{x}) > \perp$. This value $p$ is the size of the image support actually handled. The structure (e.g. a static array) that models $\mathcal{S}$ and $\mathcal{I}$ presents a space cost $O(p)$. We can assume that for any point $\mathbf{x} \in \mathcal{S}$, its value $\mathcal{I}(\mathbf{x})$ is accessed (and updated) with a time cost $O(1)$.

A tree of shapes $\mathfrak{T}$ is composed by the set of nodes $\Theta$, the set of edges $<$, the proper part function $\rho$ and the height function $\eta$. We note $n$ (resp. $e$) the number of nodes (resp. edges) of $\mathfrak{T}$. We have $e + 1 = n \le p$. A node $X \in \Theta$ only needs to be identified, since its spatial and spectral information are carried by the function $\rho$ and $\eta$. The structure (e.g. a static array) that models $\Theta$ then presents a space cost $O(n)$. We can assume that any node $X \in \Theta$ is accessed in this structure with a time cost $O(1)$. We will only remove nodes from $\Theta$. Then, in absence of addition of new nodes, the update of the structure has a time cost $O(1)$.

For each node $X \in \Theta$, we need to determine the parent $P$ of $X$ ($X \prec P$). We then need a first structure that allows to access $P$ for each node $X$. This structure (e.g. a static array) has a space cost $O(n)$. We can assume that for any node $X$, its parent node is accessed in this structure with a time cost $O(1)$. For each node $X$, we also need to determine the children $C$ of $X$ ($C \prec X$). We then need a second structure that allows to access the set of the children nodes $C(X)$ for each node $X$. This structure (e.g. a static array of dynamic lists) also has a space cost $O(n)$, since the size of $\Theta$ is $n$ and each node is the child of at most one node. We can assume that for any node $X \in \Theta$, its set of children nodes $C(X)$ is accessed in this structure with a time cost $O(1)$. Updating the children nodes is required in Func. Discard (Lines 3–6). This requires to update both structures. The first structure is updated with a time cost $O(|C(X)|)$. The second structure is updated with a time cost that depends on its potential sorting. If it is sorted with respect to $\eta$, then the time cost for the updating is $O(|C(X)|\log(|C(P)| + |C(X)|))$. If it is not sorted, then the time cost for the updating is $O(1)$. Note that for any node $X \in \Theta$ we have in average $|C(X)| \sim 1$. We can then assume that $C(X)$ is maintained sorted
<table><caption>**Table 1**

Space and time cost for the data structures required to handle Func. Discard and Algs. 1–2.</caption><thead><tr><th>Data structures</th><th><i>I</i></th><th><i>Θ</i></th><th>&lt;</th><th><i>ρ</i></th><th><i>η</i></th></tr></thead><tbody><tr><td>Space cost</td><td><i>O</i>(<i>p</i>)</td><td><i>O</i>(<i>n</i>)</td><td><i>O</i>(<i>n</i>)</td><td><i>O</i>(<i>p</i>)</td><td><i>O</i>(<i>n</i>)</td></tr><tr><td>Time cost</td><td><i>O</i>(1)</td><td><i>O</i>(1)</td><td><i>O</i>(1)</td><td><i>O</i>(1)</td><td><i>O</i>(1)</td></tr></tbody></table>

and that the time cost for the updating is $O(1)$.

For each node $X$, we need to determine its proper part $\rho(X) \subseteq \mathbb{S}$. Here, we need only one structure that associates to each node $X$ its proper part $\rho(X)$. (Indeed, it is not required to store, for each point $\mathbf{x} \in \mathbb{S}$ the node $X$ such that $\mathbf{x} \in \rho(X)$, since this information will be used only once, when the final image will be reconstructed from the tree (Eq. (3.8)).) The space cost of the structure (e.g. a static array of dynamic lists) is $O(p)$. We can assume that for any node $X \in \Theta$, the node and the set of points of its proper part $\rho(X)$ is also accessed with a time cost $O(1)$. Updating the proper part of a node is required in Func. Discard (Line 3). By assuming that the points within the proper part are not sorted, updating the structure accordingly is done with a time cost $O(1)$.

For each node $X \in \Theta$, we need to determine its height $\eta(X) \in \mathbb{V}$. The structure (e.g. a static array) that models $\eta$ presents a space cost $O(n)$. We can assume that any node $X$ and its height $\eta(X)$ are accessed in this structure with a time cost $O(1)$. Updating the height of a node is required in Alg. 1 (Lines 2, 7). The structure is updated with a time cost $O(1)$.

These space and time cost information are summarized in Tab. 1.

**6.4.2. Complexity analysis.** Function Discard determines the parent node $P$ of $X$ (Line 1) with a time cost $O(1)$. It removes the node $X$ from $\Theta$ (Line 2) with a time cost $O(1)$. The proper part of $X$ is added to the proper part of its parent $P \in \Theta$ (Line 3) with a time cost $O(1)$. The edges between $X$ and its former parent and children are updated (Lines 4–7) with a time cost $O(1)$. The time cost of Func. Discard is then

$$ (6.7) \qquad \text{Cost}(\text{Func. Discard}) = O(1) $$

Algorithm 1 deals with two mutually exclusive cases, that depend on the value of $v$ with respect to $\mu^-$ and $\mu^+$. It compares the values of $v$, $\mu^-$ and $\mu^+$ (Line 1) with a time cost $O(1)$ (since $h^-$ and $h^+$ are computed with a time cost $O(|C(X)|)$ with $|C(X)| \sim 1$ and then $\mu^-$ and $\mu^+$ are computed with a time cost $O(1)$ from $h^-$ and $h^+$). If we have $\mu^- < v < \mu^+$, then $\eta(X)$ is set to $v$ (Line 2) with a time cost $O(1)$. Otherwise (Line 3), we first assess if $v = h^+$ (resp. $v = h^-$) (Line 4) with a time cost $O(1)$. If so, for each child node $C \in \mathcal{M}^+$ (resp. $\mathcal{M}^-$) (Line 5), Func. Discard is called (Line 6). Since $|C(X)| = O(1)$, the determination of $\mathcal{M}^+$ (resp. $\mathcal{M}^-$) has a time cost $O(1)$ and the space cost of $\mathcal{M}^+$ (resp. $\mathcal{M}^-$) is also $O(1)$. The number of iterations (Line 5) is then also $O(1)$. The time cost of Func. Discard is $O(1)$. The time cost of the “foreach” block (Lines 5–6) is then $O(1)$. The value $\eta(X)$ is updated (Line 7) with a time cost $O(1)$. The time cost of the “if” block (Lines 4–7) is then $O(1)$. Second, we assess if $v = h$ (Line 8) with a time cost $O(1)$. If so, Func. Discard is called (Line 9) with a time cost $O(1)$. The time cost of the “if” block (Lines 8–9) is then $O(1)$. The time cost of Alg. 1 is then

$$ (6.8) \qquad \text{Cost}(\text{Alg. 1}) = O(1) $$

Algorithm 2 iterates $\delta$ times, with $1 \le \delta \le |\eta(X) - v|$ (Line 1). At each iteration, the node $P$ is determined (Line 2) with a time cost $O(1)$. We also need to compute $\mu^+$ and $\mu^-$ with a time cost $O(1)$
(see discussion on Alg. 1). Then, b can be updated (Lines 3–8) with a time cost $O(1)$. Algorithm 1 is called (Line 9) with a time cost $O(1)$. Finally, we assess if $X \notin \Theta$ (Line 10) with a time cost $O(1)$. If so, we update $X$ as $P$ with a time cost $O(1)$. The time cost of Alg. 2 is then

$$ (6.9) \qquad \text{Cost}(\text{Alg. 2}) = O(1 + \delta) = O(1 + |\eta(X) - v|) $$

Note that until the $(\delta - 1)$th iteration, the calls of Alg. 1 lead to the discarding of nodes. For each node $X \in \Theta$, we observed that $|C(X)| \sim 1$, which implies that the number of discarded nodes at each iteration is also equivalent to 1. It follows that the number $\delta$ of iterations and the number of discarded nodes are equivalent. The time cost of Alg. 2 is then output-sensitive, and it linearly depends on the reduction $\delta$ (i.e. the reduction of the size of $\Theta$) of the tree $\mathfrak{T}$.

## 7. Building connected operators from the tree of shapes – Step 2: Shifting many nodes of the tree.
In Sect. 6, we described how to shift a single node of a tree of shapes (Alg. 2). We now describe how to shift many nodes of a tree of shapes in order to build connected operators.

### 7.1. Criterion, target height, priority.
This process, described in Alg. 3, basically consists of applying iteratively, as many times as necessary, the single node shifting of Alg. 2. To carry out such an iterative process, three questions arise:

* Which nodes to shift?

* To which values?

* In which order?

Answering these three questions requires to define three functions defined on the set of nodes: a criterion function $\kappa$, a target height function $v$ and a priority function $\pi$.

The criterion is a Boolean function $\kappa: \Theta \to \mathbb{B}$. It allows to determine if a node $X \in \Theta$ should be shifted ($\kappa(X) = True$) or not ($\kappa(X) = False$). This criterion may depend, for instance, on properties of the nodes, intrinsic or with respect to their context in the tree (for instance size of the nodes, number of children, height, etc.).

The target height is a function $v: \Theta \to \mathbb{V}$ (for instance, height of the parent node, height of the closest neighbour, average height over the $k$ nearest neighbours, etc.). For any node $X \in \Theta$, it indicates the value $v(X) \in \mathbb{V}$ to which $X$ should be shifted, if such shifting would occur. This target height may be any value of $\mathbb{V}$. Depending on the application, the target height $v(X)$ may be chosen inside, on the boundary, or outside of the interval $[[\mu^-, \mu^+]]$ associated to $X$.

The priority is a function $\pi: \Theta \to \mathbb{R}$. The nodes $X \in \Theta$ of greatest value $\pi(X)$ are those that should be shifted first, provided that they also satisfy $\kappa$. Once again, the definition of the priority is guided by the application (for instance, bottom-up / top-down, by increasing / decreasing area / height, etc.). It may also happen that no priority be required, in particular in the case of greedy algorithms.

Depending on the application, $\kappa$, $v$, $\pi$ may remain constant, or may (locally or globally) evolve when the tree undergoes modifications.

We set

$$ (7.1) \qquad \Theta_{\kappa} = \{X \in \Theta \mid \kappa(X)\} $$

the set of the nodes that are eligible for shifting. The node $X$ that will be processed will be

$$ (7.2) \qquad X = \arg\min_{\tilde{X} \in \Theta_{\kappa}} \max \pi(\tilde{X}) $$
<figure><img src="image_14.png" /><figcaption>**Figure 12.** An application of Alg. 3 for image simplification. (a) A remote sensing image (Landsat-7 image courtesy of the U.S. Geological Survey) (image: 2.3 · 10⁵ pixels; tree of shapes: 1.7 · 10⁵ nodes). We apply the generic tree of shapes modification by considering a criterion $κ$ that selects the nodes X with a proper part smaller than a given size $λ$, i.e. $Θ_k = \{X \in Θ | |ρ(X)| \le λ\}$. The target height is the height of the parent of the selected nodes X, i.e. $v(X) = η(P(X))$. The priority $π$ is induced by the post-order traversal of the tree. (b-c) Simplified images obtained for (b) $λ = 10$ (tree of shapes: 1.6 · 10⁴ nodes) and (c) $λ = 50$ (tree of shapes: 4.3 · 10³ nodes). (a-c) The red-squared sample is magnified in the black-squared bottom-right area.</figcaption></figure>

<table><caption>**Algorithm 3:** Generic tree of shapes modification</caption><tr><td>Input:</td><td>$\mathfrak{T} = (Θ, ↓, ρ, η)$</td><td></td></tr><tr><td>Parameters:</td><td>$κ : Θ → B; υ : Θ → V; π : Θ → R$</td><td>(Criterion; Target height; Priority)</td></tr><tr><td>Output:</td><td>$\mathfrak{T}$ modified according to $κ, υ$ and $π$</td><td></td></tr><tr><td>1</td><td>Compute $κ, υ, π$</td><td></td></tr><tr><td>2</td><td>Build $Θ_k$</td><td></td></tr><tr><td>3</td><td>while $Θ_k ≠ ∅$ do</td><td></td></tr><tr><td>4</td><td>&nbsp;&nbsp;&nbsp;&nbsp;Choose $X ∈ Θ_k$ with respect to $π$</td><td></td></tr><tr><td>5</td><td>&nbsp;&nbsp;&nbsp;&nbsp;Apply Alg. 2 ($\mathfrak{T}, X, υ(X)$)</td><td></td></tr><tr><td>6</td><td>&nbsp;&nbsp;&nbsp;&nbsp;Update $κ, υ, π$</td><td></td></tr><tr><td>7</td><td>&nbsp;&nbsp;&nbsp;&nbsp;Update $Θ_k$</td><td></td></tr></table>

The set $Θ_k$ may evolve at each iteration, on the one hand due to the progressive reduction of $Θ$ caused by the discarding operations, on the other hand due to the potential updating of $κ$.

**7.2. General description of the process.** The modification process described in Alg. 3 takes as input a tree of shapes $\mathfrak{T} = (Θ, ↓, ρ, η)$. It also considers the three functions $κ, υ$ and $π$. These functions are given as parameters, not as input. Indeed, the modus operandi for building $κ, υ$ and $π$ is known, but the three functions are not built beforehand, and need to be set while running the algorithm. The tree of shapes provided as output is the tree $\mathfrak{T} = (Θ, ↓, ρ, η)$, modified with respect to $κ, υ$ and $π$.

The first step consists of building $κ, υ$ and $π$ (Line 1). It is then possible to build $Θ_k$ (Eq. (7.1)) (Line 2). The while loop (Lines 3-7) iterates until $Θ_k$ becomes empty, i.e. until no node need to be shifted. At each iteration of the loop, the node X to be processed is chosen in $Θ_k$ with respect to the priority $π$ (Eq. (7.2)) (Line 4). Alg. 2 is then run for this node and its target height $υ$ (Line 5), leading to an update of the tree $\mathfrak{T}$. The parameter functions $κ, υ$ and $π$ are updated (Line 6). These updates do not necessarily imply modifications of these functions, and depend on the application. Updating $κ$, at
<figure><img src="image_15.png" /><figcaption>**Figure 13.** In red: evolution of the number of nodes |Θ| of the tree of shapes (y-axis, left) of the images resulting from the simplification process of Fig. 12, for λ varying from 0 to 50 (x-axis). In blue: Evolution of the perceptual similarity measure LPIPS (y-axis, right) for λ varying from 0 to 50 (x-axis). The input image is that of Fig. 12(a).</figcaption></figure>

least by fixing $κ(X) = False$ is a sufficient condition for guaranteeing the termination of Alg. 3. It is then possible to update $Θ_κ$ (Line 7).

An application of Alg. 3 is exemplified in Fig. 12. The comparative evolution of the perceptual similarity measure (LPIPS [69]) and of the structural simplification of the image (number of nodes of the tree of shapes) is given in Fig. 13, where nodes that exhibit a proper part lower than a threshold $λ$ are given the altitude of their parent to remove them. We observe that the size of the tree of shapes rapidly decreases, with 10% of its initial size at $λ = 10$ (Fig. 12(b)). In the meantime, the LPIPS measure slowly increases (the lower, the better), with a value 0.1 at $λ = 10$ (Fig. 12(b)). The structure of the tree of shapes and of the image can then be greatly simplified while preserving a satisfactory perceptual similarity.

**7.3. Complexity analysis.** The three functions $κ, v$ and $π$ are chosen with regards to the targeted application of the algorithm. Their time cost cannot be explicit in a general analysis. We will note $c \ge 1$ the time cost required to compute / update $κ, v$ and $π$ for one node $X$.

Computing $κ, v, π$ (Line 1) is done with a time cost $O(n \cdot c)$. Each of these three functions has a space cost $O(n)$, and we can assume that their value for a given node $X \in Θ$ is accessed with a time cost $O(1)$.

The construction of $Θ_κ$ from $Θ$ and $κ$ is then done with a time cost $O(n)$. The size of $Θ_κ$ is $O(n)$. If a non-trivial priority $π$ is considered, i.e. if Alg. 3 is not greedy, then $Θ_κ$ is sorted with a time cost $O(n \cdot \log n)$. We can assume that any element is accessed in $Θ_κ$ with a time cost $O(\log n)$. The vacuity test of $Θ_κ$ (Line 3) is done with a time cost $O(1)$. The while loop iterates $ℓ$ times ($ℓ \ge 0$). We label each iteration by $j \in [1, ℓ]$. At iteration $j$, a node $X$ is chosen as maximizing $π$ in $Θ_κ$ (Line 4) with a time cost $O(\log n)$. Alg. 2 is then run (Line 5). We note $δ_j$ the number of nodes discarded from $Θ$ by Alg. 2 at iteration $j$. It follows that the time cost of Alg. 2 at iteration $j$ is $O(1 + δ_j)$. The functions $κ, v, π$ are updated (Line 6) with a time cost $O(ζ \cdot c)$ where $ζ = 1$ if this update is local (i.e. if it relates to a number of nodes $O(1)$ in the modified part of the tree), and $ζ = n$ if this update is global. The update of $Θ_κ$ from $Θ$ and $κ$ is done with a time cost $O(ζ)$. If a non-trivial priority $π$ is considered, then $Θ_κ$ is maintained sorted with a time cost $O(ζ \cdot \log n)$. The time cost of iteration $j$ (Lines 4–7) is then $O(δ_j + ζ \cdot (c + ε \cdot \log n))$ with $ε = 0$ (resp. 1) if Alg. 3 is greedy (resp. non-greedy). The time cost for
<caption>Table 2</caption>

Time cost of Alg. 3 depending on the properties of the processing scheme: greedy algorithm ("Greedy"), local computation / update of $κ, v, π$ ("local"), unique / many processing(s) of each node ("Unicity")

<table><thead><tr><th>Greedy</th><th>Local</th><th>Unicity</th><th>Time cost</th></tr></thead><tbody><tr><td>✓</td><td>✓</td><td>✓</td><td>O(n · c)</td></tr><tr><td>✓</td><td>✓</td><td>✗</td><td>O((n + ℓ) · c)</td></tr><tr><td>✓</td><td>✗</td><td>✓</td><td>O(n² · c)</td></tr><tr><td>✓</td><td>✗</td><td>✗</td><td>O(n · ℓ · c)</td></tr><tr><td>✗</td><td>✓</td><td>✓</td><td>O(n · (c + log n))</td></tr><tr><td>✗</td><td>✓</td><td>✗</td><td>O((n + ℓ) · (c + log n))</td></tr><tr><td>✗</td><td>✗</td><td>✓</td><td>O(n² · (c + log n))</td></tr><tr><td>✗</td><td>✗</td><td>✗</td><td>O(n · ℓ · (c + log n))</td></tr></tbody></table>

the whole set of iterations of the while loop (Lines 3–7) is then $O(Δ + ℓ · ζ · (c + ε · log n))$. The time cost of Alg. 3 is then

$$ (7.3) \qquad \text{Cost}(\text{Alg. 3}) = O(Δ + (n + ℓ \cdot ζ) \cdot (c + ε \cdot \log n)) $$

where $Δ = O(n)$ is the number of nodes finally removed from the tree. Note that if each node $X$ is processed (at most) once by Alg. 2, we have $ℓ = O(n)$. Based on these facts, the various scenarios of time costs are given in Tab. 2.

**8. A unifying scheme.** In this section we show that the proposed algorithmic framework unifies the principal connected operators previously designed from morphological trees. By unifying, we mean that these previous algorithms can be expressed as occurrences of Alg. 3 with adequate (hyper)parameters.

**8.1. Connected filters from the component tree.** In Sects. 6–7, Func. Discard and Algs. 1–3 were given in the case of the tree of shapes. However, the discarding process of Func. Discard is also valid in the case of the component tree. More generally, the short range shifting of a node described in Alg. 1 is also valid for the component tree. We consider here the case of the max-tree. The symmetric case of the min-tree is left to the reader. The notions introduced in Sect. 6.1 remain valid and can even be simplified. Indeed, we have

$$ (8.1) \qquad C^+ = C \quad \text{and} \quad C^- = \emptyset $$

$$ (8.2) \qquad h^+ = \bigwedge \eta(C) \quad \text{and} \quad h^- = -\infty $$

$$ (8.3) \qquad \mu^+ = h^+ \quad \text{and} \quad \mu^- = h $$

$$ (8.4) \qquad \mathcal{M}^+ = \{C \in \mathcal{C} \mid \eta(C) = h^+\} \quad \text{and} \quad \mathcal{M}^- = \emptyset $$

In particular, $C^+, C^-, h^-$ and $\mathcal{M}^-$ are no longer required.

With these simplifications, the short range shifting of Alg. 1 holds for the max-tree. Note that we cannot have simultaneously $v = h^+$ and $v = h$. By contrast with the tree of shapes, Case (a) and Case (b) are then mutually exclusive: either $v = h^+ = \mu^+$ and the node $X$ absorbs its children nodes in $\mathcal{M}^+$, or $v = h = \mu^-$ and the node $X$ is absorbed by its parent node while all its children nodes are unaltered.
By side effect, the long range shifting of a node described in Alg. 2 is also valid for the component tree. It relies on successive calls of Alg. 1.

The connected operator construction pionneered in [8, 54, 29] can then be implemented with Alg. 3 as follows:

* the (parametric) criterion $\kappa$ is unchanged compared to the standard algorithm;

* the priority $\pi$ is defined so that the nodes $X \in \Theta$ that satisfy $\kappa(X)$ are processed by decreasing values $\eta(X)$;

* for each node $X \in \Theta$ that satisfies $\kappa(X)$ we set $v(X) = \eta(P)$ with $X \triangleleft P$;

* for each node $X$ to be discarded, we call Alg. 2, without update of $\kappa(P)$.

**8.2. Grain filtering from the tree of shapes.** A first approach for designing connected filters from trees of shapes was proposed by [13], leading to the notion of grain filtering. It consists of applying the connected operator construction initially designed for the component tree [54, 29, 8] in the case of the tree of shapes. In order to avoid defects such as those discussed in Sect. 5.3, the node discarding criterion $\kappa$ is considered in conjunction with a second criterion that only authorizes leaf nodes to be processed.

To express grain filtering, we can rely on the notions introduced in Sect. 6.1 with simplifications. Indeed for a leaf node $X$, we have

$$C(X) = C^{+} = C^{-} = M^{+} = M^{-} = \emptyset \qquad (8.5)$$

$$h^{+} = +\infty \quad \text{and} \quad h^{-} = -\infty \qquad (8.6)$$

$$\mu^{+} = \begin{cases} h & \text{if } h > 0 \\ +\infty & \text{if } h \le 0 \end{cases} \quad \text{and} \quad \mu^{-} = \begin{cases} h & \text{if } h < 0 \\ -\infty & \text{if } h \ge 0 \end{cases} \qquad (8.7)$$

Of course, With these simplifications, the short range shifting of Alg. 1 still holds for the tree of shapes. Note that we have neither $v = h^+$ nor $v = h^-$. In other words, Case (b) cannot occur. If $h > 0$ (resp. $h < 0$) and $v < \mu^+$ (resp. $\mu^- < v$), then we are in the case of Prop. 12. If $h > 0$ (resp. $h < 0$) and $v = \mu^+$ (resp. $v = \mu^-$), then we are in Case (a) and the node $X$ is absorbed by its parent node. The long range shifting of a node described in Alg. 2 is also valid in this simplified case. Once again it relies on successive calls of Alg. 1.

The grain filtering proposed by [13] can then be implemented with Alg. 3 as follows:

* the (parametric) criterion $\kappa$ is the same one that allows to discard the leaves of the tree of shapes;

* the leaves $X \in \Theta$ that satisfy $\kappa(X)$ are processed in any arbitrary order $\pi$;

* for each leaf $X \in \Theta$ that satisfies $\kappa(X)$ we set $v(X) = \eta(P)$ with $X \triangleleft P$;

* for each leaf $X$ to be discarded, we can call Alg. 2, with or without side effect on $\kappa(P)$, depending on the application.

**8.3. Global and local contrast transformations.** Finally, we observe that the proposed framework can also handle (global and local) contrast transformations. By contrast with Sects. 8.1–8.2, here, the expression of these contrast transformations as occurrences of the proposed scheme is algorithmically inefficient. We present this instantiation to emphasize the ability of the scheme to unify the usual connected operators.

A global or local contrast transformation (Sect. 5.1), can be implemented with two successive applications of Alg. 3. The first one is set as follows:
* the criterion $κ$ holds true for all the nodes;

* the nodes $X \in \Theta$ (that all satisfy $κ(X)$) are processed by decreasing value $η(X)$;

* for each node $X \in \Theta$ we set $v(X) = η(X) + τ - ⊥ + 1$.

(Note that this first step brings the values $η(X)$ in the interval $[T + 1, 2 \cdot T - \perp + 1]$, i.e. outside the interval $[\perp, T]$.) The second one is set as follows:

* the criterion $κ$ holds true for all the nodes;

* the nodes $X \in \Theta$ (that all satisfy $κ(X)$) are processed by increasing (new) value $η(X) + τ - \perp + 1$;

* for each node $X \in \Theta$ we set $v(X) = \tilde{η}(X)$ with $\tilde{η}(X) \in [\perp, T]$ the target height function induced by the contrast transformation.

In both steps, it is easily proved that the call of Alg. 2 leads to a unique call of Alg. 1 that falls in the case of Prop. 12.

Many standard image processing operators rely on pixel-wise computing based on the analysis of pixels neighbourhood. This paradigm holds both for linear and non-linear operators. Such operators are designed to act while guaranteeing the preservation of specific properties (e.g. integral value preservation for diffusion, non-creation of new values in morphological filters, etc.). However, their pixel-wise—i.e. local—behaviour generally forbids to preserve the global spatial/spectral structure of the image, which is a relevant property in certain application cases.

In this article, the proposed scheme allows to design connected operators that preserve the spatial and spectral structure of the image: no new contours are created, the signs of the gradient are preserved, and more generally the topographic structure of the image is unchanged since the tree of shapes of the output image is a simplified version of the tree of shapes of the input image. Revisiting standard pixel-wise filters in this framework opens the way to the design of connected versions of such filters, to benefit from the best of both worlds.

To reach that goal, the key-idea is to transpose the computation so that the processing unit is no longer the pixel of the image, but the node/region of its associated tree.

Let $Γ: I \to I$ be a standard pixel-wise operator. Let $I \in I$ be an image. We consider the action of $Γ$ on $I$. For any point $x \in U$, we generally have

$$721 \quad (8.8) \qquad \Gamma(I)(x) = \mathcal{F}(I, x, \mathcal{N}(x))$$

where $\mathcal{N}(x) \subset U$ is a spatial neighbourhood of pixel $x$, and $\mathcal{F}$ defines the behaviour of the operator, i.e. how the new value of the filtered image $Γ(I)$ at pixel $x$ depends on the information carried by the initial image $I$ in the neighbourhood $\mathcal{N}(x)$. Here, the primitive for defining the image $I$ is the pixel $x \in U$, and the primitive for processing it is the local neighbourhood $\mathcal{N}(x)$.

The tree of shapes $\tilde{\mathcal{I}}$—or more generally a morphological tree—of the image $I$ also describes the image, with a primitive which is no longer the pixel $x \in U$ but the node $X \in \Theta$. A tree being a graph structure, it also allows to define a notion of neighbourhood $\mathcal{N}(X)$. Typically, one may consider that

$$729 \quad (8.9) \qquad Y \in \mathcal{N}(X) \iff (X \triangleleft Y \lor Y \triangleleft X)$$

i.e. that the neighbours of a node in a tree are its parent and children nodes. Based on these considerations, we can rewrite the pixel-wise operator $Γ$ as a node-wise operator

$$732 \quad (8.10) \qquad \Gamma_{\Delta}(\tilde{\mathcal{I}})(X) = \mathcal{F}(\tilde{\mathcal{I}}, X, \mathcal{N}(X))$$
<figure><img src="image_16.png" /><figcaption>**Figure 14.** (a) Original image (image: $1.0 \cdot 10^6$ pixels; tree of shapes: $4.1 \cdot 10^5$ nodes). (b) Image obtained by applying 4 iterations of a pixel-wise mean filtering with a (3, 3) kernel (tree of shapes: $6.5 \cdot 10^4$ nodes). (c–d) Images obtained by node-wise mean filtering on the tree of shapes. We set $\kappa = \text{True}$ (i.e. $\Theta_{\kappa} = \Theta$). For any $X \in \Theta_{\kappa}$, the target height $v(X)$ is the mean value of X and its neighbouring nodes (parent, children). The priority $\pi$ is such that the tree is traversed from the root to the leaves. (e) Image obtained by applying 4 iterations of filtering (tree of shapes: $1.6 \cdot 10^5$ nodes). (f) Image obtained by applying 10 iterations of filtering (tree of shapes $6.7 \cdot 10^4$ nodes).</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>**Figure 15.** (a) Original image (Synchrotron microtomography, SOLEIL ANATOMIX, project #20211303, courtesy Sébastien Almagro) (image: $4.2 \cdot 10^6$ pixels, tree of shapes: $1.2 \cdot 10^6$ nodes). (b) Image obtained by applying 4 iterations of pixel-wise median filtering with a (3, 3) kernel (tree of shapes $3.5 \cdot 10^5$ nodes). (c–d) Images obtained by node-wise median filtering on the tree of shapes. We set $\kappa = \text{True}$ (i.e. $\Theta_{\kappa} = \Theta$). For $X \in \Theta_{\kappa}$, the target height $v(X)$ is the median value of X and its neighbouring nodes (parent, children). The priority $\pi$ is such that the tree is traversed from the root to the leaves. (e) Image obtained by applying 4 iterations of filtering (tree of shapes: $5.0 \cdot 10^5$ nodes). (f) Image obtained by applying 12 iterations of filtering (tree of shapes $1.6 \cdot 10^5$ nodes).</figcaption></figure>

where $\mathcal{F}$ defines the same behaviour as in Eq. (8.8). More precisely, $\Gamma_{\Delta}(\mathfrak{Z})(X)$ is designed to assign a new height $\hat{\eta}(X)$ to each node $X$, since $\eta(X)$ is the analogue of $\mathcal{I}(\mathbf{x})$, i.e. the spectral information that contributes to the definition of $\mathcal{I}$ from $\mathfrak{Z}$ (Eq. (3.8)).

**9. Towards connected versions of standard filters.** We can then derive a node-wise operator $\Gamma_{\Delta}$ acting on trees (Eq. (8.10)) from a pixel-wise operator $\Gamma$ acting on images (Eq. (8.8)). From the strategy formalized in Eqs. (4.1–4.2), we can then derive a connected operator $\Gamma_{\square}$ on images from this node-wise operator $\Gamma_{\Delta}$ on trees. In particular, $\Gamma_{\square}$ is then a connected version of the pixel-wise operator $\Gamma$.
<figure><img src="image_18.png" /><figcaption>**Figure 16.** Evolution of the SSIM (a) and LPIPS (b) measures vs. the number of nodes of the tree of shapes, for the images obtained by iteratively applying the pixel-wise and node-wise mean filters on the image of Fig. 14(a). The result images of Fig. 14(b–d) are depicted by diamonds.</figcaption></figure>

In Figs. 14–15, we provide examples for two standard operators, namely the mean filter (which alters contours and creates new values in its pixel-wise version) and the median filters (which does not create new values but alters contours in its pixel-wise version), respectively. In these figures, we successively apply pixel-wise (standard filter) (b) and node-wise (tree of shapes-based) (c–d) versions of the mean and median filters, respectively. In Figs. 16–17, The results are compared using the structural similarity measure (SSIM) [65] and the LPIPS perceptual similarity measure [69]. The node-wise versions of these filters effectively simplify the structure of the tree of shapes / image (by reducing the number of nodes / flat zones), while maintaining higher SSIM and LPIPS values compared to the pixel-wise versions for an equivalent number of nodes in the tree of shapes of the resulting images. The node-wise versions of these filters inherit the good properties of their pixel-wise counterparts. For instance, the node-wise median does not create new values, while the node-wise filter preserves the global intensity property of the image. These results highlight that simplification of the image is relevant by acting on its tree of shapes, in particular when it is important to preserve the structure of its content, which is not guaranteed by pixel-wise filtering. Of course, beyond these straightforward applications involving standard filters, the chosen filtering strategies can be tailored based on the requirements of the targeted applications. For instance, nodes could be selected based on geometric properties such as area size, compactness, intensity value, or other region-specific characteristics.

Nonetheless, pixel-wise operators and node-wise operators differ in various aspects. A non-exhaustive list of these differences includes:

* Pixels and pixel neighbourhoods have homogeneous sizes in pixel-wise operators $\Gamma$, while nodes and node neighbourhoods may be of heterogeneous sizes in node-based operators $\Gamma_\Delta$.

* The pixel space $\mathcal{U}$ is not modified by pixel-wise operators $\Gamma$, while the node space $\Theta$ may be progressively modified (in particular, reduced) by node-wise operators $\Gamma_\Delta$.

* All the pixels are processed independently (i.e. possibly in parallel) in pixel-wise operators $\Gamma$, while nodes have to be processed iteratively by node-wise operators $\Gamma_\Delta$.

In practice, these differences may induce challenges and pitfalls that have to be considered carefully in order to design unbiased connected operators $\Gamma_\square$ from usual pixel-wise operators $\Gamma$. This will
<figure><img src="image_19.png" /><figcaption>**Figure 17.** Evolution of the SSIM (a) and LPIPS (b) measures vs. the number of nodes of the tree of shapes, for the images obtained by iteratively applying the pixel-wise and node-wise median filters on the image of Fig. 15(a). The result images of Fig. 15(b–d) are depicted by diamonds.</figcaption></figure>

constitute our next work on this topic.

**10. Conclusion.** In this article, we proposed a generic scheme to design consistent connected operators based on the tree of shapes. By consistent, we mean that (1) the built connected operators do not alter the differential properties of the processed image (i.e. no gradient sign modification) and (2) the structure of the image with respect to its tree of shapes (i.e. to its topographic structure) is not altered. This generic scheme was also proved valid for the component tree, the other classical morphological tree used for image modeling. More generally, the proposed scheme unifies the principal connected operator construction frameworks based on morphological trees.

This scheme opens the way to the development of connected versions of standard pixel-based filters, which may allow to design of flat-zone-based versions of these filters. This constitutes our main perspective from a methodological point of view. Keeping in mind that the tree of shapes is not only an image processing tool, but also an image model, the proposed scheme may also be involved in the design of strategies for analyzing images, extracting their structural properties, and comparing them at various scales of detail. This opens the way to the involvement of the proposed scheme in domains where the morphological paradigms have already proved their relevance, for instance topological data analysis [7, 2] or deep learning [22, 62, 47].

REFERENCES

[1] J. BADEROT, M. DESVIGNES, L. CONDAT, AND M. DALLA MURA, *Tree of shapes cut for material segmentation guided by a design*, in ICASSP, 2020, pp. 2593–2597.

[2] G. BERTRAND, N. BOUTRY, AND L. NAJMAN, *Discrete Morse functions and watersheds*, J Math Imaging Vis, 65 (2023), pp. 787–801.

[3] S. BEUCHER AND C. LANTUÉJOUL, *Use of watersheds in contour detection*, in International Workshop on Image Processing, 1979.

[4] I. BORLIDO BARCELOS, F. DE CASTRO BELÉM, L. DE MELO JOÃO, Z. K. G. DO PATROCÍNIO JR., A. X. FALCÃO, AND S. J. FERZOLI GUIMARÃES, *A comprehensive review and new taxonomy on superpixel segmentation*, ACM Comput Surv, 56 (2024), pp. 200:1–200:39.
794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

820

821

822

823

824

825

826

827

828

829

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

[5] N. BOUTRY AND T. GÉRAUD, *A new matching algorithm between trees of shapes and its application to brain tumor segmentation*, in DGMM, 2021, pp. 67–78.

[6] N. BOUTRY, L. NAJMAN, AND T. GÉRAUD, *Topological properties of the first non-local digitally well-composed interpolation on $n-D$ cubical grids*, J Math Imaging Vis, 62 (2020), pp. 1256–1284.

[7] N. BOUTRY, L. NAJMAN, AND T. GÉRAUD, *Some equivalence relation between persistent homology and morphological dynamics*, J Math Imaging Vis, 64 (2022), pp. 807–824.

[8] E. J. BREEN AND R. JONES, *Attribute openings, thinnings, and granulometries*, Computer Vis Image Und, 64 (1996), pp. 377–389.

[9] E. CARLINET, S. CROZET, AND T. GÉRAUD, *The tree of shapes turned into a max-tree: A simple and efficient linear algorithm*, in ICIP, 2018, pp. 1488–1492.

[10] E. CARLINET AND T. GÉRAUD, *MToS: A tree of shapes for multivariate images*, IEEE T Image Process, 24 (2015), pp. 5330–5342.

[11] E. CARLINET AND T. GÉRAUD, *Morphological object picking based on the color tree of shapes*, in IPTA, 2015, pp. 125–130.

[12] V. CASELLES, B. COLL, AND J. MOREL, *Topographic maps and local contrast changes in natural images*, Int J Comput Vision, 33 (1999), pp. 5–27.

[13] V. CASELLES AND P. MONASSE, *Grain filters*, J Math Imaging Vis, 17 (2002), pp. 249–270.

[14] V. CASELLES AND P. MONASSE, *Geometric Description of Images as Topographic Maps*, Lecture Notes in Mathematics, Springer, 2010.

[15] G. CAVALLARO, M. DALLA MURA, J. A. BENEDIKTSSON, AND A. J. PLAZA, *Remote sensing image classification using attribute filters defined over the tree of shapes*, IEEE T Geosci Remote, 54 (2016), pp. 3899–3911.

[16] J. COUSTY, L. NAJMAN, Y. KENMOCHI, AND S. J. F. GUIMARÃES, *Hierarchical segmentations with graphs: Quasi-flat zones, minimum spanning trees, and saliency maps*, J Math Imaging Vis, 60 (2018), pp. 479–502.

[17] J. CRESPO, R. W. SCHAFER, J. SERRA, C. GRATIN, AND F. MEYER, *The flat zone approach: A general low-level region merging segmentation method*, Signal Process, 62 (1997), pp. 37–60.

[18] S. CROZET AND T. GÉRAUD, *A first parallel algorithm to compute the morphological tree of shapes of nD images*, in ICIP, 2014, pp. 2933–2937.

[19] D. J. DA SILVA, W. A. L. ALVES, A. MORIMITSU, C. F. GOBBER, AND R. F. HASHIMOTO, *Incremental bit-quads count in tree of shapes*, in ISMM, 2019, pp. 162–173.

[20] A. DUBROVINA, R. HERSHKOVITZ, AND R. KIMMEL, *Image editing using level set trees*, in ICIP, 2014, pp. 4442–4446.

[21] B. ESTEBAN, G. TOCHON, AND T. GÉRAUD, *Estimating the noise level function with the tree of shapes and non-parametric statistics*, in CAIP, 2019, pp. 377–388.

[22] D. L. FARFAN CABRERA, N. GOGIN, D. MORLAND, B. NAEGEL, D. PAPATHANASSIOU, AND N. PASSAT, *Segmentation of axillary and supraclavicular tumoral lymph nodes in PET/CT: A hybrid CNN/component-tree approach*, in ICPR, 2020, pp. 6672–6679.

[23] T. GÉRAUD, N. BOUTRY, S. CROZET, E. CARLINET, AND L. NAJMAN, *A proof of the tree of shapes in $n-D$, CoRR*, abs/2206.05109 (2022).

[24] T. GÉRAUD, E. CARLINET, AND S. CROZET, *Self-duality and digital topology: Links between the morphological tree of shapes and well-composed gray-level images*, in ISMM, 2015, pp. 573–584.

[25] T. GÉRAUD, E. CARLINET, S. CROZET, AND L. NAJMAN, *A quasi-linear algorithm to compute the tree of shapes of nD images*, in ISMM, 2013, pp. 98–110.

[26] C. F. GOBBER, R. F. HASHIMOTO, AND W. A. L. ALVES, *An efficient algorithm to update non-flat and incremental attributes in morphological trees*, Pattern Recognit Lett, 163 (2022), pp. 47–54.

[27] J. GROSS AND J. YELLEN, *Graph Theory and its applications*, CRC Press, 1998.

[28] L. GUIGUES, J.-P. COCQUEREZ, AND H. LE MEN, *Scale-sets image analysis*, Int J Comput Vision, 68 (2006), pp. 289–317.

[29] R. JONES, *Connected filtering and segmentation using component trees*, Computer Vis Image Und, 75 (1999), pp. 215–228.

[30] B. R. KIRAN AND J. SERRA, *Global-local optimizations by hierarchical cuts and climbing energies*, Pattern Recogn, 47 (2014), pp. 12–24.

[31] B. R. KIRAN AND J. SERRA, *Braids of partitions*, in ISMM, 2015, pp. 217–228.

[32] V. A. KOVALEVSKY, *Finite topology as applied to image analysis*, Comput Vision Graph, 46 (1989), pp. 141–161.

[33] C. KURTZ, B. NAEGEL, AND N. PASSAT, *Connected filtering based on multivalued component-trees*, IEEE T Image Process, 23 (2014), pp. 5152–5164.

[34] L. J. LATECKI, U. ECKHARDT, AND A. ROSENFELD, *Well-composed sets*, Computer Vis Image Und, 61 (1995), pp. 70–83.
848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

[35] J. MENDES FORTE, N. PASSAT, AND Y. KENMOCHI, *Building the topological tree of shapes from the tree of shapes*, in DGMM, 2024, pp. 271–285.

[36] J. MENDES FORTE, N. PASSAT, AND Y. KENMOCHI, *How to modify the tree of shapes of an image: Connected operators without gradient inversion*, in ICPR, 2024, pp. 1–18.

[37] P. MONASSE, *A root-to-leaf algorithm computing the tree of shapes of an image*, in RRPR, 2018, pp. 43–54.

[38] P. MONASSE AND F. GUICHARD, *Fast computation of a contrast-invariant image representation*, IEEE T Image Process, 9 (2000), pp. 860–872.

[39] P. MONASSE AND F. GUICHARD, *Scale-space from a level lines tree*, J Vis Commun Image R, 11 (2000), pp. 224–236.

[40] A. MONTANVERT, P. MEER, AND A. ROSENFELD, *Hierarchical image analysis using irregular tessellations*, IEEE T Pattern Anal, 13 (1991), pp. 307–316.

[41] L. NAJMAN AND M. SCHMITT, *Geodesic saliency of watershed contours and hierarchical segmentation*, IEEE T Pattern Anal, 18 (1996), pp. 1163–1173.

[42] N. PASSAT AND Y. KENMOCHI, *A topological tree of shapes*, in DGMM, 2022, pp. 221–235.

[43] N. PASSAT, J. MENDES FORTE, AND Y. KENMOCHI, *Morphological hierarchies: A unifying framework with new trees*, J Math Imaging Vis, 65 (2023), pp. 718–753.

[44] N. PASSAT AND B. NAEGEL, *Component-hypertrees for image segmentation*, in ISMM, 2011, pp. 284–295.

[45] N. PASSAT AND N. NAEGEL, *Component-trees and multivalued images: Structural properties*, J Math Imaging Vis, 49 (2014), pp. 37–50.

[46] B. PERRET, *Inf-structuring functions: A unifying theory of connections and connected operators*, J Math Imaging Vis, 51 (2015), pp. 171–194.

[47] B. PERRET AND J. COUSTY, *Component tree loss function: Definition and optimization*, in DGMM, 2022, pp. 248–260.

[48] B. PERRET, S. LEFÈVRE, C. COLLET, AND É. SLEZAK, *Hyperconnections and hierarchical representations for grayscale and multiband image processing*, IEEE T Image Process, 21 (2012), pp. 14–27.

[49] C. RONSE, *Partial partitions, partial connections and connective segmentation*, J Math Imaging Vis, 32 (2008), pp. 97–125.

[50] A. ROSENFELD, *Connectivity in digital pictures*, J ACM, 17 (1970), pp. 146–160.

[51] A. ROSENFELD, *Adjacency in digital pictures*, Inform Control, 26 (1974), pp. 24–33.

[52] A. ROSENFELD, *Digital topology*, Am Math Mon, 86 (1979), pp. 621–630.

[53] P. SALEMBIER AND L. GARRIDO, *Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval*, IEEE T Image Process, 9 (2000), pp. 561–576.

[54] P. SALEMBIER, A. OLIVERAS, AND L. GARRIDO, *Anti-extensive connected operators for image and sequence processing*, IEEE T Image Process, 7 (1998), pp. 555–570.

[55] P. SALEMBIER AND J. SERRA, *Flat zones filtering, connected operators, and filters by reconstruction*, IEEE T Image Process, 4 (1995), pp. 1153–1160.

[56] P. SALEMBIER AND M. H. F. WILKINSON, *Connected operators*, IEEE Signal Proc Mag, 26 (2009), pp. 136–157.

[57] J. SERRA, *Image Analysis and Mathematical Morphology. II: Theoretical Advances*, London, UK: Academic Press, 1988.

[58] J. SERRA, *Tutorial on connective morphology*, IEEE J Sel Top Signa, 6 (2012), pp. 739–752.

[59] P. SOILLE, *Constrained connectivity for hierarchical image decomposition and simplification*, IEEE T Pattern Anal, 30 (2008), pp. 1132–1145.

[60] Y. SONG AND A. ZHANG, *Monotonic tree*, in DGCI, 2002, pp. 114–123.

[61] Y. SONG AND A. ZHANG, *Analyzing scenery images by monotonic tree*, Multimedia Syst, 8 (2003), pp. 495–511.

[62] Q. TANG, B. DU, AND Y. XU, *Self-supervised learning based on max-tree representation for medical image segmentation*, in IJCNN, 2022, pp. 1–6.

[63] R. TAO AND J. QIAO, *Fast component tree computation for images of limited levels*, IEEE T Pattern Anal, 45 (2023), pp. 3059–3071.

[64] E. R. URBACH, N. J. BOERSMA, AND M. H. F. WILKINSON, *Vector-attribute filters*, in ISMM, 2005, pp. 95–104.

[65] Z. WANG, A. C. BOVIK, H. R. SHEIKH, AND E. P. SIMONCELLI, *Image quality assessment: From error visibility to structural similarity*, IEEE T Image Process, 13 (2004), pp. 600–612.

[66] M. H. F. WILKINSON, *Attribute-space connectivity and connected filters*, Image Vision Comput, 25 (2007), pp. 426–435.

[67] Y. XU, T. GÉRAUD, AND L. NAJMAN, *Connected filtering on tree-based shape-spaces*, IEEE T Pattern Anal, 38 (2016), pp. 1126–1140.

[68] Y. XU, T. GÉRAUD, AND L. NAJMAN, *Hierarchical image simplification and segmentation based on Mumford-Shah-
902 *salient level line selection*, Pattern Recogn Lett, 83 (2016), pp. 278–286.

903 [69] R. ZHANG, P. ISOLA, A. A. EFROS, E. SHECHTMAN, AND O. WANG, *The unreasonable effectiveness of deep features as a*

904 *perceptual metric*, in CVPR, 2018, pp. 586–595.