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

Goals:

1. to install become familiar with Sayood's compression software.
2. to become familiar with Sayood's 256X256 grayscale images.
3. to become familiar with 256X256 grayscale difference images.
4. to use Huffman encoding on grayscale images and difference images
5. to become familiar with "seeing" the contents of binary files using the octal dump (od) command

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 compressed (using 'gzip') and archived (using 'tar'), and is located in www.cis.udel.edu/~amer/CISC651/Sayood/software/Amer451-651VersionOfSayoodSoftware.tar.gz  After you download this file, uncompress it, and then untar it. Then use the Makefile to compile all of the code for your machine. A README file explaining the software and data is in www.cis.udel.edu/~amer/CISC651/Sayood/software/READMe
   
   
1. (20 pts) Required for all students
• 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+1 - x_i" 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.)
• 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, 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 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 differnce 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
• (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) Extra credit for all students
   • use your favorite image software (e.g., xv, GIMP) to view the original sena, sinan, and omaha images, and their difference images on your computer.  Most commercial software (including 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 and their difference images.
   
   
4. (4 pts) Extra credit for all students
   • Section 3.10 - Projects and Problems 2c
   
   
5. (4 pts) Extra Credit for all students
• Program a decoder "ConvertDifferenceImageBackToOriginalImage".
• (submit) Submit a hard copy of your code, and a script that demonstrates your program works.

Notes:

1. Students may work individually or in groups of 2.   Only one submission should be turned in from each group.
2. (repeated from syllabus)   Academic Honesty: Unless explicitly stated otherwise, students in one group are not permitted to access or compare any homework, or program-project answers with those of any other student (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 are cheating, and if caught, will be prosecuted according to University guidelines. This applies both to the student who gets answers and the student who gives answers.
3. (repeated from syllabus)  Lateness: Unexcused late assignments will be penalized up to 5% per day not including weekends up to a 10-day maximum penalty of 50%. Without prior discussion with the professor, assignments will not be accepted more than two weeks late.
4. Submit answers in the order assigned.