eské vysoké u£ení technické v Praze Fakulta elektrotechnická Katedra po£íta£·
Bakalá°ská práce
3D rekonstrukce neuronovými sít¥mi
Daniel Fi²er
Vedoucí práce:
RNDr. Miroslav Kulich, Ph.D.
Studijní program: Elektrotechnika a informatika, strukturovaný, Bakalá°ský
Obor: Výpo£etní technika
20. dubna 2010
iv
v
Pod¥kování D¥kuji RNDr. Miroslavu Kulichovi, Ph.D., za odborné vedení mé bakalá°ské práce.
vi
vii
Prohlá²ení Prohla²uji, ºe jsem práci vypracoval samostatn¥ a pouºil jsem pouze podklady uvedené v p°iloºeném seznamu. Nemám závaºný d·vod proti uºití tohoto ²kolního díla ve smyslu 60 Zákona £. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o zm¥n¥ n¥kterých zákon· (autorský zákon).
V Praze dne 15. 5. 2009
.............................................................
viii
Abstract The goal of the bachelor thesis is to implement growing self organizing neural network called Growing Self-reconstruction Maps [19], which is useful for surface reconstruction of 3D objects. It is also shown that the algorithm can be used for reconstruction of data collected by a mobile robot. Input is an unstructured set of points in space de ning a 3D object, while output should be a reconstructed surface of the object. The neural network is adopted to the input set to learn geometric arrangement and topology of points. Various models of 3D objects as well as data collected by a mobile robot can be reconstructed using this algorithm as will be shown in the bachelor thesis.
Abstrakt Cílem bakalá°ské práce je implementace rostoucí samoorganizující se neuronové sít¥ Growing Self-recontruction Maps [19] slouºící k rekonstrukci povrchu 3D objektu a p°edev²ím ukázat, ºe tento algoritmus lze s úsp¥chem pouºít i na rekonstrukci senzorických dat nam¥°ených mobilním robotem. Vstupem je nestrukturovaná mnoºina bod· v prostoru de nující 3D objekt, výstupem by pak m¥l být zrekonstruovaný povrch objektu. Neuronová sí´ se tak musí adaptovat na vstupní mnoºinu bod· a nau£it se geometrické uspo°ádání a topologii bod·. Tímto algoritmem lze rekonstruovat nejr·zn¥j²í modely 3D objekt· nebo také, jak bude ukázáno v této bakalá°ské práci, senzorická data nam¥°ená mobilním robotem.
ix
x
Obsah 1 Úvod
1
2 Samoorganizující se neuronové sít¥
3
2.1
Kohonenovy mapy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2
Rostoucí neuronové sít¥ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3
GSRM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3 Popis algoritmu GSRM 3.1
7
Struktura mapy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.1.1
Uzel
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.1.2
Hrana
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.1.3
Trojúhelníková plo²ka . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.2
Stavba mapy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.3
Postprocesing
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.3.1
3.3.2
3.3.3 3.4
12
3.3.1.1
Trojúhelníkové plo²ky
. . . . . . . . . . . . . . . . . . . . .
13
3.3.1.2
Hrany . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
Dokon£ení triangulace mapy . . . . . . . . . . . . . . . . . . . . . . .
15
3.3.2.1
De nice omezení
. . . . . . . . . . . . . . . . . . . . . . . .
15
3.3.2.2
Vytvá°ení nových plo²ek . . . . . . . . . . . . . . . . . . . .
16
Postprocesing jako celek
Parametry algoritmu 3.4.1 3.4.2 3.4.3 3.4.4 3.4.5
3.5
Zkvalitn¥ní mapy . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .
17
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
εb a εn . . . Parametr λ . . . . . . Parametry β a α . . . Parametr agemax . . . Parametry φv , θf a φe Parametry
. . . . . . . . . . . . . . . . . . . . . . . . . .
18
. . . . . . . . . . . . . . . . . . . . . . . . . .
18
. . . . . . . . . . . . . . . . . . . . . . . . . .
18
. . . . . . . . . . . . . . . . . . . . . . . . . .
19
. . . . . . . . . . . . . . . . . . . . . . . . . .
19
Historie revizí £lánku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.5.1
První verze £lánku
20
3.5.2
Druhá verze £lánku . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.5.3
T°etí a zatím poslední verze . . . . . . . . . . . . . . . . . . . . . . .
20
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Optimalizace 4.1
23
Nalezení nejbliº²ího uzlu . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4.1.1
Struktura pro vyhledávání . . . . . . . . . . . . . . . . . . . . . . . .
24
4.1.2
Vyhledávací algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . .
25
xi
xii
OBSAH
4.2
Kumulativní £íta£ chyb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Implementace 5.1
26
29
Základní struktury knihovny . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
5.1.1
Uzel, hrana, plo²ka
29
5.1.2
Reprezentace mapy (sít¥) . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.3
Struktura
gsrm_t
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
5.2
Implementace seznam· . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
5.3
SVT - Nástroj pro zobrazování 3D objekt· . . . . . . . . . . . . . . . . . . .
32
6 Experimentální výsledky 6.1
Rekonstrukce 3D povrchu
35 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
6.1.1
Kvalita vygenerovaných povrch· . . . . . . . . . . . . . . . . . . . . .
36
6.1.2
Výstupní parametry rekonstrukcí
36
. . . . . . . . . . . . . . . . . . . .
6.2
R·zná výstupní rozli²ení . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
6.3
as pot°ebný pro rekonstrukci . . . . . . . . . . . . . . . . . . . . . . . . . .
38
6.4
Shrnutí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
7 Záv¥r
41
A Obrázky výsledk· rekonstrukcí objekt·
43
B Obsah p°iloºeného CD
53
Literatura
55
Seznam obrázk· 2.1 2.2
Mapování kohonenovy mapy na bitmapové obrázky. Zdroj: [16] . . . . . . . . Porovnání výsledk· t°í r·zných rostoucích neuronových sítí. Zleva: Growing Grid, Growing Cell Structures, Growing Neural Gas. Zdroj: [13]
2.3
4
. . . . . . .
5
Výsledky porovnání z [10]. T°i r·zná rozloºení pravd¥podobnosti. Siln¥ ohrani£ené £ásti jsou místa, kde je uniformní rozloºen pravd¥podobnosti, zbytek prostoru má nulovou hustotu pravd¥podobnosti. Horní °ádek je adaptace KFM a spodní °ádek GCS. Zdroj: [10] . . . . . . . . . . . . . . . . . . . . . . . . .
3.1
3.2
Propojení dvou uzl·, které jsou nejblíºe vstupnímu signálu (n1 ,
pokud
nejsou propojené a jejich spole£ní sousedé (na ,
. . .
Na obrázku (a) stav p°ed p°idáním nového
s uº
p°idaným novým uzlem. 3.3
n2 ),
nb ) propojení jsou. . . . uzlu nr . Na obrázku (b) stav
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
11
Ukázka rekonstrukce 3D objektu ze vstupních bod· - (a). Na obrázcích (b) aº (f ) lze vid¥t, jak neuronová sí´ roste a zp°es¬uje se.
. . . . . . . . . . . . . .
3.4
P°íklad odstran¥ní hran p°ipojených do mapy jen jednou stranou.
3.5
P°íklad odstran¥ní p°í£ných hran, které nemohou tvo°it trojúhelníkovou plo²ku, a
. . . . . .
následné vytvo°ení hran v místech, kde je to díky tomuto kroku moºné. . . . 3.6
5
12 14
15
Na obrázcích (a) a (b) jsou vid¥t struktury, ve které lze vytvo°it trojúhelníky jen jedním zp·sobem. Na obrázcích (c) a (d) pak struktury, ve kterých není
3.7 3.8
triangulace jednozna£n¥ dána. . . . . . . . . . . . . . . . . . . . . . . . . . .
16
Ukázka dokon£ení triangulace £ásti mapy. . . . . . . . . . . . . . . . . . . . .
17
Ukázka výstupu algoritmu podle první verze £lánku. Vlevo je pohled na zrekonstruovaný objekt, vpravo pak v¥t²í detail. Z obrázku je vid¥t, ºe je tvo°eno velké mnoºství hran a plo²ek, které se r·zn¥ k°íºí a p°ekrývají a netvo°í tak souvislý povrch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1
21
Ukázka, jak vypadá struktura pro vyhledávání ve 2D. Na obr. (a) je vyzna£en £tverec, ve kterém za£íná vyhledávání (kam spadá vstupní signál), na obr. (b) okolní vrstva £tverc·, která je v prvním kroku také prohledávána. Na obr. (c) je znázorn¥no, ºe pokud je nejbliº²í uzel ve vzdálenosti do jedné délky hrany, musí to být nejbliº²í uzel. Na obr. (d) je znázorn¥na dal²í vrstva a na obr. (e) op¥t ukázka, ºe pokud je nejbliº²í uzel ve vzdálenosti do dvou délek hrany, musí to být nejbliº²í uzel v·bec. . . . . . . . . . . . . . . . . . .
gsrm_node_t, gsrm_edge_t a gsrm_face_t. gsrm_mesh_t. . . . . . . . . . . . . . . . . . . . . . .
25
5.1
Schéma propojení struktur
. . .
30
5.2
Schéma struktury
. . .
30
xiii
xiv
SEZNAM OBRÁZK
5.3
Ukázka programu - je zobrazen objekt de novaný ve výpise 5.2 . . . . . . . .
6.1
Doba rekonstrukce objekt· Místnost a Dragon p°i r·zných výstupních rozli-
33
²eních vynesená do grafu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
A.1
Vstupní body jednotlivých objekt·. . . . . . . . . . . . . . . . . . . . . . . .
43
A.2
Zrekonstruovaný objekt Dragon 20 000 uzly.
. . . . . . . . . . . . . . . . . .
44
A.3
Zrekonstruovaný objekt Arm 20 000 uzly. . . . . . . . . . . . . . . . . . . . .
45
A.4
Zrekonstruovaný objekt Místnost 20 000 uzly.
46
A.5
Detail nekvalitn¥ zrekonstruované £ásti objektu Dragon, na kterém jsou jsou vid¥t nevytriangulované £ásti povrchu.
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
A.6
Detaily zrekonstruovaného objektu Arm.
A.7
Detail zrekonstruovaného objektu Místnost - pohled od dve°í dovnit° místnosti. 47
A.8
Rekonstrukce objektu Dragon v r·zných rozli²eních. . . . . . . . . . . . . . .
A.9
Ukázka p°eu£ení sít¥ p°i rekonstrukci objektu Dragon. P°i p°eu£ení vzniká více nevytriangulovaných d¥r v zrekonstruovaném povrchu.
. . . . . . . . . . . .
47 48 49
A.10 Detail hlavy zrekonstruovaného objektu Dragon v r·zných rozli²eních. . . . .
50
A.11 Rekonstrukce objektu Místnost v r·zných rozli²eních. . . . . . . . . . . . . .
51
A.12 Detail pohledu dovnit° místnosti rekonstruovaného objektu Místnost v r·zných rozli²eních. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
Seznam tabulek 6.1
Tabulka hodnot parametr· pouºitých b¥hem experiment· . . . . . . . . . . .
35
6.2
Tabulka výsledk· rekonstrukce pro cílové rozli²ení 20 000 uzl·. . . . . . . . .
36
6.3
Tabulka po£tu plo²ek v map¥ p°ed a po postprocesingu. . . . . . . . . . . . .
36
6.4
Tabulka výsledk· rekonstrukce objektu Dragon pro r·zné výstupní rozli²ení.
37
6.5
Tabulka výsledk· rekonstrukce objektu Místnost pro r·zné výstupní rozli²ení.
38
xv
xvi
SEZNAM TABULEK
Kapitola 1 Úvod Cílem bakalá°ské práce je implementace rostoucí samoorganizující se neuronové sít¥ Growing Self-recontruction Maps [19] slouºící k rekonstrukci povrchu 3D objektu a p°edev²ím ukázat, ºe tento algoritmus lze s úsp¥chem pouºít i na rekonstrukci senzorických dat nam¥°ených mobilním robotem. Vstupem je nestrukturovaná mnoºina bod· v prostoru de nující 3D objekt, výstupem by m¥l být zrekonstruovaný povrch objektu. Neuronová sí´ se tak musí adaptovat na vstupní mnoºinu bod· a nau£it se geometrické uspo°ádání a topologii bod·. Tímto algoritmem lze rekonstruovat nejr·zn¥j²í modely 3D objekt· nebo také, jak bude ukázáno v této bakalá°ské práci, senzorická data nam¥°ená mobilním robotem. Techniky pouºívané k rekonstrukci povrchu jsou vyuºívány v nejr·zn¥j²ích aplikacích jako je vizualizace medicínských dat, která slouºí pro diagnostikování chorob (nap°. úrazy hlavy) nebo plánování operací (nap°. v plastické chirurgii) [20]. Tyto techniky lze také s úsp¥chem pouºít i pro p°evod 3D objekt· nebo rovnou celých prost°edí do virtuální reality. Rekonstrukce povrchu má své místo i v robotických aplikacích. Ze senzoru robotu se obvykle získává velké mnoºství bod· v prostoru. Cílem rekonstrukce je rapidní sníºení po£tu bod· tak, aby se ztratilo jen minimum informace v nich obsaºené. P°i rekonstrukci povrchu se naopak ze senzorických dat vyt¥ºuje dal²í dodate£ná informace. Tou informací je práv¥ zrekonstruovaný povrch, který lze následn¥ vyuºít pro mapování prost°edí, vizualizaci prost°edí nebo nap°. k plánování pohybu robotu.
Bakalá°ská práce je rozd¥lena následujícím zp·sobem. Druhá kapitola obsahuje stru£ný úvod do rostoucích neuronových sítí. Ve t°etí kapitole je kompletn¥ popsán implementovaný algoritmus, ve £tvrté kapitole jsou uvedeny optimalizace, které výrazn¥ zrychlují provád¥ní p·vodního algoritmu a v páté kapitole jsou popsány nejd·leºit¥j²í £ásti implementace. V následující, ²esté, kapitole jsou uvedeny výsledky experiment· a v poslední, sedmé, kapitole je záv¥r, kde budou shrnuty výsledky celé bakalá°ské práce.
1
2
KAPITOLA 1.
ÚVOD
Kapitola 2 Samoorganizující se neuronové sít¥ Samoorganizující se neuronové sít¥, n¥kdy také nazývané samoorganizující se mapy (Self Organizing Maps SOM) nebo Kohonenovy mapy, jsou neuronové sít¥ schopné u£ení se bez
u£itele. To znamená, ºe b¥hem u£ení, na rozdíl od u£ení se s u£itelem, není pot°eba
znát trénovací mnoºinu dvojic vstup a o£ekávaný výstup. Samoorganizující se mapy jsou schopny samy nalézt pot°ebnou informaci p°ímo v trénovacích datech (vstupech) bez jakýchkoli vn¥j²ích informací (bez p°ítomnosti u£itele), trénovací data jsou tedy p°ímo vstupní data. Výstupem pak je p°ímo sama neuronová sí´ (mapa), která se de novaným zp·sobem adaptovala na vstupní data.
2.1
Kohonenovy mapy
U vzniku samoorganizujících se neuronových sítí stál profesor Teuvo Kohonen, který navrhl první model SOM Kohonen Feature Map (KFM) [14]. T.
Kohonen
navrhl
model,
ve
kterém
je
dop°edu
dána
neuronová
sí´
i
se
svojí
topologií to znamená, ºe je dán po£et neuron·, kaºdý neuron (uzel) má svojí polohu a také má ur£ené svoje sousedy. Kaºdý z t¥chto neuron· je propojen se v²emi vstupními signály (mnoºinou vstupních dat vstupní vrstva). Kaºdý vstupní signál je de nován n-dimenzionálním vektorem polohy (v1 , v2 , ..., vn ) a kaºdý neuron pak svou polohou v síti (sousedností
s
okolními
neurony)
a
svým
váhovým
vektorem
také
n-dimenzio-
nálním (w1 , w2 , ..., wn ). Algoritmus u£ení probíhá tak, ºe se náhodn¥ vybírají vstupní signály, které se aktivují a neuronová sí´ se na n¥ postupn¥ adaptuje. Ke kaºdému aktivovanému vstupnímu signálu se vybere nejbliº²í neuron ze sít¥ neuron, u n¥hoº je rozdíl mezi jeho váhovým vektorem a pozicí vstupního signálu
~v
w ~
nejmen²í, tento vektor se nazývá vít¥zný. Následn¥ se vyberou
v²echny neurony z okolí vít¥zného neuronu, p°i£emº polom¥r okolí se s kaºdým cyklem (kaºdým dal²ím aktivovaným vstupním signálem) sniºuje. Nakonec se váhový vektor vít¥zného uzlu i váhové vektory uzl· z okolí posunou sm¥rem k polohovému vektoru vstupního signálu. Intenzita s jakou jsou neurony posunuty (síla jakou neurony vstupní signál p°itahuje) se sniºuje s jejich vzdáleností od vít¥zného uzlu. Váhový vektor vít¥zného neuronu se tedy sníºí nejvíce a váhové neurony na okraji jeho okolí nejmén¥.
3
4
KAPITOLA 2.
SAMOORGANIZUJÍCÍ SE NEURONOVÉ SÍT
P·vodn¥ byl tento algoritmus pouºit pro rozpoznávání °e£i, ale byl s úsp¥chem pouºit i pro dal²í aplikace, jako je bibliogra cká klasi kace [15], analýza velkých soubor· dat [8], komprese dat [6] atd.
Obrázek 2.1: Mapování kohonenovy mapy na bitmapové obrázky. Zdroj: [16]
Takto postavená neuronová sí´ má ale jednu nevýhodu a ta spo£ívá v nutnosti dop°edu de novat strukturu a velikost neuronové sít¥. To totiº m·ºe být v n¥kterých p°ípadech komplikované aº nemoºné. Zárove¬ to z £ásti odporuje tomu, co bylo o SOM napsáno vý²e a to je schopnost sít¥ adaptovat se bez dal²ích vn¥j²ích informací. Zde totiº ona inicializace z £ásti supluje u£itele, protoºe struktura a velikost sít¥ musí být vybrána se znalostí problému, se znalostí konkrétních vstupních dat. Pro rekonstrukci povrchu 3D objektu byla SOM pouºita nap°. v [21]. Tato metoda ale vyºaduje, aby uºivatel na po£átku vybral mapu s korektní topologií (sousednost bod· i povrch), která zhruba odpovídá tvaru rekonstruovaného objektu - nap°. kulová plocha. Algoritmus pak p°izp·sobí tento objekt vstupní mnoºin¥ bod·. Je zde tedy op¥t nevýhoda v tom, ºe je pot°eba dop°edu znát p°ibliºn¥ rekonstruovaný objekt a celá rekonstrukce je na inicializaci siln¥ závislá. Tento problém se snaºí °e²it rostoucí neuronové sít¥.
2.2
Rostoucí neuronové sít¥
Modely rostoucích samoorganizujících se neuronových sítí se snaºí °e²it problém výchozího de nování sít¥ tak, ºe ji jednodu²e nede nují. Místo toho se sí´ náhodn¥ inicializuje do n¥jakého minimálního stavu, ve kterém se snaºí optimáln¥ adaptovat na vstupní signály. Postupem £asu se pak p°idávají jednotlivé neurony (nebo v¥t²í struktura jako nap°. v algoritmu Growing Grid [11]) do uº £áste£n¥ nau£ené neuronové sít¥ tak, aby se sí´ zp°es¬ovala. Sí´ tak postupn¥ roste a s ní se i tvo°í struktura mapy, dokud nedosáhne ur£ité velikosti nebo dokud se nenaplní jinak de novaná ukon£ovací podmínka. Po£áte£ní nastavení struktury sít¥ tak v·bec není pot°eba, protoºe se sí´ neu£í jen pozici neuron· (váhové vektory), ale i svojí strukturu. Zajímavé porovnání mezi rostoucí a nerostoucí neuronovou sítí nap°. ukázal Dr. Bernd Fritzke v [10], kde porovnával vý²e zmín¥ný algoritmus Kohonen Feature Map (KFM) a algoritmus Growing Cell Structures (GCS), který sám navrhl [9]. Zjednodu²en¥ °e£eno se porovnávala schopnost map modelovat r·zné rozloºení pravd¥podobnosti v ohrani£eném prostoru.
2.2.
ROSTOUCÍ NEURONOVÉ SÍT
(a) Growing Grid
5
(b) GCS
(c) GNG
Obrázek 2.2: Porovnání výsledk· t°í r·zných rostoucích neuronových sítí. Zleva: Growing Grid, Growing Cell Structures, Growing Neural Gas. Zdroj: [13]
Výsledek byl takový, ºe KFM dosahovalo lep²ích výsledk· jen v p°ípad¥, kde se modelovalo uniformní rozloºení pravd¥podobnosti v celém prostoru. V ostatních p°ípadech, kde byla pravd¥podobnost rozloºena v prostoru r·zn¥, byla sí´ jednodu²e omezena po£áte£ním nastavením struktury, kdeºto GCS strukturu vytvá°el aº podle modelovaného prostoru.
Obrázek 2.3: Výsledky porovnání z [10]. T°i r·zná rozloºení pravd¥podobnosti. Siln¥ ohrani£ené £ásti jsou místa, kde je uniformní rozloºen pravd¥podobnosti, zbytek prostoru má nulovou hustotu pravd¥podobnosti. Horní °ádek je adaptace KFM a spodní °ádek GCS. Zdroj: [10]
6
KAPITOLA 2.
2.3
SAMOORGANIZUJÍCÍ SE NEURONOVÉ SÍT
GSRM
Algoritmus Growing Self-reconstruction Maps (GSRM) spadá mezi samoorganizující se rostoucí neuronové sít¥ a je zaloºen na algoritmu Growing Neural Gas (GNG), který navrhl B. Fritzke [12]. V algoritmu GNG se, tak jako v ostatních rostoucích neuronových sítích, st°ídá fáze u£ení s fází p°idávání uzl· do sít¥. Fáze u£ení má vºdy více cykl·. V kaºdém cyklu se propojí hranou dva neurony, které jsou nejblíºe aktivnímu vstupnímu signálu, poté se vít¥zný uzel a jeho sousedé posunou sm¥rem ke vstupnímu signálu a nakonec se odstraní zastaralé hrany (hrany, které jsou v map¥ uº p°íli² dlouho a nebyly dlouho aktivovány) spole£n¥ s neurony, které zbyly nepropojeny. Ve fázi p°idávání uzl·, se vytvo°í nový neuron v míst¥, ve kterém docházelo k nejv¥t²ímu pohybu neuron· v p°edcházejících cyklech u£ení, a propojí se se zbytkem mapy. To v²e se opakuje sí´ roste, dokud není napln¥na ukon£ovací podmínka. Tento algoritmus byl pouºit pro rekonstrukci povrchu 3D objektu nap°. v [5]. Bohuºel tak, jak je sí´ GNG navrhnuta, nedokáºe sama o sob¥ nést informace o plo²e, pouze o sousednosti neuron·. V [5] proto pouºívají za prvé preprocesing vstupních dat, který je nutný k tomu, aby se vyt¥ºilo více informace ze vstupní mnoºiny nestrukturovaných bod· v prostoru, neº je jejich poloha. Za druhé je pot°eba kone£ný postprocesing sít¥, p°i kterém se z neuronové sít¥ musí je²t¥ vytvo°it povrch 3D objektu. Neuronová sí´ GSRM je navrºena tak, aby informaci o plo²e nesla sama o sob¥ a byla schopna se ji nau£it p°ímo ze vstupních dat. Sí´ GSRM obsahuje krom¥ uzl· (neuron·) a hran spojující uzly, také informaci o trojúhelníkových plo²kách ty jsou ohrani£ené trojicí uzl· a trojicí hran. Tím sí´ získala prost°edek, jak reprezentovat plochu a m·ºe tedy vytvá°et povrch 3D objektu uº b¥hem u£ení není pot°eba ºádný preprocesing, který by získával více informací ze syrových dat, ani ºádný postprocesing, který by z neuronové sít¥ je²t¥ musel vytvá°et kompletn¥ celou plochu povrchu. Postprocesing, který byl navrºen pro algoritmus GSRM (popsaný v podkapitole 3.3), uº jen dotvá°í rekonstruovaný povrch na základ¥ adaptované neuronové sít¥, kde je povrch rekonstruován jen £áste£n¥, ale obsahuje jiº dostatek informace na jeho dokon£ení. Detailní popis algoritmu je uveden ve 3. kapitole.
Kapitola 3 Popis algoritmu GSRM Algoritmus GSRM lze rozd¥lit na t°i £ásti. První je u£ení (nebo také adaptace) neuronové sít¥, druhá je vkládání nových uzl· a poslední je postprocesing. První dv¥ £ásti jsou v £lánku [19] dob°e popsány, bohuºel ta poslední uº tak dob°e popsána není, respektive implementace podle popisu zdaleka nedosahuje pot°ebných výsledk·. Proto byla vyvinuta vlastní implementace postprocesingu. Fáze u£ení spo£ívá v adaptaci sít¥ na vstup tak, aby mapa s aktuálním po£tem p°ítomných uzl· co nejlépe modelovala povrch 3D objektu. To zahrnuje za prvé posun uzl· na jejich správné pozice v prostoru, £ímº je modelován tvar objektu. Za druhé je to u£ení se topologie povrchu. Neuronová sí´ tak musí rozhodnout, které uzly spolu sousedí, mezi kterými uzly lze vytvo°it plochu. Sousednost uzl· je ve výstupní map¥ reprezentována hranami, které sousední uzly spojují a plocha je sloºena z navazujících trojúhelníkových plo²ek. Plo²ky jsou tedy ohrani£eny trojicí uzl·, ale také trojicí hran. Druhá fáze, vkládání nových uzl·, je fáze, kdy neuronová sí´ roste. Zp°es¬uje se tak výsledek, protoºe mapa pracuje s vy²²ím rozli²ením. ím více uzl· mapa obsahuje, tím p°esn¥ji lze modelovat jednotlivé detaily rekonstruovaného objektu. Pokud v²ak mapa obsahuje p°íli² mnoho uzl·, prodluºuje se doba pot°ebná pro rekonstrukci a dokonce m·ºe dojít k tomu, ºe se sníºí schopnost sít¥ rekonstruovat p°esn¥ detaily objektu. Tato situace m·ºe nastat, pokud se po£et uzl· v map¥ blíºí po£tu bod· rekonstruovaného objektu (nebo ho p°evy²uje). V tom p°ípad¥ se v n¥kterých £ástech mapy hromadí uzly, které nejsou v·bec aktivovány a zastarávají nejsou k rekonstrukci vyuºívány, p°estoºe jsou v map¥ zapojeny. Dochází tak k p°eu£ení sít¥. Nové uzly se vºdy vkládají na místa, kde b¥hem p°edchozího u£ení docházelo k nejv¥t²ím chybám, kde se nejvíce poloha uzl· li²ila od jejich správné polohy. Tím neuronová sí´ identi kuje místa v objektu, na které je pot°eba se p°i rekonstrukci více soust°edit, místa, kde je pot°eba zvý²it úrove¬ rozli²ení, protoºe aktuální rozli²ení nedovoluje detailn¥j²í vykreslení rysu objektu. Poslední fáze (postprocesing) slouºí ke zkvalitn¥ní zrekonstruovaného povrchu. To znamená, ºe odstraní takové £ásti mapy, které neformují plochu, a také £ásti plochy, které jsou evidentn¥ chybn¥ rozpoznány (nap°. kdyº spolu dv¥ sousedící plo²ky svírají velmi malý úhel). Ta nejpodstatn¥j²í £ást postprocesingu ale spo£ívá v triangulaci povrchu tam, kde toho p°edchozí dv¥ fáze nebyly schopné. Taková místa mapy jsou správn¥ adaptována v tom smyslu, ºe
7
8
KAPITOLA 3.
POPIS ALGORITMU GSRM
byla správn¥ nalezena sousednost uzl· (jejich propojení hranami), ale chybí v t¥ch místech vytvo°ené plo²ky. Algoritmus jako celek probíhá tak, ºe po inicializaci mapy se nejd°íve provádí n¥kolik cykl· adaptace mapy, následn¥ p°idání nového uzlu do mapy, poté op¥t n¥kolik cykl· adaptace, atd. Jakmile je spln¥no ukon£ovacího kritérium (obvykle po£et uzl· v map¥ úrove¬ rozli²ení mapy), vstupuje se do fáze postprocesingu, kde se struktura mapy dokon£í.
3.1
Struktura mapy
Výstupní mapa (sí´) generovaná algoritmem GSRM je sloºena z uzl·, hran a trojúhelníkových plo²ek. Trojúhelníkové plo²ky jsou ohrani£eny hranami, které propojují uzly mezi sebou. Uzly mají svoji polohu v prostoru a ur£ují tak celkový tvar 3D mapy.
3.1.1
Uzel
Uzel je základní stavební jednotka mapy. V tomto textu budou uzly vºdy ozna£eny písmenem
n,
p°ípadn¥ s indexem, nap°.:
ni , n1 .
Poloha uzlu v prostoru je ur£ena jeho váhovým vekto-
rem, který bude ozna£ován písmenem
w ~,
aby bylo z°ejmé, ºe se jedná o vektor, a indexem
odpovídajícím p°íslu²nému uzlu, tedy nap°íklad
w ~ n1
nebo
w ~ ni .
Uzly jsou v map¥ spojovány hranami. Za sousedy budou ozna£ovány takové uzly, které jsou spojeny hranou, a mnoºina soused· uzlu bude ozna£ována velkým písmenem xem odpovídajícím uzlu, nap°. mnoºina soused· uzlu
n1
bude ozna£ena
N
s inde-
Nn1 .
Kaºdý uzel má také p°i°azen chybový £íta£, který ur£uje odchylku od správné polohy. Takovýto £íta£ bude ozna£ován velkým písmenem uzlu, tedy nap°íklad
3.1.2
En1
nebo
E
s indexem odpovídajícím p°íslu²nému
Eni .
Hrana e s indexem odpovídajícím ozna£ena en1 n2 .
Hrana spojuje práv¥ dva r·zné uzly. Bude ozna£ována písmenem dvojici spojených uzl·, nap°. hrana spojující uzly
n1
a
n2
bude
Kaºdý uzel má také p°i°azeno £íslo, které odpovídá stá°í dané hrany. Toto £íslo bude ozna£ováno jako
agee ,
kde index ozna£uje p°íslu²nou hranu. Stá°í hrany je p°irozené £íslo a
platí u n¥j, ºe £ím vy²²í je £íslo, tím star²í je hrana.
3.1.3
Trojúhelníková plo²ka
Kaºdá trojúhelníková plo²ka je vºdy ohrani£ena trojicí r·zných hran a tudíº i trojicí r·zných uzl·. Tyto hrani£ní hrany pak lze ozna£it za sousedy plo²ky a naopak. Plo²ka m·ºe na kaºdé ze svých hrani£ních hran sousedit maximáln¥ s jednou dal²í plo²kou. Jinými slovy to znamená, ºe kaºdá hrana m·ºe být hrani£ní pro maximáln¥ dv¥ r·zné plo²ky.
3.2.
STAVBA MAPY
3.2
9
Stavba mapy
Algoritmus poºaduje na vstupu mnoºinu sou°adnic bod· v prostoru, z kterých se má zrekonstruovat povrch objektu. Tyto trojice vstupních sou°adnic budou dále nazývány vstupními signály a ozna£ovány symbolem
ξ~.
Vstupní parametry algoritmu jsou následující:
• εb
koe cient u£ení vít¥zného uzlu
• εn
koe cient u£ení sousedních uzl· vít¥zného uzlu
• λ
po£et u£ících krok·, b¥hem nichº se nep°idává ºádný nový uzel do sít¥
• β
koe cient sniºování £íta£· chyb pro v²echny uzly (hodnota mezi 0 a 1)
• α
koe cient sniºování £íta£· chyb pro uzly mezi které byl p°idán nový uzel (hodnota
mezi 0 a 1)
• agemax • nv
mez stá°í hrany, nad kterou je hrana povaºována za zastaralou
ukon£ovací kritérium, obvykle po£et uzl· ve výstupní map¥
Bliº²í popis typických hodnot parametr· je uveden v podkapitole 3.4. Algoritmus je popsán v deseti krocích. Jak jiº bylo zmín¥no vý²e, hlavní dv¥ £ásti jsou fáze u£ení (adaptace) a fáze vytvá°ení nových uzl·. Fáze u£ení odpovídá bod·m 2. aº 7., fáze vytvá°ení nových uzl· pak bodu 8.
Algoritmus GSRM 1. Inicializuj výstupní mapu
A t°emi uzly s náhodn¥ zvolenými váhovými vektory a £íta£i
chyb inicializovanými na nulu. 2. Náhodn¥ vyber jeden vstupní signál
ξ~ z
mnoºiny vstupních signál·.
3. Najdi první (n1 ) a druhý (n2 ) nejbliº²í uzel z výstupní mapy
ξ~ (tzn.
A
ke vstupnímu signálu
vít¥ze):
~ ≤ kw ~ ∀ni ∈ A, kw ~ n1 − ξk ~ ni − ξk, ~ ≤ kw ~ ∀ni ∈ A − {n1 }. kw ~ n2 − ξk ~ ni − ξk,
(3.1) (3.2)
4. Uprav chybový £íta£ prvního vít¥zného uzlu o kvadrát jeho vzdálenosti od vstupního signálu:
~ En1 = En1 + kw ~ n1 − ξk. 5. Vytvo° spojení mezi dvojicí vít¥zných uzl· (n1 , 5.1 Pokud neexistuje hrana spojující
n1
a
n2 :
n2 )
takto:
(3.3)
10
KAPITOLA 3.
POPIS ALGORITMU GSRM
n1
5.1.1 Odstra¬ v²echny hrany spojující spole£né sousedy jsou hranou spojeny jak s
n1
tak s
n2 ).
a
n2
(tedy uzly, které
Zárove¬ s t¥mito hranami je nutné
odstranit i plo²ky, které jsou s nimi spojeny. Na obrázku p°echod z 3.1(a) na 3.1(b). 5.1.1 Vytvo°
novou
na nula (ageen 5.1.1
hranu
n1
spojující
a
n2
(en1 n2 )
a
nastav
jí
stá°í
= 0). Vytvo° plo²ky mezi n1 , n2 a v²emi jejich spole£nými sousedy (zobrazeno na ob1 n2
rázku 3.1(c) spole£n¥ s vytvo°ením nové hrany).
(a)
(b)
(c)
Obrázek 3.1: Propojení dvou uzl·, které jsou nejblíºe vstupnímu signálu (n1 , nejsou propojené a jejich spole£ní sousedé (na ,
5.2 Pokud
jiº
na nula (ageen
hrana 1 n2
n1
mezi
= 0).
nb )
a
n2 ),
pokud
její
stá°í
propojení jsou.
n2
existuje,
nastav
jen
Tím je zaji²t¥no, ºe tato hrana nebude v nejbliº²í dob¥
odstran¥na. Zárove¬ vytvo° plo²ky mezi 6. Posu¬ vít¥zný uzel
n1
n1
a
n2
a v²emi jejich spole£nými sousedy.
a v²echny jeho sousedy sm¥rem k vstupnímu signálu:
w ~ n1 = w ~ n1 + εb (ξ~ − w ~ n1 ), w ~ ni = w ~ ni + εn (ξ~ − w ~ ni ), ∀ni ∈ Nn1 , kde
Nn1
je mnoºina v²ech soused·
7. Zvy² stá°í hran vycházejících z
n1
(3.4) (3.5)
n1 . o jedna:
ageen1 ni = ageen1 ni + 1, ∀ni ∈ Nn1 .
(3.6)
Odstra¬ v²echny hrany, a s nimi spojené plo²ky, kterým se takto zvý²í stá°í nad hranici
agemax ,
takto:
7.1 Odstra¬ v²echny plo²ky sousedící se zastaralou hranou. 7.2 Odstra¬ hranu samotnou. 7.3 Vznikne-li tím uzel, který není spojen s ºádnou hranou, odstra¬ ho také. 8. Je-li celkový po£et dosud na£tených vstupních signál· roven celo£íselnému násobku parametru
λ,
vloº nový uzel do mapy:
3.2.
STAVBA MAPY
11
8.1 Najdi uzel s nejvy²²í hodnotou £íta£e chyb (ozna£me ho jako sousední uzel (uzel, který je s ozna£me ho jako
nq
nq ),
k n¥mu vyber
spojený hranou), jeº má nejvy²²í £íta£ chyb (a
nf ): Enq ≥ Eni , ∀ni ∈ A, Enf ≥ Eni , ∀ni ∈ Nnq .
8.2 Odstra¬ hranu spojující 8.3 Sniº £íta£e chyb uzl·
nq
nq a
a
nf
(3.7) (3.8)
i s plo²kami, se kterými sousedí.
nf : Enq = αEnq , Enf = αEnf .
8.4 Vloº nový uzel (ozna£me ho
nr )
(3.9) (3.10)
do mapy p°ímo mezi uzly
nq
a
nf
a nastav mu
£íta£ chyb jako pr·m¥r jejich £íta£· chyb:
8.5 Vytvo° hrany spojující uzel
nr
~ nf w ~ nq + w , 2 Enq + Enf = . 2
w ~ nr =
(3.11)
Enr
(3.12)
s uzly
nq
a
nf .
(a)
(b)
Obrázek 3.2: Na obrázku (a) stav p°ed p°idáním nového uzlu
nr .
Na obrázku (b) stav s uº
p°idaným novým uzlem.
9. Sniº hodnotu £íta£· chyb v²ech uzl· koe cientem
β:
En = βEn , ∀n ∈ A. 10. Pokud je spln¥na ukon£ovací podmínka
nv ),
nv
(3.13)
(tedy obvykle po£et uzl· v map¥ je roven
p°ejdi k postprocesingu. Jinak pokra£uj bodem 2.
Postprocesing bude detailn¥ vysv¥tlen v následující podkapitole.
12
KAPITOLA 3.
POPIS ALGORITMU GSRM
(a) Vstupní body
(b) 10 uzl·
(c) 100 uzl·
(d) 500 uzl·
(e) 1000 uzl·
(f ) 5000 uzl·
Obrázek 3.3: Ukázka rekonstrukce 3D objektu ze vstupních bod· - (a). Na obrázcích (b) aº (f ) lze vid¥t, jak neuronová sí´ roste a zp°es¬uje se.
3.3
Postprocesing
Smyslem postprocesingu je za prvé zkvalitn¥ní vygenerované mapy a za druhé dokon£ení povrchu, který p°edchozími kroky nebyl zrekonstruován v podob¥ trojúhelníkových plo²ek. Zkvalitn¥ní mapy se provádí p°edev²ím proto, aby se na ní snadn¥ji provád¥la kone£ná triangulace. Zárove¬ se triangulace provádí tak, aby spl¬ovala v²echny poºadavky, které jsou na mapu kladeny b¥hem zkvalit¬ování. V následujících podkapitolách bude popsán mechanizmus zkvalit¬ování mapy a dokon£ení triangulace mapy. V poslední podkapitole pak budou tyto dva kroky shrnuty a spojeny do jednoho algoritmu. Zkvalit¬ovaní mapy a dokon£ování triangulace se totiº st°ídá v n¥kolika fázích, aby byl výsledek postprocesingu co nejlep²í.
3.3.1
Zkvalitn¥ní mapy
Po dokon£ení u£ení neuronové sít¥ se m·ºe mapa nacházet ve stavu, kde obsahuje trojúhelníkové
3.3.
POSTPROCESING
13
plo²ky, které nejsou úpln¥ ideální. Dá se °íci, ºe nejideáln¥j²í by bylo, kdyby v²echny plo²ky byly rovnostranné trojúhelníky. Úplný opak jsou zase tupoúhlé trojúhelníky, jejichº tupý úhel se blíºí
π.
Dal²í stav plo²ek, který bude povaºován za nekorektní, je, pokud úhel, který
spolu svírají dv¥ plo²ky p°es spole£nou hranu, bude men²í neº stanovená mez. P°íli² malý úhel mezi plo²kami totiº tém¥° ur£it¥ zna£í ²patnou adaptaci neuronové sít¥. Hrany lze zkvalit¬ovat dvojím zp·sobem. V uzlech, ve kterých se propojují pouze dv¥ hrany, lze uvaºovat o slou£ení hran a to tehdy, pokud spolu svírají úhel blíºící se
π . Z mapy je
také pot°eba odstra¬ovat hrany, které nejsou schopny tvo°it trojúhelníkové plo²ky, pon¥vadº cílem rekonstrukce je zrekonstruovaný povrch objektu a samotné hrany nemají ºádný význam pro výsledek rekonstrukce.
3.3.1.1 Trojúhelníkové plo²ky Jak jiº bylo popsáno vý²e, b¥hem zkvalit¬ování mapy jsou trojúhelníkové plo²ky pouze odstra¬ovány ty, co jsou povaºovány za nekorektní. Za nekorektní plo²ku je povaºována taková, u které je úhel v jednom z jejích vrchol· 3 π ). Odstra¬ují se tak vy²²í neº de novaná mez φv (její hodnota bude typicky vy²²í neº 4 plo²ky, které mají obvykle malou plochu a v jednom z vrchol· trojúhelníku je úhel mnohem v¥t²í neº ve zbylých dvou zdaleka se neblíºí ideálnímu stavu, kde jsou trojúhelníkové plo²ky rovnostranné. Odstra¬ovaní t¥chto plo²ek se provádí jednodu²e tak, ºe se prochází v²echny plo²ky vytvo°ené v map¥, u kaºdé se zkontrolují úhly ve v²ech t°ech vrcholech. Pokud n¥která plo²ka nevyhovuje omezení, je odstran¥na.
Za nekorektní je také povaºována plo²ka svírající s n¥kterou ze svých sousedních plo²ek 1 úhel men²í neº je stanovená mez θf (hodnota bude typicky niº²í neº je π ). 4 Odstra¬ování probíhá tak, ºe se prochází v²echny hrany v map¥. Pokud s n¥jakou hranou sousedí práv¥ dv¥ plo²ky, dojde ke kontrole. Spo£ítá se úhel
θ
mezi plo²kami:
~b = w ~ n2 − w ~ n1 , ~u = w ~ n3 − w ~ n1 , ~v = w ~ n4 − w ~ n1 , (~b × ~u) · (~b × ~v ) , cos θ = k~b × ~ukk~b × ~v k kde
(3.14) (3.15) (3.16) (3.17)
n1 a n2 jsou uzly, které spojuje hrana spole£ná ob¥ma plo²kám, n3 a n4 jsou pak zbývající ~b a ~u a mezi ~b a ~v musí být ve stejném
vrcholy první a druhé plo²ky. Vektorový sou£in mezi
po°adí, aby výsledný úhel opravdu odpovídal úhlu, který plo²ky svírají. Tímto zp·sobem lze odhalit dvojici plo²ek, které jsou ob¥ nekorektní. Otázka zní, kterou z nich odstranit. Sta£í totiº odstranit jednu, druhá uº pak bude automaticky korektní. V map¥ bude ponechána ta plo²ka, která je více propojená se zbytkem mapy. To se zjistí jednodu²e tak, ºe se spo£ítá, s kolika dal²ími plo²kami plo²ka sousedí (s kolika sdílí spole£nou hranu). Pokud ob¥ plo²ky sousedí se stejným po£tem dal²ích plo²ek, pak se odstraní ta, která má men²í plochu.
14
KAPITOLA 3.
POPIS ALGORITMU GSRM
3.3.1.2 Hrany B¥hem postprocesingu se hrany v map¥ bu¤ spojují, nebo se odstra¬ují. Odstra¬ují se ty, které nemohou slouºit k vytvo°ení plo²ky, a slu£ují ty, které na sebe p°ímo navazují p°es uzel, ze kterého nevychází ºádná dal²í hrana, a které spolu svírají úhel blízký p°ímému úhlu lze tak tuto dvojici hran zjednodu²it nahrazením za jedinou hranu p°i minimální ztrát¥ informace v map¥ obsaºené. Zkvalit¬ování mapy za£íná odstra¬ováním hran, které jsou do mapy p°ipojeny jednou stranou, neexistuje tedy zp·sob, jak by v·bec mohly ohrani£it plo²ku. Odstra¬ování lze provést tak, ºe se prochází v²echny uzly mapy. Pokud uzel sousedí jen s jednou hranou, znamená to, ºe hrana je p°ipojena do mapy jen jednou stranou (tou druhou neº je tento uzel). Taková hrana se odstraní, a pon¥vadº se odstranila jediná hrana navazující na tento uzel, odstraní se i uzel. Takto se prochází uzly stále dokola, dokud dochází k n¥jakým zm¥nám v síti. Odstran¥ním jedné hrany totiº m·ºe vzniknout dal²í, op¥t málo propojená se zbytkem mapy.
(a)
(b)
(c)
Obrázek 3.4: P°íklad odstran¥ní hran p°ipojených do mapy jen jednou stranou.
Následn¥ je moºné provést slu£ování hran. Dv¥ hrany lze slou£it do jedné tehdy, pokud z uzlu, ve kterém jsou propojené, nevychází ºádná dal²í hrana krom¥ t¥chto dvou. Dále je nutné, aby spolu tyto dv¥ hrany svíraly úhel blízký
φe ,
π.
Stanoví se tedy minimální úhel 9 π a 10
který musí hrany svírat, aby mohly být slou£eny (typicky bude hodnota meze
vy²²í). Spojování probíhá tak, ºe se postupn¥ prochází v²echny uzly. Pokud z uzlu vychází práv¥ dv¥ hrany a úhel, který hrany svírají, je v¥t²í neº
φe ,
dochází k jejich slou£ení. Slou£ení
ena nb a enb nc , vytvo°í se hrana ena nc ). Poté se odstraní staré hrany spole£n¥ s jejich spole£ným uzlem (podle p°edcházejícího p°íkladu se tedy odstraní hrany ena nb a enb nc a uzel nb ).
se provede tak, ºe se hranou propojí zbylé dva uzly (pokud se nap°. slu£ují hrany
Poslední £ást odstra¬ování nepouºitelných hran je následující. Hrana, kterou jiº nelze nijak ohrani£it plo²ku, je také taková, která by byla nucena k ohrani£ení pouºít hranu, která uº ohrani£uje dv¥ plo²ky. Poznat nepouºitelnou hranu lze následovn¥: zkontrolují se oba koncové uzly hrany. Pokud z n¥kterého uzlu vychází pouze hrany (vyjma kontrolované), které jiº sousedí se dv¥ma
3.3.
POSTPROCESING
15
plo²kami, pak je jisté, ºe touto hranou nelze jiº ºádnou plo²ku ohrani£it. Musela by se k tomu pouºít totiº jedna ze sousedních hran ty jsou v²ak uº pln¥ obsazeny. Odstra¬ování pak lze jednodu²e naimplementovat procházením v²ech uzl·. V nich se zkontroluje vý²e popsaná podmínka a odstraní nepouºitelné hrany.
(a)
(b)
(c)
Obrázek 3.5: P°íklad odstran¥ní p°í£ných hran, které nemohou tvo°it trojúhelníkovou plo²ku, a následné vytvo°ení hran v místech, kde je to díky tomuto kroku moºné.
3.3.2
Dokon£ení triangulace mapy
Po fázi stavby mapy je mapa ve stavu, kde není povrch zcela zrekonstruován. Povrch obsahuje díry, které nejsou vytriangulované. Povrch je ale rekonstruován sítí hran v t¥chto místech je de nována sousednost uzl·. To ºe taková místa nejsou vytriangulována je dáno tím, ºe p°i u£ení neuronové sít¥ jsou zastaralé hrany odstra¬ovány zárove¬ se sousedícími plo²kami. Nové plo²ky jsou naopak do mapy p°idávány jen tam, kde hrany formují trojúhelníky. B¥hem u£ení se v²ak hrany nespojují jen do trojúhelník·, úkolem triangulace b¥hem postprocesingu pak je vytriangulování zbytku mapy, vychází se p°itom z jiº nau£ené topologie sít¥.
P°i triangulaci se vychází z p°edpokladu, ºe sí´ má správn¥ nau£enou sousednost uzl· i povrch (triangulaci sít¥). Triangulace v postprocesingu tak postupuje od míst v síti, kde je jiº povrch zrekonstruován, ve sm¥ru nau£ených hran. Nové trojúhelníkové plo²ky se vytvá°í jen tam, kde je topologií jednozna£n¥ dáno, jak by taková plo²ka m¥la vypadat (v tom míst¥ neexistuje jiná moºnost, jak plo²ku vytvo°it). Automaticky se p°itom p°edpokládá, ºe pokud zárove¬ spl¬uje nároky na kvalitu plo²ky, plo²ka do mapy pat°í a je vytvo°ena.
3.3.2.1 De nice omezení Omezení, která musí nov¥ vytvo°ená plo²ka spl¬ovat, jsou stejná, jako jsou popsána v 3.3.1.1 a n¥která dal²í, která zajistí, ºe bude postprocesing respektovat vlastnosti, které mapa získala b¥hem u£ení. V 3.3.1.1 byly de novány tyto vlastnosti, které musí kaºdá plo²ka, tedy i ta vytvo°ená b¥hem postprocesingu, spl¬ovat: 1. Úhel svíraný ve v²ech vrcholech trojúhelníku musí být men²í neº de novaná mez
φv .
16
KAPITOLA 3.
POPIS ALGORITMU GSRM
2. Úhel svíraný na kaºdé hran¥ se sousední plo²kou musí být v¥t²í neº
θf .
Nov¥ vytvo°ené plo²ky navíc nesmí být p°íli² velké ani p°íli² malé, aby se postprocesingem nedeformovala jiº nau£ená mapa. Ozna£íme-li velikost plochy nejmen²í trojúhelníkové plo²ky v map¥ p°ed postprocesingem
Amin
a velikost plochy nejv¥t²í plo²ky
Amax ,
pak musí
být velikost plochy nov¥ vytvo°ené plo²ky b¥hem postprocesingu mezi t¥mito krajními hodnotami:
Amin ≤ Af ≤ Amax , kde
Af
(3.18)
je velikost plochy nov¥ vytvo°ené plo²ky.
3.3.2.2 Vytvá°ení nových plo²ek Místa, kde je topologií sít¥ dáno, ºe by tam mohla být plo²ka vytvo°ena, a kde m·ºe být vytvo°ena jen jediným zp·sobem, jsou ta, kde z uzlu vychází jediná dvojice hran, která by mohla být na opa£ném konci uzav°ená dal²í hranou a tak tvo°it trojúhelník (viz. obr. 3.6). Pokud by z uzlu vycházelo více moºných dvojic schopných uzav°ením na opa£ném konci vytvo°it trojúhelník, není jednozna£n¥ dáno, který z trojúhelníku je ten správný. V tom p°ípad¥ se ºádná plo²ka nevytvá°í. Triangulaci tedy lze provést tak, ºe se postupn¥ prochází v²echny uzly mapy. U kaºdého uzlu se spo£ítá, kolik hran, které jsou hrani£ní pro jednu nebo mén¥ plo²ek, z n¥ho vychází. Pokud vychází práv¥ dv¥, je jednozna£n¥ dáno, jak lze novou plo²ku vytvo°it (viz. obr. 3.6). Následn¥ se zkontroluje, jestli by nov¥ vytvo°ená plo²ka spl¬ovala vý²e de novaná omezení. Pokud by je spl¬ovala, vytvo°í se nová trojúhelníková plo²ka spole£n¥ s nezbytnými hranami (pokud je mapa jiº neobsahuje). Uzly v map¥ se prochází stále dokola, dokud v map¥ dochází ke zm¥nám.
(a)
(b)
(c)
(d)
Obrázek 3.6: Na obrázcích (a) a (b) jsou vid¥t struktury, ve které lze vytvo°it trojúhelníky jen jedním zp·sobem. Na obrázcích (c) a (d) pak struktury, ve kterých není triangulace jednozna£n¥ dána.
Triangulace se tak ²í°í od jiº vytvo°ených plo²ek, protoºe pokud z uzlu vychází práv¥ dv¥ hrany schopné ohrani£it plo²ku, pak v¥t²inou kaºdá z hran jiº jednu plo²ku ohrani£uje.
3.3.
POSTPROCESING
17
(a)
(b)
(c)
(d)
(e)
(f )
Obrázek 3.7: Ukázka dokon£ení triangulace £ásti mapy.
3.3.3
Postprocesing jako celek
Postprocesing se provádí ve £ty°ech fázích. V první fázi se nejd°íve provedou v²echny kroky ke zkvalitn¥ní mapy. To znamená odstran¥ní nekorektních plo²ek, odstran¥ní nekorektních hran a slou£ení hran, které slou£it lze. Poté se provede triangulace. Druhá fáze za£íná odstran¥ním nekorektních hran. B¥hem p°edchozí triangulace se z n¥kterých hran mohly stát nekorektní hrany. Mohlo totiº dojít k tomu, ºe po triangulaci z n¥kterého uzlu vychází jen jediná hrana, která by mohl ohrani£ovat plo²ku. Taková hrana je nekorektní, a proto ji lze odstranit. Nekorektní plo²ky vzniknout nemohly, a proto se ºádná kontrola plo²ek neprovádí. Druhá fáze kon£í dal²í triangulací. (Na obrázku 3.5 lze vid¥t, jak odstran¥ní hran m·ºe pomoci dal²í triangulaci.) Ve t°etí fázi se nejd°íve odstraní v²echny trojúhelníkové plo²ky, které nejsou nijak zastav¥ny do mapy. Takové plo²ky se poznají tak, ºe ºádná z ohrani£ujících hran neohrani£uje ºádnou jinou plo²ku. Následuje odstran¥ní v²ech hran, které neohrani£ují ºádnou plo²ku, a odstran¥ní uzl·, ze kterých nevychází ºádná hrana. Výstup rekonstrukce má být povrch, osamocené hrany a uzly tak nemají pro výstup ºádný význam, a proto se odstraní. Na konci t°etí fáze se op¥t provede triangulace. V poslední, £tvrté fázi se uº jen naleznou trojice propojených hran, kde kaºdá z hran ohrani£uje práv¥ jednu plo²ku. Mezi t¥mito hranami se vytvo°í nová plo²ka bez jakýchkoli kontrol. Jedná se totiº o místa, kde má zrekonstruovaný povrch jen jednu trojúhelníkovou díru. Nej£ast¥ji to bývají malé trojúhelníky, ve kterých se b¥hem p°edchozí triangulace nevytvo°í plo²ka, protoºe by nespl¬ovala omezení na minimální velikost plo²ky. Nemá ale smysl takovou plo²ku nevytvo°it, kdyº se jí zacelí zrekonstruovaný povrch.
18
KAPITOLA 3.
3.4
POPIS ALGORITMU GSRM
Parametry algoritmu
V této podkapitole bude popsán význam parametr·, které jsou pouºity b¥hem stavby mapy a b¥hem postprocesingu, a jejich povolené a typické hodnoty.
3.4.1
Parametry εb a εn
Tyto parametry slouºí k u£ení polohy vít¥zného uzlu a jeho soused· b¥hem 6. kroku algoritmu. V kaºdém cyklu algoritmu se nalezne nejbliº²í uzel ke vstupnímu signálu a ten se posune spole£n¥ s jeho sousedy sm¥rem ke vstupnímu signálu podle rovnic 3.4 a 3.5. Vzdálenost, o kterou se uzly posunou, jsou tedy vzdálenosti od vstupního signálu násobené
εb ,
parametrem
respektive
εn .
Hodnoty parametr· by nem¥ly být p°íli² vysoké, aby poloha uzl· v síti neoscilovala okolo správné hodnoty, ale aby se ke správné hodnot¥ blíºila postupn¥. P°itom by hodnota být men²í neº hodnota
εb ,
εn
m¥la
protoºe vít¥zný uzel by se m¥l ke vstupnímu signálu p°iblíºit více
neº jeho sousedé. Byly pouºity hodnoty okolo
3.4.2
0, 05
pro parametr
εb
a
0, 0006
pro parametr
εn .
Parametr λ
Tento parametr ur£uje, po£et cykl· u£ení mezi fázemi, kdy se p°idává nový uzel do mapy. T¥chto cykl· by nem¥lo být málo, aby se sít sta£ila nau£it topologii sít¥, ale nesmí jich být zase p°íli² mnoho, aby se zbyte£n¥ neprodluºovala doba rekonstrukce. Hodnota je zárove¬ závislá na velikosti mnoºiny vstupních bod·. Pokud je totiº malá, je zbyte£né,
aby bylo
t¥chto cykl· p°íli² mnoho. Na druhou stranu, pokud je cílová velikost výstupní mapy malá, je pot°eba nastavit tento parametr dostate£n¥ vysoko, aby se mapa v·bec sta£ila topologii nau£it. V experimentech, které se provád¥ly na mnoºinách od p°ibliºn¥ 40 000 bod· do p°ibliºn¥ 1 000 000 bod·, se osv¥d£ilo pouºívat hodnotu okolo 200.
3.4.3 Parametr
Parametry β a α β
slouºí ke sníºení £íta£· chyb v²ech uzl·. Hodnota £íta£· se tímto parametrem
násobí, proto musí mít hodnotu mezi 0 a 1. Toto sniºování je v algoritmu proto, aby se vyrovnávaly hodnoty £íta£· chyb a nevznikl tak jen úzký okruh uzl·, které mají jeho hodnotu neustále nejvy²²í. Hodnota parametru by m¥la být blízká jedni£ce, protoºe zase není ºádoucí, aby se rozdíly v hodnotách £íta£· úpln¥ stíraly, aby opravdu byly poznat ty uzly, jejichº poloha se od té správné polohy li²í nejvíce (ty, které se v map¥ posouvaly o nejv¥t²í vzdálenosti). Hodnota parametru, která se v experimentech osv¥d£ila, byla 0,9995.
Parametr
α
zase slouºí ke sníºení £íta£· chyb u t¥ch uzl·, mezi kterými byl vytvo°en
nový uzel. Jeho význam spo£ívá v tom, ºe p°idáním nového uzlu se vyrovná nep°esnost
3.5.
HISTORIE REVIZÍ LÁNKU
19
jejich polohy uzel se vkládá do míst, kde docházelo k nejv¥t²ím pohyb·m uzl·, tam kde uzly nebyly schopny zaujmout správnou polohu. Hodnota tohoto parametru by tedy m¥la být niº²í neº hodnota parametru
β . Aplikuje se
totiº v moment¥, kdy se jejich nesprávná poloha kompenzuje p°idáním nového uzlu. Hodnota, která se osv¥d£ila b¥hem experiment·, byla 0,95.
3.4.4
Parametr agemax
Hodnota tohoto parametru ur£uje hranici, od kdy jsou hrany povaºovány za zastaralé a kdy je pot°eba je odstranit. Pokud je hodnota p°íli² nízká, bude odstra¬ováno velké mnoºství hran spole£n¥ se sousedními plo²kami. To zp·sobí, ºe p°estoºe uzly budou mít nau£enou správnou polohu v prostoru, nebude správn¥ nau£ená topologie sít¥ ve smyslu sousednosti uzl· a plo²ek mezi uzly. Pokud je hodnota na druhou stranu p°íli² vysoká z·stanou po skon£ení u£ení v map¥ i hrany, které budou spojovat uzly na opa£ných koncích rekonstruovaného objektu. Sousednost bude nekorektn¥ nau£ená. B¥hem experiment· se ukázalo, ºe tento parametr se nastavuje na správnou hodnotu nejobtíºn¥ji. Osv¥d£ilo se v²ak nastavit ho na hodnotu blízkou hodnot¥ parametru
3.4.5
λ.
Parametry φv , θf a φe
Tyto parametry se pouºívají b¥hem postprocesingu a nastavit jejich hodnotu je asi nejsnaz²í. Parametr
φv
je maximální úhel, který m·ºe být svírán v kterémkoli vrcholu trojúhelní-
kové plo²ky. Pokud je nejideáln¥j²í podoba plo²ek rovnostranné trojúhelníky, nem¥la by být 3 hodnota tohoto parametru niº²í neº π . 4 Parametr
θf
zase °íká, jaký je minimální úhel, který mohou plo²ky svírat mezi sebou. 1 Jeho hodnota vychází z povahy vstupních bod·, ale z°ejm¥ lze °íci, ºe hodnota π bude 4 minimální pro v¥t²inu objekt·. Pokud v²ak bude dop°edu známo, ºe rekonstruovaný objekt obsahuje jen pravoúhlé st¥ny, lze bez úhony hodnotu tohoto parametru zvý²it. Parametr
φe
slouºí k rozeznání hran, které jsou odd¥leny jedním uzlem a lze je slou£it
do jedné hrany, pokud spolu svírají úhel vy²²í neº je tato mez. Jeho hodnota by tedy m¥la 9 π. být velmi blízká π . B¥hem experiment· byla pouºita hodnota 10
3.5
Historie revizí £lánku
Na implementaci algoritmu GSRM jsem za£al pracovat p°ed více neº rokem a p·l, kdy jsem se s vedoucím práce M. Kulichem domluvil na tomto tématu a obdrºel od n¥j aktuální verzi £lánku [19], který m¥l k dispozici k revizi. V £lánku byly prezentovány zajímavé výsledky p°i rekonstrukci 3D objekt·. Mým cílem pak bylo zam¥°it se na jejich moºnou aplikaci v robotice pro mapování 3D prost°edí ze senzorických dat robotu. asem se ukázalo, ºe £lánek nebyl je²t¥ p°ipravený k o ciálnímu vydání a dodnes vydán nebyl. Místo toho byly postupn¥ vydávány jednotlivé revize £lánku a bylo tak pot°eba program podle nich upravovat. V této podkapitole bude popsáno, jak byly vydávány jednotlivé verze £lánku za sebou a jak se podle nich li²ila kvalita rekonstrukce 3D objekt·.
20
KAPITOLA 3.
3.5.1
POPIS ALGORITMU GSRM
První verze £lánku
Algoritmus GSRM byl v první verzi £lánku zna£n¥ odli²ný od verze, která je zde popsaná. V této verzi bylo pot°eba vyhledat trojici nejbliº²ích uzl· vstupnímu signálu, které se navzájem propojily hranami. Odstra¬ování hran také probíhalo rozdíln¥. V poslední verzi £lánku se odstra¬ují zastaralé hrany spole£n¥ se sousedními plo²kami, ale v první verzi se zastaralá hrana odstra¬ovala, aº kdyº s ní nesousedila ºádná plo²ka. Plo²ky pak byly odstra¬ovány, pokud v²echny ohrani£ující hrany byly zastaralé. Dal²í krok, ve kterém se tato verze li²ila od té poslední, je p°idávání nového uzlu. P°i p°idání uzlu se totiº zárove¬ provád¥la triangulace s uzly, mezi kterými byl nový uzel vytvo°en, a jejich spole£nými sousedy. Poslední rozdíl spo£íval v de nici struktury. Hrany totiº mohly ohrani£ovat neomezen¥ plo²ek a nikoli pouze dv¥.
Díky p°ísn¥j²ím podmínkám odstran¥ní hran a plo²ek, docházelo k odstra¬ování mnohem mén¥ £asto a bylo tak pot°eba mít nastaven parametr
agemax
na niº²í hodnotu, aby byla
topologie sít¥ nau£ena p°esn¥ji. Zárove¬ se hrany a plo²ky vytvá°ely £ast¥ji díky zp·sobu, jakým se p°idávaly nové uzly. Nejmarkantn¥j²í rozdíl ale tkv¥l v rozdílu ve struktu°e. Pon¥vadº hrany mohly ohrani£ovat neomezený po£et plo²ek, zrekonstruovaný povrch tak m¥l mnohem sloºit¥j²í strukturu. Výsledná mapa na pohled vypadala mnohem lépe zrekonstruovaná oproti výsledku ze sou£asné verze £lánku. Jednalo se ale vlastn¥ jen o optický klam, protoºe p°i pohledu z vn¥ objektu vypadal povrch perfektn¥ zrekonstruovaný. Doopravdy ale docházelo uvnit° objektu v d¥lení povrchu a povrch rostl dovnit° objektu. Docházelo také ke generování mnohem v¥t²ího po£tu hran a plo²ek, které se r·zn¥ k°íºily a p°ekrývaly. Z vn¥j²ku tak povrch vypadal lépe, ale doopravdy nebyla kvalita zrekonstruovaného povrchu p°íli² dobrá.
3.5.2
Druhá verze £lánku
Druhá verze nep°i²la s velkým zlep²ením. P°ibyl pouze postprocesing, který spo£íval v odstran¥ní plo²ek, které spolu svíraly p°íli² malý úhel (podobn¥, jak je popsáno v postprocesingu k sou£asné verzi). Dal²í krok postprocesingu byl dokon£ení triangulace nevytriangulovaných polygon·. Bohuºel nikde nebylo popsáno, jak takové polygony v map¥ nalézt. Výsledek se tedy p°íli² neli²il od první verze, pon¥vadº stále vznikalo velké mnoºství hran a plo²ek a hlavn¥ proto, ºe hrana mohla ohrani£ovat neomezen¥ plo²ek.
3.5.3
T°etí a zatím poslední verze
Verze £lánku, která je popisována v podkapitole 3.2 uº napravovala mnoho chyb p°edchozích verzí a zárove¬ zjednodu²ovala implementaci. Jsou vyhledávány jen dvojice nejbliº²ích uzl·, hrany jsou odstra¬ovány zárove¬ se sousedícími plo²kami, s novým uzlem se p°idávají pouze dvojice hran spojující nový uzel s dvojicí
3.5.
HISTORIE REVIZÍ LÁNKU
(a)
21
(b)
Obrázek 3.8: Ukázka výstupu algoritmu podle první verze £lánku. Vlevo je pohled na zrekonstruovaný objekt, vpravo pak v¥t²í detail. Z obrázku je vid¥t, ºe je tvo°eno velké mnoºství hran a plo²ek, které se r·zn¥ k°íºí a p°ekrývají a netvo°í tak souvislý povrch.
uzl·, mezi kterými je nový uzel vytvo°en. Nejpodstatn¥j²í rozdíl ale spo£ívá ve struktu°e, kde hrana m·ºe ohrani£ovat maximáln¥ dvojici plo²ek. Výsledný povrch je tak mnohem blíºe tomu, co si pod pojmem povrch p°edstavíme. Na druhou stranu se mnohem £ast¥ji odstra¬ují hrany a plo²ky, takºe ve výsledku je sice správn¥ nau£ená sousednost uzl·, ale povrch je d¥ravý díky nedostatku vytvo°ených plo²ek. Tento problém jsem se pokusil vy°e²it vlastním návrhem postprocesingu, který je popsán v podkapitole 3.3.
V £lánku je také popsán vlastní postprocesing, který spo£ívá v n¥kolika krocích. První krok je topologické u£ení, které spo£ívá v postupném pouºití celé mnoºiny vstupních signál· pro u£ení topologie bez p°idávání nových uzl· a posunu uzl·. Druhý krok pak ve vyhledání v²ech nevytriangulovaných £ty°úhelník·, p¥tiúhelník· a ²estiúhelník·, které se vytriangulují. P°estoºe je v £lánku ukázána úsp¥²ná aplikace postprocesingu, tento úsp¥ch nebylo moºné zreprodukovat. Respektive byl implementován první krok, o kterém je v £lánku napsáno, ºe dokon£í triangulaci tém¥° celého povrch objektu, aº na velmi málo polygon·, které se dotriangulují v druhém kroku postprocesingu. Po implementaci se ale ukázalo, ºe vliv topologického u£ení na mapu není v podstat¥ ºádný. Mapa se po prvním kroku zm¥nila jen málo, díry v povrchu z·staly tém¥° stejné. Druhý krok postprocesingu nebyl v·bec implementován, protoºe nikde v £lánku nebylo popsáno, jak takové souvislé nevytriangulované polygony v map¥ nalézt. Proto byl navrhnut vlastní postprocesing.
22
KAPITOLA 3.
POPIS ALGORITMU GSRM
Kapitola 4 Optimalizace V této kapitole budou popsány optimalizace, které byly provedeny s algoritmem, popsaným ve t°etí kapitole, a vedou k jeho zrychlení. Optimalizace jsou zam¥°eny na £asov¥ nejnáro£n¥j²í £ásti algoritmu. K nejnáro£n¥j²ím operacím bezesporu pat°í hledání nejbliº²ího uzlu ke vstupnímu signálu (krok 3). Provádí se totiº opakovan¥ v kaºdém cyklu algoritmu. Vylep²ení je popsáno v podkapitole 4.1. Dal²í £ást algoritmu, který je £asov¥ náro£ný, a který je popsán v podkapitole 4.2, je 9. krok sniºování £íta£· chyb v²em uzl·m v map¥. Tato operace se provádí také kaºdý cyklus, a proto stojí za vylep²ení. Níºe popsáné optimalizace mají výrazný vliv na rychlost algoritmu. V kapitole 6 jsou uvedeny £asy b¥hu algoritmu s pouºitými optimalizacemi a bez nich.
4.1
Nalezení nejbliº²ího uzlu
Nalezení dvojice nejbliº²ích uzl· ke vstupnímu signálu pat°í k nejdraº²ím operacím celého algoritmu, dochází k n¥mu totiº v kaºdém cyklu algoritmu. Nejjednodu²²í a nejp°ím¥j²í implementace této operace je pouºití lineárního vyhledávání (n¥kdy také nazývané sekven£ní vyhledávání). Takové vyhledávání je v²ak £asov¥ p°íli² náro£né. Pro vyhledávání bod· v prostoru s niº²í neº lineární asymptotickou sloºitostí lze pouºít nap°. strukturu zvanou kd-strom [18]. Pomocí kd-stromu lze vyhledávat s asymptotickou sloºitostí
O(log n).
Bohuºel ho nelze pouºít pro hledání v uzlech mapy. Kd-strom by se
totiº musel m¥nit s kaºdým pohybem uzl·, ke kterému dochází n¥kolikrát b¥hem jednoho cyklu. Jeho pouºitím by se sníºil £as pot°ebný k vyhledání nejbliº²ích uzl· ke vstupnímu signálu, ale zase by se prodlouºila ta £ást, b¥hem níº se uzly posouvají sm¥rem ke vstupnímu signálu. Proto tu bude popsán jiný zp·sob, který byl pro tento problém vyvinut, a který £as vyhledávání výrazn¥ sniºuje. Jeho asymptotická sloºitost sice není niº²í neº lineární, ale b¥hem experiment· se jasn¥ prokázalo, ºe je v praxi velmi rychlý. Zárove¬ nemá nijak výrazný vliv na zbytek algoritmu pouze zrychluje £ást vyhledávání nejbliº²ích uzl·, ale nezpomaluje tím ºádné jiné £ásti.
23
24
KAPITOLA 4.
OPTIMALIZACE
V následujících podkapitolách bude nejprve popsána struktura, která se pro vyhledávání pouºívá, a následn¥ samotný vyhledávací algoritmus.
4.1.1
Struktura pro vyhledávání
Struktura, která je pouºita, spo£ívá v tom, ºe se prostor, ve kterém bude probíhat vyhledávání, rovnom¥rn¥ rozd¥lí na stejn¥ velké krychle s délkou hrany
a.
Vyhledávání pak m·ºe
probíhat v rámci jednotlivých krychlí sniºuje se tak prohledávaný prostor. Rozd¥lením prohledávaného prostoru na krychle vznikne 3D m°íºka krychlí. Rozm¥ry m°íºky mohou být ve sm¥ru kaºdé osy r·zné budou zna£eny v m°íºce je tak rovný (gx ,
gy , gz )
gx , gy , gz .
Po£et krychlí
gx gy gz . Velikost pokrytého prostoru je tedy de nována rozm¥ry m°íºky
a délkou hrany krychle (a). Aby bylo jednozna£n¥ de nováno, jaký prostor je
pokrytý, je je²t¥ pot°eba stanovit po£átek pokrytého prostoru vzhledem k po£átku sou°adnic. Ten bude zna£en trojicí sou°adnic
ox , oy , oz .
Kaºdá krychle je ur£ena svojí pozicí v této m°íºce, sou°adnice krychle v m°íºce budou zna£eny trojicí
cx , cy , cz .
M°íºku lze navíc de novat tak, aby pokrývala i body, které se
nenachází p°ímo v ohrani£eném prostoru. Toho lze docílit tím, ºe hrani£ní krychle m°íºky budou pokrývat ty body, které mají svou pozici mimo p°ímo pokrytý prostor. V programu lze celou m°íºku uloºit do jednorozm¥rného pole. Pozice
ci
krychle v poli
krychlí lze pak jednodu²e spo£ítat z jejích m°íºkových sou°adnic:
ci = cx + cy gx + cz gx gy Kaºdý bod prostoru je de nován trojicí sou°adnic
px , py , pz .
(4.1) Do jaké krychle struktury
takový bod pat°í, lze pak spo£ítat v konstantním £ase z jeho sou°adnic:
cx,y,z = min(
max(px,y,z + ox,y,z , 0) , gx,y,z − 1) a
(4.2)
Takto spo£ítané sou°adnice krychle platí i pro body v prostoru, které nepat°í p°ímo do pokryté oblasti.
M°íºka krychlí je v algoritmu pouºita následovn¥. Na po£átku je pot°eba vybrat prostor, který bude m°íºka pokrývat. To lze provést tak, ºe se projdou v²echny vstupní signály a ur£í se kvádr, který v²echny tyto vstupní signály obsahuje. Pokud máme de nován prostor, který chceme mít krychlemi pokrytý, sta£í uº jen zvolit délku hrany krychle. Rozm¥ry m°íºky se z ní pak jednodu²e dopo£ítají tak, aby m°íºka krychlí obsáhla celý kvádr vstupních signál·. B¥hem algoritmu pak musí mít kaºdý uzel p°i°azenu jednu krychli, do které pat°í a kaºdá krychle musí mít seznam uzl·, které obsahuje. Pokud se p°idává nový uzel do mapy, spo£ítá se podle vzorc· 4.2 a 4.1, do jaké krychle pat°í. Krychle si p°idá uzel do seznamu uzl·, které obsahuje, a uzel si uloºí odkaz na tuto krychli. P°i posunu uzlu v prostoru se pak vºdy p°epo£ítá, jaká krychle odpovídá nové pozici. Pokud se li²í od staré pozice (té uloºené v uzlu), odebere se posunutý uzel ze seznamu uzl· staré krychle a p°idá do seznamu uzl· nové krychle. Odkaz z uzlu se nakonec zm¥ní na novou krychli. V²echny operace s uzly lze tedy provád¥t v konstantním £ase (pokud jsou operace nad seznam uzl· konstantní a to jsou, jak je popsáno v kapitole 5) a mají velmi malý vliv na délku provád¥ní t¥chto operací.
4.1.
NALEZENÍ NEJBLIÍHO UZLU
4.1.2
25
Vyhledávací algoritmus
Ve struktu°e popsané vý²e probíhá hledání nejbliº²ího uzlu ke vstupnímu signálu následovn¥. Nejd°íve je ze sou°adnic vstupního signálu spo£ítáno, do které krychle signál pat°í. Následn¥ se lineárním vyhledáváním prohledá tato krychle a v²echny krychle, které tuto obklopují (celkem 27 krychlí). Pokud je vzdálenost aktuáln¥ nejbliº²ího uzlu od vstupního signálu men²í neº je délka hrany krychle, pak se jedná o nejbliº²í uzel ze v²ech uzl· a vyhledávání kon£í. Pokud je vzdálenost v¥t²í neº délka hrany, nemusí to nutn¥ být nejbliº²í uzel. Proto se prohledají i v²echny krychle, které obklopují ty jiº prohledané (lze si to p°edstavit jako dal²í vrstvu krychlí). Pokud je po tomto kroku vzdálenost aktuáln¥ nejbliº²ího uzlu ke vstupnímu signálu men²í neº dvojnásobek délky hrany, je to ten nejbliº²í ze v²ech. Pokud není men²í, prohledá se dal²í vrstva a kontroluje se trojnásobek délky. Takto se pokra£uje, dokud bu¤ nejsou prohledány v²echny uzly, nebo není ten nejbliº²í nalezen d°íve.
(a)
(b)
(d)
(c)
(e)
Obrázek 4.1: Ukázka, jak vypadá struktura pro vyhledávání ve 2D. Na obr. (a) je vyzna£en £tverec, ve kterém za£íná vyhledávání (kam spadá vstupní signál), na obr. (b) okolní vrstva £tverc·, která je v prvním kroku také prohledávána. Na obr. (c) je znázorn¥no, ºe pokud je nejbliº²í uzel ve vzdálenosti do jedné délky hrany, musí to být nejbliº²í uzel. Na obr. (d) je znázorn¥na dal²í vrstva a na obr. (e) op¥t ukázka, ºe pokud je nejbliº²í uzel ve vzdálenosti do dvou délek hrany, musí to být nejbliº²í uzel v·bec.
Z popsaného algoritmu je z°ejmé, ºe asymptotická sloºitost se oproti lineárnímu vyhledávání nesníºí, protoºe v nejhor²ím p°ípad¥ se budou prohledávat v²echny uzly. Pokud se v²ak
26
KAPITOLA 4.
OPTIMALIZACE
prohledávaný prostor vhodn¥ rozd¥lí na krychle, sta£í prohledat men²í po£et uzl·. Z experiment· vyplývá, ºe maximálního zrychlení se dosahuje, pokud se prostor vstupních signál· rozd¥lí na p°ibliºn¥ stejný po£et krychlí jako je cílový po£et výstupních uzl· (výstupní rozli²ení). Velkého zrychlení oproti lineárnímu vyhledávání se v²ak dosahuje uº p°i mnohem men²ím po£tu krychlí.
4.2
Kumulativní £íta£ chyb
V 9. kroku algoritmu se sniºují £íta£e chyb v²ech uzl· v síti parametrem
β.
Tento krok je
dal²ím kandidátem na zrychlení, pon¥vadº se provádí kaºdý cyklus algoritmu a jsou v n¥m procházeny v²echny uzly mapy. Krom¥ 9. kroku se s £íta£i chyb pracuje je²t¥ v krocích 4 a 8. B¥hem jednoho cyklu je tedy pot°eba znát £íta£e chyb u velmi málo uzl· oproti tomu, kolik jich je pot°eba sníºit v posledním kroku. Optimalizace tedy spo£ívá v tom, ºe se místo sniºování £íta£· chyb u v²ech uzl· jen po£ítá kolikrát m¥lo ke sniºování dojít. Je-li pak pot°eba zjistit aktuální stav £íta£e u konkrétního uzlu, aplikuje se
β
na £íta£ tolikrát, kolikrát je pot°eba. Odpadá tak nutnost
v kaºdém cyklu procházet v²echny uzly.
Kv·li optimalizaci je pot°eba jednak zavést globální £íta£
Eβ ,
který nese informaci, ko-
likrát do²lo ke sníºení £íta£· chyb u v²ech uzl·, a potom musí mít kaºdý uzel svojí vlastní zna£ku
β
Eβn ,
která obsahuje poslední stav £íta£e
Eβ ,
p°i kterém bylo sníºení parametrem
aplikováno na uzel. V kroku 4 se totiº zvy²uje £íta£ chyb a m·ºe tak dojít k tomu, ºe
na r·zné uzly bylo
β
pouºito v r·zných stavech jejich £íta£e mají zcela jinou hodnotu. E Navíc je je²t¥ zaveden £íta£ βcum , který obsahuje p°edem vypo£tenou hodnotu β β , kterou lze pouºít na sníºení £íta£· u t¥ch uzl·, které mají hodnotu u kterých je pot°eba sníºit £íta£ koe cientem
β Eβ -krát,
Eβn
rovnou 0. To jsou ty uzly,
protoºe nebyly od po£átku £ítání
globálního £íta£e nijak zm¥n¥ny a to není v¥t²ina uzl· v map¥. Hodnota
βcum
se vypo£í-
tává p°edem, protoºe operace mocniny je drahá a tímto jednoduchým opat°ením se poda°í eliminovat nutnost provedení této operace na minimum. Pokud máme takto p°ipravenou infrastrukturu, lze vy°e²it problém sniºování £íta£· chyb úpravou algoritmu tak, aby ji vyuºíval. Následující kroky popisují, jak lze algoritmus upravit: 1. Na po£átku algoritmu se nastaví 2. Pokud se p°idává nový uzel
Eβ
na nula a
βcum
na 1.
n do mapy, nastaví se mu parametr Eβn
na aktuální hodnotu
Eβ . 3. V kroku 4 se provádí zvý²ení £íta£e chyb u vít¥zného uzlu
n1 .
Je tedy pot°eba tento
krok upravit tak, aby se korektn¥ sníºil £íta£ chyb a nastavila správn¥ zna£ka
~ En1 = β (Eβn1 −Eβ ) En1 + kw ~ n1 − ξk, Eβn1 = Eβ .
Eβn : (4.3) (4.4)
4. V kroku 8 se sekven£n¥ prochází v²echny uzly, aby se na²el ten s nejv¥t²í hodnotou £íta£e chyb. Je tedy moºné (dokonce nutné) aplikovat globální £íta£ na v²echny uzly
4.2.
KUMULATIVNÍ ÍTA CHYB
27
mapy, a pon¥vadº jsou upraveny £íta£e v²ech uzl· lze
Eβ
vynulovat. Pro kaºdý uzel
n
se tedy provede:
En = β (Eβn −Eβ ) En , Eβn = 0. Navíc lze £len
β (Eβn −Eβ )
v rovnici 4.5 zam¥nit za
βcum ,
(4.5) (4.6) pokud je
Nakonec se vynuluje i globální £íta£ a resetuje akumulované
Eβn
β:
Eβ = 0, βcum = 1 5. V kroku 9 se místo sniºování £íta£· provede jen zm¥na
Eβ = Eβ + 1, βcum = ββcum .
rovno nule.
(4.7) (4.8)
Eβ
a
βcum : (4.9) (4.10)
S takto popsanou optimalizací se z lineární sloºitosti p°i sniºování v²ech £íta£· chyb stane sloºitost konstantní jen se m¥ní £íta£e a zna£ky. Zárove¬ se nezvý²í sloºitost ºádného jiného kroku. Je totiº vyuºito proces·, které se musí vykonat nezávisle na úprav¥ £íta£· chyb (nap°. procházení v²ech uzl· v kroku 8).
28
KAPITOLA 4.
OPTIMALIZACE
Kapitola 5 Implementace Algoritmus GSRM je implementován jako knihovna libgsrm a jako vzorový program gsrm nad touto knihovnou. V²e je implementováno v programovacím jazyce C (konkrétn¥ ve standardu C99), knihovna je pln¥ reentrantní, coº znamená, ºe je schopná vícenásobného sou£asného b¥hu. V této kapitole budou dále stru£n¥ popsány jen základní struktury, které jsou pouºity, a zajímavé implementa£ní detaily, které stojí za p°iblíºení. Spole£n¥ s programem a knihovnou implementující algoritmus GSRM byl také naprogramován program pro zobrazování 3D dat ten bude také stru£n¥ popsán v samostatné podkapitole.
5.1
Základní struktury knihovny
Struktura mapy se skládá z propojených uzl·, hran a trojúhelníkových plo²ek a tak jsou i reprezentovány uvnit° programu.
5.1.1
Uzel, hrana, plo²ka
Struktura uzlu
gsrm_node_t
(implementovaná ve zdrojových souborech node.{h,c} ) je slo-
ºena p°edev²ím z polohového vektoru, ze seznamu odkaz· na hrany, které z n¥ho vycházejí a ze struktur (gsrm_list_t - bude popsána níºe), které mu dovolují zapojovat se do seznamu v²ech uzl· v map¥ a do seznamu uzl· krychle, do které pat°í. Struktura hrany
gsrm_edge_t
(implementována ve zdroj. souborech edge.{h,c} ) je slo-
ºena z dvojice odkaz· na koncové uzly hrany a dvouprvkového pole odkaz· na plo²ky. Dvouprvkové proto, ºe hrana m·ºe ohrani£ovat maximáln¥ dv¥ plo²ky. Dále obsahuje strukturu dovolující zapojovat hranu do seznamu v²ech hran mapy. Struktura plo²ky
gsrm_face_t (implementována ve zdroj. souborech face.{h,c}) se skládá
ze trojice odkaz· na ohrani£ující hrany a ze struktury, kterou je moºné p°ipojit plo²ku do seznamu v²ech plo²ek mapy. Ke v²em t¥mto strukturám jsou implementovány jen základní operace. V²echny sloºit¥j²í operace jsou p°esunuty na vy²²í vrstvu. To je ud¥láno proto, ºe jsou v²echny struktury navzájem propojeny a bylo by sloºité provád¥t v²echny nezbytné kontroly. Vy²²í vrstva naopak
29
30
KAPITOLA 5.
IMPLEMENTACE
má více informací o celé map¥, a proto je jednodu²²í d¥lat tyto kontroly tam. Jedná se nap°íklad o operace jako je odstran¥ní nebo p°idání hran. Pokud se nap°. odstra¬uje hrana, je pot°eba zkontrolovat, ºe neohrani£uje ºádnou plo²ku, následn¥ je pot°eba ji odstranit ze seznam· hran v koncových uzlech atd. Vy²²í vrstva, která má na starosti v²echny tyto operace je struktura
gsrm_mesh_t.
Obrázek 5.1: Schéma propojení struktur
5.1.2
gsrm_node_t, gsrm_edge_t
a
gsrm_face_t.
Reprezentace mapy (sít¥)
Struktura, která sdruºuje uzly, hrany a plo²ky je struktura
gsrm_mesh_t
(implemento-
vána v souborech mesh* ). Struktura je sloºena ze seznamu v²ech uzl·, hran a plo²ek a z odkazu na m°íºku krychlí pomocí které se v map¥ vyhledává (viz. kapitola 4). ádná jiná £ást knihovny nemá p°ístup k uzl·m, hranám, plo²kám ani krychlím, neº je tato. Ve²keré informace o síti jsou uloºeny zde a jedinou manipulaci se sítí lze provád¥t jen skrze funkce za£ínající na
gsrmMesh,
gsrm_mesh_t.
a které mají v²echny jako první argument odkaz na strukturu sít¥
Nad sítí je pak poslední vrstva struktura
gsrm_t,
rozhraní knihovny.
Obrázek 5.2: Schéma struktury
gsrm_mesh_t.
coº je zárove¬ vn¥j²í
5.2.
IMPLEMENTACE SEZNAM
31
Struktura gsrm_t
5.1.3
Struktura
gsrm_t
(implementována v souborech gsrm.{h,c} ) je sloºena p°edev²ím ze struk-
gsrm_mesh_t gsrm_insig_t.
tury parametr·, odkazu na strukturu mnoºinu vstupních signál·
a odkazu na strukturu reprezentující
Jednotlivé kroky algoritmu jsou implementovány na této úrovni a p°evádí se na volání funkcí niº²í vrstvy sít¥, jako je vytvo° nový uzel a pod.
5.2
Implementace seznam·
Pon¥vadº se v programu neustále pracuje s r·znými seznamy, byl p°i implementaci kladen velký d·raz na to, aby tyto operace byly co nejrychlej²í. Proto byla za vzor k implementaci seznam· vybrána implementace, která je pouºita v zdrojových kódech jádra OS Linux. Konkrétn¥ se jedná o implementaci struktury
struct list_head
a operací s ní z hlavi£kového
souboru include/linux/list.h. Jedná se o implementaci obousm¥rného spojového seznamu. Prvky (struktury), které se do seznamu zapojují, musí v¥d¥t do jakého seznamu pat°í. Nejedná se tedy o implementaci kontejnerového typu seznamu, jako je nap°. std::list ze standardní knihovny C++, a proto je nelze pouºít v²ude. Jejich výhoda naopak je, ºe v²echny operace se provádí v konstantním £ase.
gsrm_list_t (implementována v souboru list.h). Tato struktura se skládá jen z dvou ukazatel·, .prev a .next, na dal²í strukturu gsrm_list_t. V knihovn¥ gsrm je základní strukturou
Mechanizmus seznamu funguje tak, ºe se do struktury, která vlastní seznam, vloºí struk-
gsrm_list_t a inicializuje tak, aby .next i .prev ukazovaly na sebe sama (viz. funkce init() ve výpisu 5.1).
tura
gsrm_list_t (viz. item ve výpisu 5.1). Od tohoto momentu jiº lze °et¥zit prvky seznamu p°es .next a .prev ukazatele. První prvek pole je tedy ten, na který ukazuje atribut .next struktury gsrm_list_t uloºené ve struktu°e, která vlastní seznam (podle výpisu 5.1 by tedy owner.l.next ukazoval vºdy na za£átek seznamu). Na druhý prvek ukazuje .next z prvního Do struktur, které mají být prvky seznamu, se také vloºí struktura
de nice struktury
prvku, atd. Pon¥vadº na sebe odkazují jen struktury
gsrm_list_t,
je pot°eba n¥jak zjistit ukaza-
tel na samotný uchovávaný prvek. To lze provést jednodu²e tak, ºe se hodnota ukazatele
gsrm_list_t v prvku a z polohy itemEntry() vrací ukazatel na prgsrm_list_t. To je provedeno makrem
na prvek dopo£ítá z hodnoty ukazatele na strukturu struktury
gsrm_list_t
v prvku. Ve výpisu 5.1 funkce
vek, který je spo£ítaný z ukazatele na strukturu
gsrm_container_of, které (makrem gsrm_offsetof).
jednodu²e od tohoto ukazatele ode£te oset struktury v prvku
Tato struktura pro tvorbu seznam· je pouºita pro v²echny seznamy v programu, kde je to jen moºné. Tedy pro seznamy v²ech uzl·, hran a plo²ek, pro seznamy uzl·, uvnit° krychle a pod. V²echny operace se seznamy jsou tak velmi rychlé.
32
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
KAPITOLA 5.
Výpis 5.1: Ukázka pouºití
gsrm_list_t
IMPLEMENTACE
struktury
struct owner { gsrm_list_t l }; struct item { int a , b , c ; gsrm_list_t l ; }; void ownerInit ( struct owner ∗ o ){ o−>l . next = o−>l . prev~= &o−>l ; } #define gsrm_offsetof (TYPE, MEMBER) (( size_t ) &((TYPE ∗ ) 0)−>MEMBER) #define gsrm_container_of ( ptr , TYPE, MEMBER) \ ( TYPE ∗ ) (( char ∗ ) ptr − gsrm_offsetof ( TYPE , MEMBER ) ) struct item ∗ itemEntry ( gsrm_list_t ∗ l ){ return gsrm_container_of ( l , struct item , l ) ; } 5.3
SVT - Nástroj pro zobrazování 3D objekt·
P°i implementaci a b¥hem lad¥ní knihovny bylo pot°eba prohlíºet vygenerované mapy. Bylo pot°eba prohlídnout si i jednotlivé detaily, jak vypadá zrekonstruovaný objekt ze v²ech stran i zevnit°. Zárove¬ bylo pot°eba mít moºnost skrývat r·zné £ásti tak, aby neru²ily p°i prohlíºení zbytku. Bohuºel jsem nenalezl ºádný nástroj, který by n¥co takového umoº¬oval, a proto jsem se rozhodl naprogramovat sv·j vlastní nástroj, který jsem pojmenoval SVT - Simple Visualization Tool. SVT je postaveno nad knihovnou Qt [4], která slouºí ke stavb¥ GUI, a knihovnami Coin3D a Quarter [2], které slouºí k zobrazování 3D dat a jejich integraci do frameworku Qt. Ke kompilaci je navíc pot°eba program ex [3], který slouºí ke generování lexikálního analyzátoru pro parser vstupních dat. SVT je licencován pod GPLv3 licencí a zdrojové kódy jsou dostupné p°es gitový repozitá°
git://phil.danfis.cz/SVT.git.
Tento nástroj umoº¬uje prohlíºet jednotlivé detaily 3D objekt·, vypínat a zapínat pohled na jednotlivé £ásti a m¥nit jejich barvy. V²echny zde uvedené obrázky z rekonstrukce jsou generovány z tohoto nástroje. Knihovna libgsrm také momentáln¥ generuje mapu pouze ve formátu pro tento nástroj,
ale nebude problém kdykoli v budoucnu dal²í formáty výstupu
doprogramovat.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Points
:
0 0 0 1 0 0 1 1 0 0.5 0.5 1 Edges : 0 1 1 2 2 0 0 3 1 3 2 3 Faces : 0 1 2
Výpis 5.2: Ukázka vstupních dat pro nástroj SVT - jehlan
5.3.
SVT - NÁSTROJ PRO ZOBRAZOVÁNÍ 3D OBJEKT
Obrázek 5.3: Ukázka programu - je zobrazen objekt de novaný ve výpise 5.2
33
34
KAPITOLA 5.
IMPLEMENTACE
Kapitola 6 Experimentální výsledky V této kapitole budou prezentovány výsledky experiment· rekonstrukce r·zných objekt·. Experimenty byly provád¥ny v OS Linux na notebooku s procesorem Intel Core 2 Duo taktovaným na 2 GHz a 2 GB RAM, programem bylo p°ímo vyuºito jen jedno procesorové jádro. Jako vstupní data byly zvoleny za prvé skeny objekt· dostupné z ve°ejného repozitá°e [1], který obsahuje pov¥t²inou skeny r·zných so²ek. Za druhé byly pouºity skeny z robotu, které jsem dostal k dispozici od Skupiny mobilní robotiky z Katedry kybernetiky, FEL, VUT. R·zné druhy vstupních objekt· byly zvoleny proto, aby bylo ukázáno, ºe tento algoritmus lze bez rozdílu pouºít na data z robotu stejn¥ tak jako na 3D skeny jiných objekt·. Pro rekonstrukci v²ech objekt· bez rozdílu byly pouºity ty stejné hodnoty parametr· (viz. tabulka 6.1).
εb 0,05
εn 0,0006
λ 200
β 0,9995
α 0,95
agemax 200
φv 3 π 4
θf π 4
φe 9 π 10
Tabulka 6.1: Tabulka hodnot parametr· pouºitých b¥hem experiment·
6.1
Rekonstrukce 3D povrchu
P°i rekonstrukci v²ech objekt· v této podkapitole byly pouºity hodnoty parametr· uvedených v tabulce 6.1 s cílovým rozli²eným 20 000 uzl·. Byly rekonstruovány objekty z [1] Dragon obsahující 437 646 bod·, Arm obsahující 172 974 bod· a sken z robotu, poskytnutý Skupinou mobilní robotiky, Místnost obsahující 806 092 bod·. Sken z robotu byl získán b¥hem jízdy robotu dv¥ma místnostmi. Na obrázku A.1 si lze prohlédnout, jak vypadají vstupní mnoºiny jednotlivých objekt·. Na obrázcích A.2, A.3 a A.4 jsou vid¥t výsledky rekonstrukce. V tabulce 6.2 si pak lze prohlédnout výstupní parametry jednotlivých rekonstrukcí.
35
36
KAPITOLA 6.
objekt po£et vstupních bod· po£et vygenerovaných uzl· po£et vygenerovaných hran po£et vygenerovaných plo²ek doba rekonstrukce z toho postprocesing
EXPERIMENTÁLNÍ VÝSLEDKY
Dragon
Arm
Místnost
437 646
172 974
806 092
19 190
19 499
15 029
57 247
58 510
41 884
37 826
38 832
26 652
35s
40s
37,5s
0,5s
0,5s
0,5s
Tabulka 6.2: Tabulka výsledk· rekonstrukce pro cílové rozli²ení 20 000 uzl·.
6.1.1
Kvalita vygenerovaných povrch·
Povrchy vygenerované algoritmem GSRM celkem v¥rn¥ rekonstruují povrch objekt·, jak je vid¥t z obrázk·. Rekonstrukce v²ak nejsou úpln¥ dokonalé, coº je vid¥t na obrázku A.5, kde je zobrazen detail spodní £ásti objektu Dragon po rekonstrukci. Na obrázku je vid¥t, ºe v zrekonstruovaném povrchu z·staly n¥jaké díry. To je zp·sobeno tím, ºe v t¥chto místech nemá sí´ dokonale nau£enou topologii objektu. V takových místech vznikají hrany, které se r·zn¥ k°íºí a podobn¥. Následný postprocesing pak není schopen správn¥ rozeznat, kde m·ºe a kde nem·ºe vytvo°it plo²ky. Chyba je tak v nedokonalém algoritmu GSRM i nedokonalém postprocesingu. Naopak velmi dobré výsledky jsou vid¥t p°i bliº²ím pohledu na detaily zrekonstruovaných objekt·. Na objektu Dragon je dob°e vid¥t, ºe algoritmus je schopný dob°e zrekonstruovat v²echny moºné záhyby a sloºité tvary objektu. Na objektu Arm pak, ºe i jemné detaily povrchu jsou p°i dostate£ném rozli²ení dob°e tvarované (viz. A.6(a) detailní pohled na objekt shora). Na obrázku A.6(b) je zase dob°e vid¥t, ºe zrekonstruovaný povrch je opravdu povrch objektu, a ºe se uvnit° objektu nevytvá°í ºádné p°í£né plo²ky, které by z pohledu zven£í nebyly vid¥t. Nakonec na obrázku A.7, kde je pohled dovnit° zrekonstruované místnosti, si lze v²imnout, ºe r·zné men²í, robotem oskenované, objekty, jako jsou stoly, po£íta£e a podobn¥, se nezrekonstruovaly p°íli² dob°e, protoºe uº ve vstupních bodech byly ²patn¥ rozeznatelné. Naopak je vid¥t, ºe zá°ivky u stropu, které byly ve skenu reprezentované sice malým shlukem bod·, ale jednozna£n¥ji odli²itelným od zbytku skenu, jsou alespo¬ £áste£n¥ zrekonstruované.
objekt
plo²ek p°ed pp plo²ek po pp
Dragon
25 101
37 826
Arm
27 736
38 832
Místnost
19 261
26 652
Tabulka 6.3: Tabulka po£tu plo²ek v map¥ p°ed a po postprocesingu.
6.1.2
Výstupní parametry rekonstrukcí
V tabulkách 6.2 a 6.3 jsou vypsané výstupní parametry jednotlivých rekonstrukcí.
6.2.
RZNÁ VÝSTUPNÍ ROZLIENÍ
37
D·vod, pro£ není výstupní po£et uzl· roven 20 000, coº bylo cílové rozli²ení, je ten, ºe jsou n¥jaké uzly odstran¥ny b¥hem postprocesingu. Z tabulky je vid¥t, ºe délka postprocesingu je oproti celkové délce rekonstrukce zanedbatelná. Dále je vid¥t, ºe rekonstrukce je extrémn¥ rychlá nezávisle na tom, jak velká je vstupní mnoºina. Dokonce neplatí, ºe by více vstupních bod· implikovalo del²í dobu rekonstrukce. as rekonstrukce se pohybuje od 35 sekund to 40 sekund, a´ je vstupních bod· cca 170 000 nebo cca 800 000. Navíc kvalita generovaného povrchu je u v²ech objekt· srovnatelná. Vliv postprocesingu je vid¥t na obrázcích A.2, A.3 a A.4 i z tabulky 6.3. Postprocesing dokon£il triangulaci objekt· a vytvo°il tak ve v¥t²in¥ p°ípad· souvislý povrch bez d¥r na základ¥ nau£ené topologie sít¥. Z tabulky 6.3 je také vid¥t, ºe b¥hem postprocesingu byl navý²en po£et plo²ek v map¥ zhruba o polovinu. Povrch se tedy nevytvá°í od za£átku, ale je vytvá°en na základ¥ jiº zrekonstruovaného povrchu pro úsp¥²ný výsledek postprocesingu je p°ímo nutné, aby zrekonstruovaný povrch m¥l jiº jistou kvalitu a neobsahoval p°íli² mnoho d¥r. Postprocesing lze hodnotit jako úsp¥²ný, protoºe v¥t²ina d¥r byla korektn¥ vytriangulována.
Dragon
po£et uzl· doba rekonstrukce pouze s opt. sniºování chyb. £íta£e pouze s opt. vyhledávání zcela bez optimalizací
1000
5000
10 000
20 000
0,7s
4s
10,5s
35s
7s
2m 45,5s
10m 48,2s
44m 51,7s
1,5s
27,2s
4m 18,5s
39m 35,5s
7,9s
3m 13,5s
16m 11,5s
1h 33m 3s
Tabulka 6.4: Tabulka výsledk· rekonstrukce objektu Dragon pro r·zné výstupní rozli²ení.
6.2
R·zná výstupní rozli²ení
Na obrázcích A.8 a A.10 si lze prohlédnout zrekonstruovaný objekt Dragon ve výstupním rozli²ení 1000, 5000, 10 000 a 20 000 uzl·. Na obrázcích je vid¥t, jaký má vliv zvy²ování cílového rozli²ení rekonstrukce. P°i nízkém cílovém rozli²ení je objekt zrekonstruován ve velmi hrubých obrysech. P°i zvy²ování rozli²ení se mapa m·ºe b¥hem u£ení více soust°edit na jednotlivé detaily objektu a vytvá°et tak p°esn¥ji zrekonstruovaný povrch objektu. Naopak p°i p°íli² velkém cílovém rozli²ení dochází k p°eu£ení sít¥, protoºe se vytvá°í velké mnoºství uzl·, které v map¥ z·stávají, ale nejsou dostate£n¥ £asto aktivovány p°i u£ení na n¥ p°ichází °ada velmi z°ídka. Na obrázku A.9 je zrekonstruovaný objekt Dragon p°i cílovém rozli²ení 50 000 a 100 000 uzl·. Je vid¥t, ºe uº p°i 50 000 uzlech z·stává v map¥ více d¥r a se zvy²ujícím se rozli²ením kvalita rekonstruovaného povrchu dále klesá.
Na obrázku A.11 je ukázán výsledek rekonstrukce objektu Místnost p°i r·zných cílových rozli²eních. Op¥t lze vid¥t, jak se p°i zvy²ujícím se rozli²ení rekonstruuje více detail· objektu. To je je²t¥ lépe vid¥t na obrázku A.12, kde je detail pohledu dovnit° místnosti. Zpo£átku se rekonstruují jen hrubé obrysy objektu, jakmile má ale mapa k dispozici více uzl·, m·ºe se soust°edit na modelování v¥t²ích detail·. Nap°íklad zá°ivka u stropu není p°i rozli²ení
38
KAPITOLA 6.
EXPERIMENTÁLNÍ VÝSLEDKY
1000 a 5000 uzl· v podstat¥ v·bec zrekonstruována. P°i 10 000 uzlech je jiº zrekonstruována v hrubých obrysech a p°i 20 000 uzlech ji jiº celkem dob°e rozeznatelná.
Dal²í zajímavou vlastností algoritmu GSRM je jeho schopnost dokázat se rychle adaptovat na vstupní data. Uº p°i velmi malém rozli²ení lze totiº za£ít objekt rozeznávat. Objekt Dragon je objekt s relativn¥ sloºitým tvarem a p°i jeho rekonstrukci je pot°eba dbát na vysokou míru detailu. Jeho model obsahuje tém¥° 450 000 bod·, p°esto jiº p°i výstupním rozli²ení 1000 uzl· odpovídá v hrubých obrysech tvar zrekonstruovaného objektu reálnému tvaru objektu (jak je vid¥t na obr. A.8(a)). Dokonce jsou v map¥ rozpoznatelné jednotlivé detaily, jako je tvar hlavy nebo vzadu zkroucený ocas. Podobn¥ p°esn¥ zrekonstruovaný tvar lze pozorovat i v p°ípad¥ objektu Místnost (viz. obr. A.11(a)) v tomto p°ípad¥ je v²ak pom¥r mezi výstupním rozli²ením a velikostí vstupní mnoºiny je²t¥ vy²²í (objekt Místnost je sloºen z více neº 800 000 bod·).
Místnost
po£et uzl· doba rekonstrukce pouze s opt. sniºování chyb. £íta£e pouze s opt. vyhledávání zcela bez optimalizací
1000
5000
10 000
20 000
0,6s
3,8s
10,5s
37,5s
6,8s
2m 42,2s
10m 47,5s
44m 37,3s
1,5s
37s
5m 1s
45m 37s
7,7s
3m 17s
16m 15,5s
1h 33m 42s
Tabulka 6.5: Tabulka výsledk· rekonstrukce objektu Místnost pro r·zné výstupní rozli²ení.
6.3
as pot°ebný pro rekonstrukci
Jak jiº bylo °e£eno vý²e, rekonstrukce je provád¥na b¥hem velmi krátkého £asu v °ádu sekund a to nezávisle na velikosti vstupní mnoºiny bod·. Toho je dosaºeno p°edev²ím implementací optimalizací (viz. kapitola 4). V tabulkách 6.4 a 6.5 je vid¥t, jak velký je rozdíl v £ase pot°ebném pro rekonstrukci povrchu bez optimalizace a s ní. S optimalizací se jedná o £asy od desetin sekund pro 1000 výstupních uzl· po desítky sekund pro 20 000 výstupních uzl·. Naopak bez optimalizací jsou to £asy od jednotek sekund pro 1000 uzl· po více neº hodinu a p·l pro 20 000 uzl·. Velikost rozdílu je v n¥kolika °ádech a zvy²uje se se zvy²ujícím se po£tem výstupních uzl·. V tabulkách 6.4 a 6.5 jsou také uvedeny doby rekonstrukcí s aplikovanou pouze jednou optimalizací bu¤ je optimalizováno pouze vyhledávání nejbliº²ích uzl· ke vstupnímu signálu,
nebo je optimalizováno pouze sniºování £íta£· chyb parametrem
β.
Z tabulek je
vid¥t, ºe p°i men²ím cílovém rozli²ení se více uplatní optimalizace vyhledávání a se zvy²ujícím se cílovém rozli²ení se vlivy obou optimalizací na dobu rekonstrukce p°ibliºují. V¥t²í vliv optimalizovaného vyhledávání p°i men²ím po£tu uzl· je dán tím, ºe uzly jsou v prostoru více rozprost°eny a rozd¥lení prostoru na krychle tak výrazn¥ pomáhá (není pot°eba procházet tolik uzl·). Optimalizace sniºování chybových £íta£· je zaloºena na tom, ºe u v¥t²iny uzl· v map¥ není b¥hem u£ících cykl· zapot°ebí s £íta£i v·bec pracovat (jejich hodnoty se nem¥ní). P°i malém
6.4.
SHRNUTÍ
39
po£tu uzl· v map¥ jsou v²ak chybové £íta£e m¥n¥ny u v¥t²í £ásti celkového po£tu uzl·. Tato optimalizace se tak uplat¬uje jen £áste£n¥. P°i vy²²ím cílovém rozli²ení je vliv obou optimalizací srovnatelný, protoºe vyhledávání se provádí stále na men²ím po£tu uzl·, ale po£et uzl·, u kterých dochází ke sniºování chybových £íta£·, vzhledem k celkovému po£tu uzl· se sniºuje vliv optimalizace sniºování chybových £íta£· se tak více uplat¬uje. Na tom je vid¥t, jak byly optimalizace pot°ebné a pro£ je bylo nezbytné implementovat. Zárove¬ je to d·kaz toho, ºe pro optimalizace byly opravdu vybrány ty £ásti algoritmu, které ho nejvíce zpomalovaly. Pozitivní není jenom pom¥r mezi neoptimalizovaným a optimalizovaným b¥hem, ale i samotná velmi krátká doba b¥hu. Nap°. ve srovnání s dobou, která je pot°eba k sejmutí sken· z robotu, je n¥kolikanásobn¥ krat²í. To nazna£uje, ºe by v budoucnu mohl být tento algoritmus pouºit pro mapování prost°edí uº b¥hem jízdy robotu.
Z tabulek 6.4 a 6.5 je také vid¥t, ºe doba b¥hu je v podstat¥ závislá jen na cílovém rozli²ení rekonstrukce. Ta závislost v²ak není lineární, coº je vid¥t i na grafu 6.1, kde je vynesena závislost £asu pot°ebného pro rekonstrukci na velikosti výstupního rozli²ení pro je²t¥ více p°ípad· neº je v tabulkách. Nelineárnost závislosti je dána tím, ºe ani sloºitost struktury mapy se nezvy²uje lineárn¥. P°i vy²²ím po£tu uzl· v map¥ obsaºených je propojení uzl· vy²²í, a p°estoºe se optimalizacemi povedlo eliminovat v¥t²inu p°ípad·, kdy bylo pot°eba procházet v²echny uzly, stále je pot°eba procházet v²echny uzly b¥hem kroku p°idávání nového uzlu do mapy. B¥hem tohoto kroku je také pot°eba procházet v²echny sousedy uzlu s nejvy²²í hodnotou chybového £íta£e a takových soused· také p°ibývá s vy²²í sloºitostí struktury mapy. Tyto dva aspekty se s nejv¥t²í pravd¥podobností jeví jako p°í£ina r·stu doby pot°ebné pro rekonstrukci.
6.4
Shrnutí
B¥hem p°edchozích podkapitol byla zanalyzována kvalita výstup· algoritmu pro nejr·zn¥j²í výstupní rozli²ení a na nejr·zn¥j²ích objektech. Z obrázk· je vid¥t, ºe kvalita zrekonstruovaných povrch·, i díky dob°e navrºenému postprocesingu, je vysoká. Algoritmus je schopen velmi dob°e adaptovat neuronovou sí´ na vstupní mnoºinu bod· a zrekonstruovat tak celkový tvar objektu i jeho jednotlivé detaily. Zárove¬ bylo ukázáno, ºe navrºené optimalizace výrazn¥ sniºují £as pot°ebný pro rekonstrukci.
40
KAPITOLA 6.
EXPERIMENTÁLNÍ VÝSLEDKY
Obrázek 6.1: Doba rekonstrukce objekt· Místnost a Dragon p°i r·zných výstupních rozli²eních vynesená do grafu.
Kapitola 7 Záv¥r Cílem bakalá°ské práce bylo implementovat rostoucí samoorganizující se neuronovou sí´ Growing Self-recontruction Maps (GSRM) [19] slouºící k rekonstrukci povrchu 3D objektu a p°edev²ím ukázat, ºe tento algoritmus lze s úsp¥chem pouºít i na rekonstrukci senzorických dat nam¥°ených mobilním robotem. Algoritmus GSRM byl implementován. Zárove¬ s implementací algoritmu byl navrhnut vlastní postprocesing, bez kterého by nebylo moºné dosahovat tak vysoké kvality zrekonstruovaného povrchu objekt·. Algoritmus je schopen detailn¥ zrekonstruovat povrch objektu, p°i£emº míru detailu lze °ídit nastavením výstupního rozli²ení. V experimentech bylo prokázáno, ºe tímto algoritmem lze rekonstruovat jak modely 3D objekt· jako jsou modely so²ek a pod., tak i modely prost°edí získaných z m¥°ení mobilního robotu. Byly také navrhnuty a implementovány optimalizace, které velmi významn¥ zkracují £as pot°ebný pro rekonstrukci v experimentech bylo ukázáno, ºe je to aº 150-krát pro nejvy²²í pouºité rozli²ení. S optimalizacemi trvá rekonstrukce povrchu jen n¥kolik sekund (p°i nejvy²²ím výstupním rozli²ení 20ti tisíc uzl· trvala rekonstrukce p°ibliºn¥ 35 sekund) nezávisle na velikosti vstupní mnoºiny bod·, coº bylo v experimentech ov¥°eno na modelech obsahujících p°ibliºn¥ 170 aº 800 tisíc bod·.
Velmi krátký £as rekonstrukce nazna£uje, ºe by mohlo být moºné pouºít tento algoritmus pro mapování prost°edí jiº b¥hem jízdy robotu. Algoritmus by v tom p°ípad¥ bylo pot°eba modi kovat, aby dokázal zpracovávat vstupní data postupn¥ tak, jak budou dostupná z mobilního robotu. K dal²ímu zrychlení algoritmu by mohlo dojít p°i optimalizaci kroku, ve kterém se p°idávají nové uzly do mapy. Bylo by zapot°ebí zrychlit vyhledávání nejh·°e adaptovaných míst mapy p°i zachování pozitivního dopadu jiº navrºených optimalizací. V²e vý²e uvedené m·ºe být náplní dal²í práce spole£n¥ s dal²ím vylep²ením algoritmu s cílem co nejvíce eliminovat pot°ebu záv¥re£ného postprocesingu. Pokud by se poda°ilo postprocesing zcela eliminovat,
bylo by moºné rekonstrukci kdykoli v pr·b¥hu p°eru²it
a získat tak zrekonstruovaný povrch objektu v aktuálním rozli²ení.
41
42
KAPITOLA 7.
ZÁV
R
P°íloha A Obrázky výsledk· rekonstrukcí objekt·
(a) Dragon
(b) Arm
(c) Místnost
Obrázek A.1: Vstupní body jednotlivých objekt·.
43
44
PÍLOHA A.
OBRÁZKY VÝSLEDK REKONSTRUKCÍ OBJEKT
(a) P°ed postprocesingem
(b) Po postprocesingu
Obrázek A.2: Zrekonstruovaný objekt Dragon 20 000 uzly.
45
(a) P°ed postprocesingem
(b) Po postprocesingu
Obrázek A.3: Zrekonstruovaný objekt Arm 20 000 uzly.
46
PÍLOHA A.
OBRÁZKY VÝSLEDK REKONSTRUKCÍ OBJEKT
(a) P°ed postprocesingem
(b) Po postprocesingu
Obrázek A.4: Zrekonstruovaný objekt Místnost 20 000 uzly.
Obrázek A.5: Detail nekvalitn¥ zrekonstruované £ásti objektu Dragon, na kterém jsou jsou vid¥t nevytriangulované £ásti povrchu.
47
(a) Pohled shora
(b) Pohled dovnit° objektu
Obrázek A.6: Detaily zrekonstruovaného objektu Arm.
Obrázek A.7: Detail zrekonstruovaného objektu Místnost - pohled od dve°í dovnit° místnosti.
48
PÍLOHA A.
OBRÁZKY VÝSLEDK REKONSTRUKCÍ OBJEKT
(a) 1000 uzl·
(b) 5000 uzl·
(c) 10 000 uzl·
(d) 20 000 uzl·
Obrázek A.8: Rekonstrukce objektu Dragon v r·zných rozli²eních.
49
(a) 50 000 uzl·
(b) 100 000 uzl·
Obrázek A.9: Ukázka p°eu£ení sít¥ p°i rekonstrukci objektu Dragon. P°i p°eu£ení vzniká více nevytriangulovaných d¥r v zrekonstruovaném povrchu.
50
PÍLOHA A.
OBRÁZKY VÝSLEDK REKONSTRUKCÍ OBJEKT
(a) 1000 uzl·
(b) 5000 uzl·
(c) 10 000 uzl·
(d) 20 000 uzl·
Obrázek A.10: Detail hlavy zrekonstruovaného objektu Dragon v r·zných rozli²eních.
51
(a) 1000 uzl·
(b) 5000 uzl·
(c) 10 000 uzl·
(d) 20 000 uzl·
Obrázek A.11: Rekonstrukce objektu Místnost v r·zných rozli²eních.
52
PÍLOHA A.
OBRÁZKY VÝSLEDK REKONSTRUKCÍ OBJEKT
(a) 1000 uzl·
(b) 5000 uzl·
(c) 10 000 uzl·
(d) 20 000 uzl·
Obrázek A.12: Detail pohledu dovnit° místnosti rekonstruovaného objektu Místnost v r·zných rozli²eních.
P°íloha B Obsah p°iloºeného CD |-| | | | | | | | | |
GSRM |-- LICENSE |-- README |-- text | `-- bach.pdf `-- src |-- Makefile |-- ... |-- testsuites | |-- Makefile | |-- ...
Text licence GPLv3 Postup kompilace programu a knihovny Text bakalá°ské práce v PDF Adresá° se zdrojovým textem Adresá° s~automatickými testy
53
54
PÍLOHA B.
OBSAH PILOENÉHO CD
Literatura [1] The Stanford 3D Scanning Repository. World Wide Web electronic publication, 200902-12. URL
http://www-graphics.stanford.edu/data/3Dscanrep/
[2] 3D Graphics Development Tools. World Wide Web electronic publication, 2009-06-01. URL
http://www.coin{3}{D}.org/
[3] ex: The Fast Lexical Analyzer. World Wide Web electronic publication, 2009-06-01. URL
http://flex.sourceforge.net/
[4] Qt - A cross-platform application and UI framework. World Wide Web electronic publication, 2009-06-01. URL
http://www.qtsoftware.com/
[5] Alonso-Montes, C.; González: 3D Object Surface Reconstruction Using Growing Selforganised Networks. 2004, s. 163170. [6] Amerijckx, C.; Verleysen, M.; Thissen, P.; aj.: Image compression by self-organized Kohonen map. Neural Networks, IEEE Transactions on, ro£ník 9, £. 3, May 1998: s. 503507, ISSN 1045-9227, doi:10.1109/72.668891. [7] Barhak, J.; Fischer, A.: Adaptive reconstruction of freeform objects with 3D SOM neural network grids. 2001, s. 97105, doi:10.1109/PCCGA.2001.962862. [8] Ciampi, A.; Lechevallier, Y.: Clustering Large, Multi-level Data Sets: An Approach Based on Kohonen Self Organizing Maps. V Principles of Data Mining and Knowledge
Discovery, Lecture Notes in Computer Science, ro£ník 1910, Springer Berlin / Heidelberg, 2000, ISBN 978-3-540-41066-9, ISSN 0302-9743 (Print) 1611-3349 (Online), s. 161177, doi:10.1007/3-540-45372-5_36. URL
http://www.springerlink.com/content/pv83utgrjn0nyubq/
[9] Fritzke, B.: Growing Cell Structuresa Self-Organizing Network in k Dimensions. V
Arti cial Neural Networks, 2, ro£ník II, editace I. Aleksander; J. Taylor, Amsterdam, Netherlands: North-Holland, 1992, s. 10511056. [10] Fritzke, B.: Kohonen Feature Maps and Growing Cell Structures - a Performance Comparison. V Advances in Neural Information Processing Systems 5, Morgan Kaufmann, 1993, s. 123130.
55
56
LITERATURA
[11] Fritzke, B.: Growing Grid - a self-organizing network with constant neighborhood range and adaptation strength. Neural Processing Letters, ro£ník 2, 1995: s. 913. [12] Fritzke, B.: A growing neural gas network learns topologies. V Advances in Neural
Information Processing Systems 7, editace G. Tesauro; D. S. Touretzky; T. K. Leen, Cambridge MA: MIT Press, 1995, s. 625632. [13] Fritzke, B.: Homepage of Bernd Fritzke, 1997. URL
http://www.ki.inf.tu-dresden.de/~fritzke/
[14] Kohonen, T.: Self-organized formation of topologically correct feature maps. Biological
Cybernetics, ro£ník 43, £. 1, January 1982: s. 5969. [15] Le, D.; Thoma, G.; Wechsler, H.: Document classi cation using connectionist models. Jun-2 Jul 1994, s. 30093014 vol.5, doi:10.1109/ICNN.1994.374712. [16] Matthews, J.: Self-Organizing Nets, 10 2004. URL
http://www.generation5.org/content/1999/selforganize.asp
[17] O'Rourke, J.: Computational Geometry in C (Cambridge Tracts in Theoretical Compu-
ter Science). Cambridge University Press, October 1998, ISBN 0521640105.
http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-20&path= ASIN/0521640105 URL
[18] Preparata, F. P.; Shamos, M. I.: Computational Geometry: An Introduction (Monogra-
phs in Computer Science). Springer, August 1985, ISBN 0387961313.
http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-20&path= ASIN/0387961313 URL
[19] do Rêgo, R. L.; Araujo, A.; Lima, F.: Growing Self-reconstruction Maps. Transactions
on Neural Networks, for a peer. [20] Vershinin, Y.: 3D Digital Surface Reconstruction Scanner for Medical Application. Pro-
ceedings of the Fourth IASTED International Conference Signal and Image Processing , 2002: s. 491496. [21] Yu, Y.: Surface Reconstruction from Unorganized Points Using Self-Organizing Neural Networks. V IEEE Visualization 99, Conference Proceedings, 1999, s. 6164.
