Homework 6: Pennstagram

In this homework, you’ll be completing a basic photo manipulation program in Java!

Here are the recommended homework checkpoints:

• Checkpoint 0: If you are new to Java, you should have attended the Java Bootcamp on Oct. 28. You can watch the recording here @2242. This will help you start the assignment with a solid foundational understanding of Java.
• Checkpoint 1: You can complete Task 0 now. We recommend you use Eclipse to complete this assignment.
• Checkpoint 2: You can complete Task 1 with the material on Wed 10/28 (Lecture 22) or Chapters 19 and 20.
• Checkpoint 3: You can complete Tasks 2-5 with the material on Fri 10/30 (Lecture 23) or Chapter 21.
• Checkpoint 4: You can complete Tasks 6-7 with the material on Mon 11/2 (Lecture 24) or Chapter 21.

Task 0: Set up your project and browse the files

Setup (Codio Users)

You do not have to download the files for the homework assignment – the Codio box has been configured with them for you.

Setup (Eclipse Users)

Download Eclipse and set up your Java project. To download Eclipse, follow the instructions in our Eclipse set-up guide or in our Eclipse set-up slide deck.

Don’t forget to add JUnit 5 to your libraries!

You can download all the code files here, and import them into a Java project. To run all of your tests or your photo editor while using Eclipse, click the green play button in the upper menu while viewing the respective file. To run a single test, highlight the test name and click the play button. If you are not using Codio, you can download the test images used in ImageTest.java here and you will have will have to modify the path to the test images as described in ImageTest.java.

Project Overview

We’ve given you the GUI for this program and have defined a number of super-fancy photo effects, controlled by buttons on the right-side of the application (“1890s”, “Pin Hole”, etc.). However, these effects don’t quite work yet. They depend on basic photo manipulation algorithms that you must implement. (These basic manipulations are controlled by the buttons on the left-side, provided for your testing convenience.)

We’ve given you a few completed files to get started:

• PixelPicture.java, which manages the reading and writing of image data.
• GUI.java, the simple GUI for the program (which you can run to help you test Parts 3 and 4).
• ColorMap.java, a Map data structure that helps build histograms.
• ManipulateTest.java, a JUnit test file for the image manipulations.
• PointQueue.java, a data structure for managing queues of ints (needed only for the Kudos flood fill problem).

And you’ll have to finish off a few more:

• Pixel.java, which is a point of color in an image. You’ll have to finish a few constructors (Pixel()), getRed(), getGreen(), getBlue(), getComponents(), distance(), toString() and equals().
• MyPixelTest.java, which contains an example test for Pixel. You will need to add your own tests, which will be graded manually.
• SimpleManipulations.java, a collection of simpler image manipulations. You’ll have to finish rotateCCW(), border(), invertColors(), grayScaleAverage(), scaleColors(), and alphaBlend().
• AdvancedManipulations.java, a collection of image manipulations requiring pre-processing of the image or consideration of multiple pixels at once in order to paint a single pixel. You’ll have to finish adjustContrast(), reducePalette(), and blur() (and flood() for Kudos!).
• Effects.java, which implements super-fancy photo effects, based on the basic image manipulations (modified only for Kudos).
• ImageTest.java, a place to put your own JUnit tests.

The JavaDocs for the classes you are working with can be found here, and the FAQ for this assignment can be found here.

Task 1: Pixels

Your first task is to complete the Pixel class. A pixel represents a color and is composed of three ints, indicating the amount of red, green, and blue, with values ranging from 0 to 255. Lower values mean less color; higher values mean more.

To start off, you will need to think of how to store the red, green, and blue values associated with each Pixel object. Keep in mind that every new Pixel created will need to store its own red, green and blue values. In addition, we want to make Pixels immutable. That is, once we create a new Pixel, there should be no way to modify its RGB values.

Once you decide how to store the different values, complete the two different constructors. In order to create a new Pixel, one of its constructors must be called: new Pixel(255,255,255) represents white, new Pixel(0,0,0) is black, and new Pixel(0,255,0) represents green. If a is an array containing the values {0, 0, 255} then new Pixel(a) constructs a blue pixel.

After finishing the constructors, complete the following methods:

• public int getRed()
• public int getGreen()
• public int getBlue()
• public int[] getComponents()
• public int distance(Pixel px)
• public String toString()
• public boolean equals(Pixel other)

