Proseminar: Redundanz

Vortrag 10: Das Grafikdateiformat GIF

Andreas Kunz

Das Grafikdateiformat GIF

Grafikdateiformate allgemein

Mit Beginn der achtziger Jahre wurden Computer für Privatanwender erschwinglich, die neben den herkömmlichen Zeichen auch Rastergrafiken darstellen und bearbeiten konnten. Damit war der Bedarf für Dateiformate, mit denen man die Grafiken speichern konnte, geweckt.
Während die frühen Bildformate oft nur von einzelnen Programmen gelesen werden konnten und mehr oder weniger aus einer Kopie des Bildspeichers bestanden, kamen bald Formate auf, die durch Zusatzinformationen die Programm- und Plattformabhängigkeit einer Grafikdatei beseitigten und oft auch durch Kompression halfen, die relativ grossen Grafik-Datenmengen zu verringern und somit Speicherplatz und Übertragungsbandbreite einzusparen.

Die Entstehung von GIF

Das GIF-Format wurde von Steve Wilhite erfunden und am 15. Juni 1987 in der Spezifikation der ersten Version "87a" (siehe [1]) veröffentlicht. Es steht unter dem Copyright von CompuServe Inc., darf aber von Programmen frei verwendet werden, wenn diese auf das Copyright aufmerksam machen (die verwendete LZW-Kompression ist allerdings patentiert - dazu am Ende mehr). Anlass für die Entstehung des Formats war die Notwendigkeit für möglichst bandbreitensparende Bildübertragung im Rahmen des Online-Dienstes von CompuServe.
1989 wurde das Format mit der Version "89a" (siehe [2]) noch um einige spezielle Funktionen ergänzt, allerdings nicht tiefgreifend geändert.

Grundlegende Eigenschaften von GIF

Aus der beabsichtigten Verwendung des GIF-Formats für Datenfernübertragung und Online-Dienste ergibt sich einerseits ein streng sequentieller Aufbau, so dass der Empfänger alle Daten sofort nach Erhalt sinnvoll verarbeiten kann (beispielsweise das Bild schon aufbauen, während die Datei noch empfangen wird) und andererseits, dass auch mehrere Bilder in der Datei stehen und zusätzliche Daten zum Beeinflussen der Anzeige derselben übertragen werden können (z.B. für Animationen).
Die Daten sind aber nicht durch Fehlererkennung geschützt, sondern auf eine fehlerfreie Übertragung angewiesen.
Für jedes einzelne Bild stehen bis zu 256 Palettenfarben zur Verfügung, die aus der Menge der 24-Bit-Farben frei gewählt werden können. Die Bilddaten selbst sind mit dem LZW-Algorithmus, einer Form des Ziv-Lempel-Algorithmus (siehe Vortrag 5), verlustfrei komprimiert, wodurch die Datenmenge je nach Bildmotiv von "gar nicht" (sogar Datenzuwachs um ca. 10-20 % bei komplexen Fotos beispielsweise) bis auf 1/20 (bei einfachen Zeichnungen) reduziert wird, im allgemeinen aber typische GIF-Packraten in der Grössenordnung von 30-70 % erreicht werden.
GIF ist neben JPEG (siehe Vortrag 11) heute das verbreitetste Format für Grafikdateien.
 

Der Aufbau einer GIF-Datei (anhand von GIF 87a)

Eine GIF-Datei besteht aus mehreren Blöcken. Die ersten ("der Kopf") enthalten allgemeine Daten, die alle Grafiken betreffen, dann folgen die Blöcke, die die Grafikdaten jedes Bildes und dazugehörige Informationen beinhalten. Dabei folgt der Aufbau diesem Schema:

GIF-Syntax-Schema

Bild 1: Der Aufbau einer GIF-Datei

GIF-Signature

Die GIF-Signatur kennzeichnet die folgenden Daten als gültigen GIF-Datenstrom. Sie besteht aus sechs Bytes, den Zeichen G I F 8 7 a (ASCII) oder G I F 8 9 a , wobei die 87 bzw. 89 als Versionsnummer aufgefasst werden kann.

Screen Descriptor

Dieser Abschnitt beschreibt die für alle enthaltenen Bilder geltende Umgebung:

Aufbau des Screen Descriptor
Bild 2: Der Aufbau des Screen Descriptor

Erläuterungen zur Grafik:

Global Color Map

Die globale Farbtabelle weist den Paletteneinträgen 24-Bit-Farbwerte zu. Diese Tabelle kann allerdings für einzelne Bilder durch eine lokale Farbtabelle ungültig gemacht werden. Die Grösse der Palette, also die Anzahl der Einträge ist im Screen Descriptor durch die Anzahl der Bits pro Pixel bestimmt.
Dieser Block ist optional.
Aufbau der Global Color Map
Bild 3: Der Aufbau der Global Color Map

Image Descriptor

Dieser Block beschreibt Parameter für ein einzelnes Bild wie Position und Grösse im vorher definierten "Screen" (GIF-Bildfläche).

Aufbau des Image Descriptor
Bild 4: Der Aufbau des Image Descriptor

Erläuterungen zur Grafik:

Local Color Map

Sofern im Image Descriptor angegeben, gelten für dieses eine Bild nicht die globalen Farbinformationen. Hier lässt sich dafür eine lokale Farbtabelle definieren. Nach diesem Bild sind aber wieder die Informationen aus dem Screen Descriptor und der Global Color Map gültig.
Der Aufbau ist analog zu dem der Global Color Map, auch dieser Block ist optional.

Image Data (LZW-komprimiert)

Die Bilddaten beginnen mit einem Byte, das die anfängliche Kodelänge in Bits angibt, das sind die Zahl der Bits pro Pixel (ausser bei den zweifarbigen 1-Bit-Bildern, hier muss der Wert 2 sein).
Danach folgen die eigentlichen Farbindizes der einzelnen Pixel von links nach rechts und oben nach unten (es sei denn, das Bild ist interlaced gespeichert, dann ist die Zeilenreihenfolge nach einem anderen Muster aufgebaut, siehe dem entsprechenden Abschnitt). Diese Farbindizes sind in Datenblöcke gepackt. Ein solcher Datenblock besteht aus einem Byte, das die Länge dieses Datenblocks (1-255 Bytes, dieses eine Byte nicht mitgerechnet) angibt, und dann der entsprechenden Anzahl an Datenbytes. Beliebig viele dieser Blöcke können für die Daten verwendet werden. Das Ende dieser Blöcke wird durch einen Datenblock der Länge 0, also ein Nullbyte an der Stelle eines neuen Datenblocks, markiert.

Die Farbindizes sind allerdings nicht "im Klartext" gespeichert, sondern mit dem LZW-Algorithmus (mit variabler Kodelänge) gepackt. Dieser ist eine Art des Ziv-Lempel-Algorithmus. Nähere Informationen dazu gibt es im Vortrag 5.
Grob skizziert funktioniert der Algorithmus so:
Die Grundidee ist, wiederkehrende Zeichenketten durch kürzere Kodes zu ersetzen und so Daten einzusparen. Wollte man immer die optimalen Ersetzungen benutzen, so bedeutete das einen gewaltigen Rechenaufwand und man müsste auch die Kodetabelle ("Codebook", es ordnet jedem Kode seine Zeichenkette zu) mit der komprimierten Datei zusammen verschicken. LZW lässt den Enkoder die Kodetabelle so aus den Daten aufbauen, dass auch der Dekoder es rekonstruieren kann - und das alles "single pass", also in einem Durchlauf, der auch nicht besonders rechen- oder speicherintensiv ist.
Die anfänglichen Kodes sind gerade die Farbindizes, die jeweils einem Pixel entsprechen. Kodes für längere Zeichenketten sind also zunächst ein Bit länger (die anfänglichen Kodes erhalten eine führende Null, um sie auf die selbe Länge zu bringen).
Die auf die Farbindizes folgenden zwei Kodes nehmen eine Sonderstellung ein: der erste ist der "Clear Code", der besagt, dass die Kodetabelle rückgesetzt werden soll. Er soll am Anfang und darf überall in den LZW-Daten stehen. Der zweite ist der "End Of Information Code", der am Ende der LZW-Daten gesendet werden muss.
Danach kommen die eigentlichen Kodes für längere Zeichenketten.
Der Algorithmus beginnt nun mit einer leeren Zeichenkette und fügt ihr die zu packenden Daten Byte für Byte zu, bis er für die konkatenierte Zeichenkette keinen Kode in der Kodetabelle mehr findet (am Anfang besteht diese Zeichenkette aus den ersten zwei Datenbytes). Dann fügt er den Kode für den noch in der Kodetabelle gefundenen Zeichenkettenbeginn (ohne das letzte Zeichen) den gepackten Daten zu und nimmt den nächsten verfügbaren Kode als Kode für die gesamte Zeichenkette (MIT dem letzten Zeichen) in die Kodetabelle auf. Nun beginnt wieder die Zeichenkettensuche (wobei die Anfangszeichenkette nun aus diesem letzten Zeichen besteht).
Nach einer gewissen Datenmenge sind die verfügbaren Kompressionskodes in der Kodetabelle alle belegt (bei 8-Bit-Farbindizes sind die Kodes anfangs 9 Bit lang, ohne anfängliche und Spezialkodes stehen also noch 254 zur Verfügung). Dann wird (von En- und Dekoder) die Kodelänge um ein Bit (in diesem Beispiel auf 10 Bit) erhöht, die bestehenden Kodes im Kodebook erhalten eine führende Null, die neuen beginnen mit einer Eins.
Allerdings ist die Kodelänge auf 12 Bit beschränkt, wodurch sich eine Maximalzahl von 4096 Kodes ergibt. Ist die Kodetabelle nun endgültig voll, so kann der Enkoder entweder dieses (ohne weitere Kodes hinzuzufügen) beibehalten oder einen "Clear Code" senden, um wieder mit einer leeren Kodetabelle und der anfänglichen Kodelänge zu arbeiten.

