From S. Avidan and A. Shamir, Seam carving for content-aware image resizing. ACM Transactions on Graphics, 26(3), 2007.

# Project 3: Seam Carving

## Brief

• This handout: /course/cs129/asgn/proj3/handout/
• Stencil code: /course/cs129/asgn/proj3/stencil/
• Data: /course/cs129/asgn/proj3/data/
• Handin: cs129_handin proj3
• Required files: README, code/, html/, html/index.html

## Background

Seam carving is a technique to "retarget" (smart resize) images; the technique preserves the content in order of its importance in the image (as defined by some energy function). It was introduced in 2007 (video) (paper) by Shai Avidan and Ariel Shamir.

At a high level it looks like this:

1. Compute the energy matrix for your image (e.g. the sum of gradient energy across the 3 color channels)
2. Find the best (lowest energy) seam using dynamic programming:
1. Make a scoring matrix (M) the size of your image initialized with the values in the energy matrix (E) (i.e. make a copy of your energy matrix)
2. Set the values of every entry in the matrix except for the first row by adding to it the minimal value in any of the cells above it in the seam: M(x,y) = E(x,y) + min( M(x-1,y-1), M(x,y-1), M(x+1,y-1) ), where M(x,y) is the cost of the lowest-cost seam going through that point. (You'll have to do this in an order such that M(...,y-1) is defined at the time it's evaluated -- row by row works. Also beware boundary conditions.)
3. Find the minimal value in the bottom row of the scoring matrix. This is the bottom of the optimal seam.
4. Trace back up the seam by following the smallest value in any of the positions above it in the seam.
3. Remove that seam in the image
4. Repeat with the image (now smaller by 1px in the opposite direction of the seam). Note that you have to recompute the energy matrix each time to take into account new edges added by the seam removal.

## Requirements

Implement seam carving and use it to retarget the images we've provided as well as a couple of your choice (but don't pick huge ones, or it will take awhile!). You'll implement code to find optimal seams and to remove a single seam (you'll also be given an optimized routine to remove multiple seams to make it interactive.)

## Details

MATLAB stencil code is available in /course/cs129/asgn/proj3/stencil/. You're free to do this project in whatever language you want, but the TAs are only offering support in MATLAB.

Your program will take an image as input in addition to a mode (interactive or static) and if static a size to resize the image down to.

You will be required to remove vertical or horizontal seams in static mode, but note that you can use the same seam finding routine with both cases by transposing the matrix. (In MATLAB, the transpose of A is A', transpose images with the included transpose_image function.)

In your writeup include all the given images in the data/ directory retargeted to 200 pixels less than their original width for a baseline comparison (this is the default of the static retargeting code in the stencil). Additionally include at least one image which has been resized in both dimensions.

## Write up

For this project, and all other projects, you must do a project report in HTML. In the report you will describe your algorithm and any decisions you made to write your algorithm a particular way. Then you will show and discuss the results of your algorithm. Also discuss any extra credit you did. Feel free to add any other information you feel is relevant.

Include the given images and at least three images from an outside source. Find at least one image with really poor results. Investigate and discuss the failures.

## Extra Credit

The baseline will work reasonably well for many images, but for certain types of images there are very noticable failures. In particular humans are very sensitive to distortions in faces and distortions in straight lines. Images with large areas of high-frequency texture also tend to behave oddly with simple energy functions.

Here are some ideas, but we will give credit for other clever ideas:

• up to 5 points: Implement image expansion by inserting seams.
• up to 5 points: Implement object removal by reweighting the energy function and then performing seam insertion (as in the paper).
• up to 5 points: Implement a better energy function; maybe focus on certain image elements (faces, straight lines, etc.)
• From this paper / this video implement one (or both!) of:
• up to 5 points: Use the 'forward energy' formulation as described in section 5 (this does not work well with image expansion)
• up to 5 points: Video retargeting using cumulative gradient score (not a graph cut) as described only in the video ~35s

For all extra credit, be sure to demonstrate on your web page cases where your extra credit has improved image quality or allowed new functionality.

To get graduate credit on this project you need to do at least 10 points worth of extra credit. This may not be the case for all projects.

## Web-Publishing Results

All the results for each project will be put on the course website so that the students can see each other's results. In class we will have presentations of the projects and the students will vote on who got the best results. If you do not want your results published to the web, you can choose to opt out. If you want to opt out, email cs129tas[at]cs.brown.edu saying so.

## Handing in

This is very important as you will lose points if you do not follow instructions. Every time after the first that you do not follow instructions, you will lose 5 points. The folder you hand in must contain the following at the root:

• README - text file containing anything about the project that you want to tell the TAs
• code/ - directory containing all your code for this assignment
• html/ - directory containing all your html report for this assignment (including images). Your web page should only display compressed images of moderate size (e.g. jpg or png or gif if you want to animate something, no more than 1000px on a side).

Do not hand in any images in code/results! Any result images should be under html/ as part of your writeup.

Then run: cs129_handin proj3
If it is not in your path, you can run it directly: /course/cs129/bin/cs129_handin proj3

## Rubric

• +50 pts: Optimal seam finding
• +10 pts: Horizontal and vertical seams
• +10 pts: Removing seams
• +10 pts: Failure case and discussion
• +10 pts: Write up
• +10 pts: Extra credit (up to ten points)
• -5*n pts: Lose 5 points for every time (after the first) you do not follow the instructions for the hand in format