Image clustering and image retrieval with high dimensional model representation

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.