Harvey Mudd College
Computer Science 182a
Project 1, problem 2
Due Sunday, January 30, 2011

Note: this is only one of two options for the second problem in this project. I'll be posting the other option by Thursday, 1/20... .

"Finding edge cases": Implementing seam carving

Goals

Tasks

Then, write functions to do the following tasks. This assignment may be completed using either OpenCV or Matlab - the choice is yours. You may work on your own or in pairs.

• Compute the energy function at each pixel using the magnitude of the x and y gradients (equation 1 in the paper). This requires making a choice of how to implement finding the image derivative - be sure to document your choice in your write-up.
• Compute the cumulative energy across the image. You will need one function to compute this cumulative energy horizontally and one to compute it vertically.
• Compute the optimal vertical seam given an image
• Compute the optimal horizontal seam given an image
• Reduce the image size by a specified amount in one dimension (width or height decrease)
• Display the selected seam on top of an image
• Write a resizeH function (horizontal resize) that has the following interface:

    [output] = resizeH(im, newWidth)    (Matlab)
  

    void resizeH( inputImage, outputImage, newWidth );    (C)
  

  This function takes an input image and a parameter specifying the new width (less than the original width) which the output image should have after resizing.
• In general, set up your program(s) so that you can play with the seam removal and specify different combinations of horizontal and vertical seam-removal. View the results in color, but note that the gradients should be computed with the grayscale converted image.
• Try out your system on some of the images provided here: here in caResizeImages.zip, as well as other images of your own choosing.

Coding hints

• Useful matlab functions include imfilter, fspecial, imread, imresize, rgb2gray, imagesc, imshow, and subplot
• To plot on top of a displayed image, use imshow(im); followed by hold on; followed by plot(...) .
• Be careful with double and uint8 conversions as you go between computations with the images and displaying them; filtering should be done with doubles.

OpenCV pointers:

• cvSobel is a gradient-computation operator (you'll need to run it in both directions!); cvSmooth performs Gaussian and other smoothing.
• There are a number of plotting functions that work atop images (in addition to directly changing a pixel's value). See the CxCore library's cvLine and subsequent functions at this link. That said, it is perhaps easiest for this assignment to simply change the pixels along a seam to the appropriate color.

Demo and write-up

For your write-up, create another web- or wiki-page to hold the write-up from this assignment. As noted in the syllabus, the items below will be graded on a scale of up to B+. In order to extend that grading scale up to an A, you should implement an extension of your own choosing. (A number of possible extensions are listed below.)

1. Run your resizeH function on the provided ocean.jpg image with newWidth = 540. Display the output in your write-up.
2. Display (a) the energy function output (total gradient magnitudes e1(I)) for the provided image ocean.jpg, and (b) the two corresponding cumulative minimum energy maps (M) for the seams in each direction - similar to the inset in the paper's Figure 1. Explain in a sentence or two why these outputs look the way they do given the original image's content.
3. For the same image ocean.jpg, display the original image together with (a) the first selected horizontal seam and (b) the first selected vertical seam. Explain briefly why these were chosen as the optimal seams for this image.
4. What if we were to modify the energy function to include only gradients in one direction, i.e., only one of the addends in equation 1? Explain in a setence or two how the output (selected seams) would qualitatively change? Choose any image where we might expect a difference, and show an illustrative example using the original and modified energy function.
5. Examples and testing!    Now, for the real results! Use your system with different kinds of images and seam combinations, and see what kind of interesting results it can produce. The goal is to form some perceptually pleasing outputs where the resizing better preserves content than a blind resizing would, as well as some examples where the output looks unrealistic or has artifacts.
   
   Include results for at least one more of the four provided images, as well as at least four images of your own choosing. Include at least one new example of "good" outcomes and at least one new example of "bad" outcomes. Be creative in the images you choose! Try to predict types of images where you might see something interesting happen. It's certainly ok to fiddle with the parameters (seam sequence, number of seams, etc) to look for interesting and explainable outcomes.
   
   For each result, include (a) the original input image, (b) your chosen resized image (using seam carving), (c) the result one would get if instead a simple resampling were used (Matlab and OpenCV have functions named imresize and cvResize for this), (d) the input and output image dimensions, and (e) a qualitative explanation of what we're seeing in the output.

Extension possibilities

• Implement seam-based expansion in addition to contraction, using the ideas presented in the paper.
• Allow a user to mark an object to be removed, and then remove seams until all pixels on that object are gone (as suggested in section 4.6 of the paper).
• Alternatively, allow a user to manually specify a region that should be treated as having high energy (see Matlab's ginput function for an easy way to get mouse click input).
• Experiment with an alternate energy function, instead of the gradient magnitude. The paper suggests three more or come up with one of your own.
• To avoid warping regions containing people's faces, have the system try to detect skin- colored pixels, and let that affect the energy map. Borrowing ideas from the spam-finding assignment, try using the hue (H) channel of HSV color space as a zeroth-order face detector.
• More generally, let the user select color(s) that they want or don't want to preserve.
• Optimize for the order of horizontal and vertical seams, as described in Section 4.2 of the Avidan & Shamir paper. Show an example where this compares favorably to hard-coding the sequence.
• Other ideas welcome :-)