Discriminant Tensor Dictionary Learning with Neighbor Uncorrelation for Image Set Based Classification

1 Introduction

In recent years, image set based classification (ISC) has attracted lots of research interest in computer vision and pattern classification communities [Zhang et al., 2016]. An image set can convey rich within-class variations of an object, which is helpful for classification. ISC is also a challenging task, and how to effectively model a set and compute the similarity between two sets is a crucial research topic.

Over the past several years, we have witnessed a lot of methods developed for ISC. The subspace-based and manifold-based methods [Wang and Chen, 2009; Wang et al.,

∗Corresponding authors

2015] separately use subspace and manifold to model an image set, and the performances of them may degrade when the set has a small sample size but big data variations [Hu et al., 2012]. In affine or convex hull based methods [Hu et al., 2012; Cevikalp and Triggs, 2010], the between-set distance is defined as the distance between two closest points of two sets. This kind of methods relies highly on the location of each individual sample in the set, and the model fitting can be heavily deteriorated by outliers [Wang et al., 2012]. Covariance matrix based methods [Wang et al., 2012; Lu et al., 2013] try to explore the second-order statistics of image set and represent each set with its covariance matrix, while they cannot explore intrinsic high-order structure of image set. Deep learning based methods [Hayat et al., 2015; 2014; Shah et al., 2016] introduce an adaptive multi-layer neural network structure and use it for learning class specific models. However, these deep learning based methods require a large amount of computation time.

Recently, a few sparse/collaborative representation and dictionary learning based methods have been developed for ISC and obtain state-of-the-art classification performance [Zhu et al., 2014; Zheng et al., 2017; Chen et al., 2012]. This family of methods usually builds one dictionary for each image set or class, and uses the dictionaries to measure the similarity of image sets.

1.1 Motivation

Almost all the previous works transform the image sample in the set into a vector for subsequent processing, as shown in Fig. 1(a), which not only breaks the inherent spatial structure of image samples but also breaks the structure of the image set. In fact, an image is a data matrix with the size of dW×dH. And an image set is a three-dimensional data array with the size of dW×dH×dN, where dN denotes the number of images in the set, as shown in Fig. 1(b). How to effectively model the image set without breaking its inherent structure and provide a corresponding similarity measure between sets is a crucial research topic.

Tensor is effective to model an image or image ensembles, and tensor-based learning methods can well retain the spatial structures of image and image ensembles [Li and Schonfeld, 2014]. On the other hand, existing dictionary learning based ISC methods own interesting classification effects [Zhu et al., 2014; Lu et al., 2014]. Inspired by these two aspects, we intend to employ the tensor dictionary learning (TDL) technique for ISC.

Figure 1: Illustration of the general difference between our work and existing ISC works. D(W) and D(H) are spatial dictionaries and D(N) denotes the set dictionary. X is the sparse representation coefficient tensor. The constructed third-order tensor can be well represented by linear combination of columns in D(W), D(H) and D(N).

Nowadays, some TDL methods have been addressed [Peng et al., 2014; Zubair et al., 2014]. Compared with traditional dictionary learning technique [Zhu et al., 2014], the TDL technique can learn multiple dictionaries, with each corresponding to one mode of training tensors, which can fully exploit the information contained in training samples. However, for existing TDL methods, there still exists much room for improvement:

(1) Existing TDL methods mainly focus on the reconstruction accuracy, whereas enhancing the total discriminability of tensor dictionaries has not been investigated comprehensively and thoroughly.

(2) Information redundancy among image sets will lead to redundancy in the learned dictionaries. How to effectively reduce the redundancy between tensor dictionaries corresponding to different classes has not yet been well studied.

1.2 Contribution

(1) We introduce the idea of tensor to model image set, which can preserve the structure of image set. And we propose a discriminant tensor dictionary learning with neighbor uncorrelation (DTDLNU) approach, which jointly learns two spatial dictionaries and one set dictionary. These three dictionaries jointly reflect the spatial structure of image sets. The spatial dictionaries and the set dictionary are composed by set-specific sub-dictionaries corresponding to the class labels, such that the obtained reconstruction error is discriminative. Fig. 1 illustrates the general difference between our work and existing ISC works.

