Università degli studi di Roma
“La Sapienza”
Algoritmi per
l’Image Alignment
Corso di Visione e Percezione
Studenti: Galizia Luca
Professoressa:
Martinelli Giuseppe Martino
Fiora Pirri
Musilli Roberto
Tutor:
Andrea Carbone
Introduzione al problema
RIFERIMENTI:
-“Lucas-Kanade 20 Years On: A Unifying Framework”
di Simon Baker, Ralph Gross, Takahiro Ishikawa, and Iain Matthews
OBIETTIVO:
Valutazione degli algoritmi per l’Image Alignment:
CONCETTI DI BASE:
-“Image Alignment”: muovere e deformare un template per minimizzare la differenza con una
immagine di ingresso
-“Gradient Descent”: è un algoritmo di ottimizzazione iterativo che si avvicina al minimo locale di
una funzione scendendo lungo il gradiente
-“Error Function”: valuta l’errore tra il template attuale e quello di riferimento
-“Lucas Kanade algorithm”: minimizza la somma dei quadrati tra un template e un’immagine
trasformata nel sistema di coordinate del template
-“Inverse Compositional”: riformulazione dell’algoritmo di Lukas-Kanade a matrice hessiana
costante
POSSIBILI APPLICAZIONI:
-Tracking
-Mosaic construction
-Stereo vision
-Face coding
-…
Lucas-Kanade Algorithm
-Proposto nel 1981. Introduce il problema dell’Image Allignment
-Algoritmo iterativo di ottimizzazione non-lineare di tipo gradient descent
-Allinea un template ad un immagine in ingresso
-Si basa sulla minimizzazione della somma dei quadrati
-Utilizza un vettore p di parametri caratterizzanti una trasformazione, ed una
matrice W(x;p) che identifica il set di deformazioni ammissibili
-Tutti i passi dell’algoritmo devono essere eseguiti ad ogni iterazione
(10)
-L’algoritmo termina quando la stima dei parametri p converge
(9)
Algorithm
The Inverse Compositional Algorithm
con
connorma
normaL2
L2Euclidea
Pesata
-Riformulazione dell’algoritmo di Lucas-Kanade per la riduzione del costo
computazionale
-Allinea l’immagine in ingresso ad un template (il contrario rispetto a L-K)
-Si basa sulla minimizzazione della somma dei quadrati (norma L2 Euclidea)
-Il calcolo dell’Hessiana e dello Jacobiano viene eseguito una sola volta
(non c’è dipendenza diretta rispetto ai parametri)
-L’algoritmo termina quando la stima dei parametri p converge
The Inverse Compositional Algorithm
con norma L2 Pesata
(20) l’unica differenza è che utilizza la
-Algoritmo identico al precedente;
norma pesata
(29)
(19)
(30)
(28)
Iteratively Reweighted Least Squares
IDEA: utilizzare una funzione d’errore robusta al posto della norma L2
Approssimazione
H-Algorithm
-Introdotto
da Dutter
Huber
-Si basa
sulla –minimizzazione
di
-Sostituisce all’Hessiana dell’IRLS classico la formulazione costante già vista in precedenza:
-La matrice jacobiana può essere precalcolata
-L’hessiana, poiché dipende dal vettore p dei parametri, deve
Approssimazione
essere calcolata ad ogniSpatial
iterazione Coherence degli outliers
-Si basa sul raggruppamento dei pixel outliers in gruppi coerenti
algoritmo
può essere
utilizzato
con unaorganizzati
funzioneinrobusta
-Si-Questo
divide il template
in K blocchi
o sotto-template
generalmente
una griglia
regolare
arbitraria
-La matrice Hessiana di ogni sotto-template si assume costante:
-Per le simulazioni è stata utilizzata la funzione d’errore:
-L’Hessiana generale del template assume quindi la forma di seguito riportata; essa deve essere
calcolata ad ogni iterazione ma con un costo computazionale minimo (64)
(63)
Simulazioni
-Sono proposti due script Matlab per il confronto dei vari algoritmi
1)Test
2)Test weighted
robust error
-Confronta l’algoritmo IC a norma euclidea con l’IC a
norma
pesatacon approssimazione H-algorithm e
IRLS
classico,
-Pesa
i pixel con valorispatial
opportuni
con approssimazione
coherence degli outliers
-Si assume che la causa principale di rumore sia l’occlusione
A
rumore
bianco
gaussiano
a varianza
variabile
Scenario
B - utilizza
uniforme
invariante
-La
valutazione
come
parametro
la percentuale
di occlusione
minore
ai pixel
caratterizzati
dada
una
-Comegenerato
matrice in
di modo
peso utilizza
seguente,
che
associa un
peso
maggiore
ai pixel
caratterizzati
-Viene
randomlaun
rettangolo
occludente
parte
della
figura
varianza
del rumore
minore.
un
gradiente
più elevato.
I risultati
ottenutiper
perdiversi
tre differenti
di32.0)
occlusioni (10%, 30% e 50%)
intervalli
di percentuali
varianza
-Il test è effettuato
valori
di varianza
(0.0, 16.0,
-varianza
-> 24.0
mostrano come
le 8.0
prestazioni
dell’algoritmo IC decadano all’aumentare della
Nel caso -varianza
a varianza
la velocità di convergenza dell’algoritmo con la norma
4.0 ->0.0
32.0
percentuale
fino al8.0
punto
che, con un’occlusione del 50%, l’algoritmo diverge quasi
->è40.0
euclidea -varianza
non pesata
più veloce rispetto all’algoritmo a norma pesata. Al
sempre. L’algoritmio H si comporta meglio, ma i risultati migliori si ottengono con
crescere della varianza la situazione si ribalta in quanto in presenza di rumore
l’IRLS classico e quello con l’approssimazione spatial coherence.
In stima
tutti i casi
la velocitàdel
di convergenza
dell’algoritmo
conallacrescere
norma pesata
è più
la
del gradiente
template diviene
più accurata
della sua
veloce
rispetto all’algoritmo originale. La frequenza di convergenza è di
magnitudine.
conseguenza più elevata.
Performance
IRLS
Performance migliori
migliori con
con l’utilizzo
l’utilizzo degli
della algoritmi
norma pesata
Performance migliori con l’utilizzo della norma pesata
(in presenza di rumore)
Riepilogo
-L’algoritmo IC a norma L2 pesata è efficiente tanto quanto l’IC originale, ma il suo impiego
è preferibile per le migliori prestazioni ottenute in presenza di rumore additivo
-L’algoritmo IRLS è il migliore per quanto riguarda correttezza e prestazioni, tuttavia
presenta l’handicap dell’elevato costo computazionale (scarsa efficienza)
-L’algoritmo-H presenta il minore costo computazionale, a discapito delle prestazioni
-L’approssimazione Spatial Coherence risulta essere un buon compromesso
La scelta dell’algoritmo da utilizzare dipende
dal tipo di rumore e dalle risorse computazionali
Caso A - rumore gaussiano
Caso B - rumore non gaussiano
Caso C - performance
Caso D - efficienza
IC a norma pesata
Funzione di errore robusta
IC-IRLS
IC-IRLS Spatial Coherence