Graph cuts with interacting edge weights: examples, approximations, and algorithms
We study an extension of the classical graph cut problem, wherein we replace the modular (sum of edge weights) cost function by a submodular set function defined over graph edges. Special cases of this problem have appeared in different applications in signal processing, machine learning, and comput...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2017
|
| Online Access: | http://hdl.handle.net/1721.1/107121 https://orcid.org/0000-0002-6121-9474 |
| _version_ | 1826195511764320256 |
|---|---|
| author | Bilmes, Jeff A. Jegelka, Stefanie Sabrina |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bilmes, Jeff A. Jegelka, Stefanie Sabrina |
| author_sort | Bilmes, Jeff A. |
| collection | MIT |
| description | We study an extension of the classical graph cut problem, wherein we replace the modular (sum of edge weights) cost function by a submodular set function defined over graph edges. Special cases of this problem have appeared in different applications in signal processing, machine learning, and computer vision. In this paper, we connect these applications via the generic formulation of “cooperative graph cuts”, for which we study complexity, algorithms, and connections to polymatroidal network flows. Finally, we compare the proposed algorithms empirically. |
| first_indexed | 2024-09-23T10:13:54Z |
| format | Article |
| id | mit-1721.1/107121 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:13:54Z |
| publishDate | 2017 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1071212022-09-30T19:46:29Z Graph cuts with interacting edge weights: examples, approximations, and algorithms Bilmes, Jeff A. Jegelka, Stefanie Sabrina Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Jegelka, Stefanie Sabrina We study an extension of the classical graph cut problem, wherein we replace the modular (sum of edge weights) cost function by a submodular set function defined over graph edges. Special cases of this problem have appeared in different applications in signal processing, machine learning, and computer vision. In this paper, we connect these applications via the generic formulation of “cooperative graph cuts”, for which we study complexity, algorithms, and connections to polymatroidal network flows. Finally, we compare the proposed algorithms empirically. 2017-02-23T17:28:56Z 2017-06-19T21:40:53Z 2016-07 2014-07 2017-02-23T04:34:42Z Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/107121 Jegelka, Stefanie, and Jeff A. Bilmes. “Graph Cuts with Interacting Edge Weights: Examples, Approximations, and Algorithms.” Mathematical Programming 162, no. 1–2 (July 1, 2016): 241–282. https://orcid.org/0000-0002-6121-9474 en http://dx.doi.org/10.1007/s10107-016-1038-y Mathematical Programming Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Bilmes, Jeff A. Jegelka, Stefanie Sabrina Graph cuts with interacting edge weights: examples, approximations, and algorithms |
| title | Graph cuts with interacting edge weights: examples, approximations, and algorithms |
| title_full | Graph cuts with interacting edge weights: examples, approximations, and algorithms |
| title_fullStr | Graph cuts with interacting edge weights: examples, approximations, and algorithms |
| title_full_unstemmed | Graph cuts with interacting edge weights: examples, approximations, and algorithms |
| title_short | Graph cuts with interacting edge weights: examples, approximations, and algorithms |
| title_sort | graph cuts with interacting edge weights examples approximations and algorithms |
| url | http://hdl.handle.net/1721.1/107121 https://orcid.org/0000-0002-6121-9474 |
| work_keys_str_mv | AT bilmesjeffa graphcutswithinteractingedgeweightsexamplesapproximationsandalgorithms AT jegelkastefaniesabrina graphcutswithinteractingedgeweightsexamplesapproximationsandalgorithms |