TY - JOUR
T1 - Graph cuts with interacting edge weights
T2 - examples, approximations, and algorithms
AU - Jegelka, Stefanie
AU - Bilmes, Jeff A.
N1 - Publisher Copyright:
© 2016, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
PY - 2017/3/1
Y1 - 2017/3/1
N2 - 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.
AB - 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.
KW - 68Q25
KW - 68R10
KW - 68T45
UR - http://www.scopus.com/inward/record.url?scp=84976518289&partnerID=8YFLogxK
U2 - 10.1007/s10107-016-1038-y
DO - 10.1007/s10107-016-1038-y
M3 - Article
AN - SCOPUS:84976518289
SN - 0025-5610
VL - 162
SP - 241
EP - 282
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -