Kompression und Datenformate.key

Sinnvoll beim Auftreten von stark redundanten Datenmustern,
wie z. B. flächige Farben
Verwendung eines Kennzeichens zur Unterscheidung von
Wiederholungsfaktor und Datenwort (z. B. 0).
Einfachwiederholung zur Darstellung des Kennzeichen als
Datenwort.
Beispiel:
– Originaldaten:
– RLE-Kodierung:
RLE, LZW, Huffmann, CCITT, ZIP
12341114222278555557888888888966666603744
1234031404278055709890660103744
wobei die ''0'' das Wiederholungskennzeichen ist.
Formate: TIFF, PCX
Kompression • Verlustfreie Verfahren
Urprungsformat 1977 von Abraham Lempel und Jakob Ziv »LZ77«
Verwendung in Textverarbeitungsprogrammen, dem UNIX-Programm
»compress«, in den Paketen »zoo«, »lha«, »pkzip«, und »arj«.
Modifizierter »LZ78« Algorithmus für Binärdateien und Bitmaps.
1984 Modifikation des »LZ78« durch Terry Welch bei Unisys für
»high-performance disc controller« in den heute bekannten »LZW« Algorithmus.
Stufenweise Erstellung eines Wörterbuches (Übersetzungstabelle)
aus dem Datenstrom (substitutions- oder wörterbuchbasierender Algorithmus)
Algorithmus war bis 2007 patentgeschützt (Compuserve/Unisys)
Kompression • Verlustfreie Verfahren
Folie 27
Folie 26
Kompression:
Dekompression:
set w = NIL
read a character k
output dictionary entry for k
w = k
loop
read a character k
entry = dictionary entry for k
output entry
add dictionary entry for w +
first char of entry
to the dictionary
w = index of entry
endloop
loop
read a character k
if wk exists in the
dictionary
w = wk
else
output the code for w
add wk to the dictionary
w = k
endloop
Kompression • Verlustfreie Verfahren
Folie 28
Beispiel:
– Originaldaten: ABACABA...
– LZW-Kodierung: 010240...
Vorteil:
Tabelle muss nicht
mit übertragen werden
Formate:
Index
0
1
2
3
4
5
6
7
8
Substring
A
B
C
D
AB
BA
AC
CA
ABA
GIF, TIFF, PostScript Level 2,
V.42bis Modemkompression
JPEG, PNG, MP3, MPEG
Kompression • Verlustfreie Verfahren
Folie 29
Kommunikationsprotokolle für die Übermittlung von Schwarzweiß - Bildern
»CCITT T.4« entspricht »CCITT Group 3«-Kompression (Fax)
»CCITT T.6« entspricht »CCITT Group 4«-Kompression (1-Bit-Bildformate)
Vorgegebene Codetabelle, die durch die CCITT aus einer Sammlung von
Referenzdokumenten mit Bildern und Texten gewonnen wurde
CCITT-Kodierung ist eine Art Spezialfall der »Huffman-Kompression«
Kompressionsverhältnis von 5:1 bis 8:1 bei »Group 3«
bei Auflösung von 200dpi (204x196dpi) auf DIN-A4 Seiten
»Group 4« erzielt um das doppelte verbesserte Ergebnisse
Beispiele:
David A. Huffman 1952
Erstellung einer Tabelle mit variabler Wortlänge
(Kodierung auf Bitebene)
Häufige Werte erhalten kurze Tabellenworte
Aufteilung eines Dokumentes in mehrere Blöcke
„Nachteil“: Tabelle der Kodierung muss übermittelt werden
Beispiele:
Details: Vgl. VL ADS
Kompression • Verlustfreie Verfahren
Folie 30
Archivierungs- und Kompressionsformat
– Containerformat
– Zugriff auf einzelne Dateien und Pfade möglich
9 verschiedene Stufen/Kompressionen möglich
Verbreitet ist der DEFLATE-Algorithmus
– Kombination von LZW-Kompression und
Huffman-Codierung
Beispiele:
PKzip, GZIP, Acrobat, TIFF, OpenDocument
Fax, TIFF
Kompression • Verlustfreie Verfahren
Folie 31
Kompression • Verlustfreie Verfahren
Folie 32
»Joint Photographic Experts Group« ist ein Standardisierungskomitee
der »International Standard Organization« (ISO) und
der »International Telecommunication Union« (ITU).
JPEG ist ein Zusammenschluß der ISO-PEG
(»Photographic Experts Group«)
»Entwicklung von Methoden zur effizienten Transmission von Text und
Standbildern über ISDN-Verbindungen« (1987)
und einer Untergruppe der CCITT (umbenannt in ITU)
»Entwicklung von Kompression für Grauwertbildern
bei FAX-Übertragungen« (1986)
Beispiel: JPEG-Verfahren, Wavelet-Verfahren
Kompression • Verlustbehaftete Verfahren
JPEG ist keine eigenständige Kompressionsmethode
– Bibliothek parametrisierbarer Algorithmen, die den Grad der Kompression
und den Grad der entstehenden Verluste steuern
(Qualitätsfaktor Q=1 hoher Verlust; Q = 100 geringer Verlust)
JPEG Kompression für Fotomotive geeignet
– JPEG-Kompression entworfen für farbige oder grauwertbehaftete
Abbildungen von natürlichen Objekten (typisch Fotos)
– Bilder mit mindestens vier oder fünf Bit Auflösung pro Pixel.
– JPEG benötigt Bilder, bei denen sich benachbarte Pixel nicht allzu stark
unterscheiden.
Folie 34
»Psychovisuelle Kompression«
– Kleine Änderungen im Farbton registriert das menschliche Auge nicht so
sehr wie kleine Helligkeitsänderungen. Dadurch Reduktion der Farben
möglich.
Kompression • Verlustbehaftete Verfahren
Folie 35
Die JPEG-Kompression zerfällt in 5 Einzelschritte:
1. Transformation des Bildes aus RGB in einen geeigneten
Farbraum (Standard: YUV)
2. Herunterskalieren der Farbtonkomponenten durch Mittelung
über mehrere Pixel
3. Anwendung der diskreten Cosinustransformation (DCT)
4. Gewichtung (Quantisierung) der Koeffizienten der DCT
5. Codierung der gewichteten Koeffizienten mit variabler
Wortlänge (Hufmann)
Kompression • Verlustbehaftete Verfahren
Folie 36
1 Kanal für Helligkeit
Y = Luminanz = 0,299 R + 0,587 G + 0,114 B
2 Kanäle für Farbinformationen
U = ChrominanzB = B - Y
Herunterskalieren der Farbtonkomponenten
durch Mittelung über mehrere Pixel
V = ChrominanzR = R - Y
Zusammenfassung benachbarter, nahezu gleichfarbiger
Pixelwerte (»Psychovisuelle Kompression«)
Kompression • Verlustbehaftete Verfahren
Folie 37
Folie 38
• DCT Funktion wandelt
Intensitätswerte in Frequenzwerte (verlustfrei!!!)
• Frequenzwert beschreibt die Änderung der Details eines Macro-Blocks
•Zerlegung der jeweils drei Kanäle (YUV oder YIQ oder
RGB) in Blöcke von 8 x 8 Pixeln
Kompression • Verlustbehaftete Verfahren
Kompression • Verlustbehaftete Verfahren
– Hohe Detailänderung = hohe Frequenz = Werte im Bereich 0
– Geringe Detailänderung = niedrige Frequenz = große Werte
Folie 39
Kompression • Verlustbehaftete Verfahren
Folie 40
Ermittlung von jeweils 64 Koeffizienten anhand von 64
Basisfunktionen der DCT
F(x)
Division der 64 Koeffizienten durch die Quantisierungstabelle und
ganzzahlige Rundung
Die Quantisierungstabelle berücksichtigt die Farb- und
Helligkeitsempfindlichkeit des Auges
Verkleinerung des Wertebereiches, viele Koeffizienten werden Null
Qualitätsfaktor wird mit der Quantisierungstabelle multipliziert
DIV
=
quantisation matrix
Kompression • Verlustbehaftete Verfahren
Folie 41
Blockübergreifende Codierung der Koeffizienten
Verwendung von Huffmann Codes mit variabler Wortlänge
Kompression • Verlustbehaftete Verfahren
Folie 42
Sequentiell
Auch Baseline Modus genannt
Progressiv
Zunächst werden die wichtigsten Bits aller AC Koeffizienten
übertragen (approximative Übertragung)
Hierarchisch
Bild wird zunächst in grober Auflösung codiert,
die nächstfeinere Auflösung wiederum wird nur als
Differenz zur gröberen übertragen usw.
Kompression • Verlustbehaftete Verfahren
Folie 43
Kompression • Verlustbehaftete Verfahren
Folie 44
Kompression • Verlustbehaftete Verfahren
Folie 45
• JPEG teilt Bild in Makroblöcke, Frequenztransformation blockweise
• Wavelet transformiert gesamtes Bild in den Frequenzraum (Koeffizienten)
• Koeffizienten leichter zu komprimieren,
Die JPEG-Standardisierung ist kein »starres« Kompressionsverfahren
sondern definiert nur die algorithmischen Grundprinzipien
Die konkrete Implementierung bleibt flexibel (Farbmodell,
Quantisierungstabellen, Koeffizientenkodierung, usw.)
– Information auf einige wenige Koeffizienten konzentriert
– Dieses Prinzip heißt auch Transform Coding.
• Koeffizienten werden quantisiert und die quantisierten Werte
entropiekodiert und/oder lauflängenkodiert.
JPEG 2000 (www.jpeg.org/JPEG2000.htm)
–
–
–
–
–
–
Folie 46
Ergänzung zum JPEG-Format
Wavelet Transformation an Stelle der DCT (keine Block-Artefakte mehr)
Verlustfreie Kompression möglich
Compound Documents (verschiedene Auflösungen innerhalb eines Bildes)
Verschlüsselung und Zusatzinformationen
Alpha-Kanäle
Kompression • Verlustbehaftete Verfahren
Folie 47
Kompression • Verlustbehaftete Verfahren
Folie 48
Kompression • Verlustbehaftete Verfahren
Folie 49
Kompression • Verlustbehaftete Verfahren
Rasterformate
Vektorformate
Kompression • Verlustbehaftete Verfahren
Folie 51
Folie 50
Wie lassen sich Datenformate klassifizieren?
Was gibt es für gängige Formate?
Wie sind diese Formate aufgebaut?
Für welchen Zweck eignen sich die Formate?
Foto-/Rasterformate
– TIFF, GIF, PNG, JPEG/JFIF/EXIF...
Grafik-/Vektorformate
– DXF, HPGL, EPSF, SVG, ...
Bilddateiformate
Folie 53
Bilddateiformate
Folie 54
Speicher sparen
Schnelles Öffnen und Speichern
Kompatibilität: Austauschbarkeit und
Verwendbarkeit mit verschiedenen Programmen
und Betriebssystemen
Verwendbarkeit für das World Wide Web
Verwendung von Ebenen, Alphakanälen u.a.
TIFF, GIF, BMP, PNG
Bildformate • Rasterformate
Folie 56
Rasterung
– Digitalisierung/Scannen eines Bildes
– Bildung von Pixelwerten mit Helligkeitsund/oder Farbwerten
Auflösung
– 72-100 dpi Bildschirm
– 300-1200 dpi Laserdrucker
– 1200-2400 dpi Fotosatz-Belichter
Beispiel: 72dpi
300dpi
1200dpi
2400dpi
500fache Vergrößerung
Bildformate • Rasterformate
Folie 57
Bildgröße
Farbtiefe
– Anzahl der Farben insgesamt oder pro (Farb-)Kanal
Farbmodelle
– RGB, CMYK, HSB, LAB, YUV, YIQ
Folie 58
Header oder Trailer
– Abmessung in cm oder Pixel in Abhängigkeit von der Auflösung
– Grösse des Bildes hat unmittelbaren Einfluss auf die Dateigröße
Bildformate • Rasterformate
Kanäle
– Farbkanäle, z. B. RGB, ...
– Alphakanäle, z. B. Masken, Transparenz, ...
– Volltonkanäle, z. B. Gold, Pantone, ...
Bildformate • Rasterformate
– Dateiidentifikation z. B. »GIF« (GIF), »%!« (PostScript),
»0x59a66a95h« (Sun Raster)
– Dateiversion z. B. »GIF87a«, »GIF89a«
– Anzahl der Zeilen pro Bild
– Anzahl der Pixel pro Zeile
– Anzahl der Bit pro Pixel
– Anzahl der Farbebenen
– Art der Kompression
Beispiel GIF
– Kommentartext, ...
Datenteil
Folie 59
Header LSD GCM Extension Data Term
Bildformate • Rasterformate
Folie 60
Am weitesten verbreitetes und am häufigsten unterstütztes
Print-Format
Unterstützt die LZW Komprimierung (20-50% Speicherersparnis)
Unterschiedliche Kodierung im Mac/PC-Format
Bildformate • Rasterformate
TIFF-Dateien zerfallen in drei Hauptbestandteile
– Image File Header (IFH) markiert eine Tiff-Datei
– File Directory (IFD) enthält eine beliebige Liste von »tags« mit Pointern
– Bitmapdaten
Folie 61
Neben LZW werden weitere Verfahren zur Datenverdichtung
angeboten
(Erweiterte TIFF-Speicherungsoptionen):
– Verlustlose ZIP-Kompression (geringfügig effektiver als LZW)
– PACKBITS- Export (RLC)
– Verlustbehaftete JPEG-Kompression (nicht für mehrere Ebenen)
Bildformate • Rasterformate
Unterstützung von Transparenz.
Bildpyramide für schnellere Bildübersicht bei großen Dateien.
Folie 62
Entwicklung durch CompuServe zur WEB-Übertragung
GIF, das erste Streamingformat ???
Nur 256 Farben!
Unterstützung von Transparenz
Kompression immer LZW
ACHTUNG: Das erweiterte TIFF-Format wird nicht von allen
Anwendungen unterstützt.
Bildformate • Rasterformate
Folie 63
Animated GIF:
Standard für kleine Filme im WEB
In allen Internet-Browsern darstellbar
Geeignet vor allem für plakative Grafiken
(Schriftzüge, Logos, Zeichnungen, Bildschirmfotos etc.)
Bildformate • Rasterformate
Folie 64
Folge von Datenpaketen (Blocks) und
Protokollinformationen
Pixeltiefe zwischen 1 und 8 Bit, Palette im RGB-Farbmodell
Versionen
– GIF87a (Ursprungsformat, Mai 1997)
– GIF89a (Ermöglicht Definition von Erweiterungsblöcken,
z. B. für Kommentare, Transparenzangaben, usw.)
Bildformate • Rasterformate
»ping« wurde speziell für das WEB-Publishing entworfen
Bis zu 48-Bit Farbtiefe und 16 Bit Graustufen und Transparenz
Alpha-Kanäle
Gamma-Korrektur
2-dimensionales Interlacing
Lizenzfreie verlustfreie Kompression: Huffman
Eher begrenzte Verbreitung im WEB
www.w3.org/graphics/PNG/overview.html
Folie 65
Bildformate • Rasterformate
Folie 66
JPEG-Dateiformat, basiert auf JPEG-Kompression
Farbtiefe von 8 und 24 Bit, Thumbnail-Preview möglich
Tags für Copyright- & Dateiinformationen (IPTC-Informationen)
Tags für Farbprofile zum Farbmanagement (ICM-Daten)
Windows - OS/2 System-Grafikformat (Icons,
Mauszeiger, ...)
1 bis 24-Bit Farbtiefe
Datei besteht aus
Frame Header
– Bitmap-file header, Bitmap-information header, Farbtabelle,
– Bitmap-Bits (Anordnung der Bitmapdaten)
Verlustfreie Kompression (RLE)
Sample Precision
Bit/Pixel
Width, Height
Breite und Höhe in Pixel
# of components
Anzahl der Komponenten
ID
Eindeutige Benennung
Horizontal/Vertical
Sampling Factor
Auflösung
Quantisation Table
Scan Header
# of components
Anzahl der Komponenten
Component ID
Eindeutige Benennung
Huffman Table
Bildformate • Rasterformate
Folie 67
Bildformate • Rasterformate
Folie 68
JPEG-Variante mit Zusatzinformationen für Digitalkameras
Informationsfelder (Tags) für Kameraeinstellungen
Blende, Belichtungszeit, Weißabgleich, GPS-Koordinaten
DXF, IGES, HPGL, EPSF, SVG
Bildformate • Rasterformate
Folie 69