Kurs 21796

Themen

Einführung

Einführung in die Informationstheorie (Petra Weiler und Ingmar Rosenhagen)

Die auf Claude Elwood Shannon basierende Informationstheorie (auch Shannon Theorie genannt) untersucht die Darstellung, Speicherung und den Austausch von Informationen und liefert daher viele theoretische Grundlagen für die Kodierung und Kompression von Multimediadaten. Ziel dieser Beiträge ist, diese Grundlagen zu skizzieren. Insbesondere sind die Begriffe Informationsgehalt, Entropie und Redundanz - so weit möglich auch mit Bezug zur Kompression von Multimediadaten - einzuführen. Einen umfassenden und auf Originalliteratur aufbauenden, aber nicht immer leicht zugänglichen Überblick liefert [1], weitere Quellen sind selbst zu erschließen. Bitte setzen Sie, wo möglich, Originalliteratur ein, da Sekundärliteratur nur bedingt zitierfähig ist .

[1]Sergio Verdú: Fifty Years of Shannon Theory. IEEE Transactions on Information Theory 44(6): 2057-2078 (1998) - ftp://stat-ftp.berkeley.edu/pub/users/binyu/212A/papers/verdu.pdf

Aus der Bildkodierung (Grundlagenalgorithmen)

Datenkompression nach Abraham Lempel und Jacob Ziv (Thalayasingam Kokulathasan)

Im Kurs Multimediatechnologie II ist Ihnen der Begriff LZW bereits begegnet, zu GIF heißt es dort nämlich: "Pixelfarben werden durch den LZW-Algorithmus (Lempel-Ziv-Welch) mit variabler Längenkodierung komprimiert", und auch bei TIFF ist eine LZW-Kompression möglich. Nachdem im Kurs die auf Lempel und Ziv basierenden Algorithmen leider nicht detailliert vorgestellt werden konnten, ist die Vorstellung von LZ 77 [2], LZ 78 [3] und LZW [4] Ziel dieser Beiträge. Geben Sie wo möglich Beispiele für den Einsatz der Verfahren in der Multimediatechnologie.

[2] Jacob Ziv, Abraham Lempel: A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory 23(3): 337-343 (1977) - http://www.cs.uni-paderborn.de/fileadmin/Informatik/AG-Boettcher/Lehre/WS_07_08/prosem-ws07/ziv_lempel_1977_universal_algorithm.pdf
[3] Jacob Ziv, Abraham Lempel: Compression of Individual Sequences via Variable-Rate Coding. IEEE Transactions on Information Theory 24(5): 530-536 (1978) - http://citeseer.ist.psu.edu/cache/papers/cs/27647/http:zSzzSzcompression.graphicon.ruzSzdownloadzSzarticleszSzlzzSzziv_lempel_1978_variable-rate.pdf/ziv78compression.pdf
[4] Terry A. Welch: A Technique for High-Performance Data Compression. IEEE Computer 17(6): 8-19 (1984) - http://www.informatik.uni-freiburg.de/~ipr/ipr_teaching/ss_05/lzw.pdf

Deflate (Lars Weber)

Deflate basiert auf den Ideen von Lempel und Ziv und kombiniert den Lempel-Ziv-Storer-Szymanski-Algorithmus und die Huffman-Kodierung. Ziel des Beitrags ist, ausgehend vom LZ 77 (s.o.) die Entwicklung über den Lempel-Ziv-Storer-Szymanski-Algorithmus [5] zu skizzieren und den Deflatealgorithmus [6] vorzustellen. Geben Sie wo möglich Beispiele für den Einsatz der Verfahren in der Multimediatechnologie.

[5] James A. Storer, Thomas G. Szymanski: Data compression via textural substitution. J. ACM 29(4): 928-951 (1982) - http://portal.acm.org/citation.cfm?doid=322344.322346
[6] RFC 1951 - http://tools.ietf.org/html/rfc1951

Aus der Audiokodierung (Verlustlose & Verlustbehaftete Kodierung)

MPEG-4 Audio Lossless Coding (Marc Oliver Sieben)

Verlustlose Audiostandards erlauben, einen Audiostrom so zu komprimieren, dass er originalgetreu (also Bit für Bit identisch) wieder hergestellt werden kann, während verlustbehaftete Verfahren wie MP3 versuchen, Kodierfehler lediglich für den Menschen unhörbar zu maskieren (wie es im Kurs Multimediatechnologie II thematisiert wurde). Ein recht junges, verlustloses Verfahren basiert im Wesentlichen auf Arbeiten der Technischen Universität Berlin und wurde als MPEG-4 ALS (bzw. als ISO/IEC) standardisiert. Ziel des Beitrags ist, MPEG-4 ALS vorzustellen und insbesondere auf die Besonderheiten der Kodierung einzugehen. Eine Einführung sowie Literaturhinweise können bei der TU Berlin unter http://www.nue.tu-berlin.de/mp4als gefunden werden.

Vorbis (Johannes Lindemann)

Vorbis ist ein freier, verlustbehafteter Audiocodec, der z.B. in Konkurrenz zu MP3 steht und als Ogg Vorbis durchaus bekannt ist. Insbesondere aber Pläne, in HTML 5 ein Audio-Tag einzuführen, dass das Abspielen von Audiodateien nativ unterstützen soll, haben Vorbis in den Blickpunkt der Öffentlichkeit gerückt, denn phasenweise sollte die Unterstützung dieses Codecs verpflichtend für alle HTML-5-konformen Browser sein (derartige Pläne scheinen derzeit verworfen, aber mit Firefox und Opera gibt es bereits zwei Browser, die diesen Codec nativ unterstützen). Ziel der Beiträge ist, den Vorbis Codec vorzustellen. Zum einen darf dabei gerne - da Referenzimplementierungen frei zugänglich sind - auf die softwaretechnische Umsetzung eingegangen werden, zum anderen bieten sich Vergleiche zu MPEG-4 ALS (s.o.) als verlustfreien Codec und MP3 als alternativen verlustbehafteten Codec an. Dokumentation zu Vorbis kann unter http://xiph.org/vorbis/doc/ bezogen werden, unter http://xiph.org/vorbis/ ist eine Implementierung verfügbar.

Aus der Videokodierung

Theora (entfällt)

Was Vorbis für das geplante Audio-Tag in HTML 5 ist, ist Theora für das Video-Tag in HTML 5. Auch in zwei Beiträgen ist sicher keine umfassende Darstellung aller Eigenheiten und Besonderheiten des Codec und seiner Verfahren möglich. Verschaffen Sie sich daher einen Überblick und wählen Sie interessante Aspekte aus (also insbesondere Aspekte, die unser umfangreiches Wissen zu Videokodierung aus Multimediatechnologie I ergänzen oder in Theora eine alternative Umsetzung gefunden haben) und ordnen Sie die Darstellung in den Kontext aus Multimediatechnologie I ein. Erste Informationen finden Sie unter http://theora.org/. Da dort auch eine freie Implementierung zur Verfügung steht, können Sie gerne auf mögliche Softwarearchitekturen eingehen. Bezüglich der Audiokodierung sollten Sie sich im Wesentlichen auf die Vorbis Beiträge stützen (sofern möglich und nötig).

H.264 Encode mit Hardwarebeschleunigung (Thomas Schmid)

Asymmetrische Kodierung erlaubt, die Dekodierung eines Datenstroms einfach zu halten, während die Kodierung durchaus rechenaufwändig und komplex sein kann. Zu diesen asymmetrischen Verfahren gehören z.B. MP3, aber auch H.264 (MPEG-4 AVC). Wie [7] beschreibt, ist die H.264 Kodierung so aufwändig, dass gängige Systeme gerade mal mit 25% der Abspielgeschwindigkeit (trotz voller Auslastung der Rechenkapazitäten bei der Kodierung, im Gegensatz natürlich zur Dekodierung) kodieren. Ziel des Beitrags ist, ausgehend vom Open Source Kodierer x264 (http://www.videolan.org/developers/x264.html) die Kodierung von H.264 Datenströmen zu beschreiben (viele Grundlagen wurden ja schon in Multimediatechnologie 1, Kurseinheit 7, Kap. 7.2 gelegt, hier geht es nun um eine konkrete Umsetzung des Standards, Sie ergänzen in Ihrem Beitrag das "was" Wissen aus dem Kurs durch "wie" Wissen) und dabei den Blick auf die Möglichkeiten von Kodierer mit Hardwarebeschleunigung zu weiten.

[7] Hartmut Gieselmann, Volker Zota: Videonachbrenner - H.264-Encoder mit Hardware-Beschleunigung, c't 20/2009, S. 160 - 167

Hinweise zur Teamarbeit

Einige Themen sind umfangreich genug, um auf ihnen basierend ggf. zwei eigenständige Vorträgen zu gestalten. Sie können gerne auf der Anmeldung angeben, mit wem Sie zusammenarbeiten möchten, Sie können sich aber auch allein für diese Themen melden. Wir werden dann ggf. die Teambildung vornehmen und den Kontakt zwischen Ihnen vermitteln.

Themen mit Teamarbeit werden von (bis zu) zwei Studierenden gemeinsam bearbeitet und sind selbstständig untereinander aufzuteilen.

Insbesondere in der Einarbeitungsphase bietet Teamarbeit die Chance, sich mit einem Partner auszutauschen und gemeinsam Literatur zu erschließen und auszuwählen. Nachdem Sie aber die interessanten Aspekte identifiziert haben, sollten sie diese untereinander aufteilen, denn letztendlich muss jeder von Ihnen eine eigene Ausarbeitung anfertigen und einen eigenen Vortrag halten. Aber auch in dieser Phase der Arbeit kann es sehr gewinnbringend sein, sich mit einen Kommilitonen, der im gleichen Themengebiet arbeitet, auszutauschen. Diese Möglichkeit haben Sie bei den Solothemen nicht. Bedenken Sie aber bitte auch, dass Teamarbeit entsprechende Verantwortung mit sich bringt, da Ihr Teampartner sich auf Absprachen mit Ihnen verlassen können muss.

Anforderungen/Vorgehen

Informationen zur Bearbeitung Ihres Themas und zu den Anforderungen an Ihre Ausarbeitung und Ihren Vortrag finden Sie in den Informationen zum Seminar, die Sie auf dieser Homepage unter Materialien herunterladen können. Bitte Lesen Sie sich diese Informationen schon vor der Bearbeitung Ihres Themas frühzeitig durch, um sich ggf. auch mit entsprechenden Programmen (z.B. Latex) vertraut machen zu können.

Ablauf

* Bitte geben Sie nach Möglichkeit eher ab, so haben wir mehr Zeit, Ihre Vorarbeit zu korrigieren, und Sie haben anschließend auch mehr Zeit, unsere Korrekturen einzuarbeiten. Bitte unterschätzen Sie den Arbeitsaufwand zum Einarbeiten von Korrekturen nicht.

Das Seminar findet in der FernUniversität in Hagen (Universitätsstraße 27, Philipp-Reis-Gebäude, Raum 103) statt. Die genauen Zeiten werden wir Ihnen noch mitteilen und hängen von der genauen Anzahl der Vorträge ab. Die Bewertung Ihrer Leistung erfolgt anhand der korrigierten Ausarbeitung, Ihres Vortrages samt Folien und Ihrer Mitarbeit im Seminar.

Anmeldung zum Seminar

Bitte kopieren Sie folgende Vorlage in eine E-Mail, füllen Sie diese vollständig aus, und senden Sie sie bis zum 18.04.2010 an Daniel.Schulte<at>FernUni-Hagen.de. Geben Sie bitte ggf. in der E-Mail an, mit wem Sie im Team arbeiten möchten (nicht zwingend notwendig, wie oben gesagt bilden wir ansonsten die Teams und stellen den Kontakt zwischen Ihnen her).

Name:

Vorname:

Matrikelnummer:

Bevorzugte E-Mail Adresse*:

Telefonnummer:

Themenprioritäten:

___ Einführung in die Informationstheorie (ggf. im Team)

___ Datenkompression nach Abraham Lempel und Jacob Ziv (ggf. im Team)

___ Deflate

___ MPEG-4 Audio Lossless Coding

___ Vorbis (ggf. im Team)

___ Theora (ggf. im Team)

___ H.264 Encode mit Hardwarebeschleunigung

(Bitte versehen Sie alle Themen mit Prioritäten, 1 ist die höchste Priorität. Alle nicht ausgefüllten Themen erhalten automatisch die höchste noch nicht von Ihnen vergebene Priorität. Weitere Informationen zu den Themen finden Sie auf der Internetseite des Seminars.)

Die Informationen zum Seminar Multimediatechnologie im SS 2010 habe ich zur Kenntnis genommen.

* Die Teamarbeit wird per E-Mail initiiert werden (Sie können danach gerne auf andere Kommunikationsmedien ausweichen). Darüber hinaus werden wir wichtige Informationen zum Seminar per E-Mail an Sie senden.