Research Of Applying Manifold Learning Methods To Web Image Retrieval

Web image retrieval is an active research area. It has shown its potential for real world applications. However, the state-of-the-art performance of web image retrieval is still far from satisfaction. The main difficulty resides in the fact that the Web is a huge distributed database and on-line users would not like to wait overlong for results of retrieval. Therefore, the key of Web image retrieval technology is to design an algorithm with high accuracy and fast response. In order to improve the effectiveness and efficiency of the current Web image retrieval systems, there are two possible ways: choosing (or, designing) an effective dimension reduction technique and using an appropriate relevance feedback algorithm.Recently, Locality Preserving Projections (LPP) has shown its applicability in many areas including information retrieval. LPP is based on Laplacian Eigenmaps and has similar capability for manifold learning. Yet LPP is linear, thus is simple and convenient like other linear methods. In this thesis, we systematically investigate the use of LPP for web image retrieval. Moreover, We have developed several new algorithms to improve the performance of LPP for web image retrieval by incorporating the user provided relevance feedbacks, and combining SVM and LPP.Firstly, we have studied the applicability of the LPP algorithm for image retrieval. LPP is fundamentally based on Laplacian Eigenmaps (LE). It is a linear approximation of LE. LPP has incorporated the advantages of both linear and nonlinear dimension reduction algorithms. Its advantage over LE is that it can produce a transform matrix, and is computationally much more tractable. At the same time, its advantage over linear algorithms, such as Principal Component Analysis (PCA), is that it can have more manifold learning power and is capable of discovering the intrinsic topological structure of the data set with nonlinear property.Secondly, to overcome the problem that the nearest neighbor graph can not always provide an accurate estimation of the local manifold structure, we propose a novel algorithm called Iterative Locality Preserving Projections (ILPP). If we have enough data in training set, the nearest neighbor graph that is defined by LPP can provide the best approximation to geometrical structure of image data. However, training set is produced by random sampling, it is often scarce and not uniform, thus can not assure accurate estimation of the manifold structure. ILPP iteratively updates the nearest neighbor graph, so that it can provide better approximation to the manifold structure. Experimental results show that ILPP can effectively improve performance of LPP.Thirdly, since the pages on the Web are changing frequently, there are always some new images being added into the Web image retrieval system. Most of the existing semi-supervised learners (include learner based on SVM) do not readily generalize to new test data, furthermore are very inefficient when unlabelled data have a great amount. In this thesis, we introduce a new semi-supervised learning algorithm: Semi-supervised LPP algorithm, which efficiently combines the characters of both SVM and LPP. The new algorithm can make efficient use of unlabelled data, and can explicitly consider the manifold structure. Experimental results indicate that Semi-supervised LPP can reach higher retrieval accuracy than semi-supervised learning based on SVM.Finally, based on existing relevance feedback techniques in image retrieval system, we introduce a novel algorithm: FLPP, which incorporates user's relevance feedbacks into LPP. FLPP has the capability of incorporating both short-term and long-term information. By using FLPP in image retrieval, the user's relevance feedbacks are used to update the eigenvectors which span the image representation subspace, so we can obtain a semantic subspace which can better reflect intrinsic property of image data. Experimental results show that FLPP can effectively improve retrieval accuracy, and after long-term learning, we can obtain an approximate optimal subspace.LPP has demonstrated its potential for Web image retrieval. But it has been still a short time since LPP was originally published in 2003, so there are some problems when one tries to apply LPP to Web image retrieval systems. To overcome these problems, this thesis introduces several improved algorithms based on LPP. Plenty of experiments have justified that these improved algorithms could substantially improve the accuracy and efficiency of image retrieval.