Digital Signal Processing Reference
In-Depth Information
This chapter is organized as follows. Section 1.2 reviews the existing algorithms
for image/video segmentation. Emerging methods are discussed in Sect. 1.3 to show
the trends in image/video segmentation. Finally, Sect. 1.4 summarizes main chal-
lenges in the research on segmentation methods and offers the outlook for the future.
1.2
The State-of-The-Art Segmentation Methods
The history of image segmentation (i.e., spatial domain) goes back to the nineteenth
century. In existence for over 20 years, image/video segmentation has undergone
vast technological progress, which has resulted in a great variety of algorithms.
This section focuses on representative technologies and will briefly describe specific
examples of where the emergence of the research works began a small revolution
in image segmentation. A more detailed description of addressed algorithms can be
found in numerous reference articles and topics.
1.2.1
Graph-Based Segmentation
1.2.1.1
Graph-Cut Algorithm
In 1989, an interesting work was introduced by Greig [
18
] that the solution of max-
imum a posteriori estimation (MAP) for binary images can be exactly computed
by graph cut. Unfortunately, this idea did not attract much attention until recent
years. The first report on image processing was presented by Boykov and Jolly [
19
],
which applied graph cut to image restoration and interactive image segmentation.
Given the subsets of marked object and background pixels, this work used graph cut
to find the globally optimal segmentation based on a minimum cut algorithm, which
also acts as the foundation work in [
20
-
22
].
Given an image, this work created a graph
G
=
<V ,E >
, which can be described
by a set of nodes
. In particular,
two terminals, i.e., the source terminal
s
and the sink terminal
t
, are designed to
connect to these nodes. In this graph, all the nodes are connected by two kinds
of edges: the bidirectional
n
-links between two neighboring nodes and the
t
-links
between the nodes and the terminals.
Acut
V
(e.g., pixels or regions) and a set of link edges
E
is defined as a binary partition of the nodes with two subsets, which can
be labeled either as the source terminal (foreground) or sink terminal (background).
The goal of graph cut algorithm is to search the best cut that has the globally min-
imal cost (i.e., the sum of the weights of the edges), which is exactly equal to the
maximum flow in the graph [
19
]. In general, for an image
Z
C
=
{
z
i
}
, the cost of a cut
can be expressed by an energy function, which can be defined as
)=
i
∈V
∑
(
(
)+
λ
(
,
)
,
E
Z
E
1
z
i
E
2
z
i
z
j
(1.1)
1
{
i
,
j
}∈E
where
E
1
and
E
2
denote the data and smoothness cost functions, respectively.
