• Non ci sono risultati.

Elaborazione di immagini stereoscopiche per sistemi Sense and Avoid di velivoli unmanned

N/A
N/A
Protected

Academic year: 2021

Condividi "Elaborazione di immagini stereoscopiche per sistemi Sense and Avoid di velivoli unmanned"

Copied!
72
0
0

Testo completo

(1)

Scuola di Ingegneria

Dipartimento di Ingegneria Civile e Industriale Corso di Laurea Magistrale in Ingegneria Aerospaziale

Tesi di Laurea

Elaborazione di immagini

stereoscopiche per sistemi Sense and

Avoid di velivoli unmanned

Candidato:

Matteo Pizzolante

Relatori:

Prof. Eugenio Denti

Prof. Roberto Galatolo

Ing. Francesco Schettini

Ing. Gianpietro Di Rito

(2)

‘‘Diciamo che una macchina ultraintelligente sia definita come una macchina che pu`o sorpassare di molto tutte le attivit`a intellettuali di qualsiasi uomo per quanto sia abile. Dato che il progetto di queste macchine `e una di queste attivit`a intellettuali, una macchina ultraintelligente potrebbe progettare macchine sempre migliori; quindi, ci sarebbe una ‘esplosione di intelligenza’, e l’intelligenza dell’uomo sarebbe lasciata molto indietro. Quindi, la prima macchina ultraintelligente sar`a l’ultima invenzione che l’uomo avr`a la necessit`a di realizzare, a patto che sia abbastanza docile da spiegarci come tenerla sotto controllo.’’ I. J. Good

(3)
(4)

Sommario

Il presente lavoro di tesi rientra in un’attivit`a di ricerca condotta dal Dipartimento di Ingegneria Civile e Industriale dell’Universit`a di Pisa riguardante lo sviluppo di un sistema Sense and Avoid per velivoli a pilotaggio remoto. Non essendoci la presenza di equipaggio a bordo, si ha la necessit`a di implementare sistemi di con-trollo che possano assolvere alcune funzioni che, in velivoli convenzionali, vengono svolte dal pilota.

Tale lavoro consiste nello sviluppo di algoritmi riguardanti la funzione Sense del sistema, equipaggiato con dispositivi di acquisizione di immagini costituiti da una coppia di telecamere stereoscopiche in possesso dal Dipartimento di Ingegneria Civile e Industriale.

Tramite la procedura di calibrazione si `e ottenuta la completa descrizione del si-stema di visione stereoscopico. Successivamente, `e stato sviluppato un algoritmo (SIFT ) in grado di estrarre le caratteristiche distintive dalle immagini provenienti dal sistema stereo. Di seguito, `e stato sviluppato un algoritmo di matching per effettuare un confronto affidabile tra le caratteristiche e, quindi, per rilevare le cor-rispondenze delle immagini stereoscopiche. Infine, `e stata sviluppata una tecnica di triangolazione tridimensionale in grado di valutare la distanza di un qualsiasi punto dello scenario rappresentato dal sistema di visione stereoscopico.

Gli algoritmi sono stati tutti interamente realizzati in ambiente MATLAB per ottenere un miglior interfacciamento con il sistema di visione presente.

(5)

Indice

1 Introduzione 1

1.1 Normativa . . . 2

1.2 Sistemi Sense and Avoid . . . 3

1.2.1 Gestione dei conflitti . . . 5

1.2.2 Funzioni del sistema Sense and Avoid . . . 6

1.2.3 Sensori . . . 8

2 SIFT: Scale Invariant Feature Transform 10 2.1 Immagini digitali . . . 11

2.2 L’algoritmo . . . 12

2.2.1 Identificazione degli estremi locali . . . 12

2.2.2 Localizzazione dei keypoints . . . 14

2.2.3 Assegnazione dell’orientazione . . . 17

2.2.4 Generazione dei descrittori . . . 18

2.3 Applicazioni . . . 19

2.3.1 Riconoscimento di oggetti . . . 20

2.3.2 Localizzazione e mappatura . . . 21

2.3.3 Stitching . . . 21

2.3.4 Modellizzazione, riconoscimento e monitoraggio di scene 3D 22 2.3.5 Analisi di risonanze magnetiche . . . 22

2.4 Esperienze . . . 23

3 Visione stereoscopica 27 3.1 Geometria sistema stereo . . . 27

(6)

INDICE ii 3.2 Calibrazione . . . 30 3.3 Risultati calibrazione . . . 33 4 Matching e triangolazione 35 4.1 Matching di features . . . 35 4.2 Mappa di disparit`a . . . 37 4.3 Triangolazione tridimensionale . . . 39 5 Risultati 41

6 Conclusioni e sviluppi futuri 48

A Piattaforme UAV 50

B Caratteristiche sistema stereo 52

C Filtro Gaussiano 55

(7)

Elenco delle figure

1.1 Applicazioni UAVs . . . 1

1.2 Schema a blocchi per sistema SAA . . . 4

1.3 Timeline di un sistema Sense and Avoid . . . 4

1.4 Gestione dei conflitti . . . 5

1.5 Raffigurazione soglie di SS e CA . . . 6

1.6 Operazione di un sistema SAA . . . 7

2.1 Rappresentazione numerica immagine a colori . . . 11

2.2 Filtraggio con kernel gaussiani di varianza crescente . . . 12

2.3 Rappresentazione DoG . . . 13

2.4 Rilevamento di massimi e minimi della funzione D(x, y, σ) . . . . 15

2.5 Rilevamento degli estremi effettivi della funzione . . . 16

2.6 Istogramma delle orientazioni . . . 17

2.7 Descrittore note le orientazioni nell’intorno del keypoint . . . 18

2.8 Esempio di riconoscimento . . . 20

2.9 Esempio di stitching . . . 21

2.10 Primo step . . . 24

2.11 Secondo step . . . 25

2.12 Terzo step . . . 26

3.1 Proiezione di punti distinti nello spazio nel piano immagine . . . . 27

3.2 Principio di un sistema stereoscopico . . . 28

3.3 Vincolo epipolare . . . 29

3.4 Immagini in forma standard . . . 30

(8)

ELENCO DELLE FIGURE iv

3.5 Set di immagini per la calibrazione . . . 31

3.6 Sistema di riferimento scena . . . 32

3.7 Parametri estrinseci . . . 34

4.1 Rappresentazione distanza euclidea features . . . 36

4.2 Densit`a di probabilit`a di match corretti ed errati . . . 37

4.3 Definizione di disparit`a . . . 37

4.4 Area di copertura . . . 38

4.5 Triangolazione stereoscopica . . . 39

5.1 Immagine filtrata . . . 41

5.2 (a.): punti estremi, (b.): punti filtrati, (c.): punti con orientazione 42 5.3 Coppia di immagini stereo processate . . . 43

5.4 Matching di coppia di immagini stereo, R = 0.4 . . . 43

5.5 Matching con R = 0.7 e R = 0.1 . . . 44

5.6 Filtraggio immagine con funzione gaussiana . . . 45

5.7 (a.): punti estremi, (b.): punti filtrati . . . 45

5.8 Punti notevoli di interesse . . . 46

5.9 Immagini stereo processate . . . 46

5.10 Matching coppia immagini stereo . . . 47

A.1 Classi di UAV . . . 51

B.1 Architettura del sistema OptoMotive Cameleon . . . 52

B.2 Struttura sistema di visione . . . 54

C.1 Funzione Gaussiana (a) 1D e−l2/2σ2, (b) 2D con σ = 3 e (c) trasfor-mata di Fourier di h(l, k) . . . 55

D.1 Funzione Laplaciano della Gaussiana . . . 59

(9)

Elenco delle tabelle

1.1 Confronto sensori . . . 8

3.1 Parametri intrinseci left camera . . . 33

3.2 Parametri intrinseci right camera . . . 33

3.3 Parametri estrinseci right wrt left camera . . . 34

B.1 Specifiche tecniche . . . 53

(10)

Capitolo 1

Introduzione

Tra le tante novit`a che, negli ultimi anni, hanno caratterizzato il settore dell’avia-zione civile, particolarmente rilevante `e lo sviluppo degli aeromobili a pilotaggio remoto. Un UAV, Unmanned Aerial Vehicle, `e un velivolo in grado di compiere missioni di volo senza equipaggio a bordo (Appendice A). Il loro utilizzo `e ormai consolidato per usi militari ed `e in forte crescita anche in ambito civile [1]. In Figura 1.1, si rappresenta la grande variet`a di progetti relativi allo sviluppo di aeromobili a pilotaggio remoto ed ognuno di essi presenta obiettivi e campi di applicazione differenti.

Figura 1.1: Applicazioni UAVs

(11)

CAPITOLO 1. INTRODUZIONE 2 La diffusione sempre maggiore dell’uso di questi velivoli `e dovuto ai numerosi van-taggi che possiedono rispetto agli aeromobili convenzionali in termini di costi e pesi. Oltretutto, le capacit`a di manovra dei tradizionali velivoli sono fortemente vincolate dalle capacit`a fisiche dei piloti [2]. Spostando l’interfaccia pilota-velivolo a terra, `e possibile ottenere prestazioni ancora pi`u elevate. Infine, considerando la presenza di missioni di volo che possono mettere a rischio l’incolumit`a dell’e-quipaggio, attualmente si affidano ad aeromobili a pilotaggio remoto le seguenti funzioni:

• Dirty: missioni ‘sporche’, in cui l’ambiente `e contaminato da inquinamento nucleare, chimico o batteriologico;

• Dull : missioni ‘monotone’, tipicamente di lunga durata, come la sorveglianza e la ricognizione;

• Dangerous: missioni pericolose con sorvolo di aree ostili;

Da questo, si evince la necessit`a di un sistema regolatorio nell’individuazione di leggi adeguate a fornire, da un lato, le necessarie garanzie di sicurezza ai cittadini che si servono del trasporto aereo ed ai cittadini sorvolati e, dall’altro, certezze nell’utilizzo di tali mezzi per gli operatori che intendono farne uso.

1.1

Normativa

L’Ente Nazionale Aviazione Civile, ENAC, ha stilato un regolamento riguardante i mezzi a pilotaggio remoto nel quale si descrivono norme e comportamenti necessari per garantire la sicurezza [3]. Non essendoci un pilota a bordo degli UAV, il motivo principale dell’utilizzo di determinati sistemi di sicurezza non `e necessariamente quello di salvaguardare l’aeromobile ma `e certamente essenziale evitare impatti con persone sul terreno o danni alle propriet`a.

In particolare, si descrivono le regole di circolazione e utilizzo dello spazio aereo distinguendo:

• Visual Line of Sight, VLOS : operazioni condotte entro una distanza tale per cui il pilota remoto `e in grado di mantenere il contatto visivo continuativo

(12)

CAPITOLO 1. INTRODUZIONE 3 con il mezzo aereo, senza aiuto di strumenti per aumentare la vista, tale da consentirgli un controllo diretto del mezzo per gestire il volo;

• Extended Visual Line of Sight, EVLOS : operazioni condotte in aree le cui dimensioni superano i limiti delle condizioni VLOS e per le quali i requisiti del VLOS sono soddisfatti con l’uso di metodi alternativi;

• Beyond Visual Line of Sight, BVLOS : operazioni condotte ad una distanza che non consente al pilota remoto di rimanere in contatto visivo diretto e costante con il mezzo aereo, di gestire il volo, mantenere le separazioni ed evitare collisioni;

Per quanto riguarda BVLOS, si necessita di sistemi e procedure per il mante-nimento della separazione e per evitare collisioni che richiedono l’approvazione da parte dell’ENAC. Tale regolamento, infatti, non comprende i mezzi autono-mi, come i sistemi Sense and Avoid, in quanto non rientrano nella definizione di aeromobile descritta [4]. Si attende, nel prossimo futuro, la stesura delle norme europee EASA, European Aviation Safety Agency, in cui anche i sistemi autonomi entreranno nello spazio aereo regolamentato [5].

1.2

Sistemi Sense and Avoid

Lo scopo di un sistema Sense and Avoid `e di agire al posto del pilota per rilevare e risolvere alcuni rischi per la sicurezza in volo. In particolare, come descrive la Federal Aviation Administration in [6], SAA `e la capacit`a di un UAV di essere well clear per gli altri velivoli e di evitare collisioni con oggetti o altro traffico aereo. Il concetto well clear `e stato proposto come uno standard di separazione in volo a cui un sistema SAA deve aderire. Quindi, si pu`o affermare che indichi essenzialmente una norma utilizzata per determinare le azioni necessarie in modo da mantenere una distanza adeguata dagli altri velivoli.

Lo sviluppo di un sistema SAA pone le basi su requisiti che garantiscono livelli di sicurezza equivalenti a quelli ottenuti con la capacit`a See and Avoid di aeromobili con equipaggio a bordo.

(13)

CAPITOLO 1. INTRODUZIONE 4

Figura 1.2: Schema a blocchi per sistema SAA

Affinch`e un UAV possa sottrarsi in modo autonomo da eventuali collisioni, deve essere in grado di svolgere diversi compiti identificati in due fasi principali. La prima, denominata Sense, ha la funzione di ricevere segnali relativi alla posizione e alla velocit`a di eventuali ostacoli presenti sulla rotta, attravarso l’utilizzo di una serie di sensori. La seconda fase, Avoid, ha il compito di ricevere e confrontare i dati forniti dalla funzione Sense e successivamente elaborare, attraverso opportu-ne logiche, una traiettoria di evasioopportu-ne.

Figura 1.3: Timeline di un sistema Sense and Avoid

Tale traiettoria deve osservare le regole dell’aria e garantire la separazione necessa-ria. Il sistema SAA deve essere sviluppato in modo che la sua condotta operativa

(14)

CAPITOLO 1. INTRODUZIONE 5 rispetti i principi di gestione dei conflitti indicati nei documenti dell’International Civil Aviation Organization, ICAO.

1.2.1

Gestione dei conflitti

Come rappresentato in Fig 1.4, il processo di gestione dei conflitti `e suddiviso in tre layers: Strategic Conflict Management, Separation Provision e Collision avoi-dance [7].

Figura 1.4: Gestione dei conflitti

Il primo layer si attua prima della gestione tattica dei conflitti. Tale gestione, infatti, `e strategica e si concretizza attraverso un’opportuna pianificazione del traffico aereo. In genere le azioni associate a questa fase si realizzano prima della partenza. Le misure adottate hanno come obiettivo principale quello di ridurre il pi`u possibile la necessit`a di applicare la fase successiva o perlomeno di ottenere che il numero di volte in cui avviene l’applicazione della seconda fase sia congruente con un valore di sicurezza predefinito. Il secondo layer, Separation Provision, rea-lizza il piano tattico secondo il quale si vuole mantenere l’UAV lontano dai pericoli di almeno una distanza minima, ossia di una quantit`a cui `e associato un rischio di collisione compatibile con il livello di sicurezza richiesto. Separation Provision entra in azione quando la fase precendete diventa inefficiente o non applicabile e

(15)

CAPITOLO 1. INTRODUZIONE 6 quindi quando si sta per verificare la perdita della separazione minima.

L’ultimo layer viene attivato quando la fase precedente fallisce. Durante la Col-lision Avoidance, nell’evento in cui viene a mancare la separazione minima, il sistema SAA interviene con delle manovre per evitare la collisione.

Si osserva, infine, che l’ampiezza delle tre aree dipende fondamentalmente da due fattori: lo spazio aereo in cui opera l’UAV e l’applicazione o meno del servizio di Controllo del Traffico Aereo, ATC.

1.2.2

Funzioni del sistema Sense and Avoid

Affinch`e un UAV possa essere coinvolto nel traffico aereo deve essere dotato di un sistema SAA per la gestione dei conflitti. In particolare, `e fondamentale lo svol-gimento delle funzioni Self Separation e Collision Avoidance che devono essere attuate quando la pianificazione del volo non garantisce la separazione richiesta dagli altri aeromobili del traffico aereo [8].

Figura 1.5: Raffigurazione soglie di SS e CA

Per quanto concerne Self Separation, nota la posizione e la traiettoria di un ae-romobile visto come potenziale pericolo, deve essere in grado di individuare il conflitto e successivamente ricavare una procedura di separazione che mantenga

(16)

CAPITOLO 1. INTRODUZIONE 7 l’UAV distante da tale pericolo. Questa procedura garantisce la separazione mi-nima e viene realizzata attraverso manovre che modificano la traiettoria originale. Nel momento in cui non `e pi`u garantita la distanza minima di sicurezza, il ri-schio di una collisione provoca l’intervento della funzione Collision Avoidance che dichiara necessaria un’azione per evitare la collisione. Terminata la manovra di evasione e quindi evitata la collisione, il sistema SAA continua a realizzare la Self Separation per rimanere well clear.

In Figura 1.6, si rappresentano, in modo pi`u dettagliato, i principali passi di un sistema Sense and Avoid in prossimit`a di un pericolo.

Figura 1.6: Operazione di un sistema SAA In paticolare si osservano i seguenti step:

• Detect Intruder : individuazione della presenza di un intruso;

• Track Intruder : individuazione della posizione e della velocit`a di un singolo intruso;

(17)

CAPITOLO 1. INTRODUZIONE 8 • Evaluate collision potential : valutazione del rischio di collisione sulla base

delle posizioni e delle velocit`a dell’intruso;

• Prioritize collision threats: individuazione della traiettoria dell’intruso con maggiore probabilit`a di rischio di collisione;

• Declare action is required : individuazione delle azioni richieste;

• Determine an avoidance manoeuvre: determinazione di una manovra di elusione;

• Command manoeuvre: comando della manovra da attuare; • Execute manoeuvre: esecuzione della manovra.

A livello generale, `e desiderabile che qualsiasi sistema SAA abbia sia la funzione Self Separation che la funzione Collision Avoidance, ma questo potrebbe anche non essere necessario come nel caso in cui il servizio di separazione `e fornito dal Controllo del Traffico Aereo. In questo caso `e necessario limitare la funzione SS in quanto le istruzioni del controllore hanno priorit`a sulle indicazioni del sistema SAA ed inoltre le regole di separazione potrebbero essere diverse.

1.2.3

Sensori

Per svolgere le funzioni richieste e quindi garantire un livello di sicurezza adeguato, un sistema Sense and Avoid necessita di particolari sensori che hanno il compito di rilevare la distanza che intercorre tra l’UAV e l’eventuale pericolo.

ACTIVE PASSIVE

Power High Low

Field of Regard Little Extended

Resolution Low High

Computational load Light Heavy Tabella 1.1: Confronto sensori

(18)

CAPITOLO 1. INTRODUZIONE 9 passivo. I sensori attivi forniscono la misura diretta della distanza basandosi su radiazioni acustiche ed elettromagnetiche. Il rilevamento passivo, invece, permette di ricavare la medesima distanza utilizzando, ad esempio, dispositivi per l’acqui-sizione di immagini, come le telecamere. La presenza di un singolo dispositivo permette di ricavare un’immagine bidimensionale perdendo l’informazione sulla profondit`a. Per ovviare a questo problema si fa uso di un sistema di visione com-posto da almeno due camere associato a tecniche di stereoscopia per ricavare una mappatura tridimensionale dello spazio.

