Superpixel Sampling Networks
Varun Jampani Deqing Sun Ming-Yu Liu Ming-Hsuan Yang Jan Kautz




headings




 




Superpixel Sampling Networks


Jampani et al.










^1NVIDIA  ^2UC Merced 

	 {vjampani,deqings,mingyul,jkautz}@nvidia.com, mhyang@ucmerced.edu


Superpixel Sampling Networks
    Varun Jampani^1, Deqing Sun^1, Ming-Yu Liu^1, 
 Ming-Hsuan Yang^1,2, Jan Kautz^1
    December 30, 2023
====================================================================================




Superpixels provide an efficient low/mid-level representation of image data, which greatly reduces the number of image primitives for subsequent vision tasks. Existing superpixel algorithms 
are not differentiable, making them difficult to integrate into otherwise end-to-end trainable deep neural networks. We develop a new differentiable model for superpixel sampling that
leverages deep networks for learning superpixel segmentation. The resulting 
Superpixel Sampling Network (SSN) is end-to-end trainable, which allows learning task-specific superpixels with flexible loss functions and has fast runtime. Extensive experimental analysis indicates that SSNs not only
outperform existing superpixel algorithms on traditional segmentation benchmarks, but can also learn superpixels for other tasks. In addition, SSNs can be easily integrated into downstream deep networks resulting in performance improvements.







§ INTRODUCTION



Superpixels are an over-segmentation of an image that is formed by grouping image pixels <cit.> based on 

low-level image properties. They provide a perceptually meaningful tessellation of image content, thereby reducing the number of image primitives for subsequent image processing. Owing to their
representational and computational efficiency, superpixels have become an established low/mid-level image representation and are widely-used in computer vision algorithms such as object detection <cit.>, 
semantic segmentation <cit.>,
saliency estimation <cit.>,
optical flow estimation <cit.>, 
depth estimation <cit.>, tracking <cit.>
to name a few. 

Superpixels are especially widely-used in traditional energy minimization
frameworks, where a low number of image primitives greatly reduce the optimization 
complexity. 



The recent years have witnessed a dramatic increase in the adoption of deep learning for
a wide range of computer vision problems. With the exception of a few methods (e.g., <cit.>),
superpixels are scarcely used in conjunction with modern deep networks. There are two main reasons for this.
First, the standard convolution operation, which forms the basis of most deep architectures, is usually defined over regular grid lattices and becomes inefficient when operating over irregular superpixel lattices.

Second, existing superpixel algorithms are non-differentiable and thus using superpixels in deep networks introduces non-differentiable modules in otherwise end-to-end trainable network architectures.


In this work, we alleviate the second issue by proposing a new deep differentiable algorithm for superpixel segmentation. We start by revisiting the widely-used  Simple Linear Iterative Clustering (SLIC) superpixel algorithm <cit.> 
and turn it into a differentiable algorithm by relaxing the nearest neighbor constraints present in SLIC. This new differentiable algorithm allows for end-to-end training and enables us to leverage powerful deep networks for learning superpixels instead of using traditional hand-crafted features. This combination of a deep network with differentiable SLIC forms our end-to-end trainable superpixel algorithm which we call Superpixel Sampling Network (SSN). 

Fig. <ref> shows an overview of the proposed SSN. 

A given input image is first passed through a deep network producing features at each pixel. These deep features are then passed onto the differentiable SLIC, which performs iterative clustering, resulting in the desired superpixels. The entire network is end-to-end trainable. The differentiable nature of SSN allows the use of flexible loss functions for learning task-specific superpixels. Fig. <ref> shows some sample SSN generated superpixels.





Experimental results on 3 different segmentation benchmark datasets including  
BSDS500 <cit.>,
Cityscapes <cit.> and  
PascalVOC <cit.> indicate that the proposed
superpixel sampling network (SSN) performs favourably against existing prominent superpixel algorithms, 
while also being faster. We also demonstrate that by simply integrating our SSN framework into an existing semantic segmentation network <cit.> that uses superpixels, performance improvements are achieved. In addition, we demonstrate the flexibility of SSN in learning superpixels for other vision tasks. Specifically, in a proof-of-concept experiment on the Sintel optical flow dataset <cit.>, we demonstrate how we can learn superpixels that better align with optical flow boundaries rather than standard object boundaries.

