Yüksek boyutlu model gösterilimi ile görüntü kümeleme ve görüntü erişimi
Image clustering and image retrieval with high dimensional model representation
Yazar: AYŞEGÜL KARCILI
Danışman: DOÇ. DR. BURCU TUNGA
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Mühendisliği Ana Bilim Dalı / Matematik Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2018
Konu: Matematik = Mathematics
Dizin: Sayısal görüntü = Digital image ; Sayısal görüntü analizi = Digital image analysis ; Sayısal görüntü işleme = Digital image processing

Özet:
Bu tez çalışmasında, ele alınan bir görüntünün benzerlerinin büyük bir veri tabanından bulunup getirilmesi anlamına gelen içerik tabanlı görüntü erişimi problemi ele alınmış ve bu konuda özgün bir yaklaşım ortaya konmuştur. Önerilen yaklaşım, görüntülerin içeriklerinin Yüksek Boyutlu Model Gösterilimi (YBMG) yöntemiyle analiz edilmesini içermektedir. YBMG yöntemi etkin bir veri bölüntüleme ve boyut indirgeme yöntemidir ve hesaplama karmaşıklığı düşük olduğundan oldukça hızlı çalışmaktadır. Büyük ölçekli veri tabanlarında görüntü erişimi problemine uygulandığında da yüksek bir başarı göstermiştir. Bu çalışmada ayrıca, algoritmayı daha da hızlandırmak amacıyla, veri tabanındaki görüntülerin öncelikle kümelenerek benzer görüntülerin bir arada olduğu küçük veri tabanlarının oluşturulması önerilmektedir. Kümelemenin ardından yapılan görüntü erişimi çalışmasında, ele alınan bir sorgu görüntüsü için en yakın küme tespit edilmekte ve bu görüntünün benzerleri yalnızca bu küme içinde aranmaktadır. YBMG yöntemi, hem ilk aşamada veri tabanı görüntüleri kümelenirken hem de ikinci aşamada görüntü erişimi yapılırken kullanılmaktadır ve bu yöntemle görüntüleri temsil edecek düşük boyutlu veriler hesaplanmaktadır. 

YBMG yöntemi, bir ayrıştırım yöntemidir. Verilen çok değişkenli bir fonksiyonun sabit terim, tek değişkenli terimler, iki değişkenli terimler ve bu şekilde giderek artan sayıda değişkene bağlı terimlerin toplamı olarak yeniden ifade edilmesini sağlamaktadır. Bu yöntemle aynı zamanda çok değişkenli veriler de daha az değişkenli bileşenlere ayrıştırılabilmektedir. Bu tez çalışmasında görüntüler, birer çok değişkenli veri olarak ele alınmış ve her birine YBMG ayrıştırımı uygulanmıştır. Görüntü ayrıştırımıyla elde edilen bileşenler sabit, vektör veya matris yapısındaki verilerdir. 

Çalışmanın ilk basamağı olan kümeleme aşamasında, öncelikle veri tabanındaki her bir görüntüye YBMG ayrıştırımı uygulanarak düşük boyutlu veriler elde edilmiştir. Bu veriler orijinal çok boyutlu görüntünün yerine kullanılarak kümeleme yapılmıştır. Burada, belirlenen düşük boyutlu iki ayrı veri çeşidinin üç farklı kümeleme yöntemi ile kümelenmesi durumları üzerinde çalışılmıştır. Görüntü erişimi basamağına gelindiğinde ise ilk olarak, bir sorgu görüntüsü ele alınmış ve kümeleme basamağında elde edilen kümeleme ölçütleri kullanılarak bu görüntünün en yakın olduğu küme, yani hedef küme saptanmıştır. Ardından seçilen bir YBMG verisi hem sorgu görüntüsü hem de hedef kümede bulunan görüntüler için hesaplanmış ve bu veri kullanılarak görüntü erişimi yapılmıştır. Bu basamakta tercih edilen düşük boyutlu YBMG verileri, kümeleme basamağında tercih edilen verilere göre daha yüksek boyutludur ve görüntüleri daha iyi temsil etmektedir. Bu veriler esas alınarak hedef kümede bulunan görüntülerden, sorgu görüntüsüne karesel Öklit uzaklığı ölçüsüne göre en yakın olan görüntüler sırayla getirilmiştir. Getirilen görüntülerden belirlenen ilk bir kaç tanesinin, sorgu görüntüsü ile aynı objeye ait olup olmadıkları değerlendirilmiştir. Değerlendirme çalışmasında, görüntülerin getirilme sıralarını da dikkate alan azalan kümülatif kazanç yöntemi kullanılmıştır. Elde edilen kazanç, ideal durumda elde edilecek olan kazanca oranlanmıştır. Önerilen iki aşamalı bu sistem, COIL-100 görüntü veri tabanı üzerinde yapılan deneysel çalışmalarla sınanmış ve oldukça yüksek başarı oranları elde edilmiştir. Önerilen yöntemlerden bazıları % 100 başarı oranı vermiştir.

