Strabo

Salvatore Sanfilippo <antirez@gmail.com>
Revisione 1.0 del 24 Ottobre 2008

Strabo: modello generale di funzionamento

Strabo è un programma scritto in linguaggio ANSI-C, dunque in grado di essere compilato ed eseguito su computer Winodws, Mac OS e Linux. Il programma non possiede una interfaccia utente, viene lanciato direttamente dalla linea di compando con dei parametri che ne determinano il funzionamento.

Il compito di Strabo è quello di trasformare le DEM in formato HGT in altri elaborati di sintesi come ad esempio DEM in formato diverso, curve di livello, modelli 3D. Una DEM in formato HGT comprende solo una piccola parte di territorio che a volte non è sufficiente per la creazione degli elaborati necessari ad un determinato studio. Strabo ha la capacità di affiancare diversi HGT in maniera automatica senza l'utilizzo di software ausiliari.

Parmetri della linea di comando

Strabo ha una sua semplice grammatica che deve essere utilizzata per specificare le DEM HGT da utilizzare in input e gli output che il programma deve produrre. Ad esempio un utilizzo tipico è ben rappresentato dalla seguente linea di comando:

strabo n37e014.hgt-n36e015.hgt curves

Il primo argomento (che segue il nome del programma) è n37e014.hgt-n36e015.hgt ed indica a Strabo di caricare in memoria le DEM che includono il territorno compreso nel rettangolo tra il vertice in alto a sinistra alle coordinate 37' Nord 14' Est e il vertice in basso a destra alle coordinate 35' Nord e 16' Est. Nella pratica, poichè ogni DEM HGT è un quadrato di un grado, Strabo caricherà i seguenti quattro file in memoria:

n37e014.hgt
n37e015.hgt
n36e014.hgt
n36e015.hgt

