Transformationen

Diskrete Cosinus-Transformation (DCT)

 aufwärts

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 Grund­schwingungen 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) über­einstimmt.

Bild 1: Sample-Werte einer Schwingung
Bild 1: Sample-Werte einer Schwingung

Mathematisch gesehen besteht ein Sample aus den Funktions­werten einer Funktion an bestimmten, vorgegebenen Stützstellen. Die Darstellung der Funktion durch ein Sample heißt Stützstellen­darstellung. Gesucht ist die Darstellung der Funktion als gewichtete Summe von bestimmten, vorgegebenen Basis­funktionen. Die Gewichte, mit der die Basis­funktionen in die Summe eingehen, heißen Koeffizienten. Die ent­sprechende Darstellung der Funktion heißt Koeffizientendarstellung.

Die Umwandlung der Funktion von der Stützstellen­darstellung in die Koeffizientendarstellung ist eine Trans­formation.

Statt eines Tons lassen sich auch beliebige andere Schwingungen auf diese Weise trans­formieren, und nicht nur Schwingungen, sondern beliebige Samples, z.B. die Grauwerte von neben­einander liegenden Bildpunkten.

Trans­formationen spielen bei der Filterung und Kompression von Ton- und Bildsignalen eine bedeutende Rolle. Durch Trans­formation, Veränderung der Koeffizienten und anschließende Rück­trans­formation lässt sich das Signal gezielt filtern. Ferner lässt sich durch Verringern der Dar­stellungsgenauigkeit bei den Koeffizienten die Datenmenge reduzieren. Es zeigt sich, dass die hieraus resultierende Qualitäts­einbuße weniger stark wahrnehmbar ist, als wenn die Dar­stellungsgenauigkeit direkt bei den Sample-Werten verringert würde.

Transformation

Wir definieren zunächst noch einmal genau die Begriffe Stützstellen­darstellung und Koeffizientendarstellung.

Definition:  Gegeben seien n verschiedene Stützstellen x0, ..., xn-1. Sei ferner f(x) eine Funktion und seien yj = f(xj) die Funktions­werte der Funktion an diesen Stützstellen (j = 0, ..., n-1).

Dann wird der Vektor [y0, ..., yn-1] als Stützstellen­darstellung der Funktion f(x) bezeichnet.

Definition:  Gegeben seien n Basis­funktionen c0(x), ..., cn-1(x). Sei ferner f(x) eine Funktion, die sich als gewichtete Summe dieser Basis­funktionen 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ützstellen­darstellung von f(x) zu berechnen.

Die Funktion f(x) sei in Koeffizientendarstellung gegeben, d.h. als gewichtete Summe von n vorgegebenen Basis­funktionen ci(x):

f(x)  =  a0·c0(x) + ... + an-1·cn-1(x).

Der Funktions­wert yj an einer einzelnen Stützstelle xj ergibt sich durch Einsetzen:

yj  =  a0·c0(xj) + ... + an-1·cn-1(xj).

In Vektor­schreibweise ist dies

yj   =  [a0, ..., an-1] ·
eckige Klammer auf
c0(xj)
 drei Punkte übereinander 
cn-1(xj)
eckige Klammer zu

Entsprechend lässt sich der Vektor der Funktions­werte an den n Stützstellen x0, ..., xn-1 durch ein Produkt mit einer Matrix, der Trans­formationsmatrix T, darstellen:

[y0 ... yn-1]   =  [a0 ... an-1] ·
eckige Klammer auf
c0(x0)   . . .   c0(xn-1)
 drei Punkte übereinander 
cn-1(x0) . . . cn-1(xn-1)
eckige Klammer zu

Somit lässt sich also die Stützstellen­darstellung der Funktion f(x) aus der Koeffizientendarstellung durch Multi­plikation mit der Trans­formationsmatrix T gewinnen:

[y0 ... yn-1]   =   [a0 ... an-1] · T.

Die Trans­formationsmatrix T hängt nur von der Wahl der Basis­funktionen ci(x) und der Stützstellen xj ab. Werden die Stützstellen und die Basis­funktionen geeignet gewählt, so lässt sich die Matrix T invertieren.

Dann lässt sich umgekehrt die Koeffizientendarstellung aus der Stützstellen­darstellung durch Multi­plikation mit der inversen Trans­formationsmatrix T -1 gewinnen:

[y0 ... yn-1] · T -1   =   [a0 ... an-1]

Bei einer invertier­baren Trans­formationsmatrix T lässt sich also nach Belieben zwischen Koeffizientendarstellung und Stützstellen­darstellung hin- und zurück­trans­formieren.

Diskrete Cosinustransformation

Bei der Diskreten Cosinus­transformation werden als Basis­funktionen die Cosinus­funktionen 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 Basis­funktionen cos(i·x) und die Stützstellen (j+1/2)·π/n dargestellt (i, j Element {0, ..., 3}).

Basisfunktionen cos(ix)
Bild 2: Basisfunktionen cos(i·x) sowie Stützstellen (j+1/2)·π/n

Aus praktischen Gründen werden die Cosinus­funktionen ci noch mit konstanten Faktoren si skaliert, und zwar ist

s0  =  1/Wurzeln   und
si  =  Wurzel2/Wurzeln   für  i > 0.

Entsprechend ergibt sich die Trans­formationsmatrix T als

Ti,j   =   si · ci(xj)   =   si · cos(i·(j+1/2)·π/n)

für alle i, j Element {0, ..., n-1}.

Die Skalierung hat zur Folge, dass für die Trans­formationsmatrix T gilt

T -1  =  T T

d.h. die Inverse von T ergibt sich einfach durch Trans­ponieren von T.

Für n = 4 ist die Trans­formationsmatrix somit

T   =    eckige Klammer auf
0,50,50,50,5
0,6530,271-0,271-0,653
0,5-0,5-0,50,5
0,271-0,6530,653-0,271
eckige Klammer zu

Die Diskrete Cosinus­transformation ist definiert als Umwandlung von der Stützstellen­darstellung in die Koeffizientendarstellung. Entsprechend ist der zu trans­formierende Vektor [y0 ... yn-1] mit T -1  =  T T zu multi­plizieren:

[y0 ... yn-1] · T T   =   [a0 ... an-1]

 

Die Auswertung dieser Vektor-Matrix-Multi­plikation liefert für n = 8 die in der Literatur häufig genannte Formel für die Diskrete Cosinus­transformation. Wenn n festliegt, werden die Werte Ti,j der Trans­formationsmatrix allerdings zweck­mäßiger­weise im voraus berechnet und gespeichert, daher wird diese Formel in dieser Form dann nicht benötigt:

aj   =    Summe i = 0, ..., 7  yi · Tj,i

      =    Summe i = 0, ..., 7  yi · sj · cos(j·(i+1/2)·π/8)

      =    sj ·  Summe i = 0, ..., 7  yi · cos(j·(2i+1)·π/16)

mit  s0 = 1/Wurzel8 = Wurzel2/4  und  sj = Wurzel2/Wurzel8 = 1/2  für j > 0.

Zweidimensionale Diskrete Cosinustransformation

Bei Bilddaten ist statt eines Vektors [y0 ... yn-1] eine n × n-Matrix Y von Grauwerten zu trans­formieren. Diese zwei­dimensionale Trans­formation lässt sich auf die ein­dimensionale Trans­formation zurückführen.

Zunächst werden alle Zeilen­vektoren der Matrix Y ein­dimensional trans­formiert, d.h. mit der inversen Trans­formationsmatrix T T multi­pliziert.

Dies entspricht einer Matrix­multiplikation

Y · T T   =   A.

Das Ergebnis A ist eine n × n-Matrix, deren Zeilen­vektoren die Ergebnis­vektoren der ein­dimensionalen Trans­formationen sind.

Nun werden die Spalten­vektoren der Matrix A ein­dimensional trans­formiert. Realisiert wird dies, indem A transponiert und mit T T multi­pliziert wird. Das Ergebnis wird erneut transponiert.

Dies entspricht der Matrix­multiplikation

(AT · T T)T   =   T · A.

Insgesamt wird also gerechnet

B   =   T · Y · T T

d.h. es werden zwei Matrix­multiplikationen ausgeführt. Die Matrix B ist das Ergebnis der zwei­dimensionalen Diskreten Cosinus­transformation der Matrix Y.

Zusammenfassung

Bei der ein­dimensionalen Diskreten Cosinus­transformation werden die n zu trans­formierenden Werte als Stützstellen­darstellung einer Funktion aufgefasst, wobei n Stützstellen zwischen 0 und π zugrunde gelegt werden. Die Funktion wird nun von der Stützstellen­darstellung in die Koeffizientendarstellung umgewandelt, d.h. die Funktion wird als gewichtete Summe von Basis­funktionen dargestellt. Die Basis­funktionen sind die Cosinus­funktionen cos(i·x). Die Trans­formation entspricht einer Vektor-Matrix-Multi­plikation.

Die zwei­dimensionale Diskrete Cosinus­transformation lässt sich auf den ein­dimensionalen Fall zurückführen. Die Trans­formation entspricht zwei Matrix-Multi­plikationen.

Literatur

[MH 04]B. Meffert, O. Hochmuth: Werkzeuge der Signalverarbeitung. Pearson Studium (2004)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Die diskrete Cosinus-Transformation (DCT) finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit: up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 27.02.2005   Updated: 04.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik