Metódy kompresie
Kompresia statických obrazov

Cieľom kompresie obrazov je redukcia nepotrebných informácií v obraze na zníženie šírky potrebného prenosového pásma alebo ukladacieho priestoru. Podobne ako pri audio signáloch existujú pri obraze stratové aj bezstratové algoritmy, ktoré sa používajú v závislosti od cieľového použitia.

Pri analýze obrazov automaticky predpokladáme používanie 2-rozmerných verzií transformácií.

Na to, aby sme mohli v počítači ukladať obrázky, existujú rôzne farebné priestory. Uvádzame tie najpoužívanejšie.

Vybrané farebné priestory

Skratka

Význam

Vysvetlenie

RGB

Red, Green, Blue

(červená, zelená, modrá)

Každý pixel je daný kombináciou 3 farieb svetla. Kombinácia najvyšších úrovní všetkých 3 farieb dáva bielu. Používa sa pri obrazoch vytváraných svetlom.

RGBA

Red, Green, Blue, Alpha

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

Rovnaký význam ako pri RGB. Pridaný alfa kanál popisuje priehľadnosť.

YCBCR alebo YUV

Jas (Y), Modrá farebnosť (U), Červená farebnosť (V)

Jas sa mení od čiernej po bielu. Modrá a červená farebnosť sa vypočítajú z daného zdroja RGB. Hoci sa YCBCR označuje aj ako YUV, existujú medzi nimi rozdiely pri výpočte zložiek farebnosti.

CMYK

Cyan, Magenta, Yellow, Black

(azúrová, purpurová, žltá, čierna)

Každý bod obrazu je daný kombináciou štyroch farieb. Kombinácia najvyšších úrovní všetkých 4 farieb dáva čiernu. Používa sa v tlači.

JPEG

Štandard JPEG je jedným z najpoužívanejších stratových obrazových formátov na ukladanie fotografií. Je pomenovaný podľa spojenej expertnej skupiny pre obraz (Joint Picture Experts Group), ktorá štandard uviedla v roku 1986. Dosahuje kompresný pomer 10:1 s minimálnou postrehnuteľnou stratou kvality.

Algoritmus JPEG je založený na 2-rozmernej diskrétnej kosínusovej transformácii (DCT). Vstupný obraz sa skonvertuje do farebného priestoru YCBCR, ktorý poskytuje lepšie vlastnosti než povedzme RGB. Obraz sa potom rozdelí na neprekrývajúce sa bloky veľkosti 8x8 bodov, ktoré sa transformujú pomocou DCT. Získané koeficienty sa kvantizujú a málo významné koeficienty sa odstránia (tu dochádza k stratovej kompresii). Koeficienty sa potom zoradia do 1-rozmernej sekvencie a bezstratovo zakódujú. Obrazové komponenty (Y, CB a CR) sa kódujú postupne.

Obr. 5.12: Všeobecná schéma kódéra JPEG. Vstupom je blok 8x8 bodov jasovej alebo farebnostnej zložky.

Kľúčom v kompresii JPEG algoritmom je kvantizácia. Kvantizácia je nelineárna, keďže ľudské oko je citlivejšie na zmeny v nízkych frekvenciách. Na to, aby bola kvalita, resp. kompresný pomer, meniteľná, bol zavedený faktor kvality qf, ktorý sa mení v rozsahu 1 až 100 a upravuje kvantizačnú maticu.

Na zoradenie koeficientov slúži tzv. cik-cak čítanie, ktoré začína v ľavom hornom rohu. Ak sa každý blok 8x8 zakóduje spolu, kódovanie sa označuje ako základné (baseline) JPEG. Iným prístupom je kódovanie najskôr ľavých horných rohov všetkých obrazových blokov a potom nasledujúcich koeficientov zo všetkých blokov. Takýto postup sa označuje ako progresívny JPEG a jeho výhodou je postupná rekonštrukcia obrazu už počas jeho preberania. JPEG navyše ponúka hierarchický režim, kde sa obraz kóduje pyramídovým spôsobom vo vrstvách. Každý pixel vyššej vrstvy vznikne použitím určitej operácie na blok 2x2 nachádzajúci sa priamo pod ním. Každú vrstvu dokáže dekóder dekódovať samostatne, čo umožňuje použiť obraz pri rôznych rozlíšeniach.

