6b Die Zweidimensionale Diskrete Kosinustransformation

Die Übertragung der 1D-DCT auf die 2D-DCT fällt nun recht einfach. Man muss sich darüber im Klaren sein, dass f(x,y) nun von zwei Variablen abhängig ist, die auf eine dritte Dimension projiziert werden.

Am Beispiel für u=v=4 ist hier gezeigt, wie der Graph einer kontinuierlichen Kosinusfunktion aussieht, die Variable in zwei Dimensionen besitzt.

Man kann sich das so vorstellen, dass f(x) der 1D-DCT z.B. das örtliche Auf und Ab der Meereswellen im Querschnitt beschreiben könnte, f(x,y) könnte die örtlichen Schwingungen der gesamten Meeresoberfläche beschreiben. Im Fall von Schwingungen in Bildern beschreibt f(x) einen Querschnitt durch das Bild, wohingegen f(x,y) die gesamte Bildoberfläche angibt. Bei der JPEG Kompression ist das die gesamte Bildoberfläche eines einzeln bearbeiteten 8 mal 8 großen Datenblocks.

Überlagerung zweier solcher Kosinusfunktionen.

Die 2D-DCT entsteht durch Multiplikation zweier 1D-DCT, wobei f(x) und f(y) zu einem f(x,y) kombiniert werden. Es wird daraus nicht etwa f²(x,y), da man sich die diskrete zweidimensionale Verteilung der f-Werte als eine Aneinanderreihung von eindimensionalen Verteilungen von f-Werten vorstellen kann. Die Werte bleiben gleich, für eine korrekte Zuordnung werden nun allerdings zwei Variablen benötigt. Die Formel der 2D-DCT lautet also:

6.14

Natürlich ist auch hier

Es gibt 8 verschiedene horizontal- und 8 verschiedene Vertikalfrequenzen. Es gibt also 64 verschiedene Kombinationen dieser und demnach 64 F(u,v) Werte. Analog zur eindimensionalen DCT ist der Wert F(0,0) der DC-Koeffizient, alle anderen AC-Koeffizienten.

Zunächst möchten wir wieder den DC Koeffizienten besprechen. Für ihn sind u = 0 und v = 0. Deswegen werden die Kosinuswerte zu 1 und die Faktoren C_u und C_v sind beide . Deshalb erhalten wir

.

Man summiert alle f-Werte auf und teilt durch 8. Es gibt 64 verschiedene f-Werte und deren Summe entspricht dem 64-fachen Mittelwert aller f(x,y). Wir schreiben daher um:

Wie man sieht, ist der DC-Koeffizient der 2D-DCT das 8-fache des arithmetischen Mittelwertes aller f(x,y).

Gehen wir nun näher auf die AC-Koeffizienten ein. Wie schon bei der 1D-DCT kann auch hier zur Vereinfachung der trigonometrische Satz des Pythagoras benutzt werden, um die mittlere Amplitude zu berechnen. Analog zu 6.5 und 6.6 kann 6.14 also geschrieben werden als:

6.15

Im Folgenden werden zunächst die Fälle behandelt in denen gilt: und .

In diesen Fällen sind die Faktoren C_u und C_v beide gleich 1. Man berechne die Summe nacheinander:

Der rechte Summenterm entspricht pro forma der Summe in 6.6. Geht man vor wie für 6.6, erhält man für die Summe den vierfachen gewichteten Mittelwert der Amplituden für ein x und alle y:

Nun muss noch über alle x summiert werden:

Verfährt man analog zu oben, wird daraus:

F(u,v) ist also das Vierfache einer gewichteten durchschnittlichen Amplitude.

Für den Fall, dass entweder u = 0 oder v = 0 ist, geht man ähnlich vor, man muss jedoch beachten, dass nun ein Faktor C_u oder C_v gleich ist. Setzen wir für die folgende Bearbeitung willkürlich fest, dass v = 0 ist. Aus 6.15 wird dann:

6.16

Hierbei gilt:

Unter der Annahme, dass v = 0 ist, ist also diese Summe gleich der 8-fachen Durchschnittsamplitude für die Frequenz 0, was nichts anderes ist als das 8-fache des Durchschnittswertes aller f(y)-Werte.

6.16 wird dann zu

.

Hierbei ist die Summe wieder das 4-fache der Durchschnittsamplitude, also erhält man:

Da diese Tatsache ebenso gilt, wenn u = 0 ist und , schreiben wir allgemein:

,

wobei entweder ist.

F(u,v) gibt also für den Fall, dass eine Frequenz gleich null ist, das -fache der mittleren Amplitude an.

Fazit

Die DCT transformiert die ortsabhängigen Pixelwerte, d.h. Helligkeits- oder Farbwerte, in frequenzabhängige Amplituden. Zu diesem Zweck werden die Pixelwerte als Überlagerung von diskreten Kosinusfunktionen verschiedener Frequenzen interpretiert, und zu jeder dieser Kosinusschwingungen wird durch die DCT eine Amplitude bestimmt. Die DCT gibt diese Amplituden jedoch nicht direkt aus, sondern liefert bestimmte Vielfache der einzelnen Amplituden.

Wichtig ist, dass aus den bei der DCT entstandenen Amplituden die ursprünglichen Pixelwerte wieder richtig hergestellt werden können. Durch die DCT gehen also keine Informationen verloren, was der Grund dafür ist, dass allein durch Anwendung der DCT auch kein Speicherplatz gespart werden kann. Die DCT ist verlustfrei. Würde man die durch die DCT entstandenen Amplituden direkt ohne weitere Zwischenschritte codieren, wäre man sogar vor das Problem gestellt, dass die Wertemenge der zu codierenden F(u,v)-Werte größer ist als die Wertemenge von f(x,y). F(0,0) gibt zum Beispiel den 8-fachen Mittelwert aller f(x,y) an, welche Werte von -128 bis 127 annehmen können. F(u,v) hat also eine Wertemenge von [-1024; 1016]. Für andere u und v verhält es sich ähnlich, wobei jedoch die Faktoren, mit denen die Amplituden multipliziert werden, nicht so groß sind. Allerdings gibt es noch eine interessante Tatsache, die die niedrigeren Faktoren zum Teil ausgleichen kann. Kein f(x,y) liegt auf einem Maximum einer Kosinusfunktion mit einer Frequenz (u,v). Amplituden geben allerdings den Funktionswert beim Maximum der Kosinusschwingung an. Deshalb kann eine durch die DCT angegebene Amplitude für eine bestimmte Frequenz (u,v) größer sein als 127 oder kleiner als -128, wenn f(x,y) geeignete Werte annimmt, die zu dieser bestimmten Frequenz "passen".