Diskrete Kosinustransformation

Die Diskrete Kosinustransformation (DCT) ist eine lineare, orthogonale Transformation, welche ähnlich der Diskreten Fouriertransformation (DFT) ein zeitdiskretes Signal vom Orts- in den Frequenzbereich transformiert. 1974 wurde sie erstmals von Ahmed, Natarajan und Ray erwähnt. Seit diesem Zeitpunkt ist sie die am weitesten verbreitete Transformation zur Redundanzreduktion von Bildsignalen.

Gründe für diese Präferenz:

Im Folgenden werden die Abkürzungen FDCT für "forward discrete cosine transform" und IDCT für "inverse discrete cosine transform" verwendet.

thumb|right|400px|2-Dimensionale FDCT und IDCT

Berechnung der zweidimensionalen (2D) FDCT

Um Korrelation in horizontaler und vertikaler Bildrichtung zu erfassen, wird die zweidimensionale Variante der FDCT benutzt. Zu diesem Zweck wird das Bild wie im Standard beschrieben in Blöcke von 8 x 8 Bildpunkten zerlegt. Die folgende Gleichung beschreibt die zweidimensionale FDCT für einen 8x8-Block eines Bildes.

F_{x,y}=\frac{C(x)\cdot C(y)}{4}\cdot\sum_{i=0}^7\sum_{j=0}^7 f_{i,j}\cos\left(\frac{(2i+1)\cdot x\cdot\pi}{16}\right)\cdot\cos\left(\frac{(2j+1)\cdot y\cdot\pi}{16}\right)

In dieser Gleichung sind fi,j die 64 Punkte (i,j) des Eingangsblocks, Fx,y sind die 64 DCT-Koeffizienten (x,y), und C(x), C(y) sind die Konstanten:

C(n)=\left\{ \begin{matrix} &\frac{1}{\sqrt2},&&n&=0\\ &1,&&n&\neq0 \end{matrix} \right.

Anschaulich ist dieser Vorgang in der ersten Abbildung dargestellt. Die FDCT repräsentiert jeden Block eines Bildausschnittes durch gewichtete Summen von 2D-Kosinusfunktionen, auch Basisfunktionen genannt. In der Abbildung rechts (fehlt wegen Copyright!) sind diese Funktionen als 8x8-Pixel-Basismuster dargestellt.

Das Muster links oben hat die niedrigste "Frequenz" und ist nur ein Einheitsblock. Von links nach rechts nimmt die Anzahl der "Zyklen" zwischen hell und dunkel in horizontaler Richtung zu. Diese "Zyklen" repräsentieren horizontal zunehmende räumliche Frequenz. Von oben nach unten nimmt hingegen die Anzahl der "Zyklen" zwischen hell und dunkel in vertikaler Richtung zu. Folglich nehmen sowohl die horizontalen als auch die vertikalen Frequenzen in diagonaler Richtung gleichzeitig zu. Zur Rekonstruktion der Bildpunkte eines Blocks werden diese 64 Basismuster mit dem jeweiligen Gewichtungsfaktor multipliziert und dann addiert. Dieser Faktor entspricht dem jeweiligen DCT-Koeffizienten Fx,y

Berechnung der zweidimensionalen (2D) IDCT

Die IDCT rekonstruiert einen Block mit Bildpunkten aus einem Datenfeld mit DCT-Koeffizienten. Als Eingang bedient sich die IDCT eines Blocks von 8 x 8 DCT-Koeffizienten Fx,y und rekonstruiert dann nach folgender Gleichung den Block aus den Bildpunkten fi,j.

f_{i,j}=\sum_{x=0}^7\sum_{y=0}^7\frac{C(x)\cdot C(y)}{4}\cdot F_{x,y}\cdot\cos\left(\frac{(2i+1)\cdot x\cdot\pi}{16}\right)\cdot\cos\left(\frac{(2j+1)\cdot y\cdot\pi}{16}\right)

Die Konstanten C(y) und C(x) sind dieselben wie für die FDCT.

thumb|right|180px|DCT-Koeffizienten Wie aus der Abbildung rechts ersichtlich kann mit relativ guter Genauigkeit aus sechs Koeffizienten das Originalbild rekonstruiert werden. Der erste Koeffizient (0,0) wird mit einer Gewichtung von 967.5 multipliziert und mit der IDCT transformiert. Dieser Koeffizient ist meist der wichtigste, denn er gibt den durchschnittlichen Grauwert oder "Schatten" des Blocks an. In diesem Fall wird der oben beschriebene Vorgang noch fünfmal für die weiteren DCT-Koeffizienten wiederholt. Da in den meisten Fällen die Gewichtung der anderen DCT-Koeffizienten, wie in diesem Beispiel, relativ niedrig ist, kann man die meisten Blöcke mit einer geringen Anzahl von DCT-Koeffizienten rekonstruieren.

Literatur

See also: Diskrete Kosinustransformation, 1974, Diskrete Fourier-Transformation, Multiply-Accumulate, Redundanz, Signalprozessor (Hardware), Transformation (Mathematik)