Maximum Margin Methods And Their Applications In Image Retrieval

With the advances in techniques for image capture,transmission and storage,the resources of digital images have been greatly enriched.In order for effective utilization of this image resources,we should first be able to find desirable images quickly and accurately from large scale image data set.Image retrieval is a comprehensive problem. To successfully build an image retrieval system,we need to solve some relevant problems in advance,such as measuring image similarities,ranking images according to relevance,image classification and clustering.In recent years,the advances in machine learning area has provided powerful tools for solving different application problems.Among the numerous machine learning algorithms,support vector machine(SVM) has attracted much attention due to having solid theoretical foundation and performing well in practice.This thesis studies several research problems in image retrieval using maximum margin methods,which are based on the SVM model and the principle of maximizing the margin.The thesis first studies when using local feature based image representation,how to match the local features from different images so as to measure the similarity between them,which is also critical for image classification using support vector machines. A novel dual-space pyramid matching algorithm is proposed,which can efficiently compute the implicit matching relation between two feature sets.The proposed matching algorithm first performs multi-resolution space partition in both feature space and image space.Then the feature set of an image is mapped to a multi-resolution histogram that spans the two spaces.Finally,the matching between two feature sets is obtained through weighted histogram intersection.By exploring the distribution characteristics of local features in both feature space and image space,dual-space pyramid matching can get more accurate similarity measure than the single-space matching algorithms. Moreover,the similarity measure obtained by dual-space pyramid matching satisfies the semi-definite condition.Therefore,it can be used as a kernel function for SVM based image classification.The performance of such a classifier has been evaluated on the dataset for the automatic medical image classification task of ImageCLEF 2005.It outperforms the best result announced in the campaign of that year.The thesis then studies the problem of how to effectively rank images according to their relevance to the query in keyword based image retrieval.Unlike traditional works,which usually model the retrieval problem as a binary classification problem and optimize classification performance during learning,this work models it as a rank learning problem and directly optimizes an objective function that is relevant to the ranking performance.A novel multiple-instance rank learning framework based on SVM model and maximum margin principle is proposed in this work.It assumes that the images are represented by sets of image regions.A set of image pairs with preference relations are used to learn the image ranking model.The learned model can be used to compute the ranking scores of new images and the images can then be ranked according to their scores.Within the proposed framework,three different multipleinstance ranking algorithms are proposed according to different assumptions about the relations between the ranking score of an image and those of its constituent regions. The performance of these algorithms are evaluated on real-world images collected from Flickr.The experimental results show that the multiple-instance ranking algorithms can greatly improve the ranking quality of the images.This is the first work that jointly considers the rank learning problem and the multiple-instance learning problem.The thesis also studies the clustering algorithm which exploits the maximum margin principle of support vector machine.The algorithm can be used to cluster images. This maximum margin clustering(MMC) algorithm performs data partition through finding the maximum margin separating hyperplanes in the data.Compared with traditional clustering algorithms,it has good generalization performance and can play an important role in large scale clustering problems.Based on the analysis of the limitations of existing MMC methods,this work proposes a pairwise constrained semisupervised maximum margin clustering algorithm.A set of pairwise loss functions are introduced into the clustering objective functions to make sure that the separating hyperplanes satisfy the given pairwise constraints as much as possible.This is supposed to improve the performance of MMC.Besides studying binary clustering based on the standard SVM model,this work also explores the pairwise constrained MMC algorithm for multiple class clustering based on multi-class SVM model.It is proposed to use constrained concave-convex procedure(CCCP) to efficiently solve the non-convex optimization problems corresponding to MMC.Moreover,for constrained multi-class MMC,an efficient cutting-plane algorithm is presented to solve the sub-problem in each iteration of CCCP so as to ensure its efficiency.Clustering experiments on standard image datasets indicate that the introduction of pairwise constraints can effectively make up the shortcomings of present MMC algorithms and greatly improve the accuracy of the clustering results.