Label consistent transform learning for pattern classification

Abstract

Transform learning has been successfully applied to various image processing tasks in recent years. Nevertheless, transform learning learns the representation in an unsupervised fashion. To make transform learning suitable for pattern classification, we introduce a label consistency constraint into transform learning and propose a new label consistent transform learning to enhance the classification performance of transform learning. The resulting optimization problem can be solved elegantly by employing the alternative strategy. Experimental results on publicly available databases demonstrate that label consistent transform learning outperforms several dictionary learning approaches and the recently proposed discriminative transform learning. More importantly, label consistent transform learning has the least training time which has the potential in practical applications.

Introduction

Recent years have witnessed increasing interest in the study of dictionary learning (DL) in various domains, such as face recognition, ¹ image fusion, ² and person re-identification. ³ DL can be divided into two different types, i.e. synthesis dictionary learning (SDL) and analysis dictionary learning (ADL), according to how to encode the input data. SDL aims to learn a dictionary by which the input data can be reconstructed through the linear combination of atoms in the dictionary. The most classic SDL approach is the K-SVD algorithm ⁴ which has been successfully applied to image compression and denoising. However, K-SVD mainly focuses on the representational ability of the dictionary without considering its capability for classification. To address this problem, Zhang and Li ⁵ proposed a discriminative K-SVD (D-KSVD) method by introducing the classification error into the framework of K-SVD. Jiang et al. ⁶ further incorporated a label consistency constraint into K-SVD and presented a label consistent K-SVD (LC-KSVD) algorithm. Yang et al. ⁷ developed a Fisher discrimination dictionary learning method which imposes the Fisher discrimination criterion on the coding coefficients. Wang D and Kong ⁸ presented an SDL approach called COPAR which explicitly learns the shared patterns and the class-specific dictionaries. Li et al. ⁹ proposed a locality constrained and label embedding dictionary learning algorithm to take the locality and label information of atoms into account. Many SDL employs ℓ₀/ℓ₁ norm to promote sparsity of the coding, which will lead to high computational complexity. To alleviate this problem, Zhao et al. ¹⁰ designed an orthogonal collaborative dictionary learning method which can derive analytical solutions for both code learning and dictionary updating.

Although SDL achieves impressive results in classification tasks, it is time-consuming to learn the dictionary. Recently ADL has attracted lots of attention due to its efficacy and efficiency. Rubinstein et al. ¹¹ presented the analysis K-SVD which is parallel to the synthesis K-SVD. ⁴ Gu et al. ¹² developed a projective dictionary pair learning (DPL) which simultaneously learns a synthesis dictionary and an analysis dictionary. Guo et al. ¹³ explored a discriminative ADL by integrating structure preserving and discriminative properties into the basic ADL model. Yang et al. ¹⁴ proposed a discriminative analysis-synthesis dictionary learning, in which a linear classifier based on the coding coefficient is jointly learned with the dictionary pair. Wang et al. ¹⁵ designed a synthesis linear classifier-based ADL (SLC-ADL) algorithm by introducing a synthesis-linear-classifier-based error term into the basic ADL framework. Similarly, Wang et al. ¹⁶ also incorporated the linear classification error term into ADL. The difference between SLC-ADL ¹⁵ and the approach proposed by Wang et al. ¹⁶ is that SLC-ADL actually uses the classification error term from the analysis viewpoint.

