Benutzer:ThePacker/Datenkompression DCT

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 -
$X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left(\pi {\frac {(2n+1)k}{2N}}\right)$

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

DCT III

Inverse zur DCT II deswegen meist IDCT genannt.
$X_{k}={\frac {1}{2}}x_{0}+\sum _{n=1}^{N-1}x_{n}\cos \left(\pi {\frac {(2k+1)n}{2N}}\right)$

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

DCT IV

$X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left(\pi {\frac {(2k+1)(2n+1)}{4N}}\right)$

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

2D - DCT - NxM

Zweidimensionale Diskrete Cosinus Transformation
$X_{j,k}\left(a,b\right)=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}x_{n,m}\cos {\pi {\frac {(2n+a)(2j+b)}{4N}}}\cdot \cos {\pi {\frac {(2m+a)(2k+b)}{4M}}}$

DCT I

DCT II

Insbesondere Bild und Video Verarbeitung
Parametrierung (a=1, b=0)
$X_{j,k}=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}x_{n,m}\cos {\pi {\frac {(2n+1)j}{2N}}}\cdot \cos {\pi {\frac {(2m+1)k}{2M}}}$

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
$C_{k}=\sum _{n=0}^{N-1}\cos \left({\frac {\pi (2n+1+N/2)(2k+1)}{2N}}\right)$
$k=0..N/2-1$

Synthese
$x_{n}={\frac {2}{N}}\sum _{k=0}^{N/2-1}C_{k}\cos \left({\frac {\pi (2n+1+N/2)(2k+1)}{2N}}\right)$
$n=0..N-1$

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 $\mathbf {O} (n^{2})$ . Für eine Transformation von 1024 Punkten bedeutet dass, dass $2^{20}$ 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:

$a\cdot c+b\cdot c=(a+b)\cdot c$

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 - $ca/b=cos(\pi {\frac {a}{b}})$
n=0	n=1
c 0/4	c 0/4
c 1/4	c 3/4

2 Punkt DCT als Beispiel - $ca/b=cos(\pi {\frac {a}{b}})$
n=0	n=1
1.000	1.000
0.707	-0.707

Damit ergibt sich für die Gesamttransformation:

$X_{0}=1.000\cdot (x_{0}+x_{1})$
$X_{1}=0.707\cdot (x_{0}-x_{1})$

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 - $ca/b=cos(\pi {\frac {a}{b}})$
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

$X_{0}=1.000\cdot x_{0}+1.000\cdot x_{1}+1.000\cdot x_{2}$
$X_{1}=0.866\cdot x_{0}+0.000\cdot x_{1}-0.866\cdot x_{2}$
$X_{2}=0.500\cdot x_{0}-1.000\cdot x_{1}+0.500\cdot x_{2}$

Substitution: (2 Additionen)

$a_{0}=x0+x2$
$a_{1}=x0-x2$

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 - $ca/b=cos(\pi {\frac {a}{b}})$
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:

$X_{0}=1.000\cdot x_{0}+1.000\cdot x_{1}+1.000\cdot x_{2}+1.000\cdot x_{3}$
$X_{1}=0.924\cdot x_{0}+0.383\cdot x_{1}-0.383\cdot x_{2}-0.924\cdot x_{3}$
$X_{2}=0.707\cdot x_{0}-0.707\cdot x_{1}-0.707\cdot x_{2}+0.707\cdot x_{3}$
$X_{3}=0.383\cdot x_{0}-0.924\cdot x_{1}+0.924\cdot x_{2}-0.383\cdot x_{3}$

Lassen Sie uns die Spalten und Zeilen sortieren.

$X_{0}=1.000\cdot x_{0}+1.000\cdot x_{3}+1.000\cdot x_{1}+1.000\cdot x_{2}$
$X_{2}=0.707\cdot x_{0}+0.707\cdot x_{3}-0.707\cdot x_{1}-0.707\cdot x_{2}$
$X_{1}=0.924\cdot x_{0}-0.924\cdot x_{3}+0.383\cdot x_{1}-0.383\cdot x_{2}$
$X_{3}=0.383\cdot x_{0}-0.383\cdot x_{3}-0.924\cdot x_{1}+0.924\cdot x_{2}$

nach substitution von: (4 Additionen)

$a_{0}=x_{0}+x_{3}$
$a_{1}=x_{1}+x_{2}$
$a_{2}=x_{0}-x_{3}$
$a_{3}=x_{1}-x_{2}$

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

$X_{0}=1.000\cdot (a_{0}+a_{1})$
$X_{2}=0.707\cdot (a_{0}-a_{1})$
$X_{1}=0.924\cdot a_{2}+0.383\cdot a_{3}$
$X_{3}=0.383\cdot a_{2}-0.924\cdot a_{3}$

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