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
 HARRIS
 Aspetti positivi: efficienza
 Aspetti 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 vista
 Aspetti 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 lineare
 Af=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 triangolazione
Colosseo
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
Bundle adjustment
min  ( Pj * P3i  P 2 j ,i ) 2
Pj , P 3i



j
i
P3i --- i-esimo punto 3d
Pj --- matrice di proiezione della j-esima coppia
P2j,i --- punto 2d riferito a P3i nell’immagine j
3D point P3i
2D image point P2j,i
Reprojected point
Pj* P3i
24
Upgrade Metrico
 Metodo straficato
 Ricerca 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 quadric
 Ci 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
Bibliografia
 H&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
30