Auf diese Frage wird man spontan die Antwort erhalten, dass JPEG das Dateiformat ist, das neben GIF zur Darstellung von Bildern im Internet verwendet wird. Warum JPEG dafür so gut geeignet ist und dass es eigentlich noch viel mehr als nur ein Dateiformat ist, soll in der folgenden Ausarbeitung gezeigt werden. Zunächst aber erst einmal, was JPEG bedeutet und wie es zu Stande kam.
JPEG ist die Abkürzung für Joint Photographic Expert Group, die 1988 zusammen kam, um erstmals einen Standard zur Kompression von digitalen Standbildern zu erarbeiten. Das Ergebnis wurde 1993 unter der Bezeichnung ISO 10918 als Standard definiert.
Das Wort Joint steht für die Zusammenarbeit zwischen CCITT (International Telegraph and Telephone Consultative Commitee) und ISO/IEC (International Organization for Standardization/International Electronical Commission).
JPEG verfolgte das Ziel, eine Bildkompression mit
zu schaffen.
Im JPEG-Standard gibt es nicht einen alles könnenden Algorithmus zur Kompression von Standbildern, sondern verschiedene, die im wesentlichen zwei Kompressionsverfahren möglich machen:
Unter velustbehafteter Kompression versteht man nicht zwangsläufig, dass das dekodierte Bild Qualität verloren hat (was natürlich bei sehr hohen Kompressionsrate nicht ausbleibt), sondern vielmehr, dass Daten bei der Kompression verloren gehen. Die dekodierten Daten entsprechen nämlich nicht exakt den ursprünglichen Daten die kodiert wurden. Es handelt sich eigentlich um Information, die verloren geht. Um beim Dekodieren trotz dieser Informationsverluste Bilder akzeptabler Qualität rekonstruieren zu können, suchte die JPEG-Kommision nach geeigneten Hilfsmitteln.Als besonders gut geeignet erwies sich die Diskrete Kosinus Transfomation DCT. Sie spielt die zentrale Rolle im "Baseline Codec", der der kleinste gemeinsamen Nenner der verschiedene Modi ist. Der "Baseline Codec" setzt sich aus folgende Schritten zusammen:
Die YUV-Komponenten lassen sich leicht mit gewichteten Summen aus den RGB-Werten errechnen:
| Y= 0,299 R + 0,587 G + 0,114 B |
| V = R - Y |
| U = B - Y |
Man sieht, dass die Farben nicht zu gleichen Teilen in die Formel eingehen, was daran liegt, dass das Auge des Menschen zum Beispiel für Grün sehr empfindlich ist. Aus diesem Grund ist der Faktor der Grünkomponente bei der Berechnung von Y auch am höchsten.
Mit dem gleichen Y arbeitet auch das YCbCr-Farbmodell. In den 2 Komponenten Cb und Cr werden jedoch jeweils die Abweichungen vom Grau zum Blau- bzw. Rotwert gespeichert.
Die Diskrete Cosinus Transformartion DCT
Die DCT besitzt nun 64 Basisfunktion, die jeweils aus 8x8 Pixeln bestehen. Nimmt man jede dieser Funktionen als 64-stelligen Vektor, bilden diese 64 Vektoren eine Orthonormalbasis bezüglich eines Vektorraums. Wird der zu kodierende Block nach einer Basistransformation durch die DCT bezüglich der eben beschrieben Basis dargestellt, erhält man 64 Koeffizienten, die angeben, wie stark die einzelnen Basisfunktionen an dem zu kodierende Block beteiligt sind. Diese Koeffizienten heißen DCT-Koeffizienten, und werden folgendermaßen berechnet:
 | mit x,y=0...7 und u,v=0...7 |  |
