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