Digitizing Images with Color Tables

Notice that there is a lot of redundancy in all those bits, since we only used 6 colors in the entire image. Many common image formats, such as GIF and JPEG, reduce the total number of bits needed in a file by keeping a color table that lists the full 24 bits for each color used in the image, and then use fewer bits in the actual image data by referring to the entry from the color table. How does this work? Here's an example color table for our image:

Color Color Short-cut Code Full 24-bit Representation
White   0000 111111111111111111111111
Black   0001 000000000000000000000000
Red   0010 111111110000000000000000
Green   0011 000000001111111100000000
Brown   0100 110011000110011000110011
Yellow   0101 111111111111111110011001

Now we only need specify three bits to name a color, rather than the full 24 bits. If we put this table at the beginning of our digital representation, then we can use the shortcut codes in the rest of the image data. Here again is the second row from the bottom in our house example, using shortcut codes:

Color Color Binary
white   0000
white   0000
red   0010
red   0010
red   0010
red   0010
red   0010
brown   0100
brown   0100
red   0010
red   0010
red   0010
red   0010
white   0000
white   0000
white   0000

Now, instead of 256 entries of 24 bits each (256 x 24 = 6,144 bits!), we can add the color table (with 6 entries of 24 bits each) and the 256 pixels of 4 bits each. This reduces the total size from 6,144 to (6 x 24) + (256 x 4) = 1,168 bits, about one-sixth the size. We need a little more room than this however—most commonly used image formats, like JPEG or GIF need to add a few more bits to specify the number of entries in the color table and add some additional identifying information. Even so, we can see that using a color table significantly reduces the size of the representation. There are a number of other compression tricks that can be used to reduce the size of the representation, but hopefully you get the basic idea.

Take a Look at the Big PictureWhy is it desirable to reduce the number of bits in the representation? That's a good question! The answer has to do with the relative cost of the different components in a computer system. Recall from the chapter on computer hardware that the CPU is significantly faster than the memory system. This means that computer designers and programmers are often willing to use a little more CPU in order to reduce the use of the memory system. By using the shortcut of the color table, we reduce the number of bits stored in memory necessary to represent an image, but we increase the amount of CPU work that must be done to decipher the bits (since now it must look up each color from the table). This is usually a worthwhile trade-off, because the CPU is so fast. Reducing the number of bits for storage also reduces the time to transfer an image over a network, such as the Internet.

As a final example of color mapping, let's see what happens when we reduce the number of colors available in the image. The table below shows the same image, but with a smaller and smaller color table. As we reduce the number of colors, we need fewer bits to represent each color, and the file size goes down (but so does the image quality).

Image with 256 colors

Colors: 256 colors (8 bits per pixel)
File Size: 13 Kbytes

Same image with 128 colors

Colors: 128 colors (7 bits per pixel)
File Size: 11 Kbytes

Same image with 64 colors

Colors: 64 colors (6 bits per pixel)
File Size: 9 Kbytes

Same image with 32 colors (noticable degradation)

Colors: 32 colors (5 bits per pixel)
File Size: 7 Kbytes

Same image with 16 colors (very degraded image)

Colors: 16 colors (4 bits per pixel)
File Size: 5 Kbytes

Same image with 8 colors (even worse now)

Colors: 8 colors (3 bits per pixel)
File Size: 4 Kbytes

Same image with 4 colors (barely recognizable)

Colors: 4 colors (2 bits per pixel)
File Size: 2 Kbytes

Same image with 2 colors (very difficult to recognize now)

Colors: 2 colors (1 bit per pixel)
File Size: 1 Kbyte