Graphics Reference
In-Depth Information
seams that pass through perceptually uninteresting regions of the image. The notion
of “interesting” is encapsulated in a
seamenergy
, the simplest of which is the sum of
image gradients along a given seam
s
:
+
=
∂
I
∂
I
E
(
s
)
=
x
(
x
,
y
)
y
(
x
,
y
)
e
1
(
x
,
y
)
(3.36)
∂
∂
(
x
,
y
)
∈
s
(
x
,
y
)
∈
s
Finding the lowest-cost top-to-bottom seam is easy using dynamic programming;
we simply work from the second row to the last row, keeping track of the cumulative
minimumenergy path to each pixel. We then find the pixel in the bottomrowwith the
lowest cumulative energy and backtrack to find the optimal seam (see Appendix
A.1
).
The computation for left-to-right seams is analogous. Any energy function (such as
the measures of saliency used in the previous section) can easily be substituted for
the gradient sum in Equation (
3.36
). Seam carving can also be done in the gradient
domain, using Poisson reconstruction as in Section
3.2
to recover the image.
Therefore, if we want to reduce an image's width by
k
columns, we perform
k
iterations of finding and removing the lowest-cost vertical seam. Figure
3.28
shows
the results of resizing an example image with this simple technique. For interactive
resizing applications, Avidan and Shamir showed how the cost-ordering of seams
could be pre-computed and stored in a matrix the same size as the original image.
To enlarge an image by
k
columns (which may be of more practical use for visual
effects), we instead
insert
pixels into the image at the
k
lowest-energy vertical seams,
under the assumption that these are the least perceptually distracting locations to
introduce new information. That is, we insert a one-pixel-wide gap at each seam
location and create new colors by interpolating the image colors on either side of
the seam. Figure
3.29
shows the results of expanding an example image with this
technique.
For a different approach to image inpainting, we can force seams to go through a
target region
by setting the seamenergy for these pixels equal to 0. We then remove
seams until all the pixels in
have been removed, and then expand the image by the
same number of seams to regain an image with the original dimensions. Figure
3.30
illustrates an example of inpainting with this seam-based approach; this effect would
be very difficult to achieve with the methods in Section
3.4
. Similarly, to make sure
that seams don't pass thoughperceptually critical regions of the image (suchas faces),
the energy can be made punitively high in such regions.
(a)
(b)
(c)
Figure 3.28.
Reducing an image's width by successively removing the lowest-energy vertical
seams. (a) The original image. (b) The lowest-energy seams. (c) The result of seam removal.
