{'fraction_non_alphanumeric': 0.03881963482129002, 'fraction_numerical': 0.009284642838669633, 'mean_word_length': 4.6879964695498675, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Mutex Watershed and its Objective: Efficient, Parameter-Free Image 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 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.


INTRODUCTION
M OST image partitioning algorithms are defined over a graph encoding purely attractive interactions. No matter whether a segmentation or clustering is then found agglomeratively (as in single linkage clustering / watershed) or divisively (as in spectral clustering or iterated normalized cuts), the user either needs to specify the desired number of segments or a termination criterion. An even stronger form of supervision is in terms of seeds, where one pixel of each segment needs to be designated either by a user or automatically. Unfortunately, clustering with automated seed selection remains a fragile and error-fraught process, because every missed or hallucinated seed causes an under-or oversegmentation error. Although the learning of good edge detectors boosts the quality of classical seed selection strategies (such as finding local minima of the boundary map, or thresholding boundary maps), non-local effects of seed placement along with strong variability in region sizes and shapes make it hard for any learned predictor to place exactly one seed in every true region.
In contrast to the above class of algorithms, multicut / correlation clustering partitions vertices with both attractive and repulsive interactions encoded into the edges of a graph. Multicut has the great advantage that a "natural" partitioning of a graph can be found, without needing to specify a desired number of clusters, or a termination criterion, or one seed per region. Its great drawback is that its optimization is NP-hard.
The main insight of this paper is that when both attractive and repulsive interactions between pixels are available, then a generalization of the watershed algorithm can be devised that segments an image without the need for seeds or stopping criteria or thresholds. It examines all graph edges, attractive and repulsive, sorted by their weight and adds these to an active set iff they are not in conflict with previous, higher-priority, decisions. The attractive subset of the resulting active set is a forest, with one tree representing each segment. However, the active set can have loops involving more than one repulsive edge. See Fig. 1 for a visual abstract.
In summary, our principal contributions are, first, a fast deterministic algorithm for signed graph partitioning that does not need prior specification of the number of clusters (section 4); and second, its theoretical characterization, including proof that it globally optimizes an objective related to the multicut correlation clustering objective (4).
Combined with a deep net, the algorithm also happens to define the state-of-the-art in a competitive neuron segmentation challenge (section 5). This is an extended version version of [1], with the second principal contribution (section 4) being new. arXiv:1904.12654v1 [cs.CV] 25 Apr 2019

RELATED WORK
In the original watershed algorithm [2], seeds were automatically placed at all local minima of the boundary map. Unfortunately, this leads to severe over-segmentation. Defining better seeds has been a recurring theme of watershed research ever since. The simplest solution is offered by the seeded watershed algorithm [3]: It relies on an oracle (an external algorithm or a human) to provide seeds and assigns each pixel to its nearest seed in terms of minimax path distance. In the absence of an oracle, automatic seed selection is challenging because exactly one seed must be placed in every region. Simple methods, e.g. defining seeds by connected regions of low boundary probability, don't work: The segmentation quality is usually insufficient because multiple seeds are in the same region and/or seeds leak through the boundary.
This problem is typically addressed by biasing seed selection towards over-segmentation (with seeding at all minima being the extreme case). The watershed algorithm then produces superpixels that are merged into final regions by more or less elaborate postprocessing. This works better than using watersheds alone because it exploits the larger context afforded by superpixel adjacency graphs. Many criteria have been proposed to identify the regions to be preserved during merging, e.g. region dynamics [4], the waterfall transform [5], extinction values [6], region saliency [7], and (α, ω)-connected components [8]. A merging process controlled by criteria like these can be iterated to produce a hierarchy of segmentations where important regions survive to the next level. Variants of such hierarchical watersheds are reviewed and evaluated in [9].
These results highlight the close connection of watersheds to hierarchical clustering and minimum spanning trees/forests [10], [11], which inspired novel merging strategies and termination criteria. For example, [12] simply terminated hierarchical merging by fixing the number of surviving regions beforehand. [13] incorporate predefined sets of generalized merge constraints into the clustering algorithm. Graph-based segmentation according to [14] defines a measure of quality for the current regions and stops when the merge costs would exceed this measure. Ultrametric contour maps [15] combine the gPb (global probability of boundary) edge detector with an oriented watershed transform. Superpixels are agglomerated until the ultrametric distance between the resulting regions exceeds a learned threshold. An optimization perspective is taken in [16], which introduces h-increasing energy functions and builds the hierarchy incrementally such that merge decisions greedily minimize the energy. The authors prove that the optimal cut corresponds to a different unique segmentation for every value of a free regularization parameter.
An important line of research is based on the observation that superior partitionings are obtained when the graph has both attractive and repulsive edges [17]. Solutions that optimally balance attraction and repulsion do not require external stopping criteria such as predefined number of regions or seeds. This generalization leads to the NP-hard problem of correlation clustering or (synonymous) multicut (MC) partitioning. Fortunately, modern integer linear programming solvers in combination with incremental constraint generation can solve problem instances of considerable size [18], and good approximations exist for even larger problems [19], [20] Reminiscent of strict minimizers [21] with minimal L ∞ -norm solution, our work solves the multicut objective optimally when all graph weights are raised to a large power.
Related to the proposed method, the greedy additive edge contraction (GAEC) [22] heuristic for the multicut also sequentially merges regions, but we handle attractive and repulsive interactions separately and define edge strength between clusters by a maximum instead of an additive rule. The greedy fixation algorithm introduced in [23] is closely related to the proposed method; it sorts attractive and repulsive edges by their absolute weight, merges nodes connected by attractive edges and introduces no-merge constraints for repulsive edges. However, similar to GAEC, it defines edge strength by an additive rule, which increases the algorithm's runtime complexity compared to the Mutex Watershed. Also, it is not yet known what objective the algorithm optimizes globally, if any. Another beneficial extension relative to standard approaches is the introduction of additional long-range edges. The strength of such edges can often be estimated with greater certainty than is achievable for the local edges used by watersheds on standard 4-or 8-connected pixel graphs. Such repulsive long-range edges have been used in [24] to represent object diameter constraints, which is still an MC-type problem. When long-range edges are also allowed to be attractive, the problem turns into the more complicated lifted multicut (LMC) [25]. Realistic problem sizes can only be solved approximately [22], [26], but watershed superpixels followed by LMC postprocessing achieve state-of-the-art results on important benchmarks [27]. Long-range edges are also used in [28], as side losses for the boundary detection convolutional neural network (CNN); but they are not used explicitly in any downstream inference.
In general, striking progress in watershed-based segmentation has been achieved by learning boundary maps with CNNs. This is nicely illustrated by the evolution of neurosegmentation for connectomics, an important field we also address in the experimental section. CNNs were introduced to this application in [29] and became, in much refined form [30], the winning entry of the ISBI 2012 Neuro-Segmentation Challenge [31]. Boundary maps and superpixels were further improved by progress in CNN architectures and data augmentation methods, using U-Nets [32], FusionNets [33] or inception modules [27]. Subsequent postprocessing with the GALA algorithm [34], [35], conditional random fields [36] or the lifted multicut [27] pushed the envelope of final segmentation quality. MaskExtend [37] applied CNNs to both boundary map prediction and superpixel merging, while floodfilling networks [38] eliminated superpixels altogether by training a recurrent neural network to perform region growing one region at a time.
Most networks mentioned so far learn boundary maps on pixels, but learning works equally well for edge-based watersheds, as was demonstrated in [39], [40] using edge weights generated with a CNN [41], [42]. Tayloring the learning objective to the needs of the watershed algorithm by penalizing critical edges along minimax paths [42] or end-to-end training of edge weights and region growing [43] improved results yet again.
Outside of connectomics, [44] obtained superior boundary maps from CNNs by learning not just boundary strength, but also its gradient direction. Holistically-nested edge detection [45], [46] couples the CNN loss at multiple resolutions using deep supervision and is successfully used as a basis for watershed segmentation of medical images in [47].
We adopt important ideas from this prior work (hierarchical single-linkage clustering, attractive and repulsive interactions, longrange edges, and CNN-based learning). The proposed efficient segmentation framework can be interpreted as a generalization of (c) (a) (b) Fig. 2: In (a) and (b), possible active sets A (bold edges) with associated clusterings (arbitrary node colors), for a given graph with attractive (green) and repulsive (red) edges. In (c), the active set includes a frustrated C 1 (A) cycle (highlighted in yellow), therefore it cannot be associated with a consistent node clustering.
[13], because we also allow for soft repulsive interactions (which can be overridden by strong attractive edges), and constraints are generated on-the-fly.

THE MUTEX WATERSHED ALGORITHM
In this section we introduce the Mutex Watershed Algorithm, an efficient graph clustering algorithm that can ingest both attractive and repulsive cues. We first reformulate seeded watershed as a graph partitioning with infinitely repulsive edges and then derive the generalized algorithm for finitely repulsive edges, which obviates the need for seeds.

Notation
We consider the problem of clustering a graph G(V, E + ∪ E − , W + ∪ W − ) with both attractive and repulsive edge attributes. The scalar attribute w + e ∈ R + 0 associated with edge e ∈ E + is a merge affinity: the higher this number, the higher the inclination of the two incident vertices to be assigned to the same cluster. Similarly, w − e ∈ R + 0 for e ∈ E − is a split tendency: the higher this number, the greater the desire of the incident vertices to be in different clusters. In our application, each vertex corresponds to one pixel in the image to be segmented.
We describe a clustering of G by the active set A = A + ∪ A − composed of two disjunct active sets A + ⊆ E + , A − ⊆ E − , that encode merges and mutual exclusions (must-not-link constraints) between clusters, respectively. We then define the set C i (A) of all cycles with exactly i active repulsive edges An active set is consistent when it can be associated to a clustering of G. More specifically, in a consistent active set two vertices cannot be both mutually exclusive and connected. Thus, we enforce the consistency of the segmentation by forbidding all cycles with exactly one active repulsive edge, i.e. by allowing only active sets s.t. C 1 (A) = ∅. See Fig. 2c for an example of an inconsistent active set.
On the other hand, cycles with more than one active repulsive edge are allowed and C i≥2 (A) can be nonempty in general. For instance, there can be consistent active sets s.t. C 2 (A) = ∅ when there exist multiple mutual exclusion relations between two clusters (see Fig. 2a). The fact that C i≥3 (A) can be nonempty reflects a fundamental asymmetry between attractive and repulsive edges, namely that attraction is transitive while mutual exclusion constraints are not (Fig. 2b). Inputs: weighted graph G(V, E + , W + ) and seeds S ⊆ V ; Output: clusters defined by spanning forest A ∩ E + ; Finally, the constraint C 0 (A) = ∅ can be enforced to ensure that the active set A + ⊆ E + is a forest, similarly to a seeded watershed algorithm.

Seeded watershed from a mutex perspective
One interpretation of the proposed method is in terms of a generalization of the edge-based watershed algorithm [10], [48], [49] or image foresting transform [50]. For didactic reasons, we here first reformulate this fundamental algorithm in a manner compatible with the proposed method.
Edge-based watershed can only ingest a graph with purely attractive interations, G(V, E + , W + ). Without further constraints, the algorithm would yield only the trivial result of a single cluster comprising all vertices. To obtain more interesting output, an oracle needs to provide seeds, namely precisely one node per cluster. These seed vertices are all connected to an auxiliary node (see Fig. 3a) by auxiliary edges with infinite merge affinity. A maximum spanning tree (MST) on this augmented graph can be found in linearithmic time; and the maximum spanning tree (or in the case of degeneracy: at least one of the maximum spanning trees) will include the auxiliary edges. When the auxiliary edges are deleted from the MST, a forest results, with each tree representing one cluster [48], [50], [51].
We now reformulate this well-known algorithm in a way that will later emerge as a special case of the proposed Mutex Watershed: we eliminate the auxiliary node and edges, and replace them by a set of infinitely repulsive edges, one for each pair of seeds (Fig. 3b).
Algorithm 1, applied to the seed mutex graph just defined, gives results identical to seeded watershed on the original graph.
The procedure closely resembles Kruskal's MST algorithm, which iterates over a sorted list of edges and adds each edge only if it does not introduce a cycle.
Clearly, the modified algorithm has the same effect as the original seeded watershed algorithm, because the final set A + is exactly the maximum spanning forest obtained after removing the auxiliary edges from the original solution.
In the sequel, we generalize this construction by admitting less-than-infinitely repulsive edges that do not need to coincide in seed points. This allows repulsive edges to be estimated on the same neighborhood for all pixels, favoring a fully convolutional learning and prediction with CNNs (section 5).

Mutex Watersheds
We now introduce the first core contribution: an algorithm that is empirically no more expensive than a MST computation; but that can ingest both attractive and repulsive cues and partition a graph into a number of clusters that does not need to be specified beforehand. There is no requirement of one seed per cluster, and not even of a hyperparameter that would implicitly determine the number of resulting clusters.
The Mutex Watershed, Algorithm 2, is illustrated in Fig. 4 for a toy example and proceeds as follows. Given a graph with sets of attractive and repulsive edges E + and E − with edge weights W + and W − respectively, do the following: sort all edges E + ∪ E − , attractive and repulsive, by their weight in descending order into a priority queue. Iteratively pop all edges from the priority queue and add them to the active set A, one by one, provided that a set of conditions are satisfied. More specifically, if the next edge popped from the priority queue is attractive, then it is added to the active set if and only if i) its incident vertices are not yet in the same tree of the forest A + (C 0 (A ∪ {e}) = ∅) and ii) there are no mutual exclusion constraints between the two trees (C 1 (A ∪ {e}) = ∅). If, on the other hand, the popped edge is repulsive, then a mutual exclusion constraint is added to the active set if and only if the incident vertices of the edge are not yet in the same tree of The crucial difference to algorithm 1 is that mutex constraints are no longer pre-defined, but created dynamically whenever a repulsive edge is found. However, new exclusion constraints can never override earlier, high-priority merge decisions. In this case, the repulsive edge in question is simply ignored. Similarly, an attractive edge must never override earlier and thus higher-priority must-not-link decisions.

