čtvrtek 21. listopadu 2013

Komprese metodou RLE

Run-length encoding je jednoduchá metoda bezztrátové komprese. V článku vysvětlím, v čem spočívá, jak se s ní pracuje a ukážu příklad na obrázku BMP.

Motivace

Mějme řetězec 20-ti znaků
AAABBCCCCCCCAAAAAAAA
Dokážeme zmenšit počet znaků v řetězci, aniž bychom ztratili byť jen jedinou hodnotu, kterou obsahuje?

Mějme obrázek


Je nutné uložit jej pixelu po pixelu, aby pak mohl být ve stejné formě zobrazen?

Algoritmus RLE

Řetězec výše můžeme přečíst jako "á á á bé bé cé cé cé...", nebo možná přirozeněji "tři á, dvě bé, sedm cé a osm á". Stejně tak můžeme obrázek přečíst jako "tři černé, čtyři bílé, čtyři černé, pět bílých a čtyři černé". A to je ono - jednoduše nahradíme podřetězce stejných znaků jejich délkou a samotným znakem. Řetězec výše tedy bude po zakódování vypadat
3A2B7C8A
Vidíme, že z původních 20-ti znaků dostáváme 8, aniž bychom přišli o originál. Jsme totiž schopni z našich 8-mi znaků přesně rekonstruovat vstupní řetězec o délce 20-ti. Algoritmus existuje ve více variantách a úpravách, které z části řeší nevhodná vstupní data. Používají se speciální symboly, které například detekují opakování celých skupin, mění směr průchodu, nebo značí nezakódovanou sekvenci. Poslední případ můžeme demonstrovat na řetězci
AAABCDEFGHIII
který by po zakódování neoptimalizovaným způsobem vypadal
3A1B1C1D1E1F1G1H3I
Docílili jsme záporné komprese, kdy z původních 13-ti znaků dostáváme 18. Zkusme zavést speciální symbol "#", který použijeme spolu s číslem reprezentující počet nezakódovaných znaků. Dostaneme
3A7#BCDEFGH3I
tedy 13 znaků po zakódování.

Implementace

opakovani = 1;
vystup = "";

for(pro vsechny znaky - 1) {
   if (znak == nasledujici znak) {
      opakovani += 1;
   } else {
      vystup += opakovani + znak;
   }
}

if (predposledni znak != posledni znak) {
   vystup += "1" + posledni znak;
}
Cyklus projde vstupní řetězec znak po znaku a ve chvíli kdy se následující znak nerovná zpracovávanému přidá k výstupnímu řetězci informaci o počtu jeho opakování. Na konci máme v proměnné vystup řetězec s výsledným tvarem vstupu po kompresi.

Příklad s BMP

Obrázek použitý nahoře jako příklad jsem v Gimpu uložil jako BMP a poté otevřel v HEX módu v PSPadu. Jak vidíme, zapsal se nekomprimovaně. Byty 00 jsou pixely černé barvy a FF barvy bílé.


Pokud v Gimpu zaškrtneme při ukládání možnost "Run-Length Encoded" a podíváme se do souboru, uvidíme zkomprimovanou verzi.


Literatura a odkazy

http://www.fileformat.info/format/bmp/egff.htm
http://www.root.cz/clanky/pcx-prakticky-implementace-komprimace-rle

Diskrétní dvourozměrná konvoluce

Konvoluce je operátor, který ze dvou funkcí vytvoří funkci novou. Pro dvourozměrný případ ve spojitém prostoru vypadá následovně \[ (f*g)(x, y) = \int_{u=-\infty}^{\infty} \int_{v=-\infty}^{\infty} f(x-u, y-v) g(u, v) dudv \] V článku se ovšem budeme zabývat diskrétním tvarem, který použijeme na zpracování rastrového obrazu a který nám ve vztahu výše umožní nahradit integrály sumami.

Použití

Obrázky níže ukazují možné aplikace.

a) b) c)
d) e) f)
a) vstupní obrázek; b) rozostření; b) zaostření; c) detekce hran; d) detekce vertikálních hran; e) detekce horizontálních hran

Jak vidíme, dokážeme tímtéž algoritmem dosáhnout velmi odlišných výstupů. Každý pak může být zajímavý ať už vizuálním dojmem, nebo z hlediska další aplikace.

