For new assignments, you are required to use the CSIL Subversion repository to do your work in. The TAs will have a script that will run at 8:00 a.m. on Sunday when the assignment is due that does a svn export of your most recent code in the repository. If you have not finished by that time, it is your responsibility to e-mail your TA and send your code later by hand. The same late penalty of -5 per hour still applies.
Post questions, concerns and comments to the class newsgroup at class.cs242
Image Editor - Compression
Assignment 8 - October 22, 2006
Due: 8:00AM Sunday, October 29, 2006. In the SVN repository
Language: Any programming language of your choice
Objective:
- Implement a file compression scheme and integrate it into your Image Editor
You will implement a compression algorithm and integrate it with your Image Editor so you can:
- Use the Image Editor to save images in your new format
- Use the Image Editor to 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 tradeoff decisions you made while devising or implementing your algorithm
NOTE: The final project proposal is also due by e-mail before your discussion section.
You are free to use any compression algorithm you devise or read about, but you are not allowed to use a prebuilt 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 dificult as far as implementation goes, but can achieve much better results.
You may want to think about making your compression format general, so you could use it in other applications as a library you plug in. In this case, it should clearly be a lossless compression scheme. You could also make the scheme specific to images, so you get better compression for those kinds of files. If you are only compressing images, you may want to consider lossy compression. Either way, the compression code you write should not be tightly coupled with the Image Editor code itself. It should be something like one call to compress and one to decompress.
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.
- 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.
Grading:
- Technical [16]:
- Can the Editor actually use the format to save files? [5]
- Can it restore them from disk back to images? [5]
- Are the filesizes smaller than straight .bmps? [3]
- Does it work with different sizes of images (i.e., not just 640x480)? [3]
- Style [16]:
- Were comments useful? [3]
- Were meaningful names used for variable, constants, and functions? [3]
- Is the compression code as decoupled from the Editor code as possible? [5]
- Are functions/methods/procedures no longer than 25 lines each? [5]
- Participation [15]:
- Can you explain tradeoffs that went into your design process? [10]
- Is there a particular feature you implemented that goes beyond plain RLE or huffman? Be creative! And be able to explain it to us. [5]
Previous assignments
07_image_editor.html 06_threaded_comments.html 05_parse_metadata.html 04_metadatagenerator.html 03_FSMportfolio.html 02_rasteroptimizer.html 01_rastergenerator.html