Diese komprimierten Daten werden nun wieder auf Bytes aufgeteilt, um in die Datenblöcke gepackt zu werden. Dazu werden die Bits praktisch von rechts nach links aufgereiht und dann jeweils die acht Bits ganz rechts in das nächste Datenbyte gesteckt. Bei einer Kodelänge von fünf Bits (die Bits des ersten Kodes sind mit "a" bezeichnet, die des zweiten mit "b", usw.) beispielsweise könnte man es sich so vorstellen:

76543210  Bits
+--------+       
|bbbaaaaa| Byte 1
+--------+       
|dcccccbb| Byte 2
+--------+       
|eeeedddd| Byte 3
+--------+       
|ggfffffe| Byte 4
+--------+       
|hhhhhggg| Byte 5
+--------+       
| . . .  .       
.  usw...        

Ein ausführliches Beispiel dazu findet sich in [3].

GIF Trailer

Dieses Byte markiert (sofern es ausserhalb eines Blocks vorkommt) das Ende des GIF-Datenstroms. Der Wert ist 0x3B hex, als ASCII-Zeichen das Semikolon.

GIF Extension Blocks

An der Stelle eines Bildblocks kann auch ein GIF-Erweiterungsblock vorkommen - beliebig oft in der GIF-Datei. Seine Funktion kann frei definiert werden. Die Erweiterungen zu GIF89a bestehen hauptsächlich in der Definition solcher Blocks. Für GIF87a ist meines Wissens kein Erweiterungsblock definiert worden.

Aufbau eines Extension Blocks

Bild 5: Der Aufbau eines Extension Blocks


GIF89a-Erweiterungsblöcke

Mit der Version 89a erfuhr das GIF-Format einige Erweiterungen. Diese umfassen erstens die "sortiert"-Flags für die Farbtabellen sowie die Pixel Aspect Ratio im Screen-/Image Descriptor und zweitens die Definition von vier verschiedenen Erweiterungsblöcken. Diese sind:

Plain Text Extension

Mit dieser Erweiterung lässt sich ASCII-Text in bestimmbarer Grösse und Farbe als Grafik auf die GIF-Bildfläche aufbringen - zumindest theoretisch, mir jedenfalls ist kein Programm bekannt, das einen solchen Block auswerten kann.
Dieser Block darf überall vorkommen, wo ein Bildblock vorkommen darf.

Aufbau der Plain Text Extension

Bild 6: Der Aufbau der Plain Text Extension

Comment Extension

Damit lassen sich weitergehende Informationen zur GIF-Datei (Autor, Copyright, Inhaltsbeschreibung,...) als ASCII-Text speichern, die nicht in der Grafik dargestellt, wohl aber von Programmen ausgelesen und an anderer Stelle angezeigt werden können.
Dieser Block darf überall im Körper der Datei vorkommen.

Aufbau der Comment Extension

Bild 7: Der Aufbau der Comment Extension

Graphic Control Extension

Dieser Erweiterungsblock bestimmt, auf welche Weise der folgende Bild- oder Plain-Text-Block dargestellt werden soll. Es lassen sich Zeitverzögerungen, Transparentfarben, Warten auf Benutzereingaben und Verfahren zum Wiederentfernen des Bildes bestimmen.
Dieser Block darf vor jedem Bildblock/Plain-Text-Block auftreten (aber nur je einmal).

