Getting the Skeleton Files

As usual, run git pull skeleton master to get the skeleton files. If you're using IntelliJ, you might need to manually add the SeamRemover.jar file to your project. If you're working from the command line, you'll need to make sure SeamRemover.jar is in your classpath. The easiest way to do this is to copy it into your course-materials-sp16/javalib/ folder.

Introduction

Seam-carving is a content-aware image resizing technique where the image is reduced in size by one pixel of height (or width) at a time. A vertical seam in an image is a path of pixels connected from the top to the bottom with one pixel in each row. (A horizontal seam is a path of pixels connected from the left to the right with one pixel in each column.) Below is the original 505-by-287 pixel image; further below we see the result after removing 150 vertical seams, resulting in a 30% narrower image. Unlike standard content-agnostic resizing techniques (e.g. cropping and scaling), the most interesting features (aspect ratio, set of objects present, etc.) of the image are preserved.

In this assignment, you will create a data type that resizes a W-by-H image using the seam-carving technique.

Finding and removing a seam involves three parts and a tiny bit of notation:

1. Notation. In image processing, pixel (x, y) refers to the pixel in column x and row y, with pixel (0, 0) at the upper left corner and pixel (W − 1, H − 1) at the bottom right corner. This is consistent with the Picture data type in stdlib.jar. Warning: this is the opposite of the standard mathematical notation used in linear algebra where (i, j) refers to row i and column j and with Cartesian coordinates where (0, 0) is at the lower left corner.

We also assume that the color of a pixel is represented in RGB space, using three integers between 0 and 255. This is consistent with the java.awt.Color data type.

1. Energy calculation. The first step is to calculate the energy of each pixel, which is a measure of the importance of each pixel—the higher the energy, the less likely that the pixel will be included as part of a seam (as we'll see in the next step). In this assignment, you will implement the dual gradient energy function, which is described below. Here is the dual gradient of the surfing image above:

A high-energy pixel corresponds to a pixel where there is a sudden change in color (such as the boundary between the sea and sky or the boundary between the surfer on the left and the ocean behind him). In the image above, pixels with higher energy values have whiter values. The seam-carving technique avoids removing such high-energy pixels.

1. Seam identification. The next step is to find a vertical seam of minimum total energy. This is similar to the classic shortest path problem in an edge-weighted digraph except for the following:

   • The weights are on the vertices instead of the edges.
   • We want to find the shortest path from any of W pixels in the top row to any of the W pixels in the bottom row.
   • The digraph is acyclic, where there is a downward edge from pixel (x, y) to pixels (x − 1, y + 1), (x, y + 1), and (x + 1, y + 1), assuming that the coordinates are in the prescribed range.

2. Seam Removal. The final step is remove from the image all of the pixels along the seam. The logic for this method has been implemented for you in the supplementary SeamRemover class, provided in SeamRemover.jar.

   public class SeamRemover {
       // These methods are NOT destructive
       public static Picture removeHorizontalSeam(Picture picture, int[] seam)  // returns a Picture with the specified horizontal seam removed
       public static Picture removeVerticalSeam(Picture picture, int[] seam)    // returns a Picture with the specified vertical seam removed
   }

SeamCarver

The SeamCarver API. Your task is to implement the following mutable data type:

public class SeamCarver {
    public SeamCarver(Picture picture)
    public Picture picture()                       // current picture
    public     int width()                         // width of current picture
    public     int height()                        // height of current picture
    public  double energy(int x, int y)            // energy of pixel at column x and row y
    public   int[] findHorizontalSeam()            // sequence of indices for horizontal seam
    public   int[] findVerticalSeam()              // sequence of indices for vertical seam
    public    void removeHorizontalSeam(int[] seam)   // remove horizontal seam from picture
    public    void removeVerticalSeam(int[] seam)     // remove vertical seam from picture
}

energy(): Computing the Energy of a Pixel

We will use the dual gradient energy function: The energy of pixel (x, y) is $\Delta_x^2(x, y) + \Delta_y^2(x, y)$, where the square of the x-gradient $\Delta_x^2(x, y) = R_x(x, y)^2 + G_x(x, y)^2 + B_x(x, y)^2$, and where the central differences $R_x(x, y)$, $G_x(x, y)$, and $B_x(x, y)$ are the absolute value in differences of red, green, and blue components between pixel (x + 1, y) and pixel (x − 1, y). The square of the y-gradient $\Delta_y^2(x, y)$ is defined in an analogous manner. We define the energy of pixels at the border of the image to use the same pixels but to replace the non-existant pixel with the pixel from the opposite edge.

As an example, consider the 3-by-4 image with RGB values (each component is an integer between 0 and 255) as shown in the table below.

Example 1: We calculate the energy of pixel (1, 2) in detail:

$R_x(1, 2) = 255 − 255 = 0$,
$G_x(1, 2) = 205 − 203 = 2$,
$B_x(1, 2) = 255 − 51 = 204$,

yielding $\Delta_x^2(1, 2) = 2^2 + 204^2 = 41620$.

$R_y(1, 2) = 255 − 255 = 0$,
$G_y(1, 2) = 255 − 153 = 102$,
$B_y(1, 2) = 153 − 153 = 0$,

yielding $\Delta_y^2(1, 2) = 102^2 = 10404$. Thus, the energy of pixel (1, 2) is $41620 + 10404 = 52024$.

Test your understanding: The energy of pixel (1, 1) is $204^2 + 103^2 = 52225$.

Example 2: We calculate the energy of the border pixel (1, 0) in detail:

$R_x(1, 0) = 255 − 255 = 0$,
$G_x(1, 0) = 101 − 101 = 0$,
$B_x(1, 0) = 255 − 51 = 204$,

yielding $\Delta_x^2(1, 0) = 204^2 = 41616$.

Since there is no pixel (x, y - 1) we wrap around and use the corresponding pixel from the bottom row the image, thus performing calculations based on pixel (x, y + 1) and pixel (x, height − 1).

$R_y(1, 0) = 255 − 255 = 0$,
$G_y(1, 0) = 255 − 153 = 102$,
$B_y(1, 0) = 153 − 153 = 0$,

yielding $\Delta_y^2(1, 2) = 102^2 = 10404$.

Thus, the energy of pixel (1, 2) is $41616 + 10404 = 52020$.

Examples Summary: The energies for each pixel is given in the table below:

findVerticalSeam(): Finding a Minimum Energy Path

The findVerticalSeam() method should return an array of length H such that entry x is the column number of the pixel to be removed from row x of the image. For example, consider the 6-by-5 image below (supplied as 6x5.png).

    java SeamCarverVisualizer [filename] [numPixels to remove] [y (if horizontal carving) | N (otherwise)]

    java SeamCarverVisualizer images/HJoceanSmall.png 50 y