Design Paper 4

Graphics Interchange Format (GIF)

A brief overview and history of the GIF format, its development and its challenges. This page suggests reasons why large numbers of inefficient GIF images exist on the web. VisibleGif is designed to eliminate inefficient GIF images and allow their replacement by optimised versions of the equivalent image.

Table of contents

Image features and the GIF format

• Displays, colour models, pixels, RGB format and colour tables
• Compression
• Transparency
• Animation
• Interlaced Images
• Rules for web images

A brief history

• The earliest days - Compuserve
• The early days - World Wide Web
• Patent rights - Unisys
• Developer community
• Browser "safe" colours

Reasons for inefficiencies

• GIFs without compression
• GIFs and complexity
• GIFs and colour tables
• GIFs and text
• GIFs and anti-aliasing

Image features and the GIF format

 ^  Displays, colour models, pixels, RGB format and colour tables

Computer displays implement the red-green-blue (RGB) "additive" colour model. Some devices such as printers can implement other colour models (e.g. "subtractive"). The RGB model is called "additive" because a combination of the three pure colors "adds up" to white light.

A display screen can be considered to be organised as a grid similar to a chessboard. Each square on the screen is called a "pixel" (short for "picture element"). Usual display sizes are (width x height) 640 x 480 pixels, 800 x 600 pixels and 1600 x 1200 pixels.

Each pixel requires memory to store the colour that is to be displayed by that pixel. 24-bit "true colour" displays use 24 bits to store the colour for each pixel. In this case 8 bits stores the red component, 8 bits stores the blue component and the last 8 bits stores the green component. This is the RGB format.

Each colour entry in the GIF colour tables comprises 24 bits in RGB format. The index (offset) of a particular entry in a colour table comprises 8 bits. Each colour table can have up to 256 entries. Each entry is a 24 bit RGB colour. Apart from the colour tables all blocks when refering to colours use the 8 bit index. All colours should exist in a colour table.

 ^  Compression

An image format is needed for efficient transmission of image information between computers. Images should be able to be compressed in size and decompressed without any loss of information. Compression results in reduced storage needs and reduced transmission times.

In year 2000 C.E. in Europe a typical home computer connects to the Internet using a 56000 bps modem and connects via a mobile phone using a 9600 bps modem. The need for size compression remains.

 ^  Transparency

A particular colour in an image can be set to be transparent. This means that the pixels with this colour are not displayed and do not overwrite any colour that was previously displayed on those pixels. This simplifies the process of presenting overlayed images with other images and text.

In the GIF format all images are rectangular. They have a width and a height. For an object which is not rectanglar the areas outside the object can be set to a transparent colour.

..........   
..........   
....##....   
....##....   
..######..   
....##....   
....##....   
..........   

 ^  Animation

Simple animation can be implemented by displaying a sequence of images with a variable amount of delay between each image. For improved performance images should share the same colour table and use transparency.

 ^  Interlaced Images

Interlaced images can be implemented. The image is split into four sub-images. The information in each sub-image is cummulative and adds to the understanding of what the image as a whole represents. The four sub-images are transmitted in sequence.

The first sub-image contains an eighth of the data, the second an eighth, the third a quarter and the four contains the rest.

Assume the first line in an image is row 0 the process is:

• The first sub-image is created from every eighth line and starts with the first (row 0) line.
• The second sub-image is created from every eighth line and starts with the fifth (row 4) line.
• The third sub-image is created from every fourth line and starts with the third (row 2) line.
• The fourth sub-image is created with all the lines not previously used and starts with the second (row 1) line.

Before an image is fully downloaded the viewer should be able to decide whether to wait until the whole image appears or to move on. With faster Internet connections the need to use interlacing is reduced.

 ^  Rules for Web images

1. Reduce file size by increasing lengths of horizontal runs of the same colour.
2. Reduce file size by reducing the number of colours used in the image.
3. Reduce file size by cropping width and height to the minimum.
4. Avoid anti-aliasing (see below).
5. Never use text in images. Some image products automatically anti-alias text images.
6. All colours should exist in the colour table.
7. Never use "plain text" or "comment" blocks.
8. Replace "local" colour tables by a single "global" colour table where possible.
9. Avoid using GIF format for photographs. Consider using JPEG.
10. When using GIF format for photographs (in animated banners) use the best fit colour pallet containing the 256 most frequently used colours. Avoid the old browser safe colours.

A brief history

 ^  The earliest days - Compuserve

During the eighties the Graphics Interchange Format (GIF) for images was made popular by Compuserve. Before this period most of the information transmitted between computers was text. Compuserve needed a fast and efficient format to transmit images between computers. At this time computers were linked by very slow error prone telecommunications networks. Network capability and modem bandwidth constrained what was possible. Modem speeds were 1200 bps or 2400 bps (bits per second).

At the start of the nineties Compuserve published a programming reference document "Graphics Interchange Format Programming Reference document, produced by CompuServe Incorporated, dated 31 July 1990.". The format became well understood. This document included the following:

 ^  The early days - World Wide Web

