Kompresní algoritmy grafiky
Jan Janoušek F11125
K čemu je komprese dobrá? • Pokud je třeba skladovat datově náročné soubory. Např. pro záznam obrazu, hudby a hlavně videa je třeba skladovat překvapivě mnoho dat.
• Při přenosu dat po síti. Zmenšením datové náročnosti se minimalizuje čas potřebný k přenosu.
Základní pojmy Data • „Jakékoliv fyzicky (materiálně) zaznamenané znalosti (vědomosti), poznatky, zkušenosti nebo výsledky pozorování procesů, projevů, činností a prvků reálného světa (reality).“ • „Surovina, z níž se tvoří informace.“ Zdroj: http://cs.wikipedia.org/wiki/Data
Informace • Data která dávají smysl.
Základní pojmy Kompresní algoritmus • Postup, který minimalizuje množství dat potřebné k popsání dané informace.
Entropie • Míra množství informace • Všechny kompresní algoritmy využívají faktu, že data často obsahují řadu nadbytečných informací. S odstraňováním těchto redundantních informací se zvyšuje entropie dat.
Základní pojmy Kompresní poměr k • Jedná se o poměr mezi velikostí dat po a před kompresí nebo o poměr zkomprimovaného datového toku k nezkomprimovanému.
Kompresní zisk z • Kompresní zisk je dán vztahem z=1-k a určuje tedy, kolik dat bylo kompresí „ušetřeno“. V případě, že kompresní algoritmus zvětší objem dat (kompresní poměr je větší, než jedna), je kompresní zisk záporný.
Základní pojmy Bezztrátový kompresní algoritmus
• Z komprimovaných dat lze získat původní data bez jakékoliv ztráty kvality. Obvykle méně účinná, než ztrátová komprese.
Ztrátový kompresní algoritmus
• Z komprimovaných dat nelze zrekonstruovat původní data, protože při komprimaci dochází k určitému zkreslení. Při komprimaci grafiky se využívá znalostí psychovizuálního model.
Výhody/nevýhody Ztrátové • Z komprimovaných dat nelze zrekonstruovat původní data • Pro obrázky s vysokým počtem barev (fotky) lepší kompresní poměr
Bezztrátové • Nehodí se pro fotky a spol. • Z komprimovaných dat lze zrekonstruovat původní data • U obrázků z nízkým počtem barev obvykle lepší kompresní poměr i kvalita.
Bezztrátové kompresní algoritmy • Slovníkové metody komprese – Komprimovaná data jsou ukládána do „slovníku“. Při opakování dat, která jsou už ve slovníku obsažena, se místo dat samotných uvede odkaz na pozici ve slovníku
• Statistické metody komprese – Statistické metody komprese jsou založeny na tom, že pro nejčastěji se vyskytující znaky jsou vytvářeny nejkratší odkazy.
• Ostatní metody komprese
Ostatní metody komprese RLE • Vstup: – wwwwwbwwwbbbbwbbbbbb
• Výstup: – 5w1b3w4b1w6b
• Kompresní poměr (v tomto případě): –
12 20
= 0,6
Vlastnosti RLE • Velmi záleží na typu obrázku • Záleží i na orientaci obrázku • V některých případech může být i záporný kompresní zisk
Slovníkové metody komprese – LZ77 „Podle principu je nazývána metodou posuvného okna. Pro lepší vysvětlení předpokládejme, že budou data reprezentována řetězcem. Posuvné okno (sliding window) je rozděleno na část, kde už jsou zakódovaná data, a na část, kde jsou ta nezakódovaná. Kódování začíná nastavením sliding window na řetězec, který má být zakódován, tak, že část pro již zakódovaná data je prázdná a druhá část je naplněna řetězcem (netřeba celým). Hledá se shoda co nejdelšího řetězce (počínajíce rozmezím) z nezakódované části s řetězcem v zakódované části. V případě shody je nový podřetězec zakódován uspořádanou dvojicí (p, n), kde p je pozice prvního znaku v zakódované části, a n je délka shodného podřetězce. “ Zdroj: Foltýnek, Tomáš a Přichystal, Jan. Komprimace a šifrování.
Slovníkové metody komprese – LZ77 Příklad: Vstupní text: leze leze po železe Výstupní text: leze l(2,3) po že(5,4) Zdroj: Foltýnek, Tomáš a Přichystal, Jan. Komprimace a šifrování.
Zdroj: Večerka, Arnošt. Komprese dat
Slovníkové metody komprese – LZW84 • Použití: – Gif, tiff, zip
• Na 20 let byl chráněn patentem Zdroj: Foltýnek, Tomáš a Přichystal, Jan. Komprimace a šifrování.
Statistické metody komprese Huffmanovo kódování „Konvertuje znaky vstupního souboru do bitových řetězců různé délky. Znaky, které se ve vstupním souboru vyskytují nejčastěji, jsou konvertovány do bitových řetězců s nejkratší délkou (nejfrekventovanější znak tak může být konvertován do jediného bitu), znaky, které se vyskytují velmi zřídka, jsou konvertovány do delších řetězců (mohou být i delší než 8 bitů). Nejjednodušší metoda komprese touto metodou probíhá ve dvou fázích. První projde soubor a vytvoří statistiku četností každého znaku. Ve druhé fázi se využije této statistiky pro vytvoření binárního stromu a k následné kompresi vstupních dat.“ Zdroj: http://cs.wikipedia.org/wiki/Huffmanovo_k%C3%B3dov%C3%A1n%C3%AD
Ztrátové kompresní algoritmy • Ztrátové kompresní algoritmy se používají tam, kde nevadí určité zkreslení informací (obraz, audio, video). • Psychovizuálním model pro obrazová data • Psychoakustický model pro zvuková data
Psychoakustický model • Klíčové znalosti pro ztrátovou kompresi obrazu: – Lidské oko je mnohem citlivější na jas barvy, než na její odstín. – Lidské oko má větší citlivost na nízké frekvence, než na vysoké.
• Při ztrátové kompresi jsou tedy přednostně komprimovány (a tedy zkreslovány) právě tyto informace.
Kompresní algoritmus JPEG • Pro velké obrázky z mnoha barvami se bezztrátové komprimační algoritmy nehodí. • Algoritmus využívá tzv. diskrétní kosinová transformace (DCT)
Kompresní algoritmus JPEG „Metoda je vhodná především pro kódování fotografií, u nichž sousední pixely mají sice odlišné, ale přesto blízké barvy. Snižování kvality se projevuje potlačováním rozdílů v blízkých barvách. U metody DCT je kompresní poměr řízen požadavkem na výši kvality dekomprimovaného obrazu. V praxi se ukazuje, že snížení kvality na 75 % je pro většinu uživatelů nepozorovatelné, přitom kompresní poměr v takovém případě může být až 25:1.“ Zdroj: Foltýnek, Tomáš a Přichystal, Jan. Komprimace a šifrování.
Postup kompresního algoritmu 1. Transformace barev z barevného prostoru RGB do YCBCR – kvůli aplikaci komprese využívající psychovizuálního modelu (barevné složky budou ve výsledku více zkreslené, než složky jasové)
2. Podvzorkování barevných složek – redukce objemu dat zprůměrováním barevných složek sousedních pixelů
Postup kompresního algoritmu 3. Rozdělení obrazu na čtverce 8 × 8
4. Aplikace dopředné diskrétní kosinové transformace na prvky čtvercové matice vzniklé v minulém kroku
Postup kompresního algoritmu 5. Kvantování koeficientů matice – v tomto kroku se určuje stupeň komprese obrazu)
6. Zkomprimování kvantovaných koeficientů pomocí Huffmanova kompresního algoritmu – po předchozím kroku má mnoho prvků matice nulovou hodnotu
Transformace barev • Transformace z barevného prostoru RGB do barevného prostoru YCBCR je přesně definována ve specifikaci JFIF, ve které jsou uvedeny jak rovnice pro převod z barevného prostoru RGB do YCBCR, tak rovnice pro převod inverzní.
Transformace barev • Specifikace předpokládá, že složky RGB a YCBCR jsou reprezentovány jako celá čísla v rozsahu 0 až 255. • Ačkoliv tato transformace je v principu bezztrátová, tyto samotné převody jsou do určité míry ztrátové, protože dochází k zaokrouhlování výsledků na celá čísla.
YCBCR Jasová složka barvy – Y (luma)
Barevné složky – CB a CR (chroma)
Na tuto složku je lidské oko nejvíce citlivé a podléhá tedy nejmenší kompresi.
• Barevné složky pro modrou a červenou barvu. • 𝐶𝐵 = −0,1687𝑅 − 0,3313𝐺 + 0,5𝐵 + 128 • 𝐶𝑅 = 0,5𝑅 − 0,4187𝐺 + 0,0813𝐵 + 128 • Barevná složka pro zelenou se neuvádí, protože je jí možno z Y, CB a CR dopočítat.
𝑌 = 0,299𝑅 + 0,587𝐺 + 0,114𝐵
Zpětný převod 𝑅 = 𝑌 + 1,402 × 𝐶𝑅 − 128 𝐺 = 𝑌 − 0,34414 × 𝐶𝐵 − 128 − 0,71414 × 𝐶𝑅 − 128 𝐵 = 𝑌 + 1,772 × 𝐶𝐵 − 128
Podvzorkování barevných složek • Protože lidské oko je mnohem méně citlivé na barvy, než na jas, využívá se podvzorkování (nebo také redukce) barvonosných složek pro zvýšení efektivity kompresního algoritmu. • Jedná se o první významněji ztrátový převod, protože informace o barvách v tomto procesu zanikají.
Podvzorkování barevných složek Podvzorkování funguje tak, že z hodnot barevných složek sousedních pixelů je spočítána průměrná hodnota. Jsou přípustné dvě možnosti:
Podvzorkování barevných složek • Průměrování hodnot dvou sousedních pixelů na řádku. – Úspora dat ze 6 bytů na 4, kompresní poměr tedy asi 67%.
• Průměrování hodnot pixelů tvořící čtverec 2×2 – Úspora dat ze 12 bytů na 6, kompresní poměr tedy 50%.
Rozdělení obrazu na čtverce 8 × 8 • Obrázek je rozdělen na čtvercové bloky o rozměrech 8 × 8 pixelů.
• Tohoto rozdělení lze později využít pro rychle generování náhledového obrázku.
Rozdělení obrazu na čtverce 8 × 8 • Pokud není výška nebo šířka obrázku dělitelná osmi, je nutné tyto „okrajové“ bloky vhodně doplnit do požadovaného rozměru 8 × 8 pixelů. Způsob doplnění je ponechán na konkrétním software, který obrázek zpracovává. Obvykle se používá zrcadlení již existujících pixelů.
Aplikace dopředné diskrétní kosinové transformace • Nyní máme matici 8 × 8 pixelů, kde každý prvek této matice obsahuje informaci o jasu (složka Y) a o barvě (složky CB a CR).
• Od všech jednotlivých složek se odečte hodnota 128, čímž se přetransformuje jejich rozsah do intervalu -128 až 127
Aplikace dopředné diskrétní kosinové transformace • Jednotlivé složky se budou nyní dopřednou DCT zpracovávat samostatně. • DCT je nutno provést celkem třikrát: jednou pro jasovou složku Y a dvakrát pro barevné složky CB a CR.
• Účelem DCT je přetransformovat tuto matici do matice nové, ve které budou, z hlediska lidského vnímání, nejdůležitější prvky uvedeny v levém horním rohu a směrem k rohu levému bude jejich důležitost klesat.
Aplikace dopředné diskrétní kosinové transformace • Transformace se pro jednotlivé prvky provádí pomocí rovnice:
•
𝑪 𝒊 ,𝑪 𝒋 –
•
1 2
a 𝐶 𝑖 = 𝐶 𝑗 = 1 pro 𝑖, 𝑗 ≠ 0
𝑵 –
•
Funkce, pro které platí: 𝐶 0 =
Rozměr matice. V tomto případě tedy platí 𝑁 = 8.
𝒇 𝒎, 𝒏 – Hodnota matice v bodě 𝑚, 𝑛.
Aplikace dopředné diskrétní kosinové transformace • Výsledkem transformace je matice, která v levém horním rohu obsahuje tzv. stejnosměrný koeficient (DC), u něhož jsou hodnoty Y, CB a CR průměrné celého bloku matice.
Aplikace dopředné diskrétní kosinové transformace • Výsledkem transformace je matice, která v levém horním rohu obsahuje tzv. stejnosměrný koeficient (DC), u něhož jsou hodnoty Y, CB a CR průměrné celého bloku matice.
Aplikace dopředné diskrétní kosinové transformace • Ostatní koeficienty jsou tzv. střídavé (AC). Čím vyšší frekvenci tyto koeficienty mají, tím je jejich důležitost nižší a mohou se v následujícím kroku více zkomprimovat (a tedy více zkreslit jejich hodnota).
Kvantování koeficientů matice • Až na proces podvzorkování barvonosných složek dosud algoritmus dosud neprováděl žádnou kompresi. Ta nejdůležitější část komprese – kvantování koeficientů tabulky – se provádí právě zde.
Kvantování koeficientů matice • Z předchozího kroku je připravena matice, která má v určité části důležité koeficienty a v jiné méně důležité až téměř nevýznamné. Každý prvek této matice se celočíselně vydělí hodnotami z tzv. kvantizační tabulky.
Kvantování koeficientů matice • Kvantizační tabulky obsahují nízké hodnoty u důležitých členů (nízkofrekvenčních) a vysoké hodnoty u důležitých členů (vysokofrekvenčních). Po tomto procesu tedy vzniknou u vysokofrekvenčních prvků převážně nuly.
Zdroj: http://www.root.cz/clanky/p rogramujeme-jpegkvantizace-dct-koeficientu/
Kvantování koeficientů matice • Výsledná kvalita závisí převážně na použité kvantizační tabulce. Proto obvykle existují pro různé stupně komprese různé tabulky.
• Kvantizační tabulky nejsou dány normou, a proto každý výrobce softwaru může zvolit vlastní sadu kvantizačních tabulek.
Kvantování koeficientů matice • Často aplikace neobsahuje pro každý stupeň komprese specifickou kvantizační tabulku. Tento problém se řeší pomocí lineární interpolace ze známých příslušných hodnot ostatních kvantizačních tabulek.
Kvantování koeficientů matice
Zdroj: http://www.root.cz/clanky/programujeme-jpeg-kvantizace-dctkoeficientu/
Zkomprimování kvantovaných koeficientů • V aktuálním stavu obsahuje kvantovaný blok 8 × 8 pixelů mnoho pixelů v části vysokofrekvenčních členů. Tento blok nyní stačí už pouze zkomprimovat pomocí Huffmanova kompresního algoritmu.
Zkomprimování kvantovaných koeficientů • Matice je komprimována postupně „cik-cak“ od členu s nejnižší frekvencí (stejnosměrný člen – DC) po člen s nejvyšší frekvencí. Tímto postupem Huffmanovo kódování dosáhne nejvyšší účinnosti díky opakování mnoha nul po sobě.
Zdroj: http://www.root.cz/clan ky/programujeme-jpegkvantizace-dctkoeficientu/
Zkomprimování kvantovaných koeficientů • Tímto krokem je samotná komprimace dokončena. Nyní zbývá už jen data uložit v podobě dle specifikace, přidat hlavičku a ostatní metadata (EXIF, IPTC apod.).
Zdroje 1. 2. 3.
4.
5. 6. 7.
Foltýnek, Tomáš a Přichystal, Jan. Komprimace a šifrování. *Online+ *Citace: 6. 4 2012.] https://akela.mendelu.cz/~foltynek/KAS/elearning/KAS_PDF.pdf. Večerka, Arnošt. Komprese dat. *Online+ 2008. *Citace: 6. 4 2012.+ phoenix.inf.upol.cz/esf/ucebni/komprese.pd. Tišnovský, Pavel. Programujeme JPEG: diskrétní kosinová transformace (DCT). Root.cz. [Online] 4. 1 2007. [Citace: 6. 4 2012.] http://www.root.cz/clanky/programujeme-jpeg-diskretni-kosinova-transformacedct/. —. Programujeme JPEG: Kvantizace DCT koeficientů. Root.cz. *Online+ 11. 1 2007. [Citace: 6. 4 2012.] http://www.root.cz/clanky/programujeme-jpeg-kvantizacedct-koeficientu/. Bařina, David. Ztrátová komprese obrazu. FIT VUT Brno. *Online+ 2007. *Citace: 6. 4 2012.] www.fit.vutbr.cz/study/DP/rpfile.php?id=5779. Data compression ratio. Wikipedia. [Online] [Citace: 6. 4 2012.] http://en.wikipedia.org/wiki/Data_compression_ratio. Komprese Dat. Wikipedia. [Online] [Citace: 1. 4 2012.] http://cs.wikipedia.org/wiki/Komprese_dat.
