# Measuring Hierarchiness of Image Segmentations

Felipe Belém, Fábio Kochem, Alexandre Falcão, Zenilton Patrocínio, Silvio Jamil F. Guimarães, Benjamin Perret, Jean Cousty

► To cite this version:

Felipe Belém, Fábio Kochem, Alexandre Falcão, Zenilton Patrocínio, Silvio Jamil F. Guimarães, et al. Measuring Hierarchiness of Image Segmentations. 37th SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI 2024), Sep 2024, Manaus, Brazil. 10.1109/SIBGRAPI62404.2024.10716344. hal-04826627

HAL Id: hal-04826627

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

Submitted on 9 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Measuring Hierarchiness of Image Segmentations

Felipe Belém*†‡, Fábio Kochem*, Alexandre Falcão.†, Zenilton Patrocínio Jr.*, Silvio Jamil F. Guimarães*, Benjamin Perret‡ and Jean Cousty‡

*IMScience, Pontifical Catholic University of Minas Gerais – Minas Gerais, Brazil 30535-901

Email: {felipebelem,sjamil,zenilton}@pucminas.br, fabiofkochem@gmail.com

†LIDS, University of Campinas – São Paulo, Brazil 13083-970

Email: {felipe.belem,afalcao} @ic.unicamp.br

‡LIGM, Université Gustave-Eiffel, CNRS – Marne-la-Valée, France F-77454

Email: {felipe.belem,benjamin.perret,jean.cousty}@esiee.fr

*Abstract*—Numerous segmentation methods are able to produce several partitions of the same image by tuning a scale parameter. In such a series of multilevel segmentations, if every region at a given level is included in a single region of the segmentation at the next level, then the series is called a hierarchy. Hierarchies are often desired for multiscale image representation and analysis due to their mathematical properties, leading to accurate and efficient solutions. Although certain effective strategies may not produce a hierarchy, it is uncertain whether their multiscale output is close to be one. This work explores several cases when analyzing two consecutive segmentations, as full inflation and full merge, for instance. From those, we provide three measures for evaluating the hierarchiness between two subsequent partitions: (i) nestedness; (ii) refinement error; and (iii) inflation ration. Using our proposals in a in-sequence pairwise comparison, as shown by the experimental results, it is possible to verify whether a multiscale segmentation is a hierarchy and, if not, to analyze the nature and extent of the hierarchical errors that prevent it from becoming hierarchical.

I. INTRODUCTION

In segmentation, an image is partitioned into several regions
so that the object can be built by its comprising parts (ideally
only one). However, in certain applications, the mere construc-
tion of one partition is insufficient for calculating, for instance,
the object's saliency. For that, one may generate several
partitions so that the object information is presented in several
and different granularities, from few to many regions produced
(i.e., coarser to finer segmentations). Consequently, finer re-
gions describe the object's characteristics with higher level of
details, crucial for extracting local information, whilst coarser
ones describe global information of the object, reducing the
redundancy from finer partitions. Several works [1], [2] recur
to such multiscale segmentation, where each segmentation is
named as *scale* or *layer*.

Two strategies are often used for computing a multiscale
segmentation. One builds a *hierarchical segmentation* so that
any desired partition can be obtained efficiently. If all possible
partitions are generated, then it is a *dense hierarchy*. But, if
only a subset of the latter suffices, then it is *sparse* [3], as
presented in Fig. 1. Conversely, *non-hierarchical* approaches
build the necessary amount of partitions through one or
several executions of the same algorithm. In the end, effective

hierarchical and non-hierarchical approaches aim to accurately
delineate the objects of interest in all scales.

