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.
Why
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).
Colors: 256 colors
(8 bits per pixel) |
Colors: 128 colors
(7 bits per pixel) |
Colors: 64 colors
(6 bits per pixel) |
Colors: 32 colors
(5 bits per pixel) |
Colors: 16 colors
(4 bits per pixel) |
Colors: 8 colors
(3 bits per pixel) |
Colors: 4 colors
(2 bits per pixel) |
Colors: 2 colors
(1 bit per pixel) |