Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2008. / Includes bibliographical references (p. 179-180). / 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. / by Chun Fan Goh. / S.M.
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/45277 |
| Date | January 2008 |
| Creators | Goh, Chun Fan |
| Contributors | Gilbert Strang., Massachusetts Institute of Technology. Computation for Design and Optimization Program., Massachusetts Institute of Technology. Computation for Design and Optimization Program. |
| Publisher | Massachusetts Institute of Technology |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 180 p., application/pdf |
| 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., http://dspace.mit.edu/handle/1721.1/7582 |
Page generated in 0.0119 seconds