Řádkové filtry v PNG

Obsah

1. Prokládání pixelů v rastrovém obrázku
2. Filtrace obrazových řádků před jejich komprimací
3. Filtr číslo 0: None
4. Filtr číslo 1: Sub
5. Filtr číslo 2: Up
6. Filtr číslo 3: Average
7. Filtr číslo 4: Paeth
8. Obsah dalšího pokračování tohoto seriálu

1. Prokládání pixelů v rastrovém obrázku

Už v první části tohoto seriálu jsme si řekli, že všechny tři nejpopulárnější webové grafické formáty, tj. GIF, JPEG i PNG obsahují podporu pro postupné zobrazování částí obrázků už v době jejich postupného načítání či přenosu po datové síti, tj. nikoli až při přenosu celého obrázku. Grafický formát GIF díky svému prokládanému režimu (scanline interlacing) umožňuje, aby se nejprve ukládaly a následně zobrazovaly obrazové řádky v rozdílném pořadí – nejprve – v prvním kroku – každý osmý řádek (12,5% celkového objemu nekomprimovaných dat), ve druhém kroku každý čtvrtý řádek (12,5% objemu dat), posléze zbývající sudé řádky (25% objemu dat) a nakonec všechny řádky liché (zbylých 50% objemu dat).

Grafický formát JPEG, ve kterém jsou pixely ukládány naprosto odlišným způsobem, naproti tomu nabízí takzvaný progresivní režim, při kterém jsou nejprve přenášeny koeficienty DCT transformace s nízkou frekvencí a teprve poté koeficienty s frekvencí vyšší. Pokud by nebyla použita ztrátová komprimace, stačilo by v prvním kroku přenést pouze 1/64 objemu dat (1,5625%), ve skutečnosti se však jedná o vyšší číslo, neboť ztrátová komprimace je založena na snižování počtu bitů u koeficientů s vyššími frekvencemi (na něž je lidské oko méně citlivé), takže koeficienty s frekvencemi nižšími zabírají v souboru větší objem.

Obojí způsob „prokládání“, tj. jak prokládání obrazových řádků, tak i progresivní režim, má za následek užitečný efekt způsobující, že se při přenosu obrázku na pomalých či lagujících linkách nejprve zobrazí hrubý náhled na obrázek, který je posléze s příchodem dalších dat zjemňován. Uživatel tak má již při přenosu poměrně malé části dat (v případě GIF jedné osminy, u JPEGu cca jedné dvacetiny) možnost udělat si představu o celém obrázku a popř. přenos zastavit (ve webových prohlížečích většinou klávesou ESC).

Způsob prokládání pixelů (interlacing, progressive display), který je implementován v grafickém formátu PNG, vznikl vylepšením řádkového prokládání použitého u formátu GIF. Zatímco se u GIFu je prokládání nesymetrické, protože je prováděno pouze ve vertikálním směru, je u PNG použito symetrické (alespoň v co největší míře) vícekrokové prokládání, tj. pixely jsou ukládány „napřeskáčku“ jak ve směru horizontálním, tak i ve směru vertikálním. Pro lidské vnímání je tento způsob přirozenější než čistě řádkové prokládání. Na schématu zobrazeném níže je patrné, jakým způsobem se přenáší blok o velikosti 8×8 pixelů. V prvním kroku je přenesen pixel označený číslicí 1 na prvním řádku, ve druhém kroku pixel označený číslicí 2, ve třetím kroku již 2 pixely na pátém řádku atd. V posledním kroku se přenese celá polovina dat, tj. všechny sudé řádky.

   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 

Symetrický způsob prokládání přináší tu výhodu, že prvotní náhled na obrázek je možné provést již po přenesení pouhé 1/64 (1,5625%) všech pixelů, zatímco u GIFu to byla celá 1/8 pixelů, tj. 12,5%. S respektováním určité nepřesnosti (přenos hlaviček, rozdíly díky aplikaci komprimace) je tedy možné říci, že první náhled na celý obrázek uložený ve formátu PNG je až osmkrát rychlejší, než náhled na obrázek typu GIF. Je však nutné poznamenat, že změna posloupnosti ukládaných pixelů má negativní vliv na komprimační poměr, protože se statisticky zmenšuje korelace mezi sousedními hodnotami – to ovšem platí pro všechny tři popisované souborové formáty.