Bu özgün yaklaşım, daha iyi bir değerlendirme yapabilmek amacıyla, kümeleme basamağının bulunmadığı çalışmalarla ve YBMG yöntemi yerine Temel Bileşen Analizi yönteminin kullanıldığı başka çalışmalarla karşılaştırılmıştır. Önerilen yaklaşımın başarı oranları ve özellikle de hesaplama süreleri bakımından daha avantajlı olduğu görülmüştür.

Abstract:
Content based image retrieval means retrieving similars of a considered image from a large image database by means of mathematical methods and computer systems. This is a significant field of study in image processing because of increasing needs in a wide range of application areas such as commercial advertisements, criminal cases, security systems, artificial intelligence studies, etc. This thesis proposes a novel method in this field which contains analyzing the contents of images by High Dimensional Model Representation (HDMR) method. HDMR is an effective method in data partitioning and dimensionality reduction and it works fast since its computational complexity is considerably low. Therefore it has succeeded in image retrieval problem when it is used to reduce the dimension of images each of which is a high dimensional datum. In addition, to speed up the algorithm even more, the images in database are proposed to be clustered first to obtain small groups in which similar images are together. After clustering step, for a considered query image the closest cluster is determined and the similars of the query image is searched in that cluster. Both in the clustering and the retrieval steps the HDMR method is utilized. 

HDMR expansion for a given multivariate function is a finite sum which consists of constant term, univariate terms, bivatiate terms and so on. Each term is uniquely determined in the given order from the given multivariate function using formulas for HDMR terms. Due to the structure of HDMR, all the terms are orthogonal to each other and the lower variate terms which are calculated earlier carry higher amount of information of the original function. Thus this method is commonly used to approximate the given function by truncating after some terms.

This method for multivariate functions has also been adapted for multivariate data. Multivariate data is similarly decomposed and then approximated by its terms using formulas for HDMR data decomposition. In this thesis, an RGB image as a three-way array is considered as a trivariate datum and decomposed using HDMR formulas to reduce dimension, in other words, to obtain lower dimensional terms. These terms represent the original image very accurately owing to HDMR's powerful mathematical structure and are calculated very quickly owing to its low computational complexity. 

When the method is applied on an RGB image, the constant, univariate and bivariate terms are obtained as constant, vectors and matrices respectively. The trivariate term which is a three-way array corresponds to margin of error and calculated by subtracting all the previous terms from the original image. 

In this thesis, a two-step image retrieval system is proposed. In the first step of the proposed methods, f0 or f3 term of HDMR is calculated for each image in the database and used for clustering the images. These terms, which are considerably low dimensional, have been selected to be used because this study proposes the clustering step to speed up the retrieval process by coping with the problem of large scale image database. Clustering is executed using three different clustering methods: equal interval size clustering, k-means clustering and equal number of elements clustering. Clustering studies via two different HDMR terms and using three different clustering methods are performed completely separately. In this regard an analysis-based study is followed. The clustering criteria obtained in these clustering studies are kept to be used in the second step. 

When it comes to the retrieval step, a query image which does not exist in the database is taken for investigation. The closest cluster for that image is determined using the criteria obtained in the clustering step. Then a chosen HDMR data is calculated for both the query image and the images in the closest cluster to be used in the retrieval process. Using these data the closest images to the query image according to squared Euclidean distance measure are retrieved in order. The HDMR data which are used in this step have higher dimensions than the ones which are used in the clustering step and thus represent the original image better. One of the representation terms used is f1 term. The vector obtained by attaching f1, f2 and f3 terms end-to-end is used as another tool. Lastly the univariate HDMR approximation which is the superposition of f0, f1, f2 and f3 is examined. Studies with these representation data are performed separately. 

The retrieved images are evaluated in terms of whether or not they belong to the same object as the query image, taking into account of their order in the list. For this purpose the discounted cumulative gain method is used. This is a method of calculating the gain of each retrieved image by discounting with respect to the order number of that retrieved image in the result list. The gain value is calculated by accumulation throughout the retrieved images. In this study, the obtained gain value is divided by the value which will be obtained in the ideal case to give the evaluation results as success rates. 

The proposed methods in this thesis were tested by experiments conducted on COIL-100 image database. This database includes 100 different objects and consists of 72 poses per object. Images of an object are at 5 degrees of rotation on a table around its own axis. For experiments of this thesis, randomly selected one image for each object was discarded from the database. These discarded 100 images were used as query images while the remaining 7100 images were used as the training set. Experiments were conducted on these separated image sets by implementing the algorithms on MATLAB. In these experiments the proposed methods gave significantly high success rates. In some studies, 100% success rate was obtained. 

The novel approach proposed in this study was also subjected to comparative analysis. Since one of the novel aspects of this approach is clustering, the proposed methods was firstly compared with methods which omit the clustering step and perform image retrieval directly. With this comparison, it was seen that the proposed methods are better than the methods without clustering in terms of computation times and, in some cases, success rates. A second comparison was made in terms of the preferred dimensionality reduction method. PCA (Principal Component Analysis) method is used instead of HDMR method for this comparison. HDMR gave better success rates and computation times with respect to PCA. 

The experiments and comparisons in this thesis have shown that using HDMR method for dimensionality reduction and clustering database images prior to retrieval are notably successful in image retrieval problem.