# Patch-Based Deep Unsupervised Image Segmentation using Graph Cuts

Isaac Wasserman
University of Pennsylvania
Philadelphia, Pennsylvania
<EMAIL_ADDRESS>Jeová Farias Sales Rocha Neto
Bowdoin College
Brunswick, Maine
<EMAIL_ADDRESS>
###### Abstract

Unsupervised image segmentation aims at grouping different semantic patterns
in an image without the use of human annotation. Similarly, image clustering
searches for groupings of images based on their semantic content without
supervision. Classically, both problems have captivated researchers as they
drew from sound mathematical concepts to produce concrete applications. With
the emergence of deep learning, the scientific community turned its attention
to complex neural network-based solvers that achieved impressive results in
those domains but rarely leveraged the advances made by classical methods. In
this work, we propose a patch-based unsupervised image segmentation strategy
that bridges advances in unsupervised feature extraction from deep clustering
methods with the algorithmic help of classical graph-based methods. We show
that a simple convolutional neural network, trained to classify image patches
and iteratively regularized using graph cuts, naturally leads to a state-of-
the-art fully-convolutional unsupervised pixel-level segmenter. Furthermore,
we demonstrate that this is the ideal setting for leveraging the patch-level
pairwise features generated by vision transformer models. Our results on real
image data demonstrate the effectiveness of our proposed methodology.

##  1 Introduction

Image segmentation has long been one of the main tasks in computer vision and
it has been widely applied in general image understanding or as a
preprocessing step for other tasks such as object detection. It aims at
corresponding each pixel in an image to a semantically relevant class, in such
a way that similar pixels are assigned to the same class. This problem finds
various industrial applications such as autonomous driving, medical image
analysis, video surveillance and virtual reality to name a few [32].

On the supervised front, deep learning approaches using Convolutional (CNN)
and Fully Convolutional Neural Networks (FCN) achieved unprecedented results
in image segmentation, as illustrated by the UNet [37] and DeepLab [13]
models. Recently, however, methods using transformer-based models, such as
Segformer[46], DETR [9] and DINO [11], are slowly outperforming established
CNN solutions. This has prompted the recent interest in deep models that
utilize image patches instead of their full-sized counterparts [41, 22],
leading some to postulate that patch representations are the main source of
the transformer’s success [42].

These accomplishments come, however, at the cost of long training schemes and
the need for larger amounts of annotated data, which hinder their application
in many domains where data can be expensive or scarce, such as in biology, or
astrophysics [47]. These issues can be resolved via the application of
unsupervised techniques instead. In this setting, one aims at creating a model
that automatically discovers semantically important visual features or groups
that characterize the various objects in a scene. Classically, this could be
approached via variational, statistical, and graphical methods, exemplified in
active contours [12], conditional random fields [27], and graph cuts [39, 7].
Within the deep learning literature, prominent advances were made in the field
of unsupervised deep image clustering [36], which eventually led to
developments in deep image segmentation techniques [25, 20, 30, 21, 44].

In this work, we introduce GraPL, an unsupervised image segmentation technique
that draws inspiration from the success of CNNs for imaging tasks, the
learning strategies of deep clustering methods, and the regularization power
of graph cut algorithms. Here, we alternate the training of a CNN classifier
on image patches and the minimization of a clustering energy via graph cuts.
To the best of our knowledge, this is the first attempt in both the deep
clustering and image segmentation literature to make use of graphs cuts to
solve a deep learning-based unsupervised task. We show that our zero-shot
approach detects visual segments in an image without onerous unsupervised
training on an entire image dataset, automatically finds a satisfactory number
of image segments, and easily translates the patch-level training to efficient
pixel-level inference. Furthermore, because of its structure, it also
naturally incorporates pretrained patch embeddings [11, 33], without relying
on them for the final product. Finally, we show that this simple approach
achieves state-of-the-art results in deep unsupervised image segmentation,
demonstrating the potential of graph cuts to improve other patch-based deep
segmentation algorithms. Specifically, we make the following main
contributions with our work:

  * •

We introduce GraPL, an unsupervised segmentation method that learns a fully
convolutional segmenter directly from the image’s patches, using an iterative
algorithm regularized by graph cuts.

  * •

We show that this framework naturally employs patch embeddings for pixel-level
segmentation without the need for postprocessing schemes such as CRF refining.

  * •

We demonstrate that GraPL is able to outperform the state-of-the-art in deep
unsupervised segmentation by iteratively training a small, low complexity CNN.

##  2 Related Work

###  2.1 Deep Clustering

With the advancements in deep supervised image classification techniques,
interest in deep architectures to solve unsupervised problems followed
naturally. This pursuit led to the task of partitioning image datasets into
clusters using deep representations without human supervision, inaugurating
the body of work which is now referred to as “deep clustering.” The interested
reader is referred to [36] for a comprehensive review on the available
approaches to deep clustering.

In GraPL, we treat image patches as individual images to be clustered as a
pretext task to train our segmenter and efficiently use graph cuts to impose
constraints on the patch clusters. To the best of our knowledge, our method is
the first to use MRF-based algorithms for clustering CNN-generated visual
features.

###  2.2 Deep Unsupervised Image Segmentation

As deep clustering aims to learn visual features and groupings without human
annotation via deep neural models, deep unsupervised image segmentation hopes
to use the same models to learn coherent and meaningful image regions without
the use of ground-truth labels. To do so, many methods explore strategies that
resemble those from deep clustering. Cho et al. [15] iteratively employs
$k$-means to cluster pixel-level features extracted from a network trained on
different photometrically and geometrically varying image views. The work in
[24] efficiently extends a mutual information-based deep clustering algorithm
to the pixel-level by recognizing that such a process can be achieved via
convolution operations. [23] computes pixel embeddings from a metric learning
network and segments each image using a spherical $k$-means clustering
algorithm.

In [25], the authors train an FCN with pseudo-labels generated by the same
network in a prior step. They attain reliable segmentations by proposing a
complex loss function that ensures the similarity among pixels in shared
segments, while encouraging their spacial continuity and limiting their total
count. Our method, while similarly training an FCN, works on patches and is
able to reinforce spacial continuity and low segment count via our graph cut
approach. Furthermore, due to its use of graph cuts, GraPL is able to
naturally incorporate pairwise patch relationships. Finally, while other
patch-based unsupervised solutions require a segmentation refinement stage
after a patch feature clustering step [21, 44, 43], we both discover and
instill patch knowledge interactively, without the need for postprocessing our
result.

###  2.3 Graph Cuts for Image Segmentation

Modeling image generation as a Markov random field (MRF) has a long history in
Computer Vision, dating its initial theoretical and algorithmic achievements
to the works of Abel et al [1] and Besag [5]. Soon enough, MRFs found
applications in various image processing tasks, such as edge detection, image
denoising, segmentation, and stereo [28]. In particular, the works conducted
by Boykov and Jolly [7] and Boykov et al. [6] demonstrated that one can apply
efficient min st-cut based algorithms to solve image segmentation by modeling
it as a Maximum a Posteriori (MAP) estimator of an MRF. Their groundbreaking
results made possible the emergence of classical graph-based segmentation
methodologies such as GrabCut [38] and was, more recently, used to improve the
training of CNN-based segmenters [31]. CRF modeling, closely related to MRF,
has also played an important role in refining coarse network predictions in
recent segmentation methods [48, 13, 14].

In some ways, our proposed method draws inspirations from the methodologies
proposed by Rother et al. [38], and Marin et al. [31]. In [38], the authors
propose GrabCut, an algorithm that iteratively bound-optimizes a segmentation
energy, requiring the solution of a min st-cut problem at each iteration in
order to perform unsupervised regularized fitting of the image’s appearance,
which is modeled as a Gaussian mixture model. Our algorithm also uses min st-
cut solvers iteratively, but here we (1) work on patch data, instead of
individual pixels, and (2) fit the image appearance using a CNN classifier.
Due to the nature of CNNs, our network can seamlessly translate the patch-
level classifier into a pixel-level image segmenter. In [31], the authors show
how to perform weakly-supervised CNN segmentation via an optimizer that
alternates between solving an MAP-MRF problem and gradient computation. In
contrast, our method solves a fully unsupervised segmentation problem and does
not use our MAP solution to adjust gradient directions.

##  3 Methodology

Figure 1: The proposed algorithm. GraPL trains a convolutional neural network
to cluster patches of a single image without supervision under the guidance of
graph cuts, spatial continuity loss, and a patch affinity encoder. At
inference, this patch clustering knowledge is applied to pixel-level
segmentation of the image. $F^{\prime}_{\theta}$ and $F_{\theta}$ share the
same parameters.

GraPL (Graph Cuts at the Patch Level) is a fully unsupervised segmentation
method which operates in a single-image paradigm. Using patch clustering as a
pretext task for segmentation, during training it is able to learn distinctive
segment features that enable it to effectively segment the image at the pixel
level. Although other techniques have previously shown patch clustering to be
an effective surrogate task [24, 34, 44, 43], our method demonstrates that
clustering the patches of a single image provides sufficient feature learning
to accurately segment it. GraPL’s training is guided by patch-level graph
cuts; this intervention imposes spatial coherence priors which are helpful for
learning clusters that are conducive to segmentation. At inference, the
complexities of the pipeline disappear, leaving only the network. Leveraging a
generalization of CNNs, the trained model is “convolved” over the entire image
to produce a pixel-level segmentation.

###  3.1 Algorithm

Let $I:\Omega\mapsto\mathbb{R}^{c}$ be an image of $c$ channels with pixel set
$\Omega=\\{1,\ldots,n\\}\times\\{1,\ldots,m\\}$, and
$S:\Omega\mapsto\\{1,\ldots,K\\}$ be a segmentation map of $I$ in $K$ regions.
Let $\mathcal{P}$ be a set of patches from $I$, such that all patches are of
the same size, i.e., for each $p$ in $\mathcal{P}$,
$p:\Omega_{p}\mapsto\mathbb{R}^{c},\Omega_{p}\subset\Omega,|\Omega_{p}|=\operatorname{const}$.
In practice, we populate $\mathcal{P}$ by selecting all patches on a non-
overlapping $d\times d$ grid of $I$, resulting in patches of shape
$(w/d,h/d)$. We make this choice of $\mathcal{P}$ based on two factors: (1)
efficiency, as this operation can be efficiently performed by most deep
learning libraries via their unfolding methods, and (2) simplicity, as it’s
one of the simplest ways to generate equal sized patches that span $\Omega$.

Let $F_{\theta}:\Omega\mapsto[0,1]^{K\times|\Omega|}$ be an FCN, and
$F^{\prime}_{\theta}:\Omega_{p}\mapsto[0,1]^{K}$ be a CNN patch classifier. In
GraPL, both networks are parametrized by the same parameters $\theta$.
$F^{\prime}_{\theta}$ is used in our training stage and is applied to the
patches in $\mathcal{P}$, while $F_{\theta}$ is employed in our inference
phase and is our final segmenter. The full algorithm is shown in Figure 1.

#### Training Stage

