Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts

By Margret Keuper, Evgeny Levinkov, Nicolas Bonneel, G. Lavoué, Thomas Brox, Bjoern Andres. 2015

133 citations recorded by the source corpus.

Formulations of the Image Decomposition Problem [18] as a Multicut Problem (MP) w.r.t. a superpixel graph have received considerable attention. In contrast, instances of the MP w.r.t. a pixel grid graph have received little attention, firstly, because the MP is NP-hard and instances w.r.t. a pixel grid graph are hard to solve in practice, and, secondly, due to the lack of long-range terms in the objective function of the MP. We propose a generalization of the MP with long-range terms (LMP). We design and implement two efficient algorithms (primal feasible heuristics) for the MP and LMP which allow us to study instances of both problems w.r.t. the pixel grid graphs of the images in the BSDS-500 benchmark. The decompositions we obtain do not differ significantly from the state of the art, suggesting that the LMP is a competitive formulation of the Image Decomposition Problem. To demonstrate the generality of the LMP, we apply it also to the Mesh Decomposition Problem posed by the Princeton benchmark [16], obtaining state-of-the-art decompositions.

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Graph Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Graph Learning

In Optimization & Training

Citations in the corpus

Axial-DeepLab: Stand-Alone Axial-Attention for Panoptic Segmentation (2020, methodology): “SSAP [27] exploits the pixel-pair aﬃnity pyramid [58] enabled by an eﬃcient graph partition method [42].”
InstanceCut: From Edges to Instances with MultiCut (2016, background): “Although the problem is NP-hard in general, there are efﬁcient approximate solvers for it, see e.g. [5, 27, 28].”
MaX-DeepLab: End-to-End Panoptic Segmentation with Mask Transformers (2020, methodology): “Then, instance segments are obtained by grouping ‘thing’ pixels with various methods, such as instance center regression [44, 86, 70, 100, 20], Watershed transform [88, 3, 8], Hough-voting [4, 53, 8], or pixel affinity [45, 66, 81, 30, 8].”
Panoptic-DeepLab: A Simple, Strong, and Fast Baseline for Bottom-Up Panoptic Segmentation (2019, methodology): “Recently, SSAP [22] proposes to group pixels based on a pixel-pair affinity pyramid [51] with an efficient graph partition method [31].”
SSAP: Single-Shot Instance Segmentation With Affinity Pyramid (2019, methodology): “Then, in order to utilize the cues about global context reasoning, this work employs a graph partition method [26] to derive instances from the learned affinities.”
CMT-DeepLab: Clustering Mask Transformers for Panoptic Segmentation (2022, methodology): “Other proxy-based methods typically start with semantic segments [11,13,16] and group ‘thing’ pixels into instance segments with various proxy tasks, such as instance center regression [19,42,56,67,79,83,90], Watershed transform [4, 8, 81], Hough-voting [5, 8, 51], or pixel affinity [8, 29, 43, 61, ”
Joint Graph Decomposition & Node Labeling: Problem, Algorithms, Applications (2016, methodology): “The algorithm KLj of [9] for the minimum cost lifted multicut problem generalizes the Kernighan-Lin-Algorithm [8] for the minimum cost multicut problem.”
Towards Bounding-Box Free Panoptic Segmentation (2020, background): “This cascaded graph partition module solves a multicut optimisation problem [15] and takes between 0.”
Multiple People Tracking by Lifted Multicut and Person Re-identification (2017, methodology): “In this work, we exploit a primal heuristic proposed by [12], where the bi-partitions of a subgraph are updated by a set of sequences of transformations.”
Deep learning in video multi-object tracking: A survey (2019, methodology): “The multicut problem was solved with the heuristic algorithm proposed in [144].”
Joint Graph Decomposition and Node Labeling by Local Search (2016, methodology): “This is precisely the algorithm KLj of [12].”
k-means Mask Transformer (2022, methodology): “…clustering-based methods usually operate on semantic segments [13,15,18] and group ‘thing’ pixels into instance segments with various representations, such as instance center regression [50,89,77,104,22,94,63], Watershed transform [91,5], Hough-voting [6,59,92], or pixel aﬃnity [51,69,85,36,47].”
Motion Trajectory Segmentation via Minimum Cost Multicuts (2015, background): “Concerning related work on minimum cost multicut formulations, most prior applications in computer vision were focussing on image segmentation on superpixel graphs [1, 2, 20] and pixel graphs [22].”