Operatori noti per la stima del moto

(1)

Capitolo 2

Operatori noti per la stima del moto

2.1 Introduzione

La stima del moto su una sequenza di immagini è una problematica di grande interesse nell’ambito della robotica, dell’automazione e della diagnostica medica; per capire gli usi che possiamo farne basti pensare al monitoraggio del traffico o all’inseguimento di particolari pattern in una catena di produzione automatizzata, applicazioni che sfruttano algoritmi di stima del moto per rilevare il movimento di un qualsiasi oggetto.

In ambito medico tale tecnica può trovare impiego, oltre alla ricostruzione panoramica, nel monitoraggio delle pareti della arteria brachiale o della carotide, rilevando addirittura movimenti non stimabili ad occhio nudo.

Dal 1980 ad oggi sono stati presentati molti metodi per il calcolo dei vettori di moto, tutti riscontrabili in letteratura sotto la voce optical flow; quello che si va cercando infatti è l’insieme dei vettori di moto relativi a ciascun punto dell’immagine. Tale insieme descrive quindi l’evoluzione temporale dell’immagine stessa, il suo flusso ottico.

2.2 Il problema dell’apertura

Ogni algoritmo di stima del moto, così come accade nella visione umana, è soggetto ad un errore di valutazione dello spostamento di oggetti se siamo in presenza del cosiddetto problema dell’apertura.

(2)

figura 5: il problema dell’apertura (1/2)

In figura 5 viene illustrato un piano ideale (in grigio) sul quale è stata realizzata una apertura rettangolare; dietro al piano è presente un oggetto rettangolare (in nero) del quale è visibile solo la zona esposta tramite l’apertura mentre della parte coperta si indica solo il contorno con la linea tratteggiata.

La situazione di partenza (A) mostra che lo spigolo in basso a sinistra dell’oggetto si trova nel punto ( , )x y mentre la situazione (B) mostra che l’oggetto si è spostato nel ₀ ₀ punto ( , )x y ; osservando lo spostamento attraverso l’apertura, in particolare ₁ ₀ concentrandoci nel punto evidenziato dal cerchio, l’occhio umano non è capace di percepire lo spostamento avvenuto: il problema dell’apertura consiste proprio in questo. Notare invece le due seguenti situazioni, alternative alla (B), da relazionare quindi con (A):

figura 6: il problema dell’apertura (2/2)

Nel passaggio A Æ B1 possiamo rilevare uno spostamento lungo y ma non lungo x, mentre in A Æ B2 si evidenzia invece uno spostamento in entrambe le direzioni.

(3)

Si capisce allora che in certe condizioni l’occhio umano, e di conseguenza gli algoritmi di stima del moto, non ha sufficienti informazioni per rilevare correttamente lo spostamento.

2.3 L’ optical flow

“L’optical flow è la distribuzione delle velocità apparenti del movimento del pattern dell’intensità di un’immagine […], di conseguenza, l’optical flow fornisce importanti informazioni sulla posizione degli oggetti visti in un’immagine e sul cambiamento di tale posizionamento”

Questa definizione è stata data da Horn & Schunck nel 1980 nel loro articolo “Determining Optical Flow”, che rappresenta il punto di partenza per lo studio e la realizzazione di metodi per la stima del campo degli spostamenti data una coppia di immagini.

Ricaviamo ora l’equazione fondamentale per il calcolo dell’optical flow, la gradient constraint equation.

Gradient Constraint Equation

Siano date un’immagine I e una funzione ( , )f x t che ne descriva l’intensità dei livelli di grigio in ogni suo punto; il vettore

x y   =     x

indica un punto nello spazio bidimensionale dell’immagine, descritto dalle coordinate

( )

x y . ,

Supponiamo che l’intensità dell’immagine non cambi nel tempo (soggetto tempo invariate), ipotesi esprimibile come

( , ) 0 df t dt ≈ x (2.1)

(4)

( )

,

(

, ,

)

f x t ≈ f x dx y dy t dt+ + + (2.2)

espandendo in serie di Taylor la parte destra dell’uguaglianza:

( )

,

( )

, f f f ( ) f t f t x y t O f x y t ∂ ∂ ∂ ≈ + ∂ + ∂ + ∂ + ∂ ∂ ∂ x x (2.3)

semplificando e trascurando i termini di ordine superiore si ottiene

( , ) ( , ) ( , ) 0 f t x f t y f t x t y t t ∂ ∂ ₊∂ ∂ ₊∂ ₌ ∂ ∂ ∂ ∂ ∂ x x x (2.4) definendo poi ( , ) x f t f x ∂ = ∂ x , f_y f( , )t y ∂ = ∂ x , f_t f( , )t t ∂ = ∂ x , u x t ∂ = ∂ , y v t ∂ = ∂ possiamo riscrivere l’equazione come:

0 x y t f u+ f v+ f = (2.5) ovvero ( , ) _t( , ) 0 f t f t ∇ x ⋅ +h x = (2.6) dove ( , ) ( , ) ( , ) T x y f _f _t _f _t f t f x y   ∂ ∂  ∇ =_{ } =_ _ ∂ ∂     x x x , u v   =     h

La (2.6) rappresenta la gradient constraint equation, che chiameremo anche “equazione fondamentale dell’optical flow”.

(5)

Quello che dobbiamo risolvere è quindi un sistema con due incognite ma una sola equazione; se ne deduce che la sola (2.6) non è sufficiente a calcolare l’optical flow, serve quindi una seconda condizione.

L’equazione necessaria alla soluzione del problema può essere ricavata facendo una ulteriore ipotesi sulle caratteristiche del moto.

