Upload
gertrud-kaestner
View
212
Download
0
Embed Size (px)
Citation preview
JPEGIngo Kregel
2
JPEG
Gliederung
1. Einleitung und Überblick2. Visuelle Wahrnehmung und Farbräume3. Angewandte Komprimierungsverfahren4. Die JPEG-Modi5. Ausblick
3
JPEG
Einleitung
JPEG: Joint Photographic Experts GroupZusammenschluss von Gruppen der
ISO – International Organization for Standardization ITU-T – International Telegraph and Telephone Consultative Committee
Erstes Ziel: Kompressionsverfahren für ISDN-Kanäle
4
JPEG
Einleitung
Ausschreibung eines WettbewerbsAnforderungen:
Parametrisierbarkeit der QualitätUnterstützung verschiedenster Farbräume, Bildgrößen und InhalteAnnehmbare Komplexität in Bezug auf Implementierung und AusführungSequenzielle, progressive, verlustlose und hierarchische Modi
Gewinner der Ausschreibung:Die Diskrete Kosinustransformation (DCT)
5
JPEG
Einleitung
1992: Veröffentlichung des JPEG-Standards“Information technology – Digital compression and coding of continuous-tone still images: Requirements and guidelines”ISO/IEC 10918-1 CCITT (ITU-T) Recommendation T.81
Heute:Verbreitetstes Grafikformatik der WeltVerwendung im prof. Layoutbereich, Speicherung medizinischer Daten, digitaler Videotechnik (MPEG), WWW…
6
JPEG
Ordnungsrahmen
7
JPEG
Ordnungsrahmen
8
JPEG
Gliederung
1. Einleitung und Überblick2. Visuelle Wahrnehmung und Farbräume3. Komprimierungsverfahren4. Die JPEG-Modi5. Fazit & Ausblick
9
JPEG
Visuelle Wahrnehmung des Menschen
Bildkompression auch im menschlichen GehirnBsp.: Verhältnis von Rezeptoren zu Nervenfasern im Auge 80:1
Optische Täuschungen:Illusion über Farben, geometrische Formen, Bewegungen…
Ruhende Bilder erhalten höhere Auflösung als bewegteHelligkeitsunterschiede werden stärker wahrgenommen als FarbunterschiedeForschungsfeld der Wahrnehmungspsychologie, Psychophysik
10
JPEG
Ordnungsrahmen
11
JPEG
RGB
Rot, Grün, BlauEntspricht der Technik in Farbmonitoren8 Bit: 0-255Hexadezimal: 00-ff
12
JPEG
YCbCr
Ursprung: Umstieg von S/W auf Farbfernsehen
13
JPEG
YCbCr
Y
Cb
Cr+
14
JPEG
Tiefpassfilterung
„Chroma Subsampling“Unterabtastung der ChrominanzenAusnutzung der visuellen Wahrnehmung des MenschenDatenreduktion:
4:4:4 24 Bit volle Informationsdichte4:2:2 16 Bit Halbierung der Chrominanzen (horizontal)4:2:0 12 Bit Horizontale und Vertikale Halbierung der Chrom.
15
JPEG
Gliederung
1. Einleitung und Überblick2. Visuelle Wahrnehmung und Farbräume3. Angewandte Komprimierungsverfahren4. Die JPEG-Modi5. Fazit und Ausblick
16
JPEG
Gliederung – Kapitel 3
1. Die Diskrete Kosinus-Transformation (DCT)2. Quantisierung3. Prädiktion4. Lauflängenkodierung (RLC)5. Entropiekodierung
Huffman-KodierungArithmetische Kodierung
17
JPEG
Diskrete Kosinus-Transformation
1972 Ahmed, Natarajan und Rao Weiterentwicklung der Fourier-TransformationAufgrund ihrer guten Kompressionseigenschaften in meisten verlustbehafteten Verfahren zur Bild- und Videokompression eingesetzt
Vorbereitung: Aufteilen der Grafik in 8x8-BlöckeFarbige Grafiken entsprechen mehrstufiger Verarbeitung von Graustufenbildern
18
JPEG
Diskrete Kosinus-Transformation
Berechnungsvorschriften:
7 7
0 0
2 1 2 11: ( , ) , cos cos4 16 16x y
x u y vFDCT F u v C u C v f x y
7 7
0 0
2 1 2 11: , ( , ) cos cos4 16 16u v
x u y vIDCT f x y C u C v F u v
1
, 0, 2
1
für u vC u C v
sonst
( , ) : (8 8)
( , ) : .
F u v DCT Koeffizienten x
f u v Matrix vor FDCT bzw nach IDCT
: :
: :
u Spalten v Zeilen
x Spalten y Zeilen
19
JPEG
Diskrete Kosinus-Transformation
Vollständiges Beispiel:
20
JPEG
Diskrete Kosinus-Transformation
Ausschnitt 1: Koeffizient bei (0; 0)
7 7
0 0
1( , ) ,8 x y
F u v f x y
7 7
0 0
2 1 2 11: ( , ) , cos cos4 16 16x y
x u y vFDCT F u v C u C v f x y
7 7
0 0
1 1 1( , ) , cos 0 cos 04 2 2 x y
F u v f x y
1
, 0, 2
1
für u vC u C v
sonst
( , ) : (8 8)
( , ) : .
F u v DCT Koeffizienten x
f u v Matrix vor FDCT bzw nach IDCT
: :
: :
u Spalten v Zeilen
x Spalten y Zeilen
21
JPEG
Diskrete Kosinus-Transformation
Ausschnitt 2: Koeffizient bei (1; 1)
7 7
0 0
1 2 2( , ) , cos cos4 16 16x y
x yF u v f x y
7 7
0 0
2 1 2 11: ( , ) , cos cos4 16 16x y
x u y vFDCT F u v C u C v f x y
7 7
0 0
2 1 1 2 1 11( , ) 1 1 , cos cos4 16 16x y
x yF u v f x y
1
, 0, 2
1
für u vC u C v
sonst
( , ) : (8 8)
( , ) : .
F u v DCT Koeffizienten x
f u v Matrix vor FDCT bzw nach IDCT
: :
: :
u Spalten v Zeilen
x Spalten y Zeilen
+
22
JPEG
Diskrete Kosinus-Transformation
Vollständiges Beispiel:
23
JPEG
Division der Bildwerte durch QuantisierungsmatrixAufstellen solcher Matrizen nach VersuchsreihenQuantisierungswerte unterschiedlich optimal, je nach Anwendungsgebiet und GrafikeigenschaftenGenutzte Q-Matrix wird in JPEG-Datei mit gespeichert
Quantisierung
24
JPEG
Komprimierung:
Rekonstruktion:
Quantisierung ist die Hauptursache für Qualitätsverluste der DCT-basierten Verfahren
Quantisierung
,,
,Q
F x yF x y round
Q x y
, , ,R QF x y F x y Q x y
25
JPEG
Zusammenhang:
Quantisierung
26
JPEG
Vergleich von Original- und rekonstruierten Werten:
Quantisierung
27
JPEG
Prädiktion
Unterschiedliche Behandlung der Komponenten jedes 8x8-BlocksDC – Direct CurrentAC – Alternating Current
28
JPEG
Prädiktion
DC: Speicherung Mittelwerts des gesamten 8x8-BlocksAbleitung dieses Koeffizienten aus dem VorgängerblockSpeicherung der Differenz, statt absoluten Werts
29
JPEG
Lauflängenkodierung
Effektiv für Symbolfolgen mit häufigen WiederholungenZiel: Ersetzen von Wiederholungen durch TokensEin Token besteht aus 3 Elementen:
ESC Escape-Zeichenr Lauflänge s Zu ersetzendes Symbol
Effizient daher erst ab Folge von 4 Symbolen
30
JPEG
Lauflängenkodierung
Beispiel:Symbolfolge: 15400000013 Ersetzen der Nullen durch ein Token
Escape-Zeichen hier: $Länge: 6Ersetztes Symbol: 0
Token: 154$6013
31
JPEG
Lauflängenkodierung
Anwendung in JPEG:Überführen der DCT-Matrix in eine eindimensionale Symbolfolge durch Zickzack-Abtastung
32
JPEG
Lauflängenkodierung
Günstige Eigenschaften quantisierter Matrizen:
33
JPEG
Entropiekodierung
Entropie (Informationstheorie):„Mittlere Informationsdichte“
Entropiekodierung ist verlustfrei!Optimierung des Speicherplatzes einer gegebenen SymbolfolgeReduktion der zu speichernden Symbole ist Aufgabe vorhergehender Komprimierungsmethoden
34
JPEG
Gliederung
1. Einleitung und Überblick2. Visuelle Wahrnehmung und Farbräume3. Komprimierungsverfahren4. Die JPEG-Modi
Sequenziell vs. ProgressivHierarchischBaseline-Kodierung und ErweiterungenVerlustfreie KompressionRekonstruktion
5. Fazit & Ausblick
35
JPEG
Sequenzielle Verarbeitung
Nur ein DurchlaufJeder 8x8-Block nacheinanderEs wird nur exakt der Speicher benötigt, den das Bild auch einnimmtSimple Vorgehensweise Schlanke Implementierung und geringe Ausführungszeit
36
JPEG
Progressive Verarbeitung
Unter Umständen sind andere Eigenschaften von größerem VorteilÜbertragung der Information in mehreren SchrittenErster Durchlauf: sehr grobe AuflösungVerfeinerung des Ergebnisses bei weiteren Durchläufen durch zusätzliche Koeffizienten
37
JPEG
Progressive Verarbeitung
2 Unterarten der progressiven Kodierung:Spektrale Selektion: Tieffrequente Koeffizienten werden vor höherfrequenten Koeffizienten übertragenSchrittweise Verfeinerung: Senden der oberen Bits, bevor die niedrigeren Bits das Bild vervollständigen
Vorteile dieser Verarbeitungsweise:Bei geringer Bandbreite für den EmpfangVorschaumöglichkeit Betrachter kann das Laden abbrechenGeringere Auflösung kann ggf. genügen
38
JPEG
Hierarchische Verarbeitung
Sonderform des progressiven VerfahrensAufbau der Grafik in mehreren EbenenErste Ebene erzeugt mehrfach unterabgetastetes, unscharfes BildAufwärtstasten auf weitere Ebenen Hochrechnen auf größere AuflösungWerte der Hochrechnung dienen als Prognosewerte nach dem PrädiktionsverfahrenVerfahren bei niedrigen Bitraten gut geeignet, Mehraufwand bei höheren Bitraten bis zu 33%
39
JPEG
Hierarchische Verarbeitung
Schema:
40
JPEG
Baseline-Standard & Erweiterungen
Baseline-Standard: MindestbedingungenDiskrete Kosinustransformation, ausschließlich sequenziell8 Bit pro BildpunktNur Huffman-Kodierung nutzbarMaximal 2 Tabellen für Kodierung der AC- und DC-Koeffizienten
Erweiterter Standard: Progressive und sequenzielle Speicherung möglichAuch 12 BitEntscheidung zwischen Arithmetischer Kodierung und HuffmanMaximal 4 Tabellen für Kodierung der AC- und DC-Koeffizienten
41
JPEG
Verlustfreie Kompression
Unterschiede:Wahl der Bildauflösung von 2-16 Bit Verzicht auf DCT und QuantisierungAusschließliche Nutzung der Prädiktion
42
JPEG
Verlustfreie Kompression
43
JPEG
Verlustfreie Kompression
Nicht Schwerpunkt der EntwicklungsarbeitDurchschnittlich komplexe farbige Grafiken:50% Kompression 1994 JPEG-LS-Standard: Speziell verlustfreie KodierungBessere Ergebnisse als integrierte Modi in JPEG oder JPEG2000
44
JPEG
Rekonstruktion
45
JPEG
Gliederung
1. Einleitung und Überblick2. Visuelle Wahrnehmung und Farbräume3. Angewandte Komprimierungsverfahren4. Die JPEG-Modi5. Ausblick
46
JPEG
Ausblick: JPEG2000
2000: ISO 15444, Nachfolger des JPEG-StandardsWaveletbasierte TransformationFlexibler Zugriff: Änderungen ohne RekompressionEntnahme von Ausschnitten oder geringerer Auflösung aus einer Datei möglichVerbreitung bisher aufgrund der Zufriedenheit mit JPEG geringJPEG-LS-Standard oder PNG-Format für bestimmte Grafiken effizienter