Motivation

1

Ziel der Kompression multimedialer Daten

• Ziel ist die Kompression multimedialer Daten:
  • Reduktion der Datenmenge
  • Vermeidung von Qualitätsverlusten
• Digitale, multimediale Dateien sollen zugänglich sein für:
  • bestehende Nachrichtenübertragungssysteme (Telefonkabel, Satelliten- und terrestrische Antennensysteme, etc)
  • bestehende Speichersysteme (PC-Festplatten, CDs und DVDs, Servers, etc.)

Anwendungen

• Audio - Digitale Telephonie, Handy, Musiktauschbörsen im Internet, digitales Radio, Radioprogramme im Internet
• Bild - Bilder auf Webpages, digitale Fotokameras
• Video - Spielfilme auf DVD, digitales Fernsehen, Videoclips via Internet

2

Ziel der Kompression multimedialer Daten

Ziel der Kompression ist es, durch verschiedene Verfahren das Datenvolumen zu reduzieren. Multimediadaten (Video, Bilder, Audio) benötigen beträchtlichen Speicherplatz. Durch Kompression, das heißt gezielte Reduktion der Datengröße, können auch digitale Audio-, Video und Bilddaten einerseits gespeichert werden, andererseits können sie über verschiedenste Medien übertragen werden.Modul „Komprimierung von Mulzuimediadaten“ bietet den Studenten einen Einblick in die Funktionsweisen der unterschiedlichen Algorithmen zur Datenkompression und Kodierung multimedialer Daten. Hauptaugenmerk wird dabei auf die Standards der ISO135 gelegt: MPEG31 (für Video und Audio), JPEG29 und JPEG2000 (für Bild).

Anwendungen

Audio

Audiodateien können als komprimierte Dateien via Internet übertragen werden. Internetradiostationen können via Telefonleitungen empfangen werden, ohne dass die Qualität des Audiosignals trotz geringer Bandbreite des Mediums stark beeinträchtigt ist. Auch digitales Radio (terrestrisch, Satellitenempfang) ist nur mit komprimierten Audiodateien möglich.

Bilder

Bilder können auf Webseiten ohne störende Wartezeiten angezeigt werden. Kleine digitale Fotokameras speichern Fotos auf einem internen Speichermedium.

Video

Abendfüllende Spielfilme können auf einer einzigen DVD gespeichert werden, Komprimierte Videodaten erlauben die Vorteile des digitalen Fernsehens zu nutzen (siehe Lerneinheiten Video- und Fernsehnormen, Der MPEG-2 Standard und MPEG-2 Levels und Profiles). Stark komprimiertes Video ermöglicht Broadcasting im Internet.

Überblick

1

auto

• Basistechniken
  • Entropiekodierung
    • Beseitigung von statistischen Redundanzen
  • Transformationskodierung
    • keine Datenreduktion
    • Multimediale Inhalte in alternative Repräsentationsformen transferiert
    • Alternative Repräsentationsformen besser für Datenreduktion geeignet
    • Wichtige Transformationen
      • Fouriertransformation
      • Wavelet Ttransformation
• Audiokompression
  • Erklärung derBegriffe
    • Subband Kodierung
    • Skalierung
    • Quantisierungsrauschen
    • Maskierungseffekt
  • Datenreduktion durch perzeptuelle Kodierung
    • nur Daten, die gehört werden, werden kodiert
• Bildkompression
  • JPEG
    • Herz ist DCT
  • JPEG2000
    • Herz ist Wavelettranformaiton
  • weitereFormate
    • bmp, tiff, png ,gif
• Videokompression
  • Zwei Dimensionen der Redundanz
    • Örtliche Redundanz
      • Wird beseitigt durch Intra-Kodierung
        • funktioniert ähnlich wie bei JPEG
    • Zeitliche Redundanz
      • Wird beseitigt durch Inter-Kodierung
        • Bewegungsschätzung und Bewegungskompensation
  • MPEG-1
    • Einfachster Videostandard
  • MPEG-2
    • digitales Fernsehen
    • Archivierung von digitalem Video in hoher Qualität
  • MPEG-4
    • Erweiterung von MPEG-2 für geringe Datenraten
    • Objektbasierte Kodierung
  • ITU Standard
    • Standard für Videokonferenzen

