Cut, Glue, & Cut: A Fast, Approximate Solver for Multicut Partitioning
By Thorsten Beier, Thorben Kröger, Jörg H. Kappes, Ullrich Köthe, Fred A. Hamprecht. 2014
48 citations recorded by the source corpus.
Recently, unsupervised image segmentation has become increasingly popular. Starting from a superpixel segmentation, an edge-weighted region adjacency graph is constructed. Amongst all segmentations of the graph, the one which best conforms to the given image evidence, as measured by the sum of cut edge weights, is chosen. Since this problem is NP-hard, we propose a new approximate solver based on the move-making paradigm: first, the graph is recursively partitioned into small regions (cut phase). Then, for any two adjacent regions, we consider alternative cuts of these two regions defining possible moves (glue & cut phase). For planar problems, the optimal move can be found, whereas for non-planar problems, efficient approximations exist. We evaluate our algorithm on published and new benchmark datasets, which we make available here. The proposed algorithm finds segmentations that, as measured by a loss function, are as close to the ground-truth as the global optimum found by exact solvers. It does so significantly faster then existing approximate methods, which is important for large-scale problems.
Subfields: Mathematical Optimization, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Mathematical Optimization
In Algorithms & Complexity
Citations in the corpus
- Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts (2015, methodology): “2 that feasible solutions of the MP found by GAEC are not improved significantly by either of the local search heuristics KLj or CGC [13].”
- Asymmetric Cuts: Joint Image Labeling and Partitioning (2014, background): “The multicut formulation has recently become popular for unsupervised image segmentation [3,4,6,20,37,1,27,9] where the weights w are either learned in a supervised fashion [3,6,4,20,27], or derived from boundary detectors such as gPb [29] as in [37].”