# Deep Superpixel Cut for Unsupervised Image Segmentation

Qinghong Lin1,2, Weichan Zhong1, Jianglin Lu1,2 1College of Computer Science
and Software Engineering, Shenzhen University, Shenzhen, 518060, China
2Institute of Computer Mathematics and Information Technologies, Kazan Federal
University, Kazan 420008, Russia
Email<EMAIL_ADDRESS>
###### Abstract

Image segmentation, one of the most critical vision tasks, has been studied
for many years. Most of the early algorithms are unsupervised methods, which
use hand-crafted features to divide the image into many regions. Recently,
owing to the great success of deep learning technology, CNNs based methods
show superior performance in image segmentation. However, these methods rely
on a large number of human annotations, which are expensive to collect. In
this paper, we propose a deep unsupervised method for image segmentation,
which contains the following two stages. First, a Superpixelwise Autoencoder
(SuperAE) is designed to learn the deep embedding and reconstruct a smoothed
image, then the smoothed image is passed to generate superpixels. Second, we
present a novel clustering algorithm called Deep Superpixel Cut (DSC), which
measures the deep similarity between superpixels and formulates image
segmentation as a soft partitioning problem. Via backpropagation, DSC
adaptively partitions the superpixels into perceptual regions. Experimental
results on the BSDS500 dataset demonstrate the effectiveness of the proposed
method.

##  I Introduction

Image segmentation aims to divide an image into many perceptual regions, where
pixels within a region will have similar features, e.g. color, intensity, or
texture. This technique has been widely used in many vision tasks, such as
object detection [1], semantic segmentation[2], object tracking [3]. Although
image segmentation has been researched for many years, still remains a core
problem in computer vision.

Existing segmentation methods always split the image into regular superpixels
and merge them superpixels into large regions. Generally, these methods do not
need human annotation for segmentation. The representative method is NCuts
[4], which recursively computes normalized cuts on the graphs, Although NCuts
can generate compact regions, the learned boundary adhere is poor. To solve
this problem, FH [5] is proposed to well preserve the boundaries. However, FH
always produces too large or too small segments, which leads to unsatisfactory
segmentation results. Generally, the traditional segmentation methods utilize
low-level hand-crafted features, which is the main reason for limiting
segmentation performance.

Owing to the great success of deep learning technology, amount of deep
segmentation methods [2] [6] [7] have been proposed in recent years. One of
the most important works is FCNs (Fully convolutional networks) [2], which
replaces the fully connected layers with convolutional layers in the used
network. FCNs regards the segmentation task as a pixel-wise classification
problem, also known as semantic segmentation. Thank to the powerful feature
representation capabilities of CNN, deep segmentation methods has achieved
better performance than the classic methods. However, deep segmentation
methods usually require massive labels for training, which are expensive and
time-consuming to collect.

Figure 1: Classical segmentation algorithms divide the image into superpixels
according to their low-level features, while deep learning methods regard
segmentation as a pixelwise classification problem in a supervised manner.

For this purpose, we propose a deep learning architecture for unsupervised
image segmentation, which regards the image segmentation as a graph
partitioning problem. Our approach relies on a Superpixelwise Autoencoder
(SuperAE) and contains two stages. First, SuperAE take the original image and
a high quality oversegment template [8] as input, use this template as
guideline to learn deep embedding and reconstruct a smoothed image, then this
smoothed image is used to generate superpixels. Second, we present a novel
clustering method called Deep Superpixel Cut (DSC), which measures the deep
similarity of superpixels, and partitions them into perceptual segments
adaptively. Our main contributions are summarized as follows:

  * •

We propose a new autoencoder SuperAE to learn the deep embedding and smooth
the original image, which conducive to the superpixels generation and
segmentation.

  * •

We propose an unsupervised segmentation algorithm DSC, which adopts a soft
partitioning strategy to group superpixels into multiple regions based on
their deep similarity.

  * •

The experiment results on BSDS500 [8] prove the effectiveness of our method.
Our framework can achieve satisfactory segmentation based on the existing
superpixel algorithms.

##  II Related Work

In this section, we briefly review the traditional superpixel algorithms, then
discuss recent works on semantic segmentation, especially in unsupervised
scenario. Finally, we introduce some research works on deep unsupervised
learning.

###  II-A Superpixel Segmentation

Over-segmentation is an important process in traditional segmentation, which
divides the image into many regions based on low-level information, such
regions also called superpixels. These algorithms can be mainly divided into
two categories: graph-based and clustering-based algorithms.

Graph-based methods consider the segmentation as a graph-partitioning problem,
in which pixels are represented as nodes, and the strength of connectivity
between adjacent pixels are denoted as an edge. N-Cut [4] recursively computes
normalized cut on the graph, which generates regular results. FH [5] proposed
an algorithm that preserves boundary well by minimum spanning tree of the
constituent pixels. ERS [9] merges disjoint sets by maximizing the entropy
rate of pixel affinities. Clustering-based methods employ clustering
techniques for segmentation, group pixels into regions, and refine them until
satisfying the criteria. Some widely-used methods like SLIC [10] initialize
cluster centers on a uniform grid and apply $k$-means in CIELab space. LSC
[11] expands the CIELab space to ten-dimensional space, considering the graph
cut problem as a clustering problem. Manifold SLIC [12] uses a 2-dimensional
manifold feature space instead of CIELab space. Generally, superpixel
algorithms can generate regular regions, but because they do not consider the
global information of the image, they are not suitable for direct
segmentation. In our DSC, we first generate superpixels by existing methods,
then use deep features to represent them, and then partitions them superpixels
to obtain segmentation.

###  II-B Semantic Segmentation

Recent deep learning techniques have achieved impressive result in image
segmentation tasks. Most methods learn a CNNs to produce pixel-wise
classification, this tasks is also called semantic segmentation. One of the
most important models is fully convolutional networks (FCNs) [2], FCNs
replaces fully connected layers with convolutional layers to generate a
prediction map of the same size as the image. Inspired by FCNs, various
semantic segmentation models [7] [6] have been proposed.

Although CNNs can learn richer image representation for segmentation, training
CNNs usually require a large number of pixel-wise labels, which are difficult
to collect. To eliminate the dependence on labels, some unsupervised methods
are proposed. Recently, Backpro [13] applies post-processing to superpixels
and updates the CNN through backpropagation. W-Net [14] produces a pixelwise
prediction by soft N-Cut loss. [15] proposes a Mumford-Shah loss that can be
integrated into existing networks. IIC [16] learn a good representation by
maximizing the mutual information between image patch. Different from the
above methods, DSC formulates the image segmentation as a superpixel-level
graph partition problem and introduces deep representation, aiming to take
advantage of the superpixels and alleviate the restrictions of hand-crafted
features.

###  II-C Deep Clustering

Clustering is a core problem in unsupervised machine learning and has been
studied for many years. Classical algorithms such as $k$-means, hierarchical
clustering, spectral clustering have been widely used. Inspired by the success
of deep learning in supervised learning, some works integrate the deep
learning techniques into clustering tasks. DEC [17] adopts a stacked
autoencoder to learn the latent representations and refines clusters by
minimizing the KL divergence loss. JULE [18] jointly optimizes CNNs with
clustering parameters in a recurrent manner, performs clustering in forwarding
and learns the features in backward. [19] proposes a joint learning framework
based on a dual autoencoder network for learning discriminative embedding and
spectral clustering. In our SuperAE, we regard $k$-means loss as
regularization in image reconstruction, which helps to minimize the within-
cluster variance to smooth the image. Borrowed the idea of spectral
clustering, DSC regards the segmentation as a graph-partition problem and
adopt soft association, which is differentiable and can be optimized by
backpropagation.

Figure 2: The proposed architecture. First, the SuperAE takes the original
image and a template as input, learns the deep embedding, and smooths the
image, then the smoothed image is passed into the existing superpixel
algorithm to generate superpixels. Second, the DSC algorithm takes the
superpixels and deep features as input, and partitions the superpixels into
different regions iteratively. The purple lines indicate the gradient flow.

##  III Method

The framework of our method is shown in Fig. 2, which consists of two stages.
First, we train the SuperAE to learn deep features and smooth the images, then
the partitions images are passed to generate superpixels. Second, DSC measures
the deep similarity of superpixels and partitions them into different regions.
In this section, we will introduce SuperAE and DSC in turn and finally
describe how to optimize the DSC.

###  III-A Superpixelwise Autoencoder

Our SuperAE is based on the stacked autoencoder, which is composed of a series
of basic modules, containing a $3\times 3$ convolution layer, batch
normalization, and ReLU activation. The encoder includes three modules, the
number of output channels are 64, 128 and 256 respectively. For down-sampling,
we use the $2^{th}$ and $3^{th}$ convolution layers by a factor of 2. The
decoder contains three modules and the number of output channels are 128, 64
and 3. Especially, we adopt $3\times 3$ transpose convolution with a factor of
2 for up-sampling in $4^{th}$ and $5^{th}$ layers. Finally, we get the
reconstructed result from the sigmoid layer.

Since images from the real world contain some noise, the segmentation will be
affected. Therefore, we hope that SuperAE can denoise the input and output of
a smoothed image. We observe that the spatially continuous pixels are usually
continuous in color space, and pixels within the same superpixel usually
satisfy this criterion, so we regard this as a constraint in SuperAE and adopt
the high-quality over-segmentation from [8] as templates, use it as a
guideline for reconstruction.

Given an image and a superpixel template, SuperAE updates the parameters by
minimizing the loss function Eq. 1. The first item is the pixel-wise MSE loss
and the second item is a regularization added by superpixel templates.

$\mathcal{L}_{r}=\|x-x^{R}\|^{2}+\lambda\sum_{i=1}^{N}\sum_{j=1}^{M}t_{ij}\|x^{R}_{i}-v_{j}\|^{2}$
(1)

where $x$ is the input image, $x^{R}$ is the reconstruction result. Given a
superpixel template $t$, $t_{ij}$ equal to 1 if pixel $i$ belong to superpixel
$j$, otherwise equal to 0. $N$ and $M$ denote the number of pixels and
superpixels. $x_{i}$ and $v_{j}$ represent the RGB vector of pixel $i$ and
superpixel $j$, and $v_{j}$ is defined as the average vector of pixels belong
to superpixel $j$.

$v_{j}=\frac{\sum_{i=1}^{N}t_{ij}x_{i}}{\sum_{i=1}^{N}t_{ij}}$ (2)

The effect of the second term of Eq. 1 can be seen as minimizing the variance
of pixel features within a superpixel, thus smoothing the regions. After
training, the reconstructed image $x^{R}$ is a smoothed version of the
original image $x$, which will be used to generate superpixels $z$ by existing
algorithms like SLIC[10]. We also preserve the encoder of SuperAE, we denote
it as $\mathbf{E}(\cdot;\theta)$, which has learned the mapping from RGB to
deep embedding space. Considering the high layer features contain more coarse
and global information while the low layer features contain more fine and
local information, we upsample and concatenate the output of $1^{th}$,
$2^{th}$ and $3^{th}$ layers with the original image and follow a $1\times 1$
convolution with $K$ output channels, where $K$ is the number of partitions in
DSC, so that we can obtain a better representation and use it as the deep
embedding of the image. Our first stage has been described in Algorithm. 1.

Algorithm 1 Learning Superpixelwise Autoencoder

0: Image set $\mathbf{X}=\\{x\\}$, Superpixel templates $\mathbf{T}=\\{t\\}$,
Network ${\mathbf{N}}(;\theta)$, factor $\lambda$.

1: Initialize the network parameters $\theta$.

2: repeat

3: Update network parameters $\theta$ by minimize (1)

4: until convergence

5: for each image $x$ in $\mathbf{X}$ do

6: Generate reconstructed image $x^{R}$ from ${\mathbf{N}}(x;\theta)$.

7: Generate superpixel $z$ from $x^{R}$ by existing superpixel algorithm.

8: end for

8: Superpixels ${\mathbf{Z}}=\\{z\\}$, Encoder $\mathbf{E}(\cdot;\theta)$

###  III-B Deep Superpixel Cut

After the first stage, we obtain the superpixels $\mathbf{Z}=\\{z\\}$ and
trained encoder of SuperAE $\mathbf{E}(\cdot;\theta)$. In this stage, we first
consider the segmentation as a  pixelwise $K$-class classification problem, in
where each class been seen as a segment or partition. We consider the most
commonly used cross-entropy loss in semantic segmentation.

$\mathcal{L}_{1}=-\sum_{n=1}^{N}\sum_{k=1}^{K}y^{k}_{n}\log(p^{k}_{n})$ (3)

where $y\in\\{0,1\\}$ is the label, $p\in[0,1]$ is the predicted probability,
$N$ and $K$ denote the number of pixels and classes. Due to the lack of label
$y$ in our task, so we adopt the following strategy to generate the pseudo
label $\widetilde{y}$

Given an image $x$ and corresponding superpixel $z$, we first extract the deep
feature embedding
$\mathbf{F}=[f_{1},f_{2},\cdots,f_{N}]^{T}\in\mathbb{R}^{N\times K}$ from
SuperAE’s encoder $\mathbf{E}(\cdot;\theta)$. Then, we apply softmax operation
on $\mathbf{F}$ to obtain probability
$\mathbf{P}=[P_{1},P_{2},\cdots,P_{N}]^{T}\in\mathbb{R}^{N\times K}$, each
column $P_{i}=[p_{i}^{1},\cdots,p_{i}^{K}]\in\mathbb{R}^{1\times K}$ represent
the probability of pixel $i$ belong to different partition.

For each pixel $n$, we apply argmax operation on probability $p_{n}$ to get
the maximum probability class $c_{n}$. Then, we mark the class ${C}_{j}$ with
the largest number of pixels for each superpixel $S_{j}$. Finally, we assign
${C}_{j}$ to all pixel in the same superpixel $S_{j}$ to obtain the pseudo
label $\widetilde{{{Y}}}=\\{\widetilde{y}_{n}^{k}\\}\in\mathbb{R}^{N\times
K}$, which employ one-hot coding. So that we can use Eq. 3 replace $y_{n}^{k}$
with ${\widetilde{y}_{n}^{k}}$. The generation of pseudo-labels can be
described as follows.