(2) We design a neighbor-uncorrelated discriminant tensor dictionary term for TDL, which minimizes the withinclass scatter of the training sets in the projected tensor space and reduces tensor dictionary correlation among setspecific sub-dictionaries corresponding to neighbor image sets from different classes. This designed term can make the learned dictionaries have favorable discriminative power and low between-class correlation.

2 Brief Review of RelatedWork

2.1 Image Set based Classification (ISC) Methods

Current ISC methods can be generally categorized into five kinds:

(1) Subspace and manifold based methods. Manifold discriminant analysis (MDA) [Wang and Chen, 2009] aims to learn an embedding space by maximizing manifold margin. The discriminant analysis on Riemannian manifold of Gaussian distributions (DARG) [Wang et al., 2015] method represents image set as Gaussian mixture model comprising a number of Gaussian components and seeks to discriminate Gaussian components from different classes.

(2) Affine/convex hull based methods. Cevikalp and Triggs [2010] presented the affine hull based image set distance (AHISD) and convex hull based image set distance (CHISD) methods. Sparse approximated nearest points (SANP) method [Hu et al., 2012] focuses on nearest points of two image sets, which can be sparsely approximated by the samples of its respective set.

(3) Covariance matrix based methods. Covariance discriminative learning (CDL) [Wang et al., 2012] represents each image set with its covariance matrix and models the ISC problem as classifying points on the Riemannian manifold. Localized multi-kernel metric learning (LMKML) [Lu et al., 2013] regards the out product between the covariance matrix and mean of image set as the third-order statistics, and combines the third-order statistics, second-order statistics (covariance matrix) and first-order statistics (mean vector) information for classification.

1. Deep learning based methods. The deep reconstruction model with weighted voting (DRM-WV) [Hayat et al., 2015] method designs a multi-layer neural network to learn class-specific deep reconstruction models. With the learned models, DRM-WV uses reconstruction error based weighted voting strategy for classification.

(5) Sparse/collaborative representation and dictionary learning based methods. The image set based collaborative representation and classification (ISCRC) method [Zhu et al., 2014] models the query set as a convex or regularized hull, and represents the hull collaboratively over all the gallery sets for classification. The dictionary-based face recognition from video (DFRV) method [Chen et al., 2012] builds one dictionary for each face image set and uses the learned dictionaries to measure the similarity of face image sets. The simultaneous feature and dictionary learning (SFDL) method [Lu et al., 2014] jointly learns a feature projection matrix and structured dictionary for image set based face recognition.

As analyzed in Introduction, there exist respective shortcomings in these five categories of methods.

2.2 Tensor Dictionary Learning (TDL) Methods

Based on the theory of tensor, nowadays, some TDL methods have been developed [Quan et al., 2015]. Considering the nonlocal similarity over space and the global correlation across spectrum, Peng et al. (2014) designed a decomposable nonlocal TDL method for multispectral image denoising. Roemer et al. [Roemer et al., 2014] presented tensor extensions of the popular MOD and K-SVD dictionary learning algorithms and obtained the tensor-MOD and higher-order KSVD (K-HOSVD) algorithms. With the region covariance descriptor, Zhang et al. [Zhang et al., 2013] introduced structural incoherence constraint between dictionary atoms from different classes to promote discriminating information into the dictionary.

As analyzed in Motivation, there exists much room for improvement in existing TDL methods. In addition, the TDL technique has not been used to solve the ISC problem.

3 Definitions and Notations

Let A ∈ RI1×···×In×···×IN be a tensor of order N, whose elements are denoted as ai1···in···iN , 1 ≤ in ≤ In. The Frobenius norm of the tensor A is defined as ‖A‖F =

