| Title: | JPEG Kodierungstechnik | ||
|---|---|---|---|
| Abstract: | Der JPEG Standard definiert drei Modi der verlustbehafteten Kodierung: Sequentielle, progressive und hierarchische Kodierung. Jeder Modus ist für bestimmte Anwendungen gedacht. Allen drei Techniken sind der erste Schritt der JPEG Kodierung, die Bildvorbereitung (siehe LU19 "JPEG Bildvorbereitung"), und die Art der Quantisierung der DCT Koeffizienten gemeinsam. Unterschiedlich sind aber die Kodierung der quantisierten DCT Koeffizienten. | ||
| Status: | Captions missing | Version: | 2005-01-17 |
| History: |
2005-01-17 (Thomas Migl): Tabelleneigenschaft geändert 2005-01-07 (Robert Fuchs): Added VisJPEG applet => please test, .jar might not work properly 2004-11-04 (Thomas Migl): 2 applets entfernt, acro added 2004-09-16 (Thomas Migl): fehlende pda hinzugefügt, viso-applet auf melville verlinkt 2004-08-16 (Robert Fuchs): Checked, fixed and exported for Review #2. 2004-07-29 (Thomas Migl): Platzhalter für zwei applets,bil-finalPC +++ TO DO: Abb PDA, Imp. Applet +++ VERW. APPLETS:41902, 4170 2004-07-26 (Robert Fuchs): Manual import into the Greybox. 2004-03-12 (Robert Fuchs): Closed for 50% Content Deadline import in Scholion. 2004-03-08 (Thomas Migl): LOD1 und abstract hinzugefügt 2004-03-07 (Robert Fuchs): Fixed buggy source stru2002 (was stru2202). 2004-03-05 (Thomas Migl): Mit LOD1 begonnen 2004-03-05 (Robert Fuchs): Added images, formulas and links. 2004-03-02 (Robert Fuchs): Imported and tagged content from "m4-LU20-JPEGKodierungstechnik-fertig.doc". 2004-02-25 (HTMLContentTools): Created skeleton page. |
||
| Author 1: | Thomas Migl | E-Mail: | migl@ims.tuwien.ac.at |
|---|---|---|---|
| Author 2: | (empty) | E-Mail: | (empty) |
| Author 3: | (empty) | E-Mail: | (empty) |
| Author 4: | (empty) | E-Mail: | (empty) |
| Author 5: | (empty) | E-Mail: | (empty) |
| Organization: | Technische Universität Wien; Institut für Softwaretechnik und Interaktive Systeme; Arbeitsgruppe für Interaktive Multimediale Systeme; http://www.ims.tuwien.ac.at/ | ||
Einleitung1JPEG Kodierungstechnik
3 Arten der JPEG Kodierung
2KodierungstechnikenFür alle JPEG Kodierungstechniken wird das Bild vor der eigentlichen Kompression aufbereitet, wie es in der Lerneinheit JPEG Bildvorbereitung beschrieben ist. Auch die Quantisierung, die den eigentlichen Kompressionsvorgang ausmacht, ist für alle JPEG Kodierungstechniken gleich. Unterschiede gibt es dann, wie die errechneten DCT 242 Koeffizienten im JPEG Datenstrom kodiert werden. Je nach Anwendung kann man zwischen drei unterschiedliche JPEG Kodierungstechniken wählen:
Sequentielle KodierungDas ist die am meist angewandte Technik. Bei einigen Anwendungen kann nachteilig sein, dass man sich das Bild erst dann ansehen kann, wenn die gesamte JPEG Datei zur Verfügung steht. So muss man beim Surfen im Internet darauf warten, bis die Bilder einer Webseite vollständig herunter geladen sind. Erst dann ist eine Betrachtung der Webseite möglich. Progressive KodierungDieser Modus ist dafür gedacht, dass schon während des Runterladens von einem Server das Bild bereits am Bildschirm sichtbar ist. Am Anfang ist das Bild in schlechter Qualität dargestellt, diese wird aber kontinuierlich besser und erreicht bei Beendigung des Ladevorganges volle Bildqualität. Hierarchische KodierungDie Hierarchische Kodierung ist eine spezielle Form der progressiven Kodierung. Sie ist für Anwendungen gedacht, die ein und dasselbe Bild in verschiedenen Auflösungen benötigen. Quantisierung bei JPEG1Quantisierung
DCT KoeffizientenDCT Koeffizienten werden individuell quantisiert:
Quantisierungstabellen
Von JPEG empfohlene Quantisierungstabelle für Luminanz stru2002, 166
Von JPEG empfohlene Quantisierungstabelle für Chrominanz stru2002, 166
2EinleitungBei der Quantisierung handelt es sich um jenen Teil der Prozedur, in dem die eigentliche Kompression passiert. Es werden dabei die Koeffizienten nicht in voller Genauigkeit dargestellt, sondern:
Prinzip der Quantisierung bovi2000, 514Um das Bild möglichst exakt aus dem Spektralberreich wieder zu rekonstruieren, bedarf es einer hohen Präzision in der Darstellung der DCT-Koeffizienten und damit verbunden eine große Anzahl an erforderlichen Bits. Bei der Quantisierung werden die DCT-Koeffizienten so modifiziert, dass sie nur eine limitierte Anzahl an Werten annehmen können. Eines der Key-Features ist dabei, dass viele DCT-Koeffizienten den Wert 0 annehmen, das eine effektive Kodierung mit Hilfe von Huffman und Lauflängenkodierung erlaubt. QuantisierungsintervallJedem DCT-Koeffizient wird individuell ein Quantisierungsintervall zugeordnet. Dabei gilt, je größer das Quantisierungsintervall q, desto gröber die Quantisierung, und damit auch einer größer Quantisierungsfehler. Formel für quantisierten DCT Koeffizienten bovi2000, 517
Wahl der Quantisierungsintervalle stru2002, 165Die Wahl der individuellen Quantisierungsintervalle erfolgt unter Berücksichtigung der menschlichen Wahrnehmung (siehe Lerneinheit Grundlagen der perzeptuellen Bildkodierung). Der JPEG-Standard macht einen Vorschlag für diese Quantisierungswerte. Diese Werte sind in einer Quantisierungstabelle abgelegt und können als Parameter für die Kompression angegeben werden. Ermittlung der Werte für die Quantisierungstabelle bovi2000, 517In einer Testreihe wurde für jeden Koeffizienten ein mittlerer Quantisierungswert ermittelt, bei dem die Veränderung des Koeffizienten im rücktransformierten Bild noch nicht zu erkennen ist. Zur Ermittlung geeigneter Quantisierungsintervalle wurde ein 760x576 Bild mit einem Unterabtastung (siehe Lerneinheit Grundlagen der perzeptuellen Bildkodierung) der Chrominanzwerte von 2 betrachtet. Die Entfernung Betrachter und Bild betrug das 6-fache der Bildbreite. Aus diesen Testreihen ergaben sich zwei Quantisierungstabellen: Eine für den Luminanz- und eine für den Chrominanzblock. QuantisierungstabellenBei der Untersuchung der Tabellen sieht man, dass die Tabelle für die Chrominanz generell größere Werte hat, was einer gröberen Quantisierung entspricht. Das resultiert aus dem Phänomen, dass unser Seesinn für Chrominanz wesentlich unsensibler ist als für Luminanz (siehe Lerneinheit Grundlagen der perzeptuellen Bildkodierung) Diese unverbindlich empfohlenen Quantisierungstabellen bringen für viele Anwendungen passende Ergebnisse und haben sich daher unter der Bezeichnung "default"-Quantisierungstabellen gleichsam als Standard durchgesetzt. Von JPEG empfohlene Quantisierungstabelle für Luminanz stru2002, 166
Von JPEG empfohlene Quantisierungstabelle für Chrominanz stru2002, 166
Einsatz eigener QuantisierungstabellenEs können natürlich auch eigene Tabellen verwendet werden. Will man zum Beispiel ein Bild auf eine vorgegebene Größe komprimieren, müssen die Werte in der Quantisierungstabelle dementsprechend modifiziert werden. Damit das Bild dann auch wieder durch einen Enkoder darstellbar ist, muss die bei der Kodierung verwendete Quantisierungstabelle im Datenstrom enthalten sein. Kodierung der DC-Koeffizienten1Koeffizienten
Kodierung
2Differenzkodierung stru2002, 167Bei der JPEG Kodierung werden die AC 507 und DC 494 Koeffizienten getrennt voneinander kodiert. Der DC Koeffizient beschreibt die mittlere Helligkeit eines 8x8 Blockes. Es wird davon ausgegangen, dass benachbarte Blöcke einen ähnlichen Mittelwert besitzen. Es ist daher sinnvoll, die Differenzkodierung anzuwenden. Somit kann ein DC-Wert aus seinem Vorgänger prädiziert werden.
Mit
Huffmankodierung des PrädiktionsfehlerDer theoretische Wertbereich der Prädiktionsfehler ist sehr groß. In der Praxis wird in den meisten Fällen der Differenzwert sehr klein sein. Um eine gute Kompression zu erzielen, ist es förderlich, kleine Prädiktionsfehler mit wenigeren Bitstellen als große zu kodieren, da ja kleinere Differenzen statistisch gesehen viel öfter vorkommen. Zur Umsetzung dieses Denkansatzes verwendet man die Huffmankodierung (siehe Lerneinheit Entropiekodierung). Kodierung des Prädiktionsfehlers mittels HuffmancodierungDifferenzwerte werden in 12 Kategorien eingeteilt, und jeder Kategorie wird ein Codewort zugewiesen. Die Kategorienummer legt fest, wie viele Bits für die Übertragung des tatsächlichen Differenzwertes DIFF folgen. Dekodiert der Empfänger zum Beispiel den Huffman-Code für die Kategorie 2, so weiß er damit, dass weitere 2 Bits kommen, die den entsprechenden Wert aus der Tabelle identifizieren. Verwendung eigener HuffmancodesEs steht jeden Anwender frei, selbst einen Huffmancode zu konstruieren um optimale Kompressionsergebnisse zu erzielen. Die verwendeten Codes müssen dann im Datenstrom mitgeschickt werden. Kodierung der AC-Koeffizienten1Zick-Zack AbtastungStruktogramm der Zick-Zack Abtastung PC
Struktogramm der Zick-Zack Abtastung PDA_Phone
Prinzip der Zick-Zack Abtastung
2Zick-Zack-AbtastungStruktogramm der Zick-Zack Abtastung PC
Struktogramm der Zick-Zack Abtastung PDA_Phone
Prinzip der Zick-Zack AbtastungZuerst wird die 8x8- Koeffizientenmatrix durch eine Zick-Zack-Abtastung in einen eindimensionalen Vektor überführt. Dies bewirkt eine Sortierung der Koeffizienten entsprechend ihrer Ortsfrequenz. Tiefe Frequenzen stehen am Anfang des Vektors, hohe am Ende. Erfahrungsgemäß werden jene DCT-Koeffizienten, die hohe Frequenzen beschreiben, durch die Quantisierung auf den Wert Null gesetzt. Huffmankodierung/LauflängenkodierungAlle AC-Koeffizienten ungleich Null werden wie die DC- Koeffizienten in Kategorien unterteilt. Außerdem wird für jeden dieser Koeffizienten der Abstand zum Vorgänger ungleich Null ermittelt. Diese Lauflänge darf einen Wert von 0 bis 15 haben. Da die Anzahl benachbarter Nullen und die Größe des nachfolgenden Koeffizienten miteinander korreliert sind, werden aus der Kombination von Lauflänge und Kategorie des AC-Koeffizienten neue Datensymbole gebildet. Dabei sind zwei besondere Symbole zu unterscheiden. ZRL definiert eine Lauflänge von 15 Nullen mit einen Folgewert 0. Das Ende einer Zick-Zack-Abtastung wird durch ein EOB ( End of Block) markiert. Das EOB 508 Symbol folgt dem letzten AC- Koeffizienten ungleich Null. Alle nachfolgenden, zu Null quantisierten Koeffizienten müssen dadurch nicht mehr kodiert werden. Den aus der Kombination entstandenen, neuen Datensymbolen werden Huffman-Codewörter zugeordnet. Entsprechend der statischen Verteilung werden bei gleicher Lauflänge kürzere Kodes für kleinere AC-Werte und bei gleicher Kategorie kürzere Kodes für kurzen Lauflängen vergeben. Applet: JPEG Visualisierung1JPEG Visualisierung2JPEG VisualisierungEinleitungDas folgende Java Applet soll im experimentellen Umgang helfen, Prozeduren, die die JPEG Kodierung durchläuft, kennen- und verstehen zu lernen. Es beschreibt unteranderem die in dieser Lerneinheit erläuterten Techniken der Quantisierung und die Kodierung der AC-Koeffizienten (Zick-Zackabtastung, RLE und Entropiekodierung) AppletbeschreibungDie Oberfläche des Applets ist in zwei Bereiche geteilt. Bereich mit ReiterauswahlDer rechte Bereich ist in 6 Reiter aufgeteilt. Jeder Reiter beschreibt eine Prozedur von JPEG . Die Anordnung der Reiter (von links beginnend) entspricht der streng festgelegten Reihenfolge der JPEG Kodierung. Bereich für BildauswahlDer linke Bereich des Applets bleibt unabhängig vom gewählten Reiter gleich. Hier kann die Studentin ein Bild auswählen, welches im oberen Bildfenster angezeigt wird. Verändert nun die Studentin in einer der Prozeduren bestimmte Parameter, kann sie in der linken Spalte den Button „Neu berechnen“ wählen. Im unteren Bildfenster wird dann das entsprechende JPEG Bild angezeigt (wobei sie auch „Differenzbild“ wählen kann, welches Aufschluss über die Qualität der Kodierung gibt). Weiters wird auch der entsprechende Kompressionsgrad berechnet und in einem Fortschrittsbalken angezeigt. Reiter für JPEG KodierungsprinzipQuantisierungDie Studentin kann mit Maus einen 8x8 Pixelblock im Bild wählen. Weiters kann sie einen Qualitätsfaktor vorgeben.Es wird die Matrix mit den nicht quantisierten und die Matrix mit den quantisierten DCT Koeffizienten sowohl in Tabellen- wie auch in 3D Ansicht dargestellt. Zick-Zack ScanFür einen gewählten Block wird das Ergebnis einer von links nach rechts und von oben nach unten gescannten Matrix mit einer im Zick-Zackverfahren abgetasteten Matrix verglichen. DPCM+RLEDie Studentin kann mit Maus einen 8x8 Pixelblock im Bild wählen. Es werden die DPCM kodierten DC Werte und die RLE kodierten AC Werte dargestellt. EntropiekodierungEs wird wieder ein Block im Bild gewählt. Man kann zwischen standard Huffman und optimierten Huffman wählen. Dargestellt werden
Progressiver Modus stru2002, 1721Bildaufbau in mehreren Schritten
Vorteil
Zwei Arten der ProgressionSpektrale Selektion
Schrittweise Approximation der Koeffizienten
2Prinzip des progressiven ModusIm progressiven Modus wird das Bild in mehreren Schritten, beginnend mit einer groben Auflösung des gesamten Bildes, übertragen. Jeder weitere Schritt verfeinert sukzessiv die Bildqualität. In jedem Durchlauf wird also nur ein Teil der Koeffizienten kodiert. Dieser Modus von JPEG ist dort von Vorteil, wo mit langsamen Übertragungen gearbeitet wird. Man empfängt sofort ein Bild, wenn auch nur in sehr grober Auflösung, kann aber sofort entscheiden, ob man den Übertragungsvorgang des ganzen Bildes abwarten oder abbrechen will. Arten der ProgressionJPEG definiert zwei Arten der Progression:
Spektrale SelektionHier werden zuerst nur die tieffrequenten Koeffizienten übertragen. Die höherfrequenten Anteile werden erst sukzessive in den folgenden Durchgängen übertragen. Während des Bildaufbaus wird das Bild am Beginn wie ein sehr stark komprimiertes JPEG Bild angezeigt, anschließend werden die Artefakte kontinuierlich verschwinden. Schrittweise Approximation der KoeffizientenNach der Übertragung der DC-Koeffizienten werden von allen AC-Koeffizienten zuerst die oberen Bits geschickt. In den folgenden Durchgängen werden die Werte der Koeffizienten präzisiert. Vergleich Spektrale Selektion/schrittweise Approximation bovi2000, 522Wenn alle Koeffizienten empfangen wurden, sind die Koeffizienteninformationen identisch mit denen einer sequentiellen Kodierung. Die Bildqualität ist daher im sequentiellen und progressiven Modus dieselbe, nur auf Grund der unterschiedlichen Kodierung variiert die benötigte Bitrate. Dabei benötigt die schrittweise Approximation meist weniger Bits als die spektrale Selektion und die sequentielle Kodierung. Die schrittweise Approximation liefert auch bei unvollendeter Übertragung eine bessere Qualität als die spektrale Selektion, ist aber am schwierigsten zu implementieren. Trotz der Vorteile, die die progressive Kodierung bringt, gibt es nur wenige Implementationen von progressiven JPEG codecs. Hierarchischer Modus - Ein Spezialfall der Progession1Bild in Pyramidenstuktur aufgebaut
Anwendung des hierarchischen Modus
Kodierungstechnik
2Arbeitsweise des hierarchischen ModusDer hierarchische Modus ist ein spezieller Fall des progressiven Modus. In diesem Modus wird das Bild in eine Pyramidenstruktur mit ansteigender Auflösung zerlegt. Am oberen Ende der Pyramide steht das Bild in seiner geringsten Auflösung, an der Basis der Pyramide ist das Bild in seiner voller Auflösung. Diese Arbeitsmethode wird dort eingesetzt, wo ein und dasselbe Bild in verschiedener Auflösung angezeigt werden können soll, z.B. auf dem Display eines Hand-Held Gerätes, auf einem Computerbildschirm, einem hochauflösenden Drucker. Erzeugung der AuflösungspyramideZur Erzeugung der Auflösungspyramide wird das Originalbild mehrfach mit M=2 unterabgetastet. Der erste Durchlauf (niedrigste Auflösung) verwendet einen sequentiellen oder progressiven Verarbeitungsmodi. Das Ergebnis dieser Kodierung wird aufwärtsgetastet, bilinear interpoliert und als Prädiktor für die nachfolgende Ebene verwendet. |
![<math> <semantics> <mrow> <mi>q </mi> <mi>X </mi> <mrow> <mo>[ </mo> <mrow> <mi>m </mi> <mo>, </mo> <mi>n </mi> </mrow> <mo>] </mo> </mrow> <mo>= </mo> <mi>r </mi> <mi>o </mi> <mi>u </mi> <mi>n </mi> <mi>d </mi> <mrow> <mo>[ </mo> <mrow> <mi>X </mi> <mo stretchy='false'>( </mo> <mi>m </mi> <mo>, </mo> <mi>n </mi> <mo stretchy='false'>) </mo> <mo>/ </mo> <mi>q </mi> <mo stretchy='false'>( </mo> <mi>m </mi> <mo>, </mo> <mi>n </mi> <mo stretchy='false'>) </mo> </mrow> <mo>] </mo> </mrow> </mrow> </semantics> </math>](images/20dctq_formula.gif){kind=small}
wenn 
wenn 
| (empty) |