Seam Carving

Seam Carving is a classic dynamic programming algorithm for content-aware image resizing. Rather than scaling or cropping, the seam carving algorithm resizes images by removing (or copying) horizontal and vertical slices of the image. These slices, called seams, must cross the entire image, but are allowed to zig and zag around salient regions in order to avoid too much deformation.

Below, the image to the left was resized using my seam carving demo to produce the image on the right. Images of hot-air balloons are practically the best-case scenario for seam carving, since the salient objects in the image (balloons!) are mostly surrounded by empty space. Click the link to try it out for yourself, in real-time, on a variety of test images!

Seam carving was first introduced by [Avidan & Shamir 2007] at SIGGRAPH. Due to its simplicity and effectiveness, the algorithm has since made its way into computer science textbooks as well as commercial photo editing software. To me, this technique is quite refreshing, and serves as a reminder that not all problems require a deep neural network!

Avidan, Shai, and Ariel Shamir. "Seam carving for content-aware image resizing." In ACM SIGGRAPH 2007 papers, pp. 10-es. 2007.

Typically, seam carving implementations alternate between taking horizontal and vertical slices to reduce the height and width of an image. For width reduction, the algorithm works in several phases:

Energy Computation. Assign an importance value to each pixel in the image. Common choices for the energy function include gradient magnitude, entropy, and visual salience.

Downward Accumulation. In a dynamic programming implementation of seam carving, the downward accumulation phase keeps track of, for each pixel, the value of the minimum energy path from this pixel to the top of the image.

Backtracking & Seam Removal. Once downward accumulation is complete, a backtracking algorithm is recovers the lowest-energy seams for each pixel in the bottom row of the image. The seams with the lowest energy are removed from the image.

Vertical resizing follows an analogous procedure. To increase the dimensions of an image, low-energy seams are duplicated instead of removed. Further variations exist for efficiently removing many seams simultanously, for intelligently cropping after no low-energy seams remain, and even for seam-carving videos!