Chapter 37Graph Cuts for Energy Minimization and Assignment Problems

Graph cuts have numerous applications in computational structural biology. In this chapter, we introduce a generalized Potts energy model in the Markov Random Field (MRF) framework, and present a multiway graph cut algorithm to find the minimum energy [1]. Then, we present an Ξ±\alpha -expansion move algorithm to compute visual correspondence with occlusions [2]. Graph cuts provide an algorithm for a wide variety of assignment problems.

Some of these assignment problems first arose in machine vision. We review these vision problems since image processing arises often in computational biology. However, graph cuts also have broader applications, as we shall see. This chapter builds on the MRF concepts introduced in chapter 25.

Construction of the Energy Function

Markov Random Fields (MRFs) An image is an array of pixels connected in a grid topology. Suppose that we are given two images. A pixel in one image is said to correspond to a pixel in the other if these two pixels are projections along lines of sight from the same physical scene element [2]. In the visual correspondence problem, we can regard the pixels in the second image as labels, and our goal is to compute a β€œlabel” fpf_p , which denotes a disparity value, for each pixel pp in the primary image. Let fpf_p denote the disparity at pixel pp , and 𝒩p\mathcal{N}_p denote the set of the neighbors of pp . In a Markov Random Field (MRF) framework, we have

Pr⁡(fp|fq,pβ‰ q)=Pr⁡(fp|fq,qβˆˆπ’©p).\Pr(f_p | f_q, p \neq q) = \Pr(f_p | f_q, q \in \mathcal{N}_p).

Hammersley-Clifford Theorem Let f=(f1,…,fm)f = (f_1, \dots, f_m) denote a configuration of all mm pixels 𝒫={1,…,m}\mathcal{P} = \{1, \dots, m\} . If we focus on the MRF framework, with a clique potential VV , we have

Pr⁡(f)∝exp⁡(βˆ’βˆ‘pβˆˆπ’«βˆ‘qβˆˆπ’©pV(p,q)(fp,fq)).(37.1)\Pr(f) \propto \exp \left( - \sum_{p \in \mathcal{P}} \sum_{q \in \mathcal{N}_p} V_{(p,q)}(f_p, f_q) \right). \quad (37.1)

f*=argmaxfPr⁡(f|O),f^* = \underset{f}{\operatorname{argmax}} \Pr(f | O), where OO denotes the observed data. By Bayes’ rule, we have

f*=argmax⁡fPr⁡(O|f)β‹…Pr⁡(f),f^* = \operatorname{argmax}_f \Pr(O|f) \cdot \Pr(f), where Pr⁡(O|f)β‹…Pr⁡(f)\Pr(O|f) \cdot \Pr(f) is also called the posterior probability; Pr⁡(f)\Pr(f) is the prior probability, obtained from equation (37.1), and Pr⁡(O|f)=∏pβˆˆπ’«gp(O|fp)\Pr(O|f) = \prod_{p \in \mathcal{P}} g_p(O|f_p) is called the likelihood probability,1 which also represents the sensor noise model.

Energy Minimization We wish to find a configuration ff that minimizes the posterior energy function:

E(f)=βˆ’βˆ‘pln⁡gp(O|fp)+βˆ‘(p,q)V(p,q)(fp,fq).(37.2)E(f) = - \sum_p \ln g_p(O|f_p) + \sum_{(p,q)} V_{(p,q)}(f_p, f_q). \quad (37.2)

The Generalized Potts Model In a Generalized Potts Model MRF (GPM-MRF), a clique potential for any pair of neighboring pixels pp and qq is defined by

V(p,q)(fp,fq)=u{p,q}⋅δ(fp≠fq),V_{(p,q)}(f_p, f_q) = u_{\{p,q\}} \cdot \delta(f_p \neq f_q), where δ(fp≠fq)=1\delta(f_p \neq f_q) = 1 if fp≠fqf_p \neq f_q , δ(fp≠fq)=0\delta(f_p \neq f_q) = 0 otherwise, and u{p,q}u_{\{p,q\}} denotes the penalty for discontinuity at pair (p,q)(p, q) . The posterior energy function of a GPM-MRF is

E(f)=βˆ’βˆ‘pln⁡gp(O|fp)+2βˆ‘(p,q)u{p,q}β‹…Ξ΄(fpβ‰ fq).(37.3)E(f) = - \sum_p \ln g_p(O|f_p) + 2 \sum_{(p,q)} u_{\{p,q\}} \cdot \delta(f_p \neq f_q). \quad (37.3)

Optimizing the Energy Function by Graph Cuts

Graph Construction

Given a set of pixels 𝒫={1,…,m}\mathcal{P} = \{1, \dots, m\} and a set of labels β„’={l1,…,lk}\mathcal{L} = \{l_1, \dots, l_k\} , we construct a graph G=(V,E)G = (V, E) such that V=𝒫βˆͺβ„’V = \mathcal{P} \cup \mathcal{L} and the edge set EE is constructed in the following way. Any two neighboring vertices in 𝒫\mathcal{P} are connected by an edge, called an nn -link. Each nn -link between pixels pp and qq is assigned a weight:

w{p,q}=2u{p,q}.w_{\{p,q\}} = 2u_{\{p,q\}}.

A vertex pp in 𝒫\mathcal{P} is connected to a vertex ll in β„’\mathcal{L} if lβˆˆβ„’pl \in \mathcal{L}_p . Each edge (p,l)(p, l) is called tt -link, which is assigned a weight:

w{p,l}=ln⁡gp(O|l)+K(p)+βˆ‘qβˆˆπ’©pw{p,q},w_{\{p,l\}} = \ln g_p(O|l) + K(p) + \sum_{q \in \mathcal{N}_p} w_{\{p,q\}}, where K(p)K(p) denotes some constant for each pixel pp .

1 Here, gg is the sensor noise distribution.

Figure 37.1 (plate 41)

An example of multiway graph cut. Dashed lines in (b) denote the cut edges in the graph [1]. Copyright 1998 IEEE.

Figure 37.1a shows an example of such a constructed graph.

The Multiway Cut Formulation

A subset of edges CβŠ‚EC \subset E in a graph G=(V,E)G = (V, E) is a multiway cut if the terminals (label vertices) are separated in the induced graph G=(V,Eβˆ’C)G = (V, E - C) . Figure 37.1 (plate 41) shows a multiway cut example in a graph. The cost of a cut CC , denoted by |C||C| , is equal to the sum of weights of all cut edges. The multiway cut problem is to find a multiway cut with the minimum cost.

Theorem If CC is a multiway cut with the minimum cost, then the corresponding configuration fCf^C (see section 37.3.3) minimizes E(f)E(f) in equation (37.3).

The Multiway Cut Algorithm

A special case of the multiway cut problem, in which there are only two terminals, is a standard min-cut problem and can be solved in polynomial time using the max-flow (Ford-Fulkerson) algorithm. The general multiway cut problem in which there are more than two labels is NP-complete. Currently, efficient approximation algorithms exist that are optimal within a factor of 2. The following algorithm (algorithm 1) is applied to find the minimum cut for a given graph:

Algorithm 1

  1. 1: Start with an arbitrary multiway cut CC from any pair of terminals.
  2. 2: while CC improves do
  3. 3: Β Β for all pairs of labels ll and Ξ»\lambda do
  4. 4: Β Β Β Β Find sβˆ’ts-t min cut on G{l,Ξ»}G_{\{l,\lambda\}} .
  5. 5: Β Β Β Β Update CC if a better new cut is found.
  6. 6: Β Β end for
  7. 7: end while
  8. 8: Return CC .

Graph Cuts for Computing Visual Correspondence with Occlusions

Notation

Computing Visual Correspondence Suppose that we are given two images. A pixel in one image is said to correspond to a pixel in the other if these two pixels are projections along lines of sight from the same physical scene element [2]. In the visual correspondence problem, we can regard the pixels in the second image as labels, and our goal is to compute a β€œlabel” fpf_p , which denotes a disparity value, for each pixel pp in the primary image. In other words, the visual correspondence problem can be formulated into a GPM-MRF. The reader is referred to section 4 in Boykov et al.Β [1] for more implementation details.

Occlusion Problem In a visual correspondence problem, some pixels may be visible only in one image, but occluded in the other one. Hence, there is no correspondence for these pixels (or β€œlabels”) in the other image.

Ξ±\alpha -Expansion Move Let d(a)=(qxβˆ’px,qyβˆ’py)d(a) = (q_x - p_x, q_y - p_y) denote the disparity of an assignment a=⟨p,q⟩a = \langle p, q \rangle . In an Ξ±\alpha -expansion move operation, some currently active assignments are deleted, and some assignments with disparity Ξ±\alpha are added.

Energy Function

The basic idea of designing the energy function here is to construct an energy model on assignments so that the graph cut algorithms can be applied. Here each vertex in a graph represents an assignment between two corresponding pixels, while in the previous section (37.2), each vertex in the graph denotes a pixel in the image.

Given a configuration ff of pixel assignments (or correspondences) between two images, the energy function incorporating the occlusion correspondences is defined by

E(f)=Edata(f)+Eocc(f)+Esmooth(f),(37.4)E(f) = E_{data}(f) + E_{occ}(f) + E_{smooth}(f), \quad (37.4) where EdataE_{data} denotes the intensity difference between corresponding pixels, and EoccE_{occ} denotes a penalty for an occluded pixel, and EsmoothE_{smooth} denotes a smoothness between two neighboring assignments. More specifically, these three terms are designed as follows (we use the same terminology as in section 3.2 from Kolmogorov and Zabih [2]):

  1. Edata=βˆ‘a∈A(f)D(a)E_{data} = \sum_{a \in A(f)} D(a) , where D(a)=(I(p)βˆ’I(q))2D(a) = (I(p) - I(q))^2 denotes the disparity of an assignment a=⟨p,q⟩a = \langle p, q \rangle , and I(p)I(p) denotes the intensity of pixel pp .
  2. Eocc(f)=βˆ‘all pixels pCpβ‹…T(|Np(f)|=0)E_{occ}(f) = \sum_{\text{all pixels } p} C_p \cdot T(|N_p(f)| = 0) , where CpC_p denotes a penalty if pixel pp is occluded, and Np(f)N_p(f) denotes the set of active assignments involving pixel pp , and T(β‹…)T(\cdot) is 1 if its argument is true, and 0 otherwise.
  3. Esmooth(f)=βˆ‘{a1,a2}βˆˆπ’©Va1,a2β‹…T(f(a1)β‰ f(a2))E_{smooth}(f) = \sum_{\{a_1, a_2\} \in \mathcal{N}} V_{a_1, a_2} \cdot T(f(a_1) \neq f(a_2)) , where 𝒩\mathcal{N} denotes the neighborhood system.

  1. Start with an arbitrary unique configuration ff
  2. Set success :=0:= 0
  3. For each disparity Ξ±\alpha
    1. 3.1. Find fΜ‚=arg⁡min⁡E(fβ€²)\hat{f} = \arg \min E(f') among unique fβ€²f' within single Ξ±\alpha -expansion of ff
    2. 3.2. If E(fΜ‚)<E(f)E(\hat{f}) < E(f) , set f:=fΜ‚f := \hat{f} and success :=1:= 1
  4. If success = 1 goto 2
  5. Return ff

Figure 37.2 The Ξ±\alpha -expansion move algorithm [2].

The Ξ±\alpha -Expansion Move Algorithm

Overview of the Algorithm The algorithm to find the configuration with the minimum energy is described in figure 37.2. The key step in the expansion algorithm is to find the configuration fΜ‚\hat{f} with smallest energy within a single Ξ±\alpha -expansion move. This step is implemented by constructing a weighted graph such that the minimum graph cut is equal to the configuration with the minimum energy. The following section shows how to construct the desired graph and compute the minimum cut.

Graph Construction Let f0f^0 denote the starting configuration. Let AΜƒ=π’œ0βˆͺπ’œΞ±\tilde{A} = \mathcal{A}^0 \cup \mathcal{A}^\alpha denote the set of all possible assignments within one Ξ±\alpha -expansion move, where π’œ0={aβˆˆπ’œ|d(a)β‰ Ξ±}\mathcal{A}^0 = \{a \in \mathcal{A} | d(a) \neq \alpha\} and π’œΞ±={aβˆˆπ’œ|d(a)=Ξ±}\mathcal{A}^\alpha = \{a \in \mathcal{A} | d(a) = \alpha\} . Now we construct a directed graph where nodes are all assignments in AΜƒ\tilde{A} plus two terminal nodes ss and tt , and edges are constructed according to the following rules:

  1. For every vertex a∈AΜƒa \in \tilde{A} , edges (s,a)(s, a) and (a,t)(a, t) are constructed.
  2. Edges (a1,a2)(a_1, a_2) and (a2,a1)(a_2, a_1) are constructed if {a1,a2}βˆˆπ’©\{a_1, a_2\} \in \mathcal{N} .
  3. Edges exist between assignments a1=⟨p,q⟩a_1 = \langle p, q \rangle and a2=⟨p,r⟩a_2 = \langle p, r \rangle , where qβ‰ rq \neq r .

Figure 37.3 shows an example of a constructed graph. The weights assigned for all edges are shown in table 37.1.

Graph Cuts Given a cut π’ž=𝒱s,𝒱t\mathcal{C} = \mathcal{V}^s, \mathcal{V}^t on 𝒒\mathcal{G} , the configuration fπ’žf^\mathcal{C} corresponding to the cut π’ž\mathcal{C} is defined by

βˆ€aβˆˆπ’œ0faπ’ž={1,if aβˆˆπ’±s0,if aβˆˆπ’±t\forall a \in \mathcal{A}^0 \quad f_a^\mathcal{C} = \begin{cases} 1, & \text{if } a \in \mathcal{V}^s \\ 0, & \text{if } a \in \mathcal{V}^t \end{cases}

Figure 37.3 An example of a constructed graph to find the minimum energy within one Ξ±\alpha -expansion move. (a) β„’={p,q,r,s}\mathcal{L} = \{p, q, r, s\} and β„›={w,x,y,x}\mathcal{R} = \{w, x, y, x\} denote two original images. Solid lines represent the current active assignments, and dashed lines represent the assignments after an Ξ±\alpha -expansion move (here Ξ±=2\alpha = 2 ). (b) Vertices in the top row represent the assignments in set π’œ0\mathcal{A}^0 , and vertices in the bottom row represent the assignments in π’œΞ±\mathcal{A}^\alpha . The number associated with each edge represents the rule order applied. The edges from rule 1 are not shown here [2]. Copyright 2001 IEEE.

Table 37.1 Assigned weights for all edges [2]

Edge Weight For
(s,a)(s, a) Docc(a)D_{occ}(a) aβˆˆπ’œ0a \in \mathcal{A}^0
(a,t)(a, t) Docc(a)D_{occ}(a) aβˆˆπ’œΞ±a \in \mathcal{A}^\alpha
(a,t)(a, t) D(a)+Dsmooth(a)D(a) + D_{smooth}(a) aβˆˆπ’œ0a \in \mathcal{A}^0
(s,a)(s, a) D(a)D(a) aβˆˆπ’œΞ±a \in \mathcal{A}^\alpha
(a1,a2),(a2,a1)(a1, a2), (a2, a1) Va1,a2V_{a1,a2} {a1,a2}βˆˆπ’©,a1,a2βˆˆπ’œΜƒ\{a1, a2\} \in \mathcal{N}, a1, a2 \in \tilde{\mathcal{A}}
(a1,a2)(a1, a2) ∞\infty pβˆˆπ’«,a1βˆˆπ’œ0,a2βˆˆπ’œΞ±,a1,a2∈Np(fΜƒ)p \in \mathcal{P}, a1 \in \mathcal{A}^0, a2 \in \mathcal{A}^\alpha, a1, a2 \in N_p(\tilde{f})
(a2,a1)(a2, a1) CpC_p pβˆˆπ’«,a1βˆˆπ’œ0,a2βˆˆπ’œΞ±,a1,a2∈Np(fΜƒ)p \in \mathcal{P}, a1 \in \mathcal{A}^0, a2 \in \mathcal{A}^\alpha, a1, a2 \in N_p(\tilde{f})

βˆ€aβˆˆπ’œΞ±faC={1,if aβˆˆπ’±s0,if aβˆˆπ’±t\forall a \in \mathcal{A}^\alpha \quad f_a^C = \begin{cases} 1, & \text{if } a \in \mathcal{V}^s \\ 0, & \text{if } a \in \mathcal{V}^t \end{cases}

βˆ€aβˆ‰π’œ0faC=0.\forall a \notin \mathcal{A}^0 \quad f_a^C = 0.

The following theorem shows that the minimum cut of a constructed graph is equal to the unique configuration with the minimum energy within one Ξ±\alpha -expansion move.

Theorem [2] Let π’ž\mathcal{C} be the minimum cut on 𝒒\mathcal{G} . Then fCf^C is the unique configuration that minimizes the energy EE within one Ξ±\alpha -expansion move of f0f^0 .

The minimum cut of the graph can be computed by using the Ford-Fulkerson algorithm in polynomial time.

Comments What is the difference between the graph cut algorithm and the other methods for assignment, such as the EM or bipartite matching approach?

Exercise The pixel assignment problem can be generalized to the NMR resonance and NOE assignment problems by first generalizing the grid network to have a more general graph neighborhood topology. What is the best algorithm you can obtain for these NMR problems? Analyze the complexity of your algorithm. Compare to EM and bipartite matching. Will graph cuts be more, or less robust than bipartite matching? Explain. Implement and test your algorithm, using both synthetic and real NMR data.

References

  • [1] Yuri Boykov, Olga Veksler, Ramin Zabih. Markov Random fields with efficient approximations. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (1998). Santa Barbara, CA.
  • [2] V. Kolmogorov and R. Zabih. Computing visual correspondence with occlusions using graph cuts. Proceedings of the Eighth International Conference on Computer Vision (ICCV-01) 2001, Vancover, British Columbia.