Vorlesung Informatik 1 - Teil B: Theorie
2.7 Diskrete Cosinustransformation
Die DCT ist eine Verfahren, das sowohl im Bild- als auch in modifizierter Form im Tonbereich bei der Kompression von Daten verwendet wird.
Sie ist eine Sonderform der Fourier-Transformation (FT). Jean Fourier hat 1822 erkannt, das ein beliebiges periodisches Signal als Summe von Sinus- und Cosinus Funktionen dargestellt werden kann. Die Koeffizienten dieser Funktionen bilden das Fourier-Spektrum einer Funktion.
Die Fourier-Transformation wandelt eine Funktion vom Zeit- in den Frequenzraum und umgekehrt. Die Wandlung in den Frequenzraum wird als Fourier-Analyse, die in den Zeitbereich als Fourier-Synthese bezeichnet. Am besten kann man sich das bei Audio-Signalen vorstellen, ein anschauliches Beispiel ist https://www.falstad.com/fourier/ . Sie werden die Fourier-Transformation im zweiten Semester Mathematik kennen lernen.
Die Diskrete Cosinustransformation ist eine spezielle Form (ganzzahlige Werte, nur Cosinus-Terme).
Bei der Bildverarbeitung wird die DCT auf ein Pixel-Raster angewendet, z.B. eine 4*4 Pixel Ausschnitt eines Bildes (Grau- oder Farbwerte):
| 8 | 7 | 6 | 6 |
|---|---|---|---|
| 7 | 5 | 5 | 6 |
| 4 | 5 | 5 | 5 |
| 4 | 5 | 5 | 4 |
Transformieren wir dieses Raster mittels der DCT, dann ensteht wieder eine 4*4 Matrix, allerdings sind darin keine ganzen Zahlen mehr:
| 20,75 | 0,79 | 9,25 | -0,05 |
|---|---|---|---|
| 3,48 | 1,38 | 1,52 | 0,073 |
| 0,75 | 0,79 | -0,75 | -0,05 |
| -0,09 | -0,54 | -0,9 | -0,38 |
Dieser Algorithmus verkleinert die Datenmenge nicht, sondern er wandelt sie nur um. Dabei handelt es sich um eine Transformation in einen Frequenzraum, allerdings in Ortsfrequenzen:
- tiefe Ortsfrequenzen entsprechen großen Strukturen, also geringen Unterschieden zwischen benachbarten Pixeln,
- hohe Ortsfrequenzen kommen bei feinen Strukuren vor, also z.B. scharfen Kanten, bei einem Übergang zwischen Hell und Dunkel.
In der DCT Matrix entsprechen Werte im oberen linken Bereich der Matrix groben Strukturen (tiefe Ortsfrequenzen),
Werte im unteren rechten Bereich feinen Strukturen (hohe Ortsfrequenzen).
Beispiel:
der Bildausschnitt
| 8 | 8 | 8 | 8 |
|---|---|---|---|
| 8 | 8 | 8 | 8 |
| 8 | 8 | 8 | 8 |
| 8 | 8 | 8 | 8 |
| 40 | 0 | 0 | 0 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
Die DCT ist eine wichtige Zwischenstufe in vielen Kompressionverfahren, denn man kann in der Regel den rechten unteren Bereich der Matrix, der feinen Strukturen entspricht, weglassen oder nur grob quantisieren, ohne dass das Auge es wahrnimmt.
Wenn wir die Werte eine n*n großen Bild-Rasters mit f(x,y) und die Koeffizienten der DCT Matrix mit F(u,v) bezeichnen, gilt folgende Formel für die Berechnung eines DCT Wertes:
F(u,v) = 2/n k(u) k(v) Σ Σ f(x,y) cos (u π (2x+1)/2n) cos(v π (2y+1)/2n)
Wobei ku und kv Korrekturwerte für denn Rand sind:
k=1sqrt(2) für u,v=0 und k=1 für u,v != 0
\)
Für die Rücktransformation gibt es eine ähnliche Formel
Bis auf numerische Ungenauigkeiten ist die DCT reversibel, verlustfrei und symmetrisch. Der Rechenaufwand steigt quadratisch mit der Anzahl Pixel, weshalb im JPEG Verfahren auch nur Blöcke der Größe 8*8 bearbeitet werden.
Die DCT erfolgt z.B. am Anfang des JPEG-Algorithmus, dann werden die Werte der DCT Matrix mäanderförmig entlang der Hauptdiagonale ausgelesen, so dass sie nach zunehmender Ortsfrequenz sortiert sind. Die letzten Werte, die zu hohen Ortsfrequenzen gehören, kann man dann entweder weglassen oder mit wenig Bits quantisieren.