Andy ZengCS 194-26

Overview

The objective of this project is to shrink images horizontally or vertically while preserving as much detail as possible. Given a desired dimension, the algorithm scores each pixel with an energy value based on its 'importance' via an energy function. For each iteration until the image width/height is reduced to the desired dimension, the lowest-important seam is removed. Note: a horizontal seam is defined to be a connected path from one side of the image to the other with exactly one pixel from each column. Likewise, a vertical seam is a connected path from the top or bottom of the image to the other side with exactly one pixel from each row.

Original Image
First Vertical Seam (energy map)
First Horizontal Seam (energy map)

Sample Images (Vertical Seam Carving)

Original Image
20% Width-reduction
40% Width-reduction
Original Image
20% Width-reduction
40% Width-reduction
Original Image
20% Width-reduction
40% Width-reduction
Original Image
20% Width-reduction
40% Width-reduction

Sample Images (Horizontal Seam Carving)

Note: implementation for horizontal seam carving is almost exactly the same as that of vertical seam carving.

Original Image
20% Height-reduction
40% Height-reduction
Original Image
20% Height-reduction
40% Height-reduction
Original Image
20% Height-reduction
40% Height-reduction
Original Image
20% Height-reduction
40% Height-reduction
Original Image
20% Height-reduction
40% Height-reduction
Original Image
20% Height-reduction
40% Height-reduction

Pre-computation (Bells and Whistles #1)

To produce results faster, I divided my program into a pre-compute section and an online section. During pre-computation, the resulting images at each iteration of seam removal is saved into a cell array. During the online section, given the desired width or height value, the corresponding resized image is retrieved from the cell array. On my computer, pre-computation for most images takes roughly 1-2 minutes, while the online section takes less than a second to shrink an image to the desired width or height.

Energy Function (Bells and Whistles #2)

Using gradient sums as an energy function produced some very outstanding results. However, there were a few exceptions where it didn't work out so well. Example:

Original Image
20% Width-reduction (gradient sums)

Notice above how the bench becomes slightly distorted after width reduction (especially the vertical beams). The seams do not avoid objects of interest because gradient magnitude alone does not capture this extra information. To fix this problem, we can use an alternative energy function based on state-of-the-art data-drive edge detection (Dollar and Zitnick's "Structured Forests for Fast Edge Detection"). We generate a response map of edges, where the edge magnitudes (as a result of a data-driven approach) can be interpreted as rough likelihood estimations for object segmentation contours. Sample output using edge detection:

Edge Response Map
20% Width-reduction (edges)

Notice how the bench distortion is substantially reduced using this new energy function. However, there are still drawbacks - losing the gradient information causes the seams to be too liberal. Notice how the tree leaves on the upper right side near the center still have cubic angle artifacts. Originally, I was going to propose a heuristic to select the better energy function for the input image by computing the average gradient magnitude and see if it exceeds some threshold, but instead I decided to combine the two energy functions to get the best of both worlds, and I got far better results:

Edge Response Map + Gradient Magnitudes
20% Width-reduction (edges + gradient sums)

There is a minimal amount of artifacts, and the bench is not distorted! The new energy map is computed by summing the gradients magnitudes with the edge response times some weight (I empirically chose 0.5). The results were outstanding, so I ultimately used this energy function to generate all of my images displayed above.

Failures

It is difficult to maintain geometric shapes and features in seam carved images, because the energy functions do not capture the extra information. Seam carving also cannot discern between features that need to maintain scalar properties (such as faces or objects of interest) versus areas that can be carved freely (such as backgrounds). Furthermore, without any post-processing, the disjoint image concatenations following seam removals can cause sharp cubic angle artifacts. Here are a few sample failure images:

Original Image
20% Width-reduction
40% Width-reduction
Original Image
20% Width-reduction
40% Width-reduction
Original Image
20% Width-reduction
40% Width-reduction
Original Image
20% Height-reduction
40% Height-reduction
Original Image
20% Width-reduction
40% Width-reduction
Original Image
20% Width-reduction
40% Width-reduction

Image Sources

inspiringwallpapers.net
hdwallpaper.us
hdwallpapersfullhd.net
wall.alphacoders.com
impfashion.com
fanpop.com
hdwallsource.com
hdwallpaperia.com

What I Learned

The coolest thing that I learned from this project was that in image processing, a simple concept (such as that of a seam) could produce some pretty fantastic effects! It was also very interesting to look at energy functions in a whole new light!