Barevné formáty Neindexované barevné formáty
zleva: 15 bpp, 12 bpp
zleva: 9 bpp (3-3-3), 8 bpp (3-3-2)
zleva: 7 bpp (2-3-2), 6 bpp (2-2-2)
zleva: 5 bpp (2-2-1), 4 bpp (1-2-1)
3 bpp (1-1-1)
srovnání použití koeficientu (vlevo) a pouhého bitového posunu (vpravo), shora: 8 bpp (3-3-2), 6 bpp (2-2-2), 3 bpp (1-1-1)
Indexované barevné formáty Statická vyhledávací tabulka Velmi snadný způsobem, jak vytvořit paletu pro obrázek je založený na tom, že si všechny zobrazitelné barvy promítneme na úsečku, kterou rozdělíme rovnoměrně tolikrát, kolik chceme získat barev. Jednotlivé dělicí body potom budou označovat reprezentativní barvy. Tento postup je však nepraktický, protože barvy vytvořené palety závisí pouze na počtu zvolených barev a nikoliv na barvách obsažených v obrázku (ten se vůbec neprochází). Při vhodně zvoleném počtu barev však může vzniknout globálně optimální paleta, kterou je možné použít obecně s nejmenší ztrátou, avšak konkrétní obrázky si obvykle vyberou jen několik barev, přičemž zbylá většina je k neupotřebení. Jedinou výhodou algoritmu je vysoká rychlost, protože odpadá potřeba jednoho průchodu obrázkem. Algoritmus začíná jednoduchým určením délky kroku na úsečce se všemi barvami:
step =
2563 16777216 = colors − 1 colors − 1
Následuje cyklus, který naplní jednotlivé položky palety (pro 256 barev jsou indexy palety i od 0 do 255). Hodnota index udává umístění na přímce:
index = i ⋅ step Toto číslo se posléze převede do 256-kové soustavy, takže získáme trojciferné číslo s hodnotami cifer 0-255. Tyto hodnoty označíme za intenzity jednotlivých barevných složek a získáme tak jednotlivé barvy. Výsledky Dalším nešvarem tohoto algoritmu je periodicita, která se při špatně zvolené hodnotě kroku projeví (v případě 256 nebo 16 barev budou barevné složky stejné, takže vygenerovaná paleta paleta bude obsahovat stupně šedi):
Static look-up table algoritmus, zleva: 256 barev, 16 barev Sporadické výsledky dostaneme při zvolených neobvyklých počtech barev:
Static look-up table algoritmus, shora: 250 barev, 171 barev
Static look-up table algoritmus, 8 barev
Prostorové podvzorkování Velmi jednoduchý a rychlý algoritmus pro redukci počtu barev se zakládá na zmenšení obrázku na „velikost palety“, takže barvy pixelů obrázku budou určovat reprezentativní barvy. Nevýhodou algoritmu je zanedbání velkého množství pixelů, které se vyhýbají načítaným hodnotám. Paleta pak obsahuje mnoho podobných, ne-li stejných barev, přičemž jiné důležité barvy se v ní vůbec nevyskytují. Rychlost je však hlavní předností, která dovoluje např. redukci počtu barev v reálném čase. Velikost zmenšené bitmapy odvodíme z předpokladů, že počet jejích pixelů se má blížit požadovanému počtu barev a její poměr stran musí odpovídat poměru stran původního obrázku. Platí tedy:
width′ ⋅ height ′ = colors width′ width = height ′ height Odtud dostáváme vztahy pro velikost podvzorkované bitmapy:
width ⋅ colors width′ = ceiling height colors height ′ = ceiling width′ Hodnoty jsou zaokrouhleny nahoru, protože velikost bitmapy je diskrétní. Výsledky
Spatial subsampling algoritmus, zleva: 256, 16 a 8 barev
Prostorové průměrování Tento algoritmus pracuje v podstatě stejně, jen při zmenšování bitmapy používá interpolaci (v programu ImagingShop bikubická). Tím vlastně započítává i méně četné barvy, ale dochází tak k míchání barev a barvy v paletě už odpovídají spíše skupinám pixelů, než konkrétním barvám obsaženým v obrázku. V některých případech však tento algoritmus dosahuje lepších výsledků, než při podvzorkování. Výsledky
Spatial averaging algoritmus, zleva: 256, 16 a 8 barev
rozdíl ve výstupu při použití podvzorkování (vlevo) a interpolace
palety při použití podvzorkování (vlevo) a interpolace
Stejnoměrné rozdělení barevného prostoru Tento algoritmus pracuje v barevném prostoru RGB krychle, která je rozsekána na přibližně tolik malých shodných kvádříků, kolik požadujeme barev. Jakmile je prostor exaktně rozdělen, prochází se pixely obrázku a jejich barvy se
vnáší do jednotlivých kvádrů. Reprezentativní barva se z každého kvádru přečte jako průměr všech barev, které se v dané krychli nacházejí. Nevýhodou tohoto algoritmu je rozklad barevného prostoru, který nerespektuje rozložení barev v krychli, takže některé kvádříky nemusí obsahovat žádnou barvu (nevyužité položky palety) a některé mohou obsahovat dva shluky barev, které se zprůměrňují do jedné barvy a vnesou tak do výsledného obrázku velké homogenní plochy. Algoritmus trpí podobnými problémy, jako předchozí, nicméně už částečně vychází z rozložení barev v obrázku, takže přináší lepší výsledky. Implementace algoritmu je také poměrně jednoduchá. Nejprve je třeba určit počet hran kvádříků na každé ose výchozí RGB krychle. Součin počtů hran na každé ose by se měl co nejvíce blížit požadovanému počtu barev, přičemž kvádříky by se svým tvarem měli co nejvíce blížit krychli. Počet hran musí být přirozené číslo, proto budeme ze začátku zaokrouhlovat dolů a začneme u modré osy. Potom bude následovat červená a nakonec zelená. Díky tomuto pořadí připadne na zelenou největší zbytek, což odpovídá pořadí citlivosti člověka na doplňkové barvy (zelená bude mít nejvíce úrovní, pak červená a nakonec modrá):
slicesb3 = colors slicesb = floor
(
3
colors
)
slicesr2 ⋅ slicesb = colors
colors slicesr = floor slicesb slicesg ⋅ slicesr ⋅ slicesb = colors
colors slicesg = floor slicesr ⋅ slicesb Velikost kroku na ose je dána:
stepr , g ,b =
256 slicesr , g ,b
Před zahájením procházení pixelů obrázku je zinicializováno statické pole struktur o rozměrech slicesr × slicesg × slicesb . Každý prvek tohoto pole obsahuje čtyři proměnné: součty hodnot barevných složek pixelů spadajících do daného prvku pole (kvádříku v RGB krychli) a vlastní počet takových pixelů. Pozice v poli, na které se jednotlivé proměnné inkrementují je [
R G B , , ] , kde R, G, B jsou hodnoty barevných složek stepr stepg stepb
příslušných pixelů. V závěru algoritmu se celé pole projde, přičemž každá složka reprezentativní (průměrná) barvy na určité pozici je podíl odpovídajících součtů barevných složek a počtu pixelů. Při mapování barev do palety je potřeba dát pozor na kvádříky, ve kterých žádná barva není (dělení nulou). Výsledky
Uniform algoritmus, zleva: 256, 16 a 8 barev Z posledního dodatku vyplývá, že ne vždy se objeví nějaká barva v každém kvádříku, rovněž nelze krychli rozdělit na zlomky kvádříků, proto je výsledná paleta neúplná:
Paleta obrázku Parrots, Uniform algoritmus, 256 barev
Popularity algoritmus Tento algoritmus vychází pouze z histogramu obrázku. Pro získání přesného histogramu je potřeba nejprve projít celý obrázek, často se v praxi prochází třeba jen každý čtvrtý pixel. Obvykle je to dostačující, protože se nevychází z přesných počtů pixelů té které barvy, ale pouze je třeba určit, které barvy je víc než jiné. Podívejme se na histogramy původního obrázku a obrázku zpracovaného Popularity algoritmem. Vzdálenost na vodorovné ose (příklad níže) odpovídá intenzitě barevné složky, na svislé ose potom pravděpodobnost výskytu této intenzity. K průchod histogramy červené, zelené a modré složky dojde tolikrát, kolik výsledných barev požadujeme. Při prvním průchodu se z každého histogramu „odpíchne“ ta intenzita, která odpovídá největší výskytovosti. Z hodnot intenzit jednotlivých složek potom vytvoříme nejpopulárnější barvu. V druhém průchodu zvolíme druhou nejpopulárnější barvu a tak dále.
Histogram obrázku Parrots před a po zpracování Popularity algoritmem (256 barev) Achylovou patou algoritmu je zanedbání barev, které se v obrázku vyskytují sice málo, ale vyjadřují klíčové detaily. Velmi záleží na tvaru histogramu. V příkladu je nejvíce barev nakumulováno v oblasti menších intenzit, takže výstupem algoritmu při nižším počtu zvolených barev budou barvy právě z této oblasti. Obrázek tedy bude tmavý. Hladší graf histogramu zase vede k vkládání podobných barev, takže výsledný obrázek může pozbývat na kontrastu. Oba tyto nešvary jsou na výsledcích vidět. Na druhou stranu je algoritmus přímočarý, pouze vyčte příslušné barvy z histogramu (rychost). Navíc může u obrázků, které neobsahují příliš odstínů jedné barvy, dosahovat podobných výsledků, jako jiné algoritmy. Výsledky
Popularity algoritmus: 256 barev, vygenerovaná paleta Paleta obrázku obsahuje barvy seřazené podle „popularity“, avšak barvy se mohou odchylovat od původních, protože byly vytvořeny na základě analýzy jednotlivých barevných kanálů a ne celých barev (viz chocholka papouška arara).
Degradace kontrastu a světlosti při sníženém počtu barev, zleva: 16 a 8 barev
Diversity algoritmus Hlavní problém Popularity algoritmu (žádný ohled na barvy s menším výskytem) částečně řeší Diversity algoritmus, který nehledá jen intenzity s největším výskytem, ale střídavě intenzity s nejvyšším-nejnižším výskytem. Samozřejmě zase není zaručeno, že právě barvy, které z hlediska výskytu leží někde mezi těmito dvěma extrémy, nebudou zrovna ty, které dokreslují důležité detaily (základ v histogramu).
Diversity algoritmus: 256 barev, vygenerovaná paleta
Diversity algoritmus, zleva: 16 a 8 barev Z obrázků je patrné, že vynucení méně se vyskytujících barev nevede vždy k výběru všech vhodných barev. Výsledky jsou však obvykle lepší, než u popularity algoritmu.
Octree algoritmus Tento algoritmus patří k jedněm z nejpoužívanějších, zejména kvůli rychlosti a efektivitě. K redukci počtu barev využívá oktalové stromy (pro vysvětlení a implementaci viz kap. Datové struktury v počítačové grafice). Octree algoritmus vychází z RGB krychle. Každý bod v této krychli vyjadřuje svými souřadnicemi jednu barvu a krychle sama může obsahovat všechny zobrazitelné barvy (rozměry krychle jsou tedy 256x256x256). Nejprve je potřeba získat prvních k unikátních barev, tedy právě tolik barev, kolik má mít výsledný obrázek. Jednotlivé barvy leží zpočátku v listech stromu v hloubce 8 (maximální hloubka). Samotná pozice listu říká, jakou barvu vyjadřuje, avšak list obsahuje pro pozdější redukci počtu barev datovou strukturu s proměnnými r, g, b, references, které jsou typu long. Při každém přidání nové barvy Se jde ve stromu tak hluboko, až se narazí na uzel obsahující tuto strukturu (takový uzel se považuje za list) a k proměnným r, g, b se přičtou hodnoty složek vkládané barvy. K proměnné references se přičte jedna. Jakmile se ve stromu vyskytne k+1 unikátních barev, je třeba provést redukci některého uzlu. Zde se objevuje základní problém algoritmu, tedy nalezení toho správného uzlu, který by měl být zredukován. Hlavním kritériem pro volbu uzlu je jeho hloubka, protože uzly ve vetší hloubce mají pod sebou listy, které vyjadřují bližší barvy, takže jejich zredukováním vznikne menší odchylka. Druhým kritériem je počet pixelů, který daný uzel vyjadřuje (tedy součet počtu pixelů barev, které vyjadřují listy). Vybíráme samozřejmě z uzlů, ze kterých už vycházejí jen listy, což jsou zpočátku uzly v hloubce 7, později mohou být i výše. Obvykle se jako druhé kritérium pro výběr uzlu volí co nejmenší počet pixelů s barvami, které jsou v listech níže. Lze však volit jako druhé kritérium co největší počet reprezentovaných pixelů. V tomto případě bude celková odchylka výsledného obrázku vyšší,
avšak získáme věrnější zobrazení v detailních částech obrázku na úkor homogenních barevných ploch a protáhlých přechodů. V programu ImagingShop je zohledněno první kritérium. Výsledky
Octree algoritmus, zleva: 256, 16 a 8 barev Vylepšená varianta Vylepšená varianta algoritmu buduje sekundární oktalový strom, který slouží ke kontrole, zda je vkládaná barva nová, do redukovaného stromu tedy přicházejí pouze unikátní barvy. Obrázky jsou potom pestřejší, protože paleta obsahuje více rozdílných barev.
originál
vlevo: obrázek zpracovaný Octree algoritmem a jeho paleta, vpravo: Improved octree algoritmus
Median Cut algoritmus Tento algoritmus poprvé představil P. Heckbert začátkem 80. let. Algoritmus se snaží dosáhnout přibližně stejného počtu pixelů na každou reprezenativní barvu v paletě. Výsledky
Median Cut algoritmus, zleva: 256, 16 a 8 barev
Variance-based algoritmus Další algoritmy pro redukci počtu barev
