Image Compositing and Editing - Computer Vision for Visual Effects - page 85

(a) (b) (c)

Figure 3.29. Increasing an image's width by adding pixels at the lowest-energy vertical seams.
(a) The original image. (b) The lowest-energy seams. (c) The result of seam expansion.

(a) (b)

Figure 3.30. Inpainting with seam carving. (a) The original image. (b) An inpainted image of the
same size created by removing, then adding vertical seams. Can you find the two topics that have
been removed, and identify other topics that have been compressed/expanded to compensate?

Rubinstein et al. [ 408 ] proposed two key algorithmic refinements to the original
seam carving algorithm. First, they showed how the problem of finding the optimal
seam could be naturally posed as computing the minimum cut on a graph, which
can be generalized more easily than dynamic programming. As usual, the vertices
of the graph correspond to image pixels. However, unlike the graph-cut methods in
Section 3.3 and the previous chapter, we create a directed graph inwhich each pair of
4-neighbors can be connected by two arcs going in different directions. Figure 3.31
illustrates the graph setup and arc weights that correspond to seam carving. For a
vertical seam, we attach all the pixels on the left edge of the image to one terminal S ,

T

and all the pixels on the right edge to another terminal . We seek a cut of the graph

that separates the terminals; the cost of such a cut is the sum of the weights of the