Videocodierung

Inhaltsverzeichnis

1 Grundlagen 1.1 Warum Codierung ? 1.2 Bilddarstellungen 1.3 M√∂glichkeiten der Codierung 1.3.1Huffman-Codierung 1.3.2Arithmetische Codierung 2 Bildcodierungsformate 2.1 GIF 2.2 JPEG 2.2.1Diskrete Cosinus-Transformation (DCT) 2.2.2Quantisierung 2.2.3Entropiecodierung 2.3 Fraktale Kompression 2.4 Wavelet-Kompression 3 Videocodierungsformate 3.1 H.261 3.1.1DPCM 3.1.2Funktionsweise von H.261 3.2 MPEG 3.2.1MPEG-Versionen 3.2.2Verfahrensablauf 3.3 Motion-JPEG 4 Fazit: Welche Bildcodierung wof√ľr?

Grundlagen

Warum Codierung ?

Besonders durch die gestiegene Popularität des Internet durch die Möglichkeiten der Präsentation im World Wide Web hat die Bildcodierung enorm an Wichtigkeit gewonnen.

Zum einen locken besonders bunte Bilder und ansprechende Illustrationen die Menschen auf bestimmte Webseiten, zum anderen bewirken gerade gro√üe Bilder erh√∂hte Wartezeiten durch die im Vergleich zu Festplatten oder CD-ROMs k√ľmmerlich kleine Bandbreite einer Netz√ľbertragung.

Kaum dass die Größe eines digitalen Bildes auf der Festplatte durch eine mittlerweile Mindestgröße neuer Platten von 1 GB fast unerheblich geworden ist, bedeutet die Reduzierung der Übertragungszeit durch Bildkompression von z.B. 5 Minuten auf 20 Sekunden (BMP auf JPEG bei einem 1024x768 TrueColor Landschaftsbild) einen erheblichen Zeitgewinn.

Unkomprimierte digitale Videos dagegen beanspruchen so viel Speicherplatz, dass auch heutige Festplatten schnell am Ende sind, von der √úbertragungsrate ganz zu schweigen.

Bei der Codierung unterscheidet man grundsätzlich zwischen verlustbehafteter (lossy) und verlustfreier Codierung.

Bei verlustfreier Codierung werden nur die Redundanzen eines Bildes zusammengefaßt, z.B. wird bei aufeinanderfolgenden Pixeln gleicher Farbe nur einmal die Farbe und die Anzahl der Pixel gespeichert (variable Lauflängencodierung - variable length coding, VLC). Die Wiederherstellung des Ursprungsbildes ist jederzeit vollständig möglich. Man spricht hierbei von Datenkompression.

Zus√§tzlich werden bei verlustbehafteter Codierung die (theoretisch vollst√§ndig) irrelevanten Informationen entfernt, also Informationen, die das menschliche Auge sowieso nicht erkennen oder unterscheiden kann. Es ist dabei m√∂glich, den Fehlergrad einzustellen, so dass zur besseren Datenreduktion auch Informationen weggelassen werden k√∂nnen, die kaum wahrnehmbar sind. In der Realit√§t gibt es allerdings kein Verfahren, das absolut keine St√∂rungen erzeugt. Diese Bildst√∂rungen, Artefakte genannt, verst√§rken sich nat√ľrlich bei steigender Kompressionsrate. Bei diesen Methoden ist eine Rekonstruktion des Ausgangsbildes nat√ľrlich nicht m√∂glich, daf√ľr sind im Allgemeinen die Kompressionsraten erheblich h√∂her als bei verlustfreier Codierung.

Weitere wichtige Zielsetzungen sind nach Le Galle:

- Bildfehlerkorrektur: Die Codierung soll in der Lage sein, Fehler, die beim Abspielen, Speichern oder Kopieren auftreten können, zu erkennen und zu korrigieren.

- Skalierbarer Codier-/Decodieraufwand: Es soll m√∂glich sein die Codierung/Decodierung auch auf qualitativ schlechteren Systemen, eventuell unter Qualit√§tsverlust, durchzuf√ľhren.

- Format- und Aufl√∂sungsvielfalt: Unterschiedliche Formate und Aufl√∂sungen sollen unterst√ľtzt werden.

- Der Algorithmus soll kosteng√ľnstig, also mit vertretbarem Aufwand in Hardware realisierbar sein.

Bei der Codierung von Videosequenzen ergeben sich weitere Anforderungen:

- Wahlfreier Zugriff: Es muss möglich sein, auf einzelne Bilder innerhalb der Sequenz zuzugreifen.

- Schneller Vor-/R√ľcklauf: Bildsuchlauf innerhalb der Sequenz durch Anzeigen nur jedes n-ten Bildes.

- R√ľckw√§rtsabspielen: insbesondere f√ľr Videospiele, Lernsoftware und andere interaktive Anwendungen von Bedeutung.

- Audiovisuelle Synchronisation: Audio- und Videosequenz eines Films sollen synchronisierbar sein.

Bilddarstellungen

Wie wird ein Bild √ľberhaupt digital dargestellt?

Das menschliche Auge (genauer gesagt die Rezeptoren auf der Netzhaut) empfängt Lichtwellen verschiedener Wellenlängen, die vom Gehirn als Farben interpretiert werden.

Am Computer gibt es verschiedene Schemata um diese Farbwerte darzustellen. Die wichtigsten f√ľr die Bildcodierung sind RGB (Rot, Gr√ľn, Blau) und YUV (Helligkeit, 2 Farbbalancen) .

