Connected Filters on Generalized Shape-Spaces

Le Duy Huỳnh, Nicolas Boutry*, Thierry Géraud

EPITA Research and Development Laboratory (LRDE), 14-16 rue Voltaire, F-94270 Le Kremlin-Bicêtre, France

**Abstract**

Classical hierarchical image representations and connected filters work on sets of connected components (CC). These approaches can be defective to describe the relations between disjoint objects or partitions of images. In practice, objects can be made of several connected components in images (due to occlusions for example), therefore it can be interesting to be able to take into account the relationship between these components to be able to detect the whole object. In Mathematical Morphology, second-generation connectivity (SGC) and tree-based shape-spaces study this relation between the connected components of an image. However, they have limitations. For this reason, we propose in this paper an extension of the usual shape-space paradigm into what we call a Generalized Shape-Space (GSS). This new paradigm allows us to analyze any graph of connected components hierarchically and to filter them thanks to connected operators.

*Keywords*: Mathematical Morphology; connected operators; tree-based representations; tree of shapes; alpha-tree; hyper-connectivity.

**1. Introduction**

The notions of connectivity and of connected components (CCs) are essential in mathematical morphology for image processing and image analysis (Serra (1988)). In the case of 2D images, the classical 4- or 8-connectivities are usually used.

Using these notions, a family of morphological operators that focuses on attributes of CC's rather than individual elements has been developed. These operators are known as attribute filters (Breen and Jones (1996); Westenberg et al. (2007); Ouzounis and Wilkinson (2011)), connected filters (Jones (1999)) or connected operators (Serra and Salembier (1993); Salembier and Serra (1995); Salembier and Wilkinson (2009)). They remove

connected components of the image, so they cannot create new extrema nor shift contours. Their edge-preserving property is desirable in many applications.

Whereas the first connected operators in the literature relied on classical morphological filtering followed by a reconstruction procedure, many connected operators now compute from the input image a tree-based representation of this image. With this new representation, connected operators can be defined by removing unwanted nodes in the tree, the filtered image being reconstructed from the simplified tree.

