Image Representation And Matching Based On Graph Theory

Image representation and matching are not only the basic techniques in image processing, analysis and understanding but also important for the further image processing and recognition. Recently, graph theory based image analysis and recognition methods have attracted more and more interests. It is an important research branch in the area of image processing. This thesis focuses on the image representation and matching methods based on the current results. Specifically, it includes shape feature extraction, graph based image representation and recognition and graph matching based image matching techniques.The main contributions and novelties in this thesis are follows:As for the sensitiveness to the non-rigid transformations in the traditional object shape feature extraction methods, this thesis proposes a new skeleton tree based shape feature extraction method and then achieves shape matching and similarity measuring for the shape objects. The method further considers the shape contour on the basic of the skeleton, and explores the topological and geometric information of the shape simultaneously. It is robust to some non-rigid transformations with low computation complexity. Additionally, this thesis improves the optima subsection bijection (OSB) method and presents a novel formation. Our novel OSB can handle with the sequences matching with different start points. Moreover, it can satisfy the symmetric condition of the usual distance function. We adapt it to skeleton graph matching and obtain better performance.A new shape feature extraction method, called as skeleton context, is proposed in this thesis. It combines shape context and skeleton graph of the shape at the same time. Moreover, it extends the description ability for shape context in the non-rigid shape recognition. Based on this skeleton context, the NOSB proposed to achieve skeleton graph matching and similarity measuring in this thesis. Retrieve experiments on the object shape databases demonstrate that this skeleton context can return higher recognition rate and obtain better performance than shape context, especially for the non-rigid object shape. A new graph embedding and similarity measurement method is proposed in this thesis based on complex network theory. This method firstly constructs a small world network to represent the graph structure, and then extracts features for the graph structure by adapting the static and dynamic evolution characteristic for the complex network. It further provides a new basic theory for the area of application of complex network in image processing and pattern recognition. Experiments on both synthetic and real world data show that, the method can not only achieve object classification and clustering but also explore the views of the object in different poses.For the image feature point matching problem, a new graph matching based image matching technique is proposed in this thesis. The method commences with the definition of the path similarity measurement. Then, it gives a new way to compute the affinity of the matching relations based on the shortest path similarity measurement. At last, it completes matching by using the cluster detection technique. As a popular research area in data mining and pattern recognition, cluster detection has been adapted to graph matching method originally in this thesis. The proposed method can not only avoid the high computation complexity but also perform more robustness than the traditional optimization based methods. Promising experimental results on both synthetic and real world data demonstrate that this method can return better performance when lager distortion exists.A new graph matching method based on random dot product graph and dot product representation of graphs is proposed in this thesis. Random dot product graph is one of the important branches in random graph theory area. As an important model in random graph theory system, random dot product graph has been successfully used in image processing and pattern recognition area. This thesis further develops this model and proposes a new graph matching algorithm. Comparison experiment results on both synthetic and real-world image matching demonstrate the effectiveness and robustness of the matching algorithm.