New Graph regularized Sparse Coding Improving Automatic Image Annotation

Abstract

Typical image classification pipeline for shallow architecture can be summarized by the following three main steps: i) a projection in high dimensional space of local features, ii) sparse constraints for the encoding scheme and iii) a pooling operation to obtain a global representation invariant to common transformation. Sparse Coding (SC) framework is one particular example of this general approach. The main problem raised by it is the local feature encoding which is done independently, loosing correlation of the input space. In this work we propose to simultaneously encode sparse codes to tackle this problem with Joint Sparse Coding (JSC) inspired by Graph regularized Sparse Coding (GSC). We experiment SC, GSC and JSC on UIUCsports and scenes15 database. We will show that results obtained, for UIUCsports, with SC (87:27 1:33), JSC (84:17 1:57) and the State-of-the-Art (88:47 2:32 [23]) are tackled by a simple fusion (95:37 1:29). Several assumptions will be advanced to explain this phenomenon which can't be generalized.

Keywords

• Scenes categorization
• Sparse Coding
• Graph regularized Sparse Coding
• Dictionary Learning
• Scale Invariant Feature Transform
• Spatial Pyramid Matching
• Joint Sparse Coding

-

In the field of computer vision and signal processing, significant progress has been made since the 2000s with more general methods such as Bag of Words (BoW) [ 19 ]. We have at our disposal a significant number of databases as, for example, UIUCsportss [ 11 ], scenes from 15 databases [ 8 ], where the goal is to label images into a finite number of classes. The first way could be to evaluate the metric distance between two images. Unfortunately, due to the high dimensionality of this input space, most of these distances are concentrated into a sub-manifold whatever the image class, making the discrimination by direct distances not robust. To overcome this problem, a solution has to be designed to find a general application Y j(:; μ j) with parameter μ j which characterizes the class C j satisfying: dist(Y j(I1; μ j); Y j(I2; μ j)) ! 0 if I1 2 C j and I2 2 C j dist(Y j(I1; μ j); Y j(I2; μ j)) ! ¥ if I1 2 C j and I2 2= C j;(1) where I1 and I2 are two images. The choice of Y j represents a trade-off between its representation capacity versus the μ j optimization difficulty. In general, in order to estimate/optimize μ j, we have to start from a local representation (patches) x 2 Rd to obtain the global representation Y j(:; μ j). From Y j associated to BoW, Sparse Coding (SC) [ 21 ], up to ConvNet [ 3, 9 ] follow the three main procedures: i) high dimension local feature projection, ii) sparsity constraints into the representation model and iii) non-linearity operation and pooling to obtain a global invariant representation.

In this article, we will focus on a new formulation of encoding method, which corresponds more specifically to procedure ii), inspired by SC and more generally by Graph regularized Sparse Coding (GSC) [ 25 ]. This new formulation allows to encode simultaneously testing patches as with the GSC model which has good properties. Although we will only work on a single layer, we will show that a simple fusion will allow to improve considerably the classification accuracy and that our results will be close to CNN (convolutional neural nets) [ 6, 18 ] initialized on Image Net as shown in [ 3 ]. This article is divided into five parts. The first part focuses on SC models and its derivatives (GSC especially). The second part presents our modeling Joint Sparse Coding (JSC). The third part presents Graph regularized Sparse Coding (GSC) dictionary inspired by [ 13 ]. A fourth part presents results we obtained on UIUCsports and scenes15 databases and in the last part, we conclude on our contribution. 2

Related Works