2

auto

Das Modul „Komprimierung von Multimedia Daten“ besteht aus 35 Lerneinheiten und befasst sich mit 4 Hauptthemen: Basistechniken zur Datenkompression, Audiokompression, Bildkompression und Videokompression. Im Folgenden wird ein kurzer Überblick über die abgehandelten Themen gegeben.

Basistechniken

Hier lernt die Studentin grundlegende Techniken zur Datenreduktion. Die beschriebenen Algorithmen können unabhängig vom Datentyp angewendet werden, d.h. sie können bei Audiodaten genauso wie bei Video- oder Bilddaten zum Zwecke der Datenreduktion verwendet werden. In den meisten multimedialen Anwendungen gehen diese Algorithmen dann als Teil einer Hybridkodierung903 in die Berechnung ein. Eine wichtige Basistechnik ist die Entropiekodierung (Lauflängen-, Huffman-, LZ- und LZW- und Arithmetische Kodierung), die es erlaubt, statistische Redundanzen zu beseitigen. Eine ebenfalls elementare Technik ist die Transformationskodierung. Es findet hier allerdings keine eigentliche Kompression statt, vielmehr werden hier durch geeignete mathematische Prozeduren multimediale Inhalte in alternative Repräsentationsformen transferiert, welche eine effektivere Datenreduktion versprechen. Es werden die Fouriertransformation - inklusive deren Derivate wie Diskrete Fouriertransformation (DFT), Fast Fouriertransformation (FFT), Short Time Transform (STT), Diskrete Cosinustransformation (DCT) - und die Wavelettransformation im Detail besprochen.

Audiokompression

Das Zauberwort der Audiokompression heißt „Perzeptuelle Kodierung“: Die Algorithmen nutzen die perzeptuellen Eigenschaften des menschlichen Hörsystems. Psychoakustische Erkenntnisse liefern dabei die Grundlagen, um entscheiden zu können, welche Werte kodiert werden müssen und welche Werte weggelassen werden können, da sie ohnehin von unserem Ohr nicht gehört werden. Um diese Techniken im Detail verstehen zu können, erfährt man hier über Psychoakustik, Quantisierungsrauschen, Signal to Noise ratio, Nyquist-Shannon Theorem, Subbandkodierung, Filterbanken und Skalierung des Dynamikbereiches eines Audiosignals. Als Vertreter einfach aufgebauter Encoder werden hier MPEG-1/Audio Layer1 und Layer2 beschrieben. Der hochkomprimierende MP3 Encoder ist zwar auf derselben simplen Architektur aufgebaut, ist aber in seiner Funktionsweise weitaus komplexer. Er verwendet eine höchst anspruchsvolle Iterationstechnik um Wortlänge und Skalierung der Werte zu berechnen. Weiters werden die Subbands mittels einer zusätzlichen MDCT493 in feinere Frequenzbänder aufgelöst, eine anschließende Huffmankodierung erhöht den möglichen Kompressionsfaktor. MPEG-2/AAC ist eine vollkommene neue MPEG Architektur, die keine Rücksicht auf Rückwärtskompatibilität in Bezug auf MPEG-1/Audio nimmt. Grundsätzlich folgt AAC18 den selben Paradigmen wie MP3, nur in verbesserter Form. Als einziger nicht-MPEG Encoder wird hier der AC-3 Encoder der Firma Dolby vorgestellt. Er spielt eine dominante Rolle für Kinoproduktionen, und somit auch für Video-DVDs und zukünftig auch für digitales Fernsehen. Eine Lerneinheit beschreibt den MPEG-4/Audio Standard. MPEG-4 ist einerseits eine Erweiterung des MPEG-2 Standards, andererseits führt er die „objektorientierte Kodierung“ ein. Es gibt eigene Tools für Sprachkodierung (z.B. CELP452), synthetische Klänge, synthetische Sprache.

