Learning Descriptive Visual Representation by Semantic Regularized Matrix Factorization

1 Introduction

Inspired by the success of bag-of-words (BOW) in text information retrieval, we can similarly represent an image as a histogram of visual words through quantizing the local keypoints or regions within the image into visual words, which is known as visual BOW in the areas of image analysis and computer vision. As an intermediate representation, it can help to reduce the semantic gap between the low-level visual features and the high-level semantics of images to some extent. Hence, in the literature, many efforts have been made to apply the visual BOW representation to image classification (one typical task in image analysis and computer vision). In fact, the visual BOW representation has been shown to give rise to encouraging results in image classification [Lazebnik et al., 2006; Moosmann et al., 2008; Li et al., 2008; Guillaumin et al., 2010; Stottinger et al., 2012].

∗Corresponding author.

However, as reported in previous work [Mallapragada et al., 2010; Ji et al., 2009; Liu et al., 2009; Lu and Peng, 2011], the traditional visual BOW representation has one distinct drawback as follows. That is, for efficiency purposes, the visual vocabulary is commonly constructed for visual BOW generation by directly clustering the low-level visual feature vectors extracted from local keypoints or regions within images, without considering the high-level semantics of images. In other words, the traditional visual BOW representation still suffers from the problem of semantic gap and thus may lead to significant performance degradation in more challenging tasks such as classification of community-contributed images. Here, it is worth noting that the community-contributed images are shared in an unconstrained way and thus are more difficult to classify with larger intra-class variations (see examples in Figure 3). In this paper, our main motivation is to propose a new method for learning descriptive visual BOW representation to overcome the aforementioned drawback associated with the traditional visual BOW representation.

Considering that matrix factorization has been successfully applied to image representation [Cai et al., 2011; Liu et al., 2012], we develop a semantic regularized matrix factorization (SRMF) method for learning descriptive visual BOW representation by exploiting the tags (easy to access although noisy) of community-contributed images. The basic idea is to formulate the problem of learning descriptive visual BOW representation as low-rank matrix factorization (see Figure 2). We further define Laplacian regularization [Zhu et al., 2003; Zhou et al., 2004; Fergus et al., 2010] with the tags of images (unlike [Liu et al., 2012] that utilizes the class labels of images) and add this term into the objective function of matrix factorization. Due to the special definition of Laplacian regularization, our new SRMF problem can be solved efficiently based on the label propagation technique proposed in [Zhou et al., 2004]. Although a Laplacian regularized matrix factorization method has also been proposed in [Cai et al., 2011], our SRMF method has two distinct differences as follows: 1) we define Laplacian regularization in this paper mainly to guarantee a good approximation to the original visual BOW representation, while this term is defined in [Cai et al., 2011] mainly to find a good dimension reduction; 2) we do not consider the nonnegative constraints and thus a sound initialization can be derived from eigenvalue decomposition, while for [Cai et al., 2011] only a random initialization (which may severely affect the performance) can be provided without any prior knowledge of the original visual BOW representation. More importantly, our later experiments also show that our SRMF method obviously outperforms [Cai et al., 2011].

It should be noted that the tags of images used for learning descriptive visual BOW representation are very easy to access (although noisy) for community-contributed image collections (e.g. Flickr). In contrast, the class labels of images used for learning image representation based on nonnegative matrix factorization in [Liu et al., 2012] are commonly very expensive to obtain in practice. Similarly, it is also very expensive to obtain the constraints with respect to local keypoints, although this kind of high-level semantics has been successfully used for visual vocabulary optimization in [Mallapragada et al., 2010]. In addition, other than many previous approaches [Ji et al., 2009; Liu et al., 2009; Lu and Peng, 2011] to visual vocabulary optimization that have ignored the high-level semantics, our SRMF method can explicitly utilize the tags of images (i.e. semantics) for learning descriptive visual BOW representation.

In summary, we propose a novel semantic regularized matrix factorization (SRMF) method for learning descriptive visual BOW representation by exploiting the tags of images, which can effectively reduce the semantic gap associated with the traditional visual BOW representation. As illustrated in Figure 1, the proposed SRMF method consists of two key steps: matrix factorization over visual BOW representation, and semantic regularization with textual BOW representation (derived from the tags of images). Here, it is worth noting that our SRMF method is efficient even for large image datasets. More notably, when the global visual features are also utilized for image classification, we can obtain the best results so far (to our best knowledge) on the PASCAL VOC'07 [Everingham et al., 2007] and MIR FLICKR [Huiskes and Lew, 2008] benchmark datasets, as shown in our later experiments. Although only evaluated in image classification tasks, our SRMF method can be readily extended to other challenging tasks such as image annotation and retrieval.

