REALIZZAZIONE DI UN ALGORITMO DI SCAN MATCHING PER …rizzini/student_theses/TesiCapra.pdf · 2.1...

UNIVERSITAacute DEGLI STUDI DI PARMAFACOLTAacute DI INGEGNERIA

Corso di laurea di Ingegneria Informatica

REALIZZAZIONE DI UN ALGORITMODI SCAN MATCHING

PER SISTEMI DI MISURA DELLA DISTANZACON TECNOLOGIA LASER

RelatoreChiarmo Prof MONICA REGGIANI

CorrelatoriChiarmo Prof STEFANO CASELLI

Dott Ing DARIO LODI RIZZINI

Tesi di laurea diGIOVANNI CAPRA

ANNO ACCADEMICO 2004-2005

2

Grazie a tutti e stato davvero bello fare questa tesi spero vada a buon ter-minetanto questa e una prova

Indice

1 Introduzione 1

2 Scanner Laser SICK LMS 200 421 Uso dei sensori in robotica 422 Descrizione dello scanner laser 523 Driver utilizzato 824 Analisi delle prestazioni del laser 12

3 Scan Matching 1831 Formulazione del problema di Scan Matching 2032 Algoritmi di Scan Matching 21

321 Scan Matching con trasformata di Hough 21322 Scan Matching sviluppato da Cox 24323 Iterative Closest Point (ICP) 25

33 Considerazioni finali sugli algoritmi 32

4 Progettazione dellrsquoapplicazione 3541 Obiettivi 3542 Struttura del progetto 37

421 Classi sviluppate 37422 Strumenti utilizzati 41

43 Applicazioni pratiche e testing 44

5 Conclusioni 48

bibliografia 49

i

Capitolo 1

Introduzione

La percezione egrave dellrsquoambiente esterno egrave una delle componenti fondamentali diun sistema robotico La rilevazione di informazioni dallrsquoambiente infatti assumegrande importanza negli ambiti della localizzazione della navigazione e della ri-costruzione di mappe Questo perchegrave uno degli obiettivi principali della robotica egravequello di realizzare dei sistemi che possano svolgere autonomamente alcuni com-piti e che quindi devono essere in grado di determinare la propria posizione e dinavigare anche in ambienti sconosciuti Le applicazioni per questo tipo di sistemisono numerose e comprendono il monitoraggio di aree lrsquointerazione dellrsquouomo conil robot lrsquointrattenimento la sicurezza e molto altroLe informazioni su ciograve che circonda il robot sono acquisite attraverso sensori Es-istono varie tipologie di sensori Molto diffusi ad esempio sono i sensori di visioneLrsquoutilizzo di questo tipo di dispositivo egrave in larga espansione a causa dei prezzi rel-ativamente bassi delle videocamere e della grande disponibilitagrave del mercato Sonosensori che possiedono unrsquoelevata potenza di calcolo ma intrinsecamente sono pocoprecisi Notevole diffusione hanno anche i sensori di prossimitagrave che ormai fannoparte dellrsquoequipaggiamento standard di un robot e che garantiscono una buona af-fidabilitagrave Un posto di rilievo fra questi dispositivi egrave occupato dal laser scanner cherisalta per la precisione e la risoluzione che egrave in grado di garantire Proprio la pre-cisione di questo strumento rende possibile la ricostruzione del profilo determinatodegli ostacoli presenti nellrsquoambiente sul piano di scansione Ottenere queste rile-vazioni dettagliate egrave alla base di tutte le applicazioni piugrave rilevanti della robotica

1

Capitolo 1 Introduzione

Mediante il confronto fra due scansioni prese dal robot in posizioni diverse risultapossibile infatti calcolare la differenza di posizionamento del robot stesso una voltaricavata lo differenza di rotazione e di traslazione delle due scansioni Si riesce intal modo a ldquocontrollareldquo la navigazione del robotIl problema dellrsquoallineamento delle scansioni o scan matching consiste nella ricer-ca di un moto rigido solitamente bidimensionale che porti alla sovrapposizione didue insiemi di punti ottenuti come informazioni sullrsquoambiente Se il rilevatore laseregrave fisso rispetto al robot la risoluzione dello scan matching permette di ricostruire ilmovimento del robot e di localizzarlo Una scansione rappresenta solo un panora-ma parziale dello spazio in cui si sta agendo quindi integrando e confrontandofra loro numerose scansioni rilevate per esempio ogni qualvolta il robot muta lasua posizione si riesce ad ottenere una ricostruzione piugrave completa dellrsquoambienteLrsquoallineamento e la fusione di ogni scansione con quelle rilevate precedentementerisiede alla base di questa applicazione In tal modo il risultato finale egrave la definizionedi una vera e propria mappa dellrsquoambiente che circonda il robot e con cui esso deveinteragire come per esempio nellrsquoevitarne gli ostacoliQuesto lavoro di tesi si prefigge da un lato di valutare le prestazioni di un laserscanner (laser Sick LMS 200) dallrsquoaltro di studiare il problema dello scan match-ing e di realizzare in libreria attraverso lrsquouso del linguaggio di programmazione adoggetti C++ un algoritmo di scan matchingLe valutazioni sulle prestazioni del dispositivo laser sono state rappresentate at-traverso lrsquouso della teoria della probabilitagrave Sono state prese infatti come model-li di riferimento rappresentazioni basate su variabili aleatorie con una certa dis-tribuzioneSebbene lrsquoimpiego pratico dello scan matching sia relativamente recente esiste undiscreto numero di algoritmi Nella fase di analisi dello scan matching vengonoanalizzati alcuni dei metodi maggiormente conosciuti od utilizzati La scelta diquale tecnica di matching sviluppare in questo progetto non egrave stata presa in terminidi efficienza e prestazioni ma si egrave preferito puntare a tecniche giagrave consolidate e conbuona facilitagrave di calcolo Questo perograve non preclude la possibilitagrave di implementarealtre tecniche di matching in possibili sviluppi futuri Si egrave deciso di sviluppare lrsquoar-chitettura della libreria in modo flessibile ovvero essa fornisce soluzioni adatte adorganizzare varie modalitagrave di matching e a gestire la scelta e lrsquouso di una di esse in

2


particolareIl lavoro di tesi egrave organizzato nel modo seguente Nel capitolo 2 dopo una breveintroduzione sui sensori viene descritto lo strumento utilizzato per effettuare i testcon la libreria il laser SICK LMS 200 viene descritto il driver di interfacciamen-to tra il laser e il computer e infine vengono effettuate alcune considerazioni sulleprestazioni del dispositivo Nel capitolo 3 vengono presentati inizialmente alcuneapplicazioni in relazione alla ricostruzione dei profili degli ambienti Viene invecediscusso successivamente nello specifico il problema dello scan matching e ven-gono presentati alcuni fra i piugrave celebri algoritmi di scan matching tra cui anchequelli implementati dalla libreria Il capitolo 4 riporta una descrizione dettagliatadelle classi della libreria esegue un analisi degli strumenti e delle tecniche utilizzateper la realizzazione e infine riporta i risultati dei test applicativi Nel capitolo 5 sonotratte le conclusioni finali sulla realizzazione della libreria e alcune considerazionisu possibili sviluppi futuri

3

Capitolo 2

Scanner Laser SICK LMS 200

21 Uso dei sensori in robotica

Uno degli obiettivi della robotica mobile egrave la realizzazione di robot in grado dinavigare in ambienti non strutturati Lrsquoacquisizione di informazioni sullrsquoambienteegrave dunque essenziale per poter ottenere informazioni di posizione rilevare ostacolipianificare il percorso del robot I sensori i dispositivi che restituiscono al robotinformazioni sul contesto in cui opera sotto forma di misurazioni e dati numericirisultano dunque fondamentali per il moto ed il posizionamento di un robot Dellevarie classificazioni per i sensori proposte in lettaratura la piugrave significativa egrave quellache distingue sensori propriocettivi e sensori eterocettivi [1] I propriocettivi sono isensori che restituiscono informazioni sullo stato interno del robot come per esem-pio lo stato dellrsquoalimentazione la velocitagrave dei motori o lrsquoangolo di sterzata di unaruota Si tratta quindi di variabili che sono sotto il diretto controllo del robot I sen-sori eterocettivi invece rilevano informazioni sullrsquoambiente esterno che circonda ilrobot e sono solitamente i dispositivi che vengono associati al termine ldquosensorialeldquoTra i sensori eterocettivi spiccano i cosiddetti sensori di prossimitagrave Questi sono ingrado di misurare la grandezza fisica relativa alla distanza fra il sensore e gli oggettiche gli sono vicini Il loro funzionamento egrave basato sullrsquoemissione di un segnale chesi propaga con una velocitagrave nota sulla riflessione di tale segnale da parte di oggettiesterni e sul calcolo del tempo di volo cioegrave dellrsquointervallo di tempo fra lrsquoinvio e laricezione del segnale I sensori di prossimitagrave si distinguono fra loro per il tipo di

4

Capitolo 2 Scanner Laser SICK LMS 200

segnale utilizzato

bull Sensori ultrasonici(sonar) Questi sensori inviano onde di pressione con fre-quenza superiore a quella udibile dallrsquoorecchio umano generalmente fra i 40ei 180 kHz

bull Laser Il dispositivo utilizza pacchetti di onde infrarosse inviandole verso unoggetto e ricevendo la sua riflessione (che puograve essere totale o parziale) Solita-mente egrave possibile inviare il raggio secondo la direzione desiderata adoperandouno specchio rotante

22 Descrizione dello scanner laser

La realizzazione di un algoritmo di Scan Matching per sistemi di misura della dis-tanza egrave stata strettamente correlata in questo progetto di tesi allrsquoutilizzo di unoscanner laser I dati misurati con un dispositivo laserinfatti sono solitamente impie-gati allo scopo di determinare la distanza degli oggetti e definirne la loro posizionePiugrave concretamente nello sviluppo del progetto egrave stato utilizzato lo Scanner Laser

SICK LMS 200 in dotazione del Dipartimento di Ingegneria Informatica di Parma(si veda la figura 21)

Il principio alla base del funzionamento del dispositivo LMS egrave alquanto sem-plice Il sistema opera attraverso la misura del tempo di volo degli impulsi laserun fascio (beam) di impulsi laser viene emesso ed esso viene riflesso ogni qualvol-ta incontri un superficie riflettente La riflessione viene poi registrata dal receiverdello scanner Il tempo occorso tra lrsquoemissione e la ricezione dellrsquoimpulso laser egravedirettamente proporzionale alla distanza tra lo scanner e lrsquooggetto (tempo di volo)Il fascio di impulsi inoltre viene deviato da uno specchio interno che ruota in modotale da realizzare una scansione a forma di ventaglio (fan-shaped scan) dellrsquoareacircostante il dispositivo (radar laser) Il contorno dellrsquooggetto egrave determinato dal-lrsquoinsieme degli impulsi ricevuti I dati misurati inoltre sono disponibili in temporeale per unrsquoeventuale valutazione in formato binario attraverso lrsquouso di una inter-faccia serialeI dispositivi laser stanno avendo grande sviluppo poichegrave offrono una soluzione perun gran numero di applicazioni

5


Figura 21 Scanner Laser SICK LMS 200

bull determinazione del volume degli oggetti

bull determinazione della posizione degli oggetti

bull prevenzione di collisioni per veicoli

bull classificazione degli oggetti

bull automazione dei processi

bull monitoraggio di aree e spazi aperti

bull determinazione del volume o dei contorni d oggetti di grandi dimensioni

bull e altro

Vediamo ora in maniera piugrave approfondita le specifiche e le caratteristiche del LaserSICK LMS 200

6


