Graph Cut
&
Energy Minimization
Yevgeny Doctor
IP Seminar 2008, IDC
Yevgeny Doctor, March 2008, IDC 2
Outline
Motivation
Graph Cuts
Energy Minimization in Computer Vision
Solving Energy Minimization with Graph Cuts
Results
Yevgeny Doctor, March 2008, IDC 3
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.
t
s
Yevgeny Doctor, March 2008, IDC 4
Min-Cut
The capacity of a cut (S,T ) is defined as
Min-Cut – finding the cut with the minimal capacity
Sx Ty
yxcTSc ,,
Yevgeny Doctor, March 2008, IDC 5
Max Flow
Find the maximum flow from s to t
