Bilevel Visual Words Coding for Image Classification

1 Introduction

Bag-of-Words (BoW) approach has received widely attention as the state-of-the-art for image classification [Yu et al., 2009; Wang et al., 2010; Liu et al., 2011; Ponce et al., 2011]. The key steps of BoW model are local feature extraction, codebook generation, feature coding and pooling. Different approaches have worked on each step to improve both its generative property to describe images accurately and its discriminatory power for classification. Despite remarkable progresses, there still remain challenges and disputes especially on effective codebook generation and reasonable coding.

A codebook is a set of visual words that further used as the bases for coding. Most coding methods use k-means clustering to generate the codebook for its efficiency [Sivic and Zisserman, 2003; Yu et al., 2009; Wang et al., 2010; Liu et al., 2011]. The obtained codebooks often lose the cluster size and shape information with distortion errors and low discriminative power [Lazebnik and Raginsky, 2009; van Gemert et al., 2010]. To optimize codebook, sparse coding uses the unsupervised learning to learn an over-complete codebook ensuring sparse representation of local descriptors [Olshausen and Fieldt, 1997; Mairal et al., 2008]. Some supervised learning methods are also proposed to improve the discriminative power of the codebook [Lazebnik and Raginsky, 2009; Boureau et al., 2010]. However, these approaches are too computationally expensive to be scalable to largescale problems [Shabou and LeBorgne, 2012]. Moreover, in the following coding stage, sparse coding usually tends to select quite different bases for similar descriptors to favor sparsity. As a result, the correlations between codes are overlooked that leads to low discriminative power of the final representation [Yu et al., 2009]. In contrast, it has been shown that localized coding with several nearest local bases would lead to more effective representations with better discriminative power [Wang et al., 2010; Liu et al., 2011].

In this paper, we propose a bilevel visual words coding approach in consideration of representation ability, discriminative power and efficiency. In the bilevel codebook generation stage, the first level visual words are firstly generated using k-means separately in each class to synthesize each class information. Then an efficient spectral clustering is run on the first level visual words to better capture the shapes of visual words and acquire better discriminative power. The output cluster centers with the lower dimensionality consist the second level visual words as the final codebook. To obtain discriminative representation in the coding stage, we design a certain localized coding rule with bilevel codebook to select local bases. To further achieve an efficient coding referring to this rule, an online method is proposed to efficiently learn a projection of local descriptor to the visual words in the codebook. After projection, coding can be efficiently completed by firstly projecting the local descriptor to the same dimensionality with the codebook, secondly coding with a localized soft-assignment. Experimental results on two typical datasets demonstrate that our proposed coding method with bilevel visual words outperforms the state-of-the-art approaches for image classification.

2 Backgrounds

Considerable research efforts have been devoted to coding techniques in the area of artificial intelligence [Li et al., 2009; Pan et al., 2010; Gong and Zhang, 2011]. To review the state-of-the-art coding methods, we first give some notations. Let us consider a codebook of visual words denoted as B = [b1, b2, ..., bm] ∈ Rd×m, where d is the dimensionality of a local descriptor and m is the codebook size. Let xi ∈ Rd be the i-th local descriptor in an image and zi be the coding coefficient vector of xi, with zij being the coefficient with respect to visual word bj .

The codebook B usually consists of the cluster centers generated by the efficient k-means clustering. Then the common objective of coding methods is to quantize the local descriptor to visual words by the least square fitting:

Different constraints or regularizers for this objective lead to different coding methods. The traditional Vector Quantization (VQ) [Cosman et al., 1996] used the non-negative constraints ‖zi‖ℓ1 = 1 and zi ⪰ 0 to force the coding weight to be 1, and the cardinality constraint ‖zi‖ℓ0 = 1 to make the coefficient only have one non-zero element. Then the quantization could be simply performed by a hard assignment: each local descriptor is assigned to the nearest visual word. This coding method would lead to unreasonable mapping results because of the variability, such as image noise, varying scene illumination and non-affine changes in the measurement regions. Any of these will make the mapping results drift a lot from the original one [Philbin et al., 2008].

Sparse Coding (SC) [Lee et al., 2006; Mairal et al., 2008] is one alternative method which yields better results in many applications. It utilizes the idea of soft-assignment and uses a sparsity regularization term (i.e. the ℓ1 norm of zi) to relax the constraint ‖zi‖ℓ0 = 1:

As the codebook B is usually over-complete, the sparsity regularization is necessary to ensure that the under-determined system has an unique solution. Compared with vector quantization approach, sparse coding achieves much less quantization error. However, it is very likely to select quite different visual words for similar descriptors to favor sparsity, leading to a weak correlations between codes [Wang et al., 2010].