Obr. 5.13: Zoraďovanie koeficientov do 1-rozmerného vektora pomocou cik-cak čítania

Štandard JPEG podporuje tiež bezstratové kódovanie založené na predikčnom kódovaní a bezstratovom VLC kódovaní, čím sa vynecháva DCT a úpravy spektra. Typický kompresný pomer je približne 2:1.

JPEG 2000

Formát JPEG 2000 (Obr. 5.14) sa snaží nahradiť nedokonalý, no stále výrazne obľúbenejší formát JPEG. Rozširuje možnosti svojho predchodcu, zlepšuje pomer kvalita/kompresia, umožňuje škálovateľnú stratovú a bezstratovú kompresiu. Medzi ďalšie vylepšenia patrí kódovanie oblasti záujmu, pri ktorom sa dôležité časti obrazu kódujú presnejšie než zvyšok.

Obr. 5.14: Všeobecná schéma kódera JPEG 2000

Transformačná funkcia sa zmenila z DCT na 1D diskrétnu waveletovú transformáciu (DWT). Pôvodný obraz sa transformuje pomocou waveletu, kvantizuje a entropicky zakóduje. Hlavný rozdiel medzi DCT a waveletovou transformáciou je v tom, že DWT rozdeľuje bloky obrazu na podbloky, ktoré sa rozkladajú na podbloky, atď.

Obr. 5.15: Príklad rozkladu obrazu pomocou 2D DWT. Všimnite si, ako sú detaily rozdelené do blokov. Každý blok je tvorený DWT transformáciou v horizontálnom, vertikálnom a diagonálnom smere. Nižšia úroveň sa rozkladá do blokov vyššej úrovne.

Wavelet je časť funkcie v tvare vlnky, ktorá, na rozdiel od povedzme funkcie sínus idúcej od nekonečna do nekonečna, má stanovený začiatok, amplitúdu a koniec. Môže mať rôzne tvary, ktoré si vyberáme v závislosti od charakteru analyzovaného signálu.

Waveletová transformácia v podstate hľadá podobnosť waveletu s časťou analyzovaného signálu. Keďže wavelet má svoj začiatok a koniec, môžeme ho rozťahovať v ľubovoľnej mierke. Ak použijeme presne stanovené kroky mierky, získame viacúrovňové waveletové spektrum.

DWT transformácia vytvára 2 súpravy vzoriek, vzniknuté filtráciou dolno-, resp. hornopriepustným filtrom. Na úspešnú rekonštrukciu signálu však potrebujeme poznať iba vzorky z hornopriepustného filtra každej úrovne rozlíšenia. Tie predstavujú detaily, ktoré musíme pridať k odhadu signálu v nižšej úrovni, aby sme mohli zrekonštruovať vyššiu úroveň.

GIF

Formát GIF (Graphics Interchange Format) je na Internete stále populárnym formátom obrázkových súborov. Bol uvedený v roku 1987 a predstavuje bitmapový formát s podporou 8-bitovej farebnej palety, priehľadnosti a má dobrý kompresný pomer. Kvôli obmedzenej palete farieb (255 farieb) má obmedzené použitie pre obrazy s vysokou vernosťou, ako sú fotografie. Je však vhodný na obrázky s obmedzeným počtom farieb, s ostrými hranami a minimálnymi farebnými prechodmi, ako sú napríklad logá. Druhá verzia formátu (1989) prináša podporu priehľadnosti.

GIF na kompresiu obrazových údajov používa algoritmus Lempel-Ziv-Welch (LZW), ktorý farbám vo farebnej palete priraďuje bajtové sekvencie zo slovníka.

Napriek tomu, že v súčasnosti existujú pokročilejšie algoritmy, napríklad PNG, formát GIF si stale udržuje svoju popularitu vďaka svojej podpore pre animácie umiestnením viacerých obrázkov jeden nad druhý. Táto vlastnosť bola využitá na vytváranie plnofarebných (24-bitových) obrázkov a animácií umiestnením troch 8-bitových rámcov na seba, kde každý rámec obsahuje časť 24-bitovej farebnej palety.

PNG

Portable Network Graphics (prenosná sieťová grafika) je bitmapový obrazový formát určený na nahradenie formátu GIF, ktorý je zaťažený licenčnými aj technickými obmedzeniami. Bol predstavený v roku 1996 a medzinárodným štandardom ISO/IEC sa stal v roku 2004. PNG podporuje farebné priestory RGB a RGBA s 8 bitmi/farba (24-bitové RGB a 32-bitové RGBA).

Formát PNG je veľmi flexibilný vďaka svojej štruktúre podobnej kontajneru. Obraz sa vytvorí po kúskoch, ktoré umožňujú rozložiť obrazovú informáciu, podporujú vrstvenie a streamovanie dát.

Bezstratová kompresia pracuje v dvoch krokoch:

Počas predkompresie sa množstvo obrazových dát zredukuje metódou podobnou DPCM: hodnota pixelu sa ukladá ako rozdiel medzi ním a pixelom vľavo, nad ním, vľavo nad ním alebo ich kombinácie. Na každý riadok pixelov je možné použiť iný filter. Potom sa hodnoty komprimujú algoritmom DEFLATE, ktorý nahrádza rovnaké reťazce referenciami, a Huffmanovo kódovanie používa nie na celý obraz, ale na jednotlivé bloky dát.

Prvý návrh na názov formátu bol PING – „PING is not GIF“ (PING nie je GIF).

V porovnaní s formátom JPEG vytvára formát PNG z fotografií s jemnými prechodmi väčšie súbory.

Napriek tomu má formát JPEG veľké problémy pri spracovaní ostrých prechodov a hrán, ako je text, línie alebo grafika, a na veľkých plochách rovnakej farby, kde vytvára artefakty. PNG je schopný lepšej kompresie, po ktorej nezostávajú žiadne artefakty, takže je ideálny na použitie na webe.

Obr. 5.16: Porovnanie obrázkov zakódovaných vo formáte JPEG (vyššie) a PNG (nižšie). Pri JPEG verzii sú na hranách viditeľné nedokonalosti na hranách. Veľkosť súboru JPEG je 61 kB, súbor PNG má iba 11 kB.

WebP

Najmladší z obrazových formátov, WebP, uviedli laboratóriá spoločnosti Google v roku 2010. Prezentujú ho ako nový otvorený štandard, ktorý chce súťažiť so stále populárnym JPEG-om. WebP v sebe spája najlepšie vlastnosti JPEG (dobré spracovanie plnofarebnej grafiky), JPEG 2000 (stratová aj bezstratová kompresia), PNG (priehľadnosť v stratovom aj bezstratovom režime) a GIF (podpora animácií).

Stratový algoritmus je založený na postupoch vo video formáte VP8. Kompresia je založená na predikcii obrazových blokov z troch blokov nad a jedného naľavo od analyzovaného bloku s použitím jedného zo štyroch režimov: horizontálny, vertikálny, DC (jedna farba) a TrueMotion. Zle predikované a nepredikované bloky sa potom komprimujú v blokoch 4x4 pixelov pomocou CDT alebo Walsh-Hadamartovej transformácie. Výstup sa entropicky zakóduje.

Okrem bežných techník ako je slovníkové a Huffmanovo kódovanie používa bezstratový algoritmus pokročilé metódy ako rozličné entropické kódy pre rôzne farebné kanály alebo dočasná pamäť nedávno použitých farieb.

V porovnaní s obrazovými formátmi JPEG a PNG sa WebP javí prekonať svojich konkurentov vo svojich zameraniach najmenej o 20%. WebP je v súčasnosti podporovaný na Linux a Windows pomocou pluginov a podporujú ho aj prehliadače Firefox, Chrome a Opera.