Diskrete Kosinustransformation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die diskrete Kosinustransformation (englisch discrete cosine transformation, DCT) ist eine Transformation der numerischen Mathematik. Sie wird z. B. bei der verlustbehafteten Kompression von Audio- und Bilddaten verwendet. Bei Bilddaten wird sie beispielsweise beim Dateiformat JPEG verwendet, im Bereich der Audiodatenkompression findet eine modifizierte diskrete Kosinustransformation (MDCT) Anwendung, beispielsweise im Rahmen des MP3-Formats. Die Diskrete Kosinustransformation wurde 1974 von N. Ahmed et al. erstmals beschrieben.[1]

Zusammenhang[Bearbeiten]

Die diskrete Kosinustransformation zählt zu den reellwertigen, diskreten, linearen, orthogonalen Transformationen, die ähnlich der diskreten Fouriertransformation (DFT) ein zeitdiskretes Signal von dem Zeitbereich (bei Zeitsignalen) bzw. dem Ortsbereich (bei räumlichen Signalen) in den Frequenzbereich transformiert.

Audio- und Videosignale weisen typischerweise im unteren Spektralbereich hohe Signalenergien auf, zu deren Dekorrelation sich die DCT besonders gut eignet und die verbreitete Verwendung dieser Transformation erklärt. Weitere untergeordnete Anwendungen liegen bei der Lösung von partiellen Differentialgleichungen mittels spektraler Lösungsmethoden. Die DCT besitzt im Rahmen der Tschebyschow-Approximation mathematischen Bezug zu den Tschebyschow-Polynomen. Sie ist weiterhin eng verwandt mit der diskreten Sinustransformation (DST).

Beschreibung[Bearbeiten]

Wie andere diskrete Frequenztransformationen drückt auch die diskrete Kosinustransformation eine endliche Eingangssignalfolge als eine endliche Summe von gewichteten trigonometrischen Funktionen mit unterschiedlichen Frequenzen aus. Bei der Kosinustransformation finden nur Kosinusfunktionen Anwendung.

Die diskrete Fouriertransformation, welche über eine endliche Eingangsfolge definiert ist, besitzt implizit durch die Art der Transformation und deren Randbedingungen auch eine Festlegung, wie die Eingangsdatenfolge außerhalb dieser endlichen Folge fortgesetzt wird. Im Fall der diskreten Fouriertransformation ist dies eine periodische Fortsetzung, im Fall der diskreten Kosinustransformation ist dies eine gerade Fortsetzung der erzeugenden Signalfolge.

Bei der Art der Fortsetzung der Eingangsdatenfolge und deren Unterscheidung in gerade und ungerade Fortsetzung ergeben sich unterschiedliche Kombinationen. Es bestehen zwei Randbereiche der Eingangsfolge (Anfang und Ende der Folge), welche jeweils gerade oder ungerade fortgesetzt werden können. Daraus ergeben sich vier verschiedene Möglichkeiten. Weiter ist festzulegen, ab welcher Position in der Folge die Fortsetzung zu erfolgen hat. Dabei kann die Fortsetzung genau am Wert erfolgen oder zwischen zwei Werten. Falls die Fortsetzung zwischen zwei Werten liegt, wird der erste bzw. letzte Wert der Folge dupliziert. Diese Festlegung erfolgt getrennt nach Anfang und Ende der Folge, womit sich wieder vier verschiedene Kombinationen ergeben. So ergeben sich 4\cdot4=16 verschiedene Formen der Fortsetzung bzw. mögliche Formen der Randwerte.

Darstellung der impliziten Fortsetzung am Beispiel einer Eingangsdatenfolge mit 11 Werten (in rot) und deren Möglichkeiten zur geraden bzw. ungeraden Fortsetzungen im Rahmen der vier üblichen DCT-Varianten (DCT Typ I bis IV)

Die acht Randwertbedingungen bei der Fortsetzung, die am Anfang einer Folge eine gerade Fortsetzung aufweisen, werden zu der diskreten Kosinustransformation gezählt, die restlichen acht Formen mit einer ungeraden Fortsetzung am Anfang der Folge ergeben die diskrete Sinustransformation (DST). Die verschiedenen Formen werden in der Literatur als DCT-I bis DCT-VIII und DST-I bis DST-VIII bezeichnet. Die vier im Bereich der Datenkompression wesentlichen Varianten DCT-I bis DCT-IV und deren Fortsetzungen sind in nebenstehender Abbildung dargestellt. Die anderen vier Varianten der DCT und alle 8 Varianten der DST besitzen im Bereich der Datenkompression keine Bedeutung.