Classical connectivities have a limitation. Because an image is a partial representation of the real world, an object can be represented by several CCs in the image (due to occlusions for example). Thus, a set of CCs can mistakenly be treated as distinct objects, instead of parts of the same object. To handle this problem, a well-established approach known as second-generation connectivity (Serra

<footnote>*Corresponding author: Phone: +33 1 53 14 59 47;
Email address: nicolas.boutry@lrde.epita.fr (Nicolas Boutry)</footnote>
<figure><img src="image_1.png" /><figcaption>Figure 1: Generalized shape-space filtering scheme.</figcaption></figure>

(1996); Braga-Neto and Goutsias (2002) (called SGC for short) uses morphological operators to define a second connectivity class. The first SGC approaches use structuring elements (SE), which limit how the image domain can be connected. The mask-based SGC, introduced in Ouzounis and Wilkinson (2007), cancels this dependency by using a mask. In these two approaches, it is sometimes difficult to define a sequence of morphological operators or a specific mask that allows us to extract all object clusters. Furthermore, we cannot represent the fact that there exist different levels of hierarchies in images: we can have different letters, each made of several connected components when words are made of several letters (different levels of abstraction).

For this reason, we introduce in this paper a new approach which is able to group in a hierarchical way CC's that are distant from each other. This approach is inspired by the tree-based shape-space (Xu et al. (2016)). The main contributions of our approach are: (1) an extension of the shape-space paradigm, namely the Generalized Shape-Space (GSS), that encodes the relationship between nodes of a tree-based image representation (this GSS will be analyzed hierarchically thanks to a second tree-based representation), (2) a new procedure capable of reconstructing the GSS, and consequently, reconstructing the image from the filtered second tree (this reconstruction procedure is more flexible than the one proposed in Xu et al. (2016) because we can apply any tree-filtering strategies available to the framework of tree-based connected operators), (3) some results showing that the GSS can be used to retrieve sets of CC's that represent (broken) objects in images; note that our approach can easily be used for object extraction or image simplification (see Fig. 1).

The paper is organized as follows: in Section 2, we recall the definitions of connected operators and second generation connectivities. We will also expose some drawbacks and limitations of SGC and tree-based shape-spaces. Then, Section 3 introduces our generalized shape-space (GSS) and shows how we can use connected filters on it. In Section 4, we present how to apply GSS to represent hierarchically object clusters in images, and in Section 5, we show some applications of our new paradigm. Finally, we conclude in Section 6.

## 2. Background

In this section, we briefly recall related concepts, notably the tree-based shape-space and second generation connectivity, and discuss their limitations. For more detail, we recommend Xu et al. (2016) and Salembier and Wilkinson (2009).

A graph $(V, E)$ is a pair defined as a set of vertices $V$ (defined in some space) and a set of edges $E \subseteq V \times V$. Two vertices $v_1, v_2$ such that $(v_1, v_2)$ belongs to $E$ are said to be neighbors. A graph $G = (V, E)$ is said to be connected if $\forall x, y \in V$, there exists a path $\pi(x, y) = (p_1 = x, \dots, p_i, \dots, p_N = y)$ which verifies that every $p_i$ belongs to $V$ and any pair $(p_i, p_{i+1})$ belongs to $E$. A set of vertices $X \subseteq V$ is said to be connected (in $G$) if the induced subgraph $G_X = (X, E_X)$ with $E_X = X \times X \cap E$ is connected. A connected component of $X$ is a connected subset of $V$ which is maximal in the inclusion sense.

An image $I$ is a triplet $(V, E_I, f_I)$ corresponding to a graph $(V, E_I)$ supplied with a color function $f_I: V \to \mathbb{V}$. In practice, $V$ is equal to $\mathbb{Z}^n$, $(V, E_I)$ is connected as a graph and the value space $\mathbb{V}$ is equal to $\mathbb{R}^N$ with $N \in \{1, 3\}$ depending on whether we work with grayscale or color images.

### 2.1. *Connected operators*

Connected operators were first defined for binary images with the introduction of opening by reconstruction (Klein (1976)) of the foreground. Their extension to grayscale images is based on flat zones (Serra and Salembier (1993)). Connected operators work with CC's: they remove these components and change their associated value in such a way that they do not create extrema nor shift the contours. Consequently, they do not create
new structures in the image. From a higher level stand-
point, such operators could be implemented by construct-
ing and filtering a tree-based image representation.

2.1.1. Tree-based image representations

A tree-based image representation $T = (R, \subseteq)$ of an image $I = (V, E_I, f_I)$ is a connected poset of non-empty disjoint or nested CC's of $V$ supplied with the inclusion relationship $\subseteq$.

The first family of tree-based image representation is made of hierarchies of segmentations (see the Binary Partition Tree in Salembier and Garrido (2000)), and of hierarchies of quasi-flat zones (see Meyer and Maragos (2000)) or α-trees (see Ouzounis and Soille (2011, 2012)). These representations are usually computed in a bottom-up fashion: starting from a partition of the image, some neighbors are iteratively connected until we have only one CC covering the whole domain of the image.

The second family of tree-based representation are threshold decompositions. When the value space X of the image is supplied with a total order <, the lower and upper level sets at level λ are defined respectively by: [f_I < λ] = {ν ∈ V | f_I(ν) < λ} and [f_I ≥ λ] = {ν ∈ V | f_I(ν) ≥ λ}. The min-tree (resp. max-tree) (Hanusse and Guillataud (1992); Jones (1997); Salembier et al. (1998); Carlinet and Géraud (2014)) codes the inclusion relationship between the connected components of all possible lower (resp. upper) threshold sets: R< = ∪<λ CC([f_I < λ]) and R≥ = ∪<λ CC([f_I ≥ λ]). The tree of shapes (ToS) (Caselles and Monasse (2010); Géraud et al. (2013)) is a fusion of the min-tree and the max-tree. It is the hierarchy induced by the saturated connected components of the lower and upper threshold sets R = { Sat(Γ); Γ ∈ R< ∪ R≥ } .

A tree-based image representation $T$ is usually supplied
with a function $F: R \to V$ so that $T$ is an equivalent
representation of $I$; that is, $I$ can be reconstructed from
the triplet $(T, \subseteq, F)$.

2.1.2. Tree-based implementation of connected operators

When implementing connected operators using trees,
the image contents are first mapped into a tree-based
representation. The choice of the tree is often driven
by the application and the input image contents (for in-
stance, when dealing with a text document image with

dark text over a bright background, the min-tree contains
the components of the characters). The nodes of the tree
$T = (R, \subseteq)$ will then be weighted using an attribute func-
tion $\mathcal{A}: R \to \mathbb{R}$. The attribute $\mathcal{A}(R)$ of a region $R$ can
be the value of the pixels corresponding to $R$ in the initial
image, or the area of $R$, or more complex measures such
as the compactness (Montero and Bribiesca (2009)), the
elongation (Westenberg et al. (2007)) of $R$, and so on.

Image filtering is a process of selected tree node removal depending on the associated $\mathcal{A}$. In the case of trees encoding the image decomposition with connectivity criteria as in Serra (1988), tree filtering can be divided into two classes: pruning and non-pruning (Urbach et al. (2007)). We call a method a “tree pruning” strategy if it removes the whole sub-trees associated to some nodes in the tree, and we call it a “non-pruning” strategy otherwise. In the latter case, some descendants of a filtered node can be preserved. Please note that the differentiation between “pruning” and “non-pruning” does not apply to $\alpha$-trees; it only makes sense for threshold-based trees (min-tree, max-tree, and tree of shapes).

When the attribute function $\mathcal{A}$ is increasing (which
means that $\forall C_i, C_j \in R$, $C_i \subseteq C_j \Rightarrow \mathcal{A}(C_i) \le \mathcal{A}(C_j)$),
the tree filtering is easy to implement: when a node is
removed, it means that its attribute fails to satisfy some
criteria, and all its descendants fail in the same manner. It
always leads to a pruning strategy. When $\mathcal{A}$ is not increas-
ing, several tree-filtering strategies exist. Three tree prun-
ing strategies (Min, Max, and Viterbi) and a non-pruning
(direct rule) one were proposed in Salembier et al. (1998).
Some other non-pruning strategies were introduced in Ur-
bach et al. (2007) (subtractive rule), and in Ouzounis and
Wilkinson (2011) (k-subtractive and absorption rules).

2.1.3. *Connected filtering on tree-based shape-space*

When using tree-based connected operators, three main
approaches are possible:

1. The local non-pruning approaches (see Salembier et al. (1998)) (by “locality” we mean that the decision to preserve or not a node depends only on the attribute of this node).

2. The pruning approaches, which are by definition based on a non-local criterion: the decision whether to filter a node or not depends on whether its ancestors and descendants satisfy some criterion. This
way, we cannot preserve two nodes in the same branch when we remove all the nodes between them (the merge of monotonic branches usual in tree simplification is then incompatible with this scheme).

3. The non-local non-pruning approaches (see the shaps- ings detailed in Xu et al. (2016)): from some tree $T = (R, \subseteq)$ computed on a given image $I$ seen as a graph, we compute a new graph $G = (R, E_G)$ with the same structure/topology as $T$, that is, the directed edges of $T$ (representing the parenthood relation- ship) become undirected edges (representing then a neighborhood relationship). From $G$, a second tree $\mathcal{T} = (\Re, \subseteq)$ is computed. In practice, this tree is a max- or min-tree. Then, $\mathcal{T}$ is weighted by some attributes, and then filtered by a pruning approach. From the remaining tree $\mathcal{T}' = (\Re', \subseteq)$, we construct the graph $G' = (R', E_{G'})$ that $\mathcal{T}'$ represents, from which we deduce the tree $T' = (R', \subseteq)$ (thanks to the inclusion relationship of the elements of $R'$), and then we finally obtain $I'$, the filtered version of $I$. The set of regions $R'$ is obtained thanks to the following equation (Xu et al. (2016)):

$$R' = R \setminus \bigcup_{C \in \Re \setminus \Re'} C. \qquad (1)$$