In this part, we will focus on the encoding step using linear coding to reconstruct inputs. An approximation of any patches x 2 Rd can be given by xi = Dai, where D , [d1; : : : ; dK ] 2 Rd K is a given/trained dictionary where 8k = 1; : : : ; K; kdkT dkk22 = 1 and dkj 0. A patch is a vector extracted from an image. A dictionary is a matrix of “words” allowing the patch reconstruction. In many encoding methods, three common steps can be found: i) a projection into a higher dimension space with (K >> d) ii) sparse constraints and iii) a non-linear operation procedure. If ai is obtained with Ordinary Least Square (OLS), the solution is full dense (all elements are non zero). One way to get around this problem is the use of the `1-norm constraint which corresponds to Lasso problem [ 21 ] or Basis Pursuit [ 4 ]:

LSC(aijxi; D) = min ai2RK 2

kxi 1

Daik22 + lkaik1; (2) with l the regularization parameter associated to the SC formulation. This parameter controls the sparsity level as is shown in [ 15 ]. Thus, the more l is large, the more ai (solution of eq.2) will be sparse.

Usually in SC framework, if we take two neighbor patches xi and x j (with a strong correlation between them), their respective sparse codes, ai and a j, can lose this strong correlation, especially indexes of non-zero inputs can completely mismatch. It means they are involving different atoms for their patches’ reconstructions. An atom is an element of the vector patch. There exist some SC variations which have been introduced to tackle this behaviour. Principles of this improvement can be divided into two categories: one plays on adding of proximity constraint into the loss directly while the second adds some extra terms into the regularization term. To illustrate the first category, we can cite two approaches: Local Constrained linear Coding (LCC) [ 24 ] and the Local Sparse Coding (LSC) [ 20 ]. In the second category, we can mention GSC [ 25 ].

We will define the set of pre-computed sparse codes of Xtrain , f 1 xtrain; : : : ; xtNrtarianin g by Atrain , f 1

atrain; : : : ; atNrtarianin g where Ntrain designates the number of local features sampled from the training set. Indeed, this adds a spatial constraint in the regularization term. Its equation is:

LGSC(aijxi; Atrain; D; l; b) = ami2iRnK kxi

Daik22 + lkaik1 + bLiiaiT ai + 2baiT hi; (3)

Ntrain

where hi = å Li jatjrain, L = Li j i; j=1;:::;Ntrain is a Laplacian matrix and b a reguj6=i larization parameter. The matrix L is defined by L = S W, where W is a weight matrix with and Wi; j = expf kxi xst2jraink22 g if xtjrain 2 V (xi) (where V (xi) is the set of neighborhood of xi excluding xi itself), Wi; j = 0 else. The matrix S is diagonal and

Ntrain Si;i = å Wi; j. We propose to improve SC by simultaneously encoding all the test local j=1 patches (for example associated with a test image). This new modeling will be inspired from the GSC. 3

Joint Sparse Coding - JSC

JSC principle is to jointly encode all local features Xtest = f 1 xtest ; : : : ; xtNetsetst g simultaneously to overcome the decorrelation problem. We also enforce aik 0 in the previous optimization problem. This additional constraint improves pooling performances, thus avoiding to pool simultaneously on positive and negative sparse code values and decreasing as a consequence the final size vector by a factor by two. The equation of our modeling is very similar to GSC: LJSC(aijxi; Atest ; D; l) = ami2iRnK kxi

Daik22 + lkaik1 + bLiiaiT ai + 2baiT hi; s:t: aik

Ntest

where hi = å Li jatjest , L = Li j i; j=1;:::;Ntest is a Laplacian matrix, b a regularization j6=i parameter. Here, L = S W, where Wi; j = expf

Ntest else and Si;i = å Wi; j. Here, Atest , fat1est ; : : : ; atNetsetst g are computed and stacked inij=1 tially. In practice Ntest << Ntrain, so we need to store only a sparse K Ntest matrix. kxi xtest 2 s2j k2 g if xtjest 2 V (xi), Wi; j = 0 0; (4) Our Laplacian matrix (Ntest Ntest ) is very sparse. If we don’t need to compute the full matrix, one way is to only calculate the non-zero elements ((v + 1) Ntest ) with the previous formulation. Each column of this ((v + 1) Ntest ) matrix is denoted by Li. To realize this, we use a fast NN-search technical (FLANN) [ 14 ] which speeds up the computation considerably. Thus, the solution of eq.4 is given by a modified Feature Sign Search (FSS) algorithm [ 10 ] by adding a) a positivity constraint on sparse codes and b) integrating the two right terms (in b) of eq.4 in the gradient formulation used during the FSS algorithm. JSC is given by the algorithm 1. To illustrate the Algorithm 1 Joint Sparse Coding

Inputs: D, l, b, Xtest , s and v

for i = 1 : Ntest do [Vi, disti] = v-nn search of xtiest into Xtest Vi are indexes of xi neighbors in Xtest

Compute Li from disti and s end for Atest = lasso(Xtest ; D; l) for i = 1 : Ntest do

ai = JSC(xtiest ; Atest ; D; Li; Vi; l; b) end for Output: Atest 2 2 300 jå<i [r(xi; x j) Ñr = 300 299 i=å1 j=1 correlation problem, viewed with SC, we compare the normalized correlation computed between two inputs vectors with the normalized correlation computed with their respective output vectors. In this example, 300 different pairs, extracted from UIUCsports local features, are chosen to realize this. The normalized correlation formulation between x and y is given by r(x; y) = kxkx2Tkyyk2 2 [0; 1]: We also introduce the scalar value r(ai; a j)]2 which measures the average quadratic difference between normalized correlation of the input space and the output space. The lower Ñr2 is the better. Table 1 summarizes our results including the sparsity percentage. The last line presents r(ai; a j) correlation associated to output space, for a strong correlation r(xi; x j) = 90% in input space. We note that the correlation gain is accom

Method Level Sparsity

Ñr2 r = 90%

SC (0:2) 5:82% 126:75 31%

GSC (0:4; 0:2) 9:36% 116:59 75%

JSC (0:4; 0:2) 15:05% 81:83 63%

GSC (0:2; 0:2) 17:66% 108:77 79%

JSC (0:2; 0:2) 22:75% 73:35 70% panied by a sparsity level drop. Thus, l is increasing sparsity while b is working in the opposite direction. 4

Dictionary Learning

The analytical solution to update a dictionary D ,[d1; : : : ; dK ] off-line exists and it is formulated as D = (XAT )(AAT ) 1, where A , faig; i = 1; : : : ; N and A 2 RK N . The problems comes from the computation of (AAT ) 1. It is a matrix of size (K K) and the computational complexity of this matrix inversion is in O(K3). Moreover, we have to store the matrix A in central memory. Thus, we want efficient methods (in term of complexity and memory occupation) to train such dictionaries under basis constraints. One would minimize the regularized empirical risk Rn:

RN (A; D) , 1 N

å l(xi; f (ai; D)) + G(A);

N i=1 where f (ai; D) = Dai, l(:) is typically a quadratic loss function and G(:) represents the regularization term (for example SC and GSC regularization terms). Eq. 5 would be optimized iteratively by a (stochastic) gradient descent. Unfortunately, the problem is not jointly convex but only conditionally convex. Alternatively, we can minimize: 1 N 1

å

N i=1 2 RN (AjDˆ ) , kxi

k Dˆ aik22 + G(ai); s:t: ai 1 and 5 5.1

Experiments

Metrics 1 N 1

å

N i=1 2 RN (Dj Aˆ) , kxi

D aˆik22 s:t:kdkT dkk22 = 1 and dkj 0: In order to obtain a suboptimal solution of eq. 5., eq. 6 can be solved efficiently in parallel via SC/GSC procedures while eq. 7 can be solved by a constrained linear system [ 13 ].

In this section we present some results obtained with SC and GSC dictionaries when we use SC and JSC for the encoding part. We fix the dictionary size to K = 1024 and a positivity constraint on dictionary columns and sparse codes are applied. The regularization parameters are l = 0:2 for SC, (l = 0:4 ; b = 0:2) and (l = 0:2 ; b = 0:2) for GSC and JSC for encoding part. Only the GSC (l = 0:2, b = 0:2) dictionary will be used. We measure a classification rate given by a 1-vs-all approach thanks to a linear Support Vector Machine (SVM). Its regularization parameter is fixed to C = 0:07. This classification is made by an Average Overall Accuracy (AOA):

AOA = 1 N ( 1 N

å å d(yˆi;m M m=1 N i=1

) yi;m) ; (5) (6) (7) (8) where N represents the number of available data, d the loss function chosen (mean square error), M, the number of cross validation and yˆi;m and yi;m, the true and predicted label. We realize our experiments on UIUCsportss database [ 11 ] and scenes15 database [ 8 ]. UIUCsportss database contains 1579 images from 8 different classes. The number of images in each class varies from 137 to 250. We randomly select 70 images from each class for training and 60 for testing. scenes15 database contains 4485 images belonging to 15 different categories and the number of images per class varies between 200 to 400. 100 images are selected for training part and the others for testing part. In our experiments, M = 10, NUIUCsports = 60 8 = 480 and Nscenes15 = 4485 15 100 = 2985. We extract densely SIFT patches (24 24) [ 12 ] with a grey level and on one scale. The grid size is 80 80 for UIUCsportss database and 30 30 for scenes15 database. We apply a Spatial Pyramid Matching (SPM) [ 8 ] which is defined on L levels. For UIUCsportss, L = 2, thus pooling is performed on the entire image ((1 1) - first layer) and the second layer on (2 2) grid with stride of 25%. For scenes15, L = 3, thus we use (1 1), (2 2) and (4 4) sub-regions for SPM. We apply μ-pooling (μ = 2:5) for the pooling step 1. 1 As remind, μ-pooling is written as f (v; w; μ) = åcm=1 wmvμm = wT vμ s:t:kwk22 = 1 and μ 6= 0, where vμ = aμm ; m = 1; : : : ; c and wm encodes the contribution of the m-image location for specific visual words [ 7 ]

XXXXDictionary

Encoding XXX

SC (0:2) GSC (0:2; 0:2)

SC (0:2) gain (until +8 points) with SC dictionary. This is less significant with GSC (0.2,0.2) dictionary where few relative gains are observed. For dictionary fusion, strong relative PP Encoding DictionParyPPPPP fusion 16 14 12 %10 n i AO8 A ifno 6 a g litveeR 24 a 0 −2 −4 gains are viewed for SC and the two GSC encoding models. There is no gain for the two JSC encoding models. The best result is for SC dictionary and encoding with SC and GSC (0.2,0.2) dictionary with SC encoding. The table 5 summarizes our results: No gain is observed for this dataset. The best re

XXXXDictionary

Encoding XXX sults are for SC dictionary and encoding. Fusion results which follow, are summarized in tables 6 and 7 which present fusion results obtained. Figures 4 and 5 illustrate the previous tables respectively. We notice that the behaviour is inverted for the two fuGSC (0.4,0.2) JSC (0.4,0.2) GSC (0.2,0.2) JSC (0.2,0.2) SC + GSC (0.4,0.2) SC + JSC (0.4,0.2) SC + GSC (0.2,0.2) SC + JSC (0.2,0.2) PP Encoding DictionParyPPPPP fusion

SC

GSC (0.4,0.2) JSC (0.4,0.2) GSC (0.2,0.2) JSC (0.2,0.2) SC

GSC (0.2,0.2) sion cases. However, the deficits decrease with fusion and more specifically for GSC (0.2,0.2) dictionary. For the dictionaries fusion, it is between the two models that we obtain the most significant gain. The best result is for the couple (SC + GSC) dictionary associated with SC encoding. To go further more, we plot the accuracy for a weighted arithmetic fusion. In a first time, the weights are the same for each classes and curves of figure 6 illustrate the weighted arithmetic fusion (AOAarith =SC +(1 μ)AOAGSC ). We notice for UIUCsports, when we use adapted coefficients with fusion, no improvement is observed and the accuracy 1.5 1 0.5 in% 0 A fAO−0.5 o n iga −1 e v it lea−1.5 R −2 −2.5 −3

UIUCsports scenes15 0.1 0.2 0.3 0.4

We0.i5ght 0.6 0.7 0.8 0.9 1 SC decreases considerably for other couples. For scenes15, a very small improvement is seen but it does not allow us to conclude to the real benefit of the method. Another alternative would be to calculate others means as harmonic or energy means for examples. Also, the considerable gain obtained with UIUCsports database can be explained by putting forward two assumptions: the heterogeneity between images of training and testing sets and the correlation conservation between the input and output space. The study conducted so far shows that the second assumption is the one that goes in the right direction. 6

Conclusion

Although the results obtained with GSC and JSC alone are not living up to our expectations, we highlight the relevance of our proposal, thanks to the fusion procedure which

Initial accuracy Blinded fusion Weighted fusion State-of-the-Art 87:27% 1:33 95:37% 1:29 95:37% 1:29 88:47 2:32 [ 23 ] 84:69% 0:6 84:66% 0:64 84:88% 0:55 81:04% 0:5 [ 8 ]

Table 8. Summarize of fusion results - details in Tables 2, 3, 4, 5, 6, 7. greatly improves the State-of-the-Art for UIUCsports (88:47 2:32) of [ 23 ] (our modeling: 95:37 1:29). A complete study must be realized with different couples (l; b) for dictionary and encoding parts to find the right setting for UIUCsports and scenes15 databases. Also, the nature of the images is to be considerate and a study of the heterogeneity level of images could be achieved [ 22 ] through the Shannon entropy measure. However, we think that our modeling can be improved by three ways. The first will be to get even better stabilized JSC results by adding an outer loop in the JSC algorithm. After multiple stages, we can expect some improvements. The second is a direct extension of the JSC by integrating some Laplacian regularization computed from a training set of local features. Here, sparse codes will be reconstructed by simultaneously minimize the deviation from both this training set and the image local features. The fusion could be improved by weighted average fusion using statistic from code image. Finally, it had been shown that adding some orthogonal constraints during the dictionary learning process can improves results [ 5, 17 ]. Here, too, a full study should be conducted with the two methods of sparse codes encoding.

Acknowledgement. We thank Direction Ge´ne´rale de l’Armement (DGA) for a financial support to this research. We thank Lucian ALECU for his comments.

References

1. C. Bauge , M. Lagrange , J. Ande´n, and S. Mallat . Representing environmental sounds using the separable scattering transform . In ICASSP , pages 8667 - 8671 , 2013 .

2. Y. Bengio . Learning deep architectures for ai . Found. Trends Mach. Learn. , 2 ( 1 ): 1 - 127 , Jan. 2009 .

3. K. Chatfield , K. Simonyan , A. Vedaldi , and A. Zisserman . Return of the devil in the details: Delving deep into convolutional nets . CoRR, abs/1405.3531 , 2014 .

4. S. S. Chen , D. L. Donoho , Michael, and A. Saunders . Atomic decomposition by basis pursuit . SIAM Journal on Scientific Computing , 20 : 33 - 61 , 1998 .

5. A. Cherian . Nearest neighbors using compact sparse codes . In T. Jebara and E. P. Xing, editors, Proceedings of the 31st International Conference on Machine Learning (ICML - 14) , pages 1053 - 1061 . JMLR Worshop and Conference Proceedings, 2014 .

6. J. Deng , K. Li , M. Do , H. Su , and L. Fei-Fei . Construction and Analysis of a Large Scale Image Ontology . Vision Sciences Society , 2009 .

7. J. Feng , B. Ni , Q. Tian , and S. Yan . Geometric `p-norm feature pooling for image classification . In CVPR , pages 2697 - 2704 , 2011 .

