Diskrete Kosinus Transformation

Die diskrete Kosinustransformation (engl. Discrete Cosinus Transform, DCT) ist, ähnlich wie die Schnelle Fourier Transformation, eine sehr bedeutende Transformation in der Informatik. Sie wird häufig dazu eingesetzt um Redundanz in Bildsignalen zu reduzieren, so ist sie zum Beispiel das Kernstück der JPEG Kompression.

Vorbemerkungen

Angenommen wir haben eine Funktion $\Phi$, die sich als gewichtete Summe von $n$ Funktionen $c_j$ zusammensetzt. Also konkret

\begin{gather*} \Phi(x) = a_0 c_0(x) + \ldots + a_{n-1}c_{n-1}(x) \end{gather*}

Es gibt nun verschiedene Möglichkeiten, wie wir diese Funktion $\Phi$ beschreiben können, wenn die $c_j$ bekannt sind. Eine Möglichkeit ist beispielsweise durch Angabe der Koeffizienten $a_j$. Damit erhalten wir einen Vektor

\begin{gather*} a = \begin{pmatrix} a_0 \\ \vdots \\ a_{n-1} \end{pmatrix} \end{gather*}

der $\Phi$ eindeutig beschreibt. Diese Darstellungsform nennt man auch Koeffizientendarstellung.

Eine weitere Möglichkeit wäre die Beschreibung der Funktion anhand von $n$ paarweise verschiedenen Koordinatenpaaren $(x_i, y_i)$ durch die $\Phi$ führt. Diese Darstellungsform heißt auch Stützstellendarstellung.

Die Überführung von einer Darstellung in die andere ist gerade die Aufgabe einer Transformation. Bei der DCT werden für die Funktionen $c_j$ spezielle Kosinusfunktionen benutzt, mehr dazu im nächsten Abschnitt.

Die Inverse Diskrete Kosinunstransformation (IDCT)

Wir fangen rückwärts an, da so die Herleitung einfacher zu verstehen ist. Bei der IDCT will man von der Koeffizientendarstellung in die Stützstellendarstellung transformieren. Also wir haben den Vektor $a$ gegeben, und somit die Funktion

\begin{gather*} \Phi(x) = \sum_{j=0}^{n-1} a_j c_j(x) \end{gather*}

Offensichtlich erhält man einen Wert $y_i = \Phi(x_i)$ zu einem $x_i$ in der Stützstellendarstellung einfach durch einsetzen. Nun sucht man sich bei der DCT diese Stellen $x_i$ nicht einfach beliebig aus, sondern definiert sie:

\begin{gather*} x_i := (i + \frac{1}{2}) \frac{\pi}{n} = (2i + 1) \frac{\pi}{2n} \end{gather*}

Die Funktionen $c_j$ werden auch definiert, nämlich:

\begin{gather*} c_j(x) := s_j \cdot \cos(j \cdot x) \quad \text{mit} \quad s_j = \left\{\begin{array}{ccc} \frac{1}{\sqrt{n}} & \text{falls} & j = 0\\ \frac{\sqrt{2}}{\sqrt{n}} & \text{sonst} & \end{array}\right.\end{gather*}

Dabei nennt man $s_j$ auch den Skalierungsfaktor.

Wir haben also $n$ paarweise verschiedene $x$-Werte für die Stützstellen und $n$ paarweise verschiedene Kosinusfunktionen und können so eine Transformationsmatrix $T$ definieren:

\begin{gather*} T_{ij} := c_j(x_i) = s_j \cos\Big(j \cdot (2i + 1) \frac{\pi}{2n}\Big)\end{gather*}

Die inverse diskrete Kosinustransformation $f^{-1}: \mathbb{R}^n \to \mathbb{R}^n$ ist nun einfach definiert durch

$\displaystyle f^{-1}(x) := T \cdot a$

Dies entspricht nun gerade einer Überführung des Vektors $a$ (Koeffizientendarstellung) in einen Vektor $y := f(a)$, der die Stützstellen an den Werten $x_i$ enthält, denn wegen der ausgeschriebenen Matrix-Vektormultiplikation für eine Komponente ist

\begin{align*} y_i &= \sum_{j=0}^{n-1} a_j c_j(x_i) \\ &= a_0 c_0(x_j) + \ldots + a_{n-1} c_{n-1}(x_j) \end{align*}

gerade die Auswertung der Funktion an der Stelle $x_j$!

Die Vorwärtstransformation

Kommen wir nun zur eigentlichen DCT. Wir möchten also den Vektor $y$ wieder zurück in den Vektor $a$ überführen. Ein bisschen lineare Algebra liefert

\begin{align*} & y = T x \\ \Leftrightarrow\;& T^{-1} y = T^{-1} T x \\ \Leftrightarrow\;& T^{-1} y = x \end{align*}

Offenbar ist also die Multiplikation von $y$ von rechts mit der inversen Transformationsmatrix gerade die Vorwärtstransformation. Also definieren wir $f: \mathbb{R}^n \to \mathbb{R}^n$

$\displaystyle f(x) := T^{-1} \cdot a$

Nun gibt es jedoch noch einen schönen Trick. Man kann nämlich beweisen, dass gilt

\begin{gather*} T \cdot T^\top = E_n \end{gather*}

Damit folgt nun $T^{-1} = T^\top$, was die Berechnung der inversen Transformationsmatrix erheblich vereinfacht! Anders geschrieben ist also

\begin{gather*} T^{-1} = T_{ji} \end{gather*}

Es gilt also

\begin{align*} a_i &= \sum_{j=0}^{n-1} y_j c_i(x_j) \\ &= \sum_{j=0}^{n-1} y_j s_i \cos\Big(i \cdot (2j + 1) \frac{\pi}{2n}\Big) \\ &= s_i \cdot \sum_{j=0}^{n-1} y_j \cos\Big(\frac{i(2j+1)\pi}{2n}\Big) \end{align*}

Diese Formel findet man auch häufig in Büchern.

2D Transformation

Eingangs wurde erwähnt, dass die DCT wichtig für die Kompression von Bilddaten ist. Diese sind jedoch zweidimensional. Wir benötigen also eine DCT die nicht auf Vektoren, sondern auf Matrizen operiert! Sei nun $Y \in \mathbb{R}^{n \times n}$ eine Matrix die wir transformieren möchten, so liefert die Multiplikation

\begin{gather*} Z = T^{-1} Y \end{gather*}

die 1D Transformation jedes einzelnen Spaltenvektors von $Y$, dessen Transformierte die Spaltenvektoren in $Z$ sind. Da wir nun noch in die andere Dimension transformieren wollen, müssen wir folgende Operation durchführen:

\begin{gather*} A = (T^{-1} Z^\top)^\top \end{gather*}

Wir transponieren also das Zwischenergebnis $Z$, führen jetzt die DCT durch und transponieren das Ergebnis zurück. Anschaulich haben wir also eine 1D-DCT mit jedem Zeilenvektor in $Z$ durchgeführt. Fassen wir zusammen:

\begin{align*} A &= (T^\top (T^\top Y)^\top)^\top \\ &= (T^\top Y) T \\ &= T^\top Y T \end{align*}

Die 2D Diskrete Kosinustransformation $g: \mathbb{R}^{n \times n} \to \mathbb{R}^{n \times n}$ ist also

$\displaystyle g(Y) := T^\top \cdot Y \cdot T$

Die Rücktransformation $g^{-1}: \mathbb{R}^{n \times n} \to \mathbb{R}^{n \times n}$ ist damit trivial herleitbar und ist

$\displaystyle g^{-1}(A) := T \cdot A \cdot T^\top$

Damit gilt: Die Matrix $T$ ist orthogonal und ihre Spaltenvektoren bilden eine Orthonormalbasis des Vektorraums $\mathbb{R}^n$, das heißt je zwei paarweise verschiedene Spalten von $T$ liegen orthogonal zueinander, und ihre Norm beträgt jeweils $1$. Die Matrizen $A$ und $Y$ heißen auch orthogonal äquivalent.

Interpretation

Nochmal zur Erinnerung: Bei der Vorwärtstransformation transformieren wir Vektoren, die eine Stützstellendarstellung haben, in Vektoren die eine Koeffizientendarstellung der einzelnen Summanden der Kosinusterme haben. Fassen wir die Stützstellen als die zeitdiskreten Amplituden eines Audiosignals zu den Zeitpunkten $(t_0 = x_0, \ldots, t_{n-1} = x_{n-1})$ auf, so liefert die Transformation quasi die Stärke der Einzelfrequenzen, die durch die Kosinusterme beschrieben werden. Man zerlegt also ein Signal in seine einzelnen Frequenz-Bestandteile aus denen es zusammengesetzt ist.

Weiteres zur DCT

Website by: Thomas Pajor, Augartenstr. 56, 76137 Karlsruhe - www.darkviper.de - with help from: flowhase