Research On L1-norm-based Two-dimensional Maximum Margin Criterion

In the field of image processing and pattern recognition, the amount and dimension of image data are increasing quickly. However, it’s more difficult to process the image data because of the redundant information in the high dimensional image, so the "Curse of dimensionality" is emerged. In addition, in high dimensional data space still exist "concentration of measure", namely the measure of the distance between the data points difference will decrease with increasing the dimension of the data. Therefore, in order to solve the problem of high dimensional data effectively and improve the performance of data classification, it’s essential to reduce the dimensions of high-dimensional data linearly. Traditional methods of linearly decreasing dimensions, such as PCA and LDA, are widely used in many fields, opened a new chapter in the field of pattern recognition. It’s hard to calculate because the dimensions of traditional one-dimensional methods are very high. Moreover, the objective function based on the L2-norm is severely affected by outliers, it is unable to obtain the optimal projection direction. At the same time, because of the small sample size problem, the within-class scatter matrix and between-class scatter matrix of LDA algorithm is singular. Relative the lack of traditional one-dimensional methods, the two-dimensional dimensionality reduction method based on image-as-matrix directly, such as 2DPCA and 2DLDA method is able to solve the "Curse of dimensionality" problem. The linear dimensionality reduction based on L1-norm method, such as PCA-L1, LDA-L1 method, is robust to handle outliers. MMC method can adequately solve the problem of small sample. In this paper, the methods of LDA-L1, LDA and MMC are studied thoroughly, and three improved methods are put forward to the problems:(1) On the basis of the basic principle and the existing problems of the LDA-L1 method, the two-dimensional linear discriminant analysis based on L1-norm method (2DLDA-L1) is put forward.2DLDA-L1 method calculating the within-class scatter matrix and between-class scatter matrix based on image-as-matrix directly, instead of translating the image-as- matrix into image-as-vector and reduced the computer storage and computation complexity; at the same time, this improved method compared to the traditional method which is based on L2-norm can effectively reduce the impact of outliers to the projection. In order to obtain the optimal projection direction, this paper adopts an gradient iteration algorithm, and the experiments on the plurality of image databases verify that this improved method has higher robustness and discriminative performance.(2) Inorder to solve the problems of small sample of the LDA method and the outliers of the MMC method, the Maximum Margin Criterion method based on L1-norm (MMC-L1) is proposed. This method doesn’t need to compute the inverse of within-class scatter matrix when seeking the optimal projection direction. It avoids the problem of small sample in the feature extraction, and makes full use of the L1-norm to solve the problem of the outliers in the image data. This paper proposes an gradient iterative algorithm to extract the optimal projection direction. The effects of noise, occlusion and the recognition rate of the classifiers in the different face image database, verify that MMC-L1 method has strong robustness and discrimination performance.(3) Based on the MMC-L1 method, the two-dimensional Maximum Margin Criterion based on L1-norm (2DMMC-L1) method is put forward.2DMMC-L1 method makes full use of L1-norm to solve the problem of outliers and spatial structure of image data. It reduces the dimensions on the image matrix directly, at the same time, it reduces the loss of spatial image data information, avoid the dispersion of the image to the quantized high-dimensional matrix of complex calculation and result. On the multiple image databases, the experimental results show that the effect of the training set, the number of projection direction and outliers on recognition rate, 2DMMC-L1 method is better than other methods.