| Title: | JPEG2000 Kodierungstechnik | ||
|---|---|---|---|
| Abstract: | Bei der Erarbeitung der JPEG2000 Kodierungstechnik hatte man nicht nur optimales Kompressionsverhalten als Ziel. Aus Erfahrungen mit dem alten JPEG Standard hat sich eine lange Liste an Verbesserungsvorschlägen und Wünschen nach zusätzlichen Features ergeben. Möglichst vielen dieser Wünsche nachzukommen, war daher das Hauptziel für den neuen Standard. In dieser Lerneinheit wird die Architektur des JPEG2000 Encoders beschrieben, der einen Datenstrom erzeugt, der sämtliche Features des JPEG2000 Standards darstellen kann (unter anderem auch verlustbehaftet, verlustlos). Es wird die Technik des Embedded Coding beschrieben, und die Vorteile,die sich aus dieser kodierungstechnik ergeben. | ||
| Status: | Final for Review #2 - captions missing | Version: | 2005-01-17 |
| History: | 2005-01-17
(Thomas Migl): math-xml hinzugefügt 2004-11-04 (Thomas Migl): acro added 2004-10-14 (thomas migl): pda Abb. hinzugefügt 2004-09-16 (Thomas Migl): pda abb. hinzugefügt 2004-08-16 (Robert Fuchs): Checked, fixed and exported for Review #2. 2004-07-26 (Thomas Migl): LOD1 und LOd2 textlich fertiggestellt. ausgezeichnet +++ ABGESCHLOSSEN LOD2 +LOD1 text+auszeichnung komplett; Abstract,Summary, keine LOD3 +++ NOCH ZU MACHEN: Abb. Bitebenen noch draft, restl. fehlt PDA 2004-07-23 (Thomas Migl): LOD2 komplett imprtiert, teiweise ausgezeichnet |
||
| 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/ | ||
Einleitung marc20001Motivation zur JPEG2000 Kodierung
2autoIn den Lerneinheiten Wavelets und Waveletbasierte Bildkodierungstechnik wird ausführlich die Funktionsweise der Wavelettransformation und deren Bedeutung für die Bildkodierung erläutert. Weiters werden die sich durch die Wavelettransformation eröffnenden Möglichkeiten zur Bildkompression aufgezeigt.(perzeptuelle Kodierung , Entropiekodierung etc). Die einfachste Möglichkeit wäre nun, die DCT 242 durch eine Wavelettransformation zu ersetzen, alle weiteren Kodierungsschritte könnte man von JPEG (Quantisierungstabelle, Entropiekodierung etc) übernehmen. Alleine durch die Eigenschaften der Wavelettransformation wäre diese Kodierungstechnik der herkömmlichen JPEG Kodierungstechnik überlegen (bessere Qualität bei niedrigen Datenraten, keine Blockbildung). Motivation zur JPEG2000 KodierungBei der Erarbeitung der JPEG2000 Kodierungstechnik hatte man nicht nur optimales Kompressionsverhalten als Ziel. Aus Erfahrungen mit dem alten JPEG Standard hat sich eine lange Liste an Verbesserungsvorschlägen und Wünschen nach zusätzlichen Features ergeben. Möglichst vielen dieser Wünsche nachzukommen, war daher das Hauptziel für den neuen Standard. So musste man bei der Erstellung der Kodierungstechnik von JPEG2000 unter anderem auf folgende Anforderungen achten:
JPEG2000 Encodergray20011Blockschaltbild eines JPEG2000 Encoders PC
Blockschaltbild eines JPEG2000 Encoders PDA_Phone
Beschreibung des Blockschaltbildes
2Blockschaltbild eines JPEG2000 Encoders PC
Die Abbildung zeigt den Aufbau eines JPEG2000 Encoders. Diese Architektur erfüllt sämtliche Anforderungen wie verlustfreie/verlustbehaftete Kompression, progressiver Bildaufbau etc
Blockschaltbild eines JPEG2000 Encoders PDA_PhoneDie Abbildung zeigt den Aufbau eines JPEG2000 Encoders. Diese Architektur erfüllt sämtliche Anforderungen wie verlustfreie/verlustbehaftete Kompression, progressiver Bildaufbau etc
Pre-Processing gray2002gray2001 marc2000 rabb20021Tiling
Leveloffset
Aufteilung in Komponenten
2Der erste Schritt der JPEG2000 Kodierung, der Pre-Processing Schritt, unterteilt sich in drei Teilschritte. TilingIm JPEG2000 Standard soll es möglich sein, auch Bilder mit einer sehr hohen Datengröße (hohe Pixelanzahl), unabhängig von der Komplexität der verwendeten Hardware, zu bearbeiten. Da für viele Anwendungen Decoder verwendet werden, die nur eine beschränkte Speicherkapazität zur Verfügung haben, kann ein Bild im JPEG2000 Standard optional in Unterabschnitte (sogenannte Tiles, engl.: Kacheln) unterteilt werden. Die Tiles sind aneinandergrenzende Rechtecke, die sich nicht überlappen und von gleicher Größe sind (Ausnahme: Tiles am Rand eines Bildes).Jedes Tile wird bei der anschließenden Kodierung unabhängig kodiert, quasi als eigenes Bild betrachtet. Erst der Decoder setzt aus den Tiles das Bild in Originalgröße wieder zusammen. Es ist natürlich auch möglich, das gesamte Bild als ein einziges Tile zu verarbeiten. Level OffsetJPEG2000 benötigt am Eingang Signalwerte, deren dynamischer Bereich sich um den Nullpunkt zentriert. Gründe dafür sind unter anderem die von JPEG2000 verwendeten Hochpassfilterstufen (Wavelettransformation), die arithmetische Kodierung etc.. Ein Bildsignal besteht nun aber aus Werten größer gleich Null. Um sie JPEG2000 freundlich zu machen, muss man sie daher einem Level Offset unterziehen. Dabei wird der mittlere Wert des Wertebereiches als Null, die anderen Werte durch ihren Differenzbetrag dazu und mit entsprechenden Vorzeichen kodiert. Aufteilung in KomponentenIm JPEG2000 Standard kann ein Bild aus einer hohen Zahl von Komponenten bestehen. Jede Komponente besteht aus einer Matrix von Werten, jeder Wert repräsentiert einen Pixelpunkt des Bildes. Die Werte können mit oder ohne Vorzeichen sein, und eine Größe von 1 bis 32 Bit/Abtastwert haben. Im einfachsten und häufigsten Fall handelt es sich bei diesen Werten um die Farbkomponenten Rot, Grün und Blau (siehe Lerneiheit der JPEG 2000 Standard). Wie im JPEG Standard gilt auch hier, dass zur Datenkompression eine bestimmte Farbe durch ihren Grauwert und zwei Farbkomponenten (Chrominanzwerte) besser repräsentiert wird als durch seine RGB Komponenten. Gründe dafür sind
Im JPEG2000 Standard sind nun zwei Farbraumtransformationen definiert, mit deren Hilfe man von der RGB zur YUV Darstellung gelangt. Irreversible Farbtransformation (ICT)Sie ist ident mit der im JPEG verwendeten Farbraumtransformation (siehe Lerneinheit JPEG Bildvorbereitung). Ein Problem dieser Transformation ergibt sich dadurch, dass sich für die Grau- und Chrominanzwerte Beträge mit beliebig vielen Nachkommastellen ergeben. Durch Rundungsfehler gehen hier gezwungener Maßen immer Informationen verloren. Die RGB Werte können daher aus den YUV 304 Werten nicht mehr verlustfrei rekonstruiert werden. Reversible Farbtransformation (RCT)Mit JPEG2000 muss auch eine absolut verlustfreie Kompression möglich sein. Dafür wurde eigens eine neue Farbraumtransformation eingeführt. Sie ist so beschaffen, dass sowohl die RGB Werte wie auch die Helligkeits- und Chrominanzwerte immer nur ganzzahlige Beträge annehmen können. Hier kann zwischen RGB- und YUV Farbraum hin- und hergewechselt werden, ohne dass Informationen verloren gehen. Die RCT 514 muss bei der verlustfreien Kodierung verwendet werden, kann aber auch zur verlustbehafteten Kompression herangezogen werden. Diskrete Wavelettransformation gray2001 marc2000 rabb20021Die zwei Arten der diskreten Wavelettranformation für JPEG2000
2Die zwei Arten der diskreten Wavelettranformation für JPEG2000Für die Wavelettranformation kann zwischen zwei Arten von DWT Algorithmen gewählt werden, zwischen der Gleitkomma – und der Integertransformation. Für die verlustlose Kodierung kann ausschließlich die Integer WT verwendet werden, für die verlustbehaftete kann User zwischen den beiden frei wählen. Für beide Transformationen gilt, dass im Originalbereich die Werte (Helligkeitswerte der Pixel) immer ganze Zahlen (Integer) sind.
Totzonen Quantisierer gray20011auto
Prinzip des Totzonenquantisierers PC
Prinzip des Totzonenquantisierers PDA_Phone
Totzonen Quantisierer PC
Totzonen Quantisierer PC
Quantisierung für verlustfreie Kodierung
2autoAuch bei der Quantisierung beschreitet JPEG2000 eigene Wege. Es kommt ein sogenannter Totzonenquantisierer zum Einsatz. Für jedes Subband werden die Werte mit einem gegebenen Quantisierungsintervall quantisiert:
Es gilt dabei: Ein großes Quantisierungsintervall entspricht einer groben Quantisierung (was eine hohe Datenkompression mit sich bringt) ein kleines Quantisierungintervall hingegen einer sehr genauen Repräsentation der Koeffizienten. Prinzip des TotzonenquantisierersBei der Totzonenquantisierung wird der Umstand ausgenutzt, dass die Werte durch den Level Offset um einen Nullpunkt (entspricht für die Y Werte einem mittleren Grau) zentriert sind. Prinzip des Totzonenquantisierers PCBei der Totzonenquantisierung wird der Umstand ausgenutzt, dass die Werte durch den Level Offset um einen Nullpunkt (entspricht für die Y Werte einem mittleren Grau) zentriert sind.
Die Bezeichnung „Totzone“ bezieht sich auf den Bereich um den Nullpunkt. Alle Werte in diesem Bereich werden durch die Quantisierung null. Da sich dieser über zwei Quantisierungsintervalle erstreckt (für plus und minus Werte), setzt er doppelt so viel Koeffizienten auf Null, was gut für die Kompression ist. Prinzip des Totzonenquantisierers PDA_PhoneBei der Totzonenquantisierung wird der Umstand ausgenutzt, dass die Werte durch den Level Offset um einen Nullpunkt (entspricht für die Y Werte einem mittleren Grau) zentriert sind.
Die Bezeichnung „Totzone“ bezieht sich auf den Bereich um den Nullpunkt. Alle Werte in diesem Bereich werden durch die Quantisierung null. Da sich dieser über zwei Quantisierungsintervalle erstreckt (für plus und minus Werte), setzt er doppelt so viel Koeffizienten auf Null, was gut für die Kompression ist. Totzonen Quantisierer PCDas Quantisierungsintervall sei mit 10 festgelegt. Welchen Wert erhält der Wert -21,82 nach seiner Quantisierung?
Totzonen Quantisierer PDA_PhoneDas Quantisierungsintervall sei mit 10 festgelegt. Welchen Wert erhält der Wert -21,82 nach seiner Quantisierung?
Quantisierung für verlustfreie KodierungAuch bei der verlustfreien Komprimierung durchlaufen die Koeffizienten den Totzonenquantisierer. Es wird dabei das Quantisierungsintervall auf eins gesetzt. So findet keine wirkliche Quantisierung (und somit auch keine Verluste) statt. Blockkodierung marc2000 rabb20021Embedded CodingMotivation zur Blockkodierung
Blöcke im JPEG2000 Datenstrom PC
Blöcke im JPEG2000 Datenstrom PDA_Phone
2Embedded CodingZur Kodierung wird jedes Subband in kleine, rechteckige und sich nicht überlappende Blöcke, den so genannten Codeblöcken, unterteilt. Die Größe dieser Blöcke können dabei frei gewählt werden, wobei ein Block maximal 4096 Werte umfassen darf. Bei der folgenden Entropiekodierung wird jeder dieser Blöcke unabhängig von den anderen kodiert. Die Kodierungsschritte sind dabei so angelegt, dass eine möglichst genaue Auftrennung der Information erzeugt wird(embedded Coding). Motivation zur Blockkodierung
Blöcke im JPEG2000 Datenstrom PC In diesem Beispiel bezeichnet jede Zahl einen Codeblock. Die Zahlen beschreiben, in welcher Reihenfolge die Codeblöcke für den Datenstrom kodiert werden. Durch diese Anordnung ist gewährleistet, dass alle Informationen, die nötig sind, um eine bestimmte Bildstelle in einer gewünschten Auflösungsstufe darzustellen, auch im Datenstrom an der gleichen Stelle zu finden sind. Blöcke im JPEG2000 Datenstrom PDA_Phone
In diesem Beispiel bezeichnet jede Zahl einen Codeblock. Die Zahlen beschreiben, in welcher Reihenfolge die Codeblöcke für den Datenstrom kodiert werden. Durch diese Anordnung ist gewährleistet, dass alle Informationen, die nötig sind, um eine bestimmte Bildstelle in einer gewünschten Auflösungsstufe darzustellen, auch im Datenstrom an der gleichen Stelle zu finden sind. Entropiekodierung1auto
Kontextbasierte binäre arithmetische Kodierung rabb2002
Bitebenen
LSB und MSB all
Bitebenen PC
Bitebenen PDA_Phone! Darstellung eines Wavletkoeffizienten in mehrere Bitebenen PC
Darstellung eines Wavletkoeffizienten in mehrere Bitebenen PDA_Phone
Vorteil der Bitebenen Kodierung
2autoFür die Entropiekodierung wird bei JPEG2000 ausschließlich die arithmetische Kodierung verwendet. Diese nutzt gleich der Huffmankodierung die Auftrittswahrscheinlichkeit von Zeichen in einer Nachricht zu dessen Kompression. Die Huffmankodierung kann aus Prinzip nicht optimal arbeiten, da die Auftrittswahrscheinlichkeit eines bestimmten Zeichens gewöhnlich eine beliebig reele Zahl ist, die Anzahl der Bitstellen für ein Zeichen allerdings nur ganzzahlig sein kann. Die arithmetische Kodierung beseitigt diesen Nachteil. Es werden dabei nicht die Zeichen einzeln kodiert, sondern es wird eine ganze Nachricht durch eine einzige Gleitkommazahl, welche durch eine sequentielle Intervallschachtelung ermittelt wird, aus dem Intervall[0,1] repräsentiert. Kontextbasierte binäre arithmetische Kodierung rabb2002JPEG2000 verwendet eine kontextbasierte binäre arithmetische Kodierung.
BitebenenAnders wie bei JPEG wird bei JPEG2000 nicht jeder Koeffizient für sich kodiert, sondern es werden die Bits gleicher Wertigkeit eines Codeblockes zusammengefasst und in einer entsprechenden Bitebene kodiert. Die Bits höchster Wertigkeit werden als MSB (most significant bit) bezeichnet und werden in der MSB 515 -Ebene kodiert, die Bit geringster Wertigkeit als LSB (least significant Bit) und in der LSB 516-Ebene kodiert. LSB und MSBMan betrachte den 4 stelligen binären Wert 1011 Bitebenen PCEs seien 3 binäre Werte mit 5 Bitstellen gegeben
Die MSB-Ebene umfasst jene Bitstellen, auf welcher mindestens einer der Werte eine 1 aufweist. In diesem Beispiel sind an der höchsten Bitstelle alle Werte null. Die MSB 515 Ebene fasst daher erst die Bits von der 4-ten Stelle zusammen. Darstellung eines Wavletkoeffizienten in mehrere Bitebenen PC Die Abbildung zeigt die Darstellung eines Waveletkoeffizienten in den verschiedenen Bitebenen. Darstellung eines Wavletkoeffizienten in mehrere Bitebenen PDA_Phone Die Abbildung zeigt die Darstellung eines Waveletkoeffizienten in den verschiedenen Bitebenen. Vorteil der Bitebenen KodierungDie Bitebenen Kodierung erfüllt die Anforderungen für ein embedded Coding. Jede Bitebene repräsentiert einen Qualitätslevel. Die oberste Ebene zeigt eine reine schwarz/weiße Repräsentation. Die weiteren Ebenen liefern sukzessive die Werte um die genauen Waveletwerte zu erhalten. Durch die Bitebenen Kodierung kann zum Beispiel auf einfache Weise eine gewünschte Datenrate eingestellt werden. Es werden dabei nur so viele Bitebenen kodiert, die die gewünschte Dateigröße zulässt. Kodierung der Bitebenen1Abtastung PC
Abtastung PDA_Phone
Drei Pass Methode
Vorteil der Drei-Pass Methode
Diagramm Verzerrung/Datenrate PC
Diagramm Verzerrung/Datenrate PDA_Phone
2Abtastung rabb2002Die Bitebenen werden getrennt von einander kodiert. Die Abbildung zeigt die vom JPEG2000 Standard vorgegebene Reihenfolge der Abtastung der Werte. Diese Art der Abtastung wurde gewählt, um eine einfache Implementierung von JPEG2000 in Hinsicht auf Hard- und Software zu ermöglichen. Abbildung: Abtastung PC
Die Abbildung zeigt die Reihenfolge, in welcher die Werte einer Bitebene innerhalb eines Kodeblockes kodiert werden. Oben beginnend, werden die ersten vier vertikalen Werte eingelesen, dann auf die nächste Spalte gesprungen, etc Abbildung: Abtastung PDA_Phone
Die Abbildung zeigt die Reihenfolge, in welcher die Werte einer Bitebene innerhalb eines Kodeblockes kodiert werden. Oben beginnend, werden die ersten vier vertikalen Werte eingelesen, dann auf die nächste Spalte gesprungen, etc Drei Pass Methode rabb2002 gruen2004Mit der MSB-Ebene beginnend, werden die Werte jeder Ebene einer dreistufigen Kompressionsprozedur unterzogen. In welcher Stufe welcher Wert kodiert wird, entscheidet das Kriterium der Signifikanz. Signifikanz eines WertesEin Stelle in einer Bitebene wird als signifikant bezeichnet, wenn in betrachteter Ebene oder in einer höherwertigen Ebene an dieser Stelle eine Eins steht.
Vorteil der Drei-Pass Methode rabb2002 gruen2004Die Drei-Pass Methode stellt eine weitere Aufgliederung der Werte dar. Die Werte sind derart kodiert, dass im ersten Schritt der Hauptanteil der Information in minimaler Dateiengröße kodiert ist.
Diagramm Verzerrung/Datenrate PC Die x-Achse repräsentiert den Qualitätslevel, wobei eine hohe Qualität geringen Datenfehlern entspricht (hier als Verzerrung bezeichnet), die y-Achse repräsentiert die Datenrate. Man sieht, dass bei richtiger Reihenfolge der Schritte (ABC) eine viel bessere Vorschauqualität gegeben ist, als wenn man die Reihenfolge umkehrte (CBA). Diagramm Verzerrung/Datenrate PDA_Phone! Die x-Achse repräsentiert den Qualitätslevel, wobei eine hohe Qualität geringen Datenfehlern entspricht (hier als Verzerrung bezeichnet), die y-Achse repräsentiert die Datenrate. Man sieht, dass bei richtiger Reihenfolge der Schritte (ABC) eine viel bessere Vorschauqualität gegeben ist, als wenn man die Reihenfolge umkehrte (CBA). Steuerung der Datenrate gray20011
2Beim Prozess der Datenratesteuerung muss der durch die Kompression entstandene Datenstrom so modifiziert werden, dass die gewünschte Zieldatenrate erreicht wird. Da der JPEG2000 Datenstrom so aufgebaut ist, dass für jeden Block die Informationen in qualitätsabhängigen Tranchen (Bitebenen, Drei Pass kodierung) vorliegen, muss ein Algorithmus nur bestimmen, welche Tranchen aus den Datenstrom entfernt werden müssen, um die gewünschte Datenrate zu erzielen. Zusammenfassung JPEG2000 Kodierungstechnik1auto
2autoDie Motivation für die JPEG2000 Kodierungnstechnik liegt neben optimierten Komprimierungsverhalten vor allem in der Vereinheitlichung der Encoder Architektur. Es sollen mit ein und demselben Aufbau alle Features geboten werden können, die der JPEG2000 Standard bietet, so auch das Feature der verlustfreien Bildkomprimierung, für die eigens die RreversibleFarbtransformation und die Integer Wavelettransformation eingeführt worden ist (siehe pre-processing, diskrete Wavelettranformation). Weiters soll jede Bildstelle im Datenstrom eindeutig lokalisierbar sein. Dies wird erreicht durch das so genannte embedded Coding (siehe Blockkodierung). So kann auf beliebige Bildstellen zugegriffen werden. Die Informationen für eine Bildstelle sind durch Bitebenen und drei Pass Methode in "Qualitätstranchen" aufgesplittert (siehe Blockkodierung). Je nach Anwendung kann die nötige Information gelesen werden. Die Methode des embedded Coding erlaubt unteranderem eine einfache Datenratesteuerung. |
![<math> <semantics> <mrow> <mi>q</mi><mo>=</mo><mi>s</mi><mi>i</mi><mi>g</mi><mi>n</mi><mo stretchy='false'>(</mo><mi>y</mi><mo stretchy='false'>)</mo><mrow><mo>[</mo> <mrow> <mfrac> <mrow> <mrow><mo>|</mo> <mi>y</mi> <mo>|</mo></mrow> </mrow> <mrow> <msub> <mi>Δ</mi> <mi>b</mi> </msub> </mrow> </mfrac> </mrow> <mo>]</mo></mrow> </mrow> <annotation encoding='MathType-MTEF'> </annotation> </semantics> </math>](images/23_01.gif)
| (empty) |