Seyrek İşaret İşlemede Sınıflandırma Uygulamaları Ve Çekirdek Tabanlı Yaklaşımlar

Abstract

Seyreklik tabanlı işaret işleme araştırmacılar tarafından oldukça fazla ilgi çeken ve örüntü tanıma, görüntü işleme ve bilgisayar görmesi gibi alanlarda sıklıkla kullanılan bir teoridir. Seyrek işaret işleme, işaret ve görüntü işlemenin birçok disiplininde teorik ve pratik olarak gittikçe artan bir popülariteye sahip olmuştur. Günümüzde de bu alandaki çalışmalar aktif olarak devam etmektedir. Seyrek işaret işlemenin temeli son yıllarda ortaya çıkmış sıkıştırılmış algılama teorisine dayanmaktadır. Shannon örnekleme teoremi ancak bir sinyalin en büyük frekansının iki katı ile örneklenmesi durumunda bu örnekler ile tekrar oluşturulabileceğini konu alır. Fakat bu örnekler birbiri arasında büyük bir ilintiye ve yedekliliğe sahiptir. İşte bu noktada sıkıştırılmış algılama bir sinyalin mümkün olduğu kadar seyrek ve sıkıştırılabilir temsil edilebilmesi durumunda sadece bir kaç değer ile tekrar oluşturulabileceğini konu alır. Sıkıştırılmış algılama bu özelliği nedeniyle literatürde yeni bir örnekleme teoremi olarak gösterilmektedir. Sıkıştırılmış algılama 3 temel adımdan oluşmaktadır. Bunlar seyrek temsil, kodlama ve yeniden oluşturma adımlarıdır. Bu adımlardan ilki olan seyrek temsil, büyük boyuttaki veriyi örneklerken geleneksel örnekleme ve sıkıştırma adımlarını birleştirerek Shannon örnekleme teoreminden daha etkin örneklemeye imkân sağlamaktadır. Seyrek işaret işleme, bu özellikleri ile sınıflandırma uygulamalarında da oldukça fazla dikkat çekmiştir. Bu tezde de seyrek işaret işlemede sınıflandırma uygulamaları ile doğrusal olmayan sınıflandırma için kullanılan çekirdek tabanlı yaklaşımlar ele alınmıştır. Seyrek işaret işlemede gözetimli sınıflandırma, sınıfları bilinen eğitim seti ile test nesnesinin seyrek gösterilmesi ile gerçeklenir. Bu problem eğitim setindeki eleman sayısının test nesnesi boyutundan çok büyük olması nedeniyle eksik belirtilmiş doğrusal bir optimizasyon problemidir. Seyrek vektör 𝑙0 optimizasyon probleminin çözümü ile bulunur. Bu problem eşleştirmeli takip ve dikey eşleştirmeli takip gibi açgözlü algoritmalarla çözülebileceği gibi problem 𝑙1 veya 𝑙2 normlu optimizasyon problemlerine dönüştürülerek de yaklaşık çözüm elde edilebilir. Optimizasyon probleminin çözümünden sonra test nesnesi, elde edilen seyrek vektör ile her bir sınıfa ait eğitim seti kullanılarak temsili olarak tekrar oluşturulur. Her bir sınıfa ait temsili nesne ile orjinal test nesnesi arasındaki fark hesaplanır. Hangi sınıf ile yapılan temsil daha az fark oluşturuyor ise test nesnesinin o sınıfa ait olduğuna karar verilir. Bu yaklaşım tezde doğrusal sınıflandırma yapan seyreklik tabanlı sınıflandırma olarak ele alınmıştır. Doğrusal olmayan sınıflandırma için giriş uzayında doğrusal olarak ayrılmayan iki sınıf, bir doğrusal olmayan fonksiyon ile yüksek boyutlu öznitelik uzayına çevrilir. Fakat bu doğrusal olmayan dönüşüm oldukça büyük bir işlemsel yük ve zaman gerektireceğinden dönüşüm SVM’de kullanılan çekirdek fonksiyonları ile yapılır. Seyreklik tabanlı sınıflandırmada doğrusal olmayan ayrım, bu doğrusal olmayan öznitelik boyutuna haritalanmış test nesnesini yine doğrusal olmayan öznitelik uzayına haritalanmış eğitim seti ile doğrusal olarak temsil edebilmektir. Bu dönüşüm uygun bir çekirdek yaklaşımı ile yapılabilmektedir. Çekirdek fonksiyonları doğrusal, Gauss ve polinom gibi fonksiyonlar olabilmektedir. Her uygulama için en iyi başarımı veren çekirdek fonksiyonu ve parametreleri farklılık göstermektedir. Bu yaklaşım tezde seyreklik tabanlı sınıflandırmada çekirdek yaklaşımı olarak ele alınmıştır. Teze konu yaklaşımda doğrusal sınıflandırma yapan seyreklik tabanlı sınıflandırma ve doğrusal olmayan sınıflandırma yapan seyreklik tabanlı sınıflandırmada çekirdek yaklaşımı yukarıdaki bilgiler ışığında irdelenmiştir. Her iki sınıflandırıcı için yüz tanıma ve rakam tanıma uygulamalarındaki benzetimleri MATLAB ortamında gerçekleştirilmiştir. Benzetimlerde elde edilen sonuçlar sınıflandırma sistemlerinde oldukça bilinen doğrusal destek vektör makineleri ve en yakın komşuluk sınıflandırıcıları ile karşılaştırılmıştır.

