Die diskrete Kosinustransformation (DCT – discrete cosine transformation) ist eine diskrete, reellwertige, lineare und orthogonale Transformation. Sie wurde 1974 ertsmalig vorgestellt und wurde aus der Fourier-Transformation (FT) unter Ausnutzung von Signalsymmetrien abgeleitet. Da es sich um eine reellwertige Transformation handelt, im Gegensatz zur FT deren Ergebnisse einen Real- und einen Imaginärteil hat, was natürlich nicht ganz so bequem zu handhaben ist und auch die doppelte Menge an Daten erfordert.
In diesem Artikel möchte ich einerseits die theoretischen Grundlagen und Anwendungsgebiete der DCT streifen, sowie anhand von Codebeispielen in Java eine Implementierung der diskreten Kosinustransformation vorstellen.
Theoretischer Hintergrund der diskreten Cosinus-Transformation
Generell kann man mit Hilfe der DCT eine Transformation eines Signales in geeignete Basisfunktionen vornehmen. Dabei werden die Signalwerte x auf die Koeffizienten der Basisfunktion abgebildet. Dabei gilt es Basisfunktionen zu finden die das Signal in möglichst wenige Bestandteile aufteilen. Die Qualität der Basisfunktionen wird zudem dadurch bestimmt, wie gut das Signal dekorreliert wird. Dekorrelation ist in diesem Zusammenhang so zu verstehen, dass Abhängigkeiten der Signalwerte untereinander reduziert werden, da bei zeitlichen oder räumlichen Signalen Werte meist vom benachbarten Wert abhängen. Nach der Dekorrelation sollen die Abhängigkeiten möglichst beseitigt sein, ohne dabei Informationsgehalt zu verlieren. Abgesehen von der Transformationen eigenen sich zur dekorrelation von Signalen sog. Prädiktionsverfahren, wie die lineare Prädiktion, oder aber Filterbanken.
Anwendungsgebiete der DCT
Genau wie die DFT wandelt die DCT ein Signal vom Orts- bzw. Zeitbereich in den Frequenzbereich. Besonders im Audio- und Videobereich liegen oftmals im unteren Spektralbereich hohe Signalenergien vor die mit Hilfe dieser Transformation gut dekorreliert werden können.
Ein weiteres Anwendungsgebiet ist die Bildverarbeitung. Ein bekanntes Beispiel ist das JPEG Format, welches die 2-D Kosinustransformation einsetzt um die Bildmatrix vom Ortsbereich in den Frequenzbereich zu wandeln, welcher die Helligkeitsschwankungen einen Bildes visualisiert. Bei der Frequenzanalyse der Helligkeitsschwankungen werden grobe und feine Strukturen eines Bildes voneinander getrennt. Beim JPEG-Format ist die Transformation eine Vorbereitung der Daten für die anschliessende Kompression.
Implementierung der diskreten Cosinus-Transformation
Es gibt generell drei populäre Möglichkeiten für die Implementierung.
Die direkte Implementierung
Die separierte Implementierung, welche die 2D DCT auf die eindimensionale Variante zurückführt. Dies reduziert die Komplexität um eine Größenordnung: O(n^4) -> O(n^3)
Das Schema von Arai, welches einen sehr schnellen Algorithmus für den (wichtigen) Spezialfall N=8 bezeichnet. Auf diesen Algorithmus werde ich hier jedoch nicht näher eingehen, da die Implementierung eher trivial ist. Auf Wunsch kann ich jedoch auch hier eine Erklärung sowie eine Implementierung gerne hinzufügen.
Codebeispiel – Java Implementierung der direkten Kosinus-Transformation
Codebeispiel - Java Implementierung der inversen Kosinus-Transformation (iDCT)
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.