Superpixel Segmentation Based on Spatially Constrained Subspace Clustering

Superpixel segmentation aims at dividing the input image into some representative regions containing pixels with similar and consistent intrinsic properties, without any prior knowledge about the shape and size of each superpixel. In this paper, to alleviate the limitation of superpixel segmentation applied in practical industrial tasks that detailed boundaries are difficult to be kept, we regard each representative region with independent semantic information as a subspace, and correspondingly formulate superpixel segmentation as a subspace clustering problem to preserve more detailed content boundaries. We show that a simple integration of superpixel segmentation with the conventional subspace clustering does not effectively work due to the spatial correlation of the pixels within a superpixel, which may lead to boundary confusion and segmentation error when the correlation is ignored. Consequently, we devise a spatial regularization and propose a novel convex locality-constrained subspace clustering model that is able to constrain the spatial adjacent pixels with similar attributes to be clustered into a superpixel and generate the content-aware superpixels with more detailed boundaries. Finally, the proposed model is solved by an efficient alternating direction method of multipliers (ADMM) solver. Experiments on different standard datasets demonstrate that the proposed method achieves superior performance both quantitatively and qualitatively compared with some state-of-the-art methods.


I. INTRODUCTION
Superpixels are alternative primitives to represent the original pixels in an image based on certain intrinsic properties, such as coherent spatial relationship, and similar appearance. Instead of utilizing pixel entities directly, superpixels can provide semantic representation and reduce the dimension of primitives [1], [2], which have been widely applied in practical and industrial tasks of computer vision, such as saliency detection [3]- [20], feature selection [21], object recognition [22], background subtraction [23], image enhancement and reconstruction [24]- [26]. In recent years, numerous methods with diverse problem formulations have been proposed for superpixel segmentation [27]- [31] and achieved excellent performance in theoretical study. However, one obvious weakness of the existing superpixel methods is the limitation to adapt to the local image details, such as the content boundaries and object contours. And in many cases of practical problems and industrial tasks [3]- [5], [22], the local details are the key information, which should not be ignored. For most methods, the detailed boundaries of image content are still hard to be well preserved, due to the lack of the prior knowledge about the shape and size of the superpixels in an image. These methods have to increase the number of superpixels and reduce the superpixel size to achieve the detailed boundaries. This may usually lead to large data redundancy in the sparse area, which is unwillingness for practical tasks. How to balance the detailed information and superpixel number is a challenging problem for superpixel segmentation to be applied in industrial tasks.
To alleviate this problem, we suppose each superpixel with independent information comes from one distinct subspace, and formulate the superpixel segmentation as a subspace clustering problem [32]- [34]. Subspace clustering is an effective way to segment data drawn from different dimensions or subspaces, and has achieved impressive performance in some real-world tasks, such as face clustering [34] and foreground extraction [35]. Moreover, it also has been adopted in industrial applications, e.g., hyperspectral image classification based on superpixel-level subspace learning [36]- [38]. For superpixel segmentation, each superpixel is regarded as a subspace containing pixels with similar intrinsic attributes, such as similar texture, boundary, color and coherent spatial information, while pixels in different subspace have different properties. Then the solution to the subspace clustering corresponds to the segmentation of superpixels. By this way, the pixels in the unit containing independent semantic information are more probably segmented into one superpixel, no matter how small the unit area is. At the same time, the size of the superpixels in sparse area are relatively large according to the similar attributes of pixels. Consequently, the detailed content boundaries and the superpixel number can be better balanced, i.e., using less superpixels to preserve more detailed information.
Nevertheless, it is still a challenging work by inducing subspace clustering theory to superpixel segmentation directly. Different from the general sample data in clustering, pixels in an image have certain spatial correlation that only the similar pixels in adjacency tend to be clustered as one superpixel. Directly applying the conventional subspace clustering models to superpixel segmentation task can not excellently work since the spatial correlation of pixels is not taken into consideration. This may cause the confusion and segmentation error of content boundaries. In other words, we should consider the spatial constraints when using the subspace clustering for superpixel segmentation task. To this end, we devise a spatial regularization term to emphasize the spatial correlation, and propose a spatially constrained subspace clustering based superpixel segmentation model to generate superpixels with more accurate and detailed boundaries, which is more appropriate for practical and industrial tasks.
In this paper, considering the limitation of superpixel segmentation in the application of practical industrial tasks, we propose a novel spatially constrained subspace clustering based superpixel segmentation model to produce more adaptive superpixels. In summary, the contributions of this paper include: • Considering the challenge of pursuing detailed boundaries, we formulate the superpixel segmentation task as a subspace clustering problem to generate content-aware supeprixels with more detailed boundaries and fewer primitives. To the best of our knowledge, this is the first attempt to induce subspace clustering theory to solve the superpixel segmentation problem, and effectively alleviate the challenge in superpixel segmentation. • To enforce the spatial adjacent pixels with similar attributes to be clustered into a superpixel corresponding to a subspace, we design a spatial regularization term in the loss function to constrain the local adjacency when clustering pixels. The ablation study has verified the effectiveness of the spatial regularization term. • The extensive experiments and discussions on the widely used benchmarks and datasets demonstrate that the proposed method achieves superior performance both quantitatively and qualitatively. The paper is organized as follows. The related works are presented in Section II. In Section III, we propose a novel superpixel segmentation model. The comparative experimental results and analyses are presented in Section IV. Finally, Section V concludes this paper.
II. RELATED WORK Various superpixel segmentation algorithms have been proposed for different motivations and tasks. They can be classified into two categories: unsupervised approach and supervised approach.