The remainder of this paper is organized as follows. In Section 2, we develop a novel semantic regularized matrix factorization (SRMF) method for learning descriptive visual BOW representation by exploiting the tags of images. In Section 3, the learnt descriptive visual BOW representation is evaluated on two benchmark datasets by directly applying it to image classification tasks. Finally, Section 4 gives the conclusions drawn from our experimental results.

2 Semantic RegularizedMatrix Factorization

This section presents our semantic regularized matrix factorization method in detail. We first give our problem formulation for learning descriptive visual BOW representation from a low-rank matrix factorization viewpoint, and then develop an efficient SRMF algorithm based on the label propagation technique proposed in [Zhou et al., 2004].

2.1 ProblemFormulation

In this paper, to reduce the semantic gap associated with the original visual BOW representation, we focus on learning descriptive visual BOW representation by exploiting the tags of images, which are easy to access (although noisy) for community-contributed image collections (e.g. Flickr). Here, it should be noted that the tags of images are used as the high-level semantic information for learning descriptive visual BOW representation. Similar to the formation of the visual BOW representation, we generate a new textual BOW representation with the tags of images, i.e., the high-level semantic information has been encoded into the new textual BOW representation. This means that our problem is actually how to learn more descriptive visual BOW representation from the original one by exploiting the textual BOW representation. More importantly, as illustrated in Figure 2, we can transform it into a low-rank matrix factorization problem [Singh and Gordon, 2008; Lee and Seung, 1999]. Our problem formulation will be elaborated as follows.

Let Y ∈ RN×M denote the visual BOW representation and A ∈ RN×N denote the kernel (affinity) matrix computed over the textual BOW representation, where N is the number of images andM is the number of visual words. In this paper, we only adopt linear kernel to define the similarity matrix over the textual BOW representation. By directly setting the weight matrix W = A, we construct an undirected graph G = {V,W} with its vertex set V being the set of images. The normalized Laplacian matrix of G is given by

where I is an identity matrix and D is a diagonal matrix with its i-th diagonal entry being the sum of the i-th row of W.

Based on the above preliminary notations, the problem of learning descriptive visual BOW representation can be formulated from a low-rank matrix factorization viewpoint:

where U ∈ Rm×N and V ∈ Rm×M denote the low-rank factors, ˆ Y ∈ RN×M denotes the ideal visual BOW representation, λ and γ denote the positive regularization parameters, and tr(·) denotes the trace of a matrix. The immediate observation is that our problem formulation is quite different from [Cai et al., 2011] which takes the form of minU,V 1 2 ||Y - U T V ||2F + λ2 tr(ULU T ). Moreover, since the semantic information has been encoded to the normalized Laplacian matrix L, solving Eq. (2) is called as semantic regularized matrix factorization (SRMF) in this paper.

The objective function given by Eq. (2) is further discussed as follows. The first term denotes the Frobeniusnorm fitting constraint, also used in the standard matrix factorization, which means that the product of U and V 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; Fergus et al., 2010], which means that the product of U and V should not change too much between similar images. The third term denotes the L1-norm fitting constraint, which can impose direct noise reduction on Y due to the nice property of L1-norm optimization [Elad and Aharon, 2006; Mairal et al., 2008; Wright et al., 2009]. Here, besides the two low-rank factors U and V , we also introduce the ideal visual BOW representation ˆ Y into our problem formulation. Our main motivation is to impose direct noise reduction on Y by extra consideration of the L1-norm fitting constraint || ˆ Y - Y ||1. Although this L1-norm fitting constraint is only defined with respect to ˆ Y , the effect of noise reduction can be transferred to U T V by solving Eq. (2) with ˆ Y being an intermediate representation. In this paper, we focus on learning descriptive visual BOW representation (i.e. U T V ) based on SRMF, without considering other types of sparsity penalties (e.g. ||U||1).

