Image segmentation refers to a process of dividing the image into disjoint regions that were meaningful. This process is fundamental in computer vision in that many applications, such as image retrieval, visual summary, image based modeling, and others, can benefit from it. This process is also challenging because segmentation is usually subjective and computation is highly costly....[ Read more ]

Image segmentation refers to a process of dividing the image into disjoint regions that were meaningful. This process is fundamental in computer vision in that many applications, such as image retrieval, visual summary, image based modeling, and others, can benefit from it. This process is also challenging because segmentation is usually subjective and computation is highly costly.

Recently graph based image segmentation has attracted growing interest. In this thesis, we investigate different graph structures and priors based on them for image segmentation from three perspectives.

First, we investigate the pairwise graph based prior. We design a joint prior in the joint segmentation for 3D clustering and 2D image segmentation. This problem makes good use of the current states of the art in both unbiased and biased graph partitioning.

Second, we generalize the pairwise graph to the hypergraph that can model multiplewise relation among the data points. We propose a biased hypergraph partitioning approach, called Linear Neighborhood Propagation, which leads to a linear system with an efficient solution.

Finally, we degrade the cyclic graph to a connected acyclic graph, i.e. tree. We propose a tree partitioning method based on the normalized cut criterion, called Normalized Tree Partitioning. It runs in linear time, and can potentially get superior performance over spectral graph partitioning due to less approximation.