Notice that in the last approach, we compute a tree- based representation on (the graph induced by) another tree-based representation, which corresponds to an ab- straction of order two. However, imagine now that we select a node in the filtered tree $\mathcal{T}'$; the region in the image corresponding to this node will be connected, which is a strong limitation. Moreover, Eq. 1 implies that a pruning strategy has been used on $\mathcal{T}$. To overcome these limita- tions, we will see next how we can extend the paradigm of tree-based shape-spaces to graph-based shape-spaces (GSS) by changing the connections between nodes in $G$, how we can proceed to non-pruning strategies in the new shape-space $\mathcal{T}$ computed from the modified $G$, and this way how we can extract (sets of) disconnected objects from images.

Lastly, note that all these more or less sophisti- cated filtering strategies are essentially relevant for non- increasing criteria.

## 2.2. Second-generation connectivities (SGC's)

Let us now recall what the clustering-based and mask- based second generation connectivities are. In brief, they permit the retrieval of groups of related CC's in images when their relative distance is small, which is a good ap- proach when objects are made of several connected com- ponents due, for example, to occlusions.

An important drawback of the usual 4- and 8- connectivities is that when we try to segment objects in images supplied with these connectivities, we often get a large component made of several objects, when we would like to obtain several connected components correspond- ing to the same object instead.

