Graph Cut & Energy Minimization Yevgeny Doctor IP Seminar 2008, IDC Outline Motivation Graph Cuts Energy Minimization in Computer Vision Solving Energy Minimization with Graph Cuts Results Yevgeny Doctor, March 2008, IDC 2 Graph Cut

G(V,E) is a finite directed graph and every edge (u,v) has a capacity c(u,v) (a non-negative real number). Assume two vertices, the source s and the sink t, have been distinguished. A cut is a split of the nodes into two sets S and T, such that s is in S and t is in T. s t Yevgeny Doctor, March 2008, IDC

3 Min-Cut The capacity of a cut (S,T ) is defined as c S , T c x, y xS yT Min-Cut finding the cut with the minimal capacity Yevgeny Doctor, March 2008, IDC 4 Max Flow

Find the maximum flow from s to t Yevgeny Doctor, March 2008, IDC 5 Min-Cut Max-Flow Min-Cut and Max-Flow are equivalent problems Fast polynomial algorithms for max flow exist For example: Ford-Fulkerson algorithm O(E*maxflow) Edmonds-Karp algorithm O(VE2)

Yevgeny Doctor, March 2008, IDC 6 Energy Minimization Problems In general terms, given some problem, we: Formulate the known constraints Build an energy function (aka cost function) Look for a solution that minimizes it If we have no further knowledge: The problem can be NP-Hard (requires exponential solution time)

Use slow, generic approximation algorithms for optimization problems (such as simulated annealing) Yevgeny Doctor, March 2008, IDC 7 EM in Computer Vision Consider a broad class of problems called Pixel Labeling Given some images we want to say something about the pixels For each pixel p, give it a label fp from a finite set of labels L,

such that we minimize some energy function. Many applications Image Segmentation Image Restoration Stereo and Motion Medical Imaging Multicamera Scene Reconstruction Yevgeny Doctor, March 2008, IDC 8 Pixel Labeling Example

"Graph Cut Matching In Computer Vision", Toby Collins, February 2004 http://homepages.inf.ed.ac.uk/rbf/CVonline/ Yevgeny Doctor, March 2008, IDC 9 EM in Computer Vision Consider a specific family of Energy Functions Powerful enough to formulate many useful problems Can be reduced to solving a graph min-cut problem Problems defined with these functions: Can

be solved quickly (using max-flow algorithms) In many cases optimal solution or within a known factor of the optimum Yevgeny Doctor, March 2008, IDC 10 Energy Function Definition E f D f V f , f p p

p p ,q p q p , qN Edata(f) Esmooth(f) Input: set of pixels P, set of labels L, N P P is a neighbourhood system on pixels. Goal: find a labeling f : P L that minimizes E f . D

. p f p is a function derived from the observed data that measures the cost of assigning label f p to pixel p. V . p ,q f p , f q measures the cost of assigning the labels f p , f q to adjacent pixels p, q. Used to impose spatial smoothness. Yevgeny Doctor, March 2008, IDC 11 Energy Function - Edata Component The Edata(f) component: Look at each pixel independently Given its current value, what would it cost to label it with each of the labels?

Examples: Cost based on a-priori known pixel intensity or color distribution 2 f p i p , i p is the observed intensity of pixel p What if we used only this component in E(f)? Label each pixel independently with the most likely (cheap) label

Yevgeny Doctor, March 2008, IDC 12 Optimizing Edata Only Illustration What would be the problem? For example (object segmentation): Images from Nearest Neighbor lecture here for illustration purposes only We need to add a smoothness cost Yevgeny Doctor, March 2008, IDC 13 Energy Function - Esmooth Component

Look at all pairs of neighbor pixels Penalize adjacent pixels with different labels What smoothness cost function to use? Noised diamond image Fast Approximate Energy Minimization via Graph Cuts Yuri Boykov, Olga Veksler, Ramin Zabih Yevgeny Doctor, March 2008, IDC 14 Smoothness Cost Functions

Potts Interaction Penalty: E smooth f K T f p f q p , qN indicator function, K constant The solution will be piecewise constant, with discontinuities at the boundaries T Fast Approximate Energy Minimization via Graph Cuts March 2008, IDC Yuri Boykov, OlgaYevgeny Veksler, Doctor, Ramin Zabih 15 Smoothness Cost Functions

