Structure from motion Biagio Montesano Alessandro Previti Francesco Puja.
-
Upload
santo-pagano -
Category
Documents
-
view
216 -
download
0
Transcript of Structure from motion Biagio Montesano Alessandro Previti Francesco Puja.
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