Datenkompression
Verlustfreie Datenkompression – Lauflängencodierung
Bei der Datenkompression (auch: Datenkomprimierung) wird die Menge an Daten reduziert, also verringert. Wenn die Verringerung der Datenmenge mit einem Qualitätsverlust einher geht, spricht man vonverlustbehafteter Datenkompression, ansonsten von verlustfreier Kompression. Dabei ist es unwesentlich, ob der Qualitätsverlust wahrnehmbar ist oder nicht. Relevant ist nur, ob die ursprüngliche Datei aus den reduzierten Daten wiederhergestellt werden kann oder nicht.
In Aufgabe 1 werden zwei Bilder verglichen, die dasselbe Format, aber ein ganz unterschiedliches Datenvolumen haben. Der Inhalt der Datei beeinflusst also deren Größe.
Die SuS analysieren in Aufgabe 2 eine Lauflängencodierung (engl.: RLE, Run Length Encoding) (9s 6w 2s 1w 1s 2w 1s 1w 2s 6w 2s 1w 4s 1w 2s 6w 9s) und ermitteln daraus die Bilddaten.
Bei Schwarzweiß-Bildern kann die Information, dass auf 9 schwarze Pixel 6 weiße folgen, weggelassen werden, weil schwarze und weiße Pixel sich abwechseln. Die Bilddaten können weiter reduziert werden zu: 9 6 2 1 1 2 1 1 2 6 2 1 4 1 2 6 9. Wichtig ist hierbei, dass eine Vereinbarung getroffen werden muss, mit welcher Farbe begonnen wird.
Im Kompressionsalgorithmus ist festgelegt, mit wie vielen Bit eine Zahl codiert wird. Diese Bitanzahl ist nicht abhängig vom der jeweiligen Datei. Denkbar wäre allerdings auch, dass ein Kompressionsalgorithmus die Datei analysiert und die kleinstmögliche Codierung für eine Zahl festlegt – individuell für jede Datei.
In Aufgabe 3 wird die Lauflängencodierung geübt und die Speicherplatzersparnis berechnet. Eventuell erkennen die SuS bereits an dieser Stelle, dass nicht immer eine Ersparnis erreicht wird (Aufgabe 4).
Im Bild aus Aufgabe 2 wird beispielsweise keine Reduzierung erreicht. Ein einzelnes Pixel benötigt (bei binärer Speicherung) 1 Bit Speicher, 9 Pixel benötigen 9 Bit Speicher. Kommen 9 gleiche Pixel vor, benötigt man 4 Stellen, um die Zahl 9 binär darzustellen, also 4 Bit. Allerdings werden dann auch '2 weiße Pixel' mit 4 Bit codiert. Erst ab 5 gleichartigen Pixel ergibt sich also eine Einsparung durch die Lauflängencodierung.
Nach dieser Erkenntnis kann man mit den SuS Verbesserungsvorschläge sammeln, um die Lauflängencodierung effektiver zu gestalten (Aufgabe 7 b).
Ein Verbesserungsvorschlag könnte sein, dass die Lauflängencodierung nur angewendet wird, wenn es eine Verbesserung bringt. Im Beispiel aus Aufgabe 2 sähe das so aus:
9 6 sswswwswss 6 sswsssswss 6 9 bzw.: 9 6 1101001011 6 1101111011 6 9
Hinweis: Die entstehende Problematik erkennen die SuS eventuell erst, wenn die binäre Darstellung betrachtet wird: Wie kann unterschieden werden, ob es sich um eine Folge von s/w Bits handelt (z.B. swws => 10012) oder um eine Binärzahl (z.B. 9 => 10012)?
Kommen in den Daten nicht nur zwei sich abwechselnde Zeichen (s, w) vor, sondern mehrere verschiedene, muss zusätzlich zur Zahl auch das Zeichen genannt werden, das wiederholt wird. Bsp.: AAABBBBBCCDDDDDDEEF wird codiert zu: A3 B5 C2 D6 E2 F1. (Aufgabe 5, Aufgabe 9)
Damit die komprimierte Datei nicht länger wird als die originale, könnte man nur Zeichen codieren, die häufiger als z.B. dreimal hintereinander auftreten.
AAABBBBBCCDDDDDDEEF ⇒ AAAB5CCD6EE
Hierbei muss aber unterschieden werden können, ob es sich um ein Einzelzeichen oder um eine Wiederholung handelt. Das kann durch ein Sonderzeichen geschehen, welches sonst nie verwendet wird. z.B. AAA#B5CC#D6EE. Falls alle Zeichen im Text vorkommen können, dann kann man ein möglichst seltenes Zeichen verwenden. Kommt es nun im Text vor, muss es dort als Wiederholung gekennzeichnet werden. Aus # wird dann ##1. Bsp.: ABBB#CDDDDE## ⇒ ABBB##1C#D3E##2
Die Lauflängencodierung kann auf verschiedenen Ebenen angewendet werden: Auf Bit-Ebene wie in Aufgabe 1 und 2, auf Zeichen-Ebene wie in Aufgabe 4 oder auch auf Pixel-Ebene wie in Aufgabe 5.
Hinweis:
Bei den Aufgaben wird nicht unterschieden, ob die Zahlen binär- oder ASCII-codiert werden. Im Allgemeinen ergibt sich das aus der Aufgabenstellung. Wenn genau dieses Thema im Unterricht vertieft werden soll, dann sollten die Aufgabenstellungen angepasst und konkretisiert werden.
Hinweis:
Die Huffman-Codierung, die sich logisch anschließen würde, ist im Bildungsplan nicht vorgesehen.
Verlustbehaftete Datenkompression
Bei der verlustbehafteten Kompression1 wird aus einer Datei Information entfernt, die später nicht wiederhergestellt werden kann. Ziel ist es nun, genau solche Information zu entfernen, die nicht notwendig ist – man spricht von Irrelevanzreduktion. Verlustbehaftete Kompression findet meist Anwendung in der Bild-, Video- und Audio-Übertragung.2
Die Entscheidung, welche Information für die Qualität des Bildes (oder auch z.B. einer Audiodatei) wesentlich ist, hängt von der menschlichen Wahrnehmung ab.
Bei Audiodateien könnten z.B. Töne, die im nicht hörbaren Bereich liegen, entfernt werden. Allerdings ist der hörbare Bereich nicht bei allen Menschen exakt gleich. Das Audio-Format MP3 liefert für einige eine völlig ausreichende Musik-Qualität, für andere ist MP3 inakzeptabel.
Die Netzhaut des menschlichen Auges kann Helligkeitsunterschiede viel stärker wahrnehmen als Farbunterschiede. Daher können Farben eher reduziert werden als Helligkeitsstufen, ohne dass ein qualitativer Unterschied bemerkt wird. Diesen Effekt macht sich bereits das Farbfernsehen mit der YUV-422 Reduzierung zunutze.
Linien und Kanten sehr wichtig für die Wahrnehmung von Objekten, so wird z.B. eine Strichzeichnung oft schneller erkannt als ein Farbbild desselben Objekts.
Weiterhin verstärkt die menschliche Bildverarbeitung Kontraste. Beim Effekt der Machschen Streifen werden an den Grenzen von einheitlich gefärbten Flächen die Kontraste viel stärker wahrgenommen als real vorhanden.3
Bildquelle: Maschsche Streifen.svg by Polini [CC BY-SA 3.0] via via Wikimedia Commons (abger. 12.3.19)
Der JPEG-Algorithmus macht sich solche Effekte (unter anderem) zunutze und erreicht eine sehr starke Reduzierung der Datenmenge, ohne deutliche Qualitätsverringerungen.
Neben der individuellen Wahrnehmung muss bei der Qualitätsentscheidung natürlich auch berücksichtigt werden, für welchen Zweck ein Bild benötigt wird (z.B. Betrachtung auf dem Handy oder auf einem großen Bildschirm; Ausdruck als Postkarte oder Poster) sowie die Qualität des Darstellungsmediums (z.B. sehr 'gutes' Foto in Verbindung mit einem 'schlechten' Beamer, Bildschirm bzw. Drucker).
Die SuS untersuchen in Aufgabe 11 das Aussehen und Datenmenge eines JPEG-Fotos, nachdem sie es in unterschiedlichen JPEG-Kompressionsgraden gespeichert haben. Wahrscheinlich sprechen die SuS von einer besseren oder schlechteren 'Qualität' des Bildes. Dann muss man thematisieren, dass zuvor definiert wurde, dass die 'Qualität' abhängig ist von der Auflösung und der Farbtiefe.
Bildquelle: M. Klein
In Aufgabe 13 kann (optional oder differenzierend) auf den Effekt der Kompressionsartefakte eingegangen werden. Das sind sichtbare Blockstrukturen (daher Blockartefakte), die durch eine Unterteilung des Bildes in (meist 8•8 Pixel) große Blöcke bei der JPEG-Kompression entstehen.
Kompressionsartefakte treten auch bei der Audio-Kompression als hörbare Störungen auf.
Ergänzung: Verlustbehaftete Audio-Kompression4
Wie bei Bildern spielt die Wahrnehmung eine große Rolle (Psychoakustik). Zum Beispiel werden Frequenzen oberhalb von ca. 20 kHz nicht wahrgenommen und können entfernt werden.
Zwei Töne werden erst dann als getrennte Töne wahrgenommen, wenn der Frequenzbereich weit genug auseinander liegt. Und ein leiser Ton ist nach einem lauten Ton zunächst nicht hörbar.
Durch solche Phänomene können die Ausgangsdaten ohne hörbaren Qualitätsverlust weiter reduziert werden. Werden Musik, Sprache oder Geräusche auf Werte um etwa 192 kbit/s reduziert, können die meisten Menschen kaum Qualitätsunterschiede zum unkomprimierten Ausgangsmaterial feststellen.
Ein Standardverfahren zur Audiokompression ist das 1982 entwickelte MP3-Verfahren. Der maßgebliche Entwickler dieses Verfahrens ist der deutsche Mathematiker und Elektrotechniker Karlheinz Brandenburg.
Bei der Qualität von Audio-Aufnahmen muss unterschieden werden zwischen der Qualität der Aufnahme und der Qualität der Wiedergabe.
1 https://de.wikipedia.org/wiki/Datenkompression(abgerufen am 02.01.2019)
2 Theoretische Grundlage bildet die Shannonsche Rate-Distortion-Theorie. Sie beschreibt, welche Datenübertragungsrate mindestens nötig ist, um Informationen mit einer bestimmten Güte zu übertragen.
3 https://de.wikipedia.org/wiki/Machsche_Streifen#/media/File:Maschsche_Streifen.svg (abgerufen am 12.3.19)
3 https://de.wikipedia.org/wiki/Datenkompression (abgerufen am 2.1.2019)
Unterrichtsgang: Herunterladen [odt][1 MB]
Unterrichtsgang: Herunterladen [pdf][824 KB]
Weiter zu Digitalisierung von Audio