# Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts

arXiv: https://arxiv.org/abs/1505.06973 · HTML: https://mlsanity.com/paper/1505.06973/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2015.

## Built on by (most cited first, 26 of 26)

- [CMT-DeepLab: Clustering Mask Transformers for Panoptic Segmentation](https://mlsanity.com/paper/2206.08948/) (2022)
- [VoxelTrack: Multi-Person 3D Human Pose Estimation and Tracking in the Wild](https://mlsanity.com/paper/2108.02452/) (2021)
- [Amodal Panoptic Segmentation](https://mlsanity.com/paper/2202.11542/) (2022)
- [LMGP: Lifted Multicut Meets Geometry Projections for Multi-Camera Multi-Object Tracking](https://mlsanity.com/paper/2111.11892/) (2021)
- [kMaX-DeepLab: k-means Mask Transformer](https://mlsanity.com/paper/2207.04044/) (2022)
- [In Pursuit of Many: A Review of Modern Multiple Object Tracking Systems](https://mlsanity.com/paper/2209.04796/) (2022)
- [Siamese-DETR for Generic Multi-Object Tracking](https://mlsanity.com/paper/2310.17875/) (2023)
- [Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach](https://mlsanity.com/paper/2106.03188/) (2021)
- [RAMA: A Rapid Multicut Algorithm on GPU](https://mlsanity.com/paper/2109.01838/) (2021)
- [Large-Scale Multi-Hypotheses Cell Tracking Using Ultrametric Contours Maps](https://mlsanity.com/paper/2308.04526/) (2023)
- [Conjugate Product Graphs for Globally Optimal 2D-3D Shape Matching](https://mlsanity.com/paper/2211.11589/) (2022)
- [Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks](https://mlsanity.com/paper/2204.01366/) (2022)
- [ClusterFuG: Clustering Fully connected Graphs by Multicut](https://mlsanity.com/paper/2301.12159/) (2023)
- [Optimizing Edge Detection for Image Segmentation with Multicut Penalties](https://mlsanity.com/paper/2112.05416/) (2021)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)
- [Uncertainty in Minimum Cost Multicuts for Image and Motion Segmentation](https://mlsanity.com/paper/2105.07469/) (2021)
- [A Polyhedral Study of Lifted Multicuts](https://mlsanity.com/paper/2202.08068/) (2022)
- [I Spy With My Little Eye: A Minimum Cost Multicut Investigation of Dataset Frames](https://mlsanity.com/paper/2412.01296/) (2024)
- [A Graph Multi-separator Problem for Image Segmentation](https://mlsanity.com/paper/2307.04592/) (2023)
- [Box Facets and Cut Facets of Lifted Multicut Polytopes](https://mlsanity.com/paper/2402.16814/) (2024)
- [Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network](https://mlsanity.com/paper/2502.14536/) (2025)
- [Correlation Clustering of Bird Sounds](https://mlsanity.com/paper/2306.09906/) (2023)
- [Correlation Clustering of Organoid Images](https://mlsanity.com/paper/2403.13376/) (2024)
- [Graph Neural Networks with Triangle-Based Messages for the Multicut Problem](https://mlsanity.com/paper/2605.13673/) (2026)
- [Contrastive Learning and Correlation Clustering for Sequences of Network Telescope Data](https://mlsanity.com/paper/2606.04733/) (2026)
- [The canonical facets of multi-separator polytopes](https://mlsanity.com/paper/2608.16861/) (2026)

## Abstract (arXiv)

Formulations of the Image Decomposition Problem 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, obtaining state-of-the-art decompositions.