| This dissertation explores original techniques for the construction of hypergraph models for computer vision applications. 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 is in sharp contrast with the more conventional graph representation of visual patterns where only pairwise connectivity between objects is described. The contribution of this thesis is fourfold: (i) For the first time the advantage of the hypergraph neighborhood structure is analyzed. We argue that the summarized local grouping information contained in hypergraphs causes an 'averaging' effect which is beneficial to the clustering problems, just as local image smoothing may be beneficial to the image segmentation task. (ii) We discuss how to build hypergraph incidence structures and how to solve the related unsupervised and semi-supervised problems for three different computer vision scenarios: video object segmentation, unsupervised image categorization and image retrieval. We compare our algorithms with state-of-the-art methods and the effectiveness of the proposed methods is demonstrated by extensive experimentation on various datasets. (iii) For the application of image retrieval, we propose a novel hypergraph model --- probabilistic hypergraph to exploit the structure of the data manifold by considering not only the local grouping information, but also the similarities between vertices in hyperedges. (iv) In all three applications mentioned above, we conduct an in depth comparison between simple graph and hypergraph based algorithms, which is also beneficial to other computer vision applications. |
