Graphics Reference
In-Depth Information
That is, if node
i
should have label 0, we want
E
data
(
L
(
i
)
=
0
)
to be low and
E
data
(
L
(
i
)
=
1
to be high. Thus wewant theweight of the edge attaching node
i
to the source (label
0) to be high and the weight of the edge attaching node
i
to the sink (label 1) to be
low, so that the edge to the sink is cut and node
i
remains attached to the source.
In this section, we briefly describe how to compute the
minimum cut
on such a
graph — that is, a subset of edges
)
C
E
such that if we remove these edges from
, there
is no path from
S
to
T
in the resulting subgraph, and the subset
C
minimizes the cost
|
C
|=
w
ij
(A.13)
(
i
,
j
)
∈
C
The key concept is to transform the minimum cut problem to a
maximum flow
problemon the graph. That is, we think of the edgeweights as capacities for transport-
ing material (e.g., water), and want to determine the maximum amount of material
the maximum flow, the set of edges at full capacity corresponds to the minimum cut
(and the cost of this cut corresponds to the maximum amount of material that can be
flowed).
Computing the maximum flow is a well-studied problem in combinatorial opti-
mization, and one of the main approaches is called the
Ford-Fulkerson
method,
which at a high level operates as follows:
1. Initialize the flow along each edge
e
ij
to 0.
2. While there is still a path
p
from
along which we can push more flow,
add more flow along
p
until one of its edges is at capacity.
S
to
T
Themain issue is how to efficiently find goodpaths in Step 2 to reach themaximum
flow as quickly as possible. Cormen et al. [
106
] describe various classical approaches,
including the Edmonds-Karp algorithm, in which the augmenting path is the short-
est path from
in the residual network (i.e., a graph in which an edge appears
if it has unused capacity). From the perspective of computer vision problems, in
which the graphs have a typical, regularly connected structure, the most important
contribution was made by Boykov and Kolmogorov [
60
]. They used a pair of search
trees emanating from the source and the sink that explore non-saturated edges to
find augmenting paths, and efficiently reuse these trees in each step. Their algorithm
has superior performance on computer vision problems such as image segmenta-
tion and stereo compared to the leading maximum-flow algorithms. Many computer
vision researchers use Kolmogorov's publicly available maximum-flow/minimum-
cut implementation
(
http://vision.csd.uwo.ca/code/
)
, which was also incorporated
into Szeliski et al.'s common interface for minimizing energies over Markov Random
Fields (see the previous section).
Many Gibbs energy problems require more than two labels at a node, and the
algorithm used previously can't be directly applied. For example, in Section
5.5.2
we discussed the problem of stereo correspondence, in which the labels correspond
S
to
T
4
Maximum flow problems generally require the graph to be directed, not undirected; this is
addressed by creating a directed graph that has two opposing directed edges
i
→
j
and
j
→
i
in
place of every edge
in the original undirected graph. Each directed edge is given the same
weight as the original undirected edge.
(
i
,
j
)
