Komprese dat
Obsah přednášky z
Komprese dat
z z
doc. Ing. Miroslav Beneš, Ph.D. katedra informatiky FEI VŠB-TUO A-1007 / 597 324 213 http://www.cs.vsb.cz/benes
[email protected]
Motivace Podstata a typy komprese Základní metody kódování z z z z
z z
Huffmanovo kódování Aritmetické kódování Slovníkové metody Prediktivní metody
Komprese obrazu, zvuku a videa Komprese dat v prostředí Java Komprese dat
Motivace z
z
z
Umístění rozsáhlých dat na média s omezenou kapacitou
2 min. hudby na CD z z
44 100 vzorků/sec, 16 bitů vzorek Bez komprese > 84 mil. bitů
Přenos dat z
z
Motivace
Ukládání dat z
2
Snížení nároků na objem přenášených dat (doba přenosu, cena)
z
z
Archivace z
z
Omezení prostoru, který zabírají méně často používaná dat Komprese dat
1 sec. videa
3
(c) Miroslav Beneš, Katedra informatiky FEI VŠB-TU Ostrava
Rámec 720x480 vzorků, 30 fps, 16 bitů/vzorek Bez komprese > 160 mil. bitů
Komprese dat
4
1
Komprese dat
Podstata komprese z
Informační hodnota roste s klesající pravděpodobností zprávy z
z
z
Typy komprese z
z
Informace přenášená symbolem X s pravděpodobností výskytu P(X) - log2 P(X) Odpovídá počtu bitů, které bychom potřebovali v ideálním případě na její reprezentaci
z
z
z
Část informačního obsahu se kompresí ztrácí Používá se hlavně při kompresi obrazu a zvuku z
z
Využití fyziologických omezení lidských smyslů
Účinnost komprese
x
Velikost ztrát
Komprese dat
6
Huffmanovo kódování
Přidělení binárních posloupností symbolům nějaké abecedy A ….. 0 B ….. 10 C ….. 11
z
5
Kódování z
Při kompresi nedochází ke ztrátě informačního obsahu Po obnově dostáváme původní data
Ztrátová komprese z
Při kódování informace se snažíme dosáhnout co nejlepšího poměru mezi délkou zprávy a její informační hodnotou Komprese dat
Bezztrátová komprese
z
.-… -.-.
A B C D E
ABBAC ….. 01010011 …... .-/-…/-…/.-/-.-. Komprese dat
7
(c) Miroslav Beneš, Katedra informatiky FEI VŠB-TU Ostrava
Přidělení kódu tak, aby symbol s největší pravděpodobností výskytu měl nejkratší kód
0.4 0.2 0.2 0.1 0.1
1 0 1
1
0.6 1
0.4
0.2 0
0 Komprese dat
1.0 0
A=11 B=10 C=01 D=001 E=000 8
2
Komprese dat
Huffmanovo kódování z
Problém z z z
z
Aritmetické kódování z
Vyžaduje znalost pravděpodobností symbolů Nutnost předzpracování komprimovaných dat Tabulka pravděpodobností musí být dostupná při dekompresi
0.0
A B C D E
Adaptivní kódování z z
Tabulka se vytváří v průběhu kódování Nemusí se uchovávat – při dekompresi se obnoví Komprese dat
z
0.8 0.9 1.0
C D E
A 0.48 0.52 0.56 0.58 0.60
B C D E
0.568 0.572 0.576 0.578 0.580
BD=(0.56,0.58] BDB=(0.568,0.572] 10
Slovníkové metody
Vyžaduje aritmetiku s vysokou přesností Výsledné číslo lze reprezentovat libovolným prvkem z intervalu BDB …… 0.57
z
Zejména při kompresi textů se často opakují některé posloupnosti znaků nebo slov z
I přes zdánlivou složitost lze jednoduše implementovat
z
11
(c) Miroslav Beneš, Katedra informatiky FEI VŠB-TU Ostrava
např. zdrojové texty programů
Můžeme vytvořit slovník opakujících se slov a do výstupu kódovat jen reference do slovníku z
Komprese dat
0.6
B
0.560
Komprese dat
z z
0.40
A 0.4
B=(0.4,0.6] 9
Aritmetické kódování z
Kódování posloupnosti symbolů na reálné číslo z intervalu (0,1]
Statický slovník – připravíme předem Adaptivní slovník – vytváří se průběžně Komprese dat
12
3
Komprese dat
Algoritmus LZ77 (Jacob Ziv – Abraham Lempel) z z z
Algoritmy LZ78 a LZW
Slovník je součástí již dříve zakódované sekvence Ukládá se posloupnost trojic
Použito s úpravami v PKZip, Zip, PNG, gzip, ARJ, … vyhledávací paměť
dopředu nahlížená paměť
l=3
z z
<6, 3, b>
z
Komprese dat
z
ababbaababaab
z
123
7
Komprese dat
Vytváří se samostatný slovník Ukládá se posloupnost dvojic Varianta LZW ukládá jen posloupnost indexů do slovníku Velikost slovníku lze omezit max. délkou kódu pro reprezentaci indexu Aplikace: UNIX compress, gif, V.42 bis
13
Příklad – algoritmus LZW
3
z
o=6
a b a b a b b a a c a b b b a c b
4
z
1 2 3 4 5 6 7 8
Komprese dat
14
Prediktivní metody a b ab ba abb baa aba abaa
z
z
Předchozí metody vycházejí z posloupnosti nezávislých symbolů Často jsou symboly závislé – v určitém kontextu se vyskytují více nebo méně často z z
z
15
(c) Miroslav Beneš, Katedra informatiky FEI VŠB-TU Ostrava
„V Á N O C“ … E „?“ … mezera
Ve faxové zprávě - po černém nebo bílém bodu lze očekávat opět bod stejné barvy Komprese dat
16
4
Komprese dat
Metoda RLE (Run Length Encoding) z
z
Komprese obrazu
Snaha redukovat posloupnosti opakujících se znaků xyzzzzyyyyyxwwww => xy#z4#y5x#w4 Co když se opakuje jen 2x? z Co když je více než 255 opakování? z Co když je v textu znak #? xyzzz1yyy2xwww1
z
GIF (Graphics Interchange Format) z z
z
z
z
Komprese dat
z
z
z
z
z
Pro přenos rastrových dat Velmi flexibilní – obtížný na zpracování
z
z
z
Důraz na přenositelnost Vylepšuje vlastnosti GIF (průhlednost, prokládání, lepší komprese) 19
(c) Miroslav Beneš, Katedra informatiky FEI VŠB-TU Ostrava
menší nároky na přesnost Telefon, GSM
Komprese hudby z
Perceptual encoding – využívá znalostí z psychoakustiky (nedokonalosti lidského ucha) z z
z Komprese dat
18
Komprese řeči z
PNG (Portable Network Graphics) z
Komprese dat
Komprese zvuku
TIFF (Tagged Image File Format) z
Ztrátová komprese – pro fotografické snímky Založen na diskretní kosinové transformaci (DCT), případně na waveletech Progressive JPEG – postupné zobrazování
17
Komprese obrazu z
JPEG (Joint Photographic Experts Group) z
Použití v PCX, BMP, faxové protokoly
Bezztrátová komprese – pro grafiku, ikony, … Implementace LZW algoritmu s omezenou délkou slovníku (po naplnění je statický)
maskování frekvencí – nelinearita citlivosti časové maskování - setrvačnost
Audiosystémy, přenosné přehrávače, video Komprese dat
20
5
Komprese dat
Komprese zvuku z
Komprese videa
MPEG-1 Layer 3 (MP3) z z z
z
1987, univerzita Erlangen Veřejně dostupný formát, mnoho implementací Rychlé dekódování, nízké nároky
Video = posloupnost obrázků + zvuk z
z
MPEG (Moving Picture Experts Group) z
z
Dolby Laboratories AC-3 z z
z
Vícekanálová komprese (mono … 5.1) Možnost doplnění o metadata, jazykové verze, … Komprese dat
z
Komprese dat
Posloupnost rámců (snímků)
z
Využití prediktivní komprese z
java.util.jar
z
Na základě jednoho rámce odhadujeme další
Typy rámců z z
JarInputStream, JarOutputStream
java.util.zip z
z
22
Komprese v prostředí Java z
z
MPEG-1 (do 1.5 Mbit/sec – VideoCD, Internet) MPEG-2 (1.5-15 MBit/sec – DVD, digit. TV) MPEG-4 (komprese založená na objektech)
21
Komprese videa z
Vysoký tok dat
z
ZIPInputStream, ZIPOuputStream GZIPInputStream, GZIPOutputStream
I-frame: obsahuje celý obrázek (JPEG) P-frame: obsahuje rozdíly od odhadnutého rámce Komprese dat
23
(c) Miroslav Beneš, Katedra informatiky FEI VŠB-TU Ostrava
Komprese dat
24
6
Komprese dat
Příklad
Příklad
String[] filenames = new String[]{"filename1", "filename2"}; byte[] buf = new byte[1024];
// // Vytvoření nové výstupní položky out.putNextEntry(new ZipEntry(filenames[i]));
try { String outFilename = "outfile.zip"; ZipOutputStream out = new ZipOutputStream( new FileOutputStream(outFilename));
// Přenos obsahu souboru int len; while ((len = in.read(buf)) > 0) { out.write(buf, 0, len); }
for (int i=0; i in.close(); } out.close(); } catch (IOException e) {}
// Uzavření výstupní položky out.closeEntry(); Komprese dat
25
(c) Miroslav Beneš, Katedra informatiky FEI VŠB-TU Ostrava
Komprese dat
26
7
