An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision.
After [15], [31], [19], [8], [25], [5], minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of this paper is to provide an experimental comparison of the efficiency of min-cut/max flow algorithms for applications in vision. We compare the running times of several standard algorithms, as well as a new algorithm that we have recently developed. The algorithms we study include both Goldberg-Tarjan style "push-relabel methods and algorithms based on Ford-Fulkerson style "augmenting paths. We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases, our new algorithm works several times faster than any of the other methods, making near real--time performance possible. An implementation of our max-flow/min-cut algorithm is available upon request for research purposes.
Introduction
Greig et. al. [10] were rst to discover that powerful min-cut/max-
ow algorithms
from combinatorial optimization can be used to minimize certain important
energy functions in vision. The energies addressed by Greig et. al. and by
most later graph based methods (e.g. [15, 12, 2, 11, 4, 1, 18, 13, 16, 17, 3, 14]) can
be represented as a posterior energy in MAP-MRF 1 framework:
(p;q)2N
Pg is a labeling of image P , D p () is a data penalty function,
V p;q is an interaction potential, and N is a set of all pairs of neighboring pixels.
Papers above show that, to date, graph based energy minimization methods
provide arguably the most accurate solutions for the specied applications.
stands for Maximum A Posterior estimation of a Markov Random Field.
Greig et.al. constructed a two terminal graph such that the minimum cost cut
of the graph gives a globally optimal binary labeling L in case of the Potts model
of interaction in (1). Previously, exact minimization of energies like (1) was not
possible and such energies were approached mainly with iterative algorithms
like simulated annealing. In fact, Greig et.al. used their result to show that in
practice simulated annealing reaches solutions very far from the global minimum
even in very simple image restoration examples.
Unfortunately, the result of Greig et.al. remained unnoticed for almost 10
years mainly because the binary labeling limitation looked too restrictive. In the
late 90's new computer vision techniques appeared that used min-cut/max-
ow
algorithms on graphs. [15] was the rst to use these algorithms to compute multi-camera
stereo. Later, [12, 2] showed that with the right edge weights on a similar
to [15] graph one can minimize the energy in (1) for linear interaction penalties.
The exact minimum could be computed when there are more than two labels.
The results in [2, 4] showed that iteratively running min-cut/max-
ow algorithms
on appropriate graphs can be used to nd provably good approximate solutions
for even more general multi-label case when interaction penalties are metrics.
A growing number of publications in vision use graph based energy minimization
techniques for applications like image segmentation [12, 18, 13, 3], restoration
reconstruction [16], object recognition [1], augmented
reality [17], and others. The graphs corresponding to these applications
are usually huge 2D or 3D grids, and min-cut/max-
ow algorithm e-ciency is
an issue that can not be ignored.
The goal of this paper is to compare experimentally the speed of several min-
cut/max-
ow algorithms on graphs typical for applications in vision. In Section 2
we provide basic facts about graphs, min-cut and max-
ow problems, and some
standard combinatorial optimization algorithms for them. Section 3 introduces a
new min-cut/max-
ow algorithm that we developed while working with graphs
in vision. In Section 4 we tested our new algorithm and three standard min-
cut/max-
ow algorithms: H PRF and Q PRF versions of Goldberg-style \push-
relabel" method [9, 5], and the Dinic algorithm [7]. We selected several examples
in image restoration, stereo, and segmentation where dierent forms of energy
(1) are minimized via graph structures originally described in [10, 12, 2, 4, 14, 3].
Such (or very similar) graphs are used in all computer vision papers known to
us that use graph cut algorithms. In many interesting cases our new algorithm
was signicantly faster than the standard min-cut/max-
ow techniques from
combinatorial optimization. More detailed conclusions are presented in Section 5.
2 Background on Graphs
In this section we review some basic facts about graphs in the context of energy
minimization methods in vision. A graph consists of a set of nodes V
and a set of directed edges E that connect them. Usually the nodes correspond
to pixels, voxels, or other features. A graph normally contains some additional
special nodes that are called terminals. In the context of vision, terminals correspond
to the set of labels that can be assigned to pixels. We will concentrate
on the case of graphs with two terminals. Then the terminals are usually called
the source, s, and the sink, t. In Figure 1(a) we show a simple example of a two
terminal graph (due to Greig et. al. [10]) that can be used to minimize the Potts
case of energy (1) on a 3  3 image with two labels. There is some variation in
the structure of graphs used in other energy minimization methods in vision.
However, most of them are based on regular 2D or 3D grid graphs as the one
in

