The Image Format That Made The Internet

▶ Visit brilliant.org/NewMind to get started learning STEM for free, and the first 200 people will get 20% off their annual premium subscription
The GIF format was introduced in 1987 by CompuServe, America's first major commercial online service provider. In early 1980s, advances in modem speed, processing power and the introduction of their CompuServe B file transfer protocol had now allowed for the exchange of graphics on the platform. This also opened the door to CompuServe's eventual transition to a GUI based interface.
At the time, access to most online information services were billed by time and for graphics to be exchanged cost effectively and within a practical transfer time, the service required a method to reduce the memory requirements of informationally dense graphical data.
PALETTES
Because of this the concept of a palette or a color lookup table was introduced. A palette is a data structure that contains an indexable lookup table of chromaticity coordinates. In this mechanism, each pixel of the image data is defined by a palette table index, where its color data can be found. A 2-bit per pixel image for example can reference 4 color definitions within a palette while a 16 bit per pixel image can reference a little over 65k unique color definitions.
IMAGE COMPRESSION
This technique is known as lossy compression, as it alters the original image data in the compression process. While lossy compression can dramatically reduce memory requirements, the technique was far too processor intensive for consumer computer hardware of the time and its losseness made it unusable for functional graphics, such as in case of graphic user interfaces. Lossless image compression that did not change the image data was chosen for the JIF format as the available techniques were relatively simple and could operate easily on existing hardware. It also best matched the intended application of sharp-edged line art based graphics that used a limited number of colors, such as logos and GUI elements.
RLE
This allowed long runs of similar pixels to be compressed into one data element and it proved to be most efficient on image data that contained simple graphics such as with icons and line drawings. Because of the overhead of the counting mechanism, more memory is required than the original image in such cases, making the technique unusable for more complex images.
LZW
Wilhite had concluded that run length encoding was not an effective solution and looked towards a new class of data-compression algorithms, developed in the late 1970s by Jacob Ziv and Abraham Lempel. A key characteristic of LZW is that the dictionary is neither stored or transmitted but rather developed within the algorithm as the source data is encoded or compressed data decoded.
ENCODING
In the encoding process an initial code-width size is established for the encoded data. An 8-Bit based data source for example would require the first 256 dictionary indexes to be mapped to each possible 8-bit word value.
From here, if more data is available in the source data stream the algorithm returns to its loop point. If there is no data left to encode, the contents of the remaining index buffer is found within the dictionary and its index code-word sent to the output code stream, completing the final encoding.
DECODING
A dictionary table matched to the bit-width specification of the encoded data is first initialized in a manner similar to the encoding process. Because the encoding process always starts with a single value, the first code-word read from the input code stream always references a single value within the dictionary, which is subsequently sent to the decoded output data stream. If one is found or the code-word represents a single value, the referenced values are sent to the decoded output data stream.
VARIABLE BIT-DEPTH
This requires the bit-width of a code-word to be, at minimum one bit larger than that of the image data. This is accomplished by starting the encoding process with the assumption that the bit-width of a code-word will be one bit larger than the image data’s bit-depth. This is the minimum needed to index every possible value of the image data plus the control codes.
IMAGE LAYOUT
Each image is contained within a segment block that defines its size, location on the canvas, an optional local color palette and the LZW encoded image data along with its starting code-word bit-width size. Each image can either use its own local color palette or the global color palette, allowing for the use of far more simultaneous colors than a single 8-bit palette would allow. The LZW encoded data within the image block are packaged into linked data sub-blocks of 256 bytes or less.
GRAPHIC CONTROL EXTENSION
The graphic control extension also took advantage of the format's ability to store multiple images with the introduction of basic animation.
SUPPORT NEW MIND ON PATREON
/ newmind