About

Content-aware image resizing, also called "seam carving", is a method of resizing an image while preserving the structure of important objects. It's better than traditional image resizing because it doesn't squish or stretch content. It's better than cropping because it doesn't omit important content.

The algorithm was developed by Shai Avidan and Ariel Shamir (paper, cool video, Wikipedia article).

How it Works

Some energy function is defined on the image such that higher energy implies greater importance. I used gradient magnitude as my energy function, though there are other choices which yield different results.

A seam is a path of pixels that runs vertically or horizontally along the image. The seam that runs though the least amount of energy is the best seam to remove because it contains the least important pixels. This optimal seam is computed by first computing a cumulative minimum energy map, which maps each pixel to the minimum amount of energy required to reach it. Such a map is efficiently computed using a dynamic programming algorithm.

The seams are computed from these cumulative minimum energy maps by working backwards greedily. Intuitively, they intersect the least amount of detail. This means they aren't very noticeable when they're removed. Here are the first horizontal and first vertical seams for this image:

Repeatedly computing and removing seams gives the effect of content-aware image resizing. Here is an example where width is reduced by 100 pixels, then height is reduced by 100 pixels.

Compare this to the naive resizing (left). Naive resizing shrinks the content. Notice the buildings are all smaller. When compared to cropping (right), you can see how some buildings near the top are lost, and much of the blue sky is now gone. Cropping also removed several rocks in the ocean.

Increasing dimensions

Seam carving can also be used to increase image dimensions. Seams are computed the same way, but instead of removing pixels, we insert new pixels that are the average of their neighbors. To prevent inserting pixels along the same seam every time, multiple seams are computed at once, then pixels are inserted.

In the example below, notice how the boats maintain their original shape and size. The mountains are taller and closer together. They're shaped differently, not just stretched. Also notice their reflections in the water no longer match.