Although every hierarchical segmentation sequence is a
multiscale one, the converse is not necessarily true since the
former only made possible if every region on a finer scale
is included in the subsequent coarser scale. By executing
the same algorithm with different parameters, several ap-
proaches [4], [5] output multiscales that violate two principles
in hierarchical segmentation [6]. If borders of coarser regions
do not overlap those at finer scales, then it violates the *locality
principle*. Also, if the quantity of regions varies in a non-strict
monotonical behavior within a multiscale, then it violates the
*causality principle*. As a result, numerous properties on hier-
archies, which may assist in terms of efficiency and efficacy,
are not applicable in such series of partitions, independently
of the degree of violation. For instance, the task of generating
scales presenting effective object delineation can be reduced
as a meticulous node-selection procedure only in hierarchical
approaches. Conversely, non-hierarchical strategies [5] allow
object delineation corrections at each new execution of their
strategy by not imposing a hierarchical nested relation between
scales. As an example, by removing one region existent in
a previous scale, the subsequent one may correct internal
inaccurate borders by inducing a novel competition for the
newly “orphan” elements. For hierarchical approaches, how-
ever, the existence of incorrect delineations is perpetuated or
even aggravated as the hierarchy is being built [7], since their
single region-operation is either merging or splitting regions.
The latter occurs independently whether is a top-down or
bottom-up approach. Furthermore, if no node presents accurate
object delineation within a hierarchy, generating an output that
maximizes delineation is challenging.

For a given non-hierarchical multiscale in which violations
exist, it may be possible to extract information so that the
objective is easily achievable. As an example, if there is
a causality violation, one may order the series so that the
quantity of regions is strictly monotonically decreasing. In
contrast, for locality violations, one must evaluate their mag-
nitude since they may be dismissed in non-crucial regions for
solving a problem, especially when state-of-the-art delineation
performance is achieved in such segmentation. If one aims to
<figure><img src="image_2.png" /><figcaption>Fig. 1. Different multiscale segmentation outputs (borders depicted in cyan) of an image of a helminth egg. Images were cropped for visualization purposes.</figcaption></figure>

hierarchically segment an object, it suffices to guarantee that
object regions present a nested behavior in between partitions,
implying that hierarchical background segmentation, although
existent, may not be necessary. Consequently, one may exploit
hierarchical properties for optimization and simplification of
segmentation tasks in regions crucial for the user. If a measure
determines the resemblance of a non-hierarchical multiscale
segmentation resembles to a hierarchical one, one could relax
several hierarchical definitions and exploit, up to some extent,
hierarchical properties if such ratio is significantly low.

Although one may analyze the nested behavior between
sequential partitions to verify whether a given multiscale
segmentation is hierarchical or not, such binary measure does
not provide insights into whether the given multiscale is “al-
most” a hierarchy (i.e. slight or severe violations). Even using
hierarchical structures, violations may occur when defining
objects [8]. Also, if one considers the possibility of adding,
removing, or reordering scales, such problem becomes com-
binatorial. The latter stays unchanged even when considering
only two subsequent partitions in the multiscale.

As consequence, and to the best of our knowledge, the
existence of such a measure is unknown. Most of the works
somewhat related require a ground-truth for segmentation
quality assessment [9]–[11], but not for a hierarchiness mea-
surement. Simply put, such proposals do not assist in determin-
ing whether a multiscale segmentation is close to a hierarchy,
but whether a hierarchical segmentation achieves an effective
object delineation. One could recur to our approach and of
others for two, but different analysis. Although one may argue
that, in our approach, the next scale is the contour ground-truth
of its predecessor, we consider all borders equally relevant,
differing from [12], which weights differently based on the
object’s contours. Consequently, the study of strategies for
transforming a multiscale segmentation into a hierarchical one
are hampered by such challenge.

In this work, we characterize eight different modifications
a region may present when considering two subsequent parti-
tions: (i) full inflation; (ii) full merge; (iii) merge and inflation;
(iv) instability; (v) stability; (vi) full deflation; (vii) full split;

and (viii) deflation and split. From such characterization, we
propose three distinct measures for measuring the degree of
locality violations in a series of partitions: (a) **nestedness**;
(b) **inflation ratio**; and (c) **refinement error**. For evaluating
whether a multiscale segmentation resembles a hierarchy, one
may apply such measures for each pair of subsequential
partitions in the sequence. Using **nestedness**, we estimate
the ratio of nested regions between the segmentations, being
maximum when it is a hierarchy. On the other hand, **inflation
ratio** calculates the ratio of inflation, which leads to locality
violations. Finally, **refinement error** is an error measure that
estimates the cost of “correcting” the precedent scale to be-
come nested in its subsequent one. Experimental results show
that, using the proposed measures, it is possible to verify if a
multiscale segmentation is a hierarchy and, if not, to measure
the degree of locality errors from a local or global perspective,
that is, to provide a deep analysis of the violations in between
partitions in a multiscale segmentation, each measure can be
computed with respect to each region or to the whole partition,
respectively. Finally, from the information computed by each
measure, one can assert the nature of the errors that prevent
it from becoming hierarchical.