The paradigm known as second-generation connectiv- ity (SGC) (Serra (1996); Ronse (1997)) is an interesting solution to this problem. In particular, the mask-based SGC (Ouzounis and Wilkinson (2007)), coming from a fusion of the clustering-based and the contraction-based SGC, has fewer limitations compared to both these ap- proaches when considered individually, and better serves our goal. More details about these connectivities can be found in Wilkinson and Ouzounis (2010).

The clustering-based SGC (Ouzounis and Wilkinson (2006)) defines a child connectivity class based on a struc- tural operator $\psi$: a set of CC's in the image $I$ is seen as a single cluster if they are included in a same connected component of $\psi(I)$ and the size of some chosen struc- turing elements controls the maximum distance separat- ing two CC's which belong to the same cluster. How- ever, $\psi$ must satisfy many constraints like those detailed in Ouzounis and Wilkinson (2007).

Mask-based SGC allows us to get rid of this depen- dency on a structural operator $\psi$: it encodes the (hyper-)connectivity defined in the image thanks to a mask $M$, computed from $I$ like in Ouzounis and Wilkinson (2007). This computation can be based on alternating-sequential filters (ASF) (Heijmans (1997)) or on Minkowski addi- tions. Furthermore, in Ouzounis and Wilkinson (2007) and in Salembier and Wilkinson (2009), the authors sug- gest that the mask could also be an image of the same scene, obtained at different wavelengths or with different modalities.

In both clustering-based and mask-based SGC's, an op- erator or a mask only corresponds to a class of cluster.
<figure><img src="image_2.png" /><figcaption>Figure 2: An example of segmentation based on our method: here, the first tree is a ToS and the second tree is an α-tree.</figcaption></figure>

However, sometimes object clusters should be considered hierarchically, e.g., some CC's that represent parts of objects form a “broken” object, some related “broken” objects form an object cluster. In such a case, a new mask must be defined for each level of abstraction. Our approach is devoted to tackling this problem and to capturing this hierarchical structure of sets of objects, each one being a set of connected components in the image.

### 3. Generalized shape-space (GSS)

The initial tree-based shape-space approach of Xu et al. (Xu et al. (2016)) only permits the retrieval of connected regions in the image. To overcome this limitation, we propose to adding/removing connections between the nodes of the graph induced by $T = (R, \subseteq)$ (cf. the procedure described before) which satisfy some particular constraints (like alignment or neighborhood relationship between shapes) to obtain a new graph $G = (R, E_G)$ (see Figure 2). We call this new representation the Generalized Shape-Space (GSS); note that the tree-based shape-space (Xu et al. (2016)) can be seen as a particular case of our GSS.

When $G$ is complete, its number of edges reaches the value $|R|(|R| - 1)/2$, which is hard to manage in practice. For this reason, we connect only nodes which satisfy some meaningful relationship among the following ones:

**Neighborhood relationship:** We can assume that elements of a cluster are relatively close to each other. In this

case, we connect the nodes of $G$ corresponding to components in the image which are close to each others. Note that the maximum distance parameter can be fixed relatively to the size of the components.

**Alignment relationship:** We can also assume that the parts of an object, or that the objects of the same cluster, are aligned together (as in text detection, when we seek the windows in a building, or in crosswalk marking).

**No-parenthood relationship:** When two nodes in $T$ are parents, either they belong to the same object at different scales, or they do not belong to the same object and they correspond to structures in the image which are not related. In other words, we possibly want to compute the complement of $G$ in $R \times R$ so that only the nodes which are not parents in $T$ will be connected in $G$. To limit the complexity of this new graph, we will generally restrict the connections to aligned or nearby components in the image like described before.

#### 3.1. GSS segmentation

We could proceed to the segmentation of $G$: we initialize the nodes of $G$ to 1 when they correspond to the parts of the broken object (or the cluster of objects) we are looking for; otherwise we initialize them to 0. Two approaches are then possible. Either we use node-weighted graphs and nodes are weighted by some attribute, or we use edge-weighted graphs and we use some dissimilarity function (based on color, size, or dimensions). In particular, we could use graph cuts (Boykov and Funka-Lea (2006)) or graph convolutional networks (Kipf and Welling (2017)).
However, this approach has limitations because it is not progressive. For this reason, it can be more flexible and efficient to propose a hierarchical segmentation of G. In order to achieve that, we will compute some tree on G (like a min-tree, a max-tree, or a ToS), following the idea presented in Xu et al. (2016).

