A Sampler of Useful Computational Tools for Applied Geometry, Computer Graphics, and Image Processing

202 Graphs and Images

p

i,j

p

i,j+1

p

i+1,j

p

i+1,j+1

E

1

E

1

(a)

T

S

(b)

T

S

(c)

T

S

(d)

p

i,j

p

i,j+1

p

i+1,j

p

i+1,j+1

+LR

+LR

+LU

-LU

+LU

-LU

(e)

Figure 12.17: The graph construction for seam carving vertical seams

using graph cut. The subgraph in (a) is tiled across the image while the

left and right columns are connected with s and t, respectively, as illus-

trated in (b). Note that the backward horizontal infinity edges ensure

that the cut is monotonic, or else an infinity edge from S to T must

be cut (for example, the green edge in (c)). Backward diagonal edges

ensure continuous seams, or else a diagonal infinity edge from S to T

must be cut (for example, ...