A. Unsupervised Superpixel Segmentation Methods
Unsupervised approach mainly includes two categories: graph-based methods and clustering-based methods.
Normalized cut (Ncut) algorithm [39] is one of the representative graph-based methods, which first groups pixels into several large areas by normalized cut, and then adopts Kmeans to segment the large areas into small units. However, it suffers from high computational complexity cost and low boundary adherence, which limit its utilization. Considering the image topological structure, topology preserved regular superpixel (TPS) [2] algorithm was put out to produce relatively regular superpixel. However, it suffers from low adherence to boundaries due to the demand of regular superpixel shape. In contrast to TPS, lazy random walk (LRW) [27] algorithm achieves high object boundary adherence by iteratively optimizing an energy function based on texture measurement. Recently, approximately structural superpixels (ASS) [31] was proposed to generate approximately structural superpixels by an asymmetrically square-wise superpixel segmentation way, which can largely reduce data amount as well as preserve image content boundaries.
Turbopixel [40] is one of the early clustering-based methods, which adopts local image gradient and geometric flow to generate regular superpixel, but it suffers from the time consuming problem in practice. Simple linear iterative clustering (SLIC) [28] is widely used due to its high efficiency. SLIC adopts K-means clustering approach and changes the search area into a local area rather than the global searching in Kmeans, which largely reduces the computation complexity. As an extension of SLIC, Fast linear iterative clustering (FLIC) [30] is an active search method which emphasizes the neighboring continuity. Linear spectral clustering (LSC) [29] generates superpixels by mapping pixels into a high-dimensional space through a kernel function. Recently, Bayesian Adaptive Superpixel Segmentation (BASS) [41] is proposed to generate adaptive superpixels by a Bayesian mixture model. However, the number of superpixel cannot be predefined, which is not convenient for certain tasks that demand to initialize the number manually.

B. Supervised Superpixel Segmentation Methods
Supervised superpixel segmentation algorithms are mainly based on deep-learning based approaches. Recently, deep learning based methods for superpixel segmentation have been proposed to incorporate deep learning technique with traditional segmentation. There are three representative deep learning based superpixel segmentation methods, Segmentationaware Loss(SEAL) [42], Superpixel Sampling Networks(SSN) [43], and Superpixel Segmentation with Fully Convolutional Networks (FCN) [44].
SEAL adopts deep neural network and designs a segmentation-aware affinity learning method to keep weak object boundary in superpixel segmentation. SSN presents a differentiable superpixel sampling model which can be integrated into end-to-end trainable networks. FCN algorithm adopts a simple fully connected network to predict superpixel on regular image grids. Then, on the basis of the predicted

Global regularization Spatial regularization
Error Matrix ... × = + Fig. 1. The framework of our proposed method. Given an input image, we first construct the input data as a locality-constrained subspace clustering model with spatial regularization, and then work out the coding matrix by the proposed approach. Finally, the superpixels are generated via clustering the affinity graph of the coding matrix.  [28], FLIC [30], and LSC [29], respectively. (e) shows the result based on a naive subspace clustering method. We also show the result using our spatially constrained subspace clustering method in (f).
superpixel, it further develops a down-sampling/up-sampling scheme for deep networks to generate high-resolution output for intensive prediction tasks. By this way, the stereo matching network architecture can predict both superpixel and parallax.

III. PROPOSED METHOD
In this section, we first explore a naive subspace clustering model in superpixel segmentation, and analyze the irrationality of the simple integration. Then, we propose a novel localityconstrained subspace clustering model with spatial regularization for image superpixel segmentation. An overview of the proposed method is illustrated in Fig. 1.

A. Superpixels via Naive Subspace Clustering
Superpixels aims at representing the original image by some units containing pixels with similar properties, such as close appearance and spatial correlation. Subspace clustering finds diverse subspaces with different dimensions and bases, and clusters each data point in one subspace [34]. Each superpixel can be regarded as a subspace containing pixels with similar intrinsic attributes, such as similar texture, boundary, color and coherent spatial information, while pixels in different subspace have different properties. Then, superpixel segmentation problem can adopt subspace clustering theory to find the segmentation of these subspaces.
A naive way to solve this problem is to directly apply off-the-shelf subspace clustering algorithms (e.g., [34]) to superpixel segmentation by constructing an affinity matrix by learning effective representation coding. For efficiency, we use the extracted features from the raw pixel units rather than the raw pixel features as input. Here, a self-expressive model [34] is adopted to learn the affinity matrix for efficiency, and the data is explained by itself: a data point can be represented as a linear combination of other data points in the same subspace, i.e., X = XZ + E, where X = [x 1 , x 2 , · · · , x n ] is the feature matrix, Z is the coding matrix, and E is the error matrix. Consequently, we first formulate the superpixel segmentation problem as: where λ is a trade-off parameter, and 0 n ∈ R n×1 is an all zeros vector. The constraint diag(Z) = 0 n is used to eliminate the trivial solution, i.e., Z equals to an identity matrix. The term Z 0 is a regularization to enforce the sparsity, representing the global subspace structure in X. 0norm means to find the sparsest solution. However, minimizing (1) is extremely difficult since it corresponds to an NP-hard problem. To find a nontrivial sparse representation efficiently, the 0 -norm is usually relaxed to its convex surrogate, i.e., the 1 -norm [34].
Nevertheless, directly applying the conventional subspace clustering models to superpixel segmentation task does not work well. Fig. 2 shows the segmentation results of some stateof-the-art superpixel methods. From Fig. 2(b)-(d), we can see that the spots in the butterfly wing are almost unrecognizable. In Fig. 2(e), we adopt the subspace clustering model in (1) to generate superpixels, and the boundaries of the spots are also not achieved. The reason is that different from the general sample data in clustering, image pixels have inherent spatial correlations, which is not taken in the consideration of the conventional models. Therefore, we design a locality constraint to pursue the spatial correlation.

B. Superpixels via Locality-Constrained Subspace Clustering
Considering the spatial correlation of pixels in an image that only the similar pixels in adjacency tend to be clustered as one superpixel, we devise a spatial regularization term to 3. A simple case of adjacent matrix. If two units are neighbors, the corresponding element is labeled as "1" in the adjacent matrix; otherwise, the element is labeled as "0". enforce the adjacent correlation. Then, we propose a localityconstrained subspace clustering model to generate contentaware superpixels with more detailed boundaries.
Spatial Regularization: Considering a data set X = [x 1 , x 2 , · · · , x n ] drawn from input image units, for image superpixel segmentation, we devise a spatial regularization term f (Z) to incorporate the neighbor relationship information in X. The neighbors of the i-th column x i (e.g., x i−1 , x i+1 ) could be similar to x i . In other words, in the coding space, the corresponding neighbors of z i , which is a new representation for x i , could be close to z i . The spatial regularization term f (Z) is defined as: 2,1 -norm adopted here aims to achieve the similarity between neighboring pixels. W is the weight matrix enforcing the neighboring correlations in X, which is defined as: where ω is the spatial adjacent matrix of X, ω is the lower To show the spatial regularization term more clearly, denoted the adjacent relationship as ω, we illustrate a simple case in Fig. 3. Specifically, W is induced as follows: , which is devised to enforce the neighbors more probably to be segmented into the same superpixel. Locality-Constrained Subspace Clustering Model: Integrated with the spatial regularization in (2), we propose a locality-constrained subspace model for image superpixel segmentation: where λ 1 and λ 2 are the trade-off parameters to balance the weights of global regularization and spatial regularization, respectively.
Algorithm 1 Locality-Constrained Subspace Clustering Superpixel Input: An image I, desired number of superpixels K, initial number of pixel units n Output: K superpixels 1: Initially segment the image I into n raw pixel units by K-means. 2: Extract features of the raw pixel units as input data set X = [x 1 , x 2 , · · · , x n ] (each column is the feature vector of the corresponding pixel unit). 3: Construct matrices ω, D and W . 4: Solve the coding matrix Z according to Algorithm 2. 5: Build the affinity graph G with respect to Z according to (5). 6: Segment G with Ncut to generate K clusters. 7: Merge isolated pixels with the nearest neighbor clusters and update K.
After working out the coding matrix Z (See the detailed optimization algorithm in Section III-C), an affinity graph G can be constructed for segmenting the coding matrix Z and determining the subspace clusters. Similar to [34], the affinity graph G is defined as: This symmetrization transformation aims to assure the two connected points are in each other's sparse representation, to achieve the ideal correspondence of each element to the points from the same subspace. Then, Ncut [39] is adopted to generate the superpixel clusters with G. Moreover, in image superpixel segmentation, there may exist some isolated pixels not belonging to any clusters after the clustering step. Generally, such pixels are enforced to be assigned to the nearest cluster. The complete procedure of the proposed method is summarized in Algorithm 1. We show the result using our locality-constrained subspace clustering method in Fig. 2(f). It is clear that compared with other methods, only our method preserves the boundaries of the spots. More experimental results are presented in Section IV.

C. Optimization
To solve the objective function in (4), we adopt alternating direction method of multipliers (ADMM) [45] to devise an optimization algorithm. Two auxiliary variables U = Z and V = U W are induced to separate the terms of variable Z. Hence, (4) is equivalent to be written as: The augmented Lagrangian function of (6) is: where Θ ∈ R n×n and Ξ ∈ R n×n are the Lagrangian multiplier matrices, α 1 and α 2 are the regularization parameters. We can solve for U , V and Z alternatively by minimizing L when fixing the other two.
1) Update Z when fixing U and V: The problem in (7) becomes Since (8) is element-wise to each Z ij , by soft thresholding operator [46], we can get a closed-form solution: 2) Update U when fixing Z and V: By setting the derivative with respect to U to zero, we can obtain the following equation: (11) is a standard Sylvester equation [47], which can be linearized and solved by: where ⊗ is the tensor product and vec(·) returns a column vector by stacking the columns of a matrix.

D. Discussion
In the proposed model, three blocks of variables Z, V , and U need to be optimized in eq. (6). In each iteration, with the help of the ADMM, the objective function can converge to a local optimum with the optimized variables. Though there is no general convergence proof for the ADMM based algorithm with more than two blocks of variables [49], to the best of our knowledge, we observe that our algorithm empirically converges well and produces satisfactory performance on realworld data sets, contributing to the fact that the proposed model is convex, and each subproblem has a closed form solution.
The convergence curve is illustrated in Fig. 4. The algorithm can be updated iteratively until it the stopping conditions are satisfied, i.e., the iteration error is reduced to a stable value (10 −3 in our experiments) after several iterations or the algorithm exceeds the maximum iteration. We empirically find that 20 iterations are sufficient for most images, and thus we set the maximum iteration number to 20 for efficiency.
The computational complexity of the proposed method is dominated by the initialization by K-means and the optimization process. The computational complexity of K-means is O(N ), where N is the total number of pixels in the input image. That of the optimization process is O(k 3 ), where k is the initial number of pixel units, which is far less than the total pixel number N. Hence, the time complexity for the proposed method is O (N + k 3 ).

IV. EXPERIMENTAL RESULTS AND DISCUSSIONS
To show the merits qualitatively and quantitatively, we compare the proposed method with some state-of-the-art methods, including Ncut [39], Turbopixel [40], TPS [2], LRW [27], SLIC [28], ASS [31], FLIC [30], LSC [29] and BASS [41]. The parameters of the compared methods are set according to the original works. Since BASS cannot set the superpixel number manually, we adopt the published results directly.

