Description And Matching Of Image Structure Based On Mixed Graph Structure

In this thesis, we propose a new structure named Mixed Graph Structure (MGS) to describe and represent an image and use this structure to perform image matching. We preprocessed and segmented an image into a set of regions, and establish its MGS according to both the attributes and spatial relations of regions within an image. Each region in an image is denoted by one and only one vertex of MGS. This image representation does not contain redundant vertexes. Unlike a graph, a MGS contains both directed and undirected edges, which represent "inclusion" and "adjacency" relationship respectively. We show that Mixed Graph Structure has better ability than a tree structure in describing an image.We apply the Mixed Graph Structure in image matching. Image matching is a basic issue in high-level image analysis. An image matching process focuses on evaluating region attributes and relationships contained in the corresponding Mixed Graph Structure. In the image matching process, we build an Association Graph from the MGS, and search all Maximal Cliques in the Association Graph to calculate the matching rate and the similarity of images. Experiments are presented to show the feasibility and high efficiency of our approach.