The proposed SSN has the following favorable properties in comparison to existing superpixel algorithms:

    
  * End-to-end trainable: SSNs are end-to-end trainable and can be easily integrated into other deep network architectures.
    
    To the best of our knowledge, this is the first end-to-end trainable superpixel algorithm.
    
  * Flexible and task-specific: SSN allows for learning with flexible loss functions resulting in the learning of task-specific superpixels.
    
  * State-of-the-art performance: Experiments on a wide range of benchmark datasets show that SSN outperforms existing superpixel algorithms.
    
  * Favorable runtime: SSN also performs favorably against prominent superpixel algorithms in terms of runtime, making it amenable to learn on large datasets and also effective for practical applications.





§ RELATED WORK



Superpixel algorithms.
Traditional superpixel algorithms can be broadly classified into graph-based and clustering-based 
approaches. Graph-based approaches formulate the superpixel segmentation as a graph-partitioning
problem where graph nodes are represented by pixels and the edges denote the strength
of connectivity between adjacent pixels. Usually, the graph partitioning is performed by solving
a discrete optimization problem. 

Some widely-used algorithms in this category include
the normalized-cuts <cit.>, Felzenszwalb and Huttenlocher 
(FH) <cit.>, 
and the entropy rate superpixels (ERS) <cit.>.
As discrete optimization involves discrete variables, the optimization objectives are
usually non-differentiable making it difficult to leverage deep networks in graph-based
approaches.





Clustering-based approaches, on the other hand, leverage traditional clustering techniques such as
k-means for superpixel segmentation. 

Widely-used algorithms in this category include
SLIC <cit.>, LSC <cit.>, and Manifold-SLIC <cit.>.
These methods mainly do k-means clustering but differ in their feature representation.
While the SLIC <cit.> represents each pixel as a 5-dimensional positional
and Lab color features (XYLab features), LSC <cit.> method projects 
these 5-dimensional features on to a 10-dimensional space and performs clustering 
in the projected space.
Manifold-SLIC <cit.>, on the other hand, uses a 2-dimensional manifold
feature space for superpixel clustering.
While these clustering algorithms require iterative updates, a non-iterative clustering scheme for superpixel segmentation is proposed in the SNIC method <cit.>.
The proposed approach is also a clustering-based approach. However, unlike existing techniques,
we leverage deep networks to learn features for superpixel clustering via an end-to-end training framework.





As detailed in a recent survey paper <cit.>, other techniques are used for superpixel segmentation, including watershed transform <cit.>, geometric flows <cit.>, graph-cuts <cit.>, mean-shift <cit.>, and hill-climbing <cit.>. However, these methods all
rely on hand-crafted features and it is non-trivial to incorporate deep networks into these techniques. A very recent technique of SEAL <cit.> proposed a way to learn deep features for superpixel segmentation by bypassing the gradients through non-differentiable superpixel algorithms. Unlike our SSN framework,
SEAL is not end-to-end differentiable.



Deep clustering.
Inspired by the success of deep learning for supervised tasks, several methods investigate the use of deep networks for unsupervised data clustering. Recently, Greff  <cit.> propose the neural expectation maximization framework where they model the posterior distribution of cluster labels using deep networks and unroll the iterative steps in the EM procedure for end-to-end training.
In another work <cit.>, the Ladder network <cit.> is used to model a hierarchical latent variable model for clustering. Hershey  <cit.> propose a deep learning-based clustering framework for separating and segmenting audio signals. Xie <cit.> propose a deep embedded clustering framework, for simultaneously learning feature representations and cluster assignments. 


In a recent survey paper, Aljalbout <cit.> give a taxonomy of deep learning based clustering methods. 
In this paper, we also propose a deep learning-based clustering algorithm. Different 
from the prior work, our algorithm is tailored for the superpixel segmentation task where we use image-specific constraints. Moreover, our framework can easily incorporate other vision objective functions for learning task-specific superpixel representations.




§ PRELIMINARIES




At the core of SSN is a differentiable clustering technique that is inspired by the
SLIC <cit.> superpixel algorithm. Here, we briefly review the SLIC 
before describing our SSN technique in the next section.
SLIC is one of the simplest and
also one of the most widely-used superpixel algorithms. It is easy to implement,
has fast runtime and also produces compact and uniform superpixels.