Unlike the sparse coding, Locality-constrained Linear Coding (LLC) [Wang et al., 2010] enforces locality instead of sparsity, which leads to smaller coefficient for the basis vectors farther from a local descriptor xi:

where ⊙ denotes the element-wise multiplication, and di ∈ Rm is the locality adaptor that gives different freedom for each visual word proportional to its similarity to the input descriptor xi. Specifically, di = [exp( dist(xi ,b1) δ ), . . . , exp( dist(xi,bm) δ )]T , where dist(, ) denotes the Euclidean distance and δ is a positive parameter adjusting the weight decay speed for the locality adaptor. In practice, a approximation is proposed to improve the computational efficiency by ignoring the second term in Eq. (3). It directly selects the k nearest visual words of xi to minimize the first term by solving a much smaller linear system. This gives the coding coefficient for the selected k visual words and other coefficients are set to zero.

3 Coding with Bilevel Visual Words

In this section, we will introduce a novel coding method for image classification using bilevel visual words, that can better reflect the shapes of visual words with better discriminative power. We firstly introduce the bilevel structure to generate codebook, where k-means and an efficient spectral clustering are run in each level by taking both class information and the shapes of each visual word cluster into account. A corresponding localized coding rule is then designed with bilevel codebook to select local bases. To achieve a faster coding, an online projection learning method is further proposed to learn the localized coding rule between local descriptor and the visual words from the bilevel structure.

3.1 Codebook Generation

In most previous works, in consideration of efficiency, the initial codebook usually consists of the cluster centers obtained by k-means clustering method on randomly selected local descriptors from the training images. The obtained codebooks often lose the cluster size and shape information with distortion errors and low discriminative power [Lazebnik and Raginsky, 2009; van Gemert et al., 2010].

To deal with this weakness while preserving the efficiency, we propose to generate the codebook in two levels as illustrated in Fig. 1. Firstly k-means is run on local descriptors from each class separately. After that, we have h cluster centers from each class. The total n = h × c cluster centers consist the first level visual words B1 ∈ Rd×n = [˜b1, ˜b2, ..., ˜bm] if we have c classes image dataset. Secondly, we run an efficient spectral clustering [Ng et al., 2001] on these first level visual words to generate the second level visual words as the final codebook B2 ∈ Rde×m = [b1, b2, ..., bm], each column of which is the cluster center output by the spectral clustering with the lower dimensionality de.

As we know, spectral clustering can adapt to a wider range of geometries and detect non-convex patterns and linearly non-separable clusters [Ng et al., 2001; Filippone et al., 2008]. Also it can detect the cluster (arbitrary shapes) structure of data [Cai et al., 2010]. So it shows better performance than k-means. The spectral clustering can be thought as a two-step approach [Belkin and Niyogi, 2001]. The first step is unfolding the data manifold using the manifold learning algorithms and the second step is performing typically k-means on the flat embedding for the data points. Therefore, the obtained lower dimensional cluster centers can better reflect the cluster information. In the first step, we usually embed the data by retaining the top eigenvectors of a graph Laplacian, which is defined on the affinity matrix of data points. Since it is computational infeasible to directly build the large affinity matrix for all local descriptors from the training dataset, we instead run the spectral clustering on the first level visual words, which synthesize each class information.

Efficient Spectral Clustering

Consider a graph with n vertices where each vertex corresponds to a first level visual word. We define the affinity matrix W on the graph as the dot-product weighting, i.e., Wij = ˜b⊤i ˜bj and W = B⊤ 1 B1. The Laplacian matrix L = D - W, where D is the degree matrix whose diagonal elements are the column/row sums of W, D = ∑j Wij and other elements are all zero. It is easy to check that the eigenvectors of the normalized Laplacian D-1/2LD-1/2 corresponding to the smallest eigenvalues are the same as the eigenvectors of D-1/2WD-1/2 corresponding to the largest eigenvalues [Ng et al., 2001]. Then the embeddings can be obtained by solving the eigen-decomposition of D-1/2WD-1/2 = ˆ B1⊤ ˆ B1 ∈ Rn×n , where ˆ B1 = B1D-1/2 . As we know, it is commonly an O(n3 ) problem that is not scalable to the number of first level visual words.

As ˆ B1⊤ ˆ B1 shares the non-zero eignvalues with ˆ B1 ˆ B1⊤ ∈ Rd×d , we can solve the eign-problem of ˆ B1 ˆ B1⊤ instead, which takes only O(d3 + dedn), that is only linear to the number of first level visual words. Since the dimensionality of the used local descriptor d (128 for SIFT and 64 for SURF) is much smaller than n, the computational time could be O(dedn), much less than O(n3 ). In detail, we denote a diagonal matrix Σ ∈ Rde×de whose diagonal elements are the selected top de eigenvalues as σ1, σ2, · · · , σde where σ1 ≥ σ2 ≥ · · · ≥ σde ≥ 0. The corresponding top eignvectors of ˆ B1⊤ ˆ B1 and ˆ B1 ˆ B1⊤ are V ∈ Rde×n and U ∈ Rde×d . Considering the singular value decomposition of ˆ B1, the eigenvectors V and U have the following relationship:

Thus, we could firstly get U by O(d3 ) computations for eigndecomposition of ˆ B1 ˆ B1⊤ and get the final embeddings of the first level visual words V = [v1, v2, · · · , vn] by O(dedn) computations for above equation. After that, we run k-means on V to m clusters with de-dimensional cluster centers as the second level visual words B2 consisting our final codebook.

3.2 Coding Rule

In this section, we will discuss how to code the local descriptor on bilevel visual words. Since the dimensionality are different between the second level visual words and the local descriptor, we cannot directly use the existing localized coding methods for single level. A simple solution is to learn a linear projection P ∈ Rd×de by a regression between V and P ⊤B1, then project the local descriptor into the same subspace of second level visual words for coding:

However, directly using this projection does not consider the localized coding rule, i.e., selecting the several nearest visual words as bases. Most previous works have demonstrated that carefully choosing the visual words (local bases) using this localized rule to quantize the descriptor is the key to the success of coding [Liu et al., 2011; Wang et al., 2010]. Similarly, we can give a localized rule for the bilevel structure as in Fig. 2(a). A local descriptor xi can be firstly mapped to its nearest first level visual word ˜bi in its own class:

where y(xi), y(˜bl) denotes the class label they come from. Then xi is further mapped to those near second level visual words according to the distances between the second level visual words and vi, the embedding of ˜bi.

However, for a novel input descriptor, we cannot know its class label that ˜bi cannot be obtained. Though it could be solved by a nearest neighbor search among all first level visual words, it incurs much more distance computations as well. To both consider the computation efficiency and the localized coding rule. We propose an online method to learn the linear projection P of the local descriptor to the second level visual words based on the localized coding rule for the bilevel structure. In detail, for a certain local descriptor xi, we denote its ideal second level visual word for coding as b+i and in contrast b-i indicates the second level visual word.

b+i , b-i can be chosen according to the localized coding rule for the bilevel visual words as illustrated in Fig. 2(a):

b+i ∈ {bl|bl ∈ Nk(vi)}, b-i ∈ {bl|bl /∈ Nk(vi)}; (7) where vi is the embedding of the nearest first level visual word ˜bi of xi in its class and Nk(vi) denotes the k-nearest

second level visual word of vi.

After projection, we want the distance of P ⊤xi to b+i is smaller than that to b-i :

where η is a positive parameter which controls the safe distance. To give a more effective loss function, we define the hinge loss:

After further expanding items in ‖.‖22 , we could have the final compact form:

3.3 Projection Learning

To minimize the global loss LP , we propose an algorithm inspired by the Passive-Aggressive family of algorithms [Crammer et al., 2006]. The algorithm iteratively learns the projection matrix P for each triplet (xi, b+i , b-i ). In each iteration, we solve the following convex problem with a soft margin:

where ‖.‖F is the Frobenius norm, ξ is the slack variable and the parameter α controls the trade-off between changes of P and loss minimization. In t-th iteration, we want to minimize the loss on current triplet (xi, b+i , b-i ) while P is close to that of the last iteration.

In the following, we try to solve the optimization problem in Eq. (11). It can be easily found that P t = P t-1 satisfying Eq. (11) when ri - 2x⊤i P(b+i - b-i ) < 0. Otherwise, lP (xi, b+i , b-i ) = ri - 2x⊤i P(b+i - b-i ). Then the Lagrangian LP,ξ,β,λ is introduced:

where β ≥ 0, λ ≥ 0 are the Lagrangian multipliers. The optimal solution can be obtained by setting the gradient of LP,ξ,β,λ to zero:

where Qi = 2xi(b+i -b-i )⊤. This is the update function of P. Next we need to know the value of β. Firstly we set the derivative of the Lagrangian with respect to ξ to 0:

According to Eq. (13)(14), we can rewrite the Lagrangian in Eq. (12) as follows:

Then we set the derivative of the Lagrangian with respect to β to 0:

From Eq. (14) and λ ≥ 0, we can also have β ≤ α. As when ri - 2x⊤i P(b+i - b-i ) < 0, P t = P t-1 , we have β = 0. Considering all the conditions for β, the final update function should be:

