Fuzzy Connectedness Image Segmentation in Graph Cut Formulation: A Linear-Time Algorithm and a Comparative Analysis

Abstract

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 ℓ _∞ norm ∥F _P ∥_∞ 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 ∥F _P ∥ _q for q∈[1,∞]. Of these, the best known minimization problem is for the energy ∥F _P ∥₁, 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 ∥F _P ∥ _q , q∈[1,∞), is identical to that for ∥F _P ∥₁, when the original weight function w is replaced by w ^q. Thus, any algorithm GC_sum solving the ∥F _P ∥₁ minimization problem, solves also one for ∥F _P ∥ _q with q∈[1,∞), so just two algorithms, GC_sum and GC_max, are enough to solve all ∥F _P ∥ _q -minimization problems. We also show that, for any fixed weight assignment, the solutions of the ∥F _P ∥ _q -minimization problems converge to a solution of the ∥F _P ∥_∞-minimization problem (∥F _P ∥_∞=lim _q→∞∥F _P ∥ _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.

Appendix

Example A.1

For the energies ε _q and E _q,q with q∈(1,∞] it is possible that $\mathcal {P}_{\hat{\theta}_{\min }}^{F}(S,T)$ and $\mathcal {P}_{\theta_{\min}}^{H}(S,T)$ are disjoint and that $\bar{x}\in \mathcal {P}^{H}(S,T)$ associated with $x_{\min}\in \mathcal {P}_{\hat{\theta}_{\min}}^{F}(S,T)$ does not belong to $\mathcal {P}_{\theta_{\min}}^{H}(S,T)$.

Proof

Take C={s,c,d,t}, where s is a foreground seed and t is a background seed, that is, S={s} and T={t}. Consider a graph on C with just three symmetric edges, {s,c}, {c,d}, and {d,t} (so, with six directed edges) with the respective weights 1, v, and v for v>1 to be determined. Then, $\mathcal {P}^{F}(S,T)$ consists of all fuzzy sets x _y,z :C→[0,1] with y,z∈[0,1], where x _y,z (s)=1, x _y,z (c)=y, x _y,z (d)=z, and x _y,z (t)=0.

First fix a q∈(1,∞). Then, E _q,q (x _y,z )=2[(1-y)^q+v ^q|y-z|^q+v ^q z ^q] is a function of two variables, y and z. It has precisely one minimum⁹ at z _q =(v ^q/(q-1)+2)^-1 and y _q =2(v ^q/(q-1)+2)^-1. Thus, $\mathcal {P}_{\hat{\theta}_{\min}}^{F}(S,T)=\{x_{y_{q},z_{q}}\}$, leading to $x_{\min}=x_{y_{q},z_{q}}$. Now, if v∈(1,2^(q-1)/q), then 1<v ^q/(q-1)<2 and we have 0<z _q <0.5<y _q <1, leading to $\bar{x}$ with $\bar{x}(s)=\bar{x}(c)=1$ and $\bar{x}(d)=\bar{x}(t)=0$. But this implies that $E_{q,q}(\bar{x})=v^{q}>1=E_{q,q}(\mbox {\raise .48ex\hbox {$\chi $}$_{\{s\}}$})$, so indeed $\bar{x}\notin \mathcal {P}_{\theta_{\min}}^{H}(S,T)$.

To see that the same example works for q=∞, fix a v∈(1,2^1/2). Then, for every q>2 and y,z∈ℝ, we have $\|F(x_{y,z})\|_{q}\geq\|F(x_{y_{q},z_{q}})\|_{q}$. Taking the limit, as q→∞, gives $\|F(x_{y,z})\|_{\infty}\geq \|F(x_{y_{\infty},z_{\infty}})\|_{\infty}$, where z _∞=lim _q→∞ z _q =(v+2)^-1 and y _∞=2z _∞. Then, similarly as above, $\mathcal {P}_{\theta_{\min}}^{F}(S,T)=\{x_{y_{\infty},z_{\infty}}\}$, leading to $x_{\min}=x_{y_{q},z_{q}}$ and $\bar{x}$ with $\bar{x}(s)=\bar{x}(c)=1$ and $\bar{x}(d)=\bar{x}(t)=0$. But this implies that ${\varepsilon }_{\infty}(\bar{x})=v>1={\varepsilon }_{\infty}(\mbox {\raise .48ex\hbox {$\chi $}$_{\{s\}}$})$, so once again $\bar{x}\notin \mathcal {P}_{\theta_{\min}}^{H}(S,T)$. □

Proof of Theorem 4.6

We start with proving that $P^{IFT}_{S,T}\in \mathcal {F}_{M}(S,W)$. Let ${\mathbb{F}}$ be the OPF returned by $\mbox {GC$_{\max }$}$, so that we have $P^{IFT}_{S,T}=P(S,{\mathbb{F}})$. We will find an MSF $\hat{{\mathbb{F}}}$ relative to W which returns the same object, that is, such that $P(S,\hat{{\mathbb{F}}})=P(S,{\mathbb{F}})$.

Recall, that the Kruskal’s algorithm creates MSF $\hat{{\mathbb{F}}}={\langle }C,\hat{E}{\rangle}$ as follows:

• it lists all edges of the graph in a queue Q such that their weights form a decreasing sequence;

• it removes consecutively the edges from Q, adding to $\hat{E}$ those, whose addition creates in the expanded $\hat{{\mathbb{F}}}={\langle}C,\hat{E}{\rangle}$ neither a cycle nor a path between different spels from W; other edges are discarded.

This schema has a leeway in choosing the order of the edges in Q: those that have the same weight can be ordered arbitrarily.

Let B be the boundary of $P(S,{\mathbb{F}})$, $B=\mathrm {bd}(P(S,{\mathbb{F}}))$. Assume, that we create the list Q in such a way that, among the edges with the same weight, all those that do not belong to B precede all those that belong to B. We will show that Kruskal’s algorithm with Q so chosen, indeed returns MSF $\hat{{\mathbb{F}}}$ with $P(S,\hat{{\mathbb{F}}})=P(S,{\mathbb{F}})$.

Clearly, by the power of Kruskal’s algorithm, the returned $\hat{{\mathbb{F}}}={\langle}C,\hat{E}{\rangle}$ will be MSF relative to W. We will show that $\hat{E}$ is disjoint with B. This easily implies the equation $P(S,\hat{{\mathbb{F}}})=P(S,{\mathbb{F}})$.

To prove that $\hat{E}$ is disjoint with B, choose an edge e={c,d}∈B. Consider the step in Kruskal’s algorithm when we remove e from Q. We will argue, that adding e to the already existing part of $\hat{E}$ would add a path from S to T, which implies that e would not be added to $\hat{E}$.

Let p _c and p _d be the paths in ${\mathbb{F}}$ from W to c and d, respectively. By symmetry, we can assume that $c\in V\setminus P(S,{\mathbb{F}})=P(T,{\mathbb{F}})$ and $d\in P(S,{\mathbb{F}})$. We will first show that

$$ \mu(p_c)\geq w_e \quad\mbox{and}\quad \mu(p_d)\geq w_e.$$

(19)

Indeed, if μ(p _c )>μ(p _d ), then w _e ≤μ(p _d ), since otherwise μ(d,S)=μ(p _d )<min{μ(p _c ),w _e }≤μ(d,T), implying that d belongs to the RFC object $P_{T,S}\subset P(T,{\mathbb{F}})$, which is disjoint with $P(S,{\mathbb{F}})$. Similarly, if μ(p _c )<μ(p _d ), then w _e ≤μ(p _c ), since otherwise μ(c,T)=μ(p _c )<min{μ(p _d ),w _e }≤μ(c,S), implying that c belongs to the RFC object $P_{S,T}\subset P(S,{\mathbb{F}})$. Finally, assume that μ(p _c )=μ(p _d ). Then w _e <μ(p _c )=μ(p _d ), since otherwise GC_max (during the execution of lines 6–8 for c and d) would reassign d to $P(T,{\mathbb{F}})$, which is disjoint with $P(S,{\mathbb{F}})$. So, (19) is proved.

Next, let E′={e′∈E:w _e′≥w _e }∖B. Then, every edge in E′ is already considered by the Kruskal’s algorithm by the time we remove e from Q. In particular, $\hat{E}\cap E'$ is already constructed. We claim, that there is a path $\hat{p}_{d}$ in $\hat{G}={\langle}C,\hat{E}\cap E'{\rangle}$ from S to d.

Indeed, the component of d in $\hat{G}$ must intersect S, since otherwise there is an edge $\hat{e}$ in p _d (so, in E′) only one vertex of which intersects this component. But this means that $\hat{e}\in E'$ would have been added to $\hat{E}$, which was not the case. So, indeed, there is a path $\hat{p}_{d}$ in $\hat{G}$ from S to d. Similarly, there is a path $\hat{p}_{c}$ in $\hat{G}$ from T to c. But this means that adding e to $\hat{E}$ would create a path from S to T, which is a forbidden situation. Therefore, indeed, Kruskal’s algorithm discards e, what we had to prove. This completes the argument for $P^{IFT}_{S,T}\in \mathcal {F}_{M}(S,W)$.

The inclusion $\mathcal {F}_{M}(S,W)\subset \mathcal {F}^{IRFC}(S,W)$ is proved in [2, Proposition 8]. Thus, to finish the proof, we need to show that $\mathcal {F}_{M}(S,W)\subset \mathcal {P}_{\theta}(S,T)$. So, fix a $P\in \mathcal {F}_{M}(S,W)$. Then, there is an MSF ${\mathbb{F}}={\langle }C,E'{\rangle}$ with respect to W for which $P=P(S,{\mathbb{F}})$. Clearly, $P=P(S,{\mathbb{F}})\in \mathcal {P}(S,T)$. So, to finish the proof, it is enough to show that ε ^max(P)≤θ _min=μ(S,T).

By way of contradiction, assume that this is not the case. Then, there exists an edge e={c,d}∈E with $c\in P=P(S,{\mathbb{F}})$ and $d\in V\setminus P=P(T,{\mathbb{F}})$ for which w _e >θ _min=μ(S,T). Let p _c and p _d be the paths in ${\mathbb{F}}$ from W to c and d, respectively. Then either μ(p _c )<w _e or μ(p _d )<w _e , since otherwise the path p starting with p _c , followed by e, and then by p _d is a path from S to T with μ(p)=w _e >μ(S,T), a contradiction.

Assume that μ(p _c )<w _e . Then p _c ={〈}c ₁,…,c _k 〉 with k>1 and the edge e′={c _k-1,c _k } has weight ≤μ(p _c )<w _e . But then $\hat{{\mathbb{F}}}={\langle}C,\hat{E}{\rangle}$ with $\hat{E}=E'\cup \{e\}\setminus\{e'\}$ is a spanning forest rooted at W with $\sum_{e\in\hat{E}} w(e)=\sum_{e\in E'} w(e)+w_{e}-w_{e'}>\sum _{e\in E'}w(e)$, what contradicts maximality of ${\mathbb{F}}$. This completes the proof of the theorem. □