Na prvním animovaném obrázku je naznačeno, jakým způsobem by se vykreslovala bitmapa o rozlišení 8×8 pixelů (to je velikost základního bloku pro prokládání) v případě, že by pozadí bylo zobrazeno bílou barvou a pixely by byly černé. Z animace je patrné, že schéma není zcela symetrické, protože se nejprve přenáší pixely v horizontálním směru a teprve poté ve směru vertikálním.

Obrázek 1: Sedm kroků vedoucích v vykreslení všech pixelů v obrázku

2. Filtrace obrazových řádků před jejich komprimací

Jak grafický formát GIF, tak i jeho přímý následovník PNG používá bezeztrátovou komprimační metodu založenou na hledání stejných posloupností v datech reprezentujících rastr pixelů. Obě komprimační metody (LZW v případě GIF a deflate v případě PNG) jsou však z lidského hlediska poměrně „hloupé“ v tom smyslu, že pouze sériově zpracovávají přicházející data a neudělají si dopředu kompletní představu o barvových a prostorových vlastnostech celého obrázku.

Z tohoto důvodu obsahuje grafický formát PNG jednu velmi zajímavou a prospěšnou funkci – na každý obrazový řádek je možné ještě před jeho komprimací aplikovat jednoduchý konvoluční filtr, jehož úkolem je předpřipravit data tak, aby se posléze komprimovala lépe. Většinou se počítá s tím, že se po aplikaci filtru (který hledá podobnosti sousedních pixelů – viz navazující kapitoly) v datech objeví větší množství pixelů s nulovou hodnotou, nebo hodnotou alespoň blízkou nule či naopak 255, čímž se statisticky zvýší pravděpodobnost toho, že komprimační program v datech nalezne delší shodné posloupnosti a tím zmenší výslednou délku souboru.

Filtrů, které je na jednotlivé obrazové řádky možné aplikovat, existuje v PNG celkem 5 (z toho nultý filtr vlastně žádnou filtraci neprovádí), přičemž však stojí za zmínku, že v současnosti není vyvinut žádný sofistikovaný algoritmus, který by zjistil, jaká kombinace filtrů vede k nejmenší velikosti výsledného souboru. Z tohoto důvodu se některé programy určené k optimalizaci grafických souborů typu PNG (například známý pngcrush) uchylují k metodám hrubé síly a přitom vykazují poměrně dobré výsledky – není výjimkou, že pngcrush zmenší velikost souboru PNG vygenerovaného jiným programem i o 10%, ovšem čas komprimace se zvyšuje až stonásobně.

Tyto programy by teoreticky mohly jít ještě dále a vyzkoušet celý stavový prostor parametrů, tj. na každý řádek aplikovat všechny kombinace filtrů, měnit parametry komprimačního algoritmu deflate apod. To je však časově ještě více náročné, proto snad (podle autorových znalostí) tuto techniku žádný program dosud nepoužívá.

O tom, že filtrace obrázků před jejich komprimací může být u některých typů obrázků účinná, svědčí i následující tabulka, ve které jsou zapsány výsledky komprimace jednoho známého reprezentativního obrazového souboru pomocí programu zip, který – stejně jako PNG – používá komprimační metodu deflate (pro znalce: jedná se o známý obrázek Leny, použitý v mnoha testech algoritmů pro zpracování obrazu, jehož originál můžete vidět například zde).

Každý obrázek (jejich screenshoty budou uvedeny v dalším textu) byl upraven pomocí jednoho filtru a posléze zkomprimován. Ve skutečném PNG je možné filtry pro každý obrazový řádek měnit, takže je možné dosáhnout ještě větších komprimačních poměrů.

Některé typy obrázků však obsahují jednobarevné plochy, které se v originále komprimují lépe než jejich filtrované kopie. Je to z toho důvodu, že filtry do obrázků vlastně zanáší (zvýrazňují) hrany, tj. do volných ploch přibývají další nepravidelnosti. U takových obrázků může být výhodnější filtraci neprovádět, resp. zvolit filtr None:

3. Filtr číslo 0: None

Nejjednodušším filtrem je u grafického formátu PNG filtr číslo 0 neboli None. Ve skutečnosti se o žádný filtr nejedná, protože pouze provádí kopii vstupních pixelů do pixelů výstupních bez jakéhokoli zpracování. V předcházející kapitole jsme viděli, že i tento typ „filtrů“ může být u některých obrázků užitečný. Na obrázku 2 a 3 jsou zobrazeny testovací obrázky tak, jak prošly filtrem None. Na pravé straně je u každého obrázku zobrazen i jeho histogram, aby bylo patrné, jak se tento statistický parametr obrázku bude lišit po filtraci obrázku. To, že u obrázku Leny se v jeho histogramu nachází nulové hodnoty a těsně vedle nich špičky, je způsobeno špatnou funkcí konverzního programu (patrně vlivem zaokrouhlení či useknutí výsledků nějakých aritmetických operací).