THEORETICAL CHARACTERIZATION
This section summarizes our second core contribution, the proof that the Mutex Watershed Algorithm presented in the previous section globally optimizes a precise energy minimization problem. We begin by defining the Mutex Watershed Objective (Sec. 4.1) and prove that the Mutex Watershed Algorithm solves it optimally (Sec. 4.2).
Finally, we show how this objective is related to the NP-hard correlation clustering / multicut graph partitioning problem [52] (Sec. 4.3).

Mutex Watershed Objective
We now define the Mutex Watershed energy that is minimized by the Mutex Watershed Algorithm. First, we introduce the following property: Definition 4.1. Dominant power: Let G = (V, E, W ) be an edgeweighted graph, with unique weights w e ∈ R + 0 , ∀e ∈ E. We call p ∈ R + a dominant power if: Note that there exists a dominant power for any finite set of edges, since for any e ∈ E we can divide (2) by w p e and observe that the normalized weights w p t /w p e (and any finite sum of these weights) converges to 0 when p tends to infinity. To prove Theorem 4.1 and show that the Mutex Watershed Algorithm 2 finds the optimum of the Mutex Watershed Objective, we prove its greedy choice and optimal substructure property [53]. For both proofs we rely on Equation 2, which guarantees that the greedy choice (i.e. the feasible edge with the highest weight) will always give a greater negative energy contribution than any combination of weaker edges.

