# Efficient connected alternating sequential filters based on component trees

Wonder Alves, Nicolas Passat, Dênnis José da Silva, Alexandre Morimitsu, Ronaldo F. Hashimoto

► To cite this version:

Wonder Alves, Nicolas Passat, Dênnis José da Silva, Alexandre Morimitsu, Ronaldo F. Hashimoto. Efficient connected alternating sequential filters based on component trees. International Conference on Discrete Geometry and Mathematical Morphology (DGMM), 2025, Groningen, Netherlands. pp.210-223, 10.1007/978-3-032-09544-2_15. hal-05163556v2

HAL Id: hal-05163556

https://hal.science/hal-05163556v2

Submitted on 7 Sep 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
# Efficient Connected Alternating Sequential Filters
## Based on Component Trees

Wonder A. L. Alves<fnref n="1" />, Nicolas Passat<fnref n="2" />, Dennis J. Silva<fnref n="2" />,<fnref n="3" />,<fnref n="4" />, Alexandre Morimitsu<fnref n="4" />, and
Ronaldo F. Hashimoto<fnref n="4" />

**Abstract.** Alternating Sequential Filters (ASFs) rely on the iterated application of openings and closings of increasing strength. Since connected openings and closings can be designed from the component tree, it is possible to define Connected ASFs (CASFs) by alternatively pruning the branches of the dual max- and min-trees of an image. The main drawback of this approach is that pruning one of the trees modifies not only the image but also the dual tree. Recomputing a component tree at each iteration of the process is computationally expensive. In this article, we show how a component tree can be efficiently updated (avoiding reconstruction) when its dual tree is pruned. We build upon this algorithmic scheme to propose a computationally efficient CASF algorithm.

**Keywords:** Alternating Sequential Filters · Connected operators · Component Tree · Algorithmics

# 1 Introduction

The component tree was popularized in the field of mathematical morphology at the end of the 90's [15]. This morphological tree is especially well fitted for modeling grey-level images. By encoding the inclusion relation on the connected components over the successive threshold sets of a grey-level image, it allows to represent in a lossless way the information carried by the image in a mixed spatial/spectral space. The strength of the component tree derives, on the one hand, from its low computational cost. This assertion holds both for its construction [1,3,6,8] and for its processing, in particular based on attribute filtering [2,9,19]. On the other hand, by pruning a max-tree (resp. min-tree), one can easily compute openings (resp. closings) [12] in the framework of connected operators [14].

Alternating Sequential Filters (ASFs), are a class of morphological operators that apply successive, alternated operations of openings and closings with increasing strength [10,11,16,17]. These openings/closings can be designed from the classical paradigm of structuring element. However, any valid opening/closing can be involved, and in particular those designed from component trees. Building ASFs from component trees leads

<footnote n="1">¹ Informatics and Knowledge Management Graduate Program,
Universidade Nove de Julho, São Paulo, Brazil</footnote>

<footnote n="2">² Université de Reims Champagne Ardenne, CRESTIC, Reims, France</footnote>

<footnote n="3">³ Université de Reims Champagne Ardenne, MEDyC, UMR CNRS 7369, Reims, France</footnote>

<footnote n="4">⁴ Department of Computer Science, Institute of Mathematics and Statistics,
Universidade de São Paulo, São Paulo, Brazil</footnote>
in particular to Connected ASFs (CASFs), which gather the behaviours of ASFs and connected operators. Building a CASF from component trees requires to process, at each iteration, either the max- or the min-tree of the current image and to prune that tree. This pruning modifies the image but also its dual tree, involved at the next iteration. Recomputing one of the trees at each step is indeed tractable, but this leads to low computational performance, as highlighted in [5].

In this article, we address the computational bottleneck of CASFs built from component trees. To reach that goal, we propose an algorithmic scheme that allows to update a component tree when its dual tree is pruned, thus avoiding its whole reconstruction. We then embed this scheme in the design of CASFs and we experimentally compare their computational cost to CASFs that reconstruct ex nihilo one tree at each iteration.

The remainder of this article is organized as follows. Section 2 recalls the basics of component trees. Section 3 presents the theoretical aspects of the update of the component tree, the induced component tree updating algorithms, and the CASF approach based on these updating algorithms. Section 4 presents experimental results. Section 5 concludes the article.

## 2 Basics on the component tree

A grey-level image is defined as a mapping $f: \mathcal{D} \to \mathbb{K}$. The domain $\mathcal{D}$ and the co-domain $\mathbb{K}$ are defined as finite sets. The elements of $\mathcal{D}$ are called points. The elements of $\mathbb{K}$ are called values. Without loss of generality, we set $\mathbb{K} = [[0, K]] \subset \mathbb{Z}$, namely the interval of $K + 1$ integers from 0 to $K$ and we assume that $f(p) \neq K$ for any $p \in \mathcal{D}$. The definition of a component tree only requires that the domain $\mathcal{D}$ be endowed with a non-directed graph structure. However, since we will simultaneously work with the max- and min-trees, we consider here stronger hypotheses. In particular, we assume that $\mathcal{D}$ is endowed with a topological structure. For the sake of readability, in this article, we consider $\mathcal{D}$ as a connected subset of $\mathbb{Z}^2$ endowed with the digital topology [13]. In particular, the points of $\mathbb{Z}^2$ are linked by the dual 4- and 8-adjacencies, denoted by $\sim_4$ and $\sim_8$, respectively. If $\alpha$ denotes an adjacency, we denote its dual as $\bar{\alpha}$. These $\alpha$-adjacencies induce the notions of $\alpha$-connectedness. (Note that for the sake of concision, the illustrative figures will be proposed for $\mathcal{D} \subset \mathbb{Z}$ instead of $\mathbb{Z}^2$.)

A tree is an acyclic, connected graph $\mathcal{T} = (V(\mathcal{T}), E(\mathcal{T}))$. The elements of $V(\mathcal{T})$ are called nodes. The (directed) elements of $E(\mathcal{T})$ are called edges. A tree $\mathcal{T}$ supports two basic operations on any node $\tau \in V(\mathcal{T})$:

$$ \text{parent}(\mathcal{T}, \tau) = \tau_p \iff (\tau, \tau_p) \in E(\mathcal{T}) \quad (1) $$

$$ \text{children}(\mathcal{T}, \tau) = \{\tau_c \in V(\mathcal{T}) \mid (\tau_c, \tau) \in E(\mathcal{T})\} \quad (2) $$

From these two operations, we define the root and the leaves of the tree $\mathcal{T}$ as:

$$ \text{root}(\mathcal{T}) = \tau_R \iff \forall \tau \in V(\mathcal{T}), \tau \neq \text{parent}(\mathcal{T}, \tau_R) \quad (3) $$

$$ \text{leaves}(\mathcal{T}) = \{\tau_L \in V(\mathcal{T}) \mid \text{children}(\mathcal{T}, \tau_L) = \emptyset\} \quad (4) $$

The component tree is a tree obtained from the connected components (CCs) of the threshold sets of $f$ and the inclusion relations between these CCs. Let $k \in \mathbb{K}$. We define
the upper and lower threshold sets at value k as:

$$ \mathcal{X}_k(f) = \{p \in \mathcal{D} | f(p) \geq k\} \qquad (5) $$

$$ \mathcal{X}^k(f) = \{p \in \mathcal{D} | f(p) < k\} \qquad (6) $$

The image f can be reconstructed from either the family of lower or upper level sets, i.e. $\forall p \in \mathcal{D}$ we have:

$$ f(p) = \sup\{k | p \in \mathcal{X}_k(f)\} = \inf\{k-1 | p \in \mathcal{X}^k(f)\} \qquad (7) $$

Each nonempty threshold set of f is partitioned into CCs. By gathering all these CCs, we define:

$$ \mathcal{U}(f) = \{\tau \in \mathcal{CC}(\mathcal{X}_k(f), \alpha) | k \in \mathbb{K}\} \qquad (8) $$

$$ \mathcal{L}(f) = \{\tau \in \mathcal{CC}(\mathcal{X}^k(f), \bar{\alpha}) | k \in \mathbb{K}\} \qquad (9) $$

where $\mathcal{CC}(\mathcal{X}, \alpha)$ denotes the set of CCs of $\mathcal{X}$ induced with respect to the chosen adjacency $\alpha$.

The CCs of upper and lower level sets and the inclusion relation $\subseteq$ on sets induce two dual trees [9,15] called component trees. Formally a component tree of an image f is defined as a tree $\mathcal{T}_f = (V(\mathcal{T}_f), E(\mathcal{T}_f))$ such that:

$$ V(\mathcal{T}_f) = \mathcal{U}(f) \text{ or } \mathcal{L}(f) \qquad (10) $$

$$ E(\mathcal{T}_f) = \{(\tau_C, \tau_P) \in V(\mathcal{T}_f) \times V(\mathcal{T}_f) | \tau_C \subset \tau_P \wedge \nexists \tau \in V(\mathcal{T}_f), \tau_C \subset \tau \subset \tau_P\} \qquad (11) $$

A component tree $\mathcal{T}_f$ of the image f can be completely represented by a compact, non-redundant data structure [4]. In particular, we denote by $\text{flat}(\mathcal{T}_f, p)$ the smallest CC of $V(\mathcal{T}_f)$ containing p. We also say that $p \in \mathcal{D}$ is a compact node point (CNP) of $\text{flat}(\mathcal{T}_f, p)$. For any node $\tau \in V(\mathcal{T}_f)$, we set:

$$ \text{compact}(\mathcal{T}_f, \tau) = \{p \in \mathcal{D} | \tau = \text{flat}(\mathcal{T}_f, p)\} \qquad (12) $$

the set composed of the CNPs of $\tau$. Note that, from Eq. (12), for any node $\tau \in V(\mathcal{T}_f)$,

$$ p \in \text{compact}(\mathcal{T}_f, \tau) \iff \tau = \text{flat}(\mathcal{T}_f, p). \qquad (13) $$

The compact representation of a component tree $\mathcal{T}_f = (V(\mathcal{T}_f), E(\mathcal{T}_f))$ is denoted by $\widehat{\mathcal{T}}_f = (\widehat{V}(\mathcal{T}_f), \widehat{E}(\mathcal{T}_f))$ with:

$$ \widehat{V}(\mathcal{T}_f) = \{\text{compact}(\mathcal{T}_f, \tau) | \tau \in V(\mathcal{T}_f)\} \qquad (14) $$

$$ \widehat{E}(\mathcal{T}_f) = \{(\text{compact}(\mathcal{T}_f, \tau_C), \text{compact}(\mathcal{T}_f, \tau_P)) | (\tau_C, \tau_P) \in E(\mathcal{T}_f)\} \qquad (15) $$

Since $\text{compact}(\mathcal{T}_f, \tau) \neq \emptyset$ for any $\tau \in V(\mathcal{T}_f)$, the sets $\widehat{V}(\mathcal{T}_f)$ and $V(\mathcal{T}_f)$ are in bijection. This bijection induces a trivial isomorphism between $\mathcal{T}_f = (V(\mathcal{T}_f), E(\mathcal{T}_f))$ and $\widehat{\mathcal{T}}_f = (\widehat{V}(\mathcal{T}_f), \widehat{E}(\mathcal{T}_f))$.

In practice, our algorithms will act on compact component trees $\widehat{\mathcal{T}}_f = (\widehat{V}(\mathcal{T}_f), \widehat{E}(\mathcal{T}_f))$. These compact representations of component trees for upper and lower level sets are
called max-tree and min-tree [15] and denoted by $\widehat{T}_f^{\max}$ and $\widehat{T}_f^{\min}$, respectively. For the sake of simplicity, we will also refer to the max-tree (resp. min-tree) as the component tree of upper (resp. lower) level sets.

Based on Eq. (7), we consider the mapping $level(T_f, \cdot) : V(T_f) \to \mathbb{K}$ from CCs of a component tree $T_f$ to the grey-level values. This mapping is defined so that, for any node $\tau \in V(T_f)$, we have $level(T_f, \tau) = f(p)$ with $p \in \text{compact}(T_f, \tau)$. From Eq. (13), we have $\tau = \text{flat}(T_f, p)$. Based on this mapping, the image $f$ can be reconstructed from its tree $T_f$ by setting, for all $p \in \mathcal{D}$:

$$f(p) = level(T_f, flat(T_f, p)) \qquad (16)$$

# 3 Method

In this section, we describe our approach to efficiently building CASFs using component trees. To this end, we first build the max- and min-trees of the image. Then, we alternatively remove a leaf from one of them and update the other, repeating this process until no further leaf needs to be removed. We first present theoretical results in Subsection 3.1. Then we describe the induced algorithms in Subsection 3.2.

## 3.1 Theory

We first investigate how the max-tree evolves when removing a leaf node from the min-tree, as illustrated in Fig. 1, which serves as a running example throughout this theoretical section. For interactive exploration and a clearer illustration of the method, we provide a dedicated notebook<fnref n="5" />.

For a given grey-level image $f: \mathcal{D} \to \mathbb{K}$, we assume that its max-tree $T_f^{\max}$ is built for a given $\alpha$-adjacency ($\alpha = 4$ or 8), while its min-tree $T_f^{\min}$ is built for the dual $\bar{\alpha}$-adjacency. We set:

- $L \in V(T_f^{\min})$, a leaf node in the min-tree $T_f^{\min}$;

- $T_g^{\min}$, the min-tree obtained after pruning the leaf node $L$;

- $g: \mathcal{D} \to \mathbb{K}$, the image reconstructed from the pruned min-tree $T_g^{\min}$;

- $T_g^{\max}$ the max-tree of the image $g$.

The problem that we consider is formulated as follows.

**Problem 1** How to modify $T_f^{\max}$ to obtain $T_g^{\max}$?

By definition, the leaf node $L$ is $\bar{\alpha}$-connected. If $\bar{\alpha} = 4$, then $L$ is 4-connected and then also 8-connected. It follows that $L$ is included in a unique node in both max-trees $T_f^{\max}$ and $T_g^{\max}$.

If $\bar{\alpha} = 8$, then $L$ may be composed of many 4-connected components. If so, let us choose $L_1, L_2$ two distinct 4-connected components of $L$ which are 8-connected. Then, there exists $p_1 \in L_1$ and $p_2 \in L_2$ such that $p_1 \sim_8 p_2$. Let $q$ be such that $p_1 \sim_4 q \sim_4 p_2$.

<footnote n="5">⁵ Code available at https://github.com/wonderalexandre/MorphoTreeAdjust</footnote>
We have $q \notin L$, otherwise $L_1, L_2$ would be 4-connected. By definition, we have $q \notin L$, and, since $L$ is a leaf node of the min-tree, we have $f(q) > f(p_1) = f(p_2)$. It follows that $p_1, p_2, q$ belong to a same node in the max-trees $\mathcal{T}_f^{\max}$ and $\mathcal{T}_g^{\max}$. By induction, it comes that $L$ is included in a unique node in both max-trees $\mathcal{T}_f^{\max}$ and $\mathcal{T}_g^{\max}$. This justifies the following result.

**Proposition 1.** All the points in the node $L$ are compact node points of the two nodes $\text{flat}(\mathcal{T}_f^{\max}, p)$ and $\text{flat}(\mathcal{T}_g^{\max}, p)$ with $p \in L$.

Let $\tau_L$ denote the node $\text{flat}(\mathcal{T}_f^{\max}, p)$. By removing the leaf node $L$ from the min-tree $\mathcal{T}_f^{\min}$, the points $p \in L$ are transferred from the node $L$ to the node $\text{parent}(\mathcal{T}_f^{\min}, L)$. Doing so, they are assigned the new value $g(p) = \text{level}(\mathcal{T}_f^{\min}, \text{parent}(\mathcal{T}_f^{\min}, L)) > \text{level}(\mathcal{T}_f^{\min}, L) = f(p)$. Let $a = f(p)$ and $b = g(p)$.

## Node updating

We first investigate the differences between the nodes of the max-trees $\mathcal{T}_f^{\max}$ and $\mathcal{T}_g^{\max}$.

Let $\tau$ be a node of $\mathcal{T}_f^{\max}$ such that (i) $\text{level}(\mathcal{T}_f^{\max}, \tau) \notin [[a, b]]$ or (ii) $\tau$ is not $\alpha$-connected to $L$. If (i) holds, then the CC associated to $\tau$ is not affected by modifying the value of $L$ from $a$ to $b$, since the threshold sets of $f$ and $g$ are the same outside the interval $[[a, b]]$ (see nodes $\tau_R$ and $\tau_I$ in Fig. 1(c)). If (ii) holds, then the CC associated to $\tau$ is not affected by modifying the value of $L$, since $L$ is not part of this CC (see nodes $\tau_{III}$ and $\tau_V$ in Fig. 1(c)). This justifies the following result.

**Proposition 2.** Let $\tau \in V(\mathcal{T}_f^{\max})$. If $\text{level}(\mathcal{T}_f^{\max}, \tau) \notin [[a, b]]$ or $\tau$ is not $\alpha$-connected to $L$, then we have $\tau \in V(\mathcal{T}_g^{\max})$, with $\text{compact}(\mathcal{T}_g^{\max}, \tau) = \text{compact}(\mathcal{T}_f^{\max}, \tau)$ and $\text{level}(\mathcal{T}_g^{\max}, \tau) = \text{level}(\mathcal{T}_f^{\max}, \tau)$.

Let us now focus on the other nodes of $\mathcal{T}_f^{\max}$. We denote by $\mathcal{F}$ the set of all the nodes $\tau$ of $\mathcal{T}_f^{\max}$ such that $\text{level}(\mathcal{T}_f^{\max}, \tau) \in [[a, b]]$ and $\tau$ is $\alpha$-connected to $L$. The set $\mathcal{F}$ is not empty, since $\text{level}(\mathcal{T}_f^{\max}, \tau_L) = a$ and $L \subseteq \tau_L$. The set $\mathcal{F}$ can be subdivided into subsets $F_\lambda = \{\tau \in \mathcal{F} \mid \text{level}(\mathcal{T}_f^{\max}, \tau) = \lambda\}$ for $\lambda \in [[a, b]]$ (see sets $F_2, F_3$ and $F_5$ in Fig. 1(c)). We have $\cup_{\lambda \in [[a,b]]} F_\lambda = \mathcal{F}$ and, for any distinct $k, \ell \in [[a, b]]$, we have $F_k \cap F_\ell = \emptyset$. However, $\{F_\lambda\}_{\lambda \in [[a,b]]}$ is not necessarily a partition of $\mathcal{F}$, since we may have $F_\lambda = \emptyset$ for certain $\lambda \in [[a+1, b]]$ (see $F_4$ in Fig. 1(c)).

We also consider the additional set $F_{>b}$ composed of nodes $\tau$ of $\mathcal{T}_f^{\max}$ such that $\text{level}(\mathcal{T}_f^{\max}, \tau) > b$, $\tau$ is $\alpha$-connected to $L$ and $\text{parent}(\mathcal{T}_f^{\max}, \tau) \in \mathcal{F} \setminus F_b$ (see node $\tau_I$ in Fig. 1(c)).

We consider the following three (mutually exclusive) cases.

- $\lambda = b$. Each $\tau \in F_b \cup F_{>b}$ is an $\alpha$-connected component of $X_b(f)$. Since the value of $L$ is modified so that $g(p) = b$ for any $p \in L$, we have the following:

$$ \tau_b = L \cup \bigcup F_b \cup \bigcup F_{>b} \qquad (17) $$

is an $\alpha$-connected component of $X_b(g)$, and thus it is a node of the max-tree $\mathcal{T}_g^{\max}$. We have $\text{compact}(\mathcal{T}_g^{\max}, \tau_b) = L \cup \bigcup_{\tau \in F_b} \text{compact}(\mathcal{T}_f^{\max}, \tau)$ and $\text{level}(\mathcal{T}_g^{\max}, \tau_b) = b$ (see $\tau_5$ in Fig. 1(d)).
<figure><img src="image_2.png" /><figcaption>Fig. 1. Illustration of a 1D image transformation and its associated trees, with a grey-level bar indicating the level of each node. The CNPs are shown in red, while the non-CNPs are shown in black. (a) The original image f and the resulting image g, obtained by reconstructing the min-tree of f after pruning node L (highlighted with a blue box in (b)). Pixels affected by the pruning of the min-tree are shown in blue. (b) The min-tree $\mathcal{T}_f^{\min}$ of the image f, with the leaf node L highlighted by a blue box. (c) The max-tree $\mathcal{T}_f^{\max}$ of the image f, highlighting the node $\tau_L$ and the sets $F_2, F_3, F_5$, and $F_{>b}$, which are affected by the pruning of L in the min-tree. (d) The max-tree $\mathcal{T}_g^{\max}$ of the reconstructed image g, highlighting the new nodes $\tau_2, \tau_3$, and $\tau_5$, which are defined from the sets $F_2, F_3$, and $F_5$.</figcaption></figure>

$-\lambda \in \llbracket a+1, b-1 \rrbracket$ with $F_\lambda \neq \emptyset$. Each $\tau \in F_\lambda$ is an $\alpha$-connected component of $\chi_\lambda(f)$. Let $\sigma = \min\{\tilde{\lambda} \in \llbracket \lambda+1, b \rrbracket \mid F_{\tilde{\lambda}} \neq \emptyset\}$. By induction, it follows that

$$ \tau_{\lambda} = \tau_{\sigma} \cup \bigcup F_{\lambda} \qquad (18) $$
is an α-connected component of $\mathcal{X}_\lambda(g)$, and thus it is a node of the max-tree $\mathcal{T}_g^{\max}$.
We have $\text{compact}(\mathcal{T}_g^{\max}, \tau_\lambda) = \bigcup_{\tau \in \mathcal{F}_\lambda} \text{compact}(\mathcal{T}_f^{\max}, \tau)$ and $\text{level}(\mathcal{T}_g^{\max}, \tau_\lambda) = \lambda$
(see $\tau_3$ in Fig. 1(d)).

$$ - \lambda = a. \text{ We have } F_a = \{\tau_L\}. \text{ By definition,} \tag{19} $$
$$ \tau_a = \tau_L $$

is an α-connected component of $\mathcal{X}_a(g)$, and thus it is a node of the max-tree $\mathcal{T}_g^{\max}$.
Two (mutually exclusive) subcases can occur.

* $\text{compact}(\mathcal{T}_f^{\max}, \tau_L) \supset L$. In that case, $\tau_a$ is not an α-connected component of $\mathcal{X}_{a+1}(g)$, and we then have $\text{compact}(\mathcal{T}_g^{\max}, \tau_a) = \text{compact}(\mathcal{T}_f^{\max}, \tau_L) \setminus L$ and $\text{level}(\mathcal{T}_g^{\max}, \tau_a) = a$ (see $\tau_2$ in Fig. 1(d)).

* $\text{compact}(\mathcal{T}_f^{\max}, \tau_L) = L$. In that case, $\tau_a$ is an α-connected component of $\mathcal{X}_\lambda(g)$ for any $a \le \lambda \le \lambda^+$ with $\lambda^+ = \min\{\tilde{\lambda} \in \llbracket a+1, b \rrbracket \mid F_{\tilde{\lambda}} \ne \emptyset\}$, and we then have $\tau_a = \tau_{\lambda^+} = \tau_L$, $\text{compact}(\mathcal{T}_g^{\max}, \tau_a) = \text{compact}(\mathcal{T}_g^{\max}, \tau_{\lambda^+})$, and $\text{level}(\mathcal{T}_g^{\max}, \tau_a) = \text{level}(\mathcal{T}_g^{\max}, \tau_{\lambda^+})$.

Let $\tilde{\mathcal{F}} = \{\tau_\lambda \mid \lambda \in \llbracket a, b \rrbracket \wedge F_\lambda \ne \emptyset\}$ (see $\tau_5$, $\tau_3$, and $\tau_2$ in Fig. 1(d)). The previous discussion justifies the following result.

**Proposition 3.** The set $\tilde{\mathcal{F}}$ in the max-tree $\mathcal{T}_f^{\max}$ is replaced with the set $\tilde{\mathcal{F}}$ in the max-tree $\mathcal{T}_g^{\max}$.