Diese unterschiedlich fortgesetzten Folgen bestimmen wesentlich die Eigenschaft der einzelnen Transformationen und deren praktische Bedeutung. Bei der Lösung von partiellen Differentialgleichungen mittels Spektraltransformation werden dabei je nach Problemstellung alle Varianten der DCT bzw. DST eingesetzt. Im Bereich der verlustbehafteten Datenreduktion von Bildsignalen wie bei JPEG findet die DCT-II in einer zweidimensionalen Transformation Anwendung, weshalb umgangssprachlich unter der „DCT“ oder der FDCT für forward discrete cosine transform der Typ DCT-II verstanden wird. Die Umkehrung der DCT-II ist aus Symmetriegründen und bis auf einen konstanten Faktor die DCT-III, auch als IDCT für inverse discrete cosine transform (dt. inverse diskrete Kosinustransformation) bezeichnet. Im Bereich der verlustbehafteten Audiosignalkompression, wie dem Dateiformat MP3, muss ein fortlaufender diskreter Audiodatenstrom transformiert werden, wobei zur Vermeidung von Alias-Effekten im Zeitbereich die MDCT, die auf einer eindimensionalen DCT-IV basiert, eingesetzt wird.

Im Bereich der Bild- bzw. Audiokompression bestimmt die Art der Fortsetzung und somit die Randwerte, wie gut sich die Transformation für die Datenkompression eignet. Der Grund dafür ist, dass Sprünge in der Signalfolge zu hohen Koeffizientenwerten in allen Frequenzbändern und damit insbesondere zu hochfrequenten spektralen Anteilen führen. Dies gilt auch, wenn diese Sprünge an den Rändern der Signalfolge infolge einer ungünstigen Fortsetzung auftreten.

Die diskrete Fouriertransformation ist im Allgemeinen eine komplexwertige Transformation und durch die periodische Fortsetzung können an den Randstellen Sprünge im Signalverlauf auftreten. Dies gilt auch für die diskrete Sinustransformation, die am Anfang der Folge eine ungerade Fortsetzung aufweist.

Im Gegensatz zur diskreten Fourier-Transformation sind alle Formen der DCT reelle Transformationen und liefern reelle Koeffizienten.

  • Die DCT transformiert, aufgrund der Wahl der Art der Fortsetzung an den Rändern, Signale (z. B. Bild- oder Audiosignale) in ihre spektralen Komponenten.
  • Die DCT kann sowohl in Software als auch in Hardware effizient implementiert werden. Es existieren ähnliche Implementierungen wie bei der schnellen Fourier-Transformation (FFT). Unter Verwendung von Signalprozessoren und deren Multiply-Accumulate-Befehlen (MAC) lässt sich die DCT-Berechnung effizient realisieren.

Definition[Bearbeiten]

Die verschiedenen Arten der DCT bilden jeweils die reellwertige Eingabefolge (Orts- bzw. Zeitbereich) mit N Elementen x[n] auf eine reellwertige Ausgabefolge (Spektralbereich) X[n] ab:

x[n]=x_0, \ldots, x_{N-1} \Rightarrow X[n]=X_0, \ldots, X_{N-1}

DCT-I[Bearbeiten]

Die DCT-I ist bezüglich ihrer Randwerte gerade am Anfang um x0 und gerade am Ende um xN-1.

X_k = \frac{1}{2} (x_0 + (-1)^k x_{N-1}) + \sum_{n=1}^{N-2} x_n \cos \left[\frac{\pi}{N-1} n k \right] \quad \quad k = 0, \dots, N-1

Die DCT-I entspricht, bis auf einen Faktor von 2, der DFT einer reellen Folge der Länge 2N−2 mit gerader Symmetrie. Beispielsweise ist die DCT-I einer N=5 Zahlen langen Folge abcde bis auf den Faktor 2 identisch zu der DFT der Folge abcdedcb. Die DCT-I ist nur für Folgen mit minimaler Länge von 2 definiert, für alle anderen DCT-Varianten muss N ganzzahlig positiv sein.

DCT-II[Bearbeiten]

Die DCT-II ist die übliche DCT. Sie ist bezüglich ihrer Randwerte gerade am Anfang um x−1/2 und gerade am Ende um xN−1/2.

X_k = \sum_{n=0}^{N-1} x_n \cos \left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) k \right] \quad \quad k = 0, \dots, N-1

Die DCT-II entspricht bis auf den konstanten Faktor 2 der DFT einer reellen Folge von 4N Elementen mit gerader Symmetrie, wobei alle Elemente mit geradem Index den Wert 0 aufweisen.

DCT-III[Bearbeiten]

Die DCT-III ist die Umkehrung der DCT-II. Sie ist bezüglich ihrer Randwerte gerade am Anfang um x0 und ungerade am Ende um xN. Die Ausgabefolge ist gerade am Anfang um X−1/2 und gerade am Ende um XN−1/2.

X_k = \frac{1}{2} x_0 + \sum_{n=1}^{N-1} x_n \cos \left[\frac{\pi}{N} n \left(k+\frac{1}{2}\right) \right] \quad \quad k = 0, \dots, N-1

DCT-IV[Bearbeiten]

Die DCT-IV ist bezüglich ihrer Randwerte gerade am Anfang um x−1/2 und ungerade am Ende um xN−1/2.

X_k = \sum_{n=0}^{N-1} x_n \cos \left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) \left(k+\frac{1}{2}\right) \right] \quad \quad k = 0, \dots, N-1.

Eine Variante der DCT-IV ist die modifizierte diskrete Kosinustransformation (MDCT), wobei dabei die Datenfolgen der einzelnen Datenblöcke ähnlich wie bei dem Overlap-Add-Verfahren überlappt werden um eine aperiodischen Verlauf zu erhalten.

Umkehrung[Bearbeiten]

Wie jede Transformation kann die DCT umgekehrt werden. Die Inverse der DCT-I ist die DCT-I mit einem Faktor von 2/(N−1). Die Inverse der DCT-IV ist die DCT-IV mit einem Faktor 2/N. Die Inverse der DCT-II ist die DCT-III mit einem Faktor von 2/N bzw. umgekehrt.

Die Vorfaktoren der DCT sind in der Literatur nicht einheitlich festgelegt. Beispielsweise wird von manchen Autoren bei der DCT ein zusätzlicher Faktor von \sqrt{2/N} eingeführt, um den zusätzlichen Faktor bei der inversen Operation zu vermeiden. Durch geeignete Wahl des konstanten Faktors kann die Transformationsmatrix eine orthogonale Matrix darstellen.

Mehrdimensionale DCT[Bearbeiten]

Spektralkoeffizienten der zweidimensionalen DCT-II mit N1=N2=8
Basisfunktionen der diskreten Kosinustransformation

Insbesondere in der digitalen Bildverarbeitung spielt die zweidimensionale DCT, basierend auf der DCT-II, eine wesentliche Rolle. Die Erweiterung auf mehrere Dimensionen erfolgt im einfachsten Fall durch eine spalten- bzw. zeilenweise Anwendung der Transformation. Für praktische Implementierungen existieren zur Berechnung höherdimensionaler Transformationen effizientere Algorithmen.

X_{k_1,k_2} =
\sum_{n_1=0}^{N_1-1}
\sum_{n_2=0}^{N_2-1}
x_{n_1,n_2}
\cos \left[\frac{\pi}{N_1} \left(n_1+\frac{1}{2}\right) k_1 \right]
\cos \left[\frac{\pi}{N_2} \left(n_2+\frac{1}{2}\right) k_2 \right]

Die rechte Abbildung zeigt als einfaches Beispiel alle Spektralkomponenten einer zweidimensionalen DCT-II mit in jeder Dimension acht Koeffizienten. Das Feld links oben (Index 0,0) stellt den Gleichanteil des Signals dar, in horizontaler Richtung sind die horizontalen Frequenzanteile aufsteigend. Über zwei Indizes hinweg wird die Frequenz verdoppelt. Gleiches gilt für die vertikale Richtung und für die Linearkombination aus den beiden Richtungen.

Anwendung von 2D-DCT[Bearbeiten]

In JPEG wird jede Farb-Komponente (Y, Cb und Cr) des Bildes in 8×8-Blöcke eingeteilt, die einer 2D-DCT unterzogen werden.

Anwendung von 3D-DCT[Bearbeiten]

In Filmformaten wird mitunter auch 3D-DCT angewendet. Dabei wird eine Bildergruppe (Group of Pictures, GoP) von mehreren Bilder auch bezüglich der zeitlichen Veränderung betrachtet. Diese Methode findet zum Beispiel bei SoftCast Anwendung.[2]

Literatur[Bearbeiten]

  •  Philipp W.Besslich, Tian Lu: Diskrete Orthogonaltransformationen. Springer Verlag, 1990, ISBN 3-540-52151-8.
  •  Vladimir Britanak, Patrick C. Yip, K. R. Rao: Discrete Cosine and Sine Transforms: General Properties, Fast Algorithms and Integer Approximations. 1. Auflage. Academic Press, 2007, ISBN 978-0-12373624-6.

Einzelnachweise[Bearbeiten]

  1. N. Ahmed, T. Natarajan, K. R. Rao: Discrete Cosine Transform. In: IEEE Trans. Computers. Band C-23, Nr. 1, 1974, S. 90–93, doi:10.1109/T-C.1974.223784.
  2. S. Jakubczak, D. Katabi: A Cross-Layer Design for Scalable Mobile Video. In: Proceeding MobiCom '11 Proceedings of the 17th annual international conference on Mobile computing and networking. 2011, S. 289–300, doi:10.1145/2030613.2030646.