EECS20N: Signals and Systems

CompuServe GIF Image Format

Contributed by Steve Neuendorffer

One of the widely used formats for representing images on the Internet is CompuServe's GIF, or graphics interchange format. An image file, like any other computer file, is a collection of bits. If you attempt to read the file in a text editor (such as emacs, which can open binary files) you will see something like this: 

GIF89at+ÿJ´¨Ñ£H*]Ê´©Ó§P£JJµªÕ«X³jÝʵ«¯`ÃK¶¬Ù³
followed by several hundred or thousand more lines of absolutely incomprehensible nonsense, and an occasional beep. How does this represent an image?

The text editor is expecting a binary sequence representing characters in the ASCII format, The American Standard Code for Information Interchange. In ASCII, each 8 bits are grouped together in a byte, and each byte corresponds to a single character. This allows for 2^8=256 possible characters. Since there are only 26 letters in the English alphabet, plus 26 upper case letters, plus 10 digits, plus a dozen or so punctuation marks, there are quite a few extra characters leftover. Your text editor interprets these additional characters as shown above. If you are using a text editor that supports 16-bit unicode characters, you might see instead Chinese or Hebrew characters, for example. A few of the characters are interepreted as control characters, like the Carriage Return (ASCII 13), Line Feed (ASCII 10), and Bell (ASCII 7), which would ring a physical bell on old Teletype machines. Modern computers usually beep whenever a Bell character comes along, hence the beeps that the text editor produces.

Pictures in a computer are divided into pixels (picture elements), organized horizontally and vertically in lines, much like lines of characters on a page. The GIF must represent a rather large number of pixels efficiently, or the file size (and Internet transport time) gets too large.

In a GIF image, the first pixel in the file goes in the upper left hand corner, and the second one goes just to its right. The image is scanned from left to right, top to bottom, until all the pixels have been specified. (This is not the only way of ordering pixels in a computer. TIFF images happen to start at the bottom and work their way up.)

Each pixel has a color. In GIF images, a color is specified using Red, Green, and Blue components. With 8 bits for each component, there are over 2^24, or about 16 million possible colors. A naive representation of the image would simply store three bytes for each pixel. But then a 640x480 pixel image (which is a modest size) would be around a megabyte of data. At a modem speed of 56 kilobits per second, it would take 131 seconds, more than two minutes, to download the image. GIF compresses the data, reducing the number of bits to represent the image.

The first kind of compression that GIF uses is called a colormap. Instead of allowing the image to contain all 16 million colors, GIF restricts the image to a maximum of, say, 256 out of the 16 million (the number of colors in the colormap can be varied). It can be any 256 out of the 16 million, so there is no loss of richness of possible colors. But no more than 256 distinct colors can be used simultaneously in any one image. The colors are stored in a colormap table, and the color for each pixel is specified as an index into the table. So instead of using 24 bits for each pixel, a file only contains an 8 bit index. (A 24-bit display of a modern computer can display all 16 million colors simultaneously, so multiple GIF images with different colormap tables can be simultaneously displayed with good color fidelity.)

With colormap table of 256 entries, the above scheme reduces the amount of data by a factor of three. But GIF does better than this. The second kind of compression that GIF includes is called run-length coding. This makes use of the fact that neighboring pixels are often the same color in a typical image. When several pixels have the same color, instead of storing them individually, they are stored as a run length followed by the color. For example, a sequence of three Blue pixels could be stored as "Blue Blue Blue" or "3, Blue". The specifics of how this is done is a little complex; GIF uses a sophisticated variation of run-length coding known as Lempel-Ziv-Welch coding. The algorithm is also used in several file-compression utilities as well. See the details in an article on GIF compression.)

How is a GIF file converted into an image? To make things easier, here are the first few bytes of the file above written in binary (each line is a byte, or 8 bits): 

1)  01000111 -> 'G'
2)  01001001 -> 'I'
3)  01000110 -> 'F'
4)  00111001 -> '8'
5)  00111010 -> '9'
6)  01100001 -> 'a'
7)  01110100 
8)  00000011 -> 884 pixels wide
9)  00101011
10) 00000100 -> 1067 pixels high
11) 11110111 -> Global colormap present, 256 colors, 24 bits per color.
12) 11111111 -> background is color index 255.
13) 00000000 -> zero
14) 00000000
15) 00000000
16) 00000000 -> color 0 in the colormap = (0, 0, 0) = black
17) 10000000 
18) 00000000
19) 00000000 -> color 1 in the colormap = (128, 0, 0) = red
20) 00000000
21) 10000000
22) 00000000 -> color 2 in the colormap = (0, 128, 0) = green
The first six bytes contain six ASCII characters. For the file above the first six characters are the ASCII characters "GIF89a", indicating that this file is compatible with the GIF standard written in 1989. You may also see "GIF87a" which was an earlier version of the standard. There is no information there about any pixels, just information to the decoder about what kind of file it is looking at.

From here on, the bytes do not correspond to ASCII characters. Next comes a sequence of bytes that give the size of the screen, two bytes for the width and two bytes for the height. The image above happens to be 884 pixels by 1067 pixels.

Byte 11 tells how the colors are stored in the file. In the file above, and in most GIF files, this byte indicates that the file contains its own colormap (as opposed to using the default colormap), that the colormap contains 255 entries, and that each color in the color map is specified using 24 bits. If the colormap is not present, then the GIF standard assumes that a pre-defined default colormap is used.

Byte 12 gives the index of the background color in the colormap, in this case it is color 255. Byte 13 is always zero.

The first 13 bytes are the "screen descriptor". In the file above, this is followed by 768 bytes of colormap information. In GIF files, the red component comes first, followed by green and then blue. 0 indicates the minimum intensity of that component, while 255 indicates the maximum intensity.

Following the global colormap is an "image descriptor." A GIF file can contain more than one image. Each image can be individually positioned on the screen and can even have its own colormap. The file we are using just has one image with the following descriptor: 

1)  00101100 -> ","
2)  00000000
3)  00000000 -> 0 pixels offset to the right.
4)  00000000
5)  00000000 -> 0 pixels offset to the bottom.
6)  01110100 
7)  00000011 -> 884 pixels wide
8)  00101011
9)  00000100 -> 1067 pixels high
10) 00000000 -> No local colormap, non-interlaced.
The first character in the image descriptor is always the ASCII code for a comma. The next 8 bytes give the position and size of the image, which in this case starts in the upper left of the screen, and is the same size as the screen. Byte ten specifies that there is no local colormap, and the lines of the image are scanned in normal order. (GIF also allows images to be scanned in an interleaved fashion, which permits a browser to display a blurry approximation of the image before it has received all the data. For more information about this, see the GIF87a specification.)

Finally we get to the image data for the pixels, run-length coded. After all the image data, there is a single ASCII semicolon, binary code 00111011.