The Mutex Watershed and its Objective: Efficient, Parameter-Free Graph Partitioning

Steffen Wolf, Alberto Bailoni, Constantin Pape, Nasim Rahaman, Anna Kreshuk, Ullrich Köthe, Fred A. Hamprecht

Abstract

Image partitioning, or segmentation without semantics, is the task of decomposing an image into distinct segments or detecting closed contours. Most prior work either requires one seed per segment, a specific threshold, or formulates the task as an NP-hard multicut/correlation clustering problem. We propose the Mutex Watershed (MWS), an efficient algorithm for graph partitioning that accommodates both attractive and repulsive cues. This allows it to find an unspecified number of segments without explicit seeds or tunable thresholds. We prove that MWS solves a global objective function related to the multicut formulation. The algorithm is deterministic, simple to implement, and has empirical linearithmic complexity. On the ISBI 2012 EM segmentation benchmark, MWS achieves state-of-the-art results.

Introduction: The Seed and Complexity Dilemma

Image segmentation—grouping pixels into meaningful regions—is a fundamental computer vision challenge. Traditionally, researchers have faced a trade-off between speed and flexibility:

  1. Seeded Watersheds: These are computationally efficient but require "seeds" for every region. Missing a seed leads to under-segmentation, while extra seeds cause over-segmentation.
  2. Multicut/Correlation Clustering: This elegant formulation uses attractive and repulsive cues to determine the natural number of clusters. However, finding the global optimum is NP-hard, making it impractical for large-scale high-resolution images.

The Mutex Watershed (MWS) bridges this gap, offering the speed of the watershed with the flexibility of the multicut formulation.

The Mutex Watershed Algorithm

The MWS can be viewed as a generalization of Kruskal’s algorithm for Minimum Spanning Trees, adapted for graphs with both positive (attractive) and negative (repulsive) edge weights.

The Mutex Watershed (MWS) algorithm pseudocode.

The algorithm processes edges in descending order of their absolute weights. If it encounters an attractive edge, it merges the two regions unless a "mutex" (mutual exclusion) constraint already exists between them. If it encounters a repulsive edge, it adds a "mutex" constraint between the two regions, ensuring they can never be merged by lower-priority attractive edges. This greedy approach is deterministic and efficient, utilizing a modified Union-Find data structure to achieve an empirical complexity of $O(E \log E)$.

Theoretical Foundation and Global Optimality

A key contribution of this work is the proof that MWS is not merely a heuristic. The authors demonstrate that MWS globally optimizes a specific objective function related to the multicut problem. Specifically, it solves the multicut objective in the limit where edge weights are raised to a "dominant power," making the highest weights strictly dictate the partitioning. This theoretical bridge shows that for many practical tasks, the full complexity of Integer Linear Programming is unnecessary.

Application to Neural Circuit Reconstruction

The method was evaluated on the ISBI 2012 EM segmentation challenge, which involves segmenting individual neurons in electron microscopy volumes. This task is notoriously difficult due to thin, faint membranes where "leaks" can easily merge distinct cells.

MWS applied to EM data: (Left) Long-range cues; (Middle) Boundary predictions; (Right) Final segmentation with mutex constraints.

By using a Convolutional Neural Network (CNN) to predict both local neighbor affinities and long-range repulsive interactions, MWS gains a global perspective. High-priority repulsive edges act as dynamic constraints, preventing leaks in areas with weak membrane evidence.

Key Results and Performance

  • State-of-the-Art Accuracy: Combined with a 3D U-Net, MWS achieved the top spot on the ISBI 2012 leaderboard at the time of publication.
  • Exceptional Efficiency: MWS is orders of magnitude faster than traditional multicut solvers. On benchmark data, MWS required only 43.3 seconds, compared to over 9,400 seconds (2.5+ hours) for a standard multicut solver (MC-FULL), while producing superior results.
  • Parameter-Free: Unlike many competing methods, MWS does not require manual seeding or the tuning of a global threshold to determine the number of segments.

Conclusion

The Mutex Watershed provides a powerful, efficient, and theoretically grounded approach to graph partitioning. By incorporating repulsive cues into a greedy framework, it achieves the flexibility of global optimization methods at a fraction of the computational cost. While its performance depends on the quality of the input weights, its success on challenging EM datasets demonstrates its potential for large-scale image analysis.

Summary updated

Abstract

Image partitioning, or segmentation without semantics, is the task of decomposing an image into distinct segments, or equivalently to detect closed contours. Most prior work either requires seeds, one per segment; or a threshold; or formulates the task as multicut / correlation clustering, an NP-hard problem. Here, we propose an efficient algorithm for graph partitioning, the "Mutex Watershed". Unlike seeded watershed, the algorithm can accommodate not only attractive but also repulsive cues, allowing it to find a previously unspecified number of segments without the need for explicit seeds or a tunable threshold. We also prove that this simple algorithm solves to global optimality an objective function that is intimately related to the multicut / correlation clustering integer linear programming formulation. The algorithm is deterministic, very simple to implement, and has empirically linearithmic complexity. When presented with short-range attractive and long-range repulsive cues from a deep neural network, the Mutex Watershed gives the best results currently known for the competitive ISBI 2012 EM segmentation benchmark.
BibTeX
@article{wolf2020mutex,
  author = {Steffen Wolf and Alberto Bailoni and Constantin Pape and Nasim Rahaman and Anna Kreshuk and Ullrich Köthe and Fred A. Hamprecht},
  title = {{The Mutex Watershed and its Objective: Efficient, Parameter-Free Graph Partitioning}},
  journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  year = {2020},
  doi = {10.1109/tpami.2020.2980827},
}

Loading related content...

Figure