Image Representation and Retrieval Based on Graph Theory 

Author  TangJin 
Tutor  LuoBin 
School  Anhui University 
Course  Applied Computer Technology 
Keywords  Graph Representation ContentBased Image Retrieval Graph Spectra Graph Matching Graph Seriation 
CLC  TP391.41 
Type  PhD thesis 
Year  2007 
Downloads  617 
Quotes  4 
With the rapid development of the Internet and multimedia technology, the amount of image data produced and accumulated is increased dramatically. A lot of important information may be concealed if there are no efficient method to manage the mass data. How to represent and retrieve images accurately is a. worthwhile problem to research.ContentBased Image Retrieval(CBIR) is introduced in this dissertation firstly. Traditional CBIR systems usually take image colour, texture and shape features into consideration, while ignore the structural information of it. In this dissertation, we propose an graphbased image retrieval framework. We focus on developing graphbased image retrieval methods which serves as an assistance of the CBIR. The contributions of the dissertation are as follows:In order to improve the performance of the graphbased CBIR, some appropriate graph models should be found to represent image. The dissertation introduces Delaunay graph derived from image feature points and testifies the performance of this representation method through image classification experiments. Affineinvariant Fourier transfbrm based weighted graph(AFWG) is proposed to symbolize the simple content of an image. AFWG is builded from the coefficients of affineinvariant Fourier transform and can preserve the structural information of the original image. On the other hand, a skeletonbased graph representation method is also proposed in this thesis. Level sets and divergence theories are served as the foundations of the algorithm. Both of the graphs described above can only process the image containing single object. So a hierarchical graph(HG) is proposed to solve this problem. Combining contour and skeleton features, images can be represented by HGs in different levels. An idea that converts 2D graph to 1D sequence called graph seriation is introduced for graph distance measure purpose. Two novel graph seriation algorithms are presented in the dissertation. One of them is based on the angle between spectral coefficient vectors(ASCV) of graphs. The starting node of seriation processing are selected, the sorted ASCV will determine the rest nodes position. Another seriation algorithm are based on random graph theory. Graph node positions are decided by building a catch digraph. With seriated graphs at hand, dynamic time warping(DTW) distance is using to represent the dissimilarity between graphs. It measures the structural differences of graphs based on the dynamic warping technique. The experiment results demonstrate that this proposed method is eligible for graph distance measure.The highdimensional indexing is also studied based on mixture model and vector approximation. For graph database indexing, a new automatic model selection method is proposed.The method uses improved componentwise EM to estimate the distribution of graph database and employes vector quantization to build approximate vectors. Unfbrtunately, if there are outliers in the database, the efficiency of traditional indexing scheme based on Gaussian mixture model will degrade rapidly. Under the circumstances, tmixture model based indexing algorithm is proposed. The algorithm adopts multidimensional tdistribution to fit the data and applies independent component analysis(ICA) to quantitate the feature vectors. Experiment results show a remarkable perfbrmance improvement in CBIR while the retrieval accuracy is sacrificed little. In addition, a novel method based on attributed relational graph is presented for image retrieval, which employs ASCV to give more precise retrieval results.