Our goal is to learn $\theta$ exclusively from the data in $\mathcal{P}$ and
transfer it to $F_{\theta}$. To do so, our method trains $F^{\prime}_{\theta}$
by minimizing an energy formulated at the patch level of $I$. Let
$S^{\prime}:\mathcal{P}\mapsto\\{1,\ldots,K\\}$ be a labeling for the patches
in $\mathcal{P}$. Following the literature on MRF modeling [7], we define the
energy of $S^{\prime}$ for an unknown $\theta$ as:

$E(S^{\prime},\theta|\mathcal{P})=U(S^{\prime},\theta|\mathcal{P})+\lambda
V(S^{\prime}|\mathcal{P}),$ (1)

with $\lambda\geq 0$. The unary term $U(\cdot)$ is traditionally defined as:

$\displaystyle U(S^{\prime},\theta|X)=$ $\displaystyle-\sum_{p\in
P}\sum_{k=1}^{K}\mathbbm{1}(S^{\prime}(p)=k)[\ln{F^{\prime}_{\theta}(p)}]_{k},$
(2)

where $\mathbbm{1}(\cdot)$ is the indicator function and $[\cdot]_{k}$ is the
$k$-th position of a vector. Let $\alpha$ and $\beta$ be probability
distributions in $\mathbb{R}^{K}$, and let
$H(\alpha,\beta)=-\sum_{k=1}^{K}[\alpha]_{k}\ln[\beta]_{k}$ be their cross
entropy. This means that Eq. 2 can be seen as the sum of cross entropies
$H(S^{\prime}(p),F^{\prime}_{\theta}(p))$ between $S^{\prime}(p)$, taken as a
one-hot probability distribution, and $F^{\prime}_{\theta}(p)$ over all
$p\in\mathcal{P}$. The pairwise energy term $V(\cdot)$ is given by:

$V(S^{\prime}|\mathcal{P})=\sum_{(p,q)\in\mathcal{P}\times\mathcal{P}}\mathbbm{1}(S^{\prime}(p)\neq
S^{\prime}(q))\phi(p,q),$ (3)

with the patch similarity function $\phi(\cdot)$ defined as:

$\phi(p,q)=\frac{1}{\text{dist}(p,q)}\exp\left(-\frac{\text{aff}(p,q)^{2}}{2\sigma}\right),$
(4)

where the data affinity function $\text{aff}(p,q)$ evaluates the data
similarity between $p$ and $q$, and $\text{dist}(p,q)$ considers the Euclidean
distance between the centers of $p$ and $q$. We select $\sigma$ as the
standard deviation of affinities for all $p,q\in\mathcal{P}$. To compute patch
affinities we make use of a patch encoder, which extracts an embedding from
each patch in $\mathcal{P}$.

Inspired by GrabCut [38], GraPL minimizes $E$ using a block-coordinate descent
iterative strategy, where we alternate between optimizing for $\theta$ and
$S^{\prime}$, keeping the other constant. The current labeling
$S^{\prime}_{t}$ is updated using the current network parameters
$\theta_{t-1}$, now taken as fixed in Eq. 1:

$S^{\prime}_{t}=\operatorname*{arg\,min}_{S^{\prime}}E(S^{\prime}|\theta_{t-1},\mathcal{P}).$
(5)

The above problem can be approximately solved by a series of minimum $st$-cut
in the form of $\alpha$-expansion or $\alpha\beta$-swap moves [6]. This step
is can be quickly accomplished due to the efficiency of such graph cut
algorithms and the comparatively small size of $\mathcal{P}$, which presents a
further advantage to our patch-based framework. We then compute the updated
parameters $\theta_{t}$ via:

$\theta_{t}=\operatorname*{arg\,min}_{\theta}\mathcal{L}(F^{\prime}_{\theta}(\mathcal{P}),S^{\prime}_{t}),$
(6)

where
$F^{\prime}_{\theta}(\mathcal{P})=\\{F^{\prime}_{\theta}(p)\\}_{p\in\mathcal{P}}$.
We employ traditional gradient descent-based backpropagation to solve the
above problem. The loss $\mathcal{L}(\cdot)$, is designed to predict the
outputs of $F^{\prime}_{\theta}$ on each patch using the labels from
$S^{\prime}_{t}$. Keeping $S^{\prime}_{t}$ fixed, Eq. 2 conveniently
formulates that process as a sum of cross entropy losses, just as one would
naturally devise in a supervised segmentation learning scheme. We then follow
Kim _et al_. [25] and include a patch-level continuity loss $C(\theta)$:

$C(\theta)=\sum_{p\in\mathcal{P}}\sum_{q\in\mathcal{N}_{p}}|F^{\prime}_{\theta}(p)-F^{\prime}_{\theta}(q)|,$
(7)

where $\lvert\cdot\rvert$ is the $L1$ norm and $\mathcal{N}_{p}$ is the set of
patches immediately neighboring $p$ in $\Omega$ space. In the general case,
one can employ a $k$-nearest neighbors graph of the elements in $\mathcal{P}$,
considering the Euclidean distance between patch centers. For the $d\times d$
grid from Figure 1, we choose $\mathcal{N}_{p}$ to be given by the patches
immediately above and to the left of $p$, resembling what is done in [25].
This continuity loss brings spatial coherence outside the graph step and
encourages smooth boundaries on the network outputs. In practice, we found it
to be beneficial to have both the graph step and $C(\theta)$ in our method.
Our final loss is then defined as:

$\mathcal{L}(F^{\prime}_{\theta}(\mathcal{P}),S^{\prime}_{t-1})=\sum_{p\in
P}H(S_{t-1}^{\prime}(p),F^{\prime}_{\theta}(p))+\mu C(\theta),$ (8)

