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