Seam Carving 15-463 Computational Photography

Cary Yang (caryy)

Typically, to change the size of an image, we would either resize the image or crop it. However, resizing the image can distort some features, and cropping the image loses detail. Here, we explore seam carving, first detailed in Seam Carving for Content-Aware Image Resizing by Aviden and Shamir. The particular algorithm used in my implementation is the one from Real-time content-aware image resizing by Huang et al.

The Approach

For the most part, the algorithm I used followed exactly what was described in the paper.

For the energy function, I used the standard gradient magnitude with a slight twist, running a median filter over the image first to remove noise while preserving edges.

Bells and Whistles

My implementation uses the algorithm described in Real-time content-aware image resizing by Huang et al to find all the seams of the image in a precomputation step before performing the carving, making it extremely fast.

I have also implemented seam insertion, and diagonal resizing. Because I chose to use Huang’s algorithm, optimal diagonal resizing as described in the original paper was not necessary, indeed, any ordering of horizontal and vertical seams is optimal as the seams in each direction are consistent index maps, as defined in the Appendix of Avidan’s original paper.

As a side note, I attempted to implement a forward energy function, one that tries to minimize the gradient created by removing some pixel, but that seemed to perform about as well as the gradient magnitude method, and was significantly slower, so I left it commented out in my code.

Failure Cases

In some rare cases, failure occured because the seam carving method described in the paper by Huang et al, while extremely performant, does not necessarily find the optimal cut because it finds a perfect matching between pixels at each level, where the optimal seam might cross over previously removed seams and thus not be included in this search.

This can result in failures like the picture on the right, where the results given by Huang et al’s algorithm differ significantly from the optimal result.

More commonly, failures can occur because the energy function used values edges highly, so when the smooth parts of the image are more important than some detailed areas, such as human faces in the following examples, the results appear distorted, as in the following examples.

Further Examples