where $\mu\geq 0$. As a consequence of the use of both graph cuts and the
continuity loss described above, GraPL naturally suppresses extraneous labels
arising from irrelevant patterns or textures, automatically promoting model
selection.

As the alternation continues, $F^{\prime}_{\theta}$ improves to the point
where it no longer requires the guidance of the graph cuts to produce
spatially and semantically coherent patch clusters. At that point, we end our
training phase.

#### Inference Stage

Once $F^{\prime}_{\theta}$ is trained, our next goal is to classify all
possible patches in $I$ of shape equal to the patches in $\mathcal{P}$. To
that end, we first assume that, as a CNN, $F^{\prime}_{\theta}$ is composed of
an initial series of convolutional layers and a final stage of say $Q$ dense
layers, along with a softmax function at the end. Assume that the inputs of
all layers are unpadded, and that each dense layer has $s_{q}$ units leading
to a final output of size $K$. Now, one can replace each dense layer in
$F^{\prime}_{\theta}$ with a convolutional one of kernel size $\sqrt{s_{q}}$
and retain its exact functionality. Our resulting FCN, $F_{\theta}$, is now
capable of efficiently being applied to $I$, by effectively “convolving” it
with patch classifier $F^{\prime}_{\theta}$.

###  3.2 Advantages of using Graph Cut Iterations

In the absence of labels, GraPL learns to cluster patches via an iterative
procedure. This general formulation allows us to inject knowledge about the
domain by designing an apt method for selecting pseudo-labels. While similar
methods use $k$-means [10], mixture models [23], or simply argmax [25] to
transform network outputs into new pseudo-labels, GraPL uses these response
vectors to define the unary energy of a patch-level MRF graph of the image.

This approach for patch clustering introduces some advantages to our method.
First, while the MRF modeling step is done primarily to impose a spatial
coherence prior, due to the known shrinking bias of graph cuts [26], the
resultant partition also smooths segment boundaries and reduces the number of
distinct segments, leading to natural model selection. The spatial
regularization introduced by the proposed graph can also be generalized to
accommodate other classical graph formulations that consider segmentation
seeds [6], appearance disparity [40], curvature [16], or target distributions
[4]. Finally, in contrast to methods that discover objects by clustering patch
embeddings arising from pretrained transformers and applying a segmentation
head [21] or CRF refinement [44, 43], GraPL considers patch embeddings only as
way to guide its training stage, yielding a final pixel-level segmentation map
without postprocessing. We consider our graph cut-based approach to handle
rich patch features beneficial, as we do not overly depend on their clustering
power, and simply reference them as guidance when regularizing our training.

##  4 Experiments

###  4.1 Implementation and Experimental Setup

#### Segmentation Task

To evaluate the performance and behaviors of GraPL, the algorithm was tasked
with segmenting the 200 image test set of BSDS500 [3] using a variety of
hyperparameters. Segmentation performance is measured in terms of mean
intersection over union (mIoU) [19], with predicted segments matched one-to-
one with target segments using a version of the Hungarian algorithm modified
to accommodate $\hat{K}\neq K^{*}$, where $\hat{K}$ is the number of distinct
segments in the final segmentation, and $K^{*}$ is the number of segments in
the ground truth. Results are averaged across 10 different random seeds for
initialization.

#### Hyperparameters

Unless otherwise specified, the following configuration was used during
testing. Pseudo-labels were initialized according to the SLIC [2] based
algorithm described in Section 4.2. GraPL was run for four training
iterations, and the number of gradient steps in the loss minimization at each
iteration was 40, 32, 22, and 12 respectively. $K_{0}$, the number of initial
segments was set at 14, and $d$ was set to 32. Graph cuts were implemented
using pyGCO [29], and the pairwise energy coefficient, $\lambda$, was set to
64. The continuity loss was assigned a weight of $\mu=3$. The $L2$ norm
between DINOv2 [33] (ViT-L/14 distilled) patch embeddings was used as an
affinity metric to determine pairwise weights.

#### Network Architecture

An intentionally minimal CNN architecture was used, consisting of 2 $3\times
3$ unpadded convolutional layers with 32 and 8 filters, respectively. In
$F_{\theta}^{\prime}$, this is followed by a dense classification head with
$K_{0}$ units, and in $F_{\theta}$ it is followed by a
$(\frac{h}{d}-4)\times(\frac{w}{d}-4)$ convolutional segmentation head with
$K_{0}$ filters. The network layers are each separated by batch normalization,
$\tanh$ activations, and dropout with rate 0.2. Without padding, our network
is subject to certain regularization implications. In CNNs, zero padding an
image has the effect of dropping out some of the weights of the subsequent
convolutional layer. As our method requires the training phase to be executed
on unpadded images, it is effectively deprived of this regularization feature.
We found that applying dropout before the first convolutional layer all but
resolved issues arising from the network’s lack of padding. Despite its
simplicity, this network is complex enough to achieve reliable segmentations,
and more complex networks did not lead to better performance. In our work, we
also abstain from using padding on our inference phase, which results in
$\hat{S}=F_{\theta}(I)$ being of a size smaller than $\Omega$, due to the
convolution operations in $F_{\theta}$. GraPL handles this discrepancy by
interpolating $\hat{S}$ to the original dimensions via nearest neighbor
interpolation. Networks were implemented using PyTorch 2.0.1 [35].

#### Early Stopping

If a cross entropy loss of less than 1.0 was reached during the first
iteration, it was stopped early, and new pseudo-labels were assigned. During
the first iteration, we are fitting the initial pseudo-labels, which are
either arbitrary or assigned by SLIC. By imposing this early stopping
condition, we are avoiding the local minima where GraPL may be overfitting to
a less performant (or worse, arbitrary) segmentation.

###  4.2 Ablation Studies

#### Initialization

As an iterative algorithm, proper initialization is an important factor in
training GraPL. Although similar deep clustering algorithms have used randomly
initialized pseudo-labels [10, 25], we were unsure whether ignoring more
principled approaches was leaving performance on the table. To answer this
question, we compared four initialization strategies: “patchwise random,”
“seedwise random,” “spatial clustering,” and an approach based on SLIC [2].
The “patchwise random” approach individually assigns each patch $p$ in
$\mathcal{P}$ a random label. In the “seedwise random” strategy, we select
$K_{0}$ random patches and assign them each one of the $K_{0}$ labels; the
remaining patches are assigned the label of the patch closest to them. For
“spatial clustering,” patches are clustered using $k$-means according to their
$(x,y)$ spatial coordinates to form $K_{0}$ clusters of roughly equal size. In
the SLIC-based approach, we unfold a $K_{0}$ cluster SLIC segmentation with
low compactness into the same patches as the input image. The onehot labels of
these patches are averaged and normalized to produce soft labels. These soft
initializations are an attempt to regularize and retain all salient features
of the patch during training.

(a)

(b)

(c)

(d)

(e)

Figure 2: Example of undersegmentation from non-SLIC initialization. (a) Input
image. (b) Patchwise Random ($\hat{K}=2$). (c) Seedwise Random ($\hat{K}=4$).
(d) Spatial Clustering ($\hat{K}=4$). (e) SLIC ($\hat{K}=6$).

Tests demonstrated that patchwise random initialization is not an ideal choice
for GraPL (Table 1). This is likely because it encourages a disregard for
spatial coherence during the first and most important iteration. While SLIC
was shown to be the best choice out of the methods tested, seedwise random and
spatial clustering initialization performed only 1.0% and 0.6% worse,
respectively, and the algorithm could likely be tuned such that they meet or
exceed the performance of SLIC. However, in the current configuration, we
notice a tendency for both of these methods to result in undersegmentation, in
which $\Delta K=K_{0}-\hat{K}$ is considerably higher than the SLIC version
(Figure 2).

#### Pairwise Edge Weights

The pairwise energy function (Eq. 4) used by GraPL includes an affinity
function $\text{aff}(p,q)$. Designed with vision transformers in mind, this
function is defined by the Euclidean distance between some patch metric or
embedding $m(p)$ for $p\in\mathcal{P}$.

Though DINOv2 [33] has been shown to produce excellent, fully unsupervised
features on the patch level, requiring minimal supervised fine-tuning to
produce an effective segmentation model [33]. However, it’s unclear whether
the features are easily separable using unsupervised methods.

We examined the applicability of three definitions for $m(p)$: DINOv2
embedding, mean RGB color, and patch position. To produce the final DINO
embeddings, images were resized to $14d\times 14d$, such that each GraPL patch
corresponds to a $14\times 14$ DINO patch. These embeddings were reduced to
$K_{0}$ dimensions using 2nd degree polynomial PCA. As a baseline, we also
tested a version where the fully connected graph was replaced with a
4-neighborhood lattice of uniformly weighted edges.

In our tests, DINOv2 embeddings were a significantly better metric than
distance alone (Table 2). However, they were outperformed by simple RGB color
vectors. Acknowledging DINOv2’s ability to act as a feature extractor for
supervised segmentation, further research is needed to determine what types of
transformations are necessary for converting the embeddings into a better
affinity metric.

Initializer | mIoU
---|---
Patchwise Rand. | 0.496
Seedwise Rand. | 0.507
Spatial | 0.509
SLIC | 0.512
Table 1: Comparison of pseudo-label initialization methods

Metric | mIoU
---|---
Uniform | 0.459
Position | 0.476
Color | 0.527
DINOv2 | 0.512
Table 2: Comparison of pairwise weighting metrics

#### Warm Start

GraPL is designed to train the same network continuously throughout all
iterations. This is in contrast to similar iterative methods which prefer a
“cold start,” re-initializing the parameters of the surrogate function prior
to subsequent iterations. Preliminary tests showed that in our case, a “warm
start” approach is preferred to re-initializing the network each time. These
two approaches in fact produce very different loss curves (Figure 3). Cold
starts produce large spikes in loss at the beginning of each training
iteration, whereas warm starts require only minor adjustments at these points.
We expect that the first iterations of training provide important feature
learning to the first layers of the network. By starting cold at each
iteration, subsequent iterations are unable to benefit from the learned low-
level feature detectors and therefore present a more unstable training phase.

$0$$40$$72$$94$$0$$0.5$$1$$1.5$$2$$2.5$$3$Gradient StepCross EntopyWarmCold
Figure 3: Comparison of loss curves using warm and cold starting methods,
averaged over all test images in BSDS500 [3]. Here we consider the loss value
at the end of each gradient step. On the $x$-axis, we depict the instants
where a new training iteration starts.

#### Pairwise Energy Coefficient ($\lambda$)

GraPL uses graph cuts to generate each new set of pseudo-labels, working on
the theory that this graphical representation of the image provides an
important spatial coherence prior, which is perhaps missing from similar
unsupervised methods, and accounts for its success. Furthermore, GraPL relies
on pairwise costs as well as the continuity loss to gradually decrease
$\hat{K}$. To test these ideas, we evaluated the segmentation performance of
the algorithm as well as $\Delta K$ across different values of $\lambda$, the
hyperparameter which defines the scale of the pairwise energy as defined in
Eq. 4.

