Image Segmentation And Classification Based On Graph Theory

Pattern recognition is the basic skill of mankind. Due to the invention of computers and the development of artificial intelligence, one expects that some skills of human brain can be replaced and extended by computer. Since the 60s of the last century, pattern recognition has developed rapidly. As an interdisciplinary subject, pattern recognition relates to mathematics, computer science, machine learning, psychology, biology, cybernetics and image processing etc.; at the same time, pattern recognition has found its applications in many disciplines, including DNA sequence analysis, chemical smell recognition, image understanding, face recognition, expression recognition, gesture recognition, phonetic recognition, image retrieval and data mining etc.Clustering and classification are the two fundamental problems in pattern recognition. This dissertation mainly investigates clustering and classification algorithms based on graph theory, as well as their applications in image segmentation and image recognition. The main contributions of this dissertation are summarized as follows.Firstly, we investigate the spectral clustering algorithm with eigenvector selection, where the integrated squared error divergence is generalized and the spectral clustering algorithm with eigenvector selection using the generalized integrated squared error divergence is proposed. Due to the noise existing in the real-world data, eigenvector selection in spectral clustering is necessary, while the modal (unimodal or multimodal) of each eigenvector reflects whether the information for clustering is contained to a certain degree. We model each eigenvector using Gaussian Mixture Model, EM algorithm is used to estimate the parameters, and then the generalized integrated square error divergence is calculated and serves as the criteria to eigenvector selection. The experimental results on varied natural image segmentation show that the proposed method is simple and effective.Secondly, in the framework of split-merge strategy, an image segmentation algorithm, which estimates the probability density of each node on the region adjacency graph of the image, is constructed. First the original image is over-segmented using Mean shift algorithm; The segments are used to generate a graph, in which the segments are served as graph nodes and the texture similarity between regions is used as the weights between nodes; Then, the probability density of each nodes are computed using Kernel Density Estimation methods; finally, these regions are merged in the probability density space to complete the segmentation. Even to complex image, such as SAR image that is contaminated by speckle noise, the proposed method can produce satisfactory result, and also is suitable for real-time processing.Thirdly, we study the dot product representation of graph model (DPRG) and its application in clustering, the extended dot product representation of graph model (EDPRG) is proposed, and also a corresponding image segmentation algorithm is developed. As a non-linear dimensionality reduction method, DPRG maps the data as the vectors in dot product space, and the angles represent the similarities between vectors. To increase the between-class angles (distance) and improve clustering results, negative similarity is introduced, and then EDPRG model is proposed. The rationality of this generalization is proved in theory; the experimental results on synthetic data validate the effectiveness of EDPRG Combining with the above split-merge image segmentation method, a new image segmentation algorithm is proposed, where the EDPRG is adopted in the region merging process. The validity of the algorithms proposed is verified through the experiments on real SAR image segmentation. Fourthly, we investigate a linear dimensionality reduction method-neighbourhood preserving embedding (NPE) and its extension on two dimensional image. When dealing with image data, NPE needs the preprocess of vectorization of images, we propose the two-dimensional neighbourhood preserving embedding (2DNPE) algorithm, which performs on image matrices directly, the problem of singularity of matrix confronted in 1D case is avoided and the computing speed is increased.2DNPE actually reduces the dimension of the row of matrices. To reduce the dimension of the row and column of matrices simultaneously, we also propose a bilateral two-dimensional neighbourhood preserving embedding (B2DNPE) algorithm. Besides the same advantages as the 2DNPE, much less coefficients are needed by representation and recognition in B2DNPE. We also reveal the relationship between the extension algorithms of LPP and NPE on image matrices:they also provide two different ways to linearly approximate the eigenfunctions of the Laplace Beltrami operator on manifold. Through the experiments of face recognition and handwritten digits recognition, the effectiveness and advantages of the proposed algorithms are validated.