0-1 graph partitioning and image segmentation

Abstract

Graph partitioning is the grouping of all the nodes in a graph into two or more partitions based on certain criteria. Graph cut techniques are used to partition a graph. The Minimum Cut method gives imbalanced partitions. To overcome the imbalanced partitioning, the Normalized Cut method is used. However, it is computationally expensive. The Isoperimetric Partitioning is faster and more stable, and I aim to extend and develop the related ideas. In this thesis, I propose a graph partitioning method - the 0-1 Graph Partitioning. I treat a graph as an electrical circuit: a few nodes are fixed as the voltage inputs (sources), another few nodes are grounded (sinks), and the weight of each edge is seen as the conductance between the two ends (nodes) of the edge. With this setup, other nodes have voltages in between zero and input voltage. The method cuts the graph between the sinks and sources according to the nodes' voltages and in such a way that it minimizes the normalized cut value. The method leads to the Graph Laplacian System -- a linear system. As opposed to the Normalized Cut method, which solves an eigenvalue problem to partition a graph, solving a linear system is much faster and more stable. In addition to the speed, I have proven empirically that the quality of the bipartitions is comparable to the Normalized Cut method. Based on the 0-1 method, I have also developed the Fiedler Quick Start algorithm, which can compute the Fiedler vector faster than solving the generalized eigensystem. I have also applied the graph partitioning algorithm to image segmentation. In comparison to the Normalized Cut method, we show that the method not only gives good segmentation, but it is also much simpler and faster in terms of the construction of a graph from an image, and robust to any noise contained in an image.

(cont.) With the speed and simple graph construction advantage, the method can be applied to large images. The method is object-oriented. It focuses on the objects of images and it is able to segment out objects in the first bi-partition. For k-way image segmentation, the 0-1 method can be applied in both the simultaneous and recursive ways. Apart from the 0-1 image segmentation, I have also developed the Resized Image Segmentation Scheme and the Refinement Scheme (Fast and Thorough), which can speed up the image segmentation process and improve the segmentation. Both schemes can be used by any graph based image segmentation methods.