Prediktory
Kódování rozdílů (delta kódování) je jednoduchou metodou, která předchází vlastní kompresi. Jejím účelem je zvýšit další komprimovatelnost dat. Lze ji chápat i jako jednoduchou prediktivní metodu. Používá se stejně jako v předchozím případě jako součást složitějších metod. Jádro spočívá v nahrazení vstupní hodnoty za její rozdíl proti hodnotě předcházející.
Jedná se vlastně o jednoduchou predikční metodu. Snaží se predikovat (předpovědět) současný symbol tak, že jako odhad použije symbol předchozí. Na výstup pak pošle pouze jejich rozdíl (chybu predikce).
Příklad
V následujícím příkladu je sekvence hodnot z intervalu ⟨16, 35⟩ se střední hodnotou 27 transformována na sekvenci z intervalu ⟨−6, 14⟩ se střední hodnotou 1,375. Základním předpokladem vedoucím ke kompresi je skutečnost, že následující část kompresního řetězce bude schopna zakódovat transformované hodnoty kratšími kódovými slovy. Jinak řečeno malá čísla koncentrovaná okolo 0 se v další části lépe komprimují.
Prediktivní kódování
Kódování rozdílů je nejjednodušší prediktivní (predikční) metodou. Prediktor se snaží predikovat právě kódovaný symbol (pixel) ze symbolů již zakódovaných (tedy známých i dekódující straně). Výstupem jsou chyby predikce neboli rozdíly predikovaných hodnot od hodnot skutečných. Dekodér spočítá stejně jako kodér předpokládanou hodnotu právě dekódovaného symbolu a přičte k ní obdržený rozdíl. Podle počtu hodnot použitých k predikci se hovoří o řádu prediktoru. Kódování rozdílů používá tedy prediktor prvního řádu, protože k predikci hodnoty použije pouze jednu předchozí hodnotu.
Prediktory se dále dělí na lineární (vážený průměr několika okolních pixelů, kódování rozdílů) a nelineární (medián několika okolních pixelů, MED/LOCO-I, Paeth, GAP). U lineárních se predikovaná hodnota spočte jako vážený průměr z již přenesených hodnot. U nelineárních je na již přenesené hodnoty aplikována některá nelineární funkce, např. porovnání, minimum, maximum nebo medián.
Triviální prediktor by jako odhad x na obrázku výše mohl použít jednu z hodnot a, b, c nebo d. Další možností je spočíst z několika těchto sousedů průměr, popřípadě medián. K výpočtu není možné použít hodnoty bílých pixelů, protože ty ještě nejsou známy dekódovací straně.
V případě hladkého okolí bodu x může být dobrým odhadem jeho hodnoty proložení okolních bodů a, b a c rovinou p v rovnici níže. Takový odhad však nebude dávat dobré výsledky na hranách. Proložení znázorňuje obrázku výše, kde jsou z každého pixelu vedeny kolmice o výšce odpovídající jeho hodnotě.
Například nelineární prediktor MED (rovnice níže), který je použit ve standardu LOCO-I/JPEG-LS, předpovídá hodnotu pixelu x ze tří již zpracovaných pixelů v jeho okolí. Jedná se tedy o prediktor třetího řádu. MED se nejprve pokusí detekovat hranu. V případě úspěchu použije jako predikci hodnotu pixelu, který leží na hraně. V opačném případě (hladké okolí x) proloží okolní body rovinou a jako odhad použije bod ležící na ní, tedy hodnotu p z rovnice výše.
Právě uvedenou definici lze také zapsat jako:
Další takový nelineární editor Paeth (rovnice níže) je použit ve standardu PNG. Ten jako predikci použije toho souseda, který je nejblíž odhadu p.
Ve složitějším prediktoru GAP, který je použit ve standardu CALIC, je nejprve odhadnut gradient obrazu v okolí bodu x. Podle gradientu je následně detekuje přítomnost a síla hrany (slabá/silná, horizontální/vertikální). Na základě přítomnosti hrany je pak rozhodnuto o vztahu pro výpočet odhadu pixelu.
GIF
GIF (Graphics Interchange Format) vyvinula společnost CompuServe v roce 1987. Původní verze se označuje jako GIF87a, současný standard je GIF89a. GIF dokáže pojmout několik obrazových rámců o barevné hloubce 24 bitů. V jednom rámci však může být obsaženo maximálně 256 různých barev. Rámce však mohou obsahovat průhledné pixely. Překrýváním rámců přes sebe je tak možno zvětšit celkovou barevnou hloubku až na plných 16 milionů barev (224 = 16 777 216). Tradované tvrzení, že GIF dokáže pojmout pouze obrázky ve 256 barvách, je tedy nepravdivé nebo přinejmenším nepřesné (hledejte pojem „true color GIF“).
Na druhou stranu se s takovými obrázky nelze běžně setkat a to ze dvou důvodů – za prvé absence programů, které dokáží takový GIF vytvořit, a za druhé často chybná implementace zobrazování těchto souborů (programy chybně vkládají zpoždění mezi rámce s uvedeným nulovým trváním). Stejným způsobem lze dosáhnout také animace (rámce se vykreslují přes sebe s časovým zpožděním). Formát GIF využívá slovníkový kompresní algoritmus LZW, který byl dlouhá léta patentován (poslední patent vypršel v roce 2004). Proto také vznikl formát PNG, který není patenty zatížen.
Soubor ve formátu GIF neobsahuje popis obrázku jako celku. Obrázek zde tvoří tzv. logickou obrazovku. Ta je teprve pokryta překrývajícími se rámci, které teprve obsahují obrazová data. Rámce jsou obdélníkové oblasti a nemusejí vyplňovat celou logickou obrazovku. Zbývající část se jednoduše vykreslí barvou pozadí. Příklad je zobrazen na obrázku níže.
Maximální množství rámců není omezeno. Ke každému rámci může být přiřazena lokální barevná paleta. Celá logická obrazovka má pak přiřazenu globální barevnou paletu. Rámec je vykreslován svou lokální barevnou paletou. Pokud tato není přítomna, použije se ta globální. Verze 89a zavádí rozšíření, pomocí kterého lze nastavit dobu zobrazení rámce.
Barevné palety mohou být indexovány maximálně 8 bity (28 = 256 barev). Každá barva je popsána trojicí bajtů, které udávají pixel ve formátu RGB24. V případě nepřítomnosti lokální i globální palety by měl vykreslující program použít paletu systémovou. Pak je ovšem zobrazení závislé na programu. Barva pozadí je určena z globální palety.
Od verze 89a lze u barevných palet určit index průhledného pixelu. Jedna barva z palety tedy může být označena jako průhledná. Jedná se jen o binární hodnotu, tedy zcela průhledný a zcela neprůhledný pixel. GIF nepodporuje alfa kanál.
GIF umožňuje uložit do každého rámce pixel, který je indexem do palety barev. Varianta LZW použitá v GIFu přidává do abecedy tvořené těmito indexy ještě další symboly. Prvním z nich je „clear code“, který přikazuje dekodéru, aby vyprázdnil svůj slovník. Dalším je symbol EOF. Indexy (ukazatele) do slovníku se s jeho vzrůstající velikostí prodlužují. Jsou seskupovány do bloků (max. 255 bajtů) a ukončeny nulovým bajtem. Poslední blok musí obsahovat symbol EOF. Pixely rámce jsou komprimovány postupně po řádcích. Není zde žádná predikce z předchozích pixelů ani žádné využití jejich prostorové sousednosti.
Formát má možnost prokládat obrazová data (progresivní přenos). Prokládání rozdělí obraz na pruhy 8 řádků vysoké. Nejprve se přenese každý osmý řádek z každého pruhu, pak každý čtvrtý, atd. Celkem jsou tak při prokládání 4 průchody. Pořadí znázorňuje tabulka níže. Prokládaný soubor GIF je v porovnání s neprokládaným větší. Prokládání může být u každého rámce různé (zapnuto/vypnuto).
Řádek sekvenčně | Průchod prokládání | Řádek prokládaně |
---|---|---|
1 | 1 | 1 |
2 | 4 | 5 |
3 | 3 | 3 |
4 | 4 | 6 |
5 | 2 | 2 |
6 | 4 | 7 |
7 | 3 | 4 |
8 | 4 | 8 |
Od verze 89a jsou podporovány také animace. Animace je řada po sobě promítaných rámců, které se postupně překreslují. Mezi jejich zobrazením je vložena časová prodleva.
Od verze 89a je též možno podmínit zobrazení následujícího rámce vstupem uživatele (stisk klávesy nebo tlačítka myši). Podpora této funkce v programech je minimální.
Soubor ve formátu GIF je vnitřně rozčleněn do bloků. Některé z bloků jsou povinné, jiné nikoli. Některé z bloků je též možno opakovat (bloky vztažené k rámci). Soubor začíná signaturou ( GIF
v ASCII) a indikací verze, dále následuje popis logické obrazovky (např. rozlišení). Následně může být přítomna globální paleta barev. Dále už následuje popis rámce, lokální paleta a data rámce. Tyto bloky se samozřejmě mohou opakovat. Soubor je ukončen speciálním znakem ( 0x3b
). Od verze 89a je možno vložit ještě další rozšiřující bloky. Ty mohou přidávat metainformace, nastavovat třeba dobu zobrazení rámců nebo počet opakování animace.
PNG
Formát PNG (Portable Network Graphics) byl vyvinut v polovině 90. let jako odpověď na patentovaný formát GIF (metoda LZW používaná v GIFu byla patentována americkou společností Unisys). PNG je tedy nezatížený patenty. Formát je rozšiřitelný a podporuje mnoho barevných typů, prokládání, alfa kanál (průhlednost pixelů) a využívá kompresní metodu Deflate.
Formát sestává z bloků, přičemž každý může mít různý typ i velikost. Některé z nich jsou kritické a každý dekodér je musí být schopen zpracovat. Jiné jsou pomocné (např. metainformace). Blok sestává z následujících částí – velikosti, názvu, vlastních dat a 32bitového CRC. Blok má čtyřpísmenný název, z něhož velikost prvního písmene udává důležitost bloku (velké písmeno pro kritické bloky, malé pro pomocné). Podobně velikost druhého písmene udává, zdali se jedná o registrovaný nebo soukromý blok (velké pro registrované skupinou PNG, malé pro privátní). Třetí písmeno je vždy velké. Poslední čtvrté písmeno je velké, jestliže by blok neměl být kopírován, malé jinak. To má smysl při zpracování/úpravě obrázku PNG aplikací, která danému typu bloku nerozumí.
Každá aplikace pracující s PNG jednoduše zpracovává bloky, kterým rozumí. Může bezpečně přeskočit všechny pomocné bloky, které nezná. Jestliže však narazí na kritický blok, který nezná, měla by nahlásit chybu a v dekódování dále nepokračovat.
Čtyři kritické bloky definované standardem PNG jsou IHDR
(hlavička), PLTE
(paleta), IDAT
(obrazová data) a IEND
(patička). Soubor PNG začíná 8bajtovou signaturou. Bezprostředně za ní následuje blok IHDR
, který nese informace o rozměrech obrázku, počtu bitových rovin, apod. Pro paletové obrázky musí následovat blok PLTE
. Následuje jeden nebo více bloku IDAT
s komprimovanými pixely. Soubor pak končí blokem IEND
.
PNG může pojmout obrázek v barevném modelu RGB s hloubkou 8 nebo 16 bitů, paletový obrázek s hloubkou 1, 2, 4 nebo 8 bitů, obrázek ve stupních šedi s hloubkou 1, 2, 4, 8 nebo 16 bitů, RGB s alfa kanálem s hloubkou 8 nebo 16 bitů a stupně šedi a alfa kanálem s hloubkou 8 nebo 16 bitů. Dovolené kombinace uvádí tabulka níže. Alfa kanál udává ke každému pixelu jeho průhlednost. Je to číslo α v intervalu ⟨0, 2bits − 1⟩ (bits značí bitovou hloubku), které určuje váhu barvy vykreslovaného pixelu P a barvy pozadí B. Pixel je pak vykreslen barvou, která se získá kombinací (1 − α)B + αP. U typů pixelu, které neobsahují alfa kanál, je možno specifikovat jeden plně průhledný pixel v pomocném bloku tRNS
.
Typ obrazu | Kanály | Bitové hloubky |
---|---|---|
paleta | indexy | 1, 2, 4, 8 |
stupně šedi | Y | 1, 2, 4, 8, 16 |
stupně šedi s průhledností | Y, A | 8, 16 |
true color | R, G, B | 8, 16 |
true color s průhledností | R, G, B, A | 8, 16 |
Prokládání definované standardem PNG umožňuje dekódovací straně zobrazit obrázek nejprve v hrubém náhledu a pak jej postupně zjemňovat až do plné kvality. Užitá metoda prokládání se nazývá Adam7. Ta rozdělí obraz nejprve do bloků 8×8 pixelů. Každý tento blok je zobrazen v sedmi krocích. V prvním kroku se celý blok vykreslí barvou pixelu v levém horním rohu. V každém dalším kroku je rozlišení bloku zdvojnásobeno. V posledním kroku má každý pixel svou vlastní barvu. Pořadí pixelů je uvedeno v tabulce níže. Tabulka znázorňuje pořadí, ve kterém jsou zpracovávány pixely v prokládání Adam7. V prvním průchodu jsou z každého bloku zpracovány pixely označené jako 1, ve druhém 2, atd.
1 | 6 | 4 | 6 | 2 | 6 | 4 | 6 |
7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
5 | 6 | 5 | 6 | 5 | 6 | 5 | 6 |
7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
3 | 6 | 4 | 6 | 3 | 6 | 4 | 6 |
7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
5 | 6 | 5 | 6 | 5 | 6 | 5 | 6 |
7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
Vlastní komprese obrazu probíhá ve dvou krocích. Prvním krokem je predikce (ve standardu PNG nazývaná filtrace), která nahradí každý pixel chybou proti predikované hodnotě. Druhý krok je slovníková metoda Deflate, která se aplikuje na tyto chyby predikce.
Predikce (filtrace) neprovádí žádnou kompresi dat. Namísto toho nahradí sekvenci vstupních bajtů jinou sekvencí, kterou je Deflate schopen zkomprimovat více v porovnání se sekvencí původní. Predikce je aplikována na řádky, přičemž na každý řádek může být použit odlišný prediktor. To otevírá kompresoru cestu k vyzkoušení všech prediktorů a výběru toho nejlepšího. Predikce se provádí po bajtech, které nemusejí nutně odpovídat pixelům.
Například při použití barevného formátu RGB s hloubkou 8 bitů mají pixely formát RGB24. Predikce je pak aplikována separátně na kanál R, G a B, tedy po bajtech. Dále při použití 16bitové hloubky je predikce aplikována zvlášť na horní bajt a zvlášť na dolní bajt 16bitového pixelu. Prediktory definované ve standardu PNG jsou uvedeny v tabulce níže. Hodnota chyby predikce e se spočte ze skutečné x a predikované x̂ hodnoty jako e = x − x̂. Odečtení je počítáno v modulu 256, výsledkem je tedy opět jeden bajt.
Prediktor | Predikovaná hodnota |
---|---|
žádný | 0 |
levý | b |
horní | a |
průměr | ⌊(a + b) / 2⌋ |
Paeth | rovnice pro prediktor Paeth (výše) |
JPEG-LS
JPEG-LS je bezeztrátový formát vytvořený jako náhrada za bezeztrátový režim formátu JPEG, který je neefektivní a většinou neimplementovaný. Nejedná se o modifikaci formátu JPEG, ale o novou metodu. Formálně je tento formát standardizován v ITU-T T.87 a ISO/IEC 14495–1 z roku 1998. Formát umožňuje komprimovat obraz bezeztrátově nebo téměř bezeztrátově. JPEG-LS je založen na algoritmu LOCO-I (LOw COmplexity LOssless COmpression for Images). Tato kompresní metoda se skládá z prediktoru a následného kontextového entropického kodéru (Golombův-Riceův kód). Mimo tento řetězec může kodér zakódovat sled stejných pixelů variantou metody RLE. Zjednodušený postup znázorňuje obrázek níže.
Komprese probíhá klasicky po řádcích. Pro vícekanálové obrazy (např. R, G, B) podporuje formát několik režimů prokládání – neprokládáný režim (jediný kanál), prokládání několika řádků, prokládání vzorků (složek pixelů). Pro paletové obrázky se použije jednoduše stejný postup jako pro obrázky jednokanálové.
JPEG-LS používá souborový formát založený na souborovém formátu pro metodu JPEG – JPEG Interchange Format (JIF). Komprimovaný tok dat je rozdělen do segmentů. Některé z nich nesou informace potřebné k dekódování (rozměry obrazu), jiné nesou komprimovaná obrazová data.
V dalších odstavcích se používá toto značení. Pro vzorek (pixel) x bude jeho hodnota ve vstupním obrázku označena jako Ix, jeho predikovaná hodnota Px a rekonstruovaná (dekomprimovaná) hodnota Rx.
Určení kontextu
Vzpomeneme si na první obrázek. Prediktor MED predikuje hodnotu pixelu x ze tří okolních pixel a, b, c. Gradient D je spočten z hodnot a–d. Nejprve je kolem právě kódovaného pixelu odhadnut gradient D = (D1, D2, D3) pomocí rovnice níže. Tento gradient zachycuje tvar obrazu okolo aktuálního pixelu x (hladkost, hranu).
Následně se podle tohoto gradientu vybere režim komprese. Pro nulový gradient (nebo nízkou absolutní hodnotu derivací u téměř bezeztrátové komprese) se pokračuje kódováním RLE. V opačném případě se použije běžný režim.
Trojice derivací Di udává obrovské množství kontextů pixelu x. U obrazu je též vhodné podobné kontexty spojovat. V běžném režimu komprese se proto gradient dále kvantuje na 93 = 729 hodnot. Při tomto kvantování se každá derivace Di kvantuje do celočíselných hladin Qi v intervalu ⟨−4, 4⟩. Pro každé Di je to tudíž 9 hladin Qi, pro všechny tři derivace tak celkem 93 = 729 kvantovaných gradientů. Kvantovaná trojice (Q1, Q2, Q3 je následně spojena s trojicí (−Q1, −Q2, −Q3). Tím došlo ke spojení kvantizovaných gradientů Q s opačnými znaménky. Současně bylo množství různých kvantovaných kontextů Q redukováno na 365. Takové spojení indikováno nastavením proměnné S na hodnotu −1 (jinak +1). V dalším kroku je těchto 365 kvantovaných gradientů namapováno na celá čísla v intervalu ⟨0, 364⟩, celkem tedy na 365 celočíselných hodnot.
Predikce
V běžném režimu komprese se hodnoty pixelů převedou na chyby prediktoru. Použitý prediktor detekuje okolo predikovaného pixelu hrany. Jestliže není hrana nalezena, pak se predikovaná hodnota vypočte jako Ra + Rb − Rc, což odpovídá proložení roviny bodem x. Taková predikce tedy předpokládá hladkost obrazu v okolí x. Jestliže je však nalezena vertikální hrana, odpovídá predikce hodnotě vzorku Rb na hraně. Stejně tak je predikováno Ra v případě horizontální hrany. Predikovaná hodnota se vypočte prediktorem MED (na začátku článku). Protože predikce musí být spočtena také dekodérem, počítá se ze rekonstruovaných hodnot pixelů Ra, Rb a Rc.
Dalším krokem je korekce této predikované hodnoty. Jejím účelem je vycentrovat rozložení chyb predikce do cílového intervalu. Tento krok je založen na akumulované hodnotě doposud vypočtených chyb predikce pro pixely se stejným kontextem. Tato korekce je tedy mj. závislá na kontextu Q. Za použití skutečné Ix a predikované Px hodnoty pixelu se vypočte chyba predikce E.
Pro téměř bezeztrátový režim komprese je chyba predikce ještě kvantována. V tomto režimu musí tedy kodér spočíst rekonstruovanou hodnotu pixelu Rx, což je normálně činnost dekodéru. To dělá, protože tato hodnota je dále užívána ke kompresi. U bezeztrátového režimu je Rx shodná s Ix, takže takový výpočet není třeba.
Kódování chyby predikce
Chyby predikce jsou kódovány variantou Golombova-Riceova kódu. Před vlastním kódováním je třeba převést chyby predikce na nezáporná celá čísla. Pro téměř bezeztrátový režim je tento převod mírně odlišný. Tyto nezáporné hodnoty jsou dále kódovány Golombovými-Riceovými kódy s limitem maximální délky. Parametr kódu je závislý na kontextu a aktualizuje se vždy, když je v tomto kontextu zakódována nová hodnota.
Režim kódování sledů
Jestliže je gradient kontextu nulový (malý u téměř bezeztrátového režimu), použije se režim RLE. Kompresor hledá a počítá až do konce řádku pixely Ix shodné s předchozím zakódovaným pixelem Ra. U téměř bezeztrátového režimu se hodnoty pixelů mohou mírně lišit. Když je sled přerušen neshodným pixelem Ix, bude tento zakódován běžným režimem komprese (jen s drobnými odlišnostmi). Délky sledů se kódují rozšířenou formou Golombova kódu.
(Autorem obrázků je David Bařina.)