Sequenzieller DCT-Modus

  

Abbildung 2.20: JPEG-Kodierer im sequenziellen DCT-Modus

Quelle: [41]

  

Abbildung 2.21: JPEG-Dekodierer

Quelle: [41]

Dies ist die am weitesten verbreitete Variante. Die Vorgehensweise zur Kompression (Dekomprimierung) ist in Abbildung 2.20 (2.21) gezeigt. Die Komprimierung funktioniert wie folgt:
Das Bild wird in Blöcke von jeweils 8 x 8 Pixel aufgeteilt. Auf jedem dieser Blöcke wird eine diskrete Kosinus-Transformation (DCT) durchgeführt:

$$F_{uv} = (1/4) C(u)C(v)\sum_{i=0}^7\sum_{j=0}^{7} f(i,j)\cos((2i+1)u\pi /16) \cos((2j+1)v\pi /16)$$

mit

$$C(x) = \left\{ \begin{array}{ll} 1/\sqrt{2} & x = 0 \\ 1 & { sonst} \\ \end{array} \right.$$

Dabei ist f(i,j) der Farbwert des Pixels der Zeile i und Spalte j. F_uv ist der Wert des Pixels der Spalte u und Zeile v in der neuen, transformierten 8 x 8 Pixelmatrix.
Um die Rechengeschwindigkeit zu erhöhen, kann die Berechnung durch eine Tabelle erfolgen, in der die benötigten 64 Werte des Kosinus abgelegt sind.
Dieses Beispiel aus [10] erläutert die Funktion der DCT. Wir nehmen an eine 8 x 8 Pixelmatrix enthält nur zwei verschieden Werte 0 und X.

0	0	0	X	X	0	0	0
0	X	X	X	X	X	X	0
X	X	X	X	X	X	X	X
X	X	X	X	X	X	X	X
X	X	X	X	X	X	X	X
X	X	X	X	X	X	X	X
0	X	X	X	X	X	X	0
0	0	0	X	X	0	0	0

Wird 0 = -10 und X = 10 zugewiesen, ergibt sich für f(i,j) :

-10	-10	-10	10	10	-10	-10	-10
-10	10	10	10	10	10	10	-10
10	10	10	10	10	10	10	10
10	10	10	10	10	10	10	10
10	10	10	10	10	10	10	10
10	10	10	10	10	10	10	10
-10	10	10	10	10	10	10	-10
-10	-10	-10	10	10	-10	-10	-10

Nach der DCT und dem Runden auf ganzzahlige Werte sieht die Matrix der Koeffizienten F_uv folgendermaßen aus.

40	0	-26	0	0	0	-11	0
0	0	0	0	0	0	0	0
-45	0	-24	0	8	0	-10	0
0	0	0	0	0	0	0	0
-20	0	0	0	20	0	0	0
0	0	0	0	0	0	0	0
-3	0	10	0	18	0	4	0
0	0	0	0	0	0	0	0

Der Wert in der linken oberen Ecke ist der Gleichanteil F₀₀ der DCT. Je weiter die Werte in Richtung rechte untere Ecke liegen, desto höher ist die zugehörige Frequenz (vgl. Abbildung 2.22).
An diesem Zahlenbeispiel ist die Reduzierung der Datenmenge durch die DCT zu erkennen. Die Matrix enthält viele Nullen und die ,,Energie`` ist in der linken oberen Ecke gebündelt.
Nach der DCT werden die Bilddaten quantisiert. Jedem aus der DCT resultierenden Wert der Matrix F_uv wird ein korrespondierender Quantisierungs-Koeffizient Q_uv zugeordnet. Der quantisierte Wert Sq_uv berechnet sich dann wie folgt:

$$Sq_{uv} = abs( \frac{F_{uv}}{Q_{uv}})$$

Bei der Wahl der Quantisierungs-Koeffizienten wird eine Frequenzgewichtung benutzt, so dass die tieffrequenten Koeffizienten üblicherweise genauer quantisiert werden. Es wird dabei angenommen, dass das Auge gegenüber Fehlern bei höheren Frequenzen weniger anfällig ist.
Nach der Quantisierung werden die Werte gerundet. Durch das Runden entstehen Informationsverluste, die abhängig vom Grad der Quantisierung sind. Je weniger die Werte gerundet werden, desto mehr Speicherplatz muss für die Speicherung des Wertes verwendet werden Das führt zu einer größeren Datei.
Das folgende Beispiel für mögliche Quantisierungs-Koeffizienten Q_uv ist aus H.83 entnommen.

08	06	05	08	12	20	26	30
06	06	07	10	13	29	30	28
07	07	08	12	20	29	35	28
07	09	11	15	26	44	40	31
09	11	19	28	34	55	52	39
12	18	28	32	41	52	57	46
25	32	39	44	52	61	60	51
36	46	48	49	56	50	52	50

Die Koeffizienten Q_uv für die tieffrequenten Signale sind in der linken oberen Ecke und der höherfrequenten Signale in der rechten unteren Ecke. Je kleiner Q_uv desto genauer wird der zugehörige Wert F_uv quantisiert. Es wird also die linke obere Ecke am genausten quantisiert.

  

Abbildung 2.22: Auswertungsmuster zum Umsortieren der zweidimensionalen DCT-Koeffizienten in ein eindimensionales Feld

Quelle: [10]

Nach der DCT und der Quantisierung der 8 x 8 Pixelmatrix werden die 63 AC-Koeffizienten ( Sq₀₁ bis Sq₇₇) nach dem in Abbildung 2.22 gezeigten Schema ausgewertet. Beim DC-Koeffizienten Sq₀₀, dem Gleichanteil der DCT, wird die Differenz zum Gleichanteil des vorangegangen 8 x 8 Blockes gebildet. Diese Differenzbildung stellt die einzige Abhängigkeit zwischen den Blöcken dar, aus denen das Gesamtbild zusammengesetzt ist.
Im nächsten Schritt werden die Daten lauflängenkodiert. Wie im obigen Beispiel gezeigt, werden viele quantisierte Koeffizienten zu null. Daher werden die nicht verschwindenden Koeffizienten durch die Anzahl der ihnen vorangehenden Nullen und dem Wert des Koeffizienten selbst kodiert.
Nun folgt eine weitere Verschlüsselung durch Entropiekodierung des Datenstroms. Dies bedeutet, dass den häufig vorkommenden Werten kurze Kodeworte zugeordnet und längere für selten auftretende Werte verwendet werden. Ein Verfahren dazu ist die Huffman-Kodierung. Mit folgendem einfachen Verfahren, das [2] entnommen ist, kann ein Huffmann-Kode erzeugen werden:

1.

Ordne die Zeichen nach der Wahrscheinlichkeit ihres Auftretens.

2.

Bilde aus den beiden Zeichen mit kleinstem Gewicht (Wahrscheinlichkeit) einen Baum, dessen Kinder mit null bzw. eins markiert werden.

3.

Entferne diese beiden Zeichen aus der Liste und füge stattdessen ein neues Zeichen für den soeben konstruierten Baum hinzu. Das Gewicht dieses Zeichens ist die Summe der Gewichte der beiden Kinder.

4.

Bilde aus beiden Zeichen mit dem kleinsten Gewicht in der aktualisierten Liste einen Baum, dessen Kinder mit null bzw. eins markiert werden. Dieser Baum kann zwei andere Zeichen oder auch ein Zeichen und den soeben konstruierten Baum enthalten.

5.

Wiederhole diese Prozedur, bis ein einziger großer Baum gebildet ist.

Der JPEG-Standard stellt einen Satz von Huffman-Kodes zur Verfügung. Es kann jedoch ein beliebiger Huffman-Kode verwendet werden. Dieser muss im Header der komprimierten Bilddatei beschrieben werden.
Zusätzlich werden im Header der JPEG-Datei Informationen über die Abmessung des Bildes, die Art der Kodierung und die Quantisierungsniveaus abgelegt.