Bildkompression

JPEG ist zurzeit der weltweit am meist verbreitete Standard für digitale Bilder. Ähnlich wie bei Audiokompressionsalgorithmen, werden perzeptuelle Eigenschaften des menschlichen Seesinns zur Datenreduktion genützt. Das Herz der JPEG Architektur ist die DCT242. Sie transformiert die Helligkeit/Farbwerte der Bildpunkte in Frequenzwerte, die Aufschluss über die Struktur des betrachteten Bildabschnittes geben und sich für eine Datenkompression besser eignen. Der Transformation folgt die Quantisierung (entspricht perzeptueller Bewertung) und wahlweise Huffman- oder Arithmetische Kodierung (siehe Entropiekodierung). JPEG2000 ist der neue ISO135 Standard und sollte JPEG29 allmählich ablösen. JPEG2000 arbeitet mit einer Wavelettransformation, die eine bessere Performance vor allem bei höheren Kompressionsraten liefert, da hier keine störenden Blockartefakte sichtbar werden. Als Entropiekodierung kommt die „Binäre Arithmetische Kodierung“ zum Einsatz. Zusätzlich zur verlustbehafteten, bietet JPEG2000 auch verlustlose Kompression. In einer eigenen Lerneinheit werden andere gebräuchliche Bildformate beschrieben: PNG280 und Gif117 für Grafiken, weiters das tiff 518und das bmp96 Format.

Videokompression

Unkomprimierte Videodaten weisen in zwei Dimensionen Redundanzen auf: In der zeitlichen und in der örtlichen Dimension. MPEG und ITU Videostandards beseitigen örtliche Redundanzen ähnlich dem JPEG Standard. Man spricht hier von Intra-Kodierung. Zeitliche Redundanzen werden durch die Inter-Kodierung entfernt: Die grundlegende Technik dafür ist die Bewegungsschätzung und die Bewegungskompensation. MPEG-1 ist der simpelste Videostandard. MPEG-2 ist der Standard für digitales Fernsehen und für die digitaler Archivierung komprimierter Videos in hoher Qualität (z.B. Video für DVD311). Auf Grund der hohen Anzahl an Anwendungsmöglichkeiten wird der MPEG-2 Standard in „Levels und Profiles“ unterteilt. Ein weiterer wichtiger Teil des MPEG-2 Standards ist die „Interlaced Kodierung“. MPEG-4 schließlich ist nicht nur eine Erweiterung des MPEG-2 Standards mit zusätzlichen Features wie Kodierungstools für besonders geringe Datenraten, sondern führt zusätzliche, objektbasierte Kodierungstechniken ein. Der ITU316 Standard beschreibt Kodierungsverfahren für Videokonferenzen: Es werden hier die beiden ITU316-Videoencoder H.261 und H.263 erklärt, weiters der H.314 Standard – Bildtelefonie via konventionellen Telefonleitungen mittels stand-alone Geräten – vorgestellt (siehe Lerneinheit Standards für Videokonferenzen).

Begriffe

1

Codierung

Jedem Zeichen eines Zeichensatzes wird ein Zeichen eines anderen Zeichensatzes zugeordnet.

Kompressionsrate

• Kompressionsrate = komprimierte Dateiengröße : unkomprimierte Dateiengröße
• Angabe der Kompressionsrate nicht eindeutig festgelegt
• oft verwendete Beschreibung der Kompressionsrate
  • 1:n - komprimierte Datei um ein n-tel kleiner als Original
  • n% - komprimierte Datei n% kleiner als Original

Encoder/Decoder

• Encoder - wandelt unkomprimierte in komprimierte Datei um
• Decoder - wandelt komprimierte in unkomprimierte Datei um

2

Codierung

Die Codierung von Information ist die Grundvorrausetzung dafür, die Information elektronisch zu speichern, verarbeiten und übermitteln zu können. rech2002, 68

Nachricht, Zeichen und Zeichensatz in der Codierung

Eine zusammenhängende Menge von Daten heißt Nachricht. Jede Nachricht besteht aus Zeichen eines bestimmten Zeichensatzes (=Menge der verfügbaren Zeichen). Bei der Codierung wird jedem Zeichen eines Zeichensatzes ein Zeichen eines anderen Zeichensatzes zugeordnet. henn2001,33

Binäre Codierung von Buchstaben

Wenn ich die Buchstaben A bis Z (=Quellzeichensatz) binär codieren will, so wird jedem Buchstaben (=Quellzeichen) eine Folge von 0en und 1en (=Zielzeichen) zugewiesen. Die Menge der binären Zahlen der Tabelle ist der Zielzeichensatz. Genauso gut könnte man die Buchstaben auch dezimal codieren.

Kompressionsrate

AUTO

Die Effizienz eines Verfahrens wird durch die Kompressionsrate bestimmt. Sie gibt den Grad der Kompression wieder und wird durch das Verhältnis von Volumen der Ausgangsdaten zu komprimierten Daten definiert. Die Kompressionsrate ist der Faktor, um den die Datenmenge durch die Kompression verringert wurde.

Komprimierung im Verhältnis 4:1

4:1 bedeutet beispielsweise eine Komprimierung auf ein Viertel der ursprünglichen Datenmenge.

AUTO

Es gibt kein einheitliches Kompressionsmaß. Demnach bedeutet Kompression auf 25%, Kompression um 75% oder Kompressionsfaktor 4 das Gleiche.

Encoder/Decoder

Kompression wird oft verwendet, um die Datenmenge, die über ein Netzwerk transportiert werden muss, zu reduzieren. Deshalb wird in Zusammenhang mit Kompressionsverfahren oft von Sender und Empfänger gesprochen.

Sender

Dabei meint man mit Sender denjenigen, der die Daten komprimiert. Durch das Anwenden eines speziellen Algorithmus wird also die Datenmenge reduziert. Diese Operation wird vom Encoder durchgeführt.

Empfänger hals2000, 116

Auf der anderen Seite erhält der Empfänger die komprimierten Daten. Ein umkehrender Algorithmus zur Dekompression sorgt dafür, dass dem Empfänger wieder die die Ausgangsdaten (oder in manchen Fällen annähernd die Originaldaten) zur Verfügung stehen. Diese Arbeit wird vom Decoder erledigt.

Lokale Archivierung

Nicht immer gibt es bei der Kompression Sender und Empfänger: z. B. wenn Daten lokal archiviert werden. Die Übertragung über das Netzwerk wird aber oft als Modell herangezogen, um ein bestimmtes Verfahren zu erklären. Speichert man eine komprimierte Nachricht am eigenen PC, so kann man dies auch als Spezialfall des obigen Modells sehen, in dem Sender und Empfänger ident sind.

Klassifikation von Komprimierungsverfahren

1

Zwei Klassifizierungsmöglichkeiten

Klassifikation nach Verlustbehaftung

• Verlustfreie Komprimierung
• Verlustbehaftete Komprimierung

Klassifikation nach Art der Codierung

• Entropiecodierung
• Quellencodierung

2

Zwei Klassifizierungsmöglichkeiten

Um die Komprimierungsverfahren klassifizieren zu können, trifft man folgende Unterscheidungen:

Klassifikation nach Verlustbehaftung

Komprimierungsverfahren sind:

• verlustfrei oder
• verlustbehaftet

Klassifikation nach Art der Codierung

Bei der Art der Codierung unterschiedet man zwischen:

• Entropiecodierung und
• Quellencodierung

Verlustfreie/-behaftete Codierung

1

Verlustfreie Codierung

• kein Informationsverlust
• reversibel - Decoder kann Original vollständig regenerieren
• mässige Kompressionsrate

Verlustbehaftete Codierung

• Informationsverlust
• irreversibel -Original aus komprimierter Datei nicht mehr vollständig regenerierbar
• hohe Kompressionsrate

2

Verlustfreie Codierung hals2000, 117

