Einleitung
kap1: wahrnehmung
kap2: das digitale bild
kap3: die digitale aufnahme
kap4: das jpeg-verfahren
kap5: farbraumveränderung
kap6: dct
kap7: quantisierung
kap8: codierung
kap9: de-codierung
kap10: dateitypen
kap11: jpeg2000
resümee
quellen
autoren


< Kapitel 5 Kapitel 6b >

6a Die Eindimensionale Diskrete Kosinustransformation


Nach der Indexverschiebung wird eine zweidimensionale diskrete Kosinustransformation angewendet. Es bietet sich an, zum besseren Verständnis zuerst die simplere eindimensionale DCT zu besprechen, um von dort dann später auf die zweidimensionale DCT zu schließen. Die mathematische Anwendbarkeit der eindimensionalen wie der zweidimensionalen DCT ist selbstverständlich nicht nur auf Bildpunkte beschränkt, jedoch erscheint es sinnvoll, sie hier nur im Zusammenhang mit diskreten Bildpunkten zu besprechen. Damit man die eindimensionale DCT anwenden kann, müssen Werte von Bildpunkten in nur einer Dimension gegeben sein. Diese eindimensionale Anordnung kann zum Beispiel eine Zeile der zweidimensionalen Verteilung der Bildpunkte im Bild darstellen.
Die Werte sind also zum Beispiel von links nach rechts angeordnet.


x 0 1 2 3 ...
f(x) f(0) f(1) f(2) f(3) ...


Die diskrete Kosinustransformation ist eine mathematische Operation, die die diskrete Ort-Werte Zuordnung in eine diskrete Frequenz-Amplituden Zuordnung umwandelt. Die Frequenz einer Kosinusfunktion gibt in diesem Falle an, wie oft sich der Verlauf der periodischen Kosinusfunktion pro Ortseinheit wiederholt. Amplituden sind hier definiert als die betraglichen Maximalwerte, die eine dazugehörige Kosinusfunktion annimmt.

Durch die entstandene Zuordnung wird beschrieben, wie sehr die Werte um die Mitte des Intervalls [-128; 127], die bei -0,5 liegt, schwanken. Ausgedrückt wird dies in Amplituden von Kosinusschwingungen verschiedener diskreter Frequenzen. Das heißt, die neue Frequenz- Amplituden Zuordnung beschreibt, wie "schnell" und stark sich die Werte im Verlauf der Funktion f(x) verändern. Eine niedrige Amplitude für eine bestimmte Frequenz bedeutet, dass die f(x)-Werte mit dieser Frequenz nur geringfügig um die Mitte des Intervalls [-128; 127] schwingen.

Die diskrete Funktion f(x) wird als Überlagerung von Kosinusschwingungen verschiedener Frequenzen gedeutet. Das heißt, die f(x)-Werte werden als Addition der Funktionswerte der verschiedenen Kosinusfunktionen an der Stelle x interpretiert. Eine Überlagerung von Kosinusfunktionen bedeutet also die Summe von Kosinusfunktionen. Zur besseren Vorstellung, wie so etwas aussehen kann, liegt hier ein Beispiel vor, das drei Kosinusfunktionen zeigt, die (wie wir später sehen werden) auch in der DCT benutzt werden, und deren Überlagerung angibt.



Eine Überlagerung von Kosinusfunktionen bedeutet die Summe von Kosinusfunktionen. Als Beispiel betrachten wir diese drei cos-Funktionen k2(x), k3(x) und k7(x).



Werden obige drei cos-Funktionen überlagert, so addieren sich die Funktionswerte und wir erhalten diese neue Funktion kSum(x).

Bei der DCT entspricht die Anzahl der definierten Orte der Anzahl der verschiedenen betrachteten Frequenzen. Bei der eindimensionalen DCT werden horizontal angeordnete Werte in horizontal verlaufende Schwingungen umgewandelt, d.h. die Kosinusfunktion ist eine Funktion des Ortes. Die Frequenzen werden dabei genauso durchnummeriert wie die Orte, wobei größere Nummern der Frequenzen auch größere Frequenzen bedeuten.


u 0 1 2 3 ...
F(u) F(0) F(1) F(2) F(3) ...


Die Formel für die eindimensionale DCT lautet:

6.1

hierbei ist:

Für den Spezialfall u = 0 ergibt sich dann

,

6.2

da hier und cos(0) = 1 ist.

Da bei der JPEG Komprimierung eine 2D-DCT (zweidimensionale DCT) mit N = 8 benutzt wird, werden wir von nun an vor allem auch die 1D-DCT mit N = 8 betrachten. Für sie gilt:

6.3

Wir wissen also nun, dass die Frequenzen von 0 bis 7 in Schritten von 1 durchnummeriert werden. Dies allein sagt nichts über die Werte der tatsächlichen Frequenzen aus, denn die Zahlen 0 bis 7 bezeichnen lediglich deren Nummer, sozusagen deren Stellung in der Tabelle. Um die Frequenzen aus deren Nummern errechnen zu können, geht man folgendermaßen vor:

Für die Frequenz einer Kosinusschwingung gilt:

Durch geeignetes Umformen unserer Kosinusfunktion aus 6.3

erhält man

.

6.4

Man kann b nun einfach ablesen: .

Die Frequenz errechnet sich also durch: .

Die Frequenzen sind demnach:


u 0 1 2 3 4 5 6 7
0

Zusammenhang zwischen den Nummern u und den Frequenzen . Aus Gründen der Anschaulichkeit wurden die Frequenzen ungekürzt dargestellt.


Wenden wir uns nun wieder der Formel 6.3 zu, durch die unter Verwendung der vorgegebenen Daten der Wert F(u) ausgerechnet werden kann. Im Folgenden wird dargelegt werden, was unter F(u) zu verstehen ist.

Die Werte von F(u) entsprechen einem Maß für die Amplituden von Schwingungen der Frequenz der Nummer u im Bild. Sie sind nur ein Maß für die Amplituden, da sie, wie wir noch sehen werden nicht genau den Amplituden entsprechen.

Wie man anhand der obigen Tabelle sehen kann ist die Frequenz von u = 0 selbst null, was bedeutet dass keine Schwingung vorhanden ist. F(0) beschreibt daher den gleich bleibenden Anteil aller Werte von f(x). Dies bedeutet nichts anderes, als dass eine Art Mittelwert aller f(x) gebildet wird. Es ist deshalb eine Art Mittelwert, da sich folgender Ausdruck, der durch Einsetzen von N = 8 in 6.2 entsteht,

von der Definition des arithmetischen Mittelwertes für alle f(x)

nur um den Faktor unterscheidet. Die Formulierung "der gleich bleibende Anteil aller Werte von f(x)" eröffnet nun auch ihren Sinn: Der gleich bleibende Anteil ist der Wert, der, falls man ihn für alle Orte gleich annimmt, über alle Orte aufaddiert die gleiche Summe ergeben würde wie die Summe der tatsächlichen Werte von f(x). Dies ist auch eine Beschreibung des arithmetischen Mittelwertes. Der gleich bleibende Anteil bedeutet nichts anderes als der arithmetische Mittelwert. Wie schon gesagt, beschreibt F(0) den gleich bleibenden Anteil, also den arithmetischen Mittelwert, indem er einen Wert angibt, der sich nur durch einen Faktor, nämlich , vom arithmetischen Mittelwert unterscheidet.
F(0) wird auch DC- Koeffizient genannt, was von direct current, Gleichstrom, abgeleitet wird.
Da alle anderen Werte von u für Frequenzen stehen, die von 0 verschieden sind, werden alle Werte von F(x) außer F(0) AC- Koeffizienten genannt, welches von alternating current kommt, was Wechselstrom bedeutet.

Für ein besseres Verständnis der AC-Koeffizienten betrachten wir noch einmal den Term 6.4.

Wichtig: Die folgenden Überlegungen zur Berechnung der AC-Koeffizienten sind nur gültig für !

Wie bereits gezeigt bewirkt der Faktor , dass alle Frequenzen ein Vielfaches von sind. Auf einer Intervalllänge von 8 durchläuft die Kosinusfunktion also ein Vielfaches der halben Periode. Unsere Kosinusfunktion ist um 0,5 nach links verschoben und die diskreten x-Werte von 0 bis 7 bilden die Definitionsmenge.



Alle unsere cos-Funktionen, wie z.B. hier k(x) mit u=6, stellen sich als um 0,5 nach links verschobene, normale cos-Funktionen dar.

Dies bewirkt, dass die x-Werte gleichmäßig in dem Intervall [-0,5; 7,5], das die Länge 8 hat, verteilt sind. "Gleichmäßig verteilt" soll hier bedeuten, dass es für jeden diskreten x-Wert mit der Differenz x zum Anfang des Intervalls, einen von diesem verschiedenen x zum Ende des Intervalls gibt, was nur durch eine gerade Anzahl von definierten x-Werten zu erreichen ist. Diese gleichmäßige Verteilung bleibt auch bei mehrfacher Halbierung des Intervalls erhalten, solange mindestens zwei x-Werte im Teilintervall definiert sind. Der Grund dafür steht hier. Diese wichtige symmetrische Eigenschaft werden wir später benutzen.

In Formel 6.3 kann man f(x) schreiben als

.

6.5

Man geht nun also davon aus, dass f(x) der Wert einer Kosinusfunktion der Frequenz u mit der Amplitude Au(x) ist. Das heißt, wenn man voraussetzt, dass f(x) der Wert einer Kosinusfunktion an der Stelle x mit der Frequenz der Nummer u ist, muss diese Kosinusfunktion die Amplitude Au(x) besitzen, damit f(x) auf dieser liegen kann.

Der Grund für die Indexverschiebung wird nun auch deutlich. Für die DCT benutzen wir Kosinusfunktionen, die symmetrisch um den Wert 0 schwingen, also solche, die nicht in f(x)-Richtung verschoben sind. Diese Tatsache kann man an obigen Formeln der Kosinusfunktionen erkennen. Diese Kosinusfunktionen sind mathematisch einfacher darzustellen als welche, die um einen von null verschiedenen f(x)-Wert schwingen, also in f(x)-Richtung verschoben sind. Wenn die Elemente unserer Wertemenge nun auch symmetrisch um den Wert 0 verteilt sind, kann man sie als Funktionswerte solcher einfachen Kosinusfunktionen interpretieren. In unserem Fall wurden durch die Indexverschiebung allerdings alle f(x)-Werte symmetrisch um den Wert -0,5 angeordnet. Die Mitte aller Werte, -0,5, um die die f(x)-Werte "schwingen", kommt dem Wert 0 jedoch nah genug, um obige Interpretation zu rechtfertigen. Vertiefende Anmerkung der Verfasser...

Durch Einsetzten von 6.5 wird aus 6.3:

6.6

Zur weiteren Bearbeitung der Formel benutzen wir eine vereinfachte Darstellung der Kosinusfunktion, was uns später auch noch sehr nützlich sein wird. Wir nutzen aus, dass diese Kosinusfunktion eine mittelbare Funktion ist, d.h. dass sie die Funktion einer Funktion ist. Denn, bevor man den Kosinus anwendet, wird der Term in der Klammer berechnet. Man kann unsere Kosinusfunktion daher auch schreiben als , wobei ist.

Oder einfach: .

Durch die Funktion wird ein Winkel angegeben, auf den dann der Kosinus angewendet werden kann. Die Funktion liefert also die Definitionsmenge für die Funktion . Diese Definitionsmenge ist abhängig von dem Parameter u.

Man kann nun, indem man den Kosinus als eine Funktion von auffasst, zur Betrachtung aller 8 Kosinusfunktionen dieselbe Funktion benutzen, bei der allerdings abhängig von u verschiedene - Werte definiert sind. Dies bringt den Vorteil mit sich, dass man mit einer Funktion arbeiten kann, die für alle u die gleichen Eigenschaften besitzt, wie z.B. Symmetrie und Frequenz.

Mit Hilfe dieser Erkenntnis lässt sich nun auch 6.6 weiterbearbeiten. Zu diesem Zweck benutzen wir nun den trigonometrischen Satz des Pythagoras. Er lautet:

,

6.7

wobei gelten muss:

.

6.8

Der Vorteil, den man durch die Verwendung des trigonometrischen Satz des Pythagoras erhält, liegt auf der Hand. Laut 6.6 muss man die Produkte der Amplituden mit der quadrierten Kosinusfunktion über alle x aufsummieren. Im trigonometrischen Satz des Pythagoras werden auch zwei quadrierte Kosinuswerte addiert. Wenn nun die Möglichkeit bestünde, dass man Paare von Winkeln, und somit von x-Werten, hat, die obige Bedingung 6.8 erfüllen, könnte man mit Hilfe von 6.7 die Amplituden zu einem ganzzahligen Vielfachen aufaddieren.

Der Übersicht halber können alle Funktionswerte anders dargestellt werden, was für sie auch die Folge hat, dass für sie eine andere aber äquivalente Bedingung besteht. Diese Bedingung möchten wir als Folge der übersichtlicheren Darstellung der Funktionswerte nun festsetzen.

Die Funktion ist periodisch, d.h., dass sich ihr Verlauf nach gewissen Intervallen auf der -Achse wiederholt. Diese Abstände heißen Periode und sind hier gleich .


Dies ist, wie man an der Zeichnung erkennen kann nicht die einzige Besonderheit von . Die Funktion ist außerdem im Intervall [0;] an der Geraden gespiegelt. Die Funktion nimmt also alle Elemente der Wertemenge bereits im Intervall [0;] an. Jeder Wert von für ein kann also durch ein mit ausgedrückt werden.

Dies geschieht folgendermaßen: Gegeben sei ein mit dem Betrag des Abstands zum nächsten ungeraden Vielfachen von ist. Es gilt nun, da alle Funktionswerte gleich sind, deren -Koordinaten um den gleichen Betrag von einem ungeraden Vielfachen von , also auch von , abweichen:

, wobei der neue Winkel

6.9

innerhalb des Intervalls liegt. Die folgenden drei Tabellen sollen zeigen, wie man diese anderen -Werte benutzen kann, um die Funktionswerte anders darzustellen.





In dieser Tabelle werden die Funktionswerte unserer Kosinusfunktion angegeben, wobei die -Werte einfach unter Benutzung der jeweiligen u und x mit unserem Term für ausgerechnet wurden.





Hier werden die k(x)-Werte ausgedrückt als solche mit . Diese Kosinusfunktion nimmt auch negative Werte an und ist punktsymmetrisch um . Deshalb können negative Funktionswerte als Funktionswerte von mit negativem Vorzeichen ausgedrückt werden.





In der Graphik sieht man , wie den gleichen Funktionswert hat, wie . Deswegen kann man den zweiten -Wert benutzen, um ersteren Funktionswert zu beschreiben.



In dieser Graphik kann man erkennen, dass die Funktion bei den negativen Funktionswert von annimmt. Man kann zur Beschreibung des ersteren Funktionswertes also den negativen Funktionswert des zweiten Winkels benutzen.





Durch Quadrierung fallen die negativen Vorzeichen weg, und man kann alle Werte von , wie oben bereits dargelegt, als Funktionswerte von darstellen.



Gegeben sind in unserem Fall die beiden -Koordinaten und , die wegen

die Differenz haben. Sie haben die Differenzen bzw. zum jeweils nächsten ungeraden Vielfachen von . Addiert man diese beiden Differenzen erhält man die Differenz zwischen den beiden -Werten, die hier ja ist:

6.10

Aus 6.9 und 6.10 erhält man: . Analog gilt auch: .

Wegen 6.10 ist also die neue Bedingung, die von den vereinfacht dargestellten Funktionswerten erfüllt sein muss, um den trigonometrischen Satz des Pythagoras anzuwenden, wenn man alle Funktionswerte als mit beschreibt:

6.11

Durch die DCT muss nun gewährleistet sein, dass es immer 4 Paare von Winkeln gibt, die Bedingung 6.11 erfüllen. Dies ist der Fall, wenn der eine Winkel, ausgedrückt als Element von vom Anfang des Intervalls also von um verschieden ist und der andere von um -.

Wie bereits festgestellt sind alle x-Werte gleichmäßig in einem Intervall verteilt, dass ein Vielfaches einer halben Periode der Kosinusfunktion beträgt, die nicht quadriert ist. Die halbe Periode ist also hier , da nicht g(x) sondern die nichtquadrierte Kosinusfunktion gemeint ist. Da durch die Funktion alle x-Werte für ein u in gleicher Weise auf projiziert werden, sind auch die -Werte gleichmäßig in einem Intervall verteilt, dass ein Vielfaches der halben Periode beträgt. Halbiert man dieses Intervall solange, bis man Teilintervalle erhält, die ein ungerades Vielfaches von betragen, sind die -Werte in diesen Intervallen immer noch gleichmäßig verteilt, was wir oben schon für x-Werte gezeigt haben und für -Werte genauso wahr ist. Erinnern wir uns an die Definition des Ausdrucks "gleichmäßig verteilt", welche besagte, dass sich zwei verschiedene -Werte um den gleichen Betrag vom Anfang bzw. Ende des Teilintervalls unterscheiden müssen.

Hier hat das Teilintervall die Länge und in diesem Intervall gibt es, wie gezeigt, immer mindestens zwei Werte, die sich um den gleichen Betrag vom Anfang bzw. Ende dieses Teilintervalls unterscheiden. In allen anderen Teilintervallen verhält es sich gleich. Somit ist die Bedingung 6.11 für alle definierten Winkel >, also für ein u, erfüllt.

Man betrachte ein solches Paar von Winkeln, für die diese Bedingung erfüllt ist:

6.12

Da es sich hierbei also um ein besagtes Paar handelt, gilt auch:

6.13

Falls die Summanden in 6.13 beide gleich 0,5 sind, wird durch 6.12 der arithmetische Mittelwert zwischen Au(x1) und Au(x2) berechnet. Gewöhnlich gilt nicht dieser Spezialfall und die Summanden unterscheiden sich. Dies bewirkt, dass ein gewichteter Mittelwert von Au(x1) und Au(x2) gebildet wird. Es gibt für jedes vier solcher Paare. Gemäß 6.6 wird also die Summe von 4 gewichteten Mittelwerten gebildet und danach halbiert. Das Ergebnis repräsentiert also das doppelte des Mittelwerts der Amplitude für die Frequenz von u, der nicht das arithmetische Mittel sondern ein gewichtetes darstellt.

Es besteht kein offensichtlicher Grund, warum manche x-Werte über alle Frequenzen betrachtet einen stärkeren Einfluss auf die Bestimmung der mittleren Amplitude haben sollten als andere. Dies würde das Ergebnis, das die mittleren Amplituden angibt, verfälschen.

Im Folgenden möchten wir zeigen, dass dies nicht der Fall ist, sondern dass kein x-Wert über alle Frequenzen gesehen, also insgesamt, mehr Gewicht bei der Bestimmung der Durchschnittsamplituden erhält, als ein anderer.

Um sicherzustellen, dass kein x-Wert bevorzugt wird, betrachten wir nun die Funktion für ein feststehendes x und über alle u. Zu diesem Zweck definieren wir x als Parameter und u als Variable. Die Funktion wird dann zu und dementsprechend erhalten wir

,

wobei aus Gründen der Übersichtlichkeit wieder alle g(u) durch ein dargestellt werden.

In der Tabelle kann man erkennen, dass es für jedes x über alle Frequenzen außer u = 0 gesehen die gleichen 7 Werte für g(u) gibt. Über alle u gesehen hat jeder x-Wert also den gleichen Anteil an den mittleren Amplituden. Man erkennt außerdem, dass alle 7 Werte verschieden sind. Eine mathematische Begründung für diese Tatsache findet man hier.

Wie bereits gesehen, gibt es für g(x) immer zwei Phi-Werte, die sich um den gleichen Betrag von 0 bzw. von unterscheiden. Da es nur 7 verschiedene Werte gibt, die g(u) annehmen kann, nimmt g(x) auch nur dieselben 7 verschiedenen Werte an, wenn der Parameter ist; die Funktionen geben schließlich beide die gleichen Werte an, da im Rahmen der Definitionsmenge bei beiden alle u und x durchlaufen werden, wobei einmal der eine Variable ist und einmal der andere. Unter diesen 7 verschiedenen Werten muss es also 3 der oben beschriebenen Paare von g(u) Werten geben, von denen sich jedes zu 1 aufaddiert. Der siebte Wert, welcher 0,5 beträgt liegt bei und ist selbst sein Partner. Der Mittelwert aller dieser Werte ist deshalb

.

Es ist nun also gezeigt, dass jeder f(x)-Wert im Durchschnitt mit der gleichen Gewichtung in die Bestimmung der mittleren Amplituden eingeht, nämlich 0,5. Mit 8 Au(x) pro u erhält man durch Aufsummierung, wie in 6.6 vorgeschrieben also das Vierfache einer mittleren Amplitude.

Das bedeutet also, dass über alle Frequenzen die einzelnen Amplituden für ein x eine mittlere Gewichtung von 0,5 in einem Wertepaar erreichen, obwohl sie gegenüber den Amplituden anderer x-Werte einzelner Frequenzen unterschiedlich gewichtet werden, um die Durchschnittsamplituden zu bestimmen. Das heißt: Im Durchschnitt werden alle x-Werte bei der Berechnung der mittleren Amplituden gleich gewichtet.

Wenn ein gewisser x-Wert an der Bestimmung der mittleren Amplitude für eine bestimmte Frequenz einen geringen Anteil hat, hat er bei einer anderen Frequenz eine große Gewichtung. Diese Erkenntnis ist besonders für die Umkehrung der DCT wichtig, auf die wir in Kapitel 9 näher eingehen.

Für alle ergibt die Summe in 6.6, wie gezeigt, das Vierfache einer mittleren gewichteten Amplitude für die Schwingung der f(x)-Werte. Aus 6.6 wird daher:

.

F(u) ist also das Doppelte der Amplitude der Funktion f(x) für die Frequenz u.

< Kapitel 5 Kapitel 6b >

Die JPEG-Kompression, Kapitel 6a Sebastian Wickenburg, Aeneas Rooch, Johannes Groß 2002