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 nn Funktionen cjc_j zusammensetzt. Also konkret

Φ(x)=a0c0(x)+…+an−1cn−1(x)\Phi(x) = a_0 c_0(x) + \ldots + a_{n-1}c_{n-1}(x)

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

a=(a0⋮an−1)a = \begin{pmatrix} a_0 \\ \vdots \\ a_{n-1} \end{pmatrix}

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

Eine weitere Möglichkeit wäre die Beschreibung der Funktion anhand von nn paarweise verschiedenen Koordinatenpaaren (xi,yi)(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 cjc_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 aa gegeben, und somit die Funktion

Φ(x)=∑j=0n−1ajcj(x)\Phi(x) = \sum_{j=0}^{n-1} a_j c_j(x)

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

xi:=(i+12)πn=(2i+1)π2nx_i := (i + \frac{1}{2}) \frac{\pi}{n} = (2i + 1) \frac{\pi}{2n}

Die Funktionen cjc_j werden auch definiert, nämlich:

cj(x):=sj⋅cos⁡(j⋅x)mitsj={1nfallsj=02nsonstc_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.

Dabei nennt man sjs_j auch den Skalierungsfaktor.

Wir haben also nn paarweise verschiedene xx-Werte für die Stützstellen und nn paarweise verschiedene Kosinusfunktionen und können so eine Transformationsmatrix TT definieren:

Tij:=cj(xi)=sjcos⁡(j⋅(2i+1)π2n)T_{ij} := c_j(x_i) = s_j \cos\Big(j \cdot (2i + 1) \frac{\pi}{2n}\Big)

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

f−1(x):=T⋅af^{-1}(x) := T \cdot a

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

yi=∑j=0n−1ajcj(xi)=a0c0(xj)+…+an−1cn−1(xj)\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 xjx_j!

Die Vorwärtstransformation

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

y=Tx⇔  T−1y=T−1Tx⇔  T−1y=x\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 yy von rechts mit der inversen Transformationsmatrix gerade die Vorwärtstransformation. Also definieren wir f:Rn→Rnf: \mathbb{R}^n \to \mathbb{R}^n

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

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

T⋅T⊤=EnT \cdot T^\top = E_n

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

T−1=TjiT^{-1} = T_{ji}

Es gilt also

ai=∑j=0n−1yjci(xj)=∑j=0n−1yjsicos⁡(i⋅(2j+1)π2n)=si⋅∑j=0n−1yjcos⁡(i(2j+1)π2n)\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∈Rn×nY \in \mathbb{R}^{n \times n} eine Matrix die wir transformieren möchten, so liefert die Multiplikation

Z=T−1YZ = T^{-1} Y

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

A=(T−1Z⊤)⊤A = (T^{-1} Z^\top)^\top

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

A=(T⊤(T⊤Y)⊤)⊤=(T⊤Y)T=T⊤YT\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:Rn×n→Rn×ng: \mathbb{R}^{n \times n} \to \mathbb{R}^{n \times n} ist also

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

Die Rücktransformation g−1:Rn×n→Rn×ng^{-1}: \mathbb{R}^{n \times n} \to \mathbb{R}^{n \times n} ist damit trivial herleitbar und ist

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

Damit gilt: Die Matrix TT ist orthogonal und ihre Spaltenvektoren bilden eine Orthonormalbasis des Vektorraums Rn\mathbb{R}^n. Das heißt je zwei paarweise verschiedene Spalten von TT liegen orthogonal zueinander, und ihre Norm beträgt jeweils 11. Die Matrizen AA und YY 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 (t0=x0,…,tn−1=xn−1)(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