This work is organized as follows. Section II presents the
necessary mathematical background for a full understanding of
our proposal, which is presented and detailed in the subsequent
section (i.e., Section III). Using a state-of-the-art multiscale
segmentation algorithm, experimental results are shown and
discussed in Section IV and, finally, we draw some conclusions
and possible future work in Section V.

## II. MATHEMATICAL BACKGROUND

In this section, we recall mathematical definitions based on
the work of [13], [14] necessary for comprehending our work.
Throughout this paper, $\Upsilon$ denotes the universe of elements
(i.e., a set). The size (i.e., number of elements) of $\Upsilon$, for
instance, is here denoted by $|\Upsilon|$. Also, let $\Pi : \Upsilon \mapsto \mathbb{P}(\Upsilon)$,
being $\mathbb{P}$ the power set, be a function which defines all
partitions in $\Upsilon$ such that, $\forall P \in \Pi(\Upsilon), \cup P = \Upsilon$ and $\cap P = \emptyset$.
We term each element of a partition as *blocks* or *regions*. When
<figure><img src="image_3.png" /><figcaption>Fig. 2. Diagram depicting all eight possible cases for building a region $Y_j \in Y$ from the regions of the partition $X$.</figcaption></figure>

each element $u \in \Upsilon$ is, also, a block in a partition $P \in \Pi(\Upsilon)$, then we say that $P$ is the *identity partition*. Conversely, if $P = \{P_1\}$ is composed of a single block $P_1$ in which, $\forall u \in \Upsilon$, $u \in P_1$, then $P$ is said to be the *universal partition*. Finally, given a subset $E \subseteq \Upsilon$, we may term $Q \in \Pi(E)$ and $Q \in \Pi^*(\Upsilon)$ as a *partial partition* of $\Upsilon$, thus, $\Pi^*(\Upsilon)$ is the set of all partial partitions of $\Upsilon$ since it is a partition of $E$ but not necessarily of $\Upsilon$.

We may order the set $\Pi(\Upsilon)$ by *quantity*. Thus, given two partitions $P, Q \in \Pi(\Upsilon)$, we say that $P$ is *bigger* than $Q$ (denoted by $P \supseteq Q$) if, and only if, $|P| \geq |Q|$. Then, in such case, $Q$ is said to be *smaller* than $P$ (denoted by $Q \subsetneq P$). Similarly, it is possible to partially order the set $\Pi(\Upsilon)$ by *refinement* such that, for instance, $P$ is considered *finer* than $Q$ (denoted by $P \preceq Q$) if and only if, for every region $p \in P$, exists a unique $q \in Q$ in which $p \subseteq q$. Thus, $Q$ is said to be *coarser* than $P$ and we write such information by $Q \succeq P$. In this work, we say that $P$ is a *downscale* of $Q$ and, thus, $Q$ is an *upscale* of $P$. One can see that $P \preceq Q$ implies that $P \supseteq Q$, but the converse is not true. As one may note, the task of (hard) segmentation highly correlates with the aforementioned concepts of partition and order relations. For instance, a partition $X \in \Pi(\Upsilon)$ is then referred as a segmentation of $\Upsilon$. Also, for a given series of segmentations $\mathcal{M} = \{S_1, \dots, S_k\}$ — which we usually term as a multiscale or multilevel segmentation — we may order them by their size (i.e., by $\langle \mathcal{M}, \supseteq \rangle$) such that $S_i \supseteq S_{i+1}$ for some $i \in [1, k-1]$ and $S_i \in \Pi(\Upsilon)$. On the other hand, if it is possible to order $\mathcal{M}$ by refinement, thus, by $\langle \mathcal{M}, \preceq \rangle$, then we say that it is a hierarchical segmentation. In both cases, after ordering, we often refer to a segmentation $S_i \in \mathcal{M}$ as a *layer* or *level*, and $S_{i-1}$ and $S_{i+1}$ as the *previous* and *next layer* in $\mathcal{M}$.

### III. HIERARCHINESS

In this section, we will introduce the concepts of *nucleus* and *cover*, which are crucial for identifying the specific case, amongst eight different ones (illustrated by Fig. 2), of a region in a partition $S_{i+1} = Y$ being built by the regions of $S_i = X$, given a multiscale segmentation $\mathcal{M} = \{S_1, \dots, S_k\}$ and $1 \leq$

$i < k \in \mathbb{N}$. Furthermore, with such definitions, we present three different measures for evaluating and analyzing whether $\mathcal{M}$ is close to being a hierarchy.

#### A. Nucleus and Cover

One can perceive the *nucleus* of a coarser region as the group of those blocks at the finer scale totally included in the former (i.e., nested). In contrast, its *cover*, can be seen as the set of regions in the preceding scale necessary for building the coarser block. In this sense, building is the partial or total selection of elements in each region in the cover so that the result is equivalent. Mathematically speaking, we define the *nucleus* and *cover* of a region as follows. Given a multiscale segmentation $\mathcal{M}$ and two subsequent layers $X = \{X_1, \dots, X_r\}$ and $Y = \{Y_1, \dots, Y_c\}$ in $\mathcal{M}$, we define the nucleus $\eta(X, Y_j)$ and the cover $\tilde{\eta}(X, Y_j)$ of a region $Y_j \in Y$ with respect to $X$ as $\eta(X, Y_j) = \{X_i \in X : X_i \subseteq Y_j\}$ and $\tilde{\eta}(X, Y_j) = \{X_i \in X : X_i \supsetneq Y_j\}$, respectively, for $1 \leq i \leq r = |X|$ and $1 \leq j \leq c = |Y|$, in which $X_i \supsetneq Y_j$ indicates that $X$ and $Y$ *overlap* (i.e., $X_i \cap Y_j \neq \emptyset$). When this is not the case, we say that $X_i$ and $Y_j$ are *disjoint*. As one may note, $\cup \eta(X, Y_j) \subseteq Y_j \subseteq \cup \tilde{\eta}(X, Y_j)$ and, consequently, $|\cup \eta(X, Y_j)| \leq |Y_j| \leq |\cup \tilde{\eta}(X, Y_j)|$. Finally, both definitions are also applicable to any region $X_i \in X$ with respect to $Y$.

#### B. Region Cases

From Figure 2, we are able to identify eight possible cases, listed and defined below:

* Full Deflation: $\tilde{\eta}(X, Y_j) = \{X_i\}, \eta(X, Y_j) = \emptyset$ and $\eta(Y, X_i) = \{Y_j\}$;

* Deflation and Split: $\tilde{\eta}(X, Y_j) = \{X_i\}, \eta(X, Y_j) = \emptyset$ and $\cup \eta(Y, X_i) \neq X_i$;

* Full Split: $\tilde{\eta}(X, Y_j) = \{X_i\}, \eta(X, Y_j) = \emptyset$ and $\cup \eta(Y, X_i) = X_i$;

* Stability: $\tilde{\eta}(X, Y_j) = \eta(X, Y_j) = \{X_i\}$;

* Instability: $|\tilde{\eta}(X, Y_j)| > 1$ and $\eta(X, Y_j) = \emptyset$;

* Full Inflation: $|\tilde{\eta}(X, Y_j)| > 1$ and $|\eta(X, Y_j)| = 1$;

* Merge and Inflation: $|\tilde{\eta}(X, Y_j)| > 1$, $|\eta(X, Y_j)| > 1$ and $\cup \eta(X, Y_j) \neq Y_j$; and
<figure><img src="image_4.png" /><figcaption>Fig. 3. Three distinct partitions of a 8 × 8 square universe Υ for illustrating the eight possible cases when evaluating two partitions.</figcaption></figure>

• Full Merge: $|\eta(X, Y_j)| > 1$ and $\cup \eta(X, Y_j) = Y_j$;

We can exemplify each one of the aforementioned cases from the partitions depicted in Figure 3. For instance, while verifying whether B is an upscale of A, we can see that $B_1$ is built through full inflation, since $\eta(A, B_1) = \{A_1\}$. For $B_2$ and $B_3$, one may notice that they are constructed by instability given that both present empty nuclei and more than one element in their cover. In contrast, $B_7$ is equivalent to $A_6$ (i.e., stable). Also, $B_4$ is constructed through full deflation because it has an empty nucleus, $\hat{\eta}(A, B_4) = \{A_4\}$ and that $B_4 \in \eta(B, A_4)$. Like $B_4$, $B_9$ and $B_{10}$ are built through full deflation. Both $B_5$ and $B_6$ are resultant from deflation and split. Finally, we can see that $B_8$ is built from merging and inflation. For illustrating the case of a full merge, one can refer to $A_1, A_2, A_3, A_4$ for building $C_1$, and the converse exemplifies the case of a full split. Thus, when $X \preceq Y$, the sole case possible is the full merge of regions and, clearly, it is analogous for $X \succeq Y$ and full split (e.g., A and C).

### C. Hierarchiness Measures

Based on the previous measures, we can define three distinct measures for evaluating two subsequent partitions X, Y in a multiscale segmentation $\mathcal{M}$. First, we recur to a $r \times c$ matrix $\mathbf{M}(X, Y) = [\mathbf{M}(X, Y)_{ij}]$ in which $r = |X|, c = |Y|$, and each element is defined by $\mathbf{M}(X, Y)_{ij} = |X_i \cap Y_j|$, given $X_i \in X$ and $Y_j \in Y$. Also, we may normalize each element by $|\Upsilon|$ thus resulting in the matrix $\mathbf{M}_{\Upsilon}(X, Y)$ whose elements are $\mathbf{M}_{\Upsilon}(X, Y)_{ij} = |X_i \cap Y_j|/|\Upsilon|$. Similarly, the elements of the matrix $\mathbf{M}_{\Upsilon}(X, Y)$ are defined as $\mathbf{M}_{\Upsilon}(X, Y)_{ij} = |X_i \cap Y_j|/|Y_j|$, and it is analogous for $\mathbf{M}_{\mathcal{X}}(X, Y)$.

Given two regions $X_i \in X$ and $Y_j \in Y$, we may quantify the property of $X \in \eta(X, Y_j)$ through the nestedness measure $\mathbf{NE}(X_i, Y_j) \in \{0, 1\}$ defined by $\mathbf{NE}(X_i, Y_j) = 1(X_i \subseteq Y_j)$ or, equivalently, by $\mathbf{NE}(X_i, Y_j) = 1(\mathbf{M}_{\mathcal{X}}(X, Y)_{ij} = 1)$, in which **1** is an indicator function that outputs “0” or “1” if the input boolean expression is false or true, respectively. The inflation ratio $\mathbf{IR}(X_i, Y_j) \in \{0, 1\}$ evaluates whether any inflation has through $\mathbf{IR}(X_i, Y_j) = 1(X_i \in \hat{\eta}(X, Y_j) \setminus \eta(X, Y_j))$, which can be computed by $\mathbf{IR}(X_i, Y_j) = 1(0 < \mathbf{M}_{\mathcal{X}}(X, Y)_{ij} < 1 \wedge 0 < \mathbf{M}_{\mathcal{Y}}(X, Y)_{ij} < 1)$, considering $\wedge$ the logical operator AND. In contrast and inspired from [15], the refinement error $\mathbf{RE}(X_i, Y_j) \in [0, 1]$ can be defined by $\mathbf{RE}(X_i, Y_j) = \min \{|X_i \cap Y_j|, |X_i \setminus Y_j|\} / |X_i|$ and quantify the lowest “effort” to make $X_i \subseteq Y_j$. We can compute it, deriving from the latter equation, through $\mathbf{RE}(X_i, Y_j) = \min \{\mathbf{M}_{\mathcal{X}}(X, Y)_{ij}, 1 - \mathbf{M}_{\mathcal{X}}(X, Y)_{ij}\}$ but

imposing a harsher penalization by calculating it as $\mathbf{RE}(X_i, Y_j) = \min \{1, (1 - \mathbf{M}_{\mathcal{X}}(X, Y)_{ij}) / \mathbf{M}_{\mathcal{X}}(X, Y)_{ij}\}$.