In Tabella 1.1, si mettono a confronto i due tipi di sensori descritti considerando caratteristiche come potenza richiesta, campo di osservazione, risoluzione e carico computazionale. Si osserva molto chiaramente che il principale vantaggio garanti-to dai sensori attivi `e il basso carico computazionale necessario per fornire la stima della distanza. Tuttavia, tali sensori richiedono una alta fornitura di potenza e offrono un campo di osservazione basso. Inoltre, la risoluzione `e determinata dalla dimensione dell’antenna e quindi per ridurre ingombri e pesi si preferisce utilizzare piccole antenne che forniscono lunghezze d’onda ridotte.

Il contrario si ha per i sensori passivi. In questo caso, i sensori garantiscono una elevata risoluzione e un campo di osservazione esteso richiedendo bassa potenza. Lo svantaggio si ha in termini di carico computazionale in quanto sono necessari software in grado di gestire e processare le immagini in ingresso estrapolando le caratteristiche salienti necessarie per le tecniche di triangolazione.

Il software candidato per questo utilizzo `e il SIFT, Scale Invariant Feature Tran-sform. Tale algoritmo, gi`a noto in letteratura [9] [10], `e stato sviluppato intera-mente in ambiente MATLAB ed applicato ad immagini ottenute dal sistema di vi-sione stereoscopico acquistato dal Dipartimento di Ingegneria Civile ed Industriale dell’Universit`a di Pisa (Appendice B).

(19)

Capitolo 2

SIFT: Scale Invariant Feature

Transform

L’algoritmo SIFT rappresenta un metodo per estrarre le caratteristiche locali da un’immagine, che siano distintive e invarianti, necessarie per effettuare un confronto affidabile tra viste della medesima scena [9] [10].

Il procedimento di calcolo pu`o essere suddiviso nei seguenti stadi:

• Rilevamento dell’estremo nello scale space. In questa prima fase di calcolo si ricercano i punti notevoli di interesse invarianti rispetto alla riduzione in scala e all’orientamento facendo uso della funzione differenze di Gaussiane. • Localizzazione dei keypoint. Si eseguono successivi filtraggi dei punti

can-didati trovati. I punti chiave si selezionano su misurazioni basate sulla loro stabilit`a.

• Assegnazione dell’orientazione. Si assegnano una o pi`u orientazioni per ciascun keypoint basati sulle direzioni locali del gradiente dell’immagine. • Generazione del descrittore. I gradienti locali dell’immagine sono misurati

rispetto la riduzione di scala selezionata nella regione che circonda ciascun keypoint.

Da questa descrizione generale si osserva che l’algoritmo trasforma i dati dell’im-magine in coordinate invarianti alla scalatura relativi ai descrittori locali.

(20)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 11

2.1

Immagini digitali

Un’immagine digitale `e la rappresentazione numerica di una immagine bidimen-sionale. Tale rappresentazione `e composta da una matrice di punti, detti pixel, la cui colorazione `e definita tramite uno o pi`u valori numerici.

I valori memorizzati indicano le caratteristiche di ogni pixel dell’immagine da rappresentare:

• nelle immagini a colori viene memorizzato solitamente il livello di intensit`a dei colori fondamentali;

• nelle immagini monocromatiche in scala di grigio il valore indica l’intensit`a del grigio, che varia dal nero (valore 0) al bianco (valore 1).

Figura 2.1: Rappresentazione numerica immagine a colori

In Figura 2.1, sono raffigurate rispettivamente le rappresentazioni numeriche di una zona ristretta di pixel di una immagine a colori e successivamente in scala di grigio. Si osserva che in questo ultimo caso i valori presenti nella matrice sono compresi nell’intervallo tra zero e uno.

(21)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 12 Ai fini dell’implementazione dell’algoritmo SIFT, le immagini da processare so-no moso-nocromatiche su scala di grigio in quanto, rispetto alle immagini a co-lori, `e possibile ottere maggiore semplicit`a di sviluppo e riduzione del carico computazionale.

2.2

L’algoritmo

2.2.1

Identificazione degli estremi locali

L’obiettivo primario di questa procedura `e di individuare i punti dell’immagine, scale space extrema locations, che sono invarianti ai cambiamenti di scala e che presentino una certa robustezza ai cambiamenti di illuminazione, del punto di osservazione e all’aggiunta di rumore esterno. La ricerca di tali punti pu`o es-sere condotta attraverso la costruzione di uno scale space. La rappresentazione multiscala si ricava tramite un filtraggio in cascata dell’immagine originale con successive convoluzioni gaussiane (Appendice C).

Figura 2.2: Filtraggio con kernel gaussiani di varianza crescente

In particolare, data un’immagine I(x, y) e un filtro gaussiano G(x, y, σ) di varianza σ, lo scale space associato all’immagine `e dato da:

L(x, y, σ) = G(x, y, σ) ∗ I(x, y) dove con ∗ si indica l’operazione di convoluzione in x e y e

G(x, y, σ) = 1 2πσ2e

(22)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 13 avente valore medio nullo e varianza σ assegnata. Effettuando la convoluzione tra l’immagine data e la funzione gaussiana, si ottiene una nuova immagine che `e la riproduzione dell’immagine iniziale, ma sfocata. L’intensita di tale sfocatura viene definita dal valore del raggio σ.

La costruzione dello scale space avviene filtrando iterativamente l’immagine ad intervalli regolari, dando origine a gruppi di immagini detti ottave. Per ricavare i punti di maggiore interesse all’interno dello scale space si introduce la funzio-ne DoG, Difference of Gaussian, calcolata come la differenza tra due funzioni gaussiane, considerate a scale consecutive:

D(x, y, σ) = (G(x, y, kσ) − G(x, y, σ)) ∗ I(x, y) = L(x, y, kσ) − L(x, y, σ)

Figura 2.3: Rappresentazione DoG

La scelta di questa particolare funzione `e dovuta a diverse ragioni (Appendice D). Un primo aspetto rigurda l’efficienza nel calcolo; essendo gi`a note le convoluzioni L(x, y, σ) necessarie per la descrizione dello scale space, la funzione D(x, y, σ) `e il risultato di una semplice sottrazione di queste. In secondo luogo, la funzione DoG

(23)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 14 fornisce una buona approssimazione della funzione LoG, Laplacian of Gaussian, normalizzato in scala, σ2∇2G. Tale normalizzazione `e necessaria per l’invarianza.

La relazione che intercorre tra DoG e σ2∇2G si pu`o scrivere:

∂G

∂σ = σ∇

2G

da cui si ha, tramite l’approssimazione alle differenze finite: σ∇2G = ∂G ∂σ ≈ G(x, y, kσ) − G(x, y, σ) kσ − σ e quindi: G(x, y, kσ) − G(x, y, σ) ≈ (k − 1)σ2∇2G

Il fattore (k − 1) non influenza la locazione del massimo nell’equazione in quanto `e una costante in ogni scala. L’errore di approssimazione tende a zero quando k tende a uno e l’approssimazione stessa non ha un forte impatto sulla stabilit`a del-la ricerca del massimo, cos`ı come suldel-la sua localizzazione, per alcune significanti riduzioni di scala.

In Figura 2.3 si rappresenta la costruzione della funzione DoG. Nella colonna di sinistra, l’immagine originaria viene convoluta con una funzione gaussiana di va-rianza crescente per produrre, all’interno dello scale space, immagini separate da un fattore costante k chiamate ottave. Ogni ottava viene suddivisa in un numero intero di intervalli s in modo che sia verificata la relazione k = 21/s. Per ogni ottava, `e necessario produrre s + 3 immagini convolute. Completata la costruzio-ne di un’ottava, le immagini adiacenti in scala vengono sottratte algebricamente in modo da ottenere le DoG, rappresentate nella colonna di destra. Processa-ta un’intera otProcessa-tava, si ricampiona l’immagine convoluProcessa-ta che presenProcessa-ta il valore di deviazione standard doppio rispetto a quello iniziale e si ripete il processo.

2.2.2

Localizzazione dei keypoints

I punti di interesse sono gli estremi locali della funzione D(x, y, σ). Per deter-minare questi keypoints, ciascun punto viene confrontato con i suoi otto vicini nell’immagine corrente e i nove vicini della scala superiore e inferiore, come rap-presentato in Figura 2.4. Il criterio per cui un punto sia un massimo o un minimo

(24)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 15

