Diskrete Kosinustransformation

Die Diskrete Kosinustransformation (DCT, engl.: „Discrete Cosine Transformation“) ist eine reellwertige diskrete lineare orthogonale Transformation, die ähnlich der diskreten Fouriertransformation (DFT) ein zeitdiskretes Signal vom Zeitbereich (bei Zeitsignalen) bzw. dem Ortsbereich (bei räumlichen Signalen) in den Frequenzbereich transformiert. Sie wurde 1974 von N. Ahmed et al. beschrieben.^[1]

Anwendung findet die DCT zur Redundanzreduktion von Bildsignalen, beispielsweise im Rahmen des Bildspeicherformats JPEG. Zur Audiodatenkompression findet eine modifizierte diskrete Kosinustransformation (MDCT) Anwendung, beispielsweise im Rahmen des MP3-Formats. Jene Signale weisen typischerweise im unteren Spektralbereich hohe Signalenergien auf, zu deren Dekorrelation sich die DCT gut eignet. Weitere 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).

Allgemeines

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 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. Durch die Art, wie die Signalfolge unter Vermeidung von Sprüngen an den Rändern bei der DCT fortgesetzt wird, ergibt sich, dass sich die Energie primär in unteren spektralen Anteilen findet. Damit lässt sich durch gröbere Quantisierung der höheren Spektralanteile eine hohe Kompressionsrate bei guter Qualität mit der DCT erzielen.

Die diskrete Fouriertransformation weist, neben dem Umstand, im Allgemeinen eine komplexwertige Transformation zu sein, eine periodische Fortsetzung mit im Regelfall Sprüngen an den Randstellen auf. Dies gilt auch für die diskrete Sinustransformation, die am Anfang der Folge eine ungerade Fortsetzung aufweist. Dadurch lassen sich bei diesen Transformationen im Bereich der Datenkompression obere Spektralkomponenten nicht entsprechend grob quantisieren, bzw. wäre dies mit einem stärkeren Informationsverlust oder Qualitätsverlust verbunden, als es bei der diskreten Kosinustransformation der Fall ist. Daraus ergibt sich die Präferenz für bestimmte Formen der DCT im Bereich der verlustbehafteten Datenkompression von Bild- und Audiosignalen.

• Die DCT transformiert aufgrund der Wahl der Art der Fortsetzung (Randwerte) Signalfolgen wie Bild- oder Audiodaten primär in untere spektrale Komponenten, wodurch sich durch die Nachfolgende und von der DCT unabhängige Quantisierung der Amplitudenwerte obere Spektralanteile mit nur geringer Auflösung bzw. mit einer nur sehr groben Quantisierung ohne wesentlichen Qualitätsverlust darstellen lassen.
• Im Gegensatz zur diskreten Fourier-Transformation sind alle Formen der DCT reelle Transformationen mit reellen Koeffizienten.
• 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

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

Die DCT-I ist bezüglich ihrer Randwerte gerade am Anfang um x₀ und gerade am Ende um x_N-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

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 x_N-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

Die DCT-III ist die Umkehrung der DCT-II. Sie ist bezüglich ihrer Randwerte gerade am Anfang um x₀ und ungerade am Ende um x_N. Die Ausgabefolge ist gerade am Anfang um X_-1/2 und gerade am Ende um X_N-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

Die DCT-IV ist bezüglich ihrer Randwerte gerade am Anfang um x_-1/2 und ungerade am Ende um x_N-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

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

Spektralkoeffizienten der zweidimensionalen DCT-II mit N₁=N₂=8

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.

Literatur

• 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

1. ↑ N. Ahmed, T. Natarajan und K. R. Rao, Discrete Cosine Transform, IEEE Trans. Computers, Ausgabe 90-93, Januar 1974