Hierarchy-Agnostic Unsupervised Segmentation: Parsing Semantic Image Structure
Authors: Simone Rossetti
fiora pirri
Venue: NeurIPS 2024 poster (2024)
Keywords: Unsupervised Hierarchical Segmentation
Spectral Clustering
Self-Supervised Feature Extraction
Semantic Region Tree
Primary area: machine_vision
TL;DR: Our method creates a hierarchy-agnostic semantic region tree from image pixels, offering nuanced segmentation without predefined hierarchies, scaling effectively across datasets.

Abstract: Unsupervised semantic segmentation aims to discover groupings within images, capturing objects' view-invariance without external supervision. Moreover, this task is inherently ambiguous due to the varying levels of semantic granularity. Existing methods often bypass this ambiguity using dataset-specific priors. In our research, we address this ambiguity head-on and provide a universal tool for pixel-level semantic parsing of images guided by the latent representations encoded in self-supervised models. 
We introduce a novel algebraic approach that recursively decomposes an image into nested subgraphs, dynamically estimating their count and ensuring clear separation.
The innovative approach identifies scene-specific primitives and constructs a hierarchy-agnostic tree of semantic regions from the image pixels. 
The model captures fine and coarse semantic details, producing a nuanced and unbiased segmentation. 
We present a new metric for estimating the quality of the semantic segmentation of discovered elements on different levels of the hierarchy. The metric validates the intrinsic nature of the compositional relations among parts, objects, and scenes in a hierarchy-agnostic domain. Our results prove the power of this methodology, uncovering semantic regions without prior definitions and scaling effectively across various datasets. This robust framework for unsupervised image segmentation proves more accurate semantic hierarchical relationships between scene elements than traditional algorithms. The experiments underscore its potential for broad applicability in image analysis tasks, showcasing its ability to deliver a detailed and unbiased segmentation that surpasses existing unsupervised methods.

Hierarchy-Agnostic Unsupervised Segmentation: Parsing Semantic Image Structure
Simone Rossetti 1.2
Fiora Pirri
DIAG, Sapienza University of Rome *DeepPlants (rossetti, prossetti,pirriieeee uniroma1. it (simone, fforaa @deepppaasssssssss...
Abstract
Unsupervised semantic segmentation aims to discover groupings within images, capturing objects' view-invariance without external supervision. Moreover, this task inherently ambiguous due the varying levels of semantic granularity. Existing methods often bypass this ambiguity using dataset-specific priors. In our research, we address this ambiguity head-on and provide universal tool for pixel- level semantic parsing of images guided by the latent representations encoded in self-supervised models. We introduce novel algebraic approach that recursively decomposes an image into nested subgraphs, dynamically estimating their count and ensuring clear separation. The innovative approach identifies scene-specific primitives and constructs hierarchy-agnoste tree of semantic regions from the image pixels. The model captures fine and coarse semantic details, producing a nuanced and unbiased segmentation. We present a new metric for estimating the quality the semantic segmentation of discovered elements on different levels of the hierarchy. The metric validates the intrinsic nature of the compositional relations among parts, objects, and scenes a results prove the power of this methodology, uncovering semantic regions with- out prior definitions and scaling effectively across various datasets. This robust framework for unsupervised image segmentation proves more accurate seman- tic hierarchical relationships between scene elements than traditional algorithms. The experiments underscore its potential for broad applicability in image analysis tasks, showcasing its ability to deliver a detailed and unbiased segmentation that surpasses existing unsupervised methods.
domain. Our
Introduction
The advancement of image segmentation has recently taken significant steps forward. On the one hand, the foundation models are trained on increasingly large datasets, such as CLIPseg [57] (CLIP [67]), SAM [48], and SEEM [97], supervised by text and human prompts [92]. On the other hand, there is a rising growth unsupervised segmentation models. Unsupervised segmentation ex- plores the feature hierarchy by leveraging supe-supe contrastive learning, in SmooSeg [51], U2Seg [62]. CUTLer [87], CuVLER [5], STEGO [32], ACSeg[52], FreeSolo [85], HSG [44], Trans- Fgu [90], DeepCut [3], and others [77, 58, 96, 86, 33, 17]. Unsupervised models discover and lo- calize image categories with no annotation aid and evaluate the quality of the pseudo-masks they predict the datasets corpora used for testing, such COCO-Stuff [10] and Cityscapes [21]. De- spite exploring human perception more closely than the foundation models, they still rely on the linguistic and conceptual relations between the images and their annotations.
Curated datasets, such as ImageNet [50], PascalVOC [27], or MSCOCO [53], show an extraordinary number of objects with all their components and particulars not annotated either at the image level
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Input image
Superpisels
Output semmnclc regions free
sulteccss
partiisoning
Hlune
clestering
upper body
lower bocy
Eace
kggs
chest
Figure 1: Hierarchy-agnosten unsupervised segmentation. Finer image parts are generated via over-clustering, each region colour-coded randomly. Our algorithm recursively partitions these parts, grouping them into coarser regions across multiple levels of granularity. The resulting tree represents an unsupervised hierarchical semantic segmentation. The arrangement regions in the tree reflects their semantic distance, which is colour-coded in the heat map shown the right.
or densely. Why annotate this and not that? Annotation prejudice creates a bias towards subset of the scene. Unsupervised learning, in contrast, has the potential to generate richer representations that are not restrained by annotation decisions. Without juggling annotations, unsupervised features (e.g. [64]) nearly mirror visual perception discovering scene parts and details; indeed, feature cues live in nested context levels and are not necessarily verbalisable [76, 66]. as opposed to the Gestalt holistic view [83].
Following previous research [44, 19, 3, 94], our key idea is that the natural hierarchical structure of visual scenes is an essential attribute that we can actively pursue in unsupervised segmentation. We approach unsupervised semantic segmentation as an unsupervised pixel-wise feature learning problem, discretising the hierarchical semantic knowledge yielded by self-supervised learning. Our approach makes no assumption about the number of semantic granularity levels and the number of partitions in each level in [44]. We generate robust hierarchical segmentation for every image, solely relying on hicrarchical clustering in feature space, see Figure 1. This new method achieves unsupervised segmentation by leveraging relationships between concepts hidden in the latent space of self-sur self-supervised models, across multiple levels of semantic granularity.
We propose simple algebraic methodology based on vast literature [20, 6, 61, 81, 75, 91], that unsupervisedly segments the scene parts. The method guarantees the construction of natural, scene- dependent classes of primitives [55], which can be easily used in unsupervised segmentation without surrendering to their a priori definitions. Our contributions are:
1. We introduce a deep recursive spectral clustering that maximises an unbiased semantic simi- larity measure at multiple granularity levels. Exposing our method any generic group of images, we show that it results in hierarchical unsupervised semantic segmentation.
2. We introduce new metrics for estimating the quality of the semantic segmentation of the ele- ments discovered on the different levels of the hierarchy, called Normalised Multigranular Covering (NMCovering) and Normalised Hierarchical Covering (NHCovering).
3. We integrate the method into various self-supervised learning models to enhance its flexi- bility for benchmarking purposes, making it suitable as downstream task through unsupervised segmentation by inferring all scene parts the images of any given dataset.
Related works
Self-supervised representation learning for unsupervised segmentation. Self-supervised learn- ing (SSL) about learning representations of woal-wordd data without human supervision [14, 36, 11,

---

64]. Contrastive learning (CL) [18, 63] is the most prominent method in SSL, maximising feature similarities between an image and its affine transformations while minimising similarity between randomly sampled images. Most unsupervised segmentation methods use learning representations to feed self-supervised features to graphs for clustering [58, 88, 87, 3]. Alternatively, features are used for building distillation strategies [32, 96, 51], or for designing inductive priors forcing some consistency property [51, 17, 73J. SSL representations implicitly define a distance metric in the latent space, though learning a metric space is not their primary objective.
Unsupervised semantic segmentation. Unsupervised semantic segmentation labels pixels that be- long to specific elements in the scene, grouping all objects of the same semantic type under a single label, without supervision.
The earlier approaches, such as [41, 47, 17, 86, 77, 33] had not yet available powerful SSL features like [11], though used CL. principles. PiCie [17] used equivariance to transformations; IIC [41] resorted to invariant information clustering, maximising mutual information, to find commonality
in objects, and analogously did InfoSeg [33]. CLD [86] integrated local clustering into contrastive learning; [77] used saliency to find the image foreground and guide CL of pixel embedding.
The availability of high-level unsupervised features triggered new strategies. DINO self distilla- tion [11] inspired both STEGO [32] and SmooSeg [51]. STEGO trains segmentation head by dis- tilling the feature correspondences to form compact clusters. SmooSeg uses the smooth prior over semantically coherent regions supervision cue to generate semantic maps. However, many meth- ods suffer from the background problem and elaborate on DINO's s attention to obtaining foreground objects, such as FreeSolo [85] and [93]. Also, TransFGU [90] focuses on a top-down object-centric approach to generate pixel pseudo labels according to GradCAM [72]. Spectral clustering, as intro- duced to machine learning by [74], is considered in [88, 58, 87, 52, 68]. In particular, CutLER [87] applies NCut [74] iteratively to a masked similarity matrix to discover foreground elements of the scene. ACSeg [52] uses the affinity matrix discover concept similarities. SemPart [68] considers the foreground a single object saliency mask and applies graph regularisation. In [73], patch-level contrasting learning leverages global hidden positives learn semantic consistency.
As grouping is the common denominator, all the mentioned methods suffer from deciding the correct level of granularity. Some methods resort to an object- centric bias, such as [77, 93], CAMs [90], hinting self-attention [96, 791, fixed-size flat image partitioning [58]. Others, such as [96], and [46, 73], resort scene-centric prior assumption.
Unsupervised parts discovering. Despite hierarchically discovering parts has a long history in computer vision, it has only recently recovered and connected to unsupervised part segmentation. The first input came from [31], analysing the hierarchical nature of deep learning features. One of the first approaches was SCOPS [39] using dense self-supervised contrastive loss to discover fore- ground parts of single objects. In [94]. the authors introduce self-supervised primitive hierarchical grouping. They leverage a boundary strength map (OWT-UCM [4]) on relatively few images to leamn from a large data set. The approach formulates an ultrametric map defining a region hier- archy. Similarly, HSG [44] leverages region boundaries to obtain multi-level segmentation. HSG is unsupervisedly trained from scratch, performing pixel grouping with dense contrastive learning across different granularity levels. [19], K fixed parts are discovered via an average part deserip- tor and by forcing consistency using the equivariance of affine and photometric transformations. Leopart [96] follows DINO self-distillation to classify pixels, obtaining detailed scene parts, fur- ther clustered via community detection. Finally, DeepCut [3] approaches unsupervised semantic part segmentation using both spectral clustering with NCut and GNN convolution, constructing a patch-wise correlation [7] matrix from DINO features.
3 Method
We present flexible, unsupervised method for segmenting natural images, automatically creating data structures that organize pixels by their semantic coherence across multiple levels of detail with- out relying predefined hierarchies or labels. This method is designed to segment images from coarse regions to finer parts, providing an intuitive representation of visual content; see Figure 1.
For instance, consider an urban street view. At high level, it consists of elements such the sky, a road, buildings, and vehicles. Among the vehicles, there might be bus or a car, which can be further decomposed into parts like the body shell, wheels, and other visible components.
3

---

Our approach segments an image I E 3 with each pixel in the image assigned to leaf node. Our model is function f I + T. represented by deep neural network, which maps an image to its semantic regions. Notably, this is achieved in fully unsupervised manner; we incorporate mechanisms that guide f to produce a meaningful decomposition of the image, even without labelled examples.
MxN into eecerarchy-agnosiie tree T of semantic regions,
3.1 Overview of the Approach
Our method discovers similar parts in an image by recursively partitioning a graph constructed from deep feature representations of the image. The key idea is to treat self-supervised models for image processing as codebooks of lower-dimensional space, with the extracted feature vectors acting as codes that embed semantics of visual concepts.
The primary cue for discovering parts is deep feature extractor é. neural network pre-trained without supervision on a standard benchmark such as ImageNet. We observe that the alignment of codes leads to semantic similarity across multiple levels of granularity. A higher degree of alignment indicates semantic similarity at finer granularity levels, corresponding to indivisible object parts or primitives. Conversely, a lower degree of alignment reflects semantic similarity at coarser granular- ity levels. By discretizing the density of these alignments, we can discover scene and object parts at various levels of detail.
Let 0 = o (T),, E Idd be the code associated with pixel location i in the image. If pixel j belongs to the same finer part i, their codes should be similar. Conversely, if they belong to different parts, their codes will diverge. We expect this property to be consistent in each image / and should not be affected by the particular object instances.
straightforward approach might to cluster these codes using algorithms that minimize a distor- tion metric in the latent space to identify regions of high feature concentration. However, critical flaw that can arise when using these methods in sigh-dmmensional space is the presence of many local minima in the cost function. This would require multiple restarts of the iterative algorithms to find a suitable solution, which is impractical due to high complexity. To overcome these limita- tions, adopt efficient method to partition the image into similar regions, avoiding the pitfalls of multiple local minima and the need for iterative restarts in high-dimensional space.
Graph construction. We represent the image as a weighted undirected graph G = (V, E, w), where V = {2,)/= and n M NN. The weight assigned to each edge (i, E E is defined by scaled and shifted cosine similarity between fcature vectors Wiy = w(U, 0ÿ) E [0. 1]. These weights
form the adjacency matrix W [wr;g] E [0, 1]mx,, the degree matrix D diag [d.] R where
d; - -, Wij and the normalized graph Laplacian
1-2
1/2 (D W) D [59].
We interpret the edge weights as indicators of the semantic granularity between nodes. Specifically, why >> 1, pixels i and j likely belong to the same fine- ane-grained part (primitive). Conversely, if Wy + 0, these pixels are likely to belong to entirely different parts, indicating minimal semantic similarity even at the coarsest level of granularity.
Similarity perturbation. In an ideal scenario, at a specific granularity level, k distinct connected components emerge in G, resulting in a binary adjacency matrix W" E {0, 1]nxa with k' non-zero diagonal blocks- - indicating strong intra-component connectivity and no inter-component connec- tions and normalized Laplacian L/. However, in practice, the observed adjacency matrix is not discrete. Instead, W cxhibits tightly connected components alongside others with lower connectiv- ity, resulting in perturbed normalized graph Laplacian L. We regard the primitives of the model as affected by a small symmetric perturbation H E =x* incorporating contextual information from coarser levels of semantic granularity, i.c. L = L' + H. making the observed adjacency real-valued.
Fortunately, the Davis-Kahan symmetric sin 0 theorem [23, 91] helps us manage perturbations; see also Appendix A. If the eigenvalues of L exhibit spectral gap 6, the corresponding eigenspaces of and L.' remain close despite the perturbation H. The theorem quantifies this proximity by relating the angle 0 between the eigenspaces of I, and L/' where sin 0 is proportional to the norm of H and inversely proportional to 6. By selecting the largest gap, we isolate the part of the spectrum closest to the original graph, guessing the true semantic structure at the specific granularity level.

---

Normalized smoothness measure. We consider a function g V + RR that assigns value g each node U; V. Since = n, we identify the function 9 with a vector in R.. Based on the considerations from [74, 8] (see also Appendix C), we define the normalized smoothness measure of g on the graph G using the functional Sg
TR + R+ induced by I. through the form:
Se(g) 9 (D- W)g Ei,(o(e,) g(mz))
(1)
g Dg
E.
We observe that minimizing the functional yields normalized smoothest functions that assign similar values to tightly connected nodes and different values to weakly connected ones while accounting for their importance in the graph - avoiding trivial solutions for low connectivity nodes. Therefore, if g is both normalized and smooth with respect to G, then ((x) is similar to g(by) whenever v, is similar to V where similarity is quantified by the weight Way and adjusted by the node degree d.
Given these properties, we treat any function y continuous partition function on the graph G and evaluate its correctness by a feature density change criterion on the data partition, which measures variations in similarity across different regions of the graph.
Recursive partitioning with perturbation stability. We propose recursive partitioning strategy for discovering semantic parts by progressively dividing the graph. starting from the whole and refining it into tightly connected subgraphs. At each recursion level, we examine the subgraph's ' granularity, identify perturbations - contextual variations affecting node connections - and derive the unperturbed adjacency matrix to reveal finer semantic components. By capturing relationships at multiple levels of detail, this approach yields more nuanced segmentation than methods that partition the entire graph's 's nodes into fixed number & of sets.
We aim to find the smoothest normalized functions that best describe the semantic structure of subgraph G at a specific granularity." We tackle the minimization of Equation (1) as a standard eigenvalue problem [74] using the Rayleigh-Rize quotient form. This yields the orthonormal eigen- vectors ys corresponding to the smallest eigenvalues X of L, as guaranteed by the Courant-Fischer theorem:
y: = argmin |1,9 1 vey y/ Ly. with you = D2/21 IR..
The eigenvalues X the values the right-hand side of the problem above with 0 Ào A1 S... S A S 2. quantify the normalized smoothness of the functions y,. Since solving the eigenvalue problem has a computational complexity of O(z"), in practice, we limit the computation to the kmnz smallest eigenvalues for efficiency. We obtain the spectral gaps 6y = > - - > 0 for 2 S j S kmazz 1 and seek for the k-th gap giving the tighter sin 0 bound, i.e. k = arg max, 55-
We select up to k smoothest normalized functions on G, namely the first k eigenvectors of L, y1...., 1 we ignore yo since it is constant. These k eigenvectors provide orthogonal graph signals based on semantic coherence, with nodes showing similar values in these functions likely belonging to the same semantic part; thus, each signal points to distinct connected component.
As in [61], we recover the true semantic structure of the graph considering the matrix Y [31, ......, 11-1] E pa First, we perform fz-oomalizaaiion of each row in Y. Xt = Y2, Y2) Raxk-1 - the i-th row of X represents the normalized feature vector for the i-th node, which determines the node's membership in cluster. Then, we take the best membership for each node- - using an algorithm that attempts to minimize distortion in lower-dimensional space - finding & disjoint partitions of the nodes V1, Vz,..., V& such that Uk_ V2 = V and n V, = Q.
We determine L' and estimate the perturbation H/ = L- L' compute the sin O upper bound value.
Each recursion step splits the graph into tighter subgraphs. This process continues until one of the early stopping criteria is met: (1) if partition is too small (less than kmin), (2) if the eigenvalues exceed a maximum smoothness threshold Amaz, or (3) if the sin 0 upper bound value becomes too large (more than Pmex), indicating that the current estimate of L' is no longer reliable. These stopping conditions ensure we halt when further partitioning does not yield meaningful semantic components, thus identifying the final set of image parts or primitives.
We generalize G and L to denote any subgraph and its Laplacian, rather than just the original image graph.
5

---

lxpa
Henrdia
Careanne
lepar
Huzzchio
Cataamo
Arnokations
Irea
Hendho
Canaarice
Qualitative results of our algorithm PascalVOC2012, COCO-Stuff and Cityscapes datasets. The Hierarchy columns colour-code the pixel semantic hierarchy, and the Category columns are random colour-coded, helping visually discriminate hierarchically close pixels.
Figure 2:
Each recursive partitioning adds structure to the tree T, where nodes specify semantic regions at various levels. The final output is T, with each leaf node capturing distinct part of the image an appropriate level of granularity; see Figure 2.
The values kmin, Amaz and Pmer found experimentally for the tested dataset; tables shown in Section 4 and Appendix D. In Appendix B, we discuss the algorithm's 's properties and the generated T, and present the complete pseudocode of our method.
3.2 Pre and Post-Processing
Boosting computation. We introduce a preprocessing strategy that condenses the graph, dramati- cally reducing the algorithm's 's time and memory requirements by several orders of magnitude while maintaining comparable accuracy. The condensed graph simplifies the original graph into m nodes by contracting strongly connected components into vertices, where <
We assume that the finest semantic content in natural images inherently limited and cannot exceed the raw pixel statistics. From the input image 7 we extract regions [2, 69, 74] leading to initial undirected condensed graph G. = (Vc, Fe, w where V. = {A such that U A V. and n A, 0, and the edge weights (A, A,) represent the degree of association between regions, defined as w( (A, Aj) EucAL.EA w(u, v). We then apply our recursive partitioning algorithm to G. and its corresponding normalized Laplacian matrix Le- As a result, we obtain region tree T.
Ablation studies Section 4.3 compare performances across various overelustering methods.
Boundary Sharpening. Given a predicted region tree T with leaves, B1. B2...., Bg- each em- bedding a disjoint segment of V, such that U/=1 B, V and 1 B, 9, we compute the prototypes for the image Each prototype defined as the fn-normalized average of the fea- ture codes in each leaf uj = |B -ve B, v. For each pixel, we define a conditional probability distribution over the prototypes using the softmax function with smoothing parameter т, namely, Ply = exp (u.T "yy=1)/ //Exx exp (u,J =)) We arrange the matrix P = [P:l] E [0. [](MNN)xX and sharpen the region boundaries applying a Conditional Random Fields (CRF) [49], which re- fine the predicted distribution P by incorporating dependencies between pixel observations 1. This improves the accuracy at the boundary, ensuring sharper and more precise segmentation of leaves.
Experiments
We benchmark our algorithm unsupervised object- and scene-centric datasets and seven hierarchically structured datasets with varying granular- ity levels for hierarchy-ggnosti segmentation. Our evaluation includes ablation study assess the contributions of each algorithm component and comparisons across different self-supervised backbone architectures. We only utilize publicly available datasets, SSL model checkpoints without retraining, and validation set ground -ruth annotations. CRF is applied only where specified.
segmentation using seven major
Each dataset provides unique characteristics essential for different segmentation challenges. Pas- calVOC2012 [27] offers a broad range of object categories, making it suitable for general object segmentation tasks. With its high-level division into things and stuff, COCO-Stuff [10] extends the

---

MSCOCO [53] and tests the algorithm in complex scenes with multiple objects. Potsdam and Vai- hingen [30] datasets, focused on acrial scene parsing, are designed for remote sensing and urban planning applications. Cityscapes [21] is critical for autonomous driving research, providing de- tailed annotations of urban street scenes. Mapillary Vistats [60] adds diversity with street scenes from various global environments, testing the algorithm's 's robustness to different conditions. KITTI- STEP [89] and KITTI-SS [1], similar to Cityscapes, extend the evaluation to dynamic urban scenar- ios with instance detection and object tracking. For fine-grained part segmentation, Pascal-Part [15], PartImageNet, and PartImageNet-155 [35] offer detailed part annotations, crucial for tasks requiring precise recognition and segmentation of object parts.
These datasets ensure a comprehensive and diverse benchmark for evaluating the performance and robustness of our segmentation algorithm across various contexts, see Figure 2. Further details about datasets are in Appendix D.I, and more quantitative and qualitative results are in Appendices D.3 and D.4, respectively.
To ensure reproducibility, we standardize our experimental setup. Unless otherwise specified, we use the S-NOv2-ViT-B14-RR [22] backbone with parameters Kmin = 1, Pmax = 20, and Amax = 0.8. We apply the spectral method from Ng al. [61] with m 300 for superpixel clustering. The recursive partitioning depth is limited at 10 levels. Depending on each backbone downsampling factor, input images are resized extract 60 60 codes, except for urban street scenes, where we obtain 60 120 codes. Further details in Appendix D.
4.1 Evaluation Metrics
NFCovering
NMCovering
NHCovering
Groumd-truth S/g
Prediition T
Ground-tuth Syt
Prediction T
Ground-ruuth
Prediction
Tgt
Max Ioll Matching
Ancestors Matching
Figure 3: Comparison of segmentation metrics. NFCovering evaluates single-level foreground overlap, NMCovering extends across multiple granular levels for all categories, and NHCovering integrates hierarchical consistency. Coloured arrows indicate category-specific matches.
Granularity Following [44], we aim to evaluate the unbiased overlapping of regions between predicted segmentation and ground truth within each image via the Normalized Foreground Covering (NFCovering) metric. However, is well-suited for the multi-granular segmentation domain. The metric applies to single granularity level at a time, failing to account for multiple granularity levels. Furthermore, it disregards the background valid semantic instance, leading to an incomplete estimate of segmentation performance.
We propose novel evaluation metric, the Normalized Multigranular Covering (NMCovering), which addresses these limitations evaluating the overlap of regions between the unrolled segments in the region tree T and all the available ground-trutt categorical segments in semantic map Syt- This metric ensures that both foreground and background instances are considered, providing a more comprehensive and granularity -nndeeedeeddeeeeeeettt assessment of semantic segmentation model's performance. We adopt greedy heuristic that maximises the overlap of the full hierarchy with the ground truth segmentation and compute the average overlap ratio of the matching:
ROR' RET
NMCovering(I (T' + Syz)) =
Stpt
max
RUR
(3)
RES

---

Table 1: Granularity Evaluation of our algorithm on different datasets using a max- imum overlap heuristic for category matching.
Table 2: Hierarchy--gnossie Evaluation of our algorithm on different datasets using a maxi- overlap heuristic for category matching.
Dataset
mloU
pAce
mAce
IlU
NMCovering (T
Dataset
mloU
pAce
NMCovering (T > TTg)
NHCovering
object-centrie
whole-centric
PuscalVOC2012
78.1
82.6
91.2
78.1
75.4
COCO-Stuff
75.1
MSCOCO
93.1
78.8
Citysapes
53.7
78.8
51.1
43.8
scene centrie
TT-STP
58.3
79.6
54.2
46.5
COCO-Stuff
81.1
67.3
Mapillary Vistas
Cityscapes
48.8
82.8
76.
68.8
44.8
purt-cowiric
KITTI-STEP
51.2
79.8
76.5
65.7
48.4
Puscal Purt
25.8
80.0
39.5
38.8
Mupillary
78.9
66.1
Imagenes
79.5
Potsdam
58.9
83.4
83.2
65.0
56.3
Part- Purt-Imagenet-Tee 158
59.5
82.6
67.8
63.1
The NMCovering metric evaluates the performance of a hierarchical segmentation model consid- ering how many ground truth objects are recognised at any granularity level and how well they are segmented. A high score indicates a high segmentation coherence between human semantic percep- tion and unsupervised machine one.
Hierarchy-agnostic. We introduce a second accuracy metric, the Normalized Hierarchical Cov- ering (NHCovering). NHCovering jointly evaluates the segmentation quality and the semantic hierarchical inclusion of the prediction relating to the ground-truth semantic region tree Tgt. Hi- erarchical inclusion is the matching between the nodes of two distinct hierarchies preserving the lineage from the ancestors; this problem is commonly referred to in the literature as the unordered free inclusion problem [45].
To calculate this metric, we use a greedy heuristic that computes the average overlap ratio match- ing regions, weighting each match by the ratio of matched ancestors. The operator π (R) returns the ancestors set of the tree node R. and (R,, T) returns the nodes set in the predicted tree T that best match the ancestors of node R:
NHCovering(T Tgt) = 1
RN R
(((R,T) [T(R)
max R'TT
(4)
[Tyel
RUR
RET
POP
where ((R,T) =
U
arg max P'ET
(5)
PU P"
PE)(R)
The NHCovering metric computes the average weighted overlap of regions between the predicted tree T and the ground-truti tree Tgt. The overlap weight measures the proportion of correct an- cestorships with respect to the ground truth. Balancing segmentation performance with semantic ancestry consistency provides granularity- and This score quantifies the coherence segmentation and hierarchical organization of visual concepts between human perception [66] and unsupervised machine one.
performance assessment.
Refer Figure for a visual insight into the metrics. more detailed discussion in Appendix D.2.
4.2 Unsupervised Segmentation
Granularity-Agnon We adopt the NMCovering metric to benchmark the performance and versatility our algorithm across different natural image domains. As shown in Tables I and 5, our method achieves excellent results in segmenting object-centric images and foreground discovery. Additionally, Table demonstrates our approach's strong performance on scene-centric datasets, such remote-sensing images and urban street scenes. Table 3 compares our approach to other su- pervision strategies.? Our approach achieves segmentation quality comparable to supervised meth- ods and surpasses other supervision strategies by large gap.
Hierarchy-Agnosticc
We further benchmark the hierarchical inclusion quality of the algorithm on available datasets having hierarchical structures high level, such as MSCOCO, COCO-Stul Stuff and Cityscapes, and low level, such as PascalPart and PartlmageNet.
show in Table
We ran four experiments for each dataset with random seed and assumed normally distributed errors. However, in the segmentation literature, mloU is typically reported by the single mean value in percentage.

---

Table 3: Semantic segmentation. Comparison on Pascal VOC2012 val. Ours match unsuper- vised masks to best overlapping classes.
Table 4: Boundary potential methods. All methods match unsupervised tree segments to best overlapping classes.
NMCovering (I -> Syd)
mToU
PascalVOC2012
mloU
pAec
Method
Backbone
VOC12
MSCOCO
boundary potential
fully rupervteed
SE-OWT [24]
48.4
83.0
59.0 61.3
DeepLab-CRF [12]
ResNet-101
77.7
DeepLab-CRF [12]
VGG-16
43.6
[10)
PMI-OWT-UCM [40]
47.0
86.5
DespLabV3-JFT [13]
ResNet-101
82.7
semantic smoothness
wwwld--uperrieed
Ours w/o CRF
78.1
86.0
75.4
WT.PCM (71)
69.3
45.0
Ours W CRF
80.3
87.3
76.8
1.2G [42]
ResNet 38
72.0
44.2
WeakTr [95]
NMCovering (T + Tyr)
un-sxpervisd
Melas- Kyriazi al. [58]
WTS11
37.2
COCO-Stulf
mloU
NHCovering
Leupart [96]
VIT.16
41.7
49.2
boundary potential
HSG [4-]
ResNet-50
41.9
SE-OWT-UCM [24]
30.7
43.0
32,9
Zhang [94]
43.5
PMI-OWT-UCM [40]
27.5
43.2
23.1
MuskDistill [79]
ResNet-50
48.9
semantic smoothness
Ours w/o CRF
VITSS
76.2 1 1
52.1
Ours w/o CRF
58.7
53.5
42.1
Ours CRF
VIT-B14
80.3
56.5
55.6
43,9
segmentation evaluation on Pascal val set using a maximum overlap heuristic for category matching in each image. We report category IoU for each experiment with micro and macro averaged scores and the NMCovering.
Table 5: Backbone ablation. Granularity
Buckbaa
Skzda
Exd
Cla GE
poass
dug
MARATRE 1A5-A1R21441
66.
$1.6
54.5
K5B
134
T14
624
B16
E1S
BAR
MAB
S14
12A
665
43
170
761
661
344
125
603
750
68.2
33.1
26.3
613
134
261
940
RLA
BLT
KAN
663
165
1A3
66.
164
113
754
663
31
118
12.
the closeness performance of NHCovering with respect to the NMCovering, demonstrating the ability of the algorithm to capture hierarchical relations among the parts. The lower performance on PascalPart due to the lower granularity of part annotations compared to PartImageNet, see [35].
Recent unsupervised semantic segmentation approaches, such as [44, 94], often employ mutual in- formation maximisation between regions multiple granularity levels. These methods typically utilise hierarchical clustering that groups low-level coherent regions via boundary potentials, such as the Ultrametric Contour Map (OWT-UCM) [4]. of boundaries derived from low-level features like brightness, colour, and texture gradients, as in Structured Edges (SE) [24] or Pointwise Mutual Information (PMI) [40]. We compare our approach with these methods in Table 4. The results indi- cate that low-level processes are inappropriate for the hierarchical grouping of high-level (semantic) features. In contrast, our approach excels this area, suggesting significant room for improvement in the current state of the art. See some hierarchical grouping results in Figure 4.
4.3 Ablation Experiments
Backbone. We evaluate in Table 5 the consistency of our approach according to the latent space induced by different SSL Imagenet pre-traine praitred backbones on the gramularity-agnosiic agnostic task on the
Parts
1r tevel
2 level
3rd level
Parts
1s level
2nd level
3rd tevel
Parts
1" level
2nd level
3rd level
Figure 4: Unsupervised parts discovering examples on PartImageNet The left column shows the ground truth part masks. The second fourth column shows the predicted regions for each tree depth. Heatmap colours encode leaves" distance in the subtrees.

---

Table 6: Superpixel and parameters ablation experiments.
(a) NMCovering on PartIma-
(b) mloU for m sizes with [61].
(c) NHCovering with differ-
geNet: superpixel Amin.
ent perturbation thresholds and
Superpioel
100
Masic
Pinin (snn/ther)
Dataset
object-centric
30
100
300
None
smoothness parameters the
COCO-Stuff dataset.
colour-guace
PascalVOC2012
76.3
77.5
78.1
78.1
(54)
MSCOCO
45.8
52.4
55.7
56.1
SLJC [2]
58.1
44.9
.85
Rcene-coitric
quicksshift (80)
60.8
58.0
21
=
COCO-Stuff
43.6
52.2
59.5
60.3
Amucx
Amax
SSL-latenr-spuur
Cityscupes
30.3
37.6
48.8
50.4
Paiox
None
(son/ite))
[51]
part-centnng
15
36.9
41.1
41.4
39
00
Spectral [6]]]
Pascal-Par
18.2
23.1
25.8
26.4
39.5
42.9
43.1
66
.16
PartInageNet
47.2
Pascal val set. The performance gap reflects the representation quality assessed by SSL downstream task benchmarks. Such result assesses the best model and complementary down- stream task benchmark for SSL. We do not adopt superpixel clustering or CRF but utilise raw patch features as pixel codes.
Parameters kmins Pmaz and Amas In Tables 6a to 6c we validate the optimal parameters of our algorithm. While kmon choice affects the granularity at lower levels, the Pmon and Xmaz choice affects the granularity at higher levels by controlling the stability of the partition.
Overclustering and CRE We test different over clustering techniques in Table 6a. Results show higher performances for simultaneous normalised cut on SSL latent space. When applying CRF with r = 0.1, we obtain an increase segmentation accuracy as shown Tables and 4.
Discussion
Broader impact. Supervised learning typically relies on highly curated datasets that require pensive and time-consuming manual annotations, especially for complex tasks that demand expert knowledge, such fine-grained semantic segmentation. As the demand for larger datasets grows and costs rise, increasing interest is in advancing image understanding with minimal or no supervi- sion. Our approach addresses this challenge by streamlining the annotation process, reducing costs, and thereby significantly expanding the data available for supervised model training through the dynamic discovery of semantic regions.
Limitations. While our method shows promising results, it does have limitations. One major drawback is that both segmentation quality and algorithm execution time scale with the input size. Small object parts are especially difficult to detect, particularly when overclustering is used during preprocessing; the results support this. However, a trade-off between accuracy and inference time can be experimentally determined. Moreover, our approach is based on self-supervised lcarning, which, like all data-driven methods, is susceptible to inherent biases in the data. These biases can influence the resulting latent space of the model, potentially impacting the performance and gener- alization of our approach.
Conclusions
We introduce novel method for unsupervised hierarchical decomposition of natural scenes into primitive components, without requiring prior knowledge of scene granularity. Leveraging deep fea- ture extraction and graph partitioning, our approach constructs a tree of semantic elements from any scene for any dataset. Our core algorithm applies an innovative algebraic approach to deep spectral clustering, addressing blurring from pixel similarity across object parts. Matrix perturbation theory employed at each tree level, ensuring stable smooth partitions. This framework not only advances unsupervised semantic segmentation but also benchmarks deep neural network representations by evaluating segmentation quality at multiple granularity levels and hierarchical consistency among them. We validate method with novel metrics, evaluating overlap with ground-truth masks across diverse semantic segmentation datasets and semantic inclusion within hierarchical ones.
10

---

References
[1] Hassan Abu Alhaija, Siva Karthik Mustikovela, Lars Mescheder, Andreas Geiger, and Carsten Rother. Augmented reality meets computer vision: Efficient data generation for urban driving scenes. WCV, 126:961-9777 2018.
[2] Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. SLIC superpixels compared to state-of-the-art superpixel methods. IEEE TPAMI, 34(11):224422882, 2012.
[3] Amit Aflalo, Shai Bagon, Tamar Kashti, and Yonina Eldar. DeepCut: Unsupervised segmen- tation using graph neural networks clustering. In ICCV, pages 32-41, 2023.
[4] Pablo Arbelaez, Michael Maire, Charless Fowlkes, and Jitendra Malik. Contour detection and hierarchical image segmentation. JEEE TPAMI, 33(5):898-914) 2010.
[5] Shahaf Arica, Or Rubin, Sapir Gershov, and Shlomi Laufer. CuVLER: Enhanced unsupervised object discoveries through exhaustive self-supervised transformers. In CVPR, pages 23105- 23114, 2024.
[6] Arik Azran and Zoubin Ghahramani. Spectral methods for automatic multiscale data cluster- ing. In CVPR, volume 1, pages 190-197, 2006.
[7] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning, 56:89-113, 2004.
[8] Mikhail Belkin and Partha Niyogi. Semi-supervised learning manifolds. Machine Learning Journal, 1, 2002.
(9] Rajendra Bhatia, Chandler Davis, and Alan McIntosh. Perturbation of spectral subspaces and solution of linear operator equations. Linear algebra and its applications, 52:45-67, 67, 1983.
[10] Holger Caesar, Jasper Uijlings, and Vittorio Ferrari. COCO-Stuff: Thing and stuff classes in context. In CVPR, pages 1209-1218, 2018.
[11] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In ICCV, pages 9650-9660, 2021.
[12] Liang-Chied Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L Yuille. DeepLab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected CRFs. IEEE TPAMI, 40(4): 848, 2017.
[13] Liang-Chich Chen, George Papandreou, Florian Schroff, and Hartwig Adam. Rethinking atrous convolution for semantic image segmentation. arXiv preprint arXiv:1706.0m 2017.
[14] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In ICML, pages 1597-1607. PMLR, 2020.
[15] Xianjie Chen, Roozbeh Mottaghi, Xiaobai Liu, Sanja Fidler, Raquel Urtasun, and Alan Yuille. Detect what you can: Detecting and representing objects using holistic models and body parts. In CVPR, 2014.
[16] Xinlei Chen, Saining Xie, and Kaiming He. An empirical study of training self-supervised vision transformers. In ICCV, pages 9640-9649, 2021.
[17] Jang Hyun Cho, Utkarsh Mall, Kavita Bala, and Bharath Hariharan. PiCIE: Unsupervised se- mantic segmentation using invariance and equivariance in clustering. In CVPR. pages 16794- 16804, 2021.
[18] Sumit Chopra, Raia Hadsell, and Yann LeCun. Learning a similarity metric discriminatively, with application to face verification. In CVPR, volume 1, pages 539-546, 2005.
[19] Subhabrata Choudhury, Iro Laina, Christian Rupprecht, and Andrea Vedaldi. Unsupervised part discovery from contrastive reconstruction. NeurIPS, 34:28104-2811 2021.

---

[20] Fan RK Chung, Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[21] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Ro- drigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The Cityscapes dataset for semantic urban scene understanding. In CVPR, June 2016.
[22] Timothée Darcet, Maxime Oquab, Julien Mairal, and Piotr Bojanowski. Vision transformers need registers, 2023.
[23] Chandler Davis and W. M. Kahan. The rotation of eigenvectors by a perturbation. iii. SIAM Journal Numerical Analysis, 7(1):1-46, 1970.
[24] Piotr Dollár and C. Lawrence Zitnick. Structured forests for fast edge detection. In ICCV, 2013.
[25] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 11999, 2021.
[26] Justin Eldridge, Mikhail Belkin, and Yusu Wang. Unperturbed: spectral analysis beyond Davis-Kahan. In Algorithmic learning theory, pages 321-358. PMLR, 2018.
[27] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisser- man. The pascal visual object classes (VOC) challenge. IJCV, 88(2):303-338, 2010.
[28] Jianqing Fan, Weichen Wang, and Yiqiao Zhong. An lanfty eigenvector perturbation bound and its application. Journal of Machine Learning Research, 18(207):1-42, 2018.
[29] Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23 (2):298-300) -0098 1973.
[30] Markus Gerke. Use of the stair vision library within the isprs 2d semantic labeling benchmark (vaihingen), 01 2015.
[31] Abel Gonzalez-Garcia, Davide Modolo, and Vittorio Ferrari. Do semantic parts emerge in convolutional neural networks? IJC,, 126:476-494, 2018.
[32] Mark Hamilton, Zhoutong Zhang. Bharath Hariharan, Noah Snavely, and William T Freeman. Unsupervised semantic segmentation by distilling feature correspondences. In ICLR, 2021.
[33] Robert Harb and Patrick Knöbelreiter. InfoSeg: Unsupervised semantic image segmentation with mutual information maximization. In DAGM-GCPR, pages 18-32. Springer, 2021.
[34] Bharath Hariharan, Pablo Arbeláez, Lubomir Bourdev, Subhransu Maji, and Jitendra Malik. Semantic contours from inverse detectors. In ICCV, pages 991-998, 2011. doi: 10.1109/
[35] Ju He, Shuo Yang, Shaokang Yang, Adam Kortylewski, Xiaoding Yuan, Jie-Neng Chen, Shuai Liu, Cheng Yang, and Alan Yuille. PartImageNet: A large, high-quality dataset of parts. arXiv preprint arXiv:21
2021.
[36] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, pages 9729-9738. 2020.
[37] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. arXiv:21 1 1.06377, 2021.
[38] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[39] Wei-Chih Hung, Varun Jampani, Sifei Liu, Pavlo Molchanov, Ming- Hsug- Yang. and Jan Kautz. SCOPS: Self--spe co-part segmentation. In CVPR, pages 869- 8888 2019.
[40] Phillip Isola, Daniel Zoran, Dilip Krishnan, and Edward H. Adelson. Crisp boundary detection using pointwise mutual information. In ECCV, 2014.
12

---

[41] Xu Ji, Joao F Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. ICCV, pages 9865-9874 2019.
[42] Peng- Tao Jiang, Yuqi Yang, Qibin Hou, and Yunchao Wei. L2G: A simple local-to-global knowledge transfer framework for weakly supervised semantic segmentation. In CVPR, pages 16886-18 16886, 2022.
[43] Tosio Kato. Perturbation theory for linear operators, volume 132. Springer Science & Busi- ness Media, 2013.
[44] Tsung-War Wei Ke, Jyh-Jing Hwang, Yunhui Guo, Xudong Wang, and Stella X Yu. Unsupervised hierarchical semantic segmentation with multiview cosegmentation and clustering transform- ers. In CVPR, pages
2022.
[45] Pekka Kilpeläinen and Heikki Mannila. Ordered and unordered tree inclusion. SIAM Journal on Computing, 24(2):340-355 1995.
[46] Junho Kim, Byung- Kwan Lee, and Yong Man Ro. Causal unsupervised semantic segmenta- tion. arXiv preprint arXiv:2310007379, 2023.
[47] Wonjik Kim, Asako Kanezaki, and Masayuki Tanaka. Unsupervised learning of image seg- mentation based on differentiable feature clustering, IEEE TIP, 29:8055-8068 2020.
[48] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan Yen Lo, et al. Segment anything. In ICCV, pages 4015-4026, 2023.
[49] Philipp Krähenbühl and Vladlen Koltun. Efficient inference in fully connected CRFs with gaussian edge potentials. NeurlPS, 24, 2011.
[50] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60(6):84-99) 2017.
[51] Mengcheng Lan, Xinjiang Wang, Yiping Ke, Jiaxing Xu, Litong Feng, and Wayne Zhang. Smooseg: smoothness prior for unsupervised semantic segmentation. NeurlPS, 36, 2024.
[52] Kehan Li, Zhennan Wang, Zesen Cheng, Runyi Yu, Yian Zhao, Guoli Song, Chang Liu, Li Yuan, and Jie Chen. Acseg: Adaptive conceptualization for unsupervised semantic seg- mentation. In CVPR, pages 7162-7172, 2023.
[53] Tsung-Y Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft COCO: Common objects context. In ECCV, pages 740-755, 2014.
[54] Stuart Lloyd. Least squares quantization in PCM. IEEE TIT, 28(2):129-13) 1982.
[55] Nikos Logothetis and David L Sheinberg. Visual object recognition. Annual review of neuroscience, 19(1)5577-221, 1996.
[56] Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for seman- tic segmentation. In CVPR, pages 3431-3440, 2015.
[57] Timo Lüddecke and Alexander Ecker. Image segmentation using text and image prompts. In CVPR, pages 7086-7096, June 2022.
[58] Luke Melas Kyriazi, Christian Rupprecht, Iro Laina, and Andrea Vedaldi. Deep spectral meth- ods: A surprisingly strong baseline for unsupervised semantic segmentation and localization. In CVPR, pages 8364-8375, 2022.
[59] Russell Merris. Laplacian matrices of graphs: a survey. Linear algebra and its applications, 197:143-176. 1994.
[60] Gerhard Neuhold, Tobias Ollmann, Samuel Rota Bulo, and Peter Kontschieder. The Mapillary Vistas dataset for semantic understanding of street scenes. In ICCV, pages 4990 2017.
13

---

[61] Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algo- rithm. NeurIPS, 14, 2001.
[62] Dantong Niu, Xudong Wang. Xinyang Han, Long Lian, Roei Herzig, and Trevor Darrell. Un- supervised universal image segmentation. In CVPR, pages 22744-22754, 2024.
[63] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:180..0377 2018.
[64] Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo. Mare Szafranicc, Vasil Khali- dov, Pierre Fernandez. Daniel Haziza, Francisco Massa, Alaacldin El-Nouby, al. DINOv2: Learning robust visual features without supervision. arXiv preprint arXiv:2304.07193, 2023.
[65] Sean O' Rourke, Van Vu, and Ke Wang. Random perturbation of low rank matrices: Improving classical bounds. Linear Algebra and its Applications, 540:26-555 59, 2018.
[66] Stephen E Palmer. Hierarchical structure in perceptual representation. Cognitive psychology, 9(4):441-444, 1977.
[67] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In ICML, pages 8748-8763, 2021.
[68] Sriram Ravindran and Debraj Basu. SEMPART: Self-supervised multi-resolution partitioning of image semantics. ICCV, pages 723-733, 2023.
[69] Ren and Malik. Learning a classification model for segmentation. In ICCV, pages 10-17. IEEE, 2003.
[70] Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statisties, 39(4):1878 1915, 2011.
[71] Simone Rossetti, Damiano Zappia, Marta Sanzari, Marco Schaerf, and Fiora Pirri. Max pool- ing with vision transformers reconciles class and shape in weakly supervised semantic seg- mentation. ECCV, pages 801-818, 2022.
[72] Ramprasaath Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-CAM: Visual explanations from deep networks via gradient- based localization. In ICCV, pages 618-626, 2017.
[73] Hyun Seok Scong, WonJun Moon, SuBeen Lee, and Jae-Pil Heo. Leveraging hidden positives for unsupervised semantic segmentation. In CVPR, pages 19540-19549, 2023.
[74] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE TPAMI, 22(8): 888-900 088-905,20 2000.
[75] Gilbert W Stewart and Ji-guang Sun. Matrix perturbation theory. Academic Press, 1990.
[76] Anne M Treisman and Nancy G Kanwisher. Perceiving visually presented objets: recognition, awareness, and modularity. Current opinion in neurobiology. 8(2):218-22) 1998.
[77] Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, and Luc Van Gool. Unsu- pervised semantic segmentation by contrasting object mask proposals. In CVPR, pages 10052- 10062. 2021.
[78] Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, and Luc Van Gool. Re- visiting contrastive methods for unsupervised learning of visual representations. In NeurlPS, 2021.
[79] Wouter Van Gansbeke, Simon Vandenhende, and Luc Van Gool. Discovering object masks with transformers for unsupervised semantic segmentation. arXiv preprint arXiv:2206.06366: 2022.
[80] Andrea Vedaldi and Stefano Soatto. Quick shift and kernel methods for mode seeking. In ECCV, pages 705-718. Springer, 2008
14

---

[81] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395 -16, 2007.
[82] Ulrike Von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. The Annals of Statistics, pages 555-586, 2008.
[83] Johan Wagemans, Jacob Feldman, Sergei Gepshtein, Ruth Kimchi, James R Pomerantz, Pe- ter A Van der Helm, and Cees Van Leeuwen. A century of gestalt psychology in visual percep- tion: Ii. conceptual and theoretical foundations. Psychological bulletin, 138(6):1218, 2012.
[84] Xinlong Wang, Rufeng Zhang, Chunhua Shen, Tao Kong, and Lei Li. Dense contrastive learn- ing for self-supervised visual pre-training. In CVPR, 2021.
[85] Xinlong Wang. Zhiding Yu, Shalini De Mello, Jan Kautz, Anima Anandkumar, Chunhua Shen, and Jose M Alvarez. Freesolo: Learning to segment objects without annotations. In CVPR, pages 14176-1418 2022.
[86] Xudong Wang. Ziwei Liu, and Stella X Yu. Unsupervised feature learning by cross-level instance-group discrimination. In CVPR, pages 12586-12555 2021.
[87] Xudong Wang, Rohit Girdhar, Stella X Yu, and Ishan Misra. Cut and learn for unsupervised object detection and instance segmentation. In CVPR, pages 3124-3134, 2023.
[88] Yangtao Wang, Xi Shen, Shell Xu Hu, Yuan Yuan, James Crowley, and Dominique Vaufrey- daz. Self-supervised transformers for unsupervised object discovery using normalized cut. In CVPR. pages 14543- 14553, 2022.
[89] Mark Weber, Jun Xie, Maxwell Collins, Yukun Zhu, Paul Voigtlaender, Hartwig Adam, Bradley Green, Andreas Geiger, Bastian Leibe, Daniel Cremers, Aljosa Osep. Laura Leal- Taixe, and Liang-Chich Chen. STEP: Segmenting and tracking every pixel. NeurIPS, 2021.
[90] Zhaoyuan Yin, Pichao Wang, Fan Wang, Xianzhe Xu, Hanling Zhang, Hao Li, and Rong Jin. Transfgu: top-down approach to fine-gra fine-grained unsupervised semantic segmentation. In ECCV, pages 73-89. Springer, 2022.
[91] Yi Yu, Tengyao Wang, and Richard J Samworth. A useful variant of the Davis-Kahan theorem for statisticians. Biometrika, 102(2)3315-322 2015.
[92] Yang Yuan. On the power of foundation models. In ICML, pages 40519 401199 PMLR, 2023.
[93] Andrii Zadaianchuk, Matthaeus Kleindessner, Zhu, Francesco Locatello, and Thomas Brox. Unsupervised semantic segmentation with self-supervised object-centric representations, In Learning Representations, 2023.
[94] Xiao Zhang and Michael Maire. Self-supervieed visual representation learning from hicrarchi- cal grouping. NeurlPS, 13599199166 2020.
[95] Lianghui Zhu, Yingyue Li, Jiemin Fang, Yan Liu, Hao Xin, Wenyu Liu, and Xinggang Wang- Teak'Tr: Exploring plain vision transformer for weakly-supervised semantic segmentation, 2023.
[96] Adrian Ziegler and Yuki M Asano. Sele-super learning of object parts for semantic seg- mentation. In CVPR, pages 14502-14511, 2022.
[97] Xueyan Zou, Jianwei Yang, Hao Zhang, Feng Li, Linjie Li, Jianfeng Wang, Lijuan Wang, Jianfeng Gao, and Yong Jae Lee. Segment everything everywhere all at once. NeurIPS, 36, 2024.
15

---

A Theoretical Analysis and Perturbation Foundations
A
aasd
kgg
ball
racket
Bead
Paak
legs
bull
racket
0:55
0.32
0.
0.90
trakk
9.00
0.90
0.30
bell
rudket
likol matris
Porturbed
ATER
ball
Figure 5: An example of ideal and perturbed adjacency matrices. The left shows an input image with highlighted parts and a colour legend. The central matrix represents the ideal adjacency matrix W", corresponding to the Laplacian I,, with non-zero diagonal blocks for k' disconnected compo- nents at a specific semantic granularity. Below, a disconnected graph illustrates these isolated parts. On the right, the perturbed adjacency matrix W introduces off-diagonal entries due to pixel similar- ity across regions, resulting in the perturbed Laplacian L. Below, a graph with added connections shows these perturbations, with colours matching the highlighted parts in the input image.
From the example in Figure 5, we observe that perturbation arises from pixel similarity values that inadvertently create connections between regions, which ideally should remain separate. This unintended overlap occurs because similarity values between certain pixel pairs do not perfectly align with the true structure of the components. Perturbation theory [23, 9, 75, 43] studies how small changes, such as these unintended connections, affect a matrix's ' eigenspaces. Recent research has expanded this analysis from Hermitian matrices to include Laplacian matrices, which capture graph structures, as in [82, 26, 70, 28, 65, 91].
In our method, the two matrices are an ideal Laplacian matrix T.' and the observed Laplacian matrix T. both symmetric (not necessarily of the same rank), perturbed by a symmetric matrix H induced by higher-order pixel similarity, L = L'+ Given the recursive partitioning described in Section 3, we are looking, for each subgraph, for the best matches between the eigenvectors of L' and those of L minimising the functional defined in Equation (1).
In the ideal normalized Laplacian L', the graph is disconnected, and the number of connected com- ponents is reflected in the multiplicity of the zero eigenvalue of L'. Each connected component con- tributes one zero eigenvalue, and the constant eigenvectors corresponding to these zero eigenvalues represent these isolated components [20, 81]. In a perturbed normalized Laplacian T., the graph is connected and then the minimum of Equation (2) is achieved by the eigenvector corresponding to the second smallest eigenvalue of T/_ This eigenvector, known as the Fiedler vector, is not constant and captures the connectivity structure of the graph, often used for finding the best bipartition.
However, in the case of a perturbed graph with weak connections (e.g., low weights or nodes with only a single neighbour), small eigenvalues close zero may not indicate strongly connected sub- graphs. Instead, these small eigenvalues reflect loosely connected regions, where perturbations cre- ate weak links between components that ideally should remain separate. This implies that using the smallest eigenvectors directly for graph partitioning is sometimes unreliable, as they may reflect unstable or artificial connections introduced by perturbations. To ensure meaningful segmentation, it is essential to establish a measure that quantifies the stability of the partition under perturbations. Such measure would indicate when it is safe to apply spectral clustering, ensuring that the iden- tified clusters are robust and well-separated. According to Theorem A.1 (shown below), to achieve this, we seek the set of eigenvectors of the perturbed Laplacian L that are closest to the eigenvectors of the ideal normalized Laplacian L' despite the perturbation H:
16

---

Theorem A.1 (191)). Let A, A' E R be symmetric. with eigenvalues μ1 2 ... 2 pn and Mi 2 2 Hr respectively. Fix Sr where p40 == xc and Mat1 == -0,, Let u == 8- and let Z = (Zr; 2p-1.-.. 2x) E &Rax and
and assume that min(H1,-1 Hr. Ms 11-11 1) > 0,
7.' ( 2g)) TRax have orthonormal columns satisfying Azj = 22zz and A =
for for = -r ,,...,,. Then:
2min 2min(u\/2144t A Allop. || Alls)
sin O Z) S
(6)
min( Mr: Ms Ms+1)
Moreover there exists and orthogonal matrix O' RRxx such that:
Z'' Z| 23/2 min(u./3 Allop: I|A' Al(
min(/4--1 Mr: Pis 1s+1)
With op and F, the spectral and the Frobenius norm, respectively.
Corollary A.1 (191). Let A, A' E R be symmetric, with eigenvalues μ1 2 ... 2 nm and
(4 2 ... 2 pl, respectively. Fix j E (1, .I.....n)) and assume that min(f1;- Pjz Pj:Hi - 11++1) ) > 0,
where pi == oc and po+11 == -0. 2f 2'c E R satisfy Az 11zz and A'z' = 11 then:
2|| - Allop
sin (=), S
(8)
min ( 11 1bj 11-+1
Moreover, 2f 2 2 0, then:
23/21| Allop
|| - 211 min - Mý 14 P++1)
(9)
In our method, the above symmetric matrix A refers to the perturbed matrix I and the matrix A' to the idcal matrix L'; see Scction 3. Since we select the i smallest eigenvalues, the interval starts from n k + and ends at
and we have u = k. The denominator in Equation (6) simplifies to
min(Hnnk - #n- Un - Ma+1) = Pn-k - --11 since by definition Un+1 == -0o, and, given = 12 h ................................ 2n,) E ma and Z' -2 on the chosen eigenvalue ordering, we have:
1+1 2/1 - ..... 2n)) E m depending
2 minn (// L' L ollop |I'' LIlF) for #n 2 ... 2 Mux
|| sin O 2))l= -
(10)
Pn-k Un k+1
or, reversing the indexing eigenvalues in non-decreasing order and counting from zero, we set >; = (n and X pn-s for O,.... n - I with Y = (yo, y/,, yh 11--1) E Runk and
Y = (v6. Ví V E Baa the orthonormal columns satisfying Ly, = A5y; and I/yl = X,US-
for j 0,
have:
2 2min(22/2
LLllop IL - L(lF) for do S.... ... S An- (11)
s|n O(V Y)
d AK-1
Indeed, we apply the substitution and the indexing, given the eigenpairs (A, y) condition for all the eigenvalues and eigenvectors populating the chosen interval (r. Furthermore, given the eigenpair condition, the minimization of Equation (1) in Section 3 is guaranteed (see Algorithm 1), and we can just ratify the smoothness by resorting to the Courant-Fisher theorem; see [38] Theorem 4.2.6. Finally, we can use the Corollary A.I for more refined choice of the eigenvectors.
Note that the theorem of Yu et al. [91] is particularly useful because, differently from Davis- Kahan [23] theorem, it defines an upper bound between two symmetric matrices concerning the angles between a subset of the eigenvectors of the two matrices or their distance (up to a rotation), in terms of the eigenvalues of one of the two matrices. Indeed, this theorem shows that (an eigen- vector of the perturbed Laplacian L) is close to z' (an eigenvector of the Laplacian L'), under two main assumptions. First, assume that L is close to L' - often this is straightforward in graph theory, for instance, if L'' is derived from a theoretical (or "population") graph structure, and L is the Laplacian of graph constructed from sample noisy measurements of this structure. Second, applying Weyl's inequality, we assume that, almost certainly:
1 Myy 2 (nz-1 n2)/2 and 1 Myl 2 (1y 1y+1)/2,
17

---

where 2j and p4 are the j-th eigenvalues of L and L', respectively. Under this eigengap condition, assuming sufficient separation between the population eigenvalues of L and their neighbouring values, as shown in Yu et al. [91] results, we can conclude that || =|| is small, meaning = and z' are close in norm. Building on this, the theorem implies that when the eigengap condition holds, the eigenvector associated with L remains stable under perturbations represented by H = L. T'. Specifically, the proximity of z and z' allows us to interpret & as a meaningful approximation of z', preserving the structure of the ideal graph encoded by L'.
Consequently, this alignment of eigenvectors facilitates robust graph- based clustering or segmenta- tion, as it enables us to consistently identify clusters or partitions in perturbed graphs that mirror the structure of the unperturbed graph. Furthermore, this result provides foundation for using the perturbed cigenvectors for hierarchical clustering by ensuring that the segments or clusters derived from I. approximate those of T'' even under small changes or noise the graph data.
B
The Algorithm and BFS Implementation
Input image
nnt step
2" step
Irput image
stop
2" stce
Input image
step
2" step
1" stpp Coarse Semanti Parts Extmetion
2" step: Fine Semantic Hierarcly Extraction
Figure 6: The algorithm's 's two steps outputs. First, we quantize the graph to create an initial over- clustering of semantic parts. Next, recursively group these parts, forming multi-level semantic clusters from coarse to fine granularity. The heatmap colour-codes the distance between tree leaves.
In Section 3 of the main paper, we have presented the recursive partitioning of the graph G, which is simple and intuitive. As noted, we present Breadth- Search (BFS) pseudocode in Algorithm
The method obtains graph partitions when two or more components are detectable and recur on each partition to find new subgraphs until early stopping condition is met, see Section 3. We report that the proposed algorithm is defined in two steps for completeness - the first step is meant to speed up the overall algorithm, and hence, it is optional. In the first step, we quantise the graph, creating an over-clustering of semantic parts; in the second step, we recur on the parts, generating coarse to finer semantic groups at multiple granularity levels; see Figure 6.
In the first step, we write the patch-wise features extracted with a deep neural network as the set of nodes V of weighted undirected graph G (V,E, w), and we define the cosine similarity of points, sealed and shifted in [0, 1].
In this step. we follow the approach of Ng et al. [61] to cluster the graph in m components. The clusters define m disjoint segments A,, A2,..., Am (Uth A; V. n A, = 0) of G with high intra-cluster degree of semantic similarity.
In the second step, we adopt a top-down recursive divisive clustering approach, building hier- archical semantic decomposition of the image. In the recursive call at a certain level / and for certain subgraph e notice that here e is an index of a graph p we define an undirected condensed graph G (V..P, E w). with segments A as nodes in ViP (Uev! A C V.
Dsevi A 0) and the edges are weighted by the associativity degree of the components
18

---

(A, Aj) EuEA, w(u, v). Notice that the condensed graph at the root level is indicated as Go = (Vo Eo () and y0 = {A At each depth, we obtain semantic grouping St (V(+1e))
Je, given by all the i-th subgraphs at level / of each subgraph at level (.
The recursion defines the final hierarchy, namely the output tree T.
The semantic grouping algorithm discussed here builds upon conventional spectral clustering meth- ods [74, 61, 81].
Algorithm 1: Image Parsing via Granularity and Hierarchy-agnosie Semantic Regions Tree
Data:
V: set points wi points similarity function
desired number of superpixels
components similarity function
Amaa: max number suhgraph components
kmnn: min number of subgraph points
Aman: max normalized smoothness threshold
Pmax: perturbation threshold
Result: E-depth hierarchy of clusterings {S
1000 [A, apectral__verrcuusterriig (S') "ts.parriitionnn(([.1]]
Function opeecrra_.verrcuusterinng
Compute L for graph G E, w)
+ arg e /a Tr(Y LY)
Normalize rows X;, = Vr/(E, (/)) 1/)1/22
Group X rows in m clusters with K-means return groups (A: J of
Function bfs_ppartitionin((S}> gt+1 +
foreach segment V. E St do [V..
if n < Kmin then continue
end
Get condensed graph G +- G (V..P, E..", w) Scale W with min-max normalization and compute L
Y arg milly eanxkmar y y= Tr(Y" LY)
À diag(Y LLY)
Reorder columns and À ascending order of X Ai-1 Amar
& arg max, (As ) Rmaz
if A then continue
end
Take first eigenvectors Y +- 1(.
Normalize rows Xt,, = Yr,/(E, Y2,)2/2
Group X rows in & clusters with K-means and get T,' Compute perturbation H
min(k' [ lop, [||]|r)((ax >x-1) pmaz then continue
end
Found stable & subgraphs estimate S441 (V.+tlopk of V/ g1+11 u
end
return (5 U Wuba_pppaaaeee wtt.beeprtitionnng/SSS.t
19

---

Discussion above the algorithm. The algorithm's 's design integrates several properties that signif- icantly shape semantic components' hierarchical structure and connectivity.
One crucial feature is the dynamic estimation of the number of components, k, a parameter closely aligned with insights from perturbation theory. This estimate directly influences segmentation gran- ularity, determining the expected number of distinct semantic regions and hierarchy levels in the final output.
The algorithm produces a hierarchy-agnostic unsupervised semantic region tree T. At each recursion stage, it seeks subgraphs that represent loosely connected regions based robust algebraic criteria from graph theory, capturing coherent semantic regions at each level of granularity. By isolating each region from the context of previous layers, the algorithm accurately reflects the semantic hierarchy within the image's content. In this framework, the tree's s leaves represent regions with high intra- cluster semantic similarity, positioning these clusters as primitives of broader concepts at higher levels. The algorithm naturally embeds semantic inclusion, where finer semantic regions exist within larger semantic contexts, mirroring how complex concepts encompass finer details.
Lastly, computing the adjacency matrix only once optimizes efficiency, reducing redundant opera- tions and improving runtime performance, making the approach both scalable and effective for large datasets.
Time Complexity. The breadth-first search has a time complexity of O(IV) + EE) on general graph. In our case, with n nodes and n edges (assuming a tree graph), BFS has complexity O(n + (n - 1)) = O(2n - 1) (n)) The eigendecomposition of symmetric matrix in the worst case has a complexity of O(n"). Therefore, the combined time complexity O(n + n²) = O(n²). However, because
only compute the smallest kimax < n eigenvectors, the time complexity of the cigendecomposition reduces to (himax")") Thus, the overall complexity becomes O(n ( himxx =
O (Immax n2?) since kmax?? 2 dominates n1.
The recursive partitioning process starts with an eigendecomposition on the full graph, which has a time complexity of O(kma.??)) ) for extracting the smallest kmux eigenvectors. This initial compu- tation is the primary contributor to the algorithm's time complexity. As the partitioning proceeds, each recursive call operates on progressively smaller subgraphs. While each subgraph requires an eigendecomposstion, the cost decreases significantly as the graph size is reduced each recursion level. For balanced partitioning, the cumulative cost of these recursive steps remains asymptoti- cally bounded by the initial computation on the full graph. Thus, the overall complexity effective Olkmaxtt²) ensuring computational feasibility even for large graphs.
C Graph Partitioning with Normalised Cut
We recall here the Normalised Cut (NCut) introduced by Shi and Malik [74] for measuring the goodness of graph partition.
Let G (V, E, w) be a weighted undirected graph, having n nodes, V [0: representing points U, Rd. The weight on each edge of the graph way w(v,, 25) is a function of the similarity
between nodes v; and iy and defines an element of the adjacency matrix W = [way] E [0, 1]nx0.
The symmetrically normalised Laplacian of the graph [59] is defined as, L = D 1/ WDWWWW-- with D = diag [d.] E max= the diagonal degree matrix and d: = Σ3 Waj-
The normalised cut objective aims to partition the set V into two disjoint sets A C V and B c V (A U B V. A n () while minimising the degree of similarity between the two sets and maximising the one within each set, and it is defined as:
cut (A, B) cut(A, (A, B) NCut (A, B) assoc (A, assoc(B, V)
(12)
where cut(A,B) EVEATED w(u, v) measures the degree of similarity between A and B and is equal to the total weight edges that the partitioning has removed, assoc(A, (A, V) = EneA. w(u,t) t) measures the degree of similarity between A and V. and assoc(B, V) is equiva- lently defined. The NCut is an unbiased measure of the normalised total similarity of the two sets of points. Indeed, normalisation avoids unnatural bias when partitioning out small sets of points. Min- imising exactly Equation (12) is NP-complete, according to the proof due to Papadimitriou [74].
20

---

However, [74] shows a tractable real-valued solution to the relaxed problem in Equation (12) can be obtained by solving the generalized eigenvalue system (D 2 ADx, for z E I and R. The eigenvectors span an orthogonal basis for functions on G [81]:
32
arg min FER .| =la
x LL,, with = ,,...,7---
(13)
with 20 E RR.. The eigenvalues A; with right-hand side of the above expression. The eigenvector corresponding to the second smallest eigenvalue Å of L is the non-trivial solution to the quadratic form in Equation (13), called the Fiedler vector [29]. However, this real-valued solution can be transformed into a discrete form to partition the set in two disjoint sets A and B approximating the solution to the normalised cut problem in Equation (12) [74].
Ao S A1 S... An-1 are the values of the
The former approach can be expanded to further partition the generated subgraphs. employing the subsequent eigenvectors. Indeed, the eigenvector 32 linked to the third smallest eigenvalue X2 ef- ficiently divides into two parts, A and B. However, the practical application reveals that if higher eigenvectors are used, the gap between real-valued and discrete-valued solutions widens, asking for a global mutual orthogonality constraint for all eigenvectors. Consequently, solutions relying on higher eigenvectors tend to be less dependable. It is often more advantageous to restart the partition- ing process for each subgraph separately [74].
D More about Experiments and Metrics
The code implementation is in Python 3. We ran experiments on an ASUS ESC8000 server with two AMD EPYC 7413 24-core processors and 256GB RAM. We used the PyTorch 2.3 deep learn- ing framework and 2 NVIDIA A6000 GPUs with 48GB of VRAM to accelerate the feature extrac- tion stage. For all the experiments the paper, we ran our algorithm with the Python multi-threading library joblib up to 96 workers.
D.1 Datasets
PascalVOC2012 [27] is generic object-centric semantic segmentation dataset of 20 object cate- gories and a background class. It consists of 1, 449 images for validation. We follow [12] to obtain a larger image set with additional annotations [34], resulting in 10, 582 images.
COCO-Stuff [10] is complex scene-centric dataset that extends the object-centric MSCOCO [53] dataset, with a high-level hierarchical structure. Concepts are split at the root level into things and stuff, each having outdoor and indoor subsets. There are 12 things and 15 stuff supercategories, and 80 things and 91 stuff' categories. Objects appear in complex scenes, with more thing objects per image than PascalVOC2012 (7.3 vs. 2.3). Following [78, 84], we use v split of 5, 000 images.
Potsdam, Vaihingen [30] are scene-centric datasets for aerial scene parsing with 6 categories (roads, cars, vegetation, trees, buildings, clutter). The raw 6000 x 6000 images are di- vided into 100 RGB 600 600 patches. We obtain total of 3, 800 images for Potsdam and 3, 300 images for Vaihingen.
Cityscapes [21] is an urban street scene-centric dataset with a high-level hierarchical structure, hav- ing 7 supercategories subdivided into 19 stuff and object categories. Unlike COCO-Stuff and PascalVOCC201,, where classes appear in many scene contexts, Cityscapes contains similar street scenes that cover almost all 19 categories. The test split has 500 images.
Mapillary Vistats [60] is an urban street scene-centric dataset with a high-level hierarchical struc- ture, having 6 root-level categories subdivided into 37 supercategories and finally 66 cate- gories. Unlike Cityscapes and KITTI-STEP, street scenes are captured from various envi- ronments worldwide, including several countries, weather conditions, and seasons. aims to provide a diverse set of street scenes. The validation split has 2, 000 images.
KITTI-STEP [89], KITTI-SS [1] are datasets for urban scene understanding, instance detection, and object tracking. They have the same categories as Cityscapes and the same hierarchical structure. There are 2, 981 validation frames of KITTI-STEP, 200 test images of KITTI-SS.
21

---

Pascal-Part [15] is an extension of the PascalVOC2010 [27] dataset, designed specifically for fine- grained annotations of objects. It is part-centric dataset with a low-level hierarchical structure. It contains 20 object classes, each subdivided into low-level parts (i.e., head, left/right-eye, torso, left/right-amm, etc., for category person) for a total of 198 distinet part classes and a background category. The dataset contains 10, 103 images.
PartImageNet [35] is a part-centric dataset with a low-level hierarchical structure designed for fine-grained part segmentation. It extends the ImageNet dataset by providing detailed part annotations for subset of the images. It has 11 object supercategories and part su- percategories. PartImagenet-155 [35] arranges the annotation by ImageNet categories, counting 158 object classes and total of 597 part categories. The validation set contains total of 2, 957 images.
Normalised Muhigranular C Covering
Image
Greand tnrtk Sy
Predidiin 7,
Prodiction 72
Preficionn
Prdddtion 7,
High spoce eampless
Low scace examples
Groand trath regiass
pondictel Imaage
afwer Limen
Hig Hightrom
Inte-comm madch
Figure 7: Normalised Multigranular Covering (NMCovering) examples. For each available ground truth categorical region R in the semantic map Syt (left), we evaluate the overlap with the unrolled segments R' in the predicted region tree, c.g. Ti. The yellow labels indicate the maximum IoU matching correspondence between the ground truth and the prediction. Green line borders indicate high-score matching and red line borders indicate low-score matching. We propose two high-scoring predictions (centre) and two low-scoring (right). The total NMCovering is the average sum of the matching scores, as defined in Equation (3). The NMCovering metric evaluates the conularity-indepentee performance of the semantic segmentation model. The absence of correct semantic regions in T3 and T4 yields low score matches; see plate C' in T3 and plate B in T4.
D.2 Discussion About The Metrics
We average the metrics over each image in the dataset, ensuring comprehensive assessment across varying image contexts. In the hicrarchical scenario, the score gives equal importance to all levels, recognising the significance of coarse and fine-graines segmentation. This approach reflects the nuanced structure of hierarchical data, where higher and lower granularity levels provide comple- mentary insights.
The maximum overlap heuristics we use do not enforce exclusive matching. We intentionally choose this method to accommodate scenarios where regions in subsequent hierarchical levels overlap. For instance, in an image of human hands, the coarse category person may overlap with the finer cate- gory hand. An exclusive matching strategy might misinterpret this overlap, leading to an inaccurate assessment of segmentation performance. Our approach acknowledges such overlaps, providing a more realistic evaluation.
Additionally, the granularity of ground-truth annotations often limited. To address this, our eval- uation process disregards predictions that do not best match any annotated object, treating them as neither true positives nor false positives. This avoids penalising the model for predicting more de- tailed segments than the available annotations. Moreover, this approach permits the evaluation of the model according to standard category micro and macro-averaged segmentation metrics [56] such as the micro pixel Accuracy (pAcc) and the macro mean pixel Accurucy (mAcc), the per-class Inter- section over Union (ToU) and the relative maero mean IoU (mIoU), and micro frequency weighted loU (floU).
22

---

Normalised Hitrarchical Covering
Ground trath
Pradition
tieage-wiighod lipartlte aph
wiggt--weiggnn computation
(A & auaching
moll)
R5
HON, (*",,
R3
Good Hesage wrigte If TaM IntRa
DI (f, mancting mokgh in (Mg mOl t a.l treegeweigh (r Tie (PAPU)
moc noktiing
cxrnett treege vrree laasge Sateos
Ineage
Figure 8: Normalised Hierarchical Covering (NHCovering) computation example. Given the semantic tree ge (left), for each available ground truth categorical region R. we evaluate the overlap with the unrolled segments in the predicted region tree T. We consider one low-score lineage prediction edge (R', R24) and one high-score (R2 R2y). The yellow labels indicate the maximum IoU matching correspondence between the ground truth and the predicted regions. Green and red arrows indicate correct and wrong lineage prediction, respectively. The total NHCovering is the sum of the matching scores weighted by the ratio of correct lineages, as reported in Equation (4). The NHCovering metric assesses the granularity and crrarchy-independent performance of the semantic segmentation model. Examples of lineage-weight computation are reported for the E and D matching, on the right, using the operators (--) and (),-) defined in Section 4.1.
Interestingly, the NMCovering metric define an upper bound for the NHCovering score with appropriate modifications. Specifically, we find that NHCovering(T + Tat) ) < NMCovering(TT + T.t). Equality between these metries would indicate optimal model performance in terms of hier- archical inclusion, suggesting that the model not only segments accurately but also respects the hierarchical structure of the ground truth. Figures 7 and 8 offers finer insight into the metrics pur- pose.
These metrics provide robust framework for evaluating hierarchical segmentation models, balanc- ing granularity and hierarchical accuracy while accounting for the inherent complexities in real- world image data.
D.3 Quantitative Results
Our hierarchical semantic segmentation algorithm demonstrates strong performance across multiple datasets and hierarchical segmentation tasks, effectively capturing meaningful semantic structures at various levels of granularity.
Table showcases the comparative strength of our method, achieving high NMCovering scores against other low-level pixel hierarchical clustering algorithms. With Amax 0.6, our approach effectively segments the validation set into hierarchical clusters that closely align with ground-truth structures, indicating robustness in preserving semantic hierarchies.
Table 8 further illustrate our algorithm's adaptability in aerial scene segmentation, achieving notable NM NMCovering scores on both train sets. Using DINO-ViT-B8 features with Amax 0.9, the algo- rithm accurately segments six primary categories, confirming its applicability to complex geospatial datasets where hierarchical segmentation is critical.
Tables 9 and 10 highlight our model's proficiency in urban scene segmentation, achieving high NHCovering and mloU scores across 19 categories and seven supercategories. Notably, the use of hierarchical labels in Table 9 and detailed category IoUs in Table 10 show the model's capability to distinguish fine-grain fine-grained features within broader urban contexts. This performance suggests our approach can effectively capture semantic structures across varying levels of granularity, making well-suited for dynamic urban environments.
Table 13 is challenging benchmark with its extensive hierarchy of 'thing' and 'stuff' categories, to- talling 182 classes and 27 supercategories. Our algorithm achieves competitive performance across
23

---

both high-level supercategories and fine-grained categories, achieving strong IoU scores across each subset. This indicates that the algorithm effectively balances both coarse and fine semantic segmen- tation layers, enabling nuanced representation across diverse objects and materials.
In Table 11, focused Conditional Random Field (CRF) post-processing. our method shows that including CRF enhances segmentation accuracy across various datasets, validating its role in refining boundaries for complex regions. Additionally, comparisons with non-hierarchical spectral cluster- ing methods Table 12 underscore our approach's advantage in multi-level segmentation, achiev- ing higher NMCovering scores and consistent performance even without the need for CRF post- processing.
Table 7: Boundary potential vs. semantic smoothness. Comparison among hierarchical clustering algorithms in terms of NMCovering on PascalVOC2012 val set for Amaz 0.6.
154
254
144
400
44
144
314
280
26
116
01
Table 8: Hierarchical semantic segmentation on Potsdam and Vaihingen train sets. We use DINO-ViT-B8 [11] features and Xmaz 0.9. The two datasets have six categories. Segmentation performances are computed using NMCovering for ground truth masks exclusive matching.
Dataset
roads
baildings
vegetation
tree
car
clutter
mloU
pAee
mAo:
[oU
NHCowring
Polsdam
68.3
76.1
61.3
53.4
16.9
47.3
39.0
834
53.2
65.0
37.9
Vaihingen
56.7
43.3
76.8
73.9
58.1
53.9
Table 9: Hierarchical semantic segmentation Cityscapes and KITTI-STEP val sets and KITTI-SS train set. We use DINO-ViT-BS [11] features and Amar = 0.8. The three datasets have 19 valid categories from the Cityscapes dataset divided into seven supercategories. Segmentation performances are computed using NHCovering for ground truth masks exclusive matching.
22T
245
75
75.
796
315
613
b:kbyy
regardes
maseeds
200
325
766
39
Table 10: Hierarchical semantic segmentation on Cityscapes and KITTI-STEP val sets and KITTI-SS train set. We use DINO-ViT-B8 [11] features and Amar = 0.8. The three datasets have 19 valid categories from the Cityscapes dataset. Segmentation performances are computed using NHCovering for exclusive matching of predictions with ground truth masks. From the second column, we show the relative category IoU, Last four columns show mean IoU (mloU), frequency weighted IoU (floU), pixel accuracy (pAcc) and mean accuracy (mAcc).
RGU
2MC
RAR
051
113
KITTEA
16.9
411
714
617
Table 11: CRF ablation. We use maximum overlap for ground-truth category matching.
Dataset (mloU)
w/o CRF
w CRF
Cityscapes
48.8
$1.0
STET
$1.2
53.4
Mapillary Vistas
47.6
48.5
Potsdam
58.9
63.2
Table 12: Recursive vs. simultaneous PascalVOC2012 val set. Comparison between deep recursive (Ours) and simultaneous spectral clustering (Melas-Kyrizzi et al. [58]) for m = [4, 8, 16) using maximum overlap for category matching in each image. All the experiments extracted features with DINO-VIT-S8 [11], without CRF The other parameters are defaulted in Section 4. Notice that for simultancous clustering the NMCovering equals the NFCovering [44].
pre-
Motled
arttee
Morce
Meep
m.he
[S0]
244
.13
21.6
25
361
25.4
465
31.
455
153
454
432
415
212
45.7
353
216
435
455
676
186
X4
455
26.3
46.3
221
788
262
661
511
464
341
513
633
21
24
524
lis
MB
85
ma
184
361
101
16
N6
184
713
45A
463
68
201
116
124
184
151
764
465
357
24

---

Table 13: Hierarchical semantic segmentation on the COCO-Stuff val set. We use DINO-ViT- B8 [11] features and Amaz 0.6. COCO-Stuff dataset has 91 'thing' categories (inherited from MSCOCO), 91 'stuff" categories and 27 supercategories. Segmentation performances are com- puted using NHCovering for exclusive matching of predictions with ground truth masks. The rows show the hierarchical structure of COCO-Stuff. The first column shows the separation between things/stuff. The second column shows supercategory labels (Coarse Tags), the third column shows the relative supercategory IoU (IoU9) when considering all supercategories together, and the fourth column considers 12 things supercategories only, and the fifth column considers 15 stuff supercat- egories only. Sixth column shows leaf labels (Fine Tags), seventh column shows relative category IoU (IoU) when considering all categories, the eighth column considers 91 thing categories only and the ninth column considers 91 stuff categories only. Last row shows mean IoU (mloU), frequency weighted ToU (IloU), pixel accuracy (pAcc), and mean accuracy (mAcc) for each experiment. Here, accuracy values reported in the decimal range [0, 1].
Set
Tigs
Tip
0665
3et
Tays
Seaf7
Day
SX21-
oedy
Tacs
caly
Brcydo
0.41
0.5
0152
0.43
6607
1100
0.15
0.31
0.76
BU77
0.35
0.47
0.25
6.0
hour
B1.55
0125
0321
0,94
1662
cadiion
padkigg paior
lagu-igh
0.64
D.67
500
01.5
ted
01.5
0.5
1225
676
dog
0.75
6770
piace
016
0.7
0.75
0.75
0174
606
0.75
0.79
b:00gr
stralc
6.75
balkiy
0.66
0/65
1120
bekpw
0113
0.12
01:6
0.5
0.48
0.5
cvcabous
-boo
30%
30%
2014
Aodomat
0-6
6.5
0115
Ausiao
0.54
0.54
Eghh
0.36
0.55
0.25
sholl
qven
0.53
036
0.37
0.37
leaced Iuu
0.1
Fioe
0.56
0.5
<balbaol
6/13
8:70
30%
S0A
6/22
0175
883
Piile
00.7
0.34
tick
01.3
Eecrotafii
069
0.00
0.13
Ever
0.89
focreses
072
0.74
Ine-weed
colleg
extrg-ode
1044
1000
0.07
Socd
0.24
0.57
0.51
0.55
0033
0.66
0.64
dkeat
0.30
0.50
clai
persd plat
8/43
0.5
0.90
fanstace
0.9
dising
NIN
10%
SON
Jok.
No.
0,9
0A0
doe
NDN
0.53
030
steed
6.11
054
81
063
046
wikmoose
0.51
675
apliase
0.65
1066
teaner
0.25
0.56
2030
0063
0A0
Maxier
3.1
3.7
vulibest
(150
0.5
dlakk
0.
villeder
11:00
0.56
indoes
0.99
0:61
kolds
0.40
0.57
sall
vall-diee
1199
6071
11:17
1134
004
11:5
8:1
mikl
FG1
40%
24m
11:6
0.55
100
1054
1057
1230c
102
333
850
632
25

---

D.4 Qualitative Results
Figure 9: Qualitative results on PascalVOC2012. Random sampling from subset of our results, refined with CRF, having NMCovering greater than 70%. We show predicted subtrees (right) over- lapping with semantic masks (left). Heatmap colours encode leaves' distance in the subtrees.
26

---

Figure 10: Qualitative results on PartImageNee. Random sampling from subset of our results, refined with CRF, having NHCovering greater than 70%. The left column shows the ground truth part masks. The second to fifth column shows the predicted regions for each tree depth.
27

---

Figure 11: Qualitative results on PartImageNet. Random sampling from a subset of our results, refined with CRF, having NHCovering lower than 20%. The image shows failures in identifying very small parts. The left column shows the ground truth part masks. The second to fifth column shows the predicted regions for each tree depth. The prediction colour code does not reflect the ground truth one.
28

---

Figure 12: Qualitative results PoScalVOC2012. Random sampling from subset of our results, refined with CRF, having NMCovering greater than 70%. We assign unsupervised masks to the best overlapping classes.
29

---

Chfta
Figure 13: Qualitative results on COCO-Stuff. Random sampling from a subset of our results, refined with CRF, with NMCovering greater than 60%. We assign unsupervised masks the best overlapping classes.
30

---

vattiign
ratrrydh
Figure 14: Qualitative results on Cityscapes. Random sampling from subset of our results, refind with CRF, with NMCovering greater than 40%. We assign unsupervised masks to the best overlapping classes.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We introduce and explain the reasons for the new problem setting in Sec- tion 3 and our new metric in Section 4.1. The task also defines new downstream task for SSL,, which does not require additional training or prior, and reports some baselines in Table 5. We introduce our algebraic method for image pixel parsing via semantic re- gions tree in Section 3.1. In the same section, we define our smoothness criteria for deep features graph partitioning and our method for dynamically establishing connected compo- nents. In Tables and 2, we conduct several experiments to validate the robustness of our algorithm on different datasets. In Tables and 6, we report ablation experiments to assess the importance each algorithm component. In Table 3, we compare our results with dif- ferent semantic segmentation supervision strategies to benchmark the segmentation quality our approach; at the same time, we demonstrate that the proposed hierarchical image parsing effectively found visual semantic concepts in the images of dataset, whether they are object or scene centric, see Table 1, and whole or part centric, see Tables and 6b. Further experiments in Table 4 demonstrate the effectiveness of the algorithm in capturing semantic hierarchical relationships and an improvement over previous traditional hierarchi- cal models used nowadays in some unsupervised semantic segmentation SOTA to drive the optimization. We hope our findings may improve research in this direction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Section 5.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
32

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We refer to theorem which are fully reported and referred.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Ys]]
Justification: As stated in Section 4, to have full reproducibility. we adopt publicly available deep network checkpoints and do not perform any retraining. We evaluate our algorithm on publicly available datasets and use full validation sets. Our algorithm is deeply described in Section 3. and our code shown in the appendix, Algorithm 1. The used backbone, the superpixel clustering method, the kmin. Pmoz and Amaz values are the variables needed to reproduce the results. We clearly state their values in Section 4 and table 6. Implementation details beyond the standard algorithm are reported in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, deseribing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in
33

---

the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (c.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provided code for reproducing experiments in Table in the supplemen- tary material. We will release the full code upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines patttss//niis.. cc/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips... //tips.cc/ppppppe cttpsccccpbbbcicc /eaii//uuuiieee gewgee/iiaeeeeeee Cooeeubmiiiieeeeeo ssi ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: stated in Section 4, we evaluate our algorithm on publicly available datasets and use full validation sets only; Appendix D further specifies the name of the used sets for each specific dataset. The used backbone, the superpixel clustering method,
the Kmin- Pmoz and Amar values are the variables needed reproduce the results. We
34

---

clearly state their values in Section 4 and table 6. Implementation details beyond the stan- dard algorithm are reported in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
The paper provides comprehensive statistical information for the experiments. Specifically, we assume Gaussian error (and run time) as stated in Section 4.2, and we re- port mean and standard deviation values in Table 3 and Tables 6a and 6c. While in Tables 6a and 6c, we report such values to assess the behaviour of the algorithm with respect to its base components, in Section 4.2, we perform 4 experiments ensure the reproducibility and statistical validity of the experiments with different random seed initialization. How- ever, not all experiments report such statistical information, especially the ones in Tables 1, 2, 4, 5 and 6b, for two main reasons. The first is that typically, in the standard practices in the field of semantic segmentation, value for evaluation metrics such as the mean Intersection over Union (mIoU); it is ex- tremely rare the opposite. The second reason that our newly introduced metrics typically require more time for evaluation with respect to standard ToU. Indeed, for instance, the NHCovering searches for the leaves matching between two trees; typically, the predicted tree counts many leaves. Hence, multiple restarts make the evaluation process extremely long.
Justification:
common report single percentage mean
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
35

---

We specified the compute workers and the memory used in Appendix D to run our experiments. The time of execution depends on the parameters used and is discussed in Section 4.3 and Table 6.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: pttrps:/nneeee http///eerrrppppeee httpaappp.cpppullpcpeeee httppbliic/thiiccct.eeeeeeeeeeee
Answer: [Yes]
The research did not involve human participants (but the authors). All datasets used are publicly available. The authors do not envision harmful consequences of the work and no violations in any of the points listed in the NeurIPS Code of Ethies.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This is relevant question. As we have written, the case of annotations, there is always discrimination due to the annotator's 's subjective prejudice or the dataset's s design. the case of unsupervised segmentation, in principle, there no prejudice, but we cannot know if it can lead to some other form of prejudice. However, the most risky factor is the possibility the algorithm discloses of running it over massive set of raw images (not a curated dataset) and profiting from that. Also, it shares the risk and bias of all SSL. models and the unsupervised segmentation models. For example, the enormous amount of energy to run it over hundreds of thousands of raw images..
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups). privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
36

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Assets' owners are explicitly mentioned as reference entries.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, haperswithcode com/ dataseta has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: [NA]
37

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research
with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "yoqGjjyPET", "reviewer": "Reviewer_oEkj", "summary": "The submission presents a way to get hierarchical segmentations from the features extracted by an unsupervised semantic segmentation model. It builds a graph representation from the features or \"codes\" from the network. Spectral clustering is computed on this graph, followed by recursively partitioning the clusters until certain stopping conditions are met (for which the partition won't be further subdivided). It also proposes new evaluation metrics for evaluating a hierarchical segmentation against ground-truth pixel labels.", "questions": "1. Is there some property of the proposed method that limits it to using features/codes from the self-supervised and unsupervised models described in section 2, such as DINO, STEGO and Smooseg? Or could it also be applied to codes from any arbitrary model that extracts dense image segmentation features?\n2. What's the motivation for the specifics of stopping criterion #3? As in, it seems quite intuitive to look at the eigenvalues and the \"smoothness\" of the labelling, but why a fixed threshold? Is there any relationship to the use of the eigengap as a measure of the number of clusters?\n3. Was ablating the CRF boundary sharpening also looked at for other datasets, such as Cityscapes and Mapillary Vistas?", "limitations": "Limitations seem clear from the authors' own description. One limitation that might follow from (iii) is that the method couldn't discover sub-parts not learned by the original feature extractor training: for example if the pixel features/codes don't differentiate a given part from its surrounding object.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "i) Variable levels of hierarchy, adaptive to the image and object being segmented.\n\nThe recursive partitioning will keep dividing the partitions into sub-partitions until certain stopping criteria are met, as described at the end of Section 3.1. A key choice is to look at the eigenvalues of the graph laplacian, to get a measure of the how well the region can be divided. So the method is seeking to find some \"natural\" number of levels of hierarchy in the image and its objects, without having to assume a pre-defined set of part-object relations or depth of the tree of these relations.\n\nii) Consistently, across multiple experiments, ablates the CRF \"boundary sharpening\" post-processing.\n\nThis kind of post-processing is an important thing to ablate.\n\niii) In experiments on pre-processing, in Table 6, pays attention to computation cost requirements.\n\nAlso runs multiple trials to get error bars on timing.", "weaknesses": "iv) Features are frozen.\n\nFrom what I can tell, the hierarchy found by this method doesn't, and isn't meant to, play a role in the training of the feature extractor. This therefore seems likely to have a more limited impact than some related work, such as [42, 88]. Since the feature extractor could also be used as a foundation for other segmentation or vision tasks.\n\nv) Reliance on superpixel pre-processing. This is a practical choice, but it would likely limit the method at the finest levels of the hierarchy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer  **oEkj**,\n\nThank you for your interesting comments and for allowing us to review some relevant points.\n\n- Answer to Q1\n\nTable R1, attached below, reports experiments ablating features extracted with different pre-training strategies, namely self-supervised [3,4,5,6] supervised classification [1], natural language supervision [2]) and backbone architectures. It extends Table 5 on page 8 of the main paper. The ablations show no apparent limit to applying our method to other deep feature extractors. When applying feature extractors, a relevant aspect is the metric used to estimate similarity among extracted features.\n\n- Answer to Q2.1\n\nIn our approach, *smoothness* is a core principle that applies to the deep semantic representation of images, each with different primitive designs (tightly connected semantic components). $\\\\lambda_{max}$ provides a means to discern the primitives. As perturbation decreases beyond the upper bound given in Theorem 1, a large eigenvalue (< 1), in principle, approaches a steady state, hence a primitive. Table 6(c), page 9, displays ablation experiments on $\\\\lambda_{max}$ (likewise $p_{max})$ at varying thresholds, showing its role.\n\n- Answer to Q2.2\n\nExactly as you say, indeed. Theorem 1, as shown in Appendix A, establishes an upper bound on the subspace size that pushes W and W' away, according to the eigengap size between the $k$-th and $k+1$-th eigenvalues. Figure 3, in Appendix A, illustrates that the size of this subspace accounts for the connected components of the graph. Hence, as you noted, the eigengap is a guide for measuring the number of clusters.\n\n- Answer to Q3\n\nTable R2, attached below, reports ablation results on the CRF applied to some datasets not mentioned in Tables 3 and 4 on page 8 of the main document.\n\nThanks again for your questions; if you think our answers are accurate, we can improve our manuscript with your suggested revisions.\n \n$$\n\\\\small\n\\\\begin{array}{c}\n\\\\text{Table R1: \\\\textbf{Granularity-agnostic segmentation evaluation on the PascalVOC2012 \\\\textit{val} set. We used a maximum overlap heuristic for category matching in each image.}}\n\\\\\\\\\n\\\\text{\\\\textbf{We report the $\\\\textrm{IoU}$ category for each experiment with micro and macro averaged scores and the $\\\\textrm{NMCovering}$. We also include results for other pre-training strategies.}}\n\\\\\\\\[1em]\n\\\\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\n\\\\hline\n\\\\text{Backbone} & \\\\text{bkgd} & \\\\text{airplane} & \\\\text{bicycle} & \\\\text{bird} & \\\\text{boat} & \\\\text{bottle} & \\\\text{bus} & \\\\text{car} & \\\\text{cat} & \\\\text{chair} & \\\\text{cow} & \\\\text{d. table} & \\\\text{dog} & \\\\text{horse} & \\\\text{bike} & \\\\text{person} & \\\\text{p. plant} & \\\\text{sheep} & \\\\text{couch} & \\\\text{train} & \\\\text{tv} & \\\\textrm{mIoU} & \\\\textrm{pAcc} & \\\\textrm{mAcc} & \\\\textrm{fIoU} & \\\\textrm{NMCovering} \\\\\\\\\n\\\\hline\n\\\\text{ViT-B8} \\\\;[1] & 63.9 & 58.5 & 40.1 & 60.5 & 58.0 & 59.7 & 74.1 & 68.6 & 68.8 & 49.7 & 67.5 & 52.0 & 65.6 & 68.6 & 58.5 & 60.5 & 58.1 & 66.5 & 62.4 & 64.2 & 52.4 & 60.9 & 69.8 & 75.1 & 63.6 & 60.8 \\\\\\\\\n\\\\text{CLIP-ViT-B16} \\\\; [2] & 74.4 & 73.0 & 52.2 & 82.0 & 71.2 & 66.5 & 76.5 & 84.0 & 87.4 & 66.4 & 86.3 & 59.1 & 83.2 & 80.3 & 75.0 & 76.1 & 70.0 & 85.5 & 79.2 & 70.5 & 63.3 & 74.4 & 79.5 & 84.0 & 75.1 & 74.0 \\\\\\\\\n\\\\text{MAE-ViT-B16} \\\\;[3] & 66.2 & 81.4 & 54.6 & 85.8 & 73.4 & 71.4 & 82.4 & 80.6 & 83.8 & 64.8 & 85.1 & 66.8 & 83.8 & 81.4 & 74.6 & 72.6 & 66.5 & 87.3 & 77.0 & 76.2 & 68.7 & 75.4 & 73.5 & 85.9 & 69.1 & 70.0 \\\\\\\\\n\\\\text{MOCOv3-ViT-B16} \\\\;[4] & 72.2 & 82.6 & \\\\textbf{57.2} & 83.0 & 74.4 & 69.9 & 78.7 & 76.1 & 81.8 & 59.0 & 85.7 & 66.7 & 80.3 & 77.2 & 72.3 & 70.6 & 60.2 & 86.4 & 77.6 & 76.4 & 61.8 & 73.8 & 78.1 & 84.9 & 73.0 & 71.1 \\\\\\\\\n\\\\text{DINO-ResNet-50} \\\\;[5] & 67.2 & 65.7 & 47.6 & 70.2 & 58.8 & 49.8 & 66.8 & 56.6 & 73.9 & 46.8 & 75.6 & 47.1 & 70.3 & 71.6 & 60.7 & 55.2 & 52.6 & 77.5 & 59.5 & 63.7 & 39.2 & 60.8 & 73.3 & 76.0 & 65.7 & 61.9 \\\\\\\\\n\\\\text{DINO-ViT-S8} \\\\;[5] & 69.7 & 83.1 & 51.7 & 85.8 & 75.2 & 70.2 & 84.0 & \\\\textbf{82.0} & 86.7 & 67.1 & 85.8 & 66.3 & 85.8 & 80.0 & 76.5 & 73.5 & 66.3 & 86.4 & 81.3 & 75.9 & 66.9 & 76.2 & 76.8 & 85.6 & 72.0 & 72.5 \\\\\\\\\n\\\\text{DINO-ViT-B8} \\\\;[5] & 70.6 & \\\\textbf{87.0} & 57.1 & \\\\textbf{91.0} & \\\\textbf{77.1} & 74.3 & 83.7 & 80.0 & 88.1 & 67.5 & 86.2 & 65.2 & 85.5 & \\\\textbf{81.2} & 78.6 & 75.0 & 66.2 & \\\\textbf{88.9} & \\\\textbf{83.5} & 80.0 & 67.6 & 77.8 & 77.4 & 86.0 & 73.0 & 74.0 \\\\\\\\\n\\\\text{DINOv2-ViT-B14-R} \\\\;[6] & \\\\textbf{76.9} & 73.4 & 51.0 & 82.1 & 72.4 & \\\\textbf{82.5} & \\\\textbf{85.6} & 81.1 & \\\\textbf{90.2} & \\\\textbf{71.2} & \\\\textbf{87.1} & \\\\textbf{68.8} & \\\\textbf{87.7} & 78.3 & \\\\textbf{79.2} & \\\\textbf{82.1} & \\\\textbf{70.8} & 84.7 & 82.9 & \\\\textbf{82.9} & \\\\textbf{68.8} & \\\\textbf{78.1} & \\\\textbf{82.6} & \\\\textbf{91.2} & \\\\textbf{78.1} & \\\\textbf{75.4} \\\\\\\\\n\\\\hline\n\\\\end{array}\n\\\\end{array}\n$$\n\n$$\n\\\\small\n\\\\begin{array}{c}\n\\\\text{Table R2: \\\\textbf{CRF ablation of our algorithm on different datasets using a maximum overlap heuristic for category matching.}} \\\\\\\\[1em]\n\\\\begin{array}{|l|c|c|}\n\\\\hline\n\\\\text{Dataset} (\\\\textrm{mIoU}) & \\text{w/o CRF} & \\text{w CRF} \\\\\\\\\n\\\\hline\n\\\\text{Cityscapes} & 48.8 & 51.0 \\\\\\\\\n\\\\text{KITTI-STEP} & 51.2 & 53.4 \\\\\\\\\n\\\\text{Mapillary Vistas} & 47.6 & 48.5 \\\\\\\\\n\\\\text{Potsdam} & 58.9 & 63.2 \\\\\\\\\n\\\\hline\n\\\\end{array}\n\\\\end{array}\n$$\n\n**References**\n\n[1]  Dosovitskiy, A., et al. (2020). An image is worth 16x16 words: Transformers for image recognition at scale.\n\n[2] Radford, A., et al. (2021). Learning transferable visual models from natural language supervision.\n\n[3]  He, K., et al. (2021). Masked Autoencoders Are Scalable Vision Learners.\n\n[4]  Chen, X., et al. (2021). MoCo v3: Self-Supervised Learning for Visual Representation.\n\n[5] Caron, M., et al. (2021). Emerging Properties in Self-Supervised Vision Transformers.\n\n[6] Darcet, T., et al. (2023). Vision Transformers Need Registers.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B6DVpkAtHu", "reviewer": "Reviewer_47JN", "summary": "The paper proposes a spectral-clustering approach to hierarchically segment an image, in an unsupervised fashion. The method starts from self-supervised features assigned to each pixel. Then, a recursive partitioning is obtained by minimizing a quadratic form for a given level of the hierarchy, and repeating the process until a stopping criterion is met. For faster computation, it is possible to start from superpixels. A Conditional Random Field can be applied on the boundaries to refine the prediction. \n\nThe core of the approach is the definition of a smoothness of function labelling on a graph, the minimization of which leads to a given level of the hierarchy. \n\nExperiments show that the method achieves state-of-the-art results on several datasets.", "questions": "- I do not understand why the Normalized cuts (or any other spectral method) would not lead to the same kind of results. Specifically, I would like an ablation experiment in which another spectral method is used, as in [56] for example, but with the same superpixels, same network, and similar other details. The question is then: is the minimization of the smooth function-labelling the important idea here, or some other component of the approach? I believe the difference should not be as high as it appears in the paper.", "limitations": "The authors state that their approach can be slow, but no timing is reported.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The idea is somehow simple, yet achieves remarkable results\n- There are numerous experiments to assess the quality of the results\n- Two new metrics are introduced, one granularity-agnostic, the other hierarchy-agnostic.", "weaknesses": "- The writing of the paper could have been simpler, and more to the point. I find that many sentences are convoluted, which makes it difficult to understand the description of the method. For example, I did not understand the method until I read the first paragraph of Appendix A. \n- At a high-level, the difference of this paper with papers like [56] is only the spectral clustering method used in the process. There are other differences, but they are minor in theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer **47JN**,\n\nThanks for the valuable comments and the interesting questions. \n\n- Answer to Q1.1\n\nAs you fairly suggest, we report in Table R3, attached below,  *\"an ablation experiment in which another spectral method is used, as in [56], ..,  with the same superpixels, network, and similar other details\"*.\n\n$$\n\\\\small\n\\\\begin{array}{c}\n\\\\text{Table R3: \\\\textbf{Segmentation evaluation on PascalVOC2012 \\\\textit{val} set between recursive (Ours) and simultaneous deep spectral clustering (Melas-Kyriazi et Al. [6]) methods for $m=\\\\{4,8,16\\\\}$ (superpixels) using a maximum}} \n\\\\\\\\\n\\\\text{ \\\\textbf{overlap heuristic for category matching in each image. All the experiments run on pre-extracted features with DINO-ViT-S8 [5] without CRF post-processing. The other parameters in our method are}} \n\\\\\\\\\n\\\\text{ \\\\textbf{set as default in Sec. $4$ on page $7$ of the main paper. For non-hierarchical spectral clustering methods, i.e. [6], the $\\\\textrm{NMCovering}$ equals the Normalised Foreground Covering ($\\\\textrm{NFCovering}$) [7]. }} \n\\\\\\\\[1em]\n\\\\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\n\\\\hline\n\\\\text{Method}&\\\\text{bkgd}&\\\\text{airplane}&\\\\text{bicycle}&\\\\text{bird}&\\\\text{boat}&\\\\text{bottle}&\\\\text{bus}&\\\\text{car}&\\\\text{cat}&\\\\text{chair}&\\\\text{cow}&\\\\text{d.table}&\\\\text{dog}&\\\\text{horse}&\\\\text{bike}&\\\\text{person}&\\\\text{p.plant}&\\\\text{sheep}&\\\\text{couch}&\\\\text{train}&\\\\text{tv}&\\\\textrm{mIoU}&\\\\textrm{pAcc}&\\\\textrm{mAcc}&\\\\textrm{fIoU}&\\\\textrm{NMCovering}\\\\\\\\\n\\\\hline\n\\\\hline\n[6]\\\\;(m=4)&39.4&47.7&23.6&35.6&36.1&26.4&46.5&31.6&45.6&25.3&45.1&43.2&41.8&37.2&45.7&35.5&21.0&42.5&45.5&47.0&20.6&36.4&45.5&60.0&39.3&40.7\\\\\\\\\n\\\\text{Ours}\\\\;(m=4)&54.8&34.4&13.0&23.5&25.6&20.7&50.6&25.0&48.8&18.8&40.3&29.0&36.5&40.1&39.1&31.8&15.2&34.9&36.8&41.1&18.3&32.3&62.5&68.4&49.4&44.8\\\\\\\\\n\\\\hline\n[6]\\\\;(m=8)&27.8&44.2&32.1&42.3&39.6&26.2&29.9&31.9&34.5&37.0&35.3&37.0&35.5&37.7&39.8&36.5&30.7&34.2&40.2&35.1&39.9&35.5&31.5&42.6&29.9&36.4\\\\\\\\\n\\\\text{Ours}\\\\;(m=8)&61.1&51.0&22.1&42.0&42.6&34.8&69.5&46.6&70.0&29.3&64.1&41.3&58.4&53.1&56.1&43.6&24.1&57.7&54.5&63.3&34.8&48.6&69.1&76.4&58.5&55.5\\\\\\\\\n\\\\hline\n[6]\\\\;(m=16)&16.0&28.7&33.0&29.3&30.9&23.6&17.9&24.0&21.4&33.5&22.2&28.1&22.0&24.3&25.1&27.5&31.0&23.5&29.1&21.2&34.2&26.0&19.0&27.8&18.5&27.7\\\\\\\\\n\\\\text{Ours}\\\\;(m=16)&65.2&66.8&33.7&58.7&51.9&49.8&76.1&58.8&78.1&39.4&70.0&50.8&72.2&67.3&65.2&56.9&32.9&64.3&60.2&71.6&42.5&58.6&72.1&78.9&64.3&62.2\\\\\\\\\n\\\\hline\n\\\\hline\n\\\\text{Ours}\\\\;(m=100)&69.7&83.1&51.7&85.8&75.2&70.2&84.0&82.0&86.7&67.1&85.8&66.3&85.8&80.0&76.5&73.5&66.3&86.4&81.3&75.9&66.9&76.2&76.8&85.6&72.0&72.5\\\\\\\\\n\\\\hline\n\\\\end{array}\n\\\\end{array}\n$$\n\nTable R3, comparing our approach to [56], shows that the fixed number of categories prior and fixed granularity prior are incompatible with the hierarchical organisation of semantic concepts and do not progress with finer superpixels (over clustering).\n\n- Answer to Q1.2\n\nAs you note, minimising *smooth function-labelling* is a central idea; thanks for highlighting that.\n\nHowever, we remark that it operates via the eigengap, which is used to estimate the number of clusters at each tier of the recursion in an utterly general setting, namely for quite diverse dataset semantic hierarchies.\nAs a consequence:\n\n1) The number of clusters is *estimated*, exploiting perturbation and the eigengap upper bound (see Theorem 1, in Appendix A); that is, the *number of clusters* is *not defined a priori*, as opposed to other approaches resorting to spectral methods too.\n\n2) Recursive partitioning estimates the number of clusters at each tier, accounting for a granularity *peculiar* to the variable number of parts in each dataset.\n\n3) Finally, the novel metrics account for the hierarchical structure of the many components discovered.\n\nPerhaps these contributions to flexibility and compliance to the diverse hierarchies make a difference.\n\nTable R4 reports running time ($sec/iter$) comparisons among superpixel strategies (see Tables 6a and 6c, page 9 of the main document).\n\n\\\\[\n\\\\small\n\\\\begin{array}{c}\n\\\\text{Table R4: \\\\textbf{Timing w.r.t NMCCovering (left table) and NHCcovering (right table)}} \\\\\\\\[1em]\n\\\\begin{array}{|l|c|c|c|}\n\\\\hline\n\\\\textrm{NMCCovering}&{k_{\\\\min}}&k_{\\\\min}&k_{min}=1\\\\\\\\\n\\\\textbf{Superpixel}\\\\;(m=100)&1&5&(\\\\text{sec/iter})\\\\\\\\\n\\\\hline\n\\\\textit{colour-space}&&&\\\\\\\\\n\\\\text{k-mean}\\,[1]&32.7&33.4&0.73\\\\pm0.14\\\\\\\\\n\\\\text{SLIC}\\,[2]&58.1&44.9&\\\\textbf{0.05}\\\\pm0.01\\\\\\\\\n\\\\text{quick-shift}\\,[3]&\\\\textbf{60.8}&\\\\textbf{58.0}&0.21\\\\pm0.12\\\\\\\\\n\\\\hline\n\\\\textit{SSL-latent-space}&&&\\\\\\\\\n\\\\text{k-mean}\\,[1]&62.9&58.1&\\\\textbf{0.34}\\\\pm0.19\\\\\\\\\n\\\\text{Spectral}\\,[4]&\\\\textbf{63.1}&\\\\textbf{59.9}&0.61\\\\pm0.11\\\\\\\\\n\\\\hline\n\\\\hline\n\\\\text{None}&65.7&64.9&0.84\\\\pm0.29\\\\\\\\\n\\\\hline\n\\\\end{array}\n\\\\begin{array}{|l|c|c|c|c|}\n\\\\hline\n\\\\textrm{NHCCovering}&{\\\\lambda_{\\\\max}}&{\\\\lambda_{\\\\max}}&{\\\\lambda_{\\\\max}}&\\\\lambda_{\\\\max}=0.5\\\\\\\\\np_{\\\\max}&0.5&0.8&\\\\text{None}&(\\\\text{sec/iter})\\\\\\\\\n\\\\hline\n50&36.9&41.1&41.4&0.49\\\\pm0.09\\\\\\\\\n80&39.5&42.9&43.1&0.65\\\\pm0.16\\\\\\\\\n\\\\text{None}&40.9&43.7&44.0&0.77\\\\pm0.23\\\\\\\\\n\\\\hline\n\\\\end{array}\n\\\\end{array}\n\\\\]\n\nThanks again for your effort; if you find these additions unambiguous and accurate, we add them to the manuscript.\n\n**References**\n\n[1] Lloyd, Stuart (1982). Least squares quantization in PCM. \n\n[2] Achanta, R., et Al. (2012). SLIC superpixels compared to state-of-the-art superpixel methods. \n\n[3] Vedaldi, A., et Al. (2008). Quick shift and kernel methods for mode seeking. \n\n[4] Ng, A., et Al. (2001). On spectral clustering: Analysis and an algorithm. \n\n[5] Caron, M., et Al. (2021). Emerging Properties in Self-Supervised Vision Transformers.\n\n[6] Melas-Kyriazi, et Al. (2022). Deep Spectral Methods: A Surprisingly Strong Baseline for Unsupervised Semantic  Segmentation and Localization.\n\n[7] Ke, T., et Al. (2022). Unsupervised Hierarchical Semantic Segmentation with Multiview Cosegmentation and Clustering Transformers.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xw54RdEzX7", "reviewer": "Reviewer_E2ZP", "summary": "This paper addresses the problem of unsupervised hierarchy-agnostic segmentation by treating it as a graph partitioning problem. Specifically, each node in the graph represents a part, while the weighted edges, measured by similarity scores, reflect the connections between parts. The graph is recursively partitioned until a stopping criterion is met. To facilitate the graph partitioning, superpixel segmentation is initially performed to construct the graph, and boundary sharpening is applied post-partitioning as a technique to improve segmentation results.\nThe paper also introduces two new metrics: Normalized Multigranular Covering and Normalized Hierarchical Covering, which ensure that both foreground and background instances, as well as hierarchical inclusion, are considered. Experiments conducted on popular benchmarks demonstrate the strong capability of the proposed method as an unsupervised segmentation approach.", "questions": "Please refer to the weaknesses.", "limitations": "Limitations and broader impact of the proposed method are discusses in the paper. No other discussions are must needed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The method proposed in this method is novel and well-motivated, with detailed derivation given in the supplementary.\n- The experimental results are strong and achieve significant improvement compared to prior arts.\n- The paper is overall well-written and the figures are clean and present the information well.\n- Code is provided to facilitate the reproduction of the results.", "weaknesses": "- The pre-trained DINOv2-ViT-B14-REG backbone is a very strong backbone and also a strong requirement when compared to other unsupervised segmentation model, which harms the fair comparison.\n- The newly introduced metrics would be more clear if they could come with an example to illustrate the computation process step by step.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer **E2ZP**,\n\nWe sincerely appreciate your evaluation and sharp comments. Your feedback is helpful in enhancing the quality and clarity of our work.\n\nAs you indicate, we will address the weaknesses.\n\n- Answer to *The pre-trained DINOv2-ViT-B14-REG backbone is a very strong backbone and also a strong requirement when compared to other unsupervised segmentation models, which harms the fair comparison.*\n\nBelow, we present Table R1, which details the ablation of the backbone architecture and the pre-training strategy used in our approach relative to the PascalVOC2012 dataset.\nOn the other hand, Table 5, on page 8 of the main paper, presents a backbone ablation on PascalVOC2012. Please notice likewise that we documented quantitative results using DINO-ViT-B8, a weaker backbone than DINOv2-ViT-B14-REG, on Cityscapes, KITTI, COCO-Stuff, and Potsdam in Tables 8, 9, 10, and 11, on pages 19, 20, and 21 of the Appendix. \n\n$$\n\\\\small\n\\\\begin{array}{c}\n\\\\text{Table R1: \\\\textbf{Granularity-agnostic segmentation evaluation on the PascalVOC2012 \\\\textit{val} set. We used a maximum overlap heuristic for category matching in each image. }}\n\\\\\\\\\n\\\\text{\\\\textbf{We report the $\\\\textrm{IoU}$ category for each experiment with micro and macro averaged scores and the $\\\\textrm{NMCovering}$. We also include results for other pre-training strategies.}}\n\\\\\\\\[1em]\n\\\\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\n\\\\hline\n\\\\text{Backbone} & \\\\text{bkgd} & \\\\text{airplane} & \\\\text{bicycle} & \\\\text{bird} & \\\\text{boat} & \\\\text{bottle} & \\\\text{bus} & \\\\text{car} & \\\\text{cat} & \\\\text{chair} & \\\\text{cow} & \\\\text{d. table} & \\\\text{dog} & \\\\text{horse} & \\\\text{bike} & \\\\text{person} & \\\\text{p. plant} & \\\\text{sheep} & \\\\text{couch} & \\\\text{train} & \\\\text{tv} & \\\\textrm{mIoU} & \\\\textrm{pAcc} & \\\\textrm{mAcc} & \\\\textrm{fIoU} & \\\\textrm{NMCovering} \\\\\\\\\n\\\\hline\n\\\\text{ViT-B8} \\\\;[1] & 63.9 & 58.5 & 40.1 & 60.5 & 58.0 & 59.7 & 74.1 & 68.6 & 68.8 & 49.7 & 67.5 & 52.0 & 65.6 & 68.6 & 58.5 & 60.5 & 58.1 & 66.5 & 62.4 & 64.2 & 52.4 & 60.9 & 69.8 & 75.1 & 63.6 & 60.8 \\\\\\\\\n\\\\text{CLIP-ViT-B16} \\\\; [2] & 74.4 & 73.0 & 52.2 & 82.0 & 71.2 & 66.5 & 76.5 & 84.0 & 87.4 & 66.4 & 86.3 & 59.1 & 83.2 & 80.3 & 75.0 & 76.1 & 70.0 & 85.5 & 79.2 & 70.5 & 63.3 & 74.4 & 79.5 & 84.0 & 75.1 & 74.0 \\\\\\\\\n\\\\text{MAE-ViT-B16} \\\\;[3] & 66.2 & 81.4 & 54.6 & 85.8 & 73.4 & 71.4 & 82.4 & 80.6 & 83.8 & 64.8 & 85.1 & 66.8 & 83.8 & 81.4 & 74.6 & 72.6 & 66.5 & 87.3 & 77.0 & 76.2 & 68.7 & 75.4 & 73.5 & 85.9 & 69.1 & 70.0 \\\\\\\\\n\\\\text{MOCOv3-ViT-B16} \\\\;[4] & 72.2 & 82.6 & \\\\textbf{57.2} & 83.0 & 74.4 & 69.9 & 78.7 & 76.1 & 81.8 & 59.0 & 85.7 & 66.7 & 80.3 & 77.2 & 72.3 & 70.6 & 60.2 & 86.4 & 77.6 & 76.4 & 61.8 & 73.8 & 78.1 & 84.9 & 73.0 & 71.1 \\\\\\\\\n\\\\text{DINO-ResNet-50} \\\\;[5] & 67.2 & 65.7 & 47.6 & 70.2 & 58.8 & 49.8 & 66.8 & 56.6 & 73.9 & 46.8 & 75.6 & 47.1 & 70.3 & 71.6 & 60.7 & 55.2 & 52.6 & 77.5 & 59.5 & 63.7 & 39.2 & 60.8 & 73.3 & 76.0 & 65.7 & 61.9 \\\\\\\\\n\\\\text{DINO-ViT-S8} \\\\;[5] & 69.7 & 83.1 & 51.7 & 85.8 & 75.2 & 70.2 & 84.0 & \\\\textbf{82.0} & 86.7 & 67.1 & 85.8 & 66.3 & 85.8 & 80.0 & 76.5 & 73.5 & 66.3 & 86.4 & 81.3 & 75.9 & 66.9 & 76.2 & 76.8 & 85.6 & 72.0 & 72.5 \\\\\\\\\n\\\\text{DINO-ViT-B8} \\\\;[5] & 70.6 & \\\\textbf{87.0} & 57.1 & \\\\textbf{91.0} & \\\\textbf{77.1} & 74.3 & 83.7 & 80.0 & 88.1 & 67.5 & 86.2 & 65.2 & 85.5 & \\\\textbf{81.2} & 78.6 & 75.0 & 66.2 & \\\\textbf{88.9} & \\\\textbf{83.5} & 80.0 & 67.6 & 77.8 & 77.4 & 86.0 & 73.0 & 74.0 \\\\\\\\\n\\\\text{DINOv2-ViT-B14-R} \\\\;[6] & \\\\textbf{76.9} & 73.4 & 51.0 & 82.1 & 72.4 & \\\\textbf{82.5} & \\\\textbf{85.6} & 81.1 & \\\\textbf{90.2} & \\\\textbf{71.2} & \\\\textbf{87.1} & \\\\textbf{68.8} & \\\\textbf{87.7} & 78.3 & \\\\textbf{79.2} & \\\\textbf{82.1} & \\\\textbf{70.8} & 84.7 & 82.9 & \\\\textbf{82.9} & \\\\textbf{68.8} & \\\\textbf{78.1} & \\\\textbf{82.6} & \\\\textbf{91.2} & \\\\textbf{78.1} & \\\\textbf{75.4} \\\\\\\\\n\\\\hline\n\\\\end{array}\n\\\\end{array}\n$$\n\n- Answer to *The newly introduced metrics would be more clear if they could come with an example to illustrate the computation process step by step*.\n\nFigures R1 and R2 in the above-attached PDF (see inside the frame *Author Rebuttal by Authors*) illustrate two examples of the computation process of the introduced metrics step by step: one for the NMCovering and the other for the NHCovering.  We hope the figures give a finer insight into their purpose.\n\nThanks again for your thoughtful comments. If you find the table and figures satisfactory, please let us know so we can add them to the manuscript.\n\n**References**\n\n[1]  Dosovitskiy, A., et al. (2020). An image is worth 16x16 words: Transformers for image recognition at scale.\n\n[2] Radford, A., et al. (2021). Learning transferable visual models from natural language supervision.\n\n[3]  He, K., et al. (2021). Masked Autoencoders Are Scalable Vision Learners.\n\n[4]  Chen, X., et al. (2021). MoCo v3: Self-Supervised Learning for Visual Representation.\n\n[5] Caron, M., et al. (2021). Emerging Properties in Self-Supervised Vision Transformers.\n\n[6] Darcet, T., et al. (2023). Vision Transformers Need Registers.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "it2ddyejsj", "reviewer": "Reviewer_Xo6d", "summary": "The paper presents a novel approach to unsupervised semantic image segmentation.  The authors introduce a novel algebraic methodology that constructs a hierarchy-agnostic semantic region tree, which dynamically identifies scene-conditioned primitives and creates a nuanced and unbiased segmentation of image pixels.\nKey contributions of the paper include:\n- A deep recursive spectral clustering method that maximizes an unbiased measure of total semantic similarity across multiple levels of semantic granularity.\n- The integration of this method with diverse self-supervised learning models to enhance flexibility and applicability in unsupervised segmentation tasks.\n- The introduction of new metrics, namely Normalized Multigranular Covering (NMCovering) and Normalized Hierarchical Covering (NHCovering), for estimating the quality of semantic segmentation at different levels of hierarchy.", "questions": "no", "limitations": "see weakness", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper is well-written. I like the figures in this paper.\n- The motivation is clear and the idea of recursive spectral clustering is novel and make-sense. \n- The paper introduces a unique algebraic approach to unsupervised semantic segmentation, offering a new perspective on hierarchical image parsing without predefined structures. \n- The novel metrics proposed for evaluating segmentation quality are innovative and practical.", "weaknesses": "- The proposed approach has a few critical hyperparameters (the minimum number of points in a partition $k_{min}$, a threshold $p_{max}$,   a maximum eigenvalue $\\lambda_{max}$) which if not properly set can degrade the performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer **Xo6d**,\n\nThanks for your comments and your critical remarks on the parameters.\n\nWe make some observations concerning them.\n\nYou note that the parameters require *being well set*. However:\n\n1) Table 6 (c) and Table 6 (a) on page 9 of the main paper show that $k_{min}$, $\\\\lambda_{max}$ and $p_{max}$ influence is limited, not affecting the performance significantly.  \n\n2) Parameters are helpful for *adapting* our general hierarchy-agnostic segmentation method to many datasets' semantic hierarchies, which are remarkably different. \n\nParameters are used within the recursive partitioning to cope with the rather distinct detail levels (or granularity) in each dataset, as commented on page 18, Appendix D1, about the different properties of each dataset in terms of their parts hierarchy (e.g. *scene centric*, *object-centric*).\n\n- $𝑘_{𝑚𝑖𝑛}$ sets the minimum number of points needed to define a partition. For example, in Pascal Parts, parts can be pretty tiny, like eyebrows, which is not the case in COCO-Stuff.\n\n- $𝑝_{𝑚𝑎𝑥}$ instantiates Theorem 1 upper-bound  (see Appendix A, page 15), according to the multiplicity at each level of a dataset latent semantic hierarchy — for example, the number of car details in PascalParts as opposed to CityScape, likewise the highly varying number of categories.\n\n- $\\\\lambda_{max}$  evaluates the conditions to define a primitive by looking for large eigenvalues beyond Theorem 1 upper-bound, namely for a non-changing state. It adapts to the specific elementary semantic of the dataset (e.g. COCO-stuff primitives as opposed to Imagenet Parts primitives).\n\nThese parameters, which are entirely general for datasets with essential differences in their semantic structure, can be refined by cross-validation.\n \nThanks again for highlighting your concerns about the parameters. If you consider the explanations helpful, we shall improve the manuscript accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their time, effort and valuable comments.

We are glad the reviewer found the idea "*somehow simple, yet achieves remarkable results*" (47JN); and that they found the method "*novel and well-motivated, with detailed derivation*" and "*achieves significant improvement compared to prior arts*" (E2ZP). The reviewers also found that "*the idea of recursive spectral clustering is novel*" and that "*the novel metric proposed are innovative and practical*" (Xo6d). The reviewers have also clearly appreciated that "*the method is seeking to find some 'natural' number of levels of hierarchy in the image and its objects, without having to assume a pre-defined set of part-object relations or depth of the tree of these relations*"(oEkj).

We hope our answers, equipped with tables and figures, add further insight and answer the reviewers' sharp questions.

Meta-review: This paper proposes unsupervised semantic segmentation by recursive spectral clustering.

It has received 2x weak accepts, 1x borderline accept, and 1x accept.  Authors have an extensive rebuttal with additional clarification and results.  Reviewers like the unsupervised algebraic approach, new metrics for estimating the quality of the semantic segmentation at different levels of the discovered hierarchy, and performance gains.  They also point out the limitations on frozen features, reliance on superpixels, minor technical innovation, unfair comparisons with stronger backbone features, hyper-parameter sensitivity, and convoluted writing.

The AC recommends acceptance based on the consensus.   Please take all the comments and rebuttal into account to improve the final version.

~~~~~~~~~~~~~~~~~~~~~~~~
Here are some extra comments from SAC. 
(1) The authors are suggested to pay much effort in the layout and font size of tables, where some results can be put into appendix. 
(2) Abstract, introduction, and related work can be trimmed. If necessary, the extensive discussion on related work can be also moved into appendix.
Decision: Accept (poster)