Possiamo ad esempio imporre un vincolo di smoothness sul campo degli spostamenti (Horn & Schunck), oppure ipotizzare che il vettore h sia costante all’interno di un intorno di dimensioni e forma arbitrari centrato sul punto di applicazione del vettore spostamento (Lucas & Kanade); altre condizioni possono essere trovate andando a lavorare nel dominio della frequenza (Fleet & Jepson) (Heeger).

In alternativa possiamo basarci sul confronto tra porzioni di immagini consecutive, cercando lo spostamento come punto in cui si ottiene il miglior matching tra due aree, chiamate blocchi (Block Matching).

Di seguito vengono presentati e descritti i modelli più importanti, dei quali verrà data una classificazione iniziale in base al metodo di analisi e al contenuto informativo analizzato, per poi passare alla descrizione dell’idea e alla formulazione dell’algoritmo.

2.4 Metodi Gradient Based

I metodi gradient-based calcolano l’insieme dei vettori velocità tramite derivate spazio-temporali delle immagini o di una loro versione filtrata (LP o BP).

La soluzione del problema si ottiene applicando l’equazione fondamentale dell’optical flow in un dominio Θ della mappa dei livelli di grigio

f

( , )

x

t

dell’immagine I .

E’ quindi necessario imporre dei vincoli su Θ per ottenere una seconda condizione utile a risolvere il sistema a due incognite; tra i vari metodi presenti in letteratura, riportiamo quelli di Horn & Schunck e di Lucas & Kanade.

(6)

Metodo di Horn & Schunck

Il metodo proposto da Bertold K.P. Horn e Brian G.Schunck parte dall’equazione fondamentale

( , ) _t( , ) 0

f t f t

∇ x ⋅ +h x =

affiancata da un vincolo di smoothness sul campo delle velocità; si assume infatti che in un’immagine in movimento, il vettore velocità in ogni singolo punto non differisca molto dai suoi vicini.

Un modo per esprimere tale vincolo è quello di limitare la differenza tra ciascun vettore e la media dei suoi vicini presi in un intorno di dimensioni arbitrarie: l’ipotesi è tanto più valida quanto più l’intorno è piccolo.

Dominio continuo

Dato un punto p ed un suo intorno Θ possiamo definire due funzioni u x y e

( )

, v x y

( )

, che descrivono le due componenti del campo delle velocità in ogni

( )

x y, ∈Θ ; i Laplaciani di u x y e

( )

, v x y sono dati da:

( )

,

2 2 2 2 2 u u u x y ∂ ∂ ∇ = + ∂ ∂ , 2 2 2 2 2 v v v x y ∂ ∂ ∇ = + ∂ _∂

e possono essere approssimati con:

(

)

2_u _{u u}

∇ ≈ − , _{∇ ≈}2_v

(

_{v v}₋

)

con u e v calcolati nell’intorno di p; u e v sono in realtà una notazione semplificata per u x y e

( )

, v x y , così come nel caso di

( )

, f , _x f e _y f . _t

(7)

b f ux f vy ft ε = + + (2.7) eq. fondamentale

(

) (

2

)

2 2 c u u v v ε = − + − (2.8) vincolo di smoothness

Pensando già all’applicazione del metodo su immagini campionate, a causa del rumore e dell’errore di quantizzazione, non possiamo attribuire a queste due quantità lo stesso peso, quindi si introduce fin da ora un coefficienteα.

L’errore totale è quindi:

2 2 2 2

b c

ε =ε +α ε (2.9)

Eguagliando a zero le derivate rispetto a u e v :

(

)

(

)

2 2 2 u u 2 f u_x f v_y f f_t _x 0 u ε _α ∂ _{= −} ₋ ₊ ₊ ₊ ₌ ∂ (2.10)

(

)

(

)

2 2 2 v v 2 f u_x f v_y f f_t _y 0 v ε _α ∂ _{= −} _{− +} ₊ ₊ ₌ ∂ (2.11) e risolvendo per u e v :

(

)

(

)

2 2 2 2 2 y x x x t x y f u f f v f f u f f α α + − − = + + (2.12)

(

)

(

)

2 2 2 2 2 y x x y t x y f v f f u f f v f f α α + − − = + + (2.13)

La soluzione del problema quindi consiste nelle due funzioni u x y e

( )

, v x y ,

( )

, componenti del campo dei vettori di moto dell’immagine, che minimizzano il funzionale errore ε .

(8)

Dominio discreto

Consideriamo una sequenza di immagini campionate, ciascuna rappresentata da una matrice, ed indichiamo con f _{i j k}_{, ,} il livello di grigio in posizione

( )

i j della , k esima− immagine della sequenza.

Per il calcolo delle derivate della funzione si consideri la configurazione di fig. 7

figura 7: configurazione per il calcolo dei gradienti

dove il passo degli indici

( )

i j dipende dal campionamento dell’immagine mentre il , passo di k dipende dal frame rate della sequenza.

Basandosi su questa configurazione si possono stimare i gradienti relativi al punto centrale del cubo fatto dalle otto misure mediando sugli elementi vicini:

f_x ≈

{

f_{i j}_, ₊_1,_k − f_{i j k}_{, ,} + f_i₊_1,_j₊_1,_k− f_i₊_{1, ,}_{j k}+ f_{i j}_, ₊_1,_k₊₁− f_{i j k}_{, ,} ₊₁+ f_i₊_1,_j₊_1,_k₊₁− f_i₊_{1, ,}_{j k}₊₁

}

f_y ≈

