Il real-time DTW

L’algoritmo del DTW classico necessita di tutte e due le serie temporali in ingresso di cui si vuole calcolare la distanza. Questo per consentire il calcolo delle due matrici d e D utilizzando tutti i punti delle due serie.

E’ stata apportata una modifica all’algoritmo base per consentire una stima di distanza campione per campione. Naturalmente l’algoritmo risulta non utile quando la classificazione dovesse distinguere tra attività le quali, a fronte di una supervisione iniziale, risultino costituite da segnali simili soprattutto nell’ultima parte.

L’algoritmo proposto si basa sulla condizione iniziale di non conoscenza delle dimensioni della serie temporale in input, X, e con la sola conoscenza a priori del segnale di riferimento, o template, Y.

Nella nostra formulazione, le matrici d(xi, yi) e D(xi, yi) sono costruite campione per

campione, così come il corrispondente warping path e di conseguenza anche la distanza parziale tra le due serie temporali.

Questa implementazione può dunque essere sviluppate istante per istante, campione per campione e dunque in applicazione in tempo reale: chiameremo questa implementazione infatti real-time DTW (RT_DTW).

Il primo passo è la costruzione della matrice d 2x2 con le distanze corrispondenti tra punti dei due vettori e la matrice D, sempre 2x2, come sotto:

d(x, y)

=

(x

−

y

)

(x

−

y

)

(x

−

y

)

(x

−

y

)

















(1,1)

(1,1)

(1, 2)

( , )

(1,1)

(2,1)

min( (1,1), (1, 2), (2,1))

(2, 2)

d

D

d

D x y

D

d

D

D

D

d

+





=

_

_

+

+





Ad ogni step, la dimensione delle matrice d e D si incrementano, ad ogni nuovo campione, inserendovi una riga ed una colonna aggiuntive: (

Figura

Ad ogni step possiamo anche identificare tramite gli indici (i,j) il warping path cercando il minimo valore secondo la regola:

w(i,j)= min

Ad ogni step, la dimensione delle matrice d e D si incrementano, ad ogni nuovo campione, inserendovi una riga ed una colonna aggiuntive: (vedi figura 19

ura 19 - Costruzione delle matrici d e D

Ad ogni step possiamo anche identificare tramite gli indici (i,j) il warping path cercando il minimo valore secondo la regola:

min [D(i+1, j), D(i+1, j+1), D(i, j+1)]

Ad ogni step, la dimensione delle matrice d e D si incrementano, ad ogni nuovo figura 19).

e possiamo anche dare una stima di misura di distanza tra serie aggiungendo volta per volta il valore di distanza, sommando questo minimo valore lungo il warping path e creando il vettore L. Quando una delle due serie finisce, le matrici d e D si costruiscono aggiungendo una singola riga o colonna fino alla fine dell’algoritmo.

L

= Σ D

(i,j)

La principale differenza con il classico algoritmo del DTW è che, nella nostra formulazione, la distanza al tempo i-esimo non è l’ultimo elemento della matrice D(Ni,Mi), come per il DTW, ma è un valore cumulativo di distanza sull’elemento D-esimo calcolato lungo il percorso di minimizzazione all’istante i.

La dimensione del vettore L è spesso più lungo di i o j allo step corrente (i,j) e più lungo di N e M allo step finale, perché la sua dimensione eguaglia la dimensione del warping path.

Un possibile problema che può sopraggiungere durante l’esecuzione dell’algoritmo è la possibilità che durante la minimizzazione il percorso raggiunga il bordo della matrice troppo presto, e continui così in maniera non corretta la definizione del minimo percorso. Questo può essere superato inserendo alcune condizioni sulla pendenza del percorso, come proposto da Sakoe and Chiba [77]: se l’elemento w(i,j) procede in avanti nella direzione dell’asse i (o asse j) per p passi consecutivi, deve andare avanti almeno t passi in diagonale ( o lungo l’altro asse) (vedi figura 20). Nel nostro caso noi abbiamo imposto t/p = 1.

Figura 20

Uno degli svantaggi del DTW è che non si occupa di occupazione di memoria, dato che una volta note le lunghezze delle due serie temporali (N e M ), non ha bisogno di altro ma solo di allocare due matrici NxM.

ottimizzare l’algoritmo in termini di occupazione di memoria, distruggendo allo step k, caratterizzato dalla locazione (i,j), la (i

secondo la definizione di D. Per esempio, guardando la figura 21, matrice D è ancora quadrata e il

calcolata come D(w1) + D(w

Figura 21 Procedura dell’algoritmo al k p times

Figura 20 – Imposizioni al warping path

Uno degli svantaggi del DTW è che non si occupa di occupazione di memoria, dato che una volta note le lunghezze delle due serie temporali (N e M ), non ha bisogno di altro ma solo di allocare due matrici NxM. Nella nostra formulazione

ottimizzare l’algoritmo in termini di occupazione di memoria, distruggendo allo step k, caratterizzato dalla locazione (i,j), la (i-n)-esima riga e la (i

secondo la definizione di D. Per esempio, guardando la figura 21,

matrice D è ancora quadrata e il the warp path è wk(i, j) e la distanza parziale

) + D(w2) + … + D(wk).

Figura 21 Procedura dell’algoritmo al k-step t times

p times

t times

Uno degli svantaggi del DTW è che non si occupa di occupazione di memoria, dato che una volta note le lunghezze delle due serie temporali (N e M ), non ha bisogno di Nella nostra formulazione si propone di ottimizzare l’algoritmo in termini di occupazione di memoria, distruggendo allo step esima riga e la (i-n)-esima colonna, secondo la definizione di D. Per esempio, guardando la figura 21, allo step k la e la distanza parziale è

L ‘algoritmo è stato implementato in C con Visual Studio 2008, mentre la interfaccia grafica (GUI) è stata implementata con il real-time toolbox in Matlab R2007a. Nella versione finale dell’algoritmo, presentata qui, l’allocazione dinamica della memoria delle matrici 2-D si basa sulla informazione iniziale nota delle dimensioni dei segnali di riferimento, e a ogni step sia righe che colonne vengono aggiunte, mentre quelle che ad ogni passo non servono più, vengono distrutte. Questa versione è risultata preferibile rispetto alla dinamica allocazione e riallocazione di matrici 2-D di dimensioni via via crescenti ( matrici 2 x 2, 3 x 3, …, k x k).

Il tempo di esecuzione è perfettamente compatibile con una implementazione real- time.