图像分割外文翻译.docVIP

4 算法和他的特点 在本章中，我们描述了一种利用上文中所描述的的准则的分割算法。我们将展示一个分割结果，这个结果是根据下面的定义服从既不柔和也的性质的算法所计算出的。 定义1 如果有一对区域，期间没有边界依据，则说明分割结果太过过度。 为了定义补充概念什么是分割结果太过柔和（区域划分的太少），我们首先介绍一下分割提纯的概念。我们设2个同一基础集的分割结果和，当中的每一个区域都包含于（或者等于）中的区域，那么我们成为的提纯。另外，当不等于时，我们称为的一种适当的提纯。注意如果是的适当提纯，那么可以通柔和分裂的区域得到。当是的适当提纯，那么就比更过度，则比更柔和。 定义2 当分割结果的一个适当提纯不太过度时，那么我们称太过柔和。 这样我们获得了直观的概念，如果一个分割结果的区域仍然能够再分并且分割结果中邻域有边界依据，那么这个最初的分割结果就被当做分成太少的区域了。 两个自然问题伴随着分割结果既不柔和也不过度的情况出现了，也就是这样的分割结果是否存在，或者它是否是独一无二的。首先，我们注意到通常都会有不止一个的既不柔和也不过度的分割结果，所以这种分割结果并不是独一无二的。关于存在性的问题，在我们的实验中，总会有既不过度也不柔和的分割结果存在。 特性1 对于任何有限的图，总会存在既不柔和也不过度的分割结果。 拥有这种特性还是显而易见的。设一个分割结果中所有的元素均在一个单独的部分之内。很明显，这个分割结果就太过过度了，因为只有一个组成部分。如果我们所设的分割结果也不太柔和。否则，通过定义什么是柔和，我们得知它一定有一个适当提纯是不太过度的。挑选出一个适当提纯并且重复这个过程直到获得一个不柔和的分割结果。这个过程只能运行步，因为无论我们挑选哪一个适当提纯我们都至少给分割结果中的区域数目增加了1个，而我们能得到的最好的分割结果就是所有元素都在自己的区域之内。 我们现在来看看这种分割的算法，这是和Kruskal最小生成树算法是密切联系的。他能以的时间复杂度实现，为图中边得数目。 算法1 分割算法 输入是图，包含有个结点和条边。输出是将分割成不同的部分。 将分以不减的权值顺序分类成 从一种分割方式开始，其中每一个顶点都在自己的部分之内 重复步骤3，。 根据建立。令与表示在顺序中与第条边相连接的两个结点，例如，。如果和位于中解体的部分，并且比两部分的类内差异都要小，那么将两部分合并，否则什么也不做。更正式的，让为中包含的部分，为包含的部分。如果并且，那么则是通过合并和得来。否则。 返回值为 我们现在通过算法1建立了一种分割，它在运用区域对比准则（在第3中定义）遵守既不过度也不柔和的全局特征。虽然这种算法产生了贪婪选择，但是它满足了全局的特征。并且，我们验证了在步骤1中得到的任何的不减的边得权值排列顺序都可以得到相同的分割结果。 引理1 在算法的第三步中，当考虑到边时，如果两个明显差异的部分经过计算而且没有合并；那么这2部分中的一个一定在最终的分割结果之中。当这条边被算法计算过之后，令和表示由所连接的2个部分。那么或者，其中在最终的分割结果中为包含的部分，为包含的部分。 证明。存在着两种导致合并不能发生的情况。这是因为。因为边的权值是根据不减的顺序排列的，这样没有额外的合并会在这个部分内发生，例如，。的情况也是类似的。 注意引理1意味着引起两个区域合并的边一定是这2个区域之间拥有最小权值的。这样引起合并的边一定会被Kruskal算法所选中来构建每一部分的最小生成树。 定理 1 算法1所产生的分割结果根据定义1在运用区域对比准则时不会过度。 证明。由定义可知，为了使不过度，存在着一些成对的准则没有控制的区域。这些成对区域中至少有一条边在步骤3中进行了计算并且没有引起合并。令为顺序中的第一条边。这样算法将不会将和合并，因为。通过引理1，我们得知不是就是。无论那一种都有，这就表明控制着和，这与已知是矛盾的。 定理2 算产生的分割结果根据定义2在运用区域对比准则时不会太柔和。 证明。为了使过于柔和，一定要存在一个适当提纯，而是不过度的。设最小权值边在区域内部，但却连接着2个明显差异的部分。注意通过提纯的定义得出。 因为并不过度，或者)或者避免普遍性损失的同时，我们得到前者是真实的。通过构建连接和部分其他下面分支时会拥有至少和一样大的权值，这样又大于中最大的权值，因为。这样本算法，因为设所有边得权值为不减顺序，所有会先调用中的边，然后调用从出发到的其他部分的边。所有在形成之前一定已经形成，而在形成的同时一定将和的分支部分进行合并。引起合并的权值一定至少和一样大。然而，本算法在的情况下是不会合并的，这也是矛盾的。 定理3 算法1所产生的分割结果不会受边的权值的不减顺序所影响。 令和为不减权值顺序中相邻的并且拥有相同权值的2条边。很清楚当算