A Topological Tree of Shapes

Abstract

In this article, we enrich the framework of morphological hierarchies with new acyclic graphs and trees. These structures lie at the convergence of hierarchical models and topological descriptors. We define them in the context of digital grey-level imaging. We discuss their links with component-trees, trees of shapes and adjacency trees. This analysis leads to new notions, including a notion of topological tree of shapes.

1 Introduction

Many hierarchical, graph-based structures have been defined in the framework of mathematical morphology, especially for designing connected operators [25]. The most popular are trees (i.e. rooted, connected, acyclic graphs). They model finite sets of partitions organized with respect to the refinement order relation. These partitions can be partial. This is the case of the component-tree and its variants [9, 24], the level-line tree (a.k.a. tree of shapes) and its variants  [3, 11]. These partitions can also be total. This is the case of the binary partition tree and its variants  [19, 23, 27] and the hierarchical watershed [13, 26]. Other hierarchical structures are directed acyclic graphs (DAGs), e.g. the component-hypertree [15], the component-graph [17], the braid of partitions [8] and the directed component hierarchy [18].

The partitions modeled by these hierarchical structures are composed of connected sets defined with respect to a topology defined on a given space which is generally discrete (e.g. a part of $\mathbb {Z}^n$ [22], a complex on/tesselation of $\mathbb {R}^n$). Hierarchical structures carry intrinsic, topological information. However, these information are often limited and generally not sufficient to perform high-level topological analysis of the modeled images/data. In particular, hierarchical structures are generally less informative than high-level topological invariants/descriptors, e.g. the homology groups/homology persistence [6] or the homotopy type.

In this article, we introduce a new family of hierarchical structures—DAGs and trees, including a new notion of topological tree of shapes—dedicated to the modeling of grey-level images. They aim to gather (i) connectedness/intensity information carried by component- (min- and max-) trees [24] and (ii) topological information carried by the adjacency tree, a classical topological invariant [21]. Basically, we will first build a DAG that is composed by the min-tree and max-tree of a grey-level image, and we will enrich the nodes of these two trees by the adjacency tree structure at each grey-level, leading to the notion of a graph of valued shapes. Then, we will establish that this graph of valued shape can be simplified in a lossless fashion as a tree structure by discarding some transitive, redundant edges. This will lead to a simpler tree structure called tree of valued shapes. By factorizing some spatially equivalent nodes, we will then define a more compact structure, called the complete tree of shapes. We will establish that this complete tree of shapes can be reduced (in a lossy fashion) in two different ways, leading on the one hand to the usual notion of a tree of shapes and on the other hand to the new notion of a topological tree of shapes. (The chosen terminology of topological trees of shapes is justified by the way it is defined; however it will be shown to be different from another homonymous notion previously introduced in the literature.) We will finally evoke the links between these new structures (graph and tree of valued shapes, complete tree of shapes, topological tree of shapes) and usual morphological trees (component-tree, tree of shapes, adjacency tree).

This article is organized as follows. Section 2 provides definitions related to hierarchies and grey-level images. We introduce the notions of graph of valued shapes and tree of valued shapes in Sects. 3 and 4, respectively. Section 5 derives from the tree of valued shapes the two essential notions of this work, namely the complete tree of shapes (that generalizes the tree of shapes) and the topological tree of shapes. In Sect. 6, we discuss on the links that exist between these new notions and well-known morphological hierarchies. We provide concluding remarks in Sect. 7.

2 Basics: Hierarchies and Images

Definition 1

(Hierarchical order). Let X be a set and $\le$ be an order on X. We say that $\le$ is a hierarchical order if $\forall x \in X$ the subset $x^\uparrow = \{ y \in X \mid x < y \}$ is totally ordered.

Definition 2

(Hierarchical function). Let X be a set and $\le$ a hierarchical order on X. The hierarchical function $\zeta _\le : X \rightarrow X$ is defined by $\zeta _\le (x) = \bigwedge _{\le }x^\uparrow$. This function is defined everywhere on X except for the greatest elements of $(X,\le )$.

Remark 3

Let $\vartriangleleft$ be the Hasse relation obtained from $\le$ by reflexive-transitive reduction. $\forall x \in X$ we have

$$\begin{aligned} x \vartriangleleft \zeta _\le (x) \end{aligned}$$

(1)

This formula induces an isomorphism between $(X,\vartriangleleft )$ and $(X,\zeta _\le )$.

Definition 4

(Tree). Let X be a set and $\le$ a hierarchical order on X such that $(X,\le )$ admits a maximum. The Hasse diagram $(X,\vartriangleleft )$ is called a tree.

Let ${\mathbb {U}}$ be a discrete set endowed with a topological structure which provides the notions of adjacency and connectedness, and where the separation theorem (Jordan-Brouwer) holds.

Remark 5

In this article we choose ${\mathbb {U}}= \mathbb {Z}^n$ ($n \ge 2$) and we consider the usual framework of digital topology on binary images  [22], with the standard couples of $(2n,3^n-1)$ and $(3^n-1,2n)$-adjacencies for the foreground and background.

Let ${\mathbb {K}}$ be a set of values endowed with a total order $\leqslant _{\mathbb {K}}$. Let ${\mathcal {F}}: {\mathbb {U}}\rightarrow {\mathbb {K}}$ be an application. We assume that there exist a finite, nonempty subset ${\mathbb {S}}\subset {\mathbb {U}}$ and two values $\bot <_{\mathbb {K}}\top \in \mathbb {K}$ such that for all $\textbf{x}\in {\mathbb {U}}$

