CSE 455 Project 1b: Seam Carving

Assigned: Friday, January 15
Due: Friday, January 22 (1:30 PM)

Intro

Seam carving is an algorithm for resizing in a "intelligent" way to that the resized image maintains important image content with minimal distortions. The algorithm does this by adapting to the content of an image. Watch the video above for a good demonstration and high-level explanation.

Getting Started

We will once again be using Matlab for this project. You should all have sucessfully used Matlab for Project 1a. The same rules apply as before in that we will be testing your code using the Matlab installations in Sieg 327, so if you use Octave or the student version, you should make sure your code functions properly in Matlab in Sieg 327 before submitting. Also, you should not use functions from Matlab's Image Processing Toolbox, as this is not installed in the lab and is not allowed for the assignment.

To get started, please watch the video above if you haven't already, and refer to the January 15th lecture and/or the following publication:

Avidan, S. and Shamir, A. 2007. Seam carving for content-aware image resizing. ACM Trans. Graph. 26, 3 (Jul. 2007), 10.

You may find the following images useful for testing: lake.jpg, fishing.jpg, and gliding.jpg. Of course you may test your code on any images you like.

As in the previous assignment, after loading an image A in Matlab (using imread), you should issue the command:

B = double(A) / 255;

Code to Write

1. (15%) Write a matlab function my_imenergy (in file my_imenergy.m) that can be called with the following command:

   E = my_imenergy(A);

   The function should compute the energy image E (a m-by-n matrix) from the input RGB image A (an m-by-n-by-3 matrix). Recall, that the gradients of an image are a good measure of the information in an image. The seam carving algorithm attempts to shrink an image by removing only pixels that don't have a lot of energy, so the energy image E is an important component of the algorithm.

   To compute E, you need to compute image gradients. You can either your [DX DY] = my_gradient(A) function from Project 1a or use the built-in Matlab function [DX DY] = gradient(A). A is a color image (3 values per pixel) and E needs to be a single value per pixel. So in addition to computing gradients, you need to combine the color data. There are a few different ways to do this:

   a) You can convert the image to grayscale, which you can use your my_rgb2gray(A) function for; and then compute the gradients.

   b) You could also choose to compute gradients on each color channel separately and then combine the gradients.

   There are a few ways to do the gradient combinations: you can a) sum the absolute values or b) take their magnitude.

   For the above steps, please choose an order and method for computing and combining gradients and explain your choice (note there is no "correct" choice).

---

Finding Seams

We are going to build up to the full Seam Carving algorithm in two-stages. First you will implement what we will call "Seam Cutting", which is a simplified form of the full seam carving algorithm. This should help you get familiar with the idea of resizing an image by removing seams.

For the sake of the following discussion, let's assume that one wants to shrink an image horizontally only.

In "Seam Carving" a dynamic programing approach is used to find a low-energy, connected vertical path of pixels (one pixel per row) that can be removed without changing the image content too much. This path will look like a jagged line running from the top to the bottom of the image.

For "Seam Cutting" you will instead remove a whole column that has the lowest energy.

When shrinking vertically, the same logic applies with horizontal paths and removing rows.

2. (20%) Write a matlab function my_choose_seam_cut (in file my_choose_seam_cut.m) that can be called with the following command:

   S = my_choose_seam_cut(A,isVert);

   The function should return a seam S that is a list of the pixels to be removed. The seam should be an entire row or column, where the the seam represents the lowest-energy row or column, respectively.

   If "isVert==1", the seam should list the pixels in each row to be removed. Thus S should be an vector (an m-by-1 matrix), where each entry is the column (x position) that should be removed.

   If "isVert==0", the seam should list the pixels in each column to be removed. Thus S should be an vector (now an n-by-1 matrix), where each entry is the row (y position) that should be removed.

   Vertical Cut	Horizontal Cut

3. (25%) Write a matlab function my_choose_seam_carve (in file my_choose_seam_carve.m) that can be called with the following command:

   S = my_choose_seam_carve(A,isVert);

   Now implement the Seam Carving method. Just as before, the function should return a seam S that is a list of the pixels to be removed; however, now the seam will not be a full row or column, but will be a "jaggy" seam cutting through the image.

   Again, if "isVert==1", the seam should list the pixels in each row to be removed. Thus S should be an vector (an m-by-1 matrix), where each entry is the column (x position) that should be removed.

   Also, again if "isVert==0", the seam should list the pixels in each column to be removed. Thus S should be an vector (now an n-by-1 matrix), where each entry is the row (y position) that should be removed.

   Vertical Carve	Horizontal Carve

