cis120 HW09 - Image Processing

In this homework, you'll be implementing a tiny programming language for processing images. You'll be writing an interpreter, a program that reads in source code and runs it. We've given you a few files:

Do not edit any file other than Interpreter.java; you can add other files, though. You'll be submitting a zipfile containing Interpreter.java and any other support code you've added; we'll overwrite our own versions of the other files above.

You'll implement the interpreter in three parts. First, you'll write an interpreter for a simple language without variables or functions. This part will require you to work with bitmaps—two-dimensional arrays of color values—a standard model for images.

load(http://www.cis.upenn.edu/~mgree/zfat.jpeg)

blur(3)
rotate(ccw)
flood(255,0,0,30,30)

save(zfat.jpeg)
(The resulting file: zfat.jpeg.) Next, you'll extend your interpreter to support variables.
michael = load(http://www.cis.upenn.edu/~mgree/zfat.jpeg)
steve = load(http://www.cis.upenn.edu/~stevez/steve-new2.jpg)
  
blurrysteve = blur(steve,3)
save(blurrysteve,blurry.png)
michael = rotate(michael,cw)
michael = rotate(michael,cw)
save(michael,upsidedown.jpg)
(The resulting files: blurry.png and upsidedown.jpg.) Finally, you'll implement a simple form of functions, without parameters or return values.
fun f {
  img = blur(img,20)
  img = flood(img,255,255,255,240,125)
}

img = load(http://www.cis.upenn.edu/~mgree/zfat.jpeg)
call f
save(img,michael.gif)
(The resulting file: michael.gif.)
TIP: Read over the whole assignment before starting to code.

Grading

Here's the grade breakdown:
Basic commands (55%)
Variables (25%)
Functions (20%)
We'll be testing both parsing and functionality. You have two free submissions, after which there will be a five-point penalty for each extra submission.
TIP: Focus on getting your commands working right, then add variables. Try to only do one thing at a time: writing the parser, writing the image processing code, adding variables, etc.

Overview

We've provided a GUI interface that will make it easier to test your code, along with some support for handling images. The GUI, defined in GUI.java, is quite simple.


The UI
You can write code in the box; pushing "Run" will execute the code and display the final Picture that was calculated. If there's an error, it will be displayed above the "Run" button. Our GUI interacts with your interpreter by means of an interface Interpretable, with a single method, Picture interpret(Reader src) throws ParseException. You'll implement this interface with the Interpreter class.

The Picture and Pixel classes encapsulate all of the basic image management you'll need. The Picture class wraps up the Java library support for image processing. You won't be working with Java's image support directly; instead, you'll process bitmaps. A bitmap is an array of color values—pixels. Our Pixel class models 8-bit RGB pixels. That is, they comprise three ints, indicating the amount of red, green, and blue with values ranging from 0 to 255. Lower values mean less color, higher mean more. They are 8-bit pixels because 28 = 256, and each component of the pixel can assume 256 different values. They are RGB pixels because the colors are stored in that order: red, green, blue. So new Pixel(255,255,255) represents white, new Pixel(0,0,0) is black, and new Pixel(0,255,0) represents green. Bitmaps are indexed from left to right and from top to bottom.

0 1 2
0123 0123 0123
Left-to-right, top-to-bottom pixel layout for a 3 x 2 bitmap
Each dotted box is an array; each red box is a pixel
The numbers are the index in the array
In the figure to the left, each dashed box represents an array. The top-level array holds each of the columns of the image, in left-to-right order. Each column array holds the pixels of that column, in a top-to-bottom order. This layout is convenient because it puts the origin in the top-left corner, and lets us index a bitmap in x-y order.


A result window

Java offers a variety of classes for working with a wide variety of different image formats. In order to simplify the interface, we've wrapped up the tricky bits of this code in a class called Picture. The Picture class makes the image data available to you via the getBitmap method, which returns a bitmap corresponding to the Picture's contents. In general, you'll take a Picture p, get its bitmap via p.getBitmap(), and then finally construct a new Picture using the appropriate constructor. The interpret method ultimately returns a Picture, which will then be displayed in a result window. (We've shown the result of running the program in the screenshot of our GUI, the third example above.)

Step 1: image processing operations

Your first task will be to implement an interpreter for the core graphical operations of our language. Your interpreter has two jobs: parse the input program and run the commands. The general format of commands is as follows. Each command appears alone on a line, with (optional) whitespace before or after it, but not inside. Blank lines are ignored, lines that don't parse as any command are an error, raising ParseException. There are five commands: load, save, rotate, blur, and flood. Each command has a slightly different format.

To implement the command parsing, you'll have to break the input into a series of lines. Look at each line and try to see if it matches a command. (There are many ways to do this. One general way to do it is to use regular expressions, using the Pattern class. There will be a lab on regular expressions on Thursday, November 18th.)

TIP: Focus on one thing at a time. Either start by implementing and testing the operations, or by implementing all the parsing with dummy operations. It will be much easier if you only try to do one thing at a time.

File operations: load and save

The first two primitives you should implement are load and save. Their format is simple. For load, you can simply write the URL or filename you'd like to load. For save, you write the filename you'd like to write to. The following program, for example, loads an image off of a website and saves it to the hard drive.

load(http://www.cis.upenn.edu/~mgree/zfat.jpeg)
save(zfat.jpeg)
The underlying read and write operations are already implemented in the Picture class, so your interpreter should just use those.

Rotation

The rotate command takes an argument indicating the direction of rotation: cw is for clockwise, ccw is for counterclockwise. It will perform a 90° rotation in the given direction.

rotate(cw)
rotate(ccw)
Implementing this command will require you process bitmaps. To figure out how to implement the two rotations, consider the following bitmap, where we've numbered each pixel with its coordinates:
(0,0)(0,1)(0,2)(0,3)... (1,0)(1,1)(1,2)(1,3)... (2,0)(2,1)(2,2)(2,3)... ... ... ... ... ...
Original array, pixels numbered with coordinates
Rotating this bitmap will produce a bitmap with the following renumbered coordinates.
TIP: An n x m bitmap will rotate to an m x n bitmap.
............ (0,3)(1,3)(2,3)... (0,2)(1,2)(2,2)... (0,1)(1,1)(2,1)... (0,0)(1,0)(2,0)...
...(2,0)(1,0)(0,0) ...(2,1)(1,1)(0,1) ...(2,2)(1,2)(0,2) ...(2,3)(1,3)(0,3) ...... ... ...
Clockwise rotationCounter-clockwise rotation
Your job is to implement this "renumbering", copying pixels from their old coordinates to their new coordinates.
TIP: Remember that you can only change Interpreter.java—don't add any methods to Picture.java! You can add new classes if you like.

Blurring

The blur command takes an argument, a radius. There are different blurring algorithms; we'll implement simplest, called a box blur. Box blurring works by averaging the box-shaped neighborhood around a pixel. The size of the box is configurable by setting the radius, half the length of a side of the box.

blur(3)
blur(1)
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).
(0,0)(0,1)(0,2)(0,3)... (1,0)(1,1)(1,2)(1,3)... (2,0)(2,1)(2,2)(2,3)... ...............
Box blur neighborhood around (1,1), radius 1
Each component should be averaged separately. For a radius R, we set component c at location (x,y) according to the formula at the right.

The general equation for blurring
R is the radius
c′x,y is the new value for component c at position (x,y)
Each pixel has three components: red, green, and blue
This equation disregards 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. If a radius less than 1 is given, you should throw an exception.

Flood fill

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. Since we don't have users, the flood command must specify the coordinate. The sample result window above shows the result of the following program, which performs a flood fill of the color white at the coordinate (240,125).

load(http://www.cis.upenn.edu/~mgree/zfat.jpeg)
blur(20)
flood(255,255,255,240,125)
The first three values are the red, green, and blue components of the color. The next two values are the x and y coordinates.

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 L containing just the point (x,y).
  3. Take the first point p out of L.
  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 same color as target. If they do, add them to L.
  6. If L is empty, stop. Otherwise, go to 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?

Return values and exceptions

The interpret method must return a Picture. This should be the last Picture handled by the interpreter: i.e., the result of the last command. If there were no commands involving pictures, your interpreter should return null.

Occasionally, your interpreter will encounter malformed input. When this occurs, it should raise a ParseException.

Step 2: variables

Now that you've implemented the basic graphical operations for your interpreter, you must add variables. This changes both the format of the commands as well as how their interpretation.

michael = load(http://www.cis.upenn.edu/~mgree/zfat.jpeg)
steve = load(http://www.cis.upenn.edu/~stevez/steve-new2.jpg)

blurrysteve = blur(steve,3)
save(blurrysteve,blurry.png)

michael_1 = rotate(michael,cw)
michael_2=rotate(michael_1,cw)
_ =  flood(michael_2,255,255,255,20,20)

save(michael_2,upsidedown.jpg)
All variable names are sequences of one or more of the following characters: [a-zA-Z_0-9]. (In the Pattern regular expression language, this set of characters is abbreviated as \w.)

All commands except save must now begin with variable name, followed by (optional) whitespace, an equal sign, more (optional) whitespace, and then the command—which now takes a variable as its first argument. Just as before, no whitespace can occur inside of commands.

In addition to this new command format, you need a data structure—an environment—to keep track of the values of variables. If the user attempts to use a variable that hasn't yet been initialized, you should raise a RuntimeException (or some subclass thereof).

Step 3: functions

Finally, you must implement a simple form of functions. The syntax is as follows:

fun profs {
}
 
fun profs {
  prof1 = load(http://www.seas.upenn.edu/~cis120e/images/bcpierce.jpg)
    prof2 = load(http://www.seas.upenn.edu/~cis120e/images/stevez.jpg)
 }
 fun staff{
call profs
ta1 = load(http://www.seas.upenn.edu/~cis120e/images/luchen.jpg)
ta2 = load(http://www.seas.upenn.edu/~cis120e/images/rmenezes.jpg)
ta3 = load(http://www.seas.upenn.edu/~cis120e/images/mgree.jpg)
}
call staff
save(prof1,benjamin.png)
There are a few things to note. Functions are introduced by the form fun name { alone on a line and terminated by } alone on a line. All whitespace is optional, except that there must be exactly one space between the keyword fun and the name of the function being defined. Functions are called with the call name command, where there is at least one space between the command and its argument. Functions shouldn't be immediately evaluated. The snippet above defines two functions; if you run it on its own, nothing will happen. The code inside of a function should not run until that function is called. If functions are defined twice, only the later definition counts. It is illegal to nest functions inside of other functions. That is, the following code should raise a ParseException:
fun this {
  fun isnnot_allowed {
  }
}
No other parsing needs to be done in functions, e.g., a malformed command in a function shouldn't raise a ParseException until the function is called.

Your job here is to figure out how to parse functions—without evaluating them too early. Once parsed, you'll need to keep track of the mapping from function names to function bodies. When you encounter call name, look up name's body and start evaluating it.

Submission

Submit files.zip containing only:

Do not put InterpreterTest, PictureTest, or any of the other provided files (Pixel, Picture, GUI, Interpretable, ParseException) in the zip file.