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 Ψ j (.; µ j ) with parameter µ j which characterizes the class C j satisfying: dist(Ψ j (I 1 ; µ j ), Ψ j (I 2 ; µ j )) → 0 if I 1 ∈ C j and I 2 ∈ C j dist(Ψ j (I 1 ; µ j ), Ψ j (I 2 ; µ j )) → ∞ if I 1 ∈ C j and I 2 / ∈ C j ,
where I 1 and I 2 are two images. The choice of Ψ 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 ∈ R d to obtain the global representation Ψ j (.; µ j ). From Ψ 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.
In this part, we will focus on the encoding step using linear coding to reconstruct inputs. An approximation of any patches x ∈ R d can be given by x i = Dα i , where
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 α * i 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]:
with λ the regularization parameter associated to the SC formulation. This parameter controls the sparsity level as is shown in [15]. Thus, the more λ is large, the more α * i (solution of eq.2) will be sparse.
Usually in SC framework, if we take two neighbor patches x i and x j (with a strong correlation between them), their respective sparse codes, α i and α 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 X
where
, L = L i j i, j=1,...,N train is a Laplacian matrix and β a regularization parameter. The matrix L is defined by L = S − W, where W is a weight matrix with and W i, j = exp{−
is the set of neighborhood of x i excluding x i itself), W i, j = 0 else. The matrix S is diagonal and
We propose to improve SC by simultaneously encoding all the test local patches (for example associated with a test image). This new modeling will be inspired from the GSC.
JSC principle is to jointly encode all local features X test = {x test 1 , . . . , x test N test } simultaneously to overcome the decorrelation problem. We also enforce α k i ≥ 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:
where
Here, A test {α test 1 , . . . , α test N test } are computed and stacked initially. In practice N test << N train , so we need to store only a sparse K × N test matrix.
Our Laplacian matrix (N test × N test ) 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) × N test ) with the previous formulation. Each column of this ((v + 1) × N test ) matrix is denoted by L i . 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 β) 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
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 ρ(x, y) = x T y x 2 y 2 ∈ [0, 1]. We also introduce the scalar value 2 which measures the average quadratic difference between normalized correlation of the input space and the output space. The lower ∇ρ 2 is the better. Table 1 summarizes our results including the sparsity percentage. The last line presents ρ(α i , α j ) correlation associated to output space, for a strong correlation ρ(x i , x j ) = 90% in input space. We note that the correlation gain is accom- panied by a sparsity level drop. Thus, λ is increasing sparsity while β is working in the opposite direction.
The analytical solution to update a dictionary D [d 1 , . . . , d K ] off-line exists and it is formulated as D = (XA T )(AA T ) −1 , where A {α i }, i = 1, . . . , N and A ∈ R K×N . The problems comes from the computation of (AA T ) −1 . It is a matrix of size (K × K) and the computational complexity of this matrix inversion is in O(K 3 ). 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 R n :
R N (A, D)
where f (α i , D) = Dα i , l(.) is typically a quadratic loss function and Γ(.) 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:
R N (A| D)
and
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].
5 Experiments
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 λ = 0.2 for SC, (λ = 0.4 ; β = 0.2) and (λ = 0.2 ; β = 0.2) for GSC and JSC for encoding part. Only the GSC (λ = 0.2, β = 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):
where N represents the number of available data, δ the loss function chosen (mean square error), M, the number of cross validation and ŷi,m and y i,m , the true and predicted label. We realize our experiments on UIUCsportss database [11] and scenes15 database 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 .
Table 2 summarizes obtained results. We observe different behaviours. If we focus on encoding part variations (horizontal reading), we see that for all dictionaries choices, SC encoding is the best. Any gain is viewed for the others and a similar behavior is obtained if we read the table vertically. To go further more, in order to evaluate if SC and JSC models are complementary, we measure the accuracy of the arithmetic and geometric means of their estimates (AOA arithmetic and AOA geometric). AOA arithmetic is defined as the sum of probabilities of two selected models and AOA geometric as the 1 As remind, µ-pooling is written as square root of the product of two selected models. Tables 3 and 4, associated to figures 2 and 3 respectively (only the arithmetic fusion is showed here, because geometric fusion is lower than the first), summarize results obtained with initial models and their associated fusion. Fig. 2. Benefits and deficits obtained with GSC, JSC and arithmetic fusions encodings compared to SC encoding for the three different dictionaries for UIUCsports database. 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 4. Evolution of the arithmetic and geometric Accuracy for UIUCsportss database (dictionary fusion). The best result is obtained with the couple SC and GSC (0.2,0.2) dictionaries associated with SC encoding.An illustration is given in figure 3 SC GSC (0.4,0. Relative gain of AOA in % GSC (0.2,0.2) SC + GSC (0.2,0.2) Fig. 3. Beneficits and deficits obtained with GSC and arithmetic fusions dictionaries compared to SC dictionary with five different encoding method choices for UIUCsports database. 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 7. Evolution of the arithmetic and geometric Accuracy for scenes15 database (dictionary fusion). The best result is obtained with the couple SC and GSC (0.2,0.2) dictionaries associated with SC encoding.An illustration is given in figure 5 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 (AOA arith = SC +(1 − µ)AOA GSC ). We notice for UIUCsports, when we use adapted coefficients with fusion, no improvement is observed and the accuracy Relative gain of AOA in % GSC (0.2,0.2) SC + GSC (0.2,0.2) Fig. 5. Beneficits and deficits obtained with GSC and arithmetic fusions dictionaries compared to SC dictionary with five different encoding method choices for scenes15 database. Fig. 6. Evolution of the accuracy with different coefficient. The first point corresponds to the chosen model for fusion and the last point is the SC model. Notice the best result for UIUCsports is obtained with a coefficient of 0.5, and for scenes15, it is 0.8 for SC and 0.2 for GSC (0.2,0.2) dictionary associated with SC. For these two examples, the fusion is between SC (dictionary and encoding) and GSC (0.2,0.2) dictionary with SC encoding.
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.
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 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 (λ, β) 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 Générale de l'Armement (DGA) for a financial support to this research. We thank Lucian ALECU for his comments.