Lab 11: Seam Carving

This is a lab about shortest paths, but from a different perspective. You’ll need Lecture 25 (Directed Acyclic Graphs), or Chapter 24 to fully understand what’s going on, though you can get by without. It also helps to remember shortest paths from Lecture 23 / Chapter 22.

Note: This lab is a bit different than others. In this lab, rather than reinforcing a specific core data structure or algorithm from lecture, we’ll instead explore how the idea of shortest paths on a graph can be used for the purpose of image resizing.

Here are the slides presented in lab for your reference.

FAQ

Each assignment will have an FAQ linked at the top. You can also access it by adding “/faq” to the end of the URL. The FAQ for Lab 11 is located here.

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. That is rather than shrinking an image proportionally, it lets us cut shrink in only one dimension. It does this by repeatedly removing “seams”.

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 507-by-285 pixel image.

Further below we see the result after removing 150 vertical seams, resulting in a 30% narrower image while preserving the original width. Note that the image is not cropped, scaled, or distorted. Instead, the less important parts of the image have been removed, while the most interesting features of the image are preserved.

Seam Carving Josh Example

Seam Carving Josh Example

In this lab, you will create a data type that resizes a W-by-H image using the seam-carving technique, and then watch it work in your browser.

Goals and Outcomes

By the end of this lab, you will…

  • Have implemented a shortest paths algorithm that finds the cheapest path through a grid, solving each row’s subproblems from the row above.
  • Have seen that “shortest path in a DAG” and “fill in a table one row at a time” are the same idea.
  • Have a seam carver that can shrink any photo you drop into it.

Setup

Follow the Assignment Workflow Guide to get started with this assignment. This starter code is in the lab11 folder. NOTE as with previous labs you do not need to submit this assignment. Instead, you will get credit by completing a checkoff with your TA during lab.

The three parts of the starter code you’ll care about are:

File What’s in it
src/SeamCarver.java This is where you write code.
src/SeamCarverVisualizer.java Run this to open the browser visualizer (described below).
images/ Small test images, each with a .printseams.txt file giving its energies and seams. Also the surfing photo above.

Notation. In this lab, 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, as shown below:

a 3-by-4 image
(0, 0)(1, 0)(2, 0)
(0, 1)(1, 1)(2, 1)
(0, 2)(1, 2)(2, 2)
(0, 3)(1, 3)(2, 3)

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.

Colors are given by a java.awt.Color object, where each color is a mix of a red, green, and blue value (as shown in the next section).

Part 1: Pixel Energy (Intuitively)

The first step of seam carving 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.

The intuition is that a smooth part of an image is “low energy”, whereas a part of the image where the image is changing is “high energy”. In seam carving, we’ll ultimately be throwing away the low energy pixels.

Here is a photo of a recycling bin (with a surprise inside). Click the button to see the energy of every pixel, drawn as a grayscale image where brighter means higher energy.

Recycling bin photo

Notice where the energy is low: the flat sides of the trash can, the pavement, and the patches of sky. These are pixels you could remove without anyone noticing. Notice where it’s high: the lettering, the edges of the bin, the leaves, and the face. Those are the pixels we want to keep because removing them would be more noticeable.

If we were able to find a seam that only ever steps through low energy pixels, its removal would be almost invisible. By repeating this process we can downscale an image.

Part 2: Computing Pixel Energy

This section isn’t strictly necessary, but we recommend it so you can understand what’s really going on with the algorithm. Your choice whether to read!

We use the dual gradient energy function. In pseudocode, we compute as follows: Given a pixel P:

  • Consider that P’s left neighbor L and right neighbor R.
  • Compute $(L.red - R.red)^2 + (L.green - R.green)^2 + (L.blue - R.blue)^2$. This is the x-energy.
  • Consider P’s up neighbor U and down neighbor D.
  • Compute $(U.red - D.red)^2 + (U.green - D.green)^2 + (U.blue - D.blue)^2$. This is the y-energy.
  • The total energy is the x-energy plus the y-energy.

We define the energy of pixels at the border by wrapping around, i.e. if we go off the image, we replace the non-existent 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.

(255, 101, 51)(255, 101, 153)(255, 101, 255)
(255, 153, 51)(255, 153, 153)(255, 153, 255)
(255, 203, 51)(255, 204, 153)(255, 205, 255)
(255, 255, 51)(255, 255, 153)(255, 255, 255)

Tip: hover your mouse over (or tap) any of the underlined squared terms in the example below to highlight the two values in the table that it comes from.

We calculate the energy of pixel P = (1, 2), the shimmering cell above, in detail. Its left neighbor is L = (0, 2) = (255, 203, 51) and its right neighbor is R = (2, 2) = (255, 205, 255), so

x-energy = (255 − 255)2 + (203 − 205)2 + (51 − 255)2 = 0 + 4 + 41616 = 41620.

