 |
|
Introduction to Computer Science II Homework 3 |
|
Assigned: Saturday, Sep 13, 2014 Due: Monday, Sep 22, 2014, at 3pm. |
Homework 3Part I: Implement Seam CarvingFor a horizontal seam, we will consider each pixel to be adjacent to the three pixels to its left and the three pixels to its right. We'll consider the cost of a seam to be the total energy of the pixels it passes through. We would like to find the lowest-cost seam from one edge of the image to the other. This could be done by enumerating all possible seams and choosing the one with the lowest cost, but this would be horribly inefficient: if the image is n pixels wide, then there are 3^n possible seams through each pixel, which quickly becomes intractable. Dynamic programming lets us do much better.We'll start at the left edge of the image and work our way rightward. For each pixel, we'll compute and store the energy of the lowest-cost seam from the left edge of the image to that pixel, ignoring all the pixels to the right. For the first column on the left, this is easy! The pixel's energy is just its cost. For pixels in subsequent columns, the cost of the optimal seam from the left of the image to that pixel is the pixel's energy plus the least cost of the three pixels to its left. By the time we get to the right of the image, we'll have looked at each pixel just once, much faster than enumerating all possible seams! The savings comes from reusing the computed cost of each pixel in the calculations for the three pixels to its right, all the pixels to the right of those, and so on. Now find the pixel on the right-hand border with the lowest total cost. The best seam passes through this pixel. Move back across the image determining the path the optimal seam traces out across the image. Create a new image with one less row than the current image. Copy all pixels not in the seam to the new image and return it. My implementation of this function is 70 lines of code and contains 4 sets of for loops (one to compute the total costs, one to find the minimum pixel on the boundary, one to follow the seam across the image, and one to copy to the new image). You should also implement a function to remove vertical seams. (Hint: Transpose the image and call your other function.) Your final program should take four command line parameters, the input image file, the output image file, the desired width of the output image and the desired height of the output image. It should then iteratively remove rows and columns to achieve the desired width and height. Here are some examples:    
Use your program on at least 5 different pictures. One should be a picture of yourself. One should be a failure case (where the result is just plain weird).
Part II: Written HomeworkWhat to hand inCreate a web page for the assignment. Add a description of your program and some input and output images. Use the CADE online handin system to handin your source code. Please zip and handin your entire project directory (including an info.txt file). If you work in a team only one of you need to submit the source code, but both need to make web pages.GradingEach homework assignment will receive a grade out of 100 points. This week, the available points will be broken down like so:
|