Diskrete Kosinus-Transformation (DCT) | 
|
Problem
Jeder weiß, dass die Überlagerung von Tönen wieder einen Ton ergibt. Aber ist es umgekehrt möglich, einen beliebigen Ton wieder in seine Grundschwingungen zu zerlegen? Die Antwort ist ja.
In der Praxis liegt der Ton als ein Sample, d.h. als eine Folge von Messwerten an dicht aufeinander folgenden Stellen in einem bestimmten Bereich vor (Bild 1). Gesucht sind einfache, sinusförmige Schwingungen, deren Überlagerung mit dem Ton (zumindest an den Messwerten) übereinstimmt.
| |
| Bild 1: Sample-Werte einer Schwingung | |
Mathematisch gesehen besteht ein Sample aus den Funktionswerten einer Funktion an bestimmten, vorgegebenen Stützstellen. Die Darstellung der Funktion durch ein Sample heißt Stützstellendarstellung. Gesucht ist die Darstellung der Funktion als gewichtete Summe von bestimmten, vorgegebenen Basisfunktionen. Die Gewichte, mit der die Basisfunktionen in die Summe eingehen, heißen Koeffizienten. Die entsprechende Darstellung der Funktion heißt Koeffizientendarstellung.
Die Umwandlung der Funktion von der Stützstellendarstellung in die Koeffizientendarstellung ist eine Transformation.
Statt eines Tons lassen sich auch beliebige andere Schwingungen auf diese Weise transformieren, und nicht nur Schwingungen, sondern beliebige Samples, z.B. die Grauwerte von nebeneinander liegenden Bildpunkten.
Transformationen spielen bei der Filterung und Kompression von Ton- und Bildsignalen eine bedeutende Rolle. Durch Transformation, Veränderung der Koeffizienten und anschließende Rücktransformation lässt sich das Signal gezielt filtern. Ferner lässt sich durch Verringern der Darstellungsgenauigkeit bei den Koeffizienten die Datenmenge reduzieren. Es zeigt sich, dass die hieraus resultierende Qualitätseinbuße weniger stark wahrnehmbar ist, als wenn die Darstellungsgenauigkeit direkt bei den Sample-Werten verringert würde.
Transformation
Wir definieren zunächst noch einmal genau die Begriffe Stützstellendarstellung und Koeffizientendarstellung.
Definition: Gegeben seien n verschiedene Stützstellen x0, ..., xn-1. Sei ferner f(x) eine Funktion und seien yj = f(xj) die Funktionswerte der Funktion an diesen Stützstellen (j = 0, ..., n-1).
Dann wird der Vektor [y0, ..., yn-1] als Stützstellendarstellung der Funktion f(x) bezeichnet.
Definition: Gegeben seien n Basisfunktionen c0(x), ..., cn-1(x). Sei ferner f(x) eine Funktion, die sich als gewichtete Summe dieser Basisfunktionen ausdrücken lässt:
f(x) = a0·c0(x) + ... + an-1·cn-1(x).
Dann wird der Vektor [a0, ..., an-1] als Koeffizientendarstellung der Funktion f(x) bezeichnet.
Wir betrachten nun zunächst das Problem, aus der Koeffizientendarstellung einer Funktion f(x) die Stützstellendarstellung von f(x) zu berechnen.
Die Funktion f(x) sei in Koeffizientendarstellung gegeben, d.h. als gewichtete Summe von n vorgegebenen Basisfunktionen ci(x):
f(x) = a0·c0(x) + ... + an-1·cn-1(x).
Der Funktionswert yj an einer einzelnen Stützstelle xj ergibt sich durch Einsetzen:
yj = a0·c0(xj) + ... + an-1·cn-1(xj).
In Vektorschreibweise ist dies
| yj = | [a0, ..., an-1] · |
|
Entsprechend lässt sich der Vektor der Funktionswerte an den n Stützstellen x0, ..., xn-1 durch ein Produkt mit einer Matrix, der Transformationsmatrix T, darstellen:
| [y0 ... yn-1] = | [a0 ... an-1] · |
|
Somit lässt sich also die Stützstellendarstellung der Funktion f(x) aus der Koeffizientendarstellung durch Multiplikation mit der Transformationsmatrix T gewinnen:
[y0 ... yn-1] = [a0 ... an-1] · T.
Die Transformationsmatrix T hängt nur von der Wahl der Basisfunktionen ci(x) und der Stützstellen xj ab. Werden die Stützstellen und die Basisfunktionen geeignet gewählt, so lässt sich die Matrix T invertieren.
Dann lässt sich umgekehrt die Koeffizientendarstellung aus der Stützstellendarstellung durch Multiplikation mit der inversen Transformationsmatrix T -1 gewinnen:
[y0 ... yn-1] · T -1 = [a0 ... an-1]
Bei einer invertierbaren Transformationsmatrix T lässt sich also nach Belieben zwischen Koeffizientendarstellung und Stützstellendarstellung hin- und zurücktransformieren.
Diskrete Kosinustransformation
Bei der Diskreten Kosinustransformation werden als Basisfunktionen die Kosinusfunktionen ci(x) = cos(i·x) und als Stützstellen die Werte xj = (j+1/2)·π/n verwendet (Bild 2).
In folgendem Bild 2 sind für den Fall n = 4 die Basisfunktionen cos(i·x) und die Stützstellen (j+1/2)·π/n dargestellt (i, j 
{0, ..., 3}).
| |
| Bild 2: Basisfunktionen cos(i·x) sowie Stützstellen (j+1/2)·π/n | |
Aus praktischen Gründen werden die Kosinusfunktionen ci noch mit konstanten Faktoren si skaliert, und zwar ist
s0 = 1/
n und
si = 2/n für i > 0.
Entsprechend ergibt sich die Transformationsmatrix T als
Ti,j = si · ci(xj) = si · cos(i·(j+1/2)·π/n)
für alle i, j {0, ..., n-1}.
Die Skalierung hat zur Folge, dass für die Transformationsmatrix T gilt
T -1 = T T
d.h. die Inverse von T ergibt sich einfach durch Transponieren von T.
Für n = 4 ist die Transformationsmatrix somit
| T = |  |
|  |
Die Diskrete Kosinustransformation ist definiert als Umwandlung von der Stützstellendarstellung in die Koeffizientendarstellung. Entsprechend ist der zu transformierende Vektor [y0 ... yn-1] mit T -1 = T T zu multiplizieren:
[y0 ... yn-1] · T T = [a0 ... an-1]
Die Auswertung dieser Vektor-Matrix-Multiplikation liefert für n = 8 die in der Literatur häufig genannte Formel für die Diskrete Kosinustransformation. Wenn n festliegt, werden die Werte Ti,j der Transformationsmatrix allerdings zweckmäßigerweise im voraus berechnet und gespeichert, daher wird diese Formel in dieser Form dann nicht benötigt:
aj = 
i = 0, ..., 7 yi · Tj,i
= i = 0, ..., 7 yi · sj · cos(j·(i+1/2)·π/8)
= sj · i = 0, ..., 7 yi · cos(j·(2i+1)·π/16)
mit s0 = 1/8 = 2/4 und sj = 2/8 = 1/2 für j > 0.
Zweidimensionale Diskrete Kosinustransformation
Bei Bilddaten ist statt eines Vektors [y0 ... yn-1] eine n
n-Matrix Y von Grauwerten zu transformieren. Diese zweidimensionale Transformation lässt sich auf die eindimensionale Transformation zurückführen.
Zunächst werden alle Zeilenvektoren der Matrix Y eindimensional transformiert, d.h. mit der inversen Transformationsmatrix T T multipliziert.
Dies entspricht einer Matrixmultiplikation
Y · T T = A.
Das Ergebnis A ist eine nn-Matrix, deren Zeilenvektoren die Ergebnisvektoren der eindimensionalen Transformationen sind.
Nun werden die Spaltenvektoren der Matrix A eindimensional transformiert. Realisiert wird dies, indem A transponiert und mit T T multipliziert wird. Das Ergebnis wird erneut transponiert.
Dies entspricht der Matrixmultiplikation
(AT · T T)T = T · A.
Insgesamt wird also gerechnet
B = T · Y · T T
d.h. es werden zwei Matrixmultiplikationen ausgeführt. Die Matrix B ist das Ergebnis der zweidimensionalen Diskreten Kosinustransformation der Matrix Y.
Zusammenfassung
Bei der eindimensionalen Diskreten Kosinustransformation werden die n zu transformierenden Werte als Stützstellendarstellung einer Funktion aufgefasst, wobei n Stützstellen zwischen 0 und π zugrundegelegt werden. Die Funktion wird nun von der Stützstellendarstellung in die Koeffizientendarstellung umgewandelt, d.h. die Funktion wird als gewichtete Summe von Basisfunktionen dargestellt. Die Basisfunktionen sind die Kosinusfunktionen cos(i·x). Die Transformation entspricht einer Vektor-Matrix-Multiplikation.
Die zweidimensionale Diskrete Kosinustransformation lässt sich auf den eindimensionalen Fall zurückführen. Die Transformation entspricht zwei Matrix-Multiplikationen.
Weiter mit:  |
 H.W. Lang FH Flensburg lang@fh-flensburg.de Impressum © Created: 27.02.2005 Updated: 05.10.2009 |
 |