Its up neighbor is U = (1, 1) = (255, 153, 153) and its down neighbor is D = (1, 3) = (255, 255, 153), so

y-energy = (255 − 255)2 + (153 − 255)2 + (153 − 153)2 = 0 + 10404 + 0 = 10404.

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

Second Example: The energy of pixel (1, 1) is $204^2 + 103^2 = 52225$. (Its left and right neighbors differ only in blue, by 204, and its up and down neighbors differ only in green, by 103.)

Examples Summary: The energies for each pixel is given in the table below, where the shimmering entry is the one we calculated above.

20808.052020.020808.0
20808.052225.021220.0
20809.052024.020809.0
20808.052225.021220.0

Note that the energy of a pixel doesn’t depend on its color, but only on the colors of its neighbors.

Now test your understanding on a fresh pixel. Compute the x-energy, y-energy, and total energy of the center pixel below and type it in. The four neighbors you need are shown with their RGB values. The corners and the center pixel’s own color don’t matter.

up
(60, 160, 60)
left
(200, 50, 20)
(x, y)
(150, 100, 40)
right
(210, 40, 20)
down
(60, 163, 56)

x-energy:   y-energy:   total energy:

Show the work

x-energy (left L vs. right R): (200 − 210)² + (50 − 40)² + (20 − 20)² = 100 + 100 + 0 = 200.
y-energy (up U vs. down D): (60 − 60)² + (160 − 163)² + (60 − 56)² = 0 + 9 + 16 = 25.
Total energy = 200 + 25 = 225.

energy(int x, int y) in SeamCarver is already written and does exactly this computation for every pixel of the picture, with neighbors off the edge wrapping around to the opposite side. The results are stored in a double[][] energy table, indexed energy[x][y], that is recomputed whenever the picture changes.

Part 3: The Visualizer

Run SeamCarverVisualizer. It starts a small web server and opens a page in your browser (if nothing opens, go to the address it prints, which is http://localhost:4567/). The page starts out showing the surfing photo from the top of this page.

The visualizer just after it opens, showing the surfing photo

Load an image of your choosing: drag any photo onto the page, or click Upload image and pick one of the photos from the images folder or one of your own. If the photo is more than 500 pixels on a side, you’ll be asked whether to use it at full scale (slow) or reduced scale (fast): pick reduced. Then check Show energies and see if the energy image matches your intuition about which parts of the picture are smooth.

Now uncheck Show energies, and look at the controls. Target width and Target height start out at 75% of the picture’s size. Click GO.

Nothing happens, except for a message that findVerticalSeam returned null. The visualizer works by repeatedly asking your SeamCarver for a seam, drawing it in red, and removing it, and the two methods that findVerticalSeam relies on, computeM and findSeamFromM, are not written yet. That’s your job!

Let’s now talk about the seam carving algorithm.

Part 4: Finding a Seam by Hand

Below is a tiny 10-by-10 picture, drawn as its energy: each square is a pixel, brighter means higher energy, and the number on each square is its energy.

A vertical seam is a path from the top row to the bottom row with exactly one pixel in each row, where each pixel is directly below, below-left, or below-right of the one above it.

The best seam is the one with the smallest total energy.

Build the minimum energy seam by clicking one pixel per row, starting at the top: first a pixel in the top row, then one of the three pixels below it, and so on. The running total of your seam is shown under the picture. To change your mind, click a pixel in an earlier row and continue from there. When you reach the bottom, click CHECK.

We observe that the greedy choice (here greedy means always take the cheapest next pixel) does not necessarily find the best seam.

One approach to finding the best path would be to treat this like a directed graph with a virtual top and virtual bottom node and run the Dijkstra’s that you impelemented in lab 10 (with modifications for handling a directed graph unlike an undirected graph as in lab 10).

However, this approach would be very slow because it would require the construction of an explicit Graph object with potentially millions of nodes and millions of edges. For example, the graph for the image above would look like shown below.

The 10-by-10 picture as a directed graph with virtual top and bottom, shortest path in red

We observe that the graph structure isn’t actually necessary to store at all! Every graph for every image will have exactly the same structure as shown above, albeit with a different number of rows and columns.

A better approach than storing the graph structure is to operate directly on a 2D array of energies, i.e. effectively representing the graph with a 2D array of doubles, where the edges representing the structure of the graph are known implicitly. This is similar to what we did with heaps, where we represented a PQ with an array of values corresponding to priorities, and the edges were known implicitly (e.g. that parent(k) = k/2).

Let’s explore this idea more carefully.

Part 5: Understanding the Greedy Shortest Paths Algorithm

Above, we saw that simply picking the cheapest pixel does not give the best result. However, if we’re clever, there is a greedy algorithm that does work and avoids any need to create an explicit Graph object.

Note: The idea use here will be covered in CS 170 and is called “Dynamic Programming”. You don’t need to know what this term means in 61B.

The core idea is that you start by computing a shortest paths matrix M row by row from top to bottom, then walk back up the shortest paths matrix.

Suppose we have the following definitions:

  • $M(i, j)$ - total cost of shortest cost path ending at (i, j)
  • $e(i, j)$ - energy of pixel at location (i, j)

The top row is trivial, $M(i, 0)$ is just $e(i, 0)$ for all $i$. For lower rows, we can find $M(i, j)$ simply by adding the $e(i, j)$ to the minimum cost path ending at its top left, top middle, and top right pixels, or more formally:

$M(i, j) = e(i, j) + min(M(i - 1, j - 1), M(i, j - 1), M(i + 1, j - 1))$

Let’s watch this happen on the same 10-by-10 picture from Part 4. On the left is its energy matrix $E$, exactly the numbers you worked with by hand earlier. On the right we’ll build $M$, where $M(i, j)$ is the cost of the shortest path from the top row that ends at pixel $(i, j)$.

Click Compute M. The top row of $M$ appears first, since $M(i, 0) = e(i, 0)$. Then click Next row repeatedly. Each click fills in one more row: every entry is its own energy plus the smallest of the (up to) three entries above it, and the animation shows which cells are being looked at. Once the whole table is done, follow the instructions under it to read the seam off of $M$.

E (energy)
M (cheapest path ending here)

Part 6: computeM() and findSeamFromM()

Open SeamCarver.java. Here is its API.

You’ll write two methods: computeM computes $M$ from top to bottom. Then findSeamFromM walks back up $M$ to get the seam.

Everything else is fully written.

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 static double[][] computeM(double[][] energy)   // the M table for an energy table  <-- YOU WRITE THIS
    public static    int[] findSeamFromM(double[][] m)    // the seam encoded by an M table    <-- YOU WRITE THIS

    public   int[] findVerticalSeam()              // = findSeamFromM(computeM(energy))
    public   int[] findHorizontalSeam()            // sequence of indices for horizontal seam
    public    void removeHorizontalSeam(int[] seam)   // remove horizontal seam from picture
    public    void removeVerticalSeam(int[] seam)     // remove vertical seam from picture
}

