Social Image Parsing by Cross-Modal Data Refinement

1 Introduction

As a fundamental problem in computer vision, image parsing aims to segment all the objects within an image and then identify their categories. In the past years, image parsing has drawn much attention [Shotton et al., 2006; Yang et al., 2007; Shotton et al., 2008; Kohli et al., 2009; Ladicky et al., 2009; 2010; Csurka and Perronnin, 2011; Lucchi et al., 2012; Tighe and Lazebnik, 2013; Chang et al., 2014; Yang et al., 2014]. Although these methods have been reported to achieve promising results, most of them take pixel-level labels as the inputs of image parsing. In real-world applications, pixellevel labels are very expensive to access, and these fully supervised methods cannot be widely applied in practice.

Many recent efforts have been made to exploit imagelevel labels for image parsing [Verbeek and Triggs, 2007; Vezhnevets and Buhmann, 2010; Vezhnevets et al., 2011; 2012; Liu et al., 2013; Zhang et al., 2013; Liu et al., 2014; Xu et al., 2014], considering that image-level labels are much easier to access than pixel-level labels. The main challenge thus lies in inferring pixel-level labels from this weak supervisory information. As compared to the traditional fully supervised image parsing that takes pixel-level labels as supervisory information, such weakly supervised image parsing is more flexible in real-world applications. However, it is still expensive to collect image-level labels for image parsing. Hence, we hope that such supervisory information can be provided in an automatic and natural way.

Due to the burgeoning growth of social images over photosharing websites (e.g. Flcikr), this automatic and natural setting becomes feasible for image parsing. That is, the tags of social images can be used as image-level labels for image parsing. It is worth noting that the tags of social images may be noisy (or incomplete) in practice [Tang et al., 2009], although they are very easy to access. Hence, the main challenge lies in effectively exploiting the noisy tags for image parsing. However, such social image parsing has been rarely considered in recent work [Vezhnevets et al., 2012; Liu et al., 2013; Zhang et al., 2013].

In this paper, we focus on developing a cross-modal data refinement approach to solve the challenging problem of social image parsing. The basic idea is to first oversegment all the images into regions and then infer the labels of regions from the initial image-level labels. Since the initial labels of regions cannot be accurately estimated even from clean initial image-level labels, our main motivation is to continuously suppress the noise in the labels of regions through an iterative procedure. By considering the initial labels and visual features as two modalities of regions, we formulate such iterative procedure as a cross-modal data refinement problem over all the regions. In contrast to [Liu et al., 2013] which is limited to clean and complete image-level labels for image parsing, we do not impose any extra requirement on the initial image-level labels. Based on L1-optimization [Elad and Aharon, 2006; Chen et al., 2011] and label propagation [Zhu et al., 2003; Zhou et al., 2004], we develop an efficient algorithm to solve such cross-modal data refinement problem.

The flowchart of our cross-modal data refinement (CMDR) for social image parsing is illustrated in Figure 1. Here, we adopt the Blobworld method [Carson et al., 2002] for oversegmentation, since it can automatically detect the number of regions within an image. Meanwhile, we utilize image-level labels to infer the initial labels of regions, which are further smoothed by using some prior knowledge about regions and object categories. In this paper, to study whether our CMDR algorithm can deal with noisily tagged images, we first conduct experiments on the MSRC [Shotton et al., 2006] and LabelMe [Liu et al., 2011] benchmark datasets by adding random noise to the initial image-level labels. These two datasets are originally used in recent work on image parsing [Csurka and Perronnin, 2011; Lucchi et al., 2012; Liu et al., 2013; Zhang et al., 2013] without adding random noise. To obtain more convincing parsing results, we further conduct experiments by collecting a Flickr dataset with realistic noise, where the noisy image-level labels are directly downloaded from the Flickr website. As shown in later experiments, our investigation with random and realistic noise has provided an alternative and natural way to address the challenging problem of image parsing, given that the noisy image-level labels can be easily obtained from social image collections. In fact, our social image parsing is somewhat similar to verbal guided image parsing [Cheng et al., 2014] that aims to perform automatic image parsing using the verbal guidance.

To emphasize our main contributions, we summarize the following distinct advantages of the present work:

• ÷ This is the first attempt to formulate social image parsing as cross-modal data refinement, to the best of our knowledge. In fact, the problem of social image parsing has been rarely considered in the literature.
• ÷ We have successfully developed an efficient algorithm for social image parsing, unlike many previous image parsing approaches that incur too large time cost.
• ÷ The proposed algorithm can be considered to provide an alternative and natural way for image parsing, since the noisy image-level labels are easy to access.

2 Cross-Modal Data Refinement

2.1 ProblemFormulation

The problem of social image parsing is described as follows. Given a set of social images, we adopt the Blobworld method [Carson et al., 2002] to oversegment each image and then extract a feature vector (including color and texture features) from each region. All the features vectors are collected into X 2 RN⇥d with each row Xi▷ being a region, where N is the total number of regions and d is the dimension of feature vectors. Moreover, as illustrated in Figure 2, the initial labels of all the regions Y = ¶yij♦N⇥C are inferred from the image-level labels provided for image parsing as: yij = 1 if the region Xi▷ belongs to an image which is labeled with category j and yij = 0 otherwise, where C is the number of object categories. Here, the initial labels of regions cannot be accurately estimated by such simple inference, even if clean image-level labels are provided initially. The noise issue becomes more severe when noisy image-level labels are used as supervisory information. Hence, we need to pay attention to noise reduction over Y . In the following, we will formulate it as a cross-modal data refinement problem.

We first model the whole set of regions as a graph G = ¶V↪ A♦ with its vertex set V being the set of regions and affinity matrix A = ¶aij♦N⇥N , where aij denotes the affinity between region Xi▷ and region Xj▷. The affinity matrix A is usually defined by a Gaussian kernel in the literature. 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 its i-th diagonal element being equal to the sum of the i-th row of A (i.e. Pj aij).

Based on these notations, we formulate social image parsing as a cross-modal data refinement problem:

where ˆ Y 2 RN⇥C stores the ideal labels of regions, ˆX 2 RN⇥d denotes the ideal visual representation of regions (initialized as X), W 2 Rd⇥C denotes the correlation matrix between ˆ Y and ˆX, λ and γ denote the positive regularization parameters, and tr(·) denotes the trace of a matrix. Since the two modalities of regions (i.e. ˆX and ˆ Y ) can be optimized alternately (see our later explanation), solving Eq. (2) is called as cross-modal data refinement (CMDR) in this paper.

The objective function given by Eq. (2) is further discussed as follows. The first term denotes the Frobenius-norm fitting constraint, which means that ˆXW should not change too much from ˆ Y . The second term denotes the smoothness constraint, also known as Laplacian regularization [Zhu et al., 2003; Zhou et al., 2004; Fu et al., 2011], which means that ˆXW should not change too much between similar regions. The third term denotes the L1-norm fitting constraint, which can impose direct noise reduction on the original Y due to the nice property of L1-norm optimization [Elad and Aharon, 2006; Figueiredo et al., 2007; Mairal et al., 2008; Wright et al., 2009; Chen et al., 2011].

Although we have given the problem formulation for social image parsing, there remain two key problems to be addressed: 1) how to smooth the initial labels of regions stored in Y , and 2) how to efficiently solve the cross-modal data refinement problem in Eq. (2). In the next two subsections, we will address these two key problems, respectively.

2.2 Initial Label Smoothing

It should be noted that there exists much noise in the initial labels of regions stored in Y which are estimated simply from the image-level labels. In the following, we adopt two smoothing techniques to suppress the noise in Y and reestimate Y as accurately as possible for image parsing.

We first smooth the initial labels of regions stored in Y by considering the relative size of regions. Let ⇢i be the ratio of the region Xi▷ occupying the image that Xi▷ belongs to, where i = 1↪ ▷▷▷↪N. We directly define the smoothed labels of regions ˜ Y = ¶˜ yij♦N⇥C as follows:

which means that a larger region is more important for our cross-modal data refinement. More notably, such smoothing technique can suppress the negative effect of tiny regions produced by oversegmentation.

We further refine the smoothed ˜ Y by exploiting the semantic context of object categories. In the task of image parsing, some object categories may be semantically correlated, e.g., "water" and "sky" are at a high probability to occur in the same image while "water" and "book" are less possible to occur together. In fact, such semantic context can be defined using a single matrix S = ¶sjj 0♦C⇥C based on the Pearson product moment correlation. Let the image-level labels of M images be collected as Z = ¶zij♦M⇥C, where zij = 1 if image i is labeled with category j and zij = 0 otherwise. We then define S = ¶sjj 0 ♦C⇥C by:

where θj and σj are the mean and standard deviation of column j of Z, respectively. By directly using the label propagation technique [Zhou et al., 2004], we further smooth ˜ Y with the semantic context as follows:

where ↵c is a positive parameter to control the strength of smoothing, and Dc is a diagonal matrix with its j-th diagonal element being Pj 0 sjj 0 . In this paper, we directly set ↵c = 0▷04 in all the experiments.

