Benutzer:ThePacker/Datenkompression DCT

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Die DCT

Die DCT (Diskrete-Cosinus-Transformation) ist eine von der Fourier-Transformation inspirierte Transformationsvorschrift. Sie ähnelt der Arbeitsweise der Fouriertransormation sehr. Dafür wird die Ähnlichkeit des zu transformierenden Signals mit der Cosinusfunktion ermittelt. Bei einer 8 Punkt Transformation werden die 8 zu transformierenden Punke mit orthogonalen Basisfunktionen (Basisvektoren) verglichen. Für jede Cosinusschwingung wird die Übereinstimmung des Signals mit dieser gemessen und als Vektor ausgegeben. Die so berechneten Werte sind nun linear unabhängig. Die Ortogonalität der ganzzahligen Frequenzen der Kosinus-funktion überträgt sich damit auf den dekorrelierten Ausgabevektor.

(naja, dass muss wohl noch besser werden.)

1D - DCT

Die DCT ist mittlerweile in sehr verschiedenen Ausprägungen bekannt. Zunächst soll die eindimensionale DCT (1D-DCT) erläutert werden. ....

DCT I

Die Inverse der DCT-I ist die DCT-I.

DCT II

  • Das ist die meist genutzte Form der DCT -

Die Inverse der DCT-II ist die DCT-III.

DCT III

  • Inverse zur DCT II deswegen meist IDCT genannt.

Die Inverse der DCT-III ist die DCT-II.

DCT IV

Die Inverse der DCT-IV ist die DCT-IV.

2D - DCT - NxM

  • Zweidimensionale Diskrete Cosinus Transformation

DCT I

DCT II

  • Insbesondere Bild und Video Verarbeitung
  • Parametrierung (a=1, b=0)

DCT III

DCT IV

Überlappende Transformation

MDCT / IMDCT

  • Modifizierte Diskrete Cosinus Transformation
  • Teilband Transformationscodierung
  • Analyse / Synthese - Filterbänke
  • (MPEG 1 Layer 3) / MPEG 2 Audio
  • Analyse
  • Synthese

FDCT (Fast-DCT)

Die schnelle DCT ist ein optimiertes Rechenverfahren, um die Berechnung einr vollständigen DCT in kürzerer Zeit zu ermöglichen. Additionen, Subtraktionen und Multiplikationen haben einen unterschiedlichen Berechnungsaufwand. Eine Multiplikation zweier Zahlen ist aufwändiger zu berechnen, als eine Addition zweier Zahlen. Das gilt sowohl für den Bereich der natürlichen Zahlen, als auch für den Beeich der rationalen und irrationalen Zahlen. Möchte man eine eindimensionale 8-Werte DCT berechnen, so müssen bei einer langsamen (naheliegenden) Implementation 64 mal der Cosinus, 64 Multiplikationen und ebenso viele Additionen durchgeführt werden. Das ist für die Transformation von 8 Punkten ein quadratischer Aufwand . Für eine Transformation von 1024 Punkten bedeutet dass, dass Multiplikationen und ebenso viele Additionen und Cosinusberechungen durchgeführt werden müssen. Das sind Größenordnungen, die für eine Transformation von 1024 Bildpunkten oder Messwerten völlig inakzeptabel sind. Aus diesem Grund suchte man nach Möglichkeiten, die Berechnung der DCT effizienter auszuführen.

Im Regelfall möchte man alle Werte gemeinsam transformieren. Hin und wieder werden aufgrund der Struktur der DCT identische Berechnungen ausgeführt. Speichert man diese Ergebnisse zwischen, so können Doppelberechnungen vermieden werden. Eine andere Möglichkeit besteht darin, die Axiome der Mathematik zu verwenden, um Berechnungen zusammenzufassen.

Ein Beispiel für ein solches Axiom ist:

Der Unterschied zwischen den beiden Berechnungen (links und rechts) ist, dass die Anzahl der Additionen (eine) zwar konstant geblieben ist, sich aber die Anzahl der Multiplikationen auf der linken Seite von zwei auf eine auf der rechten Seite reduziert hat. Das bedeutet, dass durch geschicktes Sortieren der Faktoren und die Verwendung von Axiomen eine Reduktion der Anzahl der nötigen Rechenoperationen erfolgen kann, ohne die Korrektheit des Ergebnisses zu beeinflussen.

