5.5 Kompression nach JPEG

Die Joint Photographic Expert Group bildete sich aus Mitgliedern der Standardisierungsgremien CCITT (Consultative Committee for International Telephone and Telegraph) und ISO (International Standardization Organization). JPEG wurde schließlich zum Namen für den Standard selbst.

Zunächst wird das RGB-Bild in den YUV-Raum transformiert. Da das Auge für Helligkeitssprünge sensitiver ist als für Farbdifferenzen, kann man nun die Y -Matrix in der vollen Auflösung belassen und in den U, V-Matrizen jeweils 4 Pixel mitteln (4:1:1 Subsampling).

Für je 4 Originalpixel mit insgesamt 12 Bytes werden nun 4 + 1 + 1 = 6 Bytes benötigt (pro Bildpunkt also 6 · 8/4 = 12 Bit). Die Reduktion beträgt 50 %.

Werden je 16 Originalpixel bzgl. der Farbwerte gemittelt, so werden für 16 Originalpixel statt 48 Bytes nur noch 16 + 1 + 1 = 18 Bytes benötigt (pro Bildpunkt also 18 · 8/16 = 9 Bit). Die Bilddatei schrumpft auf 37.5 %.

Beim JPEG-Verfahren werden nun die drei Matrizen in Blöcke mit 8 × 8 Abtastwerten aufgeteilt. Anschließend durchlaufen die Blöcke folgende Schritte:

1.

Diskrete Cosinus Transformation

2.

Rundung der Frequenzkoeffizienten

3.

Lauflängenkodierung der quantisierten Werte

4.

Huffmancodierung der Lauflängenbeschreibung.

Um aus dem komprimierten Bild das Original zu rekonstruieren, werden die Schritte in umgekehrter Reihenfolge und inverser Funktionalität durchlaufen.

Durch die Wahl der Rundungstabelle läßt sich der Tradeoff zwischen Qualität und Kompression beliebig steuern. Ein typisches Farbbild läßt sich ohne für das Auge sichtbare Artefakte auf 10 % seiner Originalgröße reduzieren. Eine Reduktion auf 5 % verursacht oft nur leichte, kaum wahrnehmbare Verzerrungen.

DCT (Diskrete Cosinus Transformation)
Die diskrete Cosinus-Transformation ist ein Spezialfall der Fouriertransformation. Es wird ausgenutzt, daß für ``gerade'' Funktionen (d.h. f (- x) = f (x) ) der Sinus-Term mit seinem imaginären Anteil wegfällt. Ein zweidimensionaler Bildbereich läßt sich durch Spiegelung an der y -Achse künstlich gerade machen.

Hierdurch wird eine 8 × 8 Ortsmatrix in eine 8 × 8 Frequenzmatrix transformiert.

Mit Hilfe der inversen DCT lassen sich die Originalwerte rekonstruieren.

Für die Bildverarbeitung wird der Pixelwertebereich 0..255 in das symmetrische Intervall - 128..127 verschoben. Der Wertebereich von s liegt dann im Intervall - 1024.. + 1023 . Der errechnete Koeffizient s₀₀ entspricht dem Anteil der Frequenz null in beiden Achsen und wird DC-Koeffizient (Gleichspannungsanteil) bezeichnet. Die übrigen Koeffizienten werden AC -Koeffizienten (Wechselspannungsanteil) genannt. Z.B. bezeichnet s₇₇ die höchste, in beiden Richtungen auftretende Frequenz.

Die Eingangsmatrix M läßt sich auch durch T · M · T' transformieren mit Hilfe der Matrix T :

Quantisierung
Die errechnete Matrix hat von links oben nach rechts unten Werte abnehmender Größe. Da die Werte rechts unten den hohen, eher unwichtigen Frequenzen entsprechen, werden alle Einträge mit Faktoren zunehmender Größe dividiert.

Entropiekodierung
Die DC-Koeffizienten benachbarter Blöcke unterscheiden sich nur wenig und werden daher als Differenz zum Vorgängerblock übertragen.

Die AC-Koeffizienten werden zunächst in eine Zick-Zack-Sequenz umgeordnet:

Die AC-Koeffizienten längs dieses Weges bis zum letzten Eintrag ungleich Null werden als Folge von Paaren beschrieben:

Symbol 1: Länge der ununterbrochenen Folge von Nullen vor diesem Wert (Runlength) Anzahl der Bits, die zur Darstellung des Wertes erforderlich sind.

Symbol 2: der Wert selbst