When $\lambda=0$, cutting any non-terminal edge incurs no cost. In this case,
the function of the cut is effectively the same as the argmax clustering step
found in [25], as pseudo-labels are entirely dependent on the current network
response vectors. As $\lambda$ increases, network response vectors are made
less influential in the pseudo-label assignment process, as expected.

(a)02832128$0.46$$0.48$$0.5$$0.52$$\lambda$mIoU

(b)02832128$11.4$$11.6$$11.8$$12$$12.2$$\lambda$$\Delta K$

Figure 4: Effects of pairwise energy coefficient. (a) Effect of $\lambda$ on
mIoU. (b) Effect of $\lambda$ on $\Delta K$.

The results in Figure 4 demonstrate a logarithmic increase in segmentation
performance as $\lambda$ is raised from $0$ through $64$. However, increasing
$\lambda$ to values higher than 64 tends to result in comparatively poor
performance. Because increasing $\lambda$ strengthens pairwise connections, we
would expect it to be closely correlated with $\Delta K$. When $\lambda\leq
64$, we observe this behavior; however, higher values actually result in a
plateau or slight decrease in $\Delta K$.

In a configuration where the pairwise edges were uniformly weighted (or
weighted according to spatial distance), we would expect higher than optimal
values of $\lambda$ to push $\Delta K$ too high and produce oversimplified
segmentations, where multiple target segments are collapsed into a single
predicted segment. However, when pairwise edges are weighted by patch encoder
embedding affinity, pushing $\lambda$ too high can instead result in an overly
detailed segmentation, in which the graph cut considers the pairwise energy
(dictated by the patch embeddings) more than the unary weights learned by
GraPL.

#### Continuity Loss

Spatial continuity loss, first introduced in [25], provides GraPL a spatial
coherence prior which penalizes the network directly at each gradient step,
rather than through the graph cut produced pseudo-labels at the end of each
iteration. Though shown effective in [25], we instinctively believed that it
would be redundant in a graphically guided pipeline like GraPL. However, we
observed that the combination of the two different spatial coherence priors
produced more accurate segmentations than either one alone (Figure 5).

00.51248$0.35$$0.4$$0.45$$0.5$$0.55$$\mu$$\operatorname{mIoU}$ Figure 5:
Effect of spatial continuity loss weight on mIoU

In practice, we noted that this loss has a different mechanism of action than
the graphical coherence prior. In the absence of this spatial loss, GraPL
employs a level of trust in the patch encoder that may be unfounded, as the
pairwise energy only penalizes the separation of patches with a great
affinity; but when using a patch encoder like DINO, which is defined by a
large neural network, the edge weights may be high variance. In this case,
increasing $\lambda$ only serves to emphasize the patch encoder’s bias for
certain edges. However, increasing the weight of the spatial continuity loss
applies a higher penalty for _all_ edges. In effect, it could be compared to
an additive bias term in the pairwise energy function that raises the cost, no
matter the patch affinity.

#### Patch Size

Patch-based approaches are faced with a choice between granularity (with
smaller patches) and the information richness of input (with larger patches).
In GraPL’s case, smaller patches also entail more complex graphs that take
longer to solve, and larger patches entail higher memory usage. We found that
setting $d$ equal to 32 offered both optimal performance and near optimal
efficiency (Table 3).

$d$ | mIoU | Seconds per Image
---|---|---
8 | 0.248 | 3.49
16 | 0.372 | 1.72
32 | 0.512 | 1.75
64 | 0.496 | 6.98
Table 3: mIoU and segmentation time as a function of patch size. Time
measurements are based on segmentation of BSDS500 test set on an Nvidia A100
GPU and AMD Epyc 7343 CPU.

(a) Input

(b) GT1

(c) GT2

(d) GraPL

(e) DFC

(f) Double DIP

(g) PiCIE

(h) SegSort

(i) W-Net

Figure 6: Qualitative comparison of GraPL to other deep learning-based
unsupervised segmentation methods. We selected two of the available ground
truth segmentations (GT1 and GT2) for comparison, one more detailed and one
less detailed.

###  4.3 Comparison to Other Methods

We compared the segmentation performance of GraPL to six other unsupervised
deep-learning methods: Differentiable Feature Clustering (DFC) [25], Invariant
Information Clustering (IIC) [24], Pixel-level feature Clustering using
Invariance and Equivariance (PiCIE) [15], Segment Sorting (SegSort) [23] and
W-Net [45]. We also tested two baselines which use SLIC to segment images
based on RGB and DINOv2 [33] patch embeddings (interpolated to the pixel
level). These baselines were selected to demonstrate that the success of our
method does not simply originate from its initialization or its pretrained
guidance. PiCIE and SegSort were trained on their preferred datasets, COCO-
Stuff [8] and PASCAL VOC 2012 [17], as BSDS500 is too small, while the others
used only BSDS500.

Table 4 summarizes the quantitative comparative results of the above methods,
where segmentation performance was measured in terms of both mIoU and pixel
accuracy [19]. As with mIoU, pixel accuracy was computed using a one-to-one
label matching strategy. Figure 6 displays some segmentation results from the
above methods for qualitative comparison.

Method | mIoU | Accuracy
---|---|---
SLIC (RGB features) | 0.137 | 0.416
SLIC (DINOv2 features) | 0.258 | 0.280
DFC [25] | 0.398 | 0.505
DoubleDIP [18] | 0.356 | 0.423
IIC [24]† | 0.172 |
PiCIE [15] | 0.325 | 0.405
SegSort [23] | 0.480 | 0.505
W-Net [45] | 0.428 | 0.531
GraPL (proposed) | 0.527 | 0.569
Table 4: BSDS500 performance comparison of GraPL with other unsupervised deep-
learning methods and baselines.
†The value listed for IIC is sourced from [25].