Aufbau der Graphic Control Extension

Bild 8: Der Aufbau der Graphic Control Extension

Application Extension

Dieser Block eröffnet Programmautoren die Möglichkeit, in GIF-Dateien eigene Erweiterungen einzubauen, welche zumindest von eigenen Programmen erkannt und interpretiert werden. Eine Acht-Byte-Zeichenkette ("Identifier") wird benutzt, um den Block einer Applikation zuzuordnen, die drei Bytes der Authentifizierung kann man frei definieren.
Dieser Block darf überall im Körper auftreten.

Aufbau der Application Extension

Bild 9: Der Aufbau der Application Extension

Beispiel: die Netscape2.0 - Extension

Dies ist eine häufig vorkommende und meines Wissens im Prinzip auch die einzige bekannte Verwendung der Application Extension.
Mit der Graphic Control Extension kann man zwar Zeitverzögerungen der Einzelbilder zur Erstellung von Animationen festlegen, aber eine einmal durchlaufene Animation bleibt stehen. Mit dieser Erweiterung lässt sich nun eine gewünschte Anzahl an Wiederholungen bestimmen. Erkennt ein Programm diese Erweiterung, so zeigt es die Animation nach ihrem Ablauf wieder von vorne an.
Ausserdem lässt sich eine Anzahl an Bytes festlegen, die das Programm lesen soll, bevor es mit dem Anzeigen der Grafik beginnt.
Diese Erweiterung wird von Netscape Navigator ab der Version 2.0 und vom MS Internet Explorer ab 3.0 sowie einigen anderen Programmen (vor allem WWW-Browsern) erkannt. Sie muss als erster Block im Körper der GIF-Datei stehen.

Die Applikations-Identifizierung lautet "NETSCAPE" und die Authentifizierung "2.0".
Die beiden möglichen Datenblocks sind dabei folgende:

Der Looping Extension Sub-Block:
   +---------------+
0  |     0x03      |  Grösse des Datenblocks
   +---------+-----+
1  Reserviert|0 0 1|  Kennung für Loop-Block
   +---------+-----+
2  |               |  Anzahl der Wiederholungen
   +-   Anzahl    -+  der Animation
3  |               |  (0 bedeutet: unendlich)
   +---------------+
 

Der Buffering Extension Sub-Block:
   +---------------+
0  |     0x05      |  Grösse des Datenblocks
   +---------+-----+
1  Reserviert|0 1 0|  Kennung für Puffer-Block
   +---------+-----+
2  |               |  Dieser 32-Bit-Wert (ohne
   +-   Anzahl    -+  Vorzeichen, niedrigstwertiges
3  |               |  Byte zuerst) gibt an, wie
   +- zu lesender -+  viele Bytes zuerst geladen
4  |               |  bzw. empfangen werden
   +-    Bytes    -+  sollen, bevor die GIF-Datei
5  |               |  dargestellt wird.
   +---------------+

Eine formale Spezifizierung findet sich bei [4].

Der Vollständigkeit halber sei noch die ANIMEXTS1.0 Extension erwähnt. Sie ist von der Funktion her identisch, lediglich die Applikations-Identifizierung lautet "ANIMEXTS" und die Authentifizierung "1.0".
Andere Erweiterungen sind mir nicht bekannt.
 

Am Rande

"interlaced" - Bildaufbau

Um bei langsamer Übertragung schon mit einem Bruchteil der Bilddaten einen groben Überblick über eine Grafik zu gewähren, kann man diese im interlaced-Modus abspeichern. Dabei werden die Zeilen nicht der Reihe nach von oben nach unten codiert, sondern in folgender Reihenfolge: Die Wirkung dieses Modus kann man sehen, wenn man eine Internet-Seite, die ein interlaced-GIF enthält, nur mit einer niedrigen Übertragungsrate empfängt:
Man sieht zunächst eine sehr grobe Version der Grafik, sie sieht aus wie aus kleinen senkrechten Strichen aufgebaut. Mit der Zeit verfeinert sich die Grafik immer mehr, bis sie schliesslich nach dem vierten Durchlauf vollständig geladen ist.

On-line Capabilities Dialogue