$\left\\{\begin{array}[]{l}c_{n}=\mathop{\text{argmax}}\limits_{k}p_{n}^{k},\quad
n\in[0,N)\\\ {{C}}_{j}=\mathop{\text{argmax}}\limits_{k}|c_{n}|\quad
j\in[0,M),n\in S_{j}\\\ {\hat{y}}^{k}_{n}=\mathbf{1}(c_{n}={{C}}_{j})\quad
j\in[0,M),n\in S_{j}\end{array}\right.$ (4)

where $M$ is the number of superpixels and $\mathbf{1}$ is the indicator
function.

Even we obtain the pseudo label ${\widetilde{{Y}}}$, the learned
representation is not fully exploited in Eq. 3. Here, we also consider the
segmentation as a superpixelwise graph-partition problem, in where superpixels
are represented as nodes, and the deep similarity between superpixels is
regarded as an edge. First, we define the deep representation of superpixels
$\mathbf{G}=[g_{1},g_{2},\cdots,g_{M}]^{T}\in\mathbb{R}^{M\times K}$ by
pooling operation

$g_{j}=\frac{\sum_{i=1}^{N}z_{ij}f_{i}}{\sum_{i=1}^{N}{z}_{ij}}$ (5)

where ${z}_{ij}$ equal to 1 if pixel $i$ belong to superpixel $j$, otherwise
0. Next, we compute the partition association
$\mathbf{Q}=[{Q}_{1},\cdots,{Q}_{K}]\in\mathbb{R}^{M\times K}$, where
${Q}_{k}=[{q}_{1}^{k},\cdots,{q}_{M}^{k}]^{T}\in\mathbb{R}^{M\times 1}$ denote
the probability of each superpixel belong to partition $k$ by

${q}^{j}_{k}=\frac{\sum_{i=1}^{N}z_{ij}p^{i}_{k}}{\sum_{i=1}^{N}{z}_{ij}}$ (6)

Then, we construct a similarity matrix $\mathbf{W}\in\mathbb{R}^{M\times M}$,
each element $w_{ij}$ denotes the deep similarity between superpixel $i$ and
superpixel $j$, which defined as

$w_{ij}=\left\\{\begin{array}[]{l}exp({\frac{-\|g_{i}-g_{j}\|_{2}^{2}}{\sigma^{2}}}),\quad\text{if}\quad\|l(i)-l(j)\|_{2}<d\\\
0,\quad\text{otherwise}\end{array}\right.$ (7)

where $\sigma$ is a scale factor, $l(\cdot)$ is the center position of
superpixels and $d$ is a distance constant. The $w_{ij}\in[0,1]$ is close to 1
if $g_{i}$ and $g_{j}$ are highly similar, and close to 0 when $g_{i}$ and
$g_{j}$ are highly different.

Now, we assume that if two superpixel $a$ and $b$ are more similar in deep
features, then the probability they belong to different partitions should be
lower, which can be modeling as

$\displaystyle\mathcal{L}_{2}$ $\displaystyle=\sum_{k=1}^{K}\sum_{a,b\in
V}\mathcal{P}(a\in A_{k},b\notin A_{k})W(a,b)$ (8)
$\displaystyle=\sum_{k=1}^{K}\sum_{a,b\in V}{q}_{k}^{a}w_{ab}(1-q_{k}^{b})$
$\displaystyle=\sum_{k=1}^{K}{Q_{k}^{T}\mathbf{W}(\mathbf{1}-Q_{k})}$

So, our loss function as following and the DSC is described in Algorithm. 2

$\displaystyle\mathcal{L}_{s}$
$\displaystyle=\alpha\mathcal{L}_{1}+\beta\mathcal{L}_{2}$ (9)
$\displaystyle=\alpha\sum_{n=1}^{N}\sum_{k=1}^{K}{\hat{y}}^{k}_{n}\log(p^{k}_{n})+\beta\sum_{k=1}^{K}{Q_{k}^{T}\mathbf{W}(\mathbf{1}-Q_{k})}$

Algorithm 2 Deep Superpixel Cut

0: Original image $x$, Superpixels $z$, Encoder ${\mathbf{E}}(\cdot,\theta)$,
iteration $T$, coefficients $\alpha,\beta$, parameter $\sigma$, $d$.

1: for $t=1$ to $T$ do

2: Extract deep feature $\mathbf{F}$ of $x$ from encoder
${\mathbf{E}}(x;\theta)$

3: Compute the probability $\mathbf{P}$ from $\textit{softmax}(\textbf{F})$.

4: Generate pseudo label $\widetilde{{Y}}$ according to (4).

5: Compute the deep feature of superpixel $\mathbf{G}$ by (5).

6: Compute the association $\mathbf{Q}$ by (6).

7: Construct the similar matrix $\mathbf{W}$ by (7).

8: Update network parameters $\theta$ by minimize (9)

9: end for

9: Segmentation $\widetilde{{Y}}$

###  III-C Optimization

Because the softmax cross entropy $\mathcal{L}_{1}$ is differential, in order
to optimize the Eq. 9, we just need to guarantee ${\mathcal{L}_{2}}$ is
differentiable. By Chain Rule, we have

$\frac{\partial\mathcal{L}_{2}}{\partial
F}=\frac{\partial\mathcal{L}_{2}}{\partial Q}\frac{\partial Q}{\partial
G}\frac{\partial G}{\partial F}$ (10)

According to Eq. 8, the $\frac{\partial\mathcal{L}_{2}}{\partial{Q}}$ can be
calculated by

$\displaystyle\frac{\partial{\mathcal{L}_{2}}}{\partial{Q_{k}}}$
$\displaystyle=\frac{\partial(Q_{k}^{T}{\mathbf{W}}(\mathbf{1}-Q_{k}))}{\partial{Q_{k}}}$
(11)
$\displaystyle=\frac{\partial(Q_{k}^{T}{\mathbf{W}}\mathbf{1}-Q_{k}^{T}{\mathbf{W}}Q_{k})}{\partial{Q_{k}}}$
$\displaystyle={\mathbf{W}}\mathbf{1}-{\mathbf{W}}Q_{k}-(Q_{k}^{T}{\mathbf{W}})^{T}$
$\displaystyle={\mathbf{W}}\mathbf{1}-2{\mathbf{W}}Q_{k}$

$\frac{\partial Q}{\partial G}$ can be calculated by softmax operation and
$\frac{\partial G}{\partial F}$ can be computed by $\frac{\partial
g_{j}}{\partial f_{i}}$, which equal to
$\frac{{z}_{ij}}{\sum_{i=1}^{N}{z}_{ij}}$ according to Eq. 5. So,
$\mathcal{L}_{2}$ is differentiable, DSC can be optimized by back propagation
in network.

##  IV Experiment

In this section, we conduct experiments on BSDS500 [8] dataset, demonstrate
the effectiveness of our method, and compare the performance with other
unsupervised segmentation algorithms.

###  IV-A Dataset and Metrics

BSDS500 [8] is a benchmark for image segmentation, which provides 200, 100,
200 RGB images for training, validation and testing, each image with human-
annotated labels. In our method, the labels are only used for evaluating the
equality of segmentation, not used for training. We evaluate the performance
using three metrics: Segmentation Covering (SC), Variation of Information (VI)
and Probabilistic Rand Index (PRI). For SC and PRI, higher scores are better.
for VI, a lower score is better. We also report the result using the optimal
parameter setting for the entire dataset (ODS) and each image (OIS).

###  IV-B Implementation Details

In the first stage, we use the whole dataset to training the SuperAE. The
$\lambda$ is set to 1. We adopt the adam optimization techniques, and the
learning rate is set to 1e-3. We run for 100 epochs with batch sizes 10. We
also apply the data augmentation, cropping $300\times 300$ patch randomly from
each image and do a horizontal flip. In the second stage, we employ the
existing algorithms like [5] [10] to generate superpixels from the
reconstructed image. The specific algorithms and parameters will be stated in
the following experiments. In our DSC, the class number $K$ equal to 32. The
$\sigma$ is set to 10. The $d$ equal to $2\sqrt{\frac{N}{M}}$. Coefficients
$\alpha$ and $\beta$ equal to 1 and $\frac{5}{M^{2}}$ respectively. Then we
update the encoder with stochastic gradient descent (SGD) with 0.9 moments,
the learning rate is 5e-2. Each image runs for 128 iterations to obtain final
segmentation.

###  IV-C Experiment Result

Component Analysis. To clearly understand how the different components of our
method affect performance, we conduct the following experiments. We denote the
superpixels generated from original image as baseline (IMG), which generated
by EGB [5] and the number is controlled at about 100. We make the following
changes: replaced original image with reconstructed image (REC) with or
without template regularization (TEM), and then adopt $\mathcal{L}_{1}$ or
$\mathcal{L}_{2}$ to continue optimization.

TABLE I: The ablation study of different components IMG | REC | TEM | $\mathcal{L}_{1}$ | $\mathcal{L}_{2}$ | SC | PRI | VI
---|---|---|---|---|---|---|---
$\checkmark$ |  |  |  |  | 0.405 | 0.761 | 3.483
$\checkmark$ | $\checkmark$ |  |  |  | 0.388 | 0.756 | 3.622
$\checkmark$ | $\checkmark$ | $\checkmark$ |  |  | 0.453 | 0.769 | 3.019
$\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ |  | 0.477 | 0.769 | 2.471
$\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | 0.488 | 0.764 | 2.315

The OIS results are shown in Table I. Although reconstruction loses some
performance, the introduction of template regularization can bring 12%, 1%,
15% gain in SC, PRI and VI, which proves the influence of SuperAE on
superpixels generations. DSC can further improve performance by merging
superpixels. Especially combining SuperAE and DSC together, the result can
obtain 21%, 34% gain in SC and VI.

Robustness of Superpixels. Since our method is based on the existing
superpixel algorithms, so we are concerned about the robustness of different
superpixel algorithms. We evaluate the impact of following algorithms SLIC
[10], EGB [5] and MS [20]. For each algorithm, we control the number of
superpixels at 100, 50, 20, 10 for multiscale. We still consider the
superpixels generated from the original image as the baseline (IMG) and add
SuperAE and DSC respectively. As shown in the Table II, in various superpixel
algorithms, our method has obvious improvements in SC and VI.

TABLE II: Ablation study of different superpixels algorithm Method | SC | RI | VI
---|---|---|---
ODS | OIS | ODS | OIS | ODS | OIS
SLIC | IMG | 0.354 | 0.402 | 0.698 | 0.726 | 2.391 | 2.306
SuperAE | 0.376 | 0.415 | 0.710 | 0.745 | 2.360 | 2.286
DSC | 0.428 | 0.485 | 0.709 | 0.742 | 2.262 | 2.079
MS | IMG | 0.515 | 0.535 | 0.771 | 0.805 | 2.450 | 2.429
SuperAE | 0.497 | 0.550 | 0.777 | 0.795 | 2.162 | 2.077
DSC | 0.504 | 0.543 | 0.739 | 0.762 | 2.014 | 1.849
EGB | IMG | 0.458 | 0.467 | 0.770 | 0.775 | 2.334 | 2.325
SuperAE | 0.491 | 0.500 | 0.774 | 0.782 | 2.190 | 2.180
DSC | 0.506 | 0.548 | 0.737 | 0.779 | 1.989 | 1.853

Effect of DSC. For further exploring the effectiveness of DSC, we conduct the
following experiments. First, we generate superpixels by SLIC [10] and control
their number to 100, then we compare the following variants: represent the
superpixels by color (RGB) or deep feature (Deep), and clustering them
superpixels by $k$-Means or NCuts [4] to get final segmentation. For DSC and
each variants, the number of final partitions is controlled at 8,16,32,64. It
can be seen from the Table IV that directly replacing RGB with deep features
in the clustering algorithm may not necessarily improve the results, while DSC
can effectively benefit from deep features and achieves the best performance
among all variants.

TABLE III: Compare DSC with other clustering algorithm Method | SC | PRI | VI
---|---|---|---
ODS | OIS | ODS | OIS | ODS | OIS
$k$-means, RGB | 0.340 | 0.344 | 0.708 | 0.732 | 3.156 | 3.146
$k$-means, Deep | 0.375 | 0.382 | 0.718 | 0.739 | 2.865 | 2.859
NCut, RGB | 0.414 | 0.465 | 0.717 | 0.771 | 2.308 | 2.213
NCut, Deep | 0.386 | 0.423 | 0.704 | 0.754 | 2.433 | 2.382
DSC | 0.452 | 0.505 | 0.726 | 0.778 | 2.069 | 2.002

Analysis. For understanding our method intuitively, we visualize the result of
different stages in Fig. 3, including reconstructed image (b), initial
superpixels (d), partition in 64 (e) and 128 iterations (f). We can see that
the reconstructed image (b) has lower contrast than (a), and (b) is a smooth
version of (a). In (d) (e) (f), superpixels are gradually merged into
meaningful regions guided by DSC. In Fig. 4, we show the convergence curves in
the first stage and second stage. Both of them decrease stably and converge
with iterations.

(a) original image

(b) reconstructed image

(c) ground truth

(d) iter 0

(e) iter 64

(f) iter 128

Figure 3: The different stages in our method. (a) Original image, (b)
Reconstructed image of SuperAE, (c) Ground truth, (d) Initial superpixels (e)
Result in 64 iter, (f) Final segmentation

Figure 4: (a) The reconstruction loss $\mathcal{L}_{r}$ of SuperAE, (b) The segmentation loss $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ of DSC TABLE IV: The BSDS500 results of unsupervised segmentation methods Method | SC | PRI | VI
---|---|---|---
ODS | OIS | ODS | OIS | ODS | OIS
SLIC [10] | 0.37 | 0.38 | 0.74 | 0.75 | 2.56 | 2.50
NCuts [4] | 0.45 | 0.53 | 0.78 | 0.80 | 2.23 | 1.89
EGB [5] | 0.52 | 0.57 | 0.80 | 0.82 | 2.21 | 1.87
MS [21] | 0.54 | 0.58 | 0.79 | 0.81 | 1.85 | 1.64
gPb-owt-ucm [8] | 0.59 | 0.65 | 0.83 | 0.86 | 1.69 | 1.48
CAE-TVL [22] | 0.51 | 0.56 | 0.79 | 0.82 | 2.11 | 2.02
Backprop [13] | 0.47 | 0.50 | 0.75 | 0.77 | 2.18 | 2.15
Mumford-Shah [15] | 0.49 | $-$ | 0.71 | $-$ | 2.20 | $-$
W-Net[14] | 0.57 | 0.62 | 0.81 | 0.84 | 1.76 | 1.60
DSC | 0.56 | 0.60 | 0.80 | 0.83 | 1.82 | 1.62

Evaluation on BSDS500 Benchmarks. In Table IV, we compared our DSC with other
unsupervised segmentation algorithms in the BSDS500 benchmark. The superpixels
for DSC are generated by MS [21] with multiple parameters settings.
Particularly, [22] [13] [15] [14] are deep unsupervised methods. We can see
that DSC can achieve competitive performance and outperforms most of the
methods.

Qualitative Result. In Fig. 5, we show the qualitative results of DSC and
another deep unsupervised method Backprop [13], both of them start from the
same superpixels, which generated by SLIC [11] with M equal to 500. We can see
that DSC achieves a better segmentation effect than Backprop, it is mainly
because DSC considers more contextual information in the deep similarity.

##  V Conclusion

In this paper, we propose a deep learning method for unsupervised image
segmentation, which formulates the image segmentation as a graph partitioning
problem and integrates the deep representation. To learn the deep embedding,
we design a SuperAE, which also smooths the original image and conductive to
the superpixels generation. For segmentation, we propose a novel clustering
method DSC which measures the deep similarity between superpixels and
partitions them into perceptual regions by soft association. Experiment
results on BSDS500 demonstrate the efficacy of our proposed, and our DSC
outperforms most of the unsupervised segmentation methods.

##  VI Acknowledgement

This research was supported by NSFC under Grant no. 61773268, 61502177 and
Natural Science Foundation of SZU (grant no. 000346) and the Shenzhen Research
Foundation for Basic Research, China (Nos. JCYJ20180305124149387).

(a) Image

(b) Backpro [13]

(c) DSC

(d) Label

Figure 5: Examples of segmentation result. (a) Image, (b) Backprop [13], (c)
DSC, (d) Groundtruth.

## References

  * [1] M. Juneja, A. Vedaldi, C. Jawahar, and A. Zisserman, “Blocks that shout: Distinctive parts for scene classification,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2013, pp. 923–930.
  * [2] J. Long, E. Shelhamer, and T. Darrell, “Fully convolutional networks for semantic segmentation,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 3431–3440.
  * [3] S. Wang, H. Lu, F. Yang, and M.-H. Yang, “Superpixel tracking,” in _2011 International Conference on Computer Vision_. IEEE, 2011, pp. 1323–1330.
  * [4] J. Shi and J. Malik, “Normalized cuts and image segmentation,” _Departmental Papers (CIS)_ , p. 107, 2000.
  * [5] P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph-based image segmentation,” _International journal of computer vision_ , vol. 59, no. 2, pp. 167–181, 2004.
  * [6] L.-C. Chen, G. Papandreou, I. Kokkinos, K. Murphy, and A. L. Yuille, “Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 40, no. 4, pp. 834–848, 2017.
  * [7] H. Zhao, J. Shi, X. Qi, X. Wang, and J. Jia, “Pyramid scene parsing network,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 2881–2890.
  * [8] P. Arbelaez, M. Maire, C. Fowlkes, and J. Malik, “Contour detection and hierarchical image segmentation,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 33, no. 5, pp. 898–916, 2010.
  * [9] M.-Y. Liu, O. Tuzel, S. Ramalingam, and R. Chellappa, “Entropy rate superpixel segmentation,” in _CVPR 2011_. IEEE, 2011, pp. 2097–2104.
  * [10] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Süsstrunk, “Slic superpixels compared to state-of-the-art superpixel methods,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 34, no. 11, pp. 2274–2282, 2012.
  * [11] Z. Li and J. Chen, “Superpixel segmentation using linear spectral clustering,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2015, pp. 1356–1363.
  * [12] Y.-J. Liu, C.-C. Yu, M.-J. Yu, and Y. He, “Manifold slic: A fast method to compute content-sensitive superpixels,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 651–659.
  * [13] A. Kanezaki, “Unsupervised image segmentation by backpropagation,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 1543–1547.
  * [14] X. Xia and B. Kulis, “W-net: A deep model for fully unsupervised image segmentation,” _arXiv preprint arXiv:1711.08506_ , 2017.
  * [15] B. Kim and J. C. Ye, “Mumford-shah loss functional for image segmentation with deep learning,” _IEEE Transactions on Image Processing_ , 2019.
  * [16] X. Ji, J. F. Henriques, and A. Vedaldi, “Invariant information clustering for unsupervised image classification and segmentation,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 9865–9874.
  * [17] J. Xie, R. Girshick, and A. Farhadi, “Unsupervised deep embedding for clustering analysis,” in _International conference on machine learning_ , 2016, pp. 478–487.
  * [18] J. Yang, D. Parikh, and D. Batra, “Joint unsupervised learning of deep representations and image clusters,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 5147–5156.
  * [19] X. Yang, C. Deng, F. Zheng, J. Yan, and W. Liu, “Deep spectral clustering using dual autoencoder network,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 4066–4075.
  * [20] Y. Cheng, “Mean shift, mode seeking, and clustering,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 17, no. 8, pp. 790–799, 1995\.
  * [21] D. Comaniciu and P. Meer, “Mean shift: A robust approach toward feature space analysis,” _IEEE Transactions on pattern analysis and machine intelligence_ , vol. 24, no. 5, pp. 603–619, 2002.
  * [22] C. Wang, B. Yang, and Y. Liao, “Unsupervised image segmentation using convolutional autoencoder with total variation regularization as preprocessing,” in _2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2017, pp. 1877–1881.