KMI/KOM Data Compression
Lecturer: Jan Outrata
Lecture: 2 hours/week + exercise 2 hours/week
Credits: 5
Summer semester
Form of course completion: credit course, exam
- Intro: Required notions from information theory and coding (entropy), taxonomy of compression methods, basic notions and data models, simple methods (RLE, MTF, Delta).
- Statistical methods: Shannon-Fano, Huffman, arithmetic and Q-coding, principles and implementation.
- Context methods: Prediction by partial matching (PPM) and context mixing (PAQ) methods.
- Dictionary methods: LZ77 class and LZSS and Deflate methods, LZ78 class and LZW method, principles and implementation.
- Block sorting method: Burrows-Wheeler transformation (BWT), principle and implementation.
- Other lossless methods: Grammar-based, statistical and other LZ methods, LZMA.
- Lossy compression methods: Multimedia data representation and color spaces (models), survey of methods, quantization, DPCM, transform (DCT, DFT) and subband (wavelet) coding.
- Image compression: GIF, PNG, TIFF, JPEG, wavelet, fractal, WebP.
- Video compression: M-JPEG, DV, motion prediction, MPEG/H.26*, VP*, Theora, containers (MPEG, Ogg, WebM, AVI, Flash).
- Audio compression: Prediction, psychoacoustics, syntetization, MPEG (MP3, AAC), Dolby (AC-3), Vorbis, Speex, FLAC, MIDI.
- Graphics compression: Representation (polygonal meshes), topological surgery, progresive meshes, wavelet compression, MPEG.