Sparse signal processing has attracted much consideration from scientists in field of pattern recognition, image processing and computer vision. Sparse signal processing has most important theoretical and practical applications in many disciplines of signal and image processing. In this field of research still continues especially in the field of signal processing and applied mathematics. The basis of sparse signal processing is related to compressed sensing (CS) theory that has emerged in recent years. As Shannon's sampling theorem, if the sampling frequency is greater than twice the frequency of the signal, then the signal can be reconstructed perfectly. However, these samples have a great relevance and redundancy between each other. At this point, if a signal can be represented as sparse or compressible on appropriate basis elements, the original signal can be reconstructed by exploiting a few measured values. Generally, these measured values are much less than Shannon's sampling theorem. Thanks to this feature, compressed sensing is shown as a new sampling theorem in the literature. Compressed sensing includes the three basic steps, sparse representation, encoding measuring, and reconstructing. The efficient sampling from mass data is a big problem for sampling. Sparse representation step can overcome this difficulty of signal sampling. Also, sparse signal processing integrates the steps of conventional sampling and compression in one step. Sparse signal processing has attracted in much consideration in classification problem. For this thesis, sparsity based linear classification and kernel approaches for the non-linear classification have been conducted to have the knowledge of the sparse classification application. It is very critical that the classification applications need to have high performance and reliable solutions. Classification can be divided 3 different categories, type of learning, assumption on data distribution and number of outputs. In this thesis, supervised, hard and non-parametric classifiers are discussed. It is important that test object should be represented on training set with enough sparsity level for the classification with sparse signal processing. Due to this, training set can be selected pre-determined known mathematical transformation such as curvelet, wavelet. Instead of using pre-determined training set, the data set of the samples can be used directly or can be learned a training set from the data. For the sparsity based classification, firstly sparse vector must be obtained using training samples. According to sparse representation, the test object must be linearly represented by all training samples. Therefore, for obtaining the sparse vector, training samples are required to be quite large than the test object features. Finally, the sparse vector can be obtained from the results of the under-determined linear optimization problem. This linear equation is a non-deterministic polynomial-time hard and no known algorithm for finding the exact sparsest solution. Instead of finding exact solution, approximate solution can be obtained with a few approximation algorithms. Sparse vector can be found the result of 𝑙0 optimization problem. It denotes 𝑙0 norm which counts the number of non-zero entries in a sparse vector. This problem can be solved with greedy approximation algorithms such as Matching Pursuit or Orthogonal Matching Pursuit. In addition, this problem can be solved by transforming to 𝑙1 or 𝑙2 optimization problem. For all methods, sparsity level plays an important role in sparse representation. After solution of optimization problem, test object is reconstructed again representatively using the sparse vector obtained from training set of each classes. The difference between the representative object of each class and orginal test object called residual. The test object is assigned to the class, which has the minimum residual value. This approach is called as sparsity based linear classification method. Classification with linear decision boundries is not feasible for many applications. Thus, we need non-linear classification in applications. Support Vector Machines (SVM) is one of the non-linear classification methods. SVM proposes mapping of input space into high dimensional feature space using kernel approaches and using linear classification in this space. This approach can be applied to sparsity based classification methods. For non-linear classification, two classes which may not separated linearly in the input space, can be mapped into high dimensional feature space using non-linear function. Since non-linear mapping requires considerably high computational load and time, kernel functions of SVM can be used to reduce this computational load. In sparsity based classification, non-linear separation means linear representation of the test object mapped into feature space with training set mapped into feature space. This mapping can be done with appropriate kernel approach. Kernel approaches can be linear, Gaussian and polynomial functions. The best performance can be gain through different kernel functions and parameters in diffirent applications. It this thesis, linear sparsity based classification and kernel approach in non-linear sparsity based classification is studied. Face recognition and digit recognition applications are implemented in MATLAB environment for this two classifiers. The results are compared with SVM and Nearest Neighbour (NN) algorithms. Extended Yale B database is used for face recoginition application. Some of the problems faced in face recognition are light, high dimensional input space, dictionary size and noise. In this work, tests are performed with face images, which has different light, input dimension, dictionary size and noise. To calculate average performance, one-half of images of a person are selected for training and one-half of it for test. The experimental results show that the sparsity level should be 5 for the best performance. Also Gaussian and polynomial kernel functions are compared and it is shown that the polynomial functions that has 0.6 degree gives the best performance. These classifiers are compared with SVM and 3-NN classifiers and it is shown that both in noise free images and images with %10-%70 noise, the sparsity based classifiers gives the best performance. Also both in low and high feature dimension, sparsity based classifiers outperformed other classifers. Especially kernel based approach gives better results than linear sparsity classifier in noise free images and different dictionary size. Handwritten USPS database is used for digit recognition. 350 training images and 350 test images are used for every digit. Tests are performed for noiseless and noisy images. Level of sparsity is determined as 5 and 4.degree polynomial kernel function is used in experiments. These classifiers are compared with linear SVM and 1-NN classifiers. In noiseless and low noisy levels sparsity based classifers give better results. It is shown that in noiseless case, recognition rates of sparse classifiers are not affected by the dimension of the feature and dictionary size. Kernel based approach outperformed other linear sparsity based classifiers in noise free and low noisy levels. When we compare the simulation results obtained in face and digit recognition applications, sparsity based classifiers have achieved quite high and consistent performance for different feture and noise levels for face recognition. However for the digit recognition application, sparsity based classifiers show quite consistent and good success in noiseless case, but they do not give the expected performance in noisy situations. Consequently, SRC and K-SRC algorithms may be used as a good method in face recogintion applications and also for digit recognition applications in noiseless case.