Classification and face recognition application of sparsity and dictionary learning based methods

The world of engineering and science is full of signals. The real world activities generate signals such as medical signals generated by the heart and brain, seismic vibrations, audio or speech signals, video and image signals. The increasing diversity of these signals brings about increased necessity for analysis, compression, transmission and storage of the signals. To do these applications in an effective way, signal representation is crucial and it has always been at the heart of most signal processing techniques. The easiest way of representation is to represent a signal using its sample values. In recent years, there has been a growing interest in the field of sparse representation of signals which makes possible to represent a signal by using a few number of coefficients that are much less than the length of the signal. The traditional approach of signal reconstruction from measured data follows the well-known Shannon sampling theorem which states that the sampling rate must be twice the highest frequency of the signal. The principle of sparse signal representation is based on compressed sensing technique which is used in analyzing of high dimensional data and signal reconstruction. This technique has been emerged in recent years and it is also called compressed sampling. It is shown as a new sampling theorem in the literature because it enables reconstructing a signal by using fewer values than Shannon-Nyquist sampling theorem. Compressed sensing technique suggests that if a signal is sparse or compressive, the original signal can be reconstructed by exploiting a few measured values, which are much less than Shannon-Nyquist sampling theorem. Compressed sensing includes three basic stages. These are sparse representation, encoding measuring and reconstructing. Sparse representation of signals has a wide range of applications in many disciplines of computer vision, pattern recognition and image processing. As well as the applications such as denoising, compression, feature extraction, super-resolution and image restoration, sparse representation is also successfully applied to the problems in classification. In this thesis, solving the classification problem through sparsity based approaches is studied. In sparse representation of signals, there are two different models that are named synthesis and analysis sparsity models. In the synthesis model, the signal is represented as the outcome of the multiplication of a dictionary and a sparse coefficient vector, while in the analysis model, the sparse representation of the signal is found by multiplying the signal with an operator. The two approaches become equivalent in the invertible case. Sparse coefficient vector can be found the result of l_0 optimization problem. This problem is a non-deterministic polynomial-time hard (NP-Hard) problem and there is no known algorithm to find the exact solution of this problem. It can only be solved approximately with approximation algorithms. In these algorithms, sparsity level which specifies the number of non-zero elements in the sparse coefficient vector plays an important role in sparse representation. The first group of approximation algorithms contains Greedy algorithms such as Matching Pursuit or Orthogonal Matching Pursuit. The matching pursuit algorithm is the earliest method of using the greedy strategy to approximate the l_0 optimization problem. The orthogonal matching pursuit algorithm is an improvement of the matching pursuit algorithm. In these methods, locally optimal basis vectors are selected iteratively. These methods are very simple and involve the computation of inner products between the signal and the dictionary atoms. The second group includes convex relaxation methods such as Basis Pursuit or least absolute shrinkage and selection operator. The convex relaxation methods replaces the l_0 norm by l_1 norm. Sparse representation problem approximates a signal by a linear combination of a few items in an overcomplete dictionary. A dictionary can be defined as a set of basic signals called atoms and the dictionary size or the number of these atoms is larger than the dimensionality of signals. An effective dictionary can lead to better reconstruction results and the choice of the dictionary that sparsifies the signals is very important for the succes of sparse representation. The best dictionary is the one that leads to the sparsest solution. The dictionary can be constructed both through some mathematical functions and by utilizing learning algorithms. Dictionaries in the first group are characterized by an analytical formulation and fast implementation, while dictionaries in the second group have the capability to adapt to specific signal data. Dictionary learning for sparse signal representation has successful applications in several domains. There are various algorithms in the literature that solve the dictionary learning problem. Dictionary learning aims to learn a set of atoms. Sparsity constraint constitutes the key point of most of the algorithms which solve the dictionary learning problems. Dictionary learning problem is a two-step process. The first step which refered as sparse coding finds the sparse coefficients given the dictionary. Then, in the second step, the dictionary is updated assuming known and fixed coefficients. This step is called dictionary updating. Different applications requires different dictionary learning rules. Some of the learning methods are designed to produce dictionaries appropriate for images reconstruction. Their aim is to minimize the residual error of reconstructing signals while constructing the dictionary. Dictionaries learned in such a way can also be applied to classification problems. However recent research shows that dictionaries containing class information about images in the training set give better classification performances. Image classification requires the dictionary that includes discriminative information in order to the solution has the ability of distinctiveness. The purpose of this master thesis is to study the classification application of sparsity approach which is the basis of compressed sensing and dictionary learning methods. In this context, firstly a general information about the classification problem and face recognition systems are given. The concept of sparsity is discussed theoretically. Sparse representation problems and algorithms used to solve these problems are examined. In addition, detailed information about dictionary learning approach is given and current methods used for dictionary learning are presented. Sparsity based classification algorithm and current dictionary learning based methods proposed to solve classification problems are explained in detail. Face recognition application is implemented in MATLAB environment by using Extended YaleB Database. The results are compared with Nearest Neighbour algorithm which is one of the commonly used method in the literature. In this study, tests are performed with face images which has different light, input dimension and dictionary size. To calculate average performance, one half of images of a person is selected for training set and the other half of it is selected for testing set. Finally, the recognition rates for all cases are presented with tables and graphics. As a result of studies and simulations, it is seen that sparsity based approaches give very successful results in classification applications. In the face recognition application, dictionary learning based approaches draw attention with the low classificaton times and high recognition rates especially when a small number of training samples are used. From this point of view, it can be said that sparsity and dictionary learning based methods are robust and competitive methods for face recognition.