Structure from motion

Biagio Montesano

Alessandro Previti

Francesco Puja

Struttura del progetto

Ricerca dei parametri intrinseci della camera (tramite toolbox)

Features

Correlazione

Matrice F e matrici P

Triangolazione

Bundle adjustment e upgrade metrico

Calibration toolbox

Features: Harris vs Lowe I

HARRISAspetti positivi: efficienzaAspetti negativi: durante i test effettuati, si è

evidenziato un rilevante numero di falsi match

SIFT (Scale invariant feature transform)Aspetti positivi: invarianza a scalatura, illuminazione,

traslazione e rotazione, punto di vistaAspetti negativi: costo computazionale relativamente

elevato

SIFT

La scelta è ricaduta sulle SIFT perché la percentuale dei match sbagliati è risultata più bassa

SIFT(2)

Correlazione

La correlazione avviene tramite la creazione di finestre sulle due immagini che contengono le features da correlare (ottenute su ciascuna tramite metodo SIFT)

SIFT sulla prima immagine Selezione delle SIFT a sinistra

Correlazione(2)

Finestra intorno a una SIFT nell’immagine a

sinistra

Finestra intorno a una SIFT a destra, con calcolo delle dei quadrati delle differenze elemento per

elemento

Si assegna alla SIFT di sinistra la SIFT di destra con finestra SSD minima

Esempio di correlazione

Matrice F

Significato della matrice F

Rappresentazione algebrica della geometria epipolare

Rappresenta una correlazione tra un punto di una vista e la linea epipolare nell’altra

Matrice singolare di rango 2

Calcolo di F

Per la stima di F si è usato RANSAC

Caratteristica:

consente una stima robusta garantendo il 97% di correttezza

Breve funzionamento:

• Selezione casuale di campioni in un insieme dato

• Stima degli inliers utilizzando un algoritmo di fitting

• Confronto con un valore di threshold

Calcolo di F

Algoritmo di fitting

• Algoritmo 7 punti:• Vantaggi: ottiene sempre matrice di rango 2 • Maggiore efficienza computazionale nell’utilizzo con

RANSAC

• Svantaggi:• Può restituire tre F rendendo necessaria la

valutazione di ciascuna di esse• La fase di testing ha evidenziato minor accuratezza

nella stima della F e dei relativi inliers

Algoritmo 8 punti normalizzato

Vantaggi: Maggiore accuratezza nella stima di F ed inliers

dimostrata in fase di test

Svantaggi: Coercizione al rango 2 (singularity constraint) Numero dei sample doppio con RANSAC

Preferito l’8 punti come migliore in termini di trade-off

costo/risultato rispetto al 7 punti

Algoritmo 8 punti

1. Normalizzazione (Annulla l’effetto di una selezione arbitraria dell’origine e della scala)

2. Stima di F come soluzione di un sistema lineareAf=0 , SVD(A)=UDVT ultima colonna di V (smallest

singular value of A)

3. Rafforzamento del vincolo di rango 2 (singolarità di F)

4. Denormalizzazione

Esempi di inliers

Calcolo delle P

Si calcolano gli epipoli dalla SVD di F

Si usa la formula P = [[e’]xF|e’]

Approcci alla ricostruzione

Approccio denso

Approccio sparso

Triangolazione

Permette di recuperare un punto nello spazio a partire dalle sue proiezioni su due o più viste

x=PX , si risolve un sistema di equazioni

Stabilite la retta a passante per X e C (centro della prima camera) e la retta b passante per C’ e Y, si intersecano nello spazio per recuperare il punto 3D

Minimizzazione dell’errore geometrico

Triangolazione

Soluzione ottima

Vantaggi: metodo non iterativo, efficienza computazionale

PROCEDURA

1.Parametrizza il fascio di piani delle linee epipolari

2. Calcola la corrispondente linea epipolare l’(T) sulla seconda immagine

3.d(x,l(t))^2 + d(x’,l’(t))^2 [distance function]

4. Trova valore di T che minimizza la funzione

Esempi di triangolazioneColosseo

Pacchetto di gomme

Bundle adjustment

Raffinamento dei punti mondo minimizzando la distanza dei punti immagine trovati rispetto a quelli riproiettati x=PX.

Le nuove P e le nuove X vengono ricavati tramite la funzione di matlab lsqnonlin, stima ai minimi quadrati non lineare, minimizzando una funzione di costo.

Il metodo è iterativo, ad ogni iterazione si aggiornano le P e gli X, alternandole come incognite nella stima

Bundle adjustment

24

Bundle adjustment

P3i --- i-esimo punto 3d Pj --- matrice di proiezione della j-esima coppia P2j,i --- punto 2d riferito a P3i nell’immagine j

j i

ijijPP

PPPij

2,

3,)23*(min

3D point P3i

2D image point P2j,i

Reprojected point Pj* P3i

Upgrade Metrico

Metodo straficatoRicerca piano all’infinito(ricostruzione affine)

Si cercano nello spazio P^3 tre coppie di rette che si sanno essere parallele nella realtà.L’intersezione di queste tre rette ci permette di trovare tre vanish points che ci consentono di definire il piano all’infinito.Possiamo ottenere a questo punto la matrice di trasformazione affine.

Upgrade metrico

Ricerca conica all’infinito(ricostruzione metrica) Abbiamo bisogno di cinque vincoli per definire una

conica Supponiamo w12=w21=0 w11=w22 Gli altri tre vincoli sono:

v1^T*w*v2 = 0 (un vincolo)

l = w*v (due vincoli)

A*A^T = (M^T*w*M)^(-1) da cui traiamo la matrice A tramite

la Cholesky factorization(funzione implementata in matlab)

Upgrade metrico

Dual quadricCi troviamo la quadrica all’infinito, che contiene

informazioni sul piano all’infinito e sulla conica all’infinito.

Otteniamo poi w dalla relazione

e da qui otteniamo la trasformata che ci permette il passaggio da una ricostruzione proiettiva ad una metrica.

Upgrade metrico

Colosseo

Gomme

Morpheus

30

BibliografiaH&Z – Multiple View Geometry

Script matlab disponibili dal sito di H&Z

Script disponibili dal sito di Peter Kovesi

Funzioni di supporto al bundle adjustment definite da Fusiello

Funzione di upgrade metrico quadric linear definito da Kosecka