Algoritmus

Mějme vstupní obrázek a jeden další velikosti $n*n$. Tomu budeme říkat maska a ono $n$ bude nejčastěji 3. Na obrázku můžete vidět graficky, co potřebujeme pro použití konvoluce.

\[\left( \begin{array}{ccc} 76 & 107 & 45 \\ 168 & 150 & 224 \\ 104 & 145 & 114 \end{array} \right)\]
a) b)
\[\left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right)\]
c)
a) vstupní obrázek; b) intenzity pixelů vstupního obrázku; b) maska

Masku položíme na obrázek a bod který leží pod jejím středem, budeme počítat. Jednoduše vynásobíme hodnotu jasu daného pixelu hodnotou masky, která mu svým překrytím odpovídá. Všechny takové hodnoty (pro masku $3*3$ jich bude 9) sečteme a dostaneme novou hodnotu pro náš počítaný pixel. Poté okno přesuneme na další bod a počítáme dále. Mějme na paměti, že pro obraz s více barevnými kanály než jedním, počítáme konvoluci pro každý kanál zvlášť.

Matematicky

Popišme si algoritmus matematicky. Následující vztah definuje diskrétní dvourozměrnou konvoluci \[ I(x,y)=\sum_{i=-k}^{k}\sum_{j=-k}^{k} f(x-i,y-j)\cdot g(i,j) \] kde $I(x,y)$ značí intenzitu výsledného pixelu na pozici $[x,y]$, $f(x,y)$ je intenzita vstupního obrázku na pozici $[x,y]$ a $h(i,j)$ intenzita bodu v masce na pozici $[i,j]$.

Zkusme si spočítat příklad z obrázku výše. Počítáme bod $[1,1]$ (tedy ten uprostřed). Masku máme velkou 3*3 pixely, takže její indexy budou v každém směru $-1,0,1$ a $k=1$. Ve výrazu máme dvojitou sumu, ze které vidíme, že budeme sčítat 9 čísel. Zapišme si první část, kdy vypočítáme první z řady a to pixel vpravo dole. Indexy $i$ a $j$ se tedy pro první průchod budou rovnat \[ i=-k=-1 \] \[ j=-k=-1 \] po dosazení do vzorce dostaneme při středu $[1,1]$ pro políčko vpravo dole hodnotu \[ \begin{array}{lcl} I_{vd}(1,1)&=&f(1-(-1),1-(-1))\cdot h(-1,-1) \\ &=&f(2,2)\cdot h(-1,-1) \\ &=&114\cdot 1 \\ &=&114 \end{array} \]

Jak můžete vidět, pro políčko vpravo dole v původním obrázku používáme políčko vlevo nahoře v masce. Mějte na paměti, že se maska při použití otočí horizontálně a vertikálně!

Po dokončení výpočtu dostaneme hodnotu prostředního pixelu v rámci konvoluční masky. \[ I(1, 1)=76+107+45+168+150+224+104+145+114=1133 \] Vypočítaná hodnota značně přesahuje maximální intenzitu barevného kanálu, což nedokážeme vykreslit. Nabízí se řešení nahradit vyšší čísla maximální hodnotou 255. V tomto případě není řešení vhodné.

Každý pixel ve vstupním obrázku je ohodnocen hodnotou v masce, která mu přiřadí jeho důležitost v daném okolí. Pro příklad uvažujme obrázek $300*200$ v šedé barvě, kde má každý pixel jas 125. Po aplikaci masky uvedené výše by každý pixel obrazu nabyl hodnoty $9*125=1125$. Kdybychom se rozhodli velké hodnoty jednoduše nahradit nejvyšší možnou intenzitou, což je 255, dostali bychom bílý obdelník. Jak vidíme, výsledek rozostření šedého obrázku by pravděpodobně neměl být obrázek bílý. Zkusme vyzkoušet, co se stane když se zaměříme pouze na poměr hodnot v masce a na jejich součet. Nechejme všechny hodnoty stejné a trvejme na podmínce jejich součtu, který musí být roven jedné. Dostaneme tedy pole $3*3$ kde v každé buňce bude $1/9$. Po aplikaci této masky na náš šedý obrázek, dostaneme zpět tentýž.

