M ULTI - REGION SEGMENTATION

USING GRAPH - CUTS

Johannes Uln

Abstract
This project deals with multi-region segmenation using
graph-cuts and is mainly based on a paper by Delong and
Boykov [1]. The difference between a multi-label model and
multi-region model is that certain geometrical constraints can
be added with the multi-region models.

Introduction

flow, and thus also the minimum cut. The one we will use
[3] is specifically developed to solve the kind of graphs which
A segmentation is a partitioning of an image into multiple arises in computer vision problems. It works by pushing
segments. This can be the partitioning of an image into flow from both the source and sink, instead of just pushing
one segment belonging to a object in the image and one flow from the source like standard algorithms.
segment belonging to the background in the image. Each
pixel is given a label corresponding to which segment it is
part of. In multi-label segmentation more than one object is 2 Segmentation
searched for in the image and in multi-region segmentation
each pixel can be part of more than one label. In applications 2.1 Binary segmentation
information about an image can be known a priori. When In binary segmentation the image should be partitioned into
segmenting an image of the heart you know before you start two different segments, one belonging to the object and one
that there are two chambers (in a healthy patient) and that belonging to the background.
the chambers are surrounded by the heart muscle. This inWe introduce P as the set of pixel indices and a binary
formation can be used to improve the segmentation by im- variable for each pixel such that xp BP for every p
posing restriction in between the different regions. More on P. When xp = 0 pixel p is a background pixel and when
this later. We first need some background on graphs.
xp = 1 the pixel is part of the object. The intensity of any
A graph G (V, E) is a collection of data-points called ver- pixel p is given by I (p). The segmentation problem can
tices (V ) and connections between the vertices called edges formulated in the form of minimizing the energy function:
(E). Each edge has a capacity c, where we let e(i, j) = c denote an added edge between vertice i and j with capacity c.
regularization terms
data terms
In our treatment e (i, j) and e (j, i) may differ, e (i, j) 0
{ zX }|
{
zX }|
i, j and e(i, i) = 0, i.e we have no loops in the graph.
Dp (xp ) +
Vp,q (xp , xq ), (1)
E (x) =
s

5
4

2
3
2

pP
5

p,qN
i6=j

where there are many different chooses of data and regularization terms.

min-cut

Data terms adds a cost dependent on how different I (p)

