Document Type


Date of Degree

Spring 2011

Degree Name

MS (Master of Science)

Degree In

Electrical and Computer Engineering

First Advisor

Xiaodong Wu

First Committee Member

Milan Sonka

Second Committee Member

Mona Garvin


Image segmentation is an important task in computer vision and understanding. Graph Cuts have been shown to be useful in image segmentation problems. Using a criterion for segmentation optimality, they can obtain segmentation without relying heavily on a priori information regarding the specific type of object. Discussed here are a few approximations to the Normalized Cut criterion, the solving of which has been shown to be an NP-hard problem. Two Normalized Cut algorithms have been previously proposed, and a third is proposed here which accomplishes approximation by a similar method as one of the previous algorithms. It is also more efficient than either of the previously proposed Normalized Cut approximations.


Algorithms, Graph cuts, Normalized Cuts


vi, 38 pages


Includes bibliographical references (pages 37-38).


Copyright 2011 William Stonewall Monroe