51

SUI 26. 3. 2015

© Josef Pelikán, http://cgg.mff.cuni.cz/

1 / 51

Náhodné rozmisťování bodů v rovině © 2014-15 Josef Pelikán, CGG MFF UK Praha http://cgg.mff.cuni.cz/~pepca/ Seminář strojového učení a modelování, 26. 3. 2015 SUI 26. 3. 2015


2 / 51

Jiří Matoušek (1963-2015) SUI 26. 3. 2015


3 / 51

Náhodné rozložení bodů.. ?

random SUI 26. 3. 2015


4 / 51


regular SUI 26. 3. 2015


5 / 51


CCDT SUI 26. 3. 2015


6 / 51

Řízení hustotou pravděpodobnosti

SUI 26. 3. 2015


7 / 51

Řízení hustotou pravděpodobnosti

SUI 26. 3. 2015


8 / 51

Příroda fyzikální zákony, sítnice oka, ..

SUI 26. 3. 2015


9 / 51

Aplikace vzorkování pro Monte-Carlo kvadraturu rychlost, diskrepance, hustota

tiskařství – tupování („stippling“), FM dithering hustota, spektrální vlastnosti, estetika

simulace přírodních jevů (stromy, buňky, ..), hry spektrální vlastnosti, estetika, hustota deterministické chování

design, architektura estetika, efektivita výroby (opakování vzorů)

generování sítí pro FEM diskrepance, hustota SUI 26. 3. 2015


10 / 51

Jak hodnotit rozložení bodů v rovině? rovnoměrnost pokrytí: diskrepance míra nahodilosti? estetika?

Lloydův algoritmus „Centroidal Voronoi“ skalární kvantizace 1982 SUI 26. 3. 2015


11 / 51

Diskrepance míra rovnoměrnosti pokrytí domény sadou vzorků Monte-Carlo integrace Zaremba 1968 zavádí pojem diskrepance (ukotvené levé horní rohy obdélníků) [0,0]

n

n d (a , b) = ab − N

∣

N-n

∣

D∞ = max a , b∈[0,1] d (a , b)

[a,b] [1,1] SUI 26. 3. 2015


12 / 51

Jiné formy diskrepance střední kvadratická hodnota místo maxima

D 2 = ∬ d (a , b)2 da db Stroud 1971 navrhuje počítat přes všechny obdélníky

n d (a , b , c , d ) = (a−c)(b−d ) − N

∣

SUI 26. 3. 2015


∣ 13 / 51

Visualizace diskrepance

random

SUI 26. 3. 2015


Dr-Cr 14 / 51

Shluky ! jsou přirozené? „Zákon řídkých jevů“ („Law of Rare Events“) Poissonovo rozdělení s malou hodnotou m

m = 0.5 c0 = 23 c1 = 8 c2 = 5

SUI 26. 3. 2015


15 / 51

Spektrální charakteristiky hodnocení míry pravidelnosti přítomnost nežádoucích vzorů výskyt shluků

spektrální analýza se objevuje při hodnocení kvality půltónování v tiskařství již Allebach 1977 detailní použití: Ulichney, Digital Halftoning, 1987

frekvenční spektrum – Fourierova transformace periodogram – již Schuster 1898 průměrování periodogramů – Bartlett 1948 SUI 26. 3. 2015


16 / 51

Fourierovské „power spectrum“ množina N vzorků v rovině: N k k =1

S = {s }

N k =1

= { [ xk , y k ] }

funkce rozložení vzorků (definovaná na R2): N

s( x , y) = ∑ δ( x−x k , y− y k ) k =1

SUI 26. 3. 2015


17 / 51

Fourierovské „power spectrum“ Fourierova transformace se dá zjednodušit na: N

−2 π i ( f⋅sk )

F( f )=∑e k =1

kde f je frekvenční vektor [fx, fy]  Z2 a nakonec výkonové spektrum: 1 P( f ) = ∣ F( f )∣ = N 2

