Course: CIS451/651; Data Compression in Multimedia
Professor: Paul D. Amer
Semester: Spring 2013
Title: Project 1 - Using Sayood's Software; and Difference Images

Goals:

1. to install and become familiar with Sayood's compression software.
2. to become familiar with 256X256 grayscale and grayscale difference images in both raw and "meta-data" formats.
3. to use Huffman encoding on grayscale images and difference images
4. to become familiar with "seeing" the contents of non-ASCII files using the octal dump (od) command (in this case, the files contain 8-bit unsigned integers)

Tasks:

0. (0 pts) Throughout the semester, students will need to use C programs and data developed by Khalid Sayood, the textbook’s author. Download and install Professor Amer's version of Sayood's software and data to a machine of your choice. Amer's version is archived (using 'tar') and compressed (using 'gzip'), and is located in www.cis.udel.edu/~amer/CISC651/Sayood/Amer451-651VersionOfSayoodSoftware.tar.gz After you download this file, uncompress it, and then untar it. Then use the Makefile (located in the programs subdirectory) to compile all of the code for your machine. You can compile everything using "make -f Makefile all" A README file explaining the software and data is in www.cis.udel.edu/~amer/CISC651/Sayood/software/READMe-by-Amer
   
   
1. (20 pts) Required for all students - Huffman Encoding and Difference Images
• Section 3.10; Projects and Problems 2a and 2b (part 2c is extra credit and highly encouraged - see below)
• For Problem 2b, you must write a program "ComputeDifferenceImage" in the language of your choice that outputs a "difference image". For example, if the input is "sena.img", then ComputeDifferenceImage will output a file named "sena-diff.img".
• To generate a 256 X 256 difference image, assume the original ".img" file consists of pixels x₀, x₁, x₂, ..., x₆₅₅₃₅ (i.e., treat the 256 rows as a continuous 1-dimensional vector).
• Create each difference between each pair of adjacent pixels "x_i - x_i-1" as an 8-bit unsigned value (i.e., in the range [0,255].) Note that a computed difference of -1 is equivalent to a difference of +255; -2 is equivalent to +254, ..., -255 is equivalent to +1. In a decoder, if the difference +1 were added to a current pixel of 255, the next pixel would be 0. In other words, an all-white pixel (255) is "adjacent" to an all-black pixel (0). (Since an unsigned byte has only 8 bits of significance, adding 1 to the byte 11111111 results in 00000000 by ignoring overflow.)
• For this assignment, you are NOT required to write a decoder, but you might do so to help verify that your coder operates correctly. (see extra credit below)
• To compute the first pixel difference x₀ - x_-1, assume a "virtual" pixel x_-1 = 128.
• (submit) A hard copy of your well-commented, perfectly-indented program that computes a difference image. Source code listings with inconsistent indentation or lines that wraparound thereby making the program unreadable will be returned without grading. (See Amer's Coding standard for suggestions on commenting and indention here). Your program may be written in the language of your choice. (Note: you will use this program again in Chapter 11's homework and in Project 4.)
• (submit) Report the size of all Huffman-encoded original and Huffman-encoded difference image files in bytes, not in KB.
• (submit) As requested in the problem, comment on how well the original and difference images compressed using Huffman encoding.
• (submit) Submit a hard copy of the beginning of each image file's contents using the octal dump "od" and "head" commands as follows: [Note: you are encouraged to experiment with the many switches of the "od" command; "od" is useful for being able to see what non-ASCII files looks like in difference ways.]
      od -Ad -t u1 sena.img | head -10
      od -Ad -t u1 sena-diff.img | head -10
      od -Ad -t u1 sinan.img | head -10
      od -Ad -t u1 sinan-diff.img | head -10
      od -Ad -t u1 omaha.img | head -10
      od -Ad -t u1 omaha-diff.img | head -10
• (think about, do not submit) Why in general does a difference image Huffman-encode to a smaller file than the original image?
• (think about, do not submit) Can you specify an image which will Huffman-encode to a smaller file than its difference image will Huffman-encode to?
• (think about, do not submit) Can you improve on the way a difference image is computed above that would, in general, result in a smaller Huffman-encoded difference file?


2. (4 pts) Required for 651 students; Extra Credit for 451 students - Using the Wrong Codebook
• (submit) Section 3.10; Projects and Problems 3 - submit your resulting file sizes, and comment on the results.
• if you get a segmentation fault when encoding the bookshelf1 image using the codebook generated by the sinan image, you probably downloaded and installed Sayood's software from his web site (as opposed to AMER's version). In that case, you need to see me about making two small corrections to Sayood's code in huff_enc.c and sub.c.


3. (4 pts) Required for all students - Seeing an Image Next to its Difference Image
   • use your favorite image software (e.g., I recommend you install Irfanview, or GIMP) to view the original sena, sinan, and omaha images, and their difference images on your computer. Most commercial software (including Irfanview, xv, GIMP) have never encountered a Sayood raw image file (filename postfix ".img".) Sayood's raw image format is not a standard, or even widely-known image format. To view an ".img" image, convert the ".img" file to the well-known ".pgm" file format using Sayood's program "convpgm.c", and then view the ".pgm" file. (You will need to convert and view ".img" images in future assignments.)
   • (submit) Print out a few images next to their difference images.
   
   
4. (4 pts) Required for 651 students; Extra credit for 451 students - Adaptive Huffman Coding
   • Section 3.10 - Projects and Problems 2c
   
   
5. (4 pts) Required for 651 students; Extra Credit for 451 students - Reconstructing the Original Image
• Program a decoder "ConvertDifferenceImageBackToOriginalImage" thus producing sena-diff-reconstructed.img
• (submit) Submit a hard copy of your code, and an executed script that demonstrates your program works. (Hint: use a command such as the Unix "diff" command to verify that XXX.img and XXX-diff-reconstructed.img are identical.)

Notes

1. Graduate students must do this assignment individually. Undergraduate students may collaborate in groups of 2 for this assignment. Only one submission with both names should be turned in from a group.
2. Clearly label your answers, and please submit answers in the order assigned.
3. (repeated from course syllabus) Academic Honesty: Unless explicitly stated otherwise, students are not permitted to access or compare any homework, or program-project answers with those of any other student or group past or present, alive or dead, or any Internet web site prior to submitting the assignment. Comparing answers, or getting answers off the Internet before submitting one's work is considered cheating. If you do not have time to complete an assignment, it is better to submit partial solutions than to get answers from someone else. While it is obviously difficult to enforce this policy, students who do not follow this policy should be keenly aware that in this class, they a re cheating, and if caught, will be prosecuted according to University guidelines. This applies both to the student (or group) who gets answers and the student (or group) who gives answers.
4. (repeated from course syllabus)  Lateness Policy: Assignments are due at the beginning of class. Unexcused late assignments will be penalized up to 10% per school day (weekends do not count) up to a 2-day maximum penalty of 20%. Without prior discussion with the professor, assignments will not be accepted more than two school days late without a university approved excuse.