# Uncertainty in Minimum Cost Multicuts for Image and Motion Segmentation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 16 May 2021.

## Builds on (most cited first, 12 of 12)

- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Uncertainty Estimates and Multi-Hypotheses Networks for Optical Flow](https://mlsanity.com/paper/1802.07095/) (2018)
- [DeepCut: Joint Subset Partition and Labeling for Multi Person Pose Estimation](https://mlsanity.com/paper/1511.06645/) (2015)
- [Lifted Disjoint Paths with Application in Multiple Object Tracking](https://mlsanity.com/paper/2006.14550/) (2020)
- [InstanceCut: from Edges to Instances with MultiCut](https://mlsanity.com/paper/1611.08272/) (2016)
- [Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts](https://mlsanity.com/paper/1505.06973/) (2015)
- [Higher-Order Minimum Cost Lifted Multicuts for Motion Segmentation](https://mlsanity.com/paper/1704.01811/) (2017)
- [A Message Passing Algorithm for the Minimum Cost Multicut Problem](https://mlsanity.com/paper/1612.05441/) (2016)
- [Higher-order Segmentation via Multicuts](https://mlsanity.com/paper/1305.6387/) (2013)
- [Multicuts and Perturb & MAP for Probabilistic Graph Clustering](https://mlsanity.com/paper/1601.02088/) (2016)
- [Efficient Algorithms for Moral Lineage Tracing](https://mlsanity.com/paper/1702.04111/) (2017)
- [Self-supervised Sparse to Dense Motion Segmentation](https://mlsanity.com/paper/2008.07872/) (2020)

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

- [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)
- [ClimateVID -- Social Media Videos Analysis and Challenges Involved](https://mlsanity.com/paper/2604.27968/) (2026)

## Abstract (arXiv)

The minimum cost lifted multicut approach has proven practically good performance in a wide range of applications such as image decomposition, mesh segmentation, multiple object tracking, and motion segmentation. It addresses such problems in a graph-based model, where real-valued costs are assigned to the edges between entities such that the minimum cut decomposes the graph into an optimal number of segments. Driven by a probabilistic formulation of minimum cost multicuts, we provide a measure for the uncertainties of the decisions made during the optimization. We argue that access to such uncertainties is crucial for many practical applications and conduct an evaluation by means of sparsifications on three different, widely used datasets in the context of image decomposition (BSDS-500) and motion segmentation (DAVIS2016 and FBMS59) in terms of variation of information (VI) and Rand index (RI).