$$\begin{aligned} \left\{ \begin{array}{ll} \mathcal {F}(\textbf{x}) = \bot &{} ~\text { if }~ \textbf{x}\notin \mathbb {S}\\ \bot<_{\mathbb {K}}\mathcal {F}(\textbf{x}) <_{\mathbb {K}}\top &{} ~\text { if }~ \textbf{x}\in \mathbb {S} \end{array} \right. \end{aligned}$$

(2)

We set ${\mathbb {V}}= {\mathcal {F}}({\mathbb {S}}) \cup \{\bot , \top \}$. It is a finite set that we equip with the total order $\leqslant _{\mathbb {V}}$ induced by $\leqslant _{\mathbb {K}}$.

Remark 6

The application ${\mathcal {F}}$ is isomorphic to a grey-level image taking its values in an interval of $\mathbb {Z}$ of size $|{\mathbb {V}}|$, e.g. $[\![0,|{\mathbb {V}}|-1]\!]$. See Fig. 1(a).

3 Graph of Valued Shapes

3.1 (Valued) Connected Components

We set $\leqslant ^\circ \ = \ \leqslant _{\mathbb {V}}$ and $\leqslant ^\bullet \ = \ \geqslant _{\mathbb {V}}$. Let $v \in {\mathbb {V}}$. We define the threshold sets of ${\mathcal {F}}$ at value $v \in {\mathbb {V}}$ (see Fig. 1(b–i)) as

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

(3)

Let $X \subseteq {\mathbb {U}}$. When X is nonempty, we note $\varPi [X] \subset 2^{{\mathbb {U}}}$ the partition gathering all the connected components of X. If X is empty, we set $\varPi [X] = \emptyset$.

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

$$\begin{aligned} \begin{array}{lll} \varXi ^\circ _v &{}= &{}\varTheta ^\circ _v \times \{v\}\\ \varXi ^\bullet _v &{}= &{}\varTheta ^\bullet _v \times \{v\}\\ \varXi _v &{}= &{}\varTheta _v \times \{v\} \end{array} ~~~\text {with}~~~ \begin{array}{lll} \varTheta ^\circ _v &{}=&{} \varPi [\varLambda ^\circ _v ({\mathcal {F}})]\\ \varTheta ^\bullet _v &{}=&{} \varPi [\varLambda ^\bullet _v ({\mathcal {F}})]\\ \varTheta _v &{} =&{} \varTheta _v^\circ \cup \varTheta _v^\bullet \end{array} \end{aligned}$$

(4)

Remark 7

We have $\varXi ^\circ _\top = \varXi ^\bullet _\bot = \emptyset$. For any $v \in {\mathbb {V}}\setminus \{\bot , \top \}$, we have $\varXi ^\circ _v \ne \emptyset$ and $\varXi ^\bullet _v \ne \emptyset$. In the sequel, $({\mathbb {U}},\bot )$ and $({\mathbb {U}},\top )$ are considered as a unique element noted $\infty$. Then, we have $\varXi ^\circ _\bot = \{({\mathbb {U}},\bot )\} = \{\infty \} = \{({\mathbb {U}},\top )\} = \varXi ^\bullet _\top$ and $\varXi _\bot = \varXi _\top = \{\infty \}$.

We set

$$\begin{aligned} \begin{array}{lll} \varXi ^\circ &{} = \bigcup _{v \in {{\mathbb {V}}}} \varXi ^\circ _v \\ \varXi ^\bullet &{} = \bigcup _{v \in {{\mathbb {V}}}} \varXi ^\bullet _v \\ \varXi &{} = \varXi ^\circ \cup \varXi ^\bullet = \bigcup _{v \in {{\mathbb {V}}}}\varXi _v \end{array} ~~~\text {and}~~~ \begin{array}{lll} \varTheta ^\circ &{} = \bigcup _{v \in {{\mathbb {V}}}} \varTheta ^\circ _v \\ \varTheta ^\bullet &{} = \bigcup _{v \in {{\mathbb {V}}}} \varTheta ^\bullet _v \\ \varTheta &{} = \varTheta ^\circ \cup \varTheta ^\bullet = \bigcup _{v \in {{\mathbb {V}}}}\varTheta _v \end{array} \end{aligned}$$

(5)

3.2 Orders on Valued Connected Components

We define the partial orders $\sqsubseteq ^\circ$ on $\varXi ^\circ$ and $\sqsubseteq ^\bullet$ on $\varXi ^\bullet$ as

$$\begin{aligned} \begin{array}{l} ((X,v) \sqsubseteq ^\circ (Y, w)) \Leftrightarrow (X \subseteq Y \wedge w \leqslant ^\circ v) \\ ((X,v) \sqsubseteq ^\bullet (Y, w)) \Leftrightarrow (X \subseteq Y \wedge w \leqslant ^\bullet v) \end{array} \end{aligned}$$

(6)

We define the order $\sqsubseteq ^\varphi$ as the union of $\sqsubseteq ^\circ$ and $\sqsubseteq ^\bullet$, i.e. $P \sqsubseteq ^\varphi Q$ iff $P \sqsubseteq ^\circ Q$ or $P \sqsubseteq ^\bullet Q$.

Remark 8

$\sqsubseteq ^\varphi$, $\sqsubseteq ^\circ$ and $\sqsubseteq ^\bullet$ are hierarchical orders. They admit $\infty$ as maximum.

Let $v \in {\mathbb {V}}$. We define the order $\sqsubseteq ^v$ on $\varXi _v$ as

$$\begin{aligned} ((X,v) \sqsubseteq ^v (Y, v)) \Leftrightarrow \tau (X) \subseteq \tau (Y) \end{aligned}$$

(7)

where $\tau : 2^{{\mathbb {U}}} \rightarrow 2^{{\mathbb {U}}}$ is the hole closing application defined by $\tau (X) = X \cup \bigcup Z$ where $Z \subseteq \varPi [\overline{X}]$ is composed by the finite connected components of $\overline{X} = {\mathbb {U}}\setminus X$.

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

Remark 9

$\sqsubseteq ^\psi$, and $\sqsubseteq ^v$ ($v \in {\mathbb {V}}$) are hierarchical orders. Each ordered set $(\varXi _v,\sqsubseteq ^v)$ ($v \in {\mathbb {V}}$) admits a maximum $({\mathbb {U}}_v,v)$ where ${\mathbb {U}}_v \subseteq {\mathbb {U}}$ is the unique element of $\varTheta _v$ which is infinite.

We note $\vartriangleleft ^\varphi$ (resp. $\vartriangleleft ^\circ$, $\vartriangleleft ^\bullet$) and $\vartriangleleft ^\psi$ (resp. $\vartriangleleft ^v$) the Hasse relations associated to $\sqsubseteq ^\varphi$ (resp. $\sqsubseteq ^\circ$, $\sqsubseteq ^\bullet$) and $\sqsubseteq ^\psi$ (resp. $\sqsubseteq ^v$). The graph $(\varXi ,\vartriangleleft ^\varphi )$ is “similar” to the union of the max- and min-trees, whereas $(\varXi ,\vartriangleleft ^\psi )$ is “similar” to the union of the adjacency trees of each threshold set of ${\mathcal {F}}$. This will be more formally discussed in Sect. 6.

Remark 10

Let $P = (X, v), Q = (Y, w) \in \varXi$ such that $P \vartriangleleft ^\varphi Q$. We have $P, Q \in \varXi ^\star$ with $\star =$ either $\circ$ or $\bullet$. In addition, we have $X \subseteq Y$ and $v = \zeta _{\leqslant ^\star }(w)$.

Remark 11

Let $P = (X, v), Q = (Y, w) \in \varXi$ such that $P \vartriangleleft ^\psi Q$. We have ($P \in \varXi ^\bullet$ and $Q \in \varXi ^\circ$) or ($P \in \varXi ^\circ$ and $Q \in \varXi ^\bullet$). In addition, we have $v=w$ and $\tau (X) \in \varPi [\overline{Y}]$.

We note $\varphi = \zeta _{\sqsubseteq ^\varphi }$, $\varphi ^\circ = \zeta _{\sqsubseteq ^\circ }$, $\varphi ^\bullet = \zeta _{\sqsubseteq ^\bullet }$, $\psi = \zeta _{\sqsubseteq ^\psi }$ and $\psi ^v = \zeta _{\sqsubseteq ^v}$ ($v \in {\mathbb {V}}$).

3.3 Definition of the Graph of Valued Shapes

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

Definition 12

(Graph of valued shapes). The graph of valued shapes (or VS-graph, for brief) is the couple $\mathfrak {G}_{\textrm{VS}} = (\varXi ,\vartriangleleft _{\varXi })$.

Remark 13

The intersection between $\vartriangleleft ^\varphi$ and $\vartriangleleft ^\psi$ is empty. We can then consider $\mathfrak {G}_{\textrm{VS}}$ as $(\varXi ,\vartriangleleft _{\varXi })$ or as $(\varXi ,\vartriangleleft ^\varphi ,\vartriangleleft ^\psi )$ and equivalently as $(\varXi ,\varphi ,\psi )$.

Property 14

$\mathfrak {G}_{\textrm{VS}} = (\varXi ,\vartriangleleft _{\varXi })$ is a directed acyclic graph.

We define $\sqsubseteq _{\varXi }$ as the reflexive-transitive closure of $\vartriangleleft _{\varXi }$.

Remark 15

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

4 Tree of Valued Shapes

4.1 Transitive Reduction of the Graph of Valued Shapes

Let $\blacktriangleleft _{\varXi }$ be the relation on $\varXi$ defined as the transitive reduction of $\vartriangleleft _{\varXi }$.

Let $P \in \varXi$. Let us consider the following three equalities

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

(8)

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

(9)

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

(10)

Remark 16

If P satisfies Eq. (8), then we have $P \vartriangleleft _{\varXi } \psi (P)$ and . If P satisfies Eq. (9) or (10), then we have $P \vartriangleleft _{\varXi } \varphi (P)$ and .

Proposition 17

Let $P \in \varXi$ be such that $\varphi (P)$ and $\psi (P)$ exist. One of Eqs. (8–10) is satisfied.

Fig. 1.

(a) A grey-level image ${\mathcal {F}}:{\mathbb {U}}\rightarrow {\mathbb {V}}$ (${\mathbb {U}}= \mathbb {Z}^2$ and ${\mathbb {V}}= [\![0,7]\!]$). (b–i) The threshold sets $\varLambda ^\star _v ({\mathcal {F}})$ ($\varLambda ^\circ _v ({\mathcal {F}})$ in white; $\varLambda ^\bullet _v ({\mathcal {F}})$ in black), for $v = 0$ (b) to 7 (i).

Fig. 2.

Tree of valued shapes of the image ${\mathcal {F}}$ (Fig. 1(a)). The valued connected components are depicted by squares ($\varXi ^\circ$ on the left side; $\varXi ^\bullet$ on the right side) and are positioned with respect to the threshold value v (see on left), from 0 (top) to 7 (bottom). Red and green arrows correspond to the $\blacktriangleleft _{\varXi }$ relation. Green and black dotted arrows correspond to the $\vartriangleleft ^\varphi$ relation. Red arrows are a subset of the $\vartriangleleft ^\psi$ relation, not fully depicted for the sake of readibility. (Color figure online)

Proof

Let $P = (X,v) \in \varXi$ be such that $\varphi (P)$ and $\psi (P)$ exist. Case 1: $\varphi (P) = ({\mathbb {U}},\bot ) = \infty$ and $\psi (P) = ({\mathbb {U}}_v,v)$ (the unique element of $\varPi [\varLambda ^\bullet _v ({\mathcal {F}})]$ which is infinite). It is plain that $\varphi ^{|{\mathbb {V}}|-2}(({\mathbb {U}}_v,v)) = ({\mathbb {U}},\top ) = \infty = \varphi (P)$, and Eq. (10) then holds. Case 2: $\varphi (P) = ({\mathbb {U}},\bot )$ and $\psi (P) \ne ({\mathbb {U}}_v,v)$. It is plain that $\psi ^2(P)$ exists and $\varphi (\psi ^2(P)) = ({\mathbb {U}},\bot ) = \varphi (P)$, thus Eq. (9) holds. Case 3: $\varphi (P) = ({\mathbb {U}},\top )$. Since $\psi (P)$ exists (and is finite), it is plain that $\psi ^2(P)$ also exists. But then $\varphi (\psi ^2(P)) = ({\mathbb {U}},\top ) = \varphi (P)$, thus Eq. (9) holds. Case 4: $\varphi (P) \ne \infty$. If $\psi (P) = ({\mathbb {U}}_v, v)$, it is plain that $\psi (\varphi (P)) = ({\mathbb {U}}_w, w)$ with $({\mathbb {U}}_v, v) = \varphi (({\mathbb {U}}_w, w))$ and Eq. (8) then holds. Let us now suppose that $\psi (P) \ne ({\mathbb {U}}_v, v)$ and that Eq. (8) does not hold, i.e. $[\varphi \circ \psi \circ \varphi ] (P) \ne \psi (P)$. Then we have $P \sqsubset ^\psi \psi ^2(P) \sqsubset ^\psi [\varphi \circ \psi \circ \varphi ] (P)$. Now, let us suppose that $\varphi (\psi ^2(P)) \ne \varphi (P)$. Then we have $\varphi (P) \sqsubset ^\psi \varphi (\psi ^2(P))$ and it comes $\varphi (P) \sqsubset ^\psi \psi (\varphi (P)) \sqsubset ^\psi \varphi (\psi ^2(P))$ in contradiction with the Jordan theorem. Thus Eq. (9) holds. $\blacksquare$

If follows from Proposition 17 that for any $P \in \varXi$ such that both $\psi (P)$ and $\varphi (P)$ exist we have or . Since $(\varXi ,\sqsubseteq _{\varXi })$ admits a maximum (namely $\infty$), for each $P \in \varXi$, $P \ne \infty$, we have either $P \blacktriangleleft _{\varXi } \psi (P)$ or $P \blacktriangleleft _{\varXi } \varphi (P)$. The following property derives from these facts.

Property 18

Let $P \in \varXi$.

• If $\varphi (P)$ is defined and $\psi (P)$ is not, then $P \blacktriangleleft _{\varXi } \varphi (P)$.

• If $\psi (P)$ is defined and $\varphi (P)$ is not, then $P \blacktriangleleft _{\varXi } \psi (P)$.

• If $\varphi (P)$ and $\psi (P)$ are defined, then either $P \blacktriangleleft _{\varXi } \varphi (P)$ or $P \blacktriangleleft _{\varXi } \psi (P)$.

Remark 19

The transitive reduction from $\mathfrak {G}_{\textrm{VS}} = (\varXi ,\vartriangleleft _{\varXi })$ to $(\varXi ,\blacktriangleleft _{\varXi })$ is a lossless compression. The graph $\mathfrak {G}_{\textrm{VS}} = (\varXi ,\vartriangleleft _{\varXi })$ can be reconstructed from $(\varXi ,\blacktriangleleft _{\varXi })$.

4.2 Definition of the Tree of Valued Shapes

Property 20

$(\varXi ,\blacktriangleleft _{\varXi })$ is a tree. Equivalently, $\sqsubseteq _{\varXi }$ is a hierarchical order on $\varXi$.

Definition 21

(Tree of valued shapes). The tree of valued shapes (or VS-tree, for brief) is the couple $\mathfrak {T}_{\textrm{VS}} = (\varXi ,\blacktriangleleft _{\varXi })$. See Fig. 2.

5 Complete Tree of Shapes and Topological Tree of Shapes

5.1 Spatial Compression: From the Tree of Valued Shapes to the Complete Tree of Shapes

Let $\pi _{\varTheta } : \varXi \rightarrow \varTheta$ be the function defined by $\pi _{\varTheta }((X,v)) = X$. Let $\sim _{\varTheta }$ be the equivalence relation on $\varXi$ defined by

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

(11)

Property 22

The function $\tilde{\pi }_{\varTheta } : \varXi /\mathord {\sim _{\varTheta }} \rightarrow \varTheta$ defined by $\tilde{\pi }_{\varTheta }([P]_{\sim _{\varTheta }}) = \pi _{\varTheta }(P)$ is a bijection.

Remark 23

Based on the above property, we identify $\varXi /\mathord {\sim _{\varTheta }}$ and $\varTheta$. More precisely, for any $P = (X,v) \in \varXi$, we identify $[P]_{\mathord {\sim _{\varTheta }}}$ and X. In particular, we have $[\infty ]_{\mathord {\sim _{\varTheta }}} = \{\infty \} \in \varXi /\mathord {\sim _{\varTheta }}$ and it is identified to ${\mathbb {U}}\in \varTheta$.

Property 24

Let $K \in \varXi /\mathord {\sim _{\varTheta }}$. Let $\sqsubseteq _K$ be the order induced by $\sqsubseteq _{\varXi }$ on K. Then $(K, \sqsubseteq _K)$ is a totally ordered set.

For any $K \in \varXi /\mathord {\sim _{\varTheta }}$, we note $\langle K \rangle _{\varTheta } = \bigwedge _{\sqsubseteq _{\varXi }} K$ and $\langle \!\langle K \rangle \!\rangle _{\varTheta } = \bigvee _{\sqsubseteq _{\varXi }} K$. We note $\rho _{\varXi } = \zeta _{\sqsubseteq _{\varXi }}$.

Remark 25

From Property 24, it follows that $\forall p \in [\![1,|K|-1]\!]$ we have $\rho _{\varXi }^{p}(\langle K \rangle _{\varTheta }) \in K$. In particular, we have $\rho _{\varXi }^{|K|-1}(\langle K \rangle _{\varTheta }) = \langle \!\langle K \rangle \!\rangle _{\varTheta }$ whereas $\rho _{\varXi }^{|K|}(\langle K \rangle _{\varTheta }) \notin K$.

Proposition 26

Let $K \in \varXi /\mathord {\sim _{\varTheta }}$, $K \ne \{\infty \}$. Let $P = \rho _{\varXi }^{|K|}(\langle K \rangle _{\varTheta })$. We have $P = \langle [P]_{\mathord {\sim _{\varTheta }}} \rangle _{\varTheta }$.

Proof

Let $P = \rho _{\varXi }^{|K|}(\langle K \rangle _{\varTheta }) = \rho _{\varXi }(\langle \!\langle K \rangle \!\rangle _{\varTheta })$, with $\langle \!\langle K \rangle \!\rangle _{\varTheta } = (X,v)$ and $P = (Y,w)$. In particular, we have $\langle \!\langle K \rangle \!\rangle _{\varTheta } \blacktriangleleft _{\varXi } P$ and thus $\langle \!\langle K \rangle \!\rangle _{\varTheta } \vartriangleleft _{\varXi } P$. Let $Q = (Y,u) = \langle [P]_{\mathord {\sim _{\varTheta }}} \rangle _{\varTheta }$. Case 1: $\langle \!\langle K \rangle \!\rangle _{\varTheta } \vartriangleleft ^\varphi P$. This implies $X \subseteq Y$ and $w \leqslant ^\star v$ (with $\star =$ either $\circ$ or $\bullet$). As $P \notin K$, we have $X \subset Y$, and it follows that $w <^\star v$. We have $w \leqslant ^\star u$. If $u \ne w$, then we have $w <^\star u$ and it follows that $\langle \!\langle K \rangle \!\rangle _{\varTheta } \sqsubset ^\varphi Q \sqsubset ^\varphi P$, and thus : a contradiction. Then, we have $u = w$, and it follows that $P = \langle [P]_{\mathord {\sim _{\varTheta }}} \rangle _{\varTheta }$. Case 2: $\langle \!\langle K \rangle \!\rangle _{\varTheta } \vartriangleleft ^\psi P$. We have $X \in$ either $\varTheta ^\circ _v$ or $\varTheta ^\bullet _v$ (for instance, $\varTheta ^\circ _v$; the same reasoning holds with $\varTheta ^\bullet _v$) and $\varphi (\langle \!\langle K \rangle \!\rangle _{\varTheta })$ exists. Let $R = (Z, t) = \varphi (\langle \!\langle K \rangle \!\rangle _{\varTheta })$. We have $X \subseteq Z$, and since $R \notin K$, it comes $X \subset Z$. Let us suppose that $P \ne Q$. Then, we have $S = (Y,t) \in [P]_{\mathord {\sim _{\varTheta }}}$. It follows that $\tau (X) = \tau (Z)$. Consequently, we have $R \vartriangleleft ^\psi S$. But then, we obtain $\langle \!\langle K \rangle \!\rangle _{\varTheta } \vartriangleleft ^\varphi R \vartriangleleft ^\psi S \vartriangleleft ^\varphi P$, in contradiction with $\langle \!\langle K \rangle \!\rangle _{\varTheta } \blacktriangleleft _{\varXi } P$. Then, we have $P = \langle [P]_{\mathord {\sim _{\varTheta }}} \rangle _{\varTheta }$. $\blacksquare$

For any $K \in \varXi /\mathord {\sim _{\varTheta }}$, we consider $\langle K \rangle _{\varTheta } \in \varXi$ as canonical element, and we identify $\langle K \rangle _{\varTheta } = (X,v)$ with $X \in \varTheta$.

Let $\sqsubseteq _{\varTheta }$ be the order on $\{\langle K \rangle _{\varTheta } \mid K \in \varXi /\mathord {\sim _{\varTheta }}\} \subseteq \varXi$—and equivalently on $\varTheta$— induced by $\sqsubseteq _{\varXi }$.

We note $\kappa _{\varTheta } = \tilde{\pi }_{\varTheta }^{-1}$. Let $\rho _{\varTheta } : \varTheta \rightarrow \varTheta$ be the function defined by

$$\begin{aligned} \rho _{\varTheta }(X) = \pi _{\varTheta }( \rho _{\varXi }^{|K|}(\langle K \rangle )) \end{aligned}$$

(12)

with $K = \kappa _{\varTheta }(X)$.

Remark 27

From the above property, we have $\rho _{\varTheta } = \zeta _{\sqsubseteq _{\varTheta }}$. We note $\blacktriangleleft _{\varTheta }$ the relation on $\varTheta$ associated to $\rho _{\varTheta }$, namely the Hasse relation of $\sqsubseteq _{\varTheta }$.

Definition 28

(Complete tree of shapes). The complete tree of shapes (or CS-tree, for brief) is the couple $\mathfrak {T}_{\textrm{CS}} = (\varTheta ,\blacktriangleleft _{\varTheta })$. See Fig. 3 (left).

The following proposition directly derives from the above results.

Proposition 29

The equivalence relation $\sim _{\varTheta }$ induces a decreasing homeomorphism from $\mathfrak {T}_{\textrm{VS}} = (\varXi ,\blacktriangleleft _{\varXi })$ to $\mathfrak {T}_{\textrm{CS}} = (\varTheta ,\blacktriangleleft _{\varTheta })$.

Remark 30

The homeomorphism from $\mathfrak {T}_{\textrm{VS}} = (\varXi ,\blacktriangleleft _{\varXi })$ to $\mathfrak {T}_{\textrm{CS}} = (\varTheta ,\blacktriangleleft _{\varTheta })$ is a lossless compression. The tree $\mathfrak {T}_{\textrm{VS}} = (\varXi ,\blacktriangleleft _{\varXi })$ can be fully reconstructed from $\mathfrak {T}_{\textrm{CS}} = (\varTheta ,\blacktriangleleft _{\varTheta })$.

Fig. 3.

From left to right: (1) the complete tree of shapes; (2) the topological tree of shapes; (3) the tree of shapes of the image ${\mathcal {F}}$ of Fig. 1. The complete tree of shapes (1) derives from the reduction of the tree of valued shapes of Fig. 2. Green arrows are originated from the $\vartriangleleft ^\varphi$ relation. Red arrows are originated from the $\vartriangleleft ^\psi$ relation. (Color figure online)

5.2 Topological Compression: From the Tree of Valued Shapes to the Topological Tree of Shapes

Let $X, Y \in {\mathbb {U}}$, with $Y \subset X$. We aim to characterize the preservation of topological properties by a decreasing transformation from X to Y. A frequent strategy is to consider the notion of homotopic transformation. In particular, if there exists a (decreasing) homotopic transformation from X to Y, then X and Y have the same homotopy type. However, this is hardly tractable in 3D [10] and in higher dimensions. Then we consider a weaker topological invariant induced by the notion of strongly deletable set [20]. More precisely, if $X \setminus Y$ is strongly deletable, then the inclusion relation induces a bijection between the (foreground and background) connected components of X and those of Y.

Remark 31

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

Let $P, Q \in \varXi$ be such that $\rho _{\varXi }(P) = Q$. If $\rho _{\varXi }^{-1}(\{Q\}) = \{P\}$ and $\pi _{\varTheta }(Q) \setminus \pi _{\varTheta }(P)$ is a strongly deletable set, then we note $Q \searrow P$.

Remark 32

If $Q \searrow P$, then we have $\rho _{\varXi }(P) = \varphi (P)$.

Proposition 33

Let $P \in \varXi$. Let $A = \varphi ^{-1}(\{\varphi (P)\}) \cup \psi ^{-1}(\{\varphi (P)\})$. Let $B = \{\varphi (P)\} \cup \psi ^{-1}(\{P\})$. We have $\varphi (P) \searrow P$ iff the restriction $\varphi _{|A} : A \rightarrow B$ is a bijection.

Proof

Let $X = \pi _{\varTheta }(P)$. By definition, X is connected, i.e. $\varPi [X] = \{X\}$. The set $\varPi [\overline{X}]$ is composed by one infinite set $X_0 = {\mathbb {U}}\setminus \tau (X)$ and $k \ge 0$ sets $X_i$ ($1 \le i \le k$) such that $\{X_i\}_{i=1}^k = \tau (\pi _{\varTheta }(\psi ^{-1}(\{P\})))$. Let $Y = \pi _{\varTheta }(\varphi (P))$. By definition, Y is connected, i.e. $\varPi [Y] = \{Y\}$. The set $\varPi [\overline{Y}]$ is composed by one infinite set $Y_0 = {\mathbb {U}}\setminus \tau (Y)$ and $l \ge 0$ sets $Y_j$ ($1 \le j \le l$) such that $\{Y_j\}_{j=1}^l = \tau (\pi _{\varTheta }(\psi ^{-1}(\{\varphi (P)\})))$. Let $D = Y \setminus X$. Let us suppose that $\varphi (P) \searrow P$. Then, we have $\varphi ^{-1}(\{\varphi (P)\}) = \{P\}$, i.e. $\varphi$ is bijective between $\varphi ^{-1}(\{\varphi (P)\})$ and $\{P\}$. Since D is deletable we have $k = l$ and (up to reindexing), for any $i \in [\![0,k]\!]$, $Y_i \subseteq X_i$. For each $i \in [\![0,k]\!]$, there exist $\widehat{P}_i = (\widehat{X}_i,v) \in \psi ^{-1}(\{P\})$ such that $X_i = \tau (\widehat{X}_i)$ and $\widehat{Q}_i = (\widehat{Y}_i,w) \in \psi ^{-1}(\{\varphi (\{P\})\})$ such that $Y_i = \tau (\widehat{Y}_i)$. We have $Y_i \subseteq X_i$ and then $\tau (\widehat{Y}_i) \subseteq \tau (\widehat{X}_i)$. We set $D_i = D \cap \widehat{X}_i$. We have $\tau (\widehat{X}_i \setminus D_i) =\tau (\widehat{X}_i) \setminus D_i = \tau (\widehat{Y}_i)$. It follows that $\widehat{Y}_i \subseteq \widehat{X}_i$, and $\varphi$ is then bijective between $\psi ^{-1}(\{\varphi (P)\})$ and $\psi ^{-1}(\{P\})$. Let us suppose that $\varphi$ is bijective between $\varphi ^{-1}(\{\varphi (P)\})$ and $\{\varphi (P)\}$. Then both $P = \varphi (P) \setminus D$ and $\varphi (P)$ are connected and $P \subset \varphi (P)$. Let us suppose that $\varphi$ is bijective between $\psi ^{-1}(\{\varphi (P)\})$ and $\psi ^{-1}(\{P\})$. The function $\tau \circ \pi _{\varTheta }$ is a bijection between $\psi ^{-1}(\{P\})$ (resp. $\psi ^{-1}(\{\varphi (P)\})$) and $\{X_i\}_{i=1}^k$ (resp. $\{Y_j\}_{j=1}^l$). It follows that $\varphi (P) \searrow P$. $\blacksquare$

Let $\sim _H$ be the equivalence relation on $\varXi$ defined as the reflexive-transitive-symmetric closure of $\searrow$.

Remark 34

We have $[\infty ]_{\mathord {\sim _H}} = \{\infty \} \in \varXi /\mathord {\sim _H}$.

Property 35

Let $K \in \varXi /\mathord {\sim _H}$. Let $\sqsubseteq _K$ be the order induced by $\sqsubseteq _{\varXi }$ on K. $(K, \sqsubseteq _K)$ is a totally ordered set.

For any $K \in \varXi /\mathord {\sim _H}$, we note $\langle K \rangle _H = \bigwedge _{\sqsubseteq _{\varXi }} K$ and $\langle \!\langle K \rangle \!\rangle _H = \bigvee _{\sqsubseteq _{\varXi }} K$.

Remark 36

From these results, it follows that $\forall p \in [\![1,|K|-1]\!]$ we have $\rho _{\varXi }^{p}(\langle K \rangle _H) \in K$. In particular, we have $\rho _{\varXi }^{|K|-1}(\langle K \rangle _H) = \langle \!\langle K \rangle \!\rangle _H$ whereas $\rho _{\varXi }^{|K|}(\langle K \rangle _H) \notin K$.

Property 37

Let $K \in \varXi /\mathord {\sim _H}$, $K \ne \{\infty \}$. Let $P = \rho _{\varXi }^{|K|}(\langle K \rangle _H)$. We have $P = \langle [P]_{\mathord {\sim _H}} \rangle _H$.

For any $K \in \varXi /\mathord {\sim _H}$, we consider $\langle K \rangle _H \in \varXi$ as canonical element, and we identify $\langle K \rangle _H = (X,v)$ with $X \in \varTheta$. We set $H = \varXi /\mathord {\sim _H}$.

Let $\sqsubseteq _H$ be the order on $\{\langle K \rangle _H \mid K \in H\} \subseteq \varXi$—and equivalently on H— induced by $\sqsubseteq _{\varXi }$.

Let $\rho _H : H \rightarrow H$ be the function defined by

$$\begin{aligned} \rho _H(K) = [\rho _{\varXi }^{|K|}(\langle K \rangle )]_{\sim _H} \end{aligned}$$

(13)

We define the relation $\blacktriangleleft _H$ on H, induced by the relation $\blacktriangleleft _{\varXi }$ on $\varXi$ by $K \blacktriangleleft _H \rho _H(K)$.

Definition 38

(Topological tree of shapes). The topological tree of shapes (or TS-tree, for brief) is the couple $\mathfrak {T}_{\textrm{TS}} = (H,\blacktriangleleft _H)$. See Fig. 3 (centre).

The following proposition directly derives from the two above properties.

Proposition 39

The equivalence relation $\sim _H$ induces a decreasing homeomorphism from $\mathfrak {T}_{\textrm{VS}} = (\varXi ,\blacktriangleleft _{\varXi })$ to $\mathfrak {T}_{\textrm{TS}} = (H,\blacktriangleleft _H)$.

Remark 40

The homeomorphism from $\mathfrak {T}_{\textrm{VS}} = (\varXi ,\blacktriangleleft _{\varXi })$ to $\mathfrak {T}_{\textrm{TS}} = (H,\blacktriangleleft _H)$ is a topologically lossless but a geometrically lossy compression. The structure of the tree $\mathfrak {T}_{\textrm{VS}} = (\varXi ,\blacktriangleleft _{\varXi })$ can be fully reconstructed from $\mathfrak {T}_{\textrm{TS}} = (\varTheta ,\blacktriangleleft _{\varTheta })$, but not the shapes of its nodes.

6 Links with Other Trees

The graph of valued shapes $\mathfrak {G}_{\textrm{VS}}$ presents a DAG structure, similarly to other morphological hierarchies, e.g. the component-graph [17], the directed component hierarchy [18] or the braid of partitions [8]. $\mathfrak {G}_{\textrm{VS}}$ is also organized via two kinds of relations, similarly to the component-hypertree [15] and the directed component hierarchy [18] (where the initial order can be split into two distinct orders).

But, contrary to these morphological hierarchies, $\mathfrak {G}_{\textrm{VS}}$ can be modeled as a tree structure, namely $\mathfrak {T}_{\textrm{VS}}$. This should open the way to efficient construction strategies, compared, e.g. to the component-hypertree [12], the component-graph [16] or the braid of partitions [29], whose construction remains complex and/or costly.

Beyond these considerations, the graph of valued shapes and the induced trees (trees of valued shapes, complete tree of shapes) also allow to unify various morphological trees.

With the notations introduced in Sect. 3, the max-tree (resp. min-tree) [24] of ${\mathcal {F}}$ is defined as $\mathfrak {T}_{\max } = (\varTheta _{\max },\blacktriangleleft _{\max })$ (resp. $\mathfrak {T}_{\min } = (\varTheta _{\min },\blacktriangleleft _{\min })$) with $\varTheta _{\max } = \varTheta ^\circ$ (resp. $\varTheta _{\min } = \varTheta ^\bullet$) and $\blacktriangleleft _{\max }$ (resp. $\blacktriangleleft _{\min }$) is the Hasse relation induced by the restriction of $\subseteq$ on $\varTheta _{\max }$ (resp. $\varTheta _{\min }$).

Proposition 41

There is a decreasing homeomorphism from the subgraph $(\varXi ^\circ , \vartriangleleft ^\circ )$ (resp. $(\varXi ^\bullet , \vartriangleleft ^\bullet )$) of $\mathfrak {G}_{\textrm{VS}}$ to the max-tree $\mathfrak {T}_{\max } = (\varTheta _{\max },\blacktriangleleft _{\max })$ (resp. the min-tree $\mathfrak {T}_{\min } = (\varTheta _{\min },\blacktriangleleft _{\min })$).

Proof

The proof is similar to that of Proposition 29 (Properties 22, 24, 26) by considering $\varXi ^\circ$ and $\varTheta ^\circ$ (resp. $\varXi ^\bullet$ and $\varTheta ^\bullet$) instead of $\varXi$ and $\varTheta$. $\blacksquare$

The adjacency tree [21] of a binary set $X \subset {\mathbb {U}}$ is defined as $\mathfrak {T}_{\text {adj}} = (\varTheta _{\text {adj}}(X), \blacktriangleleft _{\text {adj}})$ where $\varTheta _{\text {adj}}(X) = \varPi [X] \cup \varPi [\overline{X}]$ and $\blacktriangleleft _{\text {adj}}$ is the Hasse relation induced by the “surrounding” order relation on $\varTheta _{\text {adj}}(X)$.

Proposition 42

Let $v \in {\mathbb {V}}$. The subgraph $(\varTheta _v, \vartriangleleft ^v)$ of $\mathfrak {G}_{\textrm{VS}}$ is isomorphic to the adjacency-tree $\mathfrak {T}_{\textrm{adj}} = (\varTheta _{\textrm{adj}}(\varLambda ^\circ _v ({\mathcal {F}})), \blacktriangleleft _{\textrm{adj}})$.

Proof

This proposition directly derives from the equivalence of the definitions. $\blacksquare$

The tree of shapes [11] of ${\mathcal {F}}$ is defined as $\mathfrak {T}_{\text {shape}} = (\varTheta _{\text {shape}}, \blacktriangleleft _{\text {shape}})$ where $\varTheta _{\text {shape}} = \tau (\varTheta )$ and $\blacktriangleleft _{\text {shape}}$ is the Hasse relation induced by $\subseteq$ on $\varTheta _{\text {shape}}$. See Fig. 3 (right).

Proposition 43

There is a decreasing homeomorphism from the tree $(\varTheta , \blacktriangleleft _{\varTheta })$ to the tree of shapes $\mathfrak {T}_{\textrm{shape}} = (\varTheta _{\textrm{shape}}, \blacktriangleleft _{\textrm{shape}})$.

Proof

The proof is similar to that of Proposition 29 (Properties 22, 24 and Proposition 26) by considering $\varTheta$ instead of $\varXi$ and the equivalence relation on $\varTheta$ defined by $X \sim _S Y \Leftrightarrow \tau (X) = \tau (Y)$. $\blacksquare$

Remark 44

In [28], the notion of a topological monotonic tree was introduced, where “monotonic tree” has the same meaning as “tree of shapes”. However, the topological monotonic tree of [28] is indeed different from our topological tree of shapes. Unformally, the difference between both structures lies in the fact that our topological tree of shapes relies on a topological equivalence relation between the nodes of the complete tree of shapes, whereas the topological monotonic as defined in [28] relies on a similar equivalence relation between the external border of the nodes. From [28], there is a decreasing homeomorphism from the tree of shapes to the topological monotonic tree. It can be proved that there is also a decreasing homeomorphism from our topological tree of shapes to the topological monotonic tree. These links are not formalized here by lack of room; they will be more deeply investigated in our further works.

The following result derives from the above propositions and properties.

Property 45

We have

$$\begin{aligned} |H|&\le |\varTheta | \le |\varXi | \le (|{\mathbb {S}}|+1).|{\mathbb {V}}| \end{aligned}$$

(14)

$$\begin{aligned} |\varTheta _{\textrm{shape}}|&\le |\varTheta | = |\varTheta _{\max }| + |\varTheta _{\min }| - 1 \le 2.|{\mathbb {S}}| \end{aligned}$$

(15)

7 Concluding Remarks and Perspectives

This article gathers some preliminary results about the notions of graph/tree of valued shapes and complete/topological tree of shapes. These notions shed a new light on well known morphological hierarchies, namely the component-tree and the tree of shapes. In particular they allow to unifiy and extend these notions and to link them to topological invariants related to the adjacency tree, the deletable sets and—under favourable hypotheses—the homotopy type. We believe that these structures constitute a promising subject of research in the framework of morphological hierarchies. At this stage, our introductive study focused only on the structural side of these notions.

Our perspective works will also consider the algorithmic aspects, in particular the way to build these structures efficiently. Due to their strong links with the component-tree, it is possible to propose first, naive strategies to build the graph and then the tree of valued shapes from the min- and max-trees [2], and then to derive the complete and topological trees of shapes. It is also possible to start from the construction of the tree of shapes [7] to derive the same structures. However, such approaches, although tractable, are not optimal, and seeking dedicated construction algorithms makes sense.

We initially designed the graph of valued shapes by “mixing” the min-/max-trees and adjacency trees with a precise idea in mind. Our purpose was to develop conceptual tools that would allow one to carry out the topological analysis of objects in non-binary paradigms (e.g. for grey-level images or fuzzy modeling). In this regard, our next step will be to investigate the links that exist between these new structures and frameworks developed in topological analysis, especially with respect to grey-scale topology [5] and to homology persistence and Morse theory [1].

More generally, we also believe that these new structures could be useful for developing approaches dedicated e.g. to homotopic morphology, topological compression or topological comparison.