SUI 26. 3. 2015

(

N

2

) (∑

1 ∑ cos(2 π f ⋅s k ) + N k=1


N

k=1

2

)

sin (2 π f ⋅s k )

18 / 51

Příklady spektrální analýzy Fourierova transformace

semi-jittering SUI 26. 3. 2015


19 / 51

Příklady spektrální analýzy radiálně průměrované spektrum hodnocení radiální symetrie redukce nízkých frekvencí (chceme „modrý šum“)

SUI 26. 3. 2015


20 / 51

„Pěkné“ spektrum vlastnosti „modrého šumu“ (Ulichney 1987)

Mitchell SUI 26. 3. 2015


21 / 51

„Pěkné“ spektrum radiálně průměrované spektrum červený graf – radiální rozptyl (izotropie spektra)

SUI 26. 3. 2015


22 / 51

Jiné „pěkné“ spektrum

SUI 26. 3. 2015


23 / 51

Příliš velká pravidelnost

SUI 26. 3. 2015


24 / 51

Pravidelný rastr + diskrepance + jednoduchost - pravidelnost - interference - nepokrývá doménu

SUI 26. 3. 2015


25 / 51

Náhodné vzorkování + nepravidelnost + jednoduchost + lze řídit hustotou + pokrývá doménu - diskrepance (shluky)

Nezávislé realizace vhodné náhodné veličiny

SUI 26. 3. 2015


26 / 51

Jittering (roztřesení) + nepravidelnost + jednoduchost + diskrepance + pokrývá doménu - nelze snadno řídit hustotou „Stratified sampling“ ve statistice..

SUI 26. 3. 2015


27 / 51

Jittering (roztřesení)

Subintervaly mohou být libovolné (stejný obsah)

SUI 26. 3. 2015


28 / 51

Semi-jittering + jednoduchost + diskrepance - částečná pravidelnost - nepokrývá doménu - nelze snadno řídit hustotou

SUI 26. 3. 2015


29 / 51

Semi-jittering

Amplitudy roztřesení mohou být i jiné

SUI 26. 3. 2015


30 / 51

N věží („N rooks“) + nepravidelnost + pokrývá doménu - trochu horší diskrepance (shluky)

SUI 26. 3. 2015


31 / 51

N věží („N rooks“)

V každém řádku i sloupci právě jeden vzorek..

SUI 26. 3. 2015


32 / 51

Hammersley + výborná diskrepance + deterministické + velmi rychlý výpočet - nelze zahušťovat - špatné spektrum

Na podobném principu je založena i Haltonova sekvence.. SUI 26. 3. 2015


33 / 51

Deterministické sekvence na podobném principu jsou založeny: Halton, Hammersley, Larcher-Pillichshammer

pro prvočíslo b nechť je kladné přirozené číslo n vyjádřeno pomocí b-ární reprezentace: L−1

n = ∑ d k (n)b

k

k =0

pak je definováno číslo v intervalu [0,1): L−1

g b (n) = ∑ d k (n)b

−k −1

k =0

SUI 26. 3. 2015


34 / 51

Halton, Hammersley slavná Haltonova sekvence (např. b1=2, b2=3):

x (n) = [ g b (n) , g b (n) ] 1

2

Hammersley sekvence (např. b=2):

[

n x (n) = , g b (n) N

SUI 26. 3. 2015

]


35 / 51

Larcher-Pillichshammer + výborná diskrepance + deterministické + velmi rychlý výpočet + lze randomizovat - nelze zahušťovat - špatné spektrum

SUI 26. 3. 2015


36 / 51

Larcher-Pillichshammer místo dk(n) se používá

lp k (n) =

(

)

L

∑ d i (n) i=k

mod 2

analogicky definujeme

lp(n) = ∑ lp k (n)2

−k −1

k

.. a posloupnost vzorků SUI 26. 3. 2015

[

n x (n) = , lp(n) N


] 37 / 51

