Header logo is

Submodularity beyond submodular energies: coupling edges in graph cuts


Conference Paper


We propose a new family of non-submodular global energy functions that still use submodularity internally to couple edges in a graph cut. We show it is possible to develop an efficient approximation algorithm that, thanks to the internal submodularity, can use standard graph cuts as a subroutine. We demonstrate the advantages of edge coupling in a natural setting, namely image segmentation. In particular, for finestructured objects and objects with shading variation, our structured edge coupling leads to significant improvements over standard approaches.

Author(s): Jegelka, S. and Bilmes, J.
Pages: 1897-1904
Year: 2011
Month: June
Day: 0
Publisher: IEEE

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

DOI: 10.1109/CVPR.2011.5995589
Event Name: IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2011)
Event Place: Colorado Springs, CO, USA

Address: Piscataway, NJ, USA
Digital: 0
ISBN: 978-1-4577-0394-2

Links: PDF


  title = {Submodularity beyond submodular energies: coupling edges in graph cuts},
  author = {Jegelka, S. and Bilmes, J.},
  pages = {1897-1904},
  publisher = {IEEE},
  address = {Piscataway, NJ, USA},
  month = jun,
  year = {2011},
  month_numeric = {6}