Fraktální dimenze

Definice fraktální (vnitřní) dimenze a její aplikace v databázích

David Hoksza

Obsah

Topologická dimenze Hausdorffova dimenze Fraktální dimenze (FD) Výpočet FD v O(n) Aplikace při selekci atributů Výpočet FD pomocí box-counting Aplikace při detekci očí v obrázku

Topologická dimenze (TD)

Geometricky hladké objekty Počet parametrů popisujících objekt

Pevně definovaným vztahem lze popsat libovolný bod objektu

Celočíselná TD nezávisí na dimenzi prostoru, kde je daný

objekt umístěn Vlastnosti tělesa nezávislé na měřítku

Příklady TD

Přímka y = y0 + kt

TD = 1 Funkce

x = sin(t)*log(t) y = cos2(t) z = t

TD = 1 Libovolná hladká plocha

Kruh, trojúhelník, n-úhelník TD = 2

Hausdorffova (fraktální) dimenze (FD)

Neceločíselná Udává úroveň členitosti objektu Délka břehu ostrova

Zmenšování měřítka => růst délky Zabírá více místa než hladká křivka Větší než topologická

Měření FD (1)

Úsečka Úsečku rozdělíme na N

dílů Měřítko: s = 1/N Pro FD platí: NsD = 1

NsD = 1 logNsD = log 1 logN + logsD = 0 Dlogs = - logN D = (-lognN)/logs D = logN/log(1/s)

D = logN/log(1/s) = lognN/logN = 1

Měření FD (2)

Čtverec s = 1/N2

D = logN/log(1/s) = logN/log(N2) = 1/(1/2) = 2

Měření FD (3)

Kochova křivka

5 iterací křivky

Měření FD (3)

Kochova křivka 3 x zjemnění => 4 x délka s = 1/3 => N = 4 D = logN/log(1/s) = log4/log3 = 1.261895

“Vnořená” a “Vnitřní” Dimenze

“Embedding” (vnořená) dimenze (ED) datasetu je dimenze jeho adresového prostoru. Počet atributů datasetu

“Intrinsic” (vnitřní) dimenze (ID) je dimenze prostorového objektu reprezentovaného datasetem, nezávisle na prostoru, do kterého je vnořen.

Vlastnosti ID a ED

Vzájemně nezávislé atributy => ED == ID Polynomiální korelace snižuje ID o jednotku Ostatní korelace můžou jinak (i o zlomek) Obvykle ID z dat není zřejmá ID určuje počet atributů potřebných k

charakterizaci datasetu

Zobecněná Hausdorffova fraktální dimenze (1)

Rozdělme E-dimenzionální prostor do hyperkrychlí o hraně r. Budiž N(r) počet buněk obsahující alespoň 1 bod. Potom fraktální dimenze D0 je definována jako:

Vhodné z matematického hlediska (nekonečný počet bodů)

Hausdorffova fraktální dimenze pro konečné množiny

Datasety nemají nekonečně mnoho bodů => definujeme pouze pro jistý úsek

Pro množinu sebepodobných bodů v rozsahu rozlišení r z (r1,r2) je Hausdorffova dimenze D0 pro tento rozsah:

Zobecněná Hausdorffova dimenze pro konečné množiny

Existence zobecněné definice existuje nekonečně mnoho definic Pro množinu sebepodobných bodů v rozsahu rozlišení r z

(r1,r2) je zobecněná Hausdorffova dimenze Dq definována:

Korelační fraktální dimenze ( vnitřní dimenze)

r – velikost pole

Cr,i - počet bodů v i-tém poli velikosti r

FD při selekci atributů

Datová sada o N atributech Ne všechny stejně důležité Detekce existence závislosti Odstranění závislých atributů

FD pro selekci - koncept

Zjištění “fraktální dimenze” datasetu Zjištění atributů, které FD málo ovlivňují Odstranění atributů

FD pro selekci - koncept

Obvykle data v tabulce Sloupce == vlastnosti Řádky == body Tabulka == body v E-dimenzioním

prostoru, kde |E| = |sloupce| Obvykle atributy vyjadřují číselné hodnoty

=> těžko vyjádřitelný primární klíč => indexování podle celé množiny atributů

=> “prokletí dimenzionality”

Fractal Dimension Algorithm (1) Počítá v čase O(N*E*R) E-dimenzionální prostor Mřížka s buňkami o velikosti r Cr,i - počet bodů v i-tém poli velikosti r S(r) = suma(Cr,i

2) Získání fraktální dimenze

Spočítat S(r) s různými hodnotami r a spočítat směrnici výsledné přímky

Vytvořena multiúrovňová struktura pro počítání S(r) <Cr,i,p>, kde p je ukazatel do další úrovně pro danou buňku Kazdá úroveň obsahuje S(r) pro hodnotu r=r/2 z předchozí úrovně Struktura je vytvářena v hlavní paměti => omezení její velikosti

Fractal Dimension Algorithm (2)

Množina 5-ti bodů v 2D

Fractal Dimension Algorithm (3)

