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


Na tomto mieste nájdete počas semestra informácie a dôležité odkazy k predmetu KMÚ.
Prednášky budú v tomto semestri v pondelok 15:20 v P11, cvičenia v utorok 11:40 v P04.

Záverečný test bude 22. 1. 2020 už od 9:00 v P18.

písomný test - základné pojmy, algoritmy (RGC, HC, AHC-FGK, AC, QM, Q, LZ77, LZSS, LZ78, LZW, BWT, MTF,
UQ, Jayant, LBG, DPCM, DM, CFDM, DWHT, DCT (do 4x4), JPEG, Haarove wavelety, MPEG)

Témy ústnej časti:

Prehľad preberaných tém
Doporučená literatúra a ďalšie zdroje informácií.
Pravidlá hodnotenia
Cvičenia

  Prebraté a plánované témy prednášok a cvičení
16.9.2019
15:20
Formálny model kódovania a prenosu informácie.
Stratové a bezstratové kódovanie, kompresný pomer.
Kódovanie RLE a Rice-Golombove kódy.
Zdrojová, kódová abeceda, kódové slová, kód, prenosový kanál, šum.
Jednoznačne dekódovateľné kódy, nerovnaké dĺžky kódových slov.
Zisťovanie jednoznačnej dekódovateľnosti. Blokové a prefixové kódy.
Kraft-McMillanova nerovnosť
Data Compression - kapitoly 1 a 2
23.9.2019
15:20
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 Huffmanovo kódovanie (FGK a Vitter)
Slajdy z prednášok
Handbook kap. 2.1-2.5, kap. 5.2, 5.3.
Data Compression - kapitola 3
Úlohy na precvičenie - séria A (doc, pdf) - riešenia odovzdať do 30.9.2019, 15:20
24.9.2019
11:40 P04
Cvičenie k Huffmanovmu kódovaniu.
30.9.2019
15:20
Aritmetické kódovanie - princíp.
Celočíselné aritmetické kódovanie. Adaptívna verzia.
slajdy z prednášok
Handbook - kap. 5.9-5.11.
Data Compression - kapitola 4
7.10.2019
15:20
Binárne aritmetické kódovanie - Q, QM metóda. Adaptívny QM kóder.
Výhody a nevýhody štatistických kódov.
Aritmetické kódovanie s kontextom.
Bi-level postupy, JBIG štandard.
JPEG-LS štandardy, štandardy pre prenos faxu (CCITT Group 3,4)
Bezstratové metódy kompresie s predikciou
Predikcia s čiastočnou zhodou - PPM algoritmus.
slajdy z prednášok
Handbook - kap. 5.7, 5.11, 5.14.
Data Compression - kapitola 6 a 7
Úlohy na precvičenie - séria B (doc, pdf) - odovzdať do 21.10.2019, 15:20
8.10.2019
11:40 P04
Cvičenie k aritmetickému kódovaniu.
14.10.2019
15:20
Slovníkové techniky kompresie. Statické slovníkové metódy.
LZ77 a LZSS algoritmus. LZ78 a LZW algoritmus.
Výhody a využitie transformačných metód.
Burrows-Wheelerova transformácia (BWT) + Move-to-Front kódovanie.
slajdy z prednášok
Handbook - kap. 6 dostupné v intranete.
Data Compression - kapitola 5
21.10.2019
15:20 P10
Stratová kompresia - princípy.
RD funkcia - vzťahy medzi kompresným pomerom a skreslením.
Pravdepodobnostné modely, fyziologické modely pre efektívnu kompresiu.
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.
Slajdy z prednášky.
Data Compression - kapitola 8 a 9
Úlohy na precvičenie - séria C (doc, pdf) - odovzdať do 28.10.2019, 15:20
22.10.2019
11:40 P04
Cvičenie k práci s obrazom a zvukom.
Skalárna kvantizácia údajov a ich zobrazenie.
28.10.2019
15:20 P10
Vektorová kvantizácia. Linde-Buzo-Grayov algoritmus (animácia), - využitie pri kompresii zvuku a obrazu.
Slajdy z prednášky.
Handbook - kap. 7.19, 7.20 dostupné v intranete.
Data Compression - kapitola 10
4.11.2019
15:20 P10
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.
Slajdy z prednášky.
Handbook - kap. 7.30, kap. 10.5, 10.6, 10.10 dostupné v intranete.
Data Compression - kapitola 11
Úlohy na precvičenie - séria D (doc, pdf) - odovzdať do 11.11.2019, 15:20
5.11.2019
11:40 P04
Cvičenie ku stratovým metódam kompresie - kvantizácia a predikčné metódy.
11.11.2019
15:20 P10
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.
Data Compression - kapitola 13
18.11.2019
15:20 P10
Fourierov rozvoj a Fourierova transformácia.
Diskrétna Fourierova transformácia.
DCT a jej využitie pri kompresii obrazu.
JPEG kóder - sekvenčný, progresívny, bezstratový a hierarchický režim.
kapitola 9.1 z knihy Fundamentals of Multimedia (prístupná z intranetu)
Handbook - kap. 7 - 7.8.1, 7.10.
Slajdy z prednášky.
slajdy JPEG zo Stanfordu
25.11.2019
15:20 P10
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.
Data Compression - kapitola 14
Slajdy z prednášky.
26.11.2019
11:40 P04
Cvičenia k transformáciám a JPEG (presunuté z 19.11.)
transformácie v kompresii zvuku a obrazu.
2.12.2019
15:20 P10
Psychoakustický model.
Využitie podpásmových rozkladov v kódovaní zvuku a obrazu.
Waveletové transformácie, EZW kóder.
Handbook - kap. 8 - hlavne 8.6, 8.7, 8.16., kap. 10 - kompresia zvukového signálu.
Data Compression - kapitola 15, 16
kapitola 6.1, 8.6-8.8, 13, 14 z Fundamentals of Multimedia (v intranete)
Slajdy z prednášky.
Úlohy na precvičenie - séria E (doc, pdf) - odovzdať do 9.12.2019, 13:30
3.12.2019
11:40 P04
Cvičenia k pásmovým rozkladom - využitie v kompresii zvuku a obrazu.
9.12.2019
13:30 P10
Algoritmy pre videokonferencie.
Kompresia videa, MPEG, MPEG štandardy.
MPEG-2, MPEG-4 AVC/H.264, MPEG-H HEVC/H.265
Data Compression - kapitola 18
Handbook - kap. 9
kapitola 11 z knihy Fundamentals of Multimedia (prístupná z intranetu)
Slajdy ku kompresii videa.
17.12.2019
11:40 P04
Cvičenie ku kódovaniu videa.

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 verzia)
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


Ďalšie zdroje na Sieti :

Data-Compression website
C.E. Shannon: A Mathemtatical Theory of Communication
R.W. Hamming: Error detecting and error correcting codes
Data Compression (D.A. Lelewer, D.S. Hirschberg)
.ZIP File Format Specification
JPEG a JBIG štandardy JPEG 2000 draft
MPEG home page MPEG resources
SMART project - algebra v spracovaní signálov - rýchle algoritmy
NIST - Dictionary of Algorithms
Hutter prize za bezstratovú komprimáciu 100 MB textu (súčasný stav)



Kritériá hodnotenia - bodované aktivity:

Celkove je možné získať spolu cca 140 bodov. Na absolvovanie so ziskom kreditov teda potrebujete aspoň 70 bodov. Stupňom D budem hodnotiť zisk aspoň 80 bodov, C aspoň 90 bodov, B aspoň 100 bodov a A aspoň 110 bodov.

Problémy a otázky môžete konzultovať s cvičiacim (podľa konzultačných hodín), s prednášajúcim po prednáške resp. elektronickou poštou na adrese jirasek at upjs.sk. Konzultácie je možné dohodnúť aj individuálne, no len v priebehu semestra. V skúškovom období konzultácie nebudú.