Figura 2.4: Rilevamento di massimi e minimi della funzione D(x, y, σ) locale `e che risulti pi`u grande (vicino al valore 1) o pi`u piccolo (vicino al valore 0) tra tutti i suoi vicini.

Il passo successivo, rilevati i punti chiave, `e quello di eliminare i punti con basso contrasto, valutando la presenza di bordi e linee, che vengono interpolate per au-mentare la precisione, la stabilit`a e il matching dei punti.

La tecnica consiste nell’interpolazione quadratica 3D dei campioni nell’intorno di un estremo locale e utilizza l’espansione di Taylor al secondo ordine della funzione dello scale space D(x, y, σ), traslata in modo che l’origine sia posta sulle stesse coordinate del campione dell’immagine:

D(x) = D +∂D ∂x T x + 1 2x T∂2D ∂x2x

dove D e le sue derivate vengono valutate nel punto campione e x = (x, y, σ)T `e l’offset da tale punto.

L’estremo x di tale funzione, calcolato ponendo a zero le derivate, `b e dato da:

b x = ∂ 2D ∂x2 −1 ∂D ∂x

Il valore assunto dalla funzione nei punti estremi, confrontato con una soglia imposta, `e necessario per eliminare i punti a basso contrasto:

D(x) = D +b 1 2 ∂D ∂x T b x

(25)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 16 L’eliminazione degli estremi a basso contrasto non `e sufficiente a garantire la stabilit`a.

Figura 2.5: Rilevamento degli estremi effettivi della funzione

La funzione DoG ha una forte risposta lungo i bordi, edges, anche se la posizione lungo i contorni viene determinata con scarsa precisione.

Si considera la seguente matrice Hessiana:

H =   Dxx Dxy Dxy Dyy  

Gli autovalori di H sono proporzionali alle curvature principali di D. Consi-derando α l’autovalore pi`u grande e β quello pi`u piccolo valgono le seguenti relazioni:

T r(H) = Dxx+ Dyy = α + β

Det(H) = DxxDyy− D2xy = αβ

Se il determinante `e negativo, le curvature hanno segni opposti e conseguentemente il punto viene scartato non essendo un estremo.

Definendo r il rapporto tra l’autovalore pi`u grande e il pi`u piccolo, `e possibile scrivere: T r(H)2 Det(H) = (α + β)2 αβ = (rβ + β)2 rβ2 = (r + 1)2 r

(26)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 17 La quantit`a (r+1)2/r `e minima quando i due autovalori sono uguali, mentre cresce

al crescere di r. Quindi, per imporre che il rapporto tra curvature principali sia sotto una certa soglia, occorre fissare r tale che:

T r(H)2

Det(H) <

(r + 1)2

r

Il valore di soglia proposto, in questo lavoro, `e r = 10 e determina l’eliminazione di tutti i keypoints che hanno un rapporto tra le curvature principali maggiore della soglia imposta.

2.2.3

Assegnazione dell’orientazione

Dopo aver individuato per ciascun keypoint le coordinate e la scala, il passo succes-sivo `e determinare l’orientazione dell’estremo per garantire una buona robustezza rispetto alle rotazioni. La scala associata al keypoint viene utilizzata per scegliere, nella piramide gaussiana, l’immagine con la scala pi`u vicina. Si calcolano quin-di, per ogni campione dell’immagine L(x, y) alla scala scelta, il modulo m(x, y) e l’orientazione θ(x, y) del gradiente locale, applicando le differenze tra pixel:

m(x, y) =q(L(x + 1, y) − L(x − 1, y))2+ (L(x, y + 1) − L(x, y − 1))2

θ(x, y) = tan−1(L(x, y + 1) − L(x, y − 1)) (L(x + 1, y) − L(x − 1, y))

(27)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 18 Successivamente si costruisce un istogramma di orientazioni costituito dalle orien-tazioni del gradiente dei punti campionati in una regione attorno al keypoint. Cia-scun istogramma `e composto da 36 bin che coprono i 360 gradi assumibili. Ogni campione aggiunto all’istogramma viene pesato con il valore dell’ampiezza del gradiente in quel punto. I picchi nell’istogramma delle orientazioni corrispondono alle orientazioni dominanti dei gradienti locali. Per determinare tale orientazione viene identificato il picco pi`u alto nell’istogramma e poi vengono considerati tutti gli altri picchi che hanno un valore pari almeno all’80% del valore massimo trova-to. Nel caso in cui siano stati selezionati pi`u picchi verranno creati vari keypoints con stessa posizione, stessa scala ma differente orientazione.

2.2.4

Generazione dei descrittori

Le operazioni precedenti hanno assegnato a ciascun keypoint una posizione, una scala e un’orientazione. Questi parametri costituiscono un sistema di coordinate locali 2D, con cui `e possibile descrivere localmente una regione dell’immagine e assicurare l’invarianza di tali parametri. Per ultimo, occorre attribuire a ciascun punto chiave un descrittore in modo che esso risulti invariante anche rispetto a cambiamenti di illuminazione e punti di vista 3D.

Il calcolo dei descrittori di punti chiave viene rappresentato in Figura 2.7.

(28)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 19 L’ampiezza del gradiente dell’immagine e le orientazioni vengono campionate at-torno alla posizione dei punti chiave, usando la scala del keypoint per selezionare il livello della Gaussiana. Per ottenere l’invarianza alla rotazione, le coordinate del descrittore e l’orientazione del gradiente sono ruotati relativamente all’orien-tazione dei keypoints. In particolare, i gradienti vengono rappresentati sul lato sinistro dell’immagine.

Si utilizza una finestra gaussiana, con deviazione standard pari alla met`a della larghezza della finestra del descrittore, per pesare l’ampiezza di ciascun punto. Inoltre, ha lo scopo di evitare cambiamenti improvvisi nel descrittore per piccoli spostamenti della posizione della finestra e per dare meno enfasi ai gradienti che sono pi`u lontani dal centro del descrittore.

Sul lato destro della figura viene rappresentato un descrittore di punti chiave. Le orientazioni dei singoli campioni dell’intorno del keypoint vengono raggruppate in subregioni 2x2 e per ciascuna regione viene calcolato un istogramma di 8 bin, dove ciascun bin corrisponde a una diversa direzione.

Il descrittore `e formato da un vettore contenente i valori di tutte le entrate di orientazione dell’istogramma. Generalmente, la tecnica utilizzata si avvale di ar-ray 4x4 di istogrammi a 8 bin di orientazioni in ciascuno. Pertanto il vettore che descrive ciascun punto chiave consta di 4x4x8 = 128 elementi. In fase di test si dimostra che i risultati migliorano al crescere del numero di orientazioni possibili e della ‘grandezza’ degli istogrammi. Scegliendo un numero maggiore per tali pa-rametri, si pu`o ottenere una migliore corrispondenza ma il descritore si rende pi`u sensibile alla distorsione.

2.3

Applicazioni

L’affidabilit`a delle caratteristiche che vengono estratte da questo algoritmo ne giustificano il largo impiego in molte applicazioni come il riconoscimento di oggetti, la ricostruzione tridimensionale della scena e anche in ambito medico nello studio delle risonaze magnetiche [11].

(29)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 20

2.3.1

Riconoscimento di oggetti

Per ogni oggetto presente in un’immagine ci sono molte features caratteristiche, le quali possono essere estratte in modo da fornire una descrizione univoca del-l’oggetto stesso. Questa descrizione estratta da una immagine campione pu`o poi essere utilizzata per identificare l’oggetto in una immagine di test contenente pi`u campioni. `E importante che l’insieme di caratteristiche estratte dall’immagine campione sia insensibile a variazioni di scala delle immagini, disturbi, illuminazio-ne e distorsioni geometriche, in modo da rendere affidabile il riconoscimento.

Figura 2.8: Esempio di riconoscimento

Considerando la capacit`a dell’algoritmo di individuare punti chiave caratteristici invarianti in scala, rotazione e robusti alle trasformazioni affini, `e possibile utiliz-zarlo per il riconoscimento di oggetti. I punti chiave degli oggetti sono estratti da una serie di immagini di riferimento e memorizzati in un database. Un oggetto `e riconosciuto in una nuova immagine confrontando singolarmente ciascun elemento della nuova immagine con elementi del database trovando quello pi`u simile secon-do la distanza euclidea delle loro caratteristiche vettoriali. La probabilit`a che un appaiamento sia corretto pu`o essere determinata tramite il rapporto delle distanze con i due vicini pi`u prossimi.

(30)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 21

2.3.2

Localizzazione e mappatura

Con SLAM, Simultaneous Localization and Mapping, si intende il processo per cui un robot, muovendosi in un ambiente sconosciuto, sia in grado di costruire una mappa di tale ambiente e sia capace di localizzarsi all’interno di tale mappa. In questa applicazione, un sistema stereo trinoculare viene utilizzato per deter-minare stime tridimensionali delle posizioni dei punti di interesse. Tali keypoints vengono utilizzati solo quando sono presenti in tutte e tre le immagini con le disparit`a compatibili. A seconda di come si muove, il robot si localizza autono-mamente utilizzando le caratteristiche corrispondenti alla mappa tridimensionale esistente, e aggiunge, in modo incrementale, ulteriori lineamenti utilizzando un filtro di Kalman. Questo fornisce una soluzione robusta e precisa al problema della localizzazione di un robot in ambienti sconosciuti.

