Dithering (počítačová grafika)

Dithering je v počítačovej grafike proces vytvarania polotónového obrazu takým spôsobom, aby ostala zachovaná pôvodná vizuálna informácia v čo najväčšej miere. K značnej strate vizuálnej informácie dochádza pri redukcii (nie len) TrueColor rastrového obrazu na HighColor, prípadne indexovaný (256, 16, 2 far.). Dithering (môžeme povedať aj rozptyl), túto stratu v istej miere kompenzuje. Pri redukcii sa môže vypočítať rozdiel pôvodnej a aproximovanej farby (Error-Diffusion/Dispersion), tento rozdiel sa volá kvantová odchýlka a prenáša sa z pixelu na pixel. Ďalšou možnosťou je nepoužiť výpočet odchýlky, ale použiť tzv. inverznú tabuľku farieb (Ordered/Positioned-Dithering), čo však vyžaduje presne definovanú paletu. Počas redukcie sa rozptylom simulujú farby, ktoré v obraze nie sú, tým, že spája zhluky pixelov. Princíp rozptylu je v tom, že je použitá vlastnosť ľudského zraku, kedy oko nevníma pixely, umiestnené dostatočne blízko seba, jednotlivo, ale ich vníma ako jeden farebný bod. Existuje niekoľko metód, ktoré polotónový obraz vytvárajú.

Metódy

Najznámejšie metódy rozptylu sú tieto:

náhodný rozptyl (random dithering)
maticový rozptyl (positioned alebo ordered, clustered-dot, void-and-cluster)
prenos chyby (error diffusion raster scan, e.d. riemersma space filling curve, dot diffusion)
rozptyl založený na modeli (model based dithering HVS)

Metódy sú uvedené vzostupne, od najmenej kvalitných, až po najkvalitnejšie. Kvalita v tomto prípade predstavuje istý stupeň vernosti, výsledného a originálneho obrazu.

Náhodný dithering

V angličtine random (random-based) dithering, kompenzuje straty pri redukcii farieb pripočítavaním/odpočítavaním náhodného čísla k výslednej farbe pixela.

Kvantovanie farieb

Rozptylové metódy majú priamy súvis s kvantovaním. Signály ako fyzikálne veličiny môžu spojito nadobúdať všetky možné hodnoty (v medziach daných technológiou) – potom hovoríme o spojitých signáloch, alebo nadobúdajú len isté presne dané hodnoty, preto hovoríme o nespojitých alebo diskrétnych signáloch. ^[1] Po aplikovaní uvedenej myšlienky na počítačovú grafiku nahrádzame pojem signál, signály za pojem farba, farby. Teda súvislé farebné spektrum meníme na nesúvislé, nespojité, inak povedané diskrétne spektrum. Je pritom nevyhnutné, že v spoločnom pásme (kvante) sa môže ocitnúť viac farieb. Tým vzniká kvantová chyba a zároveň dochádza k strate informácie o farbe.

Nekvantovaný obraz so súvislým farebným prechodom zelenej (256 stupňov zelenej).
Graf s vyznačením kvantovej funkcie, 16 pásiem.
Výsledný kvantovaný obraz s diskrétnymi stupňami zelenej (16 stupňov).

Maticový rozptyl

Pracuje s pixelmi, pričom nie je dôležité poradie spracovávania pixelov ani ich umiestnenie v rastri. Už navštívené pixely nie sú znova spracovávané. Simulácia sa vytvára "zahladzovaním" vzniknutej odchýlky. Používa sa dvojrozmerná matica, ktorá určuje svojimi číslami kvantové pásma. Jedna a tá istá farba tak, v závislosti od konkrétnej matice, nie je v každom okamihu kvantovaná do rovnakého pásma. Tým sa viditeľnosť nespojitosti farieb umenšuje. Matíc existuje mnoho druhov, najznámejšie sú matica s krížikovým vzorom a matica s bodíkovým vzorom.

Náhodný rozptyl

Umiestnenie pixelov v rastri a ich poradie spracovávania nehrá úlohu. Základný spôsob náhodného rozptylu je pridanie náhodného šumu na pixel, pomocou generátora pseudonáhodnej postupnosti. Šum môže byť okrem pixelu pridaný aj na hodnotu prahu (pri kvantovaní do 2 úrovní šedej).

Rozptyl s distribúciou odchýlky

Táto metóda zachováva odchýlku, vzniknutú počas kvantovania. Prenáša ju na okolité susedné pixely. Táto kvantová odchýlka môže byť prenesená z jedného pixelu v celej miere ( $E=1$ ) alebo môže byť prenesená v obmedzenej miere. To, v akej miere a na ktoré okolité pixely je chyba prenesená, určuje tzv. matica distribúcie. Najznámejšie sú matice podľa autorov Floyd-Steinberga (prví autori tejto koncepcie), Stuckiho, Burkesa, a i. Nemôžeme chybu prenášať už na spracované pixely. Pixely sa spracovávajú po riadkoch alebo po stĺpcoch. Je možné použiť režim striedania - serpent alebo Zig-Zag.

