Oregon State University

Can’t find an event? We’re busy migrating to a new event calendar. Try looking new calendar



Event Details

MS Final Examination – Zhicheng Fu

Monday, March 12, 2018 11:00 AM - 1:00 PM

Computing all minimum cuts in a planar graph with an application to image segmentation

Image segmentation is a significant problem in computer science. Many segmentation algorithms consider minimum cuts in a planar graph obtained from the image. These algorithms often consider a set of sources and sinks and compute several minimum cuts to segment the image. The best choices for the sources and sinks are not always clear, so, it makes sense to compute all possible minimum cuts, and select the best of them in a post-processing step. Although such an approach would have been too slow a decade ago, recent nearly linear time algorithms to compute the set of all minimum cuts have made it feasible.

In this project, I implemented an algorithm to compute all minimum cuts in a planar graph. This algorithm first computes a set of tight cuts that are dual to isometric cycles, and then extracts all minimum cuts from them. I used my implementation to segment some images.

Major Advisor: Amir Nayyeri
Committee: Mike Rosulek
Committee: Eugene Zhang

Kelley Engineering Center (campus map)
Calvin Hughes
1 541 737 3168
Calvin.Hughes at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: