# Hierarchy-based fuzzy segmentation and marker learning layer: theory and algorithms

Gabriel Barbosa da Fonseca, Romain Negrel, Benjamin Perret, Jean Cousty, Silvio J.F. Guimarães

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

To cite this version:

Gabriel Barbosa da Fonseca, Romain Negrel, Benjamin Perret, Jean Cousty, Silvio J.F. Guimarães. Hierarchy-based fuzzy segmentation and marker learning layer: theory and algorithms. 2025. hal-05040261

HAL Id: hal-05040261

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

Preprint submitted on 23 Jun 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Hierarchy-based fuzzy segmentation and marker learning layer: theory and algorithms

Gabriel Barbosa da Fonseca¹,²*, Romain Negrel³, Benjamin Perret²,
Jean Cousty², Silvio Jamil F. Guimarães¹

¹Laboratory of Image and Multimedia Data Science, Pontifical Catholic University of Minas Gerais, Brazil, 31980-110.

²LIGM, Université Gustave Eiffel, CNRS, ESIEE, Paris, F-77454 Marne-la-Vallée.

³ESIEE Paris, Université Gustave Eiffel.

*Corresponding author(s). E-mail(s): gabrielfonseca@pucminas.br;
Contributing authors: romain.negrel@esiee.fr; benjamin.perret@esiee.fr;
jean.cousty@esiee.fr; sjamil.pucminas.br;

## Abstract

Image segmentation is inherently challenging because it is often difficult to automatically identify the object of interest in an image. To mitigate this, human-provided markers can be incorporated into the segmentation process, greatly improving accuracy. However, human interaction is an expensive resource and methods that reduce effort in interactive segmentation are of great interest. In this work, we introduce a novel marker-based segmentation layer for deep neural networks, enabling end-to-end training of a marker creation network. Our training methodology includes a loss function with two main components: (i) segmentation loss using the new differentiable segmentation layer, and (ii) a set of regularization functions that ensure the generated markers have the desired shape properties. We show that by using the proposed method, the network can automatically generate markers that achieve effective segmentation and have desirable shape characteristics. We validate our results in the training dataset and in five unseen datasets.

**Keywords:** Fuzzy markers, interactive segmentation, automatic marker proposal, hierarchies

## 1 Introduction

Image segmentation is a foundational problem in image processing, often serving as a crucial preprocessing step for numerous high-level tasks. However, it is inherently an ill-posed problem since it is usually impossible to automatically determine the object of interest for each different user. Consequently, incorporating additional information in the form of human-provided markers significantly

improves the results, yielding precise delineations that are aligned with a specific user intent.

The most common way to introduce user-given knowledge in the segmentation process is to provide the location of objects of interest in the image. These indicators are often called *markers* (or *seeds*) and can take different shapes and forms, including scribbles [1–3], bounding boxes [4], points [5], image regions [6, 7], which are easily editable allowing one to refine the segmentation results by either adding or removing parts
of the markers. In general, an interactive procedure allows the user to iteratively refine or edit the markers until a satisfactory segmentation result is obtained [8–10]. In complex images, i.e., with a large number of objects or with objects that are not easily distinguishable from the background, a user may need to input many cues to produce an acceptable segmentation. In this context, studying ways to reduce the effort requested from a user during an interactive segmentation procedure is of great interest.

In this work, we introduce a method aimed at minimizing user effort in marker-based interactive segmentation systems. From a given minimal object location indicator, i.e., a single click inside the object of interest indicating its location, denoted here as object location cue, we automatically generate a set of markers that the user can refine or, ideally, accept as an effective marker set for achieving satisfactory segmentation. The idea is that this approach not only streamlines the interactive process but also enhances the efficiency and accuracy of the segmentation task, reducing the dependency on extensive user input. An example of this process is illustrated in Figure 1. We can observe in this example that the produced segmentation can be highly improved going from a simple cue (second row) to a learned marker (third row), reducing the amount of corrections needed for achieving a satisfactory segmentation.

Automatically generating markers to assist users in an interactive segmentation process presents a significant challenge, primarily due to the complexity of defining optimal reference markers. This fact makes it difficult to deal with the marker proposal as a traditional supervised learning approach. Instead of aiming for optimal markers, we propose a method to learn effective markers that satisfy two key properties: (i) being able to recover the correct segmentation when used as input in the chosen marker-based segmentation method, and; (ii) being easily editable by a user, which could either select, discard or modify parts of a marker during an interaction phase. To achieve these properties, we introduce a novel loss function that combines a segmentation loss with a set of regularization functions applied to the markers. With this approach, we can make use of the vast number of image segmentation datasets to train our marker proposal network.

<figure><img src="image_3.png" /><figcaption>**Fig. 1:** Example of the marker proposal method. On the top row, we have the original image on the left, and the ground-truth segmentation on the right. On the second row, we have initial object and background cues, in blue and red respectively, and a marker-based segmentation produced with the initial cues. On the bottom row, we have a automatically proposed object and background markers on the left, in blue and red respectively, and a marker-based image segmentation produced with the learned markers on the right.</figcaption></figure>

To generate such markers, we extend a classical hierarchy-based interactive segmentation method [6] to produce fuzzy segmentations, using an image and a set of fuzzy markers as input. In this work, we formally define this new approach, demonstrate its differentiable properties, and introduce an efficient algorithm to compute it, building on a hierarchy-based label propagation algorithm. This allows us to use the proposed method embedded as a layer of a deep network architecture and train it in an end-to-end fashion.

Compared to classical segmentation learning methods, our method has the advantage of producing two outputs which are (i) the markers and (ii) the segmentation produced from these
markers. The markers can be seen as an explanation of the segmentation as the relation between markers and segmentation is guided by few deterministic rules that can be easily understood by an end-user: if the end-user is not satisfied with the resulting segmentation, he/she can understand why the resulting segmentation does not correspond to his expectation and edit the proposed marker accordingly to refine the results.

In a previous work [11], the fuzzy-marker-based segmentation layer was sketched and a preliminary version of the marker learning network was presented. In order to produce good quality markers, this preliminary network needed to have the segmentation ground-truth as input. In this work, we formally define the fuzzy-marker-based segmentation and present a novel method of the marker learning network that does not rely on strong information about the object location to produce good markers. In this work, our main contributions are fourfold:

* an in-depth definition of the differentiable segmentation layer;
* an efficient algorithm to compute the fuzzy-marker-based segmentation (FMBS) in a differentiable way and its Jacobian in a form suitable for inclusion in auto-differentiation pipelines;
* a novel marker proposal network architecture to produce markers from a single click inside the object and background, achieving good results over the training dataset and four unseen ones;
* a comprehensive assessment of the proposed method, including experiments that evaluate its performance in generating both object and background markers, and an ablation study analyzing the impacts of the used regularization functions.

In Section 2 we present the related works. In Section 3, we describe the proposed marker learning architecture. In Section 4 we define the segmentation layer and describe its properties. The segmentation loss and regularization functions are detailed on Section 5. The experimental setup and results are presented in Section 7. Finally, in Section 9 we draw our conclusions and discuss future works.

## 2 Related works

Interactive segmentation, also refereed to as semi-automatic segmentation, is a classical image segmentation task, which consists in producing a segmentation by using prior knowledge in the form of user interaction. Early interactive segmentation methods rely on strict, rule-based algorithms that use predefined criteria to delineate the object of interest based on user input. In contrast, more recent deep learning-based approaches use data-driven models, being more adaptive, but having a complex decision-making process.

One of the classic rule-based methods is Graph cut (GC) [4, 12]. Graph cut methods model segmentation as an energy minimization problem on a graph-based representation for the image, where nodes represent pixels, and edges encode similarity relationships between pixels. A variation of such methods was proposed in [13], where a GC segmentation is combined with Watershed segmentations, and the graph nodes represent regions of the image instead of pixels. Another family of classical interactive segmentation methods is the Random walk-based methods (RW) [3, 14], where labels are propagated over a graph of transition probabilities. Region growing approaches, such as [15], expand regions marked by seeds in an iterative way, following region homogeneity constraints. Additionally, a significant family of methods is based on mathematical morphology, which is funded in set theory and provides powerful tools for various image processing tasks, including marker-based segmentation. Notable methods include the works relying on watersheds [2, 16] and on the image foresting transform framework [17].

More recently, with the advances on deep learning (DL), interactive segmentation methods based on convolutional neural networks were proposed [5, 18, 19], achieving great performance. More recent works based on vision transformers, such as the Segment Anything Model [20], were able to achieve unprecedented performance, but require vast amount of annotated data to be trained. Despite the success of DL-based methods in interactive image segmentation tasks, DL-based methods lack explainability. It has a special impact in the case of interactive segmentation, since it is very difficult to know what was the decision process for translating the information encoded in a marker to the final segmentation. Rule-based methods on the other hand do not cope with this challenge. In this work, we do not
want to simply tackle the interactive segmentation problem. We want to **learn the markers and the segmentation produced from these markers**. The markers can be seen as an explanation of the segmentation as the relation between markers and segmentation is guided by few deterministic rules that can be easily understand by an end-user: if the end-user is not satisfied with the resulting segmentation, he can understand why the resulting segmentation does not correspond to his expectation and edit the proposed marker accordingly to refine the results.

To cope with the problems related to the classical rule-based and the recent DL-based ones, works that combine the strengths of both paradigms were proposed. In [21] a strategy is proposed by combining a marker-based Watershed segmentation method with a marker proposal Convolutional Neural Network. This network is trained to identify borders, bodies, and center location of cell microscopy images. Then, with the output center classification maps, the markers for each cell are computed. The final segmentation is then produced using watershed segmentation. Contrary to [21], our marker learning architecture introduce a rule-based method as a layer of the network, and not as a post-processing or secondary step. A similar approach is used in [22], where a Random Walker segmentation is used in the process of training a network to learn edge weights of a graph, which are subsequently used to produce a segmentation. The method proposed in [22] consists in having a network which takes an image and a set of markers as input and produces an undirected edge-weighted graph, which encodes the relationship between pixels of the image and derives the transition matrix for the RW segmentation. Within the learning framework, the idea is to optimize the produced graph, which is then used by the random walk to propagate labels. The network is optimized to maximize segmentation quality, and as the transition matrices improve, the resulting segmentations become more robust. In [22], the RW segmentation is included in the network as a layer, which makes it trainable in a end-to-end fashion. More recent works introduce classical operations from mathematical morphology into the deep learning context [23–26], reducing the gap between rule-based techniques and data-driven models. In this context, our work contributes to this research direction by

integrating a classical hierarchy-based segmentation method [6] as a differentiable layer within deep neural networks. This integration enables the inclusion of our layer in deep architectures, allowing for end-to-end training while preserving the interpretability and robustness of classical segmentation techniques.

## 3 Marker creation network overview

In this section we present the proposed architecture for learning markers, combining neural networks and the new segmentation layer based on the fuzzy-marker-based image segmentation method. A schematic overview of our model and training procedure is illustrated in Figure 2.

The main goal of our network is to produce a marker for an object of interest for a given image, an object and background location cue, and a hierarchy of segmentations, represented by a saliency map [27]. This saliency map is the contour image representation used by the segmentation layer to find the segmentation associated with the markers. The object and background location cues are binary maps with the same size as the input image, with a small indication about the location of the object of interest and the background. We consider object location cues as minimal interactions that roughly provide an indication of the object’s location. In contrast, markers can offer more robust information, encoding details about the shape and sometimes precise delineation of the object of interest. We set the location cues as a part of the input since it would not be possible for the network to properly decide which is the object of interest that should be marked on an image containing multiple appearing objects. We also give the saliency map as input so we can produce markers that fit better a specific hierarchy and are prone to produce good segmentations when used with a specific hierarchy-based segmentation method.

The output of the network consists of an object marker. The markers proposed by the network are maps with the same size as the input image, containing values between 0 and 1. Locations that belong to the marker contain values close to 1, i.e., the generated object marker contains values close to 1 on locations where the object of interest
<figure><img src="image_4.png" /><figcaption>**Fig. 2:** Overview of the marker creation network training pipeline. The network takes as input an image, a set of cues indicating the object location, and a saliency map representation of a hierarchy for the image. The output of the marker creation network is a fuzzy object marker. This marker is then used to produce a fuzzy-marker-based segmentation. The total loss is a combination of a segmentation loss and a set of regularization functions computed over the proposed markers.</figcaption></figure>

appears. It is desired that the markers proposed by our network are able to produce a robust object segmentation and, moreover, that the markers can also be easily editable by a user during an interactive process. Also, as shown in Section 6.2, the proposed network can be tricked to also produce background markers using the background/object duality.