Although there are several different variants <cit.> of SLIC algorithm, in the original
form, SLIC is a k-means clustering performed on image pixels in a five dimensional
position and color space (usually scaled XYLab space).
Formally, given an image I ∈ℝ^n × 5, with 5-dimensional
XYLab features at n pixels, the task of superpixel computation is to assign each
pixel to one of the m superpixels i.e., to compute the pixel-superpixel
association map H ∈{0,1,⋯,m-1}^n × 1.
The SLIC algorithm operates as follows. First, we sample 
initial cluster (superpixel) centers S^0 ∈ℝ^m × 5 in the 
5-dimensional space. This sampling is usually done
uniformly across the pixel grid with some local perturbations based on image gradients.
Given these initial superpixel centers S^0, the SLIC algorithm proceeds in an iterative manner
with the following two steps in each iteration t:

    
  * Pixel-Superpixel association: Associate each pixel to the nearest superpixel
    center in the five-dimensional space, i.e., compute the new superpixel assignment at each
    pixel p, 
    
    H_p^t = i ∈{0,...,m-1}minD(I_p, S^t-1_i),

    where D denotes the distance computation D(a,b) = ||a-b||^2.
    
  * Superpixel center update: Average pixel features (XYLab) inside each
    superpixel cluster to obtain new superpixel cluster centers S^t. For each superpixel i,
    we compute the centroid of that cluster,
    
    S^t_i = 1/Z_i^t∑_p | H_p^t = i I_p,

    where Z_i^t denotes the number of pixels in the superpixel cluster i.

These two steps form the
core of the SLIC algorithm and are repeated until either convergence or for a fixed 
number of iterations. Since computing the distance D in Eq. <ref> 
between all the pixels and superpixels is time-consuming, this computation is usually constrained
to a fixed neighborhood around each superpixel center.
At the end, depending on the application, there is an optional step
of enforcing spatial connectivity across pixels in each superpixel cluster. 

More details regarding the SLIC algorithm can be found in Achanta  <cit.>.

In the next
section, we elucidate how we modify the SLIC algorithm to develop SSN.





§ SUPERPIXEL SAMPLING NETWORKS


As illustrated in Fig. <ref>, SSN is composed of two parts: A deep network
that generates pixel features, which are then passed on to differentiable SLIC. 
Here, we first describe the differentiable SLIC followed by the 
SSN architecture.



 §.§ Differentiable SLIC




Why is SLIC not differentiable? A closer look at all the computations
in SLIC shows that the non-differentiability arises because of the
computation of pixel-superpixel associations, which involves a non-differentiable
nearest neighbor operation. This nearest neighbor computation also forms the
core of the SLIC superpixel clustering and thus we cannot avoid this operation.

A key to our approach is to convert the nearest-neighbor operation into a
differentiable one. Instead of computing hard pixel-superpixel 
associations H ∈{0,1,⋯,m-1}^n × 1 (in Eq. <ref>),
we propose to compute soft-associations
Q ∈ℝ^n × m between pixels and superpixels. 
Specifically, for a pixel p and superpixel i at iteration t,
we replace the nearest-neighbor computation (Eq. <ref>) in
SLIC with the following pixel-superpixel association.




    Q_pi^t = e^-D(I_p,S_i^t-1) = e^-||I_p - S_i^t-1||^2



Correspondingly, the computation of new superpixels cluster centers 
(Eq. <ref>) is modified as the weighted sum of pixel features,




    S^t_i = 1/Z_i^t∑_p=1^n Q_pi^t I_p,

where Z_i^t = ∑_p Q_pi^t is the normalization constant. For convenience, we refer
to the column normalized Q^t as Q̂^̂t̂ and thus we can write the above superpixel
center update as S^t = Q̂^̂t̂^⊤ I. The size of Q is n × m and even
for a small number of superpixels m, it is prohibitively expensive to compute Q_pi
between all the pixels and superpixels. Therefore, we constrain the distance computations
from each pixel to only 9 surrounding superpixels as illustrated using the red and green
boxes in Fig. <ref>. For each pixel in the green box, only the surrounding
superpixels in the red box are considered for computing the association.
This brings down the size of Q from n × m to n × 9,
making it efficient in terms of both computation
and memory. This approximation in the Q computation is similar in spirit
to the approximate nearest-neighbor search in SLIC.






Now, both the computations in each SLIC iteration are completely differentiable and we
refer to this modified algorithm as differentiable SLIC. 
Empirically, we observe that replacing the hard pixel-superpixel associations in SLIC
with the soft ones in differentiable SLIC does not result in any performance degradations. 
Since this new superpixel algorithm
is differentiable, it can be easily integrated into any deep network architecture.
Instead of using manually designed pixel features I_p, we can leverage deep feature
extractors and train the whole network end-to-end. In other words, we replace the image
features I_p in the above computations (Eq. <ref> and <ref>)
with k dimensional pixel features F_p ∈ℝ^n × k 
computed using a deep network. We refer to this coupling of deep networks with the
differentiable SLIC as Superpixel Sampling Network (SSN). 