## 3.2. GSS methodology

Our method is the following: first, from an image $I = (V, E_I, f_I)$, we compute some tree $T = (R, \subseteq, F, A)$ (where A is the attribute function defined on the nodes of T), which we transform into the graph $G = (R, E_G, F, A)$ by adding/removing some connections in the graph induced by T. Second, we compute a new hierarchical representation $\mathcal{T} = (\mathcal{R}, \subseteq, \mathcal{F}, \mathcal{A}, A)$ from G. Third, we filter $\mathcal{T}$ in some way depending on the application to obtain a simplified tree $\mathcal{T}' = (\mathcal{R}', \subseteq, \mathcal{F}')$. Then, the filtered graph $G' = (R', E_{G'}, F')$ is constructed from $\mathcal{T}'$ using the following formulas:

$$ 
\begin{aligned}
R' &= \bigcup_{n \in \mathcal{R}'} n \\
E_{G'} &= E_G \cap R' \times R' \\
\forall r \in R', F'(r) &= \mathcal{F}'(\bigcap \{n \in \mathcal{R}' | r \in n\}).
\end{aligned} 
\quad (2) 
$$

Then, $T' = (R', \subseteq, F')$ is easily deduced from $G'$: since we have $R' \subseteq R$, two components of $R'$ are either disjoint or nested. Finally, $I' = (V', E_{I'}, f_{I'})$ is computed from $T'$ using the formulas:

$$ 
\begin{aligned}
V' &= \bigcup_{r \in R'} r \\
E_{I'} &= E_I \cap V' \times V' \\
\forall p \in V', f_{I'}(p) &= F'(\bigcap \{r \in R' | p \in r\}).
\end{aligned} 
\quad (3) 
$$

Assuming that an object in I is made of several nodes of T, and that we succeeded in connecting/disconnecting these nodes in G so that this same object will be represented by a CC (resp. an α-CC) of G (see Fig. 2), we will be able to extract this object by constructing $I'$ from the filtered ToS (resp. α-tree) $\mathcal{T}'$.

Note that Equations 2 and 3 are new and allow us to construct the filtered image from $\mathcal{T}'$. It complements the strategy of Xu et al. where the condition to use Eq. 1 was to use only pruning on $\mathcal{T}'$.

# 4. Object retrieval based on GSS

We propose now the following methodology to extract disconnected/broken objects from a grayscale or color image I:

* Depending on the value space $\mathbb{V}$ of the input image, we compute either a ToS (Géraud et al. (2013)) or a color ToS (Carlinet and Géraud (2015)) of I.

* We extract the more salient level lines by minimizing the Mumford-Shah functional by methods described in Xu et al. (2013) and in Carlinet and Géraud (2015) (in practice we choose $\lambda = 1000$ for color images and $\lambda = 300$ for grayscale ones).

* We apply a grain filter to remove nodes whose area is under some given threshold (in practice we choose the threshold value $a = 3$).

* We compute the graph G using the relationships described before.

* We use some dissimilarity function to evaluate the edges of G (based for example on the difference of intensity values).

* We compute the α-tree of G (see Najman et al. (2013) for its implementation).

At the end, packs of (joint or disjoint) nearby homogeneous areas in G will be represented by a node in $\mathcal{T}$, and then we will be able to reconstruct separately broken objects in the image. Let us detail this procedure.

## 4.1. Advantages of the ToS

We choose the tree of shapes for our first tree due to its interesting properties: it is self-dual (it describes the dark and bright parts of the image in the same fashion) and it is invariant relatively to the contrast variations. Furthermore, the inclusion of the level-lines (encoded by this tree) can help us to deduce the background/object relationship between image regions. Depending on the given image (grayscale or color), we will use the ToS (Géraud et al. (2013)) or the cToS (Carlinet and Géraud (2015)).

Possibly, we can apply a simplification procedure on $\mathcal{T}$ using the methodology described in Xu et al. (2013).
or Carlinet and Géraud (2015): this simplification aims to reduce the graph complexity by removing the leaves that are considered as being noise, removing nodes that represent less important level-lines thanks to the minimization of the Mumford-Shah functional (i.e., we keep only salient level-lines). Note that we take care not to oversimplify *T*, so that we preserve the structures of the “broken” objects in the image: when we consider them independently, they can be misclassified as noise.

