3 - Sistema per la stabilizzazione di flussi video.

3 - Sistema per la stabilizzazione di flussi

video.

Il sistema studiato per la stabilizzazione di flussi video provenienti da una videocamera è composto di tre macro-funzioni:

1. Stima del movimento.

2. Interpretazione dei movimenti per ricavare il moto della telecamera. 3. Eliminazione dei movimenti non voluti.

Per ciascuna di queste funzioni sono stati studiati algoritmi che consentano si svolgere nel miglior modo possibile la funzione desiderata.

3.1 - Algoritmi per la stima del movimento.

In letteratura sono numerosi gli articoli e i libri che spiegano come ricavare da una sequenza video i movimenti della videocamera. La stima del moto, nella maggior parte dei casi, viene calcolata analizzando due immagini vicine all’interno di una sequenza video. Questa operazione molto complessa computazionalmente deve essere svolta in tempo reale, in modo tale che il processo di stabilizzazione risulti il meno possibile in ritardo rispetto alla scena reale.

Per capire se c'è stato uno spostamento della telecamera da un frame a quello successivo, è necessario confrontare tra loro i due frame per capire Illustrazione 3 1: Diagramma generale del sistema per la stabilizzazione di flussi video.

se ci sono delle differenze. Il confronto o matching tra le due immagini può essere fatto in molti modi, per esempio effettuando una sottrazione pixel per pixel di una immagine rispetto alla successiva[13]. Teoricamente se le due immagini fossero identiche il risultato della differenza tra pixel nella stessa posizione risulterebbe nullo. Questo è ovviamente un caso limite, ma in generale è possibile capire se un frame si è spostato rispetto al precedente, semplicemente effettuando una sottrazione pixel per pixel tra le due immagini. In questo modo però, a meno che le immagini siano identiche, si riesce soltanto a capire se c'è stato uno spostamento oppure no. Per riuscire a individuare la direzione dello spostamento è necessario effettuare più confronti tra le due immagini: in particolare per riuscire a ricavare lo spostamento orizzontale si dovranno effettuare molti confronti shiftando le immagini orizzontalmente l'una rispetto all'altra. Se, per esempio, le immagini sono composte da n x m pixel, per ricavare lo spostamento orizzontale si devono confrontare volta per volta le due immagini spostando l'immagine attuale o corrente di un pixel. È necessario considerare che, se le due immagini hanno le stesse dimensioni, spostando una immagine rispetto all'altra, una parte di queste non è compresa nel confronto e quindi non deve essere considerata. Lo stesso procedimento deve essere effettuato anche in verticale per ricavare lo spostamento in questa direzione. Una volta effettuati tutti i confronti si ricava l'intensità, la direzione e il verso dello spostamento.

Un alternativa a questo metodo consiste nel dividere l'immagine di riferimento in molti blocchi e di effettuare confronti con una immagine successiva o corrente suddivisa in aree di ricerca, centrate sui blocchi dell'immagine di riferimento. Per ogni blocco dell'immagine di riferimento, si calcola lo spostamento che questo ha subito rispetto all’immagine successiva. Effettuando confronti tra sezioni di due immagini sequenziali si riesce solamente ad individuare lo spostamento bidimensionale di un blocco rispetto ad un altro. Quindi se si effettuasse l’operazione di

confronto fra due immagini complete, senza la separazione in blocchi, si riuscirebbe soltanto a ricavare una trasformazione bidirezionale dell’immagine su di un piano. In questo modo si ottiene un unico vettore, detto vettore di movimento, che da informazioni sulla traslazione rigida dell’immagine. La suddivisione dell’immagine in molti blocchi consente di calcolare localmente, per ogni regione del frame, il vettore di moto ad esso associato. Il risultato finale è quello di ottenere una stima del movimento locale dell’immagine. Partendo da queste informazioni è possibile ricavare, non solo una traslazione rigida dell’immagine su di un piano, ma anche una trasformazione in tre dimensioni: la ricostruzione del movimento nello spazio della telecamera. Al tempo stesso, però, questa tecnica comporta qualche svantaggio. Infatti a parità di dimensione dell’immagine, avere un grande numero di vettori significa suddividere in blocchi piccoli l’immagine e quindi, limitare il confronto tra blocchi di piccole regioni dell’immagine. In questo modo è più probabile che il confronto sia affetto da errori, perché si confrontano meno pixel tra loro e quindi è più probabile che i blocchi delle immagini si assomiglino molto. I movimenti veloci della telecamera comportano un grande spostamento di un’immagine rispetto ad un'altra. Se il movimento è abbastanza rapido, è possibile che il blocco di riferimento si sposti rispetto alla sua posizione originaria di una distanza in pixel maggiore della dimensione del blocco su cui si effettua il confronto. Quindi non si riesce ad ottenere un matching tra le due regioni; per meglio dire, qualsiasi algoritmo studiato troverebbe un vettore di moto, ma questo sarebbe il risultato del confronto tra due blocchi completamente differenti. Questo risultato è equivalente ad un errore, cioè un vettore di movimento totalmente casuale.

Un altro problema dovuto alla suddivisione dell’immagine in tanti piccoli blocchi deriva dal fatto che il vettore spostamento di ogni sezione può essere distorto a causa del movimento locale di oggetti, anche piccoli, nell’immagine. Si rischia di interpretare spostamenti di oggetti, non

appartenenti allo sfondo, come movimenti di tutta l’immagine, degradando la stima del movimento globale e peggiorando quindi la stabilizzazione.

Non bisogna dimenticare che avere più sezioni e quindi più vettori di spostamento, significa avere molti più dati da elaborare e conseguentemente una maggiore complessità dell’algoritmo in termini di calcolo.

La scelta della dimensione dei blocchi in cui deve essere divisa l’immagine è una scelta di compromesso tra la volontà di avere molti blocchi per riuscire a ricostruire lo spostamento dell’immagine in tre dimensioni e la necessità di avere dei confronti non casuali tra blocchi. In particolare risulta molto importante riuscire a capire quanto si può spostare al massimo un pixel rispetto ad un altro per i movimenti della telecamera. Purtroppo questa informazione deve essere stimata in modo empirico e, in generale, dipenderà dalla velocità con cui si muove l’operatore che fa muovere la videocamera.

La dimensione tipica dei blocchi per la codifica MPEG è di 16 x 16 pixel, infatti in questo modo si ottengono (720 / 16 = 45 e 576 / 16 = 36) 45 x 36 stime dello spostamento.

Nella scelta delle dimensioni dei blocchi è necessario riuscire ad ottenere una buona accuratezza dei vettori di movimento assieme a una complessità accettabile del calcolo dell’algoritmo. Risulta necessaria una scelta di compromesso:

● blocchi di piccole dimensioni, come quattro pixel per lato, riducono

l’accuratezza dei vettori di moto: a parità di finestra di ricerca, si confrontano meno pixel dell’immagine di riferimento;

● utilizzare blocchi di piccole dimensioni rispetto alla finestra di ricerca

consente di ottenere vettori di spostamento più grandi e quindi capaci di seguire grandi variazioni tra le due immagini;

questi sono di grandi dimensioni;

● usare aree di ricerca piccole rispetto al blocco di riferimento riduce il

numero di confronti da effettuare e quindi riduce la complessità di calcolo dell’algoritmo.

Nel caso in esame è stata data come specifica la dimensione minima di un vettore di spostamento e successivamente si è scelta la dimensione delle finestre di ricerca. Il limite consiste in un vettore di movimento che deve avere dimensioni maggiori di 50 pixel, che corrispondono a uno spostamento maggiore del 5% e minore del 10% rispetto alle dimensione di una immagine. Uno spostamento di tale entità tra una immagine e la sua successiva, continuato nel tempo, significa che immagini distanti poco più di mezzo secondo sono completamente differenti: non hanno più niente in comune. L'occhio umano non è in grado di seguire variazioni così veloci e per questo si è scelto di porre 50 pixel come limite, sotto il quale non è opportuno scendere. Infatti per riuscire a eliminare spostamenti tanto grandi o veloci, è necessario prima di tutto riuscire a riconoscerli. Tutti gli spostamenti dell'immagine con dimensioni maggiori di quella massima del vettore di spostamento, non vengono riconosciuti; quindi se si presentasse uno spostamento tanto grande tra due immagini, i vettori di moto trovati non corrisponderebbero più alla realtà, ma sarebbero del tutto casuali. Il risultato è uno spostamento casuale dell'immagine senza riuscire ad eliminare i movimenti voluti.

