Part 2a: Compute Energy

Implement the following methods for energy:

• private int getEnergy(int x, int y)
  is similar to luminosityOfPixel but returns the edge-energy of this Picture at Pixel (x,y).
  Implement this before energy(). A lot of people have the problem that they call luminosity() H*W times, but luminosity() already requires H*W steps!

• public Picture energy()
  should return the edge-energy image, as described below

Energy and Differences

The key idea in seam-carving is finding the edge-energy-minimizing path through the image. But what is this ”energy”? Intuitively, the strength of the edges around a particular pixel is that pixel’s ”energy.” High-energy pixels are ones at a strong edge in the image – those are pixels we’re most likely to notice if they disappear. Low-energy pixels are those in the middle of uniform patches of color or gray – those are least likely to be missed! To quantify this idea of ”energy,” we use simple approximations to the image derivative, which is simply how fast the luminosity is changing between adjacent pixels. If we abbreviate the luminosity at point (x,y) as i(xy). Moving horizontally, we can numerically approximate the horizontal derivative (rate of horizontal change in intensity) at (x,y) with any of three methods:

• The forward difference:

i(x + 1, y) − i(x, y)

• The backward difference:

i(x, y) − i(x − 1, y)

• The central difference

2i(x + 1, y) − i(x − 1, y)

Vertical derivatives are similar. For example the vertical central difference would be computed as:

2i(x, y + 1) − i(x, y − 1)

Although the central difference is the most accurate approximation numerically, Avidan and Shamir (the paper authors) simply used the forward energy, which is what we will do. The Seam Carving paper defines the energy at each pixel to be the sum of the absolute value (Math.abs) of two derivatives: the horizontal and vertical rates of change in luminosity. Specifically, you should use the forward difference for both the horizontal and vertical directions:

energy = abs(i(x + 1, y) - i(x, y)) + abs(i(x, y + 1) - i(x, y))

except when the pixels are on the edge of the image so that they do not have a ”forward” neighbor, either x+1 and/or y+1. Whenever one of those cases happens, your implementation should use the backwards difference. For one pixel (the lower right corner), you’ll need to use two backwards differences.

You might find the method showDifferences(Picture p) helpful. It makes differences between two pictures red. You can view that picture on the screen using explore().

In Picture.java there is a main method at the bottom of the class. You can try the following during your debugging:

public static void main(String[] args)
{
    Picture picTiny = Picture.loadPicture("Tiny.bmp"); 
    Picture picCorrect = Picture.loadPicture("TinyEnergy.bmp"); 
    Picture picTest = picTiny.energy();

    Picture picWithDifferences = picCorrect.showDifferences(picTest); 
    picWithDifferences.explore();
}

Tests

When you complete this part, all of the tests from PictureTest_Energy.java should pass.You might find the method printEnergy() helpful because you can compare the output to the correct output shown in class.