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


Prednáška sa koná v pondelok 15:20 v P10, cvičenia vo štvrtok 14:25 v P04.
O problémoch je možné diskutovať aj v googlovskej diskusnej skupine KMU-2017@googlegroups.com.
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í
18.9.2017
15:20 P10
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.
Úlohy na precvičenie - séria A (doc, pdf) - odovzdať do 25.9.2017, 15:20
25.9.2017
15:20 P10
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.
Handbook kap. 2.1-2.5, kap. 5.2.
Úlohy na precvičenie - séria B (doc, pdf) - odovzdať do 2.10.2017, 15:20
28.9.2017 Cvičenie k Huffmanovmu kódovaniu.
2.10.2017
15:20 P10
Viacznakové Huffmanovo kódovanie.
Tunstallovo kódovanie.
Úlohy na precvičenie - séria C (doc, pdf) - odovzdať do 9.10.2017, 15:20
5.10.2017
14:25 P04
Nepovinné cvičenia k Huffmanovmu kódovaniu
(a k práci v prostredí Python).
9.10.2017
15:20 P10
Kódové stromy, sibling property.
Adaptívne Huffmanovo kódovanie FGK a Vitter.
slajdy z prednášok
12.10.2017
14:25 P04
Cvičenie k Huffmanovmu kódovaniu.
Domáci projekt (odovzdať do 26.10.2017, 14:25)
Adaptívne Huffmanovo kódovanie a dekódovanie obrázka
16.10.2017
15:20 P10
Aritmetické kódovanie - princíp.
Celočíselné aritmetické kódovanie.
slajdy z prednášok
Handbook - kap. 5.
Úlohy na precvičenie - séria D (doc, pdf) - odovzdať do 23.10.2017, 15:20
19.10.2017 Konzultácie k projektu Adaptívne Huffmanovo kódovanie.
23.10.2017
15:20 P10
Binárne aritmetické kódovanie - Q, QM metóda.
Výhody a nevýhody štatistických kódov.
slajdy z prednášok
Úlohy na precvičenie - séria E (doc, pdf) - odovzdať do 30.10.2017, 15:20
26.10.2017
14:25 P04
Cvičenie k aritmetickému kódovaniu.
Domáci projekt (odovzdať do 9.11.2017, 14:25)
30.10.2017
15:20 P10
Adaptívny QM kóder
Handbook - kap. 5.
2.11.2017 Konzultácie k projektu z aritmetického celočíselného kódovania
6.11.2017
15:20 P10
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.
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.
Úlohy na precvičenie - séria F (doc, pdf) - odovzdať do 13.11.2017, 15:20
9.11.2017
14:25 P04
Cvičenie k práci s obrazom a zvukom.
Skalárna kvantizácia údajov a ich zobrazenie.
13.11.2017
15:20 P10
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.
Slajdy z prednášky.
Handbook - kap. 7.19, 7.20 dostupné v intranete.

Úlohy na precvičenie - séria G (doc, pdf) - odovzdať do 20.11.2017, 15:20

20.11.2017
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.
23.11.2017
14:25 P04
Cvičenie ku stratovým metódam kompresie - kvantizácia a predikčné metódy.

Doporučená literatúra :

D. Salomon, G. Motta : Handbook of Data Compression, Springer, 2010, dostupný v intranete.
K. Sayood: Introduction to Data Compression, Morgan Kaufmann, 2006
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ú.