## 4.2. The α-tree

When *G* is built, the next step is to hierarchically segment it thanks to the second tree *T*. Since the goal is to group related CC's as deeply as possible into *T*, we compute an α-tree.

Concerning the dissimilarity function, we use absolute difference for grayscale images and the CIELAB $\Delta E^*$ operator (Alman (1993)) for color images in the $L^*a^*b^*$ space (but we can also imagine to use height similarities (Huỳnh et al. (2016)), a “learned” dissimilarity, or to apply some penalty based on the distance between CC’s)

# 5. Experiments and discussion

In this section, we present some comparisons between our GSS approach and clustering/mask-based SGC ones.

## 5.1. Segmenting filamentous objects in images

Now, let us show the efficiency of our approach to extract filamentous objects (in the first case, a protein chain, and in the second case, some Anabaena complexes). They are disconnected components over a noisy background. The input images and a part of the results are extracted from Ouzounis and Wilkinson (2007) (we detail in the caption which part of the figure is new).

According to Ouzounis *et al.* (see Ouzounis and Wilkinson (2007)), clustering-based SGC is not adapted to protein chain segmentation while mask-based SGC gives good results (see first row of Fig. 3). To test our method, we propose to compute a (grayscale) ToS *T* simplified by a grain filter with a parameter *a* = 3 and using a minimization of a Mumford-Shah functional to keep only the most salient level-lines (we choose $\lambda$ = 300). The neighborhood relationship is then used to compute *G*: if two components are closer than 1.4 times their bounding

box size, they are considered as neighbors. To weight the edges of *G* (for the computation of *T*)), we use a dissimilarity function based on the colors of the CC's, and we apply a penalization based on the distance between their bounding boxes' center. We see in Fig. 3(f) that the protein chain is correctly segmented.

In Fig.4, we have several Anabaena complexes. The largest complex is made of two segments separated by a heterocyst. A connected component approach using 4-connectivity can only detect the larger segment, while the clustering-based SGC is able to segment the whole complex. However, in order to retrieve the two other complexes in the image, we have to perform the whole operation again and with different criteria. With our method, all Anabaena complexes are represented in the α-tree, and each one can be extracted easily thanks to our hierarchical representation. Please note that in this result we only use Fig. 3(b) and Fig. 3(c) to demonstrate the difference between regular versus clustering-based connectivities.

## 5.2. Text detection in natural images

In Figure 5, we show the efficiency of our GSS to detect text in natural color images. For the computation of the cToS *T* and its simplification, we use the same procedure as before. Since we can assume that characters are horizontally aligned, the alignment relationship is used to compute *G*. We also use a neighborhood criterion: we assume that the maximal distance between two CC's is equal to the height of the CC's multiplied by a factor of 2. In the first column of Fig.5, we expose the input images. In the second column, we can see that due to the homogeneity of its background, the first image can be easily segmented using a cToS, when the second image is a much more complicated case due to the heterogeneity of the texture of its background; furthermore, the letters are broken in several components. In the third column, we observe that our approach succeeds in segmenting the characters correctly thanks to the computation of the α-tree of *G* (we used the not-parenthood relationship in addition of the neighborhood and the alignment relationships).

Thanks to our new representation *T*, we can segment a picture at different hierarchical levels: in Fig. 6, we first label the different parts of the letters ($\alpha$ = 0), then we can group them into letters ($\alpha$ = 0.06), and then we can
group these letters into words ($α$ = 0.12). This shows the powerfulness of our new paradigm.

## 6. Conclusion

Connected operators are morphological filters which preserve contours in images. The tree-based shape-space filtering is an interesting framework to synthethize such filters. However, connected operators usually rely on direct connectivities, which are often too much rigid to extract object clusters. In this paper, we present an extension of the framework of tree shape-spaces; we called it generalized shape-space (GSS) and this approach removes strong limitations induced by the tree-based framework. Indeed, the GSS is able to build any desired relationship between components in images. Moreover, the usual filters used in the tree-based shape-space can also be applied to the generalized one.

The other approaches based on second generation connectivity (relating regions which are far away from each others) like the cluster-based SGC or the mask-based SGC have strong limitations due to their dependency to operators. On the contrary, our approach is able to consider the hierarchical nature of object clusters in images thanks to its abstraction order of two: we can segment sets of nested connected components corresponding to objects and also sets/clusters of objects. As depicted in the last figures, our methodology is efficient in matter of filamentous objects in natural images. Furthermore, the closer we are to the leaves in the second-order hierarchical representation, the more the nodes correspond to strongly related objects in the image, which gives a progressive and flexible tool for image processing and filtering.