L2 distance: Esmooth f f p fq p ,qN What is the problem? High penalties at object boundaries We want smooth objects, but allow different labels at object boundary a discontinuity-preserving function. Yevgeny Doctor, March 2008, IDC 16

Smoothness Cost Functions Truncated L2 distance: E smooth f min K , f p f q p ,qN constant The solution will be piecewise smooth, with discontinuities at the boundaries K Fast Approximate Energy Minimization via Graph Cuts March 2008, IDC Yuri Boykov, OlgaYevgeny Veksler, Doctor,

Ramin Zabih 17 Smoothness Cost Functions Normalize for neighbor distance, image contrast: 2 T f p f q I I p q

E smooth f p , qN dist p , q exp 2 2 This

function penalizes a lot for discontinuities between pixels of similar intensities when |Ip Iq| < . However, if pixels are very different, |Ip Iq| > , then the penalty is small. Yevgeny Doctor, March 2008, IDC 18 Solving Energy Minimization with Graph Cuts Many classes of Energy Minimization problems in Computer Vision can be reduced to Graph Cuts Solve multiple-labels problems with binary decisions

Yevgeny Doctor, March 2008, IDC 19 Approximate Energy Minimization Fast Approximate Energy Minimization via Graph Cuts. Yuri Boykov, Olga Veksler, Ramin Zabih, 1999 For two classes of interaction potentials V (Esmooth): V is semi-metric on a label space L if for every , :L V , V , 0

V , 0 is metric on L if in addition, triangle inequality holds: V , V , V , , , L V For example, truncated L2 distance and Potts Interaction Penalty are both metric. Yevgeny Doctor, March 2008, IDC 20 Solution for Semi-metric Class