For two segmentations $X, Y \in \mathcal{M}$ of a given image containing $|\Upsilon|$ pixels, the effort to compute $\mathbf{M}(X, Y)$ and any presented measure is $O(|\Upsilon|^2)$ and $O(|X||Y|)$, respectively. Also, one can compute each measure for $Y_j$ with respect to all partitions in X. For instance, $\mathbf{NE}(X, Y_j) = \sum_{i=1}^{r} \mathbf{NE}(X_i, Y_j) \mathbf{M}_{\mathcal{Y}}(X, Y)_{ij}$, resulting in a normalized measure (with respect to $Y_j$). Similarly, it is possible to evaluate the $\mathbf{NE}(X, Y)$ between both partitions X and Y through $\mathbf{NE}(X, Y) = \sum_{i=1}^{r} \sum_{j=1}^{c} \mathbf{NE}(X_i, Y_j) \mathbf{M}_{\mathcal{Y}}(X, Y)_{ij}$. As one may note, the aforementioned possibilities are also valid for **IR**, and **RE**.

When evaluating $X, Y \in \mathcal{M}$, if $X \preceq Y$, it is clear to see that $\mathbf{NE}(X, Y) = 1$, and $\mathbf{IR}(X, Y) = \mathbf{RE}(X, Y) = 0$. Conversely, if $X \succeq Y$, we have that $\mathbf{NE}(X, Y) = \mathbf{IR}(X, Y) = \mathbf{RE} = 0$. From Figure 3 and using $B_8$ as an example of merge and inflation, we have that $\mathbf{NE}(A, B_8) = 0.5$, $\mathbf{IR}(A, B_8) = 0.5$, and $\mathbf{RE}(A, B_8) = 0.5$, indicating that 50% of $B_8$ was built from inflation and 50% from merging. The refinement error indicates that 50% of $B_8$ present multiple region overlap. In contrast, for $C_1$, which is built solely from full merge, $\mathbf{NE}(A, C_1) = 1$, $\mathbf{IR}(A, C_1) = 0$, and $\mathbf{RE}(A, C_1) = 0$.

## IV. EXPERIMENTAL RESULTS

In this section, we provide the experimental setup and we analyze and discuss our findings. We chose two medical image datasets, named *Liver* [16] and *Parasites* [17], whose objects (i.e., human liver and intestinal parasite eggs) present smooth borders and impose a challenge in terms of delineation. Also, the object and background stability allows a more confident analysis, differently from natural image datasets in which both vary significantly. Since we propose non-optimized measures, we used all images in the dataset in the experiments. Also, in order to properly assess our proposed measures considering different multiscale segmentations (from different approaches), we selected four methods: (i) Voronoi; (ii) SICLE-COMP [5]; (iii) SICLE-IRREG [5]; and (iv) SH [18]. We use Voronoi as a representative of a method that minimizes nestedness between segmentations. For that, we generate random seeds and partition the image by minimizing the spatial distance to a seed. In contrast, Superpixel Hierarchy (SH) is a hierarchical approach and, thus, provides insight into hierarchical multiscale segmentation. Finally, SICLE-COMP and SICLE-IRREG are variants of a state-of-the-art method in superpixel segmentation named *Superpixels through Iterative CLEarcutting* (SICLE), which provides a non-hierarchical multiscale segmentation on-the-fly. The motivation relies on the resemblance of a hierarchical segmentation output, although such a condition is not assured. Finally, for all methods, we generated 750, 500, 250, and 100 regions in each segmentation and we analyzed, from finer to coarser, the following pairs of partitions: (a) (750, 500); (b) (500, 250); and (c) (250, 100). A demonstration code is
<figure><img src="image_5.png" /><figcaption>Fig. 4. Experimental results of the proposed measures on Liver and Parasites datasets (resp. left and right columns), whose average is depicted as a diamond.</figcaption></figure>

publicly available*<fnref n="1" />.

## A. Quantitative Analysis

Figure 4 presents the average results of each method in Liver and Parasites datasets. It is clear to see that SH, a hierarchical method, achieves the expected behavior for all measures: maximum for nestedness and minimum for inflation ratio and refinement error. Likewise, Voronoi, due to its unstable partitioning strategy, undermines nesting regions which explains its almost zero nestedness and quasi-maximum inflation ratio. In terms of refinement error, we argue that the Voronoi results are high due to the significant impact that random sampling imposes on the closest points to a seed. When considering 750 → 500, the competition for conquering pixels is near the seed, implying that slight changes in the seed coordinates severely affect the region, being necessary to substantially be reshaped for being nested in some other region in the following segmentation. However, as the number of regions decreases, the competition is farther from the seed, limiting such impact mostly on the region's borders, which demands fewer modifications.