Optimality of the Mutex Watershed Algorithm
In this section we prove whereÃ ⊆ E is a set of initially activated edges such that C 0 (Ã) = ∅ and C 1 (Ã) = ∅.
We note that forÃ = ∅, this optimization problem and its optimal solution S(G, ∅) are equivalent to the Mutex Watershed Objective defined in Equation 3. Inputs: • initially activated set of edgesÃ fulfilling C 0 (Ã) = ∅ and C 1 (Ã) = ∅ ; Output: final set of activated edges A ⊆ E \Ã; Algorithm 3: Generalization of the Mutex Watershed algorithm defined in Algorithm 2. An initial setÃ of active edges is given as additional input and the final active set A ⊆ E \Ã. Note that Algorithm 2 is a special case of this algorithm whenÃ = ∅. Differences with Algorithm 2 are highlighted in blue.
A is incomplete if it is not the final solution and there exists a feasible edgeẽ that can be added toÃ without violating the constraints.
Definition 4.5. First greedy step: Let us consider an incomplete, feasible initial active setÃ ⊆ E on G = (V, E, W ). We define (9) as the feasible edge with the highest weight, which is always the first greedy step of algorithm 3.
In the following two theorems, we prove that the Mutex Watershed problem has an optimal substructure property and a greedy choice property [53], which are sufficient to prove that the Mutex Watershed algorithm finds the optimum of the Mutex Watershed Objective.
Theorem 4.2. Greedy-choice property. For an incomplete, feasible initial active setÃ of the Mutex Watershed, the first greedy step g is always part of the optimal solution g ∈ S(G,Ã).
Proof. We will prove the theorem by contradiction by assuming that the first greedy choice is not part of the optimal solution, i.e. g / ∈ S(G,Ã). Since g is by definition the feasible edge with highest weight, it follows that: w(e) < w(g) ∀e ∈ S(G,Ã).
We now consider the alternative active set A = {g}, that is a feasible solution, with which contradicts the optimality of S(G,Ã). 1) After making the first greedy choice g, we are left with a subproblem that can be seen as a new optimization problem of the same structure; 2) The optimal solution S(G,Ã) is always given by the combination of the first greedy choice and the optimal solution of the remaining subproblem.
Proof. After making the first greedy choice and selecting the first feasible edge g defined in Equation 9, we are clearly left with a new optimization problem of the same structure that has the following optimal solution: S(G,Ã ∪ {g}).
In order to prove the second point of the theorem, we now show that: Since algorithm 3 fulfills the greedy-choice property, g ∈ S(G,Ã) and we can add the edge g as an additional constraint to the optimal solution: Then it follows that: which is equivalent to Equation 12.

Relation to multicut / correlation clustering
In this section, we show how the Mutex Watershed Objective (Def. 4.2) is related to the NP-hard multicut graph partition problem of [52], [54], [55]. The quick reader finds a summary in the last paragraph of this section. Consider a graph G = (V, E) with unique and finite weights w e ∈ R, ∀e ∈ E. A large positive weightw e is associated to a strong inclination of the two incident vertices to be assigned to the same cluster; on the other hand, a large negative weightw e represents a great tendency of the incident vertices to be in different clusters. Small weights express (near) indifference. Solving the correlation clustering amounts to finding a graph multicut for which the sum of the weights of cut edges is minimal, which is equivalent to solving the following integer linear program for p = 1: Optimizing this objective is NP-hard. Remarkably, we can derive a related objective that is optimally solved by the Mutex Watershed Algorithm, by choosing p sufficiently large. In order to make the relation to the Mutex Watershed Objective explicit, let us separate the sum in the objective into repulsive (E − := {e ∈ E|w e < 0}) and attractive edges (E + := {e ∈ E|w e ≥ 0}) and substitute to obtain Observe that for p = 1 this objective is equivalent to the multicut, but for p large enough to become a dominant power, becomes the MWS energy (3).
Let us now consider the cycle inequalities (16). We find that the subset of these inequalities over cycles from C 1 is equivalent to the MWS- is an integer linear program with multicut energy at p = 1 and a subset of multicut constraints. The Mutex Watershed objective differs from (23) only in the additional set of constrains C 0 (A) = ∅. These are purely cosmetic and do not affect the clustering result, since only edges within a cluster are constrained. Their purpose is to restrict the solution to be a forest (a set of trees rather than a set of disconnected loopy graphs) w.r.t. the attractive edges which is motivated by the relation of MWS to minimum spanning trees. However, since the proof of Theorem 4.1 does not rely on C 0 (A) = ∅, one can remove C 0 (A ∪ {e}) = ∅ from Algorithm 2 and use identical arguments to prove that it yields the optimal solution to (23) for p large enough in the sense of Equation 2. This optimal solution is a consistent cut of G and thus lies within the tighter full set of multicut constrains. Therefore, it is also a solution to the modified multicut linear program (15)(16) when p is chosen sufficiently large.
In summary, we make the following remarkable observation: in a graph with real (both positive and negative) edge weights in which the absolute weight of each edge is larger than the sum of absolute weights of all "lighter" edges (Equation 2), the normally NP-hard multicut problem becomes simpler and can be solved optimally using the greedy Mutex Watershed Algorithm.

