Sparse Reconstruction for Weakly Supervised Semantic Segmentation

1 Introduction

Semantic segmentation is an interesting and challenging problem in computer vision, which aims to identify the semantic label of pixels of images, i.e., assign each pixel in an image to one of pre-defined semantic categories. Semantic segmentation is usually considered as a supervised learning problem in contrast to low-level unsupervised segmentation which groups pixels into homogeneous regions based on visual features [Lu et al., 2011; Munoz et al., 2012].

In the past years there have been many attentions in the semantic segmentation task [Kohli et al., 2009; Ladicky et al., 2009; Shotton et al., 2006; 2008; Yang et al., 2007; Jain et al., 2012; Lucchi et al., 2012; Ladicky et al., 2010]. Although these methods have shown promising results, most of them rely on a training set of annotated images, where the label for each pixel is known. However, in real-world applications, reliable pixel-level labeled images is rare, and manually labeling pixels is time-consuming and labor-intensive, so fully supervised methods cannot be widely applied in practice.

Recently, a few works have been proposed to address the weakly supervised semantic segmentation problem, where only the image-level annotations are available for training [Verbeek and Triggs, 2007; Vezhnevets and Buhmann, 2010; Vezhnevets et al., 2011; 2012]. In general, the task of semantic segmentation includes several steps as follows: (1) Oversegment images into superpixles and extract visual features for each superpixel; (2) Train classifiers with the features of superpixles in training set; (3) Apply classifiers on testing images to get the results of semantic segmentation. Since there is no groundtruth label of superpixels in the training set, most existing weakly supervised methods for methods aim to maximize the likelihood between pixel label prediction and image-level label, or to maximize various kinds of potentials.

In this paper, we come up with a novel approach to weakly supervised semantic segmentation based on sparse subspace reconstruction and classification model evaluation. The overview of the proposed approach is shown in Fig.1. Firstly, Images are segmented into superpixels. For each category, we classify the positive and negative superpixels by a classification model with respect to this category, then take the positive superpixels as input, and learn the bases of the subspace for the corresponding category. Secondly, evaluation is conducted by comparing the difference between the reconstruction error of negative and positive superpixels. Thirdly, with a few random samplings of model parameters, we can efficiently identify the optimal parameter for classification model based on GMM (Gaussian Mixture Models), and then we can easily classify the superpixels of testing images and group adjacent the superpixels sharing the same label into one homogeneous region. The main contributions of this paper include:

• We develop a new way of evaluating classification models for semantic segmentation given weekly supervised labels. Based on the chosen classification model parameters, we get an approximate groundtruth for unavailable superpixel label and learn the positive basis superpixels which perform sparse reconstruction of categoryspecific subspace. By measuring the reconstruction errors among negative and positive superpixels, we provide a powerful criterion for evaluating the effectiveness

of classification models. Experimental results on two challenging datasets show that our method outperforms previous weakly supervised methods, and it even competes with some fully supervised methods.

• Based on Gaussian Mixture Models, we also develop an Iterative Merging Update (IMU) algorithm to obtain the best parameters for the classification models. This algorithm aims to identify the model with best evaluation but minimal number of samplings, which is also known as exploration vs. exploitation trade-off.

The remainder of this paper is organized as follows: We review the related work in Section 2. We then elaborate the proposed method for sparse reconstruction weight learning, basis superpixels learning, and optimal model parameters estimating by Iterative Merging Update (IMU) algorithm in Section 3. Our experimental results on two real datasets are given in Section 4. Finally, we conclude this paper in Section 5.

2 RelatedWork

In [Shotton et al., 2006], semantic segmentation was performed by defining a conditional random field (CRF) over image pixels with unary potentials which could be learnt by a boosted decision tree classifier over texture-layout filters. The successive research along this direction focused on improving the CRF structure, such as enabling inference for combining multiple segmentations [Jain et al., 2012; Gonfaus et al., 2010; Kohli et al., 2009; Munoz et al., 2010], integrating label co-occurrence statistics [Ladicky et al., 2010], and introducing hierarchy with higher order potentials [Ladicky et al., 2009]. [Vezhnevets et al., 2012] introduced pairwise potentials among multi-feature images as components of CRF appearance model. Another direction was to develop faster and more accurate features. [Shotton et al., 2008] obtained fast and powerful features via random decision forests that convert features to similar semantic texton histograms by combining node counts and category prior of each tree.

