PURPOSE:s

The purposes of this lab are to get some hands-on experience with the GIF format and to provide some time to work on your final programming project.

LAB ASSIGNMENT:

You will complete this lab by following the directions below, filling out the Lab Form(s) for this lab when directed. The Lab Forms are Google Forms that save your answers.

Recall that GIF images are represented by storing a color value for each pixel (picture element) in the grid that makes up the image. Each value is a 24-bit color, with 8 bits for each component using (R,G,B) representation. For an image that is 100 pixels wide and 50 pixels high,

• how many total pixels are contained in the image?
• how many total bits are needed to represent the image, if an (R,G,B) value is stored for each pixel?

One way that GIF images are stored more efficiently is by limiting the number of distinct colors the image can contain. For instance, a typical number is 256 colors. Each distinct color is stored in a table, known as the Color Look-Up Table. Then, the color of each individual pixel can simply be stored as a number in the 0..255 range, rather than as a 24-bit color.

• How many bits are needed to store 256 colors in a Color Look-Up Table, where each entry has 24 bits?
• For an image that is 100 pixels wide and 50 pixels high, how many bits are needed to represent the image, if the value stored for each pixel is a number between 0..255 instead of a 24-bit color?
• For an image of this size, how much storage space is saved by using a Color Look-Up Table in this way?

Record your answers on your lab sheet.

Another way that GIF images may be stored efficiently is by using run-length encoding to accomplish data compression. The simple idea of run-length encoding is to take advantage of long sequences in which the same data value is repeated. For instance, if color #7 appears 10 times in a row, the sequence 7 7 7 7 7 7 7 7 7 7 is replaced by the numbers 10 7.

In this exercise, our class will be assembling a model of a GIF image, using Post-It notes to represent the various pixels. Your teaching assistants will direct this activity.

Your teaching assistants will explain this exercise to you.

Examine the sheet you have been given. Find the part that says "Your Data". Discuss with your lab group:

• how this set of numbers corresponds to the grid to the right
• how these numbers correspond to colored pixels

Find the "quick lesson on data compression" at the bottom of the page. Discuss with your lab group how the numbers in this section represent a different way of expressing the same sequence of numbers at the top of the page. For your page, does this represent an actual savings in terms of total amount of data?

Record your answers on your lab sheet.

At this point, you should assemble your page according to the directions. Try to align your Post-Its with the grid on the back of the page, so that there are exposed pieces with adhesive on the back (see image at right). This is necessary so that the page will be able to adhere to the wall.

When you have completed this exercise, answer these questions on your lab sheet:

• GIF images: GIF images use a color table which assigns a number to each distinct color in the image, and then for each pixel, stores the position of its color in the table. For instance, our image contains as many as 8 distinct colors, and so the entire image is encoded with numbers in the range 0..7 .Explain what will happen to the image if the values in the color table get changed, i.e., we switch the values in positions 1 and 7.
• Black and White: Suppose you'd like to re-create today's image, but instead of Post-It notes, you are going to use pieces of construction paper. Unfortunately, the only colors of paper you have are black and white. Explain how you could create a black-and-white version of this image by making some simple changes to the color table.
• Compression: The run-length encoding compression algorithm replaces consecutive occurrences of a number K with two numbers, n and K, where K is the color and n is the number of consecutive occurrences. For instance, the sequence "4 4 4 4 4 4" in the original image is replaced by "6 4". For an image with 15 pixels, the highest compression occurs when all 15 of the colors are the same - if the entire image is the color "4", the compressed image is encoded as "15 4".In some cases, however, compression won't be effective. It may actually take more values to encode the "compressed" image than the original image. In the worst case, how many values will it take to encode an image with 15 pixels using the run-length encoding compression algorithm? Explain.
• Compression, continued: Using this compression algorithm, which of these images would produce better compression: an image with horizontal stripes or one with vertical stripes? Explain.

The remainder of this lab period should be used for working on your programming project. You should take the time to discuss your project with your lab assistants. If you have questions, this is a good opportunity to ask them.

This lab demonstrated GIF encoding and run-length encoding for compression. In order to demonstrate run-length encoding, each page was shown in a compressed and uncompressed version.

In reality, it is not efficient to use run-length encoding on very small sub-images. The real payoff occurs when dealing with a large image, where hundreds of equally colored pixels may appear in succession. And so, think of this example as an example.