Kódovanie a prenos multimediálnych údajov - ÚINF/KMÚ (KPI)


  Plánované témy prednášok a cvičení
1. Formálny model kódovania a prenosu informácie.
Zdrojová, kódová abeceda, kódové slová, kód, prenosový kanál, šum.
Stratové a bezstratové kódovanie, kompresný pomer.
Jednoznačne dekódovateľné kódy, nerovnaké dĺžky kódových slov.
RLE a Rice-Golombove kódy.
2. Kódovanie so známym rozdelením pravdepodobností výskytu vstupných znakov.
Huffmanova konštrukcia kódu - vzťah strednej dĺžky kódového slova a entropie.
Optimálnosť Huffmanovej konštrukcie.
Viacznakové Huffmanovo kódovanie.
Kódové stromy, sibling property. Adaptívne Huffmanove kódovanie (FGK algoritmus)
3. Aritmetické kódovanie - princíp.
Celočíselné aritmetické kódovanie.
Binárne aritmetické kódovanie - Q, QM metóda.
Adaptívny QM kóder
Výhody a nevýhody štatistických kódov.
4. Bezstratové metódy kompresie s predikciou
Predikcia s čiastočnou zhodou - PPM algoritmus.
JBIG štandard, aritmetické kódovanie s kontextom.
JPEG-LS štandardy, štandardy pre prenos faxu (CCITT Group 3,4)
Slovníkové techniky kompresie. Statické slovníkové metódy.
LZ77 a LZSS algoritmus. LZ78 a LZW algoritmus.
Burrows-Wheelerova transformácia (BWT) + Move-to-Front kódovanie.
5. Stratová kompresia - princípy.
RD funkcia - vzťahy medzi kompresným pomerom a skreslením.
Skalárna kvantizácia. Uniformná kvantizácia pre rovnomernú pravdepodobnosť zdroja.
Adaptívna uniformná kvantizácia - forward, backward metóda, Jayantova kvantizácia.
Neuniformná kvantizácia - princíp.
Optimalizácia neuniformnej kvantizácie podľa distribučnej funkcie.
Lloyd-Maxov algoritmus. Využitie kompresorov a expandérov.
Vektorová kvantizácia. Linde-Buzo-Grayov algoritmus - využitie pri kompresii zvuku a obrazu.
6. Diferenčné techniky v kódovaní, predikčné metódy.
DPCM metóda, adaptívna kvantizácia a predikcia v DPCM.
Delta modulácia, adaptívna verzia s konštantným faktorom.
Kódovanie zvuku a obrazu DPCM metódou.
7. Transformácie a ich význam v stratovom kódovaní.
Ortonormálne zobrazenia, lineárne systémy.
Komponentová analýza a KLT transformácie.
Diskrétna Walsh-Hadamardova transformácia.
Dvojdimenzionálna transformácia, DC, AC koeficienty.
Fourierov rozvoj a Fourierova transformácia.
Diskrétna Fourierova transformácia.
Rekurzívny (Cooley-Tukey) algoritmus pre FFT.
8. DCT a jej využitie pri kompresii obrazu.
JPEG kóder - sekvenčný, progresívny, bezstratový a hierarchický režim.
9. Podpásmové techniky, filtre, rozklad vstupného signálu.
Podvzorkovanie a decimácia. Haarove a QMF filtre.
Možnosti rôznej kvantizácie v jednotlivých podpásmach.
Syntéza signálu z podpásiem.
Waveletové transformácie, EZW kóder.
Využitie podpásmových rozkladov v kódovaní zvuku a obrazu.
10. Algoritmy pre videokonferencie.
Kompresia videa, MPEG, MPEG štandardy.

Doporučená literatúra :

D. Salomon, G. Motta : Handbook of Data Compression, Springer, 2010, dostupná v intranete.
Z. Li, M.S. Drew, J. Liu: Fundamentals of Multimedia, Springer, 2014, dostupná v intranete.
K. Sayood: Introduction to Data Compression, Morgan Kaufmann, 2006 (stud)
D. MacKay: Information Theory, Inference, and Learning Algorithms, CUP, 2003 (downloadable)
S.W. Smith: The Scientist and Engineer's Guide to Digital Signal Processing, CalTech Pub., 1997 (downloadable)
J. Adámek: Foundations of Coding: Theory and Applications of Error-Correcting Codes with an Introduction to Cryptography and Information Theory, Wiley, 1991
D. Hankerson, G.A. Harris, P.D. Johnson: Introduction to Information Theory and Data Compression, CRC Press, 1998
A. Moffat, A. Turpin: Compression and Coding Algorithms, Kluwer, 2002
J. Adámek: Kódování a teorie informace, ČVUT Praha, 1991