Description

“Uh oh…”

Jonah Ryan has just spilled a jug of Lysol mixed with vodka all over the latest publicity photos of Selina Meyer and her team! Some dangerous chemicals must have been in the photos because they’re doing all kinds of strange things: stretching, shrinking, turning bizarre colors. As the only computer scientist working for the Vice President, you must put it all right.

The Mission

In order to reconstruct the images, we need you to write a program that can read in a bitmap file and perform a sequence of modifications consisting of the following seven operations, depending on the commands given by the user.

 

User Command	Operation	Example
i	Invert the colors of the bitmap. If the original color of a pixel was (R, G, B), the new color value should be (255 – R, 255 – G, 255 – B).
g	Make the image grayscale. Set the R, G, and B values for a single pixel to one value. That value should be: .3R + .59G + .11B, rounded to the nearest integer. Note that when the red, green and blue components are all the same, the color is a shade of gray. For example (0,0,0) is black, (255, 255, 255) is white, and (128, 128, 128) is a 50% gray.
b	Blur the image. For each pixel, make each of its color components the weighted average of all the pixels in a two pixel radius, rounding to the nearest integer. For a normal pixel, doing so means adding up the color values for a 5 × 5 square of 25 pixels. (Two rows above and below, two columns to the left and to the right.) The red, green, and blue sums should each be divided by 25. Of course, any pixels which are close to an edge should only average pixels that are part of the image. Thus, a corner pixel will generally be the average of a 3 × 3 square of pixels. (Two rows down and two columns to the right only.) Clever use of loops and counting the number of pixels summed can take care of these edge cases without too much additional code.
v	Vertically mirror the bitmap. Flip the pixels of the bitmap around the x-axis.
s	Shrink the bitmap to half its size in both height and width directions. Because the bitmap will cover 1/4 the area that it did before, you will have to average the color values for four pixels into color values for one pixel. Averaging should be done by converting the values to floating point values, averaging them together, and rounding to the nearest integer. If either the height or width of the image are not even, ignore the last row or column that makes the image odd.
d	Double the size of the bitmap in both height and width directions. You will have to make four pixels have the same color values as one pixel did in the original.
r	Rotate the image 90 degrees to the left (counter-clockwise).

 

If you are in a 3 person group, you have to do the following extra operations:

User Command	Operation	Example
m	Perform a median filter. The purpose of a median filter is to reduce noise. One way to reduce noise is to blur an image by making it a weighted average of itself and its neighbors. Doing so destroys a lot of edge information and makes the image much less sharp. An alternative is to replace the pixel value with the median (rather than the average) of the surrounding pixels. Of course, we can’t find the median of full color values. Instead, we take the median of the red, green, and blue components separately. To implement a median filter, record the values of the R, G, and B values of all of the immediate neighbors of a pixel (including itself) in separate arrays for each color component. For a pixel that isn’t on edge of the image, it and its neighbors will form a 3 x 3 grid (actually, three different 3 x 3 grids, taking each color component separately). Take the nine elements from each grid and sort them. Then, use the middle value for as the new color component. For any pixel that’s on an edge, use the original color value without any filtering. Be sure to make a new set of arrays to hold the resulting image to avoid re-filtering image data.
h	Horizontally mirror the bitmap. Flip the pixels of the bitmap about the y-axis.

 

When your program starts, it should prompt the user for a file to open. If the file is invalid, it should quit gracefully and print an appropriate error message. Next, it should ask the user how many threads should be used. Then, it should run a loop, asking the user to input commands to alter the image. Legal commands are: i, g, b, v, s, d, r, and q to quit. When the q option is given, the program should prompt the user for a file to save the altered image into.

Some sample execution output is given below. User input is given in green.

What image file would you like to edit: image.bmp
How many threads would you like to use: 4
What command would you like to perform (i, g, b, v, s, d, r, or q): s
Command took 0.147 seconds to execute
What command would you like to perform (i, g, b, v, s, d, r, or q): i
Command took 0.014 seconds to execute
What command would you like to perform (i, g, b, v, s, d, r, or q): r
Command took 0.009 seconds to execute
What command would you like to perform (i, g, b, v, s, d, r, or q): q
What do you want to name your new image file: edited.bmp

This sample execution opens a file called image.bmp, shrinks it, inverts its colors, rotates it 90° to the left, then saves it to edited.bmp.

 

Binary Finary

The first task you need to attack is reading in the bitmap. You will need to allocate enough space to hold the data in the bitmap. How can you do that? Well, at the beginning of a bitmap file is a header which gives a lot of information about the file. If we were coding in C or C++, we could dump that data directly into a struct. Unfortunately, Java doesn’t like giving us direct access to memory. So, we’ll have to read everything in piece by piece. If we were using C, the header would be laid out as follows.

