This is an implementation of some of the concepts and algorithms described in the SIGGRAPH 2007 paper “Seam Carving for Content-Aware Image Resizing” by Shai Avidan and Ariel Shamir. I was fascinated by the YouTube video of their presentation. You can find a higher-resolution video (17MB) on Ariel Shamir's website, along with the actual paper (see previous link, about 20MB) with full details and citations. The website seems pretty slow right now; you might want to go through the Coral cache.

This is a quick-and-dirty implementation of only the basic 1-dimensional seam carving technique, as described in the video's narration, so don't expect anything fancy. :) It runs on MacOS, for the GUI, although the interesting part is all basic C stuff that ought to be easy to port to anything. The algorithm really is as simple as the narration makes it sound: I wrote this implementation in a (long) evening. I guess the logical next step is to make this into a GIMP plugin or some other reusable module.

Compiling: The Xcode project expects to find libnetpbm installed in /opt/local, where DarwinPorts puts it. If you have libnetpbm somewhere else, you'll need to change the include path and library path in the Xcode project, and possibly change the extraPath variable in Seamer.m.

Running the program: There are two image wells in the first window you see. Drag an image into the left well (the one labeled “Input Image”). The program will compute the energy function using netpbm and display it in the right-hand well. You can change the energy function by editing the text field; this is just a pipeline that gets passed to the shell so go wild. It should take a pnm file on stdin and emit another pnm file. If nothing happens, check the console for error messages; the program doesn't do anything clever with pipeline failures. The two energy functions that are most useful are pamsharpmap and pamedge, possibly combined with pnmsmooth. You can get crazy and put anything you want in there as long as the output image is the same size as the input image. Inverting the energy function with pnminvert, for example, produces interesting results.

The “Seams” window will show the energy function again, overlaid with all the seams which have been computed so far (in red). You can compute more seams using the “+” button, which runs the seam-finding algorithm once, or the “!!” button, which runs it repeatedly to get another 20 seams. You can mouse around in the Seams window to explore the dynamic programming path left over from the most recent run, showing the “cheapest” path to the top from the mouse point (in yellow).

The “Scrunchy” window displays the original image again and allows you to shrink it horizontally by clicking or dragging within the image. Note that if you want to make the image (e.g.) 50 pixels narrower, you'll need to have run the seam-finding algorithm enough to have at least 50 seams.

Notes: As I said, this is a very basic implementation. Things it doesn't do that would be nice include: expanding the image as well as shrinking; two-dimensional resizing (either the optimal 2-way seam carving technique or the good-enough “consistent index maps” technique described in the appendix); displaying cost histograms, index maps, or other visualizations of the seam-choosing operation; allowing the user to interactively mark regions as high- or low-energy.

As Avidan and Shamir mention in the paper, the seam-carving algorithm isn't too sensitive to the specific energy function you use. However, the energy function is one of the main tweakable parameters of the algorithm and there are probably interesting effects to be found by tweaking it. It's possible to use different energy functions for horizontal and vertical seams, for example, detecting only horizontal and vertical edges would avoid some undesirable kinds of distortion I've seen. The energy function can be changed midstream (after finding the first N seams), which could have artistic effects or could be useful if different energy-finding algorithms are useful at different stages of image reduction.

There are some aspects of the seam-finding algorithm that could be explored as well. Right now a seam can go vertically or it can hop diagonally left or right one pixel. Allowing a seam to hop more than one pixel to the side seems reasonable, perhaps with an additional cost assessed against that path. Of course this would make the 2-dimensional resizing algorithm more complicated.

Some visual artifacts seem to be due to the algorithm finding two very attractive low-energy regions which are isolated from each other, and carving seams through a (slight) minimum of a higher energy region between them. It might be possible to detect this kind of situation and use scaling for the traversed high-energy region and carving for the low-energy regions, reducing the visibility of the artifact. In general it ought to be possible to use the seam carving technique to do nonuniform resampling of an image; this would probably be useful for image retargeting, but not for the image editing operations demonstrated in the video. A weighted-resampling approach might be able to blend the two approaches (with weights going to 0 for excised regions).

The paper: Avidan, S. and Shamir, A. Seam Carving for Content-Aware Image Resizing. SIGGRAPH 2007.