Definition 1 (Tensor Matricization, Mode-n Product, and Kronecker Product): The mode-n matricization of A is A(n) ∈ RIn×(I1···In-1In+1···IN) . The mode-n product of A by a matrix B ∈ RJn×In , denoted by A×nB, is also an N th - order tensor C ∈ RI1×···×Jn×···×IN . The mode-n product C = A×nB can also be calculated by C(n) = BA(n). For C = A×1B1×2B2×3 · · ·×NBN, we can simplify the notation as C =A ∏Nk=1 ×kBk. The Kronecker product of matrices A ∈ RI×J and B ∈ RL×M , denoted by A⊗B, is a matrix of size (IL)×(JM). The detailed definitions can be found in [Li and Schonfeld, 2014]

Definition 2 (Block-sparsity): The concept of block sparsity for tensor is presented in [Peng et al., 2014]. For the tensor A, its block-sparsity with respect to N modes is ‖A‖B = (r1, r2, · · ·, rN) if and only if the smallest index subsets I1, I2, · · ·, IN satisfying ai1i2···iN = 0 for all (i1, i2, · · ·, iN) /∈ I1×I2×· · ·IN contain r1, r2, · · ·, rN elements, respectively. Sub(A) ∈ Rr1×r2×···rN denotes the intrinsic sub-tensor of A extracted from the entries of the N dimensions of A specified by the index sets I1, I2, · · ·, IN, respectively.

4 The Model of DTDLNU

4.1 Neighbor-uncorrelated Discriminant Tensor Dictionary Term

Let Y = {Yc} , c = 1, · · ·,C be the training set containing image sets from C different classes and Yc = {Ylc}Lc l=1 be the collection of image sets of the cth class, where Lc is the number of image sets in Yc. Each Ylc contains a set of images with the size of dW × dH, where dW and dH separately denote the spatial width and height of an image. The number of images in Ylc is denoted by dN. Then, each Ylc can be expressed as a 3rd -order tensor Y lc ∈ RdW×dH×dN with two spatial modes and one set mode.

and one structured set dictionary D(N) = [D1(N) 1 ,· · ·,DL1(N) 1 ,· · ·,D1(N) C ,· · ·,DLC(N) C ]∈RdN×mN from the total training set, where Dl(W) c ∈ RdW×rl(W) c (rl(W) c ≤ dW), Dl(H) c ∈ RdH×rl(H) c (rl(H) c ≤ dH) and Dl(N) c ∈ RdN×rl(N) c (rl(N) c ≤ dN) are set-specified sub-dictionaries associated with the lth set of the cth class, and mW > dW, mH > dH and mN > dN. Here, W, H and N separately represent the width, height and set modes of Y lc . rl(W) c , rl(H) c and rl(N) c denote the numbers of atoms in dictionaries Dl(W) c , Dl(H) c and Dl(N) c , respectively. And mW = C∑ c=1 Lc∑l=1 rl(W ) c ,

The quality of the learned dictionary influences the performance of subsequent tensor sparse representation based classification. To make the learned dictionaries be discriminative for image sets in Y, we require that the within-class scatter in the projected tensor space should be minimized. The mode-i within-class scatter matrix in the partially projected tensor subspace (by all tensor modes except for i) can be defined as:

where i = {W,H,N}, (·)T denotes the transposition operation andMc = 1Lc ∑Lc l=1 Y lc is the class mean tensor for class c. Therefore, we should minimize the value of

Due to the information redundancy between image sets, there exists much redundancy in dictionary of each mode. To reduce the redundancy and further enhance discriminabilities for dictionaries, we require that the set-specific tensor sub-dictionaries of different classes own low correlation. Reducing the correlation between sub-dictionaries of different classes can make that a set should be more likely to be represented by sub-dictionaries of its own class rather than those of the other classes, and thus generally results in improved discriminative power. In real-world ISC applications, the number of training image sets may be very large, and for the observed image set, only a few sets with different class labels are close to it. Focusing on these inseparable sets, we require that the set-specific sub-dictionaries corresponding to the neighbor image sets that are from different classes should own low tensor dictionary correlation. Thus, we should minimize

