Hypergraph Model For Image Analysis

In many image analysis methods, due to the intuitive and vivid of graph model, so they can solve the problem of tacit knowledge representation, which has become an important method in the field of image analysis. A hypergraph is a generalization of a pairwise simple graph, where an edge can connect any number of vertices. The expressive power of the hypergraph models places a special emphasis on the relationship among three or more objects, which has made hypergraphs better models of choice in a lot of problems.This dissertation focuses on the hypergraph model and its application in image analysis and explores original techniques for three aspects of hypergraph, e.g. the construction of hypergraph, the computation of hyperedge weights, and the hypergraph learning methods. Then the thesis instantiate a series of hypergraph-oriented algorithms for various image analysis tasks, e.g., image clustering, image classification, and image segmentation. The contributions are as follows:(1) We propose to build a new hypergraph model with sparse representation (HSR). For each data point, we use sparse representation to get sparse reconstruction coefficients, which are used to seek its neighbors adaptively to form a hyperedge, so the data points in a hyperedge have strong dependency. Instead of the negative coefficients, we take the similarity between the relationships from column space of sparse coefficients represent hyperedge weight. Then, new hypergraph learning algorithms including unsupervised and semi-supervised learning are derived upon the HSR model.(2) We propose a new image segmentation method, in which deep superpixels are explored by different over-segmentations and hypergraph clustering is conducted for final segmentation. First, several over-segmentation methods are first conducted to partition the image into many small regions called superpixels. Then, an iterative algorithm is developed to obtain the deep superpixels, which are shared by all the over-segmentations. Taking the deep superpixels as the vertices, a hypergraph model is constructed to effectively integrate the all the original superpixels, and hypergraph sepectral clustering is performed to obtain the final image segmentation result.