algorithm
Dynamic Time Warping

Introduzione al Dynamic Time Warping

Dynamic Time Warping (DTW) è un algoritmo per misurare la somiglianza tra due sequenze temporali che possono variare in velocità. Per esempio, le somiglianze nella deambulazione potrebbero essere rilevate usando DTW, anche se una persona camminava più velocemente dell'altra o se c'erano state accelerazioni e decelerazioni nel corso di un'osservazione. Può essere utilizzato per abbinare un comando vocale campione con un comando di altri, anche se la persona parla più velocemente o più lentamente della voce campione preregistrata. DTW può essere applicato a sequenze temporali di dati video, audio e grafici, infatti, qualsiasi dato che può essere trasformato in una sequenza lineare può essere analizzato con DTW.

In generale, DTW è un metodo che calcola una corrispondenza ottimale tra due sequenze date con alcune restrizioni. Ma atteniamoci ai punti più semplici qui. Diciamo che abbiamo due sequenze vocali campione e test e vogliamo verificare se queste due sequenze corrispondono o no. Qui la sequenza vocale si riferisce al segnale digitale convertito della tua voce. Potrebbe essere l'ampiezza o la frequenza della tua voce che denota le parole che dici. Assumiamo:

Sample = {1, 2, 3, 5, 5, 5, 6}
Test   = {1, 1, 2, 2, 3, 5}

Vogliamo scoprire la corrispondenza ottimale tra queste due sequenze.

Inizialmente, definiamo la distanza tra due punti, d (x, y) dove x e y rappresentano i due punti. Permettere,

d(x, y) = |x - y|     //absolute difference

Creiamo una tabella a matrice 2D usando queste due sequenze. Calcoleremo le distanze tra ogni punto del campione con ogni punto del test e troveremo la corrispondenza ottimale tra di essi.

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   1  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

Qui, Table [i] [j] rappresenta la distanza ottimale tra due sequenze se consideriamo la sequenza fino a Sample [i] e Test [j] , considerando tutte le distanze ottimali che abbiamo osservato prima.

Per la prima riga, se non prendiamo valori da Sample , la distanza tra questo e Test sarà infinita . Quindi mettiamo l' infinito sulla prima riga. Lo stesso vale per la prima colonna. Se non prendiamo alcun valore da Test , anche la distanza tra questa e Sample sarà infinita. E la distanza tra 0 e 0 sarà semplicemente 0 . Noi abbiamo,

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

Ora per ogni passaggio, considereremo la distanza tra ogni punto in pericolo e lo aggiungeremo alla distanza minima che abbiamo trovato finora. Questo ci darà la distanza ottimale di due sequenze fino a quella posizione. La nostra formula sarà,

Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])

Per il primo, d (1, 1) = 0 , Table [0] [0] rappresenta il minimo. Quindi il valore di Table [1] [1] sarà 0 + 0 = 0 . Per il secondo, d (1, 2) = 0 . Tabella [1] [1] rappresenta il minimo. Il valore sarà: Tabella [1] [2] = 0 + 0 = 0 . Se continuiamo in questo modo, dopo aver terminato, la tabella sarà simile a:

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |   0  |   0  |   1  |   2  |   4  |   8  |
+------+------+------+------+------+------+------+------+
|   2  |  inf |   1  |   1  |   0  |   0  |   1  |   4  |
+------+------+------+------+------+------+------+------+
|   3  |  inf |   3  |   3  |   1  |   1  |   0  |   2  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |   7  |   7  |   4  |   4  |   2  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  11  |  11  |   7  |   7  |   4  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  15  |  15  |  10  |  10  |   6  |   0  |
+------+------+------+------+------+------+------+------+
|   6  |  inf |  20  |  20  |  14  |  14  |   9  |   1  |
+------+------+------+------+------+------+------+------+

Il valore di Table [7] [6] rappresenta la distanza massima tra queste due sequenze date. Qui 1 rappresenta la distanza massima tra Sample e Test è 1 .

Ora se torniamo indietro dall'ultimo punto, fino al punto di partenza (0, 0) , otteniamo una lunga linea che si muove orizzontalmente, verticalmente e diagonalmente. La nostra procedura di backtracking sarà:

if Table[i-1][j-1] <= Table[i-1][j] and Table[i-1][j-1] <= Table[i][j-1]
    i := i - 1
    j := j - 1
else if Table[i-1][j] <= Table[i-1][j-1] and Table[i-1][j] <= Table[i][j-1]
    i := i - 1
else
    j := j - 1
end if

Continueremo fino a raggiungere (0, 0) . Ogni mossa ha il suo significato:

• Una mossa orizzontale rappresenta la cancellazione. Ciò significa che la nostra sequenza di test è accelerata durante questo intervallo.
• Una mossa verticale rappresenta l'inserimento. Ciò significa che la sequenza di test è decelerata durante questo intervallo.
• Una mossa diagonale rappresenta la corrispondenza. Durante questo periodo Test e campione erano uguali.

Il nostro pseudo-codice sarà:

Procedure DTW(Sample, Test):
n := Sample.length
m := Test.length
Create Table[n + 1][m + 1]
for i from 1 to n
    Table[i][0] := infinity
end for
for i from 1 to m
    Table[0][i] := infinity
end for
Table[0][0] := 0
for i from 1 to n
    for j from 1 to m
        Table[i][j] := d(Sample[i], Test[j])
                       + minimum(Table[i-1][j-1],      //match
                                 Table[i][j-1],        //insertion
                                 Table[i-1][j])        //deletion
    end for
end for
Return Table[n + 1][m + 1]

Possiamo anche aggiungere un vincolo di località. Cioè, richiediamo che se Sample[i] sia abbinato a Test[j] , quindi |i - j| non è più grande di w , un parametro della finestra.

Complessità:

La complessità del calcolo del DTW è O (m * n) dove m e n rappresentano la lunghezza di ciascuna sequenza. Le tecniche più veloci per l'elaborazione di DTW includono PrunedDTW, SparseDTW e FastDTW.

applicazioni:

• Riconoscimento vocale
• Analisi della potenza di correlazione