Datenkompression

3. November 2013 | Von | Kategorie: Datenkompression, Datenmenge

Von besonderer Bedeutung ist für das Speichern von Bilddaten das eingesetzte Datenkompressionsverfahren.
Es gibt verlustfreie Verfahren (Non-Lossy) und verlustbehaftete Verfahren (Lossy).

Werden bei Bilddaten nur alle redundanten Informationen reduziert, bzw. gelöscht, spricht man von Datenkompression (non-lossy). Darüberhinausgehende Verringerung der Informationen nennt sich Datenreduktion und bringt Verluste mit sich (lossy).

Zu den verlustfreien Komprimierungsverfahren zählen: Huffmann-Kodierung, LZW-Komprimierung, RLE-Verfahren.

Die Komprimierraten liegen je nach Struktur der Bild-/Textdaten zwischen 5 und 50 %. Detailarme Bilder lassen sich durch wiederkehrende Bildelemente besser komprimieren als detailreiche Bilder.

Zu den verlustbehafteten Verfahren zählt das JPEG-Kompressionsverfahren. Hier kann der Anwender die Qualität und die Größe des komprimierten Bildes einstellen. Entsprechend große Unterschiede gibt es bei den möglichen Kompressionsraten.

Komprimiert werden nur die Bilddaten – nicht der Header!
Dateigröße
Dateigröße = Bildgröße x Kompressionsfaktor + Header

Aufgabe: Eine Aufsichtsvorlage mit der Größe 9 cm x 13 cm wird in einem Flachbettscanner mit einer Auflösung von 300 ppi (Maßstab 1:1) und einer Datentiefe von 8 Bit/pixel je Kanal gescannt. Es soll zunächst im RGB-Modus und im Tif-Format abgespeichert werden. Beim Speichern wird das verlustfreie LZW-Verfahren angewendet. Die Kom-pressionsrate beträgt bei diesem Motiv 8 %. Der Datei-header wird nicht komprimiert und beträgt 450 Byte. a) Berechnen Sie die Größe der Bilddatei (Rohdaten/Bild-größe) in Byte nach dem Scannen. b) Welche Dateigröße in MB hat die gespeicherte TIFF (LZW)-Datei?

 

Digitale Bilder – Bitmap
Bei einem Bitmap-Bild gibt es nur die Farben Schwarz oder Weiß.
Bei Bilddateien im „bit-map“-Format erfolgt die Codierung im Prinzip so:


Dateikopf:

  • Anzahl der Farben
  • Code für jede Farbe
  • Breite des Bildes in Pixel
  • Höhe des Bildes

Dateikörper:

  • Farb-Code-Wert für jeden Pixel

Übung:
1. Wie viel Bit hat das Bild ? ________________ Bit
2. Wie sieht das Bild aus ? – Zeichnen Sie das Bitmap-Bild:

 

Lauflängenkodierung (Run-Length Encoding, kurz: RLE)

Bei einem Schwarz-Weiß-Bild mit der Auflösung 1024 x 768 Pixel ist der Dateikörper bei der bit-map-Codierung bereits 786432 Bit groß. Ist es möglich, die Größe des Dateikörpers zu verkleinern, ohne Bildinformationen zu verlieren?

Statt

0000000000000000000000000011100000000000000011100000000000000011100001 1111111111111000111111111111111001111111111111100000000000001110000000 00000011100000000000001110000000000000000000000

kann man auch schreiben:

26 mal weiß, 3 mal schwarz, 15 mal weiß, 3 mal schwarz,

15 mal weiß, 3 mal schwarz, 4 mal weiß, 14 mal schwarz,

3 mal weiß, 15 mal schwarz, 2 mal weiß, 14 mal schwarz,

13 mal weiß, 3 mal schwarz, 13 mal weiß, 3 mal schwarz,

13 mal weiß, 3 mal schwarz, 22 mal weiß.