Figure

1(a). This is a simple consequence of the fact that normal images (or
volume data) in vision have grid-like structures.
sink
source
s
source
sink
cut
s
(a) A graph G (b) A cut on G
Fig. 1. Example of a graph. Edge costs are re
ected by their thickness. This graph
construction was rst used in Greig et. al. [10].
All edges in the graph are assigned some weight or cost. A cost of a directed
edge (p; q) may dier from the cost of the reverse edge (q; p). Normally, there
are two types of edges in the n-links and t-links. N-links connect pairs
of neighboring pixels or voxels. Thus, they represent a neighborhood system in
the image. Cost of n-links corresponds to a penalty for discontinuity between
the pixels. These costs are usually derived from the pixel interaction term V p;q
in energy (1). T-links connect pixels with terminals (labels). The cost of a t-link
connecting a pixel and a terminal corresponds to a penalty for assigning the
corresponding label to the pixel. This cost is normally derived from the data
term D p in the energy function (1).
2.1 Min-Cut and Max-Flow Problems
An s=t cut (or just a cut) C on a graph with two terminals is a partitioning of
the nodes in the graph into two disjoint subsets S and T such that the source
s is in S and the sink t is in T . Figure 1(b) shows one example of a cut. In
combinatorial optimization the cost of a cut is dened as the sum of
the costs of \boundary" edges (p; q) where p 2 S and q 2 T . The minimum cut
problem on a graph is to nd a cut that has the minimum cost among all cuts.
One of the fundamental results in combinatorial optimization is that the
minimum s=t cut problem can be solved by nding a maximum
ow from the
source s to the sink t. Loosely speaking, maximum
ow is the maximum \amount
of water" that can be sent from the source to the sink by interpreting graph edges
as directed \pipes" with capacities equal to edge weights. The theorem of Ford
and Fulkerson [8] states that a maximum
ow from s to t saturates a set of edges
in the graph dividing the nodes into two disjoint parts fS; T g corresponding to
a minimum cut. Thus, min-cut and max-
ow problems are equivalent. In fact,
the maximum
ow value is equal to the cost of the minimum cut.
We can also intuitively show how min-cut (or max-
ow) on a graph may
help with energy minimization over image labelings. Consider an example in

Figure

