COS 429 - Computer Vision

Fall 2009

Assignment 2

Seam Carving

Seam carving is a method for re-targeting images to displays of different aspect ratios. It was originally described by Avidan and Shamir in this paper, and has since gone on to appear in several software products (such as Adobe Photoshop).

The main idea of seam carving is to add or remove seams in the image. A seam is just a path from either the top to the bottom of the image (a vertical seam) or from the left to the right of the image (a horizontal seam). A vertical seam must be have the properties that:

• It contains exactly one pixel in each row.
• In any two adjacent rows, the seam must contain pixels in either the same column or immediately adjacent columns.

Seams are added or removed where they will result in the least visual impact. This is measured using some energy function, of which the simplest (and the one you will use for this assignment) is just the sum of the absolute values of the $x$ and $y$ components of the image gradient. (See equation 1 in the seam carving paper). To reduce the size of the image by one pixel in $x$, all pixels along the vertical seam of least energy are removed. To increase the size of the image, an extra seam would be inserted, with pixel values that are just the average of their neighbors. To decrease or increase the image by one pixel in y, you would need to operate on horizontal seams.

Finding the minimum-energy seams uses dynamic programming. This method relies on the observation that we can compute the minimum-energy vertical seams going through all pixels in row i by knowing the minimum-energy seams through all pixels in row i-1. In particular, the Cumulative Minimum Energy (CME) of a path going through some pixel (i,j) is the energy at (i,j) plus the minimum of the energies at pixels (i-1,j-1), (i-1,j), and (i-1,j+1). The cost of the globally-minimum-energy path is just the lowest CME found at the last row.

For this assignment, you will implement the image-reduction step of seam carving with the energy function defined above. (The seam carving paper includes many other ways in which the basic idea can be applied, but there is no need to implment them. A small amount of extra credit will be granted for any extensions you implement.)

Implement the following in MATLAB:

1. Write a function that takes an image, converts it to intensity (e.g., using rgb2gray), and computes the x and y components of its gradient (using the method of Assignment 1: convolve with a Gaussian in one direction and the derivative of a Gaussian in the other. Use a small Gaussian, e.g. with sigma = 1.) The function should then return the e₁ energy by summing the absolute values of the x and y partial derivatives. Include the resulting energy image for one input image with your submission. (You may need to divide this image by its maximum value before writing it out.)
2. Write a function that computes the minimum-energy vertical seam using dynamic programming. First compute a CME image, one row at a time. Then find the minimum CME in the last row and trace the seam back up the rows, always walking to the minimum of the three neighbors in the previous row. For ease of testing, please make your function conform to the following interface:

   function [seam] = find_vertical_seam(energy_img)

   The energy_img is a matrix of doubles, while the seam should be a vector of the same length as the height of the image, storing the column through which the seam passes at each row.
3. For debugging, write a function that takes an image and a vertical seam, and sets all pixels along the seam to red. Include with your assignment one example of an image with its minimum-cost seam marked in red.
4. Write an analogous find_horizontal_seam function, and a function that marks horizontal seams in red.
5. Given a vertical seam, remove it from the image. This requires, for each row, shifting all pixels to the right of the seam by one pixel to the left. Write the analogous function for removing a horizontal seam.
6. Write a function that takes an input image name together with a target size, which must be equal to or smaller than the original size (in both rows and columns). Repeatedly find and remove the lowest-cost horizontal and vertical seams, until the image is the target size. For ease of testing, please make your function conform to the following interface:

   function [output_img] = seam_carve(input_filename, target_rows, target_columns)

Submitting

This assignment is due Tuesday, October 27, 2009 at 11:59 PM. Please see the general notes on submitting your assignments, as well as the late policy and the collaboration policy.

Please submit the URL to a .zip file with the following:

• The different steps of the above algorithm, as separate .m files.
• One test image of your choice, together with its e₁ energy image, a visualization of its minimum-cost vertical and horizontal seams, and two retargeting results: one that is approximately 25% shorter than the original, and one approximately 25% narrower than the original.
• Two or three additional examples of retargeting (include just the original and retargeted images - no need to include the intermediate results).
• A README.txt or README.html file containing a description of all included files, details of your experiments, and any relevant implementation notes.