Questo dispositivo realizza un sistema di misura della distanza che opera senza con-tatto attraverso la scansione dellrsquoarea circostante in due dimensioni La scansionecome giagrave spiegato precedentemente in questo paragrafo avviene attraverso lrsquoemis-sione di beams di impulsi La risoluzione dello scanner laser dipende direttamentedalla frequenza con cui questi beams vengono emessi dal dispositivo LMS 200prevede tre possibili risoluzioni lrsquointervallo con cui gli impulsi vengono rilasciatipuograve essere settato ad un quarto di grado (0 25 ) a mezzo grado (0 5 ) o ad ungrado (1 )In combinazione con la risoluzione vi egrave unrsquoaltra specifica dello scanner la massi-

ma risoluzione angolare di scanning Il dispositivo infatti non emette impulsi tuttointorno a segrave ma limita il suo raggio drsquoazione ad un angolo predefinito nel nostrocaso ad un angolo equivalente a 180 (la scansione viene effettuata in senso antio-rario) Questo vale nel caso in cui si decida di utilizzare le due risoluzioni minori(quindi un grado e mezzo grado) poichegrave per motivi di precisione e accuratezzala massima risoluzione angolare nel caso in cui si stia utilizzando una risoluzionead un quarto di grado egrave impostata a 100 In entrambi i casi perograve bisogna no-tare che lrsquoangolo di apertura viene risulta sempre essere simmetrico al centro delloscanner laser Facendo un rapido conto si nota che il massimo numero di valori ri-tornati da una scansione risulta essere 181 per la risoluzione ad un grado 361 perla risoluzione a mezzo grado e 401 per la risoluzione ad un quarto di grado A sec-onda della risoluzione utilizzata varia anche unrsquoaltro parametro quello del tempo

di acquisizione di una scansione Il laser puograve effettuare uno scanning in 13 26 o53 millisecondi in base alla configurazione che si egrave scelto di utilizzare Si riesce adosservare da questi dati che i tempi di risposta sono estremamente veloci in tuttie tre i casi e questo rende il dispositivo particolarmente adatto per applicazioni inreal-time I dati appena descritti sono riassunti e schematizzati nella tabella 21

Risoluzione 0 25 0 5 1

Max Risoluzione angolare 100 180 180

Max numero di valori 401 361 181Tempo di risposta 53 ms 26 ms 13 ms

Tabella 21 Specifiche dello scanner LMS 200

Il range di azione del dispositivo LMS egrave abbastanza ampio si possono effet-

7


tuare scansioni che riconoscano oggetti fino ad 80 metri di distanza Naturalmenteman mano che la distanza aumenta lrsquoerrore di precisione nel rilevamento cresce Incondizioni di buona visibilitagrave e a temperatura ambiente si misura un errore di preci-sione di circa plusmn15 millimetri in un range che va dagli 1 agli 8 metri e un errore diprecisione di circa plusmn4 centimetri in un range che va dagli 1 ai 20 metri La varietagravedi applicazioni per le quali lrsquoLMS risulta essere adatto egrave dovuto non solo allrsquoampioraggio di azione ma anche al fatto che esso riesce a lavorare in una molteplicitagrave disituazioni ambientali Il suo comportamento ad esempio non muta considerevol-mente in un range di temperature che variano dai minus30 C ai +70 CPer quanto riguarda le specifiche elettriche del dispositivo SICK LMS 200 essorichiede unrsquoalimentazione di 24 Volt Nella realizzazione di questo progetto peralimentare lo scanner nella fase di raccolta dati si sono sempre adoperate due bat-terie in piombo da 12 Volt ciascuna collegate in serie tramite un cavo Il laser riescea comunicare con un computer attraverso unrsquointerfaccia di tipo seriale che riportaquindi i dati in formato binario Tale interfaccia egrave in grado di supportare sia una por-ta seriale di tipo RS232 sia una porta seriale di tipo RS422 (questrsquoultima piugrave velocerispetto alla precedente e usata in maggior misura nel campo industriale) Questotipo di collegamento non si egrave rivelato del tutto ottimale come discusso nel paragrafo24 I dati descritti in questo paragrafo sono tutti tratti dalla documentazione fornitadalla casa di fabbricazione dello scanner laser [2]

23 Driver utilizzato

Avendo il laser numerose possibilitagrave di configurazione occorre necessariamente unprogramma che permetta di impostare le varie modalitagrave di utilizzo Il costruttorefornisce assieme al laser scanner il software di prova LMSLMI user software v

511 per piattaforma Windows Questo programma una volta collegato lo scanneral computer permette allrsquoutente di definire varie configurazioni si puograve sceglierequale risoluzione delle tre supportate adoperare su quale angolo di azione effet-tuare la scansione (le 180 ) e a quale distanza limitare il campo di azione Inoltreil software egrave predisposto per fornire unrsquointerfaccia grafica che visualizzi la mappaa ventaglio dellrsquoarea presa in esame durante il funzionamento del dispositivo laserEgrave possibile osservare un esempio della rappresentazione grafica di una scansione

8


fornita dal software in questione in figura 22Un equivalente per il sistema operativo Linux non viene purtroppo rilasciato dalla

Figura 22 Scansione visualizzata con LMS user software

casa di fabbricazione e bisogna quindi realizzare un proprio driver se si vuole ge-stire lo strumento anche in tale ambito Lo scopo di questo lavoro di tesi non eraquello di realizzare un driver per lrsquoLMS perciograve tale tipo di problema non egrave stato inquesta sede affrontato ma si egrave scelto di usufruire di driver giagrave realizzati e trovatisulla rete In particolare sono stati utilizzati i driver sviluppati nel 2002 da StefanoZanero e Claudio Merloni dellrsquoIstituto Politecnico dellrsquoUniversitagrave di Milano Essisono interamente realizzati in linguaggio di programmazione ad oggetti C++ e neviene rilasciato il codice sorgente Il codice egrave completamente opensource in modoche si possa utilizzare o modificare a seconda delle esigenze Le librerie implemen-tate forniscono i metodi per la comunicazione con il dispositivo e lrsquoacquisizione deidati Assieme al driver vero e proprio vengono fornite diverse classi per il filtraggioche consentono di ottenere un profilo piugrave dolce e di eliminare il rumore presentealle alte frequenze Il concetto alla base di tutte le classi del driver egrave quello di Poly-

Line I dati vengono restituiti dallo scanner tramite la porta seriale sotto forma di

9


un semplice array di misure di distanza che vengono rilevate eseguendo una scan-sione in senso antiorario Da questo array viene estratta una rappresentazione piugravemaneggevole la PolyLine appunto ovvero una struttura costituita da un elenco dipunti logicamente considerati uniti sequenzialmente da dei segmentiIl driver vero e proprio egrave costituito dalla classe LaserDriver che contiene al suointerno i metodi fondamentali per il corretto funzionamento del dispositivo La fun-zione scan() definita in LaserDriver permette di eseguire una scansione e ritornaun puntatore ad un oggetto LaserData contenitore in cui vengono immagazzinati uninsieme di misure fatte dal laser Tale metodo egrave quindi alla base del driver visto chequestrsquoultimo ha la funzione principale di comunicare con lo scanner mediante loscambio di caratteri attraverso unrsquointerfaccia seriale Oltre a questo metodo fonda-mentale allrsquointerno della classe LaserDriver sono presenti come membri privatile funzioni per settare la configurazione dello strumento tra le quali riveste unruolo principale il metodo SetLaserScan() che permette di impostare larisoluzione e lrsquoangolo di azione di una scansione Questo metodo essendo privatoin teoria non dovrebbe essere usato dagli utenti che perograve possono utilizzare perla configurazione il wrapper pubblico setResolution() I dati immagazzinatiin un oggetto di tipo LaserData possono essere restituiti sotto forma di PolyLineattraverso il metodo getData() membro pubblico della classe LaserData In-oltre egrave possibile scegliere se visualizzare i dati in coordinate polari o in coordinatecartesiane usando rispettivamente i metodi getR() getTheta() e getX()getY() implementati nella classe LaserPoint La struttura del driver egrave riassuntanel diagramma delle classi in figura 23Insieme alle classi che implementano il driver vengono forniti dei file sorgenti Javache comprendono la libreria DrawingPaneljava e due programmi PolyViewerjavache visualizza in unrsquointerfaccia grafica i dati presi da un file aggiornandoli alla pres-sione di un tasto e PolyViewerLoopjava che viceversa aggiorna continuamente idatiPer i fini di questo progetto di tesi lrsquoutilizzo del dispositivo laser egrave stato limitatoallrsquoacquisizione di dati sui quali verificare la correttezza dellrsquoalgoritmo sviluppatoIl driver [3] utilizzato non si egrave rivelato particolarmente adatto a questa modalitagrave diutilizzo poichegrave maggiormente finalizzato alla restituzione di dati di elevata qualitagraveattraverso lrsquouso di numerosi filtri Purtroppo le operazioni di filtraggio causano un

10


Figura 23 Diagramma UML delle classi del driver

tempo maggiore di elaborazione e quindi di restituzione dei dati acquisiti rallen-tando lrsquointero processo Inoltre il filtraggio elimina informazioni e questo potrebbecreare problemi ai fini della precisione dellrsquoalgoritmo Il driver perciograve non risultafunzionale se si desiderano raccogliere molte scansioni in un tempo limitatoCon lo scopo di aumentare le prestazioni del dispositivo laser riuscendo a sfruttarea pieno le potenzialitagrave dello strumento nel Laboratorio di Robotica dellrsquoUniversitagravedi Parma egrave in corso la ricerca e la parziale riscrittura di driver attraverso il linguag-gio di programmazione in C++ modificando e migliorando un driver preesistentein PlayerStage Con tale progetto si cercheragrave di eliminare tutti quei processi chepossano in qualche modo rallentare lrsquoelaborazione in modo da poter effettivamentesfruttare lo scanner per applicazioni in tempo reale Inoltre saragrave possibile attraversolrsquouso di questo driver interfacciare lo scanner LMS con una porta seriale RS422

11


giagrave acquistata che risulta nettamente piugrave veloce delle porte RS232 presenti suicomputer del laboratorio

24 Analisi delle prestazioni del laser

Lrsquoassenza di dati sperimentali diretti ottenuti con lo strumento SICK LMS 200 hareso necessario lrsquoesecuzione di test di precisione e piugrave in generale di prestazioniI test prevedevano soprattutto una larga raccolta di dati su cui compiere le analisiTutti gli esperimenti sono stati effettuati collegando lo scanner ad un computer por-tatile con processore AMD Turion 64 ML-30 e 512 MegaByte di RAM Essendotale computer sprovvisto di una porta seriale si egrave rivelato necessario utilizzare unconvertitore serial-to-USB per poter interfacciare il laser con il terminale Bisognasottolineare il fatto che lrsquoimpiego di un adattatore non ha in alcun modo alterato irisultati dei test essendo la velocitagrave di trasmissione della porta seriale perfettamentecompatibile con la velocitagrave della porta USB Lrsquoalimentazione necessaria per lo scan-ner egrave stata fornita da due batterie al piombo da 12 Volt lrsquouna collegate in serieLe applicazioni di interesse non richiedono lrsquoimpiego del laser per la ricostruzionedella mappatura dello spazio o comunque non si richiedono particolari caratter-istiche ambientali Per questo motivo nonostante la presenza di numerosi ostacoliquali armadi tavoli computer e altro le scansioni sono state tutte rilevate allrsquointernodel laboratorio di Robotica presso la palazzina 1 della sede scientifica di IngegneriaUn esempio di una rilevazione acquisita dallo scanner egrave visibile in figura 24Lrsquoobiettivo principale di queste prime analisi era la verifica della precisione dei

rilevamenti eseguiti dallo scanner LMS o meglio lrsquoanalisi dellrsquoerrore di precisione

a cui egrave soggetta una scansione Come giagrave accennato precedentemente il dispositi-vo opera attraverso lrsquoemissione di beams di impulsi laser e la ricezione della rifles-sione degli stessi impulsi ogni qualvolta incontrino un ostacolo calcolando il tempodi volo dei raggi e conseguentemente la distanza fra oggetto e scanner Purtroppoquesto calcolo risulta sempre soggetto ad approssimazioni o ad errori di precisioneLo scopo delle analisi fatte egrave proprio quello di verificare lrsquoentitagrave e la distribuzionedellrsquoerrore di approssimazione supponendo di poterlo descrivere con una variabilealeatoria Si egrave proceduto quindi alla raccolta di dati in maniera un porsquo particolareper verificare la precisione delle rilevazioni dello scanner non occorre registrare tut-

12


minus3000 minus2000 minus1000 0 1000 2000 3000 4000 5000 6000 70000

1000

2000

3000

4000

5000

6000

Figura 24 Scansione del laboratorio di robotica

ti i punti di una scansione ma egrave sufficiente focalizzare lrsquoattenzione su un singolobeam Il programma di test consiste in un semplice listato nel linguaggio di pro-grammazione C++ che prevede lrsquoesecuzione di 4000 scansioni acquisendo i dati incoordinate polari (ovvero restituendo la distanza dallo scanner e lrsquoangolazione conla quale i raggi sono stati emessi) Di questi viene memorizzato in un file di testospecificato da riga di comando solo il dato relativo allo stesso singolo beam ovverosempre la distanza relativa allo stesso angolo Il beam preso in considerazione nelnostro caso egrave stato quello centrale avente unrsquoangolazione in radianti uguale a π

2 Ai

fini del risultato delle analisi la scelta di un beam piuttosto di un altro non egrave re-strittiva e non incide sulle conclusioni Lrsquoacquisizione delle 4000 scansioni egrave stataripetuta numerose volte in modo da ottenere una buona base statistica per le analisiLa scelta di reiterare lrsquoesecuzione del programma di test quattromila volte egrave stata

13


forzata da alcuni limiti nella velocitagrave di acquisizione dei dati da parte del laser (perraccogliere 4000 dati occorrevano circa 20 minuti) Sarebbe stato piugrave opportunoprendere un numero maggiore di campioni (sullrsquoordine dei diecimila) in modo daavere maggiore precisione nei risultati finali dellrsquoanalisi anche se alla fine il numerodi dati raccolti si egrave rivelato comunque sufficiente per gli scopi prefissatiConclusa la fase di acquisizione dei campioni si egrave proceduto alla successiva fase dianalisi A tale scopo egrave stato utilizzato il software Matlab version 65 R 13 per il sis-tema operativo Windows Nellrsquoanalisi dei dati risulta interessante il confronto del-lrsquoistogramma sperimentale con la funzione di densitagrave di probabilitagrave (PDF) propostada Sebastian Thrun Wolfram Burgard e Dieter Fox[4] come modello per un beam Ilmodello proposto integra fra loro quattro tipi di rilevamento di errori piccole misuredi errori durante il corretto rilevamento errori dovuti ad oggetti inaspettati (come ilpassaggio di persone ad esempio) errori dovuti al fallimento del riconoscimento diostacoli e rumori random inaspettati Piugrave in dettaglio

bull Rilevamento corretto con errori localiAnche se il sensore misura correttamente la distanza degli oggetti il valoreche ritorna egrave sempre soggetto a rumore dovuto alla risoluzione limitata deisensori ad eventi atmosferici sulla misura del segnale e cosigrave via Tale erroreegrave solitamente modellato da una curva gaussiana con una determinata media

zklowastt e una determinata deviazione standard σ

p(zkt |xt m) =

N(zk

t zklowastt σ2) se 0 le zk

t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2

bull Oggetti inaspettatiLa presenza temporanea di oggetti tra il sensore e lrsquoipotetico oggetto sullatraiettoria di un beam altera la misura e la pdf Il modello sensoriale usatoda un localizzatore ne deve tener conto Matematicamente la probabilitagrave del-

14


la misura della distanza in queste situazioni egrave descritta da una distribuzione

esponenziale

p(zkt |xt m) =

λeminusλzk

t se 0 le zkt le zmax

0 altrimenti(22)

bull Fallimenti nel rilevamentoInoltre va considerata la possibilitagrave di rilevare falsi negativi Un risultato tipi-co di un fallimento del sensore egrave una misura di tipo max-range il sensoreritorna il suo massimo valore raggiungibile zmax Si modella questo casorappresentandolo con una delta di Dirac centrandola nel massimo valoreraggiungibile

p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)

bull Misurazioni randomI sensori occasionalmente producono falsi positivi Per fare un esempio let-ture fantasma possono essere prodotte da cross talking interferenze o altroRicorrendo ad un semplice modello a PDF con distribuzione uniforme sul-lrsquointero range di misure del sensore [ zmax] si riesce a valutare anche questifenomeni

p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)

Attraverso un banalissimo script di Matlab i dati memorizzati in un file di testosono stati inseriti in una matrice di due colonne la prima colonna contenente ilvalore della distanza e la seconda contenente lrsquoangolo del beam Sono stati poi vi-sualizzati i valori degli elementi della prima colonna e inoltre di essi si sono cal-colate la media e la deviazione standard Per rappresentare lrsquoandamento dellrsquoerroreinvecesiegrave fatto ricorso allrsquouso di un istogramma Sullrsquoasse delle ascisse egrave stato ri-posto il valore della distanza (lrsquointero range dei possibili valori egrave stato suddiviso in50 intervalli) e sullrsquoasse delle ordinate il numero di rilevazioni aventi un dato valoreI risultati ottenuti si possono osservare in figura 25

Nel riquadro a sinistra in rosso sono visualizzati i quattromila valori della dis-tanza presi sempre sullo stesso beam La linea retta verde orizzontale continua rap-

15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400

Figura 25 Andamento dellrsquoerrore

presenta la media di tali misure In tutti gli esperimenti eseguita quindi ogni voltacon quattromila dati diversi si egrave potuta rilevare una deviazione quadratica media σ2

di circa 127 centimetri valore propriamente non trascurabile Nel riquadro a destrainvece egrave visualizzato lrsquoandamento dellrsquoerrore e come balza subito allrsquoocchio essorispecchia chiaramente una distribuzione di tipo gaussiana Il picco della curva si ot-tiene naturalmente molto vicino al valore della media calcolata Rispetto al modelloriportato[4] egrave qui visibile solo lrsquoeffetto dellrsquoerrore locale dovuto al rumore gaus-siano Nelle osservazioni sperimentali effettuate in presenza di ostacoli temporaneinon egrave stata riscontrata una significativa differenza rispetto al modello gaussiano edin ogni caso la distribuzione ottenuta si discosta di molto dal modello esponenzialeProbabilmente sarebbe stato necessario modulare opportunamente la distanza del-lrsquooggetto occludente dal sensore

16


In casi isolati lrsquoistogramma si egrave discostato da un andamento gaussiano presentandoun minimo in prossimitagrave dellrsquoasse di simmetria quindi intorno al valor medio TalePDF pseudo-bimodale potrebbe essere attribuita allo scarso numero di misure ef-fettuate Il fenomeno puograve comunque essere ritenuto trascurabile data la raritagrave dellasua comparsa

17

Capitolo 3

Scan Matching

Nel capitolo precedente sono state presentate le caratteristiche principali dello sen-sore laser Ciograve che lo contraddistingue da altri sensori di prossimitagrave egrave lrsquoelevatarisoluzione angolare e la precisione (caratteristiche che sono state verificate speri-mentalmente) Grazie a tale strumento egrave possibile ricostruire il profilo degli ostacoliche si presentano sul piano di scansione Ciograve risulta estremamente importante pernumerose applicazioni in robotica Le principali sono discusse brevemente qui diseguito

bull OdometriaLrsquoodometria egrave il metodo di navigazione piugrave utilizzato per il posizionamentodei robot mobili e generalmente sfrutta sensori di tipo propriocettivi Lrsquoideafondamentale alla base dellrsquoodometria egrave lrsquointegrazione di informazioni in-crementali sul moto durante un periodo determinato che purtroppo porta in-evitabilmente allrsquoaccumulo di errori In particolare lrsquoaccumulazione di erroridi orientamento puograve causare grandi errori di posizionamento che cresconoproporzionalmente alla distanza percorsa dal robot Un esempio di questa im-precisione egrave visibile in figura 31 Nonostante queste limitazioni lrsquoodometriaegrave una parte importante del sistema di navigazione Per esempio gli algoritmipiugrave diffusi per la localizzazione integrano le informazioni odometriche [5] Imetodi di scan matching propongono un diverso approccio nella ricostruzionedello spostamento del robot

bull Map-based positioning

18

Capitolo 3 Scan Matching

Figura 31 Incertezza dellrsquoodometria

Il Map-based positioning egrave una tecnica nella quale il robot usa i propri sen-sori per creare una mappa dellrsquoambiente circostante Vengono utilizzati per-ciograve principalmente i sensori eterocettivi Questa mappa locale viene poi com-parata con una mappa globale precedentemente immagazzinata in memoriaSe viene riscontrata una corrispondenza fra le due mappe allora il robot puogravecomputare la sua posizione attuale e il suo orientamento nellrsquoambiente cir-costante Uno dei piugrave importanti aspetti della navigazione map-based egrave ilMap-matching processo che stabilisce la corrispondenza fra la mappa localee la mappa globale [1]

bull Simultaneous Localization and Mapping (SLAM)Il problema che il Simultaneous Localization and Mapping tenta di risolvere

19


consiste nella possibilitagrave di lasciare libero un robot di muoversi in un ambi-ente sconosciuto usando i sensori di prossimitagrave e simultaneamente di costru-ire una mappa dellrsquoambiente attraverso i dati raccolti dai sensori [6] Siccomeuna scansione rappresenta una vista parziale dellrsquoambiente confrontando eintegrando fra loro molte scansioni prese in posizioni differenti si riesce adottenere una descrizione dellrsquoambiente piugrave completa Il punto fondamentale egraveallineare in maniera appropriata le scansioni in modo che esse possano esserefuse fra loro La difficoltagrave risiede nel fatto che lrsquoinformazione odometrica dasola non egrave sufficiente per determinare il posizionamento e inoltre non si ri-escono ad utilizzare modelli preesistenti per correggere gli errori di posizion-amento perchegrave lrsquoambiente in cui si sta lavorando egrave sconosciuto Un approcciogenerale per la costruzione del modello dellrsquoambiente egrave lrsquointegrazione incre-mentale dei nuovi dati al modello ogni scansione rilevata dal sensore vieneallineata con la scansione precedente rilevata o con il modello cumulativoglobale

31 Formulazione del problema di Scan Matching

Un problema di Scan Matching consiste nel determinare dati due insiemi di puntiun moto rigido bidimensionale che porti ad una sovrapposizione dei due insiemi dipunti Tipicamente un insieme di punti egrave il risultato di unrsquoacquisizione sensorialein genere con un laser Una situazione comune in cui lo scan matching si applicaegrave la seguente un robot situato inizialmente in una posizione Pref dove per Pref siintende il vettore delle coordinate e dellrsquoorientamento del robot sul piano di movi-mento effettua una scansione Sref con un sensore di prossimitagrave fissato rigidamentesu di esso In seguito ad uno spostamento esso si porta in posizione Pnew e nellanuova posizione effettua una nuova scansione Snew Il compito dello scan match-ing egrave quello di determinare con esattezza la differenza tra la posizione Pnew e laposizione Pref mediante lrsquoallineamento delle due scansioni Riassumendo il prob-lema di matching si puograve formulare come segue assumendo che la posizione di Snew

sia P primenew occorre trovare una rotazione ω e una traslazione T per Snew tale che dopo

la trasformazione Snew sia allineata con Sref Lrsquoapproccio piugrave comune al problema dello scan matching risiede nel definire una

20


