CS 242 Fall 2010 : Assignment 1.3

This page last changed on Sep 13, 2010 by m3rabb.

Compressing Images

Objective

  • Implement a file compression scheme for bitmap images using your bit library

You will implement a compression algorithm and your own file format so you can:

  • Save images in your new format
  • Open images from your new format
  • Represent bitmaps on disk as files that are smaller than .bmp files (i.e., the files should actually be compressed)
  • Answer questions about trade-off decisions you made while devising or implementing your algorithm

Hand-in requirements

  1. Make sure the name of the directory is Assignment1.3. This is very important. We are using a script to do the svn export and it is important that the name matches.
  2. This assignment is due in SVN by 8:00 AM on Thursday, September 16th.
  3. Do not check in any executables, debug logs, or automatically generated doc. If anything can be regenerated, it should not be checked in.
  4. Have a README that describes how to use your program. Make sure to include three things you would like to improve (i.e. three things you think you did poorly)
  5. Include the Bit Manipulation library with your submission since the compression feature is supposed to be integrated with it. But be sure to indicate in your README which files are responsible for actually doing the compression.

You must make use of your Bit Manipulation Library from assignment 1.1. Hopefully you wrote enough tests to be confident of your library, but feel free to fix any bugs you find

Sample Data

We have provided you with some sample bitmaps of substantial dimensions so that you can investigate how various compression techniques work on different types of images. Based on the techniques you decide to use, you should see varying compression ratios for the given images:

All images linked to on this page with the exception of self_portrait.bmp are copyrighted by Russ and Charlie Meyer. Please do not redistribute/sell these images without permission.

self_portrait.bmp is copyright NASA (and is a photo of an Illinois grad, Joe Tanner – B.S. in Mechanical Engineering, 1973)

Do Not check in these images to subversion due to their substantial file size. In eclipse, you can right click on the file, select team, then select ignore to have SVN not commit the files.

Details

The first thing to understand is that images can be thought of as one long array of pixels. From left to right, top to bottom, you have something like “red”, “red”, “white”, “blue”, “yellow”, “black”, “black”, “red” … These colors are usually represented by some fixed-size number from one to four bytes long. Whatever library you used to manipulate your images, whether it was built in or external will almost definitely have methods that allow you to grab these numbers (colors) one after another.

(Suggestion only) Your first objective should be to grab these colors and be able to write them out to disk. You should probably include some kind of header on the file for width and height. This is your own kind of “uncompressed” image format. If the user asks to open one of these files, you can then read in the header, the numbers, and reconstruct the image.

After you have code to grab colors and write/read them from disk, you should learn about some compression method. You are free to use any compression algorithm you devise or read about, but you are not allowed to use a prebuilt compression library. As a recommendation for simplicity, run length encoding will probably be the most straightforward compression, but the benefits aren’t very impressive unless there are large patches of solid color. A much more enjoyable algorithm is Huffman Coding, which is not that much more difficult as far as implementation goes, but can achieve much better results.

Using only 1 compression technique in your implementation is worth 1/2 points, you must integrate multiple techniques for full credit!

You are encouraged to use the newsgroup to ask the TAs and your classmates questions, but to get you started, here are some links:

  • Run length encoding (RLE) on Wikipedia
    Although this presents the basic idea, there are many things to think about with RLE. Should you do it at the bit level (look at runs of 1s and 0s) or at the byte level (runs of ‘A’s, ‘B’s, etc)?
  • Huffman encoding on Wikipedia
    Check out the “Basic Technique” section. Here you have to think about things such as how to generate the frequencies of bytes (or maybe 6 bit chunks? or 12 bits? how many bits are there per pixel?), and encoding the frequency in some kind of header, so you can regenerate the original file from the compressed version.
  • Indexed Color on Wikipedia
  • Compressing Images
    Some information about compressing images specifically.

Your implementation should not be trivial (compressing everything to a single pixel, for example), but we encourage you to play with different kinds of compression.

Running your program

You should write a short main to run your program. You should be able to:

  • compress a given image and write out the compressed version to an arbitrary file
  • read in a compressed image and write out an uncompressed version to an arbitrary file

In addition, you should construct jUnit tests to test that:

  • the compression actually works (the size of the compressed file is smaller than the original)
  • that the image resulting from decompression is identical to the original

Image IO in Java

The basics of image IO in Java are simple if you know what classes to look for. Try the following code sample to open a BMP file

Note that you will have to import some classes (Eclipse will tell you this, but so will I just for completeness):

Since you will be using Java for your implementation, here is some sample code on how to grab pixels from an image:

You can use Java’s ImageIO class to read and write bitmaps, but you must use your BitLibrary to read and write your compressed format.

Passing arguments to Java programs

We DO NOT want you to hard code file names into your main functions (although this is ok for unit tests). When you write a main function in Java, it looks something like:

If you were to invoke your code like:

args[0] would contain “input.bmp” and args[1] would contain “output.bmp”

Although this is ok, it would be better to have a “more standard” arguments format for your program. Consider using a 3rd party library such as JArgs to parse your arguments. This way, you could call your program like:

There is sample code how to use JArgs at http://github.com/purcell/jargs/blob/master/src/jargs/examples/gnu/OptionTest.java.

Adding a 3rd party library to your project in Eclipse
  1. download the jar file for the library
  2. copy it into your project in Eclipse
  3. right click on the jar file, select build path->add to build path
  4. you can then use the library in your code
Adding arguments before running your program in Eclipse

These instructions are based on Eclipse Helios

either:

  1. click on the down arrow next to the play button in the tool bar and select run configurations
  2. find your run configuration (you might need to press the play button on your main first to create a default one for you, its easier that way)
  3. select the arguments tab
  4. add your arguments into the Program arguments text box
  5. if you find you are running out of memory, try adding -Xmx256M into the VM Arguments text box (adjust 256 to the amount of memory you want to allocate to the program)

or

  1. right click on your project
  2. select properties
  3. select Run/Debug Settings
  4. find your run configuration (you might need to press the play button on your main first to create a default one for you, its easier that way)
  5. click edit
  6. select the arguments tab
  7. add your arguments into the Program arguments text box
  8. if you find you are running out of memory, try adding -Xmx256M into the VM Arguments text box (adjust 256 to the amount of memory you want to allocate to the program)

Grading

We will use the standard Grading rubric for this assignment.

Criteria Weight Comment
Basic preparation 1  
Cleverness 1  
Code submission 1  
Decomposition 2  
Documentation 1  
Effort 3  
Naming 2  
Overall design 2 Refer to Grading.
Participation 2 How you critique others code.
Performance 1  
Personal issue 2 You satisfactorily handled any issues from 1.2
Presentation 2 How you critique your code.
Requirements satisfaction 4 You implement 2+ compression methods using your BitLibrary, and all unit-tests pass.
Testing 1  

ferrariF1.bmp (image/bmp)

rothorn.bmp (image/bmp)

self_portrait.bmp (image/bmp)

copenhagen.bmp (image/bmp)

barcelona.bmp (image/bmp)

colors.bmp (image/bmp)
Document generated by Confluence on Feb 22, 2012 18:13

  1. No comments yet.

  1. No trackbacks yet.