Das erscheint noch nicht kürzer, aber nun vereinbaren wir folgenden Code:

  1. Wir bilden Code-Worte aus 4 Bit
  2. Das erste Bit legt die Farbe fest (0 für weiß, 1 für schwarz)
  3. Die folgenden 3 Bit geben an, wie viel mal diese Farbe wiederholt wird ( 000 für 1 mal, 001 für 2 mal, 010 für 3 mal usw.)

Damit erhalten wir folgende Codetabelle:

 

Übung:
3. Codiere das Bitmap-Bild mit dieser Code-Tabelle. Wie viele Bit benötigst Du dafür?

__________________ Bit

 

Lauflängenkodierung (RLE)
Übungsaufgaben zur Lauflängenkodierung
4. Skizziere ein kleines Bild, bei dem die Lauflängen-Codierung eine besonders wirksame Kompression ermöglicht. Ermittle die Kompressionsrate in Prozent.

 

______________ % Kompressionsrate

 

5. Skizziere ein kleines Bild, bei dem die Lauflängen-Codierung eine besonders schlechte Kompression ermöglicht. Ermittle die Kompressionsrate in Prozent.

 

______________ % Kompressionsrate

 

Lauflängenkodierung (RLE)

6. a) Dekodiere folgende Daten für ein Bild mit 8 Pixel Breite und 11 Pixel Höhe.
0111-0111-0001-1011-0110-1000-0110-1000-0101-1001-0100-1000-0101-1000-0110-1011-
0111-0111-0001
b) Ermittle die Kompressionsrate in Prozent.

 

______________ % Kompressionsrate

 

7. Die bisher verwendete Form der Lauflängencodierung bestand aus Codeblöcken von je vier
Bit. Entwickle eine Codetabelle für die Blocklänge von drei Bit.

8. Vergleiche den 4-Bit -Code mit dem 3-Bit-Code. Nenne Vorteile und Nachteile.

 

_________________________________________________________________
9. Ist RLE verlustbehaftet oder verlustfrei ?

 

__________________________________________________________________

Der Morse-Code
Vor über 150 Jahren hat man begonnen, Texte mittels Telegraphie zu übertragen. Dafür wurde der Morse-Code genutzt. Das Verfahren war zuverlässig und verbreitete sich sehr schnell. Erfahrene Telegraphen konnten
erstaunlich schnell „morsen“ und Morsesignale im Kopf decodieren.
Bei diesem Code haben Zeichen unterschiedliche Codelängen.

Aufgaben:
1. Welche Buchstaben haben einen besonders kurzen Morse-Code?

 

_____________________________________________________

2. Warum hat man gerade diesen Buchstaben einen kurzen Code gegeben?

 

_____________________________________________________
3. Codiere die Zeichenfolge „INFORMATIK“ mit Hilfe des Morse-Code.
(Benutze 0 für „kurz“ und 1 für „lang“)

 

_____________________________________________________
4. Decodiere die Zeichenfolge:
0000001101010001101101

 

_____________________________________________________
5. Warum trat das Problem, dass Du beim Decodieren hattest, nicht auf, wenn geübte Telegraphieren „morsten“?

 

_____________________________________________________

 

 

Die Huffman-Codierung

Am Beispiel des Morse-Codes sieht man, dass ein drittes Symbol nötig war, nämlich eine etwas längere Pause zwischen den einzelnen Buchstaben.
Aufgeschrieben könnte das so aussehen:
0000-00-11-01-0100-01-1011-01

Da jedoch 3 Symbole (0,1 und die Pausen) unpraktisch sind, haben die amerikanischen Mathematiker David A. Huffman und Claude Shannon dieses Problem untersucht und eindeutige Codes entwickelt.
Die Idee ist wiederum nicht schwer zu verstehen: Man muss der Codierung ansehen können, wo Codewörter enden.
Also darf kein Codewort so aussehen wie das „Anfangsstück“ eines anderen Codewortes.
Solche Codes werden „präfixfrei“ genannt.

Dekodiere:
a) 001000011_______________________
b) 00000101________________________
c) 01001000011______________________
d) 000101011000_____________________

 