Il secondo argomento è la parola curves che indica al programma l'elaborato da produrre. Nel nostro caso le curve di livello. Ecco l'output generato dal programma in questo caso (si noti che l'immagine è stata diminuita di dimensione e di qualità):

L'esempio appena visto è particolarmente semplice, a volte è necessario utilizzare più parametri per ottenere degli elaborati specifici. Segue una linea di comando più complessa.

strabo n37e014.hgt-n36e015.hgt curvestep 250 curves utm prescaling 4

Questa linea di comando aggiunge l'opzione curvestep 250 che indica a Strabo di tacciare le curve di livello con un passo di 250 metri invece del default di 100 metri, utm che indica di eseguire la proiezione UTM, e prescaling 4 che indica di scalare la DEM di un fattore 4 per ogni lato prima di utilizzarla, al fine di ottenere un elaborato di dimensioni minori. Ecco l'output prodotto:

Strabo supporta una varietà di opzioni e tipi di elaborati in aggiunta a quelli visti in questi esempi. Alcuni saranno approfonditi nei paragrafi seguenti di questo capitolo, per una lista completa si rimanda all'help prodotto dal programma quando viene eseguito senza alcun argomento.

Formati di output

Strabo utilizza come formato di output per le immagini lo standard TIFF, mentre i modelli tridimenzionali sono generati in VRML. Questi due formati aperti consentono la massima interoperabilità con gli altri programmi. La TIFF è geneata in RGB, 32 bit per pixel. Il VRML segue lo standard 2.0 che è ad oggi il più diffuso ed utilizzato.

Il VRML tecnicamente permette di generare una mesh tridimensionale utilizzando diverse direttive.

Algoritmo di riconoscimento della linea di costa

I file HGT non includono informazioni sulla linea di costa, sono mere DEM la cui unica informazione è l'altezza in metri ad ogni determinato punto della griglia. Tuttavia Strabo produce alcuni elaborati come le curve di livello e le texture che necessitano di tracciare la linea di costa o di colorare la superficie dell'acqua in maniera diversa. Per questi motivi Strabo implementa un algoritmo di riconoscimento del mare e della linea di costa che anche se molto semplici si sono rivelati precisi in praticamente tutti i casi di utilizzo reale trattati fino ad ora (che coprono grosso modo tutta la superficie italiana).

L'algoritmo di riconoscimento della linea di costa utilizza come input l'output prodotto dall'algoritmo del riconoscimento della superficie del mare, per cui descriverò prima quest'ultimo.

L'approccio più ovvio per capire se un dato punto è di mare o no è quello di controllarne la quota: gli HGT sono stati generati ed editati in modo che gran parte della superficie del mare risulti a quota zero metri. In realtà per via di aree di depressione presenti all'interno delle terre emerse tale approccio è subottimale, tutta mentre il mare è stato livellato a quota zero in maniera forzata e risulta dunque regolare i punti a quota zero all'interno delle terre emerse sono quasi sempre isolati. Il nostro algoritmo di riconoscimetno del mare risolve il problema marcando come punto di mare un dato punto a quota zero solo se i suoi quattro immediati confinanti (a sinistra, a destra, in alto e in basso) sono a quota zero. Per generare una immagine della sperficie del mare con Strabo basta utilizzare l'opzione sea nella linea di comando.

Il riconoscimento della linea di costa si ottiene applicando il seguente algoritmo alla superficie del mare: un punto appartiene alla linea di costa se è un punto di terraferma al confine con almeno un punto di mare. Per generare una immagine della linea di costa con Strabo si utilizza l'opzione coastline, e l'immagine seguente è un esempio dell'output che si ottiene sugli HGT che comprendono la Sicilia.

Algoritmo di estrazione delle curve di livello

Essendo la DEM in HGT una modello digitale di elevazione del territorio contiene molte più informazioni delle curve di livello dal punto di vista strettamente matematico, tuttavia il tacciamento delle curve di livello partendo dai dati altimetrici dei singoli punti, per loro natura discreti, necessita di algoritmi che producano dei risultati leggibili in forma di linee continue chiuse.

Dal punto di vista formale il modo migliore per tracciare le curve di livello consiste nel creare un modello tridimensionale in memoria utilizzando i dati della DEM e tracciare il contorno dell'intersezione tra questo e dei piani che tagliano il modello a 50, 100, 150 metri e così via (prendendo come esempio delle curve a 50 metri di passo). Questo algoritmo è complesso da implementare e specialemnte lento dunque abbiamo tentato di trovare degli algoritmi diretti che operano sulla DEM ma capaci di produrre risultati equivalenti.

Immaginando la DEM come continua e non discreta si potrebbe pensare di accendere tutti i punti che hanno come altezza 50 metri, poi 100 metri e così via. Ciò non è possibile perchè la DEM è discreta dunque magari anche se nel territorio esste un punto a cinquanta metri noi potremmo vedere semplicemente due punti adiacenti a 48 e a 52 metri. Il modo più semplice per estendere questo algoritmo in modo che funzioni con una DEM è accendere un dato punto se è "intorno" ai 50 metri (con una determinata tolleranza di errore). Tale algoritmo non è ottimale, produce delle curve di livello ma frastagliate e con spessori variabili. Il nostro scopo era ottenere curve composte da linee continue di spessore un pixel in modo da essere chiare e permettere di usare passi estremamente contenuti. A questo proposito si ricordi che anche se l'errore assoluto degli HGT è di 17 metri circa l'errore relativo nella pratica è estremamente contenuto, per cui Strabo può tracciare curve anche a 25 metri di passo leggibili su zone sostanzialmente pianeggianti con rilievi che hanno una pendenza poco pronunciata.

Fortunatamente esiste un algoritmo che è equivalente alla intersezione tridimensionale ma che può essere eseguito ad una velocità molto più alta (strabo può ottenere curve di livello di superfici molto grandi quasi istantaneamente). Infatti un piano interseca un dato punto della proiezione 3D della DEM solo se la DEM in un dato punto è esattamente alla stessa quota del piano o tutte le volte in cui si vede un salto tra due punti adiacenti della DEM che includono la quota del piano. Ad esempio un salto da 48 a 52 metri tra due punti adiacenti implica necessariamente che tra tali due punti esiste un punto nello spazio reale che è a quota cinquanta metri. Tuttavia tale salto di quota può essere orientato in qualunque modo: orizzontale, verticale, o in uno qualunque degli angoli da zero a 360 gradi, tuttavia è dimostrabile che eseguendo una scansione della DEM con due diversi angoli, tra di loro ortogonali, possono essere rilevati tutti i salti di quota per ogni determinato piano immaginario di intersezione.

L'algoritmo finale esegue dunque una scansione orizzontale, da sinistra a destra, e marca ogni punto che è esattamente alla quota del piano con cui stiamo tagliando virtualmente la DEM, e qualunque punto che ha a destra un punto il cui salto di altezza deve necessariamente includere la quota del piano. Lo stesso processo viene poi implementato con una scansione verticale dall'alto in basso. Il risultato finale sono delle curve di livello nitide di dimensione un pixel.

Vettorializzazione delle curve di livello

Strabo produce curve di livello in formato Raster, tuttavia può essere molto interessante in diversi casi avere delle curve di livello in formato vettoriale. A tale scopo può essere utilizzato un software di vettorializzazione. Anche se leggibili e continue le curve di livello prodotte da Strabo sono spesse un solo pixel. Alcuni software di vettorializzazione hanno dei problemi a seguire il tracciato di curve così sottili. A questo scopo abbiamo rilevato empiricamente che basta aumentare la dimensione dell'immagine con un programma di grafica di un fattore 4 per permettere ai programmi di vettorializzazione un riconoscimento molto accurato delle curve.

Correzione degli errori tramite l'interpolazione

In media le DEM in formato HGT sono di alta qualità, tuttavia ci sono alcuni punti in cui per diversi problemi tecnici le informazioni sono mancanti. Tale problema solitamente trascurabile in alcune parti del territorio italiano e in molte altre parti del territorio mondiale risultano un problema non indifferente. Si veda ad esempio il livello di errore presente in tale quadrante:

Per ovviare al problema abbiamo provato ad implementare diversi metodi di interpolazione che avessero l'effetto di correggere gli errori. Ovviamente Strabo non può sapere quali sono le quote dei punti mancanti perchè tali informazioni non sono materialmente presenti nell'HGT, ma può, basandosi sul contesto, fare una predizione quanto più accurata possibile. Ecco ad esempio il risultato prodotto dalla opzione fix di Strabo sul precedente quandrante:

I risultati della interpolazione di Strabo hanno superato le nostre più rosee aspettative e siamo convinti che potrebbero essere applicate ad una estenzione di Strabo capace di lavorare su modelli su scala più piccola ottenuti dalla nuvola di punti che gli scanner laser possono generare.

Ecco la descrizione dell'algoritmo di interpolazione. Per ogni dato punto mancante Strabo esegue due interpolazioni, una verticale e una orizzontale, che sono concettualmente identiche ma ruotate di 180 gradi dunque per semplicità descriveremo solo l'interpolazione orizzontale. Dato un punto rotto Strabo cerca il primo punto valido a sinistra e a destra, e stima la quota al punto rotto tramite una semplice interpolazione lineare. Lo stessso algoritmo viene utilizzato verticalmente, e alla fine viene fatta la media tra le due altezze ottenute. Tale algoritmo può essere migliorato in futuro implementando una interpolazione che utilizza delle spline e/o aumentando il numero di angoli di interpolazione utilizzati.

Prescaling

Nel corso del lavoro è diventato chiara la necessità di produrre degli elaborati utilizzando Strabo su porzioni di territorio molto vaste. Poichè un solo quadrante dell'HGT contiene già 1201 per 1201 punti, ovvero circa un milione e mezzo di quote, e per alcuni elaborati sono stati necessari diverse decine di quadranti, i tempi di elaborazione e la memoria utilizzata sarebbe stata in molti casi un limite che non avrebbe permesso l'utilizzo di Strabo.

Tale problema è stato superato utilizzando il Prescaling. In pratica tramite l'opzione prescaling di strabo è possibile specificare al software di caricare gli HGT in formato ridotto. Ad esempio se il prescaling è settato ad un fattore quattro ogni HGT caricato utilizzerà soltanto circa novantamila quote invece che un milione e mezzo. Ciò non solo permette di avere in output elaborati di dimensioni più gestibili ma aumenta in maniera esponenziale la velocità della elaborazione, diminuendo sempre in maniera esponenziale la memoria necessaria alla produzione degli elaborati.

Attualmente il prescaling salta i punti non utilizzati. Nelle future versioni sarebbe auspicabile utilizzare degli algoritmi di interpolazione in modo da perdere meno informazioni. Non è tuttavia chiaro se ciò risulterebbe in un aumento della qualità degli output che sono già assolutamente adeguati a molti degli impieghi che abbiamo cercato di immaginare.