Bei der Bildschirmdarstellung l√§sst sich jede Farbe durch ihre Rot-, Gr√ľn- und Blauanteile repr√§sentieren. Da das menschliche Auge nicht mehr als jeweils 256 Abstufungen dieser drei Farben, also insgesamt ca. 16 Millionen Farbwerte, unterscheiden kann, werden beim RGB-Schema 24 Bit f√ľr jeden Bildpunkt (Pixel) belegt (je 8 Bit f√ľr Rot-, Gr√ľn-, Blauwert). Genau genommen kann das Auge sogar nur 60.000 Farbstufen erkennen, es w√ľrden also 17 Bit f√ľr die Darstellung ausreichen, aber das sind leider 2 Byte und 1 Bit, so dass 3 Byte benutzt werden m√ľssen.

Allerdings liegt das Aufl√∂sungsverm√∂gen des Auges f√ľr Helligkeit weit √ľber dem f√ľr Farbunterschiede. Bis zu 600 Helligkeitsstufen k√∂nnen unterschieden werden, also mehr als durch ein Byte darstellbar. Darauf beruht das YUV-Schema, bei dem Y die Helligkeit (Luminanz), U und V die Farbigkeit (Chrominanz) darstellen. U beschreibt die Balance zwischen Rot und Gr√ľn und V die zwischen Gelb und Blau. Daher wird manchmal auch statt U CR(ColorRed) und statt V CB(ColorBlue) verwendet. Durch diese Aufteilung k√∂nnen, entsprechend des menschlichen Sehverm√∂gens, mehr Bit (h√∂here Genauigkeit) f√ľr die Helligkeit als f√ľr die Farbigkeit benutzt werden. Au√üerdem k√∂nnen Grauwertebilder nur durch ihren Luminanzwert beschrieben werden.

Die Transformation von RGB zu YUV kann √ľber eine einfache Matrizenmultiplikation erfolgen:

Das CMY-Schema (Cyan, Magenta, Gelb) hat sich f√ľr die Farbmischung bei Druckern als vorteilhaft erwiesen, ist aber f√ľr dieses Thema bedeutungslos.

Möglichkeiten der Codierung

Wie schon oben erwähnt beruht jede Kompression auf der Reduzierung oder sogar Beseitigung von Redundanzen.

Diese können räumlich, spektral oder bei Filmen zusätzlich noch zeitlich sein.

Räumliche Redundanz bedeutet, dass die gleiche oder zumindest eine ähnliche Bildinformation mehrfach vorkommt, etwa bei sich wiederholenden Mustern.

Die spektrale Redundanz bezieht sich auf √Ąhnlichkeiten der Farbkomponenten, z.B. bei einem einfarbigen Bildausschnitt.

Bei Filmen verändert sich oft nur ein Ausschnitt, z.B. eine Person, während das restliche Bild, der Hintergrund, unverändert bleibt. Dieses bezeichnet man mit zeitlicher Redundanz.

Die Kompressionsverfahren entfernen die gefundenen Redundanzen, idealerweise ohne dass der Betrachter eine Beeinträchtigung der Bildqualität feststellt.

Grundsätzlich lässt sich jeder Kompressionsvorgang in vier Phasen aufteilen, wobei nicht jede Phase bei jedem Verfahren vorhanden sein muss:

- Vorverarbeitung

- reversible Transformation

- Quantisierung

- Umcodierung zur Kompression

Die Vorverarbeitung dient dazu die Bildparameter so zu ver√§ndern, dass nachfolgend eine bessere Kompression m√∂glich ist. Das wird durch Filterung, L√∂schen unerw√ľnschter Bildabschnitte oder auch Transformation der Bildelemente erreicht.

Die reversible Transformation stellt den verlustfreien Teil der Umcodierung dar. Hier werden die Bildelemente bijektiv, daher reversibel, auf eine andere Menge von Bildelementen abgebildet.

Die dritte Phase, Quantisierung, f√ľhrt die Irrelevanzreduktion durch. Sie ist bei den verlustfreien Verfahrenen nicht vorhanden.

Zum Abschlu√ü werden die transformierten und evtl. quantisierten Bildelemente umcodiert, so dass idealerweise h√§ufig vorkommende Elemente kurze, selten vorkommende Elemente lange Codes erhalten. Dies wird Entropiecodierung genannt. Dabei ist Entropie definiert als die untere Schranke f√ľr die Codel√§nge einer Codekomprimierung ohne Beachtung eines Kontextes, also nach vollst√§ndiger Entfernung aller Redundanzen. Dies wird durch Huffman- oder arithmetische Codierung erreicht.

Diese Codierungsverfahren werden bei fast allen Graphikformaten benutzt, darum werden sie schon im Folgenden erläutert:

Huffman-Codierung

Die Idee der Huffman-Codierung geht auf das Prinzip des Morsealphabets zur√ľck. Dort werden den h√§ufig vorkommenden Symbolen (in diesem Fall sind das Buchstaben) k√ľrzere Codes zugeordnet als den seltener vorkommenden. Der Code f√ľr das Symbol 'e' zum Beispiel besteht nur aus einem einzigen Morsezeichen.

Nach Huffman ordnet man alle Symbole zun√§chst nach ihrer H√§ufigkeit in einer Tabelle. Die beiden seltensten erhalten als letzte Codeziffer eine 0 und eine 1. Beide werden in der Tabelle mit der Summe ihrer Wahrscheinlichkeiten zusammengefa√üt. Die H√§ufigkeitstabelle hat damit ein Element weniger. Wieder sucht man die beiden seltensten Elemente und stellt ihrem Code eine 0 und eine 1 vor. Nach Zusammenfassen ihrer Wahrscheinlichkeiten beginnt das Spiel von vorn. Alle Symbole sind codiert, wenn nur noch ein Element in der Tabelle √ľbrig ist.

Arithmetische Codierung