In weakly supervised semantic segmentation settings , no groundtruth is available for evaluating pixel-level classification. Most existing works make use of the global consistency between image label and superpixel label, together with local consistency between various kinds of potentials. Predictions of pixel-category are conducted by maximizing either or both consistencies. Towards less supervision, [Duygulu et al., 2002] posed the problem as machine translation while [Verbeek and Triggs, 2007] solved this problem with aspect models and the spatial extensions. In [Vezhnevets and Buhmann, 2010], a multi-instance multi-task learning modification of semantic texton forest (STF) [Shotton et al., 2008] was proposed. In [Vezhnevets et al., 2011], multi-image model(MIM) was propsed to integrate observed training image features and labels together with latent superpixel labels into one network. [Vezhnevets et al., 2012] defined a parametric family of structured models, and designed a Maximum Expected Agreement model selection principle to evaluate the model parameters.

Our method performs weakly supervised semantic segmentation by subspace reconstruction and model evaluation. As for subspace reconstruction, various algorithms have been implemented with different regularizers [Elhamifar and Vidal, 2009; Liu et al., 2010; Wang et al., 2011]. As for model evaluation, the criterion for evaluating model parameters introduced in [Vezhnevets et al., 2012] can be easily affected by outliers. In contrast, our method goes from a different direction. No constraint is given on classification models employed. Based on the chosen classification model parameters, we get an approximate groundtruth for unavailable superpixel label and learn the positive basis superpixels which perform sparse reconstruction of category-specific subspace. Our method gives more promising results than the previous methods which use probabilistic inference merely with global and local consistency.

3 The Proposed Approach

Suppose that there are weakly labeled images and each image is oversegmented into several superpixels. For each image, the image-level label is provided while superpixel-level label is not available. For a specific category, if one image is labeled positive then there is at least one superpixel with the concerned label; otherwise, all superpixels included in the image are negative. Our goal is to determine the semantic label for each superpixel, and then adjacent superpixels sharing the same label are fused as the whole one. Let C = {c1, . . . , cM} be the semantic lexicon of M categories. We try to get a classification model for each category, and then can easily determine whether one superpixel belongs to this category or not. Suppose that classification models for the labels cm,m ∈ (1, . . . ,M) are parameterized by θm,m ∈ (1, . . . ,M), respectively. The task is to estimate the optimal parameters such that the classification models fit the weakly labeled images and perform well in prediction labels of superpixels. Since the labels of superpixels are unknown, the parameters of the classification models can not be learned in a straight way. Instead, we can firstly estimate the parameters at random, and then evaluate the random guess by investigating whether the corresponding classifier performs well on the given data.

For a certain category cm, all superpixels included in negative images are negative while the superpixels included in positive images can be either positive or negative. Once its classifier parameters θm are provided, the set of superpixels included in positive images can be divided into two subsets: positive or negative. Let X = [x1, ..., xN] denote the set of all positive superpixels where each column is the visual feature of one superpixel. It should be pointed out that the above classification results might be incorrect because the parameters θm are provided at random.

3.1 Sparse ReconstructionWeight Learning

We extract low-level visual features for each superpixel, and the feature vector is often high-dimensional. However, highdimensional data usually lie in a low-dimensional subspace with respect to some category the data belongs to, and one data point can be approximately reconstructed by some other points from the same subspace. For a certain category cm, since X = [x1, ..., xN] is the set of all positive superpixels, each superpixel can be reconstructed by the others in X, and intuitively, those more similar samples will contribute more in reconstructing it. The number of reconstructing points is much less than the number of all positive candidates in X, so the reconstruction is sparse. Denote W ∈ RN×N as the reconstruction matrix, which can be obtained by minimizing the cost function as follows:

where 1 denotes an all-one vector, and α is the trade-off parameter. In the first term, ‖X - XW‖F is the reconstruction error expressed in the Frobenius matrix norm. Denote the j-th column of X as col(X, j) which corresponds to the j-th superpixel. The j-th column of the product XW equals to the matrix X times the j-th column of W: col(XW, j) = Xcol(W, j) = ∑Ni=1 Wijcol(X, i); therefore, (‖XW-X‖F )2 = ∑Nj=1 ‖ ∑Ni=1 Wij col(X, i) - col(X, j)‖2 . By constraining that Wj,j = 0(j = 1, . . . ,N), each superpixel can be estimated as a linear combination of other superpixels except itself, which also avoids the case that the optimal W collapses to the identity matrix. As for the second term, due to Wij ∈ [0, 1], minimizing the ℓ1-norm ‖W‖1 encourages Wi,j to be zero if the reconstructing weight is too small such that W is sparse.

The cost function in Eq.(1) is convex and can be solved with the Augmented Lagrange Multiplier (ALM) method[Lin et al., 2009]. However, W is an N ×N matrix, and the computational cost is expensive for ALM to optimize the problem. As mentioned before, W is encouraged to be sparse, so we come up with a novel approach to solution by converting the original optimization of Eq.(1) with the complexity of O(N 2 ) into N sub-problems each of which operates on a single column of W with the complexity of O(N). Since these sub-problems are independent of each other, parallel computation can be employed to accelerate the optimization process. We firstly re-write Eq.(1) as follow:

