Úloha 068: FM půltónování pro laserovou tiskárnu

Úkolem je implementovat speciální algoritmus na půltónování (halftoning), který bude fungovat na laserové tiskárně s rozlišením 1200dpi. Jde o algoritmus nazývaný "FM dithering" spočívající v nahodilém rozmisťování stejně velkých teček na papír tak, aby partie s tmavšími odstíny dostaly víc teček (ideálně by měl být zachováno pokrytí papíru černou barvou přímo úměrné odstínu).

FM dithering

Princip

Na papír se umisťují stejně velké tečky tak, aby jejich hustota odpovídala negativnímu jasu vstupního obrázku (černá [0] odpovídá maximu hustoty teček = souvislá potištěná plocha, bílá [255] nemá žádné tečky = bílý papír).

Aby byl výsledek vytištěný na laserové tiskárně co nejkvalitnější, je potřeba dodržovat větší vzdálenosti mezi jednotlivými tečkami (pokud tedy nemají být tak hustě, že se musejí dotýkat). Navrhuji použít nějakou variantu algoritmu Dona Mitchella, viz Don P. Mitchell: Spectrally optimal sampling for distribution ray tracing, v češtině si můžete přečíst Prezentaci z přednášky PRG nebo rozsáhlejší příspěvek: Rozmisťování bodů v rovině (prezentace), Rozmisťování bodů v rovině (článek).

Protože se má jednat o FM půltónování, bude vstupem vašeho algoritmu velikost jednotlivé tečky (v pixelech), počet teček potřebných pro reprezentaci draného obrázku si již musíte určit sami.

Výstup

Výsledek budu tisknout na laserové tiskárně s rozlišením 1200dpi (např. HP LaserJet 1320 nebo P2015). Pro představu, jak vypadá kvalita takového tisku, každý ode mne dostane testovací obrázek s tečkami velikosti 1x1 až 10x10 pixelů vytištěnými právě na takové tiskárně..

Základ

Jako základ poslouží projekt 068laser z repository grcis. Je připravena jednoduchá aplikace, ve které uživatel může zadat vstupní obrázek a ihned se automaticky spouští metoda Dither.TransformImage() přepočítávající vstupní obrázek do nové podoby. Výstup je poté zobrazen ve formuláři. Tuto metodu musíte přeprogramovat, příslušný úsek kódu je v souboru Dither.cs označen závorkami:

  // !!!{{
  // !!!}}

Pilotní implementace

pokud není načten žádný vstup, použije se vestavěný testovací obraz obsahující šedotónové přechody (viněty) apod.
vytvoření instance výstupního rastrového obrázku s pevným formátem Format1bppIndexed (dvouprvková paleta obsahuje pouze černou a bílou barvu)
výstupní obrázek je uložen po jednotlivých bitech, je tedy nutné používat vhodné bitové operace při jeho zapisování
rychlý přístup k binárním datům pixelů - pomocí metody Bitmap.LockBits() a unsafe bloku s použitím ukazatelů do uzamčeného paměťovém bloku
výpočet v samostatném vlákně - s vhodnou frekvencí je nutné v cyklech kontrolovat hodnotu globální logické proměnné Form1.cont (při hodnotě false by měl algoritmus co nejdříve předčasně skončit)
Drag & Drop vstupního obrázku - vstupní soubor můžete do formuláře přenést myší z jakékoli aplikace Windows podporující D&D
je implementováno několik jednoduchých metod ilustrujících čtení vstupních dat, generování náhodné polohy na základě hustoty pravděpodobnosti řízené vstupním obrázkem, kreslení teček daného obsahu do jednobitového výstupního obrázku:
1. generování náhodné polohy dle hustoty řízené vstupem: připraví se monochromatická verze vstupu (FloatImage) a použitím metody FloatImage.GetSample se opakovaně generuje náhodná poloha v obrázku. Pilotní řešení jen triviálně kreslí černé tečky dané velikosti (Dot1bpp(), velikost tečky dle textového parametru 'dot') bez dalších kontrol..
2. náhodné rozptylování s velkými tečkami: při průchodu pixely vstupního obrázku se pomocí náhodného generátoru rozhoduje, zda v daném místě nakreslit tečku či nikoli. Tečka je nakreslena opět pomocí funkce Dot1bpp()
3. náhodné rozptylování na úrovni pixelů: analogie B., jen se na výstup zapisují náhodně černé pixely. Velikost tečky ('dot') musí být nula