Přidáme tedy k výpočtu intenzity jeden krok, kdy výslednou hodnotu vydělíme součtem hodnot v masce. Tomuto procesu se říká normalizace a budeme ho provádět při konvoluci vždy, když bude součet hodnot v masce větší než jedna.

Implementace

Schématicky může implementace vypadat takto.
vahy = 0;

for(i = -K; i <= K; i++) {
   for(j = -K; j <= K; j++) {
      vahy += maska[1+i][1+j];
   }
}      

if (vahy < 1) vahy = 1;

for(radek = 0; radek < VYSKA; radek++) {
   for(sloupec = 0; sloupec < SIRKA; sloupec++) {
      soucet = 0;
      
      for(i = -K; i <= K; i++) {
         for(j = -K; j <= K; j++) {
            intenzita = vstupni(radek + i, sloupec + j);
            soucet += intenzita * maska[1+i][1+j];
         }
      }
      
      vystupni(radek, sloupec) = round(soucet/vahy);
   }
}
V principu potřebujeme dostat součet všech násobků pixelů v masce maska spolu s odpovídajícími pixely ve vstupním obrázku vstupni. Vypočítanou hodnotu poté vydělíme součtem hodnot v masce (normalizace). Všimněte si, že nová hodnota je vložena do nového obrázku vystupni. Toto je velice důležité! Kdyby byla vložena do vstupni , každá další hodnota by v sobě zahrnovala výpočet s už zpracovaným pixelem. Počítáme tedy s hodnotami z původního obrázku a nové vkládáme do jiného.

Různé masky

Na závěr článku se vraťme k obrázkům v první podkapitole a ukažme, jaké masky byly použity pro jejich vytvoření.

\[\left( \begin{array}{ccc} 1 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 1 \end{array} \right)\] Gaussův filtr
\[\left( \begin{array}{ccc} 0 & -1 & 0 \\ -1 & 5 & -1 \\ 0 & -1 & 0 \end{array} \right)\] zvýraznění hran
\[\left( \begin{array}{ccc} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{array} \right)\] operátor Laplace
\[\left( \begin{array}{ccc} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{array} \right)\] Sobelův operátor (svislé hrany)
\[\left( \begin{array}{ccc} -1 & -2 & -1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{array} \right)\] Sobelův operátor (vodorovné hrany)

Poznámka
Na spodní tři obrázky byla použitá dodatečná úprava. K intenzitě každého pixelu byla v každém kanálu přidána hodnota 128.

Literatura a odkazy

HLAVÁČ, V.; SEDLÁČEK, M. Zpracování signálu a obrazu. Vydavatelství CVUT, 2005.
KOLCUN, A. Základy počítačovej grafiky. Učební texty, Ostrava 2006.
ŽÁRA, J.; SOCHOR, J.; BENEŠ, B.; FELKEL, P. Moderní počítačová grafika. Computerpress, Brno 2004.

http://cs.wikipedia.org/wiki/Konvoluce
http://bruxy.regnet.cz/fel/36ACS/konvoluce.pdf
http://www.songho.ca/dsp/convolution/convolution2d_example.html

http://homepages.inf.ed.ac.uk/rbf/HIPR2/convolutiondemo.htm - applet

Grafická hádanka

Pojďme vyzkoušet, co se stane se dvěma totožnými obrázky po aplikaci několika aritmetických operací.

=

Řekněme, že chceme oba trochu prosvětlit. Vynásobme tedy každý z nich sebou samým.

$\cdot$
=
$\cdot$

Vstupní obrázek vypadá z hlediska čísel takto
\[\left( \begin{array}{cccccccccc} 15 & 15 & 15 & 0 & 0 & 0 & 0 & 15 & 15 & 15 \\ 15 & 15 & 0 & 15 & 15 & 15 & 15 & 0 & 15 & 15 \\ 15 & 0 & 15 & 15 & 15 & 15 & 15 & 15 & 0 & 15 \\ 0 & 15 & 0 & 0 & 15 & 15 & 0 & 0 & 15 & 0 \\ 0 & 15 & 0 & 0 & 15 & 15 & 0 & 0 & 15 & 0 \\ 0 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 0 \\ 0 & 15 & 15 & 0 & 0 & 0 & 0 & 15 & 15 & 0 \\ 15 & 0 & 15 & 15 & 15 & 15 & 15 & 15 & 0 & 15 \\ 15 & 15 & 0 & 15 & 15 & 15 & 15 & 0 & 15 & 15 \\ 15 & 15 & 15 & 0 & 0 & 0 & 0 & 15 & 15 & 15 \end{array} \right)\]
Pokud spolu vynásobím nuly, dostanu novou hodnotu pixelu rovnu 0. Pokud vynásobím patnáctky, dostanu 225.