Rozptyl založený na modeli

Je rozptyl, ktorý používa postup, založený na konkrétnom modeli. Najčaastejšie na ľudskom vnímaní obrazu. V tejto súvislosti je z angličtiny známy model pod označením HVS. Existujú však aj iné.

Špecifiká uvedených metód

Maticový rozptyl

Riemersmov algoritmus pri pohybe po rastri. (úroveň 4)

matica číselných hodnôt predstavuje deliace hodnoty kvánt,
pre každý pixel je možné vyhľadať v matici presnú deliacu hodnotu (do ktorého kvanta pixel patrí),
najbežnejšie sú tieto matice (podľa dosiahnutého výsledku): krížikový vzor a bodíkový vzor.
vytvára opakujúce sa vzory,
zmena (farby) jedného pixelu neovplyvní žiadne ďalšie pixely, $d$ dvoch takto spracovaných obrazov bude menšia, než v porovnaní s distribúciou odchýlky. Vhodné preto pre animácie s kompresiou.

Náhodný rozptyl

matica číselných hodnôt predstavuje zadanie, ako sa kvantová odchýlka prenesie na susedné pixely (mieru, pozície pixelov)
nevytvára žiadne viditeľné, opakujúce sa vzory (pravidelnosti),
nezachováva pôvodnú jasovú intenzitu,
šum možno použiť na hodnotu prahu (kvantovanie do 2 pásiem) alebo na hodnotu vstupného pixelu
nezáleží na pozícii a poradí spracovávania pixelov.

Rozptyl s distribúciou odchýlky

z uvedených metód najmenšia zrnitosť,
možnosť výberu z množstva distribučných matíc, z ktorých v závislosti od koeficientov (váh) každá môže vytvoriť odlišný obraz (pre ostrosť Stuckiho, pre jemnosť Floyd-Steinberga, ...),
nutnosť spracovávať pixely po riadkoch alebo po stĺpcoch,
zmena jedného pixelu môže ovplyvniť veľké množstvo susedných (nenavštívených) pixelov, preto nevhodné pre animácie s kompresiou ( $d$ dvoch obrazov je väčšia než pri maticovom a Riemersmovom rozptyle).

Riemersmov rozptyl

Riemersmov rozptyl je založený na priestorvypĺňajúcich krivkách a jeho autorom je Thiadmer Riemersma.

neporovnateľne zrnitejší než rozptyl s distribúciou odchýlky,
každý pixel sa navštívi len raz (odchýlka sa vloží na každý pixel práve 1x),
spracovávanie pixelov po krivke (Hilbert-Peano),
vhodný pre animácie (sled obrazov) s použitou kompresiou ( $d$ dvoch komprimovaných obrazov bude menšia, než keby bola použitá metóda distribúcie odchýlky).

Ukážky uvedených metód rozptylu

2 farby

Max Wolf (pôvodný obraz)	Floyd-Steinbergova distribúcia návrh^{[nefunkčný odkaz]}	Stuckiho distribúcia návrh^{[nefunkčný odkaz]}

Shiau-Fanova distribúcia návrh^{[nefunkčný odkaz]}	Maticový rozptyl "Bayer" matica 2x2^{[nefunkčný odkaz]}	Maticový rozptyl "Bayer" matica 4x4^{[nefunkčný odkaz]}

Maticový rozptyl "Bayer" matica 8x8^{[nefunkčný odkaz]}	Maticový rozptyl "Void-and-cluster" matica 14x14 Archivované 2012-11-10 na Wayback Machine	Maticový rozptyl "Void-and-cluster" matica 25x25 Archivované 2012-11-10 na Wayback Machine

Riemersmov rozptyl

Viac než 2 farby

Obrázok s farebnými prechodmi. RGB 24 bitov.
Redukcia na 36 farieb
Redukcia na 36 farieb, metóda distribúcie odchýlky Floyd-Steinberg.
Redukcia na 36 farieb, metóda Riemersmovej distribúcie odchýlky.
Redukcia na 36 farieb, metóda maticového rozptylu.

Poznámky

V súčasnosti existuje reversibilný proces k ditheringu inverzné polotónovanie (Inverse Halftoning).

Referencie

↑ KOLENIČKA, Ján. Úvod k informatike. 2004. S. 30.

Odkazy

R.W. Floyd, L. Steinberg, An adaptive algorithm for spatial grey scale. Proceedings of the Society of Information Display 17, 75–77 (1976).
Pozri Riemersmov rozptyl na stránke Compuphase
Programy ktoré umožňujú vytvárať polotónové obrazy za pomoci ditheringu (rozptylu):ImageMagic, Gimp, [ http://www.brothersoft.com/microsoft-photo-editor-128651.html Archivované 2010-12-06 na Wayback Machine MS Photoeditor].

[kvantovanie-1] KOLENIČKA, Ján. Úvod k informatike. 2004. S. 30.

[1]