# Higher-order Segmentation via Multicuts

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

## Key facts

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

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

- [Learning Topological Interactions for Multi-Class Medical Image Segmentation](https://mlsanity.com/paper/2207.09654/) (2022)
- [RAMA: A Rapid Multicut Algorithm on GPU](https://mlsanity.com/paper/2109.01838/) (2021)
- [Optimizing Edge Detection for Image Segmentation with Multicut Penalties](https://mlsanity.com/paper/2112.05416/) (2021)
- [Uncertainty in Minimum Cost Multicuts for Image and Motion Segmentation](https://mlsanity.com/paper/2105.07469/) (2021)
- [Partial Optimality in Cubic Correlation Clustering](https://mlsanity.com/paper/2302.04694/) (2023)
- [A Graph Multi-separator Problem for Image Segmentation](https://mlsanity.com/paper/2307.04592/) (2023)
- [Partial Optimality in Cubic Correlation Clustering for General Graphs](https://mlsanity.com/paper/2510.20431/) (2025)

## Abstract (arXiv)

Multicuts enable to conveniently represent discrete graphical models for unsupervised and supervised image segmentation, in the case of local energy functions that exhibit symmetries. The basic Potts model and natural extensions thereof to higher-order models provide a prominent class of such objectives, that cover a broad range of segmentation problems relevant to image analysis and computer vision. We exhibit a way to systematically take into account such higher-order terms for computational inference. Furthermore, we present results of a comprehensive and competitive numerical evaluation of a variety of dedicated cutting-plane algorithms. Our approach enables the globally optimal evaluation of a significant subset of these models, without compromising runtime. Polynomially solvable relaxations are studied as well, along with advanced rounding schemes for post-processing.