=

Nový obrázek vypadá číselně takto
\[\left( \begin{array}{cccccccccc} 225 & 225 & 225 & 0 & 0 & 0 & 0 & 225 & 225 & 225 \\ 225 & 225 & 0 & 225 & 225 & 225 & 225 & 0 & 225 & 225 \\ 225 & 0 & 225 & 225 & 225 & 225 & 225 & 225 & 0 & 225 \\ 0 & 225 & 0 & 0 & 225 & 225 & 0 & 0 & 225 & 0 \\ 0 & 225 & 0 & 0 & 225 & 225 & 0 & 0 & 225 & 0 \\ 0 & 225 & 225 & 225 & 225 & 225 & 225 & 225 & 225 & 0 \\ 0 & 225 & 225 & 0 & 0 & 0 & 0 & 225 & 225 & 0 \\ 225 & 0 & 225 & 225 & 225 & 225 & 225 & 225 & 0 & 225 \\ 225 & 225 & 0 & 225 & 225 & 225 & 225 & 0 & 225 & 225 \\ 225 & 225 & 225 & 0 & 0 & 0 & 0 & 225 & 225 & 225 \end{array} \right)\]
Teď ho na každé straně odečtěme.

-
=
-

Dostaneme nuly, což odpovídá černým plochám.

Matematicky můžeme říct, že pokud je náš původní obrázek $A$, pak nový obrázek bude $A\cdot A$ tedy $A^2$. Znázorněný rozdíl tedy můžeme přepsat na \[ A^2-A^2=A^2-A^2 \] Aplikujme jeden ze základních vzorců \[ A^2-B^2=(A-B)(A+B) \] a pravidlo vytýkání, pro dosažení výrazu \[ A(A-A)=(A-A)(A+A) \] Vraťme se k obrázkům. Levá strana bude vypadat

$\cdot$ (
-
)

a pravá strana

(
-
) $\cdot$ (
+
)

Dostaneme po úpravách vlevo i vpravo černou plochu, což odpovídá. Protože máme na obou stranách stejné výrazy, vykraťme je.

=
+

Sečteme členy na pravé straně a máme výsledek.

=

Na první pohled všechno sedí. Máme dva totožné obrázky, které se rovnají tak jako na začátku. Jak by taky ne, dělali jsme na obou stranách ty samé úpravy.

Ovšem pozor! :)

Podívejme se pořádně na výsledný obrázek vpravo. I když vypadá stejně, součet na něm zanechal stopy. V číslech máme
\[\left( \begin{array}{cccccccccc} 30 & 30 & 30 & 0 & 0 & 0 & 0 & 30 & 30 & 30 \\ 30 & 30 & 0 & 30 & 30 & 30 & 30 & 0 & 30 & 30 \\ 30 & 0 & 30 & 30 & 30 & 30 & 30 & 30 & 0 & 30 \\ 0 & 30 & 0 & 0 & 30 & 30 & 0 & 0 & 30 & 0 \\ 0 & 30 & 0 & 0 & 30 & 30 & 0 & 0 & 30 & 0 \\ 0 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 30 & 0 \\ 0 & 30 & 30 & 0 & 0 & 0 & 0 & 30 & 30 & 0 \\ 30 & 0 & 30 & 30 & 30 & 30 & 30 & 30 & 0 & 30 \\ 30 & 30 & 0 & 30 & 30 & 30 & 30 & 0 & 30 & 30 \\ 30 & 30 & 30 & 0 & 0 & 0 & 0 & 30 & 30 & 30 \end{array} \right)\]
Co se stalo a jak je to možné?

Otázka

Kde máme ve výpočtu chybu? Pokud tam chyba není, proč se výsledný obrázek liší od původního?

Animal morph v Gimpu

Určitě už jste viděli obrázky několika zvířat spojených v jedno.


Udělejme si také takové s použitím Gimpu.

Začínáme

Použijeme tyto obrázky

a Gimp ve verzi 2.6.11 (i v jiných verzích by se postup nemusel výrazně lišit). Našim cílem bude dosáhnout spojení obou zvířat na použitých obrázcích.


Přípravy

V prvním kroku připravíme oba obrázky.
  • zkopírujeme do schránky obrázek tučňáka a vložíme do Gimpu
    • Upravit -> Vložit jako -> Nový obrázek
  • zkopírujeme do schránky obrázek králíka a vložíme jako novou vrstvu
    • Upravit -> Vložit jako -> Nová vrstva
Ujistěte se, že máte viditelný dialog "Vrstvy" - Okno -> Připojitelné dialogy -> Vrstvy. Výřez vaši pracovní plochy by teď měl vypadat nějak takto


Teď potřebujeme oříznout hlavu našeho králíka. Můžeme použít nástroj "Volný výběr" (klávesová zkratka F), nebo jako já "Výběr pomocí inteligentního hledání hran" (I). Až budete s výběrem spokojeni invertujte jej Vybrat -> Invertovat (Ctrl + I) a stiskněte klávesu Delete.


V této chvíli musíme napasovat hlavu králíka na tělo tučňáka. Když se o to pokusíme, zjistíme, že nám uši zasahují mimo obrázek. Skryjeme tedy vrstvu s králíkem (ikonka oka) a vybereme vrstvu s tučňákem.
  • změníme velikost plátna
    • Obrázek -> Velikost plátna... -> (klikněte na ikonku řetězu) -> Výška = 554
  • vytvoříme místo nad tučňákem
    • (v náhledovém okně chytíme obrázek a potáhneme tak dolů jak to jen půjde) -> Změnit velikost
  • zaplníme místo nebem
    • Vybereme klonovací razítko (C) a vyplníme novou plochu vzorem nad tučňákovou hlavou
Výsledek by měl vypadat nějak takto


Úprava barev a sloučení

Pomocí nástrojů "Přesun" (M) a "Škálování" (Shift + T) posuneme hlavu králíka kam patří a změníme její velikost, aby zapadla.


V této chvíli je třeba doladit barvy. Otevřeme si dialog Barvy -> Odstín-sytost a úpravou hodnot Odstín, Světlost, Sytost docílíme barevné shody. Nastavování je otázka cviku a ze začátku je třeba vyzkoušet, co bude vypadat nejlépe. Já vybral 180, 0, -84. Dále se mi nezdála nepravidelnost kolem uší a pár detailů, které jsem upravil klonovacím razítkem a gumou. Výsledek vypadá takto


Dále jsem ručně vybral okraje a rozmazal je přes Filtry -> Rozostření -> Gaussovské rozostření... a poté roztřepil, abych jim dodal podobný feeling jako má tělo tučňáka Filtry -> Šum -> Roztřepení....


Sloučíme obě vrstvy (pravým tlačítkem na vrstvu s hlavou králíka) -> Sloučit dolů a přistoupíme k závěrečným úpravám.

Finální úpravy

Musíme hladce napojit hlavu na tělo. Pro tento účel jsem vybral nástroj "Léčení" (H) se štětcem Circle fuzzy a krytím 70. Jako vzor (Ctrl + levý klik) jsem vybral opeření pod krkem a několikrát poklepal na spojnici hlavy a těla, než jsem byl spokojen s výsledkem.


Ještě pár úprav kontrastu, jasu, doladění několika míst "Léčením" a máme výsledek


Poznámka na závěr
Tučňákokrálíka nahoře jsem vytvořil už před nějakou dobou. Napsat tutoriál mě napadlo později kdy jsem neměl k dispozici jednotlivé kroky, takže jsem vše udělal znovu. To je důvod, proč se liší výsledný obrázek dole od obrázku nahoře. Do článku je dávám oba, aby šlo vidět, jak v podstatě stejným postupem můžeme dostat různé výsledky. Zároveň je třeba upozornit, že nejde o profesionální, ani jediný způsob, ale pouze o demonstraci jedné jednoduché cesty jak animal morphu dosáhnout.

Zdroje a literatura

http://www.zonnigforum.nl - obrázky na začátku
http://www.instructables.com/id/How-to-morph-animals-using-GIMP-free-software - článek v angličtině na stejné téma