1. The graph corresponds to a 3  3 image. Any s=t cut partitions the
nodes into disjoint groups each containing exactly one terminal. Therefore, any
cut corresponds to some assignment of pixels (nodes) to labels (terminals). If
edge weights are appropriately set based on parameters of an energy, a minimum
cost cut will correspond to a labeling with the minimum value of this energy. 2
2.2 Standard Algorithms in Combinatorial Optimization
An important fact in combinatorial optimization is that there are polynomial
algorithms for min-cut/max-
ow problems on graphs with two terminals. These
algorithms can be divided into two main groups: Goldberg-style \push-relabel"
methods and algorithms based on Ford-Fulkerson style augmenting paths.
Standard augmenting paths based algorithms, such as Dinic algorithm, work
by pushing
ow along non-saturated paths from the source to the sink until the
maximum
ow in the graph G is reached. A typical augmenting path algorithm
stores information about the distribution of the current s ! t
ow f among the
edges of G using a residual graph G f . The topology of G f is identical to G but
capacity of an edge in G f re
ects the residual capacity of the same edge in G
given the amount of
ow already in the edge. At the initialization there is no
ow from the source to the sink (f=0) and edge capacities in the residual graph
G 0 are equal to the original capacities in G. At each new iteration the algorithm
nds the shortest s ! t path along non-saturated edges of the residual graph.
If a path is found then the algorithm augments it by pushing the maximum
possible
ow df that saturates at least one of the edges in the path. The residual
capacities of edges in the path are reduced by df while the residual capacities
of the reverse edges are increased by df . Each augmentation increases the total
ow from the source to the sink . The maximum
ow is reached when
any s ! t path crosses at least one saturated edge in the residual graph G f .
Dinic algorithm uses breadth-rst search to nd the shortest paths from s
to t on the residual graph G f . After all shortest paths of a xed length k are
saturated, the algorithm starts the breadth-rst search for s ! t paths of length
Dierent graph based energy minimization methods may use dierent graph con-
structions, as well as, dierent rules for converting graph cuts into image labelings.
Details for each method are described in the original publications.
scratch. Note that the use of shortest paths is an important factor
that improves running time complexities for algorithms based on augmenting
paths. The worst case running time complexity for Dinic algorithm is O(mn 2 )
where n is the number of nodes and m is the number of edges in the graph.
Push-relabel algorithms use quite a dierent approach. They do not maintain
a valid
ow during the operation; each node may have a positive \
ow excess",
and the algorithm tries to push it to neighboring nodes. Push-relabel techniques
are harder to describe in just a few sentences and we would rather refer the
reader to our favorite text-book on basic graph theory and algorithms [6].
For our experimental tests on graph-based energy minimization methods in
vision we selected the following standard algorithms.
DINIC: Algorithm of Dinic [7].
H PRF: Push-Relabel algorithm [9] with the highest level selection rule.
Push-Relabel algorithm [9] with the queue based selection rule.
Many previous experimental tests, including the results in [5], show that the
last two algorithms work consistently better than a large number of other min-
cut/max-
ow algorithms of combinatorial optimization. The theoretical worst
case complexities for these \push-relabel" algorithms are O(n 3 ) for Q PRF and
m) for H PRF.
3 New Min-Cut/Max-Flow Algorithm
In this section we present a new algorithm that we developed while working with
graphs that are typical for energy minimization methods in computer vision. The
algorithm presented here belongs to the group of algorithms based on augmenting
paths. Similarly to DINIC it builds the search tree for nding augmenting
paths but it reuses this tree and never starts building it from scratch. The draw-back
of our approach is that the augmenting paths found are not necessarily
shortest augmenting path; thus the time complexity of the shortest augmenting
path is no longer valid. The trivial upper bound on the number of augmentations
for our algorithm is the cost of the minimum cut jCj, which results in the worst
case complexity O(mn 2 jCj). Theoretically speaking, this is worse than complexities
of the standard algorithms discussed in Section 2.2. However, experimental
comparison in Section 4 shows that on typical problem instances in vision our
algorithm signicantly outperforms standard algorithms.
3.1 Algorithm's Overview
We maintain a search tree S with the source as a root where all edges from each
parent node to its children are non-saturated. The nodes that are not in S are
called \free". The set of free nodes is denoted T . The nodes in the search tree S
are divided into \active" and \passive". The active nodes may \grow", that is,
they may acquire new children from a set of free nodes. The passive nodes are
guaranteed to have no free neighbors connected through non-saturated edges.
Thus, the passive nodes can not grow.
The algorithm iteratively repeats the following three stages:
{ \growth" stage: the search tree grows until the sink is found
{ \augmentation" stage: the path found is augmented, the search tree is broken
into a forest.
{ \adoption" stage: the forest is transformed back into a tree.
At the growth stage the search tree expands. The active nodes acquire new children
from a set of free nodes. The newly acquired nodes become active members
of the search tree S. As soon as all neighbors of a given active node are explored
the active node becomes passive. The growth stage terminates when the sink is
encountered and, thus, a path from the source to the sink is found.
The augmentation stage augments the path found in the growth stage. Since
we push through the largest
ow possible some edges in the path become satu-
rated. Thus, some of the nodes in the tree become \orphans", that is, the edges
linking them to their parents are no longer valid (they are saturated). In fact,
the augmentation phase splits the search tree S into a forest. The source is still
a root of one of the trees in the forest and the orphans form roots of other trees.
The goal of the adoption stage is to restore a single search tree structure with
a root in the source. At this stage we try to nd a new valid parent for each
orphan. If there is no such parent we remove the orphan from S and make it a
all its former children orphans. The stage terminates
when no orphans are left and, thus, the search tree structure of S is restored.
Since some orphan nodes in S may become free the adoption stage results in
contraction of the set S.
After the adoption stage is completed the algorithm returns to the growth
stage. The algorithm terminates when the search tree can not grow (all active
nodes checked their neighbors and became passive) while the sink is not found.
3.2 Details of Implementation
Assume that we are given a directed graph As for any augmenting
path algorithm, we will maintain a
ow f and the residual graph G f (see Section
2.2). For each node p we will store its parent as PARENT (p). Roots of the
forest (the source and the orphans) as well as all free nodes have no parents,
t.e. PARENT We will also keep the lists of all active nodes, A, and all
orphans, O. The general structure of the algorithm is:
while true
grow S to find an augmenting path P from s to t
augment on P
adopt orphans
while
The details of the growth, augmentation, and adoption stages are described below.
Growth stage: At this stage active nodes acquire new children from a set of
nodes.
while A 6= ;
pick an active node p 2 A
for every non-saturated edge (p; q)
add q to the search tree as an active node:
S
end for
remove p from A
while
return
Augmentation stage: The input for this stage is a path P from s to t. Note
that the orphan set is empty in the beginning of the stage, but there will be
some orphans in the end since at least one edge in P becomes saturated.
find the bottleneck capacity  on P
update the residual graph by pushing flow  through P
for each edge (p; q) in P that becomes saturated
set PARENT (q) := ;
add q to O
end for
Adoption stage: During this stage all nodes in O are processed until O becomes
empty. The node being processed tries to nd a new parent in S; in case of success
it remains in S but with a new parent, otherwise it is removed from S to the set
its children are added to O.
while O
pick a node p 2 O
remove p from O
process p
while
The operation \process p" consists of the following steps. First we are trying
to nd a new parent for p. For each non-saturated edge (q; p) entering p we check
whether q is a valid parent. Two conditions should hold for q:
{ q should be in S
{ the \origin" of q should be the source
Note that it is necessary to check the second condition because some of the nodes
in S originate from orphans.
If a new parent q is found, then p remains in S with q as its parent. The
active (or passive) status of p in S remains unchanged. If p does not nd a valid
parent in S then the following three operations are performed:
{ p is removed from S (and A) and becomes a free node in T
{ for all children q of p we set PARENT add them to the set of
orphans O
{ all \potential" parents of p (nodes q in S such that the edge (q; p) is not
saturated) are added to the active set A
The last operation is necessary to make sure that no passive node in S connects
to a free neighbor through a non-saturated edge. Only active nodes are allowed
to have such free neighbors. Suppose that an orphan p becomes free. Without
the last operation, the passive neighbors of p in S connected to p via non-saturated
edges would remain passive while they should not. At that moment
these neighbors did not qualify as valid parents for p because they originated
from other orphans and not from the source. After the search tree is xed one
of such neighbors may potentially become a new parent of p.
3.3 Correctness proof
Let's introduce some invariants which are maintained during the execution of
the algorithm.
I1 S is a forest with roots at either the source or orphans.
I2 Edges from a parent to children in the search forest have nonzero residual
capacities.
I3 There are no orphans during the growth stage.
I4 For passive nodes p in S the following property should be true: for all non-saturated
edges (p; q) the node q must belong to S.
These invariants are clearly true at the initialization of the algorithm. It is
easy to see these invariants directly follow from the construction of the algorithm.
Let's show that all stages terminate. The growth stage terminates because
the number of nodes is nite. The same argument applies to the augmentation
stage. Now we prove that the adoption stage is also nite. Note that after a node
in O has been processed it can not become an orphan again during the same
adoption stage (it will imply that the adoption stage terminates after processing
at most n nodes). Indeed, if p is moved from S to T then this holds since free
nodes in T are not involved at the adoption stage. Suppose p found a new parent
q and remained in S. The new parent q must originate from the source. Thus,
the source is the new origin of p as well. By construction, only descendants of
orphans may become orphans during the adoption stage. Therefore, p can not
become an orphan again at the same adoption stage.
The algorithm terminates if the number of cycles (augmentations) is nite.
Since the algorithm is not a shortest path algorithm the polynomial bound for
the number of augmentations does not seem to be valid. We know only a trivial
bound given by a minimum cut cost that works if all edge weights are integers.
It remains to show that when the algorithm terminates it generates the max-
imum
ow. In fact, the search tree S and the set of free nodes T at the end of
the algorithm give a minimum s=t-cut. Suppose the algorithm has terminated.
It could only have happened in the growth stage when no active nodes were left
2 S. S and T are disjoint sets such that S [
Suppose that the current residual graph contains a non-saturated path from the
source to the sink that can be used to increase the
ow. Then there is a non-saturated
edge (p; q) going from a node p 2 S to another node q 2 T . Since no
active nodes are left then p is passive. Hence, the invariant I4 does not hold for
p and we get a contradiction.
4 Experimental Tests on Applications in Vision
In this section we experimentally test min-cut/max-
ow algorithms for three
dierent applications in computer vision: image restoration (Section 4.1), stereo
(Section 4.2), and object segmentation (Section 4.3). We chose formulations
where certain appropriate versions of energy (1) can be minimized via graph
cuts. The corresponding graph structures were previously described by [10, 12,
2, 4, 14, 3] in detail. These (or very similar) structures are used in all computer
vision applications with graph cuts (that we are aware of) to date.
Note that we could not test all known min-cut/max-
ow algorithms. We
compare our new algorithm presented in Section 3 and standard algorithms
of combinatorial optimization introduced in Section 2.2: DINIC, H PRF, and
Many experimental tests, including the results in [5], show that the
last two algorithms work consistently better than a large number of other min-
cut/max-
ow algorithms of combinatorial optimization. For DINIC, H PRF, and
Q PRF we took the implementations written by Cherkassky and Goldberg [5]
and modied them to our graph representation. Both H PRF and Q PRF use
global and gap relabeling heuristics. Our algorithm also leaves some choice in
implementing certain functions. We found that the order of processing active
nodes and orphans may have a signicant eect on the running time. We made
a tuning and used it in all experiments.
4.1 Image Restoration
Here we consider two examples of energy (1) with the Potts and linear models
of interaction. Graph based methods for minimizing Potts energy were used
in many dierent applications including segmentation [13], stereo [2, 4], object
recognition [1], shape reconstruction [16], and augmented reality [17]. Linear
interaction energy was used for stereo [15] and segmentation [12]. The structures
of the corresponding graphs are identical in all applications using the same type
of energy. We chose the context of image restoration mainly for its simplicity.
The Potts energy that we use for image restoration is
(p;q)2N
(a) Diamond restoration (b) Original Bell Quad (c)\Restored" Bell Quad
method
Our
input
Diamond Bell Quad
input: Diamond input: BellQuad
(d) Potts energy (e) Linear interactions energy
Fig. 2. Image Restoration Experiments
is a vector of unknown \true" intensities of pixels on
the image P and I
are intensities observed in the original image
corrupted by noise. The Potts interactions are specied by penalties K (p;q) for
intensity discontinuities between pairs of neighboring pixels. Function T () is 1
if the condition inside parenthesis is true and 0 otherwise. In the case of two
labels the Potts energy can be minimized exactly using the graph cut method of
Greig et. al. [10]. We consider image restoration with multiple labels where the
problem becomes NP hard. We use an iterative graph based method in [4] which
is guaranteed to nd a solution within a factor of two from the global minimum
of the Potts energy. At each iteration [4] computes a minimum cost cut for a
certain generalization of the graph introduced in [10].
Our image restoration experiments with the Potts energy are presented in

Figure

2(a-c). The sizes of our test images are 100100 (Diamond) and 112136
(Bell Quad). The number of allowed labels is 215 and 256, correspondingly. The
running times (in seconds, 333MHz Pentium III) for the Potts energy minimization
tests are given in Figure 2(d). These running times represent the rst cycle
of iterations (see [4] for more details).
We also consider image restoration with \linear" interactions energy:
(p;q)2N
A (p;q)  jI p I q j (3)
where constants A (p;q) describe the relative importance of interactions between
neighboring pixels p and q. If the set of labels is nite and ordered then this
energy can be minimized exactly using either of the two almost identical graph-based
methods developed in [12, 2]. In fact, both of them use graphs very similar
to the one introduced by [15] in the context of multi-camera stereo. These methods
build graphs by consecutively connecting multiple layers of image-grids. Each
layer corresponds to one label. The structure of the graphs for linear interactions
energy has one important distinction from the graphs that are currently used to
minimize other types of energies; the two terminals are connected only to the
rst and the last layers of the graph. This distinction becomes more pronounced
when the number of labels (layers) is large. Note that allocating computer memory
for such multi-layered graphs can be problematic even for 2D images.
The table in Figure 2(e) shows how long it took each min-cut/max-
ow
algorithm to compute the exact minimum of the linear interactions energy above.
We used the same Diamond and Bell Quad images as in the Potts energy tests.
In the tests presented in (e) we varied the number of labels (layers) jLj. The
experiments show that our algorithm is the fastest when the number of labels
is relatively small (less than 50) while Q PRF wins for larger number of labels.
Note that the number of labels aects the structure of the graphs in [15, 12, 2].
In the Potts energy minimization method in [4] the number of labels changes
the number of iterations in each cycle but has no eect on the graph structures.
4.2 Stereo with Occlusions
Here we describe our tests on examples in stereo. We consider a recent formulation
[14] that takes occlusions into consideration. The problem is formulated
as a labeling problem. We want to assign a binary label (0 or 1) to each pair
is a pixel in the left image and q is a pixel in the right image that
can potentially correspond to p. The set of pairs with the label 1 describes the
correspondence between the images. The energy of conguration f is given by
occluded in the conguration f)
The rst term is the data term, the second is the occlusion penalty, and the
third is the smoothness term. P is the set of pixels in both images, and N is
the neighboring system consisting of tuples of neighboring pairs fhp; qi; hp
having the same disparity (parallel pairs). [14] gives an approximate algorithm
minimizing this energy among all feasible congurations f . In contrast to other
energy minimization methods, nodes of the graph constructed in [14] represent
pairs rather than pixels or voxels.
The tests were done for three stereo examples shown in Figure 3. We used the
Head pair from the University of Tsukuba, and the well-known Tree pair from
(a) Left image of Head pair (b) Disparity map for Head pair
(c) Left image of Tree pair (d) Disparity map for Tree pair
image of
Random pair
(f) Right image of
Random pair
for Random pair
Fig. 3. Stereo Experiments. The sizes of images are 384  288 in (a), 256  233 in (c),
and 100  140 in (e,f). The results in (b,d,g) show occluded pixels in black color.
SRI. To diversify our tests we compared the speed of algorithms on a Random
pair where the left and the right images did not correspond to each other.
Running times for stereo examples in Figure 3 are shown in seconds (450MHz
UltraSPARC II Processor) in the table below. The times are for the rst cycle
of the algorithm, which is where most of the work is done.
method input
Head pair Tree pair Random pair
DINIC 365.4 39.4 32.6
Our 17.0 4.0 7.2
4.3 Interactive Object Segmentation
In this section we describe experimental tests that compare min-cut/max-
ow
algorithms on Interactive Graph Cuts segmentation technique in [3]. The method
in [3] allows for the segmentation of an object of interest in N-D images/volumes.
This technique generalizes the MAP-MRF method of Greig at. al. [10] by incorporating
additional hard constraints into the minimization of the Potts energy
(p;q)2N
over binary (object/background) labelings of image. The hard constrains come
from a user placing some object and background seeds. The technique computes
binary segmentation of N-dimensional image with globally optimal regional and
boundary properties among all segmentations that satisfy the hard constraints
(seeds). The details of the corresponding graph construction are given in [3].
We tested min-cut/max-
ow algorithms on 2D and 3D segmentation examples
illustrated in Figure 4. We present the original data and the segmentation
results corresponding to certain sets of seeds. Note that the user places seeds
interactively. New seeds can be added to correct segmentation imperfections.
The technique in [3] e-ciently recomputes the optimal solution starting at the
previous segmentation result.

Figure

4(a-b) shows photo-editing experiment on a picture (200x300 pixels)
with a group of people around a bell. Other segmentation examples in (c-h) are
for 2D and 3D medical data. The cardiac MR data in (c-d) was tested in both
2D (256x256 pixels) and 3D (256x256x13 voxels) cases. In our 3D experiment
the seeds were placed in only one slice in the middle of the volume. This was
enough to segment the whole volume \correctly". The tests with lung CT data
(e-f) were also made in both 2D (512x512 pixels) and 3D (512x512x5 voxels)
cases. In (g-h) we tested the algorithms on 2D liver MR data (512x256 pixels).
The table below compares the running times (in seconds, 600MHz Pentium
III processor) of selected min-cut/max-
ow algorithms for the segmentation examples
described. Note that these times include only the min-cut/max-
ow com-
Photo Editing
(a) Bell Photo (b) Bell Segmentation
Medical Data
(c) Cardiac MR (e) Lung CT (g) Liver MR
(d) LV Segment (f) Lobe Segment (h) Liver Segment
Fig. 4. Segmentation Experiments
putation 3 . The tests on 3D data are marked by \3D". To diversify our tests we
also made a few experiments where inconsistent seeds were placed at random
places in the image. The corresponding columns in the table are marked as \ran-
dom". Meaningless segmentations from these tests are not shown in Figure 4.
method input
Liver Bell Lung Heart(3D) Lung(3D) Bell(random) Lung(random)
26 7 5 | | 8
Our
Note that 3D segmentation required memory e-cient implementations of
the graph cut algorithms. We made such implementations only for our new
algorithm and for Q PRF (which outperformed H PRF and DINIC in most other
experiments). H PRF and DINIC were not tested in 3D segmentation examples.
Conclusions
We tested a reasonable sample of typical vision graphs. In most examples our
new min-cut/max-
ow algorithm worked 2-10 times faster than any of the other
methods, including the push-relabel and Dinic algorithms (which are known to
outperform other min-cut/max-
ow techniques). In some cases the new algorithm
made possible near real-time performance of the corresponding applica-
tions. One noticeable exception was the energy with linear interactions (3). If
the number of labels for (3) was relatively small (< 50) then our algorithm was
only marginally the best, while Q PRF was signicantly faster for larger number
of labels. We also found that our algorithm's performance was roughly the same
as Q PRF in unrealistic examples with \random" inputs.
Our results also suggest that graphs in vision are a very specic application
for min-cut/max-
ow algorithms. In fact, Q PRF outperformed H PRF in most
of our tests despite the fact that H PRF is generally regarded as the fastest algorithm
in combinatorial optimization community. Additional experiments showed
that our algorithm was several times slower than H PRF on standard (outside
computer vision) graphs that are used for tests in combinatorial optimization.

Acknowledgements

Olga Veksler (NEC Research, NJ) greatly helped with implementations for Section
4.1. We also thank Professor Ramin Zabih (Cornell, NY) for the discussions
that signicantly improved our paper. Our research would not be possible without
support from Alok Gupta and Gareth Funka-Lea (Siemens Research, NJ).
3 The time it takes the user to place the seeds varies and may depend on image quality,
object of interest, and the level of desired details. For the experiments in Figure 4
all seeds were placed within 10 to 40 seconds.



--R

A new bayesian framework for object recognition.
Markov random
Interactive graph cuts for optimal boundary
Fast approximate energy minimization via graph cuts.
On implementing push-relabel method for the maximum ow problem
Combinatorial Optimization.
Algorithm for solution of a problem of maximum ow in networks with power estimation.
Flows in Networks.
A new approach to the maximum ow problem.
Exact maximum a posteriori estimation for binary images.

Segmentation by grouping junctions.
Fisher III
Computing visual correspondence with occlusions via graph cuts.
A maximum- ow formulation of the n-camera stereo correspondence problem
Exact voxel occupancy with graph cuts.
Fusion of color
Image segmentation by nested cuts.
--TR

--CTR
Rahul Gupta , Ajit A. Diwan , Sunita Sarawagi, Efficient inference with cardinality-based clique potentials, Proceedings of the 24th international conference on Machine learning, p.329-336, June 20-24, 2007, Corvalis, Oregon
Matthew Marsh , Shaun Bangay , Adele Lobb, Implementing the "GrabCut" segmentation technique as a plugin for the GIMP, Proceedings of the 4th international conference on Computer graphics, virtual reality, visualisation and interaction in Africa, January 25-27, 2006, Cape Town, South Africa
Han , Wei Xu , Yihong Gong, Video object segmentation by motion-based sequential feature clustering, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA
Takashi Michikawa , Ken'ichiro Tsuji , Tomoyuki Fujimori , Hiromasa Suzuki, Out-of-core distance transforms, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
Shaun Bangay , Chantelle Morkel, Graph matching with subdivision surfaces for texture synthesis on surfaces, Proceedings of the 4th international conference on Computer graphics, virtual reality, visualisation and interaction in Africa, January 25-27, 2006, Cape Town, South Africa
Jrme Darbon , Marc Sigelle, Image Restoration with Discrete Constrained Total Variation Part I: Fast and Exact Optimization, Journal of Mathematical Imaging and Vision, v.26 n.3, p.261-276, December  2006
Michael Bleyer , Margrit Gelautz, Graph-cut-based stereo matching using image segmentation with symmetrical treatment of occlusions, Image Communication, v.22 n.2, p.127-143, February, 2007
Hyung W. Kang, G-wire: a livewire segmentation algorithm based on a generalized graph formulation, Pattern Recognition Letters, v.26 n.13, p.2042-2051, 1 October 2005
Chao Wang , Qiong Yang , Mo Chen , Xiaoou Tang , Zhongfu Ye, Progressive cut, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA
Sylvain Paris , Franois X. Sillion , Long Quan, A Surface Reconstruction Method Using Global Graph Cut Optimization, International Journal of Computer Vision, v.66 n.2, p.141-161, February  2006
Jrme Darbon , Marc Sigelle, Image Restoration with Discrete Constrained Total Variation Part II: Levelable Functions, Convex Priors and Non-Convex Cases, Journal of Mathematical Imaging and Vision, v.26 n.3, p.277-291, December  2006
Graph Cuts and Efficient N-D Image Segmentation, International Journal of Computer Vision, v.70 n.2, p.109-131, November  2006
Indra Geys , Luc Van Gool, View synthesis by the parallel use of GPU and CPU, Image and Vision Computing, v.25 n.7, p.1154-1164, July, 2007
Chin-Hung Teng , Yung-Sheng Chen , Wen-Hsing Hsu, Constructing a 3D trunk model from two images, Graphical Models, v.69 n.1, p.33-56, January, 2007
maximum flow;segmentation;minimum cut;multicamera scene reconstruction;image restoration;stereo;graph algorithms;Index Terms- Energy minimization