EXPERIMENTS
We evaluate the Mutex Watershed on the challenging task of neuron segmentation in electron microscopy (EM) image volumes. This application is of key interest in connectomics, a field of neuroscience that strives to reconstruct neural wiring digrams spanning complete central nervous systems. The task requires segmentation of neurons from electron microscopy images of neural tissue -a challenging endeavor, since segmentation has to be based only on boundary information (cell membranes) and some of the boundaries are not very pronounced. Besides, cells contain membrane-bound organelles, which have to be suppressed in the segmentation. Some of the neuron protrusions are very thin, but all of those need to be preserved in the segmentation to arrive at the correct connectivity graph. While a lot of progress is being made, currently only manual tracing or proof-reading yields sufficient accuracy for correct circuit reconstruction [56].
We validate the Mutex Watershed algorithm on the most popular neural segmentation challenge: ISBI2012 [31]. We estimate the edge weights using a CNN as described in Section 5.1 and compare with other entries in the leaderboard as well as with other popular post-processing methods for the same network predictions in Section 5.2.

Estimating edge weights with a CNN
The common first step to EM segmentation is to predict which pixels belong to a cell membrane using a CNN. Different postprocessing methods are then used to obtain a segmentation, see section 2 for an overview of such methods. The CNN can either be trained to predict boundary pixels [27], [30] or undirected affinities [28], [57] which express how likely it is for a pixel to belong to a different cell than its neighbors in the 6-neighborhood. In this case, the output of the network contains three channels, corresponding to left, down and next imaging plane neighbors in 3D. The affinities do not have to be limited to immediate neighbors -in fact, [28] have shown that introduction of long-range affinities is beneficial for the final segmentation even if they are only used to train the network. Building on the work of [28], we train a CNN to predict short-and long-range affinities and then use those directly as weights for the Mutex Watershed algorithm.
We estimate the affinities / edge weights for the neighborhood structure shown in Figure 5. To that end, we define local attractive and long-range repulsive edges. When attractive edges are only short-range, the solution will consist of spatially connected segments that cannot comprise "air bridges". This holds true for both (lifted) multicut and for Mutex Watershed. We use a different pattern for in-plane and between-plane edges due to the great anisotropy of the data set. In more detail, we pick a sparse ring of in-plane repulsive edges and additional longer-range in-plane edges which are necessary to split regions reliably (see Figure 5a). We also added connections to the indirect neighbors in the lower adjacent slice to ensure correct 3D connectivity (see Figure 5b). In our experiments, we pick a subset of repulsive edges, by using strides of 2 in the XY-plane in order to avoid artifacts caused by occasional very thick membranes. Note that the stride is not applied to local (attractive) edges, but only to long-range (repulsive) edges. The particular pattern used was selected after inspecting the size of typical regions. The specific pattern is the only one we have tried and was not optimized over.
In total, C + attractive and C − repulsive edges are defined for each pixel, resulting in C + + C − output channels in the network.
We partition the set of attractive / repulsive edges into subsets H + and H − that contain all edges at a specific offset: E + = C + c=1 H + c for attractive edges, with H − defined analogously. Each element of the subsets H + c and H − c corresponds to a specific channel predicted by the network. We further assume that weights take values in [0, 1].
Our training targets for attractive / repulsive edges * w ± can be derived from a groundtruth label image * L according to * Here, i and j are the indices of vertices / image pixels. Next, we define the loss terms for attractive edges (i.e. channels) and repulsive edges (i.e. channels). Equation 26 is the Sørensen-Dice coefficient [59], [60] formulated for fuzzy set membership values. During training we minimize the sum of attractive and repulsive loss terms This corresponds to summing up the channel-wise Sørensen-Dice loss. The terms of this loss are robust against prediction and / or target sparsity, a desirable quality for neuron segmentation: since membranes are locally two-dimensional and thin, they occupy very few pixels in three-dimensional the volume. More precisely, if w + e or * w + e (or both) are sparse, we can expect the denominator e ((w + e ) 2 + ( * w + e ) 2 ) to be small, which has the effect that the numerator is adaptively weighted higher. In this sense, the Sørensen-Dice loss at every pixel i is conditioned on the global image statistics, which is not the case for a Hamming-distance based loss like Binary Cross-Entropy or Mean Squared Error.
We optimize this loss using the Adam optimizer [61] and additionally condition learning rate decay on the Adapted Rand Score [31] computed on the training set every 100 iterations. During training, we augment the data set by performing in-plane rotations by multiples of 90 degrees, flips along the X-and Y-axis as well as elastic deformations. At prediction time, we use test time data augmentation, presenting the network with seven different versions of the input obtained by a combination of rotations by a multiple of 90 degrees, axis-aligned flips and transpositions. The network predictions are then inverse-transformed to correspond to the original image, and the results averaged.

