Kodierung, Datenformate

Digitale oder elektronische Bildbearbeitung

Datenformate

Grafische Daten, die im Computer dargestellt werden sollen, werden traditionell aufbereitet in Form von Vektorgrafiken oder Rastergrafiken.

Vektorgrafik

Bei Vektorgrafiken werden Linien, Polygone oder Kurven anhand von bestimmten Schlüsselpunkten (Parameterwerten) charakterisiert, die schließlich durch ein Programm dargestellt werden. Z. B. könnte für einen Kreis ein Vektor (X-Koordinate, Y-Koordinate, Radius, Farbe, Linienstärke, Füllfarbe) abgespeichert werden, das darstellende Programm kann dann eindeutig diesen Kreis zeichnen. Vektorgrafiken können (beliebig) skaliert (vergrößert) werden, ohne das Rastereffekte auftreten. Vektorgrafiken sind im Allgemeinen nicht geeignet, fotorealistische Abbildungen zu speichern.

Rastergrafik

Rastergrafiken (oder Bitmapgrafiken) setzen sich zusammen aus einer Menge numerischer Werte, die Farb- und Helligkeitsinformationen einzelner Bildpunkte (Pixel) oder ganzer Bildelemente wiedergeben. Historisch gesehen steht die Rastergrafik mit der Entwicklung der Kathodenstrahlröhre als grafisches Ausgabegerät im Zusammenhang. Für eine Rastergrafik sind die folgenden Eigenschaften zu berücksichtigen:

• Die Bildauflösung (Picture Resolution) ist die Anzahl der Bildpunkte entlang der x-Achse und der y-Achse.

• Die Farbtiefe (Color Depth) bestimmt die Anzahl der Farben, mit denen ein Bildpunkt eingefärbt werden kann. Sie wird als Logarithmus log(c) (zur Basis 2) aller möglichen Farben c angegeben. Das ergibt die Anzahl der Bits, die benötigt werden um die Farbe eindeutig zuzuordnen. Z. B.: Für 256 Farben werden log(256)=8 (da 2^8=256) Bits benötigt. Von einer Echtfarbendarstellung kann erst ab 24Bit besprochen werden. Einige Systeme erlauben sogar 32Bit oder 48Bit Farbtiefe.

• Eine Farbpalette (Palett Size) wird von einigen Grafiksystemen verwendet, um die Anzahl der zur Ausgabe von Farben benötigten Bits zu reduzieren. Es wird von vorn herein festgelegt, welche Farben verwendet werden und welche nicht.

In einer Rastergrafik werden im einfachsten Fall die einzelnen Bildpunkte Zeile für Zeile nebeneinander abgespeichert. Dieses Verfahren hat als Nachteil, dass die Dateien sehr groß werden. Z. B. ein Bild mit einer Auflösung von 1500x1000 und einer Farbtiefe von 24-Bit benötigt dann 1500x1000x24 Bit(b) das entspricht 4.500.000 Byte(B) also 4,29MB (wobei 1B=8b, 1kB=1024B, 1MB=1024kB). Geht man davon aus, dass auf eine Diskette 1,44MB passen, so würde diese nicht mal für ein Bild dieser Größe genügen.

Abhilfe für dieses Problem schaffen Komprimierungsverfahren.

Einige wichtige Rastergrafik Datenformate:

Datei-Aufbau

Wie sieht eine Bilddatei eigentlich im Inneren aus? Im Allgemeinen haben alle Bilddateien einen ähnlichen Aufbau. Sie bestehen eigentlich immer aus zwei Teilen nämlich:

1. dem Header (Kopf) und
2. dem Datenteil.

Im Header stehen alle wichtigen Steuerinformationen z. B. welches Datenformat verwendet wird, welche Ausdehnungen das Bild hat, welche Kodierung(en) verwendet werden. Im Datenteil stehen die Bildaten meist in Form von Werten, die durch die verwendete Kodierung oder Komprimierung entstanden sind.

Siehe dazu zum Beispiel: JPEG#JPEG-Dateiaufbau

Komprimierungsverfahren

Komprimierungsverfahren sind in erster Linie dafür zuständig, Datenmengen zu reduzieren, um sie platz- und somit kostengünstig abzuspeichern oder zu transportieren. Es gibt eine ganze Reihe von Komprimierungsverfahren, jedes hat seine Vor- und Nachteile. Es ist im Allgemeinen immer so, dass es ein gewisses Gleichgewicht zwischen Stärke der Reduktion der Datenmenge und Handhabbarkeit/Kompliziertheit des Verfahrens gibt. Je mehr man vom einen hat, desto weniger hat man vom anderen.

In der digitalen Bildverarbeitung ist wohl die Unterscheidung in verlustfreie und verlustbehaftete Komprimierung (siehe auch JPEG Artefakte) von besonderem Interesse. Bei verlustfreien Komprimierungsverfahren wird die Kodierung und Dekodierung so durchgeführt, dass die ursprünglichen Daten nach dem Ausführen beider Verfahren wieder vollständig vorliegen. Die in den Ausgangsdaten enthaltene Information bleibt also vollständig erhalten. Verlustbehaftete Komprimierungsverfahren dagegen versuchen, eine höhere Komprimierungsrate zu erreichen, indem sie auf Teile der zu komprimierenden Information verzichtet, die für den vorgesehenen Verwendungszweck für weniger wichtig angesehen wird. Meist ist es möglich, dass der Benutzer selbst angibt, welche Kompressionsstärke verwendet werden soll. Das JPEG-Komprimierungsverfahren ist zum Beispiel ein verlustbehaftetes Verfahren, während bei GIF und BMP verlustfrei kodiert wird.

