CS 194-26: Image Manipulation and Computational Photography

Project Four - Seam Carving

Giulio Zhou

Seam Carving Background

In this project, we implemented seam carving, an algorithm for content-aware rescaling of images. When resizing images, we can naively use methods such as cropping or simple scaling, but these techniques will distort the images in undesired ways or leave out important information. Seam Carving works by applying an energy function on the image to determine which sections are "important". As my base energy function, I use a 2D gradient operator, working off the principle that human eyes are quite sensitive to edges and that interesting subjects tend to have some amount of sharp edges. Once applied, we use a simple dynamic programming algorithm to find the best horizontal or vertical paths through the image (as illustrated below) and remove the minimum cost seam.

Gradient function applied to the house	Seam Carving applies dynamic programming

Basic Seam Carving Results

Here are the results I obtained using the basic seam carving algorithm.

House in the Woods	Horizontal Seam Carved 20%	Vertical Seam Carved 20%
Dubai	Horizontal Seam Carved 20%	Vertical Seam Carved 20%
Half Dome	Horizontal Seam Carved 20%	Vertical Seam Carved 20%
Broadway Castle	Horizontal Seam Carved 20%	Vertial Seam Carved 20%
Berkeley Campus	Horizontal Seam Carved 20%	Vertical Seam Carved 20%

Some Failure Cases

Couple in the Fog	Horizontal Seam Carved 20%	Vertical Seam Carved 20%
	Horizontal Seam Insertion 20%	Vertical Seam Insertion 20%

Notice that seam carving and insertion worked pretty well for vertical resizing but failed catastrophically for horizontal resizing. If we look at the energy map, we quickly notice that the ground to the left and right have some fairly high energy contents, leading algorithm to delete seams from the smoother contours of our subjects (with some extraordinary weight gain and weight loss effects). For additional slight defects, also look above to the Berkeley horizontal seam carving result. Notice that quite a lot of details were removed and the edges on the buildings are somewhat uneven.

Mona Lisa	Horizontal Seam Carved 20%	Vertical Seam Carved 20%
Gradient of Mona Lisa	Horizontal Scaled Mona	Vertical Scaled Mona

Here, we see a particularly interesting failure case. Our image (Mona Lisa) is shown to have considerably high entropy due to the rendering of the painting and as a result, the seams (aside from some bias to the smoother areas) appear of have been inserted completely randomly! As a result, the seam carved and scaled images look fairly alike.

Bells and Whistles

Seam Insertion

In addition to Seam Carving, I also implemented seam insertion. We start by finding the k best seams and proceed via normal seam carving. However, we instead examine each seam in order and interpolate with the neighboring pixel. The results are shown below.

House in the Woods	Horizontal Seam Insertion 30%	Vertical Seam Insertion 30%
Dubai	Horizontal Seam Insertion 30%	Vertical Seam Insertion 30%
Half Dome	Horizontal Seam Insertion 30%	Vertical Seam Insertion 30%
Broadway Castle	Horizontal Seam Insertion 30%	Vertical Seam Insertion 30%
Berkeley Campus	Horizontal Seam Insertion 30%	Vertical Seam Insertion 30%

Object Removal Using Seam Carving/Insertion

Another awesome application of seam carving and insertion is object removal. This works by using a mask to alter the energy values at regions we want to remove and preserve (lowering and raising them respectively), and then running our normal seam carving algorithm. Once the undesired parts of the image have been removed, we can resize the image back to its original size using seam insertion.

Couple Standing Together

Mask to remove woman

Mask to keep man

Stoic Man By Himself

At first, I was curious if I could perform this deletion without the keep mask. After trying it out, I got some pretty strange results (similar to the weight loss seen in horizontal seam deletion failure) since this image has some pretty high energy elements on both sides of the couple. Also, note the slight artifact next to the man's hand, which occurred due to human error in drawing the mask.

Berkeley Campus

Mask to remove tourists

Campus Without Pesky Tourists

Resized using seam insertion

See it in action!

Diagonal Seam Carving

In addition to horizontal and vertical seam carving, I also implemented diagonal seam carving, which finds the best sequence of horizontal and vertical seams to resize images.

House in the Woods

Horizontal, then Vertically Resized

Diagonal Resizing

Overall, there doesn't appear to be too much of a difference between the two, but the diagonal resizing appears to be slightly better about minimizing distortion of edges.

Alternate Energy Functions

I tried using some alternate energy functions such as entropy, but they were generally much slower than my gradient function (and thus I didn't get a chance to run seam carving on other images). Based on the results below, it appears that the entropy function was able to identify the foreground much better than the gradient function (which generally only focused on edges). Perhaps with some optimizations, the entropy function could be very useful for seam carving.

Berkeley Campus Gradient Function

Berkeley Campus Entropy Function

What I Learned

Before this project, I had only briefly heard about content-aware image resizing. It's really amazing to see how powerful and straightforward these algorithms actually are, and the results are absolutely stunning! Even with their limitations, content-aware image resizing algorithms such as seam carving are amazing tools to have around.