Swap-Move algorithm: 1. Start with an arbitrary labeling f 2. Set success := 0 3. For each pair of labels , L 3.1. Find f* = argmin E(f') among f' within one swap of f 3.2. If E(f*) < E(f), set f := f* and success := 1 4. If success = 1 goto 2 5. Return f

swap: In the new labeling f, some pixels that were labeled in f are now labeled , and vice versa. Yevgeny Doctor, March 2008, IDC 21 Solve swap step with Graph Cut Graph: Fast Approximate Energy Minimization via Graph Cuts Yevgeny 2008, 1999 IDC

Yuri Boykov, Olga Doctor, Veksler, March Ramin Zabih, 22 Solve swap step with Graph Cut Cut and Labeling: Weights: Fast Approximate Energy Minimization via Graph Cuts Yevgeny 2008, 1999

IDC Yuri Boykov, Olga Doctor, Veksler, March Ramin Zabih, 23 Solution for Metric Class Expansion Move algorithm:

1. Start with an arbitrary labeling f 2. Set success := 0 3. For each label L 3.1. Find f* = argmin E(f') among f' within one expansion of f 3.2. If E(f*) < E(f), set f := f* and success := 1 4. If success = 1 goto 2 5. Return f expansion: In the new labeling some pixels change their label to . Yevgeny Doctor, March 2008, IDC 24

Expansion Move Algorithm Example: "What Energy Functions Can Be Minimized via Graph Cuts?", Vladimir Kolmogorov and Ramin Zabih, February 2004 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 26, NO. 2. Guaranteed approximation ratio by the algorithm: Produces a labeling f such that E f * E f 2k E f * , where f* is the global minimum and k Yevgeny Doctor, March 2008, IDC

max V , : . min V , : 25 Solve expansion step with Graph Cut Graph: Fast Approximate Energy Minimization via Graph Cuts Yevgeny 2008, 1999 IDC Yuri Boykov, Olga Doctor, Veksler, March Ramin Zabih,

26 Solve expansion step with Graph Cut Cut and Labeling: Weights: FastYevgeny Approximate Energy Minimization via Graph Cuts Doctor, March

2008, IDC Yuri Boykov, Olga Veksler, Ramin Zabih, 1999 27 Experimental Results Three energy functions: Truncated quadratic semi-metric (swap-move): E1 f p i p min K , 2

pP Potts p ,qN model metric (-expansion): E 2 f p i p 2 pP Truncated K T f

p fq p ,qN L2 distance metric (-expansion): E3 f p i p 2 pP f p fq 2

min K , f p fq p ,qN Compared with: Best Doctor, March 2008, IDC 28 simulatedYevgeny annealing algorithm Convergence Rate

Fast Approximate Energy Minimization via Graph Cuts Yuri Boykov, Olga Veksler, Ramin Zabih, 1999 Yevgeny Doctor, March 2008, IDC 29 Image Restoration Fast Approximate Energy Minimization via Graph Cuts Yuri Boykov, Olga Veksler, Ramin Zabih, 1999 Yevgeny Doctor, March 2008, IDC 30 Motion and Stereo

Fast Approximate Energy Minimization via Graph Cuts Yuri Boykov, Olga Veksler, Ramin Zabih, 1999 Yevgeny Doctor, March 2008, IDC 31 What Energy Functions Can Be Minimized via Graph Cuts? A precise characterization of the class of functions in F3 that can be minimized using graph cuts A general purpose graph construction for minimizing any function in this class

A necessary condition for any function of binary variables to be minimized via graph cuts. "What Energy Functions Can Be Minimized via Graph Cuts?", Vladimir Kolmogorov and Ramin Zabih, February 2004 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 26, NO. 2. Yevgeny Doctor, March 2008, IDC 32 What Energy Functions Can Be Minimized via Graph Cuts? Define general Energy Function classes: Given F2:

F3: F2 is contained in F3 "What Energy Functions Can Be Minimized via Graph Cuts?", Vladimir Kolmogorov and Ramin Zabih, February 2004 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 26, NO. 2. Yevgeny Doctor, March 2008, IDC 33 What Energy Functions Can Be Minimized via Graph Cuts?

Regular F2 functions: "What Energy Functions Can Be Minimized via Graph Cuts?", Vladimir Kolmogorov and Ramin Zabih, February 2004 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 26, NO. 2. Yevgeny Doctor, March 2008, IDC 34 What Energy Functions Can Be Minimized via Graph Cuts? Graph construction for F2: "What Energy Functions Can Be Minimized via Graph Cuts?", Vladimir Kolmogorov and Ramin Zabih, February 2004

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 26, NO. 2. Yevgeny Doctor, March 2008, IDC 35 What Energy Functions Can Be Minimized via Graph Cuts? Regular F3 functions: A function E of more than two variables is called regular if all projections of E of two variables are regular

And Generally: Let E be a function of binary variables. If E is not regular, then EDoctor, is not graph-representable. Yevgeny March 2008, IDC 36 GrabCut Interactive Foreground Extraction using Iterated Graph " "Cuts Carsten Rother, Vladimir Kolmogorov, Andrew Blake, 2004 Microsoft Research Cambridge, UK

Yevgeny Doctor, March 2008, IDC 37 GrabCut Yevgeny Doctor, March 2008, IDC 38 GrabCut Transparency: Yevgeny Doctor, March 2008, IDC 39

GrabCut Yevgeny Doctor, March 2008, IDC 40 Video Cutout "Video Object Cut and Paste" Yin Li, Jian Sun, Heung-Yeung Shum, 2005 Microsoft Research Asia Figure 1: Given a video (a) containing an opaque video object on a complicated background, our system can generate clear alpha mattes and foreground colors (b) for the video object, which can be pasted onto another background. Yevgeny Doctor, March 2008, IDC 41 Video Cutout

3D segmentation of spatio-temporal video volume Partition into foreground and background, while preserving temporal coherence Local refinement of initial segmentation Provide brush tools for the user to control the object boundary precisely wherever needed Apply coherent matting to extract the alpha mattes and foreground colors of the object based on the accurate binary segmentation result Yevgeny Doctor, March 2008, IDC 42 Video Cutout

Yevgeny Doctor, March 2008, IDC 43 Video Cutout Yevgeny Doctor, March 2008, IDC 44 Video Cutout Yevgeny Doctor, March 2008, IDC 45 Video Cutout

Figure 7: Clip #2, frame 27. (a) 3D graph cut result is shown by the overlaid dashed line. The flag is a rapidly deforming object, but 3D graph cut can apture the shape very well. (b) Dashed lines indicate the boundaries after both the local refinement and overriding operations. The white pixels record the actions of foreground brushing and the black pixels for background brushing. (c) coherence matting result pasted onYevgeny a blueDoctor, screen. March 2008, IDC 46