When analyzing the results from SICLE variants, one may note that the behavior is similar between datasets. It is interesting to notice that SICLE-COMP, which aims for compact regions, achieves higher nestedness and lower inflation ratio than its irregular counterpart. We infer that, by imposing a

spatial regularity factor, regions tend to present similar shapes and be less impacted by the removal of regions far from them.

Conversely, slight modifications in the competition may alter drastically the regions' shape when the goal is irregularity. Consequently, although both rarely promote merging behavior, the latter favors inflation whereas the former favors stability. The same argument goes for the refinement error. That is, by favoring stability, SICLE-COMP achieves lower errors with less variation than SICLE-IRREG, whose slightly higher results, but with higher variation, are a result of promoting inflation.

## B. Qualitative Analysis

As one may note in Figs. 5(c-a), several regions in SICLE-COMP remained unaltered from one scale to the subsequent, achieving $NE(C_{500}, C_{250}) = 71\%$, $IR(C_{500}, C_{250}) = 30\%$, and $RE(C_{500}, C_{250}) = 14\%$, when considering $C_{500}$ and $C_{250}$. However, as the number of regions decreases, regions tend to be closer to one another and, thus, removing one or more nearby regions may destabilize the ones left out. As an example, for $C_{250}$ and $C_{100}$, we have that $NE(C_{250}, C_{100}) = 36\%$, $IR(C_{250}, C_{100}) = 64\%$, and $RE(C_{250}, C_{100}) = 27\%$.

On the other hand, seeing the finer segmentation from SICLE-IRREG in Figure 5(f-d), even when removed regions are far from those left out, it may affect local tie-zones which, for a function that maximizes irregularity, can significantly alter the regions' shape in between partitions. Consequently,

<footnote n="1">¹* https://github.com/IMScience-PPGINF-PucMinas/hierarchiness.git</footnote>
<figure><img src="image_6.png" /><figcaption>Fig. 5. Pseudocolored segmentations using SICLE-COMP and SICLE-IRREG, respectively, identified by $C_n$ and $I_n$, for $n \in \{100, 250, 500\}$ regions.</figcaption></figure>

for $I_{500}$ and $I_{250}$, we have that $NE(I_{500}, I_{250}) = 16\%$, $IR(I_{500}, I_{250}) = 83\%$, and $RE(I_{500}, I_{250}) = 34\%$. In contrast, when considering coarser scales, the amount of tie-zones is significantly diminished, leading to more nested regions (i.e., unaltered) and less inflation and locality errors, specifically, for $I_{250}$ and $I_{100}$, $NE(I_{250}, I_{100}) = 33\%$, $IR(I_{250}, I_{100}) = 67\%$, and $RE(I_{250}, I_{100}) = 18\%$.

## V. CONCLUSION AND FUTURE WORK

In this paper, we analyze the “hierarchiness” between two partitions in a multiscale segmentation and, by defining eight possible situations, we propose three different measures for assisting in the estimation of how far a multiscale segmentation resembles a hierarchy. Experimental results show that our proposals are consistent and offer a wide and complementary overview on each of the four algorithms considered. For future work, we aim not only to study and propose new measures but, also, to conceive new approaches for measuring the segmentation series integrally, alongside strategies for maximizing the hierarchiness of any multiscale segmentation. The latter may allow optimization solutions of partition-related problems, as in [19], [20].

## ACKNOWLEDGMENT

The authors thank PUC Minas, CAPES (Grant PROAP 88887.842889/2023-00 – PUC/MG, Grant STIC-AMSUD 88887.878869/2023-00, Grant PDPG 88887.708960/2022-00 – PUC/MG - Informática, and Finance Code 001), CNPq (Grants 407242/2021-0, 306573/2022-9, 442950/2023-3 and 304711/2023-3), FAPEMIG (Grant APQ-01079-23, Grant APQ-05058-23 and PCE-00417-24) and FAPESP (Grants 2023/14427-8 and 2013/07375-0).

## REFERENCES

[1] Y. Lv, N. Han, and H. Du, "Estimation of bamboo forest aboveground carbon using the rglm model based on object-based multiscale segmentation of spot-6 imagery," *Remote Sensing*, vol. 15, no. 10, 2023.

