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 contenente 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 });