2.3.3

Stitching

Lo stitching di immagini `e un metodo col quale si combinano molteplici immagini fotografiche per produrre un panorama o un’immagine ad alta risoluzione. Tale processo si suddivide in tre fasi principali: acquisizione dell’immagine, calibrazio-ne e montaggio.

Figura 2.9: Esempio di stitching

(31)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 22 confrontati vicendevolmente in modo da individuare punti corrispondenti e, allo stesso tempo, vicini tra loro. Queste corrispondenze vengono utilizzate, succes-sivamente, per trovare immagini candidate per ogni input. Nella prima fase si coinvolgono diverse funzioni che vanno a ricercare gli allineamenti fra le immagini coi quali ridurre le differenze di sovrapposizione fra i pixel. La calibrazione del-l’immagine aiuta a ridurre le differenze di distorsione ed esposizione causati dalla lente dell’obiettivo impiegato nella fotocamera. Il montaggio delle immagini, in-fine, implica l’esecuzione degli aggiustamenti effettuati nella fase di calibrazione, combinata con la rimappatura delle immagini al fine di ottenerne una di uscita.

2.3.4

Modellizzazione, riconoscimento e monitoraggio di

scene 3D

Questa applicazione usa le caratteristiche del riconoscimento di oggetti e model-lazione tridimensionale nel contesto di argumented reality, nella quale soggetti virtuali si sovrappongono con precisione nelle immagini reali. Allo stesso modo, durante la proiezione di un video avviene l’estrazione sul frame di caratteristiche che vengono successivamente confrontate con dati presenti in database cercando delle corrispondenze tra frame e immagini.

2.3.5

Analisi di risonanze magnetiche

Un particolare utilizzo in ambito medico, Feature Based Morphometry, sfutta i punti estremi ricavati dalla Difference of Gaussian nello scale space per classifi-care le risonanze magnetiche tridimensionali del cervello umano. FBM mira ad identificare modelli anatomici distintivi che possono essere presenti in sottogruppi di soggetti a causa di malattie o di variabilit`a genetica. Questa tecnica, infatti, modella l’immagine come un collage di caratteristiche generiche e localizzate che non sono necessariamente presenti in ogni soggetto.

(32)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 23

2.4

Esperienze

Di seguito si riportano le immagini che descrivono, passo dopo passo, l’applicazio-ne dell’algoritmo SIFT sviluppato. In particolare, si osserva la diminuziol’applicazio-ne dei punti di interesse rappresentati con i diversi filtraggi effettuati.

Riassumendo, seguendo l’ordine delle figure, i passi che vengono affrontati sono: • rappresentazione di tutti i punti estremi trovati dal confronto di ogni

pi-xel con i rispettivi 26 vicini e calcolo, tramite lo sviluppo di Taylor, degli scostamenti di tale punti con conseguente rappresentazione;

• rappresentazione dei punti estremi tenendo conto degli scostamenti di ogni pixel e primo filtraggio considerando una soglia sul contrasto;

• rappresentazione dei punti estremi filtrati dei pixel con picchi poco definiti ed eliminazione dei punti sui bordi e rispettiva orientazione.

Da tali immagini si osserva una sostenuta eliminazione dei punti estremi meno importanti che non hanno informazioni utili per gli step successivi. Oltretutto si pu`o notare come i keypoints finali si dispongono lungo l’oggetto presente nella scena indicando, appunto, la presenza di un eventuale ostacolo nell’immagine.

(33)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 24

(34)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 25

(35)

CAPITOLO 2. SIFT: SCALE INVARIANT FEATURE TRANSFORM 26

(36)

Capitolo 3

Visione stereoscopica

3.1

Geometria sistema stereo

La rappresentazione di un punto nello spazio nel piano immagine di una telecame-ra implica la perdita dell’informazione relativa alla distanza [12] [13]. Infatti, in Figura 3.1, si pu`o osservare che due punti distinti nello spazio, P e Q, intersecati da uno stesso raggio passante per il centro ottico Ol, corrispondono ad uno stesso

punto nel piano immagine.

Figura 3.1: Proiezione di punti distinti nello spazio nel piano immagine

(37)

CAPITOLO 3. VISIONE STEREOSCOPICA 28 Un metodo per poter risalire a quale punto dello spazio corrisponda la proiezione di un punto sul piano immagine di una telecamera consiste nell’utilizzo di due o pi`u telecamere. Nel caso di un sistema composto da due telecamere, analogamente al sistema visivo umano, si ottengono due immagini diverse rappresentati la me-desima scena. Come rappresentato in Figura 3.2, tra tutti i punti nello spazio che giacciono sul segmento congiungente il centro ottico Ol e il punto q, proiezione di

Q sul piano immagine πl, al pi`u un solo punto, punto omologo, viene proiettato,

q0, anche sul piano immagine πr. La determinazione dei punti omologhi consente

di mettere in relazione le proiezioni dello stesso punto sui due piani immagine e di risalire, mediante una procedura denominata triangolazione, alle coordinate dei punti dello spazio rispetto ad un sistema di riferimento opportuno.

Figura 3.2: Principio di un sistema stereoscopico

Sia dato un punto q su un piano immagine πl, proiezione del punto Q

apparte-nente allo spazio tridimensionale. Per ottenere, attraverso la triangolazione, le coordinate del punto nello spazio `e necessario determinare il punto omologo q0 nel piano immagine πr. Tale problema, dato q in πl richiederebbe una ricerca

bidimensionale del punto omologo q0 all’interno del piano πr.

In realt`a, sfruttando una particolare caratteristica della geometria del sistema stereoscopico, `e possibile effettuare la ricerca del punto omologo in uno spazio

(38)

CAPITOLO 3. VISIONE STEREOSCOPICA 29 monodimensionale. Infatti, come mostrato in Figura 3.3, gli omologhi di tutti i punti dello spazio che sono proiezione nello stesso punto q del piano immagine πl

giacciono sulla retta generata dall’intersezione tra il piano immagine πr e il piano

epipolare contenente la retta OlQP e i due centri ottici Ol e Or. Tutti i punti

della retta OlQP avranno pertanto i punti omologhi collocati sulla retta rER, retta

epipolare, del piano immagine πr.

Figura 3.3: Vincolo epipolare

Tale vincolo, denominato vincolo epipolare, consente di limitare lo spazio di ricer-ca dei punti omologhi ad un segmento di retta semplifiricer-cando considerevolmente il problema sia da un punto di vista della complessit`a algoritmica sia per quanto concerne la correttezza della soluzione. Il problema pu`o non avere soluzione: in-fatti a causa della diversa posizione delle telecamere che compongono un sistema di visione stereoscopico nello spazio `e possibile che un punto non risulti proiettato su tutti i piani immagine delle telecamere. In tal caso, non `e possibile determinare la distanza del punto esaminato dalle telecamere.

Un sistema di visione stereoscopico `e completamente caratterizzato mediante i parametri intrinseci ed estrinseci. I primi consentono di definire la trasformazione che mappa un punto dello spazio 3D nelle coordinate del piano immagine di ogni telecamera. I parametri estrinseci rappresentano le posizioni e le orientazioni di

(39)

CAPITOLO 3. VISIONE STEREOSCOPICA 30 ogni telecamera rispetto ad una sistema di riferimento noto.

La determinazione dei parametri intrinseci ed estrinseci, ottenuta mediante la procedura di calibrazione, consente quindi di descrivere completamente il sistema stereoscopico ed in particolare di ottenere informazioni relative alle coordinate dei punti nello spazio mediante la triangolazione di punti omologhi.

La conoscenza di tali parametri consente anche di trasformare le immagini ac-quisite dal sistema stereoscopico al fine di produrre un sistema virtuale nel quale i piani immagine delle telecamere giacciono sullo stesso piano e nel quale la ri-cerca dei punti omologhi avviene esaminando le medesime righe nei diversi piani immagine, come rappresentato in Figura 3.4.

Figura 3.4: Immagini in forma standard

3.2

Calibrazione

In un ambiente ideale le telecamere di una testa stereo rispondono al modello pinhole [14], hanno esattamente la stessa lunghezza focale e assi ottici paralle-li. Purtroppo nella realt`a le lenti introducono delle distorsioni, possono avere lunghezze focali diverse e assi ottici disallineati. L’obiettivo della calibrazione `e determinare due insiemi di parametri, intrinseci ed estrinseci, che compensino l’imperfezione della testa stereo. I parametri intrinseci correggono la distorsione

(40)

CAPITOLO 3. VISIONE STEREOSCOPICA 31 delle lenti e la differenza di lunghezza focale, mentre quelli estrinseci determinano l’offset spaziale delle due telecamere, compresa la distanza tra esse e la deviazione dal parallelismo degli assi ottici. Attraverso questi parametri `e possibile trasfor-mare le immagini acquisite in immagini ‘ideali’, come sarebbero quelle viste da telecamere pinhole con assi ottici paralleli.

Figura 3.5: Set di immagini per la calibrazione

Esistono in letteratura diverse tecniche per effettuare la calibrazione di un siste-ma stereoscopico. Tipicamente per`o questa operazione viene eseguita con tecni-che basate sull’utilizzo di pattern geometrici dei quali sono note con precisione le caratteristiche, come dimensione e posizione delle features presenti. Mediante l’acquisizione di tali pattern, generalmente contenenti features simili a scacchiere,

