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 a greedy algorithm for signed 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.
Abstract (translated)
图像分割，或没有语义的分割，是将图像分解成不同的片段，或等效地检测闭合轮廓的任务。大多数先前的工作要么需要种子，每段一个；要么需要一个阈值；要么将任务定义为多输出/相关聚类，这是一个NP难题。在这里，我们提出了一种贪婪的有符号图划分算法，即“互斥分水岭”。与种子分水岭不同的是，该算法不仅能适应吸引人的线索，还能适应令人厌恶的线索，使其能够在不需要显式种子或可调阈值的情况下找到之前未指定数量的片段。我们还证明了这个简单的算法能够解决全局最优问题，即一个与多出/相关聚类整数线性规划公式密切相关的目标函数。该算法具有确定性强、实现简单、具有经验线性的复杂性。当呈现来自深度神经网络的短期吸引和长期排斥提示时，Mutex分水岭提供了目前已知的最佳竞争结果ISBI 2012 EM分割基准。
URL
https://arxiv.org/abs/1904.12654