Das Ausmaß der Komprimierung wird als Komprimierungsrate/Kompressionsrate bezeichnet, das ist das Verhältnis der Größe der ursprünglichen Information zur Größe der komprimierten Information.

Manchmal ist es sinnvoll verschiedene Komprimierungsverfahren zu kombinieren wie zum Beispiel im TIFF-Format.

Lauflängenkodierung (Run Length Encoding, RLE)

Die einfachste Form von Redundanzen in einem Bild sind aufeinanderfolgende Bildpunkte gleicher Farbe. Man betrachte zum Beispiel die folgende Bildzeile (rot, grün, schwarz, blau):

Die Folge läßt sich viel kompakter kodieren, indem man aufeinanderfolgende Bildpunkte gleicher Farbe ersetzt durch ihre Anzahl und die Farbe:

Dieses Verfahren wird als Lauflängenkodierung bezeichnet. Es ist sehr gut geeignet für Bilder mit besonders vielen gleichfarbigen Anteilen. Die Effizienz schwindet allerdings bei Bildern mit sehr wechselhaften Farbanteilen wie zum Beispiel Rauschen. Im schlimmsten Fall kann sich die Datenmenge verdoppeln. Probiert es aus, die Lauflängenkodierung wird in BMP Bildern verwendet.

Die Lauflängenkodierung lässt sich nicht nur auf Pixel anwenden, sondern auch auf Binärdaten, die aus Folgen von 0 und 1 bestehen. Man spricht dann von Bit-Level Lauflängenkodierung. Weitere sind die Byte-Level Lauflängenkodierung sowie die Pixel-Level Lauflängenkodierung wie oben beschrieben. Es wäre auch denkbar auf Bildzeilen die Lauflängenkodierung anzuwenden.

LZW-Komprimierung

Das LZW-Verfahren ist benannt nach seinen Urhebern Abraham Lempel, Jacob Zif und Terry Welch. Lempel und Zif haben 1977 das LZ77-Substitutionskomprimierverfahren entwickelt, das in vielen Archivierungsprogrammen wie z. B. zoo, lha, pkzip oder arj verwendet wird. 1984 modifizierte Welch das Verfahren und es entstand der LZW-Algorithmus.

Das LZW-Verfahren ist für verschiedene Arten von Daten verwendbar. Es ist ein wörterbuchbasiertes Kodierungsverfahren, das zur Kodierung aus den Ursprungsdaten ein Wörterbuch aufbaut. Die auftretenden Datenmuster des Datenstroms (z.B. eine Folge von Pixeln Zeile für Zeile) werden den Wörterbucheinträgen zugeordnet. Kommt ein betrachtetes Datenmuster nicht im Wörterbuch vor, wird ein neues Codewort generiert und im Wörterbuch gespeichert. Tritt das Datenmuster erneut auf, so wird es durch das entsprechende Codewort ersetzt. Da die Codewörter eine kürzere Länge als das betrachtete Datenmuster haben, findet eine Komprimierung statt. Beim LZW Verfahren muss das Wörterbuch nicht mit den komprimierten Daten gespeichert werden, sondern beim Entpacken wird es aus den komprimierten Daten wieder aufgebaut.

Der Algorithmus und ein schönes Applet sind auf folgender Webseite zu finden:

http://www.cs.sfu.ca/cs/CC/365/li/squeeze/LZW.html

Die LZW-Komprimierung wird im GIF und im TIFF-Format verwendet.

Huffmann-Kodierung

Die Huffmann-Kodierung wurde 1952 von David A. Huffmann entwickelt.

Sie wird durch einen Binärbaum, also einem Baum, dessen Knoten nie mehr als 2 Kinder haben, erzeugt. Dabei wird ein sogenannter präfixfreier Code generiert. Ein präfixfreier Code ist dadurch charakterisiert, dass kein Codewort ein Anfangswort eines anderen Codewortes ist.

Nehmen wir folgende Bildzeile als Beispiel (rot, grün, schwarz, blau):

Man betrachte nun die Häufigkeiten der Farben:

Nun kann man den Binärbaum konstruieren. Je häufiger eine Farbe vorkommt, desto näher liegt sie an der Wurzel des Baumes und desto kürzer ist ihr Codewort. Die linken Kinder werden mit einer 0 markiert, die rechten mit einer 1. Geht man nun den Pfad von der Wurzel zu einem Blattknoten und notiert die 0en und 1en, so erhält man das Codewort für den entsprechenden Blattknoten.

Fehlendes Bild
Huffmann.gif
Bild:Huffmann.gif

Letztendlich können die Farben ersetzt werden durch ihre Codewörter.

Das Schöne am präfixfreien Code ist, dass man jetzt eindeutig ohne Trennzeichen von links nach rechts dekodieren kann.

Nun zur Kompressionsrate:

• unkomprimiert:

21 Pixel á 8Bit = 168Bit

• komprimiert:

14 Pixel á 1Bit +

5 Pixel á 2Bit +

4 Pixel á 3Bit = 36Bit

Natürlich muss auch noch eine Kodierungstabelle abgespeichert werden, dafür genügen 8Bit pro Codewort, also 32Bit.

Insgesamt werden mit Komprimierung also nur 36Bit+32Bit = 68Bit für obiges Beispiel benötigt.

Die Huffmann Kodierung wird im TIFF-Format verwendet.

JPEG-Kodierung

Hier wird auf den JPEG Artikel verwiesen.