The Mutex Watershed and its Objective: Efficient, Parameter-Free Graph Partitioning
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Clusteringgraph partitioningSegmentationSimilar Papers 제목 키워드 기반
The Mutex Watershed: Efficient, Parameter-Free Image Partitioning
Image partitioning, or segmentation without semantics, is the task of decomposing an image into distinct segments; or equivalently, the task of detecting closed contours in an image. Most prior work either requires seeds…
Clusteringgraph partitioningSegmentationJoint Semantic Instance Segmentation on Graphs with the Semantic Mutex Watershed
Semantic instance segmentation is the task of simultaneously partitioning an image into distinct segments while associating each pixel with a class label. In commonly used pipelines, segmentation and label assignment are…
graph partitioningInstance SegmentationSegmentationSemantic Segmentation+1The Semantic Mutex Watershed for Efficient Bottom-Up Semantic Instance Segmentation
Semantic instance segmentation is the task of simultaneously partitioning an image into distinct segments while associating each pixel with a class label. In commonly used pipelines, segmentation and label assignment are…
graph partitioningInstance SegmentationSegmentationSemantic Segmentation+1Mutex Graphs and Multicliques: Reducing Grounding Size for Planning
We present an approach to representing large sets of mutual exclusions, also known as mutexes or mutex constraints. These are the types of constraints that specify the exclusion of some properties, events, processes, and…
At-Most-One Constraints in Efficient Representations of Mutex Networks
The At-Most-One (AMO) constraint is a special case of cardinality constraint that requires at most one variable from a set of Boolean variables to be set to TRUE. AMO is important for modeling problems as Boolean satisfi…