高效无参数的图像分割算法：Mutex Watershed

Mutex Watershed：高效、无参数的图像分割SteffenWolf 1，Constantin Pape 1，2，Alberto Bailoni 1，Nasim Rahaman 1，Anna Kresuk1，2，UllrichKoüthe1，anddFredA. 火腿precht11德国海德堡大学HCI/IWR{firstname.lastname}@ iwr.uni-heidelberg.de2EMBL海德堡，德国抽象。图像分割或无语义分割是将图像分解为不同片段的任务;或者等效地，检测图像中的闭合轮廓的任务大多数先前的工作要么需要种子，每段一个;或阈值;或者将该任务表述为NP-难有符号图划分问题。在这里，我们提出了一个算法的经验线性复杂度。与种子watershed，该算法不仅可以容纳有吸引力的，但也排斥线索，使其能够找到一个以前未指定数量的段，而不需要明确的种子或可调阈值。该算法被称为“M ut ex W a t e r s h e d”，与最小生成树计算密切相关。它是确定性的，易于实现。当呈现来自深度神经网络的短程吸引和长程排斥线索时，Mutex Watershed给出的结果目前定义了竞争性ISBI2012 EM分割基准中的最新技术水平。这些结果也优于最近提出的其他聚类策略操作上非常相同的网络输出。1介绍大多数图像分割算法都是在编码纯粹吸引力交互的图上定义的。无论分割或聚类然后是聚合地（如在单链接聚类/分水岭中）还是分开地（如在谱聚类或迭代归一化切割中）发现的，用户都需要以指定期望的段数或终止标准。一种更强的监督形式是种子，其中每个片段的一个像素不幸的是，使用自动种子选择的聚类仍然是一个脆弱且充满错误的过程，因为每个丢失或幻觉的种子都会导致欠分割或过分割错误。虽然好的边缘检测器的学习提高了经典种子选择策略的质量（例如，找到边界图的局部最小值，或阈值化边界图），但是沿着边缘检测器的种子放置的非局部效应仍然存在。作者贡献相等。2Wolf、Pape、Bailo ni、Rahaman、Kreshuk、Ko¨the和Hamprecht图1：左：来自ISBI 2012 EM分割挑战的原始数据和使用CNN针对每个像素中：在中/长范围的垂直/水平排斥相互作用显示在上/下半部分。右图：所提出的算法在分段过程中调用的主动互斥（mutex）约束区域大小和形状的强可变性使得任何学习的预测器难以在每个真实区域中精确地放置一个与上述类别的算法相比，多切割/相关聚类将具有吸引和排斥相互作用的顶点分割成组的边缘。可以找到图的“n个最小”分区处的多个最小区域，而不需要指定期望数量的集群、或终止标准、或每个区域一个它的最大缺点是优化问题是NP难的。本文的主要观点是，当像素之间的吸引力和排斥力的相互作用是可用的，然后可以设计一个概括的分水岭算法，分割图像，而不需要种子或停止标准或阈值。它检查所有的图形边缘，吸引力和排斥力，排序的重量，并将这些添加到一个活跃的集合，如果他们不与以前的，更高的优先级，决策冲突。所得到的活动集的有吸引力的子集是一个森林，用一棵树表示每个部分。然而，活动集可以具有涉及多于一个排斥边的循环见图1为视觉抽象。通常，在我们的 实施例中，所述Mu t e x W at e s h e s h e s是一种“bestofbothw or lds”算法，其结合了该M ut i c u t i c u t e s h y p e r -参数的可靠分配与Kruskal型分水岭算法的小计算足迹。该算法在第3节中给出。 在第4节中，我们针对非常强的基线评估算法。我们选择了一个具有挑战性的数据集神经元分割从电子显微镜（EM）图像堆栈作为基准。对于此任务，分水岭分割是一个关键组成部分：EM染色仅突出膜边界，不鼓励使用区域线索进行分割。通过将远程排斥纳入分水岭程序，我们可以得到互斥分水岭3已经从该步骤获得了准确的分割，避免了用于团聚的昂贵此外，我们目前的BSDS500的初步结果，证明所提出的方法对自然图像的适用性。我们描述了我们未来的计划，包括语义分割的扩展，在第5节。我 们 的 实 现 可 以 在 https://github.com/hci-unihd/mutex-watershed.git 上 找到。2相关工作在原始分水岭算法[1]中，种子被自动放置在边界图的所有局部极小值处。不幸的是，这会导致严重的过度分割.定义更好的种子一直是分水岭研究的一个反复出现的主题。最简单的解决方案由种子分水岭算法[2]提供：它依赖于oracle（外部算法或人类）来提供种子，并根据极大极小路径距离将每个像素分配给其最近的种子。在没有oracle的情况下，自动种子选择是具有挑战性的，因为必须在每个区域中放置一个种子。简单的方法，例如通过低边界概率的连接区域定义种子，不起作用：分割质量通常是不够的，因为多个种子在同一区域和/或种子泄漏通过边界。该问题通常通过将种子选择偏向过度分割来解决（在所有最小值处播种是极端情况）。然后，分水算法产生超像素，这些超像素通过或多或少复杂的后处理合并到最终区域中。这比单独使用分水岭效果更好，因为它利用了超像素邻接图提供的更大上下文。已经提出了许多标准来识别在合并期间要保留的区域，例如区域动态[3]，瀑布变换[4]，消光值[5]，区域显着性[6]和（α，ω）-连接分量[7]。由这些标准控制的在[8]中审查和评价了此类分级流域的变体。这些结果突出了流域与分层聚类和最小生成树/森林的密切联系[9，10]，这激发了新的合并策略和终止标准。例如，[11]简单地通过预先固定幸存区域的数量来终止分层合并。[12]将广义合并约束的预定义集合并入聚类算法。根据[13]的基于图形的分割定义了当前区域的质量度量，并且当合并成本超过该度量时停止。超度量轮廓图[14]将gPb（全局边界概率）边缘检测器与定向分水岭变换相结合聚集超像素，直到所得区域之间的超度量距离超过学习阈值。在[15]中采用了优化视角，其引入了h-递增能量函数并递增地构建层次结构作者证明4Wolf、Pape、Bailo ni、Rahaman、Kreshuk、Ko¨the和Hamprecht最优切割对应于自由正则化参数的每个值的不同的唯一分割。一个重要的研究路线是基于观察，即当图具有吸引和排斥边时，可以获得优越的partitionings。最佳平衡吸引和排斥的解决方案不需要外部停止标准，例如预定义数量的区域或种子。这种一般化导致了相关聚类或（同义）多切（MC）划分的NP难题[16]。幸运的是，现代整数线性规划求解器结合增量约束生成可以解决相当大的问题实例[17]，并且对于更大的问题存在良好的近似[18，19]。另一个有益的扩展是引入额外的长程边缘。由于其更大的视野，这些边缘的强度往往可以估计更大的确定性比在标准流域中使用的局部边缘是可实现的。这已经在[20]中用于通过排斥长范围边缘来表示对象大小约束，这仍然是MC型问题。当长距离边缘也被允许是有吸引力的时，问题变成更复杂的提升多切（LMC）[21]。现实的问题大小只能近似解决[22，23]，但流域超像素之后的LMC后处理在重要基准上实现了最先进的结果[24]。在[25]中也使用了长程边缘，作为边界检测CNN的侧损失;但是它们没有在任何下游推断中被显式地使用。总的来说，通过使用卷积神经网络（CNN）学习边界图，在基于分水岭的分割方面取得了显着进展这是很好地说明了神经分割的进化连接组学，一个重要的领域，我们也在实验部分地址。CNN在[26]中被引入到这个应用中，并且以更精细的形式[27]成为ISBI 2012年神经分段挑战赛的获奖作品[28]。通过CNN架构和数据增强方法的进步，使用U-Nets [29]，FusionNets [30]或inception模块[24]进一步改进了边界图和超像素。使用GALA算法[31，32]、条件随机场[33]或提升的多切[24]的后续后处理推动了最终分割质量的包络MaskExtend [34]将CNN应用于边界图预测和超像素合并，而flood-filling网络[35]通过训练递归神经网络来一次执行一个区域的区域生长来消除超像素。到目前为止提到的大多数网络都在像素上学习边界图，但是学习对于基于边缘的流域同样有效，正如[36，37]中使用CNN生成的边缘权重所证明的那样[38，39]。通过惩罚沿极大极小路径的临界边缘[39]或边缘权重和区域生长的端到端训练[40]来根据分水岭算法的需要定制学习目标，再次改善了结果。在连接组学之外，[41]通过学习不仅是边界强度，而且是其梯度方向，从CNN中获得了更好的边界映射。整体嵌套边缘检测[42，43]使用多分辨率耦合CNN损失互斥分水岭5深度监督，并在[44]中成功用作医学图像分水岭分割的基础。本文将所有这些概念（分层聚类，吸引和排斥的相互作用，长程边缘，和基于CNN的学习）结合到一个新的高效分割框架中。它可以被解释为[12]的一般化，因为我们还允许软约束（可以被强吸引边覆盖），并且约束是由神经网络动态生成的，而不是预定义的。根据[22]，我们的方法也与贪婪加性边缘收缩（GAEC）相关，但是我们分别处理吸引和排斥相互作用，并且通过最大值而不是加性规则来定义集群之间的边缘强度。3互斥分水岭算法3.1定义和符号我们考虑图G（V，E+∪E-，W+∪W-）的聚类问题，其中吸引和排斥边缘属性。标量属性w+∈R+为-e0级与边e∈E+相关联的是合并亲和度：该数字越高，将被分配到同一聚类的两个入射顶点的倾斜度越类似地，对于e∈E−，w − ∈ R +是分裂趋势：这个数字越高，e0级入射顶点在不同簇中的趋势越大。在我们的应用程序中，每个顶点对应于图像中的一个像素进行分割。两个顶点可以没有连接它们的边;或吸引边e∈E+;或排斥边e∈E−;或同时有两条边，一条吸引，一条排斥。边缘可以是局部/短距离（当连接图像中紧邻的两个像素时）或长距离。Mutex Watershed算法在3.3小节中定义，分别维护离散事件A+E+、A−E−、A+∩A−=、编码项和群集通过“连接”定义i，j∈V：Πi→j={ pathπ fromi toj withπ连通（i，j）路π∈Πi→j且πA+E+cluster（i）={i}∪{j：connected（i，j）}相反，排斥边的活动子集A−E−通过使用以下谓词来定义相互排斥关系：互斥量（i，j）惠函数e=（k，l）∈A−，k∈cluster（i）和l∈cluster（j），cluster（i）/= cluster（j）必须选择允许的活动边集A+和A-，使得结果聚类是一致的，即参与互斥约束的节点6Wolf、Pape、Bailo ni、Rahaman、Kreshuk、Ko¨the和Hamprecht∞∞∞∞∞∞14121412201716201718166186871598715595(a)（b）第（1）款图2：使用（a）最大生成树计算或（b）算法1获得的种子分水岭聚类的两个等效表示。两个图共享加权吸引（绿色）边和种子（阴影节点）。（a）中与辅助节点（灰色）的无限吸引连接被（b）中每对种子之间的无限排斥（红色）边所取代两个最终聚类由活动集（粗体边缘）定义并且是相同的。节点颜色指示聚类结果，但可以是任意的。不能在同一个集群中：mutex（i，j）⇒ not connected（i，j）.“连接”和“多个”提供了使用统一查找数据结构的高效评估3.2从互斥体的角度看种子流域所提出的方法的一种解释是基于边缘的分水岭算法[45，46，9]或图像森林变换[47]的泛化。该算法只能摄取具有纯吸引交互的图G（V，E+，W+）。在没有进一步约束的情况下，该算法将仅产生包括所有顶点的单个聚类的平凡结果。为了获得更有趣的输出，oracle需要提供种子，即每个集群精确地一个节点这些种子顶点都连接到一个辅助节点（见图1）。2（a））通过具有无限合并亲和性的辅助该图的最大生成树（MST）可以在线性时间内求出;并且最大生成树（或者在退化的情况下：至少一个最大生成树）将包括辅助边。当从MST中删除辅助边时，就会产生一个森林，每个树代表一个聚类[9，45，47]。我们现在以一种稍后将作为所提出的互斥分水岭的特殊情况出现的方式重新制定这个众所周知的算法：我们去掉了辅助节点和边，并用一组无限排斥的边来代替它们，其中一条边对应于e的一对seeds（Fig.第2段（b）分段）。该算法是Kruskal的 M S T 算 法 在 刚 定 义 的 种子 互 斥 图 上 的 一 个 变 种 ， 它 给 出 了 与 原 始 图 上 的 种 子 分 水岭 相 同 的 结 果 .这种算法仅通过对if语句中的计算结果的检查来区分来自Krusk的算法。显然，修改后的算法与原算法具有相同的效果，因为最终的集合A+正好是原解去掉辅助边后得到的最大生成森林。互斥分水岭7输入：加权图G（V，E+，W+）和种子SV，使得E−={（s，s）|i，j ∈ 1，. . . 、|S|; i = j}是无限排斥边的集合Ij在所有种子之间;输出：由激活的边A+定义的聚类;Initialization：A+=;A−=E−;对于（i，j）=e∈E+按w+do如果不连接（i，j）且不互斥（i，j），则A+←A+e;合并i和j并继承父集群端端算法一：互斥版本的种子分水岭算法。在续集中，我们推广这种结构，承认小于无限的ly排斥边缘。重要的是，这些可能是密集的，因此比种子更容易自动估计，因为种子严格要求每个集群只有一个。3.3互斥分水岭我们现在介绍核心贡献：一种算法，其在经验上不比MST计算更昂贵;但是其可以摄取吸引和排斥线索并且将图划分为不需要预先指定的多个聚类。不需要每个聚类一个种子，甚至不需要隐含地确定结果聚类的数量的超参数。互斥分水岭算法2如下进行：给定一个具有吸引和排斥边集合E+和E-的图，边权重为W+和W-分别，做以下事情：将所有边E+∪E-，吸引或排斥，按其权重降序排列到优先级队列中。迭代弹出所有边并将它们逐个添加到活动集，前提是满足一组条件更具体地，如果从优先级队列弹出的下一条边是有吸引力的，并且其关联顶点还不在同一树中，则连接相应的树，只要这不被互斥约束排除。另一方面，如果弹出的边是排斥的，并且如果它的关联顶点还不在同一棵树中，则在两棵树之间添加互斥算法1的关键区别在于互斥约束不再是预定义的，而是在发现排斥边时动态创建。然而，新的排除约束永远不能覆盖早期的高优先级合并决策。在这种情况下，所讨论的排斥边被简单地忽略。类似地，有吸引力的边缘决不能覆盖较早的并且因此较高优先级的必须不链接的决定。8Wolf、Pape、Bailo ni、Rahaman、Kreshuk、Ko¨the和Hamprecht输入：加权图G（V，E+∪E−，W+∪W−）;输出：由激活边A+定义的簇;Initialization：A+=;A−=;对于（i，j）=e∈E+∪E−按W+∪W−do的降序如果e∈E+则如果不连接（i，j）且不互斥（i，j），则merge（i，j）：A+←A+e;合并i和j并继承父集群端其他如果不连接（i，j），则addmutex（i，j）：A−←A−∪e;在i和j之间添加互斥约束端结束结束算法2：互斥分水岭3.4时间复杂度分析在分析算法2的时间复杂度之前，我们首先回顾了Kruskal算法的复杂度。在一个实例中使用union-findd，merge（i， j）和connected（i， j）的复杂度为O（α（V）），其中α是缓慢增长的逆Ackerman函数，并且总的运行时复杂度由边的初始排序O（ElogE）[48]决定。为了有效地检查互斥约束，我们维护了一组所有活动互斥边M[Ci]={（u，v）∈ A−|u ∈ Ci<$v ∈ Ci}对于每个Ci= cluster（i），使用哈希表，其中插入新的互斥体边缘（即，addmutex）和搜索的平均复杂度为O（1）。请注意，每个集群都可以通过其union-find根节点有效地识别。对于多个x（i，j），如果M[Ci]∩M[Cj]=b，则对于较大散列表中的因此，mutex（i，j）的平均复杂度为O（min（|M[Ci]|、|M[Cj]|）的情况。类似地，在m_rge（i，j）期间，通过合并两个散列表来继承多个约束，这也具有平均复杂度O（m_in（|M[Ci]|、|M[Cj]|）的情况。最 后 ， 吸 引 边 的 平 均 运 行 时 间 贡 献 O （ |E+|·α （ V ） +|E+|·M ）（checkingmuxconstrainsandposibimerg ing）和repivedg esO（|E−|·α（V）+|E−|）（在一个示例中）计算算法2的总平均运行时复杂度：O（ElogE + E·α（V）+EM）。（一）互斥分水岭9|E||E|2019 - 05 - 22 00：00：0000：00（|M[Ci]|、|M[Cj]|）的情况。我们ingα（V）∈O（l ogV）∈O（logE），这简化为O（E log E+ EM）。（二）在最坏的情况下O（M）=O（E），互斥分水岭算法的运行时间复杂度为O（E2）.从经验上讲，我们通过测量ISBI挑战的不同子卷的MutexWatershed的运行时间发现O（EM）≈ O（ElogE）（参见图3），从而得出经验互斥分水岭复杂度：O（E log E）（3）图3：在不同大小的ISBI挑战的子体积上测量的Mutex分水岭的运行时间T（没有对边缘进行排序）（从而改变总的阈值边数E）。我们绘制T超过|E|在对数图中，T|E|1998年12月20日（|E|）显示为直线。 对数函数（绿线）拟合到测量的T（蓝色十字），其中（R2= 0。9896）。最佳契合表明经验上T≈ O（ElogE）。10Wolf、Pape、Bailo ni、Rahaman、Kreshuk、Ko¨the和Hamprecht4实验我们评 估互斥分水 岭的挑战性 任务的神经元 分割的电子 显微镜（EM）的图像体积。该应用程序是连接组学的关键兴趣，连接组学是神经科学的一个领域，致力于重建跨越完整中枢神经系统的神经接线图。该任务需要从神经组织的电子显微镜图像中分割神经元-这是一项具有此外，细胞含有膜结合的细胞器，其必须在分割中被一些神经元突起非常薄，但是所有这些突起必须在分割中被保留以达到正确的连通性图。虽然最近已经取得了很多进展，但只有手动跟踪才能为正确的电路重建提供足够的精度[49]。我们在最流行的神经分割挑战中验证了Mutex Watershed算法：ISBI2012 [28]。我们使用4.1中描述的CNN估计边缘权重，并与排行榜中的其他条目进行比较以及用于相同网络预测4.2的其它通用后处理方法。4.1用CNN估计边缘权重EM分割的常见方法是使用CNN预测哪些像素属于在顶部使用不同的后处理方法以获得分割，参见第2节以了解这些方法的概述。CNN可以被训练来预测边界像素[27，24]或无向亲和度[25，50]，其表示像素与其在6邻域中的邻居属于不同单元的可能性在这种情况下，网络的输出包含三个通道，对应于3d中的左、下和下一成像平面邻居。亲和度不必局限于近邻-事实上，[25]已经表明，引入长程亲和度对于最终分割是有益的，即使它们在训练期间仅用作辅助损失。在[25]的工作基础上，我们训练CNN来预测短期和长期亲和力，然后直接将其用作Mutex Watershed算法的权重。我们估计图4所示的邻域结构的亲和力/边权重。 为此，我们定义本地的吸引力和长程排斥边缘。这种结构的选择必须受到底层数据的激励-由于验证数据集的各向异性，我们更详细地说，我们选择了一个稀疏的面内排斥边缘环和额外的较长范围的面内边缘，这是可靠地分割区域所必需的（见图4a）。我们还添加了与下部相邻切片中的间接邻居的连接，以确保正确的3D连接（参见图4b）。总的来说，为每个像素定义了C+吸引和C−排斥边，从而在网络中产生C++C−输出通道我们划分了互斥分水岭11（0，27）（-9，9）（-4，9）（0，9）（4、9）（9，9）(-9，第4页）（9，4）(-27，0）(-9，0）（9，0）(27、0）(-9，-4）（9，-4）(-9、-9）(-4、-9）（0，-9）（4，-9）（9，-9）（0，-27）吸引/排斥边缘到子集H+和H-，包含所有的边缘在一个特定偏移，吸引边：E+=SC+H+和排斥边类似。Cc子集H+和H-的每个元素对应于特定的信道预编码。C c由网络决定。我们进一步假设权重取值于[0，1]，并采用与第3节相同的吸引力/排斥力约定。有关网络架构和培训的更多详细信息，请参见补充1。在我们的实验中，我们挑选了一个子集的排斥边缘，通过使用2的步幅在XY平面，以避免偶尔非常厚的膜造成的文物。注意，步幅不应用于局部（吸引）边缘，而仅应用于长范围（排斥）边缘。(a) XY平面邻域，具有局部吸引边、具有近似半径9的稀疏排斥边和具有距离27的(b) 由于数据的高各向异性，我们将Z平面边缘限制为1.直接邻居有吸引力;间接邻居是排斥的。图4：互斥分水岭图中吸引（绿色）和排斥（红色）边的局部邻域结构。由于原点的点对称性，我们只能用神经网络预测一半的方向。4.2ISBI挑战ISBI 2012 EM分割挑战赛[28]是神经元分割挑战赛，参赛作品数量最多挑战数据包含两个体积，尺寸为1.5× 2× 2微米，分辨率为50× 4×4 nm/像素。地面实况被提供为二进制膜标签，其可以容易地被转换为2D而不是3D分割。为了训练3D模型，我们遵循[24]中描述的过程。测试卷具有私有的地面实况;结果可以提交到排行榜。基于适应性兰德分数（Rand-Score）和信息变化分数（VI-Score）[28]分别对每个2D切片进行评估12Wolf、Pape、Bailo ni、Rahaman、Kreshuk、Ko¨the和Hamprecht图5：应用于ISBI挑战测试数据的Mutex分水岭。有关更多图像以及与基线分割方法的详细比较，请参见补充章节2。我们将在提交时将该操作记录在表格的第3栏中，见表1a。这一点特别值得注意，因为它比保存其他顶级条目的方法更简单。与我们类似，他们依赖CNN来预测边界位置，但使用[24]中描述的复杂管道对其输出进行后处理，这涉及NP-hard分区步骤。此外，我们从网络预测开始比较基线后处理方法：两个分水岭变体（WS、WSDT）和一个多切割变体（MC-LOCAL）仅考虑短程预测。寿命多切（LMC）和另一个多切变体（MC-FULL）也使用长期预测。对于这些基线方法，我们仅为单个切片产生2D分割，因为3D结果较差（THRESH、WS、WSDT）或无法获得（MC、LMC）。相比之下，Mutex Watershed受益于3D分割。评价结果见表1b，基线方法和定性比较的更多详细信息见补充资料2。使用短距离和长距离连接性的三种方法的性能显著优于其他方法。有点令人惊讶的是，MWS的表现优于MC-FULL和LMC，这是基于NP-硬分区问题。这可能是由于后两种方法中缺乏3D信息（求解3D模型是不可行的）。4.3自然图像分割我们在伯克利分割数据集BSD500 [53]上进行了初步实验，以研究Mutex分水岭对自然图像的适用性3http://brainiac2.mit.edu/isbichallenge/leaders-board-new互斥分水岭13方法随机评分VI评分方法随机评分VI评分时间[s]UNet + MWS0.987920.99183 MWS0.987920.9918343.32M2FCN + LMC [51]0.987880.99072 MC-FULL0.980290.990449415.8SCN + LMC [52]0.986800.99144 LMC0.979900.99007966.0FusionNet + LMC [30]0.983650.99130 THRESH0.914350.969610.2ICv1 + LMC [24]0.982620.98945 WSDT0.883360.963124.4(a) 提交时的前五个条目。我们的互斥分水岭（MWS）是国家的最先进的，而不依赖于复杂的解除多切后处理使用的所有其他顶级条目。MC-LOCAL0.709900.868741410.7WS0.639580.892374.9(b) 与其他分割策略进行比较，所有这些策略都基于我们的CNN。表1：ISBI 2012 EM细分挑战的结果在这个小数据集上训练最先进的边缘检测网络需要一组特定于数据集的优化技巧，例如使用外部数据，多分辨率架构和辅助损失进行训练[43]。 在这项初步研究中，我们训练了用于ISBI实验的2D版本的网络，以预测图4a中所示的2D连接模式。为了缓解训练集的小规模，我们提出了这个网络，其中[42]的预测作为额外的输入通道。为了隔离潜在亲和力的质量的影响，我们运行消融实验，其中我们在以下各项之间插值（通过加权平均）：(a) 由我们的神经网络预测的亲和力，（b）从地面实况获得的亲和力和（c）均匀噪声。我们从BSD测试集的内插亲和力中获得Mutex分水岭图6a中示出了由这些指数构成的“相变图”;图6 b示出了针对该图上的观察到对应于（a）和（c）的顶点可以（分别）被解释为地面真实亲和度上的结构化和非结构化噪声。因此，我们的实验结果表明，互斥分水岭是相当强大的对这两种类型的噪音;当GT与噪声混合时，分割的质量不受高达60%噪声的影响。当将GT与NN预测混合时，它甚至在更高的程度上不受影响。此外，我们与[22]的结果进行了比较，[22]使用与我们类似的方法，并基于从预先计算的概率图中提取的长程势来求解提升多切在补充3中，我们示出了在GT、NN预测和噪声之间的不同插值阶段产生的14Wolf、Pape、Bailo ni、Rahaman、Kreshuk、Ko¨the和HamprechtNNGT噪声RIVI百分百0%的百分比0%的百分比0.826 1.7220%的百分比百分百0%的百分比0.901 0.9270%的百分比百分之三十八百分之六十二0.897 0.9760%的百分比百分之三十三百分之六十六0.820 1.912百分之八十百分之二十0%的百分比0.878 1.247百分之四十三0%的百分比百分之五十七0.813 2.127百分之四十三百分之十四百分之四十三0.838 1.636(a) MWS算法的BSD 500分割质量，给定来自地面实况（上角）、来自神经网络（右角）或纯噪声（左角）的亲和力;再加上对上述加权组合的数百次实验。MWS分割质量（用Rand指数评估）仅在大量噪声被添加到亲和力时才会降低。Keuper等人[22] 0.82 1.75(b) 神经网络预测（NN）之间各种插值的BSD 500得分地面实况（GT）和噪声。参见补充部分3，例如内插亲和力的图像。我们包括[22]作为参考点，因为他们在分割方法中也使用长程电位。5结论本文提出了一种同时具有吸引边和排斥边的图的快速聚类算法。考虑这两种情况的能力消除了对停止标准或甚至种子的需要，除了相关聚类之外，所有流行的算法都需要停止标准或种子。所提出的方法具有较低的计算复杂度，在它的封闭性的关系，Kruskal的算法。最后，我们已经发现，所提出的算法，当从一个良好的神经网络的信息的边缘成本，优于所有已知的方法上的竞争力的生物图像分割基准，包括方法，在非常相同的网络预测。在未来的工作中，我们希望将我们的算法推广到自然图像分割挑战中常见的语义实例分割[54，55，56]。6确认作者承认DFG HA 4364/8-1和DFG SFB 1129的部分支持。互斥分水岭15引用1. 文森特湖Soille，P.：数字空间中的流域：一种基于沉浸模拟的高效算法。IEEE Trans.模式分析机器智能（6）（1991）58 32. Beucher，S.，Meyer，F.：分割的形态学方法：水-OpticalEngineRingg34（1992）4333. Grimaud，M.：对比度的新测量方法：动态。在警局盖德E. R. Dougherty ， J.C. Serra 编 ： 图 像 代 数 与 形 态 学 处 理。 第 1769 卷 ，SPIEConf。 是的。（1992年）2924. Beucher，S.：分水岭、层次分割和瀑布算法。在：Pr oc. 我是MM' 94。第94章. （1994年）695. 瓦希尔角Meyer，F.：消光值：一种新的持久性测量方法。In：Worksh. 无限制签名和标记处理。 第1卷。（1995年）2546. Najman湖Schmitt，M.：分水岭轮廓的测地线显著性与分层分割。IEEETrans. Pattern Analysis and Machine Intelligence 18（12）（1996）11637. Soille，P.：层次图像分解和简化的约束连通性。 IEEETrans. PATT。Anal. Mach。 我告诉你。30（7）（2008）11328. Perret，B.，Cousty，J.，Guimaraes，S.J.，Maia，D.S.：等级流域评价。（2017）HAL预印本01430865。9. Meyer ， F. ： 形 态 学 多 尺 度 和 交 互 式 分 割 。 在 ： WS onNonlinearSignalandImagePr ocessing中。（1999年）36910. Najman ， L. ：层 次 分 割 与 超 矩 阵 分 割 的 等 价 性 。J.MathemalImangandVision40（3）（2011）23111. Salembier，P.，加里多，L.：二进制分割树是图像处理、分割和信息检索的有效表示方法.IEEE Trans. ImageProc. 9（2000）56112. Malmberg，F.， Strand，R.， Nystr¨om，I. ：一般来说，图形分割会产生复杂的图像。见：斯堪的纳维亚图像分析会议，Springer（2011）36-4713. Felzenszwalb，P.F.，Huttenlocher，D.P.：基于图的高效图像分割 Int. J.来吧。《美国专利法》59（2）（2004）16714. Arbelaez，P.，Maire，M.，福克斯角Malik，J.： 轮廓检测和分层图像片段。IEEETrans. PATT。 Anal. Mach。 我告诉你。33（5）（2011）89815. Kiran ， B.R. ， Serra ，J. ： 通过 分层 切割和 爬 网 的 全 局 局 部 优 化 。PatternRecogniti on47（1）（2014）1216. 还有B Kap pesJ. H、 Beer，T.， Kéothe，U.， Hamprecht，F. A. ：使用hclosednessscnstraints提供可靠的数据段。 在：Pr oc. ICCV' 11。 （2011）2611- 2618 1.17. 还有B Kr¨oger，T.， Briggmann，K. L.， Denk，W.， 不，不， 知道吗GKo¨the，U.， Hamprecht，F. A. ：全局最小化关闭的数据段，以用于集成。In：Pr oc. ECCV' 12，第2页。Number7574（2012）77818. Yarkony，J.，Ihler，A.，Fowlkes，C.C.：图像序列的快速平面相关聚类。In：Pr oc. ECCV' 12。（2012）56819. 佩普角Beier，T.，Li，P.，Jain，V.博克，D.D.，Kreshuk，A.：用区域分解法求解连通组的大型In：Proceedings of the IEEE ConferenceonComuterVisisinandPater nRecognitin. （2017）120. 张，C.，Yarkony，J.，Hamprecht，F.A.：使用相关聚类的细胞检测和分割。 In：Pr oc. MICCAI' 14。（2014）916Wolf、Pape、Bailo ni、Rahaman、Kreshuk、Ko¨the和Hamprecht21. H ornˇa´kova´，A.， Langge，J. H、 A andres，B. 通常，通过提升的多路复用来实现对多个分量的分组化。国际机器学习会议（InternationalConference on Machine Learning）（2017）15 3922. Keu per，M.， Levinkov，E.， Bonnee1，N.， 我来了，G.， Br ox，T.， Aandres，B. ：有效通过灵活的多个计算机来减少信息和数据存储的成本。 In：Pr oc. ICCV'15。（2015）1 7 51-175923. Beer，T.， Aandres，B.， Ko¨the，U.， Hamprecht，F. A. ：Anefficientfusionmoveelgo-最小代价提升多割问题的算法。In：European ConferenceonCommputerVision，Springer（2016）71524. Beier，T.，佩普角Rahaman，N.Prange，T.e.a.：Multicut带来自动化神经突分割更接近人类的表现。自然方法14（2）（2017）10125. Lee，K.，Zung，J.，Li，P.，Jain，V.Seung，H.S.：超人般的精准度snemi3d连接组学挑战。 arXiv预印本arXiv：1706.00120（2017）26. Jain，V. Murray，J.F. Roth，F.，Turaga，S.，Zhigulin，V.，Briggman，K.L.，赫尔姆-施泰特，医学博士，Denk，W.，Seung，H.S.：基于约束优化的图像恢复的监督学习。 Pr oc. ICCV27. Ciresan，D.C. Giusti，A.，Gambardella，L.M.，Schmidhuber，J.：深度神经网络-工作段的神经元网络是一个独立的电子计算机系统。 Pr o c. 02TheDog28. 阿尔甘达-卡雷拉斯岛Turaga，S.，Berger，D.等：众包创建图像分割算法。前面04 The Fantasy（2015）29. Ronneberger，O.，Fischer，P.，Brox，T.： U-Net：用于生物医学Ialimagesegmentati on. Pr oc. MICCAI30. Quan，T. M.，Hilderbrand，D.G.， Jeong，W.K.： FusionNet：一个用于连接组学图像分割的深度全残差卷积神经网络。1612.05360（2016）31. Nunez-Iglesias，J.，肯尼迪河Parag，T.，施，J.，Chklovskii，D.：机器学习的分层聚类分割2D和3D图像。PLoS one 8（2013）e7171532. Knowles-Barley，S.凯尼格琼斯T.R. Wilson，A.，Morgan，J. Lee，D.，Berger，D. Kasthuri，N. Lichtman，J.W.，Pfister，H.：RhoanaNet管道：密集自动神经注释。1611.06973（2016）33. Uzun bas ， M. G. ，Chen ， C. ，Metaxas ， D. ： OPTRE ： ALEAR NING-BASEDAPTIVETER-神经元分割脱落算法In：Int.Conf. 医学图像计算和计算机辅助设计（Medical Image Computing andC〇mputer-Assiste dIte ri nt e r i t i n terin ti t i n ti n t i n t i t i n t i t i n t i n t i n）（MICCA1（2014）9734. Meirovitch，Y.，Matveev，A.，Saribekyan，H.，Budden，D.Rolnick，D.气味G琼斯S.K.B.T