(41)

CAPITOLO 3. VISIONE STEREOSCOPICA 32 in diverse posizioni e utilizzando determinati algoritmi, `e possibile stimare i pa-rametri che caratterizzano tale sistema stereoscopico. In questo studio, il pattern utilizzato `e una scacchiera costituita da una griglia di 9x7 caselle quadrate con lato 110mm. Sono stati generati due set di immagini, relativi alle camere destra e sinistra, considerando diversi posizionamenti della scacchiera rispetto al sistema stereoscopico, come rappresentato in Figura 3.5.

Per ogni immagine di ognuno dei due set, si `e considerato sempre uno stesso ori-gine del sistema di riferimento scena, coincidente con uno specifico corner della scacchiera, rappresentato in Figura 3.6.

Figura 3.6: Sistema di riferimento scena

Orientando gli assi x e y del sistema di riferimento secondo la direzione delle righe e delle colonne della scacchiera e nota la dimensione dei quadrati, `e possibile ri-cavare le coordinate di tutti i corner della scacchiera e quindi i parametri intriseci

(42)

CAPITOLO 3. VISIONE STEREOSCOPICA 33 di ciascuna delle telecamere e i parametri estrinseci del sistema stereoscopico.

3.3

Risultati calibrazione

In particolare, per questo studio, il processo di calibrazione ha fornito i seguenti parametri intrinseci.

Caratteristiche Valore

Lunghezza focale [pixel] [762.43; 763.51] ± [4.01; 3.90] Punto principale [pixel] [217.43; 390.74] ± [7.82; 6.73]

Skew [degree] [0] ± [0]

Distorsione [−0.48; 0.35; 0; 0; 0] ± [0.04; 0.25; 0; 0; 0] Tabella 3.1: Parametri intrinseci left camera

Caratteristiche Valore

Lunghezza focale [pixel] [764.41; 764.83] ± [3.95; 3.86] Punto principale [pixel] [250.81; 381.71] ± [7.74; 6.55]

Skew [degree] [0] ± [0]

Distorsione [−0.50; 0.39; 0; 0; 0] ± [0.04; 0.26; 0; 0; 0] Tabella 3.2: Parametri intrinseci right camera

Per quanto riguarda il sistema stereoscopico, la conoscenza dei parametri estrinseci permette di stimare il posizionamento e l’orientamento relativo delle due telecame-re. Si osserva infatti che, in output, viene fornito il vettore rotazione contenente i tre angoli di Eulero tra i due sistemi di riferimento delle camere e il vettore traslazione che fornisce la posizione dei due centri ottici.

La conoscenza di queste grandezze `e necessaria a garantire un corretto allinea-mento delle immagini fornite dalle due telecamere.

(43)

CAPITOLO 3. VISIONE STEREOSCOPICA 34

Caratteristiche Valore

Vettore rotazione [0.00567; 0.03028; 0.01167] ± [0.01179; 0.01294; 0.00114] Vettore traslazione [−1.08177; −0.00005; −0.01815] ± [0.00412; 0.00205; 0.02501]

Tabella 3.3: Parametri estrinseci right wrt left camera

(44)

Capitolo 4

Matching e triangolazione

4.1

Matching di features

Nel caso della visione stereo le features SIFT vengono estratte allo stesso istante dalle immagini di una coppia di frame, sinistro e destro, e caratterizzate mediante appositi descrittori [15]. Ogni feature `e rappresentata dalla posizione del keypoint e dal suo vettore descrittore.

L’operazione di matching si esegue paragonando ciascuna feature estratta dal-l’immagine sinistra con ogni feature deldal-l’immagine destra in termini di distanza euclidea dei vettori descrittori [9]. Si utilizza un algoritmo che rintraccia il vettore descrittore di feature pi`u vicina, nearest neighbor algorithm, ovvero rintraccia la feature pi`u simile, che diventa la candidata al matching, tra tutte quelle che pi`u le ‘assomigliano’ tra le feature dell’altra immagine.

L’imposizione di una soglia globale sulla distanza non si rivela una scelta ottimale in quanto esistono descrittori pi`u discriminanti di altri. Un metodo pi`u robusto si ottiene controllando il rapporto tra la distanza del descrittore pi`u prossimo ed il secondo pi`u prossimo. Questa scelta risulta migliore della precedente poich`e, per ottenere un matching affidabile, le corrispondenze corrette necessitano di avere descrittori dell’immagine destra significativamente vicini a descrittori dell’imma-gine sinistra.

Si definisce R = d1/d2 il rapporto delle distanze euclidee dei due vettori di

(45)

CAPITOLO 4. MATCHING E TRIANGOLAZIONE 36 tori, Figura 4.1. In particolare d1 `e la distanza euclidea tra il descrittore

dell’im-magine di sinistra e il suo corrispettivo che ha distanza minima nell ’imdell’im-magine di destra, mentre d2 `e la distanza euclidea tra lo stesso descrittore dell’immagine di

sinistra e il suo secondo corrispettivo pi`u vicino nell’immagine destra. Il motivo per cui si utilizza tale rapporto `e dato dalla maggiore robustezza a falsi match. Infatti, si pu`o considerare il valore della distanza dal secondo descrittore come una stima della probabilit`a di ottenere un match errato. Nel caso in cui i primi due valori siano tra loro molto vicini, R ≈ 1, l’attendibilit`a del match `e molto inferiore rispetto al caso in cui tale rapporto si avvicina a zero.

Figura 4.1: Rappresentazione distanza euclidea features

In particolare, in questo lavoro, nel caso di matching corretto R assumer`a valori non elevati. Se sar`a inferiore a 0.8 il matching `e corretto, altrimenti il punto con descrittore considerato non deve essere preso in considerazione.

Tale idea `e confermata dall’andamento delle funzioni di densit`a di probabilit`a dei rapporti tra le prime due distanze, per il caso di match corretti ed errati rappre-sentata in Figura 4.2. La soglia imposta garantisce difatti una buona separazione tra le due curve probabilistiche. Diversamente, con l’aumento di R `e possibile notare come vi sia un conseguente aumento della probabilit`a di rilevare un match errato.

(46)

CAPITOLO 4. MATCHING E TRIANGOLAZIONE 37

Figura 4.2: Densit`a di probabilit`a di match corretti ed errati

4.2

Mappa di disparit`

a

Nei capitoli precedenti `e stato descritto il funzionamento della visione stereosco-pica sottolineando l’aspetto della presenza di immagini con punti di vista diversi. Sfruttando questa caratteristica `e possibile ricavare la profondit`a della scena raf-figurata.

Figura 4.3: Definizione di disparit`a

(47)

CAPITOLO 4. MATCHING E TRIANGOLAZIONE 38 rispettivamente L, left, e R, right. Si prende in esame lo spazio dei punti del piano contenente gli assi ottici a e b delle telecamere. Si considera che siano d’interesse nella scena i due punti P e Q, giacenti nel piano, come indicato in Figura 4.3. La retta identificata dai punti P e L interseca il piano immagine sinistro nel punto P L. Cos`ı anche la retta identificata dai punti Q e L, interseca il piano immagine sinistro nel punto QL. Analogamente definiamo i punti P R e QR nel piano im-magine destro.

Con semplici considerazioni geometriche si pu`o dimostrare che il punto P ha come corrispondente destro il punto P R ottenuto come P L spostato di una quantit`a DP a sinistra. Analogo ragionamento pu`o essere fatto per il punto Q. La quantit`a DP `e funzione della distanza che ha il punto P dal piano immagine ed `e denomi-nata disparit`a del punto P .

Facendo corrispondere ogni pixel dell’immagine di sinistra con uno dell’immagine di destra si pu`o costruire l’immagine di disparit`a, contenente le informazioni di profondit`a [16]. A causa della diversa area di copertura della scena offerta dalle due telecamere, l’immagine di disparit`a conterr`a informazioni solo per l’area in cui sono presenti dati provenienti da entrambe le telecamere, come rappresenta la Figura 4.4.

(48)

CAPITOLO 4. MATCHING E TRIANGOLAZIONE 39

4.3

Triangolazione tridimensionale

Al fine di capire il problema della triangolazione `e utile partire dal caso basilare, considerando due telecamere parallele e allineate, in modo da riportarci al caso bidimensionale rappresentato in Figura 4.5.

Figura 4.5: Triangolazione stereoscopica

Si osserva che i tringoli pP p0 e OLP OR sono triangoli simili. In particolare,

tra-mite considerazioni geometriche, `e possibile imporre l’uguaglianza tra il rapporto base/altezza dei due triangoli [16].

B Z =

B + xR− xL

Z − f Indicando con d = xL− xR la disparit`a:

B Z =

B − d Z − f

(49)

CAPITOLO 4. MATCHING E TRIANGOLAZIONE 40 quindi `e possibile risolvere l’equazione rispetto a Z:

(Z − f )B = Z(B − d) ⇒ Z = Bf d dove:

• B: distanza tra i centri ottici, baseline; • f : distanza focale.

Da tale relazione `e possibile effettuare le seguenti considerazioni:

• fissato il valore della lunghezza focale e la baseline, la profondit`a dipende esclusivamente dalla disparit`a;

• la profondit`a `e inversamente proporzionale alla disparit`a;

