Capitolo 5:
RISULTATI E PRESTAZIONI
In questo capitolo vengono presentati i risultati, dal punto di vista qualitativo, ottenuti dal sistema per la generazione di un ambiente virtuale urbano a partire da mappe raster, Successivamente vengono illustrati alcuni esperimenti allo scopo di valutare le prestazioni sulla base di un insieme di parametri significativi fissati preventivamente.
I criteri di valutazione scelti possono essere riassunti in:
• Tempo di generazione della struttura del CityGraph (analizzando separatamente ogni singolo algoritmo)
• Complessità del CityGraph.
• Complessità della geometria generata in output.
Il primo parametro risulta utile al fine dell’analisi delle prestazioni per valutare l’efficacia del sistema e la sua scalabilità. Questa valutazione viene effettuata prendendo in esame alcuni esempi generati dal sistema riguardanti la stessa città con un livello di dettaglio differente: i modelli considerati sono infatti generati a partire da una rete viaria composta da un numero crescente di strade. I modelli, di conseguenza, rappresentano porzioni della città di aree di estensione diverse; ciò implica che, pur mantenendo un fissato dettaglio di modellazione, ogni modello è composto da un numero crescente di elementi.
verranno generati a partire dal CityGraph. Si può immaginare, peraltro, di mantenere residenti sui client un insieme di texture generiche che possano fungere da livello di base, in attesa, o in sostituzione, delle altre specifiche texture. Anche in questo caso l’analisi viene effettuata sulla base di vari modelli della stessa città di diverso livello di dettaglio e si articola procedendo ad un confronto tra le dimensioni dei singoli file generati.
Il terzo parametro invece, serve a valutare la complessità del modello 3D generato a partire dalla descrizione del CityGraph e, dunque, le sue caratteristiche di dettaglio e la sua utilizzabilità per la navigazione interattiva.
5.1. Risultati
ottenuti
5.1.1.
Riconoscimento rete stradale
Sono stati presi in esame i risultati ottenuti con due diverse mappe digitali, la prima consistente in una mappa ad alta qualità della zona del centro storico di Pisa (risoluzione 2813x2076 pixel) [figura 5.1], con colori ben definiti e diversificati, la seconda nel risultato di una scansione a bassa qualità di una mappa stradale di Pontedera (risoluzione 1158x859 pixel) [figura 5.5]. Nel primo caso, come era lecito aspettarsi, il risultato ottenuto è stato piuttosto soddisfacente. Sono state riconosciute quasi tutte le strade, le piazze e gli isolati, e le rispettive dimensioni rispecchiano in maniera accettabile la mappa originale. [figura 5.4] [figura 5.3].
L’unico problema rilevante riguarda l’interruzione di alcune strade, dovuta a scritte troppo invadenti nell’immagine originale, oppure a ponti e sottopassaggi (fiumi ferrovie ecc), che “interrompono” il colore sull’immagine originale [figura 5.2]. Questo, oltre a modificare la rete viaria, rende difficoltoso anche il riconoscimento degli isolati, provocando la fusione di due o più isolati reali in uno solo. In questo caso l’intervento manuale sul City Graph attraverso l’editor, può correggere l’errore.
figura 5.1 - mappa a colori di Pisa
a – mappa originale b – mappa generata dal programma
Le seconda mappa [figura 5.5] invece, come prevedibile, ha generato un serie di problemi a partire dal primo step del programma: il cleaning. Il risultato di tale processo viene mostrato in [figura 5.6a].
figura 5.5 - mappa della rete stradale di Pontedera, ottenuta da scansione
Il problema è da imputarsi a diverse caratteristiche di questa mappa: l’eccessiva disomogeneità dei colori, dovuta a una cattiva scansione, il colore di sfondo molto simile al colore delle scritte da rimuovere e la risoluzione piuttosto bassa dell’immagine (ogni piccola “sbavatura” viene in questo modo amplificata). [figura 5.6b]
a – mappa di Pontedera dopo il cleaning automatico
b – particolare della mappa di Pontedera
figura 5.6 – cleaning automatico mappa di Pontedera
Per ovviare a questo problema, la mappa originale è stata “ripulita” attraverso un programma evoluto di fotoritocco [figura 5.7a], mediante l’applicazione di una serie di selezioni e filtri automatici, e poi passata nuovamente all’algoritmo di cleaning automatico [figura 5.7b]. In questa seconda mappa si è cercato di contrastare maggiormente i colori delle varie entità, pur lasciando volutamente alcune imperfezioni, come il reticolo delle coordinate e alcune scritte piuttosto ingombranti.
a -Mappa ritoccata manualmente prima del processo di cleaning automatico
b - Mappa ritoccata manualmente dopo il processo di cleaning automatico
Con la mappa così modificata, gli algoritmi successivi riescono a riconoscere abbastanza bene strade, incroci, isolati e piazze [figura 5.8]. Data la scarsa risoluzione dell’immagine, può capitare che un gruppo di strade molto vicine vengano riconosciute come piazza, oppure vengano rimosse in fase di ottimizzazione. Permane il problema delle strade interrotte, qui amplificato dalle scritte molto ingombranti nella mappa di input e dalle linee delle coordinate, che in fase di cleaning, in alcuni casi assumono il colore dello sfondo anziché della strada attraversata.
5.1.2.
Generazione del modello 3D
L’analisi dei risultati riguardanti la fase di generazione del modello tridimensionale, può essere fatta sulla base di un campione di immagini riportato di seguito. In esse sono raffigurati alcuni screenshot nei quali sono visibili porzioni del modello generato sulla base della rete viaria ricreata a partire dalla mappa raster della città di Pisa (la stessa dell’esempio precedente [figura 5.1]). A scopo dimostrativo (non rientrando negli obiettivi di questa tesi), è stata data anche una rappresentazione semplificata dei diversi isolati, usando diversi colori per le varie tipologie (ricavate dalla mappa) e laddove presenti estraendo informazioni relative alle altitudini degli edifici da un apposito DTM. Strade, piazze e incroci sono stati invece modellati con più cura, considerando però che i modelli creati da questo sistema hanno volutamente dimensioni contenute in termini di complessità geometrica e occupazione di memoria e risultano, dunque, adatti per applicazioni in tempo reale e per applicazioni distribuite.
Nelle figure seguenti, sono mostrati due esempi di navigazione all’interno del modello effettuati usando il software XVR. Nel primo, [figura 5.9] viene mostrata in dettaglio la texturizzazione e l’inclinazione delle strade e degli altri elementi riguardanti la rete viaria attraverso la visualizzazione di alcuni particolari della città generata. Successivamente, vengono messi a confronto due screenshot riguardanti una vista aerea del modello. Il primo [figura 5.10] è stato ricavato unicamente dai dati contenuti nei DTM (ad ogni altezza è stato assegnato un punto colorato sullo schermo), il secondo [figura 5.11] invece è stato estrapolato dal modello generato. Questo confronto rende bene l’idea della bontà del modello generato, relativamente alle varie tipologie di isolati e alla rete viaria.
figura 5.9 - Alcuni scorci della città virtuale generata
figura 5.11 – Rappresentazione virtuale di Pisa
5.2. Generazione del CityGraph
Al fine di misurare il tempo richiesto per l’estrazione automatica dei componenti del CityGraph da un’immagine in input, sono stati effettuati due differenti test su due diverse macchine.
5.2.1.
Test 1
Il test consiste nella generazione del CityGraph con tre diversi livelli di dettaglio della stessa mappa (per il test è stata considerata una mappa di Pisa centro) [figura 5.12]
2813x2076 px 1407x1038 px 704x519 px
figura 5.12 - Immagini usate per il test 1
Il corrispondente CityGraph è risultato composto dal seguente numero di elementi:
Risoluzione mappa # di nodi # di link # di piazze # di isolati
2813 x 2076 2267 1382 121 340
1407 x 1038 1517 1393 53 326
704 x 519 917 870 5 95
tabella 5.1 – Numero di elementi riconosciuti sulla stessa mappa a diverse risoluzioni
Da questo primo risultato del test, si vede quindi che, come era prevedibile, il livello di dettaglio della mappa influenza gli algoritmi di estrazione automatica degli elementi. Questo può derivare o da una considerevole perdita di dettagli della mappa alle varie risoluzioni o dagli artifici dovuti all’anti-aliasing. Gli errori dovuti alla perdita di dettagli si notano soprattutto nel numero delle piazze; infatti, con risoluzioni più piccole ci sono anche meno
nodi (e conseguentemente isolati), infatti la pulizia di una scritta può in taluni casi (soprattutto a risoluzioni minori), decretare l’interruzione non voluta di una strada.
Per quanto riguarda i risultati temporali, i valori ottenuti sono stati i seguenti:
Step dell’algoritmo Tempo(millisec) a 2813
x 2076 Tempo(millisec) a 1407 x 1038 Tempo(millisec) a 704 x 519 1 - Inizializzazione 2672 1000 485 2 - Cleaning 6203 1562 500 3 - Skeletonizzazione 23578 3203 515 4 - Ricerca incroci 344 15 < 0 5 - Ricerca curve 172 79 32 6 - Semplificazione rete 1000 343 93 7 - Ricerca piazza e successiva risemplificazione 312 32 16 8 - Ricerca cicli 31 31 16 9 - Calcolo altitudini 4438 2937 2906 Tempo Totale 38750 9202 4563
Step dell’algoritmo T (millisec) a 2813 x 2076 T (millisec) a 1407 x 1038 T (millisec) a 704 x 519 1 - Inizializzazione 3735 891 219 2 - Cleaning 9218 2328 593 3 - Skeletonizzazione 50297 6203 828 4 - Ricerca incroci 125 47 16 5 - Ricerca curve 218 78 31 6 - Semplificazione rete 1657 813 578
7 - Ricerca piazza e succ. ri semplificazione
687 109 16
8 - Ricerca cicli 47 31 16
9 - Calcolo altitudini 5172 4563 4500
Tempo Totale 71156 15063 6797
Generazione citygraph (PC1) 0 10000 20000 30000 40000 50000 60000 70000 80000 1 2 3 4 5 6 7 8 9 Step Temp o(mi lli sec) PC1 (2813 x 2076) PC1 (1407 x 1038) PC1 (704 x 519)
figura 5.13 - tempo impiegato dopo ogni step per la generazione della roadmap (PC1)
Generazione citygraph (PC2) 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 1 2 3 4 5 6 7 8 9 Step Tem po (mil lisec ) PC2 (2813 x 2076) PC2 (1407 x 1038) PC2 (704 x 519)
Confronto generazione citygraph fra i due Pc del test (2813x2076) 0 10000 20000 30000 40000 50000 60000 70000 80000 1 2 3 4 5 6 7 8 9 Step Tem po (mil lisec ) PC1 (2813 x 2076) PC2 (2813 x 2076)
figura 5.15 - Confronto fra i due pc con la mappa ad alta risoluzione in input
Influenza di ogni singolo step
10000 20000 30000 40000 50000 60000 70000 80000 Te mpo ( m il li se c) Calcolo altitudini Ricerca cicli
Ricerca piazza e successiva risemplificazione Semplificazione rete Ricerca curve Ricerca incroci Skeletonizzazione Cleaning Inizializzazione PC1 PC2
Da questo test risulta quindi evidente che il collo di bottiglia dell’intero processo è rappresentato dal preprocessing dell’immagine: skeletonizzazione e cleaning. In entrambi i PC, alla risoluzione maggiore, richiede più dell’80% del tempo totale. Percentuale che si riduce alle minori risoluzioni. In altre parole il tempo totale per il resto degli algoritmi è di circa soli 21 sec sul PC1 e di 6 sec sul PC2. [figura 5.16]
C’è comunque da considerare che il preprocessing viene eseguito quando il tempo di esecuzione ha minore importanza. Infatti una delle applicazioni più interessanti della modellazione procedurale consiste in applicazioni web o distribuite. In questo caso, la generazione del CityGraph potrebbe avvenire sul lato server, sulla base di informazioni anche più ricche (ad es. già in formato vettoriale) e georeferenziate, delegando al client la sola parte di modellazione procedurale degli elementi tridimensionali a partire dal CityGraph.
Queste considerazioni verranno affrontate in dettaglio nei paragrafi successivi.
5.2.2.
Test 2
Il secondo test consiste nel generare il CityGraph a partire da tre diverse sezioni di dimensione decrescente della stessa immagine (alla stessa risoluzione). L’immagine presa in esame è una mappa di Pisa ad alta risoluzione.
a – 2048x2048 px b – 1024x1024 px c – 512x512 px
Nei limiti del possibile sono state scelte figure, che abbiano una frequenza degli elementi il più possibile comparabile. Il test cerca di scoprire se l’elaborazione di più sottosezioni di un’immagine, può essere preferibile a un’unica elaborazione globale dell’intera mappa.
Risoluzione mappa # di nodi # di link # di piazze # di isolati
2048x2048 1876 1150 99 272
1024x1024 632 377 34 82
512x512 156 92 7 9
tabella 5.4 - Numero di elementi riconosciuti su varie sezioni della mappa
Le mappe scelte contengono all’incirca lo stesso numero di “elementi per area” (escludendo almeno per il momento il numero dei cicli):
Risoluzione mappa # sezioni (64x64 px) # nodi per sezione # link per sezione # piazze per sezione # cicli per sezione 2048x2048 1024 ~2 ~1 ~0,1 (1 ogni 10 sezioni) ~0,3 (3 ogni 10 sezioni) 1024x1024 256 ~2 ~1 ~0,1 (1 ogni 10 sezioni) ~0,3 (3 ogni 10 sezioni) 512x512 64 ~2 ~1 ~0,1 (1 ogni 10 sezioni) ~0,1 (1 ogni 10 sezioni)
tabella 5.5 - numero di elementi rispetto a sezioni di uguale dimensione
Step dell’algoritmo Tempo(millisec) a 2048 x 2048 Tempo(millisec) a 1024 x 1024 Tempo(millisec) a 512 x 512 1 - Inizializzazione 2516 625 156
3 - Skeletonizzazione 9453 2188 500 4 - Ricerca incroci 109 16 16 5 - Ricerca curve 141 46 < 0 6 - Semplificazione rete 1094 47 15 7 - Ricerca piazza e successiva risemplificazione 453 47 < 0 8 - Ricerca cicli 32 16 < 0 9 - Calcolo altitudini 4703 4547 4500 Tempo Totale 25564 9266 5609
tabella 5.6 - Tempi di esecuzione sottosezioni PC (AMD Athlon 1800+ (1,54GHz) RAM 512 Mbyte)
Si può notare che l’andamento del tempo di elaborazione, a differenza di quanto ci si potrebbe aspettare, è subquadratico. Il rapporto fra il tempo di elaborazione fra le mappe risoluzioni successive tende comunque ad aumentare.
Questo sembrerebbe indicare che, oltre una determinata risoluzione della mappa, sia preferibile dividerla ed elaborare ogni singola sottosezione. Chiaramente in questo caso, va aggiunto il tempo necessario per la fusione dei vari sotto-CityGraph trovati. Sarebbe quindi necessario fondere assieme i nodi sui link che si interrompono sul bordo e ricalcolare eventualmente piazze e isolati (soprattutto gli isolati che potrebbero non essere stati riconosciuti perché “interrotti” dal bordo della sottosezione). Ovviamente, affinché ciò sia possibile, è necessaria una corretta geo-referenziazione. Inoltre sussiste il rischio che alcuni dati vadano persi.
Generazione del citygraph 0 5000 10000 15000 20000 25000 30000 1 2 3 4 5 6 7 8 9 Step Tem po (mil lisec ) 2048 x 2048 1024 x 1024 512 x 512
figura 5.18 - Generazione del CityGraph per le tre diverse sottosezioni
5.3. Generazione 3D della rete stradale
Nonostante la generazione del modello 3D sia un processo molto veloce, sono comunque riportati i risultati ottenuti. E’ particolarmente interessante il confronto fra i possibili files descrittivi della roadmap. Uno descrive la geometria vera e propria del modello 3D, l’altro si limita a descrivere le strutture dati e le classi facenti parte del CityGraph .
# link # poligoni Dimensione CityGraph serializzato (ASCII) Tempo stimato di download ADSL 640 Kbps Dimensioni file di descrizione geometria 3D (ASCII) Tempo stimato di download ADSL 640 Kbps Tempo di generazione geometria 3D
1054 3839 67,5 Kbytes 844 millisec 580,8 Kbytes 7260 millisec 140 millisec
1371 5691 99,2 Kbytes 1240 millisec 861 Kbytes 10762 millisec 203 millisec
1382 7967 148 Kbytes 1850 millisec 1205,3 Kbytes 15066 millisec 266 millisec
tabella 5.7 - Vari aspetti della rete stradale in funzione del # link, PC (AMD Athlon 1800+ (1,54GHz) RAM 512 Mbyte)
Complessità poligonale roadmap
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 92 377 1054 1371 1382 # link # po ligo n i Dimensione Files 0 200 400 600 800 1000 1200 1400 92 377 1054 1371 1382 # link fi le s ize (K b y te ) File vertici Serializzazione citygraph
Tempo generazione roadmap 3D
0 50 100 150 200 250 300 92 377 1054 1371 1382 # link Tem po ( m ill isec)
Stima del tempo per la creazione del modello 3D in applicazioni di rete (ADSL 640Kbps)
0 2000 4000 6000 8000 10000 12000 14000 16000 92 377 1054 1371 1382 # link Tem po ( m ill isec) Download Geometria
Download del CityGraph + generazione "on the fly"
figura 5.19 - grafici che illustrano la generazione 3D della rete stradale
I risultati [figura 5.19] mostrano che l’incremento della complessità poligonale, del tempo di generazione della roadmap 3D e delle dimensioni dei files contenente i dati per la visualizzazione in 3D sono lineari. Dimostrano anche la convenienza di poter rappresentare il CityGraph serializzato in un file di dimensioni notevolmente minore rispetto ad un file che riporti la descrizione geometrica del modello, rendendo di conseguenza minore anche l’eventuale tempo di download.
In realtà il tempo di download del file che serializza il CityGraph va sommato al tempo di generazione del modello (da effettuare quindi on the fly). I tempi sono comunque nettamente inferiori al download del file contenente la geometria del modello.
