Project 2 - Seam Carving

Overview

Seam carving is a content-aware image resizing technique for changing the size of an image by one pixel of width or height at a time. It is a core feature in Adobe Photoshop and other graphics applications. The underlying algorithm is simple and elegant, but the technique was not discovered until 2007 by Shai Avidan and Ariel Shamir. Here is their original video presentation from SIGGRAPH 2007, the premier conference for computer graphics research:

Objectives

• Manipulate 2D arrays of objects and integers.
• Validate arguments by throwing exceptions.

Provided Files

• 3x4.png – small example image
• 6x5.png – another small example image

• HJoceanSmall.png – real image
• Main.java – example application
• Picture.java – for loading images (originally found at https://introcs.cs.princeton.edu/java/stdlib/Picture.java)
• ProvidedCode.java (find this in your Canvas course) – partial solution
• SeamCarver.java – stubs

Acknowledgements

This assignment is based on materials by Josh Hug, Maia Ginsburg, and Kevin Wayne.

Example Use

Given an image, it is sometimes desirable to resize it in only one dimension. Consider the 507 pixel wide by 285 pixel tall image below. Suppose that we’d like to resize it to 357 x 285 pixels (i.e., making it narrower without changing the height).

Example 1

The easiest approaches are to rescale the image or to crop the image. However rescaling ruins the aspect ratio, making everything look squashed, whereas cropping removes image content (like the people on the right).

Example 2

Example 3

By contrast, seam carving resizes images in a content-aware manner, resulting in much better results for some types of images. Unimportant pixels (like the ocean separating the two people in the middle) are thrown away, while interesting pixels (like the people and the island) are preserved.

Example 4

Example 5

How It Works

Despite its power and modernity, the seam carving algorithm is elegant and easy to describe. We start by converting an image to an “energy matrix” using a very simple function that gives higher (brighter) energy values to important pixels and lower (darker) energy to unimportant ones.

Example 6

We then find the path from the top to the bottom such that the total energy of the path is minimized. This can be done using a dynamic programming approach or by casting it as a shortest paths problem on a directed graph. (You’ll learn about these more advanced techniques in CS 327 and CS 412.)

Example 7

We then “shrink” the image by creating a copy of the original image, but excluding all of the seam pixels (highlighted in image above). Since the seam is exactly one pixel per row, the resulting image is one pixel narrower.

To shrink the image further, we repeat the entire process as many times as we’d like, reducing the width by one each time. Finding and removing horizontal seams is analogous.

Image Library

To read, write, and display images, we will use the Picture class from Sedgewick’s and Wayne’s standard libraries. Within an image, the pixel (x, y) refers column x and row y. Pixel (0, 0) is at the upper-left corner, and pixel (W-1, H-1) is at the bottom right corner.

Warning: this “column-major” order is the opposite from the mathematical notation used in linear algebra, where (i, j) refers to row i and column j. It’s also different from Cartesian coordinates, where (0, 0) is at the lower-left corner.

Colors

Each pixel is represented by a java.awt.Color object. Colors are based on three integers (ranging from 0 to 255) that represent the amounts of Red, Green, and Blue (also known as RGB values).

You can look for color charts on the web to see your favorite colors represented in values specific enough for computers. There are different systems for representing colors, but the 3-channel R.G.B. representation with values ranging from 0-255 (inclusive) is quite popular. Marketing departments often publish “Branding” guidelines to help standardize an organizations presentation on the web, in print, and etc. See for example JMU’s Branding Identity Colors page, just one component of our overall Brand Guide.

SeamCarver

In this assignment, you will implement the seam-carving technique. The main algorithm involves three steps: (1) compute the energy of each pixel, (2) find the seam with the least amount of energy, and (3) remove all the pixels along the seam. Step 2 has already been implemented for you in the ProvidedCode class. Your task is to implement the SeamCarver class in the UML diagram below.

classDiagram
class SeamCarver
SeamCarver: -Picture picture
SeamCarver: -int width
SeamCarver: -int height
SeamCarver: +SeamCarver(picture Picture)
SeamCarver: +getPicture() Picture
SeamCarver: +getWidth() int
SeamCarver: +getHeight() int
SeamCarver: +energy(x int, y int) int
SeamCarver: +energyMatrix() int[][]
SeamCarver: +removeHorizontalSeam(seam int[]])
SeamCarver: +removeVerticalSeam(seam int[])

energy

For this assignment, we will use the “dual-gradient” energy function:

• The energy of a pixel at (x, y) is Δ_x² + Δ_y².
• The square of the x-gradient Δ_x² = R_x² + G_x² + B_x². The square of the y-gradient Δ_y² = R_y² + G_y² + B_y²
• R_x, G_x, and B_x are the differences of red, green, and blue components between pixel (x + 1, y) and pixel (x − 1, y).
• R_y, G_y, and B_y are the differences of red, green, and blue components between pixel (x, y + 1) and pixel (x, y − 1).

By convention, the indices x and y are integers between 0 and W − 1 and between 0 and H − 1 respectively, where W is the width of the current image and H is the height. Your method should throw an IndexOutOfBoundsException if either x or y is outside its range. When x is out of bounds, the error message of the exception should be “x = %d, width = %d” (with the specific values). When y is out of bounds, the error message of the exception should be “y = %d, height = %d” (with the specific values).

To handle pixels on the borders of the image, we will define the leftmost and rightmost columns as adjacent and the topmost and bottommost rows as adjacent. For example, to compute the energy of a pixel (0, y) in the leftmost column, we use its right neighbor (1, y) and its left neighbor (W − 1, y).

Consider [the 3-by-4 image](the 3-by-4 image) with RGB values shown in the table below:

• Non-border pixel example

  The energy of pixel (1, 2) is calculated from pixels (0, 2) and (2, 2) for the x-gradient:

  R_x = 255 − 255 = 0,
  G_x = 205 − 203 = 2,
  B_x = 255 − 51 = 204,
  

  yielding Δ_x² = 0² + 2² + 204² = 41620.

  The energy of pixel (1, 2) is calculated from pixels (1, 1) and (1, 3) for the y-gradient:

  R_y = 255 − 255 = 0,
  G_y = 255 − 153 = 102,
  B_y = 153 − 153 = 0,
  

  yielding Δ_y² = 0² + 102² + 0² = 10404.

  Thus, the energy of pixel (1, 2) is 41620 + 10404 = 52024.

• Border pixel example

  The energy of the border pixel (1, 0) is calculated by using pixels (0, 0) and (2, 0) for the x-gradient:

  R_x = 255 − 255 = 0,
  G_x = 101 − 101 = 0,
  B_x = 255 − 51 = 204,
  

  yielding Δ_x² = 0² + 0² + 204² = 41616.

  The energy of the border pixel (1, 0) is calculated by using pixels (1, 3) and (1, 1) for the y-gradient:

  R_y = 255 − 255 = 0,
  G_y = 255 − 153 = 102,
  B_y = 153 − 153 = 0,
  

  yielding Δ_y² = 0² + 102² + 0² = 10404.

  Thus, the energy of borderpixel (1, 0) is 41616 + 10404 = 52020.

energyMatrix

The energy matrix is constructed by getting the energy at each pixel (x, y). For example, using the 3-by-4 image from the previous section, the energy matrix would be:

findVerticalSeam

The findVerticalSeam() method returns an array of length H such that entry i is the column number of the pixel to be removed from row i the image. For example, consider [the 6-by-5 image](the 6-by-5 image) below:

The corresponding pixel energies are shown below, with a minimum energy vertical seam highlighted in pink. In this case, findVerticalSeam() returns the array { 3, 4, 3, 2, 2 }.

Remember that seams cannot wrap around the image. When there are multiple vertical seams with minimal total energy, your method should return the leftmost seam (based on its starting position on the top row).

The behavior of findHorizontalSeam() is analogous to that of findVerticalSeam() except that it returns an array of length W such that entry j is the row number of the pixel to be removed from column j of the image.

removeVerticalSeam

This removeVerticalSeam method replaces this.picture with a new Picture object and decreases this.width by 1. The new picture is a copy of the old picture with the seam pixels removed. The removeHorizontalSeam method is analogous, except that it decreases this.height by 1.

Notice that copying the picture is necessary, because you cannot change the picture’s width or height. And there is no method to copy the image; you will need to copy each pixel one at a time in this method.

removeHoriztonalSeam

See mention above

Validating Seams

Both of the seam removal methods need to handle edge conditions. They should throw an exception when called with invalid arguments:

1. Throw a NullPointerException if either removeVerticalSeam() or removeHorizontalSeam() is called with a null argument.
2. Throw an IllegalArgumentException if either removeVerticalSeam() or removeHorizontalSeam() is called with an array of the wrong length or if the array is not a valid seam (either an entry is outside the height/width bounds or two adjacent entries differ by more than 1).
3. Throw an IllegalArgumentException if either removeVerticalSeam() or removeHorizontalSeam() is called when the width or height of the current picture is 1, respectively.

Grading

Note: Your code must pass checkstyle before you can get any points for it on this assignment.

To help prepare you for implementing this project, please review the specifications and ask questions. Prior to writing the code for this project, check your understanding of the specifications via the P2 Readiness Quiz in gradescope.