When we have obtained the final smoothed ¯ Y using the above two smoothing techniques, we reformulate our crossmodal data refinement problem as:

In the following, we will develop an efficient algorithm to solve the above problem for image parsing.

2.3 Efficient CMDRAlgorithm

In fact, the CMDR problem in Eq. (6) can be solved in two alternate optimization steps as follows:

where LAP(W↪ ˆX) = tr(W T ˆXT L ˆXW). We set ˆX⇤ = X and ˆ Y ⇤ = ¯ Y initially. As a basic L1-norm optimization problem, the second subproblem has an explicit solution:

where soft thr(·↪ ·↪ γ) is a soft-thresholding function. Here, we directly define z = soft thr(x↪ y↪ γ) as:

where f1 = (z1 - x)2 + 2γ♣z1 - y♣ and f2 = (z2 - x)2 + 2γ♣z2 - y♣. In the following, we focus on efficiently solving the first quadratic optimization subproblem.

Let Q(W↪ ˆX) = 12 ♣♣ ˆ Y ⇤ - ˆXW♣♣2F + λ2 LAP(W↪ ˆX). We can still adopt the alternate optimization technique for the first subproblem minW↪ ˆX Q(W↪ ˆX): 1) fix ˆX = ˆX⇤ , and update W by W ⇤ = argminW Q(W↪ ˆX⇤ ); 2) fix W = W ⇤ , and update ˆX by ˆX⇤ = argmin ˆX Q(W ⇤ ↪ ˆX).

UpdatingW: When ˆX is fixed at ˆX⇤ , minW Q(W↪ ˆX⇤ ) can be solved by setting the gradients of Q(W↪ ˆX⇤ ) to zeros:

Since ( ˆX⇤ )T (I + λL) ˆX⇤ 2 Rd⇥d and d ⌧ N, the above linear equation can be solved very efficiently.

Updating ˆX: WhenW is fixed at W ⇤ , min ˆX Q(W ⇤ ↪ ˆX) can be solved by setting the gradients of Q(W ⇤ ↪ ˆX) to zeros:

Let F( ˆX) = ˆXW ⇤W ⇤T . Since I + λL is a positive definite matrix, the above linear equation has an analytical solution:

However, this analytical solution is not efficient for large image datasets, since matrix inverse has a time complexity of O(N 3 ). Fortunately, this solution can also be efficiently found using the label propagation technique proposed in [Zhou et al., 2004] based on k-NN graph. Finally, the solution of min ˆX Q(W ⇤ ↪ ˆX) is found by solving:

Since W ⇤W ⇤T 2 Rd⇥d and d ⌧ N, the above linear equation can be solved very efficiently.

The complete CMDR algorithm is outlined as follows:

1. Construct a k-NN graph with its affinity matrix A being defined over all the regions X;
2. Compute the normalized Laplacian matrix L = I - D- 12AD- 12 according to Eq. (1);
3. Initialize ˆX⇤ =X and ˆ Y ⇤ = ¯ Y ;
4. Find the best solution W ⇤ by solving (( ˆX⇤ )T (I + ↵ 1-↵ L) ˆX⇤ )W = ( ˆX⇤ )T ˆ Y ⇤ , which is exactly Eq. (8) with ↵ = λ◁(1 + λ) 2 (0↪ 1);
5. Iterate Ft+1( ˆX) = ↵(I - L)Ft( ˆX) + (1 - ↵)ˆ Y ⇤W ⇤T until convergence, where a solution can thus be found just the same as Eq. (10) with ↵ = λ◁(1 + λ);
6. Find the best solution ˆX⇤ by solving Eq. (11): ˆX(W ⇤W ⇤T ) = F ⇤ ( ˆX), where F ⇤ ( ˆX) denotes the limit of the sequence ¶Ft( ˆX)♦;
7. Iterate Steps (4)-(6) until the stopping condition is satisfied, and update ˆ Y ⇤ = soft thr( ˆX⇤W ⇤ ↪ ¯ Y ↪ γ);
8. Iterate Steps (4)-(7) until the stopping condition is satisfied, and output the final parsing results ˆ Y ⇤ .

Similar to the convergence analysis in [Zhou et al., 2004], the iteration in Step (5) converges to F ⇤ ( ˆX) = (1 - ↵)(I - ↵(I -L))-1 ˆ Y ⇤W ⇤T , which is equal to the solution given by Eq. (10) with ↵ = λ◁(1 + λ). Moreover, in our experiments, we find that the iterations in Steps (5) , (7), and (8) generally converge in a limited number of steps (<10). Finally, since the time complexity of Steps (4)-(7) is respectively O(d2C + dCN + d2N + kdN), O(dCN + kdN), O(d2C + d2N), and O(dCN) (k↪ d↪ C ⌧ N), the proposed algorithm can be applied to a large set of regions.

