Seam Carving

Intro and Overview

If you have already seen the video on content aware image resizing at seamcarving.com then you probably know what seam carving is. If not, I recommend you to do so.

Seam carving is a method to resize an image that takes the images content into account – and can therefore produce really great results. This is my attempt to provide the reader with an easy to understand explanation of how seam carving works.

A few notes before we start. The images I used for this were released under the terms of CC-BY. They are:

The Sourcecode that I wrote is available at Github. You may use it for anything you like, but be warned that this is highly unoptimized and quickly thrown together code. To compile and run you will also need the DevIL library.

Also note that I will mostly write about horizontal resizing and that this is also the only thing my code can do. However there is no real difference between horizontal and vertical resizing, besides some variable-swapping here and there.

Basic algorithm

The algorithm itself is actually really easy to understand. The paper is easy to read and there is only one or two things I had to figure out by myself.

Here is an outline of the seam carving algorithm and its idea:

Step 1: calculate the energy for each pixel of the image
Step 2: build a map of the minimum cumulative energies
Step 3: do a backtrace on this data to get the path (“seam”) with the lowest energy
Step 4: delete the pixels which belong to the seam

A seam is an 8-connected path of pixels, where a vertical seam runs from top to bottom, containing exactly one pixel in each row. 8-connected means that for each pixel we only consider its 8 adjacent neighbors.

Calculating the energy

When we want to remove a seam with the lowest energy we need to decide how we calculate the energy of a single pixel. There are many ways to do that – the original paper lists a few. I chose to implement a gradient measure by using the so called Sobel operator.

Have a look at the following images to see what results the sobel operator yields:

Original Sobel Operator

This is also commonly referred to as “edge detection”. Here is an image that illustrates the gradient calculation:

To calculate the y-gradient of a pixel, you would add up the values of its neighbors, scaled following the sobel matrix. Lets call the result Gy.

Now we usually want to be able to work with RGB images. To do this, I just evaluated the gradient for each color-channel (R, G, B) independently – say GyR, GyG and GyB – and took the average for Gy. Thus Gy = (GyR + GyG + GyB) / 3.

Then I did the analogous part for the horizontal gradient Gx and finally stored the (x, y)-gradient magnitude at this pixels position in the energy map. The images you see above are directly rendered from that energy map.

Note that my code sets the energy for border pixels (that is pixels which are at the very top / bottom / left / right) always to maximum energy.

Cumulative Energy Map

The next step with our seam carving is to prepare a map of the cumulative energies on that we can do the backtracing later on. This will be the dynamic programming part and it can be easily summarized by the following formula:

M(x, y) = energy(x, y) + min( M(x-1, y-1), M(x, y-1), M(x+1, y-1) )

To compute the cumulative minimum energy M(x, y) for a pixel (x, y), add its energy to the minimum cumulative energy of one of its predecessors (remember the “8-connected” thing?).

Again, I rendered the cumulative energy map:

Original Energy Min. Cumul. Energy

Backtracing

This is the part where we need to use the cumulative enrgy map (CE/M) to find the vertical seam with the lowest energy. Backtracing is a common method for doing such kind of things, so let me give you a brief explanation of how it works.

We start by searching the pixel with the lowest CE in the very last row. After adding that pixel to the seam, we look at its 3 neighbors to the top and agian choose the one with the lowest CE. Have a look at the following image:

The algorithm starts at the bottom row and finds that 11 is the minimal CE. We add that pixel to our seam and look at the two adjacent pixels above. 8 is the minimal CE, so this is the next pixel to be added to the seam. Again in the next step we consider the thre pixels with CE values 7, 2 and 6 respectively. Can you tell how this goes on?

Now let’s think about this for a few seconds. In each step we choose the pixel with the minimal CE, therefore when the algorithm arrives at the top of the image, we know the seam with the overall minimal CE. Remove all these pixels and you’ll have seem carving!

Here is a real example with the seam rendered as a red line and a zoomed version:

Results

Seam carving results depend almost entirely on the chosen energy function. I used a gradient based method because I thought that it was easy to implement and produces quite good results. Of course this will not work as well on some images as it does on others. Quality of the outcome can also be improved by providing the user with tools to manually add energy to parts of the image (therefore “protecting” those parts) or remove energy (force the removal of parts).

Now for the results. I have used my program to resize three different images and these are the results.

Original
Energy
CEM
First Seam
Result

Contact

Alexander Gitter
contact at agitter net