ISBI Challenge
The ISBI 2012 EM Segmentation Challenge [31] is the neuron segmentation challenge with the largest number of competing entries. The challenge data contains two volumes of dimensions 1.5 × 2 × 2 microns and has a resolution of 50 × 4 × 4 nm per pixel.  The groundtruth is provided as binary membrane labels, which can easily be converted to a 2D, but not 3D segmentation. To train a 3D model, we follow the procedure described in [27].
The test volume has private groundtruth; results can be submitted to the leaderboard. They are evaluated based on the Adapted Rand Score (Rand-Score) and the Variation of Information Score (VI-Score) [31].
Our method holds the top entry in the challenge's leader board 1 at the time of submission, see Table 1a. This is especially remarkable insofar as it is simpler than the methods holding the other top entries. Three out of four rely on a CNN to predict boundary locations and postprocess its output with the complex pipeline described in [27]. This post-processing first generates superpixels via distance transform watersheds. Then it computes a merge cost for local and long-range connections between superpixels. Based on this, it defines a lifted multicut partioning problem that is solved approximately. In contrast, our Comparison with other segmentation methods The weights predicted by the CNN described above can be postprocessed directly by the Mutex Watershed algorithm. To ensure a fair comparison, we transform the same CNN predictions into a segmentation using basic and state-of-the-art post-processing methods. We start from simple thresholding (THRESH) and seeded watershed. Since these cannot take long-range repulsions into account, we generate a boundary map by taking the maximum 2 values over the attractive edge channels. Based on this boundary map, we introduce seeds at the local minima (WS) and at the maxima of the smoothed distance transform (WSDT). For both variants, the degree of smoothing was optimized such that each 2. The maximum is chosen to preserve boundaries.
region receives as few seeds as possible, without however causing severe under-segmentation. The performance of these three baseline methods in comparison to Mutex Watershed is summarized in Table 1b. The methods were applied only in 2D, because the high degree of anisotropy leads to inferior results when applied in 3D.
In contrast, the Mutex Watershed can be applied in 3D out of the box and yields significantly better 2D segmentation scores. Qualitatively, we show patches of results in Figure 6. The major failure case for WS ( Figure 6e) and WSDT ( Figure  6f) is over-segmentation caused by over-seeding a region. The major failure case for THRESH is under-segmentation due to week boundary evidence (see Figure 6d). In contrast, the Mutex Watershed produces a better segmentation, only causing minor over-segmentation (see Figure 6a, Figure 6b).
Note that, in contrast to most pixel-based postprocessing methods, our algorithm can take long range predictions into account. To compare with methods which share this property, we turn to the multicut and lifted multicut-based partitioning for neuron segmentations as introduced in [18] and [25]. As proposed in [62], we compute costs corresponding to edge cuts from the affinities estimated by the CNN via: We set up two multicut problems: the first is induced only by the short-range edges (MC-LOCAL), the other by short-and longrange edges together (MC-FULL). Note that the solution to the full connectivity problem can contain "air bridges", i.e. pixels that are connected only by long-range edges, without a path along the local edges connecting them. However, we found this not to be a problem in practice. In addition, we set up a lifted multicut (LMC) problem from the same edge costs.
Both problems are NP-hard, hence it is not feasible to solve them exactly on large grid graphs. For our experiments, we use the approximate Kernighan Lin [22], [63] solver. Even this allows us to only solve individual 2D problems at a time. The results for MC-LOCAL and MC-FULL can be found in Table 1b. The MC-LOCAL approach scores poorly because it under-segments heavily. This observation emphasizes the importance of incorporating the longer-range edges. The MC-FULL and LMC approaches perform well. Somewhat surprisingly, the Mutex Watershed yields a better segmentation still, despite being much cheaper in inference. We note that both MC-FULL, LMC and the Mutex Watershed are evaluated on the same long-range affinity maps (i.e. generated by the same CNN with the same set of weights).

