Zobrazenie zdroja stránky Dithering (počítačová grafika)

'''Dithering''' je v [[počítačová grafika|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 [[raster|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 [[pixel]]ov. 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.
<ref name=kvantovanie>
{{cite journal
  | last = Kolenička
  | first = Ján
  | authorlink = Ján Kolenička
  | title = Úvod k informatike
  | journal = 
  | volume = 
  | pages = 30
  | date = 2004
}}</ref>
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.

<gallery>
Obrázok:Nekvant.png|Nekvantovaný obraz so súvislým farebným prechodom zelenej (256 stupňov zelenej).
Obrázok:kvantdiagram.png|Graf s vyznačením kvantovej funkcie, 16 pásiem.
Obrázok:Kvant16.png|Výsledný kvantovaný obraz s diskrétnymi stupňami zelenej (16 stupňov).</gallery>

== 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 (<math>E=1</math>) 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 ===
[[Súbor:Std_dither_anim.gif|right|thumb|Algoritmus rozptylu s distribúciou odchýlky pri spracovávaní pixelov v rastri. (úroveň 4)]]
[[Súbor:Riemersma.gif|right|thumb|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, <math>d</math> 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 (<math>d</math> 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 [http://www.compuphase.com/riemer.htm 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 (<math>d</math> 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 [http://caca.zoy.org/browser/web/trunk/static/study/out/fig3-1-1.png návrh]{{Nedostupný zdroj|date=október 2023 |bot=InternetArchiveBot |fix-attempted=yes }}
!Stuckiho distribúcia [http://caca.zoy.org/browser/web/trunk/static/study/out/fig3-2-3.png návrh]{{Nedostupný zdroj|date=október 2023 |bot=InternetArchiveBot |fix-attempted=yes }}
|-
|[[Obrázok:Max Wolf.png]]
|[[Obrázok:Max WolfFS.png]]
|[[Obrázok:Max WolfST.png]]
|-
!Shiau-Fanova distribúcia [http://caca.zoy.org/browser/web/trunk/static/study/out/fig3-2-1c.png návrh]{{Nedostupný zdroj|date=október 2023 |bot=InternetArchiveBot |fix-attempted=yes }}
!Maticový rozptyl "Bayer"<br>[http://caca.zoy.org/browser/web/trunk/static/study/fig2-3-1c.png matica 2x2]{{Nedostupný zdroj|date=október 2023 |bot=InternetArchiveBot |fix-attempted=yes }}
!Maticový rozptyl "Bayer"<br>[http://caca.zoy.org/browser/web/trunk/static/study/out/fig2-3-2.png matica 4x4]{{Nedostupný zdroj|date=október 2023 |bot=InternetArchiveBot |fix-attempted=yes }}
|-
|[[Obrázok:Max WolfSF.png]]
|[[Obrázok:Max Wolf_ORD 2x2.png]]
|[[Obrázok:Max Wolf_ORD 4x4.png]]
|-
!Maticový rozptyl "Bayer"<br>[http://caca.zoy.org/browser/web/trunk/static/study/out/fig2-3-2b.png matica 8x8]{{Nedostupný zdroj|date=október 2023 |bot=InternetArchiveBot |fix-attempted=yes }}
!Maticový rozptyl "Void-and-cluster"<br>[http://caca.zoy.org/browser/web/trunk/www/study/out/fig2-7-1.png matica 14x14] {{Webarchive|url=https://web.archive.org/web/20121110133334/http://caca.zoy.org/browser/web/trunk/www/study/out/fig2-7-1.png |date=2012-11-10 }}
!Maticový rozptyl "Void-and-cluster"<br>[http://caca.zoy.org/browser/web/trunk/www/study/out/fig2-7-2.png matica 25x25] {{Webarchive|url=https://web.archive.org/web/20121110133216/http://caca.zoy.org/browser/web/trunk/www/study/out/fig2-7-2.png |date=2012-11-10 }}
|-
|[[Obrázok:Max Wolf ORD 8x8.png]]
|[[Obrázok:Max Wolf ORD VC 14x14.png]]
|[[Obrázok:Max Wolf ORD VC 25x25.png]]
|-
!Riemersmov rozptyl
|-
|[[Obrázok:Max WolfRIE2.png]]
|}

===Viac než 2 farby===
<gallery>
gradtriplet2.png|Obrázok s farebnými prechodmi. RGB 24 bitov.
tripletQuant.png|Redukcia na 36 farieb
tripletError.png|Redukcia na 36 farieb, metóda distribúcie odchýlky Floyd-Steinberg.
tripletRiemer.png|Redukcia na 36 farieb, metóda Riemersmovej distribúcie odchýlky.
tripletOrd.png|Redukcia na 36 farieb, metóda maticového rozptylu.
</gallery>

==Poznámky==
* V súčasnosti existuje reversibilný proces k ditheringu '''inverzné polotónovanie''' (Inverse Halftoning).

== Referencie ==
<references />

== 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 [http://www.compuphase.com/riemer.htm stránke Compuphase]
* Programy ktoré umožňujú vytvárať polotónové obrazy za pomoci ditheringu (rozptylu):[http://www.imagemagick.org ImageMagic], [http://www.gimp.org Gimp], [ http://www.brothersoft.com/microsoft-photo-editor-128651.html {{Webarchive|url=https://web.archive.org/web/20101206025950/http://www.brothersoft.com/microsoft-photo-editor-128651.html |date=2010-12-06 }} MS Photoeditor].

[[Kategória:Počítačová grafika]]