Embed Size (px)
Citation preview
KomprimierungDigitaler Grössenwahn
1. Juli 2001
„Der Digitale Alltag - Praxiswissen Informatik“
IEEE Student BranchUniversität Passau
Jens Oberender
[email protected]://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
