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