Compared to other unsupervised methods, GraPL is able to decompose complex
foregrounds into detailed yet semantically salient components. Notice how
GraPL is able to pick up on small details like sunglasses in the distance
while ignoring less relevant features of the image, such as creases in
clothing. In many cases, it is able to handle color gradient variation,
usually present in sky backgrounds or shadow regions. On occasion, GraPL
detects segments that are not present in the ground-truth, such as the bird
heads on the last qualitative example, which, despite being reasonable,
decreases its quantitative performance. Finally, it also struggles to detect
fine structures, such as castle tops, small holes and bird beaks. Despite
that, our proposed method is able to outperform all of the compared methods by
a margin of at least 6.9% in accuracy and 9.3% mIoU. It is also worth noting
the low performance of our baselines, when compared to GraPL. This
demonstrates that our method does not merely rest on the success of our our
initializer, SLIC. Instead, GraPL’s success is a product of its novel training
and inference methodology.

##  5 Conclusion

In this paper, we introduce GraPL, a deep learning-based unsupervised
segmentation framework that approaches the problem by solving a patch
clustering surrogate task to learn network parameters which are then used for
pixel-level classification. Additionally, GraPL is the first deep learning
method to employ a graph cut regularizer during training, which encourages
spacial coherence and leverages the discriminative power of patch embeddings.
Furthermore, it seamlessly translates patch-level learning to the pixel-level
without the need for postprocessing. Our experiments demonstrate our
algorithm’s promising capacities, as it is able to outperform many state-of-
the-art unsupervised segmentation methods. Our work can be seen as further
evidence for the benefit of using graph cuts in deep learning, especially in
the context of unsupervised segmentation.