misura della distanza fra le due scansioni e ricercare una appropriata trasformazionerigida che minimizza tale distanza Lo spazio in cui effettuare questa distanza egrave es-senzialmente tri-dimensionale (rotazione e traslazione bi-dimensionale)Una prima generale classificazione degli algoritmi di scan matching prevede duecategorie [1]

bull Matching icon-based accoppia i punti di una rilevazione con i punti carat-teristici della mappa precedentemente memorizzata basandosi sulla distanzaminima La posizione del robot egrave risolta attraverso la minimizzazione dellrsquoer-rore della distanza tra i punti e i loro corrispondenti sulla mappa Basandosisulla nuova posizione le corrispondenze sono ricalcolate e il processo vieneripetuto fino a quando lrsquoerrore sulla distanza non cade sotto un valore di sogliaprestabilito

bull Matching feature-based fa corrispondere i dati acquisiti ad un piccolo in-sieme di punti caratteristici che saranno poi confrontati con la mappa memo-rizzata

Nel paragrafo 24 sono stati messi in evidenza i limiti dello strumento laser larumorositagrave lrsquoerrore di approssimazione etc Lrsquoallineamento perfetto risulta pertantoimpossibile Inoltre a seguito dello spostamento alcuni degli ostacoli individuati inuna data scansione non sono visiili in quella successiva a causa del limitato campodi visibilitagrave del laser e della presenza di oggetti occludenti Per questo motivo nelcorso degli anni la ricerca ha portato alla formulazione di numerosi algoritmi discan matching ognuno di essi volto a migliorare la precisione dellrsquoallineamentoe la velocitagrave delle operazioni Nel paragrafo successivo vengono presentati alcunidegli algoritmi di matching descritti in letteratura

32 Algoritmi di Scan Matching

321 Scan Matching con trasformata di Hough

Uno degli algoritmi usati per fare scan matching egrave lrsquoHough Scan Matching (HSM)

[7] che deve il proprio nome allrsquoimpiego della [] La trasformata di Hough egrave usata

21


da tempo nellrsquoambito della visione artificiale per ricercare allrsquointerno di unrsquoimmag-ine digitale pattern corrispondenti a curve geometricheAnche nel caso dello scan matching lrsquoobiettivo egrave lrsquoindividuazione delle rette checongiungono i punti di una scansione La ricerca si svolge a partire da una equazioneparametrica della retta

x middot cos(θ) + y middot sin(θ) = ρ (31)

La ricerca delle rette viene poi effettuata nel piano dei parametri tracciando le curveduali rispetto ai punti (x y) Nel caso delle rette parametriche come (31) si ottiene

ρ =radic