From Prop. 2–3, we can determine the set of nodes of the new max-tree $\mathcal{T}_g^{\max}$ from the former max-tree $\mathcal{T}_f^{\max}$.

## Edge updating

We now deal with the definition of the parent relation in $\mathcal{T}_g^{\max}$ from the parent relation in $\mathcal{T}_f^{\max}$.

Let $\tau_C$ be a node of $\mathcal{T}_g^{\max}$ such that $\tau_C \ne \text{root}(\mathcal{T}_g^{\max})$. Hence, we have $\tau_C \ne \text{root}(\mathcal{T}_f^{\max})$. The following two cases (mutually exclusive) can occur.

- $\tau_C \notin \tilde{\mathcal{F}}$. This implies $\tau_C \in V(\mathcal{T}_f^{\max})$. Let $\tau_P = \text{parent}(\mathcal{T}_f^{\max}, \tau_C)$. Two subcases (mutually exclusive) can occur.

* $\tau_P \notin \mathcal{F}$. It follows from Prop. 2 that we have $\text{parent}(\mathcal{T}_g^{\max}, \tau_C) = \tau_P$ (see node $\tau_V$ in Fig. 1(d)).

* $\tau_P \in \mathcal{F}$. Two subcases (mutually exclusive) can occur.

* $\tau_C \in F_{>b}$. From Prop. 3 and the related discussion, we have $\tau_C \subset \tau_b$. It follows that $\text{parent}(\mathcal{T}_g^{\max}, \tau_C) = \tau_b$ (see node $\tau_I$ in Fig. 1(c-d)).

* $\tau_C \notin F_{>b}$. We have $\tau_C \subset \tau_{\text{level}(\mathcal{T}_f^{\max}, \tau_P)}$. Let us suppose that there exists $\tau \in V(\mathcal{T}_g^{\max})$ such that $\tau_C \subset \tau \subset \tau_P$. We cannot have $\tau \in V(\mathcal{T}_f^{\max})$, otherwise $\tau_P \ne \text{parent}(\mathcal{T}_f^{\max}, \tau_C)$. Then we have $\tau = \tau_\lambda \in \tilde{\mathcal{F}}$ with $\text{level}(\mathcal{T}_g^{\max}, \tau_P) < \lambda < \text{level}(\mathcal{T}_g^{\max}, \tau_C)$, which implies that there exists $\tau' \in V(\mathcal{T}_f^{\max})$ such that $\text{level}(\mathcal{T}_g^{\max}, \tau') = \lambda$ and then $\tau_C \subset \tau' \subset \tau_P$, in contradiction with $\tau_P = \text{parent}(\mathcal{T}_f^{\max}, \tau_C)$. It follows that we have $\text{parent}(\mathcal{T}_g^{\max}, \tau_C) = \tau_{\text{level}(\mathcal{T}_f^{\max}, \tau_P)}$ (see node $\tau_{III}$ in Fig. 1(c-d)).
- $\tau_C \in \tilde{\mathcal{F}}$. Two subcases (mutually exclusive) can occur.

* $\tau_C \neq \tau_a$. We have $\text{parent}(\mathcal{T}_g^{\max}, \tau_C) = \tau_{\lambda^-}$ with $\lambda^- = \max\{\tilde{\lambda} \in \llbracket a, \lambda-1 \rrbracket | F_{\tilde{\lambda}} \neq \emptyset\}$ (see nodes $\tau_3$ and $\tau_5$ in Fig. 1(d)).

* $\tau_C = \tau_a$. This implies $\tau_C \in V(\mathcal{T}_f^{\max})$. With the same notations as above, we have $\text{parent}(\mathcal{T}_g^{\max}, \tau_C) = \tau_P$ (see node $\tau_2$ in Fig. 1(d)).

The previous discussion justifies the following result.

**Proposition 4.** Let $\tau_C \in V(\mathcal{T}_g^{\max})$ such that $\tau_C \neq \text{root}(\mathcal{T}_g^{\max})$. The relation parent is unchanged from $\mathcal{T}_f^{\max}$ to $\mathcal{T}_g^{\max}$, except in the following three cases:

$$ (\tau_C \in F_{>b}) \wedge (\tau_P \in \mathcal{F}) \Rightarrow \text{parent}(\mathcal{T}_g^{\max}, \tau_C) = \tau_b \quad (20) $$

$$ (\tau_C \notin F_{>b} \cup \tilde{\mathcal{F}}) \wedge (\tau_P \in \mathcal{F}) \Rightarrow \text{parent}(\mathcal{T}_g^{\max}, \tau_C) = \tau_{\text{level}(\mathcal{T}_f^{\max}, \tau_P)} \quad (21) $$

$$ (\tau_C \in \tilde{\mathcal{F}} \setminus \{\tau_a\}) \Rightarrow \text{parent}(\mathcal{T}_g^{\max}, \tau_C) = \tau_{\lambda^-} \quad (22) $$

## 3.2 Algorithms

We decompose the proposed method in two parts: first, the updating of the trees after a leaf removal operation; second the computation of the CASF.

### Tree updating

We propose an algorithmic scheme to tackle Problem 1. For the sake of readability, this scheme is split into three algorithms, which are direct transcriptions of the results established in Section 3.1:

- the determination of the nodes to update (Alg. 1);

- the update of these nodes (Alg. 2);

- the induced update the edges (Alg. 3).

In the algorithms, we adopt the following notation: “$a := b$” means that $b$ is assigned to $a$; “$a \leftarrow b$” means that $b$ is added to $a$; “$a \rightarrow b$” means that $b$ is removed from $a$.

The tree updating procedure is designed for the computation of CASF, that relies on the removal of regions based on size criterion. It is therefore relevant to compute and maintain an up-to-date area attribute for each node in the two component trees. The initial computation incurs no additional cost when building the component trees. The update from $\mathcal{T}_f^{\max}$ to $\mathcal{T}_g^{\max}$ only affects the new nodes $\tau_\lambda$ in $\mathcal{T}_g^{\max}$, which can be handled in a bottom-up fashion, in linear time.
<caption>**Algorithm 1:** Building $\mathcal{F}$ and $F_{>b}$</caption>