{

f_i₊_{1, ,}_{j k} − f_{i j k}_{, ,} + f_i₊_1,_j₊_1,_k − f_{i j}_, ₊_1,_k+ f_i₊_{1, ,}_{j k}₊₁− f_{i j k}_{, ,}₊₁+ f_i₊_1,_j₊_1,_k₊₁− f_{i j}_, ₊_1,_k₊₁

}

(2.14)

f_t ≈

{

f_{i j k}_{, ,}₊₁− f_{i j k}_{, ,} + f_i₊_{1, ,}_{j k}₊₁− f_i₊_{1, ,}_{j k}+ f_{i j}_, ₊_1,_k₊₁− f_{i j}_, ₊_1,_k + f_i₊_1,_j₊_1,_k₊₁− f_i₊_1,_j₊_1,_k

}

(9)

(

)

2 , , , , i j k i j k u γ u u ∇ ≈ − , 2

(

)

, , , , i j k i j k v γ v v ∇ ≈ − (2.15)

calcolati pesando ancora i punti vicini secondo questa configurazione:

figura 8: configurazione per il calcolo di ui j k, , e vi j k, ,

{

}

{

}

, , 1, , , 1, 1, , , 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 1 6 12 i j k i j k i j k i j k i j k i j k i j k i j k i j k u = u₋ +u ₊ +u₊ +u ₋ + u₋ ₋ +u₋ ₊ +u₊ ₊ +u₊ ₋ (2.16)

{

}

{

}

, , 1, , , 1, 1, , , 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 1 6 12 i j k i j k i j k i j k i j k i j k i j k i j k i j k v = v₋ +v ₊ +v₊ +v ₋ + v₋ ₋ +v₋ ₊ +v₊ ₊ +v₊ ₋ (2.17)

dove il fattore di proporzionalità γ è pari a 3 se la media è calcolata come in figura 8. Gli autori riportano una soluzione iterativa di tipo Gauss-Seidel:

1 2 2 2

(

)

x x n y n t n n x y

f f u

f v

f

u

f

α

+

=

−

+

(2.18) 1 2 2 2

(

)

y x n y n t n n x y

f f u

f v

f

v

f

α

+

= −

+

(2.19)

(10)

Metodo di Lucas & Kanade

Consideriamo una funzione ( )f x che descrive la mappa dei livelli di grigio di una immagine in una certa posizione; chiamiamo ( )g x la funzione associata alla stessa immagine ma in una posizione diversa; consideriamo infine un intorno Θ di dimensione arbitraria.

Il metodo proposto da Bruce D. Lucas e Takeo Kanade consiste nel calcolo del vettore h che soddisfi, all’interno del dominioΘ , la relazione:

( ) ( )

f x h+ =g x (2.20)

figura 9

Affrontiamo la descrizione del metodo nel caso monodimensionale, in cui ( )f x e ( )g x sono funzioni ad una sola variabile; dalla soluzione è possibile poi generalizzare al caso n-dimensionale (in particolare al caso bidimensionale).

Caso monodimensionale

Le ipotesi che stanno alla base di questo metodo sono:

1) la funzione ( )f x ha un comportamento approssimativamente lineare nell’intorno del punto x

2) la funzione f x( )∈C₂

3) tutti i punti appartenenti a Θ sono soggetti allo stesso spostamento (ipotesi tanto più vera quanto più Θ è piccolo)

(11)

figura 10

Sotto queste condizioni è possibile scrivere (in particolare per h piccolo):

( ) ( ) ( ) ( ) ( ) '( ) df x f x h f x g x f x f x dx h h + − − = ≈ = (2.21) da cui ( ) ( ) '( ) g x f x h f x − = (su

{

x f x: '( ) 0≠

}

) (2.22)

Tenendo presente la prima ipotesi possiamo dire che h rimane approssimativamente costante in un intorno del punto x in cui la funzione ha un comportamento quasi lineare; per ottenere una stima migliore dello spostamento posso calcolarlo su tutti i punti x appartenenti a Θ per poi fare un’operazione di media:

' ' ( ) ( ) '( ) 1 x x g x f x f x h ∈Θ ∈Θ − =

∑

con Θ = Θ' I

{

x f x: '

( )

≠0

}

(2.23)

Notare che l’ipotesi (3) è fondamentale per includere nel calcolo tutti i punti diΘ ; questo avrà maggior peso nel caso bidimensionale.

(12)

La prima delle ipotesi viene meno all’aumentare di

| "( ) |

f x

; questo ci suggerisce di usare questa quantità come peso nel calcolo della media:

'( ) '( ) "( ) g x f x f x h − = (2.24)

Consideriamo quindi una funzione ( )w x che esprime il peso di ciascun punto all’interno del dominio, inversamente proporzionale a

f x

''( )

1 1 ( ) | '( ) '( ) | ''( ) w x g x f x f x = ∝ − (2.25)

In queste condizioni ci possiamo aspettare che l’operazione di media riporti risultati più accurati.

Il valore di h può quindi essere ottenuto, considerando anche la funzione peso, come

' ' ( )[ ( ) ( )] '( ) ( ) x x w x g x f x f x h w x ∈Θ ∈Θ − ≈

∑

(2.26)

La soluzione proposta dagli autori segue un metodo iterativo del tipo Newton - Raphson

0 " 1 " 0 ( )[ ( ) ( )] '( ) ( ) k x k k k x h w x g x f x h f x h h h w x ∈Θ + ∈Θ =   ₋ ₊   ₊  ₌ ₊ 

∑

con Θ = Θ" _I

{

x f x h: '

(

+ _k

)

≠0

}

(2.27)

Derivazione alternativa della soluzione

(13)

( ) ( ) '( ) g x f x h f x − =

