Digital Signal Processing Reference
In-Depth Information
The first term
E
1
is used to set the penalties for assigning each pixel to foreground
or background, which reflects how the pixel is close to them. In [
19
], this term was
defined as negative log-likelihoods of histograms for “object” and “background”
intensity distributions. Generally, in the interactive method, two distributions can
be estimated from the labeled regions by the user's paints. It means that the prior
distributions can be estimated from labeled pixels in a weak supervised manner.
The second term
E
2
(
is designed to measure the similarity between two
nodes
z
i
and
z
j
by setting a penalty for a discontinuity between them. This term
is close to zero when the distinct boundary is found for nodes
z
i
and
z
j
,which
means that a larger probability of a cut appears between the adjacent pixels. It can be
evaluated by using the local intensity gradient or other regularization-based criteria.
In [
19
], an
ad-hoc
function was used to set the boundary penalties.
The exact solution of the maximum flow problem can be reached by using the
max-flow/min-cut algorithm, which has been discussed in [
23
] in detail. This algo-
rithm tries to find a new augmenting path, which would saturate at least one edge
in the route and increase the flow to approach the maximum. When no new aug-
menting path can be found, the maximum flow is reached, which corresponds to the
minimum cut.
Figure
1.1
shows an example of graph cut-based image segmentation. The orig-
inal image with user's inputs is given in Fig.
1.1
a, where the red and blue strokes
represent the background and the object, respectively. The defined graph is shown
in Fig.
1.1
b, which includes two terminals (i.e., object (
flower
) and background
(
leaves
)) except for general nodes. Figure
1.1
c shows the segmentation result by
the graph-cut algorithm. It can be seen that the object
flower
is segmented success-
fully from the image.
z
i
,
z
j
)
Fig. 1.1
An example of Graph-cut based segmentation. (
a
) Original image
flower
with user's
paints. (
b
) The constructed graph with two terminal nodes. (
c
) Segmentation result
