Pružinový algoritmus a algoritmus úpravy hustoty pulsů

ve 2D

Iva Bartůňková3.ročník2004/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í vstupuZpracová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ý algoritmusHalftone Postprocessing

for Improved Rendition of Highlights and ShadowsC. Brian Atkinsy, Jan P. Allebachz, and Charles A. BoumanzVstup 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):1. 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)

2. Přemístění osamělých pixelů za účelem stejnorodějšího rozmístěníDef. TečkaPixel 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 algoritmus1 – 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čekProbí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:

1. Je prostorově oddělen od výrazných hran v obrázku – dle matice hran

2. Nesousedí s žádným pixelem stejné barvy = je to osamělý bod3. 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 okraje0 – 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 hrana1 – 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:(a) Původní obrázek(b) Po užití pružinového algoritmu(c) Matice okrajů(d) 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 algoritmuPosunutí 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.HauckBinarizač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 (1)

Dij – vzdálenost mezi dvěma body

K(Iij) – závislá na velikosti signálu v středu mezi body i a j

Implementace cyklem v 1DI(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í možnou roztečí pulsů D0

Dij = D0/I Tedy 0<I<=0.

Síly působí pouze mezi sousedícími body.

Def. Rovnovážný stavF12=…=Fij=…F N-1,N = F0

Rovnovážný stav tedy vede ke vztahu K(I)= D2

0 F0 /I2

Případ nekonstantní I(x)

Zobecnění ( do (1) dosadíme (4) ):Fij= D2

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

Implementace cyklem ve 2D

Rozšíření 1D konceptu na 2DKaž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 2DD2

ij = 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= eijD2

0 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