Per i motivi spiegati è necessario valutare la scelta della dimensione dei blocchi in funzione del particolare algoritmo da applicare per il confronto. Esistono molti algoritmi, più o meno complessi, che permettono di individuare i vettori di moto. Analizziamo alcuni criteri di confronto per il calcolo dei vettori di movimento.

3.1.1 - SAD: Somma di Differenze in valore Assoluto.

L’algoritmo SAD, cioè Sum of Absolute Differences[14], propone di calcolare il vettore di spostamento cercando il minimo della differenza tra due punti di immagini sequenziali, confrontando il blocco di riferimento con tutti i blocchi dell'area di ricerca. Il blocco che ha tale differenza in valore assoluto, minore di tutti gli altri, restituisce la posizione del vettore di moto tramite gli indici i, j:

∑ ∑

₌− ₌− + + − + + + + = 1 0 1 0 M k N l l) j k,y i R(x l) k,y C(x SAD(i,j)

dove R(x+k+i,y+l+j) è l’immagine di riferimento e C(x+k,y+l) è l’immagine corrente o di ricerca; M x N è la dimensione dell’immagine o del blocco[15]. Solitamente si confronta il blocco di riferimento con una immagine corrente che ha dimensioni maggiori rispetto a quelle di riferimento. Se immaginiamo di prendere un blocco di ricerca in modo tale che circondi l’immagine di riferimento di p pixel; si ottiene che, con questo algoritmo, per ogni pixel dell’immagine di riferimento si devono effettuare

2

1 2 p )

( ⋅ + confronti. La complessità dell’algoritmo e data da N

M ) p