More details:

computeM(double[][] e) returns a table of the same size as e. Fill it in one row at a time, top to bottom, with loops (not recursion).

findSeamFromM(double[][] m) returns an array of length height such that entry y is the column of the seam’s pixel in row y. For example, for the 10-by-10 shortest paths matrix $M$ above, you’d return [7, 7, 6, 6, 7, 8, 9, 9, 8, 9].

All matrices are indexed [x][y], e.g. e[x][y] is the energy of the pixel in column x and row y, so e.length is the width and e[0].length is the height.

When there are multiple vertical seams with minimal total energy, your method can return any such seam.

Implement computeM, and run testComputeMOnSpecGrid to check it against the table from Part 5. Then implement findSeamFromM, and run testFindSeamFromMOnSpecGrid, which hands your method the correct $M$ for that grid, so it passes or fails on its own regardless of your computeM.

When both pass, every test in SeamCarverTest should pass, including testAllReferenceImages, which runs your code on every image in images/ and compares against the reference files. You can also run PrintSeams on any small image and compare to its .printseams.txt file.

Then run SeamCarverVisualizer again (stop the old one first), load a photo, and click GO. Each red line you see is exactly the seam your two methods produced, drawn over the picture just before it is removed. A correct seam looks a bit like lightning. As the animation runs, these lightning strikes should wind their way through the flattest, most boring parts of the photo, shrinking the image as it goes.

What about horizontal seams?

findHorizontalSeam is provided. It transposes the energy table (so that rows become columns), runs your computeM and findSeamFromM on the transposed table, and hands back the result, which is already indexed by column and holds row numbers, exactly what a horizontal seam is. Have a look at it: the idea that you can solve a new problem by reshaping it into one you’ve already solved could easily appear on the final exam. The visualizer alternates between vertical and horizontal seams so that both dimensions of your picture finish shrinking together.

Checkoff

As you work through the lab, check in with your TA as a group to get attendance credit. Your TA will explain how check-ins work in your section.

For your checkoff, drop a photo of your choosing into the visualizer, shrink it, and show your TA. Then, be prepared to answer a few questions about your visualizer.

If you are not done coding, this is totally ok! As long as you have done Parts 1-5, you can answer the checkoff questions.

You do not need to have everything 100% correct to get credit. Keep working on the lab while you wait for your TA!

Extra Fun

Try out your SeamCarver on various real world images. Human or animal faces are interesting as you see the algorithm try its best not to mess up the face before eventually running out of low energy seams.

Deliverables

There is nothing to submit. Complete findVerticalSeam and get checked off by your TA during lab.

Credits

This assignment was originally developed by Josh Hug, with supporting development work by Maia Ginsburg and Kevin Wayne at Princeton University.