Das Ziel der verlustfreien Kompression ist es, die Datenmenge so zu reduzieren, dass nach Anwenden eines entsprechenden Algorithmus zur Dekomprimierung die gesamte Information erhalten bleibt. Vorübergehend wird von den ursprünglichen Daten ein Abbild erzeugt, das zwar nicht ident ist, aber dieselbe Information trägt. Diese Kompressionsverfahren sind reversibel, können also ohne Informationsverlust rückgängig gemacht werden. Ein solches Verfahren muss z.B. zur Kompression einer Textdatei verwendet werden, denn hier ist wichtig, dass der Inhalt nicht verfälscht wird.

Verlustbehaftete Codierung hals2000, 117

Im Gegensatz dazu erzeugen verlustbehaftete Verfahren kein genaues Abbild der Daten, sondern eine Version die vom Empfänger als echte Kopie erachtet wird. Dabei treten mehr oder weniger unbedeutende Informationsverluste auf. Die Kompressionsrate ist höher, je weiter die Version vom Original entfernt ist. Als Anwendungsgebiet eignen sich besonders Bilder, Videos und Audiodaten. Das Auge beziehungsweise das Ohr kann hier kleine Abweichungen nicht wahrnehmen oder die Abweichungen werden nicht als störend empfunden.

Verlustfreie vs. verlustbehaftete Kompression

Es mag vorteilhaft erscheinen, unabhängig vom Medientyp verlustfreie Kompression zu verwenden. Da aber die verlustbehafteten Verfahren weit höhere Kompressionsrate erreichen, ist ihr Einsatz z.B. für digitales Video unerlässlich.

Entropie-/Quellenkodierung

1

Entropiecodierung

• verlustfrei
• Kompressionsprinzip - je höher Auftrittswahrscheinlichkeit eines Zeichen, desto geringer dessen Informationsgehalt

Quellencodierung

• meist verlustbehaftet
• Kompressionsprinzip - betrachtet und nutzt Semantik multimedialer Daten

Hybridcodierung

• meist verlustbehaftet
• Kompressionsprinzip - mehrstufige Kompression:
  • Stufe 1 - Quellencodierung
  • Stufe 2 - Entropiecodierung
• sehr hohe Kompressionsraten
• die meisten Kompressionstechniken für multimedialer Daten verwenden Hybridcodierung

2

Entropiecodierung

Der Begriff der Entropie kommt aus der Informationstheorie. Die Entropie bezeichnet den mittleren Informationsgehalt einer Quelle (Nachricht). Der Informationsgehalt eines Zeichens hängt von der Auftrittswahrscheinlichkeit ab und ist umso größer, je kleiner die Auftrittwahrscheinlichkeit ist. rech2002, 195

Die Entropiecodierung ist verlustfrei und auf alle Informationstypen gleichermaßen anwendbar. Die Bedeutung der digitalen Werte ist hier irrelevant. Sie nutzt statistische Eigenschaften (z.B. Häufigkeit eines Zeichens) für eine effiziente Repräsentation der Information aus. Trotzdem die Darstellung der Information anders zu den Ausgangsdaten ist, können diese vollständig rekonstruiert werden. hals2000, 118 gibb1998, 117

Quellencodierung

Die Quellencodierung oder auch Source Coding genannt, nützt die Semantik des Eingabedatenstroms. In den meisten Fällen sind solche Verfahren verlustbehaftet. Die zu codierenden Daten haben eine enge Beziehung zum Endergebnis, sind diesem aber meistens nur ähnlich und stellen nicht die gleiche Information dar. Je nach Medientyp können bestimmte Informationen weggelassen werden, ohne dabei subjektiv eine Qualitätsverschlechterung zu bemerken.

Hybridcodierung

Unter Hybridcodierung versteht man ein zusammengesetztes Verfahren, welches die Vorteile beider Codierungen verbindet. Meist wird dies in zwei Stufen realisiert:

• In der ersten Stufe wird z.B. die Dateigröße durch einen geeigneten Quellencodierungsalgorithmus verringert. Dabei geht Information verloren.
• Im zweiten Schritt werden diese Daten noch mal durch Entropiecodierung reduziert. In diesem Schritt bleibt die Information aus der ersten Stufe vollständig erhalten.