Seyreklik ve sözlük öğrenme yaklaşımlarının sınıflandırma ve yüz tanımaya uygulanması
Classification and face recognition application of sparsity and dictionary learning based methods
Yazar: BERNA AZİZOĞLU
Danışman: DOÇ. DR. ENDER METE EKŞİOĞLU
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı / Telekomünikasyon Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2017
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering

Özet:
Bilim ve mühendislik dünyası sinyallerle doludur. Kalp ve beyin tarafından üretilen medikal sinyaller, sismik titreşimler, ses, görüntü ve video sinyalleri gibi gerçek dünyada kaydedilen sinyallerin çeşitliliği, bu sinyallerin analizi, sıkıştırılması, iletimi ve depolanması gibi konularda da artan bir ilgiyi beraberinde getirmektedir. Bu işlemlerin etkin bir şekilde yapılabilmesi için sinyallerin gösterilimi konusu büyük önem taşımaktadır. Sinyallerin gösteriliminde en temel yöntem sinyallerin örnek değerlerinin kullanılmasıdır. Son yıllarda ise sinyallerin kendi boyutundan daha az sayıda katsayı kullanılarak gösterilimini temel alan seyrek gösterilim konusunda artan bir ilgi mevcuttur.
Seyrek işaret işlemenin temeli son yıllarda ortaya çıkan ve yüksek boyutlu verilerin analiz edilmesinde ve sinyallerin geri çatılmasında kullanılan sıkıştırılmış algılama tekniğine dayanmaktadır. Sıkıştırılmış örnekleme olarak da isimlendirilen bu teknik, Shannon-Nyquist örnekleme teoremine kıyasla daha az değerle sinyallerin geri çatılabilmesini konu aldığı için literatürde yeni bir örnekleme teoremi olarak da gösterilmektedir.  
Sinyallerin seyrek gösterilimi bilgisayar görmesi, örüntü tanıma ve görüntü işlemenin birçok disiplininde geniş bir uygulama alanına sahip olmuştur. Gürültü giderme, öznitelik çıkarma, çözünürlük yükseltme gibi uygulamaların yanı sıra sınıflandırma problemlerinin çözümünde de oldukça başarılı uygulamalara sahiptir. Bu tez çalışmasında da seyreklik temelli yaklaşımların sınıflandırma uygulamasında kullanımı ele alınmıştır. 
Seyrek gösterilim problemi bir sinyalin aşırı-tam bir sözlüğün az sayıda bileşeninin doğrusal kombinasyonu şeklinde ifade edilmesini konu alır. Sözlük, atom olarak isimlendirilen ve sinyalin boyutundan daha fazla sayıda olan temel bileşenlerin bir kümesidir. Sözlük matrisinin tasarımı birtakım matematiksel fonksiyonlar kullanılarak yapılabileceği gibi öğrenme yöntemi ile de yapılabilir. Literatürde sözlük öğrenme problemini çözümleyen çeşitli algoritmalar bulunmaktadır. Bu yaklaşımların bir kısmı görüntünün düzgün şekilde geri çatılması için hata terimini minimize edecek şekilde sözlük tasarımını ele alır. Sınıflandırma uygulamalarında bu şekilde tasarlanan sözlükler de kullanılabilmektedir. Fakat son zamanlarda yapılan çalışmalarda eğitim örneklerinin ait olduğu sınıf bilgilerini de içeren sözlüklerin sınıflandırma performanslarının daha yüksek olduğu görülmektedir. 
Bu yüksek lisans tez çalışmasının amacı sıkıştırılmış algılamanın temelini oluşturan seyreklik yaklaşımının ve bu yaklaşımı temel alan sözlük öğrenme algoritmalarının sınıflandırma uygulamalarının incelenmesidir. Bu kapsamda öncelikle sınıflandırma problemi ile ilgili genel bir bilgi verilmiş, seyreklik kavramı teorik açıdan ele alınıp tanıtılmış, seyrek gösterilim problemleri ve bu problemlerin çözümü için kullanılan algoritmalar açıklanmıştır. Ayrıca sözlük öğrenme yaklaşımı hakkında detaylı bilgi verilmiş ve sözlük öğrenmede kullanılan güncel yöntemler anlatılmıştır. Seyreklik tabanlı sınıflandırma algoritması ve sınıflandırma probleminin çözümü için sunulan güncel ve çok sayıda atıf alan sözlük öğrenme temelli yöntemler açıklanmıştır. Ele alınan bu yöntemlerin yüz tanıma uygulamasındaki benzetimleri Genişletilmiş YaleB veri tabanı kullanılarak MATLAB ortamında gerçeklenmiştir. Benzetimlerden elde edilen sonuçlar literatürde sınıflandırma sistemlerinde oldukça bilinen bir yöntem olan En Yakın Komşuluk sınıflandırıcısı ile karşılaştırılmıştır. 
Yapılan çalışmalar ve benzetimler sonucunda seyreklik temelli yaklaşımların sınıflandırma uygulamalarında gayet başarılı sonuçlar verdiği görülmüştür. Gerçekleştirilen yüz tanıma uygulamasında sözlük öğrenme temelli yaklaşımlar özellikle az sayıda eğitim örneğinin kullanıldığı durumlarda da gösterdiği yüksek sınıflandırma başarımı ve düşük sınıflandırma süreleri ile dikkat çekmektedir. Buradan hareketle seyreklik ve sözlük öğrenme temelli yöntemlerin yüz tanıma konusunda gürbüz ve rekabetçi yöntemler oldukları söylenebilir.

Abstract:
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.