Graph Cuts with Interacting Edge Costs - Examples, Approximations, and Algorithms
This work addresses a theoretical extension of graph cuts for researchers in optimization and applied fields, but it appears incremental as it builds on existing submodular and graph cut frameworks.
The paper tackles the problem of extending classical graph cuts by using a submodular cost function over edges, connecting applications in signal processing, machine learning, and computer vision. It provides complexity analysis, algorithms, and empirical comparisons for this cooperative graph cut formulation.
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.