Diskrete Kosinustransformation

Digitale Bilder und Bildkompression

In der Digitalfotographie werden Bilder als Bitmaps aufgenommen und dargestellt: als \(M\times N\) -Raster von quadratischen Bildelementen (Pixeln), wobei \(M\) die Breite und \(N\) die H├Âhe des Bildes in Pixeln ist.

Ausschnitt

Jeder einzelne Pixel kann \(2^b\) Werte annehmen, ├╝blicherweise von \(0\) bis \(2^b-1\) f├╝r ein geeignetes \(b\in\mathbb{N}\) . Dabei wird \(b\) als Bittiefe bezeichnet und entspricht der Anzahl von Bits, die f├╝r die Speicherung der Information eines Pixels ben├Âtigt werden. ├ťblicherweise ist \(b=8\) , so dass jeder Pixelwert in genau einem Byte (8 Bits) gespeichert werden kann. Gr├Â├čere Bittiefen von 12, 14 oder 16 werden f├╝r h├Âherwertige Fotographie und Druck oder Anwendungen in der Medizin und Astronomie verwendet.

Bei einer Bittiefe von 8 liegen Werte dann im Intervall [0,255], wobei in einem Graustufenbild 0 schwarz und 255 wei├č entspricht.

Pixelraster (Graustufen)

Ein Farbbild hingegen setzt sich aus mehreren Pixelrastern zusammen, n├Ąmlich einem pro Farbkanal. Im Fall von RGB hat man also drei Pixelraster, jeweils eins f├╝r Rotwerte, eins f├╝r Gr├╝nwerte und eins f├╝r Blauwerte:

Pixelraster (RGB)

JPEG arbeitet mit dem Farbraum YCbCr, teilt die Informationen eines Bildes also in drei Kan├Ąle auf: Y f├╝r die Grundhelligkeit, Cb f├╝r Chroma Blau (Farbintensit├Ąt auf der Achse Blau-Gelb) und Cr f├╝r Chroma Rot (Farbintensit├Ąt auf der Achse Rot-Gr├╝n).

Farbbild Farbbild: Y-Kanal Farbbild: Cb-Kanal Farbbild: Cr-Kanal

Zerlegung eines Bildes in die einzelnen YCbCr-Kan├Ąle. Oben links sieht man das Originalbild, oben rechts die Grundhelligkeit (Y), unten links die Blau-Gelb-Chroma (Cb) und unten rechts die Rot-Gr├╝n-Chroma (Cr).

Diese Darstellung von Bildern eignet sich allerdings schlecht f├╝r ihre Speicherung und ├ťbertragung, da die Menge der daf├╝r ben├Âtigten Daten vor allem bei h├Âheren Aufl├Âsungen sehr umfangreich ist. Eine ├╝bliche Monitoraufl├Âsung von 1920x1200, zum Beispiel, entspricht einem Raster von 786.432 Pixeln. Bei einem Farbbild mit drei Kan├Ąlen sind das 2.359.296 Werte, f├╝r die je ein Byte ben├Âtig wird, man ist also bei einer Dateigr├Â├če von mehr als 2 MB. Bei Digitalkameras ist man schnell in der Gr├Â├čenordnung von 40 Megapixeln, was einer ungef├Ąhren Dateigr├Â├če von 115 MB pro Bild entspricht.

Um effizient mit Bilddaten arbeiten zu k├Ânnen, will man sie daher komprimieren, d.h. in eine kompaktere Darstellung ├╝berf├╝hren, die weniger Daten ben├Âtigt und dann zur Speicherung und ├ťbertragung verwendet werden kann. Um das Bild schlie├člich wieder darzustellen, wird die komprimierte Darstellung zur├╝ck in ein Bildraster ├╝berf├╝hrt.

Diagramm Bildkompression

Bei einer verlustfreien Kompression ist die dekodierte Darstellung exakt die gleiche wie die urspr├╝ngliche Darstellung vor der Kodierung, es gehen also keine Informationen verloren. Will man eine hohe Kompressionsrate erreichen, ist das allerdings oft nur mit einer verlustbehafteten Kompression m├Âglich. Bei der Kodierung gehen dann Informationen verloren, die bei der Dekodierung nur ann├Ąherungsweise wieder hergestellt werden k├Ânnen; das rekonstruierte Bild entspricht also nicht exakt dem Originalbild.

Das Ziel bei der Bildkompression ist es nun, eine m├Âglichst hohe Kompressionsrate bei m├Âglichst guter Bildqualit├Ąt zu erreichen, also m├Âglichst wenig Informationen speichern oder ├╝bertragen zu m├╝ssen, ohne dass der Unterschied zwischen Originalbild und rekonstruiertem Bild visuell wahrnehmbar ist. JPEG ist ein sehr weit verbreiteter Kompressionsstandard, der genau das schafft: Das oben erw├Ąhnte Beispielbild von reichlich 2 MB ben├Âtigt als JPEG in guter Bildqualit├Ąt nur noch ungef├Ąhr 0,2 MB.

Ein wesentlicher Teil des Algorithmus hinter JPEG besteht darin, das Bild zuerst in eine Darstellung zu transformieren, die im Gegensatz zum Pixelraster sehr effizient komprimiert werden kann. Dazu wird das Bildraster zuerst in Bl├Âcke zerlegt. Jeden Block kann man als Vektor darstellen, der dann auf einen anderen Vektor angebildet wird, der die visuell relevanten Informationen in einen wenigen Elementen konzentriert (Diskrete Kosinustransformation). Alle anderen Elemente werden bei der Kompression dann fallengelassen (Quantisierung und Kodierung).

Diagramm JPEG-Bildkompression

Im Fall eines Farbbildes werden die Farbkan├Ąle prinzipiell gleich verarbeitet, man kann aber die Kompressionsrate f├╝r jeden Farbkanal unterschiedlich w├Ąhlen. Zum Beispiel ist die menschliche Wahrnehmung sehr viel sensitiver f├╝r Grundhelligkeit als f├╝r Chroma, weswegen man f├╝r den Y-Kanal eine h├Âhere Abtastrate und geringere Kompressionsrate w├Ąhlt, w├Ąhrend man f├╝r Cb und Cr mit einer geringeren Abtastrate und gr├Â├čeren Kompressionsrate davonkommt.

Vektordarstellungen von Pixelrastern

Wir wollen im Folgenden nur einen Kanal betrachten, also entweder ein Graustufenbild oder nur einen der Kan├Ąle eines Farbbildes. Mathematisch ist es egal, welchen wir w├Ąhlen, da alle Kan├Ąle mit denselben \(2^b\) Werten arbeiten und in Bezug auf die hier betrachteten Transformationsschritte gleich behandelt werden.

Der erste Schritt bei der JPEG-Kompression ist ein sogenannter Level Shift, der die Werte mithilfe einer Abbildung von \([0,2^b - 1]\) auf \([-2^{b-1},2^{b-1} - 1]\) so verschiebt, dass die 0 zentriert ist; im Fall von \(b=8\) von [0,255] auf [-127, 128].

Pixelraster (Graustufen) ----> Pixelraster (Graustufen)

Au├čerdem wird nicht mit dem Bildraster als Ganzem gearbeitet. Statt dessen wird das Raster zun├Ąchst in 8x8-Bl├Âcke zerlegt. (Ist die H├Âhe oder Breite des Bildes nicht durch 8 teilbar, wird das Pixelraster um entsprechend viele Reihen oder Spalten erweitert, die am Ende wieder entfernt werden.) Alle Verarbeitungsschritte werden getrennt auf jeden dieser Bl├Âcke angewendet.

Solche 8x8-Bl├Âcke lassen sich mathematisch als 8x8-Matrix darstellen - oder einfacher als 64-elementige Vektoren, also Elemente im Raum \(\mathbb{R}^{64}\) . (Im Prinzip reicht hier auch \(\mathbb{Z}^{64}\) , aber f├╝r die Koeffizientendarstellung sp├Ąter brauchen wir reelle Werte.)

Der Einfachheit halber betrachten wir aber vorerst nur eine Dimension, nur die Zeilen der Bl├Âcke, d.h. Vektoren im \(\mathbb{R}^{8}\) . Die Erweiterung auf zwei Dimensionen ist am Ende unkompliziert.

Vektor als Linearkombination bez├╝glich der kanonischen Basis

Die kanonische Basis des \(\mathbb{R}^{8}\) ist:

$$e_1 = \begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\end{pmatrix}$$ $$e_2 = \begin{pmatrix}0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\end{pmatrix}$$ $$\vdots$$ $$e_8 = \begin{pmatrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\end{pmatrix}$$

Eine Zeile eines 8x8-Blocks eines Bildrasters kann als eine Linearkombination dieser Einheitsvektoren dargestellt werden.

$$\begin{pmatrix}121 & 127 & 128 & 125 & 88 & 14 & -40 & -60\end{pmatrix}$$ $$= 121\,e_1 + 127\,e_2 + 128\,e_3 + 125\,e_4 + 88\,e_5 + 14\,e_6 - 40\,e_7 - 60\,e_8$$

Da die genaue Abmessung der Bl├Âcke keine Rolle spielt, werden wir im Folgenden allgemein von Vektoren im \(\mathbb{R}^{N}\) reden (und im zweidimensionalen Fall dann schie├člich im \(\mathbb{R}^{N\cdot N}\) ).

Eine Vektordarstellung bez├╝glich der kanonischen Basis erfasst die r├Ąumliche Verteilung von Graustufen- bzw. Farbwerten. Sie hat allerdings einen entscheidenden Nachteil: Sie l├Ąsst sich nur schwer komprimieren, da die f├╝r das Bild wichtigen Informationen wenig Redundanzen aufweisen, ├╝ber den gesamten Vektor verteilt sind und diese Verteilung keinen statistischen Gleichm├Ą├čigkeiten folgt.

Die Grundidee des JPEG-Standards ist deswegen, den r├Ąumlichen Vektor in einem ersten Schritt auf einen Vektor abzubilden, der die f├╝r die menschliche Wahrnehmung wesentlichen Informationen des Bildes in einigen wenigen Elementen konzentriert. Die restlichen Elemente, die visuell weniger gut wahrnehmbare Informationen erfassen, k├Ânnen dann bei der Kompression verlorengehen. Dadurch l├Ąsst sich die Menge der zu speichernden Informationen deutlich verringern, w├Ąhrend der Informationsverlust bei der Rekonstruktion des Bildes kaum sichtbar ist.

Diese Transformation selber komprimiert aber noch nicht; das Ziel ist lediglich eine Darstellung des Bildes zu erhalten, die sich im n├Ąchsten Schritt gut komprimieren l├Ąsst, ohne die Qualit├Ąt des rekonstruierten Bildes wahrnehmbar zu beeintr├Ąchtigen.

Vektor als St├╝tzstellendarstellung einer kontinuierlichen Funktion

Bisher haben wir einen Vektor \(p = \begin{pmatrix} p_0 & p_1 & \ldots & p_{N-1}\end{pmatrix}\) in \(\mathbb{R}^{N}\) bez├╝glich der kanonischen Basis. Einen solchen Vektor k├Ânnen wir als St├╝tzstellendarstellung einer kontinuierlichen, stetigen Funktion \(f\) verstehen. Das bedeutet, dass der Vektor \(p\) f├╝r \(i = 0,\ldots, N-1\) genau die Funktionswerte \(p_i = f(x_i)\) der Funktion an den St├╝tzstellen \(x_0,\ldots,x_{N-1}\) enth├Ąlt.

Im Fall unseres Beispielvektors \(\begin{pmatrix}121 & 127 & 128 & 125 & 88 & 14 & -40 & -60\end{pmatrix}\) kennen wir also folgende Werte an den St├╝tzstellen \(i=0,\ldots,7\) .

St├╝tzstellen

Bekannt sind also nur \(N\) Werte der Funktion \(f\) in einem beschr├Ąnkten Intervall. Um die Menge der m├Âglichen Funktionen, die diese Werte durchlaufen, so weit einzuschr├Ąnken, dass wir praktisch damit weiterarbeiten k├Ânnen, treffen wir ein paar zus├Ątzliche Annahmen.

Zun├Ąchst nehmen wir an, dass die zugrundeliegende kontinuierliche Funktion \(f\) periodisch ist, mit einer Periode von \(2N\) , so dass unsere bisherige St├╝tzstellendarstellung \(p\) genau eine halbe Phase dieser periodischen Funktion abdeckt. Eine Fortsetzung der Funktion erhalten wir, indem wir die gebenenen Werte zu beiden Seiten unseres Intervalls spiegeln. Hier gibt es mehrere M├Âglichkeiten; f├╝r JPEG relevant ist eine Spiegelung achsensymmetrisch zur y-Achse in den Punkten zwischen den St├╝tzstellen. Wir erweitern die Funktion also in beide Richtungen als gerade Funktion, d.h. so dass \(f(-x)=f(x)\) , und so dass sich die Randpunkte unseres urspr├╝nglichen Vektors wiederholen.

St├╝tzstellen

Wir nehmen also an, dass unser diskreter Vektor \(p\) die Werte einer kontinuierlichen, periodischen, geraden Funktion \(f:\mathbb{R}\to\mathbb{R}\) an \(N\) St├╝tzstellen darstellt.

Vektor als Koordinatendarstellung bez├╝glich Kosinusbasisfunktionen

Die zugrundeliegende Funktion kennen wir nicht genau, aber aufgrund der ├╝ber diese Funktion getroffenen Annahmen wissen wir, dass sie als Reihe von gewichteten Kosinusfunktionen dargestellt werden kann (mit Koeffizienten \(c_k\in\mathbb{R}\) ): $$f(x) = \sum_{k=0}^\infty c_k\cos(kx)$$

F├╝r unseren Anwendungsfall interessiert uns allerdings nicht die ganze Reihe. Da wir eine endliche Darstellung, idealerweise wieder eine Vektordarstellung im \(\mathbb{R}^N\) , suchen, beschr├Ąnken wir uns auf die \(N\) -elementige Partialsumme \(\sum_{k=0}^{N-1} c_k\cos(kx)\) . Wir approximieren die zugrundeliegende Funktion \(f\) also durch ein trigonometrisches Polynom.

Wo genau liegen nun die St├╝tzstellen? Da \(\cos(x)\) eine Periode von \(2\pi\) hat, wir aber eine Periode von \(2N\) Einheiten annehmen, sind die Abschnitte von einer St├╝tzstelle zur n├Ąchsten \(\frac{2\pi}{2N}=\frac{\pi}{N}\) gro├č (die sogenannte Kreisfrequenz). Die St├╝tzstellen werden au├čerdem um \(\frac{1}{2}\) phasenverschoben und sind statt \(i\frac{\pi}{N}\) demnach \((i+\frac{1}{2})\frac{\pi}{N}\) .

Damit die Kosinusfunktionen \(\cos(kx)\) als Basis unserer Vektordarstellung im \(\mathbb{R}^N\) dienen k├Ânnen, wollen wir sie zus├Ątzlich normalisieren. Dazu skalieren wir sie um folgenden Faktor \(s_k\) : $$s_k = \begin{cases} \sqrt{\frac{1}{N}} & \text{wenn } k=0 \\ \sqrt{\frac{2}{N}} & \text{sonst} \end{cases}$$

Wir definieren also f├╝r Wellenzahlen \(k\in\{0,1,\ldots,N-1\}\) und \(i\in\{0,1,\ldots,N-1\}\) die Basisfunktionen und St├╝tzstellen wie folgt:

$$\text{Basisfunktionen}\colon b_k(x_i)=s_k \cos\left( k x_i \right)$$ $$\text{St├╝tzstellen}\colon x_i = (i+\frac{1}{2}) \frac{\pi}{N}$$

Setzt man die St├╝tzstellen ein, ergibt sich:

$$b_k(x_i)=s_k\cos\left(k\,(i+\frac{1}{2})\frac{\pi}{N}\right) = s_k\cos\left(\frac{(2i+1)k\,\pi}{2N}\right)$$

F├╝r \(N=8\) sehen die Funktionen und St├╝tzstellen damit wie folgt aus. (Die Funktionswerte der Basisfunktionen \(b_k\) an den St├╝tzstellen \(x_i\) werden am Ende unsere neuen Basisvektoren.)

Basisvektoren

Die Funktionswerte \(f(x)\) der Funktion, die unserem St├╝tzstellenvektors zugrundeliegt, lassen sich also als Linearkombination der Basisfunktionen darstellen, mit Koeffizienten \(c_k\in\mathbb{R}\) : $$f(x) \sim c_0 b_0(x) + c_1 b_1(x) + \ldots + c_{N-1} b_{N-1}(x) = \sum_{k=0}^{N-1}c_k s_k \cos(kx)$$

Bei Audiosignalen ist die Intuition hinter einer solchen Darstellung, dass das Signal in Grundschwingungen verschiedener Frequenzen zerlegt werden kann. Bei Bildern hingegen kann man die Basisfunktionen als Kontraste mit steigender Frequenz verstehen (siehe MathWorks' grafische Darstellung der Basisfunktionen). Die Linearkombination gibt dann an, welche Kontraste zu welchem Anteil im Bildraster vorkommen, wobei ein gro├čer Koeffizientenwert bedeutet, dass der Kontrast stark ausgepr├Ągt ist, die Unterschiede zwischen benachbarten Pixeln also relativ gro├č sind.

F├╝r den Anwendungsfall der Kompression interessieren uns nur die Koeffizienten, da die Basisfunktionen fix sind und nicht als Information mit gespeichert und ├╝bertragen werden m├╝ssen. Die Koordinatendarstellung liefert uns damit eine weitere diskrete Darstellung der Bildinformation: Neben der urspr├╝nglichen St├╝tzstellendarstellung eines Pixelrasters $$p=\begin{pmatrix} p_0 & \ldots & p_{N-1} \end{pmatrix}$$ wo die Elemente \(p_i\) die Graustufen- oder Farbwerte an dem r├Ąumlichen Index \(i\) sind, haben wir eine Koeffizientendarstellung $$c=\begin{pmatrix} c_0 & \ldots & c_{N-1} \end{pmatrix}$$ Die Vektorelemente in \(c\) haben dabei keine r├Ąumliche Bedeutung mehr. Entscheidend ist, dass sich in der Koeffizientendarstellung \(c\) die visuell wichtigen Information des Bildes in einigen wenigen Koeffizienten konzentriert. Die Koeffizientendarstellung erlaubt es also prinzipiell, sehr viel mehr Informationen wegzuwerfen als die St├╝tzstellendarstellung, ohne einen deutliche Informationsverlust zu erleiden.

Um das f├╝r die Bildkompression ausnutzen zu k├Ânnen, brauchen wir aber noch eine Abbildung von \(p\) auf \(c\) und umgekehrt.

Diskrete Kosinustransformation

Bisher haben wir zwei Vektordarstellungen in \(\mathbb{R}^N\) betrachtet: eine Darstellung \(p\) bez├╝glich der kanonischen Basis, die wir als St├╝tzstellendarstellung einer zugrundeliegenden Funktion \(f\) interpretiert haben, und eine Koordinatendarstellung \(c\) von \(f\) bez├╝glich einer Basis von Kosinusfunktionen verschiedener Frequenzen. Die Darstellung \(c\) stellt sich dabei als sehr viel besser komprimierbar heraus. Um das nutzen zu k├Ânnen, brauchen wir eine Abbildung von der St├╝tzstellendarstellung \(p\) auf die Koeffizientendarstellung \(c\) und umgekehrt. Beide Darstellungen sind Vektoren im Raum \(\mathbb{R}^N\) und wir werden sehen, dass die Abbildung zwischen ihnen einem Basiswechsel entspricht.

Betrachten wir zuerst die Abbildung eines Koeffizientenvektors \(c\) auf den entsprechenden St├╝tzstellenvektor \(p\) . Dazu berechnen wir den Funktionswert \(f(x_i)\) (eine Linearkombination der Basisfunktionen \(b_k\) ) an den einzelnen St├╝tzstellen \(x_i\) durch Einsetzen:

(1) $$f(x_i) = \sum_{k=0}^{N-1}c_k b_k = \sum_{k=0}^{N-1}c_k s_k\cos(k x_i) = \sum_{k=0}^{N-1}c_k\,s_k \cos(k\,(i+\frac{1}{2})\frac{\pi}{N})$$

Die Funktionswerte \(f(x_i)\) bilden die Elemente des Vektors \(p=\begin{pmatrix} p_0 & \ldots & p_i & \ldots & p_{N-1} \end{pmatrix}\) , der sich also wie folgt zusammensetzt:

$$p_0 = f(x_0) = c_0b_0(x_0) + c_1b_1(x_0) + \ldots + c_{N-1}b_{N-1}(x_0)$$ $$\ldots$$ $$p_i = f(x_i) = c_0b_0(x_i) + c_1b_1(x_i) + \ldots + c_{N-1}b_{N-1}(x_i)$$ $$\ldots$$ $$p_{N-1} = f(x_{N-1}) = c_0b_0(x_{N-1}) + c_1b_1(x_{N-1}) + \ldots + c_{N-1}b_{N-1}(x_{N-1})$$

Der Vektor \(p\) ist demnach das Produkt aus dem Koeffizientenvektor \(c=\begin{pmatrix} c_0 & c_1 & \ldots & c_{N-1} \end{pmatrix}\) und einer Matrix mit den Basisfunktionen als Elemente, die wir \(T\) nennen:

(2) $$p = c\cdot T = \begin{pmatrix} c_0 & c_1 & \ldots & c_{N-1} \end{pmatrix} \cdot \begin{pmatrix} b_0(x_0) & b_0(x_1) & \ldots & b_0(x_{N-1}) \\ \vdots & \vdots & & \vdots \\ b_i(x_0) & b_i(x_1) & \ldots & b_i(x_{N-1}) \\ \vdots & \vdots & & \vdots \\ b_{N-1}(x_0) & b_{N-1}(x_1) & \ldots & b_{N-1}(x_{N-1}) \end{pmatrix}$$

Die Elemente der Matrix \(T\) sind also:

$$T_{ij} = b_i(x_j) = s_i \cos(i\cdot(j+\frac{1}{2})\cdot\frac{\pi}{N}) = \begin{cases} \sqrt{\frac{1}{N}} & \text{ falls } i = 0 \\ \sqrt{\frac{2}{N}}\cos(i\cdot(j+\frac{1}{2})\cdot\frac{\pi}{N}) & \text{ sonst }\end{cases}$$

Die Matrix \(T\) ist orthogonal, d.h. ihre Spaltenvektoren \(t_k,t_l\) sind normalisiert und paarweise orthogonal bez├╝glich dem Standardskalarprodukt des \(\mathbb{R}^N\) : $$\langle t_k,t_l\rangle = t_k^\top t_l= \sum_{n=0}^{N-1} t_{kn} t_{ln} = \begin{cases} 1 & \text{ falls } k=l \\ 0 & \text{ sonst} \end{cases}$$

Die Spaltenvektoren von \(T\) sind demnach linear unabh├Ąngig und bilden eine Orthonormalbasis von \(\mathbb{R}^N\) . Die Matrix \(T\) selber ist also eine Basiswechselmatrix. Aus der Orthogonalit├Ąt von \(T\) folgt, dass sie invertierbar ist, wobei die Inverse \(T^{-1}\) gleich der Transponierten \(T^\top\) ist.

Aus \(p = c\cdot T\) folgt daher \(p\cdot T^{-1} = c\) und damit auch \(p\cdot T^\top = c\) , d.h.:

(3) $$c = \begin{pmatrix} p_0 & \ldots & p_i & \ldots & p_{N-1} \end{pmatrix} \cdot \begin{pmatrix} b_0(x_0) & b_1(x_0) & \ldots & b_{N-1}(x_0) \\ \vdots & \vdots & & \vdots \\ b_0(x_i) & b_1(x_i) & \ldots & b_{N-1}(x_i) \\ \vdots & \vdots & & \vdots \\ b_0(x_{N-1}) & b_1(x_{N-1}) & \ldots & b_{N-1}(x_{N-1}) \end{pmatrix}$$

Daraus ergeben sich die Koeffizienten, die die Vektorelemente von \(c\) bilden, wie folgt:

(4) $$c_i = p_0\,b_i(x_0) + p_1\,b_i(x_1) + \ldots + p_{N-1}\,b_i(x_{N-1})$$ $$= \sum_{k=0}^{N-1} p_k\,b_i(x_k)$$ $$= \sum_{k=0}^{N-1} p_k\,s_i \cos(i\cdot(k+\frac{1}{2})\cdot\frac{\pi}{N})$$

Mit (2) und (3) haben wir Abbildungen \(\mathbb{R}^{N}\to\mathbb{R}^{N}\) zwischen \(p\) und \(c\) , die Diskrete Kosinustransformation II genannt werden.

1D

Im eindimensionalen Fall definiert man die Abbildung \(p\mapsto c\) und ihre Inverse \(c\mapsto p\) ├╝blicherweise als Formel, um aus den Elementen von \(p\) die Elemente von \(c\) zu berechnen und umgekehrt. Diese Formeln ergeben sich direkt aus (1) und (4), nur unter Umbenennung von Indizes, wobei \(i,\in\{0,\ldots,N-1\}\) jeweils Vektorindizes sind:

$$p_i = \sum_{k=0}^{N-1}c_k\,s_k\cos(k\cdot(i+\frac{1}{2})\cdot\frac{\pi}{N})$$ $$c_k = \sum_{i=0}^{N-1}p_i\,s_k\cos(k\cdot(i+\frac{1}{2})\cdot\frac{\pi}{N})$$

2D

Der zweidimensionale Fall l├Ąsst sich auf den eindimensionalen Fall zur├╝ckf├╝hren, indem beide Dimensionen getrennt transformiert werden. Das Bildraster \(P\) ist eine \(N\times N\) -Matrix, deren Zeilenvektoren die Vektoren \(p\) sind. Zun├Ąchst werden diese Zeilenvektoren eindimensional transformiert, indem man sie mit \(T^\top\) multipliziert. Das Ergebnis ist eine \(N\times N\) -Matrix \(A = P\cdot T^\top\) . Um die Spalten auf die gleiche Weise zu transformieren, transponiert man diese Matrix \(A\) , multipliziert sie erneut mit \(T^\top\) und transponiert sie anschlie├čend wieder zur├╝ck. Das Ergebnis ist die Matrix \(C=(A^\top\cdot T^\top)^\top = T\cdot A\) , deren Elemente nun Koeffizienten sind. Aus \(C = T\cdot A\) und \(A = P\cdot T^\top\) ergibt sich direkt, dass: $$C = T\cdot P\cdot T^\top$$

Die zweidimensionale Formel f├╝r die Berechnung von Elementen \(C_{ij}\) der Koeffizientenmatrix aus Elementen \(P_{xy}\) der Bildmatrix und umgekehrt entspricht dann einer Hintereinanderausf├╝hrung der entsprechenden eindimensionalen Formeln, wobei \(i,j,x,y\in\{0,\ldots,N-1\}\) jeweils Vektorindizes sind:

$$P_{xy} = \sum_{i=0}^{N-1}\sum_{j=0}^{N-1} C_{ij}\,s_x\, s_y\, \cos(x\cdot(i+\frac{1}{2})\cdot\frac{\pi}{N})\, \cos(y\cdot(j+\frac{1}{2})\cdot\frac{\pi}{N})$$ $$C_{ij} = \sum_{x=0}^{N-1}\sum_{y=0}^{N-1} P_{xy}\,s_x\, s_y\, \cos(x\cdot(i+\frac{1}{2})\cdot\frac{\pi}{N})\, \cos(y\cdot(j+\frac{1}{2})\cdot\frac{\pi}{N})$$

Da die Basisfunktionen im Voraus berechnet werden k├Ânnen, ist die Transformation insgesamt effizient berechenbar.

Beispiel

Betrachten wir das Pixelraster vom Beginn:

Pixelraster (Graustufen)

Nach Anwendung der Diskreten Kosinustransformation bekommen wir ein Raster von Koeffizienten, in dem sich gro├če Werte vor allem links oben konzentrieren:

$$\begin{array}{rrrrrrr} 441.4 & 313.7 & -10.6 & 27.5 & -6.5 & -2.6 & 0.4 & -4.0 \\ 539.2 & -236.3 & -61.2 & -11.5 & -5.6 & 5.4 & -0.3 & 5.0 \\ -175.5 & -86.2 & 124.0 & 3.4 & 9.1 & -3.6 & 0.9 & -2.7 \\ 17.8 & 136.7 & -30.0 & -42.8 & 5.4 & -8.3 & 3.5 & 0.0 \\ -26.1 & -44.0 & -45.2 & 23.8 & 11.0 & 0.6 & -3.0 & 1.8 \\ 20.6 & 20.0 & 16.4 & 21.1 & -16.4 & 1.3 & 0.4 & -4.1 \\ -12.3 & -17.8 & -2.9 & -8.3 & -9.2 & 5.3 & 2.1 & 5.0 \\ 8.5 & 3.8 & 9.5 & -11.3 & 15.8 & -3.1 & -5.9 & -0.2 \end{array}$$

Der Informationsverlust passiert nun im n├Ąchsten Schritt der Quantisierung. Das Ziel ist es, Koeffizienten nur so pr├Ązise wie n├Âtig zu speichern. Kleine Koeffizienten, zum Beispiel, spielen f├╝r die visuelle Wahrnehmung kaum eine Rolle. Dazu werden nun alle Koeffizienten \(C_{ij}\) mit einer Schrittgr├Â├če \(Q_{ij}\) geteilt und ganzzahlig gerundet:

$$C'_{ij}=\text{round}_\text{int}(\frac{C_{ij}}{Q_{ij}})$$

Die Schrittwerte werden einer Quantisierungstabelle entnommen und bestimmen, wie gro├č der Informationsverlust und damit auch die Kompressionsrate (und letztendlich die Bildqualit├Ąt) ist. Intuitiv entspricht die Schrittgr├Â├če einem Wahrnehmungsschwellwert: bis zu welchem Koeefizienten man den Beitrag der entsprechenden Basisfunktion visuell wahrnehmen kann.

Je nachdem, welche Tabelle des JPEG-Standards man anwendet, ergeben sich zum Beispiel diese Raster:

$$\begin{array}{r} 28 & 29 & -1 & 2 & 0 & 0 & 0 & 0 \\ 45 & -20 & -4 & 0 & 0 & 0 & 0 & 0 \\ -13 & -7 & 8 & 0 & 0 & 0 & 0 & 0 \\ 1 & 8 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 6 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \qquad \begin{array}{r} 26 & 17 & 0 & 0 & 0 & 0 & 0 & 0 \\ 30 & -11 & -2 & 0 & 0 & 0 & 0 & 0 \\ -7 & -3 & 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}$$

Ordnet man diese Werte nun nach folgendem Muster, bekommt man eine Reihe, in der die Elemente so geordnet sind, dass die von Null verschiedenen Elemente am Anfang stehen und man einen Gro├čteil der Information nicht mehr speichern muss.

Basisvektoren

Um die Quantisierung beim Dekodieren wieder r├╝ckg├Ąngig zu machen, multipliziert man die Werte mit der Schrittgr├Â├če: \(C_{ij}=C'_{ij}Q_{ij}\) . Die Koeffizientenraster, die man so rekonstruiert, entsprechen aufgrund des Informationsverlustes nicht exakt den urspr├╝nglichen Koeffizienten, aber rekonstruiert man daraus wieder ein Pixelraster, ist der Unterschied visuell nur bei hoher Kompressionsrate sichtbar.

Zumindestens gilt das f├╝r nat├╝rliche Bilder, wo ├ťberg├Ąnge auf Pixelebene flie├čend sind. Denn die Quantisierungstabellen gehen von der Annahme aus, dass sehr harte ├ťberg├Ąnge von einem Pixel zum n├Ąchsten nicht vorkommen. Ist das in einer Bitmap der Fall, z.B. bei Textdokumenten, dann sind die Informationen gleichm├Ą├čiger ├╝ber die Koeffizienten verteilt, was dazu f├╝hrt, dass bei der Kompression f├Ąlschlicherweise auch f├╝r die Wahrnehmung relevante Informationen weggeworfen werden, was dann sichtbare Fehler bei der Rekonstruktion (sogenannte JPEG-Artefakte) zur Folge hat.

Referenzen

Berner, Julius: Diskrete Kosinustransformation in der Bildverarbeitung. BSc Thesis, Universit├Ąt Wien, 2016.

Burger, Wilhelm und Mark James Burge: Digitale Bildverarbeitung. Springer eXamen.press, 2006.

Pound, Mike: Discrete Cosine Transform (JPEG Pt2). YouTube, 2015.

Lang, Hans Werner: Diskrete Cosinus-Transformation (DCT). Hochschule Flensburg, 2005.

Wallace, Gregory K. The JPEG Still Picture Compression Standard. IEEE Transactions on Consumer Electronics, 38(1), 1992.