Early in the nineties the designers of the World Wide Web now the World Wide Web Consortium decided to adopt the format. As a result all major browsers support the format. It became even more popular. During the nineties the majority of web images were implemented in GIF format. There were initiatives to extend the format with a new version extending the two existing versions which are known as "87a" and "89a".

 ^  Patent rights - Unisys

During the nineties it became widely known that Unisys owned a patent on key elements of the compression technology which is used as an integral part of the format. Unisys established its patent rights. Unisys receives royalty payments. The patent rights expire in the United States at the end of June 2003 and expire in the United Kingdom at the end of June 2004.

The GIF format uses a file compression method known as LZW (after Lempel Zev Welch). This compresses data without loss of information. The information is compressed by sending codes which represent repeating series of characters. The method requires that a history of all characters sent is retained. A single character code (1 byte) could represent thousands of actual characters. The telecommunications network would only need to transmit the single character. The browser would recreate the thousands of actual characters from this single character and knowing the ones transmitted previously.

 ^  Developer community

During the mid nineties the web developer community ceased to work on extending the GIF format. Work was undertaken on JPEG image formats for photographic quality web images. Work coordinated by the World Wide Web Consortium was undertaken on the Portable Network Graphics (PNG) image format and the Scalable Vector Graphics (SVG) image format. An attraction for working on these formats was that it was a stated aim that the formats would only use techniques and methods that were royalty free. One aim was to replace the GIF format.

 ^  Browser "safe" colours

Displays map the colours set in a GIF image to the colours known to the display using a "best fit" approach. This matches GIF colours with those available on the local computer. If a display can handle more than 256 colours browser safe considerations are usually not necessary.

In the eighties and early nineties most displays (especially for portable computers) could only display up to 256 colours. Some displays at this time could only handle 16 colours. For 256 colour displays problems were introduced in that the Microsoft Windows colour map and the Apple Macintosh colour map had differences. There were 216 colours which were the same. These were know as the browser safe colours. It was important at this time to ensure that GIF images only used the browser safe colours.

Reasons for inefficiencies

 ^  GIFs without compression

Some developers attempted to create GIF image editor software that they claimed did not use the patented technology. It was argued at this time that a GIF image could be produced without compression. If this assertion was true then it was claimed that patent rights were not infringed.

A number of approaches were based on the following reasoning. If each "compression" code was actually an existing colour entry in the colour table the "compression" code would always be found in the table and in consequence the code is actually an "index" code not a "compression" code. Repeated series of the same character or character sequences are not compressed. The normally variable "LZW compression" size is fixed and so it should be called the "bit packing" size.

No claim is made about the validity or otherwise of these arguements but the consequences are clear. These approaches resulted in the implementation of GIF editor software that routinely produced large oversized GIF images.

 ^  GIFs and complexity

The GIF format has complexities that provide challenges to developers. It is how these challenges are met in programming, coding and data structures that can introduce ineffiencies. Some image editing software restricts access to some of the features of the GIF format.

 ^  GIFs and colour tables

A colour table can have 256 entries. Each entry requires 3 bytes. A GIF image containing a single image can have a "global" colour table and a "local" colour table. It is easier to develop a program that always assumes all 512 entries will be present. The size will be the same whether all colours or a handful of colours are used.

By having colour tables with entries that are not used each compression code size is larger than it should be. A colour table with 256 entries means the initial "LZW compression" size is nine bits. To take an extreme example if only 4 colurs were used the "LZW compression" size should be three bits (a saving of at least six bits on every compression code).

There was a reasonable rationale for taking this "bloated" colour table approach. A GIF image can be delivered without any colour table. If an initial image is delivered with the "bloated" colour table and all subsequent images are delivered without colour tables overall performance might be optimised. Web browsers do not appear to handle GIF images in this way. Each image is treated in isolation. If a colour table is not present an image is not displayed.

All colour index fields should refer to actual entries in a GIF colour table. Some image editor software sets some of these entries to an arbitary high number (such as 255). This can cause an inappropriate amount of program storage to be set aside for processing these indices.

 ^  GIFs and text

The GIF format of includes the ability to include plain text and comments. Most web browsers seem to ignore these elements. For efficiency these blocks should be deleted.

Text in web images should be avoided. The "alt" attribute in the "<IMG>" HTML tag should provide informtion about the image. It can include the text that is included in the image. This is of little use.

Header tags should be used to convey the importance of the text. This allows web robots and web search engines to catalogue and index. Text in images is invisible to search engines and accessibility enabled browsers. It is far better to use an image in a background and use the text (tagged as appropriate) in the normal way overlaying if necessary.

 ^  GIFs and anti-aliasing

Anti-aliasing changes the colours of transition areas connecting areas of different colours. Intermediate new colour shades are introduced in the transition area to minimise differences in shades between adjoining points of colour.

The wider the differences between colours the more shades are added by image editor software.

Usually horizontal and vertical lines do not need anti-aliasing. Objects with other angled or curved surfaces can benefit since the impression of depth can be improved.