Algorithm <ref> outlines all the computation steps in SSN. The algorithm starts with
deep image feature extraction using a CNN (line 1). We initialize the superpixel
cluster centers (line 2)
with the average pixels features in an initial regular superpixel grid (Fig. <ref>). 
Then, for v iterations, we iteratively update pixel-superpixel associations and superpixel
centers, using the above-mentioned computations (lines 3-6).
Although one could directly use soft pixel-superpixel associations Q for several downstream
tasks, there is an optional step of converting soft associations to hard ones (line 7), depending on the application needs. 

In addition, like in the original SLIC algorithm, we can optionally enforce spatial connectivity
across pixels inside each superpixel cluster. This is accomplished by merging the superpixels,
smaller than certain threshold, with the surrounding ones and then assigning a unique cluster ID
for each spatially-connected component. Note that these two optional steps (lines 7, 8) are not
differentiable.






Mapping between pixel and superpixel representations. For some downstream applications
that use superpixels, pixel representations are mapped onto superpixel representations
and vice versa. With the traditional superpixel algorithms, which provide hard clusters, this
mapping from pixel to superpixel representations is done via averaging inside each cluster 
(Eq. <ref>). The inverse mapping from superpixel to pixel representations is done by
assigning the same superpixel feature to all the pixels belonging to that superpixel.
We can use the same pixel-superpixel mappings with SSN superpixels as well, using the
hard clusters (line 7 in Algorithm <ref>) obtained from SSN.

However, since this computation of hard-associations is not differentiable, it may not be desirable
to use hard clusters when integrating into an end-to-end trainable system. 
It is worth noting that the soft pixel-superpixel associations generated by SSN can also be easily used for mapping between pixel and superpixel representations. Eq. <ref> already
describes the mapping from a pixel to superpixel representation
which is a simple matrix multiplication with the transpose of column-normalized Q matrix: 
S = Q̂^⊤F, where F and S denote pixel and superpixel representations respectively.
The inverse mapping from superpixel to pixel representation is done by multiplying
the row-normalized Q, denoted as Q̃, with the superpixel representations,
F = Q̃ S. Thus the pixel-superpixel feature mappings are
given as simple matrix multiplications with the association matrix and are differentiable.
Later, we will make use of these mappings in designing the loss functions to train SSN.
 



 §.§ Network Architecture


Fig. <ref> shows the SSN network architecture. 
The CNN for feature extraction
is composed of a series of convolution layers interleaved with 
batch normalization <cit.> (BN)
and ReLU activations. We use max-pooling, which downsamples the input 
by a factor of 2, after the 2^nd and 4^th convolution layers to increase the receptive
field. We bilinearly upsample the 4^th and 6^th convolution layer outputs 
and then concatenate with the 2^nd convolution layer output to pass
onto the final convolution layer.
We use 3 × 3 convolution filters with
the number of output channels set to 64 in each layer, 
except the last CNN layer which outputs k-5 channels.
We concatenate this k-5 channel output with the XYLab of the given image resulting
in k-dimensional pixel features.
We choose this CNN architecture for its simplicity and efficiency. Other network 
architectures are conceivable. 
The resulting k dimensional features are passed onto the two modules of differentiable SLIC
that iteratively updates pixel-superpixel associations and superpixel centers for v iterations.
The entire network is end-to-end trainable.




 §.§ Learning Task-Specific Superpixels


One of the main advantages of end-to-end trainable SSN is the flexibility in terms of loss 
functions, which we can use to learn task-specific superpixels. 
Like in any CNN, we can couple SSN with
any task-specific loss function resulting in the learning of superpixels that are
optimized for downstream computer vision tasks.
In this work, we focus on optimizing the representational
efficiency of superpixels i.e., learning superpixels that can 
efficiently represent a scene
characteristic such as semantic labels, optical flow, depth etc. 
As an example, if we want to learn superpixels that are going to be used for 
downstream semantic segmentation task, it is desirable to produce superpixels that
adhere to semantic boundaries. To optimize for representational efficiency, 
we find that the combination of a task-specific reconstruction loss and a compactness loss performs well.


Task-specific reconstruction loss. We denote the pixel properties  
that we want to represent
efficiently with superpixels as R ∈ℝ^n × l. 
For instance, R can be semantic
label (as one-hot encoding) or optical flow maps. 
It is important to note that we do not have access to R during the test time, i.e., SSN predicts
superpixels only using image data. 
We only use R during training
so that SSN can learn to predict superpixels suitable to represent R.
As mentioned previously in Section <ref>, 
we can map the pixel properties onto superpixels using the column-normalized 
association matrix Q̂, R̆ = Q̂^⊤R, where 
R̆∈ℝ^m × l. The resulting superpixel representation R̆ 
is then mapped back onto pixel representation R^* using
row-normalized association matrix Q̃, R^* = Q̃ S, 
where R^* ∈ℝ^n × l. Then the reconstruction loss is given as



    L_recon = ℒ(R, R^*) = ℒ(R, Q̃Q̂^⊤R)

where ℒ(.,.) denotes a task-specific loss-function.

In this work, for segmentation tasks, we used cross-entropy loss for ℒ
and used L1-norm for learning superpixels for optical flow.


Here Q denotes the association matrix Q^v after the final iteration of differentiable SLIC.
We omit v for convenience.


Compactness loss. In addition to the above loss,
we also  use a compactness loss to encourage superpixels to be spatially compact i.e.,
to have lower spatial variance inside each superpixel cluster. Let I^xy denote positional
pixel features. We first map these positional features into our superpixel representation,
S^xy = Q̂^⊤I^xy. Then, we do the inverse mapping onto the pixel representation
using the hard associations H, instead of soft associations Q, by assigning the same
superpixel positional feature to all the pixels belonging to that superpixel,
I̅_p^xy = S_i^xy | H_p = i. The compactness loss is defined as the following L2 norm:



    L_compact = ||I^xy - I̅^xy ||_2.



This loss encourages superpixels to have lower spatial variance.



The flexibility of SSN allows using many other loss functions,
which makes for interesting future research.
The overall loss we use in this work is a combination of these two loss functions,
L = L_recon + λ L_compact, where we set λ to 10^-5 in all our
experiments.





 §.§ Implementation and Experiment Protocols


We implement the differentiable SLIC as neural network layers using CUDA in the Caffe neural
network framework <cit.>. All the experiments are performed using Caffe 
with the Python interface. 

We use scaled XYLab 
features as input to the SSN, with position and color feature scales represented
as γ_pos and γ_color respectively. The value of γ_color 
is independent of the number of superpixels and is set to 0.26 with
color values ranging between 0 and 255. The value of γ_pos depends on the
number of superpixels, γ_pos = ηmax(m_w/n_w, m_h/n_h), 
where m_w,n_w and m_h,n_h denotes
the number of superpixels and pixels along the image width and height respectively. 
In practice, we observe that η = 2.5 performs well.


For training, we use image patches of size 201 × 201 and
100 superpixels. In terms of data augmentation, we use left-right flips and for the
small BSDS500 dataset <cit.>, 
we use an additional data augmentation of random
scaling of image patches. For all the experiments, we use
Adam stochastic optimization <cit.> with a
batch size of 8 and a learning rate of 0.0001. Unless otherwise mentioned,
we trained the models for 500K iterations and choose the final trained models
based on validation accuracy. 





For the ablation studies, we trained models with varying parameters for 200K iterations. 
It is important to note that we use a single trained SSN model
for estimating varying number of superpixels by scaling the input positional
features as described above. 
We use 5 iterations (v=5) of differentiable SLIC for training and used 10 iterations
while testing as we observed only marginal performance gains with more iterations.

Refer to <https://varunjampani.github.io/ssn/> for the code and trained models.




§ EXPERIMENTS



We conduct experiments on 4 different benchmark datasets. We first demonstrate the use of
learned superpixels with experiments on the prominent superpixel benchmark BSDS500 <cit.> 
(Section <ref>). We then demonstrate the use of task-specific superpixels on the
Cityscapes <cit.> and PascalVOC <cit.> datasets for semantic segmentation (Section <ref>),
and on MPI-Sintel <cit.> dataset for optical flow (Section <ref>).
In addition, we demonstrate the use of SSN superpixels in a downstream semantic segmentation
network that uses superpixels (Section <ref>).




 §.§ Learned Superpixels



We perform ablation studies and evaluate against other superpixel techniques on
the BSDS500 benchmark dataset <cit.>. 

BSDS500 consists of 
200 train, 100 validation, and 200 test images. Each image is annotated
with ground-truth (GT) segments from multiple annotators. 
We treat each annotation as
as a separate sample resulting in 1633 training/validation pairs and
1063 testing pairs. 

In order to learn superpixels that adhere to GT segments, 
we use GT segment labels in the reconstruction loss 
(Eq. <ref>). Specifically, we represent GT segments in each
image as one-hot encoding vectors and use that as pixel properties R 
in the reconstruction loss.