To generate such markers, our goal is to train a deep convolutional neural network $f(\mathbf{X}; \theta)$, parametrized by $\theta$. The symbol $\mathbf{X}$ denotes the input of the network, which is a pair of an image and an object location cue. To learn the parameters $\theta$, we propose to minimize a loss function composed of two main parts: (i) a segmentation loss $L_{Seg}$ computed over a marker-based segmentation $S(f(\mathbf{X}; \theta))$ produced using the marker proposed by the network, and (ii) a set of regularization functions $L_i, ..., L_k$ computed over the marker, to enforce some desirable shape characteristics on the produced marker. The total loss to be minimized, named $L_{marker}$, is defined by:

$$L_{marker}(f(\mathbf{X}; \theta)) = L_{Seg}(S(f(\mathbf{X}; \theta)), \hat{S}) + \sum_{i \in k} \lambda_i L_i(f(\mathbf{X}; \theta)), \quad (1)$$

where $\hat{S}$ is a ground-truth segmentation for the input image, and $\lambda_i$ is a weighting factor for the regularization $L_i$.

To train our marker creation network in an end-to-end fashion, the segmentation module $S(f(\mathbf{X}; \theta))$ must be differentiable with respect to the output of the network $f$. To achieve this, we propose a segmentation layer based on the fuzzy-marker-based segmentation method, which is an extension of the classical segmentation method proposed by Salembier and Garrido in [6].

An overview of the proposed architecture can be seen in Figure 2. We can observe that we have the image concatenated to the saliency map, the object and background location cues as input of the marker creation network. From the given input, an object marker is generated. Then, with the output marker, a fuzzy-marker-based segmentation is computed, using our proposed segmentation layer. From this segmentation, the segmentation loss $L_{Seg}$ is assessed. Also, a set of regularization functions is computed over the proposed markers. In other words, during the training of the network, the loss is based on a combination of the capacity of the markers producing a good segmentation, and the quality of the marker shape.

The total loss is minimized when the segmentation produced from the generated markers is precisely the ground-truth segmentation and when the markers match desired characteristics enforced by the regularization functions. The desirable marker characteristics include having a small size, being composed of a low number of connected
components, being smooth, and being localized far from the boundary of the object. The regularization functions used in this work are defined and explained in Section 5.

# 4 Segmentation layer

When training our network to generate markers, we want that the created markers produce good segmentations when used on a marker-based segmentation method. In this work, we aim to produce markers that are effective when used with a classical interactive marker-based image segmentation method based on hierarchies [6]. Since we do not have reference markers for evaluating their qualities, we propose a novel segmentation layer, which allows us to evaluate the capacity of the markers to produce a good segmentation, needing only a reference segmentation. Reference segmentations in the other hand are easier to define, and are widely available on image segmentation datasets.

The segmentation layer is based on the fuzzy-marker-based segmentation method, which is an extension of the classical marker-based segmentation proposed in [6].

The remainder of this section is organized as follows: in Section 4.1, we present preliminary notions on hierarchies and ultrametric distances. In Section 4.2, we define the marker based segmentation using hierarchies. In Section 4.3 we define the fuzzy-marker-based segmentation. We provide a linear time algorithm for computing the FMBS in Section 4.5. In Section 4.6 we show how to create the differentiable segmentation layer using the FMBS method. Finally, in Section 4.6 we propose an algorithm to efficiently compute the differentiable FMBS.

## 4.1 Hierarchies and ultrametric distances

As in the original marker-based segmentation method proposed in [6], the FMBS produces a segmentation based on an indexed hierarchy produced from the input image. We define the image domain as a finite nonempty set, denoted by $D$. We define a hierarchy $\mathcal{H}$ (on $D$) as a set of subsets of $D$ such that: (i) $D$ is an element of $\mathcal{H}$; (ii) for every element $x$ of $D$, the singleton $\{x\}$ belongs to $\mathcal{H}$; and (iii) for any two elements $X$ and $Y$ of $\mathcal{H}$

if the intersection of $X$ and $Y$ is nonempty, then $X$ either includes $Y$ or is included in $Y$. If $\mathcal{H}$ is a hierarchy, any element of $\mathcal{H}$ is called a region of $\mathcal{H}$.

An indexed hierarchy (on $D$) is a pair $(\mathcal{H}, \omega)$, where $\mathcal{H}$ is a hierarchy and where $\omega$ is a function from $\mathcal{H}$ to $\mathbb{R}^+$ such that: (i) $\omega(X)$, called index of $X$, is equal to 0 if and only if $X$ is a singleton; and (ii) for any two regions $X$ and $Y$ of $\mathcal{H}$, if $X$ is included in $Y$, then we have $\omega(X) \le \omega(Y)$.

Let $\mathcal{H}$ be a hierarchy and let $X$ and $Y$ be two regions of $\mathcal{H}$. The region $X$ is a parent of $Y$ and $Y$ is a child of $X$ if $Y$ is included in $X$ and if any region of $\mathcal{H}$ which is proper superset of $Y$ is also a superset of $X$. A region $R$ of $\mathcal{H}$ is called a leaf (resp. root) of $\mathcal{H}$ if it is not the parent (resp. child) of any region of $\mathcal{H}$. It can be observed that $D$ is the only root of $\mathcal{H}$ and that the set of leaves of $\mathcal{H}$ is precisely the set of all singletons on $D$. It can also be noticed that any non-root region $X$ of $\mathcal{H}$ has a unique parent, which is denoted by $par(X)$ in the following. A hierarchy $\mathcal{H}$ is a binary hierarchy if any non-leaf region has exactly two distinct children. Every region $X$ in a binary hierarchy that has a parent, it has a unique sibling, denoted $sib(X)$.

Hereafter, the pair $(\mathcal{H}, \omega)$ denotes an indexed binary hierarchy, that is an indexed hierarchy such that $\mathcal{H}$ is a binary hierarchy.

The ultrametric distance associated with an indexed hierarchy $(\mathcal{H}, \omega)$, denoted by $d_{\mathcal{H}}$, is defined as the function from $D \times D$ to $\mathbb{R}^+$ such that, for any two elements $x$ and $y$ of $D$, the value $d_{\mathcal{H}}(x, y)$ is the index of the smallest region of $\mathcal{H}$ which contains both $x$ and $y$:

$$d_{\mathcal{H}}(x, y) = \min \{\omega(X) \mid X \in \mathcal{H}, x \in X, y \in X\}. \quad (2)$$

In topology, ultrametrics define a metric space that satisfies a stronger version of the triangle inequality, called the strong triangular (or ultrametric) inequality. This is stricter than the usual triangle inequality as it forces the distance between two points to be, at most, the maximum of the distances through any intermediate point. Ultrametrics are often used to represent hierarchies of partitions, such as in the context of hierarchical clustering [28]. It is well known that the function $d_{\mathcal{H}}$ is a distance which is, in addition, ultrametric [29].
## 4.2 Marker-based segmentation using hierarchies

The segmentation method proposed in [6] relies on creating a partition by identifying as an object any region within the hierarchy that intersects with a given object marker and that does not intersect with the background marker. The process begins with the user selecting regions of the image that represent the object of interest and regions that represent the background. These regions are initially defined as the finest partitions in the hierarchy, which could correspond to individual pixels, or superpixels. Once the markers are assigned, they are propagated throughout the hierarchy to generate the final segmentation, ensuring that every region is associated with a marked region in the hierarchy.

We can formally define the segmentation method proposed in [6] as follows. Let $O$ and $B$ be two subsets of $D$, representing the object and background markers, respectively. The marker-based segmentation (of $D$) for $(O, B)$ (with respect to $(\mathcal{H}, \omega)$), denoted by $S_{\mathcal{H}}(O, B)$ is the union of the regions of $\mathcal{H}$ which contain an element of $O$ but no element of $B$:

$$S_{\mathcal{H}}(O, B) = \cup \{X \in \mathcal{H} \mid (X \cap O \neq \emptyset) \wedge (X \cap B = \emptyset)\}. \quad (3)$$

In order to propose our extension to the case where markers are fuzzy instead of crisp, we will rely on an alternative characterization of the marker-based segmentation based on ultrametric distances induced by the hierarchy.

Let $x$ be any element of $D$ and let $Y$ be any subset of $D$. We define the connection value of $x$ to $Y$ (for the hierarchy $\mathcal{H}$), denoted by $C_{\mathcal{H}}(x, Y)$, as the shortest ultrametric distance between $x$ and an element of $Y$:

$$C_{\mathcal{H}}(x, Y) = \min\{d_{\mathcal{H}}(x, y) \mid y \in Y\}. \quad (4)$$

The notion of a connection values, also referred to as fuzzy connectedness [30], has been used for defining or characterizing different classical image segmentation methods. In [31–34] the relationship between the image foresting transform, the fuzzy connectedness segmentation, shortest path forests,

watersheds, and minimum spanning forests are established through the notion of connection values. In [35] connection values play an important role in the definition of topological watersheds.

**Property 1.** Let $O$ and $B$ be two subsets of $D$. The following statement holds true:

$$S_{\mathcal{H}}(O, B) = \{x \in D \mid C_{\mathcal{H}}(x, O) < C_{\mathcal{H}}(x, B)\}. $$

In other words, Property 1 states that a point $x$ belongs to the marker-based segmentation $S_{\mathcal{H}}(O, B)$ if the shortest ultrametric distance between $x$ and an element of $O$ is smaller than the shortest ultrametric distance between $x$ and an element of $B$. The idea of producing a segmentation by assigning elements of the image to the “closest” marker based on connection values has been employed on classical segmentation methods [17, 30, 36]. The proofs of the properties presented in this section are given in Appendix A.

## 4.3 Fuzzy-marker-based segmentation

The marker-based segmentation defined in [6] relies on crisp markers to produce a segmentation. In the FMBS, markers are fuzzy, and can indicate the location of an object with different intensities on distinct locations on the image. In the FMBS method, the fuzzy markers are represented by fuzzy sets. In this section, we define the fuzzy-marker-based segmentation, and the proofs of the properties presented in this section are given in Appendix B.

A fuzzy set or marker (on $D$) is defined as a function from $D$ to the real interval $[0, 1]$. Let $\mu$ be a fuzzy marker and let $x$ be an element of $D$. The membership degree of $x$ in $\mu$, denoted by $\mu(x)$, is a value that indicates the degree of which $x$ belong to $\mu$, ranging from 0 (not belonging) to 1 (completely belonging).

The FMBS is defined based on an extension of the connection values presented in Equation 4, to the case where the markers are fuzzy. We first present the definition of fuzzy connection values before analyzing its behavior, showing in particular that this notion is indeed a generalization of the usual notion of connection value.

**Definition 2.** (Fuzzy connection value) Let $x$ be an element of $D$, and let $\mu$ be a fuzzy set. The fuzzy connection value of $x$ to $\mu$ (for $(\mathcal{H}, \omega)$),
denoted by $C_H^f(x, \mu)$, is defined by:

$$C_H^f(x, \mu) = \min\{\alpha(\mu(y))(1 - \mu(y) + d_H(x, y)) | y \in D\}, \quad (5)$$

where $\alpha$ is a decreasing function such that $\alpha(1) = 1$ and $\alpha(0)$ is strictly greater than the maximal value of $d_H$, i.e., $\alpha(0) > \max\{d_H(x, y) | x \in D, y \in D\}$.

Intuitively, it can be seen that, as in the crisp set version, if a marker is “grown” (resp. “shrinked”), then the fuzzy connection values to this marker necessarily decrease (resp. increase). Thus, in terms of connection values, the points of the domain become “closer” to (resp. “farther” from) the marker when the membership function of the marker is raised (resp. lowered). In other words, as stated by the following property, connections values are decreasing with respect to the marker.

**Property 3.** The map $C_H^f$ is decreasing with respect to its second variable. More precisely, let $x$ be any element in $D$ and let $\mu, \mu'$ be two fuzzy sets such that $\mu \le \mu'$ (i.e., for any $y$ in $D$, we have $\mu(y) \le \mu'(y)$, then $C_H^f(x, \mu) \ge C_H^f(x, \mu'$).

Let $A$ be a subset of $D$. The indicator function of $A$ is the fuzzy set $1_A$, such that for any $x$ in $D$, the value $1_A$ is equal to 1 if $x$ belongs to $A$ and is equal to 0 otherwise.

**Property 4.** Let $A$ be a non-empty subset of $D$, and let $1_A$ be the indicator function of $A$. Then, the following statement holds true:

$$\forall x \in D, \quad C_H(x, A) = C_H^f(x, 1_A).$$

In other words, Property 4 shows that the connection value and fuzzy connection value give the same results when we consider a crisp marker or its indicator function taken as a fuzzy marker. Now that we have presented the fuzzy connection value extension, we are able to define the segmentation based on fuzzy connection values, named fuzzy-marker-based segmentation.

**Definition 5. (Fuzzy-marker-based segmentation)** Let $\mu_O$ and $\mu_B$ be two fuzzy sets that represent the object and background markers, respectively. The fuzzy-marker-based segmentation (of $D$) for $(\mu_O, \mu_B)$ (with respect to $(H, \omega)$), denoted

by $S_H^f(\mu_O, \mu_B)$ is defined by:

$$S_H^f(\mu_O, \mu_B) = \{x \in D | C_H^f(x, \mu_O) < C_H^f(x, \mu_B)\}.$$

In other words, the fuzzy-marker-based segmentation of $D$ for $(\mu_O, \mu_B)$ is the set that contains every element of $D$ with a fuzzy connection value to $\mu_O$ smaller than to $\mu_B$. The following property establishes the relation between the fuzzy-marker-based segmentation and the marker-based segmentation proposed in [6]: when the fuzzy markers indeed represent crisp sets, the marker-based segmentation and the fuzzy-marker-based segmentation are the same.

**Property 6.** Let $O$ and $B$ be two subsets of $D$, and $1_O$ and $1_B$ be the indicator functions of $O$ and $B$, respectively. Then, the following statement holds true:

$$S_H^f(1_O, 1_B) = S_H(O, B).$$

For our application, we want the FMBS to be used as a layer of a marker learning network that must be trainable in an end-to-end fashion. In order to do that, the FMBS must be differentiable with respect to the input markers. For that, instead of using the formula given in Definition 5, we use a softmax function [37] to produce the final segmentation.

The softmax FMBS with respect to two fuzzy sets, denoted by $S_H^s(\mu_O, \mu_B)$ is given, for any $x \in D$ by:

$$S_H^s(\mu_O, \mu_B)(x) = \frac{e^{-\beta C_H^f(x, \mu_O)}}{e^{-\beta C_H^f(x, \mu_O)} + e^{-\beta C_H^f(x, \mu_B)}} \quad (6)$$

where $\beta$ is a positive real number. It is important to note that $S_H^s(\mu_O, \mu_B)$ is a fuzzy set. As $\beta$ tends towards infinity, $S_H^s(O, B)(x)$ will be equal to 1 if $C_H^f(x, \mu_O) < C_H^f(x, \mu_B)$ and equal to 0 if $C_H^f(x, \mu_O) > C_H^f(x, \mu_B)$. This will lead to $S_H^s(\mu_O, \mu_B)$ being an indicator function of the FMBS presented in Definition 5. If there is a tie, i.e., $C_H^f(x, \mu_O) = C_H^f(x, \mu_B)$, $S_H^s(O, B)(x)$ will be equal to 0.5. In practice, we set a threshold to produce a crisp segmentation from $S_H^s(O, B)$. If $S_H^s(O, B)(x) > 0.5$, $x$ belongs to the object segmentation, otherwise, it belongs to the background.
## 4.4 Regional connection values

In this section, we introduce the notion of a regional connection value, i.e. a connection value to the restriction of a fuzzy marker to a given subset of the domain. This notion is central for establishing an algorithm (see Section 4.5) to compute the connection values of every point of the domain to a fuzzy marker (without any restriction), and consequently a fuzzy-marker-based segmentation. Indeed, the idea of the algorithm is to leverage the nested structure of the regions in the hierarchy to incrementally compute the connection values associated with the points of the domain. We start by studying the combination of the regional connection values to two subsets of the domain in order to obtain the connections values to the union of these subsets (namely Properties 7, and 8). Then, we present our main theorems establishing (i) that the regional connection values associated to every region of the hierarchy can be obtained by induction from the root to the leaves (Theorem 11) and that the connection value of every point of the domain can be obtained easily from the regional connection values associated to the leaves of the hierarchy (Theorem 12). The proofs of the properties presented in this section are given in Appendix C.

The restriction of a fuzzy set $\mu_O$ to a subset $X$ of $D$, denoted by $\mu_O \downarrow_X$, is the fuzzy set such that $\mu_O \downarrow_X (x) = \mu_O(x)$ for any $x$ in $X$, and $\mu_O \downarrow_X (x) = 0$ for any $x$ in $D \setminus X$, i.e., $\mu_O \downarrow_X = \inf(\mu_O, \mathbb{1}_X)$, where $\mathbb{1}_X$ is the indicator function of $X$ in $D$.

Property 7 establishes that the connection values to the restriction of a fuzzy set to a given region depend only on the points of this region, or more precisely, on the membership value of the points of this region and on the ultrametric distances to the points of this region.

**Property 7.** Let $A$ be a subset of $D$, let $\mu$ be a fuzzy marker, and let $x$ be any element of $D$. Then, the following statements hold true:

1. if $A$ is nonempty, then

$$C_{\mathcal{H}}^{f}(\mu \downarrow_{A}, x) = \min\{\alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x)) \mid y \in A\}$$

2. if $A$ is empty, then

$$C_{\mathcal{H}}^{f}(\mu \downarrow_{A}, x) = \alpha(0)$$

**Property 8.** Let $A$ and $B$ be two subsets of $D$, let $\mu$ be a fuzzy marker, and let $x$ be any element in $D$. Then, the following statement holds true:

$$C_{\mathcal{H}}^{f}(\mu \downarrow_{A \cup B}, x) = \min(C_{\mathcal{H}}^{f}(\mu \downarrow_{A}, x), C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, x))$$

Lemma 9 shows that the connection values of any two points in a region $A$ to the restriction of the marker to the complement of $A$ are equal, leading us to the definition of the regional connection value of $A$ as the connection value of any of its elements to the restriction of the marker to its complement (see Definition 10).

**Lemma 9.** Let $\mu$ be a fuzzy marker, and let $A$ and $B$ be two disjoint regions of $\mathcal{H}$. Then, for any two points $x$ and $y$ in $A$, we have:

1. $C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, x) = C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, y)$; and

2. $C_{\mathcal{H}}^{f}(\mu \downarrow_{D \setminus A}, x) = C_{\mathcal{H}}^{f}(\mu \downarrow_{D \setminus A}, y)$.

**Definition 10.** (regional connection values)

Let $\mu$ be a fuzzy set, let $R$ be a region of $\mathcal{H}$, and let $x$ be any element of $R$. We define the regional connection value of $R$ to $\mu$ by:

$$T_{\mathcal{H}}^{\mu}(R) = C_{\mathcal{H}}^{f}(\mu \downarrow_{D \setminus R}, x).$$

Let us now state the two main results of this section. Theorem 11 establishes that the regional connection value of every region of the hierarchy can be obtained by induction from the regional connection value of its parent. Hence, they can be computed by browsing the hierarchy from the root to the leaves. Then, Theorem 12 establishes that the connection values of every point of the domain can be easily obtained from the regional connection values of every leaf of the hierarchy. These two theorems lead to a linear time algorithm to obtain the connections values of all points of the domain to any fuzzy marker, as presented in the following Section 4.5.

**Theorem 11.** Let $A$ be any non-root region of $\mathcal{H}$, and let $B$ (resp. $C$) be the sibling (resp. parent) of $A$. Let $\mu$ be a fuzzy marker. Then, we have:

1. $T_{\mathcal{H}}^{\mu}(A) = \min\{T_{\mathcal{H}}^{\mu}(C), \alpha(m)(1 - m + \omega(C))\}$, where $m$ is the maximum membership degree of an element in $B$, i.e., $m = \max\{\mu(y) \mid y \in B\}$.
2. Furthermore, we have $T_H^\mu(R) = \alpha(0)$ if $R$ is the root of $\mathcal{H}$, i.e., if $R = D$.

**Theorem 12.** Let $x$ be any point of $D$, and let $\mu$ be a fuzzy set. Then, the fuzzy connection value $C_H^f(\mu, x)$ is equal to $C_H^f(\mu, x) = \min\{T_H^\mu(\{x\}), \alpha(\mu(x))(1 - \mu(x))\}$.

## 4.5 Linear time algorithm for FMBS

In this section, leveraging on Theorems 11 and 12, an efficient algorithm for computing the connection values of any point of the domain to a given fuzzy marker is proposed. Based on these two theorems the correctness of the algorithm is established. Furthermore, its time complexity is analyzed, showing that it runs in linear time with respect to the number of points in the domain. Then, we present an algorithm for obtaining the softmin FMB segmentation associated to fuzzy object and background markers.

The precise implementation of the algorithm to compute the connection values to a fuzzy marker is described in Algorithm 1. It can be seen that this algorithm comprises three main blocks performed sequentially:

(i) The first one (lines 1 to 4) consists of computing for each region $\mathbb{R}$ of the hierarchy, the maximum membership degree of a point in $\mathbb{R}$ and storing the result in $\mathbb{m}[\mathbb{R}]$.

(ii) The second one (lines 5 to 8) consists of computing the regional connection value of each region of the hierarchy using the array $\mathbb{m}$ previously computed and following Theorem 11. The result is stored in the array $\mathbb{T}$. The initialization of $\mathbb{T}[\mathbb{Root}]$ before the loop and the root-to-leaves traversal order ensure that, as assumed in Theorem 11, when we compute the regional connection value of a region $\mathbb{R}$, the regional connection value $\mathbb{T}[\mathbb{par}(\mathbb{R})]$ of its parent is already known.

(iii) Finally, following Theorem 12, the third block (lines 9 to 10) consists of computing the fuzzy connection value of each point to the given fuzzy marker using the regional connection values stored in the array $\mathbb{T}$. The resulting connection values are stored in the array $\mathbb{C}$.

It can be easily seen that the first block visits each region twice (once for initialization and once during the traversal of the hierarchy) and each visit involves a constant number of constant time

**Algorithm 1** Fuzzy connection values

**Input**: A hierarchy $(\mathcal{H}, \omega)$ and a fuzzy set $\mu$

**Output**: The array $\mathcal{C}$ containing the fuzzy connection values for each $x$ in $D$ to $\mu$

1. **foreach leaf $\{x\}$ in $\mathcal{H}$ do** $\mathbb{m}[\{x\}] := \mu(x)$

2. **foreach non-leaf region $R$ of $\mathcal{H}$ do** $\mathbb{m}[R] := 0$

3. **foreach non-root region $R$ of $\mathcal{H}$ in leaves-to-root order do**

4. $\lfloor \mathbb{m}[\mathbb{par}(R)] \rfloor := \max(\mathbb{m}[\mathbb{par}(R)], \mathbb{m}[R])$

5. $\mathbb{T}[\mathbb{Root}] := \alpha(0)$

6. **foreach non-root region $R$ in $\mathcal{H}$ in root-to-leaves order do**

7. $\lfloor c := \alpha(\mathbb{m}[\mathbb{sib}(R)]) (1 - \mathbb{m}[\mathbb{sib}(R)] + \omega(\mathbb{par}(R))) \rfloor$

8. $\mathbb{T}[\mathbb{R}] := \min(\mathbb{T}[\mathbb{par}(R)], c)$

9. **foreach leaf $\{x\}$ of $\mathcal{H}$ do**

10. $\lfloor \mathbb{C}[x] := \min(\mathbb{T}[\{x\}], \alpha(\mu(x))(1-\mu(x))) \rfloor$

operations, leading to a linear-time complexity with respect to the number of regions in the hierarchy. The second block visits each region once, each visit also involving a constant number of constant-time operations. Thus this second blocks also runs in linear-time with respect to the number of regions in the hierarchy. Finally, the last block performs a constant time operation for each leaf of the hierarchy. Overall, as the number of regions of a binary hierarchy built on the domain $D$ is equal to $2|D| - 1$, we conclude that Algorithm 1 runs in linear time with respect to the number of points in the domain $D$.

As shown in Algorithm 2, a linear-time softmin FMBS algorithm can then be easily derived. It consists of first computing the fuzzy connection values to both the fuzzy object and background markers with calls to Algorithm 1 and, then applying, for each point of the domain, the formula of Equation 6.

**Algorithm 2** Softmin FMBS

**Input**: A hierarchy $(\mathcal{H}, \omega)$ and two fuzzy markers $\mu_O$ and $\mu_B$

**Output**: The array $\mathcal{S}$ containing the softmin FMBS value of every point of the domain

1. $\mathbb{Co} := \text{the fuzzy connection values to } \mu_O \text{ obtained with Algorithm 1}$

2. $\mathbb{Cb} := \text{the fuzzy connection values to } \mu_B \text{ obtained with Algorithm 1}$

3. **foreach $x$ in $\mathbb{D}$ do**

