Sistemi di visione per la Sistemi di visione per la navigazione autonomanavigazione autonoma

Relatore: ch.mo prof. Ruggero FREZZARelatore: ch.mo prof. Ruggero FREZZA

Laureando: Andrea ROSSETTILaureando: Andrea ROSSETTI

Padova, 11 aprile 2005Padova, 11 aprile 2005

2

Il problema della visione stereoIl problema della visione stereo

• Vogliamo realizzare un algoritmo di visione stereo real-time, per Vogliamo realizzare un algoritmo di visione stereo real-time, per valutare le distanze di oggetti inquadrati da due telecamerevalutare le distanze di oggetti inquadrati da due telecamere

• Feature: useremo le Feature: useremo le intensità dei pixelintensità dei pixel, danno output densi e , danno output densi e hanno un campo di applicazione ampio (es.: interni-esterni)hanno un campo di applicazione ampio (es.: interni-esterni)

(Ohta-Kanade, 1986)(Ohta-Kanade, 1986)

3

Relazione disparità-distanzaRelazione disparità-distanza• Se le telecamere hanno piani focali complanari e allineati, Se le telecamere hanno piani focali complanari e allineati,

posso trovare la distanza in base alla disparità con posso trovare la distanza in base alla disparità con un’opportuna triangolazioneun’opportuna triangolazione

b = baseline

d = disparità

Z

f = focale

d

bfZ

• Distanza: inv. prop. alla disparitàDistanza: inv. prop. alla disparità

dbf

ZZ

2

• Risoluzione: prop. al quadrato Risoluzione: prop. al quadrato della distanzadella distanza

4

Procedura di rettificazioneProcedura di rettificazione

• Si riproiettano le immagini su Si riproiettano le immagini su piani focali complanari piani focali complanari allineati, con una rotazione dei allineati, con una rotazione dei piani attorno ai centri focalipiani attorno ai centri focali

• Problema: non sempre posso Problema: non sempre posso disporre di piani focali così disporre di piani focali così allineatiallineati

C2

C1

M2

M1

W

R1

R2

C1

M2

M1

W

R1

C2

R2

• Funzione disponibile nella Funzione disponibile nella libreria OpenCVlibreria OpenCV

5

Mappe di disparitàMappe di disparità• L’output del programma consiste in un immagine in toni di L’output del programma consiste in un immagine in toni di

grigio: maggiore la disparità, maggiore l’intensità luminosagrigio: maggiore la disparità, maggiore l’intensità luminosa

• Quindi Quindi oggetti più vicini = toni di grigio più chiarioggetti più vicini = toni di grigio più chiari

• Dalla mappa di disparità è immediato risalire alle distanze con Dalla mappa di disparità è immediato risalire alle distanze con la relazione disparità-distanzala relazione disparità-distanza

Cam.1 Cam.2

6

Disparità con metodi localiDisparità con metodi locali• Utilizzo la funzione SSD per Utilizzo la funzione SSD per