[2] A. E. Ilesanmi, O. P. Idowu, and S. S. Makhanov, "Multiscale superpixel method for segmentation of breast ultrasound," *Computers in Biology and Medicine*, vol. 125, p. 103879, 2020.

[3] F. L. Galvão, S. J. F. Guimarães, and A. X. Falcão, "Image segmentation using dense and sparse hierarchies of superpixels," *Pattern Recognition*, vol. 108, p. 107532, 2020.

[4] P. F. Felzenszwalb and D. P. Huttenlocher, "Efficient graph-based image segmentation," *International Journal of Computer Vision*, vol. 59, no. 2, pp. 167–181, 2004.

[5] F. C. Belém, I. B. Barcelos, L. M. João, B. Perret, J. Cousty, S. J. F. Guimarães, and A. X. Falcão, "Novel arc-cost functions and seed relevance estimations for compact and accurate superpixels," *Journal of Mathematical Imaging and Vision*, vol. 65, no. 5, pp. 770–786, 2023.

[6] S. Guimarães, Y. Kenmochi, J. Cousty, Z. Patrocinio, and L. Najman, "Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity," *Mathematical Morphology - Theory and Applications*, vol. 2, no. 1, pp. 55–75, 2017.

[7] F. C. Belém, S. J. F. Guimarães, and A. X. Falcão, "Superpixel segmentation using dynamic and iterative spanning forest," *IEEE Signal Processing Letters*, vol. 27, pp. 1440–1444, 2020.

[8] N. Passat, B. Naegel, F. Rousseau, M. Koob, and J.-L. Dietemann, "Interactive segmentation based on component-trees," *Pattern Recognition*, vol. 44, no. 10, pp. 2539–2554, 2011, semi-Supervised Learning for Visual Content Analysis and Understanding.

[9] J. Pont-Tuset and F. Marqués, "Supervised evaluation of image segmentation and object proposal techniques," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 38, pp. 1–1, 09 2015.

[10] S. Todorovic and M. Nechyba, "Dynamic trees for unsupervised segmentation and matching of image regions," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 27, no. 11, pp. 1762–1777, 2005.

[11] Z. Wu, L. He, Z. Hu, Y. Zhang, and G. Wu, "Hierarchical segmentation evaluation of region-based image hierarchy," *IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing*, vol. 12, no. 8, pp. 2718–2727, 2019.

[12] J. Pont-Tuset and F. Marques, "Supervised evaluation of image segmentation and object proposal techniques," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 38, no. 7, pp. 1465–1478, 2016.

[13] J. Serra, "Grain building ordering," in *Mathematical Morphology and Its Applications to Image and Signal Processing*, P. Soille, M. Pesaresi, and G. K. Ouzounis, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 37–48.

[14] C. Ronse, "Orders on partial partitions and maximal partitioning of sets," in *Mathematical Morphology and Its Applications to Image and Signal Processing*, P. Soille, M. Pesaresi, and G. K. Ouzounis, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 49–60.

[15] P. Neubert and P. Protzel, "Superpixel benchmark and comparison," in *Forum Bildverarbeitung*, vol. 6, 2012, pp. 1–12.

[16] J. E. Vargas-Muñoz, A. S. Chowdhury, E. B. Alexandre, F. L. Galvão, P. A. Vechiatto Miranda, and A. X. Falcão, "An iterative spanning forest framework for superpixel segmentation," *IEEE Transactions on Image Processing*, vol. 28, no. 7, pp. 3477–3489, 2019.

[17] F. Belém, S. J. F. Guimarães, and A. X. Falcão, "Superpixel segmentation by object-based iterative spanning forest," in *Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications*, R. Vera-Rodriguez, J. Fierrez, and A. Morales, Eds. Cham: Springer International Publishing, 2019, pp. 334–341.

[18] X. Wei, Q. Yang, Y. Gong, M.-H. Yang, and N. Ahuja, "Superpixel hierarchy," *IEEE Transactions on Image Processing*, vol. PP, 05 2016.

[19] B. Ravi Kiran and J. Serra, "Global-local optimizations by hierarchical cuts and climbing energies," *Pattern Recognition*, vol. 47, no. 1, pp. 12–24, 2014.

[20] L. Guigues, J. P. Cocquerez, and H. Le Men, "Scale-sets image analysis," *International Journal of Computer Vision*, vol. 68, no. 3, pp. 289–317, 2006.