Assignment 9 ©2011 Felleisen, Proulx, Chadwick, et. al.
Due: 3/23/2011 @ 10:00pm
Practice problems help you get started, if some of the lab and
lecture material is not clear. You are not required to do these
problems, but make sure you understand how you would solve
them. Solving them on paper is a great preparation for the exams.
Color processing
The class ImageReader allows you to read any .bmp or .png file and analyze the individual pixels. The constructor expects the name of the file to be read. It reads the file and initializes the value of the width and height fields for the given image.
The method Color getColorPixel(int x, int y) returns the color value of the pixel at the given location. You can extract the red, blue, and green component of the color as integers using the methods
c.getRed() c.getGreen() c.getBlue()
Create a negative of the given Flowers.png image. Explore
other ways of manipulating the images and document your exploration.
To create new images and save then as .png files, use the given class ImageBuilder. It works as follows:
The constructor also initializes the field BufferedImage image that is ready to receive the data needed to represent the resulting image. You need to supply the height and the width of the image.
The method setColorPixel (x, y, r, g, b) sets the color of the given pixel in the image to the specified RGB shade.
The method public void saveImage(String filename) saves the image you have created in the .png format — it adds the .png to the filename you specify.
Note: The class ImageBuilder2 works the same way as ImageBuilder, but in addition it displays the image as it is created in a Canvas. To use this class you need to import the old libraries: idraw.jar, geometry.jar, and colors.jar.
This part of the assignment will act as a multiplier for the grade for this assignment. If you fail to do this part, the grade for the entire assignment will be zero. If you fulfill this part of the assignment, the grade for this assignment will be computed in the usual way, based on the remaining three problems.
To get a passing grade for this part, you must meet with your TA during the next two weeks (prior to 7 April 2011) and go with him over the code in some of your previous homeworks, especially the Chicken Game. Please, look at the wiki, where the TAs are posting their availability, email you TA to schedule an appontment, or talk to your TA during the lab. The TA assignments are posted on the wiki with the pair assignments.
Our goal is to train our computer to be a mock psychiatrist, carrying on a conversation with a patient. The patient (the user) asks a series of questions. The computer-psychiatrist replies to each question as follows. If the question starts with one of the following (key)words: Why, Who, How, Where, When, and What, the computer selects one of the three (or more) possible answers appropriate for that question. If the first word is none of these words the computer replies ’I do not know’ or something like that.
The file ElizaSample.txt shows you what a sample interaction sequence may be.
Start by designing the class ReplyToQuestion that holds a keyword for a question, and an ArrayList of answers to a the question that starts with this keyword.
Design the method randomAnswer for the class Reply that produces one of the possible answers each time it is invoked. Make sure it works fine even if you add new answers to your database later. Make at least three answers to each question.
Design the class Eliza that contains an ArrayList of ReplyToQuestions.
In the class Eliza design the helper method firstWord that consumes a String and produces the first word in the String.
The following code reads the next input line from the user. You will need to find out what was the first word in the patient’s question. Look up the documentation for the String class (and we gently hint that the methods trim, toLowerCase, and startsWith may be relevant).
System.out.println("Type in a question: ");
s = input.nextLine();
Make sure your program works if the user uses all uppercase letters, all lower case letter, mixes them up, etc.
In the class Eliza design the method answerQuestion that consumes the question String and produces the (random) answer. If the first word of the question does not match any of the replies, produce an answer Don’t ask me that. — or something similar. If no first word exists, i.e., the user either did not type any letters, or just hit the return, throw an EndOfSessionException.
Of course, you need to define the EndOfSessionException class.
In the Interactions class design the method that repeats asking questions and providing answers until it catches the EndOfSessionException — at which time it ends the game.
We have seen the recursively defined insertion sort algorithm both in the first semester and also recently, using the recursively defined lists in Java.
The main idea behind the insertion sort was that each new item has been inserted into the already sorted list. We can modify this as follows:
Design the method sortedInsert that consumes a sorted ArrayList<T> a Comparator<T> that has been used to define the sorted order for the given list, and an item of the type T. It produces a sorted ArrayList<T> by adding the given item to the ArrayList<T>, preserving the ordering.
Note: Be careful to make sure it works correctly when the given ArrayList is empty, and when the item is inserted at the end of the ArrayList.
Design the method insertionSort that consumes an arbitrary (unsorted) ArrayList<T> and a Comparator<T> and produces a new sorted ArrayList<T> as follows:
It starts with an empty sorted list and inserts into it one by one all the elements of the given ArrayList<T>.
Note: It is a bit more difficult to define the insertion sort algorithm so that it mutates the existing ArrayList in place.
Extra Credit
Design an in-place insertionSort method. You will get the credit only if the design is neat and clearly organized.
Note: Of course, the algorithms will be defined in the Algorithms class with examples of use in the Examples class.
We ask you to work with with image data, and learn two simple techniques for enhancement of images defined by pixel shades. Additionally, you will learn how secret images can be encoded in an image, and explore the power of colorization of images.
You will read images data files of NASA images of the planet Mars,
display the images as received from the Viking Explorer, and by
manipulating this data generate enhanced images.
Read the following tutorial/explanation of the techniques you will use. The detailed description of the classes and methods you should design is at the end of the tutorial.
The data in the files mg20s002, mg20s007, etc. came from a NASA jukebox of planetary images. Each file starts with several lines of text (a label) that identifies the image - the location on Mars, the resolution (how large an area is represented by one pixel), what spacecraft took the image, and the information about the size of the image data (number of lines and the number of pixels per line). After the label is histogram data - specifying how many pixels there are of each shade (gray shade, just like the color shades, has values in the range from 0 to 255). The last part of the file contains the image data: each pixel is represented as one byte.
Your program that manipulates the images should use the given library class MarsReader. You will use the following functionality of the class MarsReader:
The constructor for MarsReader looks for the original Mars image file, reads the file labels and stores them in the field labels.
The constructor then initializes the field BufferedInputStream bytestream to deliver the bytes of the selected image.
To create new images and save then as .png files, use the given class ImageBuilder. It works as follows:
The constructor also initializes the field BufferedImage image that is ready to receive the data needed to represent the resulting image. You need to supply the height and the width of the image.
The method setColorPixel (x, y, r, g, b) sets the color of the given pixel in the image to the specified RGB shade.
The method public void saveImage(String filename) saves the image you have created in the .png format — it adds the .png to the filename you specify.
Each pixel shade is represented as one byte. You can read one byte of data from the bytestream using the method
int read()
The integer will be in the range from 0 to 255.
All images in this collection have the same size: 320 lines of 306 pixels in each line. You can set the color of each individual pixel in the BufferedImage image using the method
void setColorPixel(int x, int y, int r, int g, int b)
A ’black and white’ image is represented by pixels of different shade of gray. By choosing setColorPixel (x, y, s, s, s) with values of s ranging from 0 to 255 we can represent 256 different shades of gray.
In pictures of low quality the range of the shades is often much
smaller than 256. For example, in the images from Mars most of the
shades are in the range between about 70 and 170, leaving more
than half of the shades unused. Image enhancement methods take
advantage of this deficiency.
Linear scaling.
The first method uses linear scaling to modify the shade of each pixel. It starts with computing the minimum and maximum of the existing shades. It then scales each shade so that the range of shades is expanded to 256 values. The scaling formula is:
newshade = (oldshade - min) * (255 / (max - min));
That means that in our example (the range between 70 and 170),
oldshade=70 would be represented as newshade=0,
similarly, oldshade=170 would be represented as 255,
and finally, oldshade=100 would be represented as
(100 - 70) * (255 / (170 - 70)) = 30 * 2.55 = 76.5 , or
newshade=76:
| old shade | new shade 70 | 0 170 | 255 100 | 76.5 |
We do not want to do this computation for every pixel over and over again. Instead, we should save the computed values in a table indexed by the oldshade values with the newshade values in the table.
Implement the linear scaling image processing and observe the impact
on the original image.
Histogram equalization.
The second method is called histogram equalization. Histogram equalization is simply a transformation of the original distribution of pixels such that the resulting histogram is more evenly distributed from black to white.
We start by computing the distribution of the pixel shades (a frequency array or a histogram H). Histogram is a simple count of the number of occurrences of each pixel shade (a frequency chart). (For example a histogram of rolling a die 100 times may tell us that we rolled 1 15 times, 2 18 times, 3 17 times, 4 12 times, 5 15 times and 6 13 times.)
We start by reading all pixel data and building the histogram. Let us
assume that hi is the number of pixels of the shade i and that
h is the count of all pixels in the image.
We compute the scaling factor si of each pixel initially
at gray level i as:
si = (1/h) * sum(h0, h1, h2, ..., hi)
where h is the total number of pixels and hi is the number of
pixels at gray level i (i.e. the histogram data).
Once we have the scaling factors, we compute newshadei = 255 * si
Of course, again we do not want to keep recomputing these values and store them in a lookup table instead.
Include in your program a visual display of the histogram you have computed to verify that our assumptions about the color distribution are correct.
Note: You will need to read the Mars data file twice - first
just to compute the histogram and set up the mapping of old shades to
new ones, the second time, reading the old shades and writing the new
shades into the output file.
Create a project MarsImages and include the files MarsReader.java, ImageBuilder.java. Include in your project a class MarsAlgorithms where you will implement several image processing algorithms.
Design the method setMinMax that will read a Mars image data and determine the minimum (greater than 0) and the maximum shade in the image, i.e. ignore the shade 0 and save the values.
Design the method buildLinearScaleMap needed to implement the linear scaling algorithm described earlier. The method consumes the minimum and maximum shade you have computed and produce an ArrayList pixelMap that can be used as a lookup table as follows. If the linear scaling algorithm changes the shade p - old to shade p - new, then the value of the pixelMap.get(p-old) will be p-new.
Design the method enhanceMars that reads a Mars image, processes the pixel data and displays (and saves) the image enhanced by deploying the linear scaling algorithm.
Your method should read the Mars image file and create a new image using the ImageBuilder or ImageBuilder2.
Design the method computeHistogram that consumes the Mars image data and produces an ArrayList of frequencies for each color of the pixel (i.e. an ArrayList of size 256.
Design the method that will display the histogram as a bar chart in a Scene.
Design the method that will consume a histogram for 256 pixel shades and produce an ArrayList pixelMap that can be used as a lookup table as follows. If the histogram equalization algorithm changes the shade p - old to shade p - new, then the value of the pixelMap.get(p-old) will be p-new.
Add the code needed to produce an even better Mars image file by processing the byte data using thehistogram equalization algorithm: at this point all you need to do is replace each shade by the shade defined by the pixelMap.
Note that you will need to read the Mars data twice.
The idea for this lab came from the book by Robert S. Wolff and Larry
Yaeger, Visualization of Natural Phenomena, Springer Verlag
1993 (TELOS Series)
Thanks also to Peter Ford from MIT who helped us locate the original
image data file.
In 1999, The Viking Orbiter and other planetary data files could be found at
ftp://pdsimage.wr.usgs.gov/cdroms/
We suggest using the files in vo_2002 that start with mg. For example:
ftp://pdsimage.wr.usgs.gov/cdroms/vo_2002/mg25sxxx/mg25s022.img
These files are relatively small, about 100K and contain images that are approximately 300 by 300 pixels. See
ftp://pdsimage.wr.usgs.gov/cdroms/vo_2002/volinfo.txt
for a description of the file format.