4. $\lfloor \mathbb{S}[x] = \frac{e^{-\beta \mathbb{Co}[x]}}{(e^{-\beta \mathbb{Co}[x]} + e^{-\beta \mathbb{Cb}[x]})} \rfloor$
<figure><img src="image_5.png" /></figure>

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

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

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

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

<figure><img src="image_10.png" /><figcaption>**Fig. 3:** Example of regional connection values computation. On (a) we have the set *D* and the fuzzy markers *μ*<sub>*O*</sub> and *μ*<sub>*B*</sub>. On (b) we have the fuzzy connection values for every element in *D* to *μ*<sub>*O*</sub> and *μ*<sub>*B*</sub>, considering the indexed hierarchy illustrated in (c). On (d), we have the maximum membership degree values for each region. On (e) we have the regional connection values computation (with respect to *μ*<sub>*O*</sub>) for each region of the hierarchy. Finally, in (f) we have the fuzzy connection values computation for all leaves of the hierarchy. For this example, we set *alpha*(*x*) = 1/(*x* + *ε*), with *ε* being a small constant value.</figcaption></figure>

An example of a computation of the regional
connection values is illustrated in Figure 3. Fol-
lowing the computation of the algorithm for the
example provided in Figure 3e, according to the
second condition of the equation in Theorem 11,
since R5 = D, i.e., the root of the hierarchy, we
start by setting T<sub>H</sub>(&mu;<sub>O</sub>, R5) to &alpha;(0)(1 + &omega;(R5)).
Since in our illustrated example &alpha;(*x*) = 1/(*x* + &epsilon;),
&alpha;(0), and consequently &alpha;(0)(1 + &omega;(R5)), tend to
&infin; (line 5 of Algorithm 1). This ensures that
T<sub>H</sub>(&mu;<sub>O</sub>, R5) is bigger than any other regional
connection value for every region in H. Moving
to the computation of T<sub>H</sub>(&mu;<sub>O</sub>, R4), we fall into

the first condition of Theorem 11, and we must
compute the minimum between T<sub>H</sub>(&mu;<sub>O</sub>, R5) and
Csib(&mu;<sub>O</sub>, R4) (lines 7 and 8 of Algorithm 1). The
value of Csib(&mu;<sub>O</sub>, R4) gives us the fuzzy connec-
tion value of all the elements of R4 to &mu;<sub>O</sub>&darr;Csib(R4)
(line 7 of Algorithm 1). It can be observed that
d<sub>H</sub>(&x;, &y;) for every x &isin; R4 and every y &isin; R3 is
the same, since the smallest region that contains
both elements of R4 and R3 is the parent of such
regions. As d<sub>H</sub>(&x;, &y;) is constant for T<sub>H</sub>(&mu;<sub>O</sub>, R4),
the element y &isin; R3 that minimizes the value
of equation in Definition 5 is the one with the
maximum membership degree to &mu;<sub>O</sub> &darr;R3. The
maximum values of membership degrees of each region, illustrated in Figure 3d, can be easily computed with one pass over the hierarchy in a leaves-to-root order (lines 1 to 4 of Algorithm 1). Finally, after having all regional connection values, we must use Theorem 12 to compute the fuzzy connection values for all $x \in D$ (lines 9 and 10 of Algorithm 1). This last step is illustrated in Figure 3f.

## 4.6 Differentiable segmentation layer

To train the marker creation network in an end-to-end fashion using traditional gradient descent methods, we must be able to back-propagate the segmentation error through our model. For that, the marker-based segmentation layer, highlighted in blue in Figure 2, must be differentiable with respect to the markers proposed by the network. Here we explain how we create such layer using the FMBS method.

To compute the FMBS of an image with respect to a given hierarchy and a pair of markers (object and background), we must get the fuzzy connection value of each element of the image to the object marker and to the background marker, using Algorithm 1.

Let $\mu$ be a fuzzy marker on $D$. We can observe from Definition 2 that for the fuzzy connection value of an element $x \in D$ to $\mu$, there is an element $y \in D$ that minimizes Equation 5. We call this element $y$ the closest element to $x$ (for $\mu$). This element plays a central role in the differentiation of fuzzy connection values with respect to fuzzy objects.

In order to fit the usual linear algebra notations used in automatic differentiation formalisms, let us rewrite the basic functions involved in fuzzy connection values in a vectorial form. Let $D = \{x_1, \dots, x_n\}$ and let $i$ be any index value in $\{1, \dots, n\}$. Any fuzzy object $\mu$ can be written as the vector $\mu = (\mu_1 = \mu(x_1), \dots, \mu_n = \mu(x_n))$. Furthermore, we denote by $C(\mu)$ the vector of $\mathbb{R}^n$ such that $C_i(\mu)$ is the fuzzy connection value of $x_i$ to $\mu$. We define the function $cl_i$ as the map from the set of all fuzzy objects on $D$ to the set of integer index between 1 and $n$ such that, for any fuzzy object $\mu$, the value $cl_i(\mu)$ is the index of the closest element to $x_i$ for $\mu$. Hence, we have:

$$cl_i(\mu) = \arg\min_{k \in \{1, \dots, n\}} \{\alpha(\mu_k)(1 - \mu_k) + d_{\mathcal{H}}(x_i, x_k)\}, \quad (7)$$

Thus, the fuzzy connection value $C_i(\mu)$ of $x_i$ to $\mu$ is given by:

$$C_i(\mu) = \alpha(\mu_{cl_i}(\mu)) \cdot (1 - \mu_{cl_i}(\mu) + d_{\mathcal{H}}(x_i, x_{cl_i}(\mu))), \quad (8)$$

Intuitively, it can be seen that a small modification on the membership degree $\mu_{cl_i}$ leads to a small modification of the fuzzy connection value of $x_i$ to $\mu$, i.e., if we increase $\mu_{cl_i}$ by a small amount, then $C_{\mathcal{H}}^f(\mu, x_i) = C_i(\mu)$ is decreased by a small amount as $C_{\mathcal{H}}^f(\cdot, x_i)$ is decreasing (Property 3). Indeed, the Jacobian [38] of $C$ is related to the one of $cl$, which can be written as the matrix composed of the indicator column vectors of the closest elements. More precisely, we have:

$$\frac{\partial cl}{\partial \mu} = [1_{cl_1(\mu)}, \dots, 1_{cl_n(\mu)}], \quad (9)$$

where $1_{cl_i(\mu)}$ is the column vector in $\mathbb{R}^n$, with values equal to 1 at the index $cl_i(\mu)$ of the closest element of $x_i$, and 0 elsewhere.

In the context of a back-propagation algorithm, if we have computed an error $e$, and computed $\frac{\partial e}{\partial C}$, i.e., and how the fuzzy connection values should be modified in order to minimize $e$, then, we can back-propagate the error using the chain rule: $\frac{\partial e}{\partial \mu} = \frac{\partial C}{\partial \mu} \frac{\partial e}{\partial C} = \frac{\partial cl}{\partial \mu} \frac{\partial K}{\partial cl} \frac{\partial e}{\partial K}$, where $K$ is the function such that $C = K \circ cl$, whose Jacobian can be computed from Equation 8.

For example, considering the case illustrated in Figure 3, we have the following closest elements $cl_i(\mu_O)$ for each element $x_i$ in $D$, with respect to the fuzzy marker $\mu_O$:

<table><caption>**Table 1:** Elements and their respective closest elements for the illustration depicted in Figure 3.</caption><tr><td>x</td><td>a</td><td>b</td><td>c</td><td>d</td><td>e</td><td>f</td></tr><tr><td>cl(x)</td><td>a</td><td>b</td><td>c</td><td>c</td><td>a</td><td>a</td></tr></table>

On this example, the Jacobian of the closest element function $cl$ is equal to:
$$
\begin{pmatrix}
a & b & c & d & e & f \\
1 & 0 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}
\begin{array}{l}
C_a \\
C_b \\
C_c \\
C_d \\
C_e \\
C_f
\end{array}
$$

This matrix indicates which values of $\mu_O$ should be modified to reflect the desired changes on $C_H^f(x, \mu_O)$, which can consequently modify the final segmentation. For instance, in this example, if we want to decrease the fuzzy connection value of $d$ to $\mu_O$, we should increase the value of $\mu_O(c)$, or, if we want to increase the fuzzy connection value of $f$ to $\mu_O$, we must decrease the value of $\mu_O(a)$.

Therefore, in order to backpropagate the errors through the fuzzy connection value computation layer, it is necessary to have access to the closest element to each point in $D$. The set of all closest elements can be tracked during the computation of the connection values with Algorithm 1. More precisely, Algorithm 1 can be modified to store, at each (optimization) block, the argument of the associated optimization. In other words, we have to store at each step the element of the domain which leads to an optimal value. Algorithm 3 presented hereafter, called *differentiable fuzzy connection values*, describes this modification. In particular, the lines 3 and 8 (resp. lines 14 and 15, and lines 19 and 20) were inserted to track the arguments of the maximum (resp. minimum, and minimum) involved in the first (resp. second, and third) block. These arguments are stored in the tables `mx`, `Tx`, and `cl`, respectively. When the algorithm terminates, in addition to the fuzzy connection values to $\mu$, it also outputs the closest elements to each point of the domain for $\mu$.

5 Loss and regularization
functions

To measure the quality of the generated markers
during the training of our network, we combine
the segmentation loss with several regularization
functions. These regularization functions allow
us to favor some desirable features on the pro-
duced markers. Here, we define the regularization
functions that will be used in this work.

**Algorithm 3** Differentiable fuzzy connection values

Input : A hierarchy ($\mathcal{H}$, $\omega$) and a fuzzy set $\mu$

Output: The arrays C and cl containing, for each x in D, the fuzzy connection values to μ and the associated closest element, respectively

1 **foreach** leaf {x} in **H** **do**

2 | m[{x}] := μ(x)

3 | mx[{x}] = x

4 end

5 foreach non-leaf region R of H do m[R] := 0;

6 foreach non-root region R of H in leaves-to-root order do

7 | m[par(R)] := max(m[par(R)], m[R])

8 | if m[par(R)] = m[R] **then** mx[par(R)] := mx[R];

9 end

10 T[Root] := α(0)

11 foreach non-root region R in H in root-to-leaves order do

12 | c := α(m[sib(R)]) (1-m[sib(R)] + ω(par(R)))

13 | T[R] := min(T[par(R)], c)

14 | if T[R] = c **then** Tx[R] := mx[sib(R)];

15 | else Tx[R] := Tx[par(R)];

16 end

17 foreach leaf {x} of H do

18 | C[x] := min(T[{x}], α(μ(x))(1-μ(x)))

19 | if C[x] = T[{x}] **then** cl[x] := Tx[{x}];

20 | else cl[x] := x;

21 end

For the same image, a network can propose
numerous distinct markers that are able to recover
a good segmentation. In a scenario where the
user can continue to interact after the network
generates markers, we want these markers to be
simple and easily editable. An intuitive way to
identify the characteristics of effective markers
is by considering how humans typically engage
with an interactive segmentation system. Simple
human-given markers are usually represented by
a few points and simple strokes, generally located
near the center of the objects of interest. Based
on this form of human-given markers we define
some desirable marker characteristics. We then
propose four regularization functions that allow us
to achieve markers that have such characteristics,
and these functions are described in the following.

The first characteristic we want to have is
that **the produced markers are small**. If we
consider the object segmentation ground-truth
as a marker, it would be capable of retrieving
the ground-truth segmentation when used with a
marker-based segmentation method. Although, it does not resembles a human marker in any sense, and editing the ground-truth mask for correcting a segmentation can be quite laborious. To avoid markers that are too large, we define our first regularization function, denoted by $L_{size}$.

For the remainder of this section, let $\mu_O$ be a marker proposed by our network, let $\hat{S}_O$ be the ground-truth segmentation for the object represented by the marker $\mu_O$, and let $D$ be the image domain. The first regularization function, called size regularization, is given by:

$$L_{size}(\mu_O, \hat{S}_O) = \frac{\sum_{x \in D} \mu_O(x)}{\sum_{x \in D} \hat{S}_O(x)} \quad (10)$$

In other words, this function is minimized when the marker has a small size. In the context of fuzzy sets, size can also be interpreted as the fuzzy cardinality of the set, i.e., the sum of all membership degrees. It is important to note that a marker consisting of many elements with low membership degrees and another marker consisting of a few elements with high membership degrees can yield the same $L_{size}$ value. However, in this work, this is not a significant issue, as elements with very low membership degrees have a negligible impact on the segmentation layer.

We also wish that the generated markers are not placed near or over the borders of the object of interest. Users tend to concentrate their initial interactions in the center of the object, and to add markers near the borders for necessary corrections [19]. Based on this, we propose the distance map regularization, which is defined by:

$$L_{Dmap}(\mu_O, Dmap_O, \hat{S}_O) = \frac{\sum_{x \in D} \mu_O(x) Dmap_O(x)}{\sum_{x \in D} \hat{S}_O(x)} \quad (11)$$

in which for a marker $\mu_O$, $Dmap_O$ is computed based on the Euclidean distance map (EDT) [39–41] of the ground-truth of $\mu_O$. The value $Dmap_O(x)$ for an element $x$ in $D$ is given by:

$$Dmap_O(x) = 1 - \frac{EDT_{\hat{S}_O}(x)}{max(EDT_{\hat{S}_O}(x))}, \quad (12)$$

where EDT$_{\hat{S}_O}(x)$ is the Euclidean distance from $x$ to the closest point that does not belong to the object represented by $\hat{S}_O$. In other words, this regularization function is minimized when there is no element with high value near the border of the object.

Additionally, we also want our marker to contain a low number of connected components. In order to minimize the number of connected components on the generated markers, we propose to use a third regularization function, which is a topological loss function based on component trees [42]. The component tree loss function has a similar idea to the topological loss based on persistent homology, proposed in [43]. By constructing a max-tree of the fuzzy marker, one can analyze at each scale the connected components. Analyzing the structure of the max-tree we can observe what the most prominent components are, and the idea of the loss function is to reinforce the strength of these components, and decrease the strength of weaker ones.

For our component loss function, denoted by $L_{comp}$, we use the ranked selection loss provided in [42], with the target number of maxima set to 1, i.e., enforcing the presence of only one connected component on the markers, and using dynamics as the maxima measure.

Finally, we want our markers to be smooth. To avoid noisy markers and to produce smooth ones, we apply a total variation regularization. The markers considered in this work are 2D maps of width $W$ and height $H$, and every element $x$ in a marker $\mu_O$ has a pair $(j, k)$ associated to it, representing its vertical and horizontal position. The third regularization is a total variation regularization, defined by:

$$TV(\mu_O) = \sum_{\substack{j \in W \\ k \in H}} |\mu_O(x_{j,k}) - \mu_O(x_{j+1,k})| + |\mu_O(x_{j,k}) - \mu_O(x_{j,k+1})| \\ L_{TV}(\mu_O, \hat{S}_O) = \frac{TV(\mu_O)}{\sqrt{\sum_{x \in \hat{S}_O} \hat{S}_O(x)}} \quad (13)$$

The total variation regularization is minimized when neighboring pixels have similar values throughout the marker. Enforcing this property helps prevent markers that are not spatially
smooth or that exhibit significant variations in
intensity. Notably, after the network optimiza-
tion process, markers can be binarized to enhance
usability and provide a more natural interaction
for users. However, markers with highly irreg-
ular intensity variations may result in spatially
irregular binarized outputs. This effect is further
analyzed in Section 8.

The terms in the denominator of the total vari-
ation, distance map and size regularizations are
included to make these losses invariant to the size
of the object of interest.

6 Marker proposal network:
architecture details

In this section, we first present the details of
the architecture used for our object marker pro-
posal model (Subsection 6.1) before showing that
this model can be simply tricked to also propose
background markers (Section 6.2).

6.1 Object marker proposal model

As illustrated in the top row of Figure 4, high-
lighted in green, the model comprises two major
compounds that are pipelined: the first one is a
segmentation network, while the second one, a
marker creation network, transforms an existing
segmentation into a marker. Note that the seg-
mentation from the first model does not need to be
an highly accurate delineation of the target object
as it is only used to further create the marker.

**Segmentation network.** In this work, we use a U-net network, with two Resnet34 encoder streams for the interactive segmentation network, using a strategy similar to the one proposed in [44]. The input of the interactive segmentation network is a RGB image, a binary object cue mask and a binary background cue mask, all having a resolution of 320 × 320. We feed the image to one of the encoders, and the cues to the other one. For the image encoder, we use pre-trained weights on the ImageNet dataset. This network, as the pre-trained weights, are available in the *Segmentation models pytorch* library [45]. We use a sigmoid activation function in the output, which consists of a 1-channel 320 × 320 mask, representing the object segmentation. This segmentation is then used as part of the input of the marker creation network.

**Marker-creation network.** For the marker
learning network, we also use a U-net network,
with multiple Resnet34 encoders. This network
takes as input a combination of the RGB image,
the object segmentation produced by the interac-
tive segmentation network, the background seg-
mentation, and a saliency map, all having a resolu-
tion of 320×320. We have a total of 3 encoders, one
for the image, one for the pair of object and back-
ground segmentations and one for the saliency
map.

6.2 Background marker proposal
model

As shown in Section 7, the object marker proposal
model can be trained independently to automat-
ically propose object markers. However, learning
to propose both object and background mark-
ers is of great interest, since most marker-based
segmentation methods need both to produce an
output.

An intuitive approach, would be to propose
a model that can be trained to simultaneously
propose both object and background markers.
However, the complexity of the task and the com-
petition between background and object markers
in the segmentation layer makes such process
challenging. Alternatively, we could train indepen-
dently a model (with, e.g., the same architecture
as the object creation network) to produce back-
ground markers. However, learning background
markers are inherently more challenging than
learning object markers. Indeed, objects of inter-
est are often approximately centered in an image,
which introduces a trivial solution for back-
ground marker selection — simply choosing small
regions very close to the image boundaries. This
bias makes the optimization process susceptible
to overfitting, as the network may exploit this
shortcut instead of learning a more meaningful
background representation.

To cope with these issues and produce back-
ground markers that have similar properties to
object markers, we propose an architecture, illus-
trated in Figure 4: it consists of introducing a
simple inversion layer between the segmentation
and marker creation network. Thus, to produce
background markers, we use the segmentation and
marker-creation networks with the same weights
as the one trained to produce object markers.
<figure><img src="image_11.png" /><figcaption>**Fig. 4:** Marker creation pipeline. Highlighted in the green rectangle, we have the object proposal network, and in the red rectangle, the background marker network.</figcaption></figure>

The only difference for producing background marker proposals is that we feed the marker creation network with an intermediary segmentation for the background. For producing the intermediary background segmentation, we simply take the complement of the object segmentation given by the segmentation network. Overall, this background marker proposal model does not require any more training compared to the object proposal model. The overall architecture, including both object and background-marker proposal models is depicted in Figure 4.

# 7 Experiments

In this section we describe our experimental setup, the proposed evaluation metrics, the results computed over different datasets, and a quantitative and qualitative analysis of our method.

## 7.1 Experimental setup

**Datasets.** In this work we conducted experiments over six distinct datasets. For training our models, we use a subset of the MS COCO Dataset, which contains 10.000 images. We use 9000 images for training and 1000 images for validation. The MS COCO dataset contains images with multiple objects, but in this work we produce the object marker for a single object of interest for a given

input. During the training of our models (both the interactive segmentation and the marker learning network), we randomly select one object per image. To compute the evaluation metrics, we use a subset of the MS COCO presented in [19], containing 800 object samples (800 images with one object as the object of interest).

Along with the MS COCO dataset, we evaluate our method over four unseen datasets, which are described in the following. We use the Weizmann single object dataset [46], composed of 100 images, and with three ground-truth segmentations proposed by different users for each image. During our experiments we only use the first ground-truth. Additionally, use the Weizmann Horses dataset [47], which contains 328 images of horses, with a segmentation mask for each image. We also use the GeoStar dataset [48], which is composed 151 images taken from the GrabCut [4], Pascal VOC [49] and Alpha matting [50] datasets.

The GeoStar dataset contains the ground-truth mask for each image and also contains scribble information, although in our experiments we only consider the images and ground-truths. We also test our method on the Pascal VOC 2012 segmentation dataset [49]. This dataset contains 1464 images for training and 1449 images for validation. Each image can contain more than 1 object (of the same or different class), but we only consider 1 object per image, and treat the rest of the
<figure><img src="image_12.png" /><figcaption>**Fig. 5:** Results for samples of the MS COCO validation subset and for the four unseen datasets. From left to right: input image; object and background cues superimposed over the saliency map representation of the hierarchy constructed for the input image; intermediary segmentation; object markers proposed by the network, superimposed over the saliency map; background markers (same as used to train the network), superimposed over the saliency map; marker-based segmentation; ground-truth segmentation.</figcaption></figure>

image as background. Finally, we use a subset of the MSRA10K saliency dataset [51], containing 1000 images, with one salient object per image.

During training, we only learn markers for one object of interest, and use four clicks near the corners of the images as fixed background markers. We apply a dilation on the four clicks using a disk

of radius 2 as a structuring element. The clicks are placed near the corners with distance of 8 pixels from the borders of the image. A background click is removed from the marker if it touches a region of the object of interest.

**Optimization.** We use the Adam optimizer with a learning rate of $5 \times 10^{-4}$. We set the batch
<table><caption>**Table 2:** Evaluation metrics computed for all datasets, using proposed object and fixed background markers. For the background markers, we used the same one as used for training the network, i.e., four clicks near the corners. For the average number of connected components, relative size and thinness, we consider both the object and background markers for each sample. The dataset used for training is highlighted in blue.</caption><thead><tr><th>Dataset</th><th>Average IoU</th><th>Connected Components</th><th>Average Relative Size</th><th>Average Thiness</th></tr></thead><tbody><tr><td>MS COCO</td><td>0.435</td><td>3.304</td><td>178.8%</td><td>11.52</td></tr><tr><td>Weizmann</td><td>0.776</td><td>3.630</td><td>19.9%</td><td>7.67</td></tr><tr><td>Horses</td><td>0.745</td><td>3.933</td><td>23.2%</td><td>10.61</td></tr><tr><td>GeoStar</td><td>0.648</td><td>2.894</td><td>23.3%</td><td>13.22</td></tr><tr><td>MSRA10K</td><td>0.787</td><td>3.311</td><td>23.1%</td><td>9.70</td></tr><tr><td>Pascal VOC</td><td>0.528</td><td>3.422</td><td>67.2%</td><td>9.71</td></tr></tbody></table>

size equal to 32, and we train the network for 2250 steps. During training, we use a soft Dice loss [52] as the $L_{Seg}$ term. The values of each weight $\lambda$ for the total loss were manually tuned, and set to: 30 for the $L_{seg}$, 3 for $L_{size}$, 0.01 for $L_{Dmap}$, 0.01 for $L_{TV}$, and 0.1 for $L_{comp}$. Finally, the value of $\beta$ is set to 25.

**Hierarchy computation.** The FMBS produces a segmentation based on a pair of markers and a hierarchy produced over the input image. The hierarchies in this work are computed with a watershed by volume hierarchy [53] created over a 4-adjacency graph. The graph is weighted by the a combination of a simple RGB gradient and the PoolNet gradient [54].

To create the PoolNet+RGB gradient, we compute a weighted average of both gradients. Let $x$ be an element of the gradient, its value is given by:

$$ PoolNet + RGB(x) = \gamma Poolnet(x) + (1 - \gamma) RGB(x) \quad (14) $$

In this work, we set the value of $\gamma$ as 0.7.

## 7.2 Evaluation metrics

The evaluation procedure and metrics used to evaluate the markers generated using our method are described in this section.

During training, we resize the images to a fixed size of 320 × 320, and the network output is a fuzzy marker, i.e., taking values in [0, 1], also with size of 320 × 320. During the evaluation process, we compute the markers using our network, and resize them to the original image size. For computing some of the evaluation metrics regarding the

geometric properties of the proposed markers, the markers must be binary. So, to compute the evaluation metrics, we binarize the markers generated by the network by taking the values higher than a threshold, set at 0.5. It is important to note that we only binarize markers to compute the evaluation metrics, and not during the training of the network.

Let $\mathcal{O}$ and $\mathcal{B}$ be binarized markers, and let $S_i(\mathcal{O}, \mathcal{B})$ be the segmentation with respect to the markers $\mathcal{O}$ and $\mathcal{B}$ for an image $D_i$. Let $\hat{S}_i$ be the segmentation ground-truth for $D_i$. The first evaluation metric used is the vastly used IoU segmentation metric, defined as follows:

$$ IoU(S_i(\mathcal{O}, \mathcal{B}), \hat{S}_i) = \frac{S_i(\mathcal{O}, \mathcal{B}) \cap \hat{S}_i}{S_i(\mathcal{O}, \mathcal{B}) \cup \hat{S}_i} \quad (15) $$

In the second metric, we evaluate the relative size between the proposed markers and the object of interest. This is computed with the size regularization metric over the binarized markers. For a given marker $\mathcal{O}$ and a segmentation ground-truth $\hat{S}_O$, the relative size metric is given by:

