Graph cuts with interacting edge weights: examples, approximations, and algorithms

• 成果类型: Article
• 署名作者: Jegelka, Stefanie; Bilmes, Jeff A.
• 署名单位: Massachusetts Institute of Technology (MIT); University of Washington; University of Washington Seattle
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1038-y
• 发表日期: 2017
• 页码: 241-282
• 关键词: minimization; FLOW

摘要

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.