We use the cross-entropy loss for ℒ in Eq. <ref>. 
Note that, unlike in the semantic segmentation task where the GT labels 
have meaning, GT segments in this dataset
do not carry any semantic meaning.



This does not pose any
issue to our learning setup as both the SSN and reconstruction loss are 
agnostic to the meaning of pixel properties R. 



The reconstruction loss generates a loss value using the given input signal R
and its reconstructed version R^* and does not consider whether the meaning
of R is preserved across images.


Evaluation metrics. Superpixels are useful in a wide range of
vision tasks and several metrics exist for evaluating superpixels.
In this work, we consider Achievable Segmentation Accuracy (ASA) as our primary
metric while also reporting boundary metrics such as Boundary Recall (BR)
and Boundary Precision (BP) metrics. 




ASA score represents the upper bound on the accuracy achievable by any segmentation
step performed on the superpixels. Boundary precision and recall on the other
hand measures how well the superpixel boundaries align with the GT boundaries.
We explain these metrics in more detail in the supplementary material.














The higher these scores, the better is the segmentation result.

We report the average ASA and boundary metrics by varying the 
average number of generated superpixels. 
A fair evaluation of boundary precision and recall expects superpixels to be 
spatially connected. 

Thus, for the sake of unbiased comparisons, we follow the optional
post-processing of computing hard clusters and enforcing spatial connectivity
(lines 7–8 in Algorithm <ref>) on SSN superpixels.


Ablation studies. 



We refer to our main model illustrated
in Fig. <ref>, with 7 convolution layers in deep network, as
SSN_deep.

As a baseline model, we evalute the superpixels generated 
with differentiable SLIC that takes pixel XYLab features as input. 
This is similar to standard SLIC algorithm, which we
refer to as SSN_pix and has no trainable parameters. As an another baseline
model, we replaced the deep network with a single convolution layer that learns
to linearly transform input XYLab features, which we refer to as SSN_linear.

Fig. <ref> shows the average ASA and BR scores for these different
models with varying feature dimensionality k and the number of iterations v
in differentiable SLIC. The ASA and BR of SSN_linear is already reliably
higher than the baseline SSN_pix showing the importance of our loss functions
and back-propagating the loss signal through the superpixel algorithm. SSN_deep

further improves ASA and BR scores by a large
margin. We observe slightly better scores with higher feature dimensionality k
and also more iterations v. For computational reasons, we choose
k=20 and v=10 and from here on refer to this model as SSN_deep.






Comparison with the state-of-the-arts. Fig. <ref>
shows the ASA and precision-recall comparison of SSN with state-of-the-art 
superpixel algorithms. We compare with the following prominent algorithms:
SLIC <cit.>, SNIC <cit.>, 
SEEDS <cit.>, LSC <cit.>, ERS <cit.>,
ETPS <cit.> and SCALP <cit.>.
Plots indicate that SSN_pix performs similarly to
SLIC superpixels, showing that the performance of SLIC does not drop
when relaxing the nearest neighbor constraints. Comparison with other
techniques indicate that SSN performs considerably better in terms of both 
ASA score and precision-recall. 
Fig. <ref>
shows a visual result comparing SSN_pix and SSN_deep and,
Fig. <ref> shows visual results comparing 
SSN_deep with state-of-the-arts. Notice that SSN_deep superpixels
smoothly follow object boundaries and are also more concentrated near
the object boundaries.




 §.§ Superpixels for Semantic Segmentation



In this section, we present results on the semantic segmentation benchmarks of
Cityscapes <cit.> and PascalVOC <cit.>.
The experimental settings are quite similar to that of the previous section with
the only difference being the use of semantic labels as the pixel properties R
in the reconstruction loss. Thus, we encourage SSN to learn superpixels that adhere
to semantic segments.





[14]r0pt
  
    Model     GPU/CPU     Time (ms)

    SLIC <cit.>     CPU     350 

  SNIC <cit.>     CPU     810 

  SEEDS <cit.>     CPU     160 

  LSC <cit.>     CPU     1240 

  ERS <cit.>     CPU     4600 

  SEAL-ERS <cit.>     GPU-CPU     4610

  GSLICR <cit.>     GPU     10 

  SSN models          

  SSN_pix,v=10     GPU     58 

  SSN_deep,v=5,k=10     GPU     71

  SSN_deep,v=10,k=10     GPU     90

  SSN_deep,v=5,k=20     GPU     80

  SSN_deep,v=10,k=20     GPU     101

  