Make sure that your implementation is fully encapsulated, in the sense that it is not possible to modify the internal representation of an object except by calling methods from its class. For example, if a client modifies an array obtained from getComponents, the Pixel value should not change.

Pixel Testing

In MyPixelTest.java, write unit test cases for the Pixel class. The TAs will be manually assigning a grade for these, checking to see that you have comprehensively tested each function you wrote.

Pictures

This homework will require you to work with bitmaps — two-dimensional arrays of color values — which are a standard representation for images.

Java offers a variety of classes for working with a wide variety of different image formats. In order to simplify your life, we’ve wrapped up the tricky bits of this code in a class called PixelPicture. The PixelPicture (and Pixel) classes provide all of the basic image management you’ll need. Instead of working with Java’s image processing libraries directly, you’ll process bitmaps provided by this class.

The PixelPicture class makes image data available to you via the getBitmap method, which returns a bitmap of Pixels corresponding to the PixelPicture’s contents. Note that in this application, bitmaps are indexed from top to bottom and from left to right.

In the figure above, each dashed box represents an array. The top-level array holds each of the rows of the image, in top-to-bottom order. Each row array holds the pixels of that row, in a left-to-right order.

This layout is convenient because it puts the origin in the top-left corner, and lets us visualize the 2-d array as (x,y) coordinates.

Note that since we index first by row, we access the array first by its y coordinate and secondarily by its x coordinate. This means that a coordinate at position (x,y) will appear in the array at index bmp[y][x]. This is called row-major form.

Most tasks in this assignment involve taking a PixelPicture p, getting its bitmap via p.getBitmap(), manipulating the Pixels in that bitmap in some way, and then finally constructing a new PixelPicture from the manipulated bitmap using the appropriate PixelPicture constructor.

Implementing the Photo Manipulations

For the rest of the assignment, you will use bitmaps and Pixels to implement some photo manipulation algorithms. The algorithms you are to implement are described in detail in the sections below.

Make sure to test your functions in ImageTest.java. If you are using Codio, follow the instructions found there to run ImageTest and the provided GUI through Codio. If you are using Eclipse, you can run the Gui or the tests by right-clicking on the file and using the “Run As…” menu item. Either way, the only buttons that will work (initially) are “Load new image”, “Save image”, “Undo”, “Quit”, and “RotateCW”. Note that the GUI downloads its initial image from the internet, so make sure that you have the internet available when you run it.

NOTE: For a lot of the assignment, you will be updating individual pixel values. Many (but not all) of the functions require you to divide or multiply by doubles. Since the red, green, and blue attributes of Pixels are ints, you’ll need to do a little work to make sure they are updated with the correct values to pass our tests.

Whenever you need to use doubles in calculations: at the end of your calculations, you must round using Math.round() then cast to int. Like this:

  double d = ...  /* compute a double */
  int val = (int) Math.round(d); /* convert it to an int */

Writing Tests

You can use the files MyPixelTest.java, ManipulateTest.java, and ImageTest.java to test your code (only MyPixelTest.java will count towards your grade). ManipulateTest.java contains a number of simple tests for the basic manipulations and ImageTest.java uses all of the sample images from this page as the basis of its tests. Neither of these files are sufficient, so you should also create additional test cases to help understand, debug, and evaluate your program. For help on how to write JUnit tests for this assignment, look at the provided tests in these test files. The tests verify that your methods return the correct PixelPicture objects by comparing them to simple images constructed from small two-dimensional arrays. The diff method in the PixelPicture class is useful for checking that two PixelPicture objects have the same bitmaps.

The tests in ImageTest.java are based on the picture files included in the images folder in Codio. Note that these tests compare your solution to ours exactly. Because of floating point imprecision, your code may fail these tests but still be correct. These tests will allow you to see how close your solution is to ours.

Finally, beware of image compression effects when comparing two images. Due to image compression, if you save as a jpg or gif, the pixels in the saved image on your hard drive will have slightly altered pixels compared to the PixelPicture object (in memory) that is returned from your manipulation methods. (In the case of gif images, this is due to palette reduction of the same kind as the one you will implement yourself!) Therefore, you always want to compare only saved images to our sample images.

Task 2: Rotation

Change the orientation of an image.

In SimpleManipulations.java, there are two rotation functions: rotateCW() and rotateCCW(), which rotate an image clockwise and counter-clockwise, respectively. Each function rotates the image 90° in the given direction.