Transform learning (TL) is a new representation learning technique which was presented by Ravishankar et al.^17,18; it utilizes a transform matrix to attain the representation of input data. In fact, TL and ADL have similar formulation. TL is mainly used in signal and image denoising. And there is few work on discriminative transform learning (DTL). Very recently, Maggu et al. ¹⁹ developed a label consistent TL for hyperspectral image classification. Although the method proposed by Maggu et al. ¹⁹ is termed as label consistent TL, they essentially introduced the linear classification error term into the framework of TL, so this method is coined as DTL in this paper. To further enhance the classification capability of TL, we introduce the label consistency term into the framework of TL and present label consistent transform learning (LCTL) for pattern classification. Compared with DTL, our proposed LCTL leverages the label information of both training data and dictionary atoms to form an ideal representation matrix. Through the ideal matrix, samples belonging to the same class are forced to have similar representation vectors while those from different classes to have distinct representation vectors. LCTL is evaluated on widely used databases and the experimental results demonstrate that LCTL is superior to DTL and other SDL approaches in terms of recognition accuracy and training time. The source code of our proposed LCTL can be downloaded from https://github.com/yinhefeng/label-consistent-transform-learning

Related work

Synthesis DL

Let $\mathbf{X}=\left[{\mathit{x}}_1,{\mathit{x}}_2,\dots ,{\mathit{x}}_N\right]\in {ℝ}^{n\times N}$ be the training data matrix from C classes, where n and N denote the dimensionality and total number of training samples, respectively. The objective function of K-SVD ⁴ is formulated as follows

$$\underset{\mathbf{D},\mathbf{Z}}{\text{min}}{\Vert \mathbf{X}-\mathbf{DZ}\Vert }_F^2,\text{s}.\text{t}.{\Vert {\mathit{z}}_i\Vert }_0\le T_0$$

(1)

where $\mathbf{D}=\left[{\mathit{d}}_1,{\mathit{d}}_2,\dots ,{\mathit{d}}_K\right]\in {ℝ}^{n\times K}$ is the dictionary that is to be learned, $\mathbf{Z}=\left[{\mathit{z}}_1,{\mathit{z}}_2,\dots ,{\mathit{z}}_N\right]\in {ℝ}^{K\times N}$ is the coding coefficient matrix, and T₀ is a given sparsity level. Equation (1) can be solved by alternatively updating D and Z. Although K-SVD delivers promising results in image compression and denoising, it is not tailored for classification. To make K-SVD applicable to pattern classification, Zhang and Li ⁵ presented D-KSVD algorithm by introducing the classification error term into the framework of K-SVD

$$\begin{array}{l}\underset{\mathbf{D},\mathbf{W},\mathbf{Z}}{\text{min}}{\Vert \mathbf{X}-\mathbf{DZ}\Vert }_F^2+\beta {\Vert \mathbf{H}-\mathbf{WZ}\Vert }_F^2+\lambda {\Vert \mathbf{W}\Vert }_F^2\\ \text{s}.\text{t}.{\Vert {\mathit{z}}_i\Vert }_0\le T_0\end{array}$$

(2)

where $\mathbf{H}=\left[{\mathit{h}}_1,{\mathit{h}}_2,\dots ,{\mathit{h}}_N\right]\in {ℝ}^{C\times N}$ is the label matrix of training data, ${\mathit{h}}_i={[0,0,\dots ,1,\dots ,0,0]}^T\in {ℝ}^{C\times 1}$ is the label vector of ${\mathit{x}}_i$ , and W is the parameters for a linear classifier. We can see that dictionary and classifier are jointly learned in D-KSVD. Then, Jiang et al. ⁶ developed LC-KSVD by solving the following optimization problem

$$\underset{\mathbf{D},\mathbf{W},\mathbf{A},\mathbf{Z}}{\text{min}}{\Vert \mathbf{X}-\mathbf{DZ}\Vert }_F^2+\alpha {\Vert \mathbf{Q}-\mathbf{AZ}\Vert }_F^2+\beta {\Vert \mathbf{H}-\mathbf{WZ}\Vert }_F^2,\text{s}.\text{t}.{\Vert {\mathit{z}}_i\Vert }_0\le T_0$$

(3)

where $\mathbf{Q}=\left[{\mathit{q}}_1,{\mathit{q}}_2,\dots ,{\mathit{q}}_N\right]\in {ℝ}^{K\times N}$ is an ideal representation matrix and A is a linear transformation matrix.

Transform learning

TL was presented by Ravishankar et al.^17,18 and the objective function of TL is formulated as follows

$$\underset{\mathbf{T},\mathbf{Z}}{\text{min}}{\Vert \mathbf{TX}-\mathbf{Z}\Vert }_F^2+\mu \left({\Vert \mathbf{T}\Vert }_F^2-\text{log}\text{det}\mathbf{T}\right)+\lambda {\Vert \mathbf{Z}\Vert }_1$$

(4)

where $\mathbf{T}=[{\mathit{t}}_1;{\mathit{t}}_2;\dots ;{\mathit{t}}_K]\in {ℝ}^{K\times n}$ is the transform matrix, ${\mathit{t}}_i\in {ℝ}^{1\times n}$ . $-\text{log}\text{det}\mathbf{T}$ imposes a full rank constraint to avoid the trivial solution ( $\mathbf{T}=0,\mathbf{Z}=0$ ), ${\Vert \mathbf{T}\Vert }_F^2$ is used to address the scale ambiguity of the transform matrix. TL is an unsupervised representation learning approach, thus it is unsuitable for classification tasks. Recently, Maggu et al. ¹⁹ developed a supervised version of TL by solving the following problem

$$\underset{\mathbf{T},\mathbf{Z},\mathbf{W}}{\text{min}}{\Vert \mathbf{TX}-\mathbf{Z}\Vert }_F^2+\mu \left({\Vert \mathbf{T}\Vert }_F^2-\text{log}\text{det}\mathbf{T}\right)+\lambda {\Vert \mathbf{Z}\Vert }_1+\beta {\Vert \mathbf{H}-\mathbf{WZ}\Vert }_F^2$$

(5)

where H and W are the label matrix of training data and parameters of linear classifier, respectively.

Label consistent TL

As mentioned earlier, we want to employ the label information of both training data and dictionary atoms to boost the discriminative capability of TL, and the objective function of our proposed LCTL is formulated as

$$\underset{\mathbf{T},\mathbf{Z},\mathbf{A}}{\text{min}}{\Vert \mathbf{TX}-\mathbf{Z}\Vert }_F^2+\mu \left({\Vert \mathbf{T}\Vert }_F^2-\text{log}\text{det}\mathbf{T}\right)+\lambda {\Vert \mathbf{Z}\Vert }_1+\alpha {\Vert \mathbf{Q}-\mathbf{AZ}\Vert }_F^2$$

(6)

where $\mathbf{Q}=[{\mathit{q}}_1,{\mathit{q}}_2,\dots ,{\mathit{q}}_N]\in {ℝ}^{K\times N}$ is an ideal representation matrix formed by the label information of training data and dictionary atoms, ${\mathit{q}}_i={\left[0,0,\dots ,1,1,\dots ,0,0\right]}^T\in {ℝ}^{K\times 1}$ . The entries in ${\mathit{q}}_i$ are 1 when the training samples and the dictionary atoms have the same class label. For instance, suppose $\mathbf{X}=\left[{\mathit{x}}_1,{\mathit{x}}_2,\dots ,{\mathit{x}}_6\right]$ and $\mathbf{T}=\left[{\mathit{t}}_1;{\mathit{t}}_2;\dots ;{\mathit{t}}_6\right]$ , where ${\mathit{x}}_1,{\mathit{x}}_2,{\mathit{t}}_1$ , and ${\mathit{t}}_2$ belong to the first class, ${\mathit{x}}_3,{\mathit{x}}_4,{\mathit{t}}_3$ , and ${\mathit{t}}_4$ belong to the second class, and ${\mathit{x}}_5,{\mathit{x}}_6,{\mathit{t}}_5$ , and ${\mathit{t}}_6$ belong to the third class, then Q can be defined as