Obrázek 2: Testovací obrázek „Lena“ zpracovaný filtrem None

Obrázek 3: Testovací obrázek „Tcl/Tk“ zpracovaný filtrem None

4. Filtr číslo 1: Sub

Filtr číslo 1 má název Sub. Jedná se o velmi jednoduchý filtr, který na svůj výstup posílá rozdíl mezi dvěma byty. Tyto byty reprezentují buď odstín šedi či index do barvové palety (obrázky grayscale a palette based) nebo hodnotu uloženou v jednom barvovém kanálu (obrázky typu RGB a RGBA). Při výpočtu rozdílů bytů může dojít k podtečení, to je však dovoleno – z tohoto důvodu musí všechny výpočty probíhat po jednotlivých bytech a ne po vyšších celcích. Specifikace také řeší okrajové podmínky – pixely, které leží mimo hranice obrázku, mají definitoricky nastavenou nulovou hodnotu ve všech barvových kanálech. Na obrázcích 4 a 5 jsou zobrazena testovací data i se svými histogramy. Za povšimnutí stojí zejména vyfiltrovaný obrázek Leny, ve kterém došlo ke znatelné změně histogramu – více se vyskytují hodnoty v okolí 0 a 255. Z obrázku Tcl/Tk je patrné, že filtr Sub velmi jednoduchým způsobem detekuje vertikální hrany v obrázku (ty se tudíž špatně komprimují).

Obrázek 4: Testovací obrázek „Lena“ zpracovaný filtrem Sub

Obrázek 5: Testovací obrázek „Tcl/Tk“ zpracovaný filtrem Sub

//-----------------------------------------------------------------------------
// Aplikace filtru Sub na paletové obrázky či na grayscale obrázky
//-----------------------------------------------------------------------------
void applyFilterSub(pixmap *p1, pixmap *p2)
{
    int i, j;
    unsigned char sub;
    for (j=0; j<p1->height; j++) {      // pro všechny řádky zdrojové pixmapy
        for (i=0; i<p1->width; i++) {   // pro všechny pixely na řádku
            sub=getpixel(p1, i, j)-getpixel(p1, i-1, j); // provést filtraci
            putpixel(p2, i, j, sub);    // zápis výsledku do cílové pixmapy
        }
    }
} 

5. Filtr číslo 2: Up

Filtr číslo 2 má název Up. Jedná se o obdobu filtru Sub, pouze s tím rozdílem, že se porovnávají pixely (resp. jejich barvové složky) umístěné nad sebou a nikoli vedle sebe. Opět se využívá definitorického nastavení pixelů mimo obrázek na nulu (používat filtr Up na první obrazový řádek je však IMHO zcela zbytečné). Na šestém a sedmém obrázku jsou testovací data upravená tímto filtrem; opět si můžeme všimnout výrazné změny v histogramu a také toho, že filtr detekuje horizontální hrany (ty se tedy komprimují nejhůře).

Obrázek 6: Testovací obrázek „Lena“ zpracovaný filtrem Up

Obrázek 7: Testovací obrázek „Tcl/Tk“ zpracovaný filtrem Up

//-----------------------------------------------------------------------------
// Aplikace filtru Up na paletové obrázky či na grayscale obrázky
//-----------------------------------------------------------------------------
void applyFilterUp(pixmap *p1, pixmap *p2)
{
    int i, j;
    unsigned char up;
    for (j=0; j<p1->height; j++) {      // pro všechny řádky zdrojové pixmapy
        for (i=0; i<p1->width; i++) {   // pro všechny pixely na řádku
            up=getpixel(p1, i, j)-getpixel(p1, i, j-1); // provést filtraci
            putpixel(p2, i, j, up);     // zápis výsledku do cílové pixmapy
        }
    }
} 

6. Filtr číslo 3: Average

Filtr číslo 3 (Average) vznikl kombinací předchozích dvou typů filtrů. Už se nebere v úvahu barva pouze jednoho sousedního pixelu, ale hned pixelů dvou: horního a levého souseda. Hodnoty obou zmiňovaných sousedů se sečtou a vydělí dvěma, resp. při praktické implementaci se místo dělení pouze posunou doprava o jeden bit. Výsledkem jsou obrázky s ještě vyrovnanějším histogramem a teoreticky i vyšším komprimačním poměrem. Také můžeme vidět, že filtr nejhůře reaguje na hrany o úhlu 45°.

Obrázek 8: Testovací obrázek „Lena“ zpracovaný filtrem Average

Obrázek 9: Testovací obrázek „Tcl/Tk“ zpracovaný filtrem Average

//-----------------------------------------------------------------------------
// Aplikace filtru Average na paletové obrázky či na grayscale obrázky
//-----------------------------------------------------------------------------
void applyFilterAverage(pixmap *p1, pixmap *p2)
{
    int i, j;
    unsigned char average;
    for (j=0; j<p1->height; j++) {      // pro všechny řádky zdrojové pixmapy
        for (i=0; i<p1->width; i++) {   // pro všechny pixely na řádku
            average=getpixel(p1, i, j)-((getpixel(p1, i-1, j)+
                                        getpixel(p1, i, j-1))>>1);
            putpixel(p2, i, j, average);// zápis výsledku do cílové pixmapy
        }
    }
} 

7. Filtr číslo 4: Paeth

Posledním a současně i nejsložitějším typem filtru je filtr číslo 4 – Paethův filtr. Nejedná se o klasický konvoluční filtr, protože obsahuje prediktor, což je funkce, která na základě hodnot tří sousedních pixelů vybere ten, jehož barva je nejbližší pixelu zpracovávanému. Kupodivu se jedná o reverzibilní operaci, tj. stejný prediktor je možné použít i při rekonstrukci původních obrazových dat, což je jistě výhodné.

Teoreticky by se mělo jednat o filtr vytvářející nejvýhodnější podmínky pro komprimaci, ve skutečnosti to však není vždy pravda, protože se vlivem prediktoru (který pro komprimační program funguje náhodně) histogram sice upraví žádoucím způsobem, tj. zvýší se počet hodnot v okolí 0 a 255, ale tyto hodnoty jsou po obrázku rozprostřeny způsobem, který připomíná šum (a ten se velmi špatně komprimuje). Také doba komprimace je u tohoto typu filtru vyšší než u jeho kolegů, zejména kvůli tomu, že se nejedná o klasický konvoluční filtr, ale o filtr, při jehož implementaci je zapotřebí použít podmíněné skoky, u nichž se prakticky nedá předpovědět, zda se provedou či nikoli (to dnešní procesory nemají rády).

Obrázek 10: Testovací obrázek „Lena“ zpracovaný filtrem Paeth

Obrázek 11: Testovací obrázek „Tcl/Tk“ zpracovaný filtrem Paeth

Implementace Paethova filtru pro paletové a grayscale obrázky je ukázána na funkcích paethPredictor() a applyFilterPa­eth():

//-----------------------------------------------------------------------------
// Prediktor Paethova filtru
//-----------------------------------------------------------------------------
int paethPredictor(int a, int b, int c)
{
//  a: hodnota pixelu nalevo
//  b: hodnota pixelu na předchozím řádku
//  c: hodnota pixelu nalevo na předchozím řádku
    int p=a+b-c;              // prvotní odhad
    int pa=abs(p-a);          // vzdálenosti k a, b a c
    int pb=abs(p-b);
    int pc=abs(p-c);
    // vrátí se hodnota pixelu s nejbližší vzdáleností
    if ((pa<=pb) && (pa<=pc)) return a;
    else if (pb<=pc)          return b;
    else                      return c;
}



//-----------------------------------------------------------------------------
// Aplikace filtru Paeth na paletové obrázky či na grayscale obrázky
//-----------------------------------------------------------------------------
void applyFilterPaeth(pixmap *p1, pixmap *p2)
{
    int i, j;
    unsigned char paeth;
    for (j=0; j<p1->height; j++) {      // pro všechny řádky zdrojové pixmapy
        for (i=0; i<p1->width; i++) {   // pro všechny pixely na řádku
            paeth=getpixel(p1, i, j)-paethPredictor(getpixel(p1, i-1, j),
                                                    getpixel(p1, i, j-1),
                                                    getpixel(p1, i-1, j-1));
            putpixel(p2, i, j, paeth);  // zápis výsledku do cílové pixmapy
        }
    }
} 

8. Obsah dalšího pokračování tohoto seriálu

V následujícím pokračování si popíšeme význam doplňujících chunků. Konkrétně se bude jednat o chunky gAMA, cHRM, sRGB, iCCP, tEXT, zTXT, iTXT, bKGD, pHYs, sBIT, sPLT, hIST a tIME. Také si ukážeme praktickou implementaci cyklického kódu (CRC) u PNG.