Correlatore
-Committente
-Corso di laurea
Ingegneria informatica
ModuloM00002 - Progetto di diploma
Anno2017/18
DataIndice
1 Abstract 1 2 Progetto assegnato 3 2.1 Descrizione . . . 3 2.2 Compiti . . . 3 2.3 Obbiettivi . . . 4 2.4 Tecnologie . . . 4 3 Introduzione 5 3.1 Scanner 3D . . . 6 3.2 Fotogrammetria . . . 73.3 Formati point cloud . . . 7
4 Point cloud renderer 11 4.1 Octree . . . 11
4.2 Potree converter . . . 13
4.3 Funzionalità di Potree . . . 15
4.4 Informazioni utili per interagire con Potree . . . 17
5 Sviluppo 21 5.1 Conversione WGS84 a LV95 . . . 21
5.2 Movimento della camera . . . 23
5.3 Calcolo altitudine per camera . . . 25
5.4 Rilevazione ostacoli . . . 26
5.5 Lettura coordinate GPS - Firebase . . . 29
5.6 Pulizia point cloud . . . 30
6 Risultati e conclusione 35 6.1 Risultati . . . 35
6.2 Difficoltà incontrate . . . 38
Elenco delle figure
3.1 Stanford bunny . . . 5
3.2 Leica lidar . . . 6
3.3 Point cloud acquisito da un lidar Leica . . . 6
3.4 Drone Phantom 4 . . . 7
3.5 Zona di Cornaredo . . . 8
3.6 Zona di Cornaredo da vicino . . . 8
4.1 LOD in un octree . . . 12
4.2 Point cloud di esempio "Lion" su Potree . . . 13
4.3 Octree di Potree nel filesystem . . . 14
4.4 Octree boxes . . . 15
4.5 Punto selezionato . . . 15
4.6 Distanza misurata . . . 16
4.7 Volume clipping . . . 16
4.8 Features . . . 17
4.9 Struttura root in Chrome . . . 19
5.1 WGS84 . . . 21
5.2 Conversione WGS84->LV95 . . . 22
5.3 South S660P . . . 23
5.4 Prova di segmentazione . . . 27
5.5 Rilevazione di ostacoli . . . 28
5.6 Percorso effettuato dai dati . . . 30
5.7 Point cloud originale . . . 30
5.8 Point cloud modificato . . . 31
Capitolo 1
Abstract
Il progetto prevede la realizzazione di un applicazione in grado di visualizzare in un point cloud l’ambiente che circonda un veicolo attraverso l’uso di un apparecchio GPS specifico. L’applicazione deve assistere la guida di veicoli in condizioni di visibilità minima.
Come visualizzatore di point cloud si è optato per Potree, un renderer scritto in javascript che gira su browser grazie al motore grafico WebGL. In questo modo l’applicazione può essere eseguita su diversi sistemi operativi e dispositivi finchè essi sono dotati di un browser. È stato inoltre sviluppato come obbiettivo aggiuntivo un algoritmo che basandosi sull’e-levazione stradale evidenzia gli ostacoli intorno al veicolo. L’approccio risulta comunque più adatto come operazione di pre-processing piuttosto che in real-time a causa del tem-po necessario ad analizzare i punti, che è di circa un secondo per una superficie 400m2 (altamente dipendente dalla densità di punti).
Il progetto dimostra la fattibilità dell’usare un point cloud dell’ambiente circostante come supporto alla guida, sincronizzando la posizione e direzione nel point cloud con quelle reale del veicolo.
The project involves the implementation of an application which can display in a point cloud the surrounding environment of a vehicle thanks to a specific GPS device. The application must assist driving in poor visibility conditions.
Potree was chosen to display point clouds, a renderer written in javascript which can run in all the browsers supporting WebGL. In this way the application can run on a variety of operating systems and devices as long as they have a browser.
As an additional goal an algorithm has been developed which highlights obstacles around the vehicle based on the elevation of the road. This approach however is more suitable to be a pre-processing step instead of being used in real-time because of the time needed to analyse the points, which is about one second for a 400m2surface (highly dependent on the point density).
The project demonstrates the feasibility of using a point cloud of the surrounding environ-ment to assist your driving, synchronising the position and direction in the point cloud with the real ones of the vehicle.
Capitolo 2
Progetto assegnato
2.1
Descrizione
Il progetto richiede lo sviluppo di un navigatore a supporto di veicoli in condizioni estreme di poca visibilità (notte), strada coperta da neve o altri fattori.
L’applicazione richiede la ricostruzione dello scenario virtuale tramite nuvola di punti / mondo 3D. La nuvola di punti è gia definita/conosciuta e memorizzata all’interno del dispositivo (PC o table : da valutare).
Il primo prototipo prevede la visualizzazione dei dati su schemo (tablet / PC), potrà essere valutata anche la visualizzazione dei dati su appositi visori.
La soluzione prevede l’utilizzo di sensori "south surveying" già predisposti per l’invio di informazioni GPS del veicolo a un apposito server poi predisposto per l’invio di queste informazioni all’applicazione in tempo reale.
Requisito fondamentale è quindi la connettività internet sul veicolo (scheda 3G/4G).
Sulla base di queste informazioni l’applicazione dovrà visualizzare l’ambiente circostante, nell’orientamento relativo al movimento del veicolo in modo da permettere all’autista di muoversi correttamente e rimanere nel campo stradale pur non essendo questo visibile e riconoscibile.
Posizione GPS : fornita dai server di Device SA Orientamento : ricavato dalle posizioni nel tempo
Per le tecnologia di rendering si vuole fare affidamento su librerie open source : per es. Potree (potree.org) basate su WebGL quindi utilizzabili all’interno del browser
2.2
Compiti
Sviluppo di un programma di visualizzazione e navigazione all’interno di un "Point Cloud" guidato dalla posizione GPS del veicolo.
2.3
Obbiettivi
Garantire un allineamento fra scena rappresentata sullo schermo e realtà effettiva di quello che il conducente vedrebbe in condizioni reali.
2.4
Tecnologie
• Utilizzo di soluzioni open source per esempio Potree all’interno di un browser o tramite programma ad-hoc (da definire)
• WebGL, Javascript, eventualmente shader code (GLSL)
• Utilizzo di sensori "south surveying" forniti dall’azienda e connessione ai server dell’a-zienda per il recupero delle informazioni GPS
Capitolo 3
Introduzione
Una nuvola di punti, chiamata comunemente point cloud, è un insieme di punti definiti in un determinato sistema di coordinate. Questi punti sono dei vertici identificati da coordinate X, Y, e Z, a volte anche colorati, che nel loro insieme rappresentano superfici di oggetti. Ov-viamente per suggerire l’oggetto che si vuole rappresentare il numero di punti deve essere elevato. Le applicazioni dei point cloud sono principalmente legati agli ambiti della computer grafica, ma si trovano anche applicazioni in campo medico e geografico (GIS).
Uno dei principali vantaggi di optare per un point cloud è poter digitalizzare in modo molto dettagliato una scena reale, mantenendo intatte forme e dimensioni dei vari oggetti per poi poterli analizzare in un secondo tempo.
Una pratica che è comune fare è trasformare delle superfici nel point cloud in mesh così da avere più utilizzi come in progetti di animazione oppure progetti CAD.
Source:http://graphics.stanford.
edu/data/3Dscanrep/
Source:
https://imatge.upc.edu/web/sites/ default/files/pub/cPujol-Miro17.pdf
Figura 3.1: Stanford bunny
Source:
https://en.wikipedia.org/ wiki/3D_scanner
Figura 3.2: Scanner Leica
Source:http://www.revittunes.com/
Figura 3.3: Point cloud acquisito da uno scanner Leica
laser e la fotogrammetria.
3.1
Scanner 3D
La tipologia più utilizzata di laser scanner è il cosiddetto laser a tempo di volo. Questo de-termina la distanza di un oggetto misurando il tempo di andata e ritorno di un impulso di luce. Il laser misura la distanza soltanto del primo punto che esso incrocia, per scanneriz-zare l’intero campo visivo o si ruota il diodo emettitore o si ricorre ad un sistema di specchi rotanti per deviare il raggio. Questi scanner possono arrivare ad una precisione millimetrica e misurare anche fino a 100,000 punti al secondo.
Source:www.techradar.com
Figura 3.4: Drone Phantom 4
3.2
Fotogrammetria
La fotogrammetria non è un termine limitato ai point cloud bensì si riferisce alla tecnica con cui si ottengono delle misurazioni geometriche quali forma, dimensione e posizione di un oggetto mediante l’uso di fotografie, senza quindi emettere impulsi elettromagnetici. Consiste nell’acquisire diverse foto di uno stesso oggetto da angolazioni e posizioni diverse. Dei software processano poi le immagini e trovano i punti in comune così da collegare le varie immagini. In ogni fotografia si può tracciare un raggio tra la posizione della camera ed un punto nella foto, l’intersezione di questi raggi permette di triangolare la posizione dei punti. Un caso speciale di fotogrammetria che usa questo genere di triangolazione si chiama stereofotogrammetria.
Il point cloud che ho usato nella mia tesi è stato acquisito con questo sistema, la camera era montata su un drone DJI Phantom 4.
A causa della lunghezza del point cloud (maggiore di 2km) la figura 3.5 mostra solo tre parti delle dieci totali, la zona soggetta è il quartiere Cornaredo del comune di Lugano.
3.3
Formati point cloud
Esistono diversi modi per immagazzinare i dati di un point cloud e quindi diversi formati di file. Non esiste uno standard unico, però i formati che si usano comunemente sono meno di una decina.
• PLY
Conosciuto come Polygon File Format, esiste una versione binaria compatta ed una ASCII più human readable, entrambe hanno un header dove viene specificato il nu-mero di vertici e poligoni nel file. A parte le coordinate x, y, e z altre informazioni possono essere colore e normale dei vertici. Il seguente è un esempio di point cloud in PLY:
Figura 3.5: Zona di Cornaredo
property float z property float nx property float ny property float nz property float intensity property uchar diffuse_red property uchar diffuse_green property uchar diffuse_blue end_header
13.32 12.84 3.06 -0.352745 -0.230493 0.906887 1 255 243 245 13.44 12.84 3.06 0.135449 -0.0514792 0.989446 1 255 244 242
• PTS
Formato che viene usato tra altri dal software Cyclone della Leica. La prima linee contiene il numero di punti, le altre valori x, y, z, intensità (frazione di luce riflessa), r, g, b. Questo è il formato del point cloud che ho usato.
• PTX
Formato ASCII che utilizza scansioni separate, ognuna con un proprio sistema di coordinate. L’header contiene una matrice di trasformazione per ogni point cloud. Anche questa come PTS ha sette colonne ed è usata tra altri da Cyclone.
Esempio di header: number of columns number of rows
st1 st2 st3 ; scanner registered position sx1 sx2 sx3 ; scanner registered axis ’X’ sy1 sy2 sy3 ; scanner registered axis ’Y’ sz1 sz2 sz3 ; scanner registered axis ’Z’ r11 r12 r13 0 ; transformation matrix
r21 r22 r23 0 ; this is a simple rotation and translation 4x4 matrix
r31 r32 r33 0 ; just apply to each point to get the transformed coordinate tr1 tr2 tr3 1 ; use double-precision variables
Questo è semplicemente come il PTS ma senza il numero di punti come linea iniziale.
• LAS
Uno standard industriale binario per dati provenienti da macchine che usano lidar. Essendo un formato binario non viene qui approfondito, è rilevante comunque il fatto che ha dei bytes dedicati alla classificazione dei punti (terreno, albero...).
• LAZ
Una versione compressa del LAS.
Questa non intende essere una lista completa dei formati di point cloud bensì solo quelli che ho incontrato nel corso del progetto. Fortunatamente esistono dei convertitori tra i diversi formati che funzionano più o meno bene. Menziono Faro Scene LT perchè è l’unico che ho trovato in grado di convertire da ptx a diversi altri formati senza sovraccaricare inutilmente la RAM. Un altro programma che fa il suo dovere è pointzip che converte da ptx/pts a las/laz.
Capitolo 4
Point cloud renderer
Semplicemente avere un file con tanti punti non è molto utile, diventa utile se possiamo visualizzarlo e questo viene dato erroneamente per scontato. Dato l’elevato numero di punti da renderizzare una visualizzazione fluida è possibile solo con un codice performante che magari usa anche algoritmi geometrici astuti.
Un requisito indispensabile per il renderer di cui ho bisogno è che sia open-source dato che devo avere accesso a strutture dati e metodi interni per raggiungere i miei scopi. Un altro requisito non obbligatorio ma che è sicuramente utile è la platform independence, cioè la capacità di un programma di eseguire su sistemi operativi diversi senza cambiare il codice sottostante.
La scelta si è quasi subito fermata su Potree, un visualizzatore standalone che gira su browser tramite WebGL, sia perchè ci sono pochi renderer point cloud che funzionano nel browser (di altri conosco solo plasio), sia perchè offriva una guida veloce su come iniziare a visualizzare un point cloud. Purtroppo il codice sorgente consiste di 22000 e passa linee di codice javascript non documentate il che ha reso la comprensione del programma una sfida di reverse engineering.
Potree, come appena detto, è un renderer di point cloud che gira su browser, è scritto in javascript e utilizza WebGL anche se la maggior parte dell’interazioni col motore grafico sono mediate da Three.js, una libreria ad alto livello che permette di creare animazioni 3D complesse sotto licenza MIT.
4.1
Octree
Potree può visualizzare point cloud in formato las, laz, xyz e pts, però non può visualizzarli direttamente bensì bisogna prima convertire il file in questione in una struttura intermedia utilizzata da Potree, un octree.
Un octree è una particolare struttura ad albero dove ogni nodo figlio ha al massimo 8 figli, ognuno dei quali ha delle coordinate in uno spazio tridimensionale riferite al suo centro.
Source:http://www.cradle-cfd.com
Figura 4.1: LOD in un octree
Partendo dal nodo root che include tutto il volume di una scena, ogni figlio comprende un ottavo del volume del nodo padre. Questa partizione dello spazio permette di creare algoritmi efficienti nel campo della computer grafica come per esempio algoritmi di collision detection dove si riesce ad arrivare ad una time complexity diO(n log n).
Nel caso dei point cloud gli octree vengono usati per cercare in modo efficiente quali punti sono vicini ad un dato punto, ma soprattutto per decidere il livello di dettaglio con il quale renderizzare dei punti (level of detail, LOD).
Un approccio usato è il seguente: in base alla distanza di un nodo dalla camera, la gerarchia del nodo verrà percorsa più in profondità o meno. Se la camera si avvicina al nodo allora la gerarchia verrà percorsa più in profondità e verranno quindi renderizzati i punti associati a un maggiore livello di dettaglio, che tenderanno a essere anche più numerosi. In questo modo se la camera è lontana da un nodo i punti in esso contenuti verranno renderizzati con un LOD minore ma la differenza di dettaglio è viene mascherata dal fatto che la camera è lontana.
Figura 4.2: Point cloud di esempio "Lion" su Potree
4.2
Potree converter
Nella pagina github di Potree1è anche possibile trovare il programma Potree Converter che si occupa di convertire il point cloud (las, pts, ...) in un octree. La seguente linea mostra come eseguire il programma su windows convertendo un file las in una gerarchia octree e generando una pagina html che permette di visualizzare il point cloud.
1 # convert data . las and generate web page .
2 ./ PotreeConverter . exe C:/ data . las -o C:/ potree_converted -p pageName In particolare, il comando che io ho eseguito per convertire tre parti su dieci del point cloud di Cornaredo è il seguente:
1 ./ PotreeConverter . exe .\ cassarate \1. pts .\ cassarate \2. pts .\ cassarate \3.
pts
2 -o \ cassaratePotree123 -p cassaratePage -f xyzirgb --projection "+ proj =
somerc + lat_0 =46.95240555555556 + lon_0 =7.439583333333333 + k_0 =1 + x_0 =2600000 + y_0 =1200000 + ellps = bessel + towgs84 =674.
3 374 ,15.056 ,405.346 ,0 ,0 ,0 ,0 + units =m + no_defs "
Il parametro -f indica il formato del file mentre --projection è una piccolezza che indica la proiezione da usare per le coordinate affinchè la mini-mappa di OpenStreetMap in alto a
Figura 4.3: Octree di Potree nel filesystem
sinistra nella pagina html mostri il luogo esatto. La posizione dei punti non è influenzata da questo parametro.
Nel filesystem l’octree generato ha una struttura come quella in figura 4.3. Ogni file rap-presenta un nodo e il suo nome indica la posizione gerarchica, la radice è indicata con la lettera "r". Quindi il file chiamato "r006.bin" indica che per raggiungere quel nodo bisogna percorrere r, il figlio 0, il figlio 0 e il figlio 6. Per capire meglio si consideri la figura 4.4, i cubi gialli sono la rappresentazione grafica dei nodi, il cubo più piccolo che si vede contiene i punti presenti nel file "r44". Il motivo per cui non ci sono i nodi r1, r3, r5, r7 è che non ci sono punti in quelle zone, sopra i nodi 0, 2, 4, 6 ci sarebbero rispettivamente 1, 3, 5 e 7. Questo partizionamento del volume rende possible caricare solo un sottoinsieme dei punti del point cloud in RAM in un determinato istante, caricare tutti i punti sarebbe tecnicamente impossibile su un computer medio con un point cloud modesto che può anche superare i 100GB.
Figura 4.4: Octree boxes
4.3
Funzionalità di Potree
Potree non offre solo la possibilità di visualizzare un point cloud ma anche altre funzionalità tra quali le seguenti.
• Selezionare un punto
Figura 4.5: Punto selezionato
Figura 4.6: Distanza misurata
• Isolare regioni di punti
Figura 4.7: Volume clipping
Figura 4.8: Features
come quelle in figura 4.8.
Point budget è una variabile indicante a grosso modo il numero di punti da renderiz-zare. Aumentando questa variabile i nodi dell’octree in lontananza vengono percorsi più a fondo, portando ad un numero maggiore di punti renderizzati e quindi maggiore dettaglio.
Field of view (FOV) è l’estensione della scena visibile in un dato momento.
Eye-Dome-Lightning è una tecnica di ombreggiatura che aumenta la percezione della profondità, i bordi risultano più marcati.
Background come dice il nome è l’immagine da visualizzare che racchiude il point cloud.
La splat quality determina la forma dei punti. Una standard quality farà si che ogni punto del point cloud sarà renderizzato come quadrato, mentre una high quality ren-derizza i punti come circonferenze.
Min node size indica la grandezza minima dei punti. Incrementandola aumentano di dimensione i punti.
La checkbox "Box" permette di visualizzare i nodi dell’octree.
"Lock view" blocca il livello di dettaglio che si ha quando viene attivata. Quindi se sia-mo lontani dal point cloud, mettiasia-mo la spunta su lock view e ci avviciniasia-mo, vedresia-mo un livello di dettaglio scarso, che era quello di quando eravamo ancora lontani.
4.4
Informazioni utili per interagire con Potree
Dato che il codice di Potree non è documentato pongo qui alcune informazioni utili per interagire con i punti del point cloud. La struttura dati che da accesso ai dati di Potree è:
1 window . viewer = new Potree . Viewer ( document . getElementById ( 2 " potree_render_area "));
Questa linea fa parte del codice che viene generato insieme alla pagina html quando si usa Potree Converter. Per una visualizzazione della gerarchia di alcune delle seguenti strutture dati guardare la figura 4.9.
• viewer.scene.view è l’oggetto che controlla la camera di three.js. Tra gli attributi che
contiene ci sonodirection e position della camera, entrambi di tipo THREE.Vector3.
• viewer.scene.pointclouds è l’array che contiene i vari point cloud. Io ho sempre
lavorato con un solo point cloud quindi accedo sempre all’elemento 0.
• viewer.scene.pointclouds[0].root è la radice del point cloud. Il campo children
contiene i vari nodi figli.
• viewer.scene.pointclouds[0].matrixWorld contiene la matrice con qui bisogna
mol-tiplicare alcune matrici di oggetti per ottenere le world coordinates (tipo le bounding sphere dei nodi).
• viewer.scene.pointclouds[0].root.geometryNode.geometry.attributes è un
ogget-to BufferGeometry che contiene gli attributi dei punti quali posizione e colore.
• node.sceneNode.matrixWorld, dove node è un certo nodo, rappresenta la matrice
che deve essere moltiplicata per i punti di quel nodo per ottenere le world coordinates dei punti.
• viewer.scene.pointclouds[0].visibleNodes contiene tutti i nodi visibili dalla camera.
• node.geometryNode contiene anche la bounding sphere e bounding box del nodo.
• viewer.scene.pointclouds[0].nodesOnRay(viewer.scene.pointclouds[0].visibleNodes, ray); restituisce i nodi la cui bounding sphere interseca un dato raggio.
• node.geometryNode.geometry.attributes.position.array è il luogo dove
effettiva-mente sono scritte le posizioni dei punti in un nodo.
• node.geometryNode.geometry.attributes.color.needsUpdate=true è il comando da
eseguire una volta cambiata una proprietà affinchè le modifiche vengano apportate (in questo caso il colore). Il seguente snippet cambia il colore dei primi tre punti di un nodo in rosso.
1 for (let i = 0; i < 3; i ++) {
2 node . geometryNode . geometry . attributes . color . array [i * 3] = 255; 3 node . geometryNode . geometry . attributes . color . array [i * 3 + 1] = 0; 4 node . geometryNode . geometry . attributes . color . array [i * 3 + 2] = 0; 5 }
Capitolo 5
Sviluppo
5.1
Conversione WGS84 a LV95
I dispositivi GPS, quindi anche quello che ho usato io, lavorano con coordinate che si rife-riscono al World Geodetic System 1984, uno standard che viene usato in ambiti tra i quali navigazione satellitare e cartografia. Esso ha l’origine nel centro di massa della Terra, il meridiano di riferimento è quello di Greenwich.
Source:http://code7700.com/wgs-84.htm
Figura 5.1: WGS84
Per le formule matematiche mi sono basato sul documento "Formulas and constants for the calculation of the Swiss conformal cylindrical projection and for the transformation between coordinate systems", rilasciato dalla Swiss Federal Office of Topography1.
Quello che segue è un estratto del documento che è poi la parte da me implementata.
Figura 5.2: Conversione WGS84->LV95
Il dispositivo GPS usato in questo progetto è un South S660P, dispone di un’interfaccia web accessibile collegandolo con un cavo micro-USB, dove è possibile cambiare la configurazio-ne del dispositivo come ad esempio l’hotspot a cui collegarsi per accedere a interconfigurazio-net, dove inviare le coordinate, e varie impostazioni legate alla navigazione satellitare.
Source:http://www.southinstrument.com
Figura 5.3: South S660P
5.2
Movimento della camera
Per muovere la camera tra una coordinata e la successiva ho deciso di usare TweenJS, libreria di cui ho scoperto l’esistenza analizzando il sorgente di Potree (in Potree viene usata per animare lo zoom in/out). TweenJS serve a fare tweening, termine usato nell’animazione computerizzata per indicare il processo di generazione di frame intermedi tra un fotogramma iniziale ed uno finale, in questo modo lo spostamento della camera non è istantaneo ma avviene in modo più naturale. Dato che il dispositivo GPS a volte segna leggere variazioni di posizione anche se fermo, prima di muovere la camera controllo che il vettore spostamento sia lungo almeno 0.5 metri.
1 async function followGPS (nextX , nextY , nextZ ) {
2 // stableX and stableY are the last valid coordinates received
3 if ( stableX == 0 && stableY == 0) { 4 viewer . scene . view . position . setX ( nextX ); 5 viewer . scene . view . position . setY ( nextY ); 6 viewer . scene . view . position . setZ ( nextZ );
7 // When I receive the first coordinate I can 't know the direction yet , so
I set a fixed one .
8 viewer . scene . view . lookAt ({ 9 x: 2717978 ,
10 y: 1098162 ,
11 z: 300
12 });
14 stableY = nextY ; 15 return;
16 } 17
18 let deltaX = nextX - stableX ; 19 let deltaY = nextY - stableY ;
20 if ( Math . sqrt ( Math . pow ( deltaX , 2) + Math . pow ( deltaY , 2)) > 0.5 && Math .
sqrt ( Math . pow ( deltaX , 2) + Math . pow ( deltaY , 2)) < 100) {
21 viewer . scene . view . lookAt ({ 22 x: nextX ,
23 y: nextY , 24 z: nextZ 25 });
26 setupCameraPositionTween ({
27 x: viewer . scene . view . position .x, 28 y: viewer . scene . view . position .y, 29 z: viewer . scene . view . position .z 30 }, { 31 x: nextX , 32 y: nextY , 33 z: nextZ 34 }, 35 500) ; 36 stableX = nextX ; 37 stableY = nextY ; 38 } 39 } 40
41 function setupCameraPositionTween ( source , target , duration , delay , easing
) {
42 var l_delay = ( delay !== undefined ) ? delay : 0;
43 var l_easing = ( easing !== undefined ) ? easing : TWEEN . Easing . Linear . None
;
44
45 new TWEEN . Tween ( source ) 46 .to( target , duration ) 47 . delay ( l_delay ) 48 . easing ( l_easing ) 49 . onUpdate (function() {
50 // copy incoming position into camera position
51 viewer . scene . view . position . copy ( source ); 52 })
53 . start (); 54 }
riassunto come segue:
• Uso una funzione di potree che restituisce i nodi che intersecano un dato raggio, passando come argomento i nodi visibili dalla camera (nel frustum) e un raggio che ha come origine la posizione della camera e direzione z=-1
1 let camPosition = viewer . scene . view . position ; 2 let raycaster = new THREE . Raycaster (); 3 let ray = raycaster . ray ;
4 ray . direction ={x:0,y:0,z: -1};
5 ray . origin ={x: camPosition .x,y: camPosition .y,z: camPosition .z}; 6 let nodes = viewer . scene . pointclouds [0]. nodesOnRay (
7 viewer . scene . pointclouds [0]. visibleNodes , ray );
• Filtro i nodi con una bounding sphere il cui raggio è compreso tra 8 e 6 metri. Questo perchè i nodi che contengono i punti dell’asfalto in questo point cloud hanno un raggio poco maggiore di 6 metri.
1 let radius6Nodes = intNodes . filter (function( elem ){ 2 let radius = elem . geometryNode . boundingSphere . radius ; 3 return radius <8 && radius >6;
4 });
• Ordino i nodi rimanenti secondo la distanza dal loro centro alla camera e prendo il più vicino, ricordandomi che le bounding sphere devono prima essere convertite in world coordinates
1 let matrixWorld = viewer . scene . pointclouds [0]. matrixWorld ; 2 radius6Nodes . sort (function (a, b){
3 let distanceCenter1 =(a. geometryNode . boundingSphere . clone (). 4 applyMatrix4 ( matrixWorld ). center ). distanceTo ( ray . origin )); 5 let distanceCenter2 =(b. geometryNode . boundingSphere . clone (). 6 applyMatrix4 ( matrixWorld ). center ). distanceTo ( ray . origin ); 7 return distanceCenter1 - distanceCenter2 ;
8 });
9 radius6Nodes = radius6Nodes [0];
• Infine calcolo la z media dikpunti presi ognik/pointsOf N ode. Di solitokè intorno a 10.
1 for (let i =0;i< radius6Nodes . geometryNode . numPoints ; 2 i+= Math . ceil ( radius6Nodes . geometryNode . numPoints /k))
3 meanOfKPoints += radius6Nodes . geometryNode . geometry . attributes . 4 position . array [i *3+2]+ radius6Nodes . sceneNode . matrixWorld .
5 elements [14];
6 meanOfKPoints /=k;
In questo modo anche se c’è un dislivello tra i punti del nodo, come un marciapiede, ciò influerà poco sulla z media. E comunque delle lievi variazioni dell’altezza della camera non sono problematiche.
5.4
Rilevazione ostacoli
L’identificazione di punti come ostacoli non è esattamente un’impresa banale, le soluzioni che ho intravisto si basavano su due approcci diversi: uno che utilizza tecniche di machine learning, uno che si basa sulla deviazione nell’altezza dei punti rispetto a quello che è considerato asfalto. Il machine learning risulterebbe più efficacie ma essendo questo un obbiettivo aggiuntivo ed essendo questa soluzione abbastanza complessa da meritare un suo progetto indipendente, ho deciso di optare per la seconda.
L’algoritmo implementato è il risultato dei seguenti ragionamenti. Non posso sapere con certezza cosa è e cosa non è asfalto, quello su cui posso appoggiarmi è il fatto che la posi-zione della camera (quindi quella del GPS e della macchina che usa questo programma) è nel mezzo della corsia che si sta percorrendo. Non posso semplicemente prendere dei punti vicino alla camera, calcolare la z media e iniziare a colorare di rosso tutti i punti superiori alla media per il semplice motivo che il livello stradale continua a cambiare man mano che si prosegue, aggiungiamo il rumore durante il processo di acquisizione digitale dei punti e l’algoritmo non è per niente efficacie.
Per rendere l’algoritmo invariante all’evoluzione dell’asfalto percorso ho deciso di segmen-tare i punti lungo la direzione di guida in segmenti orizzontali di spessore 0.4 metri cir-ca, calcolando che in questo spazio percorso il livello stradale non subisce cambiamenti significativi.
A questo punto potrei iniziare ad analizzare i punti in ogni segmento partendo dai punti più vicini alla camera, ma questa soluzione non è efficacie per il seguente motivo. I punti analizzati partirebbero dal centro del segmento e si estenderebbero simultaneamente agli estremi, il problema è nel simultaneamente perchè se il programma incontra degli ostacoli su un estremo la media inizia ad alzarsi e i punti verso l’altro estremo del segmento potrebbero essere classificati come ostacoli anche se la loro altezza non è cambiata.
Per risolvere questo problema semplicemente suddivido i segmenti in due parti, una conte-nente tutti i punti a sinistra del vettore direzione e l’altra conteconte-nente tutti i punti a destra. Per testare il corretto funzionamento della segmentazione ho scritto una funzione che mi co-lora in modo alternato i punti nei segmenti indipendentemente dalla loro altezza. Il risultato è il seguente.
Figura 5.4: Prova di segmentazione
Dopo che i punti sono stati segmentati posso percorrere ogni segmento nelle due direzioni indipendenti partendo da quelli più vicini al vettore direzione(i segmenti sono sempre per-pendicolari al vettore direzione). Prima di testare se i punti analizzati superano di un certo threshold la media progressiva, calcolo come parte dell’asfalto un certo numero di punti in-dipendentemente dalla loro altezza così da avere una media di riferimento. La media che viene calcolata è sempre basata sugli ultimimpunti analizzati, quindi quando analizzo un nuovo punto faccio il push di questo mentre eseguo anche un pop sulla struttura trattanto l’array che contiene i punti come una queue (FIFO). Io pongoma circa 60, di conseguenza la media si adatta abbastanza in fretta all’altezza dei nuovi punti così da non prolungare troppo le linee rosse. Il threshold (delta di altezza rispetto alla media) da superare per es-sere considerato ostacolo è stato posto da me intorno ai 5cm, empiricamente è risultato un buon limite per rilevare i marciapiedi che sono stati digitalizzati discretamente.
Il numero di nodi da processare per la rilevazione di ostacoli è ovviamente limitato. Ini-zialmente per scegliere i nodi semplicemente filtravo tra i nodi visibili quelli la cui bounding sphere intersecava una bounding sphere intorno alla camera di raggio circa 20 metri. Però in questo modo prendevo in considerazione troppi nodi laterali alla strada con conse-guente penalità sul tempo per processare i punti, allora per diminuire l’estensione laterale ma mantenere quella lungo il vettore direzione ho deciso di usare un approccio diverso. Dopo aver ricavato i nodi come descritto sopra, filtro quelli la cui bounding sphere ha il centro distante meno di 12 metri da un raggio che ha come origine la camera e come direzione la direzione della camera. In questo modo costringo i nodi da processare ad essere vicini alla strada. Il risultato è il seguente.
Figura 5.5: Rilevazione di ostacoli
Se la queue che contiene la coordinata z dei punti fosse più lunga allora tutto il marciapiede sarebbe diventato rosso perchè la media ci metterebbe più tempo ad adattarsi.
Per far sì che la segmentazione dei punti abbia complessitàO(n) uso direttamente la di-stanza come indice del segmento in cui mettere i punti, come si può vedere nel piccolo snippet di codice sottostante. Per velocizzare l’algoritmo è stato fatto anche utilizzo dei Web Workers, delle sorte di thread in javascript, però il passaggio delle strutture dati a questi thread è oneroso (i dati vengono serializzati e deserializzati per ogni comunicazione al/dal main thread) e induce un ritardo.
1 let camera = viewer . scene . view ;
2 let perpendicularDirectionCamera = new THREE . Vector3 (- camera . direction .y, 3 camera . direction .x, 0);
4 // Ray passing through camera perpendicular to the direction
5 let rayPerpendicular = new THREE . Line3 ( camera . position . clone () , 6 camera . position . clone (). add ( perpendicularDirectionCamera ));
7 // If to the right of the direction vector
8 if ( perpendicularDirectionCamera . dot (new THREE . Vector2 ( point .x - viewer .
scene . view . position .x, point .y - viewer . scene . view . position .y)) < 0)
9 side = 1;
10 else 11 side = 0;
12 // Closest point in the ray perpendicular to the camera direction passing
13 // through the camera
14 let closestPoint = new THREE . Vector3 ();
arrayIndex : i,
22 x: point .x, 23 y: point .y, 24 z: point .z 25 });
5.5
Lettura coordinate GPS - Firebase
Le coordinate GPS non vengono direttamente lette dal dispositivo bensì le ricevo da un server di Device SA la cui connessione mi è stata gentilmente offerta da Paolo Romani. Il vantaggio è che i dati grezzi vengono elaborati dal loro server e il mio applicativo esegue il fetch delle coordinate già in formato LV03 (che io converto in LV95).
Il database dal quale leggo le coordinate è un cloud-database, cioè gira su una piattaforma che sfrutta il cloud computing. Esistono due tipologie di cloud database, nella prima l’utente deve comprare delle macchine virtuali su cui poi far girare il database, nella seconda il database viene fornito as-a-service cioè il proprietario della piattaforma cloud si occupa di installare e mantenere il database. Il database al quale mi connetto è Firebase Realtime Database, quindi la seconda categoria. Firebase è una piattaforma di sviluppo web e mobile acquistata da Google. Essa offre una suite di servizi quali:
• Firebase Cloud Messaging
• Firebase Auth
• Realtime Database
• Firebase Storage
• Firebase Hosting
• ML Kit (machine learning)
Uno dei vantaggi del database Firebase è che non bisogna controllare periodicamente per nuovi dati bensì una volta aperta la connessione è il server a chiamare una tua callback quando ha nuovi dati.
Source:www.fotolia.com,www.YourFreeTemplates.com,www.openclipart.org,
www.logolynx.com,www.pfcad.it
Figura 5.6: 1. Il dispositivo GPS si connette ai satelliti (4 per avere un’alta precisione); 2. Manda le coordinate a Berna per una correzione; 3. Scrive le coordinate nel database Firebase; 4. Quando ci sono cambiamenti Firebase invia le coordinate al mio client
5.6
Pulizia point cloud
Il point cloud di Cornaredo in alcune zone contiene molto rumore, soprattutto nei tratti stradali sotto gli alberi e questo fa sì che il mio algoritmo di rilevazione ostacoli classifichi
Figura 5.7: Point cloud originale
salvati. Per velocizzare la ricerca dei punti, una volta caricato il file .pts in RAM i punti vengono ordinati rispetto alla coordinata x così che posso effettuare una ricerca binaria. L’obbiettivo che mi sono posto era quello di eliminare i falsi positivi. Purtroppo però non esiste una corrispondenza esatta tra le coordinate dei punti su Potree e i punti su file, il motivo è secondo me a causa dei calcoli floating-point che Potree esegue sulle coordinate grezze, e anche perchè Potree applica una distribuzione di Poisson ai punti per ottenere maggiore uniformità. Nonostante ciò test empirici mi suggeriscono che questa deviazione inserita da Potree nelle coordinate non è abbastanza grande da impedire il ritrovamento dei punti originali nei file cercando il punto nel file più vicino a quello presente su Potree. Inoltre uso i valori dei canali r, g, b come criterio aggiuntivo.
Figura 5.8: Point cloud modificato
Il mio programma C++ produce come output il point cloud in figura 5.8, dove si può notare che la maggior parte dei falsi positivi è stata eliminata. Il motivo dei rimanenti falsi posi-tivi dovrebbe essere una leggera variazione nella posizione e direzione della camera nel momento in cui l’algoritmo è stato lanciato nelle due figure.
Segue la parte di codice che salva i punti dentro il poligono specificato su file.
1 // The polygon must be defined either in a clockwise order or in a
counter - clockwise one
2 async function saveRedPointsIn4PointsPolygon ( fileName ) { 3 let textToWrite = "";
5 let p2 = viewer . scene . measurements [1]. points [0]. position ; 6 let p3 = viewer . scene . measurements [2]. points [0]. position ; 7 let p4 = viewer . scene . measurements [3]. points [0]. position ; 8 let triangleA = new THREE . Triangle (p1 , p2 , p3);
9 let triangleB = new THREE . Triangle (p1 , p3 , p4);
10 // Create a sphere around the camera
11 var customSphere = new THREE . Mesh (new THREE . SphereGeometry (8 * 3)); 12 customSphere . position . copy ( viewer . scene . view . position );
13 // Find intersecting bounding spheres
14 var intersectingNodes = viewer . scene . pointclouds [0]. visibleNodes . filter (
function( elem ) {
15 let radiusSum = elem . geometryNode . boundingSphere . radius + customSphere .
geometry . parameters . radius ;
16 let distanceCenters = customSphere . position . distanceTo ( elem . geometryNode .
boundingSphere . clone (). applyMatrix4 ( viewer . scene . pointclouds [0]. matrixWorld ). center );
17 return distanceCenters * distanceCenters <= radiusSum * radiusSum ; 18 }, customSphere );
19 // Analise each filtered node and all points in them
20 for (let node = 0; node < intersectingNodes . length ; node ++) { 21 for (let i = 0; i < intersectingNodes [ node ]. geometryNode . geometry .
attributes . position . count ; i ++) {
22 let pointPosAttribute = intersectingNodes [ node ]. geometryNode . geometry .
attributes . position ;
23 let point = new THREE . Vector3 ( pointPosAttribute . array [i * 3],
pointPosAttribute . array [i * 3 + 1],
24 pointPosAttribute . array [i * 3 + 2]) ;
25 point . applyMatrix4 ( intersectingNodes [ node ]. sceneNode . matrixWorld );
26 let pointColorAttribute = intersectingNodes [ node ]. geometryNode . geometry .
attributes . color ;
27 // I precedently marked the obstacle points not by painting them red but
by setting their alpha channel to 200. This way their original color is preserved and can be written to file
28 // Check alpha channel
29 if ( pointColorAttribute . array [i * 4 + 3] == 200) {
30 if ( triangleA . containsPoint ( point ) || triangleB . containsPoint ( point )) { 31 textToWrite += ( point .x + " " + point .y + " " + point .z + " " +
pointColorAttribute . array [i * 4 + 0] + " " + pointColorAttribute . array [i * 4 + 1] + " " + pointColorAttribute . array [i * 4 + 2] + "\r\n");
32 // Paint the saved points green , so that you know graphically which
points were saved to file
33 pointColorAttribute . array [i * 4] = 0;
34 pointColorAttribute . array [i * 4 + 1] = 255; 35 pointColorAttribute . needsUpdate = true; 36 }
37 } 38 } 39 }
// Function to download data to a file
46 // taken from : https :// stackoverflow . com / questions /13405129/ javascript
-create -and -save - file
47 function download (data , filename , type ) { 48 var file = new Blob ([ data ], {
49 type : type 50 });
51 if ( window . navigator . msSaveOrOpenBlob ) // IE10 + 52 window . navigator . msSaveOrOpenBlob (file , filename );
53 else { // Others
54 var a = document . createElement ("a"), 55 url = URL . createObjectURL ( file ); 56 a. href = url ;
57 a. download = filename ;
58 document . body . appendChild (a); 59 a. click ();
60 setTimeout (function() {
61 document . body . removeChild (a); 62 window . URL . revokeObjectURL ( url );
63 }, 0);
64 } 65 }
Capitolo 6
Risultati e conclusione
6.1
Risultati
Per testare l’applicazione io e il mio relatore ci siamo recati nella zona interessata, vicino al cinema "Cinestar" in zona Cornaredo, una volta fissato il dispositivo GPS al tetto della macchina e collegatolo all’hotspot di uno smartphone, abbiano fatto dei giri di prova. Inizial-mente la frequenza di richiesta della posizione del GPS era settata a una volta al secondo, dopo aver notato che il viewer riusciva a tenere il ritmo siamo passati a due volte al secondo, e anche qui il viewer non aveva problemi.
Figura 6.1: GPS sopra la macchina
Abbiamo anche provato ad attivare la rilevazione di ostacoli in tempo reale però a causa del tempo necessario all’algoritmo per analizzare i punti, di circa un secondo, l’applicazione non riusciva a stare al passo con la posizione della macchina. Gran parte della zona analizzata veniva sorpassata quando la rilevazione terminava.
(a) Visuale reale
(a) Visuale reale
(b) Visuale nel point cloud
6.2
Difficoltà incontrate
Le difficoltà maggiore che ho incontrato è stata senza dubbio capire come funziona interna-mente Potree, che non è una libreria bensì un software standalone. Nonostante io mi sia limitato a capire ciò che mi sarebbe servito, navigare tra più di una decina di migliaia di righe di codice in javascript non documentate è stato il fattore che mi ha preso più tempo.
6.3
Considerazioni finali
L’obbiettivo principale di questo progetto consiste nella creazione di un’applicazione che assiste il guidatore durante la guida grazie alla visualizzazione dell’ambiente circostante mediante un point cloud. Questa applicazione sicuramente non è perfetta, anche se il di-spositivo GPS era impostato ad inviare dati con una certa frequenza a volte sembravano arrivare leggermente in ritardo. Ciò nonostante ritengo che il progetto dimostra la
fattibili-re con ffattibili-requenze maggiori (che il dispositivo GPS offfattibili-re). Inoltfattibili-re si potfattibili-rebbe utilizzafattibili-re quella che si chiama movement prediction, cioè avendo a disposizione l’informazione riguardante posizione e velocità attuale si tenta di predire quale sarà la posizione futura, nel tentativo di ridurre la correzione che avviene quando effettivamente si ricevono le coordinate succes-sive. Il problema della latenza introdotta dall’usare l’algoritmo di rilevazione di ostacoli in tempo reale è risolvibile usando l’algoritmo in una fase di pre-processing e quindi avendo un point cloud che è processato a priori.
Questo progetto è risultato sicuramente interessante e ha contribuito ad una crescita per-sonale. Mi ha permesso di ampliare le mie conoscenze di javascript, che erano basilari, e di conoscere librerie come three.js.
