Graphics Reference
In-Depth Information
e
1
(x
1,y)
x
1, y
x
1, y+1
∞
∞
S
T
∞
e
1
(x,y)
x, y
x, y+1
∞
(a)
(b)
Figure 3.31.
(a) Graph-cut formulation of seam carving. (b) Arc weights for a subset of the
graph (the dotted region in (a)) corresponding to finding the minimal-cost vertical seam. Here,
e
1
represents the sum of gradients in the summand of Equation (
3.36
).
S
T
directed arcs from
. After computing the cut, we remove the pixels to the left of
the seam in each row. The special configuration of infinite-weight arcs ensures that
the cut forms a connected path of pixels that only intersects one pixel per row (see
Problem
3.21
).
Rubinstein et al. also observed that the original formulation of the seam energy
in Equation (
3.36
) ignores energy that may be
inserted
into the image by removal
of the seam, since new edges are created when previously non-neighboring pixels
are pushed together. Instead, they proposed to measure the energy of a seam as the
energy
introduced
by removing the seam. They called this the
forward energy
of the
seam to distinguish it from the
backward energy
in Equation (
3.36
). As illustrated in
Figure
3.32
, there are three possibilities for new edges introduced for a vertical seam
depending on its direction at pixel
to
.
These three cases correspond to the forward energy cost function terms
(
x
,
y
)
C
LR
(
x
,
y
)
+
C
LU
(
x
,
y
)
Case 1
(
)
=
C
x
,
y
C
LR
(
x
,
y
)
Case 2
(3.37)
C
LR
(
x
,
y
)
+
C
RU
(
x
,
y
)
Case 3
where
C
LR
(
x
,
y
)
=
I
(
x
,
y
+
1
)
−
I
(
x
,
y
−
1
)
C
LU
(
x
,
y
)
=
I
(
x
−
1,
y
)
−
I
(
x
,
y
−
1
)
(3.38)
C
RU
(
x
,
y
)
=
I
(
x
−
1,
y
)
−
I
(
x
,
y
+
1
)
The total forward energy of a seam is thus
E
(
s
)
=
C
(
x
,
y
)
(3.39)
(
x
,
y
)
∈
s
which can again be minimized using dynamic programming. To minimize the for-
ward energy using graph cuts instead, we modify the subgraph in Figure
3.31
bto
have the weights in Figure
3.33
a. Figure
3.33
b-d illustrates an example of reducing
an image's size using both the backward and forward energies, showing that using