Bei diesem Schema werden die Symbole zunächst in einem Intervall von 0 bis 1 angeordnet. Die Wahrscheinlichkeit eines Symbols entspricht dabei der Länge seines zugehörigen Unterintervalls. Besteht eine Datei aus zehn Symbolen, so gibt es daher zehn Unterintervalle. Je kleiner das zu einem Symbol gehörige Unterintervall ist, desto länger wird sein Codewort, und umgekehrt.

Die Codierung erfolgt dadurch, dass jedem Symbol eine binäre Fließkommazahl zugeordnet wird, die dem Anfang der Position des Unterintervalls entspricht. Aus den Fließkommazahlen wird mit Hilfe der Unterintervalle eine einzige Zahlenfolge gebildet, die letztlich in einen Code umgesetzt wird.

Im Vergleich zur Huffman-Codierung, die jedem Zeichen einen Code zuordnet, ist die arithmetische Codierung mit Codes f√ľr Zeichenfolgen effizienter.

Bildcodierungsformate

GIF

GIF (Graphics Interchange Format) ist sicherlich das bekannteste Bildkompressionsverfahren. Es wurde von Compuserve entwickelt, um die Übertragungszeiten im eigenen Online-Dienst gering zu halten. GIF arbeitet verlustfrei, kann aber nur acht Bits pro Pixel speichern, was eine maximale Farbenzahl von 256 ergibt. Ein GIF-Bild besitzt eine Farbpalette, die bis zu 256 Farben enthalten kann. Je kleiner die Tabelle, desto geringer ist auch der Platzbedarf der Datei. Durch diese Reduzierung der Farben ergibt sich allerdings praktisch doch ein Qualitätsverlust, der sich besonders bei langsamen Farbverläufen bemerkbar macht. GIF verwendet zur Kompression einen LZW-Codierer, der sich wiederholende Symbolfolgen vergleicht. Da dieser Codierer zeilenweise arbeitet, bleibt er z.B. bei waagerechten Farbverläufen wirkungslos.

Die Kompressionsrate erreicht maximal 5:1, etwas mehr f√ľr einfarbige Bilder.

Als Erweiterung bieten sich interlaced GIFs an: Seit 1987 sieht die GIF-Spezifikation die Möglichkeit vor, die Zeilen eines Bildes nicht nacheinander darzustellen, sondern ähnlich der Fernsehröhre versetzt. Wenn in der Datei festgelegt ist, dass zuerst jede zehnte Zeile gezeigt wird, verringert sich die Ladezeit bis zu einer unscharfen Vorschau entsprechend.

Au√üerdem gibt es seit GIF 89a die M√∂glichkeit mehrere GIFs in einer Datei zu speichern und hintereinander abzuspielen. Trotz Farbreduzierung auf das notwendigste Ma√ü und guter Kompression neigen animierte GIFs jedoch dazu, unertr√§glich gro√ü zu werden. Daher eignen sich animierte GIFs lediglich f√ľr kleine bewegte Icons.

Als Nachfolger von GIF versucht sich das relativ neue Format PNG (gesprochen 'ping'; Portable Network Graphics Format) durchzusetzen. PNG codiert ebenfalls verlustfrei, kann aber bei besseren Kompressionsraten als GIF auch TrueColor codieren.

JPEG

JPEG ist ein standardisiertes, verlustbehaftetes Bildkompressionsverfahren, das von der Joint Photographic Experts Group entwickelt wurde. Der zugrundeliegende Algorithmus (DCT - Diskrete Cosinus-Transformation) ermöglicht eine Reduzierung der Daten, ohne dass die Wahrnehmung erheblich beeinträchtigt wird.

Diskrete Cosinus-Transformation (DCT)

Die DCT basiert auf der Fourier-Transformation, die beliebige Signale darstellt als Überlagerung von Sinuswellen verschiedener Frequenzen und Amplituden. Aus der örtlichen Verteilung von Pixelwerten in einem Bild wird nach der Fourier-Transformation eine Frequenz- und Amplitudenverteilung. Große, regelmäßige Flächen im Bild schlagen sich dabei in den niedrigen Frequenzanteilen nieder, feine Details in den hohen.

Zunächst wird jede Komponente des Bildes in YUV-Darstellung in Blöcke aufgeteilt. Meist werden hierzu quadratische Blöcke einer Größe von 8x8 Bildpunkten verwendet. Anschließend wird auf jeden dieser Blöcke die zweidimensionale FDCT (Forward Descrete Cosine Transformation) angewandt. Dadurch werden die Pixelwerte aus dem zweidimensionalen Bereich in den Frequenzbereich transformiert.

Dabei enthält der Wert in der linken oberen Ecke der Matrix die niedrigsten Frequenzanteile. Dieser Koeffizient an der Stelle (0,0) wird normalerweise als DC-Koeffizient, die anderen 63 Koeffizienten als AC-Koeffizienten bezeichnet. Da normalerweise ein starker Zusammenhang zwischen den DC-Koeffizienten zweier aufeinanderfolgender 8x8-Blöcke existiert, wird der DC-Koeffizient als Differenz zum Vorgänger codiert. Die restlichen 63 AC-Koeffizienten werden entsprechend dem Zick-Zack-Muster sortiert.

Die DCT konzentriert die Signalenergie eines Blockes in den 'niedrigen' Koeffizienten, vor allem im DC-Koeffizienten. Die h√∂heren AC-Koeffizienten sind meist 0 oder fast 0, da der √ľberwiegende Anteil der visuellen Information eines Bildes mit kontinuierlich verteilten Werten im Bereich niedriger Frequenzen liegt, da Kanten prozentual nur einen geringen Anteil des Bildes ausmachen.

Quantisierung

Darum werden in der anschließenden Quantisierung zur Irrelevanzreduktion die höherfrequenten Anteile des Bildes geringer gewichtet, als die niederfrequenten, und deren Amplituden gleich null gesetzt.