confrontare due zone rettangolari confrontare due zone rettangolari nell’immagine sinistra e destranell’immagine sinistra e destra

),(),(

2)],(),([yxWji

RL ijIidjI

• Per ogni punto (Per ogni punto (x,yx,y) scelgo il ) scelgo il valore di disparità dvalore di disparità dminmin che che

minimizza SSD(minimizza SSD(x,y,dx,y,d))

• SSD in programmazione SSD in programmazione dinamica: il tempo di calcolo dinamica: il tempo di calcolo diventa indipendente dall’area diventa indipendente dall’area della finestradella finestra

• Tempo totale di esecuzione:Tempo totale di esecuzione:O(righe • colonne • max.livelli)O(righe • colonne • max.livelli)

7

Disparità con metodi globaliDisparità con metodi globali• Cerco la sequenza di matching tra Cerco la sequenza di matching tra

feature che massimizza la feature che massimizza la probabilità di matching dell’intera probabilità di matching dell’intera scanline; tengo conto di eventuali scanline; tengo conto di eventuali occlusioniocclusioni (feature visibili in 1 sola (feature visibili in 1 sola imm.)imm.)

• Equivalente ad un problema Equivalente ad un problema di cammino a costo minimo di cammino a costo minimo (Dijkstra)(Dijkstra)

OriginaleOriginale Met.localiMet.locali Met.globaliMet.globali

• Superiorità rispetto Superiorità rispetto ai metodi localiai metodi locali

Scanline sinistraScanline sinistra

Sca

nli

ne

des

tra

Sca

nli

ne

des

tra

8

Metodi globali: vincoliMetodi globali: vincoli• Alcune combinazioni di matching corrispondono a soluzioni Alcune combinazioni di matching corrispondono a soluzioni

fisicamente impossibili: le scartiamo imponendo dei vincolifisicamente impossibili: le scartiamo imponendo dei vincoli

• Vincolo di unicitàVincolo di unicità: uno stesso pixel non può appartenere a due : uno stesso pixel non può appartenere a due matching diversimatching diversi

• Vincolo di ordinamentoVincolo di ordinamento: scelti due matching (l: scelti due matching (l11,r,r11) e (l) e (l22,r,r22), se ), se

ll11<l<l22 allora anche r allora anche r11<r<r22 e viceversa e viceversa

O(righe • colonne • max.livelli)O(righe • colonne • max.livelli)Metodi globali: tempo di esecuzioneMetodi globali: tempo di esecuzione

pari a quello ottenibile con metodi localipari a quello ottenibile con metodi locali

9

Metodi globali: miglioramentiMetodi globali: miglioramenti

• Vincolo di stabilizzazioneVincolo di stabilizzazione: a : a un’occlusione destra non un’occlusione destra non può seguire un’occlusione può seguire un’occlusione sinistra, e viceversa (almeno sinistra, e viceversa (almeno un pixel di matching nel un pixel di matching nel mezzo)mezzo)

• Uso della SSDUso della SSD anche nell’algoritmo globale anche nell’algoritmo globale

• Termine a prioriTermine a priori: aggiungiamo alla funzione di costo una : aggiungiamo alla funzione di costo una probabilità gaussiana centrata sul valore di disparità al probabilità gaussiana centrata sul valore di disparità al frame precedente; funzionamento in frame precedente; funzionamento in feedbackfeedback

10

Filtraggio di KalmanFiltraggio di Kalman• Vogliamo attenuare la rumorosità delle misure di disparitàVogliamo attenuare la rumorosità delle misure di disparità

• Per ogni pixel dell’output uso un filtro di Kalman con modello Per ogni pixel dell’output uso un filtro di Kalman con modello dinamico molto semplice:dinamico molto semplice:

tt DD 1

• Matrici di covarianza Q ed R: vanno regolate a un valore di Matrici di covarianza Q ed R: vanno regolate a un valore di compromesso tra buona attenuazione del rumore ed eccessiva compromesso tra buona attenuazione del rumore ed eccessiva presenza di “scie” in outputpresenza di “scie” in output

• Ottimizzazione con OpenCV: le operazioni matematiche per il Ottimizzazione con OpenCV: le operazioni matematiche per il filtraggio vengono eseguite in blocco su tutti i pixel con funzioni filtraggio vengono eseguite in blocco su tutti i pixel con funzioni altamente ottimizzatealtamente ottimizzate

11

Risultati sperimentaliRisultati sperimentali

Firewire Firewire 1280x1024 1280x1024 256 toni di 256 toni di

grigiogrigio

PC P4 2GHz PC P4 2GHz RAM RAM 512MB 512MB

12

Risultati sperimentaliRisultati sperimentali

DistanzaDistanzaTelec.sinistraTelec.sinistraTelec.destraTelec.destra

13

• Integrazione con i software per il controllo Integrazione con i software per il controllo e il path planninge il path planning

• Modelli più avanzati per il Filtro di Modelli più avanzati per il Filtro di KalmanKalman

• Uso di immagini a coloriUso di immagini a colori

• Ottimizzazione con istruzioni SIMD e Ottimizzazione con istruzioni SIMD e parallelizzazione per un miglior frame rateparallelizzazione per un miglior frame rate

Sviluppi futuriSviluppi futuri

•Website: http://andrear.altervista.org/tesiWebsite: http://andrear.altervista.org/tesi