• piccoli errori nella stima della disparit`a si tramutano in grandi errori nel calcolo della profondit`a.

In conclusione, gli aspetti principali che garantiscono una buona stima della di-stanza, tra telecamere e oggetto rappresentato nella scena, si basa su una precisa valutazione della disparit`a ed una corretta calibrazione del sistema stereoscopico.

(50)

Capitolo 5

Risultati

Come descritto nei capitoli precedenti, l’algoritmo SIFT, con il quale vengono pro-cessate le immagini provenienti da un sistema di visione stereoscopico, permette di estrarre delle caratteristiche invarianti da entrambe le scene. Queste caratteri-stiche sono necessarie per ricavare la profondit`a di una scena tramite l’utilizzo di algoritmi di matching e tecniche di triangolazione.

In particolare, in questo capitolo, si riportano i risultati di due diverse scene ponen-do particolare attenzione ai keypoints dati dal processo ed il successivo matching. In Figura 5.1 si rappresenta il risultato del primo passo dell’algoritmo su una sin-gola immagine, specificatamente il filtraggio dell’immagine originale con funzione gaussiana di variaza crescente.

Figura 5.1: Immagine filtrata

I punti estremi, ricavati dal confronto di ogni singolo pixel con gli altri 26 vicini, sono rappresentati nella immagine (a.) di Figura 5.2. Nell’immagine (b.), invece, si riporta il risultato dei vari filtraggi dei punti estremi, osservando una

(51)

CAPITOLO 5. RISULTATI 42 guente diminuzione dei punti che rappresentano la scena.

Figura 5.2: (a.): punti estremi, (b.): punti filtrati, (c.): punti con orientazione Il risultato finale dell’algoritmo `e ricavare una mappa di punti estremi rappresen-tativi della scena con la propria orientazione, Figura 5.2 (c.).

In Figura 5.3, si rappresentano le immagini, sinistra e destra, provenienti dal si-stema di visione stereoscopico e processate con l’algoritmo.

Si osserva la presenza di 175 keypoints nell’immagine di sinistra, mentre, nell’im-magine di destra, si hanno 177 keypoints.

(52)

CAPITOLO 5. RISULTATI 43

Figura 5.3: Coppia di immagini stereo processate

Successivamente, in Figura 5.4 si effettua il matching tra le due immagini ste-reoscopiche rilevando la presenza di 22 match con il valore di soglia imposta a R = 0.4.

Figura 5.4: Matching di coppia di immagini stereo, R = 0.4

Si ha una buona corrispondenza tra keypoints destri e sinistri tranne un numero molto limitato di match errati.

(53)

Figu-CAPITOLO 5. RISULTATI 44 ra 5.5, osservando un cambiamento del numero di match e anche l’aumento e la diminuzione dei match errati. Aumentando il valore della soglia R si ottengono 46 match ma si abbassa notevolmente la qualit`a delle corrispondenze, Figura 5.5 (a.). Abbassando il valore della soglia, invece, si osserva la presenza di soli 6 match che si dispogono sul soggetto principale della scena e si abbassa la probabilit`a si trovare match errati, Figura 5.5 (b.).

(54)

CAPITOLO 5. RISULTATI 45 In Figura 5.6, si riporta un ulteriore esempio di applicazione dell’algoritmo, rap-presentando i principali step dell’algoritmo.

Figura 5.6: Filtraggio immagine con funzione gaussiana In Figura 5.7, si rappresentano i punti estremi e i punti filtrati.

Figura 5.7: (a.): punti estremi, (b.): punti filtrati

In Figura 5.8, si rappresentano i punti notevoli di interesse con le proprie orien-tazioni.

(55)

CAPITOLO 5. RISULTATI 46

Figura 5.8: Punti notevoli di interesse

In Figura 5.9, si rappresentano le immagini, sinistra e destra, provenienti dal si-stema di visione stereoscopico e processate con l’algoritmo.

Figura 5.9: Immagini stereo processate

(56)

CAPITOLO 5. RISULTATI 47 l’immagine di destra, sono stati ricavati 258 keypoints. Per quanto riguarda il matching, Figura 5.10, con una soglia R = 0.3, sono stati ricavati 26 match con qualche corrispondenza errata. Come nel caso precedente, variando il valore di R varier`a il numero di corrispondenze. In particolare, aumentando R aumenta la probabilit`a di trovare match errati.

Figura 5.10: Matching coppia immagini stereo

Anche per questo esempio si pu`o osservare che i keypoints pi`u rilevanti si dispon-gono sul soggetto principale della scena.

Lo step successivo `e quello di applicare le tecniche di triangolazione per ricava-re la distanza dell’oggetto pricava-resente nell’immagine, ottendendo, cos`ı, le cordinate tridimensionali [x, y, z] necessarie per gli algoritmi di Avoid per le manovre di evasione.

(57)

Capitolo 6

Conclusioni e sviluppi futuri

Il presente lavoro di tesi `e parte di un ampio progetto che ha come obiettivo lo sviluppo di un completo sistema Sense and Avoid da implementare su velivoli unmanned. In particolare, l’architettura preliminare di questo sistema prevede l’utilizzo di un sistema di visione stereoscopico come sensore per il rilevamento di ostacoli. Nel presente lavoro `e stato utilizzato il sistema di telecamere stereosco-piche Camaleon della ditta OptoMotive come componente sensoristica di visione. Nei vari test effettuati si `e riscontrato un corretto funzionamento dell’algoritmo SIFT sviluppato nell’identificazione dei punti chiave. Nonostante l’esecuzione di pesanti filtraggi nell’algoritmo, i punti notevoli finali identificano, con ottima ap-prossimazione, la presenza dei soggetti nella scena. Si `e osservato, anche, che l’algortimo di matching sviluppato riesce a ricavare ottime corrispondenze su im-magini stereoscopiche rettificate e con una buona risoluzione. Invece, considerando immagini stereoscopiche non rettificate non si riesce a trovare un numero soddi-sfacente di match corretti.

Complessivamente, una valutazione preliminare dei test effettuati su diverse cop-pie di immagini stereoscopiche, in termini di punti notevoli e corrispondenze tro-vate, riportate nel lavoro di tesi, ha fornito dei buoni risultati.

L’obiettivo del prossimo futuro sar`a modificare il codice sorgente affinch`e ci possa essere l’input direttamente con i dispositivi di acquisizione delle immagini e va-lutare le diverse soglie dei filtri presenti per ottenere una maggiore affidabilit`a e

(58)

CAPITOLO 6. CONCLUSIONI E SVILUPPI FUTURI 49 robustezza nel matching.

Di seguito, l’obiettivo sar`a quello di realizzare un sistema real time che permetta, tramite l’utilizzo del controller integrato NI CompactRIO 9038 e la programma-zione in LabVIEW, di processare contemporaneamente le immagini del sistema stereoscopico effettuando, istante per istante, la determinazione degli oggetti pre-senti nel campo visivo, in modo da avere la possibilit`a di seguire il percorso di un eventuale ostacolo presente davanti al velivolo ricavando, quindi, traiettoria e ve-locit`a. In pi`u, bisognar`a considerare le variazioni di illuminazione che si potranno avere anche durante la stessa fase di volo e valutare questo studio con la presenza di diversi scenari di volo.

Successivamente, sar`a importante considerare le variazioni di assetto del velivolo durante il volo e quali problematiche comportano nel cambiamento dello scenario visto dalle telecamere e nel cambiamento della loro posizione.

In ultimo, sar`a necessario implementare gli algoritmi della funzione Avoid, i quali riceveranno le informazioni estrapolate dalla fase Sense in termini di posizione dell’ostacolo, che dovranno intervenire con cambiamenti di traiettoria dell’UAV per evitare il conflitto.

(59)

Appendice A

Piattaforme UAV

La classificazione delle diverse piattaforme avviene prendendo in considerazione caratteristiche come la dimensione, le prestazioni e l’autonomia. La nomenclatura che generamente viene adoperata in ambito civile `e la seguente:

• MAV/NAV Micro/Nano Air Vehicles: nome dovuto alle loro dimensioni. Questi velivoli tendono a operare a quote molto basse, minore di 330m, con autonomia che va da cinque a massimo trenta minuti.

• VTOL, Vertical Take-Off and Landing: sono in grado di effettuare decollo e atterraggio verticale e quindi, generalmente, sono selezionati nelle missioni-che presentano terreni impervi. Velivoli di questo tipo possono operare ad altitudini che dipendono dalle diverse missione.

• LASE, Low Altitude Short Endurance: sistemi capaci di ovviare la necessit`a di piste. Il peso si aggira intorno a due chili e mezzo con una apertura alare inferiore a tre metri. Compromessi tra peso e prestazioni tendono a ridurre l’autonomia e la comunicazione con le stazioni di terra.

• LASE Close: questa categoria, invece, necessita di piste di decollo e atterrag-gio. Le dimensioni maggiori conferiscono prestazioni e autonomia maggiori. Altitudine massima `e circa 1500 metri.

(60)

APPENDICE A. PIATTAFORME UAV 51 • LALE, Low Altitude Long Endurance: sono UAV che possono trasportare carichi di diversi chilogrammi ad altitudini di alcune migliaia di metri per lunghi periodi.

