Uncertainty in minimum cost multicuts for image and motion segmentation

Amirhossein Kardoost, Margret Keuper

This paper, presented at UAI 2021, addresses a critical missing piece in graph-based clustering: knowing when the model is guessing. While "Minimum Cost Multicuts" are a gold standard for segmenting images and tracking objects, they usually only provide a single "best" answer. The authors introduce a calibrated uncertainty measure that identifies which parts of a segmentation are reliable and which are likely errors.

TL;DR

The authors propose a novel uncertainty measure for (lifted) multicut problems that assigns a confidence score to each node-to-cluster assignment. By identifying "weak links" in a segmentation, they can improve downstream tasks like densification and generate multiple high-probability alternative solutions.

What Problem Does This Paper Address?

In computer vision, the Minimum Cost Multicut problem (also known as correlation clustering) is a powerful way to partition data. Imagine a graph where nodes are pixels or object trajectories. Edges between them have "costs": a positive cost means the nodes should stay together, while a negative cost means they should be separated. The goal is to find the partition that minimizes the total cost.

The problem is that standard solvers only give you the MAP (Maximum A Posteriori) estimate—the single most likely configuration. In fields like autonomous driving or medical imaging, a single answer isn't enough; we need to know the model's confidence. If a system segments a pedestrian but is highly uncertain about their boundaries, that uncertainty is vital information. Previous attempts to measure this often under-estimated confidence in dense graphs or focused only on edge-level labels rather than the final node clusters.

Methods

The authors derive their measure directly from the probabilistic formulation of the multicut problem.

  1. The Cost of Change: For any given node $v_i$ in a cluster $A$, they calculate $\gamma_B$—the change in the total objective function if that node were moved to a neighboring cluster $B$.
  2. The "Cheapest" Move: They identify the most likely alternative move (the one with the smallest cost increase).
  3. Logistic Calibration: They apply a logistic function to this cost difference to produce a "calibrated" probability.

Essentially, if moving a node to a different cluster barely changes the total cost, the model is uncertain. If moving the node would "break" the optimization significantly, the model is highly confident. This approach is "calibrated" because it normalizes the probability of the current solution against the second-best alternative.

Datasets

The researchers evaluated their method on three widely used computer vision benchmarks:

  • FBMS-59 (Freiburg-Berkeley Motion Segmentation): A dataset for tracking moving objects in video.
  • DAVIS-2016 (Densely Annotated Video Segmentation): A benchmark for high-quality video object segmentation.
  • BSDS-500 (Berkeley Segmentation Dataset): The standard dataset for static image decomposition and boundary detection.

Key Insights and Ideas

  • Sparsification as a Litmus Test: To prove the uncertainty measure works, the authors used "sparsification plots." They gradually removed the most uncertain nodes and re-calculated accuracy. In a good model, the error should drop sharply as uncertain points are removed. Their method significantly outperformed "random" and "likelihood-based" baselines.
  • Uncertainty Lives on the Edge: Qualitatively, the model shows that uncertainty is highest at object boundaries and on thin, articulated parts (like a person's legs or a squirrel's tail). This matches human intuition about where segmentation is hardest.
  • Generating Hypotheses: Because the method identifies nodes that are "easy to flip," it can be used to generate the top $N$ most likely segmentations rather than just one. They showed that the "true" best segmentation is often found within the top 8 proposals.
  • Boosting "Densification": In motion segmentation, we often start with sparse points and use a neural network to fill in the rest of the image. By using their uncertainty measure to weight the training data (focusing the network on "hard" but certain examples), they improved the final segmentation quality.

Key Results

  • Metric Improvement: On the FBMS-59 and DAVIS-2016 datasets, removing the 10% most uncertain trajectories led to a consistent and significant improvement in both Variation of Information (VI) and the Rand Index (RI).
  • Training Gains: Using uncertainty-aware training for a U-Net densification model improved the F-measure on FBMS-59 from 77.01 to 77.40. While the numerical gain seems small, the qualitative results show much better preservation of thin structures like limbs.
  • Robustness: Unlike simpler baselines, the proposed measure doesn't collapse when the graph becomes dense, making it more practical for real-world vision applications.

Limitations and Future Work

The authors acknowledge a few areas for growth:

  • Local vs. Global: The current measure is "local"—it looks at moving one node at a time. It doesn't account for "block moves" where a whole group of nodes might be uncertain together.
  • Computational Overhead: While the calculation is relatively efficient, it still requires iterating through nodes in the vicinity of cuts, which could be a bottleneck for extremely large-scale graphs.
  • Integration: Future work could involve integrating this uncertainty directly into the multicut solver's optimization loop, potentially leading to faster convergence or better heuristic decisions.

Summary updated

Abstract

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...
BibTeX
@inproceedings{kardoost2021uncertainty,
  author = {Amirhossein Kardoost and Margret Keuper},
  title = {{Uncertainty in minimum cost multicuts for image and motion segmentation}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=3TewmJYvUB4},
}

Loading related content...

Figure