TALK    Cooperative Cuts: Coupling Edges via Submodularity

Date & Time:

Thursday, April 12, 2012; 12:00 PM

Abstract:

Graph cuts that represent pairwise Markov random fields have been a popular tool in computer vision, but they have some well-known shortcomings that arise from their locality and conditional independence assumptions. We therefore extend graph cuts to "cooperative cuts", where "cooperating" graph edges incur a lower combined cost. This cooperation is modeled by submodular functions on edges. The resulting family of global energy functions includes recent models in computer vision and also new critieria which e.g. significantly improve image segmentation results for finely structured objects and for images with variation in contrast. While "minimum cooperative cut" is NP-hard, the underlying indirect submodularity and the graph structure enable efficient approximations.

In the second part of the talk, I will switch topics and briefly address Hilbert space embeddings of distributions. With the kernel trick, such embeddings help generalize clustering objectives to consider higher-order moments of distributions instead of merely point locations.

Speaker:

Dr. Stefanie Jegelka
UC Berkeley

Stefanie Jegelka has just completed her Ph.D. at the Max Planck Institute for Intelligent Systems in Tuebingen (Germany) and at ETH Zurich (Switzerland) and is on the move to UC Berkeley. She has worked on kernel methods, clustering, online and approximation algorithms and on discrete optimization in machine learning, where she is particularly interested in submodular set functions. She has also co-organized two NIPS workshops on Discrete Optimization in Machine Learning.

Research Area:

Computer Vision