05

Pružinový algoritmus a algoritmus úpravy hustoty pulsů ve 2D Iva Bartůňková 3.ročník 2004/05

Půltónování a rozptylování Procesy, převádějící obrázek se spojitými odstíny na jeho reprezentaci omezenou paletou (nejčastěji binární) Nejznámnější algoritmy: chybová difúze, maticové a náhodné rozptylování,… Nevýhoda nejběžnějších algoritmů: nepříjemné rozložení osamělých teček ve velmi světlých a velmi tmavých oblastech. Algoritmy, které nevýhodu řeší: • Modifikovaná chybová difúze • Úprava hustoty pulsů ve 2D • Půltónování na bázi stromového kódování • Pružinový algoritmus

• Pružinový algoritmus – vylepšuje výsledek, vytvořený jiným algoritmem – tedy pouze post-zpracování – Čím se liší od ostatních alg. řešících problém?

Nezávislý na algoritmu, užitém k vytvoření vstupu Zpracovává binární vstup bez znalosti původního spojitého obrázku

• Úprava hustoty pixelů ve 2D – Také vylepšuje výsledek, vytvořený jiným algoritmem – Používá původní spojitý obrázek

• Společné: Využití myšlenky imaginárních pružin, spojující uvažovaný bod se sousedy

Pružinový algoritmus Halftone Postprocessing for Improved Rendition of Highlights and Shadows C. Brian Atkinsy, Jan P. Allebachz, and Charles A. Boumanz Vstup algoritmu: – –

Obrázek se spojitými odstíny barvy Obrázek vytvořený některým z algoritmů tvorby binárního vyjádření

Myšlenka (2 části): 3. Určení regionů, kde může být algoritmus aplikován (algoritmus způsobuje rozmlžení hran – tedy je nutno oblasti okolo hran z aplikace algoritmu vynechat)

4. Přemístění osamělých pixelů za účelem stejnorodějšího rozmístění Def. Tečka Pixel jiné barvy, než přiléhající pixely – černý v bílé i bílý v černé

Def. Osamělý pixel V místech extrémního tónu jednoznačný pojem.

Kroky algoritmu

1.

Část algoritmu Vytvoření binární mapy odpovídající pixelům zdroje:

•

0 – na tento pixel bude aplikován algoritmus 1 – na tento pixel nebude aplikován algoritmus

2.

Část algoritmu Určení sousedů tečky Přesun tečky do nejbližšího lok. minima funkce e(n)

• • •

•

Tečka je se svými sousedy spojena imag. pružinami. U každé pružiny předpokládáme klidovou délku rovnou průměru vzdáleností tečky od sousedících teček, tedy všechny pružiny jsou ve klidovém stavu stejně dlouhé. Funkce e(n) – každé poloze n tečky přiřazuje energii, danou vzájemným působením se sousedícími body tečky.

2.část algoritmu •

Přemísťování teček Probíhá v cyklu – 1 průběh = 1 průchod obrázkem Každý pixel je možným kandidátem posunu – tedy pro něj proběhne podcyklus, pokud splňuje následující podmínky: 3. Je prostorově oddělen od výrazných hran v obrázku – dle matice hran 4. Nesousedí s žádným pixelem stejné barvy = je to osamělý bod 5. Průměr vzdáleností od N sousedů je větší, než zvolený práh. Velikost prahu se obvykle volí 3 pixely.

Hledání lokálního minima funkce e(n) • Lokální minimum funkce = místo, kam chci tečku přesunou. • Posunování tečky: – série posunů o 1 pixel – Končí v lokálním minimu funkce – (k+1). posun: Posun z n(k) do pozice n(k+1), přičemž n(k) a n(k+1) jsou přiléhající pozice. n(k+1) je vybrána jako přiléhající pozice, která nejvíce zmenší funkční hodnotu e(n) Omezení: pozice n(k+1) nesmí mít žádný přiléhající pixel stejné barvy – důvod popsán v části o výběru sousedů

Zjištění funkční hodnoty e(n) •

Energie pozice n je součet ei - energií pružin, spojujících tečku v n se sousedy:

• Jak spočtu ei(n) ? • Jak spočtu di (n)? Kde di (n) je vzdálenost mezi n – pozicí tečky a jejím i-tým sousedem. A kde r je klidová délka pružiny.

• Jak spočtu r ? Kde n(0) je počáteční pozice tečky

Příklady rozložení energie a posunů teček -vrstevnice spojují místa se stejnou f-ční hodnotou (a),(b) – přibližně konvexní vrstevnice (c) Lokálních minim bývá často několik (d) Pokud už se bod v minimu nachází, k posunu nedojde

Hledání sousedících teček • •

Cíl výběru: Maximálně stejnorodý výsledek Výběr N teček: – Vezmu tu nejbližší z každé z N pravidelných úhlových výsečí okolo tečky – Pro každou tečku výseče orientuji náhodně.

• Možný problém výběru: Vznik přiléhajících teček tím, že ignorovaná tečka je náhodou zrovna v lok. minimu, do něhož chci uvažovanou tečku posunout. Ošetřeno 3. podmínkou výběru tečky jako kandidáta posunu. •Počet sousedů: Autoři algoritmu experimentálně určili za vhodné N = 4. •Počet cyklů algoritmu: Již dvě opakování algoritmu dají dobrý výsledek, který se dalšími opakováními zlepšuje jen málo

2.část algoritmu - Tvorba mapy okrajů • Vytvoříme binární mapu E: 1 – pixel je blízko od okraje 0 – ostatní

Důvod: Algortitmus jinak rozmlží ostré hrany a okraje v obrázku Algoritmy tvorby mapy E: - algoritmus autorů - C. Brian Atkinsy, Jan P. Allebachz, and Charles A. Boumanz

- Dále např.: K.-C. Fan and C.-C. Han, „Parallel mechanism for

detecting contours in binary images," Electronic Imaging, vol. 3, no. 1, pp. 30, 36, 1994.

Algoritmus autorů •

Výslednou mapu E získáme jako logické OR map a Ed a El – El mapa hran ve světlých regionech – Ed mapa hran v tmavých regionech

• Mapy Ed a El získáme blokovou replikací z el a ed , což jsou mapy, v nichž 1 prvek odpovídá bloku LxL (tzv. L-bloku) v Ed a El • L – tzv. vzorkující faktor

Algoritmus autorů-pokračování

• Jak vytvořit el a ed ? Vytvořím D – matici čísel z intervalu{0,..,L2}, kde prvek je roven počtu tmavých pixelů v L bloku

Konstrukce el •

Matice el: 0 - byla-li v odpovídajících 2x2 prvcích matice D detekována hrana 1 – jinak

Detekce hrany v 2x2 bloku v D: - pronásobením 2x2 bloku vertikálním a horizontálním operátorem (viz obrázek) získám dvě čísla – ta porovnám s proměnným prahem t. Je-li alespoň jedno z nich větší, hrana byla detekována.

t = K1(o) + K2, Kde o je součet hodnot v 2x2 bloku matice D a K1 a K2 jsou kladné konstanty.

•Matice ed: konstrukce je obdobná, jen místo D použiji Dinv

Dinvij = L2-Dij

Výběr konstant a prahů • Výpočet prahu t: – t závisí na o, tedy je algoritmus nejcitlivější na hrany právě v nesvětlejších (nejtmavších) místech. – Závislé t funguje alespoň tak dobře jako pevné t. – Konstanta K1: ve většině případů je výsledek s nenulovým K1 obdobný nulovému případu, v některých situacích je ale výrazně lepší

• Jak získat nejlepší K1 a K2? – Zkoušením pro konkrétní vstup, ideální hodnoty neznáme. Autoři odporučují K1 z [0.0,0.6] a K2 z [2.0,8.0].

• Jak vybrat faktor L? – Velké L – příliš hrubá mapa hran, malé L způsobí malý rozsah bloku a znehodnocení vyhledávání hran. Experimenty určily jako nejlepší volbu L = 8.

Výsledky algoritmu Následující obrázky – vždy čtveřice: (b) Původní obrázek (c) Po užití pružinového algoritmu (d) Matice okrajů (e) Pružinový algitmus bez použití matice okrajů Rozlišení: 100 dpi

Naskenovaný obrázek, chybová difúze

Foto z CD, chybová difúze

Problémy algoritmu Posunutí toho, co posunuto být nemá a neposunutí toho, co posunuto být má

•Červí efekt chybové difúze označen za hranu •Nerozpoznání hranice LH obdélníku => Někdy tečky prosáknou mezerou v matici hran

Shrnutí – pružinový algoritmus • Algoritmus vylepšuje rozmístění osamělých pixelů v oblastech extrémního tónu. Používá k tomu přesun teček definováním vztahů se sousedními tečkami a přesunutím na energeticky nejvýhodnější pozici. Přesouvá pouze tečky v regionech, kde nebyla detekována hrana, aby se předešlo případnému rozmlžení ostrých linií.

Obrázek vytvořen Photoshopem, rozptylování maticí 128x128

Algoritmus úpravy hustoty pulsů ve 2D (2-D PULSE DENSITY MODULATION BY ITERATION FOR HALFTONING)

PDM Autoři: R.Eschbach a R.Hauck Binarizační algoritmus pro vylepšení výsledku půltónování a rozptylování.

Myšlenka: Obrázek lze chápat jako spojitou vektorovou funkci (Fx,Fy). A body binární reprezentace mohu vyjádřit jako přítomnost nebo nepřítomnost pulsu fixní velikosti.

Fyzikální model Obecný algoritmus PDM: Použití pro kódování spojitého signálu. Jak? Fixní pulsy a měnící se rozteče pulsů Nalezení odpovídajícího rozložení: Vyjádření pulsů jako bodů se silami, které mezi body působí. Body = centra pulsů Síly mezi body jsou závislé na roztečích tak, aby rovnovážná pozice vyjadřovala odpovídající rozložení Výpočet síly působící mezi dvěma body Fíj =K(Iij)/D2ij Dij – vzdálenost mezi dvěma body K(I ) – závislá na velikosti signálu v středu mezi body i a j

(1)

Implementace cyklem v 1D I(x) – nyní 1D signál, v pro naše účely nekonstantní Případ konstantní I(x): Logické omezení: Maximální velikost I je dána minimální roztečí pulsů D0 Dij = D0/I Tedy 0
možnou

Případ nekonstantní I(x) Zobecnění ( do (1) dosadíme (4) ): Fij= D20 F0 /I2D2ij

(5)

F0 – libovolná, ale nenulová

Rovnovážný stav s použitím (5) se dosáhne: Pro každý bod spočtu síly působící mezi ním a sousedy. Bod posunu podle výsledné síly. To celé provádím, dokud není velikost posunů menší, než zvolená přesnost. V případě 1D vede libovolné původní rozložení pulsů vždy na stejné výsledné rozložení

1D – úprava hustoty pulsů

(a) (b) (c) (d)

Signál f(x) Výchozí rozmístění, použity stejné rozteče Pružiny= působící síly, Křivky = posun bodů, situace po 100 cyklech Výsledné rozložení pulsů

Implementace cyklem ve 2D Rozšíření 1D konceptu na 2D Každý bod nyní sdílí vzájemné působení s množinou bodů, tzv. sousedů Počet sousedů však na rozdíl od 1D není zřejmý.

Logické omezení ve 2D D2ij = D20/I Dáno poměrem plochy odpovídající pulsu a plochy okolí – to je vždy čtverec vzdálenosti.

Síly působící mezi body

Modifikace 1D na 2D: Fij= eijD20 F0 /I2D2ij eij – jednotkový vektor Cyklus probíhá stejně jako v 1D, pouze s vektorovými veličinami.

Vlastnosti 2D PDM • Výsledek je různý v závislosti na počátečním rozložení pulsů Důvody – Výběr sousedů není jednoznačný – Sousedi bodu mohou být v různých cyklech různí

• Výběr sousedů Autoři algoritmu použili 8 nejbližších bodů

Výsledky algoritmu

Obrázky (a) vytvořeny náhodnou distribucí bodů, (b) po 43 cyklech 2D PDM

2D PDM - Shrnutí • PDM – obzvláště vhodné pro scannery • Fyzikální koncept aplikovatelný na libovolný počet dimenzí. • Výsledek algoritmu závisí na – Počátečním rozmístění bodů – Parametrech algoritmu – Počtu sousedů (Chybová difúze místo náhodné distribuce výrazně zlepší výsledek)

• Problémy algoritmu Časově velmi náročný – praktická použitelnost spíše v rozumné kombinaci s jinými PDM metodami