Post on 19-Oct-2020
transcript
Graphics Interchange Format
Georg Kuschk11.06.2003
Seite 1/25Martin-Luther-Universität Halle
Inhalt :
1. Einführung2. Aufbau3. Beispiel4. LZW - Algorithmus im Überblick5. Zusammenfassung / Quellen
Seite 2/25Martin-Luther-Universität Halle
• Anfang der 80er Jahre wachsender Bedarf an Grafikformaten
• frühe Bildformate waren kaum standardisiert und bestanden häufig nur aus einer Kopie des Bildschirmspeichers
• Veröffentlichung von GIF in der Spezifikation der ersten Version '87a’ am 15.06.1987 (Steve Wilhite)
• entwickelt für Online-Transfer und Austausch von Rastergrafiken, unabhängig von der benutzten Hardware
• Der LZW-Kompressioncode ist allerdings patentiert (Unisys 1984)
• 1989 Erweiterung zu heutiger Version '89a’
• 1996 - Entwicklung einr TrueColor-GIF-Variante ('GIF24')die keinen LZW-Code benutzen sollte.=> PNG Format
Seite 3/25
1. Einführung - Entstehungsgeschichte
Martin-Luther-Universität Halle
• Sequentieller Aufbau (Aufteilung in fest definierte Blöcke), dadurch möglich :
- Verarbeitung von bereits empfangenen Daten - Hinzufügen von Zusatzinformationen (z.B. bei Animationen) - Speicherung von mehreren Bildern in derselben Datei
• Farbenpalette auf 256 Farben beschränkt
• keine Übertragungs-Fehlererkennung / -korrektur
• verlustfreie Kompression durch LZW-Algorithmus
Seite 4/25
1. Einführung - Eigenschaften
Martin-Luther-Universität Halle
::= {< Daten >}*
::= []
::= ’GIF87a’ | ’GIF89a’
::=
[] ::= (RGB)
Seite 5/25
2. Aufbau - GIF89a Grammatik
AnzahlderFarben
Beispiel : 47 49 46 38 39 61 10 00 10 00 B3 00 00 = GIF89a?·?·¦··
Version 89a / Breite = 16 / Höhe = 16
Farbtabelleninformation = 10110011 (globale Farbtabelle(unsortiert) mit 16 Einträgen folgt, 4 Bits je Farbe in der Ursprungsgrafik)
Hintergrundfarbe = 0 (d.h. keine Transparenzfarbe definiert)
Pixelgrössenverhaeltnis = 0 (d.h. quadratisch(Standard))
Martin-Luther-Universität Halle
::= | []
::= [] | []
::= 0x21 0xF9 0x00
Seite 6/25
2. Aufbau - GIF89a Grammatik
Beispiel : 21 F9 04 04 00 00 08 00 = !¨??··?·0x21 = ein Erweiterungsblock folgt
0xF9 = Kennung der Grafikkontrollerweiterung
04 = Blockgrösse in Byte
04 = 00000100 (Beseitigungsmethode : Grafik nicht beseitigen,Benutzerreaktion nicht abwarten)
0x00 0x00 = Verzögerungszeit(entfällt hier)
0x08 = Index der Transparenzfarbe
0x00 = Block-Abschluss-Zeichen
Martin-Luther-Universität Halle
Seite 7/25
2. Aufbau - GIF89a Grammatik
::= []
::= 0x2C
[] ::= (RGB)
::= {}*
::= 0x00
AnzahlderFarben
+
Beispiel : 2C 00 00 00 00 10 00 10 00 00 04 = ,····?·?··?0x2C = Kennung für Grafikdaten
0x00 0x00 0x00 0x00 = Startpunkt im definierten logischen Bildschirm (x,y)
0x10 0x00 0x10 0x00 = Breite = 16 / Höhe = 16
0x00 = Zusatzinformationen (hier: keine lokale Farbtabelle, nicht Interlaced ...)
0x04 = minimale LZW-Code-Grösse
Martin-Luther-Universität Halle
::= 0x21 0x01 {}* 0x00
::= |
::= 0x21 0xFF {}* 0x00
::= 0x21 0xFE {}* 0x00
Anhang ::= 0x3B
Seite 8/25
2. Aufbau - GIF89a Grammatik
+
+
+
Martin-Luther-Universität Halle
Seite 9/25
2. Aufbau - Blockstruktur
Veranschaulichung der sequentiellen Blockstruktur :
- Dateikopf - Logischer Bildschirm - Farbtabelle
- Dateikörper - Grafikblock - GrafikkontrollerweiterungsblockGrafikkontrollerweiterungsblock - Bildblock - BildkopfBildkopf - Farbtabelle - Bilddaten - Text-Erweiterungsblock
- Anwendungs-Erweiterung - Kommentar-Erweiterung
Martin-Luther-Universität Halle
Seite 10/25
2. Aufbau - Logischer Bildschirm
Martin-Luther-Universität Halle
G : ist dieses Bit gesetzt , folgt dem logischen Bildschirm eine globale Farbtabelle
cr (color resolution) : Farbtiefe der Ursprungsgrafik (2^{cr+1} Farben)
s (sort flag) : ist eine globale Farbtabelle vorhanden und dieses Bit gesetzt, so ist die Tabelle absteigend nach der Häufigkeit der Farben sortiert
pixel : Anzahl der Bits pro Pixel (2^{pixel+1}) = Größe der Farbtabelletabelle in RGB
Pixel Aspect Ratio : Verhältnis Pixelbreite : Pixelhöhe im Ursprungsbild
Seite 11/25
2. Aufbau - Globale / Lokale Farbtabelle
Martin-Luther-Universität Halle
Seite 12/25
2. Aufbau - Grafikkontrollerweiterung
res : reserviert, haben den festen Wert 0entf : Der Wert dieser drei Bits gibt an, wie mit der Grafik nach der Anzeige auf dem Bildschirm verfahren werden soll :
• 0 - kein bestimmtes Verfahren• 1 - Grafik nicht entfernen• 2 - Fläche wieder mit der ursprünglichen Hintergrundfarbe ausfüllen• 3 - früheren Hintergrund wiederherstellen• 4-7 - noch nicht definiert
B : wenn gesetzt, dann vor dem Anzeigen des nächsten Bildes entsprechend lange wartenT : wenn gesetzt, dann ist in Byte 6 der Index der Transparentfarbe angegeben
Martin-Luther-Universität Halle
Seite 13/25
2. Aufbau - Bildkopf
L : wenn gesetzt, so folgt nach dem Bildkopf eine lokale FarbtabelleI : wenn gesetzt, so ist die Grafik "interlaced" gespeichert : jede 8-te Zeile (beginnend mit der 0.Zeile)
jede 8-te Zeile (beginnend mit der 4.Zeile)jede 4-te Zeile (beginnend mit der 2.Zeile)jede 2-te Zeile (beginnend mit der 1.Zeile)
s (sort flag): Ist eine lokale Farbtabelle vorhanden und dieses Bit gesetzt, so ist die Tabelle absteigend nach der Häufigkeit der vorkommenden Farben sortiert
res : reserviert, haben den festen Wert 0pixel : Größe der lokalen Farbtabelle, sofern vorhanden
Martin-Luther-Universität Halle
Seite 14/25
2. Aufbau - Text-Erweiterung
Martin-Luther-Universität Halle
Seite 15/25
2. Aufbau - Kommentar-Erweiterung
Martin-Luther-Universität Halle
Seite 16/25
2. Aufbau - Anwendungs-Erweiterung
Martin-Luther-Universität Halle
Seite 17/25
3. Beispiel
Adr.Dez 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ASCII ---------- 0 47 49 46 38 39 61 10 00-10 00 B3 00 00 FF FF 00 GIF89a?·?·¦·· · 16 C0 C0 C0 00 FF 00 80 80-80 80 80 00 00 80 00 FF +++· ·ÇÇÇÇÇ··Ç· 32 00 00 00 00 00 FF FF FF-00 00 00 00 00 00 00 00 ····· ········ 48 00 00 00 00 00 00 00 00-00 00 00 00 00 21 F9 04 ·············!¨? 64 05 14 00 08 00 2C 00 00-00 00 10 00 10 00 00 04 ?¶·?·,····?·?··? 80 4F 10 C9 49 AB BD 74 E8-CD F9 41 43 21 8E 45 20 O?+I½¢tÞ-¨AC!ÄE 96 14 42 50 7C 83 11 84 C1-51 96 47 10 1F E1 A1 EB ¶BP|â?ä-QûG??ßíÙ 112 B3 AE EA AD 17 6D 26 B2-01 57 3B 99 6D 89 84 C1 ¦«Û¡?m&¦?W;Ömëä- 128 94 B3 1F 0E B9 EB AD 56-20 D2 48 45 FA 24 77 03 ö¦??¦Ù¡V ÊHE·$w? 144 00 41 BC C3 84 C7 84 0F-06 F1 55 AF DF F0 49 04 ·A++äÃä¤?±U»¯-I? 160 00 3B EOF-- -- -- -- ----- -- -- -- -- -- -- -- ·;?
------- DateiKopf ----------------------------------Byte 0-5 : SignaturByte 6/7 : Breite = 0x10 0x00 = 16Byte 8/9 : Höhe = 0x10 0x00 = 16Byte 10 : Farbtabelleninformation = 0xB3 = 179 = 10110011 (MSB - B8->B1)
-> Bit8 = 1 , globale farbtabelle folgt Bit7-Bit5 = 011 , 4 Bits je Primärfarbe in der Ursprungsgrafik Bit4 = 0 , Farbtabelle unsortiert Bit3-Bit1 = 011 , 2^4 = 16 Farbeinträge in der globale Farbtabelle
Byte 11 : Hintergrundfarbe = 0 -> keine Transparenzfarbe im logischen Bildschirm definiertByte 12 : Pixelgrössenverhältnis = 0 -> quadratisch
Martin-Luther-Universität Halle
Seite 18/25
3. Beispiel
Adr.Dez 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ASCII ---------- 0 47 49 46 38 39 61 10 00-10 00 B3 00 00 FF FF 00 GIF89a?·?·¦·· · 16 C0 C0 C0 00 FF 00 80 80-80 80 80 00 00 80 00 FF +++· ·ÇÇÇÇÇ··Ç· 32 00 00 00 00 00 FF FF FF-00 00 00 00 00 00 00 00 ····· ········ 48 00 00 00 00 00 00 00 00-00 00 00 00 00 21 F9 04 ·············!¨? 64 05 14 00 08 00 2C 00 00-00 00 10 00 10 00 00 04 ?¶·?·,····?·?··? 80 4F 10 C9 49 AB BD 74 E8-CD F9 41 43 21 8E 45 20 O?+I½¢tÞ-¨AC!ÄE 96 14 42 50 7C 83 11 84 C1-51 96 47 10 1F E1 A1 EB ¶BP|â?ä-QûG??ßíÙ 112 B3 AE EA AD 17 6D 26 B2-01 57 3B 99 6D 89 84 C1 ¦«Û¡?m&¦?W;Ömëä- 128 94 B3 1F 0E B9 EB AD 56-20 D2 48 45 FA 24 77 03 ö¦??¦Ù¡V ÊHE·$w? 144 00 41 BC C3 84 C7 84 0F-06 F1 55 AF DF F0 49 04 ·A++äÃä¤?±U»¯-I? 160 00 3B EOF-- -- -- -- ----- -- -- -- -- -- -- -- ·;?
------- globale Farbtabelle ------------------------16*3 Bytes für FarbtabelleByte 13-60Farbe00 = RGB(0xFF, 0xFF, 0x00) Farbe01 = RGB(0xC0, 0xC0, 0xC0)Farbe02 = RGB(0x00, 0xFF, 0x00) Farbe03 = RGB(0x80, 0x80, 0x80)Farbe04 = RGB(0x80, 0x80, 0x00) Farbe05 = RGB(0x00, 0x80, 0x00)Farbe06 = RGB(0xFF, 0x00, 0x00) Farbe07 = RGB(0x00, 0x00, 0x00)Farbe08 = RGB(0xF0, 0xF0, 0x00) Farbe09 = RGB(0x00, 0x00, 0x00)Farbe10 = RGB(0x00, 0x00, 0x00) Farbe11 = RGB(0x00, 0x00, 0x00)Farbe12 = RGB(0x00, 0x00, 0x00) Farbe13 = RGB(0x00, 0x00, 0x00)Farbe14 = RGB(0x00, 0x00, 0x00) Farbe15 = RGB(0x00, 0x00, 0x00)
Martin-Luther-Universität Halle
Seite 19/25
3. Beispiel
Adr.Dez 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ASCII ---------- 0 47 49 46 38 39 61 10 00-10 00 B3 00 00 FF FF 00 GIF89a?·?·¦·· · 16 C0 C0 C0 00 FF 00 80 80-80 80 80 00 00 80 00 FF +++· ·ÇÇÇÇÇ··Ç· 32 00 00 00 00 00 FF FF FF-00 00 00 00 00 00 00 00 ····· ········ 48 00 00 00 00 00 00 00 00-00 00 00 00 00 21 F9 04 ·············!¨? 64 05 14 00 08 00 2C 00 00-00 00 10 00 10 00 00 04 ?¶·?·,····?·?··? 80 4F 10 C9 49 AB BD 74 E8-CD F9 41 43 21 8E 45 20 O?+I½¢tÞ-¨AC!ÄE 96 14 42 50 7C 83 11 84 C1-51 96 47 10 1F E1 A1 EB ¶BP|â?ä-QûG??ßíÙ 112 B3 AE EA AD 17 6D 26 B2-01 57 3B 99 6D 89 84 C1 ¦«Û¡?m&¦?W;Ömëä- 128 94 B3 1F 0E B9 EB AD 56-20 D2 48 45 FA 24 77 03 ö¦??¦Ù¡V ÊHE·$w? 144 00 41 BC C3 84 C7 84 0F-06 F1 55 AF DF F0 49 04 ·A++äÃä¤?±U»¯-I? 160 00 3B EOF-- -- -- -- ----- -- -- -- -- -- -- -- ·;?
-------- Grafikkontrollerweiterung ---------------------Byte61/62 = 0x21 0xF9 -> GrafikkontrollerweiterungByte63 = 4 (Blockgrösse)Byte64 = 5 -> Bit1 = 1 , Transparenzfarbe ist gegeben
Bit 3 = 1, Beseitigungsmethode : Grafik nicht beseitigenByte65/66 = 0x14 0x00 = 20 - 0,2 sekunden wartenByte 67 = 8 = Index der Transparenzfarbe (Farbe08)Byte68 = 0 = Block-Abschluss-Zeichen
Martin-Luther-Universität Halle
Seite 20/25
3. Beispiel
Adr.Dez 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ASCII ---------- 0 47 49 46 38 39 61 10 00-10 00 B3 00 00 FF FF 00 GIF89a?·?·¦·· · 16 C0 C0 C0 00 FF 00 80 80-80 80 80 00 00 80 00 FF +++· ·ÇÇÇÇÇ··Ç· 32 00 00 00 00 00 FF FF FF-00 00 00 00 00 00 00 00 ····· ········ 48 00 00 00 00 00 00 00 00-00 00 00 00 00 21 F9 04 ·············!¨? 64 05 14 00 08 00 2C 00 00-00 00 10 00 10 00 00 04 ?¶·?·,····?·?··? 80 4F 10 C9 49 AB BD 74 E8-CD F9 41 43 21 8E 45 20 O?+I½¢tÞ-¨AC!ÄE 96 14 42 50 7C 83 11 84 C1-51 96 47 10 1F E1 A1 EB ¶BP|â?ä-QûG??ßíÙ 112 B3 AE EA AD 17 6D 26 B2-01 57 3B 99 6D 89 84 C1 ¦«Û¡?m&¦?W;Ömëä- 128 94 B3 1F 0E B9 EB AD 56-20 D2 48 45 FA 24 77 03 ö¦??¦Ù¡V ÊHE·$w? 144 00 41 BC C3 84 C7 84 0F-06 F1 55 AF DF F0 49 04 ·A++äÃä¤?±U»¯-I? 160 00 3B EOF-- -- -- -- ----- -- -- -- -- -- -- -- ·;?
--------- Grafikdaten Bildkopf -------------------------------Byte69 = 0x2C -> GrafikdatenByte70/71 = 0x00 0x00 x-Position im logischen BildschirmByte72/73 = 0x00 0x00 y-Position im logischen BildschirmByte74/75 = 0x10 0x00 = 16 , BildbreiteByte76/77 = 0x10 0x00 = 16 , BildhöheByte 78 = 0x00 , Zusatzinformationen (keine lokale Farbtabelle, nicht Interlaced)Byte79 = 4 , Minimale LZW-Code-Grösse (in Bit)
Martin-Luther-Universität Halle
Seite 21/25
3. Beispiel
Adr.Dez 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ASCII ---------- 0 47 49 46 38 39 61 10 00-10 00 B3 00 00 FF FF 00 GIF89a?·?·¦·· · 16 C0 C0 C0 00 FF 00 80 80-80 80 80 00 00 80 00 FF +++· ·ÇÇÇÇÇ··Ç· 32 00 00 00 00 00 FF FF FF-00 00 00 00 00 00 00 00 ····· ········ 48 00 00 00 00 00 00 00 00-00 00 00 00 00 21 F9 04 ·············!¨? 64 05 14 00 08 00 2C 00 00-00 00 10 00 10 00 00 04 ?¶·?·,····?·?··? 80 4F 10 C9 49 AB BD 74 E8-CD F9 41 43 21 8E 45 20 O?+I½¢tÞ-¨AC!ÄE 96 14 42 50 7C 83 11 84 C1-51 96 47 10 1F E1 A1 EB ¶BP|â?ä-QûG??ßíÙ 112 B3 AE EA AD 17 6D 26 B2-01 57 3B 99 6D 89 84 C1 ¦«Û¡?m&¦?W;Ömëä- 128 94 B3 1F 0E B9 EB AD 56-20 D2 48 45 FA 24 77 03 ö¦??¦Ù¡V ÊHE·$w? 144 00 41 BC C3 84 C7 84 0F-06 F1 55 AF DF F0 49 04 ·A++äÃä¤?±U»¯-I? 160 00 3B EOF-- -- -- -- ----- -- -- -- -- -- -- -- ·;?
-------- Datenblock --------------------------------Byte80 = Blockgrösse = 0x4F = 79->Byte81-159 = LZW-codierte FarbindizesByte160 = 0 = Block-Abschluss-Zeichen
-------- Anhang --------------------------------Byte161 = 0x3B = Anhang – Ende der GIF Datei
Martin-Luther-Universität Halle
• Erstellung eines Wörterbuchs
• unkomprimierter Datenstrom wird in Zeichenketten zerlegt
• Vergleich mit den bereits vorhandenen Zeichenketten im Wörterbuch - wenn bereits vorhanden, so wird nur der Wörterbuchindex ausgegeben - ansonsten neuer Wörterbucheintrag
• => Die Kompressionsrate hängt von der Datenstruktur und von der Kunst des Programmierers ab.
Seite 22/25
4. Lempel-Ziv-Welch Algorithmus im groben Überblick
Martin-Luther-Universität Halle
Vorteile von GIF :
• Erweiterbarkeit und Spezialfunktionen durch die Erweiterungs-Blöcke
• spezielle Abstimmung auf Datenfernübertragung durch die Interlaced-Darstellung
• weite Verbreitung auf allen gängigen Plattformen
• gute Packraten ohne Datenverlust durch die LZW-Kompression
• Definition einer transparenten Farbe möglich
• jeder gängige browser kann GIF verarbeiten (ohne Plug-in) allerdings werden nicht alle Funktionen von GIF unterstützt (UserInput, PlainText)
Nachteile :
• Niedrige Anzahl an Farben
• Datenkomprimierung ist lizenzpflichtig
Seite 23/25
5. Zusammenfassung
Martin-Luther-Universität Halle
Seite 24/25
5. Zusammenfassung - Die Zukunft von GIF
1984 LZW-Algorithmus wird entwickelt und von Unisys patentiert1994 Lizenzgebühren für Software-Entwickler (1.5%)1999 Lizenzgebühren für Betreiber von kommerzielle Websites (2500$ je Server)
Aufgrund des Patentproblems und dem veralteten Funktionsumfang dürfte dieVerbreitung von GIF in Zukunft zurückgehen.
Den freien Platz dürfte dann vor allem PNG einnehmen.
Martin-Luther-Universität Halle
• www.w3.org/Graphics/GIF/spec-gif87.txt (GIF-Spezifikationen) www.w3.org/Graphics/GIF/spec-gif89a.txt
• http://goethe.ira.uka.de/seminare/rftk/ (zip/gif/jpg/png/lzw/huffman...)
• http://lpf.ai.mit.edu/Patents/Gif/gif_lic.html (offizielle Lizenzvereinbarung)• http://www.comrecht.de/deutsch/recht/pub/gifkontroverse.htm (LZW-Patent)• http://burnallgifs.org/ (Patent-Gegner)
Seite 25/25
Quellen
Martin-Luther-Universität Halle