Fuzzy Connectedness Image Segmentation in Graph Cut Formulation: A Linear-Time Algorithm and a Comparative Analysis
Fuzzy Connectedness Image Segmentation in Graph Cut Formulation: A Linear-Time Algorithm and a Comparative Analysis
复制标题
DOI：
10.1007/s10851-012-0333-3
复制
发表时间：
2012-11-01
影响因子：
2
通讯作者：
Miranda, P. A. V.
中科院分区：
文献类型：
--
作者：
Ciesielski, Krzysztof Chris;Udupa, Jayaram K.;Miranda, P. A. V.
对本文提出的图割图像分割框架进行了深入的理论分析，同时在多个方向上做出了重要贡献，其中最重要的实际贡献是对一种新的功能强大的分割算法GC(Max)进行了全面的理论描述和实现。GC(Max)的输出与一种称为迭代相对模糊连通性(IRFC)的分割算法的版本一致。然而，GC(Max)算法比经典的IRFC算法要快得多，我们从理论上证明了这一点，并通过实验证明了这一点。具体地说，我们证明了，在最坏的情况下，GC(Max)算法相对于变量M=|C|+|Z|线性运行，其中|C|是图像场景大小，|Z|是相关权重/亲和度函数的允许范围Z的大小。对于大多数实施方式，Z与允许的图像强度值集相同，并且其大小相对于|C|可以被视为较小，这意味着O(M)=O(|C|)。在这种情况下，GC(Max)关于图像大小|C|以线性时间运行.我们证明了GC(Max)的输出构成了一个图割能量最小化问题的解，其中能量被定义为映射F(P)的a“”(A)范数F(P)Ayen(A)，它与来自对象P边界的每个元素e相关联，其权重w(E).这个公式将IRFC算法引入到图割能量最小化的领域，其中Qa[1，a]的能量函数为F(P)Ayen(Q)。其中，最著名的最小化问题是能量ayenF(P)Ayen(1)，它是通过经典的最小割/最大流算法(通常被称为图割算法)来求解的。我们注意到，当原始权函数w被w(Q)代替时，ayenF(P)Ayen(Q)的最小化问题Qa[1，a)与ayenF(P)Ayen(1)的最小化问题相同。因此，任何一个求解ayenF(P)Ayen(1)极小化问题的算法GC(Sum)都可以用Qa[1，a)来求解ayenF(P)Ayen(Q)的最小化问题，因此只需两个算法GC(Sum)和GC(Max)就足以解决所有的ayenF(P)Ayen(Q)-极小化问题。我们还证明了，对于任何固定的权重分配，ayenF(P)Ayen(Q)-最小化问题的解收敛于ayenF(P)Ayen(A)-最小化问题的解(ayenF(P)Ayen(A)=Lim(Q->；a)ayenF(P)Ayen(Q)不足以推论这一点)。这集中于比较实际(相对于可证明的最坏情况)算法的运行时间，以及种子选择对输出的影响。
A deep theoretical analysis of the graph cut image segmentation framework presented in this paper simultaneously translates into important contributions in several directions.The most important practical contribution of this work is a full theoretical description, and implementation, of a novel powerful segmentation algorithm, GC(max). The output of GC(max) coincides with a version of a segmentation algorithm known as Iterative Relative Fuzzy Connectedness, IRFC. However, GC(max) is considerably faster than the classic IRFC algorithm, which we prove theoretically and show experimentally. Specifically, we prove that, in the worst case scenario, the GC(max) algorithm runs in linear time with respect to the variable M=|C|+|Z|, where |C| is the image scene size and |Z| is the size of the allowable range, Z, of the associated weight/affinity function. For most implementations, Z is identical to the set of allowable image intensity values, and its size can be treated as small with respect to |C|, meaning that O(M)=O(|C|). In such a situation, GC(max) runs in linear time with respect to the image size |C|.We show that the output of GC(max) constitutes a solution of a graph cut energy minimization problem, in which the energy is defined as the a"" (a) norm ayenF (P) ayen(a) of the map F (P) that associates, with every element e from the boundary of an object P, its weight w(e). This formulation brings IRFC algorithms to the realm of the graph cut energy minimizers, with energy functions ayenF (P) ayen (q) for qa[1,a]. Of these, the best known minimization problem is for the energy ayenF (P) ayen(1), which is solved by the classic min-cut/max-flow algorithm, referred to often as the Graph Cut algorithm.We notice that a minimization problem for ayenF (P) ayen (q) , qa[1,a), is identical to that for ayenF (P) ayen(1), when the original weight function w is replaced by w (q) . Thus, any algorithm GC(sum) solving the ayenF (P) ayen(1) minimization problem, solves also one for ayenF (P) ayen (q) with qa[1,a), so just two algorithms, GC(sum) and GC(max), are enough to solve all ayenF (P) ayen (q) -minimization problems. We also show that, for any fixed weight assignment, the solutions of the ayenF (P) ayen (q) -minimization problems converge to a solution of the ayenF (P) ayen(a)-minimization problem (ayenF (P) ayen(a)=lim (q -> a)ayenF (P) ayen (q) is not enough to deduce that).An experimental comparison of the performance of GC(max) and GC(sum) algorithms is included. This concentrates on comparing the actual (as opposed to provable worst scenario) algorithms' running time, as well as the influence of the choice of the seeds on the output.