UNIVERSIT `A DEGLI STUDI DI PARMA FACOLT `A DI INGEGNERIA CORSO DI LAUREA IN INGEGNERIA INFORMATICA

(1)

ALGORITMI OTTIMIZZATI PER LA LOCALIZZAZIONE DI OSTACOLI IN AMBIENTI NON STRUTTURATI

MEDIANTE VISIONE STEREO

Relatore:

Chiar.mo Prof. ALBERTO BROGGI

Correlatori:

Dott. Ing. CLAUDIO CARAFFI Dott. Ing. PAOLO MEDICI

Candidato:

PAOLO ZANI

ANNO ACCADEMICO 2004–05

(2)

(3)

Introduzione 3

Inquadramento del problema . . . 6

Principi guida . . . 7

Letture consigliate . . . 10

1 I principi alla base della visione stereoscopica 12 1.1 La V-disparity image . . . . 18

1.2 La disparity space image . . . . 22

2 Il sistema stereo a bordo del Terramax 24 2.1 Disposizione e parametri principali delle telecamere . . . 24

2.1.1 Meccanismi di sincronizzazione . . . 27

2.1.2 Altri problemi . . . 28

Vibrazioni . . . 28

Sporco . . . 29

3 Costruzione della V-Disparity image 30 3.1 Ottimizzazioni al codice . . . 33

4 Costruzione della disparity space image 41 4.1 Ottimizzazioni al codice . . . 43

ii

(4)

5 Individuazione degli ostacoli 54

5.1 Risultati . . . 56

5.2 Falsi negativi . . . 60

5.3 Falsi positivi . . . 62

5.4 Mappatura nel mondo reale . . . 62

6 Risultati 66 6.1 Analisi dei tempi di elaborazione . . . 66

7 Conclusioni 71 7.1 Valutazione degli algoritmi . . . 71

7.2 Sviluppi futuri . . . 72

7.2.1 V-Disparity image . . . 72

7.2.2 disparity space image . . . 72

7.2.3 Rilevamento degli ostacoli . . . 73

Bibliografia 75

Ringraziamenti 79

(5)

3 Il Terramax . . . 2

4 Esempio di immagini stereo . . . 3

5 Esempio di V-disparity image . . . . 4

6 Esempio di disparity space image . . . 5

7 Sistema di riferimento per il Terramax . . . 5

8 Esempio di ostacoli rilevati . . . 6

9 Operazione di tipo SIMD . . . 9

1.1 Disparit`a di alcuni ostacoli . . . 13

1.2 Modello pinhole box . . . . 14

1.3 Sistema di telecamere stereo . . . 15

1.4 Proiezione di un punto del mondo reale . . . 16

1.5 Piani ad uguale disparit`a . . . 17

1.6 Schema della disposizione di una coppia di telecamere stereo . . . 19

1.7 Superfici ad uguale disparit`a e terreno . . . 19

1.8 Immagini stereo sintetiche . . . 20

1.9 Abbinamento tra righe dell’immagine . . . 21

1.10 V-disparity image . . . . 21

1.11 Disparity space image . . . 22

2.1 Baseline del sistema di acquisizione . . . . 25

2.2 Telecamera e relativo supporto regolabile . . . 26

iv

(6)

2.3 Dettaglio delle viti di regolazione . . . 27

2.4 Il SyncBox . . . . 27

2.5 Il fissaggio del sistema di visione al Terramax . . . . 28

2.6 Dettaglio delle protezioni per le telecamere . . . 29

3.1 Immagini stereo di una strada asfaltata . . . 30

3.2 Immagini di Sobel di una strada asfaltata . . . 31

3.3 Immagini di Sobel ternarizzate di una strada asfaltata . . . 32

3.4 V-disparity image di una strada asfaltata . . . . 32

3.5 Elaborazione svolta dall’istruzionepsadbw . . . 35

3.6 Calcolo della correlazione tra due righe omologhe . . . 36

4.1 Immagini stereo di un centro abitato . . . 41

4.2 Immagini di Sobel di un centro abitato . . . 42

4.3 disparity space image di un centro abitato (106x80 pixel) . . . . 43

4.4 disparity space image di un centro abitato (320x240 pixel) . . . . 44

4.5 Rappresentazioni in memoria di un’immagine . . . 46

4.6 Calcolo della correlazione tra due finestre . . . 47

4.7 Caricamento ottimizzato della finestra sinistra . . . 49

5.1 Rilevazione di ostacoli ai bordi della carreggiata . . . 56

5.2 Rilevazione di ostacoli in presenza di ombre . . . 56

5.3 Rilevazione di una staccionata . . . 57

5.4 Rilevazione di un veicolo sopraggiungente . . . 57

5.5 Rilevazione di una recinzione . . . 58

5.6 Rilevazione di bidoni in lontananza . . . 58

5.7 Rilevazione di bidoni vicini . . . 59

5.8 Rilevazione di un ponte . . . 59

5.9 Rilevazione di cespugli . . . 60

5.10 Oggetto che appare in modo diverso nelle due immagini . . . 61

5.11 Falso positivo . . . 63

5.12 Mappa di una recinzione . . . 64

(7)

5.15 Mappa di un campo . . . 65

(8)

3.1 Sostituzione sui valori del filtro di Sobel ternarizzato . . . 34

3.2 Nomi dei pi`u comuni raggruppamenti di bit . . . . 37

6.1 Tempi di esecuzione sulla prima macchina di test . . . 67

6.2 Tempi di esecuzione sulla seconda macchina di test . . . 68

vii

(9)

3 Algoritmo ottimizzato per il calcolo della VDI (versione 2) . . . 40 4 Algoritmo di base per il calcolo della DSI . . . 45 5 Algoritmo ottimizzato per il calcolo della DSI (Versione 1, Parte 1) . . 50 6 Algoritmo ottimizzato per il calcolo della DSI (Versione 1, Parte 2) . . 51 7 Algoritmo ottimizzato per il calcolo della DSI (Versione 2, Parte 1) . . 52 8 Algoritmo ottimizzato per il calcolo della DSI (Versione 2, Parte 2) . . 53

viii

(10)

L’8 Ottobre 2005 si svolgerà la seconda edizione della Grand Challenge, una gara in cui veicoli autonomi si affronteranno su un percorso di 175 miglia¹nella zona deser- tica che collega Los Angeles a Las Vegas, tra sterrati, corsi d’acqua, sabbia e rocce, ostacoli naturali (come fossati, massi e vegetazione di ogni tipo) e artificiali (pali, reti metalliche, costruzioni in cemento armato e cavalli di frisia). Vincitrice del premio di due milioni di dollari sarà la squadra il cui mezzo avrà completato il percorso stabilito nel minor tempo (e comunque entro il limite massimo di dieci ore), senza aver recato danni all’ambiente circostante.

Anche quest’anno il team Terramax, di cui il Laboratorio di Visione Artificiale del Diparitmento di Ingegneria dell’Informazione dell’Università di Parma² fa parte, assieme ad Oshkosh Truck Corporation e Rockwell Collins Inc., parteciperà alle fasi finali della competizione, dopo averne superato le selezioni, tenute nella primavera del 2005; il veicolo utilizzato, un Oshkosh MTVR³(visibile in figura 1), è stato equipag- giato con un sistema di acquisizione video formato da cinque telecamere MicroPix C-640, e con un laserscanner IBEO ALASCA (figura 2): questa strumentazione, as- sieme al software sviluppato dal VisLab, lo ha reso capace di ricostruire l’ambiente circostante, pianificare una traiettoria che eviti gli ostacoli presenti⁴, e seguirla, grazie al sistema drive-by-wire installato; il risultato finale è il Terramax, ritratto in figura 3.