x2 + y2 middot[ xradic

x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic

x2 + y2 middot cos[θ minus atan2(y x)]

La trasformata di Hough dellrsquoinsieme di punti dati egrave un funzionale che associaa ciascun (ρ θ) e alla equazione della retta il numero di curve duali che passanoper il dato punto I passaggi descritti appena sopra sono visibili in figura 32 nellaquale il cerchietto rosso evidenzia lrsquointersezione delle curve nello spazio parametri-co Nellrsquoelaborazione su di un calcolatore ciograve che si calcola egrave in realtagrave la trasformatadi Hough discreta (DHT) il piano dei parametri egrave suddiviso in celle di ampiezza da-ta cui egrave associato il numero di curve parametriche passanti allrsquointerno della cellaLrsquoalgoritmo proposto [7] sfrutta le proprietagrave della HT della retta parametrizzatacome in (31) In particolare la rotazione dei punti nel piano cartesiano produceun movimento rigido nel piano dei parametri (ρ θ) Scelto un opportuno funzionaleg[ middot ] che applicato alla HT sia invariante alla rotazione risulta definito lo spettro di

HoughHSg(θ) = HSg(θ + φ)forallφ

Lo spettro di Hough HS egrave allora invariante alla rotazione Una scelta possibile perg[ middot ] egrave la funzione energia della sequenza dellrsquoinsieme nel dominio discreto

g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6

Figura 32 Rappresentazione delle rette nello spazio dei parametri e trasformatadi Hough

Il ricorso allo spettro di Hough semplifica la ricerca dellrsquoangolo di rotazione ri-conducendola alla semplice correlazione dei due HS associati alle scansioni daallineare La stima della traslazione viene invece effettuata confrontando le HT unavolta che lrsquoangolo di rotazione φ egrave stato stimatoIn sintesi i passi dellrsquoalgoritmo sono i seguenti

1 La trasformata di Hough e lo spettro di Hough (che ha la proprietagrave di es-sere invariante rispetto alla traslazione)sono calcolati sia per i dati rilevati dalsensore sia per i dati di riferimento

2 I massimi locali della cross-correlazione degli spettri sono utilizzati per avan-zare ipotesi sullrsquoangolo di rotazione θ

3 Per ogni ipotesi su θ delle limitazioni sul vettore di traslazione T sono prodottedalla correlazione delle colonne della trasformata di Hough

4 Due alternative

23


bull le limitazioni lineari sono combinate per produrre ipotesi su T e le soluzionisono ordinate con una funzione di probabilitagrave

bull i risultati delle correlazioni sono accumulati in un buffer che produce unoutput di densitagrave

322 Scan Matching sviluppato da Cox

Un precursore dei metodi di scan matching egrave quello sviluppato da Ingemar J Cox[8] Il matching secondo tale tecnica egrave composto principalmente dallrsquoestrazionedi tratti caratteristici (feature) solitamente dei segmenti dal modello (una mappadellrsquoambiente in cui si sta lavorando precedentemente memorizzata) e dalla cor-retta corrispondenza tra lrsquoimmagine e i feature del modello attraverso lrsquouso di unaqualche forma di ricerca limitata Si tratta pertanto di un algoritmo di tipo feature-based Ciograve rende questa tecnica diversa dalle altre presentate in questo capitoloCome saragrave possibile vedere tutti gli altri algoritmi si fondano sul confronto fra tuttii punti di un immagine con tutti i punti dellrsquoaltra immagine (algoritmi icon-based)Si puograve notare che se lo scarto fra lrsquoimmagine e il modello egrave relativamente picco-lo allora per ogni punto dellrsquoimmagine il segmento corrispondente nel modello siavvicina molto ad essere il segmento piugrave vicino al punto nel modello La deter-minazione della corrispondenza (parziale) tra i punti dellrsquoimmagine e le linee delmodello si riduce ad una semplice ricerca del segmento piugrave vicino ad ogni puntoLrsquooperazione che sta alla base dellrsquoalgoritmo consiste nella determinazione di unacorrispondenza approssimata fra i punti dellrsquoimmagine e le linee del modello taleda ridurre lo scostamento fra le due immagini Lrsquoiterazione di questo metodo portaal seguente algoritmo

1 Per ogni punto dellrsquoimmagine trovare il segmento del modello piugrave vicino alpunto Chiamare questo target

2 Trovare la corrispondenza che minimizza la distanza totale quadratica tra ipunti dellrsquoimmagine e i loro target

3 Muovere i punti a seconda della corrispondenza trovata in (2)

24


4 Ripetere i passi (1-3) fino alla convergenza della procedura La composizionedelle corrispondenze di tutti i passi egrave la corrispondenza totale desiderata

Il passo (2) egrave computazionalmente il punto maggiormente complesso Per questomotivo sono state introdotte due aprossimazioni Per prima cosa ogni target vienecambiato dal segmento alla linea infinita contenente il segmento Inoltre siccome ladipendenza dei punti mossi dallrsquoangolo di rotazione θ non egrave lineare questa dipen-denza egrave approssimata ai termini di primo ordine in 0Ogni corrispondenza puograve essere descritta come una rotazione di un certo angolo θ

seguita da una traslazione di T e questo egrave denotato da (tθ) La corrispondenza (tθ)correla ogni punto x rarr R(θ) middot (x-c)+(c+T) dove c egrave il centro di rotazione e R egrave lamatrice di rotazione

R =

(cos(θ) minussin(θ)

sin(θ) cos(θ)

)Si tende a scegliere come centro di rotazione il baricentro dellrsquoimmagine che sivuole confrontare con il modello Questo perchegrave avere un centro che si muoveinsieme allrsquoimmagine ha il vantaggio che una trasformazione (t1 θ1) seguita dauna trasformazione (t2 θ2) ha lo stesso effetto sulla figura di una trasformazione(t1 + t2 θ1 + θ2)

Si desidera trovare il valore di (tθ) che minimizza

S =sum

i

([R(θ) middot (vi minus c) + (c + t)]prime middotui minus ri

)dove vi sono i punti dellrsquoimmagine ui i loro corrispondenti target e rsquo denota latrasposizione La fase di minimizzazione dellrsquoerrore quadratico viene ripresa danumerose tecniche di matching ed egrave alla base degli algoritmi illustrati in seguito

323 Iterative Closest Point (ICP)

LrsquoIterative Closest Point (ICP) egrave uno degli algoritmi di scan matching maggior-mente utilizzati e si basa sullrsquoassociazione di corrispondenze punto a punto Si trat-ta di un algoritmo iterativo dove per prima cosa si calcolano le corrispondenze trale scansioni che si vogliono confrontare e successivamente si minimizza lrsquoerrore didistanza per computare lo scarto fra le scansioni Questo metodo si fonda sullrsquoidea

25


seguente Per ogni punto Pi di una scansione che chiameremo Snew si usa unasemplice regola (indipendente dalla rotazione e dalla traslazione) per determinareun punto corrispondente Pprime

i sulla scansione o mappa di riferimento che chiameremoSref Poi per ogni coppia di punti corrispondenti si computa una soluzione ai mini-mi quadrati per le relative rotazione e traslazione Questa soluzione viene applicataper ridurre lrsquoerrore di posizionamento fra le due scansioni Si ripete questo processofino a che esso non convergeLa soluzione ai minimi quadrati deriva dalla minimizzazione della seguente fun-zione per la distanza la quale egrave definita su n coppie di punti corrispondenti P(xiyi)e Pprime(xrsquoiyrsquoi)

Edist(ω T ) =nsum

i=1

| Rω middotPi + T minus P primei |2 (32)

=nsum

i=1

((xicos(ω)minus yisin(ω) + Tx minus xprime

i)2 +

+ (xisin(ω) + yicos(ω) + Ty minus yprimei)2)

(33)

dove ω egrave lrsquoangolo di rotazione e T=(TxTy) egrave il vettore di traslazione Attraversola minimizzazione di Edist si puograve ottenere una soluzione in forma chiusa per Tx Ty

e ω come mostrato qui di seguito

ω = arctanSxyprime minus Syxprime

Sxxprime + Syyprime(34)

Tx = xprime minus (x middot cos(ω)minus y middot sin(ω)) (35)

Ty = yprime minus (x middot sin(ω) + y middot cos(ω)) (36)

26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1

(xi minus x)(xprimei minus xprime) Syyprime =

sumni=1(yi minus y)(yprimei minus yprime)

Sxyprime =nsum

i=1

(xi minus x)(yprimei minus yprime) Syxprime =sumn

i=1(yi minus y)(xprimei minus xprime)

La corrispondenza tra i punti della scansione e i punti dellrsquoimmagine di riferi-mento viene effettuata attraverso la scelta del punto piugrave vicino Ogni punto di Snew

viene accoppiato con il rispetto punto piugrave vicino di Sref Da qui il nome di IterativeClosest Point La distanza tra i punti delle due scansioni viene solitamente calcolatacon la formula della distanza lineare euclidea

dist =radic

(xprime minus x)2 + (yprime minus y)2 (37)

Si egrave dimostrato che lrsquoalgoritmo di ICP converge sempre monotonicamente ad unminimo locale che rispetta la funzione ai minimi quadrati della distanza Inoltrese lrsquoangolo di rotazione egrave piccolo lrsquoalgoritmo di ICP riesce a risolvere con unabuona approssimazione il vettore di traslazione Un inconveniente di questo meto-do di scan matching risiede nel fatto che lrsquoalgoritmo converge molto lentamentespecialmente se si egrave in presenza di modelli curvi Per tale motivo in vari sviluppidi ricerca lrsquoICP egrave stato modificato per ottenere migliori prestazioni Due variantidellrsquoalgoritmo di Iterative Closest Point sono presentate di seguito

Algoritmo di Iterative Dual Corrispondence (IDC)

Nellrsquoalgoritmo di Iterative Dual Corrispondence (IDC) proposto da Feng Lu edEvangelos Milios[9] la tecnica della corrispondenza fra i punti delle scansioni basa-ta sul closest point viene combinata con un altro metodo di associazione che prendeil nome di Matching-Range-Point

27


Considerando un punto P e il proprio punto corrispondente P prime = RωP +T se si ig-nora la traslazione si ha che | P prime |asymp| P | Lrsquoangolo polare θ di P e lrsquoangolo polare θ

di Prsquo sono correlati dalla relazione θ asymp θ + ω Questo implica che il corrispondentedi P sotto effetto della rotazione egrave un punto che ha range polare uguale a quello diP e gli angoli polari dei punti corrispondenti differiscono di un angolo di rotazioneω Ora in presenza di piccole traslazioni ci si puograve aspettare che il punto Pprime con lostesso range di P sia possibilmente una buona approssimazione del vero punto cor-rispondente di P Questa approssimazione restituisce utili informazioni sullrsquoangolodi rotazione ωPer essere sicuri che questo metodo trovi un unica reale corrispondenza si ricercail punto con lo stesso range allrsquointerno di una regione locale vicina a P dellrsquoimmag-ine di riferimento Supponendo che si possa stimare una banda Bω per la rotazioneω (cioegrave | ω |le Bω) si ha che θ isin [θ minus Bω θ + Bω] Questo significa che Pprime

deve ricadere allrsquointerno del settore delimitato da θ plusmn Bω Detto ciograve la regola diMatching-Range-Point egrave la seguente per un punto P il suo corrispondente pun-

to sul riferimento egrave Pprime dove Pprime soddisfa | θ minus θ |le Bω e | P prime | egrave il piugrave vicino a

| P | Basandosi su questa regola egrave stato sviluppato un algoritmo iterativo iterativematching-range-point (IRMP) nel quale Bω controlla la grandezza dellrsquoarea in cuiricercare la corrispondenza e anche la massima rotazione possibile risolta in unaiterazione Si genera empiricamente Bω utilizzando una funzione esponenziale de-crescente Bω(t) = Bω(0) middot eminusαtQuesto algoritmo converge notevolmente piugrave velocemente dellrsquoalgoritmo di ICPConviene perciograve combinare le due regole in modo da poter sfruttare sia la velocitagravedi convergenza del matching-range-point sia la stabiltagrave del closest point Da questoconcetto nasce lrsquoalgoritmo di Iterative Dual Corrispondence che utilizza entrambele regole nel modo seguentePer ogni iterazione occorre fare i seguenti passi

1 Per ogni punto Pi

a Applicare la regola del closest point per determinare il punto corrispon-dente P prime

i di Pi

b Applicare la regola di matching-range-point per determinare il punto cor-rispondente P primeprime

i di Pi

28


2 Computare la soluzione ai minimi quadrati (ω1 T1) dal set di coppie (PiP primei )

i = 1n (che sono state ottenute con la regola del closest point)

3 Computare la soluzione ai minimi quadrati (ω2 T2) dal set di coppie (PiP primeprimei )

i = 1n (che sono state ottenute con la regola del matching-range-point)

4 Prendere (ω2 T1) come soluzione per la traslazione nellrsquoiterazione corrente

La combinazione dei due metodi sembra portare a risultati significativamente miglioridi quelli ottenuti con le singole regole Questo algoritmo non solo migliora la stabil-itagrave delle iterazioni ma incrementa anche notevolmente la velocitagrave di convergenzaInoltre lrsquoalgoritmo IDC risulta insensibile alla scelta del parametro Bω

Algoritmo di Scan Matching Metric-Based (MbICP)

La distanza euclidea calcolata negli algoritmi di ICP e di IDP non tiene conto delfatto che i punti lontani dal sensore possono essere lontani dai propri corrispon-denti a causa delle rotazioni del sensore Il problema centrale degli algoritmi basatisullrsquoICP egrave quello di trovare una misura (per trovare il corrispondente piugrave vicinoe applicare la minimizzazione) che in qualche modo prenda in considerazione latraslazione e la rotazione del sensore allo steso tempo Javier Minguez FlorentLamiraux e Luis Montesano[10] dellrsquoUniversitagrave di Saragoza in Spagna hannodefinito una misura della distanza per lo spazio immagine del sensore che tenga con-to contemporaneamente della traslazione e della rotazione Successivamente questanuova definizione della distanza egrave stata utilizzata in tutti e due i passi dellrsquoICP for-malizzando un nuovo algoritmo che prende il nome di Metric-Based ICP (MbICP)La distanza viene definita come la norma del piugrave piccolo moto rigido di trasfor-

mazione che collega un punto ad un altro Una trasformazione rigida nel pianoegrave definita dal vettore q = (x y θ) rappresentante la posizione e lrsquoorientamento(minusπ lt θ lt π) del sensore dello scanner nel piano La norma di q egrave

q =radic

x2 + y2 + L2θ2 (38)

29


dove L egrave un numero reale positivo omogeneo ad una lunghezza Dati due puntip1 = (p1x p1y) e p2 = (p2x p2y) in R2 si definisce la distanza fra p1 e p2 come

dp(p1 p2) = min q tale che q(p1) = p2 (39)

dove

q(p1) =

(x + cos(θ)p1x minus sin(θ)p1y

y + sin(θ)p1x + cos(θ)p1y

)(310)

A questo punto si introduce unrsquoapprossimazione valida quando la minima nor-ma della trasformazione egrave piccola ipotizzando θ = 0 Lrsquoinsieme di trasformazionirigide che soddisfa la condizione q(p1) = p2 puograve essere approssimato dallrsquoinsiemedi soluzioni (x y θ) del sistema seguente

x + p1x minus θp1y = p2x

y + θp1y + p1y = p2y

Quello che serve egrave trovare la soluzione che minimizza la norma di q Per un da-to θ tale norma egrave data dallrsquoequazione seguente dopo aver sostituito ad x ed y leespressioni ricavate dal sistema precedente nella (38)

q 2= (δx + θp1y)2 + (δy minus θp1x)

2 + L2θ2

dove δx = p2x minus p1x e δy = p2y minus p1y Espandendo lrsquoespressione summenzionata siarriva alla conclusione che la distanza tra p1 e p2 egrave approssimata da

dp(p1 p2) =

radicδ2x + δ2

y minus(δxp1y minus δyp1x)2

p21x + p2

1y + L2(311)

Bisogna sottolineare il fatto che questa distanza egrave minore della distanza euclideaLa ridefinizione della distanza fa sigrave che muti considerevolmente anche la tecnicadi minimizzazione dellrsquoerrore rispetto allrsquoalgoritmo di ICP Dati due punti Pi =

(pix piy) e P primei = (pprimeix p

primeiy) utilizzando lrsquoapprossimazione della distanza 311 per la

30


minimizzazione si ottiene la seguente espressione

Edist(q) =nsum

i=1

(δ2ix + δ2

iy minus(δixpiy minus δiypix)

2

p2ix + p2

iy + L2

)(312)

dove

δix = pprimeix minus pprimeiyθ + xminus pix

δiy = pprimeixθ + pprimeiy + y minus pix

Lrsquoespressione 312 egrave una funzione quadratica di tipo wrt

Edist(q) = qT Aq minus 2bT q + c

dove c egrave un numero costante A la matrice simmetrica

A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1

(pprimeixpixpiy minus pprimeiy(p2ix + L2))

a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1

(minuspprimeiypixpiy + pprimeix(p2iy + L2))

a33 =nsum

i=1

(pprimeix(p2iy + L2) + pprimeiy(p

2ix + L2)minus 2pixpiyp

primeixp

primeiy)

31


e

b =

sumn

i=1((pprimeix minus pix)(p

2ix + L2) + (pprimeiy minus piy)pixpiy)sumn

i=1((pprimeix minus pix)pixpiy + (pprimeiy minus piy)(p

2iy + L2))sumn

i=1((pprimeix minus pix)[p

primeixpixpiy minus pprimeiy(p

2ix + L2)] +

+ (pprimeiy minus piy)[minuspprimeiypixpiy + pprimeix(p2iy + L2)])

Il valore di q che minimizza Edist(q) egrave il seguente

qmin = Aminus1b (313)

Lrsquoalgoritmo MbICP che utilizza le formulazioni appena descritte risulta miglioredegli algoritmi descritti precedentemente in termini di robustezza convergenza eprecisione Gli esperimenti eseguiti con questo tipo di algoritmo rivelano che adifferenza dellrsquoICP il MbICP restituisce nella maggior parte dei casi risultati senzafalsi negativi I dati sperimentali hanno anche evidenziato che i risultati migliori siottengono con L allrsquoincirca uguale a 3

33 Considerazioni finali sugli algoritmi

La trattazione degli algoritmi di scan matching fatta nel paragrafo precedente mettein luce alcune caratteristiche che unificano o differenziano le varie tipologie dimatchingSicuramente un fattore discriminante per quello che riguarda i metodi analizzati egraveda ricercare nellrsquoesistenza di due tipi di paradigmi lrsquouso della correlazione di dueinsiemi di punti e la minimizzazione di una distanza calcolata dopo aver effettuatounrsquoassociazione fra i due insiemi di punti Lrsquoalgoritmo che sfrutta le proprietagrave dellatrasformata di Hough egrave un chiaro esempio della prima situazione In esso infatti siricorre alla correlazione fra gli spettri di Hough dei due insiemi di punti da allineareper ottenere lrsquoangolo di rotazione Il secondo paradigma invece prevede come pri-mo passo unrsquoassociazione fra i punti delle due scansioni secondo un determinatocriterio che puograve variare da algoritmo ad algoritmo e successivamente la minimiz-zazione della distanza calcolata fra i punti corrispondenti Questo principio risiedealla base dellrsquoalgoritmo di Cox e dellrsquoalgoritmo di Iterative Closest Point con tuttele sue varianti

32


Unrsquoaltra differenza che egrave possibile riscontrare egrave lrsquouso in alcuni metodi di matchingdi modelli geometrici ricavati dai punti dati mentre in altri si fa ricorso diretta-mente ad unrsquoassociazione di tipo punto-punto Un abbinamento diretto fra i puntidelle scansioni viene fatto nellrsquoICP nellrsquoIDC e nellrsquoMbICP Il criterio secondo cuifare questa associazione egrave solitamente riconducibile al problema del closest pointCome descritto precedentemente perograve la distanza viene calcolata secondo metrichediverse a seconda di quale algoritmo si stia adoperando Modelli geometrici sonoinvece utilizzati sia nel metodo ideato da Cox sia nellrsquoHough scan matching Nelprimo i punti della scansione di riferimento sono uniti a formare segmenti che rap-presentino i tratti caratteristici del modello nel secondo si ricorre ad un uso pesantedi rette parametriche e di spazio dei parametriUnrsquoulteriore fattore discriminante riguarda il metodo di ricerca della trasformazionerigida che possa sovrapporre le scansioni In alcuni casi si procede avanzando primaipotesi sullrsquoangolo di rotazione e successivamente alla luce di queste supposizioni siricava il valore della traslazione Egrave questo sicuramente il caso dellrsquoICP in cui i valoridel vettore di traslazione sono calcolati utilizzando lrsquoangolo di rotazione preceden-temente trovato Identica egrave la situazione per lrsquoIDC che sfrutta direttamente lrsquoalgo-ritmo di iterative closest point anche se di questo poi viene presa in considerazionesolo la traslazione Differentemente da quanto egrave stato appena detto alcune tecnichecome il Metric-based ICP effettuano una ricerca della rotazione simultanea a quelladella traslazione Per ottenere ciograve nellrsquoMbICP egrave stato necessario addirittura intro-durre una nuova metrica in modo che nel calcolo della distanza si tenesse conto nonsolo della traslazione fra le due scansioni ma anche dellrsquoangolo di rotazioneNon esiste un criterio generale per stabilire se un algoritmo di scan matching siamigliore di un altro egrave possibile che a seconda delle situazioni in cui si lavorasiano adatte tecniche differenti Di quelli presentati sicuramente poco utilizzatonegli ultimi anni egrave il metodo sviluppato da Cox ormai superato ma esso ha unapropria importanza essendo come giagrave detto una sorta di precursore delle tecnichemoderne LrsquoICP egrave senza dubbio una delle tecniche maggiormente adoperate per ilmatching fra due scansioni e quindi si sono raggiunti buoni risultati nella sua appli-cazione Bisogna perograve evidenziare che una stima relativamente precisa del vettoredi traslazione si ottiene solo in presenza di angoli di rotazione piccoli perciograve egraveconsigliabile usare lrsquoICP in questo tipo di situazioni Un altro difetto di questo al-

33


goritmo potrebbe risiedere nella velocitagrave non troppo elevata di convergenza Questoproblema viene risolto nellrsquoalgoritmo MbICP attraverso la ricerca simultanea del-la rotazione e della traslazione Ciograve che perograve si guadagna in velocitagrave con questometodo si perde in facilitagrave di calcolo Lrsquointroduzione di una nuova metrica complicanotevolmente la computazione della distanza fra i punti delle due scansioni Inoltrenon si capisce in che modo calcolare la stima ideale per il parametro L della nuovadistanza (si veda (38)) a seconda delle situazioni in cui ci si trova Analizzando laricerca effettuata nel corso degli anni si puograve dire che la tecnica piugrave accreditata sialrsquoutilizzo della minimizzazione dellrsquoerrore della distanza e il paradigma ICP Ciograve egravedovuto proprio alla diffusione del suo utilizzo e quindi ai numerosi passi in avantifati sotto il profilo dellrsquoefficienza e della robustezza Per questo motivo nella realiz-zazione della libreria come verragrave descritto nel capitolo 4 si egrave scelto di implementareprincipalmente un algoritmo di tipo Iterative Closest Point

34

Capitolo 4

Progettazione dellrsquoapplicazione

41 Obiettivi

Questo lavoro di tesi si prefigge come obiettivo finale lo sviluppo di un software chegestisca un algoritmo di Scan Matching mediante lrsquouso del linguaggio di program-mazione ad oggetti C++ Ciograve che si vuole ottenere dalla realizzazione di questoprogetto egrave uno strumento che sia in grado di stabilire date due scansioni per qualeangolo di rotazione e per quale vettore di traslazione si debba ruotare e traslare unadelle scansioni per poter avere una parziale o totale sovrapposizione con lrsquoaltra conuna buona approssimazione Come trattato nel capitolo 3 questo problema rivesteun ruolo importantissimo nellrsquouso dei sensori in robotica per quanto riguarda iltracciamento dellrsquoodometria la localizzazione e la possibilitagrave di ricostruire profili emappePrima di passare allrsquoanalisi dettagliata dello sviluppo del progetto occorre innanz-itutto fare alcune considerazioni su quale algoritmo di Scan Matching sia stato op-portuno implementare Le opzioni tra cui scegliere (si veda per questo lrsquoanalisi svol-ta nel paragrafo 32) erano numerose Dato la natura esplorativa di questo lavoro ditesi e la necessitagrave di procedere in modo incrementale si egrave preferito puntare su di unalgoritmo consolidato e di ampia diffusione come lrsquoICP con alcune sue variantiLa prima variante egrave quella sviluppata nel 1995 da Feng Lu ed Evangelos MiliosdellrsquoUniversitagrave di North York in Canada e che prende il nome di Iterative Dual

Correspondence - IDC La seconda variante presa in esame egrave quella proposta nel

35

Capitolo 4 Progettazione dellrsquoapplicazione

2005 da Javier Minguez Florent Lamiraux e Luis Montesano dellrsquoUniversitagrave diSaragoza in Spagna nellrsquoarticolo Metric-Based Scan Matching Algorithms for Mo-

bile Robobt Displacement Estimation che cambia nettamente prospettiva rispettoalla precedente grazie allrsquoutilizzo non piugrave della metrica euclidea ma di una nuovametrica creata appositamente per valutare efficacemente lrsquoentitagrave della rotazione Lagiustificazione matematica dei due algoritmi egrave stata presentata nel paragrafo 323 Ilpunto di forza di questo software risiede proprio nella possibilitagrave di scegliere qualedelle due varianti utilizzare per il calcolo dello Scan Matching Infatti attraversolrsquouso di tecniche e strumenti che saranno approfonditi nei paragrafi successivi siegrave reso il programma flessibile cioegrave in grado di supportare il calcolo dellrsquoalgoritmosia attraverso la metrica euclidea sia attraverso la metrica adottata da MinguezMostrate fino ad ora le finalitagrave prime che si prefigge questo tipo di progetto egrave venu-to il momento di elencare alcune specifiche che il software dovrebbe essere in gradodi supportareCome giagrave accennato un requisito fondamentale egrave quello della flessibilitagrave Il pro-gramma dovrebbe essere in grado non solo di poter consentire la scelta del tipo dialgoritmo da utilizzare per il calcolo del closest point ma anche di consentire lagestione dei tipi (in particolare dei punti ricavati dalle scansioni) e delle strutturedatiUnrsquoaltra specifica da soddisfare egrave senza dubbio quella riguardante lrsquoefficienza e laportabilitagrave in vista delle esecuzioni in tempo reale Il software deve poter consen-tire un calcolo veloce ed efficace evitando strutture pesanti che rallentino lrsquoese-cuzione a causa delle numerose iterazioni Un robot in movimentoper esempionon puograve permettersi di perdere tempo ogni volta che deve ricalcolare la sua local-izzazione o ricreare una mappa di ciograve che lo circonda Per ottenere questi obiettivisi egrave dovuto fare ricorso ad alcuni compromessi tra lrsquoefficacia e lrsquoefficienza deglistrumenti utilizzati Riportando un esempio concreto una delle scelte piugrave difficilisotto questo punto di vista egrave stata quella di decidere quale tipo di struttura utiliz-zare per la memorizzazione e la gestione dei dati rilevati In un primo istante siegrave presa in considerazione la possibilitagrave di immagazzinare i dati in una struttura ditipo KD-Tree[11] Tale container risulta molto efficace consente uno scorrimentoe un ordinamento dei dati notevolmente veloce Purtroppo abbinata a queste carat-teristiche vi egrave anche una certa difficoltagrave di implementazione Ciograve ha fatto sigrave che si

36


scegliessero contenitori piugrave semplici come quelli della standard library[12] sia permantenere una certa facilitagrave di utilizzo della libreria sia per ottenere risultati con-creti in un minor tempo Altre semplificazioni a discapito dellrsquoefficienza sono stateeffettuate allrsquointerno dellrsquoalgoritmo vero e proprio Ad esempio le distanze adop-erate nella fase di associazione tra le scansioni sono sempre state calcolate tra duepunti Spesso invece nello sviluppo teorico degli algoritmi queste distanze sonocalcolate tra un punto ed una linea spezzata Questa differenza potrebbe portare aderrori nellrsquoapprossimazione

42 Struttura del progetto

421 Classi sviluppate

Nel progettare un algoritmo la complessitagrave non risiede nel design delle classi manelle classi interne Il compito del design in questo caso egrave gestire la caratteristicadella flessibilitagrave Si egrave voluto puntare in questo modo alla realizzazione di unrsquointer-faccia che risulti il piugrave leggero possibile e che sia facilmente maneggiabile da ogniutente che intenda servirsene Bisogna ricordare come giagrave trattato nel paragrafo41 che lrsquoutilitagrave di questo progetto non egrave fine a se stessa ma pensata in funzione diapplicazioni nel campo della robotica e di sviluppi real-timeLa struttura dellrsquointero software puograve essere sintetizzata attraverso i diagrammi delleclassi rappresentati in figura 41 e 42

Le classi astratte sono sostanzialmente tre

bull ScanFactory

bull ScanSet

bull ScanMatcher

La classe ScanSet definisce al suo interno la struttura dati in cui i punti diunrsquoeventuale scansione possono essere immagazzinati Il ricorso ad unrsquointerfacciademanda alle singole istanze il compito di definire il contenitore Nello specifi-co si possono scegliere che tipo di punto il contenitore debba immagazzinare eche tipo di struttura (ad esempio un vettore una lista etc) si debba utilizzare per

37


Figura 41 Diagramma delle classi delle factory

lrsquoimmagazzinamento Le modalitagrave attraverso le quali ottenere questo polimorfismosaranno trattate piugrave in profonditagrave nel paragrafo 422Sono state previste le implementazioni EuclideanSet e MLMSet ereditano dallaclasse ScanSet e fondamentalmente non fanno altro che ridefinire un metodo del-la classe padre In EuclideanSet viene implementato il metodo che restituisce ladistanza fra due punti calcolata con la formula euclidea mentre in MLMSet vieneimplementato il metodo che restituisce la distanza fra due punti con la formula idea-ta da Minguez Lamiraux e Montesano (si veda per questo il paragrafo 323)

La classe ScanMatcher egrave la classe che si assume il ruolo piugrave delicato dellrsquoin-tero progetto Ha come compito principale infatti quello di sviluppare ed eseguirelrsquoalgoritmo di scan matching Risiedono allrsquointerno di detta classe i metodi che sipropongono di calcolare lrsquoassociazione tra i punti di due scansioni secondo il crite-rio del closest point di minimizzare lrsquoerrore di approssimazione nel calcolo dellrsquoan-golo di rotazione e del vettore di traslazione e di reiterare i passi previsti dallrsquoal-goritmo di ScanMatching Il cuore della classe ScanMatcher egrave il metodo match()la funzione che implementa e coordina lrsquoesecuzione dellrsquoalgoritmo e che restituiscequelli che dovrebbero essere lrsquoangolo di rotazione e il vettore di traslazione finali edefinitiviAnche in questo caso come per ScanSet la classe egrave stata sviluppata in modo tale

38


Figura 42 Diagramma delle classi ScanSet e ScanMatcher

da garantire una certa flessibilitagrave lascia cioegrave la possibilitagrave di applicare lrsquoalgoritmosu vari tipi di punti e non limita lrsquouso del programma ad un modello predefinitoAnalogamente allo ScanSet dallo ScanMatcher ereditano due classi EuclideanMatchere MLMMatcher Queste due classi ridefiniscono il metodo minimizeError() per laclasse padre EuclideanMatcher implementa la minimizzazione dellrsquoerrore di ap-prossimazione secondo il modello definito dallrsquoalgoritmo di IDC mentre MLM-Matcher implementa tale approssimazione con la tecnica descritta da MinguezLamiraux e Montesano nel loro articolo (paragrafo 323)

39


La classe ScanFactory ha solo un semplicissimo ruolo quello di creare oggettidi tipo ScanSet e oggetti di tipo ScanMatcher e fa riferimento al pattern Abstract-

Factory (si veda per questo il paragrafo 422) Gli unici metodi implementati al-lrsquointerno di questa classe sono i metodi createScanSet() e createScanMatcher() En-trambi ritornano un puntatore ad un nuovo oggetto di tipo ScanSet o ScanMatchera seconda del caso che lrsquoutente puograve poi utilizzare per lrsquoimmagazzinamento dei datie per lrsquoesecuzione dellrsquoalgoritmoCome ormai si puograve immaginare esistono due classi figlio di ScanFactory la classeEuclideanFactory che definisce i metodi per la creazione di oggetti di tipoEuclideanSet e oggetti di tipo EuclideanMatcher e la classe MLMFactory chedefinisce i metodi per la creazione di oggetti di tipo MLMSet e oggetti di tipo MLM-Matcher

Ai fini dello sviluppo del software per la gestione dellrsquoalgoritmo di Scan Matchingle classi precedentemente descritte sono sufficienti Per motivi di comoditagrave e conuno sguardo allrsquoimmediata applicazione pratica con lo scanner laser SICK LMS200 si egrave preferito implementare altre due semplici classi

bull Point che definisce un punto nello spazio bidimensionale e fornisce i meto-di per settare le coordinate X e Y del punto

bull Insertion il cui compito egrave quello di immagazzinare i dati contenuti in unsemplice file di testo allrsquointerno di un contenitore di tipo ScanSet

Viene comunque lasciata aperta la possibilitagrave allrsquoutente finale di utilizzare altre clas-si per rappresentare Point Vi sono perograve dei vincoli che assolutamente devono es-sere rispettati poichegrave lrsquoalgoritmo funziona solo nello spazio bidimensionale il tipodi punto che si vuole definire deve avere solo due dimensioni inoltre allrsquointernodella classe Punto devono essere ridefiniti lrsquooperatore di assegnamento ldquoopera-tor=()ldquo e lrsquooperatore di sottoscrizione ldquooperator[]()ldquo essendo largamente utilizzatiallrsquointerno del programma

40


422 Strumenti utilizzati

Durante la fase di analisi generale riguardante le tecniche di Scan Matching si egravepotuto constatare la presenza di una grande varietagrave di esse Nella realizzazione diquesto progetto si egrave voluto prendere in esame solo due di queste tecniche ma non egravedetto che quelle scelte siano le migliori e le piugrave accurate fra tutte In eventuali appli-cazioni future potrebbe nascere la necessitagrave poichegrave magari rivelatesi maggiormenteprecise o con minore complessitagrave computazionale di adottare altre metodologie dicalcolo dello Scan Matching oltre o in sostituzione alle due giagrave implementate In-oltre come evidenziato nel paragrafo precedente il grado di libertagrave non si limitaalla scelta della tecnica di associazione fra le scansioni ma si estende alla possibil-itagrave di decidere che genere di contenitore utilizzare e su quale tipo di dato svolgerelrsquoalgoritmo La struttura e gli strumenti utilizzati per lo sviluppo del software sonostati appositamente selezionati per dare un carattere di flessibilitagrave al progetto e perpermettere lrsquouso di numerose tecniche di matchingLo strumento per gestire la molteplicitagrave delle soluzioni e delle scelte possibili risiedenel costrutto template supportato dal linguaggio di programmazione ad oggettiC++ Tale costrutto egrave il fondamento della cosiddetta programmazione generica Laprogrammazione generica egrave quel paradigma di programmazione che si fonda sullacostruzione dei tipi definendone i requisiti fondamentali e sulla definizione di algo-ritmi i quali operano su tipi che soddisfino tali requisiti[13]Tutte le classi realizzate nel progetto ad eccezione delle classi Point e Insertion checome descritto nel paragrafo 421 rivestono un ruolo secondario sono state imple-mentate utilizzando la tecnica dei template Per facilitare la comprensione dellrsquousodi tale costrutto egrave bene osservarne un esempio

Nel listato 41 egrave mostrata la definizione di una tipica classe template e il codiceda editare per creare un oggetto appartenente a tale classe Si puograve notare che nellrsquois-tanza che genera lrsquooggetto Template newTemplate egrave necessario specificare i tipiP e Container presenti nella definizione della classe template Ogni qualvolta sidesideri creare un nuovo oggetto egrave possibile specificare tipi differenti creando cosigraveuna varietagrave di oggetti appartenenti alla stessa classe ma con caratteristiche diversefra loro Vi sono chiaramente poi delle limitazioni nellrsquouso dei template I tipi che sispecificano devono essere compatibili con la classe devono pertanto essere costruiti

41


template lt c l a s s P template lt c l a s s gt c l a s s C o n t a i n e r gtc l a s s Templa te

p u b l i c

p r i v a t e

Template ltP C o n t a i n e r ltPgt newTemplate

Listato 41 Esempio di classi template

in modo tale da poter essere utilizzati dai metodi della classe template (per esempiopotrebbero dover avere definiti al loro interno particolari operatori) Il controllo diquesti vincoli avviene chiaramente nel processo di compilazione La possibilitagrave discelta fra varie categorie di punti su cui operare lo scan matching e fra varie cate-gorie di contenitori in cui memorizzare i punti egrave stata ottenuta definendo la classeScanSet come una classe template del tutto similare a quella riportata nellrsquoesem-pio

Il polimorfismo della struttura oltre che allrsquouso del costrutto template egrave dovutoal concetto di Ereditarietagrave proprio della programmazione orientata agli oggettiLrsquoEreditarietagrave si fonda sulla presenza di unrsquointerfaccia base dichiarata in modo es-plicito e sullrsquoimplementazione di classi da essa derivate Attraverso lrsquouso di uno spe-ciale specificatore virtual si rende possibile allo sviluppatore ridefinire alcunimetodi della classe base allrsquointerno delle classi derivate La sintassi del costruttoappena presentato viene mostrata nel listato 42

Grazie allrsquouso dello specificatore virtual la classe Son al suo interno potragraveridefinire il metodo Method della classe base Father facendo eseguire in questomodo due cose diverse a seconda se ci si trovi al cospetto del metodo appartenenteal figlio o del metodo appartenente al padre Questo tipo di tecnica egrave stata adot-tata per creare le dipendenze fra la classe ScanSet e le classi EuclideanSet

42


c l a s s F a t h e r

p u b l i c

v i r t u a l vo id Method ( ) make Something

p r i v a t e

c l a s s Son p u b l i c F a t h e r

v i r t u a l vo id Method ( )

make S o m e t h i n g D i f f e r e n t

Listato 42 Esempio dellrsquouso dello specificatore virtual

e MLMSet con la ridefinizione del metodo per calcolare la distanza fra due puntiAnalogamente si egrave ottenuto lo stesso effetto tra la classe ScanMatcher e le classiEuclideanMatcher e MLMMatcher con la ridefinizione del metodo per il cal-colo dellrsquoapprossimazione dellrsquoerrore

Un altro aspetto importante per quanto riguarda gli strumenti adoperati risiedenellrsquoutilizzo delle factories Una factory egrave una semplice interfaccia che imple-menta alcuni metodi finalizzati alla creazione di oggetti Per riportare un esempiola classe ScanFactory possiede al suo interno i metodi createScanSet e cre-

ateScanMatcher che ritornano rispettivamente un puntatore ad un oggetto ScanSeted un puntatore ad un oggetto ScanMatcher Per rispecchiare la simmetria con le

43


altre due classi principali della struttura anche la classe AbstractFactory

possiede due classi figlio che prendono il nome di EuclideanFactory e diMLMFactory Come si puograve facilmente intuire la prima gestisce la creazione dioggetti EuclideanSet ed EuclideanMatcher mentre la seconda provvede alla creazionedi oggetti MLMSet e MLMMatcherSono stati piugrave volte presentati in questo capitolo il polimorfismo e la simmetriacaratterizzanti la struttura delle classi del software Si egrave volutamente dato questotipo di caratteristiche al progetto anche in vista di un possibile sviluppo futuro cheimpieghi lrsquouso delle cosiddette Policies Il concetto che risiede alla base di questostrumento egrave quello di decomporre una classe che puograve svolgere il proprio compi-to in varie modalitagrave diverse in diverse ldquopoliticheldquo Una politica allora in pocheparole definisce unrsquointerfaccia astratta che puograve eseguire i propri metodi in vari mo-di Queste modalitagrave saranno poi implementate nelle istanze dellrsquointerfaccia dettepolicy classes [13]

43 Applicazioni pratiche e testing

In questo paragrafo vengono presentati i risultati dei test effettuati con la libreriaimplementata Lrsquoobiettivo di tali esperimenti egrave stato quello di verificare il correttofunzionamento dellrsquoalgoritmo e di valutare la precisione dei risultati ottenuti da es-soInnanzitutto egrave stato necessario acquisire tramite il dispositivo laser (capitolo 2)delle scansioni sulle quali applicare lrsquoalgoritmo Tale operazione egrave stata eseguitaattraverso lrsquouso di un semplice programma di test in C++ che permette di effettuareuna scansione e di memorizzare i dati raccolti in un file di testo In tutti i test larisoluzione del dispositivo laser egrave stata impostata a mezzo grado e si egrave utilizzato unrange angolare di 180 In ogni file di testo sono stati memorizzati perciograve 361 datisotto forma di coordinate cartesianeSi egrave scelto di acquisire le informazioni in un ambiente che avesse un profilo semplicee di facile riconoscimento in modo da non introdurre un certo livello di incertezza odi complessitagrave Pertanto i rilevamenti sono stati effettuati nel corridoio della palazz-ina 1 della sede scientifica di Ingegneria collegando lo scanner laser ad un computerportatile e posizionando entrambi su di un sostegno mobile Lo spazio in questione

44


infatti presenta tratti caratteristici facilmente rilevabili quali le due pareti parallelefra loro e i colonnotti Anche le dimensioni si adattano particolarmente allrsquouso delloscanner laser presentando una lunghezza di circa 8 metri e una larghezza di circa2 metri Come egrave gia stato descritto in questo range di misure il laser presenta unaprecisione dellrsquoordine del millimetro Tutto ciograve risulta visibile in figura 43 la qualeriporta un esempio delle scansioni Non essendo stato realizzato in questo lavoro ditesi un software che visualizzasse le rappresentazioni grafiche delle scansioni essesono state ottenute attraverso lrsquoimplementazione di un semplice script eseguito conil software Matlab version 65 R 13 per piattaforma Windows Nelle circostanze de-

minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000

Figura 43 Scansione del corridoio della palazzina 1

scritte precedentemente sono state prese numerose rilevazioni ognuna delle qualidifferente dalle altre per angolo di rotazione per traslazione o per entrambeEseguita questa fase di acquisizione si egrave proceduto con la fase di analisi dellrsquoalgorit-

45


mo La verifica del corretto funzionamento della libreria egrave stata effettuata off-linepoichegrave i tempi di esecuzione non permettono ancora il suo utilizzo in applicazionidi tipo real-time Nei test egrave stata principalmente verificata la correttezza dei datirisultanti dallrsquoutilizzo dellrsquoalgoritmo di Iterative Closest Point Questo perchegrave datala diffusione di tale tecnica si egrave rivelato maggiormente semplice ricavare dati diconfronto su i quali basare le valutazioniI risultati sui quali fondare la verifica della correttezza del programma sono statiricavati sulla base di una stima manuale e attraverso lrsquoesecuzione di uno script Mat-lab che simula il comportamento dellrsquoICP Il software progettato in questo lavoro ditesi si egrave dimostrato abbastanza preciso ed attendibile per quanto riguarda lrsquoangolodi rotazione Come si puograve osservare dalla tabella 41 i valori dellrsquoangolo θ non sidiscostano in maniera rilevante dai dati sulla rotazione ottenuti attraverso la stimamanuale e lrsquoesecuzione dello script Matlab Tuttrsquoaltro genere di risultati si otten-

Manuale Matlab LibreriaTest θ θ θTest 1-2 1 056 119

Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757

Tabella 41 Risultati ottenuti sullrsquoangolo di rotazione

gono per quello che riguarda la traslazione Essi infatti sia nel caso dello scriptMatlab sia nel caso della libreria implementata differiscono notevolmente da quel-li riscontrati con la stima manuale come egrave visibile nella tabella 42 Sotto questopunto di vista quindi il software risulta essere alquanto inadeguato Il problemapiugrave che a livello di implementazione del codice potrebbe risiedere nel meccanismostesso dellrsquoalgoritmo ICP Questa ipotesi sembrerebbe essere confermata dal fattoche anche unrsquoulteriore implementazione in C++ dellrsquoalgoritmo di ICP trovata inrete [14] porta a risultati errati del vettore di traslazionePer ottenere una buona precisione in entrambe le componenti della trasformazionerigida egrave probabilmente piugrave opportuno scegliere di implementare algoritmi basati

46


Manuale Matlab LibreriaTest x y x y x yTest 1-2 270 1310 329 18 716 31Test 2-3 316 5 1170 221 592 683Test 3-4 055 043 1089 64 90 451Test 4-5 minus380 800 minus1613 1489 minus780 820Test 5-6 minus400 minus500 minus1880 minus181 minus1106 minus152Test 6-7 50 50 minus1476 693 1580 897

Tabella 42 Risultati ottenuti sul vettore di traslazione

sullrsquoICP ma maggiormente evoluti come ad esempio lrsquoalgoritmo di Iterative DualCorrispondence

47

Capitolo 5

Conclusioni

Questo lavoro di tesi ha previsto la valutazione delle prestazioni di un dispositi-vo laser e la realizzazione di una libreria per lrsquoesecuzione di un algoritmo di scanmatchingLa fase iniziale del progetto egrave consistita nellrsquoanalisi del dispositivo sensoriale scan-ner laser Sick LMS 200 Questo tipo di sensore si contraddistingue dalle altre tipolo-gie di dispositivi sensoriali per lrsquoelevata precisione e risoluzione Ciograve ha portato aduna ricostruzione dellrsquoerrore di precisione del sensore nella quale si egrave potuto con-statare un andamento di tipo gaussiano e una concordanza con i principali modelliproposti in letteraturaLa fase piugrave importante e maggiormente impegnativa del progetto di tesi egrave stata larealizzazione di un software in grado di eseguire un algoritmo di scan matching fradue insiemi di punti Per scan matching si intende la ricerca di una trasformazionerigida attraverso la quale due insiemi di punti possano essere sovrapposti Si trat-ta di un problema alla base di molte applicazioni della robotica Infatti tramite ilconfronto fra le scansioni rilevate da un sensore applicato su di un robot e con-corde con esso si puograve riuscire a ricostruire la posizione ed il moto del robot stesso oaddirittura a ricostruire una mappa dellrsquoambiente circostante La caratteristica fon-damentale della libreria realizzata risiede nella flessibilitagrave e nella capacitagrave di gestirepossibili differenti tecniche di matching grazie allrsquoutilizzo dello strumento template

e dellrsquoereditarietagrave propri della programmazione ad oggetti in C++ Il software cosigraverealizzato si rivela estendibile lasciando la possibilitagrave di definire altri algoritmi di

48

Capitolo 5 Conclusioni

scan matching oltre a quelli implementati In lettura egrave proposta una larga varietagrave dialgoritmi di scan matching dei quali i piugrave conosciuti ed adoperati sono stati anal-izzati in parte in una fase di ricerca del progetto di tesi Di questi si egrave scelto diimplementare lrsquoalgoritmo di Iterative Closest Point e lrsquoalgoritmo Metric-based ICPvariante del precedente La scelta egrave stata motivata dalla larga diffusione dellrsquouso del-lrsquoICP nella sovrapposizione delle immagini e quindi dalla affidabilitagrave raggiunta nelsuo utilizzo I risultati ottenuti hanno evidenziato una buona precisione dellrsquoalgorit-mo per quanto riguarda la fase di rotazione della trasformazione rigida Riguardoinvece alla traslazione i risultati non sono altrettanto affidabili poichegrave si discostanolargamente dai valori necessari per sovrapporre le due scansioni Per questo motivoun eventuale sviluppo futuro dovrebbe prevedere lrsquoimplementazione di un algorit-mo efficiente sia sulla rotazione che sulla traslazioneInoltre rendendo sufficientemente leggera e snella la struttura una possibile appli-cazione futura di questa libreria riguarda lrsquoutilizzo di essa in sistemi di tipo real-time per ad esempio il controllo della navigazione di un robot la localizzazione ola ricostruzione di una mappa dellrsquoambiente

49

Bibliografia

[1] HR Everett e L Feng J Borestein Where am I Sensors and Methods for Mobile RobotPositioning 1996

[2] Documentazione laser sick lms 200 httpwwwsickcom

[3] Stefano Zanero e Claudio Merloni Driver per laser sick 200 lmshttpwwweletpolimiituploadzanerosofthtm

[4] Wolfram Burgard e Dieter Fox Sebastian Thrun Probabilistic in robotics MIT Press 2005

[5] D Fox W Burgard and S Thrun Markov localization for mobile robots in dynamicenvironments Journal of Artificial Intelligence Research 11 1999

[6] Feng Lu ed Evangelos Milios Globally consistent range scan alignment for environmentmapping Autonomous Robots 1997

[7] Luca Iocchi e Giorgio Grisetti Andrea Censi Scan matching in the hough domain IEEEProcedings of International Conference on Robotics and Automation 2005

[8] Ingemar j Cox Blanche Position estimation for an autonomous robot vehicle IEEERSJInternational Workshop on Intelligent Robots and Systems 1989

[9] Feng Lu ed Evangelos Milios Robot pose estimation in unknown environments by matching2d range scans Journal of Intelligent and Robotic Systems 1997

[10] Florent Lamiraux e Luis Montesano Javier Minguez Metric-based scan matching algorithmsfor mobile robot displacement estimation citeseeristpsueduminguez05metricbasedhtml2005

[11] Jon Louis Bentley K-d trees for semidynamic point sets Proceedings of the sixth annualsymposium on Computational geometry 1990

[12] Nicolai M Josuttis The C++ Standard Library - A Tutorial and Reference Addison-Wesley

[13] Andrei Alexandrescu Modern C++ Design Addison-Wesley

[14] Tim Bailey Codice sorgente di unrsquoimplementazione dellrsquoalgoritmo di icp in c++ e matlabhttpwwwacfrusydeduauhomepagesacademictbaileysoftwareindexhtml

[15] Jens-Steffen Gutmann e Christian Schlegel Amos Comparison of scan matching approachesfor self-localization in indoor environments 1996

50

Introduzione


Uso dei sensori in robotica

Descrizione dello scanner laser

Driver utilizzato

Analisi delle prestazioni del laser

Scan Matching

Formulazione del problema di Scan Matching

Algoritmi di Scan Matching

Scan Matching con trasformata di Hough

Scan Matching sviluppato da Cox

Iterative Closest Point (ICP)

Considerazioni finali sugli algoritmi

Progettazione dellapplicazione

Obiettivi

Struttura del progetto

Classi sviluppate

Strumenti utilizzati

Applicazioni pratiche e testing

Conclusioni

bibliografia

2

Grazie a tutti e stato davvero bello fare questa tesi spero vada a buon ter-minetanto questa e una prova

Indice

1 Introduzione 1








5 Conclusioni 48

bibliografia 49

i

Capitolo 1

Introduzione


1



2



3

Capitolo 2




4


segnale utilizzato







5










bull e altro


6










7






8






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia

Indice

1 Introduzione 1








5 Conclusioni 48

bibliografia 49

i

Capitolo 1

Introduzione


1



2



3

Capitolo 2




4


segnale utilizzato







5










bull e altro


6










7






8






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia

Capitolo 1

Introduzione


1



2



3

Capitolo 2




4


segnale utilizzato







5










bull e altro


6










7






8






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



2



3

Capitolo 2




4


segnale utilizzato







5










bull e altro


6










7






8






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



3

Capitolo 2




4


segnale utilizzato







5










bull e altro


6










7






8






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia

Capitolo 2




4


segnale utilizzato







5










bull e altro


6










7






8






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia


segnale utilizzato







5










bull e altro


6










7






8






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia










bull e altro


6










7






8






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia










7






8






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia






8






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia






9



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



10




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia




11







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia







12



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



1000

2000

3000

4000

5000

6000



2 Ai


13





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia





p(zkt |xt m) =

N(zk


t le zmax

0 altrimenti(21)

dove

N(zkt zklowast

t σ2) =1radic

2πσ2middot eminus

12middot zk

t minuszklowastt

σ2


14



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



esponenziale

p(zkt |xt m) =

λeminusλzk


0 altrimenti(22)


p(zkt |xt m) =

1 se z = zmax

0 altrimenti(23)


p(zkt |xt m) =

1

zmaxse z = zmax

0 altrimenti(24)



15


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia


0 1000 2000 3000 40002970

2975

2980

2985

2990

2995

2970 2975 2980 2985 2990 29950

50

100

150

200

250

300

350

400




16



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



17

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia

Capitolo 3

Scan Matching




18





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia





19







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia







20










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia










21





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia





ρ =radic


x2 + y2cos(θ) +

yradicx2 + y2

sin(θ)]

=radic





g[f ] =sum

i

f 2i

22


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia


1 2 3 4 5

0

1

2

3

4

5

6

0 2 4 6

minus6

minus4

minus2

0

2

4

6






4 Due alternative

23









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia









24





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia





R =


sin(θ) cos(θ)



S =sum

i





25




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia




Edist(ω T ) =nsum

i=1


=nsum

i=1


i)2 +