Ukázka teček velikosti 1.0 až 24.9
Dot sizes

Technické detaily

Vstupní obrázek je předán Vaší metodě v parametru Bitmap input, navrhuji ponechat rychlý přístup do vstupních dat. Dva číselné parametry udávají požadované rozlišení výstupu. Výstupní obrázek vracíte pomocí výstupního parametru out Bitmap output. Uživatelem zadaný textový parametr string param se v pilotní implementaci používá k načítání množství parametrů:

scale: škálovací koeficient vstupního obrázku (desetinné číslo)
gamma: gamma koeficient, který se má použít při načítání vstupu. Pokud je koeficient nulový, vstup se bere lineárně
dot: velikost (průměr v pixelech) tečky kreslené na výstupu. Je platný pro varianty A. a B. Pro variantu C. musí být nula
rnd: koeficient náhody pro varianty B. a C. Nula znamená žádnou náhodu (tj. prahování), jednička maximální použití náhody (náhodné rozptylování)
sampling: boolovská hodnota. 'true' zapíná variantu A.

Čtení šedého odstínu ze vstupní bitmapy (včetně bilineární interpolace mezi sousedními pixely) implementuje přiložená metoda Dither.GetGray(), musíte však zachovat rychlý přístup k vstupní bitmapě zafixované v paměti..

V případě Mitchellova vzorkování budete potřebovat rychlou kontrolu vzdálenosti vzorků. Pro urychlení doporučujeme použít nějakou vyhledávací datovou strukturu v rovině. Např. grid, Point-quadtree nebo KD-tree, viz doprovodné materiály.

Inicializace parametrů: Pro pohodlné ladění i pro odevzdání rozumnného default nastavení modifikujte inicializační proceduru InitParams(). Ta se zavolá vždy na začátku při inicializaci formuláře.
Druhý parametr out string tooltip použijte pro definici obláčkové nápovědy "tooltip", která se ukáže při najetí myši na textové pole 'Param'.
Do posledního parametru out string name napište své celé jméno (stejně jako do komentáře na první řádce zdrojového souboru). Usnadníte tím příp. automatické vyhodnocování výsledků.

Materiály

Přehledné shrnutí zdrojů informací:
Don P. Mitchell: Spectrally optimal sampling for distribution ray tracing
Prezentace o vzorkování z přednášky PRG
Rozmisťování bodů v rovině (prezentace), Rozmisťování bodů v rovině (článek).
Prezentace o datových strukturách pro rychlé vyhledávání

Odevzdání

Jako řešení úlohy posílejte mailem modifikovaný zdrojový soubor Dither.cs. Je potřeba podrobně popsat případné přidané parametry - jaký mají význam, jejich přípustné hodnoty, ..

Termín

Odevzdat do: 18. 12. 2016

Body

Základ: 10 bodů (fungující algoritmus)
dalších 1 až 5 bodů navíc za efektivitu a kvalitu rastru

Projekt

Visual Studio projekt: 068laser

Zdrojový soubor

Modifikujte a odevzdejte soubor: Dither.cs
Do komentáře na první řádce napište své jméno!
V posledním parametru funkce InitParams() rovněž vraťte své celé jméno!
Nezapomeňte popsat parametry a alespoň stručně upřesnit použitý algoritmus.

Testovací data

Můžete použít pár obrázků přímo z repository, z adresáře data, dále můžete použít třeba obrázky frozentree.png, cate1600x1200bw.png nebo egsr1.png.