Die DCT ist ein Schritt innerhalb des »Baseline Codec«, ein standardisiertes Kompressionsverfahren des JPEG-Standards.
Diesen Artikel habe ich zusammen mit Jens Becker verfasst. Jens Becker ist Java-Programmierer und Experte für serverseitige Programmierung mit PHP und MySQL.
Unbearbeitete Grafiken sind oftmals zu groß, um sie im World Wide Web zu veröffentlichen oder in größerer Zahl auf einem begrenzten Datenträger wie zum Beispiel einer Diskette speichern zu können. Um die Datengröße zu verringern, werden Grafiken komprimiert. Die Grundidee aller Kompressionsverfahren ist immer dieselbe: Man sucht nach redundanten Informationen, wie zum Beispiel Ähnlichkeiten oder sich wiederholende Muster, die dann herausgerechnet werden, möglichst ohne die Bildqualität zu verringern. Es wird zwischen informationserhaltenden Verfahren und verlustbehafteten Verfahren unterschieden. Das Grafikformat JPEG zum Beispiel bietet ein standardisiertes verlustbehaftetes Kompressionsverfahren, den sogenannten Baseline Codec, der im wesentlichen aus 5 Schritten besteht:
- Konvertierung in den YCbCr- Farbraum
- Farb-Subsampling
- Diskrete Cosinus Transformation (DCT)
- Quantisieren der DCT-Koeffizienten
- Kodieren der Koeffizienten
Die einzelnen Schritte werden im folgenden kurz dargestellt.
Konvertierung
Das YCbCr-Modell ist ein Helligkeit-Farbigkeit-Modell. Ein Farbwert wird durch eine Grundhelligkeit (Y) und dessen Abweichung von Grau in Richtung Blau (Cb) und Rot (Cr) bestimmt. Die meiste Information liegt in der Grundhelligkeit, sodass man nur noch die Abweichungen nach Rot und Blau darzustellen braucht.
Farb-Subsampling
Das Auge kann feine Unterschiede nebeneinander liegender Werte Cb bzw. Cr nur sehr schlecht wahrnehmen. Daher werden die Farbwerte für Bereiche von üblicherweise 2 x 2 Pixeln gemittelt, sodass nicht der Farbwert jedes Punktes kodiert zu werden braucht.
DCT
Eine Grafik wird bei der Komprimierung mit Blöcken zu je acht mal acht Pixeln gerastert. Ein solcher Block wird nun als Vektor, bestehend aus 64 Pixelwerten (den Koeffizienten) eines geeigneten Vektorraums interpretiert. Jeder Block wird mittels der Diskreten Cosinus Transformation nach folgenden Formeln bearbeitet (ohne die Formeln jetzt näher erläutern zu wollen):
- Forward DCT:
-
- Inverse DCT:
-
Dabei werden die 64 Pixelwerte in 64 Frequenzbereiche Svu (mit v, u {0 … 7}) umgesetzt, die somit eine zweidimensionale Frequenz wiedergeben. S00 wird als DC-Koeffizient bezeichnet und entspricht dem Frequenzanteil 0 in beiden Achsen. Er bestimmt den Grundfarbton für die gesamte Dateneinheit. Die übrigen Svu werden AC-Koeffizienten genannt.
Große regelmäßige Flächen im Bild schlagen sich in niedrigen Frequenzanteilen nieder, feine Details und genaue Auflösung von Farbunterschieden in hohen. Die DCT nutzt die Schwächen des menschlichen Auges und filtert die hohen Ortsfrequenzen heraus, die das Auge ohnehin nicht wahrnehmen kann. Da sich benachbarte Pixelwerte in der Regel kaum unterscheiden, werden nach der DCT nur der DC-Koeffizient und einige niederfrequente AC-Koeffizienten größere Werte annehmen. Die anderen Koeffizienten werden fast Null oder meistens sogar gleich Null sein. Es müssen daraufhin also nur kleine Zahlen kodiert werden, was bei geeigneter Darstellung bereits einen Komprimierungeffekt hat.
Quantisierung
Auf die DCT folgt die Quantisierung. Die DCT-Koeffizienten werden durch einen Quantisierungsfaktor geteilt und auf den nächsten Integerwert gerundet. Der DC-Koeffizient, der den Farbmittelwert des Blocks (und damit die Hauptinformation) enthält, wird nicht dividiert. Die Umkehrabbildung multipliziert den quantisierten Wert später einfach wieder mit dem Quantisierungsfaktor. Durch die dabei entstehenden Rundungsfehler gehen Informationen verloren. Bei JPEG kann man den Grad der Kompression wählen, dabei wird einfach nur der Quantisierungsfaktor entsprechend skaliert. Eine Kompression von kleiner 1/10 ist ohne großen Informationsverlust möglich, zu starke Komprimierung führt allerdings zu Artefakten, das bedeutet, dass die Blockstruktur des Gesamtbildes sichbar wird. Das Bild wirkt "pixelig".
Kodierung
Die abschließende Kodierung erzeugt arbeitet die 64 Werte in einer Zick-Zack-Kurve ab und erzeugt so einen Bitstrom von 64 Integer-Werten. Der erste Wert ist der DC-Koeffizient, allerdings wird nur die Differenz zum DC-Koeffizienten im vorhergehenden Block kodiert. Dadurch und durch die Abarbeitung hin zu den höheren Frequenzen entstehen erneut kleinere Zahlen.
Die vorgestellten Verfahren beihalten noch keine direkte Kompression der Bilddaten, diese werden aber entsprechend (grob) transformiert und aufbereitet. Um die so erhaltenen Daten schließlich in einem möglichst kompakten Code abzuspeichern, stellt der JPEG-Standard mehrere Verfahren bereit, auf die hier jedoch nicht weiter eingegangen wird:
- Darstellung von variable-length-integers anstatt Integers fester Länge
- Komprimierung durch Huffman-Algorithmus
- Arithmetisches Codieren