# Higher-Order Minimum Cost Lifted Multicuts for Motion Segmentation

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2017.

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

- [Deformable Sprites for Unsupervised Video Decomposition](https://mlsanity.com/paper/2204.07151/) (2022)
- [Guess What Moves: Unsupervised Video and Image Segmentation by Anticipating Motion](https://mlsanity.com/paper/2205.07844/) (2022)
- [Learning segmentation from point trajectories](https://mlsanity.com/paper/2501.12392/) (2025)
- [The Right Spin: Learning Object Motion from Rotation-Compensated Flow Fields](https://mlsanity.com/paper/2203.00115/) (2022)
- [LOCATE: Self-supervised Object Discovery via Flow-guided Graph-cut and Bootstrapped Self-training](https://mlsanity.com/paper/2308.11239/) (2023)
- [Online Unsupervised Video Object Segmentation via Contrastive Motion Clustering](https://mlsanity.com/paper/2306.12048/) (2023)
- [Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks](https://mlsanity.com/paper/2204.01366/) (2022)
- [Uncertainty in Minimum Cost Multicuts for Image and Motion Segmentation](https://mlsanity.com/paper/2105.07469/) (2021)
- [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)
- [CAMotion: A High-Quality Benchmark for Camouflaged Moving Object Detection in the Wild](https://mlsanity.com/paper/2604.08287/) (2026)
- [ClimateVID -- Social Media Videos Analysis and Challenges Involved](https://mlsanity.com/paper/2604.27968/) (2026)
- [The canonical facets of multi-separator polytopes](https://mlsanity.com/paper/2608.16861/) (2026)

## Abstract (arXiv)

Most state-of-the-art motion segmentation algorithms draw their potential from modeling motion differences of local entities such as point trajectories in terms of pairwise potentials in graphical models. Inference in instances of minimum cost multicut problems defined on such graphs al- lows to optimize the number of the resulting segments along with the segment assignment. However, pairwise potentials limit the discriminative power of the employed motion models to translational differences. More complex models such as Euclidean or affine transformations call for higher-order potentials and a tractable inference in the resulting higher-order graphical models. In this paper, we (1) introduce a generalization of the minimum cost lifted multicut problem to hypergraphs, and (2) propose a simple primal feasible heuristic that allows for a reasonably efficient inference in instances of higher-order lifted multicut problem instances defined on point trajectory hypergraphs for motion segmentation. The resulting motion segmentations improve over the state-of-the-art on the FBMS-59 dataset.