Pravidelnosti ve spektru

SUI 26. 3. 2015


38 / 51

Poissonovo diskové vzorkování + nepravidelnost + estetika + diskrepance + pokrývá doménu + lze řídit hustotou - pomalé - obtížné nastavení D Dva vzorky nesmějí být blíž než D SUI 26. 3. 2015


39 / 51

Poissonovo diskové vzorkování Algoritmus: vrhání šipky s kontrolou vzdálenosti („dart-throwing with rejection“)

D = 0.1

SUI 26. 3. 2015


40 / 51

Mitchellův algoritmus + jako Poisson-disk + inkrementální + nepotřebuje D - velmi pomalý! Algoritmus: N-tý vzorek vybírám z NK kandidátů, přijmu ten nejvzdálenější K > 5 (větší K .. kvalita) SUI 26. 3. 2015


41 / 51

Inkrementální ukázka

Počet vzorků: 10, 40, 160, 640, 2560 K = 10 SUI 26. 3. 2015


42 / 51

Lloydův algoritmus + diskrepance + modrý šum + výborně pokrývá - pomalý! - pravidelnosti na konci konvergence! Algoritmus: generátor každé Voronoi buňky se posune do těžiště své buňky .. iterace SUI 26. 3. 2015


43 / 51

Lloyd – postup výpočtu

SUI 26. 3. 2015

1

2

3

10

30

90


44 / 51

Pravidelnosti Lloyd (Centroidal Voronoi), N = 1024, iterations = 100

SUI 26. 3. 2015


45 / 51

Kapacitně omezené distribuce + diskrepance + modrý šum + výborně pokrývá + lze řídit distribucí - pomalý (ale je známo množství urychlení) Vychází z Centr. Voronoi: Aby nevznikaly pravidelnosti, zavádí se kapacitní omezení SUI 26. 3. 2015


46 / 51

CCPD

SUI 26. 3. 2015


47 / 51

CCPD – postup výpočtu

SUI 26. 3. 2015

0

1

2

3

4

23


48 / 51

Porovnání metod - diskrepance průměrování přes 100 pokusů 1024 vzorků v sadě, vhodné nastavení parametrů jednotlivých vzorkování (někdy i více variant) Stroudova diskrepance (všechny obdélníky, RMS) průměrná diskrepance (·10-3) a std. odchylka (·10-6)

Lloydův algoritmus pro dobrý výsledek se musí zastavit před koncem konvergence (empiricky: generace 40) pro porovnání i výsledek z pokročilejšího stadia konvergence – cca Centroidal Voronoi (generace 400)

SUI 26. 3. 2015


49 / 51

Porovnání metod - diskrepance metoda Pravidelné Hammersley * Larcher-Pillichshammer * Náhodné Jittering Semi-jittering N věží Poissonův disk Mitchell Lloyd (g=40) Lloyd (g=400) CCPD SUI 26. 3. 2015

diskrepance 7.468 0.811 0.811 8.941 2.593 4.159 5.220 3.255 3.183 6.400 5.661 2.154


SD 0.0 0.0 0.0 2.5 0.0 0.0 0.5 0.2 0.2 2.5 1.8 0.0 50 / 51

Literatura P. Shirley: Discrepancy as a Quality Measure for Sample Distributions, Eurographics 1991 J. Matoušek: Geometric Discrepancy – An Illustrated Guide, Springer, 2000 A. Lagae, P. Dutré: A Comparison of Methods for Generating Poisson Disk Distribution, CGF 08 M. Balzer, T. Schlömer, O. Deussen: CapacityConstrained Point Distributions: A Variant of Lloyd's Method, SIGGRAPH 2009 D. P. Mitchell: Spectrally optimal sampling for distribution ray tracing, SIGGRAPH 1991 R. Ulichney: Digital Halftoning, MIT Press, 1987 SUI 26. 3. 2015


51 / 51

51

Recommend Documents