# Optimizing Edge Detection for Image Segmentation with Multicut Penalties

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 42 references that are in the map.
- First posted on arXiv 10 Dec 2021.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [A Survey on Deep Learning in Medical Image Analysis](https://mlsanity.com/paper/1702.05747/) (2017)
- [Holistically-Nested Edge Detection](https://mlsanity.com/paper/1504.06375/) (2015)
- [Conditional Random Fields as Recurrent Neural Networks](https://mlsanity.com/paper/1502.03240/) (2015)
- [UberNet: Training a `Universal' Convolutional Neural Network for Low-, Mid-, and High-Level Vision using Diverse Datasets and Limited Memory](https://mlsanity.com/paper/1609.02132/) (2016)
- [Richer Convolutional Features for Edge Detection](https://mlsanity.com/paper/1612.02103/) (2016)
- [Multiscale Combinatorial Grouping for Image Segmentation and Object Proposal Generation](https://mlsanity.com/paper/1503.00848/) (2015)
- [Understanding Deep Learning Techniques for Image Segmentation](https://mlsanity.com/paper/1907.06119/) (2019)
- [Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts](https://mlsanity.com/paper/1505.06973/) (2015)
- [Automatic Breast Ultrasound Image Segmentation: A Survey](https://mlsanity.com/paper/1704.01472/) (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)
- [End-to-end Learning for Graph Decomposition](https://mlsanity.com/paper/1812.09737/) (2018)

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

- [CosPGD: an efficient white-box adversarial attack for pixel-wise prediction tasks](https://mlsanity.com/paper/2302.02213/) (2023)
- [Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks](https://mlsanity.com/paper/2204.01366/) (2022)
- [I Spy With My Little Eye: A Minimum Cost Multicut Investigation of Dataset Frames](https://mlsanity.com/paper/2412.01296/) (2024)
- [ClimateVID -- Social Media Videos Analysis and Challenges Involved](https://mlsanity.com/paper/2604.27968/) (2026)

## Abstract (arXiv)

The Minimum Cost Multicut Problem (MP) is a popular way for obtaining a graph decomposition by optimizing binary edge labels over edge costs. While the formulation of a MP from independently estimated costs per edge is highly flexible and intuitive, solving the MP is NP-hard and time-expensive. As a remedy, recent work proposed to predict edge probabilities with awareness to potential conflicts by incorporating cycle constraints in the prediction process. We argue that such formulation, while providing a first step towards end-to-end learnable edge weights, is suboptimal, since it is built upon a loose relaxation of the MP. We therefore propose an adaptive CRF that allows to progressively consider more violated constraints and, in consequence, to issue solutions with higher validity. Experiments on the BSDS500 benchmark for natural image segmentation as well as on electron microscopic recordings show that our approach yields more precise edge detection and image segmentation.