**Input:** $f: \mathcal{D} \to \mathbb{K}$
**Input:** $\mathcal{T}_f^{\max} = (V(\mathcal{T}_f^{\max}), E(\mathcal{T}_f^{\max}))$ denoted by $\mathcal{T}_f$ (considered wrt $\alpha$-adjacency)
**Input:** $\mathcal{T}_f^{\min} = (V(\mathcal{T}_f^{\min}), E(\mathcal{T}_f^{\min}))$ and $L \in \text{leaves}(\mathcal{T}_f^{\min})$
**Notation:** $a := \text{level}(\mathcal{T}_f^{\min}, L)$ and $b := \text{level}(\mathcal{T}_f^{\min}, \text{parent}(\mathcal{T}_f^{\min}, L))$
**Output:** $\mathcal{F} = \{F_\lambda | a \le \lambda \le b\}$ and $F_{>b}$
1 **foreach** $\lambda \in [a, b]$ **do**
2 &nbsp;&nbsp;&nbsp; $F_\lambda := \emptyset$
3 &nbsp;&nbsp;&nbsp; $Q := \{q \in \mathcal{D} \mid L \mid \exists p \in L, q \sim_a p\}$
4 **foreach** $q \in Q$ **do**
5 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if $a \le f(q) \le b$ then $F_{f(q)} \leftarrow \text{flat}(\mathcal{T}_f, q)$
6 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if $b < f(q)$ then $F_{>b} \leftarrow \text{flat}(\mathcal{T}_f, q)$
7 **while** $b \le \max\{\text{level}(\mathcal{T}_f, \text{parent}(\mathcal{T}_f, \tau)) \mid \tau \in F_{>b}\}$ **do**
8 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $\tau := \arg\max_{g \in F_{>b}} \{\text{level}(\mathcal{T}_f, \text{parent}(\mathcal{T}_f, \tau))\}$
9 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $F_{>b} \to \tau$
10 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if $b < \text{level}(\mathcal{T}_f, \text{parent}(\mathcal{T}_f, \tau))$ then $F_{>b} \leftarrow \text{parent}(\mathcal{T}_f, \tau)$
11 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if $b = \text{level}(\mathcal{T}_f, \text{parent}(\mathcal{T}_f, \tau))$ then $F_b \leftarrow \text{parent}(\mathcal{T}_f, \tau)$
12 **foreach** $\tau \in F_{>b}$ **do**
13 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $F_{\text{level}(\text{parent}(\mathcal{T}_f, \tau))} \leftarrow \text{parent}(\mathcal{T}_f, \tau)$
14 **for** $\lambda$ **from** $b$ **to** $a+1$ **do**
15 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; **foreach** $\tau \in F_\lambda$ **do**
16 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $F_{\text{level}(\mathcal{T}_f, \text{parent}(\mathcal{T}_f, \tau))} \leftarrow \text{parent}(\mathcal{T}_f, \tau)$

<caption>**Algorithm 2:** Building $V(\mathcal{T}_g^{\max})$</caption>

**Input:** $V(\mathcal{T}_g^{\max})$ with $\mathcal{T}_g^{\max}$ denoted by $\mathcal{T}_f$
**Input:** $\mathcal{F} = \{F_\lambda | a \le \lambda \le b\}$
**Output:** $V(\mathcal{T}_g^{\max})$ with $\mathcal{T}_g^{\max}$ denoted by $\mathcal{T}_g$
1 $V(\mathcal{T}_g) := V(\mathcal{T}_f) \cup \bigcup_{\lambda=a}^b F_\lambda$
2 $V(\mathcal{T}_g) \leftarrow \tau_b$
3 $\text{level}(\mathcal{T}_g, \tau_b) := b$
4 $\text{compact}(\mathcal{T}_g, \tau_b) := L$
5 **foreach** $\tau \in F_b$ **do**
6 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $\text{compact}(\mathcal{T}_g, \tau_b) := \text{compact}(\mathcal{T}_g, \tau_b) \cup \text{compact}(\mathcal{T}_f, \tau)$
7 **foreach** $\lambda \in [a+1, b-1]$ **such that** $F_\lambda \ne \emptyset$ **do**
8 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $V(\mathcal{T}_g) \leftarrow \tau_\lambda$
9 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $\text{level}(\mathcal{T}_g, \tau_\lambda) := \lambda$
10 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $\text{compact}(\mathcal{T}_g, \tau_\lambda) := \emptyset$
11 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; **foreach** $\tau \in F_\lambda$ **do**
12 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $\text{compact}(\mathcal{T}_g, \tau_\lambda) := \text{compact}(\mathcal{T}_g, \tau_\lambda) \cup \text{compact}(\mathcal{T}_f, \tau)$
13 $F_\lambda \to \tau_L$
14 **if** $\text{compact}(\mathcal{T}_f, \tau_L) \supset L$ **then**
15 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $V(\mathcal{T}_g) \leftarrow \tau_a$
16 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $\text{level}(\mathcal{T}_g, \tau_a) := a$
17 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; $\text{compact}(\mathcal{T}_g, \tau_a) := \text{compact}(\mathcal{T}_f, \tau_L) \setminus L$
<caption>**Algorithm 3:** Building $E(\mathcal{T}_g^{\max})$</caption>

**Input:** $\mathcal{T}_f^{\max} = (V(\mathcal{T}_f^{\max}), E(\mathcal{T}_f^{\max}))$ denoted by $\mathcal{T}_f$ with $L$ and $\tau_L$ known
**Input:** $\mathcal{F} = \{F_\lambda | a \le \lambda \le b\}$ and $F_{>b}$
**Output:** $E(\mathcal{T}_g^{\max})$ with $\mathcal{T}_g^{\max}$ denoted by $\mathcal{T}_g$
1 &nbsp; $E(\mathcal{T}_g) := E(\mathcal{T}_f)$
2 &nbsp; **for** $\lambda$ **from** $b$ **to** $a+1$ **such that** $F_\lambda \ne \emptyset$ **do**
3 &nbsp;&nbsp;&nbsp;&nbsp; $\lambda^- := \max\{\tilde{\lambda} \in \llbracket a, \lambda-1 \rrbracket | F_{\tilde{\lambda}} \ne \emptyset\}$
4 &nbsp;&nbsp;&nbsp;&nbsp; **if** $\lambda^- = a$ **and** $\text{compact}(\mathcal{T}_f, \tau_L) = L$ **then**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor \text{parent}(\mathcal{T}_g, \tau_\lambda) \rfloor := \text{parent}(\mathcal{T}_f, \tau_L)$
6 &nbsp;&nbsp;&nbsp;&nbsp; **else**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor \text{parent}(\mathcal{T}_g, \tau_\lambda) \rfloor := \tau_{\lambda^-}$
8 &nbsp;&nbsp;&nbsp;&nbsp; **foreach** $\lambda \in \llbracket a, b \rrbracket$ **do**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **foreach** $\tau_p \in F_\lambda$ **do**
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **foreach** $\tau_C \in \text{children}(\mathcal{T}_f, \tau_p)$ **do**
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $\tau_C \notin \bigcup_{\lambda=a}^b F_\lambda$ **then**
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $\tau_C \in F_{>b}$ **then**
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor \text{parent}(\mathcal{T}_g, \tau_C) \rfloor := \tau_b$
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **else**
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor \text{parent}(\mathcal{T}_g, \tau_C) \rfloor := \tau_{\text{level}(\mathcal{T}_f^{\max}, \tau_p)}$

<caption>**Algorithm 4:** Building CASF by updating the component trees</caption>

**Input:** $f: \mathcal{D} \to \mathbb{K}$ (initial image)
**Parameter:** $\kappa$ (node removal criterion)
**Output:** $g: \mathcal{D} \to \mathbb{K}$ (filtered image)
1 **build** $\mathcal{T}_f^{\max}$ from $f$, denoted by $\mathcal{T}^{\max}$
2 **build** $\mathcal{T}_f^{\min}$ from $f$, denoted by $\mathcal{T}^{\min}$
3 **initiate** $\kappa$
4 **while** $\kappa$ is valid **do**
5 &nbsp;&nbsp;&nbsp;&nbsp; **while** $\exists L \in \text{leaves}(\mathcal{T}^{\max})$ **such that** $\kappa(L) = \text{True}$ **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **update** $\mathcal{T}^{\max}$ by removing $L$
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **update** $\mathcal{T}^{\min}$ from Algs. 1–3
8 &nbsp;&nbsp;&nbsp;&nbsp; **while** $\exists L \in \text{leaves}(\mathcal{T}^{\min})$ **such that** $\kappa(L) = \text{True}$ **do**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **update** $\mathcal{T}^{\min}$ by removing $L$
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **update** $\mathcal{T}^{\max}$ from Algs. 1–3
11 &nbsp;&nbsp;&nbsp;&nbsp; **update** $\kappa$

12 **reconstruct** $g$ from $\mathcal{T}^{\max}$ or $\mathcal{T}^{\min}$
## Efficient connected alternating sequential filters

We are now ready to use the component tree updating strategy established above in order to build efficient CASFs. Our proposed approach is formalized in Alg. 4. As in the naive approach, this algorithm considers a given state of the node removal criterion $κ$ at each iteration of the while loop (Line 4), and the two component trees are pruned sequentially (Lines 5–7 and 8–10). However, in contrast to a naive approach that would (1) prune all necessary leaves from the max-tree (resp. min-tree), (2) reconstruct the filtered image, and (3) build the corresponding min-tree (resp. max-tree), here Alg. 4 iteratively removes each leaf from the max-tree (resp. min-tree) (Line 6/9) and updates the min-tree (resp. max-tree) accordingly (Line 7/10) without the need to reconstruct the image or fully rebuild a tree.

## 4 Results

To assess the performance of our method, we implemented two versions of CASFs: (1) the naive version and (2) our proposed approach described in Alg. 4.

We conducted run-time experiments on the Occluded RoadText Challenge<fnref n="6" /> which contains 1019 driving-scene images (817 in the test set and 202 in the validation set) originally sized 1980 × 1080 pixels. These images, featuring natural elements, urban infrastructure, text, and crowded scenes, were rescaled to 576 × 324 pixels for processing efficiency. For each image, we ran the CASFs with increasing values of area for openings/closing, from 10 to 500 pixels, in steps of 10 (i.e. 10 × *i* pixels at iteration *i* of the process). We then computed the average computation time of the both methods over these images.

The time costs for each iteration are given in Fig. 2(a). We can observe that the costs associated with the naive method remains mostly constant across successive iterations. This is because they are primarily driven by the construction of the component trees and the reconstruction of the image, both of which mainly depend on the image size. In contrast, our method incurs a higher cost in the initial iterations but quickly decreases in subsequent ones, ultimately becoming significantly lower than that of the naive approach. This behavior is explained by the (sub)linear dependence of the computational cost per interaction on the number of removed nodes, as experimentally shown in Fig. 2(b). The reduction in cost observed during the iterations in Fig. 2(a) derives from the fact that the number of leaf nodes to be removed progressively decreases as the area increases.

The overall time costs of the two methods, obtained by summing the costs across all iterations, are shown in Fig. 3. The cost of the naive approach (red curve) increases linearly with the number of iterations, since each iteration has a similar time cost (see Fig. 2(a)). The cost of our method (blue curve) is initially higher than the naive one, due to the greater cost of the first few iterations. However, it then increases quasi-linearly, with a lower slope than the naive approach, and then becomes lower than the naive approach (here, around the 6th iteration). Our standalone approach thus becomes more efficient than the naive method when the number of iterations is sufficiently high. In

<footnote n="6">⁶ https://rrc.cvc.uab.es/?ch=29</footnote>
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** (a) Time cost of each iteration of the two CASF methods (naive, ours). (b) Correlation (log-log scale) between the time cost of each iteration (y-axis) and the number of removed nodes during the iteration (x-axis) for our method.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Time cost of CASFs. Naive approach (a–b, in red). Our approach (a, in blue). Hybrid approach obtained by considering, at each iteration, the most efficient approach (b, in green).</figcaption></figure>

addition, our approach can also be combined with the naive approach to form a hybrid strategy: the naive approach is used for the initial steps, and our approach is applied for the remaining steps. The cost of this hybrid method (Fig. 3(b), green curve) is significantly lower than that of the naive approach (Fig. 3(b), red curve).

In addition to the iteration-wise analysis, we evaluated the overall performance improvement by comparing the relative computational gains. Our approach achieved a speedup of approximately 5.55× compared to the naive method, while the hybrid method provided an even greater speedup of 8.61×. Moreover, the hybrid strategy was 1.55× faster than our standalone approach. These improvements correspond to relative reductions in computational cost of 81.97% and 88.38% for our method and the hybrid method, respectively, compared to the naive baseline. Furthermore, the hybrid method achieved a 41.5% reduction compared to our standalone method. Altogether, these find-
ings support the hypothesis that updating the component trees (rather than reconstruct-
ing them at each iteration) not only improves CASF efficiency, but also demonstrates
the benefit of integrating both strategies in a hybrid approach for optimal performance.

5 Conclusion

In this article, we investigated how to optimize the computational efficiency of Con-
nected ASFs based on component tree openings and closings. To this end, we pro-
posed an algorithmic approach for updating a max- (resp. min-) tree when a leaf node
is removed from its dual min- (resp. max-) tree. This process avoids the complete re-
construction of the component tree at each iteration of a CASF. We observed that this
strategy has a linear time cost with respect to the number of removed nodes. This im-
plies that in the initial iterations, when many nodes need to be removed, our method
is less efficient than fully reconstructing the trees. However, it quickly becomes more
computationally efficient than full reconstruction. This observation suggests that hybrid
CASF algorithms could be beneficial, initially relying on full tree reconstruction and
transitioning to tree updating in later iterations.

The perspective for future work on this topic are manifold. We plan to study how to
update a component tree when an entire distal subtree is removed from its dual tree. This
could significantly reduce the computational cost of the early iterations in the CASF
sequence. We also intend to conduct a complexity analysis of the proposed method to
identify a cut-off point where updates become more efficient than full reconstructions.
More generally, we aim to explore how to update a max- (resp. min-) tree when its dual
min- (resp. max-) tree is modified by increasing (resp. decreasing) a subset of a flat zone.
This may pave the way for a broader class of efficient image processing techniques
based on component trees. Finally, we will investigate the efficient integration of flat
and non-flat attribute updates during incremental tree updates [7,18], enabling ASFs
based on a wider range of attributes, such as perimeter, bounding box, height, among
others.

Acknowledgements

This work was funded by the *Agence Nationale de la Recherche* (Grants ANR-22-
CE45-0034 and ANR-23-CE45-0015), *CNPq – Conselho Nacional de Desenvolvimento
Científico e Tecnológico* (Grants 141422/2018-1, 428720/2018-7 and 407242/2021-
0) and *FAPESP – Fundação de Amparo a Pesquisa do Estado de São Paulo* (Grants
2015/22308-2 and 2018/15652-7).

References

1. Blin, N., Carlinet, E., Lemaitre, F., Lacassagne, L., Géraud, T.: Max-tree computation on GPUs. IEEE Transactions on Parallel and Distributed Systems **33**, 3520–3531 (2022)

2. Breen, E.J., Jones, R.: Attribute openings, thinnings, and granulometries. Computer Vision and Image Understanding **64**, 377–389 (1996)
3. Carlinet, E., Géraud, T.: A comparative review of component tree computation algorithms. IEEE Transactions on Image Processing **23**, 3885–3895 (2014)

4. Caselles, V., Monasse, P.: Geometric Description of Images as Topographic Maps. Berlin, Heidelberg: Springer-Verlag Berlin Heidelberg (2010)

5. Dalla Mura, M., Benediktsson, J.A., Bruzzone, L.: Alternating sequential filters with morphological attribute operators for the analysis of remote sensing images. In: ISPRS, Procs. pp. 43–50 (2010)

6. Gazagnes, S., Wilkinson, M.H.F.: Distributed connected component filtering and analysis in 2D and 3D tera-scale data sets. IEEE Transactions on Image Processing **30**, 3664–3675 (2021)

7. Gobber, C.F., Hashimoto, R.F., Alves, W.A.: An efficient algorithm to update non-flat and incremental attributes in morphological trees. Pattern Recognition Letters **163**, 47–54 (2022)

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

9. Jones, R.: Connected filtering and segmentation using component trees. Computer Vision and Image Understanding **75**, 215–228 (1999)

10. Morales, A.W., Acharya, R., Ko, S.: Morphological pyramids with alternating sequential filters. IEEE Transactions on Image Processing **5**, 965–977 (1995)

11. Pei, S.C., Lai, C.L., Shih, F.Y.: An efficient class of alternating sequential filters in morphology. CVGIP: Graphical Models and Image Processing **59**, 109–116 (1997)

12. Ronse, C., Heijmans, H.J.A.M.: The algebraic basis of mathematical morphology: II. Openings and closings. CVGIP Image Understanding **54**, 74–97 (1991)

13. Rosenfeld, A.: Digital topology. The American Mathematical Monthly **86**, 621–630 (1979)

14. Salembier, P., Wilkinson, M.: Connected operators. IEEE Signal Processing Magazine **26**, 136–157 (2009)

15. Salembier, P., Oliveras, A., Garrido, L.: Anti-extensive connected operators for image and sequence processing. IEEE Transactions on Image Processing **7**, 555–570 (1998)

16. Serra, J. (ed.): Image Analysis and Mathematical Morphology, Vol. II. Theoretical Advances. Academic Press, London (1988)

17. Sternberg, S.R.: Grayscale morphology. Computer Vision, Graphics, and Image Processing **35**, 333–355 (1986)

18. Wilkinson, M.H.F., Gao, H., Hesselink, W.H., Jonker, J.E., Meijster, A.: Concurrent computation of attribute filters on shared memory parallel machines. IEEE Transactions on Pattern Analysis and Machine Intelligence **30**, 1800–1813 (2008)

19. Xu, Y., Géraud, T., Najman, L.: Connected filtering on tree-based shape-spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence **38**, 1126–1140 (2016)