| x, y bezeichnen die Koordinaten innerhalb des zu kodierenden Blockes; u, v sind die Koordinaten der Basisfunktionen der DCT | ||
Betrachtet man die Basisfunktionen der 2-dimensionalen DCT, die eigentlich ein Produkt zweier eindimensionaler DCT ist, stellt man fest, dass sich in der linken oberen Ecke die einzige konstante Basisfunktion befindet. Der Koeffizient dieser Funktion, deren Frequenz in beiden Dimensionen Null ist, heißt DC-Koeffizient (direct-current terms), während die übrigen 63 Koeffizienten AC-Koeffienten (alternating-current terms) heißen.
Bis zu diesem Zeitpunkt wurde noch keine Kompression der Daten erreicht, sie wurden lediglich für die anschließende Kompression konditioniert.
Quantisierung
Im eigentlich verlustbehafteten Prozeß der Quantisierung werden die 64 DCT-Koeffizienten nun dividiert und das Ergebnis auf eine ganze Zahl gerundet. Die Division geschieht anhand einer Quantisierungstabelle, die die Farb- und Helligkeitsempfindlichkeit des Auges berücksichtigt. Das menschliche Auge reagiert auf niedrige Frequenzen viel empfindlicher als auf hohe. Die Koeffizienten höherer Frequenzen werden deshalb durch höhere Zahlen geteilt als die der niedrigeren. Hiermit erreicht man, dass sich der Wertebereich verkleinert. Viele Koeffizienten werden auch zu Null.
 | u, v wie oben |
Da die Art der Quantisierung nicht fest vorgeschrieben ist, kann an dieser Stelle die Qualität des Bildes, durch die Wahl der Quantisierungstabelle mitbestimmt werden. Diese Tatsache bewirkt aber auch, dass die verwendete Quantisierungstabelle mit abgespeichert und dem Dekodierer mitgeschickt werden muss.
DCT-Koeffizienten
Nach der Quantisierung werden die DC- und AC Koeffizienten getrennt voneinader betrachtet.
Da nämlich aufgrund der starken Korrelation, die zwischen benachbarten 8x8-Blöcken herrscht, speichert man nicht nicht in jeden Block den DC-Koeffizienten unababhängig, sondern berechnet die Differenz zum vorherigen Block und speichert diese.
Im letzen Kodierschritt werden dann die DCT Koeffizienten kodiert, wodurch noch eine weitere Kompression (ohne Verluste) erreicht wird. Die geschieht, indem man die charakteristische Verteilung der DCT-Basisfunktionen ausnutzt. Zur Kodierung werden Codes mit variablen Längen verwendet wie Variable-Length-Integers (VLI) und Huffmann Codes (VLC).
VLI werden wie in der Grafik dargestellt, je größer also die Zahl ist, desto mehr Bits werden für ihre Darstellung benötigt. Im Gegensatz zu Huffman Codes basieren die VLI nicht auf statistischen Werten, sondern werden immer gleich codiert.
| Größe | Amplitude |
|---|---|
| 1 | -1,1 |
| 2 | -3,-2,2,3 |
| 3 | -7..-4,4..7 |
| 4 | -15..-8,8..15 |
| 5 | -31..-16,16..31 |
| 6 | -63..-32,32..63 |
| 7 | -127..-64,64..127 |
| 8 | -255..-128,128..255 |
| 9 | -511..-256,256..511 |
| 10 | -1023..-512,512..1023 |
Nun macht man sich die oben bereits beschrieben längeren Nullketten, die dann von einem von Null verschiedenen AC-Koeffizienten gefolgt werden, zu Nutzen. Anstatt nämlich jeden Koeffizenten einzeln zu speichern, wird jeder AC-Koeffizient, der nicht Null ist, in Kombination mit der Anzahl der Nullen, die ihm vorausgegangen sind, angegeben.
Dies geschieht mit Hilfe von 2 Symbolen:
| Symbol 1: | (Länge, Größe) |
| Symbol 2: | (Wert) |
Das erste Symbol enthält die Länge der Nullfolge und die Anzahl der Bits, die benötigt werden, um Symbol 2 darzustellen.
In Symbol 2 ist dann der AC-Koeffizient als VLI gespeichert. Für die Kodierung von Symbol 1 wird ein Huffman-Code verwendet.
ähnlich wird auch die Kodierung des DC-Koeffizienten, bzw. der errechneten Differenz vorgenommen.
| Symbol 1: | (Größe) |
| Symbol 2: | (Wert) |
Neben einen abweichenden Symbol 1 wird auch eine andere Huffmann-Tabelle verwendet
Neben der Huffmann-Codierung ist es möglich, die Koeffizienten mit arithmetischen Codes zu kodieren. Dadurch ist es möglich, eine 5-10% stärkere Komprimierung erreichen. Da die arithmetischen Codes allerdings patentiert sind, stellt sich die Frage, ob es sich für diese vergleichsweise geringen Dateneinsparungen lohnt, Gebühren zu bezahlen.
Die Quantisierungstabellen und die Tabellen für die Huffmann-Codierung sind nicht fest vom JPEG-Standard vorgegeben, was einerseits eine Flexibiltät bei der Kompression bedeutet, andererseits aber auch, dass diese Tabellen immer mit dem komprimierten Bild mitgeschickt werden müssen.
Dekodierung
Bei der Dekodierung werden alle Schritte des Kodierens in invertierter Reihenfolge rückgängig gemacht.
 | mit u,v=0...7 |
