prev up inhalt next

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).


Abbildung 9.6: 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 \cdot 8/4 = 12$ Bit). Die Reduktion beträgt 50 %.

Beim JPEG-Verfahren werden nun die drei Matrizen in Blöcke mit $8 \times 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 \times 8$ Ortsmatrix in eine $8 \times 8$ Frequenzmatrix transformiert.

Mit Hilfe der inversen DCT lassen sich die Originalwerte rekonstruieren.

\begin{displaymath} f[x,y] := \frac{1}{4} \sum_{u = 0}^{7} \ \ \sum_{v = 0}^{7... ...dot \pi}{16} \cdot \cos \frac{(2 y + 1) \cdot v \cdot \pi}{16} \end{displaymath}

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_{00}$ entspricht dem Anteil der Frequenz null in beiden Achsen und wird DC-Koeffizient (Gleichspannungsanteil) bezeichnet. Die übrigen Koeffizienten werden $A C$-Koeffizienten (Wechselspannungsanteil) genannt. Z.B. bezeichnet $s_{77}$ die höchste, in beiden Richtungen auftretende Frequenz.

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

0cm
  0.353553 0.353553 0.353553 0.353553 0.353553 0.353553 0.353553 0.353553
  0.490393 0.415735 0.277785 0.097545 -0.097545 -0.277785 -0.415735 -0.490393
  0.461940 0.191342 -0.191342 -0.461940 -0.461940 -0.191342 0.191342 0.461940
  0.415735 -0.097545 -0.490393 -0.277785 0.277785 0.490393 0.097545 -0.415735
  0.353553 -0.353553 -0.353553 0.353553 0.353553 -0.353553 -0.353553 0.353553
  0.277785 -0.490393 0.097545 0.415735 -0.415735 -0.097545 0.490393 -0.277785
  0.191342 -0.461940 0.461940 -0.191342 -0.191342 0.461940 -0.461940 0.191342
  0.097545 -0.277785 0.415735 -0.490393 0.490393 -0.415735 0.277785 -0.097545



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.

\begin{displaymath} r[u, v] := \left\lfloor\frac{s[u,v]}{q[u,v]}\right\rfloor \end{displaymath}

0cm to 17cm
 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
Bildmatrix

$\downarrow$

 98 95 91 89 90 95 101 106
 140 143 149 156 163 167 168 167
 146 149 154 159 159 151 137 126
 149 142 136 137 145 156 163 166
 119 117 118 125 140 157 170 176
 137 147 160 170 172 166 157 150
 166 167 164 152 132 112 99 93
 151 153 150 139 125 118 119 123
rekonstruierte Bildmatrix

$\uparrow$



to 17cm
 93 2 -8 -7 3 1 1 -2
 -38 -58 11 17 -3 5 5 -3
 -84 63 -1 -17 2 7 -4 -0
 -51 -37 -10 13 -10 5 -1 -4
 -85 -42 50 -8 18 -5 -1 1
 -63 66 -13 -1 2 -6 -2 -2
 -16 14 -37 18 -12 4 3 -3
 -53 31 -7 -10 23 -0 2 2
DCT-Koeffizienten
$\longrightarrow$
 31 0 -1 0 0 0 0 0
 -7 -8 1 1 0 0 0 0
 -12 7 0 -1 0 0 0 0
 -5 -3 0 0 0 0 0 0
 -7 -3 3 0 0 0 0 0
 -4 4 0 0 0 0 0 0
 -1 0 -1 0 0 0 0 0
 -3 1 0 0 0 0 0 0
quantisierte DCT-Koeffizienten


  3 5 7 9 11 13 15 17
  5 7 9 11 13 15 17 19
  7 9 11 13 15 17 19 21
  9 11 13 15 17 19 21 23
  11 13 15 17 19 21 23 25
  13 15 17 19 21 23 25 27
  15 17 19 21 23 25 27 29
  17 19 21 23 25 27 29 31
Quantisierungsmatrix
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:


Abbildung 9.7: Durchlaufsequenz pro Macroblock

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_{70}$ 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



Ausgangsbildmatrix

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

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



motel.tif
100%

motel80.jpg
9%



motel40.jpg
5%

motel20.jpg
4%
Kompression nach JPEG. Platzbedarf in Prozent bezogen auf tif-Datei





motel10.jpg
3%

motel05.jpg
2%


motel02.jpg
1.5%

motel01.jpg
1%
Kompression nach JPEG. Platzbedarf in Prozent bezogen auf tif-Datei

prev up inhalt next