where xi(d) denotes the d-th element of xi. According to Cauchy-Schwarz Inequality (∑ni=1 aibi)2 ≤ (∑ni=1 a2i )(∑ni=1 b2i ), we get:

where Tijd ∈ (0, 1),Qij ∈ (0, 1) and ∑Ni=1 Tijd = 1, ∑Ni,j=1 Qij = 1. Thus, we obtain the upper bound of our cost function as follows:

The equalities in Eq.(3) and Eq.(4) hold if and only if

Therefore, under the condition of Eq.(5), the original optimization problem is equivalent to minimizing the right side of Eq.(4), which can be furthermore divided into N independent QP (Quadratic Programming) sub-problems:

where W.j denotes the j-th column of W whose element is non-negative. Λj ∈ RN×N is a diagonal matrix with the i-th element on the diagonal equal to 2(∑Dd=1 (xi(d))2 Tijd + α Qij ). Bj ∈ RN×1 is a vector with the i-th element equal to -2x⊤i xj. Such quadratic programming problem can be easily solved via the existing software solvers such as CVXOPT 1 , MOSEK 2 , and TOMLAB 3 . By iteratively solving the optimization problem in a flip-flop manner, i.e., updating Tijd,Qij with Eq.(5) and updating Wij with Eq.(6) alternatively until convergence, we obtain the optimal reconstruction weight matrix W .

3.2 Learning Basis Superpixels

Once the sparse reconstruction weight matrix W has been learned, we select the basis superpixels spanning the subspace corresponding to the current category cm. Actually, the weight matrix W can be viewed from two perspectives: i)column view: Each column of W corresponds to one reconstructed superpixel; ii)row view: Each row of W illustrates the contributions of one superpixel to reconstructing others in the category cm. Based on the column view, we learn the reconstruction weight matrix in above subsection. Now, we focus on the row view to choose the basis superpixels.

Note that the weight matrix W is sparse, and from the row view of W, the larger weights imply that the corresponding superpixel play an important role in reconstructing others and in spanning the subspace. Therefore, we calculate the sum of each row Sum(i) = ∑Nj=1 Wij and select the superpixels with the largest Sum(i)'s as the bases. The pseudo-code for learning basis superpixels is shown in Algorithm 1.

Algorithm 1: Learning Basis Superpixels

Input: X = [x1, ..., xN ]; r: the Number of Basis Superpixels; Output: [˜x1, ..., ˜xr]: Basis Superpixels Spanning the Subspace; begin Initialization: W ← W0; while not convergence do 1.Update T, Q with Eq.(5); 2.Solve QP Problem in Eq.(6); Sum(i) = ∑Nj=1 Wij, (i=1,...,N); Select r Superpixels with Large Sum(i)'s as Bases;

For a certain category cm, its classification model is parameterized by θm, and the learned basis superpixels are ˜X = [˜x1, ..., ˜xr]. If the classification model parameters are appropriately estimated and the learned basis superpixels are satisfying, the distance between negative superpixels and the subspace spanned by ˜X = [˜x1, ..., ˜xr] should be large. Let Xneg denote all superpixels included in negative images, and each column of Xneg corresponds to one superpixel which is definitely negative. We define the distance between negative superpixels and the subspace spanned by ˜X as the minimal negative-by-positive reconstruction error minWneg ‖Xneg - ˜XWneg‖F , where Wneg is the reconstruction weight matrix of negative superpixel by the learned bases. Since the learned bases ˜X depend on θm, the above reconstruction error depends on θm as well, and the more appropriate the parameter θm is, the larger the negative-bypositive reconstruction error becomes. Therefore, it can be looked on as one criterion to evaluate the estimation of θm, denoted as Score(θm) = minWneg ‖Xneg - ˜XWneg‖F .

1 CVXOPT: http://abel.ee.ucla.edu/cvxopt/index.html

2 MOSEK: http://www.mosek.com

3 TOMLAB: http://www.tomlab.com

Algorithm 2: Iterative Merging Update

Input:

3.3 Optimal Model Parameters Estimating

Now we provide a powerful criterion Score(θm) for evaluating the effectiveness of classification models. The larger Score(θm) is, the better classification model we get. How can we find the θm that maximizes Score(θm)? It is hard to compute the gradient of Score(θm) with respect to θm, thus direct solution of maximizing Score(θm) is intractable, and enumeration of the entire solution space is also timeconsuming. Here, inspired by [Sung, 2004], we use an Iterative Merging Update (IMU) algorithm based on Gaussian Mixture Model (GMM) which fits the distribution of Score(θm).

In the parameter space, we randomly sample K different θm's and calculate the corresponding Score(θm). Thus, we get K sample pairs < θkm, Score(θkm) >, (k = 1, ..,K). Let the set of θkm is denoted as Θ, and the set of Score(θkm) as Ψ. Each element in Θ and Ψ can be considered as random variable, and the joint probability density can be defined by GMM as follows:

where C is the number of GMM components and πj is the weight of the j-th component. μj is the joint mean vector and Σj is the joint co-variance matrix for the j-th GMM component. We obtain the conditional PDF (Probability Density Function) of Ψ|Θ as

where

In Iterative Merging Update (IMU) algorithm, we initialize the GMM with K components. In each iteration, we calculate KL-divergences between components and update the GMM by merging the most similar pair of components. At the centroid of new component after merging pair, the conditional probability density of Score(θm) achieves the local peak and thus we add the corresponding θm to the set of parameter candidates. The detail of IMU Algorithm is shown in Algorithm 2. IMU algorithm reduces the initial model to a finite Gaussian mixture of C components, where C ranges from K to 1.

4 Experiments

We conduct experiments on two real-world image datasets: MSRC [Shotton et al., 2006], and VOC2007 [Everingham et al., 2007].On both datasets, we use EDISON system[Comaniciu and Meer, 2002] for the low-level segmentation. Popular visual descriptors including texture (i.e., the output of filter banks), color statistics (histogram or moments) and SIFT [Lowe, 2004] are used for each superpixel. Max-margin classification models are employed in our experiments.

The MSRC image dataset contains 591 images of resolution 320×213 pixels, accompanied with a hand labeled object segmentation of 21 object categories[Shotton et al., 2006]. Pixels on the boundaries of objects are usually labeled as background and not taken into consideration in these segmentations. For fair comparison, we use the same train/test splits as in [Shotton et al., 2008]. Some example results for semantic segmentation by our method in comparison with the ground-truth are shown in Fig.2. Table 1 gives the average accuracies of semantic segmentation of our method on both training and test subset, compared with the other two wellknown weakly supervised methods. The results of the stateof-the-art were reported in [Shotton et al., 2008] and [Vezhnevets et al., 2011]. As can be seen, the performance of our method is better than that of the others. Table 2 shows the results of our method for individual labels on MSRC dataset, in comparison with other competitive algorithms (including fully supervised and weakly supervised ones). Our method outperforms state-of-the-art weakly supervised methods on average, and it is even competitive with those fully supervised methods in many cases.

PASCAL VOC 2007 dataset [Everingham et al., 2007] was used for the PASCAL Visual Object Category segmentation contest 2007. It contains 5011 training and 4952 testing images where only the bounding boxes of the objects present in the image are marked, and 20 object classes are given for the task of classification, detection, and segmentation. Rather on the 5011 annotated training images with bounding box indicating object location and rough boundary, we conduct experiments on the segmentation set with the 'train-val' split including 422 training-validation images and 210 test images, which are well segmented and thus are suitable for evaluation of the segmentation task.

The experimental results of our method compared with other related works are given in Table 3. The last column of 3 shows that the average accuracy of our method is better than that of the other weakly supervised method [Shotton et al., 2008] and is comparable to those fully supervised ones. Our method performs far better than the only segmentation entry (Brookes)[Everingham et al., 2007]. Although our method uses much fewer training images than TKK[Everingham et al., 2007] which is trained by 422 training-validation images as well as a large number of annotated images with semantic bounding boxes from 5011 training sample, our method still get a comparable result to state-of-the-art methods.

5 Conclusions

We perform semantic segmentation in a weakly supervised framework where only image-level labels are available. Sparse reconstruction is used to learn the basis superpixels spanning the subspace for a certain category. If the classification model parameters are appropriately estimated and the learned basis superpixels are satisfying, the distance between negative superpixels and the subspace should be large. We introduce one criterion to evaluate the estimation of classifier parameter. Based on Gaussian Mixture Models, we select the best parameters for the classifiers employed. The proposed method is a general framework for evaluating various classification models, and it is suitable for any parametric model.

1 The result of weakly supervised STF is not provided in the paper [Shotton et al., 2008], here we show the result obtained by running the code provided by the authors.

Acknowledgments

We would like to thank the anonymous reviewers for their helpful comments. We would also like to thank Mr. Bilei Zhu for the fruitful discussions. This work was supported in part by the Shanghai Leading Academic Discipline Project (No.B114), the STCSM's Programs (No. 12XD1400900), the National High Technology Research and Development Program of China (No.2011AA100701), and the 973 Program (No.2010CB327906).