It is shown that the accumulative loss of this type of iteratively learning is bounded and likely to be small [Crammer et al., 2006].

Once obtaining the projection matrix P, we can simply solve the coding problem in Eq. (5) as illustrated in Fig. 2(b). Firstly we project the local descriptor using the learned P. Then the several nearest visual words are selected as local bases according to the Euclidean distances between P ⊤xi and the visual words in B2. Finally the coefficient can be obtained by LLC [Wang et al., 2010] or localized softassignemnt [Liu et al., 2011]. In practice, we suggest using a localized soft-assignment coding and the coefficient would be:

4 Experiment

In this section, the experiments will verified that the bilevel structure codebook can improve the classification performance and our proposed coding method can achieve the leading classification accuracy and coding efficiency compared with the state-of-the-art approaches.

Two widely used data sets are evaluated: Caltech-101 [FeiFei et al., 2004] with 9144 images of 101 categories objects plus one background category and 15-Scenes [Lazebnik et al., 2006] with 4485 images of 15 categories scenes. For each dataset, we randomly sample some images to form the training set for each class and repeat the classification process for 10 times and then the average classification accuracy over all classes under different training set is used for evaluation. The Histogram of Oriented Gradient (HOG) [Dalal and Triggs, 2005] is used as the local descriptor and is extracted using the same method in [Wang et al., 2010]: the features are extracted from patches densely located by every 8 pixels on the image, under three scales, 16 × 16, 25 × 25 and 31 × 31 respectively. The dimension of each HOG descriptor is 128. We also employ the spatial pyramid mathching (SPM) algorithm [Lazebnik et al., 2006] in the pooling stage. The SPM method captures the spatial information: for each spatial subregion, the codes of the descriptors are pooled together to get the corresponding pooled feature. These pooled features from each sub-region are concatenated and normalized as the final image feature representation. In this experiment, we used the max pooling and the ℓ2 normalization as in [Yang et al., 2009]. Same as [Wang et al., 2010], 4 × 4, 2 × 2 and 1 × 1 sub-regions are used for SPM. The codebook size is set to 2048 for both datasets. For classification task, we use a linear SVM and implement it with the LibSVM toolbox.

We mainly compare the following three coding methods: Localized Soft-Assignment Coding (LSAC) with the codebook obtained by the single level k-means clustering (1kmLSAC) [Liu et al., 2011], LSAC with the codebook obtained by the bilevel k-means clustering (2km-LSAC) and our proposed Bilevel Visual Words Coding (BVWC) approach. For all these three coding methods, we fix the neighborhood size as 5 and θ as 10 suggested in [Liu et al., 2011]. For bilevel structure, we empirically set the number of cluster for each class h = 500. For our method, the dimensionality of the second level visual words is set to de = 32. Moreover, the classification results using several other state-of-the-art coding methods are also compared in our experiments.

4.1 Results

Table 1 and Table 2 give the classification results with different sizes of training images on two tested datasets. The table is divided into two sections. The bottom section lists the approaches implemented by ourselves. Firstly, we find that coding with bilevel visual words show better performance than that with the single level visual words. It is because class information is firstly synthesized by the first level clustering that leads to less noises in the second level clustering to generate the final codebook. Secondly, the leading performance of our proposed method has demonstrated that our used spectral clustering method outperforms k-means in the second level clustering as the data manifold is learned through the embedding. It also shows our learned projection referring to the localized coding rule for bilevel visual words can map the local descriptor to the desired visual words. The top section of the table lists different versions of the existing coding schemes reported in the literature. Our proposed coding method also outperforms these state-of-the-art approaches.

5 Conclusion

In this paper, we proposed a novel coding method using bilevel visual words. In the codebook generation stage, we generated the first level visual words using k-means separately in each class to synthesize each class information. An efficient spectral clustering was then run on the first level visual words to generate the second level visual words with lower dimensionality, which can better capture the shapes of visual words. We further designed a corresponding localized coding rule with bilevel codebook to select local bases. Based on this rule, an online method was proposed to efficiently learn a projection of local descriptor to the visual words in the codebook. As a result, coding can be efficiently completed by firstly projecting the local descriptor to the same dimensionality with the codebook, secondly coding with a localized soft-assignment. We have shown the effectiveness and the efficiency of our proposed bilevel visual words coding approach for the image classification in the experiments.

Acknowledgments

This work was supported by the National Basic Research Program of China(973 Program) under Grant 2011CB302206 and National Nature Science Foundation of China (Grant Nos: 61222207, 91120302, 61103105).