## References

  * [1] Kenneth Abend, Tl Harley, and L Kanal.  Classification of binary random patterns.  IEEE Transactions on Information Theory, 11(4):538–544, 1965.
  * [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 Transactions on Pattern Analysis and Machine Intelligence, 34(11):2274–2282, 2012.
  * [3] Pablo Arbelaez, Michael Maire, Charless Fowlkes, and Jitendra Malik.  Contour detection and hierarchical image segmentation.  IEEE Trans. Pattern Anal. Mach. Intell., 33(5):898–916, May 2011\.
  * [4] Ismail Ben Ayed, Hua-mei Chen, Kumaradevan Punithakumar, Ian Ross, and Shuo Li.  Graph cut segmentation with a global constraint: Recovering region distribution via a bound of the bhattacharyya measure.  In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 3288–3295. IEEE, 2010.
  * [5] Julian Besag.  On the statistical analysis of dirty pictures.  Journal of the Royal Statistical Society Series B: Statistical Methodology, 48(3):259–279, 1986.
  * [6] Yuri Boykov, Olga Veksler, and Ramin Zabih.  Fast approximate energy minimization via graph cuts.  IEEE Transactions on pattern analysis and machine intelligence, 23(11):1222–1239, 2001.
  * [7] Yuri Y Boykov and M-P Jolly.  Interactive graph cuts for optimal boundary & region segmentation of objects in nd images.  In Proceedings eighth IEEE international conference on computer vision. ICCV 2001, volume 1, pages 105–112. IEEE, 2001.
  * [8] Holger Caesar, Jasper Uijlings, and Vittorio Ferrari.  Coco-stuff: Thing and stuff classes in context.  In Computer vision and pattern recognition (CVPR), 2018 IEEE conference on. IEEE, 2018.
  * [9] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In European conference on computer vision, pages 213–229. Springer, 2020.
  * [10] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze.  Deep clustering for unsupervised learning of visual features.  In Proceedings of the European conference on computer vision (ECCV), pages 132–149, 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 Proceedings of the IEEE/CVF international conference on computer vision, pages 9650–9660, 2021.
  * [12] Tony F Chan and Luminita A Vese.  Active contours without edges.  IEEE Transactions on image processing, 10(2):266–277, 2001.
  * [13] Liang-Chieh 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 transactions on pattern analysis and machine intelligence, 40(4):834–848, 2017.
  * [14] Liang-Chieh Chen, George Papandreou, Florian Schroff, and Hartwig Adam.  Rethinking atrous convolution for semantic image segmentation.  arXiv preprint arXiv:1706.05587, 2017.
  * [15] Jang Hyun Cho, Utkarsh Mall, Kavita Bala, and Bharath Hariharan.  Picie: Unsupervised semantic segmentation using invariance and equivariance in clustering.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16794–16804, 2021.
  * [16] Noha Youssry El-Zehiry and Leo Grady.  Fast global optimization of curvature.  In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 3257–3264. IEEE, 2010.
  * [17] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman.  The PASCAL Visual Object Classes Challenge 2012 (VOC2012) Results.  http://www.pascal-network.org/challenges/VOC/voc2012/workshop/index.html.
  * [18] Yosef Gandelsman, Assaf Shocher, and Michal Irani.  ” double-dip”: unsupervised image decomposition via coupled deep-image-priors.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11026–11035, 2019.
  * [19] Alberto Garcia-Garcia, Sergio Orts-Escolano, Sergiu Oprea, Victor Villena-Martinez, and Jose Garcia-Rodriguez.  A review on deep learning techniques applied to semantic segmentation, 2017.
  * [20] Mark Hamilton, Zhoutong Zhang, Bharath Hariharan, Noah Snavely, and William T Freeman.  Unsupervised semantic segmentation by distilling feature correspondences.  In International Conference on Learning Representations, 2021.
  * [21] Mark Hamilton, Zhoutong Zhang, Bharath Hariharan, Noah Snavely, and William T Freeman.  Unsupervised semantic segmentation by distilling feature correspondences.  arXiv preprint arXiv:2203.08414, 2022.
  * [22] Kai Han, Yunhe Wang, Jianyuan Guo, Yehui Tang, and Enhua Wu.  Vision gnn: An image is worth graph of nodes.  Advances in Neural Information Processing Systems, 35:8291–8303, 2022.
  * [23] Jyh-Jing Hwang, Stella X Yu, Jianbo Shi, Maxwell D Collins, Tien-Ju Yang, Xiao Zhang, and Liang-Chieh Chen.  Segsort: Segmentation by discriminative sorting of segments.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7334–7344, 2019.
  * [24] Xu Ji, Joao F Henriques, and Andrea Vedaldi.  Invariant information clustering for unsupervised image classification and segmentation.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 9865–9874, 2019.
  * [25] Wonjik Kim, Asako Kanezaki, and Masayuki Tanaka.  Unsupervised learning of image segmentation based on differentiable feature clustering.  IEEE Transactions on Image Processing, 29:8055–8068, 2020.
  * [26] Vladimir Kolmogorov and Yuri Boykov.  What metrics can be approximated by geo-cuts, or global optimization of length/area and flux.  In Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1, volume 1, pages 564–571. IEEE, 2005.
  * [27] Philipp Krähenbühl and Vladlen Koltun.  Efficient inference in fully connected crfs with gaussian edge potentials.  Advances in neural information processing systems, 24, 2011.
  * [28] Stan Z Li.  Markov random field modeling in image analysis.  Springer Science & Business Media, 2009.
  * [29] Yujia Li and Jirka Borovec.  pygco.  https://github.com/Borda/pyGCO, 2023.
  * [30] Qinghong Lin, Weichan Zhong, and Jianglin Lu.  Deep superpixel cut for unsupervised image segmentation.  In 2020 25th International Conference on Pattern Recognition (ICPR), pages 8870–8876. IEEE, 2021.
  * [31] Dmitrii Marin, Meng Tang, Ismail Ben Ayed, and Yuri Boykov.  Beyond gradient descent for regularized segmentation losses.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10187–10196, 2019.
  * [32] Shervin Minaee, Yuri Boykov, Fatih Porikli, Antonio Plaza, Nasser Kehtarnavaz, and Demetri Terzopoulos.  Image segmentation using deep learning: A survey.  IEEE transactions on pattern analysis and machine intelligence, 44(7):3523–3542, 2021.
  * [33] Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, et al.  Dinov2: Learning robust visual features without supervision.  arXiv preprint arXiv:2304.07193, 2023.
  * [34] Yassine Ouali, Céline Hudelot, and Myriam Tami.  Autoregressive unsupervised image segmentation.  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part VII 16, pages 142–158. Springer, 2020.
  * [35] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran Associates, Inc., 2019.
  * [36] Yazhou Ren, Jingyu Pu, Zhimeng Yang, Jie Xu, Guofeng Li, Xiaorong Pu, Philip S Yu, and Lifang He.  Deep clustering: A comprehensive survey.  arXiv preprint arXiv:2210.04142, 2022.
  * [37] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18, pages 234–241. Springer, 2015.
  * [38] Carsten Rother, Vladimir Kolmogorov, and Andrew Blake.  ” grabcut” interactive foreground extraction using iterated graph cuts.  ACM transactions on graphics (TOG), 23(3):309–314, 2004.
  * [39] Jianbo Shi and Jitendra Malik.  Normalized cuts and image segmentation.  IEEE Transactions on pattern analysis and machine intelligence, 22(8):888–905, 2000.
  * [40] Meng Tang, Lena Gorelick, Olga Veksler, and Yuri Boykov.  Grabcut in one cut.  In Proceedings of the IEEE international conference on computer vision, pages 1769–1776, 2013.
  * [41] Ilya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al.  Mlp-mixer: An all-mlp architecture for vision.  Advances in neural information processing systems, 34:24261–24272, 2021.
  * [42] Asher Trockman and J Zico Kolter.  Patches are all you need?  arXiv preprint arXiv:2201.09792, 2022.
  * [43] Xudong Wang, Rohit Girdhar, Stella X Yu, and Ishan Misra.  Cut and learn for unsupervised object detection and instance segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3124–3134, 2023.
  * [44] Yangtao Wang, Xi Shen, Yuan Yuan, Yuming Du, Maomao Li, Shell Xu Hu, James L Crowley, and Dominique Vaufreydaz.  Tokencut: Segmenting objects in images and videos with self-supervised transformer and normalized cut.  arXiv preprint arXiv:2209.00383, 2022.
  * [45] Xide Xia and Brian Kulis.  W-net: A deep model for fully unsupervised image segmentation.  arXiv preprint arXiv:1711.08506, 2017.
  * [46] Enze Xie, Wenhai Wang, Zhiding Yu, Anima Anandkumar, Jose M Alvarez, and Ping Luo.  Segformer: Simple and efficient design for semantic segmentation with transformers.  Advances in Neural Information Processing Systems, 34:12077–12090, 2021.
  * [47] Hongshan Yu, Zhengeng Yang, Lei Tan, Yaonan Wang, Wei Sun, Mingui Sun, and Yandong Tang.  Methods and datasets on semantic segmentation: A review.  Neurocomputing, 304:82–103, 2018.
  * [48] Shuai Zheng, Sadeep Jayasumana, Bernardino Romera-Paredes, Vibhav Vineet, Zhizhong Su, Dalong Du, Chang Huang, and Philip HS Torr.  Conditional random fields as recurrent neural networks.  In Proceedings of the IEEE international conference on computer vision, pages 1529–1537, 2015.