CONCLUSION AND DISCUSSION
We have presented a fast algorithm for the clustering of graphs with both attractive and repulsive edges. The ability to consider both obviates the need for the kind of stopping criterion or even seeds that all popular algorithms except for multicut / correlation clustering need. The proposed method has low computational complexity in imitation of its close relative, Kruskal's algorithm. We have shown which objective this algorithm optimizes exactly, and that this objective emerges as a specific case of the multicut objective. It is possible that recent interesting work [67] on partial optimal solutions may open an avenue for an alternative proof.
Finally, we have found that the proposed algorithm, when presented with informative edge costs from a good neural network,

APPENDIX A EFFICIENT IMPLEMENTATION OF THE MUTEX WA-TERSHED ALGORITHM
In this section we propose an efficient implementation of the MWS, derive its theoretical average runtime complexity and show that in practice the MWS scales with O(E log E).

Notation:
Let us explicitly define clusters using the "connected" predicate ∀i, j ∈ V : Conversely, the active subset A − ⊆ E − of repulsive edges defines mutual exclusion relations by using the following predicate: To implement the MWS efficiently we reformulate the algorithm in terms of the predicates connected and mutex using the following equalities (for an arbitrary set A ⊆ E with C 0/1 (A) = ∅) ∀(i, j) ∈ E + \ A : connected(i, j|A) ⇔ C 0 (A ∪ {(i, j)}) = ∅ mutex(i, j|A) ⇔ C 1 (A ∪ {(i, j)}) = ∅ ∀(i, j) ∈ E − \ A : connected(i, j|A) ⇔ C 1 (A ∪ {(i, j)}) = ∅ to rewrite the Mutex Watershed Algorithm as Algorithm 4. In the following analysis we omit the dependence on A in all predicates to improve readability.

A.1 Time Complexity Analysis
Before analyzing the time complexity of algorithm 4 we first review the complexity of Kruskal's algorithm. Using a union-find data structure (with path compression and union by rank) the time complexity of merge(i, j) and connected(i, j) is O(α(V )), where α is the slowly growing inverse Ackerman function, and the total runtime complexity is dominated by the initial sorting of the edges O(E log E) [53].
To check for mutex constraints efficiently, we maintain a set of all active mutex edges
Using the indicator a e := y e , if e ∈ E − 1 − y e if e ∈ E + we can decompose the r.h.s. of equation (22) into 3. In the worst case G is a fully connected graph, with |E| = |V | 2 , hence log |V | = 1 2 log |E| for graphs without parallel edges.