Es wurden noch einige Anfragen und Nachrichten definiert, mit deren Hilfe sich ein GIF-Sender und ein GIF-Empfänger interaktiv über Grafikfähigkeiten und ähnliches verständigen können. Da diese aber nicht Teil einer GIF-Datei und mir auch keine Anwendungen dieses Protokolls bekannt sind, verweise ich für nähere Informationen auf die Spezifikation (siehe Literaturliste).

Benutzung der globalen Farbtabelle

Eine GIF-Datei kann ganz ohne Farbtabellen auskommen oder auch gar kein Bild enthalten, sondern nur den Kopf mit Farbtabelle.
Im ersten Fall wird dem Dekoder empfohlen, die letzte empfangene Farbtabelle zu verwenden. Dadurch kann man den zweiten Fall dazu benutzen, den Dekoder mit einer Farbtabelle zu initialisieren, und dann mehrere Bilder ohne Farbtabelle zu übertragen, auf welche diese erste Farbtabelle dann stets angewandt wird. Dadurch lässt sich die Menge der zu übertragenden Daten unter Umständen weiter senken.

Auswirkungen der Unisys-LZW-Lizenz

Grosse Verunsicherung gab es im Winter 1994/95, als die Firma Unisys mit der Meldung an die Öffentlichkeit trat, dass die LZW-Komprimierung von ihr patentiert sei und Unisys beabsichtige, Lizenzgebühren zu verlangen (siehe [5]) .
Tatsächlich hatte sich Unisys Corp. (damals noch unter dem Namen Sperry) am 20.6.1983 den LZW-Algorithmus patentieren lassen (US-Patent 4,558,302), ihn aber dennoch veröffentlicht.
Die Firma bemerkte nun tatsächlich erst zu Beginn der neunziger Jahre, dass LZW auch im GIF-Format (neben TIFF und PostScript) verwendet wird und handelte daraufhin 1993/94 mit CompuServe einen Lizenzvertrag aus, der aber nur Programme für CompuServes Online-Dienst betraf. Für alle sonstigen Programme sollten nun ebenfalls Lizenzgebühren anfallen, was einige Verwirrung, auch bei Unisys selbst, hervorrief: auf die anfängliche Meldung, kostenlose und bereits existierende Programme seien von der Regelung ausgenommen, folgten bald (als Firmen GIF-Plugins für ihre Programme verschenkten, um der Gebühr zu entgehen) verschiedene restriktive Korrekturen:
Die Lizenzpflicht wurde auf alle ab 1995 hergestellten Medien ausgedehnt, die LZW-Kode enthielten, auch wenn die entsprechenden Programme schon älter waren, sowie auf alles, was aus kommerziellen Softwarehäusern kam. "Echte" Freeware scheint zumindest von den Gebühren, nicht aber der Lizenzierung, verschont, kommerzielle Programme, die GIF-Bilder laden oder speichern können, werden pro verkauftem Exemplar mit Gebühren in Höhe von 0,45% des Kaufpreises, aber stets im Rahmen von 0,10$ bis 10$ belegt.
Die Bilder selbst oder ihr Betrachten oder Erstellen sind nicht von irgendwelchen Gebühren berührt.
Von CompuServe und anderen gingen schon im Januar 1995 Impulse für eine LZW-freie TrueColor-GIF Variante ("GIF24") aus, die im PNG-Format mündeten (siehe Vortrag 12). Doch ist damit das Ende von GIF noch lange nicht besiegelt, im Gegenteil: bis in den Sommer 1998 wurde LZW (u.a. für GIF) an über 1500 Firmen lizenziert, was es zu einem der meistlizensierten Patente der Welt macht.
 

Zusammenfassung

Man sieht, GIF geht über ein Format zum reinen Speichern von Computergrafiken weit hinaus. Wie kein anderes Bildformat kann GIF durch Erweiterbarkeit (durch Extension Blocks), spezielle Abstimmung auf DFÜ (interlaced-Darstellung), Spezialfunktionen (Animationen und Transparentfarbe), weite Verbreitung (auf allen gängigen Plattformen) und gute Packraten ohne Datenverlust (durch LZW-Kompression) glänzen.
Diese Eigenschaften machen GIF unter anderem zum idealen Grafikformat für das Internet.
Einzig für fotorealistische Grafiken, bei denen es nicht auf Identität mit dem Original, sondern allein auf den optischen Eindruck ankommt (wobei auch die Anzahl der Farben entscheidend ist), eignet sich das JPEG-Format (siehe Vortrag 11), vor allem auch durch seine hervorragenden Packraten, besser.
 

Literatur

Andreas Kunz 1. Januar 1999