Die gleichen Optimierungen sind auch bei unvollständigen FDCT-Berechnungen (sog. pruning von to prune) implementierbar. Einige Anwendungsfälle der DCT benötigen nur die ersten 100 von 1000 DCT-Koeffizienten. Dann helfen spezielle vorberechnete Tabellen um nur die nötigen Berechnungen optimiert durchzuführen. Dann unterscheidet man vollständige und unvollständige Berechnungsschritte. Eine vollständige Berechnung bedeutet, dass alle Rechenoperationen durchgeführt werden. Eine unvollständige Berechnung bedeutet, dass nur eine Teilmenge der Ergebnisse für die nachfolgenden Berechnungen gebraucht wird und man aufgrund dessen die nicht benötigten Ergebnisse auch nicht berechnet. Das mag sich logisch anhören, ist aber nicht leicht zu realisieren.

Eine vollständige Schmetterlingsoperation benötigt eine Multiplikation und zwei Additionen. Eine unvollständige Operation benötigt lediglich eine Addition. Allein die Unterscheidung ob das Ergebnis benötigt wird oder nicht führt dazu, dass sowohl eine Multiplikation als auch eine Addition eingespart werden kann. Wobei das Einsparen der Multiplikation das lukrativere Ziel ist, als die eingesparte Addition.

Herleitung der 2 Punkt DCT
2 Punkt DCT als Beispiel -
n=0 n=1
c 0/4 c 0/4
c 1/4 c 3/4


2 Punkt DCT als Beispiel -
n=0 n=1
1.000 1.000
0.707 -0.707


Damit ergibt sich für die Gesamttransformation:

Es werden für eine 2-Punkt DCT insgesamt 2 Additionen und eine Multilikation benötigt.

Herleitung der schnellen 3-Punkt DCT-II
3 Punkt DCT als Beispiel -
n=0 n=1 n=2
c 0/6 c 0/6 c 0/6
c 1/6 c 3/6 c 5/6
c 2/6 c 6/6 c 10/6


n=0 n=1 n=2
1.000 1.000 1.000
0.866 0.000 -0.866
0.500 -1.000 0.500


Die Gesamttransformation ergibt sich wie folgt

Substitution: (2 Additionen)

Eine Multiplikation und zwei Additionen, sowie eine shift Operation.

  • X_0 = 1.000(a_0) + 1.000(x_1)
  • X_2 = 0.500(a_0) - 1.000(x_1)
  • X_1 = 0.866(a_1)

Damit werden für eine 3 Punkt DCT 4 Additionen eine Multiplikation und eine Shiftoperation benötigt.

Herleitung der schnellen 4-Punkt DCT-II
4 Punkt DCT als Beispiel -
n=0 n=1 n=2 n=3
c 0/8 c 0/8 c 0/8 c 0/8
c 1/8 c 3/8 c 5/8 c 7/8
c 2/8 c 6/8 c 10/8 c 14/8
c 3/8 c 9/8 c 15/8 c 21/8


n=0 n=1 n=2 n=3
1.0 1.0 1.0 1.0
0.924 0.383 -0.383 -0.924
0.707 -0.707 -0.707 0.707
0.383 -0.924 0.924 -0.383


Daraus ergibt sich für die Transformation folgendes:

Lassen Sie uns die Spalten und Zeilen sortieren.

nach substitution von: (4 Additionen)

ergibt sich folgende Transformation: (4 Additionen, 5 Multiplikationen)

Damit benötigt eine 4 Punkt-Transformation 8 Additionen und 5 Multiplikationen, statt 12 Additionen und 12 Multiplikationen

Herleitung einer schnellen 5 Punkt Transformation
Herleitung einer schnellen 6 Punkt Transformation
Herleitung einer schnellen 7 Punkt Transformation
Herleitung einer schnellen 8 Punkt Transformation
Herleitung einer schnellen 9 Punkt Transformation