unsigned char 	type[2];		// always contains 'B' and 'M'
unsigned int	size;			// total size of file
unsigned int	reserved;		// always 0
unsigned int	offset;			// start of data from front of file, should be 54
unsigned int	header;			// size of header, always 40
unsigned int	width;			// width of image in pixels
unsigned int	height;			// height of image in pixels
unsigned short	planes;			// planes in image, always 1
unsigned short	bits;			// color bit depths, always 24
unsigned int	compression;		// always 0		
unsigned int	dataSize;		// size of color data in bytes
unsigned int	horizontalResolution;	// unreliable, use 72 when writing
unsigned int	verticalResolution;	// unreliable, use 72 when writing
unsigned int	colors;			// colors in palette, use 0 when writing
unsigned int	importantColors;	// important colors, use 0 when writing

If you are interested, there is a good explanation of the file format here.

C works a lot like Java, but there are a few differences. An unsigned char takes up 1 byte of space. An unsigned short takes up 2 bytes of space. An unsigned int takes up 4 bytes of space. Java does not have unsigned types for byte, short, or int (and, confusingly, a char is two bytes in Java). In the header, the unsigned types won’t cause problems since none of them are likely to be large enough to be different in signed representation.

But how do you read them? Java provides a number of ways to read binary data directly from a file, but I recommend that you use the FileInputStreamclass. FileInputStream doesn’t have a lot of frills. The only methods you’ll need are the skip(), read(), and close() methods. The skip() method will skip however many bytes you specify. The read() method will either read a single byte or an array of bytes. The close() method closes the file.

One Little Endian

In the bitmap file format (and on Intel machines in general), values are stored in Little Endian byte ordering. This means that the bytes of an int value are stored least significant byte first. When you go to reconstruct an int from four bytes that you’ve read in, you should use the bitwise left shift operator (<<) to shift each of the four bytes by the appropriate amount and add them together.

The process is similar for a short, except that there are only two bytes to worry about.

For more information, read the Wikipedia article on Endianness.

Writing the Files

When writing the files, create an object of type FileOutputStream. The only methods you’ll need to worry about are write() and close(). One version of the write() method writes a single byte and one writes an array of bytes.

When you write the header of the file, you need to output all the bytes for all the values, using the default values given above for values that you neither store nor can compute. You will need to decompose int and short values into their component bytes, in the correct order, and output them. You should use the unsigned right shift operator (>>>) to do so.

Color Data

The offset member of the header says where the color data starts in the bitmap. This value should be 54, but if it is larger, you should skip bytes after the header until you make up the difference. We will only deal with 24-bit bitmaps. That means that each pixel is represented by three bytes. The first byte is the blue value, the second byte is the green value, and the third byte is the red value. The first pixel that you read in will be the pixel in the lower left-hand corner of the bitmap. As you read in pixels, you will move across the row until you finish the row, then move onto the row above. Although bitmaps are read from the bottom up and with the color values in BGR order (instead of the more standard RGB), neither of these facts should affect your code much. As long as you are consistent, this ordering won’t matter except in the case of image rotation.

You should allocate a 2D array of bytes to hold the color data. Each row should be three times the width of the image. You can read in a whole row at a time using the read() method. Likewise, you can write out a whole row at a time using the write() method.

Unfortunately, it’s not quite that simple. The bitmap standard requires that the number of bytes in a row of pixels falls evenly on word boundaries, in other words, is evenly divisible by 4. If the number of bytes used to represent a row of pixels is not evenly divisible by 4, it will be padded with zeroes until it is. You must read these zeroes in and discard them when getting the bits. Likewise, you have to remember to appropriately repack with zeroes when writing the file back out.

For padding, there are four different possibilities:

1. 1. The bytes in a row is evenly divisible by 4. No padding is needed.
      Example: Width = 100. Given 3 bytes in a pixel, 100 × 3 = 300 bytes in a row. There is no padding.

 

1. 1. The bytes in a row has a remainder of 3 when divided by 4. Padding of 1 byte occurs.
      Example: Width = 101. Given 3 bytes in a pixel, 101 × 3 = 303 bytes in a row. There needs to be 1 byte padding in the row to make 304 bytes.

 

1. 1. The bytes in a row has a remainder of 2 when divided by 4. Padding of 2 bytes occurs.
      Example: Width = 102. Given 3 bytes in a pixel, 102 × 3 = 306 bytes in a row. There needs to be 2 bytes padding in the row to make 308 bytes.

 

1. The bytes in a row has a remainder of 1 when divided by 4. Padding of 3 bytes occurs.
   Example: Width = 103. Given 3 bytes in a pixel, 103 × 3 = 309 bytes in a row. There needs to be 3 bytes padding in the row to make 312 bytes.

Even more bizarrely, the strictest interpretation of the bitmap standard requires the total size of the file to be evenly divisible by 4. Since the header is 54 bytes (not divisible by 4) and the color data is always evenly divisible by 4, you should always output an extra two bytes of zeroes after outputting the color data. Thus, the dataSize that you output should be height × ((width × 3) + padding), and the overall image size that you output should be 54 + dataSize + 2.

Signed vs. Unsigned

The bitmap standard assumes that the bytes representing colors are unsigned, with the range 0 – 255. The Java byte type is signed and interprets these values to be in the range -128 – 127. If you are just swapping byte values around, as you will in the vertical mirroring or rotating operations, this fact is unimportant.

However, for the shrink, grayscale, invert, and blur operations, you have to do arithmetic on the byte values. You should convert them to int values to do your arithmetic. If a byte value is positive, the unsigned version is the same. If a byte value is negative, add 256 to it to get the equivalent. Oddly enough, if you store an unsigned value into a signed byte, its value is stored correctly. So, you only have to do the conversion one way.

If your images look mostly correct but have odd, brightly color noise in some parts, you have probably messed up the conversion to unsigned.

Timing and Concurrency

Your program should time each operation so that you can tell exactly how long it takes. Display this data with exactly three decimal places as shown in the sample output above. The System.nanoTime() method gives high precision time values that you can subtract from each other to find elapsed nanoseconds.

Furthermore, you should write your operations so that they use the number of threads specified by the user at the beginning of the program. These operations, like many kinds of image manipulations, are embarrassingly parallel, having a large amount of data with a clear mapping from input to output. Your threaded code does not need to have any locks or other synchronization tools. Each thread that is spawned should know what data it will write into the output 2D array of bytes. As long as none of the data that the threads are writing overlaps, the threads can run independently without fear.

An easy strategy to adopt is to number your threads. If your program is using four threads, each thread could operate on every fourth row in the image. The amount of data skipped for each thread is called its stride. An alternative strategy is for each thread to operate on blocks of rows. Again, if your program is using four threads with this strategy, the first thread would operate on the first 1/4 of the rows, the second on the second 1/4 of rows, and so on. This strategy can have better cache performance, but it is trickier to implement when the number of rows is not divisible by the number of threads.

Because these operations are memory-access intensive, you may see no speedup from threaded versions. On the other hand, your threaded versions of code should not be markedly slower. For your own development as a computer scientist, it is instructive to see which kinds of images (large or small) and which operations achieve some speedup or are particularly prone to slowdown when using multiple threads.

Hints

• • Start early. This project is tough. Do everything you can to work smoothly with your partner.

 

• • Reading in (and writing out) the bitmap data is a huge part of the problem. Once the data is in, if you have stored it in a reasonable way, doing the actual transformations should be relatively straightforward. It’s a good idea to let one member of the group work just on input and output and the other do the bitmap transformations. Also, you should test your code by reading in an image and then outputting it directly. If it looks exactly the same, you’re on the right path.

 

• • Make sure you test rectangular (non-square) bitmap images, especially with rotation! Code that works for square images without padding has no guarantee that it will work for messier cases.

 

• • You should only read in data from a file once and write it out once. It does not make sense to output the bitmap data to a file after each operation.

 

• • You may need to visualize the bitmaps you are creating to see how you are doing. The Windows image viewers should be sufficient for this purpose. If the image won’t load or doesn’t look right, you have corrupted its header or data somehow. Also, you should try to limit the size of the bitmaps you use for testing since they take up a lot of space.

 

• • Work incrementally. Compile constantly. Get bitmaps inputting and outputting without any operations first. Then, add in a simple operations like inverse. You may want to print out the header information for testing purposes (or at least view it in the debugger).

 

• • Write clean code. You can easily make code so complicated that no one (including your instructor) can figure out why it doesn’t work.

 

• • Do not import any packages other than java.io.* and java.util.Scanner.

 

• • You are expected to create a class called Bitmap to hold bitmap data. Each transformation (such as shrink or double) should have a corresponding member function. Your class should be stored in a file called Bitmap.java. You must also have a main program that reads the commands and reacts appropriately. This class should be called Manipulator and stored in a file called Manipulator.java. You may write other classes if you find them useful.

 

• • Plan out your code ahead of time. Good design saves on coding.

 

• • It is recommended that you first get all the image transformations working without using multiple threads. Once you get them working, then added threading to your Bitmap class.

 

• Refer to the coding standards page for more information on what I’m looking for in terms of style.

Provided Images Files

No Padding Required

• delaware.bmp
• jonah.bmp
• sleeping.bmp

Padding Required

• amy.bmp
• dan.bmp
• maybe.bmp