Nach Anwendung der inversen Diskreten Cosinus-Transformation kann das Bild jetzt rekronstruiert werden.
 | mit u,v=0...7 und x,y=0...7 |
Dies ist also die generelle Funktionsweise des JPEG-Algorithmus, der auf der DCT basiert. Da der Standard jedoch nicht allzu genau festgelegt ist, bleibt viel Raum für verschiedene Implementationen.
Sequentielles Kodieren
Bei dieser auf DCT-basierenden Methode werden die 8x8 Blöcke von links nach rechts und Reihe für Reihe von oben nach unten gelesen. So baut sich dann auch das Bild beim Dekodieren auf.
Progressives Kodieren
Diese Methode arbeitet die Blöcke in der gleichen Reihenfolge wie oben ab, wenn auch in mehreren Durchläufen. Um dies zu realisieren, muss zwischen Quantisierung und Kodierung noch ein Speicher (memory buffer) eingebaut werden. Die Koeffizienten jedes transformierten und quantisierten Blocks werden dort gespeichert und in den verschiedenen Durchläufen, je nach Wichtigkeit kodiert. So kann das Bild beim Dekodieren in schlechter Qualität aufgebaut werden. Diese Qualität verbessert sich dann in mehreren Schritten bis zum gewünschten Ergebnis.
Hierarchisches Kodieren
Das hierarchische Verfahren arbeitet nach dem Prinzip des progressiven Verfahren und kodiert die Bilder in einer Pyramidenstruktur. Man verwendet es vor allem für Bilder, mit hohen Auflösungen oder in Umgebungen, die verschiedene Auflösungen darstellen können. Für Details möchte ich auf den Artikel von G.K. Wallace [1] sowie die übrige angegebene Literatur verweisen.
Im ersten Teil wurden bereits die Farbformate angesprochen, aber in der Erklärung der grundlegenden JPEG-Funktionsweise nicht weiter berücksichtigt. Es wurde nämlich vereinfachend angenommen, dass das Bild nur aus einer einzigen Komponente besteht.
Die vorgestellten Farbmodelle allerdings besitzen aber alle 3 verschiedene Komponenten, die sich gut zur Kompression eigenen. Da der Standard aber keine festen Vorgaben macht, können Bilder aus bis zu 255 Komponenten bestehen. Im Folgenden wird erklärt werden, wie diese verarbeitet werden.
Jede Komponente besteht aus einem rechteckigen Feld von Farbwerten. Ein Farbwerte wird durch ein ganzzahligen Wert ohne Vorzeichen definiert, der in einem Bereich von [0, 2P - 1], mit einer Genauigkeit P liegt. Diese Genauigkeit muss bei allen Farbwerten aller Komponenten gleich sein und liegt beim Baseline Codec bei 8 Bit.
Die i-te Komponente hat die Abtastgrößen xi und yi. Da aber verschiedene Komponenten mit verschiedenen Raten abgetastet werden können, kann es zu Komponenten mit verschiedenen Größen kommen. Diese Größen müssen nun in Einklang gebracht werden, was mit folgender Formel geschieht:
Nimmt man beispielsweise ein Bild mit drei Kompenenten, dessen Größe 512 Zeilen und 512 Reihen beträgt und die Komponenten folgende Abtastraten haben:
| C0 | H0=4, | V0=1 |
| C1 | H1=2, | V1=2 |
| C2 | H2=1, | V2=1 |
Dann lassen sich mit X=512, Y=512, Hmax=4 und Vmax=2 folgende xi bzw. yi berechnen
| C0 | x0=512, | y0=256 |
| C1 | x1=256, | y1=512 |
| C2 | x2=128, | y2=256 |
Zur Verdeutlichung der Komponenten sollen die folgenden Grafiken dienen.
Bevor ich nun den Aufbau der Datenströme beschreibe, sollte noch der Begriff der Dateneinheit geklärt werden. Bei den auf der DCT-basierenden JPEG-Algorithmen beschreibt eine Dateneinheit einen 8x8 Block.
Die Art der Kodierung der Daten des Bildes hängt im Wesentlichen davon ab, wieviele Bildkomponenten in einem Durchgang codiert werden. Hier gibt es zwei Möglichkeiten, die sogenannte "non-interleaved"- und "interleaved" - Reihenfolge
"non-interleaved"- Reihenfolge
In einem Durchlauf wird nur eine Komponente codiert, indem alle Dateneinheiten einer Komponenten nach unten gezeigtem Schema von links nach rechts und von oben nach unten abgearbeitet werden. Im zweiten Durchgang geschieht das Gleiche mit der nächsten Komponente. Die minimal-codierten Einheiten (Minimum coded unit: MCU), zu der Dateneinheiten zusammengefasst werden, ist bei "non-interleaved" Daten genau eine Data unit
Bei der "interleaved" - Reihenfolge werden pro Durchlauf mindestens zwei Komponenten kodiert, indem jede Bildkomponente Ci in rechteckige Felder mit Hi horizonztalen und Vi vertikalen Dateneinheiten zerlegt wird.Wie groß die MCU bei dieser Reihefolge ist und wie sie sich zusammensetzt, hängt von den Abtastfaktoren der Komponenten ab. Das Prinzip sollte mit folgender Grafik deutlich werden.
Wie schon öfter erwähnt, ist der JPEG-Standard sehr großzügig gehalten, um seinen Ansprüchen gerecht zu werden. Eventuelle Skepsis, dieser Standard sei wegen seiner Komplexität sehr unübersichtlich, wird dadurch aufgehoben, dass vielmehr eine Art Baukasten mit vielen Hilfsmitteln geboten werden soll, der je nach Bildbeschaffenheit, eine optimale Kodiermöglichkeit bieten soll.
Dabei wurde der "lossless mode" viel mehr als zur Vervollständigung der Palette aufgenommen, denn die Stärken von JPEG liegen unbestritten in den Methoden, die mit der DCT arbeiten. Hier können je nach Bildbeschaffenheit Kompressionsraten bis zu 10:1 bis 60:1 erreicht werden ohne, dass ein Qualitätsverlust für das Auge sichtbar wird.
Man muss allerdings sagen, dass JPEG zur Kompression von Bildern mit fliessenden Übergängen, wegen der geringeren Helligkeits- und Farbunterschieden besser geeignet ist als zur Kompression von schwarzweissen und farbigen Bildern mit harten übergängen und starken Kontrasten.
| [1] | Gregory K. Wallace: The JPEG Still Picture Compression Standard, in: Communications Of The ACM, April 1991, Vol. 34, No. 4 |
| [2] | William B. Pennebaker, Joan L. Mitchell: JPEG, Still Image Data Compression Standard, Van Nostrand Reinhold, New York, 1993 |
| [3] | Christof Ricken: Einsatz datenreduzierter Videosignale (MPEG-2, JPEG) in der Fernseh-Produktionstechnik, VDI, Düsseldorf, 1998 |
| [4] | CCITT: Recommendation T.81 - Information technology - coded
representation of picture and audio information - Digital compression and
coding of continuous-tone still pictures: requirements and guidelines ITU-T T.81 /ISO/IEC 10918-1 - JPEG Standard Text http://www.igd.fhg.de/www/projects/icib/telecom/ccitt/rec_t.81/itu-11505_t81e.ps.gz |