In questo contesto si `e sviluppato il lavoro presentato in questa tesi.

1281,6 Km

2Da qui in avanti, VisLab

3Medium Tactical Vehichle Replacement

4Il path-planner `e stato realizzato da Rockwell Collins, Inc.

1

(11)

Figura 1: L’Oshkosh MTVR

(a) Telecamera MicroPix C-640 (b) Laserscanner IBEO ALASCA

Figura 2: Sensori a bordo del Terramax

Figura 3: Il Terramax

(12)

In questa tesi si `e trattato il problema della rilevazione di ostacoli in un ambiente non strutturato, attraverso un sistema di telecamere stereo montate su un veicolo, rivolgendo una particolare attenzione al contenimento dei tempi di elaborazione.

Una corretta percezione dello spazio circostante un mezzo richiede diversi tipi di elaborazione sulla coppia di immagini stereo acquisite (delle quali si pu`o osservare un esempio in figura 4) per poter ricavare, dalla grossa mole di informazione che queste contengono, la disposizione degli eventuali ostacoli presenti.

(a) Immagine sinistra (b) Immagine destra

Figura 4: Immagini stereo, acquisite nello stesso istante dalle telecamere di sinistra e di destra

La prima operazione da svolgere consiste nello stimare l’andamento del terreno, attraverso un metodo (detto della V-disparity image), introdotto da Raphael Labayrade e Didier Aubert [24, 20, 21, 23, 22], e ripreso all’interno del VisLab da Rean Isabella Fedriga [10] e Claudio Caraffi [6, 7] (figura 5).

A partire da questa approssimazione iniziale si costruisce una immagine di dispa- 3

(13)

Figura 5: V-disparity image; nel paragrafo 1.1 si vedr`a come sia possibile ricavare da questa l’andamento del terreno

rit`a, o Disparity Space Image (DSI) (visibile in figura 6), che permette di associare ai pixel delle immagini acquisite le coordinate dei punti del mondo reale che li hanno generati, rispetto ad un sistema di riferimento solidale col veicolo, illustrato in figura 7.

L’ultima fase consiste nell’individuare, all’interno della ricostruzione tridimensio- nale appena ottenuta, gli insiemi di punti che si configurano come ostacoli da evitare⁵, e di questi creare una mappa, che sar`a poi integrata con quelle generate dagli altri sensori, e utilizzata per pianificare il moto del mezzo; i risultati ottenibili sono illustrati in figura 8.

5In questa categoria ricadono, ad esempio, pali, cespugli e recinzioni

(14)

Figura 6: Disparity Space Image

Le tonalità più scure (blu e viola) rappresentano punti del mondo lontani, quelle più chiare (arancione, giallo e verde) punti vicini

Figura 7: Sistema di riferimento per il Terramax

(15)

(a) Immagine degli ostacoli (b) Mappa

Figura 8: Esempio di ostacoli rilevati

Nell’immagine di sinistra le macchie rappresentano le zone della DSI classificate come ostacoli (il colore `e stato attribuito utilizzando la stessa codifica impiegata per la DSI), mentre in quella di destra ogni poligono ne rappresenta, secondo una vista dall’alto, la posizione nel mondo

Inquadramento del problema

A poco più di sei mesi dalla gara, e nell’imminenza delle prime eliminatorie, era importante pianificare con attenzione la strada da intraprendere per realizzare una nuova ver- sione, con maggiori prestazioni ed una più grande versatilità, del software esistente⁶, mentre questo era ancora in fase di sviluppo.

La scelta fu di produrre una libreria di oggetti del tutto nuovi, che portassero i

6Si tratta dei moduli per GOLD (Generic Obstacle and Lane Detection, il framework utilizzato nel VisLab per lo sviluppo degli algoritmi) scritti da Claudio Caraffi in occasione della prima edizione della Grand Challenge [7]

(16)

miglioramenti desiderati, pur mantenendo la compatibilità col sistema già presente, di modo che fosse possibile via via integrarli al suo interno, nell’attesa di una più ampia ristrutturazione della funzionalità principale.

Una volta deciso come procedere, restavano comunque da affrontare i problemi tipici dell’elaborazione di immagini stereo, inevitabilmente emersi durante la prima stesura del codice: la notevole quantit`a di dati da trattare, ed i tempi occorrenti per farlo, che nel nostro caso dovevano essere contenuti, viste le esigenze di pianificazione del moto.

La frequenza di aggiornamento minima era stata stabilita in 5Hz, e l’obiettivo po- teva considerarsi raggiunto, a costo, per`o, di utilizzare per la DSI una risoluzione ef- fettiva di soli 106x80 pixel; il primo passo fu, dunque, cercare di portarla a 320x240 pixel, senza aumentare in proporzione i tempi di elaborazione. Visti i risultati ottenuti, si pass`o in seguito ad accelerare anche il calcolo della V-disparity image, anch’esso particolarmente oneroso.

Mentre la linea da seguire per le due attivit`a appena descritte era apparsa fin da subito ben definita, sia per l’esperienza maturata nel corso della prima edizione del- la Grand Challenge, sia per la presenza, in letteratura, di algoritmi consolidati che le affrontano⁷, il processo di obstacle detection⁸restava un argomento dibattuto: si scel- se, dunque, di tentare un approccio differente da quello seguito fino a quel momento, e confrontare le prestazioni dei due diversi sistemi.

Principi guida

Durante tutto il processo di sviluppo del software i requisiti fondamentali sono stati la modularit`a (in modo da rendere semplici integrazione e riuso di quanto veniva via via prodotto), e l’efficienza (visti i vincoli, in termini di prestazioni, cui bisogna- va far fronte): la scelta `e caduta subito sul C++, linguaggio che permette di lavorare ad un alto livello di astrazione nella fase di progettazione delle interfacce, pur mante-

7La loro applicazione, comunque, ha richiesto una particolare attenzione, date le peculiarit`a del caso in esame (le baseline utilizzate sono molto larghe, e si affrontano per lo pi`u ambienti non strutturati)

8Rilevamento di ostacoli

(17)

Quando sono necessarie prestazioni elevate, comunque, la flessibilit`a del linguaggio utilizzato da sola non basta: occorre un’attenta analisi del problema che si sta affrontando, in modo da riuscire a valutarne tutti i diversi aspetti.

La prima cosa da fare, in questi casi, è cercare un algoritmo più efficiente: tentare di migliorare le prestazioni ottenibili, ad esempio, è uno spreco di tempo, quando la complessità della soluzione analitica adottata è comunque esponenziale.

Il secondo livello a cui si può intervenire è quello dell’implementazione: la stesura del codice, infatti, deve tener conto anche delle caratteristiche della macchina su cui questo dovrà girare (processore, memoria, dischi) e del compilatore utilizzato (cer- ti costrutti sintattici, ad esempio, vengono più facilmente riconosciuti e ottimizzati, quindi, se è il caso, è preferibile utilizzarli).

L’ultima possibilità è l’ottimizzazione a basso livello, che mette s`ı a disposizione del programmatore tutte le risorse del sistema, ma che presenta anche notevoli dif- ficoltà, dal momento che spesso il codice prodotto risulta poco leggibile (e quindi scarsamente manutenibile), e la probabilità di introdurre errori è molto alta.

Interventi di questo tipo, dunque, vanno limitati alle parti pi`u critiche del codice, ovvero i punti in cui la CPU spende la maggior parte del tempo⁹: quelli, cio`e, dove ri- sparmiare un ciclo di clock vuol dire evitare che questo sia ripetuto inutilmente milioni o miliardi di volte.

