Kompresní metody
Komprese statických obrázků

Cílem komprese statických obrázků je redukce nepotřebných informací v obraze za účelem snížení šířky potřebného přenosového pásma anebo úložného prostoru. Podobně jako u audiosignálů existují i u obrazu ztrátové i bezeztrátové algoritmy, které se používají v závislosti od cílového užití.

Při analýze obrazů automaticky předpokládáme použití 2rozměrných verzí transformací.

Na to, abychom mohli v počítači ukládat obrázky, existují různé barevné prostory. Uvedeme jen ty nejpoužívanější.

Vybrané barevné prostory

Zkratka

Význam

Vysvětlení

RGB

Red, Green, Blue

(červená, zelená, modrá)

Každý pixel je dán kombinací 3 barev světla. Kombinace nejvyšších úrovní všech 3 barev dává bílou. Používá se u obrazů vytvářených světlem.

RGBA

Red, Green, Blue, Alpha

(červená, zelená, mudra, alfa)

Stejný význam jako u RGB. Přidaný alfa kanál popisuje průhlednost.

YCBCR anebo

YUV

Jas (Y), Modrá barevnost (U), Červená barevnost (V)

Jas se mění od černé do bílé. Modrá a červená barevnost se vypočítají z daného zdroje RGB. I když se YCBCR označuje i jako YUV, existují mezi nimi rozdíly při výpočtu složek barevnosti.

CMYK

Cyan, Magenta, Yellow, Black

(azurová, purpurová, žlutá, černá)

Každý bod obrazu je dán kombinací čtyřech barev. Kombinace nejvyšších úrovní všech 4 barev dáva černou. Používá se v tisku.

JPEG

Standard JPEG je jedním z nejpoužívanějších ztrátových obrazových formátů na ukládání fotografií. Je pojmenovaný podle spojené expertní skupiny pro obraz (Joint Picture Experts Group), která jej uvedla v roce 1986. Dosahuje kompresní poměr 10:1 s minimálně postřehnutelnou ztrátou kvality.

Algoritmus JPEG je založen na 2rozměrné diskrétní kosinusové transformaci (DCT). Vstupní obraz se zkonvertuje do barevného prostoru YCBCR, který poskytuje lepší vlastnosti, než řekněme RGB. Obraz se potom rozdělí na nepřekrývající se bloky velikosti 8x8 bodů, které se transformují pomocí DCT. Získané koeficienty se kvantizují a málo významné koeficienty se odstraní (zde dochází k ztrátové kompresi). Koeficienty se potom seřadí do 1rozměrné sekvence a bezeztrátově zakódují. Obrazové komponenty (Y, CB a CR) se kódují postupně.

Obecné schéma kodéru JPEG. Vstupem je blok 8x8 bodů jasové anebo barevné složky.

Klíčem v kompresi JPEG algoritmem je kvantizace. Kvantizace je nelineární, neboť lidské oko je citlivější na změny v nízkých frekvencích. Pro to, aby byla kvalita, resp. kompresní poměr, měnitelná, byl zaveden faktor kvality qf , který se mění v rozsahu 1 až 100 a upravuje kvantizační matici.

K seřazení koeficientů slouží tzv. cik-cak čítání, které začíná v levém horním rohu. Jestliže se každý blok 8x8 společně zakóduje, kódování se označuje jako základné (baseline) JPEG. Jiným přístupem je kódování nejprve levých horních rohů všech obrazových bloků a potom následujících koeficientů ze všech bloků. Takovýto postup se označuje jako progresivní JPEG a jeho výhodou je postupná rekonstrukce obrazu už během jeho přebírání. JPEG navíc nabízí tzv. hierarchický režim, kde se obraz kóduje pyramidovým způsobem ve vrstvách. Každý pixel vyšší vrstvy vznikne použitím určité operace na blok 2x2 nacházející se přímo pod ním. Každou vrstvu dokáže dekodér dekódovat samostatně, což umožňuje použít obraz při různých rozlišeních.

Seřazování koeficientů do 1rozměrného vektoru pomocí cik-cak čítání

Standard JPEG podporuje též bezeztrátové kódování založené na predikčním kódování a bezeztrátovém VLC kódovaní, čímž se vynechává DCT a úpravy spektra. Typický kompresní poměr je přibližně 2:1.

JPEG 2000

Formát JPEG 2000 se snaží nahradit nedokonalý, ale stále výrazně oblíbenější formát JPEG. Rozšiřuje možnosti svého předchůdce, zlepšuje poměr kvalita/komprese, umožňuje škálovatelnou ztrátovou a bezeztrátovou kompresi. Mezi další vylepšení patří kódování oblasti zájmu, při kterém se důležité části obrazu kódují přesněji než zbytek.

Obecné schéma kodéru JPEG 2000

Transformační funkce se změnila z DCT na 1D diskrétní waveletovou transformaci (DWT). Původní obraz se transformuje pomocí waveletu, kvantizuje a entropicky zakóduje. Hlavní rozdíl mezi DCT a waveletovou transformací spočívá v tom, že DWT rozděluje bloky obrazu na podbloky, které se rozkládají na podbloky, atd.

Příklad rozkladu obrazu pomocí 2D DWT. Všimněte si, jak jsou detaily rozdělené do bloků. Každý blok je tvořen DWT transformací v horizontálním, vertikálním a diagonálním směru. Nižší úroveň se rozkládá do bloků vyšší úrovně.

Wavelet je část funkce ve tvaru vlnky, která, na rozdíl od řekněme funkce sinus jdoucí od nekonečna do nekonečna, má stanovený začátek, amplitudu a konec. Může mít různé tvary, které si vybíráme v závislosti na charakteru analyzovaného signálu.

Waveletová transformace v podstatě hledá podobnost waveletu s částí analyzovaného signálu. Jestliže wavelet má svůj začátek a konec, můžeme ho „roztahovat v libovolné míře“. Když použijeme přesně stanovené kroky míry, získáme víceúrovňové waveletové spektrum.

DWT transformace vytváří 2 soupravy vzorků, vzniklé filtrací dolní-, resp. horní propustí. Na úspěšnou rekonstrukci signálu však potřebujeme znát jen vzorky z filtru typu horní propust každé úrovně rozlišení. Ty představují detaily, které musíme přidat k odhadu signálu v nižší úrovni, abychom mohli zrekonstruovat vyšší úroveň.

GIF

Formát GIF (Graphics Interchange Format) je na Internetu stále populárním formátem obrázkových souborů. Byl uveden v roce 1987 a představuje bitmapový formát s podporou 8bitové barevné palety, přehlednost a má dobrý kompresní poměr. V důsledku omezené palety barev (255 barev) má omezené použití pro obrazy s vysokou věrností, jako jsou fotografie. Je však vhodný na obrázky s omezeným počtem barev, jako jsou např. loga, s ostrými hranami a minimálními barevnými přechody. Druhá verze formátu (1989) přináší podporu přehlednosti.

GIF pro kompresi obrazových údajů používá algoritmus Lempel-Ziv-Welch (LZW), který barvám v barevné paletě přiřazuje bytové sekvence ze slovníku.

Přesto, že dnes existují pokročilejší algoritmy, například PNG, formát GIF si stále udržuje svoji popularitu díky svojí podpoře pro animace umístěním více obrázků nad sebou. Tato vlastnost byla využita na vytváření plnobarevných (24bitových) obrázků a animací umístěním třech 8bitových rámců na sebe, kde každý rámec obsahuje část 24bitové barevné palety.

PNG

Portable Network Graphics (přenosná síťová grafika) je bitmapový obrazový formát určený k náhradě formátu GIF, který je zatížen licenčními a technickými omezeními. Byl představen v roce 1996 a mezinárodním standardem ISO/IEC se stal v roce 2004. PNG podporuje barevné prostory RGB a RGBA s 8 bity/barva (24bitové RGB a 32bitové RGBA).

Formát PNG je velmi flexibilní díky svojí struktuře podobné kontejneru. Obraz se vytvoří „po kouscích“, které umožňují rozložit obrazovou informaci a podporuje se vrstvení a streamování dat.

Bezeztrátová komprese pracuje ve dvou krocích:

Během předkomprese se původní množství obrazových dat zredukuje metodou podobnou DPCM: hodnota pixelu se ukládá jako rozdíl mezi ním a pixelem vlevo, nad ním, vlevo nad ním anebo jejich kombinace. Na každý řádek pixelů je možno použít jiný filtr. Potom se hodnoty komprimují algoritmem DEFLATE, který nahrazuje stejné řetězce referencemi a Huffmanovo kódování používá nikoliv na celý obraz, ale na jednotlivé bloky dat.

První návrh na název formátu byl PING – „PING is not GIF“ (PING není GIF).

V porovnání s formátem JPEG vytváří formát PNG z fotografií s jemnými přechody větší soubory.

Přesto má formát JPEG velké problémy při zpracování ostrých přechodů a hran, jako je text, čáry anebo grafika, a na velkých plochách stejné barvy, kde vytváří artefakty. PNG je schopen lepší komprese, po které nezůstávají žádné artefakty, takže je ideální pro použití na webu.

Porovnání obrázků zakódovaných ve formátu JPEG (vyšší) a PNG (nižší). U JPEG verzi jsou na hranách viditelné nedokonalosti na hranách. Velikost souboru JPEG je 61 kbit, soubor PNG má pouze 11 kbit.

WebP

Nejmladší z obrazových formátů WebP, uvedly laboratoře společnosti Google v roku 2010. Prezentují ho jako nový otevřený standard, který chce soutěžit se stále populárním formátem JPEG. WebP v sobě spojuje nejlepší vlastnosti JPEG (dobré zpracování plněbarevné grafiky), JPEG 2000 (ztrátová i bezeztrátová komprese), PNG (přehlednost ve ztrátovém i bezeztrátovém režimu) a GIF (podpora animací).

Ztrátový algoritmus je založen na postupech ve video formátu VP8. Komprese je založena na predikci obrazových bloků ze třech bloků nad a jednoho nalevo od analyzovaného bloku s použitím jednoho ze čtyř režimů: horizontální, vertikální, DC (jedna barva) a TrueMotion. Špatně predikované a nepredikované bloky se potom komprimují v blocích 4x4 pixelů pomocí CDT anebo Walsh-Hadamartové transformace. Výstup se entropicky zakóduje.

Kromě běžných technik jako jsou slovníkové a Huffmanovo kódování používá bezeztrátový algoritmus pokročilé metody jako různé entropické kódy pro různé barevné kanály anebo dočasná paměť nedávno použitých barev.

V porovnání s jinými obrazovými formáty JPEG a PNG, formát WebP překonává svoje konkurenty ve svých zaměřeních nejméně o 20%. WebP je v současnosti podporován na Linux a Windows pomocí pluginů a podporují ho i vyhledavače Firefox, Chrome a Opera.