Image Representation And Retrieval Based On Graph Theory

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.Content-Based 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 graph-based image retrieval framework. We focus on developing graph-based 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 graph-based 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. Affine-invariant Fourier transfbrm based weighted graph(AFWG) is proposed to symbolize the simple content of an image. AFWG is builded from the coefficients of affine-invariant Fourier transform and can preserve the structural information of the original image. On the other hand, a skeleton-based 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 high-dimensional 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 component-wise 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, t-mixture model based indexing algorithm is proposed. The algorithm adopts multi-dimensional t-distribution 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.