Verlustbehaftete Komprimierung

KomprimierungDigitaler Grössenwahn

1. Juli 2001

„Der Digitale Alltag - Praxiswissen Informatik“

IEEE Student BranchUniversität Passau

Jens Oberender

jens.oberender@computer.orghttp://www.joooo.de

2

Digitale Datenreduktion

• verlustfrei– ungleichmässige Häufigkeitsverteilung– Redundante Muster– Exakte Wiederherstellung

• verlustbehaftet– Entfernen von

unsichtbaren Details– Ähnliche Reproduktion

3

Übertragung von Nachrichten

• im Jahr 1837• Buchstaben kodierte über

elektrische Leitungen• Bedeutung der Signal-Pausen

– kurz: Punkt– lang: Strich

• im Jahr 1837

... --- ...... --- ... Samuel F. B. Morse(1791–1872)

4

Morse-Alphabet

• häufige Buchstaben erhalten kurzen Code• unterschiedliche Länge

A .-B -...C -.-.D -..E .F ..-.G --.H ....I ..J .---K -.-

Morse-Code

5

Telefonnummern-Erkennung

• Ziffern werden nacheinander gewählt• unterschiedliche Länge• Wann ist die Ziffernfolge

zu einem Anschluss komplett?• greedy match⇒ Länge durch

die Ziffernfolgebestimmt

1101121183311880

11

0 2 833

80

6

Länge der Kodierungen

• Flexibel– Kodierungslänge implizit festgelegt– wird beim Einlesen erkannt

ermöglicht kürzere Darstellung• Konstant

– 8 Bit

7

Huffmann-Kodierung

• 1. SchrittNachricht wird analysiert

Häufigkeitswerte werden berechnet

I E E E P A S S A U

8

Huffmann-Kodierung (II)

• 2. SchrittGraph wird erstelltunter Verwendung der Häufigkeitstabelle

häufige Zeichen stehen nahe an der Wurzel

9

Huffmann-Kodierung (III)

• 3. SchrittNachricht wird kodiert

10

Huffmann-Komprimierung

• Erfolgsrezept– bei wenigen Symbole ⇒ Tiefe des Baumes– ungleichmässige Häufigkeitsverteilung

• einfach zu implementieren• vorherige Analyse der Daten notwendig• nur Muster der Länge 1 werden erkannt

11

Adaptive Komprimierung

• Familie von Algorithmen auf Basis von Lempel und Ziv

• Erlernen häufige Muster • Algorithmus erinnert sich

an bereits verarbeitete DatenZiv Lempel

12

LZW

EEFIAusgabe

(2,2) FEingabe

E(Abstand:3,Länge:2)

13

Lempel / Ziff / Welch

• Schnelle Algorithmen durchsuchen die Historie

• passt sich den Daten an• weitverbreitetes Verfahren• One-Pass Verfahren

14

Weiterverarbeitung

Quelle digitalisieren

DigitaleForm

elektro-chemischeAufnahme

“wahrnehmen”

menschliche Sinne:Sehen, Hören

Eindruck

Sinnesverarbeitung

Interpretation:“Gedanke”

15

Grafiken

• zweidimensionale Pixelmenge• jeder Pixel enthält eine Farbinformation• Restaurierung einer

ähnlichen Abbildung ausreichend

• lokale Redundanz

16

Vorhersage

• Vorhersage von neuen Farbwertenaus bereits gelesenen Daten

• Differenz wird abgespeichertWerte in der Nähe von Null:⇒ Darstellung in wenigen Bits

17

Farbmodelle

• Wahrnehmungs-geprägt• Drucktechnisch• Additiv

RGB

Rot/Grün/Blau

YMCK

Yellow/Magenta/Cyan/Black

YUV

Luminanz/Diff-Rot/Diff-Blau

18

Das menschliche Auge

• Sehr detailierteHelligkeits-wahrnehmung

• Gröberes Farbempfinden

19

JPEG Komprimierung

• Joint Picture Expert Group

20

Diskrete Cosinus Transformation

• Folge bestimmt eine periodische Funktion• Darstellung in

Frequenzbändern

21

Quantisierung

• Nicht alle Frequenzbereich gleich wahrnehmbar:– Ungenauigkeiten hoher

Frequenzen bleiben unbemerkt

– Bitbreite flexibel

22

Zig-Zag-Coding

• Belegte haupstächlichWerte in der rechten oberen Ecke

⇒ Null-Werte werden nicht unterbrochen

23

Artefakte an Segment-Grenzen

• Bruch zwischen den 8x8 Blöcken• Lösung: Wavelets

(verwendet in JPEG-2000)

24

Wavelets

• Progressivität• Multiskalenanalyse

Verringerung der Bild-Auflösung

25

SchrittweiseApproximation

Wavelets (II)

26

Audiokompression mit MP3

• Gezieltes Vernachlässigen von Details

• psychoakustisches Modell– verdeckte Frequenzen– zeitliche Maskierung

27

Fraktale

• Selbstähnlichkeit• Sirpinski-Dreieck• Aus wenig Information

entstehen detailierte Daten• Iterierte Funktions Systeme (IFS)

„Kopierer mit vielen Linsen“

28

Inverses Problem

• Finde ein IFS und eine Quelle, die wenig vom Zielbild abweichen

• wenn gefunden:Kompressionsrate > 1:1000

• aber: sehr schwer zu finden

29

Umbau der Daten

• Idee: vorheriges Umformen der Datenin eine gut komprimierbare Form

• Burrows-Wheeler-Transformation (BWT) Paper, Mai 1994: DEC

S B P A S S A U

30

BWT

• 1. Schritt:Für jede Positioneine Zeile mit allen folgenden Daten

31

BWT

• 2. Schritt:Sortieren durch Zeilen-Vertauschungnach lexikalischer Ordnung

32

BWT

• 3. SchrittWiederherstellung der ursprünglichen Reihenfolge: S0, S1, ..., S7

33

BWT

• Reihenfolge nur aus den Spalten restaurierbar– First-Spalte– Last-Spalte ist Prefix von F

34

BWT

• Für ein L-Feld:Suche nach dem ersten gleichen F-Feld

35

BWT

• Transformationsvektor wird restauriert aus Startposition und der L-Spalte(F-Spalte wird durch Sortieren hergestellt)

36

BWT

• Transformierten Daten enthalten mehr Redundanz

• grössere Datenmenge⇒ bessere Komprimierungsrate

37

Vorgestellte Verfahren

• Huffmann-Kodierung• LZW• JPEG• Wavelets• MP3• Fraktale Komprimierung• Burrows-Wheeler-Transformation