$$\mathbf{Q}=\left[\begin{array}{cccccc}1& 1& 0& 0& 0& 0\\ 1& 1& 0& 0& 0& 0\\ 0& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 1& 1\end{array}\right]$$

Equation (6) can be solved by alternatively updating T, Z, and A, and the optimization process is presented as follows:

Update T: When Z and A are fixed, we can obtain the following optimization problem with respect to T

$$\underset{\mathbf{T}}{\text{min}}{\Vert \mathbf{TX}-\mathbf{Z}\Vert }_F^2+\mu \left({\Vert \mathbf{T}\Vert }_F^2-\text{log}\text{det}\mathbf{T}\right)$$

(7)

Equation (7) has closed-form solution. ¹⁸ First, we factorize $\mathbf{X}{\mathbf{X}}^T+\mu \mathbf{I}$ as $\mathbf{L}{\mathbf{L}}^T$ , then let ${\mathbf{L}}^{-1}\mathbf{X}{\mathbf{Z}}^T=\mathbf{U}\Sigma {\mathbf{V}}^T$ be a full singular value decomposition (SVD). Finally, the solution to Equation (7) is given by

$$\mathbf{T}=0.5\mathbf{V}\left(\mathbf{\Sigma }+{\left({\mathbf{\Sigma }}^2+2\mu \mathbf{I}\right)}^{\frac{1}{2}}\right){\mathbf{U}}^T{\mathbf{L}}^{-1}$$

(8)

Update Z: Fix the other variables and update Z by solving the following problem

$$\underset{\mathbf{Z}}{\text{min}}{\Vert \mathbf{TX}-\mathbf{Z}\Vert }_F^2+\lambda {\Vert \mathbf{Z}\Vert }_1+\alpha {\Vert \mathbf{Q}-\mathbf{AZ}\Vert }_F^2$$

(9)

Equation (9) can be rewritten as

$$\underset{\mathbf{Z}}{\text{min}}{\Vert \left(\begin{array}{c}\mathbf{TX}\\ \sqrt{\alpha }\mathbf{Q}\end{array}\right)-\left(\begin{array}{c}\mathbf{I}\\ \sqrt{\alpha }\mathbf{A}\end{array}\right)\mathbf{Z}\Vert }_F^2+\lambda {\Vert \mathbf{Z}\Vert }_1$$

(10)

Let ${\mathbf{X}}_{\mathit{new}}=\left(\begin{array}{c}\mathbf{TX}\\ \sqrt{\alpha }\mathbf{Q}\end{array}\right)$ and ${\mathbf{A}}_{\mathit{new}}=\left(\begin{array}{c}\mathbf{I}\\ \sqrt{\alpha }\mathbf{A}\end{array}\right)$ , equation (10) can be reformulated as

$$\underset{\mathbf{Z}}{\text{min}}{\Vert {\mathbf{X}}_{\mathit{new}}-{\mathbf{A}}_{\mathit{new}}\mathbf{Z}\Vert }_F^2+\lambda {\Vert \mathbf{Z}\Vert }_1$$

(11)

Equation (11) is the ℓ₁ norm constrained sparse coding problem which can be solved by the Homotopy algorithm. ²⁰

Update A: When fixing the other variables, equation (6) is degenerated into the following problem with respect to A

$$\underset{\mathbf{A}}{\text{min}}{\Vert \mathbf{Q}-\mathbf{AZ}\Vert }_F^2+{\eta }_1{\Vert \mathbf{A}\Vert }_F^2$$

(12)

Equation (12) has the following closed-form solution

$$\mathbf{A}=\mathbf{Q}{\mathbf{Z}}^T{\left(\mathbf{Z}{\mathbf{Z}}^T+{\eta }_1\mathbf{I}\right)}^{-1}$$

(13)

When the training phase is completed, we can obtain the transform matrix T, and the representation matrix of training data can be computed by ${\mathbf{Z}}_{tr}=\mathbf{TX}$ . We employ a simple yet effective linear classifier to classify the test samples. A linear classifier W can be learned based on the label matrix H of training data and the representation matrix ${\mathbf{Z}}_{tr}$ , and the following problem is utilized to learn W

$${\mathbf{W}}^{*}=\text{arg}\underset{\mathbf{W}}{\text{min}}{\Vert \mathbf{H}-\mathbf{W}{\mathbf{Z}}_{tr}\Vert }_F^2+{\eta }_2{\Vert \mathbf{W}\Vert }_F^2$$

(14)

Equation (14) has the following closed-form solution

$${\mathbf{W}}^{*}=\mathbf{H}{\mathbf{Z}}_{tr}^T{\left({\mathbf{Z}}_{tr}{\mathbf{Z}}_{tr}^T+{\eta }_2\mathbf{I}\right)}^{-1}$$

(15)

For a test sample x , first we can compute its coding vector by $\mathit{z}=\mathbf{T}\mathit{x}$ , then the identity of x is given by

$$\text{label}\left(\mathit{x}\right)=\text{arg}\underset{i}{\text{max}}{\mathbf{W}}^{*}\mathit{z}$$

(16)

Experimental results and analysis

In this section, we evaluate the classification performance of our proposed LCTL on four benchmark datasets: the Yale database, the Extended Yale B database, the AR database, and the Scene 15 dataset. To illustrate the superiority of LCTL, we compare LCTL with the following approaches: SRC, ²¹ LLC, ²² K-SVD, ⁴ D-KSVD, ⁵ LC-KSVD, ⁶ and DTL. ¹⁹ Apart from the recognition accuracy, we also present the training time (in seconds) of all the competing methods. All experiments are run with MATLAB R2019a under Windows 10 on a PC equipped with Intel i9-8950HK 2.90 GHz CPU and 16 GB RAM.

Experiments on the Yale database

The Yale database consists of 165 images for 15 subjects, each individual has 11 images. These images have illumination and expression variations. Figure 1 shows some example images from this database. All the images are resized to 24 × 24, resulting in a 576-dimensional vector. Six images per subject are randomly selected for training and the remaining for testing. The learned dictionary contains 60 atoms, i.e. each class has four atoms. Experimental results are summarized in Table 1. We can see that LCTL has the highest recognition accuracy and the least training time. Specifically, the accuracy gain of LCTL over DTL is 2.6%.

Figure 1.

Example images from the Yale database.

Table 1.

Recognition accuracy and training time on the Yale database.

Methods	Accuracy (%)	Training time (s)
SRC	88.0	No need
LLC	93.3	No need
K-SVD	96.0	0.27
D-KSVD	90.7	0.80
LC-KSVD	94.7	0.80
DTL	94.7	0.20
LCTL	97.3	0.16

Note: Bold values signify the best recognition accuracy and the least training time.DTL: discriminative transform learning; LCTL: label consistent transform learning.

Experiments on the Extended Yale B database

The Extended Yale B face database contains 2414 images of 38 individuals. Each individual has 59–64 images taken under different illumination conditions; example images from this dataset are shown in Figure 2. In our experiments, each 192 × 168 image is projected onto a 504-dimensional space via random projection. We randomly select half of the images per category as training and the remaining for testing. The dictionary consists of 570 items, which corresponds to an average of 15 atoms per person. Experimental results are listed in Table 2. Although the accuracy gain of LCTL over LC-KSVD is not that significant, LCTL is about 31 times faster than LC-KSVD.

Figure 2.

Example images from the Extended Yale B database.

Table 2.

Recognition accuracy and training time on the Extended Yale B database.

Methods	Accuracy (%)	Training time (s)
SRC	80.5	No need
LLC	82.2	No need
K-SVD	93.1	1.79
D-KSVD	94.1	32.43
LC-KSVD	95.0	38.96
DTL	94.3	3.91
LCTL	95.2	1.27

Note: Bold values signify the best recognition accuracy and the least training time.DTL: discriminative transform learning; LCTL: label consistent transform learning.

Experiments on the AR database

The AR database has more than 4000 face images of 126 subjects with variations in facial expression, illumination conditions, and occlusions. Figure 3 shows example images from the database. In our experiments, we use a subset of 2600 images of 50 male and 50 female subjects from the database. Each 165 × 120 face image is projected onto a 540-dimensional vector by random projection. For each person, 20 images are randomly selected for training and the remaining for testing. The learned dictionary has 500 dictionary items, i.e. five atoms per person. Table 3 shows the experimental results on this database. Although the AR database consists of occluded images which pose challenge to face recognition, LCTL achieves the best recognition accuracy and the highest efficiency.

Figure 3.

Example images from the AR database.

Table 3.

Recognition accuracy and training time on the AR database.

Methods	Accuracy (%)	Training time (s)
SRC	66.5	No need
LLC	69.5	No need
K-SVD	86.5	1.97
D-KSVD	88.8	45.64
LC-KSVD	93.7	54.48
DTL	95.7	4.75
LCTL	96.2	1.32

Note: Bold values signify the best recognition accuracy and the least training time.DTL: discriminative transform learning; LCTL: label consistent transform learning.

Experiments on the Scene 15 dataset

Scene 15 dataset contains 15 natural scene categories introduced by Lazebnik et al., ²³ which comprises a wide range of indoor and outdoor scenes, such as bedroom, office, and mountain; example images from this dataset are shown in Figure 4. For fair comparison, we employ the 3000-dimensional SIFT-based features used in LC-KSVD. ⁶ Following the common experimental settings, we randomly select 100 images per category as training data and use the remaining for testing. The learned dictionary has 450 atoms. Experimental results are presented in Table 4. One can see that LCTL outperforms DTL by a large margin, and it makes 7.2% and 4.7% improvement over DTL and LC-KSVD, respectively. The confusion matrix for LCTL is shown in Figure 5. As can be seen from Figure 5, LCTL obtains over 99% recognition accuracy for the categories of suburb, coast, forest, insidecity, opencountry, street, office, and kitchen.

Figure 4.

Example images from the Scene 15 dataset.

Table 4.

Recognition accuracy and training time on the Scene 15 dataset.

Methods	Accuracy (%)	Training time (s)
SRC	91.8	No need
LLC	89.2	No need
K-SVD	91.6	7.74
D-KSVD	89.9	99.20
LC-KSVD	93.8	111.01
DTL	91.3	11.45
LCTL	98.5	8.56

Note: Bold values signify the best recognition accuracy and the least training time.DTL: discriminative transform learning; LCTL: label consistent transform learning.

Figure 5.

Confusion matrix on the Scene 15 dataset.

To examine how the dictionary size influences the performance of DL approaches, here we compare LCTL with DTL, LC-KSVD, D-KSVD, and K-SVD. We evaluate all the competing methods under dictionary sizes of 150, 450, 750, 1050, 1350, and 1500, which correspond to 10, 30, 50, 70, 90, and 100 atoms per category, respectively. Recognition accuracy with different dictionary sizes is plotted in Figure 6. We can observe that LCTL consistently outperforms all other approaches for all dictionary sizes.

Figure 6.

Recognition accuracy on the Scene 15 dataset with varying dictionary size.

Conclusion

In this paper, we present an LCTL algorithm. To enhance the discriminative ability of TL and apply it to pattern classification tasks, a label consistency constraint is incorporated into the framework of TL to form a unified objective function. The variables in our optimization problem are updated alternatively and some of them have closed-form solutions. Experiments are conducted on three benchmark face databases and one scene dataset, and the results validate the effectiveness of our proposed LCTL. Moreover, LCTL shows high efficiency in terms of training time, which can be used in real-time scenarios.