Damit können auch Bilddateien kodiert werden. Dabei müssen die Bilddateien aber zunächst untersucht
werden, damit die Kodierung so eingerichtet werden kann, dass sie sich „lohnt“.

Aufgabe:
1. Nimm das Bild mit dem Pfeil.
Betrachte immer Paare von zwei (aufeinander folgenden) Pixeln und erstelle eine Häufigkeitstabelle.


2. Ordne nun die vier Code-Wörter möglichst geschickt den „Pixelpaaren“ zu. Wie viele Bits benötigt man, wenn man die Bilddatei so codiert? (Hinweis: Das kannst Du ausrechnen, ohne die Bilddatei zu codieren.)

 

__________________ Bit

 

Wie könnte der Pfeil mit folgender Codetabelle beschrieben werden ?

 Warum wäre es nicht sinnvoll, das folgende Bild mit der Codierung von Aufgabe 1 zu codieren ?
Welche Alternative schlägst Du vor ?


Wir sehen hier, welche Morse-Codezeichen den einzelnen Buchstaben zugeordnet sind. Um
den Code eines Zeichens zu ermitteln startet man bei der Wurzel (höchster leerer Knoten). Die
einzelnen Kreise mit den Buchstaben werden Knoten bzw. jene am Ende jedes Pfades auch
Blätter genannt, so wie bei einem richtigen Baum. Ein Pfad ist eine Folge von Knoten, quasi der
Weg von einem Knoten zu einem anderen. Folgt man also den Knoten bis zum gewünschten
Buchstaben, so erhält man den zugeordneten Morsecode.
Anstelle von ● (kurz) und ▬ (lang) schreiben wir 0 und 1

5. Welcher Code ergibt sich für den Buchstaben E?

_____________________________________________________
6. Welcher Code ergibt sich für Q?

_____________________________________________________

7. Was fällt euch dabei auf? Warum sind die Codes unterschiedlich lang?

_____________________________________________________

8. Warum sind die Buchstaben auf der Computer-Tastatur nicht alphabetisch angeordnet ?

_____________________________________________________

In den beiden Abbildungen sehen Sie verschiedene Codiermöglichkeiten der Buchstaben ABCDEF.

9. Worin liegt der Unterschied ?

_____________________________________________________

10. Erstellen Sie für beide Abbildungen die entsprechende Codetabelle:

11. Welcher Code benötigt weniger Speicher ?

 

12. Rechts sehen Sie die Häufigkeitsverteilung der Buchstaben in der deutschen Sprache.
Wie könnte man den Codebaum optimieren, um zusätzlich Daten zu komprimieren ?

 

Zeichnen Sie einen optimalen Codebaum:

 

In den beiden Abbildungen sehen Sie verschiedene Codiermöglichkeiten der Buchstaben ABCDE.

9. Worin liegt der Unterschied ?

_____________________________________________________
10. Erstellen Sie für beide Abbildungen die entsprechende Codetabelle:

 

11. Erstellen Sie einen eigenen Codebaum für den sinnfreien Satz „Schule ist schön“:

 

Verlustbehaftete Komprimierung an einem Beispiel
Verfahren, die Bilder verlustbehaftet komprimieren, verwenden im Prinzip zwei Bearbeitungsschritte:

  1. Vereinfachung der Bildinformationen
  2. Kodierung des vereinfachten Bildes.

Um ein Beispiel von Hand ausführen zu können, benutzen wir eine ganz einfache Regel zum „Vereinfachen“:
a) weiße Pixel bleiben unverändert
b) schwarze Pixel bleiben schwarz, wenn ihr linker und rechter Nachbar auch schwarz war, sonst werden sie weiß.
Aufgabe:
Bearbeite das folgende Bild nach der obigen Regel und wende danach unsere 4-Bit
Lauflängenkodierung an. Ermittle die Kompressionsrate in % im Vergleich zur Bit-Map-
Kodierung.

 

______________ % Kompressionsrate

 

wird fortgesetzt …

 

Keine Kommentare möglich.