Structure from
motion
Corso Visione e percezione a.a.2008/2009
Prof.ssa Maria Fiora Pirri Ardizzone
Studenti:
- Brunetti Mario
- Mancarella Alessandro
- Pavone Giuseppe
1
Contenuti








Presentazione del problema
Sift & Correlazione
Matrice fondamentale
Calibrazione
Triangolazione
Bundle adjustment
Metric upgrade
Approcci alla ricostruzione densa
2
Presentazione problema


Structure from motion
Ricavare la struttura
di una scena a partire
da una sequenza di
immagini
3
Fasi di progettazione



Decomposizione in sottoproblemi
Trattazione teorica
Implementazione in Matlab



Implementazione di differenti metodi
Scelta del metodo con il miglior risultato
Testing su 4 differenti set:




Morpheus
Soggetto semplice (parallelepipedo)
Composizione di soggetti semplici
Soggetto complesso
4
SIFT vs Harris
Necessità di trovare dei punti da correlare nelle varie immagini



Harris:
computazionalmente facili
da trovare
Poca robustezza
Numero di falsi match
elevato


SIFT: maggiore
robustezza a
rotazione,traslazione,
scalatura e variazioni di
luminosità
Con l’implemetazione di
Lowe in C (interfacciata in
Matlab) migliora la
complessità di calcolo
5
Estrazione features








Costruzione scale-space
Costruzione DoG
Localizzazione elementi
estremali
Localizzazione feature points
Filtraggio punti a basso
contrasto
Scelta della risposta lungo gli
edge
Orientazione
Costruzione descrittori
6
Esempi di SIFT
7
Correlazione





Effettuata su coppie di immagini
Per ogni punto si ricerca il suo omologo nell’altra
immagine
Si ricerca l’omologo solo entro un certo raggio
dalle coordinate del primo
Si minimizza l’SSD su una finestra di date
dimensioni (15)
Vengono accettate solo le coppie di punti che
sono vicendevolmente correlati
8
Esempi di correlazione
9
Stima della matrice fondamentale



Permette di correlare ogni punto di un immagine
con la retta epipolare dell’altra
Utilizzo di RANSAC per migliorare la qualità
delle correlazioni
Algoritmo 8-punti normalizzato per la stima della
matrice F
 La
normalizzazione permette che le rette epipolari si
incontrino in un unico punto
 Migliore stima rispetto all’algoritmo 7 punti, minore
complessità rispetto al gold standard
10
RANSAC+Alg. 8 punti norm.
1.
2.
3.
4.
5.
6.
7.
Scelta di 8 coppie di punti correlati (x-x’)
Normalizzazione
Calcolo della F tramite stima ai minimi quadrati a
soddisfare x*F*x’=0
Denormalizzazione
Ricerca degli inliers riferiti agli 8 punti selezionati,
valutando la distanza di Sampson
Valutazione della percentuale di inliers trovati, se
insufficiente ritorna al punto 1
Trovati gli inliers, ri-esecuzione dell’algoritmo 8-punti
per stimare F su un maggior numero di punti
11
Esempi di inliers
12
Calibrazione
Si è fatto ricorso al Calibration Toolbox
 Uso del pattern scacchiera
 Set di foto da diverse angolazioni
 Estrazione dei parametri intrinseci ad
eccezione delle dimensioni del pixel della
camera mx my
 Costruzione della matrice di calibrazione K

13
Esempi di calibrazione
14
Matrici proiettive

Si è scelto di decomporre la matrice
fondamentale (tramite svd) per ricavare gli
epipoli necessari al calcolo della coppia di
matrici proiettive canoniche
15
Triangolazione


Metodo di triangolazione lineare applicato ad
ogni coppia di punti correlati, si risolve un
sistema di equazioni (se sovradeterminato si
ricorre alla stima ai minimi quadrati) estratto
dalle relazioni x=PX
Ai fini di una migliore ricostruzione si è deciso di
utilizzare l’Optimal Triangulation Method, come
descritto da H&Z, correggendo i match trovati
sulle viste forzandoli sui vincoli epipolari
x*F*x’=0
16
Esempi di triangolazione
17
Unificazione delle triangolazioni da
coppie di viste

