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.1: 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.

$$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}$$

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.

$$r[u, v] := \frac{s[u,v]}{q[u,v]}$$

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.2: 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

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

Ausgangsbildmatrix

rekonstruierte Bildmatrix

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%

Kompression nach JPEG. Platzbedarf in Prozent bezogen auf tif-Datei

motel40.jpg 5%

motel20.jpg 4%

motel10.jpg 3%

motel05.jpg 2%

Kompression nach JPEG. Platzbedarf in Prozent bezogen auf tif-Datei

motel02.jpg 1.5%

motel01.jpg 1%