whereβhq cl = { 1, if Y qh is one of the k nearest neighbors of Y lc 0, otherwise

.

By minimizing u(D(W),D(H),D(N)), we can reduce the local between-class tensor dictionary correlation.

4.2 The Objective Function of DTDLNU

Considering the dictionary reconstruction error and the neighbor-uncorrelated discriminant tensor dictionary term, we formulate the objective function of DTDLNU as follows:

where X l c ∈ RmW×mH×mN is the sparse coding coefficient tensor of Y lc over D(W) ,D(H) and D(N) , v1≺ v2 denotes that each entry of v1 is no more than the corresponding entry of v2. The block-sparsity of X l c guarantees that X l c is only associated with rl(W) c , rl(H) c , rl(N) c atoms of dictionaries D(W) ,D(H) ,D(N) , respectively. λ is a balance factor.

Due to the redundancy setting of spatial and set dictionaries, we can assume that each training image set Y lc is only related to the sub-dictionaries: Dl(W) c , Dl(H) c and Dl(N) c , which is similar to the idea in [Peng et al., 2014]. Then, we can get

where Sub(X l c ) ∈ Rrl(W) c ×rl(H) c ×rl(N) c is the intrinsic subtensor of X l c .

When updating the variables corresponding to the lth image set from the cth class, the variables corresponding to other image sets are supposed to be fixed. To update X l c , Dl(W) c , Dl(H) c and Dl(N) c , (4) can be reduced to:

where G lc = Sub(X l c ) ∈ Rrl(W) c ×rl(H) c ×rl(N) c is the representation coefficient tensor of Y lc over Dl(W) c , Dl(H) c , and Dl(N) c .

5 Optimization of DTDLNU

There is no theoretical guarantee that the objective function (6) is jointly convex to (G lc , Dl(W) c , Dl(H) c ,Dl(N) c ); however, it is convex with respect to each of G lc , Dl(W) c , Dl(H) c , andDl(N) c when the others are fixed. We develop an iterative algorithm to optimize the variables alternatively.

When updating G lc , Dl(i) c (i =W,H,N) is supposed to be fixed. Then, (6) is reduced to

Algorithm 1 Optimization process of DTDLNU

1. Initialize D(W) , D(H) and D(N) . Initialize all the atoms of D(i) (i =W,H,N) as random vectors, and orthonormalize each column of dictionaries.
2. Update Glc and Dl(i) c (i =W,H,N).
3. Fix Dl(i) c (i =W,H,N), and calculate the coefficient tensor Glc with (9).
4. Fix Glc and Dl(j) c (j ̸= i), and update Dl(i) c by solving (11). Orthonormalize each atom of Dl(i) c .

3. Output.

Return to step 2 until the values of (4) in adjacent iterations are close enough. Output D(W) , D(H) and D(N) .

According to [Lathauwer et al., 2000], the solution can be obtained by solving a classical linear least-squares problem:

To avoid G lc being overdetermined, we orthonormalize each column of Dl(i) c (i =W,H,N). Then we can get

When updating Dl(i) c , G lc and Dl(j) c (j ̸= i) are fixed. To calculate Dl(i) c , we can solve the following problem:

where Y lc(i) and G lc(i) are separately the mode-i unfolded forms of Y lc and G lc , and

(11) is a standard Sylvester equation, which can be effectively solved using existing tools [Bartels and Stewart, 1972]. Algorithm 1 describes the optimization of DTDLNU. The optimization is an example of generalized block coordinate descent algorithm where its convergence has been theoretically analyzed for multiconvex optimization [Xu and Yin, 2013].

6 The Classification Scheme of DTDLNU

When {D(W) ,D(H) ,D(N)} is available, a test image set can be classified via coding it over these dictionaries. For the given test image set Ztest , we can organize it as a 3rd -order tensor Z test ∈ RdW×dH×dN . The sparse coding coefficient tensor Q can be obtained by solving:

where S0 refers to the total sparsity (i.e. the number of nonzeros) of Q. Q can be achieved with the Tensor-OMP algorithm [Caiafa and Cichocki, 2012]. The reconstruction error associated with the cth (c = 1, · · ·, C) class is computed by:

where Qlc is the coding coefficient tensor corresponding to the lth set of the cth class. The classification can be done by assigning the test image set to the class with the smallest reconstruction error.

7 Experiments

7.1 ComparedMethods

In experiments, we compare DTDLNU with five categories of state-of-the-art related methods including:

1. Subspace and manifold based methods: MDA [Wang and Chen, 2009] and DARG [Wang et al., 2015];
2. Affine/convex hull based methods: AHISD [Cevikalp and Triggs, 2010], CHISD [Cevikalp and Triggs, 2010] and SANP [Hu et al., 2012];
3. Covariance matrix based methods: CDL [Wang et al., 2012] and LMKML [Lu et al., 2013];
4. Deep learning method: DRM-WV [Hayat et al., 2015];
5. Dictionary learning based methods: ISCRC [Zhu et al.,
6. 2014], DFRV [Chen et al., 2012] and SFDL [Lu et al., 2014].

7.2 Datasets

In experiments, we use three challenging and large datasets, i.e., YouTube Celebrities (YTC) [Kim et al., 2008], COX [Huang et al., 2015], and YouTube Faces (YTF) [Wolf et al., 2011]. YTC contains 1,910 video sequences of 47 celebrities from YouTube. COX is a dataset involving 1,000 different subjects, each of which has 3 videos captured by different camcorders. YTF contains 3,425 videos of 1,596 subjects downloaded from YouTube. And there are large variations in pose, illumination, expression, and resolution in these videos.

We employ the Viola-Jones face detector [Viola and Jones, 2004] to detect the faces in each frame and resize the detected faces to gray-scale images of 30×30 for YTC, 32×40 for COX, and 30×30 for YTF. Histogram equalization is implemented to reduce the illumination variations.

7.3 Experimental Settings

To make a fair comparison with related ISC methods, we follow the protocol used in [Wang et al., 2015; Hayat et al., 2015; Zhu et al., 2014; Lu et al., 2014]. On YTC, ten random selections for training and testing videos are conducted for reporting average experimental results. The whole dataset is equally divided into ten folds with each containing 9 videos per subject. In each fold, 3 videos per subject are randomly selected for training, and the remaining 6 are selected for testing. For COX, we follow the same protocol as the prior work [Huang et al., 2015; Wang et al., 2015], which conducted ten-fold cross validation, i.e., 10 randomly selected gallery/probe combinations. Since there are 3 independent testing sets of videos in COX, each person has one video as the gallery and the remaining two videos for two different probes, thus in total 6 groups of testings need to be conducted. For YTF, we follow the standard evaluation protocol [Wolf et al., 2011]. 5,000 video pairs are collected randomly and half of them are from the same subject, half from different subjects. These pairs are then divided into 10 splits and each split contains 250 intrapersonal pairs and 250 inter-personal pairs. The evaluation protocol of YTF was originally developed for face verification. For verification, we compute the class label for each video in the given video pair with our classification scheme, and then make a decision whether the video pair is an intrapersonal pair or not. We perform 10-fold cross validation. For these datasets, one video is regarded as an image set.

In experiments, the tuning parameters (the balance factor λ and the neighboring set number k ) of DTDLNU are set by using 5-fold cross validation with training data. Concretely, they are set as λ = 1.5 and k = 50 on YTC; λ = 0.8 and k=90 on COX; and λ=1.5 and k=220 on YTF. The default dictionary atoms number for each set in DTDLNU, which is associated with rl(W) c , rl(H) c and rl(N) c , is set as rl(W) c =dW, rl(H) c =dH and rl(N) c =dN. S0 can be automatically selected.

7.4 Results and Analysis

Comparison with the State-of-the-Arts: Table 1 shows average recognition/verification results of compared methods on three datasets. From Table 1, DTDLNU performs better than eleven compared ISC methods on the YTC and YTF datasets. On COX, DTDLNU also outperforms the recently presented ISC methods, like [Wang et al., 2015; Hayat et al., 2015; Lu et al., 2014], in all testing cases. To observe the effect of using tensor for image set modeling intuitively, we also compare DTDLNU with the method that organizes image samples as vectors and learns ordinary dictionary (rather than tensor dictionary) by using the vector version of our objective function. We call this method as DTDLNUvec. It can be seen that DTDLNU significantly outperforms DTDLNUvec on all datasets. All these results indicate the effectiveness of modeling image set with tensor and learning uncorrelated discriminant tensor dictionaries.

Evaluation of the Neighbor-uncorrelated Discriminant Tensor Dictionary (NDTD) Term: Fig. 2 shows tensor Table 3: Computation time (seconds) of all compared methods on YTC for training and testing (classification of one image set).

dictionary correlation 1 of set-specific sub-dictionaries corresponding to different classes learned by DTDLNU and DTDLNUnoNDTD (the version of DTDLNU that does not include the NDTD term). In Fig. 2, we also report the interclass set-specific dictionary correlation corresponding to ISCRC and DFRV. Table 2 reports the classification results of DTDLNU and DTDLNUnoNDTD. In the table, we also report the results of DTDLNU only with part 1 or part 2 of the term. Here, part 1 means minimizing the within-class scatter in projected tensor space; and part 2 means minimizing correlation of sub-dictionaries corresponding to neighbor sets from different classes. It is noted that for COX, we report the average results across 6 groups of testings.

According to Fig. 2, with the designed term, DTDLNU owns lower between-class dictionary correlation. From Table 2, we can see that the designed term can improve the classification results, which demonstrates the effectiveness of the term. In addition, the part 1 plays a relatively more important role than the part 2 in the term.

Parameter Analysis: To evaluate the influences of the balance factor λ and the neighboring set number k, we separately conduct experiments by changing the values of λ from 0 to 1.5 with step length 0.05, and of k from 5 to 60 with step length 5 on YTC (when k > 60, the performance is stable, and when λ > 1.5, the performance will experience a slight decrease). Fig. 3 shows the classification accuracy of our approach versus different values of λ or k. We can see that its performances are stable with respect to λ in the range of [1.1,1.5], and with respect to k in the range of [50,60]. For simplicity, we set λ as 1.5 and k as 50 on YTC. A similar phenomenon also exists on the other two datasets.

Computational Time: Lastly, we report the computation-

1 Here, the between-class set-specific sub-dictionary correlation is calculated by corr= 1 Ns ∑ i={W,H,N} C∑ c=1 Lc∑l=1 C∑ h=1 Lh∑ q=1 ∥∥∥Dl(i) c T Dq(i) h ∥∥∥2 F.

Here, Ns denotes the number of accumulating calculations.

al time of compared methods. Our hardware configuration comprises a 2.8-GHz CPU and a 24GB RAM. Table 3 tabulates the computational time of different methods on YTC. The reported testing time refers to the time of classifying one image set. We can see that our approach requires less training time than that of LMKML, DRM-WV, DFRV and SFDL. In addition, the testing time of DTDLNU is comparable to that of other methods.

8 Conclusion

In this paper, by modeling an image set as a third-order tensor, we can well preserve the inherent spatial structure of the set. We for the first time introduce TDL into ISC for learning two spatial dictionaries and one set dictionary. We thus propose a novel ISC approach DTDLNU. It can make the obtained dictionaries have favorable discriminability and reduce the between-class tensor dictionary correlation. We apply DTDLNU for ISC tasks on three challenging datasets. Experimental results demonstrate that DTDLNU achieves better classification results than several state-of-the-art methods.

Acknowledgments

The work described in this paper was supported by the Scientific Research Staring Foundation for Introduced Talents in NJUPT (NUPTSF, No. NY217009), and Province-SchoolRegion Project of Henan University (No. 2016S11).