Runtime AnalysisAverage runtime (in ms) of different superpixel
techniques, for computing 1000 superpixels
on a 512 × 1024 cityscapes image.




Cityscapes.
Cityscapes is a large scale urban scene understanding benchmark with pixel accurate
semantic annotations. 

We train SSN with the 2975 train images and evaluate on the 500
validation images. 

For the ease of experimentation, we experiment with
half-resolution (512 × 1024) images.

Plots in Fig. <ref> shows that SSN_deep performs 
on par with SEAL <cit.> superpixels in terms of ASA
while being better in terms of precision-recall. 

We show a visual result
in Fig. <ref> with more in the supplementary.




Runtime analysis. We report the approximate runtimes of different 
techniques, for computing 1000 superpixels on a 512 × 1024 
cityscapes image in Table <ref>. We compute GPU runtimes using an
NVIDIA Tesla V100 GPU. The runtime comparison between SSN_pix and SSN_deep
indicates that a significant portion of the SSN computation time is due to
the differentiable SLIC. 




The runtimes indicate that SSN is considerably faster than the implementations of 
several superpixel algorithms. 




















PascalVOC.
PascalVOC2012 <cit.> is another widely-used semantic 
segmentation benchmark, where we train SSN with 1464 train images and validate
on 1449 validation images. Fig. <ref>(a) shows the ASA scores
for different techniques. We do not analyze boundary scores on this dataset as the
GT semantic boundaries are dilated with an ignore label.

