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

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.

References in corpus (13)

• Adam: A Method for Stochastic Optimization
• FusionNet: A deep fully residual convolutional neural network for image segmentation in connectomics
• Large Scale Image Segmentation with Structured Loss based Deep Learning for Connectome Reconstruction
• Superhuman Accuracy on the SNEMI3D Connectomics Challenge
• Machine learning of hierarchical clustering to segment 2D and 3D images
• Maximin affinity learning of image segmentation
• A Multi-cut Formulation for Joint Segmentation and Tracking of Multiple Objects
• On the equivalence between hierarchical segmentations and ultrametric watersheds
• Image Segmentation by Size-Dependent Single Linkage Clustering of a Watershed Basin Graph
• A Multi-Pass Approach to Large-Scale Connectomics
• Analysis and Optimization of Graph Decompositions by Lifted Multicuts
• RhoanaNet Pipeline: Dense Automatic Neural Annotation
• Anisotropic EM Segmentation by 3D Affinity Learning and Agglomeration

Cited by in corpus (8)

• FusionNet: A deep fully residual convolutional neural network for image segmentation in connectomics
• Triplet-Watershed for Hyperspectral Image Classification
• Spatial-Temporal Deep Embedding for Vehicle Trajectory Reconstruction from High-Angle Video
• Dynamic Spectral Residual Superpixels
• Estimating the Robustness of Classification Models by the Structure of the Learned Feature-Space
• Stateless actor-critic for instance segmentation with high-level priors
• Cell segmentation of in situ transcriptomics data using signed graph partitioning
• Deep learning for bioimage analysis