To apply our SRMF to large image datasets, we have to concern the following key problem: how to solve Eq. (2) efficiently. Fortunately, due to the special definition of Laplacian regularization in Eq. (2), the problem of learning descriptive visual BOW representation can be solved efficiently using the label propagation technique [Zhou et al., 2004] based on k-nearest neighbors (k-NN) graph constructed with the textual BOW representation. The proposed efficient SRMF algorithm will be elaborated in the next subsection.

2.2 Efficient SRMF Algorithm

In fact, the SRMF problem (2) can be solved in two alternate optimization steps as follows:

Here, we set ˆ Y ∗ = Y initially. As a basic L1-norm optimization problem, the second subproblem has an explicit solution based on the soft-thresholding function:

where soft(y, γ) = sign(y)max{|y| - γ, 0}. In the following, we focus on developing an efficient algorithm to solve the first quadratic optimization subproblem.

Let Q(U, V ) = 12 || ˆ Y ∗ -U T V ||2F + λ2 tr(V T ULU T V ). We can still adopt the alternate optimization technique for the first subproblem minU,V Q(U, V ) as follows: 1) fix U = U ∗ , and learn V by V ∗ = argminV Q(U ∗ , V ); 2) fix V = V ∗ , and learn U by U ∗ = arg minU Q(U, V ∗ ).

Learning V : When U is fixed at U ∗ , the solution of minV Q(U ∗ , V ) can be found by solving

which can be further transformed into

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

Learning U: When V is fixed at V ∗ , the solution of minU Q(U, V ∗ ) can be found by solving

which is actually equivalent to

Let X(U) = V ∗V ∗T U. 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 minU Q(U, V ∗ ) is found by solving:

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

The complete SRMF algorithm for learning descriptive visual BOW representation is outlined as follows:

1. Construct a k-NN graph with its weight matrix W being defined over the textual BOW representation;
2. Compute the normalized Laplacian matrix L = I - D- 1 2WD- 12 according to Eq. (1);
3. Initialize the deal visual BOWrepresentation as ˆ Y ∗ = Y , where Y is the original visual BOW representation;
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. (4) 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. (6) with α = λ/(1+λ) (see more explanation below);
7. Find the best solution U ∗ by solving Eq. (7): (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 the deal visual BOW representation as: ˆ Y ∗ = soft(U ∗T V ∗ - Y, γ) + Y ;
9. Iterate Steps (5)-(8) until the stopping condition is satisfied, and output the final descriptive visual BOW representation U ∗T V ∗ .

Similar to the convergence analysis in [Zhou et al., 2004], the iteration in Step (6) converges to X∗ (U) = V ∗ (ˆ Y ∗ )T (1 - α)(I - α(I - L))-1 , which is equal to the solution given by Eq. (6) with α = λ/(1 + λ). Moreover, in our later experiments, we find that the iterations in Steps (6) , (8), and (9) generally converge in very limited number of iteration steps (<10). Finally, since L is computed over k-NN graph, finding m smallest eigenvectors of sparse L in Step (4) has a time complexity of O(m2N + kmN). Meanwhile, the time complexity of Steps (5-8) is respectively O(m2M + mMN + m2N + kmN), O(mMN + kmN), O(m2M +m2N), and O(mMN). Hence, given that m, k ≪ min(N,M), the proposed algorithm can be applied to large datasets.

To give an explicit explanation of the descriptive visual BOW representation, we show the comparison between the descriptive and original visual BOW representations in Figure 3. Here, we conduct the experiments on a subset of the

0

10

20

30

40

50

60

70

80

90

100

0

10

20

30

40

50

60

70

80

90

100

Figure 3: Comparison between the descriptive and original visual BOW representations. The similarity of two histograms is measured by histogram-intersection kernel (HIK). It can be observed that the intra-class variations due to scale changes and cluttered backgrounds can be reduced through learning descriptive visual BOW representation. That is, the semantic gap associated with the original visual BOW representation is indeed reduced to some extent by our semantic regularized matrix factorization.

PASCAL VOC'07 dataset [Everingham et al., 2007]. We can observe that the intra-class variations due to scale changes and cluttered backgrounds can be reduced by our semantic regularized matrix factorization in terms of the histogramintersection kernel (HIK) values [Barla et al., 2003]. This means that the semantic gap associated with the original visual BOW representation is indeed reduced to some extent by exploiting the tags of images. Another interesting observation is that some visual words of the descriptive visual BOW representation tend to be explicitly related to the high-level semantics of images. For example, the visual word marked by an orange box is clearly shown to be related to "bike", considering that this visual word becomes dominative (originally far from dominative) in the histogram of the fourth image after learning descriptive visual BOW representation. This observation further verifies the effectiveness of our semantic regularized matrix factorization. In the next section, we will conduct more extensive experiments in image classification to evaluate the performance of our algorithm.

3 Experimental Results

In this section, the proposed SRMF algorithm for learning descriptive visual BOW representation is evaluated in image classification on two benchmark datasets. We first describe the experimental setup, including information of the two benchmark datasets and the implementation details. Moreover, our algorithm is compared with other closely related methods on the two benchmark datasets.

k

m

α

log 2(γ/0.00003)

Figure 4: The cross-validation classification results using the descriptive visual BOW representations learnt by our SRMF algorithm on the training set of the PASCAL VOC'07 dataset.

3.1 Experimental Setup

We select two benchmark datasets for performance evaluation. The first dataset is PASCAL VOC'07 [Everingham et al., 2007] that contains around 10,000 images. Each image is annotated by users with a set of tags, and the total number of tags used in this paper is reduced to 804 by the same preprocessing step as [Guillaumin et al., 2010]. This benchmark dataset is organized into 20 classes. Moreover, the second dataset is MIR FLICKR [Huiskes and Lew, 2008] that contains 25,000 images annotated with 457 tags. This benchmark dataset is organized into 38 classes. For the PASCAL VOC'07 dataset, we use the standard training/test split, while for the MIR FLICKR dataset we split it into 12,500 training/test images just as [Guillaumin et al., 2010]. The task of image classification on these two datasets is rather challenging, given that each image may belong to multiple classes and each class may have large intra-class variations.

For each benchmark dataset, we extract the same feature set as [Guillaumin et al., 2010]. That is, we use local SIFT features [Lowe, 2004] and local hue histograms [van de Weijer and Schmid, 2006], both computed on a dense regular grid and on regions found with a Harris interest-point detector. We quantize the four types of local descriptors using k-means clustering, and represent each image using four visual word histograms. Moreover, following the idea of [Lazebnik et al., 2006], each visual BOW representation is also computed over a 3×1 horizontal decomposition of the image, and concatenated to form a new representation that encodes some of the spatial layout of the image. Finally, by concatenating all the visual BOW representations into a single representation, we generate a large visual vocabulary of about 10,000 visual words the same as [Guillaumin et al., 2010]. Here, we only adopt k-means clustering for visual BOW generation, regardless of other more advanced clustering techniques [Bagirov, 2008; Moosmann et al., 2008].

To evaluate the learnt descriptive visual BOW representation, we apply it directly to image classification using SVM with χ2 kernel. Since we actually perform multi-label classification on the two benchmark datasets, the classification results are measured by mean average precision (MAP) just the same as [Guillaumin et al., 2010]. To verify the effectiveness of learning descriptive visual BOW representation for image classification based on our semantic regularized matrix factorization, we make comparison among the following four closely related matrix factorization methods:

1. Semantic Regularized Matrix Factorization (SRMF): minU,V, ˆ Y 1 2 || ˆ Y -U T V ||2F + λ2 tr(V T ULU T V )+γ|| ˆ Y - Y ||1;
2. Regularized Matrix Factorization (RMF) [Tak´acs et al., 2008]: minU,V 1 2 ||Y - U T V ||2F + λ2 (||U||2F + ||V ||2F );
3. Graph Regularized Nonnegative Matrix Factorization (GRNMF) [Cai et al., 2011]: minU,V>0 12 ||Y - U T V ||2F + λ2 tr(ULU T );
4. SparseNonnegativeMatrix Factorization (SPNMF) [Kim and Park, 2007]: minU,V >0 1 2 ||Y -U T V ||2F + λ2 ||V ||2F + γ||U||1.

Here, both GRNMF and our SRMF exploit the tags of images for learning descriptive visual BOW representation through Laplacian regularization, while the other two methods do not consider this semantic information for matrix factorization. In the experiments, the parameters of our SRMF algorithm are selected by cross-validation on the training set. For example, according to Figure 4, we set the two parameters of our SRMF algorithm on the PASCAL VOC'07 dataset as: k = 25, m = 80, α = 0.96 and γ = 0.00012 (which appear in Steps 1, 4, 5 (or 6), 8 of our algorithm proposed in Section 2.2, respectively). In particular, the performance of our SRMF algorithm is shown to only become slightly better (or keep unchanged) when the parameter m is increased to certain level (e.g. ≥80 here). The same parameter selection strategy is adopted by the other matrix factorization methods for learning descriptive visual BOW representation.

3.2 Classification Results

We first show the comparison between different BOW representations on the two benchmark datasets in Figure 5(a). The immediate observation is that the descriptive visual BOW representation learnt by our SRMF algorithm significantly outperforms the original visual BOW representation. That is, the tags of images have been successfully added to the descriptive visual BOW representation and thus the semantic gap associated with the original visual BOW representation has been reduced effectively. More notably, our descriptive visual BOW representation is even shown to achieve more than 37% gains over the original textual BOW representation for both of the two benchmark datasets. The significant gains over both of the original visual and textual BOW representations are due to the fact that our SRMF algorithm can exploit these two types of BOW representations simultaneously for learning descriptive visual BOW representation. In other words, the original visual and textual BOW representations can complement each other well for image classification.

The comparison between different matrix factorization methods for learning descriptive visual BOW representation is further shown in Figure 5(b). Here, it should be noted that only GRNMF and our SRMF can exploit the tags of images for learning descriptive visual BOW representation through Laplacian regularization, while the other two methods do not consider this semantic information for matrix factorization. From Figure 5(b), we find that both GRNMF and our SRMF obviously outperform the other two matrix factorization methods (i.e. RMF and SPNMF). These impressive results are due to the fact that the tags of images can be exploited by Laplacian regularization to reduce the semantic gap associated with the original visual BOW representation, while such important semantic information is completely ignored by the other two matrix factorization methods. Moreover, when the two Laplacian regularized matrix factorization methods (i.e. GRNMF and SRMF) are compared to each other, our SRMF is shown to achieve obvious improvements over GRNMF, since we define a different Laplacian regularization term to guarantee a good approximation to the original visual BOW representation (other than only a good dimension reduction guaranteed by GRNMF) and also provide a sound initialization based on eigenvalue decomposition (instead of random initialization used by GRNMF).

Besides the above advantages in image classification, our SRMF method has another advantage, i.e., it can run very fast even on large image datasets. For example, the running time of learning descriptive visual BOW representation taken by SRMF, RMF, GRNMF and SPNMF on PASCAL VOC'07 is 3.0, 2.1, 6.9 and 3.5 minutes, respectively. Here, we run the algorithms (Matlab code) on a computer with 3GHz CPU and 32GB RAM. It can be clearly observed that our SRMF runs faster than GRNMF and SPNMF, while RMF runs the fastest without considering Laplacian regularization.

The comparison of our SRMF method with the state-ofthe-art on the two benchmark datasets is shown in Table 1. To the best of our knowledge, the recent work [Guillaumin et al., 2010] has reported the best results so far for image classification on the PASCAL VOC'07 and MIR FLICKR datasets. However, when the descriptive visual BOW representation (i.e. local visual features) obtained by our method is fused with the global visual features (i.e. color histogram and GIST descriptor [Oliva and Torralba, 2001]), our method is shown to achieve better results than [Guillaumin et al., 2010] on both of the two benchmark datasets. This becomes more impressive given that the present work makes use of much weaker global visual features than [Guillaumin et al., 2010] (i.e. two types vs. seven types). Moreover, from Table 1, we can also observe that both [Guillaumin et al., 2010] and our method obviously outperform the winner of PASCAL VOC'07 due to the effective use of extra tags for image classification.

4 Conclusions

In this paper, to reduce the semantic gap associated with the traditional visual BOW representation, we have developed an efficient semantic regularized matrix factorization method for learning descriptive visual BOW representation by adding Laplacian regularization defined with the tags of communitycontributed images into matrix factorization. The effectiveness of the proposed method has been verified by the extensive experimental results on the PASCAL VOC'07 and MIR FLICKR datasets. When we also consider the global visual features for image classification, we can obtain even more impressive results on these two benchmark datasets. For future work, the proposed method will be extended to more challenging tasks such as video content analysis.

Acknowledgments

This work was supported by National Natural Science Foundation of China under Grants 61073084 and 61202231, Beijing Natural Science Foundation of China under Grants 4122035 and 4132037, Ph.D. Programs Foundation of Ministry of Education of China under Grants 20120001110097 and 20120001120130, and National Hi-Tech Research and Development Program (863 Program) of China under Grant 2012AA012503.