We have implemented rotateCW for you; you will need to implement rotateCCW. Implementing this command will require you process bitmaps. To understand the two rotations, consider the following bitmap, where we’ve numbered each pixel with its coordinates:

Your job is to implement this “renumbering”: copying pixels from their old coordinates to their new coordinates.

For this implementation you should fill in the definition of the static method rotateCCW in SimpleManipulations.java. Do not merely call rotateCW three times.

Task 3: Border

Create a new image that adds a border to an existing image.

The next step is to implement the static method border in SimpleManipulations.java. As with rotation, this operation is performed by renumbering, or copying pixels from their old locations to new coordinates. However, this time the new image will be larger than the supplied picture because of the added border.

Task 4: Simple Pixel Transformations

Perform image manipulations that actually require manipulation of Pixel RGB values.

For this task, you will need to implement several basic pixel transformations from SimpleManipulations.java. These manipulations are simple in that they only require you to consider each pixel independently; you don’t have to pre-process the image or consider neighboring pixels. As an example of this kind of transformation, we have given you an implementation of grayScaleLuminosity. You will implement the following transformations:

• Color Inversion: invertColors()

  

• Grayscaling Via Averaging: grayScaleAverage()

  

• Color Scaling: scaleColors() with (1.0, 0.5, 0.5)

  

Color inversion takes each pixel and chooses the “opposite” color of the current one — that is, the one directly across the color wheel.

Grayscaling algorithms transform images from colorful ones to shades of gray; there are several methods of doing this, each of which works best in different situations. We have given you one algorithm and you will be implementing another. An explanation of the specific algorithms can be found in the relevant files.

Color scaling multiplies the color components of each pixel by given scaling values. For example, with the parameters (1.0, 0.5, 0.5), the red components will be unchanged, but the blue and green parameters will be converted to half their value. This has the effect of giving the picture a strong red tint and decreasing the overall brightness.

The transformations you will need to implement all require decomposing each pixel into its three color components: red, green, and blue. Take a look at the included Pixel class for help with this.

TIP: If you have a double value d, you can convert it to an int by rounding and then casting, using the code (int) Math.round(d).

Task 5: Alpha-Blend

Blend the pixels of another image into the current image.

The next picture manipulation, alphaBlend() in SimpleManipulations.java, actually takes two pictures and combines them pixel-by-pixel to produce a new image. Both pictures must be of the same dimensions - if they are not, return the picture provided as the first argument. This algorithm goes through the two pictures computing the weighted average of each of the corresponding pixels in the two images.

The default image blended (alpha = 0.3) with a gray scale (average) version of itself. This blend reduces the color saturation of the image by incorporating gray into each pixel.

Task 6: Advanced Pixel Transformations

For the next operations, work in AdvancedManipulations.java. Each of these transformations requires your to compute additional information about the image before they can be executed.

Contrast

Change the contrast of a picture by implementing the method adjustContrast() in AdvancedManipulations.java.

Your job is to change the intensity of the colors in the picture, following this simple method of changing contrast:

1. Find the average color intensity of the picture.

   1. Sum the values of all the color components in all of the pixels.
   2. Divide the total by the number of pixels times 3 (the number of components). This is the average color intensity.

2. Subtract the average color intensity from each color component of each pixel, resulting in a “normalized” color component. (This will make the average color intensity for the entire image zero.)

3. Scale each normalized color component by multiplying them by the contrast “multiplier” parameter. Note that the multiplier is a double (a decimal value like 1.2 or 0.6) and normalized color values are integers.

   These scaled and normalized color components may be negative or larger than 255, but that is OK! (See below.)

4. Add the original average color intensity back to the scaled, normalized components to create a new pixel. Note that the Pixel class will handle clipping of the resulting components to the range 0-255, as desired.

The default image with contrast multiplier of 2.0.

Reduced color palette

Reduce a picture to its most common colors by implementing the method reducePalette().

You will need to make use of the ColorMap class to generate a map from Pixels of a certain color to the frequency with which identically-colored pixels appear in the image. Once you have generated your ColorMap, select your palette by retrieving the pixels whose color appears in the picture with the highest frequency. Then, change each pixel in the picture to one with the closest matching color from your palette. Use the distance method in the Pixel class to figure out the difference between two pixels.

Algorithms like this are widely used in image compression. GIFs in particular compress the palette to no more than 255 colors. The variant we have implemented here is a weak one, since it only counts color frequency by exact match. Advanced palette reduction algorithms (known as “indexing” algorithms) calculate color regions and distribute the palette over the regions. For example, if our picture had a lot of shades of blue and a little bit of red, our algorithm would likely choose a palette of all blue colors. An advanced algorithm would recognize that blues look similar and distribute the palette so that it would be possible to display red as well.

The default image with a palette reduced to 512 colors

Task 7: Blur

Make an image appear blurry or indistinct.

The blur() method in AdvancedManipulations.java takes one argument, a radius. There are different blurring algorithms; we’ll implement the simplest, called a box blur. Box blurring works by averaging the box-shaped neighborhood around a pixel. Be sure to include this pixel in each average. The size of the box is configurable by setting the radius, half the length of a side of the box.

In the simplest case — a radius of 1 — blurring just takes the average around a pixel. Here, to blur around the pixel at (1,1) with radius 1, we take the average value of the pixels of its neighborhood: (0,0) though (2,2), including (1,1).

This algorithm must be careful of corner cases. When blurring (0,0) with radius 1, we only need to consider the top-left corner, (0,0) through (1,1) — we’ll divide by 4 at the end, not 9. You’ll have to be careful to only access bitmaps inside of their bounds. You can assume that you will not be given a radius less than 1.

The default image blurred with radius 2.

There are very inefficient ways to implement this algorithm. If your solution takes more than 3 seconds to run upon testing, then it is likely incorrect and will timeout upon submission!

A Custom Effect (Kudos Problem I)

At this point you have implemented all of the basic transformations. The effects on the right-side of the GUI should all work, except for the last one. For this effect, you have the opportunity to design your own filter. Take a look at how the effects in Effects.java are implemented and do something cool in the method custom. This part of the assignment is worth no points, but we want to see what you come up with. If you create a particularly nice effect, post the output image (and the source code if you wish) to Ed.

Flood fill (Kudos Problem II)

The last problem is a challenge problem. It is here for additional practice but again worth no points on the assignment.

Finally, there is the flood command. The name is short for flood fill, which is the familiar “paint bucket” operation in graphics programs. In a paint program, the user clicks on a point in the image. Every neighboring, similarly colored point is then “flooded” with the color the user selected.

Suppose we want to flood color at (x,y). The simplest way to do flood fill is as follows.

1. Let target be the color at (x,y).
2. Create a set of points Q containing just the point (x,y).
3. Take the first point p out of Q.
4. Set the color at p to color.
5. For each of p’s non-diagonal neighbors—up, down, left, and right — check to see if they have the color target. If they do, add them to Q.
6. If Q is empty, stop. Otherwise, go to step 3.

Questions you should ask yourself (and not the TAs): what happens when target and color are the same? How can you speed up this naïve algorithm?

For Q, you should use the provided PointQueue class. It works very much like the queues we implemented in OCaml.

Submission

If you are using Codio

Submit hw06-submit.zip containing only:

• Pixel.java
• MyPixelTest.java
• SimpleManipulations.java
• AdvancedManipulations.java
• ImageTest.java

This zip file will be automatically created with the correct files if you use the Zip command in Codio.

If you are using Eclipse

Alternative 1 - Zip your files from Eclipse using the instructions below.

Follow these instructions to create and upload hw06.zip:

• Right click on project, select Export…
• Expand General, select Archive File
• Only select the files listed above (click on arrow in window on left and select files in the window on the right)
• Browse… -> Save as hw06-submit in Desktop/Documents/Downloads
• Select “Save in zip format”
• Finish
• Go to submission site, find file in Desktop/Documents/Downloads and then upload

Alternative 2 - Copy&Paste your code in Codio and zip from there.

You can also copy-paste your java files into Codio (e.g., if you have Pixel.java open, copy-paste that into Pixel.java on Codio and so on for the rest of the files) and create the zip file there.

Grading

Here’s the grade breakdown:

1. Pixel: 13 points
2. Simple image manipulations (rotateCCW, border): 10 points total
3. Simple pixel transformations (color inversion, gray scale average, color scaling): 12 points total
4. Alpha-Blend: 8 points total
5. Contrast: 12 points total
6. ReducePalette: 20 points total
7. Blur: 20 points total
8. Flood fill: 0 (kudos only)
9. Style: 5 points total

You have five free submissions, after which there will be a five-point penalty for each extra submission.