Sono state provate diverse tecniche, basate sulla
decomposizione delle P=K[R T]=KR[I| -C]:



Rototraslare le successive matrici di proiezione prima di
calcolare i punti mondo, per ottenere i punti riferiti alle coordinate
della prima camera
Per ogni coppia, creare una matrice [R T; 0 0 0 1] dalla P
corrente e premoltiplicarla per i punti mondo trovati in modo da
riferirli tutti alle coordinate della camera corrente, alla fine del
ciclo, tutti i punti sono riferiti alle coordinate dell’ultima camera
Nessuno dei metodi restituisce risultati ottimi, ad ogni
modo quelli migliori sono stati con il secondo metodo
18
Unificazione delle Triangolazioni
da coppie di viste
19
Bundle adjustment




Dall’equazione x=PX, riproiettiamo i punti mondo sui
rispettivi piani immagine
Minimizziamo la distanza tra i punti immagine originali e
quelli riproiettati, modificando i valori dei punti mondo e
delle matrici, basandoci anche sulla matrice di
calibrazione
Le nuove P e i nuovi X vengono ricavati tramite
lsqnonlin, funzione di matlab che esegue la stima ai
minimi quadrati non lineare a minimizzare una data
funzione di costo
Il metodo è iterativo, alla fine di ogni iterazione si
aggiornano prima le P e poi le X, effettuando 2 stime,
considerandole singolarmente come variabili, e si
riproiettano le x, per 5 volte
20
Bundle adjustment
min
Pj , P 3i



P3i --Pj --P2j,i ---
 ( P * P3  P2
j
j
i
j ,i
)2
i
i-esimo punto 3d
matrice di proiezione della j-esima coppia
punto 2d riferito a P3i nell’immagine j
3D point P3i
2D image point P2j,i
Reprojected point
Pj* P3i
21
Esempi di bundle adjustment
22
Upgrade metrica

Anche in questo caso sono stati
considerati diversi metodi:
 Stratificato
 Diretto
23
Stratificato


Si ricava il piano all’infinito calcolando (manualmente) 3 vanishing
points da 3 coppie di linee che sappiamo essere nel mondo
parallele tramite la funzione houghlines chiamata sull’immagine.
Con il piano all’infinito che passa per i punti trovati è possibile
costruire una trasformazione che porta da una ricostruzione
prospettica ad una affine Haff=[I 0; Pinf]
Successivamente, sotto ipotesi di pixel camera quadrati e skew
nullo,si ricava la conica ω all’infinito trovando 3 punti che soddisfano
vincoli:




v1’*ω*v2=0
l= ω*v
Con la conica si ricava la matrice Hm=[A^-1 0; 0 1] dove A soddisfa
AAt=(Mt* ω*M)^-1
Hm*Haff*Xp=Xm è la trasformazione da prospettiva a metrica
24
Diretto




Il metodo stratificato restituisce risultati poco
accettabili
È stata tentata un’altra strada, che esula dal
programma del corso: dual quadric.
La quadrica è una struttura che contiene
l’informazione sul piano all’infinito e sulla conica
all’infinito
Da essa è possibile ricavare una trasformazione
omografica che porta i punti da una
ricostruzione proiettiva a metrica
25
Esempi di upgrade metrico
26
Ricostruzione densa






Sono state create alcune funzioni che permettono di
effettuare una ricostruzione densa
Rettificazione delle immagini
Mappa di disparità per trovare correlazioni per ogni
punto
Triangolazione densa
Le altre funzioni sono identiche alla ricostruzione sparsa
A causa dei cattivi risultati della rettificazione non è stato
possibile effettuare il testing
27
Bibliografia
H&Z – Multiple View Geometry
 Script matlab disponibili dal sito di H&Z
 Script disponibili dal sito di Peter Kovesi
 Funzione di upgrade metrico quadric linear
definito da Kosecka
 Funzioni di supporto al bundle adjustment
definite da Fusiello

28
Grazie per
l’attenzione …
29