3 Social Image Parsing

In the previous section, we assume that the large set of regions have been provided in advance. In the following, we discuss how to generate this input for our CMDR algorithm.

Given a set of images, we adopt the Blobworld method [Carson et al., 2002] for oversegmentation. Concretely, we first 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. The pixels within this image are then grouped into regions, and the number of regions is automatically detected by a model selection principle. To ensure an oversegmentation of each image, we slightly modify the original Blobworld method in two ways: 1) the number of regions is initially set to a large value; 2) model selection is forced to be less important during segmentation.

After we have oversegmented all the images into regions, we collect them into a single matrix X 2 RN⇥d . Here, each region Xi▷ is denoted as a 137-dimensional feature vector by concatenating color and texture features: three mean color features with their standard deviations (6-dimensional), three mean texture features with their standard deviations (6dimensional), and color histogram (125-dimensional). Finally, we compute a Gaussian kernel over X for our crossmodal data refinement algorithm.

The full algorithm for social image parsing is as follows:

1. Oversegment each image into multiple regions using the modified Blobworld method;
2. Extract a 137-dimensional feature vector from each region by concatenating color and texture features;
3. Perform image parsing by running our CMDR algorithm over the large set of regions.

4 Experimental Results

In this section, our CMDR algorithm for image parsing is evaluated by conducting two groups of experiments: test with noisily tagged images and test with social images.

4.1 Test with Noisily Tagged Images

Experimental Setup

We select two benchmark datasets for performance evaluation: MSRC [Shotton et al., 2006] and LabelMe [Liu et al., 2011]. The MSRC dataset contains 591 images, accompanied with a hand labeled object segmentation of 21 object categories. Pixels on the boundaries of objects are usually labeled as background and not taken into account in these segmentations. The LabelMe dataset (also called as the SIFT Flow dataset) contains 2,688 outdoor images, densely labeled with 33 object categories using the LabelMe online annotation tool. For these two benchmark datasets, we oversegment each image into multiple regions and then totally obtain about 7,500 regions and 33,000 regions, respectively.

To study whether our CMDR algorithm can deal with noisily tagged images, we add random noise into the image-level labels that are initially provided for image parsing. More concretely, we randomly select certain percent of images and then attach each selected image with one extra wrong label. This means that the noise strength is determined by the percent of noisily tagged images (see Table 1) in the following experiments. It should be noted that the noise level is actually high, although we only add one wrong label for each selected image. That is, since most of the images used in our experiments are segmented into three or four objects in the ground-truth segmentations, one wrong label induces 1/5 to 1/4 noise within an image. More notably, we will also make evaluation with realistic noise in the next subsection.

To verify the effectiveness of our cross-modal data refinement for image parsing, we first consider a baseline method that is a variant of our CMDR algorithm without optimizing ˆX in Eq. (6) (thus denoted as DR). Moreover, we compare our CMDR algorithm with two representative methods [Tang et al., 2009; Chen et al., 2011] for data refinement by

[Liu et al., 2013] 26 24◦5 18◦4 14◦2 13◦2

sparse coding. Finally, we make direct comparison to the recent work [Liu et al., 2013] 1 on image parsing by inputting noisily tagged images into the algorithm developed in [Liu et al., 2013]. For fair comparison, we make use of the same initial label smoothing techniques proposed in Section 2.2 for all the methods compared here. We evaluate the parsing results on a subset of images equivalent to the test set used in [Vezhnevets et al., 2011; Liu et al., 2013]. The accuracy is computed by comparing the parsing results to the ground truth segmentations for each category and then averaged over all the categories. Each trial is randomly repeated 25 times.

It should be noted that the ground-truth pixel-level labels of all the images are unknown in our setting for image parsing. Hence, it is not possible to select the parameters by cross-validation for our CMDR algorithm. In this paper, we thus uniformly set the parameters of our CMDR algorithm as k = 110, ↵ = 0▷45 (equally λ = 0▷82), and γ = 0▷12 for the two benchmark datasets. Moreover, we construct k-NN graphs over all the regions for other related methods to speed up image parsing. The parameters of these methods are also set to their respective optimal values.

Parsing Results