Der Sinn der Quantisierung besteht u.a. darin, die Qualit√§t des Bildes dem gew√ľnschten Kompressionsfaktor anzugleichen. Durch Quantisierung werden verschiedene eng beieinander liegende Werte auf ein Level zusammengefa√üt. Hierbei wird der Wert aus der DCT durch die Quantisierungsschrittgr√∂√üe Q geteilt und zur n√§chsten ganzen Zahl gerundet. Dabei kann f√ľr jeden der Koeffizienten eine eigene Quantisierungsschrittgr√∂√üe vorgegeben werden.

Da gro√üe Fl√§chen st√§rker auffallen als Bereiche, in denen auf kleinstem Raum viele Farbwechsel stattfinden, werden der DC-Koeffizient und die niedrigen AC-Koeffizienten mit kleinen Quantisierungsschrittgr√∂√üen quantisiert. Daraus folgt eine relativ gro√üe Genauigkeit, w√§hrend die hohen AC-Koeffizienten bei der durchgef√ľhrten Quantisierung fast alle zu 0 werden.

Je detaillierter die Bilddaten sind, desto gröber werden dadurch die Amplituden der zugehörigen Frequenzen aufgezeichnet. Der optimale Satz von Quantisierungskoeffizienten ist noch nicht gefunden. Die meisten Anwendungen benutzen die von der JPEG herausgegebenen Beispielwerte.

Der dadurch entstehende Qualitätsverlust wirkt sich bei Zeichnungen oder textbehafteten Bilder viel stärker aus, als z.B. bei digitalisierten Fotos, da die scharfen Kanten hohe Frequenzen erzeugen, die gerade minimiert werden. Dadurch verwischen bei der JPEG-Kompression vor allem diese scharfen Kanten.

Entropiecodierung

Die Entropiecodierung besteht aus einer Huffman-Codierung. Die Reihenfolge der Codierung hängt davon ab, welche der folgenden 3 Methoden gewählt wurde:

Sequentielle Codierung: Jede Bildkomponente wird in einem Durchgang von links oben nach rechts unten codiert. Dieses Verfahren wird auch als 'Baseline Method' bezeichnet.

Progressive Codierung: Das Bild wird in mehreren Durchgängen codiert, so dass zuerst die wichtigen (DC- und niedrige AC-Koeffizienten) Komponenten codiert werden. Dies ermöglicht durch Nachlieferung der unwichtigen Koeffizienten eine schrittweise Verbesserung der zunächst recht schlechten Qualität. Besonders im Web ist dieses Verfahren sehr beliebt, da das Bild bereits während des Ladevorgangs sichtbar wird.

Hierarchische Codierung: Das Bild wird in mehreren Auflösungen codiert, so dass zuerst die niedrigen Auflösungen decodiert und angezeigt werden können, ohne das Bild komplett zu decodieren. Statt jedes einzelnen Bildes speichert man deren Differenzen ab, was erheblich weniger Speicherplatz benötigt.

In der JPEG-Spezifikation ist auch eine Möglichkeit zur verlustfreien JPEG-Kompression vorgesehen. Sie erreicht aber nur Kompressionsraten von 2:1 und wird deshalb kaum eingesetzt.

Fraktale Kompression

Die fraktale Bildkompression beruht auf der Tatsache, dass in der Natur, wie bei Bildern fraktaler Berechnungen, Selbst√§hnlichkeiten bestehen. Damit ist gemeint, dass scheinbar zuf√§llige Formen im Gro√üen aussehen wie im kleinen. Zum Beispiel treten die Umrisse einer Pflanze auch wieder im Rand ihrer Bl√§tter auf. Eine K√ľstenlinie zeigt vergr√∂√üert immer neue Einbuchtungen und Rinnsale, die denen eines gro√üen K√ľstenabschnittes √§hneln. Solche √Ąhnlichkeiten innerhalb von digitalen Bildern versucht man durch Vergleiche gro√üer mit kleinen Bildbereichen zu ermitteln. Daf√ľr wird das gesamte Bild gleichm√§√üig in kleine Range Blocks eingeteilt. Zus√§tzlich werden, je nach Verfahren, gr√∂√üere Domain Blocks gebildet, die sich auch √ľberschneiden k√∂nnen und nicht das ganze Bild abdecken m√ľssen. Ziel ist es, einen m√∂glichst √§hnlichen gro√üen Bildbereich f√ľr jeden kleineren zu finden. Je gr√∂√üer die Domain Blocks dabei gew√§hlt werden, desto st√§rker die Kompression - desto st√§rker leidet aber auch die Qualit√§t des komprimierten Bildes.

Die √Ąhnlichkeit zwischen Domain- und Range Block muss nicht offensichtlich sein, sondern stellt sich oft erst nach Transformationen wie Spiegelung oder Streckung ein. Insgesamt gibt es acht Typen dieser affinen Transformationen. Mit dazu geh√∂ren Spiegelungen und Rotationen. Jeder Domain Block wird unter Anwendung dieser acht Transformationen mit jedem Range Block verglichen. Da jedoch zwei Bl√∂cke selten perfekt √ľbereinstimmen, wird zus√§tzlich die Distanz (als Quadratsumme der Differenz korrespondierender Pixel) zwischen Domain- und transformierten Range Blocks berechnet. Zwei Bl√∂cke passen dann zueinander, wenn die Distanzwerte zwischen ihnen am geringsten sind. Das transformierte Bild besteht am Ende aus vielen mathematischen Gleichungen, welche die fraktalen Teilbilder darstellen.

F√ľr die Bildung der Domain Blocks und die Vergleichsmethodik gibt es allerdings viele verschiedene Verfahren:

Das Quad-Tree-Verfahren teilt das Bild auf in große quadratische Blöcke. Wenn zu den Domain Blocks kein passender Range Block existiert, findet eine weitere Aufspaltung eines Quadratblocks in vier gleich große quadratische Unterblöcke statt. Dieser Prozeß wiederholt sich, bis zueinander passende Blöcke gefunden werden. Vorteil der Methode: Die Zuordnung größerer Areale mit wenig Detailinformation passiert schneller bei nur geringem Speicherverbrauch.

Eine andere Alternative, die HV-Methode, beginnt damit, das gesamte Bild als einen einzigen Domain Block zu interpretieren. Einen korrespondierenden Range Block gibt es zu Anfang noch nicht. Die Bildaufteilung erfolgt entlang eines Sprungs in der Helligkeitsverteilung (also einer Kante) entweder in horizontaler oder vertikaler Richtung. Die so kreierten Domain Blocks werden genauso immer weiter aufgeteilt, bis zueinander passende Blöcke erscheinen.

√Ąhnliches geschieht bei der Aufteilung durch Triangulation, einem weiteren Verfahren, das ein Anfangsbild rekursiv in Dreiecke entlang der Kanten im Bild aufspaltet. Mit dieser Methode findet man besser zueinander passende Bl√∂cke, die Transformationen wie Rotation und Spiegelung erfordern jedoch einigen Rechenaufwand.

Die Suche nach dem besten Verfahren ist noch Gebiet der Forschung. Die existierenden Strategien bieten allerdings schon hohe Kompressionsraten bei Realbildern und Schwarzweißgraphiken.

Die Vielzahl der Vergleiche bei allen diesen Verfahren erfordern allerdings viel Zeit bei der Codierung. Anfangs dauerte ein fraktaler Kompressionsproze√ü Stunden bis Tage, mittlerweile schaffen das clevere Algorithmen in Minuten. Die Dekompression ist dagegen rasend schnell: In weniger als 16 Iterationen ist die Bildrekonstruktion abgeschlossen. Die Transformationen werden in umgekehrter Richtung abgearbeitet, indem das B√ľndel mathematischer Gleichungen immer wieder auf das Bild angewendet wird. Dadurch stellt sich das urspr√ľngliche Verh√§ltnis von Domain zu Range Blocks wieder ein. Dieses Verfahren wird so lange wiederholt, bis das nach einigen Iterationen erzeugte Bild sich nicht mehr vom Ergebnis der n√§chsten Iteration unterscheidet.

Wavelet-Kompression

Die Struktur des Wavelet-Verfahrens ist der von JPEG sehr √§hnlich, allerdings k√∂nnen anstatt Sinus- und Cosinuswellen verschiedene Wellenformen (Wavelets) als Grundlage benutzt werden. Eine Wavelet-Transformation wandelt das Originalbild in Wavelet-Koeffizienten um, aus denen man Schritt f√ľr Schritt immer gr√∂bere Bildstrukturen herausfiltern kann. Diese Koeffizienten bestehen aus hoch- und tiefpa√ügefilterten Versionen der Bilder und sind in hohem Ma√üe redundant.

Die Wavelet-Transformation zerlegt das Bild in hoch- und tiefpaßgefilterte Anteile. Nach einer Iteration steckt die wesentliche Bildinformation im tiefpaßgefilterten Teilbild, da auch hier der größte Teil der Bildinformation in den niedrigen Frequenzen liegt. Auf dieses Teilbild wird das Verfahren dann erneut angewendet.

Die Filterpaare teilen die Bandbreite des Bildes in zwei Hälften, die eine hoch-, die andere tiefpaßgefiltert. Beide Hälften sind so beschaffen, dass sich bei beiden Bildern jeweils jede zweite Pixelspalte entfernen lässt.

Das Ergebnis: zwei insgesamt 'schmalere' Bilder.

Die gleiche Filterung wird nochmals auf die beiden Bilder angewendet, jetzt allerdings entlang der Vertikalen. Am Ende liegen dann vier gefilterte Bilder vor. Statt jeder zweiten Spalte kann nun jede zweite Zeile entfernt werden. Aus dem Ausgangsbild sind vier verkleinerte Bilder entstanden, wobei eines davon eine Sonderstellung einnimmt: Dieses eine Bild entspricht dem Durchschnittssignal, die anderen drei sind dagegen Detailsignale. Das Durchschnittssignal-Bild lässt sich genauso weiter transformieren und reduzieren - theoretisch so lange, bis es nur noch ein Pixel groß ist. Das ist allerdings nur möglich, wenn die Kantenlängen des Bildes Zweierpotenzen sind. Da das im Allgemeinen nicht der Fall ist, ist es praktischer, bei einer bestimmten Iteration aufzuhören.

Nach dieser Wavelet-Transformation in Vorwärtsrichtung liegen die Teilbilder in Form einer Matrix von Koeffizienten vor.

Die eigentliche Kompression erfolgt dann wie bei JPEG im Quantisierungsschritt. Verschiedene Strategien fassen dabei unwichtige Bilddetails zusammen, sofern man nicht gleich auf sie verzichtet. Koeffizienten mit Werten nahe Null werden je nach Toleranzschwelle gel√∂scht. Nach einer anschlie√üenden Codierung, zum Beispiel mit dem Huffman-Verfahren, liegt das Ergebnis vor. Dieses Verfahren arbeitet im Gegensatz zu allen anderen hier vorgestellten Codierungen global, teilt das Bild also nicht in Bl√∂cke auf. Um aus den Daten wieder ein Bild zu erhalten, werden alle Schritte in umgekehrter Reihenfolge, mit denselben gespiegelten Hoch- und Tiefpa√üfiltern ausgef√ľhrt.