$$ R_{size}(\mathcal{O}, \hat{S}_O) = \frac{\sum_{x \in D} \mathcal{O}(x)}{\sum_{x \in D} \hat{S}_O(x)}. \quad (16) $$

The third metric measures the number of connected components on each proposed marker. We denote the number of connected components of a marker $\mathcal{O}$ by $CC(\mathcal{O})$.

Finally, we also propose a metric to measure the thinness of the proposed markers. Ideally, if
<table><caption>**Table 3:** Evaluation metrics computed for all datasets, using learned background markers. The dataset used for training is highlighted in blue.</caption><thead><tr><th rowspan="2">Dataset</th><th rowspan="2">Average IoU</th><th colspan="3">Object marker</th><th colspan="3">Background Marker</th></tr><tr><th>Connected Components</th><th>Average Relative Size</th><th>Average Thiness</th><th>Connected Components</th><th>Average Relative Size</th><th>Average Thiness</th></tr></thead><tbody><tr><td>MS COCO</td><td>0.506</td><td>3.304</td><td>178.9%</td><td>11.52</td><td>14.504</td><td>6.2%</td><td>5.493</td></tr><tr><td>Weizmann</td><td>0.704</td><td>3.630</td><td>19.9%</td><td>7.67</td><td>12.810</td><td>5.6%</td><td>3.396</td></tr><tr><td>Horses</td><td>0.841</td><td>3.933</td><td>23.2%</td><td>10.61</td><td>21.966</td><td>6.3%</td><td>4.936</td></tr><tr><td>GeoStar</td><td>0.706</td><td>2.894</td><td>23.3%</td><td>13.22</td><td>15.974</td><td>4.2%</td><td>4.478</td></tr><tr><td>MSRA10K</td><td>0.752</td><td>3.311</td><td>23.1%</td><td>9.70</td><td>13.553</td><td>4.5%</td><td>3.664</td></tr><tr><td>Pascal VOC</td><td>0.578</td><td>3.422</td><td>67.2%</td><td>9.71</td><td>14.847</td><td>4.6%</td><td>4.438</td></tr></tbody></table>

the proposed markers look like scribbles or points located on the image, they should not be too thick. To measure the thinness of a marker, we measure the maximum value obtained from an Euclidean distance map computed on the marker. We compute this metric for each connected component in the set of markers and compute a global average to get the final metric. Let $C$ be the set of all connected components computed on the crisp markers produced for a dataset. Let $EDT(x)$ be the Euclidean distance map of a marker $x \in C$. The thinness metric is given by:

$$Thinness(C) = \frac{\sum_{x \in C} max(EDT(x))}{|C|}. \quad (17)$$

In other words, this metric measures the maximum thickness of a marker in terms of the number of pixels at its widest point.

## 7.3 Results

We first evaluate our method over the MS COCO dataset, the one used to train the network. Qualitative results are shown in Figure 5. We can see in the figure some examples of the MS COCO dataset, with the generated object markers, and the fixed background markers used for training the network, i.e., four clicks near the corners of the image. We can observe that, for most cases, it is possible to recover good object segmentations by using the automatically generated markers. For the fourth image from top to bottom, the produced segmentation is not desirable, as there is a leakage of the segmentation from the ball to the floor. This happens due to a combination of two factors: the object is small, and the proposed markers might touch an area outside the borders of the object; the saliency map used for the segmentation does not strongly delineate the

boundaries between the ball and the other regions in the image that are adjacent to the ball. It is possible to observe that the markers follow some of the desired shape characteristics, such as being smaller than the object of interest, smooth and composed by a small number of connected components. This behavior can be observed both on the MS COCO Dataset and on the four unseen ones.

In Table 2, the evaluation metrics are shown for all datasets, with the results for the MS COCO dataset (the one used for training) highlighted in blue. The metrics shown are an average over the validation sets of MSRA10K and Pascal VOC datasets, and over the complete dataset for Weizmann single object, Weizmann Horses and GeoStar. For the MS COCO dataset, we use a subset of 800 images to evaluate our model, made available in [19].

The *CC*, *R<sub>size</sub>* , and *Size* metrics confirm that the generated markers follow the desirable characteristics. The average number of connected components over all datasets is 3.371, showing that the proposed markers are indeed formed by a small number of components. Furthermore, the markers are smaller than the objects of interest, and relatively thin, having an average thinness of 10.4 pixels (distance between the border of the object and the center at the thickest area).

We can observe from the *IoU* metric that the network is able to propose markers that recover a good segmentation for the MS COCO subset used for testing, as well as for the unseen datasets. The lowest *IoU* scores were achieved on the Pascal VOC and MS COCO datasets. This is expected, as the images from both datasets are much more complex compared to the other datasets used in this work, containing multiple objects with varied sizes, including very small objects in some cases.
<figure><img src="image_13.png" /><figcaption>**Fig. 6:** Results for samples of the MS COCO validation subset, and for the unseen datasets, using learned background markers. From left to right: input image; object and background cues superimposed over the saliency map representation of the hierarchy constructed for the input image; intermediary segmentation; object markers proposed by the network, superimposed over the saliency map; background markers proposed by the network, superimposed over the saliency map; marker-based segmentation; ground-truth segmentation.</figcaption></figure>

In Figure 7, we can observe the IoU scores for each dataset, sorted by object size. To compute this metric we first sort all images on a non-decreasing order of object size (in number of pixels). Then, to smooth the curves we compute a moving average over the results. We can observe that for the *GeoStar*, *MS COCO*, and *Pascal VOC* datasets the IoU scores increase as the size of the objects of interest increase, and in the remaining of the datasets, the IoU scores are more evenly distributed over the different object sizes. This is expected, since on the *Weizmann*, *Horses*, and *MSRA10K* we have only one salient object per image with a big size in average. On the other

hand, *MS COCO*, and *Pascal VOC* contain multiple objects per image with varying sizes, including very small objects. Producing a good segmentation for these very small objects can be quite challenging, thus the smaller scores for smaller objects.

## 7.4 Background markers proposal

Initially, in the setup used for producing the results presented in Section 7.3, we train our marker learning network to propose object markers, and use fixed background markers, i.e., four clicks near the corners of the image, for producing our image segmentations. In this Section, we present the results regarding the proposed
<figure><img src="image_14.png" /><figcaption>**Fig. 7:** Intersection over union scores sorted by object size. For each dataset, the objects are ordered in non-decreasing order by size in area of pixels. The line in black represents the average *IoU* for each dataset.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>**Fig. 8:** Bar plot of the average IoU scores obtained using the FMBS for each dataset, showing in red the results when using the initial cues as markers, in green, using the learned object markers and the four clicks near the corners as background markers, and in blue the learned object and background markers.</figcaption></figure>

pipeline for automatically proposing object and background markers, presented in Section 6.2.

In Figure 6, we provide samples of the learned object and background markers for the MS COCO validation subset. We can observe that the proposed background markers are usually composed by a larger number of connected components when compared to the proposed object markers, but are

generally thinner. This observation is evidenced in Table 3, where for every dataset, we have a higher number of connected components and smaller average thinness when compared to the results shown in Table 2, which considers only the proposed object markers. Additionally, if we compare the *IoU* scores on Figure 8, we can observe that by using the proposed background markers we achieve better segmentation results in four of the six datasets used in our evaluation.

For the Horses, MS COCO, Pascal VOC and GeoStar datasets, we see an increase of segmentation quality of approximately 11% in average when using the learned background markers. For the Weizmann and MSRA10K datasets we see a decrease in segmentation quality. This can be attributed to the fact that the intermediate segmentation network is trained in the scenario where we have multiple objects per image, and small objects in scene. The Weizmann and MSRA10K datasets contain samples with only one big salient object per image. This fact contributes to the creation of bad intermediate segmentations, which consequently lead to bad object and background marker proposals, as it can be observed on the example on the bottom row of Figure 6.

In Figure 8, the mean *IoU* scores for each dataset employed in our assessment are presented.
<figure><img src="image_16.png" /><figcaption>**Fig. 9:** Comparison of evaluation metrics across all datasets for object markers predicted by networks trained under different configurations. In each plot, the bars (from blue to purple) represent the network with all regularization functions, followed by versions trained without $L_{size}$, without $L_{Dmap}$, without $L_{TV}$, and without $L_{comp}$, respectively.</figcaption></figure>

Three distinct marker configurations, in conjunction with the FMBS method, were utilized. In one configuration, the initial cues were utilized as markers, in another, the learned object markers were employed alongside four clicks near the corners, which served as background markers. These configurations were compared to a scenario where both learned object and background markers were used concurrently. It is discernible that employing the proposed markers consistently enhances segmentation quality across all datasets when compared to the initial cues, indicating the greater robustness of the information encoded in the proposed markers compared to the cues.

## 8 Ablation Studies

To assess the effect of each regularization function in the markers proposed by our network, we conduct a series of ablation experiments by

removing one regularization term at a time and evaluating its effects on the generated markers. We then assess the impact of each regularization term removal on the evaluation metrics used in Section 7, and analyze the markers shape characteristics qualitatively. This study helps to identify the importance of each regularization term and how they collectively contribute to producing effective and user-friendly markers.

To evaluate the impact of each regularization term on the created markers, we use the network trained with all regularization functions as the baseline. The baseline configuration is precisely the one used to produce the results in Section 7. To contrast with this default setting, we train four additional versions of the marker proposal network, each omitting a single regularization term: one without $L_{size}$, one without $L_{Dmap}$, one without $L_{comp}$ and one without $L_{TV}$. This allows us
<figure><img src="image_17.png" /><figcaption>**Fig. 10:** Evaluation of regularization functions on the learned markers. From left to right: the original image, followed by the markers predicted by the network with all regularization functions applied, and then with each regularization function removed individually: without $L_{size}$, without $L_{dmap}$, without $L_{comp}$, and without $L_{TV}$, respectively.</figcaption></figure>

to isolate the effect of each regularization function and analyze the shape characteristics of the produced markers.

In Figure 10, a qualitative analysis is presented, showing examples of object markers produced under each network configuration. Additionally, the comparison of the evaluation metrics for each configuration are presented in Figure 9.

By comparing the results obtained from the baseline network and the ones obtained without the use of $L_{size}$, presented on Figure 10, one can observe that the removal of $L_{size}$ leads the network to consistently generate larger markers, in number of pixels. This behavior is consistent with the $R_{size}$ metric shown in Figure 9, as for all datasets, the average relative size and average thinness increases when $L_{size}$ is removed from the total loss. The removal of $L_{Dmap}$ shows a similar outcome, as without $L_{Dmap}$, the produced markers are larger. This is expected, since $L_{Dmap}$ has a similar nature to $L_{size}$, penalizing high activations in the location of the object of interest, but opposed to $L_{size}$, in $L_{Dmap}$ elements close to

the border of the object suffer a higher penalization. Although, there is no clear indication that the markers produced $L_{Dmap}$ are more centralized than the ones produced with $L_{size}$.

In the results presented on Figure 10, the markers produced without $L_{comp}$ are composed by a larger number of connected components when compared to the baseline configuration. This effect can also be observed in Figure 9, as the average number of connected components also increases when we remove the $L_{comp}$ term from the total loss. The markers produced without $L_{comp}$ also have a tendency of being less smooth. This happens because when a marker contains closely spaced but separated components, $L_{comp}$ either tries to erase one, or to merge both, leading to markers that have fewer and more continuous components.

On the last column of Figure 10, the markers produced without $L_{TV}$ are shown. By removing the $L_{TV}$ regularization, the proposed markers present a more rough, irregular shape, compared
to the ones produced under the baseline configuration. It is possible to observe that some markers, such as the one in the second row, contain holes in its structures, and others, such as the one in the final row, are composed by a larger number of connected components. This effect happens since $L_{TV}$ not only favors smoothness from a spatial point of view, but also from a spectral one. Fuzzy markers that have a big discontinuity in value, when binned, might contain holes in its structures or be completely separated into multiple components. This behavior is evidenced in the results presented in Figure 9, as the average number of connected components increase when $L_{TV}$ is removed from the total loss.

## 9 Conclusion and future work

In this work, we have proposed a novel segmentation layer that can be used together with neural networks to create an end-to-end trainable marker learning architecture. In the limit case where the fuzzy markers tend to be binary, the results of the new proposed segmentation layer tend towards those of the widely used marker based segmentation described in [6], so that the proposed learned markers are adapted to (reduce the effort of) the users of this popular method. We showed that by using the proposed layer and a loss function composed by a segmentation loss and a set of regularization functions that control the shape of the markers, we can automatically generate markers that recover a good segmentation and have desirable shape characteristics. This behavior is observed on the dataset used for training, as well as on four unseen datasets.

In future works, we plan to continue the studies on the marker learning problem, exploring new regularization functions that favor desirable features on markers. We would also like to insert users in the training loop, to learn from their feedback and corrections on the proposed markers in order to improve the quality of those generated in the future.

**Acknowledgements.** This work was partially financially supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico – CNPq – (Universal 407242/2021-0, PQ 306573/2022-9, 42950/2023-3), the Fundação de Amparo a Pesquisa do Estado de Minas Gerais – FAPEMIG

– (PPM-00006-18 and APQ-01079-23), and the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – CAPES (Finance code 001 and COFECUB 88887.191730/2018-00). This work is also supported by the French ANR grant ANR-20-CE23-0019. The authors also thank PUC Minas for the support during this work.

## References

[1] Bai, X. & Sapiro, G. Geodesic matting: A framework for fast interactive image and video segmentation and matting. *International journal of computer vision* **82**, 113–132 (2009).

[2] Cousty, J., Bertrand, G., Najman, L. & Couprie, M. Watershed cuts: Minimum spanning forests and the drop of water principle. *IEEE transactions on pattern analysis and machine intelligence* **31**, 1362–1374 (2008).

[3] Grady, L. Random walks for image segmentation. *IEEE transactions on pattern analysis and machine intelligence* **28**, 1768–1783 (2006).

[4] Rother, C., Kolmogorov, V. & Blake, A. "Grabcut": interactive foreground extraction using iterated graph cuts. *ACM transactions on graphics (TOG)* **23**, 309–314 (2004).

[5] Jang, W.-D. & Kim, C.-S. Interactive image segmentation via backpropagating refinement scheme. *In IEEE Conference on Computer Vision and Pattern Recognition* 5297–5306 (2019).

[6] Salembier, P. & Garrido, L. Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval. *IEEE transactions on Image Processing* **9**, 561–576 (2000).

[7] Malmberg, F., Nordenskjöld, R., Strand, R. & Kullberg, J. Smartpaint: a tool for interactive segmentation of medical volume images. *Computer Methods in Biomechanics and Biomedical Engineering: Imaging and Visualization* **5**, 36–44 (2017).
[8] Falcão, A. X. & Bergo, F. P. Interactive volume segmentation with differential image foresting transforms. *IEEE Transactions on Medical Imaging* **23**, 1100–1108 (2004).

[9] Perret, B., Cousty, J., Ura, J. C. R. & Guimarães, S. J. F. Evaluation of morphological hierarchies for supervised segmentation. *International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing* 39–50 (2015).

[10] Lebon, Q., Lefèvre, J., Cousty, J. & Perret, B. Incremental watershed cuts: Interactive segmentation algorithm with parallel strategy. *Pattern Recognition Letters* (2024). URL https://www.sciencedirect.com/science/article/pii/S016786552400360X.

[11] Da Fonseca, G. B., Negrel, R., Perret, B., Cousty, J. & Guimaraes, S. J. F. New hierarchy-based segmentation layer: towards automatic marker proposal. *Proceedings - 2021 34th SIBGRAPI Conference on Graphics, Patterns and Images, SIBGRAPI 2021* 354–361 (2021).

[12] Boykov, Y. Y. & Jolly, M.-P. Interactive graph cuts for optimal boundary & region segmentation of objects in nd images. *Proceedings eighth IEEE international conference on computer vision. ICCV 2001 1*, 105–112 (2001).

[13] Li, Y., Sun, J., Tang, C.-K. & Shum, H.-Y. Lazy snapping. *ACM Trans. Graph.* **23**, 303–308 (2004).

[14] Tong, H., Faloutsos, C. & Pan, J.-y. Fast random walk with restart and its applications. *Sixth International Conference on Data Mining (ICDM’06)* 613–622 (2006).

[15] Adams, R. & Bischof, L. Seeded region growing. *IEEE Transactions on Pattern Analysis and Machine Intelligence* **16**, 641–647 (1994).

[16] Vachier, C. & Meyer, F. The viscous watershed transform. *Journal of Mathematical Imaging and Vision* **22**, 251–267 (2005).

[17] Falcão, A. X., Stolfi, J. & de Alencar Lotufo, R. The image foresting transform: Theory, algorithms, and applications. *IEEE transactions on pattern analysis and machine intelligence* **26**, 19–29 (2004).

[18] Xu, N., Price, B., Cohen, S., Yang, J. & Huang, T. S. Deep interactive object selection. *In IEEE Conference on Computer Vision and Pattern Recognition* 373–381 (2016).

[19] Li, Z., Chen, Q. & Koltun, V. Interactive image segmentation with latent diversity. *In IEEE Conference on Computer Vision and Pattern Recognition* 577–585 (2018).

[20] Kirillov, A. et al. Segment anything. *Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)* 4015–4026 (2023).

[21] Kucharski, A. & Fabijańska, A. Cnn-watershed: A watershed transform with predicted markers for corneal endothelium image segmentation. *Biomedical Signal Processing and Control* **68**, 102805 (2021).

[22] Cerrone, L., Zeilmann, A. & Hamprecht, F. A. End-to-end learned random walker for seeded image segmentation. *In IEEE Conference on Computer Vision and Pattern Recognition* 12559–12568 (2019).

[23] Liu, X., Blusseau, S. & Velasco-Forero, S. Counting melanocytes with trainable h-maxima and connected component layers. *Discrete Geometry and Mathematical Morphology* 417–430 (2024).

[24] Velasco-Forero, S., Rhim, A. & Angulo, J. Fixed point layers for geodesic morphological operations. *British Machine Vision Conference (BMVC)* (2022).

[25] Velasco-Forero, S., Pagès, R. & Angulo, J. Learnable empirical mode decomposition based on mathematical morphology. *SIAM Journal on Imaging Sciences* **15**, 23–44 (2022).
[26] Challa, A., Danda, S., Sagar, B. S. D. & Najman, L. Triplet-watershed for hyperspectral image classification. *IEEE Transactions on Geoscience and Remote Sensing* **60**, 1–14 (2022).

[27] Cousty, J., Najman, L., Kenmochi, Y. & Guimarães, S. Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps. *Journal of Mathematical Imaging and Vision* **60**, 479–502 (2018).

[28] Murtagh, F. & Contreras, P. Algorithms for hierarchical clustering: an overview. *Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery* **2**, 86–97 (2012).

[29] Benzecri, J.-P. et al. L'analyse des données. 1. la taxinomie. *Paris: Dunod* **195**, 196 (1973).

[30] Udupa, J. K. & Samarasekera, S. Fuzzy connectedness and object definition: Theory, algorithms, and applications in image segmentation. *Graphical models and image processing* **58**, 246–261 (1996).

[31] Audigier, R. & Lotufo, R. Duality between the watershed by image foresting transform and the fuzzy connectedness segmentation approaches. *2006 19th Brazilian Symposium on Computer Graphics and Image Processing* 53–60 (2006).

[32] Audigier, R. & de Alencar Lotufo, R. Banon, G. J. F. (ed.) *Watershed by image foresting transform, tie-zone, and theoretical relationships with other watershed definitions*. (ed.Banon, G. J. F.) *8th ISMM 2007: Rio de Janeiro, Brazil - Volume 1*, 277–288 (MCT/INPE, 2007).

[33] Allène, C., Audibert, J., Couprie, M., Cousty, J. & Keriven, R. Banon, G. J. F. (ed.) *Some links between min-cuts, optimal spanning forests and watersheds*. (ed.Banon, G. J. F.) *8th ISMM 2007: Rio de Janeiro, Brazil - Volume 1*, 253–264 (MCT/INPE, 2007).

[34] Cousty, J., Bertrand, G., Najman, L. & Couprie, M. Watershed cuts: Thinnings, shortest path forests, and topological watersheds.

*IEEE Transactions on Pattern Analysis and Machine Intelligence* **32**, 925–939 (2010).

[35] Bertrand, G. On topological watersheds. *Journal of Mathematical Imaging and Vision* **22**, 217–230 (2005).

[36] Saha, P. K. & Udupa, J. K. Relative fuzzy connectedness among multiple objects: theory, algorithms, and applications in image segmentation. *Computer Vision and Image Understanding* **82**, 42–56 (2001).

[37] Strickert, M. & Hüllermeier, E. Notes on soft minimum and other function approximations. *MIWOCI Workshop-2013* 60 (2013).

[38] Goodfellow, I., Bengio, Y. & Courville, A. *Deep learning* (MIT press, 2016).

[39] Meijster, A., Roerdink, J. B. T. M. & Hesselink, W. H. A general algorithm for computing distance transforms in linear time. *Mathematical Morphology and its Applications to Image and Signal Processing* 331–340 (2000).

[40] Saito, T. & Toriwaki, J.-I. New algorithms for euclidean distance transformation of an n-dimensional digitized picture with applications. *Pattern Recognition* **27**, 1551–1565 (1994).

[41] Hirata, T. A unified linear-time algorithm for computing distance maps. *Information Processing Letters* **58**, 129–133 (1996).

[42] Perret, B. & Cousty, J. Component tree loss function: Definition and optimization. *International Conference on Discrete Geometry and Mathematical Morphology* 248–260 (2022).

[43] Clough, J. et al. A topological loss function for deep-learning based image segmentation using persistent homology. *IEEE Transactions on Pattern Analysis and Machine Intelligence* (2020).

[44] Hazirbas, C., Ma, L., Domokos, C. & Cremers, D. Fusenet: Incorporating depth into semantic segmentation via fusion-based
cnn architecture. Computer Vision-ACCV
2016: 13th Asian Conference on Computer
Vision, Taipei, Taiwan, November 20-24,
2016, Revised Selected Papers, Part I 13
213-228 (2017).

[45] Yakubovskiy, P. Segmentation models pytorch. GitHub repository (2020). URL https://github.com/qubvel/segmentation Models.pytorch.

[46] Alpert, S., Galun, M., Brandt, A. & Basri, R. Image segmentation by probabilistic bottom-up aggregation and cue integration. *IEEE Transactions on Pattern Analysis and Machine Intelligence* **34**, 315–327 (2011).

[47] Borenstein, E. & Ullman, S. Learning to segment. Computer Vision-ECCV 2004: 8th European Conference on Computer Vision 315–328 (2004).

[48] Gulshan, V., Rother, C., Criminisi, A., Blake, A. & Zisserman, A. Geodesic star convexity for interactive image segmentation. In *IEEE Conference on Computer Vision and Pattern Recognition* 3129–3136 (2010).

[49] Everingham, M. & Winn, J. The pascal visual object classes challenge 2012 (voc2012) development kit. PASCAL, Tech. Rep **8** (2011).

[50] Rhemann, C. et al. A perceptually motivated online benchmark for image matting. In *IEEE Conference on Computer Vision and Pattern Recognition* 1826–1833 (2009).

[51] Cheng, M.-M., Mitra, N. J., Huang, X., Torr, P. H. & Hu, S.-M. Global contrast based salient region detection. *IEEE Transactions on Pattern Analysis and Machine Intelligence* **37**, 569–582 (2014).

[52] Milletari, F., Navab, N. & Ahmadi, S.-A. V-net: Fully convolutional neural networks for volumetric medical image segmentation. *2016 fourth international conference on 3D vision (3DV)* 565–571 (2016).

[53] Cousty, J. & Najman, L. Incremental algorithm for hierarchical minimum spanning

forests and saliency of watershed cuts. *International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing* 272–283 (2011).

[54] Liu, J. J., Hou, Q., Cheng, M. M., Feng, J. & Jiang, J. A simple pooling-based design for real-time salient object detection. *Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition* 2019-June, 3912–3921 (2019).

A Proofs of the properties of
Section 4.2

This appendix section provides the proofs of all
properties presented in Section 4.2.

*Proof of Property 1.* Let $o \in O$ be the element that minimizes $C_H(x, O)$, and let $b \in B$ be the element that minimizes $C_H(x, B)$. Let $O'$ be the smallest region that contains $x$ and $o$, and let $B'$ be the smallest region that contains $x$ and $b$. It is important to note that $C_H(x, O) = \omega(O')$ and $C_H(x, B) = \omega(B')$. If $C_H(x, O) < C_H(x, B)$, then $\omega(O') < \omega(B')$. This indicates that either $O'$ is included in $B'$, or $O'$ and $B'$ are disjoint and are both included in a third set $M$ such that $\omega(M) \ge \omega(B') > \omega(O')$.

In the first case, where $O' \subseteq B'$, every element in $O'$ has a connection value at most $\omega(O')$. This means that $x, o \in O'$ and $b \in B' \setminus O'$, hence $(x \cap O \ne \emptyset) \land (x \cap B = \emptyset)$.

