+-------------------------------------------------+
| Adaptivní metody vytváření palety (heuristické) |
+-------------------------------------------------+
Adaptivní metody kvantování využívají informace z obrazu a
vytvářejí paletu přímo na míru. Prakticky všechny adaptivní metody
pracují s výčtem všech barev a jejich histogramem. Množinu
reprezentantů barev obrazu tvoří všechny RGB vektory, které se ve
vstupním obraze objevují alespoň jednou. Při vytváření takové tabulky
reprezentantů je vhodné současně vytvářet histogram, tj. sčítat
četnost výskytů každé z barev.
Výpočet histogramu a reprezentantů v šedotónových obrazech je
jednoduchý, jednoprůchodový proces s konstantní složitostí [22]. V
případě barev v RGB prostoru je problém složitější. Zdánlivě
nejjednodušším řešením je vytvoření velkého statického pole s
konstantní složitostí přístupu k položkám. V rozlišení True Color
však toto pole musí obsahovat 256^3, tedy přibližně 16 milionů barev,
a to je i v dnešní době ještě poměrně mnoho. Podobným řešením s
podobnými problémy je lineární spojový seznam s lineární složitostí
přístupu. Proto se většinou uvažuje jen vyšších 5 bitů každé složky
barvy a předpokládá se, že by tyto barvy stejně byly zaokrouhleny do
jediné položky ve výsledné paletě [1].
Jiným přístupem je uchovávat informace jen o těch barvách,
které se v obrázku vyskytují alespoň jednou. V praxi se totiž
ukazuje, že pokud není obrázek specielně vygenerován, zdaleka
neobsahuje všechny barvy. Z barev, které jsou opravdu v obrázku
obsaženy je možno vytvořit strukturu octree [8][21], známou spíše z
prostorové počítačové grafiky.
Octree je strom, kde každý uzel má maximálně 8 synů. Kořen
potom reprezentuje celý RGB prostor, jeho synové dělí tento prostor
na 8 podkrychlí s poloviční velikostí hrany a toto dělení dále
pokračuje až do hloubky 8. V listech jsou již uloženy informace o
počtech výskytů jednotlivých barev. Na počátku generování histogramu
existuje jen kořen a během procházení obrázku přibývají podle potřeby
synové a listy. Přístupová doba k položkám octree je konstantní (s
koeficientem 8) a paměťové nároky jsou přijatelné, protože většina
uzlů v octree je prázdná. Způsob uchování barev v octree je
ilustrován na obrázku .
Nejjednodušší metoda adaptivního kvantování je nazývána
popularity algorithm [1][2]. Vybírá jednoduše 256 nejčastěji se
vyskytujících barev a předpokládá, že málo zastoupené barvy v obrázku
není třeba uvažovat a můžeme je nahradit nejbližší barvou z nové
palety. Setřídíme tedy sestupně histogram podle četnosti a paletu pak
tvoří jen prvních N barev (N je počet barev v paletě, většinou v
rozsahu 16 - 256). Tento algoritmus v kombinaci se snížením barevné
hloubky (předkvantování) histogramu na 5 nebo 6 bitů může docela
dobře fungovat [18], pro zašumělé nebo nekontrastní obrázky má však
velmi špatné výsledky [1]. Pokud jsou v obraze objekty a pozadí
plynule mění barvu, je většina barev spotřebována na pozadí, které má
vysokou četnost výskytu.
Další metoda je nazývána metoda akumulativního histogramu [20].
Snaží se vytvářet skupiny z barev, které mají zhruba stejný počet
výskytů a dohromady zastupují přibližně 1/N pixelů v obrázku.
Pracujeme opět nad sestupně setříděným histogramem RGB vektorů,
který se snažíme adaptivně rozdělit na N dílů tak, aby byl součet
četností v každém z dílů shodný. Procházíme tedy histogram od
nejčetnějších barev a sčítáme počty výskytů. Jestliže překročíme
hodnotu 1/N počtu pixelů v obrázku, skupina získala dostatek
potenciálních zájemců o tuto barvu a provedeme dělení. Barvy ve
skupině sloučíme a tím získáme jednu z položek v paletě. Barvy
slučujeme obyčejným aritmetickým průměrem nebo váženým průměrem dle
jejich četností. Tento postup opakujeme až do konce histogramu.
Proces slučování je kritickým bodem metody. Skutečnost, že
barvy mají podobnou četnost nemusí znamenat, že jsou si barevně
blízké. Tato metoda má podobné vlastnosti jako popularity algoritmus
a často zkresluje původní barvy. Má uspokojivé výsledky pro obrazy s
menším počtem kontrastních barev.
Myšlenka předchozího algoritmu byla úspěšně převzata metodou
uvedenou v [8]. Uvedený proces neprovádíme pro globální histogram
barev, ale pro každou z os RGB krychle zvlášť a dělíme osy na
nestejné úseky. Jde tedy o adaptivní, ale přesto ortogonální dělení
RGB krychle, podobně jako u uniformní palety.
Vytvoříme tedy nejprve histogramy barev pro jednotlivé složky
R, G a B. Pak opět vypočítáme hodnotu, po jejímž překročení dojde k
dělení, ale s tím, že dělíme ve třech složkách, tudíž musí být součin
počtu úseků jednotlivých os menší nebo roven N. Nyní pro každý
histogram provedeme dělení na skupiny jako v předchozí metodě a v
závěrečné fázi do palety uložíme všechny kombinace vypočtených hodnot
z jednotlivých os. Tato metoda má lepší výsledky než neadaptivní
dělení krychle, přitom zachovává některé výhody jako uspořádání a
znalost nejbližšího souseda. Přejímá samozřejmě i nevýhody, například
v možné redundanci barev.
Další metoda vytváření palety barev vychází přímo z octree
reprezentace histogramu a bývá označována octree quantization [8].
Tato metoda vychází z myšlenky, že barvy, které jsou v RGB krychli
blízko u sebe, jsou si podobné a je možno je sloučit. Algoritmus má
mnoho variant, jedna z nich nejprve vytvoří octree histogram pro celý
obrázek, což bylo popsáno výše. V dalším se využívá vlastnosti, že
každý rodič má maximálně 8 potomků. Všechny originální barvy jsou
uloženy v listech takového stromu, tedy v hloubce 8. Ve vyšších
vrstvách jsou uloženy uzly, které mohou být jakousi aproximací těchto
originálních barev, protože je vlastně na vyšší úrovni zastupují.
Postupně tedy redukujeme listy a pak i uzly stromu, přičemž barvy
vhodně slučujeme, například váženým průměrem dle četností. Postup
opakujeme tak dlouho, dokud celkový počet barev v octree nebude menší
nebo roven N.
Tento velice efektivní algoritmus má problémová místa ve volbě
uzlů vhodných pro redukci barev a v přílišné rychlosti redukce,
protože redukujeme až 8 barev najednou. Pro redukci barev jsou
například vhodné ty uzly, které obsahují barvy s nejmenší četností,
protože ty nebudou v obrázku tolik podstatné. Rychlost redukce barev
můžeme odstranit postupným slučováním pouze dvojic barev.
Octree algoritmus je hojně používaný [2][8] i pro svou malou
paměťovou náročnost. Jiná varianta totiž nevytváří předem octree
histogram pro celý obraz, ale zařazuje barvy postupně do stromu tak
dlouho, dokud jejich počet nepřesáhne stanovené M. Jakmile se načítá
M+1 barva, dochází k automatické redukci barev ve stromě. Tento
postup zaručuje, že v paměti je nejvýše M barev zároveň. Nevýhodou
tohoto postupu je závislost na pořadí příchozích barev, proto se
doporučuje jiné než sekvenční zpracovávání obrazu, například pomocí
fraktálních vyplňovacích křivek [16][9][15].
Nejrozšířenější metodou pro adaptivní vytváření palety je
algoritmus nazvaný median cut algorithm [1][2]. Tento algoritmus je
používán i ve shlukové analýze [23]. Snaží se najít a ohraničit v RGB
prostoru shluky podobných barev, které dostanou přidělenu jednu
položku v paletě.
Nejprve vytvoříme opsaný kvádr (bounding box) kolem všech bodů
(reprezentantů) v RGB krychli. V tomto kvádru jsou tedy nejprve
všechny barvy obsažené v obrázku. Potom tento kvádr rozdělíme podél
osy s největší velikostí hrany na dva podkvádry. Tento krok se nazývá
cut. Nově vzniklé RGB kvádry zmenšíme tak, aby opět tvořily opsané
kvádry pro všechny body (barvy) v nich obsažené a zařadíme je do
seznamu ohraničujících kvádrů. Potom opět vybereme z této množiny
kvádr s největší stranou R, G nebo B a celý proces opakujeme tak
dlouho, dokud nerozdělíme RGB krychli na N částí. Nakonec barvy,
obsažené v jednotlivých ohraničujících kvádrech sloučíme, například
váženým průměrováním, a vypočtené barvy uložíme do palety.
Uvedený algoritmus má své modifikace, a to zejména ve způsobu
dělení RGB kvádru a ve způsobu výběru nového kandidáta na dělení.
Nejčastější způsob dělení kvádru je podle mediánu, tj. střední
hodnoty seznamu barev, uspořádaného podle barvy ve které se dělí [1],
pro některé případy je ale lepší obyčejné dělení v geometrickém
středu. Při dělení lze též uvažovat četnosti rozdělovaných barev a
vytvářet stejně početné kvádry. Dělení v mediánu je nazýváno median
cut a dělení v geometrickém středu geometric cut.
Uvedený algoritmus je ve variantě geometrického dělení velmi
rychlý a má velmi dobré výsledky [1].
Další metody kvantování barev jsou založeny na shlukové
analýze, podobně jako předchozí algoritmus. Asi nejlepší rozdělení
RGB krychle na daný počet oblastí (clustering) uvádí [9]. Provádí
rozdělení RGB krychle na shluky podle Voronoiova diagramu v prostoru
[12]. Tento diagram rozdělí krychli na N konvexních buněk,
obsahujících shluky barev, jejichž sloučením získáme hledanou paletu.
Nevýhoda tohoto algoritmu je v časové a paměťové náročnosti. Pro
vytváření diagramu v RGB prostoru si tento algoritmus alokuje (pokud
nepoužijeme doporučené předkvantování barev) celý barevný prostor 16
milionů barev, který pak geometricky zpracovává. Jiné metody
používají přímo metody shlukové analýzy založené na statistických
metodách [23].
Jedna z metod například náhodně vyplní paletu, kterou potom v
dalších krocích vylepšuje. Pro každou barvu obsaženou v histogramu
nalezne nejbližší barvu z této vytvářené palety a barvu v paletě
touto barvou z histogramu modifikuje. Modifikace se provádí váženým
průměrováním těchto dvou barev, váha jádra (položky v paletě) se tedy
postupně zvyšuje. Pokud v první fázi máme dvě barvy těsně vedle sebe,
v průběhu váhových modifikací se od sebe pravděpodobně vzdálí.
Tento proces lze provést buď jen jednou, nebo několikrát po
sobě, měl by poměrně rychle konvergovat. V principu jde o opačný
postup, než provádí median cut, který se snaží RGB prostor dělit na
kvádry a dodatečně vypočítat jádro.
výheň