La tesi verte sulla costruzione della mappa di ambienti indoor a partire da immagini omnidirezionali acquisite da un robot in movimento.
L'idea di base è di valutare la distanza degli oggetti presenti nella scena a partire dal movimento apparente di essi nella sequenza di immagini, secondo il principio che un oggetto posto nelle vicinanze del robot sara soggetto ad un movimento apparente maggiore di uno lontano; si pensi a quello che succede viaggiando in automobile e osservando il paesaggio dal finestrino laterale, il bordo della strada sembra muoversi molto velocemente, mentre gli oggetti lontani dalla strada sembrano quasi fermi. Si noti che per ottenere una stima fatta in questa maniera è necessario che gli oggetti considerati non siano soggetti a movimento (ipotesi di ambiente statico).

Da quanto detto si può quindi suddividere il problema considerato in due sotto problemi:

• Rilevamento del movimento apparente degli oggetti nelle immagini omnidirezionali
• Calcolo della struttura dell'ambiente a partire dai dati ricavati in precedenza

Della soluzione di questi due sottoproblemi si occupano i capitoli 3 e 4 della tesi che riassumeremo in questa introduzione, dopo aver introdotto il concetto di optical flow

.

L'Optical Flow

Si può avere una percezione diretta dell'optical flow mentre ci si muove ad una certa velocità come di un "flusso" nel campo visivo che ha origine in un punto (solitamente posto all'orizzonte) e che si espande verso i lati del campo visivo stesso.
Esso viene utilizzato da molte specie animali e dall'uomo per ricavare informazioni sul moto rilevabile nel campo visivo e per la navigazione. Allo stesso modo viene utilizzato nella computer vision a partire da sequenze di immagini, e in questo ambito esso assume la forma di campo vettoriale nello spazio dell'immagine, associando ad ogni punto (o solamente ad alcuni, secondo l'algoritmo) un vettore di velocità. Alternativamente, l'optical flow può essere rappresentato da un vettore di spostamento (o corrispondenze tra i punti delle immagini) se vengono considerate solamente due immagini per volta.

In letteratura sono presenti un gran numero di algoritmi per la rilevazione dell'optical flow, per le più disparate applicazioni, che possono essere suddivisi in linea di massima in base al principio di funzionamento (Barron):

• Algoritmi basati sul calcolo delle derivate spazio-temporali delle immagini
• Tecniche basati sull'anlisi in frequenza: questi metodi utilizzano informazioni sull'energia o sulla fase ricavate da filtri sintonizza ti in velocità applicati alla sequenza di immagini
• Metodi basati sulle corrispondenze: calcolano gli spostamenti dal confronto della posizione di punti salienti (features) all'interno delle immagini

Le tecniche differenziali fanno riferimento ad una formula detta optical flow constraint equation (equazione di vincolo sull'optical flow) che si ottiene considerando un gradiente luminoso in movimento. Chiamando I_x, I_y e I_t rispettivamente le derivate lungo gli assi x e y delle immagini e lungo la direzione temporale possiamo ottenere, nel caso in cui le velocità degli oggetti all'interno di essi siano sufficiemtemente piccole, una relazione tra di esse e con la velocità del gradiente (v_x,v_y), corrispondenete all'optical flow, in una sequenza di immagini: I_x v_x + I_yv_y + I_t = 0 Questa formula vincola l'optical flow con le derivate spazio-temporali delle immagini ma non lo definisce univocamente, dato che le incognite sono due. Gli algoritmi basati sulle derivate spazio-temporali si differenziano per il tipo di vincolo aggiunto per arrivare ad una stima univoca dell'optical flow.

Algoritmo realizzato per il calcolo dell'optical flow

Osservando le immagini acquisite dal robot in un corridoio possiamo osservare come l'informazione sia contenuta nella parte centrale di esse.Se in particolare consideriamo che quanto detto relativamente alla relazione distanza-moto possiamo notare come l'informazione sull'ambiente utile ai nostri fini sia quella riguardante i muri e le porte presenti nell'immagine.

Sfruttiamo una peculiarità del visore omnidirezionale, quella di mappare le linee vericali presenti nell'ambiente in linee radiali nelle immagini, che insieme ad alcuni vincoli sul movimento del robot (generalmente soddisfatti in questa applicazione) permette di restringere il campo della ricerca dell'optical flow alla sola componente azimutale all'interno dell'immagine.

Questa può essere ottenuta prendendo in considerazione solamente la parte dell'immagine evidenziata in figura. Recuperando i valori RGB della regione di interesse (ROI) e mediandoli lungo le linee radiali otteniamo una immagine unidimensionale (di dimensioni 1 x 1024). Le informazioni sul movimento apparente delle strutture nelle immagini sono calcolate sui punti dell'immagine unidimensionale che presentano variazioni rilevanti nella derivata spaziale dC /dx, che sono di solito associate a zone dove si ha una variazione della struttura spaziale dell'ambiente (bordi delle pareti) oppure variazioni di colore.

L'utilizzo di un'immagine unidimensionale permette di limitare il numero di calcoli da effettuare ed ottenere una veloce esecuzione dell'algoritmo.

L'optical flow viene calcolato in modo gerarchico, stimandolo prima su versioni a bassa risoluzione delle immagini originali ed raffinandolo successivamente sulle immagini ad alta risoluzione. Tale tecnica permette di rilevare ampi valori dell'optical flow senza incorrere nei problemi dovuti all'aliasing temporale, che pregiudicherebbe altrimenti l'affidabilità dei risultati.; L'optical  flow constraint equation applicata alle immagini unidimensionali riesce (scomparendo una delle incognite) a determinare univocamente l'optical flow .

Per ridurre l'influenza del rumore e gli errori dovuti ai fenomeni di occlusione utilizziamo le informazioni derivate dal colore in due modi: abbiamo utilizzato una riformulazione dell'OFCE che fa riferimento alle varianzioni di colore piuttosto che di luminosità; inoltre abbiamo posto una soglia sul prodotto interno dei gradienti spaziali nello spazio RGB, escludendo nel calcolo dell'optical flow quei valori che nelle due immagini portavano ad associare punti aventi variazione di colore troppo diverse.

Il sistema di calcolo dell'optical flow è stato implementato in C++, utilizzando le librerie QT della Trolltech. Le classi principali implementate sono state:

Optical:

si occupa del prelievo della zona d'interesse dall'immagine omnidirezionale

CircOf:

la classe che calcola il valore dell'optical flow a partire da due immagini unidimensionali

Winopt:

classe di interfaccia per interagire con le altre due (scelta delle immagini e visualizzazione dei risultati), non utilizzata in un'eventuale implementazione su robot

Sono state implementate inoltre alcune classi ausiliarie tra le quali sono importanti:

RGBVect:

mantiene le informazioni di un'immagine unidimensionale a colori

ImPyr:

piramide di immagine unidimensionali, utilizzata nell'implementazione del metodo gerarchico

Altre classi sono state utilizzate per motivi di ricerca.

L'algoritmo risulta abbastanza veloce e ne è stato misurata la varianza dell'errore su immagini reali.

Costruzione della mappa

Le osservazioni delle posizioni degli edges permettono di risalire alla distanza degli oggetti dal robot a meno di un fattore determinato dal movimento effettuato tra due osservazioni. In Nelson viene fornita una formula approssimata (nel caso in cui lo spostamento M del robot sia piccolo rispetto alla distanza r_i dell'edge) che collega queste grandezze all'optical flow.

Tralasciando le formule mostriamo la forma dell'optical flow nel caso di traslazione pura, caratterizzato dalla presenza di un fuoco di espansione e da uno di contrazione (nelle cui vicinanze l'immagine appare espandersi e contrarsi per effetto prospettico). Il grafico dell'optical flow appare così costituito da una sinusoide la cui ampiezza dipende dalla distanza degli oggetti osservati alla quale va sommata una costante nel caso in cui il movimento del robot presenti una componente rotazionale.

Per costruire la mappa (costituita dalle coordinate dei punti rilevati) utilizziamo il metodo proposto in Yagi: dato che le equazioni che legano le osservazioni ai punti sono non lineari

la cui risoluzione richiederebbe un tempo di calcolo notevole; per linearizzare il sistema Yagi introduce un passaggio intermedio che consiste nella stima della rotazione mediante il fitting dell'optical flow con una sinusoide. Conoscere la rotazione consente di linearizzare il sistema dal quale è possibile ottenere una stima delle posizioni dei punti della mappa (X_i,Y_i) e della posizionie del robot (U,V)(t) all'ultimo passo in tempo reale.

Il sistema risultante presenta sensibilità all'errore molto alta nella direzione del moto (dove l'optical flow è nullo a prescindere dalla distanza degli oggetti) e minima in direzione perpendicolare al moto.

L'algoritmo per la mappa è stato implementato come script SCILAB, un ambiente open-source simile a MATLAB. Gli script principali sono contenuti nei files

genmap.sci:

script principale, partendo dai dati dell'algoritmo di optical flow costruisce le tracce degli edges e da queste calcola la mappa

stimarot.sci:

stima i parametri della sinusoide a partire dai dati dell'optical flow

gensens.sci:

crea dei dati sintetici (utilizzato per testare l'algoritmo di costruzione della mappa)

getedges.sci e getofrif.sci:

leggono i files contenenti i dati dell'optical flow

Risultati ottenuti

Abbiamo applicato l'algoritmo ad una sequenza di immagini acquisite dal robot in un corridoio del Dipartimento di elettronica e informatica, ottenendo la mappa mostrata in figura.

Come si vede la mappa risulta simile a quella reale e, pur non essendo adatta a creare mappe metriche dell'ambiente, si presta all'utilizzo per navigazione autonoma del robot potendo essere calcolata in real-time.

L'algoritmo risulta inaffidabile riguardo la percezione delle distanze nella direzione del moto, ma a questo è possibile ovviare evitando di percorrere lunghi tratti nella stessa direzione, ma muovendosi lungo linee spezzate o curve (a questo riguardo sono state eseguite delle prove nell'ambiente simulato).

Un problema non risolto è stato quello della gestione dell'apparizione e scomparsa di edges.

L'algoritmo dipende per il suo funzionamento da una stima del moto del robot. Negli esperimenti effettuati si è supposto che il robot si muovesse di 10 cm per frame, sarebbe opportuno inserire nel sistema una stima più precisa del movimento, basata per esempio sul calcolo dell'optical flow sul piano di terra, dal quale estrarre i parametri del moto (in particolare, l'algoritmo si è dimostrato sensibile agli errori sulla stima della rotazione).