A. Evaluation Criteria and Datasets
In the experiments, three commonly used metrics are utilized to evaluate all of the methods quantitatively: achievable segmentation accuracy (ASA), boundary recall (BR) and under-segmentation error (USE) [30]. ASA measures the highest achievable accuracy of a segmentation, i.e., the percentage of the most labeled pixels of superpixel segments overlapped from the ground truth segments with respect to the total number of the pixels in superpixel segments. Higher ASA indicates better segmentation of image content. USE measures the fraction of pixels of superpixel segments that not overlapped from the ground truth segments. Lower USE means fewer pixels leak from the object boundaries and edges. BR is the fraction of correctly overlapped pixels of superpixel segments from the ground truth boundaries. A high BR means the image content boundaries are well preserved after segmentation.
We compare the proposed method with some state-of-theart superpixel segmentation methods on the public Berkeley Segmentation Dataset (BSDS500) [50] for thorough superpixel segmentation evaluation. BSDS500 contains 500 natural images including humans, animals, buildings, landscape and outdoor scenes. Since the dataset has accurate annotated segmentation boundaries, almost all of the superpixel methods adopt BSDS500 for evaluation. The dataset provides 5 ground truth for each image and we average segmentation results with respect to the different ground truth for evaluation. For further comparisons, we evaluate the methods on two other datasets: Densely Annotated VIdeo Segmentation (DAVIS) [51] and Cityscapes [52]. Since these datasets do not contain accurate boundaries, the ASA metric is adopted to evaluate the upper bound segmentation performance. Besides, we add NYUv2 [53] dataset which consists of indoor-scene images for further extensive comparison.

B. Parameter Selection
The image size of BSDS500 dataset is 481 × 321. If every pixel is drawn as a sample, the dimension of the input is 154401. To speed up the computation, we use K-means to produce raw pixel units to keep the dimension of input data at thousand level. Let r denote the ratio of the initial number of pixel units n and the desired number of superpixels K. Fig.  5 shows the influence of r with respect to different metrics. We can see that the segmentation quality keeps a relatively high level when r is around 3. Indeed, blindly increasing the number of raw input units cannot improve the performance obviously, but increase the computation amount. Eventually we set the parameter r to 3 in our experiments to trade off the computation speed and segmentation performance. We have tried different λ 1 and λ 2 , and find that excessively increasing the weight of λ 1 and λ 2 may reduce the performance. Finally, λ 1 and λ 2 in (4) are empirically set to 10 −6 and 10 −4 , respectively (see more details in Section IV-E). The features are extracted from each pixel units, including color feature (average gray and R, G, B values of pixels unit), spatial feature (average coordinate of pixels unit), edge feature (average x and y components of gradient, gradient magnitude, and gradient direction) and texture feature (extracted by [54]). These features are concatenated and vectorized to X.

C. Visual Comparison
We compare our method with some state-of-the-art superpixel segmentation methods. Fig. 6 illustrates some visual comparative results when the desired number of superpixels K is set to 300. As can be seen, the proposed method maintains more detailed and complete object boundaries. For example, in the first image, our method has kept more detailed boundary information: most of the small spots in the butterfly wing are captured by our method, but almost unrecognizable by the compared methods. For the second image, our method also catches the most complete and accurate boundaries, and moreover, the homogeneous regions of the zebra stripes have better coherence and clearer segmentation compared with others. In the third image, the boundaries of doggies are preserved more accurately than other methods. Ncut, LRW and TPS cannot catch most of the boundaries in the doggies' forehead and nose, while SLIC, FLIC and LSC can capture most boundaries but missing a little bit. Only the segments of our method can cover all the boundaries of foreheads, and the most boundaries of noses. The reason is that in our method, each superpixel is regarded as a subspace containing pixels with similar intrinsic attributes, such as similar texture, boundary, color and coherent spatial information. By this way, the pixels in the unit containing independent semantic information are more probably segmented into one superpixel, no matter how small the unit area is.
It is clear that other methods can also capture more image boundaries like ours if the desired superpixel number K increases heavily. In Fig. 7, we investigate the minimum desired superpixel number K for accurate spot segmentation in the butterfly image. The proposed method can segment the spot when K = 300, while that of LRW, SLIC, and LSC are 1600, 1800, and 1600, respectively. This shows that our method can achieve more details and semantic information with less superpixels compared with other methods.
Subsequently, the proposed method is compared with three recent deep learning based methods, and Fig. 8 illustrates some visual results. It can be seen that our method can preserve more detailed boundaries than the deep-learning based methods. In the first image, only SEAL and our method segment the logo of the airplane. In the second image, both the two athletes' number "1257" and "282" are mostly recognizable in the proposed method, while in FCN, SSN, and SEAL, the number "1257" are unrecognizable. So our method is comparable with deep learning based methods, and even has superiority in detail preservation. It is also worth pointing out that our method is unsupervised, which does not need any ground truth information, while the compared deep-learning based methods all need some labeled samples that are costly to acquire.  Fig. 9 shows the quantitative comparisons with some stateof-the-art methods. Fig. 9 (a) and Fig. 9 (b) are the BR and USE metric results, which show that our method can largely improve the performance and outperforms all the other compared methods. Taking 300 superpixels for example, our method's minimum percentage gain (computed with the highest score of the compared methods) of USE is 62.5%, while that of BR is 6.7%. Fig. 9 (c), Fig. 9 (d), and Fig.  9 (e) are the ASA scores on BSDS500, DAVIS, Cityscapes datasets, respectively. In terms of ASA, the proposed method is competitive and improves the performance especially when the number of superpixels is small. Fig. 9 (g), and Fig. 9 (h) are the BR and USE score on NYUv2 dataset. The performance of our method also achieves the best performance in this dataset. The minimum and maximum percentage gains of BR are 3.60% and 41.15%, respectively. The minimum and maximum percentage gains of USE are 3.43% and 40.22%, respectively. The proposed method can largely improve the segmentation quality. Fig. 9 (i) shows the BR scores of our method and deep learning based methods FCN, SEAL and SSN on the 200 images of test in BSDS500. Compared with the deep learning based methods, the BR score of our method is higher than SEAL and FCN, and comparable with SSN. Moreover, our method performs better than SSN when the number of superpixels is less than 300.

D. Quantitative Comparison
Our method is implemented in Matlab and runs on a PC with a 3.6 GHZ Intel Core i7-6850K CPU and 16GB RAM. Fig.  9 (f) shows the trade-off between efficiency and performance compared with some state-of-the-art methods when desired superpixel number is 100 and 600. According to the BR    Fig. 10. Ablation studies on BSDS500. When λ 1 = 10 −6 , λ 2 = 10 −4 , BR, USE, and ASA can achieve the highest score.
scores, the proposed method can achieve the best segmentation performance, slightly slower than SLIC and LSC, but faster than others.
In conclusion, the quantitative results show that the pro-posed method performs better than the compared state-of-theart methods by standard evaluation criteria.

E. Ablation Study
To verify the effectiveness of the global regularization (GR) and spatial regularization (SR) in the proposed model, we evaluate our method on BSDS500 by varying the trade-off parameters λ 1 (the weight of global term in (4)) and λ 2 (the weight of spatial term in (4)). Table I lists the results of our model without the GR or SR respectively with different K. E is the error term in (4). It can be seen both the SR and GR are important to the proposed model, since E + GR + SR always performs the best. Moreover, E + SR performs better than E + GR, indicating the importance of the spatial prior term.
Moreover, Fig. 10 illustrates the BR, USE, and ASA scores with different λ 1 and λ 2 . From Fig. 10, we can see that excessively increasing the weight of λ 2 reduces the performance of BR. When λ 1 = 10 −6 and λ 2 = 10 −4 , all the metrics achieve the highest score. Therefore, we choose these two values for the parameters. For DAVIS and Cityscapes datasets, we adopted the same parameter values and achieved excellent results.

V. CONCLUSION
In this paper, we formulated image superpixel segmentation as a subspace clustering problem based on the assumption that an input image is constituted of several subspaces, and pixels with similar intrinsic attributes lie in the same subspace. We designed a novel local regularization term to enforce the spatial correlation, and the proposed spatially constrained subspace clustering model is able to generate content-aware superpixels with more detailed boundaries. The proposed method has been compared with some state-of-the-art methods, and the experiments on different standard datasets demonstrate that the proposed method achieves superior performance both quantitatively and qualitatively.