In the second case, every element in $O'$ has a connection value at most $\omega(O')$. This means that $x, o \in O'$, and since $O'$ and $B'$ are disjoint, $(x \cap O \ne \emptyset) \land (x \cap B = \emptyset)$.

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

B Proofs of the properties of
Section 4.3

This appendix section provides the proofs of all
properties presented in Section 4.3.

*Proof of Property 3.* For any $y$ in $D$, $\mu(y) \le \mu'(y)$ implies that we have $\alpha(\mu(y)) \ge \alpha(\mu'(y))$ since $\alpha$ is decreasing and that $(1 - \mu(y) + d_H(x, y)) \ge (1 - \mu'(y) + d_H(x, y))$. Thus, for any $y$ in $D$, $\mu(y) \le \mu'(y)$ implies that $\mu(y)(1 - \mu(y) + d_H(x, y)) \ge \alpha(\mu'(y))(1 - \mu'(y) + d_H(x, y))$ since
$\alpha(\mu(y)), \alpha(\mu'(y)), (1 - \mu(y) + d_{\mathcal{H}}(x, y)), \text{ and } (1 - \mu'(y) + d_{\mathcal{H}}(x, y))$ are positive values. Thus, we deduce that $C_{\mathcal{H}}^f(x, \mu) \ge C_{\mathcal{H}}^f(x, \mu')$.

**Proof of Property 4.** Let $y$ in $D$. We have:

$$
\begin{align*}
C_{\mathcal{H}}^{f}(y, \mu_A) &= \min_{x \in D} \alpha(\mu_A(x))(1 - \mu_A(x) + d_{\mathcal{H}}(x, y)) \\
&= \min \left( \min_{x \in A} \alpha(\mu_A(x))(1 - \mu_A(x) + d_{\mathcal{H}}(x, y)), \right. \\
& \phantom{= \min} \left. \min_{x \in D \setminus A} \alpha(\mu_A(x))(1 - \mu_A(x) + d_{\mathcal{H}}(x, y)) \right) \\
&= \min \left( \min_{x \in A} \alpha(1)(1 - 1 + d_{\mathcal{H}}(x, y)), \right. \\
& \phantom{= \min} \left. \min_{x \in D \setminus A} \alpha(0)(1 - 0 + d_{\mathcal{H}}(x, y)) \right) \\
&= \min \left( \min_{x \in A} d_{\mathcal{H}}(x, y), \min_{x \in D \setminus A} \alpha(0)(1 + d_{\mathcal{H}}(x, y)) \right)
\end{align*}
$$

Then, by definition, $\alpha(0)$ is strictly greater than the maximal value of $d_{\mathcal{H}}$, which implies that $\min_{x \in D \setminus A} \alpha(0)(1 + d_{\mathcal{H}}(x, y))$ is strictly greater than $\min_{x \in A} d_{\mathcal{H}}(x, y)$. Therefore, we have $C_{\mathcal{H}}^f(y, \mu_A) = \min_{x \in A} d_{\mathcal{H}}(x, y) = C_{\mathcal{H}}(y, A)$. $\square$

**Proof of Property 6.** We have:

$$
\begin{align*}
S_{\mathcal{H}}(\mu_O, \mu_B) &= \{x \in D \mid C_{\mathcal{H}}^f(x, \mu_O) < C_{\mathcal{H}}^f(x, \mu_B)\} \\
&= \{x \in D \mid C_{\mathcal{H}}(x, O) < C_{\mathcal{H}}(x, B)\} \quad (\text{Prop. 4}) \\
&= S_{\mathcal{H}}^f(\mu_O, \mu_B)
\end{align*}
$$

## C Proofs of the properties of Section 4.4

This appendix section provides the proofs of all properties presented in Section 4.4.

**Proof of Property 7.** Let us first prove Property 7.1. Note that $D \setminus A \cup A = D$. Since $\alpha(0) = \infty$ and $(1 - \mu(y) + d_{\mathcal{H}}(y, x))$ is non-negative for every $x, y \in D$:

$$
\begin{align*}
y \in D \setminus A, \quad C_{\mathcal{H}}^{f}(\mu \downarrow_A, x) &= \infty, \quad \text{hence,} \\
C_{\mathcal{H}}^{f}(\mu \downarrow_A, x) &= \min_{y \in D} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x)) \\
&= \min \left( \min_{y \in A} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x)), \right.
\end{align*}
$$

$$
\begin{align*}
& \min_{y \in D \setminus A} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x)) \\
&= \min \left( \min_{y \in A} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x)), \infty \right) \\
&= \min_{y \in A} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x))
\end{align*}
$$

Now, we will prove Property 7.2. Note that $d_{\mathcal{H}}(x, x) = 0$ for every element $x \in D$. If $A$ is empty, then $\mu \downarrow_A (y) = 0$ for every element $y \in D$. Then,

$$
\begin{align*}
C_{\mathcal{H}}^{f}(\mu \downarrow_A, x) &= \min_{y \in D} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x)) \\
&= \min_{y \in D} \alpha(0)(1 - 0 + d_{\mathcal{H}}(y, x)) \\
&= \alpha(0)(1 - 0 + d_{\mathcal{H}}(x, x)) \\
&= \alpha(0)(1 - 0 + 0) \\
&= \alpha(0)
\end{align*}
$$

**Proof of Property 8.** We have:

$$
\begin{align*}
C_{\mathcal{H}}^{f}(\mu \downarrow_{A \cup B}, x) &= \\
& \quad \min_{y \in A \cup B} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x)) \quad (\text{Prop. 7}) \\
&= \min \left( \min_{y \in A} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x)), \right. \\
& \phantom{= \min} \left. \min_{y \in B} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x)) \right) \\
&= \min \left( C_{\mathcal{H}}^{f}(\mu \downarrow_{A}, x), C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, x) \right) \quad (\text{Prop. 7})
\end{align*}
$$

**Proof of Lemma 9.** Let us begin by proving Lemma 9.1. Let $L$ be the smallest region that contains both $A$ and $B$, let $X$ be a region included in $A$ and let $Y$ be a region included in $B$. Suppose that $M$ is the smallest region of $\mathcal{H}$ that contains the elements $X$ and $Y$. Then, since $A$ and $B$ are disjoint, $M$ must contain $A$ and $B$ in order to contain $X$ and $Y$.

By the definition of $L$, it is the smallest region that contains both $A$ and $B$. Thus, any other region containing $A$ and $B$ must also contain $L$. Now, since $M$ is the smallest region containing $X$ and $Y$, it cannot be larger than $L$, because $L$ already contains both $A$ and $B$, and hence $X$ and $Y$. Therefore, $M$ must be equal to $L$.
Then, for every element $a$ of $A$ and $b$ of $B$, $d_{\mathcal{H}}(A, B) = d_{\mathcal{H}}(a, b)$, since the smallest region that contains both $A$ and $B$ must be the smallest region that contains both an element of $A$ and an element of $B$ (since $A$ and $B$ are disjoint). Let $m$ and $n$ be elements of $A$. Then, we have:

$$
\begin{align*}
C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, m) &= \min_{y \in B} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, m)) \quad (\text{Prop. 7}) \\
&= \min_{y \in B} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(A, B)) \\
&= \min_{y \in B} \alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, n)) \\
&= C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, n)
\end{align*}
$$

Let us now prove Lemma 9.2. The sets $A$ and $D \setminus A$ are disjoint. As $A$ is a region of $\mathcal{H}$, $D \setminus A$ is represented in $\mathcal{H}$ as a union of regions, all disjoint from $A$. Let $m$ and $n$ be elements of $A$. Then, we have:

$$
C_{\mathcal{H}}^{f}(\mu \downarrow_{D \setminus A}, m) = \min_{B \in D \setminus A} C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, m). \quad (\text{Prop. 8})
$$

As shown in Lemma 9.1, if $A$ and $B$ are disjoint, $C_{\mathcal{H}}^f(\mu \downarrow_B, m) = C_{\mathcal{H}}^f(\mu \downarrow_B, n)$. So, we have:

$$
\begin{align*}
\min_{B \in D \setminus A} C_{\mathcal{H}}^{f}(\mu \downarrow_B, m) &= \min_{B \in D \setminus A} C_{\mathcal{H}}^{f}(\mu \downarrow_B, n) \\
&= C_{\mathcal{H}}^{f}(\mu \downarrow_{D \setminus A}, n)
\end{align*}
$$

□

*Proof of Theorem 11.* Let us first prove Theorem 11.1. Let $x$ be any element of $A$. From Definition 10, we have:

$$
T_{\mathcal{H}}^{\mu}(A) = C_{\mathcal{H}}^{f}(\mu \downarrow_{D \setminus A}, x).
$$

As $\mathcal{H}$ is a binary hierarchy, we have $A \cup B = C$ and $D \setminus A = (D \setminus C) \cup (C \setminus A)$. Since $B$ is the sibling of $A$, the regions $A$ and $B$ are disjoint. Thus, we deduce that $D \setminus A = (D \setminus C) \cup B$. Therefore, from Property 8, we deduce that:

$$
T_{\mathcal{H}}^{\mu}(A) = \min\{C_{\mathcal{H}}^{f}(\mu \downarrow_{D \setminus C}, x), C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, x)\}.
$$

As $A \subseteq C$, we can affirm that $x$ belongs to $C$. By Definition 10, we have:

$$
T_{\mathcal{H}}^{\mu}(A) = \min\{T_{\mathcal{H}}^{\mu}(C), C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, x)\}. \quad (18)
$$

By Property 7, we have:

$$
C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, x) = \min\{\alpha(\mu(y))(1 - \mu(y) + d_{\mathcal{H}}(y, x)) \\
\qquad \mid y \in B\}. \qquad (19)
$$

As $x$ belongs to $A$, as $y$ belongs to $B$ and as $C$ is the smallest region of $\mathcal{H}$ that includes both $A$ and $B$, we have $d_{\mathcal{H}}(y, x) = \omega(C)$. Thus, from Equation 19, we deduce that

$$
C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, x) = \min\{\alpha(\mu(y))(1 - \mu(y) + \omega(C)) \\ \qquad \mid y \in B\}.
$$

As $\alpha$ is decreasing (Definition 2), the expression $\alpha(\mu(y))(1 - \mu(y) + \omega(C))$ is decreasing with respect to $\mu(y)$. Thus, it is minimized when $\mu(y)$ is maximized. Since $m = \max\{\mu(y) \mid y \in B\}$, we deduce that:

$$
C_{\mathcal{H}}^{f}(\mu \downarrow_{B}, x) = \alpha(m)(1 - m + \omega(C)). \quad (20)
$$

From Equations 18 and 20, we deduce that

$$
T_{\mathcal{H}}^{\mu}(A) = \min\{T_{\mathcal{H}}^{\mu}(C), \alpha(m)(1 - m + \omega(C))\},
$$

which completes the proof of Theorem 11.1.

Let us now establish Theorem 11.2. If $R = D$, then, from Definition 10, we deduce that $T_{\mathcal{H}}^{\mu}(R) = C_{\mathcal{H}}^{f}(\mu \downarrow_{\emptyset}, x)$ for any $x$ in $D$. Then, by Property 7 (second statement), we deduce that $T_{\mathcal{H}}^{\mu}(R) = \alpha(0)$. $\square$

*Proof of Theorem 12.* By the very definition of the restriction of a set, we have $C_{\mathcal{H}}^{f}(\mu, x) = C_{\mathcal{H}}^{f}(\mu \downarrow_{D}, x)$. Since $D = \{x\} \cup (D \setminus \{x\})$, by Property 8, we have $C_{\mathcal{H}}^{f}(\mu, x) = \min\{C_{\mathcal{H}}^{f}(\mu \downarrow_{D \setminus \{x\}}, x), C_{\mathcal{H}}^{f}(\mu \downarrow_{\{x\}}, x)\}$. Then, it can be easily seen from Definition 10 that

$$
C_{\mathcal{H}}^{f}(\mu, x) = \min\{T_{\mathcal{H}}(\{x\}), C_{\mathcal{H}}^{f}(\mu \downarrow_{\{x\}}, x)\}. \quad (21)
$$

By Property 7, we deduce that:

$$
C_{\mathcal{H}}^{f}(\mu \downarrow_{\{x\}}, x) = \alpha(\mu(x))(1 - \mu(x) + d_{\mathcal{H}}(x, x)).
$$

Furthermore, since $d_{\mathcal{H}}(x, x) = 0$, we deduce from Equation 21 that

$$
C_{\mathcal{H}}^{f}(\mu, x) = \min\{T_{\mathcal{H}}(\{x\}), \alpha(\mu(x))(1 - \mu(x))\},
$$

which completes the proof of Theorem 12 $\square$