Introduction

The foundation of this project is the basic "seam carving" algorithm described in (Avidan and Shamir, 2007). The "energy function" chosen was the simple sum of partial derivatives named "e1" in the paper. As noted by the paper, "e1" produces surprisingly good results on a variety of images (seemingly in spite of its simplicity).

As a visual aid, my implementation of the "seam carving" algorithm displays both the resized image and a version of the original image with the removed pixels marked in red; this allows for easier analysis of the algorithm's exact behavior on a given image.

(Note: Some of these example images are previewed at reduced scale. Please click on any image to see its original size).

Image #1: "Glacier Canyon" by Matt Mosher (InterfaceLIFT)

This landscape provides an excellent example of basic seam carving functionality.

Horizontal Shrink (-64px)


Vertical Shrink (-120px)


"Bells & Whistles #1" - "Pre-Compute" and "Online" Modes

The calculations required to identify seams for removal take significantly longer than the removal operations themselves. It is therefore convenient to have a means to save pre-computed seam data for later use (e.g. previewing a number of different resize operations without waiting for each to be completed "from scratch"). My implementation is able to return seam information in a compact array representation which may be provided to subsequent function calls as an optional argument. The pre-computed data may be used either to completely satisfy the requirements of a "smaller" resize, or to provide a "head start" on calculating additional seams for a more drastic resize. For example, performing the horizontal shrink above on a Wean 5336 cluster machine takes ~36 sec. "from scratch" but less than ~3 sec. to reproduce using pre-computed seam data. Additionally, extending the shrink to 128px requires ~67 sec. "from scratch" but only ~34 sec. when using pre-computed results from the 64px shrink.

"Bells & Whistles #2" - Seam Insertion

In addition to shrinking images via "seam carving," the Avidan and Shamir paper also describes a means to enlarge images via an analogous technique dubbed "seam insertion." My project implementation can employ this techniques to stretch images either vertically or horizontally; an example of a horizontal stretch is below.

Image #2: "Desert Beetle" by Andy Welsh (flickr)

Horizontal Stretch (+80px)


"Bells & Whistles #3" - Object Removal (And Related Topics)

There is a slight problem with the "Desert Beetle" image above: some of the chosen seams go through the Beetle rather than the desert background, causing a just-noticeable distortion of the Beetle's shape (although still less than simple scaling would cause). Were the image to be stretched further, the effect would become unacceptably pronounced.

This problem can be quite significant in cases when the image's subject is composed of smooth surfaces with lower energy than their background, as in the next example:

Image #3: "Atlantic Spotted Dolphin" by Chris Johnson (flickr)

Horizontal Shrink (-150px)


Poor dolphin... there's so much water that could have been removed (at least 175px on the left side alone), yet the seam carving algorithm goes right through him. A human, on the other hand, can easily recognize that the dolphin is important image content (regardless of what the energy function says). To handle situations like this, my project implementation allows the operator to specify up to two bounding boxes (in the usual [xmin ymin width height] format), along with instructions to either "preserve" or "remove" the content the box contains. This information is used to modify the values of the energy function in that area, thereby "attracting" seams to the region or "repelling" them away as appropriate. Use of this functionality on this image is shown below:

Horizontal Shrink (-150px, Preserve [174 37 261 238])


In spite of a slight "tearing" artifact in the water at left, this result seems clearly preferable to the first.

By combining a "removal" bounding box with a subsequent seam insertion to replace the removed pixels, it becomes possible to remove objects from a scene with somewhat different results than those obtained through conventional techniques. My project implements the automatic approach described in the Avidan and Shamir paper: seams are removed until all marked pixels have been eliminated (choosing automatically between horizontal or vertical removals to minimize the number of seams required), then a matching number of seams are re-inserted to restore the image to its original size. An example of object removal is shown below:

Image #4: "Alone Among The Crowd" by "The Visions of Kai" (flickr)

Automatic Removal Of [245 210 21 35]


"Bells & Whistles #4" - A Forward-Looking Energy Policy in 2008

Although energy function "e1" is quite good for many images, certain images do cause problems. One such image is shown below:

Image #5: "The Ramesseum in Luxor" by Jannet Duroc (flickr)

Horizontal Shrink (-240px)

In this example, objectionable carving artifacts may be clearly seen on all four statues (in particular the legs of the far right statue and near the head of the far left statue). One approach to dealing with difficult situations such as this was proposed by Avidan and Shamir (along with Michael Rubinstein) in a subsequent paper published in 2008. The so-called "forward energy" approach, in brief, chooses seams for carving based on the amount of "disruption" they will cause to the image after removal (as opposed to the older technique which considers the pre-removal relevance of the pixels to the image). My project implements "forward energy" as described in (Avidan, Rubinstein, and Shamir, 2008) as an optional feature. The effects of applying "forward energy" seam selection to this image are shown below:

Horizontal Shrink Using "Forward Energy" (-240px)

The seams selected using "forward energy" tend to run more vertically down the statues (as opposed to diagonally across them), greatly improving the appearance of this result.

One More Example...

Vertical resizing by carving horizontal seams is underrepresented in the examples above, so here's another image that turned out nicely:

Image #6: "A Grand Entrance" by Sandra Leidholdt (flickr)

Vertical Shrink Using "Forward Energy" (-111px)


Things That Just Don't Work...

The images above contain several examples where seam carving did not work as hoped. In each of the above cases, however, it was possible to remedy the situation through use of one of the "Bells & Whistles" features such as forward energy. Still, certain images are not handled well by this seam carving implementation, even with the help of the additional features. One such image is reproduced below:

"Bad" Image: [The Bellefield Bridge] (Public Domain, c.1899) (pghbridges.com)
Horizontal Shrink Using "Forward Energy" (-400px)

Not even the use of forward energy can prevent another injustice from being committed against this stately old stone arch bridge. A simple horizontal scaling would likely have produced a better result, given the bridge's symmetrical shape.