Weakly Supervised Matrix Factorization for Noisily Tagged Image Parsing

1 Introduction

Noisily tagged image parsing is an extensive problem of image parsing. The goal of image parsing is originally to segment images into multiple regions and identify their categories (i.e., infer pixel-level labels). In recent years, image parsing has become popular and drawn much attention. Traditional approaches to image parsing require pixel-level labels as fully or partial supervisory information [Li et al., 2009; Socher and Li, 2010; Liu et al., 2011; Achanta et al., 2012]. Since collecting pixel-level labels is time-consuming, these approaches cannot be widely applied in practice. As a result, many efforts have been made to exploit image-level labels for image parsing [Vezhnevets and Buhmann, 2010; Vezhnevets et al., 2011; 2012]. The goal of image parsing is now to infer pixel-level labels from image-level labels. Since lots of photo-sharing websites (e.g., Flickr) provide us with plenty of social images, it is easy to collect images-level labels from the tags provided by social users. It should be noted that the social tags may be noisy in practice [Tang et al.,

∗Co-first authors of equal contributions

†Corresponding author

2009]. Image parsing only with noisy image-level labels is really an interesting but challenging problem. In fact, such noisily tagged setting has been rarely considered in recent works on image parsing [Vezhnevets and Buhmann, 2010; Vezhnevets et al., 2012; Zhang et al., 2013; Xu et al., 2014]. Our motivation is thus to build a robust and efficient model for such noisy weakly-supervised setting.

Inspired by the successful use of matrix factorization for image representation [Cai et al., 2011; Liu et al., 2012], we propose a novel Weakly Supervised Matrix Factorization (WSMF) approach to solve the challenging image parsing problem under the noisy weakly-supervised setting (i.e., only noisy image-level labels are provided initially). The proposed WSMF approach has two main components: 1) oversegment each image into multiple regions, and 2) annotate the regions based upon the initial noisy image-level labels. Different from recent work [Liu et al., 2013] that takes clean and complete labels of images as supervisory information, we do not impose any restriction on the initial image-level labels.

The proposed WSMF approach is illustrated in Figure 1. Here, we adopt the Blobworld method [Carson et al., 2002] for automatic over-segmentation. To deal with the noisy image-level labels, we choose to decompose the matrix that collects the initial region-level labels into low-rank matrices. Furthermore, to guarantee a better solution to matrix factorization, we define a new Laplacian regularization term [Zhu et al., 2003; Zhou et al., 2003] and add it into the objective function of matrix factorization. The resulting WSMF problem is finally solved by developing an efficient algorithm based on the label propagation technique [Zhou et al., 2003]. It should be noted that the proposed WSMF approach is quite different from [Cai et al., 2011] that also proposed a Laplacian regularized matrix factorization method. Specifically, we do not consider the nonnegative constraints and thus can derive a sound initialization from eigenvalue decomposition, while only a random initialization can be provided for [Cai et al., 2011] which may severely affect the performance. More notably, as shown in our later experiments, the proposedWSMF approach can provide a better solution to matrix factorization. In this paper, to verify the effectiveness of the proposed approach, we conduct experiments on two public benchmark datasets: MSRC [Shotton et al., 2006] and LabelMe [Liu et al., 2009]. The experimental results show the encouraging and robust performance of the proposed approach.

Our main contributions are summarized as follows:

• We propose a novel low-rank matrix factorization approach to address the challenging problem of noisily tagged image parsing. To the best of our knowledge, we are the first to formulate image parsing as matrix factorization from the viewpoint of noise reduction over the region-level labels, which is an active extension to the traditional image parsing problem.
• We define a new Laplacian regularized term in our problem formulation, which is shown to improve the performance of matrix factorization for image parsing under the noisy weakly-supervised setting.
• The encouraging results of the proposed approach show that it is much more flexible for image parsing in realworld applications, since only noisy image-level labels are used as supervisory information.

The reminder of this paper is organized as follows. Section 2 gives a brief review of related work. In Section 3, we formulate image parsing as a Weakly Supervised Matrix Factorization (WSMF) problem. In Section 4, we develop an efficient WSMF algorithm. In Section 5, we apply the proposed algorithm to noisily tagged image parsing. Section 6 provides the experimental results on two benchmark datasets. Finally, Section 7 draws our conclusions.

