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:
- 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.
- 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 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.
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