We compare our CMDR algorithm for image parsing with other related methods when different percents of noisily tagged images are provided initially. The comparison results on the two benchmark datasets are listed in Table 1. The immediate observation is that our CMDR algorithm achieves the best results in all cases (see example results in Figure 3). This means that our CMDR algorithm is more effective for noisily tagged image parsing than the two data refinement methods [Tang et al., 2009; Chen et al., 2011] based on sparse coding. The comparison of CMDR vs. DR shows that the "crossmodal" idea plays an important role in our algorithm for image parsing. More notably, our CMDR algorithm is shown to obviously outperform the recent work [Liu et al., 2013], mainly due to the fact that extra requirements are imposed on the initial image-level labels in [Liu et al., 2013] while our problem formulation is much more flexible.

1 Originally developed for weakly supervised setting, but applied to noisily tagged setting here for fair comparison.

We further give an overview of the parsing results obtained by our CMDR algorithm and the state-of-the-art results on the two benchmark datasets in Tables 2 and 3, respectively. Here, three settings for image parsing are considered: FS-fully supervised image parsing using pixel-level labels, WS-weakly supervised image parsing using clean image-level labels, and NT-noisily tagged image parsing using noisy image-level labels. Strictly speaking, the three settings for image parsing cannot be compared directly. Here, we mainly want to give an overview of them in Tables 2 and 3. In fact, from such overview, we find that our CMDR algorithm can provide an alternative and natural way to address the challenging problem of image parsing. That is, when the image-level labels (maybe noisy) are easy to access in practice, we are able to achieve promising results by our CMDR algorithm, without the need to directly collect pixel-level labels as supervisory information at too expensive cost. However, this conclusion does not hold for the recent work on image parsing [Liu et al., 2013], which means that our noisily tagged image parsing is indeed a very challenging problem and the algorithm design in this setting is very important.

Besides the above advantages, our CMDR algorithm has another distinct advantage, i.e., it runs efficiently on a large set of regions. For example, the running time of data refinement over ¯ Y taken by our CMDR algorithm, [Tang et al., 2009], [Chen et al., 2011], and [Liu et al., 2013] on the MSRC dataset (N ⇡ 7↪ 500) is 23, 63, 30, and 68 seconds, respectively. We run all the algorithms (Matlab code) on a computer with 3.9GHz CPU and 32GB RAM. It can be clearly observed that our CMDR algorithm runs the fastest among the four related methods for image parsing.

4.2 Test with Social Images

Experimental Setup

In this paper, we actually derive a Flickr dataset with realistic noise from the PASCAL VOC2007 benchmark dataset [Everingham et al., 2007]. The original VOC2007 dataset contains 632 images, well segmented with 20 object categories. Since images in the VOC2007 dataset are originally downloaded from the Flickr website, we choose to construct a Flickr dataset based on this benchmark dataset. Concretely, we directly copy all the images from the VOC2007 dataset and then collect the image-level labels from the Flickr website, instead of the original clean image-level labels from the VOC2007 dataset. In our experiments, we only keep 100 object categories that most frequently occur in this Flickr dataset. Moreover, the ground-truth pixel-level labels derived from the original VOC2007 dataset are used for performance evaluation. To this end, we only consider the 20 object categories that occur in the ground-truth segmentations in the evaluation step (while 100 object categories are still considered in the other steps of image parsing).

To verify the effectiveness of our CMDR algorithm for social image parsing with realistic noise, we compare it with several closely related methods [Tang et al., 2009; Chen et al., 2011; Liu et al., 2013]. Here, we just take the same strategy of parameter selection and performance evaluation as that on the MSRC and LabelMe datasets. In fact, the experimental setup of this subsection is the same as that of the previous subsection except that we consider the realistic noise in image-level labels instead of random noise.

Parsing Results

We show the comparison of our CMDR algorithm to related methods in Figure 4. Overall, we can make the same observation on this new dataset as we have done with the MSRC and LabelMe datasets in the previous subsection. That is, our CMDR algorithm is still shown to achieve the best results in social image parsing with realistic noise. This means that our CMDR algorithm is more effective for data refinement over the initial labels of regions even when the noisy image-level labels are directly collected from the Flickr website. In fact, our WSSL algorithm can be considered to provide an alternative and natural way to address the challenging problem of image parsing, since the noisy image-level labels collected from the Flickr website are much easier to access than pixellevel labels (used in fully supervised setting). In fact, this is also the place where we stand in the present work.

5 Conclusions

In this paper, we have investigated the challenging problem of social image parsing. From the viewpoint of data refinement over the labels of regions, we have formulated social image parsing as a cross-modal data refinement problem. Based on L1-optimization and label propagation techniques, we have further developed an efficient algorithm to solve such crossmodal data refinement problem. The experimental results have demonstrated the effectiveness of our cross-modal data refinement algorithm for image parsing. In the future work, we will extend our algorithm to other challenging tasks in computer vision for the need of data refinement.

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.