Il problema di questa espressione è che per '( ) 0f x = , h non è definito; nel caso precedente infatti è stato necessario ridefinire Θ in modo da avere h ben definito; è opportuno quindi formulare la risoluzione in modo differente.

Considerando lo sviluppo in serie di Taylor della funzione (f x h+ ) arrestato al primo ordine

( ) ( ) '( )

f x h+ ≈ f x +hf x (2.28)

il valore di h può essere trovato minimizzando la norma L della differenza tra le curve, ₂ cercando quindi una soluzione ai minimi quadrati:

2 [ ( ) ( )] x f x h g x ε =

∑

_∈Θ + − (2.29) minimizzando si ottiene 2 0 _x [ ( )f x hf x'( ) g x( )] _x 2 '( )[ ( )f x f x hf x'( ) g x( )] h h ε ∈Θ ∈Θ ∂ ∂ = = + − = + − ∂ ∂

∑

(2.30) da cui: 2 '( )[ ( ) ( )] '( ) x x f x g x f x h f x ∈Θ ∈Θ − ≈

∑

(2.31)

Notiamo che in questo caso il problema della definizione di h è meno sentito in quanto, avendo al denominatore una sommatoria, l’unico caso in cui h non è definito è quello in

(14)

cui '( ) 0f x = in ogni punto di Θ , mentre avere '( ) 0f x = in alcuni punti soltanto non comporta nessun problema.

Notare che '( ) 0f x = in ogni punto del dominio indica una porzione di immagine con intensità costante: in questa condizione ha senso avere h non definito poiché andiamo a scontrarci con il problema dell’apertura, in quanto non possiamo affermare nulla riguardo al moto di una regione ad intensità costante; non avendo infatti nessuna feature da individuare nelle due funzioni non possiamo stimare il movimento.

Anche in questa seconda formulazione, gli autori propongono una soluzione di tipo iterativo: 0 1 2 0 ( ) '( )[ ( ) ( )] ( ) '( ) k k x k k k x h w x f x h g x f x h h h w x f x h ∈Θ + ∈Θ =   ₊ ₋ ₊  ₌ ₊  ₊ 

∑

(2.32) dove: ( ) 1 | '( ) '( ) | w x g x f x = − Caso bidimensionale

Passando al caso bidimensionale dobbiamo definire

x y   =     x , u v   =     h , f_x f( ) x ∂ = ∂ x , f_y f( ) y ∂ = ∂ x , f_t g x

( )

f x

( )

f( ) t ∂ = − ≈ ∂ x 1

Riprendendo l’equazione fondamentale dell’optical flow possiamo scrivere:

(

)

2 x y t f u f v f ε ∈Θ =

∑

+ + x (2.33)

(15)

che equivale alla (2.29) per il caso bidimensionale; definendo:

( )

2 _, xx x f = f x y , 2_{( , )} yy y f = f x y

possiamo ricavare le due componenti di h che minimizzano ε

(

)

(

)

2 2 2 0 2 0 x y t x x x y x t x y t y x y y y t f u f v f f f u f f v f f u f u f v f f f f u f v f f v ε ε ∈Θ ∈Θ ∈Θ ∈Θ ∂ = + + = + + = ∂ ∂ = + + = + + = ∂

∑

x x x x (2.34)

ed enunciare infine la soluzione del problema in forma matriciale come segue:

xx x y x t x y yy y t f f f f f u v f f f f f ∈Θ ∈Θ ∈Θ ∈Θ ∈Θ ∈Θ         _{= −}     _{ }          

∑

x x

∑

x x x x (2.35)

riconducibile alla forma: A⋅ = −h b ; risolvendo: _h_{= −}_A−1_{b .}

Anche in questa formulazione si cerca la convergenza di h ad un valore che minimizza l’errore quadrato tramite un processo iterativo:

0 1 1 0 k k A − + =   ₌ ₋  h h h b (2.36)

Più avanti verranno discusse in modo più approfondito le caratteristiche di questo modello, evidenziando l’importanza dell’iteratività.

2.5 Metodi Matching Based

I metodi Matching Based partono da un’idea molto semplice: sfruttare un criterio di similitudine (matching) tra una o più regioni (blocchi) di ciascun fotogramma con regioni

(16)

corrispondenti del fotogramma successivo per stabilire la nuova posizione del blocco considerato e quindi il suo spostamento. Approfondiamo l’idea di base formalizzando il metodo.

Data una sequenza di fotogrammi, consideriamone due successivi: ( , )f x y e_i f_i₊₁( , )x y ; supponiamo di essere in presenza di moto traslatorio puro, cerchiamo quindi un vettore

( , )dx dy =

d tale che f_i₊₁(x dx y dy+ , + )= f x y_i( , ) per ogni ( , )x y , inoltre supponiamo che la sequenza per piccoli intervalli di tempo possa essere considerata tempo invariante, ovvero che il suo contenuto informativo non cambi nel tempo.

Vogliamo quindi trovare le componenti ( , )dx dy del vettore di moto.

L’idea allora è questa:

consideriamo, in ( , )f x y un certo numero di blocchi, ovvero parti del fotogramma _i racchiuse da un contorno rettangolare o quadrato

consideriamo le coordinate ( , )x y per ciascun blocco, ad esempio quelle dell’angolo _i _i in alto a sinistra

prendiamo poi le stesse coordinate ( , )x y sul fotogramma successivo, _i _i f_i₊₁( , )x y , e intorno a queste consideriamo un’area di dimensioni maggiori rispetto al blocco chiamata scan area

muoviamo il blocco considerato in ogni possibile posizione all’interno della scan area per ogni posizione assunta dal blocco andiamo a valutare un criterio di matching tra

il blocco stesso e l’area sottostante

una volta fatta la valutazione su tutti i punti della scan area andiamo a considerare la posizione che ha dato il miglior matching; chiamando questo punto (x_i₊₁,y_i₊₁), la soluzione del mio problema sarà:

(

dx dy,

) (

xi+1 x yi, i+1 yi

)

= = − −

(17)

I parametri su cui possiamo intervenire utilizzando questo metodo sono:

Criterio di matching Indichiamo con:

- B h k l’intensità del livello di grigio del blocco nella posizione

( )

,

( )

h k , - f h k l’intensità del livello di grigio del frame nella posizione

( )

,

( )

h k , - ,H L le dimensioni del blocco

- 1 1 0 0 1 ( , ) H L h k B B h k HL − − = =

=

∑∑

il valor medio della intensità dei livelli di grigio sul blocco

- 1 1 0 0 1 ( , ) H L h k f f h k HL − − = =

(18)

-

(

m n la posizione del frame sulla quale vado a posizionare il blocco per calcolare il ,

)

parametro di matching; tale posizione è relativa all’angolo in alto a sinistra del blocco

Mean Squared Error (MSE)

(

)

1 1

(

( )

(

)

2 0 0 1 , H L , , h k MSE m n B h k f m h n k HL − − = = =

∑∑

− + +

Mean Absolute Error (MAE) – Mean Absolute Difference (MAD)

(

)

1 1

( )

(

)

0 0 1 , H L , , h k MAE m n B h k f m h n k HL − − = = =

∑∑

− + +

Sum of Absolute Differences (SAD)

(

)

1 1

( )

(

)

0 0 , H L , , h k SAD m n − − B h k f m h n k = = =

∑∑

− + + Correlation Coefficient (CC)

(

)

(

( )

)

(

)

( )

(

)

(

)

1 1 0 0 2 1 ₂ 1 0 0 , , , , , H L h k H L m n B h k B f m h n k f m n B h k B f m h n k f ρ − − = = − − = = − + + − = − + + −

∑∑

∑

Dimensioni dei blocchi

Le dimensioni dei blocchi devono essere un compromesso tra quantità di informazione necessaria e complessità computazionale, infatti blocchi troppo piccoli forniscono troppa poca informazione mentre blocchi troppo grandi aumentano la complessità computazionale

Dimensione della scan area

Le dimensioni della scan area devono essere stabilite sulla base delle ipotesi sul moto in analisi, tenendo in conto anche il peso computazionale.

(19)

Con una scan area troppo piccola infatti riduco il numero di operazioni ma rischio di non includere il punto che rappresenta lo spostamento, viceversa sono quasi certo di includere la posizione che indica lo spostamento ma aumento il numero di operazioni.

Posizionamento dei blocchi

I punti, e quindi i blocchi, dei quali si vuol calcolare lo spostamento possono essere scelti sulla immagine secondo una configurazione prefissata; così facendo però rischiamo di considerare alcuni (se non tutti) blocchi contenenti poca informazione (o al limite nessuna), ad esempio nel caso di immagini con zone prevalentemente omogenee.

Possiamo però scegliere il posizionamento analizzando l’immagine ed individuando dei punti chiave che possano aiutare a ridurre l’errore: possiamo ad esempio posizionarci in corrispondenza di discontinuità dei livelli di grigio (punti di edge).

Questa considerazione, fatta a proposito del block matching, vale per ogni modello di stima del moto e riguarda la selezione di particolari feature sulla immagine.

Posizionamento della scan area

Possiamo pensare di posizionare la scan area centrata sul punto

(

x y_i, _i

)

2_{, in modo da non} privilegiare nessuna direzione di spostamento rispetto alle altre; possiamo però pensare di aumentare la scan area nella direzione del punto che si presume possa rappresentare quello a miglior matching; sostanzialmente, se ci accorgessimo che la storia del moto, fatta su un certo numero di coppie di fotogrammi precedenti a f x y indica una certa _i

( )

, direzione privilegiata, si può pensare di ampliare la scan area in quella direzione, così da concentrare il calcolo in una zona che si presume possa includere il punto cercato con maggior probabilità

Posizionamento dei blocchi nella scan area

Una volta considerato il blocco di f x y e posizionata la scan area in _i

( )

, f_i₊₁

( )

x y, , dobbiamo muovere il blocco nella area suddetta; la prima cosa che viene in mente è di fare uno spostamento “pixel per pixel”, ovvero muovere il blocco all’interno dell’area in tutte le possibili posizioni, scorrendo quindi i pixel riga per colonna; così facendo siamo

(20)

sicuri che, prima o poi, se l’area è sufficientemente grande e l’immagine non è rumorosa , troveremo lo spostamento corretto.

Otteniamo così una funzione bidimensionale definita nel dominio della scan area che esprime l’andamento del criterio di matching: un esempio classico è la funzione SAD

(Sum of Absolute Differences) della quale si cerca il punto di minimo (MSAD), come

illustrato in figura:

figura 11: andamento teorico della SAD

(21)

Da questo possiamo pensare che per cadere nel punto di minimo non è necessario percorrere tutte le possibili posizioni, possiamo invece percorrere una strada passo per passo, in cui si va a valutare il matching in un insieme ristretto di punti secondo una certa configurazione e spostarsi quindi solo sui punti che presentano un matching migliore dei precedenti.

2.6 Algoritmi di Block Matching

Vengono ora analizzati alcuni tra i principali algoritmi di block matching nella loro formulazione base (senza trattare eventuali modifiche); in letteratura si trovano infatti moltissime tecniche di block matching, molte delle quali sono soltanto piccole varianti rispetto alle altre. Presentiamo quindi solo alcune tra le principali, delle quali è possibile dare un riferimento in letteratura.

Full search (FS)

Letteralmente significa ricerca esaustiva, ad indicare la completa scansione di ogni possibile posizione del blocco alla ricerca di quella che fornisce una stima migliore dello spostamento effettivo.

Usando il MSE come criterio di matching possiamo esprimere il metodo come

(

)

(

)

₍ ₎

(

)

( )

)

( ) 1 1 ₂ 1 , 0 0 _, min , min , , s s H L i i m n h k _{m n} MSE m n − − f₊ m h n k B h k ∈Θ = = _∈Θ   = _ + + − _ 

∑∑



usando invece la SAD si ha

(

)

(

)

₍ ₎

(

)

( )

( ) 1 1 1 , ₀ ₀ , min , min , , s s H L i i m n _h _k m n SAD m n − − f₊ m h n k B h k ∈Θ ₌ ₌ ∈Θ   = _ + + − _ 

∑∑



(22)

Si va quindi a cercare l’errore minimo sottraendo e sommando pixel a pixel le intensità dei livelli di grigio tra il blocco selezionato al frame precedente B ed il frame attuale _i

1

i

f₊ .

Si capisce subito che questo algoritmo teoricamente fornisce risultati molto buoni in termini di stima del moto poiché provando tutte le possibili posizioni del blocco sicuramente troviamo quella che fornisce un matching perfetto: questo è vero in assenza di rumore e per posizioni che non risentono del problema dell’apertura, entrambe condizioni che portano a risultati errati.

figura 13: algoritmo FS

Basandosi su una ricerca fatta su ogni possibile posizione, questo algoritmo fornisce risultati che in letteratura vengono presi come valore di riferimento nel confronto con altri algoritmi di block matching; nel seguito vi faremo riferimento nella descrizione di varianti del full search dove si impiegano diverse strategie di ricerca del punto a miglior matching, con il solo scopo di ridurre il numero di operazioni necessarie.

(23)

Complessità computazionale

Consideriamo in questo caso, e in tutti i successivi, la SAD come criterio di matching; definiamo poi:

H_block, L_block: dimensioni del blocco H_frame, L_frame: dimensioni dell’immagine

H_{scan area}_{_} , L_{scan area}_{_} : dimensioni dell’area di scansione step : valore iniziale della distanza tra i punti ₀

Per ogni punto, per il calcolo di una SAD , le operazioni da fare sono: H_block⋅L_block somme

H_block⋅L_block differenze H_block⋅L_block valori assoluti

Nella notazione usata, con il termine SAD si fa riferimento all’insieme di queste operazioni.

Nell’algoritmo FS allora le operazioni richieste per il calcolo dello spostamento in un punto sono:

_ _

scan area scan area

H ⋅L ⋅SAD

Three step search (TSS)3

Questo algoritmo consente una implementazione semplice, robusta, e conduce a risultati vicini a quelli del full search. E’ del tipo coarse to fine, ovvero parte da una stima rozza per poi affinarla, passo dopo passo.

Può essere riassunto nei seguenti passi:

(24)

si sceglie un numero intero che rappresenta lo step iniziale; si considera poi un punto ed i suoi otto circostanti posizionati ad una distanza pari allo step. Si ottengono quindi nove punti totali sui quali si va a calcolare il matching

tra i nove punti, quello in cui viene riscontrato il miglior matching diventa il punto centrale per il passo successivo; si dimezza quindi lo step e si vanno a considerare nuovamente otto punti intorno a questo nuovo centro, questa volta distanziati di step/2 ciascuno

si procede in questo modo finché non si ottiene uno step = 1; il punto in cui si ha il miglior matching nell’ultimo passo dell’algoritmo è considerato il punto che meglio indica lo spostamento

In figura è riportato un esempio di esecuzione dell’algoritmo TSS (ogni quadrato rappresenta un pixel)

figura 14: algoritmo TSS

Dovendo ad ogni passo bisezionare lo step, per non avere problemi di arrotondamento si ipotizza di partire da valori che sono potenze di 2: in questo modo il numero di iterazioni che si hanno dividendo ogni volta lo step sono pari alog₂

(

step₀

)

+ , considerando che 1 l’ultima iterazione si fa per step = 1.

(25)

(

)

2 0

9 log⋅ _ step +  ⋅1_ SAD

Two dimensional Logarithmic search (TDL)

Questo algoritmo riprende in alcuni punti il TSS, anche se fornisce risultati più accurati del precedente, usando però un numero di passi maggiore.

Può essere descritto come:

si sceglie uno step iniziale; si considera un punto a partire dal quale si considerano i punti posti a croce rispetto a quest’ultimo, ciascuno ad una distanza pari allo step. Su ciascun punto si calcola il matching

se il punto in cui si rileva miglior matching è quello centrale, si dimezza lo step e si va avanti

se il punto in cui si rileva il miglior matching non è quello centrale, si assume questo come nuovo punto centrale e si considerano ancora i quattro punti circostanti, senza dimezzare lo step; si va quindi avanti finché non si verifica il miglior matching sul punto centrale della configurazione corrente, dopodiché si procede con l’algoritmo quando si ha step = 1 si considera una configurazione a nove blocchi (quello centrale

e gli otto circostanti, come nel TSS) e su questi si calcola il matching; il punto in cui si ha miglior matching corrisponde al punto che meglio approssima lo spostamento

(26)

figura 15: algoritmo TDL

Per calcolare le operazioni necessarie al calcolo di un vettore, vista la descrizione dell’algoritmo, si ipotizza di riscontrare il miglior matching nel punto centrale alla seconda iterazione, per ogni valore di step: dimezzo quindi il passo ogni due iterazioni, finché non è unitario.

Sotto questa ipotesi le operazioni da compiere sono (tenendo presente i punti in cui la SAD si calcolerebbe due volte):

(

)

(

)

2 0 2 0

8SAD_log step  +_ 8SAD=8SAD_log step + 1_ Binary search (BS)

L’idea di fondo consiste nel suddividere il frame in un numero di regioni ed effettuare una ricerca esaustiva solo all’interno di queste regioni.

L’algoritmo può essere descritto come:

si considera il punto centrale del frame assieme ai nove punti circostanti di questi punti si sceglie quello cui corrisponde il miglior matching

(27)

suddividiamo il frame in regioni di dimensione prefissata attorno a ciascuno dei nove punti considerati; si esegue una ricerca esaustiva solo all’interno della regione relativa al punto che presenta miglior matching

il nuovo punto a miglior matching rappresenta la miglior approssimazione dello spostamento

figura 16: algoritmo BS

Per indicare le operazioni necessarie si ipotizza di fare la scansione esaustiva su un’area che ha dimensioni dimezzate rispetto a quelle date dal full search: questo ha senso dal momento che una prima informazione sul posizionamento della scan area si ha dal matching sulle 9 posizioni iniziali, quindi possiamo permetterci di ridurre l’area di ricerca.

Le operazioni sono quindi 9 SAD iniziali più la ricerca esaustiva nella zona ricavata:

_ _ _ _

9 9

2 2 2 2

scan area scan area scan area scan area

H L H L

SAD+ ⋅ SAD SAD= _ + ⋅ _

(28)

Four step search (FSS)

Anche in questo caso si parte da una configurazione a nove punti, per poi scegliere i successivi secondo il criterio ora descritto:

si fissa uno step iniziale pari a 2; si calcola il matching sulla configurazione a nove punti centrata sul frame. Se il punto a miglior matching corrisponde al centro dell’area di ricerca, si dimezza lo step e si ripete la ricerca come sopra, altrimenti si procede come segue:

si muove il centro verso il punto con miglior matching, si mantiene a 2 lo step. Il passo successivo dipende ora dalla posizione del punto a miglior matching:

o se il punto è posizionato in uno dei “vertici” della configurazione, si considerano cinque punti intorno a quest’ultimo e su questi si calcola il matching

o se il punto è invece uno dei quattro restanti, posizionato quindi lungo la direzione verticale od orizzontale rispetto a quello centrale, si considerano tre ulteriori punti esterni lungo una linea parallela a quella su cui giace il punto in questione; anche su questi viene calcolato il matching.

trovato il punto con miglior matching, se questo è al centro, si dimezza lo step e si procede come da capo, altrimenti si calcola il matching su ulteriori punti aggiuntivi; lo step quindi viene dimezzato solo nel caso in cui il punto ottimale sia nel centro della configurazione “quadrata” attuale, ovvero quella sotto esame passo per passo

(29)

figura 17: algoritmo FSS

Anche in questo caso si fanno le stesse ipotesi fatte per l’algoritmo TDL, ovvero si biseziona ogni due iterazioni:

(

9SAD+5SAD

)

⋅log (2 step0) 9+ SAD

Orthogonal search algorithm (OSA)

L’idea consiste in un susseguirsi di passi lungo direzioni ciascuna ortogonale alla precedente, cercando ogni volta il miglior matching.

Può essere descritto così:

si sceglie uno step iniziale e si considera il punto centrale della finestra e i 2 punti nella direzione orizzontale distanziati da questo di una quantità pari allo step, si calcola il matching e si assume come nuovo centro il punto a miglior matching

si dimezza lo step e si procede allo stesso modo ma nella direzione ortogonale alla precedente

(30)

figura 18: algoritmo OSA

Complessità computazionale: 3SAD+2SAD

[

log (₂ step₀) 1+

]

One at a time algorithm (OTA)

L’idea alla base di questo algoritmo consiste in due scansioni separate, orizzontale e verticale, al fine di trovare in modo veloce la miglior approssimazione dello spostamento; si procede in questo modo:

si considera il punto centrale della finestra di scansione e i suoi due punti adiacenti a destra e sinistra (tre punti in totale) e si calcola il matching

se il punto a miglior matching è quello centrale, si ripete quanto detto al punto precedente ma questa volta lungo al direzione verticale della finestra di ricerca

se il punto a miglior matching non è quello centrale, si considerano i due punti adiacenti a quello ottimale (quindi si considera un solo punto in più) e si va avanti così finché non si verifica che il punto ottimale è quello centrale; sostanzialmente mi sposto verso la direzione di miglior matching

(31)

figura 19: algoritmo OTA

Questo algoritmo richiede pochissimi passi per convergere alla soluzione, però le prestazioni non sono molto buone.

In questo caso non sappiamo quanti passi sono necessari per convergere alla soluzione; poniamoci allora nel caso peggiore di scansione dell’intero frame, supponendo che la ricerca orizzontale porti dal punto centrale fino all’ultimo punto a destra della immagine, mentre quella verticale porti da quest’ultimo punto fino alla prima riga della immagine stessa.

(

)

2 2 2 frame frame frame frame H L SAD SAD SAD H L ⋅ + ⋅ = +

Cross Search Algorithm (CSA)

L’idea di fondo consiste in una ricerca che privilegia le direzioni ortogonali, concludendo la ricerca con un affinamento lungo la diagonale su cui giace presumibilmente il punto a miglior matching; si descrive con:

(32)

si fissa uno step iniziale; si considera poi il punto centrale della finestra e su questo si costruisce una X, considerando quindi quattro punti circostanti a formare un quadrato il cui lato è doppio dello step. Su questi calcolo il matching e assumo come nuovo centro quello ottimale

dimezzo lo step e ripeto quanto detto al punto precedente finché lo step risulta > 1 se ho step = 1 distinguo due situazioni diverse:

o il punto ottimale del passo precedente è quello alto a destra o basso a sinistra (entrambi lungo la stessa diagonale) si affina la ricerca considerando anche i quattro punti messi a croce intorno a questo punto, con step unitario

o il punto ottimale del passo precedente è quello in alto a sinistra o in basso a destra (anch’essi sulla stessa diagonale) si affina la ricerca considerando anche i quattro punti messi a X intorno a questo punto, con step unitario Il motivo per cui si opera in questo modo è legato all’idea di privilegiare la direzione della diagonale “da cui stiamo arrivando”, ovvero quella lungo cui giaceva il punto precedente all’ultimo step; questo perché essendosi sempre mosso lungo direzioni diagonali, è ragionevole pensare che quella sia la direzione a miglior matching, quindi quella da affinare all’ultimo passo.

(33)

Complessità computazionale: 5SAD+4SAD⋅ _log₂

(

step₀

)

+ 1_

Grafichiamo le curve della complessità computazionale al variare delle dimensioni del blocco:

IPOTESI

- il valore assoluto ha un peso confrontabile con somme e sottrazioni - Hblock = Lblock

- Hframe = Lframe = 256 [pixel] - step0 = 4 [pixel]

- Hscan_area = Lscan_area = Hblock + 10

2 4 6 8 10 12 14 16 18 20 0 0.5 1 1.5 2 2.5 3x 10 4

dimensioni dei blocchi [pixel]

nu m er o d i o per az io ni FS TSS TDL BS FSS OSA OTA CSA

2.7 Risultati sperimentali

Vengono ora riportati i risultati ottenibili dall’implementazione di alcuni degli algoritmi sopra descritti; si riporta il numero di frames utilizzati, il valore del parametro di matching medio (AMAD) ed il tempo di calcolo della CPU.

I valori presentati sono stati tratti dall’articolo “Search Algorithms for Block-Matching in Motion Estimation”.

(34)

Lo standard CIF (Common Intermediate Format) prevede una risoluzione di 352x288 pixel mentre il QCIF (Quarter Common Intermediate Format) prevede una risoluzione di 176x144 pixel.

Sequenza N° frames Algoritmo AMAD CPU time (s) fps

Children QCIF 10 FS 6.824 47.32 0.2113 TSS 8.414 1.73 5.78 TDL 9.272 0.6 16.67 FSS 8.638 1.04 9.615 OTA 9.0315 0.49 20.408 OSA 8.714 0.99 10.10 Weather QCIF 10 FS 2.5 47.94 0.020 TSS 2.776 1.8 5.55 TDL 3.005 0.56 17.857 FSS 2.827 1.0 10 OTA 2.895 0.39 25.64 OSA 2.808 1.00 10 CoastGuard QCIF 300 FS 3.511 ND ND TSS 3.758 62.5 4.8 TDL 6.500 20.99 14.292 FSS 3.675 41.83 7.171 OTA 3.791 17.07 17.574 OSA 3.7957 36.59 8.2 Akiyo QCIF 300 FS 0.4695 1546.19 0.194 TSS 0.6177 61.70 4.862 TDL 0.6374 20.13 14.903 FSS 0.6177 35.19 8.525 OTA 0.6178 14.51 20.675 OSA 0.6179 36.46 8.228 Carphone QCIF 382 FS 3.337 ND ND TSS 3.677 78.93 4.84 TDL 4.3747 29.11 13.123 FSS 3.6670 51.86 7.36

(35)

OTA 3.883 21.03 18.16 OSA 3.7686 47.18 8.1 Container CIF 300 FS ND ND ND TSS 1.686 267.81 1.12 TDL 1.692 87.97 3.41 FSS 1.688 151.62 1.97 OTA 1.689 58.99 5.08 OSA 1.6864 152.07 1.97 MaD CIF 300 FS ND ND ND TSS 1.616 267.7 1.12 TDL 6.500 20.99 14.29 FSS 1.58 169.04 1.77 OTA 1.644 62.42 4.81 OSA 1.644 152.46 1.96

I parametri interessanti della tabella sono il valore della AMAD ed il numero di frame al secondo (fps).

Il valore della AMAD ci dice, mediamente, quanto è stato il valore della MAD calcolata su tutti i punti usati per la ricerca; essendo la MAD un parametro di matching da minimizzare, un valore piccolo di AMAD indica una certa efficacia nella ricerca dei punti a miglior matching, a parità di immagine.

Sebbene i valori riportati siano un po’ datati (l’articolo di riferimento risale al 1998) ne risulta comunque interessante il confronto dal momento che il parametro AMAD è indipendente dalla tecnologia, a differenza del CPU time e del frame-rate; è comunque ragionevole aspettarsi gli stessi rapporti in termini di prestazioni, anche su un hardware di ultima generazione.

Dalla tabella, comunque, emergono le elevate prestazioni in termini di qualità del metodo FS, accompagnate però da un alto CPU time; subito dopo vengono il TSS ed il FSS, che forniscono risultati molto buoni in termini di errore.

Escludendo quindi la full search per un’implementazione real time, tra tutti gli algoritmi proposti emergono come ottimo compromesso tra prestazioni e tempo di calcolo il metodo TSS e l’FSS.