Chapter 38Classifying the Power of Graph Cuts for Energy Minimization

We now continue our discussion of graph cuts, which were introduced in the previous chapter. In this chapter, we discuss an energy minimization framework using a spatially coherent clustering of feature space, which is a popular approach to image segmentation in the field of computer vision [1]. We then discuss the use of graph cut techniques for energy minimization, and finally give a characterization of the energy functions that can be minimized efficiently using graph cuts [2]. Energy minimization problems are ubiquitous in computational biology, and graph cuts provide an elegant and efficient paradigm that has already proven useful in computer vision, and which shows significant promise in structural biology and biophysics. We attack assignment problems since these energy minimization problems arise naturally in image processing and NMR.

Feature Space Clustering

Feature Space A feature space is characterized by a set of pixels where with each pixel a set of local properties (called “features”) is associated. Features such as intensity, texture, or motion are the commonly studied parameters. Since these properties are local properties, the feature vector of each pixel is a vector of local properties in a high dimensional space.

Feature Space Clustering Since significant features are shared by many pixels, the feature space is clustered and each pixel is labeled with the cluster that contains its feature vector. This is a popular approach for image segmentation problems arising in computer vision.

Spatial Coherence Since a good cluster in feature space is not necessarily coherent in image space, and the correct segmentation in image space may not correspond to a highly distinctive group of feature vectors, it is important that feature space clustering/segmentation algorithms should yield spatially coherent clusters (i.e., corresponding to compact groupings of pixels).

Energy Minimization Framework for Feature Space Clustering

The Pixel Labeling Problem

Input The input image has a set of pixels 𝒫={1,2,…,n}\mathcal{P} = \{1, 2, \dots, n\} .

𝒳\mathcal{X} is the feature space with dd dimensions.

Each pixel p∈𝒫p \in \mathcal{P} corresponds to a feature vector xp∈𝒳x_p \in \mathcal{X} .

The feature space is summarized by a set of KK models, such that each model kk describes a cluster in 𝒳\mathcal{X} and has some model parameter θk\theta_k .

Let θ={θ1,…,θk}\theta = \{\theta_1, \dots, \theta_k\} be the entire set of clusters.

Output It is required to compute the parameter set θ\theta and the labeling f:𝒫→{1,2,…,K}f : \mathcal{P} \rightarrow \{1, 2, \dots, K\} , that is, ff assigns each pixel pp to a model fp∈{1,2,…,K}f_p \in \{1, 2, \dots, K\} . Obviously, a cluster can be viewed as either a set of pixels Pk(f)={p∣fp=k}P_k(f) = \{p \mid f_p = k\} , or as a set of points in the feature space Xk(f)={xp∣p∈Pk(f)}X_k(f) = \{x_p \mid p \in P_k(f)\} .

The feature space clustering is done in such a way that the following criteria (quality measure) are satisfied:

  • Good cluster quality in feature space, that is, low intracluster variation and/or high intercluster variation. Call this measure QQ .
  • Spatial coherence in image space, that is, the labeling ff should be spatially coherent.

Let Q(f,θ)=Q(f, \theta) = cost of assigning the label fpf_p to the pixel pp (called assignment cost).

Let V(fp,fq)=V(f_p, f_q) = cost of assigning the labels fpf_p and fqf_q to adjacent pixels pp and qq . (This is called separation cost.)

Let 𝒩⊂𝒫×𝒫\mathcal{N} \subset \mathcal{P} \times \mathcal{P} be a neighborhood system on pixels that incorporates spatial coherence.

Then, the pixel labeling problem can be formulated as an energy minimization problem where the energy function has the following form:

E(f,θ)=Q(f,θ)+∑p,q∈𝒩V(fp,fq).(38.1)E(f, \theta) = Q(f, \theta) + \sum_{p, q \in \mathcal{N}} V(f_p, f_q). \quad (38.1)

Note that here QQ is the penalty of assigning a particular pixel to a particular cluster and VV imposes the penalty for assigning two different clusters to two neighboring pixels. VV is a robust metric in the space of clusters.

The goal is to minimize the overall penalty, that is, to minimize the energy function in equation (38.1).

An EM-Style Energy Minimization Algorithm

We now give an expectation/maximization (EM) algorithm for this energy minimization problem. The energy function in equation (38.1) can be minimized iteratively as follows:

Step 1: E Step Fix the cluster parameter θ\theta and find the best labeling ff .

Step 2: M Step Fix the labeling ff and find the best clusters θ\theta .

Step 3: Repeat until some convergence criterion is satisfied.

Fixing the cluster parameter θ\theta , the energy function looks like

E(f)=∑p∈𝒫Dp(fp)+∑p,q∈𝒩V(fp,fq),(38.2)E(f) = \sum_{p \in \mathcal{P}} D_p(f_p) + \sum_{p, q \in \mathcal{N}} V(f_p, f_q), \quad (38.2) where Dp(fp)D_p(f_p) is the assignment cost of the pixel pp and is related to QQ by the following equation:

Q(f)=∑p∈𝒫Dp(fp).(38.3)Q(f) = \sum_{p \in \mathcal{P}} D_p(f_p). \quad (38.3)

Fixing the clusters θ\theta , if for the function QQ , equation (38.3) is satisfied for some DpD_p , then QQ is called linear. Equation (38.3) is referred to as the linearity criterion.

The energy function in equation (38.2) can be minimized efficiently for a wide range of choices of VV using the α\alpha -expansion move algorithm (refer to chapter 37), which is based on the idea of graph cuts.

The M step is done by fixing the labeling ff and then optimizing for the cluster parameters θ\theta . Following are different clustering methods that are used here:

Parametric Clustering Method Here the idea is to maximize the posterior probability

Pr⁡(f,θ|x)∼Pr⁡(x|f,θ)⋅Pr⁡(f),\Pr(f, \theta|x) \sim \Pr(x|f, \theta) \cdot \Pr(f), where ff and θ\theta are assumed to be independent and θ\theta has a uniform prior distribution. The likelihood term on ff is given by the expression Pr⁡(x|f,θ)=∏p∈𝒫Pr⁡(xp|θfp)\Pr(x|f, \theta) = \prod_{p \in \mathcal{P}} \Pr(x_p|\theta_{f_p}) and the prior term is given by Pr⁡(f)=exp⁡(−∑p,q∈𝒩V(fp,fq))\Pr(f) = \exp\left(-\sum_{p, q \in \mathcal{N}} V(f_p, f_q)\right) . Taking the negative logarithm, the clustering objective function becomes

Q(f,θ)=∑p∈𝒫−log⁡Pr⁡(xp|θfp),(38.4)Q(f, \theta) = \sum_{p \in \mathcal{P}} -\log \Pr(x_p|\theta_{f_p}), \quad (38.4) which meets the linearity criterion. Note that this model of clustering is a generalization of the finite mixture model (FMM) and is justified under the Markov Random Field (MRF) framework.

Nonparametric Clustering Method Here the idea is to represent a cluster kk as a set of points in the feature space XkX_k .

Let Pr⁡(x|Xk)\Pr(x|X_k) be an estimate of the distribution in the cluster kk .

Then we can write the following expression for QQ in light of equation (38.4):

Q(f,θ)=∑p∈𝒫−log⁡Pr⁡(xp|Xfp(f)),(38.5)Q(f, \theta) = \sum_{p \in \mathcal{P}} -\log \Pr(x_p|X_{f_p}(f)), \quad (38.5) where (as we have already defined) Xk(f)X_k(f) is the set of features of pixels with the label kk under the labeling ff .

It is important to note that although this clustering method does not meet the linearity criterion (equation 38.3), it works well in practice with the α\alpha -expansion move algorithm.

Approaches to Incorporating Spatial Coherence

Several approaches have been proposed to incorporate positional information as a feature in the feature space analysis. They can be summarized as follows:

Super Pixel Approach The idea is to preprocess and compute feature vectors from the preprocessed segments, rather than computing them directly from pixels. This approach fails when superpixels cross the boundaries of object.

Extensions to EM Style Algorithm The idea is to use an EM style algorithm with additional constraints. This approach suffers from not being able to impose spatial coherence efficiently.

Soft Membership Clustering Here the feature vectors are labeled with a probability distribution over clusters rather than hardwired to one cluster, an approach justified within the framework of Markov Random Fields. This makes the M step more effective. But the drawback of this approach is that computing soft membership is computationally intractable under MRF.

Use of Hard Membership with Graph Cuts This is the approach described in Zabih and Kolmogorov [1]. Hard membership implies that each feature vector belongs to exactly one cluster. The advantage with this approach is that it facilitates the use of graph cut-based energy minimization methods, which have tremendous success in energy minimization in the context of pixel labeling problems in stereo vision.

Classifying Energy Functions that Can Be Minimized Efficiently Using Graph Cuts

Consider the study of computational problems in early vision, which can often be expressed as an energy minimization problem over a very high dimensional space. In general, the energy minimization function can be a nonconvex function, which is often very difficult to minimize. Recently, graph cut-based techniques have been proved to be very useful and can minimize the energy functions to give solutions with promising theoretical bounds. A natural question comes to mind: “How can we classify energy functions that can be efficiently minimized by using the graph cut technique?” The paper [2] answers this fundamental question, by classifying energy functions according to their ability to be represented as a graph such that they can be minimized efficiently. A general-purpose graph construction is also given for each class of energy functions, that minimizes any energy function in that class.

In computational biology, energy minimization is a ubiquitous, yet difficult and expensive task, which is a subroutine in many protocols. Hence, new insights about the properties of energy functions are valuable, and graph cuts provide new tools for their classification.

Figure 38.1 Schematic of the graph cut technique. Here, the cuts are labelings and the cost of a cut represents the energy. Credit: Chittu Tripathy and Bruce Donald.

38.4.1 Using Graph Cuts in Energy Minimization

A standard form of energy function is given by

E(f)=∑p∈𝒫Dp(fp)+∑p,q∈𝒩V(fp,fq),(38.6)E(f) = \sum_{p \in \mathcal{P}} D_p(f_p) + \sum_{p, q \in \mathcal{N}} V(f_p, f_q), \quad (38.6) where 𝒩⊂𝒫×𝒫\mathcal{N} \subset \mathcal{P} \times \mathcal{P} defines the neighborhood system of interaction, Dp(fp)D_p(f_p) denotes the assignment cost function, and V(fp,fq)V(f_p, f_q) is the separation cost function. This energy function was studied extensively in computer vision and the graph cut technique has been applied successfully to minimize such energy functions.

The general idea behind the graph cut technique is to construct a specialized graph for the energy function to be minimized, so that minimization of energy (locally or globally) corresponds to computing a minimum cut of the graph. Figure 38.1 illustrates the general framework for energy minimization using graph cuts.

38.5 Representation of Energy Functions by Graphs

Graph Representable Functions A function EE of nn binary variables is graph representable if there exists a graph 𝒢=(𝒱,ℰ)\mathcal{G} = (\mathcal{V}, \mathcal{E}) with terminal vertices ss and tt and a subset of vertices 𝒱0={v1,…,vn}⊂𝒱−{s,t}\mathcal{V}_0 = \{v_1, \dots, v_n\} \subset \mathcal{V} - \{s, t\} such that, for any configuration x1,x2,…,xnx_1, x_2, \dots, x_n , the value of the energy E(x1,x2,…,xn)E(x_1, x_2, \dots, x_n) is equal to a constant plus the cost of the minimum ss - tt -cut among all cuts C=S,TC = S, T in which vi∈Sv_i \in S , if xi=0x_i = 0 , and vi∈Tv_i \in T , if xi=1x_i = 1 (i≤i≤ni \leq i \leq n). We say that EE is exactly represented by 𝒢,𝒱0\mathcal{G}, \mathcal{V}_0 if this constant is zero.

Note that the addition of a constant does not change the minimum energy configuration.

This definition leads to the following result. If the energy function EE is graph representable by a graph 𝒢\mathcal{G} and a subset 𝒱0\mathcal{V}_0 , then it is possible to find the exact minimum of EE in polynomial time by computing the minimum ss - tt -cut on 𝒢\mathcal{G} .

Two important classes of energy functions called ℱ2\mathcal{F}^2 and ℱ3\mathcal{F}^3 in terms of graph representability are discussed in the following sections, which provide general procedures to construct graphs.

The Class ℱ2\mathcal{F}^2

The class ℱ2\mathcal{F}^2 is a subset of energy functions where each individual term can be expressed as a function of at most two Boolean variables.

Theorem 38.1 (ℱ2\mathcal{F}^2 Theorem) Let EE be a function of nn binary variables from the class ℱ2\mathcal{F}^2 , i.e.,

E(x1,…,xn)=∑iEi(xi)+∑i<jEi,j(xi,xj).(38.7)E(x_1, \dots, x_n) = \sum_i E^i(x_i) + \sum_{i < j} E^{i,j}(x_i, x_j). \quad (38.7)

Then EE is graph representable if and only if each term Ei,jE^{i,j} satisfies the following condition, called the regularity condition:

Ei,j(0,0)+Ei,j(1,1)−Ei,j(0,1)−Ei,j(1,0)≤0.(38.8)E^{i,j}(0, 0) + E^{i,j}(1, 1) - E^{i,j}(0, 1) - E^{i,j}(1, 0) \leq 0. \quad (38.8)

Note that functions of one Boolean variable are always regular.

Graph Construction for ℱ2\mathcal{F}^2

Construct a graph 𝒢=(𝒱,ℰ)\mathcal{G} = (\mathcal{V}, \mathcal{E}) as follows:

  • The vertex set 𝒱={v1,…,vn,s,t}=S∪T∪{s,t}\mathcal{V} = \{v_1, \dots, v_n, s, t\} = S \cup T \cup \{s, t\} , where viv_i encodes the Boolean variable xix_i , such that xi=0x_i = 0 if vi∈Sv_i \in S , and xi=1x_i = 1 if vi∈Tv_i \in T .
  • We write edge(v,c)edge(v, c) to mean an edge (s,v)(s, v) with the weight cc if c>0c > 0 or an edge (v,t)(v, t) with the weight −c-c if c<0c < 0 .
  • For each term Ei(xi)E^i(x_i) , add an edge (vi,Ei(1)−Ei(0))(v_i, E^i(1) - E^i(0)) . Refer to figure 38.2 a and b.
  • As figure 38.2 c, d, and e shows, for each term Ei,j(xi,xj)E^{i,j}(x_i, x_j) add the following three edges:
    • edge(vi,Ei,j(1,0)−Ei,j(0,0))edge(v_i, E^{i,j}(1, 0) - E^{i,j}(0, 0)) ,
    • edge(vj,Ei,j(1,1)−Ei,j(1,0))edge(v_j, E^{i,j}(1, 1) - E^{i,j}(1, 0)) , and
    • (vi,vj)(v_i, v_j) with weight −π(Ei,j)=Ei,j(0,1)+Ei,j(1,0)−Ei,j(0,0)−Ei,j(1,1)-\pi(E^{i,j}) = E^{i,j}(0, 1) + E^{i,j}(1, 0) - E^{i,j}(0, 0) - E^{i,j}(1, 1) . The function π(⋅)\pi(\cdot) is called the functional, which we formally define in section 38.7. Note that for regular functions of two variables, π(Ei,j)≤0\pi(E^{i,j}) \leq 0 .
  • Once the graph for each individual term is constructed, merge the graphs together to get the final graph. The merging is justified by the additivity theorem, which states that the sum of two graph representable functions is graph representable.

Each edge weight is made nonnegative by construction, which is important since we construct the graph to finally compute a min-cut of the graph.

Ei,j=Ei,j(0,0)Ei,j(0,1)Ei,j(1,0)Ei,j(1,1)ABCD=ABCDE^{i,j} = \frac{\begin{array}{c|c} E^{i,j}(0,0) & E^{i,j}(0,1) \\ \hline E^{i,j}(1,0) & E^{i,j}(1,1) \end{array}}{\begin{array}{c|c} A & B \\ \hline C & D \end{array}} = \begin{array}{c|c} A & B \\ \hline C & D \end{array}

Figure 38.2 Graph cuts for functions ℱ2\mathcal{F}^2 . (a) Shows the graphs for EiE^i where Ei(1)>Ei(0)E^i(1) > E^i(0) ; (b) shows the graphs for EiE^i where Ei(1)≤Ei(0)E^i(1) \leq E^i(0) ; in (c), the table shows the individual terms for the two variable function Ei,jE^{i,j} ; in (d) we show the third edge for Ei,jE^{i,j} ; (e) represents the complete graph for Ei,jE^{i,j} when C>AC > A and C>DC > D . Note that (e) shows one of the four possibilities [2].

NP-Hardness of General E2E^2 Functions

Theorem 38.2 Let E2E^2 represent an energy function of two variables that is not regular. Then, minimization of functions of the form

E(x1,…,xn)=∑iEi(xi)+∑(i,j)∈𝒩E2(xi,xj),(38.9)E(x_1, \dots, x_n) = \sum_i E^i(x_i) + \sum_{(i,j) \in \mathcal{N}} E^2(x_i, x_j), \quad (38.9) where EiE^i are arbitrary functions of one variable and 𝒩⊂{(i,j)∣1≤i<j≤n}\mathcal{N} \subset \{(i, j) \mid 1 \leq i < j \leq n\} , is NP-hard.

The Class ℱ3\mathcal{F}^3

Theorem 38.3 (ℱ3\mathcal{F}^3 Theorem) Let EE be a function of nn binary variables from the class ℱ3\mathcal{F}^3 , that is,

E(x1,…,xn)=∑iEi(xi)+∑i<jEi,j(xi,xj)+∑i<j<kEi,j,k(xi,xj,xk).(38.10)E(x_1, \dots, x_n) = \sum_i E^i(x_i) + \sum_{i < j} E^{i,j}(x_i, x_j) + \sum_{i < j < k} E^{i,j,k}(x_i, x_j, x_k). \quad (38.10)

Then EE is graph representable if and only if EE is regular.

The regularity condition in case of functions of three Boolean variables will be stated after introducing a few more concepts. We define the functional π\pi of an energy function E(x1,…,xn)E(x_1, \dots, x_n) to be a mapping from the set of all functions of Boolean variables to the set of all real numbers given by the following equation:

π(E(x1,…,xn))=∑x1,…,xn∈{0,1}(Πi=1n(−1)xi)E(x1,…,xn).(38.11)\pi(E(x_1, \dots, x_n)) = \sum_{x_1, \dots, x_n \in \{0, 1\}} (\Pi_{i=1}^n (-1)^{x_i}) E(x_1, \dots, x_n). \quad (38.11)

For example, π(E)=E(0,0)+E(1,1)−E(0,1)−E(1,0)\pi(E) = E(0, 0) + E(1, 1) - E(0, 1) - E(1, 0) for a two variable function EE . The functional π\pi is linear, i.e., π(E1+E2)=π(E1)+π(E2)\pi(E_1 + E_2) = \pi(E_1) + \pi(E_2) .

For a three-variable function Ei,j,kE^{i,j,k} we compute the functional as follows. We take all projections of two variables of Ei,j,kE^{i,j,k} (a projection means fixing the value of one variable and then computing Ei,j,kE^{i,j,k} , which can now be thought of as a function of two variables) with positive values of functional π\pi . If we don’t find such a projection, then Ei,j,kE^{i,j,k} is regular.

Graph Construction for ℱ3\mathcal{F}^3

Construct a graph 𝒢=(𝒱,ℰ)\mathcal{G} = (\mathcal{V}, \mathcal{E}) as follows:

  • The vertex set 𝒱={v1,…,vn,s,t}=S∪T∪{s,t}\mathcal{V} = \{v_1, \dots, v_n, s, t\} = S \cup T \cup \{s, t\} , where viv_i encodes the Boolean variable xix_i , such that xi=0x_i = 0 if vi∈Sv_i \in S , and xi=1x_i = 1 if vi∈Tv_i \in T .
  • We write edge(v,c)edge(v, c) to mean an edge (s,v)(s, v) with the weight cc if c>0c > 0 or an edge (v,t)(v, t) with the weight −c-c if c<0c < 0 .
  • For the terms in the forms Ei(xi)E^i(x_i) and Ei,j(xi,xj)E^{i,j}(x_i, x_j) , the edges are added as explained in the construction of the graph for ℱ2\mathcal{F}^2 . Refer to figure 38.2. We now construct the part of the graph where each term involves three Boolean variables, that is, the terms of the form Ei,j,k(xi,xj,xk)E^{i,j,k}(x_i, x_j, x_k) .
  • For each term Ei,j,k(xi,xj,xk)E^{i,j,k}(x_i, x_j, x_k) , add one extra vertex uijku_{ijk} in addition to the vertices vi,vj,vk,sv_i, v_j, v_k, s and tt . If π(Ei,j,k)≥0\pi(E^{i,j,k}) \geq 0 , then the following edges are added (see figure 38.3 b):
    • edge(vi,Ei,j,k(1,0,1)−Ei,j,k(0,0,1))edge(v_i, E^{i,j,k}(1, 0, 1) - E^{i,j,k}(0, 0, 1)) ,
    • edge(vj,Ei,j,k(1,1,0)−Ei,j,k(1,0,0))edge(v_j, E^{i,j,k}(1, 1, 0) - E^{i,j,k}(1, 0, 0)) ,
    • edge(vk,Ei,j,k(0,1,1)−Ei,j,k(0,1,0))edge(v_k, E^{i,j,k}(0, 1, 1) - E^{i,j,k}(0, 1, 0)) ,
    • (vj,vk)(v_j, v_k) with weight −π(Ei,j,k[x1=0])-\pi(E^{i,j,k}[x_1 = 0]) ,
    • (vk,vi)(v_k, v_i) with weight −π(Ei,j,k[x2=0])-\pi(E^{i,j,k}[x_2 = 0]) ,

Ei,j(0,0,0)E^{i,j}(0,0,0) Ei,j(0,0,1)E^{i,j}(0,0,1) AA BB
Ei,j(0,1,0)E^{i,j}(0,1,0) Ei,j(0,1,1)E^{i,j}(0,1,1) CC DD
Ei,j(1,0,0)E^{i,j}(1,0,0) Ei,j(1,0,1)E^{i,j}(1,0,1) EE FF
Ei,j(1,1,0)E^{i,j}(1,1,0) Ei,j(1,1,1)E^{i,j}(1,1,1) GG HH

Figure 38.3 Graph cuts for functions ℱ3\mathcal{F}^3 . (a) Shows the terms depending on three variables xi,xj,xkx_i, x_j, x_k . Here P=π(Ei,j,k)=(A+D+F+G)−(B+C+E+H)P = \pi(E^{i,j,k}) = (A + D + F + G) - (B + C + E + H) . (b) Represents the graph for the case when P≥0P \geq 0 . (c) Shows the graph for the case when P<0P < 0 [2].

  • ⋅(vi,vj)\cdot (v_i, v_j) with weight −π(Ei,j,k[x3=0])-\pi(E^{i,j,k}[x_3 = 0]) , and
  • ⋅(vi,uijk),(v2,uijk),(v3,uijk),(uijk,t)\cdot (v_i, u_{ijk}), (v_2, u_{ijk}), (v_3, u_{ijk}), (u_{ijk}, t) with weight π(Ei,j,k)\pi(E^{i,j,k}) .

If π(Ei,j,k)≤0\pi(E^{i,j,k}) \leq 0 then we add the following edges (see figure 38.3 c):

  • ⋅edge(vi,Ei,j,k(1,1,0)−Ei,j,k(0,1,0))\cdot edge(v_i, E^{i,j,k}(1, 1, 0) - E^{i,j,k}(0, 1, 0)) ,
  • ⋅edge(vj,Ei,j,k(0,1,1)−Ei,j,k(0,0,1))\cdot edge(v_j, E^{i,j,k}(0, 1, 1) - E^{i,j,k}(0, 0, 1)) ,
  • ⋅edge(vk,Ei,j,k(1,0,1)−Ei,j,k(1,0,0))\cdot edge(v_k, E^{i,j,k}(1, 0, 1) - E^{i,j,k}(1, 0, 0)) ,
  • ⋅(vk,vj)\cdot (v_k, v_j) with weight −π(Ei,j,k[x1=1])-\pi(E^{i,j,k}[x_1 = 1]) ,
  • ⋅(vi,vk)\cdot (v_i, v_k) with weight −π(Ei,j,k[x2=1])-\pi(E^{i,j,k}[x_2 = 1]) ,
  • ⋅(vj,vi)\cdot (v_j, v_i) with weight −π(Ei,j,k[x3=1])-\pi(E^{i,j,k}[x_3 = 1]) , and
  • ⋅(uijk,vi),(uijk,v2),(uijk,v3),(s,uijk)\cdot (u_{ijk}, v_i), (u_{ijk}, v_2), (u_{ijk}, v_3), (s, u_{ijk}) with weight −π(Ei,j,k)-\pi(E^{i,j,k}) .
  • Once the graphs for each individual term is constructed, merge the graphs together to get the final graph. The merging is justified by the additivity theorem.

Comments

The graph construction technique used for the class of functions in ℱ2\mathcal{F}^2 does not introduce any additional vertices in ℱ2\mathcal{F}^2 beyond necessity, and in the case of functions in the class ℱ3\mathcal{F}^3 , only one extra vertex for every ternary interaction term is introduced. This construction yields much smaller graphs and hence the minimum cut can be computed efficiently.

The graph cut technique using the above graph construction procedure is very powerful when applied to stereo and multicamera scene reconstruction. The usefulness of the technique is strongly supported by the experimental results.

Since ℱ2⊂ℱ3\mathcal{F}^2 \subset \mathcal{F}^3 , the class ℱ3\mathcal{F}^3 includes a larger class of functions that can be minimized using the graph cut framework.

Finally, it will be interesting to see how the graph cut technique can be applied in other areas of computational biology and molecular biophysics.

Exercise Are the pairwise energy functions commonly used for protein design in class ℱ2\mathcal{F}^2 or ℱ3\mathcal{F}^3 ? Compare and contrast both classes of functions, to those used in protein design.

Exercise Can you use graph cuts to model side-chain rotamer assignments, and thereby devise an efficient algorithm for computing the GMEC?

Exercise Can you use graph cuts to model NMR resonance assignments, and thereby devise an efficient algorithm for structure-based assignment?

References

[1] Ramin Zabih and Vladimir Kolmogorov. Spatially coherent clustering using graph cuts. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2, (2004):437–444.

[2] Vladimir Kolmogorov and Ramin Zabih. What energy functions can be minimized via graph cuts?. IEEE Transactions on Pattern Analysis and Machine Intelligent, 26;2(2004):147–159.