• MALE, Medium Altitude Long Endurance: velivoli leggermente pi`u grandi dei precedenti che possono raggiungere altitudini di circa 9000 metri della durata di diverse ore.

• HALE, High Altitude Long Endurance: sono i velivoli pi`u grandi e complessi di tutti gli UAVs, raggiungono dimensioni paragonabili ai generici velivoli con equipaggio a bordo. Possono raggiungere i 20000 metri di altitudine con una autonomia di circa 30 ore, stabilendo cos`ı record di quota e durata del volo.

Riassumendo, `e possibile collocare ogni diversa classe di UAV in una figura con-siderando le varie caratteristiche di ognuno, come rappresentato in Figura A.1.

(61)

Appendice B

Caratteristiche sistema stereo

Il sistema di visione stereo scelto per questa fase di sviluppo del progetto corri-sponde al sistema di telecamere stereo Cameleon della ditta OptoMotive, costituito da due telecamere denominate base camera e head camera, e collegate tra loro con una cavo di collegamento di tipo ribbon.

Figura B.1: Architettura del sistema OptoMotive Cameleon

(62)

APPENDICE B. CARATTERISTICHE SISTEMA STEREO 53 In Figura B.1 si illustra la configurazione del sistema OptoMotive Cameleon che `e alimentato da una porta USB con tre convertitori DC-DC.

Il sistema OptoMotive Camaleon `e costituito principalmente da tre componenti: • camera base;

• camera head ; • modulo FPGA.

Entrambe le telecamere utilizzano il sensore monocromatico Aptina MT9V034, capace di fornire 64 frame al secondo alla risoluzione massima di 752x480 pixel. In Tabella B.1 sono riportate le principali caratteristiche delle due telecamere.

Caratteristiche Valore

Tipo di sensore global shutter CMOS

Colore monocromatico Formato ottico 1/3’ Risoluzione 752x480 Dimensione pixel 6.0x6.0µm Pixel clock 27M Hz Frame rate 64F P S

Risoluzione convertitore ADC 10bit

Dimensioni (con lenti montate) Base: 47x54x30mm, Head: 30x35x18mm Peso (con lenti montate) Base: 37g, Head: 7g

Tabella B.1: Specifiche tecniche

Come rappresentato in Figura B.2, il sistema di visione stereo Cameleon, utilizzato per le prove in laboratorio, `e stato realizzato posizionando le due telecamere su di un supporto, composto da:

• un treppiedi;

• una staffa formata da tre elementi e fissata al treppiedi, in grado di consentire la regolazione della distanza tra le due telecamere;

(63)

APPENDICE B. CARATTERISTICHE SISTEMA STEREO 54 • due teste a tre movimenti con meccanismo a cremagliera per la regolazione

spaziale di precisione delle due telecamere;

• due supporti di metallo per il fissaggio delle telecamere sulle teste.

(64)

Appendice C

Filtro Gaussiano

Un filtro gaussiano `e un filtro la cui risposta impulsiva `e una funzione gaussiana. Tali filtri si dimostrano molto efficaci per attenuare il rumore di tipo Gaussiano presente nell’immagine.

La funzione di trasferimento h(l, k), modellata dalla funzione Gaussiana discreta con media nulla, `e data da:

h(l, k) = ce−(l2+k2)2σ2

dove σ `e la deviazione standard della distribuzione di probabilit`a associata, c il fattore di normalizzazione che per semplicit`a si assume uguale a 1. La deviazione standard `e l’unico parametro che modella la funzione di trasferimento e definisce l’area di influenza del filtro Gaussiano, come rappresentato in Figura C.1.

Figura C.1: Funzione Gaussiana (a) 1D e−l2/2σ2

, (b) 2D con σ = 3 e (c) trasformata di Fourier di h(l, k)

(65)

APPENDICE C. FILTRO GAUSSIANO 56 Il peso dei coefficienti della maschera `e inversamente proporzionale alla distanza dei pixel rispetto a quello centrale, ne consegue che i pixel a distanza maggiore di circa 3σ non avranno nessuna influenza per il filtraggio.

Tra le propriet`a del filtro Gaussiano si ha: • simmetria circolare;

• monotonia decrescente nel dominio spaziale e delle frequenze; • separabilit`a.

La trasformata di Fourier della funzione Gaussiana `e ancora una Gaussiana con soli valori reali.

H(u) = F (h(x)) =

Z +∞

−∞ h(x)e −jux

dx =√2πσe−2v2u2

Da ci`o si pu`o osservare che:

• il filtro Gaussiano produce uno smoothing lieve se la deviazione standard σ ha valori piccoli che corrispondono a valori grandi nel dominio delle frequenze con il conseguente limitato taglio delle alte frequenze, in quanto ν2 = 1/σ2.

• Al contrario se σ ha valori alti, l’operazione di smoothing `e notevolmente accentuata avendo in corrispondenza un valore piccolo di ν eliminando un numero maggiore di alte frequenze. In quest’ultimo caso, l’eliminazione delle alte frequenze comporta una maggiore attenuazione del rumore e delle strutture presenti nel dominio spaziale.

Con la funzione di trasferimento H(u) ancora Gaussiana nel dominio delle fre-quenze, si conferma di nuovo l’esistenza di un unico picco.

Come anticipato, una delle propriet`a del filtro Gaussiano `e la separabilit`a. Dal punto di vista computazionale `e di fondamentale importanza in quanto `e possibile effettuare due filtraggi monodimensionali, orizzontale e verticale, invece di uno bidimensionale. Il risultato finale `e uguale ma vantaggioso per la minore comples-sit`a di calcolo. Scambiando l’ordine delle convoluzioni i risultati non cambiano, per la propriet`a associativa e commutativa della convoluzione.

(66)

APPENDICE C. FILTRO GAUSSIANO 57 Esempio di filtro Gaussiano composto da una maschera 7x7 con varianza σ2 = 2

normalizzando il valore massimo del picco uguale ad 1 nella posizione centrale `e il seguente: [i, j] −3 −2 −1 0 1 2 3 −3 0.0111 0.0388 0.0821 0.1054 0.0821 0.0388 0.0111 −2 0.0388 0.1353 0.2865 0.3679 0.2865 0.1353 0.0388 −1 0.0821 0.2865 0.6065 0.7788 0.6065 0.2865 0.0821 0 0.1054 0.3679 0.7788 1.0000 0.7788 0.3679 0.1054 1 0.0821 0.2865 0.6065 0.7788 0.6065 0.2865 0.0821 2 0.0388 0.1353 0.2865 0.3679 0.2865 0.1353 0.0388 3 0.0111 0.0388 0.0821 0.1054 0.0821 0.0388 0.0111

(67)

Appendice D

LoG e DoG

Con il termine Laplacian of Gaussian, LoG, si intende un operatore per l’estra-zione dei bordi nell’ambito di analisi delle immagini. In particolare, LoG combina l’effetto del filtro Gaussiano, usato per appiattire i livelli di grigio, con quello del-l’operatore Laplaciano che esalta i bordi.

Nel continuo, se con f (x, y) si indica l’immagine di input e con h(x, y) la funzione gaussiana, l’operatore Laplaciano della Gaussiana g(x, y) `e ottenuto come segue:

g(x, y) = ∇2[h(x, y) ∗ f (x, y)]

che evidenzia l’operazione combinata del Laplaciano applicato al risultato della convoluzione tra l’immagine f e la risposta impulsiva del filtro gaussiano h. Ricordando che il filtro Gaussiano `e dato da:

h(x, y) = e−(x2+y2)2σ2

con σ che controlla il livello di smoothing, ed applicando le regole di derivazione per la convoluzione si ottiene:

g(x, y) = [∇2h(x, y)] ∗ f (x, y)

dove il termine in parentesi `e la risposta impulsiva del Laplaciano della gaussiana, data da: hLoG(x, y) = ∇2h(x, y) = ∇2  e−(x2+y2)2σ2  = x 2+ y2− 2σ2 σ4 e −(x2+y2) 2σ2 58

Riferimenti

Documenti correlati

I risultati dell’applicazione di una stessa trasformazione in RGB e HSI non sono, però, perfettamente identici (perché la conversione tra i due spazi colore può comportare

Per informazioni su come scorrere un elenco e su come selezionare una riga in un elenco si veda il paragrafo Come selezionare un'opzione in un elenco del capitolo Come

Il pulsante Allergie nella barra degli strumenti Paziente è visibile solo nei pazienti con allergie, ovvero nei pazienti in cui sono state impostate una o più allergie nel

di tecnica di pianifi cazione e progettazione urbanistica, nonché un’attenzione signifi cativa al tema della forma della città, nel contesto del bagaglio culturale tipico

Its aim should be the positioning and design of small centers or central meeting points, the design of public space, non built-up space, and transport corridors, as well as the

In tutte le classi, dalla seconda primaria, alla terza secondaria di primo grado, abbiamo svolto il lavoro sui diversi tipi di lettura a seconda del contesto, delle finalità che

Gli studi qui proposti contribuiscono piuttosto a rendere comprensibile l’oggetto più vasto e incommensurabile della ricerca, la storia stessa, attraverso un punto di vista in

La conoscenza dei parametri intrinseci ed estrinseci consente anche di trasformare le immagini acquisite dal sistema stereoscopico al fine di produrre un sistema virtuale nel quale