SIN: Superpixel Interpolation Network

Traditional superpixel segmentation algorithms can be roughly categorized as graph-based and clustering-based algorithms. Graph-based algorithms treat image pixels as graph nodes and pixel affinities as graph edges. Usually, superpixel segmentation problems are solved by graph-partitioning.  [17] applies the Normalized Cuts algorithm to produce the superpixel map. FH [6] defines an adaptive segmentation criterion to capture global image properties. ERS [14] proposes an objective function for superpixel segmentation, which consists of the entropy rate and the balancing term.

Clustering-based algorithms utilize clustering methods such as $k$-means for superpixel segmentation. SEEDS [4] starts from an initial superpixel partitioning and continuously exchanges pixels on the boundaries between neighboring superpixels. SLIC [1] adopts a $k$-means clustering approach to generate superpixels based on a 5-dimensional positional and $Lab$ color features. Owing to its simplicity and high performance, there are many variants [12, 15, 2] of SLIC. LSC [12] projects the 5-dimensional features to a 10-dimensional space and performs weighted $k$-means in the projected space. Manifold-SLIC [15] maps the image to 2-dimensional manifold feature space for superpixel clustering. SNIC [2] proposes a non-iterative scheme for superpixel segmentation. Traditional superpixel algorithms are mainly based on hand-crafted features, which often fail to preserve weak object boundaries. Most traditional algorithms are computed on CPU, so it is hard to achieve real-time speed. What’s more, we cannot integrate traditional methods into subsequent tasks in an end-to-end way because they are non-differentiable.

Recently, some researchers have focused on integrating deep networks into superpixel segmentation algorithms [24, 11, 29]. [24, 11] use a deep network to extract pixel features, which are then fed to a superpixel segmentation module. SEAL [24] develops the Pixel Affinity Net for affinity prediction and defines a new loss function which takes the segmentation error into account. These affinities are then passed to a graph-based algorithm to generate superpixels. To form an end-to-end trainable network, SSN [11] turns SLIC into a differentiable algorithm by relaxing the nearest neighbors’ constraints. FCN [29] combines feature extraction and superpixel segmentation into a single step. The proposed method employs a fully convolutional network to predict association scores between image pixels and regular grid cells. When utilizing superpixels generated by existing deep learning-based methods, a post-processing step is needed to handle orphan pixels. The step is not trainable and can only be computed on CPU, so existing deep learning-based methods cannot be integrated into downstream tasks in an end-to-end approach.

Most superpixel algorithms [6, 1, 12, 15, 24, 11, 29] do not explicitly enforce connectivity and there may exist some ”orphaned” pixels that do not belong to the same connected components. To correct this, SLIC [1] assigns these pixels the label of the nearest cluster. [11, 29] also apply a component connection algorithm to merge superpixels that are smaller than a certain threshold with the surrounding ones. These algorithms enforce connectivity using a post-processing step, whereas SNIC [2] enforces connectivity explicitly from the start. SNIC uses a priority queue to choose the next pixel to be assigned, and the queue is populated with pixels which are 4 or 8-connected to a currently growing superpixel. As far as we know, there is no method which utilizes learned features and enforces connectivity explicitly.

Our superpixels are obtained by initializing pixel-superpixel map and updating the map multiple times. Similar to the commonly adopted strategy in [4, 1, 2], we generate the initial superpixels by sampling the image $I\in\mathbb{R}^{H\times W\times 3}$ with a regular step $S$. By assigning each pixel to a unique superpixel, we get the initial pixel-superpixel map $M_{0}\in\mathbb{Z}^{h_{0}\times w_{0}}$. The values of $M_{0}$ denote ID of superpixels to which sampled pixels are assigned.

Superpixel segmentation is to find the final pixel-superpixel map $M\in\mathbb{Z}^{H\times W}$, which assigns all pixels to superpixels. The problem of finding $M$ can be seemed as expanding $M_{0}$ to $M$. Inspired by resizing image, we use interpolation to expand the matrix. The rule of interpolation is carefully designed to enforce spatial connectivity from the start and to be computed on GPU in parallel. As depicted in Figure1, the process of expanding $M_{0}$ to $M$ can be divided into multiple similar steps and each step consists of a horizontal interpolation and a vertical interpolation. As shown in Figure 2, when we expand pixel-superpixel map in horizontal/vertical dimension, we interpolate values among all neighboring elements in each row/column. The inserted values are the same as neighboring elements with certain probability. The probabilities(association scores) are computed by neural networks which we will introduce in Section 3.2.

In detail, we use $P\in\mathbb{R}^{H\times W}$ to denote image pixels. $P(i,j)$ represents the image pixel at the intersection of $i$-th row and $j$-th column. $M(i,j)$ is the superpixel to which $P(i,j)$ is assigned. In the initial step, we find partial connections between image pixels $P$ and superpixels. $M_{0}(i,j)$ represents the superpixel to which $P(i*S,j*S)$ is assigned.

To obtain $M$, we need to expand $M_{0}$ multiple times. At $l$-th expansion, we use $M_{l}^{h}\in\mathbb{Z}^{h_{l-1}\times w_{l}}$ and $M_{l}\in\mathbb{Z}^{h_{l}\times w_{l}}$ to denote pixel-superpixel maps after horizontal and vertical interpolation.

Figure 2 has shown a part of interpolation at $l$-th expansion. At $l$-th horizontal/vertical interpolation step, the inserted values are confirmed by association scores $A_{l}^{h}\in\mathbb{R}^{h_{l-1}\times(w_{l-1}-1)\times 2}$/$A_{l}\in\mathbb{R}^{(h_{l-1}-1)\times w_{l}\times 2}$ and neighboring superpixels $Q_{l}^{h}\in\mathbb{Z}^{h_{l-1}\times(w_{l-1}-1)\times 2}$/$Q_{l}\in\mathbb{Z}^{(h_{l-1}-1)\times w_{l}\times 2}$. $A_{l}^{h}(i,j,k)$ and $A_{l}(i,j,k)$ denote the probability of $i$-th row, $j$-th column inserted value is the same with its $k$-th neighbor. All association scores are obtained from multi-layer outputs of the neural network described in Section 3.2. $Q_{l}^{h}(i,j,k)$ and $Q_{l}(i,j,k)$ denote the $k$-th neighbor’s value of $i$-th row, $j$-th column inserted element. Neighboring superpixels are obtained from current pixel-superpixel map. We interpolate new elements among existing neighboring elements at each row/column, so a pair of existing neighboring elements’ values are neighboring superpixel IDs of the corresponding inserted element. According to association scores and neighboring superpixels, inserted values can only be same with one of their neighboring elements with certain probability.

We use a convolutional neural network similar to [29] to extract image feature $F_{0}\in\mathbb{R}^{h_{0}\times w_{0}\times c_{0}}$. We stack module $deconv\_h$ and $deconv\_v$ multiple times to extract multi-layer features $F_{l}^{h}\in\mathbb{R}^{h_{l-1}\times w_{l}\times c_{l}}$ and $F_{l}\in\mathbb{R}^{h_{l}\times w_{l}\times c_{l}}$, where $c_{l}$ denotes feature channels. $deconv\_h$ and $deconv\_v$ are transposed convolutional neural networks, in which stride are $(1,2)$ and $(2,1)$ respectively. Specially, $deconv\_h$ will reduce feature channels by half. $conv$ is a convolutional neural network, which transforms the multi-layer features to 2-dimensional association scores.

Our model is trained with ground truth segmentation labels $T\in\mathbb{Z}^{H\times W}$ from BSDS500. Every interpolation is to find partial connections between pixels and superpixels. To get loss of all connections, we need to compute partial loss at every interpolation. We define $s_{l}=S/2^{l}$ to simplify descriptions. The inserted values at $l$-th step in horizontal/vertical dimension are ID of superpixels to which pixels $U_{l}^{h}$ and $U_{l}$ are assigned. $U_{l}^{h}$ denotes the subtraction of pixels sampled by stride $(s_{l-1},s_{l})$ and $(s_{l-1},s_{l-1})$. $U_{l}$ denotes the subtraction of pixels sampled by stride $(s_{l},s_{l})$ and $(s_{l-1},s_{l})$. Partial ground truth connections $T_{l}^{h}$ and $T_{l}$ are segmentation labels of pixels $U_{l}^{h}$ and $U_{l}$. To speed up training process, we do not generate pixel-superpixel maps to compute loss. Instead, we utilize association scores to compute loss directly. Association scores $A_{l}^{h}$ and $A_{l}$ denote the probabilities of pixels assigned to neighboring superpixels. Inspired by tasks of classification, the ground truth labels $G_{l}^{h}$ and $G_{l}$ are defined as the indexes of neighboring superpixels to which pixels should be assigned. $G_{l}^{h}$ and $G_{l}$ can be inferred from $T_{l}^{h}$ and $T_{l}$. Owing to each inserted element has two neighbors, the ground truth labels are 0 or 1. If the neighboring superpixels ID of an inserted element are same, we will ignore it when computing loss. We define $\mathbb{I}_{l}^{h}$ and $\mathbb{I}_{l}$ to represent whether to consider the elements when computing loss. Loss of each interpolation at $l$-th step can be computed by:

where $L_{l}^{h}$ and $L_{l}$ denote the loss of horizontal and vertical at $l$-th step. $\mathcal{C}_{\mathbb{I}_{l}^{h}}$ and $\mathcal{C}_{\mathbb{I}_{l}}$ denote cross entropy loss functions, which only consider partial elements according to the values of $\mathbb{I}_{l}^{h}$ and $\mathbb{I}_{l}$.

Total loss $\mathcal{L}$ can be computed by:

where $w_{l}^{h}$ and $w_{l}^{v}$ denote weights of horizontal and vertical interpolation loss at $l$-th step.

Thanks to removing the post-processing step, our method can be integrated into subsequent tasks in an end-to-end way. The key to enforcing spatial connectivity from the start is the rule of interpolation. An expanding step consists of a horizontal interpolation and a vertical interpolation. The design ensures spatial connectivity of pixel-superpixel maps will not be destroyed by interpolations. Owing to initial pixel-superpixel map has spatial connectivity and interpolations preserve the property, the final pixel-superpixel map $M$ remains spatial connectivity. $M$ assigns all pixels to superpixels, so $M$ has spatial connectivity equals our SIN superpixels have spatial connectivity. In the following, we will first explain why the spatial connectivity of $M$ and superpixels are equivalent. Afterwards, we illustrate how interpolations preserve spatial connectivity of pixel-superpixel maps.

The fact that a superpixel has spatial connectivity means the set of all pixels in the superpixel is a connected set. We use $X_{i}$ to denote a set where elements have same value $i$ in $M$ and $X=\{X_{1},X_{2},\dots,X_{n}\}$ to denote all such sets. If all elements in $X$ are connected sets, $M$ has spatial connectivity. Spatial information of elements in $X_{i}$ equals spatial information of pixels assigned to superpixel $i$, so $X_{i}$ is a connected set represents superpixel $i$ has spatial connectivity. Evidently, $M$ has spatial connectivity equals all superpixels have spatial connectivity. All sets in $M_{0}$ only has one element, so $M_{0}$ has spatial connectivity definitely. If interpolations can preserve spatial connectivity, we can infer that $M$ has spatial connectivity.

Our scheme of interpolation is to insert elements among existing neighboring elements at each row/column. When we insert a element between a pair of neighbors, only sets including these three elements will be taken into consideration. If existing neighboring elements are in a same set, the inserted element will be added to the set and the set is still connected. If existing neighboring elements belong to different sets, the inserted element will be added to one of the sets, and the other will not change. The added set is still connected and spatial connectivity of the other will not be affected. We want to address that it is the design of interpolation preserves spatial connectivity. If we interpolate once at an expanding step and the inserted value is same with its 8-neighborhood, spatial connectivity of pixel-superpixel map will be destroyed. Above all, our method can enforce spatial connectivity explicitly through the delicate design of interpolation.

We present an ablation study where we evaluate different design choices of the image feature extraction and loss sum. Unlike [29], we do not take image features from previous layers into account to predict association scores. Our total loss is the sum of horizontal and vertical loss at each step, so we can compute average or weighted sum. In our final model, we choose weighted sum to compute total loss. For comparison, we include a baseline model which uses the previous features and current features(concat) to predict scores and simply sums the loss values averagely. We evaluate each of these design options of the network. Figure 8 shows that each of the 2 alternatives in our model performs better.