Nel nostro caso, l’algoritmo è ben definito, e la sua complessità deriva, come si ve- drà in seguito, dall’elevato numero di confronti necessari per abbinare i punti omologhi in una coppia di immagini: siamo in una di quelle situazioni in cui anche un’ottima implementazione non può essere di grosso aiuto.

La soluzione a questo problema esiste, ma `e particolare, dal momento che coinvol- ge contemporaneamente almeno due dei tre i livelli di ottimizzazione appena esposti:

si tratta, infatti, di modificare parte dell’algoritmo, per poter utilizzare le capacit`a di

9Tali sezioni sono solitamente dette innermost loop

(18)

calcolo parallelo SIMD (Single Instruction Multiple Data) dei processori moderni, e di implementare queste operazioni direttamente in linguaggio macchina.

Molte attività comuni nel mondo dell’informatica, come la codifica e decodifica audio e video, l’elaborazione di immagini, la compressione dati e la crittografia ri- chiedono di ripetere le medesime operazioni su un numero elevato di elementi: queste ragioni hanno spinto, nel tempo, le case produttrici di microprocessori general purpose ad estendere i set di istruzioni esistenti, in modo che fosse possibile accelerare i pro- cessi appena elencati, eseguendo la stessa operazione su più dati in parallelo (questo principio è illustrato in figura 9).

Figura 9: Operazione di tipo SIMD

L’elaborazione di tipo SIMD consiste nell’applicare l’operatore op in parallelo sugli operandi contenuti nei registri A e B; il tempo di calcolo risulta idealmente ridotto di un fattore n (dove n indica il numero di operandi per registro) rispetto alla versione sequenziale della medesima operazione, anche se, come si vder`a in seguito, le prestazioni ottenibili vengono limitate dalla lentezza degli accessi alla memoria, necessari sia al caricamento dei dati da elaborare che al salvataggio dei risultati.

La difficolt`a maggiore nell’utilizzare questo tipo di istruzioni risiede nel fatto che, al giorno d’oggi, i compilatori sono in grado di parallelizzare solo pattern di codice

(19)

messi a disposizione dai processori Intel a partire dalla famiglia Pentium III per velocizzare le operazioni di calcolo del costo di abbinamento tra i punti delle coppie di immagini acquisite.

Il risultato finale `e un sistema che, per le sue prestazioni, pu`o essere considerato soft real-time, dato che i tempi di elaborazione non possono essere garantiti, ma ri- sultano comunque, in media, abbastanza contenuti da poter permettere una adeguata interazione tra il Terramax e l’ambiente che lo circonda.

Letture consigliate

Qui di seguito vengono presentate alcune letture che possono risultare interessanti per chi voglia approfondire i temi relativi alla visione stereoscopica, all’ottimizzazione del codice o anche solamente alla Grand Challenge:

• Questa tesi

• La tassonomia di Daniel Scharstein [28], che contiene una accurata comparazio- ne di molti sistemi stereo presenti in letteratura

• Gli articoli di Takeo Kanade [17, 16], che propongono un’approfondita analisi degli aspetti teorici ed implementativi legati ad un calcolo efficace ed efficiente dell’immagine di disparit`a

• Il manuale di Agner Fog [11], che si occupa con un notevole grado di dettaglio degli aspetti legati alla stesura di codice ottimizzato per i processori della famiglia Intel^R Pentium^R

• La tesi di laurea di Claudio Caraffi [7], che ha tratta l’originaria implementazione del sistema di visione stereo ripreso in questo lavoro

10Ad esempio, il GCC (GNU Compiler Collection) dalla versione 4 inizia a presentare un’unit`a dedicata all’autovettorizzazione del codice

(20)

• La tesi di laurea di Pier Paolo Porta [27], che presenta gli aspetti legati all’integrazione dei diversi sensori presenti a bordo del veicolo che parteciper`a alla seconda edizione della Grand Challenge

(21)

stereoscopica

Ogni giorno i nostri occhi ci guidano con sicurezza all’interno di un mondo a tre dimensioni molto complesso, e ci riescono perchè uno stesso oggetto è visto, da ciascuno di loro, sotto angoli appena diversi; allo stesso modo, nella visione artificiale stereoscopica, un punto dello spazio appare, nelle due immagini, in posizioni differenti: la distanza tra tali posizioni viene detta disparità.

Nella figura 1.1 si pu`o notare come gli oggetti presentino disparit`a sempre minori via via che questi si trovino ad una maggiore distanza dal punto di osservazione; tale fatto ci induce a concludere in modo intuitivo che:

note le caratteristiche del sistema di acquisizione che si sta utilizzan- do, e la disparit`a con cui un oggetto appare, `e possibile ricavare la sua posizione nel mondo

Per dare una giustificazione rigorosa a questa affermazione `e necessario introdurre un modello geometrico, detto pinhole box¹, che approssimi il fenomeno fisico che porta alla formazione dell’immagine acquisita dalla telecamera; tale modello `e riprodotto in figura 1.2.

1Alla lettera, scatola su cui `e stato praticato un foro con uno spillo

12

(22)

Figura 1.1: Disparit`a di alcuni ostacoli

L’immagine superiore è stata acquisita con la telecamera di sinistra, mentre quella infe- riore con la telecamera di destra; si può notare come la disparità del fanale posteriore sinistro del veicolo parcheggiato sia maggiore di quella del traliccio visibile sullo sfondo (e ciò è del tutto naturale, dal momento che il primo oggetto è più vicino del secondo al punto di osservazione)

(23)

Punto di fuoco Immagine

Piano dell’immagine simmetrica Piano dell’immagine

Figura 1.2: Modello pinhole box

I raggi luminosi provenienti dall’esterno attraversano il piccolo foro sulla scatola, e penetrano al suo interno, andando a formare l’immagine rovesciata sul lato opposto.

Nella realt`a, i raggi luminosi vengono concentrati sul sensore della telecamera dalle lenti ottiche, che determinano anche la distanza tra il punto di fuoco e il piano dell’im- magine, contrassegnata in figura 1.2 con la lettera f, detta lunghezza focale; bisogna, comunque, tenere conto del fatto che tali lenti introducono delle distorsioni: esiste un metodo, proposto da Tsai [32], che permette di costruire una LUT (Look Up Table) con cui effettuare un’operazione, detta rettificazione, grazie a cui `e possibile rimuoverle dalle immagini acquisite².

La piramide centrata sul punto di fuoco, e contenente i punti del mondo che possono essere proiettati sull’immagine, rappresenta il campo visivo, e la sua apertura deter- mina l’angolo di vista della telecamera, che diminuisce all’aumentare della lunghez- za focale; le dimensioni e le proporzioni dell’immagine, infine, vengono determinate dall’estensione della matrice di sensori della telecamera.

Come `e stato gi`a accennato, l’immagine acquisita risulta essere capovolta; prima di subire ulteriori elaborazioni deve, dunque, essere raddrizzata, attraverso un processo hardware (interno alla telecamera), o software.

Per maggiore chiarezza nella trattazione successiva ci si riferir`a ad un piano, det-

2All’interno di GOLD `e gi`a presente uno strumento, denominato ImageLUT, in grado di eseguire questo tipo di elaborazione

(24)

to piano dell’immagine simmetrica, su cui viene proiettata una immagine virtuale corrispondente all’immagine reale gi`a raddrizzata.

Si consideri ora il particolare sistema stereoscopico presentato in figura 1.3: in esso sono stati posti in evidenza gli assi ottici delle telecamere, ovvero le perpendicolari ai piani delle immagini passanti per i punti di fuoco, e la distanza tra di loro, detta baseline, indicata col simbolo T_y³; le due immagini risultano essere complanari, e i loro bordi superiori e inferiori risultano allineati.

Piano delle immagini

Ty

Asse ottico destro Asse ottico sinistro

Punto di fuoco telecamera destra

Punto di fuoco telecamera sinistra

Figura 1.3: Sistema di telecamere stereo

Nella figura 1.4 `e illustrata, vista dall’alto, la proiezione di un punto del mondo sui piani delle immagini simmetriche nel sistema appena presentato.

In queste ipotesi (che rispecchiano la configurazione delle telecamere installate sul Terramax), risulta semplice dare prova dell’affermazione con cui si `e aperto questo capitolo.

Osservazione 1 Punti del mondo reale posti su uno stesso piano parallelo al piano delle immagini presentano la stessa disparit`a

Questo principio pu`o essere dimostrato provando che, al variare della posizione del punto del mondo reale all’interno del piano indicato in figura 1.4 dalla linea tratteggiata, e perpendicolare al foglio, la distanza tra le proiezioni di tale punto sul piano dell’immagine simmetrica non cambia.

3A seconda delle applicazioni, questa pu`o variare da pochi centimetri a diversi metri

(25)

Ty 0 X

Y

d

Punto di fuoco sinistro

Punto di fuoco destro f

Asse ottico destro

Piano dell’immagine simmetrica Asse ottico sinistro

immagine Punti dell’

mondo realePunto del

Figura 1.4: Proiezione di un punto del mondo reale sul piano delle immagini

(26)

Quando il movimento considerato avviene in una direzione perpendicolare al foglio si pu`o immediatamente considerare l’osservazione verificata, mentre nel caso lo spostamento venga effettuato lungo la linea tratteggiata, bisogna ricorrere alla similitudine tra i triangoli con vertici uno il punto del mondo reale e i punti di fuoco, e l’altro ancora il punto del mondo reale e le sue proiezioni sul piano dell’immagine simmetrica.

Detta similitudine sussiste in quanto un angolo `e in comune tra di essi, mentre i relativi lati opposti sono paralleli, e non viene meno al muoversi del vertice superiore lungo la linea tratteggiata.

La lunghezza del lato inferiore del triangolo interno (che rappresenta la disparità del piano in esame) non può dunque variare, in quanto proporzionale a T_y(che è fisso) secondo il rapporto di similitudine esistente tra i due triangoli.

In figura 1.5 sono rappresentati i piani a disparit`a costante appena trattati.

Figura 1.5: Piani ad uguale disparit`a, perpendicolari agli assi ottici

Osservazione 2 La disparità con la quale un punto del mondo reale è proiettato nelle due immagini è inversamente proporzionale alla distanza tra il punto reale e il piano delle immagini simmetriche (prolungato all’infinito), e può essere espressa secondo la formula:

d = f · Ty

x (1.1)

(27)

Osservando il triangolo verde in figura 1.4, si pu`o notare come questo sia simile a quello che ha per vertici il fuoco sinistro, l’intersezione tra l’asse ottico sinistro e il piano dell’immagine simmetrica, e l’intersezione tra la linea obliqua che congiunge il punto del mondo reale col fuoco sinistro e il piano dell’immagine simmetrica.

Il cateto parallelo all’asse Y del secondo triangolo descritto rappresenta la disparit`a d del punto del mondo reale considerato, dal momento che questo si trova sull’asse ottico destro, mentre quello parallelo all’asse Y rappresenta la lunghezza focale f ; vale quindi la proporzione

x : Ty= f : d (1.2)

da cui si ricava l’enunciato.

1.1 La V-disparity image

Si consideri la figura 1.7: essa rappresenta, secondo una visuale laterale, la scena inquadrata da una coppia di telecamere disposte come in figura 1.6; al suo interno sono evidenziati ed etichettati alcuni dei piani a disparit`a costante gi`a presentati in figura 1.5; il terreno, supposto perfettamente orizzontale, corrisponde al piano Z = 0.

Tenendo presente queste considerazioni, si pu`o facilmente capire come, nelle immagini sintetiche presentate in figura 1.8, generate simulando il comportamento della coppia di telecamere appena descritte, la riga inferiore derivi dalla proiezione dell’in- tersezione tra il piano S3 ed il terreno.

Conoscendo la disparit`a d che caratterizza S3, e tenendo conto della baseline Ty

e della lunghezza focale f `e possibile risalire, tramite la proporzione 1.2, alla sua distanza dal punto di fuoco.

Da questo risultato si pu`o ricavare, tramite opportune formule trigonometriche che tengano conto dell’angolo di pitch delle telecamere, la coordinata dell’intersezione tra il piano S3 e l’asse X .

(28)

X Y Z

Figura 1.6: Schema della disposizione di una coppia di telecamere stereo

Pitch z

Asse ottico S2 S3 S4

0

S5 S6 S1

x simmetricaImmagine

Figura 1.7: Superfici ad uguale disparit`a e loro intersezioni col terreno (rappresentato dall’asse x)

(29)

Immagine sinistra Immagine destra

Figura 1.8: Immagini stereo sintetiche

Basandosi su queste considerazioni si può calcolare il costo di abbinamento [28], per diversi valori di disparità, tra due righe di pixel corrispondenti nelle due immagini, secondo un approccio introdotto da Labayrade [24], e illustrato in figura 1.9 (in cui viene evidenziato, per la coppia di righe in esame, il valore di disparità per cui il costo di abbinamento risulta minimo).

Riportando in un grafico i costi di abbinamento, in funzione della riga dell’im- magine (coordinata V ) e della disparità (coordinata D) per cui sono stati calcolati, si ottiene la cosiddetta V-disparity image, o immagine di correlazione (come quella in figura 1.10), dove la luminosità di ciascun pixel è proporzionale alla bontà del match corrispondente.

Osservando questa immagine si può notare una serie di punti più luminosi allineati, corrispondenti alle disparità per cui si ha, riga per riga, un buon abbinamento tra gli elementi del terrreno; ci sono, poi, due segmenti verticali: quello più alto corrisponde al cielo, che, essendo a distanza infinita, assume una disparità nulla, mentre il secondo viene generato dal pedone, che si configura come un elemento verticale di una certa dimensione, e che quindi dà origine ad un tratto a disparità costante.

(30)

Figura 1.9: Individuazione della disparit`a a minimo costo di abbinamento tra righe dell’immagine

V

U D

V

0 0

Immagine sinistra Immagine destra V-disparity image

Figura 1.10: V-disparity image

(31)

no, ma l’approccio utilizzato per la sua costruzione `e di tipo globale, e risulta dunque poco adatto quando si tenta di analizzare aspetti locali dell’immagine, quali possono essere gli ostacoli in essa presenti.

Questo genere di problematica risulta pi`u facile da trattare se si utilizza la cosid- detta disparity space image (DSI), in cui si cerca di determinare un valore di disparit`a per ciascuno dei suoi elementi, in modo che sia poi possibile ricostruirne la posizione all’interno del mondo, secondo la proporzione 1.2.

La costruzione della DSI, nel caso il sistema stereo utilizzato sia quello illustrato in figura 1.6, avviene abbinando ciascun pixel dell’immagine destra con quelli dell’im- magie sinistra presenti sulla stessa riga⁴, e scegliendo come valore di disparit`a quello per cui il costo di questa operazione sia minimo.

In figura 1.11 si pu`o osservare come ai pixel dell’immagine originale destra ven- gano assegnati i valori di disparit`a che meglio li caratterizzano.

Immagine originale destra Immagine di disparit`a

Figura 1.11: Esempio di immagine di disparit`a: differenti colori contraddistinguono differenti valori di disparit`a.

4Ciò è corretto, dal momento che il sistema utilizzato prevede telecamere allineate, con angoli di pit- ch identici, e di roll e yaw nulli, in modo che i loro assi ottici risultino paralleli ed i piani dell’immagine congruenti; in un caso più generale la retta su cui eseguire la ricerca, detta retta epipolare, risulterà obliqua

(32)

I criteri per l’abbinamento dei pixel sono senza dubbio l’aspetto pi`u delicato del calcolo della DSI, dal momento che devono soddisfare esigenze contrastanti: accuratezza dei risultati, velocit`a, assenza di artefatti, robustezza.

In letteratura sono stati seguiti diversi approcci [28], pensati per far fronte ai problemi appena citati, ma nessuno `e ancora in grado di dare una risposta soddisfacente a tutti nello stesso momento.

La situazione affrontata nella Grand Challenge ha reso necessaria una scelta, e questa `e ricaduta sulla classe di metodi che garantisce le prestazioni migliori in termini di velocit`a: la correlazione basata su finestre.

Gli assunti che stanno alla base di questo tipo di algoritmi sono che le superfici trattate siano Lambertiane (ovvero che non cambino aspetto al variare del punto di osservazione)⁵ e continue a tratti (caratteristica, questa, tipica delle immagini naturali);

sotto queste ipotesi, piccole regioni attorno alla proiezione dello stesso punto del mondo reale appaiono pressochè identiche in entrambe le immagini della coppia stereo, pur se in posizioni leggermente differenti: attraverso un processo iterativo di confronto è dunque possibile accoppiarle, e risalire cos`ı alla disparità sotto cui viene visto il punto che le ha generate.

Esiste, comunque, anche la possibilità che per una finestra non sia possibile trovare alcun abbinamento soddisfacente, ad esempio a causa di fenomeni di occlusione, o perché il contenuto informativo al suo interno è troppo basso (come accade in zone particolarmente prive di tessitura); in questi casi si assegna un valore convenzionale per indicare una disparità sconosciuta.

5Come si vedrà in seguito, tale ipotesi non sempre risulterà rispettata, in particolar modo quando la baseline impiegata sarà grande

(33)

Le ragioni di natura teorica fin qui introdotte non sono state le uniche a determinare i requisiti tecnici del sistema di visione a bordo del Terramax; vedremo ora come anche altri aspetti, di natura pi`u pratica, abbiano influito sulla sua messa a punto, e quale sia stata la configurazione finale risultante.

2.1 Disposizione e parametri principali delle telecame- re

Quando si vuole realizzare un sistema di acquisizione stereo uno degli aspetti fon- damentali da considerare `e la distanza tra le telecamere, ovvero la baseline; que- sto parametro, infatti, influenza sia le dimensioni del campo visivo analizzabile, sia l’accuratezza dei risultati forniti.

In robotica i sistemi stereo sono molto studiati, ma le baseline utilizzate sono spes- so piccole (pochi centimetri) [30, 31, 13]: in questo modo, infatti, è possibile produrre una mappa molto dettagliata della regione di spazio più prossima al robot¹, che è quella di interesse maggiore, dal momento che le velocità in gioco sono in genere basse.

Nel caso in esame, invece, il veicolo deve muoversi sia a velocit`a sostenute che a basse velocit`a, durante le operazioni di manovra; nella prima situazione il pianificatore

1I range considerati vanno di solito dai 3 ai 7 metri di distanza

24

(34)

di moto deve poter disporre di una mappa che copra una regione di spazio abbastanza ampia, per consentirgli di elaborare in tempo utile una traiettoria in grado di evitare gli ostacoli presenti, mentre nella seconda il range visivo va ridotto a favore di un maggior grado di dettaglio nella ricostruzione dell’ambiente circostante il mezzo.

Per far fronte a queste esigenze contrastanti si `e scelto di utilizzare il sistema visi- bile in figura 2.1, formato da tre telecamere, disposte in modo tale da formare baseline di dimenisoni differenti.

Figura 2.1: Baseline del sistema di acquisizione

Come si può osservare la disposizione dei sensori è asimmetrica, dato che in que- sto modo è possibile disporre di tre baseline differenti; la dimensione della maggiore

`e stata fissata in 1.5 m, mentre per le altre si era pensato di rispettare la cosiddetta

”proporzione aurea”², poi arrotondata³ arrivando ad avere due baseline intermedie di 0.5 m e 1.0 m.

Le lenti ottiche utilizzate sono da 6mm, una misura in grado di fornire agli og- getti un ingrandimento adatto nei range visivi in esame, senza introdurre eccessive distorsioni.

2Secondo cui, dette a e b le parti di cui si compone un segmento, queste sono legate alla sua lunghezza totale (a + b) dalla relazione a

b= b

a + b

3I valori esatti sarebbero stati a = 0.57 m, b = 0.93 m, a + b = 1.5 m

(35)

questo vincolo riduce il carico computazionale del sistema, dal momento che il problema trattato risulta di complessit`a inferiore, ma richiede anche una calibrazione molto accurata.

Per semplificare questa operazione i supporti delle telecamere sono stati dotati di viti di regolazione, in modo da poter intervenire in maniera indipendente sugli angoli di roll, pitch e yaw; nelle figure 2.2 e 2.3 si possono vedere alcuni particolari del sistema di acquisizione installato sul Terramax.

Figura 2.2: Una delle telecamere del Terrmamx, e il relativo supporto regolabile

Analizzando più nel dettaglio le regolazioni da effettuare, si osserva che l’angolo di roll deve essere portato il più possibile vicino allo zero, ad esempio utilizzando una livella; l’angolo di pitch, invece, deve risultare identico per tutte le telecamere: a questo scopo è utile visualizzare le immagini acquisite sovrapponendole, cos`ı da poter controllare che alcuni elementi caratteristici (come la linea dell’orizzonte) compaiano sempre alla stessa altezza.

Al momento di fissare l’angolo di yaw si è scelto di tenere gli assi ottici delle telecamere leggermente convergenti, in modo da aumentare la regione di campo visivo che queste condividono: tale configurazione tende a produrre una rotazione delle rette epipolari (che comunque può essere trascurata), e, cosa più importante, fa comparire

(36)

Figura 2.3: Dettaglio delle viti di regolazione

gli oggetti oltre una certa distanza con una disparit`a negativa (e di questo si `e dovuto tenere conto al momento della stesura del codice).

2.1.1 Meccanismi di sincronizzazione

Perch`e l’intero sistema funzioni correttamente `e necessario che sia le telecamere che il sensore laser installati sul Terramax acquisiscano i dati nello stesso momento: a tale scopo viene utilizzato un dispositivo (denominato SyncBox, e visibile in figura 2.4) in grado di generare i segnali di attivazione per i vari sensori a bordo del veicolo; una analisi dettagliata del suo funzionamento si trova in [27].

Figura 2.4: Il SyncBox

(37)

della Grand Challenge, presentati in [7].

2.1.2 Altri problemi

Vibrazioni

Il sistema di visione `e stato posizionato nella parte frontale del veicolo, e risulta solidale col telaio, essendo fissato ad una grossa barra d’acciaio, come si pu`o vedere in figura 2.5; questa configurazione, pur necessaria, ha lo svantaggio di trasmettere alle telecamere notevoli vibrazioni, soprattutto quando il motore gira a bassi regimi: le sollecitazioni che si producono purtroppo tendono a modificare le impostazioni delle telecamere (come gli angoli di pitch, roll e yaw o l’apertura del diaframma), rendendo necessario il ricorso ad appositi liquidi per il fissaggio delle viti di regolazione.

Figura 2.5: Il fissaggio del sistema di visione al Terramax

(38)

Sporco

Nell’ambiente in cui si trova ad operare il Terramax sono comuni tratti di strada ster- rati o sabbiosi, dove fango, schizzi e polvere possono rapidamente rendere inservibili le telecamere; per evitare questo tipo di inconvenienti sono state realizzate le sca- tole protettive visibili in figura 2.6, che integrano un sistema di pulizia automatico dell’obbiettivo.

Figura 2.6: Dettaglio delle protezioni per le telecamere

(39)

Ricavare la V-disparity image da una coppia di immagini stereo come quelle presentate in figura 3.1, tenendo conto delle considerazioni gi`a esposte sull’approccio da seguire per contenere i tempi di esecuzione, richiede essenzialmente di confrontare regioni delle immagini di destra e di sinistra, misurandone la somiglianza secondo una qualche metrica.

Figura 3.1: Immagini stereo di una strada asfaltata

In quest’ottica, utilizzare direttamente le immagini acquisite dalle telecamere pu`o dare luogo a risultati scadenti, sia per le differenze di luminosit`a che talvolta sono presenti tra i due fotogrammi, sia, soprattutto, per il fatto che zone di colore partico-

30

(40)

larmente uniformi possono dare luogo a buoni valori di matching anche per disparit`a diverse da quella corretta.

Mentre al primo problema si può porre rimedio correggendo via software la lumi- nosità, il secondo suggerisce di utilizzare una coppia di immagini, derivate da quelle originali, in cui siano state messe in risalto le zone a più alto contenuto informativo, ovvero i bordi, tramite una operazione di filtraggio, ad esempio utilizzando la maschera di Sobel, il cui risultato è visibile in figura 3.2.

Figura 3.2: Immagini di Sobel di una strada asfaltata

Risultati migliori si possono ottenere considerando solo la componente verticale dei bordi, e il loro segno; in [6, 7] sono esposte in dettaglio le considerazioni che hanno infine portato ad applicare alle immagini acquisite, prima di utilizzarle per il calcolo della V-disparity image, un tipo di filtraggio derivato da quello appena descritto, in cui però i possibili valori di intensità assunti dai bordi sono soltanto tre (-1, 0, 1), come è stato fatto in figura 3.3; il principale effetto di questa operazione è di mettere in risalto i tratti caratteristici della V-disparity image, da cui ricavare l’andamento del terreno; il risultato ottenuto è quello presentato in figura 3.4.

All’interno di GOLD esiste un modulo per gestire i tipi di filtraggio descritti, ed `e stato utilizzato per generare le immagini su cui calcolare la V-disparity image: ci`o ha facilitato il confronto tra i risultati prodotti dal software esistente e quello nuovo, dal momento che entrambi hanno potuto utilizzare gli stessi dati in ingresso.

(41)

Figura 3.3: Immagini di Sobel ternarizzate di una strada asfaltata

I pixel verdi corrispondono ad un bordo positivo, quelli rossi ad uno negativo e quelli neri all’assenza di bordi

Figura 3.4: V-disparity image di una strada asfaltata

(42)

3.1 Ottimizzazioni al codice

La V-Disparity image è costituita da una matrice con un numero di righe pari a quel- lo delle immagini da cui viene ricavata, ed un numero di colonne fissato a piacere¹, che indicheremo con c_vdi. Detto dmin il minimo valore di disparità per cui si vuole effettuare il calcolo, l’elemento posto all’intersezione tra l’i-ma riga e la j-ma colon- na rappresenterà la correlazione tra l’i-ma riga dell’immagine sinistra e l’i-ma riga di quella destra, traslata in orizzontale di j + d_min posizioni.

Algoritmo 1 Algoritmo di base per il calcolo della VDI

1:

2: procedure VDI(imm_sx, imm_dx, d_min, c_vdi, vdi)

3: r ← num righe(imm_dx)

4: for i ← 0, r − 1 do

5: for j ← 0, c_vdi− 1 do

6: PESOELEMENTOVDI(imm_sx, imm_dx, i, j + d_min, p)

7: vdi(i, j) ← p

8: end for

9: end for

10: end procedure

11:

12: procedure PESOELEMENTOVDI(imm_sx, imm_dx, riga, disparita, peso)

13: peso ← 0

14: c ← num colonne(imm_dx)

15: inizio ← −(min(disparita, 0))

16: f ine ← (c − (max(disparita, 0)))

17: for k ← inizio, f ine − 1 do

18: peso ← peso + abs(imm_dx(riga, k) − imm_sx(riga, k + disparita))

19: end for

20: peso ← peso/( f ine − inizio)

L’algoritmo 1 mette in evidenza il tipo di criterio utilizzato per valutare la correlazione tra una coppia di righe omologhe, per un certo valore di disparit`a: la somma

1Tenendo comunque presente che, detto c il numero di colonne di una delle immagini di partenza, deve sempre valere che

−c < d_min< c 1 ≤ c_vdi≤ c − d_min

(43)

elevate [18], e si `e scelto di impiegarlo anche in questa occasione dal momento che, tra le istruzioni del set Intel^R SSE, ne esiste una in grado di calcolare in parallelo tale costo di abbinamento.

Per poter comprendere come sia possibile applicare il modello computazionale SIMD al problema in esame occorre, per`o, conoscere prima pi`u in dettaglio come le immagini da elaborare vengano memorizzate all’interno del calcolatore e come sia possibile accedervi tramite le istruzioni Intel^R MMX ed SSE.

Per prima cosa dalle immagini acquisite dalle telecamere viene estratta l’informazione sulla luminanza, codificata come una serie di valori compresi tra 0 e 255²(dove 0 rappresenta il nero, e 255 il bianco); viene quindi applicato su di esse il filtraggio che produce le immagini di Sobel ternarizzate, operando, per`o, la sostituzione illustrata nella tabella 3.1 rispetto ai valori in uscita originariamente previsti dal filtro.

Valori in uscita dal filtro originale nuovo

-1 0

0 127

1 254

Tabella 3.1: Sostituzione sui valori del filtro di Sobel ternarizzato

A questo punto in memoria sono presenti due immagini filtrate, costituite da una serie di pixel contigui, ciascuno dei quali occupa un solo byte, e assume uno tra i tre valori positivi (0, 127, 254).

Come si `e visto, nel corso dell’elaborazione, fissate la riga e la disparit`a in esame, si deve procedere calcolando i valori assoluti delle differenze pixel a pixel tra le due porzioni di immagini sovrapposte, sommandoli, e dividendo il risultato per il numero di elementi analizzati; l’istruzione cui si faceva riferimento poc’anzi, il cui opcode³

`epsadbw, effettua con un buon grado di parallelismo gran parte delle operazioni ri- chieste, dal momento che, agendo su 64 bit per volta, computa le differenze in valore

2Dunque rappresentabili tramite log₂(256) = 8 bit, ovvero 1 byte, ciascuno

3Ossia lo mnemonico utilizzato per invocarla all’interno del codice assembly

(44)

assoluto byte a byte tra le porzioni corrispondenti dei suoi operandi e le somma, secon- do o schema riportato in figura 3.5: ci`o significa che `e possibile suddividere ciascuna riga in finestre di 8 pixel, e per ciascuna calcolare un unico contributo di correlazione, pari alla somma di quelli dei suoi elementi.

Figura 3.5: Elaborazione svolta dall’istruzionepsadbw

L’impiego di questa istruzione richiede, comunque, alcuni accorgimenti, dal momento che vengono fatte in modo implicito almeno due ipotesi sui dati trattati, ovvero che questi siano costituiti da una serie di interi senza segno di lunghezza 1 byte, e che tutti gli 8 byte presenti in ciascun registro vadano elaborati.

La sostituzione presentata in tabella 3.1 risolve il primo problema, mentre per quanto riguarda il secondo si deve tener conto che, nella rappresentazione in memoria utilizzata per le immagini, l’ultimo pixel di ciascuna riga precede immediatamente il primo di quella successiva: se la differenza tra i valori degli indici denominati nell’al- goritmo 1 inizio e f ine non risulta multipla di 8, le finestre su cui eseguire il confronto non possono coprire esattamente l’intera area di sovrapposizione tra le righe (come si pu`o vedere in figura 3.6).

(45)

Figura 3.6: Calcolo della correlazione tra due righe omologhe

Supponendo che le immagini utilizzate siano larghe 13 pixel, si vede come, per una dispa- rit`a di -2, l’istruzionepsadbwpossa essere invocata senza ulteriori interventi correttivi una sola volta (pixel azzurri), dato che una sua seconda esecuzione andrebbe ad inte- ressare altri elementi oltre a quelli rossi (gli unici su cui il calcolo debba essere ancora svolto)

(46)

I dati vengono prelevati dalla memoria sempre a gruppi di 4 od 8 byte, tramite le istruzionimovd(move doubleword) e movq(move quadword), ed inseriti nei registri MMX, dove sono elaborati; dalle considerazioni appena esposte appare evidente come le opzioni disponbili al momento di effettuare il calcolo della correlazione siano due:

gestire in qualche modo i casi di bordo, o semplicemente ignorarli, evitando di tenerne conto ai fini del computo del valore di match per la riga in esame.

numero bit nome

4 nibble

8 byte

16 word

32 doubleword

64 quadword

Tabella 3.2: Nomi dei pi`u comuni raggruppamenti di bit

La prima strada comporta delle operazioni aggiuntive, e in generale una efficienza leggermente minore, in quanto il flusso di controllo risulta pi`u complesso, mentre la seconda fornisce risultati meno accurati, dal momento che questi vengono in generale ricavati da un numero inferiore di pixel (pi`u precisamente, ( f ine − inizio) mod 8 pixel⁴ in meno rispetto a quelli disponibili).

Sperimentalmente si è potuto osservare che la versione approssimata della V-disparity image risulta comunque pressochè indistinguibile da quella calcolata in modo esat- to, con in più il vantaggio che il codice risulta semplice (come si può osservare nel- l’algoritmo 2, dove l’elaborazione svolta dall’istruzionepsadbw è stata indicata con SAD 8) e veloce.

Un aspetto critico nell’utilizzo della tecnologia Intel^R MMX ed SSE `e costituito dalla elevata latenza⁵ legata alla lettura dei dati in memoria [1]; completare il cari- camento di un registro MMX pu`o richiedere fino a 12 cicli di clock, e, se la succes- siva istruzione lo utilizza, il processore si ritrova in una condizione di stallo, in cui,

4L’operatore mod indica il resto della divisione tra due numeri interi

5Ovvero il numero di cicli di clock che devono trascorrere prima di poter utilizzare il valore conte- nuto nel registro di destinazione; si definisce invece throughput il numero di cicli di clock che bisogna attendere prima che il processore possa cominciare ad eseguire di nuovo la medesima istruzione

(47)

Algoritmo 2 Algoritmo ottimizzato per il calcolo della VDI (versione 1)

1: procedure VDI(imm_sx, imm_dx, d_min, c_vdi, vdi)

3: for i ← 0, r − 1 do

4: for j ← 0, c_vdi− 1 do

5: PESOELEMENTOVDI(imm_sx, imm_dx, i, j + d_min, p)

6: vdi(i, j) ← p

7: end for

8: end for

10:

12: peso ← 0

16: f ine ← ( f ine − ( f ine%8))

17: iter ← ( f ine − inizio − 8)%8

18: for k ← 0, iter do

19: SAD 8(imm_sx, imm_dx, riga, inizio + k ∗ 8, disparita, sad)

20: peso ← peso + sad

21: end for

24:

25: procedure SAD 8(imm_sx, imm_dx, riga, colonna, disparita, sad)

26: sad ← 0

27: for l ← 0, 8 do

28: sad ← sad + abs(imm_dx(riga, colonna + l) − imm_sx(riga, colonna + disparita + l))

29: end for

(48)

cio`e, il normale funzionamento di tipo pipeline risulta interrotto, con una conseguente dilatazione dei tempi di esecuzione.

Questo problema risulta mitigato se si riesce ad inserire, tra la lettura di un dato dalla memoria e la sua successiva elaborazione, altre istruzioni da esso indipenden- ti, secondo una tecnica detta instruction pairing: con questo sistema si pu`o tenere occupato il processore, nell’attesa che la prima operazione venga completata.

Nel caso in esame si possono migliorare le prestazioni utilizzando finestre di 16 pixel, ciascuna suddivisa in due parti da 8, ed elaborando due righe alla volta, portando cos`ı il numero di registri impiegati a (2 ∗ 2) ∗ 2 = 8: le operazioni di caricamento dei dati possono essere dunque svolte in parallelo, e gli effetti dovuti agli stalli venire ridotti; l’algoritmo 3 sintetizza questi interventi⁶.

6Nell’ipotesi che il numero di righe dell’immagine sia divisibile per due

(49)

r ← num righe(imm_dx

3: for i ← 0, (r/2) − 1 do

4: for j ← 0, c_vdi− 1 do

5: PESOELEMENTOVDI(immsx, imm_dx, i ∗ 2, j + dmin, p)

6: vdi(i ∗ 2, j) ← p

7: PESOELEMENTOVDI(imm_sx, imm_dx, (i ∗ 2) + 1, j + d_min, p)

8: vdi((i ∗ 2) + 1, j) ← p

9: end for

10: end for

12:

14: peso ← 0

18: f ine ← ( f ine − ( f ine%16))

19: iter ← ( f ine − inizio − 16)%16

20: for k ← 0, iter do

21: SAD 16(imm_sx, imm_dx, riga, inizio + k ∗ 16, disparita, sad)

22: peso ← peso + sad

23: end for

26:

27: procedure SAD 8(imm_sx, imm_dx, riga, colonna, disparita, sad)

28: sad ← 0

29: for l ← 0, 8 do

30: sad ← sad + abs(imm_dx(riga, colonna + l) − imm_sx(riga, colonna + disparita + l))

31: end for

33:

34: procedure SAD 16(immsx, imm_dx, riga, colonna, disparita, sad)

35: SAD 8(imm_sx, imm_dx, riga, colonna, disparita, sad₁)

36: sad ← sad₁

37: SAD 8(immsx, imm_dx, riga, colonna + 8, disparita, sad2)

38: sad ← sad + sad₂

(50)

Costruzione della disparity space image

Come per la V-disparity image, anche nel caso della disparity space image utilizzare direttamente le immagini acquisite non porta a risultati soddisfacenti, con la differenza, però, che la soluzione consiste nell’utilizzare un filtraggio di Sobel che faccia risaltare i bordi verticali, dal momento che ciò che va messo in evidenza sono proprio gli aspetti locali (legati alla presenza di ostacoli), e non quelli globali (per i quali solitamente pre- vale l’informazione legata all’andamento del terreno); nelle figure 4.1 e 4.2 è illustrato questo tipo di preelaborazione.

Figura 4.1: Immagini stereo di un centro abitato

Il tipo di approccio scelto per il calcolo della disparity space image, introdotto nel capitolo 1, prevede che la disparit`a associata ad un punto sia quella per cui il costo di

41

(51)

Figura 4.2: Immagini di Sobel di un centro abitato

abbinamento, calcolato su una finestra di pixel, risulti minimo; detto questo, `e facile capire come il dimensionamento di tale regione sia piuttosto critico, e meriti alcune considerazioni.

Nel caso in cui una finestra si trovi a cavallo di un cambiamento di disparit`a, come accade, ad esempio, lungo i bordi di un ostacolo che si staglia sullo sfondo, l’abbinamento avviene secondo il valore predominante tra quelli al suo interno: finestre piccole, dunque, meglio si prestano se gli elementi da individuare hanno dimensioni ridotte, dal momento che solo cos`ı questi possono occuparne una porzione significativa.

Il sistema di visione privilegia la localizzazione degli ostacoli paliformi, dal momento che i sensori laser vengono facilmente messi in crisi da questi oggetti, i quali, occupando un angolo di scansione molto ridotto, danno luogo a pochi echi: una caratteristica desiderabile sar`a, dunque, che le finestre si estendano prevalentemente in direzione verticale.

Anche in questo caso, come per la V-disparity image, la strada seguita per l’ottimiz- zazione del codice `e quella dell’elaborazione SIMD: tale scelta ha posto un ulteriore vincolo sulle regioni da considerare, ed in particolare che una delle loro dimensioni sia multipla di 4 o di 8, in modo da facilitare le operazioni di caricamento dei dati all’interno dei registri.

Visti i requisiti da soddisfare, si `e infine deciso di impiegare finestre rettangolari larghe 3 pixel e alte 4, che, come si vedr`a, hanno rappresentato un buon compromesso.

(52)

La risoluzione della disparity space image era stata in origine ridotta per consentire prestazioni accettabili, mentre in questa nuova implementazione si ottengono tempi ragionevoli senza bisogno di alcun sottocampionamento: si è comunque provveduto a mantenere la compatibilità col sistema esistente, lasciando la possibilità di ridurre sia in orizzontale che in verticale il numero di pixel presenti¹; nelle figure 4.3 e 4.4 sono messe a confronto le disparity space image ottenute alle risoluzioni previste dal vecchio metodo e da quello nuovo, a partire dalla coppia stereo presentata in figura 4.1.

Figura 4.3: disparity space image di un centro abitato (106x80 pixel)

4.1 Ottimizzazioni al codice

Passiamo ora ad analizzare nel dettaglio come sia possibile ricavare la disparity space image, tenendo conto che per semplicit`a di trattazione gli algoritmi esposti si riferi- scono al caso in cui non siano applicati sottocampionamenti (ossia la risoluzione della DSI risulti identica a quella delle immagini utilizzate per calcolarla). In questa ipotesi, e detti d_terr il vettore contenente, riga per riga, le disparit`a stimate per il terreno²e d_max

1Per dare un’idea delle quantit`a in gioco, un tempo si utilizzavano immagini di 320x240 pixel, e la DSI veniva calcolata per un pixel ogni nove, portando cos`ı la sua risoluzione effettiva a 106x80 pixel, mentre ora tale sottocampionamento non risulta pi`u necessario

2Ottenute applicando i principi esposti in [7] alla V-disparity image calcolata sulla stessa coppia stereo

(53)

Figura 4.4: disparity space image di un centro abitato (320x240 pixel)

la disparità massima per cui effettuare la ricerca, il calcolo dell’immagine di disparità si può svolgere secondo l’algoritmo 4.

Il risultato prodotto può essere reso più affidabile cercando di rimuovere i pixel che abbiano dato luogo ad abbinamenti scadenti, attraverso l’introduzione di una soglia sul valore di correlazione del match migliore, e di una sull’intensità dei valori nella finestra di riferimento (in presenza di poca informazione su bordi è difficile ottenere risultati corretti).

L’elaborazione svolta dalla procedura CORRELAZIONEFINESTRA risulterebbe di molto semplificata utilizzando l’istruzione psadbw, gi`a introdotta nel capitolo 3, a condizione, per`o, di modificare la rappresentazione in memoria delle immagini da elaborare, come mostrato in figura 4.5; in questo modo, infatti, i 24 byte rappresentanti i valori di una coppia di finestre possono essere trasferiti, con sei semplici operazioni di caricamento di doubleword (movd), all’interno di sei diversi registri MMX, per essere poi confrontati secondo lo schema visibile in figura 4.6³.

3Dove, per semplicit`a, non `e stata indicata l’operazione di normalizzazione

(54)

Algoritmo 4 Algoritmo di base per il calcolo della DSI

1: procedure DSI(imm_sx, imm_dx, d_terr, d_max, dsi)

4: for all p ∈ dsi do

5: p ← DISPARITY U NKNOW N

6: end for

7: for i ← 0, r − 1 do

8: for j ← 0, c − dterr(i) do

9: normalizzazione(i, j) ← 0

10: for l ← −1, 2 do

11: for m ← −1, 1 do

12: normalizzazione(i, j) ← normalizzazione(i, j) + imm_dx(i + l, j + m)

13: end for

14: end for

15: end for

16: end for

17: for i ← 0, r − 1 do

18: for j ← 0, c − d_terr(i) do

19: cmin←∞

20: d ← DISPARITY U NKNOW N

21: for k ← 0, d_max do

22: CORRELAZIONEFINESTRA(immsx, imm_dx, i, j, k,

normalizzazione(i, j), c)

23: if c < c_min then

24: cmin← c

25: d ← k

26: end if

27: end for

28: dsi(i, j) ← d

29: end for

30: end for

32: procedure CORRELAZIONEFINESTRA(immsx, imm_dx, riga, colonna, disparita, norm, correlazione)

33: correlazione ← 0

34: for l ← −1, 2 do

35: for m ← −1, 1 do

36: correlazione ← correlazione + abs(imm_dx(riga + l, colonna + m) − immsx(riga + l, colonna + m + disparita))

37: end for

38: end for

39: correlazione ← correlazione/norm

(55)

Figura 4.5: Rappresentazioni in memoria di un’immagine

La figura a) illustra il modo pi`u comune di trasformare una matrice di pixel (in questo caso di dimensioni 13x10) in un vettore, concatenando le righe che la compongono; nalla figura b) si pu`o invece osservare come, effettuando la medesima operazione agendo sulle colonne, pixel allineati in senso verticale risultino contigui in memoria.

(56)

Figura 4.6: Calcolo della correlazione tra due finestre

(57)

con registri mmx(i)), e con SAD 8 la somma di differenze di valori assoluti su 8 byte in parallelo si ottiene l’algoritmo 5, in cui il costo di abbinamento `e calcolato su gruppi di 4 byte.

Le prestazioni fin qui ottenute possono essere ulteriormente migliorate se si osserva che, per calcolare la disparità di un punto dell’immagine destra, si confronta la finestra che lo circonda con quelle ricavate in successione dalla medesima riga dell’immagine sinistra: si può, dunque, evitare di caricare di volta in volta dalla memoria tutti e tre i segmenti che compongono tali finestre (operazione molto onerosa), riutilizzando, invece, i due già presenti nei registri del processore, secondo lo schema presentato in figura 4.7.

Impiegare questo accorgimento permette anche di sovrapporre, in parte, le operazioni di calcolo della correlazione per una finestra con quelle di caricamento della successiva, riducendo le situzioni di stallo; il risultato di queste ottimizzazioni `e presentato nell’algoritmo 7.

(58)

Figura 4.7: Caricamento ottimizzato della finestra sinistra

Ad ogni iterazione i valori presenti nei registri 1 e 2 sono salvati (1) nei registri tem- poranei 6 e 7, quindi copiati rispettivamente nei registri 0 e 1 (2); infine nel registro 2 vengono inseriti, caricandoli dalla memoria, i valori dei pixel che andranno a costituire la colonna pi`u a destra della nuova finestra