8. S. Lazebnik , C. Schmid , and J. Ponce . Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories . In Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 , CVPR ' 06 , pages 2169 - 2178 , Washington, DC, USA, 2006 . IEEE Computer Society.

9. Y. LeCun , K. Kavukcuoglu, and C. Farabet . Convolutional networks and applications in vision . In ISCAS, pages 253 - 256 . IEEE, 2010 .

10. H. Lee , A. Battle , R. Raina , and A. Y. Ng . Efficient sparse coding algorithms . In In NIPS, pages 801 - 808 . NIPS, 2007 .

11. L. -J. Li . What, where and who? classifying event by scene and object recognition . In In IEEE International Conference on Computer Vision , 2007 .

12. D. G. Lowe. Object recognition from local scale-invariant features . In Proceedings of the International Conference on Computer Vision-Volume 2 - Volume 2, ICCV ' 99 , pages 1150 -, Washington, DC, USA, 1999 . IEEE Computer Society.

13. J. Mairal , F. Bach , J. Ponce , and G. Sapiro . Online dictionary learning for sparse coding . In Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09 , pages 689 - 696 , New York, NY, USA, 2009 . ACM.

14. M. Muja and D. G. Lowe . Scalable nearest neighbor algorithms for high dimensional data . Pattern Analysis and Machine Intelligence , IEEE Transactions on, 36 , 2014 .