The ASA scores indicate that SSN_deep outperforms other techniques.
We also evaluated the BSDS-trained model on this dataset and observed only a marginal
drop in accuracy (`SSN_deep-BSDS' in Fig. <ref>(a)).
This shows the generalization and robustness of SSN to different datasets. An example 
visual result is shown in Fig. <ref> with more in the supplementary.


[11]r0pt
  
    
        Method      IoU 

        DeepLab <cit.>                    68.9 

        + CRF <cit.>                     72.7 

        + BI (SLIC) <cit.>     74.1 

        + BI (SSN_deep)           75.3 

        
SSN with a downstream CNNIoU improvements, on the VOC2012 
test data, with the integration of SSN into the bilateral inception (BI) network from <cit.>.



We perform an additional experiment where we plug SSN
into the downstream semantic segmentation network of <cit.>,

The network in <cit.>
has bilateral inception layers that makes use of superpixels for long-range
data-adaptive information propagation across intermediate CNN representations. 

Table <ref>
shows the Intersection over Union (IoU) score

for this joint model evaluated on the test data. The
improvements in IoU with respect to original SLIC superpixels 
used in <cit.> shows that SSN can also bring performance
improvements to the downstream task networks that use superpixels.




 §.§ Superpixels for Optical Flow



To demonstrate the applicability of SSN for regression tasks as well, we
conduct a proof-of-concept experiment where we learn superpixels that adhere
to optical flow boundaries. 

To this end, we experiment
on the MPI-Sintel dataset <cit.> and 
use SSN to predict superpixels given a pair of input frames. 
We use GT optical flow as pixel properties R in the reconstruction loss 
(Eq. <ref>) and use L1 loss for ℒ, encouraging SSN
to generate superpixels that can effectively represent flow.

The MPI-Sintel dataset consists of 23 video sequences, which we split into
disjoint sets of 18 (836 frames) training 
and 5 (205 frames) validation sequences. To evaluate the superpixels,
we follow a similar strategy as for computing ASA. That is, for each
pixel inside a superpixel, we assign the average GT optical flow resulting
in a segmented flow. 
Fig. <ref> shows sample segmented flows obtained using different
types of superpixels. We then compute the Euclidean distance between
the  GT flow and the segmented flow, which is referred to as
end-point error (EPE). The lower the EPE value, the better the superpixels
are for representing flow. 







A sample result in Fig. <ref> shows that SSN_deep
superpixels are better aligned with the changes in the GT flow than other superpixels.
Fig. <ref>(b) shows the average EPE values
for different techniques where SSN_deep 
performs favourably against
existing superpixel techniques. This shows the usefulness of
SSN in learning task-specific superpixels.






§ CONCLUSION




We propose a novel superpixel sampling network (SSN) that 


leverages deep features learned via end-to-end training for
estimating task-specific superpixels. To our knowledge, this is the first deep superpixel
prediction technique that is end-to-end trainable. Experiments several benchmarks
show that SSN consistently performs favorably against 
state-of-the-art superpixel techniques, while also being faster.  


Integration of SSN into a semantic
segmentation network <cit.> also results in performance
improvements showing the usefulness of SSN in downstream computer vision
tasks. SSN is fast, easy to implement, can be easily integrated into other deep networks
and has good empirical performance.


SSN has addressed one of the main hurdles for incorporating superpixels into deep networks
which is the non-differentiable nature of existing superpixel algorithms.

The use of superpixels inside deep networks can have several advantages.
Superpixels can reduce the computational complexity, especially when processing high-resolution
images. Superpixels can also be used to enforce piece-wise constant assumptions and also help
in long-range information propagation <cit.>. 


We believe this work opens up new avenues in leveraging superpixels inside deep
networks and also inspires new deep learning techniques that use superpixels.




Acknowledgments. We thank Wei-Chih Tu for providing evaluation scripts.
We thank Ben Eckart for his help in the supplementary video.



splncs04








§ SUPPLEMENTARY MATERIAL


In Section <ref>, we formally define the
Acheivable Segmentation Accuracy (ASA) used for evaluating
superpixels. Then, in Section <ref>,
we report F-measure and Compactness scores with more visual results on different datasets.
We also include a supplementary video[<https://www.youtube.com/watch?v=q37MxZolDck>]
that gives an overview of Superpixel Sampling Networks (SSN) with a glimpse of experimental results.



 §.§ Evaluation Metrics



Here, we formally define the Achievable Segmentation Accuracy (ASA) metric that is 
used in the main paper. Given an image I with n pixels, let H ∈{0,1,⋯,m}^n × 1 denotes the superpixel segmentation with m superpixels.
H is composed of m disjoint segments, H = ⋃_j=1^m H^j, where
j^th segment is represented as H^j. Similarly, let G ∈{0,1,⋯,w}^n × 1 denotes ground-truth (GT) segmentation with w segments.
G = ⋃_l=1^w G^l, where G^l denotes l^th GT segment. 



ASA Score. The ASA score between a given superpixel segmentation H
and the GT segmentation G is defined as


    ASA(H,G) = 1/n∑_H^j ∈ Smax_G^l|H^j ∩ G^l|,


where |H^j ∩ G^l| denotes the number of overlapping pixels between S^j and
G^l. To compute ASA, we first find the GT segment
that overlaps the most with each of the superpixel segments and then sum the number of
overlapping pixels. As a normalization, we divide the number of overlapping pixels
with the number of image pixels n. In other words, ASA represents an upper bound
on the accuracy achievable by any segmentation step performed on the superpixels.



Boundary Precision-Recall. Boundary Recall (BR) measures how well the boundaries of superpixel segmentation aligns with the GT boundaries.
Higher BR score need not correspond to higher quality of superpixels.
Superpixels with high BR score can be irregular and may not be useful in practice.
Following reviewers' suggestions, we report Boundary Precision-Recall curves instead of 
just Boundary Recall scores. 

We also report F-measure and Compactness in the next section (Section <ref>).  
We use the evaluation scripts from <cit.> 
with default parameters to compute Boundary Precision-Recall, F-measure and Compactness.















 §.§ Additional Experimental Results





  §.§.§ Compactness and F-measure.



We compute compactness (CO) of 
different superpixels on the BSDS dataset (Fig. <ref>(a)). SSN superpixels 
have only slightly 
lower CO compared to widely-used SLIC showing the practical utility of SSN. 
SSN_deep has
similar CO as SSN_pix showing that training SSN, while improving ASA and boundary 
adherence, does not destroy compactness. 
More importantly, we find SSN to be flexible and responsive to task-specific loss functions 
and one could use more weight (λ) for the compactness loss (Eq. 6 in the main paper) 
if more compact superpixels are desired.
In addition, we also plot F-measure scores in Fig. <ref>(b). In summary,  SSN_deep also outperforms other techniques in terms of F-measure while
maintaining the compactness as that of SSN_pix. This shows the robustness of SSN with
respect to different superpixel aspects.





  §.§.§ Additional visual results.


In this section, we present additional visual results of different techniques and on different
datasets. Figs. <ref>, <ref> and <ref> show superpixel visual results
on three segmentation benchmarks of BSDS500 <cit.>, 
Cityscapes <cit.> and PascalVOC <cit.> respectively.
For comparisons, we show the superpixels obtained with 3 existing superpixel techniques of
SLIC <cit.>, LSC <cit.> and ERS <cit.>.
Fig. <ref> shows additional visual results on MPI-Sintel <cit.>
where we present sample segmented flows obtained using different types of superpixels.