(₂⋅ + ₁ 2⋅ ⋅ _{confronti, dove per confronto si intendono le operazioni di}

sottrazione, modulo e somma. Questo è un metodo molto costoso in termini computazionali, ma assicura di trovare il vettore di spostamento più corretto. Infatti nessun pixel viene tralasciato e quindi il minimo dell’algoritmo SAD può essere assoluto.

Nella ricerca del minimo del SAD non ci possono essere errori perché si confrontano tutti i pixel dell'area di ricerca con il blocco di riferimento, senza tralasciarne nessuno. Di fatto questo algoritmo trova lo spostamento in una regione ampia (2⋅ p+ 1) x (2⋅ p+ 1) pixel. Questo significa che utilizzando una finestra corrente larga N e un blocco di riferimento di lato L, le componenti del vettore spostamento non possono essere maggiori di N-L. Il vettore spostamento è calcolato rispetto al

centro della finestra di dimensioni (2⋅ p+ 1) x (2⋅ p+ 1).

R R R R

Best match

In realtà gli indici dei pixel delle immagini considerano le immagini come se appartenessero al semi-quadro positivo, ma per semplicità si è soliti considerare il vettore spostamento rispetto al centro del blocco. È necessaria una traslazione dell’origine per allineare il centro della finestra all’origine delle coordinate cartesiane.

(-p,p) (0,p) (p,p) (-p,0) (0,0) (p,0) (-p,-p) (0,p) (p,-p) 2p+1 u p p p p

Illustrazione 3 2: Nella figura è rappresentato un blocco con p = 3 al cui centro si trova l’immagine di riferimento composta da quattro pixel R.

Illustrazione 3 3: Traslazione degli indici i, j in funzione del centro dell'immagine.

3.1.1.1 - Valutazione dell'algoritmo SAD.

Dalle specifiche del progetto si ricava che è necessario riuscire a determinare spostamenti molto grandi dell'immagine di riferimento. Questa condizione del sistema obbliga ad utilizzare blocchi riferimento molto più piccoli rispetto all'area di ricerca su cui vengono calcolati i confronti. In questo modo, però, per calcolare il valore del SAD(i,j) sono necessarie molte più operazioni matematiche.

Per eseguire i calcoli in tempi brevi, vi sono due possibili soluzioni: effettuare operazioni matematiche in parallelo o in serie.

Effettuando operazioni matematiche in parallelo, si riesce a calcolare il valore della sommatoria del SAD per un generico blocco (i,j), in tempo reale; dove per “in tempo reale” si intende negli istanti successivi all'arrivo del pixel dell'immagine corrente e prima del pixel successivo. Ma questo significa che, all'interno della FPGA, devono essere programmate più strutture identiche che eseguono la stessa funzione. Quindi si rischia di riuscire a calcolare il valore del SAD in tempo reale, ma di occupare tutte le risorse hardware della FPGA.

Viceversa, se si vuole risparmiare risorse hardware sulla FPGA, è necessario implementare su di essa un numero esiguo di elementi che effettuano operazioni matematiche e utilizzarli ciclicamente per il calcolo delle sommatorie. Con questo procedimento, però, dato che l'elemento per il calcolo del SAD(i,j) è utilizzato più volte e per più somme parziali è necessario memorizzare i dati parziali delle sommatorie. Inoltre, questo metodo, assicura di riuscire a trovare il risultato delle somme parziali in tempo reale, se si riesce a eseguire un numero di operazioni abbastanza elevato prima che arrivi il pixel successivo dell'immagine corrente. Ma, per riuscire a effettuare più operazioni nello stesso periodo di tempo, senza la moltiplicazione delle risorse hardware, è necessario utilizzare una frequenza di clock più alta e una quantità maggiore di memoria.

quasi sempre dei dati, infatti la sommatoria si estende per un numero di righe equivalente a quelle del blocco di riferimento. Quindi è necessario ricordare il risultato parziale della sommatoria per più righe di una immagine.

L'algoritmo SAD, per come è realizzato, si presta bene all'implementazione con risorse in parallelo per il calcolo degli elementi della sommatoria. Infatti è possibile realizzare più strutture parallele per il calcolo della sommatoria delle differenze in valore assoluto.

Un metodo per organizzare i calcoli delle somme dell'algoritmo SAD è quello di implementare sulla FPGA tante strutture hardware che calcolano la somma delle differenze tra pixel in valore assoluto, quanto il risultato della sottrazione tra le dimensioni dell'area di ricerca e il blocco di riferimento. Per esempio, se si dovesse effettuare una ricerca su di un'area di 8 x 8 pixel con un blocco di riferimento di 4 x 4 pixel, sarebbero necessari 5 elementi che effettuano la somma di differenze in valore assoluto tra pixel. Quindi, in generale, per calcolare il valore del SAD(i,j) in tempo reale, sono necessari un numero di elementi che calcolino la somma di differenza in valore assoluto pari alla differenza, in pixel, tra l'area di ricerca e il blocco di riferimento. Per calcolare tutti i valori del SAD in tempo reale è necessario calcolare 2p+1 volte in parallelo il valore del SAD(i,j). In questo modo si ottengono i valori dell’algoritmo SAD in uscita in tempo reale.

Per realizzare questo metodo di organizzare i calcoli sono necessari più elementi che eseguono calcoli in parallelo. A ogni elemento arriva in ingresso sia il pixel dell'immagine corrente necessario al calcolo del SAD(i,j), sia quello di riferimento. Questo significa che ogni elemento calcola uno specifico valore del SAD(i,j), quindi gli devono essere forniti soltanto i pixel dell'immagine corrente che servono al calcolo del particolare valore SAD(i,j). Successivamente effettua la differenza e il modulo tra i due pixel. Quindi si somma il risultato con quelli

precedentemente calcolati, appartenenti al particolare valore SAD(i,j), utilizzando un accumulatore.

Un singolo elemento permette di calcolare soltanto un unico valore SAD(i,j). Per riuscire a calcolare in tempo reale tutti i valori del SAD, mentre il decoder video sta trasmettendo i dati dell'area di ricerca, è necessario utilizzare più elementi in parallelo. Inoltre si può notare che i pixel necessari al calcolo del primo valore del SAD(i,j) sono necessari anche al calcolo del secondo valore del SAD(i,J+1): i pixel dell'immagine corrente arrivano regolarmente dal decoder e per questo devono essere selezionati a seconda a quale elemento servono; i pixel dell'immagine di riferimento, invece, devono essere recuperati dalla memoria, quindi per ridurre il numero di accessi alla memoria è possibile propagare l'arrivo dei dati di riferimento a tutti i blocchi, utilizzando dei registri che ritardino il dato.

INGRESSI Elemento1 Elemento2 Elemento3 Elemento4 Elemento5 CLK Corr. Rif. 0 c(0,0) r(0,0) |c(0,0)-r(0,0)| 1 c(0,1) r(0,1) |c(0,1)-r(0,1)| |c(0,1)-r(0,0)| 2 c(0,2) r(0,2) |c(0,2)-r(0,2)| |c(0,2)-r(0,1)| |c(0,2)-r(0,0)| 3 c(0,3) r(0,3) |c(0,3)-r(0,3)| |c(0,3)-r(0,2)| |c(0,3)-r(0,1)| |c(0,3)-r(0,0)| 4 c(0,4) |c(0,4)-r(0,3)| |c(0,4)-r(0,2)| |c(0,4)-r(0,1)| |c(0,4)-r(0,0)| 5 c(0,5) |c(0,5)-r(0,3)| |c(0,5)-r(0,2)| |c(0,5)-r(0,1)| 6 c(0,6) |c(0,6)-r(0,3)| |c(0,6)-r(0,2)| 7 c(0,7) |c(0,7)-r(0,3)| a c(1,0) r(1,0) |c(1,0)-r(1,0)| a+1 c(1,1) r(1,1) |c(1,1)-r(1,1)| |c(1,1)-r(1,0)| a+2 c(1,2) r(1,2) |c(1,2)-r(1,2)| |c(1,2)-r(2,1)| |c(1,2)-r(1,0)| a+3 c(1,3) r(1,3) |c(1,3)-r(1,3)| |c(1,3)-r(2,2)| |c(1,3)-r(1,1)| |c(1,3)-r(1,0)| a+4 c(1,4) |c(1,4)-r(1,3)| |c(1,4)-r(1,2)| |c(1,4)-r(1,1)| |c(1,4)-r(1,0)| a+5 c(1,5) |c(1,5)-r(1,3)| |c(1,5)-r(1,2)| |c(1,5)-r(1,1)| a+6 c(1,6) |c(1,6)-r(1,3)| |c(1,6)-r(1,2)| a+7 c(1,7) |c(1,7)-r(1,3)| b c(2,0) r(2,0) |c(2,0)-r(2,0)| b+1 c(2,1) r(2,1) |c(2,1)-r(2,1)| |c(2,1)-r(2,0)| b+2 c(2,2) r(2,2) |c(2,2)-r(2,2)| |c(2,2)-r(2,1)| |c(2,2)-r(2,0)| b+3 c(2,3) r(2,3) |c(2,3)-r(2,3)| |c(2,3)-r(2,2)| |c(2,3)-r(2,1)| |c(2,3)-r(2,0)| b+4 c(2,4) |c(2,4)-r(2,3)| |c(2,4)-r(2,2)| |c(2,4)-r(2,1)| |c(2,4)-r(2,0)| b+5 c(2,5) |c(2,5)-r(2,3)| |c(2,5)-r(2,2)| |c(2,5)-r(2,1)| b+6 c(2,6) |c(2,6)-r(2,3)| |c(2,6)-r(2,2)| b+7 c(2,7) |c(2,7)-r(2,3)| c c(3,0) r(3,0) |c(3,0)-r(3,0)| c+1 c(3,1) r(3,1) |c(3,1)-r(3,1)| |c(3,1)-r(3,0)| c+2 c(3,2) r(3,2) |c(3,2)-r(3,2)| |c(3,2)-r(3,1)| |c(3,2)-r(3,0)| c+3 c(3,3) r(3,3) |c(3,3)-r(3,3)| |c(3,3)-r(3,2)| |c(3,3)-r(3,1)| |c(3,3)-r(3,0)| c+4 c(3,4) |c(3,4)-r(3,3)| |c(3,4)-r(3,2)| |c(3,4)-r(3,1)| |c(3,4)-r(3,0)| c+5 c(3,5) |c(3,5)-r(3,3)| |c(3,5)-r(3,2)| |c(3,5)-r(3,1)| c+6 c(3,6) |c(3,6)-r(3,3)| |c(3,6)-r(3,2)| c+7 c(3,7) |c(3,7)-r(3,3)| sommo i tutti i termini della colonna: sommo i tutti i termini della colonna: sommo i tutti i termini della colonna: sommo i tutti i termini della colonna: sommo i tutti i termini della colonna:

SAD(i,0) SAD(i,1) SAD(i,2) SAD(i,3) SAD(i,4)

funzione dei cicli di clock per un blocco di riferimento (Rif. nella tabella) di 4 x 4 pixel e una immagine corrente (Corr. nella tabella) di 8 x 8 pixel. Le caselle grigie nella tabella indicano le zone dove il calcolo si ferma fino a che non è terminato l’invio dell’intera riga dell’immagine, da parte del decoder[15].

È possibile pre-caricare i blocchi di riferimento e i risultati parziali della sommatoria nella memoria interna della FPGA. Ma, quest’ultima operazione, deve essere valutata in modo molto accurato, infatti la memoria interna della FPGA ha dimensioni ridotte e non è detto che l’inserimento dei dati in memoria consenta la ricerca dei vettori di moto in tempo reale. Inoltre se si utilizza le memoria interna per memorizzare i dati intermedi è molto difficile che possa contenere anche tutti i blocchi di riferimento. L'uso della memoria interna alla FPGA è comunque necessario perché la memoria esterna non riesce a lavorare con frequenza di clock molto alte e quindi recuperare tutte le informazioni necessarie per il calcolo dei vettori di moto da essa, significherebbe collassare le vie di comunicazione con essa soltanto per il calcolo del SAD e non dare la possibilità agli altri elementi del sistema di poter accedere ad essa.

Una volta calcolati i valori j del SAD(i,j) per tutti gli elementi di una riga, è necessario calcolare il minore tramite un confronto. Il valore minimo dell’algoritmo SAD di una riga sarà memorizzato e successivamente utilizzato per calcolare il minimo assoluto dell’algoritmo, cercando il minimo tra i valori delle righe. Per avare il minimo su tutte le righe è sufficiente utilizzare il solito schema, variando semplicemente i dati della immagine corrente.

L’elemento raffigurato nell’immagine sovrastante evidenzia come viene calcolato e strutturato, a livello di macro-blocchi funzionali, un elemento dell’algoritmo SAD[15]. Si mandano i pixel dell’immagine corrente e di quella di riferimento. Ogni elemento sceglie, tramite il blocco di controllo, i pixel dell’immagine di riferimento necessari e calcola il valore assoluto della differenza tra il pixel dell’immagine di riferimento e quello corrente. Si può pensare di porre la logica di controllo anche all’esterno del blocco, in modo tale che si utilizzi un singolo controllo per tutti gli elementi. I pixel dell’immagine di riferimento sono mandati anche ai blocchi successivi, ma ritardati del periodo di un pixel, in modo tale che risultino sincroni con quelli dell’immagine corrente.

Gli elementi descritti devono essere collegati tra loro per riuscire a calcolare in tempo reale il minimo del SAD su di una riga del blocco:

Illustrazione 3 4: Diagramma funzionale di un elemento per il calcolo del SAD.

Collegando insieme gli elementi è possibile ottenere un elemento circuitale che permetta di calcolare in tempo reale tutti i valori del SAD di una riga[15]. Bisogna notare che mentre l'immagine corrente entra in tutti gli elementi, quella di riferimento, che è contenuta in memoria, entra soltanto nel primo elemento per il calcolo e successivamente i dati vengono propagati verso gli altri elementi utilizzando dei blocchi di ritardo.

Per riuscire ad ottenere il vettore di movimento è necessario porre tante strutture, come quella sopra, in parallelo, quante sono il numero di righe su cui si calcola il SAD: 2p+1.

Questo non è il solo modo di ordinare i pixel che permette di calcolare il SAD in tempo reale.

Illustrazione 3 5: Diagramma funzionale di un blocco per il calcolo del SAD, composto da più elementi.

INGRESSI Elemento

1 Elemento2 Elemento3 Elemento4

CLK Corr. Rif. E1 E2 E3 E4 0 c(0,0) r(0,0) |c(0,0)-r(0,0)| 1 c(0,1) r(0,1) |c(0,1)-r(0,0)| |c(0,1)-r(0,1)| 2 c(0,2) r(0,2) |c(0,2)-r(0,0)| |c(0,2)-r(0,1)| |c(0,2)-r(0,2)| Sommatoria: (CLK,E1)+ +(CLK+1,E2)+ +(CLK+2,E3)+ +(CLK+3,E4)+ Parziale Precedente 3 c(0,3) r(0,3) |c(0,3)-r(0,0)| |c(0,3)-r(0,1)| |c(0,3)-r(0,2)| |c(0,3)-r(0,3)| Parziale SAD(i,0) a 4 c(0,4) |c(0,4)-r(0,0)| |c(0,4)-r(0,1)| |c(0,4)-r(0,2)| |c(0,4)-r(0,3)| Parziale SAD(i,1) a 5 c(0,5) |c(0,5)-r(0,1)| |c(0,5)-r(0,2)| |c(0,5)-r(0,3)| Parziale SAD(i,2) a 6 c(0,6) |c(0,6)-r(0,2)| |c(0,6)-r(0,3)| Parziale SAD(i,3) a 7 c(0,7) |c(0,7)-r(0,3)| Parziale SAD(i,4) a a c(1,0) r(1,0) |c(1,0)-r(1,0)| a+1 c(1,1) r(1,1) |c(1,1)-r(1,0)| |c(1,1)-r(1,1)| a+2 c(1,2) r(1,2) |c(1,2)-r(1,0)| |c(1,2)-r(1,1)| |c(1,2)-r(1,2)|

a+3 c(1,3) r(1,3) |c(1,3)-r(1,0)| |c(1,3)-r(1,1)| |c(1,3)-r(1,2)| |c(1,3)-r(1,3)| Parziale SAD(i,0) b

a+4 c(1,4) |c(1,4)-r(1,0)| |c(1,4)-r(1,1)| |c(1,4)-r(1,2)| |c(1,4)-r(1,3)| Parziale SAD(i,1) b

a+5 c(1,5) |c(1,5)-r(1,1)| |c(1,5)-r(1,2)| |c(1,5)-r(1,3)| Parziale SAD(i,2) b

a+6 c(1,6) |c(1,6)-r(1,2)| |c(1,6)-r(1,3)| Parziale SAD(i,3) b

a+7 c(1,7) |c(1,6)-r(1,3)| Parziale SAD(i,4) b

b c(2,0) r(2,0) |c(2,0)-r(2,0)| b+1 c(2,1) r(2,1) |c(2,1)-r(2,0)| |c(2,1)-r(2,1)| b+2 c(2,2) r(2,2) |c(2,2)-r(2,0)| |c(2,2)-r(2,1)| |c(2,2)-r(2,2)| b+3 c(2,3) r(2,3) |c(2,3)-r(2,0)| |c(2,3)-r(2,1)| |c(2,3)-r(2,2)| |c(2,3)-r(2,3)| Parziale SAD(i,0) c b+4 |c(2,4)-r(2,0)| |c(2,4)-r(2,1)| |c(2,4)-r(2,2)| |c(2,4)-r(2,3)| Parziale SAD(i,1) c b+5 |c(2,5)-r(2,1)| |c(2,5)-r(2,2)| |c(2,5)-r(2,3)| Parziale SAD(i,2) c b+6 |c(2,6)-r(2,2)| |c(2,6)-r(2,3)| Parziale SAD(i,3) c b+7 |c(2,7)-r(2,3)| Parziale SAD(i,4) c c c(3,0) r(3,0) |c(3,0)-r(3,0)| c+1 c(3,1) r(3,1) |c(3,1)-r(3,0)| |c(3,1)-r(3,1)| c+2 c(3,2) r(3,2) |c(3,2)-r(3,0)| |c(3,2)-r(3,1)| |c(3,2)-r(3,2)| c+3 c(3,3) r(3,3) |c(3,3)-r(3,0)| |c(3,3)-r(3,1)| |c(3,3)-r(3,2)| |c(3,3)-r(3,3)| SAD(i,0) c+4 |c(3,4)-r(3,0)| |c(3,4)-r(3,1)| |c(3,4)-r(3,2)| |c(3,4)-r(3,3)| SAD(i,1) c+5 |c(3,5)-r(3,1)| |c(3,5)-r(3,2)| |c(3,5)-r(3,3)| SAD(i,2) c+6 |c(3,6)-r(3,2)| |c(3,6)-r(3,3)| SAD(i,3) c+7 |c(3,7)-r(3,3)| SAD(i,4)

Tabella 3: Ordine delle operazioni di modulo di differenze in funzione dei cicli di clock per un blocco di riferimento (Rif. nella tabella) di 4 x 4 pixel e una immagine corrente (Corr. nella

tabella) di 8 x 8 pixel. Le caselle grigie nella tabella indicano le zone dove il calcolo si ferma fino a che non è terminato l’invio dell’intera riga dell’immagine, da parte del decoder. L'ultima colonna della tabella mostra come effettuare la somma per ottenere il valore del SAD(i,j). Di fatto la somma deve essere fatta in diagonale rispetto ai dati nella tabella: si inizia la sommatoria con il dato posto nella colonna E1 e riga CLK=0 e si prosegue con il dato (CLK=1,E2), (CLK=2,E3) e (CLK=3,E4). A questo punto si è ricavato un valore parziale che deve essere memorizzato e recuperato all'inizio della trasmissione della colonna successiva. Qui la sommatoria inizia con il risultato della riga precedente [Parziale SAD(i,0) a] e continua con (CLK=a,E1), (CLK=a+1,E2), (CLK=a+2,E3) e (CLK=a+3,E4). Quindi quando inizia la trasmissione dell'ultima riga si ottengono in uscita i risultati definitivi del SAD(i,j)[15].

Per implementare la tabella sovrastante sulla FPGA occorre modificare l’elemento strutturale e collegare gli elementi in modo diverso:

Illustrazione 3 6: Diagramma funzionale di un elemento per il calcolo del SAD.

A differenza del metodo di ordinamento precedente, a ciascun elemento è assegnato un pixel del blocco di riferimento[15]. Quindi per ogni blocco si ottengono tanti elementi quanti sono i pixel in una riga del blocco di riferimento. Ogni elemento calcola il valore assoluto della differenza di due pixel, addiziona questo risultato alla somma proveniente dal blocco precedente e passa il risultato al blocco successivo. La somma calcolata dall’elemento precedente è passata all’elemento successivo: il primo elemento inizialmente somma a zero, il valore assoluto della differenza tra i due pixel. Successivamente si fa commutare il multiplexer affinché arrivi in ingresso al primo elemento il valore calcolato dall’ultimo. Di fatto questo algoritmo calcola le somme parziali degli elementi che compongono il SAD. Dopo N² somme, dove N è la dimensione del blocco di riferimento (quadrata), l’algoritmo inizia a fornire in uscita i dati dei valori SAD ordinati per riga. Questi valori vengono confrontati gli uni con gli altri in tempo reale e quindi al termine dei calcoli si ottiene il valore minimo dell’algoritmo SAD per il blocco specifico, senza bisogno di ulteriori paragoni. Il primo SAD(i,0) arriva dopo N²-N somme parziali in uscita dall’ultimo blocco. Quindi si confronta questo valore con quello in uscita al Illustrazione 3 7: Diagramma funzionale di un blocco per il calcolo del SAD, composto da più elementi.

ciclo successivo, SAD(i,1) e così via.

Questo modo di ordinare risulta strutturalmente più efficiente rispetto al precedente, nel caso in cui la differenza, in pixel, tra la dimensione del lato dell'area di ricerca e la quella del blocco di riferimento sia più grande delle dimensioni del blocco di riferimento. Infatti nel caso preceente il numero di elementi da dover utilizzare per calcolare il SAD(i,j) di una riga era di 2p+1, mentre nel caso attuale è di N, dimensione del lato del blocco di riferimento. Dalle specifiche di progetto si ricava che N=16 e 2p+1>25 si ricava che è più efficiente l'utilizzo dell'ultimo metodo di organizzazione dei calcoli.

Come nel caso precedente, per riuscire ad ottenere il vettore di movimento voluto in tempo reale, è necessario porre 2p+1 strutture in parallelo. Dove 2p+1 sono le righe su cui si calcola l’algoritmo SAD.

3.1.2 - Algoritmo di ricerca bidimensionale logaritmica

e di ricerca parallela gerarchica.

Gli algoritmi di ricerca bidimensionale logaritmica e di ricerca parallela gerarchica consentono di ottenere il risultato di un confronto con un numero molto inferiore di operazioni perché non sono algoritmi di ricerca completa, cioè non utilizzano tutti i pixel delle due figure per calcolare il vettore di moto.

3.1.2.1 - Algoritmo di ricerca bidimensionale logaritmica.

L’algoritmo di ricerca bidimensionale logaritmica divide l’area di ricerca nell’immagine corrente, di dimensione [-p< x < p],[-p< y < p] in due regioni,

una interna di [-p x p],[-p y p]

2 2

2

2 < < < < e una esterna[15]. Si confronta il punto o blocco (0,0) dell’immagine di riferimento con i pixel sul perimetro

dell’area delimitata da [-p x p],[-p y p]

2 2

2

2 < < < < . I punti scelti per il confronto sono: (0,d1), (0,-d1), (d1,0), (-d1,0), (d1,d1), (d1,-d1), (-d1,d1) e (-d1,-d1). Dove la distanza d1 = 2k−1 con k = log2(p). Si utilizza il metodo SAD

sui punti selezionati per trovare il pixel o blocco che meglio assomiglia a quello dell’immagine di riferimento (0,0). Successivamente si continua la ricerca posizionando il centro (precedentemente il punto (0,0)) nel pixel che rendeva minimo il SAD al passo precedente e si riduce la distanza: da

d1 si passa a

2

1 2

d

d = . La regione di ricerca adesso avrà un lato che è un quarto della precedente, ma si continuano a confrontare 8 punti rispetto a quello centrale. Iterando k volte questo procedimento si arriva a confrontare un pixel o blocco con i pixel o blocchi che lo circondano. Quindi si ricava il vettore di moto voluto, considerando la distanza tra il centro (0,0) e il pixel ottenuto alla fine del processo. La complessità di questo algoritmo è molto minore rispetto a quella dell’algoritmo SAD, infatti si confrontano solo (8⋅



log₂p



+ 1)⋅M⋅ N punti per area di ricerca. Questo metodo richiede molti meno confronti rispetto al metodo completo di ricerca SAD. Non bisogna però scordare che questo algoritmo non assicura di trovare i vettori di moto corretti, perché, non confrontando tutti i pixel dei due blocchi, rischia di fermarsi, nella ricerca del minimo assoluto dell’algoritmo SAD, a dei minimi relativi. Il calcolo dei vettori di movimento è soggetto ad errori che possono essere grandi.

1 1 1

2 2 2

2 1 2 1 1

2 2 2

1 1 1

Illustrazione 3 8: Nella figura sovrastante si utilizza k = 2 e p = 4 per calcolare il vettore di moto. In questo caso, il vettore di moto

sarà uno degli 8 pixel o blocchi denominati con 2.

3.1.2.2 - Algoritmo monodimensionale di ricerca parallela gerarchica.

L’algoritmo monodimensionale di ricerca parallela gerarchica, a differenza dell’algoritmo logaritmico, propone di effettuare una ricerca in parallelo sulle due dimensioni, prese indipendentemente l’una dall’altra[15]. Assumendo come regione di ricerca sulla immagine corrente

p] y p],[-p x

[-p< < < < , e ponendo S = 2(log2p) e prendendo l’origine della

ricerca nel centro dell’immagine di riferimento (x = 0 , y = 0), si calcola in parallelo:

1. il minimo locale sull’asse orizzontale i, utilizzando il metodo SAD su tre punti (i , j), (i-S , j), (i+S , j) con i uguale al valore della x del centro.

2. il minimo locale sull’asse orizzontale j, utilizzando il metodo SAD su tre punti (i , j), (i , j-S), (i , j+S) con j uguale al valore della y del centro.

Dopo aver calcolato in parallelo questi due valori si dimezza S: 2

S

S = e si continua la ricerca spostando il centro nel punto che minimizza il SAD tra i tre punti scelti su ogni asse. Quando si arriva ad avere S = 1, significa che il processo di ricerca è terminato.

Questo metodo utilizza un numero ancora inferiore di punti su cui applicare l’algoritmo SAD: (4⋅



log2p



+ 1)⋅ M⋅ N, ma offre il vantaggio e

svantaggio di limitare la ricerca dei punti su due assi soltanto. In questo modo è sufficiente conoscere soltanto alcune righe e colonne dei due blocchi, rendendo il calcolo molto semplice. Anche in questo caso non si deve dimenticare che la probabilità di trovare dei minimi relativi dell’algoritmo SAD è ancora più alta rispetto al caso precedente.

y1

x2 x1 x2 x1,y1 x1

y2 y1 y2

Illustrazione 3 9: Nella figura sovrastante vengono mostrati i punti utilizzati da questo algoritmo con p = 7. Quelli denominati con 1 appartengono al primo passo, mentre quelli con 2 al secondo. Il pixel o blocco nero è l’ipotetico punto migliore per il matching.

3.1.2.3 - Valutazione dell'algoritmo di ricerca logaritmica e parallela gerarchica.

Nell’algoritmo di ricerca logaritmica e di ricerca parallela si applica l’algoritmo SAD per un numero di punti molto minore rispetto a quanto viene fatto nell’algoritmo puro. I confronti tra blocchi differenti sono realizzati partendo dal centro dell’immagine corrente per poi espandere la ricerca nelle direzioni che minimizzano il SAD. Ma iniziare i confronti partendo dal centro e spostarsi in due direzioni, significa che per effettuare il primo confronto deve essere già stato trasmesso almeno metà blocco. Quindi l’unico modo per memorizzare tanti dati è quello di immagazzinali nella memoria RAM esterna e recuperarli quando è necessario. Il grande limite di questi algoritmi è proprio quello che necessitano che le due immagini siano presenti entrambe in memoria. Quindi l’unico modo per applicare questi algoritmi è quello di riuscire a sfruttare la memoria esterna per recuperare dati appartenenti a pixel non consecutivi.

Nell’algoritmo di ricerca logaritmica, per ogni passo, si calcola il SAD per 9 parti del blocco corrente, rispetto a quello dell’immagine di riferimento che

si suppone disponibile perché pre-caricato nella memoria interna alla FPGA. Terminato il calcolo per i primi nove blocchi, devono essere recuperati altri otto dall'area di ricerca per continuare la ricerca. Di questi pixel non si conosce a priori la posizione: è determinata dal passo precedente. Quindi è necessario riuscire a recuperare almeno otto blocchi dell'immagine corrente per ogni passo della ricerca logaritmica: l’utilizzo della memoria diventa molto intensivo. Il vantaggio risiede nel fatto che la complessità computazionale è molto ridotta perché si deve calcolare il SAD per pochi pixel che devono essere recuperati dalla memoria RAM esterna. Ad ogni passo sono necessari otto nuovi blocchi dell’immagine di ricerca. Anche questi devono essere recuperati dalla RAM esterna.

L’algoritmo di ricerca parallela richiede un numero ancora inferiore di blocchi, su cui calcolare l’algoritmo SAD. Quindi è richiesto un minor uso della memoria esterna.

Questi due algoritmi non consentono di trovare il minimo assoluto del SAD, perché limitano la ricerca ad un numero molto piccolo di pixel rispetto a tutti quelli dell'area di ricerca. Per questo motivo è preferibile implementare questi algoritmi di ricerca solo se è richiesta una bassa complessità dell’hardware e si accetta di ottenere valori, dei vettori di moto, che possono essere poco precisi.

3.1.3 - SAD con sotto-campionamento.

Un metodo alternativo per la riduzione della complessità del calcolo dell’algoritmo SAD consiste nel ridurre le dimensioni dei blocchi, sotto-campionando in modo particolare. In questo modo si ottengono delle immagini di dimensioni minori, ma, se non si effettua un filtraggio preventivo dell'immagine, si escludono dei pixel nella ricerca. Per non eliminare parti dell’immagine, si può pensare di sotto-campionare con una strategia precisa, in modo tale che si riesca comunque a confrontare tutti i

pixel di una immagine, senza effettuare un filtraggio passa basso. Così facendo viene ridotta la complessità computazionale dell’algoritmo senza perdita di informazioni. Per esempio sotto-campionare di fattore due una immagine, significa prendere un pixel ogni quattro, dove i quattro pixel formano un quadrato. 1 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4 1 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4 1 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4 1 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4

Illustrazione 3 10: Schema di sotto-campionamento dei pixel in una parte di immagine. I pixel numerati 1, 2, 3 e 4 indicano l'ordine in cui vengono campionati.

I pixel numerati, come nella illustrazione precedente, indicano l’ordine con cui vengono campionati: si calcola il SAD prima per i pixel chiamati 1, poi per quelli 2, 3 e in fine 4. Con questa strategia di campionamento e associando una opportuna regione di ricerca ad ogni sotto-blocco si riesce a diminuire notevolmente al complessità dell’algoritmo SAD anche del 25%[15].

3.1.4 - SAD con proiezioni laterali.

Un altro approccio per ridurre i pixel nel calcolo dell’algoritmo SAD è quello di formare proiezioni dei blocchi lungo varie direzioni e usare i campioni lungo le proiezioni al posto dei pixel stessi. Ciascun elemento del vettore proiettante della colonna è somma dei pixel, lungo la corrispondente colonna del blocco, divisa per il numero di pixel della stessa. La proiezione della riga è formata nel solito modo. Nel calcolo del

SAD si sostisce la somma valori assoluti di pixel differenti con la somma del valore assoluto delle differenze delle proiezioni delle corrispondenti righe e colonne. Quindi nel calcolo della complessità dell’algoritmo SAD si

sostitusce a M x N il valore approssimato di

N M N M + ⋅ _{[15]. Questo approccio}

richiede solo il 12.5% dei calcoli necessari per la stima dell’algoritmo SAD.

↑

∑

_/N ↑

∑

_/N ↑

∑

_/N ↑

∑

_/N ↑

∑

_/N ↑

∑

_/N ↑

∑

_/N ↑

∑

_/N ←

∑

/N + + + + + + + + ←

∑

/N + + + + + + + + ←

∑

/N + + + + + + + + ←

∑

/N + + + + + + + + ←

∑

/N + + + + + + + + ←

∑

/N + + + + + + + + ←

∑

/N + + + + + + + + ←

∑

/N + + + + + + + +

Illustrazione 3 11: Struttura delle proiezioni dei pixel per il calcolo del SAD considerando soltanto i blocchi in cui vi è il simbolo di sommatoria.

3.1.5 - Algoritmi di ricerca binari.

Gli algoritmi binari effettuano una ricerca completa sui due blocchi delle immagini da confrontare. Anche questi algoritmi confrontano le due immagini pixel per pixel e da questo confronto, che corrisponde a una

operazione logica solitamente poco complessa, ricavano, a differenza degli altri algoritmi di ricerca, un risultato molto semplice: il confronto positivo o negativo. Quindi il confronto ottimo si ottiene quando due immagini hanno il numero più elevato di confronti positivi.

3.1.5.1 - Algoritmo di classificazione binaria della differenza tra pixel.

L’algoritmo BPDC, classificazione binaria della differenza tra pixel, è un metodo per il confronto tra blocchi a bassa complessità. Questo algoritmo si propone di confrontare tutti i pixel dei blocchi dell’immagine di riferimento con quelli del blocco dell’immagine corrente[15]. A differenza dell’algoritmo SAD impone una soglia per effettuare il confronto, in modo tale che non sia necessario confrontare tutti i bit di un generico pixel, ma solo n°bit_pixel − t1 dove t1 = log2t. In questo caso t = 2t1 è la soglia con cui si

valuta il matching tra i pixel.

{

[

]

}

∑ ∑

+ + + + + + = = k l t t j i k l BPDC i j and xnorC x k y l R x k i y l j T_, ( , ) (, ) ₁( , ), ₁( , )

in questa formula Ct1(x+ k,y + l) è il blocco corrente e Rt1(x+ k + i,y+ l + j) è

l’immagine di riferimento. Il pedice t1 indica che si considerano solo )

_

(n°bit pixel− t₁ bit dei pixel di ogni blocco. Se i pixel considerati sono uguali,

viene sommato uno al pixel appartenente a Ti,j(k,l); zero altrimenti. Il pixel che individua il vettore di moto è quello che restituisce il massimo del valore di Ti,j(k,l). Con questo algoritmo si contano i matching tra i pixel usando una soglia:

    ↔ ≤ + + + + − + + ↔ = altrimenti t j l y i k x R l y k x C l k T_{i j} 0 ) , ( ) , ( 1 ) , ( ,

∑ ∑

= k l ij l k T BPDC _, ( , )

caso in cui si calcola il matching con l’algoritmo SAD, proporzionale a t. É necessario valutare in modo accurato la scelta della soglia.

3.1.5.2 - Algoritmo per confronto a livello binario.

L’algoritmo BPROP, criterio di confronto a livello binario, è del tutto simile all’algoritmo precedente; in questo caso però, anziché effettuare una differenza tra i pixel delle due immagini, si effettua uno xor:

[

]

∑ ∑

+ + + + + + = k l t t j l y i k x R l y k x C xor j i BPROP(, ) ₁( , ), ₁( , )

In questo modo il confronto ottimo non si ottiene con il massimo della sommatoria, ma dal minimo. Anche in questo caso è possibile scegliere la soglia[15].

3.1.5.3 - Algoritmo con confronto a livello binario con soglie. L’algoritmo DPC, criterio di calcolo della differenza tra pixel, è una variante dell’algoritmo BPDC, dove si quantizzano i bit dei due blocchi portandoli da m bit a n bit (m > n), utilizzando una soglia. Risultati sperimentali affermano che la quantizzazione a 2 bit di pixel a 8 bit restituisce la migliore scelta di compromesso tra prestazioni e complessità computazionale. Vediamo in che modo avviene la quantizzazione:

quindi si quantizzano C(x+k,y+l) e R(x+k+i,y+l+j) ottenendo rispettivamente Cq(x+k,y+l) e Rq(x+k+i,y+l+j). Si calcola:

      − ≤ ↔ − ≥ > ↔ ≥ > ↔ ≥ ↔ = t l k p t l k p l k p t t l k p l k p_q ) . ( 10 ) . ( 0 11 0 ) . ( 00 ) . ( 01 ) , (

{

[

]

}

∑ ∑

+ + + + + + = k l q q j l y i k x R l y k x C xnor and j i DPC(, ) ( , ), ( , )

dove il vettore di movimento è dato dal massimo valore di DPC(i,j). Infatti questo metodo conta i confronti positivi tra i bit. Il valore della soglia può essere calcolato per ogni blocco:

dove m è il valore medio dei valori dei pixel nel blocco[15].

3.1.5.4 - Algoritmo di confronto con piani di bit.

BPM, criterio di confronto a piano di bit, è un algoritmo che trasforma il frame di riferimento e quello corrente in una immagine di pixel a valore binario.

dove Cb(x+k,y+l) e Rb(x+k+i,y+l+j) sono l’immagine corrente e quella di riferimento dopo che sono state trasformate con pixel a un bit. Il vettore di moto è il valore minimo del BMP(i,j). Un metodo per trasformare una generica immagine F in una immagine a un bit per pixel, è quello di filtrare l’immagine attraverso una matrice K (17 x17) definita:

Il filtraggio è una convoluzione di tale matrice con la matrice dell’immagine F(i,j) per ottenere G(i,j):

Questa operazione di convoluzione espande la matrice G(i,j) fino ad ottenere delle dimensioni pari alla somma delle dimensioni delle metrici che devono essere convolute tra loro. Se per esempio K ∈ (17 x 17) e F ∈

(16 x 16) la matrice risultante G ha dimensioni (33 x 33)[15]. Ma si può

    ↔ ∈ ↔ = altrimenti j i j i K 0 ] 16 , 12 , 8 , 4 , 1 [ ) , ( 25 1 ) , (

∑ ∑

+ ∞ − ∞ = + ∞ − ∞ = − − ⋅ = ⊗ = m n n j m i K n m F j i K j i F j i G(, ) (, ) (, ) ( , ) ( , )

∑ ∑

− = − = − ⋅ ⋅ ⋅ = 1 0 1 0 ) , ( 2 3 M k N l m l k p N M t

[

]

∑ ∑

+

+

+

+

+

+

=

k l b b

j

l

y

i

k

x

Rb

l

y

k

x

C

xor

j

i

BMP

(

,

)

(

,

),

(

,

)

convoluzione K realizza un filtraggio passa alto della intensità dell’immagine e quindi rivela i contorni degli oggetti presenti nella scena. Le parti dell’immagine in cui c’è un rapido cambio di intensità da basso ad alto vengono segnate con un uno nella immagine Fb con tale procedimento:

L’immagine F(i,j) è confrontata con G(i,j) che è la stessa immagine dopo un filtraggio passa alto, allo scopo di ottenere una immagine binaria in cui sono evidenziati i contorni delle figure. In alternativa si può confrontare F(i,j) con il valore medio dell’intensità dei suoi pixel:

Ottenuta la trasformazione dell’immagine nel suo equivalente binario è possibile calcolare il minimo del BPM(i,j). Il grande vantaggio che offre questo algoritmo consiste nel fatto che il confronto tra blocchi risulta molto veloce, ma a suo discapito, c’è il problema di calcolare precedentemente una convoluzione o il valore medio del blocco.

3.1.5.5 - Valutazione degli algoritmi di ricerca binaria.

Nei metodi di confronto binario tra blocchi visti sopra, la stima del moto tra due blocchi è misurata usando una ricerca con pixel a risoluzione completa. Si possono realizzare notevoli miglioramenti se la stima del movimento è realizzata con una immagine binaria del blocco, cioè formata da pixel di 1 bit. Per ottenere questo risultato è necessario che sia l’immagine di riferimento che quella corrente siano trasformate per ottenere pixel a un solo bit. Successivamente si possono applicare le strategie di ricerca del tutto identiche a quelle dell’algoritmo SAD, ma con

   ↔ ≥ ↔ = altrimenti j i G j i F j i F_b 0 ) , ( ) , ( 1 ) , (     ↔ ⋅ ≥ ↔ =

∑ ∑

= = altrimenti N M j i F j i F j i F M i N j b 0 ) , ( ) , ( 1 ) , ( 1 1

il vantaggio che in questo caso il calcolo è molto più semplice perché l’immagine ha dimensioni molto ridotte.

Il primo passo da effettuare è quello di trasformare l’immagine per ottenere pixel con dimensioni di un solo bit. Questa operazione può essere fatta utilizzando una soglia: si confrontano i valori completi dei pixel con un valore soglia. Se il pixel ha un valore di luminanza maggiore della soglia, questo viene trasformato nell’immagine in uscita in un 1 logico. Se invece, ha un valore inferiore viene trasformato in uno zero. Il problema nell’utilizzo di questo metodo sta nel valore soglia. Alcuni algoritmi propongono di utilizzare un valore fisso, invariante rispetto alle immagini, come gli algoritmi BPDC e BPROP. In questi due casi il vettore di movimento sarà calcolato con un errore proporzionale al valore della soglia, quindi per ottenere un vettore di movimento molto preciso si è costretti ad utilizzare tutti i bit di un pixel. Il grande vantaggio rispetto all’algoritmo SAD originale consiste nel fatto che, al posto di dover effettuare il modulo della differenza di due pixel, è sufficiente realizzare uno xor tra i due pixel. Una volta realizzata l’operazione di confronto, si ottiene un risultato binario: 1 se i pixel sono identici, 0 altrimenti. Quindi si eseguono le somme necessarie al calcolo considerando che in ingresso ai sommatori c’è in bit. Calcolare l’algoritmo SAD in questo modo comporta una notevole diminuzione nella complessità strutturale dell’algoritmo.

Negli algoritmi DPC e BPM la soglia varia per ogni immagine o blocco. Nel caso del DPC, la soglia è il risultato della sommatoria del valore assoluto della differenza tra i pixel dell’immagine e il valore medio dell’immagine. Nell’algoritmo BPM, invece, si propone di effettuare un filtraggio passa alto dell’immagine tramite una matrice nota, o più semplicemente confrontando ogni pixel con il valore medio del blocco. Se non si vuole recuperate dalla memoria esterna nessun bit, nessuno di questi metodi è applicabile. Infatti per calcolare la soglia di un blocco, è necessario

conoscerlo tutto e successivamente trasformarlo nel suo corrispondente binario. Quindi appena arriva un blocco si riesce a calcolare la soglia, ma poi deve essere recuperato tutto per riuscire a trasformare il blocco con pixel a valore binario.

Per evitare questo problema si può pensare di utilizzare il valore di soglia calcolato sull’immagine precedente per l’immagine corrente. Se si calcola il valore di soglia semplicemente come la media del valore della luminanza del blocco precedente, questa operazione può essere ritenuta corretta supponendo che non ci siano grandi variazioni di illuminazione tra i due frame. In questo modo ogni volta che arriva un blocco è necessario calcolare il valore medio di quest’ultimo e trasformarlo in un equivalente binario, utilizzando come soglia il valore medio della luminanza del blocco precedente.

Questi metodi non sono altro che un’ottimizzazione dell’algoritmo SAD nel caso in cui si abbiano immagini con pixel di un bit. L’organizzazione dei calcoli è identica a quella utilizzata nell’algoritmo SAD, ma questa volta gli elementi sono molto più semplici da realizzare[15].

Illustrazione 3 12: Elementi per la realizzazione di un confronto binario tra due pixel di immagini differenti.

Anche la struttura di interconnessioni è identica a quella degli elementi per il calcolo del SAD.

Così come nel caso dell’algoritmo SAD c’è un altro modo di organizzare i dati, cambiando la struttura degli elementi[15].

Illustrazione 3 13: Diagramma dei collegamenti degli elementi per il calcolo di confronti binari tra pixel di due immagini.

Illustrazione 3 14: Elementi per la realizzazione di un confronto binario tra due pixel di immagini differenti.

Ottenendo la nota struttura, con i soliti vantaggi rispetto alla precedente.

Con il metodo binario BPM si riesce ad implementare sicuramente il calcolo del vettore di spostamento in tempo reale. La complessità dell’hardware è molto ridotta, quindi si riesce al implementare questo metodo anche sulle FPGA di piccole dimensioni.

Questi algoritmi sono molto efficienti in termini computazionali, ma, anche se utilizzano tutti i pixel dell'area di ricerca, non possono essere paragonati alla certezza che offre il calcolo del SAD. Infatti gli algoritmi di ricerca binaria utilizzano tutti i pixel dell'immagine, ma dopo che questa è stata in qualche modo ridimensionata. Quindi anche se si considerano tutti i pixel, vi è comunque perdita di informazione, perché si trasformano i pixel dell'immagine con un numero minore di bit. Inoltre gli algoritmi binari più raffinati inoltre richiedono un filtraggio o la conoscenza di tutta l'immagine prima di poter iniziare i calcoli, che comporterebbe la necessità di recuperare i pixel per poter effettuare le operazioni successive.

Illustrazione 3 15: Diagramma dei collegamenti degli elementi per il calcolo di confronti binari tra pixel di due immagini.

3.1.6 - Trasformata discreta di Fourier.

Un altro metodo per calcolare il vettore di spostamento tra due blocchi, consiste nello sfruttare le proprietà della trasformata discreta di Fourier[16].

Dato un segnale discreto, f(m) si può ricavare la sua trasformata discreta di Fourier F(k) applicando la seguente trasformazione:

∑

∑

− = ⋅ − = ⋅ ⋅ − ⋅ = ⋅ = 1 0 1 0 2 ) ( ) ( ) ( N m m k N m m k N i W m f e m f k F π ∀k=0, 1, … N-1 con _{W e} i N π 2 ⋅ − =

e viceversa è possibile ricavare f(m) da F(k) dalla formula di inversione:

Esiste un metodo molto veloce per il calcolo di F(k) chiamato trasformata veloce discreta di Fourier ( Fast Fourier Trasform ) che sfrutta le proprietà di W, e la decomposizione binaria degli indici k e m[17][18].

Bisogna notare che Wq = e−i⋅N⋅q

π

2

con q=1, 2, …,N-1 sono le radici n-esime

dell’unità, infatti: ( ) 2 1 2 = = = −i⋅N⋅q⋅N −i⋅ ⋅q N q _{e e} W π π . In particolare prendendo N 2= p si ottiene che se q è multiplo di N, cioè _{q= n⋅2}p_{, allora}

1 2 2 2 2 2 = = = = −i⋅N⋅q −i⋅ ⋅n⋅ −i⋅ ⋅n q _{e e e} W p p _π π π

. Inoltre è possibile decomporre gli indici:

con ( mi , ki )∈ [0,1]. Il prodotto m⋅k può essere scritto come:

∑

− = ⋅ ⋅ ⋅ ⋅ = 1 0 2 ) ( 1 ) ( N k m k N i e K F N m f π 0 1 1 2 2 2 2 1 1 _{2 ... 2 2} 2 m m m m m m p _p p p _{⋅ + ⋅ + + ⋅ + ⋅ +} = − ₋ − − 0 1 1 2 2 2 2 1 1 _{2 ... 2 2} 2 k k k k k k p _p p p _{⋅ + ⋅ + + ⋅ + ⋅ +} = − ₋ − − ) 2 2 ... 2 2 ( ) 2 2 2 2 2 ... 2 2 2 2 ( ... ) 2 2 2 2 2 ... 2 2 2 2 ( ) 2 2 2 2 2 ... 2 2 2 2 ( 0 1 1 2 2 2 2 1 1 0 0 1 1 1 1 2 2 1 2 2 1 1 1 1 1 0 2 1 1 2 2 2 2 2 2 2 1 1 2 2 0 1 1 1 1 2 2 1 2 2 1 1 1 1 1 k k k k k m k k k k k m k k k k k m k k k k k m k m p p p p p p p p p p p p p p p p p p p p p p p p p p p p + ⋅ + ⋅ + + ⋅ + ⋅ ⋅ + ⋅ + ⋅ ⋅ + ⋅ ⋅ + + ⋅ ⋅ + ⋅ ⋅ ⋅ + + ⋅ + ⋅ ⋅ + ⋅ ⋅ + + ⋅ ⋅ + ⋅ ⋅ ⋅ + ⋅ + ⋅ ⋅ + ⋅ ⋅ + + ⋅ ⋅ + ⋅ ⋅ ⋅ = ⋅ − − − − − − − − − − − − − − − − − − − − − − − − − − − −

Di tutti questi termini ne restano molto pochi, infatti tutti quelli multipli di 2p _{possono essere ignorati. Si ottiene quindi:}

e quindi Wm⋅k = Wc0 ⋅Wc1 ⋅...⋅Wcp−1

.

Adesso è possibile esprimere tutto in funzione dei termini mi e ki:

Per ogni componente di F è richiesto il calcolo di p sommatorie, quindi si ricava che il costo computazionale totale richiesto è 2⋅ N⋅log₂N. L’implementazione della FFT si esegue in passi successivi attraverso l’introduzione dei così detti vettori intermedi f(i)_:

Illustrazione 3 16: Visualizzazione grafica del calcolo della trasformata di Fourier dove il primo vettore intermedio diventa argomento della seconda sommatoria per il calcolo del secondo vettore e così via.

∑ ∑ ∑ ∑

_{= = = =} − − − − − − − ⋅ ⋅ ⋅ ⋅ = 1 0 1 1 1 0 1 0 1 2 1 0 0 1 2 1 0 1 2 1 1 1 0 ... ) , ,..., , ( ... ) , ,..., , ( m m m m c c c p p p p p p p W W W m m m m f k k k k F

∑ ∑ ∑ ∑

= = = = − − − − − − − ⋅ ⋅ ⋅ ⋅ = 1 0 1 1 1 0 1 0 1 2 1 0 0 1 2 1 0 1 2 1 1 1 0 ... ) , ,..., , ( ... ) , ,..., , ( m m m m c c c p p p p p p p W W W m m m m f k k k k F 0 0 1 2 2 1 1 1 2 0 2 1 1 1 1 0 1 0 ) 2 ... 2 2 ( ... ) 2 2 ( 2 m k k k k c m k k c m k c p p p p p p p p p ⋅ + ⋅ + + ⋅ + ⋅ = ⋅ ⋅ + ⋅ = ⋅ ⋅ = − − − − − − − − −

Il primo vettore intermedio f(1) _{(calcolato a partire dal vettore f di input)} diventa l’argomento della seconda sommatoria per il calcolo del secondo vettore intermedio f(2) _{e così via.}

...

∑

= − − − − ⋅ = 1 0 1 2 1 0 0 1 2 0 ) 1 ( 1 0 ) , ,..., , ( ) , ,..., , ( p m c p p p m m f m m m m W m k f

∑

= − − − ⋅ = 1 0 1 0 1 2 1 0 ) 1 ( 0 1 0 ) 2 ( 1 ) , ,..., , , ( ) , ,..., 1 , ( p m c p p m m m W m k f m m k k f

∑

= − − − − − − ⋅ = 1 0 1 0 2 1 0 ) 1 ( 1 2 0 ) ( 1 ) , ,..., , ( ) , ,..., 1 , ( p m cp p p p p p _{k k k k f k k k m W} f

Illustrazione 3 17: Grafico a farfalla: le sbarrette e le frecce indicano le componenti del vettore intermedio precedente che entrano in gioco per il calcolo del successivo. Se la sbarretta termina senza freccia la componente del vettore intermedio precedente va moltiplicata per W0; con la freccia va moltiplicata per Wq indicato. Secondo la terminologia usata: f(0)_{(0)=f(0)[17].}

La trasformata di Fourier gode di molte proprietà, in particolare è interessante notare che una traslazione della variabile corrisponde nel dominio della frequenza alla moltiplicazione per un esponenziale complesso.

Si definiscef(m)⇔ F(k) F(k) è la trasformata di Fourier di f(m) e si esegue una traslazione della variabile m che diventa m→m-x0: la trasformata di Fourier di f(m-x0) è data da:

Questa formula è valida anche per le trasformate bidimensionali, quindi definendo f(m,n)⇔ F(k,h), allora:

In questo modo si riesce ad ottenere immediatamente la direzione dello spostamento bidimensionale.

La trasformata di Fourier bidimensionale si calcola applicando la trasformata di Fourier monodimensionale alle righe e alle colonne di una matrice M x N. Inoltre non è necessario che si segua un ordine preciso, si può applicare la trasformata prima alle colonne e poi alle righe: il risultato è sempre lo stesso. Quindi data una matrice M x N si può applicare la trasformata partendo dalle righe e ottenere:

e successivamente applicare la trasformazione anche alle colonne:

Ottenendo così una trasformata bidimensionale di Fourier.

Applicando la trasformata bidimensionale ai blocchi fc(m,n) dell’immagine corrente e al blocco fr(m,n) del frame di riferimento, si ottiene rispettivamente Fc(k,h) e Fr(k,h). Dove le due immagini saranno in

M x k i e k F x m f( − ₀)⇔ ( )⋅ − ⋅2π⋅ ⋅ 0 ) ( 2 0 0 0 0 ) , ( ) , ( N y h M x k i e h k F y n x m f − − ⇔ ⋅ − ⋅ π⋅ ⋅ + ⋅

∑

= ⋅ ⋅ ⋅ − ⋅ = N n n N h i R _{m h f m n e} F 0 2 ) ( _{( , ) ( , )} π

∑

− = ⋅ + ⋅ ⋅ ⋅ − ⋅ = 1 0 ) ( 2 ) , ( ) , ( M m n N h m M k i e n m f h k F π

relazione tra di loro perché una è l’equivalente dell’altra, ma traslata rispetto alle variabili spaziali. Quindi

dove lo spostamento è dato da (x0 , y0). Per ricavare tali valori è necessario eliminare il modulo della trasformata allo scopo di valutare solo la fase e quindi ricavare lo spostamento:

In realtà questa operazione non è necessaria perché calcolando la FFT discreta bidimensionale, si ottengono già due matrici, una per la parte reale del modulo e una per quella immaginaria, che descrive la fase dell’esponenziale complesso. Quindi l’operazione di divisione non è necessaria, basta effettuare una somma di due matrici[17]. Per stimare il vettore di moto è però necessario cercare il massimo della matrice della fase. La complessità del calcolo della trasformata bidimensionale è doppia rispetto a quella della trasformata monodimensionale e quindi equivale a:

N

N log₂

4⋅ ⋅ _{. A tale valore bisogna però aggiungere il tempo necessario per}

la somma delle due matrici della fase e il tempo per la ricerca del massimo.

Questo tipo di algoritmo è molto veloce ed efficiente, ma prevede che i dati delle immagini siano presenti in memoria. Inoltre sarebbe necessario memorizzare non solo le immagini, ma anche le loro trasformate, che in termini di dimensioni, sono identiche a le immagini originali. Quindi l’algoritmo non si presta ad essere implementato nel nostro caso, a causa delle limitazioni sull’utilizzo della memoria esterna.

) ( 2 0 0 ) , ( ) . ( N y h M x k i c r kh F k h e F = ⋅ − ⋅ π⋅ ⋅ + ⋅ ) ( 2 * * _{0 0} ) , ( ) . ( ) , ( ) . ( h_Ny M x k i r c r c _e h k F h k F h k F h k F _{⋅ ⋅} ⋅ ₊ ⋅ = ⋅ ⋅ π

3.1.7 - Algoritmo di ricerca gerarchica o piramidale.

L’algoritmo gerarchico per la rivelazione del movimento delle immagini, chiamato anche a piramide, utilizza una combinazione di strategie di ricerca per localizzare il minino dell’algoritmo SAD. Questo algoritmo prevede di filtrare e sotto-campionare l’immagine iniziale una o più volte a seconda del numero ci passi che si vogliono ottenere. Data l’immagine iniziale, questa viene filtrata e sotto-campionata di fattore due. Si ottiene quindi una nuova immagine del tutto simile a quella iniziale ma di dimensioni dimezzate. Si può pensare di sotto-campionare l’immagine k volte. All’ultimo passo si stimano i vettori di movimento dell’immagine sotto-campionata k volte con dei blocchi di dimensione opportuna, anche esse sotto-campionati; solitamente, assieme alla dimensione della immagine vengono scalati anche i blocchi. In questo modo è possibile effettuare una ricerca con blocchi di piccole dimensioni ma che coprono una vasta superficie dell'immagine reale.

Trovato il vettore movimento per il sotto-blocco, utilizzando l’algoritmo SAD o qualsiasi altro metodo, viene mandato al blocco successivo moltiplicato per due (fattore di sotto-campionamento scelto per le immagini). Al passo successivo si stimano i vettori di moto per il blocco che ha dimensioni doppie rispetto al precedente ed è centrato rispetto al vettore di moto stimato al passo precedente, moltiplicato per due. In questo caso si riduce l'area di ricerca a ± 1 pixel rispetto al blocco. Questo algoritmo riduce ulteriormente il numero di punti su cui si calcola il SAD,

infatti per ogni macro-blocco basta confrontare 180) ₁₆ 4 2 ( p ₊ 2_⋅ M ⋅N     ⋅ pixel[15].