CS 129 Project 3 Writeup

Jeroen Chua (jchua)
October 10 2012

Outline

I briefly describe a method to do image retargetting via seam carving, as described in "Seam Carving for Content-Aware Image Resizing, S. Avidan and A. Shamir, SIGGRAPH 2007" [1]. I implemented the algorithm using the "backward energy" formulation described in [1] (baseline method), as well as the "forward energy" formulation (extra credit). I also implemented image expansion by inserting seams, as outlined in the paper. To carve horizontal seams, the image is first transposed on each color channel, then the seam carving is carried as before (vertical seams are carved), and the resulting image is transposed back. To perform carving in both vertical and horizontal directions, I first carve vertical seams (reducing the width of the image), followed by carving horizontal seams. Note that this method performs ALL vertical seam carves before horizontal seam carves. Although this is not the method outlined in [1], this carving scheme is simple and gives satisfactory results...some of the time.

Extra credit work

The forward energy formulation was implemented as faithfully as possible as outlined in section 5 of [1]. The image expansion by seam insertion was implemented as outline in sub-section 4.3 of [1]. In particular, seams were traversed in order of removal, and were then duplicated by averaging their left and right pixel neighbours (on image boundaries, only existing neigbhours were used) and adding this new seam to the right of the original seam.

Result images for retargetting to smaller images

All images shown are reduced by 200 pixels in the noted direction. The images, from left to right, are:
  1. Source: Original image
  2. Back-width: Retargeted image using backward energy formulation, and width of original image is reduced
  3. Forward-width: Retargeted image using forward energy formulation, and width of original image is reduced
  4. Back-height: Retargeted image using backward energy formulation, and height of original image is reduced
  5. Forward-height: Retargeted image using forward energy formulation, and height of original image is reduced
The results are discussed after the displayed images.

Click an image to see it at its full size.
Source Back-width Forward-width Back-height Forward-height

Discussion of results for retargetting to smaller images

Backward energy

The backward energy seam carving method (columns 2 and 4) produces somewhat realistic images if the dimension being retargeted is not dramatically reduced. For example, for the Mona Lisa image (row 4), cutting the target image width in half results in noticeable artifacts (column 2), especially around the left side of the subject's face. However, when cutting the target image height by 1/3 (column 4), there are few artifacts and the result is visually pleasing. The same effect can be seen for the electric violin player (row 8); when the width is reduced by 1/3 (column 2), the resulting image looks reasonable (except for artifacts near the violinist's hands/scroll of the violin), but when the height is reduced by 1/2 (column 4), the result is terrible. The subject's head is extremely squished. This may be due to the pattern on the violinist's sweater, which contains high edge energy, and so the seam carving algorithm prefers to not carve through that region. The picture of the tree (row 5) indicates an error of saliency- due to the energy formulation, the texture grass/flower region at the bottom of the image is maintained, while the tree (the most salient part of the image) is carved away. This demonstrates the algorithm's weakness when dealing with highly textured, high-energy regions. Lastly, it is interesting to note that the method works reasonably on cartoon images (row 10), although there are still artifacts present (e.g., in row 2, the arm of the subject at the front of the bicycle blends into the background tree).

Forward energy

The forward energy seam carving method (columns 3 and 5) produces more realistic images than the backward energy carving method, and in general, produce pleasing results. This is especially striking in Dali's images (row 2). The image structure is better preserved in the forward energy formulation (column 5) than the backward energy formulation (column 4). Also, in the image of person sitting on the grass (row 7), the backward energy carving method (column 2) introduces many strange artifacts, in particular around the house edges and person boundary, which are seemingly absent in the forward energy formulation (column 3). Lastly, this algorithm fails on the tree image (row 5), just as with the backward energy formulation. Again, the problem demonstrated here is in figuring out what is salient in the image, and dealing with highly textured, high-energy regions that are not salient.

Result images for retargetting to larger images

Here, I show results for retargetting to larger images. I show only a subset of results for brevity. All images shown are increased by 200 pixels in the noted direction. The images, from left to right, are:
  1. Source: Original image
  2. Back-width: Retargeted image using backward energy formulation, and width of original image is increased
  3. Forward-width: Retargeted image using forward energy formulation, and width of original image is increased
  4. Back-height: Retargeted image using backward energy formulation, and height of original image is increased
  5. Forward-height: Retargeted image using forward energy formulation, and height of original image is increased
The results are discussed after the displayed images.

Click an image to see it at its full size.
Source Back-width Forward-width Back-height Forward-height

Discussion of results for retargetting to larger images

As with retargetting to smaller images, the backward energy formulation (columns 2 and 4) produces reasonable results, while the forward energy formulation (columns 3 and 5) seems to produce more visually appealing results on average. Note again that image structure is better maintained using forward energy than backward energy (as can be seen in the Dali painting in row 2). However, artifacts are still present in both approaches. For example, for the boat image (row 1), stretching the height (columns 4 and 5) results in noticeable "streaking" artifacts in the sky.

Retargetting multiple dimensions

Finally, I show results for retargetting an image in a way that both width and height are reduced. The produce images look reasonable, with the forward energy formulation producing more visually appealing results than the backward energy method.

All images shown are increased by 200 pixels in the noted direction.

The images, from left to right, are:
  1. Source: Original image
  2. Back-both: Retargeted image using backward energy formulation, width and hieght of of original image reduced
  3. Forward-both: etargeted image using forward energy formulation, width and hieght of of original image reduced