Der quantisierte DCT-Koeffizient AC₇₀ aus vorigem Beispiel wird beschrieben als Tupel < (11,2), - 3 > , denn vor ihm in der Zickzacksequenz stehen 11 Nullen, sein Wert kann mit 2 Bit codiert werden, und sein Wert beträgt - 3 .

Für das Symbol 1 gibt es Häufigkeitsverteilungen, aus denen sich ein Huffman-Code konstruieren läßt. Für das Symbol 2 wählt man ein 2-er Komplement, welches berücksichtigt, daß bei angekündigten N Bits nur solche Zahlen kodiert werden müssen, für die N - 1 Bits nicht ausreichen.

Länge/Bitzahl Codierung

0/0 (EOB) 1010

0/1 00

0/2 01

0/3 100

0/4 1011

0/5 11010

0/6 1111000

0/7 11111000

0/8 1111110110

0/9 1111111110000010

0/10 1111111110000011

1/1 1100

1/2 11011

1/3 1111001

$$\vdots \vdots$$

2/1 11100

2/2 11111001

2/3 1111110111

$$\vdots \vdots$$

3/1 111010

3/2 111110111

3/3 111111110101

$$\vdots \vdots$$

11/1 1111111001

11/2 1111111111010000

$$\vdots \vdots$$

15/10 1111111111111110

Huffman Codierung
für Symbol 1

Wert Codierung

15 1111

14 1110

13 1101

12 1100

11 1011

10 1010

9 1001

8 1000

7 111

6 110

5 101

4 100

3 11

2 01

1 1

-1 0

-2 10

-3 00

-4 011

-5 010

-6 001

-7 000

-8 0111

-9 0110

-10 0101

-11 0100

-12 0011

-13 0010

-14 0001

-15 0000

Komplement-Codierung
für Symbol 2

Huffman 2-er Komplement

Symbol 1 Symbol 2 für Symbol 1 für Symbol 2

(1, 3) -7 1111001 000

(0, 4) -12 1011 0011

(0, 4) -8 1011 0111

(0, 1) -1 00 0

(1, 1) 1 1100 1

(0, 3) 7 100 111

(0, 3) -5 100 010

(0, 3) -7 100 000

(0, 2) -3 01 00

(1, 1) 1 1100 1

(3, 1) -1 111010 0

(1, 2) -3 11011 00

(0, 3) -4 100 011

(0, 1) -1 00 0

(0, 3) 4 100 100

(0, 2) 3 01 11

(11, 2) -3 1111111111010000 00

(0, 1) 1 00 1

(0, 1) -1 00 0

EOB 1010

Symbole und ihre Kodierung für die im Beispiel vorgestellten
quantisierten AC-Koeffizienten

8 x 8 Matrix vor und nach der JPG-Kompression.

Ausgangsbildmatrix

rekonstruierte Bildmatrix

motel.tif 100%

motel80.jpg 9%

motel40.jpg 5%

motel20.jpg 4%

Kompression nach dem JPEG-Verfahren. Platzbedarf in % bezogen auf tif-Datei.

motel10.jpg 3%

motel05.jpg 2%

motel02.jpg 1.5%

motel01.jpg 1%

Kompression nach dem JPEG-Verfahren. Platzbedarf in % bezogen auf tif-Datei.

95 88 87 95 88 95 95 95

143 144 151 151 153 170 183 181

153 151 162 166 162 151 126 117

143 144 133 130 143 153 159 175

123 112 116 130 143 147 162 189

133 151 162 166 170 188 166 128

160 168 166 159 135 101 93 98

154 155 153 144 126 106 118 133

Dezimaldarstellung der Bildbereich-Matrix

01011111 01011000 01010111 01011111 01011000 01011111 01011111 01011111

10001111 10010000 10010111 10010111 10011001 10101010 10110111 10110101

10011001 10010111 10100010 10100110 10100010 10010111 01111110 01110101

10001111 10010000 10000101 10000010 10001111 10011001 10011111 10101111

01111011 01110000 01110100 10000010 10001111 10010011 10100010 10111101

10000101 10010111 10100010 10100110 10101010 10111100 10100110 10000000

10100000 10101000 10100110 10011111 10000111 01100101 01011101 01100010

10011010 10011011 10011001 10010000 01111110 01101010 01110110 10000101

8-Bit-Codierung für Bildbereich-Matrix

00011111
quantisierter DC-Koeffizient

1111001000101100111011011100011001100111100010100000010011001
1110100110110010001100010010001111111111111010000000010001010
Huffman-Codierung für quantisierte AC-Koeffizienten