2 RelatedWork

Supervised Settings for Image Parsing. In recent works, fully-supervised and weakly-supervised settings are widely applied for image parsing. In [Shotton et al., 2006; Lucchi et al., 2012], a fully-supervised setting is considered for image parsing where pixel-level labels are provided at training time. However, pixel-level labels are time-consuming to obtain in practice. In [Verbeek and Triggs, 2007; Vezhnevets and Buhmann, 2010; Vezhnevets et al., 2011; 2012; Liu et al., 2013; Nguyen et al., 2013; Huang et al., 2014], image-level labels are considered for image parsing as weakly-supervised information, which are easier to obtain in many applications than pixel-level labels, and thus the annotation cost can be significantly reduced. However, extra constraints are imposed on the initial image-level labels. For example, image-level labels need to be clear and complete in [Liu et al., 2013] due to the special model used for image parsing. It is worth noting that image-level labels provided by users may be noisy in social image collections [Tang et al., 2009]. It remains a challenging task to effectively exploit the image-level labels for image parsing under this noisy weakly-supervised setting.

Matrix Factorization for Data Representation. Matrix factorization techniques have been successfully applied for learning data representation. The main point of matrix factorization is to find two or more low-rank matrices whose product is a good approximation to the original matrix [Liu et al., 2012]. The traditional methods include Vector Quantization, LU-decomposition, QR-decomposition, and Singular Value Decomposition (SVD). Recently, [Cai et al., 2011] proposed a Graph Regularized Non-negative Matrix Factorization (GNMF) approach based on the original Non-negative Matrix Factorization (NMF) algorithm. In NMF, non-negative constraints are imposed to promise two non-negative matrices results, and GNMF further encodes the geometrical information of the data space by constructing a nearest neighbor graph. This extension also promotes the application of NMF from unsupervised learning field to semisupervised learning algorithm.

3 Weakly SupervisedMatrix Factorization

In this section, we give our problem formulation for image parsing from a low-rank matrix factorization viewpoint under the noisy weakly-supervised setting.

3.1 Notations

Given a dataset of images as the inputs, we adopt the Blobworld method [Carson et al., 2002] to over-segment each image into multiple regions, and collect the set of regions into X = {x1, ..., xN} , where N is the total number of regions and xi is the feature descriptor of the i-th region. Such oversegmentation step will be described in detail in Section 5.

Now we have a set of regions X. Let Y = {yij}N×C denote the initial labels of regions, where C is the number of object categories. The initial region-level labels are inferred from the initial image-level labels as follows:

3.2 GraphModel

Since visually similar regions have higher probability to share the same label, we represent the relationships of regions using a weight matrix W defined as

where Nk(x) is the set of k-nearest regions of x. We actually define the weight matrix based on the Gaussian kernel.

Then we can model the set of regions as a graph G = {V,W}. The vertex set V is defined as X and the weight matrix is defined as W = {wij}N×N . The normalized Laplacian matrix L of G is given by

where I is an N × N identity matrix, and D is an N × N diagonal matrix with Dii = ∑Nj=1 wij .

3.3 Fitting Constraints and Regularization

In this paper, we choose to find two new matrices U and V to obtain the optimal approximation of Y as

where U ∈ Rm×N and V ∈ Rm×C denote the two lowrank matrix factors. The Frobenius-norm fitting constraint can then be defined as follows:

This means that the product of U and V should not change too much from ˆ Y , which can be considered as an intermediate representation of Y .

Considering the advantage of L1-norm optimization in noise reduction [Elad and Aharon, 2006; Mairal et al., 2008; Wright et al., 2009; Lu et al., 2015], we define a L1-norm fitting constraint term as follows:

which can impose direct noise reduction on Y .

To guarantee that the product of U and V should not change too much between similar regions, we define the following smoothness constraint term related to the well-known Laplacian regularization [Zhou et al., 2003; Zhu et al., 2003]:

where tr(·) denotes the trace of a matrix.

3.4 The Proposed Formulation

By combining the above two fitting-constraint terms and one regularization term together, we formulate noisily tagged image parsing as the following Weakly Supervised Matrix Factorization problem from the viewpoint of noise reduction over the labels of regions:

where λ and γ are the regularization parameters. Our main motivation is to impose direct noise reduction on Y by using the L1-norm fitting constraint ‖ ˆ Y -Y ‖1. With ˆ Y being an intermediate representation, we can transfer the effect of noise reduction to U T V by solving Eq. (5).

After we have formulated noisily tagged image parsing from the noise reduction viewpoint, we will further discuss how to solve the WSMF problem efficiently. Considering the special definition of Laplacian regularization in Eq. (5), the WSMF problem can be solved efficiently by using the label propagation technique [Zhou et al., 2003] based on k-nearest neighbors (k-NN) graph.

4 Efficient WSMF Algorithm

The optimization problem in Eq. (5) can be solved in two alternate steps as follows:

Here, ˆ Y ∗ is initialized with Y . As a basic L1-norm optimization problem, the second problem can be solved based on the soft-thresholding function:

where soft(y, γ) = sign(y) max{|y|-γ, 0}. To solve the first quadratic optimization subproblem, we develop an efficient algorithm as follows.

Let Q(U, V ) = 12 ‖ ˆ Y ∗ -U T V ‖2F + λ2 tr(V T ULU T V ). For the first subproblem minU,V Q(U, V ), we adopt the alternate optimization technique as follows: 1) fix U = U ∗ ,and update V by V ∗ = argminV Q(U ∗ , V ); 2) fix V = V ∗ , and update U by U ∗ = arg minU Q(U, V ∗ ).

Updating V : When we set U = U ∗ , the solution of minV Q(U ∗ , V ) can be found by solving the linear equation

which is actually equivalent to the linear equation

Since U ∗ (I + λL)U ∗T ∈ Rm×m and m ≪ min (N, C), the above linear equation can be solved efficiently.

Updating U: When we set V = V ∗ , the solution of minU Q(U, V ∗ ) can be found by solving the linear equation:

Algorithm 1 Weakly Supervised Matrix Factorization

Input:

Regions X = {x1, ..., xN};

Initial image-level labels P ∈ RM×C ;

Parameters k, m, γ, λ.

Output:

Labels of regions U ∗T V ∗ .

• 1: Construct a weight matrixW on k-NN graph;
• 2: Compute the normalized Laplacian matrix L = I - D- 1 2 WD- 1 2 according to Eq. (1);
• 3: Initialize the labels of regions Y referring to the imagelevel labels;
• 4: Initialize U = U ∗ ∈ Rm×N using the m smallest eigenvectors of the normalized Laplacian matrix L, where each row of U ∗ corresponds to an eigenvector of L;
• 5: Find the best solution V ∗ by solving (U ∗ (I + α 1-α L)U ∗T )V = U ∗ ˆ Y ∗ , which is exactly Eq. (10) with α = λ/(1 + λ) ∈ (0, 1);
• 6: Iterate Xt+1(U) = αXt(U)(I - L) + (1 - α)V ∗ ˆ Y ∗T until convergence, where a solution can thus be found just as Eq. (13) with α = λ/(1 + λ) ∈ (0, 1);
• 7: Find the best solution U ∗ by solving Eq. (14): (V ∗V ∗T )U = X∗ (U), where X∗ (U) denotes the limit of the sequence {Xt(U)};
• 8: Iterate Steps (5)-(7) until the stopping condition is satisfied, and update ˆ Y ∗ as ˆ Y ∗ = soft(U ∗T V ∗ - Y, γ) + Y ;
• 9: Iterate Steps (5)-(8) until the stopping condition is satisfied, and output the final labels of regions U ∗T V ∗ .

which can be further transformed into the linear equation

Let X(U) = V ∗V ∗T U. Since (I + λL) is a positive definite matrix, the above linear equation has an analytical solution:

However, due to an O(N 3 ) time complexity of matrix inverse, this analytical solution is not suitable for large image datasets. Fortunately, this solution can also be efficiently found using the label propagation technique proposed in [Zhou et al., 2003] based on k-NN graph. Finally, the solution of minU Q(U, V ∗ ) is found by solving:

Since V ∗V ∗T ∈ Rm×m and m ≪ min(N,C), the above linear equation can be solved very efficiently.

The complete WSMF algorithm for noisily tagged image parsing is outlined as Algorithm 1. Similar to the convergence analysis in [Zhou et al., 2003], the iteration in Step (7) converges to X∗ (U) = V ∗Y ∗T (1 -α)(I -α(I -L))-1 , which is equal to the solution given by Eq. (13) with α = λ/(1+λ). Moreover, in our later experiments, we find that iterations in Steps (6), (8), (9) generally converge in very limited number of iteration steps (≤ 10). Finally, collecting m smallest eigenvectors of sparse L in Step (4) has a time complexity of O(m2N + kmN). Given that m, k ≪ min(N, C), the time complexity of Steps (6-9) is respectively O(m2M+mMN+

m2N + kmN), O(mMN + kmN), O(m2M +m2N), and O(mMN), the proposed WSMF algorithm can be applied to a large set of regions in practice.

5 Noisily Tagged Image Parsing

In the previous section, we have just developed an efficient WSMF algorithm for noisily tagged image parsing. As for the inputs of our WSMF algorithm, we assume that we have collected a large set of regions with image-level labels in advance. In this section, we will focus on how to generate the large set of regions for our WSMF algorithm.

Given a set of images, we first adopt the Blobworld method [Carson et al., 2002] for over-segmentation. Specifically, we extract a 6-dimensional vector of color and texture features for each pixel of an image and then model this image as a Gaussian mixture model. With all pixels grouped into different regions, the number of regions can be automatically detected by a model selection principle. To ensure an oversegmentation of each image, we modify the original Blobworld method slightly: 1) the number of regions is initially set to a relatively large value; 2) model selection is forced to be less important during over-segmentation.

After over-segmenting all the images, we collect a large set of regions X = {x1, ..., xN}. Each region is represented as a 137-dimensional feature vector by concatenating color and textual features, which includes three mean color features with their standard deviations (6-dimensional), three mean texture features with their standard deviations (6dimensional), and 125-dimensional color histogram. Finally, we apply a Gaussian kernel over X to produce the weight matrix W in our WSMF algorithm.

Different from many previous image parsing methods [Shotton et al., 2006; Ladicky et al., 2009; Vezhnevets et al., 2012] that consume too much time during training the generative or discriminative model, our WSMF algorithm for image parsing runs very efficiently on a large set of regions. As for the time-consuming over-segmentation, we can readily speed it up by running in a distributed way.

6 Experimental Evaluation

In this section, we evaluate our WSMF algorithm on two benchmark datasets. Experiments are conducted to answer the following questions: 1) How do matrix factorization methods perform in the image parsing task? 2) How does our WSMF algorithm perform when more noisy image-level labels are considered? 3) How does our WSMF algorithm perform when compared to the state-of-the-arts?

6.1 Experimental Setup

To evaluate the effectiveness of our WSMF algorithm, we conduct experiments on two public datasets, i.e., MSRC [Shotton et al., 2006] and LabelMe [Liu et al., 2009].

MSRC: The MSRC dataset contains 591 images with 21 different object categories. The dataset is split into 276 training images and 256 test images.

LabelMe: The LabelMe dataset contains 2688 images with 33 different categories. The dataset is split into 2488

training images and 200 test images. It is more challenging than MSRC in image parsing tasks.

To verify the effectiveness of our WSMF algorithm for noisily tagged image parsing, we add random noise to the image-level labels as a simulation of social images. Concretely, we randomly select certain percent of images and then attach an extra wrong label to each selected image. Since most images have about 3 or 4 labels according to the groundtruth segmentations, one extra label for each selected image induce relatively strong noise into the inputs of image parsing. We over-segment each image into multiple regions and then totally obtain about 7,000 regions and 33,000 regions for the two benchmark datasets.

We evaluate the performance of noisily tagged image parsing by using average per-class accuracy, which measures the percentage of correctly classified pixels for a class then averaged over all classes. In the experiments, we make comparison to closely related algorithms under the same noisy weakly-supervised setting. Concretely, since a Laplacian regularization term is considered in our problem formulation, we compare our WSMF algorithm with Graph Regularized Non-negative Matrix Factorization (GNMF) [Cai et al., 2011], which considers a similar Laplacian regularization term with non-negative constraints and we extend it to the noisy weakly-supervised setting for fair comparison. Although Weakly-Supervised Dual Clustering (WSDC) [Liu et al., 2013] is originally designed for weakly-supervised image parsing, we can readily extend it to the noisy weaklysupervised setting for comparison with our WSMF algorithm. Moreover, we make comparison to the traditional matrixfactorization methods such as QR-decomposition (QR) and Singular Value Decomposition (SVD).

It should be noted that the ground-truth pixel-level labels of all the images are unknown in our image parsing setting. Hence, it is not possible to select the parameters by crossvalidation. In this paper, we thus uniformly set the parameters of our WSMF algorithm as k = 30, α = 0.1, γ = 0.013, and m = 30 for the two datasets. The parameters of other closely related methods are also set their respective optimal values.

6.2 Parsing Results

The comparison of our WSMF algorithm to other closely related methods is shown in Tables 1 and 2 (see some example results in Figure 2). We can see that our WSMF algorithm performs the best in all cases. That is, our WSMF algorithm is more effective for noisily tagged image parsing. In particular, the improvements achieved by our WSMF algorithm over GNMF are mainly due to the fact that our new Laplacian regularized term is quite different from that used in GNMF. Specifically, our Laplacian regularized term is used to guarantee a good approximation to the intermediate representation of region-level labels, while this term is defined in GNMF to find a good dimension reduction. More importantly, without the nonegative constraints (considered in GNMF), we can drive a sound initialization from eigenvalue decomposition, while GNMF can only take a random initialization. In addition, when we add noise into image-level labels for the MSRC dataset, the average per-class accuracy of our WSMF decreases by 4% with the ratio of noisy images increasing by 25%, while the average per-class accuracy of WSDC decreases by 7.5%. And for LabelMe, the average per-class accuracies of WSMF and WSDC decrease by 1.5% and 3.5%, respectively. Such observation shows the effectiveness of our WSMF in noisily tagged image parsing. These results can be used to answer Question 1) and 2).

Besides the above advantages in noisily tagged image parsing, our WSMF algorithm runs efficiently on a large set of regions. For example, the running time of WSMF, WSDC, GNMF, QR, and SVD on MSRC is 16, 52, 22, 10, and 8 seconds, respectively. Here, we run all the algorithms (Matlab code) on a computer with 3.4GHz CPU and 8GB RAM.

6.3 Comparison to the State-of-the-Arts

We show the comparison to more full-supervised methods and weakly-supervised methods for image parsing in Tables 3 and 4. Firstly, our WSMF algorithm achieves higher average per-class accuracies than other weakly-supervised approaches, and even outperforms some fully-supervised approaches on the two benchmark datasets. Secondly, our WSMF algorithm obtains the best results for 10 out of 21 categories on the MSRC dataset and for 9 out of 30 categories on the LabelMe dataset, especially for animals such as cow, sheep, bird, cat and dog, which are difficult to distinguish from the backgrounds by other methods. Thirdly, the number of categories that have zero accuracies is only one for our WSMF algorithm, much lower than other methods on the LabelMe dataset. These results demonstrate that our WSMF algorithm is more effective in more challenging tasks such as image parsing on the LabelMe dataset. This evaluation can be a good answer to Question 3).

7 Conclusion

We have proposed a Weakly Supervised Matrix Factorization approach to image parsing with noisy image-level labels under the weakly-supervised setting. Concretely, we first formulate the problem of noisily tagged image parsing as matrix factorization by defining a novel Laplacian regularized term. Moreover, an efficient WSMF algorithm is developed based on the label propagation technique. The experimental results have demonstrated the promising performance of our WSMF algorithm. In the future work, we plan to 1) apply other methods to obtain initial segmentation labels such as Markov random field-type optimization; and 2) evaluate directly over social image collections.

Acknowledgments

This work was supported by National Natural Science Foundation of China under Grants 61202231 and 61222307, National Key Basic Research Program (973 Program) of China under Grant 2014CB340403, Beijing Natural Science Foundation of China under Grant 4132037, the Fundamental Research Funds for the Central Universities and the Research Funds of Renmin University of China under Grant 15XNLQ01, and IBM Global Faculty Award Program.