+--------------------------------+
| Vytváření paletovaného obrázku |
+--------------------------------+
V předchozí kapitole jsme si ukázali, jak nalézt omezenou
paletu barev tak, aby co nejlépe charakterizovala vstupní obrázek.
Nyní musíme pomocí nalezené palety vytvořit nový paletovaný obraz, co
nejvíce podobný původnímu. Budeme tedy opět procházet pixel po
pixelu celým obrázkem, číst barvy v rozlišení True Color a nahrazovat
je vhodnou barvou z palety. Do nového obrázku se totiž, jak již bylo
uvedeno dříve, neukládají přímo údaje o barvách, ale jen indexy barev
v paletě.
Opět existuje několik různých metod, lišících se složitostí,
paměťovou a časovou náročností i kvalitou výsledných obrázků. Jsou
založeny na několika základních myšlenkách.
• Zaokrouhlování k nejbližší barvě (color rounding).
• Náhodné rozptylování (random dithering).
• Maticové rozptylování (matrix dithering).
• Distribuce chyby (error distribution).
Všechny uvedené metody spojuje problém hledání nejbližší barvy
z palety k barvě z původního obrázku (nearest neighbor searching).
Pokud jde o adaptivně vytvořenou paletu, musíme většinou pro zadaný
RGB vektor prohledat celou vytvořenou paletu a pro každou položku
vyčíslit vzdálenost dané RGB barvy od barvy v paletě. Výsledkem je
potom index do vytvořené palety barev. Jelikož tuto operaci musíme
provést pro každý pixel obrazu alespoň jednou, je nutno tento proces
co nejvíce urychlit.
Než si ukážeme, jak hledání nejbližšího souseda urychlit, je
nutno říci, že obvykle se vzdálenost dvou barev měří jako
Euklidovská vzdálenost (nebo její kvadrát) v RGB krychli, nebo jako
maximum z absolutních hodnot rozdílů jednotlivých složek RGB
vektoru [14] [2]. Tato metrika je však, jak již bylo uvedeno, chybná,
vzhledem k nelineárnímu zobrazování a vnímání barev lidským okem.
Proto byly navrženy specielní barevné modely, které umožňují měřit co
nejpřesněji vzdálenost dvou barev. Jedná se o barevné modely L-a-b a
L-u-v. Korektní porovnávání vzdálenosti barev by tedy mělo být
prováděno právě v jednom z těchto modelů. Převod z RGB prostoru do
L-u-v lze nalézt například v [4]. K převodu je nutno nejprve provést
převod z RGB do prostoru XYZ [13] [14] [4], kde musíme znát smluvní
bílou barvu (white balance). Porovnání kvality obrazů, uvedené v
[14], ukazuje, že i přes nutnost použití neceločíselné aritmetiky,
která značně zpomaluje výpočet nejbližší barvy, se převod vyplatí.
Jednoduchou metodou urychlení hledání nejbližšího souseda je
použití tzv. localy sorted search [1][2]. Nejprve RGB krychli
rozdělíme na pravidelné díly v každé ose, podobně jako pro uniformní
paletu. Pro každý vzniklý RGB voxel (objemový element, kvádr) je pak
vytvořen spojový seznam všech barev, které mohou být nejbližšími
sousedy dané buňky. Tento seznam obsahuje jak index do palety barev,
tak vzdálenost od nejbližší barvy v buňce. Tento seznam se setřídí
vzhledem ke středu každého voxelu. Při hledání nejbližší barvy
nejprve nalezneme (zaokrouhlením) příslušný voxel a následně
prohledáme sekvenčně tento seznam barev.
Jinou možností urychlení je použití tzv. k-d tree reprezentace
barev [2], což je skupina stromových datových struktur do kterých
spadá například binární strom a octree (oktanový strom).
Reprezentujeme tedy všechny barvy palety například pomocí binárního
stromu BSP tree (Binary Space Partitioning Tree, [10]) a pro
vyhledání nejbližší barvy v paletě použijeme algoritmu binárního
půlení. Vytváření BSP stromu je známé z prostorové počítačové grafiky
a je založeno na geometrické reprezentaci RGB vektorů. Jinou možností
je využití přímo octree, již zmiňovaného v dřívějších kapitolách. Ke
každému reprezentantu si předem vypočteme nejbližší barvu v paletě a
vyhledávání nejbližšího souseda proběhne v konstantním čase. Tato
metoda je velice účinná, pro menší obrázky je však náročnost
předzpracování a hloubka stromu nezanedbatelná, proto se celková
náročnost prohledávání v některých případech může blížit původní
lineární složitosti.
Z uvedených metod hledání nejbližšího souseda je neúčinnější
octree s tím, že informaci o nejbližší barvě negenerujeme předem,
ale až v průběhu dotazů na nejbližší barvu. Pokud barva ještě není v
octree, nebo nemá určenou nejbližší barvu z palety, vyhledá se a
uloží, jinak se použije již vypočtená hodnota. Nevýhodou je jen
možnost potenciálně velké paměťové náročnosti.
V případě šedotónových obrazů je jednoznačným řešením tabulka,
obsahující 256 položek, stejně jako možných odstínů šedi.
Pokud umíme nalézt dostatečně efektivně nejbližší barvu v
paletě, můžeme této funkce použít pro nejjednodušší metodu vytváření
paletovaného obrázku, tj. zaokrouhlení na nejbližší barvu. Pro každý
bod původního obrazu nalezneme nejbližší barvu z palety a tu vložíme
na stejné místo do nového indexovaného obrazu. Tato metoda je velmi
jednoduchá a rychlá, ale v novém obraze jsou patrné přechody barev a
některé původní barvy mohou být zkreslené, protože se pravidelně
zaokrouhlují k nějaké dosti vzdálené barvě z palety.
Neprávem méně používanou metodou je náhodné rozptylování barev.
Do původního obrázku se vlastně přidává náhodný signál daného
rozložení v každé RGB složce barvy. Algoritmus tedy ke každé složce
barvy přičte náhodnou hodnotu a teprve potom provede vyhledání
nejbližší barvy z palety. Výsledný obraz je mírně zašumělý, ale na
přechodu barevných odstínů se náhodně střídá několik barev z palety a
nevzniknou tak rušivé přechody. Taktéž v případě, že některá ze
vstupních barev není v paletě, vybírají se náhodně nejbližší barvy z
palety a výsledek se blíží původní barvě. Tato metoda není příliš
populární, protože se pro generování šumu často chybně používá
standardního náhodného generátoru. Pokud však šum generujeme v
závislosti na odchylce barvy z palety a původní barvy, může být
výsledek překvapivě dobrý. Velmi zajímavé výsledky jsou uvedeny v [3]
[12] [5] [15]. Náhodný šum je zde navíc generován v závislosti na
poloze pixelu v obraze a proto je rozptýlení barev v obraze
dostatečně rovnoměrné. Ke generování takového šumu se používá
algoritmu, popsaného například v [14], který vytváří tzv. Poissonův
disk. Není tedy generován pravidelný vzor, který se projevuje na
plochách s konstantní barvou, ale přitom dochází k rozptýlení barev
do okolí.
Velmi často používanou metodou je maticové rozptylování barev.
Této metody je však možno použít jen pro palety s definovaným
uspořádáním, tedy pro uniformní palety a modifikovanou metodu
akumulativního histogramu, protože zpracovává každou z barevných
složek zvlášť a navíc potřebuje informaci o sousedech.
Maticové rozptylování bylo původně navrženo pro případ
zvětšování obrázku. Místo jednoho pixelu v původním obrázku vkládá
jakýsi maxipixel 4x4 nebo 8x8 bodů a rozměry obrázku se proto
čtyřikrát nebo osmkrát zvětšují. Využívá přitom řady matic stejné
velikosti (viz např. [9][11][3]), tedy 4x4 nebo 8x8, které obsahují
pouze hodnoty 0 a 1. Podle velikosti chyby, která by vznikla prostým
zaokrouhlením do palety, se vybere jedna z matic. Ta potom řídí, na
kterých místech maxipixelu se použije jasnějšího a kde tmavšího
odstínu složky barvy. Pokud je v matici na odpovídajícím místě
hodnota 1, použije se světlejšího odstínu, jinak odstínu tmavšího. Po
vyhodnocení všech tří barevných složek se tyto spojí do jednoho
bajtu, zastupujícího barvu z palety. V našem případě však ke zvětšení
rozměrů obrázku nedochází. Z jednoho pixelu původního obrázku tedy
vznikne opět jen jeden pixel. Která konkrétní hodnota z matice se
použije pak neurčuje poloha v maxipixelu, jako v předchozím případě,
ale nejnižší bity souřadnic pixelu v obrázku. Implementace lze nalézt
například v [3][20][4][5][19][9].
Algoritmus není závislý na pořadí zpracování, je proto hojně
používán v hardwarových grafických akcelerátorech a stal se
součástí téměř každého grafického programu. Hlavními nevýhodami je
viditelnost generovaných pravidelných vzorů ve výsledném obraze
[5][7][4] a obtížně zajistitelné uspořádání palety při použití
adaptivních metod tvorby palety.
Nevýhody maticového rozptylování částečně odstraňuje metoda
nazývaná distribuce chyby. Algoritmus zpracovává pixely po řádcích,
pro právě zpracovávanou barvu původního obrazu nalezne odpovídající
nejbližší barvu z palety a odečtením barevných složek získá chybu
kvantování. Tuto chybu rozdělí do svého okolí. Přitom využívá váhové
matice, která určuje, jak velká část chyby připadne jednotlivým
sousedům. Protože je nutno modifikovat barvy sousedů chybou ještě
před jejich zpracováním, nelze distribuovat chybu všem sousedům.
Předpokládá se proto většinou zpracování shora dolů a zleva doprava a
chyba se distribuuje jen doprava a dolů. Pokud je chyba dostatečně
velká, zaokrouhlí se sousední pixely jinak, než právě zpracovávaný a
vznikne opět efekt střídání barev. Vzhledem k řádkovému zpracování
obrázku je generován charakteristický vzor, který je jiného
charakteru než u maticového rozptylování. Tento jev lze částečně
potlačit změnou směru zpracování jednotlivých řádků, nebo lépe
použitím zig-zag cest nebo fraktálních vyplňovacích křivek
[15][16][9].
Volbou váhové matice můžeme řídit kvalitu rozptylování. Různé
váhové matice můžeme najít například v [9][3][4]. Nejpoužívanější
váhové matice, nazvané podle svých autorů, jsou uvedeny v tabulce.
Matice se liší svou velikostí (3*3 nebo 5*5) a vahami. Křížkem je
označen zpracovávaný bod. Matice obsahující mocniny dvou umožňují
použít při výpočtech posuvů a urychlit tak zpracování.
+ +
1 | 0 0 0 |
-- | 0 x 7 |
16 | 3 5 1 |
+ +
Floyd & Steinberg
+ +
1 | 0 0 0 |
- | 0 x 2 |
4 | 1 1 0 |
+ +
Frankie & Sierra
+ +
| 0 0 0 0 0 |
1 | 0 0 0 0 0 |
-- | 0 0 x 8 4 |
42 | 2 4 8 4 2 |
| 1 2 4 2 1 |
+ +
Stucki
+ +
| 0 0 0 0 0 |
1 | 0 0 0 0 0 |
-- | 0 0 x 7 5 |
48 | 3 5 7 5 3 |
| 1 3 5 3 1 |
+ +
Jarvis, Judice and Ninke
Metoda distribuce chyby se nejlépe hodí k rozptylování s
adaptivně vytvořenou paletou barev, protože pro svou činnost
nevyžaduje uspořádání barev v paletě. Navíc má tato metoda pro
některé váhové matice zaostřovací účinek.
výheň