Figure 1: The source (s) and sink (t) is indicated by squares, is compared to the expected value of either the background
the vertices by circles and edges by directed arrows. The Eb or the object Eo . One possible data term is:
value over and edge indicate the capacity of the edge. The
(
2
Minimum s t cut is indicated by the thick line. Removing
(I (p) Eb ) , if xp = 0
D
(x
)
=
(2)
p
p
2
the three edges covered by the line will stop all flow from s
(I (p) Eo ) , if xp = 1.
to t.
Regularization terms adds a cost if neighboring pixels are
similar but have different labels. N can be any pixel connectivity and is usually chosen as the 4-neighborhood. A
possible regularization term is

Graphs can be used to formulate discrete optimization

problems such as the max-flow problem. In the problem
flow of any kind, say oil, should be transported from a vertice called source (s) to a vertice called sink (t). The goal is
too find a route which maximizes the flow, this formulation
gives rise to a so called s t graph. The minimum s t cut,
or min-cut, on the graph is the set of edges with minimal
capacity such that there are no edges connecting the source
with the sink, an example is given in Figure 1. The term
graph-cuts comes from the search for the minimal cut in a
s t graph.
A well known result in graph theory is the max-flow/mincut theorem [2] , which states the maximum flow through a
s t graph is the same as the minimum cut in the graph.
There are very effective algorithms for finding the maximum

(
0,

Vp,q (xp , xq ) =
2
1 (I (p) I (q))

if xp = xq

if xp 6= xq ,
(3)
where can be used to regulate the influence from the
regularization term on the energy function
2.1.1

Graph construction

For a min-cut on any graph we set xp = 0 for all vertices

connected to the source and xp = 1 for all vertices con1

nected to the sink. The energy function E (x) can be reformulated into a min-cut problem where the minimal cut
leads to the same labeling as the global minimum of E (x) .
In [4] a general method for converting the energy minimization problem into a min-cut problem is presented, which
works as long as E (x) is a submodular function of up to
three variables.
Definition 1. A function f of two variables with the domain {0, 1} is called submodular if
Figure 2: Examples on how E (x) is turned into a graph.
L EFT: Edge for Dp (xp ) when Dp (1) > Dp (0) R IGHT:
f (0, 0) + f (1, 1) f (1, 0) + f (0, 1) .
(4) Edges for V (x , x ) when D C > 0 and C A < 0.
pq
p
q
A function of n variables is called submodular if from
fixing n 2 variables to any values it follows that the two
(
free variables fulfill (4).
e (s, q) = D C, if D > C
e (q, t) = C D, otherwise.
Definition 2. A supermodular function is the same a subThe last term could be very tricky if it wasnt for the submodular function with the inequality reversed.
modularity, we know that it must be positive and it suffices
It is possible to minimize E (x) via graphs even when the to add the edge e(p, q) = B + C A D. An example on
function is not submodular [5], however global optimum is how the edges are added is given in figure 2. To better unnot guaranteed. These methods lay outside the scope of this derstand why this work it is recommended to work through
the example given in the figure and validate that any cut
project.
We now shortly describe how the graph is constructed for indeed give the same cost as Vp,q (xp , xq ).
the binary segmentation problem. We begin with the data
term, for each pixel p, add the edge
2.1.2 User seeds
(
If we a priori know the label of some pixels we can use this
e (s, p) = Dp (1) Dp (0) , if Dp (1) > Dp (0)
information to calculate an estimation of Eb and Eo . The
e(p, t) = Dp (0) Dp (1) , otherwise.
information can also be added to the graph by adding the
For the regularization term we begin by splitting Vp,q into edges:
the four different combinations of labeling for neighboring
pixels.
Vp,q =

Vp,q (0, 0)
Vp,q (1, 0)

Vp,q (0, 1)
A
=
Vp,q (1, 1)
C

(
e (s, p) =
e (p, t) =

B
D

By adding these edges we prohibit cuts which will contradict our a priori knowledge.

We continue by rewriting the expression as

A
C

B
D

=A+

0
C A

0
C A

0
0

DC
+
DC

0
0

p known to be background,
p known to be object.

B+C AD
0

2.2

Multi-region segmentation

We now extend the binary segmentation to multiple regions.

The notation from [1] is adopted. Define L to be the set of
region indices. We define a new binary variables x BPL
which we index as xip with i L and p P. If xip = 1
pixel p is interior in region i. Let xp denote the vector of all
region variables that correspond to pixel p. If xp = 0, then
pixel p belongs to the background.
The basic idea in [1] is to let each pixel be represented by
The third term can be handled just as easy by adding an- |L| vertices in the graph. For |L| = 1 this will lead to the
same graph as in binary segmentation. For |L| = 2 a new
other edge

The first term is a positive constant so we dont need any

edges for it as it will increase E (x) with the same amount
no matter what labeling is chosen. The second term can be
implemented by adding one edge
(
e (s, p) = C A, if C > A
e (p, t) = A C, otherwise.

i contains j
ij
xip xjq Wpq
0
0
0
0
1

1
0
0
1
1
0

i excludes j
ij
xip xjq Wpq
0
0
0
0
1
0
1
0
0
1
1

i attracts j
ij
xip xjq Wpq
0
0
0
0
1
0
1
0

1
1
0

Table 1: Energy terms for different geometric interactions.

For the i contains j interaction an edge with infinite capacity is added between xip to xjp prohibiting any cut which
separates them. Equal statements can be made for the exclusion and attraction terms.

Figure 3: Graph construction for a 4 4 pixel image. Each

layer i and j have 16 vertices corresponding to each pixel.
The geometric interaction terms are constructed by adding
edges in the inter-region neighborhood N ij which can be
seen as an extension from the normal neighborhood in an
image.

The exclusion term is everywhere supermodular, we can

for simple interactions just flip the meaning of xip and turn
the problem into a everywhere submodular problem.

layer of vertices is added along with edges which interacts

between the different layers, figure 3.
2.2.1 Three regions
Define the multi-region energy function as
We will now explain how to solve a three-region segmentation problem for a special segmentation problem which is
regularization
geometric interaction
data
{ zX }|
{ zX
}|
{ useful in medical image analysis. Assume we have three rezX }|




Dp (xp ) +
V i xi +
W ij xi , xj , gions 13 and that we know a priori that region 2 and 3 are
E (x) =
interior of region 1 and that region 2 and 3 should not overpP
iL
i,jL
i6=j
lap. We enforce the interior geometric constraint by adding
edges with infinite capacity going from the vertices used to
below we explain each part of the energy function.
represent region 1 to those used to represent region 2 and 3.
The data term will now be a function of three variables.
Data terms defines the cost for every combination of re- We introduce the function
gions, i.e each pixel can either be inside or outside each re

D = Dp x1p , x2p , x3p
gion i L leading up to 2|L| different costs. For |L| = 2
the data terms can be reformulated into a graph exactly like
as the cost for pixel p to be interior in any combination for
the regularization term for binary segmentation.
the three regions. We can represent this function as in table
2.
Regularization terms is independent for each region i
and edges are only being added between vertices belonging
Table 2:
to the same layer i. For each region i the regularization terms
are equal to those of binary segmentation.
Di,j,k (0, 0, 0) Di,j,k (0, 0, 1)
A B
Di,j,k (0, 1, 0) Di,j,k (0, 1, 1)
C D
=
Di,j,k (1, 0, 0) Di,j,k (1, 0, 1)
E F
Geometric interaction terms encodes all geometric inDi,j,k (1, 1, 0) Di,j,k (1, 1, 1)
G H
teractions between regions i and j. The inter-region neighborhood N ij is the set of all pixel pairs (p, q) at which region i is assigned some geometric interaction with region j,
We introduce
see figure 3 for an example. Formally we define the terms as:
P = (A + D + F + G) (B + C + E + H) ,
X


ij
ij
i
i
W =
Wpq xp , xq .
from [4] we know that D can be turned into a graph-cut
pqN ij
problem if for every pixel p the following holds.
ij
In table 1, Wpq
is given for three different geometric in- Case 1: For every pixel p where P 0 then the following
teractions. These terms can be reformulated into the graph must also hold:
just like the regularization term for binary segmentation.
3

A + D
A+F

A+G

B+C
B+E .
C +E

Figure 4
(5)

Case 2: For every pixel p where P < 0 then the following

must also hold:

E + H
C +H

B+H

F +G
D+G.
D+F

(6)

The energies B, C, D can be set to any finite value as the

geometric interaction terms will make sure that these combinations never happened. Unfortunately we cannot have
both containment and exclusion interactions for the same
pixel without turning the energy function supermodular [1],
the trick with flipping the meaning of xip does not work.
This means that the cost of H does matter. Since we dont
want region 2 and 3 to overlap our goal is to find a maximum H such that D is still submodular.
We begin with case 1. To maximize H we directly see that
A + D + F + G = B + C + E + H.

(a) Motivational example image.

(b) L EFT: Region 1 in blue overlay. R IGHT: Region 2 in red

overlay.

(7)

From (7) and (5) it is evident that we must maximize D

in order to maximize H which gives
A + D = B + C.

3.1
3.1.1

(8)

Motivation

We begin with motivational example for a two-region segmentation. We have the image in Figure 5a, and assume we
are only interested in segmenting out gray regions when they
are contained inside a black region. This requirement can be
enforced with geometric interaction terms leading up to the
resulting segmentation found in Figure 5b. Here no user
seeds are used, only expected intensities of both regions.

Inserting (8) into (7) yields:

F + G = E + H H = F + G E.
The value of B and C does not matter for the value of
H, it must however fulfill (5) so we set:
(

Two regions

B = A + F + G E,
C = A + F + G E,

3.1.2

MR-segmentation

We continue with the more difficult problem of segmenting out both the myocardium (heart muscle) and the left
and right ventricles (heart chambers) of a short-axis images
(a direction in which the MR-images are captured). We
know a priori that both chambers will be surrounded by myocardium. We set region 1 to be the myocardium and region
2 to be both the left and right ventricle, we then force region
2 to be contained inside region 1. We give the algorithm
3 Experiments
some user seeds, figure 6a. The resulting segmentation can
In all experiments the data term is chosen as (2) and the be seen in Figure 6b, where = 1/5 was used as parameter
regularization terms like (3) with = 1 if nothing else is for the regularization term and connected components with
less than 50 pixels was filtered away in a post processing step.
stated.
which hold as long as G, F 0. In case 2 we see that we
cannot achieve a better value for H because of (6). For the
details on how to construct the graph from this the reader
is referred to [4], and note that P = 0 for the maximum
chose of H.

Figure 6

Figure 5

(a) A simple image containing three regions. User seeds

is shown in colors.

(a) L EFT: A short axis image of the human heart. The lighter area around the
letters LV and RV are the left and right ventricles. The grayish area around
both ventricles is the myocardium. The myocardium is much thicker around
left ventricle compared to the right ventricle. R IGHT: Seeds used to segment
the heart.

(b) L EFT: Region 1 in blue overlay. M IDDLE : Region 2 in red overlay.

R IGHT: Region 3 in green overlay.

3.2
3.2.1

Three regions
Basic result

We begin the experiments with three region segmentation

with an example showing that it is possible to get excellent
results with a single cut, to do this we use the synthetic image found in Figure 7a along with the user seeds given in
the same image. In Figure 7b the resulting segmentation is
shown.
3.2.2

Submodular limitations

The restriction on the energy functions to be submodular

can lead to troubles even for some very simple image such as
the one found in Figure 7a. As was derived in Section 2.2.1
the maximum value of H = F + G E. A normal choice
of data terms for the regions we are interested in may be:

(b) For both images the user seeds are shown in a darker overlay. L EFT: Region 1, myocardium and the left and right ventricles shown in blue overlay.
R IGHT: Region 2, the left and right ventricles shown in red overlay.

A = Dp (0, 0, 0)

+ (I (p) E (Background))

E = Dp (1, 0, 0)

+ (I (p) E (Region 1))

F = Dp (1, 0, 1)

+ (I (p) E (Region 2))

G = Dp (1, 1, 0)

+ (I (p) E (Region 3))

H = Dp (1, 1, 1)

F + G E,

where E () is the expected value of a region and any

positive constant. And in here lies the problem if F + G >
5

2E and H < A; H will be the smallest energy for that

pixel. In Figure 7(b)-(f ), the energy associate with labeling
each pixel to A and E H is given. As can be seen the
lowest energy is attained if all white pixels are labeled to H.
Increasing decreases the relative difference but destroys the
contrast in energies.
3.2.3

MR segmentation

We redo the MR segmentation in Section 3.1.2 but we make

the left and right ventricle into separate regions. Region 1
is the set to be the myocardium, region 2 the left ventricle
and region 3 the right ventricle. We use geometric interaction terms to force region 2 and 3 to be inside of region
1. The user seeds are shown in Figure 8a. The resulting
segmentation when = 1/5 is used as parameter for the
regularization term can be seen in Figure 8b. Region 2 and
Region 3 overlap due to the problem discussed in Section
3.2.2.

(a) Example image where submodularity causes problem. User seeds are given in yellow, blue, red and green.
The scale is used in all images in this Figure.

Discussion

It would be desirable to model the short axis image as three

regions where the left and right ventricle are to different regions; but the experiment in Section 3.2.3 gave poor result.
This is because we are limited to submodular energies. The
results can be improved if supermodular energies are used
which can be solved by Quadratic Pseudo-Boolean Optimization [5].

(b) A = Dp (0, 0, 0)

(c) E = Dp (1, 0, 0)

(d) F = Dp (1, 0, 1)

(e) G = Dp (1, 1, 0)

References
[1] A. Delong and Y. Boykov, Globally Optimal Segmentation of Multi-Region Objects, ICCV, 2009.
[2] L. Ford and D. Fulkerson, Maximal Flow Through a
Network, Canadian Journal of Mathematics, 1956.
[3] Y. Boykov and V. Kolmogorov, An experimental comparison of min-cut/max- flow algorithms for energy
minimization in vision, Pattern Analysis and Machine
Intelligence, IEEE Transactions on, 2004.
(f ) H = Dp (1, 1, 1)
[4] V. Kolmogorov and R. Zabih, What Energy Functions
Can Be Minimized via Graph Cuts?, Pattern Analysis
Figure 7: The problem with a submodular constraint on H,
and Machine Intelligence, IEEE Transactions on, 2004.
H = F + G E.
[5] V. Kolmogorov and C. Rother, Minimizing Nonsubmodular Functions with Graph Cuts-a Review, IEEE
transactions on pattern analysis and machine intelligence,
2007.

(a) A short axis images of the human heart with

user seeds given by the user in yellow, blue, red
and green.

(b) L EFT: Region 1 shown in blue overlay. M IDDLE: Region 2 shown in

red overlay. R IGHT: Region 3 shown in green overlay.

Figure 8: Segmentation of a short-axis image with three a

region model.