Ein Aspekt dabei, der sich vor Allem bei der Netz√ľbertragung positiv auswirkt ist, dass sehr schnell ein grobes Bild vorhanden ist, dessen Qualit√§t sich w√§hrend der Daten√ľbertragung stetig verbessert.

Die Vielzahl der möglichen Grundwellenformen bewirkt allerdings auch hier, wie bei der Fraktalen Codierung, dass die Suche nach der besten Methode sehr schwierig ist und ein wirkliches Optimum wahrscheinlich nie gefunden wird.

Bei geeignetem Wavelet und Filtern ergeben sich allerdings schon jetzt bessere Kompressionsraten, als bei JPEG.

Videocodierungsformate

H.261

H.261 ist ein Standard f√ľr Videokonferenzen und Videotelefonie √ľber das ISDN-Netz. Diese Anwendungsgebiete setzen voraus, dass sowohl Codierung als auch Decodierung gleichm√§√üig schnell ablaufen.

H.261 beruht auf einer Hybridcodierung (Verwendung mehrerer Codierverfahren) aus der bei JPEG beschriebenen Diskreten Cosinus Transformation (DCT) und der Differenziellen Puls Code Modulation (DPCM).

DPCM

Die DPCM ist eine Pr√§diktionstransformation, d.h. es wird aus der Kenntnis bereits abgetasteter Bildpunkte eine Vorhersage (Pr√§diktion) f√ľr den aktuellen Punkt gemacht. Der transformierte Wert ergibt sich als Differenz zwischen Pr√§diktion und tats√§chlichem Wert und wird als Pr√§diktionsfehler bezeichnet. Bei der Videocodierung findet diese Vorhersage auf der zeitlichen Ebene statt, d.h. es werden die Unterschiede zum vorhergehenden Bild gespeichert.

Durch die Prädiktionstransformation entsteht eine Matrix gleicher Dimension, deren Werte aber nur eine kleine Varianz aufweisen, so dass eine abschließende Entropiecodierung höhere Kompressionsraten erzielen kann.

Funktionsweise von H.261

Bei der Hybridcodierung von H.261 wird die durch DPCM erstellte Pr√§diktion DCT-codiert und quantisiert. Zus√§tzlich kann noch eine vektorielle Bewegungsabsch√§tzung f√ľr Bildteile eingesetzt werden.

Der Codierer erzeugt zwei verschiedene Arten von Bildern: Inter- und Intra-Frames. Die Intra-Frames ben√∂tigen keine weiter Information, um decodiert zu werden, sie sind (im Prinzip) Standbilder. Die Inter-Frames sind 'Zwischen-Bilder', d.h. in Inter-Frames wird nicht das Bild selbst, sondern nur die Differenz zum vorigen Intra-Frame √ľbertragen. Intra-Frames werden (optimalerweise) bei Beginn einer √úbertragung und bei einem Szenenwechsel verwendet. Inter-Frames erm√∂glichen eine k√∂here Kompressionsrate, da nicht nur die r√§umliche, sondern auch die zeitliche Redundanz ausgenutzt werden.

Analog zu JPEG wird das hereinkommende Bild in 8x8-Blöcke aufgeteilt. Anschließend werden vier Luminanz- und die beiden entsprechenden Chrominanzblöcke zu einem Makroblock zusammengefaßt.

H.261 erm√∂glicht eine Anpassung der Bildqualit√§t an die √úbertragungsleistung durch eine Coding-Control-Einheit. Bei fast vollem Ausgabe-Puffer kann durch Wahl eines gr√∂√üeren Q-Faktors eine gro√üz√ľgigere Quantisierung erreicht werden. Au√üerdem kann die Bewegungskompensation ausgeschaltet und auch ganze Bilder ausgelassen werden.

Anschlie√üend wird vom Videomultiplexcodierer die Entropiecodierung durchgef√ľhrt, wobei extrem unwahrscheinliche, d.h. lange Codes, nicht √ľbertragen, sondern durch Escape-Sequenzen ersetzt werden.

Die gepufferte Ausgabe durch den √úbertragungscodierer erfolgt dann mit konstanten Bitraten von n¬∑64 kbit/s f√ľr n ISDN B-Kan√§le.

MPEG

MPEG steht f√ľr Moving Picture Experts Group. Hier werden nicht nur Videobilder, sondern auch Audiosignale komprimiert. Au√üerdem sorgt das Verfahren f√ľr die Synchronisation zwischen Bild und Ton.

MPEG sollte eine Weiterentwicklung des H.261-Standards sein, die bei besseren √úbertragungsraten eine erheblich bessere Qualit√§t bietet und auch asymmetrische Videoanwendungen, d.h. Filme, die einmal mit einigem Aufwand codiert und oft wiedergegeben werden, unterst√ľtzt. Beispiele hierf√ľr sind Unterhaltungsvideos, Pr√§sentationen, Animationen in Lexika, etc.

MPEG-Versionen

Es gibt verschiedene MPEG-Standards; alle derzeit geltenden basieren auf zwei Techniken: Zum einen gibt es die Bewegungskompensation f√ľr die Redundanz der Einzelbilder, die Unterschiede zwischen den einzelnen Bildern der Bildsequenz aufsp√ľrt. Zum anderen verwendet MPEG eine Kompression auf DCT-Basis - ganz nach Art von JPEG.

Das Ziel der stufenweisen Entwicklung von aufeinander aufbauenden Standards waren haupts√§chlich die unterschiedlichen Anforderungen von Video- und Fernseh-Anwendungen. So wurde MPEG-1 f√ľr CD-ROM Video-Anwendungen mit Datenraten um 1,5 Mbit/s optimiert. MPEG-2 wurde dann entworfen f√ľr Anwendungen in der Fernsehtechnik bei h√∂heren √úbertragungsraten und einem Bildaufbau mit Zeilensprung (interlaced), dessen spezielle Eigenschaften auch besondere Verarbeitungsweisen erfordern.

MPEG-3 zielte urspr√ľnglich auf HDTV-Anwendungen. Bei der Entwicklung von MPEG-2 wurde dann jedoch erkannt, dass die MPEG-2 Verfahren mit geringer Verbesserung ihrer Leistungsf√§higkeit imstande sind, Videodaten auch von hochaufl√∂senden Bildern gut zu verarbeiten. Daher wurde MPEG-3 in den MPEG-2-Standard eingebettet.

Neben Entwicklungen von Test- und Simulationsstandards f√ľr die bestehenden Verfahren wird im Rahmen von MPEG-4 an einer neuen Technologie gearbeitet, deren Ziel u.a. die Unterst√ľtzung folgender Anwendungen ist:

· Videotelefon auf herkömmlichen analogen Telefonleitungen

¬∑ Videotelefon √ľber Funkverbindungen

· Datentransfer auf bzw. von Multimedia-Datenbanken

¬∑ Fern√ľberwachung und Fernsteuerung von Industrieanlagen

Die Entwickler von MPEG-4 legen bei ihren Forschungen das Hauptaugenmerk zus√§tzlich auf eine Reihe von Verbesserungen gegen√ľber den beiden bisherigen MPEG Verfahren. Dazu geh√∂ren:

· erhöhte Codiereffizienz zur Realisierung niedriger Übertragungsraten

· inhaltsbezogene Manipulierbarkeit der Bilder und Bildobjekte

· inhaltsbezogene Skalierbarkeit von Bildobjekten

· erweiterte Fehlerrobustheit

Trotz der massiven multinationalen Forschungen in diesem Bereich ist f√ľr MPEG-4 aufgrund der hochgesteckten Ziele das Erreichen eines Internationalen Standards nicht vor 1998 zu erwarten.

Verfahrensablauf

Um sowohl eine hohe Kompressionsrate, als auch wahlfreien Zugriff zu ermöglichen, verwendet man wie bei H.261 eine Mischform aus Intra- und Interframe-Codierung.

Allerdings werden bei MPEG neben Intra-Frames (I-Frames) zwei verschiedene Arten von Inter-Frames verwendet:

· Forward-Predicted Frames (P-Frames) werden durch Differenzbildung zum vorherigen Referenzbild berechnet. Sie werden ebenso wie die I-Frames als Referenzbilder verwendet.

¬∑ Bidirectional-Predicted Frames (B-Frames) erreichen die h√∂chste Kompressionsrate, ben√∂tigen aber zur Berechnung sowohl ein vorheriges als auch ein zuk√ľnftiges Bild. Sie interpolieren also das Bild aus zwei Referenzen.

Um B-Frames zu erm√∂glichen werden zuerst ein I-Frame, dann der n√§chste P-Frame und erst anschlie√üend die dazwischenliegenden B-Frames √ľbertragen. Allerdings entscheidet die Anwendung selbst, in welchem Verh√§ltnis I-, P- und B-Frames generiert werden, so dass Parameter wie Codierungsverz√∂gerung oder Anzahl der M√∂glichkeiten f√ľr wahlfreien Zugriff gesteuert werden k√∂nnen.

Zur Bewegungskompensation verwendet MPEG 16x16-Pixel große Luminanzblöcke, deren Ortsänderung zum vorherigen (und bei B-Frames auch nächsten) Referenzbild berechnet wird.

Diese Bl√∂cke und die zugeh√∂rigen Chrominanzbl√∂cke werden als Makroblock bezeichnet. Die L√§nge der Bewegungsvektoren ist jedoch nicht wie bei H.261 auf 15 Pixel pro Block beschr√§nkt, sondern erlaubt eine Verschiebung √ľber das gesamte Bild. Die Bewegungsvektoren werden als Differenz zu dem Bewegungsvektor des vorherigen Makroblocks codiert, da nah beieinanderliegende Makrobl√∂cke mit hoher Wahrscheinlichkeit nur geringf√ľgig unterschiedliche Bewegungsvektoren besitzen.

Das Ergebnis der Bewegungssch√§tzung kann daf√ľr verwendet werden, zu entscheiden, auf welche der drei Arten ein Bild codiert wird. Finden zu viele √Ąnderungen statt (z.B. bei einem Szenenwechsel) muss ein I-Frame erzeugt werden. Sonst gen√ľgt, je nach L√§nge des Bewegungsvektors, ein P- oder B-Frame.

Der Gesamtablauf besteht wie bei JPEG aus einer Cosinustransformation, einer Quantisierung und einer Entropiecodierung.

Bei der Quantisierung kann jeder Koeffizient einzeln behandelt werden, wobei auch die Bildart (I, P- oder B-Frame) ber√ľcksichtigt werden kann. MPEG stellt daf√ľr vordefinierte Matrizen f√ľr intra- und nonintra-kodierte Makrobl√∂cke zur Verf√ľgung, jedoch besteht die M√∂glichkeit, neue, unabh√§ngige Tabellen zur Quantisierung zu verwenden. Diese werden dann direkt im Videostrom zu Beginn eines jeden Bildes eingetragen.

Die Entropiecodierung erfolgt wie bei H.261. Die Codes bilden sogar eine Übermenge der von H.261 verwendeten, so dass eine Hardwareimplementierung beider Standards möglich ist.

Um das Abspielen der Videos auch auf langsamerer Hardware, oder √ľber langsamere Verbindungsleitungen zu erm√∂glichen, besteht bei MPEG-2 die M√∂glichkeit der geschichteten Bildcodierung. Dabei kann das Video zeitlich, r√§umlich oder qualitativ skaliert werden.

Bei der zeitlichen Skalierung wird nur ein Teil der Bilder des Videos √ľbertragen, was ein st√§rkeres Ruckeln im Ablauf bewirkt.

Bei der r√§umlichen Skalierung wird die Bildgr√∂√üe verkleinert, so dass eine geringere Datenmenge pro Bild √ľbertragen werden muss.

Qualitative oder SNR-Skalierbarkeit (Signal-to-Noise Ratio) wird z.B. durch eine Reduzierung der Farben des Videos durchgef√ľhrt.

Um das zu erreichen, wird das Signal mit mehreren niedrigeren Aufl√∂sungen abgetastet. Aus dem Signal mit der niedrigsten Aufl√∂sung wird ein Signal mit h√∂herer Aufl√∂sung interpoliert, und die Differenz zwischen dem interpolierten und dem tats√§chlichen Signal wird als zweite Schicht zus√§tzlich zu der niedrigsten Aufl√∂sung √ľbertragen. Dieser Proze√ü wird mehrmals wiederholt, um verschiedene Stufen zu erhalten.

F√ľr Spezialanwendungen (TV, HDTV, ...) wurden aber auch einige dieser Parameter (Aufl√∂sung, Frames per Second, Codierungsverfahren) in 'Levels' festgelegt. Dabei wurden die Codierungsverfahren je nach Anforderungen (Geschwindigkeit gegen Kompressionsrate) f√ľr die verschiedenen Anwendungen in unterschiedliche Profiles eingeteilt.

Durch diese Einteilung wird es einfacher, f√ľr eine spezielle Anwendung die besten Einstellungen auszusuchen.

Motion-JPEG

Motion-JPEG ist quasi eine Zwischenstufe zwischen Bild- und Videocodierung, da einfach eine Sequenz von JPEG-Bildern als Video aufgefa√üt wird. Diese Methode nutzt zwar die zeitliche Redundanz nicht aus, erm√∂glicht daf√ľr aber beliebige Filmschnitte und verlangt weniger Aufwand an Hard- oder Software. M√∂glichkeiten zur Synchronisation mit Audiodaten sind allerdings nicht vorgesehen. Es bietet daher nur eine schlechte, daf√ľr aber kosteng√ľnstige Alternative zu MPEG.

Erfolgversprechend sind auch Verfahren, bei denen die Intra-Frames der Videos mit Fraktaler- oder Wavelet-Kompression codiert werden sollen. Diese befinden sich aber noch in der Entwicklung.

Fazit: Welche Bildcodierung wof√ľr?

Das JPEG-Verfahren kommt bei fotografischen Motiven der menschlichen Sichtweise entgegen. Es eignet sich daher f√ľr Portraits, Landschaftsaufnahmen und √§hnliches.

Bei niedrigen Kompressionsraten ist JPEG s√§mtlichen auf Fraktalen basierenden Verfahren √ľberlegen. Das Blatt wendet sich ab Kompressionsraten von 25:1, denn h√∂here Raten ergeben grobe Rasterungen. Bedingt durch das Weglassen ganzer Frequenzbereiche des Ausgangsbildes durch die Diskrete Cosinus-Transformation hat JPEG au√üerdem mit starken Kontrasten Probleme. Dadurch liefert das JPEG-Format aber bei Strichzeichnungen oder Text in Bildern eine wesentlich schlechtere Qualit√§t als GIF.

GIF ist nur f√ľr Bilder mit weniger als 256 Farben sehr gut. Die Kompressionsrate von maximal 5:1 ist zwar im Vergleich zu den anderen Verfahren gering, aber daf√ľr ist es verlustfrei.

Die Wavelet-Kompression zeigt im Vergleich die besten Ergebnisse mit der niedrigsten Fehlerrate bei gr√∂√ütm√∂glicher Kompression eines nat√ľrlichen Bildes. Wann ein Wavelet-Verfahren geeignet ist, l√§sst sich nicht eindeutig sagen. Es gibt eine Vielzahl von Basisfunktionen, die f√ľr verschiedene Bildtypen unterschiedlich gut geeignet sind. Die Kompressions- und Dekompressionszeiten f√ľr Wavelet-Verfahren sind mit denen von JPEG vergleichbar.

Die St√§rke der Fraktal-Kompressoren sind Realbilder. Auch mit hohen Kompressionsraten ist die Qualit√§t gut bis sehr gut. Bei abstrakter Computergrafik liefert ein Fraktal-Kompressor dagegen eher mittlere Qualit√§t. Unerreicht ist die Qualit√§t von fraktal gepackten Schwarzwei√ügrafiken mit harten Kontrasten. Allerdings erfordert die Kompression ungleich mehr Zeit, als die Dekompression. Verbesserte Algorithmen verk√ľrzen die fraktale Kompressionszeit auf teilweise unter eine Minute. Sie kann zus√§tzlich durch den Einsatz spezieller Hardware beschleunigt werden.

Sowohl f√ľr Fraktal- als auch f√ľr Wavelet-Verfahren gibt es allerdings noch eine Menge Forschungsarbeit zu tun.

Quellen:

Heinrichs, Bernd: Multimedia im Netz S.39ff: Bildcodierung und Videokommunikation

c't 11/1996 S.222ff: Handlich bunt - Kompressionstechniken ... im Vergleich

c't 7/1996 S.206ff: Mischobst - Grafikformate f√ľr WWW-Dokumente

c't 11/1994 S.258ff: Flinkes Wellenspiel - Signalverarbeitung mit Wavelets

The JPEG Payground II

The Almighty JPEG FAQ

Introduction to JPEG

Beschreibung des Wavelet-Verfahrens

Wavelets

MPEG (I+II)

MPEG

MPEG-FAQ 4.1

4695 Worte in "deutsch"  als "hilfreich"  bewertet