WiSe 20/21: Datenkompression
Heiko Schwarz
Kommentar
Die Datenkompression stellt eine Technologie dar, welche zahlreiche Anwendungen in unserem Informationszeitalter erst ermöglich. Obwohl es der Endnutzer oft nicht bemerkt, verwenden wir sie täglich beim Musik hören, Bilder und Videos anschauen, oder der generellen Benutzung unseres Mobiltelefons.
In der Vorlesung wird eine Einführung in die grundlegenden und am häufigsten verwendeten Verfahren der Datenkompression gegeben. Es werden sowohl theoretische Grundlagen als auch praktische Verfahren behandelt und anhand von Beispielen aus der Praxis erläutert.
Der erste Teil der Vorlesung behandelt die verlustlose Kompression, bei der die Originaldaten exakt rekonstruiert werden können. Dieser Teil umfasst die folgenden Themen:
- Eindeutige Decodierbarkeit und Prefix-Codes
- Entropie und Entropierate als theoretische Grenzen der verlustlosen Kompression
- Optimale Codes, Huffman Codes
- Arithmetische Codierung
- Lempel-Ziv Codierung
- Linear Prädiktion
- Beispiele aus der Text-, Bild- und Audiokompression
Im zweiten Teil der Vorlesung wird die allgemeinere verlustbehaftete Kompression eingeführt, bei der nur eine Approximation der Originaldaten rekonstruiert werden kann. Diese Art der Kompression ermöglicht deutlich höhere Kompressionsfaktoren und ist die dominante Form der Kompression für Audio-, Bild- und Videodaten. Dieser zweite Teil der Vorlesung umfasst folgende Themen:
- Skalare Quantisierung, optimale skalare Quantisierung
- Theoretische Grenzen der verlustbehafteten Kompression: Rate-Distortion-Funktionen
- Vektorquantisierung
- Prädiktive Quantisierung
- Transformationscodierung
- Beispiele aus der Audio-, Bild- und Videocodierung
Literaturhinweise
- Sayood, K. (2018), “Introduction to Data Compression,” Morgan Kaufmann, Cambridge, MA.
- Cover, T. M. and Thomas, J. A. (2006), “Elements of Information Theory,” John Wiley & Sons, New York.
- Gersho, A. and Gray, R. M. (1992), “Vector Quantization and Signal Compression,” Kluwer Academic Publishers, Boston, Dordrecht, London.
- Jayant, N. S. and Noll, P. (1994), “Digital Coding of Waveforms,” Prentice-Hall, Englewood Cliffs, NJ, USA.
- Wiegand, T. and Schwarz, H. (2010), “Source Coding: Part I of Fundamentals of Source and Video Coding,” Foundations and Trends in Signal Processing, vol. 4, no. 1-2.
15 Termine
Regelmäßige Termine der Lehrveranstaltung