15. G. V. Pendse . A tutorial on the lasso and the ”shooting algorithm” . Technical report , P.A.I.N Group, Imaging and Analysis Group - McLean Hospital , Harvard Medical School, 8 February 2011 .

16. F. Perronnin , J. Sa ´nchez, and T. Mensink . Improving the fisher kernel for large-scale image classification . In Proceedings of the 11th European Conference on Computer Vision: Part IV, ECCV'10 , pages 143 - 156 , Berlin, Heidelberg, 2010 . Springer-Verlag.

17. I. Ramirez , F. Lecumberry , and G. Sapiro . Universal priors for sparse modeling . In Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) , 2009 3rd IEEE International Workshop on, pages 197 - 200 , Dec 2009 .

18. O. Russakovsky , J. Deng , H. Su , J. Krause , S. Satheesh , S. Ma , Z. Huang , A. Karpathy , A. Khosla , M. Bernstein , A. C. Berg , and L. Fei-Fei . Imagenet large scale visual recognition challenge , 2014 .

19. J. Sivic and A. Zisserman. Video Google : A text retrieval approach to object matching in videos . In Proceedings of the International Conference on Computer Vision , volume 2 , pages 1470 - 1477 , Oct. 2003 .

20. J. J. Thiagarajan , K. N. Ramamurthy , and A. Spanias . Local Sparse Coding for Image Classification and Retrieval . Technical report , 2012 .

21. R. Tibshirani . Regression shrinkage and selection via the lasso . Journal of the Royal Statistical Society , Series B, 58 : 267 - 288 , 1994 .

22. S. Tollari and H. Glotin . Lda versus mmd approximation on mislabeled images for keyword dependant selection of visual features and their heterogeneity . In IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) , volume II, pages 413 - 416 , may 2006 .

23. X. Wang , B. Wang , X. Bai , W. Liu, and Z. Tu . Max-margin multiple-instance dictionary learning . In S. Dasgupta and D. Mcallester , editors, Proceedings of the 30th International Conference on Machine Learning (ICML-13) , volume 28 , pages 846 - 854 . JMLR Workshop and Conference Proceedings, May 2013 .

24. B. Xie , M. Song , and D. Tao . Large-scale dictionary learning for local coordinate coding . In Proceedings of the British Machine Vision Conference , pages 36 . 1 - 36 .9. BMVA Press, 2010 . doi: 10 .5244/C.24.36.

25. M. Zheng , J. Bu , C. Chen , C. Wang , L. Zhang , G. Qiu, and D. Cai . Graph regularized sparse coding for image representation . IEEE Transaction on Image Processing , 20 ( 5 ): 1327 - 1336 , 2011 .