Algorimus pro selekci atributů

FD (=D) <= ED (=E) Existuje D neodvoditelných atributů (D <= E) => existuje (E-D) odvoditelných atributů

Získat Eliminovat

Parciální fraktální dimenze (pD)Korelační fraktální dimenze datasetu bez bez

jednoho či více atributů.

Algorimus pro selekci atributůFDR – Fractal Reduction Algorithm

Spočítaní FD celého datasetu Spočítání pD s každým odebraným atributem Vybrání atributu s minimálním rozdílem pD

od FD datasetu Odebrání atributu Iterativně opakovat

Př.: atributy {a,b,c} c=a+b

FDR

Datasety pro testování Sierpinsky5

5D Sierpinského trojúhelník a=x,b=y,c=a+b,d=a2+b2,e=a2-b2

Hybrid5 5D Sierpinského trojúhelník a=x,b=y,c=f(a,b),d=random1,e= random2

Měna 6-ti dimenzionální dataset normaliyovaných kurzů měny z 01/02/87-01/28/97 a=Hong Kongský dolar, b=Japonský jen, c=US dolar, d=Německá marka,

e=Francouzský frank, f=Britská libra Eigenfaces

11000 vekotrů obličeje z projektu Informedia 16 dimenzí

FD datasetů

Testování 450 MHz Pentium II 128 MB RAM Windows NT 4.0

C++

Počítání dimenze O(N)

FDR Lineární vzhledem k N Kvadratická vzhledem k dimenzi prostoru

Testování – fraktální dimenze

Testování - FDR

Lokace páru očí v obrázku

3 úrovně1. detekce kandidátů na oko

2. normalizace, FD, orientovaná FD, vytvoření dvojic

3. FD hraničního obrázku, FD tváře, výstup

FD pomocí box-counting (1) Počet kvádrů (box) pokrývající obrázek převedený do 3D 2D -> 3D

x=x y=y z=“intenzita šedé barvy”

Vytvoření mřížky obrázek IxI mřížka SxS buňky (i,j), kde 0<=i,j<r, r=spodní_celá_část(I/S) převod na krychli SxSxS’

maximální_intensita_šedé = G spodní_celá_část(G/S’) = spodní_celá_část(I/S)

FD pomocí box-counting (2)

Padne-li min a max intenzita šedé na buňce (i,j) do kostek k, resp. l, pak nr(i,j)=l-k+1, kde r=spodní_celá_část(I/S)

celkový počet kostek potřebný k pokrytí povrchu:

Nr=sumai,jnr(i,j) FD = směrnice přímky proložené jednotlivými hodnotami

(log(Nr),log(1/r))

),(,

jinji

r

SI /

FD pomocí box-counting pro binární obrázek

2 hladiny – černá, bílá černá – obrázkový bod bílá – bod pozadí

mřížka obrázek IxI mřížka SxS nr(i,j) = “počet obrázkových bodů v buňce” zbytek stejně jako pro šedou

FD v centru oka a jeho okolí

Detekce oka v obrázku

“Údolí” – malá intenzita šedé Kandidát na region oko (x,y), jestliže:

f(x,y)<t1 , f(x,y)...obrázek tváře, t1…hranice

Φv(x,y)>tv , Φv...údolí, tv…hranice

vybrání kandidáta z každého regionu

Spárování kandidátů (1)

normalizace stupňů šedi (rozdílné světelné podmínky na každém z očí)

stejná velikost stejná orientace

místo square-box-counting se počítá s orintovanými kvádry horizontální fraktální dimenze FDh

vertikální fraktální dimenze FDv

Na rozdíl od ostatních textur se FDh a FDv duhovek výrazněji liší

Spárování kandidátů (2) Příklad FDh a FDv

Spárování kandidátů (3)

(x0,y0) ... lokace kandidáta levého oka

(x1,y1) ... lokace kandidáta pravého oka

Meye … průměrná FD regionu oka

t1, t2, t3, t4 ... hranice

Verifikace párů

(x,y) ... pozice regionu páru očí Feye(x,y) … průměrná FD regionu páru očí

Fface(x,y) … průměrná FD regionu tváře

t5, t6 ... hranice (t5 = 0,038, t6 = 0,035)

při překrytí regionů volíme minimum z:|Feye(x,y) – M’eye(x,y)| + |Fface(x,y) – M’face(x,y)|

Experimenty Použití MIT a ORL databáze obličejů

Získání ostatních vlastností

Literatura Fast feature selection using fractal dimension

Caetano Tranja Jr., Afma Traina, Leejay Wu, Christos Faloutsos Estimating the Selectivity of Spatial Queries Using the

‘Correlation’ Fractal Dimension Alberto Belussi, Christos Faloutsos

Fractional Box-Counting Approach to Fractal Dimension Estimation Jie Feng, Wei-Chung Lin, Chin-Tu Chen

Locating the eye in human face images using fractal dimensions K.-H.Lin, K.-M.Lam,W.-C.Siu

Fraktály v počítačové grafice Pavel Tišnovský, www.root.cz