(33)







26


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia


dove

x =1

n

nsumi=1

xi y = 1n

sumni=1 yi

xprime =1

n

nsumi=1

xprimei yprime = 1

n

sumni=1 yprimei

Sxxprime =nsum

i=1



Sxyprime =nsum

i=1





dist =radic





27







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia







1 Per ogni punto Pi


i di Pi


i di Pi

28











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia











q =radic

x2 + y2 + L2θ2 (38)

29




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia




dove

q(p1) =



)(310)






2 + L2θ2


dp(p1 p2) =

radicδ2x + δ2


p21x + p2

1y + L2(311)




30



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



Edist(q) =nsum

i=1

(δ2ix + δ2


2

p2ix + p2

iy + L2

)(312)

dove






A =

a11 a12 a13

a12 a22 a23

a13 a23 a33

a11 =nsum

i=1

(p2ix + L2)

a12 =nsum

i=1

pixpiy

a13 =nsum

i=1


a22 =nsum

i=1

(p2iy + L2)

a23 =nsum

i=1


a33 =nsum

i=1



primeixp

primeiy)

31


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia


e

b =

sumn




2iy + L2))sumn



2ix + L2)] +







32



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



33



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



34

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia

Capitolo 4


41 Obiettivi



35




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia




36







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia







bull ScanFactory

bull ScanSet

bull ScanMatcher


37





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia





38




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia




39








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia








40





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia





41



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



p u b l i c

p r i v a t e






42



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



p u b l i c


p r i v a t e








43






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia






44



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



minus1000 minus500 0 500 1000 15000

1000

2000

3000

4000

5000

6000

7000

8000

9000



45




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia




Test 2-3 26 21 31

Test 3-4 2574 19 2559

Test 4-5 4555 52 4221

Test 5-6 44 4113 4134

Test 6-7 35 3762 3757



46





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia





47

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia

Capitolo 5

Conclusioni



48



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia



49

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia

Bibliografia
















50

Introduzione




Driver utilizzato


Scan Matching








Obiettivi


Classi sviluppate



Conclusioni

bibliografia

REALIZZAZIONE DI UN ALGORITMO DI SCAN MATCHING PER …rizzini/student_theses/TesiCapra.pdf · 2.1...

Documents

Transcript of REALIZZAZIONE DI UN ALGORITMO DI SCAN MATCHING PER …rizzini/student_theses/TesiCapra.pdf · 2.1...