0-1 graph partitioning and image segmentation

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.

Department dc:contributor.department

Massachusetts Institute of Technology. Computation for Design and Optimization Program.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Goh, Chun Fan

Advisor dc:contributor.advisor

• Gilbert Strang.

• Computation for Design and Optimization Program.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/45277

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/45277