As future work, we will study how much groups of objects of interest can be extracted from the second hierarchical representation using markers (Salembier and Garido (2000)), we will consider how we can use learned attributes to weight the GSS *G*, we will test the superpixels frameworks instead of trees to compute *G*, and we will try graph-segmentation algorithms like graph cuts or graph convolutional networks (Duvenaud et al. (2015)).

**Acknowledgments:** The authors would like to warmly thank Isabelle Bloch, Hugues Talbot, and Yongchao Xu for the fruitful discussions we had about this work, and the reviewers for their relevant comments.

## References

Alman, D.H., 1993. CIE technical committee 1-29, industrial color-difference evaluation progress report. Color Research & Application 18, 137-139.

Boykov, Y., Funka-Lea, G., 2006. Graph cuts and efficient $n$-d image segmentation. International Journal of Computer Vision 70, 109-131.

Braga-Neto, U., Goutsias, J., 2002. Connectivity on complete lattices: New results. Computer Vision and Image Understanding 85, 22-53.

Breen, E.J., Jones, R., 1996. Attribute openings, thinings, and granulometries. Computer Vision and Image Understanding 64, 377-389.

Carlinet, E., Géraud, T., 2014. A comparative review of component tree computation algorithms. IEEE Transactions on Image Processing 23, 3885-3895.

Carlinet, E., Géraud, T., 2015. MToS: A tree of shapes for multivariate images. IEEE Transactions on Image Processing 24, 5330-5342.

Caselles, V., Monasse, P., 2010. Geometric description of images as topographic maps. volume 1984 of Lecture notes in mathematics. Springer.

Duvenaud, D.K., Maclaurin, D., Iparraguirre, J., Bambarell, R., Hirzel, T., Aspuru-Guzik, A., Adams, R.P., 2015. Convolutional networks on graphs for learning molecular fingerprints, in: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R. (Eds.), Advances in Neural Information Processing Systems 28. Curran Associates, Inc., pp. 2224-2232.

Géraud, T., Carlinet, E., Crozet, S., Najman, L., 2013. A quasi-linear algorithm to compute the tree of shapes of $n$-D images., in: Mathematical Morphology and Its Application to Signal and Image Processing - Proceedings of the International Symposium on Mathematical Morphology (ISMM). Springer. volume 7883 of Lecture Notes in Computer Science, pp. 98-110.

Hanusse, P., Guillataud, P., 1992. Fractal Geometry and Computer Graphics. Springer-Verlag. chapter Dentronic Analysis of Pictures, Fractals and other Complex Structures. Beiträge zur Graphischen Datenverarbeitung, pp. 203-216.
Heijmans, H., 1997. Composing morphological filters. IEEE Transactions on Image Processing 6, 713–723.

Huỳnh, L.D., Xu, Y., Géraud, T., 2016. Morphology-based hierarchical representation with application to text segmentation in natural images, in: Proceedings of the International Conference on Pattern Recognition (ICPR), pp. 4029–4034.

Jones, R., 1997. Component trees for image filtering and segmentation, in: Proceedings of IEEE Workshop on Nonlinear Signal and Image Processing, p. 5.

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

Kipf, T.N., Welling, M., 2017. Semi-supervised classification with graph convolutional networks. Proceedings of International Conference on Learning Representations (ICLR), 1–14.

Klein, J.C., 1976. Conception et réalisation d'une unité logique pour l'analyse quantitative d'images.

Meyer, F., Maragos, P., 2000. Nonlinear scale-space representation with morphological levelings. Journal of Visual Communication and Image Representation 11, 245–265.

Montero, R.S., Bribiesca, E., 2009. State-of-the-art of compactness and circularity measures. In International Mathematical Forum, 31.

Najman, L., Cousty, J., Perret, B., 2013. Playing with Kruskal: Algorithms for morphological trees in edge-weighted graphs, in: Mathematical Morphology and Its Application to Signal and Image Processing – Proceedings of the International Symposium on Mathematical Morphology (ISMM). Springer. volume 7883 of *Lecture Notes in Computer Science*, pp. 135–146.

Ouzounis, G.K., Soille, P., 2011. Pattern spectra from partition pyramids and hierarchies, in: Mathematical Morphology and Its Application to Signal and Image Processing – Proceedings of the International Symposium on Mathematical Morphology (ISMM), Springer. pp. 108–119.

Ouzounis, G.K., Soille, P., 2012. The Alpha-Tree Algorithm: Theory, Algorithms, and Applications. JRC Technical Reports JRC74511, EUR 25500 EN. Joint Research Centre, European Commission. Luxembourg.

Ouzounis, G.K., Wilkinson, M.H., 2006. Filament enhancement by non-linear volumetric filtering using clustering-based connectivity, in: Proceedings of International Workshop on Intelligent Computing in Pattern Analysis and Synthesis, Springer. pp. 317–327.

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

Ouzounis, G.K., Wilkinson, M.H.F., 2011. Hyperconnected attribute filters based on k-flat zones. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 224–239.

Ronse, C., 1997. Set-theoretical algebraic approaches to connectivity in continuous or digital spaces. Journal of Mathematical Imaging and Vision, 18.

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

Salembier, P., Oliveras, A., Garrido, L., 1998. Antiextensive connected operators for image and sequence processing. IEEE Transactions on Image Processing 7, 555–570.

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

Salembier, P., Wilkinson, M.H., 2009. Connected operators. IEEE Signal Processing Magazine 26, 136–157.

Serra, J., 1988. Image analysis and mathematical morphology: Theoretical advances. Academic Press.

Serra, J., 1996. Connectivity on complete lattices, in: Maragos, P., Schafer, R.W., Butt, M.A. (Eds.), Mathematical Morphology and its Applications to Image and Signal Processing. Springer US. volume 5, pp. 81–96.
Serra, J., Salembier, P., 1993. Connected operators and pyramids, in: Proceedings of Image Algebra and Morphological Image Processing IV, SPIE. p. 12.

Urbach, E.R., Roerdink, J.B., Wilkinson, M.H., 2007. Connected shape-size pattern spectra for rotation and scale-invariant classification of gray-scale images. IEEE Transactions on Pattern Analysis and Machine Intelligence 29, 272–285.

Westenberg, M.A., Roerdink, J.B.T.M., Wilkinson, M.H.F., 2007. Volumetric attribute filtering and interactive visualization using the max-tree representation. IEEE Transactions on Image Processing 16, 2943–2952.

Wilkinson, M.H., Ouzounis, G.K., 2010. Chapter 5—Advances in connectivity and connected attribute filters, Elsevier. volume 161 of *Advances in Imaging and Electron Physics*, pp. 211–275.

Xu, Y., Géraud, T., Najman, L., 2013. Salient level lines selection using the Mumford-Shah functional, in: Proceedings of IEEE International Conference on Image Processing, pp. 1227–1231.

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

<figure><img src="image_3.png" /><figcaption>Figure 3: Top row (from Ouzounis and Wilkinson (2007)): (a) The original image *I*, Results of (b) clustering-based SGC using *I* • □<sub>5×5</sub>, (c) Mask-based SGC using ((*I* • □<sub>5×5</sub>) ◦ □<sub>5×5</sub>) • □<sub>11×11</sub> as the mask, where • and ◦ denote respectively the closing and opening operators and the square □<sub>S×S</sub> of size *S* is the structuring element. An elongated filter with threshold value equal to 3 has been applied to (b) and (c). Bottom row: results of our GSS (d) labeling of the nodes of the grayscale ToS, (e) the largest 0.4-CC in the neighborhood shape-space that does not contain the root followed by a filter that removes CC's whose area is smaller than 5% of the largest one in this cluster. (f) extraction of the protein chain.</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Figure 4: Top row (from Ouzounis and Wilkinson (2007)): (a) the original image, (b) the filtered image using an area criterion relying on the 4-neighborhood relationship and (c) clustering-based SGC. Bottom row: results of our GSS (d) the labeling map of the grayscale ToS obtained by reconstructing the image from *T*' using random colors, (e) the 0.25-CC's of *G*', (f) the simplified image *I* whose values are set at the mean of the remaining region.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 5: First column: the input image, Second column: the segmentation using a cToS, Third column: the extraction resulting from the α-tree computation on *G*.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 6: (a) the input image, (b), (c), (d) are the reconstructions of the filtered tree $T$ for respectively $\alpha = 0, \alpha = 0.06$, and $\alpha = 0.12$ ($\tilde{\mathcal{N}}'$ maps one different color for each node of $T'$).</figcaption></figure>