4. (15%) Write a matlab function my_remove_seam (in file my_remove_seam.m) that can be called with the following command:

   B = my_remove_seam(A,Z,isVert);

   This function should remove the seam returned by either of previous two functions your wrote. Handle vertical and horizontal seams as you did before.

5. (15%) Write a matlab function my_imresize_smart (in file my_imresize_smart.m) that can be called with the following command:

   B = my_imresize_smart(A,S,doCarving);

   The function should intelligently resize an RGB image A (an m-by-n-by-3 matrix) to the size Z = [m' n'], using the functions from the earlier parts of the assignment. If "doCarving==1" then you should use your Seam Carving methods, if "doCarving==0" then use "Seam Cutting".

   Seams should be removed one at a time (you don't need to return the intermediate result). So you should find a seam, remove it, and then find the next seam, remove it, etc.

   For example, if A is a 320x480 (h x w) images and S = [220 470], you'd call your find seam and remove seam method 100 times for vertical seams and 10 times for horizontal seams.

   The order in which you remove seams does make a difference. For example, you could shrink horizontally first (remove 10 vertical seams in the example above) and then vertically (remove 100 horizontal seams), or you could alternate between vertical and horizontal. Choose a method for ordering how your remove seams and explain how the order can affect the result and explain your choice. (Note: there is no "correct" order; however if you are interested, the research paper linked above does have a good method for doing this).

   "Seam Cutting" Result

   Seam Carving Result

Assignment Writeup (10%)

For this project we are asking you to submit a document (either and Webpage, Word Doc, or PDF) that shows the results of a few experiments and where you will answer a few questions. Specifically, your document should answer these questions. Some questions have multiple parts, make sure you answer all of them.

1. Who are the members in your group?
2. How did you divide up the work?
3. How do you combine the color channels and gradients in part 1? Why did you make this choice? Are there an particular advantages or disadvantages of your method that you see?
4. How are you ordering removing vertical and horizontal seams in part 5? Why did you make this choice? Are there an particular advantages or disadvantages of your method?
5. Include a result where you shrink an image both vertically and horizontally using both seam cutting and seam carving. How do the results differ?
6. Include a "negative" result for seam carving, where the result is not pleasing. A good way to get such a result is to try more extreme shrinking in one or both dimensions (still be reasonable though, shrinking to a really small image, such as 1-by-1 or 10-by-10, etc. is not a good example). Try different images from the web. Why does the result look bad? Can you think of types of images or image features that will cause problems for the seam carving algorithm?
7. Describe any extra credit you did and show results.

Extra Credit

Extra credit problems do not count towards your score for the project, but are accumulated separately. One star (*) is awarded for easier extra credit problems, with more stars for more difficult problems. At the end of the course, the stars you've earned will be used to adjust your final grade upward by at most 5%.

• (*) Add a simple way to preserve certain parts of the image from getting removed, i.e., modify your smart resizing function to take a second image that is marked up to indicate regions that should not be cut. Use this image to modify your energy function.

• (*) Implement one or more of the alternative energy functions discussed in the research paper linked above. Make sure to show and discuss results comparing the initial energy function you implemented and the new ones you added for extra credit.

• (**) In the main part of your assignment, the my_imresize_smart function you wrote can only shrink an image. Extend your resize function to do content-preserving enlarging. The process is similar to shrinking in some respects, in that you now will add seams; however, there are some subtlies to the process -- use the research paper linked above as a guideline.

• (*) Make a GUI that allows you to load an image and as you shrink the window resizes the images using seam-carving, like in the video at the top of the page.

  (**) If you use your GUI to call your code as currently written, the resizing process will be slow and not very interactive. Instead pre-compute the seams when the image is loaded, so when the user resizes the window all you have to do is remove the seams -- use the research paper linked above as a guideline.

• (**) Implement the research paper's algorithm for selecting the order of removal for vertical and horizontal seams.

Submission

To turn in your project, submit a single zip file to the dropbox at:

https://catalysttools.washington.edu/collectit/dropbox/iansimon/8903