Dictionary learning algorithms for analysis and synthesis sparsity and applications in image processing

In the research area of signal processing, reconstruction of any audio,video or image signal from its measured data is a commonly encountered problem. The linear information acquisition process can be shown as Ax=y for the measured data y and the signal x. According to the classical information, the amount of the measured data must be at least as large as the signal length to reconstruct the signal x from its measured data y, by solving the linear system of equations. For this reason, without any additional information, it is impossible to recover the signal from the measured data which is smaller than the signal length N. However, under some certain assumption, it becomes possible to recover a signal when the amount of measurements, m, is smaller than the signal length N. The 'sparsity' assumption of signals makes this case possible. Via the sparse representation, many signals can be defined with a few number of coefficients, which are much less than the length of the signal. The sparse representation of signals is used in signal and image processing area for many problems such as signal reconstruction, compression, image decomposition, denoising, feature extraction and classification. There are two basic models for sparse representation of signals which are named "synthesis" and "analysis" sparsity models. In synthesis sparsity model, a signal is defined as the outcome of the multiplication of a dictionary and a sparse coefficient vector. This used dictionary is an overcomplete dictionary and the signal is represented as a linear combination of few columns from this dictionary which correspond to the nonzero elements of the sparse coefficients vector. Here the number of used atoms is less than the length of the signal. In the analysis sparsity model the sparse representation of a signal is obtained by multiplication of the signal and an operator. In recent years sparsifying transform model which is more general form of the analysis model has been considered as a quite efficient approach. In this transform model, the operators which are similar to the analysis operators are learned with less computational complexity. In this master thesis, the models which are used in sparse representation of signals are studied. Moreover the dictionary learning, operator learning and sparsifying transform learning problems which are the essential problems of the mentioned models are handled. Therefore various algorithms are implemented with MATLAB for solving these problems. Additionally Transform K-SVD, a new transform operator learning algorithm is proposed which brings the transform learning and the K